一種新的粒子群優化聚類算法

張俊溪，楊海粟（.西安航空學院車輛工程系，西安　70077；.西安電子工程研究所，西安　7000）

?

一種新的粒子群優化聚類算法

張俊溪1，楊海粟2
（1.西安航空學院車輛工程系，西安710077；2.西安電子工程研究所，西安710100）

摘 要：K-means算法在聚類分析中有著廣泛應用。它采用了均值中心這一啟發式信息，具有計算效率高的優點，但對初始聚類中心選擇敏感，且容易陷入局部最優。PSO算法的隨機性和并行性特點使其在處理數據庫形式的海量數據中表現出更大的優越性，不僅具有較強的全局搜索能力，同時，通過對PSO算法搜索過程的改進增強了算法在最優解附近的搜索概率，降低樣本對初始化敏感的程度，可以彌補K-means算法的缺陷。將改進的PSO算法應用于K-means聚類算法可以提高算法的穩定性和收斂效率，通過四組標準UCI數據集的試驗，驗證了新算法的有效性。

關鍵詞：K-平均算法；粒子群優化算法；聚類中心；穩定性；搜索；收斂；敏感

1 引 言

聚類分析是數據挖掘的一個重要分支，是一種重要的非監督學習方法。聚類是按照事物空間、時間或屬性等特點將其劃分成多個類別的過程，并要求類間的相似性最小，類內的相似性最大［1］。目前聚類分析的方法較多，根據不同聚類方法將其劃分為7種類別：基于劃分的聚類、基于層次的聚類、基于密度的聚類、基于網格的聚類、基于模型的聚類、字符屬性聯合聚類和神經網絡聚類等［2］。其中基于劃分聚類中的K-means算法是應用最為廣泛的算法，該算法以樣本中任意位置為初始中心，以樣本到聚類中心的平均距離之和作為適應度函數，具有模型簡單、計算效率高的優點。但由于K-means算法基于適應度函數極值的方法來優化目標函數，存在易于陷入局部最優和處理海量數據效率低等缺點。近年來對該算法的改進是聚類領域的研究熱點，出現了將遺傳算法、PSO算法、人工免疫算法、螞

?蟻算法及其相關改進算法與k-means相結合的多聚類算法等。

粒子群算法通過模擬自然界鳥群或魚群等生物的覓食行為，將其覓食過程中的學習和經驗作為更新手段，來達到最優目標的模式，具有隨機性和并行性的特點，全局搜索能力強，適合于處理數據庫形式的海量數據，與聚類算法相比不易陷入局部最優。但是鑒于基本粒子群優化算法在搜索空間中對解搜索的盲目性和對最優解空間搜索缺乏針對性，近年來提出了大量的改進算法。常見粒子群改進的優化算法有：帶慣性權重的標準粒子群算法，通過給粒子群的速度公式乘以慣性權重因子來改變粒子的速度［3］；將免疫算法中的免疫信息處理機制引入到粒子群算法中的免疫粒子群算法［4］；將混沌理論中混沌運動的遍歷性引入到粒子群搜索過程中，將粒子群搜索的最優位置與混沌序列的最優位置粒子進行比較獲得最優解的混沌粒子群算法［5］；將協同理論引入到粒子群算法中，通過將位置向量加入到粒子群的適應度函數計算適應度值，提高算法的收斂精度［6］。

通過去掉隨機粒子群算法模型中的當前速度，使速度本身失去記憶性，同時在搜索空間中重新隨機產生新的微粒取代原始微粒，可以大大增強全局搜索能力。將耗散結構的自組織性加入到粒子群算法，粒子在搜索過程中的更新不僅依賴歷史經歷，還要受環境影響，通過附加信息使得系統處于不平衡狀態，從而使群體進化能力增強［7］。無論是哪一種改進方法，目標都是為了提高PSO算法收斂的速度和收斂解的精度。本文基于此提出了一種對適應度值權重分配的PSO算法，并將其應用于K-means聚類算法中，通過兩組人工數據和兩組UCI數據，試驗結果表明改進的PSO應用于K-means算法與基本PSO算法相比具有較快的收斂速度和較好的收斂解。

2 k-means聚類算法基本原理

K-means算法的實現過程是，指定聚類的數目k，隨機產生k個聚類中心，將待聚類對象分給最近的簇中心，依據最近鄰法則［8］進行賦值，通過計算每個簇中個體與聚類中心的距離平均值，并更新為新的聚類中心［9］，反復迭代直至誤差準則函數達到最小值，如公式（1）所示：

其中p為空間的點，即數據對象，mi是簇Ci的聚類中心。E值越小表示類內數據越相似。經典的K-means算法過程描述如下［1］：

輸入：簇的數目k和包含n個對象的數據庫；

輸出：平方誤差總和最小條件下的k個簇；

①指定聚類數目K，隨機選擇其初始聚類中心；

②根據最近鄰法則將所有對象劃分到相應的簇中；

③根據誤差準則函數E計算適應度值，并更新每個簇中心；

④若未達到結束條件，則轉②重復；

⑤輸出結果。

