数据流聚类算法研究

摘要：近几年来，流数据成为主流的数据形式之一。如网络入侵监测数据，股票数据等都是不断变化的流数据。聚类作为数据挖掘领域的主要技术手段之一，因此流数据的聚类也受到了众多学者的广泛关注。而流数据不同于静态数据的特性给流数据的聚类带来了挑战。本文总结了传统数据的聚类算法和流数据聚类挖掘的研究方法，并提出了对未来将群智能应用于流数据聚类算法的展望。

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

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

0引言

随着无线传感网络以及有关领域的相应发展，流数据日益成为主要的数据形式之一。例如无线传感器中的监测数据，网络入侵监测数据，以及金融产业中不断变化的股票数据等，即属于此类。这些数据都具有与传统静态数据不同的特性，诸如实时、有序、快速变化等。而对于目前较为有限的存储空间，数据流却又无法长期保存在计算机中，因此如何在线实时有效地处理这些数据，从中挖掘提取有用的知识，即成为数据挖掘领域的热点问题之一。

数据挖掘，亦称作知识发现，是指从大量的数据中挖掘得到人们感兴趣的知识的具体发现过程。现如今，人们可以通过多种渠道获取信息数据，随着数据量的大幅增长，如何从这些数据中找到有价值的信息，就成为数据挖掘的首要任务。数据挖掘的分析方法主要有以下几种：

（1）关联分析。两个或多个数据变量之间存在着某种相关性，这就是关联。通常情况下，数据库中庞大数据的关联性很难发现，而且关联分析又具有一定的不确定性，因此产生的规则必须带有可信度。

（2）分类分析。分类是数据挖掘领域的一个重要技术手段。一般分为训练学习过程和测试过程。例如，决策树、神经网络、k近邻算法、贝叶斯算法等都是常见的分类技术。

（3）聚类分析。作为数据挖掘、模式识别等工程和技术领域的研究热点之一，聚类分析表现了高度优良的性能和效果。聚类就是将一个整体的数据集划分成若干个簇，使得不同簇之间的相似性尽可能地小，而同一个簇中的相似性又尽可能地大。

综上所述，可知聚类技术是数据挖掘领域的重要技术方法之一，而数据流高速动态变化和一次扫描等特性却给数据流聚类带来了巨大的挑战。如何能够仅利用一次扫描就达到最好的聚类效果，以及如何生成任意形状的聚类，则是近些年来研究者们深度探讨的重点课题之一。

1传统的数据聚类算法

传统静态的数据聚类算法对于后期数据流聚类算法的进一步研究具有相当重要的现实意义，很多数据流聚类算法都是一些常见的经典聚类算法的变形。聚类算法一般可以分为三类，分别是基于划分的方法、基于层次的方法、基于密度的方法。在此，对这三类方法进行分别的探讨和解析，具体如下。

1.1传统的聚类方法

（1）基于划分的方法

（2）基于层次的聚类方法

基于层次的方法通常分为自顶向下和自底向上两种情况。在这些方法中，比较常用的就是Birch算法[1]。Birch算法中引入了CF聚类特征和CF tree聚类特征树这两个概念。具体过程为：首先全面扫描数据库，建立一个初始的聚类特征树；从根节点向下，计算与要插入的数据点间的距离，找寻最短距离，直至找到与该数据点最近的叶节点；如果吸收后大于阈值T，删除或分裂叶节点。

Birch算法适用于大数据集的聚类处理，具有较低的算法空间复杂度和时间复杂度，聚类效果良好。但是，birch算法多是利用半径来计算聚类的范围，因此对于非球状的聚类，就不会达到理想的效果。

（3）基于密度的聚类方法

基于密度的聚类方法是将具有相似的密度点的数据聚合在一起，可以根据不同的密度变化将聚类拓展到任意的地方，这就弥补了基于距离聚类只能产生球状实现效果的缺陷。但是这类算法的复杂度一般却比较高。

1.2基于群智能的聚类方法

群智能就是昆虫或者飞鸟等群体表现出来的群体智能，例如蚂蚁觅食，筑巢等过程中所表现出来的智能。近年来，众多学者将群智能应用于数据聚类中，取得了良好的聚类效果。群智能优化算法主要有蚁群优化算法（ACO）、粒子群优化算法（PSO）、人工鱼群优化算法等。

2003年，Merwe等人[2]最先提出了PSO与K-means算法结合的混合聚类算法。该算法利用K-means方法得到某组聚类的中心，并在粒子群初始化时将聚类中心赋值给某个粒子，其余粒子则随机初始化，之后运用基本PSO聚类算法完成聚类。

