首先要明白，降维往往是为了在降低计算量的同时，尽量保持原来样本的分布
PCA
对于正交属性空间中的样本点，用超平面对样本进行表达需要满足最近重构性及最大可分性
理论基础
- 基本假设如下
-
，
- 投影变换后得到的新坐标系为
- 对样本进行中心化
-
- 过程推导：
样本点在在新空间的投影为
,若使得个样本在新的空间尽量分开来，则需要使得方差最大，而方差为
，对上述式子采用Lagrange乘子法，则可以得到
因此，仅需要对于协方差阵
进行特征值分解，并对特征值进行排序，选取前
项特征值对应的特征向量构成
伪代码
% INPUT: 样本集D={x_1,x_2,...x_m}; 低维空间维数 d'
对所有样本进行中心化
计算协方差矩阵 XX^T
对协方差阵进行特征值分解
取最大的d'个特征值所对应的特征向量 w_1,w_2,...w_d'
多维缩放(MDS)
理论基础
- 基本假设如下：
- 保证任意两个样本在
- 过程推导
令，表示降维后样本的内积矩阵
假设降维后的样本Z被中心化，即
，故而有
，由上述形式有：
因此，可以知道
从而B可得，对B进行特征值分解，得到
,其中
为特征值从大到小排序构成的对角矩阵，V为对应的特征向量矩阵，假设特征值中仅有
个非零值，则Z可以表达为
， 但是实际中不必如此严格，只需要降维之后彼此距离与原始空间距离尽可能近似，而不必严格相等，此时可以直接选取
个最大特征值构成的对角阵，计算对应的Z
伪代码
% INPUT: 距离矩阵D，其元素为dist_{ij}为x_i到x_j的距离；低维空间的维数$d'$
计算dist_{i.},dist_{.j},dist_{..}
计算B
对B进行特征值分解
取\lambda中前d'个最大特征值和对应的特征向量矩阵V
输出: V\lambda^{0.5}
参考自 周志华 《机器学习》
