不完備信息系統(tǒng)中一種拓展粗糙集模型

摘 要：以同時具有遺漏型和缺席型未知屬性值的不完備信息系統(tǒng)為研究對象，提出了一種使用參數(shù)進(jìn)行控制的二元關(guān)系以及相應(yīng)的粗糙集模型，將這種拓展粗糙集模型與不完備信息系統(tǒng)中現(xiàn)有的幾種拓展粗糙集模型進(jìn)行了對比研究。對一不完備信息系統(tǒng)進(jìn)行了實(shí)例分析，以說明新提出的二元關(guān)系的有效性。

關(guān)鍵詞：不完備信息系統(tǒng)；粗糙集；容差關(guān)系；相似關(guān)系；特征關(guān)系

中圖分類號：TP301文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2009)06-2101-03

doi:10.3969/j.issn.1001-3695.2009.06.030

Extension of rough set model in incomplete information system

SHEN Jin-biao

(School of Mathematics Information Science， Guangxi University， Nanning 530004， China)

Abstract:This paper investigated the incomplete information system in which lost and absent unknown values were coexisting deeply.In such information systems，proposed a reflective relation which was based on the controlling of one parameter.Compared the rough set model based on this reflective relation with some other existing rough set models which had been used to deal with incomplete information system.Analyzed an illustrative example to indicate the validity of the new-defined binary relation.

Key words:incomplete information system(IIS); rough set; tolerance relation; similarity relation; characteristic relation

0 引言

粗糙集理論(rough set theory，RST)是由波蘭科學(xué)家Pawlak^[1]于20世紀(jì)80年代初提出的一種處理含糊和不精確性問題的新型數(shù)學(xué)工具。近年來，為了適應(yīng)實(shí)際工程應(yīng)用的需求，已有許多學(xué)者提出了各種各樣的粗糙集模型^[2]，如可變精度粗糙集、概率粗糙集、模糊粗糙集等。其中不完備信息系統(tǒng)(IIS)中各種拓展粗糙集模型的應(yīng)用已成為粗糙集理論發(fā)展的一個重要方面^[3，4]。

一般來說，IIS中的未知屬性值具有兩種解釋：a)所有的未知屬性值僅僅是被遺漏的，但又是確實(shí)存在的；b)所有的未知屬性值是被認(rèn)為是丟失的，是不允許被比較的。根據(jù)第一種解釋，Kryszkiewicz^[5]提出了IIS中的容差關(guān)系，進(jìn)而進(jìn)行了知識約簡的方法研究；根據(jù)第二種解釋，Stefanowski等人^[6]構(gòu)建了其中的相似關(guān)系并建立了近似集的概念。可以看出，無論Kryszkiewicz還是Stefanowski所做的工作都認(rèn)為IIS中的未知屬性值僅僅具有一種可能的解釋，即遺漏型或丟失型。然而現(xiàn)實(shí)世界中IIS的情況可能更為復(fù)雜，如Grzymala-Busse^[7]就考慮了一種廣義的IIS。其中的未知屬性值有的是屬于遺漏型，而有的則屬于丟失型。為了使用RST處理這種同時具有遺漏和丟失型未知屬性IIS，Grzymala-Busse提出了特征關(guān)系，特征關(guān)系是結(jié)合了容差和相似關(guān)系的一種推廣形式。

隨著對特征關(guān)系的深入研究，發(fā)現(xiàn)由特征關(guān)系所得到的特征類存在兩種不盡合理的情況：a)可能會將兩個沒有任何明確相同屬性值的對象誤判在同一類中；b)在信息系統(tǒng)中屬性數(shù)目非常多時兩對象僅具有極少數(shù)相同的屬性值就被歸為一類。因此，筆者在深入研究現(xiàn)有廣義的IIS模型的基礎(chǔ)上提出了一種新的二元關(guān)系，較好地解決了上述問題。

1 基本概念

1.1 不完備信息系統(tǒng)

一個IIS為一個四元組:S=〈U，AT，V，f〉。其中：U是一個被稱為論域的非空有限的對象集合;AT是非空有限的屬性集合;對于a∈AT，有a:U→Va，Va是屬性a的值域(可包丟失型、遺漏型空值，文中分別用“?”和“*”表示) ，全體屬性值域集合V=∪a∈ATVa；定義f為信息函數(shù)，對于a∈AT，x∈U，有f(x，a)∈Va。

1.2 容差關(guān)系

