不完備貝葉斯決策信息系統(tǒng)的屬性約簡

韓 楠, 莫智文, 舒 暢

(四川師范大學 數(shù)學與軟件科學學院, 四川 成都 610066)

不完備貝葉斯決策信息系統(tǒng)的屬性約簡

韓 楠, 莫智文*, 舒 暢

(四川師范大學 數(shù)學與軟件科學學院, 四川 成都 610066)

在不完備貝葉斯決策信息系統(tǒng)中,改進全局增益函數(shù),結(jié)合二進制分辨矩陣編碼方法提出一種新的不完備貝葉斯決策信息系統(tǒng)啟發(fā)式屬性約簡算法,并將其應用于系統(tǒng)的故障狀況診斷研究中,該方法提高了約簡的效率.

不完備貝葉斯決策信息系統(tǒng); 二進制分辨矩陣; 全局增益函數(shù); 屬性約簡

0 前言

經(jīng)典粗糙集是處理不確定和不精確問題的有效工具[1].由于經(jīng)典粗糙集以等價關系為基礎,只適用于完備信息系統(tǒng).對于不完備信息系統(tǒng)[2-3],則不再適用.目前對不完備信息系統(tǒng)的處理方式有2種:1)將不完備信息系統(tǒng)通過某種方法轉(zhuǎn)化為完備信息系統(tǒng);2)將經(jīng)典粗糙集進行拓展.目前常見的擴展模型有變精度、容差、限制容差、優(yōu)勢、模糊等粗糙集模型.經(jīng)典粗糙集只考慮屬性值之間的可區(qū)分關系,未考慮到偏好關系,因此并不能很好地在決策過程中表達原有的偏好信息.文獻[4-5]研究了優(yōu)勢關系下決策信息系統(tǒng),文獻[6]提出了可變精度粗糙集模型,在經(jīng)典粗糙集的基礎上引進閾值β,允許一定程度上錯誤分類的存在,但在實際運用中變精度粗糙集也有其局限性.文獻[7]結(jié)合貝葉斯推理提出貝葉斯粗糙集模型,貝葉斯粗糙集是一種修正的變精度粗糙集模型,將變精度粗糙集中精度參數(shù)用先驗概率來替代,從而避免了變精度粗糙集中參數(shù)對約簡過程帶來的影響,同時貝葉斯理論與統(tǒng)計決策相結(jié)合形成的貝葉斯決策理論,在醫(yī)療和管理中起到了重要作用,因此本文對不完備貝葉斯決策信息系統(tǒng)進行屬性約簡,在限制容差關系分類模型的基礎上,利用貝葉斯粗糙集模型,通過引入全局增益函數(shù)和二進制分辨矩陣,給出了不完備貝葉斯決策信息系統(tǒng)的啟發(fā)式屬性約簡算法.

1 預備知識

1.1 不完備貝葉斯決策信息系統(tǒng)

定義 1.1[8]稱一個四元組(U,A,V,f)為信息系統(tǒng),其中U為有限非空對象集;A為有限非空屬性集;V為屬性值值域;f為對象屬性值映射,即U={x1,x2,...,xn},A={a1,a2,...,ap},V=∪a∈AVa,Va為屬性a的值域,f:U×A→V,且f(x,a)∈Va.

如果至少有一個屬性b∈A使得Vb含有空值,用“*”表示空值,則稱S是不完備信息系統(tǒng),否則稱為完備信息系統(tǒng).A=C∪D,C∩D=?,C稱為條件屬性集,D稱為決策屬性集.V=∪Va,a∈A,Va是屬性a的值域;f表示U×A→V的信息函數(shù),為每個對象的每個屬性賦予一個信息值,即?a∈A,x∈U,f(x,a)∈Va,稱這樣具有條件屬性和決策屬性的信息系統(tǒng)為決策信息系統(tǒng).

定義 1.2[9]在信息系統(tǒng)S=(U,A,V,f)中,U為非空有限論域,A為有限非空屬性集,E為U上的等價關系,對于目標集X?U有:

貝葉斯正域為

|[x]E)>P(X)};

貝葉斯負域為

|[x]E)

貝葉斯邊界域為

|[x]E)=P(X)},

其中,P(X)=|X|/|U|,P(X|[x]E)=|X∩[x]E|/|[x]E|.

