基于量子粒子群模糊C均值聚類(lèi)算法應(yīng)用研究

王富強(qiáng)，張振華，朱 然

(1.93856部隊(duì)，甘肅 蘭州 730070；2.太原電務(wù)段，山西 太原 030000)

?

基于量子粒子群模糊C均值聚類(lèi)算法應(yīng)用研究

王富強(qiáng)1，張振華1，朱 然2

(1.93856部隊(duì)，甘肅 蘭州 730070；2.太原電務(wù)段，山西 太原 030000)

模糊C均值聚類(lèi)對(duì)初始參數(shù)有著較強(qiáng)的依賴性，文中針對(duì)其對(duì)初始聚類(lèi)中心敏感的問(wèn)題，提出利用量子粒子群來(lái)優(yōu)化FCM的初始聚類(lèi)中心。粒子群優(yōu)化算法具有較強(qiáng)的全局搜索能力，但局部搜索能力不足，因此借助于量子理論，將粒子群量子化，借助量子旋轉(zhuǎn)門(mén)改變粒子的移動(dòng)，同時(shí)利用量子非門(mén)增加種群的多樣性，加強(qiáng)粒子群優(yōu)化算法的局部尋優(yōu)能力。并最終利用量子粒子群優(yōu)化算法搜尋FCM算法的初始聚類(lèi)中心，通過(guò)實(shí)驗(yàn)仿真表明，改進(jìn)的算法在加快搜索速度的同時(shí)，能獲得較為穩(wěn)定的聚類(lèi)中心且分割效果明顯優(yōu)于標(biāo)準(zhǔn)的FCM算法。

模糊C均值聚類(lèi)；抗噪性；道岔缺口；圖像分割

模糊C均值聚類(lèi)(Fuzzy C-Means, FCM)算法是一種基于目標(biāo)函數(shù)的算法，在圖像分割領(lǐng)域占有重要地位。但FCM算法在進(jìn)行圖像分割時(shí)，需初始化參數(shù)，包括聚類(lèi)中心和聚類(lèi)數(shù)目等[1]。若選取的聚類(lèi)中心處于局部極值時(shí)，算法不僅收斂速度下降，且分割精度也會(huì)降低。本文在粒子群聚類(lèi)算法的基礎(chǔ)上，針對(duì)粒子群算法易于陷入局部極小值的問(wèn)題，通過(guò)引入量子理論，將二者進(jìn)行融合，形成基于量子粒子群的模糊聚類(lèi)算法。

1 FCM算法

