基于k近鄰屬性重要度和相關系數的屬性約簡

林芷欣，劉遵仁，紀 俊

(青島大學 計算機科學技術學院，山東 青島 266071)

0 引 言

為了有效去除冗余信息，并且不改變原始信息的分類能力，屬性約簡算法隨之產生。在鄰域粗糙集中，為了能快速得到屬性約簡，Hu等提出基于屬性重要度的前向貪心式屬性約簡算法；Hu等又通過研究正域的變化，發現新加入的屬性不會改變之前正域樣本的性質，由此提出了FARNeMF算法。Liu等通過改進Hu等的FARNeMF算法，提出了FHARA算法[1]。以上3種算法，都是通過逐漸優化所選待測樣本，來降低鄰域計算的次數，達到節省算法的時間開銷的目的。但是，上述算法在貪心選擇重要度高的屬性時，一直保持著高維計算，算法復雜度高，且重復計算較多，浪費資源[2]。基于這種情況，本文在算法屬性重要度的計算上做了一些改進，提出一種屬性重要度計算方法，根據樣本k近鄰條件屬性與決策屬性的關系[3,4]，重新給出了屬性重要度的定義，降低計算維度，提高算法運行效率。另外，考慮到條件屬性之間的關聯程度，也會對約簡結果產生影響，因此引入相關系數的概念，降低屬性間關聯程度對屬性約簡結果的影響[5]。實驗結果表明，本文提出的算法能獲得較好的屬性，并得到較高的分類精度。

1 相關概念和理論

1.1 粗糙集理論

粗糙集理論認為，客觀世界可以抽象為一個知識表達系統。這個知識表達系統又可以被看成是一個關系數據表，表的行代表被研究的對象，表的列代表被研究對象的屬性，對象信息就通過各屬性對應的屬性值來表達[6]。給定一四元組DT=(U,A,V,f) 是一個知識表達系統，知識表達系統的詳細定義請參考文獻[7]。

定義1 設DT=(U,A,V,f)， 若P?A， 對論域上的一個對象子集X?U， 定義X關于P的上近似、下近似和邊界域分別為

(1)

(2)

(3)

1.2 鄰域粗糙集

定義2 在給定實數空間Ω上的非空有限集合U={x1,x2,…,xn}，U={x1,x2,…,xn} 對U中任意對象xi的δ-鄰域定義為：δ(xi)={x|x∈U,d(x,xi)≤δ}。

其中δ≥0，d為距離函數。δ(xi) 稱作由xi生成的δ-鄰域信息粒子，簡稱為xi的鄰域粒子。

定義3 給定一四元組NDT=(U,C∪D,V,f) 為鄰域決策系統，C是條件屬性集，D是決策屬性集，C∩D=φ。D將U劃分為N個等價類： (X1,X2,…,XN)， 對?B?C，X關于B的下近似、上近似和邊界域分別為

(4)

(5)

(6)

2 屬性約簡算法

已有的基于屬性重要度的約簡算法，它們大部分都是基于Hu提出的屬性重要度概念，在選擇下一個屬性時，需要計算所有未選入約簡集合的屬性的重要度，最后貪心的選擇一個屬性并入約簡集合[2]。雖然后來提出的FHARA算法優化了待測樣本的數量問題，但還是避免不了其中需要進行很多重復的鄰域計算操作。針對這個問題本文提出了一種k近鄰屬性重要度算法，通過依次計算每一維度下樣本點x的k近鄰異類樣本點平均距離和k近鄰同類樣本點平均距離的比值，來判斷每一維度屬性對同類和異類樣本的區分能力，并將其作為屬性重要度的衡量指標。但由于該方法只考慮了樣本條件屬性對決策類的影響，忽略了條件屬性之間可能存在的相互影響[8]，因此，本文再將屬性間相關系數融入到屬性約簡算法中。當屬性約簡集擬并入新屬性時，新屬性需要和約簡集中已有屬性進行相關系數計算，若相關系數較高，則新屬性不加入約簡集，反之，新屬性加入約簡集，直至得到最終的屬性約簡。

