基于實(shí)例推理的配置中相似性的研究

高山武，李迎江，朱永彬

紅河學(xué)院，云南 蒙自 661100

推理理論和文法在解決實(shí)際問題的應(yīng)用是當(dāng)前的一個研究熱點(diǎn)，基于實(shí)例推理(Case-Based Reasoning，簡稱CBR)的基本思想在于從以往的成功設(shè)計(jì)中尋找與當(dāng)前問題最為接近的實(shí)例作為問題的初始解，并經(jīng)過對舊的實(shí)例的調(diào)整，使之滿足新問題的要求，從而生成一個當(dāng)前問題的解。由于基于實(shí)例推理與傳統(tǒng)的基于規(guī)則推理的方法主要區(qū)別在于尋找問題解的過程中直接從以往設(shè)計(jì)中吸取經(jīng)驗(yàn)，而不是通過把知識歸納成問題求解的一系列規(guī)則，依靠一定的事件去觸發(fā)規(guī)則來搜索、產(chǎn)生問題的解。然而許多問題領(lǐng)域——譬如機(jī)械系統(tǒng)設(shè)計(jì)的方案設(shè)計(jì)問題的這種規(guī)則的歸納和提取具有很大的難度，使之成為基于規(guī)則推理系統(tǒng)實(shí)現(xiàn)的一個瓶頸，基于實(shí)例推理的文法的實(shí)現(xiàn)為克服這不足提供了可能性。

通常用距離測度法進(jìn)行最相似實(shí)例的評判，這種相似度量的計(jì)算方法沒有從系統(tǒng)的組成要素及相互關(guān)系角度出發(fā)進(jìn)行系統(tǒng)分析，忽視了組成要素的特性的相似性，導(dǎo)致算出的相似系數(shù)不能很好地反映實(shí)例的相似程度，而相似學(xué)經(jīng)過長期研究，形成了完整的相似理論和方法，并用數(shù)學(xué)公式比較準(zhǔn)確地刻畫了兩個相似系統(tǒng)之間的相似程度。本文直接采用相似學(xué)中的相似度計(jì)算公式算出新問題和實(shí)例庫中所有實(shí)例的相似度，再由相似度排序進(jìn)行最相似實(shí)例的檢索，這種方法簡單有效。但在相似度量時，特征屬性的權(quán)重值一般在實(shí)際中很難確定，通常是在先驗(yàn)知識的基礎(chǔ)上通過事先假設(shè)或是采用平權(quán)的辦法來處理，這種權(quán)重值的處理方法都無法證明其正確性，無疑會給最相似實(shí)例檢索的準(zhǔn)確性造成影響，必須先解決這個問題，這就要用到粗集理論，對特征集進(jìn)行約簡。粗集(Rough Set)理論是從知識分類的角度出發(fā)的一種新的數(shù)據(jù)推理方法，主要用于知識的約簡和屬性依賴性的分析。用粗集理論處理相似度量中屬性權(quán)重值問題，可以不用事先假定的信息，只利用已有的信息來判斷所有的屬性，在特定的分類下是否具有同等的重要性，某個特征性的重要性也就是重要程度該特征屬性在相似配置中的權(quán)重。

1 系統(tǒng)相似及相似度

相似學(xué)并不是現(xiàn)代產(chǎn)生的，早期人們在探索自然規(guī)律的過程當(dāng)中，就已經(jīng)逐漸形成了研究相似現(xiàn)象的方法和理論。牛頓、柯西(Cauchy)等都曾把相似模型成功的應(yīng)用于工程問題。相似三定理則奠定了相似理論的理論基礎(chǔ)。周美立在《相似學(xué)》、《相似系統(tǒng)論》兩部著作中，建立了新的學(xué)科——相似學(xué)(Similology)，研究自然界中相似現(xiàn)象的本質(zhì)，相似性形成原理和演變動力，系統(tǒng)相似的一般規(guī)律及其應(yīng)用。相似學(xué)的基本概念定義：相似要素指兩個或兩個以上系統(tǒng)間存在著共有屬性或特征，在數(shù)值上存在著差異。將這些共有屬性和特征稱為相似屬性或相似特征，通稱為相似要素。

相似元：系統(tǒng)間存在一個相似要素，便在系統(tǒng)間構(gòu)成一個相似單元，簡稱相似元，計(jì)作：

通過計(jì)算相似元的數(shù)值量化相似要素的相似程度。設(shè)A、B兩個系統(tǒng)間某個相似元具有m個特征，計(jì)Uj(ai)為要素ai對于第j個特征的特征值，Uj(bi)為要素bi相對于第j個特征的特征值。其比例系數(shù)，其中各特征值可以為確定的數(shù)，也可以為一個模糊數(shù)。

相似元的數(shù)值：

式（1）中ui為系統(tǒng)間第i個相似元，wij為第i個相似元中第j個特征的權(quán)重。

相似系統(tǒng)A、B間的相似程度則由相似度QA-B表示，相似度的計(jì)算公式為：

式（2）中：k，l——A、B系統(tǒng)的要素個數(shù)；n——相似元的個數(shù)；βi——第i個相似元的權(quán)重。式中項(xiàng)表示系統(tǒng)間相似元個數(shù)對系統(tǒng)相似度的影響。βiq(ui)項(xiàng)表示第i個相似元數(shù)值對系統(tǒng)相似度的影響。

