基于網格耦合的數據流聚類?

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

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

2(麗江師范高等專科學校,云南 麗江 674199)

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

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

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

本文的主要貢獻包括:

(1) 聚類過程中不再獨立處理網格,而是考慮了網格之間的耦合關系,從而更加準確地表達了數據之間的相關性;

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

(3) 在人工和真實數據流上進行了實驗驗證,通過實驗對比了所提算法的性能.

本文第1節介紹數據流聚類的典型算法.第2節介紹網格耦合的相關概念和定義.第3節給出GCStream的算法流程并分析算法的時間復雜度.第4節給出在合成和真實數據集上的對比實驗.最后,總結論文工作.

1 相關工作

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

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

除了聚類效率,上述算法在新數據到達而更新數據摘要時均獨立處理摘要結果,忽略了概要之間的相互影響,從而影響了算法的聚類精度.

2 網格耦合的相關概念和定義

本節首先介紹網格耦合的相關概念,然后給出網格耦合的定義.

2.1 基本概念

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

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

數據流中的數據對象有不同的到達時間,對聚類的貢獻也不同.為了區分歷史數據和新數據,許多數據流聚類算法[1,7,8]為數據流中每個數據對象分配一個帶有衰減因子的權重,使其重要性(新鮮度)隨時間推移而下降.

定義2.1(數據權重).如果數據對象X在tp時刻到達,那么X在t時刻的權重W(X,t)定義為

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

由于數據對象被映射到網絡中,因此可以基于數據對象的權重定義網格權重.

定義2.2(網格權重).設E(g,t)表示到時刻t為止,映射到網格g中的數據對象集合,則網格g在時刻t的權重定義為網格g內所有數據對象的權重之和,即:

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

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

2.2 網格耦合

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

Fig.1 Data distribution within the grid as the timetp圖1 截止到tp時刻網格內的數據分布

為了表示網格內數據對象的分布狀態,本文將網格內帶權數據對象的中心定義為網格質心.由于數據流是動態的,因此網格質心也會隨時間而變化.如果數據對象在網格內均勻分布,則網格質心位于網格中心;如果數據對象在網格內分布不均勻,則網格質心不在網格中心.如圖1中,網格3和網格4的網格質心就不在網格中心.

定義2.3(網格質心).設E(g,t)為截止到t時刻映射在網格g中的數據對象集合,W(X,t)代表數據對象X在t時刻的權重,則網格g在t時刻的質心C(g,t)定義為網格g內帶權數據對象的加權平均,即:

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

定理2.1.假設網格g在tp時刻的質心是C(g,tp),t時刻有新數據對象X′映射進來,則t時刻網格g的質心C(g,t)的計算公式為

其中,k是一個質心調節參數:如果0＜k＜1,則表示降低歷史數據權重對網格質心的影響,提高網格質心的實時性;如果k＞1,則表示增加歷史數據權重對網格質心的影響,降低網格質心的實時性.

證明:假設每一時刻數據流中只有一個數據對象到達,網格g在tp時刻的質心是C(g,tp).根據網格質心定義公式(3)、網格權重公式(2)可以得出t時刻質心公式:

因為t時刻網格權重可以根據tp時刻網格權重迭代得出,所以通過公式(5)可推得公式(6):

另一方面,根據將tp時刻的質心公式可得到公式(7):

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

網格質心表示網格內數據的分布狀態,為了度量兩個網格內數據分布的距離,本文定義了網絡間的質心距離. □

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

為了減少計算量,本文只考慮相鄰網格間的耦合,因此,兩個不相鄰網格間的質心距離定義為無窮大.

網格之間的相互影響與網格質心之間的距離有關:距離越近,影響越大;反之越小.實際上,質心距離越近的網格,網格內的數據點屬于同一個簇的可能性越大;而距離較遠的網格內的數據點屬于不同簇的可能性大.屬于同簇的網格,其權重的變化趨勢應該相同;屬于異簇的網格,其權重的變化趨勢應該相反.為了區分網格之間的不同影響,本文定義了正影響和負影響的概念.設Dislen為影響區域閾值,如果disC(gi,gj)≤Dislen,則網格gi對網格gj產生正影響;反之產生負影響.正影響表明gi權重增加,gj權重隨之增大;負影響則表示gi權重增加,gj權重隨之減小.影響系數定量度量了網格間的影響強度.

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

其中,MaxCdis為相鄰網格質心距離的最大值(體對角上的兩點間距離).假設網格空間為d維,網格邊長為len,則MaxCdis定義為

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

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

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

定義2.7(密度相連).設網格gi是一個核心網格,如果gj是LD中離網格gi質心距離最近的網格,則稱網格gj與gi密度相連,網格gj中的數據點被分配到gi中數據點所屬的簇.核心網格gi及其密度相連的網格內數據對象構成的集合稱為簇,記為Cgi.

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

Fig.2 Effect of mapping data objects in grid 4 on grid 3 and grid 6圖2 網格4中映射數據對象對網格3和網格6的影響

3 GCStream算法

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

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

