不完备信息系统知识获取方法在桥梁养护决策中的应用

'不完备信息系统知识获取方法在桥梁养护决策中的应用2010年第7期计算机与现代化JISUANJIYUXIANDAIHUA总第179期文章编号:1006—2475(2010)07-0188-03不完备信息系统知识获取方法在桥梁养护决策中的应用邹艳,杨丹(重庆师范大学数学与计算机科学学院,重庆400047)摘要:基于相容关系和区分矩阵的知识获取算法来分析信息不完备情况下的桥梁养护决策问题,根据对不完备决策表和完备决策表知识获取结果的对照分析来验证不完备信息系统中知识获取方法的有效性.结果表明,本文所采用的不完备信息系统知识获取方法能有效地消除信息不完备所带来的知识丢失和信息过度膨胀的情况.关键词:不完备信息系统;相容关系;区分矩阵;知识获取;桥梁养护决策中图分类号:TPI82文献标识码:Adoi:10.3969/j.issn.1006-2475.2010.07.050Decision-makingProblemsinBridgeCareBasedonKnowledgeAcquisitionofIncompleteInformationSystemZOUYan,YANGDan(CoHegeofMathematicsandComputerScience,ChongqingNormalUniversity,Chongqing400047,China)Abstract:Thispaperappliesthealgorithmofknowledgeacquisitionofincompleteinformationsystembasedontolerancerelmionanddiscernibilitymatrixtoanalyzethedecision—makingproblem.Accordingtoeontrastiveanalysesofresultsbetweenincompletedecision—makingtableandcompletedecision— makingtable,validityofknowledgeacquisitionofincompleteinformationsystemisverified.Theresultsshowthatthemethodofinformationacquisitioninincompleteinformationsystemcanefficientlycontrolknowledgemissingandextremelyinformationexpanding.Keywords:incompleteinformationsystem;tolerancerelation;discernibilitymatrix;knowledgeacquisition;decision—makinginbridgecare0引言数据挖掘是指从大量不完全,有噪声,模糊和随机的数据集中识别有效,潜在有用以及最终可理解的模式的非平凡过程.基于粗糙集理论的数据挖掘,主要是基于信息系统这种直观的数据表达方式.经典的粗糙集理论¨刮是以等价关系为基础,它的一个假设前提是每个对象的所有属性值都是已知的.但在不完备数据存在的情况下,经典粗糙集模型的应用受到了极大的限制.使用粗糙集理论处理不完备信息,最简单的方法是从初始的不完备信息系统中去掉含有缺失值的对象,这种方法简单但会造成样本的减少和有用数据的丢失.另一种方法是对缺失的数据进行填充使之完备化,然后再用经典粗糙集方法对数据进行处理.这样也可能会造成部分有用信息的丢失或者是信息的过度膨胀,使最后获得的信息严重失真.近年来很多学者将经典粗糙集理论进行扩展,提出了很多直接对不完备信息系统进行处理的基于粗糙集理论的扩充模型和方法.文献[3]引人了不完备信息系统中的相似关系,并在相似关系的基础上建立了知识系统和约简的概念,冯朝一等人在此基础上作了进一步研究引.KryszkiewiczM.提出相容关系 后J,基于相容关系的不完备信息系统的研究就开始不断深入.学者们相继提出了基于相容关系的一种遗传算法的分配约简算法J,在不完备系统中引入了离散数学中的极大相容块技术J,给出了相容关系下的一般粗计算方法以及变精度模型的思想¨叫收稿日期:2010-01-25基金项目:重庆市自然科学基金资助项目(CSTC2009BB6388)作者简介:邹艳(1974一),女,重庆人,重庆师范大学数学与计算机科学学院副教授,重庆大学博士研究生,研究方向:信息系统,粗糙集等;杨丹(1968一),女,副教授,研究方向:信息系统,远程教育.2010年第7期邹艳等:不完备信息系统知识获取方法在桥梁养护决策中的应用189等.张宏宇和梁吉业将变精度模型的思想引入到基于相容关系的不完备信息系统中¨,建立了新的相容类.王国胤等人在相容关系基础上,提出了限制相容关系¨,解决了相似和相容关系的一些局限.陈子春等人基于属性集值的相似程度在集值信息系统上定义了一种新的相容关系¨.面对日益庞大的信息数据,路桥企业在对桥梁养护管理过程中就经常碰到信息不完备的情况.冈此本文主要讨论不完备信息系统知识获取方法在桥梁养护决策问题中的一个应用.为了便于进行理论探讨,本文从桥梁养护的所有指标中选择了一部分重要指标来作为决策表的初始指标.1不完备信息系统和扩展粗糙集定义1141信息系统S=(U,AT,V,f),论域U=(X,X:.…,X)为非空有限集,A={a.,a2,…,a}表示属性集合,存在xi∈U(.=l,2,…,n),ai∈A(j=l,2,…,m),使得f(xi,ai)不存在,即f(X,aj)=null. null表示空值,在信息系统中用""表示,则称S为不完备信息系统.决策表是特殊的信息系统,当AT=CuD时,C和D分别称为条件属性集和决策属性集,这种信息系统称为决策表.定义2设有信息系统S=(u,AT,V,f),f(X,a)是记录x属性a上的值,c.i表示分辨矩阵中第i行,第j列的元素,由此将区分矩阵定义为:(.)={a∈ATIf(xj,a)≠f(xj,a)}其中,i,j=1,2,…,n,这里n=Iul.定义3定于不完备系统中条件属性aEAT确定的相容关系:aT:v甘f(v,d)∈a.(u),U,v∈U定义4设T是论域U=(U,u,…,u…)上的相容关系(满足自反性和对称性),则T对应的相容矩阵定义如下:MT=()…其中(rij):2不完备决策表中基于相容矩阵和区分矩阵的知识获取算法定义5有不完备决策表S=(U,ATU{d},V,f),其中AT为条件属性,{d}为决策属性,ATA{d}=.对任意的u∈U,f(U,d)≠$,定义u关于a∈AT的广义决策函数如下:a(u.):{f(ui,d)If(u.,a)=f(v,a)Vf(I1.,a)=}Vf(V,a):,V∈U}定义6设AAT,A是决策表S的一个约简(d约简),当且仅当a=OAT且(VBcA)a,=aB;AAT是S的一个对于x的相对约简(对于X的d约简),当且 仅当0(x)=a(x)且(VBcA)a(x)≠a(x).定义7设有不完备信息系统S=(U,AT,V,f),f(x,a)是对象x属性a上的值,当值为空时,f(X,a)=.cii表示分辨矩阵中第i行,第j列的元素,定义不完备信息系统中的扩展区分矩阵为:(c.)={a∈ATIf(x.,a)≠f(x,a)^f(x.,a)≠$^f(xj,a)≠}其中,i,j:1,2,…,n,这里n=lUI.定义8区分函数是从区分矩阵中构造出来的.用△表示,对每个属性,指定一个布尔变量"a",若a(xi,xj)={a.,a,…,a}≠,则指定一个布尔函数a】Va2V…Vak,用∑a(xi,xi)来表示.如果a(xi,j)=D,则指定布尔常量为1.布尔函数△可定义如下:/x=n∑a(xi,x;)(xi.x1)EUxU"不完备决策表中,基于相容矩阵和区分矩阵的知识获取算法的基本思想:在不完备信息系统中,通过相容关系和广义决策函数,求出区分矩阵,通过区分函数的约简得到不完备决策表的最优决策规则.设S=(U,AT,V,f)为不完备决策表,算法的基本步骤如下:(1)对S中的数据进行预处理;(2)求出与每个对象可能不可区分的对象集合S(x);S(X)表示对象集{YEUI(X,Y)∈M},令AAT,M表示属性集A上的一个相容矩阵.(3)求解广义决策函数a(x)和扩展区分矩阵;(4)利用区分矩阵求不完备决策表的所有约简;(5)列出不完备决策表所有为真的决策规则,再 由约简得到不完备决策表的最优规则.3桥梁养护方案的决策过程在桥梁养护方案的决策过程中,首先根据检测得到的数据组成初始决策表.然后对数据进行预处理:消去重复的对象和一些不合理的数据,形成最终决策表.根据相关理论和方法对决策表进行属性约简,并最终获取决策规则,为得到最终的桥梁养护决策提供支持.根据对桥梁养护涉及的8个主要指标的10次检测数据,获得某桥梁的初始养护方案决策表,通过消除重复记录和将数据做离散化处理,得到信息完备的决策表S=(u,AuD,V,f)(如表1所示),其中条件属性集A={b,c,d,e,f,g,h,i},决策属性集D={des}.计算机与现代化2010年第7期表l某桥梁总体养护方案决策表UbCdfghdes1l1llllll121l21I12l2321lllll224lll1l2lll5lIl11l3l36l1l3lll227l1l211】l18ll2l2lll19l21111l22103111l1ll3其中,b表示路面纵裂指数;c表示人行道塌陷量;d表示人行道板剥离量;e表示人行道钢栏杆立柱,横管,基座裂开度;f表示斑马线式分隔带损坏程度;g表示桥台台身剥离量;h表示主桥伸缩缝边梁, 横梁,中梁变形量;i表示主桥伸缩缝斜向支撑梁变形量;des表示养护方案.使用ROSETrA软件中的Johnson"salgorithm约简算法,得出约简集合为{h,b,i}.根据得到的属性约简{h,b,i},得出相应的决策规则.规则1:(b,1)^(h,1)^(i,1)一(des,1)规则2:(b,1)^(h,2)^(i,1)一(des,2)规则3:(b,2)^(h,1)^(i,2)—+(des,2)规则4:(b,1)^(h,3)^(i,1)一(des,3)规则5:(b,1)^(h,1)^(i,2)一(des,2)规则6:(b,3)^(h,1)^(i,1)一(des,3)其中,规则1的含义是当路面纵裂指数为1,主桥伸缩缝边梁,横梁,中梁变形量为1,主桥伸缩缝斜向支撑梁变形量为1时,养护方案应该确定为1.其它规则的含义类似.为了便于对比,现根据收集数据的难易程度,在专家的建议下,删除大约10%的数据,从而形成一个不完备决策表S=(u,Au{des},V,f)(见表2).表2某桥梁总体养护方案的不完备决策表UbCdfghdesaAT11l11l11l{1}2ll21ll12{1,2}32l1llll2{2}41ll12ll1{1}511l^113l3{3}6l113l1l22{2l7l12llll1{1}8ll211111{1,2I921111122{2}l03111111l3{3} 根据基于相容关系和区分矩阵的知识获取方法来得出不完备决策表的属性约简和决策规则.首先通过相容关系计算出各对象的S值,再求出各对象的广义决策值(见表2).根据表2,得到区分矩阵(见表3):表3不完备决策表对应的区分矩阵Ul234567891Oldbhe,Ib2db,d3bb,gb.hb,eb,db●●4d,gb,gg,he,g,lg,Ib,g5hdb,hg,hh,ihd,hc,h,i●6e,1e,g,"h,ie.Id,e,ib,e,i7d,eb,ehe.1e.Ib,e8d.hb,({●9g,"C,h,ie,1c,d,iC,110bb,dbb,gb,e,ib.eb.dC.1根据区分矩阵得出区分函数,通过对区分函数的化简得到△=hbdi,即属性约简为}h,b,I,d}.最后得出相应的决策规则为:规则1:(b,1)^(d,1)^(h,1)^(i,1)一(des,1)规则2:(b,1)^(d,2)^(h,})^(i,1)一(des,2)规则3:(b,2)^(d,1)^(h,1)^(i,})-一(des,2)规则4:(b,1)^(d,1)^(h,3)^(i,1)一(des,3)规贝05:(b,1)^(d,2)^(h,1)^(i,1)一(des,1)规则6:(b,)^(d,1)^(h,1)^(i,2)一(des,2)规则7:(b,3)^(d,1)^(h,1)^(i,1)一(des,3)将完备决策表和不完备决策表的属性约简和规则获取结果进行比较,在遗失10%数据的情况下,不完备决策表的属性约简结果即能够包含完备决策标时的属 性约简结果,又不会使约简属性集过渡膨胀.从规则获取的情况看,不完备决策表得出的规则集也是完全包含了完备决策表的规则集,但规则膨胀的规模也不大.在选择最优决策规则时,如果属性约简结果有多个,则可以尽可能选择那些信息完备的属性集合.4结束语本文将扩展粗糙集理论应用于不完备信息系统的知识获取中,采用基于相容关系和区分矩阵的不完备信息系统知识获取算法对桥梁养护过程中的一个决策问题进行了分析.在对不完备决策表和完备决策表属性约简和规则获取结果的对照分析中发现:本文所采用的不完备信息系统知识获取方法既不会使信息过多丢失,也没有使信息过度膨胀.下一步要进行的工作是继续改进算法,降低计算过程的复杂度.(下转第196页)196计算机与现代化2010年第7期图12图形显窗口(2)实现方法:在对数据库检索时选择课程名称和指标等级作为检索变量.(3)操作方法:选择课程,指标等级和图形样式,点击确定,即可显示出相应指标影响程度的指标.选择其他图形样式,即可显示出不同的风格.5结束语经过两个月的学习和研究,大学生知识结构影响分析系统已基本完成.经过测试,其功能基本符合设计的目标,能够支持院校评估课程体系对大学生知识结构的影响分析,发现教学中课程体系安排上存在的不足.在系统设计和开发过程中,也认识到系统有一些问题存在,如目前功能比较单一,界面不够人性化等,还需 要根据学校教学改革的要求不断地完善系统,增加新功能接口,并将开发的程序运行到我院的网络服务器上,让管理者使用更加方便,操作更加快捷,数据更加准确,获取更加及时,使其更人眭化,科学化,网络化.参考文献:[1]尹涛.管理信息系统[M].北京:高等教育出版社,2004:76.80.[2]郑阿奇.PowerBuilder实用教程[M].北京:电子工业出版社,2004:10.[3]何旭洪.PowerBuilder9.0信息管理系统开发[M].北京:人民邮电大学出版社,2005:68?72.[4]汉龙.PowerBuilder9.0项VI开发实例导航[M].上海:上海科学普及出版社,2004:189?194.[5]魏景柱.高校学生素质综合评价研究[D].大庆:大庆石油学院硕士学位论文,2006.[6]赵任凭.论大学生合理知识结构的构建[J].长春理工大学(高教版),2007,2(4):69-71.[7]孙利生.论大学生的基本素质构成及其相互关系[J].民办高等教育研究,2007(3):4547.[8]赵淑英.我国高校学生综合素质测评系统研究[D].哈尔滨:哈尔滨工程大学硕士学位论文,2007.[9]田勤.学校办公用品智能管理系统[D].长春:吉林大学硕士学位论文,2007.[1O]王卫斌,丁慧.层次分析法在学生综合素质评价中的应用[J].牡丹江教育学院,2007(2):86-87.[11]谭跃进,陈英武,易先进.系统工程原理[M].长沙:国防科技大学出版社,1999:1-396.[12]郭齐胜,董志明,李亮,等.系统建模与仿真[M].北京:国防工业出版社,2007:37}5. [13]黄伟超.学生知识增长模式研究[D].哈尔滨:哈尔滨工程大学硕士学位论文,2007.[14]李忠.军事创新人才培养的实践与思考[M].北京:金盾出版社,2005.[15]宣勇,钱配忠.知识增长与学科发展的关系探析[J].大学(研究与评价),2007(1):21.(上接第190页)参考文献:[1]PawlakZ.Rou~lsets[J]IntemationaJournalofComputerandInformationSciences,1982(11):341-356.[2]PawlakZ.RoughSet:TheoreticalAspectsofReasoningA—boutData[M].Boston:KluwerAcademicPublishers,1991.[3]QuinlanJR.Unknownattributevaluesininduction[C]//Proceedingsofthe6thInternationalMachineLearningWorkshop.SanMateo.Canada,1989:164—168.[4]冯朝一,等.基于集合覆盖的不完备信息系统属性约简方法[J].计算机应用,2006(11):2661-2663.[5]杨习贝,於东军,吴陈,等.不完备信息系统中基于相似关系的知识约简[J].计算机科学,2008,35(2):163—165,177.[6]KryszkiewiczM.Roughsetapproachtoincompleteinforma—tionsystem[J].InformationSciences,1998,112(4):3949.[7]KryszkiewiczM.Rulesinincompleteinformationsystems[J].InformationSciences,1999,113(3):171—292.[8]宫俊,唐加福.基于不完备信息系统的分配约简的启发式算法[J].东北大学(自然科学版),2007,28(1):19-22.[9]YeeLeuing,DeyuLi.Maximalconsistentblocktechniqueforruleacquisitioninimcompleteinformationsystems[J]. hfformationSciences,2003,153(7):85—106.[10]ChinKS,LiangJiye,DangChuangyin.Roughsetanalysisalgorithmsforincompleteinformationsystems[C]//Pro—ceedingsof9thInternationalConferenceRSFDGrC.Chongqing,China,2003:264-268.[11]张宏字,梁吉业.不完备信息系统下的变精度粗糙集模型及其知识约简算法[J].计算机科学,2003,30(4):l53—155.[12]王国胤.Rough集理论在不完备信息系统中的扩充[J].计算机研究与发展,2002,39(1o):1238—1243.[13]陈子春,秦克云.集值信息系统在相容关系下的属性约简[J].模糊系统与数学,2009,23(1):150—154.[14]曾黄麟.智能计算[M].重庆:重庆大学出版社,2004.'