数据挖掘化功大法（8）——相似性和相异性

前面说过了数据矩阵和相异性矩阵，并且对标称属性和二元属性的相异性进行了分析。

下面综合看一下矩阵的相异性和相似性。

相似性和相异性被许多数据挖掘技术所使用，如聚类、最近邻分类、异常检测等。两个对象之间的相似度是这两个对象相似程度的数值度量，通常相似度是非负值，并常常在0(不相似)和1(完全相似)之间取值。两个对象之间的相异度是这两个对象差异程度的数值度量，两个对象越相似，它们的相异度就越低，通常用“距离”作为相异度的同义词。数据对象之间相似性和相异性的度量有很多，如何选择度量方法依赖于对象的数据类型，数据的量值是否重要，数据的稀疏性等。

1. 欧氏距离(Euclidean Distance)

欧式距离是高维空间中两点之间的距离，它计算简单、应用广泛，但是没有考虑变量之间的相关性，当体现单一特征的多个变量参与计算时会影响结果的准确性，同时它对向量中得每个分量的误差都同等对待，一定程度上放大了较大变量误差在距离测度中的作用。

两个n维向量A(x11,x12,…,x1n)与B(x21,x22,…,x2n)间的欧氏距离定义为：D(A,B)=[(x11-x21)^2+(x12-x22)^2+…+(x1n-x2n)^2]^0.5

欧式距离的公式是 d=sqrt( ∑(xi1-xi2)^ ) 这里i=1,2..n

欧氏距离：(∑(Xi-Yi)2)1/2，即两项间的差是每个变量值差的平方和再平方根，目的是计算其间的整体距离即不相似性。

欧氏距离虽然很有用，但也有明显的缺点。它将样品的不同属性(即各指标或各变量)之间的差别等同看待，这一点有时不能满足实际要求。例如，在教育研究中， 经常遇到对人的分析和判别，个体的不同属性对于区分个体有着不同的重要性。因此，有时需要采用不同的距离函数。

欧氏距离看作信号的相似程度。 距离越近就越相似，就越容易相互干扰，误码率就越高。

2. 曼哈顿距离(Manhattan Distance)

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

两个n维向量A(x11,x12,…,x1n)与B(x21,x22,…,x2n)间的曼哈顿距离定义为：D(A,B)=|x11-x21|+|x12-x22|+…+|x1n-x2n|

两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的曼哈顿距离

以上两个距离都具有的数学性质是：

非负性：d(i,j)≥0 距离是一个非负的数值

同一性：d(i,i)= 0 对象到自身的距离为0

对称性：d(i,j)= d(j,i)距离是一个对称函数

三角不等式：d(i,j)≤d(i,k)+d(k,j)从对象i到对象j的直接距离不会大于途经的任何其他对象k的距离

3. 切比雪夫距离 (Chebyshev Distance )

数学上，切比雪夫距离(Chebyshev distance)或是L∞度量是向量空间中的一种度量，二个点之间的距离定义为其各座标数值差的最大值。以(x1,y1)和(x2,y2)二点为例，其切比雪夫距离为max(|x2-x1|,|y2-y1|)。切比雪夫距离得名自俄罗斯数学家切比雪夫。

切比雪夫距离也称为棋盘距离，国际象棋中，国王走一步能够移动到相邻的8个方格中的任意一个，那么国王从格子A(x1,y1)走到格子B(x2,y2)最少需要多少步你会发现最少步数总是max{|x2-x1|,|y2-y1|}步。

两个n维向量A(x11,x12,…,x1n)与B(x21,x22,…,x2n)间的切比雪夫距离定义为：D(A,B)=max{|x11-x21|,|x12-x22|,…,|x1n-x2n|},该公式的另一种等价形式是：D(A,B)=[(x11-x21)^k+(x12-x22)^k+…+(x1n-x2n)^k]^(1/k)，其中k趋向于无穷大。

4. 闵氏距离(Minkowski Distance)

闵可夫斯基距离：

