趙思雨，魏玲

?

基于決策表的保邊界域不變及保負(fù)域不變約簡(jiǎn)

趙思雨，魏玲*

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

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

決策表；屬性約簡(jiǎn)；邊界域；負(fù)域

引言

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

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

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

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

1 基礎(chǔ)知識(shí)

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

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

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

(2)

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

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

2 保持邊界域不變的約簡(jiǎn)及保持負(fù)域不變的約簡(jiǎn)

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

表1 例1中的決策表

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

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

類(lèi)似定理1的證明，可得保持負(fù)域不變的約簡(jiǎn)的存在性定理。

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

針對(duì)本文給出的保持邊界域不變的約簡(jiǎn)、保持負(fù)域不變的約簡(jiǎn)，之后還可以研究這兩種約簡(jiǎn)的計(jì)算方法，例如通過(guò)辨識(shí)矩陣的方法進(jì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]. 計(jì)算機(jī)學(xué)報(bào), 1998, 21(5): 393-400.

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

[7] 魏玲. 粗糙集與概念格約簡(jiǎn)理論與方法[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ìn)金, 陳錦坤, 林國(guó)平. 圖支配集問(wèn)題的粗糙集屬性約簡(jiǎn)方法[J]. 模式識(shí)別與人工智能, 2015, 28(6): 507-512.

[11] 錢(qián)進(jìn), 呂萍, 岳曉冬. 決策粗糙集屬性約簡(jiǎn)算法與屬性核研究[J]. 計(jì)算機(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。

國(guó)家自然科學(xué)基金項(xiàng)目(11371014，11071281)。

趙思雨(1992-): 女，陜西延安人，碩士生，主要研究方向?yàn)樾问礁拍罘治?、粗糙集理論；魏?1972-)，女，陜西西安人，教授，博士生導(dǎo)師，主要研究方向?yàn)樾问礁拍罘治?、粗糙集理論、概率論等?/p>

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