基于PCA優(yōu)化的PSO-FCM聚類(lèi)算法①

陳 誠(chéng),劉振宇

(南華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,衡陽(yáng) 421001)

作為傳統(tǒng)聚類(lèi)算法模糊C-均值聚類(lèi)算法(Fuzzy C- Mean clustering algorithm,FCM)的一種優(yōu)化算法,引入了粒子群優(yōu)化算法(Particle Swam Optimization,PSO),粒子群模糊聚類(lèi)算法(Particle Swarm-based Fuzzy Clustering algorithms,PSO-FCM),通過(guò)PSO 算法的收斂速度快,粒子收斂由自身最優(yōu)位置和群體最優(yōu)位置相結(jié)合,在一定程度上解決了FCM 對(duì)初始值敏感,對(duì)噪聲數(shù)據(jù)敏感,容易陷入局部最優(yōu)解的缺點(diǎn).如今,隨著數(shù)據(jù)量多樣化,復(fù)雜化,多類(lèi)別化,PSOFCM 只是單一優(yōu)化初始聚類(lèi)中心選取問(wèn)題,沒(méi)有合理的限制粒子的移動(dòng),并不能更好優(yōu)化好FCM 算法面對(duì)多聚類(lèi)問(wèn)題時(shí)[1-7].

為了解決上述問(wèn)題,引入主成分分析(Principal Component Analysis,PCA),本文提出基于PCA 優(yōu)化的粒子群模糊聚類(lèi)算法(PCA-PSO-FCM),通過(guò)PCA 對(duì)數(shù)據(jù)各維度的分析和評(píng)定綜合給出一個(gè)權(quán)重值,粒子各維度會(huì)根據(jù)該調(diào)整權(quán)重速度和方向.本文詳細(xì)介紹了PCA-PSO-FCM,并且與FCM 和PSO-FCM 進(jìn)行了實(shí)驗(yàn)結(jié)果的比對(duì),從實(shí)驗(yàn)上來(lái)看,本文的算法在多種群聚類(lèi)問(wèn)題上性能更好,是一種很有潛力的聚類(lèi)算法.

本文結(jié)構(gòu)如下:第1 部分主要對(duì)已有的算法的研究成果進(jìn)行簡(jiǎn)要分析總結(jié);第2 部分對(duì)于本文的優(yōu)化算法進(jìn)行詳細(xì)說(shuō)明;第3 部分說(shuō)明實(shí)驗(yàn)過(guò)程相關(guān)細(xì)節(jié),設(shè)定參數(shù)以及實(shí)驗(yàn)結(jié)果的分析;第4 部分總結(jié)全文.

1 算法介紹

PSO-FCM 算法是模糊均值聚類(lèi)算法基礎(chǔ)上的優(yōu)化算法,傳統(tǒng)的模糊C 均值算法的結(jié)果精度,對(duì)初始中心的選取有很?chē)?yán)格的要求,并且容易陷入局部最優(yōu)解.為了解決這個(gè)問(wèn)題,國(guó)內(nèi)許多學(xué)者,利用具有集體智能的粒子群優(yōu)化算法,與傳統(tǒng)模糊C 均值算法結(jié)合.利用PSO 算法求解初始聚類(lèi)中心,進(jìn)而優(yōu)化了FCM 依賴(lài)初始中心的問(wèn)題;利用PSO 算法中,粒子個(gè)體與粒子群體之間關(guān)系,粒子整體移動(dòng)的速度可以調(diào)節(jié),進(jìn)而降低了FCM 容易陷入最優(yōu)解的可能性.

1.1 PSO-FCM 算法

PSO-FCM 算法是基于數(shù)據(jù)樣本之間的模隸屬矩陣建立的聚類(lèi)算法.算法的核心思想是:n個(gè)文本樣本為X=(x1,x2,···,xn),劃分為C =(c1,c2,···,cn),p個(gè)聚類(lèi)中心,計(jì)算出每個(gè)文本的隸屬度 μij,μij表示第j個(gè)樣本隸屬于第i個(gè)樣本的隸屬度.

根據(jù)每個(gè)樣本的隸屬度值計(jì)算出適應(yīng)度函數(shù)值:

式中,m是加權(quán)指標(biāo),m＞1,xj-νi表示樣本xj到第i個(gè)樣本中心的聚類(lèi),PSO-FCM 算法適應(yīng)度函數(shù)Jm值越小說(shuō)明性能越好;ρi是粒子最優(yōu)適應(yīng)度的位置,σi是群體最優(yōu)適應(yīng)度函數(shù),c1和c2是 學(xué)習(xí)因子;r1和r2是[0,1]之間的隨機(jī)因子數(shù),?是慣性權(quán)重.

