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

?

一種新的粒子群優(yōu)化聚類算法

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

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

關(guān)鍵詞：K-平均算法；粒子群優(yōu)化算法；聚類中心；穩(wěn)定性；搜索；收斂；敏感

1 引 言

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

?蟻算法及其相關(guān)改進(jìn)算法與k-means相結(jié)合的多聚類算法等。

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

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

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

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

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

輸入：簇的數(shù)目k和包含n個對象的數(shù)據(jù)庫；

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

①指定聚類數(shù)目K，隨機(jī)選擇其初始聚類中心；

②根據(jù)最近鄰法則將所有對象劃分到相應(yīng)的簇中；

③根據(jù)誤差準(zhǔn)則函數(shù)E計算適應(yīng)度值，并更新每個簇中心；

④若未達(dá)到結(jié)束條件，則轉(zhuǎn)②重復(fù)；

⑤輸出結(jié)果。

3 粒子群優(yōu)化算法及其改進(jìn)

PSO大規(guī)模應(yīng)用于聚類算法始于2002年，Omran等人［10］在對PSO算法進(jìn)行大量分析研究后，提出了一種基于粒子群優(yōu)化的無指導(dǎo)圖像分類算法。

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

其中，

基本PSO算法流程如下：

（1）初始化粒子群并根據(jù)適應(yīng)度函數(shù)計算各粒子的適應(yīng)度值；

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

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

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

（5）如果收斂到最優(yōu)解，則結(jié)束，否則執(zhí)行步驟（2）。

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

4 適應(yīng)度權(quán)重分配的粒子群優(yōu)化K-means聚類算法

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

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

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

利用公式（8）對聚類中心進(jìn)行調(diào)整：

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

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

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

新算法的流程如下：

（1）初始化粒子，隨機(jī)生成簇中心并賦給各個粒子，隨機(jī)產(chǎn)生粒子的速度；

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

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

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

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

5 試驗結(jié)果

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

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

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

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

6 結(jié)束語

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

選用4組標(biāo)準(zhǔn)UCI數(shù)據(jù)，將改進(jìn)的粒子群優(yōu)化聚類算法與基本粒子群優(yōu)化算法以及單純K-means聚類算法分別應(yīng)用于4組數(shù)據(jù)集的聚類中，并與標(biāo)準(zhǔn)聚類結(jié)果進(jìn)行比較，通過比較各算法的聚類準(zhǔn)確率，可以得出以下結(jié)論：

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

（2）改進(jìn)的粒子群聚類算法的平均聚類效率明顯優(yōu)于其他兩種算法；

（3）改進(jìn)的粒子群優(yōu)化算法對于大數(shù)據(jù)集具有更好的收斂特性。

參考文獻(xiàn)：

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

［2］姜園，張朝陽，仇佩亮，等.用于數(shù)據(jù)挖掘的聚類算法［J］.電子與信息學(xué)報，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］高鷹，謝勝利.免疫粒子群優(yōu)化算法［J］.計算機(jī)工程與應(yīng)用，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］高鷹，謝勝利.混沌粒子群優(yōu)化算法［J］.計算機(jī)科學(xué)，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］王萬良，唐宇.微粒群算法的研究現(xiàn)狀與展望［J］.浙江工業(yè)大學(xué)學(xué)報，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

文獻(xiàn)標(biāo)識碼：A

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

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

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

收稿日期：2015-06-09