基于效用误差的变精度粗糙集的逼近性能研究

李艳，李坤燕*，李法朝，*，靳晨霞

（1.河北科技大学 理学院，河北 石家庄 050018；2.河北科技大学 经济管理学院，河北 石家庄 050018）

0 引言

自1982年波兰数学家Pawlak［1］提出粗糙集（称之为经典粗糙集）概念以来，学者们结合不同的背景推广了粗糙集模型，并取得了诸多成功的应用。在理论研究方面，文献［2-3］针对经典粗糙集模型不能直接处理具有连续属性值的大规模数据集问题，结合具体案例分析指出，无论采用何种方式的数据离散化方法，均可能导致关键信息丢失、数据过渡拟合、结论失真等现象；文献［4］将经典粗糙集模型中的等价关系推广为相似关系，提出了基于相似关系的粗糙集模型；文献［5-6］将经典粗糙集模型中的等价关系和目标集推广为模糊等价关系和模糊集，提出了粗糙模糊集模型和模糊粗糙集模型，为模糊环境下的数据处理奠定了基础；文献［7］提出了覆盖粗糙集模型，在一定程度上解决了基于相似关系的粗糙集模型不能有效处理关联对象之间的传递性问题；文献［8］针对研究对象的重要性不同，提出了概率空间上的粗糙集模型，给出了粗糙模糊集在概率近似空间上的粗糙性度量模式，为构建数据价值不同的数据决策方法提供了一种理论支撑；文献［9］针对经典粗糙集模型缺乏抗噪音能力和容错性差等问题，以集合之间的包含程度为基础，提出了具有良好可解释性的变精度粗糙集模型；文献［10］提出了三类基于边界域的变精度粗糙集模型；文献［11］以覆盖为基础，对变精度粗糙直觉模糊集进行研究；文献［12］针对现实世界中多个论域之间信息分类和属性约简问题，提出了U×W型双论域变精度粗糙集模型；文献［13］将结构化技术用于变精度粗糙集模型，提出结构化变精度粗糙集模型；文献［14］为了提高对混合型数据的抗噪能力，提出一种混合信息系统的变精度粗糙集模型，并进一步提出对象增加和减少时的动态变精度粗糙集模型。在应用方面，学者们围绕数据挖掘、模式识别等领域存在的现实问题开展了深入的研究，其中最具代表性的应用是属性约简。文献［15］以某种邻域体系下的数据结构特征不变为基准，提出了一种基于邻域粗糙集的属性约简方法；文献［16］通过引入局部等价类的概念，提出了一种称为双局部粗糙集的增强局部粗糙集框架；文献［17］结合粗糙集和人工神经网络，提出基于公差关系的粗糙集理论，并利用近似分类质量不变的条件，提供属性归约算法；文献［18］提出了一种基于模糊粗糙集的广义无监督混合属性约简模型；文献［19］在区间值决策系统中的β分布约简基础上提出了基于差别矩阵的特定类β分布约简算法；文献［20］在辨识矩阵的辅助下研究了具体度量偏好直觉模糊序决策信息系统下的分布约简方法；文献［21］提出了一种改进的概率复合粗糙集模型及分布属性约简方法；文献［22］通过将Pawlak决策系统中的等价关系扩展到区间值决策系统中的相容关系，提出了区间值决策系统的分布约简目标；文献［23］以某种粗糙精度下的数据结构特征不变为基准，提出了一种基于变精度粗糙集的属性约简方法；文献［24］将决策表中相同决策规则出现的次数作为权，提出了带权的决策表的概念，通过辨识矩阵给出了带权决策表的变精度约简算法；文献［25］提出了一种基于最小误分类程度的变精度模糊粗糙集模型，以误分代价不变为准则，给出了一种启发式属性约简算法。

