基于邊界域的變精度粗糙集

馬周明，王育齊，林依婷

(1.閩南師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，福建 漳州 363000；2.閩南師范大學(xué) 計(jì)算機(jī)學(xué)院，福建 漳州 363000；3.數(shù)字福建氣象大數(shù)據(jù)研究所，福建 漳州 363000)

0 引 言

粗糙集理論[1]作為一種處理不精確、不確定、不完備知識(shí)和數(shù)據(jù)的表示、學(xué)習(xí)、分類方法，在大數(shù)據(jù)快速發(fā)展的今天，已逐漸成為人工智能理論基礎(chǔ)方向研究的重要分支。它在機(jī)器學(xué)習(xí)、模式識(shí)別、數(shù)據(jù)挖掘、信息處理、圖像處理、醫(yī)學(xué)診斷等諸多領(lǐng)域得到了一些較好的應(yīng)用[2-9]。

粗糙集理論的核心思想是利用分類方法，將等價(jià)關(guān)系確定的等價(jià)類當(dāng)作已知的知識(shí)集合。進(jìn)而，利用這些知識(shí)來表示任意的對(duì)象集。通過一對(duì)集值函數(shù)：上下近似算子，考慮已知知識(shí)包含于對(duì)象集，還是至少與對(duì)象集相交不空，得到對(duì)象集在該已知知識(shí)框架下的近似范圍。該理論最大的優(yōu)勢(shì)在于，不需要通過任何先驗(yàn)知識(shí)或主觀判斷，完全依據(jù)數(shù)據(jù)對(duì)任意對(duì)象集進(jìn)行一定知識(shí)框架下的刻畫。這對(duì)知識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖據(jù)具有非常重要的價(jià)值。然而經(jīng)典粗糙集的這種包含關(guān)系，在現(xiàn)實(shí)生活中往往太過嚴(yán)苛。從而，隨著數(shù)據(jù)量的激增和類型的日益復(fù)雜，嚴(yán)格的包含關(guān)系作為粗糙集依賴的描述工具，在一定程度上限制了它在很多復(fù)雜環(huán)境下的應(yīng)用和推廣?；诖耍琙iarko提出了基于一定包含程度的變精度粗糙集模型[10]。其理論的基本思想是在經(jīng)典粗糙集中給出一個(gè)閾值，即允許在一定閾值范圍內(nèi)的錯(cuò)誤分類率存在。經(jīng)典粗糙集就是這種變精度粗糙集閾值為0的特殊情形。因此，變精度粗糙集是經(jīng)典粗糙集的推廣。變精度粗糙集有利于發(fā)掘出看似沒有關(guān)聯(lián)的數(shù)據(jù)之間的潛在聯(lián)系。目前，變精度粗糙集無論在理論研究還是在模型推廣方面，都取得較好的發(fā)展。比如，雙論域情形下的變精度模型及其應(yīng)用[11]，基于覆蓋的變精度粗糙集研究[12-13]，模糊環(huán)境下的變精度粗糙集推廣等[14-19]。而且在一些領(lǐng)域得到了比較廣泛的應(yīng)用[20-21]。

變精度粗糙集主要側(cè)重于將經(jīng)典粗糙集中的嚴(yán)格包含關(guān)系放寬為一定程度上的多數(shù)包含關(guān)系。在數(shù)據(jù)處理過程中，主要側(cè)重已有知識(shí)框架下的知識(shí)完整性，這就不可避免地失去了經(jīng)典近似算子最基本的自反性所對(duì)應(yīng)的公理化特征:對(duì)象集的下近似包含于對(duì)象集，且對(duì)象集包含于其上近似之中。在經(jīng)典粗糙集的推廣研究中，基于其不確定區(qū)域，即邊界的功能重要性，可直接研究對(duì)象集在一定知識(shí)分類下的邊界區(qū)域，從而出現(xiàn)了基于邊界域的粗糙集模型[22]。該模型首先考慮對(duì)象集的不確定區(qū)域，或者邊界區(qū)域，在此基礎(chǔ)上給出相應(yīng)的上下近似。和經(jīng)典粗糙集相比，基于邊界域的粗糙集從不同的側(cè)面對(duì)經(jīng)典粗糙集進(jìn)行了闡述。并且和經(jīng)典粗糙集相比，它具有更良好的性質(zhì)，比如在一般二元關(guān)系下，它總是具有原來自反性和對(duì)稱性對(duì)應(yīng)的公理化特征。為了進(jìn)一步探索變精度粗糙集不同情形下的結(jié)構(gòu)和性質(zhì)，本文研究了基于邊界域的變精度粗糙集，給出了3類帶有閾值的不同邊界域。在此基礎(chǔ)上，定義了3類相應(yīng)的基于邊界域的變精度粗糙集模型。分別研究了它們的邊界算子以及近似算子的性質(zhì)。最后，以經(jīng)典粗糙集作為參照，對(duì)最初的變精度粗糙集和這3類基于邊界域的變精度粗糙集進(jìn)行了比較研究。第Ⅰ類變精度模型是已有經(jīng)典變精度粗糙集模型的推廣，第Ⅱ類變精度模型則是經(jīng)典粗糙集模型的直接推廣。這2類變精度模型都側(cè)重于從局部多數(shù)包含的角度刻畫對(duì)象集。第Ⅲ類變精度模型則從對(duì)象集的邊界域，即整體多數(shù)包含的角度描述所研究的對(duì)象集合。

