基于直方圖的概率數(shù)據(jù)流聚類算法

程轉流 胡為成

（銅陵學院，安徽銅陵 244000）

基于直方圖的概率數(shù)據(jù)流聚類算法

程轉流 胡為成

（銅陵學院，安徽銅陵 244000）

文章提出一種概率數(shù)據(jù)流聚類方法PWStream。PWStream采用直方圖保存最近數(shù)據(jù)信息摘要，在允許的誤差范圍內(nèi)刪除過期的數(shù)據(jù)元組；并設計了一種基于距離和存在概率的簇選擇策略，從而可以發(fā)現(xiàn)更多的強簇。理論分析和實驗結果表明，該方法具有良好的聚類質(zhì)量和較快的數(shù)據(jù)處理能力。

概率數(shù)據(jù)流；聚類；直方圖

數(shù)據(jù)流就是大量連續(xù)到達的、潛在無限的數(shù)據(jù)的有序序列，對數(shù)據(jù)流中進行聚類分析已成為數(shù)據(jù)挖掘的熱點之一。最具代表性的數(shù)據(jù)聚類算法是Aggarwal提出CluStream算法[1]，在CluStream算法的基礎上，Aggarwal等又提出了專門針對高維連續(xù)屬性數(shù)據(jù)流的HPStream算法[2]；針對CluStream算法只適應于球形聚類，不能支持任意形狀聚類的缺點，F(xiàn)eng Cao等人[3]中提出了針對動態(tài)進化數(shù)據(jù)流的Den Stream算法，它可以進行任意形狀的聚類。常建龍等人[4]提出了一種基于滑動窗口的數(shù)據(jù)流聚類分析算法CluWin。實際上，由于數(shù)據(jù)產(chǎn)生的隨機性、數(shù)據(jù)收集的不完全性，不確定數(shù)據(jù)，也即概率數(shù)據(jù)大量存在于數(shù)據(jù)流中，這種數(shù)據(jù)流就是概率數(shù)據(jù)流[5]。對此，戴東波等人[6]提出一種在概率數(shù)據(jù)流上進行聚類的有效方法PStream。但P-Stream算法并不適用于滑動窗口模型下的概率數(shù)據(jù)流聚類分析問題，本文提出一種新的算法PWStream，該算法利用直方圖存儲最近數(shù)據(jù)記錄的分布狀況，并設計出符合概率數(shù)據(jù)流的簇選擇策略和簇合并策略，從而挖掘出概率數(shù)據(jù)流中存在概率較大的簇。

1.問題定義和描述

2.PWStream算法

2.1 算法的基本框架

下面將給出PWStream算法，該算法是對一個滑動窗口內(nèi)的概率數(shù)據(jù)流進行聚類分析。算法可分為兩部分，如圖1所示：第1~18為在線部分，維護EHCF結構；第19~21為離線聚類。PWStream算法包含三個參數(shù)：S為待處理的概率數(shù)據(jù)流，ε（0<ε<1）為誤差參數(shù)，NC為EHCF的最大個數(shù)，由系統(tǒng)的有效內(nèi)存來決定。

圖1 PWStream算法過程

PWStream算法的在線部分先把概率流中的前q個元組作為簇（EHCF）的中心（第2行），然后對到來的每一個元組v′，根據(jù)存在概率和距離遠近兩個因素，調(diào)用Find_cluster算法選擇合適的簇（EHCF）（第5行），如果v′可被候選簇吸收（第6、7行），則加入；否則，看簇（EHCF）的總數(shù)是否達到最大值NC，若是，則利用find_two_EHCF算法尋找兩個合適的簇（EHCF）合并（第9~12行）；再由新元組v′單獨創(chuàng)建一個簇（EHCF）（第13行）；第14行是檢測各EHCF中是否含有過期的TCF，若有，就刪除；如果EHCF中不包含任何TCF，就刪除該EHCF（第16、17行）。算法merge就是采用文獻[4]的方法對兩個簇（EHCF）進行合并，算法Find_cluster，find_two_EHCF在后面詳細說明。

2.2 尋找合適候選簇算法Find_cluster

設某一時刻PWStream算法在線部分維護的簇（EHCF）的集合EC=｛C1，C2，…，Cn｝，當一個新元組<ν，p，t>到來時，要在EC中為其找到一個Ci（1≤i≤n）作為候選簇。假設新元組<ν，p，t>與EC中簇Ci中心點的距離為Di，最近的距離為Dmin，對應的簇為Cmin，在文獻[1]中，CluStream算法采用的是只單純考慮距離的選擇方法，也就是選擇Cmin作為候選簇，但在概率流中，就要考慮距離與存在概率的綜合因素。

find_two_EHCF算法按如下規(guī)則選取待合并的兩個簇：

