0 引言

在许多实际的应用领域中, 求解问题时能够利用的知识往往是带有不确定性的, 20世纪80年代初波兰数学家Pawlak教授提出了粗糙集理论(Rough Set Thoery)^[1], 它能够定量分析处理不精确、不一致、不完整信息与知识, 该理论的提出, 为处理不确定性的问题^[2-3]提供了一种有效的工具。但是经典的粗糙集只适合处理名义型数据, 而在现实中的领域, 如市场分析、故障诊断、天气预测和投资决策等, 存在数值型数据的情况是非常普遍的, 而使用离散化的方法处理数值型数据往往会丢失重要信息。邻域粗糙集(Neighborhood Rough set, NR)^[4-5]以邻域粒化的方式近似逼近论域空间中的任一概念, 直接处理数值型数据, 从而避免了离散化给信息带来的损失。但是邻域粗糙集多用于处理完备的信息系统, 而实际的信息系统大多是不完备的, 因此, 寻求一种能够处理不完备信息系统的方法也是近年来的研究热点^[6-7]。

关于不完备的信息系统, 传统的ROUSTIDA数据补齐算法^[8]对系统进行完备化处理, 使用数据补全来填补信息系统中遗失的数据, 但这种做法会使原信息系统产生变化, 从而不能反映原始信息系统的真实情况。因此, 本文旨在寻求一种在不改变信息系统的前提下直接进行数据处理的方法, Kryszkiewicz^[9]提出了容差关系, Stefabowski等^[10]和盛立等^[11]也提出了用来扩充不完备信息系统的粗糙集模型, 这些关系模型都具有元素相似性的特点, 利用元素相似性进行样本归类, 而粗糙集理论正是利用等价关系对不确定关系进行划分, 因此它们能做到与粗糙集理论有效的结合。很多学者也提出了其他处理不完备信息系统的方法：文献[12]使用确定特征优势关系的概念, 将近似分布约简引入到广义不完备序值信息系统中, 并提出分布约简概念和方法；文献[13]将容差关系与粗糙集相结合, 定义了容差关系下的可辨识矩阵, 并运用该方法得到了不完备信息系统下的一种约简算法；文献[14]以非对称相似关系为基础, 将不同的约简形式引入到不完备信息系统中, 为知识获取提供了新的理论方法和解决手段。但是这些方法只能处理名义型的属性, 却不能处理数值型属性。文献[15]提出了一种新颖的处理不完备信息系统的方法, 它将超图模型应用于邻域粗糙集, 并训练得到一种较好的分类器；文献[16]将邻域粗糙集与容差关系相结合, 用容差邻域条件熵的结果评价系统的约简和分类性能。但这种方法没有考虑信息完备度对不完备信息系统产生的影响, 本文针对不完备信息系统提出一种可以同时处理名义型属性和数值型属性的扩展容差关系, 使用容差完备度弥补了上述方法中的不足, 利用扩展容差关系得到属性的重要性, 并以此重要性为启发因子设计了基于扩展容差关系的混合信息系统的属性约简算法。最后通过实验, 验证了该算法的有效性。

1 预备知识

定义1^[8]  给定信息表S={U, A, V, f}, 其中：U是论域中非空有限样本的集合; A=C∪D是属性集合, C和D分别是条件属性集和决策属性集；V是一个混合属性集合, 它既含有名义型属性, 又含有数值型属性；f:U×R→V是一个信息函数, 它表示U中所有对象的属性值。若存在对象x_i是未知的, x_i∈U, 对于∀a∈A, 记f(x_i, a)=*(*表示遗漏值), 称该系统为不完备的信息系统, INS={U, C∪D, V, f}; 否则为完备的信息系统。

定义2^[5]  设U是实数空间Ω上的非空有限集合, 对于∀x_i∈U, 其邻域定义为:

$\delta \left( {{x}_{i}} \right)=\left\{ x\in U\left| \Delta \left( x, {{x}_{i}} \right) \right.\le \delta, \delta >0 \right\}$

(1)

