机器学习算法原理、实现与实践 —— 距离的度量

声明：本篇文章内容大部分转载于July于CSDN的文章：从K近邻算法、距离度量谈到KD树、SIFT+BBF算法，对内容格式与公式进行了重新整理。同时，文章中会有一些对知识点的个人理解和归纳补充，不代表原文章作者的意图。

1. 欧氏距离

欧氏距离是最常见的两点之间或多点之间的距离表示法，又称之为欧几里得度量，它定义于欧几里得空间中，如点 $x = (x_1,\cdots,x_n)$ 和$y = (y_2,\cdots,y_n)$之间的距离为：

$$d(x,y) = \sqrt{(x_1 – y_1)^2 + (x_2-y_2)^2 + \cdots+(x_n-y_n)^2} = \sqrt{\sum_{i=1}^n(x_i-y_i)^2}$$

1）二维平面上两点$a(x_1,y_1)$与$b(x_2,y_2)$间的欧氏距离： $$d = \sqrt{(x_1 – x_2)^2 + (y_1 – y_2)^2}$$

2）三维空间两点$a(x_1,y_1,z_1)$与$b(x_2,y_2,z_2)$间的欧氏距离： $$d = \sqrt{(x_1 – x_2)^2 + (y_1 – y_2)^2 + (z_1 – z_2)^2}$$

3）两个$n$维向量$a(x_{11},x_{12},\cdots,x_{1n})$与 $b(x_{21},x_{22},\cdots,x_{2n})$间的欧氏距离： $$d = \sqrt{\sum_{k=1}^n(x_{1k} – x_{2k})^2}$$ 也可以用表示成向量运算的形式： $$d = \sqrt{(a-b)(a-b)^T}$$

$n$维平面上两点欧式距离，代码可以如下编写：

//unixfy：计算欧氏距离

double euclideanDistance(const vector<double>& v1, const vector<double>& v2)

{

    assert(v1.size() == v2.size());

    double ret = 0.0;

    for (vector<double>::size_type i = ; i != v1.size(); ++i)

    {

        ret += (v1[i] - v2[i]) * (v1[i] - v2[i]);

    }

    return sqrt(ret);

}

2. 曼哈顿距离

我们可以定义曼哈顿距离的正式意义为$L_1$-距离或城市区块距离，也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。

例如在平面上，坐标$(x_1,y_1)$的点$P_1$与坐标$(x_2,y_2)$的点$P_2$的曼哈顿距离为：

$$D(P_1,P_2) = |x_1-x_2| + |y_1 – y_2|$$

要注意的是，曼哈顿距离依赖座标系统的转度，而非系统在座标轴上的平移或映射。

通俗来讲，想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。而实际驾驶距离就是这个“曼哈顿距离”，此即曼哈顿距离名称的来源，同时，曼哈顿距离也称为城市街区距离(City Block distance)。

1）二维平面两点$a(x_1,y_1)$与$b(x_2,y_2)$间的曼哈顿距离$$d(a,b) = |x_1 – x_2| + |y_1- y_2|$$

2）两个$n$维向量$a(x_{11},x_{12},\cdots,x_{1n})$与$b(x_{21},x_{22},\cdots,x_{2n})$间的曼哈顿距离$$d(a,b) = \sum_{k=1}^n|x_{1k} – x_{2k}|$$

3. 切比雪夫距离

若二个向量或二个点$p,q$，其座标分别为$(p_1,p_2,\cdots,p_i,\cdots)$及$(q_1,q_2,\cdots,q_i,\cdots)$，则两者之间的切比雪夫距离定义如下：

$$D_{Chebyshev}(p,q) = \max_{i}(|p_i – q_i|)$$

这也等于以下$L_p$度量的极值：$\lim_{k\to \infty}\left(\sum_{i=1}^n|p_i – q_i|^k\right)^{1/k}$，因此切比雪夫距离也称为$L_{\infty}$度量。以数学的观点来看，切比雪夫距离是由一致范数（或称为上确界范数）所衍生的度量，也是超凸度量的一种。

1）在平面几何中，若二点$p$及$q$的直角坐标系坐标为$(x_1,y_1)$及$(x_2,y_2)$，则切比雪夫距离为：$D_{Chess} = \max(|x_2 – x_1|,|y_2-y_1|)$。

玩过国际象棋的朋友或许知道，国王走一步能够移动到相邻的8个方格中的任意一个。那么国王从格子$(x_1,y_1)$走到格子$(x_2,y_2)$最少需要多少步？。你会发现最少步数总是$\max(|x_2 – x_1|,|y_2-y_1|)$步。