Rule 1在對lj1，lj2，…，lju依次掃描的過程中，若第一次遇到的lji（1≤i≤u）滿足：Cji1和Cji2分別為過渡簇和強簇，合并之后的簇Cji′為強簇，則選取Cji1和Cji2待合并；

Rule 2如果Rule 1不滿足，在對lj1，lj2，…，lju依次掃描的過程中，若第一次遇到的lj1（1≤i≤u）滿足：Cji1和Cji2都是強簇，則選取Cji1和Cji2待合并；

Rule 3如果Rule 1和Rule 2都不滿足，則選取與lmin對應的兩個簇Cmin1和Cmin2待合并。

定理1設△SSQ(I)和△SSQ(II)分別表示根據(jù)算法CluS－tream選擇策略（僅考慮距離因素）和算法find_two_EHCF選擇策略選取兩個簇（EHCF）進行合并所引起的SSQ值的增量，則有△SSQ(II)

證明：為方便起見，假設概率數(shù)據(jù)流中的元組ν值是一維的，算法CluStream選擇策略（僅考慮距離因素）找到的邊為lmin，與之對應的兩個簇為Cmin1和Cmin2，元組的個數(shù)分別為imin1和imin2，元組值分別為a1，a2，…，aimin1和b1，b2，…，bimin2，中心點分別為Vmin1和Vmin2，合并之后的簇為C′min，中心點為V′min；find_two_EHCF選擇策略找到的邊為lk，與之對應的兩個簇為Ck1和Ck2，元組的個數(shù)分別為ik1和ik2，中心點分別為Vk1和Vk2，合并之后的簇為C′k，中心點為V′k，則

很顯然，上述兩個算法在選取待處理的簇時，均考慮了距離和存在概率兩個因素，在距離允許的情況下（用參數(shù)M1，M2來約束），盡量提高待處理簇的存在概率，這樣在最終離線聚類時的強簇數(shù)量就較多，又因為M1，M2的存在，總的距離平方和SSQ不會提高很多。

3.實驗結果和分析

3.1 實驗設置

所有實驗都在2.79GHz的PC上進行，操作系統(tǒng)為Windows XP，算法用VC++實現(xiàn)。我們用文獻[4]的CluWin算法、文獻[6]的P-Stream算法與PWStream算法進行比較。因為CluWin算法主要是針對確定數(shù)據(jù)流的，而PWStream是針對概率數(shù)據(jù)流的，為了便于比較實驗結果，我們將PWStream算法中采用CluWin算法中選擇候選簇(EHCF)策略和選擇兩個等合并簇(EHCF)策略的算法稱為P-CluWin算法，從而將PWStream算法與P-CluWin算法進行比較。

實現(xiàn)數(shù)據(jù)包括真實數(shù)據(jù)集和人工數(shù)據(jù)集，存在概率采用在[θ，1]上均勻分布的數(shù)據(jù)。

圖4 PWStream與P-Stream的SSQ比較

圖2 PWStream與P-CluWin的SSQ比較

圖3 PWStream與P-CluWin的強簇數(shù)據(jù)比較

真實數(shù)據(jù)集采用KDD-CUP′99和KDD-CUP′98兩個數(shù)據(jù)集。人工數(shù)據(jù)集滿足一系列高斯分布。每10K個數(shù)據(jù)點改變一次當前高斯分布的中心和方差，且采用如下標記描述人工數(shù)據(jù)集：‘B’表示數(shù)據(jù)集中包含的數(shù)據(jù)點數(shù)；‘C’表示簇的個數(shù)；‘D’表示數(shù)據(jù)點的維數(shù)。例如，B100C20D30表示數(shù)據(jù)集包含100K個數(shù)據(jù)點，分別屬于20個不同的簇，各數(shù)據(jù)點的維數(shù)為30。

在實驗中，PWStream中的EHCF最大個數(shù)與P-CluWin算法的EHCF最大個數(shù)、P-Stream中的最大微簇個數(shù)相等。除非特別指明，PWStream算法中的各參數(shù)設置如下：θ=0.05，ε= 0.1，N=10000。

3.2 聚類質(zhì)量

聚類質(zhì)量評價標準采用SSQ和強簇數(shù)目，由于最能影響聚類質(zhì)量的是：(1)新元組到來時，選擇候選簇的策略；(2)當簇(EHCF)的個數(shù)達最大值時，選擇兩個簇進行合并的策略。我們分別比較算法PWStream與P-CluWin、P-Stream在數(shù)據(jù)集KDD-CUP′98和KDD-CUP′99的實驗結果。為了保證結果更準確，算法采用不同的α，β，M1和M2值各執(zhí)行5次，并計算平均SSQ和平均強簇數(shù)目作為結果值。

