很久从前写过一篇 PCA,本文固然你曾经领会了PCA算法的基本原理和步骤.

从古至今写过一篇 PCA
的小白教程,但是出于当下对
PCA 的知情流于表面,所以只是介绍了一晃 PCA
的算法流程。前几日在数图课上偶然听到 PCA
在图像压缩上的行使,突然领悟了有些实质性的东西,那里趁热记录一波。

先看一眼PCA与KPCA的可视化分歧:
图片 1
PCA算法是怎么跟协方差矩阵/特征值/特征向量勾搭起来的?里曾经推导过PCA算法的小半有的原理.
正文若是你已经明白了PCA算法的基本原理和步骤.

图片 2


PCA 算法

第1依然不难回想下 PCA 的算法流程。

我们把样本数据 \(x\)
归一化后,计算其协方差矩阵 \(C_x\),然后计算 \(C_x\) 的特征向量,构造出1个特征向量矩阵
\(A\),最后把 \(x\)
通过该矩阵映射到一个新的半空中,获得的向量 \(y\) 正是能反映 \(x\) 主要成份的向量了。

从原本输入空间到特征空间

熟视无睹PCA算法的输入:

  • 教练数据集\(D={x_1, \dots,
    x_m}\), \(x_i \in
    R^n\).
  • 对象降维维度: \(d\)
  • 新的测试数据\(x\)

Kernel PCA则要求在输入中进入二个钦赐的 kernel function \(\kappa\).
笔者们早已通晓, 各种合法的 kernel function, 即对称和正半定的函数,
都能找到至少二个相应的feature mapping function \(\Phi\). 现在\(\kappa\)是已知的, \(\Phi\)是隐蔽的:存在, 但对我们来说未知.
用\(\Phi\)把每种陶冶样本\(x_i\)映射到1个特色空间\(H\), 得到\(z_i\):
\[ z_i = \Phi(x_i) \qquad Z = \left[
\begin{matrix} z_1^T \\ z_2^T \\ \vdots \\ z_m^T
\end{matrix} \right] \]

PCA 在做什么样

那便是说,那种空间映射有怎么样含义吗?难点要回来协方差矩阵 \(C_x\)
上。我们掌握,协方差矩阵是三个对称矩阵,在线性代数中,对称矩阵的特征向量是相互正交的。而大家把
\(x\) 通过这几个特征向量矩阵映射到
\(y\),其实就是把原本的数量由最初的
\([e_1, e_2, \dots, e_n]\)
的单位坐标系,调整到那些正交的特征向量组成的坐标系下,如下图所示:

图片 3

那种坐标变换的意义又在哪呢?

设若仔细分析,大家就会发现,这个新获得的向量 \(y\) 的均值为 \(0\),而且它们的协方差矩阵为:
\[ C_y=AC_xA^T=\begin{bmatrix}
\lambda_1 & & & 0 \\ & \lambda_2 & & \\ & & \ddots & \\ 0 & &
& \lambda_n \end{bmatrix} \]
这里,\(A\) 是由 \(C_x\)
的特征向量组成的矩阵,它的首先行代表最大特征值对应的特征向量,第贰行表示第2大特征值对应的特征向量。\(C_y\) 对角线上的 \(\lambda_k\) 代表 \(C_x\)
的表征值,而且是服从从大到小排序的(\(\lambda_1 > \lambda_2 > \dots >
\lambda_n\))。

其一新的协方差矩阵有三个很重点的质量,除了对角线上的要素,别的因素通通是
0。要知道,协方差矩阵中,对角线上的因素表示方差,非对角线上的要素表示协方差。那表明,经过
PCA 处理后,大家把原本的数据 \(x\),转变成种种分量之间没有此外关联(协方差为
0)的数据 \(y\)!小编觉得那多亏 PCA
的优异所在,也是大家选用 PCA 算法的平素目的。

其它,PCA 还时时用来降维处理,那么为何 PCA 的降维效果会那么好?

第二要强烈一点,降维不是不管都能降的,最棒的降维方法是要硬着头皮保存主要的新闻,而忽视次要的音讯。在
PCA
中,大家一般是对协方差矩阵的风味值按从大到小排序,然后舍弃一些相比小的特征值(以及那几个特征值对应的特征向量),那样重复计算获得
\(y\)
后,它的协方差矩阵也许是其一样子的:
\[ C_y=\begin{bmatrix} \lambda_1 & & &
0 \\ & \lambda_2 & & \\ & & \ddots & \\ 0 & & & \lambda_k
\end{bmatrix} \]
(我们扬弃掉了 \(n-k\)
个特征向量,将数据由 \(n\) 维降到
\(k\) 维)

