不确定性信息系统中的知识表达与约简

不协调优势目标信息系统的启发式约简算法不协调优势目标信息系统的启发式约简算法在信息系统领域，不协调优势目标信息系统是一个重要且复杂的研究课题。

由于信息系统中存在大量的冗余和重复信息，如何对信息系统进行有效的约简，以提高系统的效率和性能，一直是学术界和工业界共同关注的焦点。

而启发式约简算法，则是在此背景下应运而生的一种重要方法。

启发式约简算法是一种基于启发式思想，结合信息系统本身特点和问题需求，利用简单、快速的算法对系统信息进行约简的方法。

这种算法往往能够在保证系统关键信息的前提下，大大减少系统信息的冗余部分，从而提高系统的效率和性能。

在实际应用中，启发式约简算法已经被广泛应用于数据挖掘、模式识别、智能决策等领域，并取得了显著的成效。

下面，我将从深度和广度两个方面，对不协调优势目标信息系统的启发式约简算法进行全面评估，并撰写一篇有价值的文章，以便更深入地理解这一主题。

一、深度探讨1. 启发式约简算法的原理和方法启发式约简算法主要基于对信息系统的特征和相互关系进行分析和挖掘，通过设定一定的约简规则和启发式函数，对系统信息进行迭代和优化，最终得到约简后的系统信息。

常见的启发式约简算法包括基于遗传算法、模拟退火算法、粒子群算法等。

这些算法通过不断调整约简规则和参数，能够有效地降低系统信息的复杂度，提高系统的可解释性和执行效率。

2. 不协调优势目标信息系统的特点和需求不协调优势目标信息系统是一种多目标决策系统，其中存在着不同目标之间的矛盾和不协调现象。

对于这类信息系统，启发式约简算法需要考虑多目标的特点，能够兼顾系统各个目标之间的关联性和权衡性，以实现系统信息的全面约简。

3. 启发式约简算法在不协调优势目标信息系统中的应用在不协调优势目标信息系统中，启发式约简算法能够有效地对系统信息进行全面、深入的约简，从而减少系统的冗余和重复信息，提高系统的效率和性能。

通过合理设置启发式规则和参数，可以使系统在约简后仍然能够保持其多目标决策的特性，实现系统信息的精练和优化。

经自然科学奖推荐项目公示内容1、项目名称:不确定性知识发现的粗糙集理论与方法2、推荐单位:重庆市科学技术委员会3、项目简介:知识发现与数据挖掘(KDD)概念由 U . Fayyad 教授 1989 年提出。

第一届 K DD 国际会议 1995 年召开后，国际上掀起了知识发现研究热潮。

近年来云计算、物联网、 社交网络等迅猛发展，数据急剧增长，大数据的出现进一步使知识发现研究成为科技界、工业界、金融界等社会各界关注的焦点。

数据已从简单的处理对象转变成为基础性资源。

如何从数据中高效发现有价值的知识，成为世界各国竞争的战略性问题之一。

其中，不确定性知识发现的难度大、价值高，从知识发现研究开始就成为了一个关键瓶颈问题。

项目第一完成人早在上世纪九十年代就开始在国内开展粗糙集研究，利用在西安交大和西南交大作兼职教授的机会，组织两校吴伟志、米据生、李天瑞等一大批青年博士开展粗糙集不确定性知识发现研究，形成一支稳定精干的青年研究队伍。

在科技部、教育部、基金委等部委14 项科研项目持续资助下， 过十多年不懈攻关， 在不确定性知识发现的粗糙集基础理论和模型算法上取得重要突破，并在解决流程工业控制、遥感图像处理、生物信息处理等应用领域的关键问题中发挥了重要作用，部分成果获重庆市自然科学一等奖。

本项目的关键科学发现点为：①首次发现粗糙集代数描述形式与信息熵描述形式之间呈包含关系，修正了学术界长期公认的二者之间等价这一经典结论，建立了不确定性知识的粗糙集近似逼近理论，为不确定性知识发现中的知识表达、特征度量、特征选择奠定了理论基础。

