数据流聚类算法研究

王高洋 李英梅

摘 要：随着传感器数据、互联网数据、金融数据（股票价格等）、在线拍卖以及事务日志（网站访问日志、电话记录日志）等的不断产生，数据流成为了主要的数据形式。流挖掘是数据库领域的研究热点，有很大的应用前景。本文首先简单介绍了数据流与聚类分析的概念，阐述了数据流中的聚类分析及其要求，详细说明了主要传统聚类方法的演变及各自代表性流数据聚类算法，并对其进行总结。在本文的最后，对流数据挖掘的前景做出展望。

关键词：聚类；数据流；数据流聚类；数据挖掘；数据流挖掘

中图分类号：TP311 文献标识号：A 文章编号：2095-2163（2014）05-

The Study of Data Stream Clustering Algorithms

WANG Gaoyang， LI Yingmei

（College of Computer Science and Information Engineering， Harbin Normal University， Harbin 150025， China）

Abstract： With the producing of numerous data from financial tickers， network traffic monitoring， web and transaction log analysis， and sensor networks， the stream data has become a kind of main data type. Streaming mining is a hot issue in the career of database and it has a good future. In this article， firstly gives a brief introduction to data stream， clustering analysis and other concepts related to clustering data streaming. Secondly the paper elaborately states the main traditional clustering methods and their typical clustering algorithms of data stream.After that， the paper also makes a summary to them. Finally， the paper makes the prospect of data mining.

Keywords： Clustering； Data Stream； Clustering Data Streaming； Data Mining； Streaming Mining

1 数据流与其挖掘算法的特点

1.1 数据流

最近几年出现了大量新类型的应用，这些应用的典型特点是数据以序列的形式予以发布，且每时每刻都在不断地产生，诸如传感器数据、互联网数据、金融数据 （股票价格等）、在线拍卖以及事务日志等。这些数据不同于传统的数据集，而是呈现为海量的、时序的、快速变化的和潜在无限的，该种数据形态即可称为数据流。

1.2 数据流挖掘算法的特点

基于数据流的特征及特性，将传统的方法用于数据流挖掘已然不再具有可行性。而经过对数据流挖掘算法的研究分析，可将数据流挖掘算法的实现过程特点归纳总结如下：

（1） 单次且线性扫描。在满足聚类要求的情况下，要尽可能少地扫描数据集，最好只是一遍扫描；

（2）空间和时间复杂度低。因为流算法的可用空间较为有限，且流算法还是在线算法，就需要算法能够快速处理任意数据项，以此而保证处理速度不小于数据流速度；

（3） 能够确保计算结果在理论上有较好的近似度；

（4） 能够适应不断变化的流速和数据；

（5） 能够有效地处理噪音和空值；

（6） 用户在线提出的任何时间段内挖掘请求均能得到迅捷响应；

（7） 算法在任意时刻都可提供当前数据处理结果。

在以上各条性质要求中，第（1）～（3）条是一个流数据挖掘算法的必要属性。早期的流数据挖掘算法也都是以这三项为目标设计的。

2 聚类分析及其在流数据挖掘中的应用

2.1 聚类分析

聚类分析，数据挖掘中的一个重要课题。聚类，是将一个给定数据集合中的相似对象划分成一或者多个组（也称作簇）的过程。划分后，同一簇中元素彼此相似，但相异于其它簇中元素。作为独立工具，聚类分析在众多领域已然获得了广泛应用。

2.2 数据流挖掘中的聚类分析

聚类分析经历了很多年的研究探讨，针对聚类静态数据集已经提供了许多方法，但是由于上述数据流自身特性却造成了诸多限制，而不能将传统聚类方法直接应用于聚类流数据。本次研究所需要的则是适用于流数据模型且满足其特点的高效聚类方法。

3 传统聚类方法的演变及其经典算法

3.1 扩展划分方法

划分方法就是将含有n个数据元素的数据集组织为k个划分（k≤n） ，其中的每一独立划分均表示一个簇[1]。迄至目前，已经提出的划分方法主要有k-平均算法（k-Means）及k-中心点算法（k-Medoids）等。

