基于容差關(guān)系知識(shí)依賴的屬性約簡(jiǎn)算法研究

夏冰瑩, 吳 陳

(江蘇科技大學(xué) 計(jì)算機(jī)學(xué)院, 鎮(zhèn)江 212003)

粗糙集理論由波蘭學(xué)者PAWLAK Z在1982年研究不完整數(shù)據(jù)和不精確知識(shí)的表達(dá)中提出[1-3],它能有效闡述和處理模糊、不完整等各種不完備信息,并從中發(fā)現(xiàn)潛在知識(shí),揭示隱含規(guī)律．目前,粗糙集理論在許多領(lǐng)域取得了廣泛應(yīng)用,并且在機(jī)器學(xué)習(xí)領(lǐng)域中成為一個(gè)較新的研究熱點(diǎn)[4]．該理論的核心是不可分辨關(guān)系,也就是等價(jià)關(guān)系．該關(guān)系在分類(lèi)過(guò)程中產(chǎn)生,對(duì)知識(shí)庫(kù)中知識(shí)間的關(guān)系研究起到了至關(guān)重要的作用．但是在現(xiàn)實(shí)生活中,由于測(cè)量誤差、數(shù)據(jù)冗余等原因,造成信息系統(tǒng)的屬性缺失現(xiàn)象普遍存在．在不完備信息系統(tǒng)[5-7]中,根據(jù)等價(jià)關(guān)系對(duì)論域進(jìn)行劃分是不合理的．為了提高數(shù)據(jù)分析處理的準(zhǔn)確性,可以對(duì)傳統(tǒng)的基于等價(jià)關(guān)系的近似集模型進(jìn)行改進(jìn),將等價(jià)關(guān)系弱化為其他二元關(guān)系,如容差關(guān)系[8]、相似關(guān)系[9]、非對(duì)稱(chēng)相似關(guān)系[10]等．文中基于容差關(guān)系對(duì)知識(shí)的完全依賴和不完全依賴給出了定義,并給出了相關(guān)性質(zhì)．

屬性約簡(jiǎn)[11-12]是粗糙集理論的核心內(nèi)容之一,可以從信息系統(tǒng)中去除冗余知識(shí),從而得到較為精簡(jiǎn)的知識(shí)．在完備信息系統(tǒng)中,關(guān)系屬性約簡(jiǎn)已經(jīng)有很多有效的方法．由于信息缺失現(xiàn)象廣泛存在,在不完備環(huán)境下對(duì)屬性約簡(jiǎn),也引起了人們的廣泛關(guān)注．如文獻(xiàn)[13]中分析了一種基于下近似二進(jìn)制可分辨矩陣,并給出了一種直接的約簡(jiǎn)算法;文獻(xiàn)[14]以相似關(guān)系作為不可分辨關(guān)系,以屬性重要度為啟發(fā)提出了一種基于相似關(guān)系的屬性約簡(jiǎn)方法．文中通過(guò)引入知識(shí)粒度[15]、知識(shí)依賴度[16]等概念,對(duì)不完備信息系統(tǒng)的屬性重要度進(jìn)行了定義,提出了兩個(gè)對(duì)屬性進(jìn)行約簡(jiǎn)的算法,并通過(guò)實(shí)驗(yàn)證明算法可以得到最小約簡(jiǎn).

1 概念術(shù)語(yǔ)

在現(xiàn)實(shí)生活中,絕大多數(shù)信息系統(tǒng)都是不完備的,屬性缺失是其主要問(wèn)題．對(duì)于一個(gè)對(duì)象,一些屬性值遺漏或不能確定.通常未知屬性有兩種不同解釋,即遺漏型空值和缺席型空值[17]．文中研究遺漏型空值,即未知屬性實(shí)際上是存在的,只是由于某種原因,目前未能獲得該值．

定義1一個(gè)不完備信息系統(tǒng)(incomplete information system, IIS)[5]為四元組S=(U,AT,V,f),其中,U為論域，是一個(gè)非空有限對(duì)象集;AT為屬性的非空有限集合,對(duì)于?a∈AT, 有a:U→Va;V為屬性值域,其中Va為屬性a的值域,可包含空值“*”;f為信息函數(shù),對(duì)于?a∈A,?x∈U,有f(x,a)?Va．

定義2設(shè)S=(U,AT,V,f)為一個(gè)不完備信息系統(tǒng),對(duì)于?a∈AT,則基于a容差關(guān)系，SIM(a)定義[18]為:

SIM({a})={(x,y)∈U×U|a(x)=a(y)∨a(x)=*∨a(y)=*}

