主成分分析
在实践中，我们通常会得到多组不同方面的数据，但是不同的属性之间往往具有相关性，还会有一些噪声。主成分分析 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\) 即可。
核技巧几乎是贯穿整个机器学习的基本方法。这背后的数学原理和前人的宝贵经验比较复杂，这里不做展开。