具有容錯特性的兩層數(shù)據(jù)流聚類方法

由育陽 朱紀洪

(清華大學計算機系，北京100084)

楊志宏

(中國醫(yī)學科學院藥用植物研究所，北京100193)

近年來數(shù)據(jù)流環(huán)境下的聚類研究工作廣泛展開，具有代表性的相關(guān)研究包括基于k-median聚類思想的LOCAL SERACH算法和在此基礎上進行改進的STREAM 聚類算法［1］.文獻［2］將密度聚類與網(wǎng)格聚類聯(lián)合應用，提出了基于密度和網(wǎng)格技術(shù)的數(shù)據(jù)流實時聚類算法D-Stream，實現(xiàn)了數(shù)據(jù)流環(huán)境下的高效密度聚類，相關(guān)研究被認為是近年來數(shù)據(jù)流聚類技術(shù)的重要發(fā)展.文獻［3］首次提出了進化數(shù)據(jù)流聚類框架CluStream，其基本思想是將聚類過程分為在線的微觀聚類(mi-cro-cluster)過程和離線的宏觀聚類(macro-cluster)過程，CluStream算法是一種通用的數(shù)據(jù)流聚類算法，用戶可以根據(jù)不同處理需求在算法基礎上進行多種方式的擴展分析，該算法靈活的擴展性是其受到廣泛關(guān)注的主要原因之一.CluStream同樣存在一些缺點:首先更適合對球形數(shù)域空間進行聚類，然而在真實世界數(shù)據(jù)流中聚簇往往具有非凸的空間形狀;其次對于含有大量噪聲的原始數(shù)據(jù)適應性較差;最后需要預先指定聚簇數(shù)量，極大的影響了原始數(shù)據(jù)聚簇的形態(tài)分布.針對以上問題在CluStream算法的基礎上提出了HPStream算法［4］，采用高維投影和衰減函數(shù)來適應對高維數(shù)據(jù)流的挖掘，但是仍然需要用戶預先指定平均聚類數(shù)目.

本文提出了一種具有容錯特性的數(shù)據(jù)流網(wǎng)格密度聚類算法FTGDStream(Fault-Tolerant Grid-Density Clustering over Data Stream)，設計了一種新的概要數(shù)據(jù)結(jié)構(gòu)HLSFTS(Hierarchical Lifting Scheme Fault-Tolerant Synopses)，利用概要結(jié)構(gòu)的單次掃描、高壓縮和容錯程度可控的特點對新數(shù)據(jù)點和聚類中心點進行容錯度量.在FTGDStream二層框架聚類算法的第1過程中，在線微觀聚類要求算法對原始數(shù)據(jù)流進行單次掃描就可以高效的構(gòu)造小波概要數(shù)據(jù)結(jié)構(gòu).在第2過程中，聚類算法在離線狀態(tài)下進行，無需等待數(shù)據(jù)積累到希望的規(guī)模才進行一次性處理.

1 相關(guān)概念

現(xiàn)有的相關(guān)研究已經(jīng)證明任意的傳統(tǒng)小波都可以采用惰性提升的方法經(jīng)過有限次的提升和對偶提升后乘以一個常數(shù)得到［5］.

定義1 若(h，g)構(gòu)成補，則h的任何其他補g′(z)都可以表示為 g′(z)=g(z)+h(z)s(z2)，其中s(z)為Laurent多項式.

定義2 若(h，g)構(gòu)成補，則g的任何其他補h′(z)都可以表示為 h′(z)=h(z)－g(z)t(z2)，其中t(z)為Laurent多項式.

惰性提升的基本思想是首先將輸入信號分成奇偶2部分，由偶數(shù)項組成信號的低頻部分，奇數(shù)項組成原始信號的高頻部分，然后對低頻和高頻2個數(shù)據(jù)序列做有限次提升和對偶提升后乘以某常數(shù).

定義3 存在2個數(shù)據(jù)流片段 Dx={dx，1，dx，2，…，dx，n}和 Dx+1={dx+1，1，dx+1，2，…，dx+1，n}，定義相似性函數(shù)形如 S(Dx，Dx+1)，如果 S(Dx，Dx+1)≤δ成立，其中δ為由用戶設定的正常數(shù)，則稱2個數(shù)據(jù)序列Dx和Dx+1在以δ為邊界的情況下具有相似性.

