9 ms·

Introduction to K-Means Clustering

257 points by gk1 5y ago

anonymousDan 5y ago
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?
- cinntaile 5y ago
  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.
jacquesm 5y ago
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.
- csunbird 5y ago
  It is also super intuitive. The logic makes sense immediately when you see it first time.
- NicoJuicy 5y ago
  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).
  - jacquesm 5y ago
    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.
    - nerdponx 5y ago
      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.
      - anonymousDan 5y ago
        You mean to update the clusters incrementally as new data arrives?
    - NicoJuicy 5y ago
      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 )
      - dilyevsky 5y ago
        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
      - jacquesm 5y ago
        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.
      - flashfaffe2 5y ago
        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.
    - 5y ago
- Helmut10001 5y ago
  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 https://github.com/scikit-learn-contrib/hdbscan
  - jacquesm 5y ago
    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'.
  - falkenb0t 5y ago
    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/ https://www.geeksforgeeks.org/ml-mean-shift-clustering/ [2]: https://towardsdatascience.com/k-means-clustering-how-it-works-finding-the-optimum-number-of-clusters-in-the-data-13d18739255c https://towardsdatascience.com/k-means-clustering-how-it-wor...
    - nerdponx 5y ago
      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 https://cran.r-project.org/package=Ckmeans.1d.dp [2]: https://github.com/djdt/ckwrap https://github.com/djdt/ckwrap
- time_to_smile 5y ago
  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.
  - nerdponx 5y ago
    > 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 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.
  - orange3xchicken 5y ago
    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.
mistrial9 5y ago
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.
- monkeybutton 5y ago
  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%20Analysis%20intro.html https://lifelines.readthedocs.io/en/latest/Survival%20Analys... https://hdbscan.readthedocs.io/en/latest/how_hdbscan_works.html https://hdbscan.readthedocs.io/en/latest/how_hdbscan_works.h...
  - danuker 5y ago
    Props to Lifelines. It arranged my thoughts on how to handle survival data, by requiring the data in a clear format.
globular-toast 5y ago
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.
- CardenB 5y ago
  What prevents you from using a different distance than Euclidean distance?
  - danuker 5y ago
    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.
    - jacquesm 5y ago
      That is not a proper distance function.
      - danuker 5y ago
        What do you mean? Is it not the Euclidean distance? https://en.wikipedia.org/wiki/Euclidean_distance https://en.wikipedia.org/wiki/Euclidean_distance
    - nerdponx 5y ago
      This has nothing to do with using non-Euclidean distance, though. This is a separate issue related to having features on different scales.
jdeaton 5y ago
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.
- petters 5y ago
  ...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.
tus666 5y ago
Why not just do a proper course in data science?
- nerdponx 5y ago
  Why read articles about computer science when you could take a proper course in computer science?
  - tus666 5y ago
    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?
    - magicalhippo 5y ago
      > 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.
lichtenberger 5y ago
That was one of the first algorithms I learned at the university, thanks for posting :-)
sideproject 5y ago
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.
- eternityforest 5y ago
  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.
oofbey 5y ago
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?
- twelvechairs 5y ago
  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_cluster_comparison.html https://scikit-learn.org/stable/auto_examples/cluster/plot_c...
  - hoseja 5y ago
    You can still see it failing in that varying-density case.
notafraudster 5y ago
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!
- Breza 5y ago
  Agreed on both fronts. I like both algorithms as teaching tools. When I'm using clustering in a project, I reach for something else.
deleted 5y ago
[deleted]
Bostonian 5y ago
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.
- jononor 5y ago
  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++)
amelius 5y ago
How do you benchmark a clustering algorithm?
- teruakohatu 5y ago
  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.
almog 5y ago
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 https://dataskeptic.com/episodes/k-means
dirkc 5y ago
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...

257 points by gk1 5y ago

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?

cinntaile 5y ago
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.

jacquesm 5y ago

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.

csunbird 5y ago
It is also super intuitive. The logic makes sense immediately when you see it first time.
NicoJuicy 5y ago
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).
- jacquesm 5y ago
  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.
  - nerdponx 5y ago
    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.
    - anonymousDan 5y ago
      You mean to update the clusters incrementally as new data arrives?
  - NicoJuicy 5y ago
    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 )
    - dilyevsky 5y ago
      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
    - jacquesm 5y ago
      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.
    - flashfaffe2 5y ago
      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.
  - 5y ago
Helmut10001 5y ago
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 https://github.com/scikit-learn-contrib/hdbscan
- jacquesm 5y ago
  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'.
- falkenb0t 5y ago
  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/ https://www.geeksforgeeks.org/ml-mean-shift-clustering/ [2]: https://towardsdatascience.com/k-means-clustering-how-it-works-finding-the-optimum-number-of-clusters-in-the-data-13d18739255c https://towardsdatascience.com/k-means-clustering-how-it-wor...
  - nerdponx 5y ago
    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 https://cran.r-project.org/package=Ckmeans.1d.dp [2]: https://github.com/djdt/ckwrap https://github.com/djdt/ckwrap
time_to_smile 5y ago
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.
- nerdponx 5y ago
  > 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 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.
- orange3xchicken 5y ago
  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.

mistrial9 5y ago

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.

monkeybutton 5y ago
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%20Analysis%20intro.html https://lifelines.readthedocs.io/en/latest/Survival%20Analys... https://hdbscan.readthedocs.io/en/latest/how_hdbscan_works.html https://hdbscan.readthedocs.io/en/latest/how_hdbscan_works.h...
- danuker 5y ago
  Props to Lifelines. It arranged my thoughts on how to handle survival data, by requiring the data in a clear format.

globular-toast 5y ago

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.

CardenB 5y ago
What prevents you from using a different distance than Euclidean distance?
- danuker 5y ago
  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.
  - jacquesm 5y ago
    That is not a proper distance function.
    - danuker 5y ago
      What do you mean? Is it not the Euclidean distance? https://en.wikipedia.org/wiki/Euclidean_distance https://en.wikipedia.org/wiki/Euclidean_distance
  - nerdponx 5y ago
    This has nothing to do with using non-Euclidean distance, though. This is a separate issue related to having features on different scales.

jdeaton 5y ago

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.

petters 5y ago
...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.

tus666 5y ago

Why not just do a proper course in data science?

nerdponx 5y ago
Why read articles about computer science when you could take a proper course in computer science?
- tus666 5y ago
  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?
  - magicalhippo 5y ago
    > 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.

lichtenberger 5y ago

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

sideproject 5y ago

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.

eternityforest 5y ago
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.

oofbey 5y ago

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?

twelvechairs 5y ago
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_cluster_comparison.html https://scikit-learn.org/stable/auto_examples/cluster/plot_c...
- hoseja 5y ago
  You can still see it failing in that varying-density case.

notafraudster 5y ago

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!

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

deleted 5y ago

[deleted]

Bostonian 5y ago

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.

jononor 5y ago
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++)

amelius 5y ago

How do you benchmark a clustering algorithm?

teruakohatu 5y ago
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.

almog 5y ago

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 https://dataskeptic.com/episodes/k-means

dirkc 5y ago

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