2.1.2　度量

机器学习的一个重要应用就是度量（metric）。我们度量个体或群体之间的差异，以此评估个体或群体的相似性，判断其类别。最常见的是将度量应用于聚类和分类方法。对于不同的数据特性，我们抽象出来的假设空间也不一样，所以会采用不同的度量方式。

2.1.2.1　欧几里得距离

欧几里得距离（Euclidean distance），也称欧氏距离，是一种常见的距离定义，指在n维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。欧氏距离对应于L2范数，相当于两点之间的L2范数。在二维和三维空间中，欧氏距离就是两点之间的实际距离：

2.1.2.2　曼哈顿距离

曼哈顿距离（Manhattan distance）或出租车几何，是由19世纪的赫尔曼·闵可夫斯基所提出的，它是一种在几何度量空间中使用的几何学用语，用以标明两个点在标准坐标系上的绝对轴距总和。曼哈顿距离对应于L1范数。

曼哈顿距离的数学表达式为：

如图2-2所示，图中左上角的折线代表两点之间的曼哈顿距离，中间的对角线代表欧氏距离，也就是直线距离，而阶梯状的折线代表等价的曼哈顿距离。

2.1.2.3　闵可夫距离

闵可夫距离（Minkowski distance）又叫作闵可夫斯基距离，是欧氏空间中的一种度量，被看作是欧氏距离的一种推广。欧氏距离、曼哈顿距离、切比雪夫距离都可以看作是闵可夫距离的特殊情况。闵可夫距离不是一种距离，而是一组距离的定义，对应于Lp范数。其数学表达式如下，其中p为参数：

图2-3表示在平面中，p取不同值时平面上的点到原点的闵可夫距离的形状。

2.1.2.4　切比雪夫距离

当p趋于无穷大时，闵可夫距离可以转化成切比雪夫距离（Chebyshev distance）：

切比雪夫距离对应于范数，其定义为其各坐标数值差的绝对值的最大值，也就是某一维度的最大距离。切比雪夫距离是由一致范数（uniform norm）（或称为上确界范数）所衍生的度量，也是超凸度量（injective metric）的一种。

2.1.2.5　马氏距离

讲到马氏距离（Mahalanobis distance），就要先讲解其代数原理：楚列斯基分解。

1．楚列斯基分解（Cholesky Decomposition）

乔累斯基分解是对对称正定矩阵的一种减少计算量的三角分解方法。

定义　设为n阶正定矩阵，则存在一个实的非奇异下三角阵，使

如果限定是正定矩阵，则这种分解是唯一的。上式称为对称正定矩阵的楚列斯基分解，亦称为平方根分解。

2．马氏距离（Mahalanobis distance）

马氏距离实际上是利用楚列斯基分解来消除不同维度之间的相关性和尺度不同性。假设样本点之间的协方差矩阵是，可知其对称正定，为了消除不同维度之间的相关性和尺度差别，只需要对于样本点做如下变换：，变换之后的之间的欧氏距离也就是原样本点的马氏距离（为了方便计算，我们两边取平方）：

我们可以从另一个角度，也就是印度统计学家马哈拉诺比斯（P. C. Mahalanobis）提出马氏距离时采用的角度再看这个问题。很明显，欧氏距离并不会考虑各个特征之间的关系。例如，一个用户所购买的商品数量与商品所带来的收益这两个特征，如果使用欧氏距离来度量用户之间相似度，可以发现这两个特征其实是独立的度量，而且它们的尺度无关，那么使用欧氏距离来度量就会有明显的缺陷，因为用户所购买的商品数量变化的规模要远小于商品收益的变化规模。

如图2-4所示，右侧五角星（1）明显比左侧五角星（2）更趋于在包含原点的簇中。因此，度量右侧五角星（2）时，度量结果应该比左侧五角星（1）更靠近原点（中心点）。

对于一个均值向量为，协方差矩阵为的随机向量，其马氏距离为：

同样，对两个不同的随机向量进行对比，并不需要用到均值，将均值向量变为另一个随机向量d即可：

可以看到，当为单位矩阵时，马氏距离为欧氏距离；当为对角矩阵时，此时马氏距离也叫作标准化欧氏距离（standardized Euclidean distance）。其数学表达式如下：

如果将方差的倒数看成一个权重，此时的标准化欧氏距离就可以看成是一种加权欧氏距离（weighted Euclidean distance）。

马氏距离的变换和PCA（Principal Component Analysis，主成分分析）解的白化处理颇有异曲同工之妙，不同之处在于：就二维空间来看，PCA 是将数据主成分旋转到x轴（正交矩阵的酉变换），然后在尺度上缩放（对角矩阵），实现相同的尺度；而马氏距离的L逆矩阵是一个下三角阵，先在x轴和y轴方向进行缩放，再在y轴方向上进行错切（想象一下把矩形变为平行四边形），总体来说是一个没有旋转的仿射变换。

