基于决策表的保边界域不变及保负域不变约简

赵思雨，魏玲



基于决策表的保边界域不变及保负域不变约简

赵思雨，魏玲*

（西北大学数学学院，陕西省西安市邮编：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)