吳 陳，孫 宏

（江蘇科技大學(xué)江蘇鎮(zhèn)江212003）

一種對(duì)數(shù)據(jù)流進(jìn)行聚類的改進(jìn)算法

吳 陳，孫 宏

（江蘇科技大學(xué)江蘇鎮(zhèn)江212003）

針對(duì)套用傳統(tǒng)的聚類方法對(duì)數(shù)據(jù)流的聚類是行不通的這一問(wèn)題，提出一種以遺傳模擬退火算法為基礎(chǔ)的模糊C均值聚類算法（SAGA_FCM）對(duì)數(shù)據(jù)流進(jìn)行聚類。SAGA_FCM算法有效地避免了傳統(tǒng)的模糊C均值聚類算法（FCM）的最終聚類結(jié)果依賴于其初始值的選取，也解決了其容易陷入局部最優(yōu)解的問(wèn)題。通過(guò)將SAGA_FCM算法和FCM算法聚類數(shù)據(jù)流的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比，得出采用SAGA_FCM算法聚類數(shù)據(jù)流會(huì)取得較好的效果。

模糊C均值算法；遺傳模擬退火算法；數(shù)據(jù)流；聚類

隨著互聯(lián)網(wǎng)發(fā)展的不斷深化以及大數(shù)據(jù)時(shí)代的到來(lái)，在比如網(wǎng)絡(luò)監(jiān)控、環(huán)境監(jiān)測(cè)、證券交易等眾多領(lǐng)域中出現(xiàn)的數(shù)據(jù)具有自身的某些特性，不同于傳統(tǒng)的靜態(tài)數(shù)據(jù)，我們稱其為數(shù)據(jù)流[1-5]。數(shù)據(jù)挖掘就好比從一大堆廢物中撿“寶貝”一樣，它要求我們做到從繁多的數(shù)據(jù)中找到僅對(duì)我們有實(shí)際價(jià)值的信息。我們一般采用聚類分析來(lái)對(duì)數(shù)據(jù)進(jìn)行分析和處理，所謂聚類就是按數(shù)據(jù)的相關(guān)性將其分到不同的簇中，同一簇中相關(guān)性盡可能極大，相反不同簇中相關(guān)性盡可能極小，可理解為“物以類聚”[6-7]。由于受到以下幾點(diǎn)條件的制約在聚類數(shù)據(jù)流時(shí)我們不能夠再照搬傳統(tǒng)的數(shù)據(jù)挖掘方法：數(shù)據(jù)流的產(chǎn)生方式是動(dòng)態(tài)的不停歇的，須對(duì)它進(jìn)行連續(xù)性的挖掘；沒(méi)有足夠大的空間用來(lái)存儲(chǔ)這無(wú)限的數(shù)據(jù)；數(shù)據(jù)流到達(dá)具有時(shí)間有序性，對(duì)其只能實(shí)現(xiàn)單次線性掃描；數(shù)據(jù)流的模式不斷發(fā)生變化[1，8-10]。

因此在傳統(tǒng)的聚類算法的基礎(chǔ)人們不斷地去研究如何去聚類這些類似流水一般的數(shù)據(jù)。如鼻祖Brich算法，還有如Stream算法、以及在Brich算法的基礎(chǔ)上加以改進(jìn)的CluStream算法等雖然可產(chǎn)生不錯(cuò)的聚類效果，但它們均屬于硬聚類算法，硬聚類可理解“非此即彼”，但在日常生活中我們所使用的都是些模糊概念（亦此亦彼），故這些硬聚類算法壓根不具有普遍意義[11-13]。

模糊C均值聚類算法（FCM）雖然是一種典型的模糊算法，但其本身是有一定缺陷存在的比如它很容易就會(huì)出現(xiàn)局部收斂[14]。為了避免這個(gè)問(wèn)題的困擾我們可以嘗試用一定的概率來(lái)接受一個(gè)相比較當(dāng)前解來(lái)說(shuō)不是怎么好的解，恰好遺傳模擬退火算法就具備這一優(yōu)點(diǎn)。因此文中在分析了數(shù)據(jù)流的特性以及FCM算法后，提出將基于遺傳模擬退火算法的FCM算法作用于數(shù)據(jù)流上，以達(dá)到更優(yōu)的聚類效果。

1 模糊C均值聚類算法

