（计算机应用技术专业论文）基于相似度的文本聚类算法研究及应用(1).pdf

江苏大学硕士研究生学位论文 摘要 文本聚类是文本挖掘的一个重要分支，因其独特的知识发现功能而得到较 为深入的研究。文本聚类算法已经在文档自动整理、检索结果的组织和数字图 书馆服务等方面得到了广泛的应用。但是在应用中随着文本集的不断扩大，传 统的文本聚类算法遇到了一些难以克服的困难，算法忽略了文本中单词之间的 语义相关性，算法聚类结果不稳定等。论文主要针对以上问题对文本聚类进行 研究。 论文首先详细介绍了传统的文本聚类算法，并对其进行比较和分析。其次， 为了解决向量空间模型忽略单词之间的语义相关性的问题，提出了一种基于单 词相似度的文本聚类算法( t c w s ) ；针对传统k - m e a n s 算法聚类结果不稳定的 缺点，提出了一种基于文本平均相似度的k - m e a n s 算法( k a a s t ) 。最后，将研 究成果应用到公安情报系统中。本文的主要研究内容概括如下： ( 1 ) 介绍了常用文本聚类算法，并从伸缩性、多维性、处理高维数据的能力 等方面对常用文本聚类算法进行分析和比较。 ( 2 ) 提出一种基于单词相似度的文本聚类算法( t c w s ) 。该算法首先利用单词 相似度对单词进行聚类获得单词之间的语义相关性，然后利用产生的单词类作 为向量空间模型的项表示文本，降低了向量空间的维度，最后采用基于划分聚类 算法对文本聚类。实验表明t c w s 算法提高了聚类结果的正确性。 ( 3 ) 提出一种基于文本平均相似度的k - m e a n s 算法( k a a s t ) 。该算法首先构 造文本平均相似度集合，其次从集合中选取当前平均相似度最大的文本作为初 始聚类中心，同时删除集合中与其簇相关的文本，这样选取出的中心点不但具 有代表性且分散，最后利用选取的中心作为k - m e a n s 算法的初始聚类中心对文 本聚类。实验表明k a a s t 算法的稳定性有较大的提高。 ( 4 ) 在理论研究的基础上，将本文提出的算法应用到公安情报系统中，并 设计和实现了文本聚类予系统，提高了情报处理的效率和正确性。 关键词：文本聚类，单词相似度，k - m e a n s ，向量空间模型，公安情报 江苏大学硕士研究生学位论文 t e x tc l u s t e r i n gi sa l li m p o r t a n tb r a n c ho ft e x tm i n i n g ，w h i c hh a sg e tm o r e d e p t hr e s e a r c hb e c a u s eo f i t su n i q u ek n o w l e d g ed i s c o v e r yf u n c t i o n s t o d a y , t h e r ea r e l o t so fe f f i c i e n tt e x tc l u s t e r i n ga l g o r i t h m sw h i c hh a v eb e e nw i d e l yu s e di nt h e a u t o m a t i cd o c u m e n tf i n i s h i n g ，t h eo r g a n i z a t i o no fs e a r c hr e s u l t sa n dd i g j 【t a ll i b r a r y s e r v i c e s h o w e v e r , w i me x p a n s i o no fd o c u m e n ts e t s t r a d i t i o n a lt e x tc l u s t e r i n g a l g o r i t h me n c o u n t e r e dan u m b e ro fi n s u r m o u n t a b l ed i f f i c u l t i e s f o ri n s t a n c e ， a l g o r i t h mi g n o r e st h es e m a n t i cc o r r e l a t i o nb e t w e e nw o r d s ，t h ei n s t a b i l i t yo fr e s e t t h e s ep a p e r sm a i n l yf o rt h ea b o v ep r o b l e m sd os o m er e s e a r c ho nt e x tc l u s t e r i n g f i r s t ，w ei n t r o d u c et h et r a d i t i o n a lt e x tc l u s t e r i n ga l g o r i t h m s w ec o m p a r ea n d a n a l y z et h et r a d i t i o n a lt e x tc l u s t e r i n ga l g o r i t h m s s e c o n d l y , t os o l v et h ev e c t o rs p a c e m o d e li g n o r i n gt h es e m a n t i cc o r r e l a t i o nb e t w e e nw o r d s ，w ep r o p o s eat e x tc l u s t e r i n g a l g o r i t h m sb a s e do nw o r ds i m i l a r i t y ( t c w s ) d u et ot h et r a d i t i o n a lk - m e a n s a l g o r i t h m sh a v ea ns h o r t c o m i n go fc l u s t e r i n gr e s u l t si n s t a b i l i t y ，w ep r o p o s ea k - m e a n sa l g o r i t h m sb a s e do na v e r a g es i m i l a r i t yo ft e x t ( k a a s t ) f i n a l l y , r e s e a r c h r e s u l t sb ea p p l i e dt op u b l i cs e c u r i 哆i n f o r m a t i o ns y s t e m t h ew o r k si nt h i sa r t i c l ea s f o l l o w s ： ( 1 ) i n t r o d u c e d t ot h et r a d i t i o n a lt e x t c l u s t e r i n ga l g o r i t h m ，a n dt h e y w e r e c o m p a r e da n da n a l y z e df r o mt h es c a l a b i l i t y , m u l t i d i m e n s i o n a l ，d e a l i n gw i t hh i g h d i m e n s i o n a ld a t aa n ds oo n ( 2 ) w ep r o p o s eat e x tc l u s t e r i n gb a s eo nw o r d ss i m i l a r i t ya l g o r i t h m f i r s to fa l l ， t c w sa l g o r i t h mu s eo fw o r ds i m f l a d t yc l a s s i f i c a t i o no fw o r d s ，a c c e s st ow o r d s e m a n t i cr e l e v a n c eb e t w e e nw o r d s ，a n dt h e nm a k eu s eo ft h ew o r dc l a s s i f i c a t i o na sa v e c t o rs p a c em o d e lc a t e g o r yo fi t e m sw i t ht e x tt h a tr e d u c e dd i m e n s i o no fv e c t o r s p a c em o d e l ，f i n a l l y , u s e dp a r t i t i o n i n gc l u s t e r i n ga l g o r i t h m e x p e r i m e n t ss h o w e d t h a tt c w s a l g o r i t h mi m p r o v et h ea c c u r a c yo fc l u s t e r i n gr e s u l t s ( 3 ) w ep r o p o s eak - m e a n sb a s eo na v e r a g es i m i l a r i t yo ft e x ta l g o r i t h m f i m to f a l l ，s t r u c t u r a la v e r a g es i m i l a r i t yo ft e x tc o l l e c t i o n ，s e c o n d l y , s e l e c t e df r o mc o l l e c t i o n o ft h eg r e a t e s ta v e r a g es i m i l a r i t yo ft h et e x ta st h ei n i t i a lc l u s t e rc e n t e r , a tt h es a m e 江苏大学硕士研究生学位论文 t i m e ，n e e d st od e l e t et h et e x tw h i c hc l u s t e ra s s o c i a t e dw i t ht h ei n i t i a lc l u s t e rc e n t e r s e l e c t e di n i t i a lc l u s t e rc e n t e rn o to n l yo nb e h a l f o fa n ds c a t t e r e d f i n a l l y , u s e dt ot h e s e l e c t e dc e n t e ra st h ei n i t i a lc l u s t e rc e n t e r so fk - m e a n sa l g o r i t h m e x p e r i m e n t s s h o w e dt h a tk a a s t a l g o r i t h mi m p r o v eds t a b i l i t y ( a c c o r d i n gt oa b o v et h e o r yr e s e a r c h ，t h ea l g o r i t h m sp r e s e n t e di nt h i sa r t i c l e a r eu s e dt ot h ep u b l i cs e c u r i t yi n f o r m a t i o ns y s t e m ，a n dd e s i g na n di m p l e m e n t a t i o n o fat e x tc l u s t e r i n gs y s t e m ，w h i c hc a ni m p r o v ee f f i c i e n c ya n dc o r r e c t l y k e yw o r d s ：t e x tc l u s t e r i n g ，w o r ds i m i l a r i t y , k - m e a n s ，v e c t o rs p a c em o d e l ，p u b l i c s e c u r i t yi n f o r m a t i o n 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权江苏大学可以将本学位论文的全部内容或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 学位论文作者签名： 保密口，在年解密后适用本授权书。 不保密口。 謦腭】 指导教师签 签字日期：年月 日签字日期 年，月加 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已注明引用的内容以外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：絮陆午 日期：年月日 江苏大学硕士研究生学位论文 1 1 课题研究背景及意义 第一章绪论弟一早三百了匕 2 1 世纪是信息网络时代，随着科学技术的突飞猛进和社会信息化的快速发 展，以信息技术为主要标志的高新技术革命已经引起了社会各个领域的深刻变 革，信息化的历史潮流对公安机关传统的警务运作方式提出了前所未有的挑战。 2 0 0 6 年1 月1 7 日，中国互联网络信息中心( c n n i c ) 发布“第十七次中国互联 网络发展状况报告 。我国上网用户总数达到1 1 1 亿人，互联网迅猛发展，已 经成为社会生活不可分割的一部分。每天都有数以亿计的网民在w e b 上浏览、 发布信息，网络已经成为信息时代最为重要的信息集散地。网络在给我们的生 活带来巨大变化并加速全球信息革命进程的同时也存在黑暗的一面。各种违法 信息在网络上泛滥，网络犯罪层出不穷，可以说网络已经成为一种新型的犯罪 工具、犯罪场所和犯罪对象。对于公安机关情报部门而言，研究如何通过互联 网进行公安情报信息获取，依靠情报信息带动现代化，使各项警务工作围绕收 集、运用和分析情报信息而展开，已经成为当务之急。数据挖掘技术的兴起， 为公安情报部门开展工作提供了高效的工具与手段。 数据挖掘( d a mm i n i n g ) 简称d m ，是近年来随着数据库和人工智能发展起 来的一门新兴的数据库技术。它是众多学科诸如人工智能、机器学习、模式识 别、统计学、数据库和知识库、数据可视化等相互交叉的学科，把数据的应用 从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持【】。从商业角 度出发，数据挖掘可以描述为：按企业既定业务目标，对大量的企业数据进行 探索和分析，揭示隐藏的、未知的或验证已知的规律性，并做进一步将其规模 化的先进有效的方法【4 】。其处理对象是大量的日常业务数据，目的是从大量的、 不完全的、有噪声的、模糊的、随机的原始数据中提取隐含在其中的、事先未 知的、但又是潜在有用的信息和知识。 聚类分析是数据挖掘的一个重要部分。聚类( c l u s t e f i n g ) 就是将物理或抽象 的集合分组成为由相似的对象组成的多个类的过程，使得每一个类内的数据尽 可能相似而不同组内的数据尽可能不刚扪。 江苏大学硕士研究生学位论文 文本聚类在信息检索等许多方面有很广泛的应用。最初，人们研究利用文 本聚类来提高信息检索系统的准确率或召回率，同时文本聚类也是发现关联文 档的有效手段。近年来，文本聚类有了更广泛的应用，h e a r s t 等人的研究已经 证明了“聚类假设”，即与用户查询相关的文档通常会聚集得比较靠近，而远离 与用户查询不相关的文档。因此，利用文本聚类可以改善搜索引擎，将搜索结 果自动聚类，提供给用户优质的服务。著名的网站y a h o o ! 就是采用类似的技术 来自动生成文档的分类。a g g a r w a l 等人于1 9 9 9 年提出了一种基于聚类的分类 方法在己有的类似于y a h o o ! 的文档分类树中发现原有的聚类，然后利用这些聚 类形成一个有效的文档分类器。 1 2 国内外研究现状 国外对文本聚类的研究比较早也比较深入，许多技术已经进入实用化阶段， 在对搜索引擎返回的结果进行聚类【6 】、对用户感性趣的文档、数字图书管服务 等方面取得了广泛的应用。一些研究机构的研究成果已经在商业领域得到了很 好应用，如i b m 丌发的t e x t m i n e r ，m e g a p u t e r 公司的t e x t a n a l y s t ，x t r a m i n d 公司的x m m i n d s e t 等。其中m 开发的t e x t m i n e r 主要功能包括特征抽取、 文档聚集、文档分类和检索。m e g a p u t e r 公司的t e x t a n a l y s t 是一个智能文本挖 掘和语义信息搜索系统，它采用了独特的神经元网络技术，实现了对自然语言 文本的机构化处理，可以用来创建知识库、搜索语义信息和自动抽取文本。 x t r a m i n d 公司研发的大型模块集x m m i n d s e t 集成了多项核心智能技术，其中 就包括了文本聚类的功能模块( x l v l c l u s t e r i n g ) 。它在模块精度( 查准查全) 、时问 效率、广义化、鲁棒性、动态移植性等方面都表现卓越。 与国外相比，国内文本聚类的研究起步比较晚。国内对文本聚类技术的研 究机构主要集中在高校和科研究所，如中国科学院计算技术研究所智能信息处 理开放实验室、上海交通大学电脑应用研究所、哈尔滨工业大学信息检索研究 室及清华大学等。中国科学院计算技术研究所智能信息处理丌放实验室研制的 多策略数据挖掘平台，支持特征抽取、分类、聚类、预测、关联规则发现和统 计分析等数据挖掘功能。哈尔滨工业大学信息检索研究室也开发出了中文多文 档自动文摘系统和中文文本聚类系统。除科研院外还有一些公司致力于这个领 2 江苏大学硕士研究生学位论文 域的研发，如北京拓尔思( t b s ) 信息技术有限公司等。北京拓尔思( t b s ) 信息 技术有限公司研发的t r s 中文知识管理工具包为中文文本应用提供了开放的开 发工具箱，它集成了t r s 公司最新推出的多项中文处理技术，其中包括了文本 聚类。 文本聚类算法的研究早在2 0 世纪6 0 年代就开始了，但是受到当时各方面 条件的限制并没有太大的发展，直到2 0 世纪9 0 年代j 弓i 起了广泛的关注，并 且取得了非常大的突破，包括k - m e a n s 、c i a r a n s 、u p g m a 等在内的一批聚 类算法被陆续提出。2 0 0 0 年后，随着i n t e m e t 的迅速发展和数字图书馆的广泛 应用，文本集的规模复杂性随之增大，进而提出了许多新的文本聚类算法，例 如：f 】d 7 】、h d f a 8 1 、f c a 9 等。大体上，文本聚类算法可分为基于划分聚类 算法、基于层次聚类算法、基于密度聚类算法、基于网格的聚类算法和基于模 型的聚类算法。 目前，应用最多的文本聚类算法是k - m e a n s 和层次聚类算法。其中，k - m e a n s 算法是实践中最为常用的算法，在处理大数据量方面有绝对优势。由于k - m e a n s 算法只能处理数值类型数据，而在实际应用中我们遇到的数据既可能是数值型 的，也可能是类属型的，还有可能是混合属性特征。因此，z h u a n g 提出了 k - m o d e s l l 0 1 算法和k - p r o t o t y p e s 1 1 】算法，推广了k - m e a n s 方法，使之可以对类 属性和混合型属性的对象集进行聚类。上述两种改进算法属于硬聚类算法，2 0 0 1 年，c h e n 等人发表了模糊f u z z yk - p r o t o t y p e s 1 2 】算法。 1 3 研究内容及安排 论文的研究内容主要有以下几个方面： ( 1 ) 对文本聚类相关知识进行研究，并对现有的常用文本聚类算法进行分析 ， 和性能对比。 ( 2 ) 针对在文本预处理中用向量空间模型表示文本，存在数据维度过高和忽 略了单词之间的语义相关性的缺点，提出了一种基于单词相似度的文本聚类算 法，利用单词相似度对单词进行聚类获得单词间的语义相关性，然后利用产生 的单词类作为向量空间的项表示文本降低了向量空间的维度。 ( 3 ) 对k - m e a n s 算法详细的介绍，及存在的聚类个数k 需要被预先给定、算 3 江苏大学硕士研究生学位论文 法对随机选取初始中心点的依赖性等五个缺点进行分析、介绍关于随机选取初 始中心点的依赖性缺点及现有的改进方法，并提出一种基于文本平均相似度的 k - m e a n s 算法，该算法首先构造文本平均相似度集合进行排序( 升序) ，其次从 集合中选择值最大的文本作为中心点，并从集合中删除与其簇相关的文本，重 复上述直至得到k 个中心点，如果集合为空并且还没有选择k 个中心点，则把 删除的文本重新加入集合，继续选择中心点，最后，根据获得的k 个中心点作 为初始聚类中心执行k - m e a n s 算法。 ( 4 ) 最后将上述研究成果应用到公安情报系统，设计并实现公安情报系统中 的文本聚类子系统。 论文余下内容安排如下： 第二章对文本聚类分析的相关知识进行了概述。介绍了常用的文本聚类算 法，并且对它们进行了比较。 第三章对文本预处理过程进行研究，针对文本预处理过程中基于向量空间 模型的文本表示方法存在的缺点进行分析，并且提出了一种基于单词相似度的 文本聚类算法。 第四章对k - m e a n s 算法进行研究，并针对k - m e a n s 算法中随机选择初始聚 类中心点而引起的聚类结果不稳定的缺点，提出了一种基于文本平均相似度的 k - m e a n s 算法。 第五章介绍了文本聚类算法在公安情报系统中的应用，设计并实现了文本 聚类子系统。 第六章是对全文工作进行总结，并对下一步工作进行了展望。 4 江苏大学硕士研究生学位论文 第二章文本聚类算法及分析 在本章中，主要介绍了常用文本聚类算法、文本聚类效果评价指标和文本 挖掘相关知识，并从伸缩性、多维性、处理高维数据的能力等方面对常用文本 聚类算法进行分析和比较。 2 1 文本挖掘相关知识 2 1 1 文本挖掘的定义 文本挖掘是数据挖掘的一个研究分支，用于基于文本信息的知识发现【1 3 】。 文本挖掘和文本数据库中的知识发现被认为具有相同含义的两个词，最早由 r o n e nf e l d m a n 等人提出，其含义为：文本挖掘即文本数据库中的知识发现，是 从大量文本的集合或语料中发现隐含的、令人感兴趣的、有潜在使用价值的模 式和知识。 文本挖掘是利用智能算法，如神经网络、基于案例的推理、可能性推理等 并结合文字处理技术，分析大量的非结构化文本源( 如文档、电子表格、客户电 子邮件、问题查询、网页等) ，抽取或标记关键字概念，文字间的关系，并按照 内容对文档进行分类，获取有用的知识和信息。文本挖掘的早期研究是信息检 索，包括了基于关键字检索和全文检索。数据挖掘是揭示存储在数据库中的结 构化数据的数值属性之间的关系，而文本挖掘则是分析和发现大量非结构化文 本中的关系。文本挖掘研究的关键在于文本内容的量化表征。 从文本挖掘的定义可以看出，文本挖掘就是从文本或文本集合中提取有用 知识的过程，而知识的表达方式是多种多样的。例如，可以是概念、规则、规 律模式、约束等。 2 1 2 文本挖掘的处理过程 文本挖掘的处理过程分为三步：文本挖掘过程包括文本集合的预处理( 文本 数据的选择、清洗、分类、特征提取等) 、索引与存储、中间表示分析( 聚类、 5 江苏大学硕士研究生学位论文 趋势分析、关联规则发现等) 、后期处理( 知识的评价与取舍、知识的解释与知 识的可视化表达) 等步骤。文本数据挖掘的一般处理过程可以用图2 1 来概括描 述。首先选取待处理和分析的文本，对挖掘的文本进行分词处理，把文本切分 成特征词条，建立挖掘对象的特征表示。特征表示一般采用文档特征向量，但 是分词后的初始特征向量具有惊人的维数，因而特征向量的缩减处理成为文本 挖掘处理过程中一个必不可少的环节。在完成特征向量维数的缩减后，确定应 用范围，包括收集应用所涉及领域内的背景知识，理解应用要求并且确定应用 所要达到的目标，便可以利用机器学习的方法来提取面向特定应用的知识模式。 最后对获取的知识模型进行质量评价，若评价的结果满足一定的要求，则存储 该知识模式，否则返回到以前的某个环节分析改进后进行新一轮的挖掘工作。 2 1 3 文本挖掘的特点 图2 1 文本数据挖掘的处理过程 ( 1 ) 文本挖掘处理的是大规模文本集合，而不是一个或少量的自然语言文本。 ( 2 ) 文本数据的高维是文本最重要的特点，一般的数据挖掘、数据检索的方 法由于计算量过大而不具有可行性，有必要对现有的方法加以改变以适应高计 算量、高资源消耗的文本处理特点，也可以研究文本表示的新方法或有效的维 数约简方法。 ( 3 ) 文本挖掘抽取的知识足具有潜在价值的，是直接可用的，它或者是某个 特定用户感兴趣的，或者对于解答某个特定问题足有用的。 ( 4 ) 由于文本数据的特点，文本挖掘算法的复杂度必须在时问和空间上是多 项式的，并且具有很强的鲁棒性。 ( 5 ) 文本挖掘是个多学科交叉的研究课题，包括数据挖掘、机器学习、统计 学、自然语言信息、信息抽取、可视化技术、数据库技术等。 6 江苏大学硕士研究生学位论文 2 1 4 文本挖掘常用技术 ( 1 ) 人工神经网络：仿造生理神经网络结构的非线性预测模型，通过学习进 行模式识别。 ( 2 ) 决策树：代表着决策的树形结构，可以利用信息熵建立最小的分类树。 ( 3 ) 遗传算法：基于进化理论，并采用遗传结合、遗传变异、以及自然选择 等设计方法的优化技术。 ( 4 ) 近邻算法：将数据集合中每个记录进行分类的方法。 ( 5 ) 规则推导：从统计意义上对数据中的“如果一那么 规则进行寻找和推导。 采用上述技术的某些专门的分析工具已经发展了大约十年的历史，不过这些工 具所面对的数据量较小。而现在这些技术已经被直接集成到许多大型的工业标 准的数据仓库和联机分析系统中去了。 2 1 5 文本挖掘中面临的课题 文本挖掘目前面临的问题包含挖掘算法的效率和可扩展性、遗漏及噪声数 据的处理、私有数据的保护与数据安全性。 文本挖掘中的许多问题并不是在该领域内首先提出的，因此，文本挖掘与 许多领域都有密不可分的关系，其中关系最密切的包括：数据挖掘，统计学， 机器学习，模式识别，神经网络，可视化，自然语言处理等。然而，许多其它 领域提出的算法主要针对结构化数据，并且现在文本挖掘要处理的文本集合可 能非常大，因此要求处理速度快，随着i n t e m e t 的发展，出现了大量的半结构化 h t m l 文档，文本挖掘面临许多新的研究课题： ( 1 ) 文本表示 文本挖掘处理的是自然语言表示的文本，是无结构或半结构化数据，缺乏 计算机可理解的语义，在进行文本挖掘之前，需要对文本进行预处理，对文本 进行特征提取，从而把文本表示为计算机可读的一种中间形式。目前，虽然自 然语言处理领域的研究已取得很大进展，但是还没有一种能够完全表示文本语 义的中间形式。对于不同挖掘目的，也需要使用不同复杂度的中问表示形式。 对于细粒度的、领域特定的知识发现任务，需要进行语义分析，以得到足够丰 富的表示，获取文本中对象或概念之间的关系。但是，由于语义分析计算量大， 7 江苏大学硕士研究生学位论文 如何使计算机更快地进行语言分析并且对于大文本集合具有可扩展性是一个挑 战性的问题。 ( 2 ) 降维问题 通常文档的特征向量会达到数1 0 力维的大小，高维的特征可能会大大增加 机器学习时间，因此降维是至关重要的。 ( 3 ) 跨语言问题 数据挖掘算法是以数据库中的结构化数据作为输入。而文本挖掘是以自然 语言文本作为输入，依赖于自然语言。由于自然语言的多样性，各种语言各有 其特点，在一种语言中有效的文本挖掘功能却很可能不适用于其他语言，待处 理的文本集合中可能存在多种语言写成的文本，因此，挖掘功能要考虑到能够 语言之间的语义转换，需要一个语言模型及系统的方法，这将构成跨语言文本 挖掘的重要部分。 ( 4 ) 大规模文本集合 i n t e r n e t 的迅孟发展、电子商务和数字图书馆的兴起和广泛应用、永久存储 设备价格的不断降低，使得各公司各机构存储的文本信息的规模越来越大，电 子文本库中文本数量达几十万、几百力- 之多。对于如此之大的文本集合进行处 理，必须有快速高效的文本挖掘算法。 ( 5 ) 模式的理解和可视化显示 在许多应用中，发现的模式的可理解性对于用户来说很重要的，提高可理 解性的解决方法通过包括以图形方式显示结果，提供相对少量的规则，或者生 成自然语言以及利用可视化技术等，提供更友好的用户界面。而目前的文本挖 掘系统主要针对有经验的专家，一般人很难使用。 ( 6 ) 算法运行中参数的设定和调节 很多算法运行时需要用户设定许多参数，有些参数是很难理解的，因而也 很难证确设定，如何让算法自动选择相对较好的参数值，而且在算法运行的过 程中自动地选择相对较好的参数值和自行调节参数的取值，是很多算法能否被 广泛使用的一个关键问题。 ( 7 ) 中文文本分词技术 在印欧语系语言中，词与词之间有空格作为固定的分隔符，因此容易进行 8 江苏大学硕士研究生学位论文 分词，而在中文中词与词之间没有分隔符，一个句子是由一串连续的汉字组成， 加之汉语中的词具有不同的长度，相同的字出现在许多不同的词中，还有许多 词是由单个字组成，这使得中文分词是一项很难的工作，需要快速有效的技术。 2 2 文本聚类算法 目前文献中存在的大量的聚类算法中，并不是所有的算法都适用于文本对 象，本章主要对常用的文本聚类算法进行介绍和评价。 2 2 1 基于划分的算法 基于划分的算法是文本聚类算法中应用得最为普遍的，其中以k - m e a n s 算 法和k - m o d e 算法为代表。该算法要求输入聚类簇的数目k ，以及目标函数f 。 首先选取k 个初始对象，然后根据其他对象与初始k 个对象的相似度，把他们 划分到与其最相近的对象所代表的簇中根据目标函数判断是否继续划分如果需 要，根据当前各个簇中的对象重新计算得到k 个初始对象进行划分，直到目标 函数f 收敛为止。其算法的基本思想如图2 2 所示。 图2 2 基于划分的聚类算法 划分算法一般要求所有的数据都装入内存，限制了它们在大规模数据集上 的应用它们还要求用户预先指定聚类的个数，但在大多数实际应用中，最终的 聚类个数是不知道的，另外划分算法只使用某一固定的原则来决定聚类，这就使 得当聚类的形状小规则或者大小差别很大时，聚类的效果不是很好。 2 2 2 基于层次的算法 层次聚类方法递归地对对象进行合并或者分裂，直到满足某一终止条件。 层次聚类的结果可以用一个谱系图( 图2 3 ) 表示，树中的每个结点都是一个簇， 下层的簇足上层簇的嵌套，每一层结点构成一组划分。根据谱系图生成的顺序， 9 江苏大学硕士研究生学位论文 可以把层次聚类方法分为凝聚的层次聚类( h i e r a r c h i c a la g g l o m e r a t i v ec l u s t e r i n g ， h a c ) 和分裂的层次聚类( h i e r a r c h i c a ld i v i s i v ec l u s t e r i n g ) 两种。凝聚的层次聚 类从单成员聚类开始，把它们逐渐合并成更大的聚类，在每一层中，相距最近 的两个聚类合并。相反，分裂的层次聚类从包含所有对象的一个聚类开始，把 它逐渐分解成更小的聚类。 在文本聚类中，最常见的是凝聚的层次聚类算法。使用该算法可以得到比 较好的聚类结果，而且该方法无需用户输入参数；但是层次聚类算法的时间复 杂度比较高，达到了o ( n 2 ) ，对于大规模的文本集合，有其不适用性，而且一 旦两个簇在凝聚和分裂后，这个过程将不能被撤销，簇之间也不能交换对象。 如果某一步没有很好的选择要凝聚或者分裂的簇，将会导致低质量的聚类结果。 o s t c pis t e p2 s t e p 3 s t e p4 s t c p 弋：3 一一 7 二) _ ，_ 、7 7，一l - ，一：= - 、7 。，一_ = _ 、一一一一一一一一一立k 一一7 一7 * # 4 s t e p 3 s t c p2 s t e p 1 s t e p o s t e p 图2 3 层次聚类及其谱系图 典型的层次聚类算法有p d d p 、p d s d p i l 4 1 、c u r e 1 5 】、h a m e l e o n 及 改进算法【1 6 1 等。 2 2 3 基于密度的算法 绝大多数划分算法是基于对象之间的距离进行聚类。这样的方法只能发现 球状的簇，而在发现任意形状的簇上遇到了困难。为此，提出了基于密度的另 一类聚类算法【1 7 1 ，其主要思想是只要邻近区域的密度对象或数据点的数目超过 某一个阀值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定 1 0 江苏大学硕士研究生学位论文 范围的区域中必须至少包含某个数目的点。这样的方法可以用来过滤“噪声 孤立点数据，发现任意形状的簇。代表算法有d b s c a n 算法、o p t i c s 算法、 d e n c l u e 算法等。 d b s c a n 算法是将密度足够大的那部分记录组成一类，并可以在带有“噪 声”的空间数据库中发现任意形状的聚类。它定义类为密度相连的点的最大集 合。在这个算法中使用了e p s 和m i n p t s 两个全局变量。d b s c a n 算法需要由 用户主观来选择参数，从而影响了最终的聚类结果。如果采用了空间索引， d b s c a n 的计算复杂度是o ( n * l o g n ) ，这罩甩是数据库中对象的数目。否则计 算复杂度为o ( n 2 l 。 对于参数的设置通常是依靠经验难以确定。尤其是对于真实的高维数据集 合而言。o p t i c s 算法克服了d b s c a n 算法的缺点，是一种顺序聚类的方法。 o p t i c s 没有显式地产生一个数据集合，它为自动和交互的聚类分析计算一个 类秩序。这个秩序代表了数据的基于密度的聚类结构。它包含的信息等同于从 一个宽广的参数设置范围所获得的基于密度的聚类。 d e n c l u e 是一个基于一组密度分布函数的聚类算法。该算法主要基于下 面的想法：( i ) 每个数据点的影响可以用一个数学函数来形式化的模拟，它描述 了一个数据点在邻域内的影响被称为影响函数；( m 数据空间的整体密度可以被 模型化为所有数据点影响函数的总和；( i i i ) 聚类可以通过确定密度吸引点来得 到，这里的密度吸引点是全局密度函数的局部最大。 2 2 4 基于网格的算法 基于网格的算法把对象空间量化为有限数目的单元，形成了一个网格结 构。所用的聚类操作都在这个网格结构即量化的空间上进行。这种算法的主要 优点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间 中的每一维的单元数目有关。代表算法有s t i n g l l 8 】算法、c l i q u e 算法、 姗c l u s t e r 算法。 s t i n g 算法是一种基于网格的多分辨率的聚类技术，它将空间区域划分成 为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单 元形成了一个层次结构，高层的每个单元被划分为多个低一层的单元，关于每 江苏大学硕士研究生学位论文 个网格单元属性的统计信息被事先计算和存储。这些统计参数对于查询处理是 有用的。 c u q u e 算法可以自动地发现最高维的子空间，高密度聚类存在于这些子 空间中。c u q u e 对元组的输入顺序不敏感，无需假设任何规范的数据分布。 它随输入数据的大小线性地扩展，当数据的维数增加时具有良好的可伸缩性。 但是，由于方法大大简化，聚类结果的精确性可能会降低。 w a v e c l u s t e r 算法是一种多分辨率的聚类算法，它首先通过在数据空 间上强加一个多维网格结构来汇总数据，然后采用一种小波变换来变换原特征 空间，在变换后的空间中找到密集区域。在该方法中，每个网格单元汇总了一 组映射到该单元点的信息。这种汇总信息适合于在内存中进行多分辨率小波变 换使用，以及随后的聚类分析。 2 2 5 基于模型的算法 基于模型的算法【1 9 】试图优化给定的数据和某些数学模型之间的适应性。这 样的算法经常是基于这样的假设，数据是根据潜在的概率分布生成的。基于模 型的算法主要有两类，分别为统计学方法和神经网络方法。 概念聚类是一种统计学方法。概念聚类是机器学习中的一种聚类方法，给 出一组未标记的对象，它产生对象的一个分类模式。与传统的聚类不同，概念 聚类除了确定相似对象的分组外，还向前走了一步，为每组对象发现了特征描 述，即每组对象代表了一个概念或类。因此，概念聚类是一个两步的过程首先 进行聚类，然后给出特征描述。概念聚类的绝大多数方法采用了统计学的途径， 在决定概念或聚类时使用概率度量。 神经网络方法将每个类描述为一个标本，标本作为聚类的原型，不一定对 应一个特定的数据实例或对象。根据某些距离度量，新的对象可以被分配给标 本与其最相似的类，被分配给一个类的对象的属性可以根据该类的标本的属性 来预测。 基于模型的算法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟 合。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位 聚类。它也基于标准的统计数字自动决定聚类数目，考虑“噪声”数据或孤立 江苏大学硕士研究生学位论文 点，从而产生健壮的聚类算法。 一些聚类算法集成了多种聚类方法的思想，所以有时将某个给定的算法划 分为属于某类聚类方法是很困难的。此外，某些应用可能有特定的聚类标准， 要求综合多个聚类技术。 2 2 6 基于模糊的算法 传统的聚类把每个样本严格地划分到某一类。随着模糊集理论的提出，传 统聚类被推广为模糊聚类。在模糊聚类中，每个样本不再仅属于某一类，而是 以一定的隶属度属于每一类。换句话说，通过模糊聚类分析，得到了样本属于 各个类别的不确定性程度，即建立起了样本对于类别的不确定性的描述，这样 就更能准确地反映现实世界。 基于目标函数的模糊聚类方法首先由r u s p i n i 2 0 1 提出，但真正有效的算法 f c m 却是由d u n n 给出的由b e z d e k 将其进一步扩展，建立起了模糊聚类理论。 从此，模糊聚类蓬勃发展起来，并且提出了许多模糊聚类算法【2 1 】。 2 3 文本聚类算法的比较 对聚类算法可以从六个方面对其性能进行比较。 ( 1 ) 可伸缩性 很多聚类算法在小数据集上能够达到很好的效果，但是在满足小数据集的 同时能否满足大数据集、高复杂性、高增量的要求，是考察算法性能的一个方 面。 ( 2 ) 处理不同类型属性的能力 现实世界中的数据存在多种属性类型，如数值型、一元型、分类标称型、 序数型及混合型数据。一般的聚类算法都能处理数值型数据，由于聚类算法的 应用范围不断增大，也要求其能处理不同类型属性的数据。 ( 3 ) 发现任意形状的簇 很多基于距离的聚类算法只能发现具有相近尺度的球状簇，而算法能否发 现任意形状的簇是非常重要的，如螺旋型或呈延伸状态的簇，以及其它非凸形 状的簇。 1 3 江苏大学硕士研究生学位论文 ( 4 ) 处理噪声数据的能力 实际应用中的数据不可避免存在与所需内容无关的噪声数据，包括孤立点、 空缺、未知数据或错误等，算法能否降低这些噪声数据的影响，决定了算法能 否发现数据真实的分布状态。 ( 5 ) 对输入顺序的敏感性 对输入数据顺序的敏感性，是指算法能否与顺序无关，即无论以什么样的 顺序输入数据，都能得到正确的聚类结果。 ( 6 ) 处理高维数据的能力 随着数据挖掘的发展，聚类算法越来越多地被应用于文本聚类以及网页聚 类中，从而是聚类算法面临高维空间的非常稀疏、超高维的数据聚类问题。 比较各种聚类算法的性能如表2 1 表2 1 聚类算法比较 输入顺 适合的 多维数 发现簇噪声敏 聚类算法算法效率数据类伸缩性序敏感 型 据 的形状感性 性 图像、文凸状、球 k m e a l l 8 d ( 朋尉) 一般 n 敏感 一般 本数值状 凸状、球 b i r c h o o v ) 数值较高 n不 一般 状 o 心s 岬i c u r e 数值较高 n 任意不一般 l o g 虬咄) c h a m 匣i ，e o n d ( 2 ) 数值一般n任意 不 一般 d b s c a n o ( n l o g n ) 数值一般 n 任意一般 不 o p n c s o ( n l o g n ) 数值一般 n 任意一般 不 数值、文 s o m o ( j v ) 一般n任意敏感敏感 本 s t 玎n g o ( k m n ) 数值高n任意不不 1 4 江苏大学硕士研究生学位论文 2 4 文本聚类效果评价指标 聚类是要发现数据中潜在的分组，因此，聚类结果的评价，即发现聚类是 否有效是聚类分析中一个重要的环节。在评价聚类结果时，适合数据最优的聚 类个数就成为评价聚类有效性的一个重要方面。尤其是对于多维特征向量的模 式，不能直观的看出聚类效果，需要用多种指标对其进行衡量。 在传统聚类研究中，对文本聚类效果进行评价有专门的研究，称为聚类有 效性分析( c l u s t e r i n gv a l i d i t y ) 。在聚