引入特征選擇初始化策略的彈性網(wǎng)絡(luò)聚類(lèi)算法

衣俊艷,賀樹(shù)輝

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

1 引 言

隨著信息科技飛速發(fā)展以及“大數(shù)據(jù)”時(shí)代的到來(lái),聚類(lèi)分析作為數(shù)據(jù)挖掘的核心方法之一逐而備受研究者們的“青睞”.聚類(lèi)是將對(duì)象進(jìn)行分組的一項(xiàng)任務(wù),使相似的對(duì)象歸為一類(lèi),不相似的對(duì)象歸為不同類(lèi).聚類(lèi)是一個(gè)無(wú)監(jiān)督的分類(lèi),它沒(méi)有任何先驗(yàn)知識(shí)可用,因此在分類(lèi)時(shí)只依賴對(duì)象自身所具有的屬性來(lái)區(qū)分對(duì)象之間的相似程度[1].聚類(lèi)廣泛應(yīng)用于語(yǔ)音識(shí)別、字符識(shí)別、圖像分割、機(jī)器視覺(jué)、數(shù)據(jù)壓縮、信息檢索此外,聚類(lèi)還應(yīng)用于統(tǒng)計(jì)科學(xué).值得一提的是,聚類(lèi)分析對(duì)生物學(xué)、心理學(xué)、考古學(xué)、地質(zhì)學(xué)、地理學(xué)以及市場(chǎng)營(yíng)銷(xiāo)等研究也都有重要作用[2].

根據(jù)聚類(lèi)過(guò)程的動(dòng)態(tài)特性的不同,聚類(lèi)方法也劃分出了較多的類(lèi)別.大致可分為基于層次的聚類(lèi)方法[3],基于劃分的聚類(lèi)方法[4,5],基于密度的聚類(lèi)方法[6,7],基于網(wǎng)格的聚類(lèi)方法[8],基于模型(神經(jīng)網(wǎng)絡(luò))的聚類(lèi)方法[9].而以上各種聚類(lèi)方法中的大多數(shù)經(jīng)典的算法都存在一些不足之處.例如基于劃分的k-means算法以及k-medoids算法聚類(lèi)結(jié)果不穩(wěn)定,求解非凸數(shù)據(jù)聚類(lèi)結(jié)果差[5,10];基于密度的DBSCAN算法聚類(lèi)過(guò)程復(fù)雜繁瑣并且不能很好地解決高維問(wèn)題[11];基于網(wǎng)格的OPTICS算法[12]在求解高維大數(shù)據(jù)量問(wèn)題時(shí)聚類(lèi)質(zhì)量差;基于神經(jīng)網(wǎng)絡(luò)的自組織特征映射(SOFM)算法的網(wǎng)絡(luò)結(jié)構(gòu)靈活性差,對(duì)數(shù)據(jù)輸入要求較高,網(wǎng)絡(luò)收斂過(guò)程容易受到系統(tǒng)的初始狀態(tài)及參數(shù)的影響,導(dǎo)致運(yùn)行結(jié)果不夠穩(wěn)定[13,14].彈性網(wǎng)絡(luò)以其獨(dú)特的網(wǎng)絡(luò)結(jié)構(gòu)以及靈活的求解方式,不僅能夠處理高維大數(shù)據(jù)模式研究問(wèn)題,而且求解過(guò)程具有更高的穩(wěn)定性,網(wǎng)絡(luò)擁有更高的性能.經(jīng)過(guò)研究發(fā)現(xiàn)基于彈性網(wǎng)絡(luò)改進(jìn)的算法能夠很好地繼承這些優(yōu)點(diǎn),因此本文從彈性網(wǎng)絡(luò)入手,通過(guò)對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行改進(jìn)從而得到一種新的高性能的聚類(lèi)算法.

彈性網(wǎng)絡(luò)是在自組織映射網(wǎng)絡(luò)的基礎(chǔ)上發(fā)展而來(lái)的.原始彈性網(wǎng)絡(luò)是由Durbin和Willshaw提出的,最初被表述為一種啟發(fā)式方法并用于求解旅行商問(wèn)題[15],原始彈性網(wǎng)絡(luò)并不能用于求解聚類(lèi)問(wèn)題.而隨著對(duì)彈性網(wǎng)絡(luò)研究的深入,它被賦予了機(jī)械統(tǒng)計(jì)基礎(chǔ)[16]并用于模式研究中的不同問(wèn)題,彈性網(wǎng)絡(luò)逐漸成為多維空間聚類(lèi)中強(qiáng)有力的工具[17].近年來(lái)對(duì)彈性網(wǎng)絡(luò)的改進(jìn)也有很多,Salvini和Carvalho基于彈性網(wǎng)絡(luò)中的兩種受力方式提出了多維空間聚類(lèi)方法[18],提高了算法求解維度,降低了參數(shù)敏感性,但是算法計(jì)算復(fù)雜,需要耗費(fèi)大量時(shí)間與空間;Damper等人[19]將其應(yīng)用于圖像,提升了網(wǎng)絡(luò)的抗噪能力,但是運(yùn)算速度與精度不高;Yi等人在彈性網(wǎng)絡(luò)中引入基于時(shí)間的動(dòng)態(tài)參數(shù),使得網(wǎng)絡(luò)能夠隨時(shí)選取合適的參數(shù)進(jìn)行求解TSP問(wèn)題,加快了網(wǎng)絡(luò)收斂速度[20],但是網(wǎng)絡(luò)求解復(fù)雜度較高且抗噪能力較差.Shen等人通過(guò)在每次迭代中局部搜索最佳質(zhì)心的方法,提出了用于求解聚類(lèi)的彈性網(wǎng)絡(luò)新算法[21],提升了網(wǎng)絡(luò)性能及求解質(zhì)量,但是該算法計(jì)算復(fù)雜,參數(shù)敏感性較高.目前大多數(shù)基于彈性網(wǎng)絡(luò)的聚類(lèi)算法大都存在計(jì)算復(fù)雜度高,參數(shù)敏感性高,求解精度不夠高,求解速度慢的問(wèn)題.

因此,為了改善傳統(tǒng)聚類(lèi)算法及以上彈性網(wǎng)絡(luò)聚類(lèi)算法存在的不足,本文提出了引入特征選擇初始化策略的彈性網(wǎng)絡(luò)聚類(lèi)算法(FSENC).首先對(duì)于原始彈性網(wǎng)絡(luò)不能用于求解聚類(lèi)的問(wèn)題,本文根據(jù)聚類(lèi)中數(shù)據(jù)點(diǎn)與聚類(lèi)中心的關(guān)系重新定義了一個(gè)聚類(lèi)代價(jià)函數(shù),并嘗試將其替換彈性網(wǎng)絡(luò)能量函數(shù)中的目標(biāo)函數(shù).其次,在聚類(lèi)問(wèn)題中,聚類(lèi)中心的數(shù)量遠(yuǎn)遠(yuǎn)小于數(shù)據(jù)點(diǎn)的數(shù)量.因此本文改變了彈性網(wǎng)絡(luò)能量函數(shù)的結(jié)構(gòu),即在求解過(guò)程中忽略了各彈性節(jié)點(diǎn)之間的吸引力,僅考慮彈性節(jié)點(diǎn)與數(shù)據(jù)點(diǎn)之間的力.這樣能夠使聚類(lèi)過(guò)程中彈性節(jié)點(diǎn)能更快更好的向最佳聚類(lèi)中心移動(dòng),并且降低了參數(shù)調(diào)整方面的難度.最后,由于大多數(shù)聚類(lèi)算法中初始聚類(lèi)中心的位置是隨機(jī)設(shè)置的,不能根據(jù)數(shù)據(jù)進(jìn)行動(dòng)態(tài)改變,很大程度上影響著聚類(lèi)質(zhì)量.針對(duì)這點(diǎn),文中提出了一種初始化聚類(lèi)中心的方法,該方法能夠針對(duì)不同數(shù)據(jù)動(dòng)態(tài)地改變初始聚類(lèi)中心的位置,并在以特征屬性離散程度最小的二維子空間平面上進(jìn)行初始化,能夠有效提高聚類(lèi)過(guò)程穩(wěn)定性以及聚類(lèi)質(zhì)量.本文提出的彈性網(wǎng)絡(luò)算法能夠成功用于求解聚類(lèi)問(wèn)題,并且能夠有效改善大部分傳統(tǒng)和經(jīng)典算法的不足,得到更高質(zhì)量的聚類(lèi)結(jié)果.

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

原始彈性網(wǎng)絡(luò)最初用于求解旅行商問(wèn)題(TSP).原始彈性網(wǎng)絡(luò)由M個(gè)彈性節(jié)點(diǎn)U=[u1,u2,…,uM]T和N個(gè)城市節(jié)點(diǎn)P=[p1,p2,…,pN]T組成,城市節(jié)點(diǎn)即為二維空間下的城市坐標(biāo).算法最終使每個(gè)城市節(jié)點(diǎn)對(duì)應(yīng)至少一個(gè)彈性節(jié)點(diǎn).Durbin和Willshaw對(duì)于彈性節(jié)點(diǎn)和城市節(jié)點(diǎn)的數(shù)量建議使用M=2.5N,以解決圖像中邊緣點(diǎn)可能不均勻分布的問(wèn)題[15].

彈性網(wǎng)絡(luò)在求解TSP問(wèn)題時(shí)通過(guò)求解能量函數(shù)的全局最小值而得到最終解,這是一個(gè)梯度下降算法.能量函數(shù)定義如下:

(1)

公式(1)的能量函數(shù)中α項(xiàng)為代價(jià)項(xiàng),用于控制空間中城市節(jié)點(diǎn)對(duì)彈性節(jié)點(diǎn)的吸引力,作用是尋找有效解;而β項(xiàng)為限制項(xiàng),用于控制相鄰彈性結(jié)點(diǎn)間的吸引力,作用是尋找最優(yōu)解.適當(dāng)調(diào)整參數(shù)α、β則可以平衡這兩種力量.原始彈性網(wǎng)絡(luò)引入了溫度參數(shù)K,K初始值設(shè)為0.2,并且每n次迭代將其降低1%.

原始彈性網(wǎng)絡(luò)通過(guò)以下公式迭代更新彈性節(jié)點(diǎn)的位置:

(2)

在公式(2)的每n次迭代之后,K的值逐漸減小,并且這些彈性節(jié)點(diǎn)逐漸從被多個(gè)城市節(jié)點(diǎn)吸引變?yōu)楸粠讉€(gè)城市節(jié)點(diǎn)吸引.當(dāng)K值很低時(shí),保證了形成的每個(gè)彈性帶輪廓都是有效的TSP行程[22].上式中ωij表示城市節(jié)點(diǎn)pi對(duì)彈性節(jié)點(diǎn)uj的影響程度,可通過(guò)極大熵原理求得.定義如下:

(3)

根據(jù)確定性退火技術(shù)[23,24],原始彈性網(wǎng)絡(luò)求解時(shí)將整個(gè)系統(tǒng)看作是物理系統(tǒng).當(dāng)值在迭代過(guò)程中逐漸趨于0,能量函數(shù)達(dá)到全局最小值,系統(tǒng)逐漸趨于平衡.每個(gè)城市節(jié)點(diǎn)都能匹配到至少一個(gè)彈性節(jié)點(diǎn),從而得出TSP問(wèn)題的有效解.

3 引入特征選擇初始化策略的彈性網(wǎng)絡(luò)聚類(lèi)算法

本文提出了引入特征選擇初始化策略的彈性網(wǎng)絡(luò)聚類(lèi)算法(FSENC算法).通過(guò)改變能量函數(shù)與自由能函數(shù)的結(jié)構(gòu),使新算法更適用于求解聚類(lèi)問(wèn)題.而且,根據(jù)特征屬性離散度的不同,提出了一種能根據(jù)數(shù)據(jù)動(dòng)態(tài)生成彈性節(jié)點(diǎn)的方法.該方法有效地增強(qiáng)了算法靈活性,加快了聚類(lèi)過(guò)程.通過(guò)分析可知FSENC算法能夠有效提高聚類(lèi)質(zhì)量.

3.1 算法原理

對(duì)于聚類(lèi)問(wèn)題,在多元空間中定義一個(gè)含有n個(gè)數(shù)據(jù)點(diǎn)的集合X=[x1,x2,…,xn]T,每個(gè)數(shù)據(jù)點(diǎn)均含有m個(gè)特征屬性Xi=[xi,1,xi,2,…,xi,m]T.并初始化一條含有k個(gè)彈性節(jié)點(diǎn)的彈性帶y=[y1,y2,…,ym]T,其中k為最終聚類(lèi)中心的數(shù)量.

根據(jù)聚類(lèi)中數(shù)據(jù)點(diǎn)與聚類(lèi)中心的關(guān)系,本文定義了新的聚類(lèi)代價(jià)函數(shù):

(4)

將代價(jià)函數(shù)替換進(jìn)原始能量函數(shù)中,可得到新的能量函數(shù)為:

(5)

其中ωij為各數(shù)據(jù)點(diǎn)xi屬于各個(gè)聚類(lèi)中心yj的概率分布.由于ωij沒(méi)有先驗(yàn)知識(shí),是未知的概率分布,因此本文使用極大熵原理[16,23]來(lái)確定ωij的基本形式.根據(jù)能量函數(shù),熵函數(shù)定義如下:

(6)

在能量函數(shù)與熵函數(shù)的約束下,通過(guò)以下公式求解變分問(wèn)題:

(7)

可得到ωij的高斯概率分布:

(8)

公式(8)中T是常數(shù)參數(shù),對(duì)應(yīng)于原始彈性網(wǎng)絡(luò)算法中的溫度參數(shù).ωij顯示出以下概率分布特點(diǎn):當(dāng)T→∞時(shí),每個(gè)數(shù)據(jù)點(diǎn)屬于任一簇的概率相同;當(dāng)T→0時(shí),每個(gè)數(shù)據(jù)點(diǎn)以1的概率僅屬于某一簇.Zt為數(shù)據(jù)點(diǎn)xi的分布函數(shù),定義如下:

(9)

根據(jù)每個(gè)節(jié)點(diǎn)的獨(dú)立概率可以得到關(guān)于數(shù)據(jù)點(diǎn)xi的總的分布函數(shù),定義如下:

(10)

對(duì)應(yīng)物理系統(tǒng)的Helmholtz自由能函數(shù)的一般形式[24,25]如下:

(11)

公式(11)中,后一項(xiàng)為限制項(xiàng)Enod,代表彈性節(jié)點(diǎn)之間的作用力.對(duì)于聚類(lèi)問(wèn)題,由于彈性節(jié)點(diǎn)的數(shù)量較少,并且遠(yuǎn)遠(yuǎn)少于數(shù)據(jù)點(diǎn)的數(shù)量,彈性節(jié)點(diǎn)之間的相互作用力在實(shí)際問(wèn)題中非常小,因此可以忽略[17].因此,本文去掉了Enod項(xiàng),旨在加快聚類(lèi)過(guò)程.新的自由能函數(shù)定義如下:

(12)

為防止因自由能下降幅度過(guò)大導(dǎo)致彈性節(jié)點(diǎn)移動(dòng)距離過(guò)大,從而偏離簇中心導(dǎo)致聚類(lèi)失敗的問(wèn)題,本文引入了常數(shù)參數(shù)δ.該參數(shù)用來(lái)控制聚類(lèi)中心神經(jīng)元的移動(dòng)距離的幅度.在模擬退火過(guò)程中,當(dāng)自由能達(dá)到最小值時(shí),系統(tǒng)趨于穩(wěn)定達(dá)到平衡狀態(tài).

求解過(guò)程中需要更新每一次迭代后各彈性節(jié)點(diǎn)的位置從而達(dá)到實(shí)時(shí)追蹤聚類(lèi)過(guò)程,因此需要得到每次迭代中各彈性節(jié)點(diǎn)移動(dòng)的增量.由彈性網(wǎng)絡(luò)理論及極大熵原理可知最佳節(jié)點(diǎn)位置的非線性耦合方程為:

∑iωij(xi-yj)=0,?j

(13)

使用最陡下降法求解以下方程:

(14)

即可得到每次迭代中各彈性節(jié)點(diǎn)移動(dòng)增量Δyj,其中Δτ為每次迭代的步長(zhǎng),選擇合適的Δτ可以使網(wǎng)絡(luò)充分運(yùn)行從而得到高質(zhì)量解.

大多數(shù)經(jīng)典聚類(lèi)算法在對(duì)聚類(lèi)中心初始化時(shí)都是隨機(jī)選取聚類(lèi)中心的位置,這導(dǎo)致初始聚類(lèi)中心的位置無(wú)法根據(jù)輸入數(shù)據(jù)進(jìn)行動(dòng)態(tài)改變,從而影響聚類(lèi)質(zhì)量.因此,尋找一種合適的聚類(lèi)初始化方法對(duì)提高聚類(lèi)質(zhì)量有很大幫助.結(jié)合子空間聚類(lèi)相關(guān)理論,本文提出了一種能動(dòng)態(tài)地改變各彈性節(jié)點(diǎn)初始位置的初始化方法.

首先,根據(jù)以下公式:

(15)

然后,圓的半徑由以下公式求得:

(16)

最后,根據(jù)聚類(lèi)定義中各簇內(nèi)相似度高、簇間相似度低的要求,本文提出了特征屬性離散程度計(jì)算公式:

(17)

根據(jù)公式(17)可以得到所有特征屬性的離散程度值D=[D1,D2,…,Dm]T.

文中提出的初始化方法會(huì)根據(jù)數(shù)據(jù)的重心計(jì)算得到圓心與半徑,然后根據(jù)計(jì)算得到各特征屬性離散程度值D,并在離散度最小的二維平面上根據(jù)所求得的圓心與半徑生成一個(gè)圓,并在圓上均勻生成k個(gè)聚類(lèi)中心神經(jīng)元.本文提出的彈性帶及聚類(lèi)中心神經(jīng)元初始化方法綜合考慮了所有數(shù)據(jù)點(diǎn)的位置,并以重心為基礎(chǔ),能夠根據(jù)不同數(shù)據(jù)點(diǎn)的分布情況動(dòng)態(tài)調(diào)節(jié)聚類(lèi)中心神經(jīng)元的初始位置,從而適應(yīng)求解不同問(wèn)題的需要.

3.2 算法步驟描述

本文以彈性網(wǎng)絡(luò)理論為基礎(chǔ)提出了一種新的加入特征選擇初始化方法的彈性網(wǎng)絡(luò)聚類(lèi)算法(FSENC).該算法首先針對(duì)聚類(lèi)問(wèn)題中數(shù)據(jù)點(diǎn)與聚類(lèi)中心的關(guān)系定義了新的代價(jià)函數(shù),并將新的代價(jià)函數(shù)替換原彈性網(wǎng)絡(luò)中的能量函數(shù),使得改進(jìn)的彈性網(wǎng)絡(luò)能夠運(yùn)用于求解聚類(lèi)問(wèn)題;其次,提出了一種能夠根據(jù)數(shù)據(jù)內(nèi)在結(jié)構(gòu)自動(dòng)選擇合適的初始化方案方法.使得算法有更高的靈活性.所提出聚類(lèi)算法求解步驟描述如下:

首先定義一個(gè)含有n個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集X=[x1,x2,…,xn]T,每個(gè)數(shù)據(jù)點(diǎn)均具有m個(gè)特征屬性xi=[xi,1,xi,2,…,xi,m]T.設(shè)置聚類(lèi)數(shù)目k,并根據(jù)輸入數(shù)據(jù)的規(guī)模設(shè)置合適的參數(shù)T和δ的值.

2)通過(guò)對(duì)能量函數(shù)以及對(duì)應(yīng)熵函數(shù)變分處理可以得到各數(shù)據(jù)點(diǎn)屬于各彈性節(jié)點(diǎn)的高斯概率分布ωij.根據(jù)極大熵原理求解最佳節(jié)點(diǎn)的非線性耦合方程可以得到動(dòng)量公式(14),并根據(jù)公式求解可得到各彈性節(jié)點(diǎn)移動(dòng)的增量Δyj.

3)根據(jù)當(dāng)前一步求得的增量Δyj以及前一次迭代中各彈性節(jié)點(diǎn)的位置Yt-1可以得到當(dāng)前迭代次數(shù)下各彈性節(jié)點(diǎn)的位置Yt.

5)將各數(shù)據(jù)點(diǎn)xi按照求得的概率分布ωij分配給各聚類(lèi)中心,得到最終聚類(lèi)結(jié)果C={c1,c2,…,ck}.

3.3 算法分析

這一節(jié)分別從彈性帶初始化算法分析,新的能量函數(shù)分析,參數(shù)分析以及算法性能分析4個(gè)方面,通過(guò)在不同種類(lèi)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果來(lái)驗(yàn)證所提出算法的合理性以及性能.

3.3.1 彈性節(jié)點(diǎn)初始化算法分析

傳統(tǒng)算法大都用隨機(jī)選取初始聚類(lèi)中心的方式進(jìn)行初始化,這樣的方法不能根據(jù)數(shù)據(jù)的結(jié)構(gòu)靈活地變化初始聚類(lèi)中心的位置,導(dǎo)致聚類(lèi)過(guò)程不穩(wěn)定,聚類(lèi)時(shí)間過(guò)長(zhǎng)的問(wèn)題,從而影響聚類(lèi)質(zhì)量.本文提出的算法初始化方法能夠有效改善這類(lèi)問(wèn)題,提高聚類(lèi)質(zhì)量.

圖1(a)為分別使用兩種不同初始化方法得到的SED值的迭代對(duì)比圖.兩種方法除了初始化方法不同,其余都相同.FSENC為本文提出的算法,而隨機(jī)初始化方法是從所有數(shù)據(jù)點(diǎn)中隨機(jī)選取k個(gè)點(diǎn)作為初始聚類(lèi)中心的方法.從圖中可以明顯看出,FSENC算法在求解過(guò)程中非常穩(wěn)定,能更快收斂;而隨機(jī)的初始化方法聚類(lèi)過(guò)程中會(huì)有小幅波動(dòng),不穩(wěn)定,而且收斂速度慢.FSENC算法只需要迭代321次,而隨機(jī)初始化方法迭代475次,FSENC算法的迭代次數(shù)比隨機(jī)初始化算法減少32.42%.對(duì)于最終SED值,兩種方法分別為40.11和41.29,FSENC算法比隨機(jī)初始化算法的SED值減少2.86%.分析可知,雖然本文提出的初始化方法與隨機(jī)初始化方法在聚類(lèi)時(shí)SED值差距不大,但能很大程度地加快聚類(lèi)過(guò)程,提高穩(wěn)定性,幫助算法得到更聚類(lèi)質(zhì)量.

圖1 初始化方法和限制項(xiàng)對(duì)聚類(lèi)質(zhì)量的影響Fig.1 Influence of initialization methods and constraints on cluster quality

3.3.2 新的能量函數(shù)分析

本文提出的FSENC算法首先根據(jù)聚類(lèi)問(wèn)題中數(shù)據(jù)點(diǎn)與各聚類(lèi)中心的相互關(guān)系定義了一個(gè)新的代價(jià)函數(shù),從而得到了一個(gè)適用于求解聚類(lèi)問(wèn)題的新型能量函數(shù).其次,又根據(jù)彈性網(wǎng)絡(luò)求解過(guò)程中數(shù)據(jù)點(diǎn)與各彈性節(jié)點(diǎn)之間的受力進(jìn)行分析,去除了自由能函數(shù)中的Enod項(xiàng).即在聚類(lèi)過(guò)程中忽略各彈性節(jié)點(diǎn)之間的力,使各彈性節(jié)點(diǎn)更快地向著聚類(lèi)中心移動(dòng),從而提高聚類(lèi)速度.

為了證明去除Enod項(xiàng)有助于加快聚類(lèi)收斂過(guò)程,本文記錄了FSENC和FSENC算法加入Enod項(xiàng)兩種方法聚類(lèi)過(guò)程中SED值的變化,如圖1(b)所示.對(duì)比結(jié)果可知,兩種方法SED值在聚類(lèi)過(guò)程中趨勢(shì)大致相同,兩種方法迭代次數(shù)分別為347和477次,SED值分別為28.21和28.53.FSENC算法在迭代次數(shù)與SED值分別降低27.25%和1.12%.證明去除Enod項(xiàng)能有效加快聚類(lèi)收斂過(guò)程,并對(duì)提高聚類(lèi)質(zhì)量有一定程度的幫助.

FSENC算法中的能量函數(shù)針對(duì)于聚類(lèi)問(wèn)題做了相應(yīng)的變化,使得彈性網(wǎng)絡(luò)可以用于求解聚類(lèi)問(wèn)題.FSENC算法在聚類(lèi)過(guò)程中使用了確定性退火技術(shù),將整個(gè)系統(tǒng)類(lèi)比為物理系統(tǒng).隨著溫度逐漸降低,自由能逐漸降低,彈性節(jié)點(diǎn)逐漸向各簇中心移動(dòng),直到自由能達(dá)到全局最小時(shí)程序收斂.圖2為FSENC算法在聚類(lèi)退火過(guò)程中彈性節(jié)點(diǎn)與總能量變化示意圖.如圖2(a)為程序初始狀態(tài),為了更清晰的觀察到聚類(lèi)過(guò)程中彈性節(jié)點(diǎn)受溫度及自由能變化逐漸移動(dòng)的過(guò)程,實(shí)驗(yàn)假設(shè)初始狀態(tài)下的3個(gè)聚類(lèi)中心均處于整個(gè)集群的質(zhì)心位置.

圖2 FSENC算法聚類(lèi)過(guò)程中的確定性退火技術(shù)Fig.2 Deterministic annealing technique in the clustering process of the FSENC algorithm

結(jié)合圖2(d)看,在迭代次數(shù)小于20時(shí),總能量值此時(shí)恒定,此時(shí)彈性節(jié)點(diǎn)尚未移動(dòng).隨著溫度逐漸降低,當(dāng)?shù)螖?shù)為20時(shí),總能量突然下降到一個(gè)較低的恒定值.重疊的彈性節(jié)點(diǎn)開(kāi)始移動(dòng)并迅速分離,但是各節(jié)點(diǎn)未完全分離開(kāi),而是分離到了兩個(gè)不同位置,此時(shí)右下有兩個(gè)重疊的彈性節(jié)點(diǎn),如圖2(b)所示.在迭代次數(shù)處于20和50之間,能量值變化較小,各彈性節(jié)點(diǎn)處于緩慢移動(dòng)狀態(tài).當(dāng)?shù)?0次左右時(shí),總能量值再次大幅度下降,右下重疊的彈性節(jié)點(diǎn)由于數(shù)據(jù)點(diǎn)的吸引力作用再次分離.當(dāng)?shù)螖?shù)大于70時(shí),可以看到總能量值逐漸下降并最終趨于一個(gè)較低的穩(wěn)定值,在此過(guò)程中溫度也逐漸下降到較低水平,各彈性節(jié)點(diǎn)逐漸向各簇最佳聚類(lèi)中心移動(dòng).如圖2(c)所示,當(dāng)?shù)螖?shù)為300時(shí),總能量基本保持不變,彈性節(jié)點(diǎn)不再移動(dòng),最終形成3個(gè)簇并得到聚類(lèi)結(jié)果.由以上聚類(lèi)過(guò)程分析可知,FSENC算法中新能量函數(shù)的建立是合理的,能夠很好地用于求解聚類(lèi)問(wèn)題.

3.3.3 相關(guān)參數(shù)分析

FSENC算法中共有兩個(gè)參數(shù)會(huì)對(duì)聚類(lèi)過(guò)程產(chǎn)生影響,對(duì)于不同種類(lèi),不同規(guī)模的數(shù)據(jù),選取合適的參數(shù)組合能夠有效提高聚類(lèi)質(zhì)量.通過(guò)實(shí)驗(yàn)可以得到適合的參數(shù)選取范圍.分析可知,參數(shù)δ值越大,SED值越大,更容易聚類(lèi)失敗,而網(wǎng)絡(luò)迭代次數(shù)會(huì)增加,不利于網(wǎng)絡(luò)收斂,求解質(zhì)量較差.通過(guò)分析可以看出參數(shù)δ最佳取值范圍為[0.1,0.5].當(dāng)δ值在合適范圍內(nèi)時(shí),參數(shù)T值越小,SED值越小,迭代次數(shù)減少,聚類(lèi)質(zhì)量越高.

但是這并不意味著值越小越好,過(guò)小的T值會(huì)導(dǎo)致聚類(lèi)過(guò)程中能量函數(shù)不能收斂于全局最小值而提前結(jié)束程序,無(wú)法得到最優(yōu)的聚類(lèi)結(jié)果.因此在選取參數(shù)T值時(shí)應(yīng)當(dāng)在合適的取值范圍內(nèi),根據(jù)數(shù)據(jù)內(nèi)在結(jié)構(gòu)的不同,選取一個(gè)較大的初始值,隨著程序的運(yùn)行使T值逐漸減小,直到T值減小到較低水平,彈性節(jié)點(diǎn)均不再移動(dòng),此時(shí)程序收斂.這樣設(shè)置參數(shù)可以使得整個(gè)系統(tǒng)在算法初始階段有較高的活性,從而改變初期各彈性節(jié)點(diǎn)所受的力的大小,使各彈性節(jié)點(diǎn)能夠更快地找到每個(gè)簇;隨著參數(shù)越來(lái)越小,此時(shí)整個(gè)系統(tǒng)的活性降低,各彈性節(jié)點(diǎn)無(wú)法大幅度移動(dòng),避免了移動(dòng)幅度過(guò)大導(dǎo)致的聚類(lèi)失敗.各彈性節(jié)點(diǎn)只能緩慢地朝著各簇最佳聚類(lèi)中心移動(dòng),最終無(wú)限接近最佳聚類(lèi)中心并停止移動(dòng).這樣能夠很好地保證整個(gè)系統(tǒng)以最佳方式運(yùn)作,得到更好的聚類(lèi)結(jié)果.通過(guò)分析可以得到溫度參數(shù)的最佳取值范圍為[1,4].

通過(guò)大量實(shí)驗(yàn),可以發(fā)現(xiàn)不同數(shù)據(jù)規(guī)模的聚類(lèi)問(wèn)題在取得最佳聚類(lèi)結(jié)果時(shí)所用的的參數(shù)不是固定的.根據(jù)數(shù)據(jù)量的不同應(yīng)當(dāng)在參數(shù)取值范圍內(nèi)做適當(dāng)調(diào)整以取得最優(yōu)解.根據(jù)經(jīng)驗(yàn),參數(shù)選取應(yīng)當(dāng)遵循以下規(guī)則:對(duì)于數(shù)據(jù)量大的聚類(lèi)問(wèn)題,應(yīng)選取較大的值,對(duì)于較小數(shù)據(jù)量的聚類(lèi)問(wèn)題,應(yīng)選取較小的T值,這樣能使程序在不同數(shù)據(jù)量下均能夠充分的運(yùn)行以得到高質(zhì)量解.參數(shù)δ的選取與聚類(lèi)簇?cái)?shù)相關(guān),聚類(lèi)簇?cái)?shù)量越大,δ值應(yīng)當(dāng)越大.使聚類(lèi)過(guò)程中各彈性節(jié)點(diǎn)能夠更快更好地找到各簇并取得最優(yōu)解.

3.3.4 算法性能分析

為了驗(yàn)證FSENC算法的有效性及合理性,本文選取了一個(gè)含有2000數(shù)據(jù)的10維隨機(jī)生成數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),簇?cái)?shù)量為3簇.記錄了實(shí)驗(yàn)數(shù)據(jù)并與未加入創(chuàng)新步驟的基礎(chǔ)彈性網(wǎng)絡(luò)聚類(lèi)算法(ENC)做了對(duì)比,從而綜合展示FSENC算法的性能.

圖3(a)和圖3(b)分別為聚類(lèi)過(guò)程中總能量值與SED的迭代圖.對(duì)比圖3(a)中總能量值的變化可以看出FSENC算法比ENC算法更快達(dá)到較低水平并趨于收斂.FSENC需要387次迭代,而ENC算法需要594次迭代,FSENC算法比ENC算法迭代次數(shù)減少34.85%.對(duì)比圖3(b)中兩種算法的SED值,FSENC算法最終SED值為21.86,而ENC算法SED值為35.51.FSENC算法SED值比ENC算法降低38.44%,能夠得到更高的聚類(lèi)質(zhì)量.

圖3 FSENC算法和ENC算法的聚類(lèi)過(guò)程迭代圖Fig.3 Evolution of the clustering process of FSENC and ENC algorithm

FSENC算法在迭代過(guò)程中有更高的穩(wěn)定性.如圖4所示,實(shí)驗(yàn)追蹤了迭代過(guò)程中3個(gè)聚類(lèi)中心的其中一個(gè)神經(jīng)元的移動(dòng).圖4(a)為該彈性節(jié)點(diǎn)在水平方向(ΔX)的移動(dòng)距離,圖4(b)為該彈性節(jié)點(diǎn)在垂直方向(ΔY)的移動(dòng)距離.從兩張圖中可以清晰地看到FSENC算法在聚類(lèi)過(guò)程中彈性節(jié)點(diǎn)的移動(dòng)非常穩(wěn)定,雖然移動(dòng)幅度較大但是能夠很快地趨于平穩(wěn)狀態(tài).而ENC算法在聚類(lèi)過(guò)程中彈性節(jié)點(diǎn)移動(dòng)波動(dòng)較大,需要更長(zhǎng)的迭代次數(shù)才能趨于穩(wěn)定狀態(tài).FSENC算法聚類(lèi)過(guò)程神經(jīng)元的移動(dòng)比ENC算法更穩(wěn)定,更有助于算法更快地取得最優(yōu)解.

圖4 兩種算法聚類(lèi)中彈性節(jié)點(diǎn)位置變化演進(jìn)圖Fig.4 Elastic node position changes of FSENC and ENC algorithm in clustering process

由于彈性網(wǎng)絡(luò)獨(dú)特的網(wǎng)絡(luò)結(jié)構(gòu)以及求解方法,使得彈性網(wǎng)絡(luò)聚類(lèi)算法相比于其他傳統(tǒng)聚類(lèi)算法有著更高的穩(wěn)定性,總能獲得唯一解.本文分別選取了含有3000和10000個(gè)數(shù)據(jù)的隨機(jī)數(shù)據(jù)集進(jìn)行了對(duì)比試驗(yàn),將FSENC算法與較傳統(tǒng)的k-means、k-medoids與較新的FAKM[26]、ENC算法進(jìn)行了比較,FAKM算法是基于k-means算法而改進(jìn)的新算法.如圖5所示為各算法在這兩個(gè)數(shù)據(jù)集分別運(yùn)行30次的SED值.通過(guò)分析可知,FSENC算法在兩個(gè)數(shù)據(jù)量下的SED值均小于其他四種算法.而且,FSENC算法與ENC算法的SED值始終唯一,而k-means、k-medoids、FAKM算法每一次運(yùn)行的SED值均有變化,且變化幅度較大.k-means算法的SED值最大,FSENC算法SED值最小.FSENC算法平均SED值比k-means、k-medoids,FAKM、ENC算法分別減小45.77%、42.83%、25.44%、16.98%.FSENC算法的聚類(lèi)質(zhì)量均高于其他4種算法,有更高的性能.

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

在這一部分中,本文在大量人工合成和真實(shí)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)來(lái)評(píng)估FSENC算法的性能.與一些經(jīng)典的和較新的聚類(lèi)算法做了對(duì)比,例如k-means、 k-medoids、 DBSCAN、 BIRCH、 ENC、 FAKM[26]、 DEKM[27]等7種算法做了對(duì)比實(shí)驗(yàn).

4.1 數(shù)據(jù)集

實(shí)驗(yàn)中使用的數(shù)據(jù)集包括4個(gè)人工合成數(shù)據(jù)集和10個(gè)真實(shí)數(shù)據(jù)集.這些數(shù)據(jù)集的數(shù)據(jù)規(guī)模(數(shù)據(jù)量、維度、簇?cái)?shù))以及內(nèi)在結(jié)構(gòu)(凹凸,密度差)均不相同.這些數(shù)據(jù)集的屬性信息如表1所示.其中人工合成的數(shù)據(jù)集除Sy1外均可從開(kāi)源數(shù)據(jù)集網(wǎng)站(http://cs.uef.fi/sipu/datasets/)獲得.真實(shí)數(shù)據(jù)集可從UCI數(shù)據(jù)庫(kù)(http://archive.ics.uci.edu/ml/index.php)獲得.

表1 實(shí)驗(yàn)使用的數(shù)據(jù)集屬性Table 1 Attribute information of the datasets used in the experiments

4.2 聚類(lèi)質(zhì)量評(píng)價(jià)標(biāo)準(zhǔn)及參數(shù)選取

實(shí)驗(yàn)部分使用SED[28]值和聚類(lèi)精度(Accuracy)作為聚類(lèi)評(píng)價(jià)指標(biāo).SED的定義如下:

(18)

其中,是第i個(gè)數(shù)據(jù)點(diǎn),yj是第j個(gè)聚類(lèi)中心,d(xi,yj)為歐幾里得距離,Cj為第j簇.SED值代表各簇?cái)?shù)據(jù)點(diǎn)到各個(gè)簇聚類(lèi)中心的距離之和,SED值越小說(shuō)明聚類(lèi)質(zhì)量越高.

聚類(lèi)精度(Accuracy)定義如下:

(19)

其中ni為各簇被正確分類(lèi)的數(shù)據(jù)點(diǎn)的個(gè)數(shù),N為所有數(shù)據(jù)點(diǎn)的總數(shù).ACC值越大代表聚類(lèi)質(zhì)量越高.

從章節(jié)3.3.3中可知參數(shù)選取規(guī)則與范圍.對(duì)于實(shí)驗(yàn)部分的參數(shù)選取遵循以下規(guī)則:對(duì)于0～1000數(shù)據(jù)量的小規(guī)模問(wèn)題,參數(shù)T取值為2,參數(shù)α取值為0.3;數(shù)據(jù)量為1000～10000的中等規(guī)模問(wèn)題,參數(shù)T取值為3,參數(shù)α取值為0.15;數(shù)據(jù)量為10000以上的大等規(guī)模問(wèn)題,參數(shù)取值為4,參數(shù)α取值為0.1.實(shí)驗(yàn)中對(duì)不同問(wèn)題的參數(shù)可在參數(shù)取值范圍內(nèi)微調(diào).

4.3 人工合成數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

圖6～圖8為k-means、BIRCH和FSENC 3種算法分別在Jain、Uneven、R15人工合成數(shù)據(jù)集上的聚類(lèi)結(jié)果.通常情況下數(shù)據(jù)內(nèi)在結(jié)構(gòu)例如凸形或非凸、密度差異、簇?cái)?shù)目等因素會(huì)影響聚類(lèi)算法的性能.分析圖6可知,對(duì)于非凸數(shù)據(jù)Jain,FSENC算法的SED值比k-means和BIRCH算法分別減少34.41%、21.21%,聚類(lèi)質(zhì)量明顯高于其余兩種算法.圖7中Uneven數(shù)據(jù)密度差異較大,其中實(shí)心矩形為聚類(lèi)中心.從圖中結(jié)果對(duì)比可知,FSENC算法的SED值比對(duì)比算法分別減少33.95%、20.95%.FSENC算法的聚類(lèi)中心比其余兩種算法的聚類(lèi)中心更接近于高密度區(qū)域的最佳質(zhì)心的位置,證明了FSENC算法在非均勻數(shù)據(jù)中準(zhǔn)確找到簇結(jié)構(gòu)方面更有優(yōu)勢(shì).圖8中的R15數(shù)據(jù)集含有較多的簇?cái)?shù),分析得知FSENC算法的SED值比其余算法分別減少22.03%、12.08%,聚類(lèi)效果明顯好于k-means、BIRCH算法.在不同種類(lèi)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,FSENC算法能夠很好地識(shí)別出不同大小、不同形狀和不同密度的簇,得到較高的聚類(lèi)質(zhì)量.

圖6 3種算法在數(shù)據(jù)集Jain上的聚類(lèi)結(jié)果Fig.6 Clustering results of Jain by three algorithms

圖7 3種算法在數(shù)據(jù)集Uneven上的聚類(lèi)結(jié)果Fig.7 Clustering results of Uneven by three algorithms

圖8 3種算法在數(shù)據(jù)集R15上的聚類(lèi)結(jié)果Fig.8 Clustering results of R15 by three algorithms

為了進(jìn)一步驗(yàn)證FSENC算法的性能,本文在隨機(jī)生成的個(gè)人工合成數(shù)據(jù)集Sy1上做了對(duì)比實(shí)驗(yàn),并與k-means,BIRCH,DEKM算法進(jìn)行了比較.Sy1的屬性信息如表2和表3所示.這部分實(shí)驗(yàn)使用SED作為聚類(lèi)評(píng)價(jià)標(biāo)準(zhǔn),表中SED值取20次實(shí)驗(yàn)的平均值.

表2 Sy1數(shù)據(jù)集中3維和7維數(shù)據(jù)的聚類(lèi)結(jié)果Table 2 Clustering results of 3D and 7D data in Sy1 data set

表3 Sy1數(shù)據(jù)集中10維和13維數(shù)據(jù)的聚類(lèi)結(jié)果Table 3 Clustering results of 10D and 13D data in Sy1 data set

通過(guò)分析表2和表3數(shù)據(jù),k-means,BIRCH,DEKM,FSENC這4種算法平均SED分別為15968.14、15594.45、13878.52、11618.26.FSENC算法SED值比其余3種算法分別降低27.24%、25.50%、16.29%.對(duì)于數(shù)據(jù)量大于5000,維度為10、13的較大規(guī)模數(shù)據(jù),FSENC算法SED值比其余3種算法分別降低28.90%、28.10%、18.68%.FSENC算法在求解時(shí)不僅穩(wěn)定性高,而且能夠適用于求解不同數(shù)據(jù)量下的聚類(lèi)問(wèn)題,尤其在求解大數(shù)據(jù)量問(wèn)題時(shí),FSENC算法比其他算法更具優(yōu)勢(shì),能得到更高質(zhì)量的聚類(lèi)結(jié)果.

4.4 真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

FSENC算法不僅在求解隨機(jī)生成問(wèn)題時(shí)能夠得到高質(zhì)量解,而且在求解真實(shí)聚類(lèi)問(wèn)題時(shí)同樣可以得到高質(zhì)量的聚類(lèi)解.為了證明這一點(diǎn),實(shí)驗(yàn)選取了10個(gè)真實(shí)數(shù)據(jù)做了對(duì)比實(shí)驗(yàn).將FSENC算法與k-means等7種算法進(jìn)行比較,這部分實(shí)驗(yàn)以SED值與Accuracy作為評(píng)價(jià)指標(biāo),N/A代表無(wú)解,標(biāo)準(zhǔn)數(shù)據(jù)均取20次結(jié)果的平均值,如表4和表5所示.分析表中數(shù)據(jù)可以得到以下結(jié)論:

表4 真實(shí)數(shù)據(jù)集的聚類(lèi)SED值Table 4 Clustering SED on real datasets

表5 真實(shí)數(shù)據(jù)集的聚類(lèi)準(zhǔn)確率Table 5 Clustering accuracy on real datasets

1)k-medoids算法在HTRU2、Hand、Skin這3個(gè)大規(guī)模數(shù)據(jù)集上無(wú)法得到聚類(lèi)結(jié)果,而其余算法均可得到聚類(lèi)解.在有解的情況下,FSENC算法比其余7種算法平均SED分別減小27.98%、26.13%、26.75%、21.22%、15.05%、12.89%、19.73%.

2)FSENC算法平均聚類(lèi)精度為76.07%,比其余7種算法平均聚類(lèi)精度分別提高了18.09%、17.02%、21.77%、9.25%、6.07%、3.54%、8.26%.除FSENC算法外,DEKM算法平均聚類(lèi)精度最高,DBSCAN算法平均聚類(lèi)精度最低.FSENC算法平均聚類(lèi)精度均高于其余7種算法,證明該算法能夠在各類(lèi)真實(shí)數(shù)據(jù)集上得到更高質(zhì)量的解.FSENC平均聚類(lèi)精度比ENC算法高8.26%,說(shuō)明本文對(duì)算法的改進(jìn)對(duì)提升聚類(lèi)質(zhì)量有很大幫助.

3)FSENC算法在Wine-white、HTRU2、Hand、Skin等較大規(guī)模數(shù)據(jù)集上平均聚類(lèi)精度比其余算法分別提高了23.76%、30.18%、25.48%、10.06%、4.22%、3.32%、8.19%.而在其余小規(guī)模數(shù)據(jù)集上平均聚類(lèi)精度比其余算法分別提高14.32%、12.50%、19.31%、8.72%、7.31%、3.68%、8.31%.FSENC算法聚類(lèi)精度在大規(guī)模數(shù)據(jù)集上平均提高了15.03%,在小規(guī)模數(shù)據(jù)集上平均提高了10.59%.這也說(shuō)明了FSENC算法更適合求解高維大數(shù)據(jù)量聚類(lèi)問(wèn)題.

5 結(jié) 論

本文提出了一種新的加入特征選擇初始化方法的彈性網(wǎng)絡(luò)聚類(lèi)算法FSENC.該算法根據(jù)聚類(lèi)中數(shù)據(jù)點(diǎn)與聚類(lèi)中心的關(guān)系入手,首先重新定義了一個(gè)更有助于求解聚類(lèi)問(wèn)題的代價(jià)函數(shù).并基于新的代價(jià)函數(shù)和極大熵原理,定義了一個(gè)新的聚類(lèi)彈性網(wǎng)絡(luò)能量函數(shù),使FSENC算法比基礎(chǔ)彈性網(wǎng)絡(luò)聚類(lèi)算法(ENC)更適合解決聚類(lèi)問(wèn)題.FSENC算法是一種無(wú)監(jiān)督的優(yōu)化方法,通過(guò)自學(xué)習(xí)解決聚類(lèi)問(wèn)題,無(wú)需人工訓(xùn)練或干預(yù).求解時(shí)根據(jù)確定性退火技術(shù),自動(dòng)地最小化能量函數(shù)從而得到聚類(lèi)問(wèn)題的解.其次,該算法在求解時(shí)去掉了基礎(chǔ)彈性網(wǎng)絡(luò)自由能函數(shù)中的限制項(xiàng),消除了聚類(lèi)過(guò)程中彈性節(jié)點(diǎn)間的干擾,使彈性節(jié)點(diǎn)更快地移動(dòng),提高了聚類(lèi)質(zhì)量和效率.最后,本文提出了一種能夠根據(jù)數(shù)據(jù)內(nèi)在結(jié)構(gòu)自動(dòng)給出合適的初始化方案的方法.該方法可以有效提高算法靈活性,降低數(shù)據(jù)集內(nèi)部結(jié)構(gòu)的影響,從而提高聚類(lèi)速度.

由于彈性網(wǎng)絡(luò)特殊的網(wǎng)絡(luò)結(jié)構(gòu)及求解方式,FSENC算法在求解高維和大數(shù)據(jù)量的聚類(lèi)問(wèn)題時(shí)更具優(yōu)勢(shì),并且可以直觀地追蹤聚類(lèi)過(guò)程.在大量合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果直觀地表明,FSENC算法比其他一些經(jīng)典的聚類(lèi)算法具有更高的穩(wěn)定性,在求解聚類(lèi)問(wèn)題時(shí)有更好的聚類(lèi)質(zhì)量,尤其是在求解高維和大數(shù)據(jù)量的聚類(lèi)問(wèn)題方面更具優(yōu)勢(shì).