RDPSO算法與K-Means聚類算法相結(jié)合的混合集群技術(shù)

張春燕

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

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

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

1 K-Means(K均值)聚類

算法步驟：

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

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

3) 計算每一類中心點作為新的中心點。

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

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

2 PSO算法[4]

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

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

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

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

3 RDPSO算法[5]

(3)

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

(4)

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

(5)

(6)

隨機漂移粒子群的算法描述如下:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 實驗

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

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

本文采用總平均計算時間、總XB指數(shù)、方差和f-measure四個參數(shù)進行結(jié)果分析。其中研究重點是盡量減少總平均計算時間、總XB指數(shù)和方差和，增加f-measure值。實驗結(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ù)巧妙地引入到了目標函數(shù)中，充分考慮了集群的緊致性和群間的分離，從而使我們可以獲得最終的聚類結(jié)果，從實驗結(jié)果上取得了良好的效果。