（系统工程专业论文）一种文本聚类原型系统的设计与实现.pdf

大连理工大学硕士学位论文 摘要 本文提出了一种文本聚类系统原型的设计与实现。该系统的设计是针对国家自然科 学基金“项目管理中项目关联分析与立项决策支持系统研究”的实际需求而产生的。在 自然科学基金的评审过程中，需要由专家对大量的立项建议书进行评审，这一工作是相 当繁重的，而文本聚类系统的应用，可以大大减小工作强度，提高工作效率，节约评审 时间。本文设计了文本聚类系统的原型框架，并在该体系框架下，详细地讨论了系统中 各个子系统的分析设计和实现。本文主要在以下方面开展工作： ( 1 ) 深入研究了聚类算法中的平面划分法，采用j a v a 语言编程实现了典型算法k 平 均值算法和k 中心点算法，用来对立项建议书进行聚类分析。 ( 2 ) 申请书中大量存在的同义词和没有类别特征词对聚类的精度影响较大，因此，在 系统中加入了同义词的合并和无特征词的去除，提高了聚类分析的准确率。 ( 3 ) 在聚类分析结束以后，对分析结果进行了标注，得到了类模型。然后利用类模型 实现对新文本的分类。 ( 4 ) 采用j a v a 、j s p 技术开发了b s 模式下用户操作子系统。该子系统采用了j s p 技 术，实现了人机交互，方便了用户使用，并且通过程序将分析结果画成图形，给出了直 观的表示。 关键词：聚类；文本聚类；k 平均值；k 中心点 一种文本聚类原型系统的设计与实现 d e s i g na n d r e a l i z a t i o no ft e x tc 1 u s t e r i n gp r o t o t ) ，p es y s t e m a b s t r a c t t 1 l i sp a p e rp r o v i d e s 也ed e s i g na 1 1 dr e a l i z a t i o no fat e x tc l u s t 吲n gp r o t o t y p es y s t e m t h e s y s t e n li sd e s i g n e dt om e e tt 1 1 ed e m a l l d so fa na c 舡a 1p r o j e c tw h i c hb e l o n g st on a t i o n a l n 栅a 1s c i e n c ef o u n d 撕o no fc h i n a ( n s f c ) n ee v 加撕o no fp r o j e c ta p p l i c a t i o n sn e e d s m a n ye x p e r t st oe v “u a t el o t so fa p p i i c a t i o l l sw h i c hi sav e r yh e 玎v ) rw o r k u s i n gt h et e x t c l u s t e r i n gs y s t e mc a nr e d u c e 也ew o r ki n t e n s i o n ，i 埘l p r o v ee m c i e n c ya n ds a v e 廿m e t h i s p a p e rd e s i g n st h es y s t e m 撕ca t c h i t e c t l l r eo ft e x tc l u s t e r i n gs y s t e m a n du n d e rt h i ss y s t e m a t i c a r c l l i t e c t i l r e ，i th a sd i s c u s s e dt l i ea n a l y s i s ，d e s i 弘a i l dr e a l i z a t i o no f e a c hs u b s y s t e mi nd e t 札 i n l em a j o rc o m p l e t e dw o r k sa r ea sf o i i o w s ： ( 1 ) l u c u b r a t e st 1 1 ep a r l i t i o l l i n gm e t l l o d si nc l u s t e r i n ga l g 鲥m m s ，i m p l e m e n i sc l a s s i c k m e a n sa l g o r i t a 1 1 dk - m e d o i d sa l g o r i t l l i nw h i c ha r eu s e dt oc l u s t e r i n gt h ep r o j e c t a p p l i c a 丘o n s ( 2 ) l o t so f 也e s a u r i l sa 1 1 dw o r d sm a td o e sn o th a v ec l a s sf e a t 【l r e sr e d u c et h ec i u s t e 】血g p r e c i s i o n ，s ot h es y s t e mp r o v j d e sm a n a g e m e n to f 也e s a 哪sa n dn o - f e a t l l r ew o r d s ，a i l d i i n p m v e sp r e c i s i o n ( 3 ) a r e rc l u s t e r i n ga n a l y s i s ，1 a b e lc l u s t e 血gr e s l l l t sc r e a t e sc l a s sm o d e l s n l e nc l a s s i 母 n e wt c x t su s i n gc l a s sm o d e l s ( 4 ) u s e ro p e r a t i o ns u b s y 5 t e mw h i c hi su n d e rb sm o d ei sd e v e l o p e db ya d o 硼n gj a v a a n dj s pt e c h n o l o g y t 1 i ss u b s y s t e mr e g a r d sj s pa sc o n t r 0 1t e c h n 0 1 0 9 ym l i c hi sc o n v e n i e mt o u s e ，a n dp r o v i d e sv i s u a l 缈p ho f t l 】er e s u l t s k e yw o r d s ：c l u s t e r i n g ；t e x tc l u s t e 血g ；k m e a n s ；k m e d o i d s 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均己在论文中做了明确的说明并表示了谢意。 作者签名：主! 塑銎日期： 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 曳允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容绱入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名： 导师签名 孑彩年查月丝日 大连理工大学硕士学位论文 1 引言 1 1 问题的提出 随着计算机的广泛应用和i n t e m e t 的普及，人们面对的信息量急剧增长。信息量的 增加给人们带来方便，但是同时也带来了一个信息过量的问题。数据的大量涌入，大大 增加了我们获取有用信息的难度。面对浩如烟海、纷繁芜杂的信息，人们越来越希望能 够在对已有的大量数据分析的基础上进行科学研究、商业决策或企业管理口】。 在现实世界中，文本是信息最重要的载体，事实上，研究表明信息有8 0 包含在文 本文档中【2 】。特别是在互联网上，文本数据广泛地存在于各种形式，如新闻报道、电子 图书、研究论文、数字图书馆、网页、电子邮件等等。面对大量无序的文本数据，为了 便于工作的展开，人们经常遇到的一个问题就是，如何对文本进行分类、比较，评估文 本的相关性和重要性，以及发现众多文本的模式与趋势。很自然的，人们将解决这一问 题的目光投向数据挖掘。 文本挖掘属于数据挖掘这一交叉学科的一个具体颁域，它的主要任务是分析文档数 据库的内容，发现文档数据集中概念、文档之间的相互关系和相互作用，抽取有效、新 颖、有用、可理解的、散布在文本文件中的有价值知识，并利用这些知识更好地组织信 息。文本挖掘处理的是非结构化的文本信息，而不是通常数据挖掘中采用的结构化数据 信息。文本挖掘的主要研究内容包括关联分析、文本分类、文本聚类等【3 1 。 要实现对大量文本的自动分类，可以采用文本分类和文本聚类两种方法。文本分类 是在分析文本内容的基础上将多篇文本分成一个或多个类别。它通常由两个阶段组成： 训练阶段和分类阶段1 4 j 。在训练阶段，从训练文本中学习分类知识，建立分类器类模型： 在分类阶段根据分类器将输入文本分到最可能的类别中。从这个过程可以看出，分类需 要事先存在的人工分类好的训练数据。 但是，在信息瞬息万变的今天，经常会出现新的数据很难用己有的分类体系来处理。 如果重新进行分类，就必须重新建立分类好的训练文档集，而获得大量带有类别标注的 样本的代价是很大的。这时使用聚类的方法就显得很重要。 聚类( c l u s t e r i n g ) 又称聚类分析( c l u s t e d n g a n a l y s i s ) ，是最重要的无教师学习的方法。 聚类是一个将数据集划分为若干类的过程，并使得同一个类内的数据对象具有较高的相 似性，而不相同类中的数据对象则具有较大的相异性。 聚类与分类不同在于，在分类问题中，已经事先知道对象的分类属性，分类的工作 就是根据训练样本将每一个对象分别属于哪一类标记出来，而聚类分析的输入数据集是 一种文本聚类原型系统的设计与实现 一组未标记的对象，也就是说此时输入的对象还没有被进行任何分类，聚类的目的是根 据一定的规则，合理地进行分组或聚类，并用显式或隐式的方法描述不同的类别【5 j 。由 于分析可以采用不同的算法，所以对于相同的数据集合可能有不同的划分。聚类是无指 导学习的方法，分类是有指导学习的方法，两者所采用的方法相差甚远，并且聚类的时 间复杂度要比分类大得多。 聚类是无教师的机器学习，不需要任何的训练数据。聚类是一种广泛应用于知识发 现与数据挖掘的分析手段，它按照事物的某些属性，将事物分成多个类或簇，使得在同 一类别中的事物相似度尽量大，不同类别间的事物相似度尽量小1 6 j 。聚类作为一种非监 督型的知识发现方法，不需要任何事先的训练数据，而仅仅按照相似度原则，将一组数 据划分为事先未知的分类状态，因而是一种有效的、得到广泛应用的模式识别与知识发 现的方法。 本文的研究内容，依托于国家自然科学基金的“项目管理中项目关联分析与立项决 策支持系统研究”项目的实际背景，提出了一种文本聚类系统的原型，实现了对立项建 议书的自动聚类，方便了评审工作的进行。 1 2 聚类的研究现状 目前，聚类分析的研究主要集中在两个方面：一方面是对聚类分析算法的研究，另 一方面是聚类分析的实际应用的研究。 在聚类分析算法的研究方面：聚类对于从大型数据库和数据仓库中发现数据分布和 存在的模式，具有极其重要的地位，如何利用并改进传统的聚类算法以便在大型数据库 和数据仓库中发现有用的信息，越来越受到人们的重视。传统的聚类大多局限于统计学 和机器学习领域而没有充分考虑到大数据量，从而导致原有算法失效或不能直接用于数 据挖掘过程中。为了使聚类算法能处理大数据集，人们做了很多努力，例如在c l a r a n s 算法中仔细设计搜索方法( 采用随机搜索) ，在d b s c a n 算法中组织索引，b i r c h 算法 中组织数据结构。上述算法能够处理大数据量的数据，但是只能处理数值型属性，而不 能处理符号属性。k p r o t o t y p e 算法对传统k - m e a n s 算法进行了改进，不但可以处理数 值属性，也可以处理符号属性喁。“。另外，d f i s h e r 等人又提出了概念聚类挖掘方法， 我国的学者也对符号属性数据的聚类进行了广泛的研究，聚类算法得到了广泛而深入的 研究。 在聚类分析实际应用的研究方面：聚类分析可以作为独立的数据挖掘工具，来获得 数据分布的知识，也可以作为其它数据挖掘算法的预处理步骤。它在许多领域有着重要 的应用：在商务上，聚类分析能够帮助市场分析人员从客户基本库中发现不同的客户群， 大连理工大学硕士学位论文 并且用购买模式来刻画不同客户群的特征；在生物学上，聚类能用于推导植物与动物的 分类，对基因进行分类，获得种群中固有结构的认识：聚类可从地球观测数据库中确定 相似地区；对汽车保险单持有者进行分类；根据房子的类型、价值和地理位置对一个城 市中房子迸行分组；此外，聚类分析也能用于对无结构的w e b 文本数据库中的文本进 行分类。 聚类分析是数据挖掘的研究内容之一，它涉及到许多研究领域，包括数据挖掘、统 计学、生物学以及机器学习等。聚类是根据数据集中数据的不同特征，将其划分为不同 的簇，使得属于同一簇别的个体之间的距离尽可能的小，而不同簇的个体间的距离尽可 能的大。用少数的几个簇代表整个数据集会丢失数据集的一些细节信息，但这样简化了 数据集的表示。聚类分析是一种重要的人类行为。早在孩提时代，一个人就通过不断地 改进下意识中的聚类模式来学会如何区分动物和植物。目前聚类分析己应用于许多方 面，包括模式识别、数据压缩、图像处理、声音处理，以及市场分析等等【虬1 4 。通过聚 类，人们能够识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据属性之间 有趣的相互关系。 在数据挖掘应用中，需要根据应用所涉及的数据类型、聚类的目的以及具体应用要 求来选择合适的聚类算法，一些应用也需要将多个方法结合起来才能收到更好的实际应 用效果。常见的聚类方法有： 1 、划分的方法( p a n i t i o i l i n gm e t l l o d ) 给定一个包含 个对象的数据集，划分方法将数据集划分为后个子集( 划分) 。其 中每个子集均代表一个聚类( 七兰 ) 。也就是说将数据分为_ j 组，这些组满足以下要求： 1 ) 每组至少应包含一个对象； 2 ) 每个对象必须只能属于某一组。 给定要构建的划分的数目t 。划分方法首先创建个初始划分，然后通过反复迭代 的方法改变分组，使得每一次改进之后的分组方案都较前一次好。 一个好的划分衡量标准通常就是同一个组中的对象“相近”或彼此相关；而不同组 中的对象“较远”或彼此不相关。当然还有许多其它判断划分质量的衡量标准。通常算 法中会采用一个划分准则( 称为相似度函数) ，例如距离，以便在同一个簇中的对象是 “相似的”，在不同簇中的对象是“相异的”。 为获得基于划分聚类分析的全局最优结果就需要穷举所有可能的对象划分。为此大 多数应用采用一至二种常用启发方法：( a ) k m e a n s 算法，该算法中的每一个聚类均 用相应聚类中对象的均值来表示；( b ) k - m e d o i d s 算法，该算法中的每一个聚类均用相 应聚类中离聚类中心最近的对象来表示。这些启发聚类方法在分析中小规模数据集以发 种文本聚类原型系统的设计与实现 现圆形或球状聚类时工作得很好【”】。为了大规模的数据集进行聚类以及处理复杂形状的 类别，基于划分的方法需要进一步的扩展。 2 、层次的方法( h i e r a r c h i c a lm e t l l o d ) 层次的方法对给定数据对象集合进行层次的分解。根据层次的分解如何形成，层次 的方法可以分为凝聚的和分裂的。凝聚的方法，也称为自底向上的方法，一开始将没个 对象作为一个单独的一个组，然后相继地合并相近的对象或组，直到所有的组合并为一 个，或者达到一个终止条件。分裂的方法，也称为自顶向下的方法，一开始将所有的对 象置于一个簇中，在迭代的每一步中，一个簇分裂为更小的簇，直到最终每个对象在单 独的一个簇中，或者达到一个终止条件。将循环再定位与层次方法结合起来使用常常是 有效的，即首先通过利用自下而上层次方法，然后再利用循环再定位技术对结果进行调 整。 代表算法有：b i r c h 算法、c u r e 算法、c h a m e l e o n 算法等。 3 、基于密度的方法( d e n s 酊_ b a s e dm e m o d ) 绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发现球状的簇， 而难以发现任意形状的簇。随后提出了另一种聚类方法基于密度的方法。其主要思 想是：只要临近区域的密度( 对象或数据点的数目) 超过某个阈值就继续聚类。也就是 说，对给定类中的每个数据点，在一个给定范围的区域中至少包含某个数目的点。这样 的方法可以用来过滤“噪声”数据，发现任意形状的簇。 d b s c a n 是一个有代表性的基于密度的方法，它根据一个密度阀值来控制簇的增 长。o p t i c s 是另一个基于密度的方法，它为自动的和交互的聚类分析计算一个聚类顺 序。 4 、基于网格的方法( g r i d _ b a s e dm e t l l 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 ) ： 基于模型的方法为每个簇假定了一个模型，寻找数据对此模型的最佳拟合。一个基 于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类，它也可能基于 标准的统计数字自动决定聚类的数目，考虑“噪声”数据和孤立点，从而产生健壮的聚 类方法。 大连理工大学硕士学位论文 另外，根据数据集合中变量的类型可分为：基于统计的方法和基于概念的方法；根 据聚类的对象可分为：数值聚类和符号值聚类等。一些聚类算法集成了多种聚类方法的 思想，所以有时将某个给定的算法划分为属于某类聚类算法是很困难的。此外，某些应 用可能有特定的聚类标准，要求综合多个聚类技术。 1 3 文本聚类的研究现状 传统的聚类研究主要针对的是结构数据，如关系的、事务的、和数据仓库中的数据。 然而在现实世界中，可获取的大部分信息是存储在文本数据库中的，由来自各种数据源 ( 如新闻文章、研究论文、书籍、数字图书馆、电子邮件消息和、b 页面) 的大量文档组 成。由于电子形式的信息量飞速增长，使得文本数据库得到迅速的发展，大量的有用信 息淹没在文本数据的海洋之中。 此外，传统的信息检索技术己不能适应日益增加的大量文本数据处理的需要。典型 的大量文档中只有很少一部分与某一个体或用户相关。而不清楚文档中的内容，就很难 形成有效的查询，从数据中分析和提取有用信息。用户需要有关的工具完成不同文档的 比较，以及文档重要性和相关性的排列，或找出多文档的模式或趋势。因此，文本挖掘 就成为数据挖掘中一个日益流行而重要的研究课题。 文本聚类是种有效的文本挖掘方法，能从大量文本数据中发现潜在的知识和规 律，它既是一个知识获取技术，也是一种文本处理过程1 16 。下面分几个方面来探讨一下 文本聚类研究的意义。 ( 1 1 文本的聚类处理是文本有效管理的基础 文本在h l t e n l e t 上是信息、资源的一个主要形式，面对这样一个信息海洋，人们往 往会陷入窘迫的境地：一方面收到太多的信息无从选择和消化，淹没在繁杂的信息中： 另一方面是信息迷失，人们难于找到自己真正所需的信息。因此，能够快速高效地获取 所需要的信息是每个人迫切要求，因而对大量的信息自动地提取其概念空间，提供给人 一个清晰的框架，帮助人们进行信息的检索和分类则显得将必不可少。围绕文本信息这 一资源开展的各种学术研究和业界应用非常活跃，如今年出现的各种i n t e m e t 搜索引擎、 数字图书馆、电子商务等，这些领域的研究者在进行信息检索和分类的研究上取得了令 人可喜的进展，但仍然存在着许多亟待解决的问题，即处理效果不能令人满意，在相当 一定的程度上，人为地干预成分占的比较大。需要将数据挖掘技术引入文本的检索和分 类领域。而文本聚类作为文本挖掘的基础工作将尤为显得重要。 f 2 ) 文本聚类是文本挖掘的自身需要 一种文本聚类原型系统的设计与实现 所谓的文本挖掘就是以文本作为数据的处理单元，从文本的无序性、多样性、广泛 性中找出可以利用的、有一定关系的、作为信息指导性的潜在模式的过程u ”。而在这个 过程中，必然要将纷繁冗杂的文本信息按照某种特定的方式有序地排列。其中也不乏有 一个体系结构存在，这个层次结构作为类别的合理展示必不可少。而且，利用计算机对 海量的文本聚类及类别标识，是文本挖掘自身的需要，为进一步进行其他途径的挖掘提 供了很好的利用效果。 ( 3 ) 文本聚类的有效标识一海量i n t e m e t 信息检索的有效手段 信息检索是指从大量的文档集合中找到与查询请求相关的、恰当数目的文档子集。 要使检索的结果准确而且精确，就需要对检索的对象进行准确分析，在进行抽象的过程 中起到界定范围的作用：而目前的网上信息检索却远不能达到这种效果，经常是搜索出成 千上万条纪录，远没有达到准而精的效果。因此要对网页做一个适当而全面的类归并， 这不但为使用者提供了方便，而且还有利于信息资源的合理存储。现在的网页大都是人 工的进行归类，面临浩瀚的信息海洋，这样下去必将耗费大量的人力资源。况且人不是 机器，长期从事单一而冗杂的事件，必将导致错误的出现。利用机器自动地从事这方面 任务已经成为迫切的需要。 文本聚类是基于“聚类假设”：相关文档之间的相似性比无关文档之间的相似性更 大。文本聚类是一种无指导的文本分类，它把一个文本集分成若干称为簇( c l u s t e r ) 的子 集，每个簇中的文本之问具有较大的相似性，而簇之间的文本具有较小的相似性。 国外对英文文本聚类已经进行了大量的研究，并已将文本聚类应用在文本挖掘和信 息检索领域，如：将文本聚类用来改善信息检索系统中的查准率和查全率。最近，文本 聚类用于浏览文档集以及重新组织查询引擎 1 ”。此外，文本聚类还可以用于提供对一个 大的文档集内容的概括、识别隐藏的共同点等。文本聚类应用的一个例子是对顾客的 e - m a i l 进行分析来找出不同用户群的购物特点，为商业决策提供支持。 以上的研究都是基于英文环境的。与国外相比，国内对中文文本聚类的研究和应用 起步较晚。目前国内少数单位正从事中文文本聚类算法的研究及其应用，如：中国科技 大学的姜宁等人，解放军理工大学的李家福等人和中国科学院计算所的h 东波等人。 中文文本聚类不同于一般的聚类，一般的聚类通常面对的是结构化数据( 如：数据 库中的数据) ，采用的方法大多是非常明确的定量方法，其过程包括数据取样、特征提 取、模型选择、问题归纳和知识发现。而中文文本聚类由于它处理的是非结构化的文本， 因此，必须利用文本处理技术。 文本聚类的一般过程可以用图1 1 表示： 大连理工大学硕士学位论文 图1 1 文本聚类 f i g 1 1t e x tc l u s t e r i n g 1 、文本特征的建立 首先必须把文本表示成为计算机能够处理的、可体现文本本质特征的形式。文档与 数据库中的结构数据不同，它或者具有有限的结构，或者根本就没有结构。即使具有一 些结构，也是着重于格式，而非文档内容，如：文档题目、作者等。文档的内容是人类 所使用的自然语言，计算机并不具有人类的特有功能，因此很难处理其语义。文本信息 源的这些特殊性使得现有的数据发现技术无法直接应用于其上。我们需要对文本进行预 处理，抽取代表其特征的元数据，这些特征可以用结构化的形式保存，作为文档的中间 表示形式。 文本特征指的是关于文本的元数据，分为描述性特征，例如文本的名称、日期、大 小、类型等；以及语义性特征，例如文本的作者、机构、标题、内容等。描述性特征易于 获得，而语义性特征则较难获得，尤其是文本正文的语义。文本正文是自然语言并且是 文本最重要的特征，因此必须找到一种能够被计算机所处理的表示方法。空间向量模型 ( v s m ) 是近年来应用最多且效果较好的方法之一。 2 、特征提取 当使用空间向量模型表示文档时，人们发现，文档特征向量具有惊人的维数，这使 得特征集的缩减成为文本数据挖掘中必不可少的一步。 目前在文本聚类中，有几种技术可以减少高维特征向量的维数。这些技术利用多个 词之间的依赖关系来合并这些词，达到降维的目的。但是这些技术大部分都需要大量的 计算，时间复杂度般为d ( 砌2 ) ( 后为提取出的特征数，m 为原始特征数) ，当文档集很 大时，需要的计算量非常大，并且通常需要大量的内存。下面简单介绍这些方法： p c a ( p r i n c i p a lc o m p o n e n ta n a l y s i s ) 方法是一种应用较广的降维技术 1 9 】。给定一个 ”m 阶文本一词矩阵，p c a 用一个研阶协方差矩阵的t 个主要的特征向量来降低词 空间维数，最终得到比m 小得多的个特征空间维数。这t 个主要的特征向量表示了特 征之问最大的差异，相当于摄初m 个特征的线性合并。p c a 的缺点是需要很大的内存 一种文本聚类原型系统的设计与实现 空间，计算量也很大。其中协方差矩阵需要d 沏2 ) 个一单位的内存，找出个主要的特 征向量的时间复杂度为0 ( 砌1 2 ) 。 对于大规模文档，词数r ，l 通常有上万个，那么时间和空间的需求变得不可接受。 l s i ( l a t e n ts e m a m i ci n d e x i n 曲方法是一种广泛用于信息检索领域的降维方法【”】，它 在本质上与p c a 相似。l s i 不是对协方差矩阵进行奇异值分解，而是对初始的门m 阶 文档一特征矩阵进行奇异值分解，然后选出这些奇异特征向量作为代表，从而降低维数。 因为不需要计算协方差矩阵，l s i 在n 小于m 时，内存和计算量的需求都较p c a 小。 实验显示：当作用于范围广泛的文档集上时，l s i 能够显著提高检索性能。但是导致l s i 较好性能的机理仍然不清楚，这是现在一个活跃的研究领域。 c i ( c o n c 印ti n d e x i n 曲方法首先将文档聚类为七个簇，然后利用这些簇的中心向量将 高维向量降为 维。较之l s i ，c i 的计算量较少。 s o f m ( k o h o n e ns e l f - o r g a n i z i n g f e a t u r e m 印) 方法是基于神经网络的方法，其中的神 经网络保存了特征之间的大概关系，它能将高维的输入数据映射为低维的输出数据。 m d s ( m u r i d i m e l l s i o n a ls c a l i n 曲方法将高维的初始数据转换为低维的数据，同时尽 可能保持数据点间距离的等级顺序。 3 、文本聚类算法 文本聚类的方法可以分为两大类：层次凝聚法和平面划分法。 1 ) 层次凝聚法：一般层次凝聚法最终构造出一棵生成树，树的一个结点表示一个簇， 树根是包含了所有文本的簇，树叶是仅包含一篇文档的簇。每一个非叶结点是两个子结 点( 文档或簇1 合并而成或者是父结点分裂而来。存在许多方法确定两个簇的合井，如 s i n 百e 1 i n k ，g m u pa v e r a g e ，r o c k ，和c o m p l e t e l i n k 。层次凝聚法的特点是能够生成层 次化的嵌套簇，并且准确度高。但是，在每次合并时，需要全局地比较簇之间的相似度， 并选择出最佳的两个簇，因此速度较慢，不适合大量文档的集合，并且不能产生相交簇。 2 ) 平面划分法：与层次凝聚法不同，它不是生成层次化的嵌套簇，而是将文档集合 水平地分割为若干簇。这一类的方法有：k 平均值，k 中心点，a u t o c l a s s ， g r 印h p a n i t i o l l i n g b a s e d ，s i n 9 1 e p a s s 和s p e c 订a l - p a r t i t i o n i n g - b a s e d 等。平面划分法的特 点是聚类速度较快，比较适合对w e b 文档集聚类，也适合联机聚类；并且可以产生相交 簇。但也有缺点，k 平均算法的主要缺点是：必须事先确定k 的取值，且种子选取的好 坏对聚类结果有较大影响；只有当所需簇关于使用的相似度近似于球形时，它的效果才 是最优的，但实际情况中文档很可能不是落在球形簇内。s i n g l e p a s s 方法也有这种缺点， 另外它还依赖于处理文档的循序，而且容易产生大型集簇。 大连理工大学硕士学位论文 近年来各种研究显示：平面划分法比层次凝聚法更适合对大规模文档进行聚类，这 是因为平面划分法的计算量相对较小。如：层次凝聚法中的s i n 9 1 e l i i l k 和口o u p - a v e m g e 方法的时间复杂度为0 ( 2 ) ，c o m p l e t e l i n k 法的时间复杂度为0 ( n 3 ) ，”为文档数。而平 面划分法中的k 平均算法的时间复杂度为p ( 以女? ) ；s i n g l e p a s s 方法的时间复杂度为 o ( n 后) ，其中n 是文档数，_ j 是最终聚类数目，r 是迭代次数。 此外，也有将层次凝聚法和平面划分法相结合的方法。如s c a t t c r g a t l l e r 。 4 、评价聚类结果的质量 若聚类结果满足一定的要求，则存储聚类知识模式，否则返回到以前的某个环节分 析改进后，再进行新一轮的聚类工作。有两种方法来评价聚类结果的好坏。一种方法是 不参照外部知识，直接比较结果簇之间的相似度或分离度。另一种方法是对已知类别的 文档集聚类，并比较聚类结果与已知类之间的差异，查全率和查准率是其中用得比较广 泛的两种方法。 1 4 本文研究内容 随着互联网络的发展，人们所面对的信息量呈爆炸式增长，而信息的载体又以文本 为主，这些文本信息数据量大、内容繁杂而且处于不断变化之中。j 9 苴着信息资源的日益 丰富，如何充分有效地利用信息成为人们关注的焦点。文本聚类分析作为一种数据挖掘 的重要手段，成为中文文本挖掘中一个非常重要的研究课题。而对于本文的研究背景， 国家自然科学基金项目“立项建议书研究系统”来说，如何实现立项建议书的自动聚类， 是一个比较急迫的问题。针对这一问题，本文设计了一种文本聚类系统的原型。下面介 绍一下本文的组织。 全文共分六章，文章整体结构以及各章节内容如下： 第一章提出了课题的研究意义，并对国内外研究现状做了阐述。 第二章对文本聚类系统进行分析。 第三章文本聚类系统的设计。 第四章描述文本聚类系统的物理实现。 第五章给出了文本聚类系统的应用实例。 种文本聚类原型系统的设计与实现 2 文本聚类系统的分析 2 1 系统概述 文本聚类系统是应对大规模文本分类的需求而产生的。在立项建议书的分类过程 中，各个学科的申请书数以万计，如果仅仅依靠人工将申请书进行分门别类的划分，不 但任务繁重，而且可能会耽误评审工作的进行。 为了解决这一问题，我们提出了一种文本聚类系统的设计，用来对申请书进行聚类， 实现立项建议书的自动分类。 文本聚类系统并不是一成不变的，随着技术的进步和实际问题的需要，系统本身也 要改变以适应需求。因此，文本聚类系统是一个运动的、发展的系统。 系统的任何一个要素都可以看作是一个子系统，同样，任何一个系统也可以看作是 某一更大的系统的子系统。文本聚类系统可以单纯的用来实现文本的聚类，但是它也可 以作为一个大型文本挖掘系统的模块，来为其他模块提供服务。 2 2 系统的功能分析 2 2 1 系统目标 1 通过良好的人机交互界，提供直观、方便、简单的聚类分析。 2 为项目的其他模块提供服务。 3 根据学科领域的变化不断更新完善词表。 4 标注类模型并存储在数据库方便以后的使用。 5 利用标注后的类模型对新文本进行分类。 6 提供直观的结果显示方式，例如柱状图。 总之，方便、准确的实现文本的聚类分析是系统的目标。 2 2 2 系统内容 对大量的不同学科的申请书进行聚类是本系统的主要内容，同时还要能根据类别标 注得到的类模型对新文本进行合理的分类判断。具体的系统包括以下几个方面： 1 原始文本预处理。 2 无特征词处理。 3 同义词处理。 4 文本的聚类分析。 5 聚类模型的建立。 大连理工大学硕士学位论文 2 2 3 系统应达到的技术指标 1 易操作性。增加系统的可视化和可操作性，提高人机交互友好程度，方便非专业 人员使用。 2 直观性。从已有数据库中直接操作，以多种图表的方式直观地显示查询结果。 3 合理性。要具有合理的数据结构。要求这个数据结构具有包容性、开放性、可扩 展性和结构的稳定性，合理地存储文本信息和聚类模型信息。 4 灵活性。系统功能是项目需求的反映，项目的不断展开必然引起系统功能的变化， 因此要求系统在结构上保证功能具有灵活性、可扩展性和适应性，以满足日益增长的管 理需求。 2 3 系统的流程分析 系统的整体流程如图2 1 所示。 甲 j 文本建模i lf l 聚类算法i 甲 i 类别标注il 文本建模i 崮型短 聚类模块 新文本分类模块 图2 1 系统的整体流程 f 培2 1t h ep r o c e d l l r eo f t h es y s t e m 从图中可以看出，系统分为两个模块：聚类模块和新文本分类模块。 在聚类模块中，对原始文本进行文本预处理，建立文本模型，然后利用聚类算法进 行聚类分析，最后经过类别标注得到聚类模型。 一种文本聚类原型系统的设计与实现 在新文本处理模块中，首先对新文本进行文本建模，然后利用聚类分析得到的聚类 模型，对新文本进行判断，得到分析结果。 文本建模和聚类算法是系统流程的核心。下面分别对这两部分进行分析。 2 4 文本建模方法的分析 2 4 1 文本的表示 计算机并不具有人类的智能，人在阅读文章后，根据自身的理解能力可以产生对文 章内容的模糊认识，而计算机并不能轻易地“读懂”文章，从根本上说，它只认识0 和 l ，所以必须将文本转换为计算机可以识别的格式。根据“贝叶斯假设”，假定组成文 本的字或词在确定文本类别的作用上相互独立，这样，可以就使用文本中出现的字或词 的集合来代替文本，不言而喻，这将丢失大量关于文章内容的信息，但是这种假设可以 使文本的表示和处理形式化，并且可以在文本分类中取得较好的效果。目前，在信息处 理方向上，文本的表示主要采用向量空间模型v s m ( v e c t o rs p a c e d e l ) 。 在v s m 模型中，文本空间被看作是由一组正交词条向量所组成的向量空间【2 ”。每 个文本表示为其中个范化特征向量v ( d ) = ( t l ，w l ( d ) ；t i ，w i ( d ) ；t 。，w 。( d ) ) ， 其中t i 为词条项，w i ( d ) 为b 在文档d 中的权值。由于h 在文本中既可以重复出现又应该 有先后次序关系，分析起来有一定难度，为了简化分析，可以暂不考虑t ，在文本中的 先后次序并要求t i 互异( 即没有重复) 。这时可以把t l j ”，h ，t 。看成一个n 维的坐标系， 而w 。( d ) ，w 。( d ) ，w 。( d ) 为相应的坐标值，因此一个文本就表示为n 维空间的一个向 量，我们称v ( d ) = ( w l ( d ) ，w ，( d ) ，w 。( d ) ) 为文本d 的向量表示或向量空间模型。 2 4 2 分词处理与词频统计 自动分词是指按照特定规范，在中文文本中连续地能够代表语义单元的词或者n 元 词条间加入分隔符。我们知道，在英文的行文中，单词之间是以空格作为自然分界符的， 而中文只是字、句和段可以通过明显的分界符来简单划界，唯独词没有一个形式上的分 界符。而自动分词是中文信息处理的基本工作，在诸多重要领域如篇章理解、机器翻译、 文本检索、信息提取、文本校对、自动标引等领域都得到广泛的应用 2 ”。如何把文章切 分为词条，并从中提取特征词条构成特征向量已经成为文本处理的关键。 两种基本的中文分词方法： ( 1 ) 基于词库的分词方法 基于词库的分词方法是目前最常使用的、简单有效的方法，它是按照一定策略将待 分析的汉字串与一个“充分大的”机器词典中的词条进行匹配，若在词典中找到某个字 大连理工大学硕士学位论文 符串，则匹配成功( 识别出一个词) 。常用的基于词库的分词方法有最大匹配法、逆向最 大匹配法、逐词遍历法等。 此方法的优点是使用了我们所熟知的一般词法知识，对中文有一定了解的人很容易 判别其正确性。词库具有通用性，但有一个前提条件，就是该方法要求有个较全词库， 事实上，做到这一点很难。此外，该方法无法正确切分出词表中未及时收录的新词，不 具备自适应性是其一个弱势。实际使用的分词系统，都是把基于词典的分词方法作为一 种最初切分手段，还需要通过利用各种其它语言信息来进一步提高切分的准确率。 ( 2 ) 基于统计的分词方法 在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词，所以字与字 相邻共现的频率能够较好地反映成词的可信度。定义两个字的互现信息为： 郴删。g 嵩等 其中p ( x ，y ) 是汉字x 、y 的相邻共现概率，p ( x ) ，p ( y ) 分别是x 、y 在语料中出现 的概率。互现信息体现了汉字之间组合关系的紧密程度，当紧密程度高于某一个阀值时， 便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统计，不需 要切分词典，因而又q 无词典分词法或统计取词方法。但这种方法经常会抽出一些共现 频度高、但并不是词的常用字组，例如“之一、“我的、“有的”等，并且对常用 词的识别精度差，时空开销大。 下面介绍基于词库的最大匹配分词算法。其过程很简单，首先准备一个词库，顺序 扫描待分词的句子，将句中候选词按照从大到小的顺序依次跟词库中的词进行匹配，匹 配成功即作为一个词输出。在得到了所用的己分词的语料后我们还需采用的预处理步骤 为： ( 1 ) 统计语料中所有出现的词汇及其出现频率和出现次数 就是对所有语料进行一次扫描，扫描的程序并不复杂，只是汉字是两个字节的机器 内码表示的，并且每个字节的内码其值大于十六进制的a 0 ( o x a o ) 。注意这一点就可以正 确扫描到所有的词汇及其频率。 ( 2 ) 去除平凡词 高居统计频率榜首的是“在”、“了”、“和”、“的”等对文章意义贡献不大的 平凡词，英文中叫作停用词( s t o pw o r d s 如英文中的a ，a n ，t h e ，i n ，o n 等) ，一般在 搜索引擎中这些词也是被过滤掉的，所以在我们的实验中这些词也被过滤而不考虑。 ( 3 ) 去除出现频率较低的词 如大量的词其频率小于3 ，这些词一般对聚类的贡献也不大，因此也去除它。 一种文本聚类原型系统的设计与实现 2 4 3 文本特征的筛选 通过上面步骤得到的文档可能会有成千上万的特征留下，即文档特征向量仍然是一 个超高维稀疏向量- 2 4 1 。这种向量是不利于聚类的，其缺点如下： n 影响了聚类速度； 2 ) 其中的一些噪音特征会降低文档的聚类效果； 3 ) 无论使用何种相似度函数，任意两个文档特征向量之间的相似度都倾向于一个常 数，从而无法区分文档之间的差异，也就无法聚类。 因此，还需要对文档特征进行进一步地选择，以降低特征空间的维数。即在文档集 中，需从中选取一部分最具代表性的特征。特征提取的原则如下： 不保留在文档集中出现特别少的词，对于一个词i ，用d n 表示该词在文档集中的 出现率。其中甑表示文档集中包含该词的文档数，n 表示文档集中的文档数田j 。如果 该值过小，说明只有极少数文档包含该词，那么该词对于聚类的贡献就不会很大。 在确定了以向量空间模型作为文本表示的方式之后，就涉及到合理的选择特征项的 问题。项可以是文本中的各种语言单位，对中文来说有字、词、短语，甚至是句子或句 群等更高单位。项也可以是相应词语或者短语的语义概念类。因此，项的选择只能由处 理速度、精度、存储空间等方面的具体要求来决定。选出的项越具代表性，语言层次越 高，所包含的信息就越丰富但是分析的代价就越大，而且受分析精度的影响就越大。由 于词汇是文本最基本的表示项，在文本中的出现频度较高，呈现一定的统计规律，再考 虑到处理大规模真实文本所面l 瞄的困难，选择词或者短语作为特征项是比较合理的。 如果使用自动分词后得到的所有单词作为词条项，可能会造成向量维数过大而导致 计算复杂【2 ”，所以要对文本进行特征提取，抽取些词条来构成特征向量。一个有效的 特征词条集，必须具备以下三个特征： 1 ) 完全性：特征词条能够确实表示目标内容； 2 ) 区分性：根据特征向量，能将目标同其他文本相区分； 3 ) 精练性：特征向量的维数应该尽可能小。 用分词算法或词频统计方法得到的特征项来表示文本，向量维数非常巨大，这种未 经处理的文本矢量给后续处理工作带来巨大的计算开销，使整个处理过程的效率非常低 下。因此，我们必须对文本向量做进一步净化处理，在保证原文含义的基础上，找出对 文本特征类别最具代表性的文本特征，提取的特征也称为二次特征。有研究证明，在经 过特征压缩后的特征空间中进行文本聚类不但不会降低聚类性能，而且会有助于提高聚 类精度。一般说来特征选择分为