邱海峰,何振峰

(福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,福州 350116)

1 引言

作為一種重要的降維技術(shù),特征選擇是一個(gè)熱門的研究課題,現(xiàn)有的特征選擇方法可以分為兩大類:過濾法和封裝法.過濾法先對(duì)數(shù)據(jù)集進(jìn)行特征選擇,然后再訓(xùn)練學(xué)習(xí)器,特征選擇過程與后續(xù)學(xué)習(xí)器無關(guān).與過濾法不同,封裝法直接把最終要使用的學(xué)習(xí)器的性能作為特征子集的評(píng)價(jià)準(zhǔn)則.換言之,封裝法的目的就是為給定的學(xué)習(xí)器選擇最有利于其性能的特征子集.封裝法的性能常依賴于具體的分類器,而過濾法的性能通常無此依賴性,由于過濾法的較好適應(yīng)性,相比封裝法,過濾法得到了更多的關(guān)注.

Relief 是一種廣泛應(yīng)用的過濾型方法,在文獻(xiàn)[1]中首次被提出用于二類數(shù)據(jù)的特征選擇,雖然Relief 算法比較簡(jiǎn)單,運(yùn)行效率高,并且結(jié)果也比較令人滿意,但是其局限性在于只能處理二類數(shù)據(jù),Kononenko 將其擴(kuò)展到多類情況,提出ReliefF 算法,并在文獻(xiàn)[2]中對(duì)ReliefF 算法做了深入探討.雖然Relief 已經(jīng)得到較廣泛的應(yīng)用,但它依然存在一些不足之處[3],例如,該類算法的數(shù)學(xué)形式依然沒有得到很好的定義,故它的特點(diǎn)和性質(zhì)還難以得到深入的研究,此外,它依然缺乏強(qiáng)大的處理異常數(shù)據(jù)點(diǎn)的機(jī)制,以及需要提高在噪音環(huán)境下的魯棒性.目前,已有許多改進(jìn)Relief 算法的文獻(xiàn),如迭代Relief 算法I-RELIEF[4],IRELIEF 算法基于間隔最大化構(gòu)造優(yōu)化目標(biāo)函數(shù),并以類EM 算法的迭代策略來導(dǎo)出權(quán)重向量的學(xué)習(xí)規(guī)則.另外,文獻(xiàn)[5]中提出了類依賴特征權(quán)重Relief 算法,由于不同類別數(shù)據(jù)點(diǎn)的各個(gè)特征重要性可能存在很大不同,類依賴特征權(quán)重Relief 算法為每個(gè)類別數(shù)據(jù)點(diǎn)單獨(dú)訓(xùn)練一個(gè)權(quán)重,以克服使用全局權(quán)重時(shí)不同類別數(shù)據(jù)點(diǎn)間特征重要性不同帶來的影響.

另外,已有許多結(jié)合實(shí)例選擇和特征選擇的研究.有研究通過進(jìn)化計(jì)算同時(shí)進(jìn)行實(shí)例和特征選擇以及加權(quán)[6],提出了組合這四項(xiàng)任務(wù)的一般框架,并對(duì)15 種可能的組合的有用性進(jìn)行了全面研究.還有基于動(dòng)態(tài)不完整數(shù)據(jù)粗糙集的增量特征選擇[7],提出了一種增量的特征選擇方法,可以加速動(dòng)態(tài)不完整數(shù)據(jù)中的特征選擇過程.還有研究提出結(jié)合實(shí)例選擇的三種策略進(jìn)行基于實(shí)例的學(xué)習(xí)[8],首先,它使用CHC 遺傳算法的框架.其次,它包含了多次選擇每個(gè)實(shí)例的可能性.最后,它使用的本地k值取決于每個(gè)測(cè)試實(shí)例的最近鄰居,這三種組合策略能夠比以前的方法實(shí)現(xiàn)更好的減少,同時(shí)保持與k近鄰規(guī)則相同的分類性能.目前已經(jīng)有多個(gè)實(shí)例加權(quán)方案用于改進(jìn)Relief 算法的準(zhǔn)確率,如Iterative Relief,I-RELIEF,和SWRF,這些方法應(yīng)用不同的實(shí)例加權(quán)方案并且有不錯(cuò)的效果.

