基于SNP系統(tǒng)的改進(jìn)粒子群聚類算法

李 立

(安慶廣播電視大學(xué)， 安徽 安慶 246003)

0 引 言

在眾多的聚類分析算法中，K-means是基于劃分的經(jīng)典聚類算法，具有局部尋優(yōu)能力強(qiáng)、聚類速度快和易于實現(xiàn)的優(yōu)點，但該算法也存在聚類結(jié)果過于依賴初始聚類中心點、波動性大且易于陷入局部極值的缺點.對此，有學(xué)者提出了基于多種粒子群優(yōu)化(Particle swarm optimization,PSO)的聚類算法[1-2]，即將PSO算法的全局尋優(yōu)能力和K-means算法的局部尋優(yōu)能力相結(jié)合來改善聚類算法的性能，并取得了一定的效果.但是，PSO算法在實現(xiàn)優(yōu)化時會出現(xiàn)早熟收斂現(xiàn)象，且具有較強(qiáng)的隨機(jī)性，在實際應(yīng)用中具有一定的局限性.針對該問題，有學(xué)者提出一種以生物細(xì)胞為原型的膜計算算法模型[3]，其可將細(xì)胞區(qū)域劃分成各自獨立的計算單元，具有強(qiáng)大的計算能力.目前，脈沖神經(jīng)膜(Spiking neural P,SNP)系統(tǒng)是基于神經(jīng)型的膜計算模型，也是膜計算領(lǐng)域的研究熱點之一[4-7].本研究在粒子群聚類算法中引入SNP系統(tǒng)，構(gòu)建了一種基于SNP系統(tǒng)的改進(jìn)PSO-KM模型，即SNPS-PK算法，其原理是將初始聚類中心的各種組合作為粒子，將其分配到若干個神經(jīng)元，并在神經(jīng)元中進(jìn)行粒子群的迭代與進(jìn)化，利用SNP系統(tǒng)的高并行性和PSO算法的全局尋優(yōu)能力在更短的時間內(nèi)得到更優(yōu)化的初始聚類中心，為下一步K-means算法的局部尋優(yōu)提供更好的聚類初值，以進(jìn)一步提升聚類結(jié)果的穩(wěn)定性和準(zhǔn)確率.

1 概念及定義

1.1 PSO算法

PSO算法是一種仿生方法，粒子之間通過相互協(xié)作并不斷迭代來生成最優(yōu)解，其實現(xiàn)步驟如下：

假設(shè)含M個粒子的群體在一個N維空間進(jìn)行搜索，粒子i(1≤i≤M)的位置、速度和歷史最優(yōu)位置分別用3個維向量來表示，Xi=(xi1，xi2，…，xiN)，Vi=(vi1,vi2，…，viN)和Pbesti=(Pbesti1,Pbesti2，…，PbestiN).整個粒子群的全局最優(yōu)位置可表示為，Gbest=(Gbesti1，Gbesti2，…，GbestiN).在迭代過程中，粒子更新速度和位置如式(1)與式(2)所示.

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

c2r2(Gbest-Xi)

(1)

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

(2)

其中，ω為慣性權(quán)重，c1和c2為學(xué)習(xí)因子，r1和r2為隨機(jī)權(quán)重.

1.2 K-means算法

K-means算法是一種基于質(zhì)心的啟發(fā)式聚類算法，其實現(xiàn)步驟如下：

1)在n個數(shù)據(jù)樣本中隨機(jī)選擇k個Ci(i=1,2，…，k)作為初始聚類中心；

2)計算其他數(shù)據(jù)樣本與初始聚類中心的距離，若數(shù)據(jù)樣本Xj屬于第i聚類，則其權(quán)重值wji=1，否則為0，如式(3)所示：

(3)

3)由式(4)計算目標(biāo)函數(shù)J，若J值不變，則停止迭代，算法結(jié)束.否則，進(jìn)入步驟4)，

(4)

4)由式(5)更新聚類的中心點，回到步驟2).

(5)

1.3 SNP系統(tǒng)的定義

一個標(biāo)準(zhǔn)SNP系統(tǒng)的定義為，

Π=(O,σ1,σ2，…，σm，syn,in,out)

(6)

其中：

1)O={a}是脈沖a的集合.

2)σ1,σ2,…,σm是系統(tǒng)Π中所含的m(m≥1)個神經(jīng)元，σi=(ni,Ri)(1≤i≤m)，其中，ni表示σi中脈沖的初始值，而Ri表示兩類規(guī)則的集合:

