基于规则的实例检索模型

基于规则的实例检索模型

基于实例的推理（rcr），该算法适用于复杂和病态结构的机械设计问题。此步骤包括实际的表达和存储、检索、调整和学习。其中，示例研究算法的效率和精度是cbr技术的关键。最近邻算法是目前应用最为广泛的实例检索算法,但尚存在一些不足:(1)没有考虑实例的多索引机制。(2)随着实例库中实例增加,检索效率呈线性下降。(3)特征权重和特征属性相似度都需要由领域专家确定,其他算法如特征评估算法、反省算法和神经网络方法等考虑了特征权重的调整,但调整策略有待进一步研究。(4)机械设计实例的索引词汇的确定是一个NP难题,要求索引词汇便于扩充,而最近邻算法和文献算法都没有考虑索引词汇的动态扩充问题。1生成信息的规范表达针对以上问题,本文提出了一种基于多粒度的实例和规则索引统一表达机制,用基于规则推理(RBR)减小检索范围并优化实例检索的质量,支持索引词汇的动态扩充和特征权重与特征属性相似度的动态调整,基于多粒度的实例和规则索引统一表达机制见图1。实例库由零件-组合件-产品3层实例库组成,产品实例的内容包括实例号、实例索引码、实例CAD模型(总体控制结构)和所包含的标准零件、组合件的描述信息或非常用件的名称和存储路径等。规则的条件子句描述规则的适用条件,用“规则索引码”表示,结论子句可以是规范的信息,如标准件的名称、类别,也可以是自由语义信息。定义1特征集:记实例d有n个描述特征项,d={pi},每个描述特征项的当前取值为vi,其中1≤i≤n。对于实例库中的所有实例,若存在一个最小的整数I,1≤I≤n,使得d=d′⇔v1=v′1,v2=v′2,…,vI=v′I,则称由描述特征项p1,p2,…,pI构成的集合为特征集。即特征集是指能概括实例的主要功能和结构,且能使实例相互区分的描述特征项的集合。定义2特征属性集:某一实例描述特征可能取值的集合,特征属性集与特征集的关系为attribute-of。“特征集”和“特征属性集”构成索引词汇,用以描述实例和规则的索引。“实例索引码”和“规则索引码”分别是一个序列,序列的各元素用相应“特征项”的“特征属性代号”以代号(单个“特征属性代号”)、代号集(部分“特征属性代号”的并集)或“*”(全部“特征属性代号”的并集)3种粒度表示。“问题描述码”的表示方法同“实例索引码”和“规则索引码”类似,但序列的元素只以“代号”和“*”2种粒度表示。本文引入了“特征属性相似度矩阵”的概念,用以表示某“特征项”的所有“特征属性”两两间的相似度。“特征属性相似度矩阵”是一个上三角阵,可作为关系型数据库的一个大对象储存。特征属性相似度和特征权重的初值都由用户在0和1之间设定,并在应用中进行调整。一个实例往往适合不同的设计需求,本文实例的索引采用基于多粒度的表达方法,同一实例可以响应不同设计问题的检索,从而提高了检索的成功率;当前设计问题的描述、实例和规则的索引采用统一的表达机制,耦合度高,便于实例和规则的混合推理。2用户选择相似实例实例检索流程如图1,通过比较“问题描述码”和规则库中各规则的“规则索引码”,计算当前设计问题与每条规则的匹配度,取匹配度最大的N条规则形成规则集供用户确认。通过比较“问题描述码”和实例库中每个实例的“实例索引码”,计算当前设计问题与每个实例的相似度,取相似度最大并符合用户确认的设计规则的前M条实例按相似度由高到低排列形成“实例集”。某一阶段内,检索出的M条实例中包含相似实例的次数与总的检索次数的比值定义为检索成功率,而实例集中第一条实例即为最相似实例的检索次数与总的检索次数的比值,定义为检索准确率。用户选择“实例集”中最符合要求的实例作为设计的起点,系统根据用户的选择动态地调整相关特征的权重和相关特征属性的相似度。“特征集”、“特征属性集”和“规则库”都可以在检索过程中动态地扩充。3特征集和特征属性相似度计算实例库中各实例与当前设计问题的相似度V=∑i=1NQ(Wi×Sim)∑i=1NQWi(1)V=∑i=1ΝQ(Wi×Sim)∑i=1ΝQWi(1)式中:NQ表示问题描述码的长度;Wi为第i个特征的权重;Sim表示当前问题描述码和实例索引码第i位的相似度。Sim=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪1Si(l,k)2×∑n=1NA∑m=nNASi(m,n)NA×(1+NA)Qi∩Ci≠ϕQi∩Ci=ϕ且1≤i≤NCQi∩Ci=ϕ且NC≤i≤NQ(2)Sim={1Qi∩Ci≠ϕSi(l,k)Qi∩Ci=ϕ且1≤i≤ΝC2×∑n=1ΝA∑m=nΝASi(m,n)ΝA×(1+ΝA)Qi∩Ci=ϕ且ΝC≤i≤ΝQ(2)式中:Qi和Ci分别表示问题描述码和实例索引码第i位元素;VQi和VCi分别表示问题描述码和实例索引码第i位元素在相应特征属性集中的序号;l=min(VQi,VCi);k=max(VQi,VCi);Si是第i个特征项所有特征属性间相似度矩阵,m=1,2,3,…,n=1,2,3,…,NA表示该特征项包含的特征属性的个数;NQ和NC分别表示问题描述码和实例描述码的长度,NQ≥NC。特征集和特征属性集动态扩充时,根据式(1)可分析新增特征权重和特征属性相似度对实例检索准确率的影响,当两者的初始值都为0时,影响最平和;初始值越大,影响越激烈。同时为尽量减少应用过程中进行调整的变动量,所以扩充特征集时,把新增特征权重初始为原有特征权重的平均值,新特征项各特征属性相似度的初值由用户给定;扩充特征属性集时,新增特征属性与同一特征项其他特征属性的相似度初始为该特征项各相异特征属性相似度的平均值。当实例库中实例索引码的长度小于问题描述码时,式(2)用新增特征项各特征属性相似度的平均值来近似实例索引码与当前问题描述码该项的相似度,并提醒用户扩展该实例索引码。当某特征的权重小于一阀值(本文取0.001)时,在特征集和特征属性集中删除与该特征项相关的信息,并删除各实例和规则索引码中对应的元素。4规则检索算法如果用户确认规则的结论部分是规范的信息,则用以优化实例的检索,如果规则结论是自由语义信息,也可以满足在线辅助决策的实用要求。产品实例包含若干标准件和标准组合件,一个标准零部件可以表示为一个四元组{nm,st,t,p},其中nm表示该标准件或组合件的名称,st表示该零部件所属的子类的名称,t表示该零部件所属的大类的名称,p表示该零部件的主参数规格,有关标准零部件主参数的确定,参见文献。规则的结论子句记为rc,则利用规则优化实例检索算法如下:(1)类似式(1)、式(2)计算规则库中各设计规则与当前设计问题的匹配度,取匹配度最大的前N条规则形成规则集,用户从中确认与当前设计问题适用的规则(假设N′条)形成用户确认规则集。(2)提取零件实例库和组合件实例库零件与组合件的名称、子类名称和大类名称,分别形成集合NM、ST和T。(3)I表示实例库中实例的个数,Ji表示第i个实例包含的标准零部件的个数,则判断第i条实例是否符合第k条规则的算法流程见图2。图2中条件1为:rc∈NM∪ST∪T或者rc-p∈NM∪ST∪T条件2为:rc=nm|rc=st|rc=t|rc=nm+p|rc=st+p|rc=t+p条件1、2中“-”和“+”分别为字符串的减操作和加操作。符合用户确认规则的实例再根据式(1)和式(2)计算与当前问题相似度,形成实例集,既减小了实例检索的范围,又保证了实例检索的质量。5动态调整算法特征权重的调整是当前CBR研究的热点。在调整权重时,特征评估算法只考虑了实例库中各实例的比较,而反省算法只考虑了当前问题与实例库中各实例的比较,本文综合考虑了实例检索时“当前问题”、“用户选择实例”和“实例集中相似度更高的实例”的比较,提出了动态调整特征权重和特征属性相似度算法。实例集(St)中各实例按与当前问题的相似度由高到低的顺序排列,设用户选择实例为St[J],实例集中若存在比St[J]与当前设计问题更相似的实例,表示为St[j]式中:j=1,2…,J-1。Q、C[J]和C[j]分别表示问题描述码、St[J]和St[j]的实例描述码,Qi、C[J]i和C[j]i分别表示Q、C[J]和C[j]的第i位,VQi、VC[J]i和VC[j]i分别表示Q、C[J]和C[j]第i位元素在相应特征属性集中的序号,则特征权重和特征属性相似度动态调整算法流程见图3。图3中:条件1:C[J]i∩C[j]i=Φ且C[J]i∩Qi≠Φ条件2:C[J]i∩C[j]i=Φ且C[j]i∩Qi≠Φ条件3:C[J]i∩C[j]i=Φ,C[J]i∩Qi=Φ且C[j]i∩Qi=Φ公式(1):Wi=augment(Q,C)×Wi公式(2):Wi=minish(Q,C)×Wi公式(3)∶Si(l,k)={augment(Q,C)×Si(l,k),l=min(VC[J]i,VQi),k=max(VC[J]i,VQi)minish(Q,C)×Si(l,k),l=min(VC[j]i,VQi),k=max(VC[j]i,VQi)公式(3)∶Si(l,k)={augment(Q,C)×Si(l,k),l=min(VC[J]i,VQi),k=max(VC[J]i,VQi)minish(Q,C)×Si(l,k),l=min(VC[j]i,VQi),k=max(VC[j]i,VQi)公式(1)、(2)、(3)中,augment(Q,C)是Q和C的函数,取值范围为(1,2),minish(Q,C)是Q和C的函数,取值范围为(0,1)。本文把augment(Q,C)定义为1+Nne/NQ,把minish(Q,C)定义为1-Nne/NQ,其中Nne表示Q和C不相等的位数,NQ表示Q的位数,以保证调整的快速收敛。在训练阶段,可以用上述算法学习各特征项的权重和特征属性的相似度;在应用过程中,系统支持索引词汇的动态扩充,并能动态地调整特征的权重和特征属性的相似度,从而具有良好的自适应性。6基于实例的匹配规则学习采用本文算法,以大型关系数据库Oracle和高端CAD软件UG为平台,用VC++开发了“基于混合推理的机床夹具设计系统”,见图4。在实例描述过程中,“特征集”和“特征属性集”可以动态扩充。用户确认与当前问题适合的设计规则,系统根据实例与规则匹配判断算法检索得到实例集后,用户利用“实例预览”功能,从实例集中选择最符合要求的实例作为当前设计的起点,系统会根据用户的选择动态地调整相应特征项的权重和特征属性的相似度。该系统已在某大型航空企业成功地应用于国家重点型号工程的研制,算法应用效果分析见表1。由于实例索引采用了基于多粒度的表达方法,同一实例可以响应不同设计问题的检索,同时通过设计规则优化实例的检索,保证了实例检索的成功率。统计发现,用户从规则集中确认的规则平均为2.5条,一般不超过5条,实例集