δ(x_i)表示所有与x_i距离小于δ的样本集合, 对于∀x_i、x_j、x_l∈U, 设距离函数为Δ, 则Δ满足以下条件：

1)Δ(x_i, x_j)≥0, 当且仅当x_i=x_j, Δ(x_i, x_j)=0；

2)Δ(x_i, x_j)=Δ(x_j, x_i)；

3)Δ(x_i, x_l)≤Δ(x_i, x_j)+Δ(x_j, x_l)。

给定一个距离空间(U, Δ), 对于∀x_i∈U, 如果δ₁ < δ₂, 则δ₁(x_i)⊆δ₂(x_i)。

给定样本子集X⊆U, 对于属性子集B, 它的上下近似可以定义为：

$\overline{NX}=\left\{ {{x}_{i}}\in U\left| {{\delta }_{B}}\left( {{x}_{i}} \right)\subseteq X \right. \right\}$

(2)

$\underline{NX}=\left\{ {{x}_{i}}\in U\left| {{\delta }_{B}}\left( {{x}_{i}} \right)\bigcap X\ne \varnothing \right. \right\}$

(3)

对于给定的邻域系统NS={U, C∪D}, x_i是由决策属性D划分的等价类, 因此, 可以将决策属性D关于属性子集B⊆C的下近似定义为：

$\underline{NS}=\underset{i=1}{\overset{k}{\mathop{\bigcup }}}\, \underline{N{{X}_{i}}}$

(4)

定义3^[9]  称INS={U, C∪D, V, f}是一个给定的不完备信息系统, 对于具有遗漏属性值的属性子集B⊆C, 记遗漏值为“*”, ∀a_j∈C, 这里引入容差关系的定义为：

$\begin{align} & T=\left\{ \left( x, y \right)\left| x\in U\wedge y\in U\wedge \right. \right. \\ & \forall {{a}_{j}}\left( {{a}_{j}}\in B\Rightarrow \left( {{a}_{j}}\left( x \right) \right. \right.\text{=}\left. {{a}_{j}}\left( y \right) \right)\wedge \\ & \left. \left. {{a}_{j}}\left( x \right)\ne *\wedge {{a}_{j}}\left( y \right)\ne * \right) \right\} \\ \end{align}$

(5)

显然, T具有自反和对称的性质, 但有可能不是传递的。T(x, y)表示两个对象所满足的容差关系, 将T_B(x)记为对象x的容差类, 则它可以定义为：T_B(x)={y∈U|T(x, y)}, 在该容差关系下, 给定样本子集X关于属性子集B⊆A的上近似(X^B), 下近似(x_B)可以分别定义为：

${{X}_{B}}=\left\{ x\left| x\in U, {{T}_{B}}\left( x \right) \right.\subseteq X \right\}$

(6)

${{X}^{B}}=\left\{ x\left| x\in U, {{T}_{B}}\left( x \right) \right.\bigcap X\ne \varnothing \right\}$

(7)

显然, X^B=∪(x∈X∧T_B(x))。

2 扩展容差关系

式(6)和式(7)是以粗糙集为基础, 将容差关系在不完备信息系统中进行扩充, 它将粗糙集在不完备信息系统上做了有效的推广, 但却都是面向单一的不完备信息系统, 而本文的扩展容差关系是建立在邻域的基础上, 实现了对不完备信息系统中同时含有名义型和数值型属性的混合数据类型的处理。

定义4  给定不完备信息系统的实数空间Ω上的非空有限集合U={x₁, x₂, …, x_m}, 对于∀x_i定义其δ-邻域为：

${{\delta }_{p}}\left( {{x}_{i}} \right)=\left\{ x\in U\left| {{\Delta }_{p}}\left( x, {{x}_{i}} \right) \right.\le \delta, \delta >0 \right\}$

(8)

