基于可变容差关系的变精度粗糙集模型

摘要：针对已有不完备信息系统扩展粗糙集模型对噪声鲁棒性差的局限性，首先分析了调节基本知识粒大小的同时引入相对错误分类度的必要性；然后结合系统属性值的缺失定义了对象联系度权值矩阵，并以此为基础提出了基于可变容差关系的变精度粗糙集模型（VPRSVPTR）；接着讨论了模型的性质，分析了模型中相关参数（基本知识粒大小、相对错误分类度）对分类精度的影响，给出了分类精度随模型中相关参数变化的求解算法与时间复杂度分析；最后通过仿真实验与相关研究的扩展粗糙集模型进行对比。仿真结果显示，VPRSVPTR分类精度更高，而且针对UCI数据库上的几组不完备数据集进行仿真实验的结果还表明，相同参数下各不完备数据集的测试集和训练集分类精度变化趋势相同，进而验证了模型的有效性、灵活性及所提算法的可行性。

关键词：粗糙集；可变容差关系；知识粒度；变精度；分类精度

中图分类号： TP18； TP311.13

文献标志码：A

Variable precision rough set model based on variableprecision tolerance relation

ZHENG Shumei， XU Xinying*， XIE Jun， YAN Gaowei

College of Information Engineering， Taiyuan University of Technology， Taiyuan Shanxi 030024， China

Abstract：

Focusing on the underdeveloped robustness when the existing extended rough set model encounters the noise for the incomplete information system， the necessity of adjusting the size of basic knowledge granule as well as introducing the relative degree of misclassification was analyzed. Then the Variable Precision Rough Set model based on VariablePrecision Tolerance Relation （VPRSVPTR） was established on the basis of the object connection weight matrix， which was proposed according to the lack probability of system attribute value. Moreover， the properties of the VPRSVPTR model were discussed， the classification accuracy under the basic knowledge granule size and the relative degree of misclassification was analyzed， the corresponding algorithm was depicted and the time complexity analysis was given afterwards. The experimental results show that the VPRSVPTR model has higher classification accuracy compared with some other research about the expanded rough set， and the change trend of the classification accuracy is similar for the train set and the test set of several groups of incomplete data sets in UCI database. It proves that the proposed model is more precise and flexible， and the algorithm is feasible and effective.

Key words：

rough set； variable tolerance relation； knowledge granule； variable precision； classification accuracy

0引言

经典粗糙集理论[1]的核心思想是“粒化”和“逼近”。所谓“粒化”即利用等价关系将论域中的对象进行划分，得到基本知识粒；所谓“逼近”即对论域空间中任意不确定、不精确或模糊的未知概念用所得的基本知识粒进行近似描述。经典粗糙集在处理完备信息表时，无需引入论域空间之外的先验信息，因操作简单且能客观反映问题本质，在短期内得到了迅速发展。

然而，实际中的系统大多不完备且受噪声影响，针对这样的不完备信息系统，再利用等价关系进行“粒化”势必造成所得基本知识粒过细，不利于未知概念的简单刻画。为此，Kryszkiew[2]提出容差关系，Stefabowski等[3-4]提出非对称相似关系、量化容差关系，王国胤等[5-6]提出限制容差关系、改进的完备容差关系，杨习贝等[7]提出特征关系，刘富春[8]提出修正容差关系，盛立等[9]提出完备容差关系，另外还有联系度容差关系[10]。这些关系下提出的扩展粗糙集模型丰富了粗糙集的理论体系和知识框架，拓展了粗糙集在图像处理中的应用[11-12]。但这些扩展粗糙集[2-10]在进行粒化时，都基于这样一种假设――对象间对应属性值一旦有确定的差异，就一定不能粒化在同一知识粒中。例如y1=（3，2，3，5，4，0，0，6，5）和y2=（3，1，3，5，4，0，0，6，5）一定不能粒化在同一基本知识粒，而y3=（3，*，*，*，*，*，*，*，*）却有可能和y1或y2粒化在同一基本知识粒中。但从直观上判断，上例中y1和y2属于同一基本知识粒的可能性更大。针对这一局限，徐怡等[13]提出基于（α，λ）联系度容差关系的变精度粗糙集模型，高阳等[14]提出基于（α，τ）限制相似关系的变精度粗糙集模型，这些模型从理论上解决了以上问题，但并没有给出模型中涉及到的相关参数的具体取值方法，一定程度上限制了模型的应用。另外，对文献[2-12]所提出的模型进行性能评价时，只是针对主观给出的未知概念进行定性评价，而没有定量评价。对此，本文充分利用分类精度，将其作为模型可行性和有效性的评价指标。

