吳尚智，徐丹丹，王旭文，夏 寧

(西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,甘肅 蘭州 730070)

1 引言

當(dāng)今是發(fā)展迅猛的大數(shù)據(jù)時(shí)代，用于訓(xùn)練學(xué)習(xí)器的數(shù)據(jù)中，冗余和噪聲數(shù)據(jù)不僅增加了數(shù)據(jù)分析的時(shí)間復(fù)雜度，還會(huì)降低結(jié)果的準(zhǔn)確性。特征選擇是一種降低數(shù)據(jù)維度的方法，能夠從原始特征集中選出有效的特征。特征選擇作為一種有效的數(shù)據(jù)處理方式，成為機(jī)器學(xué)習(xí)、模式識(shí)別和數(shù)據(jù)挖掘等領(lǐng)域的熱門課題。

國內(nèi)外學(xué)者對(duì)特征選擇方法的研究主要有2個(gè)方向[1]：確定特征子集的搜索策略和特征子集的評(píng)價(jià)準(zhǔn)則。搜索策略分為3種：完全搜索、啟發(fā)式搜索和隨機(jī)搜索[2]。完全搜索能夠求出最優(yōu)特征子集，但數(shù)據(jù)樣本空間大、數(shù)據(jù)維度高時(shí)，需消耗大量時(shí)間，不適于處理大數(shù)據(jù)集；啟發(fā)式搜索是在搜索過程中依某種規(guī)則不斷對(duì)當(dāng)前特征子集添加或者刪除特征，從而獲得優(yōu)化的特征子集，該策略較容易實(shí)現(xiàn)，計(jì)算復(fù)雜度相對(duì)較小，但容易陷入局部最優(yōu)；隨機(jī)搜索由某個(gè)隨機(jī)產(chǎn)生的候選特征子集開始，按照一定的啟發(fā)式規(guī)則向全局最優(yōu)解逼近，但其也無法保證每次都得到最優(yōu)特征子集。常見的特征子集評(píng)價(jià)方法有過濾(Filter)法、封裝(Wrapper)法和嵌入(Embedded)法[3]。過濾法與后續(xù)學(xué)習(xí)器無關(guān)，只是針對(duì)特征的統(tǒng)計(jì)學(xué)特性進(jìn)行篩選，按照發(fā)散性或者相關(guān)性對(duì)各個(gè)特征進(jìn)行評(píng)分，通過設(shè)定閾值來進(jìn)行特征選擇，該方法沒有考慮到特征之間的關(guān)聯(lián)作用，可能會(huì)誤刪有用的特征；封裝法直接把學(xué)習(xí)器的性能作為特征子集的評(píng)價(jià)準(zhǔn)則，最終其特征選擇的效果比過濾法的好，但是多次訓(xùn)練學(xué)習(xí)器，時(shí)間復(fù)雜度高，不適于直接用于大數(shù)據(jù)降維；嵌入法用模型進(jìn)行訓(xùn)練，得到各個(gè)特征的權(quán)值系數(shù)，根據(jù)系數(shù)從大到小選擇特征，類似于過濾法，其區(qū)別在于通過訓(xùn)練來確定特征的重要性。

粗糙集理論是波蘭科學(xué)家Pawlak教授[4]于1982年提出的，是一種數(shù)學(xué)分析處理理論，用來研究模糊和不確定的數(shù)據(jù)，并從中發(fā)現(xiàn)隱含的知識(shí)，揭示潛在的規(guī)律。基于粗糙集的特征選擇(屬性約簡(jiǎn))，是粗糙集理論的核心內(nèi)容之一。經(jīng)典粗糙集理論建立在等價(jià)關(guān)系的基礎(chǔ)上，所處理的值是離散值?，F(xiàn)實(shí)中也廣泛存在連續(xù)型取值的屬性，如身高、體重等，經(jīng)典粗糙集處理該類數(shù)值的通常做法是將連續(xù)型數(shù)值離散化，離散化的處理會(huì)導(dǎo)致信息損失，實(shí)域粗糙集模型可以解決此問題。實(shí)域粗糙集模型是在屬性廣義重要度[5]度量準(zhǔn)則下進(jìn)行的擴(kuò)展。利用粗糙集進(jìn)行特征選擇，為確保得到最優(yōu)子集需要遍歷整個(gè)空間，計(jì)算量大，時(shí)間復(fù)雜度高，不適于處理大數(shù)據(jù)集。在特征選擇研究過程中，涌現(xiàn)出許多智能優(yōu)化算法，如PSO算法[6,7]、蟻群算法[8,9]和和聲搜索算法[10]等，這些算法屬于啟發(fā)式隨機(jī)搜索方法，近似人類解決問題的思想，利用問題的啟發(fā)性，引導(dǎo)搜索過程，縮小搜索范圍，為聚合優(yōu)化、知識(shí)發(fā)現(xiàn)和NP難問題提供了新的解決方案。將智能優(yōu)化算法應(yīng)用于特征選擇是一個(gè)不錯(cuò)的方法，兩者優(yōu)勢(shì)互補(bǔ)，特征選擇能夠朝著特征子集分類能力最強(qiáng)、基數(shù)最少的方向前進(jìn)，不斷逼近全局最優(yōu)解。

