（计算机应用技术专业论文）基于构造性覆盖算法的中文文本分类.pdf

摘要 文本分类是文本挖掘的基础与核心，是近年来数据挖掘和网络挖掘的一个研 究热点，在传统的情报检索、网站索引体系结构的建立和w 曲信息检索等方面 占有重要地位。文本自动分类技术是自然语言处理的一个重要的应用领域，是替 代传统的繁杂人工分类方法的有效手段和必然趋势。特别是随着互联网技术的发 展，网络成为人们进行信息交互和处理的有效的平台，各种数字化的信息每天以 极高的速度增长。面对如此巨大的信息，人工分类选择已经无能为力，计算机自 动分类已成为网络时代的必然选择。 目前，对于文本分类技术的研究，大多数研究者的精力主要放在各种不同分 类方法的探索与改进上。然而，文本分类中的特征选择也一直是文本分类的关键 技术。因此，对特征选择算法的研究与不同分类算法的研究都是十分必要的。 本文所做的主要工作及创新点如下： 1 本文首先对当前文本分类领域几个关键问题的常用解决方法进行了研 究，然后着重介绍了一个基于构造性覆盖算法的中文文本分类系统( s t r u c t u r a l c o v e r i n ga l g o r i t h i n b a s e dc h i n e s et e x tc l a s s i f i c a t i o ns y s t e m , 简记为c c t c s ) ，重 点阐述了文本预处理、特征选择、维数约简和构造性覆盖算法及其改进等技术的 实现。 2 在c c t c s 中，第一步是利用中国科学院计算技术研究所提供的汉语词法 分析系统( i n s t i t u t eo fc o m p m i n gt e c h n o l o g y , c h i n e s el e x i c a la n a l y s i ss y s t e m 。 i c t c l a s ) 对中文文本进行汉语分词，去除虚词和形容词，只保留名词和动词； 再对文本进行预处理，删除文本中的停用词和稀疏词，可使文本维数平均压缩一 半，从而实现文本的粗降维。而c c t c s 需要解决的核心问题是特征的选择问题， 特征选择涉及选择哪些特征和选择的特征维数两个问题。针对上述问题，本文使 用信息增益( i n f o r m a t i o ng a i n , i g ) 与主成分分析( p r i n c i p l ec o m p o n e n ta n a l y s i s ， p c a ) 相结合的特征选择方法。 3 c c t c s 使用人工神经网络作为分类器，特征词的权重组成原始特征向量， 和神经网络输入层的神经元一一对应。在文本训练的时候，利用标记好的训练文 本集进行网络训练。而在文本分类的时候，输入待分类文本的特征向量，通过已 训练好的神经网络对文本进行分类，以确定文本的类别。 4 本系统采用构造性覆盖算法( 即交叉覆盖算法) 来设计神经网络分类器，首 先分析了一般的交叉覆盖算法( g e n e r i ca l t e r n a t i v ec o v e t i n ga l g o r i t h m ，g a c a ) ， 发现其存在一些不足之处，在分类过程中，可能会出现拒识和误判的现象，这将 大大影响系统的识别率和正确率。然后针对这些不足，对交叉覆盖算法做出相应 的改进，并给出其算法。实验证明，改进的交叉覆盖算法( i m p r o v e da l t e r n a t i v e c o v e r i n ga l g o r i t h m , i a c a ) 在整体性能上优于一般的交叉覆盖算法。这神改进的 算法不仅可以进步提高交叉覆盖算法的训练速度，而且可以减少拒识样本数， 提高识别的精度。 5 本文通过实验比较分析了不同特征选择方法与设计分类器的交叉覆盖算 法对分类性能的影响，证明了i g + p c a 的特征选择方法比直接使用i g 在基于交 叉覆盖算法的中文文本分类中具有其优越性，而且改进的交叉覆盖算法应用到中 文文本分类中在整体性能上优于一般的交叉覆盖算法，并得出利用交叉覆盖算法 设计的神经网络的特征输入维数在2 0 0 左右的时候分类性能最佳。 本文在中文文本分类方面已经完成了一些工作，今后可以在以下几方面作进 一步的研究： 1 本论文所有的结论都是在实验的条件下得出的，而实际应用效果如何可 以进一步在实际应用中进行验证。 2 可将本文提出的特征选择方法应用于英文文本分类中，并设计更网络化、 智能化、多功能化的分类系统，可以应用到如邮件过滤器或搜索引擎等热门实际 应用中去。 3 为了进一步提高本文方法的扩展性，可考虑分类别来作p c a ，然后寻找 各个类别的主成分( p r i n c i p l ec o m p o n e n t ，p c ) 的极大线性无关组来得到全局特征， 这是我们将来研究的一个重点。 关键词：神经网络；交叉覆盖算法：文本分类；特征选择；主成分分析； i i a b s t r a c t t e x tc l a s s i f i c a t i o ni st h eb a s i sa n dc o r eo ft e x tm i n i n g ，a n dp l a y sa ni m p o r t a n t r u l ei nt r a d i t i o n a li n f o r m a t i o nr e t r i e v a l ，c o n s t r u c t i o no fw e bs i t ea r c h i t e c t u r e ，a n d s e a r c hf o rw e bi n f o r m a t i o n i th a sb e c o m eah o tr e s e a r c hp r o j e c ti nr e c e n ty e a r s t e x t a u t o m a t i cc l a s s i f i c a t i o ni sa l li m p o r t a n ta p p l i c a t i o nf i e l do f n a t u r a ll a n g u a g ep r o c e s s ， a ne f f i c i e n tm e a n sa n dn e c e s s a r yt r e n dt os u b s t i t u t et h et r o u b l e dt r a d i t i o n a lm a n u a l c 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 tt e c h n o l o g y , t h en e t w o r k b e c o m e sa l le 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 dp r o c e s si n f o r m a t i o n , a n d d i g i t a li n f o r m a t i o ni n c r e a s e sd a i l yw i t hh i g hs p e e d f a c i n gs u c hag r e a td e a lo f i 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 t a 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 rt h es t u d yo ft e ma u t o m a t i cc l a s s i f i c a t i o nt 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 yf o c u s o 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 n a 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 ft e x tc l a s s i f i c a t i o nh a sa l w a y sb e e na k e yt 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 t h e r e f o r e ，i ti sn e c e s s a r yt os t u d yf e a t u r e s e l e c t i o na l g o r i t h m sa n dd i f f e r e n tc l a s s i f i c a t i o na l g o r i t h m s t h em a i n w o r kt h i sp a p e rf i n i s h e da n di t si n n o v a t i v ep o i n t sa r ea sf o l l o w s ： 1 a t 血毗t h et r a d i t i o n a ls o l u t i o n st os o m ek e yt e c h n i c a lp r o b l e m si nt h ef i e l do f t ca r es t u d i e d ，t h e nt h i sp a p e rp r e s e n t sa ns t r u c t u r a lc o v e r i n ga l g o r i t h m - b a s e d c h i n e s et e x tc l a s s i f i c a t i o ns y s t e m ( f o rs h o r t ，c c t c s ) a st h em a i nt o p i c s o m ek e y t e c h n i q u e si m p l e m e n t e di nt h i sc l a s s i f i e r , s u c ha st e x tp r e t r e a t m e n t , f e a t u r es e l e c t i o n ， d i m e n s i o nr e d u c t i o n , s t r u c t u r a lc o v e r i n ga l g o r i t h ma n di t si m p r o v e m e n ta l ed i s c u s s e d i nd e t a i l s 一 2 t h ef i r s ts t e pi nc c t c si sc h i n e s ew o r ds e g m e n t a t i o no nc h i n e s et e x t su s i n g c h i n e s el e x i c a la n a l y s i ss y s t e m ( i n s t i t u t eo fc o m p u t i n gt e c h n o l o g y , c h i n e s el e x i c a l a n a l y s i ss y s t 锄i c t c l a s ) p r o v i d e db yc h i n e s ea c a d e m yo fs c i e n c e si n s t i t u t eo f c o m p u t i n gt e c h n o l o g y , g e t t i n gr i do fe m p t yw o r d sa n da d j e c t i v e s ，o n l yr e s e r v i n g n o a n sa n dv e r b s ；t h e na f t e rt e x tp r e t r e a t m e n t , s t o p w o r d sa n dr a r e - w o r d sa r ed e l e t e d ， 1 1 1 s ot h a tt h ed i m e n s i o no ft e x t sc a l lb er e d u c e dt ot h eh a l fo na v e r a g ea n dc o a r s e d i m e n s i o nr e d u c t i o nc a nb er e a l i z e d h o w e v e r , t h em a i np r o b l e mo fc c t c si sf e a t u r e s e l e c t i o nf o rt e x t u a ld a t a f e a t u r es e l e c t i o ni n v o l v e sw h a tf e a t u r et os e l e c ta n dh o w l a r g et h ed i mo ft h ef e a t u r es p a c es h o u l db e a i m i n ga tt h ep r e c e d i n gp r o b l e m ，t h i s p a p e ru s e saf e a t u r es e l e c t i o nm e t h o du s i n gi n f o r m a t i o ng a i n ( i g ) a n dp r i n c i p l e c o m p o n e n ta n a l y s i s ( p e a ) 3 i nc c t c s ，w ei l s ea r t i f i c i a ln e u r a ln e t w o r k s ( a n n ) a st h ec l a s s i f i e r t h e r e c o r d e dt e r mw e i g h t sf o r mt h eo r i g i n a lf e a t u r ev e c t o r , m a t c h i n gw i t hn e u r o n si nt h e ， i n p u tl a y e ro f a n no n eb yo n e i nt h es t a g eo f t r a i n i n g ，c c t c sa p p l i e sl a b e l e dt e x t s t 0a n nf o rt r a i n i n g w h i l ei nt h es t a g eo ft e x tc l a s s i f y i n g c c t c si n p u t sf e a t u r e v e c t o r so f t h et e x tt ob ec l a s s i f i e d , t h e nt h et r a i n e da n n c l a s s i f yt h eu n l a b e l l e dt e x tt o j u d g ei t sc l a s s 4 t h i ss y s t e md e s i g n st h ea n nc l a s s i f i e ru s i n gs t r u c t u r a lc o v e r i n ga l g o r i t h m ( v i z a l t e r n a t i v ec o v e t i n ga l g o r i t h m ) ，a tf i r s t , i ta n a l y z e sg e n e r i ca l t e r n a t i v e c o v e r i n ga l g o r i t h m ( g a c a ) a n df i n d si t ss e v e r a ld i s a d v a n t a g e s i nt h ep r o c e s s i n g o fc l a s s i f y i n g ，r e f u s a lo fi d e n t i f i c a t i o na n dm i s c a r r i a g eo fj u s t i c ew i l lo g c r i , w h i c h w i l lg r e a t l yi n f l u e n c et h es y s t e m si d e n t i f i c a t i o na n dc o l t e c t n e s s s oi no r d e rt o o v e r c o m et h e s ed i s a d v a n t a g e s ，a l t e r n a t i v ec o v e r i n ga l g o r i t h mi si m p r o v e da n di t s d e t a i l e dp r o c e s si s p r e s e n t e d e x p e r i m e n t sp r o v et h a t t h e i m p r o v e da l t e r n a t i v e c o v e r i n ga l g o r i t h m ( i a c a ) i sb e t t e rt h a nt h eg e n e r i co n ei nt h ew h o l ec a p a b i l i t y t h i si m p r o v e da l g o r i t h mc a nn o to n l yi m p r o v et h et r a i n i n gs p e e do ft h ea l t e r n a t i v e c o v e r i n ga l g o r i t h m ，b u ta l s or e d u c et h en u m b e ro ft h et e s ts a m p l e st h a tc a n tb e c o v e r e db yt h es p h e r i c a ln e i g h b o r h o o dg a i n e db e f o r ea n di m p r o v et h ea c c u r a c yo f r e c o g n i t i o n 5 sp a p e rc o m p a r e sa n da n a l y z e st h ec l a s s i f i c a t i o np e r f o r m a n c eo fd i f f e r e n t f e a t u r es e l e c t i o nm e t h o d sa n dd i f f e r e n ta l t e r n a t i v ec o v e r i n ga l g o r i t h m sw h i c h d e s i g nt h ec l a s s i f i e ri nt h ee x p e r i m e n t s t h e r e f o r e ，i ti sp r o v e dt h a tt h ep r o p o s e d f e a t u r es e l e c t i o nm e t h o di g + p c af o rc h i n e s et e x tc l a s s i f i c a t i o nb a s e do na l t e r n a t i v e c o v e r i n ga l g o r i t h mi ss u p e r i o rt ot h em e t h o dt h a to n l yu s ei g a n di m p r o v e d a l t e r n a t i v ec o v e r i n ga l g o r i t h mi sb e t t e rt h a ng e n e r i ca l t e r n a t i v ec o v e r i n g i v a l g o r i t h mi nt h ew h o l ep e r f o r m a n c et h a ta p p l i e dt oc h i n e s e t e x tc l a s s i f i c a t i o n t h e e x p e r i m e n t sa l s os h o w t h a tt h er e r f o r m u n c eo f t h en nt h a td e s i g n e db ya l t e r n a t i v e c o v e r i n ga l g o r i t h mb e c o m e sh i g h e s tw h e nt h ef e a t u r ed i m i sa r o u n d2 0 0 - t h i sp a p e rh a sf i n i s h e ds o m ew o r ki nc h i n e s et e x tc l a s s i f i c a t i o n , w ec o u l dd o f u r t h e rr e s e a r c ho nt h ef o l l o w i n gs e v e r a la s p e c t si nf u t u r e 1 a l lt h i sp a p e r sc o n c l u s i o ni sg a i n e di nt h ec o n d i t i o no fe x p e r i m e n t a t i o n , a n d t h e nw ec o u l dv a l i d a t ei t sa p p l i e de f f e c t si nt h ep r a c t i c a la p p l i c a t i o n 2 。t h ef e a t u r es e l e c t i o na l g o r i t h mt h i sp a p e rp u t sf o r w a r dc 狃b ea p p l i e dt o e n g l i s ht e x tc l a s s i f i c a t i o n a n dw ec a l ld e s i g nm o r en e t w o r k e d , i n t e l l e c t u a l i z e d ， m u l t i f u n c t i o n a lc l a s s i f i c a t i o ns y s t e m ，a n dt h e na p p l yi tt ot h ep o pp r a c t i c a la p p l i c a t i o n s u c ha se m a l lp e r c o l a t o r , s e a r c he n g i n ea n ds oo i l 3 i no r d e rt oi m p r o v et h ee x p a n s i b i l i t yo f t h i sp a p e r sm e t h o d , w ec o u l d c o n s i d e rc l a s s i f y i n gt om a k ep r i n c i p l ec o m p o n e n ta n a l y s i s ，t h e nw ec o u l dl o o kf o r t h ep r i n c i p l ec o m p o n e n t ( p c ) si n f m i t el i n e a ri r r e s p e c t i v eg r o u po f e a c hs o r tt og a i n t h ew h o l ef e a t u r e t h i si sa n0 1 1 1 r e s e a r c he m p h a s e si nt h ef u t u r e k e y w o r d s ：n e u r a ln e t w o r k ( n n ) ；a l t e r n a a i v ec o v e r i n ga l g o r i t h m ；t e x t 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 ；p r i n c i p l ec o m p o n e n ta n a l y s i s ； v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得安徽大学或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 盘於 签字日期：2 0 0 7 年4 月2 2 日 学位论文版权使用授权书 本学位论文作者完全了解安徽大学有关保留、使用学位论文的规定，有 吖 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 c 阅。本人授权安徽大学可以将学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：叠癜 签字日期：2 0 0 7 年4 月2 2 日 学位论文作者毕业去向： z - 作单位： 通讯地址： 导师签名： u 。 签字日期：2 0 0 7 年4 月23 日 电话： 邮编： 第一章绪论 1 1 问题提出 第一章绪论 在过去十几年中，由于以电子文本不断增加，以及苯望可以通过多釉灵活的 方式访问它们的需求，使得那些基于内容的文本管理任务在信息系统领域取得越 来越突出的地位。随着国际互联网和企业内部互联网的飞速发展，各种电子文本 数据的急剧增加，如何快速有效地获取、管理和使用这些文本数据，已经成为信 息系统学科迫切需要解决的重要问题。 文本分类( t e x tc a t e g o r i z a t i o n 或t e x tc l a s s i f i c a t i o n ，缩写为t c ) 就是一种文本 管理的任务，它是根据给定文本的内容，将其归属为事先确定的若干个文本类别 中的某一类或某几类的过程。这里所指的文本可以是媒体新闻、科技报告、电子 邮件、技术专利、网页、书籍或其中的一部分。文本分类问题关注的文本种类， 最常见的是文本所涉及的主题或话题，也可以是文本的文体风格，或文本与其他 事物之间的联系。 1 2 研究背景和研究现状 文本分类处理的研究是计算机、信息处理领域的重要内容，特别是随着网络 技术的快速发展，这种应用也变得更加迫切。自动文本分类技术的研究最早可追 溯到2 0 世纪6 0 年代的m a r o n i l 】的研究工作，从那时起，该技术便逐渐应用到信 息检索、文档组织、文档过滤等方面；1 9 7 0 年，s a l o n 等人提出了向量空间模型 s m ，v e c t o rs p a c em o d d ) 模型，由于该模型在良好的统计学方法基础上简明地 实现了对文本特性的抽象描述，从而成为文本分类处理的一种经典模型；到8 0 年代末，在文本分类领域，基于知识工程的方法一直占主导地位，其中最著名的 是c o n s t r u e 川系统，虽然该方法取得了较好的分类效果，然而该方法具有分 类规则制定困难、推广性差的缺点，很准大规模推广应用：进入9 0 年代以来， 随着互联网技术的快速发展，文本自动分类的研究也进入了一个新的阶段，各种 分类方法相继得到了发展，包括机器学习技术为主的信息分类技术逐渐取代了基 基于交叉覆盖算法的中文文本分娄 于知识工程的方法，成为文本自动分类研究的主要形式，如n a i v eb a y e s 、d e c i s i o n t r e e 、神经网络等等【3 1 ，1 9 9 8 年d o r t m u n d 大学的t j o a c h i m s t j 探讨了支持向量 机( s v m ) 方法进行文本分类，取得了很好的效果。此外，一些学者还采用 b o o s t i n g 8 方法来探讨提高分类处理的方法。国内，许多研究院所也对中文信息 分类技术进行了大量的研究 9 - 1 】，在具体分类算法上与国外是相同的，只是由于 中文的词与词之阈没有明显的分割，因此需要进行切词处理。 文本分类的历史可以追溯到6 0 年代，但是直到9 0 年代早期才成为信息系统 学科中的一个主要分支，这要归功于不断增加的应用需要和硬件的发展。文本分 类现在被应用在很多方面，包括信息检索，自动标引，文本过滤，自动文摘，机 器翻译，邮件分类，词义排歧和网页的分级归类等。 文本分类现在是机器学习和信息检索之间的交叉学科，并且与文本信息提取 和文本挖掘这些领域相通，目前为止这些学科之间确切的分界点在哪里仍然分歧 很大。而文本挖掘的概念越来越广泛地应用在分析大数据量的文本，发现其中有 用的模式，提取其中有用的信息上面。根据这个观点，文本分类可以算作文本挖 掘的一个应用实例。 文本自动分类技术是自然语言处理的一个重要的应用领域，是替代传统的繁 杂人工分类方法的有效手段和必然趋势，特别是随着互联网技术的发展，网络成 为人们进行信息交互和处理的最有效的平台，各种数字化的信息每天以极高的速 度增长，面对如此巨大的信息，人工分类选择已经无能为力，计算机自动分类已 成为网络时代的必然选择。通过利用先进的计算机技术、人工智能技术，不仅可 以实现方便快捷的分类效果，节省大量的人力物力，并且可以进一步进行更深层 次的信息挖掘处理，提高信息的利用效率。 1 3 研究目的 目前对于文本分类技术的研究，大多数研究者的精力主要放在各种不同分类 的方法探索与改进上。然而，文本分类中特征选择也一直是文本分类的关键技术 和瓶颈技术。所以，对特征选择算法的研究和不同分类算法的探索和改进都是十 分必要的。 随着网络的发展，在线文档爆炸式增加，对文本分类提出了更高的要求。对 第一牵绪论 特征空间进行降维，也就是特征选择算法，是文本分类的关键技术。文本的原始 特征的数量可能很大，或者说样本处于一个高维空间中，构成文本的词汇，数量 是相当大的，因此，表示文本的向量空间的维数也相当大，可以达到几万维。因 此，我们需要进行维数压缩的工作，这样做的目的有两个：第一，为了提高程序 的效率，提高运行速度，第二，所有几万个词汇对文本分类的意义是不同的：一 些通用的，各个类别都普遍存在的词汇对分类的贡献小：两在某特定类中出现频 率大而在其他类中出现频率小的词汇对文本分类的贡献大。为了提高分类精度， 对于每类，我们应去除那些表现力不强的词汇，筛选出针对该类的特征项集合。 通过映射( 或变换) 的方法可以用低维空间来表示样本，再从一组特征中挑选出 些最有效的以达到降低特征空间维数的目的这就是特征选择的目的。设计出 好的高精确度的特征选择算法来，可以减少人力、物力，大大地提高分类效率。 1 4 本论文的研究内容 本论文对文本分类中所涉及的各项技术进行了较全面的阐述，特别对当前文 本分类中各种常用特征选择算法的性能以及优缺点进行了分析，提出了一种新的 特征选择算法，即信息增益i g 和主成分分析p c a 相结合的特征选择方法，然后 以神经网络作为分类器，对设计神经网络的交叉覆盖算法进行详细分析，针对其 几个缺点，做出相应改进，提出了一种改进的交叉覆盖算法，并以此为基础设计 了一个中文文本分类系统。通过实验对其性能进行了测试： 首先对比该特征选择算法与传统的特征选择算法，结合应用到分类系统上的 性能，确定该方法的可行性以及该特征选择算法的优越性；然后对比了该分类系 统在不同原始特征空间维数下的分类性能；利用本文提出的特征选择方法，对比 了改进的交叉覆盖算法和一般交叉覆盖算法的分类性能，对测试结果进行了理论 分析，确定了改进的交叉覆盖算法能够在一定程度上提高分类系统的性能，证明 改进算法的有效性和优越性。最后，本文通过对上述实现技术的阐述及其对实验 结果的分析，提出了一些关于文本分类及特征选择算法研究的见解，并对今后的 研究工作进行了展望。 基于交叉覆盖算法的中文文本分类 1 5 本论文的结构安排 本论文的各章节的内容安排如下： 第一章绪论首先提出了闯题，然后介绍了文本分类的研究背景、研究现状和 研究目的，以及本论文研究的主要内容和结构安排。 第二章讲述了本论文设计的基础知识及文本分类领域中涉及到的几个关键 问题的常用解决方法，包括文本分类的基本概念和基本过程、文本表示、文本特 征的选择方法及不同方法的优缺点比较和文本分类的常用算法等。 第三章详细介绍了所设计的一个基于交叉覆盖算法的中文文本分类系统，包 括系统的整体结构、预处理、特征选择、特征抽取、训练算法、分类算法等各部 分的具体实现步骤。 第四章对系统进行实验设计，然后详细讨论该分类系统在各种不同参数和条 件下的性能，并对实验结果做出详细分析。 第五章是结束语，对本论文所做工作进行了总结和展望。 1 6 本章小结 本章首先提出了进行文本分类的必要性和文本分类的概念，并对文本分类 的研究背景、研究现状和研究目的做了系统地介绍，然后简要概括了本论文的主 要研究内容和结构安排。 4 第二章文奉分类辨定义、关建技术方法及应用 第二章文本分类的定义、关键技术方法及 应用 2 1 文本分类的定义 简单地说，文本分类系统的任务是：在给定的分类体系下，根据文本的内容 自动地确定文本所属的类别。从数学角度来看，文本分类是一个映射的过程，它 将未标明类别的文本映射到已有的类别中，该映射可以是一映射，也可以是 对多的跃射，因为通常一篇文本可以同多个类别相关联。用数学公式表示如下： f a b其中，a 为待分类的文本集合，b 为分类体系中的类别集合。 文本分类的映射规则是系统根据已经掌握的每类若干样本的数据信息，总结 出分类的规律性而建立的判别公式和判别规则。然后在遇到新文本时，根据总结 出的判别规则，确定文本相关的类别。 2 2 文本分类的基本过程 对于一般的模式识别系统，主要由4 个部分组成：数据获取，预处理，特征 提取和分类决策。而对于文本分类这样特定的模式识别系统，初始的数据是所给 定的电子文本，数据获取的过程可以省略掉。预处理的目的是去除噪声，加强有 用的信息，并且为后面的特征提取做准备。为了有效地实现分类识别，就要对原 始数据进行变换，得到最能反映分类本质的特征，这就是特征提取的过程，一般 把特征提取之后得到的分类识别赖以进行的空间叫特征空间，在文本分类中特征 空间大多是采用文本中的关键词来表示。分类决策就是在特征空间中用统计方法 把被识别对象归为某一类别。基本做法是在样本训练集基础上确定某个判决规 则，使按这种判决规则对被识别对象进行分类所造成的错误识别率最小或引起的 损失最小。在这里，我们还根据文本分类系统实际需要在特征提取之后加上一个 特征向量再处理的环节，实现对特征空间的降维。这样的文本分类过程如图2 1 所示。 基于交叉覆盖算法的中文文本分类 训练过程 图2 - 1 文本分类的过程 f i g 2 - 1 t h ep r o c e s so ft e x tc l a s s i f i c a t i o n 2 2 1 文本的预处理 分类过程 中文文本信息处理和欧洲语言信息处理的一个最大的区别就在于中文被写 成连续的字串，词与词之间没有显式的界限，而欧洲语言句子的词与词之间有空 格。所以我们必须对文本进行预处理，确定好特征项类型，即基于什么类型的特 征去分类，常见的特征项类型有字、字串、词、短语等。现有的研究认为以词为 单位来进行处理比较合理【，所以我们通常以词作为特征单位的类型。另外， 对于中文文本而言，切分词的方法主要有基于字符串匹配的方法、基于理解的方 法和基于统计的方法。对于中文文本，还需要进行词性标注、短语识别。 文本预处理一般通用的做法有： ( 1 ) 停用词表 将一些在文本中出现频率高但是含义虚泛的词放入停用词表。例如在英语中 的a ，r n ，t h e ，t h i s ，f o r ，a t ，0 1 1 ，中文中的“的，得，地，这，尽管，但是”等， 保证出现在停用词表中的词不能选作文本特征。 ( 2 ) 稀疏词处理 有些词条在整个文本集中出现的频率都很低，它们也不适合作为文本的特征 项。通过对文本集进行词条频率统计并设计一个词频阈值，只要是词条频度低于 6 第二章文本分类的定义、关键技术方法及应用 这个词频阈值的词就被删除。 ( 3 ) 单词归并 把表达形式不同而含义相同的或是含义相似的词作为同一个词条处理。如英 文中的f o o t b a l l 和s o c c e r ，中文的“电脑”和“计算机”等。 ( 4 ) 同根词处理 在英文中，还可以进行s t r i ph e a d e f 和s 。i 垃n g 的操作来对文本进彳亍初始化。 例如：t a l k e r ，t a j k i n g ，t a l k e d ，它们同属于一个词根t a l k 。 2 2 2 文本表示 文本特征指的是关于文本的元数据，分为描述性特征( 如文本的名称，大小， 类型，日期等) 和语义性特征( 如文本的作者，标题，内容等) 。描述性特征容易获 得，而语义性特征较难得到。 对于内容这个难以表示的特征，我们首先要找到一种能被计算机所处理的表 示方法。计算机不具有人类的智能，人在阅读文章后，根据自身的理解能力可以 产生对文章内容的模糊认识，而计算机并不能轻易地“读懂”文章，从根本上说， 它只认识0 和1 ，所以必须将文本转换为计算机可以识别的格式。根据“贝叶斯 假设”。假定组成文本的字或词在确定文本类别的作用上相互独立，这样，可以 就使用文本中出现的字或词的集合来代替文本，不言而喻，这将丢失大量关于文 章内容的信息，但是这种假设可以使文本的表示_ 和处理形式化，并且可以在文本 分类中取得较好的效果。向量空间模型c v s m ) 是近年来应用较多且效果较好的方 法之- - 1 1 3 】。 向量空间模型采用简洁的特征矢量来表示文本，在进行特征提取时，不使用 大量的句法语法信息，也无需对文本进行复杂的自然语言处理和语义处理，这样 不仅可以对大量文本的集合进行快速处理，并保证许多应用中的时间复杂性要 求，而且不依赖于某个特定领域。 在向量空间模型中，文本空间被看作是由一组正交特征向量所形成的向量空 间，每个文本d 被看作是向量空间中的一点，表示为向量空间中的个向量： v ( a ) = ( ( ，) ，( f ：，心) ，以，w d )( 2 一1 ) 其中，为特征项，m 为在d 中的权值。 7 基于交叉覆盖算法豹中文文本分类 可以将d 中的字或词作为，也可以要求是d 中出现的短语，从而提高内 容表示的准确性。一般定义为f ，在d 中出现频率矿的函数，即 啡一妒( 彰)( 2 2 ) 那么选取什么作为特征项呢，一般可以选择字、词或词组，根据实验结果， 普遍认为选取词作为特征项要优于字和词组，因此，要将文本表示为向量空阃中 的一个向量，就首先要将文本分词，由这些词作为向量的维数来表示文本，最初 的向量表示完全是0 、l 形式，即，如果文本中出现了该词，那么该文本向量的 维为1 ，否则为0 。这种方法无法体现这个词在文本中的作用程度，所以逐渐0 、 l 被更精确的词频代替，词频分为绝对词频和相对词频，绝对词频，即使用词在 文本中出现的频率表示文本，相对词频为归一化的词频，其计算方法主要运用 i t i d f 公式，目前存在多种t f i d f 公式，一种比较普遍的t f i d f 公式【1 4 1 ： ( f ，孑) 焉丝尘堕些訾( 2 - 3 ) 芝商渺( f ，d ) x l o g ( n n , + o 0 1 ) 】2 其中，w ( t ，d ) 为词r 在文本d 中的权重，而们，力为词t 在文本d 中的词频。 为训练文本的总数，珥为训练文本集中出现f 的文本数，分母为归化因子。 文本经预处理后进行统计词频，最终表示为上面描述的向量。完成词频统计 后，进行文本粗降维，去掉噪声文本和词频很高或者很低的垃圾数据，例如一些 没有实际意义的功能词。 除了向量空间模型外，d u m a i s ，f u r n a s ，l a n d a v e r 和h 盯s h m 肌【1 5 1 - 于1 9 9 0 年提 出隐性语义索；t ( l s i 模型，b e i k i l l 和c r o f f 1 句子1 9 9 2 年提出概率模型。 2 2 3 维数约简 经过以上步骤，得到的特征向量的维数是非常高的，如此高维的特征对即将 进行的分类学习未必全是重要，有益的，而且高维的特征会大大增加机器的学习 时间而产生与小得多的特征子集相关的学习分类结果。另外在不同内容