Questions tagged [distance]

Measure of distance between distributions or variables, such as Euclidean distance between points in n-space.

Filter by
Sorted by
Tagged with
161 votes
9 answers
105k views

Bottom to top explanation of the Mahalanobis distance?

I'm studying pattern recognition and statistics and almost every book I open on the subject I bump into the concept of Mahalanobis distance. The books give sort of intuitive explanations, but still ...
user avatar
  • 5,257
76 votes
5 answers
24k views

Intuition on the Kullback–Leibler (KL) Divergence

I have learned about the intuition behind the KL Divergence as how much a model distribution function differs from the theoretical/true distribution of the data. The source I am reading goes on to say ...
user avatar
  • 7,815
51 votes
2 answers
88k views

Choosing the right linkage method for hierarchical clustering

I am performing hierarchical clustering on data I've gathered and processed from the reddit data dump on Google BigQuery. My process is the following: Get the latest 1000 posts in /r/politics ...
user avatar
  • 611
33 votes
4 answers
52k views

Maximum Mean Discrepancy (distance distribution)

I have two data sets (source and target data) which follow different distributions. I am using MMD - that is a non-parametric distribution distance - to compute marginal distribution between the ...
user avatar
  • 431
29 votes
1 answer
8k views

Earth Mover's Distance (EMD) between two Gaussians

Is there a closed-form formula for (or some kind of bound on) the EMD between $x_1\sim N(\mu_1, \Sigma_1)$ and $x_2 \sim N(\mu_2, \Sigma_2)$?
user avatar
  • 391
28 votes
3 answers
50k views

Distribution of difference between two normal distributions

