当前位置:首页 >> 能源/化工 >>

矩阵的奇异值分解及其应用


矩阵的奇异值分解( 矩阵的奇异值分解(SVD)及其应用 ) 版权声明: 版权声明:
本文由 LeftNotEasy 发布于 http://leftnoteasy.cnblogs.com, 本文可以被全部的转载或 者部分使用,但请注明出处,如果有问题,请联系 wheeleast@gmail.com

前言: 前言:
上一次写了关于 PCA 与

LDA 的文章,PCA 的实现一般有两种,一种是用特征值分解去实现 的,一种是用奇异值分解去实现的。在上篇文章中便是基于特征值分解的一种解释。特征值和奇 异值在大部分人的印象中,往往是停留在纯粹的数学计算中。而且线性代数或者矩阵论里面,也 很少讲任何跟特征值与奇异值有关的应用背景。 奇异值分解是一个有着很明显的物理意义的一种 方法, 它可以将一个比较复杂的矩阵用更小更简单的几个子矩阵的相乘来表示, 这些小矩阵描述 的是矩阵的重要的特性。就像是描述一个人一样,给别人描述说这个人长得浓眉大眼,方脸,络 腮胡, 而且带个黑框的眼镜, 这样寥寥的几个特征, 就让别人脑海里面就有一个较为清楚的认识, 实际上,人脸上的特征是有着无数种的,之所以能这么描述,是因为人天生就有着非常好的抽取 重要特征的能力,让机器学会抽取重要的特征,SVD 是一个重要的方法。 在机器学习领域,有相当多的应用与奇异值都可以扯上关系,比如做 feature reduction 的 PCA,做数据压缩(以图像压缩为代表)的算法,还有做搜索引擎语义层次检索的 LSI(Latent Semantic Indexing) 另外在这里抱怨一下,之前在百度里面搜索过 SVD,出来的结果都是俄罗斯的一种狙击枪 (AK47 同时代的),是因为穿越火线这个游戏里面有一把狙击枪叫做 SVD,而在 Google 上 面搜索的时候,出来的都是奇异值分解(英文资料为主)。想玩玩战争游戏,玩玩 COD 不是非 常好吗,玩山寨的 CS 有神马意思啊。国内的网页中的话语权也被这些没有太多营养的帖子所占 据。真心希望国内的气氛能够更浓一点,搞游戏的人真正是喜欢制作游戏,搞 Data Mining 的 人是真正喜欢挖数据的,都不是仅仅为了混口饭吃,这样谈超越别人才有意义,中文文章中,能 踏踏实实谈谈技术的太少了,改变这个状况,从我自己做起吧。 前面说了这么多,本文主要关注奇异值的一些特性,另外还会稍稍提及奇异值的计算,不过 本文不准备在如何计算奇异值上展开太多。另外,本文里面有部分不算太深的线性代数的知识, 如果完全忘记了线性代数,看本文可能会有些困难。

一、奇异值与特征值基础知识: 奇异值与特征值基础知识:
特征值分解和奇异值分解在机器学习领域都是属于满地可见的方法。两者有着很紧密的关 系,我在接下来会谈到,特征值分解和奇异值分解的目的都是一样,就是提取出一个矩阵最重要 的特征。先谈谈特征值分解吧:

1)特征值: 特征值: 特征值
如果说一个向量 v 是方阵 A 的特征向量,将一定可以表示成下面的形式:

这时候 λ 就被称为特征向量 v 对应的特征值,一个矩阵的一组特征向量是一组正交向量。特 征值分解是将一个矩阵分解成下面的形式:

其中 Q 是这个矩阵 A 的特征向量组成的矩阵, 是一个对角阵, Σ 每一个对角线上的元素就是 一个特征值。我这里引用了一些参考文献中的内容来说明一下。首先,要明确的是,一个矩阵其 实就是一个线性变换, 因为一个矩阵乘以一个向量后得到的向量, 其实就相当于将这个向量进行 了线性变换。比如说下面的一个矩阵:

它其实对应的线性变换是下面的形式:

因为这个矩阵 M 乘以一个向 量(x,y)的结果是:

上面的矩阵是对称的,所以这个变换是一个对 x,y 轴的方向一 个拉伸变换(每一个对角线上的元素将会对一个维度进行拉伸变换,当值>1 时,是拉长,当值 <1 时时缩短),当矩阵不是对称的时候,假如说矩阵是下面的样子:

它所描述的变换是下面的样子:

这其实是在平面上对一个轴进行的拉伸变换(如蓝色的箭头所示),在图中,蓝色的箭头是 一个最主要的 主要的变化方向(变化方向可能有不止一个),如果我们想要描述好一个变换,那我们 如果我们想要描述好一个变换, 主要的 如果我们想要描述好一个变换 就描述好这个变换主要的变化方向就好了。 分解得到的 Σ 就描述好这个变换主要的变化方向就好了 反过头来看看之前特征值分解的式子, 矩阵是一个对角阵, 里面的特征值是由大到小排列的, 这些特征值所对应的特征向量就是描述这 个矩阵变化方向(从主要的变化到次要的变化排列) 当矩阵是高维的情况下,那么这个矩阵就是高维空间下的一个线性变换,这个线性变化可能 没法通过图片来表示,但是可以想象,这个变换也同样有很多的变换方向,我们通过特征值分解 得到的前 N 个特征向量,那么就对应了这个矩阵最主要的 N 个变化方向。我们利用这前 N 个变 化方向,就可以近似这个矩阵(变换)。也就是之前说的:提取这个矩阵最重要的特征。总结 提取这个矩阵最重要的特征。 提取这个矩阵最重要的特征 一下,特征值分解可以得到特征值与特征向量,特征值表示的是这个特征到底有多重要,而特征 向量表示这个特征是什么, 可以将每一个特征向量理解为一个线性的子空间, 我们可以利用这些 线性的子空间干很多的事情。不过,特征值分解也有很多的局限,比如说变换的矩阵必须是方 特征值分解也有很多的局限, 特征值分解也有很多的局限 阵。 (说了这么多特征值变换,不知道有没有说清楚,请各位多提提意见。)

2)奇异值: )奇异值:
下面谈谈奇异值分解。特征值分解是一个提取矩阵特征很不错的方法,但是它只是对方阵而 言的,在现实的世界中,我们看到的大部分矩阵都不是方阵,比如说有 N 个学生,每个学生有 M 科成绩,这样形成的一个 N * M 的矩阵就不可能是方阵,我们怎样才能描述这样普通的矩阵 我们怎样才能描述这样普通的矩阵 呢的重要特征呢? 呢的重要特征呢?奇异值分解可以用来干这个事情,奇异值分解是一个能适用于任意的矩阵的 奇异值分解是一个能适用于任意的矩阵的 一种分解的方法: 一种分解的方法

假设 A 是一个 M * N 的矩阵,那么得到的 U 是一个 M * M 的方阵(里 面的向量是正交的,U 里面的向量称为左奇异向量),Σ 是一个 M * N 的矩阵(除了对角线的 元素都是 0,对角线上的元素称为奇异值),V’(V 的转置)是一个 N * N 的矩阵,里面的向量也 是正交的,V 里面的向量称为右奇异向量),从图片来反映几个相乘的矩阵的大小可得下面的图 片

那么奇异值和特征值是怎么对应起来的呢?首先,我们将一个矩阵 A 的转置 * A,将会得到

一个方阵,我们用这个方阵求特征值可以得到: 是我们上面的右奇异向量。此外我们还可以得到:

这里得到的 v,就

这里的 σ 就是上面说的奇异值,u 就是上面说的左奇异向量。奇异值 σ 跟 特征值类似,在矩阵 Σ 中也是从大到小排列,而且 σ 的减少特别的快,在很多情况下,前 10% 在很多情况下, 在很多情况下 以上了。 我们也可以用前 r 甚至 1%的奇异值的和就占了全部的奇异值之和的 99%以上了 也就是说, 的奇异值的和就占了全部的奇异值之和的 以上了 大的奇异值来近似描述矩阵,这里定义一下部分奇异值分解 部分奇异值分解: 部分奇异值分解

r 是一个远小于 m、n 的数,这样矩阵的乘法看起来像是下面的样子:

右边的三个矩阵相乘的结果将会是一个接近于 A 的矩阵,在这儿,r 越接近于 n,则相乘的 结果越接近于 A。而这三个矩阵的面积之和(在存储观点来说,矩阵面积越小,存储量就越小)

要远远小于原始的矩阵 A,我们如果想要压缩空间来表示原矩阵 A,我们存下这里的三个矩阵: U、Σ、V 就好了。

