程轉(zhuǎn)流 胡為成

（銅陵學(xué)院，安徽銅陵 244000）

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

程轉(zhuǎn)流 胡為成

（銅陵學(xué)院，安徽銅陵 244000）

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

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

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

1.問題定義和描述

2.PWStream算法

2.1 算法的基本框架

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

圖1 PWStream算法過程

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

2.2 尋找合適候選簇算法Find_cluster

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

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

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

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

Rule 3如果Rule 1和Rule 2都不滿足，則選取與lmin對(duì)應(yīng)的兩個(gè)簇Cmin1和Cmin2待合并。

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

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

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

3.實(shí)驗(yàn)結(jié)果和分析

3.1 實(shí)驗(yàn)設(shè)置

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

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

圖4 PWStream與P-Stream的SSQ比較

圖2 PWStream與P-CluWin的SSQ比較

圖3 PWStream與P-CluWin的強(qiáng)簇?cái)?shù)據(jù)比較

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

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

3.2 聚類質(zhì)量

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

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

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

4.結(jié)束語

本文提出一種基于滑動(dòng)窗口的概率數(shù)據(jù)流聚類算法PWStream，該算法采用聚類特征指數(shù)直方圖作為概要結(jié)構(gòu)，可較好地保存數(shù)據(jù)流當(dāng)前窗口內(nèi)的數(shù)據(jù)分布狀況，從而獲取較高質(zhì)量的聚類效果；并且(1)新元組到來時(shí)，選擇基于距離和存在概率的新候選簇的策略，(2)當(dāng)簇(EHCF)的個(gè)數(shù)達(dá)最大值時(shí)，基于距離和存在概率選擇兩個(gè)簇進(jìn)行合并的策略，能找到更多的強(qiáng)簇，但其SSQ不會(huì)超過僅根據(jù)距離選擇策略的常數(shù)倍。實(shí)驗(yàn)結(jié)果表明，在概率數(shù)據(jù)流中，P-Stream算法相對(duì)于傳統(tǒng)方法有較好的聚類質(zhì)量，能夠有效地適應(yīng)數(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］常建龍，曹鋒，周傲英.基于滑動(dòng)窗口的進(jìn)化數(shù)據(jù)流聚類[J].軟件學(xué)報(bào)，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].軟件學(xué)報(bào)，2009，20(5):1313~1328.

TP311

：A

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

2010-03-04

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

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

安徽省高等學(xué)校自然科學(xué)研究項(xiàng)目（編號(hào)：KJ2009B139）；安徽省高等學(xué)校青年教師科研資助計(jì)劃項(xiàng)目（編號(hào)：2008jq1143）。