夏冰瑩, 吳 陳

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

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

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

1 概念術(shù)語

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

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

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

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

(1)

定義3對于 ?A?AT,記[19]

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

(2)

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

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

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

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

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

(3)

(4)

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

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

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

(5)

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

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

(6)

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

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

cmpbl(a)=cmpbl(Ra)

(7)

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

定義9在不完備信息系統(tǒng)中,對于任意屬性子集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)所有對象在屬性a和屬性b上值相等時,cmpbl(a)=cmpbl(b),gd(a)=gd(b)．

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

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

定義10對于不完備信息系統(tǒng)中屬性a和b,若對?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)=*,則稱屬性b完全依賴于屬性a,記為a?b,或a→b．

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

(1)Ra?Rb.

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

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

證明:(1) 當(dāng)a→b時,對任意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) 對?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對于不完備信息系統(tǒng)屬性子集P和Q,若對?a∈P,?b∈Q,?x,y∈U,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)=*．則稱屬性子集Q完全依賴于屬性子集P,記為P→Q．

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

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

(1)RP?RQ.

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

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

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

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

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

(9)

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

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

(10)

不難驗證,

(11)

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

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

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

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

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

定義14對兩個屬性子集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時,gd(RP)≤gd(RQ)．

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

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

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

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

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

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

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∪hdd5vdt,f,V),對于?A?AT,d為決策屬性．若A-{a}?A,則SIM(A)=SIM(A-a)．

證明：

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

因為A-{a}?A所以SIM(A-{a})?SIM(A)，

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

(13)

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

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

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

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

定理11給定不完備信息系統(tǒng)IIS=(U,AT,f,V)．對于?A?AT,a∈A,則下列結(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 求屬性約簡的啟發(fā)式算法設(shè)計

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

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

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

輸出:一個最小約簡B∈RED(A).

步驟：

(1) 求核，CORE(A)對任意屬性a∈A,計算SigA∪nvthrxr(a),所有在A中SigA∪rxvrz5j(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) 計算所有屬性x∈A-B的值SigB∪{x}(x),取屬性a，滿足下列條件:

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

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

(6) 輸出A的一個最小約簡B．

令B=CORE(A)={S,X},因為SIM(B)=SIM(A),所以得到一個最小約簡REDUCT=B={S,X}．

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

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

輸出:A的約簡RED.

步驟：

(1) 令RED=A.

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

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

6 實驗分析

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

6.1 結(jié)果對比

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

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

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

圖1 算法1與算法2分類精度對比Fig.1 Comparison of classification accuracy between algorithm 1 and algorithm 2

6.2 結(jié)果分析

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

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

根據(jù)圖1,從核屬性集出發(fā),采用自底向上的方法對屬性約簡的決策精度明顯高于自頂向下式的約簡．以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．對比分析可以得到,從核屬性集出發(fā),采用自底向上的方法,通過每次加入一個重要度大的屬性對屬性進(jìn)行約簡，決策精度高．

7 結(jié)論

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

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