粒子群K-means聚類算法的改進

沈艷，余冬華，王昊雷

哈爾濱工程大學理學院，哈爾濱 150001

◎數據庫、數據挖掘、機器學習◎

粒子群K-means聚類算法的改進

沈艷，余冬華，王昊雷

哈爾濱工程大學理學院，哈爾濱 150001

粒子群（PSO）與K-means結合是聚類分析中的重要方法之一，但都未考慮粒子更新導致的空類問題。提出基于多子群粒子群偽均值（PK-means）聚類算法，為該問題的解決提供一種有效途徑，并與粒子群K均值（PSOK-means），K-means算法進行比較。理論分析和實驗表明，該算法不但可以防止空類出現，而且同時還具有非常好的全局收斂性和局部尋優能力，并且在孤立點問題的處理上也具有很好的效果。

聚類分析；多子群粒子群；全局優化；K-means；PSOK-means

1 引言

K-means是聚類分析中廣泛應用的算法之一，該方法對初始中心點的敏感，容易陷入局部極小解，聚類結果中類的個數及空類等問題一直都是研究的熱點。與粒子群（PSO）結合的K-means聚類算法，在初始中心點，局部極小解方面收到了一定的效果，如劉靖明[1]，Kalyani[2]等。而在其基礎上的改進算法，如混沌粒子群的CPSOKM方法[3]、變異粒子群K-means[4]、量子粒子群K-means[5]及KCPSO方法[6]在初始中心點及局部極小解問題上獲得了極佳的效果，此外，針對聚類個數方面，有學者提出CPSOII動態聚類[7]及PM-K-means多類合并的粒子群K-means改進算法[8]。但是粒子群與K-means的結合或其改進算法，并沒有解決聚類為空問題，與此同時，由于粒子需要在連續空間內更新，導致聚類中出現空類的幾率大增，尤其是具備較高全局尋優能力的粒子，空類的出現，使得聚類結果遠離預期目標類數，在類別劃分中會淹沒一些類的特征，并且淹沒類的數據會被劃分到其他所屬類，弱化該類特征。在與粒子群結合或在其基礎上改進的文獻里，常見的做法是將其忽略，盡管這個問題不是經常出現，卻是實際存在的。文中第4章給出實例，該例子說明只要粒子進入區域G，那么該類必定為空。

基于上述事實，本文綜合K-mediods和并行粒子群思想，提出一種基于多子群偽K均值算法（Pseudo-K-means，簡記為PK-means算法）。PK-means算法只需要調整“認知”和“社會”部分的學習因子就能調整粒子的全局尋優能力及局部尋優能力。偽均值的引入并不影響多子群粒子群的尋優、處理初始中心點及局部極小問題的能力，同時消除了聚類無解的情況。為描述上的方便，文中采用集合論中商集的相關概念給出PK-means算法的描述，便于文中在理論上說明聚類結果非空。對Iris和Wine數據實驗表明，PK-means分類效果與PSOK-means一致，均比K-means準確、穩定，且沒有空類現象。在增加孤立點后，適當增加聚類數目，可以將孤立點分成單獨的類而不影響其他數據的分類。

2 多子群粒子群算法簡介

多子群粒子群是在原始粒子群算法中，將粒子分為兩個子群，對子群采用在局部和全局尋優能力上各有所長的不同更新策略。設Pi為第i個粒子曾經達到的最優解，為整個粒子群達到的最優解，那么r子群的粒子速度更新公式為：

其中，cr1，cr2，cr3，cr4分別為r子群和k子群的“認知”與“社會”部分的學習因子，r1和r2為[0，1]上的獨立的隨機數。ω為慣性權重：

在本文中，適應度函數就取聚類結果各個簇中數據對象到中心點歐式距離的平方和，記為：

