基于优化容许关系的集值粗糙集模型及属性约简

摘要：粗糙集理论是一种用于处理不确定性和模糊知识的数学工具，其基本思想是在保持系统分类能力不变的前提下，通过知识约简，导出问题的分类规则。集值信息系统使得粗糙集理论得到更广泛的应用。提出了具有协调性的优化容许关系，并讨论了基于该关系的粗糙集模型，证明了相关性质。讨论了不确定性度量问题，提出了优化容许关系下集值信息系统基于粗糙熵的属性约简，并给出了属性约简算法。

关键词：粗糙集；集值信息系统；优化容许关系；粗糙熵；属性约简

一、前言

波兰数学家Z Pawlak在1982年提出了一种新的数据分析理论——粗糙集理论（Rough Set），由此打开了一扇粗糙集研究的大门。此后，很多数学家、逻辑学家和计算机专家对此进行了深入的研究。作为一种新的处理模糊性（Vagueness）和不确定性（Uncertainty）问题的数学工具，粗糙集理论的基本思想是在维持系统分类能力不变的基础上，借助于知识约简，给出问题的分类规则。模糊集理论、证据理论和概率统计等也是处理不确定性问题的较为常用的数学工具。两相比对，粗糙集理论与它们联系较为紧密，但也同时具有它独有的优越性：在处理不确定性问题时，模糊集理论离不开隶属函数，证据理论离不开基本概率赋值，统计学离不开概率分布，而粗糙集理论则不需要任何关于数据和相应问题间的先验知识或附加信息，而仅仅通过数据自身的不可区分关系，在保持信息系统分类能力不变的前提下，对属性和属性值进行约简，从而得到保持知识能力不变的决策规则。

经典粗糙集以完备信息系统为研究对象，以等价关系（满足自反性，对称性，传递性）为基础。而在现实生活中，由于数据测量的误差、对数据理解或获取的限制等原因，使得在数据获取时往往面临的是不完备信息系统，这就限制了Z Pawlak（经典）粗糙集理论的应用范围。定义适合不完备信息系统的粗糙集模型是粗糙集理论能广泛应用的基本问题之一，集值粗糙集模型是对未知属性值赋予了它所有可能的取值，即给它赋予了该属性值域的一个子集，进而将不完备信息系统向集值信息系统进行转化。这样，集值信息系统就提供了一种卓有成效的方法用来处理不完备信息系统。本文基于改进容许关系的集值粗糙集模型，继续研究，提出新的具有协调性的优化容许关系，建立新的模型。优化容许关系除了具备改进容许关系RB（α，β）[1]所具备的性质和优点外，还有其自身的优点，它的分类精度不低于改进容许关系的分类精度，并且它是一个协调的二元关系，因此它在集值信息系统中能够得到更为广泛应用。

二、基本概念

定义1[2]称（U，A，F）是集值信息系统，若U={x1，…，xn}是对象集，每一个xi（i≤n）叫做一个对象；A={a1，…，am}是属性集，每一个al （l≤m）叫做一个属性；F={fl：l≤m}是对象属性值映射，其中fl：U→P0 （Vl）（l≤m）， Vl是属性al的值域，P0（Vl）表示Vl的非空子集全体。

在粗糙集理论中，一种关系是否为协调关系，对分类结果也会产生重要影响。协调二元关系的定义如下：

定义2信息系统S=（U，A，V，f），R是其上的二元关系，?x∈U，若满足?P，Q?A，P?Q，都有RQ（x）?RP（x），或者满足?P，Q?A，P?Q，都有RQ（x）?RP（x），则称二元关系R是协调的，否则，称之为不协调的。

虽然改进容许关系RB（α，β）有很多的优越性，但是它是一个非协调的二元关系，我们举例说明：在表1中，取B={a1，a2，a3，a4}，B?A，取α=1/3，β=3/5，

得每一对象的相容类分别为：

[x1]RA（α，β）={x1，x2，x4}，[x2]RA（α，β）={x1，x2，x4}，

[x3]RA（α，β）={x3，x6，x9，x10}，[x4]RA（α，β）={x1，x2，x4}，

[x5]RA（α，β）={x5，x6，x10}，[x6]RA（α，β）={x3，x5，x6，x9，x10}，

