李建洋，倪志偉，鄭金彬，謝秀珍

(1.合肥工業(yè)大學(xué)計算機網(wǎng)絡(luò)所，安徽 合肥 230009；2.龍巖學(xué)院計算機科學(xué)系，福建 龍巖 364000)

0 引 言

案例推理(Case-Based Reasoning, CBR)是由目標(biāo)案例而得到歷史的源案例，并由此來指導(dǎo)目標(biāo)案例求解的一種策略；它從另一個側(cè)面實現(xiàn)了人類智能，繞過了“知識獲取”這個難題，因此克服了基于規(guī)則系統(tǒng)(Rule-Based Reasoning, RBR)的一些弱點，是一種重要的機器學(xué)習(xí)方法.它根據(jù)相似性原理，由一個已知系統(tǒng)具有某些屬性，猜想另一個未全知系統(tǒng)也具有這些屬性；使用類比推理模式和假設(shè)推理模式，是從特殊到特殊的推理過程.案例由諸多的屬性組成，目標(biāo)案例和源案例的本質(zhì)特征具有相似性關(guān)系使得類比有了基礎(chǔ)[1].

案例學(xué)習(xí)系統(tǒng)往往處理的是復(fù)雜領(lǐng)域的問題，案例的表示不具備高結(jié)構(gòu)化和穩(wěn)定性，CBR系統(tǒng)的強大功能來源于它能從知識庫中迅速檢索出(case retrieve)相關(guān)案例[2-3].傳統(tǒng)的數(shù)據(jù)庫索引機制雖然可以有很好的借鑒作用，但卻存在極大的差別：傳統(tǒng)的數(shù)據(jù)庫強調(diào)的是保持存儲結(jié)構(gòu)平衡，CBR的索引用來在需要的情況下指出一個獨立的案例，不再強調(diào)存儲結(jié)構(gòu)平衡，而關(guān)心如何把案例庫劃分成概念上有用的片段；傳統(tǒng)的數(shù)據(jù)庫的操作是精確匹配，CBR中進(jìn)行的卻是相似性匹配[4-6].

1 維護技術(shù)

案例庫作為CBR系統(tǒng)中的主要知識庫，其學(xué)習(xí)功能即是不斷往案例庫中增加新的案例.當(dāng)其不斷增大時，帶來的好處是很容易找出相同或相似案例，減少修正階段(case adaptation)的次數(shù)與時間.一般來說知識庫越大，知識越豐富，這樣CBR系統(tǒng)可以解決更多的問題，體現(xiàn)了它的智能水平.但伴隨著案例庫的不斷擴大，會導(dǎo)致相似案例的檢索時間大大增加，引發(fā)“沼澤問題”.案例庫的維護就是指實現(xiàn)一些更新案例庫組織結(jié)構(gòu)或內(nèi)容的策略，包括表達(dá)方式、領(lǐng)域內(nèi)容、描述信息、實現(xiàn)方式，以保證未來的推理能完成特定的性能指標(biāo)[7-9].

1.1 不確定刪除法

1.1.1 隨機刪除法 當(dāng)知識庫中的規(guī)模超出一定的預(yù)先設(shè)定值時，就隨機刪除一個案例.隨機地刪除案例，可能是關(guān)鍵案例，從而導(dǎo)致系統(tǒng)能力的急劇下降，甚至有的目標(biāo)問題永遠(yuǎn)無解.

1.1.2 實用值度量法 utility效用=平均節(jié)省時間*應(yīng)用頻率-匹配代價，根據(jù)效用值來決定是否刪除.由于隨著知識庫的增加，一個特定知識的應(yīng)用頻率總是要下降的，所以它的度量值也在衰減，并且實用值較小的不一定就是無用的案例.

1.1.3 IB3方法 該方法通過對案例庫中的每個案例建立一個匹配記錄，一旦記錄指示該案例是一個無用案例，即把它從案例庫中刪去.此算法的缺點是：它是一個被動的不太精確的辦法，它沒有對每個案例的能力給予準(zhǔn)確地評估.

