案例知識(shí)庫(kù)維護(hù)技術(shù)的研究進(jìn)展

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

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

0 引 言

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

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

1 維護(hù)技術(shù)

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

1.1 不確定刪除法

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

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

1.1.3 IB3方法 該方法通過(guò)對(duì)案例庫(kù)中的每個(gè)案例建立一個(gè)匹配記錄，一旦記錄指示該案例是一個(gè)無(wú)用案例，即把它從案例庫(kù)中刪去.此算法的缺點(diǎn)是：它是一個(gè)被動(dòng)的不太精確的辦法，它沒(méi)有對(duì)每個(gè)案例的能力給予準(zhǔn)確地評(píng)估.

1.2 選擇刪除法

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

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

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

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

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

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

1.3 非刪除法

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

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

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

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

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

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

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

1.4 維護(hù)原則

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

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

2 結(jié) 語(yǔ)

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

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

參考文獻(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ù)的案例庫(kù)維護(hù)[J].計(jì)算機(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ì)算法[J].軟件學(xué)報(bào)，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ì)算方法)[J].軟件學(xué)報(bào),2003,14(4):770-776.