具有中心移動特性的彈性網絡聚類算法研究

衣俊艷，杜小鵬

北京建筑大學 電氣與信息工程學院，北京100044

1 引言

隨著信息技術的飛速發展，聚類分析已成為數據分析最重要的研究方向之一。聚類算法的思想是使劃分為不同類中的對象之間的相似性最小，而同一類中的對象之間的相似度最大[1]。相似度的計算方式有Jaccard相關系數、皮爾森相關系數、歐幾里得距離、余弦相似度等[2]。針對數據集的分布、形狀、數據量以及相似度計算方法等的不同，許多聚類算法已被學者提出。常用的聚類算法可以分為基于劃分的聚類、基于層次的聚類、基于密度的聚類、基于網格的聚類和基于模型的聚類等[3]。

這些算法仍存在缺點，如，k-means和medoids等基于劃分的聚類方法存在聚類結果不穩定[4-6]。與其他聚類方法相比，基于密度的聚類方法可以在嘈雜的數據中找到各種形狀和大小的聚類。但是他們需要密度參數作為停止條件，計算量大，復雜度高。神經網絡算法具有自學習能力和找到最佳解決方案的能力。但是，其找到復雜問題的最佳解決方案通常需要大量的計算。如Teuvo提出的自組織映射算法（SOM）[7]，在模式識別、數據處理、數據挖掘等理論和應用領域中也做了很多貢獻。但是，其網絡初始狀態中權重和參數的選擇對網絡的收斂性影響很大。

Durbin-Willshaw[8]的彈性網絡算法（ENA），最初是一種啟發式方法，用于解決TSP（Traveling Salesman Problem）問題。與其他神經網絡算法相同，它同樣具有無監督學習，無需人工指導的優點，但是其網絡結構簡單，計算復雜度較其他神經網絡大大降低。后來，它被用于數據統計[9-10]，模式研究[11-13]和圖像識別[14]中的各種問題。

由于ENA 算法最初是用于解決TSP 問題，其原網絡結構無法應用于聚類分析。本文依據聚類問題的目標調整并優化了彈性網絡的能量函數，僅考慮數據點對彈性節點即聚類中心的影響力。進而提出了基于中心移動的彈性網絡算法CMENA（Elastic Network Algorithm based on Center Movement for clustering），CMENA算法加強了數據點對聚類中心的影響力，可以使網絡中的彈性節點更快地聚集到最佳聚類中心附近。另外，由于網絡結構簡化，降低了參數選擇難度，減少了算法運行的時間。與k-means和k-medoids等使用隨機生成的初始聚類中心神經元不同，由于該算法使用原始彈性網絡提出的方法生成初始聚類中心神經元，該算法聚類結果唯一。

2 具有中心移動特性的彈性網絡算法

彈性網絡算法最初提出時是應用于求解TSP問題。其基本原理是根據城市點的坐標，計算出所有城市點的質心，再以質心為圓心，生成具有多個彈性節點（elastic points）的封閉小圓環，該圓環稱為彈性帶（rubber band）。隨著彈性網絡能量函數的最小化，彈性節點不斷向城市點移動，直到所有的城市點被彈性節點覆蓋，網絡達到穩定狀態，獲得該TSP問題的近似解。假定彈性節點為Y(y1,y2,…,ym)，其中m是彈性節點的數量。在算法迭代過程中，原彈性網絡通過兩種力來牽引彈性節點的移動：一種是與彈性節點yj相鄰的城市點對彈性節點yj的吸引力，使得彈性節點yj逐漸向城市點靠近；另一種是與彈性節點yj相鄰的彈性節點yj-1和yj+1對彈性節點yj的張力，迫使彈性節點之間的距離最短。本文依據聚類問題的目標調整并優化了彈性網絡的能量函數，提出了CMENA算法，并對算法的原理進行了推理驗證。

2.1 算法理論

在聚類問題中，SED 值是常用的評價指標之一。SED值可用式（1）表示：

其中，nj是屬于第j類數據的個數，k是聚類數。在此基礎上，面向聚類的目標，同一類中的對象之間的相似度最大，本文調整并優化了彈性網絡的能量函數。本文提出的CMENA 算法是一種神經網絡聚類算法。給定具有n個數據點的數據集，首先計算出所有數據點的重心，再以重心為圓心，在圓上均勻生成k個聚類中心神經元，聚類中心神經元的個數就是聚類的類數目。圓的半徑可由公式（2）確定：

