基于改進(jìn)QPSO的模糊C?均值聚類算法

楊照峰+時合生

摘 要： 針對模糊C?均值聚類算法容易陷入局部極值等缺陷，提出了基于改進(jìn)QPSO的模糊C?均值聚類，算法利用QPSO的優(yōu)點(diǎn)，并對量子門更新策略進(jìn)行了改進(jìn)。實(shí)驗(yàn)結(jié)果顯示該算法提高了模糊聚類算法的聚類效果以及搜索能力，在全局尋優(yōu)能力、跳出局部最優(yōu)能力、收斂速度等方面具有優(yōu)勢。

關(guān)鍵詞： 模糊C?均值聚類； 量子粒子群優(yōu)化； 聚類分析； 量子門更新策略

中圖分類號： TN711?34； TP393 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2014）07?0118?03

Fuzzy C?means clustering algorithm based on improved QPSO

YANG Zhao?feng1， SHI He?sheng2

（1. Software Engineering School， Pingdingshan University， Pingdingshan 467002， China；

2. Computer Science and Technical College， Pingdingshan University， Pingdingshan 467002， China）

Abstract： Since the fuzzy C?means clustering algorithm is easy to fall into local extremum， fuzzy C?means clustering algorithm based on the improved quantum particle swarm optimization （QPSO） is proposed. The local search ability and quantum gates update strategy were improved by making full use of the advantages of fast convergence of QPSO. The experimental results show that the algorithm improves the search ability and clustering effect of fuzzy clustering algorithm， and has superiority in the aspects of global optimization capability， jumping out of local optimum capacity and convergence rate.

Keywords： fuzzy C?means clustering； quantum particle swarm optimization； clustering analysis； quantum gates update strategy

0 引 言

模糊C?均值（Fuzzy C?Means，F(xiàn)CM）算法是目前眾多的聚類算法中應(yīng)用最廣泛且較成功的[1?2]，1974年由Dunn提出該算法[3]。該算法雖然具有收斂速度快、局部搜索能力強(qiáng)等優(yōu)點(diǎn)，但它對初始條件極為敏感。國內(nèi)外很多相關(guān)研究人員對這個問題進(jìn)行了深入的研究，如文獻(xiàn)[4]提出基于GA的聚類方法，在一定程度上解決FCM的初值敏感性問題，但是由于遺傳算法本身的缺陷，仍會出現(xiàn)未成熟收斂現(xiàn)象。

文獻(xiàn)[5]利用免疫機(jī)制改進(jìn)GA，并將C?均值算法與免疫GA有機(jī)結(jié)合，形成一種混合算法。文獻(xiàn)[6]提出了基于PSO算法的改進(jìn)模糊聚類算法（PSFC），該算法是一種實(shí)用的、速度更快、效率更高的改進(jìn)聚類算法。本文提出了基于改進(jìn)量子粒子群優(yōu)化算法的模糊C?均值聚類，充分利用量子粒子群算法收斂速度快、局部搜索能力強(qiáng)的特點(diǎn)，并對量子門更新策略進(jìn)行了改進(jìn)。

1 模糊C?均值聚類概述

將數(shù)據(jù)集[X={x1，x2，…，xn}∈Rm]分為C類，[X]中任意樣本[xk]對[i]類的隸屬度為群[n]，分類結(jié)果用一個模糊隸屬度矩陣[U={uik}∈Rm]表示，模糊C?均值聚類是通過最小化關(guān)于隸屬度矩陣[U]和聚類中心[V]的目標(biāo)函數(shù)[Jm（U，V）]來實(shí)現(xiàn)的。

如何為分類找到一個標(biāo)準(zhǔn)是一個非常關(guān)鍵的問題， 目前使用較多對于數(shù)據(jù)集[X]的劃分實(shí)際上就是求有約束條件函數(shù)[W]的最小值（最小平方誤差和）：

[W=min{W（U，P）}=mini=1c（xk∈Xi（dik）2）i-1cuik=1， 1≤k≤n]

式中[U]與[P]分別為數(shù)據(jù)集[X]的劃分矩陣與聚類中心矩陣。

[（dik）2=（xk-pi）T（xk-pi）]

得到如下公式：

[uik=1j=1cdikdjk2] （1）

其中[dlk≠0，1≤l≤c。]

[uir=1，]且對[k≠r，][uik=0；][?i，r，]有[dir=0。]

[pi=k=1n（uik）2xkk=1n（ujk）2] （2）

2 量子粒子群優(yōu)化算法簡介

