摘  要： 數(shù)據(jù)挖掘的一個重要分支是數(shù)據(jù)流聚類技術?；贙均值算法的基礎提出了CluTA算法。該算法在處理用K均值方法分類得到的結果時考慮時間衰減因素和相似簇的合并，達到用戶對時間的要求并實現(xiàn)了任意形狀簇聚類。理論分析和實驗結果都表明算法具有可行性。
關鍵詞： 數(shù)據(jù)流；密度聚類；均值關鍵點；時間衰減

    數(shù)據(jù)流是指連續(xù)的、潛在無限量的、快速變化的、隨時間而至的數(shù)據(jù)元素的流。由于數(shù)據(jù)采集的快捷化和自動化，數(shù)據(jù)庫技術和互聯(lián)網(wǎng)技術的飛速發(fā)展，日常生活已經(jīng)與數(shù)據(jù)流息息相關，如網(wǎng)絡實時監(jiān)控、電子商務、衛(wèi)星遙感等。這些數(shù)據(jù)都具有流的特性。而傳統(tǒng)的數(shù)據(jù)挖掘方法需多遍掃描全部數(shù)據(jù)且數(shù)據(jù)必須以靜態(tài)形式存儲在磁盤空間里，因此用來專門處理數(shù)據(jù)流的數(shù)據(jù)處理模型和算法應運而生[1]。
    CluStream算法是經(jīng)典數(shù)據(jù)流聚類和主要算法，該算法提供了一個解決數(shù)據(jù)流聚類問題的優(yōu)秀雙層聚類方法，但由于它采用的是基于BIRCH算法的核心思想，所以僅限于得到球形聚簇結果[2]。K均值算法是基于劃分的聚類方法，采用分而治之的策略對數(shù)據(jù)分塊后再進行聚類，這樣保證算法在較小的內(nèi)存空間范圍內(nèi)獲取常數(shù)因子的近似結果[3]。該算法的缺點是K取值的不確定因素太多，影響了準確性且不能考慮被分析數(shù)據(jù)的時間相關性。
1 基于時間衰減和簇合并的聚類處理算法（CluTA）
    在分析某些類數(shù)據(jù)時往往更加注重其近期變化帶來的影響，時間越久遠被關注的程度就越低，如網(wǎng)絡入侵行為的分類和趨勢、股市不斷變化的大盤信息等。為提高聚類得到結果的精確性，在挖掘時需考慮時間衰減的因素。由于K均值算法聚類的結果都是球型簇，本文通過合并相近相似簇達到輸出任意形狀簇的聚類結果。
    本算法采用分層思想，第一層增加K均值算法得到中心點的信息，使每個中心點c中保留s(簇內(nèi)所有的點到c的距離和)、d(簇內(nèi)最遠點到c的距離)、n(簇內(nèi)所有點的個數(shù))、t(c的生成時刻)。第二層結合本算法給出的衰減函數(shù)和密度計算出關鍵點的權重；比較關鍵點的權重和距離，如果距離足夠近且權重比在允許范圍內(nèi)則合并簇。重復循環(huán)直到?jīng)]有可合并的簇，輸出最終結果。
1.1 相關定義和性質(zhì)
    假設數(shù)據(jù)以塊X1,X2,…，Xn，…的形式按序到達，每個塊內(nèi)包含m個數(shù)據(jù)點xi（xi1,xi2,…，xim）且可以在內(nèi)存中進行處理。每個數(shù)據(jù)點是一個d維向量。CluTA算法是以Kmeans為基礎初次聚類生成k個關鍵點,采用五元組的方式存儲關鍵點信息。
    定義1. 關鍵點
    采用Kmeans方法對在t時刻到達內(nèi)存的數(shù)據(jù)塊Xt進行聚類得到k個關鍵點，關鍵點ri是五元組的形式，

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

1.3 算法分析
    該算法改進K均值聚類算法結果信息，第一層運用K均值算法的計算復雜度為O(nkt)，n為數(shù)據(jù)點數(shù)目，t為循環(huán)次數(shù)，通常有k<<n和t<<n。第二層將生成的k個聚簇進行合并，計算復雜度為O(k2)，k為常數(shù)級關鍵點數(shù)目。在K均值的基礎上增加的內(nèi)存空間也非常少，僅需保存k個關鍵點和一些中間變量。因此，該算法在時間和空間復雜度上都近似于K均值聚類算法，具有簡單、高效的特點。
2 實驗分析
    算法在VC 6.0環(huán)境下采用C編寫,實驗平臺為一臺CPU 2.8 GHz、內(nèi)存1 GB、操作系統(tǒng)為Windows XP的PC機。采用了UCI的KDD CUP 1999網(wǎng)絡入侵檢測數(shù)據(jù)集。KDD CUP 1999數(shù)據(jù)集共23類，每一數(shù)據(jù)有42個屬性，去除一些非數(shù)值型數(shù)據(jù)的維數(shù)，選留其中的20維做為實驗數(shù)據(jù)。使用每類中的5 000條中的20個屬性，打開文件模擬數(shù)據(jù)流環(huán)境讀入數(shù)據(jù),用Kmeans算法得出初始聚類關鍵點信息，再運用CluTA算法進行簇合并，最終與僅用Kmeans算法聚類的結果精確度比較，如圖3所示，判斷聚類質(zhì)量的算法可參考文獻[5]。聚類質(zhì)量為類內(nèi)距離值加上類間密度值。類內(nèi)距離是表示該類內(nèi)部點的密疏程度，類間密度是衡量各個類的平均密度關系，如圖4所示，該值較小表明聚類簇集的類間區(qū)分度較好，因此二者總和越小，表示聚類質(zhì)量越好。

    為解決使用價值隨時間衰減的一類流數(shù)據(jù)聚類問題和實現(xiàn)任意形狀簇的聚類，本文在基于傳統(tǒng)的K均值聚類算法基礎上，保留其直觀、高效的特點，提出了基于時間衰減的任意簇數(shù)據(jù)流聚類算法。即在K均值算法處理得到結果的基礎上再考慮用時間和密度、空間距離等因素合并簇。理論分析和實驗結果證明該算法相對于僅用K均值算法在處理對近期價值比較關心一類的數(shù)據(jù)時具有更精確的聚類結果。下一步的工作將著重于提高算法的效率和將其應用到更廣泛的生活實踐中。
參考文獻
[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].小型微型計算機系統(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.