1.2 選擇刪除法

1.2.1 基于案例分類的刪除策略 該方法認(rèn)為在案例庫中并不是所有案例都個個平等，它通過計算一個案例的覆蓋度(Coverage)及其可觸及的程度(Reachability)，區(qū)分出了4個類型的案例：核心案例，連接案例，輔助案例，支持案例.為控制案例庫的規(guī)模，算法依次刪除相對次要的案例.

1.2.2 基于模式歸納的案例庫維護 在案例保存階段(case retain)進(jìn)行模式歸納，可以尋找類似案例的共性，再加以抽象和泛化.通過模式歸納，從而可以在案例庫中刪除一些極為相似的案例.在CBR系統(tǒng)在求解問題時，當(dāng)有了抽象的一般化知識，可以不必借助于相似的具體案例，因而減少候選集合中源案例的數(shù)量.

1.2.3 維護規(guī)則方法、基于Agent等辦法 Leake和Wilson在1998年提出了在檢索階段使用維護規(guī)則來更新現(xiàn)有案例，以解決環(huán)境的快速變化而引起的案例庫維護問題.Racine和Yang在1997年描述了一個基于Agent的方法來檢測冗余案例和沖突案例；他們又詳細(xì)研究了半結(jié)構(gòu)化的案例庫上的維護問題，也采用了Agent技術(shù).McSherry敘述了一類利用案例知識獲取工具CaseMaker來選擇案例，它是從一組由大到小按案例覆蓋度排序的案例中選擇出的、并建立案例庫的方法.

1.2.4 基于孤立點的案例庫維護 孤立點就是對給定的數(shù)據(jù)對象進(jìn)行分析，其中某些數(shù)據(jù)是顯著相異的、異常的或不一致的，通常有基于統(tǒng)計、基于距離、基于偏離三種檢測方法.在案例知識庫維護中，我們采用基于距離的孤立點方法，可以與基于相似距離的案例檢索相一致，因而算法并不需要特別額外的時空開銷[10-11].通過聚類等任何方法，剔除噪聲或錯誤等確實無用的孤立點，保留了可靠的孤立點——非凡的案例知識，具有極高的泛化能力.

1.2.5 基于相似粗糙集技術(shù)的案例庫維護 相似粗糙集技術(shù)是對粗糙集理論RS(Rough Sets)的應(yīng)用研究中，提出的一種擴展模型.它不但繼承了經(jīng)典粗糙集的各種優(yōu)勢；同時以相似關(guān)系取代等價關(guān)系后，可以避免對案例屬性數(shù)據(jù)的離散化處理(案例屬性數(shù)值絕大多數(shù)是連續(xù)的，為此經(jīng)典粗糙集采用了多種離散化方法，但是很容易造成數(shù)據(jù)的割裂)；而且它對相似關(guān)系的定義，與案例相似性的定義完全相同，可以和CBR系統(tǒng)完美地結(jié)合[12-13].

相似粗糙集技術(shù)可以有效地利用差別矩陣，通過不同的相似度閾值發(fā)現(xiàn)以及處理案例庫的冗余，從而可以有選擇地刪除滿足閾值的多余的相似案例，保證了案例庫擁有較高的覆蓋度；同時減少了案例庫維護過程中相似度的計算量，并且可以實現(xiàn)案例庫的動態(tài)維護.

1.3 非刪除法

如上所述，不確定刪除法雖然可以限制案例庫的無限膨脹，但是效果并不可靠，因此使用受到限制.選擇刪除法是基于這樣的假設(shè)：隨著案例系統(tǒng)的學(xué)習(xí)，會有各種冗余的案例加入案例庫，因此可以使用某些策略來搜尋并將其永久地刪除，只需保留一些符合某些標(biāo)準(zhǔn)的“高質(zhì)量”的案例.選擇刪除法是目前案例庫維護的主要手段，但是刪除法或多或少是以犧牲知識庫為代價，以換取CBR系統(tǒng)推理時間和空間的平衡.

