# Ascertaining what clustering algorithm to use in various situations

It is said that kMeans clustering works as long as we don't have clusters of differing

1. sizes,
2. densities,
3. and non-spherical shapes

I understand how one might check the sizes and densities of data points, but I am unsure how one would check for non-spherical clusters, especially if one merely has a conceptual understanding of a dataset.

So, Q1. Since most people with real world data sets would not know if they have non-spherical clusters, would it not be a mistake to apply kMeans?

Q2. What would be a more suitable choice of a clustering algorithm if we only want to partition our data set, given we don't know the shape of our data? By partition, I refer to partitioning cluster algorithms such as kMeans and kMedoids.

Q3. What mind map would experienced clustering users have when they intend to apply partitioning cluster algorithms?

For example, the following is mine, but I am inexperienced in clustering:

1. check if the data is comprised of continuous, or continous + discrete variables
2. pick euclidean/manhattan/mahalanobis distance measure for former, or gower for latter
3. perhaps standardise first and then apply the distance measure/or correlation if a similarity matrix is sought
4. apply a partitioning cluster algorithm; kMeans if we know our data shape and outliers are not a problem. kMedoids if we don't want to be affected by outliers (although the definition of a centroid/prototype as found by kMeans seems to change if we apply kMedoids, i.e. a centroid in kMeans is understandably a prototype of each cluster, while in kMedoids this centroid is simply another data point and not a prototype)
5. validate cluster results (using the Elbow test/Dunn index/Silhouette Coeff if focusing only on internal measures) and also check for clustering tendency

Am I missing something important in the above?

Many thanks, and please pardon the ignorance.

• Q2. If you want only to partition (somehow) data, why use clustering at all? You use "partition" also in Q3.4. It is unclear what you mean by partition in your question: 1) any partition, 2) any clustering, or 3) partitioning methods of clustering (such as K-means, but not at all hierarchical agglomerative). – ttnphns Mar 5 '14 at 14:51
• Apologies, I forgot about the general meaning of a partition. What I meant was a partitioning cluster algorithm - so no hierarchical clustering, only those cluster algroithms that split data into flat partitions. – info_seeker Mar 5 '14 at 14:53
• Then please edit your question to make it clear. AND, it would be nice if you mention the partitioning methods you are interested in or you know. – ttnphns Mar 5 '14 at 14:55
• I hope now it is sufficient. Apologies. I understand it is a wide topic and some questions may seem too general - bear with me please. – info_seeker Mar 5 '14 at 15:03

If you are less interested in finding structure of your data then just "simplifying" your data - see vector quantization - then methods such as k-means can work okay.

However, often you don't even need k-means.

Just pick random points as cluster centers and partition your data accordingly.

Or make data bubbles / canopies. Overlapping groups of points, with a distance threshold.

There are many methods which mostly compress your data (reduce it to a number of representative points), which do not actually try to discover some complex structure or optimize some mathematical property.

The main question is: is this still "clustering"? Or is it more of a "data simplification", "vector quantization", "sampling" method?

• Thank you for replying - great to learn from people like yourself. Please pardon my delayed response. I originally wanted to ask for something like a step-by-step procedure to determine an appropriate clustering technique. But as I have read answers here (and some books), clustering is a lot more complex and nuanced than this. And I'm still trying to answer the question you put forth... – info_seeker Apr 7 '14 at 18:49
• The more I see, it is about compressing the data and selecting representative samples. Which is why quantization methods like k-means often work very well on data where they are ''not supposed to work'' (because of outliers etc.) - if we only need a very rough solution, they are good enough. – Has QUIT--Anony-Mousse Apr 7 '14 at 23:04
• Ah, I see. I was also wondering how come k-means is so widely applied-for example, in customer profiling, where all sorts of categorical, binary, and continuous variables occur, and it is not clear what it means to compute Euclidean distance between variables such as amount of phone usage, age, salary, etc. Neither is it certain that such data will not have outliers, different shapes, densities, etc. But now as I understand k-means more, I will be more careful in my analysis, hopefully, and also look for algorithms detecting structure (in my understanding hierarchical clustering)...Thank you! – info_seeker Apr 8 '14 at 17:03

There is no unique true clustering in a dataset. Different clusterings can be legitimate for different aims on the same dataset. The choice of method implicitly defines the kinds of clusters you will find. So the first question to ask is, what does a cluster mean in the application of interest. For example if you want clusters to be compact with all observations well represented by the mean vector and with the same spread in all directions, k-means is fine (or partitioning around medoids if you have non-Euclidean distance data). If however you want clusters to be separated by density gaps, Single Linkage (if "gap" really means no points between clusters) or something like dbscan is appropriate. If you want clusters to be approximate Gaussian, i.e., elliptical with flexible shapes (covariance matrices), you should go for Gaussian mixture clustering. If you want maximum distances within clusters to be small, it's Complete Linkage.

That said, the user often doesn't know precisely enough what they want, and the idea is that the data should somehow contain the information of what kind the cluster are. Let's say this is not totally wrong insofar as in exploratory analysis in some datasets (but not all!) some more or less clear structure can be seen that may correspond more to one method than to another. For example one could get the impression that separated clusters are rather Gaussian or rather skew (for which there are also mixture models), without wanting to use a maybe overly flexible methods such as dbscan that may give weird nonlinear shapes or too big within-cluster distances. It may also be that although one may ideally want to have Gaussian-shaped clusters, the data show that visible structures are rather nonlinear, or there are outliers that have to be dealt with.

So the user idea of what a cluster is maybe somewhat flexible, in which case the data can add information. This can be done before clustering using visualisation or after clustering using validation techniques, which may involve visualisation but also other things such as stability assessment. However the issue doesn't go away that the different methods have different inherent concepts of what a cluster is, and a user is in a much better position if they know in advance at least roughly what kinds of clusters are required in the given situation. Many datasets are ambiguous and different methods give genuinely different solutions that are all legitimate.

You may find this useful: Hennig, C. Clustering strategy and method selection. In Hennig, C., Meila, M., Murtagh, F. and Rocci, R. (eds.): Handbook of Cluster Analysis, CRC Press 2016, 703-730.

https://arxiv.org/abs/1503.02059