K-Means Clustering is one of those tools that once you understand it becomes more and more useful over time. You keep finding new ways to apply it, it's a bit like Quicksort, Bresenham or Divide and Conquer in that sense.
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.
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 )
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.
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.
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].
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.
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.
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.
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".
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.
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?
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.
times are changing online -- I definitely recall a two volume, hard bound, >$100USD edition of "Clustering Methods" in the university book store and did not buy it. I was being mocked by my non-native English colleague with a Masters in Computer Science from great (non-English) university, about the ability to even read that work. Now, I look at the Scikit-learn docs mainly. Good work pinecone dot IO.
One thing not mentioned with k-means is it requires your data to be in Euclidean space. You can't just come up with a distance function and do clustering with it. That's one reason the other techniques often make sense. In fact, those techniques often don't care what the data actually is, they only need the distances, and even then they don't need all of them.
Still, k-means is enormously practical despite its shortcomings.
Suppose you use prices and square meters, to cluster apartments. Suppose you also use a simple metric, like:
distance <- sqrt(d_price*2 + d_area*2)
Without normalizing the units somehow, so that they have a meaningfully similar numeric expression, you are essentially only clustering by price, which is in the tens- or hundreds-of-thousands.
You use very little information about the area, because that is in the hundreds, at most thousands.
The way k-means is constructed is not based on distances.
K-means minimizes within-cluster variance. If you look at the definition of variance, it is identical to the sum of squared Euclidean distances from the centroid
That's a really pedantic take, nothing precludes you from using whatever distance function you want to get the distance to k centroids and act accordingly
I totally agree with your point, but sometimes you can get away by being handwavey about it and making sure the centroids aren't skipping all over the place... and that's good enough
It's a tuple of floats that you move slightly towards the closest point it has just seen, optionally with some rate of forgetting.
You shuffle your big ass wad of data, and loop over each element doing the above, optionally decreasing the forgetting rate.
You track the location of your centroids and if your data / loss fn isn't too pathological, they won't misbehave too badly and you have handwavey assurance of convergence... Definitions be damned.
So, you made up your own algorithm that is kinda like k-means, this algorithm might sometimes work, and this shows that k-means works in non-Euclidean spaces?
This is especially useful in cases where the distance between points is given by a matrix, and cannot be derived from the points themselves. For example, the drive time between locations on a road network.
After having implemented k-means ~5 times in undergraduate classes, it was interesting to learn that k-means is just a special case of expectation maximization.
Simplicity wins in many cases and it is with K-Means clustering. There are so many clustering algorithms, far superior to K-Means, but its simplicity and easy-to-apply approach to most of the datasets available allow pretty much anyone with programming skills to understand and implement quickly to get results and gives you that feeling of "oh, hey, that's my first data science thingy". Simplicity is very powerful.
I suppose in an academic setting where the goal is understanding that makes sense, but all the other algorithms are just as easy and in fact probably have the same API, if you aren't DIYing it.
K-means has a lot going for it, but it's not very good at recovering "natural" clusters. Like if you have a dataset that you know actually is grouped in a certain way, k-means very often will not discover those clusters. Other more complex clustering algorithms will do a more reliable job. If you have to implement clustering yourself for some reason, k-means' simplicity is great. But how often do you need to write your own algorithm these days?
Yes. The visual comparison at [0] gives a good quick overview of clustering algorithms in speed and results. DBSCAN is one with an excellent combination of speed and finding clusters that are human-sensible
One thing that's nice about k-means is that it can quite literally be grasped intuitively by, say, a 10 year old. k-nearest neighbors is similarly graspable. I think these are wonderful techniques to introduce kids to data science without having to get into the math. Obviously you're going to have to abstract away high-dimensionality and a lot of the underlying math of "how" -- but that's ok!
I'm not sure I've found either to be massively useful on real-world data, but that's OK too!
The more I learn about machine learning, the more it seems to me that the real key is to understand optimization algorithms (both analytical and numerical) and how/when they are likely to converge. Am I wrong? Are there good books summarizing the relationship between all the different approaches to optimization used in ML?
You're basically trying to fit data to some model and to help with that you have a cost function that you try to optimize. Any decent machine learning curriculum will have an optimization course.
Mixtures of multivariate normals can be regarded as a method of fuzzy clustering,
where each point has a probability of coming from each of the component Gaussians. The EM (expectation maximization) algorithm can be used to fit mixture models.
Yeah, a Gaussian Mixture Model (GMM) is a very useful method which is closely related to k-means. It allows for other shapes than just spheres which tends to be very useful in practice. In addition to the probabilistic cluster membership (as you mention). Not only is the same EM algorithm used to find GMM parameters, but initial cluster assignment is usually done with k-means (typically a variation dubbed k-means++)
If you have known clusters, for example generating data from three distributions or real world data like the Iris dataset, you can measure how well the clustering works.
There are also a variety of metrics that give insight into performance, or at least performance when compared to other algorithms.
But if you are asking how do we know this is a "real" cluster, then we can't. We can only say for sure that for a dataset with n observations, there is n possible clusters.
77 comments
[ 5.2 ms ] story [ 155 ms ] threadIt'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.
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 )
[1]: https://github.com/scikit-learn-contrib/hdbscan
I always liken the latter to 'automatic feature detection'.
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...
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
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)
There are some examples of this at https://stats.stackexchange.com/questions/133656/how-to-unde...
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#...
So I assume at least part of the usefulness is that the principle applies to unrelated domains?
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.
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.
Still, k-means is enormously practical despite its shortcomings.
You use very little information about the area, because that is in the hundreds, at most thousands.
https://en.wikipedia.org/wiki/Euclidean_distance
The point I was making was that the different scale of the features influences the result by a lot.
K-means minimizes within-cluster variance. If you look at the definition of variance, it is identical to the sum of squared Euclidean distances from the centroid
K-means in its standard form does make a Euclidean hypothesis (it does not minimize a distance but the in-cluster variance).
It is not correct to use arbitrary distances because k-means may stop converging with other distance functions.
See this thread for more info: https://stats.stackexchange.com/questions/81481/why-does-k-m...
The distance function can be anything.
You shuffle your big ass wad of data, and loop over each element doing the above, optionally decreasing the forgetting rate.
You track the location of your centroids and if your data / loss fn isn't too pathological, they won't misbehave too badly and you have handwavey assurance of convergence... Definitions be damned.
https://en.m.wikipedia.org/wiki/K-medoids
This is especially useful in cases where the distance between points is given by a matrix, and cannot be derived from the points themselves. For example, the drive time between locations on a road network.
Could you imagine someone doing K-means outside of a specific data science application?
I implemented k-means clustering to reduce noise in a path tracer. I've never done a data science course or anything like that.
[0] https://scikit-learn.org/stable/auto_examples/cluster/plot_c...
I'm not sure I've found either to be massively useful on real-world data, but that's OK too!
If you have known clusters, for example generating data from three distributions or real world data like the Iris dataset, you can measure how well the clustering works.
There are also a variety of metrics that give insight into performance, or at least performance when compared to other algorithms.
But if you are asking how do we know this is a "real" cluster, then we can't. We can only say for sure that for a dataset with n observations, there is n possible clusters.
This season of the Data Skeptic podcast is all about k-means and it's excellent as always: https://dataskeptic.com/episodes/k-means
1. fitting flat surfaces to a point cloud
2. assigning people to study groups based on music tastes (they picked a few artists they liked I used to echonest API for calculating distances)
It's been too long since I've had an excuse to use it...