Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Clustering Tumors by Gene Expression

English · فارسی

Clustering Tumors by Gene Expression

Computer Science Dept, Ferdowsi University of Mashhad

The question

A pathologist names a tumor by looking at tissue under a microscope. A microarray asks a different question of the same sample: which of several thousand genes are being transcribed, and how strongly. If the tissue of origin is written into that expression profile, then a clustering algorithm — which never sees the diagnosis — should be able to recover it. That is the claim this example tests, and it is a stronger claim than “the samples form groups”: it says the diagnosis is contained in the measurements.

The experiment is small enough to follow by hand, and it is a good first case study because the algorithm is ordinary k-means; all the judgement is in how the output is read.

The data

With p=6830p = 6830 and n=64n = 64 there are far more directions than points: the distances live in the regime described on the curse-of-dimensionality page. Every distance is estimated from 64 points only, so no cluster boundary here is sharp in a statistical sense.

Deciding what “similar” means

K-means needs a distance before it needs anything else, and on expression data the choice does more work than the algorithm:

Whatever is chosen must be reported: two analyses of the same matrix with different distances are two different experiments, and they can disagree completely about which samples are neighbours.

Running k-means

For a fixed KK, k-means alternates two steps until the assignment stops changing:

  1. assign each sample to its nearest centroid;

  2. move each centroid to the mean of the samples assigned to it.

The quantity it decreases is the within-cluster sum of squares

WSS(K)=∑k=1K∑x∈Ck∥x−μk∥2.\mathrm{WSS}(K) = \sum_{k=1}^{K} \sum_{x \in C_k} \lVert x - \mu_k \rVert^2 .

Two practical points that this example makes concrete:

The result

Running k-means with K=3K = 3 and then opening the envelope — counting which pathology labels landed in which cluster — gives:

ClusterBreastCNSColonK562LeukemiaMCF7MelanomaNSCLCOvarianProstateRenalUnknowntotal
135000017629134
220026272000021
32070000000009

Read it by rows, not by eye-catching cells:

A table like this — clusters against known labels — is the right way to report a clustering when labels exist, because it shows both the purity of a cluster and its mistakes. A summary that only says “the clusters correspond to tissue types” hides exactly the information a reader needs.

A label that turned out to be wrong

The two breast samples sitting inside the melanoma-dominated cluster were re-examined after the clustering. They were not breast cancers: they were melanomas that had metastasized to the breast.

This is the most valuable outcome in the whole example, and it is worth being precise about what happened. The clustering did not “discover the truth”; it produced a suspicion — these two profiles look like that group, not like the group their labels claim. A pathologist then checked, and the suspicion was confirmed. Unsupervised learning can be right against its labels, but only a follow-up investigation turns that into knowledge. Without the re-examination, the honest conclusion would have been “two samples are inconsistent with their labels, for reasons unknown”.

What k-means cannot give here

Two limits of the method show up sharply in this application:

  1. No order inside a cluster. K-means returns sets. The members of cluster 1 can only be listed alphabetically, which says nothing about which of them are most alike; a reader who wants “these nine samples form a subgroup” gets no help.

  2. No nesting across KK. The solution for K=4K = 4 need not refine the solution for K=3K = 3: clusters can be split, merged and reshuffled when KK changes. A table built for one KK cannot be extended when the number of groups is revised, so every change of KK costs a new interpretation.

Both are cured by the same change of report: hierarchical clustering returns a dendrogram, which orders the samples along a line and gives a nested family of partitions — one picture from which any number of clusters can be read off after seeing the structure. For a study like this one, where the number of groups is unknown and the ordering within a group is meaningful, the dendrogram is the more informative object; k-means is the cheaper summary. See hierarchical clustering.

Limits of the conclusion

Summary

Questions for class

  1. Why are the samples clustered and not the 6830 genes? What would a cluster of genes mean, and what would you learn from one?

  2. The table has eleven tissue types and K=3K = 3. Which types would you expect to be merged first, and does the table agree with your expectation?

  3. If the two “breast” samples had never been re-examined, what would the correct conclusion of the experiment have been?

  4. Cluster 2 mixes leukemia, K562, MCF7 and melanoma. Is that a failure of k-means, of the distance, or of forcing eleven types into three clusters?

  5. How would you check that a cluster is stable rather than an accident of the random initialization?

Exercises

  1. Compute the correlation-distance matrix of the 64×683064 \times 6830 matrix, run average-linkage hierarchical clustering, and compare the top two splits with clusters 3 and 2 above.

  2. Rerun k-means with 50 random starts and record how often the K=3K = 3 table above is reproduced exactly. What does the answer say about the reported result?

  3. Standardize the genes before clustering and compare the resulting table with the one shown. Which clusters survive the change?

  4. Plot WSS(K)\mathrm{WSS}(K) for K=1,…,10K = 1,\ldots,10. Is there an elbow? If not, state a criterion other than the elbow for choosing KK, and its cost.

Source and further reading

The data set (NCI60 tumor cell lines) and the analysis summarized above are from §14.3.8, “Example: Human Tumor Microarray Data”, pp. 512–514 of Hastie et al. (2009); the table is that section’s cross-tabulation of three k-means clusters against the pathology labels, and the two mislabelled samples are reported there. The high-dimensional setting is discussed in High-Dimensional Spaces, and the alternative report — the dendrogram — in hierarchical clustering.

References
  1. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. 10.1007/978-0-387-84858-7