在線階段創建網格并將數據流中到達的數據對象映射到相應網格中,然后根據新到達的數據對象更新核心網格及網格的權重、質心等,并周期性檢測及刪除噪聲網格.離線階段主要基于更新的核心網格和網格的質心尋找密度相連的網格,從而完成聚類,追蹤簇的變化.每個步驟詳細介紹如下.

· 在線階段

(1) 將數據映射到網格.

首先初始化一個紅黑樹用以存儲網格列表,而每個網格由一個多元組(key,W,cvec,status,clusterid,tg,Ngkeys)組成.其中,key是由網格的位置信息生成的哈希碼,W為網格的權重,cvec為網格的質心向量,status代表網格的稠密狀態,clusterid為該網格所屬的簇號,tg記錄的為該網格上次的更新的時刻,Ngkeys為該網格的鄰居列表.當數據對象到來時,根據該數據對象的屬性向量為其尋找對應的網格進行映射.如果該網格在網格列表中不存在,則創建一個新的網格單元.

(2) 根據網格耦合思想更新網格.

當數據對象映射到網格之后,需要更新該網格的元組.值得注意的是,網格之間是相互影響的,所以本文在更新當前網格時,還通過網格質心距離捕捉該網格與周圍網格的關系,以此來確定周圍網格的更新.

(3) 更新核心網格.

當網格權重發生變化時,需要判斷該網格是否滿足核心網格條件.如果滿足,則將該網格替換進核心網格列表中.

(4) 周期性檢測及刪除噪聲網格.

噪聲網格為一些由噪聲生成的網格或一些由簇衰退形成的零星網格.在數據流不斷到達的過程中,這些網格不斷累積,會造成內存空間的浪費,所以需要定期地檢測刪除這些噪聲網格.

本文根據噪聲網格比較稀疏并不可能變為稠密網格的特性,將經過tu時間段還沒由稀疏轉為稠密的網格定義為噪聲網格.定理3.1給出了一個稀疏網格轉換為稠密網格所需時間的計算公式.

定理3.1.設網格g是一個稀疏網格,tu是g轉換為稠密網格所需的時間,則:

證明:設網格g在t1時刻為稀疏網格,則:

設網格g在t2(t2＞t1)時刻轉為稠密網格,則:

如果要求網格g能在最短的時間內由稀疏網格轉為稠密網格,則需要時間段tu(tu=t2-t1)內到達的數據對象均映射在網格g內,因此,

其中,X∈(E(g,t2)-E(g,t1))表示時間段tu映射到網格g的數據對象集合.

由數據權重公式可得時間段tu映射到網格g的數據權重為.可以看到,該組數據權重滿足等比公式,所以不等式(15)可變形為

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

(5) 檢測核心網格是否變動.

隨著時間的推移,網格中歷史數據的權重逐漸衰減,新映射進來的數據具有較大權重從而導致網格權重發生變化,進而引起網格類型發生變化:稠密網格與稀疏網格互換、核心網格與非核心網格互換.這些變化使得數據流中的簇也是不斷變化的,有的簇會隨著時間的流逝慢慢消失,有的簇會隨著新數據點的映射而慢慢擴大.所以,本文根據核心網格是否變動來調用離線組件.

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

· 離線階段

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

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

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

算法1.GCStream的在線階段.

輸出:網格列表.

步驟:

算法2.GCStream的離線階段.

輸入:網格列表信息;

輸出:聚類結果.

步驟:

4 實驗評估

本節對 GCStream算法適應和捕捉數據流演變的能力、去除噪聲數據的能力、聚類質量以及聚類效率進行了實驗評估.

4.1 實驗準備

本文實驗的操作系統為64位Windows 7旗艦版,硬件環境為Intel(R) Core(TM) i3-3240(3.40GHz),RAM為4GB.

· 測試數據集

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

Table 1 Dataset feature summary表1 數據集特征匯總

· 對比算法

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

· 聚類質量評估方法

本文中采用的聚類質量評價方法為Purity和CMM[22].Purity定義如下:

其中,K代表簇的數量,Ci代表簇i中數據對象總數,代表簇i中被正確劃分的數據對象數目.Purity度量了各個簇中正確聚類的對象比例.

CMM(clustering mapping measure)是一種考慮了數據流中數據對象的權重(新鮮度)并可以反映簇生成、移動、分裂過程固有錯誤(比如簇的移動導致部分數據對象丟失;簇的合并和分裂產生重疊的簇,導致一些數據對象被錯誤劃分)的評價指標.此外,CMM還能對數據流中的噪聲情況進行度量.CMM定義如下:

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

4.2 算法參數選擇

在進行對比實驗之前,需要統一環境變量以及對算法參數進行調整.本文默認設置各數據流數據點到達速率為 1000pt/s,各算法中數據點的衰減速度一致.在 GCStream 中,設置λ=1.002,a=1;在 D-Stream 算法中,設置λ=0.998,a=-1;在 DenStream 和 DBSTREAM 中,設置λ=2,a=0.0028,使得權重衰減函數f=λ-a=0.998.對比算法的其他參數設置需參考其原始文獻.由于GCStream算法主要受質心調節參數k,Dislen以及Ncg的影響,所以本節將通過實驗探索這3個參數的選擇.

