DEN-Stream：一種分布式數據流聚類方法

李長路　王勁林　郭志川　韓　銳

1(中國科學院大學　北京 100190)2(中國科學院聲學研究所國家網絡新媒體工程技術研究中心　北京 100190)

?

DEN-Stream：一種分布式數據流聚類方法

李長路1,2王勁林2郭志川2韓銳2

1(中國科學院大學北京 100190)2(中國科學院聲學研究所國家網絡新媒體工程技術研究中心北京 100190)

摘要現有的數據流聚類方法很難兼顧數據稀疏和子空間聚類等高維數據難題，而分布式數據流對數據流聚類提出包括在線計算效率、通信開銷以及多路數據的融合等更多挑戰。提出分布式數據流聚類方法，采用全局統一的網格劃分和衰退時間以支持多路數據流融合，并周期性檢查和刪除過期網格來控制概要規模。通過對多路高維數據流的一遍掃描，發現高維數據流子空間任意形狀的聚類，并反映數據分布隨時間的演化。在線組件效率高開銷低，概要信息簡潔，通信代價低。實驗表明，該方法能夠對分布式數據流正確聚類并演進，在線組件效率高，概要規模小。

關鍵詞分布式數據流子空間聚類網格聚類高維數據

0引言

網絡技術、互聯網應用生態以及包括智能終端、傳感器等各種數據采集設備的發展，使得分布式數據流作為一種廣泛存在的數據組織形式[1,2]。數據流聚類挖掘技術已經成為一個重要研究領域，并廣泛應用于電子商務、物理世界監測。數據流給傳統聚類技術帶來的主要挑戰包括快速的數據吞吐、潛在無限、數據高維、只能執行一遍時序掃描、高效的存儲需求以及反映數據分布的時間演進等[1]。實際的數據流大都來自分布式環境下的多個數據采集終端，除前述挑戰外，還必須面臨數據采集終端的資源約束、多路數據流正確融合[2]以及持續的數據通信帶來的帶寬占用。

著名的數據流聚類算法CluStream[3]首先提出的“在線—離線”二元組件結構。其中在線部分負責掃描數據流，形成關于數據分布的概要信息；離線部分采用基于距離的傳統聚類算法k-means，利用在線部分提供概要信息挖掘產生聚類。CluStream還提出了金字塔形時間衰減結構來優化歷史概要數據的儲存。然而CluStream無力處理噪聲、高維數據等數據流常見問題，同其他基于距離公式的方法一樣，不能發現任意形狀聚簇。后續的研究普遍繼承了和發展了二元組件結構和高效存儲思想，并針對性地發展了克服某些前述數據流難題，但很難同時解決現有挑戰。

基于密度[4,5]和網格[6-9]的聚類方法普遍具有計算速度快，能夠以便掃描數據發現任意形狀聚類，因而成為數據流聚類的一類基本方法。而子空間聚類[10]也是數據流聚類的一個重要課題。D-Stream[6]基于密度網格方法，理論上能夠發現任意形狀任意數量的聚類，同時將新數據到達時概要信息更新復雜度降低。Li等人于2009年提出對D-Stream的改進版本[11]，引入“網格引力”概念，提高了聚類質量，但其概要信息更復雜，計算復雜度更高。這兩種方法都只能發現摘要空間的聚類，不能對高維數據流進行子空間聚類；且在分布式多路數據流環境下，其關于網格密度上限、閾值的定理不再成立。文獻[7,12]針對高維空間數據作了改進，但仍不是子空間聚類，且犧牲了計算效率。DS_CABOSFV[8]將靜態高維數據聚類算法應用于數據流聚類，同樣無法發現任意形狀的子空間聚類。IGDCL[13]提出不規則網格劃分的方法降低網格尺寸和邊界帶來的負面影響，該方法概要信息量大，網格維護復雜度高，在線部分資源占用過大，不規則的網格劃分導致無法實現多路數據流的融合。

本文提出的數據流聚類方法DEN-Stream，采用主流的在線—離線二元結構設計，其離線核心算法采用密度意識子空間聚類算法DENCOS[14]。在線部分維護高維數據流全空間的網格概要信息，采用規則網格劃分，特征向量簡潔，更新效率高。離線部分采用基于密度網格的算法DENCOS[14]，發現任意形狀的子空間聚類，并能有效克服高維數據的稀疏性，采用衰退因子反映全局統一的時間進化。由于在滿空間存在大量空白網格，只在線維護非空白的有效網格以提高存儲和通信資源使用效率。在分布式多路數據流上，網格密度上限定理不再成立，通過統計所有網格密度之和來計算后續挖掘過程中的參數，同時避免刪除稀疏網格帶來聚類誤差。