在Kryszkiewicz提出的容差關(guān)系中，最主要的一個概念是賦予信息表中沒有值的元素一個“*”值，“*”值是一種任何值都有可能的值。這個解釋與這樣的值僅僅是被遺漏但又確實(shí)存在的解釋相對應(yīng)。換句話說就是由于不精確的知識迫使人們?nèi)ヌ幚碇挥胁糠中畔⒌牟煌陚湫畔⒈怼８鱾€體對象具有潛在的完備信息，而當(dāng)前只是遺漏了這些值。

定義1 在不完備信息系統(tǒng)S中，若所有未知屬性值均被認(rèn)為是遺漏型(“*”) ，則對于AAT，由A決定的容差關(guān)系記為T(A)且

T(A)={(x，y)∈U2:a∈A，f(x，a)=f(y，a)∨f(x，a)=*∨f(y，a)=*}

1.3 相似關(guān)系

在Stefanowski等人提出的基于相似關(guān)系對rough集理論進(jìn)行擴(kuò)充的方法中，認(rèn)為對象可能被不完全描述的原因不僅可能是由于知識不精確，還可能是由于干脆就不可能用所有的屬性來描述它們。不認(rèn)為未知值是不確定的，而是當(dāng)前不存在的，不允許比較未知值。基于這種觀點(diǎn)，各對象可能有或多或少的完全描述，這取決于可能采用多少屬性。從這種觀點(diǎn)看，只要兩個對象的已知屬性值相同，就可以認(rèn)為一個個體對象x與另一個對象y相似。

定義2 在不完備信息系統(tǒng)S中，若所有未知屬性值均被認(rèn)為是缺席型(“?”)，則對于a∈AT，由A決定的相似關(guān)系記為S(A)且

S(A)={(x，y)∈U2:a∈A：f(x，a)=?∨f(x，a)=f(y，a)}

顯然，相似關(guān)系是不對稱的，但是傳遞的、自反的。相似關(guān)系是對象集合上的偏序。實(shí)際上，非對稱相似關(guān)系可以認(rèn)為是包含關(guān)系的一個代表，因?yàn)橹灰獂的描述包含于y的描述就認(rèn)為x與y相似。

1.4 特征關(guān)系

很明顯，對于如表1所示的IIS，無論是容差關(guān)系還是相似關(guān)系均無法對論域進(jìn)行分類，因?yàn)槿莶铌P(guān)系僅考慮IIS中的所有未知屬性值都是遺漏型的，而相似關(guān)系則考慮IIS中的所有未知屬性值都是丟失型的。因此，對于同時具有遺漏型和丟失型未知屬性值的IIS，Grzymala-Busse構(gòu)建了其中的特征關(guān)系如下定義所示。

定義3 設(shè)S為一IIS，對于AAT，則由A決定的特征關(guān)系表示為K(A)且

K(A)={(x，y)∈U2:a∈A∧f(x，a)≠?，

f(x，a)=f(y，a)∨f(x，a)=*∨f(y，a)=*}

定義4 設(shè)S為一IIS，有AAT，則對于XU，X基于特征關(guān)系K(A)的下、上近似集分別記為AK(X)，K(X)且

AK(X)={x∈U:KA(x)X}

K(X)={x∈U:KA(x)∩X≠}

其中:KA(x)={y∈U:(x，y)∈K(A)}。

如果在IIS中，所有未知屬性值均被認(rèn)為是遺漏型的，則特征關(guān)系R(A)就退化為容差關(guān)系；從另一角度來看，若IIS中所有未知屬性值均被看做是丟失型的，則特征關(guān)系 (A)就退化為非對相似關(guān)系。因此，可以將特征關(guān)系R(A)看做是容差關(guān)系與非對稱相似關(guān)系的一種混合表現(xiàn)形式。其中既保留了容差關(guān)系的相關(guān)性質(zhì)，也保留了非對稱相似關(guān)系的相關(guān)性質(zhì)。

特征關(guān)系既可以處理具有遺漏型， 也可以處理具有缺席型未知屬性值的不完備信息系統(tǒng)。它雖然是繼承了容差關(guān)系和非對稱相似關(guān)系的優(yōu)點(diǎn)，具有更為合理的分類能力， 但也存在一些問題。首先， 特征關(guān)系將兩個沒有任何已知屬性值的不同的對象歸為一類， 如x={0，*，1，2，*}，y={*，1，*，*，1}；其次， 在數(shù)據(jù)庫中的屬性數(shù)目非常多時， 兩對象僅僅具有很少的已知相同屬性值就可以被劃分在同一類中。在這兩種情形下，兩對象僅僅是具有不可分辨的可能性， 并且由于未知屬性值的大量存在， 這種可能性非常小。例如x={0，*，1，2，1}，y={*，1，*，*，1}，此時在所有五個屬性上x與y僅有一個相同的已知屬性值， 然而特征關(guān)系卻把它們歸為一類，這很牽強(qiáng)。筆者在深入研究現(xiàn)有廣義的IIS模型的基礎(chǔ)上提出了一種新的特征關(guān)系，較好地解決了上述問題。

