Ascertaining what clustering algorithm to use in various situations

Question

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.

Answer 1

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?

Answer 2

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