（计算机软件与理论专业论文）自动文本分类算法研究.pdf

硕士学位论文 摘要 i n t 啪e t 的飞速发展导致网络上的文档信息急剧增长，如何自动处理这些海量信息成 为目前重要的研究课题。文本分类是对文档信息进行有序组织的方法，它能够为信息检 索提供更高效的搜索策略和让其返回更准确的检索结果。本文研究自动文本分类算法。 本文首先介绍了文本分类的发展概况，对常用的分类算法，比如朴素贝叶斯( n a i v e b a y e s ，简称n b ) 、t f i d f 、k 近邻( kn e a r e s tn e i g i l b o r s ，简称k n n ) 和支持向量机 ( s u p p o r tv e c t o rm a c h i n e ，简称s v m ) 等进行了介绍和分析，为后续章节的研究提供 了理论和实验基础。 平滑技术虽然能够使n b 算法避免零概率问题，但该技术本身存在一些不足之处， 为此本文提出了两种新的策略：n bt f 和n bt s ，可以在不采用平滑技术的情况下消 除n b 算法中的零概率问题。分析和实验表明，与l 印l a c e 和s g t 平滑算法进行比较， 新策略在有效性、适应性等方面具有较好的性能。 本文对调整训练文本权值能否提高单分类器性能的问题进行了研究，采用了较简单 的权值调整策略，提出了两种新算法：k t r a i n l 和k r r a 越，。分析和实验表明，新算法能 够对分类器性能起到一定的提升作用。 本文在研究t f l d f 和k n n 算法的基础上，融入增大错分训练文本权值可以改进分 类器性能的思想，提出了一种改进的t f i d f 算法s t f i d f ，该算法采用k n n 算法 思想改进t f i d f 算法性能。实验验证了s t f i d f 算法在分类性能上优于t f i d f 和k n n 算法。同时，s t f i d f 算法保持了t f i d f 算法的高运行效率，适合大规模的文本分类任 务。 关键词：自动文本分类；零概率问题；平滑技术：调整训练文本权值；结合t f d f 和 k - n n 旦垫茎奎坌鲞竺鎏竺圣 a b s t r a c t w 1 t 1 1m ed e v e l o p m e n to ft l l e i m e m e t ， t h eo n l i n ed o c m e n t sa v a i l a b l ei n c r e a s e c x p o n e n t i a l l yh o wt o d e a l 而t ht h e s e p l e n t i f u l o n l i n ed o c l l i n e n t s a u t o m a t i c a l l yi s a l l i m p o r t a l l tr e s e a r c hd i r e c t i o n t c x tc a t c g o r i z a t i o no 唱a i l i z e sm et e x td o c u i n c n t so n 血en e ti n t o c a t e g o r i e s ，p r o v i d e sm o r ee m c i e n ts e a r c hs m 札e g i e sf o ri f l f o r m a t i o nr e 岫e v a la i l dm a k e si t r e t u mm o r ca c c u r a t er c s u n s t h er c s e a r c ho na u t o m a t e dt e x tc a t e g o r i z a t i o na l g o r i m m si st l l e t o p i co f t h i st h e s i s t h et h e s i sf i r s yi 1 1 廿1 ) d u c e sg e n e r a ld e v e l o p m e n to fa u t o m a t e dt e x tc 砷e g o r i z a t i o n 1 h e n ， s o m ee x p e r i m e n t sa i l da i l a l y s e sa r cm a d et oc o m p a r em ep e r f o m l a n c e so fs o m et y p i c a l c a t e 9 0 r i z a t i o na l g o 珊瑚s ，s u c ha sn a i v eb a y e s ( n b ) ，t f i d f kn e a r e s tn e i g i l b o r s ( k - n n ) a i l ds u p p o r tv e c t o rm a c l l i n e ( s v m ) ，1 a yb a s i ct l l e o r e t i c a l 柚de x p 耐m e n t a ls 即p o n s 矗) rt t ：i c r e s e a r c hi nt l l ef o l l o w i n gc h a p t e r s a l 也o u g hs m o o m i n gc a nm a k en ba l g o r i 讥! l la v o i dz e m p m b 曲i l i t ye s t i m a t e ，i th 船s o m e d i s a d v 础g e s i nt l l et l l e s i s ，t 、v on e ws 舰t e g i e s = n b j fa n dn b j s ，a r ep r o p o s e d ，w h i c hc a i l r e m o v ez e r o p r o b a b i l i 母e s t i m a t ef m mn ba l g o r w i m o u ts m o o t h i n g a c c o r d i n gt o e x p e r i m e n t sa i l da 1 1 a l y s e s ，t h en e wa l g o r i m m ss h o wg o o dp e r f b r n l a l l c e si ne f f 醯t i v e n e s sa n d 印p l i c a b i l i t yc o m p a r c d 谢ml 印l a c ea 1 1 ds g ts m 0 0 t l l i n 兽 t h et 1 1 e s i sa l s of o c u s e so nt h ep r o b l e mw h e t t l e r 订a i l l i r 塔d o c m e n t sw e i g h t a d j u s t i n gc a n i m p r o v es i n g l ec l 骶s i f l e r ，sp e r f o r i n a n c e t w on e wa l g o m h m s ：k t r a i n la n dk t f a 砬，、h i c h u s es i m p l e rw e i g h t a d j u s t i n gs n 铽e 百e s 血a l l 、h a ti sa d o p t e db ya 出i b o o s ta l g o r i t l l l i l ，眦 p r o p o s e d t l l r o u g he x p e r i m e n t sa i l da l l a l y s e s ，t h cn e wa l g o r i 也m ss h o wb e n e rp e r f o n l l a i l c e s c o n l p a i 弓dw i t ht h eb a s el e 锄i n ga l g o r i t h m s ：n ba n dt f i d f b ya n a l y z i n gt f i d fa 1 1 dk 小附a l g o r i n h n sa 1 1 di n t e g r a t i n gt h ei d e at h a ti n c r c a s i n g 也e w e i g h t so fi r l c o n e c t l yc l a s s i f i e d 吲n i n gd o c u m e n t sc a i li m p r o v et h ec l a s s i f i e r _ p e o r m a n c e ， t h et h e s i sp r o p o s e sa i ls t f i d fa l g o r i 恤l ，w h i c hi sa 1 1i m p r o v e dv e r s i o no ft f i d f a l g o r i t l l i l l b ya d 叩t i n gk - n na l 鲥m m si d e a e x p e r i m e m sv e r i 毋t 1 1 a ts t f i d fa l g o r i t l l mo u t p e r f o 蛐s i 下i d fa n dk - n na l g o r i t h m s m o r e o v e r ，s t f i d fa l g o r i m mi sa se f n c i e n 瞳a st f i d f a l g o r i t l l m ，w h i c hi m p l i e s i ti sc o m p e t e n tf o rl a r g es c a l et e x tc a t e g o r i z a t i o nt a s k k e yw o r d s ：a u t o i r l a t e dt e x tc a t e g o r i z a t i o n ；z e r o - p m b 曲i l 酊e s t i m a t e ；s m o o t h i n g ；t m i n i n g d o c 啪e n t sw e i g h t a 由u s t i n g ；c o m b i n et f i d fa 1 1 dk - n n i i 硕士学位论文 插图索引 图2 1 文本分类系统体系结构6 图2 2 词袋模型中文档的词频向量示意图7 图2 3 词频矩阵示意图7 图2 4 最优分类线。1 0 图2 5 算法在不同训练集规模下的查准率1 7 图2 6 算法在不同选择特征数目下的查准率1 7 图2 7k - n n 算法在不同k 值下的查准率1 8 图3 1 朴素贝叶斯文本分类算法的训练与分类流程图2 0 图3 2n bt f 和n bt s 策略流程图2 5 图3 3k 次交叉验证( k - f o l dc r o s s _ v a l i d a t i o n ) 示意图2 5 图4 1a d a b 0 0 s t 算法流程图2 9 图4 2k t r a i n l 算法流程图3 l 图4 3k 胁i n 2 算法流程图3 1 图4 4k t r a n l 和k t h i i l 2 算法在2 0 新闻组数据集上的实验结果3 2 图4 5k t h m l 和k t r a i l l 2 算法在路透社数据集上的实验结果3 3 图5 1k n h 小4 0 d c l 算法示意图3 8 图5 2s 册i d f 算法流程图3 9 i i i 自动文本分类算法研究 附表索引 表2 1 相关变量表一 表2 22 0 新闻维数据集的新闻组类别 表2 3m o d a p t e 切分中被选择的2 5 个类别 表2 4 类别巳的邻接表 表2 5 全局邻接表一 表3 1 微型新闻组数据集上的实验结果 表3 2 路透社数据集上的实验结果。 表5 1s t f i d f 算法与t f i d f 算法在2 0 新闻组数据集上的实验结果 表5 2k - n n 算法在2 0 新闻组数据集上的实验结果 表5 3s - t f i d f 算法与t f i d f 算法在路透社数据集上的实验结果 表5 4k 小n 算法在路透社数据集上的实验结果 v 9 。1 3 。1 4 1 4 一1 5 2 6 2 7 4 0 一4 0 4 l 4 1 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 粜镩烈日期：。娉j 诩j 阳 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：粜馏奶 导师签名：张昂 0 飞， 日期：矽。卜年j 调，佣 日期：叫啤l 、月乙日 硕士学位论文 1 1 研究背景 第l 章绪论 随着i 曲舡俄的发展，人们进入了网络时代。在这个信息时代中，人们或多或少对信 息检索和搜索引擎有所了解，它们是获取信息的重要途径。现在虽然有很多有名的搜索 引擎，比如y a h o o ! 、e x c i t e 、g o o g l e 、百度等，但是它们的表现与人们的期望还存在很 大的差距。人们希望搜索引擎能在较短的时间内返回所有符合检索条件的信息，并且不 返回无关信息。但是，实际使用过搜索引擎的人可能都有这种体会：返回的检索结果中， 符合要求的信息很少甚至没有，不相关的信息倒是很多。信息检索能够提供的服务与人 们的期望之间存在的差距，使人们对信息检索提出了更高的要求，构造更好的信息检索 系统是人们努力的目标。 人们希望能够像订阅报纸一样订阅i n t e m e t 上的信息，只需预先在某个地方登记对 哪些信息感兴趣，或者干脆连这一步都省略掉，由某种机制从用户的近期历史浏览记录 中学习出用户的兴趣，然后只要有人在网络上发布了用户感兴趣的相关信息，就能立刻 推送到用户的电脑中。虽然通过预先登记兴趣进而获取信息这样的服务早已存在，但是 人们的兴趣不是几个简单的关键词能够精确概括的，因此这样的服务提供的很多信息可 能不是用户真正想要的，而且可能在不同的时间、不同的心情状况下，用户兴趣会有所 改变，这时候原先预定的信息就成为无关信息甚至是垃圾信息了。相比之下，自动实时 地学习用户的兴趣进而主动提供个性化的服务更加值得采纳。每个用户都有自己特定的 信息需求，设法获得这些个性化的信息需求，进而使用这些信息需求组成过滤条件，对 信息资源进行过滤，把符合条件的信息抽取出来主动对用户进行服务。个性化主动服务 将使用户获得更优质的服务，这也是人们努力的目标。 总之，一方面是人们对快速、准确且全面获取信息的渴望，而另一方面却是i n t e m t 上信息的杂乱无序，如何尽可能地为用户提供满意的服务，是信息处理研究的重点，也 是一件非常有意义的任务。为了给信息检索提供更高效的搜索策略和让其返回更准确的 检索结果，人们应该采取措施对网上的信息进行有序地组织，把相关的文档组织在一起， 文本分类聚类能够达到该目标。 文本分类“是有监督的分类，聚类。1 是无监督的分类，它们根据网络文本的内容将 其划归到不同的类别( 或簇) ，从而可以更好地对网络信息进行组织。对于信息检索， 文本分类聚类技术可以在如下几个方面有所帮助： 1 加速检索过程和提高检索性能。传统信息检索在网络文本库中搜索用户输入的关 自动文本分类算法研究 键字检索条件，出现了关键字的文本即被检出返回给用户。如果文本库中文本数目过多， 这个过程将是非常耗时的。同时，这种基于关键字的简单匹配算法，检索性能不高，会 返回很多不符合用户要求的无关文本。将文本分类聚类技术应用于信息检索可以加速 检索过程，并提高检索性能。通过采用文本分类聚类技术，将文本库中的文本预先分 为若干类别( 或簇) ，类内文本相似度高，类间文本相似度低。用户检索时，通过计算 检索条件与文本库中各类的相似度，再进一步在相似度最大的类中进行文本的选择，将 最合适的信息返回给用户。这样，既加速了检索过程，又返回了更具针对性，更加准确 的信息。另一方面，通过文本分类聚类技术，可以把信息组织成目录树结构，使用户通 过预分类的目录来浏览网页信息，这种提供目录检索网页的方式使得用户可以在较短的 时间内找到所需的相关信息。y o h o o ! 就支持这种目录结构的网页浏览。 2 组织检索结果。搜索引擎返回大量文本，各文本可能有不同的主题。用户为了寻 找所需的信息不得不在检索结果中顺序浏览，这样会浪费用户很多的时间。一种可行的 解决办法就是把获得的大量结果文本进行组织，采用自动文本分类聚类技术将文本分成 不同的类别( 或簇) ，用户在感兴趣的类别中再进行进一步的信息搜索。m a ma h e a r s t 等开发了一种称为“s c a n c r g 砒l c r “4 。”的技术，试图更合理地组织检索结果。这种技术 对检索到的结果页面进行分类聚类操作，按照页面彼此之间的相似程度分为若干组， 每组都有一个比较明确的主题，用户可以迅速地扫描每一组并选择那些和他的需求最相 关的组。 3 个性化信息推送。采用自动文本分类算法可以为用户提供主动的，个性化的信息 推送服务。通过跟踪一段时间内用户浏览过的网页，分析出用户的兴趣，然后可以有针 对性地进行主动服务”。 4 信息过滤。在i n t e m e t 上，不仅存在大量的有用信息，同时也潜伏着许多垃圾信 息和危险信息。如何避开那些令人讨厌的，甚至是危险的信息，比如垃圾邮件、黄色信 息、恶意代码、病毒、木马等，文本分类聚类同样能够在这些方面有所帮助。 1 2 文本分类研究进展 本文主要研究文本分类聚类技术中的文本分类部分。由于网页、新闻组、邮件等各 种格式的文档经过文法分析都可以转化为纯文本，而纯文本较为容易分析和处理，所以 文本分类的研究起始于纯文本分类的研究，同时纯文本分类的研究也一直是文本分类研 究的基石。超文本分类，邮件分类是在纯文本分类研究的基础上，结合超文本信息( 如 超链接、元信息、多媒体信息等) 或邮件的结构特性，来提高对超文本和邮件的分类性 能a 由予邮件分类现已是一个独立的研究方向，即垃圾邮件过滤，我们下面简要介绍纯 文本分类( 以下简称文本分类) 和超文本分类的相关研究进展。 早期的算法基于手工构建详细的分类规则集。举个例子，一条规则可能为“如果招 聘广告中有精通v c 的短语则需求职业类别为电脑程序员”。一些精确度很高的分类 硕士学位论文 器通过这种方法构造，不过代价很高，需要一批领域专家具备大量的专业知识，花费大 量的时间才能构造出正确且完整的规则集，而且以后研究领域的变更会使已有的规则集 作大规模的修改甚至全部重新构建。所以除极少数特例外，这种手工构建分类器的方法 缺乏实用价值。自动文本分类通过监督学习自动构建出分类器，同样可以达到较高的分 类性能，而且花费比人工建立分类规则集要小很多。 常用的自动文本分类算法主要包括三大类。一类是基于t f i d f 权值计算方法”1 的分 类算法，其基本思想是利用t f i d f 权值公式计算一个词在文档中的熏要性，然后用c o s i i l e 距离公式计算两个文档的相似度，这类算法包括r o c c l l i o ”3 算法，t f i d f 算法”，k 近邻 算法( k n e a r c s t n e i g h b o r s 简称k m o “”等；另一类是基于概率和信息理论的分类算法， 如朴素贝叶斯算法( n a i v e b a y c s ，简称n b ) “”，最大熵算法( m a x i m u m n 灯o p y ) “” 等；第三类是基于知识学习的分类算法，如决策树( d e c i s i o nt r e e ) “”，人工神经网络 ( 删6 c i a l n e 眦a l n e 咖d 湛，简称a n n ) “”，支持向量机( s u p p o r tv e c t o r m a c l l i n e ，简 称s v m ) “等算法。 基于监督的分类算法，必须通过对大量已标识文本进行学习，才能建立一个较精确 的模型，获得较高的分类性能。未标识文本相对于需要人工分类的已标识文本是一种廉 价且易获得的资源。将未标识文本结合到监督学习中，使得能够在较少的手工标识文本 的情况下构造较高性能的分类器，有很多学者在这方面作了研究。在1 9 6 8 年就有研究 者用已标识和未标识数据通过最大似然共同训练分类器“”。1 9 7 7 年，d e m d s t e r 等人提 出了e m ( e x p e c t a t i o n _ m 强i i r l i 刎o n ) 算法的理论框架。近年来，e m 算法在机器学习 中得到了广泛的应用“”，其中n i g 锄等人引入e m 算法结合贝叶斯文本分类算法，将 未标识文本结合到分类器的训练中脚3 。最大熵算法是另外一种利用未标识数据的分类算 法。“。未标识样本被用于联合训练( c o - 怕i n i 玎g ) 算法o ”以及作为背景知识为近邻分类 器的类别判断提供背景支持o ”。 多分类器( e n s e m b l e ) 的研究也是文本分类中的一个重点汹“1 。多分类器基于这样一 个想法：多个分类器错判的概率比单分类器错判的概率要小。通过构造多个分类器，将 各分类器的分类结果进行加权整合来最终决定待分类文本的类别。多个分类器的构造有 很多种方法。1 ，比如采用参数相同的同一训练算法在训练集的不同子集上训练出不同的 分类器，或采用参数不同的同一训练算法在同一训练集上训练出各异的分类器。多分类 器中比较有名的两个分支为b a g g i n g ”1 和b o o s t i n g 啪。3 “。b a 鹊m g 算法并行构造出多个分 类器，对各分类器结果进行加权整合。b 0 0 s t m g 算法是一种串行的学习算法，在训练中 先后产生一系列学习机，各个学习机所使用的训练集都是从原训练集提取出来的一个子 集，各个样本是否出现在该子集中取决于此前产生过的学习机的表现，已有学习机判断 出错的样本将以较大的概率出现在新的训练子集中。这使得其后产生的学习机更加专注 于处理对已有学习机来说较为困难的样本区分问题。最后对所有学习机按其i f 确率进行 加权，得到最终的分类器。a d a b o o s t 附“1 是一种应用广泛的，比较典型的b o o s t i 雌算法。 自动文本分类算法研究 传统文本分类算法大多数采用经典的向量空间模型( v e c t o rs p em o d c l ，简称 v s m ) ，即将文本表示成向量，作为向量空间中的一个点，然后通过计算向量间的距离 决定向量的类别归属。该模型的不足之处在于它一般不考虑向量中各个特征间的关系， 这使得距离的计算不够准确，从而导致分类精度不够高。现有研究者试酎使用概念代替 传统特征，将概念引入文本分类中。一些对基于概念的文本分类进行辅助韵工具，也就 是语义词典，比如w o r d n e t 3 2 1 ，知网( h o w n e t ) 。”，它们充分考虑了词与词之间的关系 ( 同义、反义、上义、下义等) ，为从传统特征中提取出概念提供了帮助。研究者在基 于概念的文本分类方面进行了研究，取得了较好的性能叶”1 。 超文本是具有结构信息的文本。在文本分类的研究基础上，研究者们发现超文本中 区别于纯文本的丰富结构化信息( 如超链接、标题和元信息等) ，对于提高超文本分类 性能有较大的帮助”“1 。y 缸矿”总结了一些利用超文本信息的规则，比如p a g eo i l l y 、 h t m lt i e 、h t m lm e t a 、l i l l l 【e dw j d d s 等，并且对于不同算法和不同的超文本数据集， 就这些不同的信息规则做了直接的比较和总结，但仍只是初步的研究和分析。 1 3 本文所做的工作 本文在自动文本分类算法方面作了一些研究和探索，主要工作总结如下： 1 本文首先介绍了文本分类的发展概况及文本分类系统的体系结构，对常用的分类 算法，比如n b 、t f i d f 、k n n 和s v m 等，进行了简单介绍和实验分析，为后续章节 的研究提供了理论和实验基础。 2 平滑技术虽然能够使n b 算法避免零概率问题，但该技术本身存在一些不足之处， 为此本文提出了两种新策略：n b j f 和n b _ _ t s ，可以在不采用平滑技术的情况下消除 n b 算法中的零概率问题。分析与实验表明，与l a p l a c e 和s g t 平滑算法进行比较，新 策略在有效性及适应性等方面具有较好的性能。 3 本文从b 0 0 s t i n g 算法思想得到启发，研究单分类器通过训练文本权值调整策略 能否得到性能提高的问题，采用了比a i d a b o o s t 算法中相关部分更简单的权值调整策略， 提出了两种新算法：k t r a i n l 和k t r a i l l 2 ，并采用n b 和t f j d f 算法作为基本学习算法 对其进行训练。分析和实验表明，在合适的k 值下，新算法能够对分类器性能起到一定 的提升作用。 4 本文在研究了t f i d f 和k 小n 算法的基础上，分析了两种算法的优缺点，并结 合增大错分训练文本在其类中的权值可以改进分类器性能的思想，提出了一种改进的 t f i d f 算法s t f i d f ，该算法采用k - n n 算法思想改进t f i d f 算法性能。实验验证 了s - t f i d f 算法在分类性能上优于t f i d f 和k n n 算法。同时，s t f i d f 算法保持了 t 兀d f 算法的高运行效率，能够胜任大规模的文本分类任务。 4 硕士学位论文 1 4 本文的内容安排 本文后续章节组织如下： 第二章：常用文本分类算法性能研究； 第三章：消除朴素贝叶斯算法中零概率问题的新策略 第四章：调整训练文本权值改善分类器性能： 第五章：一种改进的t f i d f 文本分类算法； 第六章：结论。 ： ：= ! 垫圣奎坌耋塞i ! 星璧：一：。= ：一： 2 1 引言 第2 章常用文本分类算法性能研究 文本分类算法是设计实现分类器的理论基础，因此本章专门介绍文本分类系统的体 系结构以及四种典型的分类算法，讨论它们的分类机制，通过实验测试进行性能对比及 分析，为后面章节奠定了理论和实验基础。 2 2 文本分类模型 文本分类一般基于“词袋”( b a g q f w o r d s ) 模型。4 “，即文档被看成是由相互无关的 单词构成的集合，不考虑单词之问的卜下文关系，单词出现的顺序、位置以及文章的长 度等，仅记录每个单刊在文档中出现的次数，或仅记录单词出现与否。通过对训练集进 行文法分析统计出所有单词在所有训练文档中出现的频率，得到词频矩阵。矩阵中的某 一元素就是某个单词在某篇训练文档中出现的频率。词频矩阵是文本分类算法建立分类 器模型的数据基础。下面介绍文本分类系统的体系结构，如图2 1 所示。 l 训练l 1 翥 一腰弧到习- - 1 分类器l l 语料集i 1训练 旧l 囱 1 分类器l 信息 l 待分类l 一募翥 叫匿甄咽一 1 分类器 i 文本广1 运算 f 顶处理特征选择训练、分类 图2 1 文本分类系统体系结构 1 预处理模块。预处理模块对训练语料集及待分类文本进行预处理。通过对文档进 行扫描，分析出文档中的单刊。对待英文文本，文法分析的步骤为：按空格切分出各个 单词，过滤掉其巾的停用词( s t o p 、o r d s ) ，如a ，t l l e ，t h a i 等：然后进行词干提取( s t e m m i n g ) ， 如将p l a y e d ，p l a y j n g 变为p l a y ；将文档对应的词频向量巾该单词的频率增1 ，如果这是 训练语料集中第一次遇到的新词，就存入单词列表，也称为词库。该模块中还包括保存 文档的文件名，类别等工作。如果对中文文本进行预处理，需要增加切词的工作。因为 中文与英文不同，英文有空格符将词与词进行间隔，而中文文木是连续的汉字串，词与 中文与英文不同，英文有空格符将词与词进行日j 隔，而中文文本是连续的汉字串，词与 硕士学位论文 词之闽没有明确的分隔标记。汉语中存在大量多义词，语义模糊，歧义性大，识别词的 边界很难。常用的中文分词算法有：基于词表的分词，基于统计的分词，基于规则和基 于统计相结合的分词，其中基于词表匹配的分词方法需要语言资源( 仅需一个词表( 分 词词典 ，不需要任何词法、句法、语义知识) 最少，程序实现简单。 2 特征选择模块。经过预处理模块的处理，堋练语料集文本及待分类文本均被表示 为词频向量，如图2 2 所示，同时训练语料集中所有文本的词频向量构成了词频矩阵， 如图2 3 所示。由于词库中存在大量的词汇，把所有单词都作为特征将带来一系列问题。 首先是向量的维数太大，给计算带来了非常大的压力，且存储空间大，处理速度慢。其 次是这些词中实际上有很大一部分是与类别无关的，对分类作用不大。因此。我们要降 低向量的维数t 采用某种特征选择方法选择词库中那些有代表意义的单词作为特征，从 丽得到降缎的词频矩阵和待分类文本词频向量。 o k 瓤函蜒 ：沙 3 j o l 麓嘴越 2 妇秘瑙罄柚l 糖 雾罗 o 糖麓 o 枷i 棼时 曩味r 轴t 确囊删l a 舶随毛锚翻妇孽藤船嗽 o f l 蚺幽 轴埔i 葚喇辱j 棚赢“翻整墼臻聪 _ ”一 l 妇疆艇赫e 篙慧鬣惑慧 o w 督b 轷黛l c 敦村 o舛垮 l v 静氛i 棚瞎 图2 ，2 词袋模型中文档的词频向量示意豳 釉r l 蛹2私心3 孙r d n f i l 枣l 龟j吼!d 醛 麝扭 擎i l e 2 如 旺麓群嚣 嚣妇 - - - f l l 蝴口蚍荔_ 3 露时 矗黼 豳2 。3 词频矩阵示意图 3 - 训练、分类模块。词频矩阵是算法建模的基础。在词频矩阵的基础上根据特定的 粪算法构造分类器，对待分类文本进行分类。比如，t f l d f 分类算法计算待分类文本 1 频向量与备类向量的相似度，将其妇入相似度最大的类别中去；n b 算法计算待分类 自动文本分类算法研究 文本属于各类的概率，将其分配到概率最大的类别中去。 2 3 特征选择方法 词库中包含了大量的词汇，如果将这些词都作为特征，将带来一系列问题。因此， 我们要降低向量的维数，选择那些有代表意义的词作为特征。首先对文本进行预处理， 去掉停用词和进行词干提取，然后采用某种特征选择方法对所有的词进行排序，选择一 定数量的较优的词作为特征。常用的特征选择方法有“： 2 3 1 文档频率 文档频率( d f ) 是出现某特征项的训练文档数量。通常认为d f 太小的单词没有代 表性，而d f 太大的单词又没有区分度，所以基于d f 的特征选择方法只留下那些d f 介于 中间的单词作为特征。 2 3 2 互信息 互信息即m u t i l a li n f o n n a t i o n ，简称m i ，定义如下： 毗圳。g ( 揣) = l o g ( 等 亿， m ( ，吼) 表示词f ，和类别q 的互信息量，体现了它们的共现程度。p ( 0 ) 表示词0 在训i 练文本集合中出现的概率，p ( f ，l 吼) 表示在类别唧的文本中词f ，的出现概率。 ( f ，c 女) 越大，说明词r ，和类别q 的共现程度越大，词f ，包含的类别q 信息越多。词，关于所有 类的平均互信息可以由下式求得： f | ( 0 ) = p ( q ) l 口( f ，q ) = 1 ( 2 2 ) 2 3 3 信息增益 信息增益即i n f o l l n a t i o ng a i n ，简称i g ，定义如下： l c 【 j g ( f ，) = 一p ( 唧) l o g p ( q ) 七- 1 l c ( 2 3 ) l cl c 、 + 尸( f ，) 艺p 奴h ) l o g 尸( c ；h ) 十p 酊) 芝p ( ql 劢1 0 9 p ( qi i ) = l ；1 ，g ( f ，) 反映了词0 为整个分类所提供的信息量。公式( 2 3 ) 中，p ( 0 ) 表示词0 不出现的概 率，p ( qh ) 表示词0 出现的情况下文本属于类吼的概率，尸( q1 ) 表示词f ，不出现的 硕士学位论文 情况下文本属于类q 的概率。 2 3 4z 2 统计量 以似) = 两嵩嚣 z 2 。心) = 艺尸( q 拓2 ( ，c i ) a 、b 、c 、d 均表示文本数量，如表2 1 所示，n = a + b + c + d 。 表2 1 相关变量襄 类文本集合 非q 类文本集合 ，出现ab r 不出现cd ( 2 4 ) ( 2 5 ) z 2 ( 0 ，q ) 统计量度量词0 和类别q 独立性的缺乏程度，z 2 ( 0 ，q ) 越大，两者独立性越小 相关性越大。z 2 。( 0 ) 表示对所有类别求平均值的z 2 统计量a 2 4 鞲羽文本分类算法研究 在众多文本分类算法中，我们重点讨论其中四种算法：朴素贝叶斯、支持向量机、 t f i d f 和k 近邻。 2 4 1 朴素贝叶斯算法 朴素贝叶斯算法( n a i v eb a y e s ，简称n b ，也叫简单贝叶斯算法) 是一种简单而有 效的传统分类算法，它有一个假设( 朴素贝叶斯假设) ：在给定的文档类情况下，文档 的特征( 即单词，不同单词或同一单词在文档中不同的出现位置) 是相互独立的。对朴 素贝叶斯算法来说，有一个各类统一的单词列表y = ( f i ，f 。) ，其长度( 即不同特征个 数) 为 。朴素贝叶斯算法计算文本d ：= ( d n ，d 。) 属于不同类别的后验概率，将该 文本分配到具有最大后验概率的类别中去。 文档吐属于类别吼的后验概率采用贝叶斯规则计算，见公式( 2 6 ) ： p b i 吐) = 掣 ( 2 6 ) 分类规则为： 9 自动文本分类算法研究 。船5 ( 吐) 2 a r g 圆罱 尸( q i 吐) ) 2 a r g 罂翰 尸( 略) p ( 哦i 白) ( 2 7 ) 其中1 c l 表示类别总数。类别的先验概率尸( 略) 采用最大似然估计( m 觚i m 嘲l i k e l i h o o d e s 廿m a t e ，简称m l e ) 进行求取，求取过程如公式( 2 8 ) 所示， 蚓 p ( q l z ) 以啪2 计 ( 2 8 ) 其中d = d 。， 为己标记文档的集合( 训练集) ， d i 表示其中所含文档的数目。当文 档磷属于类别q 时，尸( 1 4 ) = l ，否则p ( qi 叠) = o 。 尸( 4 q ) = n p ( f ，i 气) 略 ( 2 9 ) j l 公式( 2 9 ) 中略表示文档吐中特征0 的词频或权值( 进行特征处理后) 。尸( 0i 气) 的计 算根据采用的模型和平滑算法不同而各异。在最常用的多项式事件模型( m u l 虹n o m i a l e v e mm o d e l ，简称m m ) 和l a p l a c e 平滑算法下，其计算公式如下： 1 + 略 p ( ，lq ) = 生l _( 2 1 0 ) 盯+ 以 2 4 2 支持向量机算法 支持向量机( s u p p o r t v e c t o r m a c h i n e ，简称s v m ，也叫做支撑向量机) 是在二十世 纪9 0 年代以来发展起来的一种统计学习方法，在解决小样本学习、非线性及高维模式 识别问题中表现较好。s v m 算法不仅具有扎实的理论基础，而且在应用到文本分类时 取得了很好的效果。 图2 4 最优分类线 硕士学位论文 如图2 4 所示，图中的实心点和空心点分别表示两类的训练样本，考虑线性可分的情 况，即通过一条直线h 可以把两个类别无错误的分开，h l 和h 2 分别为过各类样本中离分 类线最近的点且平行于分类线h 的直线，h l 和h 2 之间的距离叫做两类的分类空隙或分类 间隔( m 盯西n ) 。最优分类线定义为：该分类线不但能将两类样本分开，而且要使两类 的分类间隔最大。直线h l 、h 2 上的训练样本叫做支持向量( s u p p o r tv e c t o r s 简称s v ) ， 因为它们支撑了最优分类线。图2 4 中的分类线h 是最优分类线。推广到高维空间，最优 分类线就成为最优分类面。 对于线性不可分的情形，可以构造一个变换，将问题转换到一个新的空间，在这个 新空间中使样本线性可分。 支持向量机的基本思想可以概括为：首先将输入空间变换到一个新空间，然后在这 个新空间中求取最优线性分类面。 超平面是对两类分类的划分，对于有大于两类的多类文本分类，就对每个类分别构 造一个超平面，将该类与其余类分开。有多少个类就构造多少个超平面。分类时就看哪 个超平面最适合待分类样本。 2 4 31 r i 瞪d f 算法 在t f i d f 文本分类算法中，采用的是向量空间模型( 脚0 r s p e m 0 d e l ，简称v s m ) ， 每个单词被看成是一个特征项f ，每篇文档被看成由单词组成的向量 z = ( 矗，4 ：，屯) ，在每篇具体文档吐中，单词f ，( 1 ，h ，n 为词汇表长度) 被赋予 一个数值略，表示f ，在该文档中的重要程度，称为f ，的权值，即有： 吒= 吮4 嘶 ( 2 1 1 ) 妒l 。甙劳+ 1 ) 公式( 2 1 1 ) 和( 2 1 2 ) 中，词频( t e 册f r e q u e n c y ，简称t f ) 以表示特征项0 在文档d ， 中出现的次数，文档频率( d o c l l l i l e n tf r e q u e n c y ，简称d f ) 够指整个训练文档集合中 包含特征项0 的文档个数，啦是特征项0 的反比文档频率( i n v e r s ed o c 哪e m f r e q u e n c y ，简称i d f ) 。t f i d f 算法将属于同一类的所有文档向量加起来，得到每一个 类o ( 咯c ，c 表示所有类别的集合) 的特征向量i = b 。，：，) 。利用t f i d f 算 法对一篇待分类文档进行分类时，通过计算该文档向量乏与每个类向量i 的相似度 s f m ( z ，i ) ，相似度最大的类向量i 所对应的第| 类就是待分类文档的类别。计算公式 如下： 自动文本分类算法研究 2 4 4k 近邻算法 曲n ( z ，q ) i = 虿 q e o 翼：i 圣丝：鱼 q l f m 2 + 。2 c h 。( 吐) 58 r g ! 譬3 打”( 砖，q ) ( 2 1 3 ) ( 2 1 4 ) ( 2 1 5 ) 最近邻法( n e a r e s tn e i 曲b o r ，简称n n ) 是模式识别中广泛使用的分类方法，是模 式识别非参数法中最重要的方法之一。k 近邻法( k n e a r e s t n e i g h b o r s ，简称k n n ) 是最 近邻法的一个推广，当k 取1 时就是最邻近法。n n 强调最近点的重要性，而k n n 则从整 体考虑，是一种更为普遍的方法，理论认为它的错误率比n n 低“。k n n 算法思想简单： 对于一篇待分类的文档，系统在训练集中找到其最近的k 个近邻，统计k 个近邻中多数属 于哪一类( 非加