（管理科学与工程专业论文）文本挖掘算法及其在知识管理中的应用研究.pdf

人连理工大学博士学位论文 摘要 随着知识经济的到来，知识管理在社会经济中的作用日益重要。大多数的知识管 理研究是为企业服务的，针对科研管理部门的知识管理研究非常少，本文对我国科研 管理部门的知识管理问题进行研究。与其他领域相比，科研管理部门的知识管理有一 定的特殊性。比如，科研管理部门管理着蕴含大量知识的立项建议申请书。挖掘并利 用申请书中的知识，能够在从科学研究整体层面、学科领域层面和项目管理层面对科 研管理工作提供决策支持。 申请书中的知识隐含在申请书内容之中，从申请书中挖掘知识会面临如下问题： 申请书的知识表示不能完全依赖于词典；申请书研究内容与申报学科领域不能完全吻 合；学科代码体系结构与实际研究领域的体系结构不能完全一致。针对上述问题，本 文在以下几个方面进行了研究： 第一，提出一种不依赖于词典抽取高频词的桥接模式滤除算法( b p f a ) 。首先基 于n g r a m 技术获取文本中的汉字结合模式及出现频率，然后通过消除桥接频率得到模 式的支持频率，并依此来判断和提取正确词语。实验结果显示，b p f a 能够有效提高分 词结果的查准率和查全率。该算法适用于对词语频率敏感的中文信息处理。本文应用 该算法，抽取申请书中出现的新术语，补充到系统词表中。 第二，粗分类数据中包含有文本内容与类别标记不符的噪声数据，这些噪声数据 会对文本分类结果的精度产生不良影响。本文提出一种针对粗分类数据的噪音修正算 法。首先建立文档关联网络，把文档上标记的类别作为原始的社团结构，并用模块度 衡量社团结构的质量，通过优化模块度指标把噪声数据调整到正确的类别中，从而提 高数据质量。实验结果表明，本文所提算法能够有效修正粗分类数据中的噪声，具有 较高的有效性和鲁棒性。该算法可以用于文本分类训练数据的预处理，或作为辅助技 术用于文献库建设等工作。本文把申报到各个学科代码下的申请书作为粗分类数据， 应用该算法把与代码不符的申请书调整到正确的代码中。并根据调整后的数据建立代 码模型，分析代码所代表研究领域的内涵和外延、代码之间的交叉关系。 第三，提出基于公共连接强度的快速聚类算法。利用社团成员之间的相似关系定 义了社团连接强度，根据社团的公共连接强度定义了一种新的相似度计算方法，并应 用该相似度计算方法提出一种凝聚聚类算法。在相似度计算中，综合考虑了社团内部 和外部结构关系，因此能够避免其他算法在聚类初期容易出现的聚类错误。分别对拓 扑和加权的实验数据进行聚类，实验结果证明了所提算法比其他算法更为有效。本文 应用该算法对申请书进行聚类分析，形成了项目类，并对项目类和学科代码之间的关 文本挖掘算法及其在知识管理中的应用研究 系进行了分析。 本文在理论方法研究的基础上，对国家自然科学基金委员会的基金管理工作进行 了应用研究，分析了我国基础科学研究的整体发展状况和发展规律、各个学科领域的 研究状况及其关系等，为制定发展规划、发展战略、学科代码体系调整以及项目管理 提供决策支持。 关键词：知识管理；文本知识发现；文本分类；文本聚类 一i i 大连理工人学博士学位论文 t e x tm i n i n ga l g o r i t h m sa n dt h e i ra p p l i c a t i o n si nk n o w l e d g e m a n a g e m e n t a b s t r a c t w i t ht h ea d v e n to fk n o w l e d g e b a s e de c o n o m y , t h ek n o w l e d g em a n a g e m e n t ( k m ) c o n - t r i b u t e sm u c hm o r et h a nb e f o r ei nt h es o c i a la n de c o n o m i cl i v e s m o s to ft h er e s e a r c h e r sf o c u s o nt h eo n e so nt h ee n t e r p r i s e s ，a n dt h e r ea r el i t t l er e s e a r c hw o r k sa i m i n ga ts o l v i n gt h ek m p r o b l e m si ns c i e n t i f i cm a n a g e m e n td e p a r t m e n t s ( s m d s ) i nt h i sd i s s e r t a t i o n ，t h ek m o fs m d s o fc h i n ai ss t u d i e d k mi ns m d si sd i f f e r e n tf r o mt h o s ei nt h eo t h e rd o m a i n s f o ri n s t a n c e ， s m d so fc h i n ah o l d sm a n yr e s e a r c hp r o p o s a l sw i t hl o t so fk n o w l e d g e o b v i o u s l y , t h ea c t i v i t i e s t om i n ea n du t i l i z et h ek n o w l e d g ei nr e s e a r c hp r o p o s a l sc a ns t r o n g l yp r o v i d ed e c i s i o ns u p p o r t f o rt h es m d si nt h ef o u o w i n gl e v e l s ：t h ew h o l ed i s c i p l i n e ，t h es u b d o m a i no ft h ed i s c i p l i n ea n d t h er e s e a r c hp r o j e c t s k n o w l e d g ei sc o n t a i n e di nt h ec o n t e n t so fr e s e a r c hp r o p o s a l s i no r d e rt od i s c o v e rk n o w l e d g ef r o mt h ep r o p o s a l sc o n t e n t s ，t h e r ea l es e v e r a lp r o b l e m ss h o u l dt ob es o l v e d , i n c l u d i n g k n o w l e d g er e p r e s e n t a t i o n so fr e s e a r c hp r o p o s a l sc a n n o tf u l l yr e l yo nt h et h e s a u r u s ；t h ec o n - t e n t so fr e s e a r c hp r o p o s a l sa r en o tc o m p l e t e l yc o n s i s t e n tw i t ht h es u b m i t t e ds u b j e c tf i e l d ；a n d t h es t r u c t u r eo fs u b j e c tc o d i n gs y s t e mi sn o te n t i r e l yi d e n t i c a lw i t ht h a to fa c t u a lr e s e a r c hf i e l d i nt e r m so ft h ea f o r e m e n t i o n e di s s u e s ，t h ef o l l o w i n gt h r e ef o l d sa r ec a r r i e do u t f i r s t l y ，ab r i d g e c o n n e c t i o np a r e r nf i l t e r i n ga l g o r i t h mi sp r e s e n t e df o re x t r a c t i n gh i g h f r e q u e n c yw o r d sw i t h o u tt h e s a u r u s t h ef r e q u e n c i e so fc o - o c c u r r e n c ep a t t e r n so f t h ec h i n e s e c h a r a c t e r sa r ec o u n t e df r o md o c u m e n t s 1 h es u p p o r t e df r e q u e n c i e so fp a t t e r n sa r eo b t a i n e db y e l i m i n a t i n gt h eb r i d g e c o n n e c t i o nf r e q u e n c i e s b a s e do nt h es u p p o r t e df r e q u e n c i e s ，t h ew o r d s c a nb eb e r e ri d e n t i f i e da n de x t r a c t e dt h a nt h eo n e so b t a i n e db yu s i n gt h ep r i m a r ya p p e a r i n g f r e q u e n c i e s t t l i sa l g o r i t h mc a nb ea p p l i e dt ot h ec h i n e s ei n f o r m a t i o np r o c e s s i n g w h i c hi s s e n s i t i v et ot h ew o r df r e q u e n c i e s u s i n gt h i sa l g o r i t h m ，t h en c wf e a t u r e sw h i c hd o n te x i s ti n t h et h e s a u r u sc o u l db ee x t r a c t e df r o mt h ep r o p o s a l sa n da d d e di n t ot h et h e s a u r u s s e c o n d l y , ar e v i s i o na l g o r i t h mf o rn o i s et e x t si sp r e s e n t e dt os t u d yt h ee f f e c to f t h en o i s y d a t at ot h ec l u s t e r i n gr e s u l t s i nt h ea l g o r i t h m ，t h ed o c u m e n ts i m i l a r i t yn e t w o r ki sc o n s t r u c t e d 一一 文本挖掘算法及其在知识管理中的应用研究 f r s t l yb a s e do ns i m i l a r i t i e so ft h ed o c u m e n t sc o n t e n t s t h ec a t e g o r i e sc o n s t i t u t et h ec 0 1 t e - s p o n d i n gc o m m u n i t ys t r u c t u r ei nt h en e t w o r k ，a n dm o d u l a r i t yi su s e dt oe v a l u a t et h eq u a l i t yo f c a t e g o r i e s t h en o i s et e x t sc a l lb er e v i s e db yo p t i m i z i n gt h em o d u l a r i t y t h i sa l g o r i t h mc a nb e u s e di nt h ep r e p r o c e s s i n go ft e x tm i n i n go rt a x o n o m yb u i l d i n g i nt h i sd i s s e r t a t i o n ，t h er e s e a r c h p r o p o s a l sb e l o n g i n gt os u b j e c tc o d e sa r er e g a r d e da st e x t sw i t hn o i s e u s i n gt h ep r e s e n t e d a l - g o r i t h m ，t h ep r o p o s a l st h a ta r es u b m i t t e di n t ot h ew r o n gs u b j e c tc o d e sc a nb et r a n s f e r r e dt ot h e c o r r e c to n e s b yu s i n gt h em o d i f i e dd a t a ，t h em o d e l so ft h es u b j e c tc o d e sa r eb u i l t ，a n dt h e i n t e n s i o na n de x t e n s i o no fe a c hr e s e a r c ha r e a ，e x p r e s s e db yc o d e ，c a nb ec o n f i r m e d m o r e o v e r , t h er e l a t i o n s h i p sb e t w e e nc o d e sc a nb ea n a l y z e d f i n a l l y ，i n s p i r e db yt h en o d es i m i l a r i t yo fs o c i a ln e t w o r k s ，an e wd e f i n i t i o n ，n a m e dc o m m u n i t ys i m i l a r i t y , i sp r e s e n t e db a s e do nt h ec o m m o nc o n n e c t i n gs t r e n g t h s b a s e do nt h i sd e f - i n i t i o n ，ac l u s t e r i n ga l g o r i t h mi sd e s i g n e d i nt h ei n i t i a ls t a g ee a c hd o c u m e n ti st r e a t e da sa c l u s t e r a te a c hs t e p ，t w oc l u s t e r sw i t ht h el a r g e s ts i m i l a r i t ya r ec o m b i n e d b e c a u s et h er e l a t i o n sb e t w e e na n dw i t h i nt h ec l u s t e r sa r et a k e ni n t oa c c o u n t ，s o m ec o m b i n i n ge r r o r sc a nb e a v o i d e da n db e t t e rc l u s t e r i n gr e s u l t sa r eo b t a i n e d b a s e do nt h i sa l g o r i t h m ，t h er e s e a r c hp r o p o s - a l sa r ec l u s t e r e di n t os u b j e c tc a t e g o r i e s ，a n dt h er e l a t i o n sb e t w e e ns u b j e c tc a t e g o r i e sa n dc o d e s a r ea n a l y z e d a c c o r d i n gt ot h et h e o r e t i c a lr e s e a r c hr e s u l t s ，i nt h i sd i s s e r t a t i o n ，s o m ea p p l i c a t i o ni s s u e s o nf u n d sm a n a g e m e n to fn a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o no fc h i n aa r ec o n d u c t e d m o r e s p e c i a l l y , w ea n a l y z et h ew h o l et r e n d sa n dr e g u l a t i o n so fb a s i cd i s c i p l i n er e s e a r c h ，t h ec u r r e n t s i t u a t i o n so fa l lt h es u b j e c tf i e l d sa n dt h e i rr e l a t i o n s t h e s ew o r k sc a na f f o r dp o w e r f u ld e c i s i o n s u p p o r tf o re s t a b l i s h i n go fd e v e l o p m e n tp r o g r a m sa n dd e v e l o p m e n ts t r a t e g i e s ，a n da d j u s t i n go f s u b j e c tc o d i n gs y s t e ma n dm a n a g e m e n to fp r o j e c t s k e yw o r d s ：k n o w l e d g em a n a g e m e n t ；k n o w l e d g ed i s c o v e r yf r o mt e x t s ；t e x tc a t e g o - r i z a t i o n ；t e x tc l u s t e r i n g 一一 独创性说明 作者郑重声明：本博士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名： 娜一日霸：塑里! 二， 大连理工大学学位论文版权使用授权书 本学位论文作者及导师完全了解“大连理工大学硕士、博士学位论文版权使用规 定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学将本学位论文的全部或部分内容 编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名： 日 导师签名： 日 大连理工大学博士学位论文 1 1 选题背景 第一章绪论 科学研究的过程是知识生产和知识创新的过程，科研管理其本质上是一种知识管 理，科研管理机构的主要工作就是对知识进行管理，特别是我国基础科学研究管理部 门，比如国家自然科学基金委员会更是典型的知识管理部门，其所管理的知识主要集 中在科研立项建议申请书( 以下简称申请书) 中。每一份申请书都是科研工作者长期 积累并经过仔细推敲而完成的，其中包含着广大科技工作者对于学科前沿、新兴学科 领域、热点冷点、学科发展趋势等的认识和把握，蕴含着大量的知识和智慧。 这些知识可以分为三个方面 1 ：实体知识、类( 概念) 知识和关系知识。所谓“实 体”这里指的是申请书，实体知识就是各个申请书中包含的知识；“类”是指根据申请书 内容的相似性所形成的项目类，类知识是对一类项目的知识的抽象；“关系”包括项目之 间的关系、项目与类之间的关系、类与类之间的关系等，关系知识就是对这些关系的 认知成果。利用这些知识可以发现我国基础研究和应用基础研究等有关学科整体发展 状况，发现学科发展的规律和特点，为科研管理部门制定科研发展战略、发展规划和 年度计划等提供决策支持。具体解决三个层面的应用问题： 一是面向基础研究整体发展的应用问题，包括：学科体系的构成( 内涵构成和外延 构成) 、学科体系的演变( 内涵演变和外延演变) 和学科体系的整体发展规律以及内涵交 叉、外延交叉状况等，为制定基础研究发展规划提供规律性的决策支持； 二是面向学科领域的应用问题，包括：发现研究的热点领域和冷点领域、发现交 叉研究领域、发现新学科生长点、发现衰落学科点等，为学科领域的调整和制定申报 指南提供决策支持； 三是面向项目管理的应用问题，包括：纠正研究内容与申报领域不符的项目、发 现交叉项目、发现雷同项目、发现重复申报项目、发现重复立项项目、发现疑似新项 目等，为项目管理提供决策支持。 这些知识都隐含在申请书文本中，为了把隐含的知识表示出来为科研管理所用， 就需要把知识从申请书文本中挖掘出来。但是，根据科学研究，特别是基础科学研究 的特点，对申请书中的知识进行挖掘会面临以下问题： 一、申请书的知识表示不能完全依赖于词典。科学研究的申请书中会不断地出现 文本挖掘算法及其在知识管理中的应用研究 大量的新术语、新词汇、新提法，并涉及新概念，任何词典都满足不了申请书内容分 析的要求。如何从申请书中发现新术语、提取出新概念，是需要解决的一个难点。 二、申请书研究内容与申报学科领域不能完全吻合。科研管理部门用代码来代表 学科领域，申请人根据申请书内容填报合适的代码。但是，由于申请者对学科领域的 理解不同，使得属于某个领域的申请书投到了另外的领域中，造成同一代码下的申请 书不都属于该代码所代表的学科领域。因此，有必要把投错领域的申请书归属到与之 内容相匹配的代码下。 三、学科代码体系结构与实际研究领域的体系结构不能完全一致。科研管理部门 提供的学科代码体系是人为设定的，但是申请书集合中隐含的科学研究体系与这个人 为设定的体系是有差异的，申请书中隐含的科学研究体系是广大科研工作者对科学发 展整体规律的共同认知成果。这个认知成果比人为设定的代码体系更客观、更实际。 需要根据全部申请书的分析来发现申请书集合中隐含的科学研究体系，用于提高科研 管理水平。 由于上述问题，现有的文本挖掘方法和技术不能完全适用于科研管理中申请书文 本的处理。所以，必须提出并研究新的文本挖掘方法以完善知识管理技术。 1 2 文本挖掘技术综述 目前，随着计算机网络技术的发展，各个方面的电子文档的数量急剧增长。其 中，大约有8 5 企业信息是以文本方式保存的 2 。因此，文本挖掘已经成为数据挖掘 中一个日益流行而重要的研究领域。与一般数据挖掘以关系、事物和结构化数据为研 究目标所不同，文本挖掘所研究的文本数据库，由来自各种数据源的大量文档组成， 包括新闻文章、研究论文、书籍、期刊、报告、专利说明书、会议文献、技术档案、 政府出版物、数字图书馆、技术标准、产品样本、电子邮件消息、w e b 页面等。这些文 档可能包含标题、作者、出版日期、长度等结构化数据，也可能包含摘要和内容等非 结构化的文本成分 3 】，而且，这些文档的内容是人类所使用的自然语言，计算机很难处 理其语义。因此传统的信息检索技术已不适应日益增加的大量文本数据处理的需要， 人们提出文本挖掘的方法进行不同的文档比较，以及文档重要性和相关性排列，或找 出多文档的模式或趋势等分析【4 】。遗憾的是，使用传统的基于逻辑的算法来处理文本 数据时，遇到了很大的困难。文本挖掘用来揭示隐藏于文本中的信息，一方面需要处 理自然语言中大量的词和结构，另一方面还要解决文本信息的不确定性、模糊性【5 。 文本挖掘作为数据挖掘的一个新主题，引起了人们极大兴趣。文本挖掘 一2 一 大连理工火学慧上学位论文 ( 删：t e x tm i n i n g ) 是在数据库知识发现( k d d ：k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 基础上发展起来的。文本挖掘，又称为文本知识发现( k n o w l e d g ed i s c o v e r yf r o mt e x t ) ， 是由u s a m am f e l d m a n 在1 9 9 5 年首次提出的【6 】，是指从非结构化的文本文档中抽取用 户感兴趣的、重要的模式或知识的过程，它可以看作是数据挖掘或数据库知识发现 ( k d d ) 的延伸。由于存储信息的最一般形式是文本，所以有人认为文本挖掘的商业 潜能甚至比数据挖掘还要高。当然，由于文本挖掘处理的对象是非结构化的文本数 据，所以它是一件很复杂的工作，涉及多个学科领域，如信息检索( i r ：i n f o r m a t i o n r e t r i e v e ) 、信息抽取( 匝：i n f o r m a t i o ne x t r a c t i o n ) 、自然语言处理( n l p ：n a t u r a l l a n g u a g ep r o c e s s i n g ) 、文本分析等技术，以及与这些技术相关的数据库知识发 现( k d d ) 的方法及算法，如数据挖掘( d m ：d a t am i n i n g ) 、机器学习( m l ：m a c h i n e l e a r n i n g ) 、自动聚类、自动分类、统计方法等。 文本挖掘有多种不同的定义。根据f a y y a d 等对知识挖掘的定义：知识挖掘就是从 数据集中识别出有效的、新颖的、潜在有用的、以及最终可被理解的模式的非平凡 。过程 7 ，8 】。k o s t o f f 坌f f 出了文本挖掘的定义：文本挖掘是从大型文本数据集中获取正确 的、潜在有用的并最终可被理解的知识的过程 8 】。同时，k o s t o 腊别将文本同数据作 了严格的界定，这里的文本是指以字符代码序列方式存储的，以自然语言表达的书面 文本 8 。 而n a h m 贝j j 参照数据挖掘的定义把文本挖掘定义为：文本挖掘是应用机器学习和统 计等领域的方法和算法，针对文本数据进行处理，目的是从文本数据中发现一些有用 的模式。为了这个目的，首先对文本进行相应的预处理是必要的。许多学者使用了信 息抽取方法、自然语言处理或其他一些预处理方法来对文本进行数据抽取，然后在抽 取的数据上应用数据挖掘算法【9 ，l o 】。 文本挖掘不但要处理大量的结构化和非结构化的文档数据，而且还要处理其中复 杂的语义关系。因此，现有的数据挖掘技术无法直接应用于其上。对于非结构化问 题，一条途径是发展全新的数据挖掘算法直接对非结构化数据进行挖掘，由于数据非 常复杂，导致这种算法的复杂性很高；另条途径就是将非结构化问题结构化，利用 现有的数据挖掘技术进行挖掘，目前的文本挖掘一般采用该途径进行。对于语义关 系，则需要集成计算语言和自然语言处理等成果进行分析。 文本挖掘的分析对象主要为文本内容，因此使用数据挖掘的方法就会遇到一些新 的问题，其中首要的一个问题是处理对象是非结构化的文本数据。文本挖掘结果的质 量，不仅依赖与所采用的算法，而且与文本表示方法、相似度计算方法等密切相关。 一3 一 文本挖掘算法及其在知识管理中的应用研究 文本挖掘的主要处理过程是对大量文档集合的内容进行预处理、特征提取、结构 分析、文本摘要、文本分类、文本聚类、关联分析等。我们按照文本挖掘的过程介绍 其涉及的主要技术及其进展。 1 2 1 特征提取 英文文本的特征提取，一般包括滤除停用词、词缀处理( s t e 蚰i n g ) 等过程。而汉语 与英语不同，汉语中词与词之间没有分隔符号，因此中文文本挖掘首先需要进行分词 处理。汉语自动分词是信息提取、信息检索、机器翻译、文本分类、自动文摘、自然 语言理解等中文信息处理领域的基础研究课题 11o 自动分词一直是中文信息处理研究 的一个热点和难点，其在理论和实用技术上仍存在很多问题，有待于进一步探索。目 前，研究者对中文文档自动分词己进行了大量研究，提出了许多分词方法，目前使用 较广、也较为成熟的是基于词典的机械分词。但是，机械分词的词典覆盖率有限，而 且对变化的应用领域适应性较差。对于中文文本挖掘来说，这类分词技术可能会使某 些具有重要意义的词汇被疏漏，从而导致挖掘的内容不是十分准确。 因此，一些学者致力于研究无词典分词方法，即不依靠词典把文档中的词提取出 来 i 2 - 1 6 1 。一个词是汉字字符的一种结合模式，但并不是每种结合模式都构成词，只 有那些具有确定语义或语法功能的汉字结合模式才是词。而在不使用词典的情况下， 由于缺乏先验知识，词是无法直接识别的。但在统计意义上，每个文档中的汉字结合 模式是可以观察的。如果一个词在一篇文档中重复出现的次数越多，则这个词就越容 易被识别出来，反之，这个词在文档中只出现一次或很少出现，则不易被识别。无词 典分词算法的主要思想就是利用汉字的结合模式在文档中重复出现的次数，来判断这 个结合模式是否是一个词。但是有些高频模式不一定是词，因此还需要对高频模式进 行过滤和筛选。 1 2 2 文本表示 用简单而准确的方法将文档表示成计算机能够处理的形式是进行文本挖掘 的基础。最经典文本形式化表示方法是6 0 年代末s a l t o m 等人提出向量空间模型 ( v s m ：v e c t o rs p a c em o d e l ) ，它最早用于信息检索 1 7 ，但现在已经用于包括文 本挖掘的多个领域。 v s m 使用一组正交的特征b - j ( t 】，t 2 ，如) 作为维向量来构造表示文档主题的n 维向 量空间。各个特征词在文档中的权重构成该文本的特征向量( 叫m 叫t 2 ，w 饥) ，对应于 一4 一 人连理工人学博士学位论文 空间中的一个点，用于表示文档政。最常用的特征向量使用t f i d f 函数计算文本特征的 权值 1 8 ，1 9 】： w j ：丝丝竺竺一 ( 1 1 1 ) = = = = = = = = = = 兰= = = = = = = = = = 【j v e ? ：1 南：叼( 尝+ o 0 1 ) 2 其中，这里埙j 表示词条j 在文本d 中出现的次数，表示文本集合d 中的文本总 数，表示集合d 中包含词条岛的文本数量。其本质是取词条岛在样本中的总频数亡岛为 权值，再g j l d f ( i n v e r s ed o c u m e n t 脚e n c y ) 因子z d 夕( 祟+ o 0 1 ) 乘以t 南，从而突出区分 度高的词条，抑制通用性的词条。为去除文档不同长度的影响，公式中对特征向量的 权值进行了归一化处理。 一般用来表示文本的向量空间模型都是建立在词频的基础上，但是，人们在表达 相同概念时，使用的词汇具有很大的不同，如个人的喜好，有人愿意用“电脑”一词，而 有人喜欢用“计算机”一词；也可能因为文章修辞的缘故，用词要求比较简洁，经常出现 同义替换的现象；或者词汇表达的概念层次有所不同。因此，仅仅依靠特征词的重复 而产生的频率信息是不够的。基于概念的文本表示则是将特征项映射到概念级，无疑 将有助于相近文档的识别能力。 j 文本相似性计算方法与文本表示方法密切相关，对于v s m 表示的文本， 一般使用夹角余弦、街区距离、欧式距离等计算方法。对于文本特征向 - 量d i = ( w t l ，t 3 i 2 ，叫饥) 及嘭= ( 嘶1 ，2 ，n ) ，d i 与呜之间的相似性主要有如下几种计算 方法： 夹角余弦 街区距离 毗= 耥= 喜( k ) m 2 ， 欧氏距离( e u c l i d e a nd i s t a n c e ) d ( d i ，由) = 一5 一 ( 1 3 ) ( 1 4 ) 蚴 一 请 彬 佗汹 = 略 也 d 文本挖掘算法及其在知识管理中的应用研究 夹角余弦计算结果反应了两篇文档之间的相似性，对于同一篇文档，计算结果 为1 。街区距离和欧氏距离的计算结果反应了两篇文档之间的距离，对于同一篇文档， 计算结果为0 。 对于给定的文档集合s ，其中心向量c 可以定义为： c ：高d ( 1 5 ) 两未d o 5 即中心向量的每个特征维度的权值为该特征在集合s 的所有文档向量中权重的平均 值。这样，可以使用夹角余弦、街区距离等公式计算文档与类别的相似性，或者计算 两个类别之间的相似性。比如使用夹角余弦公式，计算方法为： 1 2 3 文本分类技术 c o s i n e ( d ) c ) = 淼 c o s 饥e ( c ，2 高尚 ( 1 6 ) ( 1 7 ) 自动分类研究始于2 0 世纪5 0 年代末，l u h i l 在这一领域开始了开创性的研究 2 0 。我 国的自动分类工作始于2 0 世纪8 0 年代初期，大体上经历了从可行性探讨到辅助分类系 统再到自动分类系统三个发展阶段 2 1 。所谓的自动分类，是指用计算机代替人工，自 动产生能够表达知识资源内容特征的分类标识的一种知识资源加工方式。与人工分类 相比，它的优点是速度快，便于提高知识资源加工的质量和效率。 自动文本分类是人工智能和信息获取( r ) 技术相结合的研究领域，是进行基于 内容的自动信息管理的核心技术。国外在自动文本分类以及相关的信息检索、信息抽 取等领域进行了较为深入的研究。八十年代，自动文本分类以知识工程的方法为主， 根据领域专家对给定文本集合的分类经验，人工提取出一组逻辑规则，作为计算机自 动文本分类的依据。进入九十年代，基于统计的自动文本分类方法日益受到重视，它 在准确性和稳定性方面具有明显的优势。 文本分类是指在预先确定的分类体系下，根据文本的内容自动确定文本类型的过 程【2 2 _ 2 4 】。2 0 实际9 0 年代以前，占主导地位的文本分类方法一直是基于知识工程的分 一6 一 人连理工大学博士学位论文 类方法，即由专业人员手工进行分类。人工分类非常费时，效率过低。9 0 年代以来， 众多统计方法和及其学习方法应用于自动文本分类。文本分类是有指导的自动处理技 术，主要过程一般分为两步： s t e p1 由训练文本定义分类函数，建构文本分类器：输入训练文本的特征向量，返回此向 量与各个类别的相关值。此相关值在不同的分类器的涵义不同例如在贝叶斯分类 器中表示概率值，在r o c c h i o 分类器中则表示文本与类别在向量空间中的距离。 s t e p2 用所建构的文本分类器对测试文本进行分类：定义一个闽值，用来判断一篇文档 是否属于某个类别。给分类函数输入测试文本的特征向量求出测试文本与类别的 相关值，再与所定义的阈值比较，决定该文本是否属于所对应的类别。 文本分类技术的研究引起了研究人员的极大兴趣。目前英文自动分类已经取得了 丰硕的成果，提出了多种成熟的分类方法，如k 近邻分类( k n n ) 2 5 、基于质心的分类 算法( c o n t r o i db a s e dc l a s s i f i e r s ) j 2 6 ，通用实例集合( g e n e r a l i z e di n s t a n c es e t ) j 2 7 ，贝叶斯分 类( n a i v eb a y e s ) 2 8 以及支持向量机【2 9 】、决策树方法、回归模型和神经网络等方法， 但对于中文文本的自动分类技术还不尽人意。目前国内对自动文本分类算法也做了 较为深入的研究 3 0 ，2 1 ，3 l _ 3 6 】，其中中文文本分类研究主要集中在k n n 、朴素贝叶 斯 3 7 】、向量空间模型 3 8 ，3 9 和支持向量机 4 0 】等技术上。 1 k 近邻分类器( 心) 给定一个测试文档，k 近邻分类算法在训练集中查找离它最近的k 个邻居，并根据 这些邻居所属类别给该文档的候选类别评分。把邻居文档和测试文档的相似度作为邻 居文档所在分类的权重。如果这k 个邻居中的部分文档属于同一个分类，则对该分类中 的每个邻居的权重求和并作为该分类和测试文档的相似度。该方法的特点是允许文档 可以属于多个分类。通过对候选分类评分的排序，然后给出一个阈值，就可以判定测 试文档的分类。 在模式识别领域对k n n 算法的非常深入，在文本分类中，文献 4 l 】最早应用该算 法对新闻进行分类。文献f 4 2 首先使用夹角余弦公式计算测试文档和训练文档之间的相 似度，通过对相似度排序获得分类结果。文献 4 3 】对多种文本分类算法进行了比较， 由于k n n 算法具备了测试和健壮性等特点被选作基准分类方法。文献 4 4 】提出基于核的 距离加权心m 算法，解决了样本多峰分布、边界重叠问题核分类器的精确分类决策问 题。 一7 一 文本挖掘算法及其在知识管理中的应用研究 k n n 舅t 法是一种懒惰的学习算法，它需要存储所有的训练文档，新文档需要与所 以训练文档进行比较并选择最近的邻居，这导致它具有较高的存储代价，在分类时计 算开销也较大。对此问题有两种解决途径：其一是有效索引训练文档以便当新文档到 来时能够快速查找其潜在的邻居；其二是通过重抽样方法以减小训练文档集的规模。 前者需要在存储前就确定可能的邻居关系，后者在抽样过程中必然会丢失某些有用信 息而导致分类性能的下降。 2 r o c c h i o 方法 r o c c l l i o 方法 4 5 _ 4 7 为每个类别c ：计算一个分类器向量q = ( 毗l ，w i 2 ，毗n ) ，其 中w 让表示特征t 七在类别向量a 中的权重。w 镳通过下面公式计算： 由三& 两w j k 呐d j e n e g t i 。w 面 j k 8 ) 其中，伽缸表示特征如在类别文档d ，中的权重，p 0 & 表示属于类别g 的训练文档集 合，e g 表示不属于类别g 的训练文档集合。 公式1 8 表明，类别向量中的每个特征的权重都是由该特征在正类和负类中的权重 和的线性函数决定的。该方法易于实现且具有较高效率，但与其他线性分类器一样， 该方法的主要缺点在于线性地划分文档空间，对于非线性的情况，r o c c h i o 方法就不是 那么尽如人意了。 3 n a i v e 贝叶斯分类器 n a i v e 贝叶斯分类器 4 8 的基本思想是利用单词和分类的联合概率来估计给定文档 的分类概率。该方法假设词之间是彼此独立的，这个假设使得n a i v e 贝叶斯分类器比 非n a i v e 贝叶斯分类器要有效得多，因为它避免了使用词的组合作为预测变量。n a i v e 贝 叶斯分类假设不同单词存给定类别下的条件概率分布时相互独立的，其代表文章 有 4 9 5 u 等，但事实上，单词之间的独立性是不存在的。文献【5 2 从理论上证明了二维 独立性假设不会影响n a w e 贝叶斯分类器的有效性。文献 5 1 5 3 等用词代替文档作为事 件进行概率估计，目的是去除文档长度对分类结果的影响。 4 支持向量机( s v m ) 一8 一 大连理工人学博上学位论文 支持向量机分类方法由v a p 讪( 在1 9 9 5 年提出 5 4 ，用于解决二分类模式识别问题。 它在向量空间中找到一个具有最大边界的决策平面，它能”最好”地分割两个分类中的数 据点。决策平面可以写作叫z b = 0 ，其中z 是要分类的任意数据点，o 和常数6 通过训 练获得。s v m 的特点是决策平面由那些刚好和决策面距离为1 l l w i i 的数据点来决定， 称为决策向量，删除其他数据点不会影响算法的结果( 即产生的决策函数不变) 。支 持向量机的优点在于不需要进行词的选择且具有很高的防止过拟的能力。支持向量机 在分类应用中具有很好的效果，文献 5 5 】用s v m 对中文文本进行了分类处理。 文献 5 6 提出基于综合评价方法的多分类器决策机制，通过对多个分类器的最优化 的组合，获得最佳的分类精度。a n t o n i n ak l o p t c h e n k o 5 7 提出了原型匹配的聚类算法对 会议文章进行分类，包括单词和语句级别的快速文档编码方法，利用向量量化算法建 立单词和语句的柱状图，原型匹配步骤。鲍文等 3 5 应用k 觯法，以科技文献中的关 键词作为分类特征词条建立分类器，将9 6 篇文献分为4 个类别，可用于小样本集的数据 处理。文献 5 8 1 根据类别体系的层次结构，提出自项向下的逐层分类方法，可以提高分 类结果的精度并减少计算量。 对机器分类结果质量的评价，一般通过对比人工定义的分类数据来计算。通常通 过统计准确率( a c c u r a c y ，记为a ) 、召回率( r e c a l l ，记为r ) 、及f - m e a s u r e ( 记为f ) 等指标 来衡量分类结果 5 9 1 。这些指标的计算方法如下： a = 去静= 去喜掣 n 9 ， r = 去喜尼= 去姜掣 m f _ 去娄只= 去娄错