一種基于CBR的特征屬性權重選取與自修正方法*

王義祥，鄔群勇

(福州大學 福建省空間信息工程研究中心，福建 福州350002)

案例特征屬性權重反映了該屬性相對于其他屬性的重要程度，以及單個屬性對問題解決的貢獻程度[1-2]。案例特征屬性權重向量的選取將直接影響到檢索出案例的質量的好壞，并進一步影響到CBR推理的效率和質量，同時也決定了案例復用與修改的難易。

在傳統的CBR系統中，特征屬性的權重常采用專家主觀賦權法[3]，即特征屬性的權重一般事先由領域專家根據經驗進行主觀判斷給定，并且特征屬性的權重一旦確定以后，便被永久地固定在系統中，一般很少改變。然而在許多場合下，特征屬性對問題解決的貢獻程度呈現著一定的波動性，即特征屬性的權重會隨著環境、時間等因素的變化而變化[4]。因此，需要對特征屬性權重進行動態調整。

本文在分析現有案例特征屬性權重調整方法存在問題的基礎上，充分參考CBR的思想，提出了一種基于CBR的特征屬性權重選取與自修正方法，充分利用權重分配的歷史經驗，指導當前權重問題的動態分配與調整。

1 特征屬性權重選取基本方法

國內外學者對于特征屬性權重選取做了大量研究，并提出了多種權重向量選取與調整方法[5-7]，如Pull&Push、遺傳算法、基于時序等。

1.1 Pull&Push調整法

Pull&Push調整[8-9]基于訓練樣本成功和失敗的檢索經驗來調整特征屬性權重。當源案例被正確檢索出來，如果源案例與目標案例對應特征屬性的屬性值相同，系統將自動提高該屬性的權重，否則系統將自動降低該屬性的權重；當源案例被錯誤檢索出來，如果源案例與目標案例對應特征屬性的屬性值不同，系統將自動提高該屬性的權重，否則系統將自動降低該屬性的權重。

特征屬性權重采用下式來確定每次調整幅度的大小：

式中Wi表示權重，Fc表示一個案例被錯誤檢索到的次數，Kc表示該案例被正確檢索到的次數，當Kc增加時，Fc/Kc降低，使得W值變化的幅度越來越小，從而保證了權重不會無限地增加或減少。Δi表示每次調整的幅度，其值的大小可以根據實際需要調整。

1.2 基于遺傳算法的權重向量調整法

基于遺傳算法的權重向量調整[10]依據遺傳算法自適應迭代尋優的思想，即從某一隨機產生的或特定的初始群體出發，按照一定的操作規則，如選擇、交叉、變異等，不斷地迭代計算，并根據每一個個體的適應值，保留優良品種，淘汰次品，引導搜索過程向最優逼近。其是在領域專家指定初始權重的基礎上對權重向量進行優化，使權重向量逐漸從不佳逼近最優。

在利用遺傳算法調整權重向量時需要確定遺傳參數設置、染色體編碼、個體適應度評價以及遺傳算子選擇，實現較為復雜[11]。

1.3 基于時序的權重向量調整法

基于時序的權重向量調整[12]通過引入時間影響因子對案例的特征屬性權重進行逐一調整。設一組時序相關序列 t1，t2，…，tn分別對應案例中 n個特征屬性 p1，p2，…，pn，表示各特征屬性對時間的敏感性（由領域專家指定），其中 ti∈[0，1]，（i=1，2，…，n）。 ti=0 表示該特征屬性值的變化與時間基本無關。隨著特征屬性值與時間相關性的增大，ti逐漸增大，最大為1。同時，定義時序調整系數 μ=η×ΔT，其中 ΔT為時間跨度，單位為年；η 為時間跨度系數，可取為1。

對于案例 C的第 i個屬性權重調整為 Wi′=Wi×(1＋ti×μ)，其中 ti×μ 為時間影響因子，μ=η×ΔT，時間跨度 ΔT可由案例C與源案例S發生時間差值得到。為使同一案例中所有特征屬性的權重之和仍為1，需要相應調整特征屬性的權重：

以上這些調整方法基本都依賴于領域專家事先對特定問題給出一個經驗參考權重向量，并在此基礎上對其進行不斷地重復累積調整，這種累積經驗對于相似環境下的權重分配需求是有效的，但對于特殊環境下的權重分配需求就顯得難以勝任。

2 基于CBR的特征屬性權重選取與自修正方法

CBR核心思想是充分借鑒以往專家經驗來指導新問題的求解[13-14]。在這種思想的啟發下，對于特征屬性權重的選取和調整問題，同樣可以嘗試用CBR的思想來解決。即將以往任何一次專家的屬性權重分配經驗作為案例存入歷史權重庫中，運用歷史權重庫中歷史權重來指導目標權重的選取與調整。

根據事物發展的規律性和重現性，即相同或相似的問題具有相同或相似的解法，相同或相似的問題會重復發生，每一個權重分配案例都是某種特定需求環境下的成功經驗記錄，對將來類似問題具有重要的參考借鑒作用，同時歷史權重分配經驗直接以新案例的形式進行保存，避免了特定需求環境下的成功分配經驗的二次修改難以適應原始需求環境。