二、奇异值的计算: 奇异值的计算:
奇异值的计算是一个难题,是一个 O(N^3)的算法。在单机的情况下当然是没问题的, matlab 在一秒钟内就可以算出 1000 * 1000 的矩阵的所有奇异值,但是当矩阵的规模增长的 时候,计算的复杂度呈 3 次方增长,就需要并行计算参与了。Google 的吴军 吴军老师在数学之美 数学之美系 吴军 数学之美 列谈到 SVD 的时候,说起 Google 实现了 SVD 的并行化算法,说这是对人类的一个贡献,但 是也没有给出具体的计算规模,也没有给出太多有价值的信息。 其实 SVD 还是可以用并行的方式去实现的,在解大规模的矩阵的时候,一般使用迭代的方 法,当矩阵的规模很大(比如说上亿)的时候,迭代的次数也可能会上亿次,如果使用 Map-Reduce 框架去解,则每次 Map-Reduce 完成的时候,都会涉及到写文件、读文件的操 作。个人猜测 Google 云计算体系中除了 Map-Reduce 以外应该还有类似于 MPI 的计算模型, 也就是节点之间是保持通信,数据是常驻在内存中的,这种计算模型比 Map-Reduce 在解决迭 代次数非常多的时候,要快了很多倍。 Lanczos 迭代就是一种解对称方阵部分特征值 对称方阵部分特征值的方法(之前谈到了,解 A’* A 得到的对称方 对称方阵部分特征值 阵的特征值就是解 A 的右奇异向量),是将一个对称的方程化为一个三对角矩阵再进行求解。 按网上的一些文献来看,Google 应该是用这种方法去做的奇异值分解的。请见 Wikipedia 上 面的一些引用的论文,如果理解了那些论文,也“几乎”可以做出一个 SVD 了。 由于奇异值的计算是一个很枯燥,纯数学的过程,而且前人的研究成果(论文中)几乎已经 把整个程序的流程图给出来了。更多的关于奇异值计算的部分,将在后面的参考文献中给出,这 里不再深入,我还是 focus 在奇异值的应用中去。

三、奇异值与主成分分析(PCA): 奇异值与主成分分析( ):
主成分分析在上一节里面也讲了一些,这里主要谈谈如何用 SVD 去解 PCA 的问题。PCA 的问题其实是一个基的变换, 使得变换后的数据有着最大的方差。 方差的大小描述的是一个变量 的信息量,我们在讲一个东西的稳定性的时候,往往说要减小方差,如果一个模型的方差很大, 那就说明模型不稳定了。但是对于我们用于机器学习的数据(主要是训练数据),方差大才有意 义,不然输入的数据都是同一个点,那方差就为 0 了,这样输入的多个数据就等同于一个数据 了。以下面这张图为例子:

这个假设是一个摄像机采集一个物体运动得到的 图片,上面的点表示物体运动的位置,假如我们想要用一条直线去拟合这些点,那我们会选择什 么方向的线呢?当然是图上标有 signal 的那条线。如果我们把这些点单纯的投影到 x 轴或者 y 轴上,最后在 x 轴与 y 轴上得到的方差是相似的(因为这些点的趋势是在 45 度左右的方向,所 以投影到 x 轴或者 y 轴上都是类似的),如果我们使用原来的 xy 坐标系去看这些点,容易看不 出来这些点真正的方向是什么。但是如果我们进行坐标系的变化,横轴变成了 signal 的方向, 纵轴变成了 noise 的方向,则就很容易发现什么方向的方差大,什么方向的方差小了。 一般来说,方差大的方向是信号的方向,方差小的方向是噪声的方向,我们在数据挖掘中或 者数字信号处理中,往往要提高信号与噪声的比例,也就是信噪比。对上图来说,如果我们只保 留 signal 方向的数据,也可以对原数据进行不错的近似了。 PCA 的全部工作简单点说,就是对原始的空间中顺序地找一组相互正交的坐标轴,第一个轴 是使得方差最大的, 第二个轴是在与第一个轴正交的平面中使得方差最大的, 第三个轴是在与第 1、 个轴正交的平面中方差最大的, 2 这样假设在 N 维空间中, 我们可以找到 N 个这样的坐标轴, 我们取前 r 个去近似这个空间,这样就从一个 N 维的空间压缩到 r 维的空间了,但是我们选择 的 r 个坐标轴能够使得空间的压缩使得数据的损失最小。 还是假设我们矩阵每一行表示一个样本,每一列表示一个 feature,用矩阵的语言来表示, 将一个 m * n 的矩阵 A 的进行坐标轴的变化,P 就是一个变换的矩阵从一个 N 维的空间变换到 另一个 N 维的空间,在空间中就会进行一些类似于旋转、拉伸的变化。

