基于決策表的保邊界域不變及保負域不變約簡

趙思雨，魏玲

?

基于決策表的保邊界域不變及保負域不變約簡

趙思雨，魏玲*

（西北大學數學學院，陜西省西安市郵編：710127）

屬性約簡是粗糙集理論的重要研究方向之一。本文針對決策表, 從三支決策的角度提出了保持負域不變的約簡及保持邊界域不變的約簡, 并研究保持負域不變的約簡、保持邊界域不變的約簡與基于粗糙集理論代數角度的約簡之間的關系。

決策表；屬性約簡；邊界域；負域

引言

粗糙集理論作為一種數據分析處理理論，由波蘭科學家Pawlak于1982年提出，在數據的決策與分析、模式識別、機器學習與知識發現等方面有重要的應用[1-3]。在經典的粗糙集理論中，集合用上、下近似來表示，并由此處理一些不確定、不精確以及模糊的信息。

屬性約簡是粗糙集理論的重要研究方向之一[4-11]。特別是在決策表中，由Yao提出的三支決策對決策的獲取扮演著重要的角色[12-13]。三支即正域、負域及邊界域，其中正域表示確定執行接受指令的元素，負域表示確定執行拒絕指令的元素，邊界域表示不確定分類的元素。在此基礎上，Wang等人利用正域的概念定義了基于粗糙集理論代數角度的約簡[14]。

受Wang等人利用保持正域不變提出基于粗糙集理論代數角度的約簡的啟發，本文也從三支決策理論的角度來考慮基于負域及邊界域不變的約簡問題。負域中的元素是執行拒絕指令的元素，保持負域不變即從保守、悲觀的角度出發，保持不需要的元素不再增加。而邊界域中的元素具有不確定性，在實際應用中需要再次加以判斷。如在機器學習中研究分類問題時，設正域及負域分別代表0，1兩類，則邊界域中的元素是需要進行分類的對象。若能保持邊界域不變甚至減小邊界域，將對保持程序運行時間的穩定性，甚至降低算法的時間復雜度有重要的意義。又如在尋找決策規則時，邊界域中的元素也是尋找重點。因此，保持負域不變及保持邊界域不變都有著重要的意義。

本文提出保持負域不變的約簡及保持邊界域不變的約簡，進一步研究保持負域不變的約簡、保持邊界域不變的約簡與基于粗糙集理論代數角度的約簡之間的關系。

1 基礎知識

本節給出決策表中上、下近似及基于粗糙集理論代數角度的約簡的定義。

定義1[14]：稱四元組為決策表，其中是有限的對象集合，是有限的條件屬性集合，是有限的決策屬性集合，V是屬性的值域且，是一個信息函數，它把每一個對象映射到屬性空間。記，，則是關于條件屬性集的等價類，是關于決策屬性集的等價類。

定義2[14]：設是決策表，對于，,關于的上、下近似分別定義為：

(2)

定義3[14]：設是決策表，關于的正域定義為：

定義4[14]：設是決策表，對于，若且對任意的，，則稱是關于基于粗糙集理論代數角度的約簡。

2 保持邊界域不變的約簡及保持負域不變的約簡

考慮到三支決策理論中邊界域及負域的重要性，本節提出決策表中邊界域及負域的定義，并相應的定義兩種新的約簡：保持邊界域不變的約簡及保持負域不變的約簡。

表1 例1中的決策表

3 與基于粗糙集理論代數角度的約簡的關系

本節首先給出保持邊界域不變的約簡及保持負域不變的約簡的存在性定理；其次研究保持邊界域不變的約簡、保持負域不變的約簡與基于粗糙集理論代數角度的約簡之間的關系。

類似定理1的證明，可得保持負域不變的約簡的存在性定理。

下面給出保持邊界域不變的約簡、保持負域不變的約簡與基于粗糙集理論代數角度的約簡之間的關系。為了得到保持邊界域不變的約簡與基于粗糙集理論代數角度的約簡之間的關系，先給出引理1。

注: 針對等價類，引理1成立，而對于一般集合，該結論不一定成立。

而保持負域不變的約簡與保持邊界域不變的約簡的關系卻沒有這么直接與緊密。

