Distances

[henryliangt]

There are several ways to compute the distance between two arrays, each with its unique characteristics and use cases. The most common ones include:

Euclidean Distance: This is probably the most commonly used distance measure. It's based on the "ordinary" straight-line distance between two points in Euclidean space.

Manhattan Distance: Also known as the city block or taxicab distance, this measure computes the distance that would be traveled to get from one data point to the other if a grid-like path is followed, much like navigating through city streets.

Chebyshev Distance: This distance measure considers the maximum absolute difference between elements of two vectors. For a two-dimensional plane, it is equivalent to allowing movements diagonally as well as along axes, much like a king in chess.

Minkowski Distance: This is a generalized metric form of Euclidean Distance and Manhattan Distance. The Euclidean distance is a special case where p=2, and the Manhattan distance is a special case where p=1. For different values of p, you get different distance metrics.

Hamming Distance: This is used for categorical data and calculates the number of differences between two vectors. It's typically used with binary data.

Cosine similarity/Distance(Angular distance): This measure calculates the cosine of the angle between two vectors. It determines the cosine similarity between them, which can be used as a measure of distance.

Mahalanobis Distance: This distance measure considers the correlations of the data set and is not scale invariant. The distance between a point and a distribution is defined as the multi-dimensional analog of the standard deviation.

Jaccard Distance: This is a measure of how dissimilar two sets are. It's the complement of the Jaccard coefficient and measures the dissimilarity between sample sets, not the actual values in the vector.

Canberra Distance: This is a weighted version of Manhattan distance, useful for data which encodes relative change.

Pearson Correlation Distance: This distance measure is derived from Pearson's correlation coefficient, which gauges the linear correlation between two data sets.

Earth Mover's Distance (EMD): Also known as Wasserstein distance, it measures the distance between two probability distributions over a region.

Edit Distance (Levenshtein Distance): This measures the minimum number of operations (edits) required to transform one sequence into another. The operations can include insertions, deletions, and substitutions. It's extensively used in applications related to spell checking, DNA sequence alignment, etc.

Another variant of the Edit Distance is the Damerau-Levenshtein Distance, which allows transpositions (swapping of two adjacent elements) as well as the basic operations.

Remember that the choice of distance measure will often depend on the nature of your data, and there may not be a one-size-fits-all solution.

[henryliangt]

[henryliangt]

欧几里得距离或者余弦相似性，经常在 k-NN、 UMAP、HDBSCAN 等算法中使用，

数据是高维的，欧几里德距离还能用吗？

地理空间信息组成的，也许半正矢距离是很好的选择？

[henryliangt]

欧式距离可解释为连接两个点的线段的长度。欧式距离公式非常简单，使用勾股定理从这些点的笛卡尔坐标计算距离。

缺点：尽管这是一种常用的距离度量，但欧式距离并不是尺度不变的，这意味着所计算的距离可能会根据特征的单位发生倾斜。通常，在使用欧式距离度量之前，需要对数据进行归一化处理。

此外，随着数据维数的增加，欧氏距离的作用也就越小。这与维数灾难（curse of dimensionality）有关。

用例：当你拥有低维数据且向量的大小非常重要时，欧式距离的效果非常好。如果在低维数据上使用欧式距离，则如 k-NN 和 HDBSCAN 之类的方法可达到开箱即用的效果。

[henryliangt]

余弦相似度（Cosine Similarity）

余弦相似度经常被用作抵消高维欧式距离问题。余弦相似度是指两个向量夹角的余弦。如果将向量归一化为长度均为 1 的向量，则向量的点积也相同。

两个方向完全相同的向量的余弦相似度为 1，而两个彼此相对的向量的余弦相似度为 - 1。注意，它们的大小并不重要，因为这是在方向上的度量。

缺点：余弦相似度的一个主要缺点是没有考虑向量的大小，而只考虑它们的方向。以推荐系统为例，余弦相似度就没有考虑到不同用户之间评分尺度的差异。

