基于ALC的事例庫結(jié)構(gòu)及檢索研究①

馬林威，古天龍，徐周波

（桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實驗室，廣西 桂林 541004）

基于事例推理（case－based reasoning，簡稱CBR）是人工智能的一個重要分支［1］，具有獲取知識容易、求解效率高等特點(diǎn)，其工作過程可以歸納為一個4R循環(huán)模型：事例檢索（retrieval），事例重用（reuse），事例修正（revise）及事例保存（retain）。在CBR中事例表示是基礎(chǔ)，事例檢索是關(guān)鍵。根據(jù)事例表示方法的特點(diǎn)設(shè)計事例庫的結(jié)構(gòu)，進(jìn)而設(shè)計事例檢索算法。因此，事例表示方法決定了事例表示的準(zhǔn)確性、有效性，對事例檢索和事例庫結(jié)構(gòu)組織等有很大影響。若使用屬性－值對法表示事例，則通常采用關(guān)系數(shù)據(jù)庫存儲事例，使用SQL查詢語句進(jìn)行事例檢索［2］；若使用XML表示事例，則通常采用XML數(shù)據(jù)庫存儲事例，通過分析XML文檔及相似索引進(jìn)行檢索［3］；若使用基于框架的事例表示法，則通常采用事例及抽象事例間的偏序關(guān)系建立事例庫層次結(jié)構(gòu)［4］。

隨著事例知識及領(lǐng)域知識的復(fù)雜化、豐富化，CBR進(jìn)入知識密集型時代。在知識密集型CBR中，傳統(tǒng)的事例表示方法如屬性－值對、框架法的知識刻畫能力明顯不足。由于描述邏輯具有強(qiáng)的知識表示及推理能力，被廣泛應(yīng)用于知識密集型CBR中。已用于事例表示的描述邏輯有C－CLASSIC［5］、εL［6］及ALC［7］等。針對基于描述邏輯的事例表示方法，通常使用概念自動分類推理建立事例庫的層次結(jié)構(gòu)［5］，達(dá)到對事例分類的效果，如基于描述邏輯的CBR系統(tǒng)jCOLIBRI的事例庫［8］。此后，基于描述邏輯CBR研究主要側(cè)重于事例相似性度量的研究［6－7，9］。

現(xiàn)有基于描述邏輯的事例庫的建立依賴于知識庫中已定義的概念，但知識庫中事先定義的概念非常有限且無法滿足事例分類的需要，影響事例檢索的效率及效果。鑒于此，研究基于描述邏輯ALC的事例庫結(jié)構(gòu)，并根據(jù)該結(jié)構(gòu)給出了事例檢索算法。

1 描述邏輯ALC

1.1 ALC的語法與語義

描述邏輯是一種基于對象的知識表示的形式化工具，是一階謂詞邏輯的可判定子集，具有強(qiáng)的知識表示能力及可判定的推理能力。ALC是最基本的描述邏輯，其基本符號包括由概念名組成的集合NC、由角色名組成的集合NR及由個體名組成的集合NI，通過基本符號遞歸構(gòu)造出所有概念。

ALC－概念的集為滿足下列條件的最小集［10］。

1）若概念名C∈NC，則C是ALC－概念；

2）若C、D是ALC－概念，R是ALC－角色，則（C∩D），（C∪D），（﹁C），（?R.C），（?R.C）都是ALC－概念；

ALC－解釋I＝（ΔI，·I）由非空集合ΔI及解釋函數(shù)·I組成，其中ΔI為論域。解釋函數(shù)·I將概念名映射為ΔI的子集，將角色名映射為ΔI×ΔI的子集，同時滿足下列遞歸語義。

1）（C∩D）I＝CI∩DI；

2）（C∪D）I＝CI∪DI；

3）（﹁C）I＝ΔI＼CI；

4）（?R.C）I＝｛x∈ΔI｜?y∈ΔI，滿足〈x，y〉∈RI，則y∈CI｝；

5）（?R.C）I＝｛x∈ΔI｜?y∈ΔI，滿足〈x，y〉∈RI，則y∈CI｝；

ALC－知識庫KB＝〈T，A〉，其中TBOX的T由形如C≡D的概念定義式及C?D的一般概念包含公理組成的有限集合；AOBX的A由形如C（a）的個體斷言及R（a，b）的角色斷言組成的有限集合。

1.2 ALC中的定義

給定ALC知識庫KB＝〈T，A〉，其主要推理方法有概念包含推理及LCS推理，定義如下［11］：

1）LCS推理。對任意的ALC－概念C1、C2，稱概念C是C1、C2的LCS概念，即C＝LCS（C1，C2），當(dāng)且僅當(dāng)a）對任意概念Ci有Ci?C，其中i＝1，2；b）C為滿足條件a）的最小概念，即若存在概念C′滿足條件a），則C?C′。

