（计算机应用技术专业论文）中文文本分类的研究与应用.pdf

摘要 摘要 随着信息技术尤其是因特网相关技术的发展与成熟，人们可获得的信息越 来越多。面对海量信息，一方面是人们对快速、准确且全面获取信息的渴望， 另一方面却是信息的杂乱无序。而文本分类作为处理和组织大量文本数据的关 键技术，可在较大程度上解决信息杂乱问题，对于信息的高效管理和有效利用 都具有极其现实的意义，并已成为数据挖掘领域中一个重要的研究方向。本文 在分析和总结文本分类中文本表示模型、文本预处理、特征选择、特征加权、 分类方法和分类性能评价的基础上，对特征选择、特征加权进行了深入研究。 本文的主要研究工作如下： ( 1 ) 针对文本分类中的高维特征空问和冗余特征问题，提出了一种基于类别 分布的特征选择，并与e c b f 算法相结合，给出了一种二次特征选择方法。其 中，基于类别分布的特征选择方法可以较好的处理高维空问问题，并且对特征 集进行初步筛选，e c b f 算法能够合理的衡量特征之问的冗余程度，用来处理特 征冗余问题。通过该二次特征选择方法不仅可以为文本分类选择合适的特征， 而且还可以减少大量的冗余特征，从而提高文本分类器的性能。 但) 针对文本分类中的特征加权问题，本文首先详细分析了最经典也是常用 的估算特征权重的t f i d f 方法，发现t f i d f 只是能较好的表达一个特征词对 一个文档的区分能力，但是没有引入特征词区分一个类和其他类的能力的表示。 文本在研究朴素贝叶斯分类模型和t f i d f 特点后，提出一种改进的特征加权估 算方法。该估算方法有效的对各个特征词的类别区分能力给出合适的权重。 本文从文本分类的特征选择和特征加权两个方面，分别提出改进的方法， 在不同程度上提高了文本分类的性能。 关键词：文本分类，特征选择，特征加权，二次特征选择，t f i d f ，朴素贝叶斯 a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n ta n dm a t u r i t yo fi n f o r m a t i o nt e c h n o l o g y , e s p e c i a l l yt h e i n t e m e t - r e l a t e dt e c h n o l o g y , p e o p l ec a no b t a i nm o r ea n dm o r ei n f o r m a t i o n f a c e d w i t had e l u g eo fi n f o r m a t i o n ，o nt h eo n el l a n d ，p e o p l eh a v ead e s i r ef o rf a s t ，a c c u r a t e a n dc o m p r e h e n s i v ea c c e s st oi n f o r m a t i o n o nt h eo t h e rh a n d ，i n f o r m a t i o ns t a y si na n u n e x p e c t e dw a y sa n dt h u sl o o k sd i s o r d e r l y a sak e yt e c h n o l o g yo fp r o c e s s i n ga n d o r g a n i z i n gv a s tt e x td a t a , t e x tc l a s s i f i c a t i o nc a ns o l v et h ei n f o r m a t i o nd i s o r d e r p r o b l e mt oag r e a te x t e n t i th a sv e r yr e a l i s t i cs i g n i f i c a n c ef o re f f i c i e n tm a n a g e m e n t a n de f f e c t i v eu t i l i z a t i o no fi n f o r m a t i o n s o m ep r o b l e m si nt e x tc l a s s i f i c a t i o na r e r e s e a r c h e di nt h i st h e s i s w i t hi m p r o v e m e n to ft e x tc l a s s i f i c a t i o np e r f o r m a n c ea st h e m a i nl i n e ，t h i st h e s i sd e e p l ya n a l y s e st h ek e yt e c h n o l o g i e so ft e x tc l a s s i f i c a t i o n ， w h i c hi n c l u d et e x tr e p r e s e n t a t i o nm o d e l ，t e x tp r e p r o c e s s i n g ，f e a t u r es e l e c t i o n ，f e a t u r e w e i g h t i n g ，c l a s s i f i c a t i o nm e t h o d ，c l a s s i f i c a t i o np e r f o r m a n c ee v a l u a t i o na n ds oo n f u r t h e r m o r e ，t h i st h e s i sr e s p e c t i v e l yp r o p o s e sn o v e lm e t h o d sf o rf e a t u r es e l e c t i o na n d f e a t u r ew e i g h t i n g t h em a i nr e s e a r c hc o n t e n t so ft h i st h e s i sa r ea sf o l l o w s ： ( 1 ) f o rt h ep r o b l e m so fh i g hd i m e n s i o nf e a t u r es p a c ea n df e a t u r er e d u n d a n c yi n t e x tc l a s s i f i c a t i o n ，t h i st h e s i sp r o p o s e st h et w o s t e pf e a t u r es e l e c t i o nm e t h o dw h i c h c o m b i n e dt h ee c b fa l g o r i t h mw i t haf e a t u r es e l e c t i o nm e t h o db a s e do nf e a t u r e d i s t r i b u t i o n ，w h i c hi sp r o p o s e db yt h i st h e s i s t h e r e i n t o ，t h ef e a t u r es e l e c t i o nm e t h o d b a s e do nf e a t u r ed i s t r i b u t i o ni su s e dt ot r e a tw i t ht h ep r o b l e mo fh i g hd i m e n s i o n f e a t u r es p a c e ，w h i c hc a ns i f tt h r o u g hf e a t u r e sf r o mf e a t u r es e ta to n et i m e t h ee c b f a l g o r i t h mc a nr e a s o n a b l ym e a s u r ed e g r e eo fr e d u n d a n c ya m o n gf e a t u r e s i ti su s e dt o t r e a t 埘t ht h ep r o b l e mo ff e a t u r er e d u n d a n c y t h e r e f o r e ，t h e p r o p o s e dt w o - s t e p f e a t u r es e l e c t i o nm e t h o dc a nn o to n l ys e l e c ts u i t a b l ef e a t u r e sf o rt e x tc l a s s i f i c a t i o n ， b u ta l s or e d u c ep l e n t yo fr e d u n d a n tf e a t u r e s t h ep e r f o r m a n c eo ft e x tc l a s s i f i e ri s i m p r o v e dc o n s e q u e n t l y ( 2 ) f o rt h ep r o b l e mo ff e a t u r ew e i g h t i n gi nt e x tc l a s s i f i c a t i o n , t h et h e s i sf i r s t l y a n a l y s e st h et f - i d fm e t h o dw h i c hi st h em o s tc l a s s i c a la n dc o m m o nf e a t u r ew e i g h t i i e s t i m a t i o nm e t h o di nd e t a i l t h i sm e t h o do n l yc o n s i d e rt h ec a p a b i l i t yt od i s t i n c ta t e x t f b ma n o m e rt e x to ff e a t u r e ，a n dd on o ti n t r o d u c e di n t ot h ec a p a b i l i t yt od i s t i n c ta c l a s sf 如ma n o t h e rc l a s so ff e a t u r e t h r o u g ha n a l y s e st h ec h a r a c t e ro ft h en a i v e b a y e sc l a s s i f i c a t i o na n dt h et f i d fm e t h o d ，t h i st h e s i sp r o p o s e sa a d v a n c e df e a t u r e w e i g h te s t i m a t i o nm e t h o d t h i sm e t h o dc a ng i v e as u i t a b l ew e i g h tt of e a t u r e a c c o r d i n gt ot h ec l a s s - d i s t i n c tc a p a b i l i t y t h i st h e s i sr e s p e c t i v e l yp r o p o s e sam e t h o df r o mt w od i f f e r e n ta s p e c t s ，n a m e l y , f e a n l r es e l e c t i o na n df e a t u r ew e i g h t i n g a n dt h e s em e t h o d si m p r o v ep e r f o r m a n c eo f t e x tc l a s s i f i c a t i o ni nd i f f e r e n td e g f e e k e yw o r d s ：t e x tc l a s s i f i c a t i o n , f e a t u r es e l e c t i o n ，f e a t u r ew e i g h t i n g ，t w o 。s t e pf e a t u r e s e l e c t i o n , t f - i d f , n a i v eb a y e s i i i 学位论文独创性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得直昌太堂或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名( 手写) ：讹序! i i i - 字i i ! i i ：。l 。年，月7 日 学位论文版权使用授权书 本学位论文作者完全了解直昌太堂有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权直昌太堂可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编本学位论文。同时授权中国科学技术信息研究 所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：呻历力导师签名：白 孥 签字日期：剀b 年r 月7 日 签字日期：及。1 口年 f 月7 日 第l 章绪论 1 1 研究背景 第1 章绪论 分类是人们认识自然的一种重要手段。在计算机出现之后，人们就开始借 助这一利器研究数据的自动分类问题。自上个世纪8 0 年代以来，信息化的浪潮 席卷全球，信息技术迅速地渗透到社会经济的各个领域。信息的来源也扩展成 多方面的，比如报纸、电视、广播等等。近几年来，随着i n t e m e t 的普及和网络 技术的不断完善，i n t e m e t 已经成为了全球最庞大最丰富的信息资源库。而且由 于i n t e m e t 的开放性，各类信息都能在第一时问发布到i n t e m e t 上。然而，i n t e m e t 的这种开放性也导致了i n t e m e t 上信息的杂乱性和冗余性。由此可见，人类进入 信息时代后，不仅信息的数量急剧增长，而且信息的形式更加复杂。此外，信 息的全球化要求处理与传递信息的速度不断加快。然而，在信息保持快速增长 的同时，人们对信息的吸收能力却没有随之增强。当我们在浩瀚的信息海洋里 畅游时，经常会发现找不到所需要的信息。因此，如何有效地组织和管理这些 海量信息，并且能够从中快速、准确、全面地找到所需要的信息是当前信息科 学与技术领域面临的一大挑战。 尽管信息的形式多种多样，但文本信息依然占有主要地位。这是因为文本 是信息的主要载体，而其它形式的信息都可以用文本进行标注。因此对于文本 信息的处理至关重要。分类是人类认识世界、区分客观事物的一种思维活动， 也是根据事物的“共性”与“特性”聚集相同事物、区分不同事物的手段。人 们既可以通过分类认识事物和区分事物，也可通过分类使纷繁复杂的事物系统 化，从而为进一步探讨事物本质和相互之间的关系以及开展后续科学研究打下 坚实的基础。从这个角度来看，文本自动分类技术对于这些庞大而又杂乱的信 息处理的意义变得更加重要。因此，自动分类技术随着时代的需求而蓬勃发展 了起来。作为一种有效的信息处理方法，自动分类技术将各类信息按照一定的 分类体系进行分类整理，从而大大提高了用户搜集情报的效率。 文本自动分类【l 】最初是应信，淞( i n f o r m a t i o nr e t r i e v a l ，简称i r ) 系统的要 求出现的。从计算的观点看，如果分类原则是事先通过示例告诉计算机的，那 第l 章绪论 么计算机在示例基础上形成分类机制的过程就称为有监督的分类，称为自动分 类问题。信息检索系统必须操纵大量的数据，其文本信息库可能是非常庞大的， 同时，用来表示文本的词汇数量又是成千上万的。在这种情况下，如能给文本 集提供良好的组织和结构，就能大大的简化文本的存取和操作。文本自动分类 系统的目的就是对文本集进行有序组织，把相似的、相关的文本组织在一起。 为信息检索提供了更高效的搜索策略和更准确的查询结果。其中，高效来自于 用户可以首先确定查询的可能类别，以减小进一步匹配的文本数量。有效在于 相似的文本很可能与相同的查询有关。 自动分类技术是在手工分类技术的基础上发展起来的。传统的信息手工分 类技术已经相当成熟，但却不适于对i n t e m e t 上时刻更新的信息进行处理。因此 文本分类技术出现变革，如用k n o w l e d g ee n g i n e e r i n g 理论指导文本分类。直到 上世纪9 0 年代，“机器学习 【2 j 方法成为文本分类的主流技术，文本分类过程一 般分为训练和分类两个阶段。首先从一个己分类的训练文本集合，由一个诱导 式的过程通过学习感兴趣的类别特征，构造一个文本自动分类器。然后用这个 构造的文本自动分类器来进行文本分类。无疑，这种方法使得文本分类技术在 效率方面得到很大的提升。 1 2 研究意义 文本分类作为一项实用价值很高的关键技术，是管理文本信息的有效方法。 近年来，文本分类技术在信息过滤、信息组织和管理、语义辨析和数字图书馆 等领域内得到了广泛的应用和发展。 ( 1 ) 信息过滤 正如1 1 节中讲到的网络上信息的获取是非常得方便，但是获得的信息量越 大，人们对信息的处理就越困难。信息过滤就是对这些信息量进行过滤，保留 相关信息，去除无关信息。如果从文本形式来讲，就是保留“相关文本 ，去除 “无关文本 。信息过滤有两个显著的特点，那就是个性化和主动化。个性化即 从不同的角度采用不同的信息过滤，提供不同的信息内容。主动化是指系统自 动按照要求提供相应的信息过滤。 ( 2 ) 信息组织和管理 通过对信息的组织和管理，能使得人们更好的使用、了解信息的内容。不 2 第l 章绪论 同类型的信息需要不同类型的，甚至多种类型的数据模型来存储表示。采用文 本分类技术辅助信息资源的组织和管理，不仅能让人们从手工分类这种低效率 的劳动中解脱出来，而上l 提高了管理的效率和管理能力。 ( 3 ) 语义辨析 语义辨析是确定多义词在不同的语言环境下的含义。显然语义辨析涉及到 自然语言处理和机器翻译。对于中文文本分类来说，语义辨析是自然语言理解 与分类中很重要的一个环节。 ( 4 ) 数字图书馆 数字图书馆是在数字技术基础上发展起来的，它将现实图书馆中所有的图 书资料信息都采用数字化存储，读者不需要亲自来到图书馆查阅资料，在千里 之外就可以通过网络访问到图书馆的数据库，得到与现实图书馆同样的服务， 让人们更方便的得到各种信息资料。 在数字图书馆建设中，重复文档和近似文档会让数据库包含大量冗余。因 此必须对这两类文档数据进行控制约简。其中文本分类中可以比较文本的相似 度，通过相似度来确认是否是冗余数据，这样大大减少了数字图书馆的冗余文 档，也提高了数字图书馆的管理效率和利用率。 1 3 文本分类方法 基于机器学习文本分类的基础技术由文本的表示( r e p r e s e n t a t i o n ) 、分类方法 及效果( e f f e c t i v e n e s s ) 评估三部分组成。主要内容包括b4 j ： ( 一) 文本关于项( t e r m ) 或特征的表示模型及特征选择( s e l e c t i o n ) 与特征提取 ( e x t r a c t i o n ) 两种特征约简； ( 二) 分类器的归纳构造( i n d u c t i v ec o n s t r u c t i o n ) 或模型的挖掘学习过程； ( 三) 分类效果评估指标，如正确率( p r e c i s i o n ) 、召回率( r e c a l l ) 、均衡点( b e p ) 、 f b ( 常用f1 ) 和精度( a c c u r a c y ) 等。 文本分类的关键在于第二步，如何构造分类器模型，将未知类的文本通过 文本分类函数计算与给定的类别进行匹配。目前有许多种分类器的构造方法， 如统计方法、机器学习方法、神经网络方法等。而主流的构造方法是基于关键 词匹配的机器学习算法，主要有n a i v eb a y e s 算法【5 。、k n n ( k 近邻算法) 【6 】、s v m ( 支 持向量机) 【l 】等。具体算法将在第2 章进行介绍。 3 第l 章绪论 1 4 国内外研究现状 1 4 1 国外研究现状 国外文本分类的研究可以追溯到上世纪五十年代末。h p l u h n 首先提出将词 频统计思想用于文本分类，在该领域进行了开创性研究1 7 j 。1 9 6 0 年，m a r o n 等人 提出关键词自动分类技术，并在j o u r n a lo fa s m 上发表了关于自动分类的论文 o nr e l e v a n c e ，p r o b a b i l i s t i ci n d e x i n ga n di n f o r m a t i o nr e t d e v a l ) ) 【引。随后，许多学 者在这一领域里，进行了卓有成效的研究工作。8 0 年代之前，最有效的文本分 类系统是专家人工构建的基于知识工程技术的分类系统，其中典型代表就是卡 内基集团为路透社开发的c o n s t r u e 系统1 9 j 。该系统在r e u t e r s 的部分语料库上效果 非常好，但在其它应用领域会耗费大量的人力物力，且适应性差。 到了9 0 年代，基于机器学习( m a c h i n el e a r n i n g ) 的分类技术逐渐取代基于知 识工程的分类技术而成为主流技术。这种技术是通过归纳文本集的特征自动创 建分类器。显然这种技术比基于知识工程的分类技术要节省了大量的人力资源， 且加快了分类系统的建立速度。在几年的发展中，研究者提出了多种分类模型 和算法，如n a i v eb a y e s ，k 近邻( 1 m 町，决策树，支持向量机( s v m ) ，神经网络 等等，并将这些技术引入到实际应用阶段。1 9 9 6 年，a t & t 实验室的d a v i dd l e w i s 等人将分类技术涉足到电子邮件领域。1 9 9 7 年，德国d o r t m u n d 大学计算机系的 t o s r e t n oj a c h i m s 等人研究了基于向量空问模型的自动分类系统。1 9 9 8 年，美国 c a m e g i em e l l o n 大学计算机系的y i m i n gy a n g 等人将决策树等聚类算法应用于在 线自动分类。2 0 0 5 年，g u p t a 等人将粗糙集方法用于文本分类的特征选择1 1 。 h i r s c h 等人使用遗传算法构建简洁的文本分类规则【1 1 1 。t r a p p e y 等人利用神经网 络分类方法提出了一种新的知识管理技术，并且利用该技术对专利文本进行了 分类【1 2 1 。 国外还有许多的文本分类研究机构，其中著名的研究机构有加拿大多伦多 大学电子与计算机工程系、德国波恩大学计算机系和微软亚洲研究院的自然语 言计算组等。另外，国外关于文本分类的相关文献非常丰富，通常见于各种国 际会议以及相关的期刊和杂志中。另外还有困际杂志出版过文本分类方面的专 辑【1 3 1 4 1 。 4 第1 章绪论 1 4 2 国内研究现状 国内的义本分类研究起步较晚，始于上世纪8 0 年代初期。1 9 8 1 年，侯汉清 对计算机在文献分类工作中的应用进行了探讨，并介绍了国外在计算机管理分 类表、计算机分类检索、计算机自动分类、计算机编制分类表等方面的概况i l 引。 此后，国内的研究者在英文文本分类研究的基础上，结合中文文本的特定知识， 形成中文文本自动分类研究体系。 近几年来，随着我国对文本分类研究的不断深入，研究成果犹如雨后春笋 般不断涌现。2 0 0 5 年，李荣陆等人使用最大熵模型进行了中文文本分类；通过 模拟实验比较和分析了不同的中文文本特征生成方法、不同的特征数目以及在 使用平滑技术的情况下，基于最大熵模型的分类器的分类性能【1 6 】。王建会等人 提出了互依赖和等效半径的概念，并将两者相结合，提出一种基于互依赖和等 效半径、易更新的s e c t i l e 分类算法；s e c t i l e 算法计算复杂度较低，而且扩 展性能较好，适用于大规模场合【l n 。2 0 0 6 年，尚文倩等人介绍了另一种新的基 于基尼指数的文本特征选择算法；使用基尼指数原理进行了文本特征选择的研 究，构造了基于基尼指数的适合于文本分类特征选择的特征选择评估函数【l 引。 苏金树等人给出了基于机器学习的文本分类技术所面临的互联网内容信息处理 等复杂应用的挑战，从模型、算法和评测等方面对其研究进展进行综述评论； 认为非线性、数据集偏斜、标注瓶颈、多层分类、算法的扩展性及w e b 页分类等 问题是目前文本分类研究的关键问题，并讨论了对于这些问题可能采取的方法， 最后，对研究的方向进行了展望【4 j 。 文本分类作为信息管理的一项核心技术，在吸引越来越多国内研究者的同 时，也得到了国家各级、各类研究部门的高度重视，获得基金支持的相关论文 越来越多，从而加速了国内文本分类技术的发展。目前，我国已研制出一批计 算机辅助分类系统和自动分类系统。国际中文计算机学会、中国中文信息学会、 国内的计算机核心期刊和国内清华大学、北京大学、上海交通大学、哈工大、 中国科学院等科研院所在文本分类领域进行了大量的研究。目前，我困在中文 文本自动分类领域已经取得了令人瞩目的研究成果，其中有北京大学的天网、 复旦大学的文本分类，计算所的基于聚类粒度原理的智多星中文文本分类器等。 其中一些已经被成功推广和应用，典型的代表性系统有北大天网、百度搜索引 擎等。 5 第1 章绪论 1 5 本文的组织结构 本文主要研究文本分类的基础环节降维和特征加权。具体内容如下： 第一章绪论 介绍文本分类系统的概念、背景和现状，并阐述了本文的结构。 第二章常用文本分类算法研究 介绍分析文本分类系统中使用到的文本数学表示方法以及各种文本分 类算法。 第三章特征约简方法 介绍各种特征约简技术，并介绍一种二次特征选择方法。 第四章特征权重估算方法 介绍特征权重技术方法，并给出本文的权重计算方法。 第五章向量优化技术在朴素贝叶斯文本分类上的应用 将第三章和第四章的向量优化技术应用在朴素贝叶斯分类上，并给出了 实验数据并对此进行了分析； 第六章总结和展渠 对本文的工作进行总结，并提出了需要完善的地方和进一步的工作展 望。 6 第2 章常用文本分类算法研究 第2 章常用文本分类算法研究 文本分类算法是设计实现分类器的理论基础，因此本章专门介绍文本分类 系统的体系结构，文本的表示方法以及几种典型的分类算法，讨论它们的分类 机制，并对它们进行性能对比和分析，为后面的研究奠定理论皋础。 2 1 文本的数学表示模型 自然语言形式的文本的结构非常复杂，如何将这样的文本表示成计算机可 以识别的格式是文本分类的一个基本问题，具有非常重要的意义。 近年来，将文本用“词袋 表示( b a go fw o r d s ) ，并通过一系列的特征处理 和统计学算法对文本类别信息进行估计预测，已经成为文本分类的标准模式 4 1 。 在信息检索中，“词袋”假定对于一个文本，忽略其词序和语法，句法，将其仅 仅看作是一个词集合，或者说是词的一个组合，文本中每个词的出现都是独立 的，不依赖于其他词是否出现，或者说当这篇文章的作者在任意一个位置选择 一个词汇都不受前面句子的影响而独立选择的。 一般的，文本的数学表示模型有四种，分别是向量空间表示模型( v s m ) 、布 尔逻辑模型、概率推理模型、潜在语义索引模型。本节将分别介绍这几种模型。 2 1 1 布尔逻辑模型 布尔逻辑模型是最简单的文本表示模型，它是一种基于集合理论和布尔代 数的简单模型。标准布尔逻辑模型为二元逻辑，并假定特征词在文档中只有两 种情况：出现和不出现。因此，特征词都是由二值( o ，1 ) 数据组成，由连接词“与 、 “或 、“非 连接起来的多个特征词所组成，所以文本表示的实质是一个常规 的布尔表达式。 布尔逻辑模型的主要优点在于形式简洁、结构简单。 2 1 2 向量空间模型 7 第2 章常用文本分类算法研究 向量空间模型( v e c t o rs p a c em o d e l ，或称词组向量模型) 是一个应用于信息过 滤，信息撷取，索引以及评估相关性的代数模型。它是由g s a l t o n 等人最早提出 的，s m a r t 是首个使用这个模型的信息检索系纠1 9 , 2 0 】。 关于v s m 的有关研究主要集中在两个方面：以什么单位为特征项和特征项 的权值问题。“词是最小的能够独立活动的有意义的语言成分。【2 1 1 ，因此大部 分工作都是以词或者n g r a m 作为特征项。而在最初的向量空问模型中，所有的特 征项都用o 和l 来表示，如果一个词在文本中出现过，则它就被记为l ，否则被记 为0 t 2 2 j 。显而易见，这里有个极为不合理的情况，即一个词在文本中出现一次和 另一个词在文本中出现十次都被记为l 。也就是说，这样就不能表示出每个词在 文本中的重要程度。因此，( o ，1 ) 值的记录方式已被摹丁统计的词频所代替。 向量空间模型的最基本思想就是用“词袋 来表示文本。也就是将每一个 不同的词都看成特征空间中独立的一维，将每一个文本看成是特征空问中的一 个向量。向量空间模型有m 个无序特征项w i ，词根词短语其他每个文档d i 都可 以用特征项向量来表示( w l i ，w 2 j ，w m j ) 。 d w l i w 3 。 图2 1 向量空间模型 文本分类时，对若干已有类标签的训练集进行必要的数据处理，如分词， 降维，特征加权，并通过学习形成一个文本分类函数，形成类别的中心向量。 当有文本需要分类时，对它做必要的处理后，用向量空问模型表示出该文本， 然后通过计算它和类别中心向量的相似度，来判断该文本的类别信息。 相似度的计算形式有几种方梨2 3 1 ，如通过内积计算、余弦计算( c o s i n e g t 算) 等形式求相似度。其中，直接用内积计算相似度的形式，计算强度低，但是误 差较大。内积计算公式如( 2 1 ) 式所示： l l n n e r p r o d u c t = 乏：置z ( 2 - 1 ) 8 第2 章常用文本分类算法研究 而余弦形式的好处是，正好是一个介于o 到l 的数，如果向量一致就是1 ，如 果正交就是0 ，符合相似度百分比的特性，余弦的计算方法为，向量内积各个向 量的模的乘积。余弦计算公式如( 2 2 ) 式所示： ， 薯咒 c o s i n e c o e f f i c i e n t = 1 上等一 ( 2 2 ) 、# 订 y ，- i i = l 综上所述，一个文本要表示成向量形式，必须经过分词，特征提取，权蓬 计算等步骤，在本文中，文本表示采用的是向量空间模型。 2 1 3 概率推理模型 概率推理模型的基本思想是：给定一个检索词，相对于该检索词存在一个 包含所有相关文档的集合，通过给定一个检索词和集合中的文档概率模型来估 计检索词与文档的相关概率。它包括了检索词间的依赖关系以及主要参数，如 检索词权重计算，查询与文档相似性计算，由模型自身决定。 概率推理模型假设这种概率只决定于检索词和文档。更进一步说，该模型 假定存在一个所有文档的集合，即相对于检索词的结果文档子集，这种理想的 集合用r 表示，集合中的文档是被预料与检索词相关的。 在概率模型中检索词的权重都是二元的，耳p w i j e o ，1 ) ，w i ，q 0 ，1 ) 。q 是检 索词集合的子集。r 表示已知的相关文档集合( 初始的猜测集合) ，r 是r 的补集( 非 相关文档的集合) 。p ( 足i 嘭) 表示文档d j 与q 的相关概率，尸( 豆l 嘭) 表示文档d j 与 q 的不相关概率。文档d 对于q 的相关度值s 砌( d ，q ) 定义为： j 砌( 咖) = 粼 ( 2 - 3 ) 除了p ( r la j ) 和尸( 豆i 嘭) 两个概率以外，还有两个费用系数a l 和a 2 ，其中a l 表示由于检索不相关的文档造成的损失，a 2 表示错过检索相关文档所造成的损 失。 c 2 p ( ri 哆) q 尸( ri 乃) ( 2 - 4 ) 检索相关函数可定义为： 9 第2 章常用文本分类算法研究 g = 揣一号( 2 - 5 ) 检索结果为相关函数g 值大于o 的文档记录。g 值无法计算出来，文档的相关 特性与其中包含的检索词相关。 2 1 4 潜在语义索引模型 潜在语义索弓i ( l s i ) 最早是一种用于信息检索中的自动索引技术，是一种将 文本信息组织成语义空间结构的方法，它认为在文本中的词与词之间存在着某 种联系，即潜在的语义结构，并通过分析词与它所处上下文环境之间的关联关 系抽取出隐藏在文本背后的这种更为高层的语义结构，从而能在语义层面上对 文本进行检索，进而大幅度提高信息检索的性能阱l 。 l s i 是在向量空间的基础上进行词条关系处理的，并基于这样一种断言，即 大量的文档集合中存在隐含的关于词语使用的语义结构，这种语义由于部分的 被文档中词的语义和形式上的多样性所掩盖而不明显。因此，l s i 试图绕过自然 语言理解，运用统计运算的方法来发现词语使用的潜在的语义结构，获得文档 潜在的语义概念空间结构，从而利用概念索引取代关键词索引。 在l s i 模型中，一个文档库可以表示为一个m x n 的词文档大矩阵a 。这里，1 1 表示文档库中的文档数，m 表示文档库中包含的所有不同的词的个数。也就是说， 每一个不同的词对应于矩阵a 的一行，每一个文档对应于矩阵a 的一列。a 表示 为： 么= 吩 ，l i m ，l 刀 潜在语义索引模型利用特征项与文档对象之间的内在关系形成信息的语义 结构。这种语义结构通常是通过对特征项文档矩阵使用奇异值分解 ( s i n g u l a r - v a l u ed e c o m p o s i t i o n ，s v d ) 方法来实现的，把小的奇异值去掉，从而 形成新的语义空间。 2 2 常用文本分类算法研究 在众多的分类算法中，我们讨论以下几种分类算法：中心向量算法、k 近邻、 决策树、神经网络、支持向量机、遗传算法、粗糙集方法、朴素贝叶斯，其中 1 0 第2 章常用文本分类算法研究 熏点介绍本文中用到的朴素贝叶斯模型。 2 2 1 中心向量算法 中心向量算法也n r o c c h i o 算法，其基本思想是在训练集中为每一类确定一 个中心点( 代表元) ，计算待分类的文档与各类代表元问的距离，并以此作为判定 是否属于该类的判据。构造方法如下：给定一个类，训练集中所有属于这个类 的文档对应向量的分量用正数表示，所有不属于这个类的文档对应向量的分量 用负数表示，然后把所有的向量加起来，得到的和向量就是这个类的原型向量。 通过计算两个向量夹角的余弦来确定这两个向量之问的相似度，并通过计算训 练集中所有文档和原型向量的相似度，将从所有相似度中挑选某个相似度作为 判断是否为该类的界限。给定一篇文档，通过比对该文档向量和原型向量的相 似度来确定该文档的类别归属，如果相似度高于界限，则属于该类，否则不属 于该类。 r o c c h i o 算法的突出优点是容易实现，计算( 训练和分类) 特别简单，但效果 比较差，因此实用的分类系统很少采用这种算法，而仅仅是用该方法作为衡量 分类系统性能的基准。 2 2 2k 近邻算法 近邻法( n e a r e s tn e i g h b o r ，简称n n ) 是在模式识别中广泛使用的分类方法， 是模式识别非参数法中最重要的方法之一。k 近邻法( kn e a r e s tn e i g h b o r ，k - n n ) 是最近邻法的一个推广。当k 取l 时就是最近邻法。n n 强调最近点的重要性，而 k 小n 则从整体考虑，是一种更为普遍的方法，理论认为它的错误率比n n 低1 2 5 j 。 最近邻分类法是基于类比学习，即通过给定的检验样本与和它相似的训练 样本进行比较来学习。训练样本用n 个特征描述。每个样本代表n 维空间的一个 点。这样，所有的训练样本都存放在n 维模式空问中。当给定一个未知样本时， k 小n 方法搜索该模式空问，找出最接近未知样本的k 个训练样本。这k 个训练样 本就是未知样本的k 个“最近邻”，通过该得到未知样本的属性类别【2 6 j 。 由于k n n 方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来 确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，k - n n 方 法较其他方法更为适合。 第2 章常用文本分类算法研究 k - n n 算法使用基于距离的比较，本质上赋予每个属性相对的权重。因此， 当数据存在噪声或不相关属性时，它们的准确率可能会受到影响。然而，这种 方法已经改进，结合属性的权重和噪声数据样本的剪枝。距离度量的选择可能 是至关重要的。 k - n n 算法用于分类时的速度是非常慢的。如果d 是具有v 个样本的训练数据 库，而k = l ，则对一个给定的检验样本分类需要o ( v ) 次比较。通过将存储的样本 预先安排在搜索树中，比较次数可以降低到0 ( 1 0 9 v ) 。并行实现可以将运行时间 降低为常数，即o ( 1 ) ，独立于v 。加快分类速度的其他技术包括使用部分距离计 算和编辑存储的样本【2 6 1 。 2 2 3 决策树算法 决策树归纳分类是从类标记的训练元组学习决策树【2 6 j 。决策树( d e c i s i o n t r e e ) 是一种类似于流程图的树结构；其中，每个内部节点表示在一个属性上的 测试，每个分枝代表一个测试输出，而每个树叶节点存放一个类标号。树的最 顶层节点是根节点。 在构造决策树时，使用属性选择度量来选择样本最好地划分成不同的类的 属性。另外，在建立决策树时，许多分枝可能反映的是训练数据中的噪声或离 群点。树剪枝试图识别并剪去这种分枝，以提高对未知数据分类的准确率。 树的生成过程分两个步骤：采用贪心( 即非回溯的) 方法，从上而下、分而治 之的归纳建树过程；去除噪音和异常数据的剪枝过程。具体过程是首先查看所 有的训练样本是否都属于同一个类别，如果不是，选择一个特征，将训练集分 成两个部分，每一部分要么包含该特征，要么不包含该特征。然后在每个部分 中重复这个步骤，直到每棵树的叶子节点的所有训练文档都属于同一个类别为 止。然后通过树剪枝来减少噪声数据1 2 6 j 。 属性选择度量是一种选择分裂准则，将给定的类标签的训练样本的数据划 分d “最好”地分成个体类的启发式方法。如果根据分裂准则的输出将d 划分为 较小的划分，理想地，每个划分是纯的。从概念上讲，“最好的分裂准则是导 致最接近这种情况的划分。属性选择度量提供每个属性描述给定训练样本的秩 评定。最流行的属性选择度量方法有信息增益、增益率等。关于信息增益和熵 的概念会在后面的章节中介绍。 1 2 第2 章常用文本分类算法研究 剪枝方法有两种：先剪枝和后剪枝。先剪枝( p r e p r u n i n g ) 是通过提前停止树 的构造而对树剪枝。后剪枝( p o s t p r u n i n g ) 是对“完全生长”的树剪去子树。决策 树可以很好地抵抗噪声。但它最大的缺点在于不适应大规模的数据集，此种情 况下决策树的构造会变得效率低下【2 6 1 。 著名的决策树算法有j r o s sq u i n l a n 提出的i d 3 算法，以及他后来提出的c 4 5 算法，还有1 9 8 4 年l b r e i m a n 等人提出的c a r 嘶d g e 算法【2 6 j 。 2 2 4 神经网络算法 神经网络领域最早是由心理学家和神经学家开创的，旨在寻求开发和测试 神经的计算模拟。简单的说，神经网络是一组连接的输入输出单元，其中每个 连接都与一个权重相关联，神经网络算法采用感知算法来进行分类，分类知识 被隐性地存储在连接的权鼋值上了，通过迭代来确定权值向型2 6 1 。 在学习阶段，通过调整这些权值，能够预测输入向量的正确类标号。对每 一个输入元组，不断修改聚类中心。为了找到最接近的向量的聚类中心，各个 神经元之间通过竞争来选出一个神经元，修改该神经元所对应的聚类中心，使 之更接近于输入向量。中心权值修改的次数越多，它的类别专属度就越高。 神经网络需要很长的训练时间，对于有足够训练时间的应用更合适。需要 大量的参数，通常主要靠经验确定。神经网络也因其可解释性差而受到批评。 另外，神经网络的优点包括其对噪音数据的高承受能力，以及对未经训练的数 据的模式分类能力，并成功的应用于现实当中。 神经网络主要有前向神经网络、后向神经网络和自组织网络。 2 2 5 支持向量机算法 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是c o r t e s 和v a p n i k 于19 9 5 年首先 提出的1 2 1 7 1 ，这种统计学习方法在解决小样本、非线性及高维模式识别中表现出 许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。 支持向量机方法是建立在统计学习理论的v c 维理论和结构风险最小原理基 础上的。s v m 方法从