搜索
您的当前位置:首页正文

推理建模中基于KDD和粗糙集的案例修改

来源:六九路网
维普资讯 http://www.cqvip.com

第23卷 第lO期 文章编号:1006—9348(2006)10—0141—03 计 算 机 仿 真 2006年1O月 推理建模中基于KDD和粗糙集的案例修改 李伟明,穆志纯 (北京科技大学信息工程学院自动化系,jE京100083) 摘要:在应用基于案例推理技术进行智能建模时,案例修改后的案例质量好坏直接影响所建模型的精度,但是由于案例修改 对领域知识的依赖性很强,采用一般手工案例修改方法尤法保证案例修改的质量,即无法保证智能推理模型的精度。基于以 上原因,该文提出了一种新的案例修改方法,利用KDD技术,通过有效的多值关联规则挖掘算法从运行数据库中挖掘出案 例各属性间的依赖关系,得到案例修改的基本关联规则集,在此基础上利用粗糙集理论对基本关联规则集进行简约,然后根 据简约后的关联规则进行案例修改。在线对比实验证明,应片j本文方法进行案例修改,提商了修改后的案例质量,从而提高 了整体智能推理模型的精度。 关键词:案例推理;案例修改;知识发现;粗糙集 中图分类号:TP18 文献标识码:A Case Revision Method Based on KDD and Rough Set for Case・--Based Modeling LI Wei—ming,MU Zhi—chun (Information Engineering School,University of Science and Technology Beijing,Beijing 100083,China) ABSTRACT:The quality of revised case imposes a direct effect on the model accuracy when the case—based reasoning(CBR)technology is adopted to make the reasoning model intelligent.Manual case revision method is being used commonly,and it’S difficult to guarantee the quality of revised case for its dependence on domain knowledge,namely it is unable to guarantee the model accuracy.For the reasons mentioned above,a new case revision method is developed in this paper in which the technology of knowledge discovery in database with effective mining algorithm of quantitative association rules is introduced to find the dependence relation of each attribute from the operational data records and to get the basic association rules set,and then the rough set is used to acquire the reduction rules for revising the cases.An on—line comparison experiment with satisfactory results show that revised case has high quality by adopting the proposed case revision model,and the accuracy of CBR can be improved accordingly. KEYWORDS:Case—based reasoning(CBR);Case revision;Knowledge discovery in database(KDD);Rough Set 中,案例保存既是学习的过程,也是知识获取的过程 j。 l 引言 基于案例推理(Case—Based Reasoning,CBR)是一 种类 比推理方法,其推理过程如图1所示。具体步骤为:首先从用 户那里得到对问题(案例)的描述,根据案例描述,在案例库 中进行检索,找到最佳匹配的案例;再根据此案例和问题描 案例的检索找到了与当前案例最相似的案例,但它们之 间往往还存在差异。案例的修改就是要通过使用领域知识等 手段消除这些差异,使案例的解完全适合当前案例。由于案 例的修改与具体的问题领域有关,因此难以规定统一的方 法,它是CBR中最困难的…步,很多关十CBR应用系统的介 绍对此都是一笔带过或者干脆忽略不管。 很多CBR应用系统由用户手工调整案例,这种方法思想 述的差异,对此案例进行修改,使之适应当前问题的描述;最 后,将问题的解提供给用户,并将此新案例存人案例库…。其 简单,但工作量巨大,且需要有足够的运行数据,开发周期 收稿日期:2005—06—22 长,而且手工修正很难保证对案例库中各种案例均具有满意 一141— 维普资讯 http://www.cqvip.com

