一種新的數(shù)據(jù)流模糊聚類方法

孫力娟 陳小東 韓 崇 郭 劍

①（南京郵電大學(xué)計(jì)算機(jī)學(xué)院 南京 210003）

②（南京郵電大學(xué)江蘇省無(wú)線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室 南京 210003）

一種新的數(shù)據(jù)流模糊聚類方法

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

①（南京郵電大學(xué)計(jì)算機(jī)學(xué)院 南京 210003）

②（南京郵電大學(xué)江蘇省無(wú)線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室 南京 210003）

針對(duì)數(shù)據(jù)流上的聚類任務(wù)受到時(shí)間、空間限制等問題，該文提出一種基于權(quán)值衰減的數(shù)據(jù)流模糊微簇聚類算法（WDSMC）。該算法使用改進(jìn)的帶權(quán)值的模糊C均值算法進(jìn)行處理，并采用微簇結(jié)構(gòu)和權(quán)值時(shí)間衰減結(jié)構(gòu)提高聚類質(zhì)量。實(shí)驗(yàn)表明，相對(duì)于現(xiàn)有的數(shù)據(jù)流加權(quán)模糊 C均值聚類（SWFCM）算法和 StreamKM++算法而言，WDSMC算法具有更好的聚類精度。

數(shù)據(jù)挖掘；數(shù)據(jù)流；模糊C均值聚類；權(quán)值衰減；微簇聚類

1 引言

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

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

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

2 基本概念

定義1（數(shù)據(jù)流模型）： 數(shù)據(jù)流是一個(gè)帶有時(shí)間戳的多維的數(shù)據(jù)點(diǎn)集合 X1， X2，…，Xs，…。每個(gè)數(shù)據(jù)點(diǎn) Xi是一個(gè)包含d維的數(shù)據(jù)記錄，表示為 Xi=（x1，

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

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

關(guān)于 iju的取值范圍，滿足如下兩條性質(zhì)［15］：

性質(zhì)1 對(duì)于每個(gè)數(shù)據(jù)點(diǎn)jX 和簇iC，都有0≤ uij≤ 1。

性質(zhì)2 對(duì)于每個(gè)數(shù)據(jù)點(diǎn) Xj，都有

定義4（簇中心點(diǎn)）： 第i個(gè)模糊簇的中心點(diǎn) iV應(yīng)該結(jié)合隸屬度矩陣計(jì)算，其計(jì)算公式為［9］（p的含義見定義5）

定義5（代價(jià)函數(shù)/目標(biāo)函數(shù)）： 按照聚類C的誤差平方和來評(píng)價(jià)聚類的質(zhì)量，其公式為［9］

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

目標(biāo)函數(shù)J的值越小，表明聚類質(zhì)量越好。要求式（2）取值最小，結(jié)合的特點(diǎn)，可以得到隸屬度矩陣的計(jì)算［9］：

3 基于權(quán)值衰減的數(shù)據(jù)流模糊微簇聚類WDSMC算法

本文提出的基于權(quán)值衰減的數(shù)據(jù)流模糊聚類WDSMC算法是將數(shù)據(jù)流分塊處理，使用改進(jìn)的帶權(quán)值模糊 C均值算法（Advanced Weighted Fuzzy Clustering Method，AWFCM）微簇聚類分塊后的數(shù)據(jù)流，在每一部分聚類得到微簇中心點(diǎn)及其權(quán)值進(jìn)入下一部分?jǐn)?shù)據(jù)流之前，衰減前一部分?jǐn)?shù)據(jù)點(diǎn)權(quán)值，減小歷史數(shù)據(jù)對(duì)于最近階段聚類結(jié)果的影響。在處理完整個(gè)數(shù)據(jù)流之后，將得到微簇中心及其權(quán)值當(dāng)做數(shù)據(jù)點(diǎn)，再次調(diào)用AWFCM算法處理，最終得到整個(gè)數(shù)據(jù)流上的各個(gè)簇中心。

3.1 模糊C均值聚類（FCM）算法及其改進(jìn)

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

從表1可以看出，F(xiàn)CM算法的初始隸屬度函數(shù)是隨機(jī)選擇的，只要滿足性質(zhì)2即可，即所計(jì)算出的初始簇中心也是隨機(jī)的，與樣本數(shù)據(jù)點(diǎn)無(wú)關(guān)。因FCM算法是局部收斂的，所以FCM的算法性能強(qiáng)烈依賴于初始簇中心的選擇。本文針對(duì)上述FCM算法的缺陷，提出了改進(jìn)FCM算法（AFCM），如表2所示。

