基于PCA優化的PSO-FCM聚類算法①

陳 誠,劉振宇

(南華大學 計算機科學與技術學院,衡陽 421001)

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

為了解決上述問題,引入主成分分析(Principal Component Analysis,PCA),本文提出基于PCA 優化的粒子群模糊聚類算法(PCA-PSO-FCM),通過PCA 對數據各維度的分析和評定綜合給出一個權重值,粒子各維度會根據該調整權重速度和方向.本文詳細介紹了PCA-PSO-FCM,并且與FCM 和PSO-FCM 進行了實驗結果的比對,從實驗上來看,本文的算法在多種群聚類問題上性能更好,是一種很有潛力的聚類算法.

本文結構如下:第1 部分主要對已有的算法的研究成果進行簡要分析總結;第2 部分對于本文的優化算法進行詳細說明;第3 部分說明實驗過程相關細節,設定參數以及實驗結果的分析;第4 部分總結全文.

1 算法介紹

PSO-FCM 算法是模糊均值聚類算法基礎上的優化算法,傳統的模糊C 均值算法的結果精度,對初始中心的選取有很嚴格的要求,并且容易陷入局部最優解.為了解決這個問題,國內許多學者,利用具有集體智能的粒子群優化算法,與傳統模糊C 均值算法結合.利用PSO 算法求解初始聚類中心,進而優化了FCM 依賴初始中心的問題;利用PSO 算法中,粒子個體與粒子群體之間關系,粒子整體移動的速度可以調節,進而降低了FCM 容易陷入最優解的可能性.

1.1 PSO-FCM 算法

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

根據每個樣本的隸屬度值計算出適應度函數值:

式中,m是加權指標,m＞1,xj-νi表示樣本xj到第i個樣本中心的聚類,PSO-FCM 算法適應度函數Jm值越小說明性能越好;ρi是粒子最優適應度的位置,σi是群體最優適應度函數,c1和c2是 學習因子;r1和r2是[0,1]之間的隨機因子數,?是慣性權重.

2 算法優化

2.1 PCA 算法

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

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

2.2 優化算法實現

?

?

3 實驗分析

3.1 實驗數據處理

在測試算法的性能,本文選擇UCI 機器學習數據庫中,Wine,Breast Tissue,Dermatology,以及Glass Identification,每一組數據都進行了清洗,并且都做了使用線性函數歸一化將數據集進行標準化處理.各維度的權重是通過主成分分析得出各維度貢獻率,數據集參見表1 數據集表.

表1 實驗數據集表

3.2 模型評價指標

通過對比本算法與K-近鄰(KNN),FCM,PSO-FCM在數據集訓練的結果.本文采取的評價算法性能的指標:調整互信息(Adjusted Mutual Information based scores,AMI);調整蘭德系數(Adjusted Rand Index,ARI);FM 指數(Fowlkes and Mallows Index,FMI).3 個指標都是評價聚類算法性能的外部指標,通過聚類結果與參考數據集的標簽比較而獲得,這些外部指標度量的結果都在[0,1]之間,指標值越接近1 說明聚類的結果越好.

3.3 檢驗模型性能

圖1 和圖2 根據Breast Tissue 數據集的主成分貢獻率所選擇的平面圖,圖1 是本文算法在數據集上,兩個高貢獻率維度的圖像,圖2 是PSO-FCM 算法,從圖中可以明顯的對比出來,在相同數據集,相同維度下的本文算法聚類的結果明顯優于PSO-FCM,PSO-FCM算法在數據比較集中的區域,對于多個聚類中心的交界處的數據敏感程度低,無法有效的給出數據的準確的聚類中心,相反本文算法面對這類粒子,敏感度高,能夠更加有效的且準確的給出聚類中心.粒子各維度之間無差別移動,在多個聚類中心的粒子會被錯誤的移動到不正確的聚類中心中:本算法對于不同貢獻率的空間中,采取相對應的移動權重的能夠較低粒子錯誤移動的概率,說明該策略效果是顯著的.

由表2 和表3 中可以看出,本文算法只是在Dermatology 數據集上的AMI 這一個指標上落后KNN,這是因為作為硬聚類算法,隨著聚類中心數目的增加,每一個數據只能存在單一的一個聚類結果,不會存在多種可能性,聚類的結果純度更高.KNN 算法性能很穩定,在隨著聚類中心增多,性能反超FCM,PSO-FCM 兩個算法,但是綜合指標上,本文的算法總體仍是優于FCM,PSO-FCM,KNN 這3 個算法.FCM 采用隨機初始的中心,指標隨著聚類中心的增多,算法性能下降明顯.PSOFCM 采取使用PSO 算法得出的初始中心,明顯的發現,綜合性能上面性能上優于FCM,但是算法精度提升不高.

圖1 PCA-PSO-FCM 高貢獻率圖

圖2 PSO-FCM 高貢獻率圖

隨著各數據集的聚類中心的增加,聚類的問題的復雜化,從表中各指標上,側面體現本算法面對多個聚類中心的之間的粒子敏感度更高,分辨能力更強.總體上指標上來看,本文算法性能更強,魯棒性更高,適用面更廣.

4 結論與展望

采取PCA 優化的PSO-FCM 算法,通過主貢獻率加權的限制,控制粒子各維度上的移動,降低多聚類群交界粒子的敏感性,增強了粒子的搜索能力,降低粒子被不正確粒子群吸入,能夠一定程度上,跳出局部最優,有效的彌補了傳統PSO-FCM 性能上的不足,增加算法精度,增強算法的魯棒性,相對于其他算法,在綜合指標上面更優,部分指標上有著更好的精度,適用面更廣,魯棒性更強.接下來的工作會將優化算法應用到更多領域.

表2 算法性能表1

表3 算法性能表2