基于不完备决策信息系统的知识约简算法

不完备贝叶斯决策信息系统的属性约简韩楠;舒畅;莫智文【摘要】在不完备贝叶斯决策信息系统中,改进全局增益函数,结合二进制分辨矩阵编码方法提出一种新的不完备贝叶斯决策信息系统启发式属性约简算法,并将其应用于系统的故障状况诊断研究中,该方法提高了约简的效率.%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.【期刊名称】《四川师范大学学报（自然科学版）》【年(卷),期】2016(039)006【总页数】4页(P825-828)【关键词】不完备贝叶斯决策信息系统;二进制分辨矩阵;全局增益函数;属性约简【作者】韩楠;舒畅;莫智文【作者单位】四川师范大学数学与软件科学学院, 四川成都 610066;四川师范大学数学与软件科学学院, 四川成都 610066;四川师范大学数学与软件科学学院, 四川成都 610066【正文语种】中文【中图分类】TP301.6经典粗糙集是处理不确定和不精确问题的有效工具[1].由于经典粗糙集以等价关系为基础,只适用于完备信息系统.对于不完备信息系统[2-3],则不再适用.目前对不完备信息系统的处理方式有2种:1)将不完备信息系统通过某种方法转化为完备信息系统;2)将经典粗糙集进行拓展.目前常见的扩展模型有变精度、容差、限制容差、优势、模糊等粗糙集模型.经典粗糙集只考虑属性值之间的可区分关系,未考虑到偏好关系,因此并不能很好地在决策过程中表达原有的偏好信息.文献[4-5]研究了优势关系下决策信息系统,文献[6]提出了可变精度粗糙集模型,在经典粗糙集的基础上引进阈值β,允许一定程度上错误分类的存在,但在实际运用中变精度粗糙集也有其局限性.文献[7]结合贝叶斯推理提出贝叶斯粗糙集模型,贝叶斯粗糙集是一种修正的变精度粗糙集模型,将变精度粗糙集中精度参数用先验概率来替代,从而避免了变精度粗糙集中参数对约简过程带来的影响,同时贝叶斯理论与统计决策相结合形成的贝叶斯决策理论,在医疗和管理中起到了重要作用,因此本文对不完备贝叶斯决策信息系统进行属性约简,在限制容差关系分类模型的基础上,利用贝叶斯粗糙集模型,通过引入全局增益函数和二进制分辨矩阵,给出了不完备贝叶斯决策信息系统的启发式属性约简算法.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)<P(X)};贝叶斯边界域为|[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)记为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(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}.经典的属性约简算法中分辨矩阵以条件属性集合作为矩阵元素,其空间复杂度高,处理效率低,所以将其优化为二进制的分辨矩阵[13-14].本文通过限制容差关系模型对不完备决策信息系统进行分类,利用二进制分辨矩阵对所有对象进行编码组合,找出论域中各对象组合的行所在的属性值为1的属性集,从而提高了查找约简集合的效率.根据二进制分辨矩阵找出的各行可能的约简属性集,利用新定义的全局增益函数来度量属性重要度,给出不完备贝叶斯决策信息系统的启发式属性约简算法.定义 2.1 在不完备决策信息系统S=(U,C∪D,V,f)中,定义其二进制分辨矩阵为在很多预测模型[15](如股票市场、医疗领域、系统故障等)中,其最终目的都是为了提高决策的确定性程度.而传统的Slezak贝叶斯粗糙集模型中提出的全局增益函数则反映了相对于先验概率确定性增加或者减小的程度,但未能反映通过决策得到所需要的论域中的对象集合,本文改进了传统全局增益函数,改进的全局增益函数可以通过决策属性得到所需对象集合.定义 2.2 设S=(U,C∪D,V,f)是一个不完备决策信息系统,对于∀B⊆C,U/D=[x]d={X1,X2,...,Xn},定义则RC(X)=∪iRC(Xi),称RC(X)为C相对于D 的全局相对增益函数.定义 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 根据定义1.2和1.4得到在条件属性集下论域U中全部对象的限制容差类并计算目标事件Xi发生下,出现在限制容差类中对象的条件概率.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的集合计算相应属性集合对应的全局相对增益函数. {x1,x2,x4,x5},RC(X2)={[x]c|max P([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(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|max P([x]a1,a2|X1)}= {x1,x2,x3,x4,x5,x7},Ra1,a2(X2)={[x]a1,a2|max P([x]a1,a2|X2)}= {x1,x2,x3,x4,x5,x7},则{x1,x2,x3,x4,x5,x7}.经计算可得RC(X)=Ra1,a2(X).由定义2.3可知{a1,a2}为属性集C的约简集.所以相对于3个传感器反馈的信号,{a1,a2}应重点考虑.本文在不完备决策信息系统的基础上,利用限制容差关系和贝叶斯粗糙集决策理论相结合,引入二进制区分矩阵和改进的全局增益函数,对不完备贝叶斯决策粗糙集进行属性约简,给出新的思路和方法,从而提高了不完备决策信息系统的约简效率.【相关文献】[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. NewYork: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。

信息量不完备决策表属性约简的一种新算法张清国;郑雪峰;张明德;于义科【摘要】目前,基于不完备决策表的属性约简研究较少.基于信息量的不完备决策表属性约简是一种新的属性约简.由于在该属性约简中,计算相容关系是最主要的计算,也比计算等价关系要难得多.基于信息量的不完备决策表的属性约简算法的时间复杂度一般为o(|C|~3|U|~2).为降低其时间复杂度,首先分析了老算法的不足,然后给出了一个效率较好的计算相容类的算法.最后设计了一个新的基于信息量的不完备决策表的属性约简算法,其时间复杂度为O(|C|~2|U|~2).【期刊名称】《计算机工程与应用》【年(卷),期】2010(046)002【总页数】4页(P19-21,33)【关键词】粗糙集;属性约简;不完备决策表;信息量;算法复杂度【作者】张清国;郑雪峰;张明德;于义科【作者单位】北京科技大学信息工程学院,北京,100083;北京科技大学信息工程学院,北京,100083;北京科技大学信息工程学院,北京,100083;北京科技大学信息工程学院,北京,100083【正文语种】中文【中图分类】TP18ZHANG Qing-guo，ZHENG Xue-feng，ZHANG Ming-de，et al.New attribute reduction algorithm of incomplete decision table of informationputer Engineering and Applications，2010，46（2）：19-21. 自从Pawlak教授[1-2]提出粗糙集理论以来，它已在许多领域中取得了较为成功的应用。

在以等价关系为基础的经典粗糙集理论中，已给出了许多基于决策表的属性约简算法，并给出了一些复杂度特别是时间复杂度较好的属性约简算法。

这些算法的研究一方面丰富了粗糙集理论的研究内容，另一方面也为其他一些应用提供了算法基础。

然而等价关系要求太严格，在现实生活中，许多数据难以满足这一要求，特别是针对一些数据不全或者缺失的数据集，更不能满足等价关系。

不完备模糊多目标信息系统中的知识约简与获取研究的开题报告一、选题背景和意义多目标信息系统是指在解决某些问题时涉及到多个目标或指标，而这些目标或指标往往之间相互矛盾，难以综合考虑。

随着信息技术的发展，多目标信息系统逐渐广泛应用于决策支持、战略规划、风险评估、智能控制等领域中。

但是，由于多目标信息系统中存在不确定性、模糊性等问题，因此传统的数据挖掘、机器学习等技术难以很好地应对这些问题。

知识约简是一种重要的数据预处理技术，可以有效地减少数据维度和冗余，提高数据处理效率和精度。

在不完备模糊多目标信息系统中，如何进行知识约简以及如何获取有效的约简知识，是当前研究的热点和难点。

二、研究内容和方法本研究主要围绕不完备模糊多目标信息系统中的知识约简与获取展开，具体研究内容和方法如下：1、针对不完备模糊多目标信息系统中存在的知识不确定性和不一致性问题，提出一种改进的知识约简方法，该方法基于定性推理，利用不确定性逻辑和模糊逻辑进行知识表示和推理，同时考虑到多目标和不完备性的约束条件。

2、针对当前知识约简方法的效率问题，提出一种基于增量学习和深度学习的约简优化方法，该方法利用神经网络和深度学习技术进行特征提取和重构，以提高约简效率和精度。

3、构建一个不完备模糊多目标信息系统的实验平台，利用真实数据集进行验证和实验分析，评估所提出方法的性能、可行性和可靠性，并与其他常用方法进行对比。

三、预期结果和贡献本研究预期可以取得以下结果和贡献：1、提出一种改进的知识约简方法，该方法能够有效地解决不完备模糊多目标信息系统中的知识不确定性和不一致性问题，为实际应用提供一种新的约简技术。

2、提出一种基于增量学习和深度学习的约简优化方法，该方法利用神经网络和深度学习技术进行特征提取和重构，提高约简效率和精度，为知识约简方法的优化提供一种新的思路。

3、构建一个实验平台，验证和评估所提出方法的性能、可行性和可靠性，并与其他常用方法进行对比，为相关领域的实际应用提供一些参考和指导。