張春燕

(無錫科技職業(yè)學(xué)院，江蘇 無錫 214028)

人類已經(jīng)進(jìn)入大數(shù)據(jù)時(shí)代，每天產(chǎn)生海量數(shù)據(jù)，機(jī)器學(xué)習(xí)[1]是一類用于自動(dòng)化分析數(shù)據(jù)的工具的總稱。

作為機(jī)器學(xué)習(xí)的算法之一——聚類分析是一種典型的無監(jiān)督學(xué)習(xí)，用于對(duì)未知類別的樣本進(jìn)行劃分，將它們按照一定的規(guī)則劃分成若干個(gè)類簇，把相似(距離相近)的樣本聚在同一個(gè)類簇中，把不相似的樣本分為不同類簇，從而揭示樣本之間內(nèi)在的性質(zhì)以及相互之間的聯(lián)系規(guī)律。聚類算法在銀行、保險(xiǎn)、醫(yī)學(xué)、軍事等諸多領(lǐng)域有著廣泛的應(yīng)用[2]。K-Means算法[3]是基于劃分的聚類算法，是公認(rèn)的十大數(shù)據(jù)挖掘算法之一。

1 K-Means(K均值)聚類

算法步驟：

1) 首先我們選擇一些類/組，并隨機(jī)初始化它們各自的中心點(diǎn)。中心點(diǎn)是與每個(gè)數(shù)據(jù)點(diǎn)向量長(zhǎng)度相同的位置。這需要我們提前預(yù)知類的數(shù)量(即中心點(diǎn)的數(shù)量)。

2) 計(jì)算每個(gè)數(shù)據(jù)點(diǎn)到中心點(diǎn)的距離，數(shù)據(jù)點(diǎn)距離哪個(gè)中心點(diǎn)最近就劃分到哪一類中。

3) 計(jì)算每一類中心點(diǎn)作為新的中心點(diǎn)。

4) 重復(fù)以上步驟，直到每一類中心在每次迭代后變化不大為止。也可以多次隨機(jī)初始化中心點(diǎn)，然后選擇運(yùn)行結(jié)果最好的一個(gè)。

這個(gè)過程直到兩個(gè)計(jì)算結(jié)果不再變化，算法才收斂。從k-Means聚類的過程中，我們發(fā)現(xiàn)初始聚類中心對(duì)分類的影響很大，容易引起局部最優(yōu)。以離群值為聚類中心的聚類效果最差，且聚類間分離沒有得到有效的應(yīng)用。我們通過建立一個(gè)新的模型來解決這些問題。為了優(yōu)化新模型，引入了PSO算法。

2 PSO算法[4]

該算法將每個(gè)個(gè)體看作是在n維搜索空間中的一個(gè)沒有重量和體積的微粒,該微粒以一定的速度飛行在搜索空間中。飛行速度由個(gè)體和群體的飛行經(jīng)驗(yàn)進(jìn)行動(dòng)態(tài)調(diào)整。

設(shè)xi=(xi1,xi2,……,xid)為粒子i的當(dāng)前位置；

vi=(vi1,vi2,……,vid)為粒子i的當(dāng)前速度；

Pi=(Pi1,Pi2,……,Pid)代表粒子i的最佳適應(yīng)性值，即pbest；

Pg=(Pg1,Pg2,……,Pgd)代表粒子群的最佳適應(yīng)性值，即gbest。

粒子的速度更新見(1)和位置的更新見(2):

vij(t+1)=wvij(t)+c1r1j(t)[Pij(t)-xij(t)]+c2r2j(t)[Pgj(t)-xij(t)]

(1)

vij∈[-vmax,vmax]

xij(t+1)=xij(t)+vij(t+1)

(2)

c1,c2為加速常數(shù)，W為慣性權(quán)重。

PSO算法的缺點(diǎn)是容易出現(xiàn)早熟收斂，優(yōu)化性能因此降低, 近年來,很多研究人員對(duì)PSO進(jìn)行了研究并改進(jìn), 提出了算法的具體改進(jìn)方案。Sun教授等以智能優(yōu)化機(jī)制的基礎(chǔ)——算法的個(gè)體學(xué)習(xí)能力和社會(huì)學(xué)習(xí)能力，結(jié)合了物理中金屬導(dǎo)體自由電子具有的定向漂移運(yùn)動(dòng)方式和隨機(jī)無規(guī)則的熱運(yùn)動(dòng)方式,提出了一種改進(jìn)的PSO算法——隨機(jī)漂移粒子群(RDPSO)算法，該算法具有較強(qiáng)的全局搜索能力且不易出現(xiàn)早熟收斂。

3 RDPSO算法[5]

(3)

CJk為當(dāng)前種群中所有粒子個(gè)體的歷史最優(yōu)位置平均值(mbest)，m為種群規(guī)模,公式為

