编辑距离算法流程图（一图看遍9种距离度量）
编辑距离算法流程图（一图看遍9种距离度量）1、Euclidean Distance注意：对于大多数距离度量，很长的详细的文件可以并且已经写在它们的用例、优点和缺点上。我会尽我所能去弥补，但可能会达不到！因此，本文是这些措施的总体概述。但是，如果你的数据是高维的呢?那么欧几里得距离还有效吗?或者，如果你的数据包含地理空间信息呢?也许 haversine 距离是更好的选择!知道何时使用哪种距离度量可以帮助您从一个糟糕的分类器变成一个精确的模型。在本文中，我们将介绍许多距离度量方法，并探讨如何以及何时最好地使用它们。最重要的是，我将讨论它们的缺点，以便您能够意识到何时应该避开某些措施。
距离度量在CV 、NLP以及数据分析等领域都有众多的应用。最常见的距离度量有欧式距离和余弦距离，本文将会分享九种距离，分析其优缺点以及相应的应用常见，如果对你有所帮助，在看完之后，可以分享给你朋友圈的好兄弟，好姐妹们，共同成长进步！
有图有真相
许多算法，无论是监督或非监督，都使用距离度量。这些度量，如欧几里得距离或余弦相似度，经常可以在k-NN、UMAP、HDBSCAN等算法中找到。
理解距离度量比你可能比你想象中更加重要。以k-NN为例，这是一种经常用于监督学习的技术。作为默认值，它通常使用欧几里得距离。它本身就是一个很大的距离。
但是，如果你的数据是高维的呢?那么欧几里得距离还有效吗?或者，如果你的数据包含地理空间信息呢?也许 haversine 距离是更好的选择!
知道何时使用哪种距离度量可以帮助您从一个糟糕的分类器变成一个精确的模型。
在本文中，我们将介绍许多距离度量方法，并探讨如何以及何时最好地使用它们。最重要的是，我将讨论它们的缺点，以便您能够意识到何时应该避开某些措施。
注意：对于大多数距离度量，很长的详细的文件可以并且已经写在它们的用例、优点和缺点上。我会尽我所能去弥补，但可能会达不到！因此，本文是这些措施的总体概述。
1、Euclidean Distance
我们从最常见的距离度量开始，即欧几里得距离。它是一种距离度量，最好解释为连接两点的线段的长度。
这个公式相当简单，因为距离是从这些点的笛卡尔坐标用勾股定理计算出来的。
尽管欧几里德距离是一种常见的距离度量，但它不是尺度不变的，这意味着计算的距离可能是倾斜的，这取决于特征的单位。通常，在使用这个距离度量之前，需要对数据进行标准化（normalize）。
此外，随着数据维度的增加，欧几里得距离就变得不那么有用了。这与维数的"诅咒"有关，它与高维空间并不像我们直观地期望的那样，在2维或3维空间中发挥作用的概念有关。想要一个好的总结，请看这篇文章。
https://stats.stackexchange.com/questions/99171/why-is-euclidean-distance-not-a-good-metric-in-high-dimensions
用例欧几里得距离适用于低维数据，矢量的大小很重要，需要测量。如果在低维数据上使用欧几里得距离，像kNN和HDBSCAN这样的方法会显示出很好的开箱即用结果。
尽管许多其他的测量方法已经被开发出来，用于解决欧几里得距离的缺点，它仍然是最常用的距离方法之一，且有充分的理由。它使用起来非常直观，实现起来非常简单，并且在许多用例中都显示了很好的效果。
2、Cosine Similarity
余弦相似度常用来抵消高维欧几里得距离问题。余弦相似度就是两个向量夹角的余弦。如果它们的长度都是1，它也有相同的内积。
两个方向完全相同的向量的余弦相似性为1，而两个完全相反的向量的相似性为-1。注意，它们的大小并不重要，因为这是方向的量度。
余弦相似度的一个主要缺点是没有考虑向量的大小，而只考虑它们的方向。在实践中，这意味着没有充分考虑值（value）的差异。以一个推荐系统为例，余弦相似度没有考虑到不同用户之间评分尺度的差异。
用例当我们有高维数据和向量的大小不重要时，我们经常使用余弦相似度。对于文本分析，当数据以单词计数表示时，经常使用此度量。例如，当一个单词在一个文档中出现的频率高于另一个文档时，这并不一定意味着一个文档与这个单词的相关性更高。可能出现的情况是，文档的长度不均匀，计数的大小不那么重要。然后，我们最好使用不考虑大小的余弦相似度
3、Hamming Distance
汉明距离是两个向量之间不同值的个数。它通常用于比较两个相同长度的二进制字符串。它还可以用于字符串，通过计算不同字符的数量来比较它们之间的相似程度。
缺点如你所料，当两个向量的长度不相等时，很难使用汉明距离。为了了解哪些位置不匹配，您可能希望比较相同长度的向量。
此外，只要它们不同或相等，它就不考虑实际值。因此，当大小是一个重要的度量时，不建议使用这个距离度量。
用例典型的用例包括数据通过计算机网络传输时的错误纠正/检测。它可以用来确定二进制字中distorted bit的数目，作为估计误差的一种方法。
此外，还可以使用汉明距离来度量分类变量之间的距离
4、Manhattan Distance
曼哈顿距离，通常称为出租车距离或城市街区距离（ Taxicab distance or City Block distance），计算实值向量之间的距离。想象描述均匀网格(如棋盘)上物体的向量。曼哈顿距离是指两个矢量之间的距离，如果它们只能移动直角。在计算距离时不涉及对角线移动。
尽管曼哈顿距离在高维数据中似乎可以工作，但它比欧几里得距离更不直观，尤其是在高维数据中使用时。
此外，由于它不是可能的最短路径，它比欧几里得距离更有可能给出一个更高的距离值。这并不一定会带来问题，但这是你应该考虑的。
用例当数据集具有离散和/或二进制属性时，Manhattan似乎工作得很好，因为它考虑了在这些属性的值中实际可以采用的路径。以欧几里得距离为例，它会在两个向量之间形成一条直线，但实际上这是不可能的。
5、Chebyshev Distance
切比雪夫距离定义为两个向量在任意坐标维度上的最大差值。换句话说，它就是沿着一个轴的最大距离。由于其本质，它通常被称为棋盘距离，因为国王从一个方格到另一个方格的最小步数等于切比雪夫距离。
切比雪夫通常用于非常特定的用例，这使得它很难用作通用的距离度量，如欧氏距离或余弦相似度。因此，建议只在绝对确定它适合你的用例时才使用它。
用例如前所述，切比雪夫距离可用于提取行走从一个方块到另一个方块所需的最小步数。此外，在允许无限制的8向移动的游戏中，这也是一种有用的措施。
在实践中，切比雪夫距离经常用于仓库物流，因为它非常类似于起重机移动一个物体的时间。
6、Minkowski
闵可夫斯基距离比大多数测量都要复杂一些。它是一个在赋范向量空间(n维实空间)中使用的度量，这意味着它可以在一个空间中使用，在这个空间中，距离可以表示为一个有长度的向量。
该措施有三个要求:
- 0向量 —— 0向量的长度是0，而其他向量的长度都是正的。例如，如果我们从一个地方旅行到另一个地方，那么这个距离总是正的。然而，如果我们从一个地方到它自己，那么这个距离是零。
- 标量因子——当你用一个正数乘以向量时，它的长度会改变，同时保持方向不变。例如，如果我们在一个方向上移动一段距离，然后加上相同的距离，这个方向不会改变。
- 三角形不等式——两点之间最短的距离是一条直线。
闵可夫斯基距离公式如下:
关于这个距离度量最有趣的是参数p的使用。我们可以使用这个参数来操纵距离度量，使其与其他度量非常相似。
常见的p值有:
- p=1 — Manhattan distance
- p=2 — Euclidean distance
- p=∞ — Chebyshev distance
闵可夫斯基与它们所代表的距离度量具有相同的缺点，因此，良好地理解曼哈顿距离、欧几里得距离和切比雪夫距离等度量标准是非常重要的。
此外，使用参数p实际上可能很麻烦，因为根据你的用例，查找正确的值在计算上可能非常低效。
用例p的好处是可以迭代它，并找到最适合用例的距离度量。它允许你在距离度量上有很大的灵活性，如果你非常熟悉p和许多距离度量，这将是一个巨大的好处。
7、Jaccard Index
Jaccard索引(或联合上的交集)是一个用于计算样本集的相似性和多样性的度量。它是交集的大小除以样本集的并集的大小。
实际上，它是集合之间相似实体的总数除以实体的总数。例如，如果两个集合有一个共同的实体，而总共有5个不同的实体，那么Jaccard索引将是1/5 = 0.2。
为了计算Jaccard距离，我们只需从1中减去Jaccard索引:
Jaccard索引的一个主要缺点是它受数据大小的影响很大。大型数据集可能对索引有很大的影响，因为它可以显著增加并集，同时保持交集相似。
用例Jaccard索引经常用于使用二进制或二进制化数据的应用程序中。当你有一个深度学习模型来预测一幅图像(例如一辆汽车)的片段时，Jaccard索引就可以用来计算给出真实标签的预测片段的准确性。
同样，它也可以用于文本相似度分析，以衡量文档之间的选词重叠程度。因此，它可以用来比较模式集。
8、Haversine
哈弗辛距离是球面上的两点在给定经纬度条件下的距离。它与欧几里得距离非常相似，因为它计算两点之间最短的直线。主要的区别是不可能是直线，因为这里的假设是两点在球面上。
这种距离测量的一个缺点是假定这些点在球面上。在实践中，这种情况很少发生，例如，地球不是完全圆的，这在某些情况下会使计算变得困难。相反，观察文森特距离（Vincenty distance）会很有趣，因为文森特距离是以椭球为前提的。
用例正如您可能已经预料到的，Haversine距离经常用于导航。例如，你可以用它来计算两个国家之间飞行的距离。请注意，如果距离本身已经不那么大，那么它就不太合适了。曲率不会有那么大的影响。
9、Sørensen-Dice Index
Sørensen-Dice指数与Jaccard指数非常相似，它衡量的是样本集的相似性和多样性。虽然它们的计算方法类似，但Sørensen-Dice索引更直观一些，因为它可以被视为两个集合之间重叠的百分比，这个值在0到1之间:
就像Jaccard指数一样，它们都夸大了很少或没有ground truth的集合的重要性。因此，它可以主宰多盘比赛的平均分。它将每一项的权重与相关集合的大小成反比，而不是同等对待它们。
用例用例与Jaccard index相似(如果不相同的话)。你会发现它通常用于图像分割任务或文本相似度分析。
注意:距离测量比这里提到的9个要多得多。如果您正在寻找更有趣的指标，我建议您查看以下指标之一:Mahalanobis、Canberra、Braycurtis和KL-divergence。
