基于混沌振蕩粒子群優(yōu)化的FCM文本聚類方法

符保龍

(柳州職業(yè)技術(shù)學(xué)院 電子信息工程系，廣西 柳州 545006)

0 引言

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

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

1 FCM算法的基本原理

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

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

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

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

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

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

2 混沌因子和振蕩因子優(yōu)化的PSO算法基本原理

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

標(biāo)準(zhǔn)PSO算法更新粒子速度和位置的方程如下:

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

為了解決標(biāo)準(zhǔn)PSO算法易于陷入早熟的問題，引入一個振蕩環(huán)節(jié)，此時公式(1)可轉(zhuǎn)變?yōu)?

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

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

Step 1:令k=0，將待優(yōu)化的粒子xkj通過公式(8)轉(zhuǎn)換到區(qū)間［0，1］內(nèi);

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

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

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

Step 4:對Step3中得到的序列進(jìn)行評估，選取適應(yīng)度最高的粒子和當(dāng)前的粒子進(jìn)行比較，如果優(yōu)于當(dāng)前解則進(jìn)行替換，否則保留當(dāng)前粒子并令k=k+1，然后跳轉(zhuǎn)到Step2。

根據(jù)以上的討論，引入振蕩環(huán)節(jié)和混沌理論的PSO算法的步驟如下:

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

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

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

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

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

Step6:如果滿足設(shè)定的閾值或達(dá)到最大進(jìn)化代數(shù)，則輸出計算結(jié)果，算法結(jié)束，否則，跳轉(zhuǎn)到Step2。

3 基于混沌振蕩粒子群優(yōu)化的FCM算法

3.1 粒子編碼

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

3.2 適應(yīng)度函數(shù)

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

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

3.3 CCPSO－FCM算法的具體實現(xiàn)步驟

CCPSO－FCM算法的具體執(zhí)行步驟如下:

Step1:初始化算法的各種參數(shù)，如:聚類中心類別m、模糊加權(quán)指數(shù)b、粒子群規(guī)模N等;

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

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

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

Step5:執(zhí)行本文設(shè)計的混沌振蕩環(huán)節(jié)來更新粒子的速度和位置;

Step6:如果滿足設(shè)定的閾值或達(dá)到最大進(jìn)化代數(shù)，則輸出結(jié)果，算法結(jié)束，否則，跳轉(zhuǎn)到Step2。

4 實驗及結(jié)果分析

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

表1 CCPSO－FCM算法的實驗結(jié)果

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

表2 三種算法的對比實驗結(jié)果

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

5 總結(jié)

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

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

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

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

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

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