一种基于密度和约束的数据流聚类算法

付家祺 陈坚 淳浩 年青

摘 要： 文章在传统聚类算法的基础上，提出了一种基于密度和约束的数据流聚类算法——C-DBDStream（Constraint and Density Based Clustering of Data Stream）。该算法使用数据流聚类在线和离线两阶段框架。在线聚类阶段使用衰减窗口模型，对数据流中的数据对象进行初步的聚类，应用约束条件生成微簇，并将实例级的约束扩展到了微簇级，并将结果以快照的形式保存下来为下一阶段做准备；离线聚类阶段则利用微簇级约束规则聚类，采用DBSCAN算法中的密度可达寻找密度连通区域以产生最终结果。经实验证明，与CluStream算法的对比中，C-DBDStream算法提高了聚类效果。

关键词：数据流；聚类；密度；约束

中图分类号：TP311.13 文献标志码：A 文章编号：2095-2945（2018）12-0001-05

Abstract： Based on the traditional clustering algorithm， this paper proposes a data stream clustering algorithm based on density and constraint， C-DBD Stream （Constraint and Density Based Clustering of Data Stream）. The algorithm uses data flow clustering online and offline two-stage framework. In the online clustering stage， the attenuation window model is used to cluster the data objects in the data stream， and the constraint conditions are applied to generate the micro-clusters， and the constraints at the instance level are extended to the micro-cluster level. The results are saved in the form of snapshots and prepared for the next stage. In the off-line clustering stage， the micro-cluster level constraint rules are used to cluster， and the density in DBSCAN algorithm can be used to find the density connected region to produce the final result. Experimental results show that compared with CluStream algorithm， C-DBDStream algorithm can improve the clustering effect.

Keywords： data flow； clustering； density； constraints

随着时代的进步和发展，大数据的发展尤为迅猛，静态数据已经无法满足日益增长的需求，数据流在各个领域的发展和应用越来越广泛。聚类分析是针对数据流挖掘的一种重要手段，数据流聚类算法有以下特点：单边扫描、数据抽象、近似结果、快速处理。已有的数据流聚类算法大都是无监督的学习方法，如果利用一些约束条件，可以改进现有的数据流算法，构造性能优异的半监督数据流聚类算法。

本文在详细分析数据流的特征和约束条件的性质的基础上，对基于约束条件的聚类进行了研究，并提出了一种基于密度和约束条件的数据流聚类算法——C-DBDStream。该算法将聚类过程分为两个阶段：在线部分应用约束条件和衰减窗口模型，将数据流中的数据对象扩展到微簇级，并将结果以快照的形式保存下来；离线部分是在前面的基础上，利用扩展的微簇级约束来聚类，利用DBSCAN算法中的密度可达寻找密度连通区域，聚类出最终结果。最后通过在KDDCup99等数据流上的实验测试，验证了算法的正确性和有效性。

本文第1节介绍算法中的基本概念，第2节给出C-DBDStream算法，详细解析算法的思想和执行过程，第3节提供实验结果及分析，第4节对全文做总结并指出后续的研究。

1 算法使用的基本概念

定义1实例级约束D=（X1，X2，…，Xn）为一个数据集，（C1，C2，…，Ck）是数据集D的聚类结果，则有ML和CL约束：

？坌ML（Xi，Xj），1

？坌CL（Xi，Xj），1

上图的约束关系可以表示为：ML（a，c）、ML（a，e）、ML（I，j）、ML（g，k）、ML（h，f）、ML（b，d）、CL（a，i）、CL（b，h）、CL（c，l）、CL（d，g）。

定义2微簇级约束MC=（MC1，MC2，…，MCn）为一个微簇集合，（C1，C2，…，Ck）是微簇集MC的聚类结果，那么有ML和CL约束：

？坌ML（MCi，MCj），1？燮i？燮n，1？燮j？燮n，若MCi∈Cm，1？燮m？燮k，则MCj∈Cm。MCi、MCj必须在同一个簇中；

