（计算机科学与技术专业论文）基于密度网格结构的数据流在线聚类算法研究.pdf

习 独创性声明 iyiiiiiltllllllll7111111811111171111117111111511111111411y 17 8 7 7 5 1 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 己在论文中作了明确的说明并表示了谢意。 签名：圣坠同期：2 口细c ；- 1 0 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：导师签名： 摘要 摘要 随着计算机和互联网络技术的不断发展，各个应用领域都在源源不断地产生 数据，而这些数据通常以流的形式出现，例如传感器网络产生的数据流、股票交 易流、超市结算流、网络通信流等。数据挖掘融合了统计学、数据库、机器学习 等技术，帮助人们从海量数据中抽取出有用的知识，从而为决策提供重要依据。 数据流具有高速流动、快速变化和潜在无限等特点，因此要求数据流挖掘算 法必须满足单次线性扫描、压缩存储、低的时间复杂度等要求。现有的数据流聚 类算法，大多数停留在在线收集和离线分析阶段，典型的算法如c l u s t r e a m 。这 类算法的缺点是实时性差，不能在线生成用户需要的聚类，精确的聚类结果需要 经过离线分析才能获得。 针对这些问题，本文对数据流的在线聚类算法进行了研究，主要研究内容包 括以下几方面： ( 1 ) 使用密度网格的存储结构，将数据流的概要信息以统计值的形式存储 在网格单元中。通过设置密度网格阈值c m 舣和c m 证，能有效地控制聚类质量。 密度网格结构容易更新和维护，从而提高在线聚类效率，并节省存储空间。 ( 2 ) 本文采用计数型滑动窗口来保存当前数据流。通过调整窗口滑动一次 的步数s t e p ，可以有效地节省系统资源。 ( 3 ) 定义了网格邻居和网格簇等概念，设计优化的网格合并和更新规则， 使算法能够区分数据密集区域和稀疏区域，并较快地找到数据分布中存在的簇， 提高算法的实时性。 ( 4 ) 在论文研究过程中，通过大量的实验分析和对比，不断调整和优化算 法，取得了较好的聚类质量和在线聚类效率。 实验结果表明本算法具有快速在线聚类能力，同时保证了良好的聚类质量。 关键词数据挖掘；数据流；在线聚类 北京- e q k 大学工学硕一卜学位论文 u a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rs c i e n c ea n di n t e r n e tt e c h n o l o g y , al a r g e n u m b e ro fd a t ai sg e n e r a t e di nv a r i o u sa p p l i c a t i o n s ，w h i c hi su s u a l l yi nt h ef o r mo f s t r e a m s ，s u c ha sd a t as t r e a m sg e n e r a t e db ys e n s o rn e t w o r k s ，s t o c kf l o w , s u p e r m a r k e t s e t t l e m e n tf l o w , i n t e m e tc o m m u n i c a t i o n ，e t c d a t am i n i n g ，w h i c hc o m b i n es t a t i s t i c s ， d a t a b a s ea n dm a c h i n el e a r n i n g ，c a l lh e l pp e o p l ee x t r a c tu s e f u lk n o w l e d g ef r o mh u g e a m o u n t so fd a t aa n dp r o v i d ei m p o r t a n tb a s i sf o rd e c i s i o n - m a k i n g d a t as t r e a 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 ：h i g hs p e e d ，r a p i d l yc h a n g i n g ， p o t e n t i a l l yu n l i m i t e da n ds oo n t h e r e f o r e ，d a t am i n i n ga l g o r i t h m sm u s ts a t i s f y r e q u i r e m e n t ss u c ha ss i n g l el i n e a rs c a n ，c o m p r e s s i o na n ds t o r a g e ，l o wc o m p l e x i t y , e t c m o s te x i s t i n gs t r e a mc l u s t e r i n ga l g o r i t h ms u c ha sc l u s t r e a m ，r e m a i ni nt h eo n l i n e c o l l e c t i o na n do f f l i n ea n a l y s i sp h a s e t h ed i s a d v a n t a g eo ft w o p h a s ea l g o r i t h m si s t h a tt h e yc a l ln o tg e n e r a t ec l u s t e r so n l i n e i nt h i sp a p e r , w ed or e s e a r c ho nt h eo n l i n ec l u s t e r i n ga l g o r i t h m so fd a t as t r e a m s t h em a i nc o n t e n t sa r ea sf o l l o w s ： ( 1 ) n es u m m a r yi n f o r m a t i o no fd a t as t r e a m si ss t o r e di nc a l l e dd e n s i t yg r i d 丽n 1 r e l a t i v es t a t i s t i c a lv a l u e s b ys e t t i n gt h ed e n s i t yt h r e s h o l dc m 戤a n dc m i n ，c l u s t e r i n g q u a l i t yc a nb ee f f e c t i v e l yc o n t r o l l e d d e n s i t y 嘶ds t r u c t u r ei se a s yt om a i n t a i na n d u p d a t e ，s oi tc a ni m p r o v et h ee f f i c i e n c yo fo n l i n ec l u s t e r i n g ，a n de f f e c t i v e l ys a v e s t o r a g es p a c e ( 2 ) u s i n gc o u n t - b a s e ds l i d i n gw i n d o w , w h i c hr e f l e c t st h ec u r r e n ts i t u a t i o no f t h e d a t as t r e a m s y s t e mr e s o u r c e sc a nb ee f f e c t i v e l ys a v e db ya d j u s t i n gt h es t e po fs l i d i n g w i n d o w ( 3 ) e x c e p td e n s i t yg r i d ，t h i sp a p e r d e f i n e st h ec o n c e p t so fg r i dn e i g h b o ra n dg r i d c l u s t e r s ，t h e ya r eu s e dt oo p t i m i z e 鲥di n t e g r a t i o na n du p d a t er u l e s ，s ot h ea l g o r i t h m c a nd i s t i n g u i s hb e t w e e nd e n s er e g i o n sa n ds p a r s er e g i o n s ，a n dq u i c k l yf i n dt h e c l u s t e r si nt h ed a t ad i s t r i b u t i o ni nr e a lt i m e ( 4 ) i nt h ec o u r s eo ft h er e s e a r c h ，t h r o u g he x t e n s i v ee x p e r i m e n ta n a l y s i sa n d c o m p a r i s o n ，a n dt h ea l g o r i t h mi sc o n t i n u o u s l ya d j u s t e da n do p t i m i z e d ，s oab e t t e r c l u s t e r i n gq u a l i t ya n do n l i n ee f f i c i e n c ya r eo b t a i n e d e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h mh a sf a s to n l i n ec l u s t e r i n gc a p a b i l i t y w h i l ee n s u r i n ga g o o dc l u s t e r i n gq u a l i t y k e y w o r d sd a t am i n i n g ；d a t as t r e a m ；o n l i n ec l u s t e r i n g i i i 北京t 业大学t 学硕仁学位论文 i v 1 j 目录 目录 摘要i a b s tr a c t i i i 第1 章绪论1 1 1 研究背景及意义1 1 2 数据挖掘技术2 1 2 1 聚类分析2 1 2 2 分类和关联规则3 1 3 国内外研究现状4 1 3 1 传统的密度和网格聚类方法4 1 3 2 数据流聚类方法6 1 4 主要研究内容及论文组织形式8 1 4 1 本论文主要研究内容8 1 4 2 本论文的组织结构9 第2 章密度网格和滑动窗口技术1 1 2 1 概要数据结构。1 2 2 2 密度网格结构定义1 2 2 3 滑动窗口技术。15 2 4 数据预处理。1 6 2 5 近似性与自适应技术17 2 6 本章小结1 7 第3 章数据流在线聚类算法1 9 3 1 网格合并规则1 9 3 1 1 网格邻居合并1 9 3 1 2 密度网格簇合并2 0 3 2 基于密度网格结构在线聚类算法2 1 3 2 1 算法框架2 2 3 2 2 聚类初始化算法。2 2 3 2 3 聚类更新算法2 3 3 2 4 算法分析2 4 3 3 本章小结2 5 第4 章算法实现与实验分析2 7 4 1 实验环境与实验数据2 7 4 2 实验分析。2 7 v 北京工业入学r t 学硕l ：学位论义 4 2 1 算法实时性实验。2 7 4 2 2 网格粒度实验2 8 4 2 3s t e p 滑动窗口实验31 4 2 4 密度阈值实验3 2 4 3 本章小结3 2 结论。3 5 参考文献3 7 攻读硕士学位期间发表的学术论文4 1 致 射4 3 第1 章绪论 1 1 研究背景和意义 第1 章绪论 随着通信、计算机和互联网络的不断发展，信息技术正在不断改变着整个人 类社会。各个应用领域都在源源不断地产生大量数据，如传感器网络、电子商务、 股票交易、电话通信、信用卡交易等领域。海量数据极大地丰富了人们的信息来 源，同时也造成“数据爆炸但知识贫乏”的现象。面对多而复杂的数据，人们很 难一下从中获得自己需要的有用知识。信息过量，难以消化、信息真假难以辨识、 信息安全难以保证、信息形式不一致，难以统一处理等一系列问题亟待解决n 3 1 。 面对这一挑战，数据挖掘技术应运而生，并显示出强大的生命力。 目前数据流挖掘技术被广泛地应用于商务管理、生产控制、市场分析、工程 设计和科学探索等各个方面h 1 。在传感器网络中，大量传感器每时每刻不断感应 出大量监测数据，数据分析服务器必须及时地对这些监测数据进行分析和处理， 对气象、地理环境进行监测和预报。通过对超市销售记录进行分析，可以发现不 同商品之间的内在关联性，顾客群的消费习惯，发现这些规律有利于商家制定销 售方案和促销计划哺3 。对交通数据流的挖掘分析，有助于预测和消除交通拥挤情 况，进而提供各种交通信息。股票交易所、证券公司需要不断实时获取各种股票 和基金的价格以及各种新闻信息，并在此基础上进行大量的复杂实时分析挖掘， 如股票关联关系的发现、股价趋势分析、走势预测等。 数据挖掘融合了统计学、数据库、机器学习等技术，从存储在数据库、数据 仓库或其它信息库的数据中抽取出隐藏在数据之中的有用知识并提供给人们，帮 助人们对海量数据进行高层次的分析，为决策者进行决策提供了重要的依据，大 大提高了决策的科学性和降低了决策的盲目性儿利。典型的数据挖掘过程如图1 - 1 所示。 传统的数据挖掘方法通常针对静态数据进行挖掘，通过多次访问存储介质， 一般可以达到较高的精准度。由于数据流快速变化、潜在无限和数据规模巨大等 原因，使得传统数据挖掘技术难以满足数据流挖掘的要求。针对数据流的特点以 及在线挖掘的应用需求，要求研究人员提出新的挖掘方法和技术，以解决数据流 挖掘领域的问题。数据流挖掘算法的基本要求包括以下三方面嘈 1 伽： ( 1 ) 单次线性扫描。数据流算法按照数据的流入顺序依次读取数据一次。 ( 2 ) 低的时间复杂度。由于是在线算法，每次数据处理的时间最好是常数。 ( 3 ) 低的空间复杂度。相对于数据流的无限性，系统的内存容量十分有限。因此 算法的空间复杂度通常被要求在次线性空间内。 北京t 业大学1 = 学硕j 二学位论文 以上三点是数据流算法必须具备的，其他要求还包括算法的近似性和自适应 性、噪声和空值处理、在线回答等方面。 由于数据流的大规模出现，数据流挖掘技术逐渐成为热点研究问题，并越来 越广泛地应用于生产、生活当中。数据挖掘技术能够帮助人们提高生产效率、指 导实践活动、进行科学规律的探究，因此具有极大的研究价值和实际意义。 原始数据预处理后的数据 变换后的数据模型知识 1 2 数据挖掘技术 1 2 1 聚类分析 图1 - 1 数据挖掘过程 f i g 1 - 1p r o c e s so fd a t am i n i n g 聚类是指把数据集合中的数据对象划分为若干组不同的类或簇，并使得组内 对象的相似度尽可能的高，而组间对象的相似度尽可能的低。聚类分析作为一种 重要的数据挖掘方法，已经被广泛地应用于许多领域，包括动植物分类、疾病分 类、图像处理、模式识别和文本检索等n 。 在商业上，聚类可以帮助市场分析人员对客户的消费记录进行分析，从而发 现不同的客户群，并且用消费模式来描述不同客户群的特征。在生物学上，聚类 分析可以用来对动植物分类和对基因进行分类，获取对种群结构的认识。在电子 商务中，通过聚类得到具有相似浏览行为的客户，并分析客户的共同特征，可以 更好的了解客户，向客户提供更合适的服务。在信息检索领域中，聚类分析对文 档进行分类，改善信息检索的效率，从而提高人们的工作效率。 根据不同的思路和方法，可以将聚类算法分为以下几类： 基于划分的聚类方法：给定一个n 个对象或者元组的数据库，分割为k 个划 分，每个划分表示一个簇，并且k n 。同时满足如下要求：( 1 ) 每个组至少包含一 个对象；( 2 ) 每一个对象必须属于且只属于一个组。典型的划分方法有：k - m e a n 、 k - m e d i a 、p a m 12 l 、c l a r a n s 等。 基于层次的聚类方法：将给定数据对象进行层次的分解。根据层次的分解如 何形成，又可分为凝聚的和分裂的。凝聚的方法也称为自底向上的方法，开始时 每个成员都组成一个单独的簇，在以后的迭代过程中，再把互相邻近的簇合并成 2 第1 章绪论 曼曼曼曼曼曼曼曼量曼曼曼曼曼曼曼曼曼曼曼曼量曼曼鼍曼曼曼曼曼曼曼曼曼皇曼曼曼曼曼曼曼曼曼曼曼舅曼曼曼曼曼曼曼曼曼曼罡曼曼曼曼曼曼蔓曼曼曼曼曼曼曼曼皇曼曼曼曼曼 一个簇，直到所有的成员组成一个簇为止，分裂法则正好相反。典型算法如 a g n e s 、b i r c h 等。 基于密度的聚类方法：为了发现任意形状的聚类结果，提出了基于密度的聚 类方法。这类方法将簇看作是数据空间中由低密度区域分割开的高密度对象区 域。代表算法有：d b s c a n 、o p t i c s 、d e n c l u e 等。 基于网格的聚类方法：将数据空间划分为有限数目的单元，形成一个可以进 行聚类分析的网格结构。这种方法的主要优点是处理速度快，其处理时间与数据 的数目无关。代表性的算法有：s t i n g ，w a v e c l u s t e r ，c l i q u e 。 基于模型的聚类方法：基于模型的方法给每一个聚类假定一个模型，然后去 寻找能够很好的满足这个模型的数据集。这样一个模型可能是数据点在空间中的 密度分布函数或者其他。这种方法基于这样的假设：目标数据集是由一系列的概 率分布所决定的。基于模型的方法主要有两类：统计学方法和神经网络方法。基 于统计学模型的算法有c o b w e b n 那、a u t o c l a s s n 铂等，s o m n 5 3 算法基于神经网 络模型。 1 2 2 分类和关联规则 分类就是从数据对象集合中发现共性，并将数据对象集划分为不同类别的一 个过程。与聚类相比，分类属于有指导地学习。分类的目标是首先对训练数据进 行分析，使用数据的某些特征属性构建分类模型，给出每个类的准确描述，然后 使用这些描述，对数据对象集合中的其它未知类标号的数据集进行分类，或者是 为每个类产生更好的描述，即分类规则。分类也可以用于预测，预测的目的是从 历史数据记录中自动推导出对给定数据的趋势描述，从而能对未来数据进行预 测n6 l 。一般来说，分类输出的是离散的类别值，而预测的输出则是连续数值。分 类具有广泛的应用，例如医疗诊断、信用卡系统的信用分级、图像模式识别等。 分类器的构造方法有统计方法、机器学习方法、神经网络方法等。 关联规则挖掘是指揭示数据之间相互关系的一项数据挖掘任务，而这种关系 在数据中没有直接表示。关联规则可以识别出特殊类型的数据关联的模型，在零 售业被用来了解哪些商品频繁地被顾客同时购买，获得顾客购买行为模式后，可 以用来指导商家科学地安排进货、库存以及货架设计等。关联规则挖掘还被应用 在医学研究中，通过从成千上万份的病例中找出某种疾病的病的人共同特征，从 而为至于这种疾病提供帮助。关联规则还有很多其他应用，例如预测远程通信交 换机故障等。 许多实际的数据挖掘应用需要基于过去和当前数据对未来数据状态进行预 测。预测是利用历史数据找出变化规律、建立模型，并由此模型对未来数据的种 北京工业人学_ 学硕l 学位论文 类及特征进行预测。预测关心的是精度和不确定性，通常使用预测方差来度量。 预测可以看作是一种分类，差别在于预测主要是预测未来数据的状态而不是当前 状态。预测应用包括水灾预报、语音识别、机器学习和模式识别等。除了可以使 用时间序列分析和回归分析对未来值进行预测外，其他的技术也可用于预测。以 水灾预报为例，水灾预报是一个很困难的问题，其中一种可行的方法是在河流的 不同位置放置一些检测器，这些检测器用于收集与水灾预报相关的数据，例如水 面高度、降雨量、时间和湿度等。根据在上游河段由监测器收集到的数据就可以 预报河流潜在泛洪点的水位。预测必须根据采集数据的时间进行。 在时间序列分析中，数据的属性值是随着时间不断变化的。一般情况下，在 相等的时间间隔内( 例如日、周、小时等) 可以得到这些数据。通过时间序列图可 将时间序列数据可视化。时间序列分析有三个基本功能，第一，使用距离度量来 确定不同时间序列的相似性；第二，检验时间序列图中线的结构来确定时间序列 的行为。第三，利用历史时间序列图来预测数据的未来数值。 序列发现用于确定数据之间与时间相关的序列模式。这些模式与在数据或事 件中发现的相关的关联规则很相似，只是这些序列模式是与时间相关的。通过对 购物数据进行分析，可以发现一些简单的序列模式。例如，可以发现大多数购买 c d 唱机的顾客在一周之内还会购买c d 唱片。此时，时间关联规则在本质上与 序列发现是一致的。再比如，x y z 公司的网管定期分析w e b 日志数据以便了解 公司网页的用户是如何访问网页的，其中最感兴趣的是发现网页用户经常访问的 网页序列。经过分析发现，7 0 的用户在访问网页a 后都会发现产生如下的三种 行为模式之一： 或者 或者 。基于序列 发现的结果，可以决定直接增加一个从网页a 到网页c 的链接。 在偏差中包括很多有用的知识。数据库中的数据存在很多异常情况，因此发 现数据库中数据存在的异常情况是非常重要的。偏差检验的基本方法就是寻找观 察结果与参照之间的差别。孤立点是指不符合一般模型的数据。在挖掘正常类知 识时，通常总是把它们当作噪声来处理。当人们发现这些数据可以为某类应用( 如 信用欺诈、入侵检测等) 提供有用信息时，就为数据挖掘提供了一个新的研究课 题，即孤立点分析。发现和检测孤立点的方法已被广泛讨论，主要有基于概率统 计、基于距离和基于偏差等检测技术的三类方法n 。 1 3 国内外研究现状 1 3 1 密度和网格聚类方法 本文的数据流在线聚类算法结合了传统聚类方法中网格聚类和密度聚类的 优点。传统的聚类方法中，基于密度的方法能够帮助发现具有任意形状的聚类。 4 第l 章绪论 这类方法将簇看作是数据空间中由低密度区域分割开的高密度对象区域。其主要 思想是：只要临近区域的密度( 对象或数据点的数目) 超过某个涵值，就继续聚类。 d b s c a n 是基于密度聚类的典型算法，该算法将具有足够高密度的区域划分 为簇，如图1 2 所示，并可以在带有“噪声 的空间数据库中发现任意形状的聚 类n7 l 。d b s c a n 算法第一次使用了密度的概念，密度被定义为在某一距离内含 有点的最小数目。算法定义聚类为以最小规模和密度生成簇，使用直接密度可达、 核心点、边界点的概念，保证了核心点是构成簇的主要部分。通过规定单个异常 点不产生一个簇，算法还可以处理异常点问题。d b s c a n 的期望时间复杂度是 o ( n l o g n ) 。 图1 - 2 基于密度的聚类 f i g 1 - 2d e n s i t y b a s e dc l u s t e r i n g o p t i c s 算法的提出旨在解决d b s c a n 算法中聚类结果对参数设置较为敏 感的问题，o p t i c s 算法没有显式地产生一个数据集合簇，它为自动和交互的聚 类分析计算一个簇次序，这个次序代表了数据的基于密度的聚类结构，并存储了 每个对象的核心距离和一个适当的可达距离，基于次序信息提取聚类n 引。因此等 同于从广域的参数设置所获得的聚类。由于o p t i c s 算法的基本结构与d b s c a n 等价，因此与d b s c a n 有相同时间复杂度。 d e n c l u e 聚类算法基于一组密度分布函数，每个数据点的影响用一个数学 函数来形式化地表示，称为影响函数，它描述了数据点在邻域内的影响n 钔。数据 空间的整体密度可以被表示为所有数据点的影响函数的总和。然后聚类可以通过 确定密度吸引点来得到。该算法优点是有坚实的数学基础，概括了其他的聚类方 法，对于有大量“噪音”的数据集合，算法有良好的聚类特性。对高维数据集合 的任意形状的聚类，给出了简洁的数学描述。但是，这个方法同样要求设置密度 参数和噪音阈值，因此用户不同的参数设置会显著地影响聚类的结果。 基于网格的聚类方法把数据元素空间量化为有限数目的单元，形成网格结 构，所有的聚类操作都在这个网格结构上进行，如图1 3 所示。这种方法的主要 优点是处理速度快，其处理时间独立于数据对象的数目，仅依赖于量化空间中每 一维上的单元数目。有代表性的例子包括s t i n g ，w a v e c l u s t e r ，c l i q u e 。 北京t 业大学t 学硕十学位论文 原始数据网格聚类 图1 - 3 基于网格的聚类 f i g 1 - 3g r i d b a s e dc l u s t e r i n g s t i n g 是一种基于网格的多分辨率聚类方法，该算法将空间区域划分为矩形 单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成 了层次结构：高层的每个单元被划分为多个低一层的单元。每个网格单元属性的 统计信息( 例如平均值、最大值和最小值) 被预先计算和存储。高层单元的统计参 数可以很容易地从低层单元的计算得到。一个高层单元的分布类型可以通过它对 应的多个低层单元的分布类型，用一个阈值过滤过程来计算。如果低层单元的分 布彼此不同，阈值检验失败，高层单元的分布类型被置为空。s t i n g 算法的优 点是基于网格的计算独立于查询，并且网格结构有利于并行处理和增量更新。此 外，该算法的效率很高，s t i n g 算法通过一次扫描数据库来计算单元的统计信 息，因此产生聚类的时间复杂度是o ( 力) ，其中n 是数据对象的个数。 w a v e c l u s t e r 是一种多分辨率的聚类算法，它首先在数据空间上加入一个多 维网格结构来汇总数据，然后采用一种小波变换来变换原始的特征空间，在变换 后的空间中找到密集区域乜1 1 。小波通过压缩来缩减数据，能够自动地排除孤立点。 将小波变换应用到聚类中的好处是：数据的聚类能自动地显示出来，并“清理” 了周围的稀疏区域。w a v e c l u s t e r 在效率和聚类质量上均优于b i r c h 口羽， c l a r a n s 2 3 3 和d b s c a n 。 c l i q u e 聚类算法综合了基于密度和基于网格的聚类方法阱1 。该算法区分空 间中稀疏的和拥挤的区域，从而发现数据集合的全局分布模式。密集单位定义为 一个单元中的包含的数据点超过了某个输入参数，相连的密集单元的最大集合为 簇。c l i q u e 算法对于大型数据库中的高维数据的聚类非常有效，且对数据元组 的输入顺序不敏感，对于数据流在线聚类领域有较好的借鉴意义。 1 3 2 数据流聚类方法 由于数据流是海量的、时序的、快速变化的和潜在无限的，这些特性造成诸 多限制，使得传统的聚类方法不能直接运用到数据流聚类上。文献乜钉中总结了数 据流聚类算法的要求，认为在数据流中聚类要满足3 个要求：( 1 ) 压缩的表达；( 2 ) 6 分治的思想，使用一个迭代过程对数据流进行k - m e a n s 聚类。c a l l a g h a n 发展了 l o c a l s e a r c h 的思想，2 0 0 2 年提出s t r e a m 算法拉7 l ，采用批处理方式、分级聚 类的方法。首先对最初的m 个输入数据进行聚类得到o ( 勋个1 级带权质心，然 后将上述过程重复m o ( k ) 次，得到m 个1 级带权质心，再对这m 个1 级带权质 心进行聚类得到o ( 助个2 级带权质心；同理，每当得到m 个f 级带权质心时， 就对这些质心进行一次聚类得到o 个升1 级带权质心；重复这一过程直到得到 最终的o ( 妨个质心。但l o c a l s e 触h 和s t r e a m 方法都有一些缺点，即这 类算法必须指定k ，聚类的数目不能随便变动，对非凸形状等复杂形状的聚类也 无能为力，并且只保留了中心点的信息，造成很多有用信息的丢失。2 0 0 3 年 b a b c o c k 等使用一种称为指数直方图( e h ，e x p o n e n t i a lh i s t o g r a m ) 的数据结构来改 进g u h a 等人的算法，算法思想没有改变，仅仅用e h 结构来实现簇的合并啪1 。 2 0 0 3 年a g g a r w a l 等人提出一种解决数据流聚类演化问题的框架c l u s t r e a m ，由 在线和离线两阶段构成1 。在线阶段生成数据流的统计信息微簇，离线阶段利用 存储的微簇进行聚类。该算法实现了用户指定时间范围内的聚类以及聚类演化分 析。在此基础上，2 0 0 4 年a g g a r w a l 又提h p s t r e a m 算法，采用投影聚类解决数据 流的高维问题，并使用衰减因子随时间推进不断衰减历史数据，在聚类数目过多 时，删除最早加入的聚类。c l u s t r e a m 与h p s t r e a m 都是增量式的聚类算法， 在每个数据项到来时都进行处理，因此它们能作a n y t i m e 的回答。但该算法在线 阶段只能生成精度较低的微簇，经过离线分析才能得到精度较高的宏簇。同时算 法以k - m e a n s 算法为基础，对非凸形状聚类效果不好，无法发现任意形状的聚类， 且当噪声数据增多时，聚类质量急骤下降。 2 0 0 4 年s a r i e l 等证明了在低维情况下k - m e a n s 与k - m e d i a n 数据流的聚类过程中 存在核心子集( 舷d c o r e s e t ，从而可以使用子集( 屯d c o r e s e t 来代替原始数据集进行 聚类分析，并且运用这一方法改进t ( 1 + 西一a p p r o x i m a t e 的k - m e a n s 算法，保证插入 新数据时维持同样的精准性和对数级的空间复杂度1 。该算法说明，使用核心子 集代替原始数据进行聚类分析，可以降低运算量，从而提高聚类效率。 2 0 0 6 年f e n gc a o 等人提出的d e n s t r e a m 算法口引，扩展了传统聚类算法中基 于密度的方法d b s c a n ，可以处理任意形状的聚类。同时，算法强调了孤立点 检测问题，将孤立点与正常数据元素区分开来，有利于解决数据流中的异常点问 题。2 0 0 7 年k o m k r i t 提出的e s t r e a m 算法使用衰减因子，主要关注了数据流的 进化问题口3 。2 0 0 8 年c h e n 等人提出的d d s t r e a m 算法使用密度延迟技术来捕获 数据流的变化m 1 。2 0 0 9 年r e n 等人提出的s d s t r e a m 算法口引，使用聚类特征指数 直方图来保存核心微簇的信息。以上三种数据流聚类算法，均继承了c l u s t e a m 7 北京t 业大学_ 学硕七学位论文 算法的在线离线两阶段框架，精确的聚类结果需要通过离线阶段才能得到。 2 0 0 9 年s e b a s t i a n 提出的一种增量式的聚类算法，通过使用代表性的点来获得 聚类结果啪1 。p h i l i p 提出自适应的数据流聚类算法在不提供参数的情况下，可以 自动适应数据流的流速，同时还可以发现概念漂移情况 。m o h s e n 提出基于特 征的数据流聚类算法，首先建立一个特征群，然后通过自动识别算法区别出非重 要的特征并移出该特征群汹1 。这些思想的提出，对于本文研究的数据流在线聚类 分析有很好的启发意义。 通过对已有算法的总结和分析，可以发现目前的数据流聚类算法，大多数都 沿用了c l u s t r e a m 算法框架，即在线收集微簇和离线聚类分析两阶段。本文研究 的数据流在线聚类算法，使用户可以在线获得较高质量的聚类结果，算法具有较 好的实时性，能动态地反映数据流的变化。 1 4 主要研究内容及论文组织形式 1 4 1 本论文主要研究内容 数据流高速流动、快速变化和潜在无限的特点，对数据流聚类算法提出了新 的要求。传统的聚类分析技术已经较为成熟，并为数据流环境下的聚类提供了可 以借鉴的方法。通过对已有的数据流聚类算法分析，发现存在许多问题，如：在 线聚类效率低、算法的自适应性差、离线阶段才能得到精确的聚类结果、概要数 据结构更新不及时、算法不能随数据流的变化发现任意形状的聚类等。 针对这些问题，本文提出基于密度网格结构的数据流在线聚类算法，并从以 下几方面进行了研究和实验： ( 1 ) 密度网格结构 处理数据速度快是网格聚类方法的显著优点，因此将网格结构应用到数据流 在线聚类领域，满足了数据流聚类算法一次性读取数据、数据流速快的特点。用 统计值的形式将数据的概要信息存储在密度网格中，一方面保存了原始数据的基 本特征，同时也有效地节省了存储空间，满足了流数据算法压缩存储的要求。另 外，本文设计的密度网格结构容易实现维护和更新，有利于提高了在线聚类效率。 本文使用e n 值控制不同粒度的网格结构，并进行了大量的对比实验，得到 了不同精确度的聚类结果。用户可以根据需要均衡精度和效率，选择合适的网格 结构。此外，本算法定义了网格密度阈值c n m 和c m i l l ，并设置严c m 戕c m i n ，通 过在线调整厂，可以有效地控制聚类结果的质量，消除噪声数据对聚类的影响。 ( 2 ) 滑动窗口技术 滑动窗口可以反映当前数据流的情况，因此选择计数型的滑动窗口来控制数 据流。经过实验分析，在保证聚类精度的情况下，通过设置窗口滑动一次的步数 第1 章绪论 s t e p ，可以提高在线聚类效率。 ( 3 ) 聚类生成和簇合并规则 本文定义了网格邻居和网格簇的概念，采用优化的网格合并和更新规则，使 算法能够区分数据密集区域和稀疏区域，并较快地找到数据分布中存在的簇。 ( 4 ) 实验与分析 在本文算法的研究过程中，通过大量的实验分析和比对，不断调整和优化算 法，在聚类质量和效率方面均获得了较为满意的结果。 1 4 2 本论文的组织结构 本文结构按以下方式进行组织： 第1 章是绪论部分，介绍了本课题的研究背景及意义，聚类分析技术，并对 国内外研究现状进行了分析。 第2 章主要介绍本课题使用的相关技术，如密度网格结构、滑动窗口技术、 数据预处理技术等，通过与相似技术的对比，分析了本文所采用技术的优点。 第3 章介绍了本课题中算法设计的目的和设计思路，并详细介绍基于密度网 格的数据流在线聚类算法的总体框架以及算法各部分的具体设计，并对算法进行 了理论性分析。 第4 章的工作是算法实验和结果分析。共设计了四组实验，对算法的聚类精 度和聚类效率等方面进行了实验和对比，最后对实验结果进行了分析。 最后对全文进行总结，并对今后的研究工作进行展望。 9 北京下业大学工学硕上学位论文 1 0 第2 章密度网格和滑动窗口技术 本章介绍了数据流在线聚类算法中使用的相关技术，并分析了各项技术的优 缺点。首先定义了规范化的密度网格结构，通过数据预处理技术清除“噪声 数 据，并将数据流中的原始数据规范化，缩放在本文定义的密度网格结构中，在此 基础上进行聚类分析。同时，本文使用计数型滑动窗口来反映当前数据流的情况， 通过调整密度阈值c - 疆和，聚类算法能够自动适应数据流的动态变化。 2 1 概要数据结构 在数据流处理过程中，由于数据量远大于内存容量，系统无法在内存中保存 所有流过的数据，而数据流挖掘经常会要求读取这些数据。为了避免代价昂贵的 磁盘存取，数据流处理系统必须在内存维持一个概要数据结构，来保留扫描过的 信息1 。生成数据流概要数据结构的主要方法包括抽样、直方图、小波变换和哈 希方法等。 抽样( s a m p l i n g ) 是一种经典的统计技术，对数据流进行抽样是指以一定的概 率决定是否处理当前到达的数据项。根据各数据项被选中进行处理的概率是否相 同，抽样方法可以分为均匀抽样( u n i f o r ms a m p l i n g ) 和偏倚抽样( b i a s e ds a m p l i n g ) 两种h 0 。在均匀抽样中各数据项以相同的概率被选中进行处理，例如水库抽样和 精确抽样。在偏倚抽样中，各数据项被选中的概率各不相同，例如计数抽样。 直方图技术( h i s t o g r a m ) 是将一个大数据集划分为很多个连续的小数据集，这 些小数据集称为桶，每个桶都用一个数字来代表其特征。这种表示法直观、简洁， 能够很好地表示大数据集的轮廓，因此在一些商业数据库中采用。根据桶的划分 规则不同可以分为：等宽直方图( e q u i w i d t hh i s t o g r a m ) ，即各个桶的高度较为平 均h 1 1 。压缩直方 圈( c o m p r e s s e dh i s t o g r a m ) ，为频繁元素单独创建桶，对其他元素 采用等宽直方图h2 | 。v 优化直方图o p t i m a lh i s t o g r a m ) ，其划分桶的依据是使得 各桶的方差之和最小h 朝。 小波分析( w a v e l e t ) 是一种通用的数字信号处理技术。小波变换可以将输入的 模拟量变换成一系列的小波参数，从而能够方便地加以处理、存储、分析或近似 还原原始信号。该方法通过对原有数据做小波变换，保留原始数据主要信息的少 数几个小波参数作为概要数据保存1 。最常见且最简单的是哈尔小波，该算法将 整个数据集转换为一系列的小波参数，然后有选择地保留有限高能量参数，从而 近似模拟原始数据集。 哈希方法通过定义一组哈希函数( h a s hf u n c t i o n ) ，将数据从一个范围映射到另 北京丁业大学t 学硕【：学位论文 一个范围中去。常见的方法有b l o o mf i l t e r 方法h 5 。，s k e t c h 方法1 和f m 方法4 7 1 。 2 2 密度网格结构定义 本文关注的是数据流的在线聚类问题，使用密度网格结构保存数据流的概要 信息，以下逐步给出相关定义。 定义1 给定一个d 维的数据空间s = s lk s