如何判断两个集合相等

判断两个集合是否相等 就看两个集合中包含的元素是否完全相同
｛x│x=2n+1,n∈Z｝ z是整数 所以这个集合表示奇数
｛x│x=2n-3,n∈Z｝ z是整数 这个集合表示的也是奇数
所以这两个集合相等
｛x│x=2n+1,n∈Z｝=｛x│x=2n-3,n∈Z｝

在软件开发和数据分析的过程中，有很多不同的距离的计算方法，如欧氏距离，马氏距离，等等。对这些距离的理解，有助于我们更好的建立模型，规划数据平台的存储和索引功能。网上对这些距离概念的介绍已经很多，本文的主要目的，是对这些概念做一个归纳和总结。

首先，我们需要对”距离”本身进行一些约束。我们所描述的距离，指的是 度量空间 （Metric space）的距离。良好的测距函数应具备以下特征：

本文对一系列常见的，满足上述原则的距离定义，作以下分类：

闵可夫斯基距离 （明氏距离）适用于多维连续空间中两个点位置的判断。每个空间内的数值必须是连续的。 这一类距离定义包括：欧几里得距离（欧氏距离），曼哈顿距离， 切比雪夫距离 。 而这一族距离的定义，统称为闵可夫斯基距离。定义如下：

连续 n 维空间中两点
之间的明氏距离（闵可夫斯基距离）公式为:

p取1或2时的明氏距离是最为常用的：

欧氏距离是这里面我们最熟悉的类型，以2维空间为例，欧氏距离即两点之间的直线距离。曼哈顿距离就是各坐标差的绝对值的和。而切比雪夫距离则是各坐标上差的绝对值的最大值。

闵氏距离，包括曼哈顿距离、欧氏距离和切比雪夫距离都存在一些缺点：

马哈拉诺比斯距离 （马氏距离）针对上述第1，3个缺点做出了改进。Wiki 描述如下：

如果协方差矩阵为单位矩阵，马哈拉诺比斯距离就简化为欧氏距离。

向量和向量之间的相似度，包含了两层概念：角度的相似度，和大小的相似度。常见的向量距离计算方法是 余弦距离 （余弦相似度）。

两个向量 A 和 B 之间的余弦相似度定义如下：

对上述公式直观的解释，即把比较对象各个方向上的长度作为分母，各个方向分量的乘积和作为分子，这样可以得到两者的同一方向的分量“相同的程度”。 的值，当 为0时为1，表示它们的指向是完全相同的，当 为 时为-1，意味着两个向量指向的方向正好相反。

余弦距离常被用于文本相似度的比较，如 TF-IDF 权重的比较中。

这类的距离，度量的是 m 维离散，无序空间中两个变量之间的差异。两个变量之间，只有距离的大小，没有绝对值大小的区别。这里的变量的实际形式，可以是一组标签，一个字符串，等等。这类距离中比较常见的有：

1 编辑距离 ：编辑距离是一组定义的集合，指的是给定 2 个字符串 a, b，将 a 转换为 b 的最少 *** 作次数。

通常我们所说的编辑距离，指的是 莱文斯坦距离 ，字符 *** 作只允许如下 3 种：

对 编辑距离的计算 需要使用动态规划法，时间复杂度为 。

另外， Hamming distance 海明/汉明距离 也是编辑距离的一种，但必须作用在等长字符串上。 典型的应用，有判断图像的相似度，先将图像变为相同尺寸的黑白图再计算。

2 Jaccard 距离 ：判断两个集合的相似度。Jaccard 相似度和 Jaccard 距离的 计算方法 如下：

Jaccard 距离很容易转化为两个等长二进制字符串的判断，任意位上的1表示拥有该 item，0表示不具备该 item。计算 （不一样的 bit 数)/(总 bit 数)% 即得到 Jaccard 距离。

这类距离的索引，是软件实现的噩梦，而噩梦的名称，就叫做 维数灾难 。常规的树状索引结构，只能适用于有序数据，目前并没有一种有效的索引结构能够实现足够高效的集合距离的查找（我没有详细查过相关论文，但我猜测理论上也不会存在这样的索引结构）。当然，办法还是有的。比较常见的方案是 BK树 。然而对于特别大的数据集来说，BK树的剪枝效果远远谈不上理想。在实际的应用中，如 simhash 距离的查找中，只能采用一些比较 tricky 的方法来优化，并且带有诸多限制。

本文主要归纳了各种距离定义的共性和适用范围。基于数学的角度，分类可能并不严谨，也不够形式化，但我希望它能为相关软件系统的设计提供一些参考。后续我会再总结一下，针对上述各种类型的距离，我们是如何实现计算和索引功能的。

本文除了文中自带的链接外，应该至少还参考了下列资料：

---