runner-root算法是伊朗贊詹大學(xué)的Merrikh-Bayat[11]為了解決單峰值函數(shù)和多峰值函數(shù)的優(yōu)化問題，受到吊蘭和虎尾草等植物的繁殖方式的啟發(fā)而提出的一種智能優(yōu)化算法。runner-root算法在不滿足全局搜索的條件下會(huì)進(jìn)行多次范圍不一致的局部搜索，探索開發(fā)能力強(qiáng)，適合用來進(jìn)行特征選擇。Ibrahim等[12]基于鄰域粗糙集和runner-root算法成功地完成了對(duì)特征選擇的研究。

本文提出了一種基于廣義重要度和runner-root算法的特征選擇算法，選用runner-root算法做搜索策略，屬性子集的廣義重要度和屬性子集的大小作為評(píng)價(jià)準(zhǔn)則。廣義重要度的計(jì)算適于連續(xù)型屬性值，解決了經(jīng)典粗糙集對(duì)數(shù)據(jù)離散化處理造成的信息缺失，影響處理結(jié)果的問題。

2 理論基礎(chǔ)

2.1 廣義重要度

定理1給定決策系統(tǒng)S=(U,C∪D,V,f),U/D={d1,d2,…,dr(d)},?a∈C,設(shè)a(di)?V表示屬性a對(duì)應(yīng)決策di的屬性值子區(qū)間，如果有a(di)∩a(dj)=?,i≠j,j=1,2,…,r(d),則U/a=U/d成立。其中，U是所有對(duì)象組成的論域；C是條件屬性集；D是決策屬性；V是所有屬性的值域；f:U×C∪D→V是一個(gè)信息函數(shù)，為每個(gè)對(duì)象的每個(gè)屬性賦予一個(gè)信息值。

定理1說明，如果一個(gè)屬性對(duì)應(yīng)不同的決策值，且屬性值區(qū)間互不相交，那么這個(gè)屬性可以劃分整個(gè)空間，和決策屬性的劃分一致。對(duì)于某一個(gè)屬性，各類對(duì)應(yīng)的屬性值區(qū)間相差越大，越能根據(jù)這個(gè)屬性進(jìn)行分類，因此該屬性也越重要；同樣，各類對(duì)應(yīng)的屬性值區(qū)間相差不大，那么該屬性的分類能力就越弱，需要結(jié)合其他屬性對(duì)空間進(jìn)行分類。廣義重要度是指對(duì)全局的決策能力，而非對(duì)確定性決策元素的影響程度。

定義1(屬性的廣義重要度) 給定決策系統(tǒng)S={U,C∪D,V,f},U/D={d1,d2,…,dr(d)},?a∈C，定義屬性a的廣義重要度如式(1)所示:

(1)

定義2(屬性子集的廣義重要度) 給定決策系統(tǒng)S={U,C∪D,V,f},U/D={d1,d2,…,dr(d)},?B?C，則屬性子集B的廣義重要度為:

(2)

其中，B(di)∩B(dj)?V表示屬性子集B對(duì)應(yīng)決策值為di的集合與屬性子集B對(duì)應(yīng)決策值為dj的集合的交集部分;maxcross(B(d))?V表示屬性集合B對(duì)應(yīng)兩兩不同決策值的屬性子集的交集所包圍的最大區(qū)間。

2.2 runner-root算法