相似性函數(shù) S(Dx，Dx+1)滿足如下關(guān)系［6］:

1)正定性，S(Dx，Dx+1)≤0;

2)對稱性，S(Dx，Dx+1)=S(Dx+1，Dx);

3)三角不等關(guān)系，S(Dx，Dx+1)≤S(Dx，Dx+2)+S(Dx+1，Dx+2).

用戶設定的δ通常在(0，1］內(nèi)取值，當取δ=0時表示Dx和Dx+1完全相同，當 δ→1時表示 Dx和Dx+1相似性越小.相似性度量通常與度量相似模式之間的距離聯(lián)系在一起，最常用的距離度量方法為Minkowski距離，定義如下:

Minkowski距離是對歐幾里得距離的推廣，當取p=2時即為歐幾里得距離，當取p=1時為Manhattan距離，當取p=∞時為最大距離度量.基于距離的度量方法計算量小且算法效率相對較高，經(jīng)過簡單的加權(quán)處理就可以實現(xiàn)對平行移動、拉伸或壓縮、振幅放大或壓縮和有限趨勢疊加的數(shù)據(jù)序列進行相似性度量.

2 二層容錯聚類

2.1 HLSFTS 概要構(gòu)造

設概要結(jié)構(gòu)分為l層，每層概要結(jié)構(gòu)代表長度為L的原始序列則存在Ll=Ll－1=…=L1，每一層都保留了數(shù)目遠小于次級層次的小波系數(shù)，l越大HLSFTS對原始序列的壓縮水平越高.

定義4 當前窗口中的數(shù)據(jù)序列為P，定義提升小波容錯概要的分辨率為r=P/2i，i為小波誤差樹的層數(shù).

顯然提升小波容錯概要結(jié)構(gòu)的分辨率決定了如何對原始數(shù)據(jù)流進行子序列劃分.

定義5 提升小波容錯概要結(jié)構(gòu)為一個四元組(t，n，ft，ls)，其中 t是概要結(jié)構(gòu)的時間戳，n 是原始數(shù)據(jù)流中的數(shù)據(jù)個數(shù)，ft是概要的相似性度量，ls是提升小波概要數(shù)據(jù)結(jié)構(gòu).

每層小波誤差樹的分辨率不同，原始序列數(shù)據(jù)個數(shù)n也不同.相似性度量ft可以定義多種度量方式.ls代表提升小波概要數(shù)據(jù)結(jié)構(gòu).提升小波概要數(shù)據(jù)結(jié)構(gòu)的小波系數(shù)選擇可以采用不同的誤差度量準則，小波系數(shù)的正規(guī)化方法采用重構(gòu)誤差采用衡量.

HLSFTS構(gòu)造流程如圖1所示.

圖1 HLSFTS構(gòu)造流程

以Haar小波為參照，每個惰性提升小波概要結(jié)構(gòu)的構(gòu)造算法計算時間復雜度至多不會超過O(N(logN)log m)，算法的空間復雜度至多不會超過O(N)，HLSFTS概要數(shù)據(jù)結(jié)構(gòu)由至少1個最多|B|個提升小波概要結(jié)構(gòu)構(gòu)成，重復進行最少|(zhì)B|次最多|B|+|B|/2+…+|B|/2J次的提升小波變換，所以 HLSFTS空間復雜度最大為O(|B|×N).時間復雜度最大為

當δ=0時HLSFTS概要數(shù)據(jù)結(jié)構(gòu)不具有容錯能力，對原始數(shù)據(jù)流進行無容錯壓縮，圖2為無容錯HLSFTS結(jié)構(gòu)示意圖.

圖2 無容錯HLSFTS結(jié)構(gòu)圖

當概要結(jié)構(gòu)不具有容錯特性時，只輸出一層提升小波系數(shù)，出于簡化考慮假設將當前窗口劃分為3個批次B1，B2和B3.對B1和B2中的數(shù)據(jù)進行惰性提升，得到小波系數(shù)序列{c1，1，…，c1，l，c2，1，…，c2，l}，當窗口滑動，B1中的數(shù)據(jù)過期而 B3中的數(shù)據(jù)插入，刪除由B1中的數(shù)據(jù)產(chǎn)生的小波系數(shù)序列，對B3中的數(shù)據(jù)做惰性提升得到新的小波系數(shù)序列，與由B2中數(shù)據(jù)產(chǎn)生的小波系數(shù)序列合并輸出{c2，1，…，c2，l，c3，1，…，c3，l}，完成 HLSFTS 概要數(shù)據(jù)結(jié)構(gòu)的重構(gòu).

2.2 FTGDStream聚類算法

二層聚類框架下的宏觀聚類階段采用基于網(wǎng)格密度的聚類算法更為適合.HLSFTS算法輸出小波系數(shù)的數(shù)據(jù)規(guī)模很小，在少量小波系數(shù)輸出的前提下加快了宏觀聚類過程中密度網(wǎng)格的劃分，算法結(jié)構(gòu)如圖3所示.

圖3 容錯網(wǎng)格密度聚類示意圖

空間網(wǎng)格的劃分是FTGDStream算法的重要過程，基礎網(wǎng)格劃分定義不同算法的復雜度和聚類結(jié)果也不同［7］.

定義6 設HLSFTS概要結(jié)構(gòu)隨著數(shù)據(jù)流的流動輸出d維提升小波系數(shù)C集，將C按維數(shù)劃分為C=C1×C2×…×Cd，在此基礎上進一步對任意維小波系數(shù)Ci進行等長劃分為Ci=Ci1×Ci2×…×Cip，則整個提升小波系數(shù)集C被劃分為個單元格.對于任意單元格g存在，其中 ji=1，2，…，pi則 g=(j1，j2，…，jd).

定義7 假設任意時間戳內(nèi)的任意數(shù)據(jù)x在時間點tc到達，則其密度是與時間t相關(guān)的函數(shù)，定義為 D(x，t)= λt－T(x)= λt－tc，其中 λ 稱為衰減因子，且 λ∈(0，1).

定義8 對任意空間格g和給定時間t，令E(g，t)為在時間t或之前的空間格g的數(shù)據(jù)映射，其 密 度 D(g，t)被 定 義 為

定理1 假設單元格g在tl時刻接收數(shù)據(jù)，在tn時刻接收新數(shù)據(jù)，并且存在tn＞tl，則新的密度計算公式為

證明 令單元格g在tl時刻之前接收的數(shù)據(jù)為 C={c1，c2，…，cm}，根據(jù)定義 8 可進一步得到，且根據(jù)定義7可得到其中 i=1，2，…，m，因此有

定義9 定義任意空間容錯格g的特征向量為三元組(tl，D，L)，其中tl為單元格g最后更新數(shù)據(jù)的時間，D為數(shù)據(jù)更新后的格密度，L為格的類標簽.

定理2 令C(t)為時間戳t內(nèi)到達的所有數(shù)據(jù)，則存在

定義11 設存在單元格集合G和任意單元格 g∈G，若 g=(j1，j2，…，jd)在任意維上都有相鄰單元格，那么g為單元格集合G的內(nèi)部單元格，否則g為G的邊界單元格.

定義12 令G=(g1，g2，…，gm)是一個單元格集合，若G的每一個內(nèi)部單元格都是稠密的，每一個邊界單元格都是過渡單元格，則稱G為單元格聚簇.

定義13 t時刻對于單元格 g存在D(g，t)≥Cm/N(1－λ)=Dm，其中Cm為取值大于1的控制閾值，則稱g為稠密單元格.

若在t時刻對于單元格g存在D(g，t)≥ Cl/N(1－λ)=Dl，其中0＜Cl＜1，則稱g為稀疏單元格.

若在t時刻對于單元格 g存在 Cl/N(1－λ)≤D(g，t)≤Cm/N(1－λ)，則 g為過渡單元格.

FTGDStream算法采用微觀在線聚類和宏觀離線聚類的雙層聚類技術(shù)實現(xiàn).當窗口滑動時批次內(nèi)的原始數(shù)據(jù)做提升小波變換得到第1層小波系數(shù)，相鄰批次的小波系數(shù)做容錯度量，對滿足容錯程度的相鄰批次小波系數(shù)做提升小波變換生成第2層小波系數(shù)，不滿足容錯條件的小波系數(shù)保留在第1層.這一過程反復迭代直至不再存在相鄰批次小波系數(shù)滿足容錯條件，生成d維容錯小波系數(shù)且d≥1.采用傾斜時間框架以快照的形式對在線微觀聚類進行保存［8］.FTGDStream算法首先對d維小波系數(shù)進行單元格劃分，然后計算單元格的特征向量，并根據(jù)定義劃分所有單元格的類型，根據(jù)稠密單元格和過渡單元格對整個單元格空間進行聚類，得到最終的聚類簇.以上聚類過程反復執(zhí)行實現(xiàn)了數(shù)據(jù)流環(huán)境下的容錯聚類.

3 實驗結(jié)果分析與比較

為驗證FTGDStream算法的效率，在實驗中與HPStream算法和D-Stream算法進行了比較，實驗結(jié)果如圖4～圖8所示.實驗在主頻為3.0 GHz Intel Celeron處理器及512 MB內(nèi)存的windows XP系統(tǒng)平臺下采用Visual C++6.0與Matlab混合編程實現(xiàn).

實驗數(shù)據(jù)采用UCI數(shù)據(jù)庫中的真實數(shù)據(jù)集Bag of Word Data Set，US Census Data(1990)Data Set和 Forest Cover Type Data Set.其中 Bag of Word Data Set數(shù)據(jù)集包含8000000個詞匯實例.US Census Data(1990)Data Set數(shù)據(jù)集為1990年美國人口普查數(shù)據(jù)集，包含2458285個數(shù)據(jù)實例和68個屬性.Forest Cover Type Data Set數(shù)據(jù)集來源于美國林務局的資源信息系統(tǒng)數(shù)據(jù)，數(shù)據(jù)集中包含581012個數(shù)據(jù)實例和54個屬性值.

首先對FTGDStream算法的聚類準確性進行驗證，其中取 Cm=3.0，Cl=0.8，λ =0.998，取數(shù)據(jù)集54維數(shù)據(jù)中的44維屬性作為實驗對象，對多次試驗取平均值.圖4顯示了宏聚類過程中對每一維的數(shù)據(jù)屬性劃分長度的不同對聚類正確率的影響，在微觀聚類過程中取容錯等級為零，F(xiàn)TGDStream算法的平均聚類準確率保持在96%以上.

圖4 FTGDStream算法聚類準確率

圖5顯示了微觀聚類取不同的容錯等級時FT-GDStream算法的最終聚類準確率，劃分長度對聚類正確率的影響顯著小于容錯等級對聚類準確率的影響，容錯程度的影響起主導作用.

圖5 容錯水平對聚類準確率的影響

采用Bag of Word Data Set，US Census Data(1990)數(shù)據(jù)集對FTGDStream算法、HPStream算法和D-Stream算法計算效率進行了比較，數(shù)據(jù)維數(shù)取值10，F(xiàn)TGDStream算法和D-Stream算法的維數(shù)劃分取值 0.02，取 Cm=3.0，Cl=0.8，λ =0.998.

圖6顯示FTGDStream算法和D-Stream算法的時間效率約為HPStream算法1/3左右，F(xiàn)TGDStream算法比D-Stream算法的時間效率有略微差距，主要是2種算法的微觀聚類階段運行效率的差異造成的，宏觀聚類階段由于HLSFTS概要結(jié)構(gòu)輸出的小波系數(shù)遠遠小于D-Stream算法參加網(wǎng)格劃分的數(shù)據(jù)規(guī)模，因此宏觀聚類階段FTGDStream算法的計算效率比D-Stream算法高.

圖6 數(shù)據(jù)規(guī)模對算法效率的影響

根據(jù)以上分析可以適當?shù)恼{(diào)整HLSFTS概要結(jié)構(gòu)的誤差度量準則，使HLSFTS概要結(jié)構(gòu)輸出更多的小波系數(shù)，提高對原始數(shù)據(jù)流的重構(gòu)誤差的同時也有助于提高聚類的準確性.

圖7顯示了當原始數(shù)據(jù)流的維數(shù)發(fā)生變化時對FTGDStream算法、HPStream算法和D-Stream算法計算效率的影響，數(shù)據(jù)維數(shù)增加對HPStream算法影響最大.對Bag of Word Data Set數(shù)據(jù)集進行預處理截取其中1000000個實例，當數(shù)據(jù)維數(shù)增加時HPStream算法計算時間消耗急劇增加，F(xiàn)TGDStream算法與D-Stream算法的時間效率始終相差不多，當維數(shù)超過60維時FTGDStream算法的時間效率漸漸超過D-Stream算法，這主要是因為HLSFTS概要結(jié)構(gòu)對高維數(shù)據(jù)的壓縮能力要好于基于網(wǎng)格的劃分方法，使得參加宏觀聚類的小波系數(shù)數(shù)量要少于D-Stream算法，因此造成了FTGDStream算法對高維數(shù)據(jù)的處理能力略好一些，總體看來時間效率差距不大.

圖7 數(shù)據(jù)維數(shù)對算法效率的影響

圖8顯示了Bag of Word Data Set，US Census Data(1990)Data Set，F(xiàn)orest Cover Type DataSet 3種不同數(shù)據(jù)規(guī)模的數(shù)據(jù)集對FTGDStream算法時間效率的影響.取3個數(shù)據(jù)集中的500000個數(shù)據(jù)實例，其中Bag of Word Data Set數(shù)據(jù)集取100維屬性值，US Census Data(1990)Data Set數(shù)據(jù)集取68維屬性值，F(xiàn)orest Cover Type Data Set數(shù)據(jù)集取44維屬性值.隨著不同數(shù)據(jù)集維數(shù)的增加產(chǎn)生相同聚簇數(shù)量的時間也隨之增加，可以看出數(shù)據(jù)集的維數(shù)對FTGDStream算法的時間效率影響比較大，雖然提升小波變換具有相對較好的多維數(shù)據(jù)處理性能，當數(shù)據(jù)量較大且維數(shù)較高時算法效率有所下降.

圖8 聚簇數(shù)量對算法效率的影響

4 結(jié)論

本文首先介紹了二層數(shù)據(jù)流挖掘框架的基本思想，以及將其應用于數(shù)據(jù)流容錯聚類的優(yōu)勢.將二層框架聚類思想與層次小波容錯概要數(shù)據(jù)結(jié)構(gòu)結(jié)合在一起，提出一種新的基于二層框架的數(shù)據(jù)流容錯聚類算法，利用容錯小波概要數(shù)據(jù)結(jié)構(gòu)實現(xiàn)在線微觀聚類，然后在此基礎上對小波容錯概要數(shù)據(jù)結(jié)構(gòu)輸出的小波系數(shù)進行密度劃分，給出了網(wǎng)格的劃分方法和基于網(wǎng)格密度聚類的離線宏觀聚類算法思想.在UCI數(shù)據(jù)集上的仿真實驗結(jié)果表明，F(xiàn)TGDStream算法利用小波概要對原始數(shù)據(jù)的高壓縮率減小網(wǎng)格密度聚類算法的計算負載，增強算法對高維數(shù)據(jù)的處理能力，進而提高了基于不同容錯等級的數(shù)據(jù)流聚類算法的效率，是一種有效的數(shù)據(jù)流容錯聚類方法

References)

