一種新的自組織粒子群聚類算法

劉世華，葉展翔，劉向華（溫州職業技術學院 信息技術系，浙江 溫州 325035）

一種新的自組織粒子群聚類算法

劉世華，葉展翔，劉向華
（溫州職業技術學院 信息技術系，浙江 溫州 325035）

針對粒子群優化（PSO）算法復雜度偏高的問題，提出一種新的基于競爭學習的自組織粒子群聚類（SOPSC）算法。該算法采用每個粒子代表一個聚類中心的編碼方法，通過借鑒自組織映射（SOM）算法的競爭學習機制，采用類內相似度和類間相異度作為指導，使粒子進行自組織飛行，從而達到自動聚類的目的，克服了傳統粒子群聚類算法中粒子編碼復雜、算法復雜度偏高的缺點。實驗證明，該算法聚類精度高、穩定性好，且對初始值和參數不敏感。

粒子群聚類；競爭學習；PSO；SOM；SOPSC

DOI：10.13669/j.cnki.33-1276/z.2015.059

1　概 述

隨著群體智能算法的發展及其廣泛應用，各種智能算法廣泛應用于數據聚類，粒子群優化（PSO）算法就是其中重要的一種。2002年Omran等提出一種基于粒子群優化的無指導圖像分類算法［1］，這被認為是最早提出的基于PSO的聚類算法。之后的粒子群聚類算法大都遵循其基本思想［2］。2003年Merwe等在此算法基礎上提出了基本PSO算法［3］，用于對一般數據集進行聚類操作。同時，他們還研究了PSO算法與傳統K-means算法相結合的混合聚類算法，經實驗發現，混合方法部分改進了K-means算法容易陷入局部最優的缺點，但該算法復雜度偏高［2-3］。這是由于基本的粒子群聚類每個粒子代表一個數據劃分（聚類結果），導致單個粒子編碼的維度過大造成的。隨后，人們又將粒子群與模糊C均值算法進行結合用以改進算法效率。李峻金等對粒子群聚類算法進行了綜述，介紹了后續的一些改進工作［2］。劉春曉對PSO算法進行了大量實驗研究，并提出一種基于自組織映射（SOM）神經網絡和PSO的聚類組合算法，即SOM/PSO算法，該算法利用SOM的聚類結果初始化P S O的粒子位置，可以減少聚類算法的收斂時間，提高聚類精度［4］。

目前，所有的PSO算法及其改進都沒有對粒子編碼進行簡化，它們均采用一個粒子代表一個全局聚類中心的編碼方式。如果待聚類數據每個數據點有n維，將聚類成k類，那么每個粒子就需要至少n×k維的向量來進行編碼，直接導致了PSO算法的復雜度偏高。為有效解決這一問題，本文提出一種新的基于競爭學習的自組織粒子群聚類（Self-organized PSO Clustering，簡稱SOPSC）算法。SOPSC算法將每個粒子編碼為一個聚類中心點，每個粒子只需要n維，共投放k個粒子即可，在粒子飛行時，引入SOM算法中的“勝者為王”（Winner-takes-all，簡稱WTA）的競爭學習機制，并通過類內相似度和類間相異度特征進行引導，從而提高PS O算法的效率。實驗證明，該算法聚類效果好于K-Means算法和PSO算法，算法穩定性好，每次都能收斂到較好的全局最優解，對初始值和參數不敏感，且聚類效率高于PSO算法。

2　粒子群聚類算法

PSO算法的基本思想是通過群體中個體之間的協作和信息共享來迭代式地尋找最優解。在每一次的迭代中，粒子通過跟蹤兩個最優解來指導自己的下一步行動：一個是粒子本身所找到的最優解，稱為個體極值（Pbest）；另一個是整個種群目前找到的最優解，稱為全局極值（Gbest）。

根據以上兩個最優解，標準粒子群算法通過（1）、（2）式來更新自己的移動速度和位置，即：

（1）式為速度更新公式。其中，vi（t+1）是第t+1次迭代時第i個粒子移動的速度，ω為慣性權重，φ1，φ2為局部最優和全局最優的調節權值。

（2）式為位置更新公式，即t+1次迭代中粒子i的位置為第t次的當前位置加上速度更新。

