摘 要： 數據挖掘的一個重要分支是數據流聚類技術。基于K均值算法的基礎提出了CluTA算法。該算法在處理用K均值方法分類得到的結果時考慮時間衰減因素和相似簇的合并，達到用戶對時間的要求并實現了任意形狀簇聚類。理論分析和實驗結果都表明算法具有可行性。
關鍵詞： 數據流；密度聚類；均值關鍵點；時間衰減
數據流是指連續的、潛在無限量的、快速變化的、隨時間而至的數據元素的流。由于數據采集的快捷化和自動化，數據庫技術和互聯網技術的飛速發展，日常生活已經與數據流息息相關，如網絡實時監控、電子商務、衛星遙感等。這些數據都具有流的特性。而傳統的數據挖掘方法需多遍掃描全部數據且數據必須以靜態形式存儲在磁盤空間里，因此用來專門處理數據流的數據處理模型和算法應運而生[1]。
CluStream算法是經典數據流聚類和主要算法，該算法提供了一個解決數據流聚類問題的優秀雙層聚類方法，但由于它采用的是基于BIRCH算法的核心思想，所以僅限于得到球形聚簇結果[2]。K均值算法是基于劃分的聚類方法，采用分而治之的策略對數據分塊后再進行聚類，這樣保證算法在較小的內存空間范圍內獲取常數因子的近似結果[3]。該算法的缺點是K取值的不確定因素太多，影響了準確性且不能考慮被分析數據的時間相關性。
1 基于時間衰減和簇合并的聚類處理算法（CluTA）
在分析某些類數據時往往更加注重其近期變化帶來的影響，時間越久遠被關注的程度就越低，如網絡入侵行為的分類和趨勢、股市不斷變化的大盤信息等。為提高聚類得到結果的精確性，在挖掘時需考慮時間衰減的因素。由于K均值算法聚類的結果都是球型簇，本文通過合并相近相似簇達到輸出任意形狀簇的聚類結果。
本算法采用分層思想，第一層增加K均值算法得到中心點的信息，使每個中心點c中保留s(簇內所有的點到c的距離和)、d(簇內最遠點到c的距離)、n(簇內所有點的個數)、t(c的生成時刻)。第二層結合本算法給出的衰減函數和密度計算出關鍵點的權重；比較關鍵點的權重和距離，如果距離足夠近且權重比在允許范圍內則合并簇。重復循環直到沒有可合并的簇，輸出最終結果。
1.1 相關定義和性質
假設數據以塊X1,X2,…，Xn，…的形式按序到達，每個塊內包含m個數據點xi（xi1,xi2,…，xim）且可以在內存中進行處理。每個數據點是一個d維向量。CluTA算法是以Kmeans為基礎初次聚類生成k個關鍵點,采用五元組的方式存儲關鍵點信息。
定義1. 關鍵點
采用Kmeans方法對在t時刻到達內存的數據塊Xt進行聚類得到k個關鍵點，關鍵點ri是五元組的形式，
上述(1)表示兩簇的均值點距離小于或等于兩簇內最遠距離之和，相距足夠近則考慮合并簇。但也可能出現兩簇相距很近仍不符合合并要求的情況。如圖1所示，兩簇的距離足夠近，但二者密度相差較大就不應該再合并。因此加上條件(2),通過計算兩簇的權重比是否相差懸殊來決定是否可以合并。若上述限定條件都符合，則合并簇得到如圖2所示結果。
1.3 算法分析
該算法改進K均值聚類算法結果信息，第一層運用K均值算法的計算復雜度為O(nkt)，n為數據點數目，t為循環次數，通常有k<<n和t<<n。第二層將生成的k個聚簇進行合并，計算復雜度為O(k2)，k為常數級關鍵點數目。在K均值的基礎上增加的內存空間也非常少，僅需保存k個關鍵點和一些中間變量。因此，該算法在時間和空間復雜度上都近似于K均值聚類算法，具有簡單、高效的特點。
2 實驗分析
算法在VC 6.0環境下采用C編寫,實驗平臺為一臺CPU 2.8 GHz、內存1 GB、操作系統為Windows XP的PC機。采用了UCI的KDD CUP 1999網絡入侵檢測數據集。KDD CUP 1999數據集共23類，每一數據有42個屬性，去除一些非數值型數據的維數，選留其中的20維做為實驗數據。使用每類中的5 000條中的20個屬性，打開文件模擬數據流環境讀入數據,用Kmeans算法得出初始聚類關鍵點信息，再運用CluTA算法進行簇合并，最終與僅用Kmeans算法聚類的結果精確度比較，如圖3所示，判斷聚類質量的算法可參考文獻[5]。聚類質量為類內距離值加上類間密度值。類內距離是表示該類內部點的密疏程度，類間密度是衡量各個類的平均密度關系，如圖4所示，該值較小表明聚類簇集的類間區分度較好，因此二者總和越小，表示聚類質量越好。
為解決使用價值隨時間衰減的一類流數據聚類問題和實現任意形狀簇的聚類，本文在基于傳統的K均值聚類算法基礎上，保留其直觀、高效的特點，提出了基于時間衰減的任意簇數據流聚類算法。即在K均值算法處理得到結果的基礎上再考慮用時間和密度、空間距離等因素合并簇。理論分析和實驗結果證明該算法相對于僅用K均值算法在處理對近期價值比較關心一類的數據時具有更精確的聚類結果。下一步的工作將著重于提高算法的效率和將其應用到更廣泛的生活實踐中。
參考文獻
[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均值分區的流數據高效密度聚類算法[J].小型微型計算機系統，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.