一種基于密度和約束的數(shù)據(jù)流聚類算法

付家祺 陳堅 淳浩 年青

摘 要： 文章在傳統(tǒng)聚類算法的基礎(chǔ)上，提出了一種基于密度和約束的數(shù)據(jù)流聚類算法——C-DBDStream（Constraint and Density Based Clustering of Data Stream）。該算法使用數(shù)據(jù)流聚類在線和離線兩階段框架。在線聚類階段使用衰減窗口模型，對數(shù)據(jù)流中的數(shù)據(jù)對象進(jìn)行初步的聚類，應(yīng)用約束條件生成微簇，并將實例級的約束擴(kuò)展到了微簇級，并將結(jié)果以快照的形式保存下來為下一階段做準(zhǔn)備；離線聚類階段則利用微簇級約束規(guī)則聚類，采用DBSCAN算法中的密度可達(dá)尋找密度連通區(qū)域以產(chǎn)生最終結(jié)果。經(jīng)實驗證明，與CluStream算法的對比中，C-DBDStream算法提高了聚類效果。

關(guān)鍵詞：數(shù)據(jù)流；聚類；密度；約束

中圖分類號：TP311.13 文獻(xiàn)標(biāo)志碼：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

隨著時代的進(jìn)步和發(fā)展，大數(shù)據(jù)的發(fā)展尤為迅猛，靜態(tài)數(shù)據(jù)已經(jīng)無法滿足日益增長的需求，數(shù)據(jù)流在各個領(lǐng)域的發(fā)展和應(yīng)用越來越廣泛。聚類分析是針對數(shù)據(jù)流挖掘的一種重要手段，數(shù)據(jù)流聚類算法有以下特點：單邊掃描、數(shù)據(jù)抽象、近似結(jié)果、快速處理。已有的數(shù)據(jù)流聚類算法大都是無監(jiān)督的學(xué)習(xí)方法，如果利用一些約束條件，可以改進(jìn)現(xiàn)有的數(shù)據(jù)流算法，構(gòu)造性能優(yōu)異的半監(jiān)督數(shù)據(jù)流聚類算法。

本文在詳細(xì)分析數(shù)據(jù)流的特征和約束條件的性質(zhì)的基礎(chǔ)上，對基于約束條件的聚類進(jìn)行了研究，并提出了一種基于密度和約束條件的數(shù)據(jù)流聚類算法——C-DBDStream。該算法將聚類過程分為兩個階段：在線部分應(yīng)用約束條件和衰減窗口模型，將數(shù)據(jù)流中的數(shù)據(jù)對象擴(kuò)展到微簇級，并將結(jié)果以快照的形式保存下來；離線部分是在前面的基礎(chǔ)上，利用擴(kuò)展的微簇級約束來聚類，利用DBSCAN算法中的密度可達(dá)尋找密度連通區(qū)域，聚類出最終結(jié)果。最后通過在KDDCup99等數(shù)據(jù)流上的實驗測試，驗證了算法的正確性和有效性。

本文第1節(jié)介紹算法中的基本概念，第2節(jié)給出C-DBDStream算法，詳細(xì)解析算法的思想和執(zhí)行過程，第3節(jié)提供實驗結(jié)果及分析，第4節(jié)對全文做總結(jié)并指出后續(xù)的研究。

1 算法使用的基本概念

定義1實例級約束D=（X1，X2，…，Xn）為一個數(shù)據(jù)集，（C1，C2，…，Ck）是數(shù)據(jù)集D的聚類結(jié)果，則有ML和CL約束：

？坌ML（Xi，Xj），1

？坌CL（Xi，Xj），1

上圖的約束關(guān)系可以表示為：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的聚類結(jié)果，那么有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實例級約束擴(kuò)展到微簇級約束xi、xj分別為微簇MCi、MCj上的數(shù)據(jù)對象，那么有：

er）帶約束的核心微簇是由核心對象的？著鄰域內(nèi)包含核心對象間的約束關(guān)系及所有數(shù)據(jù)對象構(gòu)成的一個集合。在某個時刻t用CCMCi（wi，ci，ri，sni，coni）來表示。

xi1，xi2，…，xin為約束核心微簇CCMCi中的數(shù)據(jù)對象，這些數(shù)據(jù)對象都是核心對象，并分別在ti1，ti2，…，tin的時間點按序到達(dá)。

wi表示CCMCi的權(quán)重， ；

ci表示CCMCi的中心， ；

ri表示CCMCi的半徑， ，ri？燮？著，

