粒子群K-means聚類算法的改進(jìn)

沈艷，余冬華，王昊雷

哈爾濱工程大學(xué)理學(xué)院，哈爾濱 150001

◎數(shù)據(jù)庫(kù)、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)◎

粒子群K-means聚類算法的改進(jìn)

沈艷，余冬華，王昊雷

哈爾濱工程大學(xué)理學(xué)院，哈爾濱 150001

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

聚類分析；多子群粒子群；全局優(yōu)化；K-means；PSOK-means

1 引言

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

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

2 多子群粒子群算法簡(jiǎn)介

多子群粒子群是在原始粒子群算法中，將粒子分為兩個(gè)子群，對(duì)子群采用在局部和全局尋優(yōu)能力上各有所長(zhǎng)的不同更新策略。設(shè)Pi為第i個(gè)粒子曾經(jīng)達(dá)到的最優(yōu)解，為整個(gè)粒子群達(dá)到的最優(yōu)解，那么r子群的粒子速度更新公式為：

其中，cr1，cr2，cr3，cr4分別為r子群和k子群的“認(rèn)知”與“社會(huì)”部分的學(xué)習(xí)因子，r1和r2為[0，1]上的獨(dú)立的隨機(jī)數(shù)。ω為慣性權(quán)重：

在本文中，適應(yīng)度函數(shù)就取聚類結(jié)果各個(gè)簇中數(shù)據(jù)對(duì)象到中心點(diǎn)歐式距離的平方和，記為：

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

3 PK-means算法的建立

3.1 PK-means商集描述

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

3.2 聚類非空性

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

此外，由于中心點(diǎn)x1，x2，…，xn∈X，這就契合了K-medoids采用數(shù)據(jù)樣本點(diǎn)作為聚類中心的聚類思想，順承了K-medoids算法的優(yōu)點(diǎn)，有效降低了孤立點(diǎn)對(duì)聚類結(jié)果的影響。

3.3 粒子編碼

粒子群算法中的粒子，實(shí)質(zhì)上是一個(gè)可行解，對(duì)應(yīng)于劃分成n個(gè)類的聚類問(wèn)題來(lái)說(shuō)，一個(gè)粒子就需要包含n個(gè)聚類中心點(diǎn)。設(shè)數(shù)據(jù)樣本點(diǎn)有m個(gè)屬性值，那么一個(gè)粒子就是一個(gè)n×m維向量，如果用Z代表一個(gè)粒子，那么該粒子可以編碼如下：

其中，zij代表第i個(gè)聚類中心點(diǎn)的第j維屬性值。

3.4 PK-means算法描述

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

（1）讀取數(shù)據(jù)，設(shè)定初始參數(shù)集Ω。

（2）初始化模型，設(shè)定粒子個(gè)數(shù)N，針對(duì)每個(gè)粒子分別在數(shù)據(jù)對(duì)象X中，隨機(jī)抽取n個(gè)數(shù)據(jù)樣本點(diǎn)作為初始中心點(diǎn)，根據(jù)公式（5）計(jì)算各個(gè)粒子的適應(yīng)度值并排序。

（3）根據(jù)適應(yīng)度值排序結(jié)果和子群劃分比率ρ，對(duì)粒子群進(jìn)行劃分，得到r子群和k子群。

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

（5）每一個(gè)粒子選擇離均值初始中心最近的數(shù)據(jù)樣本對(duì)象作為新的簇中心。

（6）將數(shù)據(jù)樣本集中每個(gè)數(shù)據(jù)對(duì)象（再）指派到最相似的簇。

（7）計(jì)算每個(gè)簇的均值。

（8）對(duì)于每個(gè)簇的均值中心，選擇離其最近的數(shù)據(jù)對(duì)象作為新的簇中心。

（9）判斷中心點(diǎn)是否穩(wěn)定，如果穩(wěn)定，進(jìn)行聚類，根據(jù)聚類結(jié)果得到新一組N個(gè)粒子的粒子群并計(jì)算其適應(yīng)度值。然后轉(zhuǎn)向（10），否則，轉(zhuǎn)向（5）。