Merrikh-Bayat提出的元啟發(fā)式智能runner-root算法,把問題域內(nèi)的尋優(yōu)過程類比成草莓和吊蘭等植物的繁殖過程，即探索水和礦物質(zhì)的過程。草莓、吊蘭和虎尾草等植物的匍匐莖(吊蘭是匍匐枝，原理一樣)向外延伸，匍匐莖的節(jié)間會(huì)生根，生根后便會(huì)形成新的植株，只要具備水和礦物質(zhì)等生存條件，它們的生長(zhǎng)空間是不受限制的?；诖朔敝尺^程，Merrikh-Bayat抽象出3種植物器官:匍匐莖(用于全局搜索)、根和根毛(用于局部搜索)，將他們作為尋優(yōu)工具應(yīng)用到算法中去。

假設(shè)需優(yōu)化的函數(shù)是f(x)，x∈RD，f(x)是一個(gè)有著D個(gè)變量[x1,x2,…,xD]的多元函數(shù),優(yōu)化問題是求這個(gè)多元函數(shù)f(x)的最小值，約束條件為xl≤x≤xu。

minf(x):xl≤x≤xu

(3)

(4)

(5)

其中，rk是由[-0.5,0.5]隨機(jī)生成的D個(gè)浮點(diǎn)數(shù)組成的向量，控制匍匐莖延伸的方向。drunner是一次迭代中母本植物到子代植物的最大距離，為了避免母本植物一直陷入局部搜索，得到的是局部最優(yōu)解，drunner的值要設(shè)置得大一些。a是一個(gè)控制選擇的正實(shí)數(shù)，1/a的值等于適應(yīng)度最佳樣本的值。

(6)

(7)

(8)

式(5)是匍匐莖不斷生成子代植物(尋找礦物質(zhì)和水資源)的過程(全局搜索)，判斷是否一直進(jìn)行全局搜索的條件是式(9)，只要滿足式(9)的條件，種群就會(huì)一直進(jìn)行全局搜索。

(9)

其中，tol為控制搜索方式的臨界值。當(dāng)結(jié)果不滿足式(9)時(shí)，意味著目前通過全局搜索暫時(shí)找不到更好的解(礦物質(zhì)和水資源)，這時(shí)進(jìn)入局部搜索。局部搜索是對(duì)當(dāng)前迭代中適應(yīng)度最高的植物實(shí)體xdaughter_best(i)的第k項(xiàng)(即目前最優(yōu)解向量x中的第k維)進(jìn)行改造。局部搜索有2個(gè)步驟:大步長(zhǎng)搜索和小步長(zhǎng)搜索。大步長(zhǎng)搜索如式(10)所示：

xchanged,k=diag{1,1,…,1,1+

drunnernk,1,…,1}×xdaughter_best(i)

(10)

其中，nk(k=1,2,3,…,D)是一個(gè)服從正態(tài)分布的隨機(jī)數(shù),diag{1,1,…,1,1+drunnernk,1,…,1}是一個(gè)對(duì)角矩陣。從k=1開始，對(duì)最佳植物xdaughter_best(i)的第k項(xiàng)進(jìn)行改造，并判斷改造后的向量能否使目標(biāo)函數(shù)f(x)進(jìn)一步優(yōu)化，如果滿足f(xchanged,k)

局部搜索里的小步長(zhǎng)搜索如式(11)所示：

xchanged,k=diag{1,1,…,1,1+

drootrk,1,…,1}×xdaughter_best(i)

(11)

2個(gè)改造過程都是一樣的，都是判斷改造后的向量能否替代目前的最優(yōu)解向量，從而使f(x)獲得更小的值，rk(k=1,2,3,…,D)和nk都是一個(gè)服從正態(tài)分布的隨機(jī)數(shù)，2個(gè)公式中唯一不同的是droot的值比drunner的值小很多。

runner-root算法中如果式(9)一直不滿足，就無法跳出局部搜索，會(huì)陷入局部最優(yōu)，因此設(shè)置一個(gè)變量stall_count來進(jìn)行局部搜索的控制，當(dāng)stall_count超過設(shè)定的局部搜索的最大迭代次數(shù)stall_max時(shí)，算法重啟。

3 特征選擇

3.1 基于屬性廣義重要度的特征選擇