1 基于邊界域的粗糙集

基于邊界域的粗糙集的基本方法，是從優(yōu)先構(gòu)造邊界集出發(fā)，然后給出相關(guān)上下近似算子。下面介紹有限論域U中任意對(duì)象集X關(guān)于二元關(guān)系R的邊界等相關(guān)基本概念。

定義1[22]設(shè)R為有限論域U上的任意二元關(guān)系，?X?U，其余集記為-X，稱

BRL(X)={x∈X|?y∈-X,xRy∨yRx}，

BRH(X)={x∈-X|?y∈X,xRy∨yRx}

分別為集合X基于二元關(guān)系R的下邊界集和上邊界集。并將

BR(X)=BRL(X)∪BRH(X)

稱為集合X基于二元關(guān)系R的邊界集，簡(jiǎn)稱二元關(guān)系邊界。顯然

BR(X)={x|?y∈xRy∨yRx,(x∈X∧

y∈-X)∨(x∈-X∧y∈X)}

有了邊界集的概念，則稱集合

分別為集合X的下近似集和上近似集，X-BR(X)表示集合X與其邊界集BR(X)的差集。

定理1基于邊界域的粗糙集近似算子和經(jīng)典近似算子等價(jià)的充要條件是論域U上二元關(guān)系R是其上的相容關(guān)系。

換言之，論域U上的任意二元關(guān)系R和其相容閉包的基于邊界域的粗糙集近似算子和經(jīng)典近似算子完全等價(jià)。其中，二元關(guān)系R的相容閉包是指包含R的最小相容關(guān)系(滿足自反和對(duì)稱)。由于經(jīng)典粗糙集是在等價(jià)關(guān)系基礎(chǔ)上產(chǎn)生的。綜上，基于邊界域的粗糙集和經(jīng)典粗糙集在形式上自然是完全等價(jià)的。

2 基于邊界域的變精度粗糙集Ⅰ

經(jīng)典粗糙集中的近似算子主要利用了集合的包含關(guān)系。對(duì)于占絕對(duì)大多數(shù)的包含或者按照用戶需求的一定程度上的包含，經(jīng)典粗糙集顯然無法滿足其要求，從而產(chǎn)生了變精度粗糙集，首先介紹下面一些基本的概念。

定義2[23]設(shè)U為有限論域，?X,Y?U，稱D(Y/X)為集合X在Y中的包含度，如果其滿足:

(1)0≤D(Y/X)≤1;

(2)當(dāng)X?Y時(shí)，D(Y/X)=1;

(3)當(dāng)X?Y?Z時(shí)，D(X/Z)≤D(X/Y)。

顯然，D(Y/X)=|X∩Y|/|X|是一個(gè)包含度。

有了包含度的定義，下面給出基于包含度的變精度粗糙集。

定義3[10]R是有限論域U上的等價(jià)關(guān)系，D為P(U)上的包含度，α∈(0.5,1]，?X?U，記

∪{[x]|D(X/[x])≥α}，

∪{[x]|D(X/[x])>1-α}

分別稱他們?yōu)榧蟈的α下近似和α上近似。

上面變精度粗糙集的定義，根據(jù)給定的閾值α來確定對(duì)象集X的上下近似集。顯然，它適當(dāng)放寬了經(jīng)典近似算子中的包含關(guān)系，將其變?yōu)槟硞€(gè)特定閾值下的多數(shù)包含關(guān)系，使得這類具有多數(shù)包含的粗糙集，在此意義下變成了精確集。下面從邊界域的角度出發(fā)，考慮變精度粗糙集的基本形式和性質(zhì)。首先給出下面的定義。

定義4設(shè)R是有限論域U上的等價(jià)關(guān)系，?X?U，稱

