張東月,周麗華,吳湘云,趙麗紅

1(云南大學(xué) 信息學(xué)院,云南 昆明 650000)

2(麗江師范高等?？茖W(xué)校,云南 麗江 674199)

數(shù)據(jù)流是一種隨著時(shí)間增加而順序、快速、大量、連續(xù)到達(dá)的數(shù)據(jù)序列.近年來,隨著軟硬件的發(fā)展,大量的數(shù)據(jù)流不斷產(chǎn)生,如金融數(shù)據(jù)、視頻監(jiān)控?cái)?shù)據(jù)、傳感數(shù)據(jù)和網(wǎng)絡(luò)流量數(shù)據(jù)等.這些數(shù)據(jù)流大部分是無(wú)標(biāo)簽的,所以實(shí)時(shí)聚類數(shù)據(jù)流并從中提取有價(jià)值的信息,成為了數(shù)據(jù)挖掘領(lǐng)域的重要問題之一[1-4].然而,由于數(shù)據(jù)流的連續(xù)性、無(wú)限性、演變性等特點(diǎn),要求數(shù)據(jù)流聚類算法只能在資源約束的條件下單次掃描數(shù)據(jù)流,并能夠隨時(shí)間的變化追蹤簇的形狀和位置的變化[5,6].除此之外,提高數(shù)據(jù)流聚類算法的精度和效率,也是一直存在的重要挑戰(zhàn).

現(xiàn)有的數(shù)據(jù)流聚類算法大多采用經(jīng)典的在線/離線框架[7]來處理數(shù)據(jù)流.在線階段將到達(dá)的數(shù)據(jù)對(duì)象映射到一組支持快速查找的網(wǎng)格結(jié)構(gòu)中,以此匯總數(shù)據(jù)流并提取數(shù)據(jù)流的摘要信息.每個(gè)網(wǎng)格都類似于一組數(shù)據(jù)對(duì)象的集合,是在單次掃描數(shù)據(jù)流的環(huán)境下創(chuàng)建的.離線階段,根據(jù)用戶或應(yīng)用程序的需要,使用傳統(tǒng)的(或改進(jìn)的)聚類算法將網(wǎng)格結(jié)構(gòu)合并,生成最終聚類[8-10].采用在線/離線框架的數(shù)據(jù)流聚類算法通過網(wǎng)格提取數(shù)據(jù)流的概要信息,能夠較快地處理數(shù)據(jù)流并支持實(shí)時(shí)聚類,但是這些聚類算法在將數(shù)據(jù)對(duì)象映射到網(wǎng)格并增量更新網(wǎng)格時(shí),通常假設(shè)網(wǎng)格之間彼此獨(dú)立,忽略了網(wǎng)格之間的相互影響,使得提取的數(shù)據(jù)流概要信息不夠精確,從而影響了聚類精度.

為了提高聚類精度,MR-Stream[11]映射數(shù)據(jù)時(shí)使用了尺寸更加精細(xì)的網(wǎng)格;DBSTREAM[12]引入共享密度來檢測(cè)微簇內(nèi)數(shù)據(jù)的分布狀態(tài),避免了兩個(gè)微簇相交區(qū)域密度較低卻仍然將他們聚為一類的現(xiàn)象,提高了聚類質(zhì)量.但是網(wǎng)格的精細(xì)化既增大了內(nèi)存占用又降低了算法效率;而共享密度不僅需要計(jì)算微簇之間關(guān)系,還要計(jì)算數(shù)據(jù)對(duì)象與微簇的關(guān)系,這樣才能捕捉到兩個(gè)微簇相交區(qū)域的數(shù)據(jù)量,同樣降低了算法效率.本文提出了一種基于網(wǎng)格耦合的數(shù)據(jù)流聚類算法,稱為 GCStream.首先,基于網(wǎng)格內(nèi)的數(shù)據(jù)對(duì)象定義網(wǎng)格權(quán)重,并在聚類過程中不再獨(dú)立處理網(wǎng)格,而是基于網(wǎng)格內(nèi)數(shù)據(jù)對(duì)象的分布狀態(tài)考慮網(wǎng)格之間權(quán)重的相互影響,即,一個(gè)網(wǎng)格權(quán)重的變化會(huì)使相鄰網(wǎng)格的權(quán)重增加或減小,網(wǎng)格的耦合更加準(zhǔn)確地表達(dá)了數(shù)據(jù)之間的相關(guān)性,從而提高聚類精度.其次,基于網(wǎng)格內(nèi)數(shù)據(jù)的分布,通過搜索密度相連的網(wǎng)格完成聚類,并根據(jù)高密度網(wǎng)格的變化捕捉簇的演化.

本文的主要貢獻(xiàn)包括:

(1) 聚類過程中不再獨(dú)立處理網(wǎng)格,而是考慮了網(wǎng)格之間的耦合關(guān)系,從而更加準(zhǔn)確地表達(dá)了數(shù)據(jù)之間的相關(guān)性;

(2) 提出了一種基于網(wǎng)格耦合的數(shù)據(jù)流聚類算法,該算法不需要指定簇的數(shù)目,只需通過搜索密度相連的網(wǎng)格完成聚類,并根據(jù)高密度網(wǎng)格的變化捕捉簇的演化;

(3) 在人工和真實(shí)數(shù)據(jù)流上進(jìn)行了實(shí)驗(yàn)驗(yàn)證,通過實(shí)驗(yàn)對(duì)比了所提算法的性能.

本文第1節(jié)介紹數(shù)據(jù)流聚類的典型算法.第2節(jié)介紹網(wǎng)格耦合的相關(guān)概念和定義.第3節(jié)給出GCStream的算法流程并分析算法的時(shí)間復(fù)雜度.第4節(jié)給出在合成和真實(shí)數(shù)據(jù)集上的對(duì)比實(shí)驗(yàn).最后,總結(jié)論文工作.

1 相關(guān)工作

現(xiàn)有的數(shù)據(jù)流聚類算法可以分為基于劃分的、基于層次的以及基于密度的方法[13].前兩種方法主要基于對(duì)象之間的距離進(jìn)行聚類,比如STREAM[14]算法采用類似批處理的方式將數(shù)據(jù)流分塊,將每一批數(shù)據(jù)分為k個(gè)簇,通過保留k個(gè)簇的中心點(diǎn)匯總每一批數(shù)據(jù).STREAM算法無(wú)法在任意時(shí)刻給出當(dāng)前數(shù)據(jù)流的聚類結(jié)果,并且也沒有考慮數(shù)據(jù)流的演變性.CluStream[7]算法提出了在線/離線兩階段處理框架:在線階段通過微簇結(jié)構(gòu)以增量方式維護(hù)數(shù)據(jù)流的概要信息,離線階段基于概要信息和用戶輸入產(chǎn)生聚類結(jié)果,克服了STREAM算法不能實(shí)時(shí)產(chǎn)生聚類結(jié)果的問題.但是 CluStream 算法沒有體現(xiàn)近期數(shù)據(jù)與歷史數(shù)據(jù)對(duì)聚類結(jié)果的不同影響,并且在高維數(shù)據(jù)流的聚類上表現(xiàn)不佳.HPStream算法[15]通過投影技術(shù)和衰減簇結(jié)構(gòu)對(duì)CluStream算法進(jìn)行了改進(jìn),能夠集成當(dāng)前數(shù)據(jù)和歷史數(shù)據(jù),更好地聚類高維數(shù)據(jù)流.但是,HPStream 算法仍然不能聚類任意形狀的數(shù)據(jù)流,并對(duì)噪聲敏感.

