結合人工蜂群優化的粗糙K-means聚類算法

葉廷宇，葉 軍,2+，王 暉,2，王 磊,2

1.南昌工程學院 信息工程學院，南昌330000

2.江西省水信息協同感知與智能處理重點實驗室（南昌工程學院），南昌330000

-means 是一種簡單、實用、高效并得到廣泛應用的聚類算法，但該算法在處理模糊、不確定數據聚類時有局限性。為此，Lingras等人引入粗糙集理論對其進行改進，提出了一種粗糙-means 聚類算法，該算法把確定屬于某個簇類的數據劃分到下近似集，不能確定屬于某個簇類的模糊數據歸為邊界集，較好地解決了模糊、不確定數據聚類問題。但粗糙-means 聚類算法采用人為設置固定權重和閾值方式影響了聚類精度，以及初始中心的隨機選取導致聚類結果穩定性降低。研究者從不同角度提出了改進算法，文獻[3-4]結合模糊集，引入了模糊隸屬度，通過隸屬度計算下近似和邊界集中對象的權重，改變了所有對象取相同權重值的問題，增強了算法邊界處理能力。文獻[5-6]提出了一種根據每次迭代的聚類結果動態地確定下一次迭代聚類中樣本點的自適應權重方法，改進了原算法對經驗權重的依賴。文獻[7]引入粒計算理論，運用組合法尋找初始聚類中心，并且通過動態調整上近似集和邊界集的權重,避免了孤立點的影響。文獻[8]提出了一種基于香農熵理論熵的加權多視角協同劃分模糊聚類算法，給出了多視角自適應加權方法，提高了聚類性能。文獻[9]用上近似取代了聚類中心更新公式中的邊界集，以相對距離取代絕對距離作為相異度的判斷標準，有效減小了離群點影響。文獻[10]在歐氏距離中引入權值系數來初始化聚類中心，給出了一種自適應確定值的方法，改變了傳統隨機給定值的方式，提高了穩定性。文獻[11-12]結合群智能優化算法，分別用遺傳算法和蟻群算法改進了初始中心點選擇方式，降低了初始中心點的敏感性和數據差異性帶來的不利影響。文獻[13]引入區間2-型模糊集度量概念，以此自適應調整邊界區域的樣本對交叉簇類的影響系數，削弱了邊界區域對小規模類簇的中心均值迭代的影響。文獻[14-15]提出了一種以局部密度和距離的混合度量方法來確定邊界區域的對象歸屬，給出了一種魯棒學習策略尋找到最佳簇類數，提高了交疊類簇的聚類精度。文獻[16-17]引入了一種對簇類不均衡程度的自適應度量方法，提出了以類簇不平衡程度作為自適應調整權值的粗糙模糊均值聚類算法，提高了聚類效果。文獻[18]提出了一種以維度加權的歐氏距離計算樣本的密度和權重的方法，以此為基礎選擇個聚類中心，降低了初始聚類中心選取的敏感性。文獻[19]定義了一種點與集合的計算方法，通過不斷找出滿足一定數量離集合最近點來得到個聚類中心，提高了初始聚類中心的穩定性。

隨著聚類的應用領域不斷擴大，其研究價值凸顯，進一步提高聚類質量是廣大研究者一直努力的目標。人工蜂群算法（artificial bee colony，ABC）是較晚涌現出的群智能算法。一些研究結果表明，人工蜂群算法在求解連續優化問題時性能要優于蟻群、遺傳算法和粒子群優化算法。本文將聚類看作一個組合優化的問題，引入ABC 算法進行了改進：一是設計了更為合理的自適應調整上近似、邊界權重和閾值方法，并且在此基礎上定義了新的聚類中心更新計算公式；二是構造了蜜源適應度函數引導蜂群向最優秀的蜜源進行全局搜索，且避免搜索中陷入局部最優；三是以ABC 算法每次迭代求得的最優解作為初始聚類中心并同時進行聚類迭代，克服了原算法對初始聚類中心敏感等問題。實驗結果表明，本文算法提高了聚類效果。

1 粗糙K-means聚類及其改進算法