針對于兩個子群的劃分，設粒子群有N個粒子，按照粒子適應度值從優到劣排序，子群劃分比率為ρ，則r子群粒子為前[ρN]個粒子，其中[·]代表取整，剩下的就是k子群的粒子。由粒子的速度更新公式（1）與公式（2）可知，粒子更新主要涉及兩個方面的影響，習慣上稱為“認知”和“社會”部分。如果“認知”部分的影響超過“社會”部分，則更新后的粒子局部尋優能力強；如果“社會”部分影響超過“認知”部分，則更新后的粒子全局尋優能力強。因為r子群要傾向于局部搜索，所以“認知”學習因子要比“社會”學習因子大得多，而k子群要傾向于全局搜索，所以“社會”學習因子要比“認知”學習因子大得多。關于這方面更詳細的理論闡述，可以參考文獻[9]。這點正好為K-means聚類初始中心點問題提供了一種行之有效的解決方法。

3 PK-means算法的建立

3.1 PK-means商集描述

設X是樣本數據集合，R是集合X的一個等價關系，集族X/R是集合X相對于等價關系R而言的商集，[x1]R，[x2]R，…，[xn]R代表商集X/R中的n個等價類。那么，PK-means劃分為n個類的聚類就等價于存在n個中心點x1，x2，…，xn∈X，找到一個等價關系R*，使其滿足如下條件：

3.2 聚類非空性

根據商集的性質：（1）每一個等價類均非空；（2）不同等價類之間相交為空集，所有等價類的并集就是整個集合X。因為聚類結果中的每一個類就是商集中的一個元素，即一個等價類，由上述性質（1）可知，每一個類非空，且n個中心點x1，x2，…，xn∈X按照如下方式選取，每一次按照K-means方法計算第i類中心時，選取離該值距離最近的樣本集點xi作為第i類的新的中心點進行聚類。這就對數據集進行了一個完美的劃分，完成了聚類。最特殊的情況就是，該類只有中心點本身，仍然非空。

此外，由于中心點x1，x2，…，xn∈X，這就契合了K-medoids采用數據樣本點作為聚類中心的聚類思想，順承了K-medoids算法的優點，有效降低了孤立點對聚類結果的影響。

3.3 粒子編碼

粒子群算法中的粒子，實質上是一個可行解，對應于劃分成n個類的聚類問題來說，一個粒子就需要包含n個聚類中心點。設數據樣本點有m個屬性值，那么一個粒子就是一個n×m維向量，如果用Z代表一個粒子，那么該粒子可以編碼如下：

其中，zij代表第i個聚類中心點的第j維屬性值。

3.4 PK-means算法描述

設數據樣本集為X，參數集為Ω={X，N，n，ρ，cr1，cr2，ck1，ck2，ωmin，ωmax}pg，PK-means算法流程可以描述如下：

（1）讀取數據，設定初始參數集Ω。

（2）初始化模型，設定粒子個數N，針對每個粒子分別在數據對象X中，隨機抽取n個數據樣本點作為初始中心點，根據公式（5）計算各個粒子的適應度值并排序。

（3）根據適應度值排序結果和子群劃分比率ρ，對粒子群進行劃分，得到r子群和k子群。

（4）r-子群和k子群分別按照公式（1）～（3）進行繁殖得到子代，用N個子代粒子作為N組均值初始中心。

（5）每一個粒子選擇離均值初始中心最近的數據樣本對象作為新的簇中心。

（6）將數據樣本集中每個數據對象（再）指派到最相似的簇。

（7）計算每個簇的均值。

（8）對于每個簇的均值中心，選擇離其最近的數據對象作為新的簇中心。

（9）判斷中心點是否穩定，如果穩定，進行聚類，根據聚類結果得到新一組N個粒子的粒子群并計算其適應度值。然后轉向（10），否則，轉向（5）。

（10）比較適應度值。通過對比父代與其子代的適應度值大小，更新局部最優粒子pi，同時比較所有的父代與所有的子代適應度值。選取最大適應度值作為全局最優粒子pg。

（11）判斷全局最優粒子pg是否滿足結束條件，不滿足轉向（3），否則，結束程序，輸出聚類結果。

4 實驗仿真

4.1 聚類為空實例

