机器学习的常见距离度量方法

人工智能的算法中经常需要比较样本空间内两个样本数据的相似程度，比如前面小节介绍的k-NN算法中，使用到了欧氏距离，它属于闵可夫斯基距离（Minkowski distance，由H.Minkowski提出）的一种。闵可夫斯基距离是一组距离的定义，它对应着p范数（p norm）。

1.闵可夫斯基距离

设有两个样本数据x，y，每个样本有n个参数（相当于n维空间），则它们的闵可夫斯基距离的定义为

当p=1时，就是绝对值距离，也称为曼哈顿距离（manhattan distance）或街区距离（city block distance），对应着L1-范数，如图4.11（a）所示，从S点到G点的曼哈顿距离为8。街区距离这个名字很形象，假设虚线是街道，那么从S点到G点，无论怎么走，距离都是8，比如折线a和b，长度都是8，所以它也称为出租车距离（taxicab distance）。

当p=2时，就是欧几里得距离（Euclidean distance），简称欧氏距离，对应着L2-范数。在图4.11（a）中，从S点到G点的欧氏距离为，反映的是两点之间的连线长度，如线段c所示。

图4.11　常用的距离示意

当p取为∞时，称为切比雪夫距离（Chebyshev distance），也称为棋盘距离（chessboard distance），对应着L∞范数或一致范数，计算公式为：

在图4.11（a）中，从S点到G点的切比雪夫距离为4。在图4.11（b）中，棋盘上的数字就是该点距离王的距离，无论朝哪个方向，相邻的距离都是一样的。

图4.12中进一步演示了当p取不同值时，距离中心点距离相等的点的轨迹。

图4.12　距离原点相同距离的不同阶的闵可夫斯基距离示意

使用闵可夫斯基距离时需要注意到：样本的不同特征（或称不同维度）具有不同量纲时，直接计算得到的闵可夫斯基距离常常并没有什么实际意义。另外，如果数据有两个维度x和y，且x方向的值远大于y方向的值，那么这个距离公式就会过度放大x维度的作用。为了消除不同维度数据相差太大或具有不同量纲的影响，在计算距离之前，可能还需要对数据进行归一化（normalization）或者标准化（standardization）（也称z-score）处理。本质上，两者都是一种线性变换，对样本数据先压缩再平移。

归一化的目的是使预处理的数据被压缩在一定的范围之内，比如类似概率分布的［0，1］，或类似坐标分布的［-1，1］。所以，对输出结果范围有要求时，一般进行归一化处理。

需要注意的是，归一化不能处理异常值，比如x取值为2.0，1.0，1.5，1.8，2.7，81.0，其中81.0相对其他值而言差别太大，可能是异常值。另外，如果xmax和xmin不稳定，也会使后继使用效果不稳定。在这种情况下，就更适合进行标准化处理，即减去均值，然后除以标准差。

可以看到，经过上述处理后，开始体现数据的统计特性了，数据将变成均值为0，标准差为1的分布，标准化并没有限制值的范围，异常值的影响相对较小。这种方法在假设数据各个维度不相关的情况下利用数据分布的特性计算出不同的距离，所以通常对呈高斯分布的原始数据处理效果较好。当并不知道数据的分布时，使用归一化方法会更合适。比如，如果需要对年龄和收入这两个特征进行预处理，那么年龄比较适合用归一化进行预处理，而收入更适合用标准化进行预处理。

例4.5　设x=［2.0，1.0，1.5，1.8，2.7，81.0］，请写出对它进行归一化和标准化处理的结果。

解　归一化：xmax=81.0，xmin=1.0，由式（4.23）不难算出归一化后的结果为

xnew=［0.0125，0，0.006 25，0.01，0.021 25，1.0］。

标准化：均值为μx=15，标准差为

由式（4.24）得到标准化的结果为

xnew=［-0.440，-0.474，-0.457，-0.447，-0.417，2.236］

在scikit-learn中，归一化使用的函数是Min MaxScaler，标准化使用的函数是StandardScaler，例4.5可以用以下代码实现求解：

闵可夫斯基距离虽然比较直观，但是与数据的分布无关，具有一定的局限性。虽然使用归一化或者标准化可以消除不同维度之间尺度和量纲不同的问题，但是样本不同维度的分布不同也会影响分类，而且如果不同维度之间数据具有相关性，不是独立同分布的，比如身高较高的信息很有可能会带来体重较重的信息，因为两者是有关联的，并且尺度是无关的，就要用到马哈拉诺比斯距离（Mahalanobis distance，由P.C.Mahalanobis提出）了。它可以排除变量之间相关性的干扰。(www.xing528.com)

