一種中心權值流數據聚類算法*

華 崢，杜 韜，曲守寧

（1.山東開放大學，山東 濟南，250014；2.濟南大學，山東 濟南，250022）

0 引言

近年來，數據流挖掘在網絡監測、交通流量監控與管理、電力供應管理與預測、Web 點擊流分析等領域有著巨大的應用前景[1]。與傳統靜態數據集不同，數據流的聚類分析提出了許多新的挑戰：關于自然簇的數量和形狀的先驗知識難以獲取；要求算法具有高度的靈活性，可以實時捕獲任何形狀的聚類；數據貢獻可能會隨時間不斷變化，并且變化越早，對集群的貢獻就越大[2]。

本文提出一種新的數據流聚類方法中心加權數據流聚類算法（Center-Weighted algorithm for clustering data Streams，CW-Stream）。該方法通過綜合考慮量自動確定聚類中心，并且為了提供一個更好的聚類表征，通過中心權值的迭代學習過程，為聚類中心分配權重。此外，為把握數據對象的完整狀態，本文方法以模糊隸屬度矩陣的形式保存數據對象的摘要信息，且中心權值的加入為模糊隸屬度帶來了方向性的特征。通過一系列在真實數據集上的實驗表明，CW-Stream 算法在聚類的純度和效率等方面展現了良好的性能[3]。

1 聚類算法

CW-Stream 算法為了把握數據流的瞬態特征，將中心權重與距離特征相結合，以完成對數據流環境的準確描述，然后以模糊隸屬度矩陣的形式保存數據流的摘要信息。算法不斷重復上述迭代過程，直到數據流結束或者所有的數據點被全部遍歷為止。

1.1 中心加權系數

在算法的具體執行過程中，一般關心的是當前數據的聚類情況，但如果對當前數據流的信息不敏感，算法挖掘性能和挖掘結果的精度將大大降低[4]。為了避免歷史數據對更新數據造成較大的影響，本文算法創新性地提出了微簇中心權值的計算方法。微簇中心能夠表示數據流的聚類形態，但由于歷史數據過多容易陷入局部最優現象。歷史數據與當前數據的數據特征相互補充，將過去時刻數據流隨時間延續的演化信息和新數據流融合起來，從而得到具有中心權值的最優解[5]。

假設A={A1,A2,…,Ak}是一個有界的、全部有序的集合，相應地，A=A1×A2×…×Ak}是一個k維數據空間。其中，xi=〈xi1,xi2,…,xik〉表示1 個數據點；xij表示數據點xi的第j維的值。C為整數，V=(v1,v2,…,vc)為C個聚類中心[6]。

如果是第1 次聚類請求，數據點xj(1)被劃分到C個聚類中心vi(1)，更新后的聚類中心的權值pi(1)即為第一個數據流中數據的權值和初始化聚類中心權值之和，表示為：

式中：uij為數據點xj(1)，屬于聚類中心vi(1)的模糊隸屬度；1 ≤i≤C；1 ≤j≤n。

之后，當第2 個數據流到達時，更新后的聚類中心權值為第2 個數據流的數據項的權值和更新后的聚類中心權值之和。因此，C個新的聚類中心vi(2)的權值pi(2)表示為：

式中：qj(2)=1；pi(1)為聚類中心vi(1)的權值；uij為數據點xj(2)屬于新的聚類中心vi(2)的模糊隸屬度；uii為歷史聚類中心vi(1)的模糊隸屬度。

同理，當第t 個數據流到達時，算法將新到達的數據點xj(t)和前一時刻所得到的C個新的加權聚類中心vi(t-1)，劃分成C個新的數據簇。由此可得，加權聚類中心vi(t)的權值pi(t)可以表示為：

式中：qj(t)=1；pi(t-1)為聚類中心vi(1)在(t-1)時刻的權值；uij為數據點xj(t)屬于新的聚類中心vi(t)的模糊隸屬度；uii為歷史數據中心vi(t-1)的模糊隸屬度。

由此可見，后續更新的中心權值包含了前一次數據更新得到的中心權值和新增數據對象信息，然后通過不斷迭代將數據流隨著時間不斷演化的信息融合進去。

1.2 基于中心權值的數據流微簇

為了減少歷史數據對最新數據的影響，將前一部分中的數據對象的權值在更新微簇中心點之前進行衰減[7]。考慮到不同局部區域密度的歷史狀態，引入時態權重的概念，從而能夠識別各個局部密度隨時間的變化情況[8]。

