Questions tagged [distance-functions]
Distance functions refer to functions used for quantifying the notion of distance between members of a set, or between objects.
332
questions
345
votes
8
answers
141k
views
Why is Euclidean distance not a good metric in high dimensions?
I read that 'Euclidean distance is not a good distance in high dimensions'. I guess this statement has something to do with the curse of dimensionality, but what exactly? Besides, what is 'high ...
- 3,667
93
votes
6
answers
157k
views
Why does k-means clustering algorithm use only Euclidean distance metric?
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? ...
- 1,071
83
votes
6
answers
50k
views
Choosing a clustering method
When using cluster analysis on a data set to group similar cases, one needs to choose among a large number of clustering methods and measures of distance. Sometimes, one choice might influence the ...
- 5,886
56
votes
4
answers
17k
views
Kullback–Leibler vs Kolmogorov-Smirnov distance
I can see that there are a lot of formal differences between Kullback–Leibler vs Kolmogorov-Smirnov distance measures.
However, both are used to measure the distance between distributions.
Is there a ...
- 663
52
votes
2
answers
41k
views
Hierarchical clustering with mixed type data - what distance/similarity to use?
In my dataset we have both continuous and naturally discrete variables. I want to know whether we can do hierarchical clustering using both type of variables. And if yes, what distance measure is ...
- 6,174
51
votes
3
answers
24k
views
What is the distribution of the Euclidean distance between two normally distributed random variables?
Assume you are given two objects whose exact locations are unknown, but are distributed according to normal distributions with known parameters (e.g. $a \sim N(m, s)$ and $b \sim N(v, t))$. We can ...
- 3,417
37
votes
5
answers
26k
views
Measuring the "distance" between two multivariate distributions
I'm looking for some good terminology to describe what I'm trying to do, to make it easier to look for resources.
So, say I have two clusters of points A and B, each associated to two values, X and Y,...
- 1,087
35
votes
1
answer
28k
views
Comparing hierarchical clustering dendrograms obtained by different distances & methods
[The initial title "Measurement of similarity for hierarchical clustering trees" was later changed by @ttnphns to better reflect the topic]
I am performing a number of hierarchical cluster analyses ...
- 2,132
22
votes
4
answers
49k
views
Euclidean distance score and similarity
I'm just working with the book Collective Intelligence (by Toby Segaran) and came across the Euclidean distance score. In the book the author shows how to calculate the similarity between two ...
- 335
21
votes
2
answers
2k
views
Is there an unbiased estimator of the Hellinger distance between two distributions?
In a setting where one observes $X_1,\ldots,X_n$ distributed from a distribution with density $f$, I wonder if there is an unbiased estimator (based on the $X_i$'s) of the Hellinger distance to ...
- 98.1k
20
votes
1
answer
35k
views
When to use weighted Euclidean distance and how to determine the weights to use?
I have a set of data where each data consist of $n$ different measures. For each measure, I have a benchmark value. I would like to know how close each data is to the benchmark value.
I thought of ...
- 1,447
19
votes
1
answer
23k
views
What is the optimal distance function for individuals when attributes are nominal?
I do not know which distance function between individuals to use in case of nominal (unordered categorical) attributes.
I was reading some textbook and they suggest Simple Matching function but some ...
- 341
19
votes
4
answers
8k
views
Is it ok to use Manhattan distance with Ward's inter-cluster linkage in hierarchical clustering?
I am using hierarchical clustering to analyze time series data. My code is implemented using the Mathematica function DirectAgglomerate[...], which generates ...
- 191
16
votes
1
answer
15k
views
Clustering: Should I use the Jensen-Shannon Divergence or its square?
I am clustering probability distributions using the Affinity Propagation algorithm, and I plan to use Jensen-Shannon Divergence as my distance metric.
Is it correct to use JSD itself as the distance, ...
- 263
15
votes
5
answers
2k
views
Best distance measure to use to compare vectors of angles
Context
I have two sets of data that I want to compare. Each data element in both sets is a vector containing 22 angles (all between $-\pi$ and $\pi$). The angles relate to a given human pose ...
- 595
15
votes
3
answers
1k
views
$L_1$ or $L_.5$ metrics for clustering?
Does anyone use the $L_1$ or $L_.5$ metrics for clustering, rather than $L_2$ ?
Aggarwal et al.,
On the surprising behavior of distance metrics in high dimensional space
said (in 2001) that
$L_1$ ...
- 3,247
14
votes
2
answers
13k
views
Intuition of the Bhattacharya Coefficient and the Bhattacharya distance?
The Bhattacharyya distance is defined as $D_B(p,q) = -\ln \left( BC(p,q) \right)$, where $BC(p,q) = \sum_{x\in X} \sqrt{p(x) q(x)}$ for discrete variables and similarly for continuous random variables....
- 4,089
12
votes
6
answers
13k
views
Jensen-Shannon divergence calculation for 3 prob distributions: Is this ok?
I would like to calculate the jensen-shannon divergence for he following 3 distributions. Is the calculation below correct? (I followed the JSD formula from wikipedia):
...
- 1,345
12
votes
2
answers
28k
views
What is Mahalanobis distance, & how is it used in pattern recognition?
Can someone explain to me the concept of Mahalanobis distance? For example, what is the Mahalanobis distance between two points x and y, and especially, how is it interpreted for pattern recognition?
- 239
11
votes
2
answers
10k
views
What are distances between variables making a covariance matrix?
I have a $n \times n$ covariance matrix and want to partition variables into $k$ clusters using hierarchical clustering (for example, to sort a covariance matrix).
Is there a typical distance ...
- 5,666
11
votes
2
answers
749
views
Is the relative contrast theorem from Beyer et al. paper: "On the Surprising Behavior of Distance Metrics in High Dimensional Space" misleading?
This is cited very often when mentioning the curse of dimensionality and goes
(righthand formula called relative contrast)
$$ \lim_{d\rightarrow \infty} \text{var} \left(\frac{||X_d||_k}{E[||X_d||_k]...
- 297
10
votes
3
answers
10k
views
Numerical Instability of calculating inverse covariance matrix
I have a 65 samples of 21-dimensional data (pasted here) and I am constructing the covariance matrix from it. When computed in C++ I get the covariance matrix pasted here. And when computed in matlab ...
- 1,249
10
votes
3
answers
4k
views
Mahalanobis distance via PCA when $n<p$
I have an $n\times p$ matrix, where $p$ is the number of genes and $n$ is the number of patients. Anyone whose worked with such data knows that $p$ is always larger than $n$. Using feature selection I ...
- 1,601
10
votes
2
answers
3k
views
Looking for a robust, distribution-free/nonparametric distance between multivariate samples
There are many distance functions for distributions out there, but I'm having a hard time wading through them all to find one that
is "distribution-free", or "nonparametric", by which I mean only ...
- 1,947
10
votes
1
answer
932
views
What's an intuitive way to understand how KL divergence differs from other similarity metrics?
The general intuition I have seen for KL divergence is that it computes the difference in expected length sampling from distribution $P$ with an optimal code for $P$ versus sampling from distribution $...
- 319
10
votes
0
answers
9k
views
Properties of Levenshtein, N-Gram, cosine and Jaccard distance coefficients - in sentence matching
Let's say I have two strings:
string A: 'I went to the cafeteria and bought a sandwich.'
string B: 'I heard the cafeteria is serving roast-beef sandwiches today'.
...
- 541
9
votes
1
answer
10k
views
Can KL-Divergence ever be greater than 1?
I've been working on building some test statistics based on the KL-Divergence,
\begin{equation}
D_{KL}(p \| q) = \sum_i p(i) \log\left(\frac{p(i)}{q(i)}\right),
\end{equation}
And I ended up with a ...
- 93
9
votes
2
answers
8k
views
Jensen-Shannon divergence for bivariate normal distributions
Given two bivariate normal distributions $P \equiv \mathcal{N}(\mu_p, \Sigma_p)$ and $Q \equiv \mathcal{N}(\mu_q, \Sigma_q)$, I am trying to calculate the Jensen-Shannon divergence between them, ...
- 93
9
votes
3
answers
9k
views
Mahalanobis distance between two bivariate distributions with different covariances
The question is pretty much contained in the title. What is the Mahalanobis distance for two distributions of different covariance matrices? What I have found till now assumes the same covariance for ...
- 229
9
votes
2
answers
12k
views
Measuring distance between two empirical distributions
This is similar to the question Measuring the "distance" between two multivariate distributions, except that I want to measure distance between two data sets. I can imagine simply computing ...
- 261
9
votes
1
answer
806
views
Comparing two distributions in Fourier space
There exist a number of tools that provide a distance between two continuous probability distributions. Most (semi)distances, like the Kullback-Leibler divergence, use probability density functions. ...
- 842
8
votes
3
answers
9k
views
How to measure distance for features with different scales?
I'm reading the book "Collective Intelligence" and in one chapter they introduce how to measure similarity between users on a movie review website with euclidean distance.
Now are the movies rated ...
- 263
8
votes
1
answer
2k
views
What are the use cases related to cluster analysis of different distance metrics?
I'm trying to use different distance metrics like Euclidean, Manhattan, cosine, chebyshev among other distance metrics in my k-means algorithm to calculate distances between the data points and the ...
- 579
8
votes
2
answers
2k
views
Is there a version of the Mahalanobis distance for matrices?
I'm working on a computer vision problem and I want to use the Mahalanobis distance to cluster image patches (2D matrices having the same dimensions). I haven't been able to find any generalisation up ...
- 517
8
votes
2
answers
7k
views
The right distance for the clustering. Maybe Mahalanobis?
I have to do a cluster analysis and I'm asking which distance should I used.
I know that 99% of the clustering are made using a euclidean distance, but I heard about the Mahalanobis distance and it ...
- 393
7
votes
1
answer
11k
views
Similarity metrics for more than two vectors?
I am aware of Cosine Similarity which measure the angle between "two" vectors. Prototype for cosine similarity would look something like this:
...
- 577
7
votes
1
answer
1k
views
Extending the Hellinger Distance to multivariate distributions
The hellinger distance for a univariate distribution is
$$
\ H(x) = 1 - \int \sqrt {f(x)g(x)}\; dx
$$
I wish to use it for a bivariate distribution, by extending it to this form
$$
\ H(x) = 1 - \...
- 538
7
votes
2
answers
5k
views
Is there an advantage to squaring dissimilarities when using Ward clustering?
Is there a reason to prefer squaring or not squaring the dissimilarities when clustering with Ward's method?
The question is motivated by the following statement in the documentation for R's ...
- 899
7
votes
1
answer
1k
views
What options are there to combine different distance functions?
I am currently working with feature-vectors that are made up of continuous attributes, so I can use the euclidean distance for things like KNN-classification and clustering. Now I want to add a ...
- 1,343
7
votes
2
answers
1k
views
Viable distance metric for text articles
I have a list of articles, a domain of words/stems and a calculated tf-idf matrix for them.
What distance metric should I use when I try to calculate the similarity of two documents?
- 528
7
votes
1
answer
897
views
Derivation of distance in TwoStep clustering
I am working with the twostep cluster process in SPSS Modeler (Clementine) and trying to get a sense for the distance function used. It is a log-likelihood function (as stated in docs) but I am unsure ...
- 7,940
7
votes
0
answers
198
views
What techniques are there available for averaging misaligned multivariate time series? [closed]
I want to get an average time series for a set of multivariate (2-3 coordinates) time series. My aim is finding the usual pattern of several processes.
I researched the literature a bit and I only ...
- 363
6
votes
2
answers
4k
views
Jaccard similarity coefficient vs. Point-wise mutual information coefficient
Can you explain the difference between the Jaccard similarity coefficient and the pointwise mutual information (PMI) measure? It would be great if you could add a few examples.
- 173
6
votes
2
answers
945
views
Discrepancy measures for transition matrices
I'm doing some work on modelling transition matrices, and for this I need a measure of discrepancy or lack of fit: that is, if I have a matrix $T$ and a target matrix $T_0$, I want to be able to ...
- 7,839
6
votes
1
answer
318
views
Similarity function with given properties
I would like to find a similarity function $f$ between two values (each value is continuous and is bounded by $[0,1]$) that would have the following properties:
$$ f(1, 1) = 0.5 $$
$$ f(0.5, 0.5) =...
- 881
6
votes
3
answers
12k
views
How to input self-defined distance function in R?
I want to know how to to input a self-defined distance in R, in hierarchical clustering analysis. R implements only some default distance metrics, for example "Euclidean", "Manhattan" etc. Suppose I ...
- 61
6
votes
2
answers
3k
views
Is the maximum bound of Euclidean distance between two probability distributions equal to $\sqrt{2}$?
I used Euclidean distance to compute the distance between two probability distribution. The example of computation shown in the Figure below.
As my understanding, the maximum distance occur while $...
- 441
6
votes
2
answers
850
views
Distribution of "sample" mahalanobis distances
Let $x_1,\dots,x_n$ be i.i.d. observations from $N_p(0,\Sigma)$. Let $\hat S=\frac1n\sum_{i=1}^n x_ix_i^T$ be the sample covariance of the samples. Recall that the Mahalanobis distance is defined: $...
- 742
5
votes
1
answer
5k
views
If Manhattan distance always performs better on a dataset...what does it mean?
I'm analyzing my dataset using kNN. I experimented with various distance functions but Manhattan seems to perform better in terms of lowest RMSE over various values of k.
I've read a bit about ...
- 481
5
votes
2
answers
2k
views
Choice of distance metric when data is combination text/numeric/categorical
I have a large table of attributes of different real-world movie theaters. I have classified them by the "true" physical entity to which they belong, so that there may be multiple records for a given ...
- 153