基于神經(jīng)網(wǎng)絡(luò)樹(shù)和人工蜂群優(yōu)化的數(shù)據(jù)聚類

吉珊珊

(東莞職業(yè)技術(shù)學(xué)院計(jì)算機(jī)工程系,廣東 東莞 523808)

高維數(shù)據(jù)聚類算法存在“維數(shù)災(zāi)難”問(wèn)題,導(dǎo)致數(shù)據(jù)聚類的準(zhǔn)確率和時(shí)間效率均無(wú)法滿足實(shí)際的應(yīng)用要求[1]. 特征選擇處理是解決“維數(shù)災(zāi)難”問(wèn)題的一個(gè)有效方法,能夠有效地加快聚類處理的速度[2]. 高維數(shù)據(jù)的特征選擇過(guò)程中,容易誤刪除與目標(biāo)類相關(guān)的特征,保留冗余的特征,將此類特征子集應(yīng)用于聚類程序,不僅降低聚類的準(zhǔn)確率,也增加聚類的處理時(shí)間[3]. 因此,特征選擇的性能對(duì)聚類處理的性能具有巨大的影響.

特征選擇方法可以選出信息量豐富的特征子集,用于后續(xù)的聚類處理,而大多數(shù)特征選擇技術(shù)通過(guò)訓(xùn)練僅輸出唯一的特征子集,如果測(cè)試集存在噪聲或者不完整則會(huì)導(dǎo)致聚類的性能下降[4]. 采用聚類技術(shù)能夠發(fā)現(xiàn)信息量最大的多個(gè)特征類簇[5],有助于兼容不同的測(cè)試集,聚類技術(shù)和特征選擇結(jié)合的技術(shù)稱為混合特征聚類算法,這些技術(shù)能夠最大化聚類準(zhǔn)確率,同時(shí)保持較低的特征冗余度[6]. 通?；旌戏诸惼魈幚砀呔S數(shù)據(jù)集的能力強(qiáng)于單一的特征選擇技術(shù)[7],目前主流的混合聚類算法主要分為兩種策略:基于軟件、硬件的并行計(jì)算策略和基于快速學(xué)習(xí)算法的策略. 第一種策略采用GPU、云計(jì)算等并行計(jì)算架構(gòu). 第二種策略則包括動(dòng)態(tài)森林技術(shù)(dynamic clustering forest)[8]、特征分組技術(shù)[9]、粒子群混合聚類算法等. 綜合不同的實(shí)驗(yàn)結(jié)果,并行計(jì)算架構(gòu)對(duì)于加速聚類速度具有顯著的效果,但對(duì)于聚類的準(zhǔn)確率并不具備改進(jìn)效果,甚至以犧牲聚類準(zhǔn)確率為代價(jià)以加快數(shù)據(jù)處理的速度[10]. 基于學(xué)習(xí)算法的混合聚類算法不僅提高了高維數(shù)據(jù)的聚類準(zhǔn)確率,并且通過(guò)降維處理加快了聚類的速度.

綜上所述,本文設(shè)計(jì)了基于學(xué)習(xí)方法和預(yù)測(cè)方法的高維數(shù)據(jù)聚類算法. 通過(guò)二元人工蜂群優(yōu)化算法選擇每個(gè)簇的最優(yōu)特征子集,將每個(gè)特征子集作為節(jié)點(diǎn)構(gòu)建徑向基函數(shù)網(wǎng)絡(luò)神經(jīng)樹(shù),通過(guò)該機(jī)制能夠有效地提高聚類算法的聚類準(zhǔn)確率,并且加快算法的處理速度. 以神經(jīng)網(wǎng)絡(luò)構(gòu)建決策樹(shù),通過(guò)不同的神經(jīng)樹(shù)預(yù)測(cè)各個(gè)類簇,神經(jīng)樹(shù)不僅具備決策樹(shù)生成規(guī)則的優(yōu)勢(shì),而且具備徑向基函數(shù)網(wǎng)絡(luò)的泛化能力. 通過(guò)門(mén)網(wǎng)絡(luò)機(jī)制聚集森林所有神經(jīng)樹(shù)的最優(yōu)結(jié)果,最終決定最優(yōu)的類標(biāo)簽.

1 人工蜂群優(yōu)化算法

1.1 基礎(chǔ)人工蜂群算法

目前存在多個(gè)基于種群的優(yōu)化算法,如差分進(jìn)化算法、粒子群算法和進(jìn)化算法等,在高維數(shù)值問(wèn)題的效果上人工蜂群算法好于其他的同類型算法,同時(shí)能夠高效地用于解決多維工程問(wèn)題.

人工蜂群(artificial bee colony,ABC)共有雇傭蜂、觀察蜂和偵察蜂3種成員,雇傭蜂負(fù)責(zé)搜索和定位食物源,雇傭蜂和觀察蜂分享食物源的位置信息,觀察蜂對(duì)食物源的鄰域進(jìn)行開(kāi)發(fā),尋找更加優(yōu)質(zhì)的食物源. 如果在T次迭代之后無(wú)法提高食物源的質(zhì)量,此時(shí)啟動(dòng)偵察蜂階段,在搜索空間中隨機(jī)選擇一個(gè)新的食物源. 隨機(jī)選擇食物源的方法定義為:

xi,d=xd min+rand(0,1)(xd max-xd min),

(1)

式中,xi為食物源i的位置,rand(0,1)函數(shù)表示輸出區(qū)間[0,1]服從均勻分布的一個(gè)隨機(jī)數(shù),xd max和xd min分別為搜索空間維度d的上界和下界.

蜂群根據(jù)下式產(chǎn)生候選食物源的位置:

vi,d=xi,d+rand(-1,1)(xi,d-xj,d),

(2)

式中,v為產(chǎn)生的候選食物源,i和j為兩個(gè)食物源,其范圍為{1,2,…,SN},SN為食物源的數(shù)量,d的范圍為{1,2,…,D},D為最大的維度,x為當(dāng)前食物源的位置,rand(-1,1)為生成區(qū)間[-1,1]隨機(jī)數(shù)的函數(shù).

如果式(2)產(chǎn)生的候選食物源優(yōu)于當(dāng)前的食物源,那么雇傭蜂和觀察蜂按食物源質(zhì)量更新位置. 食物源的質(zhì)量評(píng)價(jià)方法為:

(3)

式中,fi為目標(biāo)函數(shù)的結(jié)果,xi為食物源,abs為取絕對(duì)值的運(yùn)算符.

根據(jù)式(4)計(jì)算一個(gè)概率值,觀察蜂根據(jù)該概率值選擇食物源.

(4)

式中,fit為食物源x的適應(yīng)度,SN為食物源的數(shù)量. 式(4)為高頻率、高質(zhì)量的食物源分配了更高的被選擇可能性.

ABC算法全部流程可參考文獻(xiàn)[11].

1.2 改進(jìn)的二元人工蜂群算法

為了使ABC算法適用于本文的特征選擇問(wèn)題,采用連續(xù)-二元映射機(jī)制將ABC的解轉(zhuǎn)化為二元形式. 采用式(5)將連續(xù)解xi映射至二元空間(zi):

zi,d=mod 2(round(abs(mod 2(xi,d)))),

(5)

式中,zi為一個(gè)二元候選解,d為維度,其取值范圍為{0,1,…,D},mod 2(·)函數(shù)將輸入值除以2,abs(·)為取絕對(duì)值的函數(shù),round(·)為取整數(shù)的函數(shù). 式(5)將解約束到區(qū)間[-a,a]內(nèi),a是一個(gè)正實(shí)數(shù).

在每個(gè)維度生成一個(gè)[0,1]區(qū)間的隨機(jī)數(shù),如果隨機(jī)數(shù)大于或等于0.5,將該維度的值改為1,否則,改為0. 二元的食物源位置定義為下式:

vi,d=xi,d?[φ(xi,d?xj,d)],

(6)

式中,“?”表示XOR運(yùn)算,φ為一個(gè)邏輯“非”運(yùn)算.

另一個(gè)二元ABC版本采用比特運(yùn)算代替連續(xù)ABC算法的實(shí)數(shù)運(yùn)算,二元人工蜂群(Binary Artificial Bee Colony,BABC)的食物源位置更新方法為:

vi,d=xi,d?[φ⊙(xi,d?xj,d)],

(7)

式中,φ為以相等概率生成0或1的函數(shù),?為XOR運(yùn)算,⊙為邏輯“與”運(yùn)算,⊕為邏輯“或”運(yùn)算.

本文對(duì)連續(xù)ABC做修改,實(shí)現(xiàn)BABC算法. 首先,修改式(1)的初始化程序,以相等的概率產(chǎn)生0和1值:

(8)

式中,xi,d為食物源i在維度d的位置,rand(·)是生成[0,1]區(qū)間隨機(jī)數(shù)的函數(shù).

對(duì)雇傭蜂階段和觀察蜂階段(式(2))做修改,采用算法1選擇、更新食物源. 算法中vi,d是式(7)生成的位置,D為維度的總數(shù)量,ceil( )返回給定數(shù)的最小整數(shù). max_flip是0～1之間的值,表示支持的最高維度,max_flip控制種群的收斂速度,ceil( )保證至少選擇1個(gè)維度.

本文對(duì)ABC的修改能夠提高雇傭蜂階段和觀察蜂階段的多樣性,原因是這兩個(gè)階段的蜂群隨機(jī)選擇食物源和維度,該機(jī)制有助于提高種群的總體多樣性. 在雇傭蜂階段和觀察蜂階段,維度可能不等于dim,如果從食物源選擇一個(gè)隨機(jī)維度,該維度可能與當(dāng)前蜜蜂的位置不同,但隨著種群收斂,位置的差異會(huì)逐漸降低.

圖1 高維數(shù)據(jù)的混合聚類算法流程框圖Fig.1 Flow chart of hybrid clustering algorithm for high dimensional data

2 基于神經(jīng)樹(shù)的特征混合聚類算法

本文提出的高維數(shù)據(jù)混合聚類算法的流程框圖如圖1所示. 首先,對(duì)輸入數(shù)據(jù)做基于聚類的特征選擇處理,初步過(guò)濾部分冗余度高的特征;然后,基于分類的特征子集和樣本集建立神經(jīng)樹(shù),為神經(jīng)樹(shù)的葉節(jié)點(diǎn)分配類標(biāo)簽;最終,采用門(mén)網(wǎng)絡(luò)分割類簇,區(qū)分類簇之間的交集.

在特征選擇和特征聚類兩類方法中,如果一些目標(biāo)類相關(guān)的特征與其他類的冗余度也較高,那么這兩種方法均會(huì)刪除此類特征. 混合特征聚類算法能夠有效地解決該問(wèn)題,其基本思想是根據(jù)分類準(zhǔn)確率將特征集分類,選出性能最好的特征子集. 本算法引入ABC算法篩選出與目標(biāo)類最相關(guān)的特征子集.

2.1 基于互信息初步篩選特征集

采用互信息(Mutual Information,MI)評(píng)估不相關(guān)特征和冗余特征,一種互信息評(píng)估方法為MI(x,y),比較特征x∈X和目標(biāo)類y之間的相關(guān)性,如果MI(x,y)較低,那么特征x是類y的不相關(guān)特征. 另一種互信息的評(píng)估方法為MI(x′,x″),計(jì)算每對(duì)特征{x′,x″}X的MI,尋找冗余的特征. 離散數(shù)據(jù)的MI計(jì)算為下式:

(9)

連續(xù)數(shù)據(jù)的MI計(jì)算為下式:

(10)

式中,P(x(i))為特征x的出現(xiàn)概率,P(x(i),y(j))為(x(i),y(j))同時(shí)出現(xiàn)的聯(lián)合概率. 因?yàn)檫B續(xù)MI的計(jì)算復(fù)雜度高,所以采用式(9)的離散MI.

設(shè)計(jì)了基于MI的過(guò)濾式特征選擇程序,其步驟為:

Step1.計(jì)算所有特征的互信息MI;

Step2.計(jì)算全部MI的平均值和標(biāo)準(zhǔn)偏差;

Step3.如果某個(gè)特征的MI值小于diff(diff=平均值-標(biāo)準(zhǔn)偏差),那么從特征空間刪除該特征.

2.2 基于BABC的特征處理

聚集初步篩選后剩余的特征集,為每個(gè)類簇構(gòu)建一個(gè)神經(jīng)樹(shù). 每個(gè)神經(jīng)樹(shù)的時(shí)間復(fù)雜度為O(hNM),M為特征數(shù)量,N為樣本數(shù)量,h為神經(jīng)樹(shù)的深度. 為了減少每個(gè)神經(jīng)樹(shù)的計(jì)算時(shí)間,定義參數(shù)δ使復(fù)雜度滿足O(hNM)<δ,根據(jù)這個(gè)不等式能夠確定每個(gè)類的特征數(shù)量. 然后通過(guò)ABC搜索每個(gè)類的最優(yōu)特征子集,ABC的目標(biāo)函數(shù)是最大化徑向基函數(shù)(Radical Basis Function,RBF)網(wǎng)絡(luò)的精度、最小化特征的冗余度. 特征聚類算法的程序如算法2所示.

2.3 結(jié)合BABC和特征選擇的實(shí)現(xiàn)方式

BABC和特征選擇的結(jié)合方式有如下兩點(diǎn):

(1)解表示方法:BABC的蜜源為二元值(0或1),如果某個(gè)蜜源為1,表示選擇該蜜源對(duì)應(yīng)的特征,每個(gè)空間維度為一個(gè)特征分類,值為1的蜜源數(shù)量約束為滿足O(hNM)<δ的最多特征數(shù)量.

(2)適應(yīng)度函數(shù):采用式(3)的適應(yīng)度函數(shù)最大化徑向基函數(shù)網(wǎng)絡(luò)的準(zhǔn)確率、最小化特征的冗余度,以封裝式方法最大化徑向基函數(shù)網(wǎng)絡(luò)的準(zhǔn)確率,以過(guò)濾式方法最小化特征的冗余度:

(11)

式中,acc(k)為訓(xùn)練徑向基函數(shù)網(wǎng)絡(luò)的準(zhǔn)確率,red(k)為特征的內(nèi)部冗余度. red(k)的計(jì)算方法為:

(12)

式中,|ck|為類簇k的特征數(shù)量. 直接將式(9)的(x,y)替換為(x′,x″),計(jì)算類簇k中所有特征的MI(x′,x″).

3 構(gòu)建神經(jīng)樹(shù)

3.1 徑向基函數(shù)網(wǎng)絡(luò)的決策樹(shù)

每個(gè)神經(jīng)樹(shù)按特征分類將數(shù)據(jù)樣本分類,其處理步驟為:

Step 1 在每個(gè)神經(jīng)樹(shù)的根節(jié)點(diǎn)中,將該類簇的特征子集按MI值降序排列,在神經(jīng)樹(shù)的每個(gè)深度將MI值最高的新特征作為分支.

Step 2 神經(jīng)樹(shù)的每個(gè)節(jié)點(diǎn)為一個(gè)徑向基函數(shù)網(wǎng)絡(luò),徑向基函數(shù)網(wǎng)絡(luò)訓(xùn)練當(dāng)前特征子集的樣本. 徑向基函數(shù)網(wǎng)絡(luò)是一種單隱層前饋神經(jīng)網(wǎng)絡(luò),使用徑向基函數(shù)作為隱層神經(jīng)元激活函數(shù),輸出層則是對(duì)隱層神經(jīng)元輸出的線性組合. 采用k-means聚類方法選擇隱層節(jié)點(diǎn)的中心,網(wǎng)絡(luò)輸入層和隱層的節(jié)點(diǎn)數(shù)量均等于特征的數(shù)量,輸出層的節(jié)點(diǎn)數(shù)量等于類標(biāo)簽的數(shù)量.

Step 3 對(duì)于父節(jié)點(diǎn)中的每個(gè)RBF網(wǎng)絡(luò)nl,評(píng)估每個(gè)類的計(jì)算誤差. 采用反向傳播方式和上文選出的特征對(duì)RBF進(jìn)行訓(xùn)練,選出誤差最小的一個(gè)類,將該類的所有樣本放入左子節(jié)點(diǎn),剩余樣本放入右子節(jié)點(diǎn). 圖2所示是構(gòu)建神經(jīng)樹(shù)的流程圖,圖3所示是構(gòu)建神經(jīng)樹(shù)的一個(gè)實(shí)例. 因?yàn)樽笞庸?jié)點(diǎn)的樣本同質(zhì),所以左子節(jié)點(diǎn)為葉節(jié)點(diǎn),而右子節(jié)點(diǎn)繼續(xù)分支處理.

圖2 構(gòu)建神經(jīng)樹(shù)的流程圖Fig.2 Flow chart for building a neural tree

圖3 構(gòu)建神經(jīng)樹(shù)的一個(gè)實(shí)例Fig.3 Building an instance of a neural tree

Step 4 右子節(jié)點(diǎn)采用父節(jié)點(diǎn)的先驗(yàn)知識(shí),從而加快RBF網(wǎng)絡(luò)的訓(xùn)練速度. 首先,將父節(jié)點(diǎn)的特征集輸入右子節(jié)點(diǎn),然后,加入一個(gè)新特征. 父節(jié)點(diǎn)徑向基函數(shù)網(wǎng)絡(luò)的最終權(quán)重w(nl)也輸入右子節(jié)點(diǎn),設(shè)計(jì)了算法3確定右子節(jié)點(diǎn)徑向基函數(shù)網(wǎng)絡(luò)的最優(yōu)權(quán)重,算法3中w(nl+1)是一個(gè)均勻隨機(jī)數(shù). 如果重新計(jì)算右子神經(jīng)樹(shù)的權(quán)重,需要計(jì)算矩陣(M行×N列)的偽逆矩陣,其復(fù)雜度為O(MN3). 因此,本文利用父節(jié)點(diǎn)的先驗(yàn)知識(shí)加速右子節(jié)點(diǎn)的分支速度.

Step 5.如果類簇的所有特征輸入分類器或者右子節(jié)點(diǎn)達(dá)到同質(zhì),那么跳至步驟6;否則更新神經(jīng)樹(shù)的結(jié)構(gòu),增加深度l=l+1,返回步驟3.

Step 6.該步驟將比例最高的類標(biāo)簽分配至右子節(jié)點(diǎn)的所有樣本.

3.2 基于門(mén)網(wǎng)絡(luò)的類簇分割

特征聚類階段并未保證特征類簇間的分離性,所以不同類簇之間可能存在交集. 將新樣本的特征集按特征分類做分解,樣本加入對(duì)應(yīng)的神經(jīng)樹(shù),神經(jīng)樹(shù)可能為樣本分配不同的類標(biāo)簽,采用門(mén)網(wǎng)絡(luò)集成所有的結(jié)果. 門(mén)網(wǎng)絡(luò)的設(shè)計(jì)目標(biāo)主要有兩點(diǎn):(1)結(jié)合所有神經(jīng)樹(shù)的結(jié)果,最終為每個(gè)樣本產(chǎn)生一個(gè)唯一的類標(biāo)簽;(2)如果一個(gè)樣本存在多個(gè)類標(biāo)簽,那么采用多數(shù)投票(Majority Voting,MV)技術(shù)根據(jù)可靠性選出唯一的類標(biāo)簽.

具體過(guò)程為:檢查是否所有葉節(jié)點(diǎn)分配了唯一的類標(biāo)簽,如果存在葉節(jié)點(diǎn)分配了多個(gè)類標(biāo)簽的情況,那么采用MV技術(shù)根據(jù)可靠性選出唯一的類標(biāo)簽. 最終所有的葉節(jié)點(diǎn)均分配了唯一的類標(biāo)簽.

3.3 算法的時(shí)間復(fù)雜度分析

神經(jīng)樹(shù)的計(jì)算復(fù)雜度依賴徑向基函數(shù)網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)量和每個(gè)徑向基函數(shù)網(wǎng)絡(luò)的復(fù)雜度.

徑向基函數(shù)網(wǎng)絡(luò)負(fù)責(zé)搜索最優(yōu)的權(quán)重向量W′,并為每個(gè)樣本分配正確的類標(biāo)簽. 假設(shè)樣本的數(shù)量為N,特征的數(shù)量為M,隱層神經(jīng)元的數(shù)量為nhidd,類的數(shù)量為C. 一個(gè)全連接RBF網(wǎng)絡(luò)輸入層-隱層的時(shí)間復(fù)雜度為O(Mnhidd),隱層-輸出層的時(shí)間復(fù)雜度為O(nhiddC),所有訓(xùn)練樣本的時(shí)間復(fù)雜度為O(N(Mnhidd+nhiddC)).

(13)

式中,|nodeRBF|為神經(jīng)樹(shù)中徑向基函數(shù)網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)量.

4 結(jié)論與討論

通常集成分類器處理高維數(shù)據(jù)集的能力較強(qiáng),本算法采用BABC優(yōu)化特征的分類,其次采用RBF神經(jīng)樹(shù)增強(qiáng)算法的分類性能. 在提高聚類性能的工作中,本算法主要設(shè)計(jì)了3個(gè)機(jī)制:(1)在RBF網(wǎng)絡(luò)的最后一層,RBF網(wǎng)絡(luò)僅識(shí)別一個(gè)類,這種一對(duì)多分類器(one-versus-rest,1-v-r)具有較高的分類準(zhǔn)確率. (2)在最后一層中,神經(jīng)樹(shù)多個(gè)RBF網(wǎng)絡(luò)積累的知識(shí)能夠糾正一些錯(cuò)誤分類的樣本. (3)神經(jīng)樹(shù)最終的分類結(jié)果是統(tǒng)計(jì)了若干個(gè)RBF網(wǎng)絡(luò)的結(jié)果所總結(jié)的結(jié)果,其準(zhǔn)確率應(yīng)當(dāng)較高.

首先,通過(guò)1.2小節(jié)的算法最大化徑向基函數(shù)網(wǎng)絡(luò)的準(zhǔn)確率. 然后,通過(guò)第2小節(jié)的方法選出每個(gè)特征子集的樣本集,利用選擇的樣本集合第3小節(jié)的方法訓(xùn)練以徑向基函數(shù)網(wǎng)絡(luò)為節(jié)點(diǎn)的神經(jīng)樹(shù). 最終,采用門(mén)網(wǎng)絡(luò)將連接的類簇分離,獲得最終的聚類結(jié)果.

4.1 實(shí)驗(yàn)數(shù)據(jù)集和實(shí)驗(yàn)方法

將本算法與其他5個(gè)混合特征聚類算法比較,分別為:AdaBoost ANN[12]、MOGPEF[13]、EFS-MI[14]、EFSHDD[15]、MCDCV[16]. AdaBoost ANN是一種基于人工神經(jīng)網(wǎng)絡(luò)的特征聚類算法,與本文的神經(jīng)樹(shù)策略相似;MOGPEF是一種基于多目標(biāo)遺傳算法的特征聚類算法與本文的BABC策略相似;EFS-MI、EFSHDD、MCDCV則是近期對(duì)于高維數(shù)據(jù)聚類準(zhǔn)確率和計(jì)算效率均較好的3個(gè)混合聚類算法.

采用低維數(shù)據(jù)集和高維數(shù)據(jù)集評(píng)估本算法的綜合性能,表1所示是低維數(shù)據(jù)集的一般屬性,其特征數(shù)量的范圍為4～60,低維數(shù)據(jù)集主要來(lái)自于UCI數(shù)據(jù)集. 表2所示是高維數(shù)據(jù)集的一般屬性,其特征數(shù)量范圍為10 000以上,其中Arcene、Twin gas和URL也來(lái)自于UCI數(shù)據(jù)集,Gas 2來(lái)自于文獻(xiàn)[17].

表1 低維數(shù)據(jù)集的基本屬性Table 1 Basic property of low dimensional datasets

表2 高維數(shù)據(jù)集的基本屬性Table 2 Basic property of high dimensional datasets

4.2 處理低維數(shù)據(jù)集的性能

首先評(píng)估本算法對(duì)于一般低維數(shù)據(jù)集的處理效果,為了保證實(shí)驗(yàn)結(jié)果的置信度,所有算法的分類準(zhǔn)確率結(jié)果采用十折交叉驗(yàn)證機(jī)制統(tǒng)計(jì)算法的準(zhǔn)確性. 圖4是5個(gè)集成分類算法對(duì)低維數(shù)據(jù)集的分類準(zhǔn)確率結(jié)果,圖中結(jié)果顯示本算法對(duì)于6個(gè)不同的數(shù)據(jù)集均實(shí)現(xiàn)了較高的分類準(zhǔn)確率,Adaboost ANN算法和MCDCV算法對(duì)于Glass數(shù)據(jù)集的分類準(zhǔn)確率低于50%,而MOGPEF算法、EFS-MI算法和EFSHDD算法對(duì)于Glass數(shù)據(jù)集的分類準(zhǔn)確率也遠(yuǎn)低于本算法,綜合圖中可看出,其他5個(gè)集成分類算法對(duì)于不同數(shù)據(jù)集的穩(wěn)定性較差,而本算法對(duì)于6個(gè)數(shù)據(jù)集的平均分類準(zhǔn)確率均高于90%.

分類算法的處理時(shí)間是一種重要的性能,比較了本算法與其他算法的時(shí)間效率. 圖5是6個(gè)集成分類算法對(duì)低維數(shù)據(jù)集的平均處理時(shí)間結(jié)果(10次獨(dú)立時(shí)間的平均值). 圖中結(jié)果顯示本算法對(duì)于IRIS數(shù)據(jù)集的時(shí)間高于其他兩個(gè)算法,對(duì)于Glass數(shù)據(jù)集和Breast數(shù)據(jù)集的時(shí)間則高于EFS-MI算法,對(duì)于Wine數(shù)據(jù)集、Heart數(shù)據(jù)集和WDBC數(shù)據(jù)集的時(shí)間則低于其他兩個(gè)算法. 總體而言,EFSHDD算法的處理時(shí)間較長(zhǎng),該算法需要針對(duì)每個(gè)特征計(jì)算其預(yù)測(cè)精度,該過(guò)程消耗大量的時(shí)間. 本算法通過(guò)高效的初步篩選機(jī)制過(guò)濾了大量的冗余特征,在構(gòu)架神經(jīng)樹(shù)的過(guò)程,神經(jīng)樹(shù)的每個(gè)深度對(duì)應(yīng)一個(gè)類簇,因此預(yù)測(cè)的效率較高.

圖4 低維數(shù)據(jù)集的分類準(zhǔn)確率結(jié)果Fig.4 Classification accuracy results for low-dimensional data sets

圖5 低維數(shù)據(jù)集的平均處理時(shí)間Fig.5 Average processing time for low-dimensional data sets

4.3 處理高維數(shù)據(jù)集的性能

本部分將重點(diǎn)評(píng)估本算法對(duì)于高維數(shù)據(jù)集的處理效果. 為了保證實(shí)驗(yàn)結(jié)果的置信度,所有算法的分類準(zhǔn)確率結(jié)果采用十折交叉驗(yàn)證機(jī)制統(tǒng)計(jì)算法的準(zhǔn)確性. 圖6是5個(gè)集成分類算法對(duì)高維數(shù)據(jù)集的分類準(zhǔn)確率結(jié)果,圖中結(jié)果顯示本算法對(duì)于4個(gè)不同的數(shù)據(jù)集均實(shí)現(xiàn)了較高的分類準(zhǔn)確率,4個(gè)數(shù)據(jù)集的特征數(shù)量均高于10 000,Arcene的特征數(shù)最低,6個(gè)分類算法均實(shí)現(xiàn)了可接受的準(zhǔn)確率結(jié)果. 比較Arcene、Gas 2、Twin gas 3個(gè)數(shù)據(jù)集的結(jié)果,其特征量從10 000大幅度增至480 000,本算法的分類準(zhǔn)確率從97.26%降至94.69%,依然保持較高的分類準(zhǔn)確率,URL數(shù)據(jù)集的特征量高達(dá)3 231 961,而本算法對(duì)于URL的準(zhǔn)確率降低至約80%,依然明顯高于其他5個(gè)分類算法. 觀察高維數(shù)據(jù)的實(shí)驗(yàn)結(jié)果,本算法對(duì)于特征數(shù)量大于樣本數(shù)量的數(shù)據(jù)集性能更好,原因是神經(jīng)樹(shù)森林中多個(gè)樹(shù)可能包含重復(fù)的樣本和非冗余的特征,而通過(guò)訓(xùn)練神經(jīng)樹(shù)中不同特征類簇的小樣本集合,綜合不同角度的神經(jīng)樹(shù)能夠有效地提高最終的分類準(zhǔn)確率.

高維數(shù)據(jù)分類處理的時(shí)間復(fù)雜度較高,所以時(shí)間是高維數(shù)據(jù)分類處理的關(guān)鍵性能,比較了本算法與其他算法的時(shí)間效率. 圖7是6個(gè)混合分類算法對(duì)高維數(shù)據(jù)集的平均處理時(shí)間結(jié)果(10次獨(dú)立時(shí)間的平均值). 圖中顯示6個(gè)算法對(duì)于Arcene數(shù)據(jù)集的處理時(shí)間較為接近,而隨著特征量的大幅度增加,EFS-MI算法和EFSHDD算法均表現(xiàn)出明顯地增長(zhǎng),而本算法時(shí)間的增長(zhǎng)幅度較小.

圖8 噪聲數(shù)據(jù)集的分類準(zhǔn)確率結(jié)果Fig.8 Classification accuracy results for noise data sets

4.4 噪聲魯棒性的性能

測(cè)試聚類算法對(duì)于噪聲的魯棒性,為數(shù)據(jù)集增加15%的高斯噪聲處理,本算法對(duì)每個(gè)數(shù)據(jù)集獨(dú)立地運(yùn)行20次,統(tǒng)計(jì)20次的平均結(jié)果作為最終的實(shí)驗(yàn)結(jié)果,結(jié)果如圖8所示. 結(jié)果顯示,本算法對(duì)于高斯噪聲的分類性能略低低于無(wú)噪聲的數(shù)據(jù),但是性能的衰減極小,屬于可接受的范圍.

5 結(jié)論

本文設(shè)計(jì)了混合特征聚類算法,算法的混合特征聚類算法支持多特征子集的聚類處理,能夠有效地增強(qiáng)對(duì)高維大數(shù)據(jù)的性能,對(duì)于噪聲也具有較好的魯棒性. 本算法通過(guò)高效的初步篩選機(jī)制過(guò)濾了大量的冗余特征,在構(gòu)架神經(jīng)樹(shù)的過(guò)程中,神經(jīng)樹(shù)的每個(gè)深度對(duì)應(yīng)一個(gè)類簇,因此預(yù)測(cè)的效率較高. 隨著數(shù)據(jù)特征量的大幅度增加,算法時(shí)間的增長(zhǎng)幅度較小,能夠高效地處理高維數(shù)據(jù). 未來(lái)將關(guān)注于將本算法應(yīng)用于GPU或者M(jìn)apReduce等并行計(jì)算架構(gòu),提高本算法的處理效率.