一種改進的CBR案例檢索相似性度量模型

［摘 要］ 案例相似性度量是基于案例推理（CBR）的突發事件應急決策管理的關鍵問題。本文基于最近鄰算法，提出一種改進的案例相似性度量模型。提出“結構相似度”度量缺失數據對于案例結構特征相似性的影響，引入“變異系數”度量案例屬性的可替代性，精確描述替代程度不同的屬性對于案例相似性的貢獻。最后通過具體案例檢索實例驗證了該模型的有效性。

［關鍵詞］ 應急決策； 基于案例推理； 案例檢索； 相似性度量

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2011 . 09 . 013

［中圖分類號］TP18；TP315 ［文獻標識碼］A ［文章編號］1673 - 0194（2011）09- 0050 - 06

１引言

案例推理（Ｃａｓｅ－Ｂａｓｅｄ Ｒｅａｓｏｎｉｎｇ， ＣＢＲ）技術廣泛應用于突發事件應急決策，可結合歷史相似案例的經驗知識解決現有問題，有效降低知識獲取難度，并通過不斷加入新案例進行自主學習，適合于知識難以獲取但已積累了豐富案例經驗的諸多復雜領域［１］。

基于案例推理的應急決策模型可劃分為案例檢索、案例重用、案例修正和案例保存等4個階段［２］。案例檢索是其中的關鍵步驟，目的是根據目標案例的特征描述，從案例庫中查找與之最相似的案例，常用案例檢索方法為最近鄰法。實際應用中案例庫數據類型多變，屬性間關系復雜，多出現屬性值缺失現象，需針對這些現象構造合理的案例相似性度量模型。

案例相似性度量模型包括屬性局部相似性和案例全局相似性。屬性局部相似性指案例在各屬性上的相似性，應急案例屬性數值類型可分為連續型、分類型、模糊數或模糊區間型等，需根據不同數據類型規定相應的屬性局部相似性度量。其中針對模糊數及模糊區間型數據進行相似性度量是難點問題，人們通常采用區間平均相似度［３，４］、長度面積重疊率［５］、義類詞典［６］等對其進行相似性度量。

案例全局相似性綜合考慮各屬性局部相似性、屬性權重等要素，是案例檢索的根本依據。應急案例常見的全局相似性（差異度）度量為屬性局部相似性（差異度）的加權值，如加權Ｅｕｃｌｉｄｅａｎ距離，加權Ｈａｍｍｉｎｇ距離等［７］。此外，也有學者將粗糙集［８］、模糊數及語義距離［９］、神經網絡［１０］等技術引入案例全局相似度計算中。這些相似性度量模型均假設描述案例的各屬性相互可替代，且未考慮缺失值屬性對案例結構特征相似性的影響。

本文首先介紹基于最近鄰算法的案例檢索方法，隨后提出一種改進的案例全局相似性度量模型，精確描述缺失數據及屬性替代關系對于案例全局相似性的貢獻，最后以洪澇災害實例驗證新度量模型的有效性。

２基于最近鄰的案例檢索方法

Ｋ最近鄰（Ｋ－Ｎｅａｒｅｓｔ Ｎｅｉｇｈｂｏｒ Ａｌｇｏｒｉｔｈｍ，ＫＮＮ）算法是最常用的ＣＢＲ案例檢索方法。它將案例的特征矢量看作高維空間中的點，然后在問題空間中尋找與目標案例相匹配的點，將超過相似度閾值的案例返還給用戶，其一般過程描述如下［１１］：

３改進的案例相似性度量模型

在基于最近鄰算法的突發事件案例檢索過程中，案例通常具有數據類型多樣、缺失數據較多、屬性間關系復雜等特點。傳統案例相似性度量模型已針對不同數據類型，設計了不同的屬性局部相似性度量方法，但均未充分考慮缺失數據及屬性關系對案例間相似性的影響。

傳統案例相似性度量模型通常將缺失數據的屬性剔除，使其不參與案例相似度的計算。這種處理方式改變了案例屬性的結構特征，剔除權重較高與較低的屬性對于案例全局相似度的有效性顯然具有不同的影響。此外，傳統案例相似性度量模型假設屬性間相互獨立，屬性間可相互替代，但在實際應用中屬性間往往不可相互替代，或在一定范圍內存在非線性替代關系。例如一件質料優秀但樣式很差的衣服對于消費者的吸引力不會強于一件質料良好且樣式良好的衣服，即質料的優秀并不能彌補樣式上的缺憾。

