一種新的數據流模糊聚類方法

孫力娟 陳小東 韓 崇 郭 劍

①（南京郵電大學計算機學院 南京 210003）

②（南京郵電大學江蘇省無線傳感網高技術研究重點實驗室 南京 210003）

一種新的數據流模糊聚類方法

孫力娟*①②陳小東①韓 崇①郭 劍①②

①（南京郵電大學計算機學院 南京 210003）

②（南京郵電大學江蘇省無線傳感網高技術研究重點實驗室 南京 210003）

針對數據流上的聚類任務受到時間、空間限制等問題，該文提出一種基于權值衰減的數據流模糊微簇聚類算法（WDSMC）。該算法使用改進的帶權值的模糊C均值算法進行處理，并采用微簇結構和權值時間衰減結構提高聚類質量。實驗表明，相對于現有的數據流加權模糊 C均值聚類（SWFCM）算法和 StreamKM++算法而言，WDSMC算法具有更好的聚類精度。

數據挖掘；數據流；模糊C均值聚類；權值衰減；微簇聚類

1 引言

隨著計算機、通信技術的發展以及大數據的到來，在如傳感器網絡、氣象分析、股票市場、計算機網絡入侵檢測等眾多應用領域產生了一些海量、高速、動態到達的數據，這些連續到達的數據被稱之為數據流。傳統的數據挖掘一般是建立在數據集是有限的，由靜態概率分布產生并能夠在內存隨機存取的基礎之上。但是對于數據流而言，傳統處理靜態數據集上的挖掘算法受到如下條件限制［1］：（1）數據對象是連續不斷到達的；（2）無法控制數據對象的處理順序；（3）數據流的大小是沒有邊界的；（4）數據對象被處理完后就會被丟棄。在實際處理時，可以使用備忘機制將部分數據保存一段時間后再丟棄；（5）數據可能是動態分布的而非單一的靜態分布。聚類分析在數據挖掘領域中扮演一個重要的角色。聚類是一個把數據對象劃分成多個組或簇的過程，使得簇內的對象具有很高的相似性，但與其他簇中的對象很不相似［2］。

文獻［3］中提出的Brich算法是最早提出的可以用于數據流的聚類算法，選擇正確的參數對 Brich算法實現效率很重要，需要專業領域的知識。文獻［4］提出一種稱為Clustream的數據流聚類算法。它將整個聚類過程分成了兩個部分：在線部分和離線部分。在線部分通過設定好的刪除和合并原則增量更新微簇的特征向量。離線部分使用改進的 K-means算法將微簇聚類成最終的簇，通過傾斜的時間窗口可以在用戶指定的不同時間粒度內發現簇。文獻［5］和文獻［6］所提出基于密度的數據流聚類算法，能夠得到任意形狀的簇結構，但不能隨著數據流的變化而動態改變，也無法在多種層次粒度下對數據流進行聚類。文獻［7］提出的StreamKM++算法是一種使用樹結構和桶結構的數據流聚類方法。該算法將數據點不斷放入桶中，當兩個桶滿時，通過調用 Coreset樹將桶合并，以此類推，最后將得到的數據點使用kmean++［8］算法合并成簇中心。

上述文獻中的算法都屬于是硬聚類算法，即每一個數據點不是完全屬于這一個簇，就完全屬于另一個簇。這種算法不具有一般意義，因為在模糊邏輯的思想中，一個數據點可能同時是許多簇的成員。文獻［9］提出的模糊C均值（Fuzzy C-Means，FCM）算法是數據集上的模糊聚類算法，通過不斷迭代計算簇中心和隸屬度矩陣，求解目標函數的最小值。數據流權值模糊 C均值［10］（Stream Weight Fuzzy C-Means，SWFCM）算法將FCM擴展到數據流上，由于該算法每部分僅保留簇中心點及其權值，相對于原始數據信息丟失量過大，聚類的效果并不是十分理想。針對數據流在不同時間段可能形成不同聚類模式的問題，文獻［11～13］提出了在數據流處理過程中可能出現的概念漂移檢測和處理方法。文獻［14］使用一種延遲處理的方法解決數據流聚類中的孤立點檢測問題。在數據流的進化過程中，用戶可能對最近到達的數據流更感興趣，而 Brich，StreamKM++，SWFCM等算法都沒有考慮過這個問題。本文在研究了一系列聚類算法基礎上，提出了一種基于權值衰減的數據流模糊微簇聚類算法（Weight Decay Streaming Micro Clustering，WDSMC），使用微簇結構提高聚類準確性，使用權值時間衰減結構降低歷史數據的影響。

