（计算机应用技术专业论文）web挖掘中的xml文档聚类研究.pdf

山东师范大学硕士学位论文 摘要 信息技术的快速发展促使w e b 上的数据爆炸式的增长，如何从海量的w e b 数据中高 效准确的获得想要的知识成为热门的研究课题。w e b 挖掘就是从w e b 信息中获取潜在的、 有价值的知识或模式的过程，分类、聚类、特征选择等作为w e b 挖掘的主要技术已经得到 长足的发展。聚类分析在w e b 挖掘中占有重要的地位，所谓聚类就是按照某种相似性度量， 根据一定的准则将一个对象集合成若干类，使得同类对象之间尽可能的相似，不同类对象 之间尽可能的相异。聚类作为w e b 挖掘的预处理阶段可以通过分类数据来提高挖掘的效率 和精确率。 w e b 页面多数以h t m l 文本的形式存在，但随着w e b 数据的多样化和复杂化，h t m l 文档已经满足不了信息处理和信息交换的要求。x m l 是由w 3 c 提出的标准，由于灵活性、 开放性和自描述性等特点，逐渐成为w e b 上主流数据格式和交换标准。因此x m l 聚类研 究具有重要的意义。本文对x m l 聚类进行了系统的分析和研究，针对x m l 特性提出了一 种能够包含语义的特征提取方法，在此基础上提出一些改进的聚类算法，并在真实文档集 和人工文档集上进行了聚类实验。本文工作和创新如下： 首先本文对文档聚类的聚类算法和x m l 相关规范进行了总结分析，指出了目前文档 聚类领域常用聚类算法的不足。接着重点研究了x m l 文档聚类的关键问题一文档相似性 度量方法，分析了经典编辑距离法和基于边集的x m l 文档相似度测度方法，在分析了空 间向量模型的基础上提出了标签与路径相结合的x m l 文档向量模型，根据文档树的层次 ：赋予向量特征岐密酌j i 交值，能够表达x m l 元素嵌套的语义信息，通过在示例文档上计算 相似度与编辑距离法和基于边集的方法等相似度度量方法进行了比较，计算结果证明此方 法对难分文档具有更好的区分能力。 ， 机器学习技术是w e b 挖掘的重要技术支撑，其中集成学习和半监督学习是机器学习近 几年新兴崛起的技术，大量研究和实验已经证明集成学习和半监督学习可以改进聚类和分 类的性能。本文基于集成学习和半监督学习对传统聚类算法进行了改进，针对传统单一的 划分聚类算法和层次聚类算法的弱点，提出了一种基于b a g g i n g 的集成聚类算法，在基聚类 器生成阶段使用b o o t s t r a p 抽样产生原始文档集的多个子集，在文档子集上基于加权的标签 和路径特征向量运行划分聚类算法，然后使用聚类共识率来删除低质量的聚类中心，在生 成的聚类中心集合上进行层次聚类得到最终的结果。由于集成聚类的计算复杂度较高，本 文对提出的集成聚类算法进行了改进，提出一种基于半监督学习的聚类算法，使用适当暂 停的模糊划分聚类f c m 算法来抽样原始文档集，选择在f c m 聚类中心附近的数据点组成 数据子集，对数据子集仍然使用层次聚类算法，然后用得到的聚类中心点作为监督信息来 指导f c m 算法继续执行。最后我们在真实文档集和人工文档集上分别应用本文聚类算法， 结果表明本文算法聚类质量优于单聚类算法，并且具有较高的鲁棒性。 山东师范大学硕士学位论文 关键词：x m l ；聚类；向量空间模型；集成学习；半监督学习 分类号：t p 3 9 1 山东师范大学硕士学位论文 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 to fi n f o r m a t i o nt e c h n o l o g y , d a mo nw e bi sh a v i n ga l le x p l o s i v e g r o w t h h o wt og e td e s i r e dk n o w l e d g ef r o mt h em a s so fw e bd a t ae f f i c i e n t l ya n da c c u r a t e l y b e c o m eah o tr e s e a r c ht o p i c i nt h i se n v i r o n m e n t ，w e bm i n i n gt e c h n o l o g yw a sb o r n , w e bm i n i n g i sa i m e dt oo b t a i np o t e n t i a l ，v a l u e dk n o w l e d g eo rp a a e mf r o mt h ew e b ，t h em a i nt e c h n o l o g yo f w e b m i n i n gs u c ha sc l a s s i f i c a t i o n ，c l u s t e r i n ga n df e a t u r es e l e c t i o n ，h a sb e e nd e v e l o p e dr a p i d l y c l u s t e ra n a l y s i sp l a y sa ni m p o r t a n tr o l ei nw e bm i n i n g ，c l u s t e rc a nd i v i d ea l lo b j e c ts e t st o s e v e r a lc a t e g o r i e sa c c o r d i n gt os o m es i m i l a r i t ym e a s u r eb a s e do i ls o m ec r i t e r i a ，t h eo b j e c t si nt h e s a m ec a t e g o r i e sa l em o s ts i m i l a r ，o b j e c t sb e t w e e nd i f f e r e n tc l u s t e ra r em o s td i f f e r e n t a sa p r e p r o c e s ss t a g e ，c l u s t e r i n gc a ni m p r o v et h ee f f i c i e n c ya n da c c u r a c yo fd a t am i n i n gt h r o u g h c l a s s i 研n gt h ed a t as e t s t h em a j o r i t yo fw e bp a g e sa r et e x td o c u m e n t si nt h ef o r mo fh t m l ， b u tw i t ht h ed i v e r s i t ya n dc o m p l e x i t yo fw e bd a t a , h t m ld o c u m e n t sc a l ln o tm e e tt h e r e q u i r e m e n t so fi n f o r m a t i o ne x c h a n g ea n di n f o r m a t i o np r o c e s s i n g x m li sa na l t e r n a t i v e s t a n d a r dw h i c hi sp u tf o r w a r db yw 3 c b e c a u s eo ft h ef e a t u r e ss u c ha sf l e x i b i l i t y , o p e n i n ga n d s e l f - e x p l a n a t i o n , x m lh a sg r a d u a l l yb e c o m et h em a i nw e bd a t af o r m a ta n dd a t ae x c h a n g e s t a n d a r d s t h e r e f o r e ，x m lc l u s t e r i n gr e s e a r c hi s o fg r e a ts i g n i f i c a n c e t h i st h e s i st a k e sa s y s t e m a t i ca n a l y s i sa n dr e s e a r c ho nx m lc l u s t e r i n ga n dp u tf o r w a r das e m a n t i cf e a t u r e e x t r a c t i o nm e t h o d s o m ei m p r o v e dc l u s t e r i n ga l g o r i t h m sa r ep r o p o s e d ，a n dw ec o n d u c t e x p e r i m e n t so nr e a ld a t a s e t sa n da r t i f i c i a ld a t a s e t s t h ew o r ka n di n n o v a t i o no ft h i st h e s i sa r ea s f o l l o w s ： i nt h ef n - s t ，c l u s t e r i n ga l g o r i t h m sa n dx m l r e l a t e dd e f i n i t i o na r es u m m a r i z e da n da n a l y z e d , a n dt h e nw ep o i n to u tt h a tt h el a c ko fc o m m o n l yu s e dc l u s t e r i n ga l g o r i t h mi nt h ec u r r e n tf i e l do f d o c u m e n t sc l u s t e r i n g s e c o n d l y , w ef o c u so nt h ek e yp r o b l e mo fx m ld o c u m e n tc l u s t e r i n g - t h e d o c u m e n ts i m i l a r i t ym e a s u r e m e n tm e t h o d s ，s t u d yt h ec l a s s i c a le d i td i s t a n c ea n dd o c u m e n t s i m i l a r i t ym e a s u r e m e n tm e t h o d sb a s e do ne d g es e t a f t e ra n a l y z i n gt h es p a c ev e c t o rm o d e l ，w e p r o p o s e dax m ld o c u m e n tv e c t o rm o d e lb a s e do nt h ec o m b i n a t i o no ft a ga n dp a t h ，t h er i g h t v a l u e so ff e a t u r e sa r ed e f i n e da c c o r d i n gt ot h el e v e lo ft h ed o c u m e n tt r e e ，w h i c hc a ne x p r e s st h e s e m a n t i c so fn e s t e dx m le l e m e n t s w ec a l c u l a t et h es i m i l a r i t yb e t w e e nt h ee x a m p l ed o c u m e n t s t h r o u g ho u rm e t h o da n d t h et w om e t h o d sm e n t i o n e da b o v e ，r e s u l t ss h o wt h a to u rm e t h o dh a sa b e t t e rd o c u m e n t sd i s t i n g u i s h e da b i l i t y m a c h i n el e a r n i n gt e c h n i q u e sa r ei m p o r t a n tw e bm i n i n gt e c h n i c a ls u p p o r t , e n s e m b l e l e a r n i n ga n ds e m i s u p e r v i s e dl e a r n i n ga l ee m e r g i n gi nr e c e n ty e a r s s u b s t a n t i a lr e s e a r c ha n d e x p e r i m e n t a t i o nh a v ep r o v e ne n s e m b l el e a r n i n ga n ds e m i s u p e r v i s e dl e a r n i n gc a ni m p r o v et h e p e r f o r m a n c eo fc l u s t e r i n ga n dc l a s s i f i c a t i o n b a s e do nt h es t u d yo fe n s e m b l el e a r n i n ga n d 山东师范大学硕士学位论文 s e m i - s u p e r v i s e dl e a r n i n gw ei m p r o v et h et r a d i t i o n a ls i n g l ec l u s t e r i n ga l g o r i t h m i no r d e rt o i m p r o v et h ew e a k n e s s e so fs i n g l ec l u s t e r i n ga l g o r i t h m s ，w ep r o p o s eac l u s t e r i n ga p p r o a c hb a s e d o nb a g g i n ga l g o r i t h m o nb a s ec l u s t e rg e n e r a t i o ns t a g e ，w eu s et h eb o o t s t r a pm e t h o dt os a m p l e t h eo r i g i n a ld o c u m e n ts e t ，r e s u l t i n gi nan u m b e ro fs u b s e t so ft h eo r i g i n a ld o c u m e n ts e t ，r u nt h e p a r t i t i o n a lc l u s t e r i n ga l g o r i t h m ，t h e ni m p l yc l u s t e r i n gc o n s e n s u sr a t et or e m o v el o w - q u a l i t y c l u s t e rc e n t e r , f i n a l l y , w er u nh i e r a r c h i c a lc l u s t e r i n go nt h ec o l l e c t i o no fc l u s t e rc e n t e r sg e n e r a t e d b yp a r t i t i o n a lc l u s t e r i n gm e t h o dt og e tt h er e s u l t b e c a u s e o ft h e h i g h e rc o m p u t a t i o n a l c o m p l e x i t y , w ep r o p o s e dac l u s t e r i n gm e t h o db a s e do ns e m i s u p e r v i s e dl e a r n i n gt oi m p r o v et h e e n s e m b l ec l u s t e r i n ga l g o r i t h m w er u nf c mc l u s t e r i n ga l g o r i t h ma n dp a u s eo n 觚i d e n t i f i e d i t e r a t et os a m p l et h eo n g i n a ld o c u m e n ts e t ，t h e nc o m b i n et h ed a t an e a rt h ec l u s t e rc e n t e r si n t oa n e wd a t as e t ，w ea p p yh i e r a r c h i c a lc l u s t e r i n gm e t h o dt og e tr i g h tn u m b e ro fc l u s t e rc e n t e r sw h i c h t h e nh e l pf c mc o n t i n u et of i n a lr e s u l t f i n a l l y , w ea p p l yt h e s ea l g o r i t h m so i lt h er e a la n d a r t i f i c i a ls e ts e p a r a t e l y , a n dr e s u l t ss h o wt h a tt h ec l u s t e r i n ga l g o r i t h mp r o p o s e di sb e t t e rt h a n s i n g l ec l u s t e r i n ga l g o r i t h m ，a n dh a sh i g h e rr o b u s m e s s k e y w o r d s ：x m l ，v e c t o rs p a c em o d e l ，e n s e m b l el e a m i n g ，s m i s u p e r v i s e dl e a r n i n g c l a s s i 6 c a t i o n ：t p 3 9 1 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得( 注：如没有其它需要特别声明的，本栏 可空) 或其它教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名：0j i 式 导师签字： 学位论文版权使用授权书 咖易 本学位论文作者完全了解兰邀有关保留、使用学位论文的规定，有权保留并向国家有 关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权! 墩可以将学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者躲乞谈导师签字乏段 签字日期：2 0 09 年月砂日签字日期：2 0 0 7 年 多加 w 月，争 山东师范大学硕士学位论文 1 1 研究背景和意义 第一章绪论 随着信息技术的发展，来自i n t e m e t 及各种方式获取的数据呈爆炸式增长，对这些海量数 据的知识发现成为热门研究方向，为了能从网络上的大量数据中高效的检索有用数据，w e b 挖掘技术应运而生，并成为研究人员普遍关注的重要课题。w e b 挖掘旨在从大量非结构化、 异质的w e b 信息资源中发现有效的、新颖的、潜在可用的及最终可理解的知识( 包括概念、 模式、规则、规律、约束及可视化等形式) 。w e b 上信息的多样性决定了w e b 挖掘任务的 多样性，针对传统数据库的数据挖掘技术只能处理结构化数据，不能直接应用于自由文本和 半结构化文本。然而网络上绝大部分电子信息以自由文本形式存在，是无结构化的数据或是 半结构化的h t m l 文本，w e b 文本挖掘技术显得尤为重要。虽然w e b 页面是以文本的形式 驻留在网络上，但是其形式不同于普通文本，w e b 页面以某种格式呈现半结构化，数据结 构不规则或不完整，复杂程度远高于普通文本文档，其数据结构隐含、模式信息量大、模式 变化快。作为w e b 挖掘主要应用之一的搜索引擎近来发展迅速，其目标是使用户可以使用 搜索引擎根据知识需求搜索自己想要的页面。目前搜索引擎的查全率有较大提高，但是没有 成熟的方法可以明显提高查准率，用户面对搜索引擎返回的大量查询结果，如何快速定位所 需求的信息仍然比较困难。 相关研究表明，文档聚类能够把文档分类为不同的类别。已经成为信息检索、数据管理、 w e b 文本挖掘的重要环节。文档聚类是一种无指导的文档分类，首先通过提取文档的特征值 映射成向量，在文档集对应的多维向量空间中使用各种聚类算法把文档集分成若干集簇，每 个集簇内的成员之间具有较大的相似性，而集簇与集簇之间的文本具有较小的相似性。好的 聚类通过把文档集划分为各种带有足够信息的子集来得到文档集的层次，同时用户通过描述 类别信息的关键词，可以对同一类别内所有文档有大致的了解，从而缩小了检索范围，缩短 了查找时间，弥补了传统w e b 文档搜索引擎的不足，提高了查询的精确度。 自1 9 9 8 年w 3 c 发布x m l l 0 标准以来，越来越多的信息采用x m l 数据模型来统一描 述，相信不久的将来，x m l 将成为w e b 上数据描述和交换的标准，并且将会代替h t m l 成 为i n t e m e t 上驻留数据的主要格式。x m l 的出现为信息的处理提供了内容与结构两方面强有 力的支持，因此w e b 上x m l 文档挖掘的研究也越来越受到重视。x m l 文档聚类作为挖掘 和检索x m l 数据的一个重要步骤，成为新的研究热点。 然而，由于半结构化文档的特殊性与w e b 文本数据的复杂性，x m l 文档聚类研究面临 着诸多困难： 1 由于x m l 文档是半结构化树形结构，x m l 文档的标签以及路径约束使其具有传 统文档所没有的结构和层次特性，传统的文档聚类方法并不适合处理x m l 文档树 形结构所含语义和元素包含的语义信息。 山东师范大学硕士学位论文 2 使用文本挖掘中的特征提取方法得到文档特征空间往往具有很高的维数，用传统 的聚类算法处理这些高维数据计算复杂度过高，效率低下。 3 w e b 网络环境错综复杂，w e b 上得到文本数据往往含有大量的噪音数据，如何增 强聚类算法的鲁棒性，提高x m l 文档聚类质量是一个挑战。 本文对x m l 文档聚类进行深入研究，针对x m l 文档结构特征，考虑节点嵌套隐含的 语义信息，提出基于路径和标签相结合的x m l 文档向量特征提取方法，在形成的x m l 文 档特征向量空间上进行聚类研究。针对传统聚类算法精度不够，抗噪能力不强等问题，将集 成学习技术应用到聚类方法中，提出基于b a g g i n g 的x m l 文档聚类方法，并在此基础上进 行改进，引入半监督学习思想，提出了一种联合划分聚类和层次聚类的半监督聚类算法，提 高了聚类质量，克服了传统聚类算法在x m l 文档聚类中的诸多缺陷。 1 2 本文工作及创新 1 2 1 本文组织结构 本文对x m l 文档聚类展开研究，具体内容组织如下： 第一章为本文绪论部分。首先分析了本文的选题背景和研究意义，然后介绍了x m l 文 档聚类需要面对的问题，最后总结了本文的工作及创新点。 第二章详细介绍了x m l 聚类研究相关的技术，包括x m l 技术的特性、概念、规范、 以及文档树的描述；分析了常见聚类技术及其存在的问题，这些技术和理论是下面章节的基 础。 第三章介绍了x m l 文档聚类中x m l 文档相似性度量的研究进展和经典方法，针对 x m l 的层次结构特性，提出一种标签与路径相结合的x m l 文档向量模型。 第四章阐述了集成学习理论以及与w e b 挖掘的关系，在集成学习的基础上提出了一种 基于b a g g i n g 的x m l 文档聚类算法并总结了算法的特点。 第五章阐述了半监督学习技术的相关进展和算法，借鉴半监督思想，联合划分聚类方法 和层次聚类方法提出一种基于半监督学习的聚类算法。 第六章描述了实验数据、环境、过程以及对实验结果的评价。 第七章总结了本文工作，并对下一步工作进行了展望。 1 2 2 本文创新 1 提出一种标签与路径相结合的x m l 文档向量特征提取方法，能够有效的表达x m l 文档树嵌套的语义信息。 2 引入集成学习技术，将原始文档集抽样，针对x m l 文档的特征项对b a g g i n g 算法进 行改进，结合了划分聚类方法和层次聚类方法的优点，并消除了各自的缺陷，提高了聚类的 健壮性和准确性。 2 山东师范大学硕士学位论文 3 针对集成学习计算规模大的缺陷，对基于集成学习的聚类进行改进，借鉴半监督学 习思想，提出一种联合单一聚类算法的算神h p c 算法，提高了聚类效率，并使聚类具有 较强的鲁棒性。 山东师范大学硕士学位论文 第二章x m l 聚类相关技术 本章介绍x m l 文档聚类涉及基础技术以及相关的一些研究，包括聚类的经典方法， x m l 技术特性和技术规范，文档聚类需要的一些相似度度量模式。 2 1 聚类技术 2 1 1 聚类概述 “物以类聚，人以群分。”人类认识世界往往从将被认识的对象进行分类而开始的，因此， 聚类是一项最基本的认识活动。通过适当聚类，事物才便于研究，事物的内部规律才可能为 人类所掌握。聚类，就是按照事物的某些属性，把事物聚集成类，使类间相似性尽量小，类 内相似性尽量大，按照相似程度的大小，将事物( 样本、对象或变量) 逐一归类。聚类分析 最初是统计学的一种方法提出来，作为统计学的重要研究内容之一，聚类分析具有坚实的理 论基础并形成了系统的方法学体系，随着信息技术的发展，网络世界的数据成级数增长，催 生了数据挖掘、机器学习等新的数据处理技术，这些技术与聚类分析技术相互促进和联系形 成一些新的研究热点，聚类作为数据挖掘采用的核心技术，已经成为这个领域中的一个非常 活跃的研究课题。 聚类的定义：聚类( c l u s t e r i n g ) 是将数据集合划分成为多个类( c l a s s ) 或簇( c l u s t e r ) 的过程。 由聚类所生成的类是对象的集合，同一个类中的对象之间具有较高的相似度，不同类中的对 象具有较大的差异性。同一类内对象的相似度遵循一定的计算准则，常见的度量准则是对象 间的距离。 聚类的严格数学描述如下： 被研究的样本集为，类c 定义为，的一个非空子集， 即c ；n c ，= 妒且c 矽 聚类就是满足下列两个条件的类c l ，c 2 ，g 的集合 1 c 1u c 2 。u c k = i 2 c fn c f = 矽( 对任意i 歹) 由第一个条件可知，样本集i 中的每个样本必定属于某一个类；由第二个条件可知， 样本集，中的每个样本最多只属于一个类。 从统计学的观点看，聚类分析是通过数据建模简化数据的一种方法，在多元数据分析 中占有重要地位。从机器学习的角度看，聚类是无监督的学习过程，而分类是有监督的学习 过程，区别在于分类需要事先知道分类所需的一些信息，而聚类预先并不知道具体类的个数 山东师范大学硕士学位论文 和属性值等相关信息，由聚类算法自动找到这个分类，从这个意义上说，聚类是种特殊的分 类，即无监督的分类，本文将一般的聚类称之为无监督聚类是为了区别于近年来出现的新的 半监督聚类，后者使用分类信息来指导聚类过程，为了方便讨论，本文把无监督聚类简称为 聚类。聚类已经被证明成功地应用在生物学、经济学、医药学等众多领域，由于可以作为 w e b 挖掘的预处理过程，提高信息检索的效率，因此聚类在信息检索、文本挖掘、w e b 数 据分析、客户关系管理等方面也起着重要作用。 2 1 2 聚类的若干关键问题 数据挖掘的聚类任务往往是复杂而且具有挑战性的，根据常用的聚类算法和应用，聚 类相关研究可归结为以下若干关键问题： 1 聚类的目标 现有的一些聚类方法试图通过对给定的数据集寻找一个划分来得到想要的聚类结果。 另有一部分聚类方法能够提供更灵活的结果，他们寻找能够划分聚类目标数据集的层次树， 在不同层次的截断，可以得到不同层次的类簇。 2 数据表示 大多数聚类方法是不可能工作在原始数据集上的，对聚类目标数据的表示关系到数据 对象之间的相似性计算，部分聚类方法将数据对象表示成为向量模式，例如传统w e b 文本 挖掘中文本聚类分析通常采用v s m 向量空间模型，将文档进行特征提取，形成特征向量， 文档对象间的相似度由向量间的欧几里德距离定义。然而，有些方法仅需要数据对象间的两 两相似度即可，这些算法往往将数据集表示成为相似度矩阵，对数据的特征并没有严格的约 束，但是这种表示方式会造成更高的计算复杂度。 3 数据处理能力 一个好的聚类算法应该具有良好的数据处理能力，包括以下几个方面： ( 1 ) 可伸缩性。聚类算法对小数据集和大规模数据集应该同样有效，许多聚类算法在小 数据集合上工作的很好，但面对一个可能包含几百万个对象的大规模数据集，聚类结果可能 出现偏差。可伸缩性要求算法能够处理大数据量的数据库对象，比如处理上百万条记录的数 据库。这就要求算法的时间复杂度不能太高。 ( 2 ) 能处理多种特性的数据。许多聚类算法设计成处理数值型的数据，然而现在w e b 上的数据多种多样，具有不同的字段属性，这要求聚类算法能够处理不同属性的数据。对于 数据集的分布，聚类算法应该有良好的兼容性，好的算法不仅能处理球形的和密度均匀的类 簇，还能处理非凸类型数据集、任意形状分布的数据集。一个数据库或者抽取的特征向量都 有很多的属性字段或者说维数，一些算法在处理维数比较少的数据集时表现不错，例如两、 三维的数据，但对于高维数据却无能为力，所以对高维数据的聚类是很具有挑战的。聚类算 法不仅要擅长处理低维的数据集，而且要能够处理高维、数据可能非常稀疏且高度偏斜的数 据集。 ( 3 ) 抗噪能力。现实数据库中常常包含有噪声数据亦即异常数据，例如孤立点、空缺、 6 山东师范大学硕士学位论文 未知数据或者错误的数据。有一些聚类算法可能会对这些数据很敏感，可能导致低质量的聚 类结果。聚类算法要能处理现实世界的数据集中普遍包含的噪声数据。 4 聚类评价 一个聚类的划分结果是否是正确的? 数据对象是否都已经划分到类簇当中? 类簇的个 数是否正确? 聚类是否符合原始数据集的固有划分? 与其它聚类方法相比效果是否更好? 对这些问题的解答就需要研究聚类的评价准则，确定什么样的聚类是有效而优秀的。外部准 则和内部准则是目前常用的评价准则。 2 1 3 主要聚类方法 随着近几年各领域的专家对聚类研究的关注，大量的聚类算法相继涌现出来，由于设 计的目标和针对的领域数据不同，很难对这些算法进行一个优劣的比较，例如，有些算法在 文本数据上表现出良好的效率，但是在半结构数据上却缺乏说服性。同样，对这些算法进行 一个严格准确的分类也是很困难的，虽然文献a n i lkj a i n 【1 1 和l k 叭缸衄【2 1 等人提出了一些划 分的方法，但是由于新聚类算法的数量的迅速增长以及各种算法间差异性愈发复杂，给定一 个完全清晰的划分是非常困难的，本文综合目前普遍流行的划分标准，借鉴文献 1 的划分建 议，将聚类算法划分为以下几类。 1 划分方法( p a r t i t i o n a lm e t h o d s ) 划分聚类方法按照一定的准则对聚类对象进行聚类，直接得到一个聚类目标的划分。 大多数划分方法都是通过不断地调整划分对象，迭代的优化一个准则函数来得到聚类结果， 当聚类准则函数达到最优，聚类对象将不再变化，聚类的划分就趋于稳定。典型的划分方法 基于最小平方误差准则函数，这类划分聚类方法通过最小化一个代价函数来运行，代价函数 为所有对象到分配的聚类中心的距离平方总和，其数学定义如下： 孟 e = l i p - m ，0 i = 1 厍 式中的是数据集中所有对象的平方误差的总和，肌，是类c ，的平均值( 或中心点) ，p 是数据空间中的数据对象。为了达到全局最优，基于划分的聚类要求穷举所有可能的划分。 划分聚类法中的经典算法是k 均值算、法【3 1 。k 均值算法基于最小平方误差函数，假设把 数据集看作空间中的点的集合，给定聚类个数k ，k 均值算法通过迭代的计算各个类簇的平 均值来选择中心点，直到各数据点到本簇的中心点距离平方和达到最小而停止划分过程。其 算法过程可描述如下： ( 1 ) 初始化 随机选择k 个点作为初始中心点； 将所有数据点分配给最近的中心点； ( 2 ) 迭代 通过计算各类簇的平均值更新各个类簇的中心点； 山东师范大学硕士学位论文 分配各数据点给距离最近的中心点； ( 3 ) 停止 直到中心点不再发生变化停止划分。 k 均值方法是解决聚类问题的一种经典方法。它的主要优点是算法简单、快速。然而这 种方法依赖于初始中心的选择，两次运行可能会导致不同的聚类结果。其次，该方法不能发 现非凸面的簇，或大小非常不对称的簇。由于少量的孤立点和“噪声”数据能对平均值产生极 大的影响，k 均值方法对此类数据很敏感，最小化代价函数容易陷入局部最优解。 k 均值方法用平均值来代表聚类中心，而有些情况下这样的平均值不好计算，k a u f m a n 和r o u s s s e e u w 提出的p a m ( p a r t i t i o n i n ga r o u n dm e d o i d ) 和c l a r a ( c l u s t e r i n gl a r g e a p p l i c a t i o n s ) 算、法【2 】中，每个类用接近该类中心的对象来表示，因此称之为k 中心点( 1 【m e d o i d ) 方法。h u a n g 4 】提出k 一模依m o d e s ) 方法，它扩展了k 平均方法，用模来代替类簇的平均值， 采用新的相似性度量方法来处理分类对象，这样使聚类算法能够处理非数值型属性数据。 近几年随着模糊c 均值算法( f u z z yc m e a n s ) 的提出，基于平方误差准则的模糊划分聚 类方法逐渐流行。模糊划分聚类的划分结果并不硬性的将聚类对象划分为某一类，而是赋予 其一个模糊隶属度，它更能避免代价函数容易陷入局部最优解的缺陷。为了提高聚类结果对 孤立点的免疫力，许多模糊聚类算法被提出，如h i e h e m 【5 l 和b e r t r a n d 6 】分别基于鲁棒性统计 和利用噪音数据点进行了模糊聚类研究。 2 基于密度的方法( d e n s i t y - b a s e dm e t h o d s ) 由于划分方法基于对象之间的距离进行聚类，这样的方法只能发现球状的类，对任意 形状的类的聚类效果很差。基于密度的聚类方法把聚类看作是由稀疏对象区域分割开的稠密 对象区域的集合，只要邻近区域的密度( 对象或数据点的数目) 超过某个阈值，就继续聚类。 也就是说，对给定类中的每个数据点，在一个给定范围的区域内必须至少包含某个数目的点。 这样聚类方法可以发现任意形状的类，聚类数据可以是任意分布。d b s c a n 算、法l7 j 是由e n t e r 提出的典型密度聚类算法，该算法根据互邻接的对象联接紧密程度将具有足够高密度的区域 划分为类，并可在空间数据中发现任意形状的类，具有一定的鲁棒性。在此基础上作者对算 法进行了改进，提出了g d b s c a n 算法【8 】，z h o us h u i g e n g 掣9 j 1 1 0 j 也在不同方面对d b s c a n 算法进行改进，提高了d b s c a n 算法的执行效率。 一些基于密度的聚类方法例如d e n c l u e 1 1 】和c l i q u e 1 2 是为稀疏数据设计的，其基本 思想是基于网格( g r i d - b a s e d ) ，但也是与密度息息相关的，因此把它们归于基于密度的聚类方 法，这些聚类方法把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类操作 都在这个网格结构( 即量化空间) 上进行，对密度高的单元进行处理，而忽略稀疏的孤立点。 这种方法的主要参数是量化步骤数和密度阈值，主要优点是它的处理速度很快，其处理速度 独立于数据对象的数目，只与量化空间中每一维的单元数目有关。但这种算法效率的提高是 以聚类结果的精确性为代价的。 大部分基于图论( g r a p h t h e o r e t i c ) 的聚类方法也是与密度相关的，基于图论的聚类用图中 山东师范大学硕士学位论文 节点代表数据对象，数据对象之间的相异度用节点之间的边长来衡量，在大多数这样的聚类 中，去掉最长的边而分割出来的子图即得到类簇，例如c t z a l a n 【1 3 】提出的方法就是首先得 到原图的最小生成树，然后剪掉最长的边生成聚类。赵艳厂等从样本分布等密度线图的思想 出发，提出一种等密度线聚类算、法【1 4 】。基于密度的聚类算法计算复杂度较高，而且对于密度 分布不均的数据集，往往得不到满意的聚类结果，基于密度的聚类算法中，参数设置的细微 不同可能导致差别很大的聚类结果，这种对参数非常敏感的特性是这类聚类算法一直很难克 服的缺陷。 3 层次方法( h i e r a r c h i c a lm e t h o d ) 层次聚类法就是把类别看作是有层次的，即随着类层次的变化，类中的对象也相应发 生变化。层次聚类结果形成一棵层次树。每个类结点还包含着若干个子结点，而兄弟结点是 对其父结点的划分，因此该方法允许在不同的粒度对数据进行聚类。按照层次树的生成方式， 可将层次聚类法分为两种，即自底向上的凝聚方法和自顶向下的分裂法。 给定n 个聚类对象，凝聚聚类在初始阶段通过把每个对象指定为单独一类，然后迭代 的合并最相似的类对，直到所有的类合并为一个( 层次的最上层) ，或者达到一个终止条件， 最后结果是形成一种层次树。凝聚聚类法聚类质量比较好，不用事先指定k 值，通过截断 不同高度的层次树可以得到聚类的层次。其弱点是二次时间复杂度，每次迭代都必须比较所 有类簇的相似度，这使得层次聚类不易处理大规模数据集。图2 1 是凝聚层次聚类的示意图， 左图中7 个对象被聚类到三个类簇中，右图就是对应的层次聚类生成的层次树，自上而下对 象的相似度逐渐增大，在一定相似度小于某一值的高度例如虚线部分截断层次树就得到三个 聚类。 bcde fc 图2 1 层次聚类 分裂的方法，也称为自顶向下的方法，一开始将所有的对象置于一个类中。在迭代的 每步中，类被分裂为更小的类，直到每个类只包含一个对象为止，或者达到一个终止条件。 在凝聚或者分裂层次聚类方法中，通常以用户定义希望得到的类的数目作为结束条件。 在类的合并或分裂过程中，需要衡量类的相似度，在欧式向量空间中即为类簇间的欧氏距离。 类簇间距离的度量广泛采用单链接( s i n g l e 1 i n k ) 、全链接( c o m p l e t e 1 i n k ) 和平均距离三种方法， 相 叙 度 山东师范大学硕士学位论文 其中单链接是计算类间最近的对象之间的距离，而全链接是计算类间最远的对象之间的距 离，平均链接( a v e r a g e 1 t r a c ) 就是计算类间所有对象距离的平均值。 单链接( s i n g l e l i n k ) ：d 咧c ，q ) = 以二q 。毫qi o d 1 ( 2 1 ) 全链接( c o m p l e t e l i n k ) ：c j q ) = 脱棚c ，d 色qi d d 1 ( 2 - 2 ) 平均链接( a v e r a g e l i n k ) ：( c ，q ) = 了 饨c 。蚂o - - 0 1 ( 2 3 ) h t ，h j 典型的层次聚类算法包括基于平衡聚类特征树的b i r c h 算、法【1 6 】，基于类中心代表策略 的c u r e 算法【1 刀和c h a m e l e o n 算法【1 8 】。 z h a n g ，r a m a k r i s h n a n 和l i n v y 提出的b i r c h 算法是一种动态方法，建立一个称为 c f ( c l u s t e rf e a t u r e ) 树的层次数据结构，用来放聚类特征，再采用某个聚类算法对c f 树的叶 结点进行聚类。 g u h a ，r a s t o g i 和s h i m 提出的c u r e ( c l u s t e r i n gu s i n gr e p r e s e n t a t i v e s ) 方法不用单个中 心或对象来代表一个类，而是选择数据空间中固定数目的具有代表性的点代表一个类，可以 识别形状复杂和大小不同的类，而且能很好地过滤孤立点。g u h a ，r a s t o g i 和s h i m 在c u r e 方法的基础上，又提出了适用于分类数据的r o c k 方法 1 9 】。q i a ny u n t a o 提出的c u r e - n s t 2 0 】 采用改进的收缩策略，提高了c u r e 方法的聚类性能。 k a