基于規(guī)則的實例檢索模型

基于實例的推理（rcr），該算法適用于復雜和病態(tài)結構的機械設計問題。此步驟包括實際的表達和存儲、檢索、調(diào)整和學習。其中，示例研究算法的效率和精度是cbr技術的關鍵。最近鄰算法是目前應用最為廣泛的實例檢索算法,但尚存在一些不足:(1)沒有考慮實例的多索引機制。(2)隨著實例庫中實例增加,檢索效率呈線性下降。(3)特征權重和特征屬性相似度都需要由領域專家確定,其他算法如特征評估算法、反省算法和神經(jīng)網(wǎng)絡方法等考慮了特征權重的調(diào)整,但調(diào)整策略有待進一步研究。(4)機械設計實例的索引詞匯的確定是一個NP難題,要求索引詞匯便于擴充,而最近鄰算法和文獻算法都沒有考慮索引詞匯的動態(tài)擴充問題。1生成信息的規(guī)范表達針對以上問題,本文提出了一種基于多粒度的實例和規(guī)則索引統(tǒng)一表達機制,用基于規(guī)則推理(RBR)減小檢索范圍并優(yōu)化實例檢索的質量,支持索引詞匯的動態(tài)擴充和特征權重與特征屬性相似度的動態(tài)調(diào)整,基于多粒度的實例和規(guī)則索引統(tǒng)一表達機制見圖1。實例庫由零件-組合件-產(chǎn)品3層實例庫組成,產(chǎn)品實例的內(nèi)容包括實例號、實例索引碼、實例CAD模型(總體控制結構)和所包含的標準零件、組合件的描述信息或非常用件的名稱和存儲路徑等。規(guī)則的條件子句描述規(guī)則的適用條件,用“規(guī)則索引碼”表示,結論子句可以是規(guī)范的信息,如標準件的名稱、類別,也可以是自由語義信息。定義1特征集:記實例d有n個描述特征項,d={pi},每個描述特征項的當前取值為vi,其中1≤i≤n。對于實例庫中的所有實例,若存在一個最小的整數(shù)I,1≤I≤n,使得d=d′?v1=v′1,v2=v′2,…,vI=v′I,則稱由描述特征項p1,p2,…,pI構成的集合為特征集。即特征集是指能概括實例的主要功能和結構,且能使實例相互區(qū)分的描述特征項的集合。定義2特征屬性集:某一實例描述特征可能取值的集合,特征屬性集與特征集的關系為attribute-of?！疤卣骷焙汀疤卣鲗傩约睒嫵伤饕~匯,用以描述實例和規(guī)則的索引?！皩嵗饕a”和“規(guī)則索引碼”分別是一個序列,序列的各元素用相應“特征項”的“特征屬性代號”以代號(單個“特征屬性代號”)、代號集(部分“特征屬性代號”的并集)或“*”(全部“特征屬性代號”的并集)3種粒度表示?！皢栴}描述碼”的表示方法同“實例索引碼”和“規(guī)則索引碼”類似,但序列的元素只以“代號”和“*”2種粒度表示。本文引入了“特征屬性相似度矩陣”的概念,用以表示某“特征項”的所有“特征屬性”兩兩間的相似度?！疤卣鲗傩韵嗨贫染仃嚒笔且粋€上三角陣,可作為關系型數(shù)據(jù)庫的一個大對象儲存。特征屬性相似度和特征權重的初值都由用戶在0和1之間設定,并在應用中進行調(diào)整。一個實例往往適合不同的設計需求,本文實例的索引采用基于多粒度的表達方法,同一實例可以響應不同設計問題的檢索,從而提高了檢索的成功率;當前設計問題的描述、實例和規(guī)則的索引采用統(tǒng)一的表達機制,耦合度高,便于實例和規(guī)則的混合推理。2用戶選擇相似實例實例檢索流程如圖1,通過比較“問題描述碼”和規(guī)則庫中各規(guī)則的“規(guī)則索引碼”,計算當前設計問題與每條規(guī)則的匹配度,取匹配度最大的N條規(guī)則形成規(guī)則集供用戶確認。通過比較“問題描述碼”和實例庫中每個實例的“實例索引碼”,計算當前設計問題與每個實例的相似度,取相似度最大并符合用戶確認的設計規(guī)則的前M條實例按相似度由高到低排列形成“實例集”。某一階段內(nèi),檢索出的M條實例中包含相似實例的次數(shù)與總的檢索次數(shù)的比值定義為檢索成功率,而實例集中第一條實例即為最相似實例的檢索次數(shù)與總的檢索次數(shù)的比值,定義為檢索準確率。用戶選擇“實例集”中最符合要求的實例作為設計的起點,系統(tǒng)根據(jù)用戶的選擇動態(tài)地調(diào)整相關特征的權重和相關特征屬性的相似度?！疤卣骷?、“特征屬性集”和“規(guī)則庫”都可以在檢索過程中動態(tài)地擴充。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表示該特征項包含的特征屬性的個數(shù);NQ和NC分別表示問題描述碼和實例描述碼的長度,NQ≥NC。特征集和特征屬性集動態(tài)擴充時,根據(jù)式(1)可分析新增特征權重和特征屬性相似度對實例檢索準確率的影響,當兩者的初始值都為0時,影響最平和;初始值越大,影響越激烈。同時為盡量減少應用過程中進行調(diào)整的變動量,所以擴充特征集時,把新增特征權重初始為原有特征權重的平均值,新特征項各特征屬性相似度的初值由用戶給定;擴充特征屬性集時,新增特征屬性與同一特征項其他特征屬性的相似度初始為該特征項各相異特征屬性相似度的平均值。當實例庫中實例索引碼的長度小于問題描述碼時,式(2)用新增特征項各特征屬性相似度的平均值來近似實例索引碼與當前問題描述碼該項的相似度,并提醒用戶擴展該實例索引碼。當某特征的權重小于一閥值(本文取0.001)時,在特征集和特征屬性集中刪除與該特征項相關的信息,并刪除各實例和規(guī)則索引碼中對應的元素。4規(guī)則檢索算法如果用戶確認規(guī)則的結論部分是規(guī)范的信息,則用以優(yōu)化實例的檢索,如果規(guī)則結論是自由語義信息,也可以滿足在線輔助決策的實用要求。產(chǎn)品實例包含若干標準件和標準組合件,一個標準零部件可以表示為一個四元組{nm,st,t,p},其中nm表示該標準件或組合件的名稱,st表示該零部件所屬的子類的名稱,t表示該零部件所屬的大類的名稱,p表示該零部件的主參數(shù)規(guī)格,有關標準零部件主參數(shù)的確定,參見文獻。規(guī)則的結論子句記為rc,則利用規(guī)則優(yōu)化實例檢索算法如下:(1)類似式(1)、式(2)計算規(guī)則庫中各設計規(guī)則與當前設計問題的匹配度,取匹配度最大的前N條規(guī)則形成規(guī)則集,用戶從中確認與當前設計問題適用的規(guī)則(假設N′條)形成用戶確認規(guī)則集。(2)提取零件實例庫和組合件實例庫零件與組合件的名稱、子類名稱和大類名稱,分別形成集合NM、ST和T。(3)I表示實例庫中實例的個數(shù),Ji表示第i個實例包含的標準零部件的個數(shù),則判斷第i條實例是否符合第k條規(guī)則的算法流程見圖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中“-”和“+”分別為字符串的減操作和加操作。符合用戶確認規(guī)則的實例再根據(jù)式(1)和式(2)計算與當前問題相似度,形成實例集,既減小了實例檢索的范圍,又保證了實例檢索的質量。5動態(tài)調(diào)整算法特征權重的調(diào)整是當前CBR研究的熱點。在調(diào)整權重時,特征評估算法只考慮了實例庫中各實例的比較,而反省算法只考慮了當前問題與實例庫中各實例的比較,本文綜合考慮了實例檢索時“當前問題”、“用戶選擇實例”和“實例集中相似度更高的實例”的比較,提出了動態(tài)調(diào)整特征權重和特征屬性相似度算法。實例集(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位元素在相應特征屬性集中的序號,則特征權重和特征屬性相似度動態(tài)調(diào)整算法流程見圖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的函數(shù),取值范圍為(1,2),minish(Q,C)是Q和C的函數(shù),取值范圍為(0,1)。本文把augment(Q,C)定義為1+Nne/NQ,把minish(Q,C)定義為1-Nne/NQ,其中Nne表示Q和C不相等的位數(shù),NQ表示Q的位數(shù),以保證調(diào)整的快速收斂。在訓練階段,可以用上述算法學習各特征項的權重和特征屬性的相似度;在應用過程中,系統(tǒng)支持索引詞匯的動態(tài)擴充,并能動態(tài)地調(diào)整特征的權重和特征屬性的相似度,從而具有良好的自適應性。6基于實例的匹配規(guī)則學習采用本文算法,以大型關系數(shù)據(jù)庫Oracle和高端CAD軟件UG為平臺,用VC++開發(fā)了“基于混合推理的機床夾具設計系統(tǒng)”,見圖4。在實例描述過程中,“特征集”和“特征屬性集”可以動態(tài)擴充。用戶確認與當前問題適合的設計規(guī)則,系統(tǒng)根據(jù)實例與規(guī)則匹配判斷算法檢索得到實例集后,用戶利用“實例預覽”功能,從實例集中選擇最符合要求的實例作為當前設計的起點,系統(tǒng)會根據(jù)用戶的選擇動態(tài)地調(diào)整相應特征項的權重和特征屬性的相似度。該系統(tǒng)已在某大型航空企業(yè)成功地應用于國家重點型號工程的研制,算法應用效果分析見表1。由于實例索引采用了基于多粒度的表達方法,同一實例可以響應不同設計問題的檢索,同時通過設計規(guī)則優(yōu)化實例的檢索,保證了實例檢索的成功率。統(tǒng)計發(fā)現(xiàn),用戶從規(guī)則集中確認的規(guī)則平均為2.5條,一般不超過5條,實例集