優(yōu)勢關(guān)系決策信息系統(tǒng)的屬性約簡

劉曉峰, 王麗麗

(1. 吉林省教育學(xué)院 綜合部, 長春 130022； 2. 渤海大學(xué) 數(shù)學(xué)系, 遼寧 錦州 121013)

0 引 言

粗糙集是一種處理不完全、 不精確性和不確定性數(shù)據(jù)的有效數(shù)學(xué)工具, 是由波蘭數(shù)學(xué)家Pawlak[1-3]于1982年提出的。近幾年來,它廣泛應(yīng)用于機(jī)器學(xué)習(xí)與知識發(fā)現(xiàn)、 數(shù)據(jù)挖掘和決策支持等方面[4-12]。屬性約簡是粗糙集理論的重要應(yīng)用之一。所謂屬性約簡, 就是在知識庫分類能力保持不變的情況下去除一些不相關(guān)的屬性。屬性約簡可以簡化信息系統(tǒng)的表達(dá)同時又能保證不丟失信息。

現(xiàn)實生活中有很多信息系統(tǒng)是基于優(yōu)勢關(guān)系的, 要想從這種復(fù)雜的基于優(yōu)勢關(guān)系下的決策信息系統(tǒng)中獲取簡潔的不確定性的命題, 必須對信息系統(tǒng)進(jìn)行知識約簡。因此, 很多研究者對優(yōu)勢關(guān)系下的信息系統(tǒng)的屬性約簡進(jìn)行了研究, 并取得了一定的研究成果。張文修等[11]給出了基于優(yōu)勢關(guān)系協(xié)調(diào)目標(biāo)信息系統(tǒng)上約簡的定義及其相應(yīng)的計算屬性約簡的辨識矩陣的方法。文獻(xiàn)[13]引入了協(xié)調(diào)近似空間的概念, 并把不協(xié)調(diào)目標(biāo)信息系統(tǒng)轉(zhuǎn)化成了一個協(xié)調(diào)的近似空間。文獻(xiàn)[14]在不協(xié)調(diào)目標(biāo)信息系統(tǒng)中引入分布和最大分布協(xié)調(diào)近似空間。文獻(xiàn)[15]引入了分布約簡和最大分布約簡的概念, 并得到了分布及最大分布約簡的判定定理以及辨識矩陣。文獻(xiàn)[16]基于證據(jù)理論討論了完備決策系統(tǒng)的知識約簡。為有效處理不一致決策的數(shù)據(jù), 筆者通過定義決策正域的概念, 從統(tǒng)一的觀點提出了基于優(yōu)勢關(guān)系的一般決策信息系統(tǒng)的屬性約簡方法, 并對屬性約簡的主要性質(zhì)進(jìn)行了分析。

1 粗糙集與基于優(yōu)勢關(guān)系的信息系統(tǒng)的屬性約簡的基本知識

基本理論知識[1,2]。

定義1 設(shè)U={x1,x2,…,xn}是非空有限論域,R?U×U是U上的二元等價關(guān)系, 也稱為不可區(qū)分關(guān)系, 則稱序?qū)?U,R)為Pawlak近似空間。對任意序?qū)?x,y)∈U×U, 若(x,y)∈R, 則稱x和y關(guān)于R是不可區(qū)分的； 否則, 稱x和y關(guān)于R是可區(qū)分的。

?X}=∪{[x]R: [x]R?X}

定義3 設(shè)U為有限論域,Rs:U→2U為集值函數(shù)。對于x∈U, 稱集Rs(x)={y∈U: (x,y)∈R}為x關(guān)于R的后繼鄰域。

定義4 設(shè)U是有限非空論域,R是U上的一個二元關(guān)系, 若R滿足自反性和傳遞性, 則稱R為U上的優(yōu)勢關(guān)系。

2 基于優(yōu)勢關(guān)系信息系統(tǒng)的屬性約簡

對于對象屬性取值是有序的情況, 用優(yōu)勢關(guān)系代替經(jīng)典的等價關(guān)系, 給出了優(yōu)勢關(guān)系信息系統(tǒng)的定義。

定義5 設(shè)U是有限非空論域,R′={R1,R2,…,Rn}是U上的一簇優(yōu)勢關(guān)系, 稱(U,R)為優(yōu)勢關(guān)系信息系統(tǒng), 其中R′稱為條件關(guān)系集。

性質(zhì)

證明略。

對任意的X?U, 定義X關(guān)于優(yōu)勢關(guān)系R′的下近似和上近似分別為

??}

定義6 對于優(yōu)勢關(guān)系信息系統(tǒng), 若P?R′, 且滿足：

1) IntP=IntR′;

