Questions tagged [distance-functions]
Distance functions refer to functions used for quantifying the notion of distance between members of a set, or between objects.
0
votes
0answers
13 views
How to Measure/Quantify Similarity between > 2 Sets of Dummies Indicators
I have multiple sets, each with a binary indicator for whether an element is part of the set.
...
0
votes
0answers
31 views
Signature of a distribution - Earth Mover distance
I am studying the Earth Mover Distance from here, but I have some difficulty in fully understanding what is the signature of a distribution and how it matches with the last constraint of the Earth ...
0
votes
0answers
33 views
Total variation norm
I am reading
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., & Zemel, R. (2012, January). Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science ...
0
votes
0answers
10 views
How to derive a formula based on hierarchy
I have a hierarchy as follows.
I want to rank the leaf nodes (i.e. 2, 3, 4) by comparing its position relativly to the two nodes 1 and 5.
For instance, node 4 should be ranked highest as it is ...
0
votes
0answers
15 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 ...
0
votes
0answers
19 views
determine suitable values for the parameters of the distance function for this graph
Hi I've been learning data mining and came across this question. I couldn't seem to figure it out myself.
So we have a large single undirected graph(without attributes) G = (V,E) and want to detect ...
0
votes
0answers
217 views
Jaccard Index for Binary Data in R using dist function
I have a presence/absence table of 0s and 1s and I would like to cluster this data. I want to create a pairwise matrix using R's dist function which has a binary ...
1
vote
1answer
14 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 ...
0
votes
0answers
70 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=...
2
votes
1answer
207 views
Is one-hot encoding and standardization of data equivalent to Gower's distance?
For clustering and other techniques for mixed data (numerical and categorical), Gower's distance is usually more preferred than Euclidean distance because the former computes distance differently for ...
0
votes
0answers
28 views
Similarity measure before and after dimensionality reduction or clustering
I have a dataset with 500 000 samples, each sample contains 30 features.
The values of the features are in the range 0.0 to 1.0.
...
0
votes
0answers
18 views
Mahalanobis: Covariance or correlation? [duplicate]
Is the Mahalanobis distance using correlations or covariances (among two vectors) to determine the similarity? I know that both are quite the same and differ only by a division of a standard deviation ...
1
vote
0answers
34 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. ...
0
votes
0answers
13 views
How to measure the “variability” across a set of many (>>2) probability distributions?
Given a set of many of discrete probability distributions, is there a way I can efficiently calculate a metric that quantifies how different the entire set of these probability distributions are to ...
0
votes
0answers
8 views
Calculate association trends
I have time series dataset for 10 consecutive periods (i.e. T, T+1, T+2, ..., T+9). Moreover, I also have 100 term triplets in each time period. Each triplet contains 3 objects namely x, y and z.
I ...
3
votes
1answer
143 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 ...
3
votes
1answer
107 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
vote
0answers
25 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?
2
votes
1answer
286 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 ...
0
votes
0answers
15 views
How is the matching distance used in the Jaro similarity index?
I read the codes in this link to have a better understanding of the Jaro similarity index. According to wikipedia, one part of the algorithm requires comparing if there are common characters using a ...
0
votes
0answers
10 views
($L_2$) distance for noisy data
I'm given a subspace $V$ and a set of $n$ corrupted observations $\tilde{x}_1 = x_1 +\epsilon_1,...,\tilde{x}_n = x_n + \epsilon_n \in \mathbb{R}^D$. Assume $D$ is large and that $\epsilon_i \sim N(0, ...
-1
votes
1answer
163 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
0answers
134 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 ...
0
votes
0answers
43 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 ...
0
votes
1answer
198 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 ...
4
votes
2answers
312 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 $...
2
votes
0answers
57 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) ...
0
votes
1answer
115 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
votes
2answers
108 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. ...
1
vote
0answers
25 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)=...
0
votes
1answer
193 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....
3
votes
2answers
177 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 ...
0
votes
1answer
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 ...
1
vote
0answers
22 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 ...
1
vote
2answers
63 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, ...
4
votes
2answers
548 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 ...
0
votes
3answers
1k 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?
1
vote
0answers
396 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 ...
2
votes
0answers
458 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 ...
0
votes
0answers
75 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 ...
1
vote
0answers
78 views
Finding optimal parameters for Mahalanobis distance's covariance matrix [closed]
I have to correctly classify a data set (~1000 instances) for 2 classes, either 0 or 1.
I have a training set of the same size. My first thought is to use a $k$-NN classification. However, instances ...
5
votes
1answer
3k 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 ...
0
votes
2answers
50 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 ...
0
votes
1answer
144 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 ...
2
votes
1answer
76 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(...
1
vote
0answers
130 views
covariance matrix of individuals or of the pool?
At first: I have individuals represented by vectors with four entries/properties:
...
1
vote
0answers
666 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-$...
1
vote
1answer
94 views
square root missing in code?
I'm using Pairwise Mahalanobis distance in R as code to calculate the Mahalanobis distance:
...
-1
votes
1answer
904 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 ...
10
votes
1answer
423 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]...