（10）比較適應(yīng)度值。通過(guò)對(duì)比父代與其子代的適應(yīng)度值大小，更新局部最優(yōu)粒子pi，同時(shí)比較所有的父代與所有的子代適應(yīng)度值。選取最大適應(yīng)度值作為全局最優(yōu)粒子pg。

（11）判斷全局最優(yōu)粒子pg是否滿足結(jié)束條件，不滿足轉(zhuǎn)向（3），否則，結(jié)束程序，輸出聚類結(jié)果。

4 實(shí)驗(yàn)仿真

4.1 聚類為空實(shí)例

在離散的樣本點(diǎn)中，采用連續(xù)化方法選取中心點(diǎn)而不加處理，就可能導(dǎo)致某個(gè)中心點(diǎn)的聚類結(jié)果為空類。采用粒子群（PSO）方法優(yōu)化的K-means方法就存在這個(gè)問(wèn)題。下面將取Iris數(shù)據(jù)集中部分點(diǎn)（取72個(gè)樣本，分別來(lái)自3個(gè)類別）作為例子說(shuō)明聚類結(jié)果為空是可能的。

將該72個(gè)點(diǎn)劃分為3類，此時(shí)粒子的可能解區(qū)域?yàn)榫匦斡騕1.0，6.9]×[0.1，2.5]，某一次粒子更新后，有兩個(gè)中心點(diǎn)分別為G1，G2，以G1，G2為圓心，以能夠包含所有點(diǎn)的最小半徑r1，r2作圓，然后再以G1，G2為圓心，以2r1，2r2作圓，劃分出的區(qū)域如圖1，而第三個(gè)中心點(diǎn)因粒子更新進(jìn)入了區(qū)域G，聚類完成后，第三類將成為空類，因?yàn)槿魏我粋€(gè)數(shù)據(jù)點(diǎn)此時(shí)與第三個(gè)中心點(diǎn)的距離必定大于min{r1，r2}，故該數(shù)據(jù)點(diǎn)一定不會(huì)指派到第三類。

圖1 部分Iris數(shù)據(jù)集聚類為空示意圖

而偽均值算法將不會(huì)出現(xiàn)這種情況，如果采用K-means計(jì)算出均值落入?yún)^(qū)域G，所尋找的偽均值就是離該均值最近的一個(gè)樣本點(diǎn)作為新的中心點(diǎn)，至少該點(diǎn)屬于樣本集，如假設(shè)初始化中心點(diǎn)或粒子更新后的聚類中心為x1，x2，x3，對(duì)應(yīng)坐標(biāo)值為（1.4，0.3），（3.0，2.0），（6.0，1.2），此時(shí)聚類中心x2所對(duì)應(yīng)的類會(huì)成為空類，采用偽均值聚類后，會(huì)選擇與聚類中心點(diǎn)最近的樣本點(diǎn)充當(dāng)偽均值，即圖1中的x1'，x2'，x3'，對(duì)應(yīng)坐標(biāo)值為（1.4，0.3），（1.9，0.4），（6.0，1.8），而這三個(gè)聚類中心必定屬于不同類別且均為樣本數(shù)據(jù)點(diǎn)，故不會(huì)出現(xiàn)空類。

4.2 Iris與Wine數(shù)據(jù)集聚類仿真

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

圖2 Iris數(shù)據(jù)散點(diǎn)圖

