關系粗糙集的鄰域擬陣結構研究

劉艷芳，陳雪云

?

關系粗糙集的鄰域擬陣結構研究

劉艷芳*，陳雪云

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

本文在論域任一關系中，通過鄰域定義了一個集族，證明其滿足擬陣的獨立集公理，建立了鄰域擬陣。為了進一步了解鄰域擬陣，研究了其極小圈、秩函數和閉包算子。同時，給出了從擬陣誘導關系的一種形式，研究了關系的上近似算子和由其誘導的擬陣閉包算子之間的關系。更進一步的研究了從關系到擬陣再到新關系與原關系之間的關聯，尤其是，原關系通過鄰域可以等價表示新關系。

粒計算；關系粗糙集；上近似；鄰域；擬陣

引言

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

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

作為線性代數和圖論的數學理論的一種推廣，擬陣論[2]由Whitney在1935年提出的，并且組合優化、算法設計、信息編碼和密碼學等領域都有著廣泛且成功的應用。擬陣理論有著完備的公理體系，和其他理論相結合的研究也受到了很多學者的關注并取得了一定的成果。張少譜等[11]建立了基于自反、傳遞關系的粗糙集的擬陣結構，并用擬陣的方法為屬性約簡設計了一個算法；劉艷芳等[4]提出了基于序、傳遞關系的粗糙集的擬陣結構；為了更好的利用粗糙集與擬陣結合的理論成果；祝峰等[12]提出了粗糙擬陣，把粗糙集與擬陣融合成一體；Marek和Skowron[5]指出將粗糙集的各種推理與擬陣Greedy算法聯系在一起，便于開發的算法尋找各類屬性集中的最大約簡和最小約簡，從而促進粗糙集理論中的屬性約簡算法的進一步發展。

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

1 預備知識

本節主要介紹關系粗糙集和擬陣，并給出了一些基本的概念和性質。

1.1 關系粗糙集

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

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

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

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

（1）

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

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

命題 1[13]設是上的任一關系，。H滿足以下性質：

(1)； （3）

(2)； （4）

(3)（5）

1.2 擬陣

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

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

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

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

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

定義 4 設A是上的一個子集族。定義：

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

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

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

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

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

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

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

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

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

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

擬陣和閉包算子是一一對應的，因此，可以從閉包算子的角度來進行定義擬陣。

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

2 鄰域擬陣的性質

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

定義 9 設是上的任一關系。定義基于下的一個集族如下：

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

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

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

假設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)。假設對任意的2－1，都有1{}I()，則存在唯一的一個元素1－2使得S() =S()。因此，有|2－1||1－2|，即|2||1|，這和已知條件|1| < |2|相互矛盾。因此，假設不成立，所以存在一個元素2－1使得1{}I()。

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

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

為了能客觀了解鄰域擬陣的結構，下面給出了一具體的例子。

例 1設= {,,}，且= {(,), (,), (,), (,), (,), (,)}是上的關系。因為S() = {,},S() = {,},S() = {,}。由式（10）可知，鄰域擬陣()(,I())的獨立集集族I() = {, {}, {}, {}, {,}, {,}}。

在下面的命題，我們給出了鄰域與其誘導出的鄰域擬陣的相關集之間的關聯。

命題 4設是上的任一關系，且()(,I())是由誘導的鄰域擬陣。則有

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

極小的相關集就是擬陣的極小圈。根據上面的命題，很容易得到鄰域擬陣極小圈的表達式。

命題 5設是上的任一關系，且()(,I())是由誘導的鄰域擬陣。則有

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

由上面的命題可知，論域上任一關系誘導出的鄰域擬陣的每個極小圈的基數都是2。秩函數是擬陣中的一個量化工具。下面從量化的角度研究鄰域擬陣的秩函數。

命題 6設是上的任一關系，且()(,I())是由誘導的鄰域擬陣。對，有

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

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

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

命題 7設是上的一個關系，且()(,I())是由誘導的鄰域擬陣。對，有

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

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

表 1 上近似和下近似與關系粗糙集的鄰域擬陣

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

當關系是自反關系時，由這個關系誘導出的鄰域擬陣的閉包算子包含在基于這個自反關系的上近似算子內。

命題 8 設是上的任一關系，且()(,I())是由誘導的鄰域擬陣，。當是自反的，則有cl(R)()H()。

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

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

命題 9[13]設是上的任一關系，。是自反的當且僅當H()。

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

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

3 鄰域擬陣與擬陣的粗糙集的關系

為了深一層研究關系粗糙集的鄰域擬陣，本節引用了一種逆序構造：從擬陣誘導出一個關系。

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

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

我們稱()是由擬陣誘導的關系。

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

命題 11[2]設(, I)是一個擬陣，()是擬陣誘導出的關系。則()是上的等價關系。

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

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

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

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

命題 13 設(, I)是一個擬陣，()是擬陣的誘導的關系。對任意的，都有H(M)()cl()。

但一個擬陣誘導出的關系粗糙集的上近似不包含該擬陣的閉包。下面給出一具體的反例。

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

由一個擬陣誘導出的關系粗糙集的上近似和該擬陣的閉包在什么條件下相等呢？

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

本文中給出了兩種構造：從關系誘導出一個鄰域擬陣，從擬陣產生一個關系。因此，一個擬陣可以誘導出一個關系，這個關系緊接著可以誘導出一個相應的擬陣。類似地，一個關系可以誘導出一個擬陣，這個擬陣緊接著誘導出一個關系。那么原來的擬陣和誘導出的新擬陣以及原來的關系和誘導出的新關系之間有什么樣的聯系呢？

定理 2 設是上的一個關系，()是由關系誘導的鄰域擬陣，且(())是由擬陣()的誘導的粗糙集，則有

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

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

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

4 結語

本文從關系中鄰域概念的角度創建了關系粗糙集的鄰域擬陣，研究了其相關集、極小圈、秩函數和閉包算子等特性。為了更深層的了解鄰域擬陣，給出了從擬陣到關系的逆構造方法，并進一步研究了這兩種構造方法之間的關聯。

[1] 耿素云, 屈婉玲, 王捍貧. 離散數學教程[M]. 北京大學出版社, 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] 史忠植. 知識發現[M]. 清華大學出版社, 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。

國家自然科學基金面上項目（61379049），龍巖學院百名青年教師攀登項目（LQ2015031），龍巖學院協同創新項目（張凌）；大學生創新創業訓練計劃項目（S20141004）。

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

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