13 ms·

K - means clustering, which I learned about recently. For non-machine learning folks, this algorithms helps in grouping relevant items together. As a practical

K - means clustering, which I learned about recently. For non-machine learning folks, this algorithms helps in grouping relevant items together. As a practical, using this algorithm you can segment your customers based on their purchase history and interests. The actual algorithm is very simple, imagine a lot of points on the 2D plane and each of them represent customers, whom you want to segment/cluster. Now, chose random cluster points and assign those customers to these points, by their distance. That is, whichever customer is near to a point, it belongs to that. At the end of iteration, you have lots of customers assigned to each cluster. Now, for each cluster, take the mean of those customers and the move the cluster to this mean value. Slowly, the cluster points move to the center with all the customers surrounded, belonging to that cluster. read more - https://en.wikipedia.org/wiki/K-means_clustering https://en.wikipedia.org/wiki/K-means_clustering

jacknews 8y ago
I prefer mean-shift for it's simplicity, as it even creates it's own clusters.
- n4r9 8y ago
  Could you explain what you mean by that a little more? I looked at the Clustering section of the Wikipedia page for Mean-Shift: https://en.wikipedia.org/wiki/Mean_shift#Clustering https://en.wikipedia.org/wiki/Mean_shift#Clustering but I don't get how C and r are chosen, nor how the method is supposed to be "non-parametric" given that you need such parameters to begin with. Also, how are you supposed to assign all points to separate clusters, and how would you determine how many clusters to use in the first place? Having looked at the that page I also definitely don't think it's simpler than K-means! Edit: This article gives a much more accessible descriptions than wikipedia: https://spin.atomicobject.com/2015/05/26/mean-shift-clustering/ https://spin.atomicobject.com/2015/05/26/mean-shift-clusteri... To answer my own questions, the number of clusters is determined by the number of max points of the kernel density function, but the kernel bandwidth does have to be specified.
  - vanderZwan 8y ago
    Thanks for not just looking for an answer to your own question but also sharing it! > So how does mean shift come into the picture? Mean shift exploits this KDE idea by imagining what the points would do if they all climbed up hill to the nearest peak on the KDE surface. It does so by iteratively shifting each point uphill until it reaches a peak. I wonder if this would still work with high-dimensional data. Distance and space start to act weird in higher dimensions, right?
    - n4r9 8y ago
      Without looking much further into it, I can't imagine it going very wrong. My intuition says that the density function will be bounded, since you're working with a finite number of points, therefore you'll always be able to climb to a local maximum.
      - vanderZwan 8y ago
        The problem I see is the word "near" in "climb to nearest peak". To quote the curse of dimensionality wiki page: > The common theme of these problems is that when the dimensionality increases, the volume of the space increases so fast that the available data become sparse. This sparsity is problematic for any method that requires statistical significance. https://en.wikipedia.org/wiki/Curse_of_dimensionality https://en.wikipedia.org/wiki/Curse_of_dimensionality
        n4r9 8y ago
        Are you concerned that in a very high dimensional space you'd need an absurd number of points in order to produce a meaninful KDE, since otherwise the points will be too sparse? If so I think I'm with you... you'll probably just end up with a very large number of small, weak clusters. Although I wonder if you can't account for that by simply increasing the kernel bandwidth. Perhaps not. Perhaps this is why mean-shift seems to be mostly used for computer vision and image processing, where (I guess?) the number of dimensions is low.
failsafe 8y ago
The interesting part is solving the "closest pair problem" which is a part of the clustering algorithm. Hurts my head just thinking about it, god knows how someone came up with a solution like this. https://www.geeksforgeeks.org/closest-pair-of-points-using-divide-and-conquer-algorithm/ https://www.geeksforgeeks.org/closest-pair-of-points-using-d...
- n4r9 8y ago
  The closest-pair algorithm is something you might use in single-linkage clustering, not K-means clustering: https://en.wikipedia.org/wiki/Single-linkage_clustering https://en.wikipedia.org/wiki/Single-linkage_clustering
another-cuppa 8y ago
K-means is not an algorithm, it's a heuristic for an Np-hard problem.
- wnkrshm 8y ago
  Isn't a method that gives an approximate or best-fit estimate to a problem still an algorithm, if it terminates?
  - another-cuppa 8y ago
    No. You can't prove that k-means does anything useful.
    - alanbernstein 8y ago
      Is the definition of "algorithm" that you're using here useful?
      - another-cuppa 8y ago
        It's one of the most fundamental concepts in computer science and underpins decades of research. You can decide if it's useful.
        mindcrime 8y ago
        This isn't a classroom, and your pedantry isn't adding anything useful to the conversation. We all understand these pedantic quibbles you're arguing about... and what the community is more or less collectively saying is "in this context, we don't care about the distinction between an 'algorithm' in the textbook sense, and a 'heuristic' in the textbook sense".
        another-cuppa 8y ago
        Nah. Most of them don't understand the difference. If you did you wouldn't can it pedantry. I personally don't find heuristics beautiful. That's why I commented.
