# How to select a clustering method? How to validate a cluster solution (to warrant the method choice)?

One of the biggest issue with cluster analysis is that we may happen to have to derive different conclusion when base on different clustering methods used (including different linkage methods in hierarchical clustering).

I would like to know your opinion on this - which method will you select, and how. One might say "the best method of clustering is which gives you the right answer"; but I may question in response that cluster analysis is supposed to be an unsupervised technique - so how do I know which method or linkage is the right answer?

In general: is a clustering alone robust enough to rely on? Or we need a second method and get a shared result to be based on both?

My question is not only about possible ways to validate / evaluate clustering performance, but is broader - on what basis do we select/prefer one clustering method/algorithm over another one. Also, is there common warnings that we should look around when we are selecting a method to cluster our data?

• Check also this similar question. May 4, 2016 at 10:24
• And this one. Jun 7, 2016 at 12:16
• Some links specifically about internal and external validation: this. And this. And that. And that. And that. And this. And yonder. And search for more. Jun 24, 2016 at 18:29

Often they say that there is no other analytical technique as strongly of the "as you sow you shall mow" kind, as cluster analysis is.

I can imagine of a number dimensions or aspects of "rightness" of this or that clustering method:

1. Cluster metaphor. "I preferred this method because it constitutes clusters such (or such a way) which meets with my concept of a cluster in my particular project". Each clustering algorithm or subalgorithm/method implies its corresponding structure/build/shape of a cluster. In regard to hierarchical methods, I've observed this in one of points here, and also here. I.e. some methods give clusters that are prototypically "types", other give "circles [by interest]", still other "[political] platforms", "classes", "chains", etc. Select that method which cluster metaphor suits you. For example, if I see my customer segments as types - more or less spherical shapes with compaction(s) in the middle I'll choose Ward's linkage method or K-means, but never single linkage method, clearly. If I need a focal representative point I could use medoid method. If I need to screen points for them being core and peripheral representatives I could use DBSCAN approach.

2. Data/method assumptions. "I preferred this method because my data nature or format predispose to it". This important and vast point is also mentioned in my link above. Different algorithms/methods may require different kind of data for them or different proximity measure to be applied to the data, and vice versa, different data may require different methods. There are methods for quantitative and methods for qualitative data. Mixture quantitative + qualitative features dramatically narrows the scope of choice among methods. Ward's or K-means are based - explicitly or implicitly - on (squared) euclidean distance proximity measure only and not on arbitrary measure. Binary data may call for special similarity measures which in turn will strongly question using some methods, for example Ward's or K-means, for them. Big data may need special algorithms or special implementations.

