Introduction to K-Means Clustering | Hacker News Reader

Introduction to K-Means Clustering

pinecone.io

257 pointsgk175 comments

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.

Not sure why this was down voted.

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...

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

Losing convergence guarantees is somewhat important!

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

But you can. Get the distance to all your centroids, assign to closest centroid, update centroid location.

The distance function can be anything.

What's a centroid? It's the point that minimises the sum of squared Euclidean distances between itself and every point in the cluster.

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?

An alternative I've used is k-medoids:

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.

What prevents you from using a different distance than Euclidean distance?

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

Do you lose convergence guarantees if you minimize "sum of squared distances from the centroid" using your other-than-Euclidean distance metric?

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.

This has nothing to do with using non-Euclidean distance, though. This is a separate issue related to having features on different scales.

It was an example metric with coefficients of 1 for each feature.

The point I was making was that the different scale of the features influences the result by a lot.

That is not a proper distance function.

What do you mean? Is it not the Euclidean distance?

https://en.wikipedia.org/wiki/Euclidean_distance

It's been ages since I've used K-means, but I thought you had a lot of freedom in how you define your distance function.

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!

Agreed on both fronts. I like both algorithms as teaching tools. When I'm using clustering in a project, I reach for something else.

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.

...which in turn is just a special case of block coordinate descent. One set of variables is fixed, while another set is optimized and vice versa.

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

[0] https://scikit-learn.org/stable/auto_examples/cluster/plot_c...

You can still see it failing in that varying-density case.

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.

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.

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.

I think its now turned in to somewhat of a competition. If you want your algorithm/package adopted, you have to make it open source and provide good documentation like this: https://lifelines.readthedocs.io/en/latest/Survival%20Analys... https://hdbscan.readthedocs.io/en/latest/how_hdbscan_works.h...

Props to Lifelines. It arranged my thoughts on how to handle survival data, by requiring the data in a clear format.

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.

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++)

I'm by no mean (sorry) a data scientist and this reads really well.

This season of the Data Skeptic podcast is all about k-means and it's excellent as always: https://dataskeptic.com/episodes/k-means

I have fond memories of the algorithm. Two practical things I've used it for are

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...

That was one of the first algorithms I learned at the university, thanks for posting :-)

How do you benchmark a clustering algorithm?

You could benchmark an implementation by speed.

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.

Why not just do a proper course in data science?

Why read articles about computer science when you could take a proper course in computer science?

Because it is far more generic and likely to be actually useful.

Could you imagine someone doing K-means outside of a specific data science application?

> 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.

Reply on news.ycombinator.com