57
$\begingroup$

Is there a specific purpose in terms of efficiency or functionality why the k-means algorithm does not use for example cosine (dis)similarity as a distance metric, but can only use the Euclidean norm? In general, will K-means method comply and be correct when other distances than Euclidean are considered or used?

[Addition by @ttnphns. The question is two-fold. "(Non)Euclidean distance" may concern distance between two data points or distance between a data point and a cluster centre. Both ways have been attempted to address in the answers so far.]

$\endgroup$
  • $\begingroup$ This question has been asked about 10 times already on stackoverflow and this site. Please use the search function. $\endgroup$ – Anony-Mousse Jan 7 '14 at 14:00
  • 3
    $\begingroup$ @Anony-Mousse: While I entirely agree with you and raised a bunch of flags recently on SO, I find the lack of duplicate closure on most of these questions disturbing. $\endgroup$ – Nikana Reklawyks Nov 23 '16 at 21:37
  • 4
    $\begingroup$ This is the page that comes first while googling about this topic. $\endgroup$ – haripkannan Oct 21 '17 at 18:06
58
$\begingroup$

K-Means procedure - which is a vector quantization method often used as a clustering method - does not explicitly use pairwise distances b/w data points at all (in contrast to hierarchical and some other clusterings which allow for arbitrary proximity measure). It amounts to repeatedly assigning points to the closest centroid thereby using Euclidean distance from data points to a centroid. However, K-Means is implicitly based on pairwise Euclidean distances b/w data points, because the sum of squared deviations from centroid is equal to the sum of pairwise squared Euclidean distances divided by the number of points. The term "centroid" is itself from Euclidean geometry. It is multivariate mean in euclidean space. Euclidean space is about euclidean distances. Non-Euclidean distances will generally not span Euclidean space. That's why K-Means is for Euclidean distances only.

But a Euclidean distance b/w two data points can be represented in a number of alternative ways. For example, it is closely tied with cosine or scalar product b/w the points. If you have cosine, or covariance, or correlation, you can always (1) transform it to (squared) Euclidean distance, and then (2) create data for that matrix of Euclidean distances (by means of Principal Coordinates or other forms of metric Multidimensional Scaling) to (3) input those data to K-Means clustering. Therefore, it is possible to make K-Means "work with" pairwise cosines or such; in fact, such implementations of K-Means clustering exist. See also about "K-means for distance matrix" implementation.

It is possible to program K-means in a way that it directly calculate on the square matrix of pairwise Euclidean distances, of course. But it will work slowly, and so the more efficient way is to create data for that distance matrix (converting the distances into scalar products and so on - the pass that is outlined in the previous paragraph) - and then apply standard K-means procedure to that dataset.

Please note I was discussing the topic whether euclidean or noneuclidean dissimilarity between data points is compatible with K-means. It is related to but not quite the same question as whether noneuclidean deviations from centroid (in wide sense, centre or quasicentroid) can be incorporated in K-means or modified "K-means".

See related question K-means: Why minimizing WCSS is maximizing Distance between clusters?.

$\endgroup$
  • $\begingroup$ Can you cite some examples-docs of the approach you are mentioning? $\endgroup$ – curious Jan 7 '14 at 13:23
  • $\begingroup$ I don't have at hand, but I added few links inside my answer $\endgroup$ – ttnphns Jan 7 '14 at 13:29
  • 3
    $\begingroup$ @Douglas, please. I said that k-means does not use pairwise distances. It is clearly stated. It uses distances to centroid. But that automatically means that it is implicitly tied with the task to optimize pairwise distances within clusters. $\endgroup$ – ttnphns May 12 '15 at 6:30
  • 1
    $\begingroup$ @ttnphns: In the number of characters that you wrote But a Euclidean distance b/w two data points can be represented in a number of alternative ways. For example, it is closely tied with cosine or scalar product b/w the points. If you have cosine, or covariance, or correlation, you can always (1) transform it to (squared) Euclidean distance, you could have just as easily written: distance(x,y) = 1 - cosine_sim(x,y) or something similarly pithy and informative. $\endgroup$ – stackoverflowuser2010 Jul 14 '16 at 2:31
  • 2
    $\begingroup$ What are you contending? That it is better in this case to rely on a link, or better to be vague, or both? And why? $\endgroup$ – whuber Jul 14 '16 at 13:54
44
$\begingroup$

