BLOG

个人博客,记录学习与生活

主成分分析

Published Oct. 3, 2020, 10:41 p.m. by kkk

PCA是使用得最普遍的降维算法,是一种非监督式线性降维算法,要将数据降维到$k$维子空间,包括两个步骤:

  • 找出最能保存数据方差的超平面(包括k个基向量)
  • 将数据投影到该超平面

这$k$个基向量又称为主成分。经过数学计算可知,这些基向量分别是数据矩阵最大的$k$的特征值所对应的单位特征向量。

注:PCA假设数据最初是以原点为中心

实际上包括两个思路:

  1. 最大重构性
  2. 最大可分性

其中最大可分性就对应上述步骤,方差最大化。今天花了几乎一整天推导,发现细节化之后就很容易绕进去,然后作出了几点改进:

  • 不必列出具体的样本数,用随机变量代替
  • 将运算高度向量化,部分步骤推导的形式可以具体化之后确定

1. 数据定义

全程并不会讨论具体的样本个数。

原数据:随机变量$X; X = {x_1, x_2, \cdots, x_m}$其中$m$为随机变量维度。

为了后续计算便捷,原数据是经过了中心化的,有:$E(\mathbf x)=0$

投影(降维)后的数据:$Z; Z={z_1,z_2,\cdots, z_d}$,$d$为投影后的维度。

投影矩阵(转移矩阵)为$W;W={w_1, w_2, \cdots, w_d}$,其中$w_i$为基向量,有$\vert w_i\vert=1;w_i^Tw_j=0,i\not=j$

于是有:$Z = W^TX; z_i = w_i^TX$

2. 基于最大可分性

基本思想:将源数据的维数从$n$降到$k$($k<n$)​,并最大程度上保持方差。即将数据从原空间映射到由k个线性无关向量张成的子空间

对$Z$中各分量按方差从大到小进行排序,如果有${{z_1, z_2,\cdots,z_d}}$,则称$z_1$为第一主成分,$z_i$为第$i$主成分。就$z_i$的方差: $$ \begin{align} D(z_i) &= E(z_i-E(z_i))^2 \\ &= E(z_i)^2 \\ &= E(w_i^TX)^2 \\ &= E(w_i^TXX^Tw_i) \\ &= w_i^TE(XX^T)w_i \\ &= w_i^T\Sigma w_i \end{align} $$ 对该主成分,优化目标为: $$ \arg\max_{w_i} D(z_i) $$ 利用拉格朗日乘子法,拉格朗日函数为: $$ w_i^T\Sigma w_i - \lambda (w^Tw-1) $$

上式对$w_i$进行求导并令整式为0,(对矩阵求导)有: $$ 2\Sigma w_i-2w_i\lambda = 0 $$ 化简有: $$ \Sigma w_i=\lambda w_i $$ 代入$D(z_i)$可得$D(z_i)=\lambda$。方差为协方差矩阵$\Sigma$的特征值,投影向量为对应的单位化特征向量

为保留最多的方差信息,并降维到$k$,可对协方差矩阵进行特征值分解,将特征值从大到小排列,取前$k$个,对应的单位化特征向量即构成投影矩阵(转移矩阵)。

3. 基于最大重构性思想

实际上指的是,原向量与在投影超平面上的投影向量之后距离最小,也是最小平方误差

向量$x_i$的投影坐标为:$z_i = (x_i^TW)^T$,投影向量为$\hat x_i=\sum_{j=1}^dz_{ij}w_j$,优化目标为: $$ \arg\min_W \sum_{i=1}^m \Vert x_i - \hat x_i\Vert_2^2 $$

优化处理之后最终可以得到跟基于最大可分性完全相同的结果。

4. 计算步骤

  1. 将数据进行预处理(通常为中心化标准化
  2. 确定要降维成的维数$k$(即k个主成分)
  3. 计算数据的协方差矩阵
  4. 对协方差矩阵进行特征值分解,将对角矩阵元素按从大到小排列,取对角矩阵的前$k$项,对应的特征向量为降维子空间的基向量

另外的计算方式:

  • 可以采用相关矩阵替代上面的协方差矩阵,顺便可以去掉对数据的预处理步骤
  • 采用奇异值分析代替特征值分解,对数据矩阵的转置代替上面的协方差矩阵。

Share this post
< Pre: 读论文9月第三周 Pos: 读论文9月第四周 >
No comments
Similar posts
Add a new comment