（管理科学与工程专业论文）基于分形的数据流聚类算法研究.pdf

基于分形的数据流聚类算法研究 摘要 数据流由一系列有序到达的、趋于无限的、动态的数据组成。现实世界和 工程实践产生了大量的数据流，这种数据不同于传统的静态数据，对其进行有 效处理和挖掘遇到了极大的挑战。传统数据挖掘算法在支持数据流挖掘时所表 现出来的局限性已被广泛认识，这也促进了对改进现有数据挖掘算法和构建新 的数据流挖掘算法的研究。如何利用有限存储空间进行聚类是数据流挖掘的重 要问题，具有非常重要的研究价值和实践意义，已经引起了国内外研究者的广 泛关注。 本文对分形理论和经典数据流聚类算法进行了系统的研究和全面的总结， 在此基础上提出了一种新的基于分形的数据流聚类算法。 首先，本文介绍了数据挖掘、分形、聚类的基本知识和一些经典的数据流 聚类算法。然后，提出了基于分形的数据流聚类算法，利用分形维数的变化程 度来度量数据点与聚类的自相似程度，在噪音干扰下能发现反映数据流自然聚 集状态的任意形状的聚类。实验证明，f c l u s t r e a m 算法是一种高效的数据流聚 类算法。最后对f c l u s t r e a m 算法进行了全面的总结和论述，并讨论了存在的主 要问题和未来的研究方向。 关键词：数据挖掘；数据流；分形；分形维数；聚类 r e s e a r c ho nt h ea l g o r i t h mo ff r a c t a lc l u s t e r i n gd a t a s t r e a m a b s t r a c t d a t a - s t r e a mc o n s i s t so fas e r i e so fo r d i n a lc o m i n g ，b o u n d l e s s ，d y n a m i c d a t a r e a l - w o r l da p p l i c a t i o n so f t e ng e n e r a t eh u g ea m o u n to fd a t as t r e a m s i d e ，w h i c h c h a l l e n g e se f f i c i e n tp r o c e s s i n ga n dm i n i n gd u et oi t ss p e c i a lc h a r a c t e r i s t i c s t h e d i s a d v a n t a g e so ft r a d i t i o n a ld a t am i n i n ga l g o r i t h m si nm i n i n gd a t a s t r e a mi s i n d i c a t e db ym a n yr e s e a r c h e r s ，m e a n w h i l e ，t h e s ed i s a d v a n t a g e sa l s op r o m o t et h e r e s e a r c h e so fi m p r o v i n go fe x i s t i n gd a t am i n i n g a l g o r i t h m sa n dc r e a t i n gn e w d a t a 。s t r e a m m i n i n ga l g o r i t h m s a s a i m p o r t a n tp r o b l e mi n d a t as t r e a m m i n i n g ，c l u s t e r i n gt e c h n i q u ee m p l o y e di nt h e s ea p p l i c a t i o n ss h o u l db ee f f e c t i v ei n t e r m so fs p a c eu s a g e t h i sh a sr e c e i v e dc o n s i d e r a b l ea t t e n t i o ni nt h ep a s tf e w y e a r s d u et oi t sr e s e a r c hv a l u ea n di n c r e a s i n ga m o u n to fi m p o r t a n t a n c ei nn u m e r o u s a p p l i c a t i o n s i nt h et h e s i s ，f r a c t a la n ds o m ec l a s s i c a la l g o r i t h m sf o rc l u s t e r i n gd a t as t r e a m h a v eb e e ns y s t e m a t i c a l l ys t u d i e da n dc o m p r e h e n s i v e l ys u m m a r i z e d o nt h eb a s i co f p r e v i o u sr e s e a r c h ，t h en o v e la l g o r i t h m sf o rf r a c t a lc l u s t e r i n gd a t as t r e a ma r e p r o p o s e d f i r s t l y ，t h et h e s i si n t r o d u c e ss o m eb a s i ck n o w l e d g eo fd a t am i n i n ga n df r a c t a l a n dc l u s t e r i n ga n ds o m ec l a s s i c a la l g o r i t h m sf o rc l u s t e r i n gd a t as t r e a m s e c o n d l y , t h et h e s i sp r e s e n ta na l g o r i t h mw h i c hi sb a s e do nf r a c t a lt oc l u s t e rd a t as t r e a ma n d u s e st h ec h a n g eo ff r a c t a ld i m e n s i o nt om e a s u r et h es e l f - s i m i l a r i t yb e t w e e nd a t a a n dc l u s t e r s w i t hn o i s yc o n d i t i o n ，t h ea l g o r i t h mc a nd i s c o v e r a r b i t r a r ys h a p e c l u s t e r st h a tr e f l e c tt h en a t u r a lg r o u ps t a t u so fd a t as t r e a m t h ee x p e r i m e n t ss h o w t h eg o o dp e r f o r m a n c ea n de f f e c t i v i t yo ff c l u s t r e a m f i n a l l y , t h et h e s i sc o n d u c ta c o m p r e h e n s i v es u m m a r ya n dd i s c u s s i o no ff c l u s t r e a m t h em a i np r o b l e m so f f c 】u s t r e a ma n df u t u r er e s e a r c hd i r e c t i o n sa r ed i s c u s s e d k e yw o r d s ：d a t am i n i n g ；d a t as t r e a m ；f r a c t a l ；f r a c t a ld e m e n s i o n ；c l u s t e r i n g i i 插图清单 图1 1 传统数据处理模型与数据流处理模型的比较4 图2 1 三次k o r c h 曲线1 0 图3 1 数据流聚类算法的发展与演化示意图2 2 图3 2 分而治之思想示意图2 3 图3 3 数据流滑动窗口示意图2 4 图3 4 金字塔时间窗口快照示意图2 5 图3 5s t r e a m 算法聚类示意图2 8 图3 6e s t r e a m 数据流聚类算法主框架3 0 图4 1f c l u s t r e a m 算法与d g s t r e a m 算法聚类有效性比较3 9 表格清单 表3 1 聚类算法的比较2 l 表4 1f c l u s t r e a m 聚类情况表3 8 v i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 金目曼王些太堂 或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意。 学位论文作者签名：呵z 欠签字日期：砌7 年 r 。日 学位论文版权使用授权书 本学位论文作者完全了解金月巴工些太堂有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授 权金罡王些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位做作者签名2 可 婵醐：冲垆川泪 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名：e 弧七诬 签字日期：渊年9 月c 一日 电话： 邮编： 致谢 值此论文完成之际，我谨向所有关心和帮助过我的老师、家人、同学以及 朋友致以最真诚的谢意! 首先，我要特别感谢我的导师倪志伟教授和张公让副教授。倪老师治学严 谨，学识渊博，对学生严格要求，使我在研究生学习中不断进步，而且对我的 生活和工作也关心备至。张老师在工作学习中给予了我最大的支持和帮助。两 位老师不仅给我提供了良好的学习研究环境和实习机会，还在培养我的科研能 力方面不遗余力。本论文从选题、研究、实验开发、修改到相关小论文的发表 无不渗透着两位老师的智慧和心血。倪老师踏踏实实研究学问的态度和智慧使 我在学业上受益匪浅，也深深地影响着我。在此，谨向我的二位导师致以最崇 高的敬意和衷心的感谢! 我要感谢师兄王超、潘永刚、忻凌、李伟东、师姐倪丽萍、杨葛钟啸、胡 汤磊、梁敏君、吴姗、郑盈盈、高雅卓和王丽红在我论文期间所提供大量的帮 助。你们的无私帮助才使本文得以顺利完成。 感谢合肥工业大学管理学院智能管理研究所的同学们，正是在和你们的交 流和帮助下，我才得以不断提高，衷心地祝愿你们学业有成、前程似锦! 最后，我要感谢我的家人，感谢他们二十多年来给予我在学习和生活方面 的支持和鼓励，使我能够安心学习，顺利完成学业! 这份论文是我给你们的礼 物。 作者：罗义钦 2 0 0 9 年3 月2 9 日 第一章绪论 1 1 论文研究背景和意义 在信息技术高度发达的今天，各种各样的系统积累了大量的数据。这些数 据背后隐藏着许多有用的重要信息。如何发掘出这些有用的信息，对这些信息 进行更高层次的分析，使这些信息为决策服务成为人们关心的问题。通常，由 于数据量太大，无法使用传统的数据分析工具和技术处理它们。有时，即使数 据集相对较小，由于数据本身的非传统特点，也不能使用传统的方法处理。在 另外一些情况下，需要回答的问题不能使用已有的数据分析技术来解决。这样 就需要新的方法。数据挖掘是一种技术，它将传统的数据分析方法与处理大量 数据的复杂算法相结合。数据挖掘为探查和分析新的数据类型以及新方法分析 旧有数据类型提供了令人振奋的机会。数据挖掘方法的提出，最终使人们有能 力认识到数据的价值所在。什么是数据挖掘呢? 数据挖掘( d a t am i n i n g ) t l j 指的 是从大型数据库或数据仓库中提取人们感兴趣的知识，这些知识是隐含，的、 潜在的、事先未知的有用信息。数据挖掘能在大型数据存储库中，自动地发现 有用信息，发现前所未有的有用模式。数据挖掘还具有预测未来观测结果的能 力。一般地，数据挖掘的技术可分为以下6 种：关联规则发现，序列发现，时 序发现，离群分析，分类，聚类等。虽然数据挖掘技术在各个领域都得到应用 和长足的发展，但是自它诞生之日起，来自现实世界的挑战一直伴随着它。当 面临新的数据集提出的挑战时，传统的数据分析技术常常遇到实际困难。引发 对数据挖掘的研究的挑战包括以下几个方面【2 j ： ( 1 ) 可伸缩性 。 由于数据产生和搜集技术的进步( 如网络技术) ，数吉字节、数太字节甚 至数拍字节的数据集越来越普遍。如果数据挖掘要处理这些海量数据集，则算 法必须是可伸缩的。许多数据挖掘算法使用特殊的搜索策略处理指数性搜索问 题。可伸缩性还需要实现新的数据结构，以有效的方式访问个别记录。 ( 2 ) 高维性 现在，常常遇到数以百计或数以千计属性的数据集，而不是数十年前常见 的只有少数属性的数据集。在生物信息学领域，微阵列技术的进步已经产生了 涉及数千特征的基因的基因表达数据。具有时间或空间分量的数据集也趋向于 具有很高的维度。例如，考虑包含不同地区的温度测量的数据集。如果温度在 一个相当长的时间周期内重复地测量，则维度的增长正比于测量的次数。为低 维数据开发的传统的数据分析技术通常不是很好地处理这样的高维数据。此 外，对于某些数据分析算法，随着维度的增加，计算复杂性迅速增加。 ( 3 ) 异常数据和复杂数据 通常，传统的数据分析方法只处理包含相同类型属性的数据集，或者是连 续的，或者是分类的。随着数据挖掘在商务、科学、医学和其他领域的作用越 来越大，越来越需要能够处理异种属性的技术。 ( 4 ) 数据的所有权与分布 有时，需要分析的数据并非存放在一个站点，或归属一个单位，而是地理 上分布在属于多个机构的资源中。这就需要开发分布式数据挖掘技术。分布式 挖掘技术要面临的挑战包括：1 ) 如何降低执行分布式计算所需的通信量?2 ) 如何有效地统一从多个资源得到的挖掘结果。3 ) 如何降低数据安全性问题? ( 5 ) 非传统分析 传统的统计方法基于一种假设一一检验模式；换句话说，提出一种假设， 设计实验来收集数据，然后针对假设分析数据。但是，这是一个劳力费神的过 程。当前的数据分析任务常常需要产生和评估数以干计的假设，因此希望自动 地产生和评估假设导致了一些数据挖掘技术的开发。此外，数据挖掘所分析的 数据集通常不是精心设计的实验的结果，并且它们通常代表数据的时机性样 本，而不是随机样本。而且，这些数据集常常涉及非传统的数据类型和数据分 布。 为了迎接这些挑战，来自不同学科的研究者汇集在一起，开始着手开发可 以处理不同数据类型的更有效的、可伸缩的工具。这些工作建立在研究者先前 使用的方法学和算法之上，在数据挖掘领域达到高潮。特别地，数据挖掘利用 了来自下面的思想：1 ) 来自统计学的抽样、估计和假设检验；2 ) 人工智能、 模式识别和机器学习的搜索算法、建模技术和学习理论。数据挖掘也迅速地接 纳包括最优化、进化计算、信息论、信号处理、可视化和信息检索等领域的思 想。 作为数据挖掘重要技术之一的聚类【3 】是数据预处理的重要手段和数据挖掘 的基础工具。它是将物理或抽想对象的集合依据对象之间某种相似性度量分成 多个集合，其中属于同一集合的对象彼此相似，属于不同集合的对象彼此相异。 空间形状的相似性、空间距离的接近性、聚类整体分布的相似性以及它们之间 综合等都是对象之间相似性的表现。聚类分析将数据划分成有意义或有用的组 ( 簇) 。如果目标是划分成有意义的组，则簇应当捕获数据的自然结构。然而， 在某种意义下，聚类分析只是其他目的( 如数据汇总) 的起点。无论是旨在理 解还是实用，聚类分析在广泛的领域扮演着重要的角色。这些领域包括：心理 学和其他社会科学、生物学、统计学、模式识别、信息检索、机器学习和数据 挖掘。 分形理论是现代非线性科学研究中一颗耀眼的新星。分形理论【4 】的本质在 于局部与整体之间的自相似性，将一个复杂现象看成是由简单对象迭代而成， 从而揭示复杂现象中所蕴含的规律和特性，特别适合解决复杂问题。分形理论 不但适用于描述自然界中的复杂的形状，而且已经被成功运用于给定数据集的 建模和压缩、图像处理、信号处理等领域。近几年，有研究表明分形维数在数 据挖掘领域能够更好地克服传统数据挖掘技术的不足，更加有效地解决在结构 复杂、高维数据集上的数据挖掘问题。作为分形理论的重要描述的分形维数也 已成为一种新的相似性度量出现在聚类算法【5 j 中。 3 0 多年来，数据库的技术发展非常迅速而且得到广泛的应用。一方面，数 据建模形式多样，从层次数据库、网状数据库、关系数据库、对象数据库，直 到关系对象数据库等等；另一方面，数据规模也越来越大。传统数据库技术的 一个共同点是：数据存储在介质中，可以多次利用：用户提交数据操纵语言 ( d m l ) 来获取查询结果。尽管传统数据库获得了巨大的成功，但是在2 0 世 纪末，一种新的应用模型数据流对它提出了挑战。面向数据流的服务广泛 出现在众多领域，例如金融应用、网络监视、通信数据管理、w e b 应用、传感 器网络数据处理等等。数据流【6 】由一系列按序到达的数据组成，也可看作是信 息传输过程中经编码处理的数字信号串。令t 表示任一时间戳，表示在该时间 戳到达的数据，流数据可以表示成 口h ，口；，a ，数据流模型区别于传统 数据应用模型在于： ( 1 ) 数据的实施到达； ( 2 ) 数据到达的次序相互独立，不受应用系统的影响； ( 3 ) 数据规模宏大，不能预知数据的最大值； ( 4 ) 数据经过处理后，除非特意保存，否则不能被重复取出利用，或者 代价昂贵。 数据流自身的特点给数据挖掘算法带来了巨大的挑战，传统技术难以满足 实时要求。图1 1 显示了传统数据处理技术和数据流处理技术的差异。从图1 1 可以看出，传统的数据处理技术将所有的数据存放到数据库或者数据仓库中； 系统响应用户提交的d m l 语句，搜索数据存储媒介，返回查询结果。当数据 规模很大时，数据往往以磁盘或者磁带为介质，因而执行查询操作需要大量的 i o 操作，效率低下，不能适应实时系统的需求。相反，新的数据流处理技术 仅维护一个远小于其规模的概要数据结构，从而能够常驻内存。数据流处理技 术往往包含两部分算法，一部分监控流中的数据，更新概要数据结构；另一部 分响应用户查询要求，返回近似查询结果。从传统数据处理模型与数据流处理 模型的差异和数据流自身的特点可以看出，研究新的数据流挖掘算法具有重要 的科学意义和现实意义。 本文所要讨论的问题主要集中在数据流的聚类算法上。数据流的聚类分析 得到的附加结果是对每个类的综合描述，这对更进一步深入分析数据流的特性 是尤其重要的。因此，展开对数据流的聚类算法的研究具有重要的意义。 ( b ) 数据流处理模型 图1 i 传统数据处理模型与数据流处理模型的比较 1 2 国内外研究现状 近年来，越来越多的领域产生了数据流的应用，它不同于传统的存储在磁 盘上的静态的数据，而是一类新的数据对象，它是连续的、有序的、快速变化 的、海量的数据。典型的数据流包括网络与道路交通监测系统的监测信息数据、 电信部门的通话记录数据、由传感器传回的各种监测数据、股票交易所的股票 价格信息数据以及环境温度的监测数据等。数据流分析是数据流研究的一个重 要方向，目前的研究主要包括数据流聚类、分类、频繁模式以及数据流o l a p 世 号手。 二十世纪末期，国外开始了数据流的研究热潮，目前已有一些系统项目问 世，如通用流系统等。但在数据模式和查询语言中加入时间、顺序、窗口；实 现近似计算操作的方法如滑动窗口技术等；设计可以重新优化的适应性查询； 适合于流操作的调度策略；分布式查询的处理，数据流挖掘等热点问题，尚没 有产品原型出现【_ 7 1 ，需要进一步研究。近几年来，数据流问题开始受到国内学 者关注，但与国外的研究相比尚处于起步阶段【8 ，9 】。 最近几年，数据流处理技术发展非常快。一方面，出现了很多数据流模型 下的管理系统，即数据流管理系统( d a t as t r e a mm a n a g e m e n ts y s t e m ，简称 d s m s ) ，包括斯坦福大学的s t r e a m 项刚1 0 】、施乐公司的t a p e s t r y 项目、 加州大学伯克利分校的t e l e g r a p h 项目1 1 2 , 1 3 、布朗大学和麻省理工大学合作的 型 一划一 模 一烫一 理 一艇一 处l 二l 据 叫一 = 一 a u r o r a 项目【l4 j 等，这些系统针对具体行业背景，给出了较全面的数据管理解决 方案；另一方面，基于数据流模型的数据挖掘技术也发展迅速，包括做聚类分 析【15 1 、决策树分析【1 6 , 1 7 】、密度估计【1 8 1 等等。下面对本文研究的主要方向一一数 据流聚类的发展做详细的介绍。 l o c a l s e a r c h 数据流聚类算法i l9 j 基于分治的思想使用一个不断的迭代 过程实现利用有限空间对数据流进行k m e a n s 聚类。s t r e a m 算法【2o 】发展了 g u h a 的l o c a l s e a r c h 的思想，并利用s s q 证明在多种情况下，s t r e a m 算法的聚类效果要比b i r c h 好。但这两种算法都只能提供对当前数据流的一 种描述，而不能反映数据流的变化情况。 c l u s t r e a m 算法1 2 l j 提出了一个优秀的解决数据流聚类框架。它使用了两个 过程来处理数据流聚类问题：首先，使用一个在线的微观聚类过程对数据流初 步聚类，并按照一定的时间跨度将聚类结果按金字塔时间结构存储，以便进行 离线的分析。同时，使用一个离线的宏观聚类过程，根据用户的要求对宏观聚 类过程的聚类结果进行再分析。但它采用距离作为相似度度量，聚类结果通常 是球形的，不能支持任意形状的聚类。a g g a r w a l 等又提出了h p s t r e a m 算法框 架1 2 引。h p s t r e a m 针对高维数据流，较之c l u s t r e a m 的不足也做了相应的改进。 d e n s t r e a m 算法【2 3 能够对有噪声的动态进化数据流进行任意形状的聚类。 它的缺点是由于采用了全局一致的绝对密度作为参数，造成了对参数十分敏 感，同时不能反映用户指定时间跨度内的数据流的变化情况。 a c l u s t r e a m 聚类算法【2 4 】是基于密度与空间的数据流聚类算法。它通过引入 有严格空间的意义聚类块，尽量保留数据的空间特性，有效克服c l u s t r e a m 算 法不能对任意形状聚类的缺陷。它的缺点是在处理不属于已有聚类块的新数据 点时误差较大，同时不能区分密度等级不同的簇。 基于网格的g c l u s t r e a m 算法【25 】是借鉴了c l u s t r e a m 算法的两阶段聚类的框 架和p y r a m i dt i m ef r a m e 的存储结构，采用相对密度作为聚类参数，通过对数 据流进行网格处理，能在噪声条件下发现任意形状的聚类。它的缺点是对于处 理高维空间中的分布稀疏、噪声难以区分的数据流的聚类结果不好，需要进行 降维处理。 而在分形理论与数据挖掘结合的方面，这方面的研究也比较活跃。虽然分 形是2 0 世纪末的一门新兴学科，但是自从它诞生以来，已经有许多学者发现 它的独特之处，将它与数据挖掘结合起来，得到了很好的结果。t r a i n a 在2 0 0 0 年提出了基于分形维数的特征属性选择方法【26 1 。b a r b a r d 于2 0 0 0 年首先提出了 基于分形的f c ( f r a c t a lc l u s t e r i n g ) 聚类算法，分析了f c 算法的时间和空间复杂 度。针对合成与实际数据机的实验结果显示，f c 算法具有较好的可扩展性， 与b i r c h 及c u r e 等聚类方法的实验对比中，f c 算法表现出了相对优良的聚 类结果。f c 算法具有发现任意形状聚类及增量聚类的特点。最为典型的基于 分形维数的关联规则挖掘算法【2 7 1 也是由b a r b a r d t 等人在2 0 0 0 年提出。在分类与 预测方法上，基于分形维数分类与预测方法【2 8 枷】上也得到了长足的发展。如 r a l p hh i p p e n s t i e l 等人结合分形维与神经网络对数字信号进行了分类。 1 3 论文的工作与组织结构 1 3 1 论文的工作 本文主要工作包括以下几个方面： 首先对分形理论、分形维数及分形维数在数据挖掘上的应用进行研究，并 提出进一步研究的方向； 其次，对聚类算法和数据流聚类算法进行系统的研究和全面的总结； 再次，在前面的研究基础上提出一种新的基于分形的数据流聚类算法，并 对算法进行了实验，证明算法的有效性和可行性，以及对算法进行了时空复杂 性的分析； 最后对全文进行总结，对本文的工作和不足进行阐述，并指出未来研究需 要努力的方向和展望。 本文工作的主要价值体现在提出了一种基于分形的数据流聚类算法。这是 首次分形与数据流结合的聚类算法。本文将在主要章节详细介绍s i d 方法如何 计算数据流中分形维数，并在这基础上结合数据流的特点和c l u s t r e a m 算法提 出的数据流聚类的框架，提出了f c l u s t r e a m 算法，然后用程序对算法进行了实 现和实验检验算法的有效性，给出了与d g s t r e a m 算法的性能比较结果，并分析 了算法的时空复杂度。 1 3 2 论文的组织结构 围绕着上述研究工作，本文的组织结构如下。 第一章：绪论。首先，本文会着手介绍数据挖掘的概念、数据挖掘技术的 分类和数据挖掘所要面临的、也是与本文的所要研究的领域一一数据流密切相 关的挑战，接着介绍聚类技术的特点和应用背景以及分形理论的地位、本质和 在数据挖掘领域的应用背景，最后介绍数据流、数据流与众不同的特点和数据 流处理模型，通过与传统数据处理模型的对比，显示出本文研究的重要意义和 作用。其次，简单介绍数据流挖掘研究的研究现状和进展情况，详细介绍了数 据流聚类算法和分形理论在数据挖掘领域的研究现状和进展情况。 第二章：分形研究。概述了分形的起源和目前分形理论的在现代科学中的 地位，介绍了分形的概念和分形维数在各个领域的应用，着重介绍其在数据挖 掘领域的应用，并对其在数据挖掘领域的研究方向做出进一步的阐述。 第三章：聚类算法和数据流聚类算法。首先，本文描述聚类的概念和在数 据挖掘中所占的地位，详细介绍了数据挖掘中的聚类算法，对聚类算法进行了 分类和比较；其次，对数据流挖掘领域的聚类问题进行了详细的介绍，概述数 据流挖掘算法在目前的研究现状，针对数据流聚类算法、分类挖掘算法以及频 繁模式挖掘算法进行研究，并对其未来研究方向做出阐述。 第四章：基于分形的数据流聚类算法。该章是本文研究的重点，主要研究 分形理论如何与数据流聚类算法结合。首先介绍数据流分形维数的计算算法一 一s i d 算法及其相对应的数据结构，同时介绍f c 算法的主要思想；接下来着 重介绍f c l u s t r e a m 算法，在数据集进行了实验，给出了实验结果和与d g s t r e a m 算法的性能比较结果，并分析了实验结果；最后分析f c l u s t r e a m 算法的时空复 杂度。 第五章：结论与展望。在文章的最后，本文对全部研究工作进行总结，并 指出未来研究需要努力的方向和展望。 第二章分形 被誉为大自然的几何学的分形( f r a c t a l ) 理论是当今世界十分风靡和活跃 的新理论、新学科，是现代数学的一个新分支，但其本质却是一种新的世界观 和方法论。分形理论与动力系统的混沌理论交叉结合，相辅相成。它承认世界 的局部可能在一定条件下、过程中，在某一方面( 形态，结构，信息，功能， 时间，能量等) 表现出与整体的相似性：承认空间维数的变化既可以是离散的 也可以是连续的，因而拓展了视野。 2 1 分形概述 分形理论创立于2 0 世纪7 0 年代中期，创立伊始就引起人们极大的兴趣， 与耗散结构、混沌并称为7 0 年代科学史上的三大发现。作为一门独立的学科， 该理论只有大约3 0 多年历史。 分形几何的概念是美籍法国数学家曼德尔布罗特( b b m a n d e l b r o t ) 1 9 7 5 年首先提出的。1 9 6 7 年他在美国权威的科学杂志上发表了题为英国的海 岸线有多长? 的著名论文。论文指出海岸线作为曲线，虽然其特征是极不规则、 极不光滑的，呈现极其蜿蜒复杂的变化，而且不能从形状和结构上区分这部分海 岸与那部分海岸有什么本质的不同，但是就是这种几乎同样程度的不规则性和 复杂性，说明海岸线在形貌上是自相似的，也就是局部形态和整体形态的相似。 19 7 5 年，曼德尔布罗特【3 1 】用法文出版了分形几何第一部著作分开：形状、 机遇和维数。19 7 7 年该书再次用英文出版。它集中了19 7 5 年以前曼德尔布罗 特关于分形几何的主要思想，它将分形定义为豪斯道夫维数严格大于其拓朴维 数的集合，总结了根据自相似性计算实验维数的方法，由于相似维数只对严格 自相似这一小类集有意义，豪斯道夫维数虽然广泛，但在很多情形下难以用计 算方法求得，因此分形几何的应用受到局限。19 8 2 年，曼德尔布罗特i jz j 的新 著自然界的分形几何出版，将分形定义为局部以某种方式与整体相似的集， 重新讨论盒维数，它比豪斯道夫维数容易计算，但是稠密可列集盒维数与集所 在空间维数相等。曼德尔布罗特第一次提出了f r a c t a l 这个英语词，其原意是“不 规则的”、“分数的”、“支离破碎的”物体，并阐述了分形理论的基本思想，即 分形研究的对象具有自相似性的无序系统，其维数的变化是连续的，应该认识 的是，自相似性是自然界的普遍规律，小到树叶的叶脉，大到宇宙天体，自相 似性普遍存在于物质系统的多个层次上，这位被科学界尊称为“分形之父”的 曼德尔布罗特的最大贡献在于提出“物体或几何图形的维数的变化可以是连续 的 这一惊人的论断，即其维数可以不是整数。 分形理论借助相似性原理洞察隐藏于混乱现象中的精细结构，为人们从部 认识整体，从有限认识无限提供新的方法论，为不同的学科发现的规律提供了 崭新的语言和定量的描述，为现代科学技术提供了新的思想方法。近2 0 年来， 分形理论在自然科学，社会科学及哲学的许多领域中得到了广泛的应用，并逐 步成为连结现代各学科的纬线。 2 2 分形基本概念 2 2 1 基本概念 目前，学术界对分形的定义的意见还没有统一。下面给出“分形”的两个定 义，在物理上易于理解，但不够精确，也不够数学化。 定义1 ( m a n d e l b r o t ，1 9 8 6 ) ，部分以某种形式与整体相似的形状叫分形。 定义2 ( e d g a r ，1 9 9 0 ) ，分形集合是这样一种集合，它比传统几何学研究的 所有集合还更加不规则( i r r e g u l a r ) ，无论是放大还是缩小，甚至进一步缩小， 这种集合的不规则性仍然是明显的。 有上述定义可知，分形具有两个重要的特性：自相似性和标度不变性。一 个系统的自相似性是指某种结构或过程的特征从不同的空间尺度或时间尺度 来看都是相似的，或者某系统或结构的局域性质或局域结构与整体类似。另外， 在整体与整体之间或部分与部分之间，也会存在自相似性。一般情况下自相似 性有比较复杂的表现形式，而不是局域放大一定倍数以后简单地和整体完全重 合。 所谓标度不变性，是指在分形上任选一局部区域，对它进行放大，这时得 到的放大图形又会显示出原图的形态特性。因此，对于分形，不论将其放大或缩 小，它的形态、复杂程度、不规则性等各种特点均不会变化。所以标度不变性 又称为伸缩对称性。所以具有自相似特性的物体( 系统) ，必定满足标度不变 性，或者说这类物体设有特性长度。 图2 1 介绍的k o c h 曲线的生成方法是把一条直线等分成三段，将中间一段 用夹角为6 0 0 的二条等长( 1 3 ) 的折线来代替，形成一个生成单元，如图2 1 ( b ) 然后再把每一条直线段用生成单元进行代替，经过无穷多次迭代后就呈现一条 无穷多弯曲的k o c h 曲线。自相似性就是跨尺度的对称。它意味着递归，在一 个图形内部还有图形。从图2 1 ( e ) 中可以清楚看到这一点。自相似性指的是， 把要考虑的图形的一部分放大，其形状与整体相同。设想把图2 1 ( e ) 中的k o c h 曲线区间【0 ，1 3 】中的图形放大3 倍，放大后的图形与原来的曲线形状完全相同。 把区间 2 3 ，1 放大3 倍，也会得到同样的结果。 k o c h 曲线是具有严格的自相似性的有规分形，无论将它放大与缩小多少 倍，它的基本几何特性都保持不变，很显然，它具有标度不变性。因此，可以看 到，自相似性与标度不变性是密切相关的。 图2 1 三次k o r c h 曲线 2 2 2 分形维数 分形的定量表征和基本参数一一分形维( 又称h a u s d o r f f 维数) ，是描述分 形体的一个重要特征量。人们用分形维来刻画分形集的复杂性，正如用整数维 数来刻画欧氏几何中的对象一样。众所周知，点是零维的，直线是一维的，平 面是二维的。它又不同于经典几何学中的整数型的欧几里德维数，而是建立在 h a u s d o r f f 测度下的一种分数型的维数。分形对象本身没有特征尺度，我们无法 去准确度量它的长度或形态，但是分形维却是其内在的不变量。通常用分数或 带小数点的数来表示分形维。实际应用中，分形体的h a u s d o r f f 维数是基于 h a u s d o r f f 测度而建立起来的一种分形维数，一般是无法直接计算得到的，而是 计算其近似值。这种计算上的困难极大地限制了h a u s d o r f f 维数的应用。分形 维的计算方法有很多，如拓扑维、h a u s d o r f f 维、盒维数、信息维、关联维等。 2 2 2 1 计盒维数 计盒维数眈是一种具有广泛应用的分形维数，它具有概念清晰、计算简单 的特点。计盒维数眈的定义如下：对于分形图形f ，用边长为s 的正方形网格 覆盖f ，设与分形图形f 相交的正方形个数为 ) ，则f 的计盒维数眈( f ) 为： 眈：l i m 掣 h 。h 1 ( ( 2 1 ) 当g 充分小时，对数比d 可以近似地看作分形f 的盒维数。盒维数具有维 数的基本性质，它也常常被称为柯尔莫哥洛夫熵、熵维数、容量维数、对数维 数和信息维数。在许多情形下，一个分形集的盒维数常常等于它的h a u s d o r f f 维。但是，上述定义的盒维数有一个严重的不足，即它可以使得一个“小”的 点集( 比如可数点集) 具有一个非零的维数，从而使维数的概念陷于混乱，这 就严格地限制了盒维数的应用。 2 2 2 2m i n k o w s k i 维数 m i n k o w s k i 维数的概念来源于形态学中的m i n k o w s k i 覆盖。 图形，其m i n k o w s k i 维数定义为： 巩= 娥( 2 一酱) 对于二维分形 ( 2 2 ) 其中：彳c ( g ) 是分形图形f 在半径为的闭集g 。下的m i n k o w s k i 覆盖的面积。 a o ( s ) = a r e a ug g ( f ，厂( f ) ) l k t e f ( 2 3 ) 其中，g s ( f ，厂( f ) ) 表示以点( f ，厂( f ) ) 为中心，占为半径的闭凸集( 可以是圆、 正方形、正三角形等) ，a r e a ( ) 表示求面积函数。 2 3 基于分形理论的数据挖掘技术 2 3 1 基于分形维数的特征属性选择方法 特征属性选择通常是数据挖掘的一个前期工作，在数据挖掘中起着重要作 用。属性选择的目的在于针对特定的应用选择最小的属性子集，且该子集能够保 证不丢失数据的原有价值。通过特征属性选择，能够提高数据的质量，加速挖掘 速度。特征属性选择方法种类很多，可以从搜索方向、搜索策略、评价准则和停 止标准四个方面来分析属性选择方法。 基于分形维数的特征属性选择方法最早是由t r a i n a 在2 0 0 0 年提出的。该 方法也是目前基于分形维数属性选择方法中一个最具有代表性的算法。该算法 在搜索方向上属于后向搜索，即首先考虑整个特征集f ，然后依据某种评价准则 不断从f 中选择最不重要的属性，直到达到某种停止标准。搜索策略采用启发式 的搜索方式。而评价准则和停止标准是该方法的特别之处，主要利用上节中提到 的数据集的分形维数来进行判断。事实上，一个数据集的分形维数是不会随着冗 余属性的加入而发生显著变化的，因而可以将分形维数的变化情况作为评价标 准。 基于分形维数的属性选择方法特点在于利用分形维数的变化情况作为衡 量属性重要性的一个标准。这种方法不需要对属性进行旋转和变换，因此能够很 容易解释最终所得到的属性集，而且能对属性的重要性进行排序。除此之外，分 形维数说明了需要保留的关键属性的个数，在与其他属性选择方法结合时可以 作为属性选择的一个停止标准。由于该方法在计算分形维数时需要多次扫描数 据集，因此一些研究者对该方法进行了改进。改进的目标在于减少扫描数据集的 次数，提高计算分形维数的效率。例如，文 2 提出了一种基于分形维的快速属性 选择算法( i f a s ) ，通过动态调整分形树( f d t r e e ) 计算分形维数，只需扫描数据集 一次。文 3 4 提出了一种基于z o r d e r i n g 的属性约简方法( z b f d r ) ，该方法也只 需要扫描数据集一次。文 3 5 】将遗传算法与z b f d r 算法结合形成g a z b f d r 算法，利用遗传算法的特点进一步加速了属性选择的速度。 2 3 2 基于分形维数的聚类方法 聚类是数据挖掘领域常用的一种方法，基于分形维数的聚类算法( f c ) 主要 思想是利用同一簇的数据点之间的自仿射性或自相似性比不同簇数据点间的 自仿射性或自相似性强的特点，根据维数的变化情况进行聚类。该算法相对于传 统聚类算法来说，具有很多优势。首先，它是利用相似性进行聚类的，而不是利用 基于距离的方法，因此能够更好地将不同类的数据区分开。其次该方法能够发现 任意形状的聚类，便于人们解释聚类的结果。目前研究者在一些数据集上如：w e b 负载记录1 36 1 、历史气象数据集【3 7 】测试基于分形维数聚类算法的有效性，都取得 了较好的效果。由于该算法采用的是一种动态的增量方法，因此特别适合应用于 数据流挖掘中，即适合对一些随时间呈现变化趋势的数据集进行挖掘。除此之外， 根据该算法的思想，还可以将其应用于离群数据挖掘中，设置一定的阈值，当数据 点落入数据集中，数据集的分形维数发生的变化大于设定的阈值，则说明该数据 点为离群数据。使用这种方法进行离群数据挖掘有利于我们解释离群点的含 义。 2 3 3 基于分形维数的关联规则发现方法 关联规则是数据挖掘中的一项重要技术，用于发现大量数据中项集之间的 有趣关系，所发现的关联规则可以成为其他领域中进行决策的依据。目前，基于 分形维数的关联规则发现方法主要应用于量化关联规则挖掘。所谓量化关联规 则是指数据集合中的数据不仅仅包含二进制属性数据，而且包含数字属性的数 据，例如年龄属性等。最为典型的基于分形维数的关联规则挖掘算法【2 7j 是 b a r b a r i 等人于2 0 0 0 年提出的，该算法依然是利用分形维数的变化情况来进行关 联规则的挖掘。动态计算数据集的分形维数，如果增加一个项集后，数据集的分 形维发生了急剧变化( 超过一定的阈值) ，那么就认为是数据区间的一个分割点。 该算法相对于以往的量化关联规则挖掘算法来说，最大的优势就在于能够很好 地发现可能丢失的频繁项集。 2 3 4 基于分形维数的分类与预测方法 从广义上说，分类是预测的一种，分类是预测离散或分类号的。而预测不仅 包括离散值的预测还包括连续值的预测。分类和预测应用于数据挖掘领域可以 描述重要数据类的模型或预测未来的数据趋势。与前面提到的几种基于分形维 数的数据挖掘技术不同的是，基于分形维数的分类和预测主要是将分形维数作 为一个特征量，将其与其他的分类或预测技术相结合从而进行分类或预测。例 如，r a l p hh i p p e n s t i e l 等人结合分形维与神经网络对数字信号进行了分类；安国 成等人在探讨了图像分类中三种分形维数提取方法的基础上，将分形维数与模 糊c 均值算法相结合对s a r 图像进行分类；陈辉等人将分形维数与神经网络相 结合构建识别模型，并以地震检测波为分析对象，对混凝土地下连续墙的区域物 性进行预测等。在这些应用中都是将分形维数作为描述事物的一个特征量的。 值得一提的是，利用分形维数进行预测时，除了使用上面提到的方法外，还有一个 比较常用的方法，利用分形统计模型进行分析预测。一般地，分形统计模型可以 表示如下1 3 8 】： ( ，) = c r d ( 2 4 ) 其中r 表示特征尺度，c o 为比例常数，d 0 称为分维数，n ( r ) 表示尺度大于等 于或小于r 的个数，其中当分形维数前面取负号时，记为