Choosing a clustering method

Question

When using cluster analysis on a data set to group similar cases, one needs to choose among a large number of clustering methods and measures of distance. Sometimes, one choice might influence the other, but there are many possible combinations of methods.

Does anyone have any recommendations on how to choose among the various clustering algorithms / methods and distance measures? How is this related to the nature of the variables (e.g., categorical or numerical) and the clustering problem? Is there an optimal technique?

Answer 1

There is no definitive answer to your question, as even within the same method the choice of the distance to represent individuals (dis)similarity may yield different result, e.g. when using euclidean vs. squared euclidean in hierarchical clustering. As an other example, for binary data, you can choose the Jaccard index as a measure of similarity and proceed with classical hierarchical clustering; but there are alternative approaches, like the Mona (Monothetic Analysis) algorithm which only considers one variable at a time, while other hierarchical approaches (e.g. classical HC, Agnes, Diana) use all variables at each step. The k-means approach has been extended in various way, including partitioning around medoids (PAM) or representative objects rather than centroids (Kaufman and Rousseuw, 1990), or fuzzy clustering (Chung and Lee, 1992). For instance, the main difference between the k-means and PAM is that PAM minimizes a sum of dissimilarities rather than a sum of squared euclidean distances; fuzzy clustering allows to consider "partial membership" (we associate to each observation a weight reflecting class membership). And for methods relying on a probabilistic framework, or so-called model-based clustering (or latent profile analysis for the psychometricians), there is a great package: Mclust. So definitively, you need to consider how to define the resemblance of individuals as well as the method for linking individuals together (recursive or iterative clustering, strict or fuzzy class membership, unsupervised or semi-supervised approach, etc.).

Usually, to assess cluster stability, it is interesting to compare several algorithm which basically "share" some similarity (e.g. k-means and hierarchical clustering, because euclidean distance work for both). For assessing the concordance between two cluster solutions, some pointers were suggested in response to this question, Where to cut a dendrogram? (see also the cross-references for other link on this website). If you are using R, you will see that several packages are already available in Task View on Cluster Analysis, and several packages include vignettes that explain specific methods or provide case studies.

Cluster Analysis: Basic Concepts and Algorithms provides a good overview of several techniques used in Cluster Analysis. As for a good recent book with R illustrations, I would recommend chapter 12 of Izenman, Modern Multivariate Statistical Techniques (Springer, 2008). A couple of other standard references is given below:

• Cormack, R., 1971. A review of classification. Journal of the Royal Statistical Society, A 134, 321–367.
• Everitt, B., 1974. Cluster analysis. London: Heinemann Educ. Books.
• Gordon, A., 1987. A review of hierarchical classification. Journal of the Royal Statistical Society, A 150, 119–137.
• Gordon, A., 1999. Classification, 2nd Edition. Chapman and Hall.
• Kaufman, L., Rousseuw, P., 1990. Finding Groups in Data: An Introduction to Cluster Analysis. New York, Wiley.

Answer 2

A quote from Hastie, Tibshirani and Friedman, Elements of Statistical Learning, p. 506:

"An appropriate dissimilarity measure is far more important in obtaining success with clustering than choice of clustering algorithm. This aspect of the problem ... depends on domain specific knowledge and is less amenable to general research."

