基于ALC的事例库结构及检索研究①

马林威，古天龙，徐周波

（桂林电子科技大学 广西可信软件重点实验室，广西 桂林 541004）

基于事例推理（case－based reasoning，简称CBR）是人工智能的一个重要分支［1］，具有获取知识容易、求解效率高等特点，其工作过程可以归纳为一个4R循环模型：事例检索（retrieval），事例重用（reuse），事例修正（revise）及事例保存（retain）。在CBR中事例表示是基础，事例检索是关键。根据事例表示方法的特点设计事例库的结构，进而设计事例检索算法。因此，事例表示方法决定了事例表示的准确性、有效性，对事例检索和事例库结构组织等有很大影响。若使用属性－值对法表示事例，则通常采用关系数据库存储事例，使用SQL查询语句进行事例检索［2］；若使用XML表示事例，则通常采用XML数据库存储事例，通过分析XML文档及相似索引进行检索［3］；若使用基于框架的事例表示法，则通常采用事例及抽象事例间的偏序关系建立事例库层次结构［4］。

随着事例知识及领域知识的复杂化、丰富化，CBR进入知识密集型时代。在知识密集型CBR中，传统的事例表示方法如属性－值对、框架法的知识刻画能力明显不足。由于描述逻辑具有强的知识表示及推理能力，被广泛应用于知识密集型CBR中。已用于事例表示的描述逻辑有C－CLASSIC［5］、εL［6］及ALC［7］等。针对基于描述逻辑的事例表示方法，通常使用概念自动分类推理建立事例库的层次结构［5］，达到对事例分类的效果，如基于描述逻辑的CBR系统jCOLIBRI的事例库［8］。此后，基于描述逻辑CBR研究主要侧重于事例相似性度量的研究［6－7，9］。

现有基于描述逻辑的事例库的建立依赖于知识库中已定义的概念，但知识库中事先定义的概念非常有限且无法满足事例分类的需要，影响事例检索的效率及效果。鉴于此，研究基于描述逻辑ALC的事例库结构，并根据该结构给出了事例检索算法。

1 描述逻辑ALC

1.1 ALC的语法与语义

描述逻辑是一种基于对象的知识表示的形式化工具，是一阶谓词逻辑的可判定子集，具有强的知识表示能力及可判定的推理能力。ALC是最基本的描述逻辑，其基本符号包括由概念名组成的集合NC、由角色名组成的集合NR及由个体名组成的集合NI，通过基本符号递归构造出所有概念。

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及解释函数·I组成，其中ΔI为论域。解释函数·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），当且仅当a）对任意概念Ci有Ci⊆C，其中i＝1，2；b）C为满足条件a）的最小概念，即若存在概念C′满足条件a），则C⊆C′。

2）概念重写规则。设C1和C2是ALC－概念且C2⊆C1，则C2重写为C2＝C1∩C＊1。

定义1 设D是任意ALC－概念，当且仅当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 设C是任意的ALC－概念，当且仅当C≡A或C≡∃R.C或C≡∀R.C，则C是单位概念。其中：A为NC中的概念名或概念名的否定形式；∃R.C及∀R.C中的后缀概念C为复杂概念或原子概念。

定义3 设C1和C2是ALC－概念且满足ALC－概念范式，C1⊙C2为概念C1和C2的异运算。令C3≡C1⊙C2，当且仅当C3由C1与C2中不同的单位概念构成的概念，若单位概念间存在包含关系，则使用概念重写规则，消去包含。

2 基于ALC的事例存储及事例库结构

CBR中的事例通常采用三元组表示，C＝（Csituation，Cmethod，Csolution），其中：Csituation为问题的描述信息；Cmethod为问题求解方法；Csolution为问题的答案［1］。基于ALC的事例表示将事例表示为知识库的个体，应用知识库中定义的概念及角色将事例的特征信息用概念表示。

基于描述逻辑的CBR传统事例库结构如图1所示，实线表示概念包含关系，虚线表示实例关联关系。其通过描述逻辑ALC中的概念包含推理及实例认知推理得到层次结构，实现事例分类。

图1 传统事例库结构Fig.1 The traditional structure of case base

该事例库结构简单、实现方便，但存在严重的局限。即随着事例库不断增大，出现很多匹配程度不高的事例的描述概念直接聚集在同一个索引概念下，影响事例的分类效果。如在CBR事例库recipeResource中存在这种问题，一个索引概念下有上百个关联不大的事例描述概念，而且随着新事例不断存储进来情况更严重。导致上述问题的主要原因是知识库中的索引节点不能根据事例描述概念的特点而改变。

由概念间的匹配关系可知，父子节点的匹配程度大于兄弟节点的匹配程度，兄弟节点的匹配程度大于非兄弟节点的匹配程度。设有概念A、B、C、D，如图2所示，首先，由于B、C、D是兄弟节点，存在相同的匹配关系，无法区分A、B、C、D间的匹配程度，事例检索得到的结果集较大；随后，由于进一步区分了B、C、D间的匹配关系，可得C、D的匹配程度最大，事例检索得到的结果集相对较小，且更合理。因此，可通过动态添加合适的索引节点实现事例更细致的分类，得到一个合理的事例库结构，以提高检索的效率及准确度。

图2 概念分类结构Fig.2 The structure of concepts classify

针对上述问题，提出新的事例存储方法及事例库结构。

算法1 事例存储及事例库结构组织算法。

输入：待存储的事例t及其描述概念Ct，知识库中定义的概念。

功能：将事例t存入事例库并建立其索引。

输出：带权重的事例库。

步骤：

1）首先对知识库中的概念，通过概念包含推理建立初始的事例库层次结构。