1995年美國研究人員J.Kennedy以及R.C.Eberhart受鳥群覓食行為的啟發(fā)，提出了粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）[6]。粒子群優(yōu)化算法自提出以來，已經(jīng)取得了巨大的成功。目前，粒子群算法在如下領(lǐng)域得到了廣泛的應(yīng)用：故障診斷、模糊控制、生物醫(yī)學(xué)、通信網(wǎng)絡(luò)、分布式網(wǎng)絡(luò)、電子與信息、組合優(yōu)化、自動控制、規(guī)劃設(shè)計(jì)、圖像與視頻、能源規(guī)劃、神經(jīng)網(wǎng)絡(luò)、水文氣象預(yù)測、機(jī)器人、軍事安全、傳感器網(wǎng)絡(luò)、信號處理等。顯然，由于粒子群優(yōu)化簡單容易擴(kuò)展，能被不同的應(yīng)用領(lǐng)域采用[7?8]。

2004年J.Sun等人提出了量子粒子群（Quantum?behaved Particle Swarm Optimization，QPSO）[7]，主要的改進(jìn)是在標(biāo)準(zhǔn)的粒子群算法基礎(chǔ)上引入量子行為，QPSO是以DELTA勢阱為基礎(chǔ)，認(rèn)為粒子具有量子的行為，該算法的迭代公式如下[9?12]：

[mBest=1Mi=1MPi=1Mi=1MPi1，1Mi=1MPi2，…，1Mi=1MPiD] （3）

[Pd=（R1dPid+R2dPgd）（R1d+R2d）] （4）

[Xid（t+1）=Pd±β×mBestd（t）-Xid（t）×ln（1u）] （5）

式中：[mBest]為平均最優(yōu)位置；[M]為粒子的數(shù)目；[D]為粒子的維數(shù)；[Pi（Pi1，Pi2，…，Pid）]為第[i]個粒子的個體最優(yōu)位置；[Xi（Xi1，Xi2，…，Xid）]為第[i]個粒子的位置；[Pg]為全局最優(yōu)位置；[u、][R1d、][R2d]是介于（0，1）之間的隨機(jī)數(shù)， [β]稱為收縮擴(kuò)張系數(shù)。

3 基于量子粒子群優(yōu)化算法的模糊C?均值

聚類算法

3.1 量子粒子編碼

量子粒子群優(yōu)化算法是采用量子染色體對問題進(jìn)行描述的，量子染色體具體形式描述如下：

[qtj=αtj1βtj1αtj2βtj2……αtjmβtjm] （6）

式中：[m]表示量子比特的個數(shù)，[j=1，2，…，n。] 在這種編碼方式中，一條染色體能夠同時表達(dá)多個態(tài)的疊加，而傳統(tǒng)的編碼方式只能表示一個具體的狀態(tài)，所以QPSO比其他傳統(tǒng)進(jìn)化算法更容易保持種群的多樣性。

QPSO中的每個微粒的位置代表一個聚類中心的集合[Ui=（zi1，zi2，…，zik），]其中[zik（1≤k≤K）]為一個聚類中心，[K]為聚類數(shù)，如果數(shù)據(jù)集有[m]個屬性，那么[zik]為[m]維。故粒子由[zik]順序連接而成，其長度為[K×m。]

3.2 量子門更新

量子門的構(gòu)造是算法的關(guān)鍵所在。目前在QPSO中主要采用的是量子旋轉(zhuǎn)門：

[U（Δθi）=cos（Δθi）-sin（Δθi）sin（Δθi）cos（Δθi）] （7）

更新過程如下：

[α′iβ′i=U（Δθi）αiβi]

旋轉(zhuǎn)量子門示意圖如圖1所示。

圖1 旋轉(zhuǎn)量子門示意圖

一般方法是通過查詢表得到角度的設(shè)置。為了防止算法陷入早熟收斂，本文提出一種[R&Nε]門旋轉(zhuǎn)策略。[R&Nε]門由旋轉(zhuǎn)門和[Nε]門構(gòu)成。非門（Not?gate）是經(jīng)典的量子門，它的作用是交換量子比特位的參數(shù)。[Nε]門即是經(jīng)改進(jìn)的帶概率[ε]的非門，它的轉(zhuǎn)換矩陣如下所示：

[Nε：0110]with probability [ε；]

[Nε：1001]with probability [1-ε；] where [0<ε?1。]

在[R&Nε]門的作用下，量子比特Q?bit更新公式如下：

[α，β=R&Nεα，β，Δθ] （8）

where for [α，β=RΔθα，β′] and [ε=rand（）]

（1） if [ε?ε] then [α，β′=β，α′]

（2） if [ε>ε] then [α，β′=α，β′。]

3.3 算法流程

改進(jìn)QPSO算法流程如圖2所示。

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

