陳萬付

（滁州廣播電視大學(xué)，安徽 滁州 239000）

案例推理中的案例檢索技術(shù)研究

陳萬付

（滁州廣播電視大學(xué)，安徽 滁州 239000）

案例推理（Case－Based Reasoning，簡稱CBR）是一種基于經(jīng)驗(yàn)知識進(jìn)行推理的人工智能方法，是對人類認(rèn)知過程的一種模擬。本文在傳統(tǒng)歐氏距離算法的基礎(chǔ)上結(jié)合了模糊數(shù)學(xué)的計(jì)算方法，提高了推理的效率，克服了傳統(tǒng)的只能對確定性指標(biāo)進(jìn)行搜索的缺陷。

案例推理；檢索；相似度

1 案例推理的基本原理和流程

基于案例的推理是近十幾年來人工智能中發(fā)展起來的一種重要的推理模式，是一種基于經(jīng)驗(yàn)知識進(jìn)行推理的人工智能方法，是對人類認(rèn)知過程的一種模擬。它的基本原理是：以實(shí)例或累積的經(jīng)驗(yàn)作為儲(chǔ)存知識的基礎(chǔ)，建立實(shí)例庫，對面臨的新問題加以定義及描述，通過搜索實(shí)例庫中過去同類問題的求解過程與結(jié)果，找到合適的實(shí)例作為解決新問題的參考，并以“模擬”、“轉(zhuǎn)換”、“調(diào)整”、“合并”等手法修改原有的解決方案以適應(yīng)新的情景。基于案例的推理的流程如圖1所示。

在此過程中，案例檢索是案例推理中的重要一環(huán)，其實(shí)質(zhì)上就是要在用戶給出案件之后，檢索系統(tǒng)能夠自動(dòng)地從案例庫中找出用戶所指定的方面與案件完全相同或相似度最大的案例來，而且要求輸出結(jié)果能按符合用戶的要求的程度進(jìn)行排序，符合提問程度高的優(yōu)先輸出。

2 案例的檢索

案例檢索，實(shí)質(zhì)上就是要在用戶給出案件之后，檢索系統(tǒng)能夠自動(dòng)地從案例庫中找出用戶所指定的方面與案件完全相同或部分相同的案例來，而且要求輸出結(jié)果能按符合用戶的要求的程度進(jìn)行排序，符合提問程度高的優(yōu)先輸出［1］。

2.1 案例檢索常用方法

案例檢索過程分為案例的索引和案例的檢索。案例的索引技術(shù)通常有三種：最近相鄰法、歸納推理法和知識引導(dǎo)法［2］。單獨(dú)使用以上每種策略都會(huì)有各自明顯的不足，。案例的檢索與案例的索引相對應(yīng)，分為三種：相聯(lián)檢索、層次檢索和基于知識的檢索。其中相聯(lián)檢索與案例索引的最近鄰法相對應(yīng)。該算法檢查目標(biāo)案例與案例庫中的案例的某種屬性的匹配程度，計(jì)算各屬性匹配程度的加權(quán)和，依此決定最佳匹配案例。在眾多最近鄰法的案例檢索方法中，傳統(tǒng)的、目前用得最多的相似度計(jì)算方法是歐氏距離。

圖1 基于案例的推理的流程

2.2 傳統(tǒng)的歐拉算法

KNN法是指從案例庫中找出與目標(biāo)案例最相似案例的方法。檢索前先為案例的各個(gè)特征屬性分別指定權(quán)值，檢索時(shí)根據(jù)輸入案例中特征屬性的權(quán)值與案例庫中各屬性的匹配程度計(jì)算相似度Sim?；蛘甙凑障嗨贫榷x公式計(jì)算出目標(biāo)案例與案例庫中所有案例間的相似值，然后從中選出距離最小的案例作為最佳目標(biāo)案例。

定義1 相似度是指兩個(gè)案例的相似程度。設(shè)案例X，K的相似度用Sim（X，K）表示，Sim（X，K）∈［0，1］，且滿足條件：

（1）對稱性，Sim（K，X）≤Sim（X，K）；

（2）自反性，Sim（X，K）＝1；