的控制效果。也有一些CBR应用系统尝试利用经验知识,采 表示为X=>Y),其中x I,Y I,且x n Y= 。其意义 在于一个交易中某些项目的出现,可推导出另一些项目在同 一用传统的基于规则推理的方法建立案例修改模型,这是一个 较好的思路,但它存在着实现上的困难,首先,将已有经验全 交易中也出现。“=>”称为“关联”操作,x称作关联规则 面地转化为规则绝非易事;其次,基于规则推理的系统必须 完全满足规则条件才能解决问题,如果问题处于系统已有规 的前提,Y是结果。 2.2 多值关联规则挖掘 则的范围之外,系统对这样问题的求解将无能为力。 考虑到CBR实际应用系统一般都需要采集大量的经验 数据构造案例库,本文将KDD技术与粗糙集理论相结合,提 出了一种基于经验和知识的案例修改新思路和方法,通过 KDD技术挖掘运行数据库中的关联规则来获取案例修改的 Apriori算法 是Agrawal等人在1994年提出来的一种 挖掘关联规则的经典算法。采用KDD中关联规则的挖掘算 法通过挖掘运行数据库中的关联规则就可以获取案例修改 的规则。按处理的对象不同,关联规则可分为布尔型关联规 则和多值关联规则。 基本关联规则集,在此基础上利用粗糙集理论对基本关联规 则集进行简约,然后根据简约后的关联规则进行案例修改。 图1 CBR的推理过程 2 利用KDD发现案例修改基本关联规则集 就CBR实际应用来看,案例作为知识的基本单元,是对 应用领域内一个问题的结构化描述。为了解决问题,需将该 问题所包含的信息表示成案例的形式,通常将案例表示成一 组特征,以形成问题的解的结构。一般地,案例的存储结构包 括二部分:问题描述,即问题的表面特征描述(条件属性);解 特征,即相应于问题描述的案例解(决策属性)。因此,对于发 现案例修改规则的问题可以简化为如下形式:(条件属性l =A。)^(条件属性2=A:)^…^(条件属性m=A ) =>(决策属性l=B。)^(决策属性2=B:)^…^(决 策属性n=B ),这与KDD中挖掘关联规则的情形类似,本 文即通过挖掘数据库中的关联规则来获取案例修改的基本 关联规则集。 2.1关联规则挖掘 关联规则是数据挖掘的重要内容之一,它最初起源于对 超级市场的“购物篮”问题的研究,由R.Agrawal等人提 出 ,侧重于确定数据中不同属性之间的联系,找出满足给 定支持度和置信度闽值的多个属性之间的依赖关系。例如, “在购买VCD的顾客中有66%的人还购买了音箱,同时购买 VCD和音箱的顾客这占整个顾客集合的5%”,其中的66% 和5%分别是该规则的置信度和支持度。挖掘关联规则为发 现数据之问潜在的联系提供了一种有效机制。 关联规则可形式化描述为:设I={i.,i:,…,i }是m个 不同交易项目的集合,给定一个交易数据库D,其中的每个 交易T是I中的一些项目的集合,即T I,每个交易T都与一 个唯一的标识符TID相关联。如果对于I中的一个子集x,有 X T,即交易T包含x,称交易T支持x。一条关联规则就是 一个形如(x包含在T中)j(Y包含在T中)的蕴含式(简单 142一 在CBR实际应用系统中,需要挖掘的案例修改规则中的 属性值常常既有数值属性,又有类别属性,可以按照多值关 联规则挖掘问题(Quantitative association rules problem, QARP)的处理方法进行规则挖掘。QARP比较复杂,一般先 将它转化为BARP(Boolean association rules problem,布尔型 关联规则的挖掘问题),再使用BARP的挖掘算法。 本文的具体算法是:首先进行布尔转换,将数据的各个 属性按一定标准划分为单位区间,将每个区间按顺序映射为 相应的非负整数,并将每一条记录的属性值映射为非负整 数。属性区间可以按数据的分布特征划分,也可以按n等分 的标准划分。从空间的角度来看,全部条件属性构成了一个 多维数据空间。在属性区间划分后,各维度的单位区间在多 维空间中交叉构成了一个个被称为数据包(data cube)t5]的 小单位空间,而每一条数据记录可以看作数据包中的一个 点。通过数据包,重新定义支持度和置信度,从而便于关联规 则的挖掘。 由于挖掘案例修改基本关联规则集时,通常进行一些必 要的假设而忽略一些因素,因此在得到了案例修改基本关联 规则集之后,仍需要进一步删除冗余属性。这时,再利用粗糙 集理论简约规则,然后根据简约后的规则进行案例修改。 3 基于粗糙集的案例修改简约关联规则 粗糙集(Rough Set)是波兰学者Z.Pawlak于1982年提 出的一种处理模糊、不精确的分类问题的新型数学工具。其 主要思想是,在保持信息系统分类能力不变的前提下,通过 知识简约,导出问题的决策或分类规则 。 我们应用Z.Pawlak提出的决策系统(Decision Systems, DS)对问题进行描述,则粗糙集的方法和模型就可以建立在 一种非常直观的二维决策表的基础上。为此进行如下定义: 定义3.1(决策系统,DS) 称S=(u,A,{Va},a)为知 识表示系统,其中: u为非空有限集,称论域; A为非空有限集,称属性集合; Va为属性a∈A的值域; a:U.一Va为一单射,使论域u中任一元素取属性a在Va 中的某一唯一值。 如果A由条件属性集合c和结论属性集合D组成,c、D 维普资讯 http://www.cqvip.com

