李校林,吳 騰,郭有慶

1(重慶郵電大學(xué) 通信與信息工程學(xué)院,重慶 400065)2(重慶郵電大學(xué) 通信新技術(shù)應(yīng)用研究中心,重慶 400065)3(重慶信科設(shè)計(jì)有限公司,重慶 401121)

1 引 言

隨著信息增長(zhǎng)速度的加快,過多的數(shù)據(jù)給人類帶來(lái)了極大的麻煩,然而,在巨大的數(shù)據(jù)體積中隱藏著大量的潛在價(jià)值和非常有用的信息[1].在統(tǒng)計(jì)學(xué)、信號(hào)處理、社交網(wǎng)絡(luò)情感分析和可視化等領(lǐng)域中,機(jī)器學(xué)習(xí)方法得到普及,數(shù)據(jù)的特征維數(shù)的提升,使得算法復(fù)雜性呈指數(shù)級(jí)上升,另外高維特征中存在許多冗余信息和噪聲信息,這些都會(huì)影響決策結(jié)果的精度,給信息處理工作帶來(lái)了巨大的挑戰(zhàn)[2].特征選擇是分類和回歸問題中一種數(shù)據(jù)降維的有效方法,能夠去除特征中對(duì)決策結(jié)果無(wú)效的信息,并且保留數(shù)據(jù)之間的聯(lián)系,用較少的特征子集使機(jī)器學(xué)習(xí)算法達(dá)到更高的分類精度[3].

目前,主流的特征選擇方法分為過濾型(filter),封裝型(wrapper)[4].過濾型方法首先利用判決指標(biāo)對(duì)特征與目標(biāo)集之間的關(guān)聯(lián)性進(jìn)行評(píng)價(jià),然后進(jìn)行排序留下前N個(gè)關(guān)聯(lián)性強(qiáng)的特征作為最優(yōu)特征子集,最后再經(jīng)過訓(xùn)練器的學(xué)習(xí),過濾型方法的特征選擇過程與訓(xùn)練學(xué)習(xí)算法之間相互獨(dú)立,因此這種算法有比較扎實(shí)的理論基礎(chǔ),計(jì)算速度快,在特征降維方面高效且擴(kuò)展性強(qiáng);缺點(diǎn)是所選特征子集沒有經(jīng)過具體學(xué)習(xí)算法的驗(yàn)證,預(yù)測(cè)或分類的準(zhǔn)確率較低[5].相對(duì)于基于判決準(zhǔn)則的過濾式方法,采用特征聚類的算法具有良好的效果.Zhou等人提出了一種高維數(shù)據(jù)集的無(wú)監(jiān)督屬性聚類算法(UACA),采用相似度系數(shù)MIC(Maximum Information)來(lái)評(píng)價(jià)每一對(duì)屬性之間的相關(guān)性,在此基礎(chǔ)上采用了最優(yōu)k-mode聚類算法[6].封裝型方法需要預(yù)設(shè)學(xué)習(xí)算法,在訓(xùn)練過程中以分類器的分類精度為判決準(zhǔn)則進(jìn)行特征選擇[7],該方法需要對(duì)所有的特征子集進(jìn)行訓(xùn)練,因此分類的準(zhǔn)確率較高,但算法的效率過低.filter方法是當(dāng)前特征選擇的一個(gè)研究熱點(diǎn),得到了廣泛的應(yīng)用.互信息是一個(gè)隨機(jī)變量中包含另一個(gè)隨機(jī)變量的信息量,具有很好的魯棒性.許多基于互信息的特征選擇算法被相繼提出,如MIFS、JMI、mRMR[8]、FCBF[9]等.這些算法都是利用互信息進(jìn)行改進(jìn)去除特征中的冗余特征,取得了更高的分類精度,但是當(dāng)數(shù)據(jù)量和特征維數(shù)過高時(shí),決策效率會(huì)變差.

以上各研究者提出的方法雖可在數(shù)據(jù)集上取得良好的實(shí)驗(yàn)效果,但只適用于特征單一的數(shù)據(jù)集,同時(shí)忽略了特征之間的相關(guān)性,特征選擇時(shí)會(huì)誤刪掉重要的特征信息,難以處理高維特征的數(shù)據(jù)集.為了解決此問題,提出一種混合式特征選擇算法NDI-RF,在特征過濾階段,在互信息的基礎(chǔ)上考慮特征之間的相關(guān)性,引入鄰域判別指數(shù)判決條件,通過圖論聚類[10]快速刪除冗余特征,保留相關(guān)特征.在封裝算法中,采用隨機(jī)森林和后項(xiàng)序列搜索的方法對(duì)特征子集進(jìn)行評(píng)估,并對(duì)隨機(jī)森林特征選擇的隨機(jī)性進(jìn)行改進(jìn),得到具有最高分類準(zhǔn)確率的最優(yōu)特征子集.

2 相關(guān)概念

2.1 鄰域判別指數(shù)相關(guān)概念

給定一個(gè)決策表[U,A,D],其中U={x1,x2,…,xn}是決策表中所有樣本對(duì)象的集合,A={a1,a2,…,an}是描述樣本的一組特征集,D是一個(gè)決策屬性集,該屬性集將樣本空間劃分為r類,U/D={D1,D2,…,Dr}.樣本空間中的相似關(guān)系可用相似矩陣RB表示,一般表示為RB=(rij)n×n,其中rij∈{0,1},i,j=1,2,…,n采用以下度量計(jì)算rij:

(1)

其中xl=[xl1,xl2,…,xls]T,l=i,j代表兩個(gè)樣本,B為屬性子集且屬性維數(shù)為s,兩個(gè)樣本的距離公式為:

(2)

閾值ε為鄰域半徑,用來(lái)控制樣本的相似度.另外,RB有兩個(gè)重要的性質(zhì):

1)自反性:?x∈U,(x,x)∈RB

定義1.給定一個(gè)決策表U,A,D,其中U={x1,x2,…,xn},B?A,ε為鄰域半徑,是特征子集B的鄰域相似關(guān)系,則B的鄰域判別指數(shù)[11]定義為:

(3)

1)如果ε1≤ε2,則Hε1(B)≥Hε2(B).

2)如果B1?B2,則Hε(B1)≤Hε(B2).

(4)

聯(lián)合判別指數(shù)代表聯(lián)合特征子集的識(shí)別能力,它隨著新的特征集的增加而增加,但不具備單調(diào)性,Hε(B1,B2)≥Hε(B1),Hε(B1,B2)≥Hε(B1)當(dāng)且僅當(dāng)B1?B2時(shí),有Hε(B1,B2)=Hε(B2).

定義3.將在B2條件下B1的條件判別指數(shù)定義為:

(5)

并且Hε(B1|B2)≥0.僅當(dāng)B1?B2時(shí),Hε(B1|B2)=0.

條件判別指數(shù)是在已知一個(gè)特征子集后,通過引入一個(gè)新的特征子集來(lái)增加判別信息,從而增加特征的識(shí)別能力.

定義4.特征子集B1,B2的相互判別指數(shù)定義為:

(6)

相互判別指數(shù)有如公式(7)所示的性質(zhì),其與鄰域判別指數(shù)和條件判別指數(shù)的關(guān)系如圖1所示.

Iε(B1;B2)=Iε(B2;B1)Iε(B1;B2)=Hε(B1)+Hε(B2)-Hε(B1,B2)

(7)

Iε(B1;B2)=Hε(B1)-Hε(B1|B2)=Hε(B2)-Hε(B2|B1)

圖1 判別指標(biāo)關(guān)系圖Fig.1 Discriminant indicator relationship diagram

2.2 特征選擇的重要依據(jù)

上述所提出的鄰域判別指標(biāo)可以用來(lái)衡量特征子集的區(qū)分能力.根據(jù)條件判別指數(shù)的定義,在所選擇的特征子集中加入一個(gè)新的特征可以增加或降低條件判別指數(shù),條件判別指數(shù)Hε(D|B)的減小反映出新特征子集的區(qū)分能力增加.因此,特征的重要性定義如下.

定義5.給定一個(gè)決策集[U,A,D],B?A,a∈A-B,特征a相對(duì)于B和D的重要程度定義為:

SI(a,B,D)=Hε(D|B)-Hε(D|B∪{a})

(8)

當(dāng)B=?時(shí),Hε(D|B)=Hε(D).特征a的重要程度取決于將a加到特征子集B后判別信息的增量.

假設(shè)特征b∈B,如果Iε(D;B)≤Iε(D;B-),則b在B中成為冗余的.如果B中的任何屬性b相對(duì)于D是不可缺少的,則稱b為依賴項(xiàng).如果B滿足以下條件,則B稱為A相對(duì)于D的約簡(jiǎn):

1)Iε(D;B)≥Iε(D;A)

2)Iε(D;B-)

(9)

3 混合式特征選擇算法

3.1 基于鄰域判別指數(shù)的特征過濾算法(NDI)

本文在考慮特征之間的交互作用的基礎(chǔ)上,提出采用鄰域判別指數(shù)作為filter模型的特征選擇判別條件,引入圖論聚類的思想的快速選擇算法,主要分為兩步:

1)利用圖論聚類的方法對(duì)特征進(jìn)行聚類;

2)從每個(gè)目標(biāo)類中選擇與目標(biāo)類密切相關(guān)的最具代表性的特征集群形成約簡(jiǎn)特征子集.考慮到大數(shù)據(jù)環(huán)境下特征維數(shù)多,為了保證特征維數(shù)約簡(jiǎn)的效率,分別在第一步和第二步中采用了最小生成樹(MST)方法和冗余窗口[12]來(lái)提高算法的效率.NDI特征過濾算法的具體步驟如下:

1)構(gòu)造完全圖.將初始特征集A={a1,a2,…,an}中的每個(gè)特征作為一個(gè)單獨(dú)的特征子集Bi,i=1,2,…,n.計(jì)算每個(gè)特征子集的鄰域判別指數(shù)Hε(Bi)作為完全圖中每個(gè)結(jié)點(diǎn)的權(quán)值;計(jì)算相互判別指數(shù)Iε(Bi;Bj)作為完全圖中每一條邊的權(quán)值.

2)生成最小生成樹.對(duì)于高維數(shù)據(jù)集生成的完全圖過于密集且各條邊交織在一起,對(duì)后續(xù)圖的剪枝操作帶來(lái)困難.本文采用Prim算法生成最小生成樹[13],使得在包含所有結(jié)點(diǎn)的情況下讓邊的權(quán)值的總和達(dá)到最小.

3)樹的剪枝.根據(jù)相互判別指數(shù)的理論可知0≤Iε(Bi;Bj)≤logn,將最小生成樹中的邊的權(quán)值滿足Iε(Bi;Bj)<δ的邊去掉,就能保證剩余的邊的兩個(gè)特征集之間有一定的相關(guān)性,形成一個(gè)特征類簇,具體思想如圖2所示.其中,δ的值要根據(jù)特征維數(shù)n具體的設(shè)定.

4)代表特征的選擇.設(shè)約簡(jiǎn)特征子集S=?,對(duì)于每一個(gè)剪枝后的特征類簇,計(jì)算每個(gè)結(jié)點(diǎn)與決策屬性集之間D的相互判別指數(shù)Iε(D;Bi),選擇使Iε(D;Bi)最大的特征Bi作為每個(gè)簇的代表特征,每個(gè)代表特征能覆蓋對(duì)應(yīng)特征類簇的大部分信息.其余的特征作為剩余特征.

5)去除冗余,生成約簡(jiǎn)特征集.根據(jù)定義5中的SI(a,B,D)判斷剩余的每個(gè)特征是否為對(duì)應(yīng)特征類簇的冗余項(xiàng)或依賴項(xiàng).若是冗余項(xiàng),則從特征子集中剔除,若是依賴項(xiàng),則加入約簡(jiǎn)特征子集S中.

圖2 圖論聚類思想Fig.2 Graph theory clustering

NDI算法的偽代碼如下：

輸入:[U,A,D]-決策表;δ-設(shè)定的閾值;ε-鄰域半徑

輸出:S-約簡(jiǎn)特征子集

//Part1:構(gòu)造完全圖G

1.fori=1 tondo

2.ai∈AasBithenB=B∪{Bi};

3.G=NULL

4.for each pair of features {Bi,Bj}∈Bdo

5. B-Correlation=Iε(Bi;Bj)

6. AddBiand/orBjtoGwith B-Correlation as the weight of the corresponding edge;

//Part2:利用Prim 算法構(gòu)造最小生成樹

7.minSpanTree=Prim(G);

8.Forest= minSpanTree

//Part3:剪枝

9.for each edgeBij∈Forestdo

10. ifIε(Bi;Bj)<δthenForest=Forest-Bij

//Part4:代表特征的選擇

11.for each treeTi∈Forestdo

//Part5:生成約簡(jiǎn)特征集S

13.S=φ

18.returnS.

為了降低特征選擇算法中去除冗余,采用冗余窗口機(jī)制.假設(shè)步驟4)生成的代表特征為F0,剩余特征為Fi(i=1,2,…,m).首先將代表特征F0壓入約簡(jiǎn)特征子集S中,并將計(jì)數(shù)器設(shè)置為1,然后計(jì)算特征F1是否為依賴項(xiàng),若是,將F1壓入S中,計(jì)數(shù)器置為2.下一步將計(jì)算F2和F3的依賴程度.冗余窗口機(jī)制可以根據(jù)S現(xiàn)有特征的個(gè)數(shù)并行計(jì)算剩余特征的依賴程度,在保證了系統(tǒng)的準(zhǔn)確性的同時(shí),提高特征維數(shù)約簡(jiǎn)的效率.

3.2 特征選擇算法

針對(duì)某些特征之間往往高度相關(guān)的數(shù)據(jù)集,諸如醫(yī)學(xué)數(shù)據(jù)、網(wǎng)絡(luò)數(shù)據(jù)、地理信息等,利用過濾式特征選擇方法并不能保證選擇出最優(yōu)的特征子集.基于wrapper特征選擇算法直接用所選的特征子集來(lái)訓(xùn)練分類器,根據(jù)分類器在數(shù)據(jù)集上的表現(xiàn)性能來(lái)評(píng)價(jià)特征子集的優(yōu)劣.在特征選擇過程中,搜索策略和評(píng)價(jià)準(zhǔn)則是最重要的因素.序列搜索能夠獲得較好結(jié)果的同時(shí)降低時(shí)間開銷,但是序列搜索基于貪心思想[14],易于收斂于局部最優(yōu)值.為了解決這類問題,采用隨機(jī)森林(RF)作為封裝器[15],與序列后項(xiàng)搜索(SBS)相結(jié)合的方式進(jìn)行進(jìn)一步的精細(xì)化特征選擇.

首先根據(jù)特征重要性度量值對(duì)特征進(jìn)行降序排序,然后對(duì)特征進(jìn)行后項(xiàng)搜索,每次迭代刪除最不重要的幾個(gè)特征進(jìn)行,逐次迭代并且計(jì)算每次迭代的分類精度,獲取分類精度最高的那次迭代所對(duì)應(yīng)的特征集作為最優(yōu)的特征選取結(jié)果.在每次迭代中采用10折交叉驗(yàn)證來(lái)計(jì)算分類準(zhǔn)確率.具體的算法步驟如下:

1)數(shù)據(jù)初始化.將原始數(shù)據(jù)集隨機(jī)分為10份,其中1份作為測(cè)試數(shù)據(jù)集,其他9份作為訓(xùn)練數(shù)據(jù)集.

2)構(gòu)建RF分類器.構(gòu)建多棵決策樹組成隨機(jī)森林對(duì)新數(shù)據(jù)進(jìn)行分類,分類結(jié)果由最終每棵樹的投票結(jié)果決定[16].為了解決傳統(tǒng)隨機(jī)森林算法在構(gòu)建決策樹的過程中選擇特征的隨機(jī)性問題所造成的分類準(zhǔn)確率兩級(jí)分化嚴(yán)重以及沒有充分考慮特征之間的關(guān)聯(lián)性.對(duì)特征排序和選擇過程進(jìn)行改進(jìn),具體步驟為:

①采用Bootstrap方法在訓(xùn)練數(shù)據(jù)集中隨機(jī)抽樣,獲得n個(gè)樣本;

③采用等比規(guī)則依次從特征子集中選取特征權(quán)重高的特征和權(quán)重低的特征組成新的特征子集.構(gòu)造決策樹,組成隨機(jī)森林,計(jì)算每個(gè)特征的重要性值,對(duì)數(shù)據(jù)集進(jìn)行分類并計(jì)算分類準(zhǔn)確率.

3)采用10折交叉驗(yàn)證計(jì)算平均分類準(zhǔn)確率.重復(fù)10次步驟2),計(jì)算10次分類的平均準(zhǔn)確率,并記錄對(duì)應(yīng)的特征子集.

4)特征刪除.根據(jù)特征重要性度量值對(duì)特征進(jìn)行降序排序,刪除最不重要的l個(gè)特征,形成新的特征子集.

5)最優(yōu)特征子集的選取.重復(fù)步驟2)～步驟4),最終選擇使分類準(zhǔn)確率最高的特征子集作為最優(yōu)特征子集.

算法的偽代碼如下:

SBS-RF算法:

輸入:約簡(jiǎn)特征子集S,其中有N個(gè)特征,原始數(shù)據(jù)集U;

輸出:驗(yàn)證集上的最大分類正確率TGMaxAcc及其對(duì)應(yīng)的特征子集TGSort;

1.初始化:讀入原始數(shù)據(jù)集,設(shè)置TGMaxAcc=0,TGSort=null;

2.fort=1,2,…,|N/l|

3.將原始數(shù)據(jù)集隨機(jī)分成10份

4.設(shè)置局部的平均分類準(zhǔn)確率MeanAcc=0

5.fori=1,2,…,10

6.初始化10次交叉驗(yàn)證中的每次迭代的正確率為Acc=0

7.在數(shù)據(jù)集T上建立RF分類器

8.在驗(yàn)證集上進(jìn)行分類

9.比較分類結(jié)果,計(jì)算分類準(zhǔn)確率Acc

10.計(jì)算平均分類準(zhǔn)確率MeanAcc=MeanAcc+Acc/10

11.對(duì)特征的重要性度量進(jìn)行降序排序

12.if(TGMaxAcc≤MeanAcc)

thenTGMaxAcc=MeanAcc

13.去掉特征重要性排序中較低的l個(gè)特征,得到新的特征集T

14.end for.

15.end for.

4 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文特征選擇算法的有效性和可行性,做了兩方面的對(duì)比試驗(yàn).1)分類準(zhǔn)確率方面,比較原始特征集、mRMR、FAST、NEREA和本文提出的NDI-RF算法所選擇出的最優(yōu)特征子集在多個(gè)分類器上的分類精度,以驗(yàn)證本文算法的有效性;2)比較了多種算法在各類數(shù)據(jù)集上所選擇的最優(yōu)特征子集的平均大小.在進(jìn)行分類性能評(píng)估時(shí)采用Na?ve Bayes分類器、SVM分類器、KNN分類器.實(shí)驗(yàn)硬件環(huán)境為Windows 10系統(tǒng),Intel core i7-6500U處理器,16G內(nèi)存.實(shí)驗(yàn)軟件環(huán)境為Matlab 2016b,Weka分類軟件.

表1 數(shù)據(jù)表信息
Table 1 Data sheet information

ID名稱特征數(shù)類別數(shù)樣本數(shù)1wine1331782zoo1771013Ionosphere3423514sonar6022085realdisp120314196elephant232213917tr12.wc313858058fqs-nowe3202256

本文所用實(shí)驗(yàn)數(shù)據(jù)集下載于UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù),各個(gè)數(shù)據(jù)集的詳細(xì)信息如表1所示.其中數(shù)據(jù)集1～4為低維小樣本數(shù)據(jù),數(shù)據(jù)集5～8為高維大樣本數(shù)據(jù).

4.1 鄰域半徑ε對(duì)特征選擇結(jié)果的影響

由于實(shí)驗(yàn)過程中需要確定鄰域半徑ε的大小對(duì)最優(yōu)特征子集的影響,本文采用SVM分類器來(lái)確定最優(yōu)特征子集的鄰域半徑ε.以數(shù)據(jù)集wine,realdisp,fqs-nowe為例,首先將數(shù)據(jù)集屬性標(biāo)準(zhǔn)化為[0,1]區(qū)間,通過在[0,1]內(nèi)調(diào)整ε的大小來(lái)確定對(duì)應(yīng)的最優(yōu)特征子集和最佳分類精度,設(shè)置ε的變化步長(zhǎng)為0.05.圖3-圖5反映了NDI-RF算法所選的最優(yōu)特征子集大小和分類精度隨ε的變化趨勢(shì).

實(shí)驗(yàn)結(jié)果表明,鄰域半徑ε的選擇對(duì)NDI-RF算法的性能有很大影響,隨著ε取值變化的不同,分類準(zhǔn)確率和最優(yōu)特征子集的大小都會(huì)發(fā)生變化.從圖3-圖5可以得出數(shù)據(jù)集1,數(shù)據(jù)集5,數(shù)據(jù)集8獲得最佳分類性能所對(duì)應(yīng)的ε值分別為0.6,0.2,0.25.按照此方法,在保證分類準(zhǔn)確率的前提下選擇最優(yōu)特征子集較小的ε為最優(yōu)鄰域半徑的取值.經(jīng)過實(shí)驗(yàn),數(shù)據(jù)集2,數(shù)據(jù)集3,數(shù)據(jù)集4,數(shù)據(jù)集6,數(shù)據(jù)集7所獲得的最優(yōu)鄰域半徑ε分別為0.45,0.3,0.6,0.55,0.3.

圖3 特征子集大小和分類準(zhǔn)確率變化趨勢(shì)(wine)Fig.3 Feature subset size and classification accuracy trend(wine)

4.2 NDI-RF算法的性能

為了比較本文提出的混合式算法NDI-RF的分類準(zhǔn)確率,分別比較了原始特征集、mRMR、FAST、NEREA等特征選擇算法選擇出來(lái)的最優(yōu)特征集在三種分類器上的分類準(zhǔn)確率,在使用KNN分類器進(jìn)行分類時(shí)取K值為3.從表2-表4可以看出NDI-RF算法在平均分類準(zhǔn)確率上明顯優(yōu)于其他算法.在低維數(shù)據(jù)集中NEREA算法的分類精度與NDI-RF相近,但在高維數(shù)據(jù)集中NDI-RF算法的性能要明顯優(yōu)于其他的特征選擇算法,這是由于NDI-RF算法在特征處理的過程中采用鄰域信息考慮了特征之間的相關(guān)性,通過圖論聚類剔除冗余特征,保留了特征與目標(biāo)類之間的關(guān)聯(lián),在訓(xùn)練封裝器階段,采用特征權(quán)重和等比分配機(jī)制克服了隨機(jī)森林分類不平穩(wěn)的問題.

圖4 特征子集大小和分類準(zhǔn)確率變化趨勢(shì)(realdisp)Fig.4 Feature subset size and classification accuracy trend(realdisp)

圖5 特征子集大小和分類準(zhǔn)確率變化趨勢(shì)(fqs-nowe)Fig.5 Feature subset size and classification accuracy trend(fqs-nowe)

表2 各算法在Na?ve Bayes分類器上分類準(zhǔn)確率對(duì)比(%)
Table 2 Comparison of classification accuracy of algorithms on Na?ve Bayes classifier(%)

ID原始特征mRMRFASTNEREANDI-RF194.3296.5896.0997.3297.05289.6087.2193.8894.5694.86378.2385.4090.5289.2190.15482.2681.9488.7592.2091.92580.0488.5689.6891.2493.02675.3482.9893.5492.7093.84772.2784.8879.9380.2088.42870.5686.2590.5688.6595.64平均值80.3386.7290.3690.7693.11

在評(píng)價(jià)NDI-RF算法選擇的最有特征子集大小方面,采用十倍交叉驗(yàn)證法統(tǒng)計(jì)每個(gè)算法所選特征子集的平均大小,如圖6和圖7所示.從圖中可以看出,NDI-RF算法在低維數(shù)據(jù)集上所選擇的特征子集大小與其他算法相差不大,在wine數(shù)據(jù)集上略高于NEREA算法,在Ionosphere數(shù)據(jù)集上略高于FAST算法.在高維特征的選擇上,NDI-RF算法均小于其他算法所選的特征子集大小,能夠有效的降低特征維數(shù),體現(xiàn)了NDI-RF算法處理高維數(shù)據(jù)的優(yōu)越性.

表3 各算法在SVM分類器上分類準(zhǔn)確率對(duì)比(%)
Table 3 Comparison of classification accuracy of algorithms on SVM(%)

ID原始特征mRMRFASTNEREANDI-RF190.5094.5894.0996.3298.25277.3088.2490.3292.5695.70380.5388.4094.5291.4193.52478.2691.9492.7591.2094.95576.0485.5689.6489.2490.02678.6490.4092.6494.5695.65776.4585.4589.9390.2096.42870.5682.4589.1294.6593.64平均值78.5388.3791.6292.5194.76

圖6 低維數(shù)據(jù)集上所選擇的特征子集平均大小Fig.6 Average size of feature subsets selected on low-dimensional data sets

圖7 高維數(shù)據(jù)集上所選擇的特征子集平均大小Fig.7 Average size of feature subsets selected on high-dimensional data sets

表4 各算法在3NN分類器上分類準(zhǔn)確率對(duì)比(%)Table 4 Comparison of classification accuracy of algorithms on 3NN(%)

5 結(jié)束語(yǔ)

特征選擇是解決分類和回歸問題中的一種重要的數(shù)據(jù)預(yù)處理技術(shù).目前大部分特征選擇方法僅僅是刪除冗余和對(duì)決策結(jié)果無(wú)關(guān)的屬性信息,缺乏對(duì)特征之間相關(guān)性的考慮,沒有進(jìn)一步的精細(xì)化特征子集的性能.為了解決此問題,提出一種融合圖論聚類方法和隨機(jī)森林選擇相結(jié)合的混合式特征選擇算法.在聚類過程中采用鄰域判別指數(shù)來(lái)確定特征之間的相關(guān)性,保留相關(guān)特征,剔除冗余特征.在訓(xùn)練封裝器階段,采用隨機(jī)森林和后項(xiàng)序列搜索方法平衡算法的收斂值,對(duì)所選特征子集的具體分類性能進(jìn)行準(zhǔn)確評(píng)估,最終選擇最高分類準(zhǔn)確率所對(duì)應(yīng)的特征子集為本次選擇的最優(yōu)特征子集.最終在多個(gè)UCI 數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法的有效性,在低維數(shù)據(jù)和高維數(shù)據(jù)中都獲得了較高的分類準(zhǔn)確率,在最優(yōu)特征子集的選擇方面,NDI-RF算法體現(xiàn)出更好的性能.