[x7]RA（α，β）={x7}，[x8]RA（α，β）={x8}，[x9]RA（α，β）={x3，x6，x9}，

[x10]RA（α，β）={x3，x5，x6，x10}。

[x1]RB（α，β）={x1，x2，x4}，[x2]RB（α，β）={x1，x2，x4}，

[x3]RB（α，β）={x3，x6，x9，x10}，[x4]RB（α，β）={x1，x2，x4}，

[x5]RB（α，β）={x3，x5，x6，x9，x10}，[x6]RB（α，β）={x3，x5，x6，x9，x10}，

[x7]RB（α，β）={x7}，[x8]RB（α，β）={x8}，[x9]RB（α，β）={x5，x6，x9}，

[x10]RB（α，β）={x3，x5，x6，x10}。

显然，[x3]RA（α，β）?[x3]RB（α，β），并且[x3]RB（α，β）?[x3]RA（α，β），所以RA（α，β）是集值信息系统（U，A，F）上的不协调的二元关系。

?C?B?A，由于RB（α，β）的非协调性，使得我们不能够断定RA（α，β）与RB（α，β）的关系，也不能断定RB（α，β）与RC（α，β）的关系，即RA（α，β）?RB（α，β）与RB（α，β）?RA（α，β）可能都不成立，RC（α，β）?RB（α，β）与RB（α，β）?RC（α，β）也可能都不成立。以上结果会造成我们在求基于改进容许关系下的集值信息系统属性约简时的计算难度，从而限制了改进容许关系在集值信息系统中的广泛应用。

为了弥补改进容许关系的以上不足，下面我们在改进容许关系的基础上进行适当修改，把其扩充为新的二元关系，以便新模型能在保持原有模型良好性能基础上会有更广泛的应用。

三、集值信息系统中基于优化容许关系的粗糙集模型

在集值信息系统（U，A，F）中，B?A，xi，xj∈U。记

，SB（xi，xj）={al∈B|fl（xi）=fl（xj），|fl （xi）|=1}。

我们将改进容许关系RB（α，β）进行修正，得到具有协调性的优化容许关系。

定义3优化容许关系RB（α，β）：

。

并记[xi]R'B（α，β）={xj∈U|（xi，xj ）∈R'B（α，β）}为xi的相容类。显而易见，优化容许关系R'B（α，β）具备等价关系中的对称性和自反性，却未必具备传递性。

优化容许关系R'B（α，β），通过合理设置参数α，β的值，同样能填充R*B[3]限制性太强、RB∩ [4]和RBα [5]限制性太宽的不足，这里不再举例说明。

定义4设（U，A，F）是一个集值信息系统，X?U，B?A。则对X的R'B（α，β）有以下概念：

