主成分分析

在实践中,我们通常会得到多组不同方面的数据,但是不同的属性之间往往具有相关性,还会有一些噪声。主成分分析 PCA(Principal Component Analysis) 就是一种解决问题的方法。其主要思想是,变换属性选取的一组基,让新的基之间没有相关性。

感性分析一下我们的要求:既然是相关性,容易想到先计算出各属性之间的相关系数矩阵,或者协方差矩阵 \(\Sigma\)。相关系数我们要得到原属性的一组新基,其实就是要找到一个正交矩阵 \(W\),使得 \(W^T\Sigma W\) 的结果是一个对角阵,不妨记作 \(\Lambda\)。所以,\(\Sigma=W\Lambda W^T\)

熟不熟悉?这玩意就是特征值分解。

说得太快了。我们慢慢来。

推导

假设属性数量是 \(n\),样本数量是 \(m\)。我们把第 \(j\) 个样本用向量 \(x_j=(x_j^{(1)},...,x_j^{(n)})^T\) 表示,\(x_j^{(i)}\) 代表第 \(j\) 个样本的第 \(i\) 个属性。把所有样本组成一个矩阵:\(X=[x_1\ ...\ x_m]\)

在主成分分析中,我们把原属性的一些线性组合称作成分。根据线性代数的一些基础知识,如果我们选择 \(n\) 个线性无关的成分,我们可以从这些成分反推出所有的属性。

而当我们选取的成分合适时,一些原本隐藏的信息就会浮现出来,也就是数据的结构会变得清晰。因为原数据可能会有噪声和冗余两个问题:

  • 噪声:有些数据可能只是无关的,或是测量时引入的随机误差。
  • 冗余:多个属性可能高度相关。比如西瓜的质量和体积,占用了两个数据却完全起不到两个数据的作用。

怎么选取恰当的成分呢?主成分分析有三个假设:

  • 所有的相关性都是线性的。
  • 样本在成分上的投影产生的方差越大,这个成分蕴含的信息就越多。反之,方差越小,越可能是一些噪声。
  • 选取的成分之间不应该有冗余,也就是协方差(或相关系数)为 0。

关于方差和协方差,可以去看我的概率论笔记

另外,我们规定成分之间是正交的。这既是为了计算方便,也同时能够最大限度地保存结构信息。

在这样的假设下,我们的主成分可以很自然地看作是标准基的一个旋转(不能放缩,因为这样会影响原有数据的方差)。不妨将主成分记作 \(p_1,p_2,...,p_n\),则我们可以用矩阵 \(P=[p_1\ p_2\ ... \ p_n]\) 来表示这个旋转。原先的一个样本 \(x\),在新的成分下就可以表示成 \(P^Tx\)。整个输入矩阵也可以表示为 \(P^TX\)

我们希望在新的成分下,数据的总方差尽可能大。也就是说,\(P^TX\) 的方差尽可能大。

有一种快速的方法来计算方差:首先把 \(X\) 中心化,每个数据分别减去那一行的均值,也就是把每个属性的均值设为 0。这样,一个属性的方差就只需要计算那一行的平方均值,而两者之间的协方差也只需要计算两行的数量积。总地来说,协方差矩阵 \(\Sigma=\frac{1}{m-1}XX^T\)\(\frac{1}{m-1}\) 的系数可以忽略。

我们要让方差尽可能大,就是让协方差矩阵的对角线尽可能大。线性代数中,对角线和被叫作迹(trace)。即:

\[ \begin{aligned} &\operatorname*{argmax}_P \operatorname{tr}(P^TXX^TP)\\ \text{s.t. } & P^TP=I \end{aligned} \]

运用拉格朗日乘子法,设向量 \(\lambda=(\lambda^{(1)},...,\lambda^{(n)})^T\),写出拉格朗日函数:

\[ L(P)=\sum_{i=1}^np_i^TXX^Tp_i+\sum_{i=1}^n\lambda^{(i)}(1-p_i^Tp_i) \]

对向量 \(p_i\) 求各个偏导置 0,我们得到:\(2XX^Tp_i=2\lambda^{(i)}p_i\)。欸,说明 \(p_i\) 就是 \(XX^T\) 的特征向量。

接下来就轻松多了。根据谱定理(建议搜索,大体证明基于对维度归纳),像 \(XX^T\) 这样的对称矩阵,一定存在一组规范正交的特征向量,刚好就是这里的 \(p_i\)

另一方面,由特征值分解知道,\(XX^T=P\Lambda P^T\),所以在新成分下,\(P^TX\) 对应的协方差(或相关系数)矩阵是 \(P^TXX^TP=\Lambda\),是一个对角阵。很幸运,我们同时实现了方差最大(信息最多)以及协方差为 0(冗余最少)。

剩下的就是噪声了。我们已经假定方差较小的是噪声,所以我们可以将特征值从大到小排序,只把特征值较大的几个成分作为有效的主成分,这样就起到了降噪和降维的作用。

还有另一些推导方法,可以参考周志华的西瓜书。

分析

协方差还是相关系数

在概率论里我提过,相关系数就是标准化之后的协方差。所以要看有没有标准化的必要,换句话说,绝对值大小到底重不重要。

比如你做的是成绩分析,那么 150 分的学科就是比 100 分关键,这时选择协方差就是明智的。

但大多数情况下,各个属性之间的量纲都不同,更难以有精确的比较关系,这时相关系数就是很好的选择。

特征选择

在主成分分析中,我们可以得到一些关键的主成分。容易想到,离主成分比较近的特征应该会比较重要,而离主成分远的特征则反之。

既然我们是用一个特征向量 \(p\) 表示的主成分,我们可以把 \(p\) 在各个特征坐标轴上的分量当作各个特征对主成分的贡献,以此达到特征选择的效果。

核技巧

前面提到过,主成分分析的一个重要假设是线性性。但是真实数据往往不是线性的。如果我们能进行一个预处理,把每一个 \(x\) 映射为 \(\varphi(x)\),就可以处理非线性的数据。

但是 \(\varphi\) 的人工选择几乎是不可能完成的。不过,容易发现,在这个问题中,我们只需要计算 \(XX^T\),也就是 \(\varphi(x)^T\varphi(y)\)。我们可以定义核函数 \(\kappa(x,y)=\varphi(x)^T\varphi(y)\)。不需要指定 \(\varphi\) 是什么,只需要根据经验指定 \(\kappa\) 即可。

核技巧几乎是贯穿整个机器学习的基本方法。这背后的数学原理和前人的宝贵经验比较复杂,这里不做展开。