2 算法優(yōu)化

2.1 PCA 算法

隨著數(shù)據(jù)量的爆發(fā)和激增,數(shù)據(jù)類(lèi)型的增多,數(shù)據(jù)復(fù)雜程度的加深,PSO-FCM 算法的性能無(wú)法完全發(fā)揮.于是近年來(lái)有學(xué)者對(duì)該算法進(jìn)行了再度優(yōu)化,陳壽文[8]提出利用混沌粒子融合粒子群模糊聚類(lèi)算法(CCPSOFCM),余曉東等[9]利用直覺(jué)模糊核優(yōu)化粒子群模糊聚類(lèi)算法.雷浩轄等[10]利用遺傳算法(GA)與PSO 混合優(yōu)化的遺傳粒子群模糊聚類(lèi)(GA-PSO-FCM).這些學(xué)者都是針對(duì)于PSO-FCM 算法依賴(lài)初始解這個(gè)問(wèn)題上進(jìn)行的優(yōu)化.算法核心是通過(guò)比較隸屬度,移動(dòng)該粒子并決定屬于哪一類(lèi),但是在各維度上面的移動(dòng)上并沒(méi)有一個(gè)主次之分,在各維度上的移動(dòng)全部是隨機(jī)因子數(shù)決定.隨著聚類(lèi)中心數(shù)量的增加,隸屬度矩陣上,各聚類(lèi)中心隸屬度值接近,粒子各維度移動(dòng)不受限,這樣導(dǎo)致部分粒子可能會(huì)被分入,與正確聚類(lèi)中心隸屬度值接近的錯(cuò)誤聚類(lèi)中心中的問(wèn)題.在維度增加,聚類(lèi)中數(shù)量增加,這個(gè)問(wèn)題會(huì)越來(lái)越頻繁出現(xiàn).

為了在一定程度降低上面的問(wèn)題出現(xiàn)的可能性,本文引入了PCA[11-13]算法對(duì)原算法進(jìn)行優(yōu)化,PCA 是一種統(tǒng)計(jì)分析的方法,通過(guò)正交變換將具有一定相關(guān)性的向量轉(zhuǎn)為彼此正交,且互相獨(dú)立的一維新向量(即主成分).每個(gè)主成分都是初始變量的線(xiàn)性組合,沒(méi)有冗余信息,構(gòu)成空間的正交基.主成分分析法可以簡(jiǎn)化統(tǒng)計(jì)數(shù)據(jù),揭示特征變量之間的關(guān)系.在本文優(yōu)化中并沒(méi)直接對(duì)數(shù)據(jù)進(jìn)行降維,根據(jù)PCA 中主成分貢獻(xiàn)率公式:計(jì)算出樣本空間各維度之間的貢獻(xiàn)率η=(η1,η2,···,ηn),進(jìn)一步優(yōu)化PSO-FCM 算法中速度的的迭代公式:

2.2 優(yōu)化算法實(shí)現(xiàn)

?

?

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

3.1 實(shí)驗(yàn)數(shù)據(jù)處理

在測(cè)試算法的性能,本文選擇UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中,Wine,Breast Tissue,Dermatology,以及Glass Identification,每一組數(shù)據(jù)都進(jìn)行了清洗,并且都做了使用線(xiàn)性函數(shù)歸一化將數(shù)據(jù)集進(jìn)行標(biāo)準(zhǔn)化處理.各維度的權(quán)重是通過(guò)主成分分析得出各維度貢獻(xiàn)率,數(shù)據(jù)集參見(jiàn)表1 數(shù)據(jù)集表.

表1 實(shí)驗(yàn)數(shù)據(jù)集表

3.2 模型評(píng)價(jià)指標(biāo)

通過(guò)對(duì)比本算法與K-近鄰(KNN),FCM,PSO-FCM在數(shù)據(jù)集訓(xùn)練的結(jié)果.本文采取的評(píng)價(jià)算法性能的指標(biāo):調(diào)整互信息(Adjusted Mutual Information based scores,AMI);調(diào)整蘭德系數(shù)(Adjusted Rand Index,ARI);FM 指數(shù)(Fowlkes and Mallows Index,FMI).3 個(gè)指標(biāo)都是評(píng)價(jià)聚類(lèi)算法性能的外部指標(biāo),通過(guò)聚類(lèi)結(jié)果與參考數(shù)據(jù)集的標(biāo)簽比較而獲得,這些外部指標(biāo)度量的結(jié)果都在[0,1]之間,指標(biāo)值越接近1 說(shuō)明聚類(lèi)的結(jié)果越好.