設模糊隸屬度矩陣U是一個c×n的矩陣，其中c是需要聚類的簇個數，n代表數據點的個數。uij表示第j個數據點xj屬于第i個聚類中心vi的模糊隸屬度。對于每個數據點xj和簇Ci，都有0 ≤uij≤1。對于每個數據點xj，都有定義目標函數為[9]：

通過Lagrange 乘子法得到的模糊隸屬度矩陣的定義為[10]：

其中，加權指數m(m≥1)控制隸屬度的影響，m的值越大，隸屬度的影響越大。而目標函數J的值越小，表明聚類質量越好[11]。

每一個數據點xj(t)都賦予了1 個隨時間衰減的權值，以及前一時刻得到的C個加權聚類中心vi(t-1)，加權聚類中心vi(t-1)在(t-1)時刻的權值為pi(t-1)；由此可以得到t時刻算法的聚類中心vi的迭代為：

可以看出在調節聚類中心時，各個集群內部的數據點之間盡量分布密集，不同的集群之間的分布盡量地遠離。

1.3 算法的細節實現及初始化過程

數據點Xj的綜合考慮量γj的計算方法為：

式（7）中，局部密度ρj的定義為[12]：

χ(dij-dc)函數用以判斷xj距離xi是否小于距離閾值dc，表達式為：

數據點Xj到比它局部密度高的其它數據點的最小距離為：

算法使得所選的初始化聚類中心盡可能地相互分離，聚類中心位于不同類簇，由此保證初始聚類中心的多樣性[13]。

基于上述的描述，基于中心權值的聚類算法的具體流程如下文所述。

輸入：數據流X=〈x1,x2,…,xn〉?RD

輸出：聚類中心V={vj,1 ≤i≤C}和模糊隸屬度矩陣U={uij,1 ≤i≤C,1 ≤j≤D}。

2 實驗分析

為了驗證本文CW-Stream 算法的性能，使用兩種廣泛使用的真實數據集進行實驗：KDD-CUP99數據集、Forest CoverType 數據集。

2.1 聚類質量評價

實驗對CW-Stream 算法的聚類效果進行評估，同時與HPStream 算法和CAStream 算法進行性能比較。本文采用平均聚類純度來評價聚類質量，平均聚類純度的定義如公式（11）所示[14]：

式中：K為簇的個數；為在微簇Ci中具有該微簇最主要類標號的數據點數；|Ci|為簇i中包含的所有數據點的個數。

實驗中均經過5 個單位時間，對每個單位時間內新進入的數據進行聚類，設置加權指數d=1.05。具體實驗結果如表1 所示。

表1 聚類質量評價

從實驗結果可以看出，CW-Stream 算法采用了前一時刻聚類中心的權值來重新計算中心點的權值，減少了歷史數據對當前數據的影響。HPStream 算法使用高維投影技術和衰減結構來處理高維數據流，對高維數據流確實具有很好的健壯性。CAStream 算法采用子空間聚類思想，對數據空間進行了網格化處理，能夠有效地處理高維數據流。

2.2 Rand 指數

為了公正地對各個聚類算法的性能做出合理評價，采用芮氏指標（Rand Index，RI）對數據集進行聚類劃分和數據集實際劃分結果的一致性[15]，計算公式為：

式中：N為整個數據集中數據點的總個數。

本文算法的參數設置為d=1.05，λ=0.125，n=1 980，c=8。對于每個數據集，在實驗中驗證每種算法獨立運行10 次，實驗結果如表2 所示。

表2 Rand 指數比較

從表2 可以看出，相比HPStream 算法，CWStream 算法中加入了中心權值，充分考慮了數據流不斷演化的特點。HPStream 算法中需要用戶來指定平均聚類維度，強行要求輸入固定的聚類維數必然影響真實的聚類形態分布。CAStream 算法在子空間中進行數據流聚類及其演化分析，對任意形狀分布的聚類效果較好。

3 結語

數據流作為一種特殊的數據模型廣泛存在于多種應用領域中，對數據流聚類算法提出了挑戰。如難以自動獲取簇的個數；難以發現任意形狀的簇等。因此，基于流式數據的有效處理和分析具有十分重要的意義。CW-Stream 算法劃分流式數據并進行初始化處理，得到初始聚類中心和微簇。引入中心權值，迭代更新數據流，同時考慮到模糊隸屬度矩陣的更新方向。實驗表明，算法的精度滿足了數據流挖掘的要求。

在未來的工作中，將研究劃分數據流的大小對最終聚類結果的影響，改進微簇結構，進一步提高聚類質量。此外，進一步展開相關方面的理論和實驗說明，從而更好地在實際問題中展開應用。