2 基本概念

定義1（數據流模型）： 數據流是一個帶有時間戳的多維的數據點集合 X1， X2，…，Xs，…。每個數據點 Xi是一個包含d維的數據記錄，表示為 Xi=（x1，

定義 2（模糊簇）： 給定一個數據X集 = ｛X1， X2，…，Xn｝，模糊簇 Cj是X的一個子集，它允許X中每個數據點都具有一個屬于jC 的0到1之間的隸屬度［15］。

定義 3（隸屬度矩陣）： 隸屬度矩陣U是一個m n× 的矩陣，其中m是需要聚類的簇個數，n是數據點的個數，iju表示第jX 在模糊簇iC 中所占的比重。

關于 iju的取值范圍，滿足如下兩條性質［15］：

性質1 對于每個數據點jX 和簇iC，都有0≤ uij≤ 1。

性質2 對于每個數據點 Xj，都有

定義4（簇中心點）： 第i個模糊簇的中心點 iV應該結合隸屬度矩陣計算，其計算公式為［9］（p的含義見定義5）

定義5（代價函數/目標函數）： 按照聚類C的誤差平方和來評價聚類的質量，其公式為［9］

其中，加權指數p（ 1p≥ ）控制隸屬度的影響。p的值越大，隸屬度的影響越大； dji=| |Xj-Vi||表示數據點jX 與第i個簇的中心iV的歐式空間距離。

目標函數J的值越小，表明聚類質量越好。要求式（2）取值最小，結合的特點，可以得到隸屬度矩陣的計算［9］：

3 基于權值衰減的數據流模糊微簇聚類WDSMC算法

本文提出的基于權值衰減的數據流模糊聚類WDSMC算法是將數據流分塊處理，使用改進的帶權值模糊 C均值算法（Advanced Weighted Fuzzy Clustering Method，AWFCM）微簇聚類分塊后的數據流，在每一部分聚類得到微簇中心點及其權值進入下一部分數據流之前，衰減前一部分數據點權值，減小歷史數據對于最近階段聚類結果的影響。在處理完整個數據流之后，將得到微簇中心及其權值當做數據點，再次調用AWFCM算法處理，最終得到整個數據流上的各個簇中心。

3.1 模糊C均值聚類（FCM）算法及其改進

FCM［9］是一種模糊聚類算法，其算法步驟如表1所示。

從表1可以看出，FCM算法的初始隸屬度函數是隨機選擇的，只要滿足性質2即可，即所計算出的初始簇中心也是隨機的，與樣本數據點無關。因FCM算法是局部收斂的，所以FCM的算法性能強烈依賴于初始簇中心的選擇。本文針對上述FCM算法的缺陷，提出了改進FCM算法（AFCM），如表2所示。

表1 FCM算法

表2 改進的FCM算法（AFCM）

從表2中可以看出，AFCM選擇距離比較遠的數據點作為初始簇中心，這符合簇內對象具有很高相似性，而簇間對象相似性低的要求。降低算法陷入局部收斂的概率，提高聚類質量。為了不陷入局部最優解中，WDSMC算法多次獨立調用AFCM算法處理數據流的第1部分，選取使得目標函數值最小的微簇中心及其權值進入數據流的下一部分。而對于數據流的其余部分，上一部分聚類得到微簇中心點就作為下一部分的初始微簇中心點，從而加快收斂速度。

