马氏距离

协方差与协方差矩阵

  协方差计算的是两个随机变量之间线性相关程度。变量之间越相关，协方差越大。变量之间越无关，协方差越小。随机变量$X,Y$之间的协方差定义为

$$cov(X,Y) = E[(X-EX)(Y-EY)]$$

显然，计算同一个变量的协方差时等同于计算其方差。

  通过样本来统计其协方差时，假设单个样本为$m$维列向量$x_i$，将$n$个样本组合为一个$m \times n$的矩阵$X = (x_1,x_2,\cdots,x_n)$ 。$X$的数据可示例如下

$$\begin{bmatrix} x_{11}& x_{12}& \cdots & x_{1n}\\ x_{21}& x_{22}& \cdots & x_{2n}\\ \vdots &\vdots &&\vdots\\ x_{m1} &x_{m2}& \cdots & x_{mn}\end{bmatrix}$$

  注意这里求取的协方差是关于不同维度之间的，也就是一个维度（属性）可看作一个随机变量。比如维度1与维度2之间样本协方差的无偏估计可计算如下

$$cov(X1,X2) = \frac 1 {n-1} \sum_{i=1}^n (x_{1i}-\bar x_1)(x_{2i}-\bar x_1)$$

  两个变量时，它们的相关程度可以方便的用协方差表示。但在机器学习任务中，常常会处理具有多个属性的问题。每个属性都可看作一个随机变量，如果要考虑这些变量两两之间的关系，再挨个列出协方差太过麻烦。因此使用矩阵的形式将其组合起来，这就是协方差矩阵。

$$\Sigma = \begin{bmatrix} cov(X1,X1) & \cdots &cov(X1,Xm)\\ \vdots & \ddots &\vdots\\ cov(Xm,X1) & \cdots & cov(Xm,Xm)\\ \end{bmatrix}$$

  对于$m$维数据的样本集合，相当于有$m$个随机变量来描述其属性特点。计算这$m$维数据两两之间的协方差便得到了一个$m\times m$的协方差矩阵。因此，协方差的具体含义可以理解为计算一组数据各个维度之间的相关性。

  协方差矩阵是实对称矩阵，实对称矩阵有一个重要性质是可以正交对角化，即存在一个正交矩阵U，对$X$作一个正交变换$Y=U^TX$后，使得协方差矩阵$\Sigma$满足

$$\Lambda = U^T\Sigma U$$

这意味着，只要对一组样本数据作一个正交变换，就能使得它变成维度之间两两无关的数据。这使得它在很多工程中成为了重要的理论基础。在下文马氏距离的推导中，就先根据这个原理讲数据变换到一个维度无关的线性空间。

  同时，协方差矩阵还是半正定矩阵，因此$\Sigma$还可做$Cholesky$分解，即

$$\Sigma = L \cdot L^T$$

其中，$L$ 是下三角矩阵，$L^T$ 是它的转置。

马氏距离

  假设单个样本为m维列向量$x_i$，将$n$个样本组合为一个$m \times n$的矩阵$X = (x_1,x_2,\cdots,x_n)$ 。$X$的数据可示例如下

$$\begin{bmatrix} x_{11}& x_{12}& \cdots & x_{1n}\\ x_{21}& x_{22}& \cdots & x_{2n}\\ \vdots &\vdots &&\vdots\\ x_{m1} &x_{m2}& \cdots & x_{mn} \end{bmatrix}$$

对于$X$第$i$个维度的样本均值可表示为$\mu ^{(x)}_i$ 。$\mu^{(x)}$ 是$X$的样本均值向量

$$\mu^{(x)} = (\mu_1^{(x)},\mu_2^{(x)},\cdots,\mu_m^{(x)})^T$$

  则其协方差矩阵可表示为

$$\begin{aligned} \Sigma_X =& E[(X-\mu^{(x)})(X-\mu^{(x)})^T]\\ =& \frac 1 {n-1} \sum_{i=1}^n (x_i -\mu^{(x)}) (x_i-\mu^{(x)})^T \end{aligned}$$

对一组数据，可通过主成分分析等方法，确定其特征向量，按照特征向量进行坐标变换就能得到一个新坐标系下的样本，虽还是同一组样本，但这组样本的各个维度在变换后的坐标系下相互独立。用$F$来表示$X$旋转后的向量组成的矩阵（它们是相同的，不过坐标系不同），$U$表示变换矩阵。于是有

$$F=(f_1,f_2,\cdots , f_m)^T=U^TX$$

旋转后的均值为

$$\mu^{(f)} =(\mu_1^{(f)},\mu_2^{(f)},\cdots,\mu_m^{(f)})^T=U^T\mu^{(x)}$$

得到

$$F-\mu^{(f)}=U^T(X-\mu^{(x)})$$

  由于$F$经过正交变换后维度无关，因此其协方差矩阵是一个由其方差组成的对角矩阵

$$\begin{aligned} E[(F-\mu^{(f)}) (F-\mu^{(f)})^T]=& \begin{bmatrix} \lambda_1& \\ &\lambda_2&\\ && \ddots&\\ &&&& \lambda_m\\ \end{bmatrix}\\ =&E\;\left [ U^T(X-\mu^{(x)})(X-\mu^{(x)})^TU \right] \\ =& U^T \Sigma_X U \end{aligned}$$

经过变换后的$F$是维度无关的，此时它的马氏距离相当于欧式距离。不过在求取欧式距离时，其变量的方差也会影响结果，所以要求标准化后的欧式距离。

$$\begin{aligned} D_F=& \frac {(f_1-\mu^{(f)}_1)} {\lambda_1} +\frac {(f_2-\mu^{(f)}_2)} { \lambda_2} +\cdots +\frac {(f_m-\mu^{(f)}_m)} { \lambda_m} \\ =& (f_1-\mu^{(f)}_1,f_2-\mu^{(f)}_2,\cdots,(f_m-\mu^{(f)}_m) \begin{bmatrix} \frac 1 {\lambda_1}&\\ &\frac 1 {\lambda_2}&\\ && \ddots&\\ &&&\frac 1 {\lambda_m}\\ \end{bmatrix} \begin{pmatrix} f_1-\mu^{(f)}_1\\ f_2-\mu^{(f)}_2\\ \cdots\\ (f_m-\mu^{(f)}_m \end{pmatrix}\\ =&(F-\mu^{(f)})^T(U^T\Sigma_XU)^{-1}(F-\mu^{(f)})\\ =&(X-\mu^{(x)})^TU(U^T\Sigma_X^{-1}U)U^T(X-\mu^{(x)})\\ =&(X-\mu^{(x)})\Sigma_X^{-1}(X-\mu^{(x)})\\ \end{aligned}$$

  通过推导过程可以发现，马氏距离计算中用到协方差矩阵的逆与计算欧氏距离中的标准化有某种关系。事实上马氏距离确实是尺度无关的一种度量，它通过对原数据进行线性变换，得到维度无关的数据之后，再计算其标准化后（去除方差影响）的欧式距离。进行线性变换的目的是去除维度之间相关性的影响。