What methods exist for distance calculation in clustering? when we should use each of them?

Question

What methods exist for distance calculation in clustering? like Manhattan, Euclidean, etc.? Plus, I don't know when I should use them. I always use Euclidean distance.

Answer 1

Well, there is a book called

Deza, Michel Marie, and Elena Deza.
Encyclopedia of distances.
Springer Berlin Heidelberg, 2009. ISBN 978-3-642-00233-5

I guess that book answers your question better than I can...

Choose the distance function most appropriate for your data.

For example, on latitude and longitude, use a distance like Haversine. If you have enough CPU, you can use better approximations such as Vincenty's.

On histograms, use a distribution-baes distance. Earth-movers (EMD), divergences, histogram intersection, quadratic form distances, etc.

On binary data, for example Jaccard, Dice, or Hamming make a lot of sense.

On non-binary sparse data, such as text, various variants of tf-idf weights and cosine are popular.

Probably the best tool to experiment with different distance functions and clustering is ELKI. It has many many distances, and many clustering algorithms that can be used with all of these distances (e.g. OPTICS). For example Canberra distance worked very well for me. That is probably what I would choose as "default".

Answer 2

There are two method which are widely used for calculating distance in the domain of clustering. They are:

• Manhattan Distance
• Euclidean Distance

However, there is no clear directive as to which of the above to select, so this post might be helpful to you regarding the same. Generally, the distance metric depends on the problem statement and the type of data.

For example, the euclidean and cosine distance are used when the data is dense and sparse respectively.

I always use euclidean distance.

I wouldn't blame you for that. However, when calculating cartesian distance (like in the case of Recommender systems), the Euclidean distance is preferred.

Answer 3

I wanna highlight that in addition to the well known distances: Manhattan Distance Euclidean Distance

Symmetric kl-d can be used when you are clustering distributions.

Answer 4

Which distance function to use depends on the data geometry itself. In some cases you can plot you data and visualize then take decisions but in real world problems mostly it is not possible.

For most clustering algorithm like Kmeans, as long as a distance function is a metric you can use it. There exists methods to learn a metric according to data geometry which you can use to cluster the data.

• What is metric learning?
• Introduction and Motivation.
• Brian Kulis has a very nice survey paper on this.

Metric learning is closely related to dimensionality reduction.

If you are using MATLAB check this toolkit.