Questions tagged [distance-functions]

Distance functions refer to functions used for quantifying the notion of distance between members of a set, or between objects.

103 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9 votes
0 answers
8k 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'. ...
user avatar
5 votes
0 answers
983 views

Compute Shannon entropy between every row of a large, sparse matrix

I have a sparse, binary matrix of user (rows) and items (columns). Each element of this matrix is either 0 or 1: ...
user avatar
  • 22.4k
5 votes
0 answers
223 views

Comparing term-frequency distributions with unequal sample sizes?

Background I have several datasets of word frequencies where some datasets have much more data than others: from 3000 samples to 20000 samples. I also have large reference corpora with millions of ...
user avatar
  • 279
5 votes
1 answer
1k views

Bhattacharyya distance for three histograms

There is a paper “Auto White Balance Based on the Similarity of Chromaticity Histograms” mention about automatic white balance. One of the key point of this algorithm is how to measure the similarity ...
user avatar
4 votes
0 answers
1k views

Scaling a distance to account for missing values

We can compute the Euclidean distance between two vectors $\mathbf{x}$ and $\mathbf{y}$ by: $$ d(\mathbf{x}, \mathbf{y}) = \sqrt{(x_1-y_1)^2 + \ldots + (x_n - y_n)^2} $$ When there are missing values ...
user avatar
  • 944
4 votes
0 answers
191 views

Approximating a Poisson distribution using a partially observed Gaussian

Note that the problem specification has changed since the original posting. Thanks to whuber for helping me better specify the question: in an attempt to make the question general, I had left out ...
user avatar
3 votes
0 answers
53 views

Metrics for assessing the quality of prior distributions

Clarification: My purpose is to compare different methods for selecting/creating priors (or perhaps I should refer to them as predictive distributions for a quantity of interest/parameter). I do not ...
user avatar
  • 23.4k
3 votes
0 answers
242 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 ...
user avatar
  • 51
3 votes
0 answers
1k views

Why the chi-square distance gives a better in high dimensional space

I am a beginner in machine learning. I did a classification program using KNN using two similarity distances: Euclidean distance and chi-square distance.The size of each feature vector is 10000. I ...
user avatar
3 votes
0 answers
112 views

Name of an $f$-divergence

The term divergence means a function $D$, which, given two probability distributions $P,Q$, assigns a non-negative real number $D(P,Q)$ such that $D(P,Q) = 0$ iff $P(x)=Q(x) \forall x$. The relative ...
user avatar
  • 1,021
3 votes
0 answers
740 views

What is a good similarity measure to use when missing data is a significant issue?

I have a list of cities that I want to compare in terms of their similarity. Each city can described by a large but finite number of characteristics but most of them will have missing data for some ...
user avatar
3 votes
0 answers
835 views

What is a good technique for grouping objects based on binary or dichotomous traits?

I have a set of objects each of which has a list of traits. Data on the traits is binary: an object has a trait or does not. The number of objects that I have is moderately greater than the number ...
user avatar
  • 2,617
3 votes
0 answers
159 views

Facebook users similarities

I'm searching for a similarity metric such that given two Facebook users it returns a value that reflects how similar the two users are. The similarity metrics must take into account (at the same time)...
user avatar
  • 215
3 votes
0 answers
193 views

Similarity Amongst Recipes Using Ingredients and Reviews/Descriptions

I'm still toying with things and just learning this, so please forgive any incorrect terminology. My toy data set is a collection of recipes with a fairly significant overlap in ingredients. I'm ...
user avatar
  • 131
3 votes
0 answers
441 views

Similarity measure for weighted sets (multisets)

I have to compute a similarity measure between different sets (Actually they are more like maps than sets). A weight is associated to each element of the set. The sets I want to compare represent ...
user avatar
3 votes
0 answers
176 views

A best measure for speaker recognition

I have a set $E_{1}$, with a finite cardinality $n$ of rectangular matrices which contains the useful MFCC coefficients generated from $n$ speech signals. Similary I have a set $E_{2}$ of same ...
user avatar
  • 71
3 votes
1 answer
9k views

Jaccard distance vs Levenshtein distance for fuzzy matching

My data is similar to the following data, but far bigger and more complex. Apple Banana Those fruits Tomato Cocumber These vegetables I would like to get the ...
user avatar
  • 4,963
2 votes
0 answers
81 views

How to Show Wasserstein Metric is Sum Invariant?

A paper I'm trying to understand states that that Wasserstein metric obeys certain properties, which I'd like to prove. This metric is defined for two random variables $U, V$ and $p \in (1, \infty)$ ...
user avatar
2 votes
0 answers
130 views

Similarity between clusters/groups?

I have a dataset consisting of multiple groups in a high dimensional space. An example is shown below: What would be the best way to calculate similarities between groups. Say how similar is group A ...
user avatar
2 votes
0 answers
361 views

How to calculate Mahalanobis distance in very high dimensions with both continuous and categorical variables?

The objective is outlier detection via a distance measure. Does mahalanobis distance suffer from curse of dimensionality just like Eucledian distance for very high dimensions? (say around 5000 ...
user avatar
2 votes
0 answers
71 views

Hierarchical clustering: distance/linkage combination that allows starting in the middle of the dendrogram

I want to use hierarchical clustering to classify some ecological data (species abundances on different places), so I would like to use a Manhattan type distance that doesn't account for double ...
user avatar
2 votes
0 answers
58 views

Determine outliers for robust Mahalanobis distance

I want to apply a robust mahal distance and found an implementation in scikit: https://scikit-learn.org/stable/auto_examples/covariance/plot_mahalanobis_distances.html but there is the number of ...
user avatar
  • 2,309
2 votes
0 answers
239 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 ...
user avatar
  • 43
2 votes
0 answers
534 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=...
user avatar
  • 21
2 votes
0 answers
103 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) ...
user avatar
  • 230