②创建不确定性知识表达的多粒度粗糙集模型，刻画了人脑多粒度认知机理，揭示了知识粒度的演化规律，实现了复杂问题的多粒度求解，突破了传统数据挖掘仅能获取单粒度知识的局限。

③首次建立不确定性知识近似逼近中特征选择的充分性判据和必要性判据，实现了最优特征选择这一NP-hard 问题的粗糙集近似求解。

④创建数据特征驱动的知识发现模型，通过不确定性知识的特征度量，实现了多源异构、海量动态数据的渐进式高效知识发现。

海量数据下不完备信息系统的知识约简算法王添;姜麟;米允龙【期刊名称】《计算机技术与发展》【年(卷),期】2015(000)001【摘要】Knowledge reduction for massive datasets has attracted many research interests in rough set theory. Traditional knowledge re-duction algorithms of incomplete information system assume that all the datasets can be loaded into the main memory,which are obvious-ly infeasible for large-scale datasets,especially for massive datasets with missing information. To this end,deeply analyze the characteris-tics of massive datasets with missing information,and allow the missing attribute value to take all possible values. Then,by combining the parallel computations used in classical knowledge reduction algorithms with the discernibility( indiscernibility) of the attributes,a knowl-edge reduction algorithm is designed for incomplete information systems under MapReduce framework. The experimental results demon-strate that this algorithm is effective and feasible,which can efficiently process massive datasets for knowledge reduction in incomplete in-formation systems.%面向大规模的数据进行知识约简是近年来粗糙集理论研究的热点。

