基于混合容差關(guān)系的粗糙集模型

楊習(xí)貝，宋晶晶，鞠恒榮

(1．江蘇科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院，江蘇 鎮(zhèn)江212003;2．南京理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院，南京210094)

0 引言

目前，隨著粗糙集理論的快速發(fā)展，粗糙集已被成功地應(yīng)用于知識發(fā)現(xiàn)、決策支持、模式識別等領(lǐng)域。Pawlak的粗糙集模型是通過不可分辨關(guān)系定義的，通過給定上下近似來對目標(biāo)進(jìn)行近似逼近［1，2］。不過，該方法只能應(yīng)用于完備信息系統(tǒng)。然而，在實(shí)際的工程應(yīng)用中，不完備信息系統(tǒng)［3］隨處可見，尤其是具有未知屬性值的不完備信息系統(tǒng)。據(jù)此，許多學(xué)者提出了不同類型的二元關(guān)系。比如，Y．Zhao提出了一種新的二元關(guān)系即弱不可分辨關(guān)系［4］;而相應(yīng)的，Pawlak提出的不可分辨關(guān)系則被看作強(qiáng)不可分辨關(guān)系。

本文將弱不可分辨關(guān)系引入到不完備信息系統(tǒng)中，然后介紹了弱容差關(guān)系。類似于強(qiáng)不可分辨關(guān)系，Kryszkiewicz提出的容差關(guān)系則稱為強(qiáng)容差關(guān)系。根據(jù)弱容差關(guān)系和強(qiáng)容差關(guān)系，提出了混合容差關(guān)系。混合容差關(guān)系是弱容差關(guān)系和強(qiáng)容差關(guān)系的一種融合形式。進(jìn)一步地，基于混合容差關(guān)系構(gòu)建了粗糙集模型。又由于混合容差關(guān)系是一個相容關(guān)系，故可以得到論域上的一族極大連續(xù)塊，我們在混合容差關(guān)系的基礎(chǔ)上，采用極大連續(xù)塊技術(shù)構(gòu)建了另一種粗糙集模型，進(jìn)而對這兩種不同的粗糙集模型進(jìn)行了對比分析，分析結(jié)果表明，采用極大連續(xù)塊構(gòu)建的粗糙集模型比基于混合容差關(guān)系構(gòu)建的粗糙集模型更有優(yōu)勢。

1 預(yù)備知識

1．1 強(qiáng)和弱不可分辨關(guān)系

一個信息系統(tǒng)可以被定義為一個二元組I=＜U，AT＞，其中，U表示所有對象的非空有限集合，稱為論域;AT是所有條件屬性的非空有限集合。

任給一個屬性子集A?AT，強(qiáng)不可分辨關(guān)系IND(AT)和弱不可分辨關(guān)系WIND(AT)分別表示如下:

定義1 設(shè)I是一個信息系統(tǒng)，?A?AT，?X?U，X基于強(qiáng)不可分辨關(guān)系IND(AT)的下近似集合和上近似集合分別定義如下:

定義2 設(shè)I是一個信息系統(tǒng)，?A?AT，?X?U，X基于弱不可分辨關(guān)系WIND(AT)的下近似集合

1．2 不完備信息系統(tǒng)和容差關(guān)系

不完備信息系統(tǒng)是指對象的一些屬性值是不精確的系統(tǒng)。本文中只考慮未知屬性值是遺漏的，但又確實(shí)存在的情況，這種類型的未知屬性值用”*”表示。假設(shè)遺漏型未知屬性值是可以與其他任意屬性值相比較的，從而構(gòu)建了如定義3所示的容差關(guān)系［5］。

定義3 設(shè)I是一個不完備信息系統(tǒng)，?A?AT，基于A的容差關(guān)系記為STA且

類似于強(qiáng)不可分辨關(guān)系，我們稱這種容差關(guān)系為強(qiáng)容差關(guān)系。

定義4 設(shè)I是一個不完備信息系統(tǒng)，?A?AT，?X?U，X基于強(qiáng)容差關(guān)系STA的下近似集合

其中STA(x)={y∈U:(x，y)∈STA}，表示U中所有與x具有強(qiáng)容差關(guān)系STA的對象的集合。

1．3 弱容差關(guān)系