stevesimmons 8y ago
The scikit-learn page on clustering [1] is a really great way to see K-means and other algorithms side-by-side. The pictures really make it easy to see how all the algorithms perform on various data distributions. [1] http://scikit-learn.org/stable/modules/clustering.html http://scikit-learn.org/stable/modules/clustering.html
rripken 8y ago
Lesson two of this course does a great job explaining K-means and its connection to Expectation Maximization. https://www.udacity.com/course/machine-learning-unsupervised-learning--ud741 https://www.udacity.com/course/machine-learning-unsupervised...

jacknews 8y ago

I prefer mean-shift for it's simplicity, as it even creates it's own clusters.

n4r9 8y ago
Could you explain what you mean by that a little more? I looked at the Clustering section of the Wikipedia page for Mean-Shift: https://en.wikipedia.org/wiki/Mean_shift#Clustering https://en.wikipedia.org/wiki/Mean_shift#Clustering but I don't get how C and r are chosen, nor how the method is supposed to be "non-parametric" given that you need such parameters to begin with. Also, how are you supposed to assign all points to separate clusters, and how would you determine how many clusters to use in the first place? Having looked at the that page I also definitely don't think it's simpler than K-means! Edit: This article gives a much more accessible descriptions than wikipedia: https://spin.atomicobject.com/2015/05/26/mean-shift-clustering/ https://spin.atomicobject.com/2015/05/26/mean-shift-clusteri... To answer my own questions, the number of clusters is determined by the number of max points of the kernel density function, but the kernel bandwidth does have to be specified.
- vanderZwan 8y ago
  Thanks for not just looking for an answer to your own question but also sharing it! > So how does mean shift come into the picture? Mean shift exploits this KDE idea by imagining what the points would do if they all climbed up hill to the nearest peak on the KDE surface. It does so by iteratively shifting each point uphill until it reaches a peak. I wonder if this would still work with high-dimensional data. Distance and space start to act weird in higher dimensions, right?
  - n4r9 8y ago
    Without looking much further into it, I can't imagine it going very wrong. My intuition says that the density function will be bounded, since you're working with a finite number of points, therefore you'll always be able to climb to a local maximum.
    - vanderZwan 8y ago
      The problem I see is the word "near" in "climb to nearest peak". To quote the curse of dimensionality wiki page: > The common theme of these problems is that when the dimensionality increases, the volume of the space increases so fast that the available data become sparse. This sparsity is problematic for any method that requires statistical significance. https://en.wikipedia.org/wiki/Curse_of_dimensionality https://en.wikipedia.org/wiki/Curse_of_dimensionality
      - n4r9 8y ago
        Are you concerned that in a very high dimensional space you'd need an absurd number of points in order to produce a meaninful KDE, since otherwise the points will be too sparse? If so I think I'm with you... you'll probably just end up with a very large number of small, weak clusters. Although I wonder if you can't account for that by simply increasing the kernel bandwidth. Perhaps not. Perhaps this is why mean-shift seems to be mostly used for computer vision and image processing, where (I guess?) the number of dimensions is low.

failsafe 8y ago

The interesting part is solving the "closest pair problem" which is a part of the clustering algorithm. Hurts my head just thinking about it, god knows how someone came up with a solution like this. https://www.geeksforgeeks.org/closest-pair-of-points-using-divide-and-conquer-algorithm/ https://www.geeksforgeeks.org/closest-pair-of-points-using-d...

n4r9 8y ago
The closest-pair algorithm is something you might use in single-linkage clustering, not K-means clustering: https://en.wikipedia.org/wiki/Single-linkage_clustering https://en.wikipedia.org/wiki/Single-linkage_clustering

another-cuppa 8y ago

K-means is not an algorithm, it's a heuristic for an Np-hard problem.

wnkrshm 8y ago
Isn't a method that gives an approximate or best-fit estimate to a problem still an algorithm, if it terminates?
- another-cuppa 8y ago
  No. You can't prove that k-means does anything useful.
  - alanbernstein 8y ago
    Is the definition of "algorithm" that you're using here useful?
    - another-cuppa 8y ago
      It's one of the most fundamental concepts in computer science and underpins decades of research. You can decide if it's useful.
      - mindcrime 8y ago
        This isn't a classroom, and your pedantry isn't adding anything useful to the conversation. We all understand these pedantic quibbles you're arguing about... and what the community is more or less collectively saying is "in this context, we don't care about the distinction between an 'algorithm' in the textbook sense, and a 'heuristic' in the textbook sense".
        another-cuppa 8y ago
        Nah. Most of them don't understand the difference. If you did you wouldn't can it pedantry. I personally don't find heuristics beautiful. That's why I commented.

stevesimmons 8y ago

The scikit-learn page on clustering [1] is a really great way to see K-means and other algorithms side-by-side. The pictures really make it easy to see how all the algorithms perform on various data distributions. [1] http://scikit-learn.org/stable/modules/clustering.html http://scikit-learn.org/stable/modules/clustering.html

rripken 8y ago

Lesson two of this course does a great job explaining K-means and its connection to Expectation Maximization. https://www.udacity.com/course/machine-learning-unsupervised-learning--ud741 https://www.udacity.com/course/machine-learning-unsupervised...