基于強(qiáng)化學(xué)習(xí)的特征選擇算法①

朱振國, 趙凱旋, 劉民康

(重慶交通大學(xué) 信息科學(xué)與工程學(xué)院, 重慶 400074)

1 引言

隨著互聯(lián)網(wǎng)、物聯(lián)網(wǎng)、傳感器等技術(shù)的快速發(fā)展,人們?cè)谏a(chǎn)和生活中產(chǎn)生了大量的數(shù)據(jù), 從這些數(shù)據(jù)中可以挖掘到有價(jià)值的信息. 然而其中很多數(shù)據(jù)呈現(xiàn)出樣本數(shù)量龐大并且數(shù)據(jù)特征維度高的特點(diǎn), 這種特點(diǎn)加大了數(shù)據(jù)挖掘的難度. 針對(duì)以上問題, 可以通過特征選擇(Feature Selection)刪除數(shù)據(jù)中無關(guān)、冗余的特征信息, 從而降低數(shù)據(jù)維度、噪音的干擾和算法的復(fù)雜度, 使模型變得簡單且易于理解, 改進(jìn)數(shù)據(jù)挖掘性能,為后期的預(yù)測(cè)分析準(zhǔn)備干凈且可理解的數(shù)據(jù). 在數(shù)據(jù)挖掘領(lǐng)域, 特征選擇已經(jīng)成為一個(gè)研究的熱點(diǎn).

目前特征選擇問題的處理方法, 根據(jù)其是否依賴后續(xù)的學(xué)習(xí)算法, 大體上可以分為過濾式(Filter)和封裝式(Wrapper)兩種方法[1]. Filter方法一般使用距離、信息、依賴性、一致性評(píng)價(jià)準(zhǔn)則來增強(qiáng)特征與類的相關(guān)性, 削弱特征之間的相關(guān)性, 從而選出更能代表原數(shù)據(jù)特點(diǎn)的特征子集. 該類方法特征選擇效率較高, 但對(duì)噪聲敏感, 在實(shí)際應(yīng)用中一般都是采用此類方法進(jìn)行特征的初步篩選. Wrapper方法和所使用的分類器關(guān)系緊密, 該方法在特征篩選過程中直接用所選特征子集來訓(xùn)練分類器, 之后用這個(gè)分類器在驗(yàn)證集上的表現(xiàn)來評(píng)價(jià)所選的特征. 因其直接用學(xué)習(xí)算法評(píng)估特征子集, 有利于關(guān)鍵特征的提取, 所以得到的特征子集有較高的分類性能, 預(yù)測(cè)準(zhǔn)確性較高;但是Wrapper方法存在時(shí)間復(fù)雜度高的問題, 不適用于超大規(guī)模的數(shù)據(jù)挖掘任務(wù). 然而隨著計(jì)算能力提高和分布式技術(shù)的成熟,在一定程度上解決了時(shí)間復(fù)雜度高的問題, Wrapper方法越發(fā)受到廣大研究者的青睞[2,3].

強(qiáng)化學(xué)習(xí)(Reinforcement Learning)是機(jī)器學(xué)習(xí)中的一個(gè)領(lǐng)域, 其基本思想是從環(huán)境中得到反饋而學(xué)習(xí),即所謂的試錯(cuò)學(xué)習(xí)方法. 在學(xué)習(xí)過程中, 智能體Agent不斷地嘗試進(jìn)行選擇, 并根據(jù)環(huán)境的反饋調(diào)整動(dòng)作的評(píng)價(jià)值, 最終智能體Agent選擇獲得最大回報(bào)的策略作為最優(yōu)策略[4]. DeepMind團(tuán)隊(duì)提出的圍棋機(jī)器人AlphaGo的算法中就包含了強(qiáng)化學(xué)習(xí)算法思想[5].