Lingras 等人把粗糙集的上、下近似兩個算子引入-均值算法中，提出了粗糙-means 聚類算法，其主要內容如下:

該算法主要思想是：以是否存在其他聚類中心與對象的距離與最小距離的差小于閾值為依據，把待分類對象分配到上近似或下近似集，并由式（1）更新聚類中心的位置，不斷重復這個過程，直到每個聚類中心不變。

在后續大量的改進算法中，典型的有Mitra等人提出的粗糙模糊-means 算法，該算法在考慮下近似和邊界集中對象分布不均勻的基礎上引入模糊隸屬度，改進了原算法賦予對象相同的權重的缺陷，隸屬度定義為：

其得到的類C的聚類中心m更新公式為：

其中，為類別數，d為數據點x到類C中心點的距離，為模糊指數，和分別表示下近似和邊界集的權重，且+=1。

隨后，Maji 等人對上述式（3）隸屬度定義進行了修正，定義如下：

式（4）把屬于下近似集即確定了歸屬關系的對象隸屬度設為1，屬于邊界集即不能確定歸屬關系的對象需要計算隸屬度，其得到聚類中心更新公式與式（3）一樣。顯然，式（4）更符合實際，并且減少了計算工作量。

上述這些改進方法是以對象的實際分布距離為依據，賦予對象不同的權重值，修正了下近似和邊界集中所有對象取相同的權重的缺陷。但是，上述研究并沒有改變、和采用固定權重的方式，其忽視了它們在迭代過程中對聚類中心的影響。

2 人工蜂群及其改進算法

Karaboga 等人模擬自然界蜂群的采蜜行為提出了人工蜂群算法，該算法將蜜源位置轉化成優化問題的可行解，蜜源的含蜜量對應優化問題的適應度函數，蜂群尋找蜜源的過程是求最優解的過程。蜂群由引領蜂、跟隨蜂和偵察蜂三種分工不同的個體構成。一般引領蜂個數和蜜源個數相等，且一個蜜源只有一只引領蜂開采，算法基本步驟如下：

初始化階段：隨機產生個候選解（即蜜源位置）{,,…,x},它們是維向量，并計算每個候選解的適應度，并從大到小排列，前一半為引領蜂，后一半為跟隨蜂和偵察蜂。設定蜂群總循環搜索次數為，每個蜜源的可重復開采次數為。

引領階段：引領蜂在其蜜源周圍進行搜索，并由式（5）進行蜜源位置更新，保留適應度值較好的蜜源。

其中，v表示新蜜源位置，∈{1,2,…,}，∈{1,2,…,},、為隨機數且≠，φ為[-1,1]內的隨機數，其控制著x鄰域的搜索范圍。

跟隨階段：跟隨蜂在獲得引領蜂傳達的蜜源信息后，采用輪盤賭方法，由式（6）得到的概率選擇引領蜂，然后跟隨蜂依據式（5）在蜜源的領域產生一個新的蜜源，并且比較前后兩個蜜源的適應度值，保留函數適應度較好的蜜源。

其中，p是第個解的選擇概率；fit是第個解的適應度值；是解的個數。當引領蜂經過次循環后，蜜源不再變化，則引領蜂離開該蜜源，變為偵察蜂，隨機產生新的蜜源。

人工蜂群算法具有魯棒性強、搜索能力強等優點。但存在容易陷入局部最優、后期收斂速度慢等問題，研究者們提出了多種改進方法。如Wang等人針對不同問題設計了與之對應的目標函數，提出一種多策略蜂群算法；Gao 等將差異進化算法與全局最優粒子改進的蜂群算法相結合，提出了一種收斂速度更快的算法，該方法將群體最好解的信息引入到候選蜜源的生成中,位置更新公式修改為：

其中，x為迄今蜂群找到的最好蜜源，α∈[0,1]。本文借鑒Gao 等構建的蜜源位置更新式（7）來優化本文算法。

3 人工蜂群優化的粗糙K-means聚類算法

3.1 下近似和邊界權重的改進

