多決策覆蓋信息系統的約簡

許麗婷 李進金? 林藝東 李怡靚

(1-閩南師范大學數學與統計學院，漳州 3 63000;2-福建省粒計算及其應用重點實驗室，漳州 3 63000)

1 引言

粗糙集理論[1-3]作為一種處理不精確、不一致、不完整等各類不完備信息的有效工具，由波蘭科學家Pawlak在1982年創立.粗糙集理論是一種天然的數據挖掘或者知識發現方法，它與概率論[4]、模糊理論[5]、證據理論[6-8]等領域都有相關的結合.

覆蓋粗糙集理論為經典粗糙集的一種推廣，其約簡理論一直受到廣泛的關注.Zhu[9]對覆蓋提出了一種約簡方法，該約簡是產生相同覆蓋上、下近似的最小覆蓋，為數據挖掘中消除冗余提供了一種有效技術.覆蓋信息系統可以進一步的推廣到覆蓋決策信息系統，其中用劃分刻畫決策屬性的覆蓋決策信息系統的約簡理論的研究十分廣泛.夏秀云等[10]利用信息熵，討論協調覆蓋決策系統的相關約簡.辨識矩陣是覆蓋決策信息系統約簡理論的一個重要的工具.Chen等[11]在決策為劃分的覆蓋決策信息系統中提出了一種減少覆蓋決策系統屬性的方法.由于決策為劃分有一定的局限性，因此一些學者將決策從劃分推廣為覆蓋，然后再對覆蓋決策信息系統的約簡理論進行研究.張燕蘭和李進金[12]在文獻[11]的基礎上研究了在決策為覆蓋的覆蓋決策信息系統中保持正域不變的相對約簡，并通過構造辨識矩陣求其約簡.Zhang和Li[13]介紹了一族覆蓋的兩種相對約簡，并且通過構造了兩個辨識矩陣研究所有相對約簡的結構.然而在根據辨識矩陣求其約簡的過程中，由于辨識矩陣過于復雜，而導致計算過程中時間復雜度為指數級.在數據集相對較大時難以計算.本文通過將決策為覆蓋的覆蓋決策信息系統轉化為多決策覆蓋信息系統，提出了兩類新約簡，并將此系統下的兩類約簡與文獻[13]下的約簡方法進行比較.

本文通過特征函數將覆蓋決策信息系統轉化為多決策覆蓋信息系統.首先，在多決策覆蓋信息系統下定義了兩類協調集，構造了兩個辨識矩陣，通過這兩個辨識矩陣研究多決策覆蓋信息系統的約簡問題，討論多決策覆蓋信息系統中的兩類協調集與覆蓋決策信息系統中的上近似協調集之間的聯系.

2 預備知識

在采集數據的過程中，可能由于條件不夠等原因使得一些對象的決策缺失或者不能完全確定，這時若將決策刻畫為劃分，則會導致數據部分失真，故在一些決策信息系統中的決策屬性以覆蓋刻畫更恰當，下面將給出例子進行解釋說明.

例1 若某企業想要判斷每項技術的成熟性，為了對技術進行創新決策.設決策信息系統為(U,A,F,d)，U表示每項技術的集合，共有5項技術待評估.A={a1,a2}表示影響各項技術成熟程度的屬性，a1表示市場需求的情況，a2表示需求變化的情況.F={f1:U→Vl(al∈A)}為每項技術和各個屬性的關系，即每項技術在各個屬性下的取值，Vl為屬性al的值域.d:U→Vd表示技術的成熟程度，Vd為屬性d的值域.如表1所示，有一個連續值決策信息系統，其條件屬性和決策屬性的取值范圍在[0,4]內.

表1 例1中的決策信息系統

對任意B?A,d，定義RB,Rd如下

其中εal>0,εd>0，顯然RB,Rd滿足自反、對稱，但一般不滿足傳遞.因此

Ci={(Rai)s(x)|x∈U},i=1,2,Cd={(Rd)s(x)|x∈U}

為覆蓋.

若εa1=0.4,εa2=0.2,εd=1.2，則可得到三個覆蓋為

C1={{x1,x2,x6},{x1,x2},{x3,x5},{x1,x4}},

C2={{x1,x2,x5},{x1,x2,x3,x5},{x3,x4,x5},{x3,x4},{x2,x3,x5}},