3 粒子群優化算法及其改進

PSO大規模應用于聚類算法始于2002年，Omran等人［10］在對PSO算法進行大量分析研究后，提出了一種基于粒子群優化的無指導圖像分類算法。

在基于粒子群算法的聚類分析中，每個粒子代表K個類的中心點，這樣每個粒子就包含一個表示簇中心的數據向量，整個粒子群則代表了對數據的多種劃分。基本PSO算法的適應度函數為Je，如公式（2）所示：

其中，

基本PSO算法流程如下：

（1）初始化粒子群并根據適應度函數計算各粒子的適應度值；

（2）尋找歷史最優解，將每個粒子的適應度值與它的歷史最優適應度值比較，取二者之中較優的一個；

（3）尋找最優位置適應度值，將每個粒子的適應度值和群體所經歷的最好位置的適應度值相比較，取二者之中較優值作為群歷史最優解；

（4）根據公式（3）和公式（4）更新粒子的速度和位置信息；

（5）如果收斂到最優解，則結束，否則執行步驟（2）。

在算法的步驟（4）中考慮將粒子的最優位置搜索和種群的最優位置賦予一定的權重進行進化，并通過試驗找出最佳權重因子，可以提高算法在最優解附近的搜索概率，使算法收斂速度和收斂精度提高。

4 適應度權重分配的粒子群優化K-means聚類算法

在優化的PSO算法過程中，每次迭代時根據聚簇的結果按照K-means算法求一次簇的中心，假設第i個聚類中心的均值mi表示為公式（5）

其中pj為簇Ci中第j個對象的位置；簇Ci中共有n個聚類對象。P為空間數據向量，在K-means算法聚類的過程中，適應度函數記為E（P），用P（t）表示在t次迭代搜索時的聚類中心，Po（t）表示已經搜索到的最優解，則有公式（6）和公式（7）：

E（P（i））=min（E（P（1）），E（P（2）），...，E（P（t）））

利用公式（8）對聚類中心進行調整：

P（t）= aK（P（t-1））+（1-α）Po（t-1）（8）

其中a是隨機數，P（t-1）表示t-1時刻的聚類中心，P0（t-1）表示到t-1時刻搜索到的最優聚類中心，且a∈［0，1］。K（P（t-1））表示K-means變換，它將t-1時刻的聚類中心進行了均值優化。顯然，當a =1時，公式（8）變化為經典的K-means算法。在算法的實際運行中，經過多次試驗，發現a 取0.1時可以獲得較好的效果。

利用改進的PSO算法結合K-means聚類，可以獲得最好解的概率明顯高于K-means方法和K-means + PSO方法。

新算法的流程如下：

（1）初始化粒子，隨機生成簇中心并賦給各個粒子，隨機產生粒子的速度；

（2）按最近鄰法則對粒子進行劃分，并按照公式（1）計算各個粒子的適應度值，更新個體極值；

（3）根據各個粒子的個體極值找出全局極值和全局極值位置，并按照公式（4）進行更新；

（4）按照粒子群優化算法的速度公式更新粒子的速度和位置，直至滿足終止條件；

（5）輸出最優粒子的位置，即最優的Nc個聚類中心。

5 試驗結果

為了考察算法的性能，選擇四組UCI數據集分別進行試驗，分別為Iris、Wing、Zoo和Glass。Iris（鳶尾屬植物）是一種基準函數數據集，被廣泛用于模式識別和聚類分析測試。Iris數據集中，每組數據包含四種屬性，分別表示Setosa、Versicolor和Virginica三種植物的萼片長度、萼片寬度、花瓣長度、花瓣寬度等；每種各有50組數據，共150個樣本，數據為150*4維矩陣，其中1-50記錄屬于第一類Iris-setosa，51-100記錄屬于第二類Iris-versicolor，101-150記錄屬于第三類Iris-virginica。Wine數據集來自于意大利同一地區產的三種不同品種的葡萄酒，三類各有59、71和48個樣本，共計178個。樣本包含Alcohol、Malic acid、Ash等13種屬性，為178*3矩陣。Zoo數據集為101種動物，這些動物屬于7大類，每個類別包含的數量為4，5，8，10，13，2和41，該數據集為101*17維矩陣。Glass數據集有6類，每一類包含數量為70，76，17，13，9和29個樣本，一共214個樣本，該數據集為214*9維矩陣。

分別通過將改進的粒子群優化聚類算法和基本粒子群優化K-means聚類算法以及單純的K-means聚類算法應用于該四組UCI數據，為了使計算結果更可靠，每組數據集分別計算50次，采用Visio Studio 6.0編譯環境，C語言實現，最后取計算所得的平均值作為最終結論。計算結果如表1所示。

表1 三種算法的聚類特性比較

通過表1可以看出，改進的粒子群優化聚類算法與其他兩種算法相比具有較高的準確率。在Iris 和Wine數據集中，改進的粒子群優化聚類算法與基本粒子群優化聚類算法相比較并沒有明顯的優勢，但比單純的K-means聚類性能優越；而在Zoo 和Glass數據集中，改進的粒子群優化聚類算法比基本粒子群優化聚類算法以及單純K-means聚類算法均具有明顯優勢。該結論也表明本文提出的改進粒子群優化聚類算法在處理大數據集時具有更好的優越性。

