线性特征降维——PCA

PCA主成分分析

主成分分析（Principal Component Analysis），是一种无监督的特征降维的方法，用于探索高维数据。PCA通常用于高维数据集的探索与可视化，还可以用于数据压缩，数据预处理等。
  由于大部分原始数据都存在高维特征，而它们并不是全部可用，这些特征中存在着噪声或者冗余，为了能达到一个比较好的效果，需要一种特征降维的方法来减少特征数，减少噪音和冗余，减少过度拟合的可能性。PCA通过线性变换将原始数据变换为一组各维度线性无关的表示实现高维数据的降维，可用于提取数据的主要特征分量，得到的低维特征称为主成分。新的低维数据集会尽可能的保留原始数据的变量，即将高维数据集映射到低维空间的同时，尽可能的保留更多的原始信息。
  PCA的思想是将n维特征映射到k维上（k < n），这k维是全新的正交特征。这k维特征称为主成分，是重新构造出来的k维特征，而不是简单地从n维特征中去除其余n-k维特征。

数学原理

• 基变换的矩阵表示
• 基的筛选

基变换的矩阵表示

  将一组向量的基变换表示为矩阵的相乘。一般地，如果我们有M个N维向量，想将其变换为由R个N维向量（R个基）表示的新空间中，那么首先将R个基按行组成矩阵P，然后将待变换向量按列组成矩阵X，那么两矩阵的乘积就是变换结果。R可以小于N，而R决定了变换后数据的维数。也就是说，我们可以将一N维数据变换到更低维度的空间中去，变换后的维度取决于基的数量。

  因此这种矩阵相乘可以表示降维变换：
$Y_{R\times M} = P_{R\times N} \times X_{N\times M}$

  两个矩阵相乘的意义：将右边矩阵中的每一列列向量变换到左边矩阵中每一行行向量为基所表示的空间中。

基的筛选

  如果我们有一组N维向量，现在要将其降到R维，要选择最优的R个基使得能最大程度保留原有的信息。
  先举一个直观的例子来说明。5个二维向量组合成矩阵表示为：

​ $X = \begin{pmatrix} 1 & 1 & 2 & 4 & 2 \\ 1 & 3 & 3 & 4 & 4 \end{pmatrix}$

其中每一列为一条数据记录，而一行代表一个维度。为了后续处理方便，我们首先将每个维度内所有值都减去该维度的均值，其结果是将每个维度的均值都变为0。

​ $X' = \begin{pmatrix} -1 & -1 & 0 & 2 & 0 \\ -2 & 0 & 0 & 1 & 1 \end{pmatrix}$

若想要使用一维来表示这些数据，又希望尽量保留原始的信息，即要在二维平面中选择一个方向，将所有数据都投影到这个方向所在直线上，用投影值表示原始记录。这是一个实际的二维降到一维的问题。那么如何选择这个基才能尽量保留最多的原始信息呢？如果想要投影后几个数据点重叠在一起，这将是一个严重的数据损失，因此为了能尽量保留原始数据的信息，我们希望投影后的投影值尽可能分散。而这种分散程度，可以用数学上的方差来表述。

• 方差

  一个维度上的方差可以看做是每个元素与所在维度均值的差的平方和的均值，即：
$Var(a)=\frac{1}{m}\sum_{i=1}^m{(a_i-\mu)^2}$

由于我们之前已经对每个向量进行了去均值的处理，所以对于矩阵 X' 表示的向量，所求方差可以表示为：
$Var(a)=\frac{1}{m}\sum_{i=1}^m{a_i^2}$

于是上面的问题被形式化表述为：寻找一个一维基，使得所有数据变换为这个基上的坐标表示后，方差值最大。

• 协方差

  对于二维降为一维，使用方差进行选择是可行的，但对于多维空间，由于方差只是针对某一个维度来研究数据在这个维度上的分散程度，它并没有考虑维度间的关系，但现实生活中的数据维度间普遍存在相关性，而维度的相关性可能会给数据带来一些噪声，影响映射的效果。因此，需要考虑维度间的关系，而对于这种关系，可用协方差来表述。
  协方差用于衡量两个维度间的总体误差。X维和Y维间的协方差表示为：
$Cov(X,Y)=\frac{1}{m}\sum_{i=1}^m{(X_i-\mu_X)(Y_i-\mu_Y)}$

如果两个维度对应的变量的变化趋势一致，那么两个维度之间的协方差就是正值；如果两个维度对应的变量的变化趋势相反，那么两个维度之间的协方差就是负值。如果X与Y是相互独立的，那么二者之间的协方差就是0。显然，正交基间的协方差为0，为了让投影的维度之间能完全独立，选择的投影基应该是相互正交的。
  至此，我们得到了降维问题的优化目标：将一组N维向量降为K维（0 < K < N），其目标是选择K个单位正交基，使得原始数据变换到这组基上后，各维度两两间协方差为0，而每个维度的方差则尽可能大（在正交的约束下，取最大的K个方差）。