PWStream與P-CluWin的聚類質(zhì)量比較如圖2和圖3所示(KDD-CUP'98數(shù)據(jù)集)。由于β的平均值為0.2，θ=0.05，M1的平均值為5，M2的平均值為10，從圖2中可以看出，如定理2和定理3所言，PWStream的SSQ不會超過P-CluWin的10倍，但在每個時標處，從圖3所示，PWStream找到的強簇都比P-CluWin的要多，如在時標120000處，強簇個數(shù)的差別最大。并且PWStream找到強簇個數(shù)主要是呈增長趨勢，而PCluWin找到的強簇個數(shù)不穩(wěn)定。這主要得益于PWStream算法中的候選規(guī)則，在M1和M2不是很小的情況下，PWStream以應用Rule 1和Rule 2為主來找到候選簇和待合并的兩個候選簇，而這兩條規(guī)則用以保持強簇個數(shù)不變或增大。而PCluWin只考慮了最近距離而沒有考慮簇的存在概率，致使強簇個數(shù)不穩(wěn)定。

PWStream與P-Stream的聚類質(zhì)量比較如圖4所示(KDD-CUP’99數(shù)據(jù)集)。由于PWStream與P-Stream都是對概率數(shù)據(jù)流進行聚類，所采用的候選簇(EHCF)策略類似，所不同的是PWStream是在滑動窗口內(nèi)進行聚類，忽略過期元組，而P-Stream是對所有元組進行聚類，兩者所得到的強簇數(shù)量差不多，但從圖4可看出，兩者在SSQ上相差較大，PWStream高質(zhì)量的聚類結果主要是因為EHCF結構能夠準確捕獲當前記錄的分布狀況，舊記錄在在線聚類過程中被及時地刪除，當EHCF在簇中心發(fā)生偏移時，能保持一個較小的半徑，然而在P-Stream中，微簇內(nèi)各記錄的時標被累加起來，當簇中心發(fā)生漂移時，微簇半徑將不斷增大，這將混淆不同的簇，并導致聚類質(zhì)量不夠理想。

4.結束語

本文提出一種基于滑動窗口的概率數(shù)據(jù)流聚類算法PWStream，該算法采用聚類特征指數(shù)直方圖作為概要結構，可較好地保存數(shù)據(jù)流當前窗口內(nèi)的數(shù)據(jù)分布狀況，從而獲取較高質(zhì)量的聚類效果；并且(1)新元組到來時，選擇基于距離和存在概率的新候選簇的策略，(2)當簇(EHCF)的個數(shù)達最大值時，基于距離和存在概率選擇兩個簇進行合并的策略，能找到更多的強簇，但其SSQ不會超過僅根據(jù)距離選擇策略的常數(shù)倍。實驗結果表明，在概率數(shù)據(jù)流中，P-Stream算法相對于傳統(tǒng)方法有較好的聚類質(zhì)量，能夠有效地適應數(shù)據(jù)流的演化情況。

［1］Aggarwal C C，Han Jia-Wei，Wang Jian-Yong，Yu P S.A framework for clustering evolving data streams[R].Proceeding of the 29th International Conference on Very Large Data Bases，Berlin，Germany，2003:81-92.

［2］Aggarwal C C，Han Jia wei，Wang Jian-yong，Yu P S.A framework for projected clustering of high dimensional data streams [R].Proceedings of the 30th International Conference on Very Large Data Bases，Toronto，Canada，2004:852-863.

［3］Cao Feng，Ester M，Qian Wei-Ning，ZhouAo-Ying.Densitybased clustering over an evolving data stream with noise[R]. Proceedings of the 6th SIAM International Conference on Data Mining，Bethesda，MD，USA，2006:326-337.

［4］常建龍，曹鋒，周傲英.基于滑動窗口的進化數(shù)據(jù)流聚類[J].軟件學報，2007，18(4):905-918.

［5］Cormode G，Garofalakis M.Sketching probabilistic data streams. In:Chan CY，Ooi BC，Zhou A，eds[C].Proc.of the ACM SIGMOD Int'1 Conf.on Management of Data，Beijing:ACM Press，2007. 281-292.

［6］戴東波，趙杠，孫圣力.基于概率數(shù)據(jù)流的有效聚類算法[J].軟件學報，2009，20(5):1313~1328.

TP311

：A

：1672-0547（2010）02-0073-03

2010-03-04

程轉流（1979-），女，安徽潛山人，銅陵學院數(shù)學與計算機科學系講師，碩士，研究方向：數(shù)據(jù)流挖掘、多Agent系統(tǒng)；

胡為成（1975-），男，安徽桐城人，銅陵學院數(shù)學與計算機科學系副教授，碩士，研究方向：數(shù)據(jù)流挖掘、遺傳程序設計等。

安徽省高等學校自然科學研究項目（編號：KJ2009B139）；安徽省高等學校青年教師科研資助計劃項目（編號：2008jq1143）。