(4)

RDPSO算法中粒子速度和位置的更新公式為

(5)

(6)

隨機(jī)漂移粒子群的算法描述如下:

步驟1:給定了整體群體的大小, 粒子的位置和速度被初始化;

步驟2:通過公式(4)計(jì)算出所有粒子個(gè)體的歷史最優(yōu)位置平均值;

步驟3:根據(jù)目標(biāo)函數(shù)值,更新了粒子的全局最優(yōu)位置；

步驟4：根據(jù)目標(biāo)函數(shù)值，更新了粒子的局部最優(yōu)位置;

步驟5: 通過公式(5) 更新了粒子的速度；

步驟6：通過公式(6) 更新了粒子的位置；

步驟7: 如果滿足結(jié)束條件, 則程序結(jié)束并輸出結(jié)果，如果不滿足,轉(zhuǎn)入步驟 2繼續(xù)執(zhí)行。

4 RDPSO與K-Means算法相結(jié)合的混合集群技術(shù)[6-8]

給定了一個(gè)數(shù)據(jù)集 s，聚類的數(shù)目為 k，m為整個(gè)粒子群的種群數(shù)量。目標(biāo)是得到聚類數(shù)據(jù)集的聚類中心不再變化的 k 個(gè)聚類劃分。

步驟1： 數(shù)據(jù)集 s中隨機(jī)選擇 k 個(gè)中心點(diǎn)，作為粒子位置 Xi 的初值；

步驟2： Vi為粒子的初始化速度；

步驟3： 反復(fù)進(jìn)行m次，共生成種群規(guī)模為m的初始粒子群；

步驟4: 根據(jù)目標(biāo)函數(shù)值,更新粒子的全局最優(yōu)位置；

步驟5： 根據(jù)目標(biāo)函數(shù)值更新粒子的局部最優(yōu)位置;

步驟6: 根據(jù)RDPSO算法中的(5)和(6)公式更新粒子的速度和位置;

步驟7: 對(duì)于選中的粒子，按照 K-Means聚類算法進(jìn)行優(yōu)化；

步驟8： 根據(jù)粒子的聚類中心編碼作為初始值，該粒子的新的聚類劃分根據(jù)最近鄰法則來確定；

步驟9：結(jié)束條件為找到好的位置或者達(dá)到最大迭代次數(shù)，如果達(dá)到了結(jié)束條件則更新粒子并結(jié)束程序，如果不滿足則轉(zhuǎn)向步驟8繼續(xù)執(zhí)行。

5 實(shí)驗(yàn)

為了測(cè)試我們的實(shí)驗(yàn)有效性，我們選擇了iris數(shù)據(jù)集150條記錄、BreastCancer數(shù)據(jù)集569條記錄、creditcard數(shù)據(jù)集284807條記錄作為測(cè)試樣本集，RDPSO-K-Means算法和PSO-K-Means算法進(jìn)行了比較。PSO-K-Means聚類性能的結(jié)果如第一列所示，我們的算法聚類性能的結(jié)果如表1第二列所示。XB指標(biāo)是尋找類內(nèi)緊湊度和類間分離度之間的某個(gè)平衡點(diǎn)。常用于評(píng)價(jià)分類模型的好壞的一個(gè)常用評(píng)價(jià)標(biāo)準(zhǔn)就是Precision和Recall的加權(quán)調(diào)和平均F-Measure。在f-measure函數(shù)中，當(dāng)參數(shù)α=1時(shí)，F(xiàn)1綜合了P和R的結(jié)果，當(dāng)F1較高時(shí)則能說明試驗(yàn)方法比較有效。

表1 PSO-K-Means算法和RDPSO-k-Means算法比較

本文采用總平均計(jì)算時(shí)間、總XB指數(shù)、方差和f-measure四個(gè)參數(shù)進(jìn)行結(jié)果分析。其中研究重點(diǎn)是盡量減少總平均計(jì)算時(shí)間、總XB指數(shù)和方差和，增加f-measure值。實(shí)驗(yàn)結(jié)果證明本文所應(yīng)用的RDPSO算法與K-Means聚類算法相結(jié)合的混合集群技術(shù)性能明顯優(yōu)于PSO算法與K-Means聚類算法相結(jié)合的混合集群技術(shù)。

6 結(jié)論

K-Means算法經(jīng)常由于初始值的選擇問題而陷入局部最優(yōu)解，而常見的PSO算法又容易陷入粒子群的早熟收斂，本文通過將聚類問題建立一種新的模型，并將RDPSO算法與K-Means算法相結(jié)合技術(shù)巧妙地引入到了目標(biāo)函數(shù)中，充分考慮了集群的緊致性和群間的分離，從而使我們可以獲得最終的聚類結(jié)果，從實(shí)驗(yàn)結(jié)果上取得了良好的效果。