關(guān)系粗糙集的鄰域擬陣結(jié)構(gòu)研究

劉艷芳，陳雪云

?

關(guān)系粗糙集的鄰域擬陣結(jié)構(gòu)研究

劉艷芳*，陳雪云

(龍巖學(xué)院信息工程學(xué)院，福建省龍巖市 364000)

本文在論域任一關(guān)系中，通過(guò)鄰域定義了一個(gè)集族，證明其滿足擬陣的獨(dú)立集公理，建立了鄰域擬陣。為了進(jìn)一步了解鄰域擬陣，研究了其極小圈、秩函數(shù)和閉包算子。同時(shí)，給出了從擬陣誘導(dǎo)關(guān)系的一種形式，研究了關(guān)系的上近似算子和由其誘導(dǎo)的擬陣閉包算子之間的關(guān)系。更進(jìn)一步的研究了從關(guān)系到擬陣再到新關(guān)系與原關(guān)系之間的關(guān)聯(lián)，尤其是，原關(guān)系通過(guò)鄰域可以等價(jià)表示新關(guān)系。

粒計(jì)算；關(guān)系粗糙集；上近似；鄰域；擬陣

引言

人類在認(rèn)識(shí)客觀世界時(shí)，根據(jù)對(duì)象的不可分辨性，或相似性，或功能性等特性將對(duì)象分成不同的子集，即粒，把那些具有相應(yīng)尺度的信息粒作為一個(gè)整體而不是個(gè)體來(lái)處理，根據(jù)問(wèn)題求解的實(shí)際需要，舍棄與當(dāng)前問(wèn)題無(wú)關(guān)的信息細(xì)節(jié)，從而簡(jiǎn)化問(wèn)題的求解。由于認(rèn)知能力有限，人類往往采用近似的方式而不是精確的方式用已知的概念去刻畫(huà)另一類事物。粗糙集理論[6]作為當(dāng)前信息處理研究領(lǐng)域中模擬人類思維和解決復(fù)雜問(wèn)題的粒計(jì)算[9]的三大分支之一，它的核心概念是基于等價(jià)關(guān)系的粒化和基于上、下近似的逼近。因此，粗糙集理論已經(jīng)在人工智能、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域獲得了廣泛的應(yīng)用。

由于等價(jià)關(guān)系的要求比較嚴(yán)格，很大程度地限制了經(jīng)典粗糙集的應(yīng)用領(lǐng)域[3]，1983年Zakowski用一個(gè)自反、對(duì)稱的二元關(guān)系替代了等價(jià)關(guān)系，建立了基于相似關(guān)系上的廣義粗糙集模型[10]；Urszula給出了基于不同二元關(guān)系上的關(guān)系粗糙集模型[7]。粗糙集體現(xiàn)了論域中對(duì)象間的不可區(qū)分性，不包含處理不精確或不確定的原始數(shù)據(jù)的機(jī)制，因此，單純地使用這個(gè)理論不一定都能有效地描述實(shí)際問(wèn)題，需要與理論相互補(bǔ)充[8]，比如模糊集、概率論、證據(jù)理論、神經(jīng)網(wǎng)絡(luò)和概念格理論等。

作為線性代數(shù)和圖論的數(shù)學(xué)理論的一種推廣，擬陣論[2]由Whitney在1935年提出的，并且組合優(yōu)化、算法設(shè)計(jì)、信息編碼和密碼學(xué)等領(lǐng)域都有著廣泛且成功的應(yīng)用。擬陣?yán)碚撚兄陚涞墓眢w系，和其他理論相結(jié)合的研究也受到了很多學(xué)者的關(guān)注并取得了一定的成果。張少譜等[11]建立了基于自反、傳遞關(guān)系的粗糙集的擬陣結(jié)構(gòu)，并用擬陣的方法為屬性約簡(jiǎn)設(shè)計(jì)了一個(gè)算法；劉艷芳等[4]提出了基于序、傳遞關(guān)系的粗糙集的擬陣結(jié)構(gòu)；為了更好的利用粗糙集與擬陣結(jié)合的理論成果；祝峰等[12]提出了粗糙擬陣，把粗糙集與擬陣融合成一體；Marek和Skowron[5]指出將粗糙集的各種推理與擬陣Greedy算法聯(lián)系在一起，便于開(kāi)發(fā)的算法尋找各類屬性集中的最大約簡(jiǎn)和最小約簡(jiǎn)，從而促進(jìn)粗糙集理論中的屬性約簡(jiǎn)算法的進(jìn)一步發(fā)展。