2）概念重寫規(guī)則。設(shè)C1和C2是ALC－概念且C2?C1，則C2重寫為C2＝C1∩C＊1。

定義1 設(shè)D是任意ALC－概念，當(dāng)且僅當(dāng)D≡或D≡⊥或D≡D1∩D2∩…∩Dn，且Di＝∪A∈p（Di）A∪∪R∈NR?R.E∪∪R∈NR，V∈VR（Di）?R.V，則D是ALC－概念范式。其中：p（Di）為Di中頂層的概念名或其否定形式組成的集合；E為Di中頂層的、角色R存在限定約束概念的后綴概念的析取，若?R.C∪?R.D，則E＝C∪D；VR（Di）為Di中頂層的、角色R值限定約束概念的后綴概念組成的集合。

定義2 設(shè)C是任意的ALC－概念，當(dāng)且僅當(dāng)C≡A或C≡?R.C或C≡?R.C，則C是單位概念。其中：A為NC中的概念名或概念名的否定形式；?R.C及?R.C中的后綴概念C為復(fù)雜概念或原子概念。

定義3 設(shè)C1和C2是ALC－概念且滿足ALC－概念范式，C1⊙C2為概念C1和C2的異運(yùn)算。令C3≡C1⊙C2，當(dāng)且僅當(dāng)C3由C1與C2中不同的單位概念構(gòu)成的概念，若單位概念間存在包含關(guān)系，則使用概念重寫規(guī)則，消去包含。

2 基于ALC的事例存儲及事例庫結(jié)構(gòu)

CBR中的事例通常采用三元組表示，C＝（Csituation，Cmethod，Csolution），其中：Csituation為問題的描述信息；Cmethod為問題求解方法；Csolution為問題的答案［1］?；贏LC的事例表示將事例表示為知識庫的個體，應(yīng)用知識庫中定義的概念及角色將事例的特征信息用概念表示。

基于描述邏輯的CBR傳統(tǒng)事例庫結(jié)構(gòu)如圖1所示，實線表示概念包含關(guān)系，虛線表示實例關(guān)聯(lián)關(guān)系。其通過描述邏輯ALC中的概念包含推理及實例認(rèn)知推理得到層次結(jié)構(gòu)，實現(xiàn)事例分類。

圖1 傳統(tǒng)事例庫結(jié)構(gòu)Fig.1 The traditional structure of case base

該事例庫結(jié)構(gòu)簡單、實現(xiàn)方便，但存在嚴(yán)重的局限。即隨著事例庫不斷增大，出現(xiàn)很多匹配程度不高的事例的描述概念直接聚集在同一個索引概念下，影響事例的分類效果。如在CBR事例庫recipeResource中存在這種問題，一個索引概念下有上百個關(guān)聯(lián)不大的事例描述概念，而且隨著新事例不斷存儲進(jìn)來情況更嚴(yán)重。導(dǎo)致上述問題的主要原因是知識庫中的索引節(jié)點(diǎn)不能根據(jù)事例描述概念的特點(diǎn)而改變。

由概念間的匹配關(guān)系可知，父子節(jié)點(diǎn)的匹配程度大于兄弟節(jié)點(diǎn)的匹配程度，兄弟節(jié)點(diǎn)的匹配程度大于非兄弟節(jié)點(diǎn)的匹配程度。設(shè)有概念A(yù)、B、C、D，如圖2所示，首先，由于B、C、D是兄弟節(jié)點(diǎn)，存在相同的匹配關(guān)系，無法區(qū)分A、B、C、D間的匹配程度，事例檢索得到的結(jié)果集較大；隨后，由于進(jìn)一步區(qū)分了B、C、D間的匹配關(guān)系，可得C、D的匹配程度最大，事例檢索得到的結(jié)果集相對較小，且更合理。因此，可通過動態(tài)添加合適的索引節(jié)點(diǎn)實現(xiàn)事例更細(xì)致的分類，得到一個合理的事例庫結(jié)構(gòu)，以提高檢索的效率及準(zhǔn)確度。

圖2 概念分類結(jié)構(gòu)Fig.2 The structure of concepts classify

針對上述問題，提出新的事例存儲方法及事例庫結(jié)構(gòu)。

算法1 事例存儲及事例庫結(jié)構(gòu)組織算法。

輸入：待存儲的事例t及其描述概念Ct，知識庫中定義的概念。

功能：將事例t存入事例庫并建立其索引。

輸出：帶權(quán)重的事例庫。

步驟：

1）首先對知識庫中的概念，通過概念包含推理建立初始的事例庫層次結(jié)構(gòu)。