(1)激發(fā)規(guī)則.E/ac→a;d(c≥1,d≥0)，E為a的正則表達(dá)式，d為時延.若神經(jīng)元σi在某時刻有k個脈沖，且ak∈L(E)(k≥c)，則利用規(guī)則E/ac→a激發(fā)，消耗c個脈沖，并在d步之后向相關(guān)神經(jīng)元分別發(fā)送1個脈沖.

(2)遺忘規(guī)則.as→λ(s≥1),對Ri中的任意規(guī)則E/ac→a;d，都滿足as?L(E).若神經(jīng)元σi在某時刻有且僅有s個脈沖，則利用規(guī)則as→λ，消耗掉所有的脈沖，且不會產(chǎn)生新的脈沖.

3)syn?{1，2,…，m}×{1,2,…，m}表示神經(jīng)元之間的突觸.其中，(i,j)∈syn,(1≤i,j≤m,i≠j).

4)σin和σout分別表示輸入和輸出神經(jīng)元，其中，in,out∈[1,2，…，m].

2 基于SNP系統(tǒng)的改進(jìn)粒子群聚類算法

本研究將SNP系統(tǒng)與PSO算法、K-means算法相結(jié)合，構(gòu)建了一種基于SNP系統(tǒng)的改進(jìn)PSO-KM模型的SNPS-PK算法，以進(jìn)一步提升聚類結(jié)果的穩(wěn)定性和準(zhǔn)確率.

2.1 粒子群的適應(yīng)度函數(shù)和編碼方案

聚類分析時，PSO算法的適應(yīng)度函數(shù)用來評價k個聚類中心的性能，其定義為，

(7)

其中，f(x)是粒子在位置x處的適應(yīng)度值Zj(1≤j≤k)，是類Cj的聚類中心，Xi是集群中的數(shù)據(jù)樣本.粒子的f(x)可以衡量數(shù)據(jù)對象的結(jié)合程度，f(x)越小表示結(jié)合越緊密，聚類效果越好.

PSO算法的優(yōu)化目標(biāo)就是搜索到f(x)值最小的粒子位置，其對應(yīng)的就是優(yōu)化后的初始聚類中心.粒子i在第(t+1)次迭代時，如果f(xi(t+1))

采用PSO算法對K-means算法的初始聚類中心優(yōu)化前，k個聚類中心Zj(1≤j≤k)映射成集群中的粒子，其坐標(biāo)向量組成了粒子在優(yōu)化過程中的位置，而粒子i的適應(yīng)度值為f(xi)(1≤i≤k).每個粒子代表某種可行解，粒子的編碼由k個d維聚類中心中粒子的位置、速度和適應(yīng)度值組成，其編碼方案為，

Z11…Z1dZ21…Z2dZk1…Zkd‖V11…V1dV21…V2dVk1…Vkd‖f(xi)

2.2 SNPS-PK算法中的參數(shù)設(shè)置

為了達(dá)到全局搜索和局部搜索之間的平衡，文獻(xiàn)[1]給出了一種慣性權(quán)重ω隨迭代次數(shù)的增加而線性下降的方法，其慣性權(quán)重ω的計算式為，

ω(t)=ωmax-(ωmax-ωmin)t/ωmax

(8)

其中，ωmax和ωmin分別是最大和最小慣性權(quán)重，t和tmax分別是當(dāng)前迭代次數(shù)和最大迭代次數(shù).ω的理想取值范圍為0.4～0.9.

在實際計算中，為了避免“振蕩”并讓粒子加快收斂到最優(yōu)解，可在式(2)中增加飛行時間因子，則式(2)變?yōu)椋?/p>

Xi(t+1)=Xi(t)+H0(1-t/tmax)Vi(t+1)

(9)

其中，t和tmax分別是當(dāng)前迭代次數(shù)和最大迭代次數(shù).H0為1.5.

式(1)中，學(xué)習(xí)因子c1和c2分別調(diào)節(jié)向Pbest和Gbest方向飛行的最大步長，c1是粒子自身學(xué)習(xí)的權(quán)重系數(shù)，c2是粒子群體學(xué)習(xí)的權(quán)重系數(shù).為了平衡隨機(jī)因素的作用，一般情況下，c1=c2.而r1和r2被設(shè)置成介于[0,1]之間的隨機(jī)數(shù)，目的在于增加粒子飛行的隨機(jī)性.

2.3 SNPS-PK算法的膜結(jié)構(gòu)

SNPS-PK算法的膜結(jié)構(gòu)如圖1所示.神經(jīng)元內(nèi)的對象不是脈沖，而是粒子對應(yīng)的位置，即不斷迭代的聚類中心.

