衣俊艷，吳博雅，雍巧玲

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

2.喀什大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，新疆 喀什844000

1 引言

聚類是目前處理數(shù)據(jù)的重要手段之一，已廣泛應(yīng)用于諸如生物學(xué)[1-2]、圖像處理[3]、金融分析[4-5]等學(xué)科領(lǐng)域。聚類是根據(jù)一組定義，將一組對(duì)象劃分為多個(gè)集群的過程，其目的是使同一集群中的對(duì)象比不同集群中的對(duì)象彼此間更加相似[6]。與監(jiān)督學(xué)習(xí)相比，聚類算法通常屬于無監(jiān)督學(xué)習(xí)范疇，這也增加了數(shù)據(jù)聚類的難度。聚類分析技術(shù)不僅可以挖掘數(shù)據(jù)之間的內(nèi)在聯(lián)系，揭示數(shù)據(jù)的分布特性，還可以作為數(shù)據(jù)的一種預(yù)處理方式，便于后續(xù)的數(shù)據(jù)分析任務(wù)[7]。

傳統(tǒng)的聚類算法可以分為五類：基于劃分的聚類、基于網(wǎng)格的聚類、基于層次的聚類、基于密度的聚類、基于模型的聚類。近年來出現(xiàn)了很多新的聚類算法，如基于粒度的聚類算法、基于熵的聚類算法、不確定聚類算法、譜聚類算法、核聚類算法等[8-9]。雖然目前已經(jīng)有很多關(guān)于聚類的算法，但這些算法仍存在以下缺點(diǎn)：可伸縮性差；容易受到噪聲點(diǎn)、離群值等因素的影響；無法自動(dòng)確定簇?cái)?shù)；無法聚類非線性可分離數(shù)據(jù)集；多維空間聚類質(zhì)量變差等[10]。

基于劃分的聚類算法如k-means、k-medoids等，其中k-means算法[11-13]具有簡(jiǎn)單、高效等優(yōu)點(diǎn)，但其由于對(duì)噪聲點(diǎn)及數(shù)據(jù)輸入順序的敏感性導(dǎo)致算法結(jié)果不穩(wěn)定的問題是不容忽視的。k-medoids[14]雖然針對(duì)該問題進(jìn)行了改進(jìn)，但仍未徹底解決。此外，基于劃分的聚類算法大多不能很好地處理具有非凸特性的數(shù)據(jù)集?；诰W(wǎng)格的聚類算法如STING（STatistical INformation Gridbased method）[15]、CLIQUE（Clustering in Quest）[16]等，擅長(zhǎng)解決高維大型的數(shù)據(jù)集，但其求解質(zhì)量有待提高?；趯哟蔚木垲愃惴ㄈ鏑URE[17]，能以較低的時(shí)間復(fù)雜度解決大型數(shù)據(jù)集，但也存在聚類結(jié)果不穩(wěn)定、聚類質(zhì)量不高等問題?；诿芏鹊木垲愃惴ㄈ鏒BSCAN（Density-Based Spatial Clustering of Applications with Noise）[18]、MeanShift[19]等，可以發(fā)現(xiàn)數(shù)據(jù)集中任意形狀的集群，可以排除噪聲的干擾，但不能很好地解決高維問題。基于模型的聚類算法如COBWEB、SOM 等，其中典型的統(tǒng)計(jì)學(xué)方法COBWEB[20]的算法簡(jiǎn)單，能夠快速處理數(shù)量級(jí)大的數(shù)據(jù)集，但無法很好地處理多維數(shù)據(jù)集。典型的神經(jīng)網(wǎng)絡(luò)方法SOM（Self-Organizing Map）[21]，能夠很好地處理高維數(shù)據(jù)，不受噪聲點(diǎn)的影響，但該算法存在不能保證網(wǎng)絡(luò)全局收斂等問題。

由SOM網(wǎng)絡(luò)延伸出來的彈性網(wǎng)絡(luò)算法（Elastic Net Method）在1987 年被Durbin 和Willshaw 提出[22]，該方法提出伊始被用來解決具有NPC計(jì)算復(fù)雜性的旅行商問題（Traveling Salesman Problem，TSP）。在沒有先驗(yàn)知識(shí)的條件下進(jìn)行聚類，一種有效的方法是設(shè)定一個(gè)聚類的目標(biāo)函數(shù)，求解該函數(shù)的最小值，從而獲得具有最佳分布函數(shù)的聚類方案。彈性網(wǎng)絡(luò)非常適合求解這類問題，可以針對(duì)目標(biāo)函數(shù)自動(dòng)求解，不需要其他人工指導(dǎo)訓(xùn)練，且保證網(wǎng)絡(luò)系統(tǒng)全局收斂。

熵最初是物理學(xué)中對(duì)系統(tǒng)混亂程度的一種度量，后有科學(xué)家從數(shù)學(xué)角度提出信息熵的概念。1957 年統(tǒng)計(jì)物理學(xué)家Jaynes提出極大熵原理后，該原理被廣泛應(yīng)用于許多學(xué)科領(lǐng)域中。該原理認(rèn)為，在掌握部分信息的情況下對(duì)分布形狀做出判斷，應(yīng)該選擇符合約束條件且熵值取得最大的概率分布，任何其他的選擇都意味著人為添加了其他的約束條件，而這些約束或假設(shè)是無法根據(jù)現(xiàn)有的知識(shí)給出的。此外，Jaynes 還指出，在物理學(xué)中一些重要的概率分布均是在一定約束條件下滿足極大熵原理的概率分布[23-24]。更為重要的是，極大熵原理滿足第一原理和一致性要求，即極大熵原理利用最少的信息，獲得最超然（Maximally Noncommittal）的解，并且求得的解與求解步驟無關(guān)[25-26]。