在離散的樣本點中，采用連續化方法選取中心點而不加處理，就可能導致某個中心點的聚類結果為空類。采用粒子群（PSO）方法優化的K-means方法就存在這個問題。下面將取Iris數據集中部分點（取72個樣本，分別來自3個類別）作為例子說明聚類結果為空是可能的。

將該72個點劃分為3類，此時粒子的可能解區域為矩形域[1.0，6.9]×[0.1，2.5]，某一次粒子更新后，有兩個中心點分別為G1，G2，以G1，G2為圓心，以能夠包含所有點的最小半徑r1，r2作圓，然后再以G1，G2為圓心，以2r1，2r2作圓，劃分出的區域如圖1，而第三個中心點因粒子更新進入了區域G，聚類完成后，第三類將成為空類，因為任何一個數據點此時與第三個中心點的距離必定大于min{r1，r2}，故該數據點一定不會指派到第三類。

圖1 部分Iris數據集聚類為空示意圖

而偽均值算法將不會出現這種情況，如果采用K-means計算出均值落入區域G，所尋找的偽均值就是離該均值最近的一個樣本點作為新的中心點，至少該點屬于樣本集，如假設初始化中心點或粒子更新后的聚類中心為x1，x2，x3，對應坐標值為（1.4，0.3），（3.0，2.0），（6.0，1.2），此時聚類中心x2所對應的類會成為空類，采用偽均值聚類后，會選擇與聚類中心點最近的樣本點充當偽均值，即圖1中的x1'，x2'，x3'，對應坐標值為（1.4，0.3），（1.9，0.4），（6.0，1.8），而這三個聚類中心必定屬于不同類別且均為樣本數據點，故不會出現空類。

4.2 Iris與Wine數據集聚類仿真

為了從實驗方面驗證PK-means算法的聚類效果，下面對UCI（http：//archive.ics.uci.edu/ml/）上的Iris和Wine數據進行實驗，該數據均可分為3類。其中Iris數據選取其第三與第四維屬性值（petal length，petal width），Wine數據選取其全部的13個屬性值，對于Iris數據點可以在平面用散點圖反映，見圖2。

圖2 Iris數據散點圖

使用PK-means對Iris數據和Wine數據聚類時參數設置如下：類數K=3，PK-means算法中的參數，N=10，ρ=0.5，cr1=0.2，cr2=1，ck1=0.5，ck2=0.5，ωmin=0.8，ωmax=1.2。在表1中，給出了聚類次數與Iris和Wine的各自的錯分點個數，由于Wine的屬性值比較多，故表中只給出了相應的Iris的初始中心點，PK-means算法的最優初始中心點分別為樣本集中第49個，第98個，第129個數據點，其中，K-means聚類結果參照文獻[10]。從表1可以看出，K-means對初始中心點的敏感程度非常大，雖然錯分數可以接受，但是PSOK-means、PK-means無論是從對初始中心點的依賴程度，還是在分類的準確程度上，都能夠好于K-means算法，有效減少了聚類的隨機性，PK-means與PSOK-means具有相同的效果，并沒有因為引入偽均值而降低聚類最終效果。

表1 分類結果

為了反映出多子群粒子群在算法中所起的作用，使用某次聚類過程中全局最優粒子更新代數和公式（5）的適應度函數值，畫出初始中心點的調整（即粒子代數）與適應度函數值之間的曲線，如圖3。Iris粒子適應度值每一次改變，都說明多子群粒子群找到了更優的初始中心點，即跳出了局部極小點，而Wine粒子的適應度值為直線，說明在初始化時，就已經找到了最優初始中心點。這也說明，加入的多子群粒子群算法起到了相應的效果。

圖3 Iris與Wine粒子更新代數與適應度值關系

對于含有孤立點的數據來說，適當增加類數，即K值，一般可以把這些孤立點單獨聚成類，而并不會影響數據分類，對于Iris數據，增加（14，0）與（20，0.2）兩個點，這兩個點很明顯超出了原有數據的屬性值范圍而成為孤立點，對于Wine數據增加點（0，0，0，0，0，0，0，0，0，0，0，0，0），然后將增加了孤立點的數據聚成4類，結果如表2。