基于密度的方法通過查找被低密度區(qū)域包圍的高密度區(qū)域來進(jìn)行聚類,能夠發(fā)現(xiàn)任意形狀的簇并且可以去除噪聲.DenStream 算法[16]、D-Stream 算法[8]、MuDi-Stream 算法[9]、MR-Stream[11]和 DBSTREAM 算法[12]都繼承了CluStream的在線/離線框架.DenStream算法的在線階段通過將數(shù)據(jù)點(diǎn)分配給離它最近的微簇來進(jìn)行微聚類,并且提出了核心微簇、潛在核心微簇和離群微簇的概念來區(qū)分正常簇的數(shù)據(jù)、可能發(fā)展為正常簇的數(shù)據(jù)和噪聲數(shù)據(jù);離線階段通過 DBSCAN算法進(jìn)行宏聚類,所以它能發(fā)現(xiàn)任意形狀的簇.D-Stream算法的在線階段將數(shù)據(jù)流映射到相應(yīng)的網(wǎng)格,并通過網(wǎng)格密度對(duì)網(wǎng)格進(jìn)行分類;離線階段通過合并相鄰網(wǎng)格產(chǎn)生聚類結(jié)果.MuDi-Stream 算法的在線階段計(jì)算數(shù)據(jù)點(diǎn)與網(wǎng)格中心的距離,并將數(shù)據(jù)點(diǎn)分配給距離其最短的網(wǎng)格;離線階段通過改進(jìn)的DBSCAN算法生成聚類結(jié)果,在多密度數(shù)據(jù)流上表現(xiàn)較好.MR-Stream算法使用網(wǎng)格樹結(jié)構(gòu)來存儲(chǔ)網(wǎng)格,樹中每個(gè)節(jié)點(diǎn)代表一個(gè)網(wǎng)格,并且存有其父和子節(jié)點(diǎn)的概要信息.MR-Stream 算法的在線階段將當(dāng)前數(shù)據(jù)映射到網(wǎng)格樹的相應(yīng)葉子節(jié)點(diǎn),離線階段在不同網(wǎng)格樹高度上通過合并相鄰網(wǎng)格進(jìn)行聚類.該方法本質(zhì)上是通過將大的網(wǎng)格細(xì)分為多個(gè)小網(wǎng)格來提高聚類質(zhì)量,但是網(wǎng)格細(xì)分導(dǎo)致內(nèi)存占用成倍地增加,降低了聚類效率.DBSTREAM 算法通過共享密度對(duì)數(shù)據(jù)流進(jìn)行聚類,其在線階段通過微簇來維護(hù)數(shù)據(jù)流的概要信息,并且通過計(jì)算微簇與微簇、數(shù)據(jù)對(duì)象與微簇之間的關(guān)系來捕捉兩個(gè)微簇之間共同擁有的數(shù)據(jù),即共享密度;離線階段在進(jìn)行宏聚類時(shí)不僅考慮微簇之間的距離關(guān)系,同時(shí)還考慮不同微簇共同擁有的數(shù)據(jù)量.這種通過引入共享密度來檢測(cè)微簇內(nèi)數(shù)據(jù)的分布狀態(tài)的方法,避免了兩個(gè)微簇相交區(qū)域密度較低卻仍然將它們聚為一類的現(xiàn)象,提高了聚類質(zhì)量.但是DBSTREAM算法需要的計(jì)算量較大,降低了聚類效率,這一點(diǎn)在高維數(shù)據(jù)流上尤為突出.

除了聚類效率,上述算法在新數(shù)據(jù)到達(dá)而更新數(shù)據(jù)摘要時(shí)均獨(dú)立處理摘要結(jié)果,忽略了概要之間的相互影響,從而影響了算法的聚類精度.

2 網(wǎng)格耦合的相關(guān)概念和定義

本節(jié)首先介紹網(wǎng)格耦合的相關(guān)概念,然后給出網(wǎng)格耦合的定義.

2.1 基本概念

假設(shè)S=s1×s2×…×sd是一個(gè)d維的空間,將空間si(i=1,2,…,d)均勻分為pi份,即,則空間S被劃分為個(gè)網(wǎng)格.每一個(gè)網(wǎng)格g由組成,其中,ji=1,2,…,pi.g可以表示為g=(j1,j2,…,jd).如果網(wǎng)格在某一維度m(1≤m≤d)上滿足并且,則稱網(wǎng)格g1和g2在第m維相鄰.兩個(gè)網(wǎng)格只要在某一維度相鄰,則稱這兩個(gè)網(wǎng)格為相鄰網(wǎng)格.

設(shè)輸入數(shù)據(jù)流中的每個(gè)數(shù)據(jù)對(duì)象X=(x1,x2,…,xd)是d維空間中的一個(gè)點(diǎn),如果xi∈si,ji,則可以將數(shù)據(jù)對(duì)象X映射到空間S的網(wǎng)格g中,記為g(x)=(j1,j2,…,jd),xi∈si,ji.映射到同一網(wǎng)格中的數(shù)據(jù)對(duì)象距離相近,因此可以對(duì)各個(gè)網(wǎng)格內(nèi)的數(shù)據(jù)進(jìn)行匯總形成概要,從而聚類過程只針對(duì)概要進(jìn)行處理,降低存儲(chǔ)空間和計(jì)算成本.

數(shù)據(jù)流中的數(shù)據(jù)對(duì)象有不同的到達(dá)時(shí)間,對(duì)聚類的貢獻(xiàn)也不同.為了區(qū)分歷史數(shù)據(jù)和新數(shù)據(jù),許多數(shù)據(jù)流聚類算法[1,7,8]為數(shù)據(jù)流中每個(gè)數(shù)據(jù)對(duì)象分配一個(gè)帶有衰減因子的權(quán)重,使其重要性(新鮮度)隨時(shí)間推移而下降.

定義2.1(數(shù)據(jù)權(quán)重).如果數(shù)據(jù)對(duì)象X在tp時(shí)刻到達(dá),那么X在t時(shí)刻的權(quán)重W(X,t)定義為

其中,λ-a(0＜λ-a＜1)為衰減因子.參數(shù)λ和a控制衰減因子的衰減速度,a的絕對(duì)值越大,衰減速度越快.

由于數(shù)據(jù)對(duì)象被映射到網(wǎng)絡(luò)中,因此可以基于數(shù)據(jù)對(duì)象的權(quán)重定義網(wǎng)格權(quán)重.

定義2.2(網(wǎng)格權(quán)重).設(shè)E(g,t)表示到時(shí)刻t為止,映射到網(wǎng)格g中的數(shù)據(jù)對(duì)象集合,則網(wǎng)格g在時(shí)刻t的權(quán)重定義為網(wǎng)格g內(nèi)所有數(shù)據(jù)對(duì)象的權(quán)重之和,即:

網(wǎng)格權(quán)重的大小反映了網(wǎng)格內(nèi)數(shù)據(jù)對(duì)象的數(shù)目和數(shù)據(jù)對(duì)象的新鮮程度.網(wǎng)格內(nèi)數(shù)據(jù)的變化會(huì)引起網(wǎng)格權(quán)重的變化,即使沒有新的數(shù)據(jù)對(duì)象映射到網(wǎng)格g,g的權(quán)重W(g,t)也會(huì)減小,因?yàn)間中數(shù)據(jù)對(duì)象的權(quán)重是隨時(shí)間逐漸衰減的.Chen和Tu在文獻(xiàn)[8]中指出,從0時(shí)刻開始到任意時(shí)刻讀取到的數(shù)據(jù)流總權(quán)重不超過1/(1-λ-a).假設(shè)網(wǎng)格數(shù)量為N,那么每個(gè)網(wǎng)格權(quán)重為1/[N(1-λ-a)].