其中，G是數據X的二維重心。在解決高維問題時，選取前兩維數據計算圓（即ENA 算法中的彈性帶）的半徑。重心由式（3）計算：

其中i=1，2。

對于給定的聚類中心Y(y1,y2,…,yk)，對應的聚類結果為C(c1,c2,…,ck),xi(i=1,2,…,n) 屬于cj(j=1,2,…,k)這一事件的概率為ωij，聚類問題可描述為求解Y(y1,y2,…,yk)及ωij使得：

即聚類中心yj與數據點xi之間歐式距離的平方，對應于SED值的距離衡量標準。

對于ωij，由于沒有先驗知識，不能確定其具體形式，故用統計物理學的極大熵原理[9]來確定。對于固定的Y(y1,y2,…,yk)，定義聚類的能量函數和熵函數分別為：

圖1 CMENA聚類過程

其中，T是常數參數，T∝t，其中t是模擬退火算法中的溫度系數。

對于數據點xi的分布函數為：

進一步得到聚類問題對應物理系統自由能函數的一般形式[15-16]：

根據模擬退火算法理論，在退火過程中，系統在每一溫度下達到平衡態的過程都應遵循自由能減少定律，系統狀態的自發變化總是朝著自由能減少的方向進行，當自由能達到最小值時，系統達到平衡態。對應于原彈性網絡理論，該公式也可描述為所有數據點對每個聚類中心神經元的牽引力之和，同樣當牽引力達到最小值時，系統達到平衡態時。為滿足實際計算要求，引入常數參數α。本文采用的自由能函數為：

其中，n是數據點的總個數。

根據彈性網絡算法理論，通過對自由能函數求導，可得到動量公式：

其中，ωij可由式（8）得到。Δyj是聚類中心神經元yj需要移動的增量，α用來控制聚類中心神經元yj移動幅度的范圍。聚類中心神經元根據下式更新：

采用一個小聚類問題的實際聚類過程圖進一步說明CMENA的聚類過程。

如圖1 所示，當參數α和T設置合理，隨著彈性網絡的能量函數的最小化，彈性節點即聚類中心神經元在每次迭代時不斷向最佳聚類中心C移動，直到能量函數最小化，Δyj接近于0，聚類中心神經元不再移動，最終所得的聚類中心神經元Yend將無限接近于最佳聚類中心C。最后根據Yend計算最終的ωij，將數據點xi分配給其所屬的ωij最大的聚類中心，得到聚類結果。

在原彈性網絡中考慮神經元相互之間的作用力，其聚類中心根據公式（16）改變：

在圖2和圖3中對本文算法和上述彈性網絡結構（ENC）進行了對比，數據采用UCI學習庫中的wine數據集。

圖2 聚類中心的Δyj 第一維的變化

圖3 聚類中心的Δyj 第二維的變化

為驗證算法的有效性，對聚類過程中第一個聚類中心神經元前兩維數據的Δyj變化軌跡進行了跟蹤。兩種算法設置同樣的參數T=2 和α=0.1，ENC 的β=0.001 時。對兩種算法采用同樣的停止標準，即對于任意yj的Δyj的絕對值均小于0.000 1 時，算法終止。從圖2 和圖3 可以看出，CMENA 算法優先收斂。其中ENC 算法花費了318 次迭代，CMENA 算法僅僅花費了255次迭代。在每次迭代的花費上，由于本文算法網絡結構更加簡單，算法運行時間也少于ENC 算法。在聚類質量上，ENC算法聚類結果的SED值為24 856，CMENA聚類結果的SED為24 410，CMENA較ENC優化了18%。因此CMENA 算法總的運行時間較ENC 算法有較大的減少，求解質量顯著提高。

2.2 算法分析

對于初始聚類中心神經元的生成方式，考慮三種方法：RAND 方式、ENC 方式和CMENA 方式。下面分別介紹三種不同的方法。RAND方式：在數據點中隨機選取k個數據點作為初始聚類中心神經元，k為聚類簇數；ENC方式：首先計算出所有數據點的重心，以0.1倍的區域半徑為半徑，在圓上均勻生成k個數據點作為初始聚類中心神經元，區域半徑根據式（17）計算：