Guha 等人在文献[1-2]中将 k-平均算法进行了扩展，并将其用于处理流数据。这一扩展算法仅需要单遍扫描，而且需要的存储空间相对也较少，算法的时间、空间复杂度则可表示为 O（nk）和 O（nε ），其中 n 是数据元素个数，k是簇中心点个数，且ε<1； 相应地，Babcock等人又利用一种叫做指数直方图（EH， exponential histogram）的数据结构改进了Guha等人提出的算法。算法的思想并未改变，只是用EH结构进行了簇的合并。而在文献[3]中，Charikar 等人却利用分而治之（Divide and Conquer）的策略提高了 k-平均算法性能。该算法是将数据进行分块处理，其最终结果是通过各小数据块所计算的信息汇总得到的。同样地，也是基于 k-平均算法，OChallagham 等人更在文献[4]中提出了 Stream 算法。Stream 算法使用分级聚类技术，并且引入 LSEARCH 算法来改进 k-Means 算法，从而提高了性能，而且得到的结果簇也具有更高的质量。

0Callaghan于2002年成功研发LOCALSEARCH算法的基础上，更进一步提出了基于分治思想的流数据聚类算法，即Stream算法。在该算法中，对数据流采用一个迭代过程进行k-means聚类，并且将其移植至数据流环境中。具体过程为：首先，Stream算法确定聚类的数目K，再利用批处理方式及分级聚类方法。对最初输入的n个数据实现聚类，由此得到0（K）个一级的带权质心，重复上述过程n/O（K）次，从而得到n个一级的带权质心，接下来，再对得到的n个一级的带权质心进行聚类，继续得到0（K）个二级的带权质心。与其类似，当得到了n个i级的带权质心，也将对其进行聚类，继而得到0（K）个i+1级带权质心。重复此过程直至获得最终的O（K）个质心，并且任意i+1级带权质心的权值即是与其对应的i级质心权值之和。

由上可知，Stream算法是单层结构，因而表现了一定的局限性，现对其分析如下：

第一，聚类数目K需预先设定，且要对不断到达数据的先后顺序也较为敏感。

第二，由于算法聚类时，只有聚类中心点的信息被保留下来，因此容易造成有用信息的丢失。

第三，算法只是对当前处理的数据流的实际描述，而并非适用于聚类进化数据流的任何阶段。

第四，对于复杂形状的流数据，该算法也不适用。

3.2 扩展层次方法

层次方法，就是按层次分解数据元素的集合，并且得到一棵聚类构成的树。BIRCH算法，是该方法的经典模型，此外也还有ROCK、Chameleon及URE等算法问世。在文献[5]中，Aggarwal 等人就对 BIRCH 算法进行了扩展，从而提出 了CluStream算法。这是一个流数据聚类框架，聚类过程分成了两部分：联机微聚类（microclustering）和脱机宏聚类（macroclustering）。此后的许多流数据聚类算法也都随之而采用了这种两个阶段的处理框架。

在文献[6]中，Aggarwal等人对CluStream算法实施了进一步的改造，并将其应用于高维的数据流，HPStream算法也随之而提出。为了更好地支持高维数据流的聚类分析，投影技术和衰减簇结构在算法中相继获得了引用。现在，HPStream和CluStream即已成为两个具有广阔应用空间的流数据聚类算法。

在文献[7]中，Udommanetanakit 等人又对HPStream进行了补充，并以其为基础创新性地提出了E-Stream 算法。

下面即对Clustream算法框架及HPStream算法框架展开详尽的论述与分析。

3.2.1 Clustream算法框架

作为流数据聚类分析的一个框架。Clustream主要解决了STREAM 算法存在的两个问题：首先，CLustream是增量式的聚类算法，能在每个数据项来到时给出即时回应；并且，Clustream使用的时间框架是塔式的，能够给出不同的时间粒度聚类结果。

Aggarwal等人于2003年提出的进化数据流聚类Clustream算法包含两个部分，也就是在线聚类和离线聚类两部分。该算法首次提出将数据流看作一个随时间不断变化的动态的数据集，而不再只是将其看作一个数据整体进行聚类，并且Clustream算法适用于数据流聚类的进化分析，同时也具有良好的可扩展性，当数据流随时间变化较大时，即能产生质量高于其他算法的聚类。Clustream算法不仅能够给出动态数据流整体的聚类结果，还能够给出流数据任意时间段内的聚类结果，这一特性正是进行数据流进化分析不可或缺的必要结果。另外，算法由在线和离线两部分构成，其中的在线部分使用微簇来存储数据流的概要信息，并且引用金字塔时间窗口技术，同时遵照最近及最新的数据优先原则，使用不同的时间粒度实现了数据流的存储和处理。而离线部分，则将在线部分所保存的微簇信息，按照用户要求进行更精细的处理分析，从而得到了用户感兴趣的聚类结果。