(1)

定義3對(duì)于 ?A?AT,記[19]

SIM(A)=∩a∈ASIM({a})

(2)

顯然SIM(A)為一個(gè)容差關(guān)系,具有自反性和對(duì)稱(chēng)性,而不滿足傳遞性．

定義4對(duì)于?A?AT,SA(x)表示對(duì)象集[19]{y∈U|(x,y)∈SIM(A)}.

對(duì)于A而言,SA(x)為與x可能可分的對(duì)象的最大集合．DA(x)表示對(duì)象集{y∈U|(x,y)?SIM(A)};對(duì)于A而言,DA(x)為與x可能不可分的對(duì)象的最大集合．令U/SIM(A)={SA(x)|x∈U}表示分類(lèi),U/SIM(A)中的任何元素稱(chēng)為相容類(lèi)．

定義5設(shè)S=(U,AT,V,f)是一個(gè)不完備信息系統(tǒng),?X?U,?A?AT,X基于容差關(guān)系的下、上近似集[20]分別為

A(X)={x∈U|SA(x)?X}

(3)

(4)

2 不完備信息系統(tǒng)下的知識(shí)依賴度

定義6容差關(guān)系SIM(a)可以等價(jià)為關(guān)系R,關(guān)系R的相容度cmpbl(R)定義為：

cmpbl(R)=|{(x,y):(x,y)∈R}|

(5)

實(shí)際上,R的相容度cmpbl(R)就是R的基數(shù),即cmpbl(R)=|R|．

定義7關(guān)系R的粒度定義為：

(6)

式中,n為論域中元素的個(gè)數(shù),n=|U|．

定義8在不完備信息系統(tǒng)中,對(duì)于任意屬性a, 定義屬性a的相容度為：

cmpbl(a)=cmpbl(Ra)

(7)

式中,Ra為由屬性a所生成的容差關(guān)系,即Ra=SIM(a)．

定義9在不完備信息系統(tǒng)中,對(duì)于任意屬性子集P,定義屬性子集P的相容度為：

cmpbl(P)=cmpbl(Rp)

(8)

式中，Rp為由屬性子集P所生成的容差關(guān)系,即Rp=SIM(P)．

于是,屬性及屬性子集的相容度具有下列特性:

(1)cmpbl(a,b)=cmpbl(Ra∩Rb)，其中Ra和Rb分別為屬性a和b構(gòu)成的容差關(guān)系．

(2)cmpbl(a,b)≤min{cmpbl(Ra),cmpbl(Rb)}.

(3)cmpbl(a1,a2,…,an)=

cmpbl(Ra1∩Ra2∩…∩Ran)≤

cmpbl(Rak1∩Rak2∩…∩Rakl)

式中,{k1,k2, …,kl}?{1,2…,n}.

(4) 0≤cmpbl(a,b)≤n2．

(5) 當(dāng)所有對(duì)象在屬性a和屬性b上值相等時(shí),cmpbl(a)=cmpbl(b),gd(a)=gd(b)．

(6) 當(dāng)所有對(duì)象在屬性a和屬性b上值都不為*，且都不相等或相異時(shí),cmpbl(a,b)=0．

對(duì)于不完備信息系統(tǒng),定義屬性間的完全依賴關(guān)系如下.

定義10對(duì)于不完備信息系統(tǒng)中屬性a和b,若對(duì)?x,y,當(dāng)f(x,a)=f(y,a)∨f(x,a)=*∨f(y,a)=* 時(shí),必有f(x,b)=f(y,b)∨f(x,b)=*∨f(y,b)=*,則稱(chēng)屬性b完全依賴于屬性a,記為a?b,或a→b．

定理1當(dāng)a→b時(shí),有：

(1)Ra?Rb.

(2) 對(duì)?x∈U,Sa(x)?Sb(x).

(3)cmpbl(Ra)≤cmpbl(Rb)．

證明:(1) 當(dāng)a→b時(shí),對(duì)任意x,y,當(dāng)f(x,a)=f(y,a)∨f(x,a)=*∨f(y,a)=*有

f(x,b)=f(y,b)∨f(x,b)=*∨f(y,b)=*,即(x,y)∈Ra?(x,y)∈Rb,所以,Ra?Rb．

(2) 對(duì)?y,若y∈Sa(x),即(x,y)∈Ra,必有(x,y)∈Rb,則y∈Sb(x)．于是,Sa(x)?Sb(x)．

(3) 由Ra?Rb,必有：

cmpbl(Ra)≤cmpbl(Rb)．