在粗糙-means 算法中，聚類中心更新式（1）中的和采用的是固定的權重值，即在整個聚類過程中這兩個值始終保持不變。由于聚類中心的尋找是一個不斷迭代更新的動態過程，這種固定權重的方式沒有客觀反映下近似和邊界集對聚類中心影響的程度。合理度量下近似和邊界區域對于聚類中心位置更新影響的重要度，動態分配和的權值是提高聚類精度的有效途徑之一。為此，文獻[5]和文獻[7]提出了改進方法，在分析了聚類中心初期與后期位置的變化情況下，構造了一個Logistic增長曲線：

式中，為聚類算法迭代次數，、、為函數的調節參數。從式（8）可以看出，隨著迭代次數的增加，權重值逐漸增大，而逐漸減小，該曲線在一定程度上動態地反映了其對聚類中心作用的重要程度。但該曲線存在不足：一是，曲線中的調節參數、和人為事先給定，主觀性強，當迭代次數不斷增大時,下近似集的權重幾乎沒有發生變化；二是，曲線沒有體現下近似和邊界集中對象數量的變化情況，也沒有反映不同對象在上近似和邊界集中分布的差異性。文獻[9]給出了一種以下近似集中對象個數和上近似集中對象個數比值的自適應確定權值公式：

文獻[12]給出了一種以下近似集中對象個數和邊界集中對象個數比值的自適應確定權值公式：

式（9）和式（10）以樣本對象的歸屬變化來動態確定和的權重值，客觀上體現了在聚類過程中上、下近似集和邊界集中數據對象數量的此消彼長動態變化情況。但是，僅以上、下近似集和邊界集中對象個數來確定權重，無法反映類內和內間樣本對象分布的差異性。事實上，同一類別內，數據集中的對象相對于聚類中心的距離分布不盡相同，其對聚類中心的作用不一樣。不同類別間，數據集中的對象對于聚類中心的重要度也存在區別。對于和權重值的確定，不僅要考慮下近似和邊界集中對象數量變化的影響，也要體現對象對于聚類中心因距離分布差異性帶來的影響。綜合這些因素，本文給出一種自適應動態調整下近似和邊界集的權重方法。

設x為任意類別C下近似集中的對象，m為C的聚類中心，則下近似集中對象到聚類中心的距離分布為：

設x為任意類別C邊界集中的對象，m為C的聚類中心，則邊界集中對象到聚類中心的距離分布為：

3.2 閾值自適應改進

閾值決定了樣本對象是劃分到類別中的上近似還是下近似集中。在經典的粗糙-means 算法中是人為給定的一個定值，這個值不會隨迭代而變化，這影響了對象的精確劃分。文獻[5]給出了一種動態改變的方法：

其中，為迭代次數，＞1。式（15）雖然可以動態調整，但其沒有合理將對象劃分到所屬類別的集合中。一個好的閾值應能夠明確區分出樣本所屬的區域，得到的劃分中樣本歸屬的不確定性小。從聚類過程對象變化情況來看，開始時，對象的歸屬關系不明確，應該大一些，使得對象大多劃入上近似集；隨著迭代次數增加，對象的歸屬關系變得明朗，越來越多的對象劃入類的下近似集，應該小一些。而式（15）隨著迭代次數增加反而變大，這會讓一些本該劃分到下近似集中的對象劃歸到了邊界集中，使對象歸屬的不確定性較大，從而導致聚類精度顯著下降。

其中，是迭代次數，＞1，其對應的閾值曲線如圖1所示。

圖1 自適應閾值的取值曲線Fig.1 Curve of adaptive threshold

從圖1 可以看出，隨著迭代次數增加，逐漸變小，越來越多的對象被劃分到下近似集即確定集中，得到劃分中對象歸屬的不確定性不斷變小。顯然，逐漸變小可以加快對象被劃歸到下近似集中的步伐，有效減少迭代次數，從而提高算法的收斂速度，這在后續的實驗中也得到了驗證。

3.3 適應度函數設計

適應度函數直接決定著蜂群的進化方向、迭代次數以及解的優劣。在ABC 算法中，吸引蜂群的主要因素取決于蜜源的含蜜量的多少，蜜源含蜜量越多，則代表它所處的位置好，其吸引能力就強，由此得到的適應度函數值越優。為使同一類別集合中的對象最大程度相似，而不同類別集合中的對象最大程度相異，本文通過定義類別內聚集度和類別間離散度函數來構造目標函數，并以此來尋找最優的初始聚類中心并進行聚類。

