衣俊艷，杜小鵬

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

1 引言

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

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

Durbin-Willshaw[8]的彈性網(wǎng)絡(luò)算法（ENA），最初是一種啟發(fā)式方法，用于解決TSP（Traveling Salesman Problem）問題。與其他神經(jīng)網(wǎng)絡(luò)算法相同，它同樣具有無監(jiān)督學(xué)習(xí)，無需人工指導(dǎo)的優(yōu)點(diǎn)，但是其網(wǎng)絡(luò)結(jié)構(gòu)簡單，計(jì)算復(fù)雜度較其他神經(jīng)網(wǎng)絡(luò)大大降低。后來，它被用于數(shù)據(jù)統(tǒng)計(jì)[9-10]，模式研究[11-13]和圖像識(shí)別[14]中的各種問題。

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

2 具有中心移動(dòng)特性的彈性網(wǎng)絡(luò)算法

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

2.1 算法理論

在聚類問題中，SED 值是常用的評(píng)價(jià)指標(biāo)之一。SED值可用式（1）表示：

其中，nj是屬于第j類數(shù)據(jù)的個(gè)數(shù)，k是聚類數(shù)。在此基礎(chǔ)上，面向聚類的目標(biāo)，同一類中的對(duì)象之間的相似度最大，本文調(diào)整并優(yōu)化了彈性網(wǎng)絡(luò)的能量函數(shù)。本文提出的CMENA 算法是一種神經(jīng)網(wǎng)絡(luò)聚類算法。給定具有n個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集，首先計(jì)算出所有數(shù)據(jù)點(diǎn)的重心，再以重心為圓心，在圓上均勻生成k個(gè)聚類中心神經(jīng)元，聚類中心神經(jīng)元的個(gè)數(shù)就是聚類的類數(shù)目。圓的半徑可由公式（2）確定：

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

其中i=1，2。

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

即聚類中心yj與數(shù)據(jù)點(diǎn)xi之間歐式距離的平方，對(duì)應(yīng)于SED值的距離衡量標(biāo)準(zhǔn)。

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

圖1 CMENA聚類過程

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

對(duì)于數(shù)據(jù)點(diǎn)xi的分布函數(shù)為：

進(jìn)一步得到聚類問題對(duì)應(yīng)物理系統(tǒng)自由能函數(shù)的一般形式[15-16]：

根據(jù)模擬退火算法理論，在退火過程中，系統(tǒng)在每一溫度下達(dá)到平衡態(tài)的過程都應(yīng)遵循自由能減少定律，系統(tǒng)狀態(tài)的自發(fā)變化總是朝著自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小值時(shí)，系統(tǒng)達(dá)到平衡態(tài)。對(duì)應(yīng)于原彈性網(wǎng)絡(luò)理論，該公式也可描述為所有數(shù)據(jù)點(diǎn)對(duì)每個(gè)聚類中心神經(jīng)元的牽引力之和，同樣當(dāng)牽引力達(dá)到最小值時(shí)，系統(tǒng)達(dá)到平衡態(tài)時(shí)。為滿足實(shí)際計(jì)算要求，引入常數(shù)參數(shù)α。本文采用的自由能函數(shù)為：

其中，n是數(shù)據(jù)點(diǎn)的總個(gè)數(shù)。

根據(jù)彈性網(wǎng)絡(luò)算法理論，通過對(duì)自由能函數(shù)求導(dǎo)，可得到動(dòng)量公式：

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

采用一個(gè)小聚類問題的實(shí)際聚類過程圖進(jìn)一步說明CMENA的聚類過程。

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

在原彈性網(wǎng)絡(luò)中考慮神經(jīng)元相互之間的作用力，其聚類中心根據(jù)公式（16）改變：

在圖2和圖3中對(duì)本文算法和上述彈性網(wǎng)絡(luò)結(jié)構(gòu)（ENC）進(jìn)行了對(duì)比，數(shù)據(jù)采用UCI學(xué)習(xí)庫中的wine數(shù)據(jù)集。

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

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

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

2.2 算法分析

對(duì)于初始聚類中心神經(jīng)元的生成方式，考慮三種方法：RAND 方式、ENC 方式和CMENA 方式。下面分別介紹三種不同的方法。RAND方式：在數(shù)據(jù)點(diǎn)中隨機(jī)選取k個(gè)數(shù)據(jù)點(diǎn)作為初始聚類中心神經(jīng)元，k為聚類簇?cái)?shù)；ENC方式：首先計(jì)算出所有數(shù)據(jù)點(diǎn)的重心，以0.1倍的區(qū)域半徑為半徑，在圓上均勻生成k個(gè)數(shù)據(jù)點(diǎn)作為初始聚類中心神經(jīng)元，區(qū)域半徑根據(jù)式（17）計(jì)算：