貝葉斯粗糙集是一種修正過的變精度粗糙集模型[10-11],用事件的先驗概率代替變精度粗糙集參數(shù),從而避免了變精度粗糙集中參數(shù)帶來的影響.貝葉斯正域定義為U/A中所有元素集的集合出現(xiàn)的條件下X發(fā)生的概率大于先驗概率,即貝葉斯正域中的任何事件都會增加事件X確定發(fā)生的程度.貝葉斯負域定義為U/A中所有元素集的集合出現(xiàn)的條件下X發(fā)生的概率小于先驗概率,即貝葉斯正域中的任何事件都會減少事件X確定發(fā)生的程度.貝葉斯邊界域定義為U/A中所有元素集的集合出現(xiàn)的條件下X發(fā)生的概率等于先驗概率,即貝葉斯正域中的任何事件不會影響事件X確定發(fā)生的程度.

為了描述分類的特征,文獻[9]中貝葉斯決策信息系統(tǒng)引入了置信增益函數(shù).

定義 1.3[9]在信息系統(tǒng)S中,對于E?C,U/D=[x]d={X1,X2...,Xp},則稱

...,p}-1

為E相對于決策屬性D的全局相對增益函數(shù),全局增益函數(shù)可以用來度量貝葉斯決策信息系統(tǒng)的屬性重要度.

1.2 限制容差關系模型

定義 1.4[12]設S=(U,C∪D,V,f)是一個不完備決策信息系統(tǒng),對于具有空值的屬性子集,記空值為“*”,B?U,定義U上的容差關系T(B)記為

T(B)={(x,y)∈U2:?a∈B,a(x)=

a(y)∨((a(x)=*∨a(y)=*)→

f(x,b)=f(y,b))}.

則可記TB(x)={y∈U:(x,y)∈T(B)}為x的限制容差類.

定義 1.5[12]設S=(U,C∪D,V,f)是一個不完備決策信息系統(tǒng),對于X?U,B?C,在容差關系T(B)下,X的下上近似集分別定義為

?X},

由表1可知:U/D=[x]d={X1,X2}={(x1,x2,x5,x6),(x3,x4,x7,x8)}.

按定義1.4將U中對象在屬性集C下進行分類可得

TC(x1)={x1,x4,x5},TC(x2)={x2,x4},

TC(x3)={x3,x7},TC(x4)={x1,x2,x4,x5},

TC(x5)={x1,x4,x5,x7},TC(x6)={x6},

TC(x7)={x3,x5,x7},TC(x8)={x8}.

2 約簡思想及算法

經(jīng)典的屬性約簡算法中分辨矩陣以條件屬性集合作為矩陣元素,其空間復雜度高,處理效率低,所以將其優(yōu)化為二進制的分辨矩陣[13-14].本文通過限制容差關系模型對不完備決策信息系統(tǒng)進行分類,利用二進制分辨矩陣對所有對象進行編碼組合,找出論域中各對象組合的行所在的屬性值為1的屬性集,從而提高了查找約簡集合的效率.根據(jù)二進制分辨矩陣找出的各行可能的約簡屬性集,利用新定義的全局增益函數(shù)來度量屬性重要度,給出不完備貝葉斯決策信息系統(tǒng)的啟發(fā)式屬性約簡算法.

定義 2.1 在不完備決策信息系統(tǒng)S=(U,C∪D,V,f)中,定義其二進制分辨矩陣為

M((i,j),c)=

在很多預測模型[15](如股票市場、醫(yī)療領域、系統(tǒng)故障等)中,其最終目的都是為了提高決策的確定性程度.而傳統(tǒng)的Slezak貝葉斯粗糙集模型中提出的全局增益函數(shù)則反映了相對于先驗概率確定性增加或者減小的程度,但未能反映通過決策得到所需要的論域中的對象集合,本文改進了傳統(tǒng)全局增益函數(shù),改進的全局增益函數(shù)可以通過決策屬性得到所需對象集合.

定義 2.3 設在不完備信息系統(tǒng)S中,對于?X?U,B?C,若B是信息系統(tǒng)S的約簡集,則必須滿足下列條件:

1)RC(X)=RB(X);

2) 不存在A?B,使得RC(X)=RA(X).

2.1 算法 輸入:不完備決策信息系統(tǒng)S=(U,C∪D,V,f),輸出:不完備貝葉斯粗糙集的R約簡.

