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

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

1.河北師范大學 數學與信息科學學院，石家莊 050024

2.河北科技大學 理學院，石家莊 050018

3.石家莊職業技術學院 科技發展與校企合作部，石家莊 050081

1 引言

Pawlak 于1982 年提出了粗糙集理論[1]，該理論是知識發現和數據挖掘的重要工具，為處理不精確數據和不完全信息的問題提出了一個新的框架，已被廣泛地應用于模式識別、人工智能以及智能信息處理等領域[2-4]。

經典Pawlak 粗糙集模型處理的信息系統都是完備的，在實際生活中由于各種因素，信息系統中的某些屬性值可能出現缺失[5]，文獻[6]對這種不完備的信息系統做出兩種解釋：一是“丟失”值，即該值被擦除或者沒有被插入到數據集中；二是“不關心”值，理解為來自于該屬性值域中的任意值。在通常的知識發現中，一般先對數據進行預處理，通過對數據分析，填補缺失的數據，或者從樣本數據出發，通過某種訓練算法，推算缺失數據[7]。

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

2 基礎知識

在不完備信息系統中，用U表示對象集，A表示屬性集，a∈A。

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

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

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

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

文獻[14]是在三種不完備信息系統分別描述了特征集的構造，定義1 給出了特征集的一個統一的表達形式。

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

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

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

文獻[7]引入了極大相容塊的概念，描述了對象相似的最大的集合，即極大相容塊中的對象是不可辨識的。

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

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

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

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

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

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

3.1 廣義變精度粗糙集模型

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

首先給出子系統中的極大相容塊與原系統中的極大相容塊之間的關系。

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

證明首先證明X?Y，若X∈C(A)，由定義3，?x,y∈X，則有(x,y)∈R(A)，因為R(A)?R(B)，所以(x,y)∈R(B)，X是由屬性集B確定的相容塊，但不一定是極大的。肯定存在極大相容塊Y∈C(B)，使得X?Y。

接下來證明Y={X|X∈Cx(A)}。易知Y?{X|X∈Cx(A)}，下證{∈Cx(A)} ?Y。對于?y∈{X|X∈Cx(A)}，則 有x,y∈X,B?A，(x,y)∈R(A)，有(x,y)∈R(B)，又因為X?Y，所以{X|X∈Cx(A)}?Y。□

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

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

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

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

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

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

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

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

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

性質3

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

（2）因為β∈(0.5,1]，β＞1-β由（1）可知，D(X/Y)≥1-β，故。

（3）由（1）可證。 □

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

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

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

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

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

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

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

定理2設DS=(U,A,V,D,G)是不完備決策信息系統，B?A，0.5 ＜α,β≤1，RD是U上由D導出的等價關系，U/RD={D1,D2,…,Dr}，容易驗證和滿足以下性質：

（1）若X1?X2，則：

預警發布后加強大壩、溢洪道、輸水洞、排水溝、濾水壩址等部位的巡視檢查，庫水位每上升2 m巡查一次，同時監測測壓管水位，發現問題及時報告處理。當水位達到89.5 m即溢洪道底坎高程時，加強對溢洪道和閘門的檢查，同時注意及時打撈閘門附近的大型漂浮物。

（2）若α≤β，則：

3.2 廣義變精度粗糙集模型上的屬性約簡

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

定義9設DS=(U,A,V,D,G)是不完備決策信息系統，對于B?A，若C(B)=C(A)，則稱B是分塊協調集。進一步，若?B′?B，C(B′)≠C(A)，那么B是分塊約簡。

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

定理3設DS=(U,A,V,D,G)是不完備決策信息系統，分塊協調集必是β-上（下）分布協調集。

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

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

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

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

證明與文獻[15]中定理3.3的證明過程類似。□

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

證明一方面，當時，{Dj:Xi?，設B是β-上分布協調集，由定義10 可知，即?Dj∈U/RD=，因此有。由性質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)，當時，假設B?(Xi,Xk)=?，則?a∈B，a(Xi)=a(Xk)，由性質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不是β-上分布協調集。

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

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

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

4 實例分析

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

下面在另外兩種不同的不完備決策信息系統中驗證上一章給出的屬性約簡方法。

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

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

由決策屬性D在U上產生劃分為：

由定義1 可得對象的特征集：

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

由定義2 可得對象的特征集生成的二元關系：

由定義4 可得極大相容塊生成的二元關系：

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

決策等價類U/RD的0.7-上近似：

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

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

由此可知{S,X}是此不完備決策信息系統的0.7-上分布約簡。同樣計算樂觀的0.7-下分布約簡的結果也是{S,X}。

屬性約簡的結果與文獻[5]和文獻[22]相同，與文獻[22]中基于對象間的可辨識矩陣比較，本文提出的基于極大相容塊的方法壓縮了可辨識矩陣規模，進一步簡化了運算過程，節省了存儲空間。

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

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

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

其中由d產生的劃分為：

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

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

則有

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

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

因此{a3,a4}和{a1,a2,a4}是此不完備決策信息系統DS2的0.7-上分布約簡。這個結果與DS2的樂觀和悲觀的0.7-下分布約簡相一致。

這個結果與DS2的樂觀和悲觀的0.7-下分布約簡相一致。

基于3.1 節提出的廣義變精度粗糙集模型，給出一種計算不完備信息系統的β-上分布約簡的算法。

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

Table 5 Description of data sets表5 數據集的基本信息

Table 6 Result of reduction表6 約簡的結果

注2在約簡結果中，數字k代表第k-1 個條件屬性。A表示該數據集的條件屬性的集合，MCB 表示極大相容塊。

5 結束語

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