6 結束語

聚類是數據挖掘最重要的任務之一，并且在未來相當長的時間內都具有重大的研究意義。提出了一種改進的具有適應度權重分配的聚類算法，通過將改進的粒子群優化算法與K-means算法相結合，PSO具有較強的全局搜索能力，可以克服K-means算法容易陷入局部最優的缺點。在改進的算法中，加入了適應度函數的權重分配，權重因子通過大量試驗獲得。

選用4組標準UCI數據，將改進的粒子群優化聚類算法與基本粒子群優化算法以及單純K-means聚類算法分別應用于4組數據集的聚類中，并與標準聚類結果進行比較，通過比較各算法的聚類準確率，可以得出以下結論：

（1）改進的粒子群聚類算法具有更好的收斂效率和收斂精度；

（2）改進的粒子群聚類算法的平均聚類效率明顯優于其他兩種算法；

（3）改進的粒子群優化算法對于大數據集具有更好的收斂特性。

參考文獻：

［1］Jiawei Han.M Kamber.Data Mining：Concepts and Techniques［M］.Los Altos，CA：Morgan Kaufmann Publishers，2001.

［2］姜園，張朝陽，仇佩亮，等.用于數據挖掘的聚類算法［J］.電子與信息學報，2005（4）：655-660.Jiang Yuan，Zhang Chaoyang，Qiu Peiliang.Clustering Algorithm Applying to Data Mining［J］.Journal of Electronic and Information，2005（4）：655-660.

［3］Clerc M.The Swarm and the Queen：Towards a Deterministic and Adaptive Particle Swarm Optimization［C］.In：Proc.1999 Congress on Evolutionary Computation.Washington，DC，Piscataway，NJ：IEEE Service Center，1999：1951-1957.

［4］高鷹，謝勝利.免疫粒子群優化算法［J］.計算機工程與應用，2004，40（6）：416-420.Gao Ying，Xie Shengli.Immune Particle Swarm Optimization Algorithm［J］.Computer Engineering and Application，2004，40（6）：416-420.

［5］高鷹，謝勝利.混沌粒子群優化算法［J］.計算機科學，2004，31（8）：13-15.Gao Ying，Xie Shengli.Chaos particle swarm optimization algorithm［J］.Computer Science，2004，31（8）：13-15.

［6］Parsopoulos K E.Stretching Technique for Obtaining Global Minimizers through Particle Swarm Optimization ［R］.Proceedings of the Workshop on PSO，Indianapolis：Purdue school of Engineering and Technology，INPUI，2001.

［7］王萬良，唐宇.微粒群算法的研究現狀與展望［J］.浙江工業大學學報，2007，35（2）：136-141.Wang Wanliang，Tang Yu.Research Status and Prospects of Particle Swarm Optimization［J］.Journal of Zhejiang University of Technology，2007，35（2）：136-141.

［8］Vance Faber.Clustering and the Continuous k-Means Algorithm［J］.Los Alamos Science，1994（22）：58-63.

［9］Mali U.Bandyopadhyay S.Genetic Algorithm-based on Clustering Technique［J］.Pattern Recognition，2000，33 （9）：1455-1465.

［10］OMRANGM，SALMAN A，ENGELBRECHTA P.Image classification using particle swarm optimization［C］.//Proc of the 4th Asia-Pacific Conference on Simulated Evolution and Learning.2002：

A New Optimization Clustering Algorithm of Improved Particle Swarm

Zhang Junxi1，Yang Haisu2
（1.Department of Vehicle Engineering，Xi’an Aeronautical University，Xi'an 710077，China；2.Xi'an Institute of Electronic Engineering，Xi'an 710100，China）

Abstract：K-means algorithm，widely used in the clustering analysis，uses the mean center of the heuristic information and has the advantage of high computational efficiency.But it is sensitive to the initial center and easy to fall into local optimum.PSO algorithm，with the parallelism and randomness characteristics，has greater superiority in massive database processing.It not only has strong global searching capability，but also enhances the searching probability around the optimal solution.And it reduces sensitive level of the initialization，so PSO algorithm can compensate deficiencies for K-means.The improved PSO algorithm is applied to K-means clustering algorithm which improves the stability and convergence efficiency of the algorithm.The experiments on four standard UCI datasets demonstrate that the new algorithm has more effectiveness.

Key words：K-means；Particle Swarm Optimization；Clustering Center；Stability；Searching；Converging；Sensitive

DOI：10.3969/j.issn.1002-2279.2016.02.016

中圖分類號：TP311

文獻標識碼：A

文章編號：1002-2279（2016）02-0061-04

基金項目：?陜西省自然科學基金項目（No.2014JM8353）

作者簡介：張俊溪（1983-），女，河南省新鄉市人，碩士研究生，講師，主研方向：模式識別，智能系統。

收稿日期：2015-06-09