不同的網(wǎng)格包含的數(shù)據(jù)量不同,因此,不同的網(wǎng)格具有不同的權(quán)重.基于網(wǎng)格權(quán)重的大小,Chen和 Tu[8]還將網(wǎng)格分為稀疏網(wǎng)格和稠密網(wǎng)格:如果t時(shí)刻網(wǎng)格g的權(quán)重W(g,t)滿足W(g,t)≤Cs/[N(1-λ-a)],則稱網(wǎng)格g為稀疏網(wǎng)格;如果W(g,t)≥Cd/[N(1-λ-a)],則稱網(wǎng)格g為稠密網(wǎng)格,其中,Cd(Cd＞1),(0＜Cs＜1)是閾值參數(shù).

2.2 網(wǎng)格耦合

許多基于網(wǎng)格的聚類算法在聚類過程中獨(dú)立處理網(wǎng)格,忽略了網(wǎng)格之間的相互影響,從而影響了聚類質(zhì)量.如圖1所示,圖中顯示了截止到tp時(shí)刻數(shù)據(jù)流映射到網(wǎng)格1～網(wǎng)格6的數(shù)據(jù)分布.網(wǎng)格6由于數(shù)據(jù)量太少,可能會(huì)被當(dāng)成噪聲網(wǎng)格,使得網(wǎng)格6中的數(shù)據(jù)不被聚類;網(wǎng)格3和網(wǎng)格4是相鄰的非稀疏網(wǎng)格,因此網(wǎng)格3和網(wǎng)格4中的數(shù)據(jù)會(huì)聚在一個(gè)簇中.實(shí)際上,網(wǎng)格6中的數(shù)據(jù)應(yīng)該與網(wǎng)格4和網(wǎng)格5中的點(diǎn)聚成一簇,網(wǎng)格3與網(wǎng)格4中的點(diǎn)應(yīng)該分屬不同的簇.針對(duì)這個(gè)問題,本文提出了一種基于網(wǎng)格耦合的數(shù)據(jù)流聚類方法.該方法在聚類過程中不再獨(dú)立處理網(wǎng)格,而是基于網(wǎng)格內(nèi)數(shù)據(jù)對(duì)象的分布狀態(tài)考慮網(wǎng)格之間權(quán)重的相互影響,即,一個(gè)網(wǎng)格權(quán)重的變化會(huì)使相鄰網(wǎng)格的權(quán)重增加或減小,比如圖1中網(wǎng)格4權(quán)重的增大使得網(wǎng)格6權(quán)重增加、網(wǎng)格3權(quán)重減少,從而避免獨(dú)立處理網(wǎng)格帶來的問題.

Fig.1 Data distribution within the grid as the timetp圖1 截止到tp時(shí)刻網(wǎng)格內(nèi)的數(shù)據(jù)分布

為了表示網(wǎng)格內(nèi)數(shù)據(jù)對(duì)象的分布狀態(tài),本文將網(wǎng)格內(nèi)帶權(quán)數(shù)據(jù)對(duì)象的中心定義為網(wǎng)格質(zhì)心.由于數(shù)據(jù)流是動(dòng)態(tài)的,因此網(wǎng)格質(zhì)心也會(huì)隨時(shí)間而變化.如果數(shù)據(jù)對(duì)象在網(wǎng)格內(nèi)均勻分布,則網(wǎng)格質(zhì)心位于網(wǎng)格中心;如果數(shù)據(jù)對(duì)象在網(wǎng)格內(nèi)分布不均勻,則網(wǎng)格質(zhì)心不在網(wǎng)格中心.如圖1中,網(wǎng)格3和網(wǎng)格4的網(wǎng)格質(zhì)心就不在網(wǎng)格中心.

定義2.3(網(wǎng)格質(zhì)心).設(shè)E(g,t)為截止到t時(shí)刻映射在網(wǎng)格g中的數(shù)據(jù)對(duì)象集合,W(X,t)代表數(shù)據(jù)對(duì)象X在t時(shí)刻的權(quán)重,則網(wǎng)格g在t時(shí)刻的質(zhì)心C(g,t)定義為網(wǎng)格g內(nèi)帶權(quán)數(shù)據(jù)對(duì)象的加權(quán)平均,即:

為了快速計(jì)算網(wǎng)格質(zhì)心,定理2.1給出了基于tp時(shí)刻的網(wǎng)格質(zhì)心C(g,tp)來計(jì)算t時(shí)刻網(wǎng)格質(zhì)心C(g,t)的更新方式.

定理2.1.假設(shè)網(wǎng)格g在tp時(shí)刻的質(zhì)心是C(g,tp),t時(shí)刻有新數(shù)據(jù)對(duì)象X′映射進(jìn)來,則t時(shí)刻網(wǎng)格g的質(zhì)心C(g,t)的計(jì)算公式為

其中,k是一個(gè)質(zhì)心調(diào)節(jié)參數(shù):如果0＜k＜1,則表示降低歷史數(shù)據(jù)權(quán)重對(duì)網(wǎng)格質(zhì)心的影響,提高網(wǎng)格質(zhì)心的實(shí)時(shí)性;如果k＞1,則表示增加歷史數(shù)據(jù)權(quán)重對(duì)網(wǎng)格質(zhì)心的影響,降低網(wǎng)格質(zhì)心的實(shí)時(shí)性.

證明:假設(shè)每一時(shí)刻數(shù)據(jù)流中只有一個(gè)數(shù)據(jù)對(duì)象到達(dá),網(wǎng)格g在tp時(shí)刻的質(zhì)心是C(g,tp).根據(jù)網(wǎng)格質(zhì)心定義公式(3)、網(wǎng)格權(quán)重公式(2)可以得出t時(shí)刻質(zhì)心公式:

因?yàn)閠時(shí)刻網(wǎng)格權(quán)重可以根據(jù)tp時(shí)刻網(wǎng)格權(quán)重迭代得出,所以通過公式(5)可推得公式(6):

另一方面,根據(jù)將tp時(shí)刻的質(zhì)心公式可得到公式(7):

將公式(7)帶入公式(6),可得到網(wǎng)格質(zhì)心迭代公式(8):

網(wǎng)格質(zhì)心表示網(wǎng)格內(nèi)數(shù)據(jù)的分布狀態(tài),為了度量?jī)蓚€(gè)網(wǎng)格內(nèi)數(shù)據(jù)分布的距離,本文定義了網(wǎng)絡(luò)間的質(zhì)心距離. □

定義2.4(網(wǎng)格質(zhì)心距離).設(shè)C(gi,t)={ci1,ci2,…,cid}和C(gj,t)={cj1,cj2,…,cjd}分別是兩個(gè)相鄰網(wǎng)格gi和gj的質(zhì)心,則在t時(shí)刻,這兩個(gè)相鄰網(wǎng)格質(zhì)心間的距離disC(gi,gj)定義為

為了減少計(jì)算量,本文只考慮相鄰網(wǎng)格間的耦合,因此,兩個(gè)不相鄰網(wǎng)格間的質(zhì)心距離定義為無(wú)窮大.

網(wǎng)格之間的相互影響與網(wǎng)格質(zhì)心之間的距離有關(guān):距離越近,影響越大;反之越小.實(shí)際上,質(zhì)心距離越近的網(wǎng)格,網(wǎng)格內(nèi)的數(shù)據(jù)點(diǎn)屬于同一個(gè)簇的可能性越大;而距離較遠(yuǎn)的網(wǎng)格內(nèi)的數(shù)據(jù)點(diǎn)屬于不同簇的可能性大.屬于同簇的網(wǎng)格,其權(quán)重的變化趨勢(shì)應(yīng)該相同;屬于異簇的網(wǎng)格,其權(quán)重的變化趨勢(shì)應(yīng)該相反.為了區(qū)分網(wǎng)格之間的不同影響,本文定義了正影響和負(fù)影響的概念.設(shè)Dislen為影響區(qū)域閾值,如果disC(gi,gj)≤Dislen,則網(wǎng)格gi對(duì)網(wǎng)格gj產(chǎn)生正影響;反之產(chǎn)生負(fù)影響.正影響表明gi權(quán)重增加,gj權(quán)重隨之增大;負(fù)影響則表示gi權(quán)重增加,gj權(quán)重隨之減小.影響系數(shù)定量度量了網(wǎng)格間的影響強(qiáng)度.

