3月机器学习在线学习班第17课笔记part1--PCA

机器学习

---

PCA

主成分分析法（PCA，Principal component analysis）,它是一种对数据进行分析的技术，最重要的应用是对原有数据进行简化。这种方法可以有效的找出数据中最主要的元素和结构，去除噪声和冗余，将原有的复杂数据姜维，揭示隐藏在复杂数据背后的简单结构。它的特点是简单，而且无参数限制。

一个简单的实例

如下图所示，这是一个理想弹簧运动规律的测定实验。假设球是连接在一个无质量无摩擦的弹簧之上的，从平衡位置沿着x轴拉开一定的距离然后释放。

对于一个具有先验知识的实验者来说，这个实验室非常容易的。求得运动只是发生在x轴，只需要记录下x轴的运动序列并加以分析即可。但是，在真实世界中，对于第一次试验的探索者来说，是不可能进行这样的假设的。那么，一般说来，必须记录下球的三维位置$(x_0,y_0,z_0)$.这一点可以通过在不同角度放置三个摄像机来实现（如图所示）。假设以200hz的频率拍摄画面，就可以得到球在空间中的运动序列。这是哪个摄像机的角度可以能不是正交的。事实上，真实世界中也并没有所谓的${x,y,z}$轴，每个摄像机记录下的都是一个二维图像，在其自己的空间坐标系，球的空间位置是由一组二维坐标记录的：$[(x_A,y_A),(x_B,y_B),(x_C,y_C)]$。怎样从这些数据中得到球是沿着某个轴运动的规律呢？怎样将实验数据中的冗余变量剔除，划归到这个潜在的轴上呢？
上面提到的两个问题就是PCA方法的目标。PCA主成分分析法是解决此类问题的一个有力的武器。

线性代数：基变换

从线性代数的角度去看，PCA的目标就是使用另一组基去重新描述已得到的数据空间。而新的基药能够尽量揭示原有的数据间的关系。所谓的基变换是针对一开始定义的标准正交基而言的。上面例子中的标准正交基即为3个摄像机的屏幕坐标（向上和向右方向作为基准）。标准正交基表现了数据观测的一般方式（获取数据的一个视角）。
那么，如何找到另外一组基：是标准正交基的线性组合而且能够更好的表示数据集呢？为解决这个问题，我们需要问：怎样才是“更好的表示”？
在线性系统中，所谓的"混乱数据"包含以下三个成分：噪声、旋转以及冗余。我们从数学上来解释这三个成分。

噪声和旋转

噪声对数据的影响是巨大的，如果不能够对噪声进行区分，就不可能抽取数据中有用的信息，噪声的衡量方式有很多种，最常见的定义是信噪比（signal-to-noise ratio）:

$$SNR = \frac{\sigma_{signal}^2}{\sigma_{noise}^2}$$
这里假设变化较大的信息被认为是信号，变化较小的则是噪声，而变化的大小则是由方差来描述的。也就是说：较高的信噪比表示数据的准确度较高，较低的信噪比表示数据中的噪声成分较多。

（a）图是摄像机A的采集数据。图中两条黑色垂直直线表示一组正交基的方向（原始的标准正交基即为x,y轴）。$\sigma_{signal}^2$即为采样点在长线方向上分布的方差，$\sigma_{noise}^2$是采样点在短线上分布的方差。将标准正交基旋转至这一组黑色垂直直线代表的正交基上，可以使得信噪比SNR最大。

冗余

有时候在实验中引入了一些不必要的变量，可能有两种情况：1）改变量对结果没有影响；2）该变量可以用其他变量表示，从而造成数据冗余。

如上图所示，它揭示了两个观测变量之间的关系。(a)图所示的情况时低冗余的，从统计学上说，这两个观测变量是相互独立的，他们之间的信息没有冗余。而相反的极端情况如图(c)，两个变量高度相关，完全可以用一个变量来表示（$r_2 = k r_1$）。这也就是PCA中“降维”思想的来源。

推导过程

对于包含$n$个特征的$m$个样本，将每个样本写成行向量，得到$m \times n$的矩阵A，即：

取单位向量$u$(即$u$的模为1)，计算$Au$的值：

对于得到的向量$Au$,求该向量的方差。在计算中，我们假定$Au$是去均值化的（即$Au$的均值为0，可事先对矩阵A加以处理，即对每个特征维，都减掉该维的平均值，然后将不同维的数据范围归一化到同一范围，方法一般是除以最大值）。

令方差为$\lambda$(一维变量)，则得到：

$$u^TA^TAu = \lambda \Rightarrow uu^TA^TAu = u\lambda \Rightarrow A^TAu = \lambda u$$
可以看到，在满足条件（当A中的列向量都是去均值化）的前提下，$A^TA$是矩阵$A$的协方差矩阵。更进一步，根据上式可知：$u$是矩阵$A^TA$的一个特征向量，对应的特征值$\lambda$的大小即为矩阵$A$在向量$u$的方向上的投影$Au$的方差。这很好理解，根据上式，$Au$的方差即为$\lambda$。

