Clustering

Clustering and Classification

This page is a placeholder, or under current development; it is here principally to establish the logical framework of the site. The material on this page is correct, but incomplete.

Clustering and Classification are conceptually related statistical techniques in that clustering attempts to identify groupings in existing data and classification asks how best to assign new data into existing groups. However, the techniques that are employed are quite different. Clustering techniques find partitions such that relationships within a set are greater than between members of different sets; they are often divided into connectivity based approaches (e.g. "hierarchical clustering") and centroid based approaches (e.g. K-means), but other approaches such as density based clustering (eg. DBSCAN) or the flow-based MCL algorithm are increasingly important in our field. Classification techniques rely heavily on machine learning methods, often in a Bayesian framework: neural networks, support vector machines, hidden Markov models, decision trees etc'.

Introductory reading

Nugent & Meila (2010) An overview of clustering applied to molecular biology. Methods Mol Biol 620:369-404. (pmid: 20652512)

[ PubMed ] [ DOI ] Abstract In molecular biology, we are often interested in determining the group structure in, e.g., a population of cells or microarray gene expression data. Clustering methods identify groups of similar observations, but the results can depend on the chosen method's assumptions and starting parameter values. In this chapter, we give a broad overview of both attribute- and similarity-based clustering, describing both the methods and their performance. The parametric and nonparametric approaches presented vary in whether or not they require knowing the number of clusters in advance as well as the shapes of the estimated clusters. Additionally, we include a biclustering algorithm that incorporates variable selection into the clustering procedure. We finish with a discussion of some common methods for comparing two clustering solutions (possibly from different methods). The user is advised to devote time and attention to determining the appropriate clustering approach (and any corresponding parameter values) for the specific application prior to analysis.

Further reading and resources

McLachlan et al. (2008) Clustering. Methods Mol Biol 453:423-39. (pmid: 18712317)

[ PubMed ] [ DOI ] Abstract Clustering techniques are used to arrange genes in some natural way, that is, to organize genes into groups or clusters with similar behavior across relevant tissue samples (or cell lines). These techniques can also be applied to tissues rather than genes. Methods such as hierarchical agglomerative clustering, k-means clustering, the self-organizing map, and model-based methods have been used. This chapter focuses on mixtures of normals to provide a model-based clustering of tissue samples (gene signatures) and gene profiles.

van Dongen & Abreu-Goodger (2012) Using MCL to extract clusters from networks. Methods Mol Biol 804:281-95. (pmid: 22144159)

[ PubMed ] [ DOI ] Abstract MCL is a general purpose cluster algorithm for both weighted and unweighted networks. The algorithm utilises network topology as well as edge weights, is highly scalable and has been applied in a wide variety of bioinformatic methods. In this chapter, we give protocols and case studies for clustering of networks derived from, respectively, protein sequence similarities and gene expression profile correlations.

Alonzo & Pepe (2007) Development and evaluation of classifiers. Methods Mol Biol 404:89-116. (pmid: 18450047)

[ PubMed ] [ DOI ] Abstract Diagnostic tests, medical tests, screening tests, biomarkers, and prediction rules are all types of classifiers. This chapter introduces methods for classifier development and evaluation. We first introduce measures of classification performance including sensitivity, specificity, and receiver operating characteristic (ROC) curves. We then review some issues in the design of studies to assess and compare the performance of classifiers. Approaches for using the data to estimate and compare classifier accuracy are then introduced. Next, methods for combining multiple classifiers into a single classifier are presented. Lastly, we discuss other important aspects of classifier development and evaluation. The methods presented are illustrated with real data.