dist（ci，xij）表示ci與xij之間的歐氏距離[14]；

sni表示CCMCi內(nèi)數(shù)據(jù)對象的真實序號的集合；

coni表示CCMCi內(nèi)數(shù)據(jù)對象的ML和CL約束關(guān)系，coni={MLi∪CLi}，MLi={ML（s=0/1，i，p），…}，CLi={CL（s=0/1，i，q），…}，s表示約束條件類型，i表示該約束核心微簇的序號。當(dāng)s=0時，p、q等表示數(shù)據(jù)對象的真實編號，表示該核心微簇與數(shù)據(jù)對象之間的約束關(guān)系；當(dāng)s=1時，p、q等表示其他的微簇的序號，表示該核心微簇與其他微簇之間的關(guān)系。

定義5帶約束的潛在核心微簇（potential constraint core micro cluster）簡稱約束潛在核心微簇（PCMC），用PCMCi（wi，，，sni，coni）來表示。

xi1，xi2，…，xin是PCMCi中的數(shù)據(jù)對象，在ti1，ti2，…，tin的時間點按序到達(dá)。

wi表示PCMCi的權(quán)重，wi=？撞f（t-tij），wi？叟βμ，β為潛在核心閥值，0<β？燮1；

為微簇中數(shù)據(jù)對象的加權(quán)線性和，=？撞f（t-tij）xij；

為微簇中數(shù)據(jù)對象的加權(quán)平方和，=？撞f（t-tij）x；

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

sni表示PCMCi內(nèi)數(shù)據(jù)對象的真實序號的集合；

coni表示PCMCi內(nèi)數(shù)據(jù)對象的ML和CL約束關(guān)系，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<βμ，ξ為權(quán)重比例下限，t0表示該離群微簇的創(chuàng)建時間。這是由于當(dāng)經(jīng)過一段時間的權(quán)重衰減，若wi<ξμ，或超過其生存周期T，帶約束的離群微簇仍然沒有跳變到潛在核心微簇時，我們將刪除該離群微簇以節(jié)省內(nèi)存。

定義 7 約束微簇的直接密度可達(dá)（Directly Core Reachable）Cp和Cq為約束潛在核心微簇，如果滿足Cq的權(quán)重wq？叟μ（即Cq為約束核心對象），dist（cp，cq）？燮max（rp+rq，2？著）且Cp和Cq之間不存在CL約束，則稱Cp是從Cq直接密度可達(dá)的。

定義 8 約束微簇的密度可達(dá)（Core Reachable）Cp和Cq為約束潛在核心微簇，如果存在有潛在核心微簇鏈，并滿足cp1=cp，cpn=cq，cpi是從cpi+1直接密度可達(dá)的，則稱Cp是從Cq密度可達(dá)的。

定義 9 約束微簇的密度連通（Density connected）Cp和Cq為約束潛在核心微簇，如果存在另一個約束潛在核心微簇Cr，使得Cp和Cq都與Cr密度可達(dá)，則稱Cp和Cq密度連通。

2 C-DBDStream算法

2.1 在線部分

在線階段首先需要完成的是初始化。這里使用經(jīng)典的DBSCAN聚類算法，將數(shù)據(jù)流中最先到達(dá)的N個數(shù)據(jù)對象作為靜態(tài)的數(shù)據(jù)集{X}來進(jìn)行初始化。其過程Initialise（DS，？著，？茁，？滋）為：

（1）計算數(shù)據(jù)對象x的？著鄰域內(nèi)的數(shù)據(jù)對象的總權(quán)重w滿足w≥βμ，并且這些數(shù)據(jù)對象之間不存在CL約束，將構(gòu)造一個新的約束潛在核心微簇（PCMC），將該數(shù)據(jù)對象從數(shù)據(jù)集中刪除；

（2）計算x的？著鄰域內(nèi)的數(shù)據(jù)對象的總權(quán)重w滿足w？叟βμ，但這些數(shù)據(jù)對象之間存在CL約束關(guān)系，刪除包含CL約束關(guān)系的數(shù)據(jù)對象中距離x較遠(yuǎn)的數(shù)據(jù)對象，并重新計算x的？著0鄰域內(nèi)的總權(quán)重w0。若w0？叟βμ，則將剩余的數(shù)據(jù)對象構(gòu)造一個約束潛在核心微簇（PCMC）；若w0？燮βμ，將這些剩余的數(shù)據(jù)對象創(chuàng)建一個約束離群微簇（OCMC）；