3.2 權值時間衰減與微簇結構

數據流是按照時間順序依次到達的數據點。隨著時間的推進，用戶往往更加在意最近到達的數據點所形成的簇。本文提出的WDSMC算法采用權值衰減結構提高最終所形成簇的時效性。

定義 6（數據點權值） 在t時刻，數據點j的權值w定義為

其中λ是衰減因子，dt是數據點到達的時刻。最近到達的數據點的權值為 1，上一部分的數據點權值為2λ-，依次類推。通過給每一個數據附加一個隨時間衰減的權值，降低歷史數據的影響。由式（4）可見，λ的取值越大，舊的數據衰減的越快，對最終簇的形成影響越小。

定義7（簇權值） 在t時刻，第i個簇的權值cw定義為

即所有數據點在該簇上的隸屬度與權值乘積之和表示該簇的權值。每個簇的權值之所以說是隨時間衰減，是因為簇中的數據點是隨時間衰減的，由式（4）和式（5），可以得出的結論為：

性質3 從t時刻到 1t+ 時刻，第i個簇權值cw將衰減2，即滿足式（6）：

在數據流分塊處理過程中，如果僅僅把m個簇的中心點和權值傳遞到下一部分的數據流中，由于包含的原始數據點信息太少，影響到聚類質量。在WDSMC算法中，每部分按更大的簇個數k進行聚類，稱之為微簇。使用微簇可以保留更多的簇中心點和權值，最后使用AWFCM算法將微簇聚類成最終的簇。

3.3 帶權值的FCM算法（WFCM）

因為在 WDSMC算法中將每個數據點都賦了一個隨時間衰減的權值，所以在使用 FCM算法處理每一部分的數據時必須要考慮到權值的因素。WFCM與FCM的區別在于式（1）和式（3）要加上權值的影響：

式（1）需要變換為式（7）：

式（2）需要變換為式（8）：

3.4 WDSMC算法框架

本節給出WDSMC數據流聚類算法框架，如圖1所示，依據數據流到達時間的次序將數據流分成形如 S1，S2，…，Sp的塊，數據塊的大小由主機內存的大小決定，記數據塊 S1，S2，…，Sp中數據點的個數分別為n1，n2，…，np。

圖1 WDSMC算法流程圖

每一部分處理過程如下：新到達的數據點的權值記為 1，上一部分計算得到的微簇中心及其權值也當作數據點處理，并使用式（6）對上一部分微簇權值進行衰減處理；依據式（3）計算隸屬度，利用式（7）和式（5）計算更新微簇中心及其權值；通過不斷地的迭代，使得式（8）達到最小或者到達到某一指定迭代次數。WDSMC算法框架偽代碼如表3所示。

在表 3中數據塊 Sq（q＞1）的處理過程中，是將Sq-1中的微簇中心當作一般的數據點，與Sq中的新的數據點一起聚類。也就是說，算法中所用到的各個方程式中，其數據點個數n是Sq（q＞1）中數據點個數與1qS-中微簇個數之和，即滿足：n=nq+k。如何通過這k個微簇中心點及其權值得到最終的m個用戶需要的簇呢？本文使用表4所示的帶權值模糊C均值算法AWFCM來完成該任務。

表3 WDSMC算法框架

表4 AWFCM算法

4 實驗結果

本文使用Matlab實現了WDSCM算法，同時實現了用來做比較分析的 SWFCM［10］算法（Matlab實現）和 StreamKM++［7］算法（Microsoft Visual C++實現）。所有的實驗都是在一個2G內存、酷睿2雙核CPU、操作系統為Windows 7的主機上運行的。SWFCM算法和StreamKM++算是兩種常見的數據流聚類算法，其中SWFCM屬于模糊聚類算法，而StreamKM++屬于硬聚類算法。所有實驗的聚類質量評價標準是依據式（2）得到的，即由數據點與簇中心的距離的平方與隸屬度乘積之和所決定。

