案例推理中的案例检索技术研究

陈万付

（滁州广播电视大学，安徽 滁州 239000）

案例推理中的案例检索技术研究

陈万付

（滁州广播电视大学，安徽 滁州 239000）

案例推理（Case－Based Reasoning，简称CBR）是一种基于经验知识进行推理的人工智能方法，是对人类认知过程的一种模拟。本文在传统欧氏距离算法的基础上结合了模糊数学的计算方法，提高了推理的效率，克服了传统的只能对确定性指标进行搜索的缺陷。

案例推理；检索；相似度

1 案例推理的基本原理和流程

基于案例的推理是近十几年来人工智能中发展起来的一种重要的推理模式，是一种基于经验知识进行推理的人工智能方法，是对人类认知过程的一种模拟。它的基本原理是：以实例或累积的经验作为储存知识的基础，建立实例库，对面临的新问题加以定义及描述，通过搜索实例库中过去同类问题的求解过程与结果，找到合适的实例作为解决新问题的参考，并以“模拟”、“转换”、“调整”、“合并”等手法修改原有的解决方案以适应新的情景。基于案例的推理的流程如图1所示。

在此过程中，案例检索是案例推理中的重要一环，其实质上就是要在用户给出案件之后，检索系统能够自动地从案例库中找出用户所指定的方面与案件完全相同或相似度最大的案例来，而且要求输出结果能按符合用户的要求的程度进行排序，符合提问程度高的优先输出。

2 案例的检索

案例检索，实质上就是要在用户给出案件之后，检索系统能够自动地从案例库中找出用户所指定的方面与案件完全相同或部分相同的案例来，而且要求输出结果能按符合用户的要求的程度进行排序，符合提问程度高的优先输出［1］。

2.1 案例检索常用方法

案例检索过程分为案例的索引和案例的检索。案例的索引技术通常有三种：最近相邻法、归纳推理法和知识引导法［2］。单独使用以上每种策略都会有各自明显的不足，。案例的检索与案例的索引相对应，分为三种：相联检索、层次检索和基于知识的检索。其中相联检索与案例索引的最近邻法相对应。该算法检查目标案例与案例库中的案例的某种属性的匹配程度，计算各属性匹配程度的加权和，依此决定最佳匹配案例。在众多最近邻法的案例检索方法中，传统的、目前用得最多的相似度计算方法是欧氏距离。

图1 基于案例的推理的流程

2.2 传统的欧拉算法

KNN法是指从案例库中找出与目标案例最相似案例的方法。检索前先为案例的各个特征属性分别指定权值，检索时根据输入案例中特征属性的权值与案例库中各属性的匹配程度计算相似度Sim。或者按照相似度定义公式计算出目标案例与案例库中所有案例间的相似值，然后从中选出距离最小的案例作为最佳目标案例。

定义1 相似度是指两个案例的相似程度。设案例X，K的相似度用Sim（X，K）表示，Sim（X，K）∈［0，1］，且满足条件：

（1）对称性，Sim（K，X）≤Sim（X，K）；

（2）自反性，Sim（X，K）＝1；

定义2 假设案例

其中

在（2）中，当r＝2时，即Dist（X，K）为欧拉距离。

欧拉距离的相似度定义如（3）所示，其中D（X，Y）的计算见（2）。

（4）式中Xij代表第i个案例的第j个属性值，Wj表示第j个属性的权重，n为属性总数，Kj为目标案例K的第j个属性的值。Sim（X，K）为目标案例K与源案例库中第i个案例之间的欧氏距离，Sim（X，K）越小说明它们之间越相似。

2.3 案例的混合检索

据上文知，目前常用的案例的索引算法主要有最近相邻法、归纳推理策略和知识导引法三种。其中最近相邻法的核心思想是计算案例间的相似度，找出一个或多个最大相似度的案例作为其检索结果。使用这种方法时，首先计算目标案例与旧案例对应属性之间的相似度，然后再根据属性的权值计算出案例之间的相似度［3］。故本文首先选择使用最近相邻法，又鉴于在各种选择案例中，描述案例特征的属性很多，且有的特征属性在不同的案例里会有不同的权重值，因此，本文同时也使用了改进TC相似法来检索最优案例。

