PCA主成分分析算法

在数据分析中，如果特征太多，或者特征之间的相关性太高，通常可以用PCA来进行降维。比如通过对原有10个特征的线性组合, 我们找出3个主成分，就足以解释绝大多数的方差，该算法在高维数据集中被广泛应用。

算法（没时间看版本）：

• 将数据标准化，即把所有数据转换以原点为中心；
• 划一条通过原点的直线，将所有点投影到该直线上，然后计算这些投影点到原点的距离平方和。设想我们不停的转动该直线，最终找到一条直线使得这个距离平方和最大，也就是该直线最接近所有的点，该直线为特征向量的方向，称为PC1，这个距离平方和即为特征值；
• 按同样的方法，找到第二条直线，该直线与PC1垂直且距离平方和最大，为PC2；
• 重复该过程直到找到所有的PC；
• 根据需求，确定头部的几个PC可以解释绝大多数方差。

下面先给出几个相关的概念。

---

协方差和散度矩阵

样本均值：
$$\bar{x}=\frac{1}{n}\sum _{i=1}^N{x}_i$$
样本方差：
$$S^2=\frac{1}{n?1}\sum _{i=1}^n{(x_i?\bar{x})}^2$$
样本X和样本Y的协方差：
$$Cov(X,Y)=E[(X?E(X))(Y?E(Y))]=\frac{1}{n?1}\sum _{i=1}^n(x_i?\bar{x})(y_i?\bar{y})$$

1. 方差的计算是针对一维特征的，即针对同一特征不同样本的取值来进行计算得到；而协方差必须要求至少满足二维特征；方差是协方差的特殊情况。
2. 方差和协方差的除数是$n?1$，这是为了得到方差和协方差的无偏估计。
   协方差为正时，说明X和Y是正相关关系；为负时负相关关系；为0时相互独立。$Cov(X,X)$就是X的方差。当样本是n维数据时，它们的协方差实际上是协方差矩阵（对称方阵）。

散度矩阵
$$S=\sum _{k=1}^n(x_k?m)(x_k?m{)}^T$$
其中$m=\frac{1}{n}{\sum }_{k=1}^n{x}_k$
对于数据X的散度矩阵为$X{X}^T$。其实协方差矩阵和散度矩阵关系密切，散度矩阵就是协方差矩阵乘以（总数据量-1）。因此它们的特征值和特征向量是一样的。同时散度矩阵是SVD奇异值分解的一步，因此PCA和SVD有密切关系。

---

特征值分解矩阵原理

1. 特征值与特征向量
   如果一个向量v是矩阵A的特征向量，则一定可以表示成下面的形式：
   $$Av=\lambda v$$
   其中，$\lambda$是特征向量v对应的特征值，一个矩阵的一组特征向量是一组正交向量。
2. 特征值分解矩阵
   对于矩阵A，有一组特征向量v，将这组向量进行正交化单位化，就能得到一组正交单位向量。特征值分解，就是将矩阵A分解为如下式：
   $$A=Q\sum Q^{?1}$$
   其中，Q是矩阵A的特征向量组成的矩阵，$\sum$则是一个对角阵，对角线上的元素就是特征值。

---

SVD分解矩阵原理

奇异值分解是一个能使用任意矩阵的一种分解的方法，对于任意矩阵A总是存在一个奇异值分解：
$$A=U\sum V^T$$
假设A是一个$m\times n$矩阵，那么得到的U是一个$m\times m$的方阵，U里面的正交向量被称为左奇异向量。$\sum$是一个$m\times n$矩阵，$\sum$除了对角线其他元素都为0.对角线上的元素称为奇异值。$V^T$是V的转置矩阵，是一个$n\times n$的方阵，它里面的正交向量被称为右奇异值向量。通常$\sum$上的值按从大到小的顺序排列。

SVD算法：

• 求$A{A}^T$的特征值和特征向量，用单位化的特征向量构成U；
• 求$A^{T}A$的特征值和特征向量，用单位化的特征向量构成V；
• 将$A{A}^T$或者$A^{T}A$的特征值求平方根，然后构成$\sum$。

---

基于特征值分解协方差矩阵实现PCA算法

输入：数据集$X=x_1,x_2,x_3,...,x_n$，需要降到k维。

1.去平均值（即去中心化），即每一位特征减去各自的平均值。
2.计算协方差矩阵$\frac{1}{n}X{X}^T$，注：这里除或不除样本数量$n$或$n?1$，其实对求出的特征向量没有影响。
3.用特征值分解方法求协方差矩阵$\frac{1}{n}X{X}^T$的特征值与特征向量。
4.对特征值从大到小排序，选择其中最大的k个。然后将对应的k个特征向量分别作为行向量组成特征向量矩阵P。
5.将数据转换到k个特征向量构建的新空间中，即$Y=PX$。

---

基于SVD分解协方差矩阵实现PCA算法

输入：数据集$X=x_1,x_2,x_3,...,x_n$，需要降到k维。

1.去平均值（即去中心化），即每一位特征减去各自的平均值。
2.计算协方差矩阵$\frac{1}{n}X{X}^T$，注：这里除或不除样本数量$n$或$n?1$，其实对求出的特征向量没有影响。
3.用SVD分解方法求协方差矩阵$\frac{1}{n}X{X}^T$的特征值与特征向量。
4.对特征值从大到小排序，选择其中最大的k个。然后将对应的k个特征向量分别作为行向量组成特征向量矩阵。
5.将数据转换到k个特征向量构建的新空间中。