定義2.5(影響系數(shù)(Ideg)).網(wǎng)格gi和gj之間的影響系數(shù)定義如下:

其中,MaxCdis為相鄰網(wǎng)格質(zhì)心距離的最大值(體對(duì)角上的兩點(diǎn)間距離).假設(shè)網(wǎng)格空間為d維,網(wǎng)格邊長(zhǎng)為len,則MaxCdis定義為

如果網(wǎng)格gi對(duì)網(wǎng)格gj產(chǎn)生正影響,則Ideg(gi,gj)＞0;反之,Ideg(gi,gj)＜0.如圖2中,兩個(gè)星形符號(hào)分別表示網(wǎng)格3和網(wǎng)格6的質(zhì)心.假設(shè)時(shí)刻t有一個(gè)數(shù)據(jù)映射到網(wǎng)格4中,則以網(wǎng)格4的質(zhì)心為圓心、Dislen為半徑,生成一個(gè)實(shí)線圓,圓內(nèi)區(qū)域是網(wǎng)格4的正影響區(qū)域,圓外是網(wǎng)格4的負(fù)影響區(qū)域.由圖可見:網(wǎng)格4權(quán)重的變化對(duì)網(wǎng)格6產(chǎn)生正影響,對(duì)網(wǎng)格3產(chǎn)生負(fù)影響,使網(wǎng)格6的權(quán)重有所增加,網(wǎng)格3的權(quán)重有所減少.網(wǎng)格間的耦合增大了網(wǎng)格4和網(wǎng)格6中數(shù)據(jù)聚到同一個(gè)簇的可能,減小了網(wǎng)格4和網(wǎng)格3中數(shù)據(jù)聚到同一個(gè)簇的可能,克服了獨(dú)立處理網(wǎng)格帶來的問題.

在基于網(wǎng)格的聚類算法中,每個(gè)簇都是由一組相連的網(wǎng)格組成,每個(gè)簇被稀疏網(wǎng)格包圍.通常,處于簇中心的網(wǎng)格,其權(quán)重與相鄰網(wǎng)格的權(quán)重之和較大;而位于簇邊緣的網(wǎng)格,其權(quán)重與相鄰網(wǎng)格的權(quán)重之和較小.為了區(qū)分這兩種不同的狀態(tài),本文定義了核心網(wǎng)格的概念,并將簇定義為密度相連的網(wǎng)格內(nèi)的數(shù)據(jù)集合.

定義2.6(核心網(wǎng)格).設(shè)L(g,t)是網(wǎng)格g在Dislen影響范圍內(nèi)的網(wǎng)格集合,如果L(g,t)內(nèi)所有網(wǎng)格的權(quán)重之和大于閾值,即,則稱網(wǎng)格g為核心網(wǎng)格.所有核心網(wǎng)格的集合表示為L(zhǎng)D.由于核心網(wǎng)格很可能為簇中心網(wǎng)格,其權(quán)重與相鄰網(wǎng)格權(quán)重之和大于簇邊緣上的稀疏網(wǎng)格及其相鄰網(wǎng)格權(quán)重之和,所以閾值ε≥Cd/[N(1-λ-a)].

定義2.7(密度相連).設(shè)網(wǎng)格gi是一個(gè)核心網(wǎng)格,如果gj是LD中離網(wǎng)格gi質(zhì)心距離最近的網(wǎng)格,則稱網(wǎng)格gj與gi密度相連,網(wǎng)格gj中的數(shù)據(jù)點(diǎn)被分配到gi中數(shù)據(jù)點(diǎn)所屬的簇.核心網(wǎng)格gi及其密度相連的網(wǎng)格內(nèi)數(shù)據(jù)對(duì)象構(gòu)成的集合稱為簇,記為Cgi.

設(shè)網(wǎng)格gi和gj密度相連,gk和gl密度相連,如果disC(gp,gq)＜Dislen(p=i,j;q=k,l),則gi,gj,gk和gl密度相連,即gi和gj構(gòu)成的簇與gk和gl構(gòu)成的簇合并.

Fig.2 Effect of mapping data objects in grid 4 on grid 3 and grid 6圖2 網(wǎng)格4中映射數(shù)據(jù)對(duì)象對(duì)網(wǎng)格3和網(wǎng)格6的影響

3 GCStream算法

本文所提的GCStream算法也是基于在線/離線框架,如圖3所示.

Fig.3 GCStream algorithm flow chart圖3 GCStream算法流程圖

在線階段創(chuàng)建網(wǎng)格并將數(shù)據(jù)流中到達(dá)的數(shù)據(jù)對(duì)象映射到相應(yīng)網(wǎng)格中,然后根據(jù)新到達(dá)的數(shù)據(jù)對(duì)象更新核心網(wǎng)格及網(wǎng)格的權(quán)重、質(zhì)心等,并周期性檢測(cè)及刪除噪聲網(wǎng)格.離線階段主要基于更新的核心網(wǎng)格和網(wǎng)格的質(zhì)心尋找密度相連的網(wǎng)格,從而完成聚類,追蹤簇的變化.每個(gè)步驟詳細(xì)介紹如下.

· 在線階段

(1) 將數(shù)據(jù)映射到網(wǎng)格.

首先初始化一個(gè)紅黑樹用以存儲(chǔ)網(wǎng)格列表,而每個(gè)網(wǎng)格由一個(gè)多元組(key,W,cvec,status,clusterid,tg,Ngkeys)組成.其中,key是由網(wǎng)格的位置信息生成的哈希碼,W為網(wǎng)格的權(quán)重,cvec為網(wǎng)格的質(zhì)心向量,status代表網(wǎng)格的稠密狀態(tài),clusterid為該網(wǎng)格所屬的簇號(hào),tg記錄的為該網(wǎng)格上次的更新的時(shí)刻,Ngkeys為該網(wǎng)格的鄰居列表.當(dāng)數(shù)據(jù)對(duì)象到來時(shí),根據(jù)該數(shù)據(jù)對(duì)象的屬性向量為其尋找對(duì)應(yīng)的網(wǎng)格進(jìn)行映射.如果該網(wǎng)格在網(wǎng)格列表中不存在,則創(chuàng)建一個(gè)新的網(wǎng)格單元.

(2) 根據(jù)網(wǎng)格耦合思想更新網(wǎng)格.

當(dāng)數(shù)據(jù)對(duì)象映射到網(wǎng)格之后,需要更新該網(wǎng)格的元組.值得注意的是,網(wǎng)格之間是相互影響的,所以本文在更新當(dāng)前網(wǎng)格時(shí),還通過網(wǎng)格質(zhì)心距離捕捉該網(wǎng)格與周圍網(wǎng)格的關(guān)系,以此來確定周圍網(wǎng)格的更新.

(3) 更新核心網(wǎng)格.

當(dāng)網(wǎng)格權(quán)重發(fā)生變化時(shí),需要判斷該網(wǎng)格是否滿足核心網(wǎng)格條件.如果滿足,則將該網(wǎng)格替換進(jìn)核心網(wǎng)格列表中.

(4) 周期性檢測(cè)及刪除噪聲網(wǎng)格.

噪聲網(wǎng)格為一些由噪聲生成的網(wǎng)格或一些由簇衰退形成的零星網(wǎng)格.在數(shù)據(jù)流不斷到達(dá)的過程中,這些網(wǎng)格不斷累積,會(huì)造成內(nèi)存空間的浪費(fèi),所以需要定期地檢測(cè)刪除這些噪聲網(wǎng)格.

