机器学习算法
机器学习算法06-主成分分析(PCA)
主成分分析基于本科线性代数中特征分解的思想,通过方差衡量不同方向所包含的信息量,从而实现特征压缩与降维。“分清主要矛盾与次要矛盾”,某种意义上正是 PCA 所做的事情。
本文思维导图如下。
1. 主成分与降维
1.1 宝山某大专
临近开学,宝山某大专组织了一次调研问卷。一共采访了 12 位学生,我们想研究同学的学习状态与日常生活安排之间的联系,于是记录了他们一周的生活数据并取平均,做出了下面这个表格:
| 学生 | 每日学习时间 h | 每周图书馆次数 | 每日睡眠 h | 每周运动次数 | 每日手机娱乐 h | 每日咖啡杯数 |
|---|---|---|---|---|---|---|
| 1 | 7.2 | 6 | 7.8 | 4 | 1.4 | 1 |
| 2 | 6.8 | 5 | 7.5 | 4 | 1.8 | 1 |
| 3 | 6.1 | 5 | 7.1 | 3 | 2.0 | 2 |
| 4 | 5.7 | 4 | 7.3 | 3 | 2.4 | 1 |
| 5 | 5.2 | 4 | 6.8 | 2 | 2.8 | 2 |
| 6 | 4.8 | 3 | 6.5 | 2 | 3.2 | 2 |
| 7 | 4.2 | 3 | 6.2 | 2 | 3.8 | 3 |
| 8 | 3.8 | 2 | 6.0 | 1 | 4.1 | 3 |
| 9 | 3.2 | 2 | 5.8 | 1 | 4.8 | 3 |
| 10 | 2.8 | 1 | 5.5 | 1 | 5.2 | 4 |
| 11 | 2.3 | 1 | 5.2 | 0 | 5.8 | 4 |
| 12 | 1.9 | 0 | 5.0 | 0 | 6.3 | 4 |
喝咖啡是否大概率是因为通宵达旦学习,还是因为熬夜刷手机?去图书馆次数多,就真的说明学习时间更长吗?面对这样一个多变量问题,我们很难只靠肉眼直接看出变量之间的整体关系。
没有头绪的时候,不妨先把问题写成数学形式。设第 $i$ 位学生的数据为一个六维向量:
其中六个特征分别为:
整个数据集可以写为:
每个特征的均值组成均值向量:
1.2 两个变量的共同变化
如果只研究一个变量,例如每日学习时间,可以用方差描述不同学生之间的差异:
如果同时观察两个变量 $x$ 和 $y$,想知道它们究竟是倾向于一起增加、一起减少,还是没有明显的共同变化趋势,就可以引入协方差:
对于有限样本,常用样本协方差:
这里使用 $n-1$ 而不是 $n$,是因为我们用样本均值估计总体均值以后损失了一个自由度。
如果把当前 12 位学生本身就视为我们研究的完整总体,也可以写成:
那么协方差究竟揭示了什么?
- $\operatorname{Cov}(x,y)>0$:两个变量倾向于同增同减,即正相关;
- $\operatorname{Cov}(x,y)<0$:一个增加时另一个倾向于减少,即负相关;
- $\operatorname{Cov}(x,y)\approx 0$:两个变量之间没有明显的线性共同变化趋势。
于是,我们可以计算六个变量两两之间的关系,并组成一个协方差矩阵:
它是一个 $6\times6$ 的对称矩阵。
1.3 标准化
这里马上会遇到一个问题。
我们的六个变量单位并不相同:学习时间是小时,图书馆和运动是次数,睡眠和手机娱乐是小时,咖啡则是杯数。不同变量的数值尺度如果相差很大,那么原始协方差就会受到单位的明显影响。
例如,一个数值本身在 $10000$ 左右的变量,变化 $100$ 可能只是一个很小的相对波动;但对于一个本身只有 $0.1$ 左右的变量而言,变化 $100$ 显然完全不是一个量级的问题。
如果直接使用原始协方差矩阵,数值尺度大的变量很可能仅仅因为单位更大,就在 PCA 中占据更高权重。
因此,对于这种不同量纲的数据,通常首先进行标准化:
其中 $x_{ij}$ 表示第 $i$ 个学生的第 $j$ 个特征,$\bar x_j$ 和 $s_j$ 分别表示第 $j$ 个特征的均值和标准差。
标准化以后,每个变量都满足:
这样,不同变量就被放到了同一个尺度上。
对标准化后的数据计算 Pearson 相关系数,可以得到:
| 学习 | 图书馆 | 睡眠 | 运动 | 手机 | 咖啡 | |
|---|---|---|---|---|---|---|
| 学习 | 1.000 | 0.986 | 0.994 | 0.980 | -0.993 | -0.953 |
| 图书馆 | 0.986 | 1.000 | 0.978 | 0.958 | -0.983 | -0.921 |
| 睡眠 | 0.994 | 0.978 | 1.000 | 0.976 | -0.990 | -0.972 |
| 运动 | 0.980 | 0.958 | 0.976 | 1.000 | -0.964 | -0.932 |
| 手机 | -0.993 | -0.983 | -0.990 | -0.964 | 1.000 | 0.949 |
| 咖啡 | -0.953 | -0.921 | -0.972 | -0.932 | 0.949 | 1.000 |
这时,最开始提出的一些问题已经能够得到一些初步答案。
喝咖啡是因为学习还是刷手机?
在这 12 位学生的数据中:
而
同时
因此,在这组数据中,咖啡摄入较多通常伴随着更长的手机娱乐时间、更少的睡眠以及更少的学习时间。
当然,这里描述的仅仅是相关关系,而不是因果关系。我们不能仅凭这些数据就得出“刷手机导致喝咖啡”或者“喝咖啡导致睡眠减少”这样的结论。
去图书馆次数多,就真的学习得多吗?
这组数据中:
是一个非常强的正相关。
所以至少对于当前这 12 位学生而言,图书馆次数确实能够较好地反映学习时间。
1.4 PCA?
对于六个变量而言,我们还可以勉强观察相关系数矩阵。
但如果现在有 60 个变量,那么变量之间两两关系的数量将达到:
此时,再试图逐个分析所有变量之间的关系就变得非常困难。
重新观察刚才的相关系数矩阵,可以发现一个很明显的现象:
学习时间、图书馆次数、睡眠和运动大体一起增加,而手机娱乐和咖啡摄入则大体向相反方向变化。
也就是说,表面上我们观察了六个变量,但它们并不是六个完全独立的变化方向。多个变量之间可能存在大量重复信息,它们很可能共同反映某个更低维度的潜在状态。
PCA 所做的事情,正是寻找一个新的坐标系,把原来彼此相关的多个变量重新组合成少数几个互相正交的新变量,并尽可能保留原始数据中的变化信息。
这些新的变量就称为主成分(Principal Components)。
2. PCA
2.1 第一主成分
设标准化后的学生数据记为随机向量 $z\in\mathbb{R}^6$ ,由于数据zscore化后期望为0 ($E[z]=0$)。协方差矩阵可简写成 $\Sigma=E[zz^T]$
现在我们希望在六维空间中寻找一个方向:
并把原始数据投影到这个方向上,得到一个新的标量特征:
PCA 希望这个新的特征尽可能保留原始数据中的变化,因此一个自然的想法就是:让投影后的方差尽可能大。
由于 $E[z]=0$,所以:
因此,我们希望寻找一个方向 $w$,使 $w^T\Sigma w$ 尽可能大。如果完全不限制 $w$ 的长度,只需要不断把 $w$ 放大,目标函数就可以无限增大。
因此,我们真正想比较的应该只是不同的“方向”,而不是向量的长度。于是规定 $w$ 为单位向量:
这样,寻找第一主成分就可以写成下面这个约束优化问题:
也就是说,PCA 寻找第一主成分的本质,就是在所有单位方向中寻找一个方向,使数据投影到该方向之后的方差最大。
这个最优方向记为 $w_1$ 它就是第一主成分。
拉格朗日乘子法求解优化问题:
分别对 $w$ 和 $\lambda$ 求偏导。对于 $w$,有:
令其为 0:
于是得到:
这正是特征方程。也就是说,PCA 中满足最优条件的方向 $w$,实际上就是协方差矩阵 $\Sigma$ 的特征向量,而对应的 $\lambda$ 则是这个特征向量对应的特征值。在等式两边左乘 $w^T$,可以得到:
而前面已经知道:
特征值 $\lambda$ 就是数据沿对应特征向量方向投影以后所具有的方差。
于是,原来的优化问题:
就等价于寻找协方差矩阵中最大的特征值以及它对应的特征向量。如果把协方差矩阵的特征值按照从大到小排列:$\lambda_1
\geq
\lambda_2
\geq
\cdots
\geq
\lambda_6,$
并把对应的单位特征向量记为:$w_1,w_2,\dots,w_6$
那么最大特征值 $\lambda_1$ 对应的特征向量 $w_1$,就是第一主成分方向。
第一主成分可以写成
2.2 第二主成分与后续主成分
找到第一主成分以后,还可以继续寻找第二个方向。
但第二个方向不能再次选择第一主成分,否则得到的仍然是相同的信息。因此,需要增加一个新的限制:
也就是说,第二主成分必须与第一主成分正交。
在这个条件下,我们继续寻找投影方差最大的方向:
最终得到的 $w_2$,正是协方差矩阵第二大特征值 $\lambda_2$ 所对应的特征向量。
于是第二主成分写为:
同样地继续下去,可以得到:
由于协方差矩阵 $\Sigma$ 是一个实对称矩阵,因此它的特征向量可以选取为一组标准正交基,即:
并且:
因此,不同主成分之间在线性意义下也是互不相关的。
例如对于两个主成分 $PC_i$ 和 $PC_j$,有:
利用:
可以得到:
因此:
第一条轴解释最多的数据变化问题,第二条轴解释剩余变化中最多的部分,第三条轴继续解释剩余变化,以此类推。如果前几个主成分已经能够解释绝大多数方差,那么后面的主成分就可以舍弃,从而实现特征降维。
2.3 方差贡献率
前面已经得到,第 $i$ 个主成分对应的特征值满足:
因此,每一个特征值都代表对应主成分所能够解释的方差大小。那么所有主成分所包含的总方差就是:$
\sum_{i=1}^{6}\lambda_i.
$
于是,第 $i$ 个主成分所解释的方差比例可以定义为 $\eta_i=\frac{\lambda_i}{\sum_{j=1}^{6}\lambda_j}$
这个量称为方差贡献率(explained variance ratio)。
它表示第 $i$ 个主成分解释了原始数据总变化中的多少比例。
例如,如果:
就意味着第一主成分一个方向已经解释了原始数据中 $80\%$ 的总体方差。
如果希望保留前 $k$ 个主成分,则可以进一步计算累计方差贡献率:
例如,如果:
说明只保留前两个主成分,就已经能够解释原数据中 $95\%$ 的总体变化。
这时候,就可以考虑把原来的六维数据压缩为二维。
2.4 为什么标准化以后特征值之和等于 6?
这里还有一个比较漂亮的线性代数关系。
对于任意方阵,矩阵的迹等于其全部特征值之和:
而协方差矩阵的对角线元素分别就是每一个变量自己的方差:
由于我们已经对六个变量进行了标准化,所以每个变量都有:
因此协方差矩阵的迹为:
于是:
这意味着,在标准化后的六维数据中,总方差正好等于特征数量,也就是 6。
因此,第 $i$ 个主成分的方差贡献率也可以直接写成:
对前面的 12 位学生数据进行 PCA,可以得到六个特征值约为:
可以先检查一下:
因此,第一主成分的方差贡献率为:
第二主成分的贡献率为:
第三主成分的贡献率约为:
所以前两个主成分的累计贡献率已经达到:
也就是说,原本需要六个变量描述的学生生活状态,仅仅用两个新的变量,就已经能够保留大约 $98.89\%$ 的总体变化。
更加夸张的是,第一主成分一个方向就已经解释了约 $97.4\%$ 的数据变化。
这说明我们的六个原始变量之间存在极其强烈的相关性。
虽然表面上它们分别是:
但在这组数据中,它们实际上大体都沿着同一个潜在方向变化。