李長(zhǎng)路　王勁林　郭志川　韓　銳

1(中國(guó)科學(xué)院大學(xué)　北京 100190)2(中國(guó)科學(xué)院聲學(xué)研究所國(guó)家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心　北京 100190)

?

DEN-Stream：一種分布式數(shù)據(jù)流聚類方法

李長(zhǎng)路1,2王勁林2郭志川2韓銳2

1(中國(guó)科學(xué)院大學(xué)北京 100190)2(中國(guó)科學(xué)院聲學(xué)研究所國(guó)家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心北京 100190)

摘要現(xiàn)有的數(shù)據(jù)流聚類方法很難兼顧數(shù)據(jù)稀疏和子空間聚類等高維數(shù)據(jù)難題，而分布式數(shù)據(jù)流對(duì)數(shù)據(jù)流聚類提出包括在線計(jì)算效率、通信開(kāi)銷以及多路數(shù)據(jù)的融合等更多挑戰(zhàn)。提出分布式數(shù)據(jù)流聚類方法，采用全局統(tǒng)一的網(wǎng)格劃分和衰退時(shí)間以支持多路數(shù)據(jù)流融合，并周期性檢查和刪除過(guò)期網(wǎng)格來(lái)控制概要規(guī)模。通過(guò)對(duì)多路高維數(shù)據(jù)流的一遍掃描，發(fā)現(xiàn)高維數(shù)據(jù)流子空間任意形狀的聚類，并反映數(shù)據(jù)分布隨時(shí)間的演化。在線組件效率高開(kāi)銷低，概要信息簡(jiǎn)潔，通信代價(jià)低。實(shí)驗(yàn)表明，該方法能夠?qū)Ψ植际綌?shù)據(jù)流正確聚類并演進(jìn)，在線組件效率高，概要規(guī)模小。

關(guān)鍵詞分布式數(shù)據(jù)流子空間聚類網(wǎng)格聚類高維數(shù)據(jù)

0引言

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

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

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

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

1分布式數(shù)據(jù)流聚類方法研究

1.1網(wǎng)格劃分

S=A1×A2×…×Ad表示d數(shù)據(jù)流的滿空間，A1,A2,…,Ad為S的各個(gè)維度屬性。其中Ai取值范圍為[Mini,Maxi)，維向量L=(l1,l2,…,ld)存儲(chǔ)響應(yīng)維度的取值區(qū)間長(zhǎng)度：

li=Maxi-Mini

(1)

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

(2)

數(shù)據(jù)流的d維全空間被劃分為kd個(gè)矩形單元組成的網(wǎng)格。

1.2特征向量

d維空間網(wǎng)格結(jié)構(gòu)中每一個(gè)網(wǎng)格由一個(gè)特征向量描述，其定義為(id,D,tg)。其中tg為該網(wǎng)格最后一個(gè)數(shù)據(jù)點(diǎn)到達(dá)時(shí)間，D為該網(wǎng)格的密度在最后一個(gè)數(shù)據(jù)點(diǎn)到達(dá)時(shí)更新的結(jié)果，空網(wǎng)格置零。若在時(shí)刻t一個(gè)新的數(shù)據(jù)點(diǎn)x到達(dá)，其對(duì)應(yīng)網(wǎng)格密度更新為：

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

(3)

任何數(shù)據(jù)對(duì)網(wǎng)格密度的貢獻(xiàn)隨著時(shí)間延伸而減弱，后到達(dá)數(shù)據(jù)對(duì)網(wǎng)格密度具有更大的貢獻(xiàn)。λ(λ∈(0,1))為網(wǎng)格密度的時(shí)間衰退因子。

id為識(shí)別網(wǎng)格的編號(hào)，為了便于將數(shù)據(jù)點(diǎn)x=(x1,x2,…,xd)映射到對(duì)應(yīng)的網(wǎng)格，定義id為：

(4)

