第27卷第2期通化师范学院学报Vol.27No.2
2006年3月JOURNALOFTONGHUATEACHERS’COLLEGEMar.2006
数据流聚类算法研究①赵法信1,刘俊岭2(1.通化师范学院网络中心,吉林通化134002;2.沈阳建筑大学计算中心辽宁沈阳110004)
摘 要:数据流是一类新的数据对象,流挖掘是数据库领域的研究热点,有很大的应用前景.本文首先综述了传统聚类算法的分类及其各自特点,并对它们进行了分析评价.然后结合流聚类分析的要求,对目前最新的几个数据流聚类研究成果进行了分析,并对数据流聚类进一步的研究方向进行了讨论.
关键词:数据挖掘;聚类分析;数据流;数据流聚类中图分类号:TP311.13 文献标识码:A 文章编号:1008-7974(2006)02-0029-04
近年来,越来越多的应用产生数据流,它不同于传统的存储在磁盘上的静态的数据,而是一类新的数据对象,它是连续的、有序的、快速变化的、海量的数据[1].典型的数据流包括网络与道路交通监测系统的监测信息数据、电信部门的通话记录数据、
由传感器传回的各种监测数据、股票交易所的股票价格信息数据以及环境温度的监测数据等.数据流分析是数据流研究的一个重要方向,目前的研究主要包括数据流聚类、分类、频繁模式以及数据流OLAP等[3][4][5].数据流本身的特点决定了数据流
聚类与传统数据聚类的不同,本文根据数据流本身的特点分析了数据流对聚类的要求以及数据流聚类方面的最新研究成果,
并对数据流聚类下一步的研究方向进行了讨论.
1 传统聚类分析随着数据聚类的蓬勃发展,各种聚类算法相继提出,每一种算法都是针对不同的情况而设计的,在数据挖掘领域对聚类算法的要求主要有以下几个方面[2]:算法的可伸缩性、对所处理属性值的要求、对数据分布的适应性、最少的参数和确定参数值
的领域知识、有效地识别噪声数据、对于输入顺序的敏感性、高维性、基于约束的聚类以及聚类结果的可解释性和可用性.许多聚类算法都是为特定的领域设计的,都有各自的特点和应用范围,因而任何聚类算法都不可能在每个标准上都优越于其它算法.传统的聚类算法主要分为基于划分的方法(如K-means
[6])、基于层次的方法(如BIRCH[7])、基于密度的方法(如DB2
SCAN[8])、基于网格的方法(如CLIQUE[9])及基于模型的方法(如COBWEB[10]).本文对这些算法进行了研究,对它们的性能
在以下几个方面进行了比较分析:
表1 聚类算法的比较
类别算法聚类质量可伸缩性聚类形状输 入敏感性噪声处理能力数据类型基于划分K-means差球状是差数值PAM差球状是好数值CLARANS好球状是好数值基于层次AGNES差球状不差数值BIRCH好好球状是好数值CURE好好任意不好数值ROCK好好任意不好分类Chameleon较好好任意不好数值基于密度DBSCAN好好任意不好数值OPTICS好好任意不好数值DENCLUE较好一般任意不好数值基于网格STING一般好任意不好数值CLIQUE一般好任意不好数值WaveCluster一般好任意不好数值基于模型COBWEB好差特定不好分类CLASSIT好差特定不好数值
・92・①收稿日期:2005-05-08
作者简介:赵法信(1974-),男,河南浚县人,硕士,通化师范学院工程师,主要研究领域为数据仓库与数据挖掘.
© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net2 数据流聚类分析算法数据流是数据点x1,x2,……,xn的一个有序的序列,它只能被按顺序访问,而且仅能被扫描一次或有限的几次[10].数据
流是快速变化的,因而,流聚类算法要能够跟上流的速度并抓住流的特征;数据流是连续的,所以对数据流聚类要能随时间而不断地进行;数据流是海量而有序的,不可能保证存贮整个数据集,只能分析一定范围内的数据,因而要有效地利用有限的空间与时间.本文首先介绍了数据流聚类分析的特点,然后介绍了现有的流聚类算法,并对这些算法进行了分析与评价.
2.1 数据流聚类分析特点数据流本身所具有的特征使得传统的聚类算法不可能(甚至不能)直接应用于数据流聚类.因而,与传统的聚类算法相比,
数据流聚类算法还应当具有以下特点[1]:
①一遍扫描:在满足聚类要求的情况下,要尽可能少的扫描数据集,最好是一遍扫描;②有限的内存及存贮空间:由于数据流具有无限连续性,不可能存贮如此海量的数据,因而要对数据流进行概化或有选择的舍弃;③实时性:每一个记录的处理时间要尽可能的少,要能够跟上流的速度.
2.2 数据流聚类算法目前,学术界对数据流的研究刚刚起步,数据流的聚类算法也处于初始阶段.现有的算法主要有数据流聚类理论与实践[11][12],通过数据流窗口维护方差和中值[13],聚类演变数据流的一个框架[14],用K平均聚类二进制数据流[15].这些都是基
于划分的流聚类算法,下面将对这些算法进行介绍.
(1)数据流聚类理论与实践.
分而治之(divide-and-conquer)的策略可以解决流聚类的空间代价问题(小空间聚类),该算法的运行时间是O(n
1+
ε
),
使用O(n
ε)(0的内存并扫描一遍数据集.该聚类算法特点是一次扫描数据,并在限定的空间、时间内聚类.
分而治之算法思想如图1所示:首先将数据集S分为大小相等的n个不相交的片段x
1,x2,...xn,然后将每个片段聚为k
个类,最后将各个片段的聚类结果(nk个带权重的中值点)聚成k个带权重的中值点,即k个类.
图1 分而治之思想示意图分而治之思想在流聚类中的应用的基本算法:
①输入第一批m个点,将其聚为2k个中值点,每个点的权重是赋于它的点的个数;②重复上述过程直到已输入m2/(2k)个原始点,此时可以得到m个中值点;③将这m个第一层中值点聚类成2k个第二层中值点并处理;④通常,维护最多m个i层中值点,点数一达到m,就产生2k个i+1层的中值点;⑤当所有的数据都到达(或需要仅对截止到目前的所有点
进行聚类)时,将所有中值点聚类为最后k个中值点.
(2)通过数据流窗口维护方差和k-Medians.利用滑动窗口解决数据流中的数据过时问题,并在滑动窗口中维护方差和k
-Medians.该算法是一个在线维护聚类的算法,更能真实反映数据流的特征.
滑动窗口模型:设N为窗口的大小,那么始终只有来自于数据流的最后N个元素才被认为和查询相关.最近的N个元素被称为活动的数据元素,其余的元素被称为废弃元素(expiredelements),且不能再用于回答查询或参与数据集统计.一旦一个数据元素已经被处理过就不再将其保存在内存里,在以后的时间里它就不能被重新获取用于进一步的计算.应注意的是,在要求存贮整个活动数据集的算法中不能使用此模型.
图2 数据流滑动窗口示意图如图2所示,在这个模型中,滑动窗口大小为N,并将窗口N分为m个桶,Bm3称之为后缀桶,它包含了在桶Bm之后到达的所有元素的信息.后缀桶中的信息是在需要时临时计算的,无需在线维护.该算法通过在线维护不等式f(B
i,i-1)
>
・03・
© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net2f(Bi-13)(i>2,f(Bi)为基于桶的代价函数)来限制所生成的桶的数量,当相邻的两个桶不满足不等式时将桶合并,
这样就
保证了在线维护的桶的数量不会超过O(logN/τ)(τ=1/L,L为每个桶中所维护的数据的层数).同时,该算法通过在线维护不等式f(B
i)≤2f(Bi3)来保证聚类结果的精确度,从而使该算法的代价与最佳K-median的代价之比不会超过2O(1/τ).该
算法基于滑动窗口模型的流聚类相关处理过程如下:
流聚类过程中桶的生成及维护方法.①对于数据流中的每一个数据点,将其放到桶B1中,当桶B1中的点数超过K时,创建一新桶B1,并对所有的桶重新编号;②如果桶Bm的时间戳超过N,就删除该桶;③对所有桶按从近到老的顺序进行扫描,
搜寻满足桶编号i>2且f(Bi,i-1)≤2f(Bi-13)的所有i值,并从中找出最小的i值,并将桶Bi和Bi-1合并.
桶中数据的维护方法.桶中共存贮L层数据,每层m个点(
m
L
=N),每层满m个点时,向下一层聚成K个中值点,该思
想借鉴了上文中分而治之的策略.
桶合并方法.桶中相应层的数据按自顶向下的顺序进行合并,若该层中的数据点数超过m,就向下一层聚类,聚类结果和下一层中的数据合为一起.
聚类方法.对Bm及Bm用K-median方法分别聚成K个类.
精确聚类方法.通过减去Bm中非活动对象,对Bm和Bm3一起进行聚类.
(3)聚类演变数据流的一个框架.以上两个算法只是考虑当前的时间窗内的聚类描述,并没有考虑历史信息的因素.这样,
当数据流速相当大时,聚类质量较差.为解决这个问题,该框架将聚类过程分为两个组件,一个是在线微聚类组件,用于阶段性存贮详细的摘要统计信息,由于该组件仅处理摘要统计信息,因而能够处理流速较大的数据流;另一个是离线宏聚类组件,利用该组件,分析者可以根据需要输入不同的参数(如时间段或类的个数)来对在线微聚类存贮的摘要统计信息进行聚类,以便能够从不同角度对数据流的聚类结果进行分析,从而提高了聚类结果的可理解性.同时,在线微聚类所存贮的详细的摘要统计信息,也为离线宏聚类高质量的聚类结果提供了保障.
在线微聚类过程中,微聚类按金字塔时间框架所产生的时间序列及时以快照的形式存贮.这个框架一方面考虑了存贮需求,另一方面兼顾了离线宏聚类在不同时间段恢复摘要统计信息的能力.金字塔时间框架定义如下:
①每一层最多存贮αL+1个快照.②第i层快照的时间间隔为αi且该快照所对应的时间要能被αi整除;③第i层仅保留不能被αi+1整除的快照;④在T时间段内最多维护(
αL
+1)logα(T)个快照.其中,金字塔最大层次数=logα(T),T表示从数
据流开始至今所逝去的时间.α为大于等于1的整数,它决定了金字塔时间框架的时间粒度.L为大于1的整数,它的大小决定了金字塔时间框架所产生的快照的精度.
如图3所示,当前时间为T=55,α=2,L=2;则最大层数为5,每层最多5个快照.最终得到的金字塔时间序列为16
,
24,32,36,40,44,46,48,50,51,52,53,54,55.
图3 金字塔时间框架存贮的快照序列(α=2,L=2)
在线微聚类过程.
①初始化:将初始的n个点用标准k-means算法聚为q个类,每个类中仅存贮统计信息(q>>k);②对每一个新到达的点,有如下处理:将其放置到原有类中;产生一个新类,同时删除一个旧类或合并两个旧类以维持总类数不变;在进行上一步的同时,若当前时间能被2i整除,则存贮当前时间所对应的微聚类的快照并按时间戳索引,同时删除过时的快照离线宏聚类过程.①用户输入时间范围T及聚类数K;②从磁盘上取出该时间范围所对应的微聚类,用k-means变种算法将其进一步聚为K个类.