（3）計算x的？著鄰域內(nèi)的數(shù)據(jù)對象的總權(quán)重w<βμ，且不存在CL約束關(guān)系，則將這些數(shù)據(jù)對象構(gòu)造一個約束離群微簇（OCMC）；

（4）計算x的？著鄰域內(nèi)的數(shù)據(jù)對象的總權(quán)重w<βμ，但是存在CL約束關(guān)系，刪除包含CL約束關(guān)系的數(shù)據(jù)對象中距離x較遠(yuǎn)的數(shù)據(jù)，并直接將剩余的數(shù)據(jù)對象構(gòu)造一個約束離群微簇（OCMC）。

在經(jīng)過初始化之后，根據(jù)數(shù)據(jù)集中的數(shù)據(jù)會形成最初的一批的約束潛在核心微簇（PCMC）和約束離群微簇（OCMC），待新數(shù)據(jù)不斷到來到后，我們需要對其進(jìn)行維護(hù)。我們專門在內(nèi)存上劃分出一個離群微簇緩沖區(qū)，在該緩沖區(qū)完成所有約束離群微簇的初始化和維護(hù)工作。而約束潛在核心微簇則直接在內(nèi)存上進(jìn)行保存和維護(hù)，這樣有利于數(shù)據(jù)的快速處理。

初始化工作完成后，在形成的微簇中需要不斷的更新與合并。微簇的維護(hù)包括新數(shù)據(jù)對象到來時的合并與對現(xiàn)有微簇的權(quán)值和類型進(jìn)行更新。

當(dāng)一個新的數(shù)據(jù)對象x到達(dá)時，我們首先檢查是否包含約束關(guān)系CL或ML。當(dāng)它不包含任何約束關(guān)系時，我們執(zhí)行Merge（x，？著，？茁，？滋，？姿，S）的過程：

（1）先嘗試把x并入最近的約束潛在核心微蔟PCMCi中。如果并入x之后，PCMCi的新的半徑ri？燮？著，則并入成功，更新PCMCi的特征向量；

（2）否則，說明x并入PCMCi失敗，嘗試把x并入與之距離最近的約束離群微蔟OCMCj中。如果并入x之后，OCMCj的新的半徑rj？燮？著，則并入成功，重新計算OCMCj的特征向量。然后判斷該約束離群微簇的類型是否會發(fā)生變化。計算并入x之后OCMCj的新權(quán)重wj，如果wj<βμ，整個操作結(jié)束；如果wj？叟βμ，將OCMCj刪除，同時根據(jù)OCMCj新建一個約束潛在核心微蔟PCMCj；

（3）如果x不滿足所有條件，則創(chuàng)建一個只有x一個數(shù)據(jù)對象構(gòu)成的約束離群微蔟OCMCi，并將OCMCi置入離群微蔟緩沖區(qū)。

但是在實際中，我們不知道它是否帶有約束關(guān)系，當(dāng)新的數(shù)據(jù)對象x到達(dá)時，需要進(jìn)行實時檢測，再來進(jìn)行合并操作。當(dāng)數(shù)據(jù)對象包含約束關(guān)系時，Combine（x，？著，？茁，？滋，？姿，S）的過程如下：

（1）如果x帶有約束關(guān)系，嘗試把x并入與之沒有CL關(guān)系且距離x最近的約束潛在核心微蔟PCMCi中。計算并入x之后，PCMCi的新的半徑。若ri？燮？著，則并入成功，重新計算PCMCi的特征向量，并更新所有與x有約束關(guān)系的微蔟的特征向量中的約束信息；

（2）若ri>？著，則x并入失敗。把x并入與之沒有CL關(guān)系且距離x最近的約束離群微蔟OCMCj中。如果并入x之后，OCMCj的新的半徑rj？燮？著，則并入成功，重新計算OCMCj的特征向量，并更新所有與x有約束關(guān)系的微蔟的特征向量中的約束信息。繼續(xù)判斷該約束離群類型是否發(fā)生變化，計算并入x之后OCMCj的新權(quán)重wj，如果wj<βμ，未發(fā)生變化；如果wj≥βμ，此時，該約束離群微簇已變?yōu)榧s束潛在核心微簇類型，將OCMCj從離群微蔟緩沖區(qū)刪除，同時新建一個約束潛在核心微蔟PCMCj，并更新所有與OCMCj有約束關(guān)系的微蔟的特征向量中的約束信息。

