PCA主成分分析

主成分分析(Principal components analysis,PCA) 是数据降维最重要的方法之一。主要通过找出数据的主要成分，替代原有数据。减少后续数据处理的维度。

PCA 主成分分析主要是找到一个超平面，使得原数据距离超平面尽可能的进，数据在超平面上的投影尽可能的远。如果找到这么一个超平面，则是有这个超平面坐标系表示原有数据。（变换后的维度一般提前给定，小于原有数据维度）

根据PCA的两个目标，原数据到超平面的距离尽可能小，在超平面上的点之间尽可能远，推导方式分为两种。

假设原始数据（做了中心化之后的数据）为$X_{m \times n}$,超平面的坐标系为$w={w_1,w_2,…w_k}$为标准正交基，则远数据到超平面的投影就是在坐标系的投影。$Y_{m \times k}$表示原始数据在新坐标系下的投影后矩阵。

特征值分解

根据PCA的两个目标，原数据到超平面的距离尽可能小，在超平面上的点之间尽可能远，推导方式分为两种。

假设原始数据（做了中心化之后的数据）为$X_{m \times n}$ ,超平面的坐标系为$w={w_1,w_2,…w_k}$为标准正交基，则远数据到超平面的投影就是在坐标系的投影。$Y_{m \times k}$表示原始数据在新坐标系下的投影后矩阵。

基于最小投影距离

$x^{(j)}$ 表示第$j$个样本，$y^{(j)}$第j个样本投影到新坐标系下的坐标。要计算样本到投影点的距离，需要把投影的坐标转换成原坐标。

$y^{(j)} = W^T x^{(j)}$

$z^{(j)} = \sum_{j}^m w_j^T y^{(j)} = W^T y^{(j)} $ 所以投影在原坐标系的坐标 $z^{(j)} =W y^{(j)}$

所以原样本到投影平面的距离为:

$$\sum_{j}^m \parallel z^{(j)} - x^{(j)} \parallel ^2$$ $$= \sum_{j}^m \parallel W y^{(j)}-x^{(j)} \parallel ^2$$ $$= \sum_{j}^m ( y^{(j)T}W^T W y^{(j)} + x^{(j)T}x^{(j)} -2 (W y^{(j)})^T x^{(j)} )$$ $$= \sum_{j}^m ( y^{(j)T}y^{(j)} + x^{(j)T}x^{(j)} -2 y^{(j)T}W^Tx^{(j)})$$ $$= \sum_{j}^m ( y^{(j)T}y^{(j)} + x^{(j)T}x^{(j)} -2 y^{(j)T}y^{(j)} )$$ $$= \sum_{j}^m ( -y^{(j)T}y^{(j)} + x^{(j)T}x^{(j)} )$$ $$= \sum_{j}^m ( -x^{(j)T}W W^Tx^{(j)} + x^{(j)T}x^{(j)} )$$ $$= \sum_{j}^m ( -x^{(j)T}W W^Tx^{(j)} ) +\sum_{j}^m ( x^{(j)T}x^{(j)} )$$

到这里有些不理解,怎么转换成矩阵的秩。

$ = -\sum_{j}^m tr( W^T x^{(j)}x^{(j)T} W ) + \sum_{j}^m ( x^{(j)T}x^{(j)} ) $

$ = -tr( W^T \sum_{j}^m(x^{(j)}x^{(j)T}) W ) + \sum_{j}^m ( x^{(j)T}x^{(j)} ) $

$ = -tr( W^T XX^T W ) + \sum_{j}^m ( x^{(j)T}x^{(j)} ) $

其中$\sum_{j}^m(x^{(j)}x^{(j)T})$是原样本的协方差矩阵，$\sum_{j}^m ( x^{(j)T}x^{(j)} ) $ 是常数，所以最小化目标函数为:

$$argmin -tr( W^T XX^T W ) s.t. W^TW=I$$

使用拉格朗日算子计算最小值

$ J(w) = -tr( W^T XX^T W ) - \lambda(W^TW-I) $ ,对$W$ 求偏导 $−XX^TW+\lambda W=0$ 所以有:

$XX^TW=\lambda W$ ,所以 $W$ 是 $XX^T$的特征向量组成的矩阵，$\lambda$为$XX^T$ 特征值组成的对角矩阵，特征值在主对角线上，其他为0

当我们将数据集从n维降到k维时，需要找到最大的k个特征值对应的特征向量。这k个特征向量组成的矩阵W即为我们需要的矩阵,使用$y^{(j)}=W^Tx^{(j)}$依次对原样本进行投影。得到降维后的矩阵。

基于投影后最大间隔（投影方差最大）

投影后的方差为

$$\sum_{j}^m ( (W^T x^{(j)})^T (W^T x^{(j)}) )$$

$=\sum_{j}^m ( x^{(j)T}WW^Tx^{(j)})$ $=tr(W^T \sum_{j}^m (x^{(j)T} x^{(j)} ) W)$

跟上面一样。

PCA算法步骤

输入：n维样本集$D=(x^{(1)},x^{(2)},…,x^{(m)})$，要降维到的维数k.

输出：降维后的样本集$\tilde{D}$

1) 对所有的样本进行中心化： $x^{(i)}=x^{(i)}−\frac{ \sum_{j}^m x^{(j)} } {m}$

2) 计算样本的协方差矩阵$XX^T$

3) 对矩阵$XX^T$进行特征值分解

4）取出最大的k个特征值对应的特征向量$(w_1,w_2,…,w_k)$, 将所有的特征向量标准化后，组成特征向量矩阵$W$。

5）对样本集中的每一个样本$x^{(i)}$,转化为新的样本$ y^{(i)}=W^Tx^{(i)} $

6) 得到输出样本集$\tilde{D}=(y^{(1)},y^{(2)},…,y^{(m)}) $