劉艷芳，陳雪云

?

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

劉艷芳*，陳雪云

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

本文在論域任一關(guān)系中，通過鄰域定義了一個集族，證明其滿足擬陣的獨立集公理，建立了鄰域擬陣。為了進(jìn)一步了解鄰域擬陣，研究了其極小圈、秩函數(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ān)系。

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

引言

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

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

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

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

1 預(yù)備知識

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

1.1 關(guān)系粗糙集

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

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

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

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

（1）

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

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

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

(1)； （3）

(2)； （4）

(3)（5）

1.2 擬陣

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

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

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

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

為了方便地理解擬陣的概念，給出下面不太常用的集合論的運算記號。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

命題 3 設(shè)是上的一個關(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()。

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

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

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

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

例 1設(shè)= {,,}，且= {(,), (,), (,), (,), (,), (,)}是上的關(guān)系。因為S() = {,},S() = {,},S() = {,}。由式（10）可知，鄰域擬陣()(,I())的獨立集集族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)出的鄰域擬陣的每個極小圈的基數(shù)都是2。秩函數(shù)是擬陣中的一個量化工具。下面從量化的角度研究鄰域擬陣的秩函數(shù)。

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

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è)是上的一個關(guān)系，且()(,I())是由誘導(dǎo)的鄰域擬陣。對，有

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

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

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

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

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

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

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

如果關(guān)系粗糙集的上近似包含由這個關(guān)系粗糙集誘導(dǎo)出的鄰域擬陣的閉包，那么這個關(guān)系一定是自反關(guā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)出一個關(guān)系。

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

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

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

事實上，()是論域上的一個等價關(guān)系。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

本文從關(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] 史忠植. 知識發(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。

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

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

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