研究中發(fā)現(xiàn)傳統(tǒng)特征選擇算法存在著不足, 或是選擇的特征子集在進(jìn)行分類任務(wù)時(shí)準(zhǔn)確率較低, 或是選擇的特征子集規(guī)模較大[6]. 針對(duì)以上問題, 本文結(jié)合強(qiáng)化學(xué)習(xí)的決策能力和Wrapper特征選擇方法, 提出了一種基于強(qiáng)化學(xué)習(xí)的特征選擇方法(Reinforcement Learning for Feature Selection, RLFS), 將強(qiáng)化學(xué)習(xí)的學(xué)習(xí)和決策能力應(yīng)用于特征選擇過程中, 通過訓(xùn)練學(xué)習(xí)得到特征子集. 最后通過仿真實(shí)驗(yàn)證明了RLFS方法有良好的降維能力, 并有較高的分類準(zhǔn)確率.

2 相關(guān)理論

2.1 信息熵

信息熵將隨機(jī)變量取值的不確定性程度以數(shù)值的大小形式來衡量, 目的是描述信息含量的多少. 假設(shè)X是一個(gè)隨機(jī)變量,X取值為x的概率用p(x)表示, 則變量X的不確定程度可以表示為信息熵H(X)的形式,

由此定義分析可得, 信息熵H(X)只與變量X的概率分布有關(guān), 而與其取值無關(guān). 這表明信息熵可以一定程度上避免噪聲數(shù)據(jù)的干擾. 并且當(dāng)變量X的不確定程度較高時(shí), 則概率分布越大, 其信息熵也隨之越大,所需的信息量越多[7]. 在數(shù)據(jù)分類中每個(gè)特征f可看作變量X, 此種情況下, 特征f的信息熵就是樣本數(shù)據(jù)集相對(duì)于特征f的不純度(Impurity)的量化形式, 表示特征f包含信息量的多少,H(f)越大, 則表明取值范圍分布比較均勻, 信息純度較低;反之, 當(dāng)H(f)越小則說明特征值分布較不均勻, 可能某個(gè)或幾個(gè)值的樣本較多.如某一個(gè)特征f在樣本數(shù)據(jù)集中取值唯一時(shí),H(f)=0,此時(shí)數(shù)據(jù)集對(duì)于特征f來講是最純的, 但這也意味該特征不能為分類提供任何有用信息[8,9].

基于以上分析, 在特征選擇過程中可以通過計(jì)算每個(gè)特征的信息熵來衡量該特征所包含信息量的多少,優(yōu)先選擇信息熵較大的特征.

2.2 Pearson相關(guān)系數(shù)

Pearson相關(guān)系數(shù)反映了兩個(gè)變量間的線性相關(guān)程度, 是一種線性相關(guān)系數(shù). 假設(shè),X,Y為隨機(jī)變量, 兩個(gè)隨機(jī)變量的Pearson相關(guān)系數(shù)定義如下,

其中,分別為X,Y的均值,ρx,y的取值在[–1, 1]之間, 該值反映了兩個(gè)變量的線性相關(guān)性的強(qiáng)弱程度, 其絕對(duì)值越大說明相關(guān)性越強(qiáng). 當(dāng)其取值為–1或1時(shí), 表示兩個(gè)變量完全相關(guān), 其取值為0時(shí), 表明兩個(gè)變量不是線性相關(guān), 但可能存在其他方式的相關(guān)性. 當(dāng)兩個(gè)特征的Pearson相關(guān)系數(shù)絕對(duì)值較大時(shí), 兩特征中有冗余特征的可能性也較大[10,11].

基于以上分析, 在特征選擇過程中可以計(jì)算特征間的Pearson相關(guān)系數(shù), 剔除特征空間中相關(guān)系數(shù)較大的一對(duì)特征中的一個(gè)特征, 盡量減少冗余特征.

2.3 Q學(xué)習(xí)

強(qiáng)化學(xué)習(xí)中Q學(xué)習(xí)方法符合馬爾科夫決策過程(Markov Decision Processes, MDP). 在決策過程中,Agent可以感知周圍環(huán)境, 并可以執(zhí)行動(dòng)作列表中的任何一個(gè)動(dòng)作. 在t時(shí)刻, 當(dāng)前環(huán)境狀態(tài)為St, Agent選擇并執(zhí)行動(dòng)作at, 環(huán)境狀態(tài)則由St轉(zhuǎn)變?yōu)镾t+1, 同時(shí)反饋收益R(St,at)給Agent, 智能體Agent一直重復(fù)以上過程, 直到訓(xùn)練學(xué)習(xí)過程結(jié)束. Q學(xué)習(xí)算法中用動(dòng)作評(píng)價(jià)函數(shù)Q(St,at)來表示在狀態(tài)St時(shí)Agent選擇動(dòng)作at后所得到的最大累計(jì)回報(bào), 此值是由Agent選擇并執(zhí)行動(dòng)作后的即時(shí)收益與之后周期執(zhí)行最優(yōu)策略所得到的值, 其中Q(St,at)的值可用公式表示為:

其中,a為動(dòng)作列表中任一動(dòng)作, 常量參數(shù)γ(0≤γ≤1)稱作折扣系數(shù). 在Agent訓(xùn)練學(xué)習(xí)過程中, 總是選擇所對(duì)應(yīng)的狀態(tài)擁有最大Q值的動(dòng)作, 然后據(jù)此策略進(jìn)行迭代訓(xùn)練. 經(jīng)過多次訓(xùn)練學(xué)習(xí), 存儲(chǔ)Q值的Q表不斷更新, 以上即是Q學(xué)習(xí)算法的訓(xùn)練學(xué)習(xí)過程[12,13].

為了讓Q學(xué)習(xí)在適當(dāng)?shù)臅r(shí)刻收斂, 在公式中加入了適當(dāng)?shù)膶W(xué)習(xí)率. 當(dāng)引入學(xué)習(xí)率α 后,Q(St,at)表示為:

其中, α (0＜α＜1)是控制Q學(xué)習(xí)算法收斂的學(xué)習(xí)率,γ(0≤γ≤1)為折扣系數(shù).

3 RLFS算法實(shí)現(xiàn)

本文所提出的RLFS算法, 將Q學(xué)習(xí)方法應(yīng)用于特征選擇過程中. 定義初始特征子集為空集, 動(dòng)作列表中定義了添加和刪除兩個(gè)動(dòng)作, 分別表示添加一個(gè)特征和刪除一個(gè)特征操作. 結(jié)合Wrapper特征選擇方法,使用高斯貝葉斯分類器的在當(dāng)前狀態(tài)(特征子集)下的分類準(zhǔn)確率作為即時(shí)收益. 具體方法如圖1所示.

圖1 RLFS算法示意圖

其中步驟A到F所代表的處理過程如下:

A) 數(shù)據(jù)預(yù)處理, 包括對(duì)原始數(shù)據(jù)集進(jìn)行歸一化和離散化處理, 得到訓(xùn)練數(shù)據(jù).

B) 計(jì)算每個(gè)特征的信息熵和信息熵均值, 并將特征信息熵高于信息熵均值的特征記錄在信息熵表.

C) 計(jì)算每兩個(gè)特征Pearson相關(guān)系數(shù)以及Pearson相關(guān)系數(shù)的均值, 將高于Pearson相關(guān)系數(shù)均值的特征對(duì)記錄在Pearson表.

D) 此步驟為Q學(xué)習(xí)算法中Agent進(jìn)行迭代訓(xùn)練學(xué)習(xí)并逐步進(jìn)行決策的核心過程. 將訓(xùn)練數(shù)據(jù)和Pearson表以及信息熵表代入Agent, Agent根據(jù)添加和刪除特征的動(dòng)作所帶來的不同收益作出決策.

E) 當(dāng)Agent訓(xùn)練學(xué)習(xí)完成后輸出Q表, 通過對(duì)Q表的分析得到經(jīng)過RLFS算法選擇后的特征子集.

根據(jù)以上算法流程, 給出RLFS的算法步驟. 假設(shè)原始數(shù)據(jù)集為X=(Xij)N×D, 代表N個(gè)樣本D個(gè)特征, 則樣本的類別向量為C=(ci)N×1, 樣本向量為 (x1,x2, …,xN)T, 特征向量為(f1,f2, …,fD). 將RLFS算法思想總結(jié)為下表所示, 并有以下定義.

1)S是經(jīng)RLFS算法選擇到的最優(yōu)特征子集;

2)T為當(dāng)前特征子集, 其表示Agent在某時(shí)刻已經(jīng)選擇特征的集合;

3)H為候選特征子集, 其表示未被選入T中的特征集合;