See also @ttnphns answer for an interpretation of k-means that actually involves pointwise Euclidean distances.

The way k-means is constructed is not based on distances.

K-means minimizes within-cluster variance. Now if you look at the definition of variance, it is identical to the sum of squared Euclidean distances from the center. (@ttnphns answer refers to pairwise Euclidean distances!)

The basic idea of k-means is to minimize squared errors. There is no "distance" involved here.

Why it is not correct to use arbitary distances: because k-means may stop converging with other distance functions. The common proof of convergence is like this: the assignment step and the mean update step both optimize the same criterion. There is a finite number of assignments possible. Therefore, it must converge after a finite number of improvements. To use this proof for other distance functions, you must show that the mean (note: k-means) minimizes your distances, too.

If you are looking for an Manhattan-distance variant of k-means, there is k-medians. Because the median is a known best L1 estimator.

If you want arbitrary distance functions, have a look at k-medoids (aka: PAM, partitioning around medoids). The medoid minimizes arbitrary distances (because it is defined as the minimum), and there only exist a finite number of possible medoids, too. It is much more expensive than the mean, though.

$\endgroup$
  • $\begingroup$ But at the first step of k-means each point is put in the cluster with the closest euclidean distance with the centroid of the cluster...So there is a distance metric $\endgroup$ – curious Jan 7 '14 at 14:22
  • $\begingroup$ @AnonyMousse @ttnphns answer refers to pairwise Euclidean distances! In my answer, 1st paragraph, I clearly refer both to "SS error" (direct) and "pairwise d^2" (implicit) interpretations. $\endgroup$ – ttnphns Jan 7 '14 at 14:40
  • 3
    $\begingroup$ I agree with you answer. Note that your operational account k-means may stop converging with other distance functions is homologous to my theoretical Non-euclidean distances will generally not span euclidean space. $\endgroup$ – ttnphns Jan 7 '14 at 14:46
  • $\begingroup$ very good explanation. I never gave the euclidean distance a second thought and didn't realize that it was actually minimizing the withing cluster sum of squares. $\endgroup$ – Verena Haunschmid Jan 7 '14 at 14:51
  • $\begingroup$ I still can't see why the mean minimizes distances in terms of euclidean distances and in terms of cosine it doesn't as part of the proof $\endgroup$ – curious Jan 7 '14 at 15:38
9
$\begingroup$

I might be a little pedantic here, but K-means is the name given to a particular algorithm that assigns labels to data points such that within cluster variances are minimized, and it is not the name for a "general technique".

K-means algorithm has been independently proposed from several fields, with strong interpretations applicable to the field. It just turns out, nicely, that it is also euclidean distance to the center. For a brief history of K-means, please read Data Clustering: 50-years beyond K-means

There are a plethora of other clustering algorithms that use metrics other than Euclidean. The most general case I know is of using Bregman Divergences for clustering, of which Euclidean is a special case.

$\endgroup$
  • $\begingroup$ "metrics other than Euclidean" I might be a little more pedantic, but those divergences are not metrics, in general :) $\endgroup$ – mic Jun 23 '15 at 16:32
  • $\begingroup$ true :); i should probably edit the answer. $\endgroup$ – user1669710 Jun 24 '15 at 19:58
8
$\begingroup$

Since this is apparently now a canonical question, and it hasn't been mentioned here yet:

One natural extension of k-means to use distance metrics other than the standard Euclidean distance on $\mathbb R^d$ is to use the kernel trick. This refers to the idea of implicitly mapping the inputs to a high-, or infinite-, dimensional Hilbert space, where distances correspond to the distance function we want to use, and run the algorithm there. That is, letting $\varphi : \mathbb R^p \to \mathcal H$ be some feature map such that the desired metric $d$ can be written $d(x, y) = \lVert \varphi(x) - \varphi(y) \rVert_{\mathcal H}$, we run k-means on the points $\{ \varphi(x_i) \}$. In many cases, we can't compute the map $\varphi$ explicitly, but we can compute the kernel $k(x, y) = \langle \varphi(x), \varphi(y) \rangle_{\mathcal H}$. Not all distance metrics fit this model, but many do, and there are such functions defined on strings, graphs, images, probability distributions, and more....

