特征分解以及奇异值分解

首先我们来看几个公式
variance公式:
$\sigma ^ { 2 } ( x ) = \frac { 1 } { n } \sum _ { i = 1 } ^ { n } \left( x _ { i } - \mu \right) ^ { 2 }$
covariance公式, 即 $E [ ( x - E [ x ] ) ( y - E [ y ] ) ]$ :
$\sigma ( x , y ) = \frac { 1 } { n } \sum _ { i = 1 } ^ { n } \left( x - \mu _ { x } \right) \left( y - \mu _ { y } \right)$
当随机变量x和y相同时, covariance等同于variance: $\sigma ( x , x ) = \sigma ^ { 2 } ( x )$
如果协方差covariance等于0说明这两个随机变量不相关
协方差矩阵:
$\mathbf { \Sigma } = \left[ \begin{array} { c c c c } { \sigma \left( X _ { 1 } , X _ { 1 } \right) } & { \sigma \left( X _ { 1 } , X _ { 2 } \right) } & { \dots } & { \sigma \left( X _ { 1 } , X _ { n } \right) } \\ { \sigma \left( X _ { 2 } , X _ { 1 } \right) } & { \sigma \left( X _ { 2 } , X _ { 2 } \right) } & { \dots } & { \sigma \left( X _ { 2 } , X _ { n } \right) } \\ { \vdots } & { \vdots } & { \ddots } & { \vdots } \\ { \sigma \left( X _ { n } , X _ { 1 } \right) } & { \sigma \left( X _ { n } , X _ { 2 } \right) } & { \dots } & { \sigma \left( X _ { n } , X _ { n } \right) } \end{array} \right]$
均值中心化(mean centering): 指得是将一系列的样本点的均值置0,也就是每个样本点的值减去所有样本点的均值, 这样新生成的所有样本点的均值即为0。
现在我们设z:
$z=\left[ \begin{array} { c c c c } {v_{11}}&{v_{12}}&v_{13}&...\\{v_{21}}&{v_{22}}&v_{23}&...\\{v_{31}}&{v_{32}}&v_{33}&... \end{array}\right]$
其中z的每一行都是mean centred后的特征向量feature vector, 此时, 之前的协方差矩阵 $\Sigma$ 就可表示为 (因为均值都变为0, 所以原来 $(x-\mu_1)(y-\mu_2)$ 直接变为了x*y )
$\Sigma \propto \mathbf { Z } ^ { \mathrm { T } } \mathbf { Z }$

1. ****Principal axes of variation (变化主轴)

Principal axes of variation指的是对于高维数据而言, 变化率最显著的数据所在维度, 为了理解这一概念, 首先介绍基向量(basis)

一组基是由n维空间中n个线性独立的向量组成, 这些向量之间是垂直的, 它们构成了一个坐标系统, 而n维空间中有无限组基向量

基向量

**
**

第一主成分轴(****The ﬁrst principal axis****)：

第一主成分轴指的是对在n维空间中的数据点, 指向最大variance方向的轴

**
**

第一和第二成分主轴

第二主成分轴是指垂直于第一主成分轴同时指向最大variance方向的轴

以此类推, 第三主成分轴是垂直于第一和第二的前提下, 指向有着最大variance的轴

2. ****特征向量和特征根

特征向量和特征根

最多有n对特征向量-特征根对
其中若A是对称矩阵(对于任何方形矩阵X， $X+X^T$ 是对称矩阵)的话, 则特征向量的集合是正交的
如果A是协方差矩阵的话, 那这些特征根就是主成分坐标轴(principal axes)

对于 $n\leq4$ 的情况, 可以通过代数的方法解得特征根和特征方程。
但对于更大的矩阵, 就需要特征分解(Eigendecomposition,简写为EVD)了。

3. ****特征分解

特征值分解（EVD），在这里，选择一种特殊的矩阵——对称阵（酉空间中叫hermite矩阵即厄米阵）。对称阵有一个性质：它总能相似对角化，对称阵不同特征值对应的特征向量两两正交。一个矩阵能相似对角化即说明其特征子空间即为其列空间，若不能对角化则其特征子空间为列空间的子空间。现在假设存在mxm的满秩对称矩阵A，它有m个不同的特征值，设特征值为 $\lambda_i$ ,对应的单位特征向量为 $x_i$
则有:
$\left.\begin{aligned} A x _ { 1 } & = \lambda _ { 1 } x _ { 1 } \\ A x _ { 2 } & = \lambda _ { 2 } x _ { 2 } \\...\\ A x _ { m } & = \lambda _ { m } x _ { m } \end{aligned} \right.$
将上面的式子用矩阵形式表示, 进而:
$\left. \begin{array} { c } { A U = U \Lambda } \\ { U = \left[ x _ { 1 } x _ { 2 } \cdots x _ { m } \right] } \end{array} \right.$
$\Lambda = \left[ \begin{array} { c c c } { \lambda _ { 1 } } & { \dots } & { 0 } \\ { \vdots } & { \ddots } & { \vdots } \\ { 0 } & { \cdots } & { \lambda _ { m } } \end{array} \right]$
令式子 $A U = U \Lambda$ 两边各除以一个U, 则有(由于对称阵特征向量两两正交，所以U为正交阵，正交阵的逆矩阵等于其转置):
$A = U \Lambda U ^ { - 1 } = U \Lambda U ^ { T }$
这里假设A有m个不同的特征值，实际上，只要A是对称阵其均有如上分解。

