基于時(shí)間衰減和密度的任意簇?cái)?shù)據(jù)流聚類*

龔 云，趙 鵬，王守軍

（安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230039）

數(shù)據(jù)流是指連續(xù)的、潛在無(wú)限量的、快速變化的、隨時(shí)間而至的數(shù)據(jù)元素的流。由于數(shù)據(jù)采集的快捷化和自動(dòng)化，數(shù)據(jù)庫(kù)技術(shù)和互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，日常生活已經(jīng)與數(shù)據(jù)流息息相關(guān)，如網(wǎng)絡(luò)實(shí)時(shí)監(jiān)控、電子商務(wù)、衛(wèi)星遙感等。這些數(shù)據(jù)都具有流的特性。而傳統(tǒng)的數(shù)據(jù)挖掘方法需多遍掃描全部數(shù)據(jù)且數(shù)據(jù)必須以靜態(tài)形式存儲(chǔ)在磁盤(pán)空間里，因此用來(lái)專門(mén)處理數(shù)據(jù)流的數(shù)據(jù)處理模型和算法應(yīng)運(yùn)而生[1]。

CluStream算法是經(jīng)典數(shù)據(jù)流聚類和主要算法，該算法提供了一個(gè)解決數(shù)據(jù)流聚類問(wèn)題的優(yōu)秀雙層聚類方法，但由于它采用的是基于BIRCH算法的核心思想，所以僅限于得到球形聚簇結(jié)果[2]。K均值算法是基于劃分的聚類方法，采用分而治之的策略對(duì)數(shù)據(jù)分塊后再進(jìn)行聚類，這樣保證算法在較小的內(nèi)存空間范圍內(nèi)獲取常數(shù)因子的近似結(jié)果[3]。該算法的缺點(diǎn)是K取值的不確定因素太多，影響了準(zhǔn)確性且不能考慮被分析數(shù)據(jù)的時(shí)間相關(guān)性。

1 基于時(shí)間衰減和簇合并的聚類處理算法（CluTA）

在分析某些類數(shù)據(jù)時(shí)往往更加注重其近期變化帶來(lái)的影響，時(shí)間越久遠(yuǎn)被關(guān)注的程度就越低，如網(wǎng)絡(luò)入侵行為的分類和趨勢(shì)、股市不斷變化的大盤(pán)信息等。為提高聚類得到結(jié)果的精確性，在挖掘時(shí)需考慮時(shí)間衰減的因素。由于K均值算法聚類的結(jié)果都是球型簇，本文通過(guò)合并相近相似簇達(dá)到輸出任意形狀簇的聚類結(jié)果。

本算法采用分層思想，第一層增加K均值算法得到中心點(diǎn)的信息，使每個(gè)中心點(diǎn)c中保留s(簇內(nèi)所有的點(diǎn)到 c的距離和)、d(簇內(nèi)最遠(yuǎn)點(diǎn)到 c的距離)、n(簇內(nèi)所有點(diǎn)的個(gè)數(shù))、t(c的生成時(shí)刻)。第二層結(jié)合本算法給出的衰減函數(shù)和密度計(jì)算出關(guān)鍵點(diǎn)的權(quán)重；比較關(guān)鍵點(diǎn)的權(quán)重和距離，如果距離足夠近且權(quán)重比在允許范圍內(nèi)則合并簇。重復(fù)循環(huán)直到?jīng)]有可合并的簇，輸出最終結(jié)果。

1.1 相關(guān)定義和性質(zhì)

假設(shè)數(shù)據(jù)以塊X1,X2,…，Xn，…的形式按序到達(dá)，每個(gè)塊內(nèi)包含 m個(gè)數(shù)據(jù)點(diǎn) xi（xi1,xi2,…，xim）且可以在內(nèi)存中進(jìn)行處理。每個(gè)數(shù)據(jù)點(diǎn)是一個(gè)d維向量。CluTA算法是以Kmeans為基礎(chǔ)初次聚類生成k個(gè)關(guān)鍵點(diǎn),采用五元組的方式存儲(chǔ)關(guān)鍵點(diǎn)信息。

定義1.關(guān)鍵點(diǎn)

