（应用数学专业论文）基于自然语言处理与非负矩阵分解的中文文本分类研究.pdf

摘要中文文本自动分类就是根据待判文本的内容，让计算机自动将其判别为预先定义好的若干类别中的某一类或者是某几类的过程，它是中文自然语言处理中的一个重要研究方向，有着极其重要的现实意义。中文文本分类的难点就是文本经向量空间模型表示后，特征空间维数很高，这样一方面会增加文本分类的计算复杂度，导致分类时间过长，另一方面这些特征中可能含有冗余特征，导致分类精度降低。另外，在选择“词”作为文本表示的特征项时，分词的精度对分类效果有着一定的影响，而目前的分词系统中存在着分词词典过于陈旧、领域相关性过强的缺点，会直接影响分词精度而导致不满意的文本分类效果。针对以上两个问题，本文提出了基于自然语言处理与非负矩阵分解的中文文本分类算法。针对目前分词词典过于陈旧、领域相关性过强的缺点，提出了基于统计的用户词典生成算法，该算法首先对最新的大规模语料库进行分词，然后利用新词发现算法，经过适当人工干预，形成一个只包含新词的用户词典，在分词时，与原词典采用一体化方法来提高分词精度。针对中文文本分类中特征空间维数较高的问题，结合非负矩阵分解的独特优点分解结果的非负性，提出了基于非负矩阵分解的中文文本分类算法。分类时，首先利用非负矩阵分解方法进行特征提取，然后进行分类识别。对上述算法，本文从四个方面进行了比较实验，实验结果表明，上述算法提高了文本分类的f 值，证实了所提算法的有效性，文章最后设计并实现了一个中文文本自动分类系统。关键词：文本分类；自然语言处理；用户词典；非负矩阵分解；特征提取a b s t r a c tu s i n gc o m p u t e rt e c h n o l o g y , b a s e do nt e x tc o n t e n t ，a u t o m a t i ct e x tc a t e g o r i z a t i o ni sap r o c e s st h a to r g a n i z e st h et e x ti n t oac e r t a i nc l a s so rs e v e r a lc l a s s e s i ti sa ni m p o r t a n ti s s u ei nn a t u r a ll a n g u a g ep r o c e s s i n g ( n l p ) a n ds i g n i f i c a n ti np r a c t i c a l h i g hd i m e n s i o n a lf e a t u r es p a c ei so n eo fd i 衔c u l t i e si nt e x tc a t e g o r i z a t i o nw h i l et e x t sw e r er e p r e s e n t e db yv e c t o rs p a c em o d e l ( v s m ) t h i ss i t u a t i o ni n e v i t a b l yi n c r e a s e sc o m p u t a t i o nc o m p l e x i t ya n d1 c a d st ol o n gc l a s s i f i c a t i o nt i m e ，a n do nt h eo t h e rh a n dt h e s ef e a t u r e sm a yc o n t a i nr e d u n d a n tf e a t u r e sw h i c hm a yr e d u c et h ec l a s s i f i c a t i o na c c u r a c y i na d d i t i o n ，w h i l ec h o o s e “w o r d s ”a si t e r nt oe x p r e s st e x t ，s e g m e n t a t i o na c c u r a c yh a sac e r t a i ni m p a c to nc l a s s i f i c a t i o n ，s o ，t h es h o r t c o m i n go fc u r r e n tc h i n e s ew b r ds e g m e n t a t i o n ：t h el e x i c o ni so u t m o d e da n dd o m a i ns p e c i f i c w i l la f f e c ts e g m e n t a t i o na c c u r a c ya n dl e a dt ou n s a t i s f i e dc l a s s i f i c a t i o ne f f e c t t oa t t a c kt h ea b o v et w op r o b l e m s ，i nt h i sp a p e r , w ep r o p o s eac h i n e s et e x tc a t e g o r i z i n ga l g o r i t h mb a s e do nn l pa n dn o n n e g a t i v em a t r i xf a c t o r i z a t i o n ( n m f ) i nv i e wo ft h es h o r t c o m i n go fc u r r e n tc h i n e s e 纬6 r ds e g m e n t a t i o n ：t h el e x i c o ni so u t m o d e da n dd o m a i ns p e c i f i c 。w ep r o p o s es t a t i s t i c - b a s e du s e rl e x i c o ng e n e r a t i o na l g o r i t h m ，f i r s t l y , s e g m e n tt h el a r g e - s c a l ec o r p u s ，a n dt h e nu s i n gn e ww o r d sd e t e c t i o na l g o r i t h m f i n a l l y , f o r mau s e rl e x i c o nt h a to n l yc o n t a i n sn e ww o r d sa f t e ra p p r o p r i a t em a n n a li n t e r v e n t i o n ，w h e ns e g m e n t a t i o n ，u s ei n t e g r a t i o na p p r o a c hw i t ht h eo r i g i n a ll e x i c o nt oi m p r o v es e g m e n t a t i o na c c u r a c y i nv i e wo fh i g hd i m e n s i o n a lf e a t u r es p a c e ，c o m b i n e dw i t ht h eu n i q u ea d v a n t a g eo fn m f ：n o n n e g a t i v ed e c o m p o s i t i o nr e s u l t s w ep r o p o s ec h i n e s et e x tc a t e g o r i z a t i o na l g o r i t h mb a s e do nn m f w h e nc l a s s i f i c a t i o n , e x t r a c t sf e a t u r e sf i r s t l yu s i n gn m f a n dt h e n ，c l a s s i f i c a t i o n t ov e r i f yt h ec a p a b i l i t yo ft h ep r o p o s e dm e t h o d ，w ed oc o m p a r a t i v ee x p e r i m e n t si nf o u ra s p e c t s e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep r o p o s e dm e t h o di m p r o v eev a l u eo ft e x tc a t e g o r i z a t i o n i nt h el a s ts e c t i o no fp a p e r , w ed e s i g na n di m p l e m e n tac h i n e s ea u t o m a t i ct e x tc a t e g o r i z i n gs y s t e m k e y w o r d s ：t e x tc a t e g o r i z a t i o n ；n l p ；u s e rd i c t i o n a r y ；n m f ；f e a t u r ee x t r a c t i o n独创性声明本人声明，所呈交的论文是本人在导师指导下进行的研究- t 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。关于论文使用授权的说明本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权保留、送交论文的复印件，允许论义被查阅和借阅；学校可以公布论义的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。( 保密的论文在解密后应遵守此规定)一橛蝴签名形孓吝刁。武汉理丁大学硕十学位论文第1 章绪论1 1 文本分类的研究背景随着互联网的快速发展，电子文本的数据量正在呈指数级增加，如何快速有效地获取、使用和管理这些文本数据，已成为困扰每个人的一个重要问题。作为解决这些问题的基本方法之一，结合文本内容，利用计算机技术的文本自动分类在近十年来引起了学者的普遍关注，得到了窄前的发展【l j 。文本分类( t e x tc l a s s i f i c a t i o n 或t e x tc a t e g o r i z a t i o n ，t c ) 是根据给定文本的内容，将其判别为事先确定的若干文本类别中的一类或多类的过程川【2 j 。这里的文本可以是网页、书籍、媒体新闻、电子邮件等，甚至可以是任何内容的电子文本。文本分类首先关注的是文本的种类，最常见的是文本所涉及的话题( 如军事、计算机、旅游、教育等) ，也可以是文本的风格( 如婉约、豪放等) ，或文本与其它事物( 如成人网页或垃圾邮件等) 之问的关联( 相关或不相关) 【i 】。迄今为止，无论是个人电子文档的整理还足国际专利文献的分类，通常都离不开人的直接参与，可以说绝大多部分的文本分类工作还是由人的脑力劳动来完成的。但是，人工文本分类方式已远远不能满足当今信息高速发展的需要，特别是海量数据处理，必须借助于计算机技术，研制专门的算法来实现。因此，研究高效的文本自动分类技术，研制快速、准确的文本自动分类系统，就显得日趋的重要和紧迫。文本自动分类就足结合给定文本的内容，利用计算机技术实现的自动的文本分类。具体地说，文本自动分类就是在给定的分类模型下，依据文本的内容让计算机自动判断文本类别的过程川，这些文本可以是新闻、电子邮件、科技报告、各种单据、甚至可以是任何电子文档。文本分类，在数学 二来看，其实就是一个映射过程，它将未知类别的文本映射到事前确定的类别中，并且这种映射可以是一对一的，也可以是- 1 对多的。下面给出文本分类的数学语言描述：对于每个 d c ( 其中d ，是文档集d 中的一篇文档，c = c l ，c 2 ，c 。 是事前确定的类别集) ，判定其布尔值，如为真( t r u e ) ，则d ，q ，否则d ，萑c f 。分类模型的作用就是构造映射函数：缈：d c - - ) t ，f ) ，其中丁表示真( d ，c ，) ，表示假( d ，萑a ) 。武汉理下人学硕十学位论文1 2 文本分类的研究意义l 、冗余过滤在搜索引擎和数字图书馆的建设中，如果不对采集的数据进行必要的控制，很可能会导致数据库中包含大量的冗余文档。这里的冗余文档丰要有两种类型：一种是重复文档，他们的内容完全相同，只是文件的存储位置、创建和修改的时问或者文件格式不同而已。虽然搜索引擎都已具备过滤重复文档的功能。但这种情况在我们使用搜索引擎时仍旧很常见，特别是当检索的结果数量较少时。另一种是近似( n e a r - r e p l i c a s ) 文档，它们只作了细微的改动。采用文本分类技术可以很好的解决这种问题，可以设定一个阈值，如果两篇文档的相似度超过了阈值，就可以认为它们是冗余的，冗余过滤的正确率一般都比较高，大约为9 5 ，其中的关键问题是过滤速度【lj 。2 、信息组织信息的有效、合理的组织是门户网站面临的一个常见问题，图1 1 和1 2 分别是搜狐网站和雅虎网站的新闻导航条，点击不同的新闻主题，用户可以查看该主题下各新闻标题。那么各个网站是如何将不同的文章分门别类的将其整理到彳i 同的主题下呢?簌圜军摹公整典霪爱姨捧胃翔默审缝s 戆经i 黝艘粟基金1 1 i 数码芋极_ 淳i受气雯入囊人霉嬖壤麋口艺喁藏耱黧窑露糖貔谖两旬馕焉变纯簇剑鑫患谈彀胃图1 1 搜狐网站新闻导航条固瓷滠黔经房产汽车娱乐绺青奥运嗣空闻撵鬻博客群组论坛氅点知识图1 - 2 雅虎网站新闻导航条当然可以使用人工的方式，人为判断文章属于哪，。类主题，但是这会浪费大量的入力、物力，而且人在长时间血对枯燥的文本数据时，极其容易疲倦而出错，再者人的处理速度是有限的。因此，采用文本自动分类技术来辅助网络信息资源的组织和管理，不仅可以节省大量的人力，而且能够管理更多的资源。同样自动信息组织在数字图书馆建设中也有着很强的需求。2武汉理工大学硕士学位论文3 、智能检索以现有的非常著名的搜索引擎为例，比如g o o g l e 、b a i d u 以及s o g o u 等，尽管它们的检索能力已非常强大但并非所有的问题都已经解决i l ”。“想查的东西查不到，不相关的东西倒是很多。”这是大家使用搜索引擎时都有过的体会。即使搜索相同的内容，各个搜索引擎的返回结果也不尽相同图l 3 和1 - 4 分别显示了用户输入“武汉香格里拉”后b a i d u 和g o o g l e 的搜索结果，在这个搜索结果中g o o g k 的结果可能更符台用广的需求。冈此，在构建搜索引擎的过程中，可以利用文本分类技术来区别概念，改进相关度计算方法，提高搜索的有效性。蜘l i l l 面鲤蛰谨醚魁窿交汉看1 i 重担一盔皿苤弛醒主盘里撞燃新兄毒l 做饭口 十十* 敝一黼i 而m m t * # * 一x 目脯口* * 最7 誊* l 拉疆g t r 轴i b 务饥s 培目$ # | ”# 乐冉n # 糠b & 蕾* * ! m el 培# n m j n j 女gw w h a “ l a l l ，c 【m p _ r 1y ，山h n ，s h 州3 k 黼b 6 直直立坚或选查擅里趁点正直盛喳担讧上垴目畦塞丝擅鹰亟监a 匠盘g 目m # 孙h ，t 辅辑e r 麓2 1 0 8 _ 9 - 4 确粤“十g m l陶1 3b a i d u 搜索结果( , 二0 0 8 1 c 篇嚣o 丽百丽沛告慕晋口醯“2 腿o mr 月o m * 十j n o 十目n i i 一一煎逸量控里擅盘醯t a e a 口t r m 枷t # i #g ，口= * )0 2 78 8 毯墼盘主薹盟勰麓鬻麓躺鸳器登蕊。惶。+ 。一。；。周1 - 4g o o g l e 搜索结果武汉理工大学硕士学位论文1 3 文本分类的研究历史与现状国外在文本分类领域的研究起步较早，且研究上的水平也普遍较高，如斯坦福、c m u 等，这与其整体学术氛围与教育体制不无关系。国内的主要研究单位有中科院计算所、东北大学、北京大学、上海复旦人学、哈尔滨工业人学等，但是，它们的研究工作主要是将国外的方法应用到中文文本分类技术上。到目前为止，国外在文本自动分类方面的研究过程，大致可以分为三个阶段【 1 ：第一阶段( 1 9 5 8 年1 9 6 4 年) 主要进行文本自动分类的可行性论证与研究。第二阶段( 1 9 6 5 年1 9 7 4 年) 进行文本自动分类的试验性研究。第三阶段( 1 9 7 5年至今) 进入实用化阶段，并在信息组织、信息过滤、邮件分类、电子会议等方面取得比较广泛的应用，其中较为成功的系统有卡内摹集团为路透社开发的c o n s t r u e 系统，麻省理工学院( m i t ) 为白宫开发的邮件分类系统等【l j 。我国文本分类的研究工作起步较晚，始于2 0 世纪8 0 年代，研究过程，大体上可以分为三个阶段：可行性探讨一辅助分类一自动分类。总的来说，我国的文本分类研究水平还比较低，主要处在试验研究阶段，正确分类率约为6 0 9 0 ，当然也在逐渐地向实用性、商、业化的软件应用靠拢，并且已经开发了一批自动分类系统。例如，清华大学吴军研制的自动分类系统、广州西风公司研制开发的西风文本自动分类系统。目前的中文自动分类技术绝大多数都用到向量空间模型，这是文本分类中的一个经典模型，其中使用较多的并且比较成熟的技术主要有基于统计学的自动分类技术和基于人工智能的自动分类技术。例如：智多星中文文本分类器，采用基于k n n 原理的v s m 分类方法。所有测试文档为复咀新闻语料集，按照中图分类法分成3 8 个大类，分类正确率为：封闭测试9 0 ，开放测试8 4 。采用基于聚类粒度原理的v s m 分类方法，以聚类指导分类，性能得到了改善，分类正确率为：封闭测试9 9 8 ，开放测试8 5 1 2 。北京工业大学计算机学院人工智能与知识工程实验室开发的个性化邮什分类系统采用了五种不同的特征提取方法及三种不| 一的分类器，在应用中可以根据实际情况选择不同的组合，以达到最佳的分类效果。该系统的准确率约为8 5 。总而言之，文本分类技术在国内的研究还处于一个较为前沿的领域。研究的方法相对也比较单一，主要足基丁向量空间模型的文本相似性比较，使用的文本特征也只停留在语法级别，没有上升到语义一级，主要为词或n 。g r a m 项。但是，使用词作为文本特征时，有一个关键的问题是如何识别新词和提高分词4武汉理工大学硕士学位论文的准确性这同时又是自然语言处理中的一个研究难点。另外，由于中文构词能力报强在进行中文文本分类时提取的特征往往成千上万，如何对这些特征进行有效的降维也是研究的重点。非负矩阵分解( n o n - n c g a d v ei v l a n _ ；xf a c t o r i z a t i o n ，n m f ) 由d d l e o 和hss e u n g 在1 9 9 9 年提出，n m f 不同于一般的矩阵分解方法它是在矩阵中所有元素均为非负数约求之下的矩阵分解方法。正是这种非负性体现了人类思维中“局部构成整体”的观念( 如下图1 5 所示) ，并且非负矩阵分解具有报多优点诸柚：实现的简单性、结果的可解释性空间的低占有率等。非负矩阵分解是人粪处理海量数据的一种新途径，目前除了应用在模式分类、图像处理、维数压缩等领域外，该方法在文本处理( 文本聚类、文本分类) 领域也有一定的应用。为了更直观的理解n m f ，奉文在这里举了一个n m f 在人脸识别中的例子米说明，图1 - 5 显示了n m f 的人脸分解基，从圈中可咀看出不同的萋突出了人脸的不| 司部位，体现了“局部构成整体”的思想。口困；目图1 - 5n m f 的人脸分解基嘲与文本分类中常用的两种矩阵分解方法主成分分析( p c a ) 和有监督主成分分析( s u p e r v i s e d p c a ，s p c a ) 相比非负矩阵分解由于其分解结果的非负性。具有直观的可解释性，更适合实际情况，文本中的词频不会是负的，分解结果理应不舍有负值，而p c a 和s p c a 分解结果出现了负值，解释不通。非负性，即各特征值的加权组台为“加法”，体现了词语组台构成文章的过程，而特征值的“减法”加权在文章构成中是解释不通的不具实际意义。基于此，本文提出了基于非负矩阵分解的中文文本分类算法，用非负矩阵分解方法来进行特征提取。武汉理r t 大学硕十学位论文1 4 本文的主要工作本文主要做了以下四个方面的工作：1 、总结和概述了中文文本自动分类的总体框架及各步骤的研究方法。2 、通过对中文自动分词算法的研究，提出了基于统计的用户词典生成算法。3 、提出了基于非负矩阵分解的中文文本自动分类算法。4 、设计和实现了一个中文文本自动分类系统。1 5 各章内容简介本文共分6 章，各章节的内容简介如下：第l 章：首先指出本文的研究背景和研究意义，在研究背景中，给出了文本分类的问题描述，然后介绍国内外的研究历史与研究现状，本文的主要工作，最后介绍本文各章的内容安排。第2 章：分析了文本分类的特点，给出了文本分类的总体框架。详细介绍了中文文本分类各处理阶段的研究方法，主要包括文本预处理、文本表示、特征降维、分类器设计等。第3 章：介绍了中文自动分词算法，分析了目前分词词典中存在的缺点及成因，提出了基于统计的用户词典生成算法。第4 章：介绍了非负矩阵分解的基本理论和计算方法，提出了基于非负矩阵分解的中文文本分类算法，最后通过实验验证了算法的有效性和实用性。第5 章：中文文本自动分类系统的设计与实现，主要描述系统设计的考虑因素、系统架构、主要步骤算法流程、用户界面及系统特点。第6 章：全文内容总结与今后工作展望。6武汉理工大学硕十学位论文第2 章中文文本分类概述2 1 文本分类的特点和框架2 1 1 文本分类的特点1 特征空间维数高这是文本分类中一个很严重的问题，也是目前最难解决的问题，特征空间的“维数灾难”普遍存在于机器学习问题当中，但是这种问题在中文文本分类中更为严重，因为中文的构词能力太强了。2 特征语义问题一种避免“维数灾难”的解决方法是，假设大部分特征之间是相同独立的【lj ，即彼此无关的，然后使用特征选择方法选择那些相同独立的特征，这是机器学习中常用的一种降维方法。但是实验表明，文本分类中大部分特征之间不是相互独立的而是彼此相关的。3 特征的多义性与同义性在文本分类中，通常使用词、n g r a m 项、概念等作为文本特征对文本进行表示。但是，中文的很多特征词条都不止具有一种含义，即多义性，如：“教授”这个特征既可以做名词，表示一种职称，也可以做动词，表示传授知识。同时，一种含义又可以用多种不同的特征来描述，即同义性或近义性，如：“电脑”和“计算机”这两个词都描述了同样的含义。4 。特征的稀疏性根据z i p f 法则，在大型语料库中统计每个单词的出现次数，然后依据单词的出现次数列出单词表，可以发现一个规律：单词的出现次数厂和它在表中位次，| 的关系为厂o c1 r ，这意味着排列在第1 0 0 位单词的出现次数是排列在第2 0 0位单词的出现次数的两倍。文本分类时，特征空间的维数是非常高的，能到达上万维，对于一篇不是很长的文档，就会存在很多频率为0 的特征，这种高维特征稀疏问题增加了后续存储和计算的难度。5 基本线性可分虽然文本的特征空间维数非常高，文本的描述方式千态百异，但是，在文武汉理t 人学硕七学位论义本分类中，大部分类别之间基本上都是线性可分的。所以要根据文本分类的这种特点，设计合适的分类方法，一些高深的、复杂的算法在其它分类问题中很有效，但是在文本分类中并。定效果好。2 1 2 文本分类的框架文本分类过程【8 】【9 】一般包括文本预处理、文本表示( 也称文本模型) 、特征降维、分类器设计与训练、分类结果评价等五大步骤。图2 1 显示了文本分类系统的总体框架。1 ) 文本预处理：根据原始语料格式和文木特征选择方法的不同，文本预处理包含的处理任务也不同，一般包含结构处理( 如去除h t m l 中的t a g ) 、分词处理、去除停用词等，实际处理时可能还会有一些参数统计的工作；2 ) 文本表示：也称文本模型，就是把文本表示成适合计算机处理的格式，一般包含文本特征及频率的统计、特征权重计算、向量空间模型生成；向量空间模型其实就是如下表2 1 所示的特征一文档权重表：表2 1 特征一文档权重农农丈潜送文档l文档2文档3电脑0 o l0 2 0o 0 0网络o o oo 1 0o 2 0电话0 1 00 0 00 o l3 ) 特征降维：一般包括特征选择、特征提取( 特征变换) ；该环节的主要目的是进行特征降维，以降低计算复杂度，提高分类性能。4 1 分类器：分类器的设计与训练是文本分类的一个重要环节；要根据文本分类的特点设计合适的分类器，并非越复杂越好。5 1 结果评价：为了比较各种文本分类方法的优劣，除了直观体验外，一般需要采用某些适宜的性能评价指标对分类结果进行自动、客观的评价。武汉理工大学硕十学位论文结构处理、分词处理、去除停用词统计特征、计算特征权重、生成向量空问模型特征选择、特征提取分类器设计、训练性能指标( r e c a l l ，p r e c i s i o n , f i 钡j j 试值)图2 1 文本分类基本框架以下分小节详细介绍中文文本分类各步骤的具体处理策略和现有算法。2 2 文本预处理文本预处理( t e x tp r e p r o c e s s i n g ) 根据文档格式的不同，包括不同的处理步骤，预处理的目的一方面是进行文档格式的统一，如：去除h t m l 的一些t a g ；另一方面是剔除区分度不强的特征测条，如：去除停用词( s t o p w o r d s ) ：还有一个方面是为文本表示提供必要处理，如：自动分词、词性标注、数字合并、短语识别、词频统计、数据清洗等【l 】。所谓停用词：一般是指那些出现频率过高，不具有类别区分度的词，比如介词( “由于”) 、连词( “和”) 、代名词( “我、他”)等；停用词还包括哪螳不携带分类信息的少见生僻词，可以根据词性确定一些停用词也可以根据日常知识积累。而在实际的文本预处理中，根据具体情况，停用词的选择有所不同，但足，应该遵循以下两点规则l lu j ：l 、文本分类的性能没有因停用词的去除而下降；2 、特征空间的维数确实在停用词去除后有所降低：9武汉理工大学硕十学位论文2 3 文本表示文本表示也称文本模型，目前也有很多种义本表示方法，但是，最常用的文本表示方法就是向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 。2 3 1 向量空间模型( v s m )v s m 是2 0 世纪6 0 年代末由g e r a r ds a l t o n 【1 1 j 等人提出的，著名的检索系统s m a r t 系统应用的就是该模型。下面先介绍v s m 模型的一些基本概念。( 1 ) 文档( d o c u m e n t ) ：泛指一般的文献或文献中的片段( 句子、句子组、段落、段落组等) ，一般指一篇文章。本文用d 表示一篇文档。( 2 ) 项( t e r m ) ：当文档被简单地看成是它所含有的基本语言单位( 词、n g r a m 或概念) 组成的集合时，这些基本的语言单位就称为项，即文本可以表示为项的集合d ( t 1 ，t 2 ，一，t 。) ，其中t i 代表项，l k n 。( 3 ) 项的权重( t e r mw e i g h t ) ：对于含有，z 个项的文本a ( t l ，t 2 ，t 。) ，项t i常常被赋予一定的权重w 。，表示它们在文本中的重要程度，即d = d ( t l ，w l ，t 2 ，w 2 ，t n , w 。) ，简记为d = d ( w l ，w 2 ，w 。) 。这时我们说项t 的权重为w ，1 k 疗。( 4 ) 向量空间模型( v s m ) ：给定一篇文档d = d ( t l ，w l ，t 2 ，w 2 ，t 。，w 。) ，由于t 。在文档中既可以重复出现义应该有先后次序的关系，分析起来仍有一定的难度。为了简化分析，可以暂不考虑t 。在文档中的先后顺序并要求t 。互异( 即没有重复，实际中也是这么处理的) 。这时可以把t 。，t ：，t 。看成n 维空间的坐标系，而w ，w ：，w n 为相应的坐标值，所以文档d = d ( w ，w ：，w n ) 可以看成是n 维空间中的一个向量。称d = d ( w 。，w ：，w 。) 为文档d 的向最表示。( 5 ) 相似度( s i m i l a r i t y ) ：两个文档d ，和d ，之间的相关程度常常用它们之间的相似度s i m ( d ，d ，) 来度量。当文档被表示为v s m 后，可以借助于向量之间的某种数学上的距离来表示文档间的相似度，常用的是向量的内积：生s i m ( d j ，嘭) = 掌( 2 - 1 )k = l或用夹角的余弦值表示：l o武汉理t 大学硕十学位论文s i m ( d j ，d j ) =其几何直观意义如下图2 2 所示：幸w j k壶= id ii。jq图2 - 2s i m ( d ，d ) 的直观几何意义( 2 2 )2 3 2 文本特征的选择从其语法层次上来看，一篇文档一般是由词、短语、句子和段落所构成的。诚然，可以用这些要素作为文档的特征。但是，随着这些要素所处的语法层次增高，组合出的特征会呈指数型增长，所以在文本分类中，一般不使用基于句子或段落层次的特征。更为常用且实用的文本特征有：词、n g r a m 项、词性、标点符号，语义模式有时也被作为了文本的特征。l 、词对于给定的文档，最直观的方法就是使用词作为文档的特征。对于英文来说，虽然不需要分词，因为单词之间已经通过空格或标点符号隔开。但是，英文中存在词形的变化，如：动词的时态变化( 人称、过去时、进行时、将来时) 、名词的单复数、词的前、后缀等，所以会有一个词干抽取的过程( s t e m m i n g ) 。对丁中文来说，虽然没有词形的变化，但是需要进行分词。现有的大多数中文分词系统一般都比较复杂，分词速度比较慢，对人名、地名、机构名等未登录词的识别率还不高。2 、n g r a m 项【1 2 1 5 】对于中文来说，n g r a m 项一般由相邻字构成。例如：从“应用数学专业”中提取2 - g r a m 项，可以得到“应用”、“用数”、“数学”、“学专”、“专业”五个2 - g r a m 项。对于英文来说，n g r a m 项既可以由相邻单词构成，也可以由相邻字母构成。武汉理工大学硕士学位论文用n g r a m 项作为文档的特征可以避免复杂的分词过程。但是，n g r a m 项的语义显然没有词明显，其中的噪声数据较多。而且，随着n 的增长，n g r a m项的数目会呈指数增长，所以n 的取值不宜过大，以减少系统的时间和空间复杂度，一般n 4 。3 、词性词性，即词语的语法类别，如：形容词、副词等。一般情况下，词性很少作为文本的特征在文本分类中使用。冈为这种特征的粒度太粗，中文的词性总数目不过几十个，很难用于文档语义的表征，所以常常是与其他特征一起使用【lj ，但是可以根据词性剔除一部分无关特征词条。4 、标点符号标点符号也很少作为文本的特征在文本分类中使用，和词性一样，也存在粒度过粗的问题【l 】，因为中文的标点符号也不过几十个。标点符号通常只作为一个辅助考虑的因素或者与其他特征一起使用，当然在网络小说和科技文献中，标点符号可能会有很强的j x 分度。2 4 特征降维高维特征空间是机器学习中普遍存在的，个问题，该问题在中文文本分类中更为突出，通常有几千上万维。高维特征空间，一方面会导致计算开销非常大，另一方面分类结果也不可靠，因此，需要进行特征降维的工作。这样做的目的主要有两个：第一，为了提高系统效率，也就是运行速度；第二，并不是所有的特征对分类的贡献都是相同的，对于每一类，应剔除那些区分度不强的特征，筛选出针对该类的特征项集合以提高分类精度。文本特征降维一般包括特征提取和特征选择。特征提取f l 】，也称特征重构，就是对原始特征进行合并或者进行变换，从而得到低维的重构特征，这是一种有效的降维方法。这种方法可以消除词之间的相关性，较好地解决了词的同义、近义、多义现象，有利于得到更低维数的、更能表达文档内容的特征。常用的方法有特征聚类、因子分析和隐含语义标引( l s i ) 等，但是重构特征在实际中。般不好解释。特征选择i ，也称为空间降维( t e r ms p a c er e d u c t i o n ，t s r ) ，是为了提高分类效率、减小计算的时问和空间复杂度，努力剔除原始特征中不带分类信息或者分类信息较少的特征词。该方法只是选择特征并不对特征进行任何处理。1 2武汉理下大学硕士学位论文目前，常用的特征选择方法有 1 6 - 1 9 】：文档频数权重、互信息权重、信息增益权重、z 2 统计量权重。2 4 1 文档频数文档频数( d o c u m e n tf r e q u e n c y ，d f ) 是指训练集中包含该特征项的文本数。通过文档频数进行特征选择的方法是：设置一个合理的阈值，剔除低于阈值的特征词，保留高于阈值的特征词，从而达到降维的目的。2 4 2 互信息利用互信息( m u t u a li n f o r m a t i o n ，m i ) 进行特征降维，主要是通过计算特征词条t 和类别c 之间的相关性来完成。公式如( 2 - 3 ) 所示：m i ( t , 。= l o g 老协3 ，假设用a 表示包含特征词条t 且属于类别c 的文档频数，曰表示包含t 但是不属于c 的文档频数；c 表示属于c 但不包含t 的文档频数，表示训练集中文档的总数且= 彳+ b ，t 和c 的互信息可用( 2 4 ) 进行简化计算：。m i ( t , c ) 1 。g 函石a x 而n 丽2 4 )如果t 和c 不相关，也就是独涉( 即p ( t x c ) = p ( t ) x 尸p ) ) ，则m l ( t ，c ) = 0 。互信息【1 6 】的基本思想就是：设定一个阂值，将原始特征空间中低于指定阈值的特征剔除，高于阈值的特征保留，从而达到降维的目的。2 4 3 信息增益信息增益( i n f o r m a t i o ng a i n ，i g ) 在机器学习领域被广泛使用。对于特征词条t 和文档类别c ，i g 通过考察c 中出现和不出现t 的文档频数来衡鼍t 对于c的信息增益，计算公式如( 2 5 ) 所示：佑o ) = 一p ( c f ) 1 9 p ( q ) + p ( f ) p ( c ti t ) l g p ( c , i f )5 12 1( 2 - 5 )+ p ( ；) p ( c f t ) i g e ( c , i t )1 3武汉理工大学硕十学位论文其中，p ( c i ) 表示q 类文档在语料中出现的概率，p ( t ) 表示语料中包含特征词条t 的文档的概率，p ( 0f ) 表示文档包含特征词t 时属于乞类的条件概率，p ( t ) = l p ( t ) 表示语料中不包含特征词条t 的文档的概率，p ( c ii t ) = p ( c f ) 一尸( c ，i t ) 表示文档不包含特征词t 时文档属于q 类的条件概率，m表示总的文档类别数。2 4 4z 2 统计量z 2 统计衡量的是一个特征t 与一个类别c ，之间的相关程度，具有和m i 方法基本相同的思想。z 2 统计假设t 和c i 之间符合自由度为l 的z 2 分布。特征词条对于某类的z 2 统计值越高，表明它与该类之间的相关性越大，携带的类别信息也越多。反之，z 2 统计量也反映特征t 和类别c i 之间的独立程度。当z 2 = 0 时，特征t 和类别q 完全独立，z 2 统计量的计算公式如( 2 6 ) 所示：舭，q ) = 酉石币n 五x ( a 丽d - 万c b 两) 2 石面( 2 - 6 )上式中，a 表示文档类别c i 中出现特征词t 的文档频数；曰表示其它类中出现特征词t 的文档频数；c 表示文档类别c i 中不m 现特征词t 的文档频数；d 表示其它类中不出现特征词t 的文档频数：表示训练语料中的文档总数，且n = a + b + c + d 。z 2 统计量和互信息的差别在于它是一个归一化的统计量，但它对低频特征项的区分效果也不好。2 5 分类器设计文本分类就是一个将文本划分到一种或多种预先确定的类别中玄的过程，因此，模式分类的很多方法可以应用到文本分类中。目前，文本分类方法基本上可以分为三大类。一种足基丁统计的方法，如相似度计算方法( r o c c h i o ) l 2 、朴素贝叶斯分类算法( n a i v eb a y e s ，n b ) 2 1 , 2 2 、k 近邻算法( k n e a r e s tn e i g h b o r ,k n n ) 2 3 1 ，支持向量机分类算法( s u p p o r tv e c t o rm a c h i n e ，s v m ) 【2 4 】【2 5 】等方法：另一种是基丁连接的方法，即人工神经网络算法( n e u r a ln e t w o r k ，n n ) 【2 0 j ；还有一种是基于规则的方法，如决策树( d e c i s i o n t r e e ) i 2 、关联规则等，这些方法的主要区别在于规则获取方法。下面给出部分方法的实现过程。1 4武汉理工大学硕十学位论文2 5 1r o c c h i o 方法一相似度计算方法r o c c h i o 方法的思路比较简单，训练阶段，主要是对每类文本训练集使用简单算术平均生成一个代表该类的中心向量，分类阶段，首先计算待分类文本的特征向量，然后计算该向量与每类文本中心向量之间的相似度，最后将文本分到相似度最大的那个类别中【。具体计算步骤如下所述：第一步：对训练集中的所有文本进行必要的文本预处理、参数统计、特征降维，并生成特征向量，然后，利用算术平均求出每类文本的中心特征向量；第二步：对于给定的待判文本，参照第一步的处理方式将其用特征向量进行表示；第三步：计算待判文本特征向量与各类中心特征向量之间的相似度，s i m z i =七= l( 2 7 )第四步：进行相似度比较，将待判文本划分到与其相似度最大的那个文本所属的类中。2 5 2k 卅k 邻近算法该算法的基本思想是：对于给定的待判文本，考虑训练集中与该待判文本距离最近的k 篇文本，这k 篇文本中哪一类的文本数日最多，则待判文本就属于哪一类。具体的算法步骤如下：第一步：对训练集中的所有文本进行必要的文本预处理，生成特征向量；第二步：对于给定的待判文本，参照第一步的处理方式将其用特征向量进行表示；第三步：在训练集中找出与待判文本最相似的k 篇文本，计算公式见( 2 - 8 ) ：s i m ( d ，d ，) = e o s ( d x ，d ，) =w 。i w i , ：，= l( 歹= 1 ，2 ，n )( 2 - 8 )k n n 分类器，是模式分类中，经常用的一种分类器，但是，目前对于k 值的确定一般是根据实验结果进行调整，没有很好的方法。武汉理工人学硕士学位论文第四步：对于待判文本的足个邻居，计算每类的权重，公式( 2 - 9 ) 显示了权重的计算方法：p ( i ，c j ) = s i m ( x ，4 ) y ( z ，c j )( 2 9 )d , e k , v l v其中，i 为待判文本的特征向量，s i m ( i ，d i ) 为相似度计算公式，而y ( 孑，c j )为类别属性函数，即：r 孑： ld i c j( 2 1 0 )【0 ，d i 区c j第五步：进行相似度比较，将待判文本划分到与其相似度最大的那个类中。2 5 3s v m 一支持向量机支持向量机【2 4 】【2 5 】是从线性可分情况下的最优分类面发展而来的。通过解一个二次规划问题，使分类边际( m a r g i n ) 达到最大从而得到一个最优分类超平面。对非线性可分情况，支持向量机通过选择一种合适的核函数将低维输入空间映射到高维核空间，试图实现非线性变换后的线性可分。支持向量机的一个优点就是可以解决小样本情况下的模式识别问题。图2 3 直观表示了s v m 的算法原理。如果一个训练集中的向量能被一个超平面无错误地线性分割，且距该超平面最近的向量之间的间隔最大( 图中红色线段所示) ，则称该超平面为最侍超平面。超半血上的点即为对超平面设计起作用的点，称为支持向量( s u p p o r t v e c t o r s ，s v ) ( 图中米黄色圆圈中的点) 。支持向量机最近两年引起了国内学术界的广泛兴趣，近两年中国期刊网上平均每天有1 5 篇与支持向量机相关的文献被收录，它被广泛应用在模式分类、数据拟合等领域。1 6武汉理工大学硕士学位论文2 6 本章小节陶2 - 3s v m 算法原理示意罔m a r 9 1 n本章首先介n t 中文文本自动分类的特点和框架；其次介绍了中文文本自动分类的各个步骤：文本预处理、文本表示、特征降维、分类器设计。罐厉对各个步骤现有的处理算法进行了洋细的介绍，武汉理丁人学硕十学位论文第3 章基于统计的用户词典生成算法文章2 3 2 节介绍了用于文本表示的4 种特征项：词、n g r a m 项、词性、标点符号，并介绍了各自的优缺点。n g r a m 项的一个显著缺点就是它的计算量比较大，特别是当n 比较大时，同时用n g r a m 项表示还存在着数据噪声大、易于过学习的缺点；词性、标点符号在实际的特征选择中，通常只是辅助考虑因素。因此，从效率和质量两个方面考虑，本文选用“词”作为文本表示的特征项。本章首先简要介绍中文自动分词；然后阐述分词词典在中文自动分词中的重要性：最后介绍基丁统计的用户词典生成算法。3 1 中文自动分词中文自动分词是汉语所特有的研究课题【27 1 。在中文处理中，词是有意义的最小单位。所谓分词，就是把一个句子按照其中词的含义进行切分，分词的难点在于如何消除歧义。目前，中文分词的常用算法可以分为三大类：机械分词方法、统计分词方法和基于理解的分词方法拉引。而在目前研究比较多的并且实用就是机械分词方法，机械分词首先需要的是