特征分解

如果A是对称矩阵(譬如协方差矩阵), 此时 $Q^{-1}=Q^T$ (即特征向量是正交的), 所以此时
$\mathbf { A } = \mathbf { Q } \mathbf { \Lambda } \mathbf { Q } ^ { \mathrm { T } }$
将eigenvector和对应的eigenvalue排序, PCA取前k个

要明确的是，一个矩阵其实就是一个线性变换，因为一个矩阵乘以一个向量后得到的向量，其实就相当于将这个向量进行了线性变换。比如说下面的一个矩阵：
$M = \left[ \begin{array} { l l } { 3 } & { 0 } \\ { 0 } & { 1 } \end{array} \right]$
因为这个矩阵M乘以一个向量(x,y)的结果是:
$\left[ \begin{array} { l l } { 3 } & { 0 } \\ { 0 } & { 1 } \end{array} \right] \left[ \begin{array} { l } { x } \\ { y } \end{array} \right] = \left[ \begin{array} { c } { 3 x } \\ { y } \end{array} \right]$
它其实对应的线性变换是下面的形式：

拉伸变换

上面的矩阵是对称的，所以这个变换是一个对x，y轴的方向一个拉伸变换, 当矩阵不是对称的时候，假如说矩阵是下面的样子：

$M = \left[ \begin{array} { l l } { 1 } & { 1 } \\ { 0 } & { 1 } \end{array} \right]$
它所描述的变换是下面的样子：

非对称矩阵

在图中，蓝色的箭头是一个最主要的变化方向（变化方向可能有不止一个），如果我们想要描述好一个变换，那我们就描述好这个变换主要的变化方向就好了。反过头来看看之前特征值分解的式子，分解得到的Σ矩阵是一个对角阵，里面的特征值是由大到小排列的，这些特征值所对应的特征向量就是描述这个矩阵变化方向(从主要的变化到次要的变化排列), 当矩阵是高维的情况下，那么这个矩阵就是高维空间下的一个线性变换，我们通过特征值分解得到的前N个特征向量，那么就对应了这个矩阵最主要的N个变化方向。我们利用这前N个变化方向，就可以近似这个矩阵(变换)。也就是之前说的：提取这个矩阵最重要的特征。

总结一下，特征值分解可以得到特征值与特征向量，特征值表示的是这个特征到底有多重要，而特征向量表示这个特征是什么

4. ****PCA流程

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

对所有的样本进行中心化： $x^{(i)} = x^{(i)} - \frac{1}{m}\sum\limits_{j=1}^{m} x^{(j)}$
计算样本的协方差矩阵 $XX^T$ , 注意, 协方差矩阵就等于 $XX^T$
对矩阵 $XX^T$ 进行特征值分解
取出最大的n'个特征值对应的特征向量 $(w_1,w_2,...,w_{n'})$ , 将所有的特征向量标准化后，组成特征向量矩阵W。
对样本集中的每一个样本 $x^{(i)}$ , 转化为新的样本 $z^{(i)}=W^Tx^{(i)}$
得到输出样本集 $D' =(z^{(1)}, z^{(2)},...,z^{(m)})$

