基于改進QPSO的模糊C?均值聚類算法

楊照峰+時合生

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

關鍵詞： 模糊C?均值聚類； 量子粒子群優化； 聚類分析； 量子門更新策略

中圖分類號： TN711?34； TP393 文獻標識碼： 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，FCM）算法是目前眾多的聚類算法中應用最廣泛且較成功的[1?2]，1974年由Dunn提出該算法[3]。該算法雖然具有收斂速度快、局部搜索能力強等優點，但它對初始條件極為敏感。國內外很多相關研究人員對這個問題進行了深入的研究，如文獻[4]提出基于GA的聚類方法，在一定程度上解決FCM的初值敏感性問題，但是由于遺傳算法本身的缺陷，仍會出現未成熟收斂現象。

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

1 模糊C?均值聚類概述

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

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

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

式中[U]與[P]分別為數據集[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 量子粒子群優化算法簡介

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

2004年J.Sun等人提出了量子粒子群（Quantum?behaved Particle Swarm Optimization，QPSO）[7]，主要的改進是在標準的粒子群算法基礎上引入量子行為，QPSO是以DELTA勢阱為基礎，認為粒子具有量子的行為，該算法的迭代公式如下[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]為平均最優位置；[M]為粒子的數目；[D]為粒子的維數；[Pi（Pi1，Pi2，…，Pid）]為第[i]個粒子的個體最優位置；[Xi（Xi1，Xi2，…，Xid）]為第[i]個粒子的位置；[Pg]為全局最優位置；[u、][R1d、][R2d]是介于（0，1）之間的隨機數， [β]稱為收縮擴張系數。

3 基于量子粒子群優化算法的模糊C?均值

聚類算法

3.1 量子粒子編碼

量子粒子群優化算法是采用量子染色體對問題進行描述的，量子染色體具體形式描述如下：

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

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

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

3.2 量子門更新

量子門的構造是算法的關鍵所在。目前在QPSO中主要采用的是量子旋轉門：

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

更新過程如下：

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

旋轉量子門示意圖如圖1所示。

圖1 旋轉量子門示意圖

一般方法是通過查詢表得到角度的設置。為了防止算法陷入早熟收斂，本文提出一種[R&Nε]門旋轉策略。[R&Nε]門由旋轉門和[Nε]門構成。非門（Not?gate）是經典的量子門，它的作用是交換量子比特位的參數。[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 算法流程

改進QPSO算法流程如圖2所示。

4 實驗結果與分析

實驗以UCI中的3個實際數據集作為聚類對象，分別用PSO算法與FCM結合以及本文算法對數據對象進行聚類分析。各算法的聚類中心數為其類別數。評價指標如下：

[E=nN×100%] （9）

式中：[N]表示總對象數；[n]表示錯誤分類的對象數。實驗結果見表1。

圖2 改進QPSO算法流程

表1 實驗結果

[數據集＼&算法＼&平均值＼&最小值＼&最大值＼& 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個實際數據集，本文算法聚類指標[E]均比PSO?FCM要小，聚類正確率尤其是對于Soybean?small樣本得到了較大的提高， 本文算法的代價函數最大值遠小于PSO?FCM，且平均值比PSO?FCM要小，這充分體現了本文改進算法的全局尋優能力強于PSO?FCM。

5 結 論

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

參考文獻

[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均值聚類算法中參數m的優選[J].模式識別與人工智能，2000，13（1）：7?11.

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

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

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

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

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

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

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

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

[12] 李棟.量子衍生多目標進化算法及其應用研究[D].長沙：湖南大學，2008.

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

參考文獻

[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均值聚類算法中參數m的優選[J].模式識別與人工智能，2000，13（1）：7?11.

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

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

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

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

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

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

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

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

[12] 李棟.量子衍生多目標進化算法及其應用研究[D].長沙：湖南大學，2008.

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

參考文獻

[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均值聚類算法中參數m的優選[J].模式識別與人工智能，2000，13（1）：7?11.

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

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

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

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

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

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

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

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

[12] 李棟.量子衍生多目標進化算法及其應用研究[D].長沙：湖南大學，2008.

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