粒子群中的每個粒子都代表待求解的優化問題的一個解，根據速度和位置的更新準則，粒子將最終收斂于一個全局最優解。

根據PSO算法的基本思路，傳統的PSO算法根據數據點的維數n和待聚類的簇數目k，對每個粒子進行n×k維編碼，每個粒子代表一個聚類劃分，其k個聚類的中心點體現在粒子編碼中，如圖1所示。

注：假設n=2，k=3。圖1　PSO算法的粒子編碼

每個粒子在尋求局部最優和全局最優解時應遵循以下適應度函數f：

其中，pi為屬于第Ci個類的樣本數，Nc為聚類簇數目，oi為第i個類的中心，mij為屬于第i個類的第j個樣本，d（x，y）為x與y的距離度量。

傳統的PSO算法將聚類問題看成優化問題，然后采用粒子群優化策略來進行求解，能夠較好地獲得全局最優解，但由于其粒子編碼采用n×k維，當數據的維度增加或聚類數目較大時，粒子的編碼維度急劇增加，這使得PSO算法計算復雜度太高而影響其實用性。

3　自組織粒子群聚類算法

3.1SOM神經網絡與競爭學習

（1）SOM神經網絡。SOM神經網絡是芬蘭Helsink大學的Kohonen教授于1981年提出的，又稱Kohonen網。Kohonen認為，一個神經網絡接受外界輸入模式時，將會分為不同的對應區域，各區域對輸入模式具有不同的響應特征，且這個過程是自動完成的［5］。

自組織競爭型神經網絡是一種無教師監督學習，具有自組織功能的神經網絡。它通過自身的訓練，可以自動對輸入模式進行分類，在網絡結構上，一般由輸入層和競爭層構成兩層網絡，兩層網絡之間各神經元實現雙向連接，且網絡沒有隱含層，有時競爭層各神經元之間還存在橫向連接，如圖2所示。

圖2　SOM神經網絡模型

自組織競爭型神經網絡構成的基本思想是：網絡的競爭層各神經元競爭對輸入模式響應的機會，最后僅有一個神經元成為競爭的勝者，這一獲勝神經元則表示對輸入模式的分類。如果H為空間的連續輸入數據，A為空間的離散輸出空間，Ф為特征映射的非線性變換，它映射輸入空間H到輸出空間A表示為：Ф：H→A。

如果給定輸入向量X，SOM神經網絡首先根據特征映射Ф確定其在輸出空間A中的最佳匹配神經元i。神經元i的突觸權值向量Wi可以視為神經元指向輸入空間X的映射。

在SOM網絡模型中，每一個權系數向量都可以看作是輸入向量在神經網絡中的一種內部表示，或者說，它是輸入向量的映像，其自組織功能的目的就是通過調整權系數，使神經網絡收斂于一種表示形態。

（2）競爭學習原理。SOM神經網絡成功的關鍵就是其競爭學習方法。網絡的輸出神經元之間相互競爭以求被激活，結果在每一時刻只有一個輸出神經元被激活。這個被激活的神經元稱為“競爭獲勝神經元”，而其它神經元的狀態被抑制，故稱為“勝者為王”。

競爭學習過程主要有以下三個步驟：

步驟1：將當前輸入模式向量X和競爭層中各神經元對應的權重向量Wj（j=1，2，…，m，表示m個競爭神經元）全部進行歸一化處理，即：

步驟2：通過計算輸入向量和m個競爭神經元的內積競選出獲勝神經元j*，使其符合：

步驟3：對獲勝神經元權重Wj*和學習率η進行調整，直到學習率η為0，學習結束，即：

其中學習率η是一個小于1的依次遞減的參數，用于確保算法的收斂。

3.2SOPSC算法

SOPSC算法引入了競爭學習的思想，并對傳統PSO算法進行了改良，簡化了每個粒子的編碼，將每個粒子編碼為一個聚類中心，即每個粒子只代表某一類的中心點，同時對粒子的位置和速度更新規則進行設定。

（1）局部最優部分Pbest，采用聚類中心點來代表，即聚類中心點作為當前簇中粒子應到達的最優位置，如果有新的數據點加入該聚類，則需更新該簇中的粒子和該聚類中心點Pbest。