—R'B（α，β）（X）={xi∈U│[xi ]R'B（α，β）∩X≠?}=∪{[xi ]R'B（α，β） |xi∈X}为上近似集，—R'B（α，β）（X）={xi∈U│[xi ]R'B（α，β）?X}={xi∈X│[xi ]R'B（α，β）?X}为下近似集，

posR'B（α，β） （X）=—R'B（α，β） （X）为正域，

negR'B（α，β）（X）=U-—R'B（α，β） （X）为负域，

bnR'B（α，β）（X）=—R'B（α，β）-（X）-—R'B（α，β） （X）为边界。

由关系R'B（α，β）定义 X的近似精度ρR'B（α，β）为：

四、基于优化容许关系的粗糙集模型的相关性质

优化容许关系R'B（α，β）的相关性质除了具备改进容许关系RB（α，β）所具备的性质外（这里不再一一列举），还具有下面的性质：

性质1 设（U，A，F）是一个集值信息系统，则?B'?B?A，有

R'B'（α，β）?R'B（α，β）?R'A（α，β）。

证明：?（xi，xj ）∈R'B'（α，β），有clij ≥α，且；

因为B'?B，所以|SB' （xi，xj）|≤|SB （xi，xj）|，

从而，

于是（xi，xj）∈R'B（α，β），R'B'（α，β）?R'B（α，β）。

同理可证R'B（α，β）?R'A（α，β）。从而R'B'（α，β）?R'B（α，β）?R'A（α，β），结论成立。

优化容许关系R'B（α，β）的近似分类精度不小于改进容许关系RB（α，β）的近似分类精度，即：

定理1集值信息系统（U，A，F），?X?U，?B?A，RB（α，β）、R'B（α，β）分别是其上的改进容许关系和优化容许关系，则ρR'B（α，β） （X）≥ρRB（α，β），其中

证明：?（xi，xj）∈R'B（α，β），即clij ≥α，且，因为B?A，所以   ，因此（xi，xj）∈RB（α，β）。即，?xi∈U，R'B（α，β）（xi）?RB（α，β）（xi），

从而，—R'B（α，β） （X）?—RB（α，β） （X），—R'B（α，β） （X）?—RB（α，β） （X），故ρR'B（α，β） （X）≥ρRB（α，β）（X）。

即结论成立。

五、优化容许关系下的集值信息系统中的不确定性度量

随着粗糙集理论研究的深化，一种新的不确定性——粗糙性，即信息系统中存在的知识和概念的不确定性，逐渐被人们认识和接受。信息系统的不确定性主要由两个原因引起：一个原因来自论域上的二元关系及其产生的模块，模块的平均大小度量信息系统的不确定性，定义为知识的粗糙性；这种不确定性的另一个原因来自给定近似空间的粗糙集的边界，边界越大知识就越粗糙，处理这种不确定性可以使用粗糙度（或近似精度）来完成，称之为概念的粗糙性。

知识的粗糙性和概念的粗糙性是粗糙集理论中不确定性问题研究的两个主要方面。在粗糙集理论中，知识被认为是信息系统中的一个属性子集。基于知识是区分对象能力的思想，知识实质上是由属性子集决定的对象空间的划分或覆盖，因此知识的粗糙性可以被认为是近似空间中基本知识粒的粗糙性。在粗糙集理论中，一个概念通过对象集来描述，如果概念不能被属性所决定的基本知识粒精确描述，则称这个概念为粗糙的。对于一个概念，在一个近似空间中可能是粗糙的，但是在另一个近似空间却可能是精确的。所以概念的粗糙性源于一个近似空间提供的基本信息粒度。所以概念的粗糙性最终受知识粗糙性的影响。总之，系统所有属性所决定的基本知识粒的粗糙性决定了一个信息系统的粗糙性。

知识的信息熵和知识的信息粒度是知识的不确定性度量的两个比较经典的方法，目前已有各种各样的知识信息熵和知识信息粒度的定义形式，它们在度量知识的不确定性方面也都有各自很好的表现。下面我们基于知识的粗糙熵来讨论知识的不确定性度量。

先将完备信息系统中知识距离的定义推广到优化容许关系下的集值信息系统中。

（一）优化容许关系下的集值信息系统中的知识距离

在上面讨论的基础上，我们给出优化容许关系下的集值信息系统中的知识距离的定义：

定义5集值信息系统（U，A，F），R'A（α，β）是其上的优化容许关系，?P，Q?A，知识P，Q之间的距离定义为：

定理2对于集值信息系统（U，A，F），R'A（α，β）是其上的优化容许关系，K（U）是其中的所有知识组成的集合，则?P，Q?A，（K（U），d）也构成距离空间，并且对于K（U）中的任意两个知识P，Q，d（P，Q）有界，即：

（1）0≤d（P，Q）≤1；

当且仅当P≈Q时，d（P，Q）=0，当且仅当U/R'P（α，β）=ω，U/R'Q（α，β）=δ或者U/R'P（α，β）=δ，U/R'Q（α，β）=ω时，d（P，Q）=1（其中，ω是论域上的恒等关系，δ为论域上的全域关系）；

（2）d（P，Q）=d（Q，P）；

（3）d（P，R）≤d（P，Q）+d（Q，R）。

性质2集值信息系统（U，A，F）中，若?B?A，P，Q?A且P≠Q，则在优化容许关系R_B^（'（α，β））下，P，Q之间的最大距离为1，最小距离为—  |U|（1|U|-1）   。

证明：设U/R'P（α，β）={[u1]R'P（α，β），[u2]R'P（α，β），…，[u|U|]R'P（α，β）}，

U/R'Q（α，β） ={[u1]R'Q（α，β），[u2]R'Q（α，β），…，[u|U|]R'Q（α，β）。

