基于极大相容块的区间集粗糙集

赵曼君，马建敏，杨璇

（长安大学 理学院，陕西 西安 710064）

0 引言

Pawlak粗糙集［1-2］是处理不确定性问题的一种工具，其主要思想是运用等价关系将论域进行划分形成基本知识粒即等价类，通过利用等价类与目标集的关系，构建上、下近似集来刻画目标集。目前，粗糙集理论已被广泛应用于知识发现、图像处理、数据挖掘、人工智能［3-6］等领域。

Pawlak粗糙集基于等价关系构建，信息系统完备且属性值单一。但在实际问题中，信息系统不完备或属性值较复杂，等价关系不再适用，经典粗糙集的应用也受到限制。为解决这一问题，许多学者对等价关系进行扩展，提出了邻域关系、相似关系、相容关系、优势关系［7-11］等，并构建了对应关系的粗糙集模型。基于相容关系的粗糙集模型应用较为广泛，其主要思想是通过相容关系产生论域的基本知识粒，构建对应的粗糙集模型。但相容关系产生的基本知识粒不能构成论域的划分，不同的知识粒可能具有相同的对象，造成对象被误判的问题。基于此，Leung等［12］构建了基于极大相容块的粗糙集模型，证明了该粗糙集模型较基于相容关系的粗糙集模型精度更高。许多学者应用极大相容块研究不完备信息系统［13-15］。文献［16］给出了快速获取极大相容块的方法。钱宇华等［17-18］从粒计算角度出发，提出乐观多粒度粗糙集和悲观多粒度粗糙集。文献［19］提出了基于极大相容块的多粒度概率粗糙集，并将其应用到多属性群决策问题中。

由于在实际应用中有些概念往往不能精确定义，概念的外延也难以用实例精确表达，Yao［20］利用已知概念作上、下界对未知概念进行描述，提出了区间集，并应用于检测、评估等［21-22］。胡宝清［23］将区间集引入粗糙集， 研究了区间集粗糙集及其三支决策。为提高对分类的容错能力，马建敏等［24］提出了区间集概率粗糙集。

针对连续型数据中概念不能被精确表达，且等价关系不适用等，为了提高近似精度，本文提出连续型信息系统中基于极大相容块的乐观和悲观区间集粗糙集。首先用基于距离的相容关系刻画连续型数据的关系，提出基于极大相容块的乐观和悲观粗糙集模型。进而将极大相容块引入区间集粗糙集中，提出基于极大相容块的乐观、悲观区间集粗糙集。利用区间集相似度，给出几类区间集粗糙集的精度刻画。最后，选取UCI数据集中五组数据集进行实验，验证本文所提极大相容块下的两类区间集粗糙集在刻画精度方面的有效性。

1 基础知识

本节介绍区间集粗糙集、相容关系及极大相容块，参考文献见［1-2，12，20，23，25-27］。

1.1 区间集粗糙集

用|X|表示集合的基数，文献［2］定义了X关于属性集A的近似精度为：

定义 1［20］设 U={x1，x2，…，xn}是 有 限 论域，2U是U的幂集。U上的区间集X定义为：

U上所有区间集的集合用I(2U)表示，即I(2U)={X=[Xl，Xu]：Xl⊆ Xu⊆ U}，称 为 U 的区间集幂集。

基于集合的交、并、差、补等运算，Yao定义了区间集的运算［20］：对任意 X=[Xl，Xu]，Y=[Yl，Yu]∈ I(2U)，

对 任 意 X=[Xl，Xu]，Y=[Yl，Yu]∈ I(2U)，I(2U)上的偏序关系“⊑”定义为：

于是，X⊑Y⇔X⊓Y=X⇔X⊔Y=Y。

定义 2［23］设 S=(U，AT，V，f)是 信 息 系统，A⊆AT。对任意 X=[Xl，Xu]∈I(2U)，X基于属性子集A的粗糙下、上近似分别定义为：

应用文献［25］中区间集的相似度，文献［26］给出了由X的下、上近似刻画X的区间集精度为：

1.2 相容关系和极大相容块

Leung等［12］在不完备信息系统中定义了极大相容块，研究了基于极大相容块的粗糙集。Sun等［19］提出了模糊信息系统中基于极大相容块的多粒度概率粗糙集。本文基于2范数引入相容关系，研究信息系统上的极大相容块。

定义 3［27］设 S=(U，AT，V，f)是 信 息 系统，A⊆AT。对任意x，y∈U，γ>0，U上的二元关系定义为：

其中，dA(x，y)为x，y关于属性子集A的距离：

易知，TA为U上的相容关系。记TA(x)={y∈U：(x，y)∈TA}表示x关于属性A的 相容类。