歷史權重庫收集了以往各種不同需求的權重分配案例，積累了豐富的經驗和知識，同時CBR具有自學習能力，隨著權重庫的不斷積累，理想情況下將會覆蓋到各種不同環境下的權重分配問題。因此，通過權重庫來解決權重分配問題是可行的也是有效的，這樣不僅能夠滿足相似環境下的權重分配需求，同時也可以處理特殊異常環境下的權重分配需求。

2.1 基于CBR的特征屬性權重選取

參考 CBR 基本過程， 即 4R（Retrieve、Reuse、Revise、Retain）[13-14]，基于CBR的特征屬性權重自學習與調整策略可分為4個過程，如圖 1所示。

圖1 基于CBR權重自學習與調整策略

（1）權重檢索：根據目標權重和歷史權重相似性度量標準，通過合適的檢索匹配算法，從歷史權重庫中找出與目標權重最相似的權重。

（2）權重重用：將最相似的權重作為參考權重，指導目標權重的分配。

（3）權重修正：分析參考權重與目標權重間的差異部分，通過合適的權重修正策略，并結合實際情況，對參考權重加以調整與修正。

（4）權重學習：根據制定的學習策略，把新權重存儲到權重庫中。

基于CBR的特征屬性權重選取思想的具體實現：

（1）結合領域應用背景，收集以往專家的特征屬性權重分配經驗，將其作為權重案例，存入歷史權重庫中以構建領域問題權重參考庫；

（2）對于一個新的權重分配問題，制定局部權重相似性度量標準，選擇合適的權重案例相似性檢索算法，結合權重分配需求條件，對歷史權重庫進行相似性檢索，找出相似度最高的歷史權重，即為與目標權重最相似的權重；

（3）結合實際應用需要，采用合適的權重調整策略，對最相似權重進行修正，以適應新問題；

（4）將調整后的新權重存入歷史權重庫中以豐富權重庫的經驗，提高權重庫解決問題的能力。

2.2 基于CBR的特征屬性權重自修正

基于CBR相似性檢索得到的參考權重，可能不完全適合于當前的權重分配需求，需要對其進行修正。一般特征屬性權重修正規則和知識獲取十分困難，而歷史權重案例庫中儲備了豐富的實際經驗和顯性知識，同時也蘊含了大量的隱性知識，這些知識對于特征屬性權重修正有一定的幫助。

基于CBR的特征屬性權重自修正的基本思想是直接從權重案例庫中得到權重修正知識。即首先從權重案例庫中檢索出與目標權重最相似的權重案例；通過比較目標權重和最相似的權重，得出存在差異的權重所對應的特征屬性集合；根據這些差異特征屬性集合對權重案例庫進行聚類，得出一個新的權重案例庫；最后從新的權重案例庫中再次檢索出和上次得到的最相似權重最接近的權重組合，將這個權重組合作為參考來指導當前的特征屬性權重分配。

整個修正方法在權重修正過程中應用CBR思想，根據重用失敗的原因，找到最終的解決方案，如圖 2所示。整個屬性權重修正過程不需要依賴領域知識。

圖2 基于CBR特征屬性權重自修正

基于CBR的特征屬性權重自修正算法描述如下：（1）假設權重案例庫為 WC，目標權重為 A，先從權重案例庫WC中檢索出與A最相似的權重B。

（2）對A和 B進行特征屬性權重差異性分析，找出兩者之間的特征屬性權重差異。假設A有m個特征屬性，其中 i（0≤i≤m）個特征屬性權重存在差異，如果 i=0，表示沒有差異，算法結束。

（3）根據這些差異特征 D1，D2，…，Di對權重案例庫進行聚類分析。即針對每一個差異特征，從權重案例庫WC中找到和A中該特征屬性的權重值相同的案例，將其聚成一類。這樣可以得到分類 D1(C)，D2(C)，…，Di(C)，其構成一個新權重案例庫WCnew。

（4）從WCnew中檢索出和B最相似的權重案例，并將其作為最佳權重分配參考方案。根據相似性的傳遞性原理，此權重案例不僅與目標權重A具有較高的相似性，同時兼顧了權重案例B中部分屬性權重不能滿足目標權重A分配的需求。

3 應用實例

本文提出的方法在突發性大氣環境污染事故案例推理系統中進行了應用。突發性大氣環境污染事故對事故現場環境依賴性特別強，不同環境背景下，各特征屬性表現出來的重要程度存在很大的差異性。以往的固定屬性權重難以滿足特殊環境下屬性權重分配的需要，而基于CBR的特征屬性權重選取與自修正方法可以很好地解決不同環境條件下的特征屬性權重分配需求。

在突發性環境污染事故案例推理系統中，對于特征屬性權重的選取與調整的實現問題，首先收集以往權重分配經驗并初步建立權重案例庫；其次根據當前的環境條件，確定特征屬性的重要程度，并給所關注特征屬性分配一定的權重，對于非特別關注或重要程度難以確定的特征屬性，其權重缺省為 0，即目標權重為 OC（0.2，-，-，0.15，0.15，0.15，-，-，0.2）， 依據特征屬性權重相似性檢索算法，對權重庫進行相似性檢索。