然而，在一些電子商務(wù)、網(wǎng)絡(luò)CBR以及一些交互式CBR、分布式CBR應(yīng)用領(lǐng)域，諸如故障診斷、聯(lián)機決策等具體的應(yīng)用中，案例庫中的每一個案例都代表一個唯一的商品、或者一個不可缺失的寶貴經(jīng)驗，案例庫很容易達(dá)到成千上萬的規(guī)模，而且都是不可約簡的，顯然上述案例庫維護方法是不能應(yīng)用在這些環(huán)境中.

1.3.1 交叉覆蓋法 CBR與神經(jīng)網(wǎng)絡(luò)之間具有天然的密切聯(lián)系，人們已經(jīng)研究開發(fā)了多種在CBR系統(tǒng)中應(yīng)用神經(jīng)網(wǎng)絡(luò)的方法.但是上述的應(yīng)用系統(tǒng)存在著一些難以克服的弱點，如系統(tǒng)的可解釋性較差、系統(tǒng)實現(xiàn)復(fù)雜、實用性較差等，特別是系統(tǒng)中因神經(jīng)網(wǎng)絡(luò)的算法復(fù)雜性較高而難以用于CBR知識豐富的大規(guī)模案例庫系統(tǒng).交叉覆蓋算法是構(gòu)造性神經(jīng)網(wǎng)絡(luò)算法，采用多層前饋神經(jīng)網(wǎng)絡(luò)技術(shù)，解決了多年來一直未解決的作為分類器的多層前饋網(wǎng)絡(luò)的設(shè)計問題，不但具有很高的分類識別率，而且時間與空間的復(fù)雜度低，因此可以作為大規(guī)模、高維數(shù)據(jù)量的分類器[14-15].

該方法首先通過擴維、空間投射方法，較好地實現(xiàn)案例庫中的相似案例的領(lǐng)域覆蓋，實現(xiàn)信息的選擇性過濾.其次，通過將這些獲得的覆蓋領(lǐng)域，輸入到多層前饋神經(jīng)網(wǎng)絡(luò)中實現(xiàn)案例匹配，提高檢索效率.該方法并沒有縮減案例庫，通過使用易于構(gòu)造、易于理解的多層前饋神經(jīng)網(wǎng)絡(luò)，并且采用交叉覆蓋算法來有效地降低網(wǎng)絡(luò)的算法復(fù)雜度，建立起了一種可信賴的高性能、確保案例的性能與效率，可以有效地解決因?qū)W習(xí)導(dǎo)致的案例庫規(guī)模增長而產(chǎn)生的問題.

1.3.2 商空間法 知識的粒度性是造成使用已有知識不能精確地表示某些概念的原因[16-17]，目前粒計算的主要模型是模糊集、粗糙集和商空間模型.與粗糙集類似，商空間理論也使用等價關(guān)系來描述，但其獨到之處在于不只是研究二維的關(guān)系，還研究了對象之間的結(jié)構(gòu)關(guān)系.由于考慮到論域的結(jié)構(gòu)，借助于拓?fù)渲羞B通性以及映射的連續(xù)性，可以得到該推理模型具有的最重要的性質(zhì)——同態(tài)原則，即保真原理(或保假原理)[18].當(dāng)面對一個復(fù)雜問題時，人們因而可以通過合理的分層遞階，大大降低問題求解的復(fù)雜性.

在案例系統(tǒng)應(yīng)用的復(fù)雜的決策科學(xué)領(lǐng)域，人類對事物的認(rèn)識屬性的先后和關(guān)注度不同，研究基于商空間粒度變換的案例推理系統(tǒng)，實現(xiàn)推理知識的粒度變換，(1)可以獲取局部知識決策，克服CBR智能系統(tǒng)中因知識庫信息缺失、決策信息不完全帶來的推理難題；(2)可以完成概略地、由粗到細(xì)、不斷求精的多粒度分析法，避免了計算復(fù)雜度高的難題，從推理需要的不同知識層次來研究問題.