？坌CL（MCi，MCj），1？燮i？燮n，1？燮j？燮n，若MCi∈Cm，1？燮m？燮k，则MCi？埸Cm。MCi、MCj必须在不同的簇中。

定义3实例级约束扩展到微簇级约束xi、xj分别为微簇MCi、MCj上的数据对象，那么有：

er）带约束的核心微簇是由核心对象的？着邻域内包含核心对象间的约束关系及所有数据对象构成的一个集合。在某个时刻t用CCMCi（wi，ci，ri，sni，coni）来表示。

xi1，xi2，…，xin为约束核心微簇CCMCi中的数据对象，这些数据对象都是核心对象，并分别在ti1，ti2，…，tin的时间点按序到达。

wi表示CCMCi的权重， ；

ci表示CCMCi的中心， ；

ri表示CCMCi的半径， ，ri？燮？着，

dist（ci，xij）表示ci与xij之间的欧氏距离[14]；

sni表示CCMCi内数据对象的真实序号的集合；

coni表示CCMCi内数据对象的ML和CL约束关系，coni={MLi∪CLi}，MLi={ML（s=0/1，i，p），…}，CLi={CL（s=0/1，i，q），…}，s表示约束条件类型，i表示该约束核心微簇的序号。当s=0时，p、q等表示数据对象的真实编号，表示该核心微簇與数据对象之间的约束关系；当s=1时，p、q等表示其他的微簇的序号，表示该核心微簇与其他微簇之间的关系。

定义5带约束的潜在核心微簇（potential constraint core micro cluster）简称约束潜在核心微簇（PCMC），用PCMCi（wi，，，sni，coni）来表示。

xi1，xi2，…，xin是PCMCi中的数据对象，在ti1，ti2，…，tin的时间点按序到达。

wi表示PCMCi的权重，wi=？撞f（t-tij），wi？叟βμ，β为潜在核心阀值，0<β？燮1；

为微簇中数据对象的加权线性和，=？撞f（t-tij）xij；

为微簇中数据对象的加权平方和，=？撞f（t-tij）x；

并且，由、可以得到微簇的中心ci=、微簇的半径ri=-（）2，ri？燮？着；

sni表示PCMCi内数据对象的真实序号的集合；

coni表示PCMCi内数据对象的ML和CL约束关系，coni={MLi∪CLi}，MLi={ML（s=0/1，i，p），…}，CLi={CL（s=0/1，i，q），…}。

定义 6 带约束的离群微簇（outlier constraint core micro cluster）简称约束离群微簇（OCMC），在某个时间t，用OCMCi（wi，，，sni，coni，t0）来表示。

其中，wi、，，sni，coni的定义和定义5相同，只是ξμ？燮wi<βμ，ξ为权重比例下限，t0表示该离群微簇的创建时间。这是由于当经过一段时间的权重衰减，若wi<ξμ，或超过其生存周期T，带约束的离群微簇仍然没有跳变到潜在核心微簇时，我们将删除该离群微簇以节省内存。

定义 7 约束微簇的直接密度可达（Directly Core Reachable）Cp和Cq为约束潜在核心微簇，如果满足Cq的权重wq？叟μ（即Cq为约束核心对象），dist（cp，cq）？燮max（rp+rq，2？着）且Cp和Cq之间不存在CL约束，则称Cp是从Cq直接密度可达的。

定义 8 约束微簇的密度可达（Core Reachable）Cp和Cq为约束潜在核心微簇，如果存在有潜在核心微簇链，并满足cp1=cp，cpn=cq，cpi是从cpi+1直接密度可达的，则称Cp是从Cq密度可达的。

定义 9 约束微簇的密度连通（Density connected）Cp和Cq为约束潜在核心微簇，如果存在另一个约束潜在核心微簇Cr，使得Cp和Cq都与Cr密度可达，则称Cp和Cq密度连通。

2 C-DBDStream算法

2.1 在线部分