在論域上的任意關(guān)系上，本文通過(guò)鄰域概念給出了一個(gè)集族，證明其滿足擬陣的獨(dú)立集公理，進(jìn)而建立了基于任意關(guān)系粗糙集上的鄰域擬陣。同時(shí)，研究了關(guān)系粗糙集的上近似算子和其鄰域擬陣的閉包算子之間的關(guān)系。更進(jìn)一步，本文給出了由關(guān)系誘導(dǎo)出擬陣的構(gòu)造方法，在此基礎(chǔ)上，研究了由一個(gè)關(guān)系誘導(dǎo)出一個(gè)擬陣，再由這個(gè)擬陣誘導(dǎo)出一個(gè)新的關(guān)系與原來(lái)的關(guān)系之間的關(guān)聯(lián)。

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

本節(jié)主要介紹關(guān)系粗糙集和擬陣，并給出了一些基本的概念和性質(zhì)。

1.1 關(guān)系粗糙集

粗糙集理論是通過(guò)基于關(guān)系鄰域概念上的一對(duì)精確集合：上近似和下近似，來(lái)對(duì)不確定的目標(biāo)集合進(jìn)行確定的近似描述。

粗糙集理論是通過(guò)基于關(guān)系鄰域概念上的一對(duì)精確集合：上近似和下近似，來(lái)對(duì)不確定的目標(biāo)集合進(jìn)行確定的近似描述。

定義 1[1]設(shè)是論域上任一關(guān)系。對(duì)任意的，如果，我們說(shuō)和具有關(guān)系，記作。對(duì)任意，稱集合為關(guān)于的鄰域，并記為S()。

定義 2[13]設(shè)是論域上的任一關(guān)系，。我們定義子集關(guān)于的下近似和上近似分別為：

（1）

在不引起混亂時(shí)，可將L()和H()分別簡(jiǎn)記為()和()。

由于關(guān)系粗糙集中上、下近似算子滿足對(duì)偶性，所以下面只給出上近似算子滿足的性質(zhì)。

命題 1[13]設(shè)是上的任一關(guān)系，。H滿足以下性質(zhì)：

(1)； （3）

(2)； （4）

(3)（5）

1.2 擬陣

作為一種同時(shí)推廣了圖和矩陣的概念，擬陣具有完備的公理系統(tǒng)，有許多不同但是等價(jià)的定義方法。下面從獨(dú)立集的角度定義擬陣，在此基礎(chǔ)上進(jìn)一步介紹擬陣的相關(guān)集、極小圈、秩函數(shù)、閉包算子和閉集等概念和性質(zhì)。如果沒(méi)有特別指出，相關(guān)內(nèi)容可參考文獻(xiàn)[2]。

定義 3設(shè)I是上的子集族。稱(, I)為一擬陣，常記為= (, I)，如果I滿足如下三個(gè)條件：

(I3) 若1,2I且|1| < |2|，則存在2－1使得1{}I。

子集族I中的元素稱為擬陣的獨(dú)立集。因此公理(I1)、(I2)和(I3)稱為擬陣的獨(dú)立集公理。

為了方便地理解擬陣的概念，給出下面不太常用的集合論的運(yùn)算記號(hào)。