2）通过概念包含推理及实例认知推理，将t事例及其描述概念Ct插入事例库中。令当前状态下Ct的父概念为Cp，则a）若概念Cp下除Ct外没有其他子概念，则计算并标注d（Cp，Ct），算法终止；b）若概念Cp下存在其他子概念Ci（1≤i≤n），且对任意Ci有d（Cp，Ci）＝1，则计算并标注d（Cp，Ct），算法终止；c）若概念Cp下存在其他子概念Cj（1≤j≤m），且对任意Cj有d（Cp，Cj）＞1，则由LCS推理得最小包含概念Ck≡LCS（Ct，Cj）。当Ck⊆Cp，则将Ck插入事例库中，计算并标注父子概念间的距离。

3）每次需要存储事例时，重复步骤2）。

通过事例存储方法得到的新事例库结构如图3所示。

图3 新事例库结构Fig.3 The new structure of case base

由算法1得到一个节点密度大且带权重的事例库结构。通过LCS推理得到新的索引节点，提高了索引节点密度，能对事例进行更好的分类；通过单位概念及概念距离统一了概念间连接线段的语义，使其具有可比性。

定理1 对相同ALC知识库及事例描述概念，设由算法1得到的事例库结构为CB1，由传统方法得到的事例库结构为CB2，则CB1中索引概念平均关联的事例数n1小于等于CB2中索引概念平均关联的事例数n2。

证明 设当前事例库中共有n个事例，由传统方法得到的索引概念总数为m，因为算法1在传统方法上通过LCS算法产生了新的索引概念，且新索引概念总数k≥0。因此，在CB1中共有（m＋k）个索引概念，则有n1＝n／（m＋k）≤n2＝n／m。证毕。

3 基于带权重的事例库结构的事例检索

事例检索分为初步筛选及相似性度量。初步筛选通过筛选算法从事例库找到一组与目标事例相关的事例作为候选事例集，筛选策略通常基于特定事例库结构；相似性度量通过相似性函数计算候选事例与目标事例的相似性，得到候选事例序列。初步筛选是提高事例检索效率的关键，因为相似性度量的复杂度通常会很高，所以通过减小候选事例集的大小，可减少相似性比较的次数，提高检索效率。

3.1 事例初步筛选

算法2 事例初步筛选算法。

输入：目标事例t及其描述概念Ct，事例库。

功能：筛选得到一组与t相匹配的事例。

输出：若干事例。

步骤：

1）通过概念包含推理将事例及描述概念Ct插入事例库中。

2）令在当前状态下Ct的父概念为C1，计算Ct与C1的距离d。a）若当d＝1，则将与C1直接关联的事例作为候选事例集；若C1没有直接关联的事例，则将C1的直接子概念关联的事例作为候选事例集，否则，将C1的父概念直接关联的事例作为候选事例集；递归执行上述步骤直到候选事例集非空。b）当d＞1，则使用算法1得到Ct的新父概念C2，并执行a）得到候选事例集。

通过初步筛选得到源事例集与目标事例的匹配程度最大。因为概念间存在精确匹配Q＝D，完全匹配Q⊆D，嵌入匹配D⊆Q，潜在匹配Q∩D≠⊥，部分匹配Q∩D＝⊥。匹配关系程度为：精确匹配≥完全匹配≥嵌入匹配≥潜在匹配≥部分匹配。

定理2 给定ALC知识库、事例的描述概念及检索条件Ct，由算法1得到的事例库为CB1，由传统方法得到的事例库为CB2，则有基于CB1筛选得到的候选事例数量n小于等于基于CB2筛选得到的候选事例数量m。

证明 设在CB2中以Ct为条件，筛选得到索引概念C直接关联的事例；在CB1将筛选得到索引概念C或其子概念关联的事例，且该子概念D只可能存在于CB1中。若CB1中存在子概念D，则C直接关联的事例将变少，且C与D直接关联事例数的和等于CB2中C关联的事例数，因此n＜m。若CB1不存在子概念D时，则CB1与CB2中C直接关联的事例数相同，即n＝m。证毕。

由定理2可知，初步筛选算法得到的候选事例集较小。

3.2 相似性度量算法

对目标事例t、源事例集｛a，b，c，…｝及其相应的描述概念Ct、Ca、Cb等，在计算相似性前，需转换为ALC－概念范式，Ct≡Cp∩Ctj∩…∩Ctn，Ca≡Cp∩Cai∩…∩Cam。根据概念的结构特点及为了计算的便利，只考虑顶层合取符号两边的子概念的权重，则事例间的相似性为：

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

其中w12为C1、C2中各部分的权重和。由外延法可得C1、C2相似性度量为

由图3所示事例库可得概念间的距离d，对任意概念C、D，其距离d（C，D）等于连接概念C、D的线段标注的数字和的最小值。在不考虑权重的情况下，距离越大则差别越大，修正的难度也越大。因此，当多个源事例与目标事例的相似性相同时，可通过距离进一步区分，得到候选事例集序列。

相似性度量函数满足标准相似性函数的3个性质：对称性、非负性及自反性。因此，式（1）是一个正确的相似性度量函数，可用于事例的相似性度量。

4 结束语

根据事例的描述概念，应用LCS推理及概念距离算法，得到了事例索引节点密度大且带权重的事例库，基于该事例库给出了事例检索算法。该结构能对事例进行更细致的分类，降低了候选事例集的大小。通过事例库LCS概念及概念间距离更容易区分事例的相似性。该事例库结构为事例检索提供更有效的支持，提高了事例检索效率。

［1］史忠植.高级人工智能［M］.北京：科学出版社，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］唐素勤，蔡自兴.描述逻辑非标准推理［J］.模式识别与人工智能，2010，23（4）：522－530.