My experience has been the opposite, K-Means clustering is generally pretty useless in the real world with real data.

In general clustering algorithms tend not to be very useful because they are ultimately just very poorly defined latent variable models. Most people starting out with clustering don't even understand that they're making the assumption that K latent variables are responsible for generating the observed data.

K-means in particular has loads of problems for practical applications: the final location of the means is heavily dependent on the initial locations, the final location can also be heavily dependent on the particular dataset used (try bootstrap resampling to get variance of your means), assumes the data rests on a Euclidean surface, making geometric assumptions about high dimensional spaces is almost always a bad a bad idea (things being close by in Euclidean terms in high dimensional spaces often misses things that are nearly identical except on feature that is quite different).

With over a decade of modeling experience and building data science products I have never seen a product ship that relies on k-means and never seen analysis that isn't coming form someone junior in the field that relies on it.

K-means is a great demo the expectation maximization algorithm, which is a useful tool to understand, but generally I would avoid k-means, and clustering in general unless you have an explicit understanding of why you are doing it. Even then, there is probably a more stable and appropriate latent variable model you could use.

> With over a decade of modeling experience and building data science products I have never seen a product ship that relies on k-means and never seen analysis that isn't coming form someone junior in the field that relies on it.

I used it exactly once, and it worked quite well :) But that was because I was clustering 1-dimensional data, which has a globally-optimal solution and there was a fast implementation for it available (see my post https://news.ycombinator.com/item?id=30675594). So it was okay in that instance to brute-force check a lot of different cluster numbers and then post-process the results with some heuristics.

I think K is usually interpreted as the # of gaussians from which the data has been assumed to be sampled. Not immediately related to # of latent variables unless you invoke kernel kmeans or something like laplacian eigenmaps/diffusion maps.

Working in spatial data science, I rarely find applications where k-means is the best tool. The problem is that it is difficult to know how many clusters you can expect on maps. Is it 5; 500; or 10,000? Here HDBSCAN [1] shines because it will cluster _and_ select the most suitable number of clusters, to cut the single linkage cluster tree.

[1]: https://github.com/scikit-learn-contrib/hdbscan

I found myself having to do some clustering a few months back and learned about mean-shift clustering [1]. I found it to be a nice clustering algorithm for when you don't know quantity of clusters ahead of time.

That said, its worth noting that there are algorithms out there for determining optimal number of clusters for k-means (though personally I found them to be costly and subject to overfitting) like using the silhouette coefficient or elbow method [2].

[1]: https://www.geeksforgeeks.org/ml-mean-shift-clustering/ [2]: https://towardsdatascience.com/k-means-clustering-how-it-wor...

Note also that specifically for one-dimensional data, there is a globally optimal solution to the k-means clustering problem. There is an R package that implements it using a C++ core implementation [1], and also a Python wrapper [2].

This implementation is also surprisingly fast, so you can use it to brute-force check many different numbers of clusters and check using silhouette distance. The advantage over traditional k-means is that you don't need to check multiple initializations for any given number of clusters, because the algorithm is deterministic and guaranteed to find the global optimum.

[1]: https://cran.r-project.org/package=Ckmeans.1d.dp

[2]: https://github.com/djdt/ckwrap

Is there a paper or a post which describes the solution?

I just want to mention that these algorithms were known way back and it is sad that the authors of CRAN package do not acknowledge it in their docs:

1. O(NK^2) dynamic programming from 1965 by James Bruce (https://dspace.mit.edu/bitstream/handle/1721.1/4396/RLE-TR-4...)

2. O(KNlogN) dynamic + divide&conquer algorighm from 1989 from Xiaolin Wu and John Rokne (http://doi.acm.org/10.1145/75427.75472)

3. O(NK) algorithm from 1991 by Xiaolin Wu (http://dx.doi.org/10.1016/0196-6774(91)90039-2)

Is there any implementation in Python / Julia / MATLAB?

Yes, the R package was written by the authors of the paper, and the CRAN info page references the paper.

A bigger problem with kmeans than figuring out the number of clusters is the fact that the model assumes multivariate gaussian spheres. That's a bad model for most non-toy data.

It is not necessarily the case.

For example, word2vec uses k-means clustering using cosine similarity measure [1]. It works very, very well. The caveat is not many optimization variations of k-means will work with that "distance".

[1] https://github.com/tmikolov/word2vec/blob/master/word2vec.c#...

My feeling is that if for a given problem "cluster center" is a meaningful concept then k-means is the right tool. The concept of "distance" can be adjusted as well. I think any metric will do. But if you want clusters without a "center of mass" then you are faced with a whole other problem and need other tools.

Not only limited to Gaussian Spheres but also being isotropic (Unless data is pre processed or distance is defined by Mahalanobis Distance).

Can you explain this please?

The model underlying k-means is that all the data is distributed into k hyperspheres. In the simple 2D case, that means drawing k circles around your data points in a X/Y plot such that the inter-group variance is minimized. This is bad because in the real world, data is typically grouped in an elliptical or irregular way.

There are some examples of this at https://stats.stackexchange.com/questions/133656/how-to-unde...

Thank you!

The elbow method exists in many fields. It essentially boils down to "hope that an obviously good choice exists"

Yes that is a good point, if you don't have a good idea on how many subdivisions you want then K-Means won't help you and hdbscan is better.

I always liken the latter to 'automatic feature detection'.

Quicksort and Bresenham aren't useful either because hardly anyone works at that low of a level and the libraries we actually use probably have deeper optimizations by now like hybrid sorts.

So I assume at least part of the usefulness is that the principle applies to unrelated domains?

I'd be interested to hear some of those examples actually, i know what it is. But I haven't used it in practise ( yet).

Just one example from recent practice, to automatically collect a number of texts (pdfs) into a set of groups for easier subsequent processing (summarization). Without K-Means you'd have a pretty hard time figuring out for each subsequent document which group you want to add it to or whether or not you need to make a new group. With K-Means given a fairly simple 'distance' function all of the grouping is automatic. In fact, once you have K-Means coded up the distance function is the problem to solve. If you can't meaningfully define a distance then you probably won't be able to use it.

This is probably the biggest (only?) advantage of k-means in real problems: it's easy to put new data points into existing clusters. You can do this with mean-shift clustering as well.

It's not obvious how to do this with HDBSCAN or hierarchical clustering. Maybe you'd have to draw some kind of boundary around each cluster after fixing the parameters.

You mean to update the clusters incrementally as new data arrives?

Do you have an example of the groups ( = output) and what you are using as variables for input ?

Eg. Wouldn't KNN be easier if you want to classify new groups later on? I'm probably missing something, but defining the groups upfront seems more labor intensive ( note: novice in this area )

Not tp but I’ve tried using k-means for similar task and and LDA and found LDA to be better. Particularly if your documents have mixture of topics

Well, you don't so much define the groups up front as that you define the number of groups up front, the distance function is what will eventually result in the mapping of inputs to groups if you use the groups (for instance: sample texts in those groups) as a part of the scoring system.

Depending on the task but using K- means implies you have have idea of the clusters you might have ( unsupervised learning). KNN assumes the groups already exist.

Interesting did you try any other techniques like HDBSCAN? I've found HDBSCAN to produce more meaningful clusters for a similar workflow.

It is also super intuitive. The logic makes sense immediately when you see it first time.