３．１改進的案例相似性度量模型定義

目標案例Ｔ與案例庫中源案例Ｒ，由ｍ個屬性描述，即Ｔ ＝ ｛ｔ１，ｔ２，…，ｔｍ｝，Ｒ ＝ ｛ｒ１，ｒ２，…，ｒｍ｝，各屬性權重為ｗ（ｊ），ｊ ＝ １，２，…，ｍ，則Ｔ與Ｒ間改進的案例相似性度量ＳＩＭｎｅｗ（Ｔ，Ｒ）可定義為：

其中，ωｔ，ｒ表示案例Ｔ與案例Ｒ的結構相似度，描述了缺失數據對于相似度的影響程度，αｔ，ｒ表示案例Ｔ與案例Ｒ的屬性可替代程度，ｓｉｍ（ｔｊ，ｒｊ）表示案例Ｔ與案例Ｒ在屬性ｊ上的局部相似度。

Ｔ與Ｒ間改進的案例相似度ＳＩＭｎｅｗ（Ｔ，Ｒ）和屬性局部相似度ｓｉｍ（ｔｊ，ｒｊ）的取值范圍均為［０，１］，取值越高說明目標案例Ｔ與源案例Ｒ間相似程度越高。

３．２改進的案例相似性度量模型解析

依據改進案例相似度的定義可知，改進案例相似度包含案例間結構相似度、屬性替代性度量、屬性局部相似性度量和屬性權重等4部分。

３．２．１結構相似度

目標案例Ｔ與案例庫中源案例Ｒ的結構相似度ωｔ，ｒ計算過程如下：

（１） 計算案例Ｔ所有非空屬性集合，記為ＡＴ；

（２） 計算案例Ｒ所有非空屬性集合，記為ＡＲ；

（３） 計算ＡＴ與ＡＲ的交集和并集，分別記為ＩＴ，Ｒ和ＵＴ，Ｒ；

（４） 計算ＩＴ，Ｒ中所有屬性權重之和，記為ωＩ；

（５） 計算ＵＴ，Ｒ中所有屬性權重之和，記為ωＵ；

（６） 則案例Ｔ與Ｒ的結構相似度ωｔ，ｒ定義為：

當案例Ｔ與Ｒ的屬性空間未出現缺失值時，結構相似度ωｔ，ｒ為１；當缺失值出現在權重較高的屬性中時，計算案例相似度的有效性降低。結構相似度的作用在于將其客觀反映在案例相似度計算結果中。

３．２．２屬性替代性度量

衡量屬性間替代程度的重要途徑是考察屬性間的差異性，因此引入統計學中綜合反映總體各單位之間差異程度的指標——變異指標，用以量化屬性之間的可替代性。屬性間差異程度越大，說明屬性間越不易被替代。

目標案例Ｔ與案例庫中源案例Ｒ的可替代性程度計算公式為：

其中，αｔ，ｒ為目標案例Ｔ與案例庫中源案例Ｒ屬性變異指標，Ｘｔ，ｒ為案例Ｔ與Ｒ屬性局部相似度的平均值，σｔ，ｒ為案例Ｔ與Ｒ加權形式下的屬性局部相似度均方差。

案例屬性差異程度越高，屬性間可替代程度越低，由這些屬性所描述的案例間相似度越低。

３．２．３屬性局部相似度

應急案例數據類型復雜多樣，案例Ｔ與Ｒ進行匹配時，需針對不同數據類型定義相應的屬性局部相似度。

（１） 連續型：連續型變量較為常見，例如產品單價、產品次品率等，其局部相似性度量定義為：

其中，ｔｊ，ｒｊ分別表示案例Ｔ和Ｒ在屬性ｊ上的取值，α，β表示該屬性的取值上界和下界。

（２） 分類型：分類型變量取值離散，包括布爾型變量，例如產品類型，其局部相似性度量定義為：

ｓｉｍ（ｔｊ，ｒｊ） ＝ １ ｔｊ ＝ ｒｊ０ ｔｊ≠ｒｊ （６）

（３） 模糊數型：模糊數包括三角模糊數、梯形模糊數、降半梯形模糊數等。例如，采購人員根據以往的采購情況，認為交貨提前期至少ａ１天，至多ａ４天，且在ａ２~ａ３天的可能性最大，可表示為梯形模糊數（ａ１，ａ２，ａ３，ａ４）。案例Ｔ和Ｒ在屬性ｊ上的取值分別為ｔｊ ＝ （ｔｊ，１，ｔｊ，２，ｔｊ，３，ｔｊ，４）和ｒｊ ＝ （ｒｊ，１，ｒｊ，２，ｒｊ，３，ｒｊ，４），其局部相似性度量可定義為：