性質(zhì) 1. 對(duì)任意關(guān)鍵點(diǎn)ri(ci，si，di，ni，ti)和數(shù)據(jù)點(diǎn) p，均值點(diǎn)ci代表的所有數(shù)據(jù)點(diǎn)到p的距離和的上界為si＋ni×dist（ci，p）[4]。

性質(zhì) 2. 對(duì)任意關(guān)鍵點(diǎn) ri(ci，si，di，ni，ti)和 rj（cj，sj，dj，nj，tj)，設(shè) c′為均值點(diǎn) ci與 cj的中點(diǎn),均值點(diǎn) ci所代表的所有數(shù)據(jù)點(diǎn)到c′的距離和的上界可以有效替代其準(zhǔn)確值[4]。

衰減函數(shù)表示簇隨時(shí)間衰減的速率，當(dāng)關(guān)鍵點(diǎn)生成時(shí)刻距當(dāng)前時(shí)刻之差達(dá)到輸入閾值△t后,即置權(quán)值為0，刪除該關(guān)鍵點(diǎn)。

定義2.衰減函數(shù)Y=f(T)：

其中，△t為用戶輸入的有效時(shí)間范圍閾值，t為該關(guān)鍵點(diǎn)的生成時(shí)刻，T為循環(huán)執(zhí)行的當(dāng)前時(shí)刻值，Y為衰減函數(shù)且取值在[0，1]之間的閉區(qū)間。

分析 T-t的取值范圍，首先在 0＜T-t≤△t內(nèi)討論：當(dāng) T-t＜△t，Y>0表示此關(guān)鍵點(diǎn)是有效的； 當(dāng) T-t=△t，表示距離當(dāng)前時(shí)間已達(dá)到用戶設(shè)置的失效時(shí)長(zhǎng)，此時(shí)Y=0,表示該關(guān)鍵點(diǎn)會(huì)被刪除；若循環(huán)計(jì)算得T-t＞△t時(shí)，此時(shí)直接置Y=0。由此可見(jiàn)，T-t的值越大衰減函數(shù)Y的值越小，該關(guān)鍵點(diǎn)的實(shí)際使用價(jià)值越小。

定義3.可合并簇

任意兩個(gè)相鄰簇r1(c1，s1，d1，n1，t1)和 r2(c2，s2，d2，n2，t2)若滿足下列條件，本文稱為可合并簇。

(1)dist(c1，c2)≤d1+d2

上述(1)表示兩簇的均值點(diǎn)距離小于或等于兩簇內(nèi)最遠(yuǎn)距離之和，相距足夠近則考慮合并簇。但也可能出現(xiàn)兩簇相距很近仍不符合合并要求的情況。如圖1所示，兩簇的距離足夠近，但二者密度相差較大就不應(yīng)該再合并。因此加上條件(2),通過(guò)計(jì)算兩簇的權(quán)重比是否相差懸殊來(lái)決定是否可以合并。若上述限定條件都符合，則合并簇得到如圖2所示結(jié)果。

1.2 CluTA算法

輸入：△t為用戶允許數(shù)據(jù)有效的時(shí)間范圍;ε為用戶允許兩個(gè)可合并簇權(quán)重相差的比例，0＜ε＜1;r[][]為初始K均值聚類結(jié)束后得到的關(guān)鍵點(diǎn)。

輸出：合并后簇的集合。

方法：

//處理初始K均值聚類結(jié)束后保留的關(guān)鍵點(diǎn)信息，進(jìn)一步合并簇，精確聚類結(jié)果:

(1)取當(dāng)前時(shí)刻記為T(mén)，計(jì)算任意關(guān)鍵點(diǎn)i，j間的距離

(2)repeat

//i，j兩個(gè)簇的距離足夠近且兩個(gè)簇的權(quán)重比不超過(guò)設(shè)定范圍，可以考慮合并:

(3)存儲(chǔ)新生成點(diǎn)r′并置關(guān)鍵點(diǎn) ci，cj為無(wú)效節(jié)點(diǎn)；

(4)until沒(méi)有可合并的簇；

(5)輸出聚簇結(jié)果。