CMENA 方式：首先計算出所有數據點的重心，再以重心為圓心，以所有數據點到重心的距離之和的平均值為半徑，在圓上均勻生成k個聚類中心神經元，聚類中心神經元的個數就是聚類簇數。

為了驗證以上三種方法的有效性，針對同一個三簇共60 個數量的聚類問題，分別采用以上三種初始神經元設置方法進行了求解，聚類結果對比圖如圖4 所示。從圖4可以看出，采用RAND方式的算法求解的SED值大于ENC 和CMENA 方式。采用ENC 算法和CMENA方式均能使算法收斂于更優解。采用RAND、ENC 和CMENA 方式所得聚類結果的SED 值分別為92.91、25.44、25.35，相比于RAND 和ENC 方式，CMENA 分別優化了72.7%、0.4%。另外，采用ENC 和CMENA 方式算法收斂速度較采用RAND方式更快。相比于ENC方式，CMENA方式能更快的收斂。

圖4 不同初始聚類中心的聚類結果

由此可見，RAND 方式隨機性大，無法保證初始聚類中心的分布狀態，所得聚類結果不穩定。ENC方式雖然能在數據的區域范圍能均勻的得到初始聚類中心神經元，但沒有充分考慮數據的分布情況，容易受到孤立點的影響。CMENA方式以數據的重心作為圓心，充分考慮了數據的分布狀況，且其半徑的確定也考慮到每個數據點，使得CMENA 方式算法收斂最快，所得的聚類結果更好。因此本文中采用CMENA 方式作為初始聚類中心神經元的生成方法。

經過實驗發現，本文算法中參數α的取值范圍為（0.1，1），參數T的取值與數據量有所關聯，對于數據量為0～1 000的聚類問題，T=3；對于數據量為1 000～5 000的聚類問題，T=6；對于數據量為5 000～10 000的聚類問題，T=9；對于數據量為10 000 的聚類問題，T取（10，100）的隨機整數。為了驗證參數選擇策略的有效性和算法運算的實時性，本文采用一系列隨機生成的二維數據集進行了驗證，將它們聚為三類，通過上述的參數選擇方法選擇了CMENA 的參數，實驗結果如圖5 所示。從圖5中可知，算法所需迭代次數與數據量的大小無關，證明了上述參數選擇方案的正確性和有效性，以及算法運算的實時性，體現了CMENA算法在解決大數據量問題時的優勢。

圖5 參數實時性分析

CMENA 算法主要有兩個參數T和α，在圖6 至圖9 使用分為三簇的二維隨機數據集對參數T和α在CMENA算法中的作用進行分析。其中“?”代表聚類成功，“×”代表聚類失敗。此處采用一個分為三簇，共60個數據點的數據集。在圖6 和圖7 中，分別將α設置為0.5、1、5，將T設置為1～10的整數。從圖6和圖7可知，在α相同時，T值越大，算法收斂性越差，容易導致聚類失敗，算法所需迭代次數越多；反之T值越小，越有利于算法快速收斂，算法運行時間越短。但根據原彈性網絡算法理論，如果在算法初始階段，T值過小，會導致算法的能量函數收斂于某一極小值，無法得到正確的聚類結果。因此本文在算法初始階段給參數T設置一個較大的初始值，在算法演進時T不斷衰減，直到T=0.01。以提高網絡在算法初始階段的活性，使得相似度大的數據點對同一聚類中心的牽引力顯著增強，后期通過減小參數T，使已經在相似度較大的數據點附近聚類中心神經元向更加接近最佳聚類中心的位置移動，最終實現聚類中心神經元與最佳聚類中心盡可能地重合，得到好的聚類結果。

圖6 參數T 對聚類質量的影響

圖7 參數T 對運行速度的影響

圖8 參數α 對聚類質量的影響

圖9 參數α 對運行速度的影響

α是用來控制每次迭代彈性節點即聚類中心神經元移動幅度的大小，在圖8和圖9中設置參數T為1、2、3，α設置為0.1～1。從圖8中可以得知，在合適范圍內的α對聚類的質量影響較小。從圖9中可以得知，在T相同的情況下α越大，算法運行所需迭代次數越少。

