矩阵的奇异值分解及其应用(完整版)实用资料.doc

矩阵的奇异值分解及其应用（完整版）实用资料(可以直接使用，可编辑 完整版实用资料，欢迎下载）矩阵的奇异值分解（SVD）及其应用版权声明：    本文由LeftNotEasy发布于, 本文可以被全部的转载或者部分使用，但请注明出处，如果有问题，请联系前言：    上一次写了关于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%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了。也就是说，我们也可以用前r大的奇异值来近似描述矩阵，这里定义一下部分奇异值分解：    r是一个远小于m、n的数，这样矩阵的乘法看起来像是下面的样子：        右边的三个矩阵相乘的结果将会是一个接近于A的矩阵，在这儿，r越接近于n，则相乘的结果越接近于A。而这三个矩阵的面积之和（在存储观点来说，矩阵面积越小，存储量就越小）要远远小于原始的矩阵A，我们如果想要压缩空间来表示原矩阵A，我们存下这里的三个矩阵：U、V就好了。 二、奇异值的计算：    奇异值的计算是一个难题，是一个O(N3)的算法。在单机的情况下当然是没问题的，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，如果我们对AA进行特征值的分解，只能得到一个方向的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）      关于svd的一篇概念好文，我开头的几个图就是从这儿截取的 3）      另一篇关于svd的入门好文 4）      svd与LSI的好文，我后面LSI中例子就是来自此 5）      另一篇svd与LSI的文章，也还是不错，深一点，也比较长 6）Singular Value Decomposition and Principal Component Analysis, Rasmus Elsborg Madsen, Lars Kai Hansen and Ole Winther, 2004      跟1）里面的文章比较类似第21卷第2期淮北煤师院学报Vol. 21No. 22000年6月Journal of Huaibei Coal Industry Teachers College J un. 2000求矩阵秩分解的初等变换法及其应用江旭光(安徽省直职工大学, 摘要:本文给出了秩为r A .关键词:分类号:C文章编号:1000-2227(2000 02-0071-73众所周知, 设A 是m ×n 矩阵, 秩A =r , 则存在可逆的 m ×m 矩阵P , n ×n 矩阵Q , 使I r 0PA Q =, 此式称为矩阵A 的秩分解1.对上式一般的教科书中从未给出P 、Q 的具0体求法, P 、Q 的初等变换求法如下:下面利用上述P 、Q 讨论线性方程组解的问题.设有齐次线性方程组(2 A X =0式中, A 同(1 式.设Q =(a 1, a 2, , a n , 则由(1 得, A a r + 1=0, , A a n =0, a r +1, , a n 是(2 的解向量, 又秩A =r , Q 可逆, 得a r +1, a r +2, , a n 是齐线性方程组(2 的一个基础解系.现考虑一般线性方程组A X =b收稿日期:20000327, 男, 浙江宁波人, 学士, 讲师作者简介:江旭光(1956-(372淮北煤师院学报2000 年其中b =(b 1, b 2, , b m T , X =(x 1, x 2, , x n T , A 如上 . 第2期江旭光 求矩阵秩分解的初等变换法及其应用73故该方程组通解为=0+k 1a 3+k 2a 4(k 3, k 4为任意实数参考文献:1张禾瑞, 郝钅丙新. 高等代数(第三版 M .北京:高等教育出版社,1983.The Elementary Operations Method of R ank Decompsion and Its ApplicationJ IAN G Xu 2guang(Staf f and Workers U niversity S ubordi nate to A uhui Provi nce , Hef ei 230001Abstract :In this paper ,a elementrary operations method is given for finding factor matrix in rank decomposition of matrix A with rank r and applied to solve linear equations.K ey w rods :rank decomposition ;elementary operations ;solve linear equations田东风, 欧 飞, 申 维(中国地质大学信息工程学院。北京100083摘要:用改进的截断与转换的矩阵奇异值分解算法。设计实现了基于字频特征的中文文本分类器.理论分析与实验结果表明,采用的方法提高了数值计算精度,降低了文本集特征空间的维数,简化了文本分类算法 的时间复杂度。提高了文本分类准确率.关键词:奇异值分解;文本分类;特征选择1引 言文本分类旨在对文本集进行自动合理分类.它包括对训练文本提取类标签、判定新文本 的类属及模型评测等一系列的计算机自动处理.文本分类是模式分类和自然语言处理的交 叉学科,它与普通模式分类相比有如下特性1。3:1特征空间维数较高当我们把词作为中文文本的特征元素时,即使一个1000篇左右的训练文档集,一般也 会产生上万个候选特征元素,从而导致特征空间维数太高.如何降低特征空间维数又不使真 实信息大量损失是文本分类研究的重点之一.2特征词歧义现象一个特征可能有多种含义,如:“教授”这个特征既可以表示职称,也可以表示传授知识. 另一方面,许多相同的含义可以用不同的特征来描述,如:“计算机”和“电脑”这两个特征又 常用来表示同一含义.3特征词分布稀疏在文本分类中,可以作为文本特征的往往是那些在语料库中出现频数适中的词.对一具 体文本来说。特征空间中多数特征词在该文本中出现频率通常为零,这导致表示该文本的文 本向量中的多数元素的值为零,此即所谓特征词分布稀疏.4海量文本的快速分类随着文本处理规模的增大,对文本分类器的分类速度提出了更高的要求.如何在不降低 分类精度的前提下,降低分类算法的时间复杂度,提高文本分类器的分类速度,又是文本分 类研究的另一重点.上述特性决定了文本分类模型的多样性:朴素贝叶斯模型,决策树分类法,最近K邻居 方法(KNN,支持向量机方法(SVM,人工神经网络方法等.中文文本分类模型可以简单 地以特征空间中的特征元素是词还是字分为两类:词分类器和字分类器.词分类器不但需要收稿日期:2007071924期 田东风,等:矩阵奇异值分解理论在中文文本分类中的应用 133解决特征空间维数高、特征词歧义、特征词分布稀疏的问题,还需要一个超大容量的精确词 表和解决中文切词这一难题.本文研究的是实现一个中文文本字分类器.它用汉字作为文本表示的基本单元,用字频 向量表示文本,由训练文本集生成的特征空间中的特征元素是字频而不是词频.因此,它不 需要任何词表,不用中文切词,特征空间中特征元素个数恒定.特征空间中的特征元素是字 频向量仍会导致特征空间的维数较高和特征元素分布稀疏.对此,我们采用矩阵奇异值分解 (SVD的方法进行处理.文献43在SVD方法应用于智能信息检索方面做了开创性工作;文 献56在设计基于字频向量的中文文本分类器和应用SVD方法于中文文本分类方面作出 了新贡献.本文在研究文献“卅的基础上,进一步深入细致分析矩阵奇异值分解方法的数值 计算特性和应用方式,在分解、截断和转换的算法选择和相似度计算等方面做了进一步研 究.本文既进行了用SVD方法的文本分类实验,还进行了KNN、SVM方法的文本分类的实 验.理论分析和实验结果表明,本文采用的改进的截断与转换的奇异值分解算法,提高了数 值计算精度,降低了特征空间维数、缩小了特征字分布稀疏度、简化了降低分类算法的时间 复杂度和提高了文本分类准确率.本文内容组织如下:第二部分剖析矩阵奇异值分解的数值计算特性和应用方式,给出改 进的截断与转换的SVD方法应用于文本分类时的实用算法;第三部分用SVD方法进行文本 分类实验;第四部分用KNN、SVM进行文本分类的实验;各项实验均取得较详细的实验评 测数据.2矩阵奇异值分解理论与文本分类算法SVD是一种有效的矩阵特征提取方法.矩阵的奇异值反映了矩阵向量间的内在代数本 质,具备良好的数值稳定性和几何不变性口,它在语音识别、图像处理、控制论等众多领域 有着重要应用.定义 设A为恕×研非零矩阵,r(A=rmin(n,研,A7A的非零特征值为A,A。J。一九>0,记矾=九(i一1,2,r,称毋为A的奇异值.如果存在分解式: A。x.=U。×。D。×。y,辨×,其中U。×。,y。×。是正交矩阵,D。一diag(D,0,D,=diag(a1,口:,O"r,则称该分解式 为A的奇异值分解.不失一般性,设m孵.定理任意非零矩阵的奇异值分解必存在.注:本定理条件的平凡导致其应用的范围极其广泛.性质1(奇异值对扰动的数值稳定性设A,B9“分别具有奇异值盯。盯。d。0和r。r:岛0,则 I巩一t l0AB|I 2,i=1,2,疗.性质2设A9“,具有奇异值口,cr2以0,则0A 0:一口,(谱范数_-_-_-_-_一II A II,=口;+,(Frobenius范数134数学的实践与认识 38卷Idet AI=口l,吒'.,吒,(行列式模实现奇异值分解的算法主要有两种:算法Ia求A7A的特征值和特征向量,得A 7A=Vdiag(D,2,OV7,V=(yl,V2。V1为m×r列正交矩阵;b计算U。=AV,D;-1,U。为理×r列正交矩阵;c扩充U。,得靠×咒列正交矩阵:U。=(U。U。.从而有A。=U。Dn。,y二。.算法IIa先用Householder变换左乘、右乘A,使A化为双对角形,即存在,l×咒正交矩阵P 和m×m正交矩阵Q使得:/E朋Q 2lo J其中E为m×m双对角形矩阵(即除对角线和上次对角线之外,其余元素均为零. b利用变形的QR方法。通过迭代运算。使E的上次对角线元素逐渐减小到零从而把 E对角化,最后得到A的奇异值分解.变形Q尺方法是基于QR分解求一般矩阵特征值和特 征向量的方法. (以上定理和性质的证明参见ET-e从数值计算的观点看算法I不如算法II好.主要是A7A的运算量大且容易引入较大的 误差引.本文采用算法II进行奇异值分解的计算.要使奇异值分解的结果能实际用于我们的中文文本分类器,还需进行截断与转换.记 U。×。一(“1,U2,U。,V。×。=(z,1,口2'.,可。,则有奇异值分解A。×。=U。×。Dn×my二×。的等 价形式:A。=九地口:.根据奇异值的含义及分解式中奇异值能有从大到小的降序排i=1列方式,我们先进行如下的截断:I 一设kr,记A。=九UiVi,也即AI=(“1,U 1.IU。DkV:, 其中仉、取、y:的阶分别为:,2×k、k×k、k×m.V。的阶为m×愚.用A。近似的代替A(我们称之为截断的奇异值分解式.截断奇异值分解的误差估计可 用下式计算:J_-_一l|AA。0。=丸+。,(谱范数-_-。-_。_。_-_-。_-_-。-_一lI AA。0F=九+l+t+2+,(Frobenius范数本文中计算矩阵AA。的截断误差用谱范数.下面进一步用图1来直观描述SVD及其截断:k,.m疗 24期 田东风,等:矩阵奇异值分解理论在中文文本分类中的应用 135图1奇异值分解的图形描述.其中U、D和矿中的阴影部分表示截断后形成的矩阵.仅有截断的SVD分解不够,我们要进行特征空间的转换:令V。=Afm,nU。,。D矗。, A。一y。,即用m×k阶的n代替珂×m阶的A。,注意到m咒(实际问题是满足 m<<咒和kr,我们实现了降低特征空间维数及降低特征元素分布稀疏度的目标.不但 要截断并转换了特征空间,还要相应截断并转换待分类的文本向量:对由某待分类文本生成 的文本向量z,进行维数截断和转换:z一;一(一U。D71,即用k×1阶的;代替咒×1阶的z.下面我们再给出实现中文文本分类算法完整步骤的描述:i对由训练文本生成的特征空间A,计算A的奇异值分解后进行截断和转换:AA。 一Vt,(n=AU。D;-1,实现用m×k阶的n代替,l×m阶的A(m<恕,kr,达到降 维去噪目的;ii对由某待分类文本生成的文本向量z,进行降维去噪:zz=(z7UtD71,实现用 志×1阶的z代替以×1阶的z;y;v:iii计算文本向量;与矩阵Vt中每一个向量y之间的相似度:d=兰;兰.即用两 。 霹y;个向量夹角的余弦来作为相似度的度量.;将属于相似度最大的文档类别.通过以上分析,我们可以得出如下结论:分解、截断与转换的SVD方法使我们在特征字 与文本的关系中既能捕获大量重要的结构信息,又能降低特征空间维数(去除了“噪声”和 特征元素分布稀疏度,从而降低分类算法的时间复杂度.3用SVD方法的具体文本分类实验我们选择了农业,教育,政治,法律,经济五种类别各80篇文章,共约125万字.对其中使 用的GB一2312一二级汉字库的6768个汉字的字频进行统计,得到反映该五类文本的5个标 准向量(6768维向量,以这5个标准向量为列构成一个6768×5的矩阵A.对每一个待分类 的新文本。同样统计这6768个字符的字频,得到一个待分类的向量,按前述文本分类的算法 进行类属判别.整个实验的算法流程如图2所示.6768×5阶的矩阵A的列向量分别按农业,教育,政治,法律,经济的顺序排列,对A进 行奇异值分解计算和截断,得到A的截断的奇异值分解。其中D。、y。的实际计算结果如下 (U。的行维数太大,此处略去:136数学的实践与认识 38卷 训练文本 测试文本图2算法流程0O0OO O141540O 11301然后对每类文本随机选择测试文本50篇进行分类测试,每一类的分类结果如表1所示; 其中,口表示判为i类且确实属于这一类的文本数目;6表示判为i类但实际并不属于这一类 的文本数目;c表示判为非i类且确实不属于这一类的文本数目;d表示判为非i类但实际上 却属于这一类的文本数目.表1分类结果政治判为政治类文本数目25042466=4趔发韭堕渔差塞奎筮旦三2QQ !三!§垡三! .法律翥篇暑耄。 4=48c=1966=4d=2经济翥嬲暑嚣。 口一46f=1946=6d=4 24期 鞭东风,等:矩阵奇异值分解理论在中文文本分类巾的应用 137在文本分类的评测中,查全率,查准率,碰确率和综合分类率(即F,值这四种常用评测 指标的计算方法为:查全率r=a/(a+d.旋准率Pa/(a+d,正确率t=(口+c/n, Fl一2rp/(r+夕,|一a+b+c+d,本实验的评测结果凳表2帮图3.袭2评测结果(单位:% 扶实验评溅数据霹淡看出,本文 方法的分类准确率是比较高的(尤其 是与同类型文本分类器相比.分类 错误较多出褒在致治穰经济类别盼 文章中.仔细分析出现分类错误的文 本,发现它们都是属于这两个类别交 叉的文章,容易崮理分类错误.4用SVD、KNN、SVM进行文豳3评测缕祭比较图本分类的多方法对院实验我们还用同样的训练文本和测试文本做了与KNN方法和SVM方法的比较测评.表3为KNN方法的分类结果,表4为KNN方法的评测结祭,表5为SVM方法的分类结果,表6为SVM方法的评测结果.KNN方法和SVM方法的分类实验都愚在基于词的切分稷词频的 统计上的所进行的,采用的是的巾文自然语富处理开放平台上的汗源软件.豢3KNN秀法戆分类缝纂138数学的实践与认识38卷表4KNN方法的评测结果(单位:%类男口查全率查准率正确率F-值平均结果98.498.599.398.3 图4KNN方法评测结果比较图 表5SVM方法的分类结果表6SVM方法的评测结果(单位:%类别查全率查准率正确率FI值99.699.699.899.5m呱 冁m648m 吼 咄m 呱加 6 O O.O O m 瑚 si瑚 m 加O O 讯m m 呱业育治律济农毂攻法经24期 鞭东风,等:瓶阵奇异值分解理论在中文文本分类巾的应用 139网5SVM方法评测结果比较图实验评测结果表明,SVD、KNN和SVM这三类方法的分类准确率都较高.尽管SVD 方法在一些评测指标上路低于KNN和SVM方法,但SVD方法的评澳l指标有不依赖于词 表,算法时间复杂度低的优点.5总 结理论分析和实验结果表明,用字作为文本表示的基本单元,用字频向爨表示文本,使用 改进的截断鸯转换戆奄异值分解方法进行牵文文本分类,提高了数值计算精度,达到了降低 特征空间维数、降低特征字分布稀疏度、降低分类算法的时间复杂度和提高文本分类准确率 的效果.本文方法还有待进行更大文本规模和更多语料类别的测试研究.参考文藏:1【2】 3】 4密】 C6 7 83 王强,王晓兜.关毅,徐惠明.KNN与SVM相融合的文本分类技术研究J.高技术通讯,2005。15(5:1924. 都云琪。巍渗竣.基于支持疯重视的孛文文搴自动分类研究0。谤算机工程,2002。28(11137-138.郭祟慧。羚建涛,陆玉最.广义支持舞薰税优化闯蘑的搬大缡方法cj.系统工程瑷论与实践,2005,25(6:2532. Berry M W,Dumais S T.Using linear algebra for intelligent information retrievalJ.SIAM Review。1995,37(4l 573595。王梦云,謦索毒。基于字簇彝蠢豹孛交文拳垂羲努类系统馨。繁援学援,2000。19(6:644.649.刘贵龙,王慧玲,宋柔.嫩阵的奇异值分解在文本分擞研究中的应用口.计算机工程.2002。28(12:1719.高惠璇.统计计算M.北京:北京大学出版社,2003.徐树方。矩簿计算的理沦岛穷法M3.:It束;憩意大学蹬舨社,2001.On the Application of Matrix Singular ValueDecomposition Theory in ChineseText ClassificatiOnTIAN Dongfeng, OU Fei, SHEN Wei(School of Information Engineering,China University of Geosciences,Beijing 100083,China140数攀鹣实黢与试谖 38卷 AbstractBy virtue of the improved truncationtransformation algorithm forthe matrix singular value decomposition,we establish a Chinese text classific