主成分分析 PCA 算法

PCA是最常用的一种降维方法(非监督),可以用于提取数据的主要特征分量。

其数学推导可以从最大可分性和最近重构性进行,前者的优化条件为划分后方差最大,后者的优化条件为点到划分平面距离最小。

从基础线性代数知识的角度,可以知道不同的基可以对同样一组数据给出不同表示,如果基的数量少于向量本身的数量,则可以达到降维效果

那么,如何选择基才是最有的降维方案呢?可以认为,投影后的投影值尽可能分散,因为如果重叠就会有样本消失。也可以理解为熵越大所含信息越多

数学推导

PCA本质上是将方差最大的方向作为主要特征,并且在各个正交方向上将数据“离相关”,也就是让它们在不同正交方向上没有相关性。那么显然,推导PCA算法的关键就在于用方差定义样本间距,方差越大那么样本分布越稀疏。

定义方差:

\[\operatorname{Var}(a)=\frac{1}{m} \sum_{i=1}^{m}\left(a_{i}-\mu\right)^{2} \tag{1} \]

为了方便处理,将每个变量均值化为\(0\)​,即\(\mu = 0\)

\[\operatorname{Var}(a)=\frac{1}{m} \sum_{i=1}^{m} a_{i}^{2} \tag{2} \]

现在问题可以表述为寻找一个一维基,使得所有数据变换为这个基上的坐标显示后,方差值最大

将这个思想拓展到多维度空间中,就需要用协方差进行约束。

协方差:可以表示两个向量的相关性,公式:

\[\operatorname{Cov}(a, b)=\frac{1}{m-1} \sum_{i=1}^{m}\left(a_{i}-\mu_{a}\right)\left(b_{i}-\mu_{b}\right) \tag{3} \]

由于均值为\(0\)​,则公式\(3\)可以简化为:

\[\operatorname{Cov}(a, b)=\frac{1}{m} \sum_{i=1}^{m} a_{i} b_{i} \tag{4} \]

协方差为 \(0\)的时候,两个变量线性不相关,至此,就得到了降维问题的优化目标:

将一组\(N\)维向量降为\(K\)维,其目标是选择\(K\)​​个单位正交基,使得原始数据变换到这组基上后,各变量两两间协方差为\( 0\),而变量方差则尽可能大(在正交的约束下,取最大的 \(K\) 个方差)。

可以看出,这个优化目标和变量内方差、变量间协方差有着密切关系。假设只有\(a,b\)​两个向量,将其按行组成矩阵:

$$ X=\left(\begin{array}{llll} a_{1} & a_{2} & \cdots & a_{m} \\ b_{1} & b_{2} & \cdots & b_{m} \end{array}\right) $$
$$ \frac{1}{m} X X^{\top}=\left(\begin{array}{cc} \frac{1}{m} \sum_{i=1}^{m} a_{i}^{2} & \frac{1}{m} \sum_{i=1}^{m} a_{i} b_{i} \\ \frac{1}{m} \sum_{i=1}^{m} a_{i} b_{i} & \frac{1}{m} \sum_{i=1}^{m} b_{i}^{2} \end{array}\right)=\left(\begin{array}{ll} \operatorname{Cov}(a, a) & \operatorname{Cov}(a, b) \\ \operatorname{Cov}(b, a) & \operatorname{Cov}(b, b) \end{array}\right) $$

这样可以看到在矩阵对角线上的是两个变量的方差,而其他元素是两个变量 \(a\), \(b\) 的协方差。他们被统一到一个矩阵中。

可以推广成为下述theorm:

设我们有 \(\mathrm{m}\)\(\mathrm{n}\) 维数据记录,将其排列成矩阵 \(X_{n, m}\), 设 \(C=\frac{1}{m} X X^{T}\), 则 \(\mathrm{C}\) 是一个对称矩 阵,其对角线分别对应各个变量的方差,而第 \(\mathrm{i}\)\(\mathrm{j}\) 列和 \(\mathrm{j}\)\(\mathrm{i}\) 列元素相同,表示 \(\mathrm{i}\)\(\mathrm{j}\)​ 两个变量的协方差。

设原始数据矩阵 \(X\) 对应的协方差矩阵为 \(C\), 而 \(P\) 是一组基按行组成的矩阵,\(Y\)\(X\)​ 对 \(P\)做机变换后的数据矩阵,那么\(Y=PX\),设\(Y\)​​的协方差矩阵为\(D\)​。则:

$$ \begin{aligned} D &=\frac{1}{m} Y Y^{T} \\ &=\frac{1}{m}(P X)(P X)^{T} \\ &=\frac{1}{m} P X X^{T} P^{T} \\ &=P\left(\frac{1}{m} X X^{T}\right) P^{T} \\ &=P C P^{T} \end{aligned} $$

优化目标变成了寻找一个矩阵 P,满足 \(P C P^{T}\)是一个对角矩阵,并且对角元素按从大到小依次排列,那么 P 的前 K 行就是要寻找的基,用 P 的前 K 行组成的矩阵乘以 X 就使得 X 从 N 维降到了 K 维并满足上述优化条件

设协方差矩阵\(C\)的单位特征向量为\(e_1, e_2, \dots, e_n\),将其组成一个行向量 $$ E=\left(e_{1}, e_{2}, \cdots, e_{n}\right)

\[则可知:

\]

E^{T} C E=\Lambda=\left(\begin{array}{llll} \lambda_{1} & & & \ & \lambda_{2} & & \ & & \ddots & \ & & & \lambda_{n} \end{array}\right)

\[其中$\lambda$为各特征向量对应的特征值,因此可知需要的矩阵$P=E^T$ P 是协方差矩阵的特征向量单位化后按行排列出的矩阵,其中每一行都是 C 的一个特征向量。如果设 $P$ 按照 $\Lambda$​ 中特征值的从大到小,将特征向量从上到下排列,则用 $P$ 的前 $K$ 行组成的矩阵乘以原始数据矩阵 $X$,就得到了我们需要的降维后的数据矩阵 $Y$​。 ## 代码实例 使用sklearn中PCA算法,如下 ```python import matplotlib.pyplot as plt from sklearn.decomposition import PCA from sklearn.datasets import load_iris data = load_iris() y = data.target x = data.data pca = PCA(n_components=2) reduced_x = pca.fit_transform(x) red_x, red_y = [], [] blue_x, blue_y = [], [] green_x, green_y = [], [] for i in range(len(reduced_x)): if y[i] == 0: red_x.append(reduced_x[i][0]) red_y.append(reduced_x[i][1]) elif y[i] == 1: blue_x.append(reduced_x[i][0]) blue_y.append(reduced_x[i][0]) else: green_x.append(reduced_x[i][0]) green_y.append(reduced_x[i][1]) plt.scatter(red_x,red_y,c='r',marker='x') plt.scatter(blue_x,blue_y,c='b',marker='D') plt.scatter(green_x,green_y,c='g',marker='.') plt.show() ``` ![image-20210811165148351](https://jczhangimg.oss-cn-hongkong.aliyuncs.com/image-20210811165148351.png) \]

updatedupdated2022-01-302022-01-30