基于k近鄰屬性重要度和相關(guān)系數(shù)的屬性約簡(jiǎn)

林芷欣，劉遵仁，紀(jì) 俊

(青島大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，山東 青島 266071)

0 引 言

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

1 相關(guān)概念和理論

1.1 粗糙集理論

粗糙集理論認(rèn)為，客觀世界可以抽象為一個(gè)知識(shí)表達(dá)系統(tǒng)。這個(gè)知識(shí)表達(dá)系統(tǒng)又可以被看成是一個(gè)關(guān)系數(shù)據(jù)表，表的行代表被研究的對(duì)象，表的列代表被研究對(duì)象的屬性，對(duì)象信息就通過(guò)各屬性對(duì)應(yīng)的屬性值來(lái)表達(dá)[6]。給定一四元組DT=(U,A,V,f) 是一個(gè)知識(shí)表達(dá)系統(tǒng)，知識(shí)表達(dá)系統(tǒng)的詳細(xì)定義請(qǐng)參考文獻(xiàn)[7]。

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

(1)

(2)

(3)

1.2 鄰域粗糙集

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

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

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

(4)

(5)

(6)

2 屬性約簡(jiǎn)算法

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

2.1 現(xiàn)有屬性重要度約簡(jiǎn)算法

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

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

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

(7)

(8)

式中：posi表示加入第i個(gè)屬性時(shí)，樣本進(jìn)行正域判定所耗時(shí)間。

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

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

(9)

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

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

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

(1)初始化，Pow=0

(2)?x∈U

forj=1∶n

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

end

(3)Order=sort(Powj)

(4)return Order

2.3 相關(guān)系數(shù)及其性質(zhì)

在2.2節(jié)提出的屬性重要度的計(jì)算方法，只考慮了單個(gè)條件屬性對(duì)決策屬性的影響，沒有考慮條件屬性之間的關(guān)系也會(huì)對(duì)約簡(jiǎn)結(jié)果產(chǎn)生影響。如果兩個(gè)條件屬性的相關(guān)性較強(qiáng)，二者又都在約簡(jiǎn)結(jié)果中，就會(huì)導(dǎo)致數(shù)據(jù)冗余[12]。因此為了避免數(shù)據(jù)冗余，本文引入秩相關(guān)系數(shù)計(jì)算條件屬性間的相關(guān)性，去除多余屬性[10]。

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

(10)

下面給出一求某對(duì)屬性相關(guān)系數(shù)的例子。

例1：給定一決策表，見表1。求表中屬性a,b的相關(guān)系數(shù)。

表1 決策表

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

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

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

表2 秩次表

(5)根據(jù)相關(guān)系數(shù)計(jì)算公式，計(jì)算屬性a、b的相關(guān)系數(shù)為0.97。

算法2： 相關(guān)系數(shù)算法

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

輸出： 相關(guān)系數(shù)ρij

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

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

(4)按照公式計(jì)算相關(guān)系數(shù)ρij;

(5)返回ρij。

2.4 基于k近鄰屬性重要度和相關(guān)系數(shù)的屬性約簡(jiǎn)算法(K2NCRS)

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

另外，在進(jìn)行樣本正域計(jì)算時(shí)，需要設(shè)置樣本的鄰域大小，為了能獲得較好的效果，本文選用文獻(xiàn)[10]提到的標(biāo)準(zhǔn)差方法，來(lái)確定鄰域δ的大小。

算法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∪f(wàn)lag)

flag=φ;

for ?aj∈red

利用算法2， 計(jì)算ai和aj的相關(guān)系數(shù)ρij。

ifρij>γ

去掉和已選屬性相關(guān)性大的屬性

else

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

red=red∪ai;

smp=setdiff(smp,max_pos);

end

end

end

end while

(5) return red

(11)

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)準(zhǔn)備

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

表3 數(shù)據(jù)集描述

3.2 算法有效性驗(yàn)證

實(shí)驗(yàn)將K2NCRS算法與Liu提出的FHARA算法分別在屬性約簡(jiǎn)數(shù)量、分類精度及算法運(yùn)行時(shí)間上進(jìn)行了詳細(xì)的對(duì)比分析，通過(guò)各項(xiàng)實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證了K2NCRS算法是有效的。并且本文算法實(shí)驗(yàn)結(jié)果是在相關(guān)系數(shù)閾值設(shè)置γ為0.6的條件下得到的。

3.2.1 屬性約簡(jiǎn)數(shù)量比較

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

3.2.2 分類精度比較

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

表4 屬性約簡(jiǎn)數(shù)量比較

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

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

