Choosing 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 and distance measures? How is this related to the nature of the variables (e.g., categorical or numerical) and the clustering problem? Is there are 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.