CMENA 方式：首先計(jì)算出所有數(shù)據(jù)點(diǎn)的重心，再以重心為圓心，以所有數(shù)據(jù)點(diǎn)到重心的距離之和的平均值為半徑，在圓上均勻生成k個(gè)聚類中心神經(jīng)元，聚類中心神經(jīng)元的個(gè)數(shù)就是聚類簇?cái)?shù)。

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

圖4 不同初始聚類中心的聚類結(jié)果

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

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

圖5 參數(shù)實(shí)時(shí)性分析

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

圖6 參數(shù)T 對(duì)聚類質(zhì)量的影響

圖7 參數(shù)T 對(duì)運(yùn)行速度的影響

圖8 參數(shù)α 對(duì)聚類質(zhì)量的影響

圖9 參數(shù)α 對(duì)運(yùn)行速度的影響

α是用來控制每次迭代彈性節(jié)點(diǎn)即聚類中心神經(jīng)元移動(dòng)幅度的大小，在圖8和圖9中設(shè)置參數(shù)T為1、2、3，α設(shè)置為0.1～1。從圖8中可以得知，在合適范圍內(nèi)的α對(duì)聚類的質(zhì)量影響較小。從圖9中可以得知，在T相同的情況下α越大，算法運(yùn)行所需迭代次數(shù)越少。

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

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

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

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

在圖11和圖12中采用一個(gè)分為3簇共60個(gè)數(shù)據(jù)的數(shù)據(jù)集，對(duì)采用不同參數(shù)時(shí)，CMENA 算法的能量函數(shù)的變化過程進(jìn)行了分析?？梢园l(fā)現(xiàn)，能量函數(shù)的總體趨勢為逐漸收斂于0。在T和α取值恰當(dāng)時(shí)，CMENA 算法通常在能量函數(shù)接近0 時(shí)停止，進(jìn)而得到聚類結(jié)果，網(wǎng)絡(luò)收斂。在圖11 中，α的取值為0.1，T的取值為2、4、6、8、10?？梢钥闯?，T越小，算法收斂速度越快，所需聚類時(shí)間越短。在圖12 中，T的取值為3，α的取值為0.2、0.4、0.6、0.8、1.0。實(shí)驗(yàn)發(fā)現(xiàn)α越大，算法收斂速度越快，算法收斂值越偏離于極小值。

為了進(jìn)一步驗(yàn)證本文算法的有效性，采用一組具有8簇共160個(gè)數(shù)據(jù)的二維隨機(jī)數(shù)據(jù)，對(duì)其分別用k-means、k-medoids、ENC、CMENA 算法進(jìn)行了聚類。ENC 和CMENA 算法采用同樣的參數(shù)T=2 和α=0.1，ENC 的β=0.01?？梢詮膱D13和圖14可以清晰地看出k-means、k-medoids在聚類時(shí)，出現(xiàn)將不同簇的數(shù)據(jù)聚為一類，相同簇?cái)?shù)據(jù)聚成兩類的錯(cuò)誤。而在圖15 和圖16 中ENC和CMENA 算法能準(zhǔn)確地將8 簇?cái)?shù)據(jù)聚為8 類。四種聚類算法的SED 值分別為96.83、90.05、46.39、43.77。CMENA 聚類結(jié)果的SED 值比k-means、k-medoids、ENC分別優(yōu)化了55%、46%、6%。

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

圖13 k-means聚類結(jié)果

圖14 k-medoids聚類結(jié)果

圖15 ENC聚類結(jié)果

圖16 CMENA聚類結(jié)果

2.3 算法描述

本文在彈性網(wǎng)絡(luò)的基礎(chǔ)上，針對(duì)聚類問題的特點(diǎn)，依據(jù)聚類評(píng)價(jià)指標(biāo)SED值，調(diào)整并優(yōu)化了彈性網(wǎng)絡(luò)算法的能量函數(shù)，并對(duì)動(dòng)量公式等進(jìn)行了重新的推導(dǎo)。當(dāng)CMENA算法的能量函數(shù)最小化，動(dòng)量公式（14）所得任意yj的Δyj接近于0 時(shí)，算法收斂。CMENA 算法的具體步驟如下：