1) 根據(jù)限制容差關系,計算U中全部對象的容差類中使用到的子域;

2) 根據(jù)不完備決策表S構(gòu)造二進制分辨矩陣M;

3) 刪除二進制分辨矩陣M中全為零的行;

4) 將i記為二進制分辨矩陣第i行,令i=i+1,初始化i=0,若第i行屬性值為1的條件屬性集合B滿足RC(X)=RB(X),則得出約簡集B,否則繼續(xù)下一行i=i+1,直到第i行屬性值為1的條件屬性集合B滿足RC(X)=RB(X),結(jié)束算法.

2.2 算法實例分析 表1為某系統(tǒng)的故障信息,其中U={x1,x2,x3,x4,x5,x6,x7,x8}表示被控制的對象,系統(tǒng)的故障狀況由3個傳感器進行信息反饋,表示為A={a1,a2,a3},傳感器會反饋3種信號,即值域為Vc={1,2,3},控制系統(tǒng)的故障d有2種狀態(tài),即{1,2},已知的歷史決策表如下所示,但因種種原因有部分信息缺失,缺失信息用*代替.根據(jù)決策,確定3個傳感器反饋信號的重要程度.

表 1 設備故障信息表

表 2 二進制分辨矩陣

步驟 1 根據(jù)定義1.2和1.4得到在條件屬性集下論域U中全部對象的限制容差類并計算目標事件Xi發(fā)生下,出現(xiàn)在限制容差類中對象的條件概率.

P([x1]C|X1)=2/4,P([x2]C|X1)=1/4,

P([x3]C|X1)=0,P([x4]C|X1)=3/4,

P([x5]C|X1)=2/4,P([x6]C|X1)=1/4,

P([x7]C|X1)=1/4,P([x8]C|X1)=0,

P([x1]C|X2)=1/4,P([x2]C|X2)=1/4,

P([x3]C|X2)=2/4,P([x4]C|X2)=1/4,

P([x5]C|X2)=2/4,P([x6]C|X2)=0,

P([x7]C|X2)=2/4,P([x8]C|X2)=1/4.

步驟 2 由不完備決策表1,構(gòu)造二進制分辨矩陣M,如表2所示,M為12×3階矩陣.表2中最后一列為各行對象組合中屬性值為1的集合.

步驟 3 計算屬性集C相對于D的全局相對增益函數(shù)RC(X),同時依據(jù)表2中二進制分辨矩陣得出的屬性值為1的集合計算相應屬性集合對應的全局相對增益函數(shù).

RC(X1)={[x]c|maxP([x]c|X1)}=

{x1,x2,x4,x5},

RC(X2)={[x]c|maxP([x]c|X2)}=

{x1,x3,x4,x5,x7},

則

RC(X)=∪iRC(Xi)={x1,x2,x3,x4,x5,x7}.

由二進制表2可得,論域中對象組合屬性值為1的集合為

(a1,a3),(a1),(a1,a2),(a3),(a2).

分別計算其限制容差類及全局相對增益函數(shù),結(jié)果如下:

Ta1,a2(x1)={x1,x2,x4,x5},

Ta1,a2(x2)={x1,x2,x4,x5},

Ta1,a2(x3)={x3,x5,x7},

Ta1,a2(x4)={x1,x2,x4,x5},

Ta1,a2(x5)={x1,x2,x3,x4,x5,x7},

Ta1,a2(x6)={x6},

Ta1,a2(x7)={x3,x5,x7},

Ta1,a2(x8)={x8};

P([x1]a1,a2|X1)=3/4,

P([x2]a1,a2|X1)=3/4,

P([x3]a1,a2|X1)=1/4,

P([x4]a1,a2|X1)=3/4,

P([x5]a1,a2|X1)=3/4,

P([x6]a1,a2|X1)=1/4,

P([x7]a1,a2|X1)=1/4,

P([x8]a1,a2|X1)=0,

P([x1]a1,a2|X2)=1/4,

P([x2]a1,a2|X2)=1/4,

P([x3]a1,a2|X2)=2/4,

P([x4]a1,a2|X2)=1/4,

P([x5]a1,a2|X2)=3/4,

P([x6]a1,a2|X2)=0,

P([x7]a1,a2|X2)=2/4,

P([x8]a1,a2|X2)=1/4;

Ra1,a2(X1)=