為了克服類依賴特征權(quán)重的不足,提高類依賴特征權(quán)重Relief 算法準(zhǔn)確率.本文從局部特征權(quán)重?cái)?shù)據(jù)分類的角度修改權(quán)重訓(xùn)練過程并引入實(shí)例權(quán)重來提高對(duì)邊界點(diǎn)的敏感性.本文第2 部分先介紹Relief 和類依賴Relief,并分析類依賴Relief 的不足之處,第3 部分提出本文算法,第4 部分采用8 個(gè)UCI 數(shù)據(jù)集進(jìn)行實(shí)驗(yàn).第5 部分對(duì)文章內(nèi)容進(jìn)行總結(jié).

2 Relief 和類依賴Relief

Relief 算法中使用全局權(quán)重,但是因?yàn)槿志嚯x度量使用的特征權(quán)重沒有區(qū)別不同的類別,所以當(dāng)一些特征對(duì)于不同的類表現(xiàn)得不同時(shí)會(huì)導(dǎo)致分類性能不佳.相比全局權(quán)重,局部特征權(quán)重更能反映不同類中相同特征的不同重要性,因此,CDRELIEF 通過學(xué)習(xí)局部權(quán)重來提高權(quán)重關(guān)于類別的相關(guān)性,目前,已有許多方法[9,10]用于在局部區(qū)域上學(xué)習(xí)距離度量,也有局部和全局相結(jié)合的距離度量[11].對(duì)于不同的類別來說特征權(quán)重是不一樣的.最有代表性的方法是類依賴加權(quán)距離度量(CDW),該距離與原型的類標(biāo)簽相關(guān):

式中dCDW(x,y)是點(diǎn)x和點(diǎn)y的類依賴加權(quán)距離,D表示數(shù)據(jù)維度,c是點(diǎn)x的類標(biāo)簽,wc,j表示類別c第j個(gè)特征的權(quán)重.

2.1 Relief

Relief 特征加權(quán)[1]的核心思想是根據(jù)每一個(gè)特征區(qū)分不同類實(shí)例的能力來估計(jì)特征權(quán)值及其重要性,給定一個(gè)包含N個(gè)實(shí)例的二類數(shù)據(jù)集X,C是類標(biāo)簽集合,x是X中的一個(gè)實(shí)例,每個(gè)實(shí)例x=(x1,x2,···,xD)是一個(gè)維度為D的實(shí)值向量.Relief 進(jìn)行如下迭代學(xué)習(xí):隨機(jī)的選取一個(gè)實(shí)例x,然后尋找同類最近實(shí)例NH(x)和 異類最近實(shí)例NM(x),接著利用如下規(guī)則更新權(quán)值:

算法1.Relief 算法① 給定一個(gè)包含N 個(gè)實(shí)例和D 個(gè)特征的二類數(shù)據(jù)集X,設(shè)置初始權(quán)值wj=0(1 ≤j ≤D)以及最大迭代次數(shù)T,并且設(shè)置迭代初始值t=1.② 從數(shù)據(jù)集X 中隨機(jī)選取一個(gè)實(shí)例x 并計(jì)算該實(shí)例的同類最近實(shí)例NH(x) 和 異類最近實(shí)例NM(x).③ 對(duì)于每一維權(quán)值,利用式(2)更新權(quán)值.④ 若t=T,算法結(jié)束,否則t=t+1 返回步驟②.⑤ 輸出更新以后的權(quán)值向量w.

從最近鄰居Relief 發(fā)展出了考慮K個(gè)鄰居的變體,它的權(quán)重更新公式為:

KNN(x,c) 是x 在Xc中通過歐氏距離求得的K個(gè)最近鄰居的集合.

2.2 類依賴Relief

Elena Marchiori[5]研究將Relief 分解為類依賴特征權(quán)重,并表示使用全局特征權(quán)重時(shí)將同一特征在不同類中的權(quán)重相加會(huì)抵消彼此關(guān)于單個(gè)類別的相關(guān)性,導(dǎo)致特征關(guān)于單個(gè)類別的相關(guān)性可能不會(huì)被檢測(cè)到,因此他們提出將原來的所有數(shù)據(jù)共用一個(gè)特征權(quán)重改為一個(gè)類別一個(gè)特征權(quán)重,類c的特征權(quán)重為wc,這樣可以保留特征關(guān)于單個(gè)類別的相關(guān)性.計(jì)算類別權(quán)重wc時(shí)只選取類別為c的實(shí)例x,然后找該實(shí)例鄰居,對(duì)類別權(quán)重進(jìn)行更新.權(quán)重更新公式為:

wc被 看做類別c的特征權(quán)重,Xc是類別為c的數(shù)據(jù)點(diǎn)集合,KNN(x,c) 是x的同標(biāo)簽k近鄰,是x的標(biāo)簽不為c的k近鄰.根據(jù)式(4)可以為數(shù)據(jù)集中每個(gè)類別數(shù)據(jù)求得一個(gè)特征權(quán)重.

3 實(shí)例加權(quán)類依賴Relief

然而,存在如下問題:在訓(xùn)練權(quán)重wc過程中,對(duì)屬于類c的數(shù)據(jù)點(diǎn)x1和不屬于類c的數(shù)據(jù)點(diǎn)x2,目的是使x1和x2在wc下的加權(quán)距離比x1和同屬于類c 的數(shù)據(jù)點(diǎn)x3在wc下的加權(quán)距離要大.即||x1-x2||wc≥||x1-x3||wc.

但是在分類過程中,與權(quán)重訓(xùn)練過程中使不同類數(shù)據(jù)點(diǎn)在同一個(gè)權(quán)重下比較距離大小的思想不同,現(xiàn)有一個(gè)屬于類別c的數(shù)據(jù)點(diǎn)x1,一個(gè)屬于類別l的數(shù)據(jù)點(diǎn)x2.要正確分類一個(gè)屬于類c的數(shù)據(jù)點(diǎn)y,需要滿足條件:||y-x2||wl≥||y-x1||wc,即點(diǎn)y與點(diǎn)x2在wl下的加權(quán)距離要比y與點(diǎn)x1在wc下的加權(quán)距離要大.點(diǎn)y和類c數(shù)據(jù)點(diǎn)x1間 的距離用wc計(jì) 算,d(y,x1)=||y-x1||wc和類l數(shù)據(jù) 點(diǎn)x2的 距離用wl計(jì) 算,d(y,x2)=||y-x2||wl.另外,為了提高訓(xùn)練出的特征權(quán)重的分類精度,本文將參與權(quán)重訓(xùn)練的實(shí)例限制在分類邊界附近的點(diǎn).

3.1 實(shí)例權(quán)重

本文中設(shè)置實(shí)例權(quán)重是一方面由于難分類的點(diǎn)是位于類邊界的點(diǎn),那些遠(yuǎn)離類邊界的點(diǎn)不容易分類錯(cuò)誤.當(dāng)類邊界處的點(diǎn)能夠正確分類時(shí)遠(yuǎn)離類邊界的點(diǎn)也能分類正確.另一方面由于遠(yuǎn)離類邊界的點(diǎn)在參與特征權(quán)重更新公式中對(duì)特征權(quán)重值造成的變化量較大,而類邊界處點(diǎn)對(duì)特征權(quán)重值造成的變化量較小,因此遠(yuǎn)離類邊界點(diǎn)的參與容易使得訓(xùn)練出的分類邊界不能夠正確分類類邊界點(diǎn).因此只需要選取類邊界附近的點(diǎn)參與分類邊界的確定,從而避免了遠(yuǎn)離類邊界的點(diǎn)對(duì)特征權(quán)重的影響,進(jìn)而提高了分類準(zhǔn)確率.

在權(quán)重更新過程中通過令遠(yuǎn)離類邊界的數(shù)據(jù)點(diǎn)實(shí)例權(quán)重值為0,來排除遠(yuǎn)離類邊界的數(shù)據(jù)點(diǎn)對(duì)特征權(quán)重更新的影響,同時(shí)也排除了離群點(diǎn)的影響,進(jìn)而提高訓(xùn)練出的特征權(quán)重具有更高的分類精度.實(shí)例權(quán)重公式如下:

其中,threshold是設(shè)定的閾值,取值為0 到1 之間的值.d1是x到k個(gè)同類鄰居的距離和,d2是x到k個(gè)異類鄰居的距離和,如果當(dāng)前實(shí)例到同類鄰居的距離之和d1與到異類鄰居的距離之和d2的比值d1/d2＜threshold說明當(dāng)前實(shí)例點(diǎn)遠(yuǎn)離類邊界,實(shí)例點(diǎn)權(quán)重設(shè)為0,從而不影響特征權(quán)重更新.另一方面,當(dāng)d2/d1＜threshold時(shí),該實(shí)例點(diǎn)是離群點(diǎn),權(quán)重值也應(yīng)該為0,從而排除了離群點(diǎn)對(duì)特征權(quán)重的影響.

3.2 新的特征權(quán)重更新公式

本文結(jié)合實(shí)例權(quán)重提出新的類依賴特征權(quán)重更新過程如下:

輸入:最大迭代次數(shù)T,以及一個(gè)包含N個(gè)實(shí)例的D維二類數(shù)據(jù)集:是數(shù)據(jù)的類別標(biāo)簽集合,因?yàn)樗惴ㄓ糜诙悢?shù)據(jù)集分類,所以C只包含兩個(gè)元素.

Step1.為每個(gè)類別的特征權(quán)重設(shè)置初始權(quán)值wc,j=0(c∈C,1 ≤j≤D).

Step2.從集合C中取出一個(gè)類標(biāo)簽c.

Step3.從數(shù)據(jù)集X中隨機(jī)選取一個(gè)類別為c的實(shí)例x.根據(jù)如下過程更新權(quán)重:

Step3.1.找出x的k個(gè)同類最近鄰居集合KNN(x,c),還有k個(gè)異類最近鄰居集合以及到KNN(x,c) 中k個(gè)點(diǎn)的距離之和d1.到的k個(gè)點(diǎn)距離之和d2.

Step3.2.將d1,d2代入式(5)計(jì)算x的實(shí)例權(quán)重IW(x).

Step3.3.c為x的類標(biāo)簽,l為不同于c的類標(biāo)簽,即集合C中的另一個(gè)類.對(duì)兩個(gè)類別的特征權(quán)重wc,j(j∈D),wl,j(j∈D)進(jìn)行更新:

||x-z||表示點(diǎn)x和點(diǎn)z的歐式距離.

Step4.t=T,則執(zhí)行Step5,t＜T則返回Step3.

Step5.若C中所有值都取出,算法結(jié)束,輸出wc(c∈C)否則返回Step2.

本文提出的新特征權(quán)重更新公式中由于引入了實(shí)例權(quán)重避免遠(yuǎn)離類邊界的點(diǎn)大幅度影響特征權(quán)重值而導(dǎo)致分類邊界不能正確分類類邊界點(diǎn).另一方面從局部權(quán)重分類的角度出發(fā)修改特征權(quán)重更新過程:當(dāng)異類鄰居的特征差值小于與同類鄰居的特征差值時(shí)減小同類特征權(quán)重值,當(dāng)異類鄰居的特征差值大于與同類鄰居的特征差值時(shí)增大異類特征權(quán)重值.

4 實(shí)驗(yàn)與分析

實(shí)驗(yàn)中采用了8 個(gè)二類UCI 數(shù)據(jù)集(見表1).所有數(shù)據(jù)都用z-score 標(biāo)準(zhǔn)化進(jìn)行預(yù)處理.對(duì)每個(gè)數(shù)據(jù)集都進(jìn)行了10 折交叉驗(yàn)證,取10 折交叉準(zhǔn)確率的平均值作為最后的準(zhǔn)確率.實(shí)驗(yàn)中閾值threshold取值范圍

從0.1 到0.9,以0.1 為間隔一共9 個(gè)取值,對(duì)每個(gè)數(shù)據(jù)集選擇效果最好的那個(gè).為了驗(yàn)證本文方法的實(shí)際效果.實(shí)驗(yàn)中取k=5,對(duì)比了本文提出的算法和類依賴Relief 的準(zhǔn)確率,表2顯示了兩個(gè)算法的平均準(zhǔn)確度以及標(biāo)準(zhǔn)差.可以看到本文提出的算法對(duì)數(shù)據(jù)集的分類準(zhǔn)確率有很明顯的提高,并且從圖一可以看出相比CDRELIEF,當(dāng)k取不同值時(shí)分類準(zhǔn)確率更加穩(wěn)定且明顯高于CDRELIEF.

表1 數(shù)據(jù)集相關(guān)信息

表2 CDRELIEF 和IWCDRELIEF 算法準(zhǔn)確率對(duì)比(%)

圖1 CDRELIEF 和IWCDRELIEF 對(duì)實(shí)驗(yàn)數(shù)據(jù)集在不同k 值下分類準(zhǔn)確率的對(duì)比(%)

5 結(jié)語

本文通過應(yīng)用實(shí)例權(quán)重到類依賴Relief 特征權(quán)重更新公式中,提出了具有更好魯棒性的實(shí)例加權(quán)類依賴Relief 算法,提出的新算法在8 個(gè)二類UCI 數(shù)據(jù)集上驗(yàn)證了其有效性.未來的工作中,研究如何進(jìn)一步提出更精確有效的實(shí)例加權(quán)方案以及如何結(jié)合快速學(xué)習(xí)理論加快算法執(zhí)行速度,減小算法時(shí)間復(fù)雜度是重點(diǎn)方向.