在线阶段首先需要完成的是初始化。这里使用经典的DBSCAN聚类算法，将数据流中最先到达的N个数据对象作为静态的数据集{X}来进行初始化。其过程Initialise（DS，？着，？茁，？滋）为：

（1）计算数据对象x的？着邻域内的数据对象的总权重w满足w≥βμ，并且这些数据对象之间不存在CL约束，将构造一个新的约束潜在核心微簇（PCMC），将该数据对象从数据集中删除；

（2）计算x的？着邻域内的数据对象的总权重w满足w？叟βμ，但这些数据对象之间存在CL约束关系，删除包含CL约束关系的数据对象中距离x较远的数据对象，并重新计算x的？着0邻域内的总权重w0。若w0？叟βμ，则将剩余的数据对象构造一个约束潜在核心微簇（PCMC）；若w0？燮βμ，将这些剩余的数据对象创建一个约束离群微簇（OCMC）；

（3）计算x的？着邻域内的数据对象的总权重w<βμ，且不存在CL约束关系，则将这些数据对象构造一个约束离群微簇（OCMC）；

（4）计算x的？着邻域内的数据对象的总权重w<βμ，但是存在CL约束关系，删除包含CL约束关系的数据对象中距离x较远的数据，并直接将剩余的数据对象构造一个约束离群微簇（OCMC）。

在经过初始化之后，根据数据集中的数据会形成最初的一批的约束潜在核心微簇（PCMC）和约束离群微簇（OCMC），待新数据不断到来到后，我们需要对其进行维护。我们专门在内存上划分出一个离群微簇缓冲区，在该缓冲区完成所有约束离群微簇的初始化和维护工作。而约束潜在核心微簇则直接在内存上进行保存和维护，这样有利于数据的快速处理。

初始化工作完成后，在形成的微簇中需要不断的更新与合并。微簇的维护包括新数据对象到来时的合并与对现有微簇的权值和类型进行更新。

当一个新的数据对象x到达时，我们首先检查是否包含约束关系CL或ML。当它不包含任何约束关系时，我们执行Merge（x，？着，？茁，？滋，？姿，S）的过程：

（1）先尝试把x并入最近的约束潜在核心微蔟PCMCi中。如果并入x之后，PCMCi的新的半径ri？燮？着，则并入成功，更新PCMCi的特征向量；

（2）否则，说明x并入PCMCi失败，尝试把x并入与之距离最近的约束离群微蔟OCMCj中。如果并入x之后，OCMCj的新的半径rj？燮？着，则并入成功，重新计算OCMCj的特征向量。然后判断该约束离群微簇的类型是否会发生变化。计算并入x之后OCMCj的新权重wj，如果wj<βμ，整个操作结束；如果wj？叟βμ，将OCMCj删除，同时根据OCMCj新建一个约束潜在核心微蔟PCMCj；

（3）如果x不满足所有条件，则创建一个只有x一个数据对象构成的约束离群微蔟OCMCi，并将OCMCi置入离群微蔟缓冲区。

但是在实际中，我们不知道它是否带有约束关系，当新的数据对象x到达时，需要进行实时检测，再来进行合并操作。当数据对象包含约束关系时，Combine（x，？着，？茁，？滋，？姿，S）的过程如下：

（1）如果x带有约束关系，尝试把x并入与之没有CL关系且距离x最近的约束潜在核心微蔟PCMCi中。计算并入x之后，PCMCi的新的半径。若ri？燮？着，则并入成功，重新计算PCMCi的特征向量，并更新所有与x有约束关系的微蔟的特征向量中的约束信息；

（2）若ri>？着，则x并入失败。把x并入与之没有CL关系且距离x最近的约束离群微蔟OCMCj中。如果并入x之后，OCMCj的新的半径rj？燮？着，则并入成功，重新计算OCMCj的特征向量，并更新所有与x有约束关系的微蔟的特征向量中的约束信息。继续判断该约束离群类型是否发生变化，计算并入x之后OCMCj的新权重wj，如果wj<βμ，未发生变化；如果wj≥βμ，此时，该约束离群微簇已变为约束潜在核心微簇类型，将OCMCj从离群微蔟缓冲区删除，同时新建一个约束潜在核心微蔟PCMCj，并更新所有与OCMCj有约束关系的微蔟的特征向量中的约束信息。