圖1中的神經(jīng)元1、2和3為輔助神經(jīng)元，神經(jīng)元4為主神經(jīng)元，神經(jīng)元5為輸出神經(jīng)元.系統(tǒng)Π中輔助神經(jīng)元粒子的主要功能是搜索可能存在最優(yōu)解的領(lǐng)域并及時將搜索信息傳回主神經(jīng)元.輔助神經(jīng)元1和3中的粒子按照式(1)和式(2)更新速度和位置，按照式(8)進(jìn)行慣性權(quán)重ω的調(diào)整.神經(jīng)元內(nèi)部每次迭代后，都根據(jù)適應(yīng)度值對粒子進(jìn)行優(yōu)劣排序，將其中最優(yōu)的s個粒子送入主神經(jīng)元4.

圖1 SNPS-PK算法對應(yīng)的膜結(jié)構(gòu)

神經(jīng)元1和3中的規(guī)則如下：

輔助神經(jīng)元2中的規(guī)則如下：

主神經(jīng)元4對從輔助神經(jīng)元1、2和3接收到的3s個粒子進(jìn)行重新迭代和排序，搜索到最優(yōu)解.

主神經(jīng)元4中的規(guī)則如下：

2.4 SNPS-PK算法的轉(zhuǎn)換時機(jī)

SNPS-PK算法包括2個階段：在前階段，利用SNP系統(tǒng)的并行性和PSO算法的全局尋優(yōu)能力進(jìn)行全局搜索，在可行解空間內(nèi)找到k個優(yōu)化的初始聚類中心；在后階段，執(zhí)行K-means算法，進(jìn)行局部優(yōu)化，并輸出最終的聚類結(jié)果.

其中，SNPS-PK算法前后兩個階段的轉(zhuǎn)換時機(jī)是根據(jù)適應(yīng)度方差σ2來判定粒子群的收斂程度.適應(yīng)度方差σ2定義如下，

(10)

其中，m是粒子群的規(guī)模，favg是粒子適應(yīng)度的平均值.當(dāng)σ2很小時，粒子群的狀態(tài)已趨于收斂，此時即為SNPS-PK算法的轉(zhuǎn)換時機(jī).

3 實驗與分析

為了驗證SNPS-PK算法的有效性，本研究對其進(jìn)行了仿真實驗測試.

實驗環(huán)境為：操作系統(tǒng)Windows 10，CPU 2.7 GHz InterCore(TM)，內(nèi)存4 GiB，編譯軟件為Edit with IDLE，用Python語言編程實現(xiàn).本研究在3個數(shù)據(jù)集上測試SNPS-PK算法，其中包含1個真實數(shù)據(jù)集Iris及2個人工數(shù)據(jù)集Data1和Data2.在實驗中，分別在此3個數(shù)據(jù)集上運行SNPS-PK算法，得到的聚類結(jié)果如圖2～圖4所示.

圖2在數(shù)據(jù)集Iris上執(zhí)行SNPS-PK算法

圖3在數(shù)據(jù)集Data1上執(zhí)行SNPS-PK算法

圖4在數(shù)據(jù)集Data2上執(zhí)行SNPS-PK算法

同時，實驗中還將SNPS-PK算法與標(biāo)準(zhǔn)K-means算法、PSO-KM算法進(jìn)行了比較.三種算法的聚類準(zhǔn)確率及運行時間的比較結(jié)果如表1所示.

由表1可知，三種算法中，K-means算法的準(zhǔn)確率最低，SNPS-PK算法的準(zhǔn)確率最高，PSO-KM算法介于兩者之間.PSO-KM算法利用PSO的全局搜索能力，此在一定程度上提升了聚類準(zhǔn)確率.而SNPS-PK算法在PSO-KM算法的基礎(chǔ)上引入SNP系統(tǒng)，利用SNP系統(tǒng)的并行性進(jìn)一步優(yōu)化了聚類中心，并對慣性權(quán)重w和飛行時間因子H0進(jìn)行動態(tài)調(diào)整，使SNPS-PK算法能夠更好地接近最優(yōu)解，聚類準(zhǔn)確率得以進(jìn)一步提升.

表1 3種算法的聚類準(zhǔn)確率及運行時間比較

4 結(jié) 語

本研究在粒子群聚類算法中引入SNP系統(tǒng)，將SNP系統(tǒng)的并行性和PSO的全局尋優(yōu)能力相結(jié)合，使得初始聚類中心得以進(jìn)一步優(yōu)化，為下一步K-means算法的局部尋優(yōu)提供了更好的聚類初值，提升了聚類結(jié)果的準(zhǔn)確率.由于聚類算法與SNP系統(tǒng)的結(jié)合是一種新的研究思路，目前對其的研究仍主要集中在理論的探討上[8-9].因此，如何利用基于SNP系統(tǒng)的聚類算法解決實際問題是下一步的主要研究方向.