計(jì)算每個(gè)屬性的廣義重要度σg(a)，設(shè)定一個(gè)閾值θ，如果σg(a)≥θ，選擇該特征;如果σg(a)<θ，過濾掉該特征。σg(a)值越大，代表該屬性對(duì)全局的分類能力越強(qiáng)?；趯傩詮V義重要度有2個(gè)缺點(diǎn)：一是過濾掉的屬性可能和其他屬性組成的屬性子集對(duì)全局的劃分能力很強(qiáng)；二是θ值的大小不好確定。廣義重要度的取值為[0,1]，如果θ值過大，會(huì)出現(xiàn)過濾掉所有特征的情形，單個(gè)特征對(duì)全局的分類能力是有限的，高維度屬性的數(shù)據(jù)集中很少出現(xiàn)一個(gè)屬性決定全局分類能力的情況；如果θ值過小，去除不了任何特征，分類能力也無法提高。例如,在Wine數(shù)據(jù)集上，設(shè)置θ=0.7，則會(huì)過濾掉所有特征，設(shè)置θ=0.1并未過濾掉任何特征，且分類準(zhǔn)確率不如設(shè)置θ=0.2時(shí)的情況。因此，本文實(shí)驗(yàn)中，合理地設(shè)置參數(shù)θ=0.5。

3.2 特征選擇算法

3.2.1 算法設(shè)計(jì)

(1)連續(xù)屬性二值化轉(zhuǎn)換函數(shù)sigmoid函數(shù)，如式(12)所示：

(12)

sigmoid函數(shù)也叫Logistic函數(shù)，其取值為(0,1)，可以實(shí)現(xiàn)將一個(gè)實(shí)數(shù)映射到0和1，sigmoid函數(shù)連續(xù)可導(dǎo)，導(dǎo)數(shù)形式簡(jiǎn)單，單調(diào)遞增，函數(shù)值恰好可以解釋為屬于0或者1的概率，如圖1所示。

Figure 1 sigmoid function

(2)連續(xù)型屬性值離散化。

特征選擇問題是離散優(yōu)化問題，連續(xù)型數(shù)據(jù)處理完后通過sigmoid函數(shù)二值化，0代表不選擇該特征，1代表選擇該特征,如式(13)所示：

(13)

其中，臨界值δ是[0,1]的一個(gè)隨機(jī)值。

(3)適應(yīng)度函數(shù)。

該適應(yīng)度函數(shù)由屬性子集的廣義重要度和特征子集長(zhǎng)度構(gòu)成，如式(14)所示：

(14)

其中，σg(B)是所選特征子集B的廣義重要度，σg(B)越大，說明對(duì)決策分類的幫助越大。|R|是挑選的特征子集長(zhǎng)度，|C′|是候選特征集長(zhǎng)度。α和1-α是屬性子集的廣義重要度和特征子集長(zhǎng)度的權(quán)重，特征選擇的目的是在保證分類能力不變的情況下減少條件屬性個(gè)數(shù)，屬性的分類能力占主要，所以廣義重要度的權(quán)重遠(yuǎn)大于特征子集長(zhǎng)度的權(quán)重。

(4)輪盤賭方法。

每次迭代中，生成的N個(gè)子代植物需要通過輪盤賭方法選出下一次迭代的N個(gè)母本植物。每個(gè)個(gè)體被選中的概率與其適應(yīng)度成正比。輪盤賭方法的計(jì)算步驟如下所示：

步驟2利用式(7)計(jì)算每一個(gè)個(gè)體被選擇進(jìn)入下一次迭代的概率。

步驟3利用式(8)計(jì)算累積概率。

步驟4隨機(jī)生成一個(gè)[0，1]均勻分布的隨機(jī)數(shù)r，判斷隨機(jī)數(shù)r落在哪個(gè)區(qū)間，則相應(yīng)的個(gè)體被選中,例如qk-1

(5)runner-root算法參數(shù)的設(shè)置。

參數(shù)設(shè)置如表1所示。

Table 1 Parameters of runner-root algorithm

(6)分類器KNN。

KNN(K-Nearest Neighbors)是最常用的分類算法，本文采用KNN算法對(duì)選出的特征子集進(jìn)行分類。scikit-learn是機(jī)器學(xué)習(xí)中常用的第三方模塊，對(duì)常用的機(jī)器學(xué)習(xí)，例如回歸、分類、降維和聚類等方法進(jìn)行了封裝，可以借助scikit-learn封裝好的KNN分類算法，用十折交叉驗(yàn)證進(jìn)行模型評(píng)價(jià)。

3.2.2 算法描述

基于廣義重要度和runner-root算法的特征選擇算法如算法1所示。

算法1基于廣義重要度和runner-root算法的特征選擇

輸入：DT=(U,C∪D)和各參數(shù)。

輸出：最優(yōu)特征子集。

步驟1初始化N,drunner,droot,i=1,imax,stall_count=0,stall_max,α。

(1)如果i<2,i+1，回到步驟(3)。

