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

王義祥，鄔群勇

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

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

在傳統(tǒng)的CBR系統(tǒng)中，特征屬性的權(quán)重常采用專家主觀賦權(quán)法[3]，即特征屬性的權(quán)重一般事先由領(lǐng)域?qū)＜腋鶕?jù)經(jīng)驗進(jìn)行主觀判斷給定，并且特征屬性的權(quán)重一旦確定以后，便被永久地固定在系統(tǒng)中，一般很少改變。然而在許多場合下，特征屬性對問題解決的貢獻(xiàn)程度呈現(xiàn)著一定的波動性，即特征屬性的權(quán)重會隨著環(huán)境、時間等因素的變化而變化[4]。因此，需要對特征屬性權(quán)重進(jìn)行動態(tài)調(diào)整。

本文在分析現(xiàn)有案例特征屬性權(quán)重調(diào)整方法存在問題的基礎(chǔ)上，充分參考CBR的思想，提出了一種基于CBR的特征屬性權(quán)重選取與自修正方法，充分利用權(quán)重分配的歷史經(jīng)驗，指導(dǎo)當(dāng)前權(quán)重問題的動態(tài)分配與調(diào)整。

1 特征屬性權(quán)重選取基本方法

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

1.1 Pull&Push調(diào)整法

Pull&Push調(diào)整[8-9]基于訓(xùn)練樣本成功和失敗的檢索經(jīng)驗來調(diào)整特征屬性權(quán)重。當(dāng)源案例被正確檢索出來，如果源案例與目標(biāo)案例對應(yīng)特征屬性的屬性值相同，系統(tǒng)將自動提高該屬性的權(quán)重，否則系統(tǒng)將自動降低該屬性的權(quán)重；當(dāng)源案例被錯誤檢索出來，如果源案例與目標(biāo)案例對應(yīng)特征屬性的屬性值不同，系統(tǒng)將自動提高該屬性的權(quán)重，否則系統(tǒng)將自動降低該屬性的權(quán)重。

特征屬性權(quán)重采用下式來確定每次調(diào)整幅度的大?。?/p>

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

1.2 基于遺傳算法的權(quán)重向量調(diào)整法

基于遺傳算法的權(quán)重向量調(diào)整[10]依據(jù)遺傳算法自適應(yīng)迭代尋優(yōu)的思想，即從某一隨機(jī)產(chǎn)生的或特定的初始群體出發(fā)，按照一定的操作規(guī)則，如選擇、交叉、變異等，不斷地迭代計算，并根據(jù)每一個個體的適應(yīng)值，保留優(yōu)良品種，淘汰次品，引導(dǎo)搜索過程向最優(yōu)逼近。其是在領(lǐng)域?qū)＜抑付ǔ跏紮?quán)重的基礎(chǔ)上對權(quán)重向量進(jìn)行優(yōu)化，使權(quán)重向量逐漸從不佳逼近最優(yōu)。

在利用遺傳算法調(diào)整權(quán)重向量時需要確定遺傳參數(shù)設(shè)置、染色體編碼、個體適應(yīng)度評價以及遺傳算子選擇，實現(xiàn)較為復(fù)雜[11]。

1.3 基于時序的權(quán)重向量調(diào)整法

基于時序的權(quán)重向量調(diào)整[12]通過引入時間影響因子對案例的特征屬性權(quán)重進(jìn)行逐一調(diào)整。設(shè)一組時序相關(guān)序列 t1，t2，…，tn分別對應(yīng)案例中 n個特征屬性 p1，p2，…，pn，表示各特征屬性對時間的敏感性（由領(lǐng)域?qū)＜抑付ǎ?，其?ti∈[0，1]，（i=1，2，…，n）。 ti=0 表示該特征屬性值的變化與時間基本無關(guān)。隨著特征屬性值與時間相關(guān)性的增大，ti逐漸增大，最大為1。同時，定義時序調(diào)整系數(shù) μ=η×ΔT，其中 ΔT為時間跨度，單位為年；η 為時間跨度系數(shù)，可取為1。

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