本文結(jié)合極大熵原理、模擬退火思想[27]，應(yīng)用彈性網(wǎng)絡(luò)的求解模式，提出一種新的聚類算法。該算法重新構(gòu)造與數(shù)據(jù)點(diǎn)、聚類中心關(guān)聯(lián)的代價(jià)函數(shù)，并考慮了各特征屬性對(duì)聚類不同程度的重要性等因素，提出一種具有加權(quán)特性的彈性網(wǎng)絡(luò)聚類算法（Weighting of Elastic Net for Clustering，WENC）。

2 彈性網(wǎng)絡(luò)

彈性網(wǎng)絡(luò)算法的基本原理是在多元空間中描述各城市點(diǎn)，在城市點(diǎn)構(gòu)成的空間內(nèi)生成一個(gè)含有彈性節(jié)點(diǎn)（Elastic Points）的以數(shù)據(jù)集重心為中心的封閉圓環(huán)，該圓環(huán)稱為彈性帶（Rubber Band）。隨著網(wǎng)絡(luò)不斷地迭代，彈性帶發(fā)生形變，彈性節(jié)點(diǎn)的位置不斷變化，不斷向城市點(diǎn)靠近，直到所有的城市點(diǎn)被彈性節(jié)點(diǎn)覆蓋，網(wǎng)絡(luò)達(dá)到穩(wěn)定狀態(tài)，即認(rèn)為獲得該TSP問題的近似解。在迭代過程中，彈性網(wǎng)絡(luò)通過兩種力來牽引彈性節(jié)點(diǎn)的移動(dòng)：一種力是與彈性節(jié)點(diǎn)i 相鄰的城市點(diǎn)對(duì)彈性節(jié)點(diǎn)i的吸引力，使得彈性節(jié)點(diǎn)i 逐漸向城市點(diǎn)靠近；一種力是與彈性節(jié)點(diǎn)i 相鄰的彈性節(jié)點(diǎn)對(duì)彈性節(jié)點(diǎn)i 的張力，迫使彈性節(jié)點(diǎn)之間的距離最短。

假設(shè)給定數(shù)據(jù)集X={x1,x2,…,xn} 含有n 個(gè)城市點(diǎn)，在該空間內(nèi)初始化含有m 個(gè)彈性節(jié)點(diǎn)的彈性帶Y={y1,y2,…,ym}，一般n ＜m 。隨著網(wǎng)絡(luò)的迭代，彈性網(wǎng)絡(luò)追蹤能量函數(shù)式（1）的極小值：

其中，K 逐漸減小，與退火算法（Deterministic Annealing Method）中的溫度對(duì)應(yīng)。參數(shù)α、β 分別決定城市對(duì)彈性節(jié)點(diǎn)的力和彈性點(diǎn)間的力的影響程度。彈性節(jié)點(diǎn)每次迭代需要的位移量為：

其中，ωij代表城市點(diǎn)i 在路徑上對(duì)彈性節(jié)點(diǎn)j 的影響程度，其描述如式（4）所示。

當(dāng)K →0 時(shí)，能量函數(shù)獲得局部最小，此時(shí)每個(gè)城市點(diǎn)至少匹配到一個(gè)彈性節(jié)點(diǎn)。當(dāng)城市點(diǎn)有且只匹配到一個(gè)彈性節(jié)點(diǎn)時(shí)，認(rèn)為網(wǎng)絡(luò)獲得最優(yōu)解決方案。

3 具有加權(quán)特性的彈性網(wǎng)絡(luò)聚類算法

傳統(tǒng)的聚類分析算法通常將數(shù)據(jù)所有的特征屬性按照相同的重要程度進(jìn)行聚類，然而在多維數(shù)據(jù)聚類中，所有的特征屬性對(duì)聚類的重要程度并不完全相同，有些特征屬性甚至可能是噪聲特征，進(jìn)而影響聚類的結(jié)果[7，28]。本文根據(jù)彈性網(wǎng)絡(luò)的特點(diǎn)，設(shè)計(jì)了一種加權(quán)方式，使其能夠在多維數(shù)據(jù)集中更好地進(jìn)行聚類。彈性網(wǎng)絡(luò)算法雖然非常適合求解具有目標(biāo)函數(shù)的問題，但并不能直接用于解決聚類問題，本文將詳細(xì)介紹具有加權(quán)特性的彈性網(wǎng)絡(luò)聚類算法。首先，根據(jù)聚類的目標(biāo)確定初始權(quán)值的方法。然后，引入加權(quán)思想，針對(duì)聚類問題構(gòu)建基于數(shù)據(jù)點(diǎn)與聚類中心間距離平方的能量函數(shù)，并運(yùn)用極大熵原理給出數(shù)據(jù)點(diǎn)的概率分布。然后，針對(duì)算法的彈性帶初始化、能量函數(shù)、權(quán)值等問題進(jìn)行詳細(xì)分析。最后，給出算法的執(zhí)行過程。

3.1 算法原理及分析

假設(shè)在多元空間中，給定一含有n 個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集X={X1,X2,…,Xn}，每個(gè)數(shù)據(jù)點(diǎn)均具有m 個(gè)特征屬性Xi=(xi,1,xi,2,…,xi,m)，目標(biāo)是將該數(shù)據(jù)集分為k 簇。初始化一條含有k 個(gè)彈性節(jié)點(diǎn)的彈性帶Y={Y1,Y2,…,Ym}，每個(gè)彈性節(jié)點(diǎn)均具有m 個(gè)特征屬性Yj=(yj,1,yj,2,…,yj,m)，每個(gè)特征屬性上所加的權(quán)值為U=(u1,u2,…,um)?？紤]到各特征屬性在聚類過程中的影響各不相同，因此需要確定各特征屬性的權(quán)值。本文首先介紹一種確定特征屬性權(quán)值的方法。