Azzag等人提出了一种基于蚂蚁觅食原理的聚类算法[3]。算法中，数据点可看作是具有不同属性的蚂蚁，而聚类中心就是蚂蚁所要寻找的“食物”， 由此数据聚类过程即成为蚂蚁寻找食物源的过程。此外，文献[4]继续提出通过蚂蚁自聚行为、达到聚类的蚁群聚类算法。该算法中，蚂蚁能够通过自我聚集行为构建一个树状结构， 即蚂蚁树（AntTree）。蚂蚁不仅代表数据，而且也代表该蚂蚁树的节点，初始状态时将蚂蚁置于一个固定点上， 该点相当于树根。接着蚂蚁在树上已经固定的蚂蚁身上移动， 寻找适合自己的位置。

将群智能应用于聚类挖掘中，能够获得明显优于传统聚类算法的实验结果，也不会象传统聚类算法（如K-means算法）一样那么容易产生局部最优解，只是算法的收敛时间较长。

2数据流聚类算法

由于数据流是随时间不断变化的，每单位时间段都有大量的数据到达，这就使得数据流中的数据将无法长期存储，此时若采用传统的数据挖掘聚类算法就无法得到很好的聚类效果。基于此，可知数据流聚类挖掘与传统的静态数据聚类即有很大的不同，具体分析如下：

首先，簇个数无法假定。由于数据流的不断变化，自然簇的个数也会相应地随之变化，因此无法预知簇的实际个数。

其次，聚类成任意形状的簇。在很多数据集，如网络入侵检测数据集中，聚类的分布情况通常是不均匀、且无规则的，因此能够发掘任意形状的聚类对于数据流聚类的应用则是至关重要的。

最后，处理噪声数据的能力。在众多数据流应用场景中，总会受到一些意外因素，如传感器网络中电池供电不足的影响等，这些均是数据流中产生的一些随机的噪声数据，如何能够分辨并处理这些噪声数据也是数据流聚类中的一大难题。

2.1数据流模型

流数据可以看作随时间不断变化的数据集合[5]。流数据集合为{X1，X2，X3，…，XN}，其中Xi包含两个数据项，一个是数据ai，另一个则是数据读入的时间点（时间戳）ti，即Xi=。而流数据将随着时间不断地发生变化，这就不可避免会有噪声数据出现于其中，可将其称为异常数据和孤立点数据。这些数据与研究中正常的数据行为模式并不一样，因而如何识别孤立点噪声数据也是数据流挖掘领域亟需解决的重点问题之一。

2.2窗口模型

在数据流聚类分析方法中，通常都基于时间窗口来进行。窗口模型一般可分为三种：界标窗口模型，滑动窗口模型和衰减窗口模型。其中，界标窗口模型则包括直方图方法、抽样方法、小波方法、哈希方法等。下面对这三种模型作以分别探讨。

在界标窗口模型中，其中之一的直方图技术就是将一个大的数据集分割成若干个小数据集。该技术能够直观地反映大数据集的轮廓梗概，因此在商业数据库中得到了广泛应用。另外，对于抽样方法来说，顾名思义，就是从大的整体数据集中抽取样本来代表整个数据集，并在样本查询中获得结果。而小波分析方法则与傅里叶变换相似，小波分析是将数据输入的模拟量，变换成一系列的小波参数，而大部分能量仅仅包含于少数几个小波参数中，因此选择利用少量的小波参数就能够还原出原始的信号。

分类之二的滑动窗口模型提出了一个时间窗口的概念。设有数据流DS=（a1，a2，a3，…，an），其中的ax是数据项，Xi是数据流中的数据样本点，Xt则是进入滑动窗口的时间点。W为窗口大小，tn是任意的时间点。只有时间窗口{tn-w+1，…，tn}内的数据才得以处理，而窗口外的数据则予以忽略。可用图1表示滑动窗口模型，具体如图1所示。

2.3在线-离线聚类方法

Clustream算法完全能够适应数据流快速到达，有序无限以及单遍扫描的特点，并且还能够挖掘出数据流的潜在演化特征。但是由于算法所采用的相似度标准是距离，这也就造成了该算法只能够产生球形的聚类结果。而且当数据流中存在噪声数据时，算法将会表现出不稳定性，而因为噪声数据无法被现有的微簇所接受，噪声数据就会创建新的微簇，进一步地，随着噪声数据的增加，微簇数量也随之增多。与此同时，算法又将限制微簇数量，由此一些微簇就必须要进行相应的合并或者删除，这就不可避免地降低了算法聚类结果的准确度。