① 若ｔｊ，１≤ｔｊ，２≤ｔｊ，３≤ｔｊ，４≤１且ｒｊ，１≤ｒｊ，２≤ｒｊ，３≤ｒｊ，４≤１，可使用Ｃｈｅｎ提出的ＳＣＧＭ法，即：

② 若ｔｊ，１≤ｔｊ，２≤ｔｊ，３≤ｔｊ，４且ｒｊ，１≤ｒｊ，２≤ｒｊ，３≤ｒｊ，４，使用隸屬度平均積分代表法（Ｇｒａｄｅｄ Ｍｅａｎ Ｉｎｔｅｇｒａｔｉｏｎ－ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ Ｄｉｓｔａｎｃｅ）來計算相似度：

ｓｉｍ（ｔｊ，ｒｊ） ＝ （１ ＋ Ｐ（ｔｊ） － Ｐ（ｒｊ））－１（８）

３．２．４屬性權重確定

本文利用結構方程，即驗證性因子分析的思想對案例屬性進行分析，并以計算所得的權重的絕對值作為屬性的權重。

４實例數值分析

４．１實例背景

本文應用防汛應急決策實例來說明改進案例相似性度量模型的有效性。案例庫中有１０個防汛應急案例（見表１，Ｃ１~Ｃ１０），由３０個屬性（ａ１~ａ３０）描述（屬性說明見表２）。 屬性空間中ａ１~ａ２描述案例基本信息，ａ３~ａ５描述案例類型信息，ａ６~ａ１５為案例環境信息，ａ１６~ａ３０描述案例問題信息（略去庫中案例解決方案及決策評價信息）。

當前應急事件：安徽某市突降暴雨，風力等級為５，災害等級為ＩＩＩ級，可控程度中等，已造成中等程度的損失，對水電和交通造成了影響。

結合當地相關歷史記錄，對于該事件進行形式化表示，得到目標案例Ｔ。案例Ｔ的類型、環境和問題信息（即ａ３~ａ30）分別為：｛自然危害，洪澇危害，山洪暴雨洪澇，安徽，長江流域，中，雨，２００~３００，５，ｎｕｌｌ，丘陵，中，ｎｕｌｌ，暴雨，ＩＩＩ， ｎｕｌｌ， ｎｕｌｌ， ＩＩ， ｎｕｌｌ，中，中，低，是，否，是， ｎｕｌｌ， ｎｕｌｌ， ｎｕｌｌ ｝。

依據本文提出的案例間改進相似性度量，在案例庫中進行案例檢索，輸出與目標案例最相似的案例。

４．２實例數值實驗結果及分析

應用本文提出的改進案例相似度模型，計算目標案例Ｔ與源案例間的相似性。利用公式（５）~（８）計算目標案例與各源案例間的屬性局部相似度（見表３“Ｃ１~Ｃ１０列”）。

本文應用結構方程確定各屬性權重，由于相似度計算涉及案例類型、環境、問題信息等２８個屬性，其中類型、環境信息的屬性相同，即均為０．０３５ ７１４，而問題信息的１５個屬性權重則各不相同，運用結構方程模型分析軟件ＡＭＯＳ １７．０對結構方程進行５００ ＋ ６５ ５００次迭代，得到權重結果見表３，結果收斂值（Ｃ．Ｓ．）為１．０２５ ０，Ｇｅｌｍａｎ論證如果該值滿足１≤Ｃ．Ｓ．≤１．１０，則可認為該模型是可接受的。

根據公式（４）計算案例間屬性替代性程度，根據公式（３）計算案例間結構相似度，計算結果見表３。目標案例中存在８個空缺值，但源案例中信息十分完整，因此目標案例與各源案例間結構相似度相同，均為０．８０２ ２２。

根據公式（２）計算目標案例與各源案例間的全局相似度，得到與目標案例最為相似的案例為Ｃ１，隨后可根據案例庫中所存儲的Ｃ１解決方案、決策結果評價等信息進行案例重用與修正。

５結論

本文針對基于ＣＢＲ的應急決策模型中案例檢索問題，提出一種改進的案例相似性度量模型。傳統相似性度量模型無法精確描述缺失數據及屬性間替代性，因此本文提出“結構相似度”度量缺失數據對于案例結構特征相似性的影響，引入“變異系數”度量案例屬性的可替代性。分別針對連續型、分類型及模糊型變量定義相應的屬性局部相似性度量方法，并利用結構方程確定各屬性權重，最后通過防汛應急決策實例驗證了改進的案例相似性度量模型的有效性。