2.1 現有屬性重要度約簡算法

基于鄰域粗糙集屬性重要度的定義最先是由Hu提出的，他給出的定義請參見文獻[6]。

比較典型的基于屬性重要度的約簡算法有Hu提出的FARNeMF算法和Lin提出的FHARA算法。通過分析可知，現有屬性重要度的定義是通過并入集合的屬性集所劃分的正域大小判斷。也就是說，一個屬性的加入，能讓越多的樣本劃入正域，這個屬性的重要度就越大。但每當要并入一個新的屬性時，都需要將所有未并入的屬性依次與已經選擇的屬性集相并，計算它們的正域大小[9,10]。最終選擇ak， 使其滿足

SIG(ak,red,D)=max(SIG(ai,red,D))

(7)

(8)

式中：posi表示加入第i個屬性時，樣本進行正域判定所耗時間。

2.2 基于k近鄰的屬性重要度

基于傳統屬性重要度的約簡算法中新屬性并入時正域的計算量雖然是一個降維的過程，但由于屬性約簡算法最終選擇的屬性較少，因此，即便是一個降維的過程，每次貪心選擇屬性時，平均正域的計算量也是維持在n維左右，算法計算量偏大，重復的正域計算較多[11]。本文提出的基于k近鄰的屬性重要度算法，在并入新屬性時只需進行一維正域計算，算法計算量減少，運行效率較高。算法具體描述如下：

(9)

算法1： 基于k近鄰的屬性重要度算法

輸入：NDT=(U,C∪D,V,f)， 樣本抽樣次數m， 最近鄰樣本個數k

輸出： 條件屬性的屬性重要度序列

(1)初始化，Pow=0

(2)?x∈U

forj=1∶n

1)在每一維度下， 找距離樣本x最近的k個同類樣本點 (x1,x2,…,xk) 和k個異類樣本點 (y1,y2,…,yk)。

end

(3)Order=sort(Powj)

(4)return Order

2.3 相關系數及其性質

在2.2節提出的屬性重要度的計算方法，只考慮了單個條件屬性對決策屬性的影響，沒有考慮條件屬性之間的關系也會對約簡結果產生影響。如果兩個條件屬性的相關性較強，二者又都在約簡結果中，就會導致數據冗余[12]。因此為了避免數據冗余，本文引入秩相關系數計算條件屬性間的相關性，去除多余屬性[10]。

定義4 給定一鄰域決策系統NDT=(U,C∪D,V,f)， ?ai,aj∈C， 將ai和aj中的數據按照屬性值從小到大分別進行排序后對每個對象進行編秩，第k個對象在ai，aj屬性下對應的秩次分別為xk和yk， 則ai和aj的相關系數ρij定義為

(10)

下面給出一求某對屬性相關系數的例子。

例1：給定一決策表，見表1。求表中屬性a,b的相關系數。

表1 決策表

(1)將屬性a的屬性值按從小到大排序，得到一個對象序列 {m5,m2,m3,m4,m1}， 對對象進行編秩得 {m5=1,m2=2,m3=3,m4=4,m1=5}。

(2)如果一個屬性中有屬性值相同，秩次取它們的平均值。屬性a中m2=m3， 所以它們的秩次調整為m2=m3=(2+3)/2=2.5， 得到新的秩次序列 {m5=1,m2=2.5,m3=2.5,m4=4,m1=5}。

(3)同理可得屬性b下各對象對應的秩次序列 {m1=1,m4=2,m2=3,m3=4,m5=5}。

表2 秩次表

(5)根據相關系數計算公式，計算屬性a、b的相關系數為0.97。

算法2： 相關系數算法

輸入：NDT=(U,C∪D,V,f)， 條件屬性子集ai，aj

輸出： 相關系數ρij

(1)將對象按ai和aj下對應屬性值從小到大排序， 并編秩;

