基于实例推理的配置中相似性的研究

高山武，李迎江，朱永彬

红河学院，云南 蒙自 661100

推理理论和文法在解决实际问题的应用是当前的一个研究热点，基于实例推理(Case-Based Reasoning，简称CBR)的基本思想在于从以往的成功设计中寻找与当前问题最为接近的实例作为问题的初始解，并经过对旧的实例的调整，使之满足新问题的要求，从而生成一个当前问题的解。由于基于实例推理与传统的基于规则推理的方法主要区别在于寻找问题解的过程中直接从以往设计中吸取经验，而不是通过把知识归纳成问题求解的一系列规则，依靠一定的事件去触发规则来搜索、产生问题的解。然而许多问题领域——譬如机械系统设计的方案设计问题的这种规则的归纳和提取具有很大的难度，使之成为基于规则推理系统实现的一个瓶颈，基于实例推理的文法的实现为克服这不足提供了可能性。

通常用距离测度法进行最相似实例的评判，这种相似度量的计算方法没有从系统的组成要素及相互关系角度出发进行系统分析，忽视了组成要素的特性的相似性，导致算出的相似系数不能很好地反映实例的相似程度，而相似学经过长期研究，形成了完整的相似理论和方法，并用数学公式比较准确地刻画了两个相似系统之间的相似程度。本文直接采用相似学中的相似度计算公式算出新问题和实例库中所有实例的相似度，再由相似度排序进行最相似实例的检索，这种方法简单有效。但在相似度量时，特征属性的权重值一般在实际中很难确定，通常是在先验知识的基础上通过事先假设或是采用平权的办法来处理，这种权重值的处理方法都无法证明其正确性，无疑会给最相似实例检索的准确性造成影响，必须先解决这个问题，这就要用到粗集理论，对特征集进行约简。粗集(Rough Set)理论是从知识分类的角度出发的一种新的数据推理方法，主要用于知识的约简和属性依赖性的分析。用粗集理论处理相似度量中属性权重值问题，可以不用事先假定的信息，只利用已有的信息来判断所有的属性，在特定的分类下是否具有同等的重要性，某个特征性的重要性也就是重要程度该特征属性在相似配置中的权重。

1 系统相似及相似度

相似学并不是现代产生的，早期人们在探索自然规律的过程当中，就已经逐渐形成了研究相似现象的方法和理论。牛顿、柯西(Cauchy)等都曾把相似模型成功的应用于工程问题。相似三定理则奠定了相似理论的理论基础。周美立在《相似学》、《相似系统论》两部著作中，建立了新的学科——相似学(Similology)，研究自然界中相似现象的本质，相似性形成原理和演变动力，系统相似的一般规律及其应用。相似学的基本概念定义：相似要素指两个或两个以上系统间存在着共有属性或特征，在数值上存在着差异。将这些共有属性和特征称为相似属性或相似特征，通称为相似要素。

相似元：系统间存在一个相似要素，便在系统间构成一个相似单元，简称相似元，计作：

通过计算相似元的数值量化相似要素的相似程度。设A、B两个系统间某个相似元具有m个特征，计Uj(ai)为要素ai对于第j个特征的特征值，Uj(bi)为要素bi相对于第j个特征的特征值。其比例系数，其中各特征值可以为确定的数，也可以为一个模糊数。

相似元的数值：

式（1）中ui为系统间第i个相似元，wij为第i个相似元中第j个特征的权重。

相似系统A、B间的相似程度则由相似度QA-B表示，相似度的计算公式为：

式（2）中：k，l——A、B系统的要素个数；n——相似元的个数；βi——第i个相似元的权重。式中项表示系统间相似元个数对系统相似度的影响。βiq(ui)项表示第i个相似元数值对系统相似度的影响。

2 特征集的约简（粗集理论的应用）

分析基于实例推理的实例检索是根据新问题的描述进行模式匹配的过程，新问题常常被定义成一组特征属性，检索的目标就是从相似实例库中找出一个最相似的实例。其检索过程是先根据新问题的初始条件中提取特征属性作为检索目标，再用新问题的特征属性值和相似实例集中的每个实例对应的特征属性进行相似度量，算出相似度的大小，找出相似度最大的实例就是最相似的实例。

相似度量时实例的各特征属性所起的作用是不同的，有的起关键作用，有的作用很小，甚至不起作用，而且这种作用的重要性会随着分类的改变而变化。在进行某一分类检索时，利用粗集理论能够算出实例属性重要程度，并且可以根据这种重要程度对各个公有相似特征属性的权重值赋值，如果某些特征属性被认为没有起到预期作用，干扰了实例检索，可以将其删除。

采用粗集理论的知识表达系统S=(U，A)来表示实例，其中，U为非空的有限论域，在实例库中是所有实例的集合；A为非空的属性有限集，包含条件属性C和决策属性D，即C∪D=A，C∩D= φ，C中某一属性a∈A，Va是属性a的值域。

实例集的属性一般均为定性属性，对于定量分析问题可以先采用离散处理，变成定性问题，然后再用粗集理论进行处理。属性的重要性可以用以下两个公式来进行判断，即

去掉属性以后，为

其中，card (·)表示集合的基，用rC-a(D)来判断某一属性a的重要程度，当从条件属性中去掉属性a以后再对库中实例进行分类时，分类U/D的正定域将受到较大影响。

3 权重的确定及相似度计算实例

以集装箱大车行走机构为例，我们取其中的3个属性进行讨论。在进行实例检索并建立不同的索引时，对应的实例中各属性的重要性会有较大差别，如表1。

表1 大车实例定量特征属性表

假设从实例库中检索1组相似实例特征属性参数，论域U由编号为1～5的实例组成，现对5个实例的定量属性进行粗略的离散处理，使其变成定性属性，离散处理结果见表2所列。其中，C={a，b，c}，D={d}，属性 a、b、c中的定性值域0、1、2分别代表各属性的不同定量范围，决策属性d是建立索引时根据动力性能优劣划分的分类，其中，0代表好，1代表一般，2代表较差。

表2 大车实例定性特征属性表

根据(3)式、(4)式，则有

从分析结果可以看出属性b和c对于建立的性能索引是重要的，它将U/D的正域改变得最多，去掉它将不能把3、4实例划入UD的性能分类。因此，属性(b，c)是按性能分类时最重要的两个属性。由于属性a对于UD的正域改变不明显，可以在相似度量时将其去除。按属性(b，c)分别计算所有库中实例和新问题的相似度大小，根据（1）式，n=k=l=3，β1=β1=1/2，设有新问题的描述向量为

将属性a去除后变为

通过检索和相似度量，确定了实例3所对应的大车特征属性和设计的大车特征属性相似度最大，可以调用对应的相关资料作为设计参考依据。

[1]刘长毅，徐诚.机械方案设计中实例检索相似性的研究[J].计算机应用，2000，8：1093-1095.

[2]刘晓冰，董建华.产品配置中相似实例模糊优选法的研究[J].高技术通讯，2003，2：65-69.

[3]王玉，邢渊，朱莉萍，阮雪榆.支持重用的层次智能CBR检索模型[J].机械科学与技术，2000，19：164-168.

[4]周美立.相似学[M].北京：中国科学技术出版社，1993：11-32.

[5]周美立.相似系统论[M].北京：科技文献出版社，1994：27-42.

[6]骆敏舟，周美立.基于特征参数度量的相似系统设计及其应用[J].机械设计与研究，2001，3：11-13.

[7]谭建荣，李涛，戴若夷.支持大批量定制的产品配置设计系统的研究[J].计算机辅助设计与图形学党报，2003，15（8）：931-937.