机器学习中距离与相似度度量

机器学习中距离和相似度计算方法距离与度量相关距离闵可夫斯基距离欧氏距离曼哈顿距离切比雪夫距离改进闵可夫斯基距离标准化欧氏距离（加权）马氏距离相似度度量余弦相似度改进：调整余弦相似度皮尔森相关系数Jaccard相似系数欧式距离和余弦相似度的比较在机器学习和数据挖掘中，我们经常需要知道个体间差异的大小，进而评价个体的相似性和类别。根据数据特性的不同，可以采用不同的度量方法。一般而言，定义一个距离函数d(x,y),需要满足下面几个基本准则：1)d(x,x)=0//到自己的距离为02)d(x,y)=0//距离非负3)d(x,y)=d(y,x)//对称性:如果A到B距离是a，那么B到A的距离也应该是a4)d(x,k)+d(k,y)=d(x,y)//三角形法则:(两边之和大于第三边)即：所有点的对应维度之差的平方的求和再开方。欧式距离相似度算法需要保证各个维度指标在相同的刻度级别，比如对身高、体重两个单位不同的指标使用欧氏距离可能使结果失效。欧式距离曼哈顿距离来源于城市区块距离，是将多个维度上的距离进行求和后的结果曼哈顿距离切比雪夫距离（Chebyshevdistance）是向量空间中的一种度量，二个点之间的距离定义为其各坐标数值差的最大值。从一个位置走到其他位置需要的步数恰为二个位置的切比雪夫距离，因此切比雪夫距离也称为棋盘距离。切比雪夫距离闵可夫斯基距离（Minkowskidistance）不是一种距离，而是一组距离的定义。该距离最常用的p是2和1,无穷大•P=2是欧几里得距离（Euclideandistance），•P=1是曼哈顿距离（Manhattandistance）。•当p趋近于无穷大时，闵可夫斯基距离转化成切比雪夫距离（Chebyshevdistance）闵可夫斯基距离pnkpkkxx1121缺点：举个栗子二维样本(身高,体重)，其中身高范围是150~190，体重范围是50~60，有三个样本：a(180,50)，b(190,50)，c(180,60)。那么a与b之间的闵氏距离（无论是曼哈顿距离、欧氏距离或切比雪夫距离）等于a与c之间的闵氏距离，但是身高的10cm等价于体重的10kg吗？因此用闵氏距离来衡量这些样本间的相似度有问题。简单说来，闵氏距离的缺点主要有两个：1.将各个分量的量纲(scale)，也就是“单位”当作相同的看待了。2.没有考虑各个分量的分布（期望，方差等)可能是不同的。引入标准化欧式距离的原因是一个数据xi的各个维度之间的尺度不一样。比如v1=(100,10,30),v2=(500,40,10)。对所有维度分别进行处理，使得各个维度分别满足标准正态分布。即如果将方差的倒数看成是一个权重，这个公式可以看成是一种加权欧氏距离(WeightedEuclideandistance)。标准化欧氏距离nkkkknkkkksxxsxx122211221d无量纲化标准化归一化使不同规格的数据转换到同一规格标准化：对不同特征维度的伸缩变换的目的是使得不同度量之间的特征具有可比性。同时不改变原始数据的分布。特点：1、保持各个特征维度对目标函数的影响权重2、对目标函数的影响体现在几何分布上3、在已有样本足够多的情况下比较稳定。归一化（区间缩放）：基于边界值（最大值，最小值），将值的区间缩放到某个特点的范围，如[0,1]特点：1、对不同特征维度进行伸缩变换2、改变原始数据的分布。使各个特征维度对目标函数的影响权重是一致的）3、对目标函数的影响体现在数值上4、把有量纲表达式变为无量纲表达式。列行马式距离若协方差矩阵是单位矩阵（各个样本向量之间独立同分布）,则公式就成了：则Xi与Xj之间的马氏距离等于他们的欧氏距离。即：若协方差矩阵是对角矩阵，公式变成了标准化欧氏距离。标准化欧氏距离是在假设数据各个维度不相关的情况下，利用数据分布的特性计算出不同的距离。如果维度相互之间数据相关（例如：身高较高的信息很有可能会带来体重较重的信息，因为两者是有关联的），就要用到马氏距离相似度度量相似度度量（Similarity），即计算个体间的相似程度，与距离度量相反，相似度度量的值越小，说明个体间相似度越小，差异越大。两个向量越相似，向量夹角越小，余弦值的绝对值越大；值为负，两向量负相关。应用：文本的相似度和推荐系统等。余弦相似度举个简单栗子：句子A：这只皮靴号码大了。那只号码合适句子B：这只皮靴号码不小，那只更合适怎样计算上面两句话的相似程度？基本思路：如果这两句话的用词越相似，它们的内容就应该越相似。因此，可以从词频入手，计算它们的相似程度。第一步，分词。句子A：这只/皮靴/号码/大了。那只/号码/合适。句子B：这只/皮靴/号码/不/小，那只/更/合适。第二步，列出所有的词。这只，皮靴，号码，大了。那只，合适，不，小，很第三步，计算词频。句子A：这只1，皮靴1，号码2，大了1。那只1，合适1，不0，小0，更0句子B：这只1，皮靴1，号码1，大了0。那只1，合适1，不1，小1，更1第四步，写出词频向量。句子A：(1，1，2，1，1，1，0，0，0)句子B：(1，1，1，0，1，1，1，1，1)第五步，使用公式计算相似度计算结果：夹角的余弦值为0.81，非常接近于1，所以，上面的句子A和句子B是基本相似的（1）欧氏距离从向量间的绝对距离区分差异，计算得到的相似度值对向量各个维度内的数值特征非常敏感，而余弦夹角从向量间的方向夹角区分差异，对向量各个维度内的数值特征不敏感，所以同时修正了用户间可能存在的度量标准不统一的问题。（2）余弦夹角的值域区间为[-1,1]，相对于欧式距离的值域范围[0,正无穷大],能够很好的对向量间的相似度值进行了量化。因此，在推荐系统场景下，推荐算法大都采用余弦夹角进行用户（或物品）的相似度计算。当然，欧氏距离能够体现个体数值特征的绝对差异，一般用于需要从维度的数值大小中体现差异的相关度分析。补充：欧式距离和余弦相似度调整余弦相似度(AdjustedCosineSimilarity)虽然余弦相似度对个体间存在的偏见可以进行一定的修正，但是因为只能分辨个体在维之间的差异，没法衡量每个维数值的差异，会导致这样一个情况：比如用户对内容评分，5分制。（此处是两个内容）X评分为(1,2)，Y评分为(4,5)，使用余弦相似度得出的结果是0.98。两者极为相似，但从评分上看X似乎不喜欢这2个内容，而Y比较喜欢，余弦相似度对数值的不敏感导致了结果的误差。需要修正这种不合理性，就出现了调整余弦相似度，即所有维度上的数值都减去一个均值，比如X和Y的评分均值都是3，那么调整后为(-2,-1)和(1,2)，再用余弦相似度计算，得到-0.8，相似度为负值并且差异不小，但显然更加符合现实。pearson是一个介于-1和1之间的值，用来描述两组线性的数据一同变化移动的趋势。相关系数0，表明它们之间是正相关的。即当一个变量增大，另一个变量也增大；相关系数0，表明它们之间是负相关的，如果一个变量增大，另一个变量却减小，；如果相关系数=0，表明它们之间不存在线性相关关系。皮尔森相关系数上面是总体相关系数，估算样本的协方差和标准差，可得到样本相关系数(样本皮尔逊系数)，常用英文小写字母r代表：缺点：1.未考虑重叠记录项的数量对相似度的影响上表中，行表示用户（1～5）对项目（101～103）的一些评分值。直观来看，User1和User5用3个共同的评分项，并且给出的评分趋势相同，User1与User4只有2个相同评分项，虽然他们的趋势也相似，但是由于102的未知，可能是User2对102未发生行为，或者对102很讨厌，所以我们更希望User1和User5更相似，但结果是User1与User4有着更高的结果。可以看出pearson系数只会对重叠的记录进行计算。2.如果只有一个重叠项则无法计算相关性从数学上讲，若只有一个重叠的记录，那么至少有一组记录的标准差为0，导致分母为0从这一点也可以看出，pearson系数不适用与小的或者非常稀疏的数据集。当然，这一特性也有它的好处，无法计算pearson系数可以认为这两组数据没有任何相关性。3.Pearson系数对绝对数值不敏感考虑这三组数据，a:(1,2,3,4)b:(40,50,70,80)c:(50,60,70,80),我们可以直观的认为b和c更为相似，它们的重叠评分数目一致，趋势也相同，记录a虽然也满足上述的条件，但是它整体数值很低。在现实中，有人习惯于给出更高的评分，而有人则恰恰相反。利用pearson计算它们之间的相似度为：a&b:0.9899494936611665b&c:0.9899494936611665a&c:0.9999999999999999可以看出pearson系数对绝对数值并不敏感，它确实只是描述了两组数据变化的趋势。Jaccard相似系数(JaccardCoefficient)Jaccard系数主要用于计算符号度量或布尔值度量的个体间的相似度，因为个体的特征属性都是由符号度量或者布尔值标识，因此无法衡量差异具体值的大小，只能获得“是否相同”这个结果，所以Jaccard系数只关心个体间共同具有的特征是否一致这个问题。如果比较X与Y的Jaccard相似系数，只比较xn和yn中相同的个数，公式如下：