定義 4 設(shè)A是上的一個(gè)子集族。定義：

(A) = {: 對(duì)任意A，若，則=（6）

(A) = {:A}。 （7）

定義 5 設(shè)= (, I)是個(gè)擬陣，。如果I，則稱為的一個(gè)相關(guān)集，記D()為的全體相關(guān)集的集合，則D() =(I)。

定義 6 極小的相關(guān)集叫做極小圈，記C()為擬陣的全體極小圈的集合，則有C() =((I))。

作為擬陣的一個(gè)量化工具，秩函數(shù)是一個(gè)重要的概念。

定義 7 設(shè)= (, I)是個(gè)擬陣。稱r為擬陣的秩函數(shù)，其中

r() ={||:,I}。 （8）

定義8設(shè)= (, I)是個(gè)擬陣，。在中的閉包為

cl() = {:r({}) =r()}。 （9）

若子集滿足=cl()，則稱為的閉集。

擬陣和閉包算子是一一對(duì)應(yīng)的，因此，可以從閉包算子的角度來(lái)進(jìn)行定義擬陣。

命題 2 設(shè):()()是個(gè)算子。則存在一個(gè)擬陣使得=cl當(dāng)且僅當(dāng)滿足下列性質(zhì)：

2 鄰域擬陣的性質(zhì)

本節(jié)提出了關(guān)系粗糙集的鄰域擬陣，并研究了其極小圈、秩函數(shù)和閉包的表達(dá)形式。首先，給出了基于鄰域上的一個(gè)集族。

定義 9 設(shè)是上的任一關(guān)系。定義基于下的一個(gè)集族如下：

I() = {:,S()S() （10）

事實(shí)上，為論域上任意關(guān)系，I()滿足擬陣的獨(dú)立集公理。

命題 3 設(shè)是上的一個(gè)關(guān)系。那么I()滿足定義3中的(I1)、(I2)和(I3)。

假設(shè)1I()，由式（10）可知，存在1使得S() =S()。由1，則有使得S() =S()，這和已知條件I()相互矛盾。因此，必有1I()。

(I3)：如果1,2I()，且|1| < |2|，則存在元素使得1{}I()。

因?yàn)?,2I()，由式（10）可知，則對(duì)于任意的1,11,11且2,22,22, 都有S(1)S(1)且S(2)S(2)。假設(shè)對(duì)任意的2－1，都有1{}I()，則存在唯一的一個(gè)元素1－2使得S() =S()。因此，有|2－1||1－2|，即|2||1|，這和已知條件|1| < |2|相互矛盾。因此，假設(shè)不成立，所以存在一個(gè)元素2－1使得1{}I()。

由上面命題可知，對(duì)論域上任一關(guān)系，I()能誘導(dǎo)出一個(gè)擬陣。

定義 10設(shè)是上的任一關(guān)系。以I()為獨(dú)立集集族的擬陣稱為鄰域擬陣，記為()(,I())。

為了能客觀了解鄰域擬陣的結(jié)構(gòu)，下面給出了一具體的例子。

例 1設(shè)= {,,}，且= {(,), (,), (,), (,), (,), (,)}是上的關(guān)系。因?yàn)?i>S() = {,},S() = {,},S() = {,}。由式（10）可知，鄰域擬陣()(,I())的獨(dú)立集集族I() = {, {}, {}, {}, {,}, {,}}。

在下面的命題，我們給出了鄰域與其誘導(dǎo)出的鄰域擬陣的相關(guān)集之間的關(guān)聯(lián)。

命題 4設(shè)是上的任一關(guān)系，且()(,I())是由誘導(dǎo)的鄰域擬陣。則有

D(()) = {:,, 滿足S() =S()}。（11）

極小的相關(guān)集就是擬陣的極小圈。根據(jù)上面的命題，很容易得到鄰域擬陣極小圈的表達(dá)式。

