8
$\begingroup$

In clustering methods such as K-means, the euclidean distance is the metric to use. As a result, we only calculate the mean values within each cluster. And then adjustments are made on the elements based on their distance to each mean value.

I was wondering why the Gaussian function is not used as the metric? Instead of using xi -mean(X), we can use exp(- (xi - mean(X)).^2/std(X).^2). Thus not only the similarity among the clusters are measured (mean), but the similarity within the cluster is also considered (std). Is this also equivalent to the Gaussian mixture model?

It is beyond my question here but I think mean-shift may arise the same question above.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ This thread may be helpful. stats.stackexchange.com/questions/76866/… Search your tags for other relevant questions. $\endgroup$
    – D L Dahly
    Dec 27, 2013 at 0:30
  • $\begingroup$ @DLDahly Thank you Dahly. Can we view EM-based GMM as a weighted k-means (with different weights on variances)? $\endgroup$
    – lennon310
    Dec 28, 2013 at 2:11
  • $\begingroup$ It's not how I would think of it; rather I see k-means as a GMM where the variances are constrained to be zero. $\endgroup$
    – D L Dahly
    Dec 28, 2013 at 8:23

2 Answers 2

Reset to default
5
$\begingroup$

There a literally thousands of k-means variations. Including soft assignment, variance and covariance (usually referred to as Gaussian Mixture Modeling or EM algorithm).

However, I'd like to point out a few things:

  • K-means is not based on Euclidean distance. It's based on variance minimization. Since the variance is the sum of the squared Euclidean distances, the minimum variance assignment is the one that has the smallest squared Euclidean, and the square root function is monotone. For efficiency reasons, it actually is smarter to not compute Euclidean distance (but use the squares)

  • If you plug in a different distance function into k-means it may stop converging. You need to minimize the same criterion in both steps; the second step is recomputing the means. Estimating the center using the arithmetic mean is a least squares estimator, and it will minimize variance. Since both functions minimize variance, k-means must converge. If you want to ensure convergence with other distances, use PAM (partitioning around medoids. The medoid minimizes the within-cluster distances for arbitrary distance functions.)

But in the end, k-means and all of its variations are IMHO more of an optimization (or more precisely, a vector quantization algorithm) than actually a cluster analysis algorithm. They will not actually "discover" structure. They will massage your data into k partitions. If you give them uniform data, with no structure beyond randomness at all, k-means will still find however many "clusters" you want it to find. k-means is happy with returning results that are essentially random.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ +1. However, claim that K-means isn't a clustering seems to be too radical, too "data-mining" viewpoint. Historically K-means is classic partinioning cluster analysis. The fact that it happily partitions "unstructured" data does not exclude it from the domain of clustering: many types of analyses can be, so to speak, misused and give silly results. $\endgroup$
    – ttnphns
    Dec 28, 2013 at 13:24
  • $\begingroup$ One more point: K-means is not based on Euclidean distance isn't enough clear place in your answer. You and I had discussions about it in the past and I showed that variance minimization is related to the sum of within-cluster pairwise euclidean d^2. $\endgroup$
    – ttnphns
    Dec 28, 2013 at 13:26
  • $\begingroup$ I'm clearly stating the relationship to Euclidean distance via variance. The thing is, you need to replace variance with a different measure (then choose assignment and update accordingly), not exchange Euclidean and hope the mean still remains meaningful. $\endgroup$
    – Has QUIT--Anony-Mousse
    Dec 28, 2013 at 14:20
  • $\begingroup$ Historically, k-means was published by Lloyd as "Least squares quantization in PCM". Similarly, Steinhaus had the desire to perform quantization. Which explains nicely why SSQ is used, as SSQ is the squared error of the discretization. MacQueen mentions cluster analysis as an application of the algorithm, but suggests to use a modified version of the algorithm that can add or remove clusters as desired (at which point it actually starts being more than quantification). $\endgroup$
    – Has QUIT--Anony-Mousse
    Dec 28, 2013 at 14:50
  • $\begingroup$ The point I'm trying to make in the end is to look at vector quantization, not just "clustering", as recently clustering research is dominated by data-mining point of view (and much of the time not k-means based anymore). Vector quantization may the much better (because much more precise) search term. $\endgroup$
    – Has QUIT--Anony-Mousse
    Dec 28, 2013 at 15:23
3
$\begingroup$

There are lots of different clustering techniques out there, and K-means is just one approach. As DL Dahly commented, EM algorithms can be used for clustering in much the way you described. It's worth noting that the main difference between K-means and using EM with a guassian mixture model for clustering is the shape of the clusters: the centroid will still closely approximate the mean of the points in the group, but K-means will give a spherical cluster whereas a gaussian kernel will give an ellipsoid.

Hierarchical clustering uses a completely different approach. Density based clustering is motivated by a similar heuristic as mean based clustering, but obviously gives different results. There are plenty of clustering techniques that don't consider any kind of mean.

Really when it comes down to it, the choice of algorithm is a function of the problem domain and experimentation (i.e. seeing what works).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you David. I guess Hierarchical gives different results from kmeans because the definitions of distance between two clusters are not the same. It may not be easy to determine which metric to use, and whether the variance should be included. It seems like different groups of people developed their own metrics on their own problem. The method just gave such problem a good result, yet it lacked theoretical support on the option of clustering methods. $\endgroup$
    – lennon310
    Dec 28, 2013 at 2:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.