［1］Callaghan O L，Mishra N，Meyerson A.Streaming data algorithms for high-quality clustering［C］//San Jose.Proceedings of International Conference on Data Engineering.California:IEEE Computer Society，2002:685 －699

［2］Chen Y X，Tu L.Density-based clustering for real-time stream data［C］//San Jose.Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.California:ACM，2007:133 －142

［3］Aggarwal C C，Han Jiawei，Wang Jianyong，et al.A framework for clustering evolving data streams［C］//Proceeding of the 29thInternational Conference on Very Large Data Bases.Berlin:Morgan Kaufmann ，2003:81－92

［4］Aggarwal C C，Han Jiawei，Wang Jianyong，et al.A framework for projected clustering of high dimensional data streams［C］//Proceeding of the 29thInternational Conference on Very Large Data Bases.Toronto，Canada:Morgan Kaufmann，2004:852 －863

［5］Chen Mingsheng，Wu Xianliang，Wei Sha，et al.Fast multipole method accelerated by lifting wavelet transform scheme［J］.Applied Computational Electromagnetics Society Journal，2009，24(2):109－115

［6］Shahin M，Badawi A，Kamel M.Biometric authentication using fast correlation of near infrared hand vein patterns［J］.International Journal of Biometrical Sciences，2007，2(3):141 －148

［7］Cao Feng，Ester M，Qian Weining，et al.Density-based clustering over an evolving data stream with noise［C］//Proceedings of the 6th SIAM International Conference on Data Mining.Bethesda，MD:SIAM，2006:326－337

［8］Han J，Kamber M.Data mining:concepts and techniques［M］.2nd ed.Morgan Kaufmann:Elsevier Inc，2006:467 －589