命題 5設(shè)是上的任一關(guān)系，且()(,I())是由誘導(dǎo)的鄰域擬陣。則有

C(()) = {{,}:,S() =S()}。 （12）

由上面的命題可知，論域上任一關(guān)系誘導(dǎo)出的鄰域擬陣的每個(gè)極小圈的基數(shù)都是2。秩函數(shù)是擬陣中的一個(gè)量化工具。下面從量化的角度研究鄰域擬陣的秩函數(shù)。

命題 6設(shè)是上的任一關(guān)系，且()(,I())是由誘導(dǎo)的鄰域擬陣。對(duì)，有

r(R)() = |{S() :}|。 （13）

證明由式（8），r(R)() ={||:,I()}。假設(shè)r(R)() = |I|，其中I且II()。由式（10），可知I() = {:,S()S()}。因此，有|I| = |{S():I}|。因此，只需證明{S():I} = {S():}。

在秩函數(shù)的基礎(chǔ)上，提出了擬陣中的閉包算子。下面從鄰域的角度研究鄰域擬陣的閉包算子。

命題 7設(shè)是上的一個(gè)關(guān)系，且()(,I())是由誘導(dǎo)的鄰域擬陣。對(duì)，有

cl(R)() = {:，滿足S() =S()}。（14）

由上面的眾多命題可知，由任一關(guān)系誘導(dǎo)出的鄰域擬陣的特性均可由其關(guān)系等價(jià)刻畫(huà)。那么作為粗糙集中的兩個(gè)核心概念，上近似和下近似與關(guān)系粗糙集的鄰域擬陣有什么樣的關(guān)系呢？下面給出一具體的例子。

表 1 上近似和下近似與關(guān)系粗糙集的鄰域擬陣

例 2 設(shè)= {,,}，且= {(,), (,), (,), (,), (,)}是上的關(guān)系。由定義1可得，S() = {,},S() = {,},S() = {}。由式（10），可知鄰域擬陣()(,I())的獨(dú)立集集族為I() = {, {}, {}, {}, {,}, {,}}。根據(jù)式（2）和式（8），得到鄰域擬陣的閉包和關(guān)系粗糙集的上近似如表1。則當(dāng)= {}，有cl(R)()H()，H()cl(R)()。

當(dāng)關(guān)系是自反關(guān)系時(shí)，由這個(gè)關(guān)系誘導(dǎo)出的鄰域擬陣的閉包算子包含在基于這個(gè)自反關(guān)系的上近似算子內(nèi)。

命題 8 設(shè)是上的任一關(guān)系，且()(,I())是由誘導(dǎo)的鄰域擬陣，。當(dāng)是自反的，則有cl(R)()H()。

證明由式（14）可知，cl(R)() = {:, 滿足S() =S()}，則對(duì)于任意的cl(R)()，存在一個(gè)元素使得S() =S()。由于是自反的，可得S()，則S()。根據(jù)式（2）知H() = {:S()}，因此，H()。

如果關(guān)系粗糙集的上近似包含由這個(gè)關(guān)系粗糙集誘導(dǎo)出的鄰域擬陣的閉包，那么這個(gè)關(guān)系一定是自反關(guān)系嗎？為了解決這個(gè)問(wèn)題，引入下面的命題。

命題 9[13]設(shè)是上的任一關(guān)系，。是自反的當(dāng)且僅當(dāng)H()。

命題 10設(shè)是上的任一關(guān)系，且()(,I())是由誘導(dǎo)的鄰域擬陣，且。如果cl(R)()H()，那么是自反的。

推論 1設(shè)是上的任一關(guān)系，且()(,I())是由誘導(dǎo)的鄰域擬陣，且。cl(R)()H()的充分必要條件是是自反的。

3 鄰域擬陣與擬陣的粗糙集的關(guān)系

為了深一層研究關(guān)系粗糙集的鄰域擬陣，本節(jié)引用了一種逆序構(gòu)造：從擬陣誘導(dǎo)出一個(gè)關(guān)系。