（3）若x不能合并到现有的微蔟当中，则创建只有x一个数据对象的约束离群微蔟OCMCi，并将OCMCi置入离群微蔟缓冲区，最后更新所有与OCMCi有约束关系的微蔟的特征向量中的约束信息。

在衰减窗口模型中，其数据对象的权重都会随着时间推移而减小。因这一特性，约束潜在核心微簇和约束离群微簇之间会发生类型变化。

当微簇中数据对象其权重w跳变到了？茁？滋时，一个约束离群微簇就会变为约束潜在核心微簇。最快的跳变方式是经过时间间隔Tmin，数据流中一个新的数据对象到达并且合并到了该约束离群微簇中就需要对微簇的权重进行检查，可以保证不会错过微簇的类型变更。

wf（T）+f（0）=βμ

将w<βμ，f（T）=2-λT，f（0）=1代入，得到：

T

所以每经过Tmin=log2的时间，就需要检查微蔟的类型是否变更。

整合后，微簇更新操Update（？姿，？孜，β，μ，S）的过程如下：

（1）從内存读取一个约束潜在核心微蔟PCMCi，将其权重更新为f（Tmin）wi，即（1-）wi，比较（1-）wi与βμ的大小。如果（1-）wi<βμ，则根据PCMCi创建一个新的约束离群微蔟OCMCi，将OCMCi放入离群缓冲区，将PCMCi从内存中移除；否则，微蔟类型不变。

（2）从离群缓冲区中读取一个约束离群微蔟OCMCi，比较t-t0（当前时间减去创建时间）与T（约束离群微蔟的生存周期）的大小。若t-t0？叟T，将OCMCi从离群缓冲区中移除，否则将其权重更新为f（Tmin）wi，即（1-）wi，比较（1-）wi与ξμ的大小。若（1-）wi<ξμ，将OCMCi从离群缓冲区中移除；否则，微蔟类型不变。

（3）重复（1）-（2），直到所有的微蔟都经过处理。

2.2 离线部分

经过在线部分处理后，可以大致定位数据流中的部分数据的密集区域。当聚类请求到达时，首先根据约束微簇的可并性，对位置相邻并存在ML的微簇进行合并，减少微簇的数量。然后再依次扫描所有的约束潜在核心微簇，根据直接密度可达、密度可达等性质，找到所有密度连通的约束潜在核心微簇。本文使用DBSCAN改进算法来进行微簇聚类。意思就是，将所有密度连通且满足簇级约束关系的潜在核心微簇聚类成为一个最终簇。每个密度连通区域都是一个最终簇，密度连通区域的数量就是聚类数。聚类结果的重要性以微簇的权重来衡量，约束潜在核心微簇其权重越大意味着其内包含的数据对象个数越多。

综上所述，完整的C-DBDStream算法在线阶段：初始化（Initialise（DS，？着，β，μ））、合并（Combine（x，？着，β，μ，λ，S））、维护（Update（λ，ξ，β，μ，S））三个操作；离线阶段只需要完成聚类（Clustering（MC，μ，？着））操作。

算法2.1 C-DBDStream（DS，？着，β，μ，λ，ξ）

Input： DS，？着，β，μ，λ，ξ

Output： clusters

1：Initialise（DS，？着，β， μ）

2：Repeat

3：Get a data x from data stream DS and Combine（x，？着，β，μ，λ，S）；

4：If（t mod Tmin）=0

5：Update（λ，ξ，β，μ，S）；

6：End if

7：Until no data of DS left；

8：If（t mod Tmin）=0

9：Update（λ，ξ，β，μ，S）；

10：End if

11：If user's clustering request arrive