則稱P是優(yōu)勢關(guān)系信息系統(tǒng)的約簡, 若優(yōu)勢關(guān)系信息系統(tǒng)的所有約簡交非空時, 則稱此非空集為優(yōu)勢關(guān)系信息系統(tǒng)的核, 記作Core(R′)。類似于等價關(guān)系的情形, 優(yōu)勢關(guān)系下的約簡一般也不是唯一的, 信息系統(tǒng)的所有約簡的集合記為Red(R′), 顯然Core(R′)=∩Red(R′)。

定義7 令Cij={Ri∈R′:xj?Rs(xi)}, 稱{Cij:i,j≤n}為優(yōu)勢關(guān)系信息系統(tǒng)(U,R′)的辨識矩陣。顯然Cij∩Cji=?(xi,xj∈U), 記C0={Cij:Cij≠?}。

定理1 設(shè)(U,R′)為優(yōu)勢關(guān)系信息系統(tǒng),P?R′, 下列命題等價：

1) IntP=IntR′;

2) 對?C∈C0,P∩C≠?;

3) 對?C?R,P∩C=?, 必有C?C0。

2)與3)顯然等價。

定理2 設(shè)(U,R′)為優(yōu)勢關(guān)系信息系統(tǒng),P是(U,R′)的約簡, 當(dāng)且僅當(dāng)滿足以下條件：

1) ?C∈C0,P∩C≠?;

2) ?Ri∈P, ?C∈C0, 使(P-{Ri})∩C=?。

證明 類似于定理1。

3 優(yōu)勢關(guān)系決策信息系統(tǒng)的屬性約簡

下面通過正域的定義, 從統(tǒng)一的觀點研究基于優(yōu)勢關(guān)系的決策信息系統(tǒng)的屬性約簡方法, 并對屬性約簡的主要性質(zhì)進(jìn)行分析。

在應(yīng)用中, 一個分類相對于另一個分類的關(guān)系非常重要, 下面給出優(yōu)勢關(guān)系決策信息系統(tǒng)的一些簡單性質(zhì)。

定理3 設(shè)(U,R′,D)為優(yōu)勢關(guān)系決策信息系統(tǒng)。若P?R, 則：

定理4 設(shè)(U,R′,D)為優(yōu)勢關(guān)系決策信息系統(tǒng)。若P?R′, 則PosR′(D)=PosP(D)??X?U/D,R′(X)=P(X)。

必要性顯然。

定義10 設(shè)(U,R′,D)為優(yōu)勢關(guān)系決策系統(tǒng),Ri∈R′, 稱Ri相對于D是R′中不必要的： 當(dāng)且僅當(dāng)PosR′(D)=Pos{R′-{Ri}}(D), 否則, 稱Ri相對于D是R′中必要的；R′中所有相對于D的必要元素組成的集合稱為R′相對于D的核, 記為CoreD(R′)。

定義12 設(shè)(U,R′,D)為優(yōu)勢關(guān)系決策信息系統(tǒng),U={x1,x2,…,xn},G為D關(guān)于R′的可辨識域, 稱n×n矩陣M(U,R′,D)為(U,R′,D)的辨識矩陣, 記為{Dij:i,j≤n}, 定義如下： 對?xi,xj∈U

記D0={Dij:Dij≠?}。

定理5 設(shè)(U,R′,D)為優(yōu)勢關(guān)系決策信息系統(tǒng), 則以下條件等價：

1) IntP?Rd;

2) 對?D∈D0,D∩P≠?;

3) 對?D?R′, 當(dāng)P∩D=?時, 必有D?D0。

證明 類似于定理1。

定理6 設(shè)(U,R′,D)為優(yōu)勢關(guān)系決策信息系統(tǒng),P是(U,R′,D)的約簡當(dāng)且僅當(dāng)它滿足以下條件：

1) ?D∈D0,D∩P≠?;

2) ?Ri∈P, ?D∈D0使(P-{Ri})∩D=?。

證明 由定理5和約簡的定義即得。

定義13 設(shè)(U,R′,D)是優(yōu)勢關(guān)系決策信息系統(tǒng),M(U,R′,D)={Dij:i,j≤n}是(U,R′,D)的辨識矩陣, 辨識函數(shù)為f(U,R′,D)=∧{∨Di j}(Di j≠?)。

例1 表1給出了決策信息系統(tǒng)。

表1 決策信息系統(tǒng)

令Ri={(xi,xj):a1(xi)≤a1(xj)},i=1,2,3。則R′是優(yōu)勢關(guān)系, 從而可得(U,R′,j5i0abt0b)是一個優(yōu)勢關(guān)系信息系統(tǒng), 其中U={x1,x2,x3,x4,x5,x6},R={R1,R2,R3}。

(U,R′,j5i0abt0b)的辨識矩陣為