In this situation, in the standard (Lloyd's) k-means algorithm, we can assign easily points to their clusters, but we represent the cluster centers implicitly (as linear combinations of the input points in Hilbert space). Finding the best representation in the input space would require finding a Fréchet mean, which is quite expensive. So it's easy to get cluster assignments with a kernel, harder to get the means.

The following paper discusses this algorithm, and relates it to spectral clustering:

I. Dhillon, Y. Guan, and B. Kulis. Kernel k-means, Spectral Clustering and Normalized Cuts. KDD 2005.

$\endgroup$
  • $\begingroup$ I don't understand how the kernel trick can be used with Lloyd's algorithm. It seems to me that to calculate a centroid (even implicitly in the Hilbert space), we are going to need the explicit map φ(x_i)? For assigning points to clusters, we only need the kernel, but for recalculating centroids, we can't get away with just the kernel, as the centroid is the mean of the {φ(x_i)} assigned to that cluster. Am I missing something? $\endgroup$ – user2428107 Aug 12 '18 at 6:53
  • $\begingroup$ You're right that we can't explicitly compute centroids. But we can represent them simply as $\frac1{n_i} \sum_{j \in C_i} \varphi(x_j)$, and compute distances to a point $x$ as $\lVert \varphi(x) - \frac1{n_i} \sum_{j \in C_i} \varphi(x_j) \rVert^2 = k(x, x) + \frac1{n_i^2}\sum_{j,j'} k(x_j, x_j') - \frac2{n_i}\sum_j k(x, x_j)$. $\endgroup$ – Dougal Aug 12 '18 at 13:07
5
$\begingroup$

I've read many interesting comments here, but let me add that Matlab's "personal" implementation of k-means supports 4 non-Euclidean distances [between data points and cluster centres]. The only comment from the documentation I can see about that is:

Distance measure, in p-dimensional space, used for minimization, specified as the comma-separated pair consisting of 'Distance' and a string.

kmeans computes centroid clusters differently for the different, supported distance measures. This table summarizes the available distance measures. In the formulae, x is an observation (that is, a row of X) and c is a centroid (a row vector).

Then a list of functions of c and x follows. Thus, considering that p is the dimensionality of the input data, it seems that no Euclidean embedding is performed beforehand.

BTW in the past I've been using Matlab's k-means with correlation distance and it (unsurprisingly) did what it was supposed to do.

$\endgroup$
  • 2
    $\begingroup$ As a note, the supported non-Euclidean distances are cosine (which is just Euclidean distance on normalized input points), correlation (Euclidean on standardized inputs), cityblock ($L_1$, in which case the median is used rather than the mean), and hamming (which is just cityblock for binary inputs). $\endgroup$ – Dougal Mar 25 '16 at 16:12
  • $\begingroup$ @Dougal, How median is accomodated into the algorithm? Doesn't it change k-means to a basically different algo? $\endgroup$ – ttnphns Mar 27 '16 at 8:32
  • 1
    $\begingroup$ Note also that for binary data "hamming distance" = cityblock = sq. euclidean distance. $\endgroup$ – ttnphns Mar 27 '16 at 8:37
  • 1
    $\begingroup$ @ttnphns Yes, it is definitely no longer k-means, but it has exactly the same structure except instead of computing the centroids as means you compute a median. And yes on binary inputs hamming $= L_2^2 = L_1$, but Matlab uses the median for it instead of the mean. $\endgroup$ – Dougal Mar 27 '16 at 15:16
  • 1
    $\begingroup$ @Dougal, Notice that the matlab procedure linked to says of various distances between a data point and the cluster centre; which is not the same thing as kinds of pairwise distances. $\endgroup$ – ttnphns Mar 28 '16 at 8:47
1
$\begingroup$

From here:

enter image description here

Let us consider two documents A and B represented by the vectors in the above figure. The cosine treats both vectors as unit vectors by normalizing them, giving you a measure of the angle between the two vectors. It does provide an accurate measure of similarity but with no regard to magnitude. But magnitude is an important factor while considering similarity.

$\endgroup$
  • $\begingroup$ This is a general answer. It doesn't explain why in k-means there is no cosine similarity. For instance in hierarchical clustering it is being used widely $\endgroup$ – curious Jan 7 '14 at 12:06
  • 3
    $\begingroup$ @DLDahly: Sometimes magnitude is important, sometimes it is noise. It depends on the research field and is an issue of data standardization. $\endgroup$ – ttnphns Jan 7 '14 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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