Processing math: 55%

Clustering QC

Mikhail Dozmorov

Fall 2016

Assess cluster fit and stability

Most often ignored.
Cluster structure is treated as reliable and precise
BUT! Clustering is generally VERY sensitive to noise and to outliers
Measure cluster quality based on how “tight” the clusters are.
Do genes in a cluster appear more similar to each other than genes in other clusters?

Clustering evaluation methods

Sum of squares
Homogeneity and Separation
Cluster Silhouettes and Silhouette coefficient: how similar genes within a cluster are to genes in other clusters
Rand index
Gap statistics
Cross-validation

Sum of squares

A good clustering yields clusters where genes have small within-cluster sum-of-squares (and high between-cluster sum-of-squares).

Homogeneity

Homogeneity is calculated as the average distance between each gene expression profile and the center of the cluster it belongs to

$H_{k}=\frac{1}{N_g} \sum_{i \in k} d(X_i,C(X_i))$

$N_g$ - total number of genes in the cluster

Separation

– Separation is calculated as the weighted average distance between cluster centers

$S_{ave}=\frac{1}{\sum_{k \neq l}{N_kN_l}} \sum_{k \neq l}{N_kN_ld(C_k,C_l)}$

Homogeneity and separation

– Homogeneity reflects the compactness of the clusters while S reflects the overall distance between clusters
– Decreasing Homogeneity or increasing Separation suggest an improvement in the clustering results

Variance Ratio Criterion (VCR)

$VRC_k=(SS_B/(K-1))/(SS_W/(N-K))$

$SS_B$ – between-cluster variation
$SS_W$ – within-cluster variation

The goal is to maximize $VRC_k$ over the clusters

$\kappa_k=(VRC_{k+1} - VRC_k) - (VRC_k - VRC_{k-1})$

Select K to minimize the value of kappaK
Calinski & Harabasz (1974)

Silhouette

Good clusters are those where the genes are close to each other compared to their next closest cluster.

$s(i)=\frac{b(i)-a(i)}{max(a(i),b(i))}$

$b(i) = min(AVGD_{BETWEEN}(i,k))$
$a(i) = AVGD_{WITHIN}(i)$
How well observation $i$ matches the cluster assignment. Ranges $-1 < s(i) < 1$
Overall silhouette: $SC=\frac{1}{N_g}\sum_{i=1}^{N_g}{s(i)}$
Rousseeuw, Peter J. “Silhouettes: A Graphical Aid to the Interpretation and Validation of Cluster Analysis.” Journal of Computational and Applied Mathematics 1987 http://www.sciencedirect.com/science/article/pii/0377042787901257

Silhouette plot

The silhouette plot displays a measure of how close each point in one cluster is to points in the neighboring clusters.
Silhouette width near +1 indicates points that are very distant from neighboring clusters
Silhouette width near 0 indicate points that are not distinctly in one cluster or another
Negative width indicates points are probably assigned to the wrong cluster.

Rand index

Cluster multiple times

Clustering A: 1, 2, 2, 1, 1
Clustering B: 2, 1, 2, 1, 1

Compare pairs

$a: \; = \; and \; =$ , the number of pairs assigned to the same cluster in A and in B
$b: \; \neq \; and \; \neq$ , … different clusters in A and in B
$c: \; \neq \; and \; =$ , … same in A, different in B
$d: \; = \; and \; \neq$ , … same in B, different in A

Rand index

$R=\frac{a+b}{a+b+c+d}$

Adjust the Rand index to make it vary between -1 and 1 (negative if less than expected)
$AdjRand = (Rand – expect(Rand)) / (max(Rand) – expect(Rand))$

Gap statistics

Cluster the observed data, varying the total number of clusters $k=1, 2, ... K$
For each cluster, calculate the sum of the pairwise distances for all points

$D_r=\sum_{i,i' \in C_r}{d_{ii'}}$

Calculate within-cluster dispersion measures

$W_k=\sum_{r=1}^k{\frac{1}{2n_r}D_r}$

Gap statistics

Cross-validation approaches

Cluster while leave-out $k$ experiments (or genes)
Measure how well cluster groups are preserved in left out experiment(s)
Or, measure agreement between test and training set

Clustering validity

Hypothesis: if the clustering is valid, the linking of objects in the cluster tree should have a strong correlation with the distances between objects in the distance vector

WADP - robustness of clustering

If the input data deviate slightly from their current value, will we get the same clustering?
– Important in Microarray expression data analysis because of constant noise

Bittner M. et.al. "Molecular classification of cutaneous malignant melanoma by gene expression profiling" Nature 2000 http://www.nature.com/nature/journal/v406/n6795/full/406536A0.html

WADP - robustness of clustering

Perturb each original gene expression profile by $N(0, 0.01)$
Re-normalize the data, cluster
Cluster-specific discrepancy rate: $D/M$ . That is, for the $M$ pairs of genes in an original cluster, count the number of gene pairs, $D$ , that do not remain together in the clustering of the perturbed data, and take their ratio.
The overall discrepancy ratio is the weighted average of the cluster-specific discrepancy rates.

WADP - robustness of clustering

If there were originally $m_j$ genes in the cluster $j$ , then there are $M_j=m_j(m_j-1)/2$ pairs of genes
In the new clustering, identify how many of these paris ( $D_j$ ) still remain in the cluster
Calculate $D_j/M_j$

$WADP=\frac{\sum_{j=1}^k{m_jD_j/M_j}}{\sum_{j=1}^k{m_j}}$

Summary

Clustering pitfalls

Any data – even noise – can be clustered
It is quite possible for there to be several different classifications of the same set of objects.
It should be clear that any clustering produced should be related to the features in which the investigator in interested.