胡霞，費(fèi)鵬，杜衛(wèi)鋒

粗集理論是一種處理不協(xié)調(diào)、不完備和不精確信息的數(shù)學(xué)工具[1]，自1982年波蘭數(shù)學(xué)家Pawlak首次提出以來(lái)，經(jīng)過(guò)30余年的研究與發(fā)展，在理論和應(yīng)用上均取得了長(zhǎng)足的進(jìn)步。

粗集理論的基礎(chǔ)之一是從近似空間誘導(dǎo)出一對(duì)近似算子——上近似算子和下近似算子。經(jīng)典的Pawlak粗集模型基于等價(jià)關(guān)系，這種嚴(yán)格的要求在一定程度上限制了粗集理論的應(yīng)用。為了推廣粗集模型，可以把等價(jià)關(guān)系放寬為一般二元關(guān)系，在此情況下，由一般二元關(guān)系決定的論域上的集簇不再“劃分”。因此，另一種推廣粗集模型的思路就是將原來(lái)由等價(jià)關(guān)系決定的“劃分”放寬為“覆蓋”，從而建立基于覆蓋的粗集理論。但不同于經(jīng)典粗集理論，基于覆蓋的粗集理論不存在唯一的定義上下近似算子的方法。

已有很多文獻(xiàn)對(duì)基于覆蓋的粗集理論開(kāi)展了卓有成效的研究[2-8]。姚一豫等[3]系統(tǒng)地研究了基于覆蓋的20對(duì)上下近似算子；Mauricio Restrepo等[4]通過(guò)某些算子的相等關(guān)系將上下近似算子縮減為16對(duì)，并提出了算子精細(xì)度的概念，給了16對(duì)近似算子的精細(xì)關(guān)系，并用哈斯圖進(jìn)行了描述。M. Restrepo等[5]則研究了基于覆蓋的具有對(duì)偶性的16對(duì)上下近似算子的拓?fù)湫再|(zhì)。在數(shù)據(jù)挖掘領(lǐng)域，去除冗余屬性，獲取屬性約簡(jiǎn)，從而簡(jiǎn)化知識(shí)的表示，提升數(shù)據(jù)處理效率是一個(gè)重要的研究課題。李立峰等[6]研究發(fā)現(xiàn)覆蓋粗糙集與形式背景之間存在一一對(duì)應(yīng)關(guān)系，并且證明了覆蓋粗糙集的交約簡(jiǎn)可化為概念格的屬性約簡(jiǎn)；C. Wang等[7]開(kāi)發(fā)了一種基于覆蓋粗糙集的屬性約簡(jiǎn)方法，這種啟發(fā)式方法可以比較高效地獲得近似最優(yōu)約簡(jiǎn)的屬性集；Yang Bin等[8]則將包含度的概念引入覆蓋粗糙集，探索了一種新的覆蓋近似空間的若干性質(zhì)。在覆蓋粗集理論中，我們有基于元素、基于粒和基于子系統(tǒng)的3類(lèi)定義上下近似的途徑，以往大多數(shù)的文獻(xiàn)往往從基于元素的角度出發(fā)進(jìn)行定義，本文則以后繼鄰域作為基本研究對(duì)象“?！?，并以此為出發(fā)點(diǎn)，借鑒格論中既約元、可約元等概念[9–10]，探討了(覆蓋)集族中的既約元、可約元、集族的約簡(jiǎn)及其算法，另外，研究了集族與其生成的下近似算子的關(guān)系，為下一步開(kāi)展基于粒的公理化方法的研究做一些初步的理論方面的準(zhǔn)備工作。

1 集族約簡(jiǎn)

下面來(lái)分析一個(gè)例子。

基于粒的廣義上下近似算子定義為后繼鄰域的廣義并，而并不考慮該后繼鄰域是哪一個(gè)元素的后繼鄰域。因此我們只需研究二元關(guān)系R誘導(dǎo)的集族，而勿需再去研究二元關(guān)系本身。此時(shí)，基于粒的廣義上下近似算子可等效為

先對(duì)二元關(guān)系R1進(jìn)行分析，令稱(chēng)為元素x的后繼鄰域，由此定義得，，，其他元素的后繼鄰域?yàn)榭占?。非空后繼鄰域可以構(gòu)成集族為：這就是二元關(guān)系R1誘導(dǎo)的集族。

同理，二元關(guān)系R2誘導(dǎo)的集族。

由此發(fā)現(xiàn)，R1和R2誘導(dǎo)了相同的集族，因此它們定義了相同的下近似運(yùn)算。

再看二元關(guān)系R3，誘導(dǎo)的集族。與R1、R2誘導(dǎo)的集族并不相同，卻也定義了相同的下近似運(yùn)算。下面的分析將回答該問(wèn)題。

由此可見(jiàn)，集族中的元素可以分成既約元和可約元兩類(lèi)。

由命題(1)、(2)得證。

證明