定义4 设 S=(U，AT，V，f)是信息系统，A⊆AT，X⊆U。 若对任意 x，y∈X，都 有(x，y)∈TA，则称X关于A是相容的。进一步，若不存在Y⊆U，使得X⊂Y，且Y关于A是相容的，则称X是A上的极大相容块。

定义5 设 S=(U，AT，V，f)是信息系统，且A⊆AT。A上所有极大相容块构成的集合记为：

用Cx(A)={Y∈C(A)：x∈Y}表示所有包含x的极大相容块构成的集合。

2 基于极大相容块的两类粗糙集

下面应用信息系统上的极大相容块， 提出基于极大相容块的乐观、悲观粗糙集。

由（3）即得（4）和（5）的结论成立。

性质2 设 S=(U，AT，V，f)是信息系统，A ⊆AT。 对任意 Xi⊆U(i=1，2，…，n)，下 列性质成立：

证明 由定义6，性质1（3）可得结论成立。

定义7 设 S=(U，AT，V，f)是信息系统，且A⊆AT。对任意X⊆U，X基于极大相容块C(A)的悲观粗糙下、上近似分别定义为：

3 基于极大相容块的区间集粗糙集

定义8 设 S=(U，AT，V，f)是信息系统，A⊆AT。 对 任 意 X=[Xl，Xu]∈I(2U)，X 基 于极大相容块C(A)的乐观区间集粗糙下、上近似分别定义为：

4 实例分析

表 1为应急预案评估表(U，AT，V，f)， U={x1，x2，…，x20} 是 应 急 预 案 集 ， AT={a1，a2，…，a5}是应急预案评估指标集 ，V={1，2，3}是应急预案在评估指标下的评估值，评估值越高说明该应急预案可行性越高。规定：3个及以上评估值大于等于2的应急预案可行性较高，3个及以上评估值小于2的应急预案可行性较低。

由题知，可行性一定高的应急预案集X={x2，x5，x6，x10，x12，x16}，可行性一定低的应急预案 集 Y={x1，x3，x4，x9，x8，x11，x15，x18，x19}。 故 可行性可能高的应急预案集YC={x2，x5，x6，x7，x8，x10，x12，x13，x14，x16，x17， }x20。 故X⊆YC。记 Xl=X，Xu=YC，得区间集 X=[Xl，Xu]，表示可行性比较高的应急预案的可能集合。

取γ=1.9，计算AT上所有极大相容块构成的集合：

X的下界Xl和上界Xu基于极大相容块C(AT)的乐观粗糙下、上近似分别为

故X基于极大相容块C(AT)的乐观区间集粗糙下、上近似分别为

由上述计算结果可以看出，基于极大相容块的粗糙集精度比基于相容关系的粗糙集精度更高。且基于极大相容块的区间集粗糙集精度也比基于相容关系的区间集粗糙集精度更高。

5 UCI数据实验

下面利用UCI上的五组数据进行实验（见表2），对比基于极大相容块的乐观粗糙集、乐观区间集粗糙集的精度，和基于相容关系的粗糙集、区间集粗糙集的精度。

表3-表7给出五组数据在γ取不同值时极大相容块的个数，乐观粗糙集、乐观区间集粗糙的精度，和相容关系下粗糙集、区间集粗糙集的精度，其中γ的取值根据每组数据集计算出来的对象之间的距离来选取。

从表3-表7可以看出，随着γ的变化，极大相容块的个数、乐观粗糙集的精度和乐观区间集粗糙集的精度、相容关系粗糙集的精度及相容关系区间集粗糙集的精度都在不断变化.且在五组数据集上，基于极大相容块的乐观粗糙集精度比基于相容关系的粗糙集精度普遍都高， 平均提高33%；同样，基于极大相容块的乐观区间集粗糙集的精度也比基于相容关系的区间集粗糙集的精度高，平均提高33%。

6 结论

本文应用极大相容块讨论区间集粗糙集，提出了基于极大相容块的乐观和悲观区间集粗糙集。将基于距离的相容关系引入信息系统中得到极大相容块，定义了基于极大相容块的乐观、悲观粗糙集。进而将极大相容块引入区间集粗糙集，提出了基于极大相容块的乐观、悲观区间集粗糙集，研究了两种模型的性质和近似精度。应用实例计算基于极大相容块的乐观、悲观区间集粗糙集及其精度。最后通过UCI数据集上的五组数据，验证了本文所提极大相容块下的模型较之相容关系下对应模型的优势。

该模型的提出一定程度上解决了概念不能被精确表达时如何对目标集进行近似刻画。但在对象较多时，计算极大相容块的困难随之增大。下一步将研究如何快速计算得到极大相容块，以及基于极大相容块的多粒度区间集粗糙集，应用于解决公路、桥梁应急预案评估及检测等实际问题中。