虽然，Clustream算法通过时间框架的倾斜使用，CluStream保留了数据流变化的历史信息，当数据流发生剧烈变化时仍能够产生较高质量聚类结果。但是该算法却并未考虑历史数据衰减问题，也就是未能突出近期数据的重要性。另外，在将CluStream算法运用于聚类高维数据流时，具体表现也依然不佳。

3.2.2 HPStream算法框架

为了解决CluStream 存在的问题，Aggarwal 等人即于2004年提出了 HPStream 算法框架。该算法基于衰减簇结构，并随着时间推进衰减因子呈指数方式对历史数据进行衰减，当有过多聚类数目时，则删除最先加入聚类的数据；同时在每个衰减簇结构中，亦需维护要进行投影的维度列表，而且在微簇级别上进行了降维处理，从而在聚类过程中提升了微簇的纯度。

尤其是，文献[6]中通过对网络入侵检测和森林覆盖类型两种流数据集进行了对比仿真实验。结果表明 HPStream 在存储性能和处理速度上都要优于 CluStream。由此可以得出结论：HPStream 算法现已成为数据流聚类的主流算法之一。

3.3 扩展基于密度的方法

大多数聚类算法的距离度量都是基于对象之间的，此类聚类算法仅能发现球状簇，但在聚类任意形状簇时，却会存在一定困难。基于密度的方法即重点解决该类问题。具体来说，是将簇看成数据空间中利用低密度区域分隔而成的高密度数据区域[1]。DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法就是业界使用频率最高的一种基于密度的聚类方法。此外基于密度的算法还有DENCLUE、PTICS等。

在文献[6]中，Cao F 等人对 DBSCAN 算法进行了扩展，提出了基于密度的面向数据流的DenStream聚类算法。其中采用的是 CluStream 算法所提出的两阶段处理框架，并且引入了孤立点簇结构和潜在簇结构。实际上，当聚类请求到来时，DenStream 算法仍会采用 DBSCAN 算法以得到最终的聚类结果。

扩展层次和划分的方法，诸如 STREAM、HPStream 和 CluStream等算法存在的主要问题是：这些算法仅在聚类分析球状的数据流时表现良好，而当处理任意形状的数据流时，其效果表现即发生了走低的趋向，具体原因就在于这些算法采用的是距离度量。

针对这一状况，DenStream 算法则对基于密度的传统数据集聚类算法DBSCAN进行了扩展，旨在解决数据流形状任意时现有算法存在的聚类问题。与此同时，该算法又强调了孤立点的检测问题，即将孤立点和正常的数据元素进行了有效区分。

实现过程中，DenStream 算法使用了 CluStream 的两阶段处理框架，也就是同样地将聚类分析过程分为联机、脱机两部分。

具体地，联机部分中，算法维护两种微簇结构：潜在微簇（p微簇）及孤立点微簇（o微簇）。这两种微簇在结构上的区别仅在于各自的约束条件，即孤立点簇是指密度低于某阈值的簇，而潜在微簇则是密度超过此一阈值的簇。当有新数据点到达时，算法步骤为：

（1） 首先，尝试将其合并到最邻近的 p微簇中；

（2） 若尝试失败，则试图将其合并到其最邻近的 o微簇中。若合并成功，则将该o微簇的密度与阈值进行比较，而当该值大于阈值，该 o微簇将转换成 p微簇；

（3） 若仍无法找到其最邻近的o微簇，即新建一个 o微簇容纳此数据点。

对于脱机部分而言，当用户的聚类要求到来时，DenStream 算法先忽略密度不足的两类微簇，再使用DBSCAN 算法，对当前的 p-micro-cluster 和 o-micro-cluster 进行处理，得到聚类结果，并最终返回。

3.4 扩展基于网格的方法

基于网格的方法是将数据元素空间量化成为有限数目的单元，从而形成一个网格结构。所有聚类操作都在该网格结构上进行与实现。基于网格的算法常常与基于密度的算法结合起来使用，具体示例即如CLIQUE算法。这类算法的一个显著优点就在于算法运行速度非常快。

