相似粗糙集理论在CBR系统中的应用研究

于 杨，许少华，陈秀红 (大庆石油学院计算机与信息技术学院，黑龙江 大庆 163318)

相似粗糙集理论在CBR系统中的应用研究

于 杨，许少华，陈秀红 (大庆石油学院计算机与信息技术学院，黑龙江 大庆 163318)

针对连续型属性离散化对相似度计算造成的影响，给出了一种基于相似粗糙集的属性权值计算方法，并提出基于相似粗糙集的CBR系统案例推理模型。经实例验证，该方法在先验知识不足且连续型属性众多的案例推理应用中具有很好的适用性。

相似粗糙集；CBR；决策表；相似关系；属性权值

在基于案例推理CBR(Case Base Reasoning)系统中，从案例库中自动提取出有用而具有代表性的案例是案例推理的一个重要步骤。为了更准确的获取案例，近年来，人们提出了多种案例获取的方法。如基于AHP的CBR系统案例检索模型[1]，应用本体的分布式案例推理方法[2]等。但这些方法在案例提取过程中，针对属性权值的选定，都要求有很准确的领域先验知识，并加入了很多主观因素。为了解决这一问题，文献[3～5]提出了应用粗糙集理论进行案例推理的方法，取得了很好的效果。但该方法要求对案例中定量的连续属性值进行属性离散化，而大多数的属性离散化方法都会产生案例相似度测量误差, 造成案例推理的不准确性。为此，笔者基于相似粗糙集理论，提出了一种基于相似粗糙集的案例推理模型及案例筛选原则，建立了在先验知识不足的情况下利用粗糙集理论计算特征权值的模型，给出了案例相似性评估方法，提高了相关案例提取的准确性。

1 基本理论与方法

在相似粗糙集(Similarity Rough Set,SRS)理论中，知识被认为是一种对客观事物进行分类的能力，为规范化起见，往往将考察的客观事物称为对象。通常，在SRS中，知识系统可以定义为S=(U,A,V,f)，其中,U为论域，表示一组有限非空的对象集；A=C∪D表示属性的集合，其中,C={c1,c2,…,cp}是条件属性集合；D={d1,d2,…,dp}为决策属性集合；V=∪Va是所有属性值域的集合，其中a∈A，Va为属性a的值域；f=U×A→V是一个信息函数，表示U中每个对象的属性取值[3,4]。

1.1决策表

通过以上方式定义的知识系统可以方便地用表格来实现其中列表示属性，一个属性对应一个等价关系，一行表示一个对象，一个表可以看作是被定义的一族等价关系的集合。知识表达系统的数据表可分为决策表与非决策表。其中，决策表是一种特殊而重要的知识表达系统，在决策应用中起着至关重要的作用。当数据表中的决策属性集不为空时，该数据表便可称为决策表，一般的决策表都是单决策属性表，即p=1。

1.2属性相似度计算

对象的属性可以根据取值范围的不同分为连续型属性与枚举型属性。对于不同类型的属性，其相似度的计算方法如下：

定义1(属性相似度[7]) 设i与j为决策表中的2个不同对象，Vi与Vj分别表示i和j在属性a上的取值，Va min与Va max表示属性a的最小与最大取值， 表示对象i和j在属性a上的相似程度，则对于连续型属性有：

(1)

对于枚举型属性有：

(2)

从以上定义可以看出，属性相似度的取值Sa(i,j)∈[0,1]，故可以为属性选定一个相似阈值ta∈[0,1]，当且仅当Sa(i,j)≥ta时，对象i与j在属性a上相似。

1.3属性权值确定

属性权值的大小反映了在案例相似性评估中各特征属性的相对重要程度，取值的不同将直接影响到评估结果。目前，常用的定权方法主要有专家咨询法、成对比较法、调查统计法、 无差异折衷法以及相关分析法等。在上述方法中，前4种方法一般是在领域专家先验知识的基础上通过事先假设或采用平权的办法来确定特征属性的权重值，无疑会给最相似实例检索的准确性造成影响；后一种方法基于一种统计的方法，相对于前者有一定的进步，但从总体看，传统的案例特征属性定权方法过分依赖于主观判断和经验[5]。

在CBR系统中应用粗糙集理论，其本质是在无先验知识或先验知识不足以及特征属性确定的情况下，根据实际数据来确定各特征属性在最终案例推理中所起的作用大小，即属性权值。为了达到这一目的，引入以下定义[6～11]：

定义2(相似关系) 设一个属性子集B⊆A，定义B上的相似关系为SIMB(i,j)，对象相似阈值为t∈[0,1]，集合的基为card(*)，则当且仅当

(3)

时称对象i与j在属性集B上相似，记为SIMB(i,j)。即只要i与j在属性集B中的一部分属性相似，就可以认为对象i与j在属性集B上相似，这个“一部分”占属性集B的比例由对象相似阈值t确定。把所有在属性集B上与对象i相似的集合(也叫对象i在相似关系SIMB上的相似类)记做：

SIMB(i)={j∈U:SIM(i,j)}

(4)

SIMB-(X)={x∈X:SIMB(x)⊆X}

(5)

其中，X的下近似表示对应相似类SIMB(x)一定能归入X的所有元素x的集合，而X的上近似则表示所有可能归入X的元素的集合。