所以f(U,R′,j5i0abt0b)=(R1∨R2∨R3)∧(R1∨R2)∧R3=R3∧(R1∨R2)=(R3∧R1)∨(R3∧R2), RedD(R′)={{R1,R3}, {R2,R3}}, CoreD(R′)={R3}。

在上例中, 當(dāng)P1={R2,R3}, ～P1={R1}?D0,P2={R1}時, ～P2={R2,R3}且{R2}?D0, {R3}?D0, {R2,R3}?D0, 所以P1和P2均是約簡。

4 結(jié) 語

在現(xiàn)實生活中有很多信息系統(tǒng)是基于優(yōu)勢關(guān)系的, 筆者分別研究了信息系統(tǒng)與決策信息系統(tǒng)兩種情況的屬性約簡方法, 給出了基于優(yōu)勢關(guān)系的辨識矩陣和辨識公式, 研究了屬性約簡的結(jié)構(gòu)和性質(zhì)。

參考文獻(xiàn)：

[1] PAWLAK Z. Rough Sets [J]. International Journal of Computer and Information Sciences, 1982, 11(5): 341-356.

[2]PAWLAK Z. Rough Sets: Theoretical Aspects of Reasoning about Data [M]. Dordrecht: Kluwer Academic Publishing, 1991.

[3]PAWLAK Z. SKOWRON A. Rudiments of Rough Sets [J]. Information Science, 2007, 177(1): 3-27.

[4]CHEN D G, WANG C Z, HU Q H. A New Approach to Attribute Reduction of Consistent and Inconsistent Covering Decision Systems with Covering Rough Sets [J]. Information Sciences, 2007, 177(17): 3500-3518.

[5]GRECO S, GRECO B, MATARAZZO R. Rough Approximation of a Preference Relation by Dominance Relations [J]. European Journal of Operational Research, 1999, 117(1): 63-83.

[6]HU Q, PEDRYCZ W, YU D. Selecting Discrete and Continuous Features Based on Neighborhood Decision Error Minimization [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, 2010, 40(1): 137-50.

[7]QIAN Y, LIANG J, PEDRYCZ W, et al. Positive Approximation: An Accelerator for Attribute Reduction in Rough Set Theory [J]. Artificial Intelligence, 2010, 174(9-10): 597-618.

[8]WANG C, WU C, HU Q. Communicating between Information Systems [J]. Information Sciences, 2008, 178(16): 3228-3239.

[9]WANG C, WU C, CHEN D. A Systematic Study on Attribute Reduction with Rough Sets Based on General Binary Relations [J]. Information Sciences, 2008, 178(9): 2237-2261.

[10]QIAN Y, DANG C, LIANG J, et al. Set-Valued Ordered Information Systems [J]. Information Sciences, 2009, 179(16): 2809-2832.

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

ZHANG Wen-xiu, LIANG Yi, WU Wei-zhi. Information Systems and Knowledge Discovery [M]. Beijing: Science Press, 2003.

[12]王長忠, 陳德剛. 基于粗糙集的知識獲取理論與方法 [M]. 哈爾濱： 哈爾濱工業(yè)大學(xué)出版社, 2010.

WANG Chang-zhong, CHEN De-gang. The Theory and Methods of Knowledge Acquisitions Based on Rough Sets [M]. Harbin: Harbin Institute of Technology Press, 2010.

[13]徐偉華, 張文修. 基于優(yōu)勢關(guān)系協(xié)調(diào)近似空間[J]. 計算機(jī)科學(xué), 2005, 32(9): 164-165.

XU Wei-hua, ZHANG Wen-xiu. Consistent Approximation Apace Based on Dominance Relation [J]. Computer Science, 2005, 32(9): 164-165.

[14]徐偉華, 張曉燕, 蘇雅娟, 等. 基于優(yōu)勢關(guān)系下協(xié)調(diào)近似空間(續(xù)) [J]. 計算機(jī)科學(xué), 2007, 325(3)： 148-150.

XU Wei-hua, ZHANG Xiao-yan, SU Ya-juan, et al. Consistent Approximation Apace Based on Dominance Relation (Ⅱ) [J]. Computer Science, 2007, 325(3): 148-150.

[15]徐偉華, 張文修. 基于優(yōu)勢關(guān)系下協(xié)調(diào)目標(biāo)信息系統(tǒng)的知識約簡 [J]. 計算機(jī)科學(xué), 2006, 33(2)： 182-184.

XU Wei-hua, ZHANG Wen-xiu. Knowledge Reduction in Inconsistent Information Systems Based on Dominance Relations [J]. Computer Science, 2006, 33(2): 182-184.

[16]WU Wei-zhi, ZHANG Mei, LI Huai-zu, et al. Knowledge Reduction in Random Information Systems via Dempster-Shafer Theory of Evidence [J]. Information Sciences, 2005, 174(3): 143-146.