（计算机应用技术专业论文）基于图模型的web文档分类方法研究.pdf

论文题目： 指导 内蒙古科技大学硕士学位论文 基于图模型的w e b 文档分类方法研究 作者：张蓐 教师：重塑查壑望 协助指导教师： 单位：塑茎壹型苎奎堂 一一单位： 一 单位： 论文提交日期：2 0 1 0 年6 月f z 日 学位授予单位：内蒙古科技大学 s 一 一 基于图模型的w e b 文档分类方法研究 r e s e a r c ho nd o c u m e n tc l a s s i f i c a t i o nm e t h o db a s e do n g r a p hm o d a l 研究生姓名：张炼 指导教师姓名：孟海东 内蒙古科技大学信息工程学院 包头0 1 4 0 1 0 ，中国 c a n d i d a t e - l i a nz h a n g s u p e r v i s o r ：h a i d o n gm e n g s c h o o lo fi n f o r m a t i o ne n g i n e e r i n g i n n e rm o n g o l i au n i v e r s i t yo f s c i e n c ea n dt e c h n o l o g y b a o t o u0 1 4 0 l0 ，p r c h 、i a 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 内蒙古科技大学或其他教育机构的学位或证书所使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并 表示了谢意。 签名：拯煌二日期：丝应：臣：f 垄 关于论文使用授权的说明 本人完全了解内蒙古科技大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文。 ( 保密的论文在解密后应遵循此规定) 日期：型兰：鱼：! 至 声 一 内蒙古科技大学硕士学位论文 摘要 目前，一些比较成熟的文本分类算法已经被应用到了文本分类中，但它们大都是基于 向量空间模型( v e c t o rs p a c em o d e l ) 的。向量空间模型( v e c t o rs p a c em o d e l ) 将每篇文章 的处理转化为高维向量空间的向量计算，每一个分量表示一个词元权重，也就是把每篇文 章的处理转化为了向量的计算。这种方法降低了文档处理的计算复杂度，提高了处理速 度。但向量空间模型把文档看成词的集合，假设词与词之间是独立的，这样就损失了大量 的文本结构信息，而在自然语言中，词与词之间往往是相互关联的，所以文章的上下文之 间的联系也是非常重要的。为了解决这个问题，一些国内外学者提出了基于图模型的文本 表示方法。 为了实现图模型下的文本分类，本文对选用的语料库进行了预处理工作；分析了现有 的特征选择算法，选择了开方检验的方法对文本进行了特征选择；针对现有的计算权值的 方法进行了改进，找到了一种适合图模型下文本分类的权值计算方法；根据图模型的定 义，建立了文本的图模型；并找出一种计算相似系数的方法对文本进行了分类，完成了整 个图模型文本分类的整个过程。 本文从文本的预处理、特征选择、图模型的建立、图模型的相似系数的计算等几个文 本分类的重要环节，设计出了自己的算法，给出了一种图模型中计算权值的具体方法，建 立了有权无向图，并对这些算法进行了实现。选用了s o u g o u 语料库的3 个类雯3 1 j c 8 财经 类、c 1 01 t 类和c 1 3 健康类进行实验，分析了准确率( p ) 、召回率( r ) 和f 1 值这些评价 文本分类算法的结果，并得出结论，证明了图模型文本分类算法是一种有效的文本分类算 法。 关键词：权重；文本图；文档分类 内蒙古科技大学硕士学位论文 a b s t r a c t a tp r e s e n t , s o m ec o m p a r a t i v e l ym a t u r et e x tc l a s s i f i c a t i o na l g o r i t h mh a sb e e na p p l i e dt ot e x t c l a s s i f i c a t i o n , b u tm o s to fi ti sb a s e do nv e c t o rs p a c em o d e l ( v e c t o rs p a c em o d e l ) v e c t o rs p a c e m o d e l ( v e c t o rs p a c em o d e l ) t u r n se v e r ya r t i c l ei n t oal l i g hd i m e n s i o n a lw 碰昕s p a c ev 咖 c a l c u l a t i o n , e a c hc o m p o n e n tr e p r e s e n t sat e r mw e i g h t s , t h a ti s t ot r a n s f o r mt h ep r o c e s s i o no fe v e r y a r t i c l ei n t ot h ec a l c u l a t i o no fv e c t o r t h i sm e t h o dr e d u c e st h ec o m p u t i n gc o m p l e x i t yo fd o c m n e n t p r o c e s s i n g , a n di n c r e a s e dp r o c e s s i n gs p l e e db u tt h ev e c t o rs p a c em o d e lt a k e st h ed o c u m e n t 雒a c o l l e c t i o no fw o r d s ，a n da s s u m e se a c hw o r di si n d e p e n d e n t , 8 0t h a t1 0 s sal o to ft e x ts m w t m e i n f o r m a t i o n w h i l ei nn a t u r a ll a n g u a g e , i ti so f t e ni n t e r r e l a t e db e t w e e nw o r da n dw o r d , t h e r e f o r e , t h e l i n kb c t v c e e i lt h ec o n t e x t so ft h ea r t i c l ei sa l s ov e r yi m p o r t a n t i no r d e rt os o l v et h i sp r o b l e m , s o m e s c h o l a r sp r o p o s e dg r a p h - m o d e l - b a s e dt e x tr e p r e s e n ：c a ：t i o m i no r d e rt oa c h i e v et h ed o c u m e n tc l a s s i f i c a t i o ni ng r a p hm o d e l , t h i s p a p e rp r e t r e a t st h ec o r p u s s e l e c t e d , a n a l y s e sp r e s 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 , c h o o s e st h em e t h o do fe x t r a c t i o nt e s tt om a k e f e a t u r es e l e c t i o n , i m p r o v e st h em e t h o do f w e i g h tc a l c u l a t i o n , f i n d sam e t h o do f w e i g h tc a l c u l a t i o nt o c l a s s i f yt e x ti ng r a p hm o d e l ，e s t a b l i s h e st h eg r a p hm o d e lo ft h et e x ta c c o r d i n gt oi t sd e f i n i t i o n , f i n d s am e t h o do fc a l c u l a t i n gs i m i l a r i t yc o e f f i c i e n t st oc l a s s i f yt h ed o c u m e n t s , a n dc o m p l e t e st h ew h o l e p r o c e s so f g r a p hm o d e ld o c u m e n tc a t e g o r i z a t i o n f r o mt h ea s p e c t so fs o m ei m p o r t a n tc o m p o n e n to ft e x tc l a s s i f i c a t i o nl i k et h ep r e t r e a t m e n t t r a i n i n g , f e a t u r es e l e c t i o n , e s t a b l i s h m e n to fg r a p hm o d e l , a n dc a l c u l a t i o no fg r a p hm o d e ls i m i l a r i t y c o e f f i c i e n t s , e t c ，t h i sp a p e rd e s i g n si t so w na l g o r i t h m , s u g g e s t sam e t h o do fw e i g h tc a l c u l a t i o ni n g r a p hm o d e l ，e s t a b l i s h e su n d i r e c t e da n dw e i g h t e dg r a p h , a n di m p l e m e n t st h e s ea l g o r i t h m s ；i tm a k e s e x p e r i m e n tb ys e l e c t i n g3c a t e g o r i e so f s o u g o uc o r p u s , c 8e c o n o m i e s , c l oi t , c 1 3h e a l t h , a n a l y s e s t h er e s u l t so fe v a l u a t i n gt e s tc l a s s i f i c a t i o na l g o r i t h ml i k ep r e c i s i o nr a t e , r e c a l lr a t ea n df 1 ，a n d c o n c l u d e st h a tt h eg r a p hm o d e lt e x tc l a s s i f i c a t i o na l g o r i t h mi sa ne f f e c t i v ed o c m n e n tc l a s s i f i c a t i o n a l g o r i t h m k e yw o r d s ：w e i g h t ；d o c u m e n tg r a p h ；d o c u m e n tc l a s s i f i c a t i o n n 内蒙古科技大学硕士学位论文 目录 摘要1 a b s t r a c t i i ll 者论1 1 1 课题的研究背景1 1 1 1w e b 文档分类的背景1 1 1 2 文本分类的意义。l 1 1 3w e b 文档分类的提出1 1 2 国内外研究现状及意义2 1 2 1 现实意义2 1 2 2 理论意义4 1 3 课题的提出5 1 3 1 现有文档分类的算法5 1 3 2 向量空间模型的特点6 1 3 3 图模型提出6 1 4 课题的主要工作7 1 5 论文的结构和组织7 2 文本分类关键技术的研究8 2 1 文本分类的意义8 2 2 文本的词频统计8 2 2 1 中文分词8 2 2 2 语料库的预处理及结果10 2 3 特征选择方法的比较1 1 2 3 1 文档频率法( d f ) 。1 2 2 3 2 信息增益法( i g ) 1 2 2 3 3 开方检验法( c h i ) 13 2 3 a 互信息法( m i ) 。1 4 2 3 5 论文中的特征选择结果15 2 4 特征权重计算方法的研究与改进18 2 4 1 布尔权重法l8 2 4 2t f 权重l9 2 4 3i d f 权重19 2 4 4t f i d f 权重19 2 4 5t f i d f i i ： ：! ( ) 2 4 6 改进后的( t f i d f i g ) “公式2 0 3 文档分类算法模型的研究与比较2 1 内蒙古科技大学硕士学位论文 3 1 贝叶斯模型。2 l 3 2 支持向量机s 儿2 2 3 3k n n 算法。2 3 3 4 决策树算法2 4 4 文本表示方法的研究。2 5 4 1 布尔模型( b o o l e a nm o d e ) 。2 5 4 2 概率模型( p r o b a b i l i s t i cm o d e ) 。2 5 4 3 向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 。2 6 4 4 图模型( g r a p hm o d e ) 。2 8 5 图模型算法的设计与实现3 0 5 1 图的表示方法3 0 5 1 1 图的定义3 0 5 1 2 图的建立方法。3 0 5 1 3 图相似性的度量3 4 5 2 基于图模型的文本相似度的计算3 4 5 2 1 最大公共子图的算法3 4 5 2 2 特征加权法计算相似系数3 5 5 2 - 3 图模型的文档分类算法。3 6 5 3 算法实现3 6 5 3 1 课题的研究步骤3 6 5 3 2 实验测试的数据集3 8 5 4 实验结果及分析4 3 结论4 6 参考文献。4 7 在学研究成果51 致谢5 2 内蒙古科技大学硕士学位论文 1 绪论 1 1 课题的研究背景 1 1 1w e b 文档分类的背景 网络上大量的网页在为人们提供丰富多样、及时有效的信息资源，同时，也为人们 带来了如何快速有效从中获取其所需资源的挑战。为了能够及时有效地组织、处理庞大 的w e b 信息，人们希望能够按照网页的内容实现对其的自动分类。事实上，w e b 文本 自动分类技术已在主题搜索、数字图书馆、搜索引擎的目录导航、个性化信息检索、主 动信息推送服务、信息过滤等领域得到了广泛的应用l l j 。w e ；b 网页自动分类技术已经成 为互联网的研究热点，而文本分类技术则是网页自动分类技术中的核心基础【2 j 。 1 1 2 文本分类的意义 文本分类是指分析文本内容并按一定的策略把文本归入一个或多个合适的类别的应 用技术【j j 。随着i n t e m e t 的出现，大量的文字信息开始以计算机可读的形式存在，以传 统的手工方式对这些信息进行组织整理既费时费力且效果不理想，文本分类由于利用机 器来对文本进行分析整理，使用户从繁琐的文档处理工作中解放出来，并能极大地提高 信息的利用率，而受到越来越多的重视，已广泛应用于文本处理和文本检索的各个领 域，成为处理和组织大规模文本信息的关键技术，并推动了信息处理朝着自动化的方向 发展。 文本自动分类的研究是文本挖掘领域里的一个重要分支，是数据挖掘领域中对复杂 类型数据的挖掘技术。因而，文本挖掘成为数据挖掘与信息检索两门学科的交叉边缘学 科，近年来己经成为一个相对独立的研究学科，取得了长足的发展。但是，文本挖掘又 与传统的数据挖掘有很大的区别。传统的数据挖掘所处理的数据是结构化的，其特征数 目通常不超过几百个。而文本挖掘所处理的文本数据无结构可言，特征数目也相当庞 大，传统数据挖掘与信息检索的技术根本不可能处理这种超大规模的数据，必须研究新 情况下文本的自动分类技术h 。 1 1 3w e b 文档分类的提出 为了帮助人们有效地组织和管理海量的w e b 信息，w e ；b 文档分类技术应运而生， 它是w e b 数据挖掘的主要内容，是在文本分类的基础上发展起来的昀。它同时也是数据 内蒙古科技大学硕士学位论文 挖掘、智能信息检索和处理领域的一个新兴和重要的研究方向，也是一门交叉学科，融 合了信息网络、人工智能等多领域学科知识，涉及面较广州。w 曲文档分类通过利用 w e b 文档的正文文本信息和h t m l 语言结构信息，针对w e b 文档的内容进行相似度的 分类。w e b 文档分类不仅可以在较大程度上解决网上信息杂乱的现象，并方便用户准确 地定位所需的信息和分流信息，而且逐渐与搜索引擎、信息过滤、文本数据库、数字化 图书馆等信息处理技术相结合，有效地提高了信息服务的质型儿。 1 2 1 现实意义 自动文本分类的研究始于2 0 世纪5 0 年代末，到目前，文本自动分类在国外经历了 三个发展阶劂： 第一阶段( 1 9 5 8 - - - , 1 9 6 4 ) ：主要进行文本自动分类的可行性研究，在此期间，m 公司的h p l u h n 在这一领域进行了开创性的研究，提出了采用词频统计提取摘要的思 想【2 4 】。1 9 6 0 年，m a r o n 在j o u r n a lo fa s m 上发表了关于文本自动分类的第一篇论文 o n r e l e v a n c e , p r o b a b i l i s t i ci n d e x i n ga n di n f o r m a t i o nr e t r i e v a l 。 第二阶段( 1 9 6 5 , - 一1 9 7 4 ) ：进行文本自动分类的实验研究，1 9 7 1 年，r o e e h i o 提出 了在通过用户的反馈来修正权重向量，来构成简单的线性分类器。m a r kv a nu d e n 、m u n 等给出了其他的一些修改权重的方法。 第三阶段( 1 9 7 5 - 至今) ：自动分类进入实用化阶段，1 9 7 9 年，v 龃r i j s b e r g e n 对 信息检索领域的研究做了系统的总结，提出的信息检索的一些概念，如向量空间模型 ( v e c t o rs p a c em o d e l ) 和评估标准，如准确率( p r e c i s i o n ) 、召回率( r e c a l l ) ，后来 被陆续地引入文本分类中。 1 9 9 2 年l e w i s 发表了他的博士论文r e p r e s e n t a t i o na n dl e a r n i n gi ni n f o r m a t i o n r e a - l o y a l ，文中系统地介绍了文本分类系统实现方法的各个细节，并且在自己建立的数 据集r e u t e r s 2 2 1 7 3 上进行了测试。这篇博士论文成为文本分类领域的经典之作。后来的 研究者在特征降维和分类器的设计方面作了大量的工作。y i m i n gy a n g 对各种特征选择 方法，包括信息增益( i n f o r m a t i o ng a i n ) 、互信息( m u t u a li n f o r m a t i o n ) 、开方统计量 等，从实验上进行了分析和比较例。她在1 9 9 7 年还对文献上报告的几乎所有的文本分 类方法进行了一次总结，在公开数据集r e u t e r s 2 1 5 7 8 和o h s u m e d 上比较了各个分类 器的性能，对后来的研究起到了重要的参考作用p j 。 1 9 9 5 年，v i p n i k 提出了基于统计理论的支持向量机( s u p p o r tv e c t o rm a c h i n e ) 方 法，基本思想是寻找最优的高维分类超平面u u j 。支持向量机以成熟的小样本统计理论作 内蒙古科技大学硕士学位论文 为理论基础，因而在机器学习领域受到广泛的重视。t h o r s t e nj o a c h i m s 第一次将线性核 函数的支持矢量机用于文本分类，与传统的算法相比，支持向量机在分类性能上有了非 常大的提高，并且在不同的数据集上显示了算法的鲁棒性。至今，支持向量机的理论和 应用仍是研究的热尉j 。 在支持向量机出现的同时，1 9 9 5 年及其后，以y o a v f r e u n d 和r o b e r t e s c h a p i r e 发 表的关于a d a b o o s t 的论文为标志，机器学习算法的研究出现了另一个高峰。r o b e r te s c h a p i r e 从理论和试验上给出a d a b o o s t 算法框架的合理性。其后的研究者在这个框架 下给出了许多的类似的b o o s t i n g 算法，比较有代表性的有r e a la d a b o o s t ，g e n t l e b o o s t ，l o g i t b o o s t 等。这些b o o s t i n g 算法己被应用到文本分类的研究中，并且取得和支 持向量机一样好的效梨“1 。 到2 0 上世纪九十年代，随着网络信息的骤增，大规模的文本分类和检索成为研究 的重点。由于人工智能技术的不断成熟，研究者开始把专家系统技术引入到文本自动分 类领域。专家系统是一种在某特定领域以人类专家的水平去解决该领域问题的计算机程 序，一般由知识库和推理机两大基础部分组成。文本分类系统首先通过在预先分类好的 文本集上训练，建立一个判别规则或分类器，从而对未知类别的新样本进行自动归类。 大量的实验结果表明它的分类精度比得上专家手工分类的结果，并且它的学习不需要专 家干预，能适用于任何领域的学习，使得它成为目前文本分类的主流方法【i 引。 国内对文本分类研究比较晚，1 9 8 1 年，侯汉清教授首先探讨和介绍了国外文本分 类的研究情况，从计算机管理分类表、计算机分类检索、计算机自动分类、机编分类表 等四个方面介绍了国外的发展概况。随后，国内很多学者在这方面进行了比较深入的研 对3 1 。 1 9 8 6 年，上海交大电脑应用技术研究所的朱兰娟、王永成等开发的中文科技文献 ( 计算机类) 实验性分类系统。1 9 9 5 年，清华大学电子工程系的吴军研制的汉语语料 自动分类系统，以语料相关系数作为分类依据，以字频、词频及常用搭配为补充，采用 停用词表排除非特征词，进行人工指导分类u 耳j 。1 9 9 8 年，东北大学的计算机系的张月 杰、姚天顺研制的新闻语料汉语文本自动分类模型，通过计算预定义类别和文本特征项 之间相关性来进行自动分类。1 9 9 9 年，邹涛、王继成等开发的中文技术文本分类系统 c t d s ( c h i n e s et e c h n i c a ld o c u m e n tc l a s s i f i c a t i o ns y s t e m ) 采用了向量空间模型和基于统 计的特征词提取技术，能够根据文本的具体内容将其分配到一个或多个类别u 川。 相比于英文文本分类，中文文本分类的一个重要的差别在于预处理阶段：中文文本 的读取需要分词，不像英文文本的单词那样有空格来区分。从简单的查词典的方法，到 后来的基于统计语言模型的分词方法，中文分词的技术已趋于成熟。比较有影响力的当 内蒙古科技大学硕士学位论文 属中国科学院计算所开发的汉语词法分析系统i c t c l a s ，现已公开发布供中文文本分 类的研究使用i l o j 。 长期以来，没有专门的适合中文文本分类研究的数据集，研究者们大都采用英文语 料库( 如路透社的r e u t e r s 2 1 5 7 8 数据集) ，这使得分类算法难以比较。现在采用较多的 中文测试集有：北京大学建立的人民日报语料库、清华大学建立的现代汉语语料库、复 旦大学李荣陆博士整理的语料库、中科院谭松波博士制作的t a n c o r p v l 0 语料库掣j 。 其实一旦经过预处理将中文文本变成了样本矢量的数据矩阵，那么随后的文本分类过程 和英文文本分类相同，也就是随后的文本分类过程独立于语种剐。因此，当前的中文文 本分类主要集中在如何利用中文本身的一些特征来更好地表示文本样本。 1 2 2 理论意义 1 2 2 1w e b 文档分类基本依据 基于内容分类是指按照预先定义的基于内容的主题类别c ( c = c l ，c 2 ，c 山，这 里的c t 可以是并列的，也可以是分层次组织起来的，为文档集合中的每个文档 d i ( i = l ，曲确定所属的类别刈。 基于性质分类方法就是将文档按照其自身性质进行分类。基于性质分类属于文本分 类的一种，同基于内容分类一样，都是将文档分到已有的类别体系中，所不同的是基于 性质分类是按照文档的性质划分，将其分为新闻页、论坛页、广告页等等 2 0 l 。w 曲文 档的基于性质分类可以更好的管理和利用网络的日益增长的信息资源，使用户能够在性 质层面上处理文档，更方便地对资源进行查找川。 1 2 2 2 两类分类方法的比较与分析 1 _ ) 两类分类方法的相同点 从两种分类方法的背景来看，两者都是在文本分类的基础上，结合超文本的结构信 息发展起来的算法。它们都产生于网络信息迅速膨胀时代，适用了管理和查找海量信息 的需求。从两种分类方法的算法思想来看，它们都是在文本分类的基础上发展起来的， 所以二者都可以借鉴和使用文本分类算法的思想，因此它们在算法思想上具有一定的相 似性。性质分类和内容分类的主体算法都是采用文本分类思想，另外各自还有一些辅助 的算法，用于提高分类的准确性懈j 。从两种分类方法所处理的对象来看，它们的处理对 象都是w e b 文档，也就是半结构化的信息，因此处理的难度都非常大。从两种分类方 法的发展前景来看，随着网络上信息在成指数的增长，人们迫切需要性质分类和内容分 类这样的技术来处理信息j 。目前，尽管内容分类已经发展了很长时间，并取得了很大 的成就，但还是跟不上网络的发展步伐，不能够达到人们自如运用信息的目标。性质分 类则提出不久，发展到人们所期望的地步还需要一段时间，因此，这两种分类方法都需 要进一步的改善，以满足人们的需求。从两种分类方法的应用领域来看，性质分类和内 内蒙古科技大学硕士学位论文 容分类都是应用于网络信息分类的技术，处理对象相同，因此应用领域也有很大的相似 之处。二者都用于管理和规范网络信息，因此在搜索引擎、邮件分类、学习用户兴趣、 网页推荐、图书馆学、情报学等方面均有相应的应用 2 4 1 。 2 ) 两种分类方法的不同点 尽管两者都是w e b 文档分类技术，但其分类的具体含义不同。内容分类是将网页 按照所含的文件内容进行分类，把所有与某一内容相关的网页分为一类，而不在意这些 网页中所包含的内容是属于新闻还是评论或是其它什么性质。对于性质分类来说，它并 不考虑网页内容的相关性，而是考虑网页性质的相关性p j 。二者依据的标准不同，因此 分出来的类别也大相径庭。从算法的具体过程来看，尽管两者的分类思想相同，主体算 法也都是文本分类技术，但二者算法的具体实现过程不同，其中主要的不同点就是特征 提取和选择算法不同。内容分类主要考虑网页的主体内容，因此一般是先删除所有的 h t m l 标记，然后再对网页的文本进行分词和特征提取，几乎不考虑h t m l 的结构信 息。而性质分类则十分依赖h t m l 的结构信息，它需要根据这些信息找到特定位置的 特征，再根据这些特殊的特征对网页进行性质分类刚。性质分类算法几乎不考虑网页的 正文内容。正是性质分类和内容分类二者分类时所依据的标准不同，分出来的类别属性 也不同，因此二者的分类体系结构自然差别很大。内容分类是按内容的类别划分体系结 构，性质分类的体系结构则按照网页性质进行构造，如分为论坛页、广告页掣2 7 j 。二者 是对网页进行不同层面、不同方向的划分，尽管它们的类别体系结构图都是树形结构， 但各类的类名称与属性都不同幽j 。从两者的发展状况来看，内容分类作为w e b 文档分 类的主流技术，已经发展了很长时间，并在多个领域和方面取得了显著的应用，它曾一 度是w e ；b 技术研究领域的一大热点，即使在内容分类技术日益成熟的现在，也仍然有 无数研究者在研究如何改进和增强它的性能。对于性质分类而言，它仅是近年来一些学 者提出的一个较新概念，理论还不完善，技术也并不成熟，但它符合人们对处理网络信 息的需求，因此，性质分类具有广阔的发展空间。 1 3 课题的提出 1 3 1 现有文档分类的算法 目前，一些比较成熟的文本分类算法已经被应用到了w e ；b 文本分类中，其中有基 于v s m 的向量距离法、贝叶斯分类算法、o n 分类算法、b o o s t i n g 、n a i v eb a y e s 、 n n e t 、l l s f 、k n n 方法、支撑向量机s v m 算法、决策树分类算法和神经网络分类算 法等等，近些年还出现了基于粗糙集合理论的文本分类算法和一些结合多种方法的混合 内蒙古科技大学硕士学位论文 分类方法t 2 9 1 。这些文本分类算法取得了较为理想的分类效果。然而，在如此众多的方法 中，它们大都是基于向量空间模型( v e c t o rs p a c em o d e l ) 的。 向量空间模型( v e c t o rs p a c em o d e l ) 是由s a l t o n 教授等人在1 9 6 8 年提出并发展起 来的文档表示方法。基于这种模型每篇文档都形式化为高维向量空间中的一个向量， 向量中的每个分量对应文档的一个特征词条的权重。词的权重一般采用t f i d f 的计算 方法【3 1 1 。 ， 1 3 2 向量空间模型的特点 优点：把对文本的处理转化成向量空间中的向量运算，使得问题的复杂度大为降 低，提高了文本处理的速度1 3 2 1 。 不足：由于向量空间模型是一种不考虑特征项出驯顿序的词袋文本表示模型，这种 模型虽然带来了计算和操作上的方便，但却损失了大量的文本结构信息，以及缺乏对特 征词条上下文环境的考虑。而这些文本结构信息或者上下文环境在自然语言中是至关重 要的。因此，从自然语言的角度来看，向量空间模型还是很不完善的幽j 。 1 3 3 图椟酿出 针对向量空间表示模型的缺陷，许多学者提出了基于图模型的文档表示方法。如 s v e t l a n a 在其论文中提出的基于辅助词典v e r bn e t 和w o r dn e t 的文档概念图表示模 型：b h o o p e s h 和p u s h p a k 在他们的论文中提出了根据u n l 图来构造代表文档的特征向 量，并采用s o m 技术对文本进行聚类；还有i n d e rj e e l ：和e r i c 在他们的论文中也提出了 用于多文档摘要提取的文档图模型表示方法 3 4 1 。这些图模型很好地体现了文档的语义信 息。 一个文本是由带有一定语义信息的句子构成的序列，同时句子又是由带有一定语义 信息的词条构成的序歹l j 【川。词条是反映文本语义信息的最小单元，但并非所有的词条都 能反映文本的语义信息，相反，只有少量的特征词汇。基于这种思想，就有了文本表示 的布尔模型 3 6 1 。 然而，大量的实践表明，这种模型还是很不完善的。于是就产生了向量空间模型。 向量空间模型是用特征词条及其频度来反映文本的语义信息的，它是目前应用最多而且 比较好的模型，它的缺点是不能反映文本的结构信息，但它是比较成功的j 。 因此，从外部特征来反映文本的语义信息，最好是能充分利用特征词条及其出现频 度这些信息。还有，一个词条的语义总是处在变换发展中，并且同一个词条还可能有多 种语义解释p 引。因此，理解词条的语义信息，需要根据其上下文信息。同时，a d a m s c h e n k e r 等人在其文献中指出，特征词条的位置关联信息，是一种反映词条上下文信息 内蒙古科技大学硕士学位论文 的很好的手段。基于这种思想，他们建立基于特征词条布尔关联的文档图表示模型，用 图的基本元素( 顶点和边) 来度量图的相似性，取得了很好的聚类效果。综上，如果从 文本的外部特征来反映其语义信息，特征词条、特征词条的频度及其特征词条的位置关 系，都是些非常重要的内科3 9 1 。就从这些角度出发，建立了一种新的基于图的文档表示 模型。 1 4 课题的主要工作 本课题的工作是研究图模型下的文本分类方法，研究目标是通过考虑文本的结构信 息而提高文本表示模型的表达能力从而优化文本分类性能。本文主要思路：首先选择测 试语料库作为实验数据；然后对测试语料库进行切词、分词、去除停用词等预处理工 作，使用特征词提取算法提取出文本的特征词，之后根据图模型的建立方法建立文本的 图模型，最后对文档进行分类，测试及评价分类效果。 1 5 论文的结构和组织 第一章绪论，简要介绍课题的研究背景、现状及论文的结构安排。 第二章阐述了文档分类关键技术的研究。 第三章阐述了文档分类算法模型的研究与比较。 第四章阐述了文本表示方法的研究。 第五章设计与实现了图模型算法。 第六章结论，对论文的工作进行总结并提出进一步的研究方向。 内蒙古科技大学硕士学位论文 2 1 文本分类的意义 文本分类是指把一个文本按照一定的标准归入一个或多个特定的类别的应用技术， 随着i n t e m e t 的大力普及和发展，网络上的文本信息爆炸式增长，以传统的手工方式进 行筛选、整理和分类难以满足信息海量增长的需要，而且耗费了大量的人力物力效果还 不理想。由此自动文档分类技术也就应运而生，使用计算机对文本进行分析、整理节省 了大量的时间，也使人们从大量的、繁琐的文本处理工作中解脱出来，大大提高了工作 效率和信息的利用率 4 0 1 。现今，自动文本分类和检索已经广泛应用到了各个领域，成为 大量文本信息组织处理的关键技术，使信息处理迈向自动化的发展方向j 。 2 2 文本的词频统计 为了提高文本表示的质量，减少文档表示的噪音数据同时也提供分离器的训练和分 类效率，在文本分类时，我们现有对文本进行预处理工作。在通常的预处理工作中，主 要包括去除停用词、代词、连词、介词等虚词，也就是对文本内容区分无意义的词1 4 2 j 。 预处理工作在文本分类过程中是非常重要的，预处理的好坏直接影响分类结果的准确 度。数据预处理的任务就是剔除文本中对文本分类作用不大的词，只剩下那些对文本区 分对大的词，并把文本转化成以词元为单位的的集合。 2 2 1 中文分词 一篇文章是由句子的序列组成，一个句子是由词语的序列组成。词是能独立表达语 义的最基本的单位j 。但对于中文文本来说，词与词之间没有明显的分界线，若要使计 算机与人类达到自由无障碍的语言交互，就必须让计算机能理解自然语言。只有当汉字 串组成的句子被准确地转化为词之后，才能继续进一步工作。分词，就是将一段文字， 按照语义上的最小单位切割开来，再把无意义的词，停用词，对文档分类区分度较小的 词去掉的过程。是处理文本信息最基础、最关键的一步1 4 4 j 。 在信息化产业的大力推动下，自动分词技术引起了人们的广泛关注，对自动分词技 术的要求也越来越高。在文本信息处理领域，国外水平大大领先于我国。英文在自动分 词这个阶段技术已经非常成熟，在自动摘要，信息检索等领域已经展开了良好的应用。 中文分词系统虽然有了一定程度的突破，但实用的中文分词系统还没有大规模的展开。 目前中文信息处理技术被广泛应用，人们迫切要求实现中文词典和语料库等中文信 息的共享和复用，对自动分词技术的要求也越来越高。在信息产业需求的强大动力推动 内蒙古科技大学硕士学位论文 下，自动分词已经引起多方面的关注，成为中文信息处理的一个前沿课题。中文的自动 分词技术虽然已经有一定程度的突破，能满足一般实用性的要求，但是实用的自动分词 系统至今尚未针对大规模真实文本展开。这要求有相当可用性的自动分词系统，而自动 分词系统的好坏，在目前语义分析的基本框架和理论下，成为中文文本语义分析的基础 【3 1 o 词是最小的能够独立活动的有意义的语言成分。但汉语是以字为基本的书写单 位，词语之间没有明显的区分标记，因此，中文词语分析是中文信息处理的基础与关 键。为此，中国科学院计算技术研究所在多年研究基础上，耗时一年研制出了汉语词 法分析系统i c t c l a s ( 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 c x i c a la n a l y s i s s y s t e m ) 。本文选用的切词系统是中科院计算所汉语词法分析系统i c t c l a s 。 在 i c t c l a s 官方网站h t t p ：w w w i c t c l a s o r g 上免费下载。 分词结果举例如下： 例如一段文章为：目前，t d 测试在全国几个城市进行得如火如茶，但在历次产品 测试过程中，也曾暴露出测试仪器、仪表等技术储备不足等问题，吸纳该领域企业加盟 被提到联盟组织者的计划中。上述类型的企业加盟似乎在意料之内。据悉，此次加盟企 业的内部审核在上月底t d 联盟的内部会议上已经通过。 切词的结果为：目献，w dt d x 测试，v n 都全国n