在第三课的时候有一个结论：实对阵矩阵的不同特征值对应的特征向量一定是正交的。那么，放在我们这里，协方差矩阵$A^TA$是实对称阵，它的不同特征值对应的特征向量一定是正交。这就是为什么协方差矩阵得到的特征向量可以作为新的正交基的原因。我们通过对特征值大小排序，即可得到对应的特征向量（基）的排序，表征的是某一个基在这一组基当中的重要程度。

PCA的优势和不足

优势：

1. PCA技术的一大好处是对数据进行降维的处理。PCA中使用的降维思想，即是将特征值排序后较小的特征值对应的特征向量去掉（因为其重要程度较小）。用最大的前$k$个特征向量（基）构成的特征空间来表征原有的$n$维特征空间（$k \leq n$）。可以达到降维从而简化模型或是对数据进行压缩的效果。同时最大程度的保持了原有数据的信息。
2. PCA技术的一个很大的优点是，它是完全无参数限制的。在PCA的计算过程中完全不需要人为的设定参数或是根据任何经验模型对计算进行干预，最后的结果只与数据相关，与用户是独立的。

不足：

1. 但是，这一点同时也可以看作是缺点。如果用户对观测对象有一定的先验知识，掌握了数据的一些特征，却无法通过参数化等方法对处理过程进行干预，可能会得不到预期的效果，效率也不高。
2. 当样本点具有一些非线性性质时候，采用PCA得到的降维效果无法反映出样本点之间所隐藏的非线性性质。
3. PCA能够找到很好地代表所有样本点的方向，但是这个方向对于分类未必就是最有利的。
4. 对于降维后的特征，比较难找到其实际含义及解释。

实行PCA的默认假设条件

线性

这是一个非常强的假设条件。该假设表明了两个信息：1.数据被限制在一个向量空间中，能够被一组基表示；2.隐含地假设了数据之间的连续性关系。这样一来数据就可以被表示为各种基的线性组合。

使用中值和方差进行充分统计

使用中值和方差进行充分的概率分布描述的模型只限于指数型概率分布模型（如高斯分布）。也就是说，如果我们考察的数据的概率分布并不满足高斯分布或者是指数型的概率分布，那么PCA就会失效。在这种情况下，不能使用方差和协方差来很好地描述噪音和冗余。

大方差对应的是重要数据，小方差对应的是噪声数据

该假设等同于另一个假设：给出的数据对应高的信噪比。这是一个很强的假设，但有时候是不对的。

主成分之间正交

这个假设使得PCA的求解可以采用线性代数分解技术实现，比如特征值分解与SVD。

Kernel PCA

PCA使用的前提是只对服从指数函数分布（如高斯分布）的数据特征提取效果很好，这就大大限制了它的应用范围。假如数据呈现的是任意分布，那么不管在原始空间中如何做政教变换，都不可能找到一组最优的特征方向。同样的，PCA是一个线性方法，对于提取数据的非线性结构无能为力，显然，不管在原始空间上对PCA方法进行多大的改进，都不可能摆脱这个前提限制，从本质上将其变成一个非线性算法。

Kernel PCA 思想及基本理论

基于核的主成分分析法是国际上新提出的一种特征提取算法，它利用核技巧对PCA进行一种非线性推广。对于服从任意分布的观测数据x，Kernel PCA首先利用一个非线性映射函数将观测数据从输入空间映射到特征空间F中，使得映射数据近似高斯分布，然后对映射数据做PCA。因为特征空间可能是一个超高维空间，且Kernel PCA算法可以表示为F空间上样本点的内积形式(类似SVM)，所以它巧妙地应用了核技巧回避了求取非线性映射的艰巨任务。

现在，有一个在原始特征空间数据为$x_i$，经映射到高维空间后得到的数据为$\phi(x_i)$。我们对经过映射后的数据集进行PCA处理。具体做法：
首先，假设映射到高维空间的数据的各个维度的均值为0。由定义求解协方差矩阵：

$$C = \frac{1}{n} \sum_{i=1}^n \phi(x_i)\phi(x_i)^T$$
协方差矩阵对应的特征值和特征向量设为$\lambda_j、v_j$，可得：
$$Cv_j = \lambda_j v_j$$
在看到了表达式$\phi(x_i)\phi(x_i)^T$之后，是不是有很多人就想着直接用核函数$K(x_i,x_i)$来表示就完啦！大功告成。但是，你想多了。看清楚$x_i$以及$\phi(x_i)$都是列向量，$\phi(x_i)\phi(x_i)^T$是一个矩阵，而不是点积。所以，没那么简单！

Kernel PCA 推导过程

那么怎么做呢？将表达式$C = \frac{1}{n} \sum_{i=1}^n \phi(x_i)\phi(x_i)^T$代入到$Cv_j = \lambda_j v_j$中，可得：

