（计算机应用技术专业论文）基于因子分析的文本分类.pdf

东北大学硕士学位论文 摘要 基于因子分析的文本分类 摘要 从2 0 世纪9 0 年代以来，伴随互联网的飞速发展，出现了大量的电子文档。如何对 这些无结构的自然语言文本进行有效的管理和使用成为一个重要的研究问题。一些自然 语言的处理技术例如信息检索、数据挖掘、文本分类等快速地发展起来。 文本分类是信息处理的一个重要研究领域。与其他的分类任务相比，文本分类本身 一个最重要的特点是，文本分类通常用词作为分类的特征。词的数目非常大，几千，几 万，甚至几十万。分类特征非常多，普通的分类器难以很好的完成分类任务。如何有效 的减少分类的特征，而同时要保证分类的性能就成为重要的研究内容。特征降维的方法 通常分为特征选取和特征抽取两类。在本文中重点研究了采用因子分析技术进行特征抽 取的方法。 潜在语义索引是种最常用的特征抽取技术，通过对项一文本矩阵的分解，利用词 之间的共现信息来抽取特征，文本表示从原来高维词空间的文本向量线性映射到潜在语 义空间的低维向量。潜在语义索引是一种非常好的特征降维的方法；它可n _ t n 用很少的 维数保存文本绝大部分的分类信息，而且能够去除数据集中的噪声来提高分类的效果。 文中对潜在语义索引对于特征降维的能力进行了研究，与常用特征选取方法如信息增 益，文档频度，互信息等进行了比较分析。实验结果表明，潜在语义索引是一种很好的 降维技术，可以用很少的特征而得到非常好的分类效果。 因为潜在语义索引采用奇异值分解实现，所有的运算都是线性转换，所以得到的新 特征是由原始特征( 词) 信息的线性组合得到的。而有些对分类有用的信息是非线性的， 潜在语义索引方法无法对这些信息很好的进行表示。 核主成分分析与潜在语义索引很相似，也是一种因子分析技术。核主成分分析通过 引入核方法，把文本从词空间映射到非常高维的特征空间后，再进行主成分分析，抽取 非线性特征。核主成分分析能成功的避开潜在语义索引的线性限制，从而能够抽取到更 适合分类的特征。核主成分分析与k n n 分类器组合模型取得很好的分类性能。本文选 用多项式核函数，并对多项式核函数的参数对分类性能影响进行初步探讨。在中文和英 文数据集上的实验结果表明，核主成分分析用来作特征抽取能够达到或者超过潜在语义 一i i 东北大学硕士学位论文 摘要 索引方法的分类效果。 关键词：文本分类；潜在语义索引；核主成分分析；k n n ；因子分析 ，i i i 东北大学硕士学位论文 f a c t o r a n a l y s i sb a s e dt e x tc a t e g o r i z a t i o n a b s t r a c t a1 0 to fd o c u m e n t sa p p e a rw i t ht h er a p i dd e v e l o p m e n to fi n t e m e ts i n c et h e 9 0 so ft h e 2 0 t hc e n t u r y t h ep r o b l e mo fh o wt oe f f e c t i v e l ym a n a g ea n da c c e s st h e s eu n s t r u c t u r e dt e x t s b e c o m e sa l li m p o r t a n ti s s u eo fi n v e s t i g a t i o n n a t u r a ll a n u a g ep r o c e s s i o n gt e c h n i q u e sa r e d e v e l o p i n gr a p i d l y , s u c ha si n f o r m a t i o nr e t r i e v a l ，d a t em i n i n g ，t e x tc a t e g o r i z a t i o n ，e t c t e x tc a t e g o r i z a t i o nh a sb e c o m ea l li m p o r t a n td o m a i no fi n v e s t i g a t i o ni ni n f o r m a t i o n p r o c e s s i n g c o m p a r i n gw i t h o t h e rc l a s s i f i c a t i o n t a s k s ，am a j o rc h a r a c t e r i s t i c o ft e x t c a t e g o r i z a t i o ni st h a tw o r d sa r eo f t e nc h o o s e na sf e a t u r e sf o rc l a s s i f i c a t i o n t h e r ea r e t h o u s a n d ，t e n so rh u n d r e d so ft h o u s a n d so fw o r d si nt h et e x tc o l l e c t i o n t h a tm a k e si t d i f f i c t u l tf o rn o r m a lc l a s s i f i e r st of i n i s ht h ec l a s s i f i c a t i o nt a s k sw i t l ls om a n yf e a t u r e s h o wt o e f f e c t i v e l yr e d u c et h ef e a t u r e sw h i l ek e e p i n gt h ep e r f o r m a n c eo fc l a s s i f i c a t i o nb e c o m e sa n i m p o r t a n ti s s u ef o ri n v e s t i g a t i o n t h e r ea r et w ok i n d so f m e t h o d sf o rf e a t u r er e d u c t i o n ，o n ei s f e a t u r es e l e c t i o na n dt h eo t h e ri sf e a t u r ee x t r a c t i o n i nt h i sp a p e rf a c t o ra n a l y s i sb a s e df e a t u r e e x t r a c t i o n sa r et h em a i nf o c u s e so ft h i sp a p e r l a t e n ts e m a n t i ci n d e x i n gi so f t e nu s e da saf o a t u r ee x t r a c t i o nt e c h n i q u e ，w h i c ht r yt og e t f e a t u r e sb yo b s e r v i n gt h ec o o c c u r r e n c eo ft e r m sw i mt h ed e c o m p o s i t i o no ft e r m - d o c u m e n t m a t r i x ，w h i c hc o n v e r t st h et e x tv e c t o r sw i t hh i g hd i m e n s i o n a l i t yi nt h et e r ms p a c e st ov e c t o r s w i t hl o wd i m e n s i o n a l i t yi nt h el a t e n ts e m a n t i cs p a c e l a t e n ts e m a n t i ci n d e x i n gi s g o o d m e t h o df o rf e a t u r er e d u c t i o n a n di tc a nh o l dm o s to ft h ei n f o r m a t i o nf o rc l a s s i f i c a t i o nw i t h v e r ys m a l ld i m e n t i o n s ，a n di ta l s or e m o v e st h en o i s ei nt h ed a t a s e ts oa st oi m p r o v et h e p e r f o r m a n c eo fc l a s s i f i c a t i o n t h i sp a p e rf o c u s e so nt h ef e a t u r er e d u c t i o no fl a t e n ts e m a n t i c i n d e x i n g ，a n dac o m p a r i s o nb e t w e e nl a t e n ts e m a n t i ci n d e x i n ga n ds o m ef e t u r es e l e c t i o n si s g i v e n ，s u c h a si n f o r m a t i o ng a i n ，d o c u m e n tf r e q u e n c y , m u t u a li n f o r m a t i o n ，e t c t h e e x p e r i m e n tr e s u l t sd e m o n s t r a t et h a tl a t e n ts e m a n t i ci n d e x i n gi sav e r yg o o dt e c h n i q u ef o r f e a t u r er e d u c t i o n ，a n di tc a r la c h i e v eg o o dp e r f o r m a n c eo nc l a s s i f i c a t i o nw i t hv e r ys m a l l f e a t u r e se x t r a c t e d b e c a u s el a t e n ts e m a n t i ci n d e x i n gi sp e r f o r m e db ys i n g l a rv a l u ed e c o m p o s i t i o n ( s v d ) ， i v 东北大学硕士学位论文 w h i c hi sd o n eb yl i n e a rt r a n s f o r m a t i o n s t h en e wf e a t u r e sa r el i n e a rc o m b i n a i o no ft h e o r i g i n a lo n e s s o m ei n f o r m a t i o nf o rc l a s s i f i c a t i o ni sn o tl i n e a r , a n dl a t e n ts e m a n t i ci n d e x i n g c a nn o tg i v eg o o dr e p r e s e n t a t i o nf o ri t k e m e lp r i n c i p a lc o m p o n e n ta n a l y s i si sa l s oam e t h o do ff a c t o ra n a l y s i sw h i c hi s s i m i l a rt ol a t e n ts e m a n t i ci n d e x i n g k e r n e lp r i n c i p a lc o m p o n e n ta n a l y s i sc a nm a pt e x t s f r o mt h eo r i g i n a ls p a c ei n t oh i g h e rd i m e n t i o n a l i t ys p a c e ，i nw h i c hp r i n c i p a lc o m p o n e n t a n a l y s i si sp e r f o r m e dt og e tn o n l i n e a rf e a t u r e s k e r n e lp r i n c i p a lc o m p o n e n ta n a l y s i sc a n a v o i dt h el i n e a rl i m i t a t i o no fl a t e n ts e m a n t i ci n d e x i n g , a n dg e tf e a t u r e sw h i c ha r em o r e s u i t a b l ef o rc l a s s i f i c a t i o n t h em o d e lw i t hk e r n e lp r i n c i p a lc o m p o n e n ta n a l y s i sa n dk n n a c h i e v eg o o dp e r f o r m a n c eo nc l a s s i f i c a t i o n p o l y n o m i a lk e m e l sa r es e l e c e da n dt h e p a r a m e t e ro fd e g r e ei sa l s os t u d i e di n t h i sp a p e r t h ee x p e r i m e n tr e s u l t so nc h i n e s ea n d e n g l i s hd a t a s e t ss h o wt h a tk e m e lp r i n c i p a lc o m p o n e n ta n a l y s i sc a nw o r ka sw e l la so r b e t t e rt h a nl a t e n ts e m a n t i ci n d e x i n g k e yw o r d s ：t e x tc l a s s i f i c a t i o n ；l a t e n ts e m a n t i ci n d e x i n g ；k e m e lp r i n c i p a lc o m p o n e n t a n a l y i s ；k n n ；f a c t o ra n a l y s i s v 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加 以标注和致谢的地方外，不包含其他人已经发表或撰写过的研究成果，也不包括本人为 获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论 文中作了明确的说明并表示诚挚的谢意。 学位论文作者签名： 签字日期 学位论文版权使用授权书 蕉榔1 1 1 年1 rl 瑚 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即 学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交 流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 学位论文作者签名：导师签名 签字f t 期：签字日期 东北大学硕士学位论文 第一章前言 第一章前言 1 1 研究背景 从2 0 世纪9 0 年代以来，信息技术迅猛发展，特别是互联网的飞速发展，使得整个 世界的联系更加紧密，人们可以获得的信息数量急剧增加，大量信息以计算机可读的电 子文档形式存在。这一方面为信息处理技术的发展准备了充分的资源，另一方面又强化 了对于便捷、快速、自动的信息处理技术的迫切需求。如果不能很好的对这些信息进行 管理，人们就如同置身于信息的海洋中，难以方便自如的寻找到所需要的知识，因此迫 切需要有效管理这些资源的方法，用有效的方式来查找、过滤和获取所需的信息【1 1 。正 是在这样的环境下，相关的信息处理技术，例如信息检索、数据挖掘、文本分类等快速 的发展起来。 i n t e m e t 上电子文档大多是半结构化文本或者是无结构的自然语言文本的形式存 在。如何对于自然语言的文本资源进行有效的管理成为信息处理的一个重要的研究课 题。文本分类就是给自然语言的文本加上预定义的类别标签，把一个文本分配到一个或 者多个预定义好的类别中去【1 o 文本分类的历史可以追述到2 0 世纪6 0 年代，但是直到 2 0 世纪9 0 年代伴随i n t e m e t 的快速发展才真正发展成为信息系统学科的一个重要的研 究领域。文本分类处在机器学习和信息检索两门学科的交叉点上，和文本挖掘很相似。 文本挖掘通过对大规模文本的分析，找到有用的模式并抽取信息，所以文本分类可以看 作是文本挖掘的一种特例。 在2 0 世纪9 0 年代之前，最常用的文本分类方法是知识工程的方法，对给定类别， 利用专家的知识，手工编写一个规则集对文本进行分类。比如h a y e s 和w e i n s t e i n 的 c o n s t r u e 系统，就是利用规则对r e u t e r s 新闻故事进行分类f 1 5 】。但是这种分类系统 对类别作出是或者不是的硬性判定，系统的性能依赖于专家的知识和技能，而且很难更 改，移植性能也不好。另一种策略是采用归纳学习技术，利用标注好的训练数据来自动 构建分类器。9 0 年代之后，机器学习的技术开始广泛应用到文本分类中，成为文本分 类的主流技术【l 】。这些方法不需要拥有特定专业知识的专家的参与，节省了人力，而同 时能够达到专家系统的准确度。自动文本分类器的优势还在于容易构建和更新，它需要 的特征人们很容易能提供。而且自动文本分类器能根据用户需求进行定制，允许用户按 东北大学硕士学位论文 第一章前言 照自己任务在准确率( p r e c i s i o n ) 和召回率( r e c a l l ) 之间进行权衡和调整，所以非常灵活 1 5 1 。本文也是采用机器学习的方法实现文本自动分类。 基于机器学习的文本分类通常由训练和分类两个阶段组成。在训练阶段，分类器利 用训练数据来学习分类的参数；在分类阶段或者评价阶段，利用训练好的分类器把测试 文本分到最可能的类别中，然后与标准答案进行比较和评价。目前已经有很多的统计分 类和机器学习技术应用到文本分类中，包括多变量回归模型1 9 1 ，k - n e a r e s tn e i g h b o r 分 类器【3 】，贝叶斯分类器 2 ，神经网络分类器【1 6 】【”1 ， 基于规则的学习器【1 8 ，核心向量分 类器川以及支持向量机4 1 等。 文本分类广泛应用到许多的领域，例如文本的过滤，w e b 页面的层次分类，语义消 歧等文本处理的多个方面【1 1 。自动文本分类在很多动态的和个性化的信息管理任务中起 到重要的作用，比如邮件实时的分类和文件层次分类，通过对主题的识别来支持对特定 主题的操作等。分类技术既能支持相对静态的分类，例如对于m e d i c a ls u b j e c t h e a d i n g s ( m e s h ) 的分类，雅虎的主题层次分类( y a h o o ! st o p i ch i e r a r c h y ) 等，也能支 持那些动态的、与个人兴趣相关的分类情况【l ”。 在英文自动分类方面，目前已经建立的标准的分类语料库有o h s l r m e d 、r e u t e r s 、 2 0n e w s g r o u p s 、a pc o l l e c t i o n , , t r e c - 3 “r o u t i n g ”c o l l e c t i o n 等；对于分类性能的评价， 也有一套统一的评价方法 1 1 。国内在中文文本分类领域也进行了大量的相关研究，比 如黄萱菁等把白适应技术应用到文本过滤系统，取得了较好性能 2 0 】；刘昌钰等提出了基 于潜在语义分析与b a y e s 分类的b b s 文档鉴别方法 2 1 ；解冲锋等提出一个基于序列的 文本自动分类算法2 2 】；孙建涛等对用于文本分类的多项式核支持向量机的泛化能力进行 了研究等。 1 2 特征表示与降维 一个自然语言文本是不能被分类器或者是一个分类算法直接解释处理的，所以需要 一个建立索引的过程。这个过程就是把自然语言的文本用一种简洁有效的方式表示出 来。现在已经有很多建立索引的方法，这些方法都是应用到对训练集、测试集和验证集 上，得到文本的表示。 对于文本分类任务来说，一个非常重要的问题是文本的表示。在文本分类中，特征 的表示方法对于分类性能的影响是决定性的25 1 。文本表示的选择依赖于对文本语义单元 的选择和对这些单元的进行组合的规则。在信息检索中，文本一般采用文本中出现的 2 东北大学硕士学位论文 第一章前言 索引项组成的向量来表示。不同的表示方法的区别主要在下面两个方面： ( 1 ) 对索引项的理解不同。 ( 2 ) 对索引项的权重计算不同。 一种最典型的索引项的选择是用所有在文本中出现过的词作为特征，通常称之为 b a go f w o r d s ( b o w ) 方法【l 】【25 1 。而很多的实验也表明，这种方法要比很多复杂的表示方 式效果要好。也有很多实验用名词短语( n o u np h r a s e s ) 而不是单个的词作为索引项，但 是实验结果并不理想。短语一般有语法驱动的短语和统计驱动的短语。语法驱动的短 语是依据语言的语法特征抽取的短语；而统计驱动的短语是选取文本集合中经常出现的 由连续的词组成的高频词串。l e w i s 认为虽然短语有较强的语义属性，但是相对于用词 作索引项的方法，它的统计特性很差【5 5 1 。尽管如此，采用短语作为索引项的方法，特别 是统计驱动的短语仍然是研究的一个热点。 在b o w 模型中，采用词作为索引，每个文本用一个词向量来表示。例如 d ，= ( w 1w 2 w d l ，对应每个词采用一定的权重，常用的权重计算方法有t f i d f 等。b o w 模型的方法认为词之间都是独立的，不考虑文本中词之间的依赖性。而文本的表示仅仅 利用了词的表层信息，不考虑词的语义信息或者称之为概念信息 2 5 。b o w 模型不能解 释同义词和多义词现象。另外b o w 模型用词作特征，词的数目非常大，所以特征集合 规模很大，从几千到几十万，分类的计算复杂度很高。这就需要降维技术把文本索引项 的数目从，降低到，其中，。 降维的另外一个优点是能降低过度拟和( o v e m t 血g ) 的程度【l 】。过度拟和是指分类器 能够对训练数据拟和得非常的好，但是对于新的未知数据的分类效果很差，也就是说分 类器的泛化能力很差。比如对于车这个类别如果只有3 个训练正例，而其中2 个是关 注黄色的车，那么分类器就可能错误的把“黄色”作为车的一个必需的特征，而很明显“黄 色”只是一个偶然的特征，这样分类器在分类的时候就会出错。有研究表明，为了避免 过度拟和现象，训练样本的数目和索引项的数目是成一定比例的。f u h r 和b u c k l e y 认为 文本分类任务中每个索引项需要5 0 - - 1 0 0 个训练样本 蚓。这样，在同样的训练样本的条 件下，降低索引项的数目能够在一定程度上避免过度拟和。 降维技术可以分为两种，局部的每个类别的降维和全局的降维。对于局部降维方法， 每个类别选取，个索引项( r r ) 来支持对于类别t 的分类。也就是说一篇文本对应 不同的类别有不同的表示，实际上就是根据不同的类别选用不同的特征集生成文本表 3 一 东北大学硕士学位论文 第一章前言 示。而全局的降维技术是选取r 。个索引项( r ，) 来支持所有类别的分类。 另外还可以根据降维得到的特征对降维技术进行分类。一种称为特征选取，从原 来的，个索引项集合中选择，个索引项( r r ) 作为特征集合；另一种称为特征抽取， ，个索引项并不是原来的r 个索引项集合的子集，也就是说它们不是同一性质的特征， ，个索引项是原来的r 个索引项通过转换或者组合得到的。 在特征选取方法中，y a n g 已经证明采用特征选取的方法降维后，分类性能大约有 5 的增长【5 1 。一种称为w r a p p e r 的方法能够针对学习算法来查找特征子集，但是它的计 算代价很大。常用的特征选取方法是过滤的方法，根据预先定义的数值函数来度量每个 词对于分类的重要性，选择r 个词作为特征集合。常用的方法有信息增益j ( i n f o r m a t i o n g a i n ) ，文档频度( d o c u m e n tf r e q u e n c y ) ，互信息( m u t u a li n f o r m a t i o n ) ，c h i s q u a r e ( c h i ) ， 相关系数( c o r r e l a t i o nc o e f f i c i e n t ) 相关分数( r e l e v a n c ys c o r e ) ，o d d s r a t i o ，s i m p l i f i e d c h i s q u a r e 等。这些方法的基本思想都是对每一个特征( 在这里是中文词) ，计算某种统 计度量值，然后设定一个阈值，把度量值小于阈值的那些特征过滤掉，剩下的认为是有 效特征。 特征抽取是从原来，个索引项合成r ( r r ) 个新的具有最大效力的索引项。这 种文本的表示方法，称之为b a g - o f - c o n c e p t s ( b o c ) 2 5 1 。这种方法的原理是，因为存在多 义词、同义词和近义词的问题，原来的索引项并不是文本表示的最优维数，所以特征抽 取就是要生成不受这些问题困扰的人工特征，称为概念或者语义。在文本分类领域已经 有两种方法得到应用，即词聚类和潜在语义索引。词聚类方法的目标是把高阶的语义相 关的词组成一个词簇，这样词簇就可以代替词作为向量空间模型的维数表示。词聚类和 特征选取不同，特征抽取用来解决同义词或者近义词带来的冗余信息的问题，而特征选 取是为了去掉不携带信息或者携带信息量少的词。任何一个词聚类方法都要描述如何把 词聚成簇以及如何把原来的文本表示转换成用词簇表示。常用的有无指导聚类的方法和 有指导的聚类方法。而另一种特征抽取方法是利用词在语料中的分布抽取潜在概念信 息，比如潜在语义索i ( l a t e n ts e m a n t i ci n d e x i n g ) ，它利用词的共现特性，采用因子分析 的技术，来抽取概念作为特征。这种方法得到的特征是抽象的概念，不是原来的词，而 是原来的词的组合作为特征。而采用抽取概念作为特征的方法特征空间较小，一般看作 是特征降维的一种方法。另外还有概率潜在语义索引俾l s i ) 1 5 4 1 5 ”，l a t e n td i r i c h l e t a l l o c a t i o n ( l d a ) 5 8 】等语言模型用来抽取概念。其中词聚类和潜在语义索引技术是应用 最为广泛的方法。 4 东北大学硕士学位论文 第一章前言 潜在语义索引是一种因子分析技术，用它抽取很少数目的特征就可以达到很好的表 示能力，而且有较好的去除噪声的作用，在信息检索、文本分类等方面应用广泛。另外 由于潜在语义索引技术是一种线性方法，这也在一定程度上限制了它的特征抽取能力。 要利用因子分析技术得到更加适合分类的特征，就需要引入非线性映射的技术。核主成 分分析是一种利用核进行特征抽取的因子分析方法，能很方便的抽取到非线性的特征， 这样可以利用词之间关系得到非线性特征来表示文本，提高文本的表示能力和分类效 果。 本文主要研究这两种基于因子分析的特征抽取方法：潜在语义索引和核主成分分 析。 1 2 1 潜在语义索引 传统的向量空间模型内在的假设是各个词的出现是独立的，这很明显难与事实相 符，并且很难解释同义词和多义词的现象。潜在语义索引( l a t e n ts e m a n t i ci n d e x i n g ， l s i ) 在1 9 9 0 年由d e e r w e s t e r 等作为一种新的自动索引和检索技术引入到信息检索领域 【”。这种方法致力于找到项( t e r m ，词、短语等特征) 与文本( t e r m d o c u m e n t ) 间的潜在 联系，也就是文本的潜在语义结构，作为文本的表示。 潜在语义索引采用因子分析的技术，分析项与文本之间关系中内在的较高阶的结构 来找到与查询相关的文本。它利用奇异值分解( s v d ) 的方法，把原来的项一文本矩阵 分解后，只保留几百个最大的奇异值对应的奇异向量，而忽略其余的很小奇异值对应的 奇异向量。原来的文本向量可以通过这些奇异向量的线性组合来逼近。这样原来的文本 就可以用几百维的权重因子向量来表示。查询可以通过矩阵相乘的方式转化到潜在语义 空间。s v d 用来找到从原始的文本向量空间到低维空间的映射函数。 潜在语义索引技术通过线性映射把原来高维的向量压缩为非常低维的向量，并且新 生成的特征之间是相互独立的。潜在语义索引的另一个特点是，新生成的特征是原来特 征的组合，不是一个词，它是很难在直观上给出解释，但是它能很好的找到词汇的隐含 结构。 w i e n e r 采用两种策略来应用潜在语义索引，分别是局部l s i 和全局l s i 。局部l s i 对于每个主题的文本矩阵单独用s v d 分解生成l s i 的一种表示方式，而全局的l s i 对 于整个的文本集的表示矩阵进行s v d 矩阵分解，对每一篇文本生成唯一的l s i 表示。 w i e n e r 的实验表明局部l s i 的方法要比全局l s i 性能好，但局部l s i 的方法计算复杂， 5 一 东北大学硕士学位论文 第一章前言 应用性很差 1 6 】。( s c h u t z e ，1 9 9 5 ) 对潜在语义索引和z 2 两种方法在3 个不同的分类器 上进行比较，实验结果表明l s i 要比z 2 更有效。 s v d 的一个主要的缺点是需要对整个项一文本矩阵进行分解，计算复杂度大，k o l d a 开发出了一个新的矩阵估计算法叫半离散矩阵分解( s e m i d i s c r e t ed e c o m p o s i t i o n ，s d d ) 1 7 1 ，降低了空间需求和计算时间，但是对原始矩阵的估计没有奇异值分解( s v d ) 准确。 本文中的实验仍然采用了最常用的奇异值分解作为分解算法。 1 2 2 核主成分分析 另外一种与潜在语义索引相关的技术是主因子分析( p r i n c i p a lc o m p o n e n t a n a l y s i s ， p c a ) 。主成分分析是模式识别领域中一种经典的特征抽取和降维方法t ”】。 p c a 是一种非参数化的方法，可以从混杂的数据集中抽取有用信息。p c a 是一种 线性代数的技术，目的在于计算最有意义的一组新的基，来重新描述数据集，过滤掉噪 音数据，并且能够找到隐含的特征。它能够找到在数据空间中变化最大的方向，分辨出 那些是重要的数据方向，那些是冗余的部分。p c a 能把复杂的数据集降为低维的数据， 用来揭示一些隐含特征。 p c a 对特征的协方差矩阵进行分析，找到原来变量的组合来生成新的变量，新的 变量能够抓住数据最大的变化【矧。4 1 和4 2 节有更具体的介绍。 p c a 的成功之处主要依赖于下面两个重要的属性【5 0 1 ： ( 1 ) 主因子序列抓住了矩阵x 中最大的变化量，保证了最少的数据丢失。 ( 2 ) 主因子之间是非相关的，所以在考虑主因子的时候可以分开考虑。 p c a 是用线性代数作为基础的，抽取的特征都是线性变换得到的，这样它在特征 抽取能力上受到了限制，无法获取高阶的非线性信息。所以又有人提出了k e r n e l p c a ”1 ， s p a r s ep c a ，p p c a 【2 6 ，m p c a t 2 7 等多种非线性的扩展模型。 本文中尝试把核主成分分析【8 ( k e r n e lp c a ) 应用于文本分类的特征抽取和特征降维。 当要处理的数据高度非线性的情况下，线性的主成分分析就没有办法找到它内在的 结构。作为主成分分析的一种扩展，核主成分分析能够在高维的特征空间中来计算主成 分值，抽取非线性特征。这个高维的特征空间可以通过非线性映射庐：r ”_ ，得到，这 个空间的一个重要特性是通过庐映射后的两个点的点积可以用和函数( 1 1 ) 来估计： k ( x ，x ) 3 ( 庐( x ) 妒( x ) ) f 1 一1 ) 6 一 东北大学硕士学位论文 第一章前言 应用性很差。( s c h u t z e ，1 9 9 5 ) 对潜在语义索引和z 2 两种方法在3 个不同的分类器 e 进行比较，实验结果表明l s i 要比z 2 更有效”1 。 s v d 的一个主要的缺点是需要对整个项一文本矩阵进行分解，计算复杂度大，k o l d a 开发出了一个新的矩阵估计算法叫半离散矩阵分解( s e m i d i s c r e t ed e c o m p o s i t i o n ，s d d ) ”，降低了空间需求和计算时间，但是对原始矩阵的估计没有奇异值分解( s v d ) 准确。 本文中的实验仍然采用了最常用的奇异值分解作为分解算法。 12 2 核主成分分析 另外一种与潜在语义索引相关的技术是主因子分析( p r i n c i p a lc o m p o n e n t a n a l y s i s ， p c a ) 。主成分分析是模式识别领域中一种经典的特征抽取和降维方法m i 。 p c a 是一种非参数化的方法，可以从混杂的数据集中抽取有用信息。p c a 是一种 线性代数的技术，目的在于计算最有意义的一组新的基，来重新描述数据集，过滤掉噪 音数据，并且能够找到隐含的特征。它能够找到在数据空间中变化最大的方向，分辨出 那些是重要的数据方向，那些是冗余的部分。p c a 能把复杂的数据集降为低维的数据， 用来揭示一些隐含特征。 p c a 对特征的协方差矩阵进行分析，找到原来变量的组合来生成新的变量，新的 变量能够抓住数据最大的变化【”，4 1 和4 2 节有更具体的介绍。 p c a 的成功之处主要依赖于下面两个重要的属性： 0 ) ：v n 子序列抓住了矩阵x 中最大的变化量，保证了最少的数据丢失。 ( 2 ) 主因子之间是非相关的，所以在考虑主因子的时候可以分开考虑。 p c a 是用线性代数作为基础的，抽取的特征都是线性变换得到的，这样它在特征 抽取能力上受到了限制，无法获取高阶的非线性信息。所以又有人提出了k e r n e l p c a ”j ， s p a r s ep c a t “，p p c a 【2 6 ，_ w c a t 2 1 等多种非线性的扩展模型。 本文中尝试把核主成分分析f 8 1 ( k e r n e lp c a ) 应用于文本分类的特征抽取和特征降维。 当要处理的数据高度非线性的情况下，线性的主成分分析就没有办法找到它内在的 结构。作为主成分分析的一种扩展，核主成分分析能够在高维的特征空间中来计算主成 分值，抽取非线性特征。这个高维的特征空间可以通过非线性映射：r “_ f 得到，这 个空间的一个重要特性是通过映射后的两个点的点积可以用和函数( 1 1 ) 来估计： 个空间的一个重要特性是通过映射后的两个点的点积可以用和函数( 1 1 ) 米估计： 七( x ，互，= ( 庐( x ) 砂( z ) ) n 1 1 6 一 东北大学硕士学位论文 第一章前言 这样点积就不用明确的通过映射来获得。这样主成分分析可以在特征空间中隐含 实现。假设在特征空间f 中的数据是中心化的，即 o ( 吒) = 0 ( 1 2 ) 协方差的形式为 c：lqb7中(1-3) f o = ( 声( 五) ，妒( 而) ( 1 4 ) 需要获得协方差矩阵的特征值和特征向量丑o ，和特征向量v e f 0 。 舢= c v ( 1 5 ) 因为所有的五0 的对应的特征向量v 在 妒( ) ，( 玉) ) 所有生成的空间中，可以考 虑等价问题： a 中v = o c v ( 1 6 ) v 可以用一个，维的向量a 来表示，即v = 0 1 口，代入上式和( 1 - 3 ) 式合并，并定义 k = 中得到1 i k c t = k 2 口，这个方程可以用解( 1 7 ) 特征值问题来实现： l a a = k a ( 1 7 ) 核矩阵的规模与样本数目成平方关系。所以当样本数目很大的时候是是不可能直接 求解奇异值问题的。k i m 提出了k e r n e lh e b b i a n a l g o r i t h m 算法解决这个问题2 ”。 主成分分析技术作为一种特征抽取方法在应用到数据处理的许多方面，比如去除噪 声、模式识别、回归估计、图像索引等吼而在这些应用中，如果抽取非线性特征，核 主成分分析方法提供了一种代价较小，而收益很大的新的工具。 1 3 本文的主要研究内容 文本的特征表示是影响分类系统性能的至关重要的因素。本文考虑采用因子分析的 方法抽取概念作为特征，分别研究了l s i 和k p c a 的方法用于抽取特征和特征降维， 解决文本分类中特征数目过于巨大的问题。l s i 是一种性能很好的特征抽取方法，但是 它是一种线性映射，难以得到词与词之间的非线性关系；而k p c a 是一种非线性的特 征抽取方法，能够利用非线性核实现抽取非线性特征的目的。文中主要研究这两种特征 抽取方法分别与k n n 分类器结合的文本分类模型k n n l s i 和k n n k p c a 。 7 一 东北大学硕士学位论文第一章前言 本文的安排如下，第二章简单介绍相关的知识，如文本分类，语料，权重计算方案， 分类器，评测方法等；第三章介绍潜在语义索引的一些知识和相关的技术；第四章介绍 核主成分分析，第五章是潜在语义索引和常用几种特征选取方法的比较分析；第六章是 基于核主成分分析的k n n 分类模型，核主成分分析用来做特征抽取的结果，并与潜在 语义索引的方法进行了比较。第七章是结束语。 一8 东北大学硕士学位论文 第二章文本分类 第二章文本分类 帚一早义今刀矢 本章主要介绍一些文本分类相关的基础知识，包括文本分类的定义、文本分类的过 程和应用、实验所用到的数据集、权重计算方法、以及分类器等，另外还介绍了分类结 果的评价方法。 2 1 文本分类的定义 文本分类可以看作是是对于每一个数据对 d xc 赋予一个布尔值，其中 d 为文本集合，c 为预定义的一个类别集合c = c 。，c ：，c l c l ) 。如果对 赋值为 真，表示判别文本d ，属于类别c 。，而赋值为假，表示判别文本d s 不属于类别q 。文本 分类的任务就是通过分类器咖d x c j r ，) 对一个未知目标函数石的做最优估计，其 中方：d xc - - t ，f ) ，描述的是理想的分类函数。 文本分类按照应用需求的不同可以分为单标签( s i n g l e l a b e l ) 年l l 多标签( m u l t i l a b e l ) 分类【”。每一篇文本只能用一个类别标签进行标记的分类方法称为单标签的分类；如果 一片文本可以用多个标签进行标记，则称之为多标签的分类。而从理论上说，单标签分 类比多标签分类更一般化，能够完成单标签分类任务的算法，也可以完成多标签分类任 务。本文中提到的分类是单标签分类，对于每一个测试文本仅输出一个类别标签。 根据对一个分类器的使用方式不同，文本分类分为面向文本分类 d p c ( d o c u m e n t p i v o t e dc a t e g o r i z a t i o n ) 和面向类别分类c p c ( c a t e g o r y - p i v o t e d c a t e g o r i z a t i o n ， ) 两种。给定一篇文本，找到它所有的正确的类别标签就是面向文本分 类；同样，给定一个类别，找到所有属于这个类别的文本就是面向类别分类。这两种方 法只是在实际应用上有区别。d p c 适用于文本在很长一个时间段内都是可用的，比如 电子邮件的过滤。c p c 适合于两种情况：( 1 ) 当很多的文本已经采用类别集合 c = c 。，c ：，c ) 的类别标签分类之后，而要把一个新的类别标签c 。加入到现有的类别 集合c 中( 2 ) 所有的文本必须需要重新测试是否属于类别c 。但是d p c 的方式要 比c p c 的方式更常用。本文也是采用这种d p c 的方式。 根据文本分类的方法的自动化程度，文本分类又分为等级分类( r a n k i n gc l a s s i f i c a t i o n ) 9 东北大学硕士学位论文 第二章文本分类 和硬分类( h a r dc l a s s i f i c a t i o n ) ”，对于一片文本d ，系统按照它与c = e lc 2 ，。) 的各 类别的适合程度( a p p r o p r i a t e n e s s ) ，对各类别进行排序，而不做出属于某个类别的硬性的 决策。这种排序之后的列表对于