（计算机应用技术专业论文）文本挖掘关键技术研究及实现.pdf

文本挖掘关键技术研究及实现 摘要 随着互联网技术的飞速发展且日益成熟，使得互联网上的信息每天都在呈现爆炸 式增长，但同时也出现了“信息丰富而知识相对匮乏”的问题。由于i n t e r n e t 的开放 性及异构性，用户很难快速准确地从互联网上获取自己所需的有价值信息，因此，文 本挖掘技术在近几年倍受研究者的关注，是一项重要的研究课题。 文本挖掘是数据挖掘与信息检索两门学科的交叉，可以对文档集合的内容进行总 结、分类、聚类、关联分析以及趋势预测等。这首先需要对文本进行预处理，获取文 档的特征表示，抽取文档的信息才可以实现的。但是由于中文文本的组织方式不同于 西文，给以上技术的研究带来了相当大的困难。虽然目前在文本预处理方面的研究有 些进展，但是对于文本信息获取的精度都不是很高，还有很大的研究空间。 本文正是对中文分词、特征抽取、文本分类等技术分别进行了研究，主要做了如 下的工作： 1 由中文词条切分技术开始，介绍了几种分词的方法，并设计了个分词系统， 提出了一种改进的歧义消除算法； 2 研究分析了文本特征值的抽取技术，分析比较了几种特征值获取技术性能优 劣，重点研究了信息增益和互信息以及词频统计等方法，提出一种改进的特 征抽取方法，并实现了相应的系统模型； 3 分析比较了文本分类技术，利用改进的权重和k n n 分类方法相结合，实现文本 的分类，并通过实验来验证其相应的查全率和准确率。 关键词：文本挖掘，中文分词，歧义消除，特征抽取，文本分类 t h er e s e a r c h & r e a l i z a t i o no nt h ek e yt e c h n i q u e so ft e x tm i n i n g a b s t r a c t w i t ht h er a p i dd e v e l o p m e n ta n dg r a d u a lm a t u r a t i o no ft h ei n t e r a c tt e c h n i q u e s ，t h e i n f o r m a t i o no ni n t e m e tg o e su pe x p l o s i v e l y , w h i l ea tt h es a n l et i m e ，t h ep r o b l e ma p p e a r s t h a tt h ei n f o r m a t i o ni sa b u n d a n tb u tt h ek n o w l e d g ei ss c r r c e b e c a u s et h ei n t e m e ti so p e n a n di s o m e r o u s ，i ti sd i f f i c u l tf o ru s e r st of i n dt h ev a l u a b l ei n f o r m a t i o nf r o mi n t e m e tq u i c k l y a n de x a c t l y t h e r e f o r e ，t e x tm i n i n gt e c h n i q u ei sa ni m p o r t a n ts u b j e c tf o rr e s e a r c hw h i c hi s p a i dm o r ea t t e n t i o nb yt h er e s e a r c h e r si nr e c e n ty e a r s t e x tm i n i n gi sac r o s so ft w os u b j e c t s ：d a t am i n i n g & i n f o r m a t i o ns e a r c h i n g i tc a n s u i i l m f l t i z c ，c l a s s i f y , c l u s t e r , a n a l y z et h er e l e v a n c y , a n df o r e c a s tt h et r e n df o rt h ec o n t e n t so f t h ed o c u m e n t s i ti sr e q u i r e dt op r e p r o c e s st h et e x tf i r s t ，g e tt h ef i g u r eo ft h ed o c u m e n t c h a r a c t e r , a n dt a k eo u tt h ed o c u m e n ti n f o r m a t i o n , e t c b u tt h ec h i n e s et e x t sf o r mi s d i f f e r e n tf r o mt h ew e s tl a n g u a g e s ，w h i c hb r i n g sm u c hm o r ed i f f i c u l t i e st ot h er e s e a r c ha b o u t t h et e c h n i q u e a l t h o u g hs o m ep r o g r e s sh a sb e e nm a d ei nt h ep r e s e n tr e s e a r c ho nt h et e x t p r e p r o c e s s ，t h e r ei ss t i l lal o to fw o r kt od of o rt h et e x ti n f o r m a t i o ni sn o td r a w nv e r y p r e c i s e l y t h et e x tm i n i n gi sr e s e a r c h e dm a i n l yi nt h i sd i s s e r t a t i o na n dm u c hw o r kh a sb e e nd o n e a sf o i l o w s ： 1 i tb e g i n sw i t ht h et e c h n o l o g yo fc h i n e s et e x ts e g m e n t ，i n t r o d u c e ss e v e r a lm e t h o d so f c h i n e s ew o r dg r o u p i n g ，a n dd e s i g n sas y s t e mf o ri t 2 i ta n a l y z e st h et e c h n o l o g yo fg e t t i n gt h et e x te i g e n v a i u e ，a n dc o m p a r e st h e i r c a p a b i l i t y t h ei 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 na n dt h ew o r df r e q u e n c y s t a t i s t i c sa t e p a i dm o r ea t t e n t i o no n a l s oi tp u t sf o r w a r da ni m p r o v e dm e t h o do fg e r i n gt h ed o c u m e n t c h a r a c t e r s 。 3 i ta n a l y z e st h et e c h n o l o g yo ft h et e x tc l a s s i f i c a t i o n ，u s e st h ei m p r o v e dw e i g h to f p o w e r & k n n t or e a l i z et e x tc l a s s i f i c a t i o na n dv a l i d a t e st h er a t i oo fe n t i r e t yo rp r e c i s i o nb y e x p e r i m e n t s k e yw o r d s ：t e x tm i n i n g ，c h i n e s et e x ts e g m e n t ，a m b i g u i t i e se l i m i n a t i o n ，c h a r a c t e r d r a w i n g t e x tc l a s s i f i c a t i o n 插图目录 图2 1 文本挖掘模型的结构图8 图3 1 系统工作流程图1 3 图3 2 正向最大匹配法切分结果1 4 图3 3 退一字组合法消除歧义1 4 图3 4 退一字组合法切分结果1 5 图3 5 动词判定算法消除歧义1 6 图3 6 动词判定流程图1 7 图3 7 优先级判定算法消除歧义1 7 图3 8 优先级判定流程图1 8 图3 9 分词字典的建立模式1 8 图3 1 0 有限状态转移网络2 0 图3 1 1 中科院的i c t c l a s1 0 2 3 图3 1 2 海量分词系统2 3 图3 1 3 本系统的分词效果2 4 图4 1 特征抽取系统的工作流程图3 0 图4 2 特征选择程序及结果3 2 图4 3 训练文本的组织结构3 3 图4 4 停用词和标点符号表3 4 图4 5 海量分词研究版关键词分析3 5 图5 1 中文分词结果4 5 图5 2 中文分类系统4 7 表格目录 表3 1 分词速度测试1 9 表3 2 分词精度测试1 9 表4 1 特征选择速度测试o e od io 3 5 表4 2 海量的关键词计算速度测试3 5 表4 3 特征选择准确度测试3 6 表5 1 文档训练和测试结果4 8 独创性声名 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得 金i 些盔堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 聪了可p 岁 学位论文版权使用授权书 本学位论文作者完全了解盒月垦王些态堂有关保留、使用学位论文的规定， 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日期：1 年， 如， l ， 学位 工作 通讯 有权保留并向国 导师签名：、仰彻 i 签寄蹶嗣年f | 聂| 弘 电话 气缓似眵 夕 跖7哆 p 岁 z 7 ； 飞7 致谢 今天，在这说些感谢的话，是情不自禁的，是由衷的，也是在论文写作完成之后 的。年前，别人问我论文将研究什么方向，我说不清。很幸运的，我遇到了胡学钢 老师，他结合我的专业，结合我自身的教学任务，很果断地说，“那就文本挖掘吧”。 这简短的话语，却给我指明了方向。从那以后，我广泛搜集资料，密切关注国内外研 究热点，也同时知道了一些自己该做的事情了，积极地投入论文的研究之中了。在这 之前，我只知道去教好自己的课，根本就不知道主动去研究什么。因此，这篇论文的 完成，它的意义不只是完成了论文写作的任务，更重要的是，它为我打开了未来的研 究方向。我发现，在这个方向上有很多东西值得去研究，值得去探索，为我今后学业 上的进步起了推波助澜的作用。在这里，向胡老师表示最崇高的敬意和衷心的感谢! 同时，在论文选题阶段，多次参加胡学钢老师组织的研究生交流学习讲座，受到 了很多启发。他们的研究热情和积极地讨论给我留下了深刻印象。因此，在这也要感 谢那些不知名的同学们。在我论文完成之前，也同时得到了舍肥工业大学计算机与信 息学院人工智能实验室的各位老师和同学的指导和帮助，向他们表示感谢! 感谢我的妻子，在我读书写论文期间，承担了太多的家务，给了我很大的支持； 感谢我的学生，在算法实现上给了我很大的帮助；感谢对我论文提出宝贵意见的老师 和专家，感谢在百忙之中评阅论文和参加论文答辩的各位专家。 谨以此文献给所有关心和支持我的人们。 作者：许高建 2 0 0 7 年1 0 月2 1 日 1 i 问题的来源 第一章绪论 今天，互联网技术飞速地发展，数以亿计的用h t m l 和x m l 编写的静态网页， 以及由w e b 数据库服务引擎生成的动态网页，汇聚了人类无穷的智慧和努力， 里面蕴含着大量的丰富的各种各样的信息。然而，由于数据的复杂性和动态性， 如何从大量的、异构的、杂乱无章的、强干扰的数据中挖掘潜在的、有利用价 值的信息，如何获取有用的知识，这给人类的智能信息处理能力提出了前所未 有的挑战。 w e b 上的搜索引擎部分地解决了资源发现问题，但是其精度不高，效果不 能使人十分满意；数据挖掘可以从大量隐含的、有用的尚未发现的信息中发现 知识，但是，它往往工作的对象是结构化的数据库，很少有处理w e b 上异构的、 非结构化的数据的工作。当前，国际上数据挖掘( d a t am i n i n g ) 、知识发现 ( k n o w l e d g e d i s c o v e r y ) 等研究的焦点主要集中到以下几个方面： ( 1 ) 研究专门用于知识发现的数据挖掘语言，也许会像s q l 语言一样走向 形式化和标准化； ( 2 ) 寻求数据挖掘过程中的可视化方法，使得知识发现的过程能够被用户 理解，也便于在知识发现过程中的人机交互； ( 3 ) 研究在网络环境下的数据挖掘技术，特别是在i n t e r n e t 上建立d m k d 服 务器，与数据库服务器配合，实现数据挖掘； ( 4 ) 数据挖掘中的隐私保护与信息安全； ( 5 ) 加强对各种非结构化数据的挖掘( w e b 挖掘) ，如文本数据、图形图像 数据、多媒体数据。 目前，研究的热点问题还包括网站的数据挖掘( w e bs i t ed a t am i n i n g ) 、生物 信息或基因( b i o i n f o r m a t i e s g e n o m i c s ) 的数据挖掘以及文本的数据挖掘( t e x t u a l m i n i n g ) 。 我国计算机科学研究者从1 9 9 7 年以来，在k d w ( k n o w l e d g ed i s c o v e r yi nw e b ) 也即w e b 挖掘方面也进行了大量的研究和努力。其中具有一定影响力的，包括 南京大学的张福炎等对w e b 文档的信息抽取进行的研究，复旦大学的施伯乐等 对半结构化数据模型的研究，以及东南大学的陈澄和王能斌等对半结构化数据 模型进行的研究。 所以，如果能由计算机智能地对文档直接信息进行过滤、分类，更加便捷 地认识和区分不同的文档内容，把用户真正感兴趣的部分提交给用户，这样便 能极大地提高信息的利用率。因而，w e b 文本挖掘成为目前重要的研究课题之 一o 1 2 研究目的 w e b 文本挖掘作为有着广泛的应用前景，主要应用在网络浏览、文本检索、 文本分类、文本聚类、文档总结等。文本挖掘的过程主要有文本的预处理、文 本的表示、特征值的抽取、文本的分类、聚类等，而文本的预处理是文本挖掘 的前提，是基础。预处理的好坏直接决定着后面环节的准确度、效率等。预处 理通常有中文词条的切分，虚词等停用词的识别，姓名、地点、时间等专有名 词的识别等。词切分的正确与否又影响到文本特征的抽取的准确性。目前中文 分词的方法主要有三大类：基于字符串匹配的分词方法、基于理解的分词方法 和基于统计的分词方法。不论哪种方法，由于汉语言的复杂性，都会有一定的 歧义，歧义的存在是不可避免的，可以尽量地缩小歧义产生的可能性。因此本 文针对某些特殊情况提出了动词的判定和优先级的设置来消除歧义的算法，从 而提高了分词的精度，对后面特征值的抽取、文本的分类都起到了至关重要的 作用。 1 3 本文的主要工作 随着中文信息处理的不断发展，出现了许多种分词方法。评定一种分词方 法的优劣主要有两条：分词速度和分词精度。而分词精度尤其重要，除了要建 立较为完备的词库外，还需正确的消除词语切分中存在的歧义问题。本文介绍 了如何实现基本的中文分词，并采用“动词的判定”和“优先级的设置”两种 算法对分词中的歧义进行消除，以此提高分词精度。在中文分词的基础上，通 过设计一个简单的应用程序。利用信息增益和互信息的方法对文本文档进行处 理，对文本文档进行特征选择，抽取代表其特征的元数据或特征词条构成特征 向量，降低噪音。本文在分析比较几种用于文本分类的特征选择方法的基础上， 提出了一种基于信息增益和互信息相结合的特征选择方法。同时，还分析了文 本自动分类的关键理论及技术，重点描述利用k n n ( k n e a r e s t n e i g h b o r ) 、朴素贝 叶斯、支持向量机( s u p p o r t v e c t o r m a c h i n e ) 等来实现文本分类的原理及方法。 1 4 本文创新点 中文分词毕竟不同于英语，没有空格作为词的自然分隔，实现起来有一定 的难度。本文采用正向最大匹配法，设计出一个简单的分词系统，同时对分词 所产生的歧义作了深入的研究，结合语义以及动词的判定，提出了一种新的歧 义消除方法。 2 在特征提取方面，信息增益的方法考察的是每个词条对于整个分类所能提 供的信息量。一个词条的信息增益越大，则说明该词条对于分类提供的信息量 越大。互信息的方法则是考察每个词条与各个类别的相关度，一个词条与一个 类别的互信息越大，则说明二者关联越紧密。通过这两种方法对文本的特征向 量进行降噪处理，能比较准确和贴近的产生出文本的特征向量，对进一步进行 文本的文档总结、文本分类和文本聚类奠定了基础。 在文本分类上采用改进权重的方法与k 近邻方法相结合，提高了分类的精 度。 1 5 全文章节安捧 全文共分六个章节，第一章大致介绍了本文研究的目的、主要内容以及创 新性所在；第二章主要介绍文本挖掘的关键技术，其中包括文本挖掘的含义、 文本挖掘的方法、文本挖掘的模型等：第三章介绍中文分词的方法，并介绍及 实现了相关的歧义消除算法；第四章介绍文本特征的选择方法，并实现了基于 信息增益和互信息相结合的系统设计；第五章分析了文本分类的相关技术，采 用改进权重的方法和k 近邻方法相结合，实现文本的分类，并对其进行了实验； 第六章对文本挖掘的前景进行了展望，并提出了下一步的工作。 第二章文本挖掘技术概述 近年来随着互联网技术的飞速发展，i n t e r n e t 已经成为了世界上最大的信息 积聚地。这些巨量的w e b 信息数据中，蕴涵着巨大潜在价值的知识。i n t e r n e t 上的信息，是以网页形式存放的，而网页的内容又多以文本方式来表示，但它 们的结构更加复杂，风格多样，构成了一个异常庞大的具有异构性、开放性的 分布式数据库。如何快速地、有效地从w e b 上获取有用的知识，已经成为当 今热门的研究方向。文本挖掘0 3 是一个非常活跃的研究领域，是近几年来数据挖 掘领域的一个分支。所以，文本挖掘既采用了很多传统的数据挖掘技术。1 ，又 有自己的特性。 2 1 文本挖掘技术的含义 2 1 1 数据挖掘 数据挖掘( d m ，d a t am i n i n g ) 是从大量的、不完全的、有噪声的、随机的 实际应用数据中采掘出隐含的、先前未知的、对决策有潜在价值的知识和规则 的过程，是知识发现最关键的步骤。数据挖掘的第一步是要确定挖掘的任务， 如进行数据总结、分类、聚类、关联规则发现、特征与偏差、时序模式发现、 趋势分析等，然后才能决定使用何种挖掘算法。选择合适的挖掘算法包括选 取合适的模型和参数，并使得知识发现算法与整个知识发现的评判标准相一 致。 但是数据挖掘的主要对象是结构化的数据仓库“1 ( d a t a w a r e h o u s e ) ，对于w e b 上的异质、非结构化信息，并不能直接应用数据挖掘的技术。 2 1 2 文本挖掘 文本挖掘( t m ，t e x tm i n i n g ) 是近几年来数据挖掘领域的一个新兴分支。其 基本思想是：首先利用文本切分技术，抽取文本特征，将文本数据转化为能描 述文本内容的结构化数据，然后利用聚类、分类技术和关联分析等数据挖掘技 术，形成结构化文本，并根据该结构发现新的概念和获取相应的关系。 2 2w e b 文本挖掘 w e b 文本挖掘是以w e b 文本文档为对象的一种数据挖掘技术，是一门交叉性 学科哺，涉及数据挖掘、机器学习、模式识别、人工智能、统计学、计算机语 言学、计算机网络技术、信息学等多个领域。w e b 挖掘是指从大量非结构化、 4 异构的w e b 信息资源中发现有效的、新颖的、潜在可用的及最终可理解的知识 ( 包括概念( c o n c e p t s ) 、模式( p a t t e r n s ) 、规则( r u l e s ) 、规律( r e g u l a r i t i e s ) 、 约束( c o n s t r a i n t s ) 及可视化( v i s u a l i z a t i o n s ) 等形式) 的非平凡过程抽1 。 2 3 文本挖掘的方法 2 3 1 文本的特征表示 与数据库中的结构化数据相比，w e b 文档具有有限的结构，或者根本就没 有结构。文本信息源的这些特征使得现有的数据挖掘技术无法直接应用于其 上。需要对文本进行预处理。抽取其特征并用结构化的形式保存，作为文档的 中间表示形式。目前，结构化标记语言x m l 能够对w e b 文档资源进行描述。这 将有利于w e b 文档的信息抽取。 特征表示”1 是指以一定的特征项( 如词条或描述) 来代表文档信息，特征 表示模型有多种，常用的有布尔逻辑型、向量空间型、概率型等。近年来应用 较多且效果较好的特征表示法是向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 法。 在v s m 中，将每个文本文档d 看成是一组词条( t 。，t 。，t 。) 构成，对于每 一词条t 。，都根据其在文档d 中的重要程度赋予一定的权值w ，可以将其看成一 个n 维坐标系，w 。，w ：，w n 为对应的坐标值，因此每一篇文档都可以映射为 由一组词条矢量张成的向量空间中的一点，对于所有待挖掘的文档都用词条特 征矢量( t ，w ：( d ) ；t 。，w ：( d ) ；，t 。，w 。( d ) ) 表示。这种向量空间模型的表 示方法，可以将d 中出现的所有单词作为t 。，也可以将d 中出现的所有短语作为 t 。，从而提高特征表示的准确性。w 。( d ) 一般被定义为t ，在d 中出现率t f ，( d ) 的函 数，即w 。( d ) = ( t f 。( d ) ) 。常用的v 有： 布尔函数：v = ：鼢乞崔。 平方根函数：v = 钡d ) 对数函数：1 l ，= l g ( t f i ( d ) + 1 ) t f i d f i 函：1 l ，：t f i ( d ) l g 盟 i u n 为所有文件的数目，n 。为含有词条t ，的文件数目。 2 3 2 文本的特征子集的选取 构成文本的词汇，数量是相当大的，因此表示文本的向量空间的维数也相 当大，可以达到几万维，因此我们需要进行维数压缩的工作。目前对w w w 文档 特征所采用的特征子集选取算法一般是构造一个评价函数，对特征集中的每一 个特征进行独立的评估，这样每个特征都获得一个评估分，然后对所有的特征 按照其评估分的大小进行排序，选取预定数目的最佳特征作为结果的特征子 集。 一般采用的评估函数“1 有信息增益( i n f o r m a t i o n g a i n ) 、期望交叉熵( e x p e c t e d c r o s s e n t r o p y ) ，互信息( m u t u a l i n f o r m a t i o n ) 、文本证据权( t h e w e i g h to f e v i d e n c e f o r t e x t ) 、几率比( o d d s r a t i o ) 、词频( w o r df r e q u e n c y ) 等。 2 3 3 文本分类 试图对w e b 上的所有文档进行分类是不可行的，这里提供的分类方法更适 合于对特定的专业领域的w e b 文档进行分类。文本分类是一种典型的有指导机 器学习问题。一般分为训练和分类两个阶段“”，具体过程如下： 训练阶段： ( 1 ) 根据该专业领域已有的分类体系，事先确定类别的集合c = c l i ”，c i i ， c ) ，这些类别可以是层次式的，也可以是并列式的； ( 2 ) 选择适量具有代表性的w e b 文档，给出训练文档集合s = s l ，“，s j ，s 。 ； ( 3 ) 对于s 中的每个训练文档s ，确定其所属的类别c 。； ( 4 ) 抽取训练文档s 。的特征，得到特征向量v ( s ，) ； ( 5 ) 统计s 中所有文档的特征矢量v ( s ，) ，以此确定代表c 中每个类别的特征 矢量￥( c 。) ； 分类阶段： ( 1 ) 对于测试文档集合t = d l i ”，d “，d ， 中的每个待分类文档d 。，计算其特 征矢量v ( d 。) 与每个v ( c 。) 之间的相似度s i m ( d 。，c 。) ； ( 2 ) 选取相似度最大的一个类别作为d 。的类别。有时也可以为d 。指定多个 类别，只要d 。与这些类别之间的相似度超过某个预定的阈值。如果d 。与所有类 别的相似度均低于阈值，那么通常将该文档放在一边，由用户来做最终决定。对 于类别与预定义类别不匹配的文档而言，这是合理的，也是必须的。如果这种情 况经常发生，则说明需要修改预定义类别，然后重新进行上述训练与分类过程。 在计算s i m ( d 。，c 。) 1 时，有多种方法可供选择。最简单的方法是仅考虑两个特征 矢量中所包含的词条的重叠程度。即 酊m ( d k , c o2 搿【公式2 1 】 其中，r l 。( d 。，c ；) 是v ( d 。) 和v ( c 。) 具有的相同词条数目，n ，( d 。，c ，) 是v ( d 。) 和 v ( c 。) 具有的所有词条数目。 最常用的方法是考虑两个特征矢量之间的夹角余弦，即 s t 州沪揣 【公式2 2 】 训练方法和分类算法是分类系统的核心部分，目前存在多种基于向量空间 模型的训练算法和分类算法“”，例如，支持向量机算法、神经网络方法，最大平 均熵方法，最近k 邻居方法和贝叶斯方法等等。 2 3 4 文本聚类 文本聚类“3 1 是从给定的文档本身出发，根据文档特征词矢量，将相关者聚 成一类。根据文本聚类的结果不同，可以将聚类方法分为层次聚类法和平面聚 类法两种类型。对于给定的文档集合d = d l i ”，d 。，d 。) ，层次聚类的过程如 下： ( 1 ) 将d 中的每一个文档d 。作为一个聚类中心c 产f d 。 ，形成d 的一个聚类集 合c = c l ，”，c i “，c 。 ； ( 2 ) 计算c 中每个聚类对( c ，c ，) 之间的相似度s i m ( c ，c ，) ； ( 3 ) 选取具有最大相似度的两个聚类( c 。，c j ) 一一m a xs i m ( c 。，c ，) ，将合并 成一个新的聚类c 。：c ，uc ，同时合并c ，和c ，的特征矢量，从而构成了d 的一个 新聚类集合c = c 1 ，”，c k ，c 。) ； ( 4 ) 重复上述步骤，根据所要产生聚类的数目和相似度阈值限制，得到最 终聚类结果。 平面划分法与层次凝聚法的区别在于，它将文档集合水平地分割为若干个 聚类，而不是生成层次化的嵌套聚类。对于给定的文档集合d = ( d l ，”，d i i ”，d 。 ，平面划分法的具体过程如下： ( 1 ) 确定要生成的聚类的数目k ； ( 2 ) 抽取d 中每个文档的特征矢量v ( d 。) ； ( 3 ) 从d 中抽取k 个文档形成聚类的中心s = s l ，“，s j j “，s t 。为了提高聚类 的准确度，在确定聚类中心时应该依据定的原则。常用的确定聚类中心的方 法有逆中心距法和密度测试法等。 ( 4 ) 对d 中的剩下的文档，依次计算它们与各个聚类中心的相似度 s i m ( d 。，s ，) ；根据预定的相似度阈值，将文档聚集在聚类中心的周围，形成稳 定的聚类结果。 从上面的聚类过程可以看出，层次聚类对文档集合d 中的每一个文档进行 了多次遍历，其结果实质上构造出了一个生成树，其中包含了聚类的动态过程 和层次信息。层次聚类方法是最为常用的聚类方法，因为它能够产生层次化的 嵌套聚类，所以有很高的准确度。另外，在层次聚类过程中，最大相似度呈递 减趋势，因此必须确定适当的相似度阈值，保证同一个聚类中文档的紧密相关。 而平面划分法的运行速度较快，但是必须事先确定k 的取值，且种子选取的好 坏对聚类结果有较大影响。 2 4 文本挖掘模型 基于w e b 的文本挖掘系统n 最终挖掘出来的知识或者模式信息如果能够用 可视化的方式进行显示，同时对用户提供信息导航的功能，那么将在极大的程 度上方便用户有效、快速地浏览和获取信息。鉴于该目的的考虑，本文在设计 信息挖掘过程中将提供信息表示和信息导航功能。信息导航的原则是提供给用 户简便、多视角的方法。通过使用可视化图形界面的信息表示技术和信息导航 技术“”，用户将能够更快地接受信息并根据自己的兴趣度对所反馈的挖掘结果 进行有目的的查询和浏览。如图2 1 所示。 图2 1 文本挖掘模型的结构图 该文本挖掘结构模型的工作流程安排如下： ( 1 ) 特征提取：对w e b 上收集到的挖掘目标样本进行特征提取，生成挖掘 目标的特征矢量；特征项集选取应该根据两个基本原则即完全性和区分性原则 来进行，并将提取得到的特征矢量经过特征子集的选取后存放到文本特征库中 形成文本中间表示形式。 ( 2 ) 文本挖掘过程：将数据挖掘中的若干算法进行适当改进后，对于w e b 文本的中间表示形式进行挖掘处理，得到潜在的知识或者模式。 ( 3 ) 挖掘结果评价：将挖掘得到的知识或者模式进行评价，将符合一定 标准的知识或者模式呈现给用户。 ( 4 ) 信息表示和信息导航：将反馈的结果用可视化的方式迸行显示，同 时对用户提供信息导航功能，从而在极大的程度上方便用户有效的浏览和获取 信息。 8 2 5 挖掘的应用前景 随着i n t e r n e t 技术的迅速发展和不断的普及应用，网络信息资源越来越丰 富，如何分析和利用这些海量的数据，是当前比较突出的一个问题。网络信息 挖掘在实际工作中具有重要的实践意义和广阔的应用前景。 在电子商务领域“，网络信息挖掘可以提供不同用户的特定信息，有的放 矢地传播网络广告，可以建立客户关系管理系统，极大地提升企业的竞争优势； 在电子政务领域，通过对政务数据进行定性和定量分析，可为高层管理者提供 决策参考；可以提高搜索引擎获取信息的准确性，并可以对用户搜索结果进行 相关处理，可以提高查准率和查全率。 目前，各种应用服务越来越多，电子邮件、b 1 3 s 等成为人们普遍采用的信 息传播手段，网络信息的管理工作成为大家越来越关注的问题。 2 6 本章小结 w e b 挖掘是w e b 技术中一个重要的研究领域，w e b 文本挖掘是将数据挖掘技 术应用于互联网的知识发现过程，它同时具有自身的特点。w e b 文本挖掘是w e b 挖掘的重要代表，可以使用户比较准确找到需要的资料，可以帮助用户节约检 索时间，可以提高w e b 大量的真正有价值等，它使充分利用w e b 大量的真正有价 值的信息成为可能，为智能化w e b 奠定了基础。w e b 文本挖掘技术也将随着人工 智能等学科的发展而发挥更大的作用，是人类在信息社会中应用互联网面临的 一个新的挑战。 9 第三章中文分词算法研究及其实现 现代社会是一个高度信息化的社会，需要利用计算机来处理大量的以自然 语言为载体的信息。如何把文章切分成词条，并且把特征词条组成特征向量成 为文本处理的关键。 对比中文和英文两种语言，二者在形式上截然不同。英文书写时，词与词 之间用空格隔开，词间界限泾渭分明：而中文是字的序列，词与词之间没有间 隔标记，而词又是中文中最小的能够独立运行的语法单位，所以必须经过“分 词”处理后，计算机才能进行下一步的分析，因此对中文的自动分词，是中文 信息处理的基础和前提。中文信息处理是文本挖掘重要的研究内容之一，而中 文自动分词又是中文信息处理中的关键技术之一，尤其是对于海量信息处理的 应用有很大的影响，分词的速度是极为重要的，对整个系统的效率有很大的影 响。因此对于这个课题的研究有很大的现实意义。 3 1 中文词语切分的方法 简单地说，分词就是将连续的字( 词) 序列按照一定的规范重新组合成词 序列的过程“。信息处理现代汉语分词规范中对分词的定义是：从信息处 理需要出发，按照特定的规范，对汉语按分词单位进行划分的过程。具体到计 算机科学，中文分词则是在计算机中通过人为的规则，编写一个计算机应用程 序来对中文文本进行处理，得到词的序列的过程。 现有的分词算法可分为三大类“”：基于字符串匹配的分词方法、基于理解 的分词方法和基于统计的分词方法。 3 1 1 基于字符串匹配的分词方法 这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与 一个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则 匹配成功( 识别出一个词) 。 按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按 照不同长度优先匹配的情况，可以分为最大( 最长) 、匹配和最小( 最短) 匹配； 按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结 合的一体化方法。常用的几种机械分词方法如下： ( 1 ) 正向最大匹配法 正向最大匹配法是最早提出的中文分词方法。基本思想为：设d 为词库， m a x 为d 中最大词长，s t r 为待切分字符串。由左至右地从s t r 里获得长度为 1 0 m a x 的字符串，并与词库匹配。匹配成功，则作为一个词语切分开来；反之， 将长度为m a x 的字符串的最后一个字符删除，再与词库匹配，直至匹配出一个 词语为止。对s t r 里的剩余部分重复此工作，直至所有的词语都被切分开来为 止。 ( 2 ) 逆向最大匹配法 逆向最大匹配法与正向最大匹配法大同小异。不同的是：逆向最大匹配法 是由右至左地从s t r 里获得长度为m a x 的字符串。 ( 3 ) 双向匹配法 双向匹配法是正向最大匹配法和逆向最大匹配法的组合。 就目前阶段而言，正向最大匹配法和逆向最大匹配法切分技术较为成熟， 思路清晰，算法比较简单，易于计算机实现。但是因为完全依赖于词库，故分 词效率和准确性受到了词库容量的束缚，并且对于分词中出现的歧义问题也无 法很有效的消除。 实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过利用 各种其它的语言信息来进一步提高切分的准确率。 3 1 2 基于理解的分词方法 这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。 其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息 来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控 部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语 义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方 法需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以 将各种语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统 还处在试验阶段。 3 1 3 基于统计的分词方法 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现 的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够 较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行 统计，计算它们的互现信息。互现信息体现了汉字之间结合关系的紧密程度。 当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个词。这种方法 只需对语料中的字组频度进行统计，不需要切分词典，因而又叫做无词典分词 法或统计取词方法。但这种方法也有一定的局限性，会经常抽出一些共现频度 高、但并不是词的常用字组，并且对常用词的识别精度差，时空开销大。实际 应用的统计分词系统都要使用一部基本的分词词典( 常用词词典) 进行串匹配 分词，同时使用统计方法识别一些新的词，即将串频统计和串匹配结合起来， 既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文 识别生词、自动消除歧义的优点。 到底哪种分词算法的准确度更高，目前并无定论。对于任何一个成熟的分 词系统来说，不可能单独依靠某一种算法来实现，都需要综合不同的算法。 3 2 分词中的两大难题 有了成熟的分词算法，是否就能容易的解决中文分词的问题昵? 事实远非 如此。中文是一种十分复杂的语言，让计算机理解中文语言更是困难。在中文 分词过程中，有两大难题一直没有完全突破。 3 2 1 歧义识别 歧义是指同样的一句话，可能有两种或者更多的切分方法。歧义大致可以 分为以下几种n ： ( 1 ) 交集型歧义 例如：网球场，因为“网球”和“球场”都是词，那么这个短语就可以分 成“网球场”和“网球场”。这种称为交叉歧义。像这种交叉歧义十分常见， 再如；“化妆和服装”可以分成“化妆和服装”或者“化妆和服装”。两 种切分方法在语法、语义上都是正确的，由于没有人的知识去理解，计算机很 难知道到底哪个方案正确，必须依靠上下文的语言环境才可以给以正确的切 分。 ( 2 ) 组合型歧义 组合歧义必需根据整个句子来判断了。例如，在句子“这个门把手坏了” 中，“把手”是个词，但在句子“请把手拿开”中，“把手”就不是一个词； 在句子“将军任命了一名中将”中，“中将”是个词，但在句子“产量三年中 将增长两倍”中，“中将”就不再是词。对于类似与此类的歧义，计算机就很 难进行识别和处理了。 ( 3 ) 真歧义 在歧义中还有一个难题就是真歧义。真歧义意思是给出一句话，由人去判 断也不知道哪个应该是词，哪个应该不是词。例如：“乒乓球拍卖完了”，可 以切分成“乒乓球拍卖完了”、也可切分成“乒乓球拍卖完了”。如 果没有上下文其他的句子，就很难知道“拍卖”在这里算不算一个词。 1 2 3 2 2 新词识别 新词，专业术语称为未登录词。也就是那些在字典中都没有收录过，但又 确实能称为词的那些词。 新词识别包括： 数字识别： 命名实体识别，如：人名、地名、机构名、专业术语； 形式词、离合词识别，如：看一看、打听打听、高高兴兴、游了一会儿泳、 担什么心等。 对于现在的搜索引擎来说，分词系统中的新词识别十分重要。目前新词识 别准确率已经成为评价一个分词系统好坏的重要标志之一。 3 3 歧义消除算法研究 经过对比不同方法的优缺点，本文采用了比较常用的基于字符串匹配的正 向最大匹配法的算法”“，设计了一个简单的分词系统，系统工作流程如图3 1 所示。 图3 1 系统工作流程 在此基础之上，采用了一种简单的消除歧义的方法一一“退一字组合法”。 在针对由动词、助词在词语切分中可能产生的歧义的问题，提出了“动词的判 定”的方法，在分词系统的数据库中添加了一些容易产生歧义的动词表和助词 表”“”1 ，通过判断动词前的一个单字以及这个单字前的助词是否能组合成一个 词，消除了如：“菜的确切的不错”、“和服装了车”等类似产生交集型歧义的 语句的错误词语切分。 为了进一步消除词语切分中存在的歧义问题，受数学运算中乘除式的优先 级高于加减式的启发，又提出了“优先级的设置”的方法，在分词系统里添加 有关词语的优先级词库，根据优先级的关系，优先级高的词被优先选定，从而 对句子进行正确的词语切分。 3 3 1 一种简单的歧义消除法 在使用正向最大匹配法时，采用一种简单的歧义消除法一一“退一字组 合法”。该方法的基本思想是：如果当前匹配的词语a 是单字的时候，取紧邻a 前面的词语d 的最后一个字b 进行组合， ! 导到新词c ；再与相应的词库进行匹 配，若匹配成功，将b 从d 中剔除，将c 存入；反之，d 不变，将a 存入。 例如：“大学生活丰富多彩。”，利用正向最大匹配法直接切分的结果出现 了“大学生活丰富多彩”，如图3 2 所示；而加入“退一字组合法”程序段 豹分