（3）若x不能合并到現(xiàn)有的微蔟當(dāng)中，則創(chuàng)建只有x一個數(shù)據(jù)對象的約束離群微蔟OCMCi，并將OCMCi置入離群微蔟緩沖區(qū)，最后更新所有與OCMCi有約束關(guān)系的微蔟的特征向量中的約束信息。

在衰減窗口模型中，其數(shù)據(jù)對象的權(quán)重都會隨著時間推移而減小。因這一特性，約束潛在核心微簇和約束離群微簇之間會發(fā)生類型變化。

當(dāng)微簇中數(shù)據(jù)對象其權(quán)重w跳變到了？茁？滋時，一個約束離群微簇就會變?yōu)榧s束潛在核心微簇。最快的跳變方式是經(jīng)過時間間隔Tmin，數(shù)據(jù)流中一個新的數(shù)據(jù)對象到達(dá)并且合并到了該約束離群微簇中就需要對微簇的權(quán)重進(jìn)行檢查，可以保證不會錯過微簇的類型變更。

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

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

T

所以每經(jīng)過Tmin=log2的時間，就需要檢查微蔟的類型是否變更。

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

（1）從內(nèi)存讀取一個約束潛在核心微蔟PCMCi，將其權(quán)重更新為f（Tmin）wi，即（1-）wi，比較（1-）wi與βμ的大小。如果（1-）wi<βμ，則根據(jù)PCMCi創(chuàng)建一個新的約束離群微蔟OCMCi，將OCMCi放入離群緩沖區(qū)，將PCMCi從內(nèi)存中移除；否則，微蔟類型不變。

（2）從離群緩沖區(qū)中讀取一個約束離群微蔟OCMCi，比較t-t0（當(dāng)前時間減去創(chuàng)建時間）與T（約束離群微蔟的生存周期）的大小。若t-t0？叟T，將OCMCi從離群緩沖區(qū)中移除，否則將其權(quán)重更新為f（Tmin）wi，即（1-）wi，比較（1-）wi與ξμ的大小。若（1-）wi<ξμ，將OCMCi從離群緩沖區(qū)中移除；否則，微蔟類型不變。

（3）重復(fù)（1）-（2），直到所有的微蔟都經(jīng)過處理。

2.2 離線部分

經(jīng)過在線部分處理后，可以大致定位數(shù)據(jù)流中的部分?jǐn)?shù)據(jù)的密集區(qū)域。當(dāng)聚類請求到達(dá)時，首先根據(jù)約束微簇的可并性，對位置相鄰并存在ML的微簇進(jìn)行合并，減少微簇的數(shù)量。然后再依次掃描所有的約束潛在核心微簇，根據(jù)直接密度可達(dá)、密度可達(dá)等性質(zhì)，找到所有密度連通的約束潛在核心微簇。本文使用DBSCAN改進(jìn)算法來進(jìn)行微簇聚類。意思就是，將所有密度連通且滿足簇級約束關(guān)系的潛在核心微簇聚類成為一個最終簇。每個密度連通區(qū)域都是一個最終簇，密度連通區(qū)域的數(shù)量就是聚類數(shù)。聚類結(jié)果的重要性以微簇的權(quán)重來衡量，約束潛在核心微簇其權(quán)重越大意味著其內(nèi)包含的數(shù)據(jù)對象個數(shù)越多。

綜上所述，完整的C-DBDStream算法在線階段：初始化（Initialise（DS，？著，β，μ））、合并（Combine（x，？著，β，μ，λ，S））、維護(hù)（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 實驗結(jié)果分析

3.1 硬件環(huán)境

本次實驗所使用的計算機(jī)CPU為Intel（R） i5-2450M雙核，主頻2.50GHZ，內(nèi)存4GB，硬盤為固態(tài)硬盤Samsung SSD 750 EVO。通過開源的數(shù)據(jù)流挖掘框架MOA進(jìn)行擴(kuò)展，使用MyEclipse 10開發(fā)工具來進(jìn)行實驗，實現(xiàn)了C-DBDStream算法。

3.2 實驗分析

本次實驗采用數(shù)據(jù)流為KDDCup99[21]的訓(xùn)練集，對比算法我們使用Clustream算法。

（1）首先我們研究不含約束的情況下C-DBDStream的性能，通過設(shè)置10%的高噪聲比例來測試算法的離群點處理能力。分別將參數(shù)值設(shè)置為：鄰域范圍？著=16，μ=10，潛在核心微簇閥值β=0.5，離群微簇閥值ξ=0.2，衰減因子λ=0.2。為消除數(shù)據(jù)流本身對聚類算法的影響，將實驗結(jié)果取幾何平均值。對比Clustream算法實驗結(jié)果如下圖2所示。

