技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 相似度计算之马氏距离

相似度计算之马氏距离

浏览:1731次  出处信息

   马氏距离(Mahalanobis Distance)是由印度统计学家马哈拉诺比斯(P. C. Mahalanobis)提出的,表示数据的协方差距离。有时也被称为马哈拉诺比斯距离。它是一种有效的计算两个未知样本集的相似度的方法。与欧氏距离不同的是它考虑到各种特性之间的联系(例如:一条关于身高的信息会带来一条关于体重的信息,因为两者是有关联的)并且是尺度无关的(scale-invariant),即独立于测量尺度。

   一些基本概念:

  • 方差:方差是标准差的平方,而标准差的意义是数据集中各个点到均值点距离的平均值。反应的是数据的离散程度。

  • 协方差:标准差与方差是描述一维数据,当存在多维数据时,我们通常需要知道每个维数的变量中间是否存在关联。协方差就是衡量多维数据集中,变量之间相关性的统计量。如果两个变量之间的协方差为正值,则这两个变量之间存在正相关,若为负值,则为负相关。

   对于一个均值为\mu =(\mu _{1},\mu _{2},\mu _{3},\dots ,\mu _{p})^{T},协方差矩阵为\Sigma的多变量向量x=(x_{1},x_{2},x_{3},\dots ,x_{p})^{T},其马氏距离为:

    \[D_{M}(x)={\sqrt {(x-\mu )^{T}\Sigma ^{-1}(x-\mu )}}\]

   马氏距离也可以定义为两个服从同一分布并且其协方差矩阵为\Sigma的随机变量{\vec {x}}{\vec {y}}的差异程度:

    \[d({\vec {x}},{\vec {y}})={\sqrt {({\vec {x}}-{\vec {y}})^{T}\Sigma ^{-1}({\vec {x}}-{\vec {y}})}}\]

   如果协方差矩阵为单位矩阵,马氏距离就简化为欧氏距离;如果协方差矩阵为对角阵,其也可称为正规化的欧氏距离。

    \[d({\vec {x}},{\vec {y}})={\sqrt {\sum _{i=1}^{p}{(x_{i}-y_{i})^{2} \over \sigma _{i}^{2}}}}\]

   其中\sigma _{i}x_{i}的标准差。

   Python实现:

import pandas as pd
import scipy as sp
from scipy.spatial.distance import mahalanobis

datadict = {
'country': ['Argentina', 'Bolivia', 'Brazil', 'Chile', 'Ecuador', 'Colombia', 'Paraguay', 'Peru', 'Venezuela'],
'd1': [0.34, -0.19, 0.37, 1.17, -0.31, -0.3, -0.48, -0.15, -0.61],
'd2': [-0.57, -0.69, -0.28, 0.68, -2.19, -0.83, -0.53, -1, -1.39],
'd3': [-0.02, -0.55, 0.07, 1.2, -0.14, -0.85, -0.9, -0.47, -1.02],
'd4': [-0.69, -0.18, 0.05, 1.43, -0.02, -0.7, -0.72, 0.23, -1.08],
'd5': [-0.83, -0.69, -0.39, 1.31, -0.7, -0.75, -1.04, -0.52, -1.22],
'd6': [-0.45, -0.77, 0.05, 1.37, -0.1, -0.67, -1.4, -0.35, -0.89]}

pairsdict = {
'country1': ['Argentina', 'Chile', 'Ecuador', 'Peru'],
'country2': ['Bolivia', 'Venezuela', 'Colombia', 'Peru']}

#DataFrame that contains the data for each country
df = pd.DataFrame(datadict)

#DataFrame that contains the pairs for which we calculate the Mahalanobis distance
pairs = pd.DataFrame(pairsdict)

#Add data to the country pairs
pairs = pairs.merge(df, how='left', left_on=['country1'], right_on=['country'])
pairs = pairs.merge(df, how='left', left_on=['country2'], right_on=['country'])

#Convert data columns to list in a single cell
pairs['vector1'] = pairs[['d1_x','d2_x','d3_x','d4_x','d5_x','d6_x']].values.tolist()
pairs['vector2'] = pairs[['d1_y','d2_y','d3_y','d4_y','d5_y','d6_y']].values.tolist()

mahala = pairs[['country1', 'country2', 'vector1', 'vector2']]