定義2 假設(shè)案例

其中

在（2）中，當(dāng)r＝2時(shí)，即Dist（X，K）為歐拉距離。

歐拉距離的相似度定義如（3）所示，其中D（X，Y）的計(jì)算見（2）。

（4）式中Xij代表第i個(gè)案例的第j個(gè)屬性值，Wj表示第j個(gè)屬性的權(quán)重，n為屬性總數(shù)，Kj為目標(biāo)案例K的第j個(gè)屬性的值。Sim（X，K）為目標(biāo)案例K與源案例庫中第i個(gè)案例之間的歐氏距離，Sim（X，K）越小說明它們之間越相似。

2.3 案例的混合檢索

據(jù)上文知，目前常用的案例的索引算法主要有最近相鄰法、歸納推理策略和知識導(dǎo)引法三種。其中最近相鄰法的核心思想是計(jì)算案例間的相似度，找出一個(gè)或多個(gè)最大相似度的案例作為其檢索結(jié)果。使用這種方法時(shí)，首先計(jì)算目標(biāo)案例與舊案例對應(yīng)屬性之間的相似度，然后再根據(jù)屬性的權(quán)值計(jì)算出案例之間的相似度［3］。故本文首先選擇使用最近相鄰法，又鑒于在各種選擇案例中，描述案例特征的屬性很多，且有的特征屬性在不同的案例里會(huì)有不同的權(quán)重值，因此，本文同時(shí)也使用了改進(jìn)TC相似法來檢索最優(yōu)案例。

由于案例庫中存儲(chǔ)的案例的數(shù)量眾多，如果需要計(jì)算案例庫中每一個(gè)案例與新問題的相似度，工作量會(huì)很大，同時(shí)很大一部分計(jì)算是沒必要的。為了減少計(jì)算量，在進(jìn)行相似度計(jì)算之前，先對案例庫進(jìn)行處理，得到候選案例集合，這可以很大的提高案例檢索的效率。此即為案例的檢索，它常用的方法有三種：相聯(lián)檢索、層次檢索和基于知識的檢索。本文選擇與最近相鄰法相對應(yīng)的案例檢索方法，相聯(lián)檢索。本文的案例庫將每個(gè)案例合作項(xiàng)目設(shè)為該案例的作業(yè)類別字段，并將案例的作業(yè)類別作為第一檢索條件。同時(shí)由于案例庫采用關(guān)系數(shù)據(jù)庫技術(shù)存儲(chǔ)，可將案例特征的第一描述符作為第二檢索條件。在出現(xiàn)新問題時(shí)本文可以利用搜索語句對眾多的案例先后進(jìn)行兩次檢索，找出與新問題在這兩個(gè)檢索條件上相匹配的關(guān)聯(lián)案例，形成候選案例集合。

（1）對數(shù)據(jù)進(jìn)行歸一化處理

對數(shù)據(jù)進(jìn)行歸一化處理，即把案例屬性值按照某種函數(shù)歸一化到某一無量綱區(qū)間，并將所有相關(guān)特征屬性歸一化到同一量級內(nèi)，以便計(jì)算結(jié)果能更準(zhǔn)確地反映源案例與目標(biāo)案例間的匹配度。為了使計(jì)算結(jié)果更為準(zhǔn)確，本文引入一種歸一化效用函數(shù)，將不同量綱的原始特征屬性值轉(zhuǎn)換到［－1，1］區(qū)間，同時(shí)盡可能將特征屬性值轉(zhuǎn)換成與原始屬性值成正比關(guān)系的值。

設(shè)S＝（S1，S2，…，Sm－1，Sm）是源案例集，C＝（C1，C2，…，Cm－1，Cn）是案例的屬性集，構(gòu)造特征屬性矩陣：

上式中Xij代表第i個(gè)案例的第j個(gè)屬性值。

記第i個(gè)特征屬性的平均值為ˉCj，j＝1，2，…，n，中間變量為Mij，有：

根據(jù)文獻(xiàn)［2］將原始特征屬性值轉(zhuǎn)換到［－1，1］區(qū)間上的效用函數(shù)為X′ij，令Xij＝X′ij，可得歸一化效用函數(shù)為：

