變精度極大相容塊粗糙集模型及其屬性約簡(jiǎn)*

孫 妍，米據(jù)生，馮 濤，李磊軍，梁美社,3

1.河北師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，石家莊 050024

2.河北科技大學(xué) 理學(xué)院，石家莊 050018

3.石家莊職業(yè)技術(shù)學(xué)院 科技發(fā)展與校企合作部，石家莊 050081

1 引言

Pawlak 于1982 年提出了粗糙集理論[1]，該理論是知識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖掘的重要工具，為處理不精確數(shù)據(jù)和不完全信息的問(wèn)題提出了一個(gè)新的框架，已被廣泛地應(yīng)用于模式識(shí)別、人工智能以及智能信息處理等領(lǐng)域[2-4]。

經(jīng)典Pawlak 粗糙集模型處理的信息系統(tǒng)都是完備的，在實(shí)際生活中由于各種因素，信息系統(tǒng)中的某些屬性值可能出現(xiàn)缺失[5]，文獻(xiàn)[6]對(duì)這種不完備的信息系統(tǒng)做出兩種解釋：一是“丟失”值，即該值被擦除或者沒(méi)有被插入到數(shù)據(jù)集中；二是“不關(guān)心”值，理解為來(lái)自于該屬性值域中的任意值。在通常的知識(shí)發(fā)現(xiàn)中，一般先對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，通過(guò)對(duì)數(shù)據(jù)分析，填補(bǔ)缺失的數(shù)據(jù)，或者從樣本數(shù)據(jù)出發(fā)，通過(guò)某種訓(xùn)練算法，推算缺失數(shù)據(jù)[7]。

基于不完備信息系統(tǒng)的知識(shí)發(fā)現(xiàn)是目前研究的熱點(diǎn)問(wèn)題。近年來(lái)許多學(xué)者在經(jīng)典粗糙集模型上進(jìn)行擴(kuò)展，對(duì)等價(jià)關(guān)系進(jìn)行弱化，提出了基于相似關(guān)系、相容關(guān)系以及鄰域關(guān)系等構(gòu)造新模型的方法來(lái)解決不完備信息系統(tǒng)的問(wèn)題[8-10]。文獻(xiàn)[7]在不完備信息系統(tǒng)中提出了極大相容塊的定義，利用極大相容塊在只含有缺失值為“不關(guān)心”值的不完備信息系統(tǒng)上構(gòu)造精度較高的上下近似，并提出了一種保持廣義決策不變的屬性約簡(jiǎn)方法。文獻(xiàn)[11-13]給出了極大相容塊的多種快速算法，這樣使得極大相容塊更容易獲得。文獻(xiàn)[14]在文獻(xiàn)[7]的基礎(chǔ)上，利用特征集和極大相容塊對(duì)不完備數(shù)據(jù)集進(jìn)行信息挖掘，分別考慮在有“丟失”值和“不關(guān)心”值、只有“丟失”值的兩種不完備系統(tǒng)下的特征值和極大相容塊生成的二元關(guān)系之間的性質(zhì)。然而利用相似關(guān)系拓展的粗糙集模型與經(jīng)典粗糙集模型具有相同的局限性，即所處理的分類必須是肯定的或者是完全確定的。文獻(xiàn)[15]提出了基于變精度粗糙集模型的知識(shí)約簡(jiǎn)方法。文獻(xiàn)[16-17]研究了不完備信息系統(tǒng)上的多粒度粗糙集模型。文獻(xiàn)[18]研究了不完備信息系統(tǒng)上的三支決策模型。屬性約簡(jiǎn)是粗糙集理論中最重要的研究?jī)?nèi)容之一，是為了簡(jiǎn)化原始的信息系統(tǒng)但不影響信息系統(tǒng)的分類能力，從而刪除冗余屬性的過(guò)程[19-21]。本文在文獻(xiàn)[14]的基礎(chǔ)上，結(jié)合變精度的思想，構(gòu)造了基于極大相容塊的變精度粗糙集模型。

2 基礎(chǔ)知識(shí)

在不完備信息系統(tǒng)中，用U表示對(duì)象集，A表示屬性集，a∈A。

在不完備信息系統(tǒng)中，對(duì)含有缺失值的對(duì)象解釋是：如果a(x)=*，則有對(duì)象x屬于每個(gè)[(a,v)]中。如果a(x)=?，則有對(duì)象x不屬于任意[(a,v)]中。因此兩種解釋的缺失值在不完備信息系統(tǒng)中具有不同的含義。于是將不完備信息系統(tǒng)分成三種：第一種只含有“*”的缺失值的不完備信息系統(tǒng)（如表1）；第二種含有“*”和“?”的缺失值的不完備信息系統(tǒng)；第三種只含有“?”的缺失值的不完備信息系統(tǒng)[6]。