圖1橫坐標(biāo)表示實(shí)驗(yàn)所選屬性集編號(hào)，并且該編號(hào)順序是按照數(shù)據(jù)集樣本數(shù)量由少至多編排，縱坐標(biāo)表示約簡(jiǎn)后每組屬性集對(duì)應(yīng)的分類精度。從圖整體上看，兩種算法對(duì)應(yīng)柱體的變化趨勢(shì)大致相同，對(duì)比兩種算法實(shí)驗(yàn)得到分類精度的最大最小值發(fā)現(xiàn)，本文算法分類精度的變化區(qū)間小于 FHARA 算法，說(shuō)明本文算法能夠得到較好的約簡(jiǎn)屬性。從前4組數(shù)據(jù)可以明顯看出，K2NCRS算法的分類精度高于FHARA算法，對(duì)比后兩組數(shù)據(jù)發(fā)現(xiàn)，K2NCRS算法的分類精度略低于FHARA算法。造成這種現(xiàn)象的原因，是因?yàn)楸疚乃惴ㄖ袃H通過(guò)兩類相鄰樣本的距離大小來(lái)判斷某個(gè)屬性的重要度這一條件，隨著樣本數(shù)量的增多，受數(shù)據(jù)中其它噪聲的影響變大，判斷條件的不穩(wěn)定性增大，進(jìn)而影響屬性重要度的判斷。

3.2.3 相關(guān)系數(shù)閾值選取

計(jì)算屬性間相關(guān)系數(shù)時(shí)，需要設(shè)置相關(guān)系數(shù)的閾值，通常情況下，相關(guān)系數(shù)大于0.8，代表屬性間相關(guān)性極強(qiáng)，相關(guān)系數(shù)在0.4-0.8代表屬性間有較強(qiáng)的相關(guān)性，相關(guān)系數(shù)低于0.4代表屬性間相關(guān)性較弱。表6～表9分別記錄了相關(guān)系數(shù)閾值γ取0.4,0.5,0.6,0.7時(shí)本文算法對(duì)應(yīng)得到的屬性約簡(jiǎn)數(shù)量和分類精度。

表6 γ=0.4

表7 γ=0.5

表8 γ=0.6

表9 γ=0.7

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

圖2 6組數(shù)據(jù)在不同閾值下的分類精度對(duì)比

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

3.2.4 運(yùn)行時(shí)間比較

圖3是本文提出的K2NCRS算法與Liu提出的FHARA算法在同一臺(tái)機(jī)器上的運(yùn)行時(shí)間對(duì)比折線圖。對(duì)比圖中兩條折線，執(zhí)行K2NCRS算法得到的折線一直在執(zhí)行FHARA算法得到折線的下方，說(shuō)明對(duì)于大部分?jǐn)?shù)據(jù)集而言，K2NCRS算法的運(yùn)行效率更高，算法執(zhí)行速度更快。同時(shí)，這一結(jié)果也與2.4節(jié)中對(duì)兩種算法計(jì)算量的分析結(jié)果相吻合。再次驗(yàn)證了本文提出的基于k近鄰的屬性重要度算法的時(shí)間復(fù)雜度低于基于依賴度的屬性重要度算法。所以，K2NCRS算法能獲得更短的時(shí)間開銷，算法運(yùn)行效率更高。

圖3 FHARA與K2NCRS算法運(yùn)行時(shí)間對(duì)比

通過(guò)以上幾組實(shí)驗(yàn)的對(duì)比，雖然本文的K2NCRS算法約簡(jiǎn)得到的屬性數(shù)量比基于屬性依賴度的傳統(tǒng)FHARA算法多，但和原始數(shù)據(jù)集的屬性個(gè)數(shù)相比，本文算法仍能夠有效去除多余屬性，并根據(jù)最終得到的屬性約簡(jiǎn)集也能獲得不錯(cuò)的分類精度，并且隨著樣本數(shù)量和條件屬性個(gè)數(shù)的增多，本文算法的運(yùn)行時(shí)間和FHARA算法的對(duì)比就越明顯。

4 結(jié)束語(yǔ)

目前鄰域粗糙集下基于屬性重要度的屬性約簡(jiǎn)算法，大多都是通過(guò)優(yōu)化區(qū)間減少正域計(jì)算時(shí)比較樣本的數(shù)量，來(lái)提高算法的運(yùn)行效率。但是這種優(yōu)化方法還是避免不了每次貪心選擇屬性時(shí)仍需要依次反復(fù)的對(duì)所有尚未選擇的屬性進(jìn)行重要度計(jì)算，因此本文從屬性重要度的定義著手，提出一種基于k近鄰的屬性重要度算法，將貪心選擇屬性時(shí)重復(fù)的重要度計(jì)算改為對(duì)每個(gè)樣本k近鄰的屬性加權(quán)評(píng)估計(jì)算，極大提高了算法的運(yùn)行效率，減少了算法的時(shí)間開銷。