對于強(qiáng)容差關(guān)系，兩個對象是相容的當(dāng)且僅當(dāng)它們在所有考慮的屬性上都是相容的。沿襲弱不可分辨關(guān)系的基本思想，我們很自然的來定義弱容差關(guān)系。對于弱容差關(guān)系，兩個對象是相容的只需它們在所考慮的屬性上至少有一個屬性是相容的即可。

定義5 設(shè)I是一個不完備信息系統(tǒng)，?A?AT，基于A的弱容差關(guān)系記為WTA且

定義6 設(shè)I是一個不完備信息系統(tǒng)，?A?AT，?X?U，X基于弱容差關(guān)系WTA的下近似集合和上近似集合分別定義如下:

其中，WTA(x)={y∈U:(x，y)∈WTA}，表示U中所有與x具有弱容差關(guān)系WTA的對象的集合。

2 混合容差關(guān)系

定義7 設(shè)I是一個不完備信息系統(tǒng)，其中A=A1∪A2?AT，基于A的混合容差關(guān)系記為HTA且

命題1 設(shè)I是一個不完備信息系統(tǒng)，其中A=A1∪A2?AT，有HTA=TA1∩WTA2。

證明:? (x，y)∈U2，根據(jù)定義6有

由定義7可以看出，混合容差關(guān)系HTA實(shí)際上是強(qiáng)容差關(guān)系STA1和弱容差關(guān)系WTA2的一種融合形式。若A2中只有一個屬性，則混合容差關(guān)系就退化為強(qiáng)容差關(guān)系;若A1是一個空集，則混合容差關(guān)系就退化為弱容差關(guān)系。

定義8 設(shè)I是一個不完備信息系統(tǒng)，其中A=A1∪A2?AT，?X?U，X基于混合容差關(guān)系HTA的下近似集合HAT(X)和上近似集合)分別定義如下:

其中，HTA(x)={y∈U:(x，y)∈HTA}，表示U中所有與x具有混合容差關(guān)系HTA的對象的集合。

明顯地，混合容差關(guān)系HTA是自反的、對稱的，故是一個相容關(guān)系。類似于文獻(xiàn)中所討論的，根據(jù)一個相容關(guān)系可以得到論域上的一族極大連續(xù)塊，這一族極大連續(xù)塊構(gòu)成了論域上的一個相容覆蓋［6，7］。因此，基于混合容差關(guān)系，我們也可以采用極大連續(xù)塊技術(shù)來構(gòu)建粗糙集模型。

定義9 設(shè)I是一個不完備信息系統(tǒng)，其中A=A1∪A2?AT，基于混合容差關(guān)系HTA的相容覆蓋記為R(A)且

定義10 設(shè)I是一個不完備信息系統(tǒng)，其中A=A1∪A2?AT，?X?U，X基于相容覆蓋R(A)的下近似集合和上近似集合分別定義如下:

Leung根據(jù)不完備信息系統(tǒng)上的相容關(guān)系，采用極大連續(xù)塊技術(shù)構(gòu)建了粗糙集模型，并將其與Kryszkiewicz的容差關(guān)系的粗糙集模型進(jìn)行了對比分析［8］。類似于Leung的結(jié)論，此處根據(jù)混合容差關(guān)系，依然可以對定義8和定義10所示的兩種不同的粗糙集模型進(jìn)行對比分析。

命題2 設(shè)I是一個不完備信息系統(tǒng)，其中A=A1∪A2?AT，?X?U，有

證明:"?"?y∈HTA(x)，根據(jù)定義7可知，(x，y)∈HTA，所以必定存在一個Y∈R(A)，使得{x，y}∈Y，從而可以得到y(tǒng)∈∪{Y∈R(A):x∈Y}，即HTA(x)?{Y∈R(A):x∈Y}。

"?"?y∈∪{Y∈R(A):x∈Y}，必定存在一個Y∈R(A)，使得x∈Y且y∈Y，從而可以得知{x，y}?Y。根據(jù)定義7可知，x和y滿足混合容差關(guān)系HTA，所以就有y∈HTA(x)，因此HTA(x)?∪{Y∈R(A):x∈ Y}。

命題3 設(shè)I是一個不完備信息系統(tǒng)，其中A=A1∪A2?AT，?X?U，有

證明:?x∈HTA(X)，根據(jù)定義8有HTA(x)?X。再根據(jù)命題2可知，∪{Y∈R(A):x∈Y}?X，所以?Y?R(A)且x∈Y、Y?X成立，于是根據(jù)定義10有

