Given \(n\) objects, assign them to \(k\) groups (clusters) based on their similarity

• Do not explicitly model the underlying biology
• Clusters are mutually exclusive, while in reality a gene may be a part of multiple biological processes

• Scale-invariance - meters vs. inches
• Richness - all partitions as possible solutions
• Consistency - increasing distances between clusters and decreasing distances within clusters should yield the same solution

No function exists that satisfies all three.

J. Kleinberg. “An Impossibility Theorem for Clustering. Advances in Neural Information Processing Systems” (NIPS) 15, 2002. https://www.cs.cornell.edu/home/kleinber/nips15.pdf

• Two categories:
  • Heuristic algorithms
    • No probabilistic model
    • Optimizing a certain target function or iteratively agglomerating (or dividing) nodes to form bottom-up (top-down) trees
    • Examples: K-means, hierarchical clustering
  • Model-based analyses
    • Probabilistic assumptions about the data
    • Expectation Maximization algorithm

• Partitioning methods
• Hierarchical methods
• Model based methods
• Density-based methods
• Grid-based methods

• Most important is selecting the variables on which the clustering is based.

• Inclusion of even one or two irrelevant variables may distort a clustering solution.

• Variables selected should describe the similarity between objects in terms that are relevant to the marketing research problem.

• Should be selected based on past research, theory, or a consideration of the hypotheses being tested.

• Non-informative genes contribute random terms in the calculation of distances

• The resulting effect is that they hide the useful information provided by other genes

• Therefore, assign non-informative genes zero weight, i.e., exclude them from the cluster analysis

• % Present >= X - remove all genes that have missing values in greater than (100-X) percent of the columns

• SD (Gene Vector) >= X - remove all genes that have standard deviations of observed values less than X

• At least X Observations with abs(Val) >= Y - remove all genes that do not have at least X observations with absolute values greater than Y

• MaxVal-MinVal >= X - remove all genes whose maximum minus minimum values are less than X

Clustering works as expected when the data to be clustered is processed correctly

• Log Transform Data - replace all data values x by log2 (x). Why?

• Center genes [mean or median] - subtract the row-wise mean or median from the values in each row of data, so that the mean or median value of each row is 0.

• Center samples [mean or median] - subtract the column-wise mean or median from the values in each column of data, so that the mean or median value of each column is 0.

Clustering works as expected when the data to be clustered is processed correctly

• Normalize genes - multiply all values in each row of data by a scale factor S so that the sum of the squares of the values in each row is 1.0 (a separate S is computed for each row).

• Normalize samples - multiply all values in each column of data by a scale factor S so that the sum of the squares of the values in each column is 1.0 (a separate S is computed for each column).

• Preprocessing (centering, normalization, scaling, \(log_2\)-transformation) is critical for the interpretable clustering

• Preprocessing operations are not associative, so the order in which these operations is applied is very important

• Log transforming centered genes are not the same as centering log transformed genes.

• Clustering organizes things that are close into groups

• What does it mean for two genes to be close?

• What does it mean for two samples to be close?

• Once we know this, how do we define groups?

• We need a mathematical definition of distance between two points

• What are points?

• If each gene is a point, what is the mathematical definition of a point?

For all objects \(i\), \(j\), and \(h\)

• Disadvantages: not scale invariant, not for negative correlations

• When deciding on an appropriate value of \(q\), the investigator must decide whether emphasis should be placed on large differences.

• Larger values of \(q\) give relatively more emphasis to larger differences.

• Canberra distance

• A weighted version of Manhattan distance

• Maximum distance between two vectors of \(p=(p_1,p_2,...,p_n)\) and \(q=(q_1,q_2,...,q_n)\)

• For all objects \(i\), \(j\)

• Gene expression profiles represent comparative expression measures

• Euclidean distance may not be meaningful

• Need distance measure that score based on similarity

• The more objects \(i\) and \(j\) are alike (or close) the larger \(s(i,j)\) becomes

• Measures similarity between two non-zero vectors.

• Works best when the outcome is within \([0,1]\) interval

• Frequently used in text mining

• Does not conform with the definition of distance - does not have the triangle inequality property.

From Euclidean dot product

\[a \cdot b = \left\lVert a \right\rVert_2 \left\lVert b \right\rVert_2 cos\theta\] \[similarity = cos\theta = \frac{a \cdot b}{\left\lVert a \right\rVert_2 \left\lVert b \right\rVert_2} = \frac{\sum_{i=1}^n{a_ib_i}}{\sqrt{\sum_{i=1}^n{a_i^2}} \sqrt{\sum_{i=1}^n{b_i^2}}}\]

• \(cos\theta\) ranges from -1 to 1. 0 indicates orthogonality (decorrelation)
• \(cos(0^o) = 1\) - perfect similarity. Measures orientation
• Other options - angular distance

