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

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

1. 引言

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

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

基于對粒子群優(yōu)化算法的分析，本文將引入粒子運動適應(yīng)度權(quán)重這一概念，并以此為核心提出一種改進的粒子群優(yōu)化算法FWPSO。FWPSO將每個粒子的適應(yīng)度和整個粒子群粒子的適應(yīng)度進行計算，得出粒子的適應(yīng)度權(quán)重，并將該權(quá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)重改進的慣性權(quán)重

在標(biāo)準(zhǔn)粒子群優(yōu)化算法中，慣性權(quán)重w隨迭代次數(shù)線性減小，而不是根據(jù)粒子群收斂情況進行動態(tài)調(diào)整，并不適合粒子群實際的情況。本文將適應(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)重改進的學(xué)習(xí)因子

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

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

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

算法具體流程如下：

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

(2)根據(jù)適應(yīng)度函數(shù)計算各個粒子的適應(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)判斷是否達到最大迭代次數(shù)或收斂解達到指定精度，若達到則算法結(jié)束，否則轉(zhuǎn)向步驟（2）。

3 改進粒子群與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行使得目標(biāo)函數(shù)收斂，相鄰兩次算法的聚類中心相同時，聚類調(diào)整結(jié)束。

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

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

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

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

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

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

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

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

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

2. 對每個粒子，按照最小距離原則，將聚類的數(shù)據(jù)對象劃分在以粒子各維為質(zhì)心的簇中，計算各個粒子的適應(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)達到最大迭代次數(shù)或粒子群達到收斂狀態(tài)，則該最優(yōu)粒子的位置表示最優(yōu)聚類劃分的簇質(zhì)心

7. 結(jié)束

4 結(jié)束語

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

參考文獻

[1] Jiawei Han，Michelin. Camber．?dāng)?shù)據(jù)挖掘概念與技術(shù)[M]，機械工業(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.

作者簡介：

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