正文借使你曾经知晓了PCA算法的基本原理和步骤.,PCA 的明亮流于表面

很久之前写过一篇 PCA
的小白教程,不过是因为当下对
PCA 的驾驭流于表面,所以只是介绍了须臾间 PCA
的算法流程。前几天在数图课上有时听到 PCA
在图像压缩上的选拔,突然通晓了一点实质性的事物,那里趁热记录一波。

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

图片 2


PCA 算法

首先如故简单回看下 PCA 的算法流程。

咱俩把样本数据 \(x\)
归一化后,总括其协方差矩阵 \(C_x\),然后总计 \(C_x\) 的特征向量,构造出多个特征向量矩阵
\(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\)映射到三个天性空间\(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\)
的特征向量组成的矩阵,它的率先行代表最大特征值对应的特征向量,第叁行表示第壹大特征值对应的特征向量。\(C_y\) 对角线上的 \(\lambda_k\) 代表 \(C_x\)
的表征值,而且是比照从大到小排序的(\(\lambda_1 > \lambda_2 > \dots >
\lambda_n\))。

以此新的协方差矩阵有3个很重庆大学的本性,除了对角线上的成分,其余因素通通是
0。要了然,协方差矩阵中,对角线上的因素表示方差,非对角线上的要素表示协方差。那注解,经过
PCA 处理后,我们把原先的数据 \(x\),转变成种种分量之间没有其余关联(协方差为
0)的数据 \(y\)!我觉着那就是 PCA
的精髓所在,也是我们利用 PCA 算法的平昔目标。

除此以外,PCA 还经常用来降维处理,那么为何 PCA 的降维效果会那么好?

第3要显然一点,降维不是不管都能降的,最好的降维方法是要硬着头皮保存重要的音信,而忽略次要的新闻。在
PCA
中,大家一般是对协方差矩阵的特色值按从大到小排序,然后摒弃一些相比较小的特征值(以及这么些特征值对应的特征向量),这样重复总结获得
\(y\)
后,它的协方差矩阵恐怕是以此样子的:
\[ C_y=\begin{bmatrix} \lambda_1 & & &
0 \\ & \lambda_2 & & \\ & & \ddots & \\ 0 & & & \lambda_k
\end{bmatrix} \]
(大家扬弃掉了 \(n-k\)
个特征向量,将数据由 \(n\) 维降到
\(k\) 维)

要领悟,这一个特征值(也许说方差)都以比照从大到小排序的,也正是说,大家在降维时,舍弃掉了那多个特征值比较小的轻重。这么做是顺应规律的,因为数量的方差越大,申明分布越广,那样,大家还原这几个数量的难度是越大的,而方差越小,注脚数据分布越集中,还原它们的难度就越小(方差为
0
的话,用四个数就可以代表享有样本了)。所以,降维时,大家尽量保存那么些方差大的多寡,而忽视那个方差小的。本文开篇的图中付出二个影象的演说,大家把一个二维的数量映射到一维时,也是先行映射到方差大的那一维上,那样,原数据的分布规律能够最大限度的保留下来,消息的保留也是最完全的。

均值化处理, 使每种维度的均值为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\)有二个特征值\(\lambda\),对应的已规范化特征向量为\(u\):
\[ \bar Z \bar Z^T u = \lambda u
\]
两边同时左乘二个\(\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的终极目标是降维, 会有二个输入向量\(x\), 到时又可与\(Z\)协作起来, 构成\(\kappa\).

对向量\(x\)举办降维操作

个中没写出来的步子, 即特征值降序排列取前\(d\)个照应的特征向量,
与平时的PCA是一致的.
降维操作通过\(x\)在四个基上的影子操作即可表达.
\[ 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} \]