7
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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".

| improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
0
$\begingroup$

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.

Metric learning is closely related to dimensionality reduction.

If you are using MATLAB check this toolkit.

| improve this answer | |
$\endgroup$
  • $\begingroup$ k-means only works with Bregman divergences, not with arbitrary metrics. Because of the mean not optimizing arbitrary metrics. $\endgroup$ – Has QUIT--Anony-Mousse Apr 16 '16 at 12:57
  • $\begingroup$ What it means when you say - mean not optimizing? Add a source please. $\endgroup$ – p.j Apr 16 '16 at 18:12
  • $\begingroup$ Search for "why k-means only works with Euclidean distance". $\endgroup$ – Has QUIT--Anony-Mousse Apr 16 '16 at 19:00

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.