2.1.2.6　余弦距离

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

夹角余弦的取值范围为[-1,1]。显然，夹角余弦的值越大，表示两个向量之间的夹角越小。

值得注意的是，余弦距离衡量的是空间中两个向量的夹角，因此有一定的适用条件。比如，在文档相似度计算中使用的TF-IDF和计算图片相似性时使用的histogram等很多经典领域，余弦距离就很适用，但如果问题的度量本身不仅跟夹角有关，还跟向量长度、位置、所在象限、密集程度等有关，则应该选用别的度量。

2.1.2.7　皮尔逊相关系数

可以看到，余弦距离受到很多因子的影响，为了解决其中的一个问题——向量的平移不变性，有人提出皮尔逊相关系数（Pearson Correlation Coefficient），简称相关系数：

皮尔逊相关系数具有平移不变性和尺度不变性，同马氏距离一样，可以作用于两个随机变量，计算两个随机变量的相关性。

如果我们展开皮尔逊相关系数的计算公式，用corr(x, y)表示，则有：

可以看到，皮尔逊相关系数与余弦相似度在数据标准化后是等价的，只不过皮尔逊相关系数对一个随机变量使用标准化的方法进行了数据缩放，使其在尺度维度归一化，消除了尺度的影响。

归一化还有其他的方法，比如标准化的方法：

此种标准化实际上是统计学中的z-score规范化，它与归一化的不同之处在于，对数据标准化并不会改变原始数据的相对距离比例，只相当于在向量的每一个维度上进行了缩放。

另外，皮尔逊相关系数与欧氏距离在数据进行标准化后也存在线性关系，有兴趣的读者可以自行推导：

2.1.2.8　杰卡德距离

杰卡德距离（Jaccard distance）用于衡量集合之间的距离。我们先介绍杰卡德相似系数。

1．杰卡德相似系数（Jaccard Similarity Coefficient）

杰卡德相似系数度量的是两个集合的相似度，使用两个集合的交集比这两个集合的并集。

2．杰卡德距离（Jaccard distance）

与杰卡德相似系数相反，杰卡德距离用两个集合中不同的元素所占的比例来衡量这两个集合的区分度：

2.1.2.9　序列距离

序列距离并不是指某种特定的距离度量方式，所有与序列有关的度量统称为序列距离。在不同的应用条件下，存在不同的距离度量方式。这里介绍三个与序列有关的距离：海明距离、编辑距离和DTW距离。

1．海明距离（Hamming distance）

海明距离指对于两个等长字符串，从一个字符串变为另一个字符串所需要的最小替换次数。

海明距离的定义比较简单，由于其简单易用，因此应用广泛。例如海明码，一种可以用于信息编码的方式，它将有效信息按照某种规律分成若干组，每组安排一个校验位。这样，校验位就可以用于检验信息的完整性。

除了海明距离，匹配系数也可以用来度量字符串的相似度。其定义如下：

2．编辑距离（Edit Distance，Levenshtein Distance）

有一个经典的动态规划算法问题，也就是字符串的编辑距离。字符串的编辑距离是指两个字符串之间，通过限定的操作（替换、插入、删除），由一个字符串转换成另一个字符串所需要的最少编辑次数。

设和表示两个子序列，表示和的编辑距离。它们的递推关系如下：

算法时间复杂度为n和m分别是序列的长度。

更复杂的编辑距离还有带权值的编辑距离，它可以对每个编辑操作赋予不同的权值，目标是求最小权值的转换操作序列。

3．DTW（Dynamic Time Warp）距离

DTW距离是当序列信号在时间或者速度上不匹配时衡量相似度的一种方法。

举个例子，两份原本一样的声音样本A和B的内容都是“你好”，A在时间上发生了扭曲，“你”这个音延长了几秒。最后的A为“你……好”，B为“你好”。DTW正是这样一种可以用来匹配A、B之间最短距离的算法。

与编辑距离类似，DTW距离限定要保持信号的先后顺序，对时间信号进行“膨胀”或“收缩”，找到最优匹配。它解决的也是动态规划问题。

设和表示两个子序列，表示它们的DTW距离，其递推关系如下：

2.1.2.10　KL散度

KL散度（Kullback-Leibler Divergence），又叫相对熵（Relative Entropy），适用于衡量概率分布之间的距离，可以应用于统计学中检测两组样本分布之间的距离。同样的检测方法还有卡方检验（Chi-Square）。统计学习中的多项分布、机器学习中的Softmax回归等问题，最终都是在计算概率分布，对于这些问题都可以应用KL散度。KL散度的定义如下：

我们知道，信息熵用于度量信息量的大小，，而KL散度相当于两个分布对应的随机变量的相对信息量。

对于Softmax回归或者逻辑回归，我们的优化目标就是尽量减小样本总体的KL散度之和（目标函数）。