12：Clustering（MC，μ，？着）；

13： End if

3 实验结果分析

3.1 硬件环境

本次实验所使用的计算机CPU为Intel（R） i5-2450M双核，主频2.50GHZ，内存4GB，硬盘为固态硬盘Samsung SSD 750 EVO。通过开源的数据流挖掘框架MOA进行扩展，使用MyEclipse 10开发工具来进行实验，实现了C-DBDStream算法。

3.2 实验分析

本次实验采用数据流为KDDCup99[21]的训练集，对比算法我们使用Clustream算法。

（1）首先我们研究不含约束的情况下C-DBDStream的性能，通过设置10%的高噪声比例来测试算法的离群点处理能力。分别将参数值设置为：邻域范围？着=16，μ=10，潜在核心微簇阀值β=0.5，离群微簇阀值ξ=0.2，衰减因子λ=0.2。为消除数据流本身对聚类算法的影响，将实验结果取几何平均值。对比Clustream算法实验结果如下图2所示。

聚类纯度是指，每个聚类结果中最多的分类数据所占全部数据的比例。随着数据流流速PPS的增加，算法聚类效果开始下降。比较两种算法，C-DBDStream算法聚类纯度降幅比Clustream算法更小，噪声对算法的影响也较小。通过引入离群点处理机制减弱了噪声对于聚类质量的不良影响。

（2）为了研究数据流含约束的情况下C-DBDStream的性能，我们随机选取2%的数据，并加入ML和CL以1：1的比例约束条件，其余参数保持不变。实验结果如图3所示。

从图3可以看出，CluStream的聚类纯度远低于C-DBDStream的聚类纯度。该算法引入约束条件来指导微簇的形成和维护，根据约束条件形成高质量的微簇，并且排除了部分噪音数据的干扰，为后续更好的聚类提供条件。

（3）分析约束条件数量对于C-DBDStream算法聚类质量的影响程度，在其余参数不变的情况下，分别随机选取2%、4%、8%的数据以ML和CL为1：1的比例加入约束条件来进行实验。结果如下图4所示。

从图4可以看出，从聚类纯度来讲，约束条件越多，其纯度越高。但是，约束条件比例为4%和8%的聚类效果相差不多。意思是，当约束条件数量超过一定比例后，如果继续增加约束条件，其实并不能显著提高聚类效果。在C-DBDStream算法的在线部分，会有多次的检查该数据对象是否含有约束条件，过多的约束条件反而会影响聚类算法的执行效率。所以在本例中，4%-6%的约束条件数量比例是一个合适的选择。可以平衡聚类的效果与其效率。

4 结束语

本文研究将约束条件和数据流聚类算法结合起来。先分析了现有数据流聚类算法，再通过对已有的基于约束的聚类算法进行研究，分析算法的本质和具体执行过程。然后，提出了一种基于密度和约束的数据流聚类算法C-DBDStream，它结合了数据流聚类算法和带有约束的数据聚类算法。C-DBDStream使用数据流聚类两阶段框架，将聚类过程分为在线初始化與更新和离线聚类两个部分，并将实例级的约束扩展到微簇级来使用。实验结果表明，与现有算法相比，本文提出的C-DBDStream算法在聚类纯度与增加约束条件数量的使用是有效的，在参数设置得当的情况下，能够明显的增强聚类质量。未来拟扩展该技术，可以分析如何将约束条件运用到其他数据流聚类算法之中以及间接约束条件的获取上进行深入研究。

参考文献：

[1]Philipp Kranen，Ira Assent， Corinna Baldauf， Thomas Seidl. The ClusTree：indexing micro-clusters for anytime stream mining[J]. Knowledge and Information Systems.2011，29（2）：249-272.

[2]Marcel R. Ackermann，Marcus，MSrtens，Christoph，Raupach，Karnil Swierkot，ChristianeLammersen，Christian Sohler.StreamKM++： A clustering algorithm fordata streams[J].ACM Journal of Experimental Algorithmics. 2012，17（1）.