4.1 數據集

本文采用來自真實世界的數據源，以期獲得具有實際指導意義的結果。所使用的數據主要來自UCI Machine Learning Repository［16］。表5總結了本文實驗即將用到的2個數據集（數據維度不包括類標號）：

表5 實驗使用的數據集

4.2 算法參數

本小節主要介紹 WDSCM以及將要做對比的SWFCM，StreamKM++算法的一些基本的參數設置。StreamKM++所有參數與文獻［9］中介紹的一樣。SWFCM算法和WDSCM算法在使用FCM或其改進時，最大迭代次數都為50次；計算目標函數的加權指數 3p= ；目標函數達到收斂條件滿足其前后值差的絕對值小于10-6。若非特別說明，WDSCM算法的權值時間衰減因子設為 λ= 0.125，微簇個數設為 400k= 。在從微簇得到最終簇的過程中，采用5次獨立調用改進的帶權值的FCM算法。在處理數據流第 1部分時也是采用 5次獨立調用改進的FCM，降低第1部分初始微簇中心隨機選擇帶來的誤差。

4.3 λ的取值分析

權值時間衰減因子λ是WDSMC算法中很重要的一個參數，它決定了歷史數據對當前簇的影響程度。在本文的其他實驗中，λ取一個較小的值0.125，而對于那些需要在最近的數據流上聚類的應用中，可以適當增大λ的值，算法具有很好的靈活性。

本文取λ的值從 0.25到 16，評估算法在Spambase數據流上的聚類效果，其中數據流的每一部分有1000個數據點，最后一部分有601個數據點，最終聚類簇個數 4m= ，微簇個數 80k= ，其余參數設置同上一節所介紹，實驗結果圖2所示。

圖2 λ取值與代價函數的關系-

在圖 2中實線段代表最終簇中心在整個Spambase數據集上的目標函數值，虛線段代表最終簇中心在 Spambase最后一部分上的目標函數值。隨著λ取值的增加，算法在最近部分的數據上的代價函數越來越小，最近部分的聚類效果越來越好；而在整體數據流上計算的代價函數值不會因為λ在一定范圍內增加而有明顯的變大，即整體聚類質量不會因為λ的增大而大幅降低。這是本文提出算法的優勢所在，提供了一定的靈活性，可以依據具體的應用需求選擇合適的λ值。-

4.4 -算法性能對比-

由于是在整個數據集上計算代價函數，為公平起見，在與SWFCM和StreamKM++算法做性能對比時，本文算法暫不考慮權值時間衰減函數的影響，即 0λ= 。每種算法下的聚類代價函數如圖 3和圖4所示，由于StreamKM++算法是一種硬聚類方法，其模糊聚類下的代價函數是通過將其聚類后的簇中心和原數據集代入式（3）和式（2）所得到的。實驗發現，雖然SWFCM算法與StreamKM++算法和WDSMC算法相比在運行時間上是較好的，但是其聚類質量（代價函數越小，聚類質量越高）卻不如另外兩種算法，特別是隨著最終簇個數的增加，與后兩種算法之間的差距更加明顯。-

與SWFCM和StreamKM++算法相比，本文算法還有如下兩點優勢：（1）由于本文算法在第1步使用微簇聚類，不需要用戶事先指定最終簇的個數。因此可以像Clustream算法一樣，將聚類過程分成在線和離線兩個部分，只要保留微簇中心及其權值，就可適應聚類成不同最終簇個數的需求。使用微簇即提高了聚類的精確性，又減少了在修改簇個數時需要重新聚類的麻煩。（2）本文算法可以根據需要，適當增大λ值，減小歷史數據對聚類的影響，適用于實時性要求高的業務。-