使用PK-means對(duì)Iris數(shù)據(jù)和Wine數(shù)據(jù)聚類時(shí)參數(shù)設(shè)置如下：類數(shù)K=3，PK-means算法中的參數(shù)，N=10，ρ=0.5，cr1=0.2，cr2=1，ck1=0.5，ck2=0.5，ωmin=0.8，ωmax=1.2。在表1中，給出了聚類次數(shù)與Iris和Wine的各自的錯(cuò)分點(diǎn)個(gè)數(shù)，由于Wine的屬性值比較多，故表中只給出了相應(yīng)的Iris的初始中心點(diǎn)，PK-means算法的最優(yōu)初始中心點(diǎn)分別為樣本集中第49個(gè)，第98個(gè)，第129個(gè)數(shù)據(jù)點(diǎn)，其中，K-means聚類結(jié)果參照文獻(xiàn)[10]。從表1可以看出，K-means對(duì)初始中心點(diǎn)的敏感程度非常大，雖然錯(cuò)分?jǐn)?shù)可以接受，但是PSOK-means、PK-means無(wú)論是從對(duì)初始中心點(diǎn)的依賴程度，還是在分類的準(zhǔn)確程度上，都能夠好于K-means算法，有效減少了聚類的隨機(jī)性，PK-means與PSOK-means具有相同的效果，并沒有因?yàn)橐雮尉刀档途垲愖罱K效果。

表1 分類結(jié)果

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

圖3 Iris與Wine粒子更新代數(shù)與適應(yīng)度值關(guān)系

對(duì)于含有孤立點(diǎn)的數(shù)據(jù)來(lái)說(shuō)，適當(dāng)增加類數(shù)，即K值，一般可以把這些孤立點(diǎn)單獨(dú)聚成類，而并不會(huì)影響數(shù)據(jù)分類，對(duì)于Iris數(shù)據(jù)，增加（14，0）與（20，0.2）兩個(gè)點(diǎn)，這兩個(gè)點(diǎn)很明顯超出了原有數(shù)據(jù)的屬性值范圍而成為孤立點(diǎn)，對(duì)于Wine數(shù)據(jù)增加點(diǎn)（0，0，0，0，0，0，0，0，0，0，0，0，0），然后將增加了孤立點(diǎn)的數(shù)據(jù)聚成4類，結(jié)果如表2。

表2 加入孤立點(diǎn)后聚類結(jié)果

從表2可以看出，Iris數(shù)據(jù)集的第一個(gè)類只有兩個(gè)數(shù)據(jù)點(diǎn)，恰為加入的孤立點(diǎn)（14，0）與（20，0.2），而Wine數(shù)據(jù)集的第三個(gè)類只有一個(gè)數(shù)據(jù)點(diǎn)，該點(diǎn)正是加入的那個(gè)孤立點(diǎn)，而對(duì)于其他的數(shù)據(jù)分類，錯(cuò)分?jǐn)?shù)分別為6個(gè)與18個(gè)，并沒有因?yàn)榧尤肓斯铝Ⅻc(diǎn)而影響到分類效果。如果有必要，可以將分離開的孤立點(diǎn)剔除，然后再重新分類。

5 結(jié)論

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

[1]劉靖明，韓麗川，侯立文.基于粒子群的K均值聚類算法[J].系統(tǒng)工程理論與實(shí)踐，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].計(jì)算機(jī)工程與應(yīng)用，2011，47（21）：130-132.

[5]葉安新，金永賢.基于量子粒子群算法的聚類分析方法[J].計(jì)算機(jī)工程與應(yīng)用，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]閆允一.粒子群優(yōu)化及其在圖像處理中的應(yīng)用研究[D].西安：西安電子科技大學(xué)，2008.

[10]連鳳娜，吳錦林，唐琦.一種改進(jìn)的K-means聚類算法[J].電腦與信息技術(shù)，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.

國(guó)家自然科學(xué)基金（No.51309068）。

沈艷（1965—），女，博士，教授，研究領(lǐng)域?yàn)榭茖W(xué)計(jì)算，系統(tǒng)建模，數(shù)據(jù)挖掘等；余冬華（1988—），男，碩士研究生，研究領(lǐng)域?yàn)榭茖W(xué)計(jì)算，數(shù)據(jù)挖掘；王昊雷（1989—），男，碩士研究生，研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，系統(tǒng)建模。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