1.3 算法分析

該算法改進(jìn)K均值聚類算法結(jié)果信息，第一層運(yùn)用K均值算法的計(jì)算復(fù)雜度為O(nkt)，n為數(shù)據(jù)點(diǎn)數(shù)目，t為循環(huán)次數(shù)，通常有 k＜＜n和 t＜＜n。第二層將生成的 k個(gè)聚簇進(jìn)行合并，計(jì)算復(fù)雜度為O(k2)，k為常數(shù)級(jí)關(guān)鍵點(diǎn)數(shù)目。在K均值的基礎(chǔ)上增加的內(nèi)存空間也非常少，僅需保存k個(gè)關(guān)鍵點(diǎn)和一些中間變量。因此，該算法在時(shí)間和空間復(fù)雜度上都近似于K均值聚類算法，具有簡(jiǎn)單、高效的特點(diǎn)。

2 實(shí)驗(yàn)分析

算法在VC 6.0環(huán)境下采用C編寫(xiě),實(shí)驗(yàn)平臺(tái)為一臺(tái) CPU 2.8 GHz、內(nèi)存 1 GB、操作系統(tǒng)為 Windows XP的PC機(jī)。采用了UCI的KDD CUP 1999網(wǎng)絡(luò)入侵檢測(cè)數(shù)據(jù)集。KDD CUP 1999數(shù)據(jù)集共23類，每一數(shù)據(jù)有42個(gè)屬性，去除一些非數(shù)值型數(shù)據(jù)的維數(shù)，選留其中的20維做為實(shí)驗(yàn)數(shù)據(jù)。使用每類中的5 000條中的20個(gè)屬性，打開(kāi)文件模擬數(shù)據(jù)流環(huán)境讀入數(shù)據(jù),用Kmeans算法得出初始聚類關(guān)鍵點(diǎn)信息，再運(yùn)用CluTA算法進(jìn)行簇合并，最終與僅用Kmeans算法聚類的結(jié)果精確度比較，如圖3所示，判斷聚類質(zhì)量的算法可參考文獻(xiàn)[5]。聚類質(zhì)量為類內(nèi)距離值加上類間密度值。類內(nèi)距離是表示該類內(nèi)部點(diǎn)的密疏程度，類間密度是衡量各個(gè)類的平均密度關(guān)系，如圖4所示，該值較小表明聚類簇集的類間區(qū)分度較好，因此二者總和越小，表示聚類質(zhì)量越好。

為解決使用價(jià)值隨時(shí)間衰減的一類流數(shù)據(jù)聚類問(wèn)題和實(shí)現(xiàn)任意形狀簇的聚類，本文在基于傳統(tǒng)的K均值聚類算法基礎(chǔ)上，保留其直觀、高效的特點(diǎn)，提出了基于時(shí)間衰減的任意簇?cái)?shù)據(jù)流聚類算法。即在K均值算法處理得到結(jié)果的基礎(chǔ)上再考慮用時(shí)間和密度、空間距離等因素合并簇。理論分析和實(shí)驗(yàn)結(jié)果證明該算法相對(duì)于僅用K均值算法在處理對(duì)近期價(jià)值比較關(guān)心一類的數(shù)據(jù)時(shí)具有更精確的聚類結(jié)果。下一步的工作將著重于提高算法的效率和將其應(yīng)用到更廣泛的生活實(shí)踐中。

[1]Han Jiawei.Micheline.Data Mining:Concepts and Techniques,Second Edition[M].China Machine Press,2008.

[2]AGGARWAL C C,et al.A framework for clustering evolving data streams.In:Proc.of the 29th VLDB Conf.,2003.

[3]GUHA S，MISHRA N，MOTWANI R.Clustering data streams[C].Proceedings of the Annual Symposium on Foundations of Computer Science.2000.

[4]倪巍偉，陸介平,陳耿，等.基于k均值分區(qū)的流數(shù)據(jù)高效密度聚類算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2007，28(1):83-87.

[5]HALKIDI M,VAZIRGIANNIS M.Clustering validity assessment；finding the optimal partitioning of adata set[C].ICDM 2001:187-194.