当U/R'P（α，β） =ω，U/R'Q（α，β）=δ或者U/R'P（α，β）=δ，U/R'Q（α，β）=ω时，d（P，Q）取到最大值1，其中，ω是论域上的恒等关系，δ为论域上的全域关系，即  U/R'P（α，β）={{u1}，{u2}…，{u|U|}}，

U/R'Q（α，β）={{u1，u2，…，u|U|}，{u1，u2，…，u|U|}…，{u1，u2，…，u|U| }}；d（P，Q）取到最小值—  |U|（1|U|-1）  ，当且仅当存在唯一一个i0∈{1，2，…，|U|}，有

|[ui0]R'P（α，β）⊕[ui0]R'Q（α，β）=1，且?i≠i0，i∈{1，2，…，|U|}，[ui]R'P（α，β）=[ui]R'Q（α，β）。证毕。

（二）优化容许关系下的集值信息系统中的知识粗糙性

下面我们用知识距离定义知识的粗糙熵，并用知识的粗糙熵来度量知识的粗糙性。

定义6集值信息系统（U，A，F）中，R'A（α，β）是其上的优化容许关系，?P?A，知识P的粗糙熵定义为：

E（P）=d（P，ω）=—  |U|（1|U|-1）  ∑i=1i=|U||[ui]R'P（α，β）⊕{ui}|。

其中，U/R'P（α，β）={[u1]R'P（α，β），[u2]R'P（α，β），…，[u|U|]R'P（α，β）}，

U/R'ω（α，β），{u2}…，{u|U|}。规定，E（?）=0。

知识粗糙熵的性质：

（1）有界性：0≤E（P）≤1。

（2）单调性：若P?Q，则E（P）≤E（Q）。

但是，E（P）=E（Q）推不出P=Q，也就是说不同的知识可能有相同的粗糙熵。

定理3（知识的粗糙不变性[6]）信息系统中任意两个知识P，Q?A，

U/R'P（α，β）={[u1]R'P（α，β），[u2]R'P（α，β），…，[u|U|]R'P（α，β）}，

UR'Q（α，β）={[u1]R'Q（α，β），[u2]R'Q（α，β），…，[u|U|]R'Q（α，β）}。

若存在一个一一映射f：U→U，，使|[ui]R'P（α，β）|=|[ui]R'Q（α，β）|，?i=1，2，…，|U|成立，则E（P）=E（Q）。

以上我们已经详细讨论了优化容许关系下的集值信息系统中知识的粗糙性问题，给出了集值信息系统在优化容许关系下的知识距离的定义，讨论了其相关性质，并用知识间的距离定义了知识的粗糙熵；用知识粗糙熵来度量信息系统中知识的不确定性。

六、集值信息系统在优化容许关系下基于知识粗糙熵的属性约简

作为粗糙集理论的其中一个焦点问题，约简包括属性约简与属性值约简等。通常情况下，信息系统中的各种属性的重要性一般不一样，某些条件属性甚至是冗余的。冗余属性会造成两方面的不利影响：首先，由于它需要处理时间和存储空间，从而对资源造成了一定的浪费；其次，它会对研究人员做出正确、简洁的决策造成一定的困扰。这样说来，属性约简在粗糙集理论中重要性就不言而喻了。

所谓属性约简，是指在维持知识库分类能力不变的基础上，去掉里面不相关或者不重要的属性[2]。一般而言，属性约简是由信息系统的属性约简和决策表的决策规则的约简组成的。可以维持原系统特定信息的属性叫做系统的约简。找出决策规则中对决策结论有影响的条件属性叫做决策规则的约简，或者叫做对象的约简或值约简。

前面讨论了基于知识信息熵和知识信息粒度的知识粗糙性的度量，接下来我们利用知识粗糙熵来讨论信息系统的属性约简。

定义7集值信息系统S=（U，A，F），?B?A，R'B（α，β）是其上的优化容许关系，属性a∈A在A中的重要性sigA （a）表达式是：sigA （a）=E（A）-E（A＼{a}），它反映了从A中除去a的前后知识粗糙熵变化情况。

特别当A={a}时，sig{a}（a）=E（{a}）-E（?）=E（{a}） 。

属性重要性的性质：

性质1 sigA （a）≥0。

性质2 属性a∈A在A中是不可或缺的，当且仅当sigA （a）>0。

