PCA.md

主成分分析(PCA)

一、介绍

主成分分析(Principal Component Analysis, PCA)是一种最常用的降维技术，它属于无监督的线性降维算法，常用于高维数据的预处理。

二、原理

所谓线性降维就是降维变换是一个线性变换，即x^new=Px，其中P是一个矩阵。对降维后数据点做出不同的假设，即得到不同的P。

Notation: 采样得到x∈R^d维数据，共n个样本，构成d行n列矩阵X∈R^d×n。将d维向量降为k维，PCA的做法是选择k个归一化正交基，张成一个K维超平面W， 使得数据投影到这个k维超平面之后，样本点新坐标W^Tx能尽可能的分开(方差最大化)，表述成优化问题即：

用拉格朗日乘子法求解，得到最优解W*为协方差矩阵XX^T前k个最大的特征值对应特征向量作为列向量组成的矩阵，2.1和2.2给出两种等价的PCA算法。

2.1 协方差矩阵特征值分解

设有n条d维数据，构成d行n列矩阵X

1. 将X的每一行(每一个特征)减去该行均值(中心化)
2. 求出协方差矩阵S = 1/mXX^T
3. 对协方差矩阵进行特征值分解S = QAQ^T
4. 取前k个最大特征值对应的特征向量按列构成矩阵Q_k
5. P = Q_k^TX即为降维到k维后的数据

降维后数据的协方差矩阵为PP^T = Q_k^TX X^TQ_k = A_k， 即新数据的协方差矩阵是一个k维对角阵，且对角元素为对角阵A的最大k个特征值。

2.2 奇异值分解

设有n条d维数据，构成d行n列矩阵X

1. 将X的每一行(每一个特征)减去该行均值(中心化)
2. 对X进行奇异值分解，X = U∑V^T，取X的最大k个奇异值对应的左奇异向量构成矩阵U_k
3. P = U_k^TX即为降维到k维后的数据

可以证明降维后的数据协方差矩阵为对角阵，对角元素为最大k个奇异值的平方。2.1和2.2的做法是完全等价的，相比而言奇异值分解更简洁， 使用右奇异矩阵可以对列进行降维，使用左奇异矩阵可以对行进行降维。

三 效果

可以赋予PCA一个几何解释，即朝着方差最大的k个正交方向上“投影“。但要注意的是，PCA是一种无监督的数据降维方法，在降维的过程中没有考虑数据的标签。 虽然方差较大的k个正交方向在大多数时候都能保存数据的信息，丢弃的是方差较小的噪声，但也不排除对于某些数据(见下图)，最能分辨数据标签的特征的方差较小，而在投影过程中，这些特征被抹去了， 进而导致数据后续分类效果较差。所以，在使用PCA的时候，需要比较降维前后学习器的性能，若性能有所提高，则认为降维起到了作用。

四、总结

PCA的算法可以基于两个性质进行等价推导，一是前面介绍的最大可分性，即投影到超平面后新坐标的方差最大，这是比较常见的推导PCA算法的假设。还有一种是最近重构性，即样本点到这个超平面的距离最近， 表述成优化问题的形式即：

由于Frobenius范数满足||A||_F² = trace(A^TA)，将Frobenius范数写成矩阵的迹的形式可得与最大可分性同样的优化形式，说明了这两种不同表述的等价性。

五、参考资料

[1] 周志华. 机器学习 : = Machine learning[M]. 清华大学出版社, 2016.(第十章)