降维PCA 主成分分析 Principal Components

一些基本概念：

1. 生成模型generative model：生成模型是指联合分布；判别模型是指条件分布。
2. WLOG: Without loss of generality 不失一般性
3. signal reconstruction: 信号重构
4. 数据噪声：引入噪声通常是为了防止过拟合的，噪声一般能提高模型的泛化能力
5. 过拟合：当训练时候的数据不够，即训练数据不足以估计整个数据的分布时，或者最模型进行过度训练时，会导致过拟合。
6. 维度：维度通常指特征的个数。它比较少的情况下也可以指数据向量的第几维。我有段时间一直将维度的概念搞错了！

下面是PCA的内容：

1. 什么是降维？
   根据维基百科的定义，在机器学习中，降维是指减少随机变量的个数的过程。主要包括两方面：特征选择(features selection)和特征提取(features extraction or features projection)。换句话说，降维是指减少特征空间的维数。
   为什么降维？
   1.为了减少数据噪声，突出主要特征，减少计算量，如PCA。
   2.为了减少模型的参数。
   3.为了避免过拟合。
   怎么降维？ 一般的想法是在低维保持数据的主要特征。

PCA是一个使数据不相关的过程。它的目标是，找到一个坐标系统，使不同的维度不相关。或者，找到一个坐标系统，找出最大的方差。

2. 怎样实现PCA：相关性可以通过旋转数据点或坐标来消除。

我们有数据，PCA找到一个方向使。优化这个式子我们必须对 有限制条件：。
拉格朗日方程有：

对求偏微分等于0有：


这是一个标准的特征方程问题。是对应最大特征根的的特征向量。
是由数据方差矩阵做特征根分解得到的：
主成分是特征向量，是对应的对角线上的特征根。

PCA的特征：
a. 特征向量是正交的： 。也就是说，PCA对应着生成模型，这儿。
b. 是对角阵。也就是说，分解出来的在时间上是无关的。
c. 第i个特征根是第i个因子的方差:

具体算法：

|-------------------------------------------------------------------------------------------|
Require : data , number of principal components k
1: #Center data:
2: #Compute Covariance Matrix :
3: #Calculate eigenvectors and eigenvalues
of the covariance matrix:
4: # Rank eigenvectors by its corresponding
eigenvalues
5: return top k eigenvectors

|-------------------------------------------------------------------------------------------|

3. 什么是信号重构？
   PCA所做的是将数据投影到输入空间的子集上。例如，这张图里，投影数据在子空间里面有最大的方差。图中的红点是在投影上重构的数据。重构误差是从蓝点到红点的距离之和。

信号重构的最优性
WLOG(不失一般性)， 假设特征向量对应的特征根有序排列，即

那么，前k个成分方向的投影，即

里面有的方差。

定理：在k维投影上的重构误差最小值是的余下的个最小的特征根之和:

最小值在处取得。
证明：
化简
而

4. Kernel Trick
   我们有数据，会遇到这样的问题：
   a. 协方差矩阵的矩阵的维数会很大
   b. 对于协方差矩阵的估计拥有的数据太少

我们知道肯定在数据的延伸上，, 是每个点的权重。
将代入PCA的式子里，得到

则有：

这种通过而不是解PCA的方法称作linear kernel PCA。

5. Singular Value Decomposition(SVD)奇异值分解
   通过SVD我们可以分解任意一个矩阵，这儿和是包含着奇异向量的正交矩阵， 是对角阵，为奇异值。

现在我们可以看到
a.协方差矩阵
b.核矩阵
是的特征向量，是的特征向量。
是和的特征值的平方根。
线性核PCA和经典PCA之间的关系是：