2）二维平面上两点$a(x_1,y_1)$与$b(x_2,y_2)$间的切比雪夫距离$$d(a,b) = \max(|x_1-x_2|,|y_1 – y_2|)$$

3）两个$n$维向量$a(x_{11},x_{12},\cdots,x_{1n})$与 $b(x_{21},x_{22},\cdots,x_{2n})$间的切比雪夫距离$$d(a,b) = \max_{i}(|x_{1i} – x_{2i}|)$$这个公式的另一种等价形式是$$d(a,b) = \lim_{k\to\infty}\left(\sum_{i=1}^n|x_{1i} – x_{2i}|^k\right)^{1/k}$$

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

闵氏距离不是一种距离，而是一组距离的定义。

两个$n$维向量$a(x_{11},x_{12},\cdots,x_{1n})$与 $b(x_{21},x_{22},\cdots,x_{2n})$间的闵可夫斯基距离定义为：

$$d(a,b) =\sqrt[p]{\sum_{k=1}^n|x_{1k} – x_{2k}|^p} $$

其中$p$是一个变参数。

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

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

当$p \to \infty$时，就是切比雪夫距离；

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

5. 标准化欧氏距离 (Standardized Euclidean distance )

标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进方案。标准欧氏距离的思路：既然数据各维分量的分布不一样，那先将各个分量都“标准化”到均值、方差相等。

假设样本集$X$的数学期望或均值为$\mu$，标准差为$\sigma$，那么$X$的“标准化变量”$\hat{X}$表示为：$(X-\mu)/\sigma$，而且标准化变量的数学期望为0，方差为1。

即，样本集的标准化过程(standardization)用公式描述就是：

$$\hat{X} = \frac{X - \mu}{\sigma}$$

经过简单的推导就可以得到两个$n$维向量$a(x_{11},x_{12},\cdots,x_{1n})$与 $b(x_{21},x_{22},\cdots,x_{2n})$间的标准化欧氏距离的公式：

$$d(a,b) = \sqrt{\sum_{k=1}^n\left(\frac{x_{1k} – x_{2k}}{\sigma_k}\right)^2}$$

如果将方差的倒数看成是一个权重，这个公式可以看成是一种加权欧氏距离(Weighted Euclidean distance)。

6. 马氏距离(Mahalanobis Distance)

有$M$个样本向量$X_1 \sim X_M$，协方差矩阵记为$S$，均值记为向量$\mu$，则其中样本向量$X$到$\mu$的马氏距离表示为：

$$D(X) = \sqrt{(X-\mu)^TS^{-1}(X-\mu)}$$

而其中向量$X_i$与$X_j$之间的马氏距离定义为：

$$D(X_i,X_j) = \sqrt{(X_i – X_j)^TS^{-1}(X_i – X_j)}$$

若协方差矩阵是单位矩阵（各个样本向量之间独立同分布）,则公式就成了：

$$D(X_i,X_j) = \sqrt{(X_i – X_j)^T(X_i – X_j)}$$

也就是欧氏距离了。

若协方差矩阵是对角矩阵，公式变成了标准化欧氏距离。
马氏距离的优缺点：量纲无关，排除变量之间的相关性的干扰。

7. 巴氏距离（Bhattacharyya Distance）

在统计中，Bhattacharyya距离测量两个离散或连续概率分布的相似性。它与衡量两个统计样品或种群之间的重叠量的Bhattacharyya系数密切相关。Bhattacharyya距离和Bhattacharyya系数以20世纪30年代曾在印度统计研究所工作的一个统计学家A. Bhattacharya命名。同时，Bhattacharyya系数可以被用来确定两个样本被认为相对接近的，它是用来测量中的类分类的可分离性。

对于离散概率分布$p$和$q$在同一域$X$，它被定义为：

$$D_B(p,q) = –ln(BC(p,q))$$

其中：

$$BC(p,q) = \sum_{x\in X}\sqrt{p(x)q(x)}$$

是Bhattacharyya系数。

对于连续概率分布，Bhattacharyya系数被定义为：

$$BC(p,q) = \int\sqrt{p(x)q(x)}dx$$

Bhattacharyya系数是两个统计样本之间的重叠量的近似测量，可以被用于确定被考虑的两个样本的相对接近。

