背景

数据科学中有个经典数据处理技术：Principal components analysis（简称PCA）。英文直译为：主成分分析。

数据的抽象

数据科学研究中，一个数据样本通常抽象成特征向量（feature vector），例如：
$$
x=(x^{(1)},x^{(2)},…,x^{(i)},…,x^{(n)})^T
$$
这里$x^{(i)}$表示第$i$个特征（数值），这是一个$n$维特征的样本数据。例如人脸图像（灰色），每张图片的像素值可以转换成一个列向量，像素值即特征。

进一步抽象，如果给这些特征向量赋予欧式度量（拓扑结构），这些特征向量取自$R^n$空间（n维欧式空间）。这样我们就可以在欧式空间框架下研究数据集了。

当然你可以赋予别的度量，甚至赋予一个拓扑结构（这是一件有趣的事情，读者可以思考探索）。

数据的降维

降维的目的

当我们将数据抽象为欧式空间的向量，欧式空间

剔除数据集的特征存在冗余信息。

数据的采集过程中，采集特征之间本身存在相关性（线性或非线性）。去除冗余信息后，减少计算量。
减少数据集中噪声信息。
高维数据的降维可视化。

将高维空间的数据映射到3维或者2维欧式空间中，降维映射会保持高维数据的结构信息。比如高维空间相似的点，在低维可视化空间中体现为距离较近，我们说降维映射是保持距离的。

降维和特征选择

在数据特征工程中，我们会对原始数据进行特征选择（feature selection），提取主要的特征因素，直接删除冗余或者认为次要的数据特征。广义上，这也属于数据降维技术，并且具有较强的可解释性。

另外数据降维还包含：

主成分分析

最大方差形式

假设${x_i}_{i=1}^{S}$ 是取自$R^n$欧式空间的数据点（列向量），即$x_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(j)},…,x_i^{(n)})^T$，我们将$R^n$中的数据点投影到$R^m$（$m<n$）空间中，同时最大化投影（正交子空间投影）数据在$R^m$空间中的方差。

约定向量均为列向量

首先我们考虑$m=1$的情况，即$R^1$空间。这时我们可以挑选单位向量$u\in R^n$作为$R^1$的方向。因为$u^Tu=1$（欧式距离），所以数据点在$u$上的投影向量为 $(x_i^Tu)u$，坐标值为标量$x_i^Tu$。数据点在新的空间中的均值为：
$$
A=\frac{1}{S}\sum_{i=1}^S{x_i^Tu}=\frac{1}{S}\sum_{i=1}^S\sum_{j=1}^nx_{i}^{j}u_{i}^{j}=\sum_{j=1}^n(\frac{1}{S}\sum_{i=1}^Sx_{i}^{j})u_{i}^{j}=\overline{x}^Tu
$$
其中$\overline{x}=(\frac{1}{S}\sum_{i=1}^Sx_{i}^{j})_{j=1,…,n}^T$

数据点在新的空间中方差为：
$$
V=\frac{1}{S}\sum_{i=1}^{S}(x_i^Tu-\overline{x}^Tu)^2=u^TCu
$$
其中C是数据的协方差矩阵（对称矩阵），定义为：
$$
C=\frac{1}{S}\sum_{i=1}^{S}(x_i-\overline{x})^T(x_{i}-\overline{x})
$$
关于$u$最大化方差$V=u^TCu$ ，引入拉格朗日乘子，即求解最大化函数：
$$
f(u,\lambda)=u^TCu+\lambda(1-u^Tu)
$$
关于$u$求偏导数：
$$
\frac{\partial f}{\partial u}=Cu-\lambda u=0
$$
显然$u$是矩阵$C$的特征值$\lambda$的特征向量。这时候方差 $V=u^TCu=u^T\lambda u=\lambda$

所以我们选择协方差矩阵$C$的最大特征值对应的特征向量即可。

对于$m>1$的情况，我们的最优目标是使得原始数据点在$R^m$的每个方向上$u_i$（$u_i \in U={u_1,u_2,…u_m}， \Vert u_i\Vert=1 $）的投影方差均最大化。即我们要挑选合适U集合，使得数据点在每个$u_i \in U$上的投影方差最大。

协方差矩阵是实对称矩阵，可以正交对角化，对角线上的元素为矩阵特征值集合。

有上面的推导容易知道U为特征值大小前$m$名所对应的特征向量的集合。

最小误差形式

假设${u_j}_{j=1}^n$是$R^n$空间的单位正交基（$u_i u_j=\delta_{ij}$），那么对于数据点${x_i}_{i=1}^S$可以由基向量线性表出：
$$
x_i=\sum_{j=1}^na_{ij}u_j=\sum_{j=1}^n(x_iu_j)u_j
$$
我们的目标是对空间降维重建，使得数据点在新的坐标系（维度为$m<n$）下得到近似表达，不失一般性，我们假设挑选基向量为${u_i}_{i=1}^m$,数据点在新的坐标系上的表示为：
$$
\hat{x_i}=\sum_{j=1}^ma_{ij}u_j
$$
我们的目标是最小化重建误差，定义为：
$$
J=\frac{1}{S}\sum_{i=1}^S\Vert x_i-\hat{x_i}\Vert^2=\frac{1}{S}\sum_{i=1}^S\Vert \sum_{j=1}^na_{ij}u_j-\sum_{j=1}^ma_{ij}u_j\Vert^2=\frac{1}{n}\sum_{i=1}^S\Vert\sum_{j=m+1}^na_{ij}u_j\Vert^2
$$
由单位正交性，得到：
$$
J=\frac{1}{S}\sum_{i=1}^S\sum_{j=m+1}^na_{ij}^2=\frac{1}{S}\sum_{i=1}^S\sum_{j=m+1}^nu_j^Tx_ix_i^Tu_j=\sum_{j=m+1}^nu_j^TCu_j
$$

降维和特征选择

数学原理

矩阵和线性变换

算法实现过程

特征分解

奇异值分解（SVD）

算法的深度理解

知乎文章：https://www.zhihu.com/question/36348219

第一层理解（最大方差投影）

第二层理解（最小重建误差）

第三层理解（高斯先验误差）

第四层理解（线性流行对齐）

矩阵知识准备

KLT（Karhunen Loeve Transform）变换

KLT变换最早用于信号学中用于压缩信息量，用于除去输入数据的相关性。首先KLT是一个线性变换，所以除去的是线性相关性。