(2)更新秩次序列， 按表中原始對象順序排列;

(4)按照公式計算相關系數ρij;

(5)返回ρij。

2.4 基于k近鄰屬性重要度和相關系數的屬性約簡算法(K2NCRS)

K2NCRS算法在根據算法1算出屬性重要度序列后，要依次選取屬性重要度最大的屬性加入約簡集，加入約簡集前，要對擬加入屬性和約簡集中的所有屬性進行相關系數的判定，這里需要設置一個閾值γ。 如果擬加入的屬性和約簡集中其它屬性的相關系數都小于γ， 則對擬加入的屬性繼續進行判斷，若加入后正域的樣本增多，則將該屬性加入約簡集，反之，刪除該屬性。如果擬加入的屬性和約簡集中其它屬性的相關系數存在不小于γ的，將擬加入的屬性刪除，繼續遍歷除約簡集外其它屬性重要度較高的屬性，直至所有樣本都被加入正域。

另外，在進行樣本正域計算時，需要設置樣本的鄰域大小，為了能獲得較好的效果，本文選用文獻[10]提到的標準差方法，來確定鄰域δ的大小。

算法3： K2NCRS算法

輸入：NDT=(U,C∪D,V,f)，δ

輸出： red

(1) 初始化pos=φ,smp=U,flag=φ;

(2) 利用算法1算出屬性重要度序列Order;

(3) red=Order(1);

(4)while sum(smp)～=0

forai=Order-(red∪flag)

flag=φ;

for ?aj∈red

利用算法2， 計算ai和aj的相關系數ρij。

ifρij>γ

去掉和已選屬性相關性大的屬性

else

pos=Pos(smp,[red,ai]);

red=red∪ai;

smp=setdiff(smp,max_pos);

end

end

end

end while

(5) return red

(11)

3 實驗分析

3.1 實驗準備

為檢驗本文算法的性能，從UCI數據庫中選取6組常用連續型數據進行實驗，表3給出了數據集的詳細描述。另外，為消除數量級對計算的影響，本文對所有實驗數據進行歸一化處理，使得所有實驗數據都在[0,1]區間內。

表3 數據集描述

3.2 算法有效性驗證

實驗將K2NCRS算法與Liu提出的FHARA算法分別在屬性約簡數量、分類精度及算法運行時間上進行了詳細的對比分析，通過各項實驗數據驗證了K2NCRS算法是有效的。并且本文算法實驗結果是在相關系數閾值設置γ為0.6的條件下得到的。

3.2.1 屬性約簡數量比較

表4顯示了FHARA算法和K2NCRS算法在約簡前后，屬性數量的變化。從表中可以看出，當鄰域大小一定時，在wdbc、sonor和wpbc這3組數據集上K2NCRS算法得到的屬性比FHARA算法多1個，在diabetes數據集上K2NCRS算法約簡得到的屬性比FHARA算法多兩個，在ionosphere和biodeg兩組數據集上K2NCRS算法得到的約簡屬性比FHARA算法多3個。整體上看K2NCRS算法約簡得到的屬性數量比FHARA算法偏多。但是，兩算法約簡后的屬性個數都明顯少于原始條件屬性的個數，因此，本文K2NCRS算法都能有效刪除冗余信息，達到屬性約簡的效果。

3.2.2 分類精度比較

為獲得約簡后屬性的分類能力，我們選用了SVM分類學習算法，選用10折交叉驗證的方法，得到兩算法約簡后屬性分類精度見表5，表5中兩算法在SVM分類器下的分類精度的對比柱狀圖如圖1所示。

表4 屬性約簡數量比較

表5 SVM分類器下分類精度比較

圖1 SVM分類器下FHARA與K2NCRS算法分類精度對比