（類內聚集度函數）設對象集={,,…,x},有個樣本，個聚類中心C={,,…,m}，則內聚集度函數為：

（類間離散度函數）設對象集={,,…,x}，有個樣本，個聚類中心C={,,…,m}，則聚類中心的類間離散度函數為：

（適應度函數）適應度計算如下：

其中，(C)為類內聚集度函數值，(C)為類間離散度函數值。在式（19）中，類內聚集度距離越小，類間離散度距離越大，適應度函數值也就越大，獲得的聚類效果越好。

3.4 算法實現步驟

本文算法的核心思想是以蜂群每次迭代得到的蜜源位置作為新的聚類中心，并在此基礎上進行粗糙-means聚類，交替進行。算法將適應度函數fit的值代表蜜源的質量，由式（19）可知，fit值越大，蜜源的含蜜量越高，這樣既保證了每個類別內的樣本對象最大程度聚集，不同類別之間的距離盡可能離散，從而可以避免孤立點的影響，提高了算法的魯棒性，并有效減少迭代次數，在尋找到最優的聚類中心的同時得到最佳聚類結果。算法的流程步驟如下：

給定類別個數，初始閾值，引領蜂和跟隨蜂個數各為，最大迭代次數，控制循環上限數；當前迭代次數，初始值為1。

根據式（19）計算各個蜜源的適應度值，并按大小排序，將前一半設置為引領蜂，后一半為跟隨蜂。

引領蜂按式（7）在鄰域內搜索新的蜜源，采用貪婪選擇原則，若新蜜源適應度值大于原蜜源值，則更新蜜源位置；否則，保持不變。搜索完成后，由式（6）計算概率p。

依據概率p，跟隨蜂基于輪盤賭規則選擇引領蜂，完成所有選擇后，按式（7）進行鄰域搜索，同樣按照貪婪原則保留適應度值高的蜜源。

若有引領蜂在次迭代后，蜜源位置不改變，則引領蜂變為偵察蜂，并隨機產生一個新的蜜源位置。

若達到最大迭代次數，則算法結束并輸出個簇類，否則轉到步驟3，=+1。

3.5 算法時間復雜度分析

與傳統的粗糙-means 算法時間復雜度(×××)相比，本文算法運算次數更多。遺傳算法改進的粗糙-means算法時間復雜度為(+×××)，蟻群算法改進的粗糙-means 算法時間復雜度約為(××××)，其中為蟻群個數。顯然，本文算法運算次數比文獻[11]和文獻[12]算法要少。但是，每執行一次算法，本文算法的運算量稍大一些。

4 實驗結果分析

為驗證本文算法的性能和效果，數據采用了UCI機器學習庫中五個數據集，如表1 所示。軟件環境為Win 7 操作系統及應用軟件Matlab9.0，硬件為CPU Intel I5 1040 3.6 GHz，內存6 GB。性能比較采用類內距離、類間距離、準確率、誤差平方、迭代次數和運行時間等指標，與文獻[1]（傳統的粗糙-means算法）、文獻[11]（遺傳算法改進的粗糙-means 算法）和文獻[12]（蟻群算法改進的粗糙-means算法）進行比較。

表1 實驗數據集信息Table 1 Experimental dataset information

實驗中相關數據設置：文獻[1]和文獻[11]采用的是固權重方式，對不同參數值在Iris 數據集上實驗得到的結果如圖2 所示，在上述其他數據集上也得到類似結果。

圖2 反映了固權重方式對和值敏感，不同的取值會改變聚類中心位置，從而導致聚類準確率顯著下降，這說明了固權重方式沒有準確反映聚類過程中下近似和邊界集對聚類中心影響的程度。因此，實驗時文獻[1]和文獻[11]取最佳值，=0.8，=0.2，=0.05；文獻[12]和本文算法采用自適應權重，∈[0.5,0)，取各數據集對應的類別數，蜂群個數＝60，＝300，＝20。分別在所選的5 個UCI 數據集上進行20次實驗取平均值，實驗結果如表2～表6所示。