综合上面的文献概述可以得到：1）以包含度为基础的相关理论可以有效地描述数据决策、数据处理问题中的不确定性特征；2）变精度粗糙集模型是最具应用价值的数据处理工具；3）在粗糙集的逼近性能方面，虽然有关于错误价值的一些研究，但缺乏对“错找到”和“未找到”的两类错误价值的系统化讨论。由于现实中的数据集大都存在不同形式的不确定性（如：数据采集的随机波动性、数据的不完备性、属性值的模糊性），且“错找到”和“未找到”的两类错误在数据决策过程中的作用价值不同，因而，构建包容“错找到”和“未找到”两类错误价值的粗糙性度量用以体现或确定变精度意义下的最佳粗糙集具有广泛应用价值。本文以寻求目标集的数据决策问题为应用面向，以目标集无法准确描述的数据集为研究对象，以构建不确定环境下具有结构特征和可解释性的数据处理方法为宗旨，以变精度粗糙集模型中的上（下）近似集作为目标集的描述策略，主要做了以下几个方面的工作：1）以“未找到”和“错找到”两类偏差的效用不同为背景，构建一种包含偏差价值的效用误差度量模式（简记为UE）；2）讨论了UE模式下的上（下）近似集的逼近性能，给出了最佳上（下）近似集和最佳粗糙精度的具体刻划模式；3）结合具体算例进一步分析了最佳上（下）近似集的特征。

1 预备知识

在为了叙述方便，本文约定：1）U={u1，u2，…，un}为有限论域；2）|C|表示有限集合 C 中的元素个数；3）对于U 上的等价关系R（即 R∈U×U且满足：i）(x，x)∈R对任何x∈U恒成立；ii）(x，y)∈ R ⇔(y，x)∈ R；iii）当 (x，y)∈ R，(y，z)∈ R 时，必有 (x，z)∈ R），[x]R={y|(x，y)∈ R}表示 x的R等价类，U/R={[x]R|x∈U}，并称(U，R)为一个近似空间；4）对X，Y⊆U，X≠∅，称

为X包含于Y的程度。

定义1［1］设U为有限论域，(U，R)为一个近似空间，X⊆U，X≠∅，

定义2［4］设U为有限论域，(U，R)为一个近似空间，β ∈(0.5，1]。称

为X关于(U，R)的β下近似集；称

为X关于(U，R)的β上近似集。

在粗糙集理论中，通常称定义2为变精度粗糙集模型（其中的β称之为粗糙精度，X称之为目标集）。不难看出：

2 基于错误效用的近似性度量

在寻找某种特定事物的过程中，经常会面对“未找到”和“错找到”两种不同的困境。比如，在病情诊断过程中，经常会遇到“无法确诊患者病情”和“误诊患者病情”两种困境；在规划模型的求解过程中，经常会遇到“无法设计出适当的求解算法”和“设计了错误的求解算法”两种困境；在数据处理过程中，经常会遇到“数据缺失”和“噪音干扰”两种困境；在命题型专业技能测试过程中，经常会遇到“不会做”和“做错了”两种困境。不难看出，上述问题在现实中广泛存在，其中的一个核心问题是两种不同困境在后续工作中的作用（或影响）是不同的。

若将上述问题中的某种特定事物视为某论域U上的一个集合，Y表示X的近似描述，那么“未找到”即可表示为X−Y（称之为Ⅰ型偏差），“错找到”即可表示为Y−X（称之为II型偏差）。由于Ⅰ型偏差和Ⅱ型偏差在众多诸如数据决策、理疗水平评估问题中的效用不同，因而，若用w和1−w分别表示Ⅰ型偏差和Ⅱ型偏差的效用权重（其中w∈[0， 1]），那么

即为Y关于X的一种体现偏差效用的近似性度量。

