（计算机软件与理论专业论文）基于密度的流数据聚类算法.pdf

东 北大学 硕士学位论文 摘要 基于密 度的流数据聚类算法 摘要 企业的大型数据库中蕴含的大量有用的信息资源，促进了知识发现和数据挖 掘的兴起。聚类是数据挖掘中一个重要的分析方法，其定义如下:给定k 维空间 的n 个数据点， 把这。 个点分成d 个组，即满足最大的组内相似性和最小的组间 相似性，使得不同聚类中的数据尽可能地不同， 而同一聚类中的数据尽可能地相 似。 数据挖掘、统计学、机器学习等很多领域都涉及到聚类分析， 它被应用到市 场营销聚类分析、空间数据技术、生物学、生物医学上基因分析、国土资源利用 等诸多领域。数据挖掘领域中的聚类分析主要是针对大的数据集，相关聚类算法 的研究主要集中在算法的可伸缩性、算法对聚类复杂形状和类型的数据的有效性 以及处理不同类型属性的能力等方面。 近年来，越来越多的应用产生数据流，它是连续的、有序的、快速变化的、 海量的数据。流数据不同于传统的存储在磁盘上的静态的数据，而是一类新的数 据对象。典型的流数据包括网络与道路交通监测系统的监测信息数据、电信部门 的通话记录数据、由传感器传回的各种监测数据、股票交易所的股票价格信息数 据以 及环境温度的监测数据等。流数据聚类分析成为聚类研究的一个重要方向。 流数据聚类分析较传统的聚类分析具有更大的挑战性，这是由流数据的特性 所决定的。对流数据分析的要求如下:第一，有限的使用内存及存贮空间:第二， 对数据的访问最多一次:第三，要能够跟上流的速度。本文分析了流数据对聚类 的要求以及流数据聚类方面的最新研究成果。 研究发现，目 前的流数据聚类算法 大多是基于k 一 中心或k 一 均值的算法，其缺点是不能对任意形状的数据分布进行聚 类。传统的基于密度的聚类算法，如d b s c a n ，可以发现任意形状的类，但这些 算法的高复杂度及多次扫描数据集的需求不适合对流数据进行聚类。基于空间划 分的 算法c l i q u e 可以发现任意形状的 类， 且只需一次 扫描数据集。 但是，该算 法中产生的单元的个数与数据集维数成指数增长，算法的高复杂度不适合对流数 据进行分析。 本文提出了一种新的索引结构c d - t r e e 对空间划分生成的非空单元进行索引， 使生成的单元数大大减少。基于该结构，提出了一种基于密度的流数据聚类算法 c d s ， 该算法可以实现对任意形状分布的流数据进行聚类。 该算法分为滑动窗口上 的在线聚类及基于磁盘的离线演化分析两部分。本文还提出了一种新的衡量数据 东北大学硕士学位论文 摘要 偏斜程度的度量 d s f ，利用该度量可以实现在线聚类中动态调整划分的粒度，以 实现在有限的内存下聚类精度的最大化。 为了实现数据流上更大跨度的聚类分析， 本文在在线聚类部分以倾斜的时间窗口 方式存储数据流的概要数据，以实现对指 定时间段的离线演化分析。 本文在真实数据集与人工数据集上进行了大量的实验，对算法的有效性、算 法的性能等指标进行了 测试。 测试结果表明，算法在一定空间使用下可以实现高 精度聚类流数据，且对流数据的数据量及维数有很好的可伸缩性。 关键字:数据挖掘聚类分析数据流空间划分c d - t r e e 流数据聚类 东北大学硕士学位论文 ab s t r a c t a d e n s i ty - b a s e d c f u s t e r in g a fg o r i t h m o v e r s t r e a m d a t a ab s t r a c t t h e w e a l t h o f i n f o r m a t i o n e m b e d d e d i n h u g e d a t a b a s e s o f c o r p o r a t i o n s h a s s p u r r e d a t r e m e n d o u s i n t e r e s t i n t h e a r e a s o f k n o w l e d g e d i s c o v e ry a n d d a t a m i n i n g . a s a c r it i c a l a n a l y s i s t e c h n i q u e , c lu s t e r i n g i s d e f i n e d a s f o l l o w s : g i v e n n d a t a p o i n t s i n a k - d i m e n s i o n a l m e t r i c s p a c e , c l u s t e r i n g i s t o p a r t i t i o n t h e d a t a p o i n t s i n t o d c l u s t e r s s u c h t h a t t h e d a t a p o i n t s w i t h i n a c l u s t e r a r e m o r e s i m i l a r t o e a c h o t h e r t h a n t h a t i n d i ff e r e n t c l u s t e r s . c l u s t e r in g h a s b e e n s t u d i e d e x t e n s i v e ly b y m a n y r e l a t e d r e s e a r c h f i e l d s s u c h a s d a t a m in i n g , s t a t i s t ic s , m a c h i n e l e a rn i n g , a n d h a s b e e n a p p l i e d i n t o s e v e r a l a p p l i c a t i o n s s u c h a s m a r k e t i n g c l u s t e r a n a l y s i s , s p a t i a l d a t a b a s e t e c h n o l o g y , b i o l o g y , g e n e a n a l y s i s o f b i o m e d i c i n e , l a n d r e s o u r c e u t i l i z a t io n e t c . i n t h e fi e l d o f d a t a m i n i n g , c l u s t e r i n g m a in l y a i m s a t l a r g e d a t a s e t s , a n d e m p h a s i z e s o n t h e s c a l a b i l it y a n d t h e v a l i d i t y f o r t h e d a t a s e t o f c o m p l e x s h a p e a n d v a r i o u s a t t r i b u t e s . r e c e n t l y , t h e r e a r e m o r e a n d m o r e a p p l i c a t i o n s t h a t a r e f a c i n g t h e e n v i r n o m e n t o f s t r e a m d a t a . s t r e a m d a t a i s a k i n d o f c o n t i n u o u s , o r d e r e d , c h a n g i n g , f a s t a n d h u g e a m o u n t d a t a . i t i s q u i t e a n e w o b j e c t th a t i s d i ff e r e n t f r o m t r a d i t i o n a l s t a t i c d a t a s t o r e d o n t h e d i s k . t h e t y p i c a l s t r e a m d a t a i n c l u d e d a t a fr o m n e t w o r k m o n i t o r i n g a n d t r a ff i c e n g i n e e r i n g s y s t e m , c a l li n g d a t a fr o m t e le c o m d e p a r tm e n t s , i n s p e c t i o n d a t a f r o m s e n s o r s , s t o c k i n f o r m a t i o n fr o m s t o c k e x c h a n g e , a n d s o o n . t o d e a l w i t h t h i s n e w d a t a o b j e c t , c l u s t e r a n a l y s i s o n s t r e a m d a t a b e c o m e s a n im p o rt a n t r e s e a r c h b r a n c h o f c l u s t e r i n g . c o m p a r e d w i th t r a d i t i o n a l c l u s t e r a n a l y s i s , c l u s t e r a n a l y s i s o n s t r e a m d a t a m e e t s m u c h m o r e c h a l l e n g e s b e c a u s e o f t h e p r o p e rt i e s o f s t r e a m d a t a . f o r s t r e a m d a t a , t h e f o l l o w i n g .c o n d it i o n s s h o u l d b e s a t i s f i e d : f i r s t l y , l i m i t e d m e m o r y a n d s t o r a g e s p a c e ; s e c o n d l y , a c c e s s t o d a t a a t m o s t o n e t i m e ; t h i r d l y , k e e p in g u p t h e s p e e d o f d a t a s t r e a m s . i n t h i s t h e s i s , w e a n a l y z e w h a t a r e r e q u ir e d f o r c l u s t e r i n g o n s t r e a m d a t a , a n d g i v e s e v e r a l r e c e n t r e s e a r c h r e s u l t s . c u r r e n t l y , m o s t o f c l u s t e r i n g a l g o r i t h m s f o r s t r e a m d a t a a r e b a s e d o n t h e k - me d i a n o r k - me a n , a n d t h e i r d r a w b a c k i s t h a t t h e s e a l g o r i t h m s c a n n o t b e a p p l i e d i n t o t h e d a t a s e t o f a r b it r a r y d i s t r i b u t i o n s in s h a p e . t r a d i t i o n a l i v 东北大学硕士学位论文ab s t r a c t d e n s i t y - b as e d c l u s t e r i n g m e t h o d s , s u c h as d b s c a n , c o u l d b e a d a p t a b l e t o t h e d a t as e t o f a r b i t r a ry s h a p e , b u t h a v e h i g h c o m p u t a t i o n a l c o m p l e x i t y a n d s c a n d a t a s e t s s e v e r a l t i m e s . s p a c e p a r t i t i o n - b a s e d c l u s t e r in g m e t h o d s , s u c h a s c l i q u e , a l s o h a v e t h e c a p a c it y o f f i n d i n g a r b i t r a ry s h a p e c l u s t e r s a n d s c a n d a t a s e t s o n l y o n c e , b u t l e a d t o t h e n u m b e r o f g e n e r a t e d c e l l s i n c r e a s i n g e x p o n e n t i a l l y v a r i e d w i t h t h e n u m b e r o f d i me n s i o n s . i n t h i s t h e s i s w e p u t f o r w a r d a n o v e l in d e x s t r u c t u re c d - t r e e , w h i c h i n d i c e s t h e n o n - e m p t y c e l l s i n p a r t it i o n e d s p a c e . b a s e d o n c d - t r e e , t o fi n d a r b i t r a ry s h a p e c l u s t e r s , a d e n s it y - b a s e d c l u s t e r i n g a l g o r i t h m o v e r s t r e a m d a t a n a m e d c d s i s p r o p o s e d . t h i s a l g o r it h m c o n s i s t s o f t w o p a rt s : o n l i n e c l u s t e r i n g b as e d o n s l i d i n g w i n d o w a n d o f fl i n e e v o l u t i o n a n a l y s i s b a s e d o n d a t a i n d i s k . m o r e o v e r , a m e as u r e n a m e d d s f i s p r o p o s e d t o m e a s u r e t h e s k e w o f d a t a s e t . w i t h d s f , t h e g r a n u l a r i t y a d j u s t m e n t c a n b e i m p l e m e n t e d d y n a m i c a l l y w i t h in o n l i n e c l u s t e r in g , s o t h e a c c u r a c y o f c l u s t e r i n g c a n b e m a x im i z e d w i t h i n l i m i t e d m e m o ry . t o a n a l y z e s t r e a m d a t a w i t h m o r e t i m e s p a n s , t h e a l g o r it h m s t o r e s t h e s u m m a ry o f s t r e a m d a t a i n t e r m s o f t i lt e d - t i m e w i n d o w p o l i c y , b y w h i c h o f f l i n e e v o l v e m e n t a n a l y s i s c a n b e p e r f o r m e d t o e v a l u a t e t h e p e r f o r m a n c e a n d e f f e c t i v i t y o f t h e a l g o r it h m p r o p o s e d i n t h i s th e s i s , w e m a k e e x t e n s i v e o f e x p e r i m e n t s o n r e a l - l i f e d a t a s e t s a n d s y n t h e t i c d a t a s e t s . t h e r e s u l t s s h o w t h a t o u r a l g o r it h m c a n g e t h i g h e r a c c u r a c y o f c l u s t e r i n g w it h in l i m i t e d m e m o ry , a n d h a s t h e g o o d s c a l a b i l i t y w i t h t h e q u a n t i t y a n d t h e d im e n s i o n a l i t y o f s t r e a m d a t a k e y w o r d s : d a t a m i n i n g , c l u s t e r i n g , d a t a s t r e a m s , s p a c e p a r t i t io n , c d - t r e e , c l u s t e r i n g s t r e a m d a t a 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成 果除加以标注和致谢的地方外，不包含其他人己 经发表或撰写过的研究成果，也 不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示谢意。 学 位 论 文 作 者 签 名 : 人从 嘴 日期 :么 e v , ; 1 , 1 犷 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规 定:即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论 文被查阅和借阅。本人授权东北大学可以将学位论文的全部或部分内容编入有关 数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名;否则视为不同意。 ) 学 位 论 文 作 者 签 名 :丸斌 落 签 字日 期 :2 w 从 i - t 导师签名: 签字日期: 饮练 东 北大学 硕士学 位论文第一章 前言 第一章 前言 数据挖掘( d a t a m i n i n g ) 是近几年来随着数据库和人工智能发展起来的一门新 兴的数据库技术。其目的是从大量的、不完全的、有噪声的、模糊的、随机的数 据中提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过 程。随着海量数据搜集的可能、计算机处理技术的增强和先进数据挖掘算法的提 出，数据挖掘技术不仅能对过去的数据进行查询和遍历，而且能够找出过去数据 之间潜在有价值的联系，并以一定的形式表现出来， 从而极大的满足了人们对知 识的迫切需求，也为企业、商家的决策者提供了 有效的决策支持。 聚类分析是一种 “ 物以 类聚” 的方法，是按照属性值把一组对象划分成一系 列有意义的子集的描述性任务。聚类的目的就是要将一组数据分组，而这种分组 要基于以下原理:即满足最大的组内相似性和最小的组间相似性，使得不同聚类 中的数据尽可能地不同，而同一聚类中的数据尽可能地相似。 目 前，聚类分析己成为数据挖掘领域的主要课题之一。一个重要的原因就是 聚类越来越多地应用在海量数据中， 而单纯的统计的方法已 经无法解决这一问 题， 必需和数据库管理、人工智能等计算机技术结合在一起提出集成的解决方案。 聚类分析己经作为一种基本的数据挖掘方法广泛地应用于相似搜索、顾客划 分、模式识别、趋势分析等领域中。聚类算法在金融投资、地理信息系统、卫星 图象和信息检索等领域有着广泛的应用。例如:在交易数据库中，顾客一次购买 的 商品 ( 数据项) 构成了 一条交易， 将经常同时购买的数据项聚类到一起有利于改善 商品的布置，提高销售利润。类似地，电子商务在每天的日 常业务中，都会产生 大量数据。这些信息被w e b 服务器自 动收集并存储在访问日 志中，经过处理转换 为交易数据库。分析这些信息能帮助销售商确定相对固定的顾客群，制定商品的 销售方案，评价各种促销活动的有效性。在信息检索领域中，聚类分析对文档进 行分类，改善信息检索的效率。在医疗分析中，通过对一组新型疾病聚类，得到 每类疾病的特征描述，就可以对这些疾病进行识别，提高治疗的功效。聚类还能 帮助医生发现不属于正常类别的特殊病例，例如识别组织结构的病变细胞。聚类 还用于发现空间趋势，即空间数据库中一个或多个非空间属性的变化模式。在天 文学上， 研究人员利用聚类分析宇宙仿真系统得到的数据，更好地理解黑洞形成 和进化的物理过程。可见，聚类分析的用途非常广泛。 近年来，随着硬件技术的发展，使得可以以 很高的速率自 动记录每天的事务。 这种处理方式产生了大量的数据，而且这些数据在无限地增长，这种数据被称为 数据流。目前，越来越多的应用产生数据流，它不同于传统的存储在磁盘上的静 东北大学硕士学位论文第一章 前言 态的数据，而是一类新的数据对象，它是连续的、有序的、 快速变化的、海量的 数据。典型的流数据包括网络与道路交通监测系统的监测信息数据、电信部门的 通话记录数据、由传感器传回的各种监测数据、股票交易所的股票价格信息数据 以及环境温度的监测数据等。数据流本身的这些特点决定了对流数据进行处理时 只能对数据作1 2遍的扫描，并只能临时存储少量的数据。因此原来很多成熟的 数据挖掘、数据分析和数据查询技术在流数据上变得不适用了，需要提出新的解 决方法。因此，流数据的问题一出现马上引起了研究界的重视，出现了很多研究 成果，对流数据从管理、查询、分析与挖掘等多个方面进行了 研究。流数据挖掘 技术作为数据挖掘领域的新问题，很多挖掘算法需要针对流数据进行改造。流聚 类分析作为流数据挖掘的一个重要研究方向，同样面临着巨大的挑战，也引起了 研究 者 们的 广泛关 注， 目 前出 现了 不 少相关的 研究 成果， s u d i p t o g u h a 提出了 用分 而治之( d i v i d e - a n d - c o n q u e r ) 的 策略解决数据流聚类中的小空间聚类问 题， b r i a n b a b c o c k 发表了 通过数据流窗口 维护方差和k - m e d i a n s 的成果， c h a n x c .a g g a r w a l 提出了一种在流数据上进行聚类操作的框架等。 本文根据流数据的特点分析了流数据对聚类的要求以及流数据聚类方面的最 新研究成果。 研究发现目 前的流数据聚类算法大多是基于k - 中心和k - 平均的算法， 其缺点是不能发现任意形状分布的类。 本文提出了 一种新的索引结构 c d - t r e e 对 空间划分生成的非空单元进行索引，基于该结构，提出了一种基于密度的流数据 聚类算法 c d s ，该算法可以实现对任意形状分布的流数据进行聚类。并提出了荃 于倾斜时间窗的流数据聚类框架，基于该框架可以实现在线和离线流数据聚类。 通过使用真实数据集与人工数据集的实验表明，该算法在一定空间使用下可以实 现高精度聚类流数据，且对流数据的数据量及维数有很好的可伸缩性。 论文后续部分的组织结构如下: 第二章，数据流聚类算法综述。在本章中，概述了数据挖掘的相关方法;分 析与评估了现有的传统聚类算法以及最新的流聚类算法:并进一步探讨了在流数 据中发现任意形状的类的方法。 第三章， 基于空间划分的索引结构c d - t r e e 。 在本章中， 提出了用于流聚类的 基于空间划分的索引结构c d - t r e e ， 对其相关的定义和各种操作算法进行了详细介 绍。 并定义了 一个新的 衡量数据偏斜程度的 度量d s f ， 用于进一步优化c d - t r e e . 第四章， 基于密度的流数据聚类算法。在本章中，探讨在 c d - t r e e索引下基 于密度的流数据聚类算法c d s 的实现策略及相关算法。 第五章， 实验分析。在本章中， 对流数据聚类算法c d 进行了 有效性测试和 ,胜能测试，并对实验结果进行了比较分析。 第六章，结论。总结全文。 东北大学硕士学位论文第二章 流数据聚类算法综述 第二章 流数据聚类算法综述 在本章中，第2 . 1 节概述了数据挖掘的任务、方法及应用，第2 .2 节综述了传 统聚类算法的分类及其各自 特点， 并对它们进行了分析评价。 第2 .3 节结合流数据 聚类分析的要求， 对目 前最新的几个流数据聚类研究成果进行了分析，并在第2 .4 节阐述了数据流中发现任意形状的类的动机。 2 . 1数据挖掘概述 我们现在已经生活在一个相当 数字化的时代中，通信，计算机和网络技术正 极大地影响着整个人类社会。然而海量信息既给人们带来方便，也带来了许多问 题，使我们惊叹信息爆炸的同时又不得不面对知识贫乏的苦恼:信息过量难以消 化、信息真假难以辨别、信息安全难以保证、信息形式相异难以统一处理。人们 开始考虑: “ 如何才能不被信息淹没，而是从中及时发现有用的知识、提高信息 利用率?”面对这一挑战，数据挖掘技术应运而生，并得到长足的发展，显示出 了强大的生命力。 人们很早就认识到应从海量的数据中归纳发现知识。7 0年代就提出了知识发 现( k n o w l e d g e d i s c o v e r y ) 1 9 8 9 年提出了 机器向 历史学习， 近年来研究者用了 更形 象 更 现实的 概念， 即“ 数据挖掘” ( d a t a m i n i n g ) , 知识发现是一个众多学科诸如人工智能、机器学习、模式识别、统计学、数 据库和知识库、数据可视化等相互交叉、融合所形成的一个新兴的且具有广阔前 景的领域。 数据挖掘( d a t a min i n g ) 简称d m， 也称为数据库中的知识发现k d d ( k n o w l e d g e d i s c o v e ry i n d a t a b as e ) ， 是近几年来随 着数据库和人工智能发展起来的一门 新兴的 数据库技术。其处理对象是大量的日常业务数据，目的是从大量的、不完全的、 有噪声的、模糊的、随机的原始数据中提取隐含在其中的、事先未知的、但又是 潜在有用的信息和知识的过程。 数据挖掘的诞生是人们对数据库技术进行长期研究和开发的结果，而数据挖 掘技术发展的同时它又反过来促使数据库技术进入了一个更高级的阶段:传统的 数据环境基本上是数据操作型的，传统的信息系统只负责数据的增，删及修改操 作 ， 而 在 数 据 库的 基 础 上可 实 现的 工 作 就 是o l t p ( o n l in e t r a n s a c t i o n p r o c e s s 联 机事务处理) 。现在由 于数据积累的不断增多， 人们需要分析型的数据环境，于是 东北大学硕士学位论文第二章 流数据聚类算法综述 第二章 流数据聚类算法综述 在本章中，第2 . 1 节概述了数据挖掘的任务、方法及应用，第2 .2 节综述了传 统聚类算法的分类及其各自 特点， 并对它们进行了分析评价。 第2 .3 节结合流数据 聚类分析的要求， 对目 前最新的几个流数据聚类研究成果进行了分析，并在第2 .4 节阐述了数据流中发现任意形状的类的动机。 2 . 1数据挖掘概述 我们现在已经生活在一个相当 数字化的时代中，通信，计算机和网络技术正 极大地影响着整个人类社会。然而海量信息既给人们带来方便，也带来了许多问 题，使我们惊叹信息爆炸的同时又不得不面对知识贫乏的苦恼:信息过量难以消 化、信息真假难以辨别、信息安全难以保证、信息形式相异难以统一处理。人们 开始考虑: “ 如何才能不被信息淹没，而是从中及时发现有用的知识、提高信息 利用率?”面对这一挑战，数据挖掘技术应运而生，并得到长足的发展，显示出 了强大的生命力。 人们很早就认识到应从海量的数据中归纳发现知识。7 0年代就提出了知识发 现( k n o w l e d g e d i s c o v e r y ) 1 9 8 9 年提出了 机器向 历史学习， 近年来研究者用了 更形 象 更 现实的 概念， 即“ 数据挖掘” ( d a t a m i n i n g ) , 知识发现是一个众多学科诸如人工智能、机器学习、模式识别、统计学、数 据库和知识库、数据可视化等相互交叉、融合所形成的一个新兴的且具有广阔前 景的领域。 数据挖掘( d a t a min i n g ) 简称d m， 也称为数据库中的知识发现k d d ( k n o w l e d g e d i s c o v e ry i n d a t a b as e ) ， 是近几年来随 着数据库和人工智能发展起来的一门 新兴的 数据库技术。其处理对象是大量的日常业务数据，目的是从大量的、不完全的、 有噪声的、模糊的、随机的原始数据中提取隐含在其中的、事先未知的、但又是 潜在有用的信息和知识的过程。 数据挖掘的诞生是人们对数据库技术进行长期研究和开发的结果，而数据挖 掘技术发展的同时它又反过来促使数据库技术进入了一个更高级的阶段:传统的 数据环境基本上是数据操作型的，传统的信息系统只负责数据的增，删及修改操 作 ， 而 在 数 据 库的 基 础 上可 实 现的 工 作 就 是o l t p ( o n l in e t r a n s a c t i o n p r o c e s s 联 机事务处理) 。现在由 于数据积累的不断增多， 人们需要分析型的数据环境，于是 东 北大学硕士学位论文第二章 流数据聚类算法综述 就出现了由数据库导出的数据仓库，以此为基础则可以实现 o l a p ( o n l i n e a n a l y s i s p r o c e s s 联机分析处理) ; 随着海量数据搜集的 可能、 计算机处理技术的增 强和先进数据挖掘算法的提出，数据挖掘技术不仅能对过去的数据进行查询和遍 历，而且能够找出过去数据之间潜在有价值的联系，并以一定的形式表现出来， 从而极大的满足了人们对知识的迫切需求，也为企业、商家的决策者提供了有效 的决策支持。 2 . 1 . 1数据挖掘的任务及方法 数据挖掘的任务主要是关联分析、聚类分析、分类、预测、时序模式和偏差 分析等。 ( 1 ) 关 联 分 析 ( a s s o c i a t i o n a n a ly s i s ) 关 联 规 则 挖 掘是由r a k e s h a p w a l 等 人 首先 提出 的 1 。 两 个或 两 个以 上 变量 的 取值之间存在某种规律性，就称为关联。数据关联是数据库中存在的一类重要的、 可被发现的知识。关联分为简单关联、时序关联和因果关联.关联分析的目 的是 找出数据库中隐藏的关联网。一般用支持度和可信度两个阀值来度量关联规则的 相关性，还不断引入兴趣度、相关性等参数，使得所挖掘的规则更符合需求。 ( z ) 聚类 分析 ( c l u s t e r i n g ) 聚类是把数据按照相似性归纳成若干类别，同一类中的数据彼此相似，不同 类中的数据相异。聚类分析可以建立宏观的概念，发现数据的分布模式，以及可 能的数据属性之间的相互关系。 ( 3 ) 分类 ( c l a s s i f ic a t i o n ) 分类就是找出一个类别的概念描述，它代表了这类数据的整体信息，即该类 的内 涵描述， 并用这种描述来构造模型，一般用规则或决策树模式表示。分类是 利用训练数据集通过一定的算法而求得分类规则。 分类可被用于规则描述和预测。 ( 4 ) 预测 ( p r e d ic a t io n ) 预测是利用历史数据找出变化规律，建立模型，并由此模型对未来数据的种 类及特征进行预测。预测关心的是精度和不确定性，通常用预测方差来度量。 ( 5 ) 时 序 摸 式 ( t im e - s e r ie s p a tt e r n ) 时序模式是指通过时间序列搜索出的重复发生概率较高的模式。与回归一样， 它也是用己知的数据预测未来的值，但这些数据的区别是变量所处时间的不同。 ( 6 ) 偏差 分 析( d e v i a t i o n ) 在偏差中包括很多有用的知识，数据库中的数据存在很多异常情况，发现数 据库中数据存在的异常情况是非常重要的。偏差检验的基本方法就是寻找观察结 果与参照之间的差别。 东 北大学硕士学位论文第二章 流数据聚类算法综述 就出现了由数据库导出的数据仓库，以此为基础则可以实现 o l a p ( o n l i n e a n a l y s i s p r o c e s s 联机分析处理) ; 随着海量数据搜集的 可能、 计算机处理技术的增 强和先进数据挖掘算法的提出，数据挖掘技术不仅能对过去的数据进行查询和遍 历，而且能够找出过去数据之间潜在有价值的联系，并以一定的形式表现出来， 从而极大的满足了人们对知识的迫切需求，也为企业、商家的决策者提供了有效 的决策支持。 2 . 1 . 1数据挖掘的任务及方法 数据挖掘的任务主要是关联分析、聚类分析、分类、预测、时序模式和偏差 分析等。 ( 1 ) 关 联 分 析 ( a s s o c i a t i o n a n a ly s i s ) 关 联 规 则 挖 掘是由r a k e s h a p w a l 等 人 首先 提出 的 1 。 两 个或 两 个以 上 变量 的 取值之间存在某种规律性，就称为关联。数据关联是数据库中存在的一类重要的、 可被发现的知识。关联分为简单关联、时序关联和因果关联.关联分析的目 的是 找出数据库中隐藏的关联网。一般用支持度和可信度两个阀值来度量关联规则的 相关性，还不断引入兴趣度、相关性等参数，使得所挖掘的规则更符合需求。 ( z ) 聚类 分析 ( c l u s t e r i n g ) 聚类是把数据按照相似性归纳成若干类别，同一类中的数据彼此相似，不同 类中的数据相异。聚类分析可以建立宏观的概念，发现数据的分布模式，以及可 能的数据属性之间的相互关系。 ( 3 ) 分类 ( c l a s s i f ic a t i o n ) 分类就是找出一个类别的概念描述，它代表了这类数据的整体信息，即该类 的内 涵描述， 并用这种描述来构造模型，一般用规则或决策树模式表示。分类是 利用训练数据集通过一定的算法而求得分类规则。 分类可被用于规则描述和预测。 ( 4 ) 预测 ( p r e d ic a t io n ) 预测是利用历史数据找出变化规律，建立模型，并由此模型对未来数据的种 类及特征进行预测。预测关心的是精度和不确定性，通常用预测方差来度量。 ( 5 ) 时 序 摸 式 ( t im e - s e r ie s p a tt e r n ) 时序模式是指通过时间序列搜索出的重复发生概率较高的模式。与回归一样， 它也是用己知的数据预测未来的值，但这些数据的区别是变量所处时间的不同。 ( 6 ) 偏差 分 析( d e v i a t i o n ) 在偏差中包括很多有用的知识，数据库中的数据存在很多异常情况，发现数 据库中数据存在的异常情况是非常重要的。偏差检验的基本方法就是寻找观察结 果与参照之间的差别。 东北大学硕士学位论文第二章 流数据聚类葬法综述 上面介绍了数据挖掘的主要任务，下面我们介绍数据挖掘所使用的主要方法: ( i ) 统计分析方法: 在数据库字段项之间存在两种关系: 函数关系和相关关系， 对它们的分析可采用统计学方法，即利用统计学原理对数据库中的信息进行分析。 可进行常用统计、回归分析、相关分析、差异分析等。 ( 2 ) 机器学习 方法: 大多数机器学习方法是利用人类的认知模型模仿人类的学 习方法从数据中提取知识，由于机器学习经过多年的研究，己取得了一些较满意 的成果，因此在k d d中可以 利用目 前已经比 较成熟的机器学习方法。 ( 3 ) 决策树方法: 决策树是一种常用于预测模型的算法， 它通过将大量数据有 目的的分类，从中找到一些有价值的，潜在的信息。它的主要优点是描述简单， 分类速度快，特别适合大规模的数据处理。 ( 4 ) 面向 数据库方法:随着数据库技术的发展，其中的一些数据处理方法不断 完善并趋于成熟。 在k d d中， 利用现有的一些启发式方法， 可以提取出数据库中 的一些特征知识。 ( 5 ) 混合方法: 上述各种方法各有其优缺点 为提高k d d的效率， 可将各种 方法有机在地结合在一起，取长补短，以发现更有价值的知识。 ( 6 ) 其他方法:除了 上述方法以 外， 还有其他一些方法， 如数据可视化技术， 知识表示技术等等。虽然这些方法并不普遍地应用于k d d ，但它们对数据的一些 处理方法也许会对k d d有所启发。 2 . 1 .2数据挖掘的应用 下面是一些数据挖掘的典型应用领域。 ( 1 ) 市场: i n t e g r a l s o h t i o n s为b b c开发了 一个采用神经元网络和规则归纳方 法来预测收视率的发现系统。 ( 2 ) 工业;k d d在工业界的应用目 标是要发现最佳生产条件。 ( 3 ) 金融:这类应用系统大都采用统计回归或神经网络的方法来构造预测模 型。 ( 4 ) 科学研究: 在生物界， 开发了h m m s 和s a m两个发现系统，己 被用于基 因发现和构造核糖核酸模型。 ( 5 ) 医 疗保健: 1 9 %年， m a t h e u s , p i a t e t s k y s h a p ir o 和m c n e i l l 等人开 发了 该 领域的第一个知识发现系统一k e f m. 东北大学硕士学位论文第二章 流数据聚类葬法综述 上面介绍了数据挖掘的主要任务，下面我们介绍数据挖掘所使用的主要方法: ( i ) 统计分析方法: 在数据库字段项之间存在两种关系: 函数关系和相关关系， 对它们的分析可采用统计学方法，即利用统计学原理对数据库中的信息进行分析。 可进行常用统计、回归分析、相关分析、差异分析等。 ( 2 ) 机器学习 方法: 大多数机器学习方法是利用人类的认知模型模仿人类的学 习方法从数据中提取知识，由于机器学习经过多年的研究，己取得了一些较满意 的成果，因此在k d d中可以 利用目 前已经比 较成熟的机器学习方法。 ( 3 ) 决策树方法: 决策树是一种常用于预测模型的算法， 它通过将大量数据有 目的的分类，从中找到一些有价值的，潜在的信息。它的主要优点是描述简单， 分类速度快，特别适合大规模的数据处理。 ( 4 ) 面向 数据库方法:随着数据库技术的发展，其中的一些数据处理方法不断 完善并趋于成熟。 在k d d中， 利用现有的一些启发式方法， 可以提取出数据库中 的一些特征知识。 ( 5 ) 混合方法: 上述各种方法各有其优缺点 为提高k d d的效率， 可将各种 方法有机在地结合在一起，取长补短，以发现更有价值的知识。 ( 6 ) 其他方法:除了 上述方法以 外， 还有其他一些方法， 如数据可视化技术， 知识表示技术等等。虽然这些方法并不普遍地应用于k d d ，但它们对数据的一些 处理方法也许会对k d d有所启发。 2 . 1 .2数据挖掘的应用 下面是一些数据挖掘的典型应用领域。 ( 1 ) 市场: i n t e g r a l s o h t i o n s为b b c开发了 一个采用神经元网络和规则归纳方 法来预测收视率的发现系统。 ( 2 ) 工业;k d d在工业界的应用目 标是要发现最佳生产条件。 ( 3 ) 金融:这类应用系统大都采用统计回归或神经网络的方法来构造预测模 型。 ( 4 ) 科学研究: 在生物界， 开发了h m m s 和s a m两个发现系统，己 被用于基 因发现和构造核糖核酸模型。 ( 5 ) 医 疗保健: 1 9 %年， m a t h e u s , p i a t e t s k y s h a p ir o 和m c n e i l l 等人开 发了 该 领域的第一个知识发现系统一k e f m. 东北大学硕士学位论文第 二幸 流数据聚类算法综述 2 . 2传统聚类算法 2 .2 . 1聚类的简介 聚类分析方法是数据挖掘的重要手段之一。聚类的定义是将物理或抽象对象 的集合分组成为有类似的对象组成的多个类的过程。一般分为:划分方法，层次 方法， 基于密 度的方法， 基于网 格的方法和基于模型的方法2 ) 聚类分析的结果主要是经验性的，使用不同的聚类分析法可以有极不相同的 结果，对所做出的结果重复性也差，特别是从统计理论上难以判断某个分类结果 是否正确