在圖10 中采用8 簇共160 個數據的聚類問題通過對CMENA、k-means、k-medoids 三種算法在聚類過程中SED值的變化分析發現。從圖10可以看出k-means，k-medoids 收斂速度極快，但CMENA 算法的聚類結果的SED優于其他兩種算法，且CMENA算法聚類時SED值的變化過程也更加平滑。實際上k-means、k-medoids和CMENA分別用4、7、261次迭代。k-means、k-medoids和CMENA 算法的聚類結果的SED 分別為94.6、95.3、43.7，CMENA 算 法 較k-means 和k-medoids 優 化 了53.8%、54.1%。另外SOM 的SED 值為45.5，CMENA 相比于SOM優化了4.0%。

圖10 不同算法聚類過程中SED的變化

圖11 不同T 值下，自由能函數的變化

圖12 不同α 值下，自由能函數的變化

在圖11和圖12中采用一個分為3簇共60個數據的數據集，對采用不同參數時，CMENA 算法的能量函數的變化過程進行了分析。可以發現，能量函數的總體趨勢為逐漸收斂于0。在T和α取值恰當時，CMENA 算法通常在能量函數接近0 時停止，進而得到聚類結果，網絡收斂。在圖11 中，α的取值為0.1，T的取值為2、4、6、8、10。可以看出，T越小，算法收斂速度越快，所需聚類時間越短。在圖12 中，T的取值為3，α的取值為0.2、0.4、0.6、0.8、1.0。實驗發現α越大，算法收斂速度越快，算法收斂值越偏離于極小值。

為了進一步驗證本文算法的有效性，采用一組具有8簇共160個數據的二維隨機數據，對其分別用k-means、k-medoids、ENC、CMENA 算法進行了聚類。ENC 和CMENA 算法采用同樣的參數T=2 和α=0.1，ENC 的β=0.01。可以從圖13和圖14可以清晰地看出k-means、k-medoids在聚類時，出現將不同簇的數據聚為一類，相同簇數據聚成兩類的錯誤。而在圖15 和圖16 中ENC和CMENA 算法能準確地將8 簇數據聚為8 類。四種聚類算法的SED 值分別為96.83、90.05、46.39、43.77。CMENA 聚類結果的SED 值比k-means、k-medoids、ENC分別優化了55%、46%、6%。

總之，與k-means 和k-medoids 算法相比，CMENA聚類質量顯著提高。相較于ENC算法，CMENA首先減少了參數的選擇難度，其次降低了算法運行花費的時間，在聚類質量上也有較大提高。

圖13 k-means聚類結果

圖14 k-medoids聚類結果

圖15 ENC聚類結果

圖16 CMENA聚類結果

2.3 算法描述

本文在彈性網絡的基礎上，針對聚類問題的特點，依據聚類評價指標SED值，調整并優化了彈性網絡算法的能量函數，并對動量公式等進行了重新的推導。當CMENA算法的能量函數最小化，動量公式（14）所得任意yj的Δyj接近于0 時，算法收斂。CMENA 算法的具體步驟如下：

（1）給定一個數據集X(x1,x2,…,xn)，為方便計算可以將數據統一轉化到（0，10）的區域內。給定聚類數k。根據數據維度高低和數據量大小設置CMENA算法的參數T和α。

（2）選擇數據的前兩維數據，根據公式：

計算要生成聚類中心神經元的圓（彈性帶）的半徑。根據彈性帶的半徑生成具有k個彈性節點即聚類中心神經元的彈性帶，彈性節點均勻分布在彈性帶上，此時生成的彈性節點就是初始聚類中心神經元Y0(y1,y2,…,yk)。

（3）根據CMENA算法的動量公式：

計算每個彈性節點需要移動的距離，根據公式：

更新聚類中心神經元的坐標。

（4）計算由動量公式得到的Δyj的最大值，如果Δyj的最大值大于閾值（本文采用0.000 1）時，重復步驟（3），直到多次迭代Δyj的最大值均小于閾值，執行下一步。

（5）根據Yend計算最終的ωij，將數據點xi分配給其所屬的ωij最大的聚類中心，得到聚類結果。

3 實驗仿真