定義 11[2]設(shè)(, I)是一個(gè)擬陣。定義上的一個(gè)關(guān)系()如下：對(duì)任意的,，

()=或{,}C()。 （15）

我們稱()是由擬陣誘導(dǎo)的關(guān)系。

事實(shí)上，()是論域上的一個(gè)等價(jià)關(guān)系。

命題 11[2]設(shè)(, I)是一個(gè)擬陣，()是擬陣誘導(dǎo)出的關(guān)系。則()是上的等價(jià)關(guān)系。

例 3 設(shè)= (, I)是個(gè)擬陣，其中= {,,}，I = {, {}, {}}。因?yàn)镃() = {{,}, {}}，因此由式（15），可得() = {(,), (,), (,), (,), (,)}，因此，()是上的一個(gè)等價(jià)關(guān)系。

擬陣的閉包算子和由擬陣誘導(dǎo)出的粗糙集的上近似算子是什么關(guān)系呢？為解決這個(gè)問(wèn)題，我們引入下面的命題。

命題 12[2]設(shè)= (, I)是個(gè)擬陣，C()是的極小圈集族，cl是的閉包算子。則

cl()={:C()，滿足{}}。（16）

命題 13 設(shè)(, I)是一個(gè)擬陣，()是擬陣的誘導(dǎo)的關(guān)系。對(duì)任意的，都有H(M)()cl()。

但一個(gè)擬陣誘導(dǎo)出的關(guān)系粗糙集的上近似不包含該擬陣的閉包。下面給出一具體的反例。

例 4 (繼續(xù)例3) 令= {}。由式（16），可得cl() = {,,}。根據(jù)式（2），可得H(M)() = {,}。因此，cl()H(M)()。

由一個(gè)擬陣誘導(dǎo)出的關(guān)系粗糙集的上近似和該擬陣的閉包在什么條件下相等呢？

定理 1 設(shè)(, I)是一個(gè)擬陣，()是擬陣的誘導(dǎo)的關(guān)系粗糙集。對(duì)任意的，都有H(M)() = cl()的充分必要條件是對(duì)于任意的C()都有|| = 2。

本文中給出了兩種構(gòu)造：從關(guān)系誘導(dǎo)出一個(gè)鄰域擬陣，從擬陣產(chǎn)生一個(gè)關(guān)系。因此，一個(gè)擬陣可以誘導(dǎo)出一個(gè)關(guān)系，這個(gè)關(guān)系緊接著可以誘導(dǎo)出一個(gè)相應(yīng)的擬陣。類似地，一個(gè)關(guān)系可以誘導(dǎo)出一個(gè)擬陣，這個(gè)擬陣緊接著誘導(dǎo)出一個(gè)關(guān)系。那么原來(lái)的擬陣和誘導(dǎo)出的新擬陣以及原來(lái)的關(guān)系和誘導(dǎo)出的新關(guān)系之間有什么樣的聯(lián)系呢？

定理 2 設(shè)是上的一個(gè)關(guān)系，()是由關(guān)系誘導(dǎo)的鄰域擬陣，且(())是由擬陣()的誘導(dǎo)的粗糙集，則有

(()) = {(,)×:S() =S()}。 （17）

證明根據(jù)式（14）可知C(()) = {{,}:,S() =S()}。根據(jù)式（15）的概念，有(())=或{,}C(())S() =S()。

定理 3設(shè)是上的一個(gè)擬陣，()是擬陣的誘導(dǎo)的關(guān)系粗糙集，且(())是由關(guān)系()誘導(dǎo)出的鄰域擬陣。那么(()) =的充分必要條件是對(duì)任意的C()，都有|| = 2。

4 結(jié)語(yǔ)