用例：当我们对高维数据向量的大小不关注时，可以使用余弦相似度。对于文本分析，当数据以单词计数表示时，经常使用此度量。例如，当一个单词在一个文档中比另一个单词更频繁出现时，这并不一定意味着文档与该单词更相关。可能是文件长度不均匀或者计数的重要性不太重要。我们最好使用忽略幅度的余弦相似度。

[henryliangt]

汉明距离（Hamming Distance）

汉明距离是两个向量之间不同值的个数。它通常用于比较两个相同长度的二进制字符串。它还可以用于字符串，通过计算不同字符的数量来比较它们之间的相似程度。

缺点：当两个向量长度不相等时，汉明距离使用起来很麻烦。当幅度是重要指标时，建议不要使用此距离指标。

用例：典型的用例包括数据通过计算机网络传输时的错误纠正 / 检测。它可以用来确定二进制字中失真的数目，作为估计误差的一种方法。此外，你还可以使用汉明距离来度量分类变量之间的距离。

[henryliangt]

曼哈顿距离（Manhattan Distance）

曼哈顿距离通常称为出租车距离或城市街区距离，用来计算实值向量之间的距离。想象一下均匀网格棋盘上的物体，如果它们只能移动直角，曼哈顿距离是指两个向量之间的距离，在计算距离时不涉及对角线移动。

缺点：尽管曼哈顿距离在高维数据中似乎可以工作，但它比欧式距离直观性差，尤其是在高维数据中使用时。此外，由于它可能不是最短路径，有可能比欧氏距离给出一个更高的距离值。

用例：当数据集具有离散或二进制属性时，曼哈顿距离似乎工作得很好，因为它考虑了在这些属性的值中实际可以采用的路径。以欧式距离为例，它会在两个向量之间形成一条直线，但实际上这是不可能的。

[henryliangt]

切比雪夫距离（Chebyshev Distance）

切比雪夫距离定义为两个向量在任意坐标维度上的最大差值。换句话说，它就是沿着一个轴的最大距离。切比雪夫距离通常被称为棋盘距离，因为国际象棋的国王从一个方格到另一个方格的最小步数等于切比雪夫距离。

缺点：切比雪夫距离通常用于特定的用例，这使得它很难像欧氏距离或余弦相似度那样作为通用的距离度量。因此，在确定适合用例时才使用它。

用例：切比雪夫距离用于提取从一个方块移动到另一个方块所需的最小移动次数。此外，在允许无限制八向移动的游戏中，这可能是有用的方法。在实践中，切比雪夫距离经常用于仓库物流，因为它非常类似于起重机移动一个物体的时间。

[henryliangt]

闵氏距离（Minkowski）

闵氏距离比大多数距离度量更复杂。它是在范数向量空间（n 维实数空间）中使用的度量，这意味着它可以在一个空间中使用，在这个空间中，距离可以用一个有长度的向量来表示。

最有趣的一点是，我们可以使用参数 p 来操纵距离度量，使其与其他度量非常相似。常见的 p 值有：

p=1：曼哈顿距离 p=2：欧氏距离 p=∞：切比雪夫距离 缺点：闵氏距离与它们所代表的距离度量有相同的缺点，因此，对哈顿距离、欧几里得距离和切比雪夫距离等度量标准有个好的理解非常重要。此外，参数 p 的使用可能很麻烦，因为根据用例，查找正确的 p 值在计算上效率低。

用例：p 的积极一面是可迭代，并找到最适合用例的距离度量。它允许在距离度量上有很大的灵活性，如果你非常熟悉 p 和许多距离度量，将会获益多多。

[henryliangt]

雅卡尔指数（Jaccard Index）

雅卡尔指数（交并比）是用于比较样本集相似性与多样性的统计量。雅卡尔系数能够量度有限样本集合的相似度，其定义为两个集合交集大小与并集大小之间的比例。

例如，如果两个集合有 1 个共同的实体，而有 5 个不同的实体，那么雅卡尔指数为 1/5 = 0.2。要计算雅卡尔距离，我们只需从 1 中减去雅卡尔指数：