Table 1 Automobile information sheet DS1表1 汽車信息表DS1

定義1在不完備信息系統(tǒng)IS=(U,A,V)中，B?A，a,b∈B，Va表示屬性a的值域。任取x∈U，定義：

為對(duì)象x的特征集。特別地，當(dāng)B={a}，且a(x)=?，則KB(x)={x}。

文獻(xiàn)[14]是在三種不完備信息系統(tǒng)分別描述了特征集的構(gòu)造，定義1 給出了特征集的一個(gè)統(tǒng)一的表達(dá)形式。

表1中，A={P,M,S,X}，對(duì)象2 的特征集為KA(2)=[(P,low)]?([(M,high)]?[(M,low)])?[(S,full)]?[(X,low)]={2,6}，其中當(dāng)a=M時(shí)，有a(2)=*。

定義2[14]在不完備信息系統(tǒng)IS=(U,A,V)中，B?A，在對(duì)象集U上定義一個(gè)二元關(guān)系R(B) ：?x,y∈U，(x,y)∈R(B)當(dāng)且僅當(dāng)y∈KB(x)。

當(dāng)不完備信息系統(tǒng)只含有“*”時(shí)，二元關(guān)系R(B)滿足自反和對(duì)稱性，與文獻(xiàn)[7]中定義的相似關(guān)系SIM(B)相同，其中SIM(B)={(x,y)∈U×U|?a∈B，a(x)=a(y)或者a(x)=* 或者a(y)=*}。當(dāng)不完備信息系統(tǒng)只含有“?”時(shí)，二元關(guān)系R(B)滿足自反、對(duì)稱和傳遞性，即等價(jià)關(guān)系。當(dāng)不完備信息系統(tǒng)含有“*”和“?”時(shí)，二元關(guān)系R(B)只滿足自反性，則R(B)稱為非對(duì)稱相似關(guān)系。

文獻(xiàn)[7]引入了極大相容塊的概念，描述了對(duì)象相似的最大的集合，即極大相容塊中的對(duì)象是不可辨識(shí)的。

定義3[7]設(shè)IS=(U,A,V)是不完備信息系統(tǒng)，B?A，Y?U，若?x,y∈Y，都有(x,y)∈R(B)，則稱Y是由B確定的相容塊。進(jìn)一步，若不存在相容塊X?U，使得Y?X，則稱Y是由B確定的極大相容塊。

用C(B)表示由屬性集B確定的全體極大相容塊的集合，記C(B)={Y1,Y2,…,Yh}，其中Yi?U。Cx(B)={Y|Y∈C(B),x∈Y}表示含有對(duì)象x的極大相容塊的集合。

定義4[14]設(shè)IS=(U,A,V)是不完備信息系統(tǒng)，B?A，定義一個(gè)U上的二元關(guān)系S(B)?U×U：任意x,y∈Y，(x,y)∈S(B)當(dāng)且僅當(dāng)存在Y∈C(B)，使得x,y∈Y。

顯然有二元關(guān)系S(B)滿足自反性和對(duì)稱性，且S(B)?R(B)。

性質(zhì)1[14]在不完備信息系統(tǒng)IS=(U,A,V)中，B?A，x∈U，則對(duì)于?Y∈Cx(B)，有Y?KB(x)。

3 基于極大相容塊的廣義變精度粗糙集模型及其屬性約簡(jiǎn)

3.1 廣義變精度粗糙集模型

本節(jié)將不完備信息系統(tǒng)中基于極大相容塊的粗糙集模型[7]推廣為變精度粗糙集模型。

首先給出子系統(tǒng)中的極大相容塊與原系統(tǒng)中的極大相容塊之間的關(guān)系。

性質(zhì)2在不完備信息系統(tǒng)IS=(U,A,V)中，B?A，?X∈C(A)，存在Y∈C(B)，使得X?Y。且C(B)中的極大相容塊Y都是由C(A)中的一些極大相容塊X的并構(gòu)成的，即：

證明首先證明X?Y，若X∈C(A)，由定義3，?x,y∈X，則有(x,y)∈R(A)，因?yàn)镽(A)?R(B)，所以(x,y)∈R(B)，X是由屬性集B確定的相容塊，但不一定是極大的?？隙ù嬖跇O大相容塊Y∈C(B)，使得X?Y。