而后，针对Clustream算法的这些不足，学者们又相继提出了多种解决办法。2004年，Aggarwal等人提出了HPStream （ High-dimensional Projected Stream Clustering method） 算法框架[7]。HPStream做出的主要改进有两方面：一是算法中使用投影聚类的方法来处理高维数据流的聚类问题；二是使用一个衰减簇的概念来代替Clustream中提出的微簇，以保存历史数据，从而利用衰减因子来实现不断衰减历史数据对整体聚类影响的不断衰减。

在已有研究的基础上，曹峰等人又提出了一种基于密度的进化数据流聚类算法DenStream算法[8]，同样这也是一种在线-离线两阶段处理方法。该算法主要提出三个概念：核心微簇，潜在核心微簇和离群微簇。算法实现可描述为：当接收到一个新的数据点时，算法首先判断这一数据是否可以被潜在核心微簇（p微簇）接收，如果不可以，再尝试将其合并到距离最近的离群微簇（o微簇）当中。如果合并后的离群微簇半径大于阈值，则将此离群微簇转化为潜在核心微簇。离线部分主要采用DBSCAN算法的变形来实现聚类。算法微簇维护的流程图如图2所示。

3未来发展趋势

FlockStream算法是将Denstream算法与一种多群智能Flocking模型相结合而加以设计并最终实现的。该算法采用分散的、自下而上的自我组织战略对相似的数据点进行聚类分组，数据点与仿生模型中的boid相关联并应用启发式策略进行聚类，在聚类效果上占有很大的优势[11]。该算法将仿生模型与数据流聚类算法相结合。获得了比较好的聚类效果。

通过以上分析可以看到，近几年来数据流聚类算法得到了许多学者的关注。同时，群智能算法具有鲁棒性和自组织等优点，并且能够在没有建立全局模型的情况下，对大量的数据搜索亦能取得良好的效果，群智能算法确实有着其它优化算法无可比拟的优势。进一步地，将群智能算法与传统的聚类算法相结合，也已获取了较好的聚类效果。因此在未来的研究中，可以将群智能优化算法应用到流数据聚类算法中，旨在实现聚类效果的高效性和稳定性。

参考文献：

[1]ZHANG T， RAMAKRISHNAN R， LLVNY M. BIRCH：An effieient data clustering method for very large databases[C]//Proc.1996ACM-SIGMOD Int.Conf. Magement of data（SIGMOD，96），103-114.

[2]MERWE D W van der ENGELBRECHTA P. Data clustering using particle swarm optimization[C] //Proc of IEEE Congress on Evolutionary Computation， 2003： 215-220.

[3]杨欣斌， 孙京诰， 黄道.基于蚁群聚类算法的离群挖掘方法[J].计算机工程与应用， 2003，（9）： 12-13+37.

[4]AZZAG H， MONMARCHE N， SLIMANCE M， et al. AntTree： a new model for clustering with artificial ants[C]//IEEE Congress on Evolutionary Computation， Canberra， Australia， 2003： 8-12.

[5]ENZINGER H M R， RAGHAVAN P， RAJAGOPALAN S . Computing on data streams. SRC Technical Note 1998-011. Digital systems research center： Palo Al t o， California， 1998.

[6]AGGARWAL C C， HAN J， WANG J， et al. A framework for clustering evolving data streams. FREYTAG J C， LOCKE M P C， ABITEBOUL S， et al， eds[C]// Proc. of the Int’l Conf. on Very Large Data Bases. Berlin： Morgan Kaufmann Publishers， 2003： 81-92.

[7]AGGARWAL C C，HAN J，WANG J，et a1.A framework for projected clustering of high dimensional data streams[C]//Proceedings of the 30th Informational Conference on Very Large Data Bases，2004：852-863.

[8]CAO F， ESTER M， QIAN W， et al. Density-based clustering over evolving data stream with noise[C]//Proceedings of the sixth SIAM international conference on data mining （SIAM’06）， Bethesda， 2006：326–337.

[9]CHEN Y X，TU L.Density-based clustering for real-time stream data [C]//Proceedings of the 13th ACM SIGKDD international conference on Knowledge Discovery and Data Mining.California：ACM，2007：133-142.

[10]黄德才，吴天虹.基于密度的混合属性数据流聚类算法[J]. 控制与决策，2010，（3）：416-421.

[11]FORESTIERO A， PIZZUTI C， SPEZZANO G. A single pass algorithm for clustering evolving data streams based on swarm intelligence[J]. Data Min Knowl Disc，2013，26：1–26.