本文采用了大量的隨機數據集和真實數據集進行實驗仿真。由于隨機數據集無標準的聚類結果，隨機數據集的實驗結果通過聚類評價指標SED值來評估，真實數據集的實驗結果通過Accuracy 來評估。Accuracy 的計算方法如式（18）所示：

其中，ai為屬于第i類的數據點是被正確分類的數據點個數，N為數據集中所有數據點的個數。

3.1 隨機數據集

由于k-means、k-medoids 算法對初始聚類中心敏感，其聚類結果的SED 值取20 次聚類結果的平均值。對于在預定時間內無法得到聚類結果情況，使用N/A標記。在表1和表2中，列出了k-means、k-medoids和CMENA算法在100到900個數據時聚類結果的SED值。CMENA算法聚類結果的SED比k-means平均小18%，比k-medoids平均小20%。在表3 中，列出了k-means、k-medoids 和CMENA算法在1000～10 000個數據時聚類結果的SED值。CMENA 算法聚類結果的SED 值比k-means 平均小21%。除10 000 個數據點外，與k-medoids 相比，CMENA聚類結果的SED值平均優化了18%。在表4中列出了k-means和CMENA算法在20 000～100 000個數據時聚類結果的SED 值。由于k-medoids 算法無法在預計時間內得到聚類結果，所以未曾列出。CMENA算法聚類結果的SED 值平均比k-means 小15%。從表3可以看出CMENA算法可以解決比k-medoids更大數量級的聚類問題。

表1 2維和3維的100～900個數據的聚類結果

表2 5維和10維的100～900個數據的聚類結果

3.2 真實數據集

選擇了UCI 機器學習庫中數據集進行真實數據聚類的準確率，包括Zoo、Iris、Wine、Handwritten Digits 和Skin 數據集。k-means 和k-medoids 對初始點的選擇敏感，故對數據量較小的三個數據集取20 次運行結果的平均值，對其余取10 次運行結果的平均值。由于k-medoids 聚類算法對“HandwrittenDigits”和“Skin”數據集的聚類未能在預期的時間內完成，因此未在表5中列出。從表5可以看出，CMENA算法準確率比k-means平均提高12%。對數據集Zoo、Iris 和Wine 的CMENA的聚類準確率比k-medoids 的平均高14%。與SOM 相比，SOM也不能在預期時間內解決Digits和Skin數據集的聚類問題，對于其他三個數據集的聚類中，CMENA在準確率上也平均有19%的優化。原始的彈性網絡通常只能解決數百個數據的TSP 問題。而CMENA 算法所解決的Skin 數據集的聚類問題有24 萬個數據之多。在k-medoids 和SOM 聚類算法都無法解決的情況下，CMENA 算法卻能在短時間內解決并且得到的聚類結果的準確率比k-means高15%。

表3 2維和3維的1 000～10 000個數據的聚類結果

表4 2維和3維的20 000～100 000個數據的聚類結果

表5 真實數據集聚類結果

4 結束語

本文針對傳統聚類算法k-means和k-medoids對初始聚類中心的敏感，導致聚類結果不穩定。雖然彈性網絡聚類算法ENC 穩定，但需花費過多時間的。針對這些聚類算法的不足，面向聚類問題的特點，提出了具有中心移動特性的彈性網絡聚類算法。實驗證明CMENA具有以下優勢：

（1）因為彈性網絡的彈性帶生成初始聚類中心神經元，聚類結果穩定。

（2）聚類過程中聚類中心神經元的位置可跟蹤，實現聚類過程的實時觀測。

（3）運算速度較原彈性網絡結構明顯加快。

（4）聚類準確率較k-means，k-medoids 以及SOM等聚類算法均有顯著的提高。在聚類數目k較大時，CMENA仍能準確地根據聚類數k聚類。

（5）解決大數據量聚類問題的能力有了極大的提高，最大解決了24萬數據的聚類問題。

本文根據聚類的目標SED 值調整并優化了彈性網絡算法的能量函數，提出了面向聚類分析問題的CMENA算法，通過對大量隨機數據和真實數據的實驗，驗證了CMENA算法的有效性。相較于其他常用的聚類算法，CMENA 性能顯著提高，該算法具有更高的穩定性，高效性，準確性。