将δ_p(x_i)称为不完备信息系统的扩展容差邻域, δ_p(x_i)≠∅, 且$\underset{i=1}{\mathop{\overset{N}{\mathop{\bigcup }}\, }}\, {{\delta }_{p}}\left( {{x}_{i}} \right)=U$, f(x, a_k)是样本x在属性a_k下的取值, r_ak是用来表示在属性a_k下关于x与y的一组邻域关系, 结合P范数定义的Δ_p(x₁, x₂), 是具有容差能力的距离函数, 该距离函数可以直接处理名义型属性和数值型属性, 它的定义如式(9)：

${{\Delta }_{p}}(x, y)={{\left( \sum\limits_{{{a}_{k}}=1}^{n}{{{r}_{{{a}_{k}}}}} \right)}^{{\text{1}}/{p}\;}}$

(9)

定义5  给定一个不完备混合信息系统INS={U, C∪D, V, f}, C∪D=A, f=U×C → V, 对于任意∀C∈A, $\underset{k=1}{\mathop{\overset{N}{\mathop{\bigcup }}\, }}\, {{a}_{k}}=C$, x_i、x_j∈U, 这里, 定义如下扩展容差关系, 记为ETR：

1) 当a_k为名义型属性时：

${r_{{a_k}}} = \left\{ \begin{gathered} 0\;\;\;\;\;\;t\left( {x, y} \right) < u \wedge \left( {f\left( x \right) = f\left( y \right) \vee } \right. \hfill \\ \;\;\;\;\;\;\;\;\;\;\;\;f\left( x \right) = * \left. { \vee f\left( y \right) = * } \right) \hfill \\ 1, \;\;\;\;\;\;t\left( {x, y} \right) > u \vee f\left( x \right) \ne f\left( y \right) \hfill \\ \end{gathered} \right.$

(10)

2) 当a_k为连续型属性时：

${r_{{a_k}}}\left\{ {\begin{array}{*{20}{c}} 0 \\ {{{\left| {f({x_{{a_k}}}) - f({y_{{a_k}}})} \right|}^p}} \end{array}} \right.\begin{array}{*{20}{c}} {t\left( {x, y} \right) < u \wedge \left( {f\left( x \right)\left. { = * \vee f\left( y \right) = * } \right)} \right.} \\ {其他} \end{array}$

(11)

在式(10)和式(11)中, 参数u为不完备信息系统INS的容差完备度, 定义为：u=1-|V|/|U|, 令V={v_ij|v_ij∈U, v_ij≠*}, 由u的大小来描述系统容差完备度的高低, 在式(10)和式(11)中, t(x, y)=$\frac{\left| {{P}_{A}}\left( x,y \right) \right|}{{\left( \left| {{P}_{A}}\left( x \right) \right|+\left| {{P}_{A}}\left( y \right) \right| \right)}/{2}\;}$, t(x, y)∈(0, 1), f(x, a)、f(y, a)为样本x、y在该属性上的取值, 令P_A(x)={a∈A|f(x, a)≠*}, P_A(x, y)需要满足条条件P_A(x, y)={x, y∈U|a∈A, (f(x, a)=f(y, a))∧f(x, a)≠*}。

由式(10)和式(11)可知, 对于混合属性的决策系统：当a_k为名义型属性时, 若x_i∈δ_p(x_i), r_ak=0, 否则, r_ak=1, 当a_k为连续型属性时, x_i∈δ_p(x_i)的情况有两种：1)两样本在满足限制条件的情况下, 对应属性值至少有一个为“*”, 即可划分进入扩展容差邻域; 2)经过计算, 两样本在欧氏空间中的距离小于或等于δ, 也可以划分进入ETR邻域。

定义6  扩展容差邻域的上近似和下近似。给定不完备信息决策系统INS={U, C∪D, V, f}, 使得该系统上的TS邻域关系为S, 则对于邻域近似空间NS=(U, C∪D), x₁, x₂, …, x_M是决策D将U划分的M个等价类, ETR_B(x)为样本x在属性子集B⊆C上的扩展容差类, 则对象集合X在近似空间中的上近似和下近似分别为：

$\overline {NS} X = \mathop \cup \limits_{i = 1}^M \overline {NS} {X_i}$