Yij＝F（Mij）是一條曲線，其中Mij反映了原始數(shù)據(jù)Xij與均值的偏離程度：

當(dāng)Xij＝時(shí)候，Mij＝0；

Although it is established that low educational level is associated with low participation rates in CRC screening programs, the results of this study indicate that those with high educational level exhibited less compliance as compared to those of low-intermediate one.

當(dāng)Xij＞時(shí)候，Mij＞0，此時(shí)Yij隨著Mij的增長而非線性遞增；

當(dāng)Xij＜時(shí)候，Mij＜0，此時(shí)Yij隨著Mij的增長而非線性遞減。

通過進(jìn)一步的研究發(fā)現(xiàn)，當(dāng)Xij＞時(shí)，經(jīng)過轉(zhuǎn)換后其效用函數(shù)值Yij大于0，原始值越大效用函數(shù)值越大，當(dāng)原始值Xij＝時(shí)，效用函數(shù)值Yij達(dá)到0.9以上，Xij＞4時(shí)，效用函數(shù)值Yij接近上限值1。同理，當(dāng)Xij＜時(shí)，經(jīng)過轉(zhuǎn)換后其效用函數(shù)值Yij小于0，原始值越大效用函數(shù)值越小，當(dāng)原始值Xij＝－時(shí)，效用函數(shù)值Yij達(dá)到－0.9以下，Xij＜時(shí)，效用函數(shù)值Yij接近下限值－1。

（2）特征屬性的分類及其對應(yīng)的相似度計(jì)算方法

結(jié)合選擇案例的特點(diǎn)，將其特征屬性分為三類：確定數(shù)字屬性集（如79%、29%等）、確定符號屬性集（如是，不是，有，沒有等）和模糊概念屬性集［3］。不同類型屬性之間的相似度采用不同的計(jì)算方式。具體做法如下：

1）確定的數(shù)字屬性值：該種屬性值可以是連續(xù)的，也可以是離散的，相似度計(jì)算方法為：

式中，max（i）和min（i）分別表示存儲(chǔ)在數(shù)據(jù)庫中的經(jīng)驗(yàn)值，由專家組確定，代表一般情況下該屬性的取值范圍。起著將特征屬性間的絕對差值轉(zhuǎn)為相對差值的作用。當(dāng)難以確定時(shí)，可簡單地由專家確定兩者之差為一正實(shí)數(shù)k。

2）確定符號屬性值：該種屬性值通常用明確的術(shù)語表示，如“是”或“不是”、“有”或“沒有”等。此種數(shù)值的相似度計(jì)算為：

3）模糊概念屬性值：該種屬性值可以認(rèn)為是一概念變量，所有這樣的屬性值可構(gòu)成一項(xiàng)目集［4］。項(xiàng)目集中，每一項(xiàng)目對應(yīng)一模糊概念。模糊關(guān)系和模糊數(shù)可以用高斯函數(shù)表示，為了簡化計(jì)算，這里采用基于梯形的模糊集合來模擬模糊屬性［5］，其函數(shù)為：

所以模糊集的隸屬函數(shù)為：

式中c，c′，p是參數(shù)，一般由領(lǐng)域?qū)＜掖_定。

通過計(jì)算兩個(gè)隸屬函數(shù)對應(yīng)余弦的夾角作為模糊集之間的相似度，具有既準(zhǔn)確又簡單的優(yōu)點(diǎn)。計(jì)算公式為：

（3）最終相似度的計(jì)算

為了提高基于案例推理的供應(yīng)鏈合作伙伴選擇案例檢索的準(zhǔn)確性，本文結(jié)合使用了最鄰近法和改進(jìn)TC相似法計(jì)算源案例與目標(biāo)案例之間的相似度。具體過程為：

①判斷目標(biāo)案例與源案例各個(gè)指標(biāo)的權(quán)重是否一樣，一樣則按②計(jì)算最終相似度，如不一樣則據(jù)③計(jì)算最終相似度。