在彈性網(wǎng)絡(luò)聚類算法（Elastic Net for Clustering，ENC）中，所有特征屬性對(duì)聚類過程的影響程度相同，此時(shí)相當(dāng)于各特征屬性的權(quán)值均為1，即U=(u1,u2,…,um)=(1,1,…,1)，相當(dāng)于網(wǎng)絡(luò)不加權(quán)。如果某一維對(duì)聚類的影響度不那么重要，其存在甚至影響聚類結(jié)果變差，但若直接刪掉該特征屬性，會(huì)破壞數(shù)據(jù)集原本的結(jié)構(gòu)。因此需要對(duì)該特征屬性的權(quán)值進(jìn)行處理，一方面減少其對(duì)聚類結(jié)果的影響，另一方面保留了原始數(shù)據(jù)集的結(jié)構(gòu)特性。

聚類的目的是根據(jù)數(shù)據(jù)的內(nèi)部結(jié)構(gòu)，將數(shù)據(jù)劃分成一些集群，每個(gè)集群中的對(duì)象盡可能相同，不同集群中的對(duì)象盡可能不同，由此可以判定，當(dāng)某特征屬性較為離散時(shí)，該特征屬性不利于聚類。本文首先利用式（5）對(duì)所有特征屬性的離散程度進(jìn)行判斷，其中xˉl為第l 個(gè)特征屬性的所有數(shù)據(jù)點(diǎn)的均值。然后根據(jù)式（6）計(jì)算閾值：當(dāng)某特征屬性的離散程度超過該閾值時(shí)，根據(jù)式（7）計(jì)算該特征屬性的權(quán)值，其中δ 為權(quán)值系數(shù)，根據(jù)數(shù)據(jù)集的特征選取；當(dāng)某特征屬性的離散程度未超過該閾值時(shí)，該特征屬性的權(quán)值為1。

聚類的目標(biāo)是使類內(nèi)對(duì)象盡可能相似而類間對(duì)象盡可能不同，即數(shù)據(jù)點(diǎn)到各簇中心的距離和最小，根據(jù)該目標(biāo)可以發(fā)現(xiàn)衡量聚類質(zhì)量的一個(gè)重要標(biāo)準(zhǔn)SED（Sum of Euclidean Distance）值與此概念一致，如式（8）所示：

其中，Xi為第i 個(gè)數(shù)據(jù)點(diǎn)，Yj為第j 個(gè)聚類中心點(diǎn)，Cj表示聚類產(chǎn)生的以Yj為聚類中心的集群。

本文針對(duì)聚類問題，直接將各簇之間的距離平方和設(shè)置為能量函數(shù)，如式（9）所示。在該能量函數(shù)的作用下，所有數(shù)據(jù)點(diǎn)對(duì)每個(gè)神經(jīng)元都具有吸引力，神經(jīng)元在該力的作用下進(jìn)行移動(dòng)。隨著網(wǎng)絡(luò)的運(yùn)行，能量函數(shù)值不斷下降，神經(jīng)元沿著使SED值最小的方向移動(dòng)，當(dāng)能量函數(shù)達(dá)到全局極小，SED 值也達(dá)到最小值，從而求得該聚類問題的最優(yōu)解或近似最優(yōu)解。此外，傳統(tǒng)的聚類分析算法通常將數(shù)據(jù)所有的特征屬性按照相同的重要程度進(jìn)行聚類，然而在多維數(shù)據(jù)聚類中，所有的特征屬性對(duì)聚類的重要程度并不完全相同，有些特征屬性甚至可能是噪聲特征，進(jìn)而影響聚類的結(jié)果。因此，本文引入加權(quán)思想，將能量函數(shù)定義為式（9），總的能量函數(shù)定義為式（10）。

其中，Pi,j為數(shù)據(jù)點(diǎn)xi屬于某一簇Cj的概率分布，在沒有先驗(yàn)知識(shí)的情況下，不能隨便確定其具體模式。本文采用極大熵原理來確定Pi,j的概率分布。

將聚類模型視作物理系統(tǒng)模型，對(duì)給定的彈性節(jié)點(diǎn)y1,y2,…,yk定義熵函數(shù)H ，如式（11）所示。

在本文的能量函數(shù)中，除考慮數(shù)據(jù)點(diǎn)與彈性節(jié)點(diǎn)之間的作用外，還考慮了彈性節(jié)點(diǎn)之間的交互作用，如式（12）所示。

其中，常數(shù)λ 為彈性系數(shù)。

綜上，與能量函數(shù)相應(yīng)的亥姆霍茲自由能（Helmholtz Free Energy）如式（13）所示[29-30]，其中Z 為總的配分方程。

本文將數(shù)據(jù)集中的數(shù)據(jù)點(diǎn)描述為多變量空間中的數(shù)據(jù)點(diǎn)，在沒有先驗(yàn)知識(shí)，也不對(duì)數(shù)據(jù)集做任何假設(shè)約束的情況下，利用極大熵原理來確定彈性節(jié)點(diǎn)與數(shù)據(jù)點(diǎn)之間的概率分布。在該算法中彈性網(wǎng)絡(luò)節(jié)點(diǎn)的位置代表聚類中心，而每個(gè)數(shù)據(jù)點(diǎn)隸屬于該簇的概率符合高斯概率分布，由式（14）給出[26，29]。

其中，Zi為配分方程：

其中，參數(shù)β 與溫度K 成反比，即β 越小溫度越高，當(dāng)β=0 時(shí)，每個(gè)數(shù)據(jù)點(diǎn)屬于每簇的概率相同；隨著β 不斷增加，當(dāng)β →∞時(shí)，每個(gè)數(shù)據(jù)點(diǎn)以1 的概率僅屬于一個(gè)簇。由于每個(gè)數(shù)據(jù)點(diǎn)屬于不同簇的概率是不同的，因而總的配分方程為：

