實例加權類依賴Relief①

邱海峰,何振峰

(福州大學 數學與計算機科學學院,福州 350116)

1 引言

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

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

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

為了克服類依賴特征權重的不足,提高類依賴特征權重Relief 算法準確率.本文從局部特征權重數據分類的角度修改權重訓練過程并引入實例權重來提高對邊界點的敏感性.本文第2 部分先介紹Relief 和類依賴Relief,并分析類依賴Relief 的不足之處,第3 部分提出本文算法,第4 部分采用8 個UCI 數據集進行實驗.第5 部分對文章內容進行總結.

2 Relief 和類依賴Relief

Relief 算法中使用全局權重,但是因為全局距離度量使用的特征權重沒有區別不同的類別,所以當一些特征對于不同的類表現得不同時會導致分類性能不佳.相比全局權重,局部特征權重更能反映不同類中相同特征的不同重要性,因此,CDRELIEF 通過學習局部權重來提高權重關于類別的相關性,目前,已有許多方法[9,10]用于在局部區域上學習距離度量,也有局部和全局相結合的距離度量[11].對于不同的類別來說特征權重是不一樣的.最有代表性的方法是類依賴加權距離度量(CDW),該距離與原型的類標簽相關:

式中dCDW(x,y)是點x和點y的類依賴加權距離,D表示數據維度,c是點x的類標簽,wc,j表示類別c第j個特征的權重.

2.1 Relief

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

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

從最近鄰居Relief 發展出了考慮K個鄰居的變體,它的權重更新公式為:

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

2.2 類依賴Relief

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

wc被 看做類別c的特征權重,Xc是類別為c的數據點集合,KNN(x,c) 是x的同標簽k近鄰,是x的標簽不為c的k近鄰.根據式(4)可以為數據集中每個類別數據求得一個特征權重.

3 實例加權類依賴Relief

然而,存在如下問題:在訓練權重wc過程中,對屬于類c的數據點x1和不屬于類c的數據點x2,目的是使x1和x2在wc下的加權距離比x1和同屬于類c 的數據點x3在wc下的加權距離要大.即||x1-x2||wc≥||x1-x3||wc.

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

3.1 實例權重

本文中設置實例權重是一方面由于難分類的點是位于類邊界的點,那些遠離類邊界的點不容易分類錯誤.當類邊界處的點能夠正確分類時遠離類邊界的點也能分類正確.另一方面由于遠離類邊界的點在參與特征權重更新公式中對特征權重值造成的變化量較大,而類邊界處點對特征權重值造成的變化量較小,因此遠離類邊界點的參與容易使得訓練出的分類邊界不能夠正確分類類邊界點.因此只需要選取類邊界附近的點參與分類邊界的確定,從而避免了遠離類邊界的點對特征權重的影響,進而提高了分類準確率.

在權重更新過程中通過令遠離類邊界的數據點實例權重值為0,來排除遠離類邊界的數據點對特征權重更新的影響,同時也排除了離群點的影響,進而提高訓練出的特征權重具有更高的分類精度.實例權重公式如下:

其中,threshold是設定的閾值,取值為0 到1 之間的值.d1是x到k個同類鄰居的距離和,d2是x到k個異類鄰居的距離和,如果當前實例到同類鄰居的距離之和d1與到異類鄰居的距離之和d2的比值d1/d2＜threshold說明當前實例點遠離類邊界,實例點權重設為0,從而不影響特征權重更新.另一方面,當d2/d1＜threshold時,該實例點是離群點,權重值也應該為0,從而排除了離群點對特征權重的影響.

3.2 新的特征權重更新公式

本文結合實例權重提出新的類依賴特征權重更新過程如下:

輸入:最大迭代次數T,以及一個包含N個實例的D維二類數據集:是數據的類別標簽集合,因為算法用于二類數據集分類,所以C只包含兩個元素.

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

Step2.從集合C中取出一個類標簽c.

Step3.從數據集X中隨機選取一個類別為c的實例x.根據如下過程更新權重:

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

Step3.2.將d1,d2代入式(5)計算x的實例權重IW(x).

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

||x-z||表示點x和點z的歐式距離.

Step4.t=T,則執行Step5,t＜T則返回Step3.

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

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

4 實驗與分析

實驗中采用了8 個二類UCI 數據集(見表1).所有數據都用z-score 標準化進行預處理.對每個數據集都進行了10 折交叉驗證,取10 折交叉準確率的平均值作為最后的準確率.實驗中閾值threshold取值范圍

從0.1 到0.9,以0.1 為間隔一共9 個取值,對每個數據集選擇效果最好的那個.為了驗證本文方法的實際效果.實驗中取k=5,對比了本文提出的算法和類依賴Relief 的準確率,表2顯示了兩個算法的平均準確度以及標準差.可以看到本文提出的算法對數據集的分類準確率有很明顯的提高,并且從圖一可以看出相比CDRELIEF,當k取不同值時分類準確率更加穩定且明顯高于CDRELIEF.

表1 數據集相關信息

表2 CDRELIEF 和IWCDRELIEF 算法準確率對比(%)

圖1 CDRELIEF 和IWCDRELIEF 對實驗數據集在不同k 值下分類準確率的對比(%)

5 結語

本文通過應用實例權重到類依賴Relief 特征權重更新公式中,提出了具有更好魯棒性的實例加權類依賴Relief 算法,提出的新算法在8 個二類UCI 數據集上驗證了其有效性.未來的工作中,研究如何進一步提出更精確有效的實例加權方案以及如何結合快速學習理論加快算法執行速度,減小算法時間復雜度是重點方向.