缺点：雅卡尔指数的一个主要缺点是它受数据大小的影响很大。大数据集对指数有很大影响，因为它可以显著增加并集，同时保持交集相似。

用例：雅卡尔指数通常用于使用二进制或二进制数据的应用程序中。当你有一个深度学习模型来预测图像分割时，比如一辆汽车，雅卡尔指数可以用来计算给定真实标签的预测分割的准确度。

类似地，它可以用于文本相似性分析，以测量文档之间有多少词语重叠。因此，它可以用来比较模式集合。

[henryliangt]

半正矢（Haversine）

半正矢距离是指球面上的两点在给定经纬度条件下的距离。它与欧几里得距离非常相似，因为它可以计算两点之间的最短连线。主要区别在于半正矢距离不可能有直线，因为这里的假设是两个点都在一个球面上。

缺点：这种距离测量的一个缺点是，假定这些点位于一个球体上。实际上，这种情况很少出现，例如，地球不是完美的圆形，在某些情况下可能使计算变得困难。相反，如果假定是椭球，使用 Vincenty 距离比较好。

用例：半正矢距离通常用于导航。例如，你可以使用它来计算两个国家之间的飞行距离。请注意，如果距离本身不那么大，则不太适合。

[henryliangt]

Vincenty

[henryliangt]

Sørensen-Dice 系数

Sørensen-Dice 系数与雅卡尔指数非常相似，都是度量样本集的相似性和多样性。尽管它们的计算方法相似，但是 Sørensen-Dice 系数更直观一些，因为它可以被视为两个集合之间重叠的百分比，这个值在 0 到 1 之间：

缺点：正如雅卡尔指数，Sørensen-Dice 系数也夸大了很少或没有真值的集合的重要性，因此，它可以控制多集合的平均得分，还可以控制多组平均得分并按相关集合的大小成反比地加权每个项目，而不是平等对待它们。

用例：用例与雅卡尔指数相似，它通常用于图像分割任务或文本相似性分析。

[henryliangt]

Canberra distance 曼哈顿距离的加权版本。 1966年被提出，1977年被G. N. Lance和 W. T. Williams重新提出。是 L₁ (Manhattan) distance的加权版本，Canberra distance已被用作比较排名列表和计算机安全中的入侵检测的测量。 通常堪培拉距离对于接近于0（大于等于0）的值的变化非常敏感。与马氏距离一样，堪培拉距离对数据的量纲不敏感。不过堪培拉距离假定变量之间相互独立，没有考虑变量之间的相关性。

import numpy as np
p = np.array([11, 0, 7, 8, 0])
q = np.array([24, 37, 5, 18, 1])
n = len(p)
distance = 0
for i in range(n):
    if p[i] == 0 and q[i] == 0:
        distance += 0
    else:
        distance += abs(p[i] - q[i]) / (abs(p[i]) + abs(q[i]))
print(distance)

[henryliangt]

Hausdorff distance

We are given two point sets A = {a1, a2, . . . , an} and B = {b1, b2, . . . , bm} in E 2 . The one-sided Hausdorff distance from A to B is defined as: ˜δH(A, B) = max a∈A min b∈B ka − bk (1) The bidirectional Hausdorff distance between A and B is then defined as: δH(A, B) = max(˜δH(A, B), ˜δH(B, A)) (2)

给定两个点集合A{ a0, a1, … }和B{ b0, b1, b2, …}

取A集合中的一点a0，计算a0到B集合中所有点的距离，保留最短的距离d0 遍历A集合中所有点，图中一共两点a0和a1，计算出d0和d1 比较所有的距离{ d0, d1 }，选出最长的距离d1 这个最长的距离就是h，它是A→B的单向豪斯多夫距离，记为h( A, B ) 对于A集合中任意一点a，我们可以确定，以点a为圆心，h为半径的圆内部必有B集合中的 交换A集合和B集合的角色，计算B→A的单向豪斯多夫距离h( B, A )，选出h( A, B )和h( B, A )中最长的距离，就是A,B集合的双向豪斯多夫距离