一種基于密度和約束的數據流聚類算法

付家祺 陳堅 淳浩 年青

摘 要： 文章在傳統聚類算法的基礎上，提出了一種基于密度和約束的數據流聚類算法——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].