• 协方差矩阵

  假设由向量组组成的矩阵 X 为：
$X=\begin{pmatrix} a_1 & a_2 & \cdots & a_m \\ b_1 & b_2 & \cdots & b_m \end{pmatrix}$

矩阵 X 有两维，分别为a和b，则协方差矩阵表示为： $C = \frac{1}{m}XX^\mathsf{T}= \begin{pmatrix} \frac{1}{m}\sum_{i=1}^m{a_i^2} & \frac{1}{m}\sum_{i=1}^m{a_ib_i} \\ \frac{1}{m}\sum_{i=1}^m{a_ib_i} & \frac{1}{m}\sum_{i=1}^m{b_i^2} \end{pmatrix} = \begin{pmatrix} Cov(a,a) & Cov(a,b) \\ Cov(b,a) & Cov(b,b) \end{pmatrix}$

协方差矩阵对角线上的两个元素分别是两个维度的方差，而其它元素是a和b的协方差。协方差和方差这两者被统一到了一个矩阵。推广到一般情况：设我们有m个n维数据记录，将其按列排成n$\times$m的矩阵X，设$C=\frac{1}{m}XX^\mathsf{T}$，则C是一个对称矩阵，其对角线分别个各个维度的方差，而第i行j列和j行i列元素相同，表示i和j两个维度的协方差。

  设原始矩阵为$X_{N\times M}$，表示M个N维向量，其协方差矩阵为$C_{N\times N}$ , $P_{R\times N}$为变换矩阵；$Y_{R\times M}$为目标矩阵, 其协方差矩阵为D。我们要求降维后的矩阵 Y 的每一维包含的数据足够分散，也就是每一行（维）方差足够大，而且要求行之间的元素线性无关，也就是要求行之间的协方差全部为0。这就要求协方差矩阵D的对角线元素足够大，除对角线外元素都为0，相当于对C进行协方差矩阵对角化。
具体推导如下：

$D = \frac{1}{m}YY^\mathsf{T} = \frac{1}{m}(PX)(PX)^\mathsf{T} = \frac{1}{m}PXX^\mathsf{T}P^\mathsf{T} = PCP^\mathsf{T}$

C是X的协方差矩阵，是实对称矩阵，整个PCA降维过程其实就是一个实对称矩阵对角化的过程。由于实对称矩阵 C 的特征值就是其相似对角矩阵 D 上对角线元素,由于矩阵 D 也是目标矩阵 Y 的协方差矩阵，选择矩阵 C 前R大的特征值作为 D 的对角线元素，则可实现协方差矩阵 D 中每一维的方差足够大；同时取矩阵 C 前R大的特征值对应的特征向量作为正交基，使得维度之间不相关。

PCA算法步骤

设有M个N维数据:

1. 将原始数据按列组成N行M列矩阵X。
2. 将X的每一行进行零均值化，即减去每一行的均值。
3. 求出X的协方差矩阵C。
4. 求出协方差矩阵C的特征值及对应的特征向量，C的特征值就是Y的每维元素的方差，也是D的对角线元素，从大到小沿对角线排列构成D。
5. 将特征向量按对应特征值大小从上到下按行排列成矩阵，根据实际业务场景，取前R行组成矩阵P。
6. Y=PX即为降到R维后的目标矩阵 。

PCA的python实现

先导入 PCA 库：

from sklearn.decomposition import PCA

引用scikit-learn官网上的例子：

import numpy as np
X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
pca = PCA(copy=True, n_components=2, whiten=False)
pca.fit(X)
print (pca.explained_variance_)
print(pca.explained_variance_ratio_)

[ 6.61628593  0.05038073]
[ 0.99244289  0.00755711]

首先先创建一个 PCA 对象：pca = PCA(copy=True, n_components=2, whiten=False) 参数说明：
n_components: 这个参数可以帮我们指定希望PCA降维后的特征维度数目。当n_components是一个整数时，它表示直接指定降维到的维度数目；当n_components是一个(0，1]之间的小数时，它指定主成分的方差之和所占的最小比例阈值；让PCA类自己去根据样本特征方差来决定降维到的维度数；也可以把参数值设为n_components='mle',PCA类会用MLE算法根据特征的方差分布情况自己去选择一定数量的主成分特征来降维。缺省时默认值为n_components=min(样本数，特征数)。

