一種改進(jìn)粒子群和K-means結(jié)合的聚類算法

摘要：本文首先提出一種基于適應(yīng)度權(quán)重的改進(jìn)粒子群算法，該算法能夠根據(jù)群中粒子收斂情況動態(tài)地調(diào)整構(gòu)成粒子運(yùn)行速度。然后將已提出的改進(jìn)粒子群算法與K-means算法結(jié)合，使結(jié)合后的聚類算法取改進(jìn)粒子群算法之所長，補(bǔ)K-means算法之所短。通過分析證明，在算法的有效性和算法效率上比其他算法都有明顯的提高。

關(guān)鍵詞：粒子群算法；聚類算法

1. 引言

粒子群優(yōu)化(Particle Swarm Optimization，PSO)是一種群智能(Swarm Intelligence)方法的進(jìn)化計(jì)算技術(shù)。其具有原理簡單，便于理解，算法容易實(shí)現(xiàn)、操作參數(shù)少、易于收斂等優(yōu)點(diǎn)。聚類分析(Cluster Analysis)利用數(shù)據(jù)間的相似性對數(shù)據(jù)進(jìn)行分類。使得不同類別中的數(shù)據(jù)盡可能相異，而同一類數(shù)據(jù)之間盡可能相似，從而發(fā)現(xiàn)數(shù)據(jù)其中隱含的、有用的信息[1]。各種聚類算法中，K-means算法憑借其便于理解，算法簡單易行，以及收斂速度快等特點(diǎn)，成為了最著名、最常用的聚類算法。但是其本身具有易陷入局部最優(yōu)解，處理海量數(shù)據(jù)效率低下等不足。如何改進(jìn)K-means算法，一直以來受到了廣泛的關(guān)注和研究。

2. 基于適應(yīng)度權(quán)重的改進(jìn)粒子群算法

基于對粒子群優(yōu)化算法的分析，本文將引入粒子運(yùn)動適應(yīng)度權(quán)重這一概念，并以此為核心提出一種改進(jìn)的粒子群優(yōu)化算法FWPSO。FWPSO將每個粒子的適應(yīng)度和整個粒子群粒子的適應(yīng)度進(jìn)行計(jì)算，得出粒子的適應(yīng)度權(quán)重，并將該權(quán)重引入到粒子速度的計(jì)算中。雖然增加了一定的計(jì)算量，但能夠使粒子的運(yùn)動速度和方向更加合理，從而提高算法收斂解的精度，有效避免算法陷入局部最優(yōu)解，提高算法的性能。

2.1 適應(yīng)度權(quán)重

本文通過測算每次迭代時粒子群中粒子適應(yīng)度的差異情況，以此得出粒子群適應(yīng)度權(quán)重，并將其作為判斷粒子群收斂程度的標(biāo)準(zhǔn)。粒子群適應(yīng)度權(quán)重 定義如下：

其中，t為迭代的次數(shù)；n為粒子群粒子個數(shù)；σ(t)為第t次次迭代時的適應(yīng)度權(quán)重；fi(t)為第t次循環(huán)時i個粒子的適應(yīng)度，favg(t)為第t次循環(huán)時所有粒子的適應(yīng)度均值。

2.2 基于適應(yīng)度權(quán)重改進(jìn)的慣性權(quán)重

在標(biāo)準(zhǔn)粒子群優(yōu)化算法中，慣性權(quán)重w隨迭代次數(shù)線性減小，而不是根據(jù)粒子群收斂情況進(jìn)行動態(tài)調(diào)整，并不適合粒子群實(shí)際的情況。本文將適應(yīng)度權(quán)重引入到慣性權(quán)重中，具體定義為：

其中：w(t)為第t次迭代時的慣性權(quán)重；wmax、wmin分別為最大慣性權(quán)重和最小慣性權(quán)重；fmax(t)為第t次循環(huán)時粒子群最大適應(yīng)度；fmin(t)為第t次循環(huán)時粒子群最小適應(yīng)度。

2.3 基于適應(yīng)度權(quán)重改進(jìn)的學(xué)習(xí)因子

以σ為依據(jù)，定義根據(jù)適應(yīng)度權(quán)重改進(jìn)的學(xué)習(xí)因子分別為：

2.4 FWPSO改進(jìn)粒子群優(yōu)化算法

將改進(jìn)的慣性權(quán)重w(t)和學(xué)習(xí)因子c1(t)和c2(t)應(yīng)用到算法中，得到FWPSO優(yōu)化算法為：

算法具體流程如下：

(1)算法初始化，確定參數(shù)，產(chǎn)生初始種群，隨機(jī)初始化粒子的位移和速度；

(2)根據(jù)適應(yīng)度函數(shù)計(jì)算各個粒子的適應(yīng)度值

(3)對所有粒子的當(dāng)前適應(yīng)度和自體最優(yōu)解，若當(dāng)前適應(yīng)度優(yōu)于自體最優(yōu)解，則將自體最優(yōu)解設(shè)為當(dāng)前適應(yīng)度

(4)將每一個粒子適應(yīng)度與群體最優(yōu)解比較，若某粒子的適應(yīng)度優(yōu)于群體最優(yōu)解，則將群體最優(yōu)解設(shè)為該粒子適應(yīng)度值，并將全局極值下標(biāo)改為該粒子下標(biāo)

(5)根據(jù)公式（6）、（7）、（8）（9）（10）確定慣性權(quán)重和學(xué)習(xí)因子，更新粒子的速度和位置，產(chǎn)生新粒子群