由命題(1)、(2)得證。

由定理1和定理2可以得出，在一個(gè)集族中刪除其中的一個(gè)可約元，并不會(huì)改變其余元素是既約元還是可約元的性態(tài)。由此，我們可以逐個(gè)刪除集族中的所有可約元，只剩下既約元。

定理1和定理2實(shí)際上還保證了集族的約簡(jiǎn)是唯一的。

2 集族約簡(jiǎn)的算法

根據(jù)上節(jié)的結(jié)論，我們可以給出求一個(gè)集族約簡(jiǎn)的算法，該算法分為如下兩大步驟：

1) 求集族的極小元(極小元必定是既約元)；

2) 由極小元求集族的非極小既約元。

將步驟1)、2)的結(jié)果并起來(lái)，就是該集族的約簡(jiǎn)。

2.1 求集族的極小元

算法1 求集族的極小元。

2) 基數(shù)最小的元素一定是極小元，設(shè)其基數(shù)為i，將其從集族中移除并加入極小元集合；

3) i=i+1；

2.2 由極小元再求集族的非極小既約元

算法2 求集族的非極小既約元。

2.3 根據(jù)求集族約簡(jiǎn)的算法，先求集族的極小元

2.4 根據(jù)算法2由極小元再求集族的非極小既約元

3 集族等價(jià)與下近似運(yùn)算

4 結(jié)束語(yǔ)

本文從集族約簡(jiǎn)出發(fā)，探討了關(guān)于集族的若干性質(zhì)，得出了兩個(gè)集族等價(jià)是兩個(gè)集族生成相同的下近似運(yùn)算的充要條件這一結(jié)論，為下一步開(kāi)展基于粒的公理化方法的研究做了一些初步的理論方面的準(zhǔn)備工作。本文借鑒格論中的概念來(lái)研究粗集，為研究粗集理論提供了一種新的思路。下一步的工作將把格論與粗集理論作更深入的結(jié)合，把格論中的一些方法和結(jié)論引入粗集理論，試圖發(fā)現(xiàn)更多有趣的結(jié)果。另外，在此基礎(chǔ)上將開(kāi)展基于粒的粗集公理化方法的研究。

[1]張文修, 梁怡, 吳偉志. 信息系統(tǒng)與知識(shí)發(fā)現(xiàn)[M]. 北京: 科學(xué)出版社, 2003.

[2]祝峰, 王飛躍. 關(guān)于覆蓋廣義粗集的一些基本結(jié)果[J]. 模式識(shí)別與人工智能, 2002, 15(1): 6–13.ZHU Feng, WANG Feiyue. Some results on covering generalized rough sets[J]. Pattern recognition and artificial intelligence, 2002, 15(1): 6–13.

[3]YAO Yiyu, YAO Bingxue. Covering based rough set approximations[J]. Information sciences, 2012, 200: 91–107.

[4]RESTREPO M, CORNELIS C, GóMEZ J. Partial order relation for approximation operators in covering based rough sets[J]. Information sciences, 2014, 284: 44–59.

[5]RESTREPO M, GóMEZ J. Topological properties for approximation operators in covering based rough sets[C]//Proceeding of the 15th International Conference on Rough Sets,Fuzzy Sets, Data Mining, and Granular Computing. Tianjin,China, 2015: 112–123.

[6]李立峰, 俞偉. 概念格約簡(jiǎn)與覆蓋約簡(jiǎn)之間的關(guān)系[J]. 陜西理工學(xué)院學(xué)報(bào): 自然科學(xué)版, 2014, 30(3): 37–40.LI Lifeng, YU Wei. Relationships of reduction between concept lattice and covering[J]. Journal of Shaanxi university of technology: natural science edition, 2014, 30(3):37–40.

[7]WANG Changzhong, HE Qiang, CHEN Degang, et al. A novel method for attribute reduction of covering decision systems[J]. Information sciences, 2014, 254: 181–196.

[8]YANG Bin, ZHU W. A new type of covering-based rough sets[C]//Proceedings of the 9th International Conference on Rough Sets and Knowledge Technology. Shanghai, China,2014: 489–499.

[9]彭育威. 完全分配格的并一既約元的性質(zhì)及分子格的代數(shù)結(jié)構(gòu)[J]. 工程數(shù)學(xué)學(xué)報(bào), 1985, 2(2): 113–117.PENG Yuwei. Charaterization of a joiet lrreducible eiement of compietiy distributive lattice and agebric structure of a molecular lattice[J]. Chinese journal of engineering mathematics, 1985, 2(2): 113–117.

[10]屈小兵, 王學(xué)平. 完備格上并既約元的性質(zhì)[J]. 模糊系統(tǒng)與數(shù)學(xué), 2004, 18(S1): 176–179.QU Xiaobing, WANG Xueping. Some properties of joinirreducible elements in complete lattice[J]. Fuzzy systems and mathematics, 2004, 18(S1): 176–179.