劉世華,葉展翔,劉向華(溫州職業(yè)技術(shù)學(xué)院 信息技術(shù)系,浙江 溫州 325035)
一種新的自組織粒子群聚類算法
劉世華,葉展翔,劉向華
(溫州職業(yè)技術(shù)學(xué)院 信息技術(shù)系,浙江 溫州 325035)
針對(duì)粒子群優(yōu)化(PSO)算法復(fù)雜度偏高的問題,提出一種新的基于競(jìng)爭(zhēng)學(xué)習(xí)的自組織粒子群聚類(SOPSC)算法。該算法采用每個(gè)粒子代表一個(gè)聚類中心的編碼方法,通過借鑒自組織映射(SOM)算法的競(jìng)爭(zhēng)學(xué)習(xí)機(jī)制,采用類內(nèi)相似度和類間相異度作為指導(dǎo),使粒子進(jìn)行自組織飛行,從而達(dá)到自動(dòng)聚類的目的,克服了傳統(tǒng)粒子群聚類算法中粒子編碼復(fù)雜、算法復(fù)雜度偏高的缺點(diǎn)。實(shí)驗(yàn)證明,該算法聚類精度高、穩(wěn)定性好,且對(duì)初始值和參數(shù)不敏感。
粒子群聚類;競(jìng)爭(zhēng)學(xué)習(xí);PSO;SOM;SOPSC
DOI:10.13669/j.cnki.33-1276/z.2015.059
隨著群體智能算法的發(fā)展及其廣泛應(yīng)用,各種智能算法廣泛應(yīng)用于數(shù)據(jù)聚類,粒子群優(yōu)化(PSO)算法就是其中重要的一種。2002年Omran等提出一種基于粒子群優(yōu)化的無指導(dǎo)圖像分類算法[1],這被認(rèn)為是最早提出的基于PSO的聚類算法。之后的粒子群聚類算法大都遵循其基本思想[2]。2003年Merwe等在此算法基礎(chǔ)上提出了基本PSO算法[3],用于對(duì)一般數(shù)據(jù)集進(jìn)行聚類操作。同時(shí),他們還研究了PSO算法與傳統(tǒng)K-means算法相結(jié)合的混合聚類算法,經(jīng)實(shí)驗(yàn)發(fā)現(xiàn),混合方法部分改進(jìn)了K-means算法容易陷入局部最優(yōu)的缺點(diǎn),但該算法復(fù)雜度偏高[2-3]。這是由于基本的粒子群聚類每個(gè)粒子代表一個(gè)數(shù)據(jù)劃分(聚類結(jié)果),導(dǎo)致單個(gè)粒子編碼的維度過大造成的。隨后,人們又將粒子群與模糊C均值算法進(jìn)行結(jié)合用以改進(jìn)算法效率。李峻金等對(duì)粒子群聚類算法進(jìn)行了綜述,介紹了后續(xù)的一些改進(jìn)工作[2]。劉春曉對(duì)PSO算法進(jìn)行了大量實(shí)驗(yàn)研究,并提出一種基于自組織映射(SOM)神經(jīng)網(wǎng)絡(luò)和PSO的聚類組合算法,即SOM/PSO算法,該算法利用SOM的聚類結(jié)果初始化P S O的粒子位置,可以減少聚類算法的收斂時(shí)間,提高聚類精度[4]。
目前,所有的PSO算法及其改進(jìn)都沒有對(duì)粒子編碼進(jìn)行簡(jiǎn)化,它們均采用一個(gè)粒子代表一個(gè)全局聚類中心的編碼方式。如果待聚類數(shù)據(jù)每個(gè)數(shù)據(jù)點(diǎn)有n維,將聚類成k類,那么每個(gè)粒子就需要至少n×k維的向量來進(jìn)行編碼,直接導(dǎo)致了PSO算法的復(fù)雜度偏高。為有效解決這一問題,本文提出一種新的基于競(jìng)爭(zhēng)學(xué)習(xí)的自組織粒子群聚類(Self-organized PSO Clustering,簡(jiǎn)稱SOPSC)算法。SOPSC算法將每個(gè)粒子編碼為一個(gè)聚類中心點(diǎn),每個(gè)粒子只需要n維,共投放k個(gè)粒子即可,在粒子飛行時(shí),引入SOM算法中的“勝者為王”(Winner-takes-all,簡(jiǎn)稱WTA)的競(jìng)爭(zhēng)學(xué)習(xí)機(jī)制,并通過類內(nèi)相似度和類間相異度特征進(jìn)行引導(dǎo),從而提高PS O算法的效率。實(shí)驗(yàn)證明,該算法聚類效果好于K-Means算法和PSO算法,算法穩(wěn)定性好,每次都能收斂到較好的全局最優(yōu)解,對(duì)初始值和參數(shù)不敏感,且聚類效率高于PSO算法。
PSO算法的基本思想是通過群體中個(gè)體之間的協(xié)作和信息共享來迭代式地尋找最優(yōu)解。在每一次的迭代中,粒子通過跟蹤兩個(gè)最優(yōu)解來指導(dǎo)自己的下一步行動(dòng):一個(gè)是粒子本身所找到的最優(yōu)解,稱為個(gè)體極值(Pbest);另一個(gè)是整個(gè)種群目前找到的最優(yōu)解,稱為全局極值(Gbest)。
根據(jù)以上兩個(gè)最優(yōu)解,標(biāo)準(zhǔn)粒子群算法通過(1)、(2)式來更新自己的移動(dòng)速度和位置,即:
(1)式為速度更新公式。其中,vi(t+1)是第t+1次迭代時(shí)第i個(gè)粒子移動(dòng)的速度,ω為慣性權(quán)重,φ1,φ2為局部最優(yōu)和全局最優(yōu)的調(diào)節(jié)權(quán)值。
(2)式為位置更新公式,即t+1次迭代中粒子i的位置為第t次的當(dāng)前位置加上速度更新。
粒子群中的每個(gè)粒子都代表待求解的優(yōu)化問題的一個(gè)解,根據(jù)速度和位置的更新準(zhǔn)則,粒子將最終收斂于一個(gè)全局最優(yōu)解。
根據(jù)PSO算法的基本思路,傳統(tǒng)的PSO算法根據(jù)數(shù)據(jù)點(diǎn)的維數(shù)n和待聚類的簇?cái)?shù)目k,對(duì)每個(gè)粒子進(jìn)行n×k維編碼,每個(gè)粒子代表一個(gè)聚類劃分,其k個(gè)聚類的中心點(diǎn)體現(xiàn)在粒子編碼中,如圖1所示。
注:假設(shè)n=2,k=3。圖1 PSO算法的粒子編碼
每個(gè)粒子在尋求局部最優(yōu)和全局最優(yōu)解時(shí)應(yīng)遵循以下適應(yīng)度函數(shù)f:
其中,pi為屬于第Ci個(gè)類的樣本數(shù),Nc為聚類簇?cái)?shù)目,oi為第i個(gè)類的中心,mij為屬于第i個(gè)類的第j個(gè)樣本,d(x,y)為x與y的距離度量。
傳統(tǒng)的PSO算法將聚類問題看成優(yōu)化問題,然后采用粒子群優(yōu)化策略來進(jìn)行求解,能夠較好地獲得全局最優(yōu)解,但由于其粒子編碼采用n×k維,當(dāng)數(shù)據(jù)的維度增加或聚類數(shù)目較大時(shí),粒子的編碼維度急劇增加,這使得PSO算法計(jì)算復(fù)雜度太高而影響其實(shí)用性。
3.1SOM神經(jīng)網(wǎng)絡(luò)與競(jìng)爭(zhēng)學(xué)習(xí)
(1)SOM神經(jīng)網(wǎng)絡(luò)。SOM神經(jīng)網(wǎng)絡(luò)是芬蘭Helsink大學(xué)的Kohonen教授于1981年提出的,又稱Kohonen網(wǎng)。Kohonen認(rèn)為,一個(gè)神經(jīng)網(wǎng)絡(luò)接受外界輸入模式時(shí),將會(huì)分為不同的對(duì)應(yīng)區(qū)域,各區(qū)域?qū)斎肽J骄哂胁煌捻憫?yīng)特征,且這個(gè)過程是自動(dòng)完成的[5]。
自組織競(jìng)爭(zhēng)型神經(jīng)網(wǎng)絡(luò)是一種無教師監(jiān)督學(xué)習(xí),具有自組織功能的神經(jīng)網(wǎng)絡(luò)。它通過自身的訓(xùn)練,可以自動(dòng)對(duì)輸入模式進(jìn)行分類,在網(wǎng)絡(luò)結(jié)構(gòu)上,一般由輸入層和競(jìng)爭(zhēng)層構(gòu)成兩層網(wǎng)絡(luò),兩層網(wǎng)絡(luò)之間各神經(jīng)元實(shí)現(xiàn)雙向連接,且網(wǎng)絡(luò)沒有隱含層,有時(shí)競(jìng)爭(zhēng)層各神經(jīng)元之間還存在橫向連接,如圖2所示。
圖2 SOM神經(jīng)網(wǎng)絡(luò)模型
自組織競(jìng)爭(zhēng)型神經(jīng)網(wǎng)絡(luò)構(gòu)成的基本思想是:網(wǎng)絡(luò)的競(jìng)爭(zhēng)層各神經(jīng)元競(jìng)爭(zhēng)對(duì)輸入模式響應(yīng)的機(jī)會(huì),最后僅有一個(gè)神經(jīng)元成為競(jìng)爭(zhēng)的勝者,這一獲勝神經(jīng)元?jiǎng)t表示對(duì)輸入模式的分類。如果H為空間的連續(xù)輸入數(shù)據(jù),A為空間的離散輸出空間,Ф為特征映射的非線性變換,它映射輸入空間H到輸出空間A表示為:Ф:H→A。
如果給定輸入向量X,SOM神經(jīng)網(wǎng)絡(luò)首先根據(jù)特征映射Ф確定其在輸出空間A中的最佳匹配神經(jīng)元i。神經(jīng)元i的突觸權(quán)值向量Wi可以視為神經(jīng)元指向輸入空間X的映射。
在SOM網(wǎng)絡(luò)模型中,每一個(gè)權(quán)系數(shù)向量都可以看作是輸入向量在神經(jīng)網(wǎng)絡(luò)中的一種內(nèi)部表示,或者說,它是輸入向量的映像,其自組織功能的目的就是通過調(diào)整權(quán)系數(shù),使神經(jīng)網(wǎng)絡(luò)收斂于一種表示形態(tài)。
(2)競(jìng)爭(zhēng)學(xué)習(xí)原理。SOM神經(jīng)網(wǎng)絡(luò)成功的關(guān)鍵就是其競(jìng)爭(zhēng)學(xué)習(xí)方法。網(wǎng)絡(luò)的輸出神經(jīng)元之間相互競(jìng)爭(zhēng)以求被激活,結(jié)果在每一時(shí)刻只有一個(gè)輸出神經(jīng)元被激活。這個(gè)被激活的神經(jīng)元稱為“競(jìng)爭(zhēng)獲勝神經(jīng)元”,而其它神經(jīng)元的狀態(tài)被抑制,故稱為“勝者為王”。
競(jìng)爭(zhēng)學(xué)習(xí)過程主要有以下三個(gè)步驟:
步驟1:將當(dāng)前輸入模式向量X和競(jìng)爭(zhēng)層中各神經(jīng)元對(duì)應(yīng)的權(quán)重向量Wj(j=1,2,…,m,表示m個(gè)競(jìng)爭(zhēng)神經(jīng)元)全部進(jìn)行歸一化處理,即:
步驟2:通過計(jì)算輸入向量和m個(gè)競(jìng)爭(zhēng)神經(jīng)元的內(nèi)積競(jìng)選出獲勝神經(jīng)元j*,使其符合:
步驟3:對(duì)獲勝神經(jīng)元權(quán)重Wj*和學(xué)習(xí)率η進(jìn)行調(diào)整,直到學(xué)習(xí)率η為0,學(xué)習(xí)結(jié)束,即:
其中學(xué)習(xí)率η是一個(gè)小于1的依次遞減的參數(shù),用于確保算法的收斂。
3.2SOPSC算法
SOPSC算法引入了競(jìng)爭(zhēng)學(xué)習(xí)的思想,并對(duì)傳統(tǒng)PSO算法進(jìn)行了改良,簡(jiǎn)化了每個(gè)粒子的編碼,將每個(gè)粒子編碼為一個(gè)聚類中心,即每個(gè)粒子只代表某一類的中心點(diǎn),同時(shí)對(duì)粒子的位置和速度更新規(guī)則進(jìn)行設(shè)定。
(1)局部最優(yōu)部分Pbest,采用聚類中心點(diǎn)來代表,即聚類中心點(diǎn)作為當(dāng)前簇中粒子應(yīng)到達(dá)的最優(yōu)位置,如果有新的數(shù)據(jù)點(diǎn)加入該聚類,則需更新該簇中的粒子和該聚類中心點(diǎn)Pbest。
(2)由于每個(gè)粒子編碼只代表一個(gè)聚類中心,聚類迭代過程中無法確定每一個(gè)聚類中心的全局最優(yōu)位置,因而新算法中取消全局最優(yōu)部分Gb es t。
(3)對(duì)于一次循環(huán)中未獲勝的粒子,出于保持類間相異度考慮,將這些粒子對(duì)照獲勝粒子進(jìn)行反彈移動(dòng)操作,即讓其他粒子遠(yuǎn)離獲勝中心點(diǎn)。
(4)對(duì)于在整個(gè)迭代過程中一直都沒有獲勝的粒子,直接將其轉(zhuǎn)移到類內(nèi)相似度比較?。W式距離比較大)的粒子附近,讓其下一輪參與該區(qū)域的競(jìng)爭(zhēng),使其用于將原來聚類數(shù)據(jù)點(diǎn)較多的簇進(jìn)一步區(qū)分。
SOPSC算法偽代碼如下:
其中,f(x)為在x所在聚類簇中,以x為中心點(diǎn)計(jì)算均方差的值,以此來判斷x在聚類中的中心性;xmax_dist(t)為類內(nèi)相似度比較?。W式距離比較大)的粒子的當(dāng)前位置;distance(yi,xj)用于計(jì)算輸入點(diǎn)yi與粒子xj的歐式距離。
為驗(yàn)證算法的有效性,首先采用Ruspini數(shù)據(jù)集進(jìn)行初步實(shí)驗(yàn),并給出原始數(shù)據(jù)點(diǎn)分布,采用SOP SC的粒子分布和K-Means算法聚類的簇中心點(diǎn)分布的直觀圖示觀察算法的穩(wěn)定性;然后采用UCI的Iris數(shù)據(jù)集進(jìn)行實(shí)際數(shù)據(jù)的聚類驗(yàn)證,分別采用兩種算法運(yùn)行100次,比較它們的平均結(jié)果和算法穩(wěn)定性;同時(shí),針對(duì)SOPSC算法,通過實(shí)驗(yàn)分析算法中權(quán)重參數(shù)和初始值對(duì)聚類結(jié)果的影響。實(shí)驗(yàn)證明,SOPSC算法聚類精度高、穩(wěn)定性好,且對(duì)初始值和參數(shù)不敏感,是一種理想可行的聚類算法。
4.1Ruspini數(shù)據(jù)集的直觀驗(yàn)證實(shí)驗(yàn)
Ruspini數(shù)據(jù)集是一個(gè)有75個(gè)二維數(shù)據(jù)點(diǎn)的數(shù)據(jù)集,分為4類,分別有20、23、17和15個(gè)數(shù)據(jù)點(diǎn),主要用于進(jìn)行模糊聚類算法的評(píng)估。Ruspini數(shù)據(jù)集原始數(shù)據(jù)分布如圖3所示。
采用K-means算法k=4時(shí)對(duì)正規(guī)化后的數(shù)據(jù)進(jìn)行聚類,從運(yùn)行結(jié)果看,K-means算法穩(wěn)定性不高,比較容易受到初始值的影響,其較好和較差結(jié)果如圖4所示。
圖3 Ruspini數(shù)據(jù)集原始數(shù)據(jù)分布
圖4 K-means聚類中心分布情況
采用SOPSC算法,使用4個(gè)粒子,全部放在中心位置,vmax=0.01,ω=0.95,算法迭代100次。在進(jìn)行聚類前,將數(shù)據(jù)集中的點(diǎn)進(jìn)行線性縮放,將數(shù)據(jù)點(diǎn)的坐標(biāo)值全部映射到[0,1]區(qū)間。此時(shí),SOPSC粒子分布情況如圖5所示。
由Ruspini數(shù)據(jù)集已知數(shù)據(jù)點(diǎn)的分類情況,因而可以比較兩種聚類算法的聚類正確性。從實(shí)際聚類結(jié)果看,SOPSC算法的聚類正確率在每次運(yùn)行時(shí)當(dāng)?shù)螖?shù)在20次以上即可達(dá)到100%;而K-Means聚類算法在初始值分布不理想時(shí),效果很差,從多次重復(fù)試驗(yàn)結(jié)果看,平均每運(yùn)行5~6次,才出現(xiàn)1次最優(yōu)結(jié)果,其最優(yōu)結(jié)果能達(dá)到100%。
4.2真實(shí)數(shù)據(jù)集的聚類比較實(shí)驗(yàn)
為進(jìn)一步驗(yàn)證算法的實(shí)用性,采用UCI提供的Iris數(shù)據(jù)集進(jìn)行聚類實(shí)驗(yàn)。Iris數(shù)據(jù)集是以鳶尾花的特征作為數(shù)據(jù)來源的真實(shí)世界的數(shù)據(jù),有150個(gè)四維的數(shù)據(jù)點(diǎn),分為3類,每類50個(gè)數(shù)據(jù)。實(shí)驗(yàn)采用Weka平臺(tái)進(jìn)行,每種聚類算法運(yùn)行100次取平均值。
圖5 SOPSC粒子分布情況
分別采用K-Means算法和SOPSC算法對(duì)Iris數(shù)據(jù)集進(jìn)行聚類,并比較它們聚類后的聚類正確性、類內(nèi)相似度和類間相異度。
(1)聚類正確性采用簡(jiǎn)單比較所分的三類中的數(shù)據(jù)點(diǎn)數(shù)目的正確性和計(jì)算聚類正確率來度量。聚類正確率ACC定義為正確聚類的數(shù)據(jù)點(diǎn)數(shù)除以總數(shù)據(jù)點(diǎn)數(shù)。
(2)類內(nèi)相似度采用均方差(即同一簇中數(shù)據(jù)點(diǎn)到數(shù)據(jù)中心點(diǎn)的距離的平方和除以數(shù)據(jù)點(diǎn)數(shù))來度量,第k類的類內(nèi)相似度記為Simk,即:
其中,Nk為屬于第k個(gè)聚類簇中數(shù)據(jù)點(diǎn)數(shù)目,Pk為第k個(gè)聚類簇的中心點(diǎn)。dist(xi,Pk)為第i個(gè)數(shù)據(jù)點(diǎn)與第k個(gè)聚類中心的距離。類內(nèi)相似度Simk數(shù)值越小,表示聚類效果越好。
(3)類間相異度采用聚類中心點(diǎn)的距離和來度量,記為Diff,即:
由表1可以看出,在Iris數(shù)據(jù)集上,SOPSC算法的表現(xiàn)略好于傳統(tǒng)的K-Means算法,但也沒有象在Ruspini數(shù)據(jù)集上的表現(xiàn)一樣達(dá)到100%。K-Means算法在某一二次運(yùn)行中能夠得到近似100%的效果,但由于受初始值影響比較大,其平均效果也受到影響。
表1 Iris聚類正確性
類內(nèi)相似度和類間相異度計(jì)算結(jié)果見表2。其計(jì)算是基于對(duì)原始數(shù)據(jù)進(jìn)行線性縮放歸一化到[0,1]范圍內(nèi)進(jìn)行,與直接在原始數(shù)據(jù)上進(jìn)行聚類和計(jì)算的結(jié)果不同。聚類的目的就是要根據(jù)樣本一定的相似特征進(jìn)行分組,并使代表類內(nèi)相似度的參數(shù)Simk最小化(Simk越小表示類內(nèi)的數(shù)據(jù)點(diǎn)越相似),使類間的相異度最大化(即聚類中心隔得越遠(yuǎn)越好)。由表2可以看出,SOPSC算法在類內(nèi)相似度上結(jié)果優(yōu)于傳統(tǒng)的K-Means算法,而類間相異度則比傳統(tǒng)的K-Means算法略勝一籌。
表2 類內(nèi)相似度和類間相異度計(jì)算結(jié)果
在SOPSC算法中,局部最優(yōu)和輸入向量在速度更新中的權(quán)重φ1,φ2分別取[0,1]之間的隨機(jī)數(shù)即可,對(duì)其聚類結(jié)果沒有影響。從本質(zhì)上看,SOPSC算法如果把輸入向量yj部分的影響去除,即如果取φ1=1,φ2=0,則SOPSC算法與K-Means算法是一樣的,因而SOPSC算法也可以看成是對(duì)K-Means算法的一種泛化,它只是在K-Means算法的基礎(chǔ)上增加了隨機(jī)擾動(dòng)和當(dāng)前輸入向量的影響。
本文對(duì)自組織粒子群聚類(SOPSC)算法進(jìn)行了初步的研究和實(shí)驗(yàn)分析。從直觀驗(yàn)證實(shí)驗(yàn)可以看出,SOPSC算法較K-Means算法穩(wěn)定。SOPSC算法繼承了PSO算法的全局尋優(yōu)特性,同時(shí)融合了S OM算法中的競(jìng)爭(zhēng)學(xué)習(xí)自組織特性,解決了傳統(tǒng)P SO算法復(fù)雜度偏高的缺點(diǎn)。從真實(shí)數(shù)據(jù)集的聚類比較實(shí)驗(yàn)可以看出,SOPSC算法在聚類精度上優(yōu)于傳統(tǒng)的K-Means算法,雖然前者算法時(shí)間和復(fù)雜度比后者高,但相較于傳統(tǒng)的PSO算法有了較大提高,粒子編碼復(fù)雜度有所降低,長(zhǎng)度由n×k變成了n。下一步將研究該算法用于實(shí)現(xiàn)聚類數(shù)目的自動(dòng)確定、孤立點(diǎn)檢測(cè)和實(shí)現(xiàn)不同形狀簇的聚類等問題。
[1]Omran M,Salman A,Engelbrecht A P.Image classification using particle swarm optimization[C]//Proceedings of the4th Asia-Pacific Conference on Simulated Evolution and Learning.Piscataway:IEEE Press,2002:370-374.
[2]李峻金,向陽,蘆英明,等.粒子群聚類算法綜述[J].計(jì)算機(jī)應(yīng)用研究,2009,26(12):4423-4427.
[3]Merwe D D.Data Clustering using Particle Swarm Optimization[C]//Proceedings of IEEE Congress on Evolutionary Computation. Canberra:IEEE Press,2003:215-220.
[4]劉春曉.基于SOM和PSO的聚類算法研究[D].成都:西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院,2009.
[5]Kohonen T.Self-organized Formation of Topologically Correct Feature Maps[J].Biological cybernetics,1982,43(1):59-69.
[責(zé)任編輯:田啟明]
A New Self-Organized PSO Clustering Algorithm
LIU Shihua, YE Zhanxiang, LIU Xianghua
(Information Technology Department, Wenzhou Vocational & Technical College, Wenzhou,325035, China)
A Self-organized PSO Clustering (SOPSC) algorithm based on competition learning was proposed against the complexity of PSO clustering algorithm. The algorithm coded one particle as a center of each cluster for clustering analysis. Through the competition learning of SOM algorithm, particles flew as self-organized manner directed by the inner similarity and dissimilarity between different clusters to achieve the goal of self-clustering. It overcame the complexity of particle coding and algorithm of traditional PSO clustering. It was tested that the algorithm improves the cluster accuracy and its stability and is not sensitive to the initial value and parameters.
PSO clustering; Competition learning; PSO; SOM; SOPSC
TP311.13
A
1671-4326(2015)03-0054-05
2014-05-14
溫州職業(yè)技術(shù)學(xué)院科研項(xiàng)目(WZY2014032)
劉世華(1978—),男,江西永豐人,溫州職業(yè)技術(shù)學(xué)院信息技術(shù)系講師,高級(jí)工程師,碩士;葉展翔(1971—),男,浙江溫州人,溫州職業(yè)技術(shù)學(xué)院信息技術(shù)系,高級(jí)工程師,碩士;劉向華(1980—),女,湖南隆回人,溫州職業(yè)技術(shù)學(xué)院信息技術(shù)系講師,碩士.