圖2 Iris上不同權重取值的分類準確率Fig.2 Accuracy of different weight values on Iris

表2 Iris數據集性能比較Table 2 Performance comparison on Iris dataset

表3 Wine數據集性能比較Table 3 Performance comparison on Wine dataset dataset

表4 Balance-Scale數據集性能比較Table 4 Performance comparison on Balance-Scale dataset

表5 Segmentation 數據集性能比較Table 5 Performance comparison on Segmentation dataset

表6 Sonar數據集性能比較Table 6 Performance comparison on Sonar dataset

從式（17）和式（18）定義的類內和類間距離可知，類內距離越小，對象對聚類中心的分布越緊湊，對象相似度高；類間距離大，則不同類別中對象差異性大，得到的聚類結果誤差就小。從表2～6 對比可知，本文算法在五個數據集上的類內距離、類間距離、誤差平方和迭代次數四個指標都明顯好于其他三個算法。準確率比較上，本文算法在上述五個數據集上好于其他三個算法。在大數據和高維數據集上，傳統粗糙-means 算法聚類的準確率顯著下降，本文算法依然取得了較好的效果。在運行時間上，由于本文算法每迭代一次，要計算下近似和邊界集中對象相對聚類中心的距離分布和對象的隸屬度，計算量比其他三個文獻稍大，在Iris和Wine 數據集上程序運行耗時稍多一些，在Balance-Scale、Segmentation 和Sonar 數據集上與文獻[12]相當。

對于聚類效果比較，本文采用文獻[7]中用各類內對象對于整個數據中心的分布與類內對象距離的比值來衡量聚類效果，它是一種有效衡量聚類效果優劣的指標。其公式為：

由式（20）可知，同一類別中的對象分布越緊湊，距離越小；不同類別中的對象之間越離散，其到整個數據中心的距離越大。顯然，比值的值越大，聚類效果就越好。實驗得到的四種算法在三個數據集上距離比值的情況分別如圖3～圖7 所示。

從圖3～圖7 中的比值可以看出，本文算法得到了較好的聚類效果，而且收劍速度明顯快于其他三個算法。顯然，由人工蜂群優化的算法得到的聚類結果更符合數據實際分布特征。

圖3 Iris數據集上距離比值比較Fig.3 Object distance ratio on Iris dataset

圖4 Wine數據集上距離比值比較Fig.4 Object distance ratio on Wine dataset

圖5 Balance-Scale數據集上距離比值比較Fig.5 Object distance ratio on Balance-Scale dataset

圖6 Segmentation 數據集上距離比值比較Fig.6 Object distance ratio on Segmentation dataset

圖7 Sonar 數據集上距離比值比較Fig.7 Object distance ratio on Sonar dataset

5 結束語

本文結合人工蜂群算法，在借鑒研究者們研究成果的基礎上，對粗糙-means 聚類算法進行了改進。在下近似和邊界集權重分配改進方面，本文給出的自適應動態確定下近似和邊界集的權重方法，既考慮了下近似和邊界集中對象數量變化的影響，也沒有忽略對象對于聚類中心因距離分布差異性帶來的影響，整體上提升了算法的性能。在初始聚類中心優化方面，每次迭代以蜂群找到的最好蜜源更新聚類中心位置并進行聚類，為改善算法因對初始數據的敏感性帶來的不利影響提供了思路。但是，本文算法中設計的自適應權重調整方式增加了算法的計算工作量，在高維且樣本數量多的數據集上更為明顯；另外，簇類數值是事先根據已知簇類數的數據集給定好的。事實上，在實際應用中，很多時候事先并不知道數據集被分成多少簇類最合適。因此，簇類數的選取對算法的聚類效果影響較大。后續將結合文獻[14]和文獻[15]提出的對未知簇類魯棒學習策略，進一步研究自適應尋找最佳類別數的方法。此外，優化本文算法的計算工作量，降低算法的時間復雜度，提升算法的執行效率也是今后要繼續開展的研究工作。