首页 > 其他分享 >马氏距离 Mahalanobis Distance

马氏距离 Mahalanobis Distance

时间:2023-11-07 11:34:49浏览次数:33  
标签:Distance 马氏 样本 Mahalanobis 距离 矩阵 协方差 维度

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

1)马氏距离的计算是建立在总体样本的基础上的,这一点可以从上述协方差矩阵的解释中可以得出,也就是说,如果拿同样的两个样本,放入两个不同的总体中,最后计算得出的两个样本间的马氏距离通常是不相同的,除非这两个总体的协方差矩阵碰巧相同;

2)在计算马氏距离过程中,要求总体样本数大于样本的维数,否则得到的总体样本协方差矩阵逆矩阵不存在,这种情况下,用欧式距离计算即可。
S = D1 * D1' (D1为m*n矩阵,m > n, m为特征维数,n为样本数)
rank(S) <= n 故 S 不可逆。
[if A=BC, then rank(A) <= min(rank(B), rank(C)).]

3)还有一种情况,满足了条件总体样本数大于样本的维数,但是协方差矩阵的逆矩阵仍然不存在,比如三个样本点(3,4),(5,6)和(7,8),这种情况是因为这三个样本在其所处的二维空间平面内共线。这种情况下,也采用欧式距离计算。
(均值向量为[5, 6], D1 = [-2 0 2; -2 0 2], S显然不可逆)

4)在实际应用中“总体样本数大于样本的维数”这个条件是很容易满足的,而所有样本点出现3)中所描述的情况是很少出现的,所以在绝大多数情况下,马氏距 离是可以顺利计算的,但是马氏距离的计算是不稳定的,不稳定的来源是协方差矩阵,这也是马氏距离与欧式距离的最大差异之处。

优点:它不受量纲的影响,两点之间的马氏距离与原始数据的测量单位无关;由标准化数据和中心化数据(即原始数据与均值之差)计算出的二点之间的马氏距离相同。马氏距离还可以排除变量之间的相关性的干扰。

缺点:它的缺点是夸大了变化微小的变量的作用。
——————————————————————————————————————
Matlab函数 d = mahal(Y,X)   ——  计算Y中每个样本到X数据集中心的马氏距离。

即:d(I) = (Y(I,:)-mu)*inv(SIGMA)*(Y(I,:)-mu)',其中mu、SIGMA分别为X的均值和方差。

X的行数必须大于列数(样本数多于维数)。

——————————————————————————————————————

相关

Pearson’s coefficient;Euclidean distance;

======================================================================

马氏距离(Mahalanobis Distance)是一种距离的度量,可以看作是欧氏距离的一种修正,修正了欧式距离中各个维度尺度不一致且相关的问题。

 

单个数据点的马氏距离

马氏距离 Mahalanobis Distance_方差

数据点x, y之间的马氏距离

马氏距离 Mahalanobis Distance_协方差矩阵_02

其中Σ是多维随机变量的协方差矩阵,μ为样本均值,如果协方差矩阵是单位向量,也就是各维度独立同分布,马氏距离就变成了欧氏距离。

马氏距离实际意义

马氏距离能干什么?它比欧氏距离好在哪里?

欧式距离近就一定相似?

先举个比较常用的例子,身高和体重,这两个变量拥有不同的单位标准,也就是有不同的scale。比如身高用毫米计算,而体重用千克计算,显然差10mm的身高与差10kg的体重是完全不同的。但在普通的欧氏距离中,这将会算作相同的差距。

归一化后欧氏距离近就一定相似?

当然我们可以先做归一化来消除这种维度间scale不同的问题,但是样本分布也会影响分类

举个一维的栗子,现在有两个类别,统一单位,第一个类别均值为0,方差为0.1,第二个类别均值为5,方差为5。那么一个值为2的点属于第一类的概率大还是第二类的概率大?距离上说应该是第一类,但是直觉上显然是第二类,因为第一类不太可能到达2这个位置。

所以,在一个方差较小的维度下很小的差别就有可能成为离群点。就像下图一样,A与B相对于原点的距离是相同的。但是由于样本总体沿着横轴分布,所以B点更有可能是这个样本中的点,而A则更有可能是离群点。

马氏距离 Mahalanobis Distance_方差_03

 

算上维度的方差就够了?

还有一个问题——如果维度间不独立同分布,样本点一定与欧氏距离近的样本点同类的概率更大吗?

 

马氏距离 Mahalanobis Distance_协方差矩阵_04

 

可以看到样本基本服从f(x) = x的线性分布,A与B相对于原点的距离依旧相等,显然A更像是一个离群点

即使数据已经经过了标准化,也不会改变AB与原点间距离大小的相互关系。所以要本质上解决这个问题,就要针对主成分分析中的主成分来进行标准化。

马氏距离的几何意义

上面搞懂了,马氏距离就好理解了,只需要将变量按照主成分进行旋转,让维度间相互独立,然后进行标准化,让维度同分布就OK了

由主成分分析可知,由于主成分就是特征向量方向,每个方向的方差就是对应的特征值,所以只需要按照特征向量的方向旋转,然后缩放特征值倍就可以了,可以得到以下的结果:

 

马氏距离 Mahalanobis Distance_欧氏距离_05

 

离群点就被成功分离,这时候的欧式距离就是马氏距离。

马氏距离的推导

首先要对数据点进行旋转,旋转至主成分,维度间线性无关,假设新的坐标为

 

马氏距离 Mahalanobis Distance_协方差矩阵_06

 

又变换后维度间线性无关且每个维度自己的方差为特征值,所以满足:

 

马氏距离 Mahalanobis Distance_方差_07

 

马氏距离是旋转变换缩放之后的欧式距离,所以马氏距离的计算公式为:

