How to evaluate distance in k-means clusters?

Question

I try to use k-means clusters (using SQLserver + R), and I was wondering how we could estimate a distance correctly.

For instance, if we consider Euclidean distance form the center of the clusters, what happen if we have, for the same dataset, clusters of different sizes ? a "normal" point in a big cluster will have a distance higher than an "outlier" point in a little one.

So:

• Is it relevant to center / scale euclidean distance on each cluster ? (and then consider outliers as the ones with the highest scaled distance)
• Are there other kind of distance to consider ?

Answer 1

There are several important points to keep in mind in considering your questions:

1. You should always normalize or standardize your data before applying k-means clustering. This is true of most other clustering algorithms also. If you are clustering in more than one dimension, the distance metric is meaningless unless each dimension has the same weight, so normalization is essential. Imagine clustering people by body weight and income. Without normalization the results will depend on whether you think in pounds and dollars, kilograms and pesos, or moles and euros. The lack of normalization introduces non-determinism.

2. Strictly speaking, the stability of the k-means algorithm has been shown for Euclidean distance metrics and there is no assurance of convergence with other distance metrics. More practically, most sensible metrics attain convergence and its not much of an issue, but its worth putting that warning out there.

3. k-means isn't a clustering algorithm that readily lends itself to statistical analysis within the cluster. Every point in the space is a member of one of the k clusters regardless of how much of an outlier the point is. There are other clustering methods that are more adept at finding and ignoring outliers. DBSCAN is one such algorithm that is very good and finding clusters and ignoring noise.

Now, answering your questions:

Is it relevant to center / scale euclidean distance on each cluster ? (and then consider outliers as the ones with the highest scaled distance)

Yes, you can certainly do this. Combining k-means with outlier detection is certainly possible but is probably not the most elegant or efficient algorithm. It kind of sounds like poor-mans's DBSCAN. Euclidean distance works fine, but just do a second set of normalizations using the centroids and the standard deviation of the cluster.

Are there other kind of distance to consider?

There are lots of other metrics that are useful for many different reasons. As stated, the k-means convergence proofs hold only for Euclidean distance. For outlier detection Euclidean seems best, but there may be cases where Cosine Similarity metrics could be useful. People may suggest L1 (Manhattan) distance metrics, but I find this is only useful when there is significant linear dependence in your data, which can be remedied with dimensionality reduction.

Short answer:

Give it a try as Euclidean should work fine, but also take a look at clustering via DBSCAN, which has outlier detection built into it.

Hope this helps!