接下來(lái)證明Y={X|X∈Cx(A)}。易知Y?{X|X∈Cx(A)}，下證{∈Cx(A)} ?Y。對(duì)于?y∈{X|X∈Cx(A)}，則 有x,y∈X,B?A，(x,y)∈R(A)，有(x,y)∈R(B)，又因?yàn)閄?Y，所以{X|X∈Cx(A)}?Y?！?/p>

定義5在不完備信息系統(tǒng)IS=(U,A,V)中，對(duì)于任意B?A，任取X?U，β∈(0.5,1]，稱

為X關(guān)于B基于C(B)的β-下近似，稱

為X關(guān)于B基于C(B)的β-上近似。其中D是P(U)上的包含度，|Y|表示Y中元素的個(gè)數(shù)，即：

稱此模型為基于極大相容塊的悲觀變精度粗糙集模型。

定義6在不完備信息系統(tǒng)IS=(U,A,V)中，對(duì)于任意B?A，任取X?U，β∈(0.5,1]，稱

為X關(guān)于B基于C(B)的β-下近似，稱

為X關(guān)于B基于C(B)的β-上近似。

稱此模型為基于極大相容塊的樂(lè)觀變精度粗糙集模型。

定義7在不完備信息系統(tǒng)IS=(U,A,V)中，對(duì)于任意B?A，任取X?U，β∈(0.5,1]，令、分別表示X關(guān)于B的悲觀精度和樂(lè)觀精度，即：

性質(zhì)3

證明（1）?x∈，則?Y∈Cx(B)，滿足D(X/Y)≥β，故x∈。

（2）因?yàn)棣隆?0.5,1]，β＞1-β由（1）可知，D(X/Y)≥1-β，故。

（3）由（1）可證。 □

由性質(zhì)3（3）可知，與基于極大相容塊的悲觀變精度粗糙集模型相比，樂(lè)觀變精度粗糙集模型的精度更高。

定義8在不完備信息系統(tǒng)IS=(U,A,V)中，B?A，任取X?U，則和分別稱為X關(guān)于B的β-上下近似，β∈(0.5,1]，即：

定理1在不完備信息系統(tǒng)IS=(U,A,V)中，B?A，任取X?U，則有：

證明（1）顯然有，接下來(lái)要證，?y∈，y屬于某一個(gè)極大相容塊Y∈C(B)，即Y∈Cy(B)，并且D(X/Y)≥β，則y∈。

同理可以證得（2）成立。 □

定理1 表明在不完備信息系統(tǒng)中利用極大相容塊定義的兩種上下近似算子是相同的。下近似算子統(tǒng)一用表示，上近似算子用表示。

稱DS=(U,A,V,D,G)為不完備決策信息系統(tǒng)，其中(U,A,V)是不完備信息系統(tǒng)，D是決策集，G是決策值域。

定理2設(shè)DS=(U,A,V,D,G)是不完備決策信息系統(tǒng)，B?A，0.5 ＜α,β≤1，RD是U上由D導(dǎo)出的等價(jià)關(guān)系，U/RD={D1,D2,…,Dr}，容易驗(yàn)證和滿足以下性質(zhì)：

（1）若X1?X2，則：

預(yù)警發(fā)布后加強(qiáng)大壩、溢洪道、輸水洞、排水溝、濾水壩址等部位的巡視檢查，庫(kù)水位每上升2 m巡查一次，同時(shí)監(jiān)測(cè)測(cè)壓管水位，發(fā)現(xiàn)問(wèn)題及時(shí)報(bào)告處理。當(dāng)水位達(dá)到89.5 m即溢洪道底坎高程時(shí)，加強(qiáng)對(duì)溢洪道和閘門的檢查，同時(shí)注意及時(shí)打撈閘門附近的大型漂浮物。

（2）若α≤β，則：

3.2 廣義變精度粗糙集模型上的屬性約簡(jiǎn)

基于上一節(jié)中提到的廣義變精度粗糙集模型，本節(jié)定義幾種屬性約簡(jiǎn)的概念和該模型上的β-上(下)分布約簡(jiǎn)方法。

定義9設(shè)DS=(U,A,V,D,G)是不完備決策信息系統(tǒng)，對(duì)于B?A，若C(B)=C(A)，則稱B是分塊協(xié)調(diào)集。進(jìn)一步，若?B′?B，C(B′)≠C(A)，那么B是分塊約簡(jiǎn)。