[3]韩东红，宋明，张宏亮，等.基于密度的不确定数据流聚类算法[J].清华大学学报（自然科学版），2017，57（08）：884-891.

[4]周华平，陈顺生.基于动态可调衰减滑动窗口的变速数据流聚类算法[J].计算机应用与软件，2015，32（11）：255-260+300.

[5]Hartigan， J. A.； Wong， M. A.（1979）. Algorithm AS 136： A K-Means ClusteringAlgorithm[M].Journal of the Royal Statistical Society， Series C 28（1）： 100-108.

[6]T. Zhang， R. Ramakrishnan， M. Livny. BIRCH： A New Data Clustering Algorithm and ItsApplications[C]. In： Jagadish HV， Mumick IS， eds. Proc. of the ACM SIGMOD Int'l Conf. onManagement of Data. Montreal： ACM Press，1996：103-114.

[7]C.C.Aggarwal， J.Han， J.Wang， and P.S.Yu. A framework for clusteringevolvingdatastreams[J].InProc. ofVLDB，pages81-92，2003.

[8]Ester， Martin；Kriegel， Hans-Peter； Sander， Jorg； Xu， Xiaowei （1996）. Simoudis， Evangelos； Han， Jiawei； Fayyad， Usama M.， eds.A density-based algorithm for discovering clusters in large spatial databases with noise[C]. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining （KDD-96）.AAAI Press. pp.226-231.

[9]萬新贵，李玲娟.基于质心距离和密度网格的数据流聚类算法[J].南京邮电大学学报（自然科学版），2017，37（01）：97-103.

[10]徐文华，覃征，常扬. 基于半监督学习的数据流集成分类算法[J].模式识别与人工智能，2012（02）：292-299.

[11]冯兴杰，黄亚楼. 带约束条件的聚类算法研究[J].计算机工程与应用，2005（7）：12-14，169.

[12]F. CAO， M. ESTER， W. QIAN， A. ZHOU. Density-based clustering overan evolving data stream with noise[C]. In Proc. of SIAM.2006：326-337.

[13]Carlos Ruiz， Myra Spiliopoulou， Ernestina Menasalvas. C-DBSCAN：Density-Based Clustering with Constraints[A]. In： 11th International Conferenceon Rough Sets， Fuzzy Sets， Data Mining and Granular Computing[C]. 2007：216-223.

[14]Zhang， T.； Ramakrishnan， R.； Livny， M. （1996）. "BIRCH： an efficient data clustering method for very large databases". Proceedings of the 1996 ACM SIGMOD international conference on Management of data - SIGMOD '96. pp.103-114.

[15]Wang Huan， Yu Yanwei， Wang Qin， Wan Yadong. A density-based clustering structure mining algorithm for data streams[C].1st International Workshop on Big Data， Streams and Heterogeneous Source Mining： Algorithms， Systems， Programming Models and Applications， BigMine-12-Held in Conjunction with SIGKDD Conference， pp.69-76.

[16]Deza， Elena； Deza， Michel Marie（2009）.Encyclopedia of Distances.[J] Springer. p.94.

[17]Campello， R. J. G. B.； Moulavi， D.； Sander， J. （2013）.Density-Based Clustering Based on Hierarchical Density Estimates.[C] Proceedings of the 17th Pacific-Asia Conference on Knowledge Discovery in Databases， PAKDD 2013. Lecture Notes in Computer Science7819. p.160.

[18]Sander， Jorg（1998）.Generalized Density-Based Clustering for Spatial Data Mining.[M] München： Herbert Utz Verlag.

[19]http：//moa.cms.waikato.ac.nz/[EB/OL].

[20]Bifet A， Holmes G， Kirkby R， et al. MOA： Massive Online Analysis. Journal of Machine Learning Research（JMLR）[J].2010：

44-50.

[21]http：//kdd.ics.uci.edu/databases/kddcup99/kddcup99.html[EB/OL].