多粒度空間中的粗糙隸屬度與知識粒度

楊習(xí)貝，顏 成，陳 才，於東軍

(1.江蘇科技大學(xué) 計算機科學(xué)與工程學(xué)院，江蘇鎮(zhèn)江 212003;2.南京理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院，南京 210094;3.江蘇尚博信息科技有限公司，江蘇無錫 214072)

0 引言

作為粒計算的一種重要數(shù)學(xué)模型，粗糙集理論在模式識別、知識發(fā)現(xiàn)、決策分析、醫(yī)療診斷等眾多領(lǐng)域已經(jīng)取得了很大的進展。

傳統(tǒng)粗糙集及其很多拓展模型是建立在一個二元關(guān)系基礎(chǔ)上的，這個二元關(guān)系可以是不可分辨關(guān)系、相容關(guān)系、序關(guān)系甚至是沒有任何約束條件的二元關(guān)系。根據(jù)某個特定二元關(guān)系，可以得到論域上的一個劃分或者覆蓋，這個劃分或者覆蓋實際上是一些信息粒的合集，因而可將這個合集視作一個?？臻g。從這個角度來看，這些粗糙集方法是在一個?？臻g中進行概念的近似逼近，因而是單粒度空間中的粗糙集。

然而，隨著研究的不斷深入以及應(yīng)用需求的不斷增加，單粒度粗糙集方法在很多數(shù)據(jù)處理問題上不再適用。例如，在決策分析問題中，多個決策者之間的關(guān)系有可能是相互獨立的，因而需要在多個相互獨立的粒空間中進行目標(biāo)的近似逼近。從這個觀點出發(fā)，錢宇華、梁吉業(yè)等人提出了多粒度粗糙集的概念。多粒度粗糙集與單粒度粗糙集最本質(zhì)的區(qū)別是可以使用一族而非單個?？臻g中的知識來進行概念的近似逼近。

在文獻［5］中，錢宇華、梁吉業(yè)等人將由一族等價關(guān)系所形成的論域上的一族劃分看作一個多粒度空間，在這個空間中，給出了樂觀多粒度粗糙集模型。與此同時，他們將這種樂觀多粒度粗糙集模型引入不完備信息系統(tǒng)，采用一族容差關(guān)系構(gòu)建多粒度空間。在此基礎(chǔ)上，他們又在由一族劃分所構(gòu)成的多粒度空間中，給出了悲觀多粒度粗糙集模型。在上述這些工作中，多粒度空間是由一次性給出的一族二元關(guān)系得到的，因而可將其視作同步多粒度方法。

為了降低粗糙集理論中知識約簡及規(guī)則抽取的算法復(fù)雜度，錢宇華、梁吉業(yè)等人提出了基于正向近似的通用特征選擇加速算法。這種算法以核屬性集為起點，根據(jù)正向近似方法逐次從論域中去掉協(xié)調(diào)部分的對象。正向近似采用一個使得多粒度空間逐漸細(xì)化的偏序關(guān)系來表述目標(biāo)概念，這種方法可被視作異步多粒度方法。

1 多粒度粗糙集模型

令U為一個非空有限論域，R={R1，R2，…，Rm}為論域上一族等價關(guān)系的集合，稱二元組(U，R)為一個知識基。

定義1 令(U，R)為一知識基，其中R1，R2…Rm∈R，令R={R1，R…Rm}，對于?X?U，X的樂觀多粒度下近似集合(X)與上近似集合(X)分別定義為:

定義2 令(U，R)為一知識基，其中R1，R2…Rm∈R，令R={R1，R…Rm}，對于?X?U，X的樂觀多粒度下近似集合RP(X)與上近似集合RP(X)分別定義為:

由定義1和定義2可以看出，樂觀多粒度下近似要求至少有一個粒度層次上的等價類包含在目標(biāo)概念中，而悲觀多粒度下近似則要求所有粒度層次上的等價類都包含在目標(biāo)概念中，因而悲觀多粒度下近似的要求比樂觀多粒度下近似的要求更嚴(yán)格。樂觀多粒度上近似和悲觀多粒度上近似都是根據(jù)其下近似的補集來定義的。據(jù)此，很容易得到如下性質(zhì)。

定理1 令(U，R)為一知識基，其中R1，R2…Rm∈R，令R={R1，R…Rm}，對于?X?U，有:

定義3 令(U，R)為一知識基，其中R1，R2…Rm∈R，令R={R1，R…Rm}，則多粒度粗糙隸屬度函數(shù)有如下兩種形式的定義:

很明顯，多粒度空間下的粗糙隸屬度依然滿足性質(zhì)0≤maxμRX(x)≤1，0≤minμRX(x)≤1。

定理2 令(U，R)為一知識基，其中 R1，R2…Rm∈ R，令 R={R1，R…Rm}，有

證明:僅證式(9)，其他證明過程類似。

定理3 令(U，R)為一知識基，其中R1，R2…，Rm∈R，R={R1，R2…Rm}，若R1?R2?…?Rm，則對于?X?U，有:

定理3 在一個多粒度空間中，隨著等價關(guān)系的嵌套變化，樂觀多粒度下、上近似集與最粗粒度等價關(guān)系所得到的下、上近似是等價的;悲觀多粒度下、上近似集與最細(xì)粒度等價關(guān)系所得到的下、上近似是等價的。

2 多粒度空間中的知識粒度

2.1 知識粒度的兩種定義方式

令(U，R)為一知識基，其中R1，R2…Rn?R，則每個等價關(guān)系族Ri(1≤i≤n)所構(gòu)成的劃分就組成了一個多粒度空間。形如:

需要注意的是，多粒度空間MSi不是論域上一族子集的合集，而是由m個劃分所構(gòu)成的合集，所有的等價關(guān)系族R1，R2…Rm所構(gòu)成的劃分就組成了n個多粒度空間。形如:

定義4 令(U，R)為一知識基，其中R1，R2…Rm∈R，令R={R1，R2…Rm}，則多粒度空間中的知識粒度有如下兩種形式的定義:

由于本文是基于劃分的多粒度空間進行討論的，所以定義4中的知識粒度有如下等價的形式:

類似于經(jīng)典粗糙集理論，多粒度空間中的知識粒度也表示了一族等價關(guān)系的分辨能力。若知識粒度越大，則表示多粒度空間的分辨能力越弱;若知識粒度越小，則表示多粒度空間的分辨能力越強。當(dāng)?shù)葍r關(guān)系族R中只有一個等價關(guān)系時，多粒度空間中的知識粒度GK∩(R)和GK∪(R)就退化為經(jīng)典粗糙集理論中知識粒度的定義。根據(jù)上述討論，顯然有:

(1)若?Ri∈R使得U/Ri={x:x∈U}，則知識粒度GK∩(R)達到最小值;

(2)若?Ri∈R使得U/Ri={x:x∈U}，則知識粒度GK∪(R)達到最大值;

(3)若?Ri∈R使得U/Ri={U}，則知識粒度GK∩(R)達到最大值 1;(4)若?Ri∈R使得U/Ri={U}，則知識粒度GK∪(R)達到最大值1。

2.2 基于知識粒度的多粒度空間約簡

根據(jù)定義4中所示的兩種知識粒度的定義，下面討論如何對多粒度空間進行約簡。多粒度空間的約簡就是在多粒度空間中根據(jù)一定的約束條件，刪除一些冗余的?？臻g。由于在多粒度空間中，知識粒度有“交”和“并”兩種形式，所以可以分別將這兩種知識粒度作為啟發(fā)式函數(shù)來對多粒度空間進行約簡。

定義5 令(U，R)為一知識基，其中 R1，R2…Rm∈ R，令 R={R1，R2…Rm}，?R＇? R。

(1)若GK∩(R＇)=GK∩(R)，則稱R＇是R的一個“交”協(xié)調(diào)集;

(2)若 R＇是R的一個“交”協(xié)調(diào)集且對于?R＇＇?R＇，R＇＇都不是R的“交”協(xié)調(diào)集，則稱R＇是R的一個“交”約簡;

(3)若GK∪(R＇)=GK∪(R)，則稱R＇是R的一個“并”協(xié)調(diào)集;

(4)若 R＇是R的一個“交”協(xié)調(diào)集且對于?R＇＇?R＇，R＇＇都不是R的“并”協(xié)調(diào)集，則稱R＇是R的一個“并”約簡。

根據(jù)定義5可知，R的“交”約簡是保持多粒度空間中知識粒度GK∩(R)不變的最小等價關(guān)系子集;而R的“并”約簡則是保持多粒度空間中知識粒度GK∪(R)不變的最小等價關(guān)系子集。這兩種約簡的概念都可以在等價關(guān)系族R中約去一些冗余的等價關(guān)系，從而簡化由等價關(guān)系族R所形成的多粒度空間。

