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

趙思雨，魏玲

?

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

趙思雨，魏玲*

（西北大學(xué)數(shù)學(xué)學(xué)院，陜西省西安市郵編：710127）

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

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

引言

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

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

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

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

1 基礎(chǔ)知識

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

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

定義2[14]：設(shè)是決策表，對于，,關(guān)于的上、下近似分別定義為：

(2)

定義3[14]：設(shè)是決策表，關(guān)于的正域定義為：

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

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

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

表1 例1中的決策表

3 與基于粗糙集理論代數(shù)角度的約簡的關(guān)系

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

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

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

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

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

例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}。顯然,，即{,}是保持邊界域不變的協(xié)調(diào)集，{,}不是保持邊界域不變的協(xié)調(diào)集。另一方面，保持邊界域不變的約簡是{}，而由例2知,。顯然，即{}不是保持負域不變的協(xié)調(diào)集。

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

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

圖1 約簡之間的關(guān)系

4 結(jié)束語

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

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

[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] 張文修, 吳偉志, 梁吉業(yè), 李德玉. 粗糙集理論與方法[M]. 北京: 科學(xué)出版社, 2001.

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

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

[7] 魏玲. 粗糙集與概念格約簡理論與方法[D]. 西安: 西安交通大學(xué), 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]. 計算機科學(xué)與探索, 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。

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

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

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