4) 將選中要添加的特征稱為fadd, 將選中要?jiǎng)h除的特征稱為fdel;

5) 其中,T←T∪{fadd}表示將T與特征fadd取并集的結(jié)果賦值給T,H←H{fadd}表示將從H中刪除特征fadd的結(jié)果賦值給H.

RLFS算法主要步驟輸入:數(shù)據(jù)集X

輸出:最優(yōu)特征子集S

1) 初始化當(dāng)前特征子集T=?, 候選特征集合為H={f1,f2, …,fD}.

2) 計(jì)算每個(gè)特征的信息熵以及信息熵均值, 將高于信息熵均值的特征記入HS.

3) 計(jì)算每兩個(gè)特征間的Pearson相關(guān)系數(shù)以及Pearson相關(guān)系數(shù)的均值, 將高于均值的特征記入PS.

4) 當(dāng)T= ?時(shí), 隨機(jī)添加一個(gè)特征fadd(fadd∈H),T←T∪{fadd},H←H{fadd}.

5) 從H∩HS中隨機(jī)選擇一個(gè)特征fadd, 計(jì)算特征子集T∪{fadd}分類準(zhǔn)確率記為Radd. 通過查詢PS找到T中特征間相關(guān)系數(shù)中較大的幾對(duì)特征, 隨機(jī)選擇幾對(duì)特征中的一個(gè)特征fdel, 計(jì)算特征子集T{fdel}分類準(zhǔn)確率記為Rdel, 執(zhí)行Radd和Rdel中值較大的那個(gè)動(dòng)作當(dāng)作此輪決策, 即

根據(jù)公式(4)計(jì)算Q值, 并更新Q表.

6) 判斷是否滿足終止條件, 若滿足則停止并通過Q表輸出最大Q值所對(duì)應(yīng)的特征子集S, 不滿足則重復(fù)步驟 4)–6).

4 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果比較

4.1 實(shí)驗(yàn)數(shù)據(jù)

本文選用的數(shù)據(jù)集是UCI Machine Learning Repository[14]. 在數(shù)據(jù)挖掘等相關(guān)領(lǐng)域中, 常用該數(shù)據(jù)集驗(yàn)證算法的性能, 現(xiàn)已經(jīng)成為該領(lǐng)域公認(rèn)的標(biāo)準(zhǔn)數(shù)據(jù)集. 實(shí)驗(yàn)部分主要使用了其中四個(gè)數(shù)據(jù)集. 各數(shù)據(jù)集具體的描述信息見表1.

表1 實(shí)驗(yàn)數(shù)據(jù)描述

4.2 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證RLFS算法的有效性, 從Filter、Wrapper方法中選擇了3個(gè)經(jīng)典特征選擇算法[6]進(jìn)行對(duì)比, 基于相互關(guān)系度量的特征選擇算法FCBF、基于支持向量機(jī)的遞歸消除方法SVM-RFE、基于L2正則化的SVM特征選擇算法SVM-L2. 以特征選擇數(shù)量和特征子集的分類準(zhǔn)確率作為評(píng)價(jià)指標(biāo)進(jìn)行了兩個(gè)對(duì)比實(shí)驗(yàn).

4.3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)1. 以選擇的特征數(shù)量作為評(píng)價(jià)標(biāo)準(zhǔn)進(jìn)行對(duì)比.

通過RLFS、FCBF、SVM-RFE、SVM-L2算法所選取的特征數(shù)量信息見表2. 表中Raw列表示數(shù)據(jù)集原始特征的數(shù)量. 此外, Average行統(tǒng)計(jì)了各算法在每個(gè)數(shù)據(jù)集所選特征數(shù)量的均值.

表2 各算法選擇的特征數(shù)量

由表2中的數(shù)據(jù)對(duì)比分析可得, 這五種算法都可以有效地減少特征數(shù)量. 觀察各算法在數(shù)據(jù)集所選特征數(shù)量的均值, 可以發(fā)現(xiàn)FCBF和SVM-L2算法的特征降維效果最為明顯, 而基于Wrapper的兩種特征選擇算法SVM-RFE、RLFS特征降維水平相對(duì)較弱, 但RLFS算法的降維能力高于經(jīng)典的SVM-RFE算法.