（2）由于每個粒子編碼只代表一個聚類中心，聚類迭代過程中無法確定每一個聚類中心的全局最優位置，因而新算法中取消全局最優部分Gb es t。

（3）對于一次循環中未獲勝的粒子，出于保持類間相異度考慮，將這些粒子對照獲勝粒子進行反彈移動操作，即讓其他粒子遠離獲勝中心點。

（4）對于在整個迭代過程中一直都沒有獲勝的粒子，直接將其轉移到類內相似度比較小（歐式距離比較大）的粒子附近，讓其下一輪參與該區域的競爭，使其用于將原來聚類數據點較多的簇進一步區分。

SOPSC算法偽代碼如下：

其中，f（x）為在x所在聚類簇中，以x為中心點計算均方差的值，以此來判斷x在聚類中的中心性；xmax_dist（t）為類內相似度比較小（歐式距離比較大）的粒子的當前位置；distance（yi，xj）用于計算輸入點yi與粒子xj的歐式距離。

4　實驗驗證

為驗證算法的有效性，首先采用Ruspini數據集進行初步實驗，并給出原始數據點分布，采用SOP SC的粒子分布和K-Means算法聚類的簇中心點分布的直觀圖示觀察算法的穩定性；然后采用UCI的Iris數據集進行實際數據的聚類驗證，分別采用兩種算法運行100次，比較它們的平均結果和算法穩定性；同時，針對SOPSC算法，通過實驗分析算法中權重參數和初始值對聚類結果的影響。實驗證明，SOPSC算法聚類精度高、穩定性好，且對初始值和參數不敏感，是一種理想可行的聚類算法。

4.1Ruspini數據集的直觀驗證實驗

Ruspini數據集是一個有75個二維數據點的數據集，分為4類，分別有20、23、17和15個數據點，主要用于進行模糊聚類算法的評估。Ruspini數據集原始數據分布如圖3所示。

采用K-means算法k=4時對正規化后的數據進行聚類，從運行結果看，K-means算法穩定性不高，比較容易受到初始值的影響，其較好和較差結果如圖4所示。

圖3　Ruspini數據集原始數據分布

圖4　K-means聚類中心分布情況

采用SOPSC算法，使用4個粒子，全部放在中心位置，vmax=0.01，ω=0.95，算法迭代100次。在進行聚類前，將數據集中的點進行線性縮放，將數據點的坐標值全部映射到［0，1］區間。此時，SOPSC粒子分布情況如圖5所示。

由Ruspini數據集已知數據點的分類情況，因而可以比較兩種聚類算法的聚類正確性。從實際聚類結果看，SOPSC算法的聚類正確率在每次運行時當迭代次數在20次以上即可達到100%；而K-Means聚類算法在初始值分布不理想時，效果很差，從多次重復試驗結果看，平均每運行5~6次，才出現1次最優結果，其最優結果能達到100%。

4.2真實數據集的聚類比較實驗

為進一步驗證算法的實用性，采用UCI提供的Iris數據集進行聚類實驗。Iris數據集是以鳶尾花的特征作為數據來源的真實世界的數據，有150個四維的數據點，分為3類，每類50個數據。實驗采用Weka平臺進行，每種聚類算法運行100次取平均值。

圖5　SOPSC粒子分布情況

分別采用K-Means算法和SOPSC算法對Iris數據集進行聚類，并比較它們聚類后的聚類正確性、類內相似度和類間相異度。

（1）聚類正確性采用簡單比較所分的三類中的數據點數目的正確性和計算聚類正確率來度量。聚類正確率ACC定義為正確聚類的數據點數除以總數據點數。

（2）類內相似度采用均方差（即同一簇中數據點到數據中心點的距離的平方和除以數據點數）來度量，第k類的類內相似度記為Simk，即：

其中，Nk為屬于第k個聚類簇中數據點數目，Pk為第k個聚類簇的中心點。dist（xi，Pk）為第i個數據點與第k個聚類中心的距離。類內相似度Simk數值越小，表示聚類效果越好。

（3）類間相異度采用聚類中心點的距離和來度量，記為Diff，即：

由表1可以看出，在Iris數據集上，SOPSC算法的表現略好于傳統的K-Means算法，但也沒有象在Ruspini數據集上的表現一樣達到100%。K-Means算法在某一二次運行中能夠得到近似100%的效果，但由于受初始值影響比較大，其平均效果也受到影響。