圖1橫坐標表示實驗所選屬性集編號，并且該編號順序是按照數據集樣本數量由少至多編排，縱坐標表示約簡后每組屬性集對應的分類精度。從圖整體上看，兩種算法對應柱體的變化趨勢大致相同，對比兩種算法實驗得到分類精度的最大最小值發現，本文算法分類精度的變化區間小于 FHARA 算法，說明本文算法能夠得到較好的約簡屬性。從前4組數據可以明顯看出，K2NCRS算法的分類精度高于FHARA算法，對比后兩組數據發現，K2NCRS算法的分類精度略低于FHARA算法。造成這種現象的原因，是因為本文算法中僅通過兩類相鄰樣本的距離大小來判斷某個屬性的重要度這一條件，隨著樣本數量的增多，受數據中其它噪聲的影響變大，判斷條件的不穩定性增大，進而影響屬性重要度的判斷。

3.2.3 相關系數閾值選取

計算屬性間相關系數時，需要設置相關系數的閾值，通常情況下，相關系數大于0.8，代表屬性間相關性極強，相關系數在0.4-0.8代表屬性間有較強的相關性，相關系數低于0.4代表屬性間相關性較弱。表6～表9分別記錄了相關系數閾值γ取0.4,0.5,0.6,0.7時本文算法對應得到的屬性約簡數量和分類精度。

表6 γ=0.4

表7 γ=0.5

表8 γ=0.6

表9 γ=0.7

為了方便觀察，繪制6組數據在不同閾值下的分類精度對比折線圖如圖2所示。

圖2 6組數據在不同閾值下的分類精度對比

對比表6～表9及圖2，可以發現當閾值為0.4時，各個數據集得到的約簡數量最少，并且對應的分類精度普遍較低，當閾值為0.7時，各個數據集對應的約簡數量最多，并且大部分數據集對應的分類精度隨著閾值的增大也逐漸提高，這是因為當閾值設置較小時，判斷屬性相關性的條件就顯得過于嚴苛，因而導致最終剩余屬性較少，且分類精度不高。當閾值設置較大時，判斷屬性相關性的條件又顯得過于寬松，不能有效去除冗余屬性，導致最終約簡出的屬性個數較多，并且閾值較大時對應的分類精度的變化也不明顯。綜合考慮，本文算法在閾值為0.6時，約簡得到的屬性個數不是最大，并且各組數據對應的分類精度均接近最大值，因此，本文算法的相關系數閾值設為0.6.

3.2.4 運行時間比較

圖3是本文提出的K2NCRS算法與Liu提出的FHARA算法在同一臺機器上的運行時間對比折線圖。對比圖中兩條折線，執行K2NCRS算法得到的折線一直在執行FHARA算法得到折線的下方，說明對于大部分數據集而言，K2NCRS算法的運行效率更高，算法執行速度更快。同時，這一結果也與2.4節中對兩種算法計算量的分析結果相吻合。再次驗證了本文提出的基于k近鄰的屬性重要度算法的時間復雜度低于基于依賴度的屬性重要度算法。所以，K2NCRS算法能獲得更短的時間開銷，算法運行效率更高。

圖3 FHARA與K2NCRS算法運行時間對比

通過以上幾組實驗的對比，雖然本文的K2NCRS算法約簡得到的屬性數量比基于屬性依賴度的傳統FHARA算法多，但和原始數據集的屬性個數相比，本文算法仍能夠有效去除多余屬性，并根據最終得到的屬性約簡集也能獲得不錯的分類精度，并且隨著樣本數量和條件屬性個數的增多，本文算法的運行時間和FHARA算法的對比就越明顯。

4 結束語

目前鄰域粗糙集下基于屬性重要度的屬性約簡算法，大多都是通過優化區間減少正域計算時比較樣本的數量，來提高算法的運行效率。但是這種優化方法還是避免不了每次貪心選擇屬性時仍需要依次反復的對所有尚未選擇的屬性進行重要度計算，因此本文從屬性重要度的定義著手，提出一種基于k近鄰的屬性重要度算法，將貪心選擇屬性時重復的重要度計算改為對每個樣本k近鄰的屬性加權評估計算，極大提高了算法的運行效率，減少了算法的時間開銷。