實(shí)驗(yàn)以UCI中的3個實(shí)際數(shù)據(jù)集作為聚類對象，分別用PSO算法與FCM結(jié)合以及本文算法對數(shù)據(jù)對象進(jìn)行聚類分析。各算法的聚類中心數(shù)為其類別數(shù)。評價指標(biāo)如下：

[E=nN×100%] （9）

式中：[N]表示總對象數(shù)；[n]表示錯誤分類的對象數(shù)。實(shí)驗(yàn)結(jié)果見表1。

圖2 改進(jìn)QPSO算法流程

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

[數(shù)據(jù)集＼&算法＼&平均值＼&最小值＼&最大值＼& E /%＼&Iris＼& PSO?FCM＼&7.115 8＼&6.835 6＼& 10.890 8＼&17.7＼&本文方法＼&6.821 1＼&6.003 2＼&6.935 8＼&15.4＼&＼&Soybean?small＼&PSO?FCM＼&266.971 1＼&250.956 7＼&277.114 3＼&25.8＼&本文方法＼&220.352 8＼&212.124 5＼&244.902 1＼&17.9＼&＼&Labor?neg＼&PSO?FCM＼&141.444 7＼&132.009 1＼&144.998 0＼&22.6＼&本文方法＼&135.224 5＼&132.346 7＼&136.999 0＼&16.3＼&]

對于UCI中的3個實(shí)際數(shù)據(jù)集，本文算法聚類指標(biāo)[E]均比PSO?FCM要小，聚類正確率尤其是對于Soybean?small樣本得到了較大的提高， 本文算法的代價函數(shù)最大值遠(yuǎn)小于PSO?FCM，且平均值比PSO?FCM要小，這充分體現(xiàn)了本文改進(jìn)算法的全局尋優(yōu)能力強(qiáng)于PSO?FCM。

5 結(jié) 論

提出了基于改進(jìn)OPSO的模糊C?均值聚類，充分利用量子粒子群算法收斂速度快、局部搜索能力強(qiáng)的優(yōu)點(diǎn)的特點(diǎn)，并對量子門更新策略進(jìn)行了改進(jìn)。實(shí)驗(yàn)結(jié)果顯示該算法提高了模糊聚類算法的聚類效果以及搜索能力，在全局尋優(yōu)能力、跳出局部最優(yōu)能力、收斂速度等方面具有優(yōu)勢。

參考文獻(xiàn)