定义4(相似粗糙集的正域) 设U/d表示对象集U依据决策属性d进行的划分，属性集B⊆A，决策属性d依据相似关系，相对于B的正域记为POSB(d)，则有：

(6)

正域表示根据相似关系SIMB，能够确定划入U/d类的对象集合。

定义5(属性集的分类能力) 不同属性集对对象的分类能力不同，用rB(d)表示根据相似关系SIMB，属性集B⊆A在决策属性d上的分类能力，则有：

(7)

定义6(属性权值) 对于同样的决策属性d，每个条件属性的重要程度不同，这种重要程度经过权值化之后便成为了属性权值，设KB(a)与WB(a)分别表示在相似关系SIMB下，条件属性a的重要度及权值，则有：

KB(a)=rB(d)-rB-{a}(d)

(8)

(9)

显然有：

0≤KB(a)lt;rB(d)≤1 0≤WB(a)≤1

1.4属性约简

定义7(属性约简) 对属性集B⊆A，依据相似关系，如果有POSB(d)=POSA(d)且不存在B1⊂B令POSB1(d)=POSB(d)，则称属性集B为A的一个约简。

2 基于SRS的案例推理模型

图1 基于SRS的案例推理模型

如图1所示，基于SRS的案例推理的过程可以分为权值定期维护、案例推理与案例重用3个阶段。其中权值定期维护是笔者讨论的重点，它包括以下5个重要步骤：

1)根据式(3)计算相对于所有条件属性集及决策属性集的相似关系；

2)计算相对所有缺少一个条件属性的属性集的相似关系；

3)根据式(5)、(6)、(7)和式(8)计算出属性的重要度；

4)根据重要度对属性集进行约简；

5)根据式(9)对属性重要度进行权值化处理。

3 实 例

表1为一个简化的压裂酸化效果案例库，下面以其为例进行权值的计算。

表1 压裂酸化效果案例

设c1表示产层有效厚度，c2表示含油饱和度，c3表示渗透率，c4表示有效孔隙度，c5表示油层压力，c6表示泥质含量，d表示压裂效果。

首先，选取阈值ta与t分别为0.75与0.8，经Step1与Step2可以得出：

U/C={{1，2，5}，{3}，{4}，{6}，{7}}}U/d={{1，2，5，6}，{3，4，7}}

U/C-c1={{1，2，5，6}，{3}，{4}，{7}}}U/C-c2={{1，2，5，7}，{3}，{4}，{6}}}

U/C-c3={{1，2，5}，{3}，{4}，{6}，{7}}}U/C-c4={{1，2，5}，{3}，{4}，{6}，{7}}}

U/C-c5={{1，2，5，6}，{3}，{4}，{7}}}U/C-c6={{1，2，5，7}，{3}，{4}，{6}}}

之后，根据式(5)、(6)、(7)计算出：

根据式(8)可以得出各属性的重要度为：

由于属性c3与c4的重要度为0，故在计算权值与推理的过程中可以将去掉，这样就得到了一个条件属性集的约简 。根据式(9)它们的权值分别为：

4 结 语

笔者介绍了SRS的基本概念与理论，并说明它在CBR中应用的特点和优势。在提出基于SRS案例推理模型的同时，给出应用相似粗糙集计算属性权值的方法，并给出了计算实例。当然，在应用SRS进行权值计算时，阈值的选取会产生很大影响。因此，研究如何对阈值选取进行优化将十分有意义，有待于进一步深入研究。

[1]屈喜龙, 杜娟, 孙林夫. 一个基于AHP的CBR系统实例检索模型[J]. 计算机应用研究, 2005,22(4)：33～35.

[2]丁剑飞，何玉林，李成武.基于本体的分布式CBR设计系统[J].计算机工程, 2007,33(21)：183～185.

[3]Salarno M，Golobardes E.Rough sets reduction techniques for Case-based reasoning[J].Pro-ceedings of ICCBR，2001：466-482.

[4]季赛，沈星，沈超.基于粗糙集和相似度量的CBR检索方法[J].计算机工程与应用, 2006,42(13):172～174.

[5]孙翎，张金隆，迟嘉昱.基于粗糙集的CBR系统案例特征项权值确定[J].计算机工程与应用, 2003,39(30):44～46.

[6]Lu Yi-juan，Ni Zhi-wei，Hu Cai-ping.Technique used in CBR based on similarity rough set[J].Computer Engineering，2003，29(19)：50～51.

[7]季赛，袁慎芳，成亚萍.基于相似粗糙集的CBR范例提取算法[J].小型微型计算机系统, 2007,(6):1072～0175.

[8]卢亦娟，倪志伟，胡彩平.基于相似粗糙集的范例推理技术[J].计算机工程，2003,(19):50～51.

[9]Kryszkiewicz M. Rough set approach to incomplete information systems[J].Information Sciences, 1998.39～49.

[10]胡可云，陆玉昌，石纯一.粗糙集理论及其应用进展[J].清华大学学报(自然科学版)，2001，(1):64～68.

[11]吴今培，孙德山.现代数据分析[M].北京：机械工业出版社，2006.102～104.

[编辑] 易国华

TP18；TP31

A

1673-1409(2009)01-N065-04

2008-12-24

于杨(1984-)，男，2006年大学毕业，硕士生，现主要从事图像处理及模式识别方面的研究工作。