這樣，應(yīng)用商空間粒度模型所獲取的典型意義就在于——可以實現(xiàn)類似結(jié)構(gòu)化數(shù)據(jù)庫的案例知識檢索片斷，方法是：建立基于不同粒度知識的類似決策樹，直接實現(xiàn)粗到細(xì)的案例知識檢索，配合復(fù)合知識的多粒度合成，極大地降低檢索復(fù)雜度.如前所述的交叉覆蓋法就是一種運用知識粒度的檢索，但該方法中的知識只是基于某種“定”粒度的劃分，尚未運用不同粒度的變換；而商空間法可以提供動態(tài)的知識粒度的變換.

1.4 維護原則

隨著應(yīng)用的日益開展，許多實用的CBR系統(tǒng)，廣泛應(yīng)用于醫(yī)療診斷、電路或機械設(shè)計、故障診斷、氣象等各個領(lǐng)域；大型的CBR系統(tǒng)也越來越普遍了.因此CBR系統(tǒng)的案例庫運行效率問題突出，而且由于噪音案例以及錯誤案例的存在，最終會導(dǎo)致系統(tǒng)總體的性能降低，因此案例庫的能力以及效率是判斷案例庫維護質(zhì)量的依據(jù).目前的研究突現(xiàn)了案例庫維護在案例推理過程中的重要性，案例作為專家經(jīng)驗的計算機存儲形式，是人類三種思維(直覺、邏輯、創(chuàng)造性思維)的一種綜合表現(xiàn)形式.

由于存在于人類思維中的非單調(diào)邏輯推理，屬于非標(biāo)準(zhǔn)邏輯范疇；用案例形式表示，容易發(fā)現(xiàn)冗余的和不一致知識；盡可能對此進(jìn)行實時監(jiān)測，實現(xiàn)實時維護.在不斷變化的環(huán)境中，由于領(lǐng)域知識的變化，導(dǎo)致類比的基礎(chǔ)即由特殊到特殊的知識假設(shè)推理失效，只能選用刪除法進(jìn)行案例庫維護.針對實際領(lǐng)域應(yīng)用中不可約簡案例庫的CBR系統(tǒng)性能維護難題，只有依賴兩方面的突破：改進(jìn)案例檢索算法以適應(yīng)大規(guī)模的案例庫，對案例庫采取某種過濾手段以適應(yīng)案例檢索算法，從而確保CBR系統(tǒng)的可靠、高效運轉(zhuǎn).

2 結(jié) 語

案例知識庫是一個系統(tǒng)及組織的核心財富，也是CBR系統(tǒng)研究的核心難題，涉及CBR推理的知識表示、適配與改寫過程；由于是非結(jié)構(gòu)化的，難以通過常規(guī)方法實現(xiàn)維護.案例知識庫維護作為CBR研究的一個重要分支，已經(jīng)開發(fā)出來不同的維護策略；然而不同的環(huán)境下，因CBR系統(tǒng)的規(guī)模、時效性以及應(yīng)用領(lǐng)域的特點不同，其維護手段和維護性能存在較大的差異.

隨著應(yīng)用領(lǐng)域的拓寬和應(yīng)用程度的加深、規(guī)模的不斷增加，其維護手段日趨復(fù)雜.目前的國內(nèi)外研究中，特別是國際商業(yè)化的CBR應(yīng)用系統(tǒng)，由于長期持久地運行，對CBM技術(shù)提出了種種挑戰(zhàn).隨著人工智能領(lǐng)域研究的不斷進(jìn)步，融合其它學(xué)習(xí)技術(shù)的案例推理系統(tǒng)(如機器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)等)已經(jīng)迅速展開.未來的案例庫維護技術(shù)應(yīng)當(dāng)可以全面地監(jiān)控CBR的能力，如案例庫的增長速度及系統(tǒng)的性能檢查；案例庫維護的定量化分析與證明；動態(tài)地組織與更新案例庫及案例庫實時壓縮等技術(shù)的研究將會更加深入.

