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
2
votes
0
answers
297
views
Distance measure for two probability distribution of unequal sample size
Context: I have 100 stores and these stores are divided into 10 business markets. I want to select 3 markets where each market is a good representation of the 100 stores i.e. the population.
There ...
- 43
1
vote
0
answers
36
views
How to transform $P[k_1\leq (x_i-\mu - \sigma\cdot Z)^2 \leq k_2]$ to $P[k_1\leq \frac{(x_i-\mu)^2}{\sigma^2}+e \leq k_2]$?
Taste estimation
As an example consider an experiment conducted to determine the optimal concentration of salt in popcorn. The concentration of salt in sample $i$ is denoted by ${x_i}$.
The subject ...
- 11
1
vote
1
answer
95
views
Understanding PAM - why is it greedy?
I've been studying k-medoids for a while but i can't understand the first step or BUILD step: in particular i can't get how the initial medoids would be "greedy". I'm not much confident with the ...
- 53
0
votes
0
answers
193
views
How to measure the difference between two random forest models?
Suppose that I have training data defined as a set of N records (or samples) defined by its attributes (or descriptors, features, as you prefer), and I trained two random forest models with two parts ...
- 224
0
votes
1
answer
169
views
Mahalanobis distance - understanding the formula [duplicate]
I've read quite a few explanations on this topic, liking this one the most:
https://mccormickml.com/2014/07/22/mahalanobis-distance/
But there is still one thing I don't understand.
I understand ...
0
votes
0
answers
102
views
Type of logarithm in Jenson-Shannon and Bhattacharyya distance
Both Jenson-Shannon and Bhattacharyya distance can be used to measure the similarity of two probability distributions.
Bhattacharyya distance between two distributions $p$ and $q$ is defined as $D_B(...
- 111
1
vote
1
answer
84
views
Dissimilarity or distance metrics between pairs of values
I have cubes (objects) in which their volume was manually calculated (let's call this method the "manual method". Assume that the volume measures obtained by this method are considered the "true" ...
- 133
2
votes
1
answer
1k
views
Am I right that Calinski-Harabasz index (Pseudo-F) can not be calculated from a distance matrix other than euclidean?
Part:
I wonder if one could calculate the Calinski-Harabasz index when only having a distance matrix (and a cluster solution, of course). As you need the within and between sum of squares to come up ...
- 51
1
vote
0
answers
23
views
Does Mahalanabis Distance have something to do with Min-Max normalisation? [duplicate]
Does Mahalanabis Distance have something to do with Min-Max normalisation?
I know that it has something to do with Z-score normalisation, but when I tried Mahalanabis Distance on the Min-max ...
- 141
1
vote
1
answer
1k
views
Is Hierarchical clustering a special case of knn(specific n=1)?
I'm working on time series in the scope of similarity detection at the moment. What seems to be a well researched approach is dynamic time warping in combination with k-1NN as classification ...
- 121
3
votes
1
answer
86
views
Non-metrics give "pathological" solutions: what does this mean?
In this set of slides on DTW, slide 25 says that we generally prefer metrics over measures because,
"Non-Metrics can sometimes give pathological solutions when clustering or classifying data etc."
...
- 133
3
votes
0
answers
268
views
Which distance metric to use to cluster categorical sequences (clickstreams or clickpaths)?
For my research, I want to cluster website visitors based on their clickstreams to understand different information behavior patterns (i.e., customer/visitor journeys). The data can be characterized ...
- 51
0
votes
0
answers
44
views
Proxy for Mahalanobis distance when n < p? [duplicate]
I'm working on a ranking problem where I want to measure the distance between a collection of query points (as a group) and each target point in my database. Each query point is part of the set of ...
- 863
2
votes
1
answer
36
views
Finding the effect of nodes on a density heatmap
Let's say I have a geo-tagged dataset of all payment transactions for businesses in a city. I know whether each payment is made by cash or card, and have made a heatmap of where in the city the ...
- 389
2
votes
0
answers
599
views
Relationship between KL divergence, JS divergence, and MMD?
What kind of relationship is there between the KL (Kullback-Leibler) divergence, JS (Jensen-Shannon) divergence, and MMD (maximum mean discrepancy)?
I know that they all share a global minimum at $P=...
- 21
1
vote
0
answers
82
views
Distance between two distributions
I am analyzing time-series data, and I would like to detect a significant change in data distribution. I already know about Bhattacharyya distance, but that requires histograms of equal-sized bins. ...
- 111
4
votes
1
answer
3k
views
Calculation of relative distance
I have 100 term triplets as shown in the below mentioned figure. Each triplet contains 3 objects namely x, y and z. I want to rank the triplets according to the following two properties.
y should be ...
- 155
4
votes
1
answer
386
views
The violation of triangle inequality in KNN
If the 0<p<1 in the distance metrics, then the triangle inequality is violated.
The question as follows
Does the violation of this inequality affect the ...
- 1,919
1
vote
0
answers
42
views
Distance metrics [closed]
I read about different distance metrics, such as Euclidean distance and so on.
What are the machine learning algorithms that use distance metrics in their calculations?
- 309
3
votes
1
answer
3k
views
How can I order kmeans clusters?
I have a kmeans cluster object and I would like to order the clusters. Not the observations within the clusters, rather the clusters in order of each other.
Is there a way of doing this? I found ...
- 1,528
-1
votes
1
answer
474
views
Cleaning Up the Data with Mahalanobis Distance [duplicate]
I have a data set and I want to cleaning up my data set from the ouliers, so I decide to use the Mahalanobis distance to find the outliers. But I have a problem here since my covariance matrix isn't ...
1
vote
0
answers
299
views
What happens with Mahalanobis-Distance, when the assumption of equal Covariance-Matrices breaks down
Assume that we want to compare the forecast quality of various forecasters $f$ on $n$ values such as stock-market prices or whatever. We could then define a "Mahalanobis-Distance" (MD) (or rather ...
- 2,801
0
votes
0
answers
60
views
What distance measure (e.g. Jaccard) to use when there are correlated observations?
I would like to use a simple distance measure (e.g. Jaccard) on a rather sparse set of 0/1 variables or probability densities, for which some of the observations are similar; this is due to repeated ...
- 255
2
votes
1
answer
988
views
Is Earth Mover Distance has maximum bound?
I have two probability distributions which each distribution has sum up to 1.
I want to compute the distance between those two probability distributions. I want to use Earth Mover Distance to ...
- 441
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
2
votes
0
answers
104
views
Recovering a distance matrix from nonnegative sparse correlation matrix?
After doing extensive literature research in all sorts of science I am completely puzzled. I am trying to find out what the state-of-the-art techniques would be to recover a (let's say euclidean) ...
- 230
2
votes
1
answer
259
views
When does the Wasserstein metric attain inequality WLOG?
I’m reading a classic paper [1] that describes a version of the Wasserstein metric (aka Mallows metric), defined as follows. Let $F$ and $G$ be probabilities in $\mathbb{R} ^B$, and let $U \sim F$ and ...
- 3,571
3
votes
2
answers
159
views
Distance calculation on variables that cannot be represented in the Euclidean space
Given a variable such as number of events attended together, which is more of a multi-dimensional data how can you calculate a sort of distance between people (i.e. ...
- 103
1
vote
0
answers
28
views
Name of divergence $D(p||q) = \max_x {p(x) - q(x)}$
$D(p||q) = \max_x {p(x) - q(x)}$ is thought of as a very simple divergence for two continuous probability distributions.
This satisfies minimum requirements of divergence, $D(p||q)\ge0$ and $D(p||q)=...
- 225
1
vote
1
answer
488
views
K-means clustering on a large matrix using kendall's tau as a distance measure
I'm trying to use kmeans clustering on a relatively large matrix (4000x4000) using the amap::Kmeans function but R seems to be freezed even after more than half an hour. I have to restart R after this....
- 919
5
votes
2
answers
450
views
Distance metric for source code
I'm trying to compare source code from multiple github projects, and in particular I'm looking for projects that include large chunks of code from other repositories, or large chunks with small ...
- 831
0
votes
1
answer
35
views
How to compare hundreds of one-dimensional functions
I have hundreds (2002 in today's case) of functions of the distance between two objects: $f_1(x)$, $f_2(x)$, ..., $f_{2002}(x)$. They are correlation functions. They all converge to 0 when $x$ is ...
- 101
1
vote
0
answers
34
views
How to calculate the similarity/distance between multiple measures for a single individual
I have what may be a relatively simple query, but I'm unsure of the best way to do it. I would like to calculate the similarity between multiple measures for a single individual. I have a data matrix ...
- 11
1
vote
2
answers
1k
views
calculating distance to 1 (positive and negative numbers)
I have what I assume is a very simple question.
I have a range of numbers from 81 to -6, that corresponds to racios pop. growth/urban construction of cities. The ideal ratio would be = 1. I need, ...
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
0
votes
3
answers
4k
views
Can I use Manhattan distance on binary data for hierarchical clustering?
I understand that classically Jaccard and Hamming work best with binary data, but is there anything specifically wrong with using a Manhattan distance instead with the complete linkage function?
- 157
1
vote
0
answers
1k
views
Distance Matrix for Big Data
I have been struggling to create a distance matrix for some Big Data (800,000x20). I have tried R (dist function), Matlab (pdist function), and cloud computing (to increase RAM).
Ultimately, the ...
- 106
3
votes
0
answers
939
views
Clustering in high dimensions: distance metrics, binary vs continuous, statistical tests for number of clusters / noise points [closed]
I’ve got several thousand observations in approximately 300-dimensional space, in a relatively sparse matrix (typically 30 non-zero dimensions per observation). I'm using a clustering algorithm (so ...
- 41
0
votes
0
answers
91
views
Levenshtein distance "proper" range for fuzzy matching
I am hoping to use Levenshtein distance concept for fuzzy matching in SQL joins between two tables on t1.first_name||last_name = t2.first_name||last_name.
Is ...
- 101
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
0
votes
2
answers
101
views
Clustering with Self Organizing Maps including time, date and month as attributes
I am about to start up a project on pattern recognition in a highdimensional dataset holding information on transactional salesdata for a company. In that manner I have decided to use the method of ...
- 133
0
votes
0
answers
626
views
Analysis or Comparison of Euclidean Distance matrix
Related: Average distance in distance matrix
I'm looking for some way to compare euclidean distance matrices. The matrices I need to compare will have constant number of rows but varying number of ...
- 113
3
votes
1
answer
138
views
Mahalanobis distance invariant against further elements/individuals?
Assume following: There are ten individuals and each is represented by two properties (Size and Gender).
Now I measure the distance between two individuals A and B via the Mahalanobis distance:
$$
d(...
- 2,939
1
vote
0
answers
154
views
covariance matrix of individuals or of the pool?
At first: I have individuals represented by vectors with four entries/properties:
...
- 2,939
1
vote
0
answers
1k
views
Distribution of the Mahalanobis distance between two samples from a Gaussian distribution
Let $\mathbf{X}=(X_1,\dots,X_p)\sim\mathcal{N}(\mu,\Sigma)$ be a Gaussian random vector. We all know that
$$d^2(\mathbf{X},\mu) = (\mathbf{X}-\mu)^T\Sigma^{-1}(\mathbf{X}-\mu) $$
has a $\chi^2_p-$...
- 16.7k
2
votes
1
answer
153
views
square root missing in code?
I'm using Pairwise Mahalanobis distance in R as code to calculate the Mahalanobis distance:
...
- 2,939
1
vote
1
answer
2k
views
Normalizing edit distance on strings
I am going to run a clustering algorithm on strings (sequences of characters). I would like to use the edit distance, but it seems to be misleading as I perceive ...
- 2,608
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
0
votes
0
answers
676
views
can I use manhattan distance function on hartigan wong kmeans clustering
I would like to perform Hartigan Wong clustering on high dimensional data. As I understand, Manhattan distance works better than the Euclidean distance in higher dimensions.
I have been using the K-...
- 223
2
votes
0
answers
536
views
Euclidean vs Manhattan distance behaviour in high dimension - curse of dimensionality
I have compared different distance functions by computing the average tf/idf distance between documents. My results show a range between $10-15$ for the Manhattan and a range between $1-1.5$ for the ...