設(shè)X={x1,x2,...,xm}，其中m為樣本的數(shù)據(jù)總數(shù)，F(xiàn)CM算法思想便是將X進(jìn)行劃分，劃為n個(gè)不同的簇（組）（ 2≤n≤m），這n個(gè)簇分別用A={A1,A2,...,An}來(lái)進(jìn)行表示，最后須求解出能夠使目標(biāo)函數(shù)到達(dá)最小值（記為Jmin）的每個(gè)簇里的簇中心點(diǎn)。

目標(biāo)函數(shù)公式如式（1），且要滿足下面式（2）式（3）兩個(gè)約束條件：

其中μjk表示xj對(duì)于Ak的隸屬度，djk是xj到Ak的中心點(diǎn)的歐氏距離，c(＞1)為加權(quán)參數(shù)。

用式（4）、式（5）循環(huán)迭代得到滿足要求的U=[μjk]m×n和V=(v1,v2,...,vn)，其中U為相似分類的矩陣，V為各類的聚類中心。

FCM算法過(guò)程如下[15]：

步驟1設(shè)定數(shù)據(jù)集個(gè)數(shù)m，和參數(shù)c；

步驟2初始化隸屬度矩陣U；

步驟3通過(guò)式（5）來(lái)計(jì)算聚類中心V；

步驟4通過(guò)式（1）來(lái)求目標(biāo)函數(shù)值J，若J=Jmin則終止迭代；

步驟5利用式（4）計(jì)算新的U，轉(zhuǎn)到步驟3。

FCM算法對(duì)于初始化數(shù)據(jù)的依賴極強(qiáng)，且容易收斂于一個(gè)局部最優(yōu)解而一個(gè)好的聚類是要達(dá)到全局收斂的效果，因此要對(duì)其進(jìn)行改進(jìn)。

2 遺傳模擬退火算法

在群體演化的過(guò)程當(dāng)中，一些極少數(shù)的個(gè)體的適應(yīng)度和其他個(gè)體相比較的話大出來(lái)很多，所以經(jīng)過(guò)幾代人的繁衍以后，這些個(gè)體就會(huì)占據(jù)整個(gè)種群，這樣就會(huì)出現(xiàn)過(guò)早收斂這種我們并不想讓其出現(xiàn)的結(jié)果。遺傳模擬退火算法（SAGA）這一算法是將模擬退火算法（SA）和遺傳算法（GA）相融合，通過(guò)使用SA、使得GA的參數(shù)選擇更加容易，SAGA通過(guò)遺傳操作讓子代與父輩競(jìng)爭(zhēng)，子代遵循Metropolis準(zhǔn)則，從而有效地避免了早熟現(xiàn)象，且隨著個(gè)體的進(jìn)化，溫度T逐漸降低，從而提高了收斂的速度[7]。

Metropolis準(zhǔn)則：設(shè)f為產(chǎn)生的新的個(gè)體的適應(yīng)性，f,為變動(dòng)閥值，當(dāng)f,＞f，用新產(chǎn)生的個(gè)體來(lái)替代舊的個(gè)體，不然就以概率來(lái)接納新產(chǎn)生的個(gè)體。這里個(gè)體適應(yīng)度和最小目標(biāo)函數(shù)Jmin之間是一種反比關(guān)系，即。

遺傳模擬退火算法過(guò)程如圖1所示。

圖1 遺傳模擬退火算法的流程圖

遺傳算法和模擬退火算法兩者間通過(guò)去粗取精，有效地避免了傳統(tǒng)的遺傳算法的結(jié)果是早熟的這一現(xiàn)象的出現(xiàn)，與此同時(shí)也依據(jù)想要聚類信息的具體實(shí)際情況設(shè)計(jì)適應(yīng)度函數(shù)并用最佳的方式來(lái)進(jìn)行遺傳編碼，以使算法更加快速有效地收斂于全局最優(yōu)解。

3 SAGA_FCM算法用于數(shù)據(jù)流聚類的過(guò)程

由數(shù)據(jù)流的特性知其到達(dá)有一定的時(shí)間順序，故按其到達(dá)時(shí)間將數(shù)據(jù)流分成不同的塊（主機(jī)內(nèi)存決定塊的大?。?，分別用n1,n2,...,ns來(lái)表示數(shù)據(jù)塊M1,M2,...,Ms中含有數(shù)據(jù)點(diǎn)的總個(gè)數(shù)。該文中針對(duì)數(shù)據(jù)流聚類的方法的過(guò)程如下。