聚類純度是指，每個聚類結(jié)果中最多的分類數(shù)據(jù)所占全部數(shù)據(jù)的比例。隨著數(shù)據(jù)流流速PPS的增加，算法聚類效果開始下降。比較兩種算法，C-DBDStream算法聚類純度降幅比Clustream算法更小，噪聲對算法的影響也較小。通過引入離群點處理機(jī)制減弱了噪聲對于聚類質(zhì)量的不良影響。

（2）為了研究數(shù)據(jù)流含約束的情況下C-DBDStream的性能，我們隨機(jī)選取2%的數(shù)據(jù)，并加入ML和CL以1：1的比例約束條件，其余參數(shù)保持不變。實驗結(jié)果如圖3所示。

從圖3可以看出，CluStream的聚類純度遠(yuǎn)低于C-DBDStream的聚類純度。該算法引入約束條件來指導(dǎo)微簇的形成和維護(hù)，根據(jù)約束條件形成高質(zhì)量的微簇，并且排除了部分噪音數(shù)據(jù)的干擾，為后續(xù)更好的聚類提供條件。

（3）分析約束條件數(shù)量對于C-DBDStream算法聚類質(zhì)量的影響程度，在其余參數(shù)不變的情況下，分別隨機(jī)選取2%、4%、8%的數(shù)據(jù)以ML和CL為1：1的比例加入約束條件來進(jìn)行實驗。結(jié)果如下圖4所示。

從圖4可以看出，從聚類純度來講，約束條件越多，其純度越高。但是，約束條件比例為4%和8%的聚類效果相差不多。意思是，當(dāng)約束條件數(shù)量超過一定比例后，如果繼續(xù)增加約束條件，其實并不能顯著提高聚類效果。在C-DBDStream算法的在線部分，會有多次的檢查該數(shù)據(jù)對象是否含有約束條件，過多的約束條件反而會影響聚類算法的執(zhí)行效率。所以在本例中，4%-6%的約束條件數(shù)量比例是一個合適的選擇?？梢云胶饩垲惖男Чc其效率。

4 結(jié)束語

本文研究將約束條件和數(shù)據(jù)流聚類算法結(jié)合起來。先分析了現(xiàn)有數(shù)據(jù)流聚類算法，再通過對已有的基于約束的聚類算法進(jìn)行研究，分析算法的本質(zhì)和具體執(zhí)行過程。然后，提出了一種基于密度和約束的數(shù)據(jù)流聚類算法C-DBDStream，它結(jié)合了數(shù)據(jù)流聚類算法和帶有約束的數(shù)據(jù)聚類算法。C-DBDStream使用數(shù)據(jù)流聚類兩階段框架，將聚類過程分為在線初始化與更新和離線聚類兩個部分，并將實例級的約束擴(kuò)展到微簇級來使用。實驗結(jié)果表明，與現(xiàn)有算法相比，本文提出的C-DBDStream算法在聚類純度與增加約束條件數(shù)量的使用是有效的，在參數(shù)設(shè)置得當(dāng)?shù)那闆r下，能夠明顯的增強(qiáng)聚類質(zhì)量。未來擬擴(kuò)展該技術(shù)，可以分析如何將約束條件運用到其他數(shù)據(jù)流聚類算法之中以及間接約束條件的獲取上進(jìn)行深入研究。

參考文獻(xiàn)：

[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]韓東紅，宋明，張宏亮，等.基于密度的不確定數(shù)據(jù)流聚類算法[J].清華大學(xué)學(xué)報（自然科學(xué)版），2017，57（08）：884-891.

[4]周華平，陳順生.基于動態(tài)可調(diào)衰減滑動窗口的變速數(shù)據(jù)流聚類算法[J].計算機(jī)應(yīng)用與軟件，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]萬新貴，李玲娟.基于質(zhì)心距離和密度網(wǎng)格的數(shù)據(jù)流聚類算法[J].南京郵電大學(xué)學(xué)報（自然科學(xué)版），2017，37（01）：97-103.

[10]徐文華，覃征，常揚. 基于半監(jiān)督學(xué)習(xí)的數(shù)據(jù)流集成分類算法[J].模式識別與人工智能，2012（02）：292-299.

[11]馮興杰，黃亞樓. 帶約束條件的聚類算法研究[J].計算機(jī)工程與應(yīng)用，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].