#Calculate covariance matrix
covmx = df.cov()
invcovmx = sp.linalg.inv(covmx)

#Calculate Mahalanobis distance
mahala['mahala_dist'] = mahala.apply(lambda x: (mahalanobis(x['vector1'], x['vector2'], invcovmx)), axis=1)

mahala = mahala[['country1', 'country2', 'mahala_dist']]

   其他参考资料:

   根据马氏距离的定义,可以得到它的几个特点如下:

  • 两点之间的马氏距离与原始数据的测量单位无关(不受量纲的影响)

  • 标准化数据和中心化数据(即原始数据与均值之差)计算出的二点之间的马氏距离相同

  • 可以排除变量之间的相关性的干扰

  • 满足距离的四个基本公理:非负性、自反性、对称性和三角不等式

  • 缺点是夸大了变化微小的变量的作用

   考虑下面这张图,椭圆表示等高线,从欧几里得的距离来算,绿黑距离大于红黑距离,但是从马氏距离,结果恰好相反:

   

   马氏距离实际上是利用 Cholesky transformation 来消除不同维度之间的相关性尺度不同的性质。

   下图是一个二元变量数据的散点图:

   

   当我们将坐标轴拿掉,如下图:

   

   根据数据本身的提示信息来引入新的坐标轴:坐标的原点在这些点的中央(根据点的平均值算得)。第一个坐标轴(下图中蓝色的线)沿着数据点的“脊椎”,并向两端延伸,定义为使得数据方差最大的方向。第二个坐标轴(下图红色的线)会与第一个坐标轴垂直并向两端延伸。如果数据的维度超过了两维,那就选择使得数据方差是第二个最大的方向,以此类推。

   

   我们需要一个比例尺度。沿着每一个坐标轴的标准差来定义一个单位长度。使用“68-95-99.7法则”更容易找到合理的单位。(大约68%的点需要在离原点一个单位长度的范围内;大约95%的点需要在离原点两个单位的长度范围内;99.7的点需要在3个单位程度范围内。)为了以示参考,如下图:

   

   由于每个轴上的单位长度不相等,所以上图中距离原点一个单位的形成的轨迹并不是一个圆形。为了更好的呈现图表,我们将图片进行旋转。同时,并让每个轴方向上的单位长度相同:

   

   上面就是从散点图中构建坐标系统的过程,为的是方便进行测量。

   说明:

  • 沿着新坐标轴的单位向量是协方差矩阵的特征向量。注意到没有变形的椭圆,变成圆形后沿着特征向量用标准差(协方差的平方根)将距离长度分割。

  • 坐标轴扩展的量是协方差矩阵的逆的特征值(平方根),同理的,坐标轴缩小的量是协方差矩阵的特征值。所以,点越分散,需要的将椭圆转成圆的缩小量就越多。

  • 尽管上述的操作可以用到任何数据上,但是对于多元正态分布的数据表现更好。在其他情况下,点的平均值或许不能很好的表示数据的中心,或者数据的“脊椎”(数据的大致趋势方向)不能用变量作为概率分布测度来准确的确定。

  • 原始坐标系的平移、旋转,以及坐标轴的伸缩一起形成了仿射变换(affine transformation)。除了最开始的平移之外,其余的变换都是基底变换,从原始的一个变为新的一个。

  • 在新的坐标系中,多元正态分布像是标准正太分布,当将变量投影到任何一条穿过原点的坐标轴上。特别是,在每一个新的坐标轴上,它就是标准正态分布。从这点出发来看,多元正态分布彼此之实质性的差异就在于它们的维度。

   参考链接:https://stats.stackexchange.com/questions/62092/bottom-to-top-explanation-of-the-mahalanobis-distance

建议继续学习:

  1. 相似度计算常用方法综述    (阅读:9353)
  2. 字符串匹配那些事(一)    (阅读:5736)
  3. 如何计算两个文档的相似度(一)    (阅读:4742)
  4. URL相似度计算的思考    (阅读:3685)
  5. 如何计算两个文档的相似度(二)    (阅读:3732)
  6. Levenshtein distance相似度算法    (阅读:3102)
  7. 如何计算两个文档的相似度(三)    (阅读:2896)
  8. 若无云,岂有风——词语语义相似度计算简介    (阅读:2471)
  9. 相似度计算之兰氏距离    (阅读:1834)
  10. 常见相似度计算方法回顾    (阅读:1699)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1