實(shí)驗(yàn)2. 以特征選擇后特征子集的分類準(zhǔn)確率作為評(píng)價(jià)指標(biāo)進(jìn)行對(duì)比.

為了減少在單一分類器上表現(xiàn)過好或過差而對(duì)實(shí)驗(yàn)分析產(chǎn)生影響, 在實(shí)驗(yàn)中采用KNN(K近鄰)、LSVM(線性支持向量機(jī))、樸素貝葉斯、決策樹四個(gè)經(jīng)典分類器進(jìn)行驗(yàn)證. 為了減少過擬合對(duì)實(shí)驗(yàn)結(jié)果的影響, 實(shí)驗(yàn)中采用10折交叉驗(yàn)證的平均分類精度的值來評(píng)價(jià)特征子集優(yōu)劣. 實(shí)驗(yàn)結(jié)果記錄于表3至表6中,其中KNN算法中參數(shù)K取值為10. 表中數(shù)值為10折交叉驗(yàn)證分類準(zhǔn)確率均值, 括號(hào)內(nèi)為標(biāo)準(zhǔn)差.

表3 不同特征選擇算法在KNN分類器下分類準(zhǔn)確度對(duì)比(單位:%)

表4 不同特征選擇算法在LSVM分類器下分類準(zhǔn)確度對(duì)比(單位:%)

通過表3到表6, 分析可得以下幾點(diǎn):

1) 通過對(duì)比4種特征選擇算法在不同分類器下平均分類準(zhǔn)確度, 可以看出本文提出的RLFS算法在不同的數(shù)據(jù)集上均有較好的表現(xiàn), 算法平均分類準(zhǔn)確度較高.

表5 不同特征選擇算法在樸素貝葉斯分類器下分類準(zhǔn)確度對(duì)比(單位:%)

表6 不同特征選擇算法在決策樹分類器下分類準(zhǔn)確度對(duì)比(單位:%)

2) RLFS算法在少數(shù)情況中表現(xiàn)不如其它算法, 如在LSVM分類器下的Iono數(shù)據(jù)集上準(zhǔn)確率低于SVM-L2, 在樸素貝葉斯分類器下的Wine數(shù)據(jù)集上準(zhǔn)確率低于SVM-RFE, 但相差較小, 而在其余情況均高于其它算法.

3) 在某些分類器下的數(shù)據(jù)集上, 經(jīng)特征選擇算法找到的特征子集分類準(zhǔn)確率低于原始特征, 例如在線性支持向量機(jī)分類器上, 所有算法不如原始特征分類準(zhǔn)確率高, 但偏差不大. 這在現(xiàn)實(shí)中是可能出現(xiàn)的, 因?yàn)樘卣鬟x擇的目標(biāo)有兩點(diǎn), 其一是刪除不相關(guān)特征和冗余特征;其二是找出關(guān)鍵特征縮減特征數(shù)目, 提高預(yù)測(cè)準(zhǔn)確率. 因此犧牲較小的分類準(zhǔn)確率得到特征數(shù)目較少的優(yōu)質(zhì)數(shù)據(jù)也是可行的.

綜合實(shí)驗(yàn)1和實(shí)驗(yàn)2數(shù)據(jù)可知, 本文提出的特征選擇算法可以明顯減少特征數(shù)目, 并在此基礎(chǔ)上有較高的分類準(zhǔn)確率, 在進(jìn)行實(shí)驗(yàn)的四個(gè)數(shù)據(jù)集上本文算法的平均分類準(zhǔn)確率均高于FCBF、SVM-RFE、SVM-L2算法.

5 總結(jié)

結(jié)合Wrapper特征選擇方法, 本文提出了基于強(qiáng)化學(xué)習(xí)的特征選擇算法(RLFS), 通過智能體訓(xùn)練學(xué)習(xí),以最大化收益的方式自主決策進(jìn)行特征選擇得到特征子集, 此算法在公開的四個(gè)UCI數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn), 通過與其它特征選擇算法進(jìn)行對(duì)比實(shí)驗(yàn), 發(fā)現(xiàn)本算法能夠選擇較少的特征并獲得較高的分類準(zhǔn)確率.