$$\frac{1}{n} \sum_{i=1}^n \phi(x_i)\phi(x_i)^T v_j = \lambda_j v_j$$
因此：
$$v_j = \frac{1}{\lambda_j n} \sum_{i=1}^n \phi(x_i)\phi(x_i)^T v_j$$
由于$\phi(x_i)^T v_j$是一个标量，也可以写成：
$$v_j = \frac{1}{\lambda_j n} \sum_{i=1}^n \phi(x_i)\phi(x_i)^T v_j = \sum_{i=1}^n \frac{\phi(x_i)^T v_j}{\lambda_j n}\phi(x_i) = \sum_{i=1}^n \alpha_{ji} \phi(x_i)$$
其中的$\alpha_{ji} = \frac{\phi(x_i)^T v_j}{\lambda_j n}$。上式可以得出：特征向量$v_j$可以用样本$\phi(x_i)$的线性组合来表示。将$v_j$表达式回代到$\frac{1}{n} \sum_{i=1}^n \phi(x_i)\phi(x_i)^T v_j = \lambda_j v_j$，有：
$$\frac{1}{n} \sum_{i=1}^n \phi(x_i)\phi(x_i)^T [\sum_{l=1}^n \alpha_{jl} \phi(x_l)] = \lambda_j \sum_{l=1}^n \alpha_{jl} \phi(x_l) \\ \frac{1}{n} \sum_{i=1}^n \phi(x_i) [\sum_{l=1}^n \alpha_{jl} \phi(x_i)^T \phi(x_l)] = \lambda_j \sum_{l=1}^n \alpha_{jl} \phi(x_l)$$
由于$\phi(x_i)^T \phi(x_l)$可以表示为点积的形式，那么就可以使用核函数来表示：
$$\frac{1}{n} \sum_{i=1}^n \phi(x_i) [\sum_{l=1}^n \alpha_{jl} K(x_i,x_l)] = \lambda_j \sum_{l=1}^n \alpha_{jl} \phi(x_l)$$
这样的简化还不够，进一步，等式两边同时左乘$\phi(x_k)^T$，可得：
$$\frac{1}{n} \sum_{i=1}^n \phi(x_k)^T\phi(x_i) [\sum_{l=1}^n \alpha_{jl} K(x_i,x_l)] = \lambda_j \sum_{l=1}^n \alpha_{jl} \phi(x_k)^T \phi(x_l)$$
由此，我们似乎已经看到了核函数。上式再经过一系列转换之后，可以变成：
$$K^2 \alpha_j = n \lambda_j K \alpha_j$$
左右两边同时乘以$K^{-1}$，有：
$$K \alpha_j = n \lambda_j \alpha_j$$
有了该表达式，至少我们可以先通过求解核函数矩阵$K$以得到其特征向量$\alpha$以及对应的特征值$n \lambda_j$。我们需要的是$v_j$与$\lambda_j$，似乎离结果已经不远了。我们希望的特征向量$v_j$有一约束条件：$v_j$必须是单位向量，又因为$\alpha_j$里包含了$v_j$，那么可得：
$$v_j^T v_j = 1 \Rightarrow \sum_{k=1}^n \sum_{l=1}^n \alpha_{jl}\alpha_{jk} \phi(x_l)^T \phi(x_k) = 1 \Rightarrow \alpha_j^TK\alpha_j = 1$$
由$K \alpha_j = n \lambda_j \alpha_j$，可得：
$$\lambda_j n \alpha_j^T \alpha_j =1$$
我们的终极目标就是：对于一个新来的数据点$x$，求得其在某一个主成分$v_j$方向上的映射：
$$\phi(x)^T v_j = \sum_{i=1}^n \alpha_{ji} \phi(x)^T \phi(x_i) = \sum_{i=1}^n \alpha_{ji} K(x,x_j)$$
发现，此时只需要用核函数矩阵以及参数$\alpha$就可以求解，那么我们就不必苦苦追究之前的目标$v_j$了。不知不觉已经找到了最终目的地。

通常呢，我们的核函数$\phi(x_i)$并不是去均值化的，但是你知道我们在Kernel PCA中求解核函数矩阵（类似于PCA中的协方差矩阵），那么如何去均值化呢？

$$\widetilde \phi(x_i) = \phi(i) - \frac{1}{n} \sum_{k=1}^n\phi(x_k)$$
那么对应的核函数矩阵中的元素，有：
$$\widetilde K(x_i,x_j) =\widetilde \phi(x_i)^T \widetilde \phi(x_j) \\ = (\phi(i) - \frac{1}{n} \sum_{k=1}^n\phi(x_k))^T(\phi(j) - \frac{1}{n} \sum_{k=1}^n\phi(x_k)) \\ = K(x_i,x_j) - \frac{1}{n} \sum_{k=1}^n K(x_i,x_k) - \frac{1}{n} \sum_{k=1}^n K(x_j,x_k) + \frac{1}{n^2} \sum_{l,k=1}^n K(x_l,x_k)$$
表示为矩阵的形式，即为：
$$\widetilde K = K - 2\mathbb{1}_{1/n}K + \mathbb{1}_{1/n}K \mathbb{1}_{1/n}$$
其中$\mathbb{1}_{1/n}$表示的是全部元素都是$1/n$的矩阵。

好了，kernel PCA的整体流程我们来回顾一下：