相似度计算之马氏距离

24 sec read

马氏距离(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实现:

其他参考资料:

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

  • 两点之间的马氏距离与原始数据的测量单位无关(不受量纲的影响)
  • 标准化数据和中心化数据(即原始数据与均值之差)计算出的二点之间的马氏距离相同
  • 可以排除变量之间的相关性的干扰
  • 满足距离的四个基本公理:非负性、自反性、对称性和三角不等式
  • 缺点是夸大了变化微小的变量的作用

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

马氏距离实际上是利用 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

打赏作者
微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode

K-Means算法之K值的选择

4 min read

聚类算法之K-Means及其变种

3 min read

信息熵与相对熵(KL距离)

信息熵 在信息论中,熵是接收的每条消息中包含的信息的平均量,又被称为信息熵、信源熵、平均自信息量。这里, 消息代表来自分布或数据流中的事件、样本或特征。在信息世界,熵越高,则能传输越多的信息,熵越低,则意味着传输的信息越少。 ...
25 sec read

Leave a Reply

Your email address will not be published. Required fields are marked *