有时候，我们不指定降维后的n'的值，而是换种方式，指定一个降维到的主成分比重阈值t。这个阈值t在（0,1]之间。假如我们的n个特征值为 $\lambda_1 \geq \lambda_2 \geq ... \geq \lambda_n$ , 则n'可以通过下式得到:
$\frac{\sum\limits_{i=1}^{n'}\lambda_i}{\sum\limits_{i=1}^{n}\lambda_i} \geq t$

这里对PCA算法做一个总结。作为一个非监督学习的降维方法，它只需要特征值分解，就可以对数据进行压缩，去噪。因此在实际场景应用很广泛。为了克服PCA的一些缺点，出现了很多PCA的变种，比如第六节的为解决非线性降维的KPCA，还有解决内存限制的增量PCA方法Incremental PCA，以及解决稀疏数据降维的PCA方法Sparse PCA等。

PCA算法的主要优点有：

1）仅仅需要以方差衡量信息量，不受数据集以外的因素影响。

2）各主成分之间正交，可消除原始数据成分间的相互影响的因素。

3）计算方法简单，主要运算是特征值分解，易于实现。

PCA算法的主要缺点有：

1）主成分各个特征维度的含义具有一定的模糊性，不如原始样本特征的解释性强。

2）方差小的非主成分也可能含有对样本差异的重要信息，因降维丢弃可能对后续数据处理有影响。

5. ****奇异值分解

奇异值分解是一个有着很明显的物理意义的一种方法，它可以将一个比较复杂的矩阵用更小更简单的几个子矩阵的相乘来表示，这些小矩阵描述的是矩阵的重要的特性。

特征值分解是一个提取矩阵特征很不错的方法，但是它只是对方阵而言的，在现实的世界中，我们看到的大部分矩阵都不是方阵, 比如说有N个学生，每个学生有M科成绩，这样形成的一个N * M的矩阵就不可能是方阵, 此时即用到了奇异值分解, 奇异值分解是一个能适用于任意的矩阵的一种分解的方法:

奇异值分解

其中p是矩阵M的秩, 秩代表线性不相关的行或者列的数量

U是一个m * p的方阵（里面的向量是正交的，U里面的列向量称为左奇异向量），Σ是一个p * p的矩阵（除了对角线的元素都是0，对角线上的元素称为奇异值），V’(V的转置)是一个p * n的矩阵，里面的行向量也是正交的，V里面的向量称为右奇异向量。

左奇异向量集合是 $MM^T$ 的特征向量集合
右奇异向量集合是 $M^TM$ 的特征向量集合
The singular values are the square roots of the eigenvalues of the corresponding eigenvectors of $M^TM$ and $MM^T$
如果M是mean centred的特征向量矩阵的话, V的列向量是 $M^TM$ 的特征向量, 它们是M的主成分(principle components)。

那么奇异值和特征值是怎么对应起来的呢？首先，我们将一个矩阵M的转置乘以M，将会得到一个方阵，我们用这个方阵求特征值可以得到：
$\left( M ^ { T } M \right) v _ { i } = \lambda _ { i } v _ { i }$
这里得到的v，就是我们上面的右奇异向量。此外我们还可以得到:
$\left. \begin{array} { l } { \sigma _ { i } = \sqrt { \lambda } _ { i } } \\ { u _ { i } = \frac { 1 } { \sigma } M v _ { i } } \end{array} \right.$
这里的σ就是上面说的奇异值，u就是上面说的左奇异向量
奇异值σ跟特征值类似，在矩阵Σ中也是从大到小排列，而且σ的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了。也就是说，我们也可以用前r大的奇异值来近似描述矩阵，这里定义一下部分奇异值分解:

近似奇异值分解

右边的三个矩阵相乘的结果将会是一个接近于M的矩阵，在这儿，r越接近于p，则相乘的结果越接近于M。而这三个矩阵的面积之和（在存储观点来说，矩阵面积越小，存储量就越小）要远远小于原始的矩阵M，我们如果想要压缩空间来表示原矩阵A，我们存下这里的三个矩阵：U、Σ、V就好了。

SVD流程：

SVD流程

至于为什么要用基于SVD的PCA是因为:

计算可行性
SVD的速度比EVD更快

除此之外, SVD适用的场合有:

求伪逆(Pseudoinverse)
解homogeneous linear equations, 如Ax=0
数据挖掘: 如基于CF的推荐系统

SVD求伪逆的一个例子

A矩阵的伪逆代表其与A的乘积等于单位矩阵

我们来具体算一个矩阵A的伪逆：

$\mathbf { A } = \left[ \begin{array} { c c } { 1 } & { 1 } \\ { 0 } & { 1 } \\ { 1 } & { 0 } \\ { 1 } & { 1 } \end{array} \right] \Rightarrow \mathbf { A } ^ { * } \mathbf { A } = \left[ \begin{array} { c c c c } { 1 } & { 0 } & { 1 } & { 1 } \\ { 1 } & { 1 } & { 0 } & { 1 } \end{array} \right] \left[ \begin{array} { c c } { 1 } & { 1 } \\ { 0 } & { 1 } \\ { 1 } & { 0 } \\ { 1 } & { 1 } \end{array} \right] = \left[ \begin{array} { c c } { 3 } & { 2 } \\ { 2 } & { 3 } \end{array} \right]$

易知，rank(A*A)=2。下面来求矩阵A*A的特征值，于是有

$\operatorname { det } \left| \begin{array} { c c } { 3 - \lambda } & { 2 } \\ { 2 } & { 3 - \lambda } \end{array} \right| = \lambda ^ { 2 } - 6 \lambda + 9 - 4 = ( \lambda - 5 ) ( \lambda - 1 ) \Rightarrow \lambda _ { 1 } = 5 , \lambda _ { 2 } = 1$

接下来求对应的特征向量，因为

$\mathbf { A } ^ { * } \mathbf { A } v = \lambda v \Rightarrow \left( \mathbf { A } ^ { * } \mathbf { A } - \lambda I \right) v = 0$

所以可知当λ1=5时，对应的特征向量（注意结果要正交归一化）：

$\mathbf { A } ^ { * } \mathbf { A } - 5 I = \left[ \begin{array} { c c } { - 2 } & { 2 } \\ { 2 } & { - 2 } \end{array} \right] \Rightarrow u _ { 1 } = \left[ \begin{array} { c } { \frac { 1 } { \sqrt { 2 } } } \\ { \frac { 1 } { \sqrt { 2 } } } \end{array} \right]$

同理还有当λ2=1时，对应的特征向量

$\mathbf { A } ^ { * } \mathbf { A } - 1 I = \left[ \begin{array} { c c } { 2 } & { 2 } \\ { 2 } & { 2 } \end{array} \right] \Rightarrow u _ { 2 } = \left[ \begin{array} { c } { \frac { 1 } { \sqrt { 2 } } } \\ { - \frac { 1 } { \sqrt { 2 } } } \end{array} \right]$

如此便得到了SVD中需要的U矩阵

$U=\left[ \begin{array} { c c } { \frac { 1 } { \sqrt { 2 } } } & { \frac { 1 } { \sqrt { 2 } } } \\ { \frac { 1 } { \sqrt { 2 } } } & { \frac { - 1 } { \sqrt { 2 } } } \end{array} \right]$

为了求出矩阵V，先求W：

$\mathbf { w } = \mathbf { A } \mathbf { U } = \left[ \begin{array} { c c } { 1 } & { 1 } \\ { 0 } & { 1 } \\ { 1 } & { 0 } \\ { 1 } & { 1 } \end{array} \right] \left[ \begin{array} { c c } { \frac { 1 } { \sqrt { 2 } } } & { \frac { 1 } { \sqrt { 2 } } } \\ { \frac { 1 } { \sqrt { 2 } } } & { \frac { - 1 } { \sqrt { 2 } } } \end{array} \right] = \left[ \begin{array} { c c } { \sqrt { 2 } } & { 0 } \\ { 1 / \sqrt { 2 } } & { - 1 / \sqrt { 2 } } \\ { 1 / \sqrt { 2 } } & { 1 / \sqrt { 2 } } \\ { \sqrt { 2 } } & { 0 } \end{array} \right]= \left[ \begin{array} { l l } { w _ { 1 } } & { w _ { 2 } } \end{array} \right]$

于是可知

$v _ { 1 } = \frac { w _ { 1 } } { \sqrt { 5 } } , \quad v _ { 2 } = \frac { w _ { 2 } } { \sqrt { 1 } } \Rightarrow \mathbf { V } = \left[ \begin{array} { l l } { v _ { 1 } } & { v _ { 2 } } \end{array} \right]$

所以根据公式A的伪逆就是, 其中V*代表其转置矩阵

$\mathbf { A } ^ { \dagger } = \mathbf { U } \mathbf { \Lambda } \mathbf { V } ^ { * } = \left[ \begin{array} { c c } { \frac { 1 } { \sqrt { 2 } } } & { \frac { 1 } { \sqrt { 2 } } } \\ { \frac { 1 } { \sqrt { 2 } } } & { \frac { - 1 } { \sqrt { 2 } } } \end{array} \right] \left[ \begin{array} { c c } { \frac { 1 } { \sqrt { 5 } } } & { 0 } \\ { 0 } & { \frac { 1 } { \sqrt { 1 } } } \end{array} \right] \left[ \begin{array} { c c c } { \frac { \sqrt { 2 } } { \sqrt { 5 } } } & { 1 / \sqrt { 10 } } & { 1 / \sqrt { 10 } } & { \frac { \sqrt { 2 } } { \sqrt { 5 } } } \\ { 0 } & { - 1 / \sqrt { 2 } } & { 1 / \sqrt { 2 } } & { 0 } \end{array} \right]$

6. ****SVD和EVD的计算方法

普遍来说, 这些计算方法都是迭代的:

Power Iteration

-Repeated for each E.V. by rotating and truncating the input to remove the effect of the previous E.V.

“Arnoldi Iteration” and the “Lanczos Algorithm”

-Move efﬁcient variants of Power Iteration

-use the “Gram-Schmidt” process to ﬁnd the orthonormal basis of the top-r E.Vs

最后编辑于：2019.01.10 13:46:01

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,324评论 5赞 476
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,303评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,192评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,555评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,569评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,566评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,927评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,583评论 0赞 257
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,827评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,590评论 2赞 320
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,669评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,365评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,941评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,928评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,159评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,880评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,399评论 2赞 342

特征分解以及奇异值分解

SVD求伪逆的一个例子

推荐阅读更多精彩内容