Cd={{x1,x2,x3,x5},{x1,x2,x3,x4},{x1,x3,x5},{x2,x4}}.

例2 如表2所示，給出了一個不完備決策信息系統I=(U,A,F,d)，其中對象集為U，屬性集為A，F={f1:U→Vl(al∈A)}代表對象和屬性的關系集，Vl為屬性al的值域，d:U→Vd，其中Vd取有限值.

表2 例2中的不完備決策信息系統

對于B?A，定義如下優勢關系

設I=(U,A,F,d)為不完備決策信息系統，對于決策d,U可以被劃分為有序的類

D={Dt,t∈T},T={1,2,···,k}.

對于任意r,s∈T，若r>s，則代表Dr中的元素優于Ds中的元素，因此，這些有序的決策類可以分別使用向上聯合和向下聯合近似來表示，有

由表2可得

決策類為D={D1,D2}，其中D1={x2,x5},D2={x1,x3,x4}.由于2>1，因此D2中的對象比D1中的對象優，根據向上聯合近似的定義可以得到

例1和例2表明在一些決策信息系統中，利用覆蓋刻畫其條件屬性與決策屬性更具有合理性，故研究以覆蓋刻畫其決策的覆蓋決策信息系統的屬性約簡問題具有理論與實踐意義.以下給出了覆蓋決策信息系統的相關知識，其決策以覆蓋刻畫.

定義1[11]設A={Cj|j=1,2,···,n}為U上的一族覆蓋，對任意x∈U，則x在覆蓋A下的鄰域定義為

(x)A=∩{K|x∈K,K∈Cj,j=1,2,···,n}.

A誘導的U上的一個覆蓋為

cov(A)={(x)A|x∈U}.

對任意B?A,x,y∈U，有如下性質：

1)y∈(x)B?(y)B?(x)B；

2) (x)B=∩C∈B(x)C；

3) (x)A?(x)B,(x)B=(x)cov(B).

根據定義1，可得一對關于覆蓋cov(A)的近似算子.

定義2[9]設A={Cj|j=1,2,···,n}為U上的一族覆蓋，對任意X?U，X關于cov(A)的上近似算子定義為

易得它的對偶下近似算子為

Zhang和Li[13]給出了有關保持上下近似算子不變的約簡理論以及辨識矩陣.

定義4[13]設(U,A,CD)是覆蓋決策信息系統，對x,y∈U且有Di∈CD，記

稱D(x,y)為x對y的上近似辨識集，則D={D(x,y)|x,y∈U}為x對y的上近似辨識矩陣.

引理1[13]設(U,A,CD)是覆蓋決策信息系統，B是A的上近似協調集，當且僅當D(x,y)?=?時，B∩D(x,y)?=?.

引理2[6]設C是A的上近似核心，且C∈A，當且僅當存在x,y∈U，使得D(x,y)={C}.

例3 設論域U={1,2,3,4,5}，U的一族覆蓋為A={C1,C2,C3}，CD為U的一個覆蓋，且

C1={{1,2,4},{2,3,5},{1,5}},C2={{1,3,4},{2,5},{4,5}},

C3={{1,4,5},{2,4},{3,5}},CD={{1,3},{2,4,5},{1,3,4},{2,5}}.

易得表3.

表3 例3中各點的鄰域

由表3可以得出

從而上近似辨識矩陣為

根據引理1知，B={C1,C2}是上近似協調集，但B1={C1}和B2={C2}都不是上近似協調集，所以B={C1,C2}是上近似約簡集.

3 基于多決策覆蓋信息系統type-1辨識矩陣的約簡

首先，給出特征函數的定義，而后通過特征函數將覆蓋決策信息系統中以覆蓋刻畫的決策轉化為一個形式背景，從而產生多決策覆蓋信息系統.

定義5 設(U,A,CD)是覆蓋決策信息系統，CD={D1,D2,···,Dn}是U上的一個覆蓋，特征函數定義為

定義6 設(U,A,CD)是覆蓋決策信息系統，其中A為U上的一族覆蓋，CD={D1,D2,···,Dn}為U上的一個覆蓋，LD={l1,l2,···,ln}，其中li:U→{0,1},i=1,2,···,n，則稱(U,A,LD)為多決策覆蓋信息系統.