SAGA_FCM算法用于數(shù)據(jù)流聚類的過(guò)程：

步驟1初始化算法中的各個(gè)參數(shù)：種群大小size，最大迭代次數(shù)MAX，初始溫度T0，終止溫度Te，冷卻系數(shù)α，交叉概率pc，變異概率pm；

①若q=1，隨機(jī)的初始化c個(gè)聚類中心，轉(zhuǎn)至步驟4；

②若q＞1，轉(zhuǎn)至步驟3；

步驟3向Mq中加入Mq-1的聚類中心點(diǎn)，并將這些聚類中心點(diǎn)看作是Mq的聚類中心；

步驟4對(duì)Mq使用SAGA_FCM進(jìn)行聚類

①對(duì)種群進(jìn)行初始化，計(jì)算種群中每個(gè)個(gè)體適應(yīng)度f(wàn)k；

②設(shè)置種群迭代計(jì)數(shù)gen＝0；

③利用遺傳算法對(duì)種群進(jìn)行選擇、交叉、變異等操作，使用式（5）和式（4）計(jì)算所產(chǎn)生的新個(gè)體的聚類中心和隸屬度，以及每個(gè)各體的適應(yīng)度f(wàn)k,，若則舊的個(gè)體就會(huì)被新產(chǎn)生的個(gè)體替換掉，不然則以概率接受新個(gè)體；

大學(xué)里的跳蚤市場(chǎng)就是解決學(xué)生們的閑置物品，而跳蚤市場(chǎng)的時(shí)間地點(diǎn)由學(xué)校決定，因此有些同學(xué)不能及時(shí)參加或者是其他因素而直接放棄該次跳蚤市場(chǎng)。還有的是在不舉行跳蚤市場(chǎng)的時(shí)候，有些同學(xué)又想將手中的閑置物品交易卻找不到渠道出售，往往大多數(shù)同學(xué)會(huì)將其中的一些物品當(dāng)作廢棄品而扔進(jìn)了垃圾桶里，白白浪費(fèi)了資源。雖然有閑魚、二手交易市場(chǎng)等網(wǎng)站，但那些都是所有群體的，有些小件的商品估計(jì)郵費(fèi)都比不上，根本解決不了大學(xué)的閑置物品交易的需求，所以就需要一個(gè)便于校園閑置商品交易的平臺(tái)。

④如果gen＜MAX，則gen＝gen＋1，轉(zhuǎn)至步驟③，否則轉(zhuǎn)至步驟⑤；

⑤如果Tk＜Te，該數(shù)據(jù)塊聚類結(jié)束，返回聚類中心和隸屬度矩陣。否則執(zhí)行如下降溫操作Tk+1=αTk，轉(zhuǎn)至②；

步驟5如果p＝＝s，則輸出全局最優(yōu)解，不然則轉(zhuǎn)至步驟2。

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

本文實(shí)驗(yàn)是基于MATLAB平臺(tái)實(shí)現(xiàn)，所有實(shí)驗(yàn)都是在一個(gè)4G內(nèi)存、酷睿i5雙核CPU、操作系統(tǒng)為Windows7的主機(jī)上運(yùn)行的。

在參數(shù)設(shè)置方面，本文所提的SAGA_FCM和標(biāo)準(zhǔn)FCM中最大迭代次數(shù)MAX都設(shè)為50，目標(biāo)函數(shù)J的加權(quán)指數(shù)c=3。

由于模擬退火算法的收斂結(jié)果受冷卻系數(shù)以及初始溫度的影響相對(duì)較大，經(jīng)過(guò)試驗(yàn)分析，初始溫度定為80，冷卻系數(shù)為0.8，終止溫度定位0.2。

表1是本文實(shí)驗(yàn)所用的數(shù)據(jù)集，該文所使用的數(shù)據(jù)集主要來(lái)自UCI Machine Learning Repository。表2是SAGA_FCM和FCM在整個(gè)數(shù)據(jù)流上目標(biāo)函數(shù)的比較

表1 本文實(shí)驗(yàn)所用數(shù)據(jù)集

除了為最后一個(gè)數(shù)據(jù)塊分有601個(gè)數(shù)據(jù)點(diǎn)外其它數(shù)據(jù)塊中的數(shù)據(jù)點(diǎn)總個(gè)數(shù)均為1 000個(gè)。

