（计算机应用技术专业论文）数据流挖掘中聚类算法的研究与实现.pdf

哈尔滨工程大学硕士学位论文 摘要 聚类分析是数据挖掘领域一项重要的研究课题。近年来，由于计算机及 应用技术的高速发展，人们获取数据的能力得到了极大的提高。数据流( d a t a s t r e a m ) 作为一种重要的数据来源，也得到了人们越来越多的关注。如w e b 点击流、气象观测信息流、电话记录信息流等。与传统的待处理数据相比， 这些数据是高速的、连续的、动态的、变化的、无限的，对它们的访问只能 是顺序的、一次或有限次的，对它们的存储也只能是动态的、概要的。数据 流的这些特性，给数据流的挖掘带来了极大的困难，也给数据流的聚类算法 提出了更高的要求。 近年来人们提出了很多聚类算法来处理数据流，并取得了一定的成果。 本文首先介绍了数据挖掘的相关算法及技术，然后给出了数据流挖掘的特点， 并对已有的数据流聚类成果进行了详细的研究分析。找出了各自的优点和不 足。针对这些不足，本文提出了一种新的基于密度的聚类算法- s d s t r e a m 算 法，来处理进化数据流。s d s t r e a m 算法引入了滑动窗口技术，采取了动态剪枝 策略，不仅能发现任意形状任意数目的聚类，而且能处理噪声，减少内存开销， 并能对数据流历史信息进行查询分析，是一种高效的聚类算法。 基于真实数据集和仿真数据集的实验表明，算法具有良好的实用性、有 效性和可扩展性，适合处理和分析大规模的进化数据流。 关键词：数据挖掘；聚类分析；进化数据流；滑动窗口 哈尔滨工程大学硕士学位论文 a b s t r a c t c l u s t e ra n a l y s i si s 觚i m p o r t a n tt o p i cj nd g br n i n i l l g 丘e l d 。w i mt h ef a s t d 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 l i o n ，p e o p i eh a v em o f es t r o n ga b i l 姆t o o b t a i nd a t as t r e a m s b e i n g 狮i m p o r t a n t 姗u r c e ，s t r e a m sh a v eb e e np a y e d m o r ea t t v n t i o 砌够w e bd i c ks t r e a m s ，m 酏m l o g i c a lo b s e r v a t i o ni n f o r m a t i o n s t r e a m s 徊l e p h o l l cr e c o r ds t r e a m se t c c o m p a r e d 、v i i ht h et r a d i t i o n a ld a t a , t h e s e d a t aa 地a m m m 吣，d y n a m i c ，v 枷o n a la n db o m l d l c 豁w ec a no n l yv i s i tt h e m o r l c e0 rs e v e r a ll i m e dt i m e sa n do l l l ys t o mt h e 鳓蛐m a r yd y 舱i i l i c l y t l l c 腿t u 瑚瑚k ed a t a 蚰e a m sm i n i n gb e c o l p em o r ed i 衢砌饥a n di th a sa l b r o u g h t a b o l nh i g h 盯r e q 仳= f o rd a t as t r e a m sc l u s t e r - a l g o r i t h m hr e c u ry c a r s ol o to fc l u s t e r i n g a l g o f i t h r a sf o rd a t as t r e a m sh a v eb e e n p r o p o s e da n da p p l i e d 。i nt l l i st h e s i s ，丘r s t i y , w em t r o d u t h er c l c v 觚ta l g o f i t h m a n dt c c i l 玎【o l o g y ，越l dt h e ns t a t et h em 血l 地o f 血诅s t r e a m sm i n i n g f i n a l l y , w e p r e s e n tan e wd e 地耐迁瞌dc l = t e r i i l ga i g o f i t h mo v e ra nw o l v m gd a t as 订e a m s s d s t r e a m t h ep i o p o s e da l g o f i t h mu s 髂s l i d i n gw i n d o wt e c h n o l o g ya n da d o p t s p r u n i n gs t r a t e g y w ec a nn o to n l yf i n dd u s t e r s 诵也a r b i t r a r ys h a p ea n da m o u n t , b u ta l s od e a l 丽l h 舯i 辩挑，a md o w nm e m o i yc o 瓯q u e r ya n da n a l y z eh i s t a 哆 i n f o m m t i o = b y = i n gt h i sa l g o f i t h m 1 ti s 孤e f f e c td a t as t r e a m sc l u s t i 嘶n g a l g o f i t h n 【l t h ea 【p 盯i m 饥t a lr e s t = o nr e a ld a t a s e t sa n ds y n t h e d cd a t a s e t sd e m o n s t r a t e t h a tt h e a l g o r i t h mh a sg o o da p p f i c a b g n y ，e 妇讯蜘e 鹤a n d a l a b i l 时1 1 l e a l g o f i t h mi ss u i t a b l ef o rd e a l i n gw i t hl a r g e s c a l e “o l v m gd a 诅蚰咖s k e yw o r d s ：m i n i n g ：c l u s t e r i n ga n a l y s i s ；e 、，o l v m gd a t as t r e a m s ；d i d i n g w i n d o w 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：董至查豳 日期：聊年月l - e 1 哈尔滨工程大学硕士学位论文 1 1 相关概念 第1 章绪论 随着信息技术的高速发展，人类积累了大量数据。数据挖掘技术旨在从 大量数据中挖掘出有用的信息，以辅助人们进行科学分析和决策。短短的十 几年里，数据挖掘得到了迅速发展，已提出很多有用的算法和框架，形成了 比较完整的体系。然而，近年来许多应用中产生了大量的、源源不断的数据， 数据内部隐藏的模式随着时间的变化发生变化，如电话通信记录、卫星传感 数据、网络监控日志、电子商务记录。这些数据适合用数据流模型进行描述。 在数据流模型中，数据流算法只能对数据进行一次顺序扫描，并且，与数据 量相比，内存空间大小非常有限，只能保存数据的概要而不是全体。传统的 数据挖掘算法针对的是静态的数据库，因此不能直接应用于数据流，这促使 人们设计新的数据挖掘算法来适应数据流模型。 1 1 1 数据挖掘 从人类步入信息化时代开始，通信、计算机和网络技术就极大地影响着 整个人类社会。海量信息既给人们带来方便，也带来了许多问题，我们在惊 叹信息爆炸的同时又不得不面对知识贫乏的苦恼：信息过量难以消化、信息 真假难以辨别、信息安全难以保证、信息形式相异难以统一处理。人们开始 考虑：“如何才能不被信息淹没，而是从中及时发现有用的知识、提高信息 利用率? ”面对这一挑战，伴随着数据库和人工智能技术的蓬勃发展，数据 挖掘技术应运而生，并显示出了强大的生命力。 在介绍数据挖掘前，先来了解一下知识发现。人们很早就认识到应从海量 的数据中归纳发现知识。知识发现是一个众多学科诸如人工智能、机器学习、 模式识别、统计学、数据库和知识库、数据可视化等相互交叉、融合所形成 的一个新兴的且具有广阔前景的领域。 数据挖掘( d a t am n i n g ) 简称蹦，也称为数据库中的知识发现k d d 哈尔滨工程大学硕士学位论文 ( k n o w l e d g ed i s c o v e r yi nd a t 曲a s e ) ，是近几年来随着数据库和人工智能 发展起来的- f 新兴的数据库技术。数据挖掘处理的对象是大量的日常业务 数据。数据挖掘的目的是从大量的、不完全的、模糊的、有噪声的原始数据 源中采用和发展有关的理论、方法和工具来提取隐含在其中的、事先未知的、 但又是潜在有用的信息和知识。 数据挖掘的诞生是人们对数据库技术进行长期研究和开发的结果，数据 挖掘技术的日益成熟，推动了数据库技术进入更高级的阶段数据仓库阶段。 ( 数据库技术的演化历程如图1 1 所示) 图1 1 数据库的演化历程 2 哈尔滨工程大学硕士学位论文 数据仓库的广泛应用，增强了人们存储大量数据的能力，同时也间接的 促进了数据挖掘技术的进一步提高。髓着计算机处理技术的增强、先进数据 挖掘算法的提出，数据挖掘技术不仅能对过去的数据进行查询和遍历，而且 能够找出过去数据之间潜在有价值的联系，并以某种形式表现出来，从而提 高了数据拥有者对大量原始数据的深层次理解、认识和应用，解决了“数据 丰富，知识贫乏”的阀题，极大的满足了人们对知识的迫切需求，也为企业、 商家的决策者提供了有效的决策支持 在长期的研究中，人们对数据挖掘有了系统的掌握，对数据挖掘的任务 更有了较明确的认识数据挖掘的任务“1 主要是关联分析、聚类分析、分类、 预测、时序模式和偏差分析等。 1 ) 关联分析( a s s o c i a t i o na n a l y s i s ) ， 关联规则挖掘是由a g g r a w a l 等人首先提出来的。1 ，它的任务是寻找数据 项中的有趣联系，决定哪些事情将一起发生。两个或两个以上变量的取值之 间存在某种规律性，就称谓关联。数据关联是数据库中存在的一类重要的、 可被发现的知识关联分为简单关联、时序关联和因果关联。关联分析的目 的是找出数据库中隐藏的关联网。一般用支持度和可信度两个阈值来表示关 联规则的相关性，有时还会引入兴趣度等参数，使得所挖掘的规则更符合需 求。 2 ) 聚类分析( c l u s t e r i n g ) 聚类是把数据按照相似性归纳成若干类别。同一类中的数据彼此相似， 不同类中的数据相异。聚类分析可以建立宏观的概念，发现数据的分布模式 以及可能的数据属性之间的相互关系 3 ) 分类( c 1 a s s i f i c a t i o n ) 分类就是找出一个类别的概念描述，它代表了这类数据的整体信息，即 该类的内涵描述，并用这种描述来构造模型，一般用规则或决策树模式表示。 分类是利用训练数据集通过一事实上的算法而求得分类规则。分类可被用于 规则描述和预测。 4 ) 预测( p r e d i c a t i o n ) 预测是利用历史数据找出变化规律，建立模型，并由此模型对未来数据 的种类及特征进行预测。预测关心的是精度和不确定性，通常用预测方差来 3 哈尔滨工程大学硕士学位论文 度量。 5 ) 时序模式( t i m e s e r i e sp a t t e r n ) 时序模式是指通过时间序列搜索出的重复发生概率较高的模式。与回归 一样，它也明智已知的数据预测未来的值。但这此数据的区别是变量所处时 间的不同。 6 ) 偏差分析( d e v i a t i o n ) 在偏差中包括很多有用的知识，数据库中的数据存在很多异常情况，发 现数据库中数据存在的异常情况是非常重要的。偏差检验的基本方法就是寻 找观察结果与参照之间的差别。 1 1 2 数据流 最近几年，有关数据流盥”的概念越来越受到人们的重视。在应用中，人 们遇到大量的、源源不断的数据( 如传感器数据) ，这些数据不是静态不变 的数据集合，而是动态的、连续的、有序的、无限的数据集合，它只能被按 顺序访问，且仅能被扫描一次或有限的几次，我们把这种数据集合称作数据 流。数据流与一般的数据的区别在于它的到达是快速的，无界的，时变的和 不可预测的，从而不可能将原始数据流中的数据完全存储 些比较常见的应用包括网络监控日志、电子商务记录、电话通信记录、 银行交易信息、传感器数据等等。这些数据的共同点是数据规模庞大、增长 迅速，例如，一天之中，沃尔玛超市有上千万个销售记录，s o h u 要处理近一 亿个查询，而电信方面，对一个中小城市来说仅短信业务一项就有几百万条。 数据流的广泛应用吸引了众多学者对数据流算法的深入研究。由于数据 流本身的特点使得传统的算法不能直接应用于数据流。因为数据量很大，而 且是持续的，与数据流的规模相比，内存或缓存等存储空间是极其有限的， 只能对数据进行一次顺序扫描，因此需要一种动态的增量式的算法来处理数 据流。并且，数据流到来的速度很快，多数应用要求在数据到来的同时进行 分析决策，这对算法的处理时间提出了更高的要求。 在文献 4 中，提出了处理数据流的算法的一般标准：， 1 ) 对数据流中每条记录的处理必须在很小的固定时间内。 哈尔滨工程大学硕士学位论文 2 ) 处理过程中对内存的占用必须是有限的，与算法已经读入的数据量 记录无关。 、 3 ) 只能对数据进行一次扫描；因为在大多数应用中，数据是连续的， 到来的速度很快，根本没时间去访问以前的数据。 4 ) 它必须能在处理的任何一个阶段输出一个可用的对数据进行描述 的模型。 5 ) 在任何时间点上，模型都必须是最新的，必须能实时地反映数据的 变化。 6 ) 它还要在用户需要的时候进行演化分析； 其中前两个标准是最为重要并且最难做到的，大多数已有的方法面临着 效率和可扩展性的挑战。这些算法的内存需求量是随数据量增加而增大的， 并且计算复杂性远超过线性，这样的算法无法用于数据流领域，因为在某一 时刻内存将会耗尽或者处理过程将落后于数据的到来，导致算法失效。因此 人们开始致力于设计新的适用于数据流模型的算法。 1 1 3 数据流挖掘 数据流中蕴含了大量的有用信息，因此从数据流中挖掘出未知的、有价 值的模式或规律将对网络安全、企业决策等产生重大影响。数据流自身的特 点决定了已有的数据挖掘模型不适合处理数据流，传统挖掘算法存在很多问 题，种种局限促使挖掘数据流只能用数据流挖掘模型。 1 1 3 1 传统数据挖掘算法存在的问题 。 1 ) 需要多次扫描，无法满足数据流算法单遍扫描的需要。 2 ) 效率较低，不能与数据流的速度同步 3 ) 占用资源过多，需要大量内存空间及i 0 开销。 因此，数据流挖掘算法的研究是一项迫切的任务。 1 1 3 2 数据流挖掘模型 在数据流挖掘模型中( 如下图1 2 ) ，待处理的数据不是从磁盘或内存中随 5 哈尔滨工程大学硕士学位论文 机访问读取的数据，而是一个或多个连续到达的、无穷的数据项组成的序列。 阳 m i n i n gd a t as t r e a n a l g o r i t h m 阳 o 图1 2 数据流挖掘模型 从全方位考量，数据流与传统数据的区别主要在以下几方面： 1 ) 数据流中的数据是随着时间变化流入的：而传统数据库中的数据是静 态地存储在磁盘或其他存储介质中 2 ) 数据流中的数据是按时间顺序流过的，对数据只能依次进行顺序地访 问，如果不做保存对数据的访问只能是一次：而磁盘或其他存储介质中的数据 可以随机访问、多次访问。 3 ) 数据流中的数据是无限的：而数据库中的数据是有限的。 4 ) 由予在有限的存储空间内无法存储无限数据流的全部数据，因此数据 流中大部分的数据在处理后被丢弃了，数据流上的挖掘多数只能得到近似结 果：而传统数据库上的挖掘则可以得到精确的挖掘结果。 5 ) 系统只能保存数据流全部数据的一个有限子集或统计数据，并随着数 据流上新数据的到来进行更新，这种更新的频度取决于数据流中数据到来的 速度。一般来说，数据流的更新频率要远远高于传统数据库中数据更新的频 率 1 1 3 3 数据流挖掘的的应用 数据流挖掘技术的潜在应用是十分广泛的，从政府管理决策、商业经营 决策和信息安全等很多领域都可以找到数据流挖掘技术的应用。下面列举一 些数据流挖掘技术的应用领域： 6 哈尔滨工程大学硕士学位论文 通讯记录：提取关于客户的分类模型、欺诈用户行为模型等。 网上交易数据：潜在的客户和潜在的利润增长点。 股票交易数据：股票走势模式及预测。 网络日志：攻击类型分析、入侵检测等。 传感器数据：分析地理和环境的变化，进行预测。 科学研究：在生物界，开发了咖m s 和s a m 两个发现系统，已被用于基因发 现和构造核糖核酸模型。 ， 医疗保健：1 9 9 6 年，m a t h e u s ，p i a t e t s k ys h a p i r o 和m c n e i l l 等人开发了 该领域的第一个知识发现系统一k e f i r 。 本文将设计出数据流挖掘中一些关键算法，为数据流的分析提供有力工具。 1 2 国内外研究现状 1 2 1 数据挖掘 数据挖掘是一个新兴的领域，从9 0 年代初开始兴起，在短短几年内得到 了迅速的发展。在国际上，k d d 会议已经成为具有相当影响力的会议，它代表 了k d d 领域中最高水平。从1 9 9 5 起，每年至少举办一次，有时举办两次，每一 届会议上都有许多高水平的论文发表，提出一些新的数据挖掘方法。重要的 会议还有v l d b ，s 1 6 m o d ，i c d e ，c i k m , p a k d d 等，重要的杂志有a c m 的t k i ) e 国外已 有许多专门的工作组，从事数据挖掘领域的研究。比较著名的有r a g g r a w a l 领导下的i b ma l m a d e n 实验室，还有j h a n 带领下的工作组。他们提出了许多 好的数据挖掘算法，为该领域的发展奠定了一定的基础。在国内，目前己有 相当一部分人员从事数据挖掘方面的研究，如上海复旦大学的施伯乐、周傲 英，清华大学的陆玉昌。中国科技大学的蔡庆生，哈尔滨工业大学的李建中等 等。国内比较重要的会议有“全国数据库学术会议”，重要的杂志有计算机 学报、软件学报、计算机研究与发展等。此外，近年来开发了许多数据挖掘 系统，如q u e s t ，d b m i n e r ，k d w ，e x p l o r e ，s k i c a t ，i b i a c s 等，还有许多包含 在数据仓库中的数据挖掘系统。一直以来，人们致力于提出高效、高质量、 低内存消耗的数据挖掘算法。己提出的数据挖掘算法涵盖了很多知识类型， 7 哈尔滨工程大学硕士学位论文 比如关联规则、聚类、分类等。 ，长期对数据挖掘算法的研究，使人们有了一套比较系统的研究方法，国 内外数据挖掘所使用的主要方法m 有： 1 ) 统计分析方法：在数据库字段项之问存在两种关系：函数关系和相关 。 关系，对它们的分析可采用统计工作学方法，即利用统计学原理对数 据库中的信息进行分析可进行常用统计、回归分析、相关分析、差 异分析等。 2 ) 机器学习方法：大多数机器学习方法是利用人类的认知模型模仿人类 的学习方法从数据中提取知识，由于机器学习经过多年的研究，已取 得了一些较满意的成果。因此在k d d 中可以利用目前已经比较成熟的 机器学习方法。 、 3 ) 决策树方法：决策树是一种常用于预测模型的算法，它通过将大量数 据有目的的分类，从中找到一些有价值的、潜在的信息。它的主要优 点是描述简单，分类速度快，特别适合大规模的数据处理。 4 ) 面向数据库方法：随着数据库技术的发展，其中的一些数据处理方法 不断完善并趋于成熟。在k d d 中，利用现有的一些启发式方法可以提 取出数据库中的一些牲知识。， 5 ) 混合方法：上述各种方法各有其优缺点，为提高k d d 的效率，可将各 种方法有机地结合在一起，取长补短，以发现更有价值的知识 除了上述方法以外，还有其他一些方法，如数据可视化技术，知识表示 技术等等。虽然这些方法并不普遍地应用于k d d ，但它们对数据的一些处理方 法也许会对d k k 有所启发。 1 2 2 数据流 数据流的概念在最近几年成为研究的热点。在国外，形成了很多数据流 研究小组，如s t a n d f o r d 大学的r m o t w a n i 教授领导的研究小组，u i u c 的j h a n 领导的研究小组在开发多个研究项目和原型系统中，涉及到了数据流的管 理、查询、挖掘等各方面的内容。主要成果如表1 1 所示。 8 哈尔滨工程大学硕士学位论文 表1 1 项目研究成果 项目研发者( 或机构)项目成果 s t a n f o r ds t r e a m ( 一个通用的数据流管理系统) b r o , na n dh i t a u r o r a ( 用于监测的数据流处理系统) o g ia n dw i s c o n s i nn i g a r a ( 用于提取、查询、监钡d x m l 数据) b e r k e l e yt e l e g r a p h ( 自适应的数据流系统) c o r n e l l c o u g a r a t th a n c o c k g e o r g i at e c ho p e n c q x e r o x t a p e s t r y b e l i c o r et r i b e c a 在数据库领域的国际会议上出现了一些与数据流相关的论文，i c d e 0 2 举 办了一个数据流讨论组( p a n e l ls i g m o d p o d s 0 2 ) 更说明了数据流己成为研究 热点，在该会议上有关于数据流的指南( t u t o r i a l ) 、讨论组、论文单元 ( p a p e r s e s s i o n ) ，r a j e e vm o t w a n i 还做了重要发言( i n v i t e dt a l k ) 。除此 之外，数据流会议已经举办了四次，探讨了数据流领域中的各方面问题。在 国内，目前还没有大规模研究数据流问题的研究小组，研究领域还有很大的 空白。文献 3 给出了数据流模型的综述，己有的数据流处理技术包括抽样溯、 直方图m 、小波“1 、滑动窗口叫及一些统计技术“”。这些技术也可以用作数据 流挖掘的预处理部分。 1 2 3 数据流挖掘 目前，大多数与数据流相关的项目主要集中在数据流管理及查询处理方 面，在数据流挖掘方面的研究项目还不多见，主要有u i u c 的r a g g r a w a l 和 j h a n 领导下的小组在做这方面的工作。但是，在数据流挖掘算法方面已经有 一些研究成果出现，如数据流分类“4 “、数据流聚类”6 ”。”、数据流关 9 哈尔滨工程大学硕士学位论文 i 联规则挖掘。“4 “4 等等在国内，也在这方面开始了一些探索，如复旦的周 傲英等人在数据流分析方面o “取得一定的成果，工大的李建中等人在数据 流历史数据的存储也聚集查询方面取得了一些成果1 然而，在数据流挖掘 领域还有很大的一片空白，有很多有趣的问题值得探索”1 。比如，怎样在满 足效率和内存要求的同时，获得高质量的挖掘结果；对高维数据，尤其是在 包含数值属性的情况下，如何进行数据流挖掘：如何对混合型数据进行有效 的分析处理；怎样将己有的传统挖掘算法移植到数据流环境中；如何同时提 供在线监测和离线分析；如何发现数据流挖掘结果的演变情况；如何在挖掘 过程中引入时间衩重等等。 1 3 热门技术的应用 在对数据流算法的研究探索过程中，人们遇到的最大问题就是数据流的 处理速度和内存消耗的问题。到目前为止，还没有发现一个最优的设计方案 和比较全能的挖掘技术。数据流本身的特点也决定了不可能有一个固定的挖 掘模式来处理所有类型的数据流，只能是尽量在多种应用环境下达到理想状 态。虽然对数据流的挖掘还在不成熟中，待解决的问题层出不穷，但还是取 得了一些成果，如滑动窗口的引入，进化分析的实施等 1 。3 。1 滑动窗口在数据流处理中的应用 与传统的数据库中的数据不同，数据流无法被全部保存之后再对其进行 处理。多数情况下，数据流处理的数据对象只能是数据流的一部分，即数据 流的样本：同时，人们常常关心的是最近到达数据的处理结果。因此，基于“最 新”数据的数据流处理技术的研究是一项很有实际意义的工作。基于滑动窗 口鲰引的数据流处理技术能够很好地实现对最近到达的数据进行处理。 滑动窗口是对数据流进行查询操作、求得近似结果的一种常用的数据采 样技术。数据流上的滑动窗口技术是指在处理数据流中的数据时，开辟一块 内存( 窗口) 区域，该区域只包含数据流中最近到来的部分数据。当新的数据 到来时。滑动窗口向前滑动，用最新的数据替换滑动窗口中最旧的数据。数 据依次流入窗口相当于窗口逆向滑向数据流随着数据的不断流入，最先流 哈尔滨工程大学硕士学位论文 入的数据将移出窗口不再保存。与随机采样等其它采样技术相比，滑动窗口 的近似语义清楚明了。更重要的是，在许多应用中，用户最感兴趣的往往是 数据流中最近到来的那部分数据。因此滑动窗口是对数据流进行处理时使用 的一种比较理想的采样存储技术。 滑动窗口通常只包含那些最近到达的数据，当最新数据到来的时候，窗 口将向前移动，将较旧的数据移出窗口。尽管基于滑动窗口的操作结果将会 丢失一些数据，但是，许多数据流处理操作只关注那些最近到达的数据所带 来的影响：同时考虑到数据流自身的特性，采用滑动窗口实现数据流处理是一 种较为理想的方式根据滑动窗口具体实现方法的差异，滑动窗口技术分为 基于序列的滑动窗i z i 技术和基于时间的滑动窗口技术两种实现方式数据流 通常与时间有着紧密联系，因此，基于时间的滑动窗口技术较为常用。本文 提及的滑动窗口技术指的就是基于时间的滑动窗口技术。 1 3 2 数据流的进化分析技术 随着人们获取数据信息量的不断增加，简单的计算查询数据已经不能满 足人们深层次的需要，并且信息量过大，原有的数据处理技术也无法有效的 查询处理这些数据，给人们提供有用的信息。人们希望在这些连续无界的数 据中，可以获取任意时间段内的数据特征信息，可视化的找出不同时间点的 数据变化情况，以便于为及时准确的决策提供依据。为迎合市场及多方面的 应用需求，人们对数据流的分析展开了深入研究，提出了有效的进化分析技 术。并给出了一个术语进化数据流。 所谓进化数据流，是指在数据流形成的过程中，内部隐含的类模式不断 发生变化的数据流。在某段时间内，将这样的数据流中的类发生变化情况以 文字或图形等形式展示出来，并对结果进行比较分析的过程就叫做进化分析， 也有研究者称其为数据流的演化分析。进化分析分析的对象是经过某些数据 挖掘技术处理得到的一些中间结果( 也就是类集合) ，如应用滑动窗口技术 以快照的形式存储的类的中间结果集。 、进行进化分析的的步骤如图l 。3 所示 哈尔滨工程大学硕士学位论文 由聚类的可加可 以文字或图形簪获取指定的两个 _ 减性特性找出两 时间点时的特征叫 时间点闻聚类集 叫 形式显示出来 籀疆快照集 的变化信急 图1 3 进化分析步骤 我们将类的进化情况分为三类：第一新类形成： 第二旧类消失： 第三类的漂移，即数据的变化引起类的 位置和属性( 如密度，形状) 发生变化。 这里我们以基于密度的聚类算法中的进化分析为例，来介绍进化分析的 过程，其大体流程如图1 4 所示。 、 ( t l 电协 恤也白) 类的演化 团圆固 圉团圈 o8 圆圆固 (b)(c) 图1 4 聚类演化示意图 其中：t 。、t f 表示选定的两个时间点 h 表示滑动窗口时间长度 ； 1 2 哈尔滨工程大学硕士学位论文 由密度的相关算法定义可知，类是连接在一起的密度单元的集合。聚类 结果就是这样的一些集合。因此我们通过对区间( t ，- h ，t 。) 和( t 2 - h 。劭中的 单元聚类就可以发现数据流的变化。我们假定区间( t 广h ，t 。) 和( t 2 - h t 2 ) 的聚 类结果分别是n ( t 。，h ) 和n ( t ：，h ) ，则获取上图中类的三种变化情况的计算方 法如表1 2 所示 表1 2 获取类变化的计算方法 类的变化情况分析出此变化用到的操作 新类的产生( 如图1 3 ( a ) 中灰色区域)n ( t 2 ，h ) 一( ( n ( t h ) nn ( t z ，h ) ) 旧类的消失( 如图1 3 ( b ) 中虚线区域)n ( t ，h ) 一( 伪( t - ，h ) nn ( t 2 ，”) 类的漂移( 如图1 3 ( c ) 中灰色区域)( t l - i i ，t - ) 和( t z - h 。t z ) 聚类的交集 用户通过对进化数据流的进化分析可以了解数据流上类的变化情况，并 可获取在指定时刻类的特征信息。 1 4 本文工作及内容安排 本文根据数据流的特点分析了数据流对聚类的要求以及数据流聚类方面 的最新研究成果。对各成果进行了分析比较，指出了各自的优点及不足，针 对所出现的不足，吸取各算法的优点，提出了一种新的适用于高速数据流的 聚类算法- s d s t r e a m 算法，该算法基于密度的思想，采用了滑动窗口技术， 应用了剪枝策略，分为在线和离线两部分。算法不但能发现任意形状的聚类、 处理噪声、有效的利用内存空间，而且能对数据流进行进化分析，是一种高 效的聚类算法。并用真实数据集和仿真数据集进行了实验，和已有算法进行 比较证明了算法的实用性及有效性。 ， 本文主要分为四个部分。 第1 章绪论。介绍了数据挖掘的相关概念，国内外研究现状，目前算法 哈尔滨工程大学硕士学位论文 中常用的比较热门的技术，本文的工作及内容安排。 第2 章，数据流聚类算法概述。在本章中，概述了数据挖掘对聚类算法 的典型要求，介绍了聚类在实际中的应用，分析与评估了现有的传统聚类算 法以及最新的数据流聚类算法，最后简单阐述了这些算法与技术对本文工作 的影响。 第3 章，基于密度的聚类算法模型。在本章中，提出了新的用来处理进 化数据流的聚类算法一s d s t r e a m 算法，算法中应用了一种剪枝策略在线动态维 护参考簇，以保证有效地利用有限的内存空间，并详细介绍了这种算法的实现 过程及理论基础。 ， 第4 章，实验分析。在本章中，应用了真实数据集和仿真数据集对 s d s t r e a 蚰算法进行了性能测试，并对实验结果进行了比较分析。 最后一部分，结论。总结全文 1 4 哈尔滨工程大学硕士学位论文 第2 章数据流聚类算法概述 在本章中，第2 1 节概述了传统聚类挖掘算法，分析了数据挖掘对聚类算 法的典型要求，第2 2 节给出了数据流聚类分析的特点，并对目前最新的几个 数据流聚类研究成果进行了分析评价，针对各类算法的优点及不足，在第2 3 节中进行了总结，为后续算法研究提供了理论及实践基础。 2 1 传统聚类算法 传统聚类算法主要是针对静态数据库进行设计的，这类算法处理的数据 多是存储在磁盘或其它存储介质中的静态数据，算法可以对这些数据进行随 机操作，多次扫描，计算量往往都是很大的，i o 开销随着数据量的增多也 会增大。 2 1 1 聚类分析简介 聚类分析是一种“物以类聚”的方法，是按照属性值把一组对象划分成 一系列有意义的子集的描述性任务。聚类的目的就是要将一组数据分组，而 这种分组要基于以下原理：即满足最大的组内相似性和最小的组间相似性， 使得不同聚类中的数据尽可能地不同，而同一聚类中的数据尽可能地相似。 目前，聚类分析已成为数据挖掘领域的主要课题之一。一个重要的原因 就是聚类越来越多地应用在海量数据中，对于这些海量数据，单纯的统计的 方法无法实现有效的处理、从中得出有用的信息，必需要和数据库管理、人 工智能等计算机技术结合在一起提出集成的解决方案，而聚类分析正好为解 决这些问题提供了一个有力工具。 近年来，随着硬件技术的发展，有越来越多的应用产生数据流，数据流 不同于传统的存储在磁盘上的静态数据，而是一类新的数据对象，它是无限 的、连续的、有序的、快速变化的、海量的数据。典型的数据流包括网络与 道路交通监测系统的监测信息数据、电信部门的通话记录数据、由传感器传 回的各种监测数据、股票交易所的股票价格信息数据以及环境温度的监测数 哈尔滨工程大学硕士学位论文 据等。数据流本身的这些特点决定了对数据流进行处理时只能对数据作l 2 遍的扫描，并只能临时存储少量的数据。因此原来很多成熟的数据挖掘、数 据分析和数据查询技术在数据流上变得不适用了，需要提出新的解决方法 因此，数据流的问题一出现马上引起了研究者的重视，出现了很多研究成果， 对数据流从管理、查询、分析与挖掘算法等多个方面进行了研究。 数据流挖掘技术作为数据挖掘领域的新问题，很多挖掘算法需要针对数 据流进行改造。数据流聚类分析作为数据流挖掘的一个重要研究方向，同样 面i 临着巨大的挑战，也引起了研究者们的广泛关注，目前出现了不少相关的 研究成果，并应用到了实践中。 2 1 2 聚类的实际应用 目前，聚类分析已经成为数据挖掘和知识发现领域中的主要课题之一 聚类分析作为一种基本的数据挖掘方法已经广泛地应用于相似搜索、顾客划 分、模式识别、趋势分析、金融投资、地理信息系统、卫星图象和医疗卫生 等领域，并取得了一定成效。 比较有代表性的应用实例如：1 ) 在交易数据库中，对顾客一次购买商品 的情况进行聚类分析，根据聚类结果来布置商品摆放位置，从而提高销售利 润。2 ) 类似地，在电子商务中，每天的日常业务会产生大量数据，用聚类算 法分析这些数据信息能帮助销售商确定相对固定的顾客群，便于商家有针对 性的制定销售方案、开展有效的促销活动，以保证在赢得更大利润的同时又 发展了新顾客群、保留住了1 日顾客群。3 ) 在信息检索领域中，聚类分析对文 档进行分类，改善信息检索的效率，从而提高人们的工作效率4 ) 在气象预 测中，通过对由传感器传来的空气的温度、湿度、可见度等信息进行聚类， 可以预测未来几天气候的变化。5 ) 在医疗分析中，通过对一组新型疾病聚类， 得到每类疾病的特征描述，就可以对这些疾病进行识别，提高治疗的功效。聚 类还能帮助医生发现不正常类别的特殊病例，例如识别组织结构的病变细胞。 6 ) 聚类还用于发现空间趋势，即空间数据库中一个或多个非空间属性的变化 模式。7 ) 在天文学上，研究人员利用聚类分析宇宙仿真系统得到的数据，更 好地理解黑洞形成和进化的物理过程等等。 1 6 哈尔滨工程大学硕士学位论文 由上可见，聚类分析的用途非常广泛，大力发展聚类分析算法、提高聚 类分析质量，事在必行 2 1 3 数据挖掘对聚类算法的典型要求 聚类分析是一个富有挑战性的研究领域。随着累积数据量的增多、数据 拥有者对数据潜在信息需求的增大，对聚类算法的要求也在不断的提高。长 期的研究与实践总结出数据挖掘对聚类的典型要求如下： 1 ) 可伸缩性 聚类要处理的数据量通常是十分巨大的，可能达到数十亿( g i g a b y t e s ) 、 万亿( t e r a b y t e s ) 甚至千万亿( p e t a b y t e s ) 字节。超大规模的数据库要求有效 的、快速的聚类算法，其运行时间必须是可预测且可接受的，时间复杂性为 指数或多项式的算法不具有实用价值。 2 ) 处理不同数据类型的能力 ， 许多方法被设计用来聚类数值类型的数据。但是，应用可能要求聚类其 它类型的数据，如二元型、序数型、分类标称类型。 3 ) 能发现任意形状的聚类 由于聚类的具体特征在允析前一般是未知的，聚类可能是球形的、狭长 形的、凹形的、嵌套的、中空的等任意复杂的形状和结构，这就要求聚类算 法能发现任意形状的聚类。 4 ) 对于输入数据的顺序不敏感 一些聚类算法对于输入数据的顺序是敏感的。例如，同一个数据集合， 当以不同的顺序提交给同一个算法时，可能产生差别很大的聚类结果。开发 对数据输入顺序不敏感的算法具有重要意义。 5 ) 基于约束的聚类 现实世界的应用可能需要在各种约束条件下进行聚类。 6 ) 最少的参数和确定参数值的领域知识 几乎所有的聚类算法都包含或多或少的参数，例如聚类的密度和个数等， 这些预先给定的参数值在很大程度上决定了聚类的结果。如果参数值不符合 数据的分布特征，算法就不能获得好的结果。而在实际应用中，合适的参数 1 7 哈尔滨工程大学硕士学位论文 往往很难确定。因此，用户希望算法能够依据某种原则或领域知识估计参数 的最佳取值。 7 ) 有效地识别噪声数据， 噪声在大规模的和高维的数据库中尤其普遍。许多领域要求聚类算法具 有识别噪声的能力。在某些特殊应用中，噪声的识别甚至比聚类的发现更有 实际意义，例如在电子商务中发现非友善的恶意行为可以有效地减少损失。 8 ) 可理解的结果 数据挖掘的结果要求用户能够理解所发现的知识，有效地分析这些知识， 区分哪些是有用的，哪些是常识的或异常情况。聚类结果的描述一直是个困 难的问题，特别是对于高维数据来说。比较常见的描述方法如表2 1 所示 表2 1 聚类结果描述方法 描述方法内容优缺点 把高维数据映射到优点：使用户可以交互地分析 低维空间，通过直观数据 可视化技术 的图形方式将模式缺点：多数可视化技术不适用 呈现给用户于维数过高的数据空间 优点：不受维数的限制 简单抽象的形式 如d n f 范式 缺点：可能把形状不规则的聚 描述聚类类分割成若干区域使得 表达式过于复杂 利用决策树得到聚缺点：对形状不规则的聚类很 决策树方法类的规则及相关的难得到简单的规则 统计信息 9 ) 处理高维数据 ， 高维空间中对象之间的关系变得更加复杂，聚类问题一直是该领域的研 究难点。、 1 0 ) 动态性 组合爆炸导致搜索空间指数级地增长，因此高维数据应用领域的数据大 都是动态的，随时间不断变化的，先前发现的知识可能过时，如果不进行更 1 3 哈尔滨工程大学硕士学位论文 新，就会导致决策错误。目前大多数聚类算法只能处理静态数据，当数据更 新后，算法需要从头开始执行得到新的模式。要处理动态数据，特别是动态 系统中周期性变化的数据，就必须研究增量聚类算法，当数据改变时，算法 可以对发现的模式加以修正。 1 1 ) 联机支持 ” 目前的聚类算法一般都遵循这样的步骤：给定算法和参数值，处理数据 库，得到聚类。这种“黑箱操作”的问题是不恰当的参数值会得到不好的结 果。如果等聚类完成之后，才发现结果不理想，修改参数值，重新开始聚类， 就无疑造成了极大的资源浪费在联机方式下，系统随时地反馈聚类过程中 每一个步骤的中间结果，用户监督聚类的进行情况，随时调整参数值，并能 按照意愿随时终止。 1 2 ) 并行和分布的聚类算法 由于聚类算法通常具有很高的时间复杂性，而现实的数据库容量巨大， 因此聚类过程需要相当长的等待时间，随着网络的普及，信息的分布性增强， 聚类的并行算法和分布算法越来越受到重视。 1 3 ) 空间数据的聚类 。 大多数聚类算法以点为处理对象，但空间中的对象通常是由若干个点、 线、面构成的区域。传统的方法是把它们转变成点，但这会失去某些空间关 系。空间对象之间相交、覆盖等关系使计算对象间的距离更加困难。另一方 面，因为空间对象的边界有时是不确定的，使得空间对象本身具有模糊性， 这就增加了聚类的复杂程度。 2 1 4 典型聚类算法 许多聚类算法都是为特定的领域设计的，都有各自的特点和应用范围， 因而任何聚类算法都不可能在每个标准上都优越于其它算法。传统的聚类算 法主要分为基于划分的方法、基于层次的方法、基于密度的方法、基于网格 的方法及基于模型的方法。 t 1 ) 基于划分的方法( p a r t i t i o n i n gm e t h o d ) ：通过优化一个主函数把数 据集分割为k 个部分。即对给定一个n 个对象或元组的数据库，一个划分方 i 9 哈尔滨工程大学硕士学位论文 法构建数据的k 个划分，每个划分表示一个聚类，并且k n 也就是说，它 将数据划分为k 个组，同时满足如下的要求： ( i ) 每个组至少包含一个对象； ( i i ) 每一个对象必须属于且只属于一个组。 为了达到全局最优，基于划分的聚类方法会要求穷尽所有可能的划分。 实际上，绝大多数应用采用了两个比较流行的启发式方法k 平均算法和k 一 中心点算法。 。 2 ) 基于层次的方法( h i e r a r c h i c a lm e t h o d ) ：是由不同层的分割聚类组 成，层次之间具有嵌套的关系。根据层次的分解如何形成，层次的方法可以 分为凝聚的和分裂的。凝聚的方法，也称为自底向上的方法，开始时将每个 对象作为单独的一个组，然后相继地合并相近的对象或组，直到所有的组合 并为一个，或者达到一个中止条件。分裂的方法刚好相反。 基于网格的方法：是将对象空间量化为有限数目的单元，形成网格结构，然 后在网格结构上进行聚类。这类方法的处理时间不受数据对象数目影响，仅 信赖于量化空间中每一维上的单元数目，因此处理速度很快。 3 ) 基于模型的方法( m o d a lm e t h o d ) ：该方法建立在数据符合潜在的概 率分布这一假设基础上，这类方法为每个簇假设一个模型，试图优化给定数 据与