在数据挖掘中，我们经常需要计算样本之间的相似度(Similarity ),我们通常的做法是计算样本之间的距离,本文对距离计算方法做以下总结。

距离计算方法

 

1.欧式距离EuclideanDistance

欧式距离：也称欧几里得距离，在一个N维度的空间里，求两个点的距离，这个距离肯定是一个大于等于零的数字，那么这个距离需要用两个点在各自维度上的坐标相减，平方后加和再开方。

 

(1)二维平面上两点a(x1,y1)，b(x2,y2)之间的欧式距离公式：

 

(2) n维空间上两点a(x1,x2……..xn)，b(y1,y2……..yn)的欧式距离公式：

 

2. 曼哈顿距离(ManhattanDistance)

 

曼哈顿距离也叫”曼哈顿街区距离”。想象你在曼哈顿街道上，从一个十字路口开车到另一个十字路口，驾驶距离就是这个“曼哈顿距离”。

(1)二维平面上两点a(x1,y1)，b(x2,y2)之间的曼哈顿距离公式：

(2) n维空间上两点a(x1,x2……..xn)，b(y1,y2……..yn)的曼哈顿距离公式：

 

3. 夹角余弦

也叫余弦相似度，是用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小的度量。如果两个向量的方向一致，即夹角接近零，那么这两个向量就越相近。要确定两个向量方向是否一致，要用到余弦定理计算向量的夹角。

 

(1)二维平面上两向量a(x1,y1)，b(x2,y2)之间的夹角余弦公式：

 

 

也可直接通过向量运算：

 

 

(2) n维空间上两点a(x1,x2……..xn)，b(y1,y2……..yn)的夹角余弦公式：

4.切比雪夫距离（Chebyshevdistance）

国际象棋中，国王可以直行、横行、斜行。国王走一步，可以移动到相邻的8个方格的任意一个。国王从格子（X1,Y1） 到格子（X2,Y2）最少需要多少步？这个距离就是切比雪夫距离。

切比雪夫距离公式简单理解为就是各坐标数值差的最大值，在2维空间中的计算公式为：D=max( | x2-x1 | , | y2-y1 | ) 。

(1)二维平面上两点a(x1,y1)，b(x2,y2)之间的切比雪夫距离公式：

(2) n维空间上两点a(x1,x2……..xn)，b(y1,y2……..yn)的切比雪夫距离公式：

 

5. 汉明距离(Hamming Distance)

    两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。

  1011101与 1001001 之间的汉明距离是2  　　

  2143896与 2233796 之间的汉明距离是3  　　

  irie与 rise之间的汉明距离是 3

 

• 定义：两个等长字符串s1与s2的汉明距离为：将其中一个变为另外一个所需要作的最小字符替换次数。例如:

• 汉明重量：是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元素个数：对于二进制字符串来说，就是 1 的个数，所以 11101 的汉明重量是 4。因此，如果向量空间中的元素a和b之间的汉明距离等于它们汉明重量的差a-b。

• 应用：汉明重量分析在包括信息论、编码理论、密码学等领域都有应用。比如在信息编码过程中，为了增强容错性，应使得编码间的最小汉明距离尽可能大。但是，如果要比较两个不同长度的字符串，不仅要进行替换，而且要进行插入与删除的运算，在这种场合下，通常使用更加复杂的编辑距离等算法。

• Matlab计算汉明距离（Matlab中2个向量之间的汉明距离的定义为2个向量不同的分量所占的百分比）：

6. 闵可夫斯基距离(Minkowski Distance)

闵氏距离不是一种距离，而是一组距离的定义，是对多个距离度量公式的概括性的表述。

• 闵氏距离定义：
• 两个n维变量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的闵可夫斯基距离定义为：

其中p是一个变参数：

当p=1时，就是曼哈顿距离；

当p=2时，就是欧氏距离；

当p→∞时，就是切比雪夫距离。

因此，根据变参数的不同，闵氏距离可以表示某一类/种的距离。

• 闵氏距离，包括曼哈顿距离、欧氏距离和切比雪夫距离都存在明显的缺点。
• e.g. 二维样本(身高[单位:cm],体重[单位:kg]),现有三个样本：a(180,50)，b(190,50)，c(180,60)。那么a与b的闵氏距离（无论是曼哈顿距离、欧氏距离或切比雪夫距离）等于a与c的闵氏距离。但实际上身高的10cm并不能和体重的10kg划等号。
• 闵氏距离的缺点：
• (1)将各个分量的量纲(scale)，也就是“单位”相同的看待了;

• (2)未考虑各个分量的分布（期望，方差等）可能是不同的。

• Matlab计算闵氏距离（以p=2的欧氏距离为例）：

7. 马氏距离(Mahalanobis Distance)

 马氏距离的引出：

上图有两个正态分布的总体，它们的均值分别为a和b，但方差不一样，则图中的A点离哪个总体更近？或者说A有更大的概率属于谁？显然，A离左边的更近，A属于左边总体的概率更大，尽管A与a的欧式距离远一些。这就是马氏距离的直观解释。

• 概念：马氏距离是基于样本分布的一种距离。物理意义就是在规范化的主成分空间中的欧氏距离。所谓规范化的主成分空间就是利用主成分分析对一些数据进行主成分分解。再对所有主成分分解轴做归一化，形成新的坐标轴。由这些坐标轴张成的空间就是规范化的主成分空间。

• 定义：有M个样本向量X1~Xm，协方差矩阵记为S，均值记为向量μ，则其中样本向量X到μ的马氏距离表示为：

向量Xi与Xj之间的马氏距离定义为：

若协方差矩阵是单位矩阵（各个样本向量之间独立同分布），则Xi与Xj之间的马氏距离等于他们的欧氏距离：

若协方差矩阵是对角矩阵，则就是标准化欧氏距离。

• 欧式距离&马氏距离：

• 马氏距离的特点：
• 量纲无关，排除变量之间的相关性的干扰；
• 马氏距离的计算是建立在总体样本的基础上的，如果拿同样的两个样本，放入两个不同的总体中，最后计算得出的两个样本间的马氏距离通常是不相同的，除非这两个总体的协方差矩阵碰巧相同；
• 计算马氏距离过程中，要求总体样本数大于样本的维数，否则得到的总体样本协方差矩阵逆矩阵不存在，这种情况下，用欧式距离计算即可。

• Matlab计算马氏距离：