在網(wǎng)絡(luò)不斷迭代的過程中，彈性節(jié)點(diǎn)在數(shù)據(jù)點(diǎn)的吸引力和相鄰彈性節(jié)點(diǎn)間的張力的作用下不斷移動(dòng)位置，每次迭代需要移動(dòng)的量由式（17）計(jì)算得到：

其中，常數(shù)Δτ 為每次迭代的步長(zhǎng)，選擇合適的Δτ 能夠使網(wǎng)絡(luò)進(jìn)行充分的運(yùn)行。

3.1.1 彈性帶初始化算法分析

由于k-means、k-medoids 算法隨機(jī)確定初始的聚類中心點(diǎn)，每次運(yùn)算的結(jié)果受到聚類中心點(diǎn)初始位置的影響，使得算法針對(duì)同一問題每次運(yùn)算的結(jié)果不唯一。而本文提出的WENC 算法通過設(shè)置彈性帶的方式，對(duì)神經(jīng)元位置進(jìn)行初始化，使算法針對(duì)同一問題求解結(jié)果唯一。WENC算法初始化彈性帶的方法描述如下：

其中，xi,l表示第i 個(gè)數(shù)據(jù)點(diǎn)的第l 個(gè)特征屬性。

（2）利用式（19）計(jì)算初始彈性帶的半徑R：

（3）初始化彈性帶為以重心Xˉ為圓心，以R 為半徑的封閉圓環(huán)，在本算法中選擇前兩維初始彈性帶，k 個(gè)彈性節(jié)點(diǎn)均勻分布在彈性帶上。

該方法綜合考慮了所有數(shù)據(jù)樣本的位置，根據(jù)所有數(shù)據(jù)點(diǎn)的坐標(biāo)計(jì)算該數(shù)據(jù)集的重心Xˉ，繼而確定神經(jīng)元的初始位置。該方法可以根據(jù)不同的數(shù)據(jù)分布情況動(dòng)態(tài)調(diào)節(jié)彈性網(wǎng)絡(luò)神經(jīng)元的初始位置，以適應(yīng)不同問題的需要。在使用該方法確定彈性網(wǎng)絡(luò)初始神經(jīng)元位置后，針對(duì)同一聚類問題，WENC網(wǎng)絡(luò)運(yùn)行結(jié)果唯一。

為驗(yàn)證WENC算法與k-means、k-medoids算法聚類結(jié)果的穩(wěn)定性，本文做了大量實(shí)驗(yàn)，此處選取含有800、1 000、3 000、5 000 個(gè)數(shù)據(jù)點(diǎn)的4 組數(shù)據(jù)集，分別利用k-means、k-medoids、WENC 算法多次運(yùn)行，結(jié)果對(duì)比如圖1所示。

從圖1 中可以發(fā)現(xiàn)，針對(duì)同一問題，k -means、k -medoids算法多次運(yùn)行結(jié)果不唯一，而WENC 算法多次運(yùn)行的結(jié)果唯一。在20 次的運(yùn)行中，WENC 算法的結(jié)果均優(yōu)于k-means、k-medoids算法。在這4組實(shí)驗(yàn)中，WENC 算法求解的SED 值分別比k -means 算法求解的SED 平均值減少5.22%、5.26%、3.83%、5.00%，比k -medoids 算法求解的SED 平均值減少6.55%、5.15%、8.25%、6.15%。因此在本文后續(xù)實(shí)驗(yàn)中，利用k-means、k-medoids算法對(duì)每組數(shù)據(jù)集分別進(jìn)行20次測(cè)試，取結(jié)果的平均值進(jìn)行比較。

3.1.2 能量函數(shù)分析

為評(píng)估WENC 算法自由能函數(shù)的作用，本文選取一組含有1 000個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集來展示在聚類過程中自由能函數(shù)及其對(duì)應(yīng)的SED 值隨迭代的演化過程，如圖2 所示。圖2（a）為WENC 算法的自由能函數(shù)隨迭代的變化過程，圖2（b）為在聚類過程中，每次迭代自由能函數(shù)變化時(shí)對(duì)應(yīng)的SED值。由圖2可知，隨著迭代次數(shù)的增加，自由能函數(shù)值逐漸降低，對(duì)應(yīng)的SED值逐漸減少。在此過程中，網(wǎng)絡(luò)會(huì)陷入局部極小值，因此自由能函數(shù)值與SED 值均出現(xiàn)一個(gè)較為穩(wěn)定的狀態(tài)。隨著迭代繼續(xù)進(jìn)行，在能量函數(shù)的作用下，網(wǎng)絡(luò)具有針對(duì)該聚類問題的自適應(yīng)、自學(xué)習(xí)能力，從而能夠主動(dòng)跳出局部極小，尋找到更接近全局最小的解。

圖1 k-means、k-medoids、WENC算法多次運(yùn)行結(jié)果對(duì)比圖

圖2 WENC算法自由能函數(shù)及對(duì)應(yīng)SED值隨迭代的演化圖