根據(jù)命題3可知，在混合容差關(guān)系的基礎(chǔ)上，采用極大連續(xù)塊技術(shù)，可以得到較大的下近似，從這個角度來看，定義10比定義8的優(yōu)勢更明顯。

表1 一個不完備信息系統(tǒng)

例1 考慮如表1所示的一個不完備信息系統(tǒng)，其中U={x1，x2，x3，x4，x5，x6}為論域，AT=A1∪A2={a，b}∪ {c，e}為條件屬性集合，d為決策屬性。根據(jù)決策屬性，可以得到論域上的劃分:U/IND(j5i0abt0b)={X1，X2}={{x1，x5，x6}，{x2，x3，x4}}。

由強(qiáng)容差關(guān)系的定義可得，IND(A1)={(x1，x1)，(x2，x2)，(x2，x3)，(x2，x4)，(x2，x5)，(x2，x6)，(x3，x2)，(x3，x3)，(x3，x4)，(x3，x5)，(x3，x6)，(x4，x2)，(x4，x3)，(x4，x4)，(x4，x5)，(x4，x6)，(x5，x2)，(x5，x3)，(x5，x4)，(x5，x5)，(x5，x6)，(x6，x2)，(x6，x3)，(x6，x4)，(x6，x5)，(x6，x6)}。

由弱容差關(guān)系的定義可得，IND(A2)={(x1，x1)，(x1，x3)，(x1，x4)，(x1，x5)，(x1，x6)，(x2，x2)，(x2，x4)，(x3，x1)，(x3，x3)，(x3，x4)，(x3，x5)，(x3，x6)，(x4，x1)，(x4，x2)，(x4，x3)，(x4，x4)，(x4，x5)，(x4，x6)，(x5，x1)，(x5，x3)，(x5，x4)，(x5，x5)，(x5，x6)，(x6，x1)，(x6，x3)，(x6，x4)，(x6，x5)，(x6，x6)}。

再由命題 1 可得，混合容差關(guān)系 HTA={(x1，x1)，(x2，x2)，(x2，x4)，(x3，x3)，(x3，x4)，(x3，x5)，(x3，x6)，(x4，x2)，(x4，x3)，(x4，x4)，(x4，x5)，(x4，x6)，(x5，x3)，(x5，x4)，(x5，x5)，(x5，x6)，(x6，x3)，(x6，x4)，(x6，x5)，(x6，x6)}。

再由定義 9 可得基于混合容差關(guān)系 HTA的相容覆蓋 R(A)={{x1}，{x2，x4}，{x3，x4，x5，x6}}。

根據(jù)定義8，可得決策類的下、上近似:

3 結(jié)論

粗糙集理論在不完備信息系統(tǒng)中的擴(kuò)展對于粗糙集理論的發(fā)展具有極其重要的意義。本文所討論的粗糙集模型是建立在不完備信息系統(tǒng)的基礎(chǔ)上的，具有非常廣泛的應(yīng)用前景。

本文通過融合強(qiáng)容差關(guān)系和弱容差關(guān)系，提出了混合容差關(guān)系，然后構(gòu)建了兩種不同的粗糙集模型，接著，對這兩種粗糙集模型進(jìn)行了對比分析。

［1］Z．Pawlak．Rough sets-theoretical aspects of reasoning about data［M］．Netherland:Kluwer Academic Publishers，1991．

［2］Z．Pawlak，A．Skowron．Rough sets:some extensions［J］．Information Sciences，2007，177:28-40．

［3］X．B．Yang，J．Y．Yang．Incomplete information system and rough set theory:models and attribute reductions［M］．Beijing:Science Press Beijing ＆ Springer，2012．

［4］Y．Zhao，Y．Y．Yao，F(xiàn)．Luo．Data analysis based on discernibility and indiscernibility［J］．Information Sciences，2007，177:4959-4976．

［5］M．Kryszkiewicz．Rough set approach to incomplete information systems［J］．Information Sciences，1998，112:39-49．

［6］［8］Y．Leung，D．Y．Li．Maximal consistent block technique for rule acquisition in incomplete information systems［J］．Information Sciences，2003，153:85-116．

［7］Y．H．Qian，J．Y．Liang，D．Y．Li．，et al．Approximation reduction in inconsistent incomplete decision tables［J］．Knowledge-Based Systems，2010，23:427-433．