要知道,这么些特征值(或许说方差)都以依照从大到小排序的,也正是说,大家在降维时,扬弃掉了那3个特征值相比较小的分量。这么做是吻合常理的,因为数量的方差越大,注解分布越广,那样,大家还原这个数据的难度是越大的,而方差越小,声明数据分布越集中,还原它们的难度就越小(方差为
0
的话,用三个数就可以代表全数样本了)。所以,降维时,我们尽量保留那么些方差大的数目,而忽视那多少个方差小的。本文开篇的图中付出1个形象的演说,大家把贰个二维的多少映射到一维时,也是先行映射到方差大的那一维上,那样,原数据的遍布规律能够最大限度的保留下去,音讯的保存也是最完全的。

均值化处理, 使各种维度的均值为0

均值向量:
\[ \mu = \frac 1m Z^T
\left[\begin{matrix}1 \\ 1 \\ \vdots
\\1\end{matrix}\right]_{m\times 1} = \frac 1m Z^T \beta
\]
从\(Z\)中每一行都减去\(\mu^T\):
\[ \bar Z = Z – \beta \mu^T = Z – \frac
1m \beta \beta^T Z \]

协方差矩阵正交对角化

这一步有点绕.
因为协方差矩阵\(C = \bar Z^T \bar
Z\)中有不解函数\(\Phi\),
所以不能直接对角化. 在在此之前推导kernel svm和kernel linear
regression算法的经过中, 大家都利用了kernel matrix:
\[ K = \left [ \begin{matrix}
\Phi(x_1)^T \Phi(x_1), &\Phi(x_1)^T \Phi(x_2), &\dots
&\Phi(x_1)^T \Phi(x_n) \\ \vdots &\dots &\dots &\vdots \\
\Phi(x_n)^T \Phi(x_1), &\Phi(x_n)^T \Phi(x_2), &\dots
&\Phi(x_n)^T \Phi(x_n) \end{matrix} \right ] \]
此次也不例外.
先看那一个看似于\(K\)的均\(K\)矩阵:
\[ \bar K = \bar Z \bar Z^T
\]
假设\(\bar K\)有3个特征值\(\lambda\),对应的已规范化特征向量为\(u\):
\[ \bar Z \bar Z^T u = \lambda u
\]
两边同时左乘1个\(\bar Z^T\):
\[ \bar Z^T \bar Z \bar Z^T u = \bar
Z^T\lambda u \]
\[ \to C \bar Z^T u =\lambda \bar Z^Tu
\]
这代表\(\bar Z^T
u\)是协方差矩阵\(C\)的特征向量, 对应的特征值也是\(\lambda\).
就此, 我们只须求专业正交对角化\(\bar
K\), 就能对角化\(C\).
规范正交对角化操作的靶子为:
\[ \bar K = \bar Z \bar Z^T = ( Z –
\frac 1m \beta \beta^T Z)( Z^T – \frac 1m Z^T \beta \beta^T) =
ZZ^T – \frac 1m \beta \beta^T ZZ^T – \frac 1m ZZ^T \beta \beta^T +
\frac 1{m^2} \beta \beta^T ZZ^T \beta \beta^T = K – \frac 1m
\beta \beta^T K – \frac 1m K\beta \beta^T + \frac 1{m^2} \beta
\beta^T K \beta \beta^T \]

特征向量规范化

由\(\bar K\)的规范化特征向量\(u\), 大家能够获取\(C\)的特征向量\(\bar Z^Tu\), 但它不肯定是单位向量,
所以大家还要对它实行规范化处理.
\[ ||u||^2 = u^T\bar Z \bar Z^Tu =
u^T\lambda u = \lambda \]
\[ p = \frac {\bar Z^Tu}{||\bar Z^Tu||}
= \frac {\bar Z^Tu}{\sqrt \lambda} \]
留神到了吗, 那里如故有\(\bar
Z\)存在, 而\(\bar Z = Z – \frac 1m
\beta \beta^T Z\), \(Z\)因为含有未知的\(\Phi\)所以也是雾里看花的.
可是PCA的末梢指标是降维, 会有3个输入向量\(x\), 到时又可与\(Z\)合作起来, 构成\(\kappa\).

对向量\(x\)进行降维操作

中等没写出来的步子, 即特征值降序排列取前\(d\)个照应的特征向量,
与平日的PCA是同等的.
降维操作通过\(x\)在2个基上的阴影操作即可表明.
\[ p^T\Phi(x) = \frac {u^T \bar Z
\Phi(x)}{\sqrt \lambda} = \frac 1{\sqrt \lambda} u^T ( Z – \frac
1m \beta \beta^T Z) \Phi(x) = \frac 1{\sqrt \lambda} u^T (k –
\frac 1m \beta \beta^T k) = \frac 1{\sqrt \lambda} u^T (I_{m
\times m} – \frac 1m \beta \beta^T)k \]
其中, \(\lambda\)与\(u\)分别是\(\bar
K\)的特征值和呼应的规范化特征向量,
\[ k = \left [ \begin{matrix}
\kappa(x_1, x) \\ \kappa(x_2, x) \\ \vdots \\ \kappa(x_m,
x) \\ \end{matrix} \right] \qquad \beta =
\left[\begin{matrix}1 \\ 1 \\ \vdots
\\1\end{matrix}\right]_{m\times 1} \]