本文從關(guān)系中鄰域概念的角度創(chuàng)建了關(guān)系粗糙集的鄰域擬陣，研究了其相關(guān)集、極小圈、秩函數(shù)和閉包算子等特性。為了更深層的了解鄰域擬陣，給出了從擬陣到關(guān)系的逆構(gòu)造方法，并進(jìn)一步研究了這兩種構(gòu)造方法之間的關(guān)聯(lián)。

[1] 耿素云, 屈婉玲, 王捍貧. 離散數(shù)學(xué)教程[M]. 北京大學(xué)出版社, 2009.

[2] 賴虹建. 擬陣論[M]. 高等敎育出版社, 2002.

[3] Lin T Y. Topological and fuzzy rough sets[M]//Intelligent Decision Support. Springer Netherlands, 1992: 287-304.

[4] Liu Y, Zhu W. Matroidal structure based on serial and transitive relations[J], Journal of Applied Mathematics, 2012: (2012): Article ID 429737, 16 pages.

[5] Marek V W, Skowron A. Rough sets and matroids[J]. Transactions on Rough Sets XVII. Springer Berlin Heidelberg, 2014: 74-81.

[6] Pawlak Z. Rough sets[J]. International Journal of Computer & Information Sciences, 1982, 11(5): 341-356.

[7] Wybraniec-Skardowska U. On a generalization of approximation space[J]. Bulletin of the Polish Academy of Sciences. Mathematics, 1989, 37(1-6): 51-62.

[8] 史忠植. 知識(shí)發(fā)現(xiàn)[M]. 清華大學(xué)出版社, 2002.

[9] Zadeh L. Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic[J]. Fuzzy Sets and Systems, 1997, 90(2): 111-127.

[10] Zakowski W. Approxiamtions in the space[J]. Demonstratio Mathematica, 1983, 16: 761-769.

[11] Zhang S, Wang X, Feng T, et al. Reduction of rough approximation space based on matroid[M]//Machine Learning and Cybernetics (ICMLC), 2011 International Conference on. IEEE, 2011, 1: 267-272.

[12] Zhu W, Wang S. Rough matroids based on relations[J]. Information Sciences, 2013, 232: 241-252.

[13] Zhu W. Generalized rough sets based on relations[J]. Information Sciences, 2007, 177(22): 4997-5011.

Neighborhood Matroid of Relation-Based Rough Set

LIU Yanfang*, CHEN Xueyun

(Institute of Information Engineering, Longyan University, Longyan Fujian 364000, China)

For a relation on a universe, a family of subsets is defined through neighborhood, and then is proved to satisfy the independence axiom of matroids, based on which, we propose a neighborhood matroid of relation-based rough sets. In order to study this type of matroids, we research its circuit, rank function and closure operator. Meanwhile, we propose another construction which is from a matroid to a relation, and investigate the relationship between the upper approximation of the relation and the closure of the matroid. Furthermore, we study the connection between a relation and a new relation induced by the matroid which is induced by the original relation. Especially, the new relation can be equally expressed by the original relation.

granular computing; relation-based rough set; upper approximation; neighborhood; matroid

1672-9129(2016)02-0006-05

TP18

A

2016-09-10；

2016-09-21。

國(guó)家自然科學(xué)基金面上項(xiàng)目（61379049），龍巖學(xué)院百名青年教師攀登項(xiàng)目（LQ2015031），龍巖學(xué)院協(xié)同創(chuàng)新項(xiàng)目（張凌）；大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目（S20141004）。

劉艷芳(1987-)，女，河南省濮陽(yáng)市，龍巖學(xué)院教師，研究生，主要研究方向：粗糙集與粒計(jì)算、人工智能和機(jī)器學(xué)習(xí)；陳雪云(1976-)，女，福建省漳平市，龍巖學(xué)院副教授，碩士，主要研究方向：數(shù)據(jù)挖掘、模式識(shí)別和機(jī)器學(xué)習(xí)。

(*通信作者電子郵箱liuyanfang003@163.com)