（计算机系统结构专业论文）中文文本分类研究.pdf

山东大学硕士学位论文 摘要 文本分类和聚类是现代搜索引擎设计的重要计算，也是在数据处理、数 据挖掘等应用中的关键计算因此对文本分类和聚类技术研究不仅具有重 要的理论意义，而且具有广阔的应用领域。 随着国际互联网的普及和目前针对w e b 网页的信息检索技术的研究， 对文本分类和聚类的研究已经不仅仅是文本文件，对w e b 网页的分类和聚 类已经成为新的研究热点。 。本论文在研究对一般文本的分类和聚类算法以及实现技术的同时，也 专门研究对w e b 网页的分类和聚类算法及实现技术。 本文的主要贡献是： i ) 深入地研究了对文档特征的提取方法和文档分类方法，通过比较， 分析了各种方法的优缺点。在此基础上，对传统的支持向量机分类法进行 了改进。对传统的支持向量机中的核函数进行了组合的研究，提出了由径 向基核函数( r b f ) 和多项式核函数( p o l y ) 组合成的新的核函数。实验表明 支持向量机在组合后的核函数下能取得更好的分类效果。 2 ) 基于对传统的特征选取方法和文本分类方法的分析，针对w e b 网页 具有半结构化的特点，提出了一种结合结构信息和内容的对w e b 网页按层 次进行分类的方法，克服了传统分类中轻视或忽略了w e b 网页的结构信息 的不足其主要思路是利用w e b 网页的结构信息对网页进行大类层次上的 粗分，然后利用网页中的全文信息再进行细分。实验结果表明，该层次分 类方法能有效地提高分类的精度和效率。 3 ) 本文对多分类器的组合问题进行了初步研究，提出了用n a i v eb a y e s 组合两种分类器对w e b 网页进行协调分类的方法，实验结果显示这是协调 超文本分类中多种分类器的一种有效方法。与只用单种方法对超文本进行 分类相比，综合分类法有效地提高了分类的正确率。 本论文的组织如下：在第1 章中介绍了文本自动分类在国内外的研究 现状。第2 章给出了文本分类的基本概念、经典的理论模型、特征提取技 山东大学硕士学位论文 术、分类模型以及我们改进的支持向量机模型，并给出我们算法和k 最近 邻( k n n ) 算法以及朴素贝叶斯算法的比较。第3 章介绍了我们基于分类 法、w e b 网页的结构信息和内容信息的层次分类方法；并通过实验验证我 们算法的有效性。第4 章讨论了多分类器的组合问题的研究。第5 章总结 了全文。 关键词：文本分类：w e b 网页分类；特征选取；k - 最邻近法；支持向量机 i i 山东大学硕士学位论文 a b s t r a c t t e x tc a t e g o r i z a t i o na n dc l u s t e r i n ga r et w oi m p o r t a n c ec o m p u t a t i o n si nt h e d e s i g n o fw e bs e a r c he n g i n e s ，w h i c ha r ea l s ot h ec r u c i a lc o m p u t i n gi n a p p l i c a t i o n s ，e g d a t ap r o c e s s i n g ，d a t am i n i n ge t c ，s ot h er e s e a r c ho nt h et e x t c a t e g o r i z a t i o n a n dc l u s t e r i n gi sn o to n l yi m p o r t a n ti nt h e o r yb u ta l s oi n p r a c t i c e s i n c et h ei n t e r n e ti st h em a i ns o u r c ef o rp e o p l et og e tm e s s a g ef o rt h e t i m eb e i n g ，t h es t u d yo ft e x tc a t e g o r i z a t i o na n dc l u s t e r i n gn o to n l yl i m i t so n g e n e r a lt e x tf i l e s ，b u ta l s of o c u s e so nw e bp a g e s t h e r e f o r et h i s t h e s i s d i s c u s s e st h et e x t c a t e g o r i z a t i o n a n dc l u s t e r i n go nb o t hc o m m o nt e x t d o c u m e n t sa n dw e bp a g e s t h em a i nc o n t r i b u t i o n so ft h i st h e s i sc a nb el i s t e da sf o l l o w s ： 1 ) at h o r o u g hs t u d y o nt h ef e a t u r es e l e c t i o nm e t h o d sa n dt e x t c a t e g o r i z a t i o nm e t h o d so ft e x td o c u m e n ti sc a r r i e do n b a s e do nt h es t u d y ，t h e a d v a n t a g eo fe a c hm e t h o di sa n a l y z e d a n dt h e nt h et r a d i t i o n a la l g o r i t h mo f s u p p o r tv e c t o rm a c h i n e ( s v m ) i si m p r o v e db yu t i l i z i n gan e w k e r n e lf u n c t i o n c o m b i n e db yr b fa n dp o l y t h ee x p e r i m e n ts h o w st h a tn e ws v mg e t sb e t t e r c a t e g o r i z a t i o nr e s u l t s 2 ) c o n s i d e r i n gt h ed i s a d v a n t a g eo ft r a d i t i o nf e a t u r es e l e c t i o n ，an e ww a y f o rw e bp a g e sc l a s s i f i c a t i o ni sp r o p o s e db a s e d0 1 1t h eo b s e r v a t i o nt h a tm o s t w e bp a g e sa r es e m i - s t r u c t u r a l ，t h en e wm e t h o du t i l i z e sb o t ht h es t r u c t u r e s i n f o r m a t i o na n dt h ec o n t e n t so fw e bp a g e s ，i to v e r c o m e st h es h o r t a g eo ft h e t r a d i t i o n a lc l a s s i f i c a t i o n ，w h i c hi g n o r e do ro v e r l o o k e dt h es t r u c t u r e i n f o r m a t i o no fw e bp a g e s t h em a i ni d e ao ft h en e wm e t h o di st oc l a s s i f yt h e w e bp a g e sf i r s tb a s e do nt h e i rs t r u c t u r a li n f o r m a t i o n ，a n dt h e nc l a s s i f yt h e m a c c o r d i n gt ot h e i rt e x tf e a t u r e s t h ee x p e r i m e n t ss h o wt h a tt h en e wm e t h o d c a ni n c r e a s et h ep r e c i s i o na n de f f i c i e n c yo fw e bp a g ec l a s s i f i c a t i o n i i i 山东大学硕士学位论文 3 、t h i st h e s i sh a sc a r r i e do np r e l i m i n a r yr e s e a r c ho nm u l t i c l a s s i f i e r s c o m b i n a t i o n t h em u l t i - c l a s s i f i e r si sc o m b i n e db yt w oc l a s s i f i e rm o d e l s t h e c o m b i n a t i o ni sb a s e do nn a i v eb a y e st h e o r ya n du s e dt oc l a s s i f yt h ew e b p a g e s ，o u re x p e r i m e n ts h o w st h a tc o m p a r et ot h es i n g l ec l a s s i f i e rm e t h o d ，t h e m u l t i c l a s s i f i e rw o r kf a i r l yw e l la n di m p r o v e dt h ep r e c i s i o no fc l a s s i f i e r e f f e c t i v e l y t h eo r g a n i z a t i o no ft h i st h e s i si sa sf o l l o w s ：w eg i v et h er e l a t e dw o r ko n 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 nc h a p t e r1 i nc h a p t e r2 ，w ei n t r o d u c e dt h e m a i nc o n c e p t so ft e x tc a t e g o r i z a t i o n ，t h ec l a s s i c a lt h e o r ym o d e l s ，t h ef e a t u r e s e l e c t i o nm e t h o d s t h ec l a s s i f i e rm o d e l sa n do u rs u p p o r tv e c t o rm a c h i n e m o d e l ；m o r e o v e r , w ea l s oc o m p a r e do u rs v m w i t hk n na n dn a i v eb a y e si n o u re x p e r i m e n t i nc h a p t e r3 ，w ei n t r o d u c e dh i e r a r c h i c a lc l a s s i f ym e t h o d b a s e do nt a x o n o m y ，s t r u c t u r ei n f o r m a t i o no fw e bp a g e sa n dt h et e x to fw e b p a g e s ，a n dv e r i f yt h ev a l i d i t yo fo u ra l g o r i t h mt h r o u g ht h ee x p e r i m e n t ；t h e n w eh a sc a r r yo np r e l i m i n a r yr e s e a r c ho nm u l t i c l a s s i f i e r sc o m b i n a t i o ni n c h a p t e r4 i nc h a p t e r5 ，w es u m m a r i z et h ew h o l et h e s i s ， k e yw o r d s ：t e x to a t e g o r iz a t io n ：w e bp a g e s0 i a s s i f i o a t i o n f e a t ur e s o lo c t i o n ：k n n ：s u p p e r tv e o t o rm a o h in o 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 柏赢繇髯阻掣 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签 山东大学硕士学位论文 1 1 背景介绍 第1 章前言 随着i n t e r n e t 的不断发展和日益普及，世界已经进入到一个信息时 代。当我们在网站寻找自己所需要的信息时，如果网页毫无有序的放在一 起，没有类别供我们查找，会使我们很难找到自己所需的信息。一方面， i n t e r n e t 上面蕴涵的信息可谓是浩如烟海，但是面对规模巨大的信息汪 洋，人们无法很有效地利用海量的资源，这增加了对于快速、自动文本分 类的迫切需求，另一方面激增的信息资源又为基于机器学习的文本分类方 法准备了充分的资源。通过文本自动分类系统把文本数据进行归类，可以 帮助人们更好地发现、过滤和分析文本信息资源。文本自动分类的目的就 是对文本集进行有序组织，把相似、相关的文本组织在一起。它作为知识 的组织工具，为信息检索提供了更高效的搜索策略和更准确地查询结果， 使得检索的查全率和准确率都得到了提高。传统的人工分类的做法存在许 多弊端，不仅是耗费大量人力、物力和精力，而且存在分类结果一致性不 高的问题。因而，构造一个有效的文本分类系统是十分必要的。 文本分类是一个活跃的科研领域，它是数据挖掘中一个重要的研究领 域，它经历了几个不同的发展阶段。最先的文本分类主要是有人工进行标 识。到1 9 6 4 ，l i o s t e l l e r 和w a l l a c e 【】在鉴别文章作者身份的工作中开创了 文本分类的新阶段，他们在分类时考虑单词，句子长度，功能词的频率和 词汇的差异等特征项。当前，虽然互联网上的信息载体呈多样化趋势，但 仍以文本为主，文字仍是互联网上信息的主要来源，这使得近期的文本分 类具有广泛的应用：抽取符号知识1 2 1 、新闻分发3 1 、排序电子邮件1 4 1 、网 页分类【5 1 、邮件分类以及信息过滤等等。 采用文本分类技术可以建立起一个自动的文本分类系统，相对于人工 分类，自动分类系统具有以下特点 山东大学硕士学位论文 ( 1 ) 高效率、高速度。自动分类的效率将是人工分类的百倍甚至千倍， 从而节约大量的人力物力。 ( 2 ) 较高的准确度消除了人为错误产生的可能。 ( 3 ) 良好的自适应性。可快速适应文本的更新及类别的变化，适应不 同环境及需求。 众多的研究者对文本分类系统，进行了深入的研究，提出了许多统计 方法和机器学习方法。并且在实验中有很好的表现。但是，在这个领域还 是有很大的空间值得我们继续去研究和探索。 1 2 国内外文本自动分类研究动态 国外对于文本自动分类的研究开展较早，2 0 世纪5 0 年代末，h r l u h n 对文本自动分类进行了开创性的研究，将词频统计思想应用于文本自动分 类 6 1 。1 9 6 0 年，m a r o 发表了关于自动分类的第一篇论文，随后，ks p a r k 、 g s a l t o n 、r m n e e d h a m 、m e l e s k 以及k s j o n e s 等学者在这一领域进行 了卓有成效的研究。目前，文本自动分类己广泛的应用于电子邮件分类、 电子会议、数字图书馆、搜索引擎、信息检索等方面。文本自动分类主要 经历了四个发展阶段： 第一阶段0 9 5 s 1 9 6 4 ) ：研究文本自动分类的可能性： 第二阶段“9 6 5 1 9 7 4 ) ：进入文本自动分类的实验性阶段； 第三阶段n 9 7 5 1 9 9 8 ) ：文本自动分类的实用性阶段： 第四阶段( 1 9 9 0 至今) ：因特网文本自动分类研究阶段。 国外较早的文本自动分类应用系统有卡内基集团为路透社开发的 c h r u c h 9 5 系统，它能对路透社成千上万的稿件进行自动分类，它是由专家定 义一系列逻辑规则，这些规则包括如何把某一给定文本归类为某一预先制 定的类别集合中的一种或几种类别：麻省理工( m i t ) 为白宫开发的邮件分 类系统：德国o l d e n b u r g 大学一个研究项目g e r h a r w 7 1 等。 相对于国外文本分类的发展水平。国内对于文本自动分类的研究起步比 较晚，1 9 8 1 年，侯汉清教授对于计算机在文本分类工作中的应用作了探讨， 2 山东大学硕士学位论文 并介绍了国外计算机管理分类表、计算机分类检索、计算机自动分类、计 算机编制分类表等方面的概况。此后，我国陆续研究出一批计算机辅助分 类系统和自动分类系统。例如，广东省中山图书馆的莫少强开发的计算机 辅助图书分类系统( c a b c ) 、清华大学吴军研制的自动分类系统、山西大 学刘开瑛等人开发的金融自动分类系统、东北大学图书馆的图书馆分类专 家系统，上海交通大学王永成等研制的基于神经网络优化算法的中文文本 自动分类系统。近期研究中比较突出的是中科院的中文文本智多星分类 器，它采用多种分类方法。虽然中英文之间存在较大差异，无法直接参照 国外的研究成果，但是，随着中文信息处理技术特别是中文自动分词技术 的日渐成熟，以此为基础的中文文本分类技术的研究得到了飞速发展，在 短短2 0 多年中完成了从可行性探索到实用化阶段的转变。 1 3 本文的工作 本文对常用的自动文本分类算法和特征选取方法进行了研究，并实现 了一个文本分类系统。工作的主要创新点可概括如下： 1 ) 深入地研究了对文档特征的提取方法和文档分类方法，通过比较， 分析了各种方法的优缺点。在此基础上，对传统的支持向量机分类法进行 了改进。对传统的支持向量机中的核函数进行了组合的研究，提出了由径 向基核函数( r b f ) 和多项式核函数( p o l y ) 组合成的新的核函数。实验表明 支持向量机在组合后的核函数下能取得更好的分类效果。 2 ) 基于对传统的特征选取方法和文本分类方法的分析，针对w e b 网页 具有半结构化的特点，提出了一种结合结构和内容的对w e b 网页按层次进 行分类的方法，克服了传统分类中轻视或忽略了w e b 网页的结构信息的不 足其主要思路是利用w e b 网页的结构信息对网页进行大类层次上的粗分， 然后利用网页中的全文信息再进行细分。实验结果表明，该层次分类方法 能有效地提高分类的精度和效率 3 ) 本文对多分类器的组合问题进行了初步研究，提出了用n a i v eb a y e s 组合两种分类器对w e b 网页进行协调分类的方法，实验结果显示这是协调 3 山东大学硕士学位论文 超文本分类中多种分类器的一种有效方法。与只用单种方法对超文本进行 分类的方法相比，综合分类法有效地提高了分类的正确率。 1 4 本文的组织和内容概要 本文的内容组织如下： 第1 章： 介绍了本文的研究背景和相关研究现状。 第2 章：给出了对文本自动分类技术的概述。详细介绍了已有的几种 特征选取方法和经典的分类方法。在此基础上，对传统的支持向量机分类 法中的核函数进行了组合研究，提出了一种基于组合核函数的改进的支持 向量机算法。 第3 章：设计了一种基于结构和内容的对w e b 网页进行层次分类的系 统，克服了传统分类中忽略w e b 网页结构信息的不足，主要思想：利用w e b 网页的结构信息对网页进行大类层次上的粗分，然后利用网页中的全文信 息再进行细分。 第4 章：讨论了对多分类器组合的研究与实现。介绍一种多分类器 组合的方法，以及该方法在w e b 网页分类中应用。 第5 章：对本文的工作进行了总结，并对本文工作中存在的一些不足 提出了可能的改进思路和基于本文的工作将来可以继续开展的一些工作。 4 山东大学硕士学位论文 第2 章文本自动分类技术概述 2 1 文本自动分类的定义 文本自动分类( a u t o m a t i c t e x t c a t e g o r i z a t i o n ，a t c ) ，在给定的分类体系 下，根据文本的内容用计算机程序确定文本所属类别的过程即用计算机程 序来确定指定文档和预先定义类别之间的隶属关系。 目前，主要的文档自动分类算法可以分为三类： 1 ) 词匹配法。词匹配法又可以分为简单词匹配法和基于同义词的词匹 配法两种。简单词匹配法是最简单、最直观的文档分类算法，它根据文档 和类名中共同出现的词决定文档属于哪些类。很显然，这种算法的分类规 则过于简单，分类效果也很差。基于同义词的词匹配法是对简单词匹配法 的改进，它先定义一张同义词表，然后根据文档和类名以及类的描述中共 同出现的词( 含同义词) 决定文档属于哪些类。这种分类算法扩大了词的 匹配范围，在性能上要优于简单词匹配法。不过，这种算法的分类规则仍 然很机械，而且同义词表的构成是静态的，对文档的上下文不敏感，无法 正确处理文档中其具体含义依赖于上下文的词，分类的准确度也很低。 2 ) 基于知识工程的方法。基于知识工程的文档分类方法，需要知识工 程师手工地编制大量的推理规则，这些规则通常面向具体的领域，当处理 不同领域的分类问题时，需要不同领域的专家制定不同的推理规则，而分 类质量严重依赖于推理规则的质量。因此，在实际的分类系统中较少使用 基于知识工程的学习法。 3 ) 统计学习法。统计学习法和词匹配法在分类机制上有着本质的不 同。它的基本思路是先搜集一些与待分类文档同处一个领域的文档作为训 练集，并由专家进行人工分类，保证分类的准确性，然后分析这些已经分 好类的文档，从中挖掘关键词和类之间的联系，最后再利用这些学到的知 识对文本分类，而不是机械地按词进行匹配。因此，这种方法通常忽略文 山东大学硕士学位论文 本的语言学结构，而用关键词来表示文本，通过有指导的机器学习来训练 分类器，最后利用训练过的分类器来对待分类的文本进行分类。这种基于 统计的经验学习法由于具有较好的理论基础、简单的实现机制、以及较好 的文本分类质量等优点，目前实用的分类系统基本上都是采用这种分类方 法。 本章介绍的文本分类算法都属于统计学习法。根据分类结果的不同， 基于统计学习法的分类系统在整体上可以被分为两类：独立二元 ( i n d e p e n d e n tb i n a r y ) 分类系统和埘元( 聊一a r y ) 分类系统。所谓独立二 元分类，也可以叫做单类别分类，就是给定一篇文档，分类系统对每一个 类别都独立地判断这篇文档是否属于该类：要么属于，要么不属于，而不 存在其它的结果，并且在分类过程中，不同类别之间互不影响。所谓m 元 分类，也可以叫做多类别分类，就是给定一篇文档，系统计算这篇文档与 所有预先定义的类的相似度，并按这篇文档和各个候选类的相似度排序， 最后输出候选类列表。 单类别分类的一个特殊例子就是上面提到的两类分类。在两类分类中， 一个文本d 要么属于类别c ，要么属于c 的补集( 不属于c ) 。从理论的角度 说，两类分类( 多类别分类更具一般性。因为，一个两类分类算法也能用于 多类别分类：只需要将对于类别集合c 的一个多分类问题转化为i q 个两类 分类问题。但是，在这种转化过程中我们人为地添加了一个假设：不同的类 别之间相互独立。 此外，根据分类过程中是否进行学习，文本的自动分类技术可以分为 两大类：有指导( s u p e r v i s e d ) 的分类和无指导( u n s u p e r v i s e d ) 的分类。有指导 的分类又称为领域分类或者简称分类，指预先确定好文本的类别，同时对 每个文本类别都提供一批预先分类好的文本，称为训练集。根据训练集确 定文本类的表示( 即类模板) 。在实际分类的时候，计算所需分类的文本与 所有的类模板之间的相似度，然后根据相似度大小和一定的分类规则决定 所有文本的类别。文本的类别及数量可以是不确定的，要经过文本的组织、 聚类后才能得到，这种分类方法称为文本聚类( c l u s t e r i n g ) 或者无指导的分 类。文本聚类通常采用层次聚类( 系统聚类) 方法，通常分为两类：一种称为 山东大学硕士学位论文 凝聚法，或自底向上的方法，开始时每篇文本都认为是一个文本类，然后 根据文本之间的相似情况，不断地把相似文本合并为一类：另一种称为分解 法，或自顶向下的方法，开始时对全体文本给定一个较粗的分类，然后再 不断细化。本文所讨论的文本自动分类技术是指有指导的分类。 下面我们给出实现中文文本自动分类的一般过程，如图2 1 - l 所示。首 先对文本进行预处理，将文本用模型表示，进行特征提取；然后构造并训练分 类器：最后用分类器对新文本进行分类。 图2 - 1 - 1 中文文本自动分类的一般过程 图2 - 1 - 2 中文文本自动分类的工作原理 根据图2 一l - l 所示的中文文本分类的一般过程，我们可以构造出分类中 所使用的分类器，其工作原理如图2 1 - 2 所示。从图2 - l 一2 可知，文本自动 分类的主要工作周期分为训练和分类两个阶段：在训练过程中，训练集实 例经过中文分词和特征选取处理后被表示成向量形式。该特征向量集用来 7 山东大学硕士学位论文 描述类别模式，在分类过程中使用；在分类过程中，一个待分类的中文网页 经过中文分词并表示成向量后，应用分类算法同训练过程得到的类别模式 逐一比较，得到候选类别列表，然后同训练过程中得到的每个类别的阈值 相比较，保留大于阌值的类别，并作为该网页的分类结果。其算法我们可 以如下表示( 单类别情况，多类别可以类推) ： ( 1 ) 训练阶段 1 ) 定义类别集合c = e l ，c 2 ，c 。) ，类别可以是并列的，也可以是层次 的。 2 ) 给出训练文本集合，s = 8 1 ，8 2 ，j 。 ，每个文本s ，被标注上所属的类 别cf 。 3 ) 统计s 中所有文本的特征矢量，对于任意属于s 的文本5 ，特征矢 量表示成以。) ，从而确定代表c 中的每个类别的特征矢量为v ( c ，) 。 ( 2 ) 分类阶段 1 ) 对于测试文本集合d = d ，d 2 ，d ， 中的每个文本d k ，计算其特征 矢量v ( a 与每个类别的特征矢量v ( e 的相似度s i r e 女，c 。 2 ) 选择相似度最大的一个类别，即c ，s i r e hc o = a r g m a x ( s i m 似k ，c ， 作为d 女的类别。 文本分类中使用的技术和方法，主要来自统计学、机器学习、模式识 别、人工智能等相关学科和技术领域。一般说来，不存在一个普遍适用的 方法。一个方法或算法在某个领域非常有效，但在另一个领域却可能不太 适合。因此在实际应用中，需要针对特定领域，精心选择有效的模型与算 法。文本分类主要涉及到三方面核心技术，它们是：自动分词、特征选择、 自动分类聚类。在研究过程中，需要对相关的技术问题进行调研，下面将 逐一探讨各项核心技术。 2 2 文本预处理 本预处理主要是进行结构处理( 比如网页) 和分词处理等。结构处理( 比 如网页) ，即去掉一些标记，例如h t m l 中的t a g ，去除禁用词、词根还原。 山东大学硕士学位论文 分词处理在处理中文等没有明显的词语分隔符的文本时非常重要。而在英 文文本中词与词之间由空格等特殊字符隔开，具有非常明显的特征，处理 起来比较简单。对于中文文本而言，因为词与词之间没有明显的切分标志， 所以需要分词。 自动分词是针对于中文的一种自然语言分析处理技术。中文与英文的 不同之处有很多，其中之一是中文句子中词与词之间没有明确的分隔标 记，而是连续的文字串。显而易见，自动识别词边界，将中文文字串切分 为正确的词串的汉语分词问题，无疑是实现中文文本自动分类的各项任务 的首要问题。为了对中文文本和信息进行分类、索引等处理，首先必须对 中文文本进行分词。 中文文本的分词处理是指在中文文本中连续的、能够代表语义单元的 词或者2 元词条间加入分隔符，将中文文本从连续字节流形式转化为离散 单词流形式的过程。 自动分词技术是各种中文信息分析处理技术( 如文本分类、自动文摘、 信息检索、信息摘录、语音识别) 的基础，也是中西文之间研究文本自动 分类的主要差异所在，中文文本自动分类要在自动分词的基础上进行，对 中文文本进行分词的过程是文本特征集确定过程中的第一个步骤。 中文分词技术发展到现今，在这方面的技术研究已有二十多年历史了。 其间提出了多种分词算法，总的来说这些算法可分为四大类：第一类为基 于词典的机械分词算法：第二类为基于统计的分词算法；第三类为第一类 和第二类的混合型分词算法；第四类为基于知识的分词专家系统。现有的 分词方法主要有基于字符串匹配的方法，基于理解的方法和基于统计的方 法。对于中文文本还需要进行词性标注、短语识别。下面介绍这三种分词 方法： 1 ) 基于字符串匹配的方法 这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字 串与一个“充分大的”机器词典中的词条进行匹配，若在词典中找到某个 字符串，则匹配成功( 识别出一个词) 。按照扫描方向的不同，基于字符串 匹配的分词方法可以分为正向匹配和逆向匹配：按照不同长度优先匹配的 9 山东大学硕士学位论文 情况，可以分为最长( 最大) 匹配和最小( 最短) 匹配：按照是否与词性标注过 程相结合，又可分为单纯分词方法和与标注相结合的一体化方法。常用的 几种机械分词方法有正向最大匹配，逆向最大匹配，逐词遍历法。 由于此种方法主要依靠词典进行分词，因而，词典中词条的数目，词 条的选择直接影响到最后的分词效果。由于词典中不涉及语法、语义等有 关自身的信息，所以，机械分词法无法避免汉语中最基本的两种歧义现象。 交集型歧义：假设字串s = x y ，鼻= a b ，y = c d ，若a ，ab ，bc ，c d ，d 都是词 典中的词，则a b c d ，a b c d 都是有效的切分结果。这就造成了所谓的交 集型歧义。例如：字符串“辛勤劳动”，其中“辛勤”、“勤劳”、“劳动”均 为词，并构成交叉，所以对“辛勤劳动”的切分就构成了交集型歧义。 组合型歧义：假设字串s = x y , x 利，y = 口，若一，b ab 均在此表中，则将 造成组合歧义。如：“玩笑”即可作为一个词切分出来，也可切分成为“玩”、 “笑”。 此外，词典中不能囊括所有的词。一方面是因为语言在不断的发展和 变化，新词会不断的出现。另一方面是因为词的衍生现象非常普遍，没有 必要把所有的衍生词都收入词典中。对于词典中未能及时收录的新词，机 械分词法无法予以正确的切分，不具备自适应性是此方法的一大弱势。但 是由于这种方法方便对特定领域内较难切分的词进行处理，易于实现，因 而得到了广泛的应用。 实际使用的分词系统，都是把机械分词法作为一种初分手段，还需要 利用其它语言信息来进一步的提高切分的准确率。一种方法是改进扫描方 式，称为特征扫描或标志切分。优先在字符串中识别和切分出一些带有明 显特征的词，以这些词作为断点，可将原字符串分为较小的串再来进行机 械分词，从而减少匹配的错误率。切分标记可以分为绝对切分标记和条件 切分标记。绝对切分标记指标点符号、数字和其它非汉字符号。条件切分 标记是指那些出现频率高，构词能力差的单字词，如“啊”，“吧”、“吗”、 “也”、“么”、“的”、“很”、“谁”、“你”、“它”、“要”等。这些字仅能 构成极少量有意义的词汇，而能构成反映文章主题的词则更少，所以将它 们作为切分标记。另一种方法是将分词和词类标注结合起来，利用丰富的 山东大学硕士学位论文 词类信息对分词决策提供帮助，并且在标注过程中又反过来对分词结果进 行检验、调整，从而极大地提高切分的准确率。 2 1 基于理解的方法 通常的切分系统，都力图在分词阶段消除所有的歧义切分现象。而有 些系统则在后续过程中来处理歧义切分问题，其分词过程只是整个语言理 解过程的小部分。其基本思想就是在分词的同时进行语法、语义分析，利 用语法信息和语义信息来处理歧义现象。这类方法通常包括三个部分：分词 子系统、语法语义子系统、总控部分。在总控部分的协调下，分词子系统 可以获得有关词、句子等的语法和语义信息来对分词歧义进行判断，即它 模拟了人对句子的理解过程。 该类分词方法主要有扩充转移网络法、联想一一回溯法、邻接约束法、 语境相关法、专家系统分词法、基于神经网络的分词法等。以扩充转移网 络法为例，它是一种普遍应用于数据库自然语言查询中进行语法分析的方 法。在实现中，需要建立一个语法知识集合，用以作为弧间状态迁移的测 试条件。利用这种方法可以大大提高分词的精度，与机械分词法相比，切 分智能性更进一步。这种分词方法需要使用大量的语言知识和信息。由于 汉语语言知识的笼统性、复杂性，难以将各种语言信息组织成机器可直接 读取的形式，因此目前基于理解的分词系统还处于试验阶段。 3 1 基于统计的方法 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时 出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或 概率能够很好的反映成词的可信度。可以对语料中相邻共现的各个字的组 合的频度进行统计，计算它们的互现信息为： m ( x ，r ) = l o g p ( x y 、 p ( x ) p 侈) ( 2 2 一1 ) 其中p y j 为汉字五r 的相邻共现概率，p 例ip 例分别是五】，在语料中 出现的概率。互现信息体现了汉字之问结合关系的紧密程度。当紧密程度 高于某一个闭值时，便可认为此字组可能构成了一个词。这种方法只需对 语料中的字组频度进行统计，不需要切分词典，因而又叫无词典分词法或 山东大学硕士学位论文 统计取词法。但这种方法也有一定的局限性，会经常抽出一些共现频度高， 但并不是词的常用字组，例如“这一”、“之一”、“有的”、“我的”、“许多 的”等，并且对常用词的识别精度差，时空开销大。 2 3 文本模型 文本和数据库中纪录的最大不同是它的非结构化特点。文本是一维的 线性字符流。从现代语言学角度看，文本有着立体的递归生成结构。但是 要分析清楚这种递归生成结构，需要进行大规模真实文本的深层次自然语 言处理。目前这种技术还没有达到实用的程度。说文本信息的内容是非结 构化的，主要是指它的表层没有像数据库里面的纪录那样的向量结构。因 此，如果想要利用结构化数据成熟的分类和聚类技术对文本进行分类和聚 类，首先耍解决的一个问题就是非结构化数据的结构化。为了使计算机能 够真正进行文本的特征进行分析，必须对文本特征进行有效的表示，将文 本表示成计算机可以处理的数学向量。从文本分类技术出现的第一天开 始，出现了许多文本表示模型，具有代表性的有布尔模型、向量空间模型、 概率模型等。这些模型从不同角度出发，使用不同的方法处理特征加权、 类别学习和相似性判断等问题。 在当前的大多数信息处理系统中，文本模型，也就是文本的表示主要 采用向量空间模型( v e c t o rs p a c e m o d e l ，简称v s m ) v s m 是s a l t o n 【s l 等人于 上个世纪6 0 年代首先提出的，并在著名的s m a r t ( s y s t e mf o rt h e m a n i p u l a t i o na n d r e t r i e v a lo f t e x t ) 系统得到成功的应用。目前，该模型及 其相关技术，包括项的选择、加权策略，以及采用相关反馈进行优化查询 等在文本分类、自动索引、信息检索等诸多领域得到广泛的应用，并取得 了较好的效果。 2 3 1 向量空间模型的基本概念 向量空间模型( v e c t o rs p a c em o d e l ，v s m ) t 9 , 1 0 , 1 1 1 是由g s a l t o n 等人在2 0 世纪6 0 年代提出的。它把文档简化为以项的权重为分量的向量表示，把 山东大学硕士学位论文- -m 分类过程简化为空间向量的运算，使得问题的复杂性大大降低。此外向量 空间模型对项的权重评价、相似度的计算都没有作出统一的规定，只是提 供一个理论框架可以使用不同的权重评价函数和相似度计算方法，这使得 此模型有广泛的适应性，迄今己在实验系统s m a r t1 1 2 】，及多种实用系统， 如l y c o s ，a l t a v i s t a 中得到了成功的应用，但这一模型也存在着诸如它的词条 正交性假设不符合自然语言的实际等问题。 定义2 3 - 1 1 文档( d o c u m e n t ) ：泛指一般的文本。本文中，用d 表示一 篇文档( 文本) 。 定义2 3 1 2 项( t e r m ) ：文本的内容特征常常用它所含有的基本语言单 位( 字、词、词组或短语) 来表示，这些基本的语言单位被统称为文本的项， 即文本可以用项集( t e r m l i s t ) 表示为d ( t ，t 如t j ，其中t i 是项，1 耋七耋月。 定义2 - 3 - 1 - 3 项的权重：对于含有刀个项的文本d ( t j ，坛t 一，常用一定 的权重w 表示项t 在文本d 中的重要程度，即出d ( t ，wj i 坛w j i t 。，w 。) ， 简记为赤d 似j ，w ，w 。 定义2 - 3 - 1 - 4 向量空间模型( v s m ) ：忽略t 在文档d 中的先后顺序并要 求互异，将文档d 简化以特征项的权重为分量的向量表示：d = d ( w i , w 加，w j 。即把t j ，坛t 。看成一个栉维的坐标系，而w ，w 加，w 。为相应的坐标值， 因而d ( wj ，w 加，w 被看成是甩维空间中的一个向量。称d ( wj ，w 加，w 一为文 本d 的向量表示。 定义2 - 3 一l 5 相似度( s i m i l a r i t y ) ：对两个文本d ，和巧之间的内容相关度 ( d e g r e eo f r e l e v a n c e ) 的度量被称为s i m 似f ，圳。对于文档d f 小w 2 ， 和文档d j ( w j l ，w ，2 ，wj ，我们可以借助向量之间的某种距离来表示它们 之间的相似度，常用向量之间的内积进行计算： 咒 s i m ( d d ) = w 腑木w 弦 k = l 也可以通过另一种方式表示； 山东大学硕士学位论文 s i r e ( d f ，d ) = w 砖w 声 向量空间模型有效地解决了非结构化文本数据的处理问题，大大提高 了文本处理的速度和效率，把对文本的操作转变为对特征向量的操作。 2 3 2 特征项的选择 在向量空间模型中，特征项的选择对其表达效果有着很重要的影响。 一般可以选择字、词或词组作为特征项，或者更高层次的语言单位都可作 为特征项特征项也可以是相应词语或者短语的语义概念类，形成概念特征 项。 在选择特征项时，我们应遵循以下原则：一是尽量选择包含语义信息较 全面，对文本的表示、代表能力较强的语言单位：二是特征项在文档中的分 布应该显示出明显的统计规律性：三是考虑特征项实现的时间和空间开销， 尽量要求不能太过于复杂。通常可以选择以下特征项： 1 字特征项 字是汉语中最基本的语言单位，以它作为特征项对文本语义的表述能 力相对较差。但是对于中文来讲，分词过程本身就是难点，不好的分词同 样会导致系统性能的下降，并且在汉语中，汉字的数量大大少于词的数量， 所以，选择字作为特征项可以使特征选择的工作量降低。 2 词特征项 一般认为，词( 词组) 是构成汉语文本的主体，是最能够反映文本语义的 基本单位，通常选择词作为特征项能充分表示汉语的语义，系统的性能优 于选择字作为特征项的系统。但是直接选用文本中的词或词组作为文本特 征项也会存在以下问题： ( 1 ) 词( 词组) 的数量十分巨大，不算各行各业的专用词，就普通词额数 量而言，一般在l o 万左右。文本中还存在一些没有实在意义但使用频率 很高的虚词和功能词，这些词常常把一些真正有分类作用的实词淹没掉。 山东大学硕士学位论文 解决的方法实将这些词组织成一个禁用词表，把禁用词表中的词从特征集 中去除。另外在文本预处理中还要进行词性标注，从特征集中去除那些对 特征区别贡献极小的大部分助词和功能词。 ( 2 ) 汉语中存在大量的同义词，近义词，将它们作为不同的特征显然会 使得两篇类似的但用词风格不同的文本距离相差过大。 3 概念特征项 以词作为特征项，汉语中又存在大量的同义词，近义词。所以提出概 念特征项。概念通常是指代表一类同义词或近义词的条目，它合并了同义 词和近义词，使得特征项的选择尽可能地集中，贴近语义。但是概念本 身的