本文所提出的能量函數(shù)，除考慮了數(shù)據(jù)點(diǎn)與彈性節(jié)點(diǎn)之間的作用外，還考慮了彈性節(jié)點(diǎn)之間的交互作用：在能量函數(shù)中增加了式（12），即增加了相鄰神經(jīng)元之間的吸引力。這有助于保持網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，保證網(wǎng)絡(luò)運(yùn)行和求解的穩(wěn)定性。通常情況下，由于彈性網(wǎng)絡(luò)神經(jīng)元節(jié)點(diǎn)數(shù)目等于聚類數(shù)目，大量數(shù)據(jù)點(diǎn)與少量彈性節(jié)點(diǎn)交互，因此能量函數(shù)中有關(guān)相鄰神經(jīng)元相互作用的計(jì)算量增量有限。為驗(yàn)證考慮彈性節(jié)點(diǎn)間作用力對(duì)網(wǎng)絡(luò)運(yùn)算的影響，本文選取一組含有500 個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集，分別使用未考慮彈性節(jié)點(diǎn)間影響力的NENC（Non-node Elastic Net of Clustering）算法和本文提出的考慮彈性節(jié)點(diǎn)間影響力的WENC算法迭代100次，SED值隨迭代的變化以及運(yùn)行所用的時(shí)間對(duì)比如圖3所示。從圖3可以發(fā)現(xiàn)：在聚類結(jié)果上，WENC 算法和NENC 算法每次迭代在SED值上的差別并不明顯；在運(yùn)行時(shí)間上，兩種算法均迭代100次，WENC算法比NENC算法運(yùn)行時(shí)間僅多了0.02 s?？梢姀椥怨?jié)點(diǎn)之間的交互作用對(duì)算法運(yùn)算的成本影響較小，因此在計(jì)算成本方面神經(jīng)元之間的交互作用可以視為擾動(dòng)。

圖3 WENC、NENC算法的SED值變化及運(yùn)行時(shí)間對(duì)比圖

相鄰神經(jīng)元之間的相互作用，在網(wǎng)絡(luò)的運(yùn)行求解過程中起到重要作用，它有助于保持網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，并保證網(wǎng)絡(luò)求解的穩(wěn)定性和唯一性。圖4 為針對(duì)同一四維含有1 000 個(gè)數(shù)據(jù)點(diǎn)的聚類問題，多次運(yùn)行WENC算法和NENC 算法的結(jié)果對(duì)比。由圖4 可見，未添加彈性節(jié)點(diǎn)之間相互作用的NENC 算法每次運(yùn)行的結(jié)果不穩(wěn)定，而WENC 算法則在多次計(jì)算中取得穩(wěn)定的唯一解。因此，考慮相鄰神經(jīng)元間的相互作用是非常必要的。

圖4 WENC算法與NENC算法多次運(yùn)行的結(jié)果對(duì)比圖

通過上述理論分析和實(shí)驗(yàn)驗(yàn)證，本文提出的WENC算法在能量函數(shù)公式（13）的作用下，網(wǎng)絡(luò)中的每一個(gè)彈性節(jié)點(diǎn)yj在數(shù)據(jù)點(diǎn)的吸引力和相鄰彈性節(jié)點(diǎn)間的張力作用下不斷移動(dòng)位置。如圖5 所示為某時(shí)刻單個(gè)彈性節(jié)點(diǎn)yj與數(shù)據(jù)點(diǎn)xi之間的力的作用圖，F(xiàn)1為相鄰彈性節(jié)點(diǎn)對(duì)彈性節(jié)點(diǎn)yj的張力之和，F(xiàn)2為數(shù)據(jù)點(diǎn)xi對(duì)彈性節(jié)點(diǎn)yj的吸引力。

圖5 某時(shí)刻單個(gè)神經(jīng)元的受力圖

在神經(jīng)網(wǎng)絡(luò)中，一般通過觀察單神經(jīng)元模型來驗(yàn)證神經(jīng)網(wǎng)絡(luò)的性能及改進(jìn)方法對(duì)網(wǎng)絡(luò)的影響。但由于彈性網(wǎng)絡(luò)中彈性節(jié)點(diǎn)是在相鄰彈性節(jié)點(diǎn)和數(shù)據(jù)點(diǎn)共同作用下進(jìn)行移動(dòng)，因此通過單神經(jīng)元模型進(jìn)行觀察的方法并不適用于彈性網(wǎng)絡(luò)。本文選取只含有3 個(gè)神經(jīng)元的簡(jiǎn)單網(wǎng)絡(luò)模型進(jìn)行實(shí)驗(yàn)，通過選取單個(gè)典型神經(jīng)元作為觀察點(diǎn)來驗(yàn)證加權(quán)后對(duì)速度的影響。單個(gè)彈性節(jié)點(diǎn)每次迭代移動(dòng)的量隨著迭代次數(shù)的增加逐漸趨于0，當(dāng)彈性節(jié)點(diǎn)的移動(dòng)量連續(xù)10 次小于0.001 時(shí)，網(wǎng)絡(luò)停止運(yùn)行，此時(shí)彈性節(jié)點(diǎn)的位置即為聚類中心點(diǎn)的位置。

基于以上理論分析，本文對(duì)網(wǎng)絡(luò)迭代速度進(jìn)行了實(shí)驗(yàn)，得到如圖6所示結(jié)果。圖6（a）、（b）分別為彈性節(jié)點(diǎn)橫縱坐標(biāo)每次迭代的位移量的變化過程，其中WENC為本文提出的加權(quán)彈性網(wǎng)絡(luò)聚類算法，ENC為未進(jìn)行加權(quán)的彈性網(wǎng)絡(luò)聚類算法。從圖6可以看出，本文提出的WENC 算法迭代了26 次即得到聚類結(jié)果，運(yùn)行時(shí)間為0.528 s；ENC 算法則迭代了28 次，運(yùn)行時(shí)間為0.544 s。此外，本文在不同數(shù)據(jù)集下還進(jìn)行了網(wǎng)絡(luò)聚類所需迭代次數(shù)的對(duì)比，結(jié)果如圖7所示。從圖7可以發(fā)現(xiàn)，在不同大小的數(shù)據(jù)集下，WENC 算法的迭代次數(shù)均少于ENC算法。因此，改進(jìn)后的加權(quán)彈性網(wǎng)絡(luò)WENC 能夠更快地找到聚類中心，比不加權(quán)的ENC算法的性能更高。