4.5 -微簇聚類最終簇-

在本文前面的實驗中，將數據流挖掘得到的微簇二次聚類成最終簇時使用的是表 4所示的AWFCM算法。本節考慮一種不同的微簇聚類成最終簇的方式———遺傳模擬退火算法（Simulated- Annealing Genetic Algorithm，SAGA）［17］。該算法將遺傳算法和模擬退火算法相結合用于聚類分析，是一種非線性的全局最優化搜索方法，通過不斷嘗試跳出局部最優解的途徑得到優化問題的全局最優解，相對而言FCM算法以及AFCM算法都是一種局部最優搜索方法，故使用該算法對比本文所提出的AFCM算法的聚類效果。-

圖3 Spambase數據集上實驗結果-

圖4 Covertype數據集上的實驗結果-

表6列出了AWFCM算法與SAGA算法將Spambase數據集上的微簇聚類成最終簇所用的時間和聚類目標函數對比，其中SAGA算法中的參數設置與文獻［17］相同。作為一種非線性優化方-法，模擬遺傳退火算法SAGA通過大量的迭代可以達到全局最優的搜索效果，但是需要消耗大量的時間。在表6中，對于實驗中Spambese數據集從微簇聚類到最終簇的過程，使～用SAGA算法需要的時間是AWFCM算法的300400倍，而對聚類質量的提升（對應于代價函數的減小）不足 1%。實驗證明，改進的帶權值的 FCM算法在保證聚類質量的前提下，大大提升了算法的時間效率。

表6 在Spambase數據集上運行時間和代價函數對比

5 結束語

本文提出了一種新的數據流模糊聚類算法。該算法使用微簇結構保存最終聚類所需要的信息，提高聚類質量和自適應最終簇的個數；使用權值時間衰減結構降低歷史數據對聚類的影響。通過對不同數據集進行實驗表明，本文所提出的WDSCM算法相對于StreamKM++和SWFCM算法而言具有更好的整體聚類效果。在微簇聚類最終簇的過程中分別使用遺傳模擬退火算法SAGA和改進的帶權值的FCM算法對比算法性能。接下來的工作方向可以包括以下主題：探究每部分數據塊大小變化對最終聚類效果的影響；改進微簇結構，以進一步提高聚類質量；關注不同時間段數據流簇的演化情況和在算法加入噪聲點的檢測處理過程等。

［1］ Jonathan A S，Elaine R F，Rodrigo C B，et al.. Data stream clustering：a survey［J］. ACM Computing Surveys，2013，46（1）：13：1-13：31.

［2］ Shifei D，Fulin W，Jun Q，et al.. Research on data stream clustering algorithms［J］. Artificial Intelligence Review，2013，43（4）：593-600.

［3］ Tian Z，Raghu R，and Miron L. BIRCH：an efficient data clustering method for very large databases［C］. Proceedings of the ACM SIGMOD International Conference on Management of Data，New York，USA，1996：103-114.

［4］ Aggarwal C C，Han J，and Yu P S. A framework for clustering evolving data streams［C］. Proceedings of the 29th Conference on Very Large Data Bases，Berlin，Germany，2003：81-92.

［5］ Chen Y and Tu L. Density-based clustering for real-time stream data［C］. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，New York，USA，2007：133-142.

［6］ Cao F，Ester M，Qian W， et al.. Density-based clustering over an evolving data stream with noise［C］. Proceedings of the 16th SIAM International Conference on Data Mining，Maryland，USA，2006：328-339.

［7］ Ackermann M R，M?rtens M，Raupach C，et al.. StreamKM ++：a clustering algorithm for data streams［J］. Journal of Experimental Algorithmics，2012，17（1）：2-4.

［8］ Arthur D and Vassilvitskii S. K-means++：the advantages of careful seeding［C］. Proceedings of the 2007 ACM-SIAM Symposium on Discrete Algorithm，New Orleans，USA，2007：1027-1035.