定義11對(duì)于不完備信息系統(tǒng)屬性子集P和Q,若對(duì)?a∈P,?b∈Q,?x,y∈U,x≠y,都有當(dāng)f(x,a)=f(y,a)∨f(x,a)=*∨f(y,a)=*時(shí),必有f(x,b)=f(y,b)∨f(x,b)=*∨f(y,b)=*．則稱(chēng)屬性子集Q完全依賴于屬性子集P,記為P→Q．

定理2對(duì)于不完備信息系統(tǒng)中屬性子集P和Q,P→Q當(dāng)且僅當(dāng)?a∈P,?b∈Q,a→b．

定理3當(dāng)P→Q時(shí),有：

(1)RP?RQ.

(2) 對(duì)?x∈U,SP(x)?SQ(x).

(3)cmpbl(RP)≤cmpbl(RQ)．

對(duì)于一個(gè)不完備信息系統(tǒng),兩個(gè)屬性之間不一定都具有完全依賴性,通?？赡苤淮嬖诓糠忠蕾嚦潭鹊年P(guān)系．文中將從更廣義的角度考慮兩種不完全依賴情況下知識(shí)依賴度的計(jì)算方案．

首先從單屬性之間的部分依賴度定義開(kāi)始,接著再討論屬性子集之間的部分依賴度．

情況1:當(dāng)屬性a,b分別為條件屬性與決策屬性,且b中不含有空值時(shí).

(9)

情況2:當(dāng)屬性a,b均為條件屬性,且a和b均可能包含空值時(shí).

定義13設(shè)a和b為兩個(gè)屬性,定義b以依賴度k依賴于a,則：

(10)

不難驗(yàn)證,

(11)

k=1 iffk=gd(Ra∩Rb)=gd(Ra)

對(duì)于在前面所定義的完全依賴,由a→b,必有Ra?Rb,即當(dāng)b完全依賴于a時(shí),按此式計(jì)算得到的b依賴于a的依賴度k=1．由此可見(jiàn),完全依賴是部分依賴的特例．

當(dāng)k(a,b)=1時(shí),記a?b．k(a,b)=0

iffgd(Ra∩Rb)=0 iffRa∩Rb=?．

當(dāng)k=0時(shí),b不依賴于a．

定義14對(duì)兩個(gè)屬性子集P和Q,Q依賴于P的依賴度定義為:

(12)

k(P,Q)=1,gd(RP∩RQ)=gd(RP) iffRP?RQ，又因,gd(RP∩RQ)≤{gd(RP),gd(RQ)}，當(dāng)RP?RQ時(shí),gd(RP)≤gd(RQ)．

以汽車(chē)的屬性值[21]為例,說(shuō)明不完備信息系統(tǒng)中的知識(shí)依賴度及其性質(zhì)．

例1設(shè)U={1,2,3,4,5,6}，AT={P,M,S,X},式中P,M,S,X分別表示價(jià)格、里程、規(guī)格、最大速度;V={high,low,full,compact,*}．則表1給出了一個(gè)不完備信息系統(tǒng)．

每個(gè)屬性子集或由該屬性子集生成的關(guān)系的粒度計(jì)算結(jié)果為:

表1 一個(gè)不完備信息系統(tǒng)Table 1 An incomplete information system

3 不完備信息系統(tǒng)下知識(shí)依賴度的性質(zhì)

考慮條件屬性可能含有空值的情況，條件屬性和決策屬性不含空值時(shí),可以看作該情況的一種特例．

3.1 完全依賴下依賴度的特性

定理4(傳遞性)若a→b,b→c則a→c．

按前面定義的完全依賴，a→biffRa?Rb,則Ra?Rb,Rb?Rc?Ra?Rc．

現(xiàn)在用新定義的依賴度加以證明．

得gd(Ra∩Rb)=gd(Ra)．

同理可得gd(Rb∩Rc)=gd(Rb)

則gd(Ra∩Rc)=gd(Ra∩Rb∩Rc)=gd(Ra∩Rb)=gd(Ra)

例1在表1中,S?P，P?M，S?M,因此,定理4成立．

定理5(增廣性)若a→b則a,c→b,c.

由Ra∩Rc?Rb∩Rc，可以得到Ra,c?Rb,c因此a,c→b,c成立．

定理6(左增廣性)若a→b,則a,c→b．

證明：由Ra?Rb,可以得到Ra,c=Ra∩Rc?Rb因此a,c→b成立．

3.2 不完全依賴下依賴度的特性

4 屬性的重要度分析

