（计算机软件与理论专业论文）基于混合并行遗传算法的文本分类及聚类研究.pdf

摘要文本分类和聚类技术是应信息检索和查询需要而出现的自然语言处理领域的重要研究课题。面对急速膨胀的各种文本信息，通过使用文本分类和聚类技术，人们能对这些信息进行高效地组织和整理，以便于实现信息的准确定位和分流，从而提高用户查询和检索的效率。文本分类和聚类的研究开展了四十多年，随着人们对该问题的深入了解和重视，投身此项研究的人员逐渐增多，各种成果不断涌现。然而，文本分类和聚类问题毕竟是一项涉及多学科知识的复杂问题，还有许多问题有待我们深入研究。文本分类和聚类问题中的特征选择和抽取技术、文本特征表示、聚类方法的选择和实现以及分类方法的选择和实现，都将对文本分类和聚类结果产生极大影响。本文的主要研究工作和创新如下：1 针对文本分类和聚类中的各种问题，提出了一一种混合并行遗传算法。该算法充分利用并行遗传算法的全局优化能力和并行性，以及k m e a n s 聚类算法的高效性和局部优化能力，通过k m e a n s 聚类、种群内遗传和变异、种群间的并行进化和联姻策略，为文本分类和聚类提供了较高的效率和精确度。2 将混合并行遗传算法应用到文本聚类问题中，采用并行遗传算法对文本特征词进行动态提取，有效地降低了文本对象的特征维数：使用混合并行遗传算法进行文本聚类，动态获取聚类数目，增强了文本聚类的精度。3 将混合并行遗传算法应用到文本分类问题中，使用混合并行遗传算法进行潜在语义挖掘，消除了同义词和近义词对文本分类精度的影响；使用混合并行遗传算法对k n n 文本分类算法进行改进，同时使用并行遗传算法对s m o s v m 算法进行参数优化，最后通过高效的改进k n n 文本分类算法结合s m o s v m 分类算法对文本集合进行分类，有效地降低了分类候选数目，并提高了分类性能。4 为了验证本文所提算法的高效性和可行性，我们从国家语委现代汉语语料库中抽取大量文本进行了多项对比实验。实验证明该算法相对于其它方法在文本分类和聚类中具有不俗的表现。关键词：遗传算法；文本分类；文本聚类；k m e a n s 聚类；k n n 分类m a s t e r st h e 姗a b s t r a c tt e x tc l a s s i f i c a t i o na n dc l u s t e r i n gt e c h n o l o g i e sa r ei m p o r t a n tr e s e a r c ht o p i c si nt h ef i e l d so fn a t u r a ll a n g u a g ep r o c e s s i n g t h e ya r ep r e s e n tf o ri n f o r m a t i o nr e t r i e v a la n di n f o r m a t i o nq u e r y f a c i n gt h er a p i di n f l a t i n go fe a c hk i n do ft e x ti n f o r m a t i o n ，w ec a no r g a n i z ea n dt i d yt h e mb yu s i n gt e x tc l a s s i f i c a t i o na n dc l u s t e r i n gt e c h n o l o g i e s f r o mt h i s ，w ec a l la c c u r a t el o c a t ea n dd f s t r i b u t ei n f o r m a t i o n a tt h es a m et i m e ，t h ee f f i c i e n c yo fq u e r ya n dr e t r i e v a li se n h a n c e d r e s e a r c ho ft e x tc l a s s i f i c a t i o na n dc l u s t e r i n gh a sd e v e l o p e df o rm o r et h a n4 0y e a r s a l o n gw i t ht h eu n d e r s t a n d i n ga n da t t e n t i o no ft h e s eq u e s t i o n s ，t h ep e r s o n n e lw h od e v o t ei n t ot h i sr e s e a r c hi n c r e a s eg r a d u a l l y i nc o u r s eo fr e s e a r c h ，e a c hk i n do fa c h i e v e m e n te m e r g e su n c e a s i n g l y h o w e v e r , t e x tc l a s s i f i c a t i o na n dc l u s t e r i n gb o t hi sc o m p l e xq u e s t i o nw h i c hi si n v o l v e dw i t hm u l t i d i s c i p l i n a r yk n o w l e d g e al o to fq u e s t i o n sw a l tf o ra st os t u d yt h o r o u g h l y s o m e t h i n gs u c ha sf e a t u r ec h o i c ea n de x t r a c t i o n ，t e x tf e a t u r ee x p r e s s i o n ，c l u s t e r i n gm e t h o dc h o i c ea n dr e a l i z a t i o na sw e l la sc l a s s i f i c a t i o nm e t h o dc h o i c ea n dr e a l i z a t i o n ，a l lo ft h e mw i l lh a v ee n o r m o u si n f l u e n c et ot h er e s u l to ft e x tc l a s s i f i c a t i o na n dc l u s t e r i n g t h em a i nr e s e a r c hw o r k sa n di n n o v a t i o n si nt h ep a p e ra r ea sf o l l o w s ：1 c o n s i d e r e dv a r i o u sp r o b l e m so ft e x tc l a s s i f i c a t i o na n dc l u s t e r i n g ，w ep r o p o s e dah y b r i dp a r a l l e lg e n e t i ca l g o r i t h m c o m b i n e dw i t ht h ep a r a l l e l i t ya n dg l o b a lo p t i m i z a t i o na b i l i t yo fp a r a l l e lg e n e t i ca l g o r i t h m ，a sw e l la st h ee f f i c i e n c ya n dl o c a lo p t i m i z a t i o na b i l i t yo fk - m e a n sa l g o r i t h m ，w ec a np r o v i d eah i g h e re f f i c i e n c ya n dp r e c i s i o nf o rt e x tc l a s s i f i c a t i o na n dc l u s t e r i n gb ym e a n so fk - m e a n sc l u s t e r i n g ，h e r e d i t ya n dm u t a t i o ni nt h ec o m m u n i t y , p a r a l l e le v o l u t i o na n di n t e r m a r r i a g ea m o n gc o m m u n i t i e s 2 w ea p p l i e dh y b r i dp a r a l l e lg e n e t i ca l g o r i t h mt ot e x tc l a s s i f i c a t i o np r o b l e m s u s e dp a r a l l e lg e n e t i ca l g o r i t h mt oe x t r a c tf e a t u r ew o r d sd y n a m i c a l l y , w ec o u l dr e d u c et h ef e a t u r ed i m e n s i o no ft e x to b j e c te f f e c t i v e l y ，u s e dh y b r i dp a r a l l e lg e n e t i ca l g o r i t h mt oi m p l e m e n tt e x tc l u s t e r i n g ，w ec o u l dg e tt h en u m b e ro fc l u s t e r i n gd y n a m i c a l l ya n da c q u i r et h eh i g ha c c u r a c yo f t e x tc l u s t e r i n g 3 w ea p p l i e dh y b r i dp a r a l l e lg e n e t i ca l g o r i t h mt ot e x tc l a s s i f i c a t i o np r o b l e m s u s e dh y b r i dp a r a l l e lg e n e t i ca l g o r i t h mt ol a t e n ts e m a n t i cm i n i n g ，w ec o u l de l i m i n a t et h ee f f e c to fs y n o n y ma n dn e a r - s y n o n y mf o rt e x tc l a s s i f i c a t i o na c c u r a c y u s e dh y b r i dp a r a l l e lg e n e t i ca l g o r i t h mt oi m p r o v ek n nt e x tc l a s s i f i c a t i o na l g o r i t h m ，a n dt h e nu s e dp a r a l l e lg e n e t i ca l g o r i t h mt oo p t i m i z et h ep a r a m e t e r so fs m o s v ma l g o r i t h m i nt h ee n d ，u s e dt e x tc l a s s i f i c a c i o na l g o r i t h mb a s e do nk n nc l a s s i f i c a t i o na l g o r i t h ma n ds m o - s v mi ic l a s s i f i c a t i o na l g o f i t h mt oc l a s s i f yt h et e x ts e t f r o mt h a t ，w ec o u l dr e d u c et h en u m b e ro fc a n d i d a t ec l a s s i f i c a t i o n sa n di m p r o v et h ec l a s s i f i c a t i o np e r f o r m a n c ee f f e c t i v e l y 4 i no r d e rt oc o n f i r mt h ee f f i c i e n c ya n df e a s i b i l i t yo fo u ra l g o f i t h m ，w ee x t r a c t e dal o to ft e x t sf r o mt h em o d e mc h i n e s ec o r p u so fs t a t el a n g u a g ec o m m i s s i o n ag r e a td e a lo fc o n t r a s te x p e r i m e n t sp r o v e dt h i sa l g o r i t h mh a dg o o dp e r f o r m a n c ei nt e x tc l a s s i f i c a t i o na n dc l n s t e r i n g k e y w o r d s ：g e n e t i ca l g o r i t h m ；t e x tc l a s s i f i c a t i o n ；t e x tc l u s t e r i n g ；k m e a n sc l u s t e r i n g ；k n nc l a s s i f i c a t i o ni i i华中师范大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本声明的法律结果由本人承担。作者娩鼓立华日期：知刁年月a 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。zz作者签名：烈土华导师勰4 歹乡听日期：瑚7 年月p 日日期- 7 棚厂年6 月7 ，日j|本人已经认真阅读“c a l l s 高校学位论文全文数据库发布章程”，同意将本人的学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的规定享受相关权益。回童途童握銮后进蜃! 旦圭生；旦二生；旦三玺筮查!作者签名：鼓支 j 【日期：细殍，月1 目日砖。碑吖何郸嘶哗f 辋狮蝴硕士擘住论文m a s t e r s1 w e s i s第1 章绪论让i n t e m e t 更好地为人类服务，一直是人们努力的方向。通过不懈努力，人们逐渐掌握了多种技术对不断膨胀的信息进行收集和整理各种海量信息的复杂性和非结构性，对信息的处理带来了极大的挑战本课题为了解决信息处理中的一些相关问题而迸行了深入研究，提出了一些切实有效的措施，为海量信息的处理提供了极大帮助。1 1 课题研究的目的和意义高速发展的i n t e m e t 是一个庞大而充满混沌的互联网络，它为信息发布提供了广阔的舞台然而随着计算机网络技术和i n t e m e t 的迅速发展，大量的信息不断涌现，给信息的查询和检索带来了极大的麻烦。1 1 1 用户对网络信息的需求面对如此纷繁复杂的互联网络，我们想要得到的是快捷的服务、精简的信息以及方便的信息组织和管理模式。简单概括起来主要包括如下几个方面：1 准确而全面的信息查询和检索系统人们一直梦想着只要给出想要查询的问题，就能得到所有符合条件的信息而且不被无关信息打搅的一种手段。这种梦想实际上在查全率( 又称召回率) 和查准率( 又称准确率) 两方面对信息检索提出了要求。查全率反映了检索系统检出相关信息的全面性，查准率则反映了检索系统检出相关信息的准确程度。只有将两者合理权衡才能设计出更为满足实际需要的检索系统。然而我们现在普遍使用的搜索引擎，在这两方面还远没有达到用户满意的程度。实际使用搜索引擎的过程中，人们不是难以找到想要的信息就是找到一些毫不相干的内容。构造更为高效实用的信息检索系统仍然是人们所需要面临的问题。2 精简的文摘资料作为解决目前信息过载问题的一种辅助手段，自动文摘能在一定程度上弥补传统的信息检索技术所表现出来的种种缺憾，帮助用户提高信息检索的速度，节省重要信息的浏览时间。质量良好的文摘能在一定程度上取代原始文本的被检索地位，作为原始文本的替代品参与检索，从而能有效地缩减检索信息的时间。同时优质的文摘能用于检索结果的可视化，使得用户无需浏览大量原始检索结果便能轻松地取舍信息，从而有效地节省信息的浏览时间，提高需求信息的命中率3 个性化的信息服务处于纷繁网络中的每一个用户，都是充满个性的社会个体他们的需求、他们的习惯、他们的兴趣爱好都各不相同我们需要一种机制，能够事先根据用户的要求，预订各自感兴趣的信息，或者直接由系统通过用户的浏览历史，对用户个性习惯等特征进行分析，挖掘用户的关注点，并主动向用户提供他们可能需要的信息集合和更周到的特色服务。这种主动的个性化的服务系统，将针对不同用户的信息需求，采取不同的策略自动过滤和抽取信息，并提供不同的服务内容4 信息的过滤、加工和整理搜索引擎为人们提供了信息的检索平台，但是仅仅依靠搜索弓 擎并不能完全满足用户对信息的不同需求。信息过滤技术是对搜索引擎的有效补充，信息过滤技术能为用户剔除有害信息并主动向用户进行信息推荐，使人们在浩瀚的信息海洋中寻求尽可能多的知识，而又能有效避免垃圾信息的干预。信息的加工和整理主要目的则是将获取的海量信息进行组织和条理化，对这些信息按照各种方式进行分类、分项加工整理，为信息的保存、查询、检索、过滤以及信息抽取等提供便利置身于混沌而纷繁复杂的网络，为了从海量信息中快速、精确而全面地获取用户感兴趣的资源，人们必须首先对这些信息进行有序地组织和整理，以便于实现信息的准确定位和分流。文本挖掘技术正是在这种需求下发展起来的。通过文本挖掘，可在大规模文本集合中发现隐含的、未知的和潜在有用的知识。1 1 2 文本分类和聚类对信息获取的作用文本分类和聚类是一种集机器学习、模式识别、统计分析和信息检索技术于一体的文本挖掘方法。通过文本分类和聚类技术，可以将大量的文本信息进行自动分类，根据文本语义划分到不同类别，以方便文本集的使用和管理。文本分类和聚类对用户信息获取的巨大作用表现在如下几个方面：1 ，合理组织检索结果互联网络中的信息都是一些无组织的杂乱的w e b 页面。为了方便用户对主页的查找，人们构建了大量搜索引擎。但是通过搜索引擎检索到的结果往往是大量的w e b 页面，而且这些页面中大部分都是与用户的查询需求不相关的资料虽然有些2项士学位论文m a s t e r st h e s i s技巧试图通过页面关键词和查询关键词的相似度等方式对查询结果进行排序，但仍然不能保证和用户需求最相关的页面一定被排在最前面。这种结果使得用户不得不对检索到的页面依次浏览，不能充分享受到搜索引擎带给我们的利益。使用文本分类和聚类技术，能对检索结果进行合理组织，自动将页面按照彼此间的相似程度划分到不同的类别，每个类别都有一个明确的主题，用户可根据自己感兴趣的主题，迅速地找到相关信息这种检索结果的组织方式将对用户的查询带来极大的方便2 提供可视化的多文档摘要传统的搜索引擎检索到的结果往往以单个文档摘要的形式逐一列出并呈现给用户这种表现形式使得用户必须查询大量原始文档的摘要信息才能找到自己想要的资料，给用户的信息查询带来了极大不便通过文本分类和聚类技术，我们能将搜索引擎检索到的大量的原始文档进行合理划分，然后采用文摘技术形成多文档摘要信息，并根据不同文档间的联系组成可视化的文档关联图，以方便用户的信息查询。3 加速检索过程基于关键词匹配的信息检索是目前信息检索的主流技术，然而由于自然语言中存在大量多义和同义的现象，这就给信息检索带来了诸多隐患。针对该问题，有学者提出了潜在语义索引( l a t e n ts e m a n t i ci n d e x i n g ，l s i ) i l 】1 2 】的概念空间结构。它通过统计分析，在大规模文档集合中提取潜在的语义联系采用潜在语义索引的检索系统，当有用户提出检索请求时，将把用户输入的检索项视为虚拟文本，并将其转化为概念空问中的投影，然后将这个虚拟文本与原始文档集合中的所有文本进行相似度比较，返回其中与检索项相似度较大的文本作为查询结果。使用潜在语义索引方法虽然能够解决单纯的关键词匹配方法中的多义和同义现象，但是文档集合中的文本数目较多时，奇异值分解和相似度比较的过程将会耗费大量时间。一种可行的解决方案就是事前对原始文档集合进行分类和聚类，将相似度较高的文本划分在同一组。检索时只须将检索项与各组的类中心进行相似度比较，从而大大加速整个检索过程。4 个性化信息推介传统的搜索引擎技术中，用户方总是处于主动地位，搜索引擎只能根据用户的请求被动地提供信息。提供个性化信息服务的现代搜索引擎能自动采集用户在互联网上的行为，并跟踪记录用户的访问链接信息，然后根据采集到的用户数据对用户的界面习惯、浏览习惯和信息关注点等进行分析通过文本分类和聚类，把用户分为对不同事物感兴趣的各个小组，最后由系统主动将信息发送到相应的用户总之，文本分类和聚类技术将为信息的查询、加工、过滤和整理等环节提供坚实的技术基础1 2 国内外研究现状文本分类和聚类技术是自然语言处理领域的重要研究课题。通过文本分类和聚类技术，人们能对急速膨胀的各种文本信息进行高效地组织和整理，以便于实现信息的准确定位和分流，从而提高用户查询和检索的效率，同时为个性化信息服务提供良好的基础。文本分类和聚类的研究已经开展了四十多年。随着互联网络的不断发展和信息的不断膨胀人们对文本分类和聚类问题有了更加深入的了解和重视，国内外大量学者不断投身到该项研究，各种成果不断涌现。对于文本分类和聚类的研究，国外主要的研究单位有斯坦福大学、麻省理工学院和c m u ( c a m b d d g em a n a g e m e n tu m 0 等，这些单位在理论研究上有很高的水平文本自动分类和聚类在国外经历了三个发展阶段1 3 】：第一阶段( 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 系统等国内文本分类和聚类的主要研究单位有东北大学、复旦大学、哈尔滨工业大学、华中师范大学、中科院计算所及北京拓尔思公司t r s 等，主要都是将国外的方法引进来应用到中文信息处理技术上。我国文本分类和聚类的研究工作始于2 0 世纪8 0 年代，大体经历了可行性探讨阶段一辅助分类聚类系统阶段一自动分类聚类系统阶段总体来说，中文文本分类和聚类还处于试验研究阶段，分类和聚类正确率约为6 0 9 0 ，已经逐渐向商业化的软件应用靠拢，并已经尝试开发了一批自动分类和聚类系统。例如清华大学吴军研制的自动分类系统、上海交通大学王永成等研制的基于神经网络优化算法的中文自动分类系统、山西大学刘正英等人开发的金融自动分类系统、t r s 公司开发的t r s 文本挖掘基础件t r sc k m 等。4硕士擘住论文m a s t e r st h e s i s现有的中文分类和聚类技术绝大多数都用到经典的向量空间模型，其中使用较多并且技术比较成熟的主要有基于统计的分类和聚类技术以及基于人工智能的自动分类和聚类技术例如：中科院计算所数字化研究室开发的智多星中文文本分类器，采用多种方法构造了不同的分类器，其中采用基于聚类粒度原理的v s m 分类方法构造的分类器，以聚类指导分类，测试文档都是新闻稿，按照中图分类法分成3 8 大类，结合聚类结果形成1 5 3 2 个子类，封闭测试分类正确率为9 9 8 ，开放测试分类正确率为8 5 1 2 ；采用基于l s i 的v s m 分类方法构造的分类器，在l s i空问进行分类，所有测试文档都是新闻稿，按照中图分类法分成3 8 大类，转换到l s i 空间，封闭测试分类正确率为8 5 。开放测试分类正确率为8 2 ；采用基于l s i和聚类粒度原理的v s m 分类方法构造的分类器，在l s i 空间以聚类指导分类，所有测试文档都是新闻稿，按照中图分类法分成3 8 大类，测试文档向量经l s i 转换后，结合聚类结果形成1 0 7 4 个子类，封闭测试分类正确率为9 9 7 ，开放测试分类正确率为8 4 o ；采用复旦大学黄萱菁的距离中心分类方法构造的分类器，基于v s m 模型，测试文档都是新闻稿，同样按照中图分类法分成3 8 大类，每类一个中心，封闭测试分类正确率为8 3 9 3 ，开放测试分类正确率为7 9 8 ；采用基于k 最近邻原理的v s m 分类方法构造的分类器，测试文档为复旦新闻语料集，按中图分类法分成3 8 大类，封闭测试分类正确率为9 0 ，开放测试分类正确率为8 4 北京工业大学计算机学院人工智能与知识工程实验室的个性化邮件分类系统，采用了五种不同的特征提取方法及三种不同的分类器，在实际使用中可以根据需要选择最好的组合，以使分类精确度达到最佳效果，经试验目前系统平均准确率在8 5 1 3 文本分类和聚类存在的问题文本分类和聚类问题都是自然语言处理领域涉及多学科多专业知识的较为复杂的问题，虽然有大量学者进行了深入研究，但是仍然存在许多问题有待我们继续研究。在研究过程中，我们发现文本分类和聚类存在如下问题：1 文本对象的高维性和稀疏性要进行文本分类和聚类，首先要做的工作就是对文本数据进行数学描述，其中使用最多的是向量空间模型1 4 1 1 5 1 1 6 1 1 7 1 在这种描述模型中，每个不同的特征词都作为特征空闻中的一维，每个文本被视为特征空间中的一个向量。这种描述方法带来的直接后果就是文本对象的高维性和稀疏性问题。文本对象的高维性通常情况下，对于中等规模的文本数据集，其特征词往往达到数万个，这种高维度的数据对于各种文本分类和聚类算法都几乎是不可能实现的即使经过文本预处理，也至少包括几百个甚至成千上万的文本特征词这相对于传统数据库中仅仅包括几个，至多几十个属性的数据对象来说，在分类和聚类过程中都将存在着很大的差异随着数据对象维度的增加，在分类和聚类算法的可伸缩性、发现任意形状的簇以及处理孤立点的能力等问题上，都面临着极大的问题。一些在低维数据上优秀的分类和聚类算法，在面对上述高维文本数据时，无论在性能还是效果上都将有很大的下降这是在文本分类和聚类中必须克服的文本对象的稀疏性待分类和聚类的文本集合经过预处理后，其中每个文本将被表示成一个文本特征向量整个向量表示的是该集会中挑选出来的所有特征词，而属于一个文本的特征词可能仅仅占整个特征词集的很小的一部分，文本特征向量在文本空间中绝大部分维度上的值都为零，文本的表示形式高度稀疏。文本对象的稀疏性导致了文本之间的关系仅仅取决于少量特征词，这种情况对于基于相似度的算法会产生较大的负面影响，使得同一簇内对象相似程度降低，违背了聚类算法的初衷对于基于模型的算法，这种情况也会导致参数估计片面和不准确的缺点，严重影响了分类和聚类质量文本对象的高维性和稀疏性不仅使得文本分类和聚类的时间复杂度加大，而且会大大降低文本分类和聚类的性能嘲【9 1 2 同义词和近义词问题除了高维性和稀疏性之外，文本数据还具有同义词和近义词等特有的自然语言现象。同义词和近义词的现象是指可以用多种不同的方式来描述同一个主题或者内容。这是由于人们所处时间、地点不同，或因知识水平、周围环境、语言习惯和特定需求等因素引起【1 0 】。例如“电脑”和“计算机”，两个词字面上完全不同，但是二者所指为同一事物。文本对象之间的相似程度不仅取决于特征词字面的关系，也就是文本内出现的相同的特征词，而且取决于出现的特征词在概念上和语义上的潜在关系。如果在文本分类和聚类中仅仅从字面上来理解特征词，不仅会使系统在文本理解上产生偏差，同时还会引起特征向量维数增加，这些问题都将使分类和聚类变得更为困难u ”，从而影响文本分类和聚类的性能。6硕士擘位论文m a s t e r s t h e s i s同义词和近义词的存在极大地降低了文本分类和聚类的精确率和效率。为了避免这种现象的发生，人们常采用潜在语义索引的方法对文本对象进行处理，从而达到特征词降维和增强语义关联的目的但是对于大规模的文档集合，采用潜在语义索引必将耗费大量的机器时问，对分类和聚类的效率带来了极大挑战。3 效率与糖确度之间的搭配问题针对文本聚类问题的算法有很多，其中传统k - m e a n s 聚类算法因其简单和高效性，在文本聚类中占有重要地位。然而k - m e a n s 聚类算法对初始聚类中心的选择敏感，易于陷入局部最优解相对于k - m e a n s 聚类算法，基于遗传的聚类算法在速度上有所逊色。但是基于遗传的聚类算法是一种全局优化算法，它不仅能解决k m e 姐s 聚类算法对初始聚类中心选择的敏感问题，还能保证聚类的精确度那么如何将这两方面的优势相互结合并合理利用，将是我们需要研究的内容。针对文本分类问题，k n n 算法是种高效的分类算法，它同样不可避免地面临着分类精度问题。s m o - s v m 算法在分类中占有重要地位，能为分类提供较高的准确度，但是它也存在学习效率低下，严重影响分类效率的弊端。能否将它们也进行结合，相互取长补短，从而达到充分发挥效益的目的呢? 我们的研究将会开创这样一个局面。4 参数优化阀题在文本分类和聚类闯题中，由于问题的复杂性，不可避免地涉及到一些参数的优化问题。采用何种优化方式才能保证算法的有效改进，这也是我们需要深入研究的一个方面。1 4 本文研究内容和目标本文的主要研究目标就是通过有效途径，合理地解决文本分类和聚类中存在的各种问题。针对上述各种问题，我们提出了基于混合并行遗传算法的文本分类和聚类方法该方法充分利用并行遗传算法的全局优化能力和并行性，以及k - m e a n s 聚类算法、k n n 等分类算法的高效性和局部优化能力，通过k - m e a n s 聚类、对悄等文本分类、种群内遗传和变异、种群问的并行进化和联姻策略，为文本分类和聚类提供了较高的效率和精确度。在文本聚类问题中，我们主要研究如下内容：7硕士擘住论文m a s t e r st h e s i s1 采用并行遗传算法对文本特征词进行动态提取使用并行遗传算法对特征词的提取进行动态寻优，从而保证聚类的精确度并行遗传算法充分利用遗传算法的并行性，通过染色体交叉和变异保证种群内染色体的多样性，通过种群间的联姻有效避免近亲繁殖带来的危害，同时由于引进其它种群的优良基因，因而能加快算法的搜索过程2 使用并行遗传算法和k - m e a n s 算法相结合的混合并行遗传算法进行文本聚类考虑到k - m e a n s 算法的高效性和对初始聚类中心敏感的问题，我们采用并行遗传算法对初始聚类中心进行优化，从而在保证聚类效率的前提下同时获得了聚类的精确度。在k - m e a n s 算法中还存在聚类数的选择问题。通过在遗传算法中采用可变长染色体编码，能有效地解决k - m e a n s 算法聚类数的选择问题，使得聚类数能够随着遗传进化的过程动态优化，这样使得聚类精确度得到极大提高。在文本分类问题中，我们主要研究如下内容：1 使用k - m e a n s 聚类算法进行特征词粗粒度聚类，然后采用混合并行遗传算法对各类特征词进行细粒度聚类，最后对各聚类中的特征词进行分析并压缩，得到最终能反映文本类别特征和语义信息的文本特征词集合相对于文本聚类来说，文本分类中的特征词抽取过程有了类别信息的帮助如果能充分地利用这些类别信息，必将对分类准确率和召回率都带来极大改善。因此在文本特征词的向量表示中，我们将类别信息加入其中，形成富含类别信息的特征词向量。为了得到能反映文本类别特征和语义信息的文本特征词集合，我们采用聚类的方法对特征词进行聚类，然后分析和压缩各聚类中的特征词这种方式避免了潜在语义索引的大规模计算和最终形成的语义信息的不可理解性。2 使用混合并行遗传算法对k n n 文本分类算法进行改进，同时使用并行遗传算法对s m o - s v m 算法进行参数优化，最后通过高效的改进k n n 文本分类算法结合s m o s v m 分类算法对文本集合进行分类k n n 算法是一种相对简单而高效的文本分类算法，但是k n n 算法分类精确度并不是很高，为了增加聚类精确度和进一步加快算法速度，我们使用k - m e a n s 算法和并行遗传算法对k n n 算法进行改进。s m o - s v m 算法是一种精确度较高的文本分类算法，但是算法训练时间消耗过多。基于上述原因，我们将前面改进的k n n 算法与s m o s v m 算法结合，形成新硕士擘住论文m a s t e r st h e $ 1 8的文本分类算法。s m o s v m 算法中，涉及到训练参数的优化问题，我们采用并行遗传算法对其进行优化1 5 本文内容组织本文共分6 章。第l 章绪论，介绍了课题研究的目的和意义，文本分类和聚类的国内外研究现状，文本分类和聚类存在的问题及本文的研究内容和目标。第2 章介绍了文本分类和聚类的基本理论及方法第3 章详细介绍了遗传算法的基本知识和并行遗传算法第4 章详细介绍了混合并行遗传算法及其在文本聚类中的应用第5 章详细介绍了混合并行遗传算法在文本分类中的应用第6 章是全文内容的总结与展望9项士擘住论文h a s t e r st h e s i s第2 章文本分类和聚类的基本理论及方法文本分类和文本聚类是一对关系密切的文本挖掘方法，在自然语言处理领域占有重要地位两者之间既有许多相似的地方，又存在较大差别本章将简要介绍文本分类和文本聚类的基本理论及方法2 1 文本分类和聚类的概念2 1 1 文本分类一文本分类就是在给定的分类模型下，由计算机根据文本内容自动判别文本类别的过程其中文本的来源可以是报告、新闻、邮件和单据等从数学上看，文本分类是一个映射过程，它将未标明类别的文本映射到已有的类别中，而且这种映射可以是一对一的，也可以是一对多的。如果使用数学语言来进行描述，文本分类可表示为：对于每个文档与类别的二元组 e d x c ，判断其值，如果值为l ，表示文档函属于类别白，如果值为0 ，表示文档西不属于类别白( 其中西是属于文档集合d 中的一个文档，c c l ，o ，c n 是预先定义的类别集) 。文本分类就是要找出描述文本如何被分类的函数中：d x c 一 l ，0 l ，这个函数又叫做文本分类器。2 1 2 文本聚类根据文本分类的定义可知文本分类是在已经知道类别标签的文档集合的基础上进行类别划分的。但是在许多实际应用中由于缺少形成模式类别过程的知识，或者模式类别的形成困难，这时我们只能在没有类别标签的文档集合上进行类别划分，这就是文本聚类。文本聚类是将文档集合全自动归类的过程，是一种无指导的文本归类方法，它与文本分类的区别在于文本聚类没有预先定义的主题类别，类别是通过机器学习相关数据得来。文本聚类的目标是通过文本聚类，将文档集合划分为若干簇，并使得同一簇中的文档具有尽可能大的内容相似度( 主题相关性) ，而不同簇问的文档内容相似度尽可能小( 主题无关性) 。如果使用数学语言进行描述，文本聚类可以表示为：给定文档集合1 9 = 西，西，磊 ，对集合d 进行划分，从而得到簇的集合1 0c c l ，句，q ( 其中0cd j = 1 2 ，玉) ，使得对v 西翰d ) ，3 c j ( c j e c ) ，且有函毋，同时使得聚类准则函数厂( c ) 的值最小2 2 文本的表示计算机不具有人类的智能，不能像人一样根据自身理解能力对文章产生模糊认识因此在文本分类和聚类之前，首先应将文本转换为易被计算机理解的形式，然后通过具体的文本分类和聚类方法对文本类别进行划分文本的表示既要能使其方便计算机的处理，又要能够有效表达文本内容。大量研究表明向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 是一种适合于大规模语料的文本表示模型。一2 2 1 向量空间模型向量空间模型【4 l 由哈佛大学的g e r a r ds a l t o n 提出。向量空问模型实际上是用于文本表示的统计模型。该模型中，文本空问被看作一组正交特征向量组成的向量空间。向量空间模型将任意一个文本表示成空间向量的形式，并以特征项作为文本表示的基本单位。向量的各维对应文本中的一个特征项，而每一维本身则表示了其对应的特征项在该文本中的权值权值代表了特征项对于所在文本的重要程度，也反映了该特征项对文本内容的反映能力。对于中文文本而言，可以选择字，词、词组、短语、句子或者句群作为文本特征项。特征项的选择要以处理速度、精度和存储空间等方面的要求为原则。由于词汇是文本的最基本表示项，在文本中出现的频率较高而且呈现一定的统计规律，不同的特征词就可以区分不同内容的文本，因此在向量空间模型中一般选择词或词组作为特征项。文本的向量空间表示可描述为如下的公式：v c d ，) = ( 嵋( 面) ，w j ( 巧) ，1 ( 巧) )( 2 1 )其中一表示文本特征抽取时所选用的特征项数日，w ， 由表示第_ ，个文本特征项在文档西中的权值。2 2 2 特征项的权值计算在文本向量空间表示中，每个特征项都有一个权值，权值的大小反映了特征项对于文本的重要程度，即一个特征项在多大程度上能将其所在文本与其它文本区分开来特征项的权值计算方法有很多种，如矿方法、矿”方法和m u t u a li n f o r m a t i o n “”方法等。较为常用的是t f * i d f 加权法，也就是特征项频率x 倒排文档频率加权法。其中特征项频率矿指某个特征项t e r r r l i 在文本4 中的出现次数，记为螗。蛎越高，意味着特征项t e r m f 对文本西越重要。文档频率矽指含有特征项t e r r a ，的文本数量，记为嘶顿越高，意味着特征项t e r m i 在衡量文本之间相似度的作用越低。倒排文档频率f c 矿则表示了一个特征项在整个文档集合中的特性，它用来衡量该特征项在整个文档集合中的分布情况。一般情况下，i d f 和矽成反比关系，如公式( 2 - 2 )所示： ，。i d f , = l o g ( - ) ( 2 - 2 )掣l其中为文档集合中的文本数目动；值越高，意味着t e r m ，对于文本的区别意义越大。如果一个特征项仅出现在一个文本中，则i d f = l o g n , 如果一个特征项出现在所有文本中，则i d f = l o g l = 0 。在向量空间模型中，文本特征项的权值计算一般采用公式( 2 3 ) ：m ( d j ) = 毵l 0 9 2 ( n + o 0 1 )( 2 - 3 )其中以为第i 个文本特征项在文本4 中出现的频次，为文档集合中的总文本数，m 为文档集合中出现第i 个文本特征的文本数。为了减小文本长度的不同对于文本相似度计算的影响，通常要将每个向量归一化到单位向量，最后得到文本特征项的权值计算公式如下；w j ( d ，) ： 丝：! ! ! ! ! 丝! 丝兰! ：! ! !(2-4)。：，。( ) 2 + 【1 0 9 ：( n n k + 0 0 1 ) 】22 2 3 文本相似度计算文本相似度是用来衡量文本之间相似程度大小的一个统计量。文本相似度一般定义为界于【o ，l 】之间的一个值。如果两文本之间相似度为1 ，则说明两文本对象完全相同，如果相似度为0 ，则说明两文本没有相似之处。对基于相似度的文本分类和聚类算法来说，作为算法基础的相似度的定义至关重要。在向量空间模型中，文本相似性的度量有相关系数法和距离函数法等。在文本分类问题中，由于使用k n n 分类算法，考虑到数据统计的方便性，我们使用余弦法进行文本相似度计算计算公式如公式( 2 5 ) s i m ( 4 ，d ，) ：c o s ( 4 ，t ) ：1圣些丝：丝( 2 - 5 )。( ：。w n 2 ) ( ：。惕2 )其中s i m ( 矗西) 表示文本d j 和巧之间的相似程度，旨，峋分别表示文档d l 和弓的第k 个特征项的权值。s i m 值越大表示两个文本越相似，$ 1 m 值越小则表示两个文本区别越大。在文本聚类问题中，考虑到本文使用k r l e a l l s 聚类算法进行文本聚类分析，根据k - m e a n s 聚类算法的特点，我们选用欧氏距离进行文本间相似性度量。具体计算公式如下：广id i s ( 4 ，哆) = 二( 屹一b ) ( 2 6 )其中d i s ( 以弓) 表示文档西和弓之间的欧氏距离，慨，坳分别表示文档珥和弓的第k 个特征项的权值。d i s 值越大，文本之间的相似度越小，d i s 值越小，文本之间的相似度越大2 3 文本特征选择和抽取构成文本的词汇，数量相当大对于中等规模的文档集合，其特征词就可达到好几万个这使得表示文本的向量空间维数剧增，必将对文本分类与聚类的效率和精度产生不良影响。为了提高文本分类与聚类的效率和精度，我们必须首先对文本进行特征选择和抽取2 3 1 文本预处理文本预处理通常包括如下几个环节：去掉某些特定文档中的格式标记；去除停用词、进行数字合并、词根还原：分词、词性标注、短语识别：词频统计；进行数据清洗以去除不合适的噪声文档或文档中的垃圾数据。通过文本预处理，能将那些对文本分类和聚类没有贡献的或贡献过小的特征词从特征词集合中去除，从而使向量空间维数明显减少。本文中我们并没有采用分词技术进行文本预处理，而是充分利用基于开放式语料的汉语术语的自动抽取【1 3 1 方法抽取适量术语，并用术语来刻画文本特征。采用该