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

吳 陳，孫 宏

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

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

吳 陳，孫 宏

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

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

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

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

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

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

1 模糊C均值聚類算法

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

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

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

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

FCM算法過程如下[15]：

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

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

步驟3通過式（5）來計算聚類中心V；

步驟4通過式（1）來求目標函數(shù)值J，若J=Jmin則終止迭代；

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

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

2 遺傳模擬退火算法

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

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

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

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

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

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

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

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

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

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

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

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

步驟4對Mq使用SAGA_FCM進行聚類

①對種群進行初始化，計算種群中每個個體適應度fk；

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

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

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

④如果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 實驗結(jié)果

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

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

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

表1是本文實驗所用的數(shù)據(jù)集，該文所使用的數(shù)據(jù)集主要來自UCI Machine Learning Repository。表2是SAGA_FCM和FCM在整個數(shù)據(jù)流上目標函數(shù)的比較

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

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

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

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

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

5 結(jié) 論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[15]Jiawei H，Micheline K Jian P.范明，孟小峰.數(shù)據(jù)挖掘:概念與技術(shù)[M].3版，北京:機械工業(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稿件編號：201609013

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