摘 要： 數(shù)據(jù)挖掘的一個(gè)重要分支是數(shù)據(jù)流聚類(lèi)技術(shù),。基于K均值算法的基礎(chǔ)提出了CluTA算法,。該算法在處理用K均值方法分類(lèi)得到的結(jié)果時(shí)考慮時(shí)間衰減因素和相似簇的合并,，達(dá)到用戶(hù)對(duì)時(shí)間的要求并實(shí)現(xiàn)了任意形狀簇聚類(lèi),。理論分析和實(shí)驗(yàn)結(jié)果都表明算法具有可行性。
關(guān)鍵詞： 數(shù)據(jù)流,；密度聚類(lèi),；均值關(guān)鍵點(diǎn)；時(shí)間衰減
數(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)專(zhuān)門(mén)處理數(shù)據(jù)流的數(shù)據(jù)處理模型和算法應(yīng)運(yùn)而生[1],。
CluStream算法是經(jīng)典數(shù)據(jù)流聚類(lèi)和主要算法,，該算法提供了一個(gè)解決數(shù)據(jù)流聚類(lèi)問(wèn)題的優(yōu)秀雙層聚類(lèi)方法，但由于它采用的是基于BIRCH算法的核心思想,，所以?xún)H限于得到球形聚簇結(jié)果[2],。K均值算法是基于劃分的聚類(lèi)方法，采用分而治之的策略對(duì)數(shù)據(jù)分塊后再進(jìn)行聚類(lèi),，這樣保證算法在較小的內(nèi)存空間范圍內(nèi)獲取常數(shù)因子的近似結(jié)果[3],。該算法的缺點(diǎn)是K取值的不確定因素太多，影響了準(zhǔn)確性且不能考慮被分析數(shù)據(jù)的時(shí)間相關(guān)性,。
1 基于時(shí)間衰減和簇合并的聚類(lèi)處理算法（CluTA）
在分析某些類(lèi)數(shù)據(jù)時(shí)往往更加注重其近期變化帶來(lái)的影響,，時(shí)間越久遠(yuǎn)被關(guān)注的程度就越低,，如網(wǎng)絡(luò)入侵行為的分類(lèi)和趨勢(shì),、股市不斷變化的大盤(pán)信息等。為提高聚類(lèi)得到結(jié)果的精確性,，在挖掘時(shí)需考慮時(shí)間衰減的因素,。由于K均值算法聚類(lèi)的結(jié)果都是球型簇，本文通過(guò)合并相近相似簇達(dá)到輸出任意形狀簇的聚類(lèi)結(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ǔ)初次聚類(lèi)生成k個(gè)關(guān)鍵點(diǎn),采用五元組的方式存儲(chǔ)關(guān)鍵點(diǎn)信息。
定義1. 關(guān)鍵點(diǎn)
采用Kmeans方法對(duì)在t時(shí)刻到達(dá)內(nèi)存的數(shù)據(jù)塊Xt進(jìn)行聚類(lèi)得到k個(gè)關(guān)鍵點(diǎn),，關(guān)鍵點(diǎn)ri是五元組的形式,，
上述(1)表示兩簇的均值點(diǎn)距離小于或等于兩簇內(nèi)最遠(yuǎn)距離之和，相距足夠近則考慮合并簇,。但也可能出現(xiàn)兩簇相距很近仍不符合合并要求的情況,。如圖1所示，兩簇的距離足夠近,，但二者密度相差較大就不應(yīng)該再合并,。因此加上條件(2),通過(guò)計(jì)算兩簇的權(quán)重比是否相差懸殊來(lái)決定是否可以合并。若上述限定條件都符合,，則合并簇得到如圖2所示結(jié)果,。
1.3 算法分析
該算法改進(jìn)K均值聚類(lèi)算法結(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均值聚類(lèi)算法,，具有簡(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類(lèi),，每一數(shù)據(jù)有42個(gè)屬性，去除一些非數(shù)值型數(shù)據(jù)的維數(shù),，選留其中的20維做為實(shí)驗(yàn)數(shù)據(jù),。使用每類(lèi)中的5 000條中的20個(gè)屬性，打開(kāi)文件模擬數(shù)據(jù)流環(huán)境讀入數(shù)據(jù),用Kmeans算法得出初始聚類(lèi)關(guān)鍵點(diǎn)信息,，再運(yùn)用CluTA算法進(jìn)行簇合并,，最終與僅用Kmeans算法聚類(lèi)的結(jié)果精確度比較，如圖3所示,，判斷聚類(lèi)質(zhì)量的算法可參考文獻(xiàn)[5],。聚類(lèi)質(zhì)量為類(lèi)內(nèi)距離值加上類(lèi)間密度值。類(lèi)內(nèi)距離是表示該類(lèi)內(nèi)部點(diǎn)的密疏程度,，類(lèi)間密度是衡量各個(gè)類(lèi)的平均密度關(guān)系,，如圖4所示，該值較小表明聚類(lèi)簇集的類(lèi)間區(qū)分度較好,，因此二者總和越小,，表示聚類(lèi)質(zhì)量越好。
為解決使用價(jià)值隨時(shí)間衰減的一類(lèi)流數(shù)據(jù)聚類(lèi)問(wèn)題和實(shí)現(xiàn)任意形狀簇的聚類(lèi),，本文在基于傳統(tǒng)的K均值聚類(lèi)算法基礎(chǔ)上,，保留其直觀、高效的特點(diǎn),，提出了基于時(shí)間衰減的任意簇?cái)?shù)據(jù)流聚類(lèi)算法,。即在K均值算法處理得到結(jié)果的基礎(chǔ)上再考慮用時(shí)間和密度、空間距離等因素合并簇,。理論分析和實(shí)驗(yàn)結(jié)果證明該算法相對(duì)于僅用K均值算法在處理對(duì)近期價(jià)值比較關(guān)心一類(lèi)的數(shù)據(jù)時(shí)具有更精確的聚類(lèi)結(jié)果,。下一步的工作將著重于提高算法的效率和將其應(yīng)用到更廣泛的生活實(shí)踐中。
參考文獻(xiàn)
[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ù)高效密度聚類(lèi)算法[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.