分別為集合X的α偽下邊界和β偽上邊界。這里(1>α>β>0)。顯然，α偽下邊界是包含度相對(duì)比較大的等價(jià)類之并，而β偽上邊界是包含度相對(duì)比較小的等價(jià)類之并。

盡管約定1>α>β>0，但事實(shí)上，為了達(dá)到多數(shù)包含的現(xiàn)實(shí)需要，往往取α為一個(gè)非常接近1且小于1的正數(shù)，而β則取一個(gè)非常接近0且大于0的正數(shù)。有了上面定義，稱集合

證明(1)—(3)根據(jù)定義4顯然,下證(4)和(5)。

證明(1)—(4)根據(jù)定義4和命題1顯然成立。下面證明(5L)，(5H)和(6LH)成立。

證畢。

定理2當(dāng)α+β=1時(shí)，基于邊界域的第Ⅰ類變精度粗糙集和已有的定義4中的變精度粗糙集完全等價(jià)，即對(duì)任意的對(duì)象集X

證明由上面定義4，下近似相等顯然。對(duì)于上近似，

{x∈U|D(X/[x])>0}-{x∈U|0

證畢。

通過上面基于邊界域的第Ⅰ類變精度粗糙可以更直觀地看出，對(duì)于任意對(duì)象集X，其下近似集不一定包含在對(duì)象集X之中。同樣，對(duì)象集X也不一定包含在其上近似集之中。因此，就經(jīng)典的變精度粗糙集而言，盡管它將嚴(yán)格包含關(guān)系放寬為多數(shù)包含關(guān)系，但同時(shí)也失去了下近似必定包含于所刻畫的對(duì)象集，以及對(duì)象集必包含于其上近似這一重要的性質(zhì)。

3 基于邊界域的變精度粗糙集Ⅱ

為了盡量讓變精度粗糙集中的上下近似算子具有經(jīng)典粗糙集中的“上”“下”內(nèi)涵，即下近似包含于對(duì)象集，且對(duì)象集包含于上近似之中。同樣，先給出下面上下邊界的定義。

定義5設(shè)R是有限論域U上的等價(jià)關(guān)系，?X?U，稱

分別為集合X的第Ⅱ類α下邊界和β上邊界。這里(1≥α>β≥0)。顯然，α下邊界是包含度相對(duì)比較小的等價(jià)類之并，而β上邊界是包含度相對(duì)比較大的等價(jià)類之并。

盡管約定1≥α>β≥0，但事實(shí)上，為了達(dá)到多數(shù)包含的現(xiàn)實(shí)需要，往往取α為一個(gè)非常接近1且小于1的正數(shù)，而β則取一個(gè)非常接近0且大于0的正數(shù)。有了上面定義，稱集合

分別為集合X的第Ⅱ類α下近似集和β上近似集。也稱其為基于邊界域的第Ⅱ類變精度粗糙集。基于邊界域的第Ⅱ類變精度粗糙，直接保證了任何對(duì)象集的下近似包含其中，它本身也包含于其上近似之中。下面考慮它們相應(yīng)的其上、下邊界和上、下近似算子的性質(zhì)。

證明(1)—(6)根據(jù)定義5顯然.下面證明(7).

證畢。

證明(1)—(4)和(6)根據(jù)定義5和命題3顯然。下面證明(5L),(5H)和(7LH)。

證畢。

4 基于邊界域的變精度粗糙集Ⅲ

基于邊界域的第Ⅱ類變精度粗糙集在適當(dāng)放寬嚴(yán)格包含的同時(shí)，也保留了經(jīng)典粗糙的一些主要的性質(zhì)。它主要從每個(gè)等價(jià)類對(duì)于對(duì)象集的包含程度進(jìn)行刻畫。然而在經(jīng)典粗糙集中，也可直接利用對(duì)象集的邊界(上下邊界之并)在對(duì)象集中的包含程度進(jìn)行刻畫。先給出一些基本相關(guān)概念。

設(shè)R為有限論域U上的等價(jià)關(guān)系，對(duì)任意的對(duì)象集X?U，稱D(X)=D(X/BR(X))為對(duì)象集X邊界包含度。顯然，對(duì)象集X邊界包含度D(X)=|BRL(X)|/|BR(X)|。它也描述了對(duì)象集上下邊界之間的比例關(guān)系，或者是經(jīng)典粗糙集中上近似集或下近似集接近對(duì)象集X的程度。

定義6設(shè)R是有限論域U上的等價(jià)關(guān)系，?X?U，稱

分別為集合X的第Ⅲ類α下邊界和β上邊界。這里(1>α>β>0)。下邊界中的“其他”包括D(X)≥α或者BLR(X)=BHR(X)=BR(X)=?；上邊界中的“其他”包括D(X)≤β或者BLR(X)=BHR(X)=BR(X)=?。

盡管約定1>α>β>0，但事實(shí)上，為了達(dá)到多數(shù)包含的現(xiàn)實(shí)需要，往往取α為一個(gè)非常接近1且小于1的正數(shù)，而β則取一個(gè)非常接近0且大于0的正數(shù)。這樣，上述數(shù)學(xué)結(jié)構(gòu)才具有更好的現(xiàn)實(shí)意義。有了上面定義，稱集合

分別為集合X的第Ⅲ類α下近似集和β上近似集。也稱其為基于邊界域的第Ⅲ類變精度粗糙集。下面考慮其上、下邊界和上、下近似算子的性質(zhì)。

證明(1)—(3)根據(jù)定義6顯然成立。下面證明(4)—(6)。

證畢。

證明根據(jù)定義6和命題5，(1)—(3)，(5)，(6)顯然成立。下面證明單調(diào)性(4L)，(4H)和α對(duì)偶性(7LH)。

證畢。

上述討論可知，對(duì)基于邊界域的第Ⅲ類變精度粗糙集，其相應(yīng)的邊界算子不滿足單調(diào)性。但是其對(duì)應(yīng)的上下近似算子卻滿足單調(diào)性。并且，基于邊界域的第Ⅱ類和第Ⅲ類近似算子具有一樣的性質(zhì)。

5 幾類近似算子之間的關(guān)系

對(duì)于基于邊界域的第Ⅰ類變精度粗糙集，根據(jù)定理2可知當(dāng)α+β=1時(shí)，它和已有的經(jīng)典變精度粗糙集完全等價(jià)。換言之，基于邊界域的第Ⅰ類變精度粗糙集本質(zhì)上是已有經(jīng)典變精度粗糙集的推廣，且二者表示方式有所不同。經(jīng)典變精度粗糙集借助包含度，適當(dāng)放寬包含條件，按照等價(jià)類在對(duì)象集中的多數(shù)包含，給出了其放寬限制的上下近似集；前者依據(jù)一定閾值下的包含度，首先給出放寬限制的邊界域，或者不確定區(qū)域，再利用其給出相應(yīng)的上下近似集。二者從代數(shù)算子的意義上具有完全相同的性質(zhì)。需要注意的是，經(jīng)典粗糙集意義上的對(duì)象集包含其下近似集，上近似集包含對(duì)象集這個(gè)重要性質(zhì)，這2種結(jié)構(gòu)一般都不成立。

下面主要考慮基于邊界域的第Ⅰ類和第Ⅱ類粗糙集之間的關(guān)系。

定理3對(duì)任意X?U和滿足1>α>β>0的任意α和β，經(jīng)典粗糙集和基于邊界域的第Ⅰ類和第Ⅱ類變精度粗糙集滿足下面的關(guān)系:

定理4對(duì)任意的X?U和滿足1>α≥β>0的任意α和β，經(jīng)典粗糙集和基于邊界域的第Ⅲ類變精度粗糙集滿足下面的關(guān)系:

6 結(jié)束語

基于邊界域的粗糙集首先定義了對(duì)象集不確定性地帶——邊界域，然后直接得到相應(yīng)的上近似集和下近似集。它和經(jīng)典近似算子完全等價(jià)的充要條件是論域上的二元關(guān)系是相容關(guān)系。在考慮邊界域基本特點(diǎn)的基礎(chǔ)上，本文提出3類基于邊界域的變精度粗糙集，并詳細(xì)討論了它們各自的性質(zhì)。其中，基于邊界域第Ⅰ類變精度粗糙集在閾值滿足α+β=1時(shí)，和最初的變精度粗糙集完全等價(jià)。而第Ⅱ類和第Ⅲ類變精度粗糙集具有比最初的變精度粗糙集更良好的一些性質(zhì)。結(jié)果表明，第Ⅰ類變精度模型是已有經(jīng)典變精度粗糙集模型的推廣，第Ⅱ類變精度模型則是經(jīng)典粗糙集的直接推廣。這2類變精度模型都側(cè)重于從單個(gè)知識(shí)粒度或等價(jià)類在對(duì)象集中的包含程度刻畫。而第Ⅲ類變精度模型從對(duì)象集的整體邊界域在對(duì)象集中的包含程度進(jìn)行描述。這些結(jié)果在大規(guī)模數(shù)據(jù)處理中，尤其是在無需嚴(yán)格包含或只要求大多數(shù)包含的環(huán)境中具有一定的實(shí)踐意義。