闵可夫斯基距离(Minkowski distance)是衡量数值点之间距离的一种非常常见的方法，假设数值点 P 和 Q 坐标如下：

那么，闵可夫斯基距离定义为：

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

该距离最常用的 p 是 2 和 1, 前者是欧几里得距离(Euclidean distance)，后者是曼哈顿距离(Manhattan distance)。假设在曼哈顿街区乘坐出租车从 P 点到 Q 点，白色表示高楼大厦，灰色表示街道：

绿色的斜线表示欧几里得距离，在现实中是不可能的。其他三条折线表示了曼哈顿距离，这三条折线的长度是相等的。

当 p 趋近于无穷大时，闵可夫斯基距离转化成切比雪夫距离(Chebyshev distance)：

我们知道平面上到原点欧几里得距离(p = 2)为 1 的点所组成的形状是一个圆，当 p 取其他数值的时候呢

注意，当 p < 1 时，闵可夫斯基距离不再符合三角形法则，举个例子：当 p < 1, (0,0) 到 (1,1) 的距离等于 (1 1)^{1/p} > 2, 而 (0,1) 到这两个点的距离都是 1。

闵可夫斯基距离比较直观，但是它与数据的分布无关，具有一定的局限性，如果 x 方向的幅值远远大于 y 方向的值，这个距离公式就会过度放大 x 维度的作用。所以，在计算距离之前，我们可能还需要对数据进行 z-transform 处理，即减去均值，除以标准差：

可以看到，上述处理开始体现数据的统计特性了。这种方法在假设数据各个维度不相关的情况下利用数据分布的特性计算出不同的距离。如果维度相互之间数据相关(例如：身高较高的信息很有可能会带来体重较重的信息，因为两者是有关联的)，这时候就要用到马氏距离(Mahalanobis distance)了。

两个n维变量A(x11,x12,…,x1n)与B(x21,x22,…,x2n)间的闵氏距离定义为：D(A,B)=[|x11-x21|^p+|x12-x22|^p+…+|x1n-x2n|^p]^(1/p)，其中p是一个可变参数。当p=1时为曼哈顿距离，当p=2时为欧氏距离，当p→∞时为切比雪夫距离。

闵氏距离，包括曼哈顿距离、欧氏距离和切比雪夫距离都存在明显的缺点：(1)对各个分量的量纲(Scale)没有区别对待。(2)未考虑各个分量的分布(期望，方差等)可能是不同的。

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

标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进，其基本思想是先将数据对象的各个分量都进行均值为μ、标准差为s的标准化，然后再计算欧式距离。

两个n维向量A(x11,x12,…,x1n)与B(x21,x22,…,x2n)的标准化欧氏距离定义为：D(A,B)={[(x11-x21)/s1]^2+[(x12-x22)/s2]^2+…+[(x1n-x2n)/sn]^2}^0.5

6. 马氏距离(Mahalanobis Distance)

马氏距离由印度统计学家马哈拉诺斯(P.C.Mahalanobis)提出，表示数据的协方差距离，与欧式距离不同，它考虑了各指标之间相关性的干扰，而且不受各指标量纲的影响，但是它的缺点是夸大了变化微小的变量的作用。

设A、B是从均值向量为μ，协方差阵为∑的总体G中抽取的两个样本，A、B两点之间的马氏距离定义为：D(A,B)=[(A-B)T∑-1(A-B)]^0.5，A与总体G的马氏距离定义为D(A,G)=[(A-μ)T∑-1(A-μ)]^0.5。

当协方差矩阵∑是单位矩阵(各个样本向量之间独立同分布),则马氏公式就转化为欧氏距离;当协方差矩阵∑是对角阵时，则马氏距离就转化为标准化欧式距离;

7. 汉明距离(Hamming Distance)

在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。

例如：1011101 与 1001001 之间的汉明距离是 2;”toned”与”roses” 之间的汉明距离是3。

8. 皮尔逊相关系数(Pearson Correlation coefficient )

