PCA主成分分析

21 Feb 2019 Category: 算法

主成分分析(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 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)} ) $ 是常数,所以最小化目标函数为:

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

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

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

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

基于投影后最大间隔(投影方差最大)

投影后的方差为

跟上面一样。

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)}) $

评论