2 新的二元關(guān)系

2.1 一種新的二元關(guān)系

設(shè)MAT（x，y）={a∈AT:f(x，a)=*∨f(y，a)=*}表示對象x或y取值為*的屬性集合，NAT(x，y)={a∈AT:f(x，a)=？∨f(y，a)=？}表示對象x或y取值為?的屬性集合。

令NAT（x）={a∈AT:f(x，a)≠?}，D={a∈AT:NAT(x)∩MAT(x，y)≠}，E={a∈AT:NAT(x)∩MAT(x，y)≠}。

定義5 設(shè)S為一IIS，對于AAT，則由A決定的新二元關(guān)系表示為Rβ(A)且

Rβ(A)={(x，y)∈U2:(a∈D，(f(x，a)=f(y，a)∨f(x，a)=*∨f(y，a)=*)∧(|MAT(x，y)|/(|AT|-|NAT(x)|)≤β))∨(a∈NAT(x，y)，f(x，a)=f(y，a)=?)∨(a∈E，f(x，a)=f(y，a))}

其中：0≤β≤1。

如果對象x和y有所給的二元關(guān)系，則表示對象x和y在屬性上的取值，除有缺席(?)數(shù)據(jù)外，要么取值全相等或取值大部分相等。

定義6 設(shè)S為一IIS，有AAT，則對于XU，X基于二元關(guān)系Rβ(A)的下、上近似集分別記為AβR(X)、βR(X)且

AβR(X)={x∈U:RβA(x)X}

βR(X)={x∈U:RβA(x)∩X≠}

其中:RβA(x)={y∈U:(x，y)∈Rβ(A)}。

定理1 設(shè)S為一IIS，對于AAT，由A決定的新二元關(guān)系表示為Rβ(A)，若0＜α≤β≤1，則RαA(x)RβA(x)。

證明 由定義易證。

定理2 設(shè)S為一IIS，對于AAT，由A決定的新二元關(guān)系表示為Rβ(A)，特征關(guān)系為K(A)，則RβA(x)KA(x)。

證明 由定義易證。

2.2 有關(guān)性質(zhì)

定理3 設(shè)S為一IIS，對于AAT，由A決定的新二元關(guān)系表示為Rβ(A)，對于任意XU，有

AβR(X)XβR(X)(1)

AβR(X)=U-βR(U-X)(2)

證明 式（1）對任意x∈AβR(X)，RβA(x)X，而x∈RβA(x)，x∈X，故

AβR(X)X。

對任意x∈X，x∈RβA(x)，有RβA(x)∩X≠，故XβR(X)。綜上有T(X)X(X)。

式（2）對任意x∈AβR(X)，RβA(x)XRβA(x)∩(U-X)=xβR(U-X)x∈U-βR(U-X)。

3 特殊情形分析

3.1 “?”值不完備信息系統(tǒng)

在定義5所建立新的二元關(guān)系的基礎(chǔ)上，如果再將IIS系統(tǒng)特殊化，可以得到它的幾種不同表現(xiàn)形式。首先，在一個IIS中，若所有的未知屬性值均為缺席型“?”時，此時β取值定為1， 所以定義5中的二元關(guān)系就退化成為相似關(guān)系。

3.2 “*”值不完備信息系統(tǒng)

另一方面， 在一個IIS中， 若所有的未知屬性值均為丟失型“*”時，此時β的取值1， 因此分類的結(jié)果不受β的影響，從而定義5中的二元關(guān)系退化成為容差關(guān)系。若0<β<1時，定義5中的二元關(guān)系退化成為限制容差關(guān)系。

3.3 “?*”值不完備信息系統(tǒng)

在一個IIS中， 若所有的未知屬性值既有缺席型“?”和丟失型“*”時，此時β的取值為1，因此分類的結(jié)果不受β的影響，從而定義5中的二元關(guān)系退化成為特征關(guān)系。

定理4 設(shè)S為一IIS，對于AAT，由A決定的新二元關(guān)系表示為Rβ(A)，特征關(guān)系為K(A)。當(dāng)β=1時，則K(A)=R1(A)。

證明 對于任意x和y，總有|MAT(x，y)|/|AT|≤β=1成立，故K(A)=R1(A)。

定理5 設(shè)S為一IIS，對于AAT，由A決定的新二元關(guān)系表示為Rβ(A)，對于任意XU，當(dāng)0＜α≤β≤1時，則