1分布式數據流聚類方法研究

1.1網格劃分

S=A1×A2×…×Ad表示d數據流的滿空間，A1,A2,…,Ad為S的各個維度屬性。其中Ai取值范圍為[Mini,Maxi)，維向量L=(l1,l2,…,ld)存儲響應維度的取值區間長度：

li=Maxi-Mini

(1)

每個維度被均勻分為k個間隔，則分辨率為：

(2)

數據流的d維全空間被劃分為kd個矩形單元組成的網格。

1.2特征向量

d維空間網格結構中每一個網格由一個特征向量描述，其定義為(id,D,tg)。其中tg為該網格最后一個數據點到達時間，D為該網格的密度在最后一個數據點到達時更新的結果，空網格置零。若在時刻t一個新的數據點x到達，其對應網格密度更新為：

D(g,t)=1+D(g,tg)×λ(t-tg)

(3)

任何數據對網格密度的貢獻隨著時間延伸而減弱，后到達數據對網格密度具有更大的貢獻。λ(λ∈(0,1))為網格密度的時間衰退因子。

id為識別網格的編號，為了便于將數據點x=(x1,x2,…,xd)映射到對應的網格，定義id為：

(4)

所有網格的編號為1至kd的正整數。由于全局統一的網格劃分以及網格標識，使得分布在多個數據流中的數據在摘要中影響了相同標識的網格密度，多路數據流網格密度計算空間上保持全局一致。

1.3時間度量與多路融合

D-Stream[5]模型中的時間實際上是單獨數據流中數據抵達順序編號。在分布式多路數據流環境下，融合時拿到的是概要信息，是無法對來自不同子數據流的數據進行順序編號。即使在單獨數據流中，如果數據不是按均勻的時間間隔采集，這種衰退方法也無法準確反映聚類隨著時間的演化。簡單的相加可能導致不同子數據流中的兩組數據，在時間上先到達的數據，對網格密度的貢獻大于時間上后到達的數據。

本文采用實際時間作為聚類演化的依據，統一各路數據流的時間，從而使多路數據流融合成為可能。總共m路數據流，對于網格g，在當前時間刻度t的密度融合計算公式為：

(5)

根據式(5)，不同子數據流的網格密度根據其更新時間，計算出當前時間的衰減后密度，相加得到多路數據流總的網格密度。不同數據流的數據點在融合時都以相同的時間度量衰減，與同一子數據流內數據處理相同，分布在多個路數據流中的數據衰退情況與同一個數據流中的衰退一致。時間衰退的全局一致與空間密度計算的全局一致，確保本文方法具有很好的可擴展性，理論上其工作性能不受數據采集終端數量限制。

1.4概要信息的在線維護

gridlist為存儲子數據流概要信息的鏈表，其成員為非空網格的特征向量，按網格id順序排列。由于引入時間衰退因子來反映流中數據分布的演化，所有網格的密度都隨著時間變化。對于沒有新數據到來的網格g，其任意時間的密度為：

D(g,t)=D(g,tg)×λ(t-tg)

(6)

根據式(6)，只需要知道其特征向量，即可計算出當前時刻密度。因此，沒有必要不斷更新gridlist中所有網格的特征向量，只需根據式(3)更新新到達數據點所在網格即可。這有效提升了在線算法的時間效率。

如果新到達數據對應的網格當前是空的，則gridlist中不存在該網格的特征向量，需要網格特征向量插入gridlist中響應位置。隨著時間推移，gridlist中的網格會越來越多，在高維數據空間，進行較高精度的網格劃分時，gridlist中網格數量上限kd很大。gridlist中網格過多，會降低在線算法的時間空間效率，同時增加與遠端離線部分的通信開銷。因此有必要定期刪除過期網格。

過期網格是這樣的網格：這些網格在很久之前曾經有數據到達，但當前相當一段時間無數據點到達。隨著時間推移，這些網格密度衰退，以至于遠小于致密網格的閾值。無論考察其時間相關性還是密度值的大小，這類網格對于當前時刻的數據分布影響甚微，可以忽略不計。為了避免這類網格帶來的資源負擔，每次提交概要之前檢查網格最后更新時間，距離當前時刻超過閾值to的視為過期網格刪除。當to足夠大時，提交的概要信息為真實統計信息的近似值，不影響聚類結果。

1.5離線聚類生成

