Standard metric for distance between two clusters

Question

Let $A=\{A_1,A_2,\cdots,A_m\}$ and $B=\{B_1,B_2,\cdots,B_n\}$ be two sets of points in $k$-dimensional Euclidean space. Each points $A_i$ or $B_i$ can be thought of as a feature vector of a data sample. I want to know if two distribution of $A$ and $B$ are similar or not.

I can proceed univariate analysis by drawing $k$ histograms for $A$ and $B$, respectively, and view the difference of them for each $k$.

Or I can proceed like this ; that's what I'm asking for. $A$ and $B$ are two clusters of points in a Euclidean space. So I can measure the distance between this two clusters. There might be various ways to define the distance, I can define by the minimal distance like

$$d(A,B)=\min_{i,j}||A_i-B_j||$$

where $||\cdot||$ is the L2 norm. Or I can define by the distance between centroid

$$d(A,B)=||C_A-C_B||$$

where

$$ \begin{align*} C_A&=\frac1m\sum_{i=1}^mA_i\\ C_B&=\frac1n\sum_{j=1}^nB_j \end{align*} $$

The former is bad since $A$ and $B$ practically overlap in some domain so that the distance is always set to nearly zero. The latter is better but have a limit ; If $A'$ has identical centroid as in $A$ but $A'$ is more scattered than $A$, then it is not desirable that $d(A',B)=d(A,B)$ ; it should be $d(A',B)<d(A,B)$.

As an alternative way to estabilish the distance, I can take standard deviations of the cluster into account ;

$$d(A,B)=\frac{||C_A-C_B||}{s_As_B}$$

where $s_A$ and $s_B$ are standard deviation of $A$ and $B$, respectively.

or I can define like

$$ \begin{align*} d(A,B)&=\frac{||C_A-C_B||}{{s_A}^2{s_B}^2}\\ d(A,B)&=\frac{||C_A-C_B||}{{s_A}^2+{s_B}^2} \end{align*} $$

Is there a standard way of defining this distance?

Note 1 : I heard the word "within cluster sum of variance" in the context of K-means clustering. But it doesn't seem to involve standard deviation.

Note 2 : chat GPT recommended the last equation.

Answer 1

As so often in data science, there is not one standard solution, but it depends on the use case and what you are aiming for. Furthermore, there are related concepts similar to the distance metrics on clusters.

In the following I will try to give and overview over some prominent methods (probably there are some missing), structure them and try to explain a bit when to use what:

Distance between clusters

A cluster is a region of the feature space

Typically, clustering alorithms try to partition the feature space into non-overlapping clusters. That means, that for most points of a cluster, the neighbour points belong to the same cluster (might be different for outliers and points at the border to other clusters) and we can imagine a cluster as a region in the feature space.

Key properties of clusters are

• their location (often defined by the centroid)
• their inner size, within distance or diameter, e.g. avg./max distance between point of the cluster. Alternatively the avg. or max distance to the centroid. The Variance can also be a measure for inner diameter, but I would consider that more a distribution property
• their distance to other clusters (between the centroids, some points or all points)

From these, a number of distance metrics can be formulated:

Absolute distances

Here, I mainly repeat your proposed metrics

1. Minimal Distances $$d_{\mathrm{min}}(A,B) = \min_{i,j}\|A_i-B_j\|$$ This focuses on the "gap" between both clusters and should be used when the absolute
2. Distance of the centroids $$d_{\mathrm{centroid}}(A,B) = \|C_A-C_B\|$$ This totally ignores the "size" or "diameter". Even strong overlaps might not effect this metric. Use with care when the gap can totally be ignored.
3. Average distance $$d_{\mathrm{avg}}(A,B) = \frac{1}{|A|\cdot|B|}\sum_i\sum_j\|A_i-B_j\|$$ This considers both location and diameter. In some cases, you are more interested in the average distance from one point of $A$ to one point of $B$
4. Other statistics: Maximal distance, median distance, ... can all suit some specific cases.

Normalized / Relative distances

In some cases, it makes sense to have distances relative to the size of the clusters. A distance of 10 between two clusters, each of diameter 1, might appear "larger" than the distance of 50 between clusters of diameter 1000.

Note: Relative distances are often no distance metrics in the mathematical sense. Typically, they do not fulfill the triangle inequality!

Sanity check: If you double ever feature value (which would double all distances and the diameter), the relative distance should stay the same (scale invariance). Your proposed relative metrics (also the one that chatGPT proposes) fail this check.

Approaches would be to normalize by the some kind of average or sum of the diameter of both clusters. Using a diameter / within cluster distance $d_\mathrm{within}(A)$ and an absolute distance (see above for choices) $d_{\mathrm{abs}}(A,B)$ these are (some) options: $$\frac{d_{\mathrm{abs}}(A,B)}{d_\mathrm{within}(A) + d_\mathrm{within}(B)}$$ $$\frac{d_{\mathrm{abs}}(A,B)}{\sqrt{d_\mathrm{within}(A)^2 + d_\mathrm{within}(B)^2}}$$ $$\frac{d_{\mathrm{abs}}(A,B)}{\sqrt{d_\mathrm{within}(A)d_\mathrm{within}(B)}}$$ In your case of $d_\mathrm{within}(A)=s_A$ I would suggest the second since variances can be additive.

Evaluation of clusterings

If your goal is to evaluate clusterings, there are indices that compute a value for a clustering with $m$ clusters. This is for example used to determine the optimale number of clusters: one does a clustering with $m=m_L,m_L+1,\ldots,m_H$ clusters and take the clustering with the best cluster index.

Popular algorithms are:

1. Dunn index
2. Davies–Bouldin index
3. Silhouette

Explaining them in detail is out of scope of this already long answer.

Distribution distances

In difference to clusters, distributions might (and often will) overlap. Distances between distributions are typically based on stochastic, statistic or information-theoretic concepts.

There exist multiple approaches to measure distance, similarity or the difference between distributions. Some prominent approaches are:

1. Statistical tests. This approaches typically test whether, the known points / samples of both distributions belong to different distrubutions.
2. Kullback-Leibner divergence. This a distances (but not a metric) between two distributions. Is is ovent used to see how close one observed distribution is to a theoretic one. It is especially used when distributions assumptions are made in models, but has also other applications. Note that the KL-divergence is not symetric!
3. Wasserstein distance with the special case optimal transport. Descriptively spoken it measures how far one has to move the points of $A$ to get the distribution of $B$