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

由育陽 朱紀(jì)洪

(清華大學(xué)計(jì)算機(jī)系，北京100084)

楊志宏

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

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

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

1 相關(guān)概念

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

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

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

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

定義3 存在2個(gè)數(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è)定的正常數(shù)，則稱2個(gè)數(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).

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

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

2 二層容錯(cuò)聚類

2.1 HLSFTS 概要構(gòu)造

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

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

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

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

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

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

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

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

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

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

當(dāng)概要結(jié)構(gòu)不具有容錯(cuò)特性時(shí)，只輸出一層提升小波系數(shù)，出于簡化考慮假設(shè)將當(dāng)前窗口劃分為3個(gè)批次B1，B2和B3.對B1和B2中的數(shù)據(jù)進(jìn)行惰性提升，得到小波系數(shù)序列{c1，1，…，c1，l，c2，1，…，c2，l}，當(dāng)窗口滑動，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 容錯(cuò)網(wǎng)格密度聚類示意圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果分析與比較

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

實(shí)驗(yàn)數(shù)據(jù)采用UCI數(shù)據(jù)庫中的真實(shí)數(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個(gè)詞匯實(shí)例.US Census Data(1990)Data Set數(shù)據(jù)集為1990年美國人口普查數(shù)據(jù)集，包含2458285個(gè)數(shù)據(jù)實(shí)例和68個(gè)屬性.Forest Cover Type Data Set數(shù)據(jù)集來源于美國林務(wù)局的資源信息系統(tǒng)數(shù)據(jù)，數(shù)據(jù)集中包含581012個(gè)數(shù)據(jù)實(shí)例和54個(gè)屬性值.

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

圖4 FTGDStream算法聚類準(zhǔn)確率

圖5顯示了微觀聚類取不同的容錯(cuò)等級時(shí)FT-GDStream算法的最終聚類準(zhǔn)確率，劃分長度對聚類正確率的影響顯著小于容錯(cuò)等級對聚類準(zhǔn)確率的影響，容錯(cuò)程度的影響起主導(dǎo)作用.

圖5 容錯(cuò)水平對聚類準(zhǔn)確率的影響

采用Bag of Word Data Set，US Census Data(1990)數(shù)據(jù)集對FTGDStream算法、HPStream算法和D-Stream算法計(jì)算效率進(jìn)行了比較，數(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算法的時(shí)間效率約為HPStream算法1/3左右，F(xiàn)TGDStream算法比D-Stream算法的時(shí)間效率有略微差距，主要是2種算法的微觀聚類階段運(yùn)行效率的差異造成的，宏觀聚類階段由于HLSFTS概要結(jié)構(gòu)輸出的小波系數(shù)遠(yuǎn)遠(yuǎn)小于D-Stream算法參加網(wǎng)格劃分的數(shù)據(jù)規(guī)模，因此宏觀聚類階段FTGDStream算法的計(jì)算效率比D-Stream算法高.

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

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

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

圖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算法時(shí)間效率的影響.取3個(gè)數(shù)據(jù)集中的500000個(gè)數(shù)據(jù)實(shí)例，其中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)生相同聚簇?cái)?shù)量的時(shí)間也隨之增加，可以看出數(shù)據(jù)集的維數(shù)對FTGDStream算法的時(shí)間效率影響比較大，雖然提升小波變換具有相對較好的多維數(shù)據(jù)處理性能，當(dāng)數(shù)據(jù)量較大且維數(shù)較高時(shí)算法效率有所下降.

圖8 聚簇?cái)?shù)量對算法效率的影響

4 結(jié)論

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

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