以上這些調(diào)整方法基本都依賴于領(lǐng)域?qū)＜沂孪葘μ囟▎栴}給出一個經(jīng)驗參考權(quán)重向量，并在此基礎(chǔ)上對其進(jìn)行不斷地重復(fù)累積調(diào)整，這種累積經(jīng)驗對于相似環(huán)境下的權(quán)重分配需求是有效的，但對于特殊環(huán)境下的權(quán)重分配需求就顯得難以勝任。

2 基于CBR的特征屬性權(quán)重選取與自修正方法

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

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

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

2.1 基于CBR的特征屬性權(quán)重選取

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

圖1 基于CBR權(quán)重自學(xué)習(xí)與調(diào)整策略

（1）權(quán)重檢索：根據(jù)目標(biāo)權(quán)重和歷史權(quán)重相似性度量標(biāo)準(zhǔn)，通過合適的檢索匹配算法，從歷史權(quán)重庫中找出與目標(biāo)權(quán)重最相似的權(quán)重。

（2）權(quán)重重用：將最相似的權(quán)重作為參考權(quán)重，指導(dǎo)目標(biāo)權(quán)重的分配。

（3）權(quán)重修正：分析參考權(quán)重與目標(biāo)權(quán)重間的差異部分，通過合適的權(quán)重修正策略，并結(jié)合實際情況，對參考權(quán)重加以調(diào)整與修正。

（4）權(quán)重學(xué)習(xí)：根據(jù)制定的學(xué)習(xí)策略，把新權(quán)重存儲到權(quán)重庫中。

基于CBR的特征屬性權(quán)重選取思想的具體實現(xiàn)：

（1）結(jié)合領(lǐng)域應(yīng)用背景，收集以往專家的特征屬性權(quán)重分配經(jīng)驗，將其作為權(quán)重案例，存入歷史權(quán)重庫中以構(gòu)建領(lǐng)域問題權(quán)重參考庫；

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

（3）結(jié)合實際應(yīng)用需要，采用合適的權(quán)重調(diào)整策略，對最相似權(quán)重進(jìn)行修正，以適應(yīng)新問題；

（4）將調(diào)整后的新權(quán)重存入歷史權(quán)重庫中以豐富權(quán)重庫的經(jīng)驗，提高權(quán)重庫解決問題的能力。

2.2 基于CBR的特征屬性權(quán)重自修正

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

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

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

圖2 基于CBR特征屬性權(quán)重自修正

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

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

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

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

3 應(yīng)用實例

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

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

基于指數(shù)法的單個特征屬性權(quán)重相似度：

式中Xi、Yi分別表示案例特征屬性 i的目標(biāo)權(quán)重值和歷史權(quán)重值。

基于簡化K-NN法的整個權(quán)重向量相似度：

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

表1給出了目標(biāo)權(quán)重與部分歷史權(quán)重之間基于指數(shù)法和K-NN算法的相似性檢索結(jié)果，其中歷史權(quán)重案例6是與目標(biāo)權(quán)重最相似的權(quán)重。

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

表1 特征屬性權(quán)重相似性檢索結(jié)果

依據(jù)相似性的傳遞性，歷史權(quán)重案例5不僅與目標(biāo)權(quán)重具有較高的相似性，同時彌補(bǔ)了歷史權(quán)重案例6部分屬性權(quán)重不能滿足目標(biāo)權(quán)重分配需求的不足。若對歷史權(quán)重案例5不滿意，可對其進(jìn)行人工局部調(diào)整，并將調(diào)整結(jié)果存入到權(quán)重庫中以備下次重用。

這樣不僅解決了當(dāng)前權(quán)重分配問題，同時也豐富了權(quán)重案例庫的經(jīng)驗，擴(kuò)大了權(quán)重案例庫的覆蓋面，增強(qiáng)了其解決問題的能力。

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

[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]章曙光，蔡慶生.一種基于屬性組合的權(quán)重向量選取模型[J].微機(jī)發(fā)展，2004，14（11）：13-15.

[3]艾芳菊.基于實例推理系統(tǒng)中的權(quán)重分析[J].計算機(jī)應(yīng)用，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]章曙光，汪淼，張永，等.一種基于遺傳算法的權(quán)重向量選取模型[J].微機(jī)發(fā)展，2005，15（12）：87-89.

[12]楊健，楊曉光，劉曉彬，等.一種基于K-NN的案例相似度權(quán)重調(diào)整算法[J].計算機(jī)工程與應(yīng)用，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.