圖6 彈性節(jié)點(diǎn)橫縱坐標(biāo)位移量的變化過程

圖7 不同大小數(shù)據(jù)集的迭代次數(shù)對(duì)比圖

3.1.3 權(quán)值設(shè)置分析

為驗(yàn)證加權(quán)對(duì)網(wǎng)絡(luò)的影響和意義，本文選取一組隨機(jī)數(shù)據(jù)集將WENC算法與其他常用聚類算法進(jìn)行實(shí)驗(yàn)比對(duì)。該數(shù)據(jù)集共含有3 個(gè)特征屬性，180 個(gè)樣本點(diǎn)。在本實(shí)驗(yàn)中，利用SED 值對(duì)聚類的結(jié)果進(jìn)行評(píng)價(jià)，SED值越小，代表聚類的質(zhì)量越高。

首先根據(jù)式（5）分別計(jì)算各特征屬性的離散程度，結(jié)果如表1所示。然后利用式（6）計(jì)算得閾值V=3.40，由此判斷僅第3個(gè)特征屬性需要計(jì)算新的權(quán)值，其余特征屬性權(quán)值仍為1。

表1 三維隨機(jī)數(shù)據(jù)集所有特征屬性的離散程度

根據(jù)該數(shù)據(jù)集的結(jié)構(gòu)，設(shè)置參數(shù)δ 為0.96，計(jì)算得第3 個(gè)特征屬性的權(quán)值為0.5，本文提出的WENC算法與不加權(quán)彈性網(wǎng)絡(luò)ENC、k -means、k -medoids、MeanShift 聚類算法的結(jié)果對(duì)比如表2 所示。其中，k -means、k -medoids 算法對(duì)初始中心點(diǎn)的位置非常敏感。每種算法分別進(jìn)行20 次測(cè)試，取所有SED 值的平均值作為最終結(jié)果進(jìn)行比較。

表2 三維180個(gè)樣本點(diǎn)的數(shù)據(jù)集各聚類算法結(jié)果對(duì)比

由表2的數(shù)據(jù)對(duì)比可知，對(duì)數(shù)據(jù)集進(jìn)行加權(quán)之后網(wǎng)絡(luò)聚類效果更好，與k-means、k-medoids、MeanShift以及不加權(quán)的ENC 算法相比，SED 值分別提高8.5%、6.6%、11.4%、4.1%。 k -means、k -medoids、MeanShift、ENC以及WENC各算法結(jié)果的平面圖分別如圖8～圖12所示，其中圖（a）、（b）、（c）分別顯示了數(shù)據(jù)集中各屬性維度之間的關(guān)系。

圖8 k-means算法的聚類結(jié)果

圖9 k-medoids算法的聚類結(jié)果

圖10 MeanShift算法的聚類結(jié)果

圖11 ENC算法的聚類結(jié)果

圖12 WENC算法的聚類結(jié)果

對(duì)比圖8～圖12 可以觀察出，該數(shù)據(jù)集中有一個(gè)特征屬性較為離散，不利于聚類過程的進(jìn)行。k -means、k -medoids、MeanShift、ENC 算法在聚類過程中均受到該特征屬性的干擾，在圖8～11（a）中，各簇的劃分情況并不理想。而WENC算法利用權(quán)值降低該特征屬性對(duì)聚類過程的影響，圖12（a）中各簇的劃分較為清晰，WENC算法的聚類結(jié)果更優(yōu)。

由此可知，在進(jìn)行聚類時(shí)，不同的特征屬性對(duì)聚類過程的影響不同，將不利于聚類的特征屬性的影響度降低后，可以提高聚類結(jié)果的質(zhì)量。

3.2 算法描述

本文在彈性網(wǎng)絡(luò)的基礎(chǔ)上，引入機(jī)械函數(shù)和加權(quán)思想，構(gòu)造新的能量函數(shù)，并利用極大熵原理確定數(shù)據(jù)點(diǎn)的概率分布，使算法更具有普適性。通過權(quán)值確定的策略，減小不利因素對(duì)聚類的影響，再計(jì)算自由能函數(shù)，當(dāng)彈性節(jié)點(diǎn)每次迭代的位移量連續(xù)10次小于0.001時(shí)，網(wǎng)絡(luò)停止運(yùn)行并獲得最后的聚類方案。該方法不僅提高了聚類質(zhì)量，網(wǎng)絡(luò)整體也比其他算法更加穩(wěn)定。WENC算法的具體步驟如下：

（1）給定一個(gè)含有n 個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集X={X1,X2,…,Xn} ，每個(gè)數(shù)據(jù)點(diǎn)均具有m 個(gè)特征屬性Xi=(xi,1,xi,2,…,xi,m)。根據(jù)式（5）、式（6）分別計(jì)算每個(gè)特征屬性的離散程度Gl和閾值V 。

（2）判斷Gl是否大于閾值V ：若是，則根據(jù)式（7）計(jì)算該特征屬性的權(quán)值ul；若否，則初始化該特征屬性的權(quán)值ul=1。

（3）在數(shù)據(jù)空間內(nèi)初始化一個(gè)含有k 個(gè)彈性節(jié)點(diǎn)的彈性帶Y={Y1,Y2,…,Ym}，每個(gè)彈性節(jié)點(diǎn)均具有m 個(gè)特征屬性Yj=(yj,1,yj,2,…,yj,m)。彈性帶是以數(shù)據(jù)集的重心Xˉ為中心，R 為半徑的封閉圓環(huán)，Xˉ、R 分別根據(jù)式（18）、式（19）計(jì)算獲得，彈性節(jié)點(diǎn)均勻分布在彈性帶上。