AβR(X)AαR(X)（1）

αR(X)βR(X)（2）

證明 （1）對任意x∈AβR(X)，有RβA(x)X，由定理1，RαA(x)RβA(x)，有RαA(x)X，即x∈AαR(X)，故AβR(X)AαR(X)。

式（2）對任意x∈αR(X)，有RαA(x)∩X≠，由定理1，RαA(x)RβA(x)，有RβA(x)∩X≠。即x∈βR(X)，故αR(X)βR(X)。

定理6 設(shè)S為一IIS，對于AAT，由A決定的新二元關(guān)系表示為Rβ(A)，特征關(guān)系為K(A)。對于任意XU，則

AK(X)AβR(X)(3)

βR(X)K(X)(4)

證明 由定理2、3可易證。

4 實(shí)例分析

在表1所示的不完備信息系統(tǒng)中，根據(jù)定義3所示的特征關(guān)系，可以得到表2 中KA(xi)所示的分類結(jié)果。

根據(jù)特征關(guān)系分類是不盡合理的，如對象7與9 沒有任何已知相等的屬性值，但對象9卻被分入到特征類KA(7)中了，對象8與9也存在類似的情況， 再者， 對象7與8僅具有一個

相同的屬性值，但是對象8卻有三個未知屬性值， 因此從直覺上來看，這兩者之間不可分辨的可能性不大，對象8與6，7與10等也是同樣的道理。此時若假設(shè)β=0.25，根據(jù)定義5， 可以得到如表2中RβA(xi)所示的分類結(jié)果。

可以看出， 這樣的結(jié)果較好地解決了根據(jù)特征關(guān)系分類所產(chǎn)生的不合理情形， 較為符合人類處理數(shù)據(jù)的直觀感覺。

5 結(jié)束語

粗糙集理論由于其堅實(shí)的數(shù)學(xué)基礎(chǔ)，近年來在知識獲取、人工智能等眾多科研領(lǐng)域得到了廣泛的應(yīng)用。傳統(tǒng)的粗糙集只能處理具有完備屬性值的信息系統(tǒng)，然而在現(xiàn)實(shí)世界中由于各種原因，需處理的信息系統(tǒng)往往是不完備的。建立IIS中的拓展粗糙集模型進(jìn)行數(shù)據(jù)分析已成為粗糙集理論研究的一個熱點(diǎn)問題。以往很多學(xué)者所討論的IIS中的未知屬性值僅具有一種可能的解釋，而本文所處理的IIS同時具有缺席型和遺漏型未知屬性值，并且為了使得這種IIS中的分類結(jié)果更加符合客觀實(shí)際和人在數(shù)據(jù)處理過程中的直觀感覺，提出了一種新的帶有參數(shù)的二元關(guān)系。從文中的分析可以看出，只要合理地設(shè)置閾值β， 新建立的粗糙集模型優(yōu)于以往的各種拓展粗糙集模型。在本文工作的基礎(chǔ)上，下一步的工作就是在IIS中根據(jù)新的二元關(guān)系討論知識約簡等相關(guān)問題。

參考文獻(xiàn)：

［1］PAWLAK Z.Rough sets[J].International Journal of Computer and Information Sciences，1982，11:341-356.

[2]張文修，吳偉志.粗糙集理論與方法[M]．北京：科學(xué)出版社，2001.

[3]王國胤.Rough集理論在不完備信息系統(tǒng)中的擴(kuò)充[J].計算機(jī)研究與發(fā)展，2002，39(10):1238-1243.

[4]楊習(xí)貝，楊靜宇，吳陳，等.不完備信息系統(tǒng)中基于特征關(guān)系的粗糙集模型[J].模式識別與人工智能，2007，20(4)：450-457.

[5]KRYSZKIEWICZ W.Generation of rules from incomplete information systems[C]//KOMOROWSKI H J，ZYTKOW J M.Proc of the 1st European Symposium on Principles of Data Mining and Knowledge Discovery. Berlin: Springer-Verlag，1997:156-166.

[6]STEFANOWSKI J，TSOUKIAS A.On the extension of rough sets under incomplete information[C]//ZHONG Ning，SKOWRON A，OHSUGA S.Proc of the 7th International Workshop on New Directions in Rough Sets， Data Mining， and Granular-Soft Computing.Berlin: Springer-Verlag，1999:73-81.

[7]GRZYMALA-BUSSE J W.Characteristic relations for incomplete data:a generalization of the indiscemibility relation[C]//Proc of the 3rd International Conference on Rough Sets and Current Trends in Computing. Uppsala，Sweden:[s.n.]，2004:244-253.