表1 FCM算法

表2 改進(jìn)的FCM算法（AFCM）

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

3.2 權(quán)值時(shí)間衰減與微簇結(jié)構(gòu)

數(shù)據(jù)流是按照時(shí)間順序依次到達(dá)的數(shù)據(jù)點(diǎn)。隨著時(shí)間的推進(jìn)，用戶往往更加在意最近到達(dá)的數(shù)據(jù)點(diǎn)所形成的簇。本文提出的WDSMC算法采用權(quán)值衰減結(jié)構(gòu)提高最終所形成簇的時(shí)效性。

定義 6（數(shù)據(jù)點(diǎn)權(quán)值） 在t時(shí)刻，數(shù)據(jù)點(diǎn)j的權(quán)值w定義為

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

定義7（簇權(quán)值） 在t時(shí)刻，第i個(gè)簇的權(quán)值cw定義為

即所有數(shù)據(jù)點(diǎn)在該簇上的隸屬度與權(quán)值乘積之和表示該簇的權(quán)值。每個(gè)簇的權(quán)值之所以說是隨時(shí)間衰減，是因?yàn)榇刂械臄?shù)據(jù)點(diǎn)是隨時(shí)間衰減的，由式（4）和式（5），可以得出的結(jié)論為：

性質(zhì)3 從t時(shí)刻到 1t+ 時(shí)刻，第i個(gè)簇權(quán)值cw將衰減2，即滿足式（6）：

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

3.3 帶權(quán)值的FCM算法（WFCM）

因?yàn)樵?WDSMC算法中將每個(gè)數(shù)據(jù)點(diǎn)都賦了一個(gè)隨時(shí)間衰減的權(quán)值，所以在使用 FCM算法處理每一部分的數(shù)據(jù)時(shí)必須要考慮到權(quán)值的因素。WFCM與FCM的區(qū)別在于式（1）和式（3）要加上權(quán)值的影響：

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

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

3.4 WDSMC算法框架

本節(jié)給出WDSMC數(shù)據(jù)流聚類算法框架，如圖1所示，依據(jù)數(shù)據(jù)流到達(dá)時(shí)間的次序?qū)?shù)據(jù)流分成形如 S1，S2，…，Sp的塊，數(shù)據(jù)塊的大小由主機(jī)內(nèi)存的大小決定，記數(shù)據(jù)塊 S1，S2，…，Sp中數(shù)據(jù)點(diǎn)的個(gè)數(shù)分別為n1，n2，…，np。

圖1 WDSMC算法流程圖

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

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

表3 WDSMC算法框架

表4 AWFCM算法

4 實(shí)驗(yàn)結(jié)果

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

4.1 數(shù)據(jù)集

本文采用來自真實(shí)世界的數(shù)據(jù)源，以期獲得具有實(shí)際指導(dǎo)意義的結(jié)果。所使用的數(shù)據(jù)主要來自UCI Machine Learning Repository［16］。表5總結(jié)了本文實(shí)驗(yàn)即將用到的2個(gè)數(shù)據(jù)集（數(shù)據(jù)維度不包括類標(biāo)號(hào)）：

表5 實(shí)驗(yàn)使用的數(shù)據(jù)集

4.2 算法參數(shù)

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

4.3 λ的取值分析

權(quán)值時(shí)間衰減因子λ是WDSMC算法中很重要的一個(gè)參數(shù)，它決定了歷史數(shù)據(jù)對(duì)當(dāng)前簇的影響程度。在本文的其他實(shí)驗(yàn)中，λ取一個(gè)較小的值0.125，而對(duì)于那些需要在最近的數(shù)據(jù)流上聚類的應(yīng)用中，可以適當(dāng)增大λ的值，算法具有很好的靈活性。

本文取λ的值從 0.25到 16，評(píng)估算法在Spambase數(shù)據(jù)流上的聚類效果，其中數(shù)據(jù)流的每一部分有1000個(gè)數(shù)據(jù)點(diǎn)，最后一部分有601個(gè)數(shù)據(jù)點(diǎn)，最終聚類簇個(gè)數(shù) 4m= ，微簇個(gè)數(shù) 80k= ，其余參數(shù)設(shè)置同上一節(jié)所介紹，實(shí)驗(yàn)結(jié)果圖2所示。