本文根據(jù)噪聲網(wǎng)格比較稀疏并不可能變?yōu)槌砻芫W(wǎng)格的特性,將經(jīng)過tu時(shí)間段還沒由稀疏轉(zhuǎn)為稠密的網(wǎng)格定義為噪聲網(wǎng)格.定理3.1給出了一個(gè)稀疏網(wǎng)格轉(zhuǎn)換為稠密網(wǎng)格所需時(shí)間的計(jì)算公式.

定理3.1.設(shè)網(wǎng)格g是一個(gè)稀疏網(wǎng)格,tu是g轉(zhuǎn)換為稠密網(wǎng)格所需的時(shí)間,則:

證明:設(shè)網(wǎng)格g在t1時(shí)刻為稀疏網(wǎng)格,則:

設(shè)網(wǎng)格g在t2(t2＞t1)時(shí)刻轉(zhuǎn)為稠密網(wǎng)格,則:

如果要求網(wǎng)格g能在最短的時(shí)間內(nèi)由稀疏網(wǎng)格轉(zhuǎn)為稠密網(wǎng)格,則需要時(shí)間段tu(tu=t2-t1)內(nèi)到達(dá)的數(shù)據(jù)對(duì)象均映射在網(wǎng)格g內(nèi),因此,

其中,X∈(E(g,t2)-E(g,t1))表示時(shí)間段tu映射到網(wǎng)格g的數(shù)據(jù)對(duì)象集合.

由數(shù)據(jù)權(quán)重公式可得時(shí)間段tu映射到網(wǎng)格g的數(shù)據(jù)權(quán)重為.可以看到,該組數(shù)據(jù)權(quán)重滿足等比公式,所以不等式(15)可變形為

聯(lián)立不等式(14)和不等式(16)可以得到:

(5) 檢測(cè)核心網(wǎng)格是否變動(dòng).

隨著時(shí)間的推移,網(wǎng)格中歷史數(shù)據(jù)的權(quán)重逐漸衰減,新映射進(jìn)來的數(shù)據(jù)具有較大權(quán)重從而導(dǎo)致網(wǎng)格權(quán)重發(fā)生變化,進(jìn)而引起網(wǎng)格類型發(fā)生變化:稠密網(wǎng)格與稀疏網(wǎng)格互換、核心網(wǎng)格與非核心網(wǎng)格互換.這些變化使得數(shù)據(jù)流中的簇也是不斷變化的,有的簇會(huì)隨著時(shí)間的流逝慢慢消失,有的簇會(huì)隨著新數(shù)據(jù)點(diǎn)的映射而慢慢擴(kuò)大.所以,本文根據(jù)核心網(wǎng)格是否變動(dòng)來調(diào)用離線組件.

在線階段的 5個(gè)步驟主要用于映射數(shù)據(jù)流以及收集數(shù)據(jù)流的概要信息.值得注意的是:在高維空間中數(shù)據(jù)是比較稀疏的,這有可能劃分出許多空網(wǎng)格或數(shù)據(jù)對(duì)象數(shù)較少的網(wǎng)格.針對(duì)這個(gè)問題,本文在線階段在生成網(wǎng)格時(shí),根據(jù)當(dāng)前到達(dá)數(shù)據(jù)樣本的屬性向量動(dòng)態(tài)生成網(wǎng)格.即當(dāng)數(shù)據(jù)流映射進(jìn)來時(shí),查找網(wǎng)格列表中是否有與其對(duì)應(yīng)的網(wǎng)格:如果有,則將該數(shù)據(jù)對(duì)象映射到該網(wǎng)格并更新該網(wǎng)格的元組;否則,為該數(shù)據(jù)對(duì)象創(chuàng)建一個(gè)新網(wǎng)格單元.除此之外,在線階段的周期性檢測(cè)及刪除噪聲網(wǎng)格等步驟則能定期刪除一些數(shù)據(jù)對(duì)象數(shù)較小的網(wǎng)格.通過以上兩個(gè)策略,使得 GCStream 算法能夠不生成空網(wǎng)格以及減少稀疏網(wǎng)格的數(shù)量,既降低了內(nèi)存占用,也提高了算法的效率.

· 離線階段

(1) 尋找與核心網(wǎng)格密度相連的網(wǎng)格生成簇.該階段通過為每個(gè)核心網(wǎng)格尋找與其密度相連的網(wǎng)格來將網(wǎng)格進(jìn)行劃分,形成以核心網(wǎng)格為中心的簇;

(2) 合并簇.上述生成的以核心網(wǎng)格為中心的簇可能存在兩個(gè)網(wǎng)格數(shù)據(jù)分布接近,使得兩個(gè)簇相連,所以進(jìn)一步判斷是否存在能夠合并的簇是有必要的.

基于核心網(wǎng)格的離線聚類時(shí)間復(fù)雜度分析.假設(shè)某一時(shí)刻網(wǎng)格列表中的總網(wǎng)格數(shù)為n,核心網(wǎng)格集合LD的大小為Ncg.首先執(zhí)行算法2的第3步～第5步,生成簇.該過程將剩余網(wǎng)格分配給核心網(wǎng)格,所需要的時(shí)間復(fù)雜度為O(0.5×Ncg(n-Ncg));然后執(zhí)行算法2的第6步～第10步,合并簇.在合并簇的時(shí)候,需要遍歷每個(gè)網(wǎng)格的鄰居.假設(shè)每個(gè)網(wǎng)格有Nng個(gè)鄰居網(wǎng)格,則該階段時(shí)間復(fù)雜度為O(Ncg×n).所以基于核心網(wǎng)格的離線聚類算法的時(shí)間復(fù)雜度為O(Ncg(n-Ncg)+Nng×n).

算法1.GCStream的在線階段.

輸出:網(wǎng)格列表.

步驟:

算法2.GCStream的離線階段.

輸入:網(wǎng)格列表信息;

輸出:聚類結(jié)果.

步驟:

4 實(shí)驗(yàn)評(píng)估

本節(jié)對(duì) GCStream算法適應(yīng)和捕捉數(shù)據(jù)流演變的能力、去除噪聲數(shù)據(jù)的能力、聚類質(zhì)量以及聚類效率進(jìn)行了實(shí)驗(yàn)評(píng)估.

4.1 實(shí)驗(yàn)準(zhǔn)備

本文實(shí)驗(yàn)的操作系統(tǒng)為64位Windows 7旗艦版,硬件環(huán)境為Intel(R) Core(TM) i3-3240(3.40GHz),RAM為4GB.

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