所有網(wǎng)格的編號(hào)為1至kd的正整數(shù)。由于全局統(tǒng)一的網(wǎng)格劃分以及網(wǎng)格標(biāo)識(shí)，使得分布在多個(gè)數(shù)據(jù)流中的數(shù)據(jù)在摘要中影響了相同標(biāo)識(shí)的網(wǎng)格密度，多路數(shù)據(jù)流網(wǎng)格密度計(jì)算空間上保持全局一致。

1.3時(shí)間度量與多路融合

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

本文采用實(shí)際時(shí)間作為聚類演化的依據(jù)，統(tǒng)一各路數(shù)據(jù)流的時(shí)間，從而使多路數(shù)據(jù)流融合成為可能?？偣瞞路數(shù)據(jù)流，對(duì)于網(wǎng)格g，在當(dāng)前時(shí)間刻度t的密度融合計(jì)算公式為：

(5)

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

1.4概要信息的在線維護(hù)

gridlist為存儲(chǔ)子數(shù)據(jù)流概要信息的鏈表，其成員為非空網(wǎng)格的特征向量，按網(wǎng)格id順序排列。由于引入時(shí)間衰退因子來(lái)反映流中數(shù)據(jù)分布的演化，所有網(wǎng)格的密度都隨著時(shí)間變化。對(duì)于沒(méi)有新數(shù)據(jù)到來(lái)的網(wǎng)格g，其任意時(shí)間的密度為：

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

(6)

根據(jù)式(6)，只需要知道其特征向量，即可計(jì)算出當(dāng)前時(shí)刻密度。因此，沒(méi)有必要不斷更新gridlist中所有網(wǎng)格的特征向量，只需根據(jù)式(3)更新新到達(dá)數(shù)據(jù)點(diǎn)所在網(wǎng)格即可。這有效提升了在線算法的時(shí)間效率。

如果新到達(dá)數(shù)據(jù)對(duì)應(yīng)的網(wǎng)格當(dāng)前是空的，則gridlist中不存在該網(wǎng)格的特征向量，需要網(wǎng)格特征向量插入gridlist中響應(yīng)位置。隨著時(shí)間推移，gridlist中的網(wǎng)格會(huì)越來(lái)越多，在高維數(shù)據(jù)空間，進(jìn)行較高精度的網(wǎng)格劃分時(shí)，gridlist中網(wǎng)格數(shù)量上限kd很大。gridlist中網(wǎng)格過(guò)多，會(huì)降低在線算法的時(shí)間空間效率，同時(shí)增加與遠(yuǎn)端離線部分的通信開(kāi)銷。因此有必要定期刪除過(guò)期網(wǎng)格。

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

1.5離線聚類生成

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

(7)

由于任意子空間的網(wǎng)格密度可以通過(guò)d維全空間投影得到，因此gridlist-sum提供了DENCOS[14]發(fā)現(xiàn)任意子空間聚類的完整信息，S的任一p維子空間Sp每個(gè)網(wǎng)格的平均密度為：

(8)

如果一個(gè)p維致密網(wǎng)格的密度不小于該子空間閾值，則認(rèn)定為致密網(wǎng)格,閾值為：

(9)

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

1.6確定gap及t0的策略

在線部分按周期gap刪除過(guò)期網(wǎng)格并提交概要信息。gap取值的約束條件包括離線部分聚類的速度和網(wǎng)格密度衰退的速度。周期過(guò)短，頻繁地提交并聚類運(yùn)算，造成過(guò)多的資源負(fù)擔(dān)，而實(shí)際聚類又沒(méi)有明顯變化因而沒(méi)有意義；周期過(guò)長(zhǎng)，則可能無(wú)法捕捉數(shù)據(jù)流分布的演進(jìn)。

由式(9)可知，d維滿空間的閾值最小，且維度數(shù)相差1的子空間閾值間存在k倍關(guān)系?？梢哉J(rèn)為一個(gè)沒(méi)有新數(shù)據(jù)到達(dá)的網(wǎng)格其密度衰退k倍，即是數(shù)據(jù)分布發(fā)生明顯改變的關(guān)鍵時(shí)間點(diǎn)。則：