基于指數法的單個特征屬性權重相似度：

式中Xi、Yi分別表示案例特征屬性 i的目標權重值和歷史權重值。

基于簡化K-NN法的整個權重向量相似度：

式中sim(OCXi，SCXi)表示對于案例特征屬性 i目標權重和歷史權重間的相似度，N為參與局部特征屬性相似度計算的屬性個數。

表1給出了目標權重與部分歷史權重之間基于指數法和K-NN算法的相似性檢索結果，其中歷史權重案例6是與目標權重最相似的權重。

若歷史權重案例6的權重分配滿足當前權重分配的需要，直接將其作為目標權重分配問題的解決方案；若對歷史權重案例6的權重分配結果不滿意，則對其執行自修正操作。即對歷史權重案例6的參考權重與目標權重進行差異性分析，得到差異屬性集合{氣象條件，應急措施}，其對應的目標權重為{0.15，0.2}；根據污染物質、應急決策兩個特征屬性的目標權重對權重庫進行聚類分析，得到兩個權重案例集{5，8}和{1，2，4，7}，并構成一個新的子權重庫{1，2，4，5，7，8}；再次利用屬性權重相似性檢索算法，從子權重庫中檢索出與歷史權重案例6中的參考權重最相似的權重，即為歷史權重案例5，并將其作為當前目標權重分配問題的參考解決方案。

表1 特征屬性權重相似性檢索結果

依據相似性的傳遞性，歷史權重案例5不僅與目標權重具有較高的相似性，同時彌補了歷史權重案例6部分屬性權重不能滿足目標權重分配需求的不足。若對歷史權重案例5不滿意，可對其進行人工局部調整，并將調整結果存入到權重庫中以備下次重用。

這樣不僅解決了當前權重分配問題，同時也豐富了權重案例庫的經驗，擴大了權重案例庫的覆蓋面，增強了其解決問題的能力。

傳統案例屬性的靜態權重已難以滿足需要，而案例屬性權重選取與動態調整是當前研究的一大難題，本文嘗試借鑒CBR思想，提出了一種基于CBR的特征屬性權重選取與自修正方法，為特征屬性權重分配與調整提供了一種新的思路?；贑BR的特征屬性權重選取與自修正方法直接援引以前積累的經驗和知識來解決當前特征屬性權重的選取與調整問題，具有操作實現簡單、進行知識積累和重用等優點，特別適合特殊環境下復雜問題的特征屬性權重選取與調整。

[1]LEAKE D B，KINLEY A，WILSON D.Learning to integrate multiple knowledge sources for case-based reasoning[C].Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence,Morgan Kaufmann，San Francisco，1997：246-251.

[2]章曙光，蔡慶生.一種基于屬性組合的權重向量選取模型[J].微機發展，2004，14（11）：13-15.

[3]艾芳菊.基于實例推理系統中的權重分析[J].計算機應用，2005，25（5）：1022-1025.

[4]AHA D W.The omnipresence of case-based reasoning in science and application[J].Knowledge-Based Systems，1998，11(5)：261-273.

[5]SKALAK D B.Prototype and feature selection by sampling and random mutation hill climbing algorithms[C].Proceedings of the 1994 International Conference on Machine Learning，293-301.

[6]MOHRI T，TANAKA H.An optimal weighting criterion of case indexing for both numeric and symbolic attributes[C].AAAI Technical Report WS-94-01,Case-Based Reasoning：Papers from the 1994 Workshop.Menlo Park，CA：AAAI Press.

[7]LING C X，WANG H.Computing optimal attribute weight setting fot nearest neighbor algorithms[J].Artificial Intelligence Review，1997，11(1-5)：255-272.

[8]SALZBERG S.A nearest hyperrectangle learning method[J].Machine Learning，1991(6)：251-276.

[9]BONZANO A，CUNNINGHAM P，SMYTH B.Using introspective learning to improve retrieval in CBR：a case study in air traffic control[C].Proceedings of the 2nd International Conference on Case-Based Reasoning，Providence RI，USA：Springer，1997：291-302.

[10]SHIN K S，HAN I.Case-based reasoning supported by genetic algorithms for corporate bond rating[J].Expert Systems with Applications，1999(16)：85-95.

[11]章曙光，汪淼，張永，等.一種基于遺傳算法的權重向量選取模型[J].微機發展，2005，15（12）：87-89.

[12]楊健，楊曉光，劉曉彬，等.一種基于K-NN的案例相似度權重調整算法[J].計算機工程與應用，2007，43（23）：8-11.

[13]WATSON I，MARIR F.Case-based reasoning：a review[J].The knowledge engineering review，1994，9(4)：327-354.

[14]CUNNINGHAM P，SMYTH B.Case-based reasoning in scheduling：reusing solution components[J].International Journal of Production Research，1997，35(11)：2947-2962.