本文實(shí)驗(yàn)總共用到5個(gè)數(shù)據(jù)集:兩個(gè)人工數(shù)據(jù)集(MTD和MOAD)和3個(gè)UCI真實(shí)數(shù)據(jù)集(KDDCUP99[17],CoverType[18]和PAMAP2[19]).其中,人工數(shù)據(jù)集MTD使用MATLAB生成,包含兩個(gè)凸型簇和兩個(gè)非凸型簇并帶有10%均勻分布的噪聲.該數(shù)據(jù)集用以測(cè)試GCStream算法適應(yīng)和捕捉簇演變的能力以及去除噪聲數(shù)據(jù)的能力.MOAD使用MOA(massive online analysis)工具生成[20,21],該工具是一個(gè)處理演變數(shù)據(jù)流的框架,廣泛用于數(shù)據(jù)流挖掘工作.MOAD數(shù)據(jù)集由12 072個(gè)數(shù)據(jù)對(duì)象組成,分屬10個(gè)簇,每個(gè)數(shù)據(jù)對(duì)象包含1 000個(gè)屬性,用以測(cè)試各算法在不同維度上的效率.KDDCUP99數(shù)據(jù)集是麻省理工學(xué)院林肯實(shí)驗(yàn)室收集的網(wǎng)絡(luò)入侵檢測(cè)數(shù)據(jù)集,包含494 020條TCP連接記錄,分屬于23種不同的網(wǎng)絡(luò)連接類型.CoverType數(shù)據(jù)集是美國(guó)森林服務(wù)信息系統(tǒng)提供的數(shù)據(jù)集,包含581 012條記錄,每條記錄由一塊30×30平方英尺上的 54個(gè)地理數(shù)據(jù)組成.PAMAP2數(shù)據(jù)集是Reiss和Strickere收集的身體活動(dòng)監(jiān)測(cè)數(shù)據(jù),由9名佩戴3個(gè)慣性測(cè)量單位和心率監(jiān)測(cè)儀的受試者進(jìn)行18項(xiàng)不同的身體活動(dòng)(如步行、騎自行車、踢足球等)產(chǎn)生的數(shù)據(jù)組成.本文通過將上述數(shù)據(jù)集中數(shù)據(jù)的輸入順序作為數(shù)據(jù)流的傳輸順序,把所有數(shù)據(jù)集轉(zhuǎn)為流.每個(gè)數(shù)據(jù)集的大小、維度、簇?cái)?shù)以及簇之間的最小距離見表1.

Table 1 Dataset feature summary表1 數(shù)據(jù)集特征匯總

· 對(duì)比算法

本文使用 D-Stream[8],DenStream[16],DBSTREAM[12],GCStream-UC作為本文的對(duì)比算法.其中,GCStream-UC為在線階段不考慮網(wǎng)格耦合的GCStream算法,即GCStream-UC算法只是更新映射了數(shù)據(jù)對(duì)象的網(wǎng)格的權(quán)重,相鄰網(wǎng)格的權(quán)重不受新映射了數(shù)據(jù)對(duì)象的網(wǎng)格權(quán)重變化的影響.

· 聚類質(zhì)量評(píng)估方法

本文中采用的聚類質(zhì)量評(píng)價(jià)方法為Purity和CMM[22].Purity定義如下:

其中,K代表簇的數(shù)量,Ci代表簇i中數(shù)據(jù)對(duì)象總數(shù),代表簇i中被正確劃分的數(shù)據(jù)對(duì)象數(shù)目.Purity度量了各個(gè)簇中正確聚類的對(duì)象比例.

CMM(clustering mapping measure)是一種考慮了數(shù)據(jù)流中數(shù)據(jù)對(duì)象的權(quán)重(新鮮度)并可以反映簇生成、移動(dòng)、分裂過程固有錯(cuò)誤(比如簇的移動(dòng)導(dǎo)致部分?jǐn)?shù)據(jù)對(duì)象丟失;簇的合并和分裂產(chǎn)生重疊的簇,導(dǎo)致一些數(shù)據(jù)對(duì)象被錯(cuò)誤劃分)的評(píng)價(jià)指標(biāo).此外,CMM還能對(duì)數(shù)據(jù)流中的噪聲情況進(jìn)行度量.CMM定義如下:

其中,Cl={Cl1,…,Cll}是真實(shí)簇集合,C={C1,…,Ck,Cφ}是聚類結(jié)果,W(o)是數(shù)據(jù)對(duì)象o的權(quán)重,pen(o,C)是聚類過程中對(duì)遺漏數(shù)據(jù)對(duì)象、錯(cuò)分及噪聲的懲罰,con(o,Cl(o))度量了數(shù)據(jù)對(duì)象o與其所屬的簇Cl(o)之間的點(diǎn)連通度,F是錯(cuò)誤劃分的數(shù)據(jù)對(duì)象集合.CMM∈[0,1],CMM值越大,代表聚類質(zhì)量越好.

4.2 算法參數(shù)選擇

在進(jìn)行對(duì)比實(shí)驗(yàn)之前,需要統(tǒng)一環(huán)境變量以及對(duì)算法參數(shù)進(jìn)行調(diào)整.本文默認(rèn)設(shè)置各數(shù)據(jù)流數(shù)據(jù)點(diǎn)到達(dá)速率為 1000pt/s,各算法中數(shù)據(jù)點(diǎn)的衰減速度一致.在 GCStream 中,設(shè)置λ=1.002,a=1;在 D-Stream 算法中,設(shè)置λ=0.998,a=-1;在 DenStream 和 DBSTREAM 中,設(shè)置λ=2,a=0.0028,使得權(quán)重衰減函數(shù)f=λ-a=0.998.對(duì)比算法的其他參數(shù)設(shè)置需參考其原始文獻(xiàn).由于GCStream算法主要受質(zhì)心調(diào)節(jié)參數(shù)k,Dislen以及Ncg的影響,所以本節(jié)將通過實(shí)驗(yàn)探索這3個(gè)參數(shù)的選擇.

4.2.1 質(zhì)心調(diào)節(jié)參數(shù)k

質(zhì)心調(diào)節(jié)參數(shù)k決定著歷史數(shù)據(jù)權(quán)重對(duì)網(wǎng)格質(zhì)心的影響程度,是網(wǎng)格質(zhì)心實(shí)時(shí)性的調(diào)節(jié)因子.0＜k＜1表示提高網(wǎng)格質(zhì)心的實(shí)時(shí)性,k＞1表示降低網(wǎng)格質(zhì)心的實(shí)時(shí)性,k=1代表不考慮網(wǎng)格質(zhì)心實(shí)時(shí)性,所以本文分別選擇小于1、等于1以及大于1的k值進(jìn)行對(duì)比實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果如圖4所示:在KDDCUP99數(shù)據(jù)流上,k=1時(shí)效果最好,于是本文在此基礎(chǔ)上進(jìn)一步縮小參數(shù)k的調(diào)整幅度,最終確定了k=0.96;在CoverType數(shù)據(jù)流上,k=0.8和k=1時(shí)結(jié)果較好,本文在此范圍內(nèi)繼續(xù)微調(diào)參數(shù)k,最終確定了k=0.97;在PAMAP2數(shù)據(jù)流上,聚類結(jié)果相差不大,于是本文最終選擇了k=0.87.

Fig.4 CMM and Purity comparison of GCStream algorithm under differentk圖4 GCStream算法在不同k值下的CMM和Purity對(duì)比

4.2.2 距離閾值Dislen

距離閾值Dislen為影響區(qū)域閾值,直接影響著網(wǎng)格之間的耦合以及簇的合并.本節(jié)實(shí)驗(yàn)通過對(duì)比GCStream算法在不同Dislen值下的CMM和Purity來探索Dislen的取值,實(shí)驗(yàn)結(jié)果如圖5所示.

在KDDCUP99數(shù)據(jù)流上,當(dāng)Dislen=70時(shí),聚類結(jié)果的CMM值明顯好于另外兩個(gè),并且Purity值也是比較高的,所以本文選擇在Dislen=70的基礎(chǔ)進(jìn)一步微調(diào)參數(shù).在CoverType數(shù)據(jù)流上,Dislen=80和Dislen=140時(shí)聚類結(jié)果的CMM值高于Dislen=300的CMM值.進(jìn)一步觀察發(fā)現(xiàn),Dislen=140時(shí)聚類結(jié)果的Purity值高于Dislen=80時(shí)的Purity值,所以本文選擇在Dislen=140附近繼續(xù)尋找最優(yōu)值.在PAMAP2數(shù)據(jù)流上,3個(gè)參數(shù)值的聚類結(jié)果相近,所以本文便選擇了Dislen=5為本文實(shí)驗(yàn)的參數(shù)值.

Fig.5 CMM and Purity comparison of GCStream algorithm under different Dislen圖5 GCStream算法在不同Dislen值下的CMM和Purity對(duì)比

4.2.3 核心網(wǎng)格集合LD大小Ncg