λgap=k

(10)

用k作為基準(zhǔn)來(lái)決定周期的另一個(gè)好處是，隨著k增大，網(wǎng)格衰退的和離線計(jì)算兩個(gè)約束條件都變慢，反之都變快，便于決定周期取值。

確定過(guò)期網(wǎng)格是為了避免gridlist隨著時(shí)間單調(diào)遞增帶來(lái)的開(kāi)銷負(fù)擔(dān)，其約束條件主要是數(shù)據(jù)采集終端資源，以及過(guò)期網(wǎng)格的密度衰退至足夠小，以至不對(duì)聚類結(jié)果造成影響。因此在終端資源允許的情況下，to應(yīng)取值盡量大，以滿足：

to?lnλ(τd)

(11)

2分布式數(shù)據(jù)流聚類算法設(shè)計(jì)

2.1在線算法

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

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離線算法

多路數(shù)據(jù)流概要信息在離線部分被融合，gridlist-sum存儲(chǔ)多路數(shù)據(jù)流融合后的概要信息。融合的過(guò)程遍歷每一個(gè)子數(shù)據(jù)流提交的概要信息，求出每個(gè)網(wǎng)格總的密度。離線部分算法如下：

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

根據(jù)聚類DENCOS[14]模型，需要將id指代的網(wǎng)格轉(zhuǎn)換為d維向量描述作為后期挖掘的頻繁項(xiàng)，網(wǎng)格的密度將會(huì)在聚類生成過(guò)程中作為網(wǎng)格向量的頻繁計(jì)數(shù)。

在開(kāi)始聚類過(guò)程之前，需要計(jì)算gridlist-sum中所有網(wǎng)格的密度之和，亦即總的“重量”W，結(jié)合用戶指定的參數(shù)α[14]，DENCOS子空間聚類過(guò)程中的密度閾值得以確定。

3測(cè)試評(píng)估與分析

3.1測(cè)試數(shù)據(jù)集

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

3.2實(shí)驗(yàn)結(jié)果與分析

(1) 衰退與演進(jìn)

為了驗(yàn)證分布式多路數(shù)據(jù)流環(huán)境下正確反映數(shù)據(jù)分布演進(jìn)的能力，將DS1分為不均等三路數(shù)據(jù)流，數(shù)據(jù)點(diǎn)比例為5:2:1。數(shù)據(jù)點(diǎn)在各自子數(shù)據(jù)流中的到達(dá)時(shí)間為DS1中到達(dá)時(shí)刻相同，即每個(gè)子數(shù)據(jù)流中數(shù)據(jù)點(diǎn)到達(dá)不均勻，速率不相等。在數(shù)據(jù)持續(xù)時(shí)間T內(nèi)，四個(gè)不同時(shí)刻輸出的聚類結(jié)果如圖1所示?？梢钥闯?，方法任意時(shí)刻的聚類輸出能夠隨著數(shù)據(jù)分布規(guī)律的變化演進(jìn)，反映當(dāng)前時(shí)刻及最近一段時(shí)間內(nèi)到達(dá)數(shù)據(jù)的分布規(guī)律，而較早到達(dá)的數(shù)據(jù)隨著時(shí)間推移衰退殆盡，不影響當(dāng)前聚類效果。

圖1　不同時(shí)刻聚類結(jié)果的演進(jìn)

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

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

(2) 在線效率

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

圖3　在線算法時(shí)間效率對(duì)比

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

對(duì)比算法在每次數(shù)據(jù)流聚類遷移之后時(shí)間開(kāi)銷就會(huì)經(jīng)歷一次增長(zhǎng)。原因在于按照密度閾值拋棄過(guò)期網(wǎng)格，在較高維度空間需要更長(zhǎng)的時(shí)間。高維數(shù)據(jù)空間存在大量的空白網(wǎng)格，僅少數(shù)網(wǎng)格存在數(shù)據(jù)，聚類區(qū)域的密度會(huì)遠(yuǎn)大于整個(gè)高維空間的平均密度。因此，即使沒(méi)有新的數(shù)據(jù)點(diǎn)到達(dá)，聚類區(qū)域網(wǎng)格的密度要衰減到平均密度以下也是一個(gè)漫長(zhǎng)的過(guò)程。在概要信息中保留舊聚類網(wǎng)格不僅降低在線算法的效率，增加開(kāi)銷，還會(huì)在當(dāng)前時(shí)間輸出早期聚類，形成錯(cuò)誤聚類結(jié)果。