對于融合多路數據流融合后的概要信息gridlist-sum，根據式(5)其每個網格的密度為當前時刻的密度，則當前d維空間所有網格總重量等于所有n個非空網格的密度和：

(7)

由于任意子空間的網格密度可以通過d維全空間投影得到，因此gridlist-sum提供了DENCOS[14]發現任意子空間聚類的完整信息，S的任一p維子空間Sp每個網格的平均密度為：

(8)

如果一個p維致密網格的密度不小于該子空間閾值，則認定為致密網格,閾值為：

(9)

根據式(4)可以得到每一個網格id對應的頻繁模式向量表示g=(v1,v2,…,vd)，其中vi與[(xi-Mini),εi]一一對應，為第i維上第[(xi-Mini),εi]+1個間隔區間。DENCOS根據以上信息，找出所有子空間聚類并輸出。

1.6確定gap及t0的策略

在線部分按周期gap刪除過期網格并提交概要信息。gap取值的約束條件包括離線部分聚類的速度和網格密度衰退的速度。周期過短，頻繁地提交并聚類運算，造成過多的資源負擔，而實際聚類又沒有明顯變化因而沒有意義；周期過長，則可能無法捕捉數據流分布的演進。

由式(9)可知，d維滿空間的閾值最小，且維度數相差1的子空間閾值間存在k倍關系。可以認為一個沒有新數據到達的網格其密度衰退k倍，即是數據分布發生明顯改變的關鍵時間點。則：

λgap=k

(10)

用k作為基準來決定周期的另一個好處是，隨著k增大，網格衰退的和離線計算兩個約束條件都變慢，反之都變快，便于決定周期取值。

確定過期網格是為了避免gridlist隨著時間單調遞增帶來的開銷負擔，其約束條件主要是數據采集終端資源，以及過期網格的密度衰退至足夠小，以至不對聚類結果造成影響。因此在終端資源允許的情況下，to應取值盡量大，以滿足：

to?lnλ(τd)

(11)

2分布式數據流聚類算法設計

2.1在線算法

除待處理的數據流外，在線部分的算法需要用戶提供若干參數，包括數據流的維數d,以及劃分網格需要的參數k和L，用以建立網格結構。L為一個向量，依次代表每個維度取值范圍，在網格劃分過程中將每個維度劃分為等長的k個間隔。gridlist為存儲非空網格特征向量列表,存儲數據在整個網格空間分布的概要信息，初始為空。數據流中新的數據x=(x1,x2,…,xd)到達，首先計算其對應的密度網格g的id。如果之前沒有數據到達該網格或該網格數據由于過于陳舊被清除，則需要向gridlist中插入該網格的特征向量，否則直接更新該網格特征向量。在線部分以gap為時間周期，移除過期網格，提交gridlist至離線部分，離線部分依據多路數據流的概要信息生成類。在線部分算法如下：

1procedure DEN-Stream-online

//input d,k,L

2gridlist=grid-partition;

3while data stream is active do

4read record x=(x1,x2,…,xd);

5compute the id of density grid g which contains x;

6if g not in gridlist then insert g to gridlist;

7update the characteristic vector of g;

8if t mod gap==0 then

9remove grids out of date;

10commit gridlist;

//offline clusters with it

11end if

12end while

13end_procedure

2.2離線算法

多路數據流概要信息在離線部分被融合，gridlist-sum存儲多路數據流融合后的概要信息。融合的過程遍歷每一個子數據流提交的概要信息，求出每個網格總的密度。離線部分算法如下：

1procedure DEN-Stream-offline

//input d,k,α

2gridlist-sum=grid-partition;

3for each substream

4for each member vector g of gridlist

5if g not in gridlist-sum then insert g to gridlist-sum;

6translate grid to vector presentation;

7update the characteristic vector of g in gridlist-sum;

8end for

9end for

10Compute the total weight W of all grid in gridlist-sum;

11call method DENCOS(d,k,W,α, gridlist-sum);

12end_procedure

根據聚類DENCOS[14]模型，需要將id指代的網格轉換為d維向量描述作為后期挖掘的頻繁項，網格的密度將會在聚類生成過程中作為網格向量的頻繁計數。

在開始聚類過程之前，需要計算gridlist-sum中所有網格的密度之和，亦即總的“重量”W，結合用戶指定的參數α[14]，DENCOS子空間聚類過程中的密度閾值得以確定。

3測試評估與分析

3.1測試數據集