主要參考文獻

［１］ Ｋｏｌｏｄｎｅｒ Ｊ Ｌ．Ｉｍｐｒｏｖｉｎｇ Ｈｕｍａｎ Ｄｅｃｉｓｉｏｎ Ｍａｋｉｎｇ ｔｈｒｏｕｇｈ Ｃａｓｅ－Ｂａｓｅｄ Ｄｅｃｉｓｉｏｎ Ａｉｄｉｎｇ［Ｊ］． ＡＩ Ｍａｇａｚｉｎｅ， １９９１，１２（２）：５２－６８．

［２］ Ａａｍｏｄｔ Ａ， Ｐｌａｚａ Ｅ． Ｃａｓｅ－Ｂａｓｅｄ Ｒｅａｓｏｎｉｎｇ：Ｆｏｕｎｄａｔｉｏｎａｌ Ｉｓｓｕｅｓ， Ｍｅｔｈｏｄｏｌｏｇｉｃａｌ Ｖａｒｉａｔｉｏｎｓ ａｎｄ Ｓｙｓｔｅｍ Ａｐｐｒｏａｃｈｅｓ ［Ｊ］．Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，１９９４，７（１）：３９－５９．

［３］ Ｓｌｏｎｉｍ Ｔ Ｙ， Ｓｃｈｎｅｉｄｅｒ Ｍ． Ｄｅｓｉｇｎ Ｉｓｓｕｅｓ ｉｎ Ｆｕｚｚｙ Ｃａｓｅ－Ｂａｓｅｄ Ｒｅａｓｏｎｉｎｇ ［Ｊ］． Ｆｕｚｚｙ Ｓｅｔｓ ａｎｄ Ｓｙｓｔｅｍｓ， ２００１，１１７（２）：２５１－２６７．

［４］ 周凱波，馮珊，李鋒． 基于案例屬性特征的相似度計算模型研究［Ｊ］．武漢理工大學學報：信息與管理工程版， ２００３，２５（１）：２４－２７．

［５］ 秦玉平， 楊興凱． 基于案例推理的區間屬性相似度研究［Ｊ］． 遼寧師范大學學報：自然科學版， ２００６，２９（４）：４４２－４４５．

［６］ Ｗａｎｇ Ｌ， Ｔｉａｎ Ｓ Ｃ， Ｙｕａｎ Ｘ Ｆ， Ｍａ Ｘ Ｍ， Ｒｅｓｅａｒｃｈ ｏｎ Ｇａｓ Ｅｘｐｌｏｓｉｏｎ ＩＤＳＳ ｉｎ Ｃｏａｌｍｉｎｅｓ Ｂａｓｅｄ ｏｎ ＣＢＲ［Ｃ］ ／／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｄｖａｎｃｅｄ Ｃｏｍｐｕｔｅｒ Ｃｏｎｔｒｏｌ， Ｓｉｎｇａｐｏｒｅ， ２００９： ６５２－６５６．

［７］ Ｘｕ Ｚ Ｓ． Ｏｎ Ｓｉｍｉｌａｒｉｔｙ Ｍｅａｓｕｒｅｓ ｏｆ Ｉｎｔｅｒｖａｌ－Ｖａｌｕｅｄ Ｉｎｔｕｉｔｉｏｎｉｓｔｉｃ Ｆｕｚｚｙ Ｓｅｔｓ ａｎｄ Ｔｈｅｉｒ Ａｐｐｌｉｃａｔｉｏｎ ｔｏ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎｓ ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｓｏｕｔｈｅａｓｔ Ｕｎｉｖｅｒｓｉｔｙ （Ｅｎｇｌｉｓｈ Ｅｄｉｔｉｏｎ），２００７，２３（１）：１３９－１４３．

［８］ 駱敏舟，周美立． 實例推理檢索中相似度量方法的研究［Ｊ］．合肥工業大學學報：自然科學版， ２００１，２４（６）：１０９１－１０９４．

［９］ 鐘詩勝，王知行． 基于模糊相似優先的實例檢索模型［Ｊ］． 計算機研究與發展，１９９８，３５（９）：８１０－８１３．