表2 加入孤立點后聚類結果

從表2可以看出，Iris數據集的第一個類只有兩個數據點，恰為加入的孤立點（14，0）與（20，0.2），而Wine數據集的第三個類只有一個數據點，該點正是加入的那個孤立點，而對于其他的數據分類，錯分數分別為6個與18個，并沒有因為加入了孤立點而影響到分類效果。如果有必要，可以將分離開的孤立點剔除，然后再重新分類。

5 結論

PK-means算法綜合了K-medoids算法和并行粒子群算法思想，在理論和實驗上驗證了該算法在克服初始中心點，局部極小，防止空類及處理孤立點問題上，都能收到很好的效果，并且在理論上論證了聚類結果非空的問題。此外，PK-means算法的收斂速度也很快，聚類的結果很穩定。值得指出，偽均值同樣可以與混沌粒子群、變異粒子群及量子粒子群聚類算法結合，防止空類又不影響聚類準確性。

[1]劉靖明，韓麗川，侯立文.基于粒子群的K均值聚類算法[J].系統工程理論與實踐，2005（6）：54-58.

[2]Kalyani S，Swarup K S.Particle swarm optimization based K-means clustering approach for security assessment in power systems[J].Expert Systems with Applications，2011，38：10839-10846.

[3]Li Y R，Zhu Y Y，Zhang C N.The K-means clustering algorithm based on chaos particle swarm[J].Journal of Theoretical and Applied Information Technology，2013，48（2）：762-767.

[4]王東，羅可.基于變異粒子群的聚類挖掘[J].計算機工程與應用，2011，47（21）：130-132.

[5]葉安新，金永賢.基于量子粒子群算法的聚類分析方法[J].計算機工程與應用，2012，48（32）：52-55.

[6]Cheng M Y，Huang K Y，Chen H M.K-means particle swarm optimization with embedded chaotic search for solving multidimensional problems[J].Applied Mathematics and Computation，2012，219：3091-3099.

[7]Masoud H，Jalili S，Hasheminejad S M H.Dynamic clustering using combinatorial swarm optimization[J].Applied Intelligence，2013，38：289-314.

[8]Lin Y C，Tong N，Shi M J，et al.K-means optimization clustering algorithm based on Particle Swarm Optimization and multiclass merging[J].Advances in Computer Science and Information Engineering，2012，168：569-578.

[9]閆允一.粒子群優化及其在圖像處理中的應用研究[D].西安：西安電子科技大學，2008.

[10]連鳳娜，吳錦林，唐琦.一種改進的K-means聚類算法[J].電腦與信息技術，2008，16（1）：38-40.

SHEN Yan,YU Donghua,WANG Haolei

College of Science,Harbin Engineering University,Harbin 150001,China

Combining particle swarm with K-means algorithm is one of the important methods in data mining,but all methods almost ignore the empty class problem which the particle update causes.This paper proposes a PK-means clustering algorithm based on multi-subswarms particle swarm and pseudo means,then is compared with both PSOK-means and K-means. The theory analysis and experiments show that the algorithm not only avoids empty clustering class but also has well global convergence and the local optimization,overcomes local minimum better,has a great effect on isolated data.

clustering analysis;multi-subswarms particle swarm;global optimization;K-means;PSOK-means

A

TP301

10.3778/j.issn.1002-8331.1401-0357

SHEN Yan,YU Donghua,WANG Haolei.Improvement of K-means based on particle swarm clustering algorithm. Computer Engineering and Applications,2014,50（21）：125-128.

國家自然科學基金（No.51309068）。

沈艷（1965—），女，博士，教授，研究領域為科學計算，系統建模，數據挖掘等；余冬華（1988—），男，碩士研究生，研究領域為科學計算，數據挖掘；王昊雷（1989—），男，碩士研究生，研究領域為數據挖掘，系統建模。E-mail：shenyan@hrbeu.edu.cn

2014-01-22

2014-03-27

1002-8331（2014）21-0125-04

CNKI出版日期：2014-05-29，http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1401-0357.html