Pearson correlation coefficient [-1, 1]

Vectors are normalized to the vector’s means

How to convert to dissimilarity [0, 1]

\[d(i,j)=(1-s(i,j))/2\]

• Jaccard distance

• Overlap coefficient

\[C = \frac{ \lvert A \cap B \rvert}{min(\lvert A \rvert, \lvert B \rvert)}\]

Both lie in the range \([0, 1]\). \(J, C = 0\) indicating no overlaps between binary vectors. A Jaccard-index \(J = 1\) indicates two identical vectors, whereas the overlap coefficient \(C = 1\) when one vector is a complete subset of the other.

• Two columns with binary data, encoded \(0\) and \(1\)
• \(a\) - number of rows where both columns are 1
• \(b\) - number of rows where this and not the other column is 1
• \(c\) - number of rows where the other and not this column is 1
• \(d\) - number of rows where both columns are 0

Jaccard distance

\[\frac{a}{a+b+c}\]

• Two columns with binary data, encoded \(0\) and \(1\)
• \(a\) - number of rows where both columns are 1
• \(b\) - number of rows where this and not the other column is 1
• \(c\) - number of rows where the other and not this column is 1
• \(d\) - number of rows where both columns are 0

Tanimoto distance

\[\frac{a+d}{a+d+2(b+c)}\]

Gower distance

J. C. Gower “A General Coefficient of Similarity and Some of Its Properties” Biometrics 1971 http://venus.unive.it/romanaz/modstat_ba/gowdis.pdf

• Idea: Use distance measure between 0 and 1 for each pair of variables: \(d_{ij}^{(f)}\)
• Aggregate: \(d(i,j)=\frac{1}{p}\sum_{i=1}^p{d_{ij}^{(f)}}\)

How to calculate distance measure for each pair of variables

• Quantitative: interval-scaled distance \(d_{ij}^{(f)}=\frac{|x_{if} - x_{jf}|}{R_f}\), where \(x_{if}\) is the value for object \(i\) in variable \(f\), and \(R_f\) is the range of variable \(f\) for all objects

• Categorical: use “1” when \(x_{if}\) and \(x_{jf}\) agree, and “0” otherwise

• Ordinal: Use normalized ranks, then like interval-scaled based on range

• Think hard about this step!
• Remember: garbage in - garbage out
• The metric that you pick should be a valid measure of the distance/similarity of genes.

Examples

• Applying correlation to highly skewed data will provide misleading results.
• Applying Euclidean distance to data measured on categorical scale will be invalid.

Other packages: cclust, e1071, flexmix, fpc, mclust, Mfuzz, class

• The number of ways to partition a set of \(n\) objects into \(k\) non-empty classes

• \(S(n,1)=1\) - one way to partition \(n\) object in to 1 group, or \(n\) disjoint groups

• \(S(n,2)=2^{n-1}-1\) - number of ways to partition \(n\) objects into two non-empty groups

• Allows organization of the clustering data to be represented in a tree (dendrogram)

• Agglomerative (Bottom Up): each observation starts as own cluster. Clusters are merged based on similarities

• Divisive (Top Down): all observations start in one cluster, and splits are performed recursively as one moves down the hierarchy.

• Idea: ensure nearby points end up in the same cluster

• Starts with as each gene in its own cluster

• Joins the two most similar clusters

• Then, joins next two most similar clusters

• Continues until all genes are in one cluster

• Starts with all genes in one cluster

• Choose split so that genes in the two clusters are most similar (maximize “distance” between clusters)

• Find next split in same manner

• Continue until all genes are in single gene clusters

• Both agglomerative and divisive are only ‘step-wise’ optimal: at each step the optimal split or merge is performed

• Outliers will irreversibly change clustering structure

Agglomerative/Bottom-Up

– Computationally simpler, and more available.

– More “precision” at bottom of tree

– When looking for small clusters and/or many clusters, use agglomerative

Divisive/Top-Down

– More “precision” at top of tree.

– When looking for large and/or few clusters, use divisive

Results ARE sensitive to choice!

• Single Linkage - join clusters whose distance between closest genes is smallest (elliptical)

• Complete Linkage - join clusters whose distance between furthest genes is smallest (spherical)

• Average Linkage - join clusters whose average distance is the smallest.

An important issue though is the form of input that is necessary to give Ward’s method. For an input data matrix, \(x\), in R’s hclust function the following command is required: hclust(dist(x)^2, method="ward") although this is not mentioned in the function’s documentation file.

Fionn Murtagh “Ward’s Hierarchical Agglomerative Clustering Method: Which Algorithms Implement Ward’s Criterion?” Journal of Classification 2014 https://link.springer.com/article/10.1007/s00357-014-9161-z