3. Internal validity. "I preferred this method because it gave me most clear-cut, tight-and-isolated clusters". Choose algorithm/method that shows the best results for your data from this point of view. The more tight, dense are clusters inside and the less density is outside of them (or the wider apart are the clusters) - the greater is the internal validity. Select and use appropriate internal clustering criteria (which are plenty - Calinski-Harabasz, Silhouette, etc etc; sometimes also called "stopping rules") to assess it. [Beware of overfitting: all clustering methods seek to maximize some version of internal validity$$^1$$ (it's what clustering is about), so high validity may be partly due to random peculiarity of the given dataset; having a test dataset is always beneficial.]

4. External validity. "I preferred this method because it gave me clusters which differ by their background or clusters which match with the true ones I know". If a clustering partition presents clusters which are clearly different on some important background (i.e. not participated in the cluster analysis) characteristics then it is an asset for that method which produced the partition. Use any analysis which applies to check the difference; there also exist a number of useful external clustering criteria (Rand, F-measure, etc etc). Another variant of external validation case is when you somehow know the true clusters in your data (know "ground truth"), such as when you generated the clusters yourself. Then how accurately your clustering method is able to uncover the real clusters is the measure of external validity.

5. Cross-validity. "I preferred this method because it is giving me very similar clusters on equivalent samples of the data or extrapolates well onto such samples". There are various approaches and their hybrids, some more feasible with some clustering methods while others with other methods. Two main approaches are stability check and generalizability check. Checking stability of a clustering method, one randomly splits or resamples the data in partly intersecting or fully disjoint sets and does the clustering on each; then matches and compares the solutions wrt some emergent cluster characteristic (for example, a cluster's central tendency location) whether it is stable across the sets. Checking generalizability implies doing clustering on a train set and then using its emergent cluster characteristic or rule to assign objects of a test set, plus also doing clustering on the test set. The assignment result's and the clustering result's cluster memberships of the test set objects are compared then.

6. Interpretation. "I preferred this method because it gave me clusters which, explained, are most persuasive that there is meaning in the world". It's not statistical - it is your psychological validation. How meaningful are the results for you, the domain and, possibly audience/client. Choose method giving most interpretable, spicy results.

7. Gregariousness. Some researches regularly and all researches occasionally would say "I preferred this method because it gave with my data similar results with a number of other methods among all those I probed". This is a heuristic but questionable strategy which assumes that there exist quite universal data or quite universal method.

Points 1 and 2 are theoretical and precede obtaining the result; exclusive relying on these points is the haughty, self-assured exploratory strategy. Points 3, 4 and 5 are empirical and follow the result; exclusive relying on these points is the fidgety, try-all-out exploratory strategy. Point 6 is creative which means that it denies any result in order to try to rejustify it. Point 7 is loyal mauvaise foi.

Points 3 through 7 can also be judges in your selection of the "best" number of clusters.

$$^1$$ A concrete internal clustering criterion is itself not "orthogonal to" a clustering method (nor to the data kind). This raises a philosophical question to what extent such a biased or prejudiced criterion can be of utility (see answers just noticing it).

• I really like the internal validity measures, like the sum of intra-cluster variances in K-means and Ward hierarchical clustering, as well as Dunn indices. They are data-independent, and sometimes even independent on clustering algorithm, even though some of them only make sense with specific algorithms. Feb 14, 2016 at 3:58
• @DouglasDeRizzoMeneghetti I disagree. They are neither data-independent (they make very strong assumptions on your data, such as linearity and equivalence of attributes) nor independent of the clustering algorithm. In fact, every internal measure is a clustering algorithm of its own (you could optimize for this function - its just usually too expensive to do). Feb 14, 2016 at 20:32
• I understand that some internal validity measures, like the sum of intra-cluster variances, have better results if the cluster memberships were acquired through a clustering method that tends to minimize the sum of intra-cluster variances, and that a validity measure like the Dunn indexes assume good clusters are compact and far apart (even though the interpretations of "compact" and "far apart" are left open to interpretation), but the fact that you can calculate these measures with only the feature values and the cluster memberships of the elements make them quite versatile. Feb 15, 2016 at 3:07

There are mostly red flag criteria. Properties of data that tell you that a certain approach will fail for sure.

1. if you have no idea what your data means stop analyzing it. you are just guessing animals in clouds.

2. if attributes vary in scale and are nonlinear or skewed. this can ruin your analysis unless you have a very good idea of appropriate normalization. Stop and learn to understand your features, it is too early to cluster.

3. if every attribute is equivalent (same scale), and linear, and you want to quantize your data set (and least-squared error has a meaning for your data), then k-means is worth a try. If your attributes are of different kind and scale, the result is not well-defined. Counterexample: age and income. Income is very skewed, and x years = y dollar is nonsense.

4. if you have a very clear idea of how to quantify similarity or distance (in a meaningful way; the ability to compute some number is not enough) then hierarchical clustering and DBSCAN are a good choice. If you don't have any idea how to quantify similarity, solve that problem first.

You see that the most common problem is that people attempt to dump their raw data into clustering, when they first need to understand and normalize it, and figure out similarity.

Examples:

1. Pixels of an image in RGB space. Least-squares makes some sense and all attributes are comparable - k-means is a good choice.

2. Geographic data: least-squares is not very appropriate. there will be outliers. but distance is very meaningful. Use DBSCAN if you have a lot of noise, or HAC (hierarchical agglomerative clustering) if you have very clean data.

3. Species observed in different habitats. Least-squares is dubious, but e. g. Jaccard similarity is meaningful. You probably have only few observations and no "false" habitats - use HAC.

• In pts 2,3 you say (non)linear attributes. What do you mean? In what way a "linear" attribute? or you are you speaking of linear relationships, i.e. ellipsoid (and not curved) shapes of clusters? Mar 5, 2016 at 8:18
• Data with e.g. an exponential distribution. Mar 5, 2016 at 8:42
• Then I thing that you definitely have to define it in the text, for clarity, and to explain (with few words and/or link) why exponentially distributed variable is inappropriate for cluster analysis. Thank you. Mar 5, 2016 at 8:52
• I'm not proving anything here, but giving my opinion... attributes like this usually don't work well. But as implied with "usually", there are exceptions to this rule. Mar 5, 2016 at 9:03

I don't think there is a good formal way to do this; I think that the good solutions are the ones that make sense, substantively.

Of course, you can try splitting the data and clustering multiple times and so one, but then there is still the question of which one is useful.

• I think the term make sense cannot be stressed enough. That is also the core point of my answer - you need to make sense of your data first. Feb 14, 2016 at 20:39
• @Anony-Mousse, its an overkill from your side. I bet people who don't know how or forget to "make sense" of their data hardly visit this site and they don't ask such good questions as the one asked here. Feb 14, 2016 at 20:46
• @ttnphns I don't know how often such people visit this site, and they certainly don't ask such questions. But a lot of people expect cluster analysis to work like an Excel function. Select the data, click "cluster" and out come the magic customer segments. Which never seems to work much better than random. And e.g. this user failed to understand his data: stats.stackexchange.com/q/195521/7828 Feb 14, 2016 at 21:06