本文首先分析了调节基本知识粒大小的同时引入相对错误分类度[15]的必要性；然后结合系统属性值的缺失定义了对象联系度权值矩阵，以此为基础提出可变容差关系，该关系不仅克服了文献[2-10]假设的局限性，而且考虑了信息系统本身对论域中对象间关系的影响；接着将可变容差关系与Ziarko[15]提出的多数包含关系相结合，提出基于可变容差关系的变精度粗糙集模型（Variable Precision Rough Set model based on VariablePrecision Tolerance Relation， VPRSVPTR），并讨论了它的性质，分析了其中相关参数对分类精度的影响；最后通过实验仿真，验证了模型的有效性和灵活性及相关算法的可行性。

1相关概念

设信息系统S=（U，A∪D），其中：U={x1，x2，…，xn}是对象集；A={a1，a2，…，am}是条件属性集；D是决策属性集；F为U到A的映射集，即F=fa：Uva（aA）。若至少存在一个属性a∈A，使得va包含空值，则称信息系统S不完备，否则为完备的。若无特殊说明，本文均以*表示信息系统中的空值，且规定对任意的a∈A，va至少包含一个确定值。

1.1Ziarko变精度粗糙集模型

定义1[15]设U是一个有限的非空对象集，对X，YU，令：

e（X，Y）=1-|X∩Y|/|X|，|X|≠0

0，|X|=0

其中：|・|表示集合“・”的基数，e（X，Y）表示集合X对于集合Y的相对错误分类度。令0≤β

定义2[15]设不完备信息系统S=（U，A），0≤β

Aβ（X）={x∈U|e（[x]A，X）≤β}

β（X）={x∈U|e（[x]A，X）

由[Aβ（X），β（X）]得到的粗糙集模型，称为变精度粗糙集模型。

1.2粒化、逼近模型的相关局限性分析

如图1所示，当“粒化”的基本知识粒为较大知识粒时，X1的下近似为，上近似为整个论域U。造成这种结果的原因是基本知识粒太粗，所以需要适当地将基本知识粒调细。但这并非表示，基本知识粒越细越好，因为用太细的基本知识粒“逼近”论域中的未知概念时不仅描述不简洁，还会使后期知识推理产生太多规则。故对论域进行“粒化”时，应根据待描述未知概念本身选择合适的基本知识粒。

这种通过调节基本知识粒来描述未知概念的方法能客观、准确地突出未知概念本身的局部特性，却对其数据全局性特征缺乏认识。

如图2所示，X2所代表的未知概念，其形状更接近一个矩形。若用较大知识粒作为基本知识粒对X2进行描述，其下近似为，上近似为整个论域左边2/3区域；若用较小知识粒作为基本知识粒对X2进行描述，上近似缩小了范围，下近似所在区域为一不规则图形，不符合我们的直观认识。这就说明单纯在“粒化”过程中调节基本知识粒大小无法在保证计算效率的前提下，有效描述X2的这一特征。

这种情况下，若结合Ziarko提出的多数包含关系对X2进行“逼近”，不仅可以大幅提升效率，而且可以从整体上把握X2的数据全局性特征。比如用较大知识粒作为基本知识粒，并引入相对错误分类度β来定义X2的上、下近似，可以得到其上、下近似均为一个矩形，和直观认识的矩形颇为相似；若此处用合适的较小知识粒作为基本知识粒，并引入β来逼近X2，虽然其上、下近似没有改变，但计算效率会明显下降。

由此可见，单纯改进“粒化”或“逼近”均有其局限性， 故本文根据待描述信息本身，平衡分类精度和时间效率两个方面，对“逼近”和 “粒化”同时调节，提出基于可变容差关系的变精度粗糙集模型。模型既考虑基本知识粒“粒化”的准确性和简洁性，又兼顾未知概念的数据全局性特征。

2可变容差关系下变精度粗糙集

2.1可变容差关系下变精度粗糙集的概念

定义3设不完备信息系统S=（U，A∪D），F为对象集U到条件属性集A的映射集，即F=fa：Uva（aA）。则对xs，xt∈U，在A下的对象联系度权值矩阵PA定义为：

PA={pA（s，t）}={∑aApa（xs，xt）}； s， t=1，2，…，n

且当s=t时，pa（s，t）=m-1（aA）；当s≠t时：

pa（xs，xt）=

m-1，a（xs）=a（xt）∧a（xs）≠*∧a（xt）≠*

（m|vmax|）-1，a（xs）=*∨a（xt）=*

-（m|vmin|）-1，a（xs）≠a（xt）∧a（xs）≠*∧a（xt）≠*

定义3中|vmax|=maxaA（|va|），|vmin|=minaA（|va|），且规定|va|表示va中非“*”元素的个数，因为对任意的a∈A，va至少包含一个非空值，故|va|为[1，|A|]区间的整数。

显然矩阵pa（s，t）依对角线对称，故分析计算时，只需计算其上三角（或下三角）。

例1

下面以表1所示的简单不完备信息系统为例，说明对象联系度权值矩阵的求法。

定义4设不完备信息系统S=（U，A∪D），pA为对象集U在条件属性集A下的对象联系度权值矩阵，δ∈（0，1]，则对xs，xt∈U，其基于属性集A的可变容差关系BδA（xs，xt）定义为：