4.2.1 質心調節參數k

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

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

4.2.2 距離閾值Dislen

距離閾值Dislen為影響區域閾值,直接影響著網格之間的耦合以及簇的合并.本節實驗通過對比GCStream算法在不同Dislen值下的CMM和Purity來探索Dislen的取值,實驗結果如圖5所示.

在KDDCUP99數據流上,當Dislen=70時,聚類結果的CMM值明顯好于另外兩個,并且Purity值也是比較高的,所以本文選擇在Dislen=70的基礎進一步微調參數.在CoverType數據流上,Dislen=80和Dislen=140時聚類結果的CMM值高于Dislen=300的CMM值.進一步觀察發現,Dislen=140時聚類結果的Purity值高于Dislen=80時的Purity值,所以本文選擇在Dislen=140附近繼續尋找最優值.在PAMAP2數據流上,3個參數值的聚類結果相近,所以本文便選擇了Dislen=5為本文實驗的參數值.

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

4.2.3 核心網格集合LD大小Ncg

核心網格集合由大于閾值ε的網格組成.本節實驗選用不同的Ncg值進行聚類結果的CMM和Purity對比,實驗結果如圖6所示.在KDDCUP99數據流上,Ncg=6,8時聚類結果的CMM值較高.進一步對比這兩個不同Ncg值的聚類結果評價指標值發現,他們的CMM值相差不大,但是Ncg=6時,聚類結果的Purity值要高些,所以本文在KDDCUP99數據集上設置Ncg=6;在CoverType數據流上,當Ncg＞12時,算法聚類結果的 CMM指標值較小,當Ncg≤12時,聚類結果的兩個評價指標相差不大,所以本文在CoverType數據流上設置Ncg=12;在PAMAP2數據流上,不同Ncg值得到的聚類結果CMM值相差不大,但是當Ncg=12時,Purity值要高些,所以本文在PAMAP2數據流上設置Ncg=12.

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

綜上,本文后續實驗在3個UCI真實數據集上,質心調節參數k分別設置為0.96,0.97,0.87;網格質心距離閾值Dislen分別設置為64,144,5;核心網格集合LD大小Ncg分別設置為6,12,12.

4.2.4 數據集處理

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

Table 2 Purity comparison under standardized and non-standardized data sets表2 標準化和非標準化數據集下的Purity對比

4.3 聚類質量評價

4.3.1 UCI數據集的聚類結果

為了驗證GCStream算法的聚類質量,本文在3個UCI數據集上運行了GCStream算法、GCStream-UC算法、D-Stream算法、DenStream算法和DBSTREAM算法,比較了這些算法的Purity和CMM指標.實驗中,各個算法每隔25s對流數據進行一次聚類,圖7比較了各種算法的平均Purity.

Fig.7 Purity comparison on UCI datasets圖7 各算法在UCI數據集上的Purity對比

由圖7可見,GCStream算法在3個數據流上的平均Purity值均大于其他算法的平均Purity值.D-Stream算法在PAMAP2數據流上的Purity值較小,這是因為PAMAP2數據流中同一時刻內生成的簇較多并且維度較高,D-Stream算法對這類數據流比較敏感.圖8展示了各種算法在每次聚類時得到的CMM值,圖9比較了各種算法的平均CMM.由圖8可見:大多數時刻,GCStream算法的CMM值都是優于對比算法的,并且比較穩定.值得注意的是:GCStream算法的CMM值在3個數據流上的多個時刻均高于GCStream-UC,說明基于網格耦合思想更新網格結構能夠提高算法聚類質量.圖9表明,在3個數據集上,GCStream算法的CMM均值均大于其他算法的平均CMM.

Fig.8 CMM comparison of algorithms on UCI datasets圖8 各算法在UCI數據集上的CMM對比

Fig.9 CMM mean comparison on UCI datasets圖9 UCI數據集上的CMM均值對比

4.3.2 GCStream算法在不同數據流速度下的聚類質量

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

Fig.10 Cluster quality comparison under different stream rate圖10 不同數據流速度下的聚類質量對比

4.3.3 GCStream算法在不同網格邊長下的聚類質量

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

Fig.11 Cluster quality comparison under different grid sides圖11 不同網格邊長下的聚類質量對比

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

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

Fig.12 MTD data distribution圖12 MTD數據分布

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

Fig.14 Evolution of clusters in MTD datasets圖14 MTD數據集中簇的演變

4.4 聚類效率評價

實時更新聚類結果對于數據流聚類算法至關重要.本文分別在多個數據集和不同維度上對各算法的效率進行了對比.

4.4.1 GCStream算法在不同數據集上的效率

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

Fig.15 Response time comparison on multiple datasets圖15 多數據集上反映時間對比

4.4.2 網格邊長與數據維度對GCStream算法效率的影響

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

Fig.16 Response time comparisons in multiple dimensions and different grid lengths圖16 不同網格邊長和多維度上反映時間對比

5 結束語

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

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