粗糙集属性约简的方法ComputerEngineeringandApplica~ons计算机工程与应用◎数据库,信号与信息处理@粗糙集属性约简的方法王培吉,赵玉琳27吕剑峰W ANGPeiii,ZHAOYulin,LVJianfeng1内蒙古科技大学数理与生物工程学院,内蒙古包头0140102内蒙古第一机械集团公司二分公司,内蒙古包头0140321.SchoolofMath.,Physics&BiologicalEng.,InnerMongoliaUniversityofSciencean dTechnology,Baotou,NeiMongol014010,China2.Branch2,InnerMongoliaFirstMachineryGroupCorporation,Baotou,NeiMongol01403 2,ChinaW ANGPeiji,ZHAOYulin,LVJianfeng.Newmethodofattributereductionbasedonroughse puterEngineeringandAp—plications,2012,48(2):113—115.Abstract:Objectsclassificationisstrictexcessivelyandtoosensitiveonnoise.Aimingatdeci sionsystemwithuncertainfactor.anal? gorithmofattributereductionbasedondependabilityisestablished.Theattributesinthesyste mwithuncertaininformationandnoisedataarereduced,wherebyfindingareducibleimpliedpatternofthedata,anddeletingthosere dundantrulesinthesystem.Anditcan keeptheoriginalpropertiesandfunctionsofthesystem.Theimplementationofalgorithmisd escribedbyintroducinganexample.Keywords:roughset;dependability;attributereduction;implementation摘要:传统粗糙集分类方法过于严格,对噪音过分敏感.针对带不确定因子决策系统,提出一种基于属性依赖度的约简算法,使含不确定信息及数据噪音的系统中的属性得以简化,找到一种具有广泛表达能力的数据隐含格式,删去冗余的规则,并保持系统的原有用途和性能.通过一个例子实现了该算法.关键词:粗糙集;依赖度;属性约简DOI:10.3778/j.issn.1002—8331.2012.02.032文章编号:1002.8331(2012)02.0113.03文献标识码:A中图分类号:TP311基于粗糙集理论】的知识获取的核心问题之一是属性约简,有很多学者作了这方面的工作,其中应用较多的是基于辨识矩阵以及在此基础上的一些改进算法1.一般说来,知识库中的知识(属性)并不是同等重要的,还存在冗余,这不利于做出正确而简洁的决策.属性约简要求在保持知识库的分类和决策能力不变的条件下,删除不相关或不重要的属性.一般而言,较优的属性约简有如下指标:约简后属性个数较少;约简后规则数目较少;最终范化规则数目较少等.已证明求决策表所有约简和最小约简是一个典型的NP嘲问题,不过,在实际应用中,往往只要求出某种次优的属性约简就可以了.传统粗糙集分类方法过于严格,以及数据中存在噪音,造成知识的遗漏.如:条件属性下的两个等价类.,,分别有100个元素,对决策属性等价类,,只有一个元素属于,而,只有一个元素不属于,基于传统的粗糙集模式,,,同属于的边界区,对都不能作出肯定的判断,然而A,中只有一个元素不属于,也许是由噪音导致的,说明传统粗糙集对噪音是非常敏感的,而在机器学习,专家系统等实际应用中,获得的数据含有噪音是不可避免的,因此传统粗糙集模式在一定程度上限制了它更有效的应用,本文提出的针对带不确定因子决策系统的分类方法可将原来由于噪音的影响,被划到边界的等价类划回到正区(如上面的,)或负区(如上面的),克服了粗糙集对噪音过分敏感的缺点,使在有噪音的环境下获得的知识更可靠.1带不确定因子决策系统定义1称=fU,CUD,{},,imp}为带不确定因子的决策系统,记为S,D=},d是带不确定因子(0<-I.t1)的结论属性,=1表示该元素对结论有完全肯定的判断,即该元素所在等价类属于结论属性的正区POSB(D),=0表示该元素对结论有完全否定的判断,即该元素所在等价类属于结论属性的负区NEG09);imp是中元素在中的重要度,体现元素在中的重要性./1,imp由领域知识及数据库操作得到.如表1为一带不确定因子的决策系统.表1带不确定因子的决策系统075O.67O-350750.670_35表1中U={1,2,3,4,5,6),条件属性集C={日1,口2),1={1,2),2={1,2,3),决策属性D={,={1,2,3),每一元素的重要度imp={4,3,4,4,3,4},及不确定因子={O.75,0.67,0.35,0.75,0.67,0.35}.基金项目:国家自然科学基金(No.81060238).作者简介:王培吉(1968一),男,副教授,主要研究领域为数据库,数据挖掘;赵玉琳(1968一),男,高级工程师;吕剑峰(1984_),男,助教.E-mail:*************收稿日期:2011-01.24;修回日期:2011-04.26;CNKI出版:2011-07—25;/kcms/detail/11.2127.TP.20110725.1624.020.html ComputerEngineeringandApplications计算机工程与应用2属性依赖度与属性约筒2.1属性依赖度定义2在S中,BcC,,YcU/B且处于边界,划POSB(D):rflJY;~IJ)kNEG口(D)的误差p()和,l(】,)分别定义为: ):—Z—(impi_x(1一-,ui))厶l州,,?(y):—~.,(im_Pixiai)乙Ilnl划入正区和y划入负区的误差水平分别记为,.即:p()P时,XcPOSB(D);n(】,)≤Ⅳ时,YcNEG口(D●.定义3对,在误差水平为和下,结论屙陛d对条件属性集合C依赖度Dep(C,D,,)是U/C被划入正区POSc(D)和Y划入负区NEG(D)中元素重要度的和与所有元素重要度之比.2.2属性约简定义4在中,误差水平为P和,BC,a∈B,Dep(B,D,,Ⅳ)=Dep(B-{a},D,,aN),称a为B中可省略的,否则a为当中不可省略的;当所有a∈B在中不可省略的,且Dep(B,D,,Ⅳ)=Dep(C,D,,Ⅳ),即D对B,C有相同的依赖度,则是c的一个约简u.定义5在S中U/C={,,…,},称)为的辨识矩阵,其中,"一C:a(X)~a(Xj),D()≠D()}1,其他'其中l≤f,j<t.m包含使得,具有不同结论属性值的所有属性.称/=,vm为S的分辨函数,其中V表示m中所有属性的析取运算,^表示合取运算.如果一个属性在信息系统中是可省略的,删除此属性并不影响信息系统的依赖关系,且能与c一样分辨所有元素的属性子集,但这样的约简不是唯一的,co~(c1表示C的所有约简的交集.核.表1表示的带不确定因子信息系统中P=0.3,=0.6条件属性C的等价类:={l}={2}={3}={4}={5}={6}由P()={{4×(1.0—0.75)j=0.25P()={{3x(1.0—0.67)}=0.33P()={4×(1.0～o.75)}:0.25P()={{3×(i.0一o.67)}:0.33Ⅳ()={4×0_35))=0.35Ⅳ(x6):{4×0_35)}=0.35及P=0.3,Ⅳ=0.6得P(D):{,(D):{,}BND(D)={,}DEP(C,D,P,Ⅳ)=I-(4+4+4+4)=0.73等价类,划回到正区,等价类,划回到负区;而用传统粗糙集进行分类,它们却都属于边界类,造成了知识的遗漏和偏差.3基于属性依赖度的属性约简算法步骤1根据挖掘目标,选取一屙l生为结论屙陛,其余为条件属性;对数据进行归纳,形成宜于实施挖掘的数据形式,同时,结合统计结果及领域知识为每一对象赋一重要度imp及不确定因子,形成带不确定因子的决策系统=(￡,,CUD, {},imp).步骤2由及不可分辨关系形成条件属性等价类和结论属性等价类,对处于边界的等价类,根据,imp及和划入正区和负区,由新的等价类形成可辨识矩阵.步骤3由可辨识矩阵找出该不可分辨关系的核B=COl~(C).步骤4C=C—B.步骤5对每一属性a∈C,计算Dep(BU{a},D,,,)一Dep(B,D,P,Ⅳ)并按降序排列C.步骤6DoJl[~序取a∈C,B=BU{a},C=C一{a}计算Dep(B,D,p,Ⅳ)UntilDep(B,D,P,Ⅳ)=Dep(C,D,dP,Ⅳ)步骤7For/=1to1B1Do如果a诺co~(c),则B:-{a}若Dep(B,D,,ON)~:Dep(C,D,P,Ⅳ)则B=BU{a.1.步骤8得条件属性c的约简为子集B.步骤9由约简简化带不确定因子的决策系统,形成由约简属性集为条件属性的决策系统S=,BU{d}).步骤10合并相同和相近元素(若结论相同,条件中仅有一项不同,则该项对该结论无关紧要).步骤11知识表示.4实例分析决策系统=,CU{d}),按结论属性d排序,为每一对象赋一重要度imp及不确定因子(如可将条件属性下每一等价类元素个数作为该对象的重要度imp),得到带不确定凶子的决策系统=(,CUD,{}c,,imp),见表2.由表2得条件属性C的等价类为={1),:{2}1={3},={4},={5,12},:{6j,={7,9},={8},=flo},Xl.:{1l},={13},:={14,15}.合并等价类得表3,进而得辨识矩阵(见表4).由可辨识矩阵得COl~(C)={a3}.:CORE(C)={a3),C={Ⅱ1,a2,a4,a5}.对每一属性a∈C,计算Dep(BU{aD,,).王培吉,赵玉琳,吕剑峰:粗糙集属性约简的方法2012,48(2)115 表2带不确定因子的决策系统表3=U,CUD,{)Ⅲ,,帅)表4辨识矩阵910l1a2a4a2a3a5ala2a3a5a2a4a2a3a5ala2a3a5a2a4a2a3a4a5dla2a3a4a5a2a4a2a3a4a5ala2a3a4a5ala4a5ala3a4a5a3a4a5a1a2a4ala2a3a4a5a1a2a3a4a5a2a4a5a2a3a4ala2a3a4a2a3a4a2a3a4a5ala2a3a4a5a3a4a2a3a4a3a2a3ala2a3a5ala3a3a5由条件属性co~(c)U{al}的等价类为={1,5,6,7,8,9,12,13},={2},={3),:{4,10},={14,15}及)=(1×(1—0.6)×2+2×(1—0.9)×4+1×(1—0.8)+l×(1—0.9))/12=0.158,z()=(1×0.6×2+2×0.9×4+1×0.8+1×0.9)/12=0.842 p(x2)p(X3)1×(1—0.9)/1=0.1n()n(X3)1x0.9/1=0.9P(X4)=(1×(1—0.9)+1×(1—0.8))/2=0.15H()=(1×0.9+1×0.8)/2=O.85)(2×(1—1)+2×(1—1))/4=0n(Xs)=f2×1+2x1)/4=l得正区等价类为={2)={3)x4={4,10}={14,15};边界等价类为={1,5,6,7,8,9,12,13).这样Dep(CORE(C)U1}, D,P,Ⅳ)=9/21.同理可得:Dep(CORE(C)U{a2},D,P,Ⅳ)=21/21Dep(CORE(C)[J{a4},D,,Ⅳ)=19/21Dep(CORE(COU{a5},D,P,Ⅳ):9/21按依赖度降序排列C={a2,a4,al,a5}B=cD衄(c)U{a2}:{a2,a3}Dep(B,D,P,Ⅳ)=21/21B=曰U{a4)={a2,a3,a4}可求得:Dep(B,D,,Ⅳ)=19/21a2硭CORE(C),贝0B=B-{a2)={a3,a4)又Del~B,D, P,Ⅳ)=19/21DIC,D,P,aN).这样,求得条件属性c的约简为子集B={a3,a4,.由约简B={口3,a4},表3简化为表5.=3对应的五:a3=3,a4=2及五:a3=3,a4=3中仅有口4的值不同,将对应的a4值去掉合并墨,化为表6.表5决策系统"=",BU{d})表6决策系统=,BU{d})知识表示:{(口3=3)^(a4=1)}v{(a3=2)^(a4=2)}(=2)(a3=3)=3)(a3=4)^(a4=3)=4)5结束语本文针对带不确定因子决策系统,提出了一种基于属性依赖度的属性约简算法,本算法能从属性集合中有效去除冗余属性,使属性选择的结果更合理,数据噪音的影响更小,获得的知识更可靠.在大部分情况下本算法都能快速有效地找到属性子集的最优解或令人满意的次优解.(下转129页)m56789m¨刘兴阳,毛力:基于f分布变异的自适应差分进化算法2o12,48(2)129进化代数进化代数进化代数进化代数图1sphere函数寻优曲线对比图2R0senbr0ck函数寻优曲线对比图3Griewallk函数寻优曲线对比图4Ackley函数寻优曲线对比表1三种算法寻优结果比较5结论本文提出一种基于f分布变异算子的自适应差分进化算法:其一在变异过程中使用f分布变异算子有效地将高斯变异和柯西变异进行结合;其二根据进化的不同阶段,提出新的自适应方式来调节进化策略及交叉概率.通过采用四个典型测试函数对新算法进行测试,实验结果表明本文提出的改进算法具有较好的全局探索能力和局部开发能力.参考文献:[1】StornR,PriceK.Differentialevolution-asimpleandefficient heuristicforglobaloptimizationovercontinuousspaces[J].Jour- nalofGlobalOptimization,1997,11(4):341—359.【2]ZhangM,LuoW,WangXF.Differentialevolutionwithdynamic stochasticselectionforconstrainedoptimization[J].Information Sciences,2008,178(15):3043.3074.【3]3唐德翠,朱学峰.改进差分进化PID参数优化及在凝絮中的应用[j]. 计算机工程与应用,2009,45(24):204.206.[4】MaulikU,SahaI.Modifieddifferentialevolutionbasedfuzzy clusteringforpixelclassificationinremotesensingimagery[J]. PaaemRecognition,2009,42(9):2135-2149.【5】RahnamayanS,TizhooshHR,SalamaMMA.Opposition-based differentialevolution[J].IEEEComputationalIntelligenceSociety,2008,12(1):64—79.[6】潭跃,谭冠政,伍雪冬.基于交叉变异策略的双种群差分进化算法[J]. 计算机工程与应用,2010,46(18):9-12.[7】DasS,AbrahamA,ChakrabortyUK.Differentialevolutionusing aneighborhood—basedmutationoperator[J].IEEETransactions onEvolutionaryComputation,2009,13(3):526.553.【8】LanKuo-Tong,LanChun-Hsitmg.NotesonthedislinctionofGaussian andCauchymutations[C]//EighthInternationalConferenceonIn. telligentSystemsDesignandApplications,2008:272-277.[9】Y aoX,LiuY,LinG.Evolutinaryprogrammingmadefaster[J].IEEE TransactionsonEvolutionaryComputation,1999,3(2):82—102.【1O】周方俊,王向军,张民.基于t分布变异的进化规划【J].电子, 2008,36(4):667.671.(da接l15页)参考文献:【1】PawlakZ.Roughset[J].InterofComputerandInformationSci- ences,1982,11.【2】刘清,刘少辉,郑非.Rough逻辑及其在数据挖掘中的应用【J】.软件,2001,12(3):415—419.【3】刘银山,吴孟达,王丹.粗糙集中求取所有最小约简快速算法【J].计算机工程与科学,2007,29(I):97—100.[4】苗夺谦,胡桂荣.知识约简的一种启发式算法[J】.计算机研究与发展,1999,36(6):681.684.【51HuXiaohua,CerconeN.Learninginrelationaldatabases:a roughsetapproach[J].ComputationalIntelligence,1995,11(2):323.337.[6]胡或,李智玲,李春伟.一种基于区分矩阵的属性约简算法[J].计算机工程与应用,2007,43(9):178.181.[7】黄治国,王端.基于粗糙集的数据约简方法研究[J】.计算机工程与设计,2009,30(18).【8】WongSK,ZiarkoW.Onoptimaldecisionrulesindecisionta-bles[J].BulletinofPolishAcademyofScience,1985,33:693-696.(上接123页)【7】ZhuZhengyu,XuJingqiu,RenXiang,eta1.QueryExpansionBased onaPersonalizedWebsearchmodel[C]//ThirdInternationalCon- ferenceonSemantics,KnowledgeandGrid,2007:128—133.【8】ZhuZhengyu,ZhouZhi,YuChunlei.Aquantizedanalyzingmethod forfindingauser'sinterestedwebpagesbasedontheuser's browsingactionsandquerywords[C]//InternationalConference onWebInformationSystemsandMining,2009.【9】ZhuZhengyu,TianYunyan,YuanKunfeng,eta1.Animproved Webdocumentsclausteringmethord[J].JournalofComputational InformationSystems,2007,3(3):1087—1094.[10】蒋萍.基于用户兴趣挖掘的个性化模型研究与设计[D].苏州大学, 2005:39-40.[11】张敏,宋睿华,马少平.基于语义关系查询扩展的文档重构方法[J].计算机,2004(10).【l2】瞿瑞彩,谢伟松.数值分析【M】.天津:天津大学出版社,2001:2-3. [13】LovicS,LuMeiliu,ZhangDu.Enhancingsearchengineperfor- manceusingexpertsystems,informationreuseandintegration[C]g IEEEIntema~IonalConferenceonSept2006:567.572.^趔卿籁闺。