（计算机应用技术专业论文）基于后缀树的中文文本聚类算法研究.pdf

摘要 文本挖掘是指在大量文本集合上发现隐含的、有趣的、有用的模式和知识。文本 挖掘技术的出现，使得汁算机处理大规模文本资源成为可能，对文本的处理，在信息 检索等领域有着广阔的应用前景。 本文研究基于后缀树的中文文本聚类。文本聚类是文本挖掘重要手段和研究分 支。后缀树作为一种数据结构，最早是为支持有效的字符串匹配和查询而提出的，例 如：寻找最长的重复子串，相似串的匹配，串比较等问题。后缀树聚类( s t c ) 方法 的一个突出的特点是将文本看作短语串而非词的集合，这样可以更充分地使用词语之 间的近似信息，达到更佳的聚类结果。s t c 已经在英文文本聚类中有了一些成功的应 用，本文针对中文文本的特点，尝试将这种方法应用到中文文本聚类上。 本文对数据挖掘尤其是中文文本聚类及相关理论与技术进行了研究，主要包括以 下内容： ( 1 )对文本聚类算法进行了研究，特别是k 一平均算法及其在中文文本中的应 用。 ( 2 )针对中文文本组成上的特点，研究了中文文本聚类的模型。 ( 3 )研究并验证了后缀树技术在中文文本聚类这一特定领域应用的可行性。 ( 4 )设计并实现了一个小型的中文文本聚类系统，可以进行k 平均和s t c 聚 类。 ( 5 )通过几组中文文本数据集对卜平均和s t c 两种聚类算法进行了实验稚：比 较，得出了一些有用的结果，并从理论上作了进一步的说明和论证。同时， 对试验中出现的问题进行了探讨，并提出了进一步研究的方向。 ；关键字：文本挖掘，文本聚类，中文文本，k 一平均，后缀树聚类( $ t c ) 注 本文的研究得到上海市教委科研基金资助( 编号：q 4 f b 2 2 ) a a b s t r a c t t e x tm i n i n gm e a n st h ei m p l i e d ，u s e f u la n di n t e r e s t i n gp a t t e r n sa n dk n o w l e d g e d i s c o v e r e di ns u b s t a n t i a lc o n g l o m e r a t i o no ft e x ld o c u m e n t so rc o r p u st h e a v a i l a b i l i t yo ft e x tm i n i n gt e c h n i q u em a k e si tp o s s i b l et op r o c e s st h el a r g es t o r eo f t e x tr e s o u r c e si ng r e a tb a t c h e s t h ep r o c e s s i n gu p o nt e x t so f f e r sm u c hp o t e n t i a lf o r d e v e l o p m e n ti ns u c hf i e l d sa si n f o r m a t i o nr e t r i e v a l t h et h e s i si sw i l ld e a lw i t ht h et e x tc l u s t e r i n g t e ) ( tc l u s t e r i n gw h i c hi sk n o w na s as i g n i f i c a n tw a yt o w a r d st e x tm i n i n ga n da tt h es a m et i m ea ni m p o r t a n tb r a n c ho f d a t am i n i n g ，l a y si t se m p h a s i so nc h i n e s et e x tc l u s t e r i n gb a s e do ns u f f i xt r e e a sa d a t as t r u c t u r e t h es u f f i xt r e ew a sf i r s tp r e s e n t e dt os u p p o r tt h es t r i n gm a t c h i n ga n d q u e r i e s ，f o ri n s t a n c e ：s e a r c h i n gt h em a x i m u mr e p e t i t i o ns u b s t r i n g ，m a t c h i n go ft h e s i m i l a rs t r i n g s ，s t i n g sc o m p a r i s o n s e t c s t ci sam e t h o dt h a tr e g a r d st h et e x ta s p h r a s es t r i n gn o ta sw o r dc o r p u s t h u si te n a b l e su st ou s et h es i m i l a ri n f o r m a t i o n b e t w e e nt h ep h r a s e st oe f f e c tab e t t e r c l u s t e r i n g s t c h a sa l r e a d yb e e n s u c c e s s f u l l yu t i l i z e di ns o m ea r e a si ne n g l i s ht e x tc l u s t e r i n g t h i sp a p e r i sd e v o t e d t oa f f e c tt h es t ci nc h i n e s et e x tc l u s t e r i n g t h i sp a p e ru n d e r l i n ei t se m p h a s i so nt h et e c h n i q u e sa n dt h e o r i e so fd a t a m i n i n g ，e s p e c i a l l yf o c u s e so nc h i n e s et e x tc l u s t e r i n g t h ep a p e ri n c l u d e s t h e f o l l o w i n gm a i na s p e c t s ： ( 1 ) r e s e a r c ho nt e x tc l u s t e r i n ga l g o r i t h m ，e s p e c i a l l yo nk - m e a n sa l g o r i t h m a n di t sa p p l i c a t i o nt ot h ec h i n e s et e x t s ( 2 ) s t u d y o nc h i n e s et e x t c l u s t e r i n g m o d e l si n c o m p l i a n c e w i t ht h e c h a r a c t e r i s t i c so fc h i n e s et e x t s ( 3 ) t h ef e a s i b i l i t y o fa p p l y i n gt h es u f f i xt r e e t e c h n i q u e t oc h i n e s et e x t c l u s t e r i n gh a sb e e ns t u d i e dd e e p l ya n dt e s t e d ( 4 ) d e s i g na n di m p l e m e n tac h i n e s et e x tc l u s t e r i n gs y s t e mw h i c hh a st h e c l u s t e r i n gf u n c t i o ni nt h ek - m e a n sa n ds t ca l g o r i t h m s ( 5 ) s o m ev a l u a b l er e s u l t so ns e v e r a lg r o u p so ft h ec h i n e s et e x td a t as e t sa r e o b t a i n e da n d t h e o r e t i c a l l ye x p l a i n e da n d d e m o n s t r a t e da f t e rs o m e e x p e r i m e n t sa r ec a r r i e d o u ta n dc o m p a r i s o n sa r em a d eb e t w e e nt h e b k - m e a n sa n ds t ca l g o r i t h m st h ep r o b l e m so c c u r r e di nt h ee x p e r i m e n t s a r ed i s c u s s e da n daf u t u r er e s e a r c hd i r e c t i o ni sp r e s e n t e d l ul i h u a ( c o m p u t e r a p p i i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f g a om a o t i n g k e y w o r d s ：t e x tm i n i n g ，t e x tc l u s t e r i n g ，k - m e a n s ，s t c c 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成 果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其他 机构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做 的贡献均已在论文中作了明确的声明并表示了谢意。 作者签名：三雏曰期：7 r 7 0 s 7 上 论文使用授权声明 本人同意上海海事大学有关保留、使用学位论文的规定，即：学 校有权保留送交论文复印件，允许论文被查阅和借阅；学校可以上网 公布论文的全部或部分内容，可以采用影印、缩印或者其它复制手段 保存论文。保密的论文在解密后遵守此规定。 作者签名：雠导师签名： 毒髟勉日期：型：乙 基于后缀树的中文文本聚类算法研究 引言 全球范围内数据库中存储的数据量急剧增加，数据库系统提供了对这些数据的 管理和简单的处理能力，人们可以利用这些数据进行商业分析和科学研究。面对庞 大的数据库，人们的需求已经不只是简单的查询和维护，而是希望能够对这些数据 进行较高层次的处理和分析以得到关于数据总体特征和对发展趋势的预测。而这些 功能是数据库技术、人工智能和统计学等无法单独完成的。我们淹没在信息之中， 但仍处于知识的饥渴中。由此，数据挖掘技术便应运而生。数据挖掘技术的出现， 使得人们得以借助计算机强大的运算能力，从海量的数据中揭示出鲜为人知的规律， 从而对未来进行有限的和无限的预测。 随着互联网的迅速发展，网络上汇集了复杂的文本结果、图像、声音等多种信 息，其中存储信息使用最多的是文本。如何从众多的文本中找到自己需要的知识， 这就使得文本挖掘成为又一个新的研究热点。根据中国互联网络信息中心调查表明， 国内w w w 站点数已达到几十万个，如何从众多的中文文本中获得隐藏在数据背后的 知识，就是中文文本挖掘迫切需要解决的问题。 本文就是在这样的背景之下展开的，设计了面向中文文本的聚类系统，使用面 向对象技术进行分析和设计，以d e l p h i7 o 作为开发工具。 本文分为五章，第一章介绍了数据挖掘及相关技术、文本挖掘的现状以及本文 的研究工作；第二章介绍了文本聚类的过程及文本聚类领域的几个主要算法：第三 章结合本文设计的系统，对中文文本聚类涉及的若干关键技术进行了阐述；第四章 重点介绍了本文设计的中文文本聚类系统，分别对k 一平均和s t c 两个算法，介绍了 系统设计的过程、关键性的几个步骤、系统的实现及算法的评估等：第五章给出了 全文的总结，并对下一步的工作提出了展望。 基于后缀树的中文文本聚类算法研究 1 1 数据挖掘技术介绍 第1 章绪论 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，数据库中存储的 数据量急剧增大，激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行 更高层次的分析，以便更好的加以利用这些数据。但是目前的数据库系统功能无法 发现数据中存在的关系和规则，难以预测未来的发展趋势，陷入“数据爆炸但却知 识贫乏”的境地，而数据挖掘的出现为我们带来了希望。 数据挖掘是一个处理过程，它是数据库、人工智能和数理统计技术的结合和发 展，它利用一种或多种计算机学习技术，从数据库中自动分析并提取知识。 1 1 l 数据挖掘的涵义 从技术上来说，数据挖掘( d a t am i n i n g ，d m ) 就是从大量不完全的、有噪声 的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但 又是潜在有用的信息和知识的过程。 一般地，数据挖掘被认为是k d d ( k n o w l e d g e d i s c o v e r y i n d a t a b a s e ) 中的一个 重要步骤。图1 1 是目前公认的k d d 的主要过程。 数据强 图卜1k d d 过程 数据挖掘阶段是整个系统的核心部分，它的主要任务是运用各种算法，接受人 基于后缎树的中文文本聚类算法研究 机交互输入的各种参数，寻找数据仓库中可能的、潜在的、有价值的概念、规则、 模式、规律或约束，并以各种知识表达的方式表示出来。 从商业上来说，数据挖掘是一种新的商业信息处理技术，其主要特点是对商业 数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助 商业决策的关键性数据。 1 1 2 数据挖掘的过程 在数据挖掘中被研究的业务对象是整个过程的基础，它驱动了整个数据挖掘过 程，也是检验最后结果和指引分析人员完成数据挖掘的依据和顾问。图1 - 2 中各步 骤是按一定顺序完成的，当然整个过程中还会存在步骤间的反馈。 图1 2 数据挖掘的基本过程和主要步骤 一个完整的数据挖掘过程包括： ( 1 ) 定义商业问题：了解数据和业务问题，定义一个清晰明确的目标。 ( 2 ) 数据准备：包括数据选择、数据清洗和预处理、数据变换3 个步骤。 a ) 数据选择：搜索所有与业务对象有关的内部和外部数据消息，并从中选 择出使用于数据挖掘应用的数据。 b ) 数据清洗和预处理：研究数据的质量，为进一步的分析做准备，并确定 将要进行的挖掘操作的类型。 c ) 数据变换：将数据转换成一个分析模型。 ( 3 ) 建立模型：选取数据挖掘工具提供的算法并应用于准备好的数据，选取相 应的参数，生成模型。 ( 4 ) 评价模型：对模型进行比较和评估，生成一个相对最优模型，并对此模型 用业务语言加以解释。 ( 5 ) 实施与维护模型：对模型在实际应用的表现进行监控，并对模型进一步的 考察和修正，以反映业务运作规律的变化。 基于后缀树的中文文本聚类算法研究 1 1 3 数据挖掘的主要方法 数据挖掘算法是将实例从原始数据转换为数据挖掘模型的数学和统计学的算 法，数据挖掘模型最终的形式很大程度上依赖于对数据所应用的数据挖掘算法。数 据挖掘的主要方法有关联分析、决策树、分类、聚类、时序模式、偏差分析等【”。 ( 1 ) 关联分析 关联分析的目的是发现特征之间或数据之间的相互依赖关系。数据的相关性代 表了一类重要的可发现的知识。一般用支持度和可信度两个阀值来度量两个元素间 的相关性。 ( 2 ) 分类与预测 分类就是找出一个类别的概念描述，它代表了这类数据的整体信息，即该类的 内涵描述，并用这种描述来构造模型，一般用规则或决策树模式表示。分类是利用 训练数据集通过一定的算法而求得的分类规则，分类可被用于规则描述和预测。 预测是利用历史数据找出变化规律，建立模型，并由此模型对未来数据的种类 及特征进行预测。预测关心的是精度和不确定性，通常用预测方差来度量。 ( 3 ) 聚类分析 聚类是根据数据的不同特征，将其划分为不同的数据类。目的是使得属于同一 类别的个体之间的“距离”尽可能的小，而不同类别上的个体间的“距离”尽可能 的大。 ( 4 ) 时序模式 时序模式是指通过时间序列搜索出的重复发生概率较高的模式。时序模式通过 历史的和当前的数据推测未来的数据，也可认为是以时间为关键属性的关联分析。 ( 5 ) 偏差分析 偏差分析的基本思想是寻找观察结果与参照量之间的有意义的差别。通过发现 异常，可以引起人们对特殊情况的加倍注意。 1 2 文本挖掘 随着互联网的迅速发展，网络上汇集了复杂的文本结果、图像、声音等多种信 息，其中存储信息使用最多的是文本：根据中国互联网络信息中心( c n n i c ) 第十 五次中国互联网络发展状况统计报告调查表明，截至2 0 0 5 年1 月，国内w w w 站点数已达到6 6 8 9 0 0 个。如何从众多的文本中找到自己需要的知识，这就使得文本 基于后缓树的中文文本聚类算法研究 挖掘成为又一个新的热点。1 9 9 5 年，r o n e nf e l d m a n 在k d d 9 5 上发表了( ( k n o w l e d g e d i s c o v e r yi nt e x t u a ld a t a b a s e ) ) 一文【2 】【孙，这被认为是文本挖掘的第一篇研究文献， 同时也标志着文本挖掘领域的兴起。 1 2 1 文本挖掘的涵义 i 文本挖掘是结合机器学习、数掘挖掘、自然语言理解、信息检索和知识管理等 技术，从大量的文本数据中发现和提取隐含的、事先未知的知识，最终形成用户可 理解的、有价值的信息和知识的过程。涉及了对文本集合的预处理、中间形式的处 理以及结果的可视化f 4 。 1 2 2 文本挖掘的过程 a h h w e et a n 给出了文本挖掘的框架，他认为文本挖掘可以分为文本提炼和知 识提取两个阶段| 5 】。文本提炼过程将自由格式或半结构化的文本转变为中间形式 知识提取过程从文本中间形式中提取模式和知识。总体上说，文本挖掘的一般处理 过程分为四个阶段：特征表示、特征降维、模式挖掘和模式评价，如图1 3 所示。 图卜3 文本挖掘的一般处理过程 首先要对文档集中的文本进行特征表示，文本通常为半结构化格式甚至是非结 构格式，因此，为了便于处理，需要抽取和描述文档集中文本的特征，并在此基础 上进行结构化特征表示。一般来说，文本初始选取的特征向量维数会非常高，因此 需要进行特征降维处理，来缩减文档特征表示向量的维数，然后在已经结构化、数 值化表述的文档特征空间基础上利用数据挖掘、机器学习、神经网络等方法来提取 兴趣模式，最后以一定的质量评价指标对获取的模式进行评价。 1 2 3 文本挖掘的应用背景 文本挖掘具有广阔的应用背景和商业前景，不仅可以用于企业的决策部门，还 基于后缀树的中文文本聚类算法研究 可以为综合信息网站提供服务。它可以帮助企业分析文档，从大量的文档中挖掘出 对企业有用的信息。应用主要包括以下几个方面： ( 1 ) 文档管理 对于许多企事业单位、政府机关来说，文档管理是一项很纷繁但又极为重要的 工作，通过文本挖掘，可以帮助组织有效的管理文档，比较典型的应用，如自动对 文档进行分类，对文档进行摘要以方便管理和使用。 ( 2 ) 电子邮件的管理 基于文本挖掘技术的电子邮件路由通过对邮件的来源、内容进行分析后，使得 企业各部门能及时的对信息进行跟踪和反馈，并且可以根据邮件的内容进行统计分 析，同时可以从客户的邮件中挖掘到客户对产品的意见和反馈信息等。 ( 3 ) 企业市场研究 企业可以通过对文本挖掘系统对从包括互联网在内的各种渠道收集到的市场报 告进行挖掘统计，进而对市场进行客观的、及时的、有效的统计分析。 ( 4 ) 情报收集 企业通过基于文本挖掘技术的个性化搜索引擎系统，收集到与企业自身相关的 情报信息，如供求信息、竞争对手信息、技术报告信息、专利信息、会展信息、人 爿信息等，并在这些信息的基础上做出对企业有用的分析报告。 ( 5 ) 企业资源规划 挖掘企业的报告、活动及事件，进而更合理的配置和规划企业有限的自身资源， 增加市场竞争力。 12 4 文本挖掘的产品及应用 目前市场上已经出现了很多文本挖掘产品，下面介绍几个比较典型的文本挖掘 产品及其应用： 0 ( 1 ) i b m 的t e x t m i n e r 在文本挖掘软件中，t e x t m i n e r 很具有代表性，其主要功能是特征抽取、文档聚 集、文档分类和检索。t e x t m i n e r 的特征抽取器能从文档中抽取人名、组织名和地名 以及由多个词组成的复合词。抽取完特征以后，有相似特征的文档就被自动聚集成 一个集合。利用这一功能，知识管理系统可以从大量文档中找到相关文档。同时 t e x t m i n e r 还可以对文档进行自动分类。 ( 2 ) a u t o n o m y 公司的a g e n t w a r e 6 基于后缀树的中文文率聚娄算法吲究 该工具可以为用户提供一个自动和精确的分类、交叉验证和表示信息的方法， 能够监视特定的因特网和企业内部网、新闻网站和内部文档库，并且生成关于这些 被监视对象的变化报告。 ( 3 ) m e g a p u t e r 的t e x t m i n e r 该工具是一个智能文本挖掘和语义信息搜索系统，它采用了独特的神经元网络 技术，实现了对自然语言文本的结构化处理，可以用来创建知识库、搜索语义信息 和自动抽取文本。 ( 4 ) t e l t e c h ( 电科) 公司 该公司采用文本挖掘技术提供专家服务、专业文献检索服务、产品与厂商检索 服务，在商业上取得了相当大的成功。t e l t e c h 成功的关键是建立了高性能的知识 结构，采用主题法，其主题词表分为不同专业，共有3 万多个，由数位知识工程师 维护，每周更新5 0 0 一1 2 0 0 个词。 除此以外，还有一些其他的产品和应用，如i b m 与s y n t h e m a 合作- 丌发的 t e c h n o l o g yw a t c h ，该系统是文本挖掘在科学领域的应用，它对专利数据库和技术刊 物蛆图的方式对结果进行聚类；k d s 的c o n c e p t 探测器，该工具是发现w e b 文档相 关内容的可视化智能搜索工具，它通过从训练文档集中学习词语间的关系来可视化 的指导用户生成检索词等等。 i 3 本文的研究方向和意义 在文本挖掘中，文本聚类以其能发现未知的知识而在近几年发展极为迅速。它 不仅可以进行不同文档的比较及文档重要性和相关性排列等问题，而且对于提耿相 关文本的显著特征，自动形成查询条件以及查找文本数据库中相似文本也很有用。 1 - 3 1 聚类研究的现状 聚类分析的研究工作可以分为两大类：一类是通用的聚类方法和算法的研究 另一类是研究不同类型领域的聚类。其组织结构如图l 一4 所示。 赫于后缀树的中文文本聚类算法研究 匿圜 圆圜 图1 4 聚类分析组织结构 1 31 1 通用的聚类方法和算法 通用的聚类方法和算法是针对结构化数据，通常有以下几类： f i ) 划分方法( p a r t i t i o n i n gm e t h o d ) 它是将数掘集划分成k 个簇，且每个簇中至少包含一个数据元素。每个数据元 素可以属于多个簇( 模糊划分) 或仅属于一个簇( 确定性划分) 。给定划分数k ，划 分方法首先创建一个初始划分，然后采用种迭代的重定位技术，尝试通过对象在 簇问的移动来改进划分。 目前使用最多的是k 一平均算法和k 冲，山点算法。为了对大规模的数据集进行聚 类，盼及处理复杂形状的聚类，基于划分的方法需要进一步的扩展。 f 2 ) 层次的方法( h i e r a r c h i c a lm e t h o d ) 层次聚类算法是传统的处理聚类数目未知情况的聚类方法，包括分裂式层次聚 ：类法和聚合式层次聚类法。前者是将所有数据对象整个作为一个聚类，然后按照使 目标函数值最优的原则将其拆分为两个聚类，之后选择聚类直径最大的类再次按照 。同样的原则进行再次拆分，直至目标函数值不再降低为止，后者则恰好与前者相反。 层次聚类的结果可以用一个二分树表示，树中的每个节点都是一个聚类，下层的聚 类是上层聚类的嵌套，每一层节点构成一组划分。如图1 5 所示。 基于后缀树的中文文本聚类算法研究 0s t e p _ l l ，二。l j 一d i v l s l v c 4s t e p3s t e p2s t e dls t e p os t e p 图1 5 聚合和分裂层次聚类 该方法的缺陷在于：它不能更正错误的决定。一旦一个步骤完成，就不能被撤 销。正是出于这个特点，使用时不用担心组合数目的不同选择，同时，其计算代偷 会较小。 有两种改进层次聚类的方法：一种是在每层划分中，仔细分析对象间的“联结”， 例如c u r e 和c h a m e l e o n 的做法：另一种是综合层次凝聚和迭代的重定位方法，首 先用自底向上的层次算法，然后用迭代的重定位来改进结果，例如b i r c h 方法。 ( 3 ) 基于密度的方法( d e n s i “一b a s e dm e t h o d ) 这种方法将具有足够高密度的区域划分为簇。主要思想是：只要临近区域的密 度( 数据元素的数目) 超过某个阀值，就继续聚类。 该方法可用来过滤“噪声”孤立点数据，发现任意形状的簇，如：d b s c a n o p t i c s 等。d b s c a n 是一个有代表性的基于密度的方法，它根据一个密度闽值来 控制簇的增长：o p t i c s 为自动的和交互的聚类分析计算一个聚类顺序。 ( 4 ) 基于网格的方法( g r i d b a s e dm e t h o d ) 这种方法把数据元素空间量化为有限数目的单元，形成了一个网格结构，所有 的聚类操作都在这个网格结构上进行。 该方法的主要优点是：处理速度很快，其处理时问独立于数据对象的数目只 与量化空间中每一维的单元数目有关。缺点是：由于将对象空间作了很大简化，因 此聚类质量和精确性较差，s t i n g 是一个典型例子。 c l i q u e 和w a v e c l u s t e r 这两种算法既是基于网格的，又是基于密度的。 ( 5 ) 基于模型的方法( m o d e l b a s e dm e t h o d ) 该方法为每个聚簇假定了一个模型，寻找数据对给定模型的最佳拟合。主要有 基于后缀树的中文文本聚类算法研究 两类：统计学方法和神经网络方法。传统的统计方法中的聚类分析是一种基于全局 比较的聚类，它需要考察所有的个体才能决定聚类的划分；神经网络方法将每个簇 描述为一个标本，标本作为聚类的“原型”，不一定对应一个特定的数据实例或对象。 根据某些距离度量，新的对象可以被分配给标本与其最相似的簇。被分配给一个簇 的对象的属性可以根据该簇的标本的属性来预测。s o m 是一种利用了人工神经网络 技术的聚类方法。 1 3 1 2 研究不同类型领域的聚类 不同领域的聚类，比如：文本聚类、w e be t 志信息的聚类、声音和特征识别、 生物数据的聚类、d n a 数据的聚类等。各个领域中得到的数据是千差万别的，如数 据的形态上有数字、符号、图像、图形、声音等：数据组织方式也各不相同，可以 是有结构、半结构和非结构的，因此不能将一般的聚类方法直接应用到这些领域。 通常的方法是将数据作适当的处理或转换，然后再聚类，但是有时需要进行专门的 研究，这一领域的研究是重点也是难点。关于在文本聚类方面的具体算法将在第二 章中进行更为详尽的阐述。 目前第一类研究已经取得了大量的研究成果，这些研究基本上是基于结构化数 据的，比如数据库，然而却很少有工作研究非结构化数据。第二类研究的成果还相 对较少，目前随着多媒体技术和互联网的迅速发展，开展这一领域的研究已成为新 的热点，有大量的研究工作需要开展，如：并行聚类算法、复杂数据的聚类算法、 算法聚类结构的可视化、聚类结果质量的提高等。本文对文本数据挖掘进行研究。 1 3 2 本文研究的意义 。 文本聚类在信息检索等许多方面有很广泛的应用。最初，人们研究利用文本聚 类来提高信息检索系统的准确率或召回率【6j i ”，同时文本聚类也是发现关联文档的 有效手段【8 1 。近年来，文本聚类有了更广泛的应用，h e a r s t 等人的研究已经证明了 “聚类假设” 9 1 ，即与用户查询相关的文档通常会聚类的比较靠近，而远离与用户 查询不相关的文档。因此，利用文本聚类可以改善搜索引擎，将搜索结果自动聚类， 提供给用户优质的服务【l 。著名的网站y a h o o ! 就是采用类似的技术来自动生成文 档的分类。a g g a r w a l 等人于1 9 9 9 年提出了一种基于聚类的分类方法：在已有的类 似于y a h o o ! 的文档分类树中发现原有的聚类，然后利用这些聚类形成一个有效的 文档分类器【i “。 基于后缀树的中文文本聚类算法研究 在前面的小节中介绍了文本挖掘的一些应用的领域，如：文档管理、信息检索 等，而作为文本挖掘基础工作的文本聚类在人们面对大量文档时，可以给出比较清 晰的层次架构，极大的方便了文档的管理工作。同时，+ 在信息检索方面也可以将检 索目标限定到一个相对小而精的范围，极大提高检索的准确率。 国外对英文文本聚类已经进行了大量的研究，与国外相比，国内对中文文本聚 类的研究和应用起步较晚，目前国内仅有少数单位从事中文文本聚类算法的研究及 其应用。中国科学院计算技术研究所智能信息处理开放重点实验室在国内率先展开 了对中文文本聚类研究。宫秀军和史忠植2 0 0 2 年提出了基于b a y e s 潜在语义模型的 半监督文本挖掘2 j ；吴斌等人提出了一种基于群体智能的w e b 文档聚类算法。另外 陈宁等人提出了基于模糊概念图的文档聚类算法；西安交通大学的宋擒豹和沈钧毅 提出了基于关联规则的w e b 文档聚类算法【1 3 】；合肥工业大学的陈福集、杨善林提出 了- 二种基于s o m 的中文w e b 文档层次聚类方法【1 4 】等等。 1 3 3 本文的研究工作 本文在这一背景下，对数据挖掘尤其是文本聚类相关理论与技术，进行了一系 列的研究，主要有以下几个方面： ( 1 ) 对数据挖掘中的聚类分析研究的进展进行了论述，尤其是在文本聚类领域 进行了深入的研究。 ( 2 ) 针对中文文本组成上的特点，研究了中文文本聚类的模型，包括：文本表 示，特征降维，聚类算法的选取，结果评估等。通过机器分词和手动分词 两种方法对待聚类的中文文本进行分词处理，对比结果上的差异，咀此可 以说明从自然语言到计算机这个文本表示过程的重要性；同时也可以浇明， 。，从平均的查准率来看，虽然分词的方式不同，但结果是相近的，从而验证 了北邮智能中心的观点，即采用何种分词对文本的分类和聚类是没有影响 的【1 5 】。 ( 3 ) 研究了经典聚类算法k 平均算法及其在中文，文本聚类中的应用。在这个过 程中考虑到k 平均算法是通用的聚类算法，要将其应用到特定的中文文本 聚类领域，做了如下的调整：在文本的选取和清洗方面考虑了中文文本需 要分词的特点，中文文本的表示方面，大量文本的特征降维等方面的特殊 要求。这样做目的主要是为了跟后面提出的基于s t c i m l 的中文文本聚类算 法7j 进行对比，来分析两者的特点及差异。 基于后缀树的中文文本聚类算法研究 ( 4 ) 对后缀树这种数据结构应用到中文文本聚类这一特定领域上的可行性情况 进行了深入的分析和研究。后缀树是一种把文本看作是短语串而不是简单 的词的集合，这样可以充分使用词语之间的关联信息，达到更佳的聚类结 果。这就是本文研究的依据。使用这个算法时，前期对中文文本的表示的 处理过程，即文本表示，与k 一平均算法相同；后期的处理根据后缀树聚类 的情况结合中文文本的特点进行了调整。 ( 5 ) 对上述两个算法，设计和实现了一个中文文本聚类系统，系统结构如图4 一l 所示，可以进行k 。平均和s t c 聚类。 ( 6 ) 最后，通过选取复旦大学计算机信息与技术系国际数据库中心自然语言处 理小组给出的已分类好的部分中文文本，通过几组实验集，对该系统的两 个算法进行试验和比较，得出- 了一些有用的结果，并从理论上作了逊一步 的说明和论证。同时，对试验中出现的问题进行了探讨，并提出了进一步 研究的方向。 1 4 j 、结 本章首先介绍了数据挖掘的涵义：常用方法和技术等方面的相关知识，接着介 绍了文本挖掘的相关知识，继而又介绍了本文的研究方向和意义，包括数掘挖掘中 聚类分析研究的现状，本文选题的意义及所作的研究工作等。 基于后缀树的中文文本聚类算法研究 第2 章文本聚类技术研究 文本聚类是文本挖掘( t e x tm i n i n g ) 的重要手段和方法，也是数据挖掘的一个重 要分支。文本聚类是一种无指导的文档分类，它把一个文本集分成若干称为簇 ( c l u s t e r ) 的子集，每个簇的文本之间具有较大的相似性，而簇间的文本具有较小的 相似性。文本聚类就是应用数据挖掘、机器学习、神经网络等技术，对文本集进行 自动分类的过程。 传统的文本聚类算法采用基于词集的向量空间模型( v s m ) 1 9 1 ，在分词的基础 上统计文本的词项权值，建立特征向量，然后采用基于概率或者基于距离的方法对 文本集进行聚类。 2l 文本聚类的过程 第一章介绍了文本挖掘的过程，在此对文本聚类进行更深入的研究。文本聚娄 不同于一般的聚类，一般的聚类通常面对的是结构化数据，采用的大多是非常明确的 定量方法，其过程包括数据取样、特征降维、模型选择、问题归纳和知识发现，丽 文本聚类由于处理的是非结构化的文本，因此必须利用文本处理技术。文本聚类的 一般过程大致有如下步骤： 2 1 1 文本表示 首先必须把文本表示成为计算机能够处理的并且可体现文本本质特征的形式。 文本与数据库中的结果数据不同，它或者具有有限的结构，或者根本就没有结构。 。文档的内容是人类所使用的自然语言，计算机并不具有人类的特有功能，因此很难 处理其语义。我们需要对文本进行预处理，抽取代表其特征的元数据，这些特征可 以用结构化的形式保存，作为文档的中间表示形式。 计算机如何完成二者之间的对应，具体的内容将在第三章进行详细的介绍。 2 1 2 特征降维 当使用v s m 表示文档时，人们发现，文档向量具有惊人的维数 集的缩减成为文本数据挖掘中必不可少的一步。 在文本聚类中，有几种常用的技术用来减少高维特征向量的维数 这使得特征 这些技术利 基于后缀树的中文文本聚娄算法研究 用多个词之间的依赖关系来合并这些词，达到降维的目的。但是这些技术往往需要 大量的计算，时间复杂度一般为o ( 砌2 ) ( k 为提取出的特征数，m 为原始特征数) 。 常用的方法有：p c a 20 1 ，它的特点是需要很大的内存空间，计算量也很大；l s a ( 也称l s i ) 1 2 1 1 方法是一种广泛用于信息检索领域的降维方法，它在本质上与p c a 相似，实验显示：当作用于范围广泛的文档集上时，l s a 能够显著提高检索性能。 21 3 文本聚类算法的选取 文本聚类算法在上- 4 , 节已经作了详细的介绍。因为具体的一种算法并不是在 所有的情况下都适用，在此过程中我们所做的工作就是根据特定的应用领域，选取 适合该应用的算法，这是一个不断循环的过程，通过结果的反馈调节选取的算法， 最终达到综合性能的最优，这是整个文本聚类过程的关键所在。 对于层次聚类算法，其特点是能够生成层次化的嵌套簇，准确度高，但是在每 次合并时，需要全局的比较簇间的相似度，并选择出最佳的两个簇，因此速度较慢， 不适合大量文档的集合，并且不能产生相交簇。这样对于聚类速度有较高的要求、 待聚类数据量较大等应用领域则不适宜采用这种方法。 对于平面划分法来酷其特点是聚类速度较快，比较适合对w e b 文档集聚类，也 适合联机聚类，但也有缺点，如：k 一平均算法要事先确定k 的取值，且初始簇选敬 的好坏对聚类结果有较大的影响，只有当选取的簇是关于使用的相似度近似于球形 时，它的效果才是最优的。但实际情况中文档很可能不是落在球形簇内。 2 1 4 评价聚类结果的质量 、若聚类结果满足一定的要求，则存储聚类知识模式，否则返回到以前的某个环 节分析改进后，再进行新一轮的聚类工作。那么究竞依据怎样的标准呢? 一般况来， 有两种方法来评价聚类结果的好坏：一种方法是不参照外部知识，直接比较结果簇 之间的相似度或分离度；另一种是对已知类别的文档集聚类，并比较聚类结果与已 知类之间的差异，查准率和查全率是其中用的比较广泛的两种方法f ”l 。 查准率p r 表征聚类的f 确性，查全率r e 表征聚类的完整性，定义如公式2 1 ： t p 7 1 p p l2 高，r 。，2 焘f n ， ( 2 _ 1 ) 。t p ? + f p j 。?tp+j。 其中f p i 是错分到簇c 的属于其他簇的文档数，t p i 是正确分到簇c i 中的文档 基于后缀树的中文文本聚类算法研究 数，f n i 是属于簇c i 而错分到其他簇的文档数。 本文使用查准率来衡量聚类质量。 除此以外，还有冗余度和放射性，m u s ( m e s s a g eu n d e r s t a n d i n gc o n f e r e n c e ) 会议就使用冗余度这个标准，它表示信息抽取中冗余的程度【2 4 】；在文本摘要和机器 翻译中有种流行的评估方法：双目失明测试【2 5 1 。它先用机器生成一组输出结果， 再混合人类专家用的相同形式的输出结果，这种混合后的输出集再交给其他的一些 人类专家，让他们给予其准确性上的评估。 2 2 文本聚类的主要算法 经过多年的发展，聚类分析领域存在了大量的聚类算法，算法的选取要取决于 数据的类型、聚类的目的和应用领域，根据文本聚类的特点，比较成熟的文本聚类 算法可以分为以下几种类型： 2 2 i 层次凝聚法 层次凝聚法可以生成层次化的嵌套类 时，需要全局的比较所有簇之间的相似度 速度慢，不适合海量文本的聚类。 并且准确度较高，但在分析簇是否合并 并选择出最为相近的两个类，因此运行 对于给定的文本集合d = 细：，讲：以，层次聚类的具体过程如下f 2 6 1 ： ( 】) 将d 中的每个文档d j 看作一个具有单个成员的类c ，= 硒，这些类构成了d 的一个聚类c = 加o ，c ； ( 2 ) 计算c 中每对类b 圳之间的相似度s i m ( c ，c ； ( 3 ) 选取具有最大相似度的类对a r g m a x s i m ( c ，c ，) ，并将c ，和c j 合并为一个新 。 q e o 的类c k = c i uc j ，从而构成d 的一个新的聚类c = 扣扣：“一； ( 4 ) 重复( 2 ) ( 3 ) 步骤，直至c 中剩下一个类为止。 层次凝聚法在聚类过程中先从叶节点出发，构造出生成树，生成树包含了类的 层次信息以及所有类间和类内的相似度。 基于凝聚层次聚类的方法有s i n g l e l i n k 、c o m p l e t e 1 i n k 、a v e r a g e l i n k 等算法，这 些算法的最大区别就在于如何计算簇间相似度。s i n g l e l i n k 算法由s n e a t h 和s o k a t 于1 9 7 3 年提出【2 ”，其主要思想是两个分类之间的相似度等价于两个分类中最相似 的两个文本之间的相似。c o m p l e t e l i n k 算法把簇间相似度定义为两个簇中最不相关 基于后缀树的中文文出聚类算法研究 的两个文本之间的相似度。a v e r a g e l i n k 算法则计算两个簇中文本的平均相似度柬 作为簇问相似度。由于计算相似度需要考查簇中所有的对象，因此这些算法的时问 复杂度为o ( n 2l o g ) 。 1 9 9 9 年，k a r y p i s 等人提出了个利用动态模型的层次聚类算法c h a m e l e o n ( 变 色龙) ，在它的聚类过程中，如果两个簇间的互连性和近似度与簇内部对象i 、白j 的互 连性和近似度高度相关，则合并这两个簇。基于动态模型的合并过程有利于自然的 和同构的聚类的发现，而且只要定义了相似度函数就可应用于所有类型的数据。 在层次凝聚法文本聚类的应用方面，c u t t i n g 和k a r g e r 等人提出了一种基于聚 类的大规模文档分类浏览方法，结合了层次聚类的层次特性、高准确度和k 一平均算 法的高效的优点，实现了对海量文本的高效的可视化管理和浏览；k o l l e r 和s a h a m i 通过文本层次聚类算法自动生成w e b 文本的分类树。 2 22 平面划分法 平面划分法与层次聚类法的区别在于，它将文本集水平的分割为若干类，而1 ： 是生成层次化的嵌套类。 对于给定的文档集合d = 胁巩以，平面划分法的具体过程如下f 2 8 l ： ( 1 ) 确定要生成的类的数目k ； ( 2 ) 按照某种原则生成k 个聚类中心作为聚类的种子s = 一s 。，s , g ： ( 3 ) 对d 中的每个文档d r ，依次计算它与所有各个种子s ，的相似度s i m ( d i s j ) ： ( 4 ) 选取具有最大相似度的种子a r g m a x s i m ( c ，s ，) ，将西归入以s ，为聚类中心 t e ( 的类c j ，从而得到d 的一个聚类c = 彤c k 凡 ( 5 ) 重复执行步骤( 2 ) ( 3 ) ( 4 ) ，从而得