数据降维技术(2)—奇异值分解(SVD)

上一篇文章讲了PCA的数据原理,明白了PCA主要的思想及使用PCA做数据降维的步骤,本文我们详细探讨下另一种数据降维技术—奇异值分解(SVD)。

在介绍奇异值分解前,先谈谈这个比较奇怪的名字:奇异值分解,英文全称为Singular Value Decomposition。首先我们要明白,SVD是众多的矩阵分解技术中的一种,矩阵分解方式很多,如三角分解(LU分解、LDU分解、乔列斯基分解等)、QR分解及这里所说的奇异值分解;其次,singular是奇特的、突出的、非凡的意思,从分解的过程及意义来看理解成非凡地,优异地分解更好理解,下面进入正题。

1、矩阵特征值及其特征特征向量

在介绍奇异值分解前,我们先看看矩阵的特征值及特征向量:

设 Anxn是n阶方阵,如果存在数λ和非零n维列向量X,使得 AX=λX 成立,则称λ是A的一个特征值(characteristic value)或本征值(eigenvalue)。非零n维列向量X称为矩阵A的属于(对应于)特征值λ的特征向量或本征向量,简称A的特征向量或A的本征向量。 矩阵不同特征值的特征向量相互正交。

从线性变化的角度看,矩阵A与一个向量X相乘的意义是将向量X在矩阵定义的空间里做线性变换,变换分为三种情况:一种是仅仅改变向量X的方向,该类矩阵主要为正交矩阵和其置换矩阵、旋转矩阵(Givens变换)及反射矩阵;另一种为改变向量X的大小(长度),这里就是这里的特征值和特征向量的关系,由矩阵的特征值和特征向量的定义(AX=λX)就可以看出;第三种情况急为对向量X的大小和方向都改变。

2、矩阵特征值分解

令 A 是一个nxn的方阵,且有n个线性无关的特征向量 qi(i=1,...,n)。这样, A 可以被分解为:

    其中Q是nxn方阵,代表被分解的矩阵A在n维空间下的一组基,每一列为一个方向上的基 。 Λ 是对角矩阵,其对角线上的元素为对应的特征值,也即Λiii,意思就是矩阵A在该特征值对应的特征向量上的包含的信息量,如果某及个特征值较小(绝对值),说明这几个方向信息量很小,可以用来降维,也就是删除小特征值方向的数据,至保留较大特征值方向对应的色数据,这样做以后数据量见效你,但是重要信息都保留了下来。

3、奇异值分解

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

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

那么奇异值和特征值是怎么对应起来的呢?首先,我们将一个矩阵A的转置AT,将会得到一个方阵,我们用这个方阵求特征值可以得到:

这里得到的v,就是我们上面的右奇异向量。此外我们还可以得到:

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

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

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

4、奇异值分解计算

奇异值的计算是一个难题,是一个O(N^3)的算法。在单机的情况下当然是没问题的,matlab在一秒钟内就可以算出1000X1000的矩阵的所有奇异值,但是当矩阵的规模增长的时候,计算的复杂度呈3次方增长,就需要并行计算参与了。Google的吴军老师在数学之美系列谈到SVD的时候,说起Google实现了SVD的并行化算法,说这是对人类的一个贡献,但是也没有给出具体的计算规模,也没有给出太多有价值的信息。

其实SVD还是可以用并行的方式去实现的,在解大规模的矩阵的时候,一般使用迭代的方法,当矩阵的规模很大(比如说上亿)的时候,迭代的次数也可能会上亿次,如果使用Map-Reduce框架去解,则每次Map-Reduce完成的时候,都会涉及到写文件、读文件的操作。个人猜测Google云计算体系中除了Map-Reduce以外应该还有类似于MPI的计算模型,也就是节点之间是保持通信,数据是常驻在内存中的,这种计算模型比Map-Reduce在解决迭代次数非常多的时候,要快了很多倍。

Lanczos迭代就是一种解对称方阵部分特征值的方法(之前谈到了,解A’A得到的对称方阵的特征值就是解A的右奇异向量),是将一个对称的方程化为一个三对角矩阵再进行求解。按网上的一些文献来看,Google应该是用这种方法去做的奇异值分解的。请见Wikipedia上面的一些引用的论文,如果理解了那些论文,也“几乎”可以做出一个SVD了。

由于奇异值的计算是一个很枯燥,纯数学的过程,而且前人的研究成果(论文中)几乎已经把整个程序的流程图给出来了。更多的关于奇异值计算的部分,将在后面的参考文献中给出,这里不再深入,我还是focus在奇异值的应用中去。

参考资料:

1)http://www.cnblogs.com/LeftNotEasy/archive/2011/01/19/svd-and-applications.html

2)https://www.zhihu.com/question/21874816

时间: 01-15

数据降维技术(2)—奇异值分解(SVD)的相关文章

数据降维技术(1)—PCA的数据原理

PCA(Principal Component Analysis)是一种常用的数据分析方法.PCA通过线性变换将原始数据变换为一组各维度线性无关的表示,可用于提取数据的主要特征分量,常用于高维数据的降维.网上关于PCA的文章有很多,但是大多数只描述了PCA的分析过程,而没有讲述其中的原理.这篇文章的目的是介绍PCA的基本数学原理,帮助读者了解PCA的工作机制是什么. 当然我并不打算把文章写成纯数学文章,而是希望用直观和易懂的方式叙述PCA的数学原理,所以整个文章不会引入严格的数学推导.希望读者在

