基于混沌振蕩粒子群優化的FCM文本聚類方法

符保龍

(柳州職業技術學院 電子信息工程系，廣西 柳州 545006)

0 引言

Internet包含了大量的數據，如何快速的尋找到用戶關心的信息是當前數據挖掘研究的一個重要問題。模糊聚類分析是一種無監督的方法，它根據一定的規則自動對數據進行分類。特別是模糊C均值聚類(Fuzzy C－Mean，簡稱FCM)算法，它具有模糊處理能力，算法簡單、運算速度快，在很多領域得到了大量應用。FCM算法聚類效果受初始值影響較大，且算法采用梯度下降對目標函數進行優化，而目標函數具有多峰值，使得算法易于陷入局部極值。很多專家學者對FCM算法進行了改進，文獻［1］提出了一種NSFCM算法，該方法通過計算樣本的平均信息熵確定最終的聚類數，使用密度函數設定FCM算法的初始聚類中心，具有較高的聚類精度和執行效率;文獻［2］提出了一種基于粒子群算法的模糊均值聚類方法，該方法利用粒子群優化算法(Particle Swarm Optimization，簡稱PSO)優化模糊均值聚類算法，獲得了較好的文本聚類效果，但PSO算法自身的缺點也影響了FCM算法的聚類效果;文獻［3］提出了一種基于多樣性策略的粒子群算法，該算法設計了一種吸引和排斥機制對粒子的速度進行更新，同時引入物理學中的反彈理論設計了一種反彈機制，該機制能將解空間外的粒子反彈回解空間內，充實了群體粒子的多樣性，有利于算法搜索到全局最優解。

在文獻［1－3］的啟發下，為了解決FCM算法受聚類中心初始值影響大的問題，同時也為了避免標準PSO算法易于陷入早熟的缺點，本文引入混沌思想對PSO算法進行優化，在尋優的過程中利用一個振蕩環節來提升PSO算法的全局收斂性。把改進的PSO算法和FCM算法相結合，提出一種基于混沌振蕩粒子群優化的模糊C均值聚類算法(Chaos Concussion Particle Swarm Optimization Fuzzy C－Mean Algorithm，簡稱CCPSO－FCM)。實驗結果表明，CCPSO－FCM算法運行速度更快，對大樣本的數據具有更好的聚類效果。

1 FCM算法的基本原理

FCM算法是在經典C均值聚類算法的基礎上發展而來的，與C均值聚類算法不同在于FCM引入隸屬度的概念，樣本中的數據點通過隸屬度來進行歸類。設有樣本集X={x1，x2，…，xn}，根據要求把樣本集X劃分m類，m是常數且m＞1。如果第i個樣本點屬于第i類的隸屬度用uij表示，且0≤uij≤1，此時X就可以用模糊矩陣U來表示，即:U=(uij)。當滿足條件0＜uij＜n，此時FCM的目標函數就可以定義為:

其中Aj(j=1，2，…，m)表示樣本的聚類中心，b(b＞1)是模糊指數。

公式(1)的約束條件為:

在公式(2)的約束下，通過引入拉格朗日乘子求解公式(1)可得:

在公式(3)、(4)中，i=1，2，…，m，j=1，2，…，n。

FCM算法的思想就是通過迭代公式(3)和公式(4)，使得目標函數j(u，A)最小。FCM每一次迭代都使得目標函數j(u，A)減小，這種梯度下降的方式使算法易于陷入局部極小值，特別是樣本數量較大的時候，陷入局部極值的問題更加明顯。而且這種算法的目標函數j(u，A)可能有多個極值，聚類初始值的選取對最終聚類的結果會產生很大影響。

2 混沌因子和振蕩因子優化的PSO算法基本原理

PSO算法源于對鳥群尋找食物行為的觀察研究，它是一種全局尋優方法，具有結構簡單、速度快且具備并行搜索能力，對問題的求解精度高。但PSO算法也存在學習因子不穩定的問題，該原因將導致群體內的個體在某個局部過多的徘徊，此時群體內的其它個體將會向同一位置聚集，從而使算法陷入早熟。針對PSO算法存在的問題，我們引入一個振蕩環節來提升PSO算法的全局搜索性能［4－5］，利用混沌理論來優化PSO算法的局部搜索能力。

標準PSO算法更新粒子速度和位置的方程如下:

其中，w稱為慣性權重，一般其值都是從0.9線性變化到0.4;c1=c2=2，它們稱為加速常數;r1和r2是兩個隨機數，且r1∈［0，1］、r2∈［0，1］;pbest(t)和gbest(t)分別表示t時刻粒子群中個體的最優值和全局最優值。

為了解決標準PSO算法易于陷入早熟的問題，引入一個振蕩環節，此時公式(1)可轉變為:

在公式(7)中，ξ1和ξ2稱為振蕩系數，它們的值隨著進化代數的不同取不同的值，以此來保證PSO算法能保持種群的收斂性和多樣性，從而保證算法全局搜索和局部搜索的性能。為了能更好的描述問題，我們假定g表示當前進化代數，Gmax表示算法設定的最大進化代數，ξ1和ξ2的取值分兩種情況:

為了能進一步保證PSO算法的多樣性，我們還引入了混沌理論對粒子的pbest和gbest進行優化，具體優化步驟如下:

Step 1:令k=0，將待優化的粒子xkj通過公式(8)轉換到區間［0，1］內;

其中i=1，2，…，n，j=1，2，…，m，第j維粒子搜索所能達到的上、下界分別用xmin，j和xmax，j表示;

Step 2:把Step1得到的數據用Logistic函數映射成為混沌系列:

Step 3:利用公式(10)對混沌變量sk+1j進行映射，經過轉換后xk+1j稱為決策變量:

Step 4:對Step3中得到的序列進行評估，選取適應度最高的粒子和當前的粒子進行比較，如果優于當前解則進行替換，否則保留當前粒子并令k=k+1，然后跳轉到Step2。

根據以上的討論，引入振蕩環節和混沌理論的PSO算法的步驟如下:

Step1:隨機初始化種群中粒子的位置，利用公式(7)計算粒子的速度;

Step2:計算種群內所有粒子的適應度，并保存各自的位置和速度，把適應度值最高的粒子的位置和適應值保存在gbest中;

Step3:更新所有粒子的速度和位置;

Step4:再次計算所有粒子的適應度并降序排序，保留前面20%的粒子;

Step5:按本文所討論的混沌步驟更新粒子的pbest和gbest;

Step6:如果滿足設定的閾值或達到最大進化代數，則輸出計算結果，算法結束，否則，跳轉到Step2。

3 基于混沌振蕩粒子群優化的FCM算法

3.1 粒子編碼

CCPSO－FCM算法的目標是確定最優的聚類中心，因此算法中的粒子采用實數編碼，每一個粒子分別表示每一個待確定的聚類中心Aj(j=1，2，…，m)，對于一個樣本集X={x1，x2，…，xn}來說，如果用aij來表示第i個粒子的第j個聚類中心，則樣本集X的聚類中心可以形成一個集合Zi=(ai1，ai2，…，aim)。

3.2 適應度函數

為了簡化問題，我們使用如下的函數作為CCPSO－FCM算法的適應度函數。即:

公式(11)表明，如果J(u，A)的值越小，則粒子群中個體適應度值越大，即CCPSO－FCM算法的聚類效果越好。

3.3 CCPSO－FCM算法的具體實現步驟

CCPSO－FCM算法的具體執行步驟如下:

Step1:初始化算法的各種參數，如:聚類中心類別m、模糊加權指數b、粒子群規模N等;

Step2:隨機生成粒子的初始位置Zi并初始化它們的速度vi;

Step3:根據公式(3)、(4)計算各樣本的隸屬度;

Step4:利用公式(11)計算所有粒子的適應度;

Step5:執行本文設計的混沌振蕩環節來更新粒子的速度和位置;

Step6:如果滿足設定的閾值或達到最大進化代數，則輸出結果，算法結束，否則，跳轉到Step2。

4 實驗及結果分析

為了驗證CCPSO－FCM算法的有效性，我們從復旦大學文本分類語料庫中隨機選取了體育、軍事、房地產、經濟以及科技等5個大類，每一類文章選200篇，共1 000篇文獻進行實驗。在實驗前，必須先對所有的文檔進行分詞、詞頻統計、特征選擇等預處理，最后得到的文本特征向量維數為4 165。實驗的硬件配置為酷睿i3CPU 2.8 GHz、4 G內存。軟件環境為64位Win7系統，采用Matlab7編程實現。實驗所采用的相關參數的值設置如下:模糊指數b=2、最大進化代數Gmax=500，粒子群規模N=20。由于涉及到5類文檔，因此本實驗中選擇的聚類中心數m=5，實驗結果采用準確率和召回率這兩個評價指標。經過多次運行，取結果最好的一次，如表1所示。

表1 CCPSO－FCM算法的實驗結果

從表1可以看到，CCPSO－FCM算法具有較高的準確率和召回率。為了能進一步證明CCPSO－FCM算法的性能，我們把它與PSO－FCM算法和FCM算法在經濟類文檔上進行了對比實驗，結果如表2所示。

表2 三種算法的對比實驗結果

從表2中可以看出，沒有經過優化的FCM算法性能最差，主要原因在于聚類中心的初始值是隨機的，對算法的性能影響很大，經過PSO優化的FCM算法相對FCM算法在性能上有所提升，這主要是因為在聚類中心的初始值經過PSO算法優化后趨于合理。本文提出的CCPSO－FCM算法明顯要優于其它兩種算法，這主要得益于改進算法設計的振蕩環節增加了粒子種群的多樣性，同時引入的混沌搜索環節能有效保證粒子群能搜索到局部極值，保證了算法的收斂性。

5 總結

本文提出了基于混沌振蕩粒子群優化的模糊C均值聚類方法，該方法在標準PSO算法中設計了一個振蕩環節，同時引入混沌理論來進一步增加粒子群的多樣性和收斂性。將改進后的PSO算法和FCM算法相互結合，并應用于文本挖掘中。仿真實驗表明，相對于PSO－FCM算法和FCM算法，CCPSO－FCM算法具有良好的全局搜索能力和收斂速度，有效提升了傳統FCM算法的聚類效果，對文本挖掘算法是一種有益的補充。

［1］劉志勇，耿新青.基于模糊聚類的文本挖掘算法［J］.計算機工程，2009，35(5):45－49.

［2］葉吉祥，林泉.基于粒子群算法的文檔模糊均值聚類分析［J］.計算機工程與設計，2009，30(6):1 446－1 448.

［3］徐剛，楊玉群，劉斌斌，等.一種基于多樣性策略的粒子群算法［J］.南昌大學學報(理科版)，2013，37(1):17－21.

［4］耿立艷，趙鵬，張占福.基于二階振蕩微粒群最小二乘支持向量機的物流需求預測［J］.計算機應用研究，2012，29(7):2 558－2 560.

［5］胥小波，鄭康峰，李丹，等.新的混沌粒子群優化算法［J］.通信學報，2012，33(1):24－30.