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

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

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

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

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

1 集族約簡

下面來分析一個例子。

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

先對二元關(guān)系R1進(jìn)行分析，令稱為元素x的后繼鄰域，由此定義得，，，其他元素的后繼鄰域為空集。非空后繼鄰域可以構(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)算。下面的分析將回答該問題。

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

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

證明

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

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

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

2 集族約簡的算法

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

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

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

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

2.1 求集族的極小元

算法1 求集族的極小元。

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

3) i=i+1；

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

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

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

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

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

4 結(jié)束語

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

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

[2]祝峰, 王飛躍. 關(guān)于覆蓋廣義粗集的一些基本結(jié)果[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]李立峰, 俞偉. 概念格約簡與覆蓋約簡之間的關(guān)系[J]. 陜西理工學(xué)院學(xué)報: 自然科學(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é)報, 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.