核心網(wǎng)格集合由大于閾值ε的網(wǎng)格組成.本節(jié)實(shí)驗(yàn)選用不同的Ncg值進(jìn)行聚類結(jié)果的CMM和Purity對(duì)比,實(shí)驗(yàn)結(jié)果如圖6所示.在KDDCUP99數(shù)據(jù)流上,Ncg=6,8時(shí)聚類結(jié)果的CMM值較高.進(jìn)一步對(duì)比這兩個(gè)不同Ncg值的聚類結(jié)果評(píng)價(jià)指標(biāo)值發(fā)現(xiàn),他們的CMM值相差不大,但是Ncg=6時(shí),聚類結(jié)果的Purity值要高些,所以本文在KDDCUP99數(shù)據(jù)集上設(shè)置Ncg=6;在CoverType數(shù)據(jù)流上,當(dāng)Ncg＞12時(shí),算法聚類結(jié)果的 CMM指標(biāo)值較小,當(dāng)Ncg≤12時(shí),聚類結(jié)果的兩個(gè)評(píng)價(jià)指標(biāo)相差不大,所以本文在CoverType數(shù)據(jù)流上設(shè)置Ncg=12;在PAMAP2數(shù)據(jù)流上,不同Ncg值得到的聚類結(jié)果CMM值相差不大,但是當(dāng)Ncg=12時(shí),Purity值要高些,所以本文在PAMAP2數(shù)據(jù)流上設(shè)置Ncg=12.

Fig.6 CMM and Purity comparison of GCStream algorithm under differentNcg圖6 GCStream算法在不同Ncg值下的CMM和Purity對(duì)比

綜上,本文后續(xù)實(shí)驗(yàn)在3個(gè)UCI真實(shí)數(shù)據(jù)集上,質(zhì)心調(diào)節(jié)參數(shù)k分別設(shè)置為0.96,0.97,0.87;網(wǎng)格質(zhì)心距離閾值Dislen分別設(shè)置為64,144,5;核心網(wǎng)格集合LD大小Ncg分別設(shè)置為6,12,12.

4.2.4 數(shù)據(jù)集處理

在實(shí)驗(yàn)進(jìn)行之前,有時(shí)需要對(duì)數(shù)據(jù)集進(jìn)行標(biāo)準(zhǔn)化處理.因?yàn)閷?shí)驗(yàn)數(shù)據(jù)的不同維度代表不同含義,有時(shí)數(shù)據(jù)跨度差別非常大.這就需要對(duì)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理以消除不同維度間的量綱差異,使數(shù)據(jù)具有可比性.但如果對(duì)數(shù)據(jù)跨度不大的數(shù)據(jù)集也進(jìn)行處理,則可能會(huì)丟失數(shù)據(jù)集的真實(shí)性和原始性.為此,本文在3個(gè)UCI真實(shí)數(shù)據(jù)集(標(biāo)準(zhǔn)化和非標(biāo)準(zhǔn)化)上測(cè)試了GCStream算法和3種對(duì)比算法的聚類Purity值來決定是否對(duì)數(shù)據(jù)集進(jìn)行標(biāo)準(zhǔn)化處理.實(shí)驗(yàn)結(jié)果見表2,可以看到各算法在 3個(gè)數(shù)據(jù)集標(biāo)準(zhǔn)化和非標(biāo)準(zhǔn)化下的聚類Purity值差異很小,所以本文選擇不對(duì)數(shù)據(jù)集進(jìn)行標(biāo)準(zhǔn)化處理.

Table 2 Purity comparison under standardized and non-standardized data sets表2 標(biāo)準(zhǔn)化和非標(biāo)準(zhǔn)化數(shù)據(jù)集下的Purity對(duì)比

4.3 聚類質(zhì)量評(píng)價(jià)

4.3.1 UCI數(shù)據(jù)集的聚類結(jié)果

為了驗(yàn)證GCStream算法的聚類質(zhì)量,本文在3個(gè)UCI數(shù)據(jù)集上運(yùn)行了GCStream算法、GCStream-UC算法、D-Stream算法、DenStream算法和DBSTREAM算法,比較了這些算法的Purity和CMM指標(biāo).實(shí)驗(yàn)中,各個(gè)算法每隔25s對(duì)流數(shù)據(jù)進(jìn)行一次聚類,圖7比較了各種算法的平均Purity.

Fig.7 Purity comparison on UCI datasets圖7 各算法在UCI數(shù)據(jù)集上的Purity對(duì)比

由圖7可見,GCStream算法在3個(gè)數(shù)據(jù)流上的平均Purity值均大于其他算法的平均Purity值.D-Stream算法在PAMAP2數(shù)據(jù)流上的Purity值較小,這是因?yàn)镻AMAP2數(shù)據(jù)流中同一時(shí)刻內(nèi)生成的簇較多并且維度較高,D-Stream算法對(duì)這類數(shù)據(jù)流比較敏感.圖8展示了各種算法在每次聚類時(shí)得到的CMM值,圖9比較了各種算法的平均CMM.由圖8可見:大多數(shù)時(shí)刻,GCStream算法的CMM值都是優(yōu)于對(duì)比算法的,并且比較穩(wěn)定.值得注意的是:GCStream算法的CMM值在3個(gè)數(shù)據(jù)流上的多個(gè)時(shí)刻均高于GCStream-UC,說明基于網(wǎng)格耦合思想更新網(wǎng)格結(jié)構(gòu)能夠提高算法聚類質(zhì)量.圖9表明,在3個(gè)數(shù)據(jù)集上,GCStream算法的CMM均值均大于其他算法的平均CMM.

Fig.8 CMM comparison of algorithms on UCI datasets圖8 各算法在UCI數(shù)據(jù)集上的CMM對(duì)比

Fig.9 CMM mean comparison on UCI datasets圖9 UCI數(shù)據(jù)集上的CMM均值對(duì)比

4.3.2 GCStream算法在不同數(shù)據(jù)流速度下的聚類質(zhì)量

能夠快速聚類數(shù)據(jù)流,是數(shù)據(jù)流聚類算法的一個(gè)重要特性.因此,本文在 KDDCUP99數(shù)據(jù)流上以不同的數(shù)據(jù)流速度(1k/s,2k/s,7k/s)驗(yàn)證本文算法聚類質(zhì)量.聚類結(jié)果如圖10所示.首先,本文算法能夠在這3種速度下處理完數(shù)據(jù)流,說明 GCStream算法有能力處理速度較快的數(shù)據(jù)流.然后,分析聚類質(zhì)量評(píng)價(jià)指標(biāo)結(jié)果可以得出,隨著數(shù)據(jù)流速度的上升,CMM指標(biāo)值有所下降,但是下降幅度并不大;Purity指標(biāo)值下降幅度比CMM值略大,但仍保持在較高的水平.說明GCStream算法在聚類高速數(shù)據(jù)流時(shí)依然可以保存較高的聚類質(zhì)量.

Fig.10 Cluster quality comparison under different stream rate圖10 不同數(shù)據(jù)流速度下的聚類質(zhì)量對(duì)比

4.3.3 GCStream算法在不同網(wǎng)格邊長(zhǎng)下的聚類質(zhì)量