圖2 λ取值與代價(jià)函數(shù)的關(guān)系-

在圖 2中實(shí)線段代表最終簇中心在整個(gè)Spambase數(shù)據(jù)集上的目標(biāo)函數(shù)值，虛線段代表最終簇中心在 Spambase最后一部分上的目標(biāo)函數(shù)值。隨著λ取值的增加，算法在最近部分的數(shù)據(jù)上的代價(jià)函數(shù)越來越小，最近部分的聚類效果越來越好；而在整體數(shù)據(jù)流上計(jì)算的代價(jià)函數(shù)值不會(huì)因?yàn)棣嗽谝欢ǚ秶鷥?nèi)增加而有明顯的變大，即整體聚類質(zhì)量不會(huì)因?yàn)棣说脑龃蠖蠓档汀＿@是本文提出算法的優(yōu)勢(shì)所在，提供了一定的靈活性，可以依據(jù)具體的應(yīng)用需求選擇合適的λ值。-

4.4 -算法性能對(duì)比-

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

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

4.5 -微簇聚類最終簇-

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

圖3 Spambase數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果-

圖4 Covertype數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果-

表6列出了AWFCM算法與SAGA算法將Spambase數(shù)據(jù)集上的微簇聚類成最終簇所用的時(shí)間和聚類目標(biāo)函數(shù)對(duì)比，其中SAGA算法中的參數(shù)設(shè)置與文獻(xiàn)［17］相同。作為一種非線性優(yōu)化方-法，模擬遺傳退火算法SAGA通過大量的迭代可以達(dá)到全局最優(yōu)的搜索效果，但是需要消耗大量的時(shí)間。在表6中，對(duì)于實(shí)驗(yàn)中Spambese數(shù)據(jù)集從微簇聚類到最終簇的過程，使～用SAGA算法需要的時(shí)間是AWFCM算法的300400倍，而對(duì)聚類質(zhì)量的提升（對(duì)應(yīng)于代價(jià)函數(shù)的減?。┎蛔?1%。實(shí)驗(yàn)證明，改進(jìn)的帶權(quán)值的 FCM算法在保證聚類質(zhì)量的前提下，大大提升了算法的時(shí)間效率。

表6 在Spambase數(shù)據(jù)集上運(yùn)行時(shí)間和代價(jià)函數(shù)對(duì)比

5 結(jié)束語(yǔ)

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

［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，F(xiàn)ulin 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］ 郭躬德，李南，陳黎飛. 一種基于混合模型的數(shù)據(jù)流概念漂移檢測(cè)算法［J］. 計(jì)算機(jī)研究與發(fā)展，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］ 胡偉. 一種改進(jìn)的動(dòng)態(tài) k-均值聚類算法［J］. 計(jì)算機(jī)系統(tǒng)應(yīng)用，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］ 李子柳. 大數(shù)據(jù)實(shí)時(shí)流式聚類框架研究［D］. ［碩士論文］，中山大學(xué)，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. 范明，孟小峰. 數(shù)據(jù)挖掘：概念與技術(shù)［M］. 第3版，北京：機(jī)械工業(yè)出版社，2012：323-350.

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

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

孫力娟： 女，1963年生，博士，教授，博士生導(dǎo)師，研究方向?yàn)檠莼?jì)算、無(wú)線傳感器網(wǎng)絡(luò)和數(shù)據(jù)處理等.

陳小東： 男，1992年生，碩士生，研究方向?yàn)閿?shù)據(jù)挖掘、數(shù)據(jù)處理.

韓 崇： 男，1985年生，博士，講師，研究方向?yàn)槎嗝襟w信息處理、數(shù)據(jù)挖掘.

郭 劍： 男，1978年生，博士，副教授，碩士生導(dǎo)師，研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)、無(wú)線多媒體傳感器網(wǎng)絡(luò).

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網(wǎng)絡(luò)優(yōu)先出版

國(guó)家自然科學(xué)基金（61171053，61300239），教育部博士點(diǎn)基金（20113223110002），中國(guó)博士后科學(xué)基金（2014M551635）和江蘇省博士后科研資助計(jì)劃項(xiàng)目（1302085B）資助課題

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