假設(shè)給定任意的一組數(shù)據(jù)樣本集合記為X={x1,x2…xn}?Rs，其中s為數(shù)據(jù)集X的維數(shù)，n為集合中樣本的數(shù)目，c(2≤c

(1)

其中，m是模糊因子；uij是第j個(gè)樣本xj屬于第i類(lèi)的隸屬度值，取值范圍在(0,1)間；‖xj-vi‖表示樣本點(diǎn)xj到聚類(lèi)中心vi的歐氏距離。vi和uij的表達(dá)式為

(2)

(3)

FCM算法步驟為：

步驟1 為參數(shù)初始化，包括設(shè)定聚類(lèi)數(shù)目c，模糊因子m，最大的迭代次數(shù)Tmax以及允許的最小迭代誤差ε，初始化各聚類(lèi)中心V(0)=[v1,v2,…,vc]；令迭代次數(shù)t=0；

步驟2 用式(2)更新隸屬度矩陣Ut+1；

步驟3 用式(2)更新聚類(lèi)中心V(t+1)；

步驟4 為若滿足‖V(t+1)-V(t)‖<ε或t>Tmax，則聚類(lèi)停止，輸出U和V；否則令t=t+1，返回步驟2，直到滿足停止迭代的條件為止。

2 量子粒子群模糊聚類(lèi)算法

2.1 粒子群優(yōu)化算法

粒子群優(yōu)化算法[3]用粒子表示所求問(wèn)題的解，然后在解空間中通過(guò)迭代搜索最優(yōu)值，從而找到問(wèn)題的最優(yōu)解。每個(gè)粒子由3部分構(gòu)成：粒子的歷史最優(yōu)位置、粒子的飛行速度及粒子的適應(yīng)度值。在迭代尋優(yōu)的過(guò)程中，粒子按照個(gè)體極值和全局極值改變自身的移動(dòng)方向和位置。個(gè)體極值是當(dāng)前粒子自身搜尋到的最優(yōu)解，記為Pbest，代表粒子自身的認(rèn)知能力；全局極值是目前整個(gè)種群搜尋到的最優(yōu)解，記為Gbest，代表粒子對(duì)種群的認(rèn)知能力[4]。在找到Pbest和Gbest這兩個(gè)極值后，所有粒子按照如下公式更新自身速度及新的位置

Vi(t+1)=ωVi(t)+c1r1(Pbesti(t)-Xi(t))+

c2r2(Gbest(t)-Xi(t))

(4)

Xi(t+1)=Xi(t)+Vi(t+1)

(5)

其中，Xi(t)是當(dāng)前第i粒子的位置；Vi(t)是當(dāng)前第i粒子的速度向量；Pbesti(t)是第i個(gè)粒子經(jīng)過(guò)t次迭代后搜尋到的自身最優(yōu)解的位置；Gbest(t)是當(dāng)前整個(gè)粒子群所找到的最優(yōu)解位置；c1、c2是學(xué)習(xí)因子；分別代表粒子對(duì)自身的認(rèn)知系數(shù)和對(duì)社會(huì)的認(rèn)知系數(shù)，一般均為常數(shù)2，r1、r2是[0,1]之間的隨機(jī)數(shù)。按照適應(yīng)度值的大小來(lái)評(píng)價(jià)搜索到解空間位置的優(yōu)劣，從而使所有的粒子向著搜索空間內(nèi)個(gè)體最優(yōu)位置和全局最優(yōu)位置移動(dòng)[5]。

2.2 量子理論

量子理論其根本在于量子微觀世界成功的揭示了物質(zhì)的內(nèi)部組成及運(yùn)動(dòng)規(guī)律[6]。比特是經(jīng)典信息中的基本概念，通常用0和1二進(jìn)制數(shù)表示信息，與經(jīng)典比特相同，量子比特(Quantum bit)也描述一種信息狀態(tài)[7]，也可寫(xiě)成|0〉和|1〉的形式，稱為計(jì)算基矢，其中“|〉”為Dirac標(biāo)記。量子比特與經(jīng)典比特的最大區(qū)別在于：經(jīng)典比特只有0和1兩種狀態(tài)，而量子比特除了|0〉和|1〉以外，還可以是這兩種狀態(tài)的任意線性組合，即量子的疊加態(tài)，其表達(dá)式可表示為

|φ〉=α|0〉+β|1〉=[α,β]T

(6)

其中，α、β均為復(fù)系數(shù)，分別表示|0〉、|1〉出現(xiàn)的概率，通常稱為量子態(tài)的概率幅，需滿足歸一化條件|α|2+|β|2=1 。當(dāng)α=0或β=0時(shí)，量子比特退化為|0〉或|1〉，此時(shí)量子比特退化為經(jīng)典比特。

量子計(jì)算的發(fā)展從一切量子系統(tǒng)中最簡(jiǎn)單的運(yùn)算開(kāi)始。通過(guò)一系列的幺正變換可使量子態(tài)實(shí)現(xiàn)一些邏輯功能。通常將在這一時(shí)間間隔內(nèi)實(shí)現(xiàn)邏輯變換的量子裝置稱為量子邏輯門(mén)或量子門(mén)，較為常見(jiàn)的量子門(mén)主要有非門(mén)、旋轉(zhuǎn)門(mén)和Hadamard門(mén)等[8]。其中，量子旋轉(zhuǎn)門(mén)占有重要地位，通過(guò)量子旋轉(zhuǎn)角來(lái)完成更新操作，用 表示量子旋轉(zhuǎn)角。其矩陣表示為

(7)

當(dāng)量子旋轉(zhuǎn)門(mén)作用于量子比特|φ〉時(shí)，更新表達(dá)式為

(8)

通過(guò)上式可以看出量子旋轉(zhuǎn)門(mén)的作用，且更新后的量子比特概率幅依然滿足歸一化要求 (|cos(θ+φ)|2+|sin(θ+φ)|2=1)。值得注意的是，量子旋轉(zhuǎn)角θ是量子旋轉(zhuǎn)門(mén)的核心部分，其關(guān)系到算法的收斂速度和尋優(yōu)能力，因此也是量子智能算法及其衍生算法主要的研究對(duì)象。量子旋轉(zhuǎn)角θ的選擇公式為

θ=s(α,β)*Δθ

(9)

其中，Δθ為當(dāng)前量子狀態(tài)旋轉(zhuǎn)到目標(biāo)狀態(tài)時(shí)轉(zhuǎn)過(guò)角度大??；s(α,β)表示所需旋轉(zhuǎn)的方向。

2.2.1 粒子群量子位編碼

由于粒子群在編碼初始化時(shí)有較強(qiáng)的隨機(jī)性，故在此采用實(shí)數(shù)編碼方案，將量子位的概率幅作為編碼值

(10)

其中，θij2π×rnd;rnd為(0,1)之間的隨機(jī)數(shù)，i=1,2,…,m；j=1,2,…,n。而n是種群規(guī)模；n是空間維數(shù)。經(jīng)過(guò)量子位編碼后，每個(gè)粒子在搜索空間中占據(jù)了兩個(gè)位置，每個(gè)位置的概率幅分別為

Pic=[cos(θi1)cos(θi2)…cos(θin)];Pis=

[sin(θi1)sin(θi2)…sin(θin)]

(11)

可見(jiàn)經(jīng)過(guò)量子編碼后，整個(gè)粒子群在種群規(guī)模不變的前提下，搜索空間加倍，種群多樣性增加。

2.2.2 量子粒子的狀態(tài)更新

在量子粒子群優(yōu)化算法中，粒子位置的移動(dòng)是通過(guò)量子旋轉(zhuǎn)門(mén)來(lái)實(shí)現(xiàn)的。與標(biāo)準(zhǔn)PSO中速度和位置的更新公式相比，量子旋轉(zhuǎn)門(mén)角度的更新代替粒子速度的更新；粒子量子位概率幅的更新代替粒子位置的更新。假設(shè)粒子Pi當(dāng)前搜索到的最優(yōu)位置為

Pil=(cos(θil1),cos(θil2),…,cos(θiln))

(12)

整個(gè)種群當(dāng)前搜索到的最優(yōu)位置為

Pg=(cos(θg1),cos(θg2),…,cos(θgn))

(13)

(1)量子位旋轉(zhuǎn)角度更新。粒子Pi的量子位更新后的角度增量為

Δθij(t+1)=ωΔθij(t)+c1r1(Δθl)+c2r2(Δθg)

(14)其中，ω是慣性因子；c1、c2是常數(shù)；r1、r2是[0,1]之間的隨機(jī)數(shù)；Δθl和Δθg分別是當(dāng)前粒子與移動(dòng)后粒子的角度差值以及全局最優(yōu)位置的角度差值，其計(jì)算公式為

(15)

(16)

(2)量子位概率幅更新。

(17)

利用量子旋轉(zhuǎn)門(mén)可得到粒子 更新后的位置為

(18)

(3)變異處理。粒子群算法由于在搜索過(guò)程中種群多樣性的丟失導(dǎo)致算法易陷入局部極小值。為此，需要通過(guò)變異操作來(lái)增加種群的多樣性，防止算法陷入局部最優(yōu)，利用量子非門(mén)實(shí)現(xiàn)變異操作

(19)

其中，i∈{1,2,3,…,m},j∈{1,2,3,…,n}。

為此，引入一個(gè)變異概率，記為pm，同時(shí)規(guī)定每個(gè)粒子在(0,1)之間均有一個(gè)隨機(jī)數(shù)rndi，若rndi

2.3 改進(jìn)的算法步驟

步驟1 為參數(shù)初始化，包括種群規(guī)模n，變異率pm，聚類(lèi)類(lèi)別c，隨機(jī)選取c個(gè)樣本點(diǎn)作為聚類(lèi)中心組成一個(gè)量子個(gè)體；

步驟3 根據(jù)式(14)和式(17)更新粒子的位置；

步驟4 按照異概率，對(duì)每個(gè)粒子依式(19)實(shí)現(xiàn)變異操作；

步驟5 返回步驟2循環(huán)計(jì)算，直到滿足收斂條件或代數(shù)達(dá)到最大迭代次數(shù)；

步驟6 解碼最優(yōu)個(gè)體，將其作為FCM算法的初始聚類(lèi)中心點(diǎn)，并初始化FCM算法其他參數(shù)；步驟7 利用FCM算法完成圖像進(jìn)行分割；

步驟8 為算法結(jié)束。

3 實(shí)驗(yàn)仿真及分析

為了驗(yàn)證算法的有效性，在聯(lián)想 Intel(R)Core(TM)i3-2120，CPU 3.3 GHz， 內(nèi)存1.98 GB平臺(tái)上，利用Matlab對(duì)多幅標(biāo)準(zhǔn)測(cè)試圖像進(jìn)行了驗(yàn)證。

圖1 兩種算法對(duì)“Airfield”的分割效果

參數(shù)選取：粒子群規(guī)模n=30；c1=c2=2；w=0.2；變異率Pm=0.02；最大迭代次數(shù)Tmax=100；允許最小的停止迭代閾值ε為0.000 1。圖1(a)是Airfield原圖像，圖1(b)和圖1(c)分別為FCM算法及本文算法分割效果，聚類(lèi)數(shù)目c=3。

圖2(a)是Boats原圖像，圖2(b)和圖2(c)分別是FCM算法及本文算法的分割效果，聚類(lèi)數(shù)目c=2。

圖2 兩種算法對(duì)“Boats”的分割效果

圖3(a)是Girl原圖像，圖3(b)和圖3(c)分別是FCM算法及本文算法的分割效果，聚類(lèi)數(shù)目c=2。

圖3 兩種算法對(duì)“Girl”的分割效果

圖4(a)是腦部MRI圖像，圖4(b)和圖4(c)分別是FCM算法及本文算法的分割效果，聚類(lèi)數(shù)目c=4。

圖4 兩種算法對(duì)“腦部MRI ”的分割效果

通過(guò)對(duì)比圖1中3種分割效果，本文算法能較好地分割出信號(hào)樓，地面上的線路分割連續(xù)且清晰；通過(guò)對(duì)比圖2中3種分割效果，本文算法分割出的直線型信息(包括船桿、船體側(cè)面的直線以及房屋的輪廓)基本完整且邊緣部分更平滑，地面紋理信息分割的也更為細(xì)膩；通過(guò)對(duì)比圖3中3種分割效果，在桌面、書(shū)架等物體的分割上，本文算法分割出的紋理更加清晰，在人物的手臂、服裝的紋理及人物面部信息保留的更為完整；對(duì)比圖4中3種分割效果，本文算法分割出的腦白質(zhì)、腦灰質(zhì)、腦脊液的邊緣連續(xù)、清晰，尤其在腦脊液的分割中保留了更多的細(xì)節(jié)信息。

客觀上，表1給出了每幅圖像經(jīng)過(guò)30次實(shí)驗(yàn)后在聚類(lèi)中心、劃分系數(shù)、劃分熵、迭代次數(shù)以及運(yùn)行時(shí)間的數(shù)據(jù)對(duì)比。由于量子粒子群搜尋到最優(yōu)的初始聚類(lèi)中心，使得本文算法收斂具有較強(qiáng)的方向性，因此在迭代次數(shù)及運(yùn)行時(shí)間上均有所減少，劃分系數(shù)和劃分熵表明，本文算法的分割效果較好。

表1 兩種算法性能比較

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

針對(duì)FCM算法對(duì)初始聚類(lèi)中心敏感的問(wèn)題，利用量子粒子群優(yōu)化算法搜尋FCM算法的初始聚類(lèi)中心，形成基于量子粒子群優(yōu)化算法的模糊聚類(lèi)算法，利用量子非門(mén)增加種群搜索空間多樣性，防止陷入局部極小值。同時(shí)，借助于量子算法提高粒子群優(yōu)化算法的收斂速度，完成后續(xù)的圖像分割。實(shí)驗(yàn)仿真結(jié)果表明，改進(jìn)算法能獲得穩(wěn)定的聚類(lèi)中心且分割效果理想，同時(shí)解決了及粒子群優(yōu)化算法易于陷入局部最優(yōu)的不足，提高算法的分割精度。

[1] 張翡,范虹.基于模糊C均值聚類(lèi)的醫(yī)學(xué)圖像分割研究[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(4):144-151.

[2] Joseph C Dunn.A fuzzy relative of the ISODATA process and its use in detecting compact well separated clusters[J].Journal of Cybernetics,1973,3(1):32-47.

[3] Kennedy J, Eberhart R C. Partiele swarm optimization[C]. Perth, Australia :Proe of the IEEE Intemational Conference on Neural Networks(ICNN), 1995.

[4] 紀(jì)震,吳青華,廖惠連.粒子群算法及應(yīng)用[M].北京:科學(xué)出版社,2009.

[5] 孫俊,方偉,吳小俊,等.量子行為粒子群優(yōu)化:原理及其應(yīng)用[M].北京:清華大學(xué)出版社,2011.

[6] 李士勇,李盼池.量子計(jì)算與量子優(yōu)化算法[M].哈爾濱:哈爾濱工業(yè)大學(xué)出版社,2009.

[7] 趙生妹,鄭寶玉.量子信息處理技術(shù)[M].北京:北京郵電大學(xué)出版社,2010.

[8] 陳漢武.量子信息與量子計(jì)算簡(jiǎn)明教程[M].南京:東南大學(xué)出版社,2006.

Study on the Application of Fuzzy C-Means Clustering Algorithm Based on Quantum Particle Swarm C

WANG Fuqiang1, ZHANG Zhenhua1, ZHU Ran2

(1. Unit 93856, PLA, Lanzhou 730070, China; 2. Taiyuan Signal Depot, Taiyuan 030000, China)

Fuzzy c-means (FCM) clustering has an excessive dependence on initial parameters. The quantum particle swarm is adopted to optimize initial clustering center of FCM to address its sensitivity to the initial clustering center. The particle swarm optimization algorithm has stronger global searching ability, but insufficient local search ability. The quantum rotating gate changes the movement of the particles and increases the diversity of population, thus better local optimization ability of particle swarm optimization algorithm. The quantum particle swarm optimization algorithm is used to search the initial clustering center of FCM algorithm. The experimental simulation shows that the improved algorithm can speed up the search while obtaining more stable clustering center and better segmentation effect than the standard FCM algorithm segmentation effect.

FCM; noise immunity; rail gap; image segmentation

2016- 01- 15

王富強(qiáng)(1988-)，男，碩士，助理工程師。研究方向：圖像分割，靜電感應(yīng)器件和集成電路的設(shè)計(jì)。

10.16180/j.cnki.issn1007-7820.2016.11.039

TN911.73

A

1007-7820(2016)11-137-05