參考文獻(xiàn)：

[1]倪志偉.智能管理技術(shù)與方法[M].北京：科學(xué)出版社，2007.

[2]Susan Craw, Jacek Jarmulak & Ray Rowe. Maintaining Retrieval Knowledge in a Case-Based Reasoning System[J]. Computational Intelligence,2002,17(2): 346-363.

[3]Roth-Berghofer T, Reinartz T. MAMA: a maintenance manual for cased-based reasoning systems[C]// Proceedings of International Conference on Case-Based Reasoning 2001(ICCBR 2001). Springer, 2001:452-466.

[4]Petra Perner. Case-Based Reasoning and the Statistical Challenges[C]// Proceedings of European Conference on Case-Based Reasoning (ECCBR 2008). Springer, 2008:430-443.

[5]Grachten M，F(xiàn) Alejandro G, Josep L A. Navigating through case base competence[C]// Proceedings of International Conference on Case-Based Reasoning 2005(ICCBR 2005). Springer, 2005:282-295.

[6]Isabelle Bichindaritz.Prototypical Cases for Knowledge Maintenance in Biomedical CBR[C]// Proceedings of International Conference on Case-Based Reasoning 2007 (ICCBR 2007). Springer, 2007:492-506.

[7]Gomes P, Pereira F C, Paiva P.Evaluation of case-based Maintenance Strategies in Software Design[C]// Proceedings of International Conference on Case-Based Reasoning 2003(ICCBR 2003). Springer, 2003:186-200.

[8]Chen Fu-chien, Wen Chih-wang, Jen Chieh-cheng. Data mining for yield enhancement in semiconductor manufacturing and an empirical study [J]. Expert Systems with Applications, 2007,33(1):192-198.

[9]Petra Perner. Case-base maintenance by conceptual clustering of graphs[J]. Engineering Applications of Artificial Intelligence, 2006,19(4): 381-393.

[10]Ni Zhi-wei, Liu Yu, Li Feng-gang.Case-base maintenance based on outlier data mining[C]// Proceedings of International Conference on Machine Learning and Cybernetics 2005(ICMLC2005). Springer, 2005: 2861- 2864.

[11]Shi Dong-hui, Zhang Chun-yang, Cai Qing-sheng. A new algorithm of outlier mining in data base [J].Mini-micro Systems, 2002,22(10):1234-1236.

[12]李建洋，倪志偉，劉慧婷.一種基于相似粗糙集技術(shù)的案例庫維護[J].計算機工程與應(yīng)用，2005，41(32):19-21.

[13]Gento A M, Redondo A. Rough sets and maintenance in a production line [J]. Expert Systems, 2003, 20(5): 271-278.

[14]張鈴，張鈸.多層前饋網(wǎng)絡(luò)的交叉覆蓋設(shè)計算法[J].軟件學(xué)報，1999，10(7):737-742．

[15]Li-Jian-yang, Ni Zhi-wei, LIU Xiao. Case-base maintenance based on multi-layer alternative-covering algorithm[C]// Proceedings of International Conference on Machine Learning and Cybernetics 2006(ICMLC2006). Springer, 2006:2035-2039.

[16]Zhang Ling, Zhang Bo, The structure analysis of fuzzy sets[J]. International Journal of Approximate Reasoning. 2005:24:92-108.

[17]Zadeh L A. Generalized theory of uncertainty (GTU)-principal concepts and ideas [J]. Computational Statistics & Data Analysis, 2006, 51(1): 15-46.

[18]張鈴,張鈸.模糊商空間理論(模糊粒度計算方法)[J].軟件學(xué)報,2003,14(4):770-776.