(3) 概要規(guī)模

與在線算法時(shí)間效率對(duì)比相同的實(shí)驗(yàn)相同方法，對(duì)比兩個(gè)算法在每個(gè)gap形成的概要信息規(guī)模。如圖4所示，實(shí)驗(yàn)結(jié)果與時(shí)間效率對(duì)比實(shí)驗(yàn)的結(jié)果相符。本文算法由于及時(shí)拋棄過(guò)期網(wǎng)格，能夠在每次數(shù)據(jù)分布改變之后迅速將概要信息規(guī)?；謴?fù)至合理范圍，壓縮需要通信的概要規(guī)模73.5%～82.1%，節(jié)約通信帶寬。而對(duì)比算法D-Stream在相當(dāng)長(zhǎng)時(shí)間內(nèi)不能拋棄過(guò)期網(wǎng)格，在數(shù)據(jù)分布改變數(shù)次之后仍保留最早期的概要網(wǎng)格，導(dǎo)致概要信息不斷累積，造成資源浪費(fèi)的同時(shí)引入早期聚類結(jié)果，不能正確反映數(shù)據(jù)分布隨時(shí)間的演進(jìn)。

圖4　概要信息規(guī)模對(duì)比

4結(jié)語(yǔ)

本文提出的分布式數(shù)據(jù)流聚類方法，采用全局統(tǒng)一的網(wǎng)格劃分和密度衰退，使得多路數(shù)據(jù)流概要信息融合的過(guò)程簡(jiǎn)潔、意義明確、準(zhǔn)確性高。通過(guò)適當(dāng)?shù)倪^(guò)期網(wǎng)格拋棄策略將概要信息規(guī)模維持在合理水平，提高了在線算法運(yùn)行的時(shí)間、空間效率并降低概要信息提交過(guò)程中的通信開(kāi)銷。尤其在高維數(shù)據(jù)流處理過(guò)程中，本文算法與對(duì)比算法相比，優(yōu)勢(shì)更加明顯。實(shí)驗(yàn)表明，本算法能在分布式多路數(shù)據(jù)流環(huán)境下找出正確聚類，并根據(jù)數(shù)據(jù)分布隨時(shí)間的遷移，演進(jìn)聚類結(jié)果；同時(shí)，本文算法具有更高的在線效率和更小的概要規(guī)模以節(jié)省帶寬資源。

參考文獻(xiàn)

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

[2] 郭昆,張岐山.基于灰關(guān)聯(lián)分析的多數(shù)據(jù)流聚類[J].模式識(shí)別與人工智能,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] 于彥偉,王沁,鄺俊,等.一種基于密度的空間數(shù)據(jù)流在線聚類算法[J].自動(dòng)化學(xué)報(bào),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] 于翔,印桂生,許憲東,等.一種基于區(qū)域劃分的數(shù)據(jù)流子空間聚類方法[J].計(jì)算機(jī)研究與發(fā)展,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。國(guó)家科技支撐計(jì)劃項(xiàng)目(2012BAH73 F01)；國(guó)家高技術(shù)研究發(fā)展計(jì)劃項(xiàng)目(2011AA01A102)；中科院先導(dǎo)專項(xiàng)課題(XDA06040301)。李長(zhǎng)路，博士生，主研領(lǐng)域：數(shù)據(jù)挖掘，用戶興趣建模。王勁林，研究員。郭志川，副研究員。韓銳，副研究員。

中圖分類號(hào)TP3

文獻(xiàn)標(biāo)識(shí)碼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