不难看出，在考虑多个对象集Y关于一个目标集X的逼近性能时，H(X，Y， w)与具有相同的作用效果，但在考虑不同的对象集Y关于多个目标集X的综合逼近性能时，以H(X，Y， w)和̂(X，Y， w)作为基本度量模式的度量结果却存在本质的不同，而 H(X，Y， w)对应的度量结果更具有统计意义下的合理性。由于在数据决策和数据挖掘过程中经常要同时兼顾多个不同的目标集，因而，本文将以（6）作为度量模式来分析变精度上（下）近似集的逼近性能，为进一步构建兼顾错误价值的数据决策（数据挖掘）方法提供一种理论依据。下面给出UE的一些基本性质。

3 UE模式下的最佳下近似集

本部分和第4部分主要讨论以UE为度量模式的变精度粗糙集的逼近性能。其基本思想是以UE为基础来分析何种粗糙精度的上（下）近似集具有较好的逼近性能。对X⊆U，X≠∅，β ∈(0.5， 1]，若记

定理2 设(U，R)为近似空间，U/R={U1，U2，…，Um}，X ⊆ U，X ≠ ∅，β ∈(0.5， 1]，w∈[0，1]，αi=D(Ui⊆ X)，i∈{1，2，…，m}，(U/R，X，(0.5，1))={Ui|i∈{1，2， …， m} }且 0.5<αi<1。

2.1 ） 当 w<0.5 且存在 s∈{ 1， 2， …， r } 使 得 αs−1<1− w ≤ αs时 ，H(X，(X，β)，w)=H(X，(X，1−w)，w ) 对 任 何 β ∈(αs−1， αs] 恒 成 立 ， 且 H(X，(X，1 − w)，w)=

2.2 ） 当 w<0.5 且不存在 s∈{ 1， 2， …， r }使 得 αs−1<1−w≤αs时 ，H(X，(X，β)，w)=H(X，(X，1−w)， )w 对任何 β∈(αr， 1]恒成立，且

2.2 ） 由 不 存 在 s∈{1，2，…，r} 使 得 αs−1<1−w≤ αs成 立 可 知 αk<1−w 对 任 何k∈{1，2，…，r}，恒 成 立 ，由此及引理 1 可 得(R， X， β)>0 对 任 何 β ∈(0.5， 1]恒 成 立 ，H(X，(X， 1 − w)， w)= min{H(X，(X， β)， w)|0.5< β ≤ 1}。

2.3 ） 由 w≥0.5可 知 αk>1−w 对 任 何 k∈{ 1， 2，…， r }恒 成 立 ，由 此 及 引 理 1可 得 ：①(R， X， β)<0 对 任 何 β ∈(0.5，1]恒 成 立 ；②(R，X，β)关 于 β 在 (0.5，1]上 单 调 不 减 ；③H(X，(X，β)，w)=H(X，(X，α1)，w)对 任 何 β ∈(0.5，α1]恒 成 立 ；④ H(X，(X， α1)， w)=min{H(X，(X， β)， w)|0.5< β ≤ 1}。

定理2给出了各种情形下逼近效果最佳的下近似集以及相对应的粗糙精度范围。若记Best((X， β))≜ min{H(X，(X， β)， w)| 0.5< β ≤ 1}（即 X 关于近似空间(U，R)的逼近效果最佳的下近似集，简称为最佳下近似集），并采用定理2的相关符号约定，则定理2可以系统地表述为：

4 UE模式下的最佳上近似集

2.1 ） 由 αs≤1−w<αs+1可知 αk≤1−w 对任何 k∈{1，2，…，s}恒成立，αk>1−w 对任何k∈{s+1，s+2，…， r}恒成立 ，由 此 及 引 理 2 可得：① 当 1−β∈[0，α1)（即 β∈(1−α1，1]）时，(U/R， X， β)={Ui|i∈{1， 2，…， m} 且 0< αi≤ 1− β }=∅，(R， X， β)=0；② 当 1 − β ∈[αk，αk−1)（即 β ∈(1 − αk+1，1 − αk]），k∈{1，2，…，r}时，

