不完备贝叶斯决策信息系统的属性约简

韩 楠, 莫智文, 舒 畅

(四川师范大学 数学与软件科学学院, 四川 成都 610066)

不完备贝叶斯决策信息系统的属性约简

韩 楠, 莫智文*, 舒 畅

(四川师范大学 数学与软件科学学院, 四川 成都 610066)

在不完备贝叶斯决策信息系统中,改进全局增益函数,结合二进制分辨矩阵编码方法提出一种新的不完备贝叶斯决策信息系统启发式属性约简算法,并将其应用于系统的故障状况诊断研究中,该方法提高了约简的效率.

不完备贝叶斯决策信息系统; 二进制分辨矩阵; 全局增益函数; 属性约简

0 前言

经典粗糙集是处理不确定和不精确问题的有效工具[1].由于经典粗糙集以等价关系为基础,只适用于完备信息系统.对于不完备信息系统[2-3],则不再适用.目前对不完备信息系统的处理方式有2种:1)将不完备信息系统通过某种方法转化为完备信息系统;2)将经典粗糙集进行拓展.目前常见的扩展模型有变精度、容差、限制容差、优势、模糊等粗糙集模型.经典粗糙集只考虑属性值之间的可区分关系,未考虑到偏好关系,因此并不能很好地在决策过程中表达原有的偏好信息.文献[4-5]研究了优势关系下决策信息系统,文献[6]提出了可变精度粗糙集模型,在经典粗糙集的基础上引进阈值β,允许一定程度上错误分类的存在,但在实际运用中变精度粗糙集也有其局限性.文献[7]结合贝叶斯推理提出贝叶斯粗糙集模型,贝叶斯粗糙集是一种修正的变精度粗糙集模型,将变精度粗糙集中精度参数用先验概率来替代,从而避免了变精度粗糙集中参数对约简过程带来的影响,同时贝叶斯理论与统计决策相结合形成的贝叶斯决策理论,在医疗和管理中起到了重要作用,因此本文对不完备贝叶斯决策信息系统进行属性约简,在限制容差关系分类模型的基础上,利用贝叶斯粗糙集模型,通过引入全局增益函数和二进制分辨矩阵,给出了不完备贝叶斯决策信息系统的启发式属性约简算法.

1 预备知识

1.1 不完备贝叶斯决策信息系统

定义 1.1[8]称一个四元组(U,A,V,f)为信息系统,其中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是不完备信息系统,否则称为完备信息系统.A=C∪D,C∩D=∅,C称为条件属性集,D称为决策属性集.V=∪Va,a∈A,Va是属性a的值域;f表示U×A→V的信息函数,为每个对象的每个属性赋予一个信息值,即∀a∈A,x∈U,f(x,a)∈Va,称这样具有条件属性和决策属性的信息系统为决策信息系统.

定义 1.2[9]在信息系统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],用事件的先验概率代替变精度粗糙集参数,从而避免了变精度粗糙集中参数带来的影响.贝叶斯正域定义为U/A中所有元素集的集合出现的条件下X发生的概率大于先验概率,即贝叶斯正域中的任何事件都会增加事件X确定发生的程度.贝叶斯负域定义为U/A中所有元素集的集合出现的条件下X发生的概率小于先验概率,即贝叶斯正域中的任何事件都会减少事件X确定发生的程度.贝叶斯边界域定义为U/A中所有元素集的集合出现的条件下X发生的概率等于先验概率,即贝叶斯正域中的任何事件不会影响事件X确定发生的程度.

为了描述分类的特征,文献[9]中贝叶斯决策信息系统引入了置信增益函数.

定义 1.3[9]在信息系统S中,对于E⊆C,U/D=[x]d={X1,X2...,Xp},则称

...,p}-1

为E相对于决策属性D的全局相对增益函数,全局增益函数可以用来度量贝叶斯决策信息系统的属性重要度.

1.2 限制容差关系模型

定义 1.4[12]设S=(U,C∪D,V,f)是一个不完备决策信息系统,对于具有空值的属性子集,记空值为“*”,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)是一个不完备决策信息系统,对于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 约简思想及算法

经典的属性约简算法中分辨矩阵以条件属性集合作为矩阵元素,其空间复杂度高,处理效率低,所以将其优化为二进制的分辨矩阵[13-14].本文通过限制容差关系模型对不完备决策信息系统进行分类,利用二进制分辨矩阵对所有对象进行编码组合,找出论域中各对象组合的行所在的属性值为1的属性集,从而提高了查找约简集合的效率.根据二进制分辨矩阵找出的各行可能的约简属性集,利用新定义的全局增益函数来度量属性重要度,给出不完备贝叶斯决策信息系统的启发式属性约简算法.

