基于辨識(shí)矩陣的多伴隨模糊粗糙集屬性約簡

梁 美 社

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

粗糙集理論是20世紀(jì)80年代波蘭學(xué)者Pawlak教授提出的，主要用于處理關(guān)系數(shù)據(jù)庫中不完備、不精確的信息[1-2].當(dāng)前，粗糙集理論被廣泛應(yīng)用于工業(yè)控制[3-4]、生物醫(yī)學(xué)[5-6]、市場預(yù)測[7]、圖像處理[8-9]等領(lǐng)域.

早期粗糙集理論的經(jīng)典著作主要利用一些等價(jià)關(guān)系，來處理數(shù)據(jù)集中對(duì)象關(guān)于屬性取值為特殊離散值的情況.等價(jià)關(guān)系的交集仍是等價(jià)關(guān)系，Pawlak將其稱為不可辨識(shí)關(guān)系[1-2].因?yàn)榈葍r(jià)關(guān)系的要求過于嚴(yán)苛，因此在實(shí)際應(yīng)用中往往受到很大的限制.在過去的20年中，針對(duì)不同的問題，學(xué)者們對(duì)等價(jià)關(guān)系進(jìn)行了多種形式的推廣，如優(yōu)勢關(guān)系[10-11]、容差關(guān)系[12-13]、模糊關(guān)系[14-16]和相容關(guān)系等.

1965年，Zadeh教授提出了模糊集的概念[17].粗糙集與模糊集都是處理不確定性信息的重要工具，也是研究信息系統(tǒng)中知識(shí)不完全、不確定問題的重要方法.將粗糙集中被近似的經(jīng)典集合擴(kuò)展到模糊集合，將等價(jià)關(guān)系推廣到模糊關(guān)系，就得到了模糊粗糙集的概念[18].后來，一些學(xué)者進(jìn)一步把經(jīng)典邏輯算子推廣為模糊邏輯算子[19-24].而多伴隨算子的運(yùn)用，使其理論發(fā)展到了一個(gè)全新的階段.

現(xiàn)有的多伴隨模糊粗糙集模型[25]中，通過定義模糊測度，得到的屬性約簡均為水平α下的近似約簡.本文擬在多伴隨模糊粗糙集模型的基礎(chǔ)上，通過構(gòu)造屬性約簡的可辨識(shí)矩陣，給出屬性約簡的計(jì)算方法和相關(guān)性質(zhì)，進(jìn)而得到模糊決策信息系統(tǒng)的精確屬性約簡.

1 預(yù)備知識(shí)

1.1 粗糙集理論

經(jīng)典粗糙集理論[1]中，信息系統(tǒng)通常表示為IS=(U,Α)，其中對(duì)象集合U={x1,…,xn}，屬性集合Α={a1,…,am}，是非空有限集.對(duì)于?a∈Α，定義映射fa:U→Va，其中Va是屬性a在U上的值域. 對(duì)于B?A，記為RB={(x,y)∈U×U:?a∈B,fa(x)=fa(y)}，則RB是由屬性集合B確定的U上的等價(jià)關(guān)系. 由RB可以得到U上的一個(gè)劃分.U/RB={[x]B:x∈U}，其中[x]B={y∈U:(x,y)∈RB}.

對(duì)于X?U，它關(guān)于RB的下、上近似分別為:

若rA=1，稱(U,Α∪j5i0abt0b)為一致的決策信息系統(tǒng). 若POSB=POSA，且?B′?B，有POSB′≠POSA，稱B為A的決策約簡.

經(jīng)典粗糙集中，另一種求屬性約簡的方法是基于可辨識(shí)矩陣和辨識(shí)函數(shù)的.

決策信息系統(tǒng)(U,Α∪j5i0abt0b)的辨識(shí)矩陣O是一個(gè)(n×n)階矩陣，具體定義為：

其辨識(shí)函數(shù)定義為f(U,RA)=∧{∨Oij}(i≠j).由辨識(shí)函數(shù)計(jì)算得到的最小析取范式，即為該決策信息系統(tǒng)(U,Α∪j5i0abt0b)的所有約簡.

1.2 多伴隨模糊粗糙集理論

多伴隨模糊粗糙集是對(duì)粗糙集理論的一種推廣.通過引入一組伴隨對(duì)來計(jì)算模糊集的上下近似.不同伴隨對(duì)的使用表達(dá)了研究者對(duì)不同對(duì)象的偏好.這種推廣極大地增強(qiáng)了粗糙集理論的應(yīng)用.

定義1[21]設(shè)(P1,≤1)，(P2,≤2)，(P3,≤3)為三個(gè)偏序集，定義映射:P1×P2→P3， ↙:P3×P2→P1，↖:P3×P1→P2，若對(duì)于任意x∈P1，y∈P2，z∈P3，滿足:

(1)x≤1z↙y當(dāng)且僅當(dāng)x&y≤3z，當(dāng)且僅當(dāng)y≤2z↖x;

(2)&對(duì)兩個(gè)參數(shù)是單調(diào)增的;

(3)↙,↖對(duì)第一個(gè)參數(shù)單調(diào)增，對(duì)第二個(gè)參數(shù)單調(diào)減;

(4)稱(&,↙,↖)是關(guān)于P1,P2,P3的伴隨三元組.

常用的有Godel，product，ukasiewiczt-模及其蘊(yùn)含算子構(gòu)成的伴隨三元組，它們分別定義[21]為：

x&Py=x·y,z↖Px=min{1,z/x};

x&Ly=max{0,x+y-1},

z↖Lx=min{1,1-x+z}.

假設(shè)(U,Α∪j5i0abt0b)為模糊決策信息表，(P,≤)為一偏序集，TP為P中最大元素，對(duì)于?a∈A，定義映射Ra:U×U→P為P-模糊容差關(guān)系，使其滿足自反性，即對(duì)于?x∈U，有Ra(x,x)=TP;使其滿足對(duì)稱性，即?x,y∈U，有Ra(x,y)=Ra(y,x).

在多伴隨面向?qū)傩钥蚣芟拢紤]形式背景(U,U,RB,τ)，對(duì)于?x,y∈U，定義似然算子和必然算子:

g↑π(x)=sup{RB(x,y)&τ(x,y)g(y)|y∈U}，

f↓N(y)=inf{f(x)↖τ(x,y)RB(x,y)|x∈U}.