BδA（xs，xt）={（xs，xt）∈U×U|pA（s，t）≥δ}

相应地，对x∈U，其可变容差关系类BδA（x）定义为：

BδA（x）={y|y∈U∧BδA（x，y）}

显然BδA（xs，xt）满足自反性、对称性，不满足传递性，因为BδA（xs，xt）满足对称性，故BδA（xs，xt）又可记为BδA。

为说明定义4中参数δ的意义，参考文献[16]在不完备信息系统中提出的知识粒度的概念给出如下定义5。

定义5设不完备信息系统S=（U，A∪D），BδA是可变容差关系，且U/BδA={BδA（x1），BδA（x2），…，BδA（x|U|）}，则A的知识粒度定义为：

GK（A）=1|U|2∑|U|i=1|BδA（xi）|

定义5中，δ的变化直接影响着A的知识粒度，且一般地，随着δ变大，A的知识粒度变小，其区分能力增强；随着δ变小，A的知识粒度变大，其区分能力减弱。

定义6设不完备信息系统S=（U，A∪D），其中U={x1，x2，…，xn}是对象集，A={a1，a2，…，am}是条件属性集，0≤β

Aδβ（X）={x∈U|e（BδA（x），X）≤β}

δβ（X）={x∈U|e（BδA（x），X）

由[Aδβ（X），δβ（X）]得到的粗糙集模型，称为基于可变容差关系的变精度粗糙集模型（VPRSVPTR）。显然，当δ=1，β=0时，VPRSVPTR退化为Pawlak的经典粗糙集模型。

定义7设不完备信息系统S=（U，A∪D），集合簇U/D={X1，X2，…，XN，}表示决策属性集D对论域U进行等价划分的结果，BδA表示属性集A下的可变容差关系，则对0≤β

dA（D）=

∑Nk=1|Aδβ（Xk）|/∑Nk=1|δβ（Xk）|

dA（D）描述了用属性集A分类时，能够确定类别的样本比例，是属性分类优劣的度量。

2.2可变容差关系下变精度粗糙集的性质

定义8设不完备信息系统S=（U，A∪D），对象集合XU，则X在属性集A下基于可变容差关系的β正区域POSδβ（X），β负区域NEGδβ（X），β边界域BNDδβ（X）分别定义为：

POSδβ（X）={x∈U|e（[x]A，X）≤β}

NEGδβ（X）={x∈U|e（[x]A，X）≥1-β}

BNDδβ（X）={x∈U|β

由定义8可推出定理1成立。

定理1

设不完备信息系统S=（U，A∪D），则对XU，有下面的关系式成立：

POSδβ（～X）=NEGδβ（X）

其中～X=U-X。

证明由POSδβ（～X）的定义知：

x∈POSδβ（～X）e（[x]A，～X）≤β即

1-|BδA（x）∩（～X）||BδA（x）|≤β|BδA（x）∩（～X）||BδA（x）|≥1-β，

又

|BδA（x）∩（～X）|=|BδA（x）|-|BδA（x）∩X|，故1-|BδA（x）∩X||BδA（x）|≥1-βe（[x]A，X）≥1-β，即

x∈POSδβ（～X）x∈NEGδβ（X）；

同理有x∈NEGδβ（X）x∈POSδβ（～X）。

证毕。

性质1设不完备信息系统S=（U，A∪D），对于X，Y∈U，有：

1）Aδβ（X）X，Xδβ（X）；

2）Aδβ（）==δβ（），Aδβ（U）=U=δβ（U）；

3）δβ（X∪Y）δβ（X）∪δβ（Y）；

4）δβ（X∩Y）δβ（X）∩δβ（Y）；

5）Aδβ（X∪Y）Aδβ（X）∪Aδβ（Y）；

6）Aδβ（X∩Y）Aδβ（X）∩Aδβ（Y）。

证明

1）Aδβ（X）X对x1，x2U，由：

e（BδA（x1），X）≤β∧e（BδA（x2），X）≤βe（BδA（x1）∪BδA（x2），X）≤β

恒成立。事实上由定理1可知：

e（BδA（x1），X）=|BδA（x1）∩（～X）||BδA（x1）∩（～X）|+|BδA（x1）∩X|≤β

（1）

e（BδA（x2），X）=|BδA（x2）∩（～X）||BδA（x2）∩（～X）|+|BδA（x2）∩X|≤β

（2）

由式（1）、（2）相加得：

|BδA（x1）∩（～X）|+|BδA（x2）∩（～X）|≤

β[|BδA（x1）∩（～X）|+|BδA（x1）∩X|+

|BδA（x2）∩（～X）|+|BδA（x2）∩X|]

变形为：

e（BδA（x1）∪BδA（x2），X）=|（BδA（x1）∪BδA（x2））∩X||（BδA（x1）∪BδA（x2））|≤β

证毕。

同理可证Xδβ（X）。

2）由xUe（BδA（x），）=1，所以Aδβ（）=且δβ（）=；

同理由xUe（BδA（x），U）=0，所以Aδβ（）=，δβ（U）=U。

证毕。

3）δβ（X∪Y）δβ（X）∪δβ（Y）x∈U， X，YUe（BδA（x），X∪Y）≤e（BδA（x），X）且e（BδA（x），X∪Y）≤e（BδA（x），Y），事实上根据定义1及集合的性质知上式恒成立。证毕。

同理可证5）。

4）δβ（X∩Y）δβ（X）∩δβ（Y）x∈UX， YUe（BδA（x），X∩Y）≥e（BδA（x），X）且e（BδA（x），X∩Y）≥e（BδA（x），Y），事实上根据定义1和集合的性质知上式恒成立。证毕。

同理可证6）。

2.3分类精度随δ、β的变化趋势分析

为验证所建模型的有效性，首先需要分析分类精度dA（D）随δ、β变化的趋势。

为分析dA（D）=∑Nk=1|Aδβ（Xk）|/∑Nk=1|δβ（Xk）|，只需分析对X，d′A（D）=|Aδβ（X）|/|δβ（X）|的变化趋势。

设E为基本知识粒，根据定义1，定义2知：

d′A（D）=

|Aδβ（X）|/|δβ（X）|=

||E∩X|/|E||≥1-β|

||E∩X|/|E||≥β|

因为β∈[0，0.5），对β，1-β>β，故d′A（D）∈[0，1]。

1）当δ不变，β增大时，下近似增大或不变，上近似减少或不变，故d′A（D）增大或不变；

2）当β不变，δ增大时，基本知识粒变小，d′A（D）整体上呈增长趋势，但也有可能变小。

基于上述分析，为直观显示分类精度dA（D）随δ及β变化而变化的三维趋势图，特给出如下算法1。

算法1可变容差关系BδA下条件属性A依β的分类精度dA（D）的求解算法。

输入不完备信息系统S=（U，A∪D），基本知识粒大小影响指标δ的步长δstep，相对错误分类度β的步长βstep；

输出分类精度dA（D）随δ及β的变化趋势三维图。

步骤1计算[n，m]=size（data）。

步骤2计算对象联系度权值矩阵PA={pA（s，t）}。

步骤3计算决策属性D对论域U进行等价划分的结果U/D={X1，X2，…，XN，}。

步骤4初始化p=1，dA（D）=[]。

步骤5画三维趋势图，核心代码如下：

程序前

δ=0：δstep：m

β=0：βstep：0.5

[P，Q]=meshgrid（floor（δ/δstep+1），（δ/βstep+1））；

mesh（β， δ， dA（D））；

程序后

算法时间复杂度分析：设不完备信息系统中样本数为n，条件属性个数为m。算法1的时间主要消耗在步骤2和步骤4上，其中：步骤2的算法时间复杂度为O（n2m），步骤4的算法时间复杂度为O（0.5n2m/（δstep*βstep））。可见δstep、βstep的取值越小，算法1的时间复杂度越大。

3仿真实验与分析

实验分两部分：第一部分是针对表2所示的不完备信息表进行仿真实验，目的是和文献[2-6]的扩展粗糙集相比较分析，以验证VPRSVPTR模型的有效性和准确性；第二部分是选用University of California Irvine（UCI）数据库[17]中的几组不完备数据集进行仿真，以进一步验证针对VPRSVPTR模型所提算法的可行性和高效性。

实验1如表2所示S=（U，A∪d）为文献[6]中的不完备信息系统，其中对象集U=（x1，x2，…，x12），条件属性集A={a1，a2，a3，a4}，决策属性集为{d}，则{d}对论域U的划分结果为：

Ψ={x1，x3，x5，x10，x12}，Φ={x2，x4，x6，x7，x8，x9，x11}。

1）针对表2，若取δ的步长δstep=0.0025，相对错误分类度β的步长βstep=0.0100，据算法1作出dA（d）随δ、β变化趋势如图3所示；若取δstep=0.0250，βstep=0.0500，据算法1作出dA（d）随δ、β变化趋势图如图4所示。

比较图3、4可知：当δstep、βstep取值较大时，dA（d）随δ、β变化趋势并没有显著改变，但计算时间却大幅减少。故实际计算中，为得到分类精度随δ、β变化的趋势图，取较大δstep、βstep即可。

2）分析图3，可知当δ为[0，1]内的固定值时，dA（d）随β的增大而增大，但这种增长趋势为非严格的阶梯型增长趋势；反之，当β为[0，0.5]内的固定值时，dA（d）随δ的增大却不一定增大，例如：当β=0.2500时，dA（d）随δ的变化趋势如图5所示。

3）先求出特定的δ、β值下各对象的可变容差关系类，然后得到Ψ、Φ的下近似和上近似，进而将结果与文献[2-6]提出的其他扩展粗糙集作比较分析。

①取δ=1.8300，β=0.3400，求得各对象的可变容差关系类为：

BδA（x1）={x1}，BδA（x2）={x2，x3}，

BδA（x3）={x2，x3}，BδA（x4）={x4}，BδA（x5）={x5}，BδA（x6）={x6，x7}，BδA（x7）={x6，x7，x9}，BδA（x8）={x8}，BδA（x9）={x7，x9，x11，x12}，BδA（x10）={x10}，BδA（x11）={x9，x11，x12}，BδA（x12）={x9，x11，x12}。

则VPRSVPTR模型下，Ψ、Φ的下近似、上近似分别为：

Aδβ（Ψ）={x1，x5，x10}， δβ（Ψ）={x1，x2，x3，x5，x10}；

Aδβ（Φ）={x4，x6，x7，x8，x9，x11，x12}，

δβ（Φ）={x2，x3，x4，x6，x7，x8，x9，x11，x12}；

dA（d）=0.7143。

②文献[6]中，针对表2求得各扩展粗糙集模型下Ψ、Φ的下近似、上近似结果如下：

容差关系下：

ΨB=， ΨB=U， ΦB=， ΦB=U； dA（d）=0.0000。

非对称相似关系下：

ΨB={x1，x10，x12}， ΨB={x1，x2，x3，x4，x5，x9，x10，x11，x12}；ΦB={x6，x7，x8，x9}，

ΦB={x2，x3，x4，x5，x6，x7，x8，x9，x11，x12}；

dA（d）=0.3684。

限制容差关系下：

ΨB={x1，x10}， ΨB={x1，x2，x3，x4，x5，x9，x10，x11，x12}；ΦB={x6，x7，x8}， ΦB={x2，x3，x4，x5，x6，x7，x8，x9，x11，x12}；dA（d）=0.2632。

改进的完备容差关系下：

ΨB={x1，x10}， ΨB={x1，x2，x3，x4，x5，x9，x10，x11，x12}；ΦB={x6，x7，x8}， ΦB={x2，x3，x4，x5，x6，x7，x8，x9，x11，x12}；dA（d）=0.2632。

比较分析①、②的实验结果，可知VPRSVPTR模型更准确有效。

实验2为进一步验证针对VPRSVPTR模型所提算法的可行性和有效性，特从UCI数据库[16]中选取几组不完备数据集（具体描述见表3）进行仿真实验。

以Wisconson Breast Cancer为例，仿真时，首先利用其中的489个训练样本得到分类精度dA（d）随δ、β变化趋势图；然后根据分类精度选择对应的δ、β值，对其余210个测试样本进行“粒化”“逼近”并得到新的分类精度，比较相同参数下的测试样本与训练样本的分类精度。

1）分别取δ的步长δstep=0.0063，相对错误分类度β的步长βstep=0.0100，针对表3的4组不完备数据集，根据算法1依次得到分类精度随参数δ、β变化趋势如图6。

2）针对表3的4组不完备数据集，依次参考图6所示的各训练样本分类精度随δ、β的变化趋势图，随机选取几组δ、β值，依次求得各测试样本的分类精度值。比较相同δ、β值下，训练样本和测试样本的分类精度值，结果如表4。

分析表4中的数据可知，随着δ、β取值的不同，针对训练样本和测试数据的分类精度的变化趋势是相同的，且针对测试数据的分类精度比训练样本的分类精度相对较高，进一步说明模型的有效性和灵活性。

4结语

不完备信息系统由于属性值的缺失和遗漏，使得信息系统的不确定性和不精确性大幅增加，因此用经典粗糙集理论对其处理时，需分别对“粒化”和“逼近”作改进和拓展。本文在充分分析粒化、逼近模型相关局限性的基础上，提出了VPRSVPTR模型，讨论了VPRSVPTR的性质，给出了相关算法和时间复杂度分析，并通过分析和实验仿真讨论了模型中相关参数对分类精度的影响，说明了VPRSVPTR模型的可行性和灵活性。下一步的工作是针对该模型提出基于信息熵的属性约简算法，并将该模型应用到图像特征提取上，指导图像分割[18-19]。

参考文献：

[1]

PAWLAK Z. Rough sets [J]. International Journal of Computer and Information Sciences， 1982， 11（5）： 341-356.

[2]

KRYSZKIEWICZ M. Rough set approach to incomplete information system [J]. Information Sciences， 1998， 112： 39-49.

[3]

STEFANOWSKI J， TSOUKIAS A. Incomplete information tables and rough classification [J]. Computational Intelligence， 2011， 17（3）： 545-566.

[4]

STEFANOWSKI J， TSOUKIAS A. On the extension of rough sets under incomplete information [C]// RSFDGrC99： Proceedings of the 7the International Workshop on New Directions in Rough Sets， Data Mining and GranularSoft Computing， LNCS 1711. Berlin： Springer， 1999： 73-81.

[5]

WANG G. Extension of rough set under incomplete information systems [J]. Journal of Computer Research and Development， 2002， 39（10）： 1238-1243. （王国胤.Rough集理论在不完备信息系统中的扩充[J].计算机研究与发展，2002，39（10）：1238-1243.）

[6]

MA X， WANG G， ZHANG Q， et al. Extended rough set model based on improved complete tolerance relation [J]. Journal of Computer Applications， 2010， 30（7）： 1873-1877. （马希鹜，王国胤，张清华，等.基于改进的完备容差关系的扩充粗糙集模型[J].计算机应用，2010，30（7）：1873-1877.）

[7]