（1）給定一個(gè)數(shù)據(jù)集X(x1,x2,…,xn)，為方便計(jì)算可以將數(shù)據(jù)統(tǒng)一轉(zhuǎn)化到（0，10）的區(qū)域內(nèi)。給定聚類數(shù)k。根據(jù)數(shù)據(jù)維度高低和數(shù)據(jù)量大小設(shè)置CMENA算法的參數(shù)T和α。

（2）選擇數(shù)據(jù)的前兩維數(shù)據(jù)，根據(jù)公式：

計(jì)算要生成聚類中心神經(jīng)元的圓（彈性帶）的半徑。根據(jù)彈性帶的半徑生成具有k個(gè)彈性節(jié)點(diǎn)即聚類中心神經(jīng)元的彈性帶，彈性節(jié)點(diǎn)均勻分布在彈性帶上，此時(shí)生成的彈性節(jié)點(diǎn)就是初始聚類中心神經(jīng)元Y0(y1,y2,…,yk)。

（3）根據(jù)CMENA算法的動(dòng)量公式：

計(jì)算每個(gè)彈性節(jié)點(diǎn)需要移動(dòng)的距離，根據(jù)公式：

更新聚類中心神經(jīng)元的坐標(biāo)。

（4）計(jì)算由動(dòng)量公式得到的Δyj的最大值，如果Δyj的最大值大于閾值（本文采用0.000 1）時(shí)，重復(fù)步驟（3），直到多次迭代Δyj的最大值均小于閾值，執(zhí)行下一步。

（5）根據(jù)Yend計(jì)算最終的ωij，將數(shù)據(jù)點(diǎn)xi分配給其所屬的ωij最大的聚類中心，得到聚類結(jié)果。

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

本文采用了大量的隨機(jī)數(shù)據(jù)集和真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)仿真。由于隨機(jī)數(shù)據(jù)集無標(biāo)準(zhǔn)的聚類結(jié)果，隨機(jī)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果通過聚類評(píng)價(jià)指標(biāo)SED值來評(píng)估，真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果通過Accuracy 來評(píng)估。Accuracy 的計(jì)算方法如式（18）所示：

其中，ai為屬于第i類的數(shù)據(jù)點(diǎn)是被正確分類的數(shù)據(jù)點(diǎn)個(gè)數(shù)，N為數(shù)據(jù)集中所有數(shù)據(jù)點(diǎn)的個(gè)數(shù)。

3.1 隨機(jī)數(shù)據(jù)集

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

表1 2維和3維的100～900個(gè)數(shù)據(jù)的聚類結(jié)果

表2 5維和10維的100～900個(gè)數(shù)據(jù)的聚類結(jié)果

3.2 真實(shí)數(shù)據(jù)集

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

表3 2維和3維的1 000～10 000個(gè)數(shù)據(jù)的聚類結(jié)果

表4 2維和3維的20 000～100 000個(gè)數(shù)據(jù)的聚類結(jié)果

表5 真實(shí)數(shù)據(jù)集聚類結(jié)果

4 結(jié)束語

本文針對(duì)傳統(tǒng)聚類算法k-means和k-medoids對(duì)初始聚類中心的敏感，導(dǎo)致聚類結(jié)果不穩(wěn)定。雖然彈性網(wǎng)絡(luò)聚類算法ENC 穩(wěn)定，但需花費(fèi)過多時(shí)間的。針對(duì)這些聚類算法的不足，面向聚類問題的特點(diǎn)，提出了具有中心移動(dòng)特性的彈性網(wǎng)絡(luò)聚類算法。實(shí)驗(yàn)證明CMENA具有以下優(yōu)勢：

（1）因?yàn)閺椥跃W(wǎng)絡(luò)的彈性帶生成初始聚類中心神經(jīng)元，聚類結(jié)果穩(wěn)定。

（2）聚類過程中聚類中心神經(jīng)元的位置可跟蹤，實(shí)現(xiàn)聚類過程的實(shí)時(shí)觀測。

（3）運(yùn)算速度較原彈性網(wǎng)絡(luò)結(jié)構(gòu)明顯加快。

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

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

本文根據(jù)聚類的目標(biāo)SED 值調(diào)整并優(yōu)化了彈性網(wǎng)絡(luò)算法的能量函數(shù)，提出了面向聚類分析問題的CMENA算法，通過對(duì)大量隨機(jī)數(shù)據(jù)和真實(shí)數(shù)據(jù)的實(shí)驗(yàn)，驗(yàn)證了CMENA算法的有效性。相較于其他常用的聚類算法，CMENA 性能顯著提高，該算法具有更高的穩(wěn)定性，高效性，準(zhǔn)確性。