2）通過概念包含推理及實例認(rèn)知推理，將t事例及其描述概念Ct插入事例庫中。令當(dāng)前狀態(tài)下Ct的父概念為Cp，則a）若概念Cp下除Ct外沒有其他子概念，則計算并標(biāo)注d（Cp，Ct），算法終止；b）若概念Cp下存在其他子概念Ci（1≤i≤n），且對任意Ci有d（Cp，Ci）＝1，則計算并標(biāo)注d（Cp，Ct），算法終止；c）若概念Cp下存在其他子概念Cj（1≤j≤m），且對任意Cj有d（Cp，Cj）＞1，則由LCS推理得最小包含概念Ck≡LCS（Ct，Cj）。當(dāng)Ck?Cp，則將Ck插入事例庫中，計算并標(biāo)注父子概念間的距離。

3）每次需要存儲事例時，重復(fù)步驟2）。

通過事例存儲方法得到的新事例庫結(jié)構(gòu)如圖3所示。

圖3 新事例庫結(jié)構(gòu)Fig.3 The new structure of case base

由算法1得到一個節(jié)點(diǎn)密度大且?guī)?quán)重的事例庫結(jié)構(gòu)。通過LCS推理得到新的索引節(jié)點(diǎn)，提高了索引節(jié)點(diǎn)密度，能對事例進(jìn)行更好的分類；通過單位概念及概念距離統(tǒng)一了概念間連接線段的語義，使其具有可比性。

定理1 對相同ALC知識庫及事例描述概念，設(shè)由算法1得到的事例庫結(jié)構(gòu)為CB1，由傳統(tǒng)方法得到的事例庫結(jié)構(gòu)為CB2，則CB1中索引概念平均關(guān)聯(lián)的事例數(shù)n1小于等于CB2中索引概念平均關(guān)聯(lián)的事例數(shù)n2。

證明 設(shè)當(dāng)前事例庫中共有n個事例，由傳統(tǒng)方法得到的索引概念總數(shù)為m，因為算法1在傳統(tǒng)方法上通過LCS算法產(chǎn)生了新的索引概念，且新索引概念總數(shù)k≥0。因此，在CB1中共有（m＋k）個索引概念，則有n1＝n／（m＋k）≤n2＝n／m。證畢。

3 基于帶權(quán)重的事例庫結(jié)構(gòu)的事例檢索

事例檢索分為初步篩選及相似性度量。初步篩選通過篩選算法從事例庫找到一組與目標(biāo)事例相關(guān)的事例作為候選事例集，篩選策略通常基于特定事例庫結(jié)構(gòu)；相似性度量通過相似性函數(shù)計算候選事例與目標(biāo)事例的相似性，得到候選事例序列。初步篩選是提高事例檢索效率的關(guān)鍵，因為相似性度量的復(fù)雜度通常會很高，所以通過減小候選事例集的大小，可減少相似性比較的次數(shù)，提高檢索效率。

3.1 事例初步篩選

算法2 事例初步篩選算法。

輸入：目標(biāo)事例t及其描述概念Ct，事例庫。

功能：篩選得到一組與t相匹配的事例。

輸出：若干事例。

步驟：

1）通過概念包含推理將事例及描述概念Ct插入事例庫中。

2）令在當(dāng)前狀態(tài)下Ct的父概念為C1，計算Ct與C1的距離d。a）若當(dāng)d＝1，則將與C1直接關(guān)聯(lián)的事例作為候選事例集；若C1沒有直接關(guān)聯(lián)的事例，則將C1的直接子概念關(guān)聯(lián)的事例作為候選事例集，否則，將C1的父概念直接關(guān)聯(lián)的事例作為候選事例集；遞歸執(zhí)行上述步驟直到候選事例集非空。b）當(dāng)d＞1，則使用算法1得到Ct的新父概念C2，并執(zhí)行a）得到候選事例集。

通過初步篩選得到源事例集與目標(biāo)事例的匹配程度最大。因為概念間存在精確匹配Q＝D，完全匹配Q?D，嵌入匹配D?Q，潛在匹配Q∩D≠⊥，部分匹配Q∩D＝⊥。匹配關(guān)系程度為：精確匹配≥完全匹配≥嵌入匹配≥潛在匹配≥部分匹配。

定理2 給定ALC知識庫、事例的描述概念及檢索條件Ct，由算法1得到的事例庫為CB1，由傳統(tǒng)方法得到的事例庫為CB2，則有基于CB1篩選得到的候選事例數(shù)量n小于等于基于CB2篩選得到的候選事例數(shù)量m。