(That said, wouldn't it would be nice if (wibni) there were a site where students could try a few algorithms and metrics on a few small standard datasets ?)

Answer 3

You can't know in advance which clustering algorithm would be better, but there are some clues, for example if you want to cluster images there are certain algorithms you should try first like Fuzzy Art, or if you want to group faces you should start with (GGCI) global geometric clustering for image.

Anyway this does not guarantee the best result, so what I would do is use a program that allows you to methodically run different cluster algorithms, such as weka, RapidMiner or even R (which is non visual), There I will set the program to launch all the different clustering algorithms I can, with all the possible different distances, and if they need parameters, experiment each one with a variety of different parameter values (besides if I do not know the amount of clusters, run each one with a variety of numbers of it). Once you settled the experiment, leave it running, but remember to store somewhere the results of each clustering run.

Then compare the results in order to obtain the best resulting clustering. This is tricky because there are several metrics you can compare and not all are provided by every algorithm. For example fuzzy clustering algorithms have different metrics than non-fuzzy, but they can still be compared by considering the fuzzy resulting groups as non-fuzzy, I will stick for the comparison to the classic metrics such as:

• SSE: sum of the square error from the items of each cluster.

• Inter cluster distance: sum of the square distance between each cluster centroid.

• Intra cluster distance for each cluster: sum of the square distance from the items of each cluster to its centroid.

• Maximum Radius: largest distance from an instance to its cluster centroid.

• Average Radius: sum of the largest distance from an instance to its cluster centroid divided by the number of clusters.

Answer 4

Choosing the right distance is not an elementary task. When we want to make a cluster analysis on a data set, different results could appear using different distances, so it's very important to be careful in which distance to choose because we can make a false good artefact that capture well the variability, but actually without sense in our problem.

The Euclidean distance is appropriate when I have continuous numerical variables and I want to reflect absolute distances. This distance takes into account every variable and doesn’t remove redundancies, so if I had three variables that explain the same (are correlated), I would weight this effect by three. Moreover, this distance is not scale invariant, so generally I have to scale previously to use the distance.
Example ecology: We have different observations from many localities, of which the experts have taken samples of some microbiological, physical and chemical factors. We want to find patterns in ecosystems. These factors have a high correlation, but we know everyone is relevant, so we don’t want to remove these redundancies. We use the Euclidean distance with scaled data to avoid the effect of units.

The Mahalanobis distance is appropriate when I have continuous numerical variables and I want to reflect absolute distances, but we want to remove redundancies. If we have repeated variables, their repetitious effect will disappear.

The family Hellinger, Species Profile and Chord distance are appropriate when we want to make emphasis on differences between variables, when we want to differentiate profiles. These distances weights by total quantities of each observation, in such a way that the distances are small when variable by variable the individuals are more similar, although in absolute magnitudes was very different. Watch out! These distances reflect very well the difference between profiles, but lost the magnitude effect. They could be very useful when we have different sample sizes. Example ecology: We want to study the fauna of many lands and we have a data matrix of an inventory of the gastropod (sampling locations in rows and species names in columns). The matrix is characterized by having many zeros and different magnitudes because some localities have some species and others have other species. We could use Hellinger distance.

Bray-Curtis is quite similar, but it’s more appropriate when we want to differentiate profiles and also take relative magnitudes into account.

Answer 5

Here is a summary of several clustering algorithms that can help to answer the question

"which clustering technique i should use?"

There is no objectively "correct" clustering algorithm Ref

Clustering algorithms can be categorized based on their "cluster model". An algorithm designed for a particular kind of model will generally fail on a different kind of model. For eg, k-means cannot find non-convex clusters, it can find only circular shaped clusters.

Therefore, understanding these "cluster models" becomes the key to understanding how to choose among the various clustering algorithms / methods. Typical cluster models include:

[1] Connectivity models: Builds models based on distance connectivity. Eg hierarchical clustering. Used when we need different partitioning based on tree cut height. R function: hclust in stats package.

[2] Centroid models: Builds models by representing each cluster by a single mean vector. Used when we need crisp partitioning (as opposed to fuzzy clustering described later). R function: kmeans in stats package.

[3] Distribution models: Builds models based on statistical distributions such as multivariate normal distributions used by the expectation-maximization algorithm. Used when cluster shapes can be arbitrary unlike k-means which assumes circular clusters. R function: emcluster in the emcluster package.

[4] Density models: Builds models based on clusters as connected dense regions in the data space. Eg DBSCAN and OPTICS. Used when cluster shapes can be arbitrary unlike k-means which assumes circular clusters.. R function dbscan in package dbscan.

[5] Subspace models: Builds models based on both cluster members and relevant attributes. Eg biclustering (also known as co-clustering or two-mode-clustering). Used when simultaneous row and column clustering is needed. R function biclust in biclust package.

[6] Group models: Builds models based on the grouping information. Eg collaborative filtering (recommender algorithm). R function Recommender in recommenderlab package.

[7] Graph-based models: Builds models based on clique. Community structure detection algorithms try to find dense subgraphs in directed or undirected graphs. Eg R function cluster_walktrap in igraph package.

[8] Kohonen Self-Organizing Feature Map: Builds models based on neural network. R function som in the kohonen package.

[9] Spectral Clustering: Builds models based on non-convex cluster structure, or when a measure of the center is not a suitable description of the complete cluster. R function specc in the kernlab package.

[10] subspace clustering : For high-dimensional data, distance functions could be problematic. cluster models include the relevant attributes for the cluster. Eg, hddc function in the R package HDclassif.

[11] Sequence clustering: Group sequences that are related. rBlast package.

[12] Affinity propagation: Builds models based on message passing between data points. It does not require the number of clusters to be determined before running the algorithm. It is better for certain computer vision and computational biology tasks, e.g. clustering of pictures of human faces and identifying regulated transcripts, than k-means, Ref Rpackage APCluster.

[13] Stream clustering: Builds models based on data that arrive continuously such as telephone records, financial transactions etc. Eg R package BIRCH [https://cran.r-project.org/src/contrib/Archive/birch/]

[14] Document clustering (or text clustering): Builds models based on SVD. It has used in topic extraction. Eg Carrot [http://search.carrot2.org] is an open source search results clustering engine which can cluster documents into thematic categories.

[15] Latent class model: It relates a set of observed multivariate variables to a set of latent variables. LCA may be used in collaborative filtering. R function Recommender in recommenderlab package has collaborative filtering functionality.

[16] Biclustering: Used to simultaneously cluster rows and columns of two-mode data. Eg R function biclust in package biclust.

[17] Soft clustering (fuzzy clustering): Each object belongs to each cluster to a certain degree. Eg R Fclust function in the fclust package.

Answer 6

As far as I'm concerned, if you want a safe choice, spectral clustering methods have been achieving the highest accuracy rates in recent years - at least in image clustering.

As for the distance metric, it depends a lot on how your data is organized. The safe choice is the simple euclidean distance but if you know your data contains manifolds, you should map the points via kernel methods.

PS: they're all related to numerical values, not categorical. I'm not sure how one would go about clustering categorical data.