由于案例库中存储的案例的数量众多，如果需要计算案例库中每一个案例与新问题的相似度，工作量会很大，同时很大一部分计算是没必要的。为了减少计算量，在进行相似度计算之前，先对案例库进行处理，得到候选案例集合，这可以很大的提高案例检索的效率。此即为案例的检索，它常用的方法有三种：相联检索、层次检索和基于知识的检索。本文选择与最近相邻法相对应的案例检索方法，相联检索。本文的案例库将每个案例合作项目设为该案例的作业类别字段，并将案例的作业类别作为第一检索条件。同时由于案例库采用关系数据库技术存储，可将案例特征的第一描述符作为第二检索条件。在出现新问题时本文可以利用搜索语句对众多的案例先后进行两次检索，找出与新问题在这两个检索条件上相匹配的关联案例，形成候选案例集合。

（1）对数据进行归一化处理

对数据进行归一化处理，即把案例属性值按照某种函数归一化到某一无量纲区间，并将所有相关特征属性归一化到同一量级内，以便计算结果能更准确地反映源案例与目标案例间的匹配度。为了使计算结果更为准确，本文引入一种归一化效用函数，将不同量纲的原始特征属性值转换到［－1，1］区间，同时尽可能将特征属性值转换成与原始属性值成正比关系的值。

设S＝（S1，S2，…，Sm－1，Sm）是源案例集，C＝（C1，C2，…，Cm－1，Cn）是案例的属性集，构造特征属性矩阵：

上式中Xij代表第i个案例的第j个属性值。

记第i个特征属性的平均值为¯Cj，j＝1，2，…，n，中间变量为Mij，有：

根据文献［2］将原始特征属性值转换到［－1，1］区间上的效用函数为X′ij，令Xij＝X′ij，可得归一化效用函数为：

Yij＝F（Mij）是一条曲线，其中Mij反映了原始数据Xij与均值的偏离程度：

当Xij＝时候，Mij＝0；

Although it is established that low educational level is associated with low participation rates in CRC screening programs, the results of this study indicate that those with high educational level exhibited less compliance as compared to those of low-intermediate one.

当Xij＞时候，Mij＞0，此时Yij随着Mij的增长而非线性递增；

当Xij＜时候，Mij＜0，此时Yij随着Mij的增长而非线性递减。

通过进一步的研究发现，当Xij＞时，经过转换后其效用函数值Yij大于0，原始值越大效用函数值越大，当原始值Xij＝时，效用函数值Yij达到0.9以上，Xij＞4时，效用函数值Yij接近上限值1。同理，当Xij＜时，经过转换后其效用函数值Yij小于0，原始值越大效用函数值越小，当原始值Xij＝－时，效用函数值Yij达到－0.9以下，Xij＜时，效用函数值Yij接近下限值－1。

（2）特征属性的分类及其对应的相似度计算方法

结合选择案例的特点，将其特征属性分为三类：确定数字属性集（如79%、29%等）、确定符号属性集（如是，不是，有，没有等）和模糊概念属性集［3］。不同类型属性之间的相似度采用不同的计算方式。具体做法如下：

1）确定的数字属性值：该种属性值可以是连续的，也可以是离散的，相似度计算方法为：

式中，max（i）和min（i）分别表示存储在数据库中的经验值，由专家组确定，代表一般情况下该属性的取值范围。起着将特征属性间的绝对差值转为相对差值的作用。当难以确定时，可简单地由专家确定两者之差为一正实数k。

2）确定符号属性值：该种属性值通常用明确的术语表示，如“是”或“不是”、“有”或“没有”等。此种数值的相似度计算为：

