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

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

1 引言

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

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

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

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

本文提出了一種基于廣義重要度和runner-root算法的特征選擇算法，選用runner-root算法做搜索策略，屬性子集的廣義重要度和屬性子集的大小作為評價準(zhǔn)則。廣義重要度的計算適于連續(xù)型屬性值，解決了經(jīng)典粗糙集對數(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對應(yīng)決策di的屬性值子區(qū)間，如果有a(di)∩a(dj)=?,i≠j,j=1,2,…,r(d),則U/a=U/d成立。其中，U是所有對象組成的論域；C是條件屬性集；D是決策屬性；V是所有屬性的值域；f:U×C∪D→V是一個信息函數(shù)，為每個對象的每個屬性賦予一個信息值。

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

定義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對應(yīng)決策值為di的集合與屬性子集B對應(yīng)決策值為dj的集合的交集部分;maxcross(B(d))?V表示屬性集合B對應(yīng)兩兩不同決策值的屬性子集的交集所包圍的最大區(qū)間。

2.2 runner-root算法

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

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

minf(x):xl≤x≤xu

(3)

(4)

(5)

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

(6)

(7)

(8)

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

(9)

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

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

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

(10)

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

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

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

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

(11)

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

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

3 特征選擇

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

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

3.2 特征選擇算法

3.2.1 算法設(shè)計

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

(12)

sigmoid函數(shù)也叫Logistic函數(shù)，其取值為(0,1)，可以實現(xiàn)將一個實數(shù)映射到0和1，sigmoid函數(shù)連續(xù)可導(dǎo)，導(dǎo)數(shù)形式簡單，單調(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]的一個隨機(jī)值。

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

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

(14)

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

(4)輪盤賭方法。

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

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

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

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

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

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

Table 1 Parameters of runner-root algorithm

(6)分類器KNN。

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

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

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

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

4 實驗結(jié)果及分析

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

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

Table 2 Basic information about dataset

Figure 2 Bar chart of the contrast experiment results

第1個實驗的設(shè)置是把所有的數(shù)據(jù)全部輸入KNN分類器模型，十折交叉驗證結(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個實驗用屬性的廣義重要度進(jìn)行特征選擇，這種方法屬于過濾法，在特征選擇過程中并不涉及分類。這種評價準(zhǔn)則是對單個屬性進(jìn)行評價，沒有考慮屬性間的相互作用。這種方法對分類器的分類貢獻(xiàn)是不確定的，如在Glass數(shù)據(jù)集上的分類效果不如在Wine數(shù)據(jù)集上的分類效果。實驗中對數(shù)據(jù)進(jìn)行了特征選擇，實驗選出的特征子集輸入分類器，分類效果總體得到了改善，在Iris、Glass和Wine數(shù)據(jù)集上的分類準(zhǔn)確率分別為0.953 333 33，0.728 632 44和0.818 627 45。

第3個實驗是基于廣義重要度和runner-root算法的特征選擇，選出特征子集輸入分類器，十折交叉驗證得到的準(zhǔn)確率在3組實驗中是最高的，也是相對穩(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。

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

5 結(jié)束語

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

Table 3 Results comparison of GIFS and GI-RRFS