g↑π是g的上近似，f↓N是f的下近似.{(&τ(x,y),↙τ(x,y),↖τ(x,y)為伴隨對(duì)集合，其中τ:U×U→I表示將任意一對(duì)對(duì)象映射為某一特定的伴隨對(duì)，I為一指標(biāo)集.

定義3[24]對(duì)于給定模糊子集h∈LX，(h↓N,h↑π)稱為多伴隨模糊粗糙集.

在模糊決策信息表(U,A∪D,f,V)中，D=j5i0abt0b為決策屬性，利用必然算子定義多伴隨模糊粗糙集正域，對(duì)于?y∈X，

文獻(xiàn)[25]中利用模糊蘊(yùn)含和模糊基數(shù)來定義正域依賴度，通過模糊蘊(yùn)含算子來定義L-測度.

由定義4可以得到，模糊決策信息表(U,A∪D,f,V)中屬性子集B的正域依賴度為：

定義6[24]設(shè)γ:Ρ(Α)→L是決策系統(tǒng)(U,Α∪j5i0abt0b)的一個(gè)L-測度，B?Α且α∈L，若γ(B)≥α，α≠⊥L則稱B是一個(gè)α水平下L-決策超約簡.若對(duì)于?B1?B，有γ(B1)<α，則稱B是一個(gè)α水平的下L-決策約簡.

顯然，這個(gè)約簡與參數(shù)α的取值密切相關(guān).給定α后，其得到的約簡均為近似約簡.

2 基于辨識(shí)矩陣的模糊正域約簡

在定義2中，模糊不可辨識(shí)關(guān)系是通過一個(gè)單調(diào)聚合算子得到的.而在經(jīng)典的粗糙集理論中，對(duì)于屬性子集B?A，其等價(jià)關(guān)系為RB=∩a∈BRa.本文將借鑒這個(gè)思路，給出新的模糊不可辨識(shí)關(guān)系的定義.

為了方便討論問題，本文的模糊信息決策表為(U,A∪D,V,f)，其中，|U|=n，|A|=m，D=j5i0abt0b，且決策屬性為經(jīng)典的明確關(guān)系.

證明由定義7可直接得到.

如果保證模糊正域不變，則可得到屬性約簡定義8.

定義9給出了利用辨識(shí)矩陣求解模糊決策約簡的方法.

定理3設(shè)(U,A∪D,V,f)為一模糊決策信息表，屬性子集B?A，B∩mij≠?(i≠j,i,j≤n)，則B是一個(gè)模糊正域協(xié)調(diào)集.

定理4設(shè)(U,A∪D,V,f)為一模糊信息決策表，MF為其辨識(shí)矩陣，有以下性質(zhì)：

(1)mii=A，i≤n；

(2)若a為核心屬性，當(dāng)且僅當(dāng)存在i,j≤n時(shí)，

(3)使得mij=a.

(2)設(shè)a為核心屬性，若任意包含a的可辨識(shí)屬性集mij(i≠j)中至少含有兩個(gè)元素，令B=∪i≠j(mij-{a})，則B∩mij≠?(?i≠j).由定理3可知，B是一個(gè)模糊正域協(xié)調(diào)集，因而存在C?B使得C為一個(gè)模糊正域約簡.顯然a?C，這與a為核心屬性矛盾.

反之，設(shè)mi0j0={a}，?B?A(a?B)為一個(gè)模糊正域約簡，則B是一個(gè)模糊正域協(xié)調(diào)集，由定理3可知，B∩mij≠?(i≠j,i,j≤n)，這與B∩mi0j0≠?矛盾，故若B為一個(gè)模糊正域約簡，均有a∈B，由核心屬性定義可知，a為核心屬性.

定義10設(shè)(U,A∪D,V,f)為一模糊決策信息決策表，MF為模糊決策信息表的可辨識(shí)矩陣，定義fF(U,RA)=∧{∨mij}，其中i≠j.稱fF(U,RA)為(U,A∪D,V,f)上的記辨識(shí)函數(shù).

證明根據(jù)定義9、定理3和最小析取范式的定義即可證得結(jié)論.

所有約簡集合的交集稱為核心屬性，記為CoreF(A).

3 實(shí)例分析

例1設(shè)屬性集A={a1,a2,a3,a4}，決策屬性集合D=j5i0abt0b，對(duì)象集U={x1,x2,…,x7}，映射f:U×A→V，模糊決策表(U,A∪D,V,f)如表1所示.

表1 模糊決策表(U,A∪D,V,f)

同樣的方法，可以得到A的所有子集的模糊容差關(guān)系矩陣.令

由此計(jì)算出關(guān)于所有屬性子集的直覺模糊正域依賴度如下：

kA=0.91,k{a1,a2,a4}=0.90,k{a1,a2}=0.81,k{a2,a4}=0.76,k{a1,a2,a3}=0.84,k{a1,a3}=0.36,k{a2,a3}=0.71,k{a1,a3,a4}=0.85,k{a2,a3,a4}=0.84,k{a3,a4}=0.75,k{a1,a4}=0.80,k{a1}=0.30,k{a2}=0.61,k{a3}=0.19,k{a4}=0.46.

令I(lǐng)=↖L，根據(jù)定義5有，γA=1,γ{a1,a2,a4}=0.99,γ{a1,a2}=0.90,γ{a2,a4}=0.85,γ{a1,a2,a3}=0.93,γ{a1,a3}=0.45,γ{a2,a3}=0.80,γ{a1,a3,a4}=0.94,γ{a2,a3,a4}=0.93,γ{a3,a4}=0.84,γ{a1,a4}=0.89,γ{a1}=0.39,γ{a2}=0.70,γ{a3}=0.28,γ{a4}=0.55.

若α=0.95，則B={a1,a2,a4}為L-決策約簡；若α=0.90，則{a1,a3,a4,a2,a3,a4,a1,a2}為L-決策約簡.

表2 屬性集合A的模糊容差關(guān)系矩陣

例2例1中的模糊決策表(U,A∪D,V,f)，根據(jù)定義7，可得到屬性集合A的新模糊不可辨識(shí)關(guān)系矩陣，見表3.

表3 屬性集合A的新模糊容差關(guān)系矩陣

根據(jù)定義9，可得到模糊信息決策表(U,A∪D,V,f)的辨識(shí)矩陣MF如表4. 由定義10中辨識(shí)函數(shù)計(jì)算公式可知，B={a1,a2,a4}為模糊信息決策表(U,A∪D,V,f)的一個(gè)約簡.a1,a2,a4均為核心屬性.

表4 辨識(shí)矩陣

利用模糊L-測度求解模糊信息決策表約簡時(shí)，最壞的情況是，先求出所有屬性子集所對(duì)應(yīng)的模糊關(guān)系矩陣，然后再求各個(gè)關(guān)系矩陣下的模糊正域，其計(jì)算時(shí)間復(fù)雜度應(yīng)不小于o(2n·(m+n)n2)；利用辨識(shí)矩陣求解約簡時(shí)，不需要求解所有屬性子集的模糊關(guān)系矩陣及相應(yīng)模糊正域，在最壞情況下的時(shí)間復(fù)雜度為o((3m+n)n2). 因此，辨識(shí)矩陣方法在求解約簡時(shí)可大大降低時(shí)間復(fù)雜度.

4 結(jié)語

通過實(shí)例對(duì)比分析可知，本文提出的利用辨識(shí)矩陣求解多伴隨模糊粗糙集屬性約簡具有以下性質(zhì)：所求約簡集合為模糊決策信息系統(tǒng)的精確約簡集合；簡化了屬性約簡的計(jì)算過程，有利于提高知識(shí)的獲取效率.