3）模糊概念属性值：该种属性值可以认为是一概念变量，所有这样的属性值可构成一项目集［4］。项目集中，每一项目对应一模糊概念。模糊关系和模糊数可以用高斯函数表示，为了简化计算，这里采用基于梯形的模糊集合来模拟模糊属性［5］，其函数为：

所以模糊集的隶属函数为：

式中c，c′，p是参数，一般由领域专家确定。

通过计算两个隶属函数对应余弦的夹角作为模糊集之间的相似度，具有既准确又简单的优点。计算公式为：

（3）最终相似度的计算

为了提高基于案例推理的供应链合作伙伴选择案例检索的准确性，本文结合使用了最邻近法和改进TC相似法计算源案例与目标案例之间的相似度。具体过程为：

①判断目标案例与源案例各个指标的权重是否一样，一样则按②计算最终相似度，如不一样则据③计算最终相似度。

②据最邻近法的相似度定义计算案例之间的相似度。按照上述按照上述不同的计算方法将各个不同种类的特征属性的相似度Sim0（xi，yi）求出，代入式（11）即可得到源案例和目标案例的相似值。

式中，wi为各属性的权重。∑wi＝1初始默认权重由专家评估法给出，如表3－3所示，使用过程中不满足时可以调整。

③据改进TC相似法的相似度定义计算案例之间的相似度。因为目标案例与源案例之间指标的权值不一样，故不能直接使用上述不同类型属性的计算方法计算各指标之间的相似度。本文为了减少案例检索的计算量，减轻系统的负荷，直接对目标案例与源案例的权值进行处理，求其平均值，然后按照上述的计算方法求出各个不同种类的特征属性的相似度Sim1（xi，yi），代入式（12）即可求得源案例和目标案例的最终相似度。

其中，是第i个指标在案例X中的权值，是第i个指标在案例G中的权值

本文的案例检索算法如图2所示：

图1 案例检索算法的流程

从候选案例集中选出相似度最大的案例，此案例即为搜索得到的最优案例。

实践证明，本文案例检索克服了传统算法只能对确定性指标进行计算的缺陷，将传统算法和模糊集的计算方法相结合，大大提高了检索的准确性。

［1］王永成.案例检索的若干问题［J］.情报学报，2000，19（6）：587－591.

［2］栾好利，张翼英，曾 文.基于案例推理的技术研究［J］.沈阳工程学院学报，2005，1（2、3）：95－97.

［3］王建成，李 宁，吴晓明.基于CBR的自行火炮故障诊断系统设计［J］.2006中国控制与决策学术年会论文集，2007.

［4］倪志伟，李学俊，胡彩平，等.基于范例和规则相结合的推理技术［J］.小型微型计算机系统，2004，25（7）：1156－1159.

［5］雷 萍.基于案例推理的供应链合作伙伴选择与评价［J］.集团经济研究，2007：313－314.

［6］杨 健，赵秦怡.基于案例的推理技术研究进展及应用［J］.计算机工程与设计，2008，29（3）：710－713.

［7］刘伯超.供应链合作伙伴选择指标体系研究［J］.现代企业文化，2008：28－29.

［8］乔 忠，陈新辉.关于企业销售量的模糊预测［J］.中国管理科学，2001，9（6）：31－35.

［9］戴闻战.基于三层BP网络的多指标综合评估方法及应用［J］.系统工程理论与实践，1999，5（5）：30－34.

The Research of Case Retrieval in Case-Based Reasoning Technology

Chen Wanfu

Case－Based Reasoning is a kind of artificial intelligent design method of reasoning the experiencial knowledge，and it is also a kind of imitation of human cognitive process.Based on traditional Euclidean Distance Transform，this paper combines computing method of fuzzy mathematics，raises the efficiency of reasoning，and overcomes traditional defect of only searching deterministic index.

case reasoning；retrieval；similarity

C931.2

A

1673-1794（2012）05-0014-03

陈万付（1969－），男，安徽滁州人，讲师，管理学硕士，主要研究方向：中小企业管理。

2012-08-11