一種改進粒子群和K-means結合的聚類算法

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

關鍵詞：粒子群算法；聚類算法

1. 引言

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

2. 基于適應度權重的改進粒子群算法

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

2.1 適應度權重

本文通過測算每次迭代時粒子群中粒子適應度的差異情況，以此得出粒子群適應度權重，并將其作為判斷粒子群收斂程度的標準。粒子群適應度權重 定義如下：

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

2.2 基于適應度權重改進的慣性權重

在標準粒子群優化算法中，慣性權重w隨迭代次數線性減小，而不是根據粒子群收斂情況進行動態調整，并不適合粒子群實際的情況。本文將適應度權重引入到慣性權重中，具體定義為：

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

2.3 基于適應度權重改進的學習因子

以σ為依據，定義根據適應度權重改進的學習因子分別為：

2.4 FWPSO改進粒子群優化算法

將改進的慣性權重w(t)和學習因子c1(t)和c2(t)應用到算法中，得到FWPSO優化算法為：

算法具體流程如下：

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

(2)根據適應度函數計算各個粒子的適應度值

(3)對所有粒子的當前適應度和自體最優解，若當前適應度優于自體最優解，則將自體最優解設為當前適應度

(4)將每一個粒子適應度與群體最優解比較，若某粒子的適應度優于群體最優解，則將群體最優解設為該粒子適應度值，并將全局極值下標改為該粒子下標

(5)根據公式（6）、（7）、（8）（9）（10）確定慣性權重和學習因子，更新粒子的速度和位置，產生新粒子群

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

3 改進粒子群與K-means結合的聚類算法

3.1 K-means算法

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

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

3.2 結合算法算法思想

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

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

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

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

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

3.3 結合算法的算法描述

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

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

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

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

5. 根據式（5）和式（6）調整粒子的速度和位置；

6. 當達到最大迭代次數或粒子群達到收斂狀態，則該最優粒子的位置表示最優聚類劃分的簇質心

7. 結束

4 結束語

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

參考文獻

[1] Jiawei Han，Michelin. Camber．數據挖掘概念與技術[M]，機械工業出版社，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] 王萬良，唐宇，微粒群算法的研究現狀與展望[J]，浙江，浙江工業大學學報，2007，35(2)；136-141.

作者簡介：

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