定義15已知不完備信息系統(tǒng)IIS=(U,AT∪j5i0abt0b,f,V),對(duì)于?A?AT,d為決策屬性．若A-{a}?A,則SIM(A)=SIM(A-a)．

證明：

由A-{a}?A可以得到SIM(A)?SIM(A-{a})，

因?yàn)锳-{a}?A所以SIM(A-{a})?SIM(A)，

因此SIM(A)=SIM(A-{a}).

(13)

定義17給定不完備信息系統(tǒng)IIS=(U,AT,f,V)．對(duì)于?A?AT,a∈A≠?．已知屬性a在A中的重要度是由A中去掉a后引起的知識(shí)粒度變化的大小來(lái)衡量的．也就是說(shuō),對(duì)于一個(gè)屬性集合,去掉一個(gè)屬性引起的知識(shí)粒度變化量越大,該屬性對(duì)此屬性集就越重要．若SigA(a)>0,即gd(A∪j5i0abt0b)

定義18給定不完備信息系統(tǒng)IIS=(U,AT,f,V)．對(duì)于?A?AT,A中所有核屬性所構(gòu)成的屬性子集記為CORE(A),即CORE(A)={a:SigA(a)>0,a∈A}．

定義19給定不完備信息系統(tǒng)IIS=(U,AT,f,V)．對(duì)于?A?AT,B?A,若SIM(B)=SIM(A),且不存在B′?B，使得SIM(B′)=SIM(A),則稱(chēng)B為A的一個(gè)約簡(jiǎn)．A的所有約簡(jiǎn)作為元素構(gòu)成的集合記為RED(A)．

可以證明,CORE(A)=B,B∈RED(A)．

定理11給定不完備信息系統(tǒng)IIS=(U,AT,f,V)．對(duì)于?A?AT,a∈A,則下列結(jié)論等價(jià).

(1)a是A中不重要的,即SigA(a)=0.

(2)a是A中冗余的,即SIM(A-{a})=SIM(A).

(3)A?a.

(4)A-{a}?A.

(5)k=k(A-{a},A)=1．

5 求屬性約簡(jiǎn)的啟發(fā)式算法設(shè)計(jì)

依據(jù)屬性重要度作為啟發(fā)式信息可設(shè)計(jì)求信息系統(tǒng)屬性約簡(jiǎn)的兩個(gè)算法,一個(gè)從核屬性集出發(fā),采用自底向上的方法,通過(guò)每次加入一個(gè)重要度大的屬性來(lái)求解,另一個(gè)采用自頂向下的方法從整個(gè)屬性集出發(fā),每次去掉一個(gè)重要度最小的屬性來(lái)求解．

算法1由核屬性集出發(fā)每次加入一個(gè)屬性重要度最大的屬性求最小約簡(jiǎn).

輸入:不完備信息系統(tǒng)IIS=(U,AT∪j5i0abt0b,f,V),其中?A?AT.

輸出:一個(gè)最小約簡(jiǎn)B∈RED(A).

步驟：

(1) 求核，CORE(A)對(duì)任意屬性a∈A,計(jì)算SigA∪j5i0abt0b(a),所有在A中SigA∪j5i0abt0b(a)值大于0的屬性都是核屬性,即CORE(A)={a:SigA(a)>0,a∈A}．

(2) 初始化B值，B=CORE(A)．

(3) 判斷SIM(B)=SIM(A)是否成立,若成立,則轉(zhuǎn)步驟(6),否則轉(zhuǎn)步驟(4)．

(4) 計(jì)算所有屬性x∈A-B的值SigB∪{x}(x),取屬性a，滿足下列條件:

即具有最大重要度的屬性a．

(5)B=B∪{a},將步驟(4)中計(jì)算的具有最大重要度的屬性a加入B．

(6) 輸出A的一個(gè)最小約簡(jiǎn)B．

令B=CORE(A)={S,X},因?yàn)镾IM(B)=SIM(A),所以得到一個(gè)最小約簡(jiǎn)REDUCT=B={S,X}．

算法2由屬性集出發(fā)每次減少1個(gè)重要度最小的屬性直到求出一個(gè)最小約簡(jiǎn).

輸入:不完備信息系統(tǒng)IIS=(U,AT∪j5i0abt0b,f,V),其中?A?AT.

輸出:A的約簡(jiǎn)RED.

步驟：

(1) 令RED=A.

(3) 判斷，若SIM(RED-{a})≠SIM(A),則轉(zhuǎn)步驟(4),否則RED=RED-{a},將屬性a從RED中刪除,轉(zhuǎn)步驟(2)．