皮尔逊相关系数也称为简单相关系数，它是衡量随机变量X与Y相关程度的一种方法，相关系数的取值范围是[-1,1]。相关系数的绝对值越大，则表明X与Y相关度越高，负值表示负相关，正值表示正相关。

皮尔逊相关系数定义如下：r(X,Y)=Cov(X,Y)/[(D(X)^0.5)*(D(Y)^0.5)]=E((X-EX)*(Y-EY))/[(D(X)^0.5)*(D(Y)^0.5)]=[(X1-X_bar)(Y1-Y_bar)+(X2-X_bar)(Y2-Y_bar)+…+(Xn-X_bar)(Yn-Y_bar)]/{[(X1-X_bar)^2+(X2-X_bar)^2+…(Xn-X_bar)]*[(Y1-Y_bar)^2+(Y2-Y_bar)^2+…(Yn-Y_bar)]}^0.5。

Pearson相关系数要求参与计算的变量为服从双变量正态分布的连续型数据，并且仅适用于线性相关的情况。另外，当极值对Pearson相关系数的影响非常大，因此在计算之前要首先进行极值处理。

9.斯皮尔曼秩相关系数(Spearman Rank Correlation)

与Pearson相关系数一样，它也可以反映两组变量联系的紧密程度，取值在-1到+1之间，计算方法上也完全相同，不同的是它建立在秩次的基础之上，对原始变量的分布和样本容量的大小不作要求，属于非参数统计方法，适用范围更广。

设R(R1,R2,…,Rn)表示X在(X1,X2,…,Xn)中的秩，Q(Q1,Q2,…,Qn)表示Y在(Y1,Y2,…,Yn)中的秩，如果X和Y具有同步性，那么R和Q也会表现出同步性，反之依然，将其代入Pearson相关系数，就得到秩之间的一致性，也就是Spearman相关系数。考虑到R1+R2+…Rn=Q1+Q2+…+Qn=n(n+1)/2，R1^2+R2^2++Rn^2=Q1^2+Q2^2+…+Qn^2=n(n+1)(2n+1)/6，Spearman相关系数可以定义为：r(X,Y)=1-6*[(R1-Q1)^2+(R2-Q2)^2+…(Rn-Qn)^2]/[n(n^2-1)]

10.肯德尔秩相关系数(Kendall Rank Correlation )

Kendall在本质设想方面与Spearman是一样的，它从两个变量是否协同一致的角度出发检验两变量之间是否存在相关性。什么是协同假设两

个变量X、Y有n对观察值(X1,Y1)(X2,Y2)…(Xn,Yn)，如果(Xj-Xi)(Yj-Yi)>0(j>i),称(Xi,Yi)与(Xj,Yj)满足协同性(concordant)，或者说变化方向一致。否则，不满足协同性。

全部数据共有n(n-1)/2对，如果用Nc表示同向数对的数目，Nd表示反向数对的数目，则Nc+Nd=n(n-1)/2，Kendall相关系数由两者的平均差定义：(Nc-Nd)/[n(n-1)/2]。Kendall相关系数的取值范围在-1到1之间，当等于1时，表示两个随机变量拥有一致的等级相关性;当等于-1时，表示两个随机变量拥有完全相反的等级相关性;当等于0时，表示两个随机变量是相互独立的。

11. 余弦相似度(Cosine Similarity)

几何中夹角余弦可用来衡量两个向量方向的差异，机器学习中用这一概念来衡量样本向量之间的差异。夹角余弦的取值范围为[-1,1]。夹角余弦越大表示两个向量的夹角越小，夹角余弦越小表示两向量的夹角越大。当两个向量的方向重合时夹角余弦取最大值1，当两个向量的方向完全相反夹角余弦取最小值-1。

两个n维样本向量A(x11,x12,…,x1n)和B(x21,x22,…,x2n)的夹角余弦定义为：cosθ=(A·B)/(|A|*|B|)=(x11*x21+x12*x22+…X1n*X2n)/[(x11^2+x12^2+…+x1n^2)^0.5*(x21^2+x22^2+…+x2n^2)^0.5]，夹角余弦经常应用于像文档这样的稀疏数据，它变量的长度无关，如向量(1,2)和(2,4)的夹角余弦与向量(1,2)和(10,20)的相等。