2.2 ） 由不存在 s∈{1，2，…，r}使得 αs≤1− w< αs+1成立可知 αk>1−w（即 αk+w− 1>0）对 任 何 k∈{ 1， 2， …， r } 恒 成 立 ，由此及引理2可得知(R， X， β)=H(X，(X， β)， w)−H(X，(X， 1)， w)>0 对任何 β∈(0.5，1]恒成立，H(X，(X，w)，w)=min{H(X，(X，β)，w)|0.5<β≤1}。

2.3 ） 由w≤0.5可知αk<1−w（即αk+w−1<0）对任何k∈{1，2，…，r}恒成立，由此及引理2 可 得 ：①(R，X，β)=H(X，(X，β)，w)− H(X，(X，1)，w)<0 对 任何 β∈(0.5，1]恒 成 立 ；②(R，X，β)关于 1-β 在[0，0.5]上单调不减（即关于 β 在 ( 0.5， 1 ]上单调不增）；③ H(X，(X， 1−αr)， w)=H(X，(X， β)， w) 对任何 1− β ∈[αr，0.5)（ 即 β ∈(0.5，1− αr]） 恒成立 ； ④H(X，(X， 1 − α1)， w)=min{H(X，(X， β)， w)|0.5< β ≤ 1}。

综合上面的分析可以看出，在UE模式下，目标集X的最佳上（下）近似集与效用权重密切相关、且均具有具体的表示形式。由于效用权重是刻划偏差处理意识的参数，在具体的数据决策（数据处理）问题中可以认为是事先给定的数值，因而，定理2和定理3在本质上解决了最佳上（下）近似集的计算问题。

5 算例分析

本部分将结合一个具体算例来进一步分析不同粗糙精度的上（下）近似集的逼近性能。

其具体取值如表1。

由表1、定理2和定理3可知：

3） X1和X2的几种不同偏差效用下的最佳上（下）近似集如表2和表3；4）X1和X2的几种不同偏差效用和不同粗糙精度下的上（下）近似集效用误差如表4。

自表2―4可以看出：

1） 最佳上（下）近似集随着偏差效用的变化而变化，甚至有较大的差异（比如：w=0.2时，Best((X2， β ))=U7；w=0.8 时，Best((X2， β ))=U3∪ U6∪ U7∪ U8∪ U9）；

2） 不同的偏差效用对应的最佳上（下）近似集可能相同，但对应的效用误差不同（比如，w=0.4 与 w=0.6 时 ， 都有(X1，β∗)=U1∪U4∪U6∪U8∪U9，但 H(X1，(X1，β∗)，0.4)=0.23，H(X1，(X1，β∗)，0.6)=0.22）；

3） 相同偏差效用下，同一集合的最佳上近似集和最佳下近似集的粗糙精度不一定相同（比如，w=0.5 时，

4） 对于给定的偏差效用，最佳上（下）近似集的效用误差一定是最小的（比如：

上述事实进一步反映了效用粗糙集的特征以及最佳上（下）近似集的有效性，与第4-5部分的理论分析完全一致。

6 结论

本文针对变精度粗糙集的逼近性能问题，以“错找到”和“未找到”的作用价值不同为背景，建立了一种集合的效用误差（UE）度量模式，讨论了UE模式下变精度粗糙集的逼近性能，给出了不同情况下的最佳上（下）近似集的具体形式及确定步骤，同时给出了最佳粗糙精度的范围，最后结合具体算例分析了上（下）近似集的变化特征。理论分析和实例计算表明，UE具有良好的结构特征和可解释性，可以简捷地将误差效应融入到度量体系中。由于数据集之间的差异性度量是不确定环境下的数据决策必须面对的问题，因而，本文的讨论不仅在一定程度上丰富了现有的相关理论，而且在数据挖掘、资源管理、模式识别等众多领域具有广泛的应用价值。但值得注意的是本文的讨论仅适用于一个目标集的情形，而对于多个目标集的情况，可以结合各目标集的特征，通过各目标集的综合效用误差度量来考虑最佳逼近问题。该方面的工作将另行文讨论。