對于多決策覆蓋信息系統定義一個U上的等價關系如下.

定義7 設(U,A,LD)是多決策覆蓋信息系，對x,y∈U，有

當LD={li}時，有

下面給出關于多決策信息系統type-1覆蓋協調集和type-1覆蓋約簡集的判定定理.

定理1 設(U,A,CD)是覆蓋決策信息系統，(U,A,LD)是多決策覆蓋信息系統，若B為覆蓋信息系統的上近似協調集，則B為多決策覆蓋信息系統的type-1覆蓋協調集.

然而，反之不一定成立，下面舉例說明.

例4 設論域U={1,2,3,4,5}，U的一族覆蓋為A={C1,C2,C3}，CD為的一個覆蓋，且C1={{1,2},{2,3,4},{4,5}},C2={{1,2,3},{3,4},{5}},C3={{1,2},{3,4},{4,5}}.

我們可以通過構造辨識矩陣來描述覆蓋協調集和覆蓋約簡集.首先，針對type-1覆蓋協調集和type-1覆蓋約簡集構造對應的type-1多決策覆蓋辨識集并給出相關定理.

定義9 設(U,A,LD)是多決策覆蓋信息系統，對x,y∈U，存在li∈LD，記

稱D1(x,y)為x對y的type-1多決策覆蓋辨識集，則D1={D1(x,y)|x,y∈U}為x對y的type-1多決策覆蓋辨識矩陣.

下面通過構造的type-1多決策覆蓋辨識集和type-1多決策覆蓋辨識矩陣來判定type-1覆蓋協調集和type-1覆蓋約簡集.

定理3 設(U,A,LD)是多決策覆蓋信息系統，B是type-1覆蓋協調集，當且僅當D1(x,y)?=?時，B∩D1(x,y)?=?.

例5 續例3，由覆蓋CD={{1,3},{2,4,5},{1,3,4},{2,5}}，可以得到如表4的一個形式背景.

表4 例5中x與li的關系

由表4可知產生的等價類為

從而可得一個type-1多決策覆蓋辨識矩陣

根據定理3知，B={C1,C2}是type-1覆蓋協調集，但B1={C1}和B2={C2}都不是type-1覆蓋協調集，所以B={C1,C2}是type-1覆蓋約簡集.

對于例3，在多決策覆蓋信息系統下求出的約簡與覆蓋決策信息系統的結果相同.在計算辨識矩陣的過程中，由于文獻[13]在計算辨識矩陣時需要計算的是上近似，而本文只需計算等價類，所以此方法比文獻[13]中的方法簡便，且計算量小，節省時間.

在計算出type-1多決策覆蓋辨識矩陣之后，我們不僅可以通過定理3得出type-1覆蓋協調集和type-1覆蓋約簡集，還可以通過以下區分函數來求得多決策覆蓋信息系統的約簡集.

定義10 設(U,A,LD)是多決策覆蓋信息系統，D1={D1(x,y)|x,y∈U}為type-1多決策覆蓋辨識矩陣，記

M=∧{∨{C|C∈D1(x,y)}|x,y∈U},

M稱為覆蓋區分函數，其中∧表示(合取)運算，∨表示(析取)運算.

由定義10，可以得到如下定理.

定理4 設(U,A,LD)是多決策覆蓋信息系統，D1={D1(x,y)|x,y∈U}為type-1多決策覆蓋辨識矩陣，覆蓋區分函數M的最小析取范式是

其中Bk={Cs|s=1,2,···,qk},{Bk|k=1,2,···,p}是type-1覆蓋約簡集.

例6 續例5，利用區分函數有

M=C1∧(C2∨C3)∧(C1∨C3)∧(C1∨C2∨C3)∧(C1∨C2)∧C2=C1∧C2.

所以B={C1,C2}是type-1覆蓋約簡集.

將多決策覆蓋信息系統中的覆蓋分類后，便于研究不同覆蓋各自的特征.下面給出覆蓋分類及判別方法.

定義11 設(U,A,LD)是多決策覆蓋信息系統，Bk(k≤r)為所有覆蓋約簡集，記

Ci∈C時，稱Ci為核心覆蓋，C稱為核心覆蓋集；Ci∈K時，稱Ci為相對必要覆蓋，K稱為相對必要覆蓋集；Ci∈I時，稱Ci為不必要覆蓋，I稱為不必要覆蓋集.

