引入原因

为了防止过拟合，我们通常的解决办法有：增加数据，正则化，降维等方法。

为什么要引入降维呢？
当数据量过大特征过多的时候，数据的维度过高有可能会导致维度灾难。在没有更过数据进行补充的情况下，一般都是做降维处理。
而且在高维情况下，数据会越来越稀疏，并且数据会分布在样本空间的边缘地区，这绝对不是我们想要的结果。

下面看看降维的主要方法：
降维的主要方法：
1.直接降维----特征选择
2.线性降维----PCA，MDS
3.非线性降维----isomap，LLE

均值和方差的矩阵形式

引入数据：$X=(x_1,x_2,...,x_N)_{N×P}^T=\begin{pmatrix} x_1^T\\ ...\\ x_N^T \end{pmatrix}=\begin{pmatrix} x_{11} & ... &x_{1p}\\ .& .& .\\ x_{N1}& ... &x_{Np} \end{pmatrix}_{N×P}$

样本均值：$\bar x_{p×1}=\frac{1}{N}\sum x_i$
样本方差：$S_{p×p}=\frac{1}{N}\sum_{i=1}^{N}(x_i-\bar x)(x_i-\bar x)^T$

将上面的均值和方差写成矩阵形式：
样本均值：$\bar x=\frac{1}{N}\sum x_i=\frac {1}{N}(x_1,...,\bar x)\begin{pmatrix} 1\\ ...\\ 1 \end{pmatrix}=\frac{1}{N}X^T1_N$
样本方差：

上式中的H矩阵，我们称为中心矩阵。H具有一些特殊的性质，如：$H^T=H,H^N=H$

PCA

主成分分析是最常用的一种降维方法。
给定一个特征空间，如何用一个超平面对所有的样本进行恰当的划分？

我们可以想象到的，如果存在这样一个超平面，那么它应该具有这样两种性质：
1.最大投影方差。
2.最小重构距离。
也即是样本点到这个超平面的距离都足够近，样本点在这个超平面上的投影尽量能分开。

那我们就从这两个角度分别看看PCA的推导

最大投影方差

假设我们要找的方向是$u,$
第一步，中心化。中心化的目的是为了方便计算。做法就是用样本-均值$x_i-\bar x，$将样本都集中在坐标轴附近。
假定我们要找的方向就是$u_1,$并且它的模$||u_1||=1.$我们的数据$x_i-\bar x$到找的向量$u_1$的距离就是$(x_i-\bar x)^Tu_1$。

投影我们用$J$表示，N个点的投影方差就是:

$J=\frac{1}{N}\sum_{i=1}^{N}[(x_1-\bar x)^Tu_1]^2$

$=\sum_{i=1}^{N}\frac{1}{N}u_1^T(x_1-\bar x)(x_1-\bar x)^Tu_1$

$=u_1^T[\sum_{i=1}^N\frac{1}{N}(x_1-\bar x)(x_1-\bar x)^T]u_1$

$=u_1^TSu_1$

最后我们要找的$u_1$就出来了，
$\hat u_1=argmaxu_1^TSu_1$

$s.t.u_1^Tu_1=1$

用拉格朗日乘子法对其求解，可以得到$Su_1=\lambda_1 u_1$最终的结果。之后对协方差矩阵$S$进行特征值分解求得特征值，这就是主成分分析的解。

最小重构代价

换个角度，我们转换一下坐标系也就是把$u_1,u_2$作为坐标轴，原先的点可以表示维$x_i=(x_i^Tu_1)u_1+(x_i^Tu_2)u_2$

PCA算法描述

输入：样本集$D=\left \{ x_1,x_2,...,x_m\right \}$，低维空间维数$d'$。

过程：
1.对书友样本进行中心化：$x_i<--x_i-\frac{1}{m}\sum_{i=1}^{m}x_i$;
2.计算样本的协方差矩阵$XX^T$
3.对协方差矩阵$XX^T$做特征值分解
4.取最大的$d'$个特征值对应的特征向量$w_1,w_2,...,w_d$。

输出：投影矩阵$W^*=(w_1,w_2,...,w_{d'})$

上面算法中的维数$d'$通常由用户事先指定。而且低维空间和高维空间有所不同，因此对应最小的$d-d'$个特征值的特征向量被舍弃了，这就是降维导致的结果。但是舍弃这部分信息并不代表不好：数据受到噪声影响的时候，最小的特征值对应的特征向量往往和噪声有关，舍弃他们在一定程度上有降噪的效果；另一方面，舍弃后我们的采样密度也会更大，而这也正是我们的动机。