而将一个 m * n 的矩阵 A 变换成一个 m * r 的矩阵, 这样就会使得本来有 n 个 feature 的, 变成了有 r 个 feature 了(r < n),这 r 个其实就是对 n 个 feature 的一种提炼,我们就把这 个称为 feature 的压缩。用数学语言表示就是:

但是这个怎么和 SVD 扯上关系呢?之前谈到,SVD 得出的奇 异向量也是从奇异值由大到小排列的,按 PCA 的观点来看,就是方差最大的坐标轴就是第一个 奇异向量,方差次大的坐标轴就是第二个奇异向量…我们回忆一下之前得到的 SVD 式子:

在矩阵的两边同时乘上一个矩阵 V, 由于 V 是一个正 交的矩阵,所以 V 转置乘以 V 得到单位阵 I,所以可以化成后面的式子

将后面的式子与 A * P 那个 m * n 的 矩阵变换为 m * r 的矩阵的式子对照看看,在这里,其实 V 就是 P,也就是一个变化的向量。 这里是将一个 m * n 的矩阵压缩到一个 m * r 的矩阵,也就是对列进行压缩,如果我们想对行 进行压缩(在 PCA 的观点下,对行进行压缩可以理解为,将一些相似的 sample 合并在一起, 或者将一些没有太大价值的 sample 去掉)怎么办呢?同样我们写出一个通用的行压缩例子:

这样就从一个 m 行的矩阵压缩到一个 r 行的矩阵了, SVD 来 对 说也是一样的,我们对 SVD 分解的式子两边乘以 U 的转置 U'

这样我们就得到了对行进行压缩的式子。可以看 出, 其实 PCA 几乎可以说是对 SVD 的一个包装, 如果我们实现了 SVD, 那也就实现了 PCA 了, 而且更好的地方是,有了 SVD,我们就可以得到两个方向的 PCA,如果我们对 A’A 进行特征值 的分解,只能得到一个方向的 PCA。

四、奇异值与潜在语义索引 LSI: :
潜在语义索引(Latent Semantic Indexing)与 PCA 不太一样,至少不是实现了 SVD 就 可以直接用的,不过 LSI 也是一个严重依赖于 SVD 的算法,之前吴军老师在矩阵计算与文本处 理中的分类问题中谈到:

“三个矩阵有非常清楚的物理含义。 第一个矩阵 X 中的每一行表示意

思相关的一类词,其中的每个非零元素表示这类词中每个词的重要性 (或者说相关性),数值越大越相关。最后一个矩阵 Y 中的每一列表示 同一主题一类文章,其中每个元素表示这类文章中每篇文章的相关性。 中间的矩阵则表示类词和文章雷之间的相关性。因此,我们只要对关联 矩阵 A 进行一次奇异值分解,w 我们就可以同时完成了近义词分类和 文章的分类。(同时得到每类文章和每类词的相关性)。”
上面这段话可能不太容易理解,不过这就是 LSI 的精髓内容,我下面举一个例子来说明一 下,下面的例子来自 LSA tutorial,具体的网址我将在最后的引用中给出:

这就是一个矩阵,不过不太一样的 是,这里的一行表示一个词在哪些 title 中出现了(一行就是之前说的一维 feature),一列表 示一个 title 中有哪些词,(这个矩阵其实是我们之前说的那种一行是一个 sample 的形式的一 种转置,这个会使得我们的左右奇异向量的意义产生变化,但是不会影响我们计算的过程)。比 如说 T1 这个 title 中就有 guide、investing、market、stock 四个词,各出现了一次,我们 将这个矩阵进行 SVD,得到下面的矩阵:

左奇异向量表示词的一些特性,右奇异向量表示文档的一些特性,中间的奇异值矩阵表示 左奇异向量的一行与右奇异向量的一列的重要程序,数字越大越重要。 继续看这个矩阵还可以发现一些有意思的东西,首先,左奇异向量的第一列表示每一个词 的出现频繁程度,虽然不是线性的,但是可以认为是一个大概的描述,比如 book 是 0.15 对应 文档中出现的 2 次,investing 是 0.74 对应了文档中出现了 9 次,rich 是 0.36 对应文档中出 现了 3 次; 其次,右奇异向量中一的第一行表示每一篇文档中的出现词的个数的近似,比如说,T6 是 0.49,出现了 5 个词,T2 是 0.22,出现了 2 个词。 然后我们反过头来看,我们可以将左奇异向量和右奇异向量都取后 2 维(之前是 3 维的矩 阵),投影到一个平面上,可以得到:

在图 上,每一个红色的点,都表示一个词,每一个蓝色的点,都表示一篇文档,这样我们可以对这些 词和文档进行聚类,比如说 stock 和 market 可以放在一类,因为他们老是出现在一起,real 和 estate 可以放在一类,dads,guide 这种词就看起来有点孤立了,我们就不对他们进行合并 了。按这样聚类出现的效果,可以提取文档集合中的近义词,这样当用户检索文档的时候,是用 语义级别(近义词集合)去检索了,而不是之前的词的级别。这样一减少我们的检索、存储量, 因为这样压缩的文档集合和 PCA 是异曲同工的, 二可以提高我们的用户体验, 用户输入一个词, 我们可以在这个词的近义词的集合中去找,这是传统的索引无法做到的。 不知道按这样描述,再看看吴军老师的文章,是不是对 SVD 更清楚了?:-D

参考资料: 参考资料:
1)A Tutorial on Principal Component Analysis, Jonathon Shlens 这是我关于用 SVD 去做 PCA 的主要参考资料 2)http://www.ams.org/samplings/feature-column/fcarc-svd 关于 svd 的一篇概念好文,我开头的几个图就是从这儿截取的 3) http://www.puffinwarellc.com/index.php/news-and-articles/articles/30-singular-v alue-decomposition-tutorial.html 另一篇关于 svd 的入门好文 4) http://www.puffinwarellc.com/index.php/news-and-articles/articles/33-latent-se mantic-analysis-tutorial.html svd 与 LSI 的好文,我后面 LSI 中例子就是来自此 5)

http://www.miislita.com/information-retrieval-tutorial/svd-lsi-tutorial-1-understa nding.html 另一篇 svd 与 LSI 的文章,也还是不错,深一点,也比较长 6) Singular Value Decomposition and Principal Component Analysis, Rasmus Elsborg Madsen, Lars Kai Hansen and Ole Winther, 2004 跟 1)里面的文章比较类似


相关文章:
矩阵奇异值分解在图像隐藏中的应用
矩阵奇异值分解在图像隐藏中的应用_数学_自然科学_专业资料。奇异值分解及其应用 矩阵奇异值分解在图像隐藏中的应用摘 要:基于数字图像的奇异值分解和Arnold置换,...
矩阵的奇异值分解
§2 矩阵的奇异值分解 定义 设 A 是秩为 r 的 m × n 复矩阵, AT A ...与矩阵 A 距离最近的一个矩阵.这在实 际中应用广泛.例如, 在图像数字化技术...
矩阵的奇异值分解
矩阵的奇异值分解_数学_自然科学_专业资料。§2 定义 矩阵的奇异值分解 设 A...与矩阵 A 距离最近的一个矩阵.这在实 际中应用广泛.例如, 在图像数字化技术...
矩阵分解及其应用
根据本学期所学知识, 本 文把矩阵分解分为三角分解、正交三角分解、奇异值分解和满秩分解。在论文中对相关理论 进行了简要的说明与描述, 并在应用方面, 展示了...
矩阵的奇异值分解
矩阵分解的研究及应用 12页 免费 奇异值分解 7页 免费 奇异值分解定理 2页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进...
对于矩阵奇异值分解的探究
的 特把征向量为U的列向量, 由此对其进行奇异值分解。 参考文献:矩阵的奇异值与特征值的关系探究及应用,刘长河, 高圣洁, 1. 河南科技大学数学与统计 学院, ...
矩阵的奇异值分解在虹膜识别中的应用
矩阵的奇异值分解在虹膜识别中的应用矩阵的奇异值分解(SVD)可以应用于虹膜识别系统中。对预处理后的虹膜图像进行 经典模态分解, 将获得的一系列固有模态函数和残差...
奇异值分解
奇异值分解_计算机软件及应用_IT/计算机_专业资料。奇异值分解(SVD) --- 几何...σ15 = 0.05 很明显,前面三个奇异值远远比后面的奇异值要大,这样矩阵 如下...
矩阵分解及其应用
《线性代数与矩阵分析》课程小论文 矩阵分解及其应用 学生姓名:*** 专业:***...方法,它们分别是矩阵的等价分解、三角分解、谱分解、奇异值分解和 Fitting 分解...
SVD分解及其应用
机器学习中的数学(6)-强大的矩阵奇异值分解(SVD)及其应用 PCA 的实现一般有两种,一种是用特征值分解去实现的,一种是用奇异值分解去实现的。在上篇文 章中便...
更多相关标签: