本篇博客的主要内容有：
- 降维
- PCA的数学基础
- PCA的两种思想推导
- 基于最大投影方差
- 基于最小重构距离
- PCA的计算过程
降维
降维属于无监督学习，可以用来解决训练中过拟合和维数灾难问题。
-
维数灾难 导致数据稀疏性/过拟合
一个直观的理解是：假设我们有十个样本
特征维数为1D时，当特征空间是长度为5的线段时，样本密度是10/5=2。
特征维数为2D时，特征空间大小为\(5^{2}\)，样本密度为10/25=0.4。
特征维数为3D时，特征空间大小为\(5^{3}\)，样本密度为10/125=0.08
如果我们继续增加特征，特征空间的维数就会不断增长，变得越来越稀疏。由于这种稀疏性，当特征的数量无穷大时，训练样本位于最佳超平面错误一侧的可能性无穷小，因此找到可分离超平面就变得容易得多。事实上，增加特征数量使得高维空间线性可分，相当于在低维空间内训练一个复杂的非线性分类器。不过，这个非线性分类器学习了训练数据中的specific instances and exceptions，这就直接导致导致了过拟合 -
过拟合(overfitting) 使用太多特征将会导致过拟合，泛化能力差
overfitting: The classifier starts learning exceptions that are specific to the training data and do not generalize well when new data is encountered.
虽然在较低维度下分类器的性能表现的可能不如在高维空间中的好，但是对于未见过的数据却表现了良好的泛化能力，也就是说，使用更少的特征，我们的分类器可以避免过拟合，进而避免维数灾难
-
维数灾难不同视角一
假设每个样本的特征值都是唯一的，并且每个特征的范围都是[0-1]
在1D时，如果我们想要将训练数据覆盖特征范围的20%时，我们需要所有样本的20%作为训练数据
在2D时，0.45^2=0.2，因此我们需要所有样本的45%作为训练数据
在3D时，0.58^3=0.2，因为我们需要所有样本的58%作为训练样本
也就是说，随着特征维数的增加，为了覆盖特征值值域的20%，我们需要增加更多的训练样本，当训练样本数量固定时，增加更多的特征维数，就容易导致过拟合 -
维数灾难中不同视角二
维数灾难导致训练样本的分布不均 在中心位置的数据比在其周围的数据分布更加的稀疏，更多的数据将会分布在超立方体的角落。
可以这样来理解，设我们的立方体的边长为1。
不管维数多少，我们的超立方体的体积都为1
超球体的体积计算公式为：
\(V_{超球体} = K \cdot r ^{D}\) （r为小于1的数）
当D->无穷大时，V->0，这部分说明了分类问题中的“维数灾难”：在高维特征空间中，大多数的训练样本位于超立方体的角落。 -
维数灾难中不同视角三
想象我们有一个圆环，其外环半径为1，内环半径为\(1-\varepsilon\)
可以求得：
\(V_{外} = K \cdot 1 ^{D} = K\)
\(V_{环} =V_{外} - V_{内} = K - K \cdot (1-\varepsilon )^{D}\)
从而有：
\(\frac{V_{外}}{V_{内}} = 1 - (1-\varepsilon ) ^{D}\)
\(\lim_{D \to \infty }\frac{V_{外}}{V_{内}} = 1\)
随着维数的增加，我们在三维空间中的几何直觉会在考虑高维空间中不起作用。 一个球体的大部分体积都聚集在表面附近的薄球壳上面。 -
降维的方法分类
对于数据降维的方法有- 直接降维(特征选择)
- 线性降维(PCA等)
- 非线性降维(流行学习等)
下面将开始介绍PCA降维的思想。
PCA的基础概念
-
求和向量\(1_{n}\)
对于任何一个向量x，其所有元素之和都等于x与求和向量的内积 -
中心化矩阵(centering matrix)
\(H = I_{N} - \frac{1}{N}\cdot 1_{N}\cdot 1_{N}^{T}\)
对于任意的向量x,\(H\cdot x\)表示将原数据向量的各个元素减去n个数据的均值的结果,直观上理解就是将数据往中心原点移动
中心化矩阵有两个基本性质：
- \(H^{T} = H\)
- \(H^{n} = H\)
以上两个将会在推导PCoA中使用到
-
Data:
\(X_{N\times P} = \begin{pmatrix} x_{1}& x_{2} & ... & x_{n} \end{pmatrix}^{T}\)
表示有N个数据，每个数据是P维的 -
Sample Mean:
\(\bar{X} = \frac{1}{N} \sum_{i=1}^{N}x_{i}\) -
Sample Covariance
对于一维数据，我们有：
\(S = \frac{1}{N} \sum_{i=1}^{N}(x_{i}-\bar{x})^{2} = \frac{1}{N}\cdot X^{T}\cdot 1_{N}\)
对于p维数据，我们有：
\(S_{p\times p} = \frac{1}{N} \sum_{i=1}^{N}(x_{i}-\bar{x})\cdot (x_{i}-\bar{x})^{T} = \frac{1}{N}\cdot X^{T}\cdot H\cdot X\) -
计算向量在某个方向上的投影
\(\vec{a}\cdot \vec{b} = \left | \vec{a} \right |\cdot \left | \vec{b} \right |\cdot \cos \theta\)
因此，当\(\left | \vec{b} \right | = 1\)时，\(\vec{a}\)在\(\vec{b}\)上面的投影为：
\(P = \left | \vec{a} \right |\cdot\cos \theta\)
PCA的思想与推导过程
PCA的主要内容可以用一句话来概括，那就是：一个中心，两个基本点
一个中心：是对原始特征空间的重构，将一组可能是线性相关的数据通过正交变换，变成线性无关的数据(即去除数据的线性相关性)，当重构的空间维数小于原始特征空间维数时，就达到了降维的目的。
两个基本点：
- 最大投影方差思想
- 最小重构距离思想
基于最大投影方差思想的推导过程
最大投影方差指：
将样本投影到新的坐标下，数据能够尽可能的分开(也就是方差尽可能大)，这样就能尽可能的将降低数据维度的时候更好的保留原始数据的特性，更好的区分原始数据。
我们先计算将数据降至1维，投影方向\(\vec{u_{1}}\)
\(j = \overrightarrow{(x_{i}-\bar{x})^{T}}\cdot \vec{u_{1}}\)
实际上投影是一个数，以\(u_{1}\)为基底时，在\(u_{1}\)上面的坐标
那么投影方差应该表示为：
\(J = \frac{1}{N}\sum_{i=1}^{N}\begin{Bmatrix}
(x_{i}-\bar{x})^{T}\cdot u_{1}
\end{Bmatrix}^{2}\)
\(= \frac{1}{N}\sum_{i=1}^{N}u_{1}^{T}\cdot (x_{i}-\bar{x})\cdot (x_{i}-\bar{x})^{T}\cdot u_{1}\)
\(=u_{1}^{T}\cdot \bigl(\begin{smallmatrix}
\frac{1}{N}\sum_{i=1}^{N}
(x_{i}-\bar{x})\cdot (x_{i}-\bar{x})^{T}
\end{smallmatrix}\bigr)\cdot u_{1}\)
\(= u_{1}^{T}\cdot S \cdot u_{1}\)
到这里我们就得到了J的表示函数，就将问题转为求：
\(\check{u_{1}} = argmax ( u_{1}^{T}\cdot S \cdot u_{1})\)
s.t. \(u_{1}^{T} \cdot u_{1} = 1\)
根据拉格朗日乘子法
\(\alpha (u_{1},\lambda ) = u_{1}^{T}\cdot S \cdot u_{1}) + \lambda \cdot (1-u_{1}^{T}\cdot u_{1})\)
\(\frac{\partial \alpha}{\partial u_{1}} = 2\cdot S\cdot u_{1} - \lambda \cdot 2\cdot u_{1}=0\)
\(Su_{1} = \lambda u_{1}\)
这里面涉及到矩阵求导，请参考：
矩阵求导术
实际上式子推导到这里，我们得出结论：
\(\lambda\)即特征值，\(u_{1}\)即特征向量
也就是说，我们的投影方向应该是S的特征向量的方向
再接着我们可以得到：
\(u_{1}^{T}\cdot S \cdot u_{1} = \lambda\)
也就是说，如果将数据降至一维，那么我们的\(\check{u_{1}} = argmax ( u_{1}^{T}\cdot S \cdot u_{1})\) 极大值就是\(\lambda\)
即\(u_{1}\)是S最大特征值对应的特征向量时，投影方差取到极大值，我们称\(u_{1}\)为第一主成分
那么接下来我们就先获得方差最大的1维，生成该维的补空间；，继续在补空间中获得方差最大的1维，继续生成新的补空间，依次循环下去得到M维的空间，我们就可以降至M维了。
S的特征向量，就可以认为是主成分
基于最小重构距离思想的推导过程
最小重构距离指：
恢复到原始数据的代价最小(当我们考虑最大投影方差时，其实也可以任务数据尽可能的分散，那么恢复成原始数据的代价就更小，如果数据都重合在了一起，那么想要恢复数据，也就是重构，就更加困难了)
-
在新基底(以S的特征向量为基底)的向量表示
\(\vec{x_{i}} = \sum_{k=1}^{p}(\vec{x_{i}^{T}}\cdot \vec{u_{k}} )\cdot \vec{u_{k}}\)
为了简化描述，我们先假设数据已经中心化，注意这里的原始数据是p维的 -
降至q维的向量表示
\(\vec{\hat{x_{i}}} = \sum_{k=1}^{q}(\vec{x_{i}^{T}}\cdot \vec{u_{k}} )\cdot \vec{u_{k}}\) -
最小重构代价计算
\(J = \frac{1}{N} \sum_{i=1}^{N}\left \| \vec{x_{i}}-\hat{x_{i}} \right \|^{2}\)
\(= \frac{1}{N} \sum_{i=1}^{N}\left \| \sum_{k=q+1}^{p}(\vec{x_{i}^{T}} \cdot \vec{u_{k}} )\cdot \vec{u_{k}} \right \|^{2}\)
\(= \frac{1}{N} \sum_{i=1}^{N} \sum_{k=q+1}^{p}(x_{i}^{T}\cdot u_{k})^{2}\)
前面我们假设数据已经中心化，现在我们代入真正的数据
\(J= \frac{1}{N} \sum_{i=1}^{N} \sum_{k=q+1}^{p}\begin{Bmatrix} (x_{i}^{T}-\bar{x})\cdot u_{k} \end{Bmatrix}^{2}\)
\(J= \sum_{k=q+1}^{p}\sum_{i=1}^{N} \frac{1}{N} \begin{Bmatrix} (x_{i}^{T}-\bar{x})\cdot u_{k} \end{Bmatrix}^{2}\)
\(J=\sum_{k=q+1}^{p}u_{k}^{T}\cdot S \cdot u_{k}\)
s.t. \(u_{k}^{T}\cdot u_{k}=1\)
到这里我们的推导已经基本上完成了，下面是我们的优化目标：让J最小
\(J = argmin (\sum_{k=q+1}^{p}u_{k}^{T}\cdot S \cdot u_{k})\)
s.t. \(u_{k}^{T}\cdot u_{k}=1\)
在这里我们可以发现，这个优化目标与最大方差的优化目标形式是一样的，只不过一个是求最大的\(\vec{u}\)，一个是降至k维后余下向量的\(\vec{u}\)
要求最小的J的话,应该求最小的特征值，那么剩下的特征值就是前q维的主成分了。
PCA的计算过程(IPO)
input: \(X_{N \times p}\),降至q维
Process:
- 中心化 \(X:= H \cdot X\)
- 计算样本的协方差矩阵S
- 对S做特征值分解
- 取前q大个特征值所对应的特征向量 \(u_{1},u_{2},...u_{q}\)(列向量)组成投影矩阵\(P=(u_{1}u_{2}...u_{q})\)
Output:
\(X_{N \times q} = P^{-1} \cdot X_{N \times p} = P^{T} \cdot X_{N \times p}\)
关于PCA的内容还有一个是关于PCA的计算优化PCoA，使用SVD分解，以及scikit learn中的PCA源码就是使用PCoA，这个先挖坑待填，下次我将会更新从SVD角度的PCoA和PCA的实现源码。
References：
- Vincent Spruyt. The Curse of Dimensionality in classification. Computer vision for dummies. 2014.
- 西瓜书
- PRML
- 求和向量和中心矩阵
- 矩阵求导术
- 白板推导系列