例4 由例1及例2知保持邊界域不變的約簡是{}，保持負域不變的約簡是{,}與{,}。一方面，保持負域不變的約簡是{,}與{,}，而由例1知BND() = {x,x,x,x,x,x,x,x,x}，{a, b}() = {x,x,x,x,x,x,x,x,x}，{b, c}() = {x,x,x,x,x,x,x,x,x,x,x}。顯然,，即{,}是保持邊界域不變的協調集，{,}不是保持邊界域不變的協調集。另一方面，保持邊界域不變的約簡是{}，而由例2知,。顯然，即{}不是保持負域不變的協調集。

由定理3及保持負域不變的約簡與保持邊界域不變的約簡的關系易得，保持負域不變的約簡與基于粗糙集理論代數角度的約簡之間的關系亦不確定。

由此，得到保持邊界域不變的約簡、保持負域不變的約簡與基于粗糙集理論代數角度的約簡之間的關系，如圖1所示。

圖1 約簡之間的關系

4 結束語

本文從粗糙集理論負域及邊界域的定義出發，在決策表中分別提出了保持負域不變的約簡及保持邊界域不變的約簡，并將保持邊界域不變的約簡、保持負域不變的約簡及基于粗糙集理論代數角度的約簡進行比較，給出三者之間的關系。

針對本文給出的保持邊界域不變的約簡、保持負域不變的約簡，之后還可以研究這兩種約簡的計算方法，例如通過辨識矩陣的方法進行研究。

[1] Pawlak Z.. Rough Set[J]. International Journal of Computer and Information Sciences, 1982, 11: 341-356.

[2] Pawlak Z.. Theoretical Aspects of Reasoning about Data[M]. Boston: Kluwer Academic Publishers, 1991.

[3] Pawlak Z., Skowron A.. Rudiments of Rough Sets[J]. Information Science, 2007, 177: 3-27.

[4] 張文修, 吳偉志, 梁吉業, 李德玉. 粗糙集理論與方法[M]. 北京: 科學出版社, 2001.

[5] 王玨, 王任, 苗奪謙等. 基于Rough set 理論的“數據濃縮”[J]. 計算機學報, 1998, 21(5): 393-400.

[6] 王國胤. Rough集理論與知識獲取[M]. 西安: 西安交通大學出版社, 2001.

[7] 魏玲. 粗糙集與概念格約簡理論與方法[D]. 西安: 西安交通大學, 2005.

[8] WEI L, LI H R, ZHANG W X. Knowledge Reduction Based on the Equivalence Relations Defined on Attribute Set and Its Power Set[J]. Information Sciences, 2007, 177(15): 3178-3185.

[9] Ren R S, Wei L. The attribute reductions of three-way concept lattices[J]. Knowledge-Based Systems, 2016, 99: 92-102.

[10] 譚安輝, 李進金, 陳錦坤, 林國平. 圖支配集問題的粗糙集屬性約簡方法[J]. 模式識別與人工智能, 2015, 28(6): 507-512.

[11] 錢進, 呂萍, 岳曉冬. 決策粗糙集屬性約簡算法與屬性核研究[J]. 計算機科學與探索, 2014, 8(3): 345-351.

[12] Yao Y Y. An outline of a theory of three-way decisions[C]. //Proc of RSCTC. Heidelberg: Springer, 2012: 1-17.

[13] Yao Y Y. Three-way decisions with probabilistic rough sets[J]. Information Sciences, 2010, 180: 341-353.

The Attribute Reduction Preserving the Boundary/Negative Based on a Decision Table

ZHAO Siyu, WEI Ling

（School of Mathematics, Northwest University, Xi’an Shanxi 710127,China)

Attribute reduction is one of the core issues in rough set theory. On the basis of a decision table, this paper firstly defines two attribute reductions which can preserve the boundary region and the negative region from the viewpoint of three-way decision respectively. Then, we compare these two attribute reductions with attribute reduction from the algebra viewpoint of rough set theory, and present the relations among them.

decision table; attribute reduction; boundary region; negative region

1672-9129(2016)01-00028-04

TP301.6，O29

A

016-05-24;

2016-06-21。

國家自然科學基金項目(11371014，11071281)。

趙思雨(1992-): 女，陜西延安人，碩士生，主要研究方向為形式概念分析、粗糙集理論；魏玲(1972-)，女，陜西西安人，教授，博士生導師，主要研究方向為形式概念分析、粗糙集理論、概率論等。

(*通信作者電子郵箱： wl@nwu.edu.cn)