表2 SAGA_FCM和FCM在整個(gè)數(shù)據(jù)流上目標(biāo)函數(shù)的比較

圖2 SAGA_FCM和FCM的目標(biāo)函數(shù)值折線圖

從圖2中可直觀的看出，SAGA_FCM的聚類效果明顯優(yōu)于FCM，從而證實(shí)了本文所提的SAGA_FCM算法比FCM算法可以尋找的更好的全局最優(yōu)解。

5 結(jié) 論

以上就是所提出的基于遺傳模擬退火算法的數(shù)據(jù)流聚類算法，稱為SAGA_FCM。SAGA_FCM是將數(shù)據(jù)流進(jìn)行分塊處理，采用一種分治的方法，且會(huì)在當(dāng)前解得鄰域中，以概率p選擇一個(gè)非全局最優(yōu)解，并繼續(xù)重復(fù)下去，從而避免了FCM算法容易陷入局部最優(yōu)的缺陷。接下來(lái)我們可以研究改變已有數(shù)據(jù)塊的大小會(huì)對(duì)聚類效果產(chǎn)生怎樣的影響，以及怎樣更好的把握控制參數(shù)的設(shè)置，提高搜索速度。

[1]孫力娟，陳小東，韓崇，等.一種新的數(shù)據(jù)流模糊聚類方法[J].電子與信息學(xué)報(bào)，2015，37（7）:1620-1625.

[2]張博，陳光，王旭.基于數(shù)據(jù)流模型的模糊聚類[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（33）:124-126.

[3]郭躬德，李南，陳黎飛.一種基于混合模型的數(shù)據(jù)流概念漂移檢測(cè)算法[J].計(jì)算機(jī)研究與發(fā)展，2014，51（4）:731-742.

[4]安鵬.數(shù)據(jù)流聚類算法的研究[D].哈爾濱:哈爾濱工業(yè)大學(xué)，2012.

[5]汪仁紅.基于聚類分析的數(shù)據(jù)流處理算法[D].重慶:重慶交通大學(xué).2013.

[6]程軍鋒.數(shù)據(jù)流挖掘技術(shù)研究[J].洛陽(yáng)師范學(xué)院學(xué)報(bào)，2014，33（2）:37-39.

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

[8]張丹丹.面向數(shù)據(jù)流挖掘的分類和聚類算法研究[D].北京:北京交通大學(xué)，2014.

[9]徐天音.數(shù)據(jù)流挖掘中的聚類方法綜述[D].南京:南京大學(xué)，2010.

[10]江楠，徐秦.數(shù)據(jù)流聚類算法在數(shù)據(jù)處理中的應(yīng)用[J].電子科技，2015，28（1）:155-157.

[11]李子柳.大數(shù)據(jù)實(shí)時(shí)流式聚類處理框架研究[D].廣州:中山大學(xué)，2013.

[12]林輝.改進(jìn)模糊聚類在數(shù)據(jù)流中的應(yīng)用[J].河南科學(xué)，2012，30（9）:1243-1245.

[13]胡偉.一種改進(jìn)的動(dòng)態(tài)k-均值聚類算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2013，22（5）:116-121.

[14]潘國(guó)濤.數(shù)據(jù)流聚類算法研究[D].浙江:浙江工業(yè)大學(xué)，2011.

[15]Jiawei H，Micheline K Jian P.范明，孟小峰.數(shù)據(jù)挖掘:概念與技術(shù)[M].3版，北京:機(jī)械工業(yè)出版社，2012.

An optimized algorithm for data stream clustering

WU Chen，SUN Hong
（Jiangsu University of Science and Technology，Zhenjiang212003，China）

Due to data stream cannot be clustered by using the traditional clustering methods，raising a data stream clustering method，which is based on Simulated Annealing Genetic Algorithm Fuzzy C Means（SAGA_FCM），is proposed.The method proposed in the current work effectively avoid the disadvantages of traditional FCM method，which relies on the initial values.The method also avoid the local optimization problems.In the current work，the data stream clustering algorithms based on SAGA_FCM and FCM are compared.Based on experimental observations，algorithm SAGA_FCM proposed in the current work achieves better clustering effects.

fuzzy C-means；simulated annealing genetic algorithm；data stream；clustering

TN0

A

1674-6236（2017）22-0023-03

2016-09-02稿件編號(hào)：201609013

吳陳（1962—），男，湖北武漢人，博士。研究方向：數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)。