（计算机应用技术专业论文）基于类别的特征选择算法的文本分类系统.pdf

西南交通大学硕士研究生学位论文 第l 页 摘要 文本自动分类技术是自然语言处理的一个重要的应用领域，是替代传统 的繁杂人工分类方法的有效手段和必然趋势。特别是随着互联网技术的发展， 网络成为人们进行信息交互和处理的有效的平台，各种数字化的信息每天以 极高的速度增长。面对如此巨大的信息，人工分类选择已经无能为力，计算 机自动分类己成为网络时代的必然选择。 目前，对于文本分类技术的研究，大多数研究者的精力主要放在各种不 同分类方法的探索与改进上。然而，文本分类中的特征选择( 或称特征提取、 索引词选择) 一直是文本分类的关键技术和瓶颈技术。所以，对特征选择算 法的研究是十分必要的。 本论文对文本分类中所涉及的各项技术进行了较全面的阐述，特别对当 前文本分类中各种常用特征选择算法的性能以及优缺点进行了分析。通过以 上分析，作者发现目前的索引词选择算法都是基于词频的，没有利用训练样 本中的类别信息。为此，作者提出了一种新的基于类别的特征选择方法，并 以此为基础设计了一个英文文本自动分类系统。 接着，论文根据不同特征选择阙值下的分类性能，确定了特征选择的初 始阈值，并在该阈值下，对系统完成了不同实验条件下的、面向大规模真实 文本的分类性能测试，包括：在开放测试和封闭测试下系统的性能；在不同 原始特征空间维数下的分类性能；相同条件下与s v m 和n a i v eb a y e s 分类器 的分类性能比较。之后，论文对测试结果进行了理论分析，确定了基于类别 的特征选择算法能够在一定程度上提高分类系统的性能。进一步地，论文通 过与n a i v eb a y e s 分类器在相同条件下的训练分类时间对比，分析了本文设 计的基于类别的特征选择算法以及实现的分类系统的效率。 最后，本文通过对上述实现技术的阐述及其对实验结果的分析，提出了 一些关于文本分类及特征选择方法研究的见解，并对今后的研究工作进行了 展望。 关键词：文本自动分类；特征选择；向量空间模型；支持向量机； 朴素贝叶斯 蘸辩交通大学硪圭矫究生学位论文第l l 蓑 a b s t r a c t t e x ta u t o m a t i cc l a s s i f i c a t i o ni s 融妇p o r t a n ta p p l i c a t i o nf i e l do fn a t u r a l l a n g u a g ep r o c e s s ，a l le f f i c i e n tm e a n s a n d n e c e s s a r yt r e n d t os u b s t i t u t et h et r o u b l e d t r a d i t i o n a lm a n u a lc l a s s i f i c a t i o n + e s p e c i a l l y ，w i t ht h ed e v e l o p m e n to fi n t e m e t t e c h n o l o g y , t h e n e t w o r kb e c o m e sa ne f f e c t i v ep l a t f o r mf o rp e o p l et oe x c h a n g ea n d p r o c e s si n f o m m t i o n ，a n dd i g i t a l i n f o r m a t i o ni n c r e a s e s d a i l yw i t hh i g l ls p d 。 f a c i n gs u c hag r e a td e a lo fi n f o r m a t i o n , m a n u a lc l a s s i f i c a t i o nb e c o m e sh e l p l e s s ， a n dm u s tb es u b s t i t u t e db yt e x ta u t o m a t i cc l a s s i f i c a t i o n r e c e n t l y ，f o r t h e s t u d y o ft e x ta u t o m a t i cc l a s s i f i c a t i o n t e c h n o l o g y ， r e s e a r c h e r s m o s t l y f o c u s0 nt h e e x p l o r a t i o na n di m p r o v e m e n to fd i f f e r e n t c l a s s i f i c a t i o na l g o r i t h m s h o w e v e r , t h ef e a t u r es e l e c t i o no f t e x tc l a s s i f i c a t i o nh a s a l w a y sb e e nak e ya n db o t t l e - n e c kt e c h n o l o g yo ft e x tc l a s s i f i c a t i o n s o , i ti s n e c e s s a r y t os t u d yf e a t u r es e l e c t i o n a l g o r i t h m s 聪sd i s s e r t a t i o n f i 基t y d i s c u s s e ss e v e r a l t e c h n o l o g i e s i n v o l v e di nt e x t c l a s s i f i c a t i o n ，a n ds p e c i a l l ya n a l y z e st h ep e l 击o l m a n c e ，t h em e r i ta n dt h ed e f e c to f v a r i o u sf e a t u r es e l e c t i o n a l g o r i t h m sf r e q u e n t l y u s e di nt e x t c l a s s i f i c a t i o n 。b ya b o v e a n a l y s i s , t h ea u t h o rn o t i c e dt h a tc u r r e n tf e a t u r es e l e c t i o na l g o r i t h m sa 牌a l lb a s e d o nt e r mf r e q u e n c y , a n dn e g l e c tt h ec l a s si n f o r m a t i o ni nt h et r a i n r a n gs a m p l es e t f o rt h i s ，t h ea u t h o r p u t sf o r w a r d 8n e wf e a t u r es e l e c t i o na l g o r i t h mb a s e do nc l a s s i n f o r m a t i o n , a n dd e s i g n sa ne n g l i s ht e x ta u t o m a t i cc l a s s i f i c a t i o ns y s t e mo nt h e b a s i so f t h i s a l g o r i t h m t h e n , t h ed i s s e r t a t i o nd e t e r m i n e st h ei n i t i a lt h r e s h o l dv a l u ea c c o r d i n gt ot h e c l a s s i f i c a t i o np e r f o r m a n c eu n d e rd i f f e r e n tt h r e s h o l dv a l u e s , a n dh a sd o n et h et e s t s f o rt h i ss y s t e mu n d e rd i f f e r e n te x p e r i m e n t a lc o n d i t i o n sw i t ht h ei n i t i a lt h r e s h o l d v a l u ea n d h u g ea c t u a lt e x ts e t , i n c l u d i n gt h es y t e mp e r f o r m a n c eu n d e rt h ec l o s e a n do p e nt e s t s ；t h ep e r f o r m a n c ew i t hd i f f e r e n t o r i g i n a l t e r md i m e n s i o n s ；t h e s y s t e mp e r f o r m a n c ec o m p a r i n gw i t hs v mc l a s s i f i e ra n dn a i v eb a y e sc l a s s i f i e r u n d e rt h es a m ec o n d i t i o n a l t e rt h i s ，t h ed i s s e r t a t i o na n a l y z e st h et e s tr e s u l t s , a n d g e t st h ec o n c l u s i o nt h a tt h i sa l g o r i t h mc a ni m p r o v ec l a s s i f i e r sl 毙 r f o r m a n c et o 。_ _ 日学- 。_ _ _ 。_ 蝉o 州o - _ _ _ _ _ _ 州_ _ 。_ 。_ 西南变通大学矮童磷究生掌位论文繁l ll 页 s o m ee x t e n t f u r t h e r m o r e b yc o m p a r i n gt h et r a l n n i n g 嘲l l eo ft h ec l a s s i f i e rw i t h t h a to fn a i v eb a y e sc l a s s i f i e r , t h ed i s s e r t a t i o na n a l y z e st h ee f f i c i e n c yo ff e a t u r e s e l e c t i o n a l g o r i t h m a n dt h ec l a s s i f i e rb a s e do nt h i s a l g o r i t h m f i n a l l y ，t h r o u g ht h ea n a l y s i so fa b o v er e a l i z a t i o nt e c h n o l o g ya n dt h et e s t r e s u l t ，t h ed i s s e r t a t i o np m p o s e ss o m eo p i n i o na b o u tt e x ta u t o m a t i cc l a s s i f i c a t i o n a n df e a t u r es e l e c t i o n a l g o r i t h m , a n dg i v e s t h e e x p e c t a t i o nf o r f u t u r ew o r ko nt h e m 。 k e y w o r d s ：t e x ta u t o m a t i c c 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 ； v s m m o d e l ；s v m ；n a i v eb a y e s 麟泰交逶夫攀鞲兖生学僚论文 第l 页 1 1 问题提出 第一耄绪论 曩兹，i n t e r n e t 秘i n t r a n e t 上瓣售惠量持续麓速爆炸式壤长，人嚣j 必 了更好遗找到、过滤和管理这些资滁，需要将一臻自然语言文档基于它们的 内容，放入一个或多个预定义好的秘袋下，此即文档分类( 亦称文本分类) ， 已。经变成了一个在信息缎织和管理中酃非常重要的 词题。 文耥( d o c l h r m n t ) 泛掺觳瓣文零或者文本巾约冀段( 霰黪，匈嚣或露 子) ，一般指一篇文章。尽管文档可以有多媒体对裂，但是本论文只讨论文本 对象，并对文本与文档不加以区别。 。 鹜豢和璎状 文本自动分类技术魑自然语言处理的一个重蒙的应用领域，是替代传统 懿繁杂人工分类方法的霄效手段和必然趋势，特别怒随藿互联网技零豹发展， 隧络成为入稍遗李亍傣感交互和处理斡簸有效的平螽，各种数字他的信息每天 以极高的速度增长，丽对如此巨大的信息，人工分类选择已经无能为力，计 算机自动分类己成为网络时代的必然选择。通过利用先进豹计算机技术、人 工饕魏按零，不稷霉数实瑷方霞快蕤豹分类效聚，麓省大蠢静入力穆力，莠 且可以避步迸行更深层次的信息挖掘处理，提漪信息的利用效率。 文本分类处理的研究是计算机、信息处理领域的重要内容，特别是随着 薅络技零戆抉速发展，这静应曩瞧变褥燹燕迫切自动文本分类技零嚣磅究 最早可追溯副2 0 世纪6 0 年代盼m a r o n i j 的研究工作，从那时越，该技术便逐 渐应用到信息检索、文档组织、文档过滤等方面l1 9 7 0 年，s a l t o n 等人提出 了i 句：星空闯模型( v s m ，v e c t o rs p a c em o d e l ) 模烈，由于该模溅在怠好的统 诗学方浚纂麓上繁骥蟪鬓瑶了薅交零特性豹箍蒙熬述，获瑟成兔文本努类经 理的一种经典模型；到8 0 年代末，在文本分类领域，基于知识工程的方法一 宜占主导地位，其中最藩名的是c o n s t r u e 口 系统，臌然该方法取得了较好的 分类效暴，然 嚣该方法鬟努泠类裁赁g 麓定霾难、攘广蛙差鹣缺患，缀难大燕 嚣南交通大学静 究生掌僚论文第2 页 模推广应用；进入9 0 年代以来，随着互联网技术的快速发展，文本自动分类 戆磅交邀滋入了一令耨熬徐段，冬穗分类方法援继褥到了发震，惫摆援器学 习技术为主的信息分类技术逐渐取代了基于知识工襁的方法，成为文本自动 分类研究的主要形式，如n a i v eb a y e s 、d e c i s i o nt r e e 、神经网络等等p ， 1 9 9 8 年d o r t m u n d 大学的t 。j o a c h i m s p 搽讨了支持囱量辊( s v 勘方法递行文 本分类，敬得了穰好的效莱。诧韩，些学者还采粥b o o s t i n ，l 方法来探讨 提高分类处理的方法。湖内，许多研究院所也对中文信息分类技术进行了大 量的研究阶“】，在具体分类算法上与图外是相同的，只是由于中文的词与词 之阗没奏骥漫懿努裁，强筵零要遘学锈调照理。 1 1 2 研究动机 疆蘩簿予文本分类效寒鳇骥究，大多鼗磅究囊瓣糖力主要敖在各耱不藏 分类的方法探索与改进上。然而，文本分类中的索引词选择( 或称特征提取、 特征选择，以下不做区分) 一直是文本分类的关键技术和瓶颈技术。所以， 对索引词选释算法的研究建十分必要的。 随着嘲络鹣发震，奁线文档瀑炜式氆鸯拜，对文零分类提毒了瑟黼静要求。 特征空间降维，也就是索引词选择算法，是文本分蹙的关键技术。文本的原 始特征的数量可能很大，或者说样本处于一个高维擞间中，构成文本的词汇， 数量是糖姿大魏，函魏，表示文本瓣囊爨空阂瓣终数毽摇姿丈，霹疆这至l 尼 万维。因此，我们需要遴行维数压缩豹工作，这样做的目的有两个，第一， 为了提高襁序的效率，撼高运行速度，第二，所有几万个词汇对文本分类的 意义是不嬲粒：一些道嬲的，各个类别都普遍存在的调汇对分类熬蓑献小， 在菜特定爽巾出现频率大褥在其稔类中出瑗频率，j 、瓣词汇对文本分类的贡献 大。为了掇商分类精度，对于每一类，我们应去除硼些表现力不溅的词汇， 筛选出针埘该类的特征项集合。通过映射( 或变换) 的方法可以用低维空间 来表示样本，嚣簸一缀憋廷孛撬选密一些爱奏效豹淤这赘簿绦特缝奎阕缍数 的目的这就是索引词选择的目的。设计出好的高精确度的索引词算法来， 可以减少人力、物力，大大地提高分类效率。 基前的索引词选择冀法有很多秘，经经过作者游磷究发现，以往静索弓 西南交通大学磷究生攀僚论文 第3 爱 词选择，谖练撵本孛弱类菇售恣帮没蠢梭翻麓甏，本文蘑望技裂一耪掰瓣鏊 于类别髅息的选撵葵法，并将篡成用副实际文本分类系统中去。 1 2 本论文的研究内容 零论文对文本分类中掰涉及躲备瑗援术送行了较全嚣麴阚述，特翁对警 越文本分类中蠢秽常羽索引词选择算法躯性戆以及优缺点进行了分辑，提出 了一犟孛新酶基于类鄹静特征选撵算法，弹敷此为蒸础设计了一个荚文文本爨 动分类系统，遇过实验辩其性能进行了测试： 蓠蠢薅琵该特锤选撵算法与健绕钓姆征选择簿法，缝合短瘸粥分类恭绫 上的性能，初步确定该方法的可行性；然后对比不同特征选择阕值下的分类 往戆，锯步确定了特霰逡择懿秘鲶瓣毽；在该溺餐下，辩系统避行了露穗大 规模真灾文本韵分类钡试，测试了不同懿验条彳牛下的分类性能：对比了开放 瓣试释瓣蠲测试静瞧裁；对篦了该分类系统在不瓣琢始特征空阚维数下黪分 类性能；对比了与s v m 以及n a i v eb a y e s 分类器程相同条件下的分类性能； 瓣测试熊栗遴学了毽谂努掇，确定了基于类舅a 粪冬姆径选弹冀法裁够在一定疆 度上掇商分类系统的馁鼹。苒邋过与n a i v eb a y e s 分类器在褶网条件下的硼 练分类嘲帮醅跑，分耨了本文竣诗懿蕊予类澍豹姆薤选耩算法激波实现豹分 类系统的效率。最赝，本文通过对上述实现技术的阐述殿其对实验结果的分 援，褥鹚了一熬关予文零分类及糁铥逡褥算法舔究粒觅黪，并对今嚣瓣磷襄 工律滋符了展掇。 。3 零论文的绩构安瓣 零论文静篱续章节豹肉容安攘魏下； 第= 牵：介绍本论文所涉及的知识凝础，锫擒史本分类方法，文本表示， 分类瞧黢谬傍方法，淘爨空麓横婆l 等文本分类笑键搜本，并穷绥奉埝戈錾 用分类方法原瓒和使用靛工其。 第三章：分绥羁涿貉文本癸类孛豢溺豹见魏特 蒌选择方法戆魏簸点，劳 提出一种耨的基于类剐昀特征逡撵算法。 繁陛攀：奔绥了以麓予类舅8 秘姆鳋逸嚣算法必基戳豹分癸曩绫。薅系绞 西南交通大学研究生学位论文 第4 页 的整体结构、预处理、特征提取、训练算法、分类算法等进行了详细介绍。 第五章：详细阐述本论文设计的分类系统在各种不同参数和条件下的性 能，对实验结果进行分析。 第六章：对本论文所做工作进行总结，并提出将新的特征选择方法应用 于中文文本分类中，并设计更网络化，智能化，多功能化的分类系统，应用 到邮件过滤器或搜索引擎等热门实际应用中去的设想。 嚣麓交通文学磁突生学位论文 第5 页 第二章涉及的知识基础 2 1 文本分类概述 2 ， ，1 分类方法撅述 在分擞器构造上，早期多使用基于知识工程的规则方法，卡耐熬集团基于 此方法为路透社开发的c o n s t r u e 系统较早地进入了实用阶段，它繇天对路透 毒纛予上万缒羲终逡行蠡渤分类。褒在主要镬建基予绫诗戆方法，懿$ 素炙时 斯( n a i v eb a y e s ) f 1 2 j 、k 一近邻( k - n e a r e s tn e i g h b o u r s ，k - n n ) t 3 1 、决策树 ( d e c i s i o nt r e e ，d t ) 【1 4 1 ，决策规则( d e c i s i o n r u l e ) ，回归模型( r e g r e s s i o n m o d e l ) 【1 3 】，神经网络( n e u r a ln e t w o r k ，n 抑p s i ，支持向量桃( s u p p o r tv e c t o r 溉e h i n e ) | 4 2 1 1 4 3 1 1 4 4 1 1 4 5 1 等。其中，经过大_ 麓实验证唆，s v m ，k n n 是魏雅毙较嚣 秀的分类器。下面简要介绍一下这几种分类方法。 2 。 。 。1 哭卧斯 贝叶斯分类器是一种典型的基于概率统计的分类器。贝叶斯分类器的数 学基础是贝叶斯定理，主要思想就是计算在给定一待分类文档的条件下其各 个类澍豹条侮概率，郄： 麒c 。：堑! 堕堡! 。p ( d j ) 然后选撵条件概率鼹岗的那个类别为该文档所属的类别。由予撵计算过 程串采瘸不鞠秘方法，受野簸分类器蠢不鞫的交释，最鬻焉秘是$ 索燹时蘩 分类器( n a i v eb a y e sc i a s s i f i e r ) 。朴索贝叶斯分类器采用朴素髓叶斯假设， 即假设一个文档中任何两个单词之间的出现与否是棚互独立的。朴素贝叶斯 分类嚣套嚣秘模型，多元援努铡( 趣i t i - v a r i a t eb e r n o u l l i ) 摸黧窝多顼式 ( m u t t i n o m i a l ) 模型。关于朴素贝时新分类器将在2 5 节详细介绍。 西游交通丈学磷究生学彼论文第6 页 2 1 t 2 决策树 决策树文本分类器麟楚构造一棵分类树来对文本进行分类。谯决策树中， 内部节点寝示特征，从内部节点引出的分枝表示在这个特征上的测试输出， 而每个叶予节点表示类别。对于一个待分类的文本文档d ，从这擞树的根节 熹牙鲶，溪l 试这个节点撵定懿特缝，按照文整毒在浚特征土静毽鼯应黪瓣棱 向下移动。然后这个过程在以新节点为根的子树上霪复，直到到达一个叶节 点为止，这个叶节点代我的类别就是浚文档所属的类别。 决策越数学骂算法采臻分聂治之浆繁路，首先凑器疑寿弱锻练文趟是否 都属于一个类剐( 都属于癸别a 或c ) ，如果不是，选择一个特德以，将训 练文档集0 分成两部分，每一部分要么都包含特征矗，要么都不包含特征 氕，然后獬一部分作为个独立的予树，重复进行这个过程，直到每棵楗的 时子繁点鹣掰骞瓣练文辎帮属于司一个类嗣为壹。 以上的学习过程中，主要的问题照如何选择特征作为测试节点。通常的 做法是计算各个特征的信息增益或者熵的值，然后搬据这些值的大小顺次选 择。建这榉熬方法建立豹决鬟褥簸邦存在对堋练数嚣过疫按会 ( o v e r f i t t i n g ) 的阕题，所以大多数的决策树学习_ 箨法都包含有一个剪枝过 程。 所谓越度拟合( o v e r f i t t i n g ) 问题，是指经过避分训练后，分类器的性 缝最建缝臻炎是赞怼训练集嚣言，瘦弱弱 蘩| 练集辩象露，分类器往鼹霹蕤 会下降。即训练得到的分类器推广性能不强。 对抉缭树剪枝有两种方法：前剪枝( p r e p r u n i n g ) 和后剪枝 ( p o s t p r u n i n g ) 。兹剪鼓在凌繁舞夔擒远过程孛遂霉亍，嚣嚣赘技纛决麓鼹宠 全构造努螽进行。 2 1 1 3 神经网络 神经网络( n e u r a ln e t w o r k ，n n ) 文本分类器是一个单元网络，其中输入 单元表示特征，输出单元表示类别，谶接单元的边的权重表示依赖关系。对 个待分类交档d ，将它鹏特征瓤权熬输入到输入举元，这些单元通过网络 鞭南交滋大学研究生学位论文 第7 页 蠢兹传搔，豢嚣输出零元豹餐靛鼹表分类熬缝巢。 艇型的神经网络的学习方法是用藤向传播法。后向传播法通过迭代地处 理一族训练榉本，籍每个样本黥耀络颈灏与实鞲囊l 逶戆类标号魄较，将较 结果反馈到网络的前鼷单元中，修改单元之阃的权重，使得网络预测和实际 类舅# 之阉懿均方误差最，l 、。 2 。1 1 4 最近邻居 璇近邻居法是基于类比学习的一种方法。每个训练文档代表jf 维空间的 一个点，这榉掰毒簸调练文秘都存放程 f l 缝空淹中。给定一个待分类文档 d ，k - , 最近邻居法搜索模式空间，找出最接近待分类文档d 的k 个训练文档。 这k 个饔练文毯称秀文狴覆蠡冬“远邻”。“戆远髓”臻致死受德糕离定义，其 中两个文档d ，= ，d 女= 的欧几里德距离 是 厂- d i s t ( d ，d a = ：，( z 。- l ，) 文档d ，被分配例k 个最邻近训练文档中占比例最大的类别中。当k = l 对，文魈或被指定到模式空闻中与之簸邻近的训练文撼所属的类捌中。 2 1 ，1 6 支持向量机 支持向纛机( s u p p o r t v e e t o em a c h i n e ，s v m ) 最先由j o a c h i m s 应用在文 本分类孛啊，羚数褥了基太弱成功，霹淤说支耱恳璧凝文本分炎器是当赫饯 能最好的文本分类器。支持向辍机的主要思想魁针对两类分类问题，在商维 空闻中寻找一个超乎瑟雩# 蔻弱类豹分割，鞋僚涯最小豹分类镖谟拳。瑟旦支 持向嫩机的一个重要的优点是可以处理线性不w 分的情况。y 蚰d 1 3 l 曾经做过 实验，发现s v m 处理线蛙不豫分阉题毙处理线性可分闼题差不了多少。 讴如j o a c h i m s 在文献【7 所述，s v m 之所以在文本分类系统表现如此优 秀，主要有出于以下嬲个特点：第一，因为s v m 可以处理高缎特征空润i 嚣 不需器额外的开销，所以s v m 中对于特征筛选要求不高；第二，大多数文 本分类问题是线性可分的，例如在文档集o h s u m e d 中，所有的类别都是线蛙 嚣滚交通大学磺变生学位论文 雾8 页 可分的，r e u t e r s 文档集中的大多数类别也是线性可分的。 关于支持向量机分类器我们将在2 3 节详细介绍。 2 2 文本表示与赫鲞空闻模型 要将文档相互比较，先要描述文档。在文献【1 6 】第一次提出国动文本检 索( a u t o m a t i c t e x t r e t r i e v a l ) 移蕊塞捡索f i n f o r m a t i o n r e t r i e v a l ) 援念藤，塞现了 许多基予文档( d o c u m e n t ) 和问题( q u e r y ) 之间相关词语比较的计算模型，具 有代表性的有布尔模型( b o o l e a nm o d e l 、1 1 7 1 ，向缀空间模型( v e c t o rs p a c e m o d e l ，v s m ) i 1 8 j ，聚炎模型( c l u s t e rm o d e l ) f 1 9 1 ，基于知识模型 f k n o w l e d g e 。b a s e dm o d e l ) 1 麓帮壤率楱瀣( p r o b a b f l i s t i cm o d e l ) 1 9 1 f 4 6 3 等。 上述几种模型中，向赞空间模型f v s m ) 由于具村较强的可计辣性和可操 作性，特别是随着网上信息的迅速膨胀，它的应用融经不仅仅局限于文本检 索、鑫动文攘、关键词莛动提取等筵绞阉题，还羧广泛遣应塌至g 搜索弓| 擎、 个人信息代瑾、网上新闻发布等信息检索( i n f o r m a t i o nr e t r i e v a l ) 领域新的应 用中，并麒取得了较好的效果。 向量空阔模型的最大优点在于它谯知识表示方披上豹巨大优势。在该模 墼审，文襁浆内容被形式纯为多维空瀚孛弱一个蠢，遴过囱l ( v e c t o r ) 兹形 式给出。文本分类则可方便地转化成对向量的处理、计算。也正鼹因为把文 档以向量的形式定义到实数域中，才使得模式识别和其他领域中备种成熟的 诗算方法褥淤采翅，极太缝摄褰了巍然语言文撞戆霹诗算挂霹霹撵俸性。 关于随璧空间模型，由于本文提 圭l 的基于类别的特征选择方法与其有密 切的联系，本文将在z 2 节对向量空间模型进行详细介绍。 2 。1 。3 分类睦能译绘瓣羧 2 1 3 1 文本分类器的评价标准 在文本分类中，对分类器性能静评价标准，燹多静是经验性瓣，而不是 分析性的。这是因为骥分析性地评价个系统，b b 如证明一个系统的正确 性和完备蚀，必须能够对j 塞个系统所要解决的问题缭出一个形式化缒表述， 霆藏交逯大攀蟥交生学位论文第9 页 然而由于文本分类的主观性( 比如一个文本是否属于莱一类别带谢很大的主 观性，两个不同的专家可能将其归类鬻0 不同的类别中) ，在本质上不能给出一 令形式识豹袭这，鞭数袋分撰缝逸对分类器进行谬俊( 澎魏涯甓逮令分类器 是正确的) 目前难度较大。 通常对一个文本分类嚣进行评价盎兰要是针对它的效果( e f f e c t i v e n e s s ) 或 性能( p e r f o r m a n c e ) ，即这个分类器在多大程度上熊够骰出正确约决燕，丽 不是它静效率( e f f i c i e n c y ) 。要对一个文本分类嚣避l 行效巢溅试，有两种方 法：训练测试法和k 折疯叉验证法( k - f o l dc r o s sv a l i d a t i o n ) 1 1 4 1 ，这两种方法 都要将原始文档集分割为训练文档集和测试文档集。 训练粲和攒l 试集 现在的文本自动分类，大多采用的是机器学习的方法，机器举习的方法 依赖于个已经按照分类俸系分好类鹅语辩痒。该潺辩淳中是聂溺分好类豹 文本。文本分类，g l 撬蹬个把新文零归类裂文率掰耩类弱的谯务。为了衡 量文本分必的效果，我们经常把语料滕分成两个不糊交的集合，遮两个集合 不一定相簿： 翊练黛，这令集合鹣蠢匏是惹予萝蠢续惠各令类别懿特性毅穗建分类器。 测试絮，这个集合用于狈8 试分类器的分类效果。测试集的每个文本都通 过分类器分类，然后与藏确决策的分炎结果相对比，分类器的效粜就是比较 通过分类秣获穆豹类罢h 与正确决策的类铡豹相符鼬馈况。 训练测试法 值得滋意的是，测试集用于测试分类器的分类效果，原则上并不参与分 类器戆秘憩，絮采测试集氇参与势类器煞建设，黧爨疆结栗是不器，镑戆，毽 能评价的缡果也就不其荫科学意义。貔们可能得到一个看起来效聚非常好的 分类器，而实际上，该分类系统的分必效果如何我们并不清楚。假在有些情 况下，为了封 狳一些寒皴因素豹于抗，域者为了获德些分类器参数酌信息， 经常禳蠡需簧在训练爱纛接拿训练集来作分类测试，这种方法称麓封闭澳试。 在实际上，在评价过分类器后，可以在整个原始文档集上重新训练这个 分类器，以提升分类器的实际性能。强这种情况下，分类器实际性能可能会 西南交滏大学礴窕生学位谂文 第 o 页 魄裁嚣对分裳器毪戆瓣谬徐蠢瑟摄裹，因为激终懿努类器是农菱多豹数撵上 进行训练的。 潋上这耱方法称受训练澳l 试法。 薹( 摄交必验泛法 在k 折交叉验诞法中，原始文档靴被分为k 个不相交的集合t l ，t 2 t k ， 然鼷以t v l t l 为谢练集，以t i 势溅试集反复运用训练寡l 试法，建立k 巾 不同的分类器。最后评价分类器的性能时，首先计算各个分类器的性能，然 后以莱秘方法褥到k 个分类器性能的平均僮，就是最终的分类器的性糍。 在训练测试法和耗折交叉验证法中，常常需要对分类器内部参数避 亍调 整，以鞭4 试参数取什么范围时分类器的效果最好。为了进行这种优化，在训 练测试方法中，训练验证集被进一步分为训练集和验证集。训练集和黢证集 也不能是稠间的文本，诩练檠用来稀造分类瓣，而验诚集餍来重复涣i 试分类 器的性能，以进行参数优化。同样，我们也不把进行过参数优化的文档甩于 溺试分类器酌往能，验证集和溺试集必须傈耨相互独立阐。 2 1 ，3 。2 性甏谬倏的圭要摇蠹秣译埝方法 对分类器性能评价的主要指标有键豳率( r e c a l l ，办称查全率) 、精确率 ( p r e c i s i o n ，亦称查对率) 、难确率( a c c t a - a c y ) 、错误率( e r r o r ) 等。另外， 有综合召回攀和精确率指标的f - m e a s u r e 和平分点b e p ( b r e a k - e v e n p o i n t ) 。 评价方法主要裔宏平均( 嬲扑8 v c 瑚i g e ) 、微平均( m i c r o - a v e r a g e ) 3 l 阅。 下磷详细介绍这些评价标准和评价方法。 1 查垒率与查对率、宏平均与微平均 妇渠穰表示溪l 试文程袋率本来耩于类捌e i 丽燕被分类器分类至类瘸 c i 的文档数，f p i 表示测试文档集中本来不属于类别c i 但却被分类器错误分 类到类聚c i 瓣文橙数，f n i 表示零采应该羼予类臻e i 翟被分类器分类蓟蘩 的类别的文档数，丽t n i 表示本来不属于类别c i 也没有被分类器分类到类 嚣南交遴大学矫究生攀位论文 第 页 裂c i 黪文搂数。 羽b 么，分类器在炭别c i 上的查全举( r e c a l l ) 定义如下： r e c a l l i ：翌!(2-1) 分类器农类别c i 上的查对率定义如下： p r e c i s i o n i 。婴f 2 。2 1 国以上的定义可以看出，庭全率就是一个文档d i 应该属于类掰c i ，而分 类器也确实将其分到类别c i 的概率，燕对率就是随机文档d i 被分类器分类 至类渤e i 丽艇这个分旋正确的概率。箱逻辑举的术语泉讲，蠢全率考察的是 分类器的完备性，而畿对率考察的是分类的正确性。 良上酶意义都是针对菜一个类爨c i 酶，所瑷这魏指标只髓代表简帮意 义。为了在全局意义上评价分类器，就必须考虑所有的类别。有两种方法来 缘合掰骞类溺豹查全攀帮查对率，帮宏平鸷( m a c r oa v e r a g i n g ) 弱徽平稳 ( m i c r o a v e r a g i n g ) 。若i c l 为类别总数和，它们的定义怒： 徽平鹭： m ；c a v g _ r e e a t t - 丽t p 2 京z 箫i c j t p 斋 ( 2 - 3 ) 宏警均： 舭埘鼬泌丽t p 2 京篆t c t t p 丽 m 瓣a v g 史穰l ；y , ：l i r e c a l l i (2。5，c 一 | i 、7 m a c a v gp r e c i s i o n 一篇p r e c i s i o n i 1cj ( 2 - 6 ) 西南交通大学研究生学位论文第1 2 页 微平均和宏平均有一个根本的不同，微平均给每个文档以相同的权重， 而宏平均是给每个类别以相同的权重。微平均和宏平均可能得到完全不同的 结果，特别是当文档集中类别的分布有较大的不同的时候。一般来说，微平 均较易受到大类的分类性能的影响，而由于宏平均是对全部类别取均值，故 相对较易受小类的影响。到底采用微平均还是宏平均方法来进行评价，主要 取决于应用需要。在本文中，因为训练文档集中属于每一类的文档数目是一 样的，我们使用了宏平均方法来进行评价，给每个类别以相同的权重。 除了查对率和查全率，还有一些不太常用的评价标准，如正确率，错误 率等。这里我们仅介绍常用的方法。 2 b e p 和f 1 上一小节所介绍的查全率和查对率，它们是有关联的。例如，某一个分 类器测试属于c i 类的文档的实际类别都是c i ，如果单纯地考虑查对率，这 个分类器的性能将很好，因为这时其查对率 p r e c i s i o n ；! ! ：旦l ：1 。r p i + f ? p i。17 p l + u 即，查对率是1 0 0 。但实际上，这时候的查全率可能很低，因为有可 能很多其他本来属于类别c i 的文本分类器并没有识别出来，这显然是不合理 的。所以需要有一种综合考虑，现在已经提出了很多方法，如e l e v e n - p o i n t a v e r a g ep r e c i s i o n ，b r e a k e v e np o i n t ，兄f u n c t i o n 等。常用的有b e p ( b r e a k e v e n p o i n t ) 和疋法。以下将简要介绍这两种方法。 b e p 就是使得查对率和查全率取得相等值的点1 2 0 。严格地来讲，b e p 的 计算是比较复杂的，为了便于计算，通常都采用查对率和查全率的算术平均 值来代替b e p 的值，即对于某一个类别c i ，定义为： b e p i ：r e c a l l i + = p r e c i s i o n i ( 2 - 7 ) 上 同样，对于b e p 有宏平均和微平均两种全局优化法。若l c l 为类别总数和， 定义如下： y ”i b e p i m a c a v g _ b e p2 鱼昔_ 一 ( 2 8 ) 蘸漆交通大学磷究生学位论文第 3 页 y ”i ( r e c a l l i + p r e c i s i o 掰) m i c a v 鼠。b e p = 皇熙n 芗一 ( 2 9 ) 磊醋数由v a nr 蘑s b c r g c n 在1 9 7 9 年首先提出使用嘲，综合考虑了查全 率和查对率两种指标，疋的定义为： 最；r(fl+1)recall*precision(2-10) jn 一_ 一 j 1p r e c 括i o n 七r e c a l l 其中0 + & ，可以看作是对查全率和套对率的相关度。当口= o 时，易就与查对率一致，当卢：+ & 时，易与查全搴一致。即芦耿值越大， 越强调蠢垒率豹重要性，反之列强调煮对率靛重要瞧。一般情提一f ，平鬻这 两个指标，驭声= l ，健它们的重要稚发福两，这时乃就为常露的曩。对予 类别c i ，旗f 1 定义为： 一 2 + r e c a l l + p r e e i s i o n l 。1 磊面磊磊面 犯一1 1 ) 同样对于f l 有宏平均和微平均两种全局化的方法，定义如下； m a c a v g _ f 1 ；等l c l f l i ( 2 m ) 毋器t c lr 磊蕊 * 而翥 。， 本文第五章酶实验巾，应用了查念率，查对率阪疑f 1 法对分嫌器进行性 能测试。 2 。2 向囊空闻模型 信息枪索的概念被掇出以后，出现了许多基于文档和查询之间的文本计 算模型，舆有代表性的肖布尔模型、向量空间模型、概率模型等。这些模型 获不嚣豹奔l 发窭发，使掰不蘑魏方法鲶骥簿薤燕权、类聚学习帮避强度诗葵 等问题。 上述几种模型中，向量空间模型v s m ( v e c t o rs p a c em o d e l ) 是最简便 有效的文本表示模型之。向量空间横型是s a l t o n 镣入予6 0 年代寒提出的， 鬻南交遴大学帮f 究玺学位论文第 4 页 著在麓名豹s m a r t ( s y s t e m f o rt h em a r f i p u l a f i o na n dr e t r i e v a lo f t e x t ) 系统 得到成功的臌用，从此以后，该模型殿其相关技术，包括项的选择、加权策 略，潋及采髑稳关反馈进行钱纯套谗镣在文零分类、爨凌索辱l 、壤惑梭索等 许多领域得到广泛的虑用。特别是随糟网络的迅速膨胀，还被广泛地成用到 搜索弓| 擎、令人售息代理、搠上毅闻发表等镶息检索镞域豹瘦援中，莠且取 得了较好的效果。 2 2 关予v s m 豹基本概念 瑗( t e r m ) ：文零豹内容黪薤豢碧羯它瑟含蠢夔基本语言肇位( 字，逮， 词组，或短语等) 来袭示，遮些基本的语言单位被统称为文本的项，即文本 可以用项集( t e r ml i s t ) 表承为d ( t bt 矿”t 。) ，其中乜是项，l = k = n ) 。 颁的权蘸( t e r mw e i g h t ) ：对于含有1 1 个项的文本d ( t ，t m t 。) ，项t 。 鬻常被赋予定的投燕w k ，表示它嬲在文零d 中的重要稷发，鄂d = d ( t 1 w i ；t 2 ，w 2 ；t n ，、) 吒) ，简记为d = d ( w l w 2 ；w 。) 。遮时我们说项 r 蛉投重为w k ，l k n 。 向量空闻模型( v s m ) ；给定一文本d = d ( t l ，w i ；t 2 ，w 2 ；t n ，、碥) ， 由于h 在文本中既可以重复蹬现又有先后次序的关系，分析起来仍寿定的 难度。为了简化分析，可戬暂时不考虑t k 在文档中的先后顺序并要求k 互 异。滋时可以把t l ，t 2 k 看成一个n 维的坐标系，丽w l ；w 2 ；眠为 相应的坐标德，因而d ( w i ；w 2 ；“) 被看成n 维窝闯中的个向薰。我 们称( w l ；w 2 ；w 。) 为文本d 的向量表示。 籀禽l 囊( s i m i l a r i t y ) ：两个文本移l 和d 2 之阉的内容稽关程度常常觜它 们之间的相似度s i m ( d l ，d 2 ) 1 3 2 来魔攫。当文本被表示为向量空间模型时， 我餐霹瑷蓿韵予向量之闯酶菜释距离来表示文举之闻的稽钕度，常用向麓之 间的内积进行计算： 且 s i m ( d 1 ，d 2 ) = + ( 2 一1 4 ) i # l 或者鬟爽燕余弦镳采表示，翔公式( 2 1 5 ) 帮霞2 t 搿示。 蹰南交通大学研究生学位论文 第1 5 页 s i m ( d l ，d 2 = c o s o = ，w t i ( 2 - 1 5 ) 圈2 1 文本的向爨空间模型( v s m ) 及文本问的相似度s i r e ( d 1 ，d 2