②據(jù)最鄰近法的相似度定義計(jì)算案例之間的相似度。按照上述按照上述不同的計(jì)算方法將各個(gè)不同種類的特征屬性的相似度Sim0（xi，yi）求出，代入式（11）即可得到源案例和目標(biāo)案例的相似值。

式中，wi為各屬性的權(quán)重。∑wi＝1初始默認(rèn)權(quán)重由專家評估法給出，如表3－3所示，使用過程中不滿足時(shí)可以調(diào)整。

③據(jù)改進(jìn)TC相似法的相似度定義計(jì)算案例之間的相似度。因?yàn)槟繕?biāo)案例與源案例之間指標(biāo)的權(quán)值不一樣，故不能直接使用上述不同類型屬性的計(jì)算方法計(jì)算各指標(biāo)之間的相似度。本文為了減少案例檢索的計(jì)算量，減輕系統(tǒng)的負(fù)荷，直接對目標(biāo)案例與源案例的權(quán)值進(jìn)行處理，求其平均值，然后按照上述的計(jì)算方法求出各個(gè)不同種類的特征屬性的相似度Sim1（xi，yi），代入式（12）即可求得源案例和目標(biāo)案例的最終相似度。

其中，是第i個(gè)指標(biāo)在案例X中的權(quán)值，是第i個(gè)指標(biāo)在案例G中的權(quán)值

本文的案例檢索算法如圖2所示：

圖1 案例檢索算法的流程

從候選案例集中選出相似度最大的案例，此案例即為搜索得到的最優(yōu)案例。

實(shí)踐證明，本文案例檢索克服了傳統(tǒng)算法只能對確定性指標(biāo)進(jìn)行計(jì)算的缺陷，將傳統(tǒng)算法和模糊集的計(jì)算方法相結(jié)合，大大提高了檢索的準(zhǔn)確性。

［1］王永成.案例檢索的若干問題［J］.情報(bào)學(xué)報(bào)，2000，19（6）：587－591.

［2］欒好利，張翼英，曾 文.基于案例推理的技術(shù)研究［J］.沈陽工程學(xué)院學(xué)報(bào)，2005，1（2、3）：95－97.

［3］王建成，李 寧，吳曉明.基于CBR的自行火炮故障診斷系統(tǒng)設(shè)計(jì)［J］.2006中國控制與決策學(xué)術(shù)年會(huì)論文集，2007.

［4］倪志偉，李學(xué)俊，胡彩平，等.基于范例和規(guī)則相結(jié)合的推理技術(shù)［J］.小型微型計(jì)算機(jī)系統(tǒng)，2004，25（7）：1156－1159.

［5］雷 萍.基于案例推理的供應(yīng)鏈合作伙伴選擇與評價(jià)［J］.集團(tuán)經(jīng)濟(jì)研究，2007：313－314.

［6］楊 健，趙秦怡.基于案例的推理技術(shù)研究進(jìn)展及應(yīng)用［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（3）：710－713.

［7］劉伯超.供應(yīng)鏈合作伙伴選擇指標(biāo)體系研究［J］.現(xiàn)代企業(yè)文化，2008：28－29.

［8］喬 忠，陳新輝.關(guān)于企業(yè)銷售量的模糊預(yù)測［J］.中國管理科學(xué)，2001，9（6）：31－35.

［9］戴聞戰(zhàn).基于三層BP網(wǎng)絡(luò)的多指標(biāo)綜合評估方法及應(yīng)用［J］.系統(tǒng)工程理論與實(shí)踐，1999，5（5）：30－34.

The Research of Case Retrieval in Case-Based Reasoning Technology

Chen Wanfu

Case－Based Reasoning is a kind of artificial intelligent design method of reasoning the experiencial knowledge，and it is also a kind of imitation of human cognitive process.Based on traditional Euclidean Distance Transform，this paper combines computing method of fuzzy mathematics，raises the efficiency of reasoning，and overcomes traditional defect of only searching deterministic index.

case reasoning；retrieval；similarity

C931.2

A

1673-1794（2012）05-0014-03

陳萬付（1969－），男，安徽滁州人，講師，管理學(xué)碩士，主要研究方向：中小企業(yè)管理。

2012-08-11