（计算机软件与理论专业论文）基于网格和密度的数据流聚类算法研究(1).pdf

摘要 近年来，由于计算机及应用技术的高速发展，人们获取数据的能力得到极 大的提高，数据流作为一类重要的数据来源，受到越来越多的关注。 数据流是连续的、有序的、快速变化的、海量的数据。数据流不同于传统 的存储在磁盘上的静态的数据，而是一类新的数据对象。当前在数据挖掘领域 中，数据流已经成为一个研究热点。数据流聚类分析成为聚类研究的一个重要 方向。 本文的工作重点就是设计并开发一个具有较快速度和很高准确性的数据流 聚类算法。为此本文做了这些工作：介绍了课题的相关背景与意义；总结了目 前比较成熟的各种聚类算法的优缺点和适用范围：重点研究了数据流的特点和 处理数据流聚类的关键技术点；并在此基础上；通过修改摘要数据结构的方法、 设计并实现了基于网格和密度的数据流聚类算法g d e s t r e a m ( g r i da n dd e n s i t y b a s e de v o l v i n gs t r e a m ) ，该算法具有以下特点： 1 借鉴c l u s t r e a m 算法处理数据流的框架，将系统分为在线层和离线层。在 线层快速处理数据流，并将相关信息保存在摘要数据结构中；离线层在摘要数 据上进行计算提供精确聚类，以达到聚类准确度和算法速度的平衡。 2 利用网格来保存数据流的特征信息，除记录其统计信息外，还加入了记录 其空间信息的数据结构，能减少数据流信息丢失。 3 在在线层中，利用摘要数据结构记录的空间信息，数据流读取算法比较新 数据到相关网格的距离，并把新记录映射到正确网格中，能解决部分网格边缘 信息丢失的问题，比较准确地记录数据流信息。 4 在离线层中，采用基于密度的聚类算法，系统能发现任意形状的数据集； 通过引入网格帧和演化差等概念，系统能满足用户对历史信息聚类和演化分析 的需求。 基于人造数据集和真实数据集的实验表明，算法具有较好的适用性和准确 性，能对数据流进行高效的聚类分析。 关键词：数据流、聚类、双层处理模型、网格、密度 a b s t r a c t i nr e c e n ty e a r s ，b e c a u s eo ft h er a p i dd e v e l o p m e n to fc o m p u t e ra n da p p l i c a t i o n t e c h n o l o g y ，p e o p l e sa b i l i t yo fo b t a i n i n gd a t ai m p r o v e sg r e a t l y d a t as t r e a mi sat y p e o fi m p o r t a n td a t as o u r c e ，a n di ss u b j e c t e dt om o r ea n dm o r ec o n c e m s t r e a md a t ai sak i n do fc o n t i n u o u s ，o r d e r e d ，c h a n g i n gf a s ta n dh u g ea m o u n t d a t a i ti sq u i t ean e wo b je c tt h a ti sd i f f e r e n tf r o mt r a d i t i o n a ls t a t i cd a t as t o r e do nt h e d i s k c u r r e n t l y ，d a t am i n i n go nd a t as t r e a mb e c o m e sah o tr e s e a r c hf i e l d c l u s t e r i n g d a t as t r e a mi so n eo ft h eh o t t e s tr e s e a r c hp o i n t so ni t o n et a r g e to nt h i st h e s i si st od e s i g na n dd e v e l o pad a t as t r e a mc l u s t e r i n g a l g o r i t h m ，w h i c hi sa c c u r a c ya n dh i g h - s p e e d i no r d e rt or e a c ht h i s ，w eh a v ed o n e s o m ew o r ka sf o l l o w s b a c k g r o u n da n dr e l e v a n tw o r ko nd a t as t r e a mm i n i n gi s d i s c u s s e d p o p u l a rc l u s t e r i n ga l g o r i t h m sa r es u m m a r i z e d t h ec h a r a c t e r i s t i c so fd a t a s t r e a ma n dk e yt e c h n i c a lp o i n t so nd a t as t r e a mc l u s t e r i n ga r er e s e a r c h e d o nt h eb a s i s o ft h e s e ，w ep r o p o s eg d e - s t r e a m ( g r i da n dd e n s i t yb a s e de v o l v i n gs t r e a m ) a l g o r i t h m ，w h i c h i saf r a m e w o r kb a s e do n 酣da n dd e n s i t y b ym o d i f y i n gt h e s y n o p s i sd a t as t r u c t u r e ，t h i sa l g o r i t h mh a st h ef o l l o w i n gc h a r a c t e r i s t i c s 1 b o r r o w i n gt h ef r a m e w o r kf r o mc l u s t r e a ma l g o r i t h m ，g d e s t r e a mi sd i v i d e d i n t oo n l i n el a y e ra n do f f l i n el a y e r o n l i n el a y e rr e a d sd a t as t r e a mr a p i d l y ，a n ds t o r e s r e l a t i v ei n f o r m a t i o nb ys y n o p s i sd a t as t r u c t u r e w i t ht h i s ，o f f l i n el a y e rp r o v i d e a c c u r a t ec l u s t e r i n g t h et w ol a y e r sw o r kt o g e t h e rt oa c h i e v et h eb a l a n c eo fa c c u r a c y a n ds p e e d 2 t h es y s t e mp r e s e r v e st h ec h a r a c t e r i s t i c so fd a t as t r e a mb yg r i d i na d d i t i o nt o s u m m a r ys t a t i s t i c si n f o r m a t i o n ，g r i d sa l s or e c o r dt h es p a t i a l i n f o r m a t i o no fd a t a s t r e a m ，w h i c hc a nr e d u c el o s eo fi n f o r m a t i o n 3 o no n l i n el a y e r ，w i t ht h es p a t i a li n f o r m a t i o ni ns y n o p s i sd a t as t r u c t u r e ， o n l i n e r e a da l g o r i t h mc o m p a r et h ed i s t a n c e sb e t w e e nt h en e wr e c o r da n dr e l a t i v e g r i d sa n dm a pi t t oc o r r e c t g r i d ，w h i c hc a ns o l v et h ep r o b l e mo ft h e l o s so f i n f o r m a t i o no nt h ee d g eo fg r i dp a r t l y 4 o no f f l i n el a y e r ，d e n s i t y - b a s e dc l u s t e r i n ga l g o r i t h mi su s e d ，s ot h a tt h es y s t e m i i i ss e n s i t i v et ot h ed a t a s e t so fa r b i t r a r ys h a p e t h es y s t e mc a na l s os a t i s f yt h en e e do f c l u s t e r i n ga n de v o l u t i o nh i s t o r yd a t as t r e a m ，w i t ht h ec o n c e p to f 酣df r a m ea n d e v o l u t i o nd i f f e r e n c e e x p e r i m e n t so nb o t hs y n t h e t i cd a t a s e t sa n dr e a ld a t a s e ts h o w st h a tt h ea l g o r i t h m i sa p p l i c a b i l i t ya n da c c u r a c ya n dc a nc l u s t e rd a t as t r e a me f f i c i e n t l y k e y w o r d s ：d a t as t r e a m ，c l u s t e r i n g ，t w o t i e rf r a m e w o r k ，g r i d ，d e n s i t y i l l 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 研究生( 签名) ：彳l l 日期二与乙 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权武汉理工大学可以将本学位论文的全部内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存或汇编本学位论文。同时 授权经武汉理工大学认可的国家有关机构或论文数据库使用或收录本学位论 文，并向社会公众提供信息服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：生公导师( 签名) ： 同期一竺2 = _ 武汉理工大学硕士学位论文 第1 章绪论 1 1 课题研究背景和意义 随着信息技术的高速发展，人们处理的数据量越来越大，对数据操作的需 求也越来越高，从最初的简单保存数据，到对数据进行简单的统计分析，再到 发现隐藏在庞大数据中的各种关系；于此同时我们处理数据的方法，也经历了 几个阶段的变化，从六十年代前最初的文件系统( f i l es y s t e m s ) ，到七八十年 代的数据库管理系统( d b m s ，d a t ab a s em a n a g e m e n ts y s t e m s ) ，再到八九十年 代的数据仓库和数据挖掘技术( d a t aw a r ea n dd a t am i n i n g ) 等。 数据挖掘技术的产生，来自与这一现实大量庞杂的数据充斥着我们， 包括学习和生活等各个方面。尽管人们投入了大量的人力和物力来收集和存储 这些数据，但实际上这些数据中只有很小部分会被我们利用。这是因为人们在 创建一个数据集时，往往都将精力集中在如何有效地存储、访问这些数据上， 而并没有认真的去思考这些数据最终将怎样分析使用。结果，随着数据的不断 积累，由于缺乏从海量数据中提取有价值知识的工具，那些被收集在大型数据 库中快速增长的数据变成了“数据坟墓”。如何将知识的有价值的信息从海量 数据中挖掘出来? 这就需要数据挖掘技术【i l 。 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用 数据中，提取隐含在其中的、事先不为人知的，但又是潜在有用的信息和知识 的过程【1 1 。 数据挖掘技术从提出到快速发展，在短短的十几年里，已经提出很多有用 的算法和框架，形成了比较完整的体系。然而，近年来许多应用中产生了大量 的、源源不断的数据，数据内部隐藏的模式随着时间的变化发生变化，如电话 通信记录、卫星传感数据、网络监控日志、电子商务记录、入侵检测数据、情 报分析数据、金融服务、股票交易数据。这些数据和传统的存储在数据库中的 数据相比，有很多不同点。首先，他们的速度很快，通常能达到每秒几千条数 据；其次，他们的数据量很大，他们的计量单位通常是t b ，在理论上看，甚至 是无限量大的；再次，数据流会演变，对前部分很高效的算法，可能会随着他 武汉理丁大学硕+ 学位论文 们的演变，变得效果很差；再者，对历史数据的查询访问会变得很困难，查询 开销很大，甚至不太可能。数据流的这些特点，使得传统的挖掘算法，无论是 在时间还是空间复杂度上，都无法满足要求1 2 j 。 一方面，是数据流越来越广泛的应用前景，另一方面却是很难满足应用要 求的传统的挖掘算法；这方面的矛盾，极大地制约着，数据流的应用与发展； 因此，研究和开发出适应数据流特点的挖掘算法，具有极大的现实意义。 1 2 国内外研究现状与分析 由于数据流广泛的应用前景，国内外大量学者对数据流挖掘进行了大量的 研究【3 训，从方向上来分主要做了如下工作：( 1 ) 数据流管理系统( d s m s ，d a t a s t r e a mm a n a g e m e n ts y s t e m ) 的研究( 2 ) 数据流挖掘算法的研究，包括数据流 的聚类、决策树分类、关联规则挖掘等等。 1 2 1 数据流管理系统 相对与数据库管理系统( d b m s ) 的成熟来说，数据流管理系统( d s m s ) 的研究和开发，尚处于实验阶段，还没有产品出现，比较著名的数据流项目主 要有以下几个： ( 1 ) s t a n f o r ds t r e a md a t am a n a g e r 项目畸1 斯坦福桥大学是较早从事数据流管理系统研究的科研机构。s t r e a m 项目 是一个以关系为基础的数据流管理系统，它扩展了s q l 语言在数据流上的处理 功能，开发了连续查询和关系的查询语言。通过特殊的窗口操作项将数据流转换 为关系处理，并将结果转为数据流。通过优化内存和近似查询，该系统能快速处 理易变的、大量涌入的数据流信息，其主要技术包括：连续的自我监控和再优 化；适应于不同需要的良好近似：合理的资源分配和使用。s t r e a m1 o 版本 已经设计完成并正在运行期间，它可以支持多种查询语言。 ( 2 ) a u r o r a 项目】 a u r o r a 系统由布朗大学、布兰代斯大学和麻省理工大学联合开发。该系统 致力于构建一个新型的数据处理系统，其主要目标是处理工作流式监控。a u r o r a 系统结构框架简单，可以处理三种不同的应用：实时监控应用、处理以时间序 列存储的大量历史数据的档案管理型应用和包含对历史以及当前数据进行处理 2 武汉理丁大学硕士学位论文 的跨度应用。 ( 3 ) t e l e g r a p hc q 项目7 1 t e l e g r a p hc q 数据流项目是目前发展时间最长，最成熟的一个数据流管理系 统，由伯克利大学开发。该系统是一个连续查询处理系统，在共享查询评价和 适应性查询处理方面具有优势。 1 2 2 数据流挖掘算法的研究 数据流的挖掘算法1 2 - 3 1 主要包括：数据流的聚类和分类、数据流关联规则挖 掘的研究等等。 1 2 2 1 数据流的聚类分析 在传统数据聚类领域，聚类算法已经相对成熟。如何针对数据流的特点、 选择一种适合的聚类算法是数据流聚类的核心问题。自从2 0 0 0 年首次提出数据 流聚类这一概念之后，这方面的研究己受到广泛的关注。当前对数据流聚类， 研究人员主要从以下几个方面进行研究：利用各种数学方法高效地保留数据流 的特征信息；在传统聚类方法的基础上根据数据流的特点进行增量式改进，将 聚类过程用在线和离线两个进程来实现，高效管理内存信息等等。这些方法都 很难同时保证系统的准确和高效，要在动态数据流中进行快速准确地聚类仍具 有很大的难度。 1 2 2 2 数据流的分类分析 相对与数据流聚类，数据流的分类问题更是难点。在数据流分类方面主要 是p d o m i n g o s 和g h u l t e n 的研究成果【3 l 。目前的研究主要集中在：传统的增量 式的决策树分类，h e o f f d i n gt r e e 和基于它的v f d t ( v e r y f a s td e c i s i o nt r e e ) ， 可调整的v f d t ：c v f d t ( c o n c e p t a d a p t i n gv e r yf a s td e c i s i o nt r e e ) ，使用整 合的技术等等。 1 2 2 3 数据流的关联规则挖掘研究 1 9 9 3 年a g r a w a l 等人首先提出了挖掘顾客交易数据库关联规则问题，以后 很多研究人员都对关联规则的挖掘进行了大量的研究【9 】。他们的工作包括优化原 有的算法以提高算法效率，如引入随机采样、并行的思想等；对关联规则的应 用进行推广。针对数据流模型的研究包括标记取样方法和有损计算，带删除的 武汉理工大学硕士学位论文 频繁项集挖掘、c o u n t i n gb l o o mf i l t e r 方法、考虑f a l s ep o s i t i v e 的方法等等。 1 3 本文的研究内容 本文的主要研究内容是设计出一个符合数据流特点，具有较高的处理速度 和较高准确性的数据流聚类算法。研究的工作主要包括以下几个方面。 首先，回顾了数据库技术的发展，对数据流聚类的必要性做了阐述，研究 并分析国内外数据流处理的发展现状；由于聚类分析算法是数据流聚类的基础， 现有的比较成熟的聚类算法也是本文学习的一个重点，对各种聚类方法的特点 了然于胸是进行下一步工作的基础； 其次，分析数据流的特点，处理数据流的关键技术分析是本文研究的另一 个重点；在这部分中，我们重点研究了数据流的计算模型选择、摘要数据结构 设计、聚类算法的选择和内存的管理等几个关键技术点，并结合现有的数据流 聚类算法，剖析了各个算法的优缺点； 再次，研究并设计基于网格和密度的聚类算法框架，是本文研究的目的， 也是最重要的内容；在这部分中，针对网格密度算法中存在的边缘网格信息缺 失、参数先验知识缺乏、难以进行演化分析等特点，结合了c l u s t r e a m 算法和 c l i q u e 算法中摘要数据结构的特点，改进了摘要数据结构，并在此基础上改进了 在线层算法和离线层的聚类算法，能解决c l u s t r e a m 不能分辨球形聚类和 d s t r e a m 网格信息丢失和历史信息聚类困难的问题。 1 4 本文解决的关键问题 本文所解决的关键问题概括如下： 1 在聚类框架的选择上，借鉴c l u s t r e a m 算法，提出了基于网格和密度的 双层聚类算法框架； 2 在摘要数据结构的设计上，分析了c l u s t r e a m 算法只能分辨球形数据， c li q u e 算法网格信息丢失，难以进行演化分析的原因；并在此基础上改进了原 有的摘要数据结构； 3 在这种摘要数据结构的基础上，改进了在线层算法，比较了新记录到相 关网格的距离，比较好的解决了网格信息丢失的问题； 4 武汉理= 大学硕+ 学位论文 4 在离线层聚类的算法上，充分利用新的摘要数据结构，能很好的进行数 据流上的演化分析，并能解决c l u s t r e a m 算法只能分辨球形数据的问题。 1 5 论文组织结构 本文共分为六章，结构组织如下： 第1 章介绍数据流挖掘的研究背景和意义、国内外研究现状、论文的研究 内容、本文所解决的关键问题以及本文的组织结构。 第2 章对现有的比较成熟的传统聚类算法进行研究并总结比较了不同算法 的适用条件和优缺点。 第3 章对数据流的定义特点进行了阐述，并结合现有的数据流聚类算法分 析了数据流处理中的关键技术点，最后，总结了各数据流聚类算法的优缺点和 产生的原因。 第4 章论述了基于网格和密度的数据流聚类框架，包括摘要数据结构的设 计、在线层的快速读取算法、先下层的演化分析聚类算法等等。 第5 章在第4 章的基础上，对算法进行了实验测试，用以说明算法的适用 性，和准确性。 第6 章对本文的研究工作进行总结并对未来工作做出展望。 武汉理丁大学硕士学位论文 第2 章聚类算法综述 聚类算法是数据流聚类的基础，为了更好的根据数据流的特点，设计合适 的框架和算法，有必要对现有的比较成熟的聚类算法进行总结和归纳，在本章 中，将首先介绍数据挖掘的相关概念和过程，之后介绍各种不同的聚类算法及 其特点。 2 1 数据挖掘 在绪论中，我们已经介绍了数据挖掘技术产生的背景。在本节中，将给出 数据挖掘的定义和处理过程，以便读者对数据挖掘的过程有一个大概的了解。 2 1 1 数据挖掘的定义 随着数据库技术的不断发展及数据库管理系统的广泛应用，数据库中存储 的数据量急剧增大，在大量的数据背后隐藏着许多重要的信息，如果能把这些 信息从数据库中抽取出来，将创造很多潜在的利润，而这种从海量数据库中挖 掘信息的技术，就称之为数据挖掘。 从广义上讲，数据挖掘是指从大量的、不完全的、有噪声的、模糊的、随 机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息 和知识的过程。这个定义包括以下四个层次的含义： ( 1 ) 数据源必须是真实的、大量的、含噪声的； ( 2 ) 发现的是用户感兴趣的知识； ( 3 ) 发现的知识要可接受、可理解、可运用，最好能用自然语言表达发现 结果； ( 4 ) 并不是要求发现放之四海皆准的知识，也不是要去发现崭新的自然科 学定理和纯数学公式，更不是什么机器定理证明，所有发现的知识都是相对的， 是有特定前提和约束条件、面向特定领域的。 从商业角度出发，数据挖掘可以描述为：按企业既定业务目标，对大量的 企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一 6 武汉理t 大学硕士学位论文 步将其模型化的先进有效的方法【1 1 。 2 1 2 数据挖掘的过程 数据挖掘是一个完整的过程，该过程从大型数据库或数据仓库中挖掘先前 未知的、有效的、可实用的信息，并使用这些信息做出决策或丰富知识。在实 施数据挖掘之前，先决定采取什么样的步骤，每一步都做什么，达到什么样的 目标是必要的，有了好的计划才能保证数据挖掘有条不紊的实施并取得成功。 一般地，数据挖掘在任何一个问题上的应用，都可以大致分为三个阶段。 第一阶段，即数据准备阶段，拿到要分析的问题，以及与该问题相关的数 据库。主要步骤包括：数据清理、数据集成、数据变换、数据规约等。 第二阶段，即数据挖掘阶段，借助各种数据挖掘工具，从数据库中找出有 可能解决问题的知识。主要步骤包括：挖掘任务的确定、挖掘技术的选择和挖 掘算法的选择、挖掘数据等等。 第三阶段，结果表现及解释阶段，将发现的知识用于解释当前或历史现象， 预测未来可能发生的情况，使决策者参照从过去发生的事实中抽取的信息进行 决策制定。包括：模式评估和知识表示。 上面三个阶段的工作，在实际运作中，一般都存在反复。也有人把上述整 个过程称为数据库知识发现( 即l d ) ，而仅把第二阶段称为数据挖掘，认为它 是知识发现过程的一个步骤【l0 1 。现在更流行的观念是数据挖掘和数据库知识发 现是等同的，学术界、工业界和媒体等通常不加区别地使用它们。图2 1 给出了 数据挖掘的三个主要阶段及各阶段的相关步骤。 7 武汉理工大学硕士学位论文 据 模式 卜数据准备卜数据挖掘十结果表示与解释叫 2 2 聚类分析 图2 1 数据挖掘过程 从上面的数据挖掘过程中，我们可以看出；挖掘算法对数据挖掘至关重要。 如何选择合适的聚类算法，是数据流聚类的最重要因素之一。 聚类是数据挖掘中的一项重要技术，是一种无监督的学习算法，在本节中 将重点分析比较几种成熟的聚类算法。 2 2 1 聚类分析定义 聚类就是将数据对象分组成为多个簇( c l u s t e r ) ，使得同一个簇中的对象之间 具有较高的相似性( s i m i l a r i t y ) ，而不同簇中的对象具有较大的相异( d i s s i m i l a r i t y ) 。 一个好的聚类方法应产生具有如下特性的聚类结果：簇内的对象具有高度相似 性m i g hi n t r a c l a s ss i m i l a r i t y ) ，而簇间的对象很少相似( 1 0 wi n t e r - c l a s ss i m i l a r i t y ) 。 按照数学定义，聚类分析可以定义如下：在数据空间d 中，数据集x 由许 多数据点( 或数据对象) 组成，数据点x i2 ( ，x f 2 ，) d ，薯的每个属性( 或特 征、或维度) 既可以是数值型的，也可以是枚举型的。数据集x 相当于是一个 n d 矩阵。假设数据集x 中有个对象墨u 。i ，厶州，。聚类的最终目的是把数 8 武汉理工大学硕士学位论文 据集x 划分为七个分割c 胂( 朋= 1 ，2 ，钠，也可能有些对象不属于任何一个分割， 这些就是噪声g 。所有这些分割与噪声的并集就是数据集x ，并且这些分割之间 没有交集，即， j x j 9 y 1 0u 9 ( 2 1 ) ig n c ，= o ( 浮) 这些分割c 卅就是聚类li 1 2 】。 2 2 2 聚类评价标准 要对数据流进行高效聚类，就必须了解聚法好坏的评价标准，具体的评价 一个聚类算法，可以从以下几个方面进行【l 副： ( 1 ) 可伸缩性：聚类算法不只是对含有较少数据对象的数据集有很好的效 果，对大规模数据集同样需要较好的效果。 ( 2 ) 发现任意形状的聚类：基于欧氏距离的聚类算法只对球状数据集比较 敏感，为了发现任意形状的数据集，需要对算法进行改进或引入基于密度的聚 类算法。 ( 3 ) 用于决定输入参数的领域知识最少：很多聚类方法在聚类分析中要求 用户输入一定的参数，例如，k - m e a n s 算法中希望产生类的数目，密度算法中稠 密度的阈值等等。一般而言，聚类结果对于输入参数十分敏感。参数通常很难 确定。要求用户输入参数不仅加重了用户的负担，也使得聚类的质量难以控制。 如何较少参数领域知识，是设计聚类算法时必须考虑的问题。 ( 4 ) 对于输入数据的顺序不敏感：对于某些聚类算法，对同一个数据集， 当以不同的顺序提交给时，可能生成差别很大的聚类结果。如何减少算法对数 据集的顺序依赖性，是设计算法时要考虑的。 ( 5 ) 高维性：许多聚类方法擅长处理低维的数据，比如二维或三维。在高 维空间中聚类数据对象是非常有挑战性的，特别是这样的数据可能非常稀疏， 而且高度偏斜。同时高维数还给聚类分析带来两个问题：首先，不相关的属性 削弱了数基于网格密度与空间划分树的聚类算法研究据汇聚的趋势。其次，高 维使得在低维中很有效的区分数据的标准在高维空间中失效了。 ( 6 ) 处理噪声数据的能力：绝大多数现实世界中的数据都包含了各种噪音 比如：孤立点，空缺，未知数据或错误的数据。这样的数据可能为降低聚类算 9 武汉理工大学硕士学位论文 法的准确性，因此需要加强算法对噪声的鲁棒性。 ( 7 ) 处理不同类型属性的能力：许多聚类方法只能聚类数值类型的数据。 但是，实际应用中的数据对象己远远超出关系型数据的范畴。 ( 8 ) 基于约束的聚类：现实世界中的应用可能需要在各种约束条件下进行 聚类。要找到既满足特定的约束，又具有良好聚类特性的数据分组是一项具有 挑战性的任务。 ( 9 ) 可解释性和可用性：用户希望聚类结果是可解释的、可理解的、可用 的。也就是说，聚类可能需要和特定的语义解释和应用相联系。 2 3 常见聚类算法及其特点 聚类分析是数据挖掘中重要的一个研究方向，它可以是分类算法是预备工 作，也可广泛应用于各领域。经过多年的研究，大量聚类算法涌现出来，我们 很难对其进行一个简介的分类；根据其特征，大体可以分为以下几类：划分方 法、层次方法、基于密度的方法、基于网格的方法和基于模型的方法等等【1 4 l 。 2 3 1 划分的方法( p a r t i t i o n i n gm e t h o d ) 基于划分的聚类方法的基本思想是：通过一步划分产生所有的簇，然后在 这些簇上逐步迭代以达到最优解。他包括初始划分和迭代求解两个过程。 在初始划分阶段，通常采用随机方式。从n 个对象中，构建k 个划分，七刀。 同时满足如下的要求：( 1 ) 每个组至少包含一个对象；( 2 ) 每个对象必须属 于且只属于一个组。注意在某些模糊划分技术中，第二个要求可以放宽。一个 好的划分的一般准则是：在同一个类中的对象之间尽可能“接近”或相关，而 不同类中的对象之间尽可能“远离”或不同。 在最优解搜索阶段，为了达到全局最优，基于划分的聚类会要求穷举所有 的划分，但由于可能解数量非常多，通常采用启发式的迭代，尝试通过对象在 划分间移动来改进划分。比较流行的算法有k - m e a n s 算法【l5 j 和k - m e d o i d s 算法【1 6 】 在k - m e a n s 算法中，每个簇用该簇中对象的平均值来表示。而在k - m e d o i d s 算法中，每个簇用接近聚类中心的一个对象来表示。k - m e d o i d s 算法是为了解决 k - m e a n s 算法对噪声点太敏感而做出的改进，当然这付出了更高计算复杂度的代 价。 l o 武汉理工大学硕士学位论文 基于划分的方法，有计算比较快速、用户可以设定迭代终止阀值、和想要 的聚类个数等优点。但是类似k - m e a n s 算法、k - m e d o i d s 算法都是基于空间距离 的，这使得他们在处理非球状的数据集时，效果不佳。再者，他们对领域知识 要求比较高，一般用户很难准确设定划分的聚类个数。 2 3 2 层次的方法( h i e r a r c h i c a lm e t h o d ) 与划分聚类方法不同，层次聚类算法对给定的数据集进行层次的分解，直 到满足终止条件为止；步骤大概包括：相似度计算和层次分解两个阶段。根据 层次的形成过程，层次方法可以分为凝聚( a g g l o m e r a t i v e ) 方法和分裂 ( d i v i s i v e ) 方法。凝聚聚类方法将每个对象作为一个簇，然后将相互邻近的簇 合并为一个大簇，直到所有的对象都在一个簇中，或者某个终结条件被满足。 与凝聚的层次聚类相反，分裂聚类方法首先将所有对象置于一个簇中，然后逐 渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终结条件。 在层次聚类算法中，最大的困难就是合并或分类点的选择。这种选择相当 关键，这是因为该过程是不可逆的；一旦一组对象被合并或者分裂，下一步的 处理将在新生成的簇上进行。已做的处理不能被撤消，聚类之间也不能交换对 象。如果在某一步没有很好地选择合并或分裂的决定，可能会导致低质量的聚 类结果。而且，这种聚类方法不具有很好的可伸缩性，因为合并或分裂的决定 需要检查和估算大量的对象或簇。 为改进层次聚类效果，通常将层次聚类与其他聚类技术结合，形成多阶段 聚类方法。典型的层次聚类算法有b i r c h 算法，c u r e 算法等。 ( 1 ) b i r c h 算法【1 7 1 ( b a l a n c e d i t e r a t i v er e d u c i n ga n dc l u s t e r i n gu s i n g h i e r a r c h i e s ) b i r c h 算法是一种大型数据库聚类算法，由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 l u s t e r i n gf e a t u r ec f ) 和聚类特征树( c f 树) 。c f 定义为一个三元组c f = ( n ，l s ，s s ) ，其中是子簇中 的点数，l s 是个点的线性和，鼹是个点的平方和。c f 可以对簇信息进行 概括，是对给定子簇的统计汇总，因此c f 是计算聚类和利用存储的关键度量。 一棵c f 树是高度平衡的树，其中存储了层次聚类的c f 信息，每个中间节点存 储了其孩子节点的c f 总和。b i r c h 算法的主要步骤如下： 武汉理工大学硕士学位论文 1 扫描数据集，建立一棵初始存放于内存的c f 树。算法试图使c f 树在内 存许可范围内尽可能详细地反映数据集的聚类信息。为此，算法将密集的数据 点分组成为子簇，而将稀疏的数据点作为孤立点去除，并利用得到的数据总结， 构建c f 树。 2 有选择地压缩。对初始c f 树中的叶条目进行扫描，重建一棵更小的c f 树，同时去掉多余的孤立点，并将比较密集的子簇组合成更大的子簇。 3 采用一个已有的全局或半全局的聚类算法对c f 树中所有跨不同节点边界 的叶条目进行聚类。 4 有选择地对聚类结果提炼。将3 产生的簇质心作为种子，将数据点重新 分配给距离其最近的种子，以得到一个新的聚类集合，从而更正了不精确的地 方，提炼出更好的聚类结果。 b i r c h 算法以一种紧凑的压缩格式存放大型数据集，然后直接在压缩的数 据集( 而不是原始的数据集) 上进行聚类，其i o 成本与数据集的大小呈线性关系。 b i r c h 特别适合大数据集，由于c f 结构的可加性，算法支持增量聚类或动态 聚类。算法扫描数据集一遍就可生成较好的聚类，增加扫描次数可用来进一步 改进聚类质量。但由于b i r c h 算法用半径的概念来控制簇的边界，因而不能很 好的识别非球形的簇。再者，b i r c h 算法对数据集到达顺序比较敏感。 ( 2 ) c u r e 算法1 1 8 1 ( 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 ) c u r e 算法由g u h a ，r a s t o g i ，s h i m 等人提出，致力于解决大多数聚类算法 偏好球形和难以处理异常点的问题。与b i r c h 算法不同，c u r e 算法选用数据 空间中固定数目的、具有代表性的点代表簇，然后根据一个特定的分数或收缩 因子向簇中心“收缩 或将其移动。如果两个簇的代表点距离最近，则将这两 个簇合并。由于每个簇有一个以上的代表点，使c u r e 算法可以适应非球形的 几何形状，而且簇的收缩或凝聚可以控制异常点的影响，因此c u r e 算法对异 常点的处理更健壮。对于大型数据库，c u r e 算法有良好的伸缩性，不会降低聚 类的质量。c u r e 算法的主要处理步骤如下： 1 从数据集中抽取一个随机样本s ，包含s 个对象。 2 将样本s 划分为p 分区，每个划分大小为s p 。 3 对每个划分，利用层次算法局部聚类成( s p ) q 聚类，其中q 1 。 4 删除异常点。利用两种不同的技术删除异常点。第一种技术是将增长缓慢 的簇删除，第二种技术是，在聚类的最后阶段，将非常小的簇删除。 1 2 武汉理工大学硕士学位论文 5 对局部的簇进行再聚类，落在每个新形成的聚类中的代表点，则根据用户 定义的收缩因子a 收缩或向簇中心移动。这些点将用于代表并描绘出聚类的边 界。 6 对簇中的数据标记上相应簇标记。 c u i 迮算法的最大问题是无法处理分类属性。 2 3 3 基于密度的方法( d e n s i t y b a s e dm e t h o d ) 在基于划分和层次的聚类算法中，都对对象进行相似性度量，而大部分的 相似性度量都是基于距离的。这些算法只能发现规则的球状数据集合。为了能 发现任意形状的簇，研究人员提出了基于密度的聚类算法。其基本思想就是： 只要临近区域的密度( 对象或数据点的数目) 超出某个阀值，就继续聚类。也就 是说，对给定类中的每个数据点，在一个给定范围的区域中必须包含一定数目 的点。这样的方法可以用来过虑“噪音 孤立点数据，发现任意形状的簇。 基于密度的聚类算法的典型代表是d b s c a n 算法。 d b s c a n t l 9 1 ( d e n s i t y - b a s e ds p a t i a lc l u s t e r i n go fa p p l i c a t i o n sw i t h n o i s e ) 通过不断生长高密度区域来进行聚类，它能从含有噪声的空间数据库中 发现任意形状的聚类。d b s c a n 方法将一个聚类定义为一组“密度相连”的点集。 d b s c a n 算法建立在以下核心概念上： ( 1 ) 占邻域：给定对象半径s 内的区域称为对象的s 邻域。 ( 2 ) 核心点：一个对象的占邻域至少包含最小数目( m i n p t s ) 个对象，则 称该对象为核心点。 ( 3 ) 直接密度可达：即给定一组对象集合d ，如果p 是在q 的s 邻域内， 而q 是一个核心点，则称对象p 从对象q 出发是直接密度可达的。 ( 4 ) 密度可达：如果存在一个对象链a ，p 2 ，凤，a = g ，以= p ，对于 p i d ( 1 f n ) ，只+ l 是从只关于占和m i n p t s 直接密度可达的，则对象p 是从对 象q 关于s 和m i n p t s 密度可达的。 ( 5 ) 密度相连：如果对象集合d 中存在一个对象0 ，使得对象p 和q 是从0 关于s 和m i n p t s 密度可达的，则对象p 和q 是关于和m i n p t s 密度相连的。 ( 6 ) 边界点：非核心点，是从某一核心点直接密度可达的。 d b s c a n 算法的主要步骤如下： 1 从数据对象集合d 中选择一个对象p 。 武汉理工大学硕+ 学位论文 2 根据用户输入参数m i n p t s 和占，搜索从p 可以密度可达的所有点。 3 如果p 是核心点，建立一个新簇。 4 如果p 是边界点，并且p 的密度可达点集为空，算法选择数据对象集合 中的另一个对象。 5 重复上述过程，直到数据对象集合d 被完全处理。 如果用户定义的参数设置恰当，该算法可以有效地找出任意形状的聚类。 d b s c a n 算法的计算复杂度是o ( n 2 ) ，如果采用空间索引，计算复杂程度可以 优化到o ( n l o g 疗) ，其中n 是数据库中对象的数目。 分析d b s c a n 算法，我们可以发现一个问题：d b s c a n 算法对全局的数据集使 用统一的参数占和m i n p t s ；这对密度分布不均匀的数据集显然不合适。为了解 决这个问题，a n k e r s t ，m b r e u n i g 等人提出了o p t i c s 【2 u j ( o r d e r i n gp o i n t st o i d e n t i f yt h ec l u s t e r i n gs t r u c t u r e ) 聚类分析方法。 o p t i c s 算法建立在两个核心概念，核心距离( c o r ed i s t a n c e ) 和可达距离 ( r e a c h a b l ed i s t a n c e ) 上： ( 1 ) 核心距离( c o r ed i s t a n c e ) ：一个对象p 的核心距离是使得p 成为核 心对象的最小占。如果p 不是核心对象，p 的核心距离没有定义。 ( 2 ) 可达距离( r e a c h a b l ed i s t a n c e ) ：一个对象q 关于另一个对象p 的可 达距离是p 的核心距离和p 与g 的欧几里德距离两者中的较大值。如果p 不是核 心对象，p 和q 之间的可达距离没有定义。 在以上概念上，o p t i c s 通过覆盖几乎所有的s 值来计算密度连通类从而进 行类似于d b s c a n 的延伸算法一样的聚类操作。与d b s c a n 不同的是，它仅为自 动和交互的聚类分析计算一个簇次序而不产生明确的簇。这个次序代表了数据 的基于密度的聚类结构。它包含的信息，等同于从一个宽广的参数设置范围所 获得的基于密度的聚类。 o p t i c s 算法创建了数据库中对