2 votes
0 answers
514 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 ...
user avatar
2 votes
0 answers
89 views

Doing Mahalanobis Metric Learning on a Per-Population Basis?

I have a dataset that consists of pairs $(x,y)$, with: $x$ being a high dimensional vector of personal features (e.g height, weight etc) of individuals; the individuals belong to one of three ...
user avatar
  • 2,222
2 votes
0 answers
102 views

How to choose the best dissimilarity method?

There are a lot of methods to measure the distance between pairs of objects such as Euclidean distance, Standardized Euclidean distance, Minkowski, Cosine distance and Correlation distance,.... etc ...
user avatar
  • 21
2 votes
1 answer
75 views

How to build a distance function given a cluster of points?

Given a non-elliptical cluster of points in a n-dimensional space I would like to get a distance function from the centroid of this cluster such that its "equipotential" surfaces has the same shape as ...
user avatar
2 votes
0 answers
158 views

$L_1$ distance between two Gaussian processes

In Brown's famous paper (1996), the $L_1$ norm between two Gaussian processes defined on time domain $[0,1]$ $$dY_t = f(t)dt + \sigma(t)dB_t\quad\text{and}\quad dZ_t = g(t)dt + \sigma(t)dB_t$$ is ...
user avatar
  • 151
2 votes
0 answers
128 views

How to create a (perceptual) distance function from human-generated examples?

My goal is to create a perceptually balanced distance metric to compute the similarity between two scatter plots (inspired by the work on Graph-Theoretic Scagnostics). My plan is to run a user study ...
user avatar
2 votes
0 answers
45 views

Bhattacharyya Distance for Age/Gender Groups?

I'm calculating distances for groups based on Age/Gender Compositions (to rank their similarity in demographic composition.) I'm working with the following: Men 18-34, Men 35-49, Men 50-64, Men 65+, ...
user avatar
2 votes
0 answers
274 views

Calculate the Hamming Distance between the two same datasets

How to Calculate the Hamming Distance between two datasets of same points?Both the data sets look exactly the same. http://postimg.org/image/u11qnsolh/ There are two datasets of same number of points....
user avatar
2 votes
0 answers
307 views

Kernel Methods for Binary Vectors

I am currently involved in a project which requires a minor point in choosing a proper similarity metric for a set of binary vectors, i.e. all components are either 1 or 0. Currently, the go-to ...
user avatar
2 votes
0 answers
51 views

Way to Measure Groupings Using Distances Between Individuals?

I am working on a problem that requires me to measure groupings of people. I have the location of every individual in my sample at every point in time. It's therefore trivial to calculate the ...
user avatar
  • 121
2 votes
0 answers
316 views

Calculate number of standard deviations separating two multivariate Gaussians?

Given a set of multivariate Gaussian distributions (from fitting a Gaussian mixture model) I would like to be able to calculate the likelihood that a data point drawn from one Gaussian will improperly ...
user avatar
  • 21
2 votes
0 answers
179 views

Statistical Test for Differences in Groups Based on Multivariate Function/Map

I've recently run into an issue where I am trying to test for a statistical difference between two groups, where each element of a group is itself a data object. For any pair of objects, I can ...
user avatar
  • 203
2 votes
0 answers
205 views

LDA, Significance of orthonormality- Trace Ratio Maximization

The objective of fisher linear discriminant analysis can be formulated as maximizing $\frac{Tr[X^TAX]}{Tr[X^TBX]}$ over $X$ where $A$ and $B$ are positive semi-definite with orthonormality constraints ...
user avatar
  • 2,365
1 vote
0 answers
48 views

What are the moments of the Beckmann distribution?

Let $U=(u_1, u_2)$ and $V=(v_1, v_2)$ be two randomly distributed points on the Euclidean plane assuming bivariate normal distributions $U \sim N(\mu_u, \Sigma_u)$ and $V \sim N(\mu_v, \Sigma_v)$ with ...
user avatar
  • 11
1 vote
1 answer
117 views

Bhattacharya Distance for Sets of Vectors

I have two sets of vectors and want to find a differentiable measure that can help quantify/approximate the degree of separability of the two sets. This metric might correlate well with the ...
user avatar
1 vote
0 answers
423 views

k-means inertia

I use Minkoski distance to measure distance, like so: I'm trying to locally optimize centroids by averaging the points that were assigned to the centroids. After using k-means with (p,k) when p is ...
user avatar
  • 111
1 vote
1 answer
38 views

Modified distance functions for a cluster analysis

I'm developing some software to allow users to perform various kinds of clustering on some data using a pairwise distance matrix (k-medoids is the main method). I would like to allow the user to tune ...
user avatar
1 vote
1 answer
82 views

Metric for distance of sinewaves

I have time-series data consisting of the sum of 2 sinewaves and my goal is to predict their frequencies and their amplitudes. I would like to know what are the best distance metrics/loss functions I ...
user avatar
  • 31
1 vote
0 answers
35 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 ...
user avatar
  • 11
1 vote
0 answers
69 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. ...
user avatar
1 vote
0 answers
273 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 ...
user avatar
  • 2,741
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)=...
user avatar
  • 225
1 vote
0 answers
33 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 ...
user avatar
  • 11
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 ...
user avatar
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: ...
user avatar
  • 2,309