(4) 輸出約簡(jiǎn)RED，算法結(jié)束．

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

為了進(jìn)一步考察文中算法的有效性,選取了5組UCI數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析,數(shù)據(jù)信息的基本描述如表2．實(shí)驗(yàn)環(huán)境為PC機(jī),Windows 8操作系統(tǒng),MATLAB R2014a實(shí)驗(yàn)平臺(tái)．

6.1 結(jié)果對(duì)比

針對(duì)不完備信息系統(tǒng),選用表2中的5組UCI數(shù)據(jù),對(duì)文中的兩個(gè)算法及文獻(xiàn)[22]中的約簡(jiǎn)算法進(jìn)行約簡(jiǎn)個(gè)數(shù)比較．

表2 文中算法與文獻(xiàn)[22]中算法進(jìn)行屬性約簡(jiǎn)結(jié)果比較Table 2 Comparison of the reduction result between our algorithm and the algorithm in literature[22]

文中用UCI中的數(shù)據(jù)庫(kù)計(jì)算決策精度(正確率):一部分?jǐn)?shù)據(jù)作訓(xùn)練數(shù)據(jù)提取出決策,另一部份數(shù)據(jù)作測(cè)試,正確率可計(jì)算出來(lái)．如用類(lèi)似于1/10法,有100個(gè)數(shù)據(jù),每次用90個(gè)數(shù)據(jù)提取決策規(guī)則,用剩下的10個(gè)數(shù)據(jù)作測(cè)試數(shù)據(jù),得到每次正確個(gè)數(shù)的總和再除以10得到平均正確率．圖1為算法1與算法2對(duì)表2中5組UCI數(shù)據(jù)的分類(lèi)精度．

圖1 算法1與算法2分類(lèi)精度對(duì)比Fig.1 Comparison of classification accuracy between algorithm 1 and algorithm 2

6.2 結(jié)果分析

從表3的結(jié)果可以分析得出:從約簡(jiǎn)個(gè)數(shù)來(lái)看,文中算法與其他文獻(xiàn)相比,屬性個(gè)數(shù)少于或等于其結(jié)果．

表3 數(shù)據(jù)集描述Table 3 Data sets description

根據(jù)圖1,從核屬性集出發(fā),采用自底向上的方法對(duì)屬性約簡(jiǎn)的決策精度明顯高于自頂向下式的約簡(jiǎn)．以Congressional Voting數(shù)據(jù)集為例,算法1的決策精度為0.632 2,0.613 5,0.609 5,0.609 0,0.627 4,0.632 7,0.625 2,0.622 8,0.634 4,0.606 9；算法2的決策精度為0.566 0,0.554 7,0.517 5,0.538 5,0.537 9,0.505 9,0.552 0,0.521 8,0.563 5,0.552 3．對(duì)比分析可以得到,從核屬性集出發(fā),采用自底向上的方法,通過(guò)每次加入一個(gè)重要度大的屬性對(duì)屬性進(jìn)行約簡(jiǎn)，決策精度高．

7 結(jié)論

為了對(duì)屬性進(jìn)行約簡(jiǎn),文中首先研究知識(shí)之間的依賴關(guān)系．在基于容差關(guān)系的粗糙集模型中,研究了完全依賴、部分依賴及其依賴度等概念，接著探討了不完備信息系統(tǒng)中知識(shí)依賴的性質(zhì),得到的結(jié)論用例子加以證明．接著對(duì)不完備信息系統(tǒng)的屬性重要度進(jìn)行了定義,提出了兩個(gè)對(duì)屬性進(jìn)行約簡(jiǎn)的算法,算法1是一種啟發(fā)式的約簡(jiǎn)算法,根據(jù)核屬性進(jìn)行約簡(jiǎn)．算法2從整個(gè)屬性集出發(fā),采用自頂向下的方法．通過(guò)實(shí)驗(yàn)證明,從核屬性集出發(fā),采用自底向上方法對(duì)屬性約簡(jiǎn)，決策精度明顯高于自頂向下式的約簡(jiǎn)．

對(duì)IIS中知識(shí)依賴的研究,使得知識(shí)依賴在不完備信息系統(tǒng)即遇到屬性為空值的情況時(shí),也能夠具有新的合理解釋并進(jìn)行分析處理,從而為不完備信息系統(tǒng)中的屬性約簡(jiǎn)提供新方法．今后還將進(jìn)一步研究不完備信息系統(tǒng)中的粗糙集模型的擴(kuò)展,以獲得更多更好的粗糙集模型來(lái)處理不完備信息,提高其粗糙集的近似精度．