2.马哈拉诺比斯距离

马哈拉诺比斯距离，简称马氏距离，表示了两个服从同一分布并且协方差矩阵为Σ的随机变量之间的差异程度，反映的是一个点和一个分布之间的距离。它可以看作是对欧氏距离的一种修正，是旋转变换缩放之后的欧式距离。它修正了欧氏距离中各个维度尺度不一致并且相关的问题。

马氏距离可以利用Cholesky矩阵实现由线性相关变量到不相关变量的转换，以此来消除不同维度之间的线性相关性和尺度不同。如果样本点特征矢量（列矢量）之间的协方差矩阵是Σ，且是对称正定的，就满足Cholesky分解的条件，可以通过Cholesky分解为下三角矩阵和上三角矩阵的乘积，即下三角矩阵L和其共轭转置矩阵的乘积

Σ=L LT　（4.25）

如果两个样本数据D1、D2服从同一分布且各维度之间协方差矩阵为Σ，则马氏距离定义为

由式（4.25）可以得到

如果要将每个样本数据转换到马氏距离，则只需要计算其和样本空间的均值的马氏距离即可，这样就消除了不同维度之间的相关性和尺度不同。由式（4.27）可知，只需要对样本数据各个维度的协方差矩阵进行Cholesky分解，求其下三角矩阵的逆再乘以样本数据减去均值的差

z=L-1（X-μ）,μ为均值　（4.28）

对处理之后的数据求欧氏距离，也就得到了样本数据到μ的马氏距离。

图4.13所示为在x，y轴上呈线性分布的某一样本空间的数据，可以看到数据随着x增加，y也有增加的趋势，两者之间是有一定的相关性的，且分布的中心为原点。从图中看，A点相对于B点来说距离原点更近，但直观上感觉B点似乎更属于这个分布中的一点。

图4.13　某样本空间数据分布

如果对数据用式（4.28）进行处理后，用马氏距离来度量，则分布变为了图4.14，此时B点明显距离中心点更近。

图4.14　用马氏距离度量的样本数据分布

在Python中，使用NumPy包实现这个过程比较容易，完整代码请参考\s4_2_4\MahDist.py，主要代码如下，设x和y矩阵是样本两个维度的数据：

通过以上代码就可以将x，y转换为马氏空间的值，再用欧氏距离公式计算，得到的就是马氏距离。如果使用Scipy包，可以直接使用距离类计算闵可夫斯基距离、马氏距离：

另外，需要注意的是，马氏距离要求样本数要大于维度，否则无法求协方差矩阵。另外，马氏距离只对线性空间有效。

3.余弦相似性（cosine similarity）

余弦相似性通过测量两个矢量的夹角的余弦值来度量它们之间的形似性。它关注的是两者之间的角度关系，用来判断它们是否指向相同的方向，而不关心幅度的大小。针对多维空间的两个矢量x和y，它们之间的余弦相似性定义为

取值范围为［-1，+1］，两个矢量之间的夹角越小，表示它们越相似。当两个矢量指向相同方向时，余弦相似性为1；当两个矢量正交时，余弦相似性为0；当两个矢量方向完全相反时，余弦相似性为-1。

相较于用欧氏距离来判断相似性，当研究对象的维度很高时，余弦相似性由于不考虑数值的绝对大小，有时会表现得更稳定。比如某影评网站对3部电影的打分情况，A用户给出的分值为（10，8，9），B用户给出的分值为（4，2，3），C用户给出的分值为（8，10，9），如果根据用户行为对用户进行分类来进一步用于电影推荐，那么用余弦相似性判断，A和B会归为一类人，虽然评分不同，但是他们应该有相似的喜好。如果用欧氏距离来判断，就会将A和C归为具有类似喜好的一类人，这就有点不太合理了。A和C可能在评分尺度上相似，或者说A和C对3部电影都喜欢，而B对这三部都不喜欢，这个时候需要关注数值差异，欧氏距离可能就更合适了。不过为了避免余弦相似性因为对数值的不敏感而带来上述影响，引入了修正的余弦相似性——分别减去该用户的所有评分的均值。

在商品推荐之类的协同过滤算法中，会经常采用这种方法。