定理5 設(U,A,LD)是多決策覆蓋信息系統，則下列命題等價：

1)C′是核心覆蓋；

2) 存在x,y∈U,D1(x,y)={C′}；

3) 若C′為不必要覆蓋?存在li∈LD，使得(x)(C′)?[x]li∪(x)C′.

4 基于多決策覆蓋信息系統type-2辨識矩陣的約簡

下面給出另一類多決策覆蓋辨識矩陣來判定覆蓋協調集和覆蓋約簡集.

由定理1上近似協調集是type-1覆蓋協調集可類似的推出上近似協調集是type-2覆蓋協調集.

定理8 設(U,A,CD)是覆蓋決策信息系統，(U,A,LD)是多決策覆蓋信息系統，若B為覆蓋信息系統的上近似協調集，則B為覆蓋信息系統(U,A,CD)的上近似協調集，當且僅當B為多決策覆蓋信息系統(U,A,LD)的type-2覆蓋協調集.

定理9 設(U,A,LD)多決策覆蓋信息系統，若B為type-2覆蓋協調集，則B為type-1覆蓋協調集.

反之，不一定成立，下面舉例說明.

類似定理2，可以得到如下定理，根據此定理構造type-2多決策覆蓋辨識集.

定義13 設(U,A,LD)是多決策覆蓋信息系統，對x,y∈U，任意li∈LD，記稱D2(x,y)為x對y的type-2多決策覆蓋辨識集，則D2={D2(x,y)|x,y∈U}為x對y的type-2多決策覆蓋辨識矩陣.

通過上述構造的type-2多決策覆蓋辨識集和type-2多決策覆蓋辨識矩陣給出相關的type-2覆蓋協調集和type-2覆蓋約簡集的定理.

根據定理3中type-1覆蓋協調集的充要條件，類似的可以得出type-2覆蓋協調集的充要條件.

定理11 設(U,A,LD)是多決策覆蓋信息系統，B是type-2覆蓋協調集，當且僅當D2(x,y)?=?時，B∩D2(x,y)?=?.

例8 由例5的等價類可得一個type-2多決策覆蓋辨識矩陣

根據定理11知B={C2}是type-2覆蓋約簡集.

從例8可以看出，type-2多決策覆蓋辨識矩陣求出的約簡集與type-1多決策覆蓋辨識矩陣有所不同.由于type-1多決策覆蓋辨識矩陣中的非空集合比type-2多決策辨識矩陣中的非空集合多，因此，在利用區分函數來計算約簡集時tpye-2比type-1計算量小.

對于type-2多決策覆蓋辨識矩陣，也有類似于定義10的覆蓋區分函數

M=∧{∨{C|C∈D2(x,y)}|x,y∈U}.

在type-2多決策覆蓋辨識集下也有相關覆蓋分類的判別方法.

根據定理5，可以類似給出type-2多決策覆蓋辨識集下核心覆蓋的等價條件.

定理12 設(U,A,LD)是多決策覆蓋信息系統，則下列命題等價：

1)C′′是核心覆蓋；

2) 存在x,y∈U,D2(x,y)={C′′}；

由定理6，同理可以給出type-2多決策覆蓋辨識集下不必要覆蓋的等價條件.

結合定理12與定理13，得出相對必要覆蓋的充要條件.

定理14 設(U,A,LD)是多決策覆蓋信息系統，則有以下結論：

5 結束語

本文將覆蓋決策信息系統中以覆蓋刻畫的決策通過特征函數轉化為由0和1組成的形式背景，給出了多決策覆蓋信息系統的定義，進而研究在多決策覆蓋信息系統下的約簡.在多決策覆蓋信息系統中提出兩類協調集判定方法，構造了兩個相應的辨識集，進一步討論多決策覆蓋信息系統中的兩類協調集與覆蓋決策信息系統的協調集之間的關系.

對于本文給出的兩類多決策覆蓋辨識矩陣，計算量相對較小，可以節省求解覆蓋約簡的時間，在實際應用中具有一定的意義.此外，還可以繼續討論三個辨識矩陣之間的關系，以及三個辨識矩陣所產生的約簡集之間的聯系.