性质3 CORE（A）={a∈A|sigA （a）>0}，称为A的核属性，它由A中所有的必要的属性组成。

下面来定义集值信息系统在优化容许关系下基于知识粗糙熵的属性约简中，属性集外的属性对属性集的重要性，以方便在求出信息系统的核属性后，能够尽快的求出信息系统的属性约简。

定义8优化容许关系下的集值信息系统S=（U，A，F），B?A，a∈A-B，a对B的重要性定义为：B中添加a后引起的知识粗糙熵变化的大小，即：

sigB （a）=E（B∪{a}）-E（B）。

a对B是必要的，当且仅当sigA （a）>0。

下面给出集值信息系统在优化容许关系下基于知识粗糙熵的属性约简的定义：

定义9集值信息系统S=（U，A，F），B?A，R'B（α，β）是其上的优化容许关系，称B是S的一个约简，如果E（B）=E（A），并且?b∈B，E（B＼＼{b}）≠E（A）。

由以上讨论我们给出基于知识粗糙熵的属性约简算法：

输入：一个优化容许关系下的集值信息系统S=（U，A，F）。

输出：系统的约简。

第1步：计算系统的知识粗糙熵E（A）；

第2步：计算CORE（A）={a∈A|sigA（a）>0}，C?CORE（A）；

第3步：计算E（C），如果E（C）=E（A），那么算法结束，否则（E（C）

第4步：（1）对每个属性a∈A-C，计算sigC（a）；

（2）选择属性重要性最大的属性，即选择属性a满足：

a'∈A-Cmax{sigC（a'）并C?C∪{a}；

（3）计算E（C）；

（4）如果E（C）=E（A），那么算法结束，否则，转（1）。

以上给出了集值信息系统在优化容许关系下，基于知识粗糙熵的属性约简，并给出了约简算法，可以看出属性约简在粗糙集理论中的重要地位。

七、结语

基于优化容许关系，本文提出了一种新的集值粗糙集模型。这个模型填充了RBα未考虑取值明确且相等属性对相容度影响、RB*限制性过高、RB∩宽松度过大的不足。由于改进容许关系RB（α，β）的非协调性，往往会造成我们在求基于改进容许关系下的集值信息系统属性约简时的计算难度，从而限制了改进容许关系在集值信息系统中的广泛应用。阐述了不确定性度量问题的主要方法，提出了优化容许关系下集值信息系统的基于知识粗糙熵的属性约简，并给出了约简算法。

粗糙集理论从诞生到现在，已经被广泛应用到许多领域。譬如在人工神经网络、决策分析、智能控制、图像处理、模式识别、知识发现、故障诊断和数据挖掘等很多领域都有着广泛应用。近年来，不少研究者在粗糙集理论的应用上继续探究，譬如文献[ 7]将粗糙集理论应用在小区夜间用水量分析的漏损识别研究实际问题上。

下一步工作是在本文提出的优化容许关系的基础上，进一步研究不完备系统中属性约简和规则抽取算法，为实际应用系统开发奠定理论基础。

参考文献

[1]陶志，李桂秋.基于集值信息系统的改进粗集模型[J].中国民航大学学报，2010，28（6）：45-48.

[2]张文修，梁怡，吴伟志.信息系统与知识发现[M].北京：科学出版社，2003.

[3]宋笑雪，李鸿儒，张文修.集值信息系统的知识约简与属性特征[J].计算机工程，2006，32（22）：26-27+36.

[4]宋笑雪，解争龙，张文修.集值决策信息系统的知识约简与规则提取[J].计算机科学，2007，34（4）：182-184+191.

[5]陈子春，秦克云.集值信息系统基于变精度相容关系的知识约简[J].计算机工程与应用，2008，44（9）：27-29，32.

[6]王宝丽，梁吉业.信息系统中的知识距离与知识粗糙熵[J].计算机科学，2007，34（3）：151-154.

[7]储文强，陈功，胡鸿昊.结合粗糙集属性约简和夜间用水量分析的漏损识别研究[J].科技通报，2021，37（9）：94-98+108.

基金项目：1.广东省普通高校特色创新类项目（项目编号：2018KTSCX160）；2.广州市科技计划项目（项目编号：201804010088）

作者单位：广东第二师范学院数学学院

责任编辑：尚丹