(6)判斷是否達(dá)到最大迭代次數(shù)或收斂解達(dá)到指定精度，若達(dá)到則算法結(jié)束，否則轉(zhuǎn)向步驟（2）。

3 改進(jìn)粒子群與K-means結(jié)合的聚類算法

3.1 K-means算法

K-means算法首先從n個數(shù)據(jù)對象中任意選擇k個作為初始聚類的簇心，再將剩余數(shù)據(jù)對象分配給離其最近的的簇心所在的聚類中。然后以減小目標(biāo)函數(shù)值為方向，通過迭代不斷調(diào)整每個類的簇心和數(shù)據(jù)對象在類中的分布。當(dāng)?shù)M(jìn)行使得目標(biāo)函數(shù)收斂，相鄰兩次算法的聚類中心相同時，聚類調(diào)整結(jié)束。

K-means聚類算法具有算法簡單，計(jì)算執(zhí)行速度快，資源耗費(fèi)少。當(dāng)聚類是密集的，類與類間區(qū)分明顯時，算法的效果好。但K-means算法也具有易陷入局部最優(yōu)解而找不到全局最優(yōu)解，在處理海量大數(shù)據(jù)集時較為費(fèi)時等缺點(diǎn)。這些缺點(diǎn)在很大程度上限制了算法的應(yīng)用范圍。

3.2 結(jié)合算法算法思想

由于粒子群算法的并行性和分布式處理問題的特點(diǎn)適合處理數(shù)據(jù)庫形式的海量數(shù)據(jù)，且較聚類算法具有較強(qiáng)的全局搜索能力。與粒子群算法結(jié)合的聚類算法不但具有粒子群算法優(yōu)良的全局搜索能力，同時具備了聚類算法局部搜索能力強(qiáng)的特點(diǎn)，在處理大規(guī)模數(shù)據(jù)集上也比單純的聚類算法效果好?；诖?，本文將已提出的FWPSO算法與K-means算法相結(jié)合，提出了一種改進(jìn)的粒子群聚類算法——FWP-K算法。

在FWP-K聚類算法中，一個粒子表示一種聚類劃分的情況，粒子的每一維表示聚類一個簇的質(zhì)心，任意粒子i定義如下：

xi=(mi1,…,mij,…mik)

其中mij為第i個粒子所表示的第j個簇Cij的質(zhì)心；

算法初始化m個粒子，粒子的維數(shù)為k，隨機(jī)分配粒子的位置，將每個粒子作為一個候選劃分。對于每個粒子，根據(jù)最小距離原則，將聚類的數(shù)據(jù)對象劃分在以粒子各維為質(zhì)心的簇中。運(yùn)用FWPSO算法迭代運(yùn)算，每次迭代均更新聚類數(shù)據(jù)劃分，直至求出最優(yōu)粒子。該最優(yōu)粒子的位置表示最優(yōu)聚類劃分的簇質(zhì)心。

3.3 結(jié)合算法的算法描述

1. 初始化m個j維粒子的粒子群，隨機(jī)產(chǎn)生粒子的速度；

2. 對每個粒子，按照最小距離原則，將聚類的數(shù)據(jù)對象劃分在以粒子各維為質(zhì)心的簇中，計(jì)算各個粒子的適應(yīng)度值；

3. 對每個粒子，比較其當(dāng)前適應(yīng)度值和其經(jīng)歷過最好位置的適應(yīng)度，若干當(dāng)前適應(yīng)度更好，則更新最好位置；

4. 對每個粒子，比較其當(dāng)前適應(yīng)度值和群體經(jīng)歷最好位置的適應(yīng)度，若干當(dāng)前適應(yīng)度更好，則更新全局位置；

5. 根據(jù)式（5）和式（6）調(diào)整粒子的速度和位置；

6. 當(dāng)達(dá)到最大迭代次數(shù)或粒子群達(dá)到收斂狀態(tài)，則該最優(yōu)粒子的位置表示最優(yōu)聚類劃分的簇質(zhì)心

7. 結(jié)束

4 結(jié)束語

本文基于粒子群粒子適應(yīng)度差異提出了適應(yīng)度權(quán)重這一概念，并以此為核心提出了一種基于適應(yīng)度權(quán)重的改進(jìn)粒子群算法。并將該改進(jìn)算法與K-means聚類算法結(jié)合，結(jié)合聚類算法克服了K-means算法的缺點(diǎn)，提高了算法的有效性和算法效率。

參考文獻(xiàn)

[1] Jiawei Han，Michelin. Camber．?dāng)?shù)據(jù)挖掘概念與技術(shù)[M]，機(jī)械工業(yè)出版社，2007.3

[2] Shi Y ， Ebethart R C．Empirical study of Particle swarmoptimization[A] ． In ： Proceedings of the 1999 Congress onEvolutionary Computation[C]. Piscataway，NJ：IEEE Service Center，1999：1945-1950．

[3] 王萬良，唐宇，微粒群算法的研究現(xiàn)狀與展望[J]，浙江，浙江工業(yè)大學(xué)學(xué)報，2007，35(2)；136-141.

作者簡介：

錢偉強(qiáng)（1982-），西安電子科技大學(xué)在讀研究生，講師，工作單位：陜西交通職業(yè)技術(shù)學(xué)院，從事計(jì)算機(jī)數(shù)據(jù)庫方向教學(xué)工作。