几种数据流聚类算法分析

朱 强，周 晓

（合肥师范学院，安徽 合肥 230601）

随着传感器技术和网络通信技术的不断发展和广泛应用，一种被称为数据流的新的数据时时刻刻地不断产生了，例如在网上商城等web应用、网络监控、实时监控、卫星遥感系统、股票交易系统、物联网、气象与环境监控等动态环境当中产生了大量的实时数据.这类数据与传统的存储在物理存储介质上的静态数据不同，它是动态的，像水流一样的形式存在，是一种实时持续到达、数据规模不能预知且宏大、到达速度快、数据到达无序、突变的数据[1].因此处理数据流只能进行单遍扫描算法，一经处理的数据不能或没有必要再次提取或者提取的代价较高；传统的数据挖掘算法应用于数据流上效果不同理想，如何高效地从数据流中获取有价值的信息是目前数据挖掘领域的重要研究内容.聚类分析是数据挖掘的一个重要研究方法，基于数据流的聚类分析也引起了越来越多人的关注，他们提出了多种基于数据流的聚类分析算法，较好地解决了传统聚类分析的不足.本文首先介绍了数据流和基于数据流的聚类分析算法应该满足的特点，然后讨论了几种数据流聚类算法，并对其进行分析和评价.

1 数据流定义与窗口模型

数据流是一种实时持续到达、数据规模不能预知且宏大、到达速度快、数据到达无序、突变的数据序列X1,X2,…,Xn…,序列中每一个数据Xi假设是d维，xi=xi1,xi2,…,xid,每一项数据到达的时间假设是T1,T2,…Tn,…,则数据流可可以看作是带有时间标记的一系列数据项：<X1,T1>,<X2,T2>,….基于数据流的数据挖掘往往是在某一个时间段内进行，也就是在时间窗口内进行，比较常用的时间窗口模型有三种[2]：

1.1 界标窗口模型(Landmark Window Model):该种窗口模型是指被用来挖掘的数据流为从数据流开始到当前到达的所有数据项的集合，即{X1,X2,…,Xn},其中是Xn当前时刻的数据项，且窗口大小随着数据的到达不断增加.

1.2 滑动窗口模型(Sliding Window Model):该种窗口模型是指被用来挖掘的数据流从当前时刻开始，到最近到达的N个数据项的集合，N即是滑动窗口的大小，数据项集合为{Xi-N+1…Xi},其中Xi是当前时刻的数据项.这种窗口模型的窗口位置在时间轴上随着数据流不断滑动.

1.3 衰减窗口模型(Damped Window Model):该种窗口模型是指被用来挖掘的数据流为从数据流开始到当前到达的所有数据项的集合，但个数据项被赋予不同的权重，较早到达的数据项具有较小的权重，较晚到达的数据项具有较大的权重.各数据项的权重根据某种衰减函数随着时间不断地衰减.

用户根据需求选择其中一种或几种窗口模型应用于数据流的挖掘，不论采用哪种窗口模型，一般数据流挖掘都采用相同的挖掘框架，如下图1所示.

该框架下，算法需要在内存中维护一个概要数据结构[2]，概要数据结构是一种利用较少的内存空间从已往数据流中提取数据特征或信息而形成的数据结构.当新的数据项到达时，数据流挖掘算法通过计算来维护和更新内存中的概要数据结构.当用户发出挖掘请求时，算法从概要数据结构中读取信息并处理，再把处理的结果反馈给用户.不同的概要数据结构对挖掘结果的影响很大，因此，设计出新的概要数据结构也是数据流挖掘的一个重要研究内容.

2 几种代表性的数据流聚类算法

数据流聚类分析是数据流挖掘的一个重要研究方向，而数据流本身的特点也决定了对于一般数据的聚类分析算法不适合数据流聚类.数据流聚类算法有以下几个基本的要求[3]：

2.1 由于数据流是源源不断地持续到达，因此对于数据流聚类算法的速度要很快，甚至实时响应，而传统的聚类数据是静态的，对时间复杂度的要求并不苛刻.

2.2 由于数据流持续无限、规模庞大，因此整个流数据集不可能在存储在内存或硬盘上，须对数据流进行必要的概化舍弃处理；同样，对数据流的分析也不像传统的聚类那样可以多次扫描数据，而只能是单遍扫描.

2.3 数据流数据往往都是高维的、海量的，因此其算法的复杂性比传统算法更高.目前影响比较大的数据流聚类算法有以下几种：

2.3.1 CluStream数据流聚类算法[4]