定義10設(shè)DS=(U,A,V,D,G)是不完備決策信息系統(tǒng)，B?A，U/RD={D1,D2,…,Dr}。對(duì)于β∈(0.5,1]，記：

定理3設(shè)DS=(U,A,V,D,G)是不完備決策信息系統(tǒng)，分塊協(xié)調(diào)集必是β-上（下）分布協(xié)調(diào)集。

證明由屬性集A確定的極大相容塊的集合為C(A)={X1,X2,…,Xm}，若B?A，B為該系統(tǒng)的一個(gè)分塊約簡(jiǎn)，則有C(B)=C(A)，由定義6 可知，=，?Dj∈U/RD，分塊協(xié)調(diào)集必是樂(lè)觀β-下分布協(xié)調(diào)集，同理可證分塊協(xié)調(diào)集是悲觀β-下分布協(xié)調(diào)集和β-上分布協(xié)調(diào)集。 □

定義11設(shè)DS=(U,A,V,D,G)是不完備決策信息系統(tǒng)，β∈(0.5,1],U/RD={D1,D2,…,Dr},C(A)={X1,X2,…,Xm}，記：

注1當(dāng)信息系統(tǒng)中a(x)=?時(shí)，該對(duì)象x所在極大相容塊與其他極大相容塊的辨識(shí)屬性集一定包含屬性a。

定理4設(shè)DS=(U,A,V,D,G)是不完備決策信息系統(tǒng)，令C(A)={X1,X2,…,Xm}，β-上（下）分布可辨識(shí)屬性集具有以下性質(zhì)，其中i,k,s≤m：

證明與文獻(xiàn)[15]中定理3.3的證明過(guò)程類似。□

定理5設(shè)DS=(U,A,V,D,G)是不完備決策信息系統(tǒng)，B?A。

證明一方面，當(dāng)時(shí)，{Dj:Xi?，設(shè)B是β-上分布協(xié)調(diào)集，由定義10 可知，即?Dj∈U/RD=，因此有。由性質(zhì)2 可知，Xi、Xk肯定也是由屬性集B確定的相容塊，但不一定是由屬性集B確定的極大相容塊。存在極大相容塊Yi,Yk∈C(B)，Xi?Yi，Xk?Yk，則有，因此存在a∈B，使得a(Yi)≠a(Yk)，那么a(Xi)≠a(Xk)，即證得該式子B?(Xi,Xk)≠?成立。另一方面，?Xi,Xk∈C(A)，當(dāng)時(shí)，假設(shè)B?(Xi,Xk)=?，則?a∈B，a(Xi)=a(Xk)，由性質(zhì)2 知，Yi,Yk∈C(B)，Xi?Yi，Xk?Yk，a(Yi)=a(Yk)，一定存在al∈A，且al?B，使得al(Xi)≠al(Xk)。故存在Dj∈U/RD，有，則B不是β-上分布協(xié)調(diào)集。

同理可以證得（2）和（3）成立。 □

在不完備決策信息系統(tǒng)DS=(U,A,V,D,G) 中，(Xi,Xk),i,k≤m)表示為不完備DS的β-上（下）分布可辨識(shí)矩陣，A={a1,a2,…,as}，記：

其中，i,k≤m，t=1,2,3，Mβ t稱為β-上（下）分布可辨識(shí)公式。

4 實(shí)例分析

對(duì)于只含有“?”的缺失值的不完備決策信息系統(tǒng)[7]，R(A)滿足自反、對(duì)稱和傳遞性。S(A)?R(A),故極大相容塊構(gòu)成的集合C(A)不僅是U上的一個(gè)覆蓋還是一個(gè)劃分，因此在這類決策信息系統(tǒng)中與完備決策信息系統(tǒng)中利用第3 章中的方法求取屬性約簡(jiǎn)的過(guò)程相同。

下面在另外兩種不同的不完備決策信息系統(tǒng)中驗(yàn)證上一章給出的屬性約簡(jiǎn)方法。

例1表1 是只含有“*”的不完備信息表DS1，條件屬性集為A={P,M,S,X}，決策屬性集為D={D1=good,D2=poor,D3=excellent}，計(jì)算0.7-上分布約簡(jiǎn)和0.7-下分布約簡(jiǎn)。

記μB(Y)=(D(D1/Y),D(D2/Y),…,D(Dr/Y))為極大相容塊Y關(guān)于屬性集B在不完備信息系統(tǒng)中的廣義決策分布函數(shù)。

由決策屬性D在U上產(chǎn)生劃分為：