為了驗證方法反映數據分布隨著時間演進的性能，采用合成二維數據集DS1，所有16 000個數據點均勻分布在x軸100～900之間，y軸400～600之間，長800，寬200。數據集包含每個數據點到達時刻心系，時序上x=100處數據最先到達，數據點以均勻的速率在時間T內從x=100開始勻速移動至x=900覆蓋整個區域。在后續驗證方法效率和形成概要規模時，采用從加州大學歐文分校提供的用于機器學習的數據庫(http://archive.ics.uci.edu/ml/)選取的真實數據集DS2。

3.2實驗結果與分析

(1) 衰退與演進

為了驗證分布式多路數據流環境下正確反映數據分布演進的能力，將DS1分為不均等三路數據流，數據點比例為5:2:1。數據點在各自子數據流中的到達時間為DS1中到達時刻相同，即每個子數據流中數據點到達不均勻，速率不相等。在數據持續時間T內，四個不同時刻輸出的聚類結果如圖1所示。可以看出，方法任意時刻的聚類輸出能夠隨著數據分布規律的變化演進，反映當前時刻及最近一段時間內到達數據的分布規律，而較早到達的數據隨著時間推移衰退殆盡，不影響當前聚類效果。

圖1　不同時刻聚類結果的演進

圖2反映了不同衰減因子下較早到達的數據對聚類結果的影響。選擇t=T時刻，即所有數據完全到達時刻，分別選擇四個不同的衰退因子取值。聚類結果表明方法能夠在多路環境下正確反映較早數據及其分布規律在聚類結果中的漸進衰退。衰退因子越小，衰退越迅速。

圖2　不同衰退因子下歷史聚類的衰退

(2) 在線效率

從數據集DS2隨機選取一個5維空間，共60 000數據點的數據集，使其按時間順序均勻到達，形成一個穩定數據流。分別用本文方法在線算法和D-Stream[5]算法的在線算法處理該數據流，兩種算法都在每個在線周期內吸收100個數據點，維護在線概要并提交。對比兩種算法處理每個gap內數據所需時間如圖3所示。

圖3　在線算法時間效率對比

由圖3可知，兩個算法在啟動階段，由于要不斷向空的概要信息中插入新的網格，會導致較大的時間開銷，之后逐漸趨于穩定。本文算法在第100個gap和第470個gap附近有數次時間開銷的峰值，原因在于此時數據分布隨著時間發生遷移，生成的聚類發生明顯改變。這個過程中新舊聚類的網格同時存在于概要信息中，增加了在線算法的時間空間開銷。聚類遷移完成，數據分布穩定在新的聚類區域后，本算法概要信息中只存在新聚類的網格，而早前聚類網格作為過期網格被刪除，在線算法的時間、空間開銷恢復穩定。400gap之后本文算法比對比算法時間效率高85%～208%。

對比算法在每次數據流聚類遷移之后時間開銷就會經歷一次增長。原因在于按照密度閾值拋棄過期網格，在較高維度空間需要更長的時間。高維數據空間存在大量的空白網格，僅少數網格存在數據，聚類區域的密度會遠大于整個高維空間的平均密度。因此，即使沒有新的數據點到達，聚類區域網格的密度要衰減到平均密度以下也是一個漫長的過程。在概要信息中保留舊聚類網格不僅降低在線算法的效率，增加開銷，還會在當前時間輸出早期聚類，形成錯誤聚類結果。

(3) 概要規模

與在線算法時間效率對比相同的實驗相同方法，對比兩個算法在每個gap形成的概要信息規模。如圖4所示，實驗結果與時間效率對比實驗的結果相符。本文算法由于及時拋棄過期網格，能夠在每次數據分布改變之后迅速將概要信息規模恢復至合理范圍，壓縮需要通信的概要規模73.5%～82.1%，節約通信帶寬。而對比算法D-Stream在相當長時間內不能拋棄過期網格，在數據分布改變數次之后仍保留最早期的概要網格，導致概要信息不斷累積，造成資源浪費的同時引入早期聚類結果，不能正確反映數據分布隨時間的演進。

圖4　概要信息規模對比

4結語

本文提出的分布式數據流聚類方法，采用全局統一的網格劃分和密度衰退，使得多路數據流概要信息融合的過程簡潔、意義明確、準確性高。通過適當的過期網格拋棄策略將概要信息規模維持在合理水平，提高了在線算法運行的時間、空間效率并降低概要信息提交過程中的通信開銷。尤其在高維數據流處理過程中，本文算法與對比算法相比，優勢更加明顯。實驗表明，本算法能在分布式多路數據流環境下找出正確聚類，并根據數據分布隨時間的遷移，演進聚類結果；同時，本文算法具有更高的在線效率和更小的概要規模以節省帶寬資源。

參考文獻

[1] 張建朋,陳福才,李邵梅,等.基于仿射傳播的進化數據流在線聚類算法[J].模式識別與人工智能,2014,27(5):443-451.

[2] 郭昆,張岐山.基于灰關聯分析的多數據流聚類[J].模式識別與人工智能,2011,24(6):769-775.

[3] Aggarwal C C,Han J,Wang J,et al.A framework for clustering evolving data streams[C]//Proceedings of the 29th international conference on Very large data bases-Volume 29.VLDB Endowment,2003:81-92.

[4] 于彥偉,王沁,鄺俊,等.一種基于密度的空間數據流在線聚類算法[J].自動化學報,2012,38(6):1051-1059.

[5] Amini A,Saboohi H,Wah T Y.A Multi Density-Based Clustering Algorithm for Data Stream with Noise[C]//Data Mining Workshops,IEEE International Conference on.IEEE,2013:1105-1112.

[6] Chen Y,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.ACM,2007:133-142.

[7] Ren J,Cai B,Hu C.Clustering over data streams based on grid density and index tree[J].Journal of Convergence Information Technology,2011,6(1):83-93.

[8] Pan J.DS_CABOSFV clustering algorithm for high dimensional data stream[C]//2012 4th International Conference on Awareness Science and Technology (iCAST),IEEE,2012:16-19.

[9] Zhang D,Tian H,Sang Y.A Clustering Algorithm Based on Density-Grid for Stream Data[C]//Parallel and Distributed Computing,Applications and Technologies,International Conference on.IEEE,2012:398-403.

[10] 于翔,印桂生,許憲東,等.一種基于區域劃分的數據流子空間聚類方法[J].計算機研究與發展,2014(1):88-95.

[11] Tu L,Chen Y.Stream data clustering based on grid density and attraction[J].ACM Transactions on Knowledge Discovery from Data (TKDD),2009,3(3):167-176.

[12] Chairukwattana R,Kangkachit T,Rakthanmanon T,et al.Efficient evolution-based clustering of high dimensional data streams with dimension projection[C]//Computer Science and Engineering Conference (ICSEC),2013 International.IEEE,2013:185-190.

[13] Hou G B,Yao R X,Ren J D,et al.Irregular Grid-based Clustering Over High-Dimensional Data Streams[C]//2010 First International Conference on Pervasive Computing Signal Processing and Applications (PCSPA),IEEE,2010:783-786.

[14] Chu Y H,Huang J W,Chuang K T,et al.Density conscious subspace clustering for high-dimensional data[J].IEEE Transactions on Knowledge and Data Engineering,2010,22(1):16-30.

收稿日期：2014-12-03。國家科技支撐計劃項目(2012BAH73 F01)；國家高技術研究發展計劃項目(2011AA01A102)；中科院先導專項課題(XDA06040301)。李長路，博士生，主研領域：數據挖掘，用戶興趣建模。王勁林，研究員。郭志川，副研究員。韓銳，副研究員。

中圖分類號TP3

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.07.013

DEN-STREAM：A DISTRIBUTED DATA STREAM CLUSTERING METHOD

Li Changlu1,2Wang Jinlin2Guo Zhichuan2Han Rui2

1(UniversityofChineseAcademyofSciences,Beijing100190,China)2(NationalNetworkNewMediaEngineeringResearchCenter,InstituteofAcoustics,ChineseAcademyofSciences,Beijing100190,China)

AbstractCurrent data stream clustering methods are difficult to take into account the high-dimensional data problems including data sparsity and subspace clustering, etc., while the distributed data stream raises more challenges on data stream clustering, such as online computational efficiency, communication overhead and the integration of multi-channel data. The distributed data stream clustering method proposed in this paper uses globally uniform meshing and declining time to support the integration of multi-channel data streams, and controls the summary size by periodically checking and removing outdated grids. By scanning multi-channel high-dimensional data stream once, the method finds the clusters with arbitrary shapes in subspace of high-dimensional data stream, and they reflect the evolution of data distribution over time. The online component in the paper has high efficiency and low overhead, succinct summary information and low communication cost. Experiment shows that the proposed method can correctly cluster the distributed data streams and evolve them, the efficiency of online component is high, and the summary size is small as well.

KeywordsDistributed data streamSubspace clusteringGrid-based clusteringHigh-dimensional data