(12)

$\underline {NS} X = \mathop \cup \limits_{i = 1}^M \underline {NS} {X_i}$

(13)

式(12)和式(13)中：

$ \overline {NS} X = \left\{ {{x_j}\left| {{x_j} \in U, ET{S_B}\left( {{x_j}} \right) \cap {X_i} \ne \emptyset } \right.} \right\} $

$ \underline {NS} X = \left\{ {{x_i}\left| {{x_i} \in U, ET{S_B}\left( {{x_j}} \right) \subseteq {X_i}} \right.} \right\} $

则决策属性D在属性子集B下的边界域定义为：

$BNS\left( D \right) = \overline {NS} X - \underline {NS} X$

(14)

3 属性约简算法设计

对不完备信息系统中的样本属性进行约简, 就是在不影响决策系统分类能力的基础上, 将冗余的、不必要的属性删除。本章所介绍的基于扩展容差关系的属性约简算法, 是采用前向贪心搜索的办法, 以属性重要度为启发因子。从空集开始, 每次添加一个属性, 按照定义5所述方法, 在判断属性的类型之后对不完备信息系统的样本进行划分, 经计算得到系统的扩展容差类和扩展容差邻域, 并以此来计算系统的属性重要度, 选择使属性重要度达到最大的属性加入约简集, 直到计算的属性重要度为0时得到约简集。

定义7  给定一个不完备的信息系统INS={U, C∪D, V, f}, 属性子集B⊆C, ∀a_j∈C-B, 则在不完备信息系统中, a_j相对于条件属性B的重要度定义为:

$SI{G_{{a_j}}}\left( D \right) = \frac{{\left| {\underline {NS} {X_{B \cup {a_j}}}\left( D \right)} \right|}}{{\left| U \right|}} - \frac{{\left| {\underline {NS} {X_B}\left( D \right)} \right|}}{{\left| U \right|}}$

(15)

以下为基于扩展容差关系的属性约简的算法描述：

输入  不完备信息系统INS, U是论域, C∪D是条件属性和决策属性的集合；

输出  属性约简集合redc。

步骤1  初始化redc=∅, 为属性a_j∈C添加标签, 0和1分别表示a_j为名义型或者连续型属性。

步骤2  对任意a_j∈C-redc, 判断其标签类型, 由扩展容差关系公式计算得到扩展容差类, 并以此划分上下近似。

步骤3  计算每次添加a_j后的属性重要度SIG=SIG(a_j∪redc, D)。

步骤4  找一个属性a_j, 使得SIG(a_j∪redc, D)达到最大值, a_k=a_i。

步骤5  如果SIG(a_k∪redc, D)>0, 则redc=a_k∪redc转至步骤2；否则, 跳转至步骤6。

步骤6  返回约简集, 算法结束。

4 实验分析

本文从UCI数据集中选取了7组不同类型数据进行实验, 在这些数据集中, 有2个是完备的, 5个是不完备的, 其中有4个完全是连续型属性, 2个是混合型属性, 1个完全是名义型属性。为了得到精确的数据处理结果, 消除数据在数量级上差异, 在数据处理之前需要进行归一化处理, 将数值型属性转化到[0, 1]内。本文将基于扩展容差关系的属性约简算法的实验结果分别与邻域粗糙集(Neighborhood Rough set, NR)^[5]、容差邻域熵(Tolerance Neighborhood Entropy, TRE)^[16]和扩展邻域关系(Extension Neighborhood relation, EN)^[17]三种算法的实验结果进行比较, 其中EN和TRE是具有容差能力的算法, NR是不具有容差能力的算法, 使用这4种算法分别对不完备信息系统进行属性约简。实验结果如表 1所示(表中13/0表示属性类型比例, 13表示连续属性个数, 0表示离散属性个数)。

