主成分分析 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算法,如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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

updatedupdated2021-08-112021-08-11