马氏距离 Mahalanobis Distance_协方差矩阵_08

这就是之前提到的马氏距离的公式

马氏距离的问题

  • 协方差矩阵必须满秩

里面有求逆矩阵的过程,不满秩不行,要求数据要有原维度个特征值,如果没有可以考虑先进行PCA,这种情况下PCA不会损失信息

  • 不能处理非线性流形(manifold)上的问题

只对线性空间有效,如果要处理流形,只能在局部定义,可以用来建立KNN图

 

 

马氏距离 Mahalanobis Distance_欧氏距离_09

 

 

 

======================================================================

参考:

https://www.yingsoo.com/news/devops/38000.html

https://www.jb51.net/article/137650.htm

https://zhuanlan.zhihu.com/p/46626607http://zh.wikipedia.org/wiki/%E9%A9%AC%E6%B0%8F%E8%B7%9D%E7%A6%BB
http://rogerdhj.blog.sohu.com/39020502.html

http://zoonek2.free.fr/UNIX/48_R/06.html
http://www.jennessent.com/arcview/mahalanobis_description.htm
http://www.aiaccess.net/English/Glossaries/GlosMod/e_gm_mahalanobis



标签:Distance,马氏,样本,Mahalanobis,距离,矩阵,协方差,维度
From: https://blog.51cto.com/emanlee/8228767

相关文章

  • CodeForces 1246F Cursor Distance
    洛谷传送门CF传送门发现一个性质:能跳不超过\(j\)步到达\(i\)的所有点形成一段区间。设这这段区间为\([L_{i,j},R_{i,j}]\)。那么答案即为:\[\sum\limits_{i=1}^n\sum\limits_{j=0}n-R_{i,j}+L_{i,j}-1\]并且:\[[L_{i,j},R_{i,j}]=\bigcup\limits_......
  • AT_abc301_h [ABC301Ex] Difference of Distance
    AT_abc301_h[ABC301Ex]DifferenceofDistance更好的阅读体验一道基础图论,很好口胡,但是实现不太简单。考虑离线,把询问挂在边上,按边权从小到大处理。处理到一个边权时,把边权小于它的边的两端用并查集合并,对于等于这个边权的边在并查集上建图,跑一边tarjan,因为问的是边,所以把......
  • * Codeforces Round 665 (Div. 2) A. Distance and Axis
    有一个点\(A\)在\(OX\)正坐标轴上的\(x\)坐标为\(n\)。需要找到一个点\(B\),使得\(||OB|-|AB||=k\)。现在给出非负整数\(n\)\(k\),你可以执行任意次以下操作:每步操作可以使\(A\)的坐标加一或减一。询问最少需要进过多少次操作使\(B\)可以存在。先假设出......
  • Codeforces Round 903 (Div. 3) F. Minimum Maximum Distance(图论)
    CodeforcesRound903(Div.3)F.MinimumMaximumDistance思路对标记点更新fg,从0开始进行bfs,更新d1为所有点到0的距离获得到0最远的标记点L,从L开始bfs,更新d2为所有点到L的距离获得距离L最远的标记点R,从R开始bfs,更新d3为所有点到R的距离遍历所有点,这个点与标记点的最大距......
  • CF1881F Minimum Maximum Distance
    给定一棵树,树上的一些点被打上了标记,定义一个节点的贡献为其到所有标记节点距离的最大值,求最小贡献。\(n\le2\times10^5\)。这道题的原题是CF337D(甚至要更困难一些)。很套路的换根DP啊。我们考虑设\(f_i\)为\(i\)子树内的标记节点到\(i\)的最大距离,\(g_i\)为子......
  • System.NotSupportedException:“无法显式设置 SplitterPanel 的高度。改在 SplitCont
    System.NotSupportedException:“无法显式设置SplitterPanel的高度。改在SplitContainer上设置SplitterDistance。”这个错误信息是在使用SplitContainer控件时出现的。它表明您尝试显式设置SplitterPanel的高度,但这是不支持的操作,应该在SplitContainer上设置Splitte......
  • 基于pHash+hammingdistance的图片相似度比较
    参考文献图片相似度计算方法总结-知乎(zhihu.com)PythonOpenCV视觉特征提取和匹配-知乎(zhihu.com)图像相似度中的Hash算法-Yumeka-博客园(cnblogs.com)汉明距离及其高效计算方式(zhihu.com)开源仓库https://github.com/python-pillow/Pillowhttps://github.com/cybe......
  • 题解 [ARC165C] Social Distance on Graph
    赛时:看不懂题,啊这!赛后:就这?题目描述有一个简单相连的无向图,其顶点数为\(n\),编号为\(1\)至\(n\)。图中有\(m\)条加权边,第\(i\)条边连接顶点\(a_i\)和\(b_i\),权重为\(w_i\)。此外,连接两个顶点的简单路径的权重是简单路径中包含的边的权重之和。我们给每个顶点涂上红......
  • hdu 4712 Hamming Distance-----随机
    计算出二进制数中有多少个1:数据范围太大,想到可以随机如果你在第一次调用rand()之前没有调用srand(),那么系统会为你自动调用srand()。------百度rand#include<cstdio>#include<cstring>#include<algorithm>#include<time.h>usingnamespacestd;constintN=1e5+10......
  • AtCoder Beginner Contest 201 E - Xor Distances
    E-XorDistances原题链接题意:设dist(i,j)即i到j之间路径的异或和,求树上所有两点之间dist(i,j)的和思路:dist(i,j)=dist(i,1)^dist(j,1)根据异或性质相同的部分会被消掉用bfs求得dist(i,1)优化两层i,j的枚举:通过遍历每个数的每一位1的个数cnt,以及0的个数n-cnt,从而在1^0=1......