集族等價與基于粒的下近似算子研究

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

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

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

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

1 集族約簡

下面來分析一個例子。

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

先對二元關系R1進行分析，令稱為元素x的后繼鄰域，由此定義得，，，其他元素的后繼鄰域為空集。非空后繼鄰域可以構成集族為：這就是二元關系R1誘導的集族。

同理，二元關系R2誘導的集族。

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

再看二元關系R3，誘導的集族。與R1、R2誘導的集族并不相同，卻也定義了相同的下近似運算。下面的分析將回答該問題。

由此可見，集族中的元素可以分成既約元和可約元兩類。

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

證明

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

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

定理1和定理2實際上還保證了集族的約簡是唯一的。

2 集族約簡的算法

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

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

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

將步驟1)、2)的結果并起來，就是該集族的約簡。

2.1 求集族的極小元

算法1 求集族的極小元。

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

3) i=i+1；

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

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

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

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

3 集族等價與下近似運算

4 結束語

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

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

[2]祝峰, 王飛躍. 關于覆蓋廣義粗集的一些基本結果[J]. 模式識別與人工智能, 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]李立峰, 俞偉. 概念格約簡與覆蓋約簡之間的關系[J]. 陜西理工學院學報: 自然科學版, 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ù)結構[J]. 工程數(shù)學學報, 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]屈小兵, 王學平. 完備格上并既約元的性質(zhì)[J]. 模糊系統(tǒng)與數(shù)學, 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.