{[x]a1,a2|maxP([x]a1,a2|X1)}=

{x1,x2,x3,x4,x5,x7},

Ra1,a2(X2)=

{[x]a1,a2|maxP([x]a1,a2|X2)}=

{x1,x2,x3,x4,x5,x7},

則

Ra1,a2(X)=∪iR(Xi)=

{x1,x2,x3,x4,x5,x7}.

經(jīng)計算可得RC(X)=Ra1,a2(X).由定義2.3可知{a1,a2}為屬性集C的約簡集.所以相對于3個傳感器反饋的信號,{a1,a2}應重點考慮.

3 結(jié)論

本文在不完備決策信息系統(tǒng)的基礎上,利用限制容差關系和貝葉斯粗糙集決策理論相結(jié)合,引入二進制區(qū)分矩陣和改進的全局增益函數(shù),對不完備貝葉斯決策粗糙集進行屬性約簡,給出新的思路和方法,從而提高了不完備決策信息系統(tǒng)的約簡效率.

[1] 張文修,吳偉志,梁吉業(yè). 粗糙集理論與方法[M]. 北京:科學出版社,2001.

[2] 楊柳嬌,莫智文. 幾類不完備信息系統(tǒng)的屬性約簡[D]. 成都:四川師范大學,2014.

[3] 王國胤. Rough集理論在不完備信息系統(tǒng)中的擴充[J]. 計算機研究與發(fā)展,2002,39(10):1238-1243.

[4] 張輝. 優(yōu)勢關系下區(qū)間值決策信息系統(tǒng)一致性度量[J]. 計算機工程與設計,2013,34(12):4336-4339.

[5] 王斌,邵明文,王金鶴. 基于改進的優(yōu)勢關系下的不完備區(qū)間值信息系統(tǒng)評估模型[J]. 計算機科學,2014,41(2):253-258.

[6] 華偉,祁云嵩,王芳. 不完備目標信息系統(tǒng)中的可變精度粗糙集模型[J]. 江蘇科技大學學報,2009,23(6):531-534.

[7] DOMINIK S, WOJCIECH Z. The investigation of the Bayesian rough set model[J]. Inter J Approximate Reasoning,2005(40):81-91.

[8] WANG X. Incomplete decision-theoretic rough set model based on improved complete tolerance relation[C]//Computer Engineering and Networking. New York:Springer International Publishing, 2014:273-280.

[9] 蔡娜,張雪峰. 基于貝葉斯粗糙集模型的屬性約簡[J]. 計算機工程,2007,33(24):45-48.

[10] 陳可,張小強,徐選華. 基于改進貝葉斯粗糙集和證據(jù)理論的決策信息融合方法[J]. 計算機應用研究,2014,31(9):2625-2628.

[11] 韓敏,張俊杰,彭飛,等. 一種基于多決策類的貝葉斯粗糙集模型[J]. 控制與決策,2009,24(11):1615-1619.

[12] 郭嗣琮,徐麗,鄭愛紅. 限制容差關系的不完備可變粗糙集[J]. 遼寧工程技術(shù)大學學報,2015,33(7):988-991.

[13] 趙軍,陳宸. 一種基于二進制分辨矩陣的屬性約簡新算法[J]. 重慶郵電大學學報,2012,24(4):490-494.

[14] 陳宸,趙軍. 一種新的基于二進制分辨矩陣的屬性約簡方法[J]. 計算機應用與軟件,2013,30(9):123-127.

[15] 張本文. 基于貝葉斯粗糙集的大數(shù)據(jù)頻繁項挖掘技術(shù)[J]. 科技通報,2015,31(6):210-213.

2010 MSC：03F03

(編輯 鄭月蓉)

Attribute Reduction in Incomplete Bayesian Decision Information System

HAN Nan, MO Zhiwen, SHU Chang

(College of Mathematics and Software Science, Sichuan Normal University, Chengdu 610066, Sichuan)

In incomplete Bayesian decision information system, this paper improves the global gain function, and combines with the coding method of binary discernibility matrix. A new heuristic attribute reduction algorithm is proposed. The method is applied to the study of the system of the fault condition's diagnosis, and improves the efficiency of reduction.

incomplete Bayesian decision information system; binary resolution matrix; global gain function; attribute reduction

TP301.6

A

1001-8395(2016)06-0825-04

10.3969/j.issn.1001-8395.2016.06.008