从表 1中可以得到, 本文所使用的ETR算法对数据集进行属性约简, 平均能够得到6.143个属性, 而NR算法平均得到7.286个属性, TRE算法平均得到8.000个属性, EN算法平均得到9.125个属性。由上述结果可得, 使用扩展容差关系进行属性约简能够得到比其他三种算法更少的属性。在比较各种算法选择属性的能力的基础上, 本文使用K最近邻(K-Nearest Neighbor, KNN)、分类回归树(Classification And Regression Tree, CART)和径向基函数-支持向量机(Radial Basis Function-Support Vector Machine, RBF-SVM)分类器来计算分类精度, 使用十折交叉验证方法测试4种算法的分类准确性, 得到的实验数据如表 2~4所示。

通过表 2~4实验数据可以发现, 虽然删除了某些属性, 使用新的属性子集对系统进行分类, 但是实验结果的分类精度并没有降低, 这是因为在原始数据集中不可避免地会掺杂一些噪声, 当属性约简删除了一些冗余的属性后, 会减少这些噪声数据对分类所造成的影响。观察表 2的数据可得, 使用KNN算法对样本进行分类, 经检验, 本文方法得到的分类精度平均为0.911 6, 比不具有容差能力的NR方法高出0.011 3、比TRE和EN算法得到的结果高出0.009 0和0.017 6, 这说明本文算法在KNN分类器下进行计算, 在不降低分类精度的前提下能够得到更好的分类结果。由表 3可得, 在CART分类器下, ETR方法得到分类精度比NR方法少0.009 2, 这个结果是合理, 说明ETR方法对不完备信息系统属性约简后, 能够得到比对比算法更少的属性, 也能使分类精度保持在较好的水平。观察表 4的实验结果, 经RBF-SVM分类计算后, EN、NR和TRE方法得到的分类精度均值分别是0.919 5、0.894 5和0.910 7, 而本文算法得到的分类精度平均为0.931 4, 比算法EN高出0.011 9, 说明本文算法不仅可以选择得到更少的属性, 而且可以保持甚至提高约简后系统的分类精度。因此可以得出, 具有一定容差能力的ETR方法不仅能够处理样本数据的冗余信息, 而且能够更好地解决实际应用中信息系统中的不完备问题。

然后, 使用数据集Wine和ionosphere分别测试了在不同的邻域阈值下, 单个样本集在使用不同的分类算法时, 分类精度变化的趋势, 邻域阈值δ以0.01为步长, 在0~0.8之间取值, 实验结果如图 1和图 2所示。

图 1显示, 当δ < 0.08时, 分类精度稍低, 这是因为系统只选择了少量的属性；当0.35 < δ < 0.5时, 分类精度略微下降, 这是由于系统选择了过多的属性, 因而出现冗余, 降低了分类精度；当δ≥0.5时, 因为系统没有选择得到任何属性, 所以得到的分类精度为0。从图 2中可以发现, 当0.05 < δ < 0.3时, 分类精度取值较为平稳；当0.3 < δ < 0.5是选择得到的属性出现冗余, 分类精度略为下降；当δ≥0.5时, 由于系统只选择得到1个属性, 所以分类精度呈现平稳且保持较低水平的现象。综上所述：邻域阈值δ在[0.08, 0.3]内取值是较为合理的。

5 结语

本文通过引入邻域的概念对经典粗糙集理论在不完备信息系统上进行了扩充, 并结合了容差关系中元素之间具有相似性的性质对经典不完备信息系统决策表补齐的方法进行了改进, 提出了一种扩展容差关系, 该方法可以直接处理混合数据类型的不完备决策系统, 从而避免了通过数据补齐或删除以及数值型属性离散化等预处理方法对系统数据造成的损失。最后, 提出了一种基于扩展容差关系的混合决策系统的属性约简算法, 使用7组UCI数据进行了实验, 并与另外两种具有容差能力和不具有容差能力的算法结果进行了比较, 讨论了在不同的邻域取值对分类结果产生的影响, 实验结果证明了算法的有效性。本文提出的扩展容差关系是将改进的容差关系与邻域系统相结合, 也可以将它与可辨识矩阵的知识相结合, 这将会是下一步的研究方向。