本節(jié)實(shí)驗(yàn)主要測(cè)試不同網(wǎng)格邊長(zhǎng)對(duì)聚類質(zhì)量的影響.以KDDCUP99為測(cè)試數(shù)據(jù)流,我們分別設(shè)置網(wǎng)格邊長(zhǎng)len=40,100,120,160,其中,len=100為本文整理數(shù)據(jù)集時(shí)發(fā)現(xiàn)的KDDCUP99數(shù)據(jù)集中簇之間的最小距離.聚類結(jié)果如圖11所示.從圖11可以看出,當(dāng)網(wǎng)格邊長(zhǎng)大于100時(shí),聚類結(jié)果的CMM值和Purity值隨著網(wǎng)格邊長(zhǎng)的增加均有明顯的下降.當(dāng)網(wǎng)格邊長(zhǎng)小于 100時(shí),聚類質(zhì)量總體相對(duì)穩(wěn)定.實(shí)驗(yàn)結(jié)果說明:本文實(shí)驗(yàn)設(shè)置的網(wǎng)格邊長(zhǎng)len=100是比較準(zhǔn)確的,并且GCStream算法聚類質(zhì)量隨著網(wǎng)格邊長(zhǎng)的增加而有所下降.

Fig.11 Cluster quality comparison under different grid sides圖11 不同網(wǎng)格邊長(zhǎng)下的聚類質(zhì)量對(duì)比

4.3.4 GCStream算法捕捉簇的演變能力

數(shù)據(jù)聚類算法的一個(gè)重要特性是能夠適應(yīng)和捕捉簇的演變.為了驗(yàn)證GCStream算法的這兩個(gè)特性,本文在人工數(shù)據(jù)集 MTD上對(duì) GCStream 算法進(jìn)行了評(píng)估.在這個(gè)測(cè)試中,本文設(shè)置數(shù)據(jù)流到達(dá)速度為 1000pt/s,整個(gè)MTD數(shù)據(jù)流在116s內(nèi)處理完.該數(shù)據(jù)集的分布如圖12所示.圖12(a)～圖12(c)分別顯示了MTD數(shù)據(jù)集中簇的生成順序.其中,簇1和簇2中的數(shù)據(jù)是交叉分布的,在同一時(shí)刻,既有簇1中的數(shù)據(jù)到達(dá)也有簇2中的數(shù)據(jù)到達(dá),所以簇1和簇2能夠同時(shí)生成.圖13中顯示了GCStream算法處理下的MTD數(shù)據(jù)分布.圖13(a)～圖13(d)分別顯示了在t=5,t=54,t=84,t=116時(shí)刻生成的聚類結(jié)果.圖中深顏色的區(qū)域代表當(dāng)前時(shí)刻的生成的簇,淺藍(lán)色的區(qū)域代表即將消失掉的簇.可以看出,GCStream能夠發(fā)現(xiàn)4個(gè)不同形狀的簇并且不受噪聲影響.圖14顯示了MTD數(shù)據(jù)流中簇的演變時(shí)刻.不同顏色的線條表示不同的簇,線條的長(zhǎng)度表示簇存在的時(shí)間段.可以看到,簇1和簇2在初始時(shí)刻產(chǎn)生,在 55時(shí)刻消失;簇 3在 54時(shí)刻產(chǎn)生,在 85時(shí)刻消失;簇 4在 84時(shí)刻產(chǎn)生.除此之外,本文測(cè)得GCStream算法在人工數(shù)據(jù)集MTD的上的Purity均值為0.983,CMM均值為1.說明GCStream算法具有較高的聚類質(zhì)量.

Fig.12 MTD data distribution圖12 MTD數(shù)據(jù)分布

Fig.13 Data distribution of MTD data set changes with time圖13 MTD數(shù)據(jù)集的數(shù)據(jù)分布隨時(shí)間的變化

Fig.14 Evolution of clusters in MTD datasets圖14 MTD數(shù)據(jù)集中簇的演變

4.4 聚類效率評(píng)價(jià)

實(shí)時(shí)更新聚類結(jié)果對(duì)于數(shù)據(jù)流聚類算法至關(guān)重要.本文分別在多個(gè)數(shù)據(jù)集和不同維度上對(duì)各算法的效率進(jìn)行了對(duì)比.

4.4.1 GCStream算法在不同數(shù)據(jù)集上的效率

本節(jié)在3個(gè)UCI數(shù)據(jù)流上測(cè)試了GCStream與對(duì)比算法的聚類效率.設(shè)置數(shù)據(jù)流到達(dá)速率為1000pt/s,并且每隔25s顯示一次聚類結(jié)果.如果各算法能夠在25s內(nèi)處理完這段時(shí)間內(nèi)到達(dá)的數(shù)據(jù),則證明該算法能夠正常運(yùn)行;否則,說明該算法的效率不足以處理 1000pt/s的數(shù)據(jù)流.圖15顯示了 25s間隔內(nèi)不同算法的響應(yīng)時(shí)間對(duì)比.其中,DBSTREAM算法在3個(gè)數(shù)據(jù)流上只在開始時(shí)正常運(yùn)行,隨后便運(yùn)行失敗;DenStream和D-Stream算法在PAMAP2數(shù)據(jù)流上運(yùn)行失敗;而本文的GCStream算法能以1000pt/s的速度正常處理3個(gè)數(shù)據(jù)流并且所需時(shí)間最少,這說明GCStream算法效率比對(duì)比算法高.

Fig.15 Response time comparison on multiple datasets圖15 多數(shù)據(jù)集上反映時(shí)間對(duì)比

4.4.2 網(wǎng)格邊長(zhǎng)與數(shù)據(jù)維度對(duì)GCStream算法效率的影響

本文在MOAD數(shù)據(jù)流上測(cè)試GCStream與對(duì)比算法在不同維度和不同網(wǎng)格邊長(zhǎng)上的聚類效率.圖16(a)、圖16(b)分別顯示了網(wǎng)格邊長(zhǎng)len=6和len=12.4時(shí),各算法在不同維度上平均效率.在不同大小的網(wǎng)格邊長(zhǎng)上比較可看出:隨著網(wǎng)格邊長(zhǎng)的增加,GCStream,D-Stream以及DenStream算法效率都有所提升.在不同數(shù)據(jù)維度上的算法效率比較可以看到:在數(shù)據(jù)維度小于 100維時(shí),GCStream算法的效率是最高的;當(dāng)數(shù)據(jù)維度大于 100維時(shí),GCStream算法的效率也是比較高的,基本處于各算法效率的第2位.

Fig.16 Response time comparisons in multiple dimensions and different grid lengths圖16 不同網(wǎng)格邊長(zhǎng)和多維度上反映時(shí)間對(duì)比

5 結(jié)束語(yǔ)

本文針對(duì)現(xiàn)有數(shù)據(jù)流聚類算法在實(shí)時(shí)處理高速、大量的數(shù)據(jù)流時(shí)聚類效率和精度不高的問題,提出了一種基于網(wǎng)格耦合和核心網(wǎng)格的數(shù)據(jù)流聚類算法 GCStream.首先,通過網(wǎng)格耦合實(shí)現(xiàn)了對(duì)數(shù)據(jù)流更精確的匯總,提高算法聚類質(zhì)量;其次,本文根據(jù)數(shù)據(jù)流中局部權(quán)重較高的網(wǎng)格相比于局部權(quán)重較低的網(wǎng)格更可能為簇中心的特點(diǎn)引入了核心網(wǎng)格,然后以核心網(wǎng)格為簇中心生成簇,并且根據(jù)核心網(wǎng)格集合的變化來捕捉簇的演變;最后,通過真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),對(duì)比了本文所提方法與其他方法的聚類效果和聚類效率.實(shí)驗(yàn)結(jié)果表明,本文所提算法的聚類效果和聚類效率都優(yōu)于對(duì)比方法.

由于本文算法的實(shí)驗(yàn)都是在網(wǎng)格邊長(zhǎng)相等的基礎(chǔ)上進(jìn)行的,沒有考慮不同維度上的數(shù)據(jù)分布差異.所以本文的未來研究工作將著重研究根據(jù)不同維度上的數(shù)據(jù)分布采用不同的網(wǎng)格邊長(zhǎng)來使網(wǎng)格劃分更精確,以進(jìn)一步提高聚類質(zhì)量.