Chen 等人在文献[8]中提出了 D-Stream ，通过使用密度网格，即基于密度与网格，从而得到高质量的聚类结果。概括地说，该算法就是基于密度与网格的算法。而且，与 DenStream 算法相同的是，该算法也旨在解决任意形状数据流的聚类问题，既强调了孤立点检测，又依据密度而判断聚类；但与其不同的却是，该算法也还是基于网格方法的算法，因而采用了密度网格结构。

推演开来，D-Stream 算法也分为联机、脱机两部分：联机部分可将其接收到的每个元素映射到某个网格中，而脱机部分则计算网格的密度，并对这些网格进行基于密度的聚类。

具体地，联机部分不断地读入新数据元素，并将多维数据元素映射到其对应的多维空间中的离散的密度网格中，同时又将密度网格的特征向量进行即时更新。而脱机部分，则每隔一个时间空隙 （gap time）就要动态地调整当前簇，第一个时间隙后形成的可称为初始簇，此后，算法将周期性地移除零星簇，并调整已生成的簇。使用网格结构，将不再需要对大量原始数据进行保留，而只要对网格进行操作即可。

综上所述，由于联机部分仅是将数据元素映射到其对应的网格中，再也无需计算权值或距离，D-Stream将比不曾采用网格的算法实现起来更为高效，且更具良好的可扩展性，即算法速度不会随数据量的增大而变慢。然而，D-Stream 算法也存在相应的问题，就是处理高维数据流时，其需要的网格数量将可能偏大。

仍需提及的是，在文献[9]中，Bhatnagar等人又提出了ExCC（Exclusive and Complete Clustering of Streams）算法，该数据流聚类算法也是基于网格与密度的。该算法即专门针对簇聚类的完备性 （completeness） 与排他性 （exclusiveness），进而提出完备性聚类概念，亟需深入探讨和重点研究。

4 结束语

图1给出了聚类算法由面向传统数据向面向流数据的发展和演变过程。需要说明的是，该图并不完全，一些正在演进中的算法及思想并没有体现于其中。

图1 数据流聚类算法发展与演化示意图

Fig.1 The development and evolution of data stream clustering algorithms

虽然现已提出了大量优秀算法及处理框架，数据流的聚类分析仍是一个充满挑战的科研领域。可以预测，在未来的几年中，必将有更多、更为高效的算法相继出现，藉此解决相关应用领域知识与数据流挖掘技术的结合问题，从而在相当程度上推进相关领域如天文、物理等实际应用的迅猛发展，以期收获研究成果上的重大突破。

参考文献：

[1] GUHA S， MISHRA N， MOTWANI R，et al. Clustering data streams[C]//Proceedings of the Annual Symposium on Foundations of Computer Science， IEEE， 2000.

[2] GUHA S， MEYERSON A， MISHRA N， et al. Clustering data streams： theory and practice[J]. IEEE Transactions on Knowledge and Data Engineering， 2003，15（3）：515-528.

[3] CHARIKAR M， O'CALLAGHAN L， PANIGRAHY R. Better streaming algorithms for clustering problems[C]//Proc. of 35th ACM Symposium on Theory of Computing， 2003.

[4] L.OCALLAGHAN L，MISHRA N，MEYERSON A，et al. Streaming-data algorithms for high-quality clustering[C]//Proc.of ICDE Conf.of IEEE International Conference on Data Engineering， March 2002：685-694.

[5] AGGARWAL C， HAN J， WWANG J， et al. A framework for clustering evolving data streams[C]//Proceedings of the 29th VLDB Conference， Berlin， Germany， 2003.

[6] AGGARWAL C， HAN J， WANG J， et al. A framework for projected clustering of high dimensional data Streams[C]//Proceedings of the 30th VLDB Conference， Toronto， Canada， 2004.

[7] Udommanetanakit K， Rakthanmanon T and Waiyamai K. E-Stream： Evolution-Based Technique for Stream Clustering[M]. Springer-Verlag Berlin Heidelberg， 2007： 605-615.

[8] CHEN Y， TU L. Density-based clustering for real-time Stream data[C]//KDD07， San Jose， California， USA，August 12–15，2007：133-142.

[9] Bhatnagar V， and Kaur S. Exclusive and Complete Clustering of Streams[M]. Springer-Verlag Berlin Heidelberg， 2007：629–638