计算Bhattacharyya系数涉及集成的基本形式的两个样本的重叠的时间间隔的值的两个样本被分裂成一个选定的分区数，并且在每个分区中的每个样品的成员的数量，在下面的公式中使用

$$\text{Bhattacharyya} = \sum_{i=1}^n\sqrt{(\sum a_i \cdot \sum b_i)}$$

考虑样品$a$和$b$ ，$n$是的分区数，$\sum a_i$是指样品$a$中落在分区$i$内的个数，$\sum b_i$有类似的定义。

8. 汉明距离(Hamming distance)，

两个等长字符串$s_1$与$s_2$之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。

例如字符串“1111”与“1001”之间的汉明距离为2。

应用：信息编码（为了增强容错性，应使得编码间的最小汉明距离尽可能大）。

9. 夹角余弦(Cosine)

几何中夹角余弦可用来衡量两个向量方向的差异，机器学习中借用这一概念来衡量样本向量之间的差异。

(1)在二维空间中向量$A(x_1,y_1)$与向量$B(x_2,y_2)$的夹角余弦公式：

$$cos\theta = \frac{x_1x_2+ y_1y_2}{\sqrt{x_1^2+y_1^2}\sqrt{x_2^2+y_2^2}}$$

(2) 两个$n$维向量$a(x_{11},x_{12},\cdots,x_{1n})$与 $b(x_{21},x_{22},\cdots,x_{2n})$的夹角余弦

$$cos(\theta) = \frac{a\cdot b}{|a||b|}$$

类似的，对于两个n维样本点$a(x_{11},x_{12},\cdots,x_{1n})$与 $b(x_{21},x_{22},\cdots,x_{2n})$，可以使用类似于夹角余弦的概念来衡量它们间的相似程度，即：

$$cos(\theta) = \frac{\sum_{k=1}^nx_{1k}x_{2k}}{\sqrt{\sum_{k=1}^nx_{1k}^2}\sqrt{\sum_{k=1}^nx_{2k}^2}}$$

夹角余弦取值范围为[-1,1]。夹角余弦越大表示两个向量的夹角越小，夹角余弦越小表示两向量的夹角越大。当两个向量的方向重合时夹角余弦取最大值1，当两个向量的方向完全相反夹角余弦取最小值-1。

10. 杰卡德相似系数(Jaccard similarity coefficient)

10.1 杰卡德相似系数

两个集合$A$和$B$的交集元素在$A,B$的并集中所占的比例，称为两个集合的杰卡德相似系数，用符号$J(A,B)$表示。

$$J(A,B) = \frac{|A\cap B|}{|A\cup B|}$$

杰卡德相似系数是衡量两个集合的相似度一种指标。

10.2 杰卡德距离

与杰卡德相似系数相反的概念是杰卡德距离(Jaccard distance)。

杰卡德距离可用如下公式表示：

ML 07、机器学习中的距离度量

杰卡德距离用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度。

10.3 杰卡德相似系数与杰卡德距离的应用

可将杰卡德相似系数用在衡量样本的相似度上。

举例：样本A与样本B是两个n维向量，而且所有维度的取值都是0或1，例如：A(0111)和B(1011)。我们将样本看成是一个集合，1表示集合包含该元素，0表示集合不包含该元素。

M11 ：样本A与B都是1的维度的个数

M01：样本A是0，样本B是1的维度的个数

M10：样本A是1，样本B是0 的维度的个数

M00：样本A与B都是0的维度的个数

依据上文给的杰卡德相似系数及杰卡德距离的相关定义，样本A与B的杰卡德相似系数J可以表示为：

ML 07、机器学习中的距离度量

这里M11+M01+M10可理解为A与B的并集的元素个数，而M11是A与B的交集的元素个数。而样本A与B的杰卡德距离表示为J'：

ML 07、机器学习中的距离度量

11.皮尔逊系数(Pearson Correlation Coefficient)

在具体阐述皮尔逊相关系数之前，有必要解释下什么是相关系数 ( Correlation coefficient )与相关距离(Correlation distance)。

相关系数 ( Correlation coefficient )的定义是：

ML 07、机器学习中的距离度量

(其中，E为数学期望或均值，D为方差，D开根号为标准差，E{ [X-E(X)] [Y-E(Y)]}称为随机变量X与Y的协方差，记为Cov(X,Y)，即Cov(X,Y) = E{ [X-E(X)] [Y-E(Y)]}，而两个变量之间的协方差和标准差的商则称为随机变量X与Y的相关系数，记为 ML 07、机器学习中的距离度量 )