- Ref: 《统计学习方法》
目录
- L p L_p Lp 距离 ( L p L_p Lp distance) / Minkowski 距离 (Minkowski distance)
- 马氏距离 / 马哈拉诺比斯距离 (Mahalanobis Distance)
L p L_p Lp 距离 ( L p L_p Lp distance) / Minkowski 距离 (Minkowski distance)
- 当
p
=
2
p=2
p=2 时，称为欧氏距离 (Euclidean distance)
- 当
p
=
1
p=1
p=1 时，称为曼哈顿距离 (Manhattan distance)
- 当
p
=
∞
p= ∞
p=∞ 时，称为切比雪夫距离 (Chebyshev distance)，它是各个坐标距离的最大值，即
马氏距离 / 马哈拉诺比斯距离 (Mahalanobis Distance)
- 马氏距离是度量学习中一种常用的距离指标，同欧氏距离、曼哈顿距离、汉明距离等一样被用作评定数据之间的相似度指标。但却可以应对高维线性分布的数据中各维度间非独立同分布的问题
马氏距离
- 单个数据点的马氏距离
D M ( x ) = ( x − μ ) T Σ − 1 ( x − μ ) D_{M}(x)=\sqrt{(x-\mu)^{T} \Sigma^{-1}(x-\mu)} DM(x)=(x−μ)TΣ−1(x−μ) - 数据点
x
,
y
x, y
x,y 之间的马氏距离
D M ( x , y ) = ( x − y ) T Σ − 1 ( x − y ) D_{M}(x,y)=\sqrt{(x-y)^{T} \Sigma^{-1}(x-y)} DM(x,y)=(x−y)TΣ−1(x−y) 其中 Σ Σ Σ 是多维随机变量的协方差矩阵， μ μ μ 为样本均值，如果协方差矩阵是单位向量，也就是各维度独立同分布 (且各维度方差为 1)，马氏距离就变成了欧氏距离
马氏距离到底有什么用？
- 如下图的过程，此例的数据中心为原点，
P
1
P_1
P1,
P
2
P_2
P2 到原点的欧氏距离相同，但点
P
2
P_2
P2 在
y
y
y 轴上相对原点有较大的变异，而点
P
1
P_1
P1 在
x
x
x 轴上相对原点有较小的变异。所以
P
1
P_1
P1 点距原点的直观距离是比
P
2
P_2
P2 点的小的
-
马氏距离就是解决这个问题，它将直观距离和欧式距离统一。为了做到这一点， 它先将数据不同维度上的方差统一（即各维度上的方差相同），此时的欧式距离就是直观距离。如下图所示：统一方差后，
P
^
1
\hat P_1
P^1 到原点的距离小于
P
^
2
\hat P_2
P^2
- 但是，如果不同维度之间具有相关性，则压缩的效果就不好了。如下图只在横向和纵向上压缩，则达不到上图的压缩效果；只有在
F
1
F_1
F1 方向和
F
2
F_2
F2 方向上压缩数据才能达到较好的效果。所以需要将原始数据在
X
Y
XY
XY 坐标系中的坐标表示在
F
F
F 坐标系中。然后再分别沿着坐标轴压缩数据
- 所以，计算样本数据的马氏距离分为两个步骤
- (1) 坐标旋转: 使旋转后的各个维度之间线性无关 (也就是使得各个维度数据之间的协方差均为 0)，所以该旋转过程就是主成分分析的过程
- (2) 数据压缩: 将不同的维度上的数据压缩成为方差都是 1 的的数据集
马氏距离的推导
- 定义一组 R n \R^n Rn 上的正交基 P P P 作为旋转后的新坐标系， y y y 为样本 x x x 旋转后的新坐标 (在新坐标系内，样本 y y y 各个属性之间协方差为 0)，即 x = P y x=Py x=Py
- 设原协方差矩阵为
Σ
\Sigma
Σ，旋转后的协方差矩阵为
D
D
D (由于旋转后各个属性之间协方差为 0，因此
D
D
D 一定为对角矩阵)，有
Σ = 1 N − 1 ∑ n = 1 N ( x n − μ ) ( x n − μ ) T ∴ D = 1 N − 1 ∑ n = 1 N ( y n − μ ′ ) ( y n − μ ′ ) T = 1 N − 1 ∑ n = 1 N P ( x n − μ ) ( x n − μ ) T P T = P Σ P T \begin{aligned}\Sigma&=\frac{1}{N-1}\sum_{n=1}^N(x_n-\mu)(x_n-\mu)^T\\ \therefore D&=\frac{1}{N-1}\sum_{n=1}^N(y_n-\mu')(y_n-\mu')^T \\&=\frac{1}{N-1}\sum_{n=1}^NP(x_n-\mu)(x_n-\mu)^TP^T \\&=P\Sigma P^T\end{aligned} Σ∴D=N−11n=1∑N(xn−μ)(xn−μ)T=N−11n=1∑N(yn−μ′)(yn−μ′)T=N−11n=1∑NP(xn−μ)(xn−μ)TPT=PΣPT注意到这上面的推导和 PCA 是一样的， P P P 由 Σ \Sigma Σ 的特征向量基组成， D D D 为对角矩阵，对角元素为 Σ \Sigma Σ 对应的特征值 - 通过上面的推导，我们知道了如何旋转坐标系，之后我们要做的就是对旋转后的样本 y y y 进行数据压缩，压缩后的样本 y ^ = D − 1 y \hat y=\sqrt{D^{-1}}y y^=D−1 y
-
马氏距离是旋转变换缩放之后的欧式距离，因此马氏距离为:
D M = ( y ^ 1 − y ^ 2 ) T ( y ^ 1 − y ^ 2 ) = ( y 1 − y 2 ) T D − 1 ( y 1 − y 2 ) = ( x 1 − x 2 ) T P D − 1 P T ( x 1 − x 2 ) = ( x 1 − x 2 ) T ( P T D P ) − 1 ( x 1 − x 2 ) = ( x 1 − x 2 ) T ( P T P Σ P T P ) − 1 ( x 1 − x 2 ) = ( x 1 − x 2 ) T Σ − 1 ( x 1 − x 2 ) \begin{aligned}D_M&=(\hat y_1-\hat y_2)^T(\hat y_1-\hat y_2) \\&=(y_1-y_2)^T{D^{-1}}(y_1-y_2) \\&=(x_1-x_2)^TP{D^{-1}}P^T(x_1-x_2) \\&=(x_1-x_2)^T(P^T{D}P)^{-1}(x_1-x_2) \\&=(x_1-x_2)^T(P^TP\Sigma P^TP)^{-1}(x_1-x_2) \\&=(x_1-x_2)^T\Sigma^{-1}(x_1-x_2) \end{aligned} DM=(y^1−y^2)T(y^1−y^2)=(y1−y2)TD−1(y1−y2)=(x1−x2)TPD−1PT(x1−x2)=(x1−x2)T(PTDP)−1(x1−x2)=(x1−x2)T(PTPΣPTP)−1(x1−x2)=(x1−x2)TΣ−1(x1−x2)