由定義1 可得對(duì)象的特征集：

由條件屬性集A確定的極大相容塊的集合為：

由定義2 可得對(duì)象的特征集生成的二元關(guān)系：

由定義4 可得極大相容塊生成的二元關(guān)系：

得到極大相容塊的廣義決策分布為：

決策等價(jià)類U/RD的0.7-上近似：

從而得到極大相容塊之間的可辨識(shí)矩陣（表2），則不完備決策信息系統(tǒng)的0.7-上分布辨識(shí)公式：

Table 2 Discernible attribute matrix of DS1表2 DS1 的可辨識(shí)屬性矩陣

由此可知{S,X}是此不完備決策信息系統(tǒng)的0.7-上分布約簡(jiǎn)。同樣計(jì)算樂(lè)觀的0.7-下分布約簡(jiǎn)的結(jié)果也是{S,X}。

屬性約簡(jiǎn)的結(jié)果與文獻(xiàn)[5]和文獻(xiàn)[22]相同，與文獻(xiàn)[22]中基于對(duì)象間的可辨識(shí)矩陣比較，本文提出的基于極大相容塊的方法壓縮了可辨識(shí)矩陣規(guī)模，進(jìn)一步簡(jiǎn)化了運(yùn)算過(guò)程，節(jié)省了存儲(chǔ)空間。

而DS1的悲觀0.7-下分布約簡(jiǎn)的結(jié)果是{S,X,P}和{S,X,M}。

例2含有“ *”和“ ?”的不完備的決策信息表DS2（表3），決策屬性的值域?yàn)閐={d1,d2,d3}，對(duì)象集為U={x1,x2,x3,x4,x5,x6,x7,x8}，條件屬性集為A={a1,a2,a3,a4}，決策屬性d，計(jì)算0.7-上分布約簡(jiǎn)。

Table 3 Incomplete information DS2表3 不完備信息表DS2

其中由d產(chǎn)生的劃分為：

由條件屬性集A確定的極大相容塊的集合為：

極大相容塊的廣義決策分布為：

則有

從而得到各個(gè)極大相容塊之間的辨識(shí)屬性集（表4），不完備決策信息系統(tǒng)的0.7-上分布辨識(shí)公式：

Table 4 Discernible attribute matrix of DS2表4 DS2 的可辨識(shí)屬性矩陣

因此{(lán)a3,a4}和{a1,a2,a4}是此不完備決策信息系統(tǒng)DS2的0.7-上分布約簡(jiǎn)。這個(gè)結(jié)果與DS2的樂(lè)觀和悲觀的0.7-下分布約簡(jiǎn)相一致。

這個(gè)結(jié)果與DS2的樂(lè)觀和悲觀的0.7-下分布約簡(jiǎn)相一致。

基于3.1 節(jié)提出的廣義變精度粗糙集模型，給出一種計(jì)算不完備信息系統(tǒng)的β-上分布約簡(jiǎn)的算法。

為了進(jìn)一步驗(yàn)證該算法的有效性。本文在UCI數(shù)據(jù)集中選擇了5 組含缺失值的數(shù)據(jù)，數(shù)據(jù)基本信息如表5 所示。根據(jù)上述算法，其中令β=0.7，得到0.7-上分布約簡(jiǎn)結(jié)果（表6）。

Table 5 Description of data sets表5 數(shù)據(jù)集的基本信息

Table 6 Result of reduction表6 約簡(jiǎn)的結(jié)果

注2在約簡(jiǎn)結(jié)果中，數(shù)字k代表第k-1 個(gè)條件屬性。A表示該數(shù)據(jù)集的條件屬性的集合，MCB 表示極大相容塊。

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

本文將變精度粗糙集模型和極大相容塊相結(jié)合，在不完備信息系統(tǒng)中建立了基于極大相容塊的廣義變精度粗糙集模型，構(gòu)造了極大相容塊間的可辨識(shí)屬性集，進(jìn)而利用布爾計(jì)算方法獲取屬性約簡(jiǎn)。為區(qū)分兩種缺失值，對(duì)含有“?”的極大相容塊與其他極大相容塊間的可辨識(shí)屬性集做了特定的要求。此約簡(jiǎn)方法可有效地縮小可辨識(shí)矩陣的規(guī)模，進(jìn)一步簡(jiǎn)化了計(jì)算屬性約簡(jiǎn)的過(guò)程，在一定程度上能夠有效地節(jié)省計(jì)算時(shí)間和存儲(chǔ)空間。