欧氏距离是最常见的距离度量，而余弦相似度则是最常见的相似度度量，很多的距离度量和相似度度量都是基于这两者的变形和衍生，所以下面重点比较下两者在衡量个体差异时实现方式和应用环境上的区别。

借助三维坐标系来看下欧氏距离和余弦相似度的区别：

从图上可以看出距离度量衡量的是空间各点间的绝对距离，跟各个点所在的位置坐标(即个体特征维度的数值)直接相关;而余弦相似度衡量的是空间向量的夹角，更加的是体现在方向上的差异，而不是位置。如果保持A点的位置不变，B点朝原方向远离坐标轴原点，那么这个时候余弦相似度cosθ是保持不变的，因为夹角不变，而A、B两点的距离显然在发生改变，这就是欧氏距离和余弦相似度的不同之处。

根据欧氏距离和余弦相似度各自的计算方式和衡量特征，分别适用于不同的数据分析模型：欧氏距离能够体现个体数值特征的绝对差异，所以更多的用于需要从维度的数值大小中体现差异的分析，如使用用户行为指标分析用户价值的相似度或差异;而余弦相似度更多的是从方向上区分差异，而对绝对的数值不敏感，更多的用于使用用户对内容评分来区分用户兴趣的相似度和差异，同时修正了用户间可能存在的度量标准不统一的问题(因为余弦相似度对绝对数值不敏感)。

12.调整余弦相似度(Adjusted Cosine Similarity)

余弦相似度更多的是从方向上区分差异，而对绝对的数值不敏感。因此没法衡量每个维数值的差异，会导致这样一个情况：比如用户对内容评分，5分制，X和Y两个用户对两个内容的评分分别为(1,2)和(4,5)，使用余弦相似度得出的结果是0.98，两者极为相似，但从评分上看X似乎不喜欢这2个内容，而Y比较喜欢，余弦相似度对数值的不敏感导致了结果的误差，需要修正这种不合理性。

调整余弦相似度，将所有维度上的数值都减去一个均值，比如X和Y的评分均值都是3，那么调整后为(-2,-1)和(1,2)，再用余弦相似度计算，得到-0.8，相似度为负值并且差异不小，但显然更加符合现实。

13. 简单匹配系数(Simple Matching Coefficient，SMC)

设A、B是两个二元属性组成的对象，这两个对象的比较导致如下四个频率变量：f00：A取0并且B取0属性的个数;f01：A取0并且B取1属性的个数;f10：A取1并且B取0属性的个数;f11：A取1并且B取1属性的个数。那么SMC就是两个对象A、B属性值匹配的属性个数与所有属性个数的比值，即SMC(A,B)=(f11+f00)/(f01+f10+f11+f00)

14. Jaccard系数(Jaccard Coefficient)

当数据对象的二元属性是非对称的时，例如用1表示商品被购买，用0表示商品未被购买。由于未被购买的商品数远远大于被购买的商品数，因此，如果用SMC计算数据对象的相似度，其结果必然是所有的数据对象都是相似的。

Jaccard系数可以处理仅包含非对称二元属性的对象，它是匹配属性的个数与不涉及0-0匹配的属性个数的比值，即J(A,B)=f11/(f01+f10+f11)。

15. 广义Jaccard系数(Extended Tanimoto Coefficient)

广义Jaccard系数又称为Tanimoto系数，常常用于文档数据，并在二元属性情况下规约为Jaccard系数。

该系数用EJ表示，定义如下：EJ(A,B)=(A·B)/(|A|*|A|+|B|*|B|-A·B)=(x11*x21+x12*x22+…+x1n*x2n)/[(x11^2+x12^+…x1n^2)+(x21^2+x22^2+…+x2n^2)-(x11*x21+x12*x22+…+x1n*x2n)]