[1] ZHU L， CHUNG F L， WANG S T. Generalized fuzzy C?means clustering algorithm with improved fuzzy partitions [J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B： Cybernetics， 2009， 39（3）： 578?591.

[2] BAMI M， CAPPELLINI V， MECOCCI A. Comments on “a possibilistic approach to clustering” [J]. IEEE Transactions on Fuzzy Systems， 1996， 4（3）： 393?396.

[3] 高新波，謝維信.模糊C均值聚類算法中參數(shù)m的優(yōu)選[J].模式識別與人工智能，2000，13（1）：7?11.

[4] 歐陽，成衛(wèi)，韓逢慶.基于遺傳算法的模糊C?均值聚類算法[J].重慶大學(xué)學(xué)報(bào)：自然科學(xué)版，2004，27（8）：89?92.

[5] 孫洋，羅可.基于免疫遺傳算法的模糊C?均值聚類[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（3）：152?153.

[6] 薛麗萍，尹俊勛，紀(jì)震.基于粒子群優(yōu)化?模糊聚類的說話人識別[J].深圳大學(xué)學(xué)報(bào)：理工版，2008，25（2）：178?183.

[7] 關(guān)慶，鄧趙紅，王士同.改進(jìn)的模糊C?均值聚類算法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（10）：27?28.

[8] 劉兵，夏士雄，周勇，等.基于樣本加權(quán)的可能性模糊聚類算法[J].電子學(xué)報(bào)，2012，40（2）：371?375.

[9] 武小紅，周建江.可能性模糊C?均值聚類新算法[J].電子學(xué)報(bào)，2008，36（10）：1996?2000.

[10] 李盼池，張巧翠，楊雨.一種基于相位編碼的自適應(yīng)量子粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（23）：57?60.

[11] 向毅，鐘育彬.自適應(yīng)階段變異量子粒子群優(yōu)化算法研究[J].計(jì)算機(jī)應(yīng)用研究，2012，29（6）：2035?2039.

[12] 李棟.量子衍生多目標(biāo)進(jìn)化算法及其應(yīng)用研究[D].長沙：湖南大學(xué)，2008.

[13] 皋軍，王士同.具有特征排序功能的魯棒性模糊聚類方法[J].自動化學(xué)報(bào)，2009，35（2）：145?153.

參考文獻(xiàn)

[1] ZHU L， CHUNG F L， WANG S T. Generalized fuzzy C?means clustering algorithm with improved fuzzy partitions [J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B： Cybernetics， 2009， 39（3）： 578?591.

[2] BAMI M， CAPPELLINI V， MECOCCI A. Comments on “a possibilistic approach to clustering” [J]. IEEE Transactions on Fuzzy Systems， 1996， 4（3）： 393?396.

[3] 高新波，謝維信.模糊C均值聚類算法中參數(shù)m的優(yōu)選[J].模式識別與人工智能，2000，13（1）：7?11.

[4] 歐陽，成衛(wèi)，韓逢慶.基于遺傳算法的模糊C?均值聚類算法[J].重慶大學(xué)學(xué)報(bào)：自然科學(xué)版，2004，27（8）：89?92.

[5] 孫洋，羅可.基于免疫遺傳算法的模糊C?均值聚類[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（3）：152?153.

[6] 薛麗萍，尹俊勛，紀(jì)震.基于粒子群優(yōu)化?模糊聚類的說話人識別[J].深圳大學(xué)學(xué)報(bào)：理工版，2008，25（2）：178?183.

[7] 關(guān)慶，鄧趙紅，王士同.改進(jìn)的模糊C?均值聚類算法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（10）：27?28.

[8] 劉兵，夏士雄，周勇，等.基于樣本加權(quán)的可能性模糊聚類算法[J].電子學(xué)報(bào)，2012，40（2）：371?375.

[9] 武小紅，周建江.可能性模糊C?均值聚類新算法[J].電子學(xué)報(bào)，2008，36（10）：1996?2000.

[10] 李盼池，張巧翠，楊雨.一種基于相位編碼的自適應(yīng)量子粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（23）：57?60.

[11] 向毅，鐘育彬.自適應(yīng)階段變異量子粒子群優(yōu)化算法研究[J].計(jì)算機(jī)應(yīng)用研究，2012，29（6）：2035?2039.

[12] 李棟.量子衍生多目標(biāo)進(jìn)化算法及其應(yīng)用研究[D].長沙：湖南大學(xué)，2008.

[13] 皋軍，王士同.具有特征排序功能的魯棒性模糊聚類方法[J].自動化學(xué)報(bào)，2009，35（2）：145?153.

參考文獻(xiàn)

[1] ZHU L， CHUNG F L， WANG S T. Generalized fuzzy C?means clustering algorithm with improved fuzzy partitions [J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B： Cybernetics， 2009， 39（3）： 578?591.

[2] BAMI M， CAPPELLINI V， MECOCCI A. Comments on “a possibilistic approach to clustering” [J]. IEEE Transactions on Fuzzy Systems， 1996， 4（3）： 393?396.

[3] 高新波，謝維信.模糊C均值聚類算法中參數(shù)m的優(yōu)選[J].模式識別與人工智能，2000，13（1）：7?11.

[4] 歐陽，成衛(wèi)，韓逢慶.基于遺傳算法的模糊C?均值聚類算法[J].重慶大學(xué)學(xué)報(bào)：自然科學(xué)版，2004，27（8）：89?92.

[5] 孫洋，羅可.基于免疫遺傳算法的模糊C?均值聚類[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（3）：152?153.

[6] 薛麗萍，尹俊勛，紀(jì)震.基于粒子群優(yōu)化?模糊聚類的說話人識別[J].深圳大學(xué)學(xué)報(bào)：理工版，2008，25（2）：178?183.

[7] 關(guān)慶，鄧趙紅，王士同.改進(jìn)的模糊C?均值聚類算法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（10）：27?28.

[8] 劉兵，夏士雄，周勇，等.基于樣本加權(quán)的可能性模糊聚類算法[J].電子學(xué)報(bào)，2012，40（2）：371?375.

[9] 武小紅，周建江.可能性模糊C?均值聚類新算法[J].電子學(xué)報(bào)，2008，36（10）：1996?2000.

[10] 李盼池，張巧翠，楊雨.一種基于相位編碼的自適應(yīng)量子粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（23）：57?60.

[11] 向毅，鐘育彬.自適應(yīng)階段變異量子粒子群優(yōu)化算法研究[J].計(jì)算機(jī)應(yīng)用研究，2012，29（6）：2035?2039.

[12] 李棟.量子衍生多目標(biāo)進(jìn)化算法及其應(yīng)用研究[D].長沙：湖南大學(xué)，2008.

[13] 皋軍，王士同.具有特征排序功能的魯棒性模糊聚類方法[J].自動化學(xué)報(bào)，2009，35（2）：145?153.