数据流聚类算法CluStream是有C.Aggarwal等人提出的，它把不是把数据流看成一个整体，而是看成是一个随时间变化的过程进行聚类分析，因此，算法优点是当数据流随着时间变化较大时，它的聚类结果质量更高.而且，CluStream算法可以给出任意时间范围内的聚类结果及进行数据流的进化分析.CluStream算法的聚类过程包含两部分或两阶段：在线的微聚类和离线的宏聚类.在线部分用micro-cluster定时存储数据流的摘要信息，以增量的方式对数据进行处理和更新，并在金字塔时间框架下分级保存摘要信息；离线部分是用micro-cluster在在线部分保存的中间结果再进行分析得到指定时间范围内的聚类结果.CluSTream算法提出的这个两阶段处理框架被之后的许多数据流聚类算法所改进和采用.但是由于算法的micro-cluster采用类似于BRICH算法所用的特征值记录它所产生的子聚类，因此算法对球形的聚类结果很好，但对其它形状聚类并不能产生很好的聚类结果.

2.3.2 HPStream数据流聚类算法[5]

Aggarwal等人后来为了解决高维数据流聚类问题又提出了一种基于投影的数据流聚类算法HPStream，该算法是将投影的技术应用到数据流聚类中，在相关维形成的子空间内算法解决了高维数据的稀疏性问题，提供了聚类的质量.HPStream算法使用衰减结构，利用可调衰减因子较好地将当前数据和历史数据结合起来，在数据流的进化中逐步删除过期的历史数据，体现了当前数据的重要.但是HPStream算法和CluStream算法一样，对球形的聚类结果很好，但对其它形状聚类并不能产生很好的聚类结果.

2.3.3 DenStream数据流聚类算法[6]

DenStream数据流聚类算法是由Cao等人提出的一种基于密度的聚类算法，它改进了DenStream算法，采用CluStream算法中提出的两阶段处理框架，引入了核心微聚类簇、孤立点微聚类簇和潜在微聚类簇等概念以获取较准确的聚类结果,可挖掘在有噪声环境下衰减窗口内数据流中任意形状的簇.但因为采用全局一致的绝对密度作参数,所以聚类结果对参数值比较敏感，同时，由于需要统计输入数据带有时间特性的特征向量及大量密度计算，所以其时间复杂度也比较高.SDStream算法[7]是在DenStream算法的基础上，利用滑动窗口来处理数据流，虽然减少了时间复杂度，但是却只能获取到最近数据流中任意形状的聚类簇.

2.3.4 D-Stream数据流聚类算法[8]

D-Stream数据流聚类算法是一种典型的数据流网格聚类算法.网格聚类往往是将数据空间首先划分为由一定数目的网格单元组成的网格结构，然后将数据流映射到网格结构中，形成网格密度的概念，相邻的高密度网格的集合代表一个聚类，聚类操作在网格上进行.D-Stream算法在线部分将数据映射到一个网格，在离线部分计算网格的密度，从而形成基于密度的簇.D-Stream算法使用密度衰减技术来捕获数据流的动态变化，通过实时地调整簇，以探索衰减因、数据密度和簇结构间的关系，合理地移除属于离群的点的稀疏网格，提高系统的空间和时间效率.D-Stream算法能有效地对高速数据流进行聚类而不损失聚类质量，能发现任意形状的簇，能准确地识别实时数据流的演化行为，但其聚类效果明显会受到网格粒度的影响.

3 结论

基于数据流的聚类算法得到了众多人员的研究，也产生了很多的聚类算法成果，但是在实时数据流聚类、高维数据流聚类以及提高聚类的质量和降低时间复杂度等方面还存在不足，数据流的模糊聚类还处于起步阶段，这也是下一步努力的方向.

〔1〕万仁霞.数据流聚类算法研究[D].上海：东华大学，2009.

〔2〕曹锋.数据流聚类分析算法[D].上海：复旦大学，2006.

〔3〕赵焕平，曹蕾.基于密度的数据流聚类算法[J].南阳理工学院学报，2012,4（2）:73-75.

〔4〕C.Aggarwal,J.Han,et al.A framework for clustering evolvingdata streams[J].Proc.of VLDB,2003:81-87.

〔5〕C.Aggarwal,J.Han,et al.A framework for projected clustering of high dimensional data streams[J].Proc.of VLDB,2004:850-859.

〔6〕F.Cao,A.zhou,etc.Density -based clustering over an evolving data stream with noise [J].Proc.of the SIAM Conf.on Data Mining.2006.

〔7〕Ren J D,Ma R Q.Density-based data streams clustering over sliding windows.Proceedings of the 6th International Conference on FKD,2009:240-251.

〔8〕Chen Y X,Tu L.Density-based clusteing for real-time stream data.Proceeding of the 13th ACM SIGKDD,2007:130-140.