證明 設(shè)在CB2中以Ct為條件，篩選得到索引概念C直接關(guān)聯(lián)的事例；在CB1將篩選得到索引概念C或其子概念關(guān)聯(lián)的事例，且該子概念D只可能存在于CB1中。若CB1中存在子概念D，則C直接關(guān)聯(lián)的事例將變少，且C與D直接關(guān)聯(lián)事例數(shù)的和等于CB2中C關(guān)聯(lián)的事例數(shù)，因此n＜m。若CB1不存在子概念D時，則CB1與CB2中C直接關(guān)聯(lián)的事例數(shù)相同，即n＝m。證畢。

由定理2可知，初步篩選算法得到的候選事例集較小。

3.2 相似性度量算法

對目標(biāo)事例t、源事例集｛a，b，c，…｝及其相應(yīng)的描述概念Ct、Ca、Cb等，在計算相似性前，需轉(zhuǎn)換為ALC－概念范式，Ct≡Cp∩Ctj∩…∩Ctn，Ca≡Cp∩Cai∩…∩Cam。根據(jù)概念的結(jié)構(gòu)特點(diǎn)及為了計算的便利，只考慮頂層合取符號兩邊的子概念的權(quán)重，則事例間的相似性為：

概念Ct與Ca的相似性由其相同的子概念及相交的子概念共同決定。由算法1可知，Ct與Ca相同部分在最小包含概念Cp中，可能相交的子概念為C1≡Ctj∩…∩Ctn與C2≡Cai∩…∩Cam。因此，

其中w12為C1、C2中各部分的權(quán)重和。由外延法可得C1、C2相似性度量為

由圖3所示事例庫可得概念間的距離d，對任意概念C、D，其距離d（C，D）等于連接概念C、D的線段標(biāo)注的數(shù)字和的最小值。在不考慮權(quán)重的情況下，距離越大則差別越大，修正的難度也越大。因此，當(dāng)多個源事例與目標(biāo)事例的相似性相同時，可通過距離進(jìn)一步區(qū)分，得到候選事例集序列。

相似性度量函數(shù)滿足標(biāo)準(zhǔn)相似性函數(shù)的3個性質(zhì)：對稱性、非負(fù)性及自反性。因此，式（1）是一個正確的相似性度量函數(shù)，可用于事例的相似性度量。

4 結(jié)束語

根據(jù)事例的描述概念，應(yīng)用LCS推理及概念距離算法，得到了事例索引節(jié)點(diǎn)密度大且?guī)?quán)重的事例庫，基于該事例庫給出了事例檢索算法。該結(jié)構(gòu)能對事例進(jìn)行更細(xì)致的分類，降低了候選事例集的大小。通過事例庫LCS概念及概念間距離更容易區(qū)分事例的相似性。該事例庫結(jié)構(gòu)為事例檢索提供更有效的支持，提高了事例檢索效率。

［1］史忠植.高級人工智能［M］.北京：科學(xué)出版社，2006：78－99.

［2］Watson I.Case－based reasoning is a methodology not a technology［J］.Knowledge－Based Systems，1999，12（5）：303－308.

［3］Changchien S W，Lin Mingchin.Design and implementation of a case－based reasoning system for marketing plans［J］.Expert Systems with Applications，2005，28（1）：43－53.

［4］Napoli A，Lieber J，Simon A.A classification－based approach to case－based reasoning［C］／／Proceedings of International Workshop on Description Logics，1997：246－250.

［5］Salotti S，Ventos V.Study and formalization of a casebased reasoning system using a description logic［C］／／Smyth B，Cunningham P.Advances in Case－Based Reasoning.Berlin Heidelberg：Springer，1998：286－297.

［6］Sánchez－Ruiz A A，Ontanón S，González－Calero P A，et al.Measuring similarity in description logics using refinement operators［C］／／Ram A，Wiratunga N.Case－Based Reasoning Research and Development.Berlin Heidelberg：Springer，2011：289－303.

［7］Cojan J，Lieber J.An algorithm for adapting cases represented in ALC［C］／／Walsh T.Proceedings of the Twenty－Second International Joint Conference on Artificial Intelligence.Menlo Park：AAAI Press，2011：2582－2589.

［8］Recio－Garía J A，Díaz－Agudo B.Ontology based CBR with jCOLIBRI［C］／／Ellis R，Allen T.Applications and Innovations in Intelligent Systems XIV.London：Springer，2007：149－162.

［9］Janowicz K.Sim－DL：towards a semantic similarity measurement theory for the description logic ALCNR in geographic information retrieval［C］／／Meersman R，Tari Z.On the Move to Meaningful Internet Systems.Berlin Heidelberg：Springer，2006：1681－1692.

［10］Baader F，Nutt W.Description Logics Handbook［M］.Cambridge：Cambridge University Press，2003：47－100.

［11］唐素勤，蔡自興.描述邏輯非標(biāo)準(zhǔn)推理［J］.模式識別與人工智能，2010，23（4）：522－530.