（4）根據(jù)式（13）計(jì)算數(shù)據(jù)點(diǎn)及相鄰節(jié)點(diǎn)間的總能量，并由推導(dǎo)出的式（17）計(jì)算每次迭代彈性節(jié)點(diǎn)在每個(gè)特征維度上移動(dòng)的距離Δyj,l。

（5）重復(fù)步驟（4），當(dāng)彈性節(jié)點(diǎn)的移動(dòng)量連續(xù)10 次小于0.001時(shí)，網(wǎng)絡(luò)停止運(yùn)行，此時(shí)彈性節(jié)點(diǎn)的位置即為各集群的中心點(diǎn)，即獲得各簇的聚類中心點(diǎn)。

（6）計(jì)算數(shù)據(jù)點(diǎn)到各彈性節(jié)點(diǎn)的距離Di,j，并將數(shù)據(jù)點(diǎn)分配至距離該點(diǎn)最近的彈性節(jié)點(diǎn)，獲得最終的聚類方案，完成聚類。Di,j如式（20）所示：

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

彈性網(wǎng)絡(luò)具有非常好的幾何特性，能夠有效地解決固定目標(biāo)函數(shù)求解極小值的問題，因此基于彈性網(wǎng)絡(luò)的聚類算法雖然能夠很好地對(duì)數(shù)據(jù)集進(jìn)行聚類，但只適用于數(shù)值型數(shù)據(jù)集，非數(shù)值型數(shù)據(jù)集必須轉(zhuǎn)換為數(shù)值型數(shù)據(jù)集后才能夠進(jìn)行聚類運(yùn)算。

為驗(yàn)證WENC 算法是否能夠有效提高聚類質(zhì)量，本文采用了大量的隨機(jī)數(shù)據(jù)集和真實(shí)數(shù)據(jù)集對(duì)其進(jìn)行實(shí)驗(yàn)仿真。由于隨機(jī)數(shù)據(jù)集沒有標(biāo)簽，隨機(jī)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果通過聚類標(biāo)準(zhǔn)SED 值來評(píng)價(jià)。真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果通過SED 值和Accuracy 來評(píng)價(jià)。Accuracy 的計(jì)算方法如式（21）所示。

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

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

隨機(jī)數(shù)據(jù)集生成的方法類似文獻(xiàn)[31]，由Matlab程序生成。為使實(shí)驗(yàn)更具普適性，本文合成了含有不同特征屬性、不同數(shù)量級(jí)的數(shù)據(jù)集。WENC算法中參數(shù)設(shè)置為β=1,Δτ=0.001,λ=0.5。每次實(shí)驗(yàn)的彈性帶以實(shí)驗(yàn)數(shù)據(jù)的重心Xˉ為中心，半徑R 通過式（19）確定。為顯示W(wǎng)ENC算法的優(yōu)勢(shì)，每組實(shí)驗(yàn)均與k-means、k-medoids、MeanShift以及未加權(quán)的彈性網(wǎng)絡(luò)聚類算法ENC的結(jié)果進(jìn)行對(duì)比。由于k-means、k-medoids 算法對(duì)初始中心點(diǎn)的位置非常敏感，分別對(duì)每組數(shù)據(jù)集進(jìn)行20次測(cè)試，取結(jié)果的平均值進(jìn)行比較。

為驗(yàn)證網(wǎng)絡(luò)增加權(quán)值的有效性，本文首先選取了具有60、300、1 000個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集，表3列出了各組數(shù)據(jù)集詳細(xì)的聚類結(jié)果。

由表3 可以得到五種算法在不同維度下平均SED值的比較結(jié)果：對(duì)含有60、300、1 000個(gè)數(shù)據(jù)點(diǎn)的隨機(jī)數(shù)據(jù)集，WENC算法求解的SED值比k-means算法分別減少7.51%、6.12%、1.82%，比k -medoids 算法分別減少8.93%、10.42%、7.57%，比MeanShift 算法分別減少8.67%、24.29%、19.53%，比ENC 算法分別減少2.65%、3.33%、7.99%。此外WENC網(wǎng)絡(luò)運(yùn)行多次結(jié)果不變，與k -means、k -medoids 算法相比，結(jié)果非常穩(wěn)定，因此本文提出的WENC算法在解決聚類問題時(shí)不需要多次運(yùn)行。綜上，對(duì)不同的多維隨機(jī)數(shù)據(jù)集，WENC 算法均可獲得比k-means、k-medoids、MeanShift、ENC算法更好的聚類結(jié)果，驗(yàn)證了加權(quán)的有效性。此外加權(quán)提高了網(wǎng)絡(luò)的求解速度，速度對(duì)比如圖6所示。

為驗(yàn)證WENC 算法處理大規(guī)模數(shù)據(jù)集的能力，本文還對(duì)具有3 000、6 000、10 000個(gè)數(shù)據(jù)點(diǎn)，分為3簇、10簇的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。具體實(shí)驗(yàn)結(jié)果如表4所示。

由表4 可以得到五種算法在不同維度下的平均SED 值比較結(jié)果：對(duì)含有3 000、6 000、10 000 個(gè)數(shù)據(jù)點(diǎn)的隨機(jī)數(shù)據(jù)集，WENC算法求解的SED值比k-means算法分別減少1.43%、0.87%、2.03%，比k-medoids 算法分別減少6.29%、5.15%、7.12%，比MeanShift 算法分別減少25.46%、20.98%、20.82%，比ENC 算法分別減少8.91%、3.55%、0.41%。此外WENC 網(wǎng)絡(luò)運(yùn)行多次結(jié)果不變，與k-means、k-medoids算法相比，結(jié)果非常穩(wěn)定，分析對(duì)比如圖1所示。綜上，對(duì)不同的多維隨機(jī)數(shù)據(jù)集，WENC 算法在處理大規(guī)模數(shù)據(jù)集方面均可獲得比k -means、k-medoids、MeanShift、ENC算法更好的聚類結(jié)果。