［１０］ 許志端，楊蘭蓉，張金隆． 一種基于神經網絡的事例相似度評估方法［Ｊ］．華中理工大學學報， ２０００，２８（１０）：９１－９３．

［１１］ Ｄ Ｗｅｔｔｓｃｈｅｒｅｃｋ， Ｄ Ｗ Ａｈａ， Ｔ Ｍｏｈｒｉ． Ａ Ｒｅｖｉｅｗ ａｎｄ Ｅｍｐｉｒｉｃａｌ Ｅｖａｌｕａｔｉｏｎ ｏｆ Ｆｅａｔｕｒｅ Ｗｅｉｇｈｔｉｎｇ Ｍｅｔｈｏｄｓ ｆｏｒ ａ Ｃｌａｓｓ ｏｆ Lａｚｙ Ｌｅａｒｎｉｎｇ Ａｌｇｏｒｉｔｈｍｓ ［Ｊ］． Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ Ｒｅｖｉｅｗ，１９９７，１１（１－５）： ２７３－３１４．

An Improved Case Similarity Measure for Case Retrieval in CBR Based on Emergency Decision

GU Shu-juan， GAO Xue-dong， SUN Ran

（School of Economics and Management， University of Science and Technology Beijing， Beijing 100083， China）

Ａｂｓｔｒａｃｔ： Ｃａｓｅ－Ｂａｓｅｄ Ｒｅａｓｏｎｉｎｇ （ＣＢＲ） ｉｓ ｗｉｄｅｌｙ ｕｓｅｄ ｉｎ ｅｍｅｒｇｅｎｃｙ ｄｅｃｉｓｉｏｎ． Ｃａｓｅ ｓｉｍｉｌａｒｉｔｙ ｍｅａｓｕｒｅ ｉｓ ａ ｋｅｙ ｉｓｓｕｅ ｉｎ ｔｈｅ ｃａｓｅ ｒｅｔｒｉｅｖａｌ ｐｒｏｃｅｓｓ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ａｎ ｉｍｐｒｏｖｅｄ ｃａｓｅ ｓｉｍｉｌａｒｉｔｙ ｍｅａｓｕｒｅ ｉｓ ｇｉｖｅｎ ｔｏ ｄｅａｌ ｗｉｔｈ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｍｉｓｓｉｎｇ ｄａｔａ ａｎｄ ｓｕｂｓｔｉｔｕｔａｂｉｌｉｔｙ， ｗｈｉｃｈ ａｒｅ ｉｇｎｏｒｅｄ ｂｙ ｔｒａｄｉｔｉｏｎａｌ ｃａｓｅ ｓｉｍｉｌａｒｉｔｙ ｍｅａｓｕｒｅｓ． ‘Ｓｔｒｕｃｔｕｒｅ ｓｉｍｉｌａｒｉｔｙ’ ｉｓ ｐｒｏｐｏｓｅｄ ｔｏ ｃａｌｃｕｌａｔｅ ｔｈｅ ｓｔｒｕｃｔｕｒａｌ ｉｍｐａｃｔ ｏｆ ｍｉｓｓｉｎｇ ｄａｔａ， ａｎｄ ‘ｖａｒｉａｔｉｏｎ ｃｏｅｆｆｉｃｉｅｎｔ’ ｉｓ ｕｓｅｄ ｔｏ ｍｅａｓｕｒｅ ｔｈｅ ｓｕｂｓｔｉｔｕｔａｂｉｌｉｔｙ ｂｅｔｗｅｅｎ ａｔｔｒｉｂｕｔｅｓ． Ｆｉｎａｌｌｙ， ｎｕｍｅｒｉｃａｌ ｅｘａｍｐｌｅｓ ｉｎ ｔｈｅ ｒｅａｌ ｅｍｅｒｇｅｎｃｙ ｄｅｃｉｓｉｏｎ ａｐｐｌｉｃａｔｉｏｎ ｊｕｓｔｉｆｉｅｄ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ｎｅｗ ｃａｓｅ ｓｉｍｉｌａｒｉｔｙ ｍｅａｓｕｒｅ．

Ｋｅｙ ｗｏｒｄｓ： Ｅｍｅｒｇｅｎｃｙ Ｄｅｃｉｓｉｏｎ； Ｃａｓｅ Ｒｅｔｒｉｅｖａｌ； Ｃａｓｅ－Ｂａｓｅｄ Ｒｅａｓｏｎｉｎｇ （ＣＢＲ）； Ｃａｓｅ Ｓｉｍｉｌａｒｉｔｙ Ｍｅａｓｕｒｅｓ