2 特征集的約簡（粗集理論的應(yīng)用）

分析基于實(shí)例推理的實(shí)例檢索是根據(jù)新問題的描述進(jìn)行模式匹配的過程，新問題常常被定義成一組特征屬性，檢索的目標(biāo)就是從相似實(shí)例庫中找出一個最相似的實(shí)例。其檢索過程是先根據(jù)新問題的初始條件中提取特征屬性作為檢索目標(biāo)，再用新問題的特征屬性值和相似實(shí)例集中的每個實(shí)例對應(yīng)的特征屬性進(jìn)行相似度量，算出相似度的大小，找出相似度最大的實(shí)例就是最相似的實(shí)例。

相似度量時實(shí)例的各特征屬性所起的作用是不同的，有的起關(guān)鍵作用，有的作用很小，甚至不起作用，而且這種作用的重要性會隨著分類的改變而變化。在進(jìn)行某一分類檢索時，利用粗集理論能夠算出實(shí)例屬性重要程度，并且可以根據(jù)這種重要程度對各個公有相似特征屬性的權(quán)重值賦值，如果某些特征屬性被認(rèn)為沒有起到預(yù)期作用，干擾了實(shí)例檢索，可以將其刪除。

采用粗集理論的知識表達(dá)系統(tǒng)S=(U，A)來表示實(shí)例，其中，U為非空的有限論域，在實(shí)例庫中是所有實(shí)例的集合；A為非空的屬性有限集，包含條件屬性C和決策屬性D，即C∪D=A，C∩D= φ，C中某一屬性a∈A，Va是屬性a的值域。

實(shí)例集的屬性一般均為定性屬性，對于定量分析問題可以先采用離散處理，變成定性問題，然后再用粗集理論進(jìn)行處理。屬性的重要性可以用以下兩個公式來進(jìn)行判斷，即

去掉屬性以后，為

其中，card (·)表示集合的基，用rC-a(D)來判斷某一屬性a的重要程度，當(dāng)從條件屬性中去掉屬性a以后再對庫中實(shí)例進(jìn)行分類時，分類U/D的正定域?qū)⑹艿捷^大影響。

3 權(quán)重的確定及相似度計(jì)算實(shí)例

以集裝箱大車行走機(jī)構(gòu)為例，我們?nèi)∑渲械?個屬性進(jìn)行討論。在進(jìn)行實(shí)例檢索并建立不同的索引時，對應(yīng)的實(shí)例中各屬性的重要性會有較大差別，如表1。

表1 大車實(shí)例定量特征屬性表

假設(shè)從實(shí)例庫中檢索1組相似實(shí)例特征屬性參數(shù)，論域U由編號為1～5的實(shí)例組成，現(xiàn)對5個實(shí)例的定量屬性進(jìn)行粗略的離散處理，使其變成定性屬性，離散處理結(jié)果見表2所列。其中，C={a，b，c}，D=j5i0abt0b，屬性 a、b、c中的定性值域0、1、2分別代表各屬性的不同定量范圍，決策屬性d是建立索引時根據(jù)動力性能優(yōu)劣劃分的分類，其中，0代表好，1代表一般，2代表較差。

表2 大車實(shí)例定性特征屬性表

根據(jù)(3)式、(4)式，則有

從分析結(jié)果可以看出屬性b和c對于建立的性能索引是重要的，它將U/D的正域改變得最多，去掉它將不能把3、4實(shí)例劃入UD的性能分類。因此，屬性(b，c)是按性能分類時最重要的兩個屬性。由于屬性a對于UD的正域改變不明顯，可以在相似度量時將其去除。按屬性(b，c)分別計(jì)算所有庫中實(shí)例和新問題的相似度大小，根據(jù)（1）式，n=k=l=3，β1=β1=1/2，設(shè)有新問題的描述向量為

將屬性a去除后變?yōu)?/p>

通過檢索和相似度量，確定了實(shí)例3所對應(yīng)的大車特征屬性和設(shè)計(jì)的大車特征屬性相似度最大，可以調(diào)用對應(yīng)的相關(guān)資料作為設(shè)計(jì)參考依據(jù)。

[1]劉長毅，徐誠.機(jī)械方案設(shè)計(jì)中實(shí)例檢索相似性的研究[J].計(jì)算機(jī)應(yīng)用，2000，8：1093-1095.

[2]劉曉冰，董建華.產(chǎn)品配置中相似實(shí)例模糊優(yōu)選法的研究[J].高技術(shù)通訊，2003，2：65-69.

[3]王玉，邢淵，朱莉萍，阮雪榆.支持重用的層次智能CBR檢索模型[J].機(jī)械科學(xué)與技術(shù)，2000，19：164-168.

[4]周美立.相似學(xué)[M].北京：中國科學(xué)技術(shù)出版社，1993：11-32.

[5]周美立.相似系統(tǒng)論[M].北京：科技文獻(xiàn)出版社，1994：27-42.

[6]駱敏舟，周美立.基于特征參數(shù)度量的相似系統(tǒng)設(shè)計(jì)及其應(yīng)用[J].機(jī)械設(shè)計(jì)與研究，2001，3：11-13.

[7]譚建榮，李濤，戴若夷.支持大批量定制的產(chǎn)品配置設(shè)計(jì)系統(tǒng)的研究[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)黨報(bào)，2003，15（8）：931-937.