表3 隨機(jī)數(shù)據(jù)集聚類結(jié)果對(duì)比

表4 大規(guī)模隨機(jī)數(shù)據(jù)集聚類結(jié)果對(duì)比

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

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

真實(shí)數(shù)據(jù)集是從標(biāo)準(zhǔn)庫UCI內(nèi)獲取的，與k-means、k-medoids、MeanShift算法進(jìn)行了對(duì)比實(shí)驗(yàn)。本文選取Zoo、Seeds、Iris、Wine、Handwritten等數(shù)據(jù)集進(jìn)行運(yùn)算測(cè)試。其中Zoo 包含101 個(gè)數(shù)據(jù)樣本，16 個(gè)特征屬性，目標(biāo)劃分為7 簇；Seeds 包含210 個(gè)數(shù)據(jù)樣本，7 個(gè)特征屬性，目標(biāo)劃分為3 簇；Iris 包含150 個(gè)數(shù)據(jù)樣本，4 個(gè)特征屬性，目標(biāo)劃分為3簇；Wine包含178個(gè)數(shù)據(jù)樣本，13個(gè)特征屬性，目標(biāo)劃分為3 簇；Handwritten Digits（為方便記錄，表中記為Hand）包含10 992 個(gè)數(shù)據(jù)樣本，16 個(gè)特征屬性，目標(biāo)劃分為10 簇。該實(shí)驗(yàn)使用與隨機(jī)數(shù)據(jù)集實(shí)驗(yàn)相同的方法對(duì)聚類結(jié)果進(jìn)行評(píng)估，并增加Accuracy聚類標(biāo)準(zhǔn)來多方面評(píng)估聚類結(jié)果。實(shí)驗(yàn)的詳細(xì)結(jié)果如表5所示。

通過對(duì)比表5的數(shù)據(jù)結(jié)果可知，WENC算法在真實(shí)數(shù)據(jù)集中的聚類結(jié)果，與k-means 算法對(duì)比，SED 值分別降低20.68%、22.29%、7.54%、13.06%、9.65%，Accuracy分別提高19.70%、31.88%、18.33%、30.43%、8.82%；與k -medoids 算法結(jié)果對(duì)比，SED 值分別降低16.88%、21.25%、5.95%、13.06%、5.64%，Accuracy 分別提高16.18%、28.17%、9.23%、18.42%、17.46%；與MeanShift算法結(jié)果對(duì)比，SED值分別降低4.13%、2.21%、17.17%、0.69%、10.22%，Accuracy 分別提高9.72%、2.25%、10.94%、2.27%、25.42%。實(shí)驗(yàn)結(jié)果表明，WENC算法不僅提高了聚類質(zhì)量，還優(yōu)化了Accuracy，聚類結(jié)果得到有效改善。

由此分析，本文提出的WENC 算法無論對(duì)低維還是高維數(shù)據(jù)集的聚類能力均優(yōu)于k-means、k-medoids、MeanShift 等傳統(tǒng)算法。此外，WENC 算法在排除噪聲因素干擾、穩(wěn)定聚類的同時(shí)，保證了整個(gè)網(wǎng)絡(luò)收斂。

5 結(jié)束語

本文針對(duì)聚類算法中存在的聚類結(jié)果易受噪聲干擾、多維空間聚類質(zhì)量不佳等問題，提出了一種具有加權(quán)特性的彈性網(wǎng)絡(luò)聚類算法（WENC）。與傳統(tǒng)聚類算法相比，本文選擇適合求解固定目標(biāo)函數(shù)極小問題的彈性網(wǎng)絡(luò)模型。由于原始彈性網(wǎng)絡(luò)不能直接用于解決聚類問題，本文在彈性網(wǎng)絡(luò)基礎(chǔ)上考慮到不同特征屬性對(duì)聚類的重要程度不同，通過對(duì)數(shù)據(jù)集中某些影響聚類結(jié)果的特征屬性進(jìn)行加權(quán)，達(dá)到削弱這些特征屬性在聚類過程中對(duì)網(wǎng)絡(luò)影響的目的?；谝陨显?，重新構(gòu)建模型的能量函數(shù)，并結(jié)合極大熵原理確定數(shù)據(jù)集的概率分布。設(shè)置新的彈性網(wǎng)絡(luò)目標(biāo)函數(shù)，以達(dá)到聚類的目的。該算法中彈性網(wǎng)絡(luò)初始彈性節(jié)點(diǎn)的數(shù)量與目標(biāo)劃分簇?cái)?shù)相等，在網(wǎng)絡(luò)利用模擬退火思想，不斷給系統(tǒng)“降溫”達(dá)到能量函數(shù)最小值時(shí)，彈性節(jié)點(diǎn)的位置即為聚類各簇中心點(diǎn)的位置。此外，由于更改了彈性節(jié)點(diǎn)初始化的個(gè)數(shù)，使得彈性網(wǎng)絡(luò)針對(duì)聚類問題可以求解含有近一萬個(gè)樣本點(diǎn)的多維數(shù)據(jù)集，顯著提高了求解問題的規(guī)模。最后，在不同維度、不同數(shù)量級(jí)的隨機(jī)數(shù)據(jù)集以及UCI 真實(shí)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，并分別利用聚類內(nèi)部評(píng)價(jià)標(biāo)準(zhǔn)SED 值和聚類外部評(píng)價(jià)標(biāo)準(zhǔn)Accuracy 對(duì)聚類結(jié)果進(jìn)行評(píng)估，結(jié)果表明，WENC 算法能夠?qū)Ω呔S數(shù)據(jù)集穩(wěn)定地提供更好的聚類方案。