降维方法综述

2019-05-29 本文已影响0人长安逸魂

首先要明白，降维往往是为了在降低计算量的同时，尽量保持原来样本的分布

PCA

对于正交属性空间中的样本点，用超平面对样本进行表达需要满足最近重构性及最大可分性

基本假设如下
- $x_i\in R^d, x_i' \in R^{d'}$ ， $W\in R^{d \times d'}$ $x = [x_1, x_2, ..., x_m]$
- 投影变换后得到的新坐标系为 $\{\omega_1,\omega_2,...,\omega_{d'}\}$
- 对样本进行中心化 $x_i = \frac{1}{m}\sum^m_{i=1}x_i$
过程推导：
样本点 $x_i$ 在在新空间的投影为 $W^Tx_i$ ,若使得个样本在新的空间尽量分开来，则需要使得方差最大，而方差为
$\max_{W}tr(W^TXX^TW)$ $s.t. W^TW=I$ ，对上述式子采用Lagrange乘子法，则可以得到
$W^TXX^TW - \lambda(W^TW-I)=0 \longrightarrow XX^TW=\lambda W$ 因此，仅需要对于协方差阵 $XX^T$ 进行特征值分解，并对特征值进行排序，选取前 $d'$ 项特征值对应的特征向量构成 $W=(\omega_1,\omega_2,...,\omega_{d'})$

% INPUT: 样本集D={x_1,x_2,...x_m}; 低维空间维数 d' 
对所有样本进行中心化
计算协方差矩阵 XX^T
对协方差阵进行特征值分解
取最大的d'个特征值所对应的特征向量 w_1,w_2,...w_d'

基本假设如下：
- $X\in R^{d\times m}, Z\in R^{d' \times m}$
- 保证任意两个样本在 $d'$ 维的欧式距离等于在原空间的距离，即 $||z_i-z_j||=dist_{ij}$
过程推导
令 $B = Z^TZ\in R^{m\times m}$ ，表示降维后样本的内积矩阵
$dist_{ij}^2=||z_i||^2+||z_j||^2-2z_i^Tz_j=b_{ii}+b_{jj}-2b_{ij}$ 假设降维后的样本Z被中心化，即 $\sum^m_{i=1}z_i=0$ ，故而有 $\sum^m_{i=1}b_{ij}=\sum^{m}_{j=1}b_{ij}=0$ ，由上述形式有：
$\sum^m_{i=1}dist_{ij}^2=tr(B)+mb_{jj}$ $\sum_{j=1}^mdist_{ij}^2=tr(B)+mb_{ii}$ $\sum^{m}_{j=1}\sum^{m}_{i=1}dist_{ij}^2=2mtr(B)$ 因此，可以知道 $b_{ij}=-0.5 (dist_{ij}^2-dist_{i.}^2-dist_{.j}^2+dist_{..}^2)$ 从而B可得，对B进行特征值分解，得到 $B=V\lambda V^T$ ,其中 $\lambda$ 为特征值从大到小排序构成的对角矩阵，V为对应的特征向量矩阵，假设特征值中仅有 $d^*$ 个非零值，则Z可以表达为 $Z=\lambda_*^{0.5}V_*^T\in R^{d^*\times m}$ ，但是实际中不必如此严格，只需要降维之后彼此距离与原始空间距离尽可能近似，而不必严格相等，此时可以直接选取 $d''<<d$ 个最大特征值构成的对角阵，计算对应的Z

% INPUT: 距离矩阵D，其元素为dist_{ij}为x_i到x_j的距离；低维空间的维数$d'$
计算dist_{i.},dist_{.j},dist_{..}
计算B
对B进行特征值分解
取\lambda中前d'个最大特征值和对应的特征向量矩阵V
输出: V\lambda^{0.5}

参考自周志华《机器学习》