定义 2.1 在不完备决策信息系统S=(U,C∪D,V,f)中,定义其二进制分辨矩阵为

M((i,j),c)=

在很多预测模型[15](如股票市场、医疗领域、系统故障等)中,其最终目的都是为了提高决策的确定性程度.而传统的Slezak贝叶斯粗糙集模型中提出的全局增益函数则反映了相对于先验概率确定性增加或者减小的程度,但未能反映通过决策得到所需要的论域中的对象集合,本文改进了传统全局增益函数,改进的全局增益函数可以通过决策属性得到所需对象集合.

定义 2.3 设在不完备信息系统S中,对于∀X⊆U,B⊆C,若B是信息系统S的约简集,则必须满足下列条件:

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

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

2.1 算法 输入:不完备决策信息系统S=(U,C∪D,V,f),输出:不完备贝叶斯粗糙集的R约简.

1) 根据限制容差关系,计算U中全部对象的容差类中使用到的子域;

2) 根据不完备决策表S构造二进制分辨矩阵M;

3) 删除二进制分辨矩阵M中全为零的行;

4) 将i记为二进制分辨矩阵第i行,令i=i+1,初始化i=0,若第i行属性值为1的条件属性集合B满足RC(X)=RB(X),则得出约简集B,否则继续下一行i=i+1,直到第i行属性值为1的条件属性集合B满足RC(X)=RB(X),结束算法.

2.2 算法实例分析 表1为某系统的故障信息,其中U={x1,x2,x3,x4,x5,x6,x7,x8}表示被控制的对象,系统的故障状况由3个传感器进行信息反馈,表示为A={a1,a2,a3},传感器会反馈3种信号,即值域为Vc={1,2,3},控制系统的故障d有2种状态,即{1,2},已知的历史决策表如下所示,但因种种原因有部分信息缺失,缺失信息用*代替.根据决策,确定3个传感器反馈信号的重要程度.

表 1 设备故障信息表

表 2 二进制分辨矩阵

步骤 1 根据定义1.2和1.4得到在条件属性集下论域U中全部对象的限制容差类并计算目标事件Xi发生下,出现在限制容差类中对象的条件概率.

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,构造二进制分辨矩阵M,如表2所示,M为12×3阶矩阵.表2中最后一列为各行对象组合中属性值为1的集合.

步骤 3 计算属性集C相对于D的全局相对增益函数RC(X),同时依据表2中二进制分辨矩阵得出的属性值为1的集合计算相应属性集合对应的全局相对增益函数.

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).

分别计算其限制容差类及全局相对增益函数,结果如下:

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}.

经计算可得RC(X)=Ra1,a2(X).由定义2.3可知{a1,a2}为属性集C的约简集.所以相对于3个传感器反馈的信号,{a1,a2}应重点考虑.

3 结论

本文在不完备决策信息系统的基础上,利用限制容差关系和贝叶斯粗糙集决策理论相结合,引入二进制区分矩阵和改进的全局增益函数,对不完备贝叶斯决策粗糙集进行属性约简,给出新的思路和方法,从而提高了不完备决策信息系统的约简效率.

[1] 张文修,吴伟志,梁吉业. 粗糙集理论与方法[M]. 北京:科学出版社,2001.

[2] 杨柳娇,莫智文. 几类不完备信息系统的属性约简[D]. 成都:四川师范大学,2014.

[3] 王国胤. Rough集理论在不完备信息系统中的扩充[J]. 计算机研究与发展,2002,39(10):1238-1243.

[4] 张辉. 优势关系下区间值决策信息系统一致性度量[J]. 计算机工程与设计,2013,34(12):4336-4339.

[5] 王斌,邵明文,王金鹤. 基于改进的优势关系下的不完备区间值信息系统评估模型[J]. 计算机科学,2014,41(2):253-258.

[6] 华伟,祁云嵩,王芳. 不完备目标信息系统中的可变精度粗糙集模型[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]. 计算机应用研究,2014,31(9):2625-2628.

[11] 韩敏,张俊杰,彭飞,等. 一种基于多决策类的贝叶斯粗糙集模型[J]. 控制与决策,2009,24(11):1615-1619.

[12] 郭嗣琮,徐丽,郑爱红. 限制容差关系的不完备可变粗糙集[J]. 辽宁工程技术大学学报,2015,33(7):988-991.

[13] 赵军,陈宸. 一种基于二进制分辨矩阵的属性约简新算法[J]. 重庆邮电大学学报,2012,24(4):490-494.

[14] 陈宸,赵军. 一种新的基于二进制分辨矩阵的属性约简方法[J]. 计算机应用与软件,2013,30(9):123-127.

[15] 张本文. 基于贝叶斯粗糙集的大数据频繁项挖掘技术[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