3.3 檢驗(yàn)?zāi)Ｐ托阅?/h3>

圖1 和圖2 根據(jù)Breast Tissue 數(shù)據(jù)集的主成分貢獻(xiàn)率所選擇的平面圖,圖1 是本文算法在數(shù)據(jù)集上,兩個(gè)高貢獻(xiàn)率維度的圖像,圖2 是PSO-FCM 算法,從圖中可以明顯的對(duì)比出來(lái),在相同數(shù)據(jù)集,相同維度下的本文算法聚類(lèi)的結(jié)果明顯優(yōu)于PSO-FCM,PSO-FCM算法在數(shù)據(jù)比較集中的區(qū)域,對(duì)于多個(gè)聚類(lèi)中心的交界處的數(shù)據(jù)敏感程度低,無(wú)法有效的給出數(shù)據(jù)的準(zhǔn)確的聚類(lèi)中心,相反本文算法面對(duì)這類(lèi)粒子,敏感度高,能夠更加有效的且準(zhǔn)確的給出聚類(lèi)中心.粒子各維度之間無(wú)差別移動(dòng),在多個(gè)聚類(lèi)中心的粒子會(huì)被錯(cuò)誤的移動(dòng)到不正確的聚類(lèi)中心中:本算法對(duì)于不同貢獻(xiàn)率的空間中,采取相對(duì)應(yīng)的移動(dòng)權(quán)重的能夠較低粒子錯(cuò)誤移動(dòng)的概率,說(shuō)明該策略效果是顯著的.

由表2 和表3 中可以看出,本文算法只是在Dermatology 數(shù)據(jù)集上的AMI 這一個(gè)指標(biāo)上落后KNN,這是因?yàn)樽鳛橛簿垲?lèi)算法,隨著聚類(lèi)中心數(shù)目的增加,每一個(gè)數(shù)據(jù)只能存在單一的一個(gè)聚類(lèi)結(jié)果,不會(huì)存在多種可能性,聚類(lèi)的結(jié)果純度更高.KNN 算法性能很穩(wěn)定,在隨著聚類(lèi)中心增多,性能反超F(xiàn)CM,PSO-FCM 兩個(gè)算法,但是綜合指標(biāo)上,本文的算法總體仍是優(yōu)于FCM,PSO-FCM,KNN 這3 個(gè)算法.FCM 采用隨機(jī)初始的中心,指標(biāo)隨著聚類(lèi)中心的增多,算法性能下降明顯.PSOFCM 采取使用PSO 算法得出的初始中心,明顯的發(fā)現(xiàn),綜合性能上面性能上優(yōu)于FCM,但是算法精度提升不高.

圖1 PCA-PSO-FCM 高貢獻(xiàn)率圖

圖2 PSO-FCM 高貢獻(xiàn)率圖

隨著各數(shù)據(jù)集的聚類(lèi)中心的增加,聚類(lèi)的問(wèn)題的復(fù)雜化,從表中各指標(biāo)上,側(cè)面體現(xiàn)本算法面對(duì)多個(gè)聚類(lèi)中心的之間的粒子敏感度更高,分辨能力更強(qiáng).總體上指標(biāo)上來(lái)看,本文算法性能更強(qiáng),魯棒性更高,適用面更廣.

4 結(jié)論與展望

采取PCA 優(yōu)化的PSO-FCM 算法,通過(guò)主貢獻(xiàn)率加權(quán)的限制,控制粒子各維度上的移動(dòng),降低多聚類(lèi)群交界粒子的敏感性,增強(qiáng)了粒子的搜索能力,降低粒子被不正確粒子群吸入,能夠一定程度上,跳出局部最優(yōu),有效的彌補(bǔ)了傳統(tǒng)PSO-FCM 性能上的不足,增加算法精度,增強(qiáng)算法的魯棒性,相對(duì)于其他算法,在綜合指標(biāo)上面更優(yōu),部分指標(biāo)上有著更好的精度,適用面更廣,魯棒性更強(qiáng).接下來(lái)的工作會(huì)將優(yōu)化算法應(yīng)用到更多領(lǐng)域.

表2 算法性能表1

表3 算法性能表2