類似于粗糙集理論中的啟發(fā)式約簡算法，以下給出定義5中約簡算法的一般步驟。

2.2.1 求多粒度R的一個“交”約簡

輸入:等價關(guān)系族R={R1，R2…Rm}，輸出:R的一個“交”約簡R＇。步驟如下:

第1步，令R＇= ?;

第2步，判斷GK∩(R＇)=GK∩(R)是否成立，若成立，轉(zhuǎn)第6步，否則轉(zhuǎn)第3步;

第3步，對于 ?Ri∈ R-R＇，計算 GK∩(Ri∪ R＇);

第4步，取一個等價關(guān)系 Rj∈ R-R＇滿足 GK∩(Rj∪ R＇)=min{GK∩(Ri):Ri∈ R-R＇};

第5步，令R＇=Rj∪R＇，判斷GK∩(R＇)=GK∩(R)是否成立，若成立，轉(zhuǎn)第6步，否則轉(zhuǎn)第3步;

第6步，輸出“交”約簡R＇。

讓我們回到“der Morgenstern ist die Venus”這個句子上來。此處“ist”的確不是傳統(tǒng)意義上的系詞，而是一個類似于“killed”的關(guān)系詞，即帶有兩個空位的概念詞，它本身作為質(zhì)料的一部分構(gòu)成了對無序的相等關(guān)系的表達：“( ) ist ( )”，此時它的前后只能填入專名。

2.2.2 求多粒度R的一個“并”約簡

輸入:等價關(guān)系族R={R1，R2…Rm}，輸出:R的一個“并”約簡R＇。

步驟如下:

第1步，令R＇= ?;

第2步，判斷GK∪(R＇)=GK∪(R)是否成立，若成立，轉(zhuǎn)第6步，否則轉(zhuǎn)第3步;

第4步，取一個等價關(guān)系 Rj∈ R-R＇滿足 GK∪(Rj∪ R＇)=min{GK∪(Ri):Ri∈ R-R＇};

第5步，令R＇=Rj∪R＇，判斷GK∪(R＇)=GK∪(R)是否成立，若成立，轉(zhuǎn)第6步，否則轉(zhuǎn)第3步;

第6步，輸出“并”約簡R＇。

上述兩種算法的復(fù)雜度是O(m2)，其中m表示等價關(guān)系族R中等價關(guān)系的數(shù)目。

3 結(jié)論

本文以多粒度空間為研究對象，針對多粒度粗糙集模型和多粒度空間約簡問題進行了討論，提出了兩種形式的多粒度粗糙隸屬度函數(shù)，這兩種多粒度粗糙隸屬度函數(shù)是經(jīng)典粗糙集理論中粗糙隸屬度函數(shù)的拓展形式。在多粒度粗糙隸屬度函數(shù)的基礎(chǔ)上，重構(gòu)了樂觀和悲觀多粒度粗糙集。以多粒度空間中多個等價關(guān)系的交、和、并為基礎(chǔ)，定義了多粒度空間中兩種知識粒度的度量方式，并以這兩種度量為函數(shù)，給出了多粒度空間約簡的概念及啟發(fā)式算法。

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

［2］Y.H.Qian，J.Y.Liang，Y.Y.Yao，et al.MGRS:a multi-granulation rough set［J］.Information Sciences，2010，180:949-970.

［3］Y.H.Qian，J.Y.Liang，C.Y.Dang.Incomplete multigranulation rough set［J］.IEEE Transactions on Systems，Man and Cybernetics，Part A，2010，20:420-431.

［4］Y.H.Qian，J.Y.Liang，W.Wei.Pessimistic rough decision［J］.Journal of Zhejiang Ocean University:Natural Science，2010，29(5):440-449.

［5］錢宇華.復(fù)雜數(shù)據(jù)的?；瘷C理與數(shù)據(jù)建模［D］.太原:山西大學(xué)，2011.

［6］Y.H.Qian，J.Y.Liang，W.Pedrycz et al.Positive approximation:An accelerator for attribute reduction in rough set theory［J］.Artificial Intelligence，2010，174(9):597-618.

［7］錢宇華，梁吉業(yè)，王鋒.面向非完備決策表的正向近似特征選擇加速算法［J］.計算機學(xué)報，2011，34(3):435-443.