满足C U D=A,C n D= ,则称S为决策系统 。 定义3.2(DS的不可分辨关系,Indiscernibi!ity Relation) 对决策系统S:(U,C U{d}),B C是条件属 最小支持度和最小置信度的关联规则; 4)对挖掘出的关联规则进行聚类,得到解释能力更强的 案例修改基本关联规则集; 性集合的一个子集,称二元关系IND(B,{d})={(x,Y)∈U X U:d(x)=d(Y)或者V a∈B,a(x)=a(Y)}为S的不可 分辩关系,其中,x,Y为U中的元素。 不可分辨关系是一个等价关系,通过一个不可分辨关 5)根据粗糙集理论简约案例修改基本关联规则集; 6)得到简约的案例修改关联规则,并以表格的形式存放 于数据库中,以此作为案例修改规则库供CBR使用。 系,可以得到决策系统的一个划分,称划分后的等价类为不 4 应用实例 可分辨类,通常用[x] 来表示包含元素x的不可分辨类。 常用IND(B)来表示不可分辨关系IND(B,{d})。 粗糙集理论的不确定性是建立在上、下近似的概念之上 的。 定义3.3(上近似和下近似) 对于知识表示系统S= (U,A),设B A,x∈U,称 BX:{x∈U l[x] (B)∈X}, BX={x∈U I[x]INDf B)n X≠ } 分别为x的B一下近似(B—Lowerapproximation),B一上 近似(B—upperapproximation) 。 定义3.4(粗糙隶属函数,Rough Membership Function)[ ] B(x,X)=card([x]B n X)/card([x].1),其中 card(・)表示取集合中元素的个数。 粗糙集理论具有从信息表中抽取规则的能力,在粗糙集 理论中抽取规则是一个求值约简的过程。 定义3.5(简约,Reduction):对于一个给定的决策系统S =(U,C U{dt),条件属性集合C的简约是C的一个非空子 集C ,它满足: (1)IND(C ,{dt)=IND(C,{dt) (2)不存在C C C ,使IND(C”,{dt):IND(C,{d}) C的所有归约集合记作RED(C) 。简约可以理解为,在 不丢失信息的前提下,可以最简单地表示决策系统的结论属 性对条件属性的集合的依赖和关联 。 定义3.6(相对可去除属性) 对于决策系统S=(U,C u{d}),不可分辨关系IND(C)将U划分为t个不可分辨类 x。,x:,…,x ,令D(X.)为x 的所有结论属性d的取值的集 合,即D(X.)={v=d(x):x∈X.},如果D([x ] ~ ) =D(Xi),条件属性a∈C称为相对于不可分辨类x.可去除 的。即,如果a为相对于x 可去除,则a的存在与否不影响x. 的结论值的集合。 总的来说,案例修改关联规则的挖掘和简约是一个比较 复杂的过程,本文提出的基于KDD和粗糙集进行案例修改 的具体步骤为: 1)提取数据; 2)对需要挖掘关联规则中的每个属性进行区间划分,分 别将各区间按顺序映射为非负整数; 3)对条件属性构成的多维数据空间中的每个数据包进 行加权计算,得到加权支持度和加权置信度满足用户给定的 将本文提出的案例修改模型应用于国内某钢铁厂轧制 规程的推理建模,进行在线对比实验,以钢种、来料厚度、成 品厚度分别为Q195,3.Omm,0.8 mm为例,用本文提出的基 于KDD和粗糙集的案例修改方法和手工案例修改方法分别 进行案例修改,得到两种不同的轧制修改案例,再分别利用 这两种不同的轧制修改案例进行轧制规程的推理建模,具体 如表1所示(利用KDD技术挖掘到的案例修改基本关联规则 集如表2所示,根据粗糙集理论进行案例修改关联规则的简 约如表3所示) 表1 轧制规程比较 (辊缝值;arm) 道次 手工案例修改 基于KDD和粗糙集案例修改 实际采集的 生成的轧制规程 生成的轧制规程 轧制规程 l 1.62 1.6O 1.6l 2 O.9,1- 0.96 O.98 3 0.5,-1 O.55 0.56 表2 利用KDD挖掘到的案例修改规则 规则号 条件属性 决策属性 O l l O O l l O O l 2 O l O l 表3 根据粗糙集理论得到简约规则 规则号 条件属性 决策属性 O l l O l O l 2 O l 从表1所示的数据中可以看出,利用本文基于KDD和粗 糙集方法得到的轧制修改案例所建立的轧制规程与实际采 集的规程更接近,亦即所建的模型更为合理,精度更高。 在实际应用中,利用KDD和粗糙集进行案例修改后,有 可能还需进行某些修正,这时可以通过人机界面进行微调。 5 结论 本文针对基于案例推理智能建模中案例修改这一关键 技术,提出了利用KDD技术和粗糙集理论进行案例修改。采 用KDD技术可以从运行数据库中挖掘潜在的领域知识,得 到案例修改基本关联规则集, (下转第159页) l43— 维普资讯 http://www.cqvip.com

司的飞机液压系统脉冲试验台中使用了CMAC自学习控制 方法,控制参数同4.1中的CMAC参数,针对不同的试验件均 取得了较好的控制效果,图4a是试验件为2升蓄能器的水锤 IEEE International Conference On Systems, Man and Cybernetics,Volume:4,6—9 Oct.2002,4:6. edit assigned CMAC and its l 3 J F S Shun,T Ted,T H Hung.Cr波实际CMAC控制结果。综合仿真结果图与实际的控制结果 图可发现仿真模型贴近实际情况,仿真结果可信度较高;在 液压脉冲系统中采用的CMAC的自学习控制对不同试验件 具有自适应能力,且控制精度高,收敛性快,鲁棒性好的特 点。 application to online learning robust controllers[J]。IEEE Trans.On Systems,Man and Cybernetics,PartB:Cyb'ernetics, 一 2003。3(2):202—213. Jovic and Vinko. Finite elements and the method of characterisitcs applied to water hammer modeling[J].Int. Jour.For Eng.Modeling,1995,8(3—4):51—58. zquierdo and P L Iglesias.Mathematical Modeling of [5] J I5 结束语 液压脉冲是导致飞机液压系统提前损坏的重要原因之 一tlydraulic transients in Simple Systems[J].Mathematic and Computer Modeling,2002,(3). ,因此开展液压脉冲的理论和试验技术研究具有重要的理 [6] V L Streeter.Water hammer analysis[J].Jour.Hyd.Div., ASCE,1969,88,HY3(5):79一ll3. 论价值和现实意义。论文建立飞机液压系统脉冲试验系统的 数学模型,综合了水锤波的控制特点和CMAC网络在非线性 函数逼近问题中的优势,提出采用CMAC自学习控制方案解 [7] 叶正茂,李洪人,王经甫.基于CMAC的电液负载模拟器自学 习控制[J].控制与决策,2003,5. [8] 李辉.一种自适应CMAC神经网络控制器的设计与仿真[J]. 系统仿真学报,2005,9. 决不同试验件的水锤波控制问题,并进行了仿真计算。仿真 结果表明,该方法对不同的试验件和试验环境具有自适应能 力,且控制精度高,波形调整时间短,具有较强的鲁棒性。目 前,该控制方案已成功的应用在某航空公司的飞机液压系统 脉冲试验平台上,并取得了预期的效果。 参考文献 J S Albus.A new approach to manipulator control:The cerebellar model articellation controller(CMAC)[J].ASME J. Dynamic Systems,Measurement,Control,1975,220—227. _ [李在仿陈博职真 士博。生 军明士导研(师1究9731生9一,研),男作究方(者汉向简族为介)液,】 湖江压南苏伺邵南服京阳控人制,讲、教系师授统, ,研究方向为检测技术与自动化装置。 赵怀军(1968一),男(汉族),陕西宝鸡人,讲师,研究方向为检测技 术与自动化装置。 [2] Ming—Feng Yeh.Hung—Ching Lu.On—Line Adaptive Quantization Input Space in CMAC Neural Network[C].2002 (上接第143页) [5] R Agrawal,A Gupta,S Sarawagi.Modeling multidimensional 再利用粗糙集理论进行案例修改基本关联规则集简约,删除 冗余属性,进一步提高了案例修改关联规则的精度和解释能 力,提高了修改后的案例质量,从而提高了整体智能推理模 型的精度。 [7] databases[C]。Proc.the 13th Int Conf.on Data Engineering, l997. 科学出版社,2001。 [6] 刘清.Rough集及Rough推理[M].北京:Z Pawlak.Rough Sets Theoretical Aspects of Reasoning About Data[M].Kluwer Academic Publishers,l991. 参考文献: [1] 田盛丰.人工智能与知识工程[M].北京:中国铁道出版社, 1999. [2]D Leake.CBR in Context:the Present and Future.Case—based Reasoning:Experiences,Lessons&Future Directions[M]. AAAI Press,1996. 飘 [李士机穆生过伟志程,纯明主控(要制19研75。 2究.3方一向)作为,女者复(简杂汉系介族统)】 ,建内模蒙与古控包头制人,计,博算 .1一),男(回族),天津人,博士生导 [3]R Agrowal, et a1.Database Mining:A performance Perspective[J].IEEE Transaction on knowledge and Data Engineering,1993,(12):914—925. 师,教授,主要研究方向为复杂系统建模与控制,计 算机过程控制,生物特征识别。 [4] R Agrawal,R Srikant.Fast Algorithms for Mining Association Rules[C].In:Proceedings of the 2Oth International Conference on Very Large Databases,Santiago,Chile,Sept,1994.487—499. 一l59— 

因篇幅问题不能全部显示,请点此查看更多更全内容

Top