I have two probability density functions of normal distributions: $$f_1(x_1 \; | \; \mu_1, \sigma_1) = \frac{1}{\sigma_1\sqrt{2\pi} } \; e^{ -\frac{(x-\mu_1)^2}{2\sigma_1^2} }$$ and $$f_2(x_2 \; | \...
user avatar
  • 405
28 votes
1 answer
20k views

Converting similarity matrix to (euclidean) distance matrix

In Random forest algorithm, Breiman (author) constructs similarity matrix as follows: Send all learning examples down each tree in the forest If two examples land in the same leaf increment ...
user avatar
  • 467
27 votes
1 answer
36k views

Using correlation as distance metric (for hierarchical clustering)

I would like to hierarchically cluster my data, but rather than using Euclidean distance, I'd like to use correlation. Also, since the correlation coefficient ranges from -1 to 1, with both -1 and 1 ...
user avatar
  • 373
26 votes
1 answer
2k views

Can the Mantel test be extended to asymmetric matrices?

The Mantel test is usually applied to symmetric distance/difference matrices. As far as I understand, an assumption of the test is that the measure used to define differences must be at least a semi-...
user avatar
25 votes
8 answers
29k views

Perform K-means (or its close kin) clustering with only a distance matrix, not points-by-features data

I want to perform K-means clustering on objects I have, but the objects aren't described as points in space, i.e. by objects x features dataset. However, I am able ...
user avatar
  • 253
23 votes
4 answers
9k views

Why are mixed data a problem for euclidean-based clustering algorithms?

Most classical clustering and dimensionality reduction algorithms (hierarchical clustering, principal component analysis, k-means, self-organizing maps...) are designed specifically for numeric data, ...
user avatar
  • 1,042
22 votes
1 answer
6k views

Link between variance and pairwise distances within a variable

Please, prove that if we have two variables (equal sample size) $X$ and $Y$ and the variance in $X$ is greater than in $Y$, then the sum of squared differences (i.e., squared Euclidean distances) ...
user avatar
  • 52.5k
21 votes
4 answers
50k views

Comparing two histograms using Chi-Square distance

I want to compare two images of faces. I calculated their LBP-histograms. So now I need to compare these two histograms and get something that will tell how much these histograms are equal (0 - 100%). ...
user avatar
20 votes
9 answers
11k views

Pairwise Mahalanobis distances

I need to calculate the sample Mahalanobis distance in R between every pair of observations in a $n \times p$ matrix of covariates. I need a solution that is efficient, i.e. only $n(n-1)/2$ distances ...
user avatar
  • 1,289
20 votes
5 answers
20k views

How I can convert distance (Euclidean) to similarity score

I am using $k$ means clustering to cluster speaker voices. When I compare an utterance with clustered speaker data I get (Euclidean distance-based) average distortion. This distance can be in range of ...
user avatar
  • 331
18 votes
3 answers
11k views

What's the maximum value of Kullback-Leibler (KL) divergence

I am going to use KL divergence in my python code and I got this tutorial. On that tutorial, to implement KL divergence is quite simple. ...
user avatar
  • 421
18 votes
3 answers
7k views

How to measure the statistical "distance" between two frequency distributions?

I am undertaking a data analysis project which involves investigating website usage times over the course of the year. What I would like to do is compare how "consistent" the usage patterns ...
user avatar
17 votes
1 answer
21k 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 ...
user avatar
  • 321
17 votes
4 answers
42k views

Definition of normalized Euclidean distance

Recently I have started looking for the definition of normalized Euclidean distance between two real vectors $u$ and $v$. So far, I have discovered two apparently unrelated definitions: http://en....
user avatar
  • 679
16 votes
3 answers
13k views

Calculate the Kullback-Leibler Divergence in practice?

I am using KL Divergence as a measure of dissimilarity between 2 $p.m.f.$ $P$ and $Q$. $$D_{KL}(P||Q) = \sum_{i=1}^N \ln \left( \frac{P_i}{Q_i} \right) P_i$$ $$=-\sum P(X_i)ln\left(Q(X_i)\right) + \...
user avatar
16 votes
4 answers
12k views

What is the purpose of row normalization

I understand the reasoning behind column normalization, as it causes features to be weighted equally, even if they are not measured on the same scale - however, often in the nearest neighbour ...
user avatar
15 votes
1 answer
34k views

Cosine Distance as Similarity Measure in KMeans [duplicate]

I am currently solving a problem where I have to use Cosine distance as the similarity measure for k-means clustering. However, the standard k-means clustering package (from Sklearn package) uses ...
user avatar
  • 255
15 votes
1 answer
2k views

Is there an intuitive characterization of distance correlation?

I've been staring at the wikipedia page for distance correlation where it seems to be characterized by how it can be calculated. While I could do the calculations I struggle to get what distance ...
user avatar
14 votes
3 answers
37k views

Which distance to use? e.g., manhattan, euclidean, Bray-Curtis, etc

I am not a community ecologist, but these days I am working on community ecology data. What I couldn't understand, apart from the mathematics of these distances, is the criteria for each distance to ...
user avatar
  • 355
13 votes
4 answers
4k views

Is there any probability distance that preserves all properties of a metric?

In studying Kullback–Leibler distance, there are two things we learn very quickly is that it does not respect neither the triangle inequality nor the symmetry, required properties of a metric. My ...
user avatar
  • 1,249
13 votes
1 answer
4k views

Why is Kullback-Leilbler divergence a better metric for measuring distance between two probability distributions than squared error? [duplicate]

I know that KL-divergence is a metric that is more suitable when we want to measure the distance between numbers which a probability form. However, I am still confused what is the benefit of using KL-...
user avatar
  • 385
13 votes
4 answers
7k views

Is triangle inequality fulfilled for these correlation-based distances?

For hierarchical clustering I often see the following two "metrics" (they aren't exactly speaking) for measuring the distance between two random variables $X$ and $Y$: $\newcommand{\Cor}{\mathrm{Cor}}$...
user avatar
  • 133
13 votes
2 answers
11k 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....
user avatar
13 votes
2 answers
24k views

How does the Gower distance calculate the difference between binary variables'?

I have 17 numeric and 5 binary (0-1) variables, with 73 samples in my dataset. I need to run a cluster analysis. I know that the Gower distance is a good metric for datasets with mixed variables. ...
user avatar
12 votes
3 answers
19k views

Distance Metrics For Binary Vectors

I have vectors of same length consisting of 1 and 0. I am trying to find out how similar they are. So far I am using hamming distance that I calculate sum of one vector then sum of second vector and ...
user avatar
  • 241
12 votes
4 answers
6k views

Dynamic Time Warping for irregular time series

I have been reading a lot about Dynamic Time Warping (DTW) lately. I am very surprised that there is no literature at all on the application of DTW to irregular time series, or at least I could not ...
user avatar
  • 275
12 votes
1 answer
2k views

Efficient/fast Mahalanobis distance computation

Suppose I have $n$ data points $x_1,\dots,x_n$, each of which is $p$-dimensional. Let $\Sigma$ be the (non-singular) population covariance of these samples. With respect to $\Sigma$, what is the most ...
user avatar
12 votes
1 answer
3k views

Statistical significance of difference between distances

I have over 3000 vectors on a two-dimensional grid, with an approximately uniform discrete distribution. Some pairs of vectors fulfil a certain condition. Note: the condition is only applicable to ...
user avatar
  • 123
12 votes
3 answers
9k views

Intuitively, why is cross entropy a measure of distance of two probability distributions?

For two discrete distributions $p$ and $q$, cross entropy is defined as $$H(p,q)=-\sum_x p(x)\log q(x).$$ I wonder why this would be an intuitive measure of distance between two probability ...
user avatar
  • 121
12 votes
2 answers
4k views

What is the distance between a finite Gaussian mixture and a Gaussian?

Suppose I have a mixture of finitely many Gaussians with known weights, means, and standard deviations. The means are not equal. The mean and standard deviation of the mixture can be calculated, of ...
user avatar
  • 10.4k
12 votes
2 answers
559 views

Does Mercer's theorem work in reverse?

A colleague has a function $s$ and for our purposes it is a black-box. The function measures the similarity $s(a,b)$ of two objects. We know for sure that $s$ has these properties: The similarity ...
user avatar
  • 79.4k
12 votes
2 answers
1k views

Finding a known number of circle centers that maximize the number of points within a fixed distance

I have a set of 2-D data where I want to find the centers of a specified number of centers of circles ($N$) that maximize the total number of points within a specified distance ($R$). e.g. I have 10,...
user avatar
12 votes
0 answers
4k views

How to compare two distance matrices?

Suppose that I have two distance matrices for the same set of items. By a distance matrix I mean a square matrix whose (i,j)th entry holds the distance (in terms of cosine similarity) between ith and ...
user avatar
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 ...
user avatar
  • 5,616
11 votes
2 answers
18k views

Similarity measure between multiple distributions

To compare distributions, it is common to use box blots. I'm looking for a similarity measure that calculates whether distributions are the similar or not. Ideally, given that e.g. four ...
user avatar
  • 131
11 votes
2 answers
10k views

Is Mahalanobis distance equivalent to the Euclidean one on the PCA-rotated data?

I've been led to believe (see here and here) that Mahalanobis distance is the same as the Euclidean distance on the PCA-rotated data. In other words, taking multivariate normal data $X$, the ...
user avatar
  • 12.2k
10 votes
2 answers
9k views

How to find the expected distance between two uniformly distributed points?

If I were to define the coordinates $(X_{1},Y_{1})$ and $(X_{2},Y_{2})$ where $$X_{1},X_{2} \sim \text{Unif}(0,30)\text{ and }Y_{1},Y_{2} \sim \text{Unif}(0,40).$$ How would I find the expected ...
user avatar
  • 403
10 votes
4 answers
3k views

Clustering with asymmetrical distance measures

How do you cluster a feature with an asymmetrical distance measure? For example, let's say you are clustering a dataset with days of the week as a feature - the distance from Monday to Friday is not ...
user avatar
  • 2,220
9 votes
3 answers
2k views

Distance metric and curse of dimensions

Some where I read a note that if you have many parameters $(x_1, x_2, \ldots, x_n)$ and you try to find a "similarity metric" between these vectors, you may have a "curse of dimensioality". I believe ...
user avatar
  • 1,863
9 votes
2 answers
4k views

Probability that uniformly random points in a rectangle have Euclidean distance less than a given threshold

Assume we have $n$ points in a rectangular with bound $[0,a] \times [0,b]$, and these points are uniformly distributed in this plane. (I am not quite familiar with statistics, so I don't know the ...
user avatar
9 votes
2 answers
3k views

Expected magnitude of a vector from a multivariate normal

What is the expected magnitude, i.e. euclidean distance from the origin, of a vector drawn from a p-dimensional spherical normal $\mathcal{N}_p(\mu,\Sigma)$ with $\mu=\vec{0}$ and $\Sigma=\sigma^2 I$, ...
user avatar
  • 302
9 votes
2 answers
22k views

K-means: Why minimizing WCSS is maximizing Distance between clusters?

From a conceptual and algorithmic standpoint, I understand how K-means works. However, from a mathematical standpoint, I don't understand why minimizing the WCSS (within-cluster sums of squares) will ...
user avatar
  • 484
9 votes
1 answer
7k views

How is the distance formula related to the formula for standard deviation

The formula for the standard deviation of n numbers is the same as the formula for the distance between two points in n dimensions. Could someone explain why this is and how these are related?
user avatar
8 votes
3 answers
8k 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 ...
user avatar
  • 263
8 votes
1 answer
7k views

Measure for Separability

I have a (binary) classification problem where after merging single training data points (that can be tracked back to the same source) into aggregates, test accuracy (on single data points again) ...
user avatar
  • 295

1
2 3 4 5
14