［9］ Baraldi A and Blonda P. A survey of fuzzy clustering algorithms for pattern recognition［J］. IEEE Transactions on Systems，Man， and Cybernetics， Part B： Cybernetics，1999，29（6）：778-785.

［10］ Renxia W，Xiaoya Y，and Xiaoke S. A weighted fuzzy clustering algorithm for data stream［C］. Proceedings of the 2008 ISECS International Colloquium on Computing，Communication，Control，and Management，Guangzhou，China， 2008：360-364.

［11］ 郭躬德，李南，陳黎飛. 一種基于混合模型的數據流概念漂移檢測算法［J］. 計算機研究與發展，2014，51（4）：731-742.

Guo Gong-de，Li Nan，and Chen Li-fei. Concept drift detection for data stream based on mixture model［J］. Journal of Computer Research and Development，2014，51（4）：731-742.

［12］ 胡偉. 一種改進的動態 k-均值聚類算法［J］. 計算機系統應用，2013，22（5）：116-121.

Hu Wei. Research and realization of a web information extraction and knowledge presentation system［J］. Application of Computer System，2013，22（5）：116-121.

［13］ 李子柳. 大數據實時流式聚類框架研究［D］. ［碩士論文］，中山大學，2013. Li Zi-liu. A framework for real time stream clustering of big data［D］. ［Master dissertation］，Sun Yat-sen University，2013.

［14］ Hossein M K，Suhaimi I，and Javad H. Outlier detection in stream data by clustering method［J］. International Journal of Advanced Computer Science and Information Technology，2013，2（3）：25-34.

［15］ Jiawei H，Micheline K，Jian P. 范明，孟小峰. 數據挖掘：概念與技術［M］. 第3版，北京：機械工業出版社，2012：323-350.

［16］ David Aha. UCI Machine Learning Repository［OL］. https：// archive.ics.uci.edu/ml，2014.

［17］ 史峰，王輝，郁磊，等. Matlab智能算法：30個案例分析［M］.北京：北京航天航空大學出版社，2011：188-196.

孫力娟： 女，1963年生，博士，教授，博士生導師，研究方向為演化計算、無線傳感器網絡和數據處理等.

陳小東： 男，1992年生，碩士生，研究方向為數據挖掘、數據處理.

韓 崇： 男，1985年生，博士，講師，研究方向為多媒體信息處理、數據挖掘.

郭 劍： 男，1978年生，博士，副教授，碩士生導師，研究方向為無線傳感器網絡、無線多媒體傳感器網絡.

New Fuzzy-Clustering Algorithm for Data Stream

Sun Li-juan①②Chen Xiao-dong①Han Chong①Guo Jian①②

①（College of Computer，Nanjing University of Posts and Telecommunications，Nanjing 210003，China）
②（Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks，Nanjing University of Posts and Telecommunications，Nanjing 210003，China）

There is a great challenge in the data stream clustering due to a limitation of time and space. In order to solve this problem，a new fuzzy-clustering algorithm，called Weight Decay Streaming Micro Clustering （WDSMC），is presented in this paper. The algorithm uses a reformed weighted Fuzzy C-Means （FCM） algorithm，and improves the quality of clustering by the structures of micro-clusters and weight-decay. Experimental results show that this algorithm has better accuracy than Stream Weight Fuzzy C-Means （SWFCM） and StreamKM++ algorithm.

Data mining；Data stream；Fuzzy C-Means （FCM）；Weight decay；Micro-clustering

TP301

A

1009-5896（2015）07-1620-06

10.11999/JEIT141415

2014-11-05收到，2015-03-20改回，2015-06-01網絡優先出版

國家自然科學基金（61171053，61300239），教育部博士點基金（20113223110002），中國博士后科學基金（2014M551635）和江蘇省博士后科研資助計劃項目（1302085B）資助課題

*通信作者：孫力娟 sunlj@njupt.edu.cn