表1　Iris聚類正確性

類內相似度和類間相異度計算結果見表2。其計算是基于對原始數據進行線性縮放歸一化到［0，1］范圍內進行，與直接在原始數據上進行聚類和計算的結果不同。聚類的目的就是要根據樣本一定的相似特征進行分組，并使代表類內相似度的參數Simk最小化（Simk越小表示類內的數據點越相似），使類間的相異度最大化（即聚類中心隔得越遠越好）。由表2可以看出，SOPSC算法在類內相似度上結果優于傳統的K-Means算法，而類間相異度則比傳統的K-Means算法略勝一籌。

表2　類內相似度和類間相異度計算結果

在SOPSC算法中，局部最優和輸入向量在速度更新中的權重φ1，φ2分別取［0，1］之間的隨機數即可，對其聚類結果沒有影響。從本質上看，SOPSC算法如果把輸入向量yj部分的影響去除，即如果取φ1=1，φ2=0，則SOPSC算法與K-Means算法是一樣的，因而SOPSC算法也可以看成是對K-Means算法的一種泛化，它只是在K-Means算法的基礎上增加了隨機擾動和當前輸入向量的影響。

5　結 論

本文對自組織粒子群聚類（SOPSC）算法進行了初步的研究和實驗分析。從直觀驗證實驗可以看出，SOPSC算法較K-Means算法穩定。SOPSC算法繼承了PSO算法的全局尋優特性，同時融合了S OM算法中的競爭學習自組織特性，解決了傳統P SO算法復雜度偏高的缺點。從真實數據集的聚類比較實驗可以看出，SOPSC算法在聚類精度上優于傳統的K-Means算法，雖然前者算法時間和復雜度比后者高，但相較于傳統的PSO算法有了較大提高，粒子編碼復雜度有所降低，長度由n×k變成了n。下一步將研究該算法用于實現聚類數目的自動確定、孤立點檢測和實現不同形狀簇的聚類等問題。

［1］Omran M，Salman A，Engelbrecht A P.Image classification using particle swarm optimization［C］//Proceedings of the4th Asia-Pacific Conference on Simulated Evolution and Learning.Piscataway：IEEE Press，2002：370-374.

［2］李峻金，向陽，蘆英明，等.粒子群聚類算法綜述［J］.計算機應用研究，2009，26（12）：4423-4427.

［3］Merwe D D.Data Clustering using Particle Swarm Optimization［C］//Proceedings of IEEE Congress on Evolutionary Computation. Canberra：IEEE Press，2003：215-220.

［4］劉春曉.基于SOM和PSO的聚類算法研究［D］.成都：西南交通大學信息科學與技術學院，2009.

［5］Kohonen T.Self-organized Formation of Topologically Correct Feature Maps［J］.Biological cybernetics，1982，43（1）：59-69.

［責任編輯：田啟明］

A New Self-Organized PSO Clustering Algorithm

LIU Shihua， YE Zhanxiang， LIU Xianghua
（Information Technology Department， Wenzhou Vocational & Technical College， Wenzhou，325035， China）

A Self-organized PSO Clustering （SOPSC） algorithm based on competition learning was proposed against the complexity of PSO clustering algorithm. The algorithm coded one particle as a center of each cluster for clustering analysis. Through the competition learning of SOM algorithm， particles flew as self-organized manner directed by the inner similarity and dissimilarity between different clusters to achieve the goal of self-clustering. It overcame the complexity of particle coding and algorithm of traditional PSO clustering. It was tested that the algorithm improves the cluster accuracy and its stability and is not sensitive to the initial value and parameters.

PSO clustering； Competition learning； PSO； SOM； SOPSC

TP311.13

A

1671-4326（2015）03-0054-05

2014-05-14

溫州職業技術學院科研項目（WZY2014032）

劉世華（1978—），男，江西永豐人，溫州職業技術學院信息技術系講師，高級工程師，碩士；葉展翔（1971—），男，浙江溫州人，溫州職業技術學院信息技術系，高級工程師，碩士；劉向華（1980—），女，湖南隆回人，溫州職業技術學院信息技術系講師，碩士.