copy: bool 类型，表示是否在运行算法时，将原始训练数据复制一份。若为True，则运行PCA算法后，原始训练数据的值不会有任何改变，只在原始数据的副本上进行运算；若为False，则运行PCA算法后，会在原始数据上进行降维计算，原始训练数据的值会改。缺省时默认为True。

whiten: bool 类型，判断是否进行白化。所谓白化，就是对降维后的数据的每个特征进行归一化，让方差都为1.对于PCA降维本身来说，一般不需要白化。如果你PCA降维后有后续的数据处理动作，可以考虑白化。默认值是False，即不进行白化。

fit(X): 用数据 X 训练 PCA 模型。

explainedvariance: 返回保留下来的n个维度的方差。

explainedvariance_ratio: 返回保留下来的各维度方差占的百分比。

pca = PCA(n_components='mle')
X1 = pca.fit_transform(X)
print(X1)
print (pca.explained_variance_)
print(pca.explained_variance_ratio_) 
print(pca.n_components_)

[[ 1.38340578]
 [ 2.22189802]
 [ 3.6053038 ]
 [-1.38340578]
 [-2.22189802]
 [-3.6053038 ]]
[ 6.61628593]
[ 0.99244289]
1

当参数ncomponents='mle'时，会自动选取满足要求的n个特征。 **n_components**: 返回选取的特征数。

fit_transform(X): 用数据 X 训练 PCA 模型，并返回降维后的数据。

pca = PCA(n_components=0.95)
pca.fit(X)
print (pca.explained_variance_)
print(pca.explained_variance_ratio_) 
print(pca.n_components_)

[ 6.61628593]
[ 0.99244289]
1

当参数 n_components=0.95时，指定了主成分方差和比例至少占95%。由于第一个主成分占投影特征的方差比例高达99%。只选择这一个特征维度便可以满足95%的阈值。

参考资料

1. 特征哈希(Feature Hashing)
2. Trevor Hastie et al. The Elements of Statistical Learning, 2001.
3. Kilian Weinberger et al. Feature Hashing for Large Scale Multitask Learning, 2010.
4. Joshua Attenberg et al. Collaborative Email-Spam Filtering with the Hashing-Trick, 2009.
5. https://www.zhihu.com/question/264165760/answer/277634591
6. sklearn.feature_extraction.FeatureHasher
7. sklearn学习笔记2 Feature_extraction库
8. 特征选择和稀疏学习
9. 《西瓜书》笔记11：特征选择与稀疏表示（三）
10. 特征选择与稀疏学习
11. https://www.zhihu.com/question/24124122/answer/50403932
12. https://blog.csdn.net/u014595019/article/details/52433754
13. PCA算法详解
14. 主成分分析（PCA）原理详解
15. 主成分分析PCA算法：为什么去均值以后的高维矩阵乘以其协方差矩阵的特征向量矩阵就是“投影”？
16. 用Python的sklearn库进行PCA(主成分分析)
17. 用scikit-learn学习主成分分析(PCA)
18. 独立成分分析（Independent Component Analysis）
19. 独立成分分析 ( ICA ) 与主成分分析 ( PCA ) 的区别在哪里？
20. 独立成分分析ICA系列4:ICA的最优估计方法综述
21. ICA-独立成分分析
22. 独立成分分析Independent component analysis(ICA)
23. 线性判别分析LDA原理总结
24. 一文读懂特征工程
25. 线性判别分析LDA详解
26. LinearDiscriminantAnalysis
27. 用scikit-learn进行LDA降维
28. https://blog.csdn.net/u010705209/article/details/53518772
29. https://blog.csdn.net/u012162613/article/details/42214205
30. https://blog.csdn.net/qianhen123/article/details/40077873
31. https://github.com/ceys/jdml/wiki/ALS
32. 美团点评技术团队之深入FFM原理与实践
33. [深度学习笔记（一）稀疏自编码器] (https://blog.csdn.net/u010278305/article/details/46881443)
34. Field-aware Factorization Machines for CTR Prediction ,Yuchin Juan et al.
35. Factorization Machines, Steffen Rendle et al.[2010]
36. http://deeplearning.stanford.edu/wiki/index.php/UFLDL_Tutorial
37. 局部线性嵌入(LLE)原理总结
38. Locally linear embedding(LLE)局部线性嵌入-降维
39. LocallyLinearEmbedding
40. 用scikit-learn研究局部线性嵌入(LLE)
41. 聚类和降维的区别与联系
42. 聚类算法
43. 受限玻尔兹曼机（RBM）学习笔记
44. 受限制玻尔兹曼机RBM原理简介
45. 从SNE到t-SNE
46. t-SNE完整笔记
47. SNE降维与可视化
48. 比PCA降维更高级 —— t-SNE聚类算法实现指南