[机器学习之13]降维技术——主成分分析PCA

始终贯彻数据分析的一个大问题就是对数据和结果的展示,我们都知道在低维度下数据处理比较方便,因而数据进行简化成为了一个重要的技术.对数据进行简化的原因: 1.使得数据集更易用使用.2.降低很多算法的计算开销.3.去除噪音.4.使得结果易懂 这里我们关心的数据降维技术为主成分分析(PCA).在PCA中,数据原来的坐标系转换成了新的坐标系,新的坐标系是由数据本身决定的.第一个新的坐标轴的选择是原始数据中方差最大的方向,第二个新的坐标轴的选择和第一个坐标轴正交且具有最大方差方向.这个过程一直重复,重复次

奇异值分解(SVD) --- 几何意义 (转载)

PS:一直以来对SVD分解似懂非懂,此文为译文,原文以细致的分析+大量的可视化图形演示了SVD的几何意义.能在有限的篇幅把 这个问题讲解的如此清晰,实属不易.原文举了一个简单的图像处理问题,简单形象,真心希望路过的各路朋友能从不同的角度阐述下自己对SVD实际意义的理 解,比如 个性化推荐中应用了SVD,文本以及Web挖掘的时候也经常会用到SVD. 原文:We recommend a singular value decomposition 关于线性变换部分的一些知识可以猛戳这里  奇异值分解(S

[机器学习笔记]奇异值分解SVD简介及其在推荐系统中的简单应用

本文先从几何意义上对奇异值分解SVD进行简单介绍,然后分析了特征值分解与奇异值分解的区别与联系,最后用python实现将SVD应用于推荐系统. 1.SVD详解 SVD(singular value decomposition),翻译成中文就是奇异值分解.SVD的用处有很多,比如:LSA(隐性语义分析).推荐系统.特征压缩(或称数据降维).SVD可以理解为:将一个比较复杂的矩阵用更小更简单的3个子矩阵的相乘来表示,这3个小矩阵描述了大矩阵重要的特性. 1.1奇异值分解的几何意义(因公式输入比较麻烦

Stanford机器学习---第十讲. 数据降维

本文原始地址见http://blog.csdn.net/abcjennifer/article/details/8002329,在此添加了一些自己的注释方便理解 本栏目(Machine learning)包括单参数的线性回归.多参数的线性回归.Octave Tutorial.Logistic Regression.Regularization.神经网络.机器学习系统设计.SVM(Support Vector Machines 支持向量机).聚类.降维.异常检测.大规模机器学习等章节.内容大多来自

机器学习中的数学(5)-强大的矩阵奇异值分解(SVD)及其应用

机器学习中的数学(5)-强大的矩阵奇异值分解(SVD)及其应用 版权声明: 本文由LeftNotEasy发布于http://leftnoteasy.cnblogs.com, 本文可以被全部的转载或者部分使用,但请注明出处,如果有问题,请联系[email protected] 前言: 上一次写了关于PCA与LDA的文章,PCA的实现一般有两种,一种是用特征值分解去实现的,一种是用奇异值分解去实现的.在上篇文章中便是基于特征值分解的一种解释.特征值和奇异值在大部分人的印象中,往往是停留在纯粹的数学计

奇异值分解(SVD)原理详解及推导

声明:转自http://blog.csdn.net/zhongkejingwang/article/details/43053513 在网上看到有很多文章介绍SVD的,讲的也都不错,但是感觉还是有需要补充的,特别是关于矩阵和映射之间的对应关系.前段时间看了国外的一篇文章,叫A Singularly Valuable Decomposition The SVD of a Matrix,觉得分析的特别好,把矩阵和空间关系对应了起来.本文就参考了该文并结合矩阵的相关知识把SVD原理梳理一下. SVD不

降维技术---PCA

数据计算和结果展示一直是数据挖掘领域的难点,一般情况下,数据都拥有超过三维,维数越多,处理上就越吃力.所以,采用降维技术对数据今夕简化一直是数据挖掘工作者感兴趣的方向. 对数据进行简化的好处:使得数据集更易于使用,降低很多算法的计算开销,去除噪声,使得结果易懂. 主成分分析法(PCA)是一种常用的降维技术.在PCA中,数据从原来的坐标系转换到了新的坐标系,新坐标系的选择是由数据本身决定的.第一个新坐标轴选择的是原始数据中方差最大的方向,第二个新坐标轴的选择和第一个坐标轴正交且具有最大方差的方向.

数据预处理技术

数据预处理技术数据清理:空缺值处理.格式标准化.异常数据清除.错误纠正.重复数据的清除数据集成:将多个数据源中的数据结合起来并统一存储,建立数据仓库的过程实际上就是数据集成.数据变换:平滑.聚集.规范化.最小 最大规范化等数据归约:维归(删除不相关的属性(维)).数据压缩(PCA,LDA,SVD.小波变换).数值归约(回归和对数线形模型.线形回归.对数线形模型.直方图)数据离散化和概念分层 1.数据清理:格式标准化.异常数据清除.错误纠正.重复数据的清除通过填写空缺值,平滑噪声数据,识别删除孤立