(2)如果i≥2且i

步驟4局部搜索是對(duì)當(dāng)前迭代狀態(tài)下?lián)碛凶罴堰m應(yīng)度的個(gè)體進(jìn)行改造，改造分2步，局部范圍大步長(zhǎng)搜索采用式(9)和局部范圍小步長(zhǎng)搜索采用式(10)，2步改造遵循的過程如下：從最佳適應(yīng)度個(gè)體的第k項(xiàng)進(jìn)行改造，k從1開始:

若滿足f(xchanged,k)>f(xdaughter_best(i))，則f(xdaughter_best(i))=f(xchanged,k)。接著k=2,3,…,D依次計(jì)算比較，完成改造。

步驟5當(dāng)i=imax時(shí)，算法結(jié)束，輸出最佳適應(yīng)度個(gè)體。

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

基于Python語言環(huán)境進(jìn)行實(shí)驗(yàn)，從UCI數(shù)據(jù)庫選取了3個(gè)數(shù)據(jù)集，數(shù)據(jù)集基本信息如表2所示。

用scikit-learn封裝好的KNN對(duì)數(shù)據(jù)集進(jìn)行分類，參數(shù)用默認(rèn)值，在此基準(zhǔn)上，用基于廣義重要度算法的特征選擇算法(GIFS)和本文提出的基于廣義重要度和runner-root算法的特征選擇算法(GI-RRFS)進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表3和圖2所示。

Table 2 Basic information about dataset

Figure 2 Bar chart of the contrast experiment results

第1個(gè)實(shí)驗(yàn)的設(shè)置是把所有的數(shù)據(jù)全部輸入KNN分類器模型，十折交叉驗(yàn)證結(jié)果顯示，Iris數(shù)據(jù)集的分類效果較好，準(zhǔn)確率達(dá)到0.946 666 66。但在Glass和Wine數(shù)據(jù)集上，分類效果不是很理想，準(zhǔn)確率分別為0.669 480 52和0.696 732 03。

第2個(gè)實(shí)驗(yàn)用屬性的廣義重要度進(jìn)行特征選擇，這種方法屬于過濾法，在特征選擇過程中并不涉及分類。這種評(píng)價(jià)準(zhǔn)則是對(duì)單個(gè)屬性進(jìn)行評(píng)價(jià)，沒有考慮屬性間的相互作用。這種方法對(duì)分類器的分類貢獻(xiàn)是不確定的，如在Glass數(shù)據(jù)集上的分類效果不如在Wine數(shù)據(jù)集上的分類效果。實(shí)驗(yàn)中對(duì)數(shù)據(jù)進(jìn)行了特征選擇，實(shí)驗(yàn)選出的特征子集輸入分類器，分類效果總體得到了改善，在Iris、Glass和Wine數(shù)據(jù)集上的分類準(zhǔn)確率分別為0.953 333 33，0.728 632 44和0.818 627 45。

第3個(gè)實(shí)驗(yàn)是基于廣義重要度和runner-root算法的特征選擇，選出特征子集輸入分類器，十折交叉驗(yàn)證得到的準(zhǔn)確率在3組實(shí)驗(yàn)中是最高的，也是相對(duì)穩(wěn)定的，在Iris數(shù)據(jù)集、Glass數(shù)據(jù)集和Wine數(shù)據(jù)集上的分類準(zhǔn)確率分別為0.966 666 67，0.882 765 44和0.852 941 18。

實(shí)驗(yàn)結(jié)果表明，利用屬性子集的廣義重要度和runner-root算法選出特征子集作為分類器的輸入，在降低數(shù)據(jù)冗余度的同時(shí)，還具有更好的分類效果。

5 結(jié)束語

本文提出的基于屬性的廣義重要度和runner-root算法的特征選擇算法具有以下特點(diǎn)：(1)屬性的廣義重要度用于連續(xù)型屬性值的計(jì)算，避免連續(xù)型屬性值離散化導(dǎo)致信息的缺失；(2)runner-root算法是一種探索勘測(cè)能力較強(qiáng)的隨機(jī)搜索算法，避免了搜索整個(gè)樣本空間，減少了算法運(yùn)行時(shí)間；(3)所選特征子集對(duì)樣本空間的劃分具有較高的準(zhǔn)確率。然而，該算法還是有其局限性，二分類情況下無法體現(xiàn)屬性對(duì)全局的劃分能力。

Table 3 Results comparison of GIFS and GI-RRFS