209

Here is a scatterplot of some multivariate data (in two dimensions): What can we make of it when the axes are left out? Introduce coordinates that are suggested by the data themselves. The origin will be at the centroid of the points (the point of their averages). The first coordinate axis (blue in the next figure) will extend along the "spine" ...


70

Methods overview Short reference about some linkage methods of hierarchical agglomerative cluster analysis (HAC). Basic version of HAC algorithm is one generic; it amounts to updating, at each step, by the formula known as Lance-Williams formula, the proximities between the emergent (merged of two) cluster and all the other clusters (including singleton ...


65

Adding to the other excellent answers, an answer with another viewpoint which maybe can add some more intuition, which was asked for. The Kullback-Leibler divergence is $$ \DeclareMathOperator{\KL}{KL} \KL(P || Q) = \int_{-\infty}^\infty p(x) \log \frac{p(x)}{q(x)} \; dx $$ If you have two hypothesis regarding which distribution is generating the data $X$,...


53

It might help to give slightly more of an overview of MMD.$\DeclareMathOperator{\E}{\mathbb E}\newcommand{\R}{\mathbb R}\newcommand{\X}{\mathcal X}\newcommand{\h}{\mathcal H}\DeclareMathOperator{\MMD}{MMD}$ In general, MMD is defined by the idea of representing distances between distributions as distances between mean embeddings of features. That is, say we ...


39

My grandma cooks. Yours might too. Cooking is a delicious way to teach statistics. Pumpkin Habanero cookies are awesome! Think about how wonderful cinnamon and ginger can be in Christmas treats, then realize how hot they are on their own. The ingredients are: habanero peppers (10, seeded and finely minced) sugar (1.5 cups) butter (1 cup) vanilla ...


36

A (metric) distance $D$ must be symmetric, i.e. $D(P,Q) = D(Q,P)$. But, from definition, $KL$ is not. Example: $\Omega = \{A,B\}$, $P(A) = 0.2, P(B) = 0.8$, $Q(A) = Q(B) = 0.5$. We have: $$KL(P,Q) = P(A)\log \frac{P(A)}{Q(A)} + P(B) \log \frac{P(B)}{Q(B)} \approx 0.19$$ and $$KL(Q,P) = Q(A)\log \frac{Q(A)}{P(A)} + Q(B) \log \frac{Q(B)}{P(B)} \approx 0....


31

This question can be answered as stated only by assuming the two random variables $X_1$ and $X_2$ governed by these distributions are independent. This makes their difference $X = X_2-X_1$ Normal with mean $\mu = \mu_2-\mu_1$ and variance $\sigma^2=\sigma_1^2 + \sigma_2^2$. (The following solution can easily be generalized to any bivariate Normal ...


30

According to cosine theorem, in euclidean space the (euclidean) squared distance between two points (vectors) 1 and 2 is $d_{12}^2 = h_1^2+h_2^2-2h_1h_2\cos\phi$. Squared lengths $h_1^2$ and $h_2^2$ are the sums of squared coordinates of points 1 and 2, respectively (they are the pythagorean hypotenuses). Quantity $h_1h_2\cos\phi$ is called scalar product (= ...


29

$\DeclareMathOperator\EMD{\mathrm{EMD}} \DeclareMathOperator\E{\mathbb{E}} \DeclareMathOperator\Var{Var} \DeclareMathOperator\N{\mathcal{N}} \DeclareMathOperator\tr{\mathrm{tr}} \newcommand\R{\mathbb R}$The earth mover's distance can be written as $\EMD(P, Q) = \inf \E \lVert X - Y \rVert$, where the infimum is taken over all joint distributions of $X$ and $...


26

Obviously, k-means needs to be able to compute means. However, there is a well-known variation of it known as k-medoids or PAM (Partitioning Around Medoids), where the medoid is the existing object most central to the cluster. K-medoids only needs the pairwise distances.


23

I am providing an answer that is complementary to the one by @whuber in the sense of being what a non-statistician (i.e. someone who does not know much about non-central chi-square distributions with one degree of freedom etc) might write, and that a neophyte could follow relatively easily. Borrowing the assumption of independence as well as the notation ...


22

You are exactly describing the problem setting of kernel $k$-means; when you cannot represent a data point as a Euclidean vector, but if you can still calculate (or define) the inner product between two data points then you can kernelize the algorithm. The following webpage provides brief description of the algorithm: Kernel $k$-means page This kernel ...


22

Requirements for hierarchical clustering Hierarchical clustering can be used with arbitrary similarity and dissimilarity measures. (Most tools expect a dissimilarity, but will allow negative values - it's up to you to ensure whether small or large valued will be preferred.). Only methods based on centroids or variance (such as Ward's method) are special, ...


22

First of all, the violation of the symmetry condition is the smallest problem with Kullback-Leibler divergence. $D(P||Q)$ also violates triangle inequality. You can simply introduce the symmetric version as $$ SKL(P, Q) = D(P||Q) + D(Q||P) $$, but that's still not metric, because both $D(P||Q)$ and $SKL(P, Q)$ violates triangle inequality. To prove that ...


21

Starting from ahfoss's "succint" solution, I have used the Cholesky decomposition in place of the SVD. cholMaha <- function(X) { dec <- chol( cov(X) ) tmp <- forwardsolve(t(dec), t(X) ) dist(t(tmp)) } It should be faster, because forward-solving a triangular system is faster then dense matrix multiplication with the inverse covariance (see ...


21

It should be the same, for normalized vectors cosine similarity and euclidean similarity are connected linearly. Here's the explanation: Cosine distance is actually cosine similarity: $\cos(x,y) = \frac{\sum x_iy_i}{\sqrt{\sum x_i^2 \sum y_i^2 }}$. Now, let's see what we can do with euclidean distance for normalized vectors $(\sum x_i^2 =\sum y_i^2 =1)$: $...


20

Take a look at this paper that covers a wide range of popular metrics on the space of probability measure. My personal favorites are the total variation distance and $L^2$ Wasserstein distance (earth mover distance).


20

Or even with the same support, when one distribution has a much fatter tail than the other. Take $$KL(P\vert\vert Q) = \int p(x)\log\left(\frac{p(x)}{q(x)}\right) \,\text{d}x$$ when $$p(x)=\overbrace{\frac{1}{\pi}\,\frac{1}{1+x^2}}^\text{Cauchy density}\qquad q(x)=\overbrace{\frac{1}{\sqrt{2\pi}}\,\exp\{-x^2/2\}}^\text{Normal density}$$ then $$KL(P\vert\vert ...


18

Technically to compute a dis(similarity) measure between individuals on nominal attributes most programs first recode each nominal variable into a set of dummy binary variables and then compute some measure for binary variables. Here is formulas of some frequently used binary similarity and dissimilarity measures. What is dummy variables (also called one-...


17

If $d(p_1,p_2)$ represents the euclidean distance from point $p_1$ to point $p_2$, $$\frac{1}{1 + d(p_1, p_2)}$$ is commonly used.


16

It is plain, from looking at the question geometrically, that the expected distance between two independent, uniform, random points within a convex set is going to be a little less than half its diameter. (It should be less because it's relatively rare for the two points to be located within extreme areas like corners and more often the case they will be ...


16

You can't and you don't. Imagine that you have an random variable of probability distribution Q. But your friend Bob thinks that the outcome comes from the probability distribution P. He has constructed an optimal encoding, that minimizes the number of expected bits he will need to use to tell you the outcome. But, since he constructed the encoding from P ...


15

The question of "significantly" different always, always presupposes a statistical model for the data. This answer proposes one of the most general models that is consistent with the minimal information provided in the question. In short, it will work in a wide array of cases, but it might not always be the most powerful way to detect a difference. Three ...


15

Overview: KL-Divergence is derived from the Shannon entropy. The Shannon entropy is the amount of information contained in a signal X with distribution $\mathrm{P}(X)$. The cross entropy is the information contained in a signal X when we encode it with an estimated distribution $\mathrm{Q}(X)$ instead of its true distribution $\mathrm{P}(X)$. The KL-...


14

Unfortunately, in most situations there is not a clear-cut answer to your question. That is, for any given application, there are surely many distance metrics which will yield similar and accurate answers. Considering that there are dozens, and probably hundreds, of valid distance metrics actively being used, the notion that you can find the "right" distance ...


14

Let $x$ be one of your data points. Compute the Cholesky decomposition $\Sigma=LL^\top$. Define $y=L^{-1}x$. Compute $y$ by forward-substitution in $Ly=x$. The Mahalanobis distance to the origin is the squared euclidean norm of $y$: $$ \begin{align} x^\top\Sigma^{-1}x &= x^\top(LL^\top)^{-1}x \\ &= x^\top(L^\top)^{-1}L^{-1}x \\ &= x^\top(L^{-1})...


14

For distributions which do not have the same support, KL divergence is not bounded. Look at the definition: $$KL(P\vert\vert Q) = \int_{-\infty}^{\infty} p(x)\ln\left(\frac{p(x)}{q(x)}\right) dx$$ if P and Q have not the same support, there exists some point $x'$ where $p(x') \neq 0$ and $q(x') = 0$, making KL go to infinity. This is also applicable for ...


13

Seems like you're looking for either the Jaccard distance or the Dice dissimilarity. Jaccard distance: $1 - \frac{|A \cap B|}{|A \cup B|}$ Dice dissimilarity: $1 - \frac{2|A \cap B|}{|A| + |B|}$ These both are equal to zero if $A$ and $B$ are exactly the same, and one if they are completely different. However, Jaccard will "punish" differences more ...


13

Covariance (or correlation or cosine) can be easily and naturally converted into euclidean distance by means of the law of cosines, because it is a scalar product (= angular-based similarity) in euclidean space. Knowing covariance between two variables i and j as well as their variances automatically implies knowing d between the variables: $d_{ij}^2 = \...


13

As far as I understand, by irregular time series you mean unevenly spaced time series, also referred to as irregularly sampled time series. Since I am curious about time series in general, I have performed a brief research on the topic of your (and now mine) interest. The results follow. Despite high popularity of dynamic time warping (DTW) approach in time ...


Only top voted, non community-wiki answers of a minimum length are eligible