混合决策信息系统下基于加权k近邻的属性约简

Attribute Reduction Based on Weighted k-Nearest Neighborhood in Hybrid Decision Information System

摘要: 属性约简是粗糙集理论的一项重要应用，大多数的邻域粗糙集模型只关注邻域粒完全包含在某些决策类中的对象，而忽略邻域粒不包含在任何决策类中的边界对象的可分性。本文采用k近邻来描述混合信息系统对象的粒化，利用边界对象邻域粒中对象的决策信息以及在各自决策类中的分布情况构造对象的评价函数，并基于此定义近似正域。进而在混合型信息系统上提出基于加权k近邻的约简定义，给出属性的重要性度量，以及基于加权k近邻的属性约简方法。最后在3个混合数据集上对约简结果的分类精度进行比较。与传统邻域粗糙集的属性约简算法相比，该算法能保证约简后数据有较高的分类精度。

Abstract: Attribute reduction is an important application of rough set theory. Most neighborhood rough set models only focus on the objects whose neighborhood granules are completely contained in some decision classes, but ignore the divisibility of boundary objects whose neighborhood granules are not contained in any decision classes. In this paper, the k-nearest neighborhood is used to describe the granulation of hybrid information system objects. The evaluation function of objects is constructed by using the decision information of objects in the neighborhood of boundary objects and their distribution in their decision classes. Then, the definition of reduction based on weighted k-nearest neighborhood is proposed in hybrid information system, the importance measure of attribute and the attribute reduction method based on weighted k-nearest neighborhood are given. Finally, the classification accuracy of the reduction results is compared on 3 mixed data sets. Compared with the traditional neighborhood rough set attribute reduction algorithm, the proposed algorithm in this paper can ensure the high classification accuracy of the reduced data.

1. 引言

属性约简是数据预处理的关键步骤[1]，在模式识别和机器学习中有着广泛的应用[2] [3]。属性约简要求在保持原始数据集的决策能力不变的前提下，删除其中不相关的、冗余的属性信息，从而起到提高决策效率的作用。通过属性约简，能有效地简化决策规则和减少储存需求，从而降低计算复杂度[4]。

粗糙集理论[5]是一种处理不确定知识的数据分析方法。经典粗糙集理论是建立在等价关系上的，只适用于离散数据。但是，当面对较复杂的实际问题时，可能呈现连续落在某个区间或者数值型与分类型混合的数据。因此，研究人员陆续提出多种信息系统[6]-[9]用于存放复杂数据。粗糙集理论在处理连续数据时，必须先将原始数据离散化，而数据离散化会导致大量的信息丢失。为了解决这一问题，Hu等[10]在连续型数据集上建立了邻域关系，并提出了邻域粗糙集模型，该模型可以对连续型数据直接进行处理。

目前已经提出了多种邻域粗糙集模型及相应的属性约简算法。文献[11]针对数值型信息系统提出了邻域粗糙集，并利用邻域粗糙集的依赖度构建了数值型信息系统属性约简算法；邻域粗糙集模型只关注邻域完全包含在某些决策类中的对象，因此文献[12]提出了一种最大决策邻域粗糙集模型，增加邻域与某些决策类交集最大的对象来扩展正域，并决策依赖度设计了属性约简算法；文献[13]提出了一种优势邻域粗糙集模型，并构造了一种并行属性约简算法来提高计算速度；文献[14]针对数值型信息系统，利用模糊邻域的概念定义对象的模糊决策，利用模糊邻域与模糊决策之间的关系，构造了一种模糊邻域粗糙集模型；为了处理动态混合信息系统，文献[15]对传统的邻域粗糙集进行了增量式学习的构造，提出了一种基于邻域熵的增量式属性约简算法；文献[16]在计算邻域关系之前充分挖掘属性与决策之间的相关性，对相关性高的属性赋予更高的权重，提出一种加权邻域粗糙集模型，同时设计出相应的属性约简算法；当对象之间存在类内差异时，选择单个属性子集来表示整个数据集可能会降低性能，为此文献[17]对每个类进行再分类，利用邻域粗糙集对每个类进行局部特征选择；文献[18]考虑了边界域的模糊性而导致分类错误的概率和类的不均匀分布，提出了一种基于邻域粗糙集理论的非平衡混合数据特征选择方法；文献[19]基于模糊粗糙集理论，对不同类型的属性定义不同的模糊关系，提出了一种基于模糊粗糙集的信息熵用于混合数据集的特征选择。

邻域粗糙集的目的是利用邻域信息粒来区分属于不同决策的对象。文献[20]结合$\delta$ 单位邻域信息粒和k近邻信息粒，提出了一种在实值信息系统上的新的k近邻信息粒。在属性约简中，如何选择属性是一个至关重要的问题。依赖度通过比较正域和论域的基数比例来衡量邻域决策系统的分类能力。然而，基于正域的依赖度忽略了边界域中对象的可分性，为了提高分类能力，通过对边界域中的对象进行再划分来扩大正域。

针对混合决策信息系统，本文引入k近邻来描述对象的粒化，通过定义边界域中对象的评价函数来判断其可分性，定义近似正域来反映邻域决策系统的分类能力。由于提出的近似正域不是单调的，进而提出一种具有单调性的近似正域，并定义新的属性依赖度，基于此设计出一种启发式属性约简算法。通过实验验证本文提出的属性约简方法的有效性。

2. 预备知识

称$DIS=\left(U,A=C\cup D,V,f\right)$ 为决策信息系统[21]，其中$U$ 表示非空有限对象集，称为论域；$C$ 是条

件属性集，$D$ 是决策属性集，且$C\cap D=\varnothing$ ；信息函数$f:U\times A\to {\displaystyle \underset{a\in A}{\cup }{V}_a}$ ，$V_a$ 是属性$a$ 的值域。

定义1 [20] 给定决策信息系统$DIS=\left(U,A=C\cup D,V,f\right)$ 。对任意$B\subseteq C$ ，$x_i\in U$ ，$x_i$ 关于属性子集$B$ 的$\delta$ 邻域信息粒定义为：

${\delta }_B\left(x_i\right)=\left\{x_j\in U|{\Delta }_B\left(x_i,x_j\right)\le \delta \right\}.$ (1)

其中${\Delta }_B\left(x_i,x_j\right)=\sqrt{{\displaystyle \sum _{a\in B}{\left(\frac{f\left(x_i,a\right)-f\left(x_j,a\right)}{{\sigma }_a}\right)}^2}}$ ，${\sigma }_a$ 表示$V_a$ 的标准差。

由$\delta$ 邻域信息粒可得到$\delta$ 邻域关系$N_B^{\delta }=\left\{\left(x_i,x_j\right)\in U\times U|x_j\in {\delta }_B\left(x_i\right)\right\}$ ，$N_B^{\delta }$ 满足自反性和对称性，但不满足传递性。$\delta$ 邻域信息粒${\delta }_B\left(x_i\right)$ 构成$U$ 的一个覆盖。

定义2 [20] 给定决策信息系统$DIS=\left(U,A=C\cup D,V,f\right)$ 。对任意$B\subseteq C$ ，$x_i\in U$ ，$x_i$ 关于属性子集$B$ 的$k$ 近邻信息粒定义为：

${\kappa }_B\left(x_i\right)=\left\{x_i^1,x_i^2,\cdots ,x_i^k|\forall x_j\in U,x_j\ne x_i^h,{\Delta }_B\left(x_i,x_j\right)>{\Delta }_B\left(x_i,x_i^h\right),h=1,2,\cdots ,k\right\}.$ (2)

${\kappa }_B\left(x_i\right)$ 表示与$x_i$ 距离最近的$k$ 个对象集合。由于$x_i\in {\kappa }_B\left(x_i\right)$ ，因此$k$ 近邻信息粒$\left\{{\kappa }_B\left(x_i\right)|x_i\in U\right\}$ 构成$U$ 的一个覆盖。

文献[20]结合$\delta$ 单位邻域信息粒和$k$ 近邻信息粒，引入了$x_i$ 关于属性子集$B$ 的新的$k$ 近邻信息粒：

${\tau }_B\left(x_i\right)=\left\{x_j\in U|x_j\in B\left(x_i\right)\cap {\kappa }_B\left(x_i\right)\right\}.$ (3)

其中$B\left(x_i\right)=\left\{x_j\in U|{\Delta }_B\left(x_i,x_j\right)\le 1\right\}$ 。

同样，新的$k$ 近邻信息粒$\left\{{\tau }_B\left(x_i\right)|x_i\in U\right\}$ 也构成了$U$ 的一个覆盖。

定义3 [20] 给定决策信息系统$DIS=\left(U,A=C\cup D,V,f\right)$ 。对任意$B\subseteq C$ ，$D_j\in U/D$ ，$D_j$ 关于属性子集$B$ 的下、上近似定义为：

${\underset{\_}{KN}}_B\left(D_j\right)=\left\{x_i|{\tau }_B\left(x_i\right)\subseteq D_j\right\},{\overline{KN}}_B\left(D_j\right)=\left\{x_i|{\tau }_B\left(x_i\right)\cap D_j\ne \varnothing \right\}.$ (4)

决策属性$D$ 关于属性子集$B$ 的下、上近似定义为：

${\underset{\_}{KN}}_B\left(D\right)={\displaystyle \underset{j=1}{\overset{r}{\cup }}{\underset{\_}{KN}}_B}\left(D_j\right),{\overline{KN}}_B\left(D\right)={\displaystyle \underset{j=1}{\overset{r}{\cup }}{\overline{KN}}_B}\left(D_j\right).$ (5)

决策属性$D$ 关于属性子集$B$ 的正域[20]表示为：

$KPO{S}_B\left(D\right)={\underset{\_}{KN}}_B\left(D\right).$ (6)

决策属性$D$ 关于属性子集$B$ 的依赖度为：

${\gamma }_B\left(D\right)=\frac{\left|PO{S}_B\left(D\right)\right|}{\left|U\right|}.$ (7)

其中$\left|\cdot \right|$ 表示集合的基数。${\gamma }_B^{\delta }\left(D\right)$ 反映了$B$ 近似$D$ 的能力，${\gamma }_B^{\delta }\left(D\right)$ 越大表示$B$ 近似$D$ 的能力越强。

3. 基于加权k近邻的属性约简

本节将文献[20]中信息粒的构造方法引入到混合决策信息系统中，提出混合决策信息系统上新的$k$ 近邻信息粒。同时关注边界域中对象邻域的决策信息，定义对象的评价函数来判断边界域对象的可分性，将边界域中能够区分的对象近似地划分到正域中，基于此提出近似正域的概念，进而讨论混合决策信息系统上的属性约简方法。

称$HDIS=\left(U,A=C\cup D,V,f\right)$ 为混合决策信息系统[11]，其中$U$ 表示非空有限对象集，称为论域；$C$ 是条件属性集，$C=C_c\cup C_n$ ，$C_c$ 表示分类型属性集，$C_n$ 表示数值型属性集，$D$ 是决策属性集，且$C\cap D=\varnothing$ ；信息函数$f:U\times A\to {\displaystyle \underset{a\in A}{\cup }{V}_a}$ ，$V_a$ 是属性$a$ 的值域。

定义4 [18] 给定混合决策信息系统$HDIS=\left(U,A=C\cup D,V,f\right)$ 。对任意$B\subseteq C$ 且$B=B_c\cup B_n$ ，$x_i\in U$ ，邻域半径$\delta \in \left[0,1\right]$ ，$x_i$ 关于属性子集$B$ 的$\delta$ 邻域信息粒定义为：

${\delta }_B\left(x_i\right)=\left\{x_j\in U|d_B\left(x_i,x_j\right)\le \delta \right\}.$ (8)

其中

$d_B\left(x_i,x_j\right)=\sqrt{\frac{1}{\left|B\right|}\left({\displaystyle \sum _{a_k\in B_n}{\left|\widehat{f}\left(x_i,a_k\right)-\widehat{f}\left(x_j,a_k\right)\right|}^2}+{\displaystyle \sum _{a_l\in B_c}{\phi }_{a_l}\left(x_i,x_j\right)}\right)},$ (9)

$\widehat{f}\left(x_i,a_k\right)=\frac{f\left(x_i,a_k\right)-\min \left(V_{a_k}\right)}{\max \left(V_{a_k}\right)-\min \left(V_{a_k}\right)},\forall a_k\in B_n$ ，${\phi }_{a_r}\left(x_i,x_j\right)=\{\begin{array}{l}0,f\left(x_i,a_r\right)=f\left(x_j,a_r\right)\\ 1,f\left(x_i,a_r\right)\ne f\left(x_j,a_r\right)\end{array},\forall a_r\in B_c$ 。

定义5 给定混合决策信息系统$HDIS=\left(U,A=C\cup D,V,f\right)$ 。对任意$B\subseteq C$ 且$B=B_c\cup B_n$ ，$x_i\in U$ ，邻域半径$\delta \in \left[0,1\right]$ ，$x_i$ 关于属性子集$B$ 的$k$ 近邻信息粒定义为：

${\kappa }_B\left(x_i\right)=\left\{x_i^1,x_i^2,\cdots ,x_i^k|\forall x_j\in U,x_j\ne x_i^h,d_B\left(x_i,x_j\right)>{\Delta }_B\left(x_i,x_i^h\right),h=1,2,\cdots ,k\right\}.$ (10)

$x_i$ 关于属性子集$B$ 新的$k$ 近邻信息粒定义为：

${\tau }_B\left(x_i\right)=\left\{x_j\in U|x_j\in {\delta }_B\left(x_i\right)\cap {\kappa }_B\left(x_i\right)\right\}.$ (11)

例1 考虑混合决策信息系统$HDIS=\left(U,A=C\cup D,V,f\right)$ ，其中$U=\left\{x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8\right\}$ ， $C=\left\{a_1,a_2,a_3,a_4,a_5,a_6,a_7\right\}$ ，$C_n=\left\{a_1,a_2,a_3,a_4,a_5\right\}$ ，$C_c=\left\{a_6,a_7\right\}$ ，$D=\left\{d\right\}$ (见表1)。

Table 1. Mixed decision information system $HDIS=\left(U,A=C\cup D,V,f\right)$

表1. 混合决策信息系统$HDIS=\left(U,A=C\cup D,V,f\right)$

$U$	$a_1$	$a_2$	$a_3$	$a_4$	$a_5$	$a_6$	$a_7$	$d$
$x_1$	0.22	1.02	0.30	0.81	1.52	1	男	健康
$x_2$	0.24	1.11	0.52	0.39	0.31	1	女	健康
$x_3$	2.10	0.06	0.95	1.01	2.98	2	女	健康
$x_4$	0.63	5.04	1.52	1.12	0.64	2	男	不健康
$x_5$	1.01	1.53	0.71	0.52	1.24	1	男	健康
$x_6$	0.10	2.05	1.13	0.73	0	1	女	健康
$x_7$	1.43	3.98	1.36	1.39	1.22	2	男	不健康
$x_8$	1.21	2.49	0.30	0.88	0.93	1	女	不健康

当$\delta =0.4$ ，$k=3$ 时，${\tau }_C\left(x_1\right)=\left\{x_1,x_2,x_5\right\}$ ，${\tau }_C\left(x_2\right)=\left\{x_2,x_6,x_8\right\}$ ，${\tau }_C\left(x_3\right)=\left\{x_3\right\}$ ，${\tau }_C\left(x_4\right)=\left\{x_4,x_7\right\}$ ，${\tau }_C\left(x_5\right)=\left\{x_1,x_5\right\}$ ，${\tau }_C\left(x_6\right)=\left\{x_2,x_6\right\}$ ，${\tau }_C\left(x_7\right)=\left\{x_4,x_7\right\}$ ，${\tau }_C\left(x_8\right)=\left\{x_2,x_8\right\}$ 。根据下、上近似的定义可得：${\underset{\_}{KN}}_C\left(D\right)=\left\{x_1,x_3,x_4,x_5,x_6,x_7\right\}$ ，即$KPO{S}_C\left(D\right)=\left\{x_1,x_3,x_4,x_5,x_6,x_7\right\}$ 。

根据正域的定义，在例1中，$x_1$ 的$k$ 近邻信息粒中对象决策都相同，我们认为$x_1$ 属于正域，$x_2$ 的$k$ 近邻信息粒中对象决策不完全相同，我们认为$x_2$ 属于边界域。但是，边界域中可能存在一些可分的对象被误分，所以认为需要对边界域进行再划分。

本文通过分析邻域粒中对象的决策信息，寻找一种描述可分性的方式，找出存在于边界域中的可分对象。文献[22]中在数值型信息系统中，将对象的决策信息以及在各自决策类中的分布情况考虑到对象的评价标准中，为k近邻对象加权。本文借鉴文献[22]中对象$x$ 的评价准则，提出评价函数来量化边界域中对象决策的差异程度，从而刻画对象的可分性。

定义6 给定混合决策信息系统$HDIS=\left(U,A=C\cup D,V,f\right)$ 。对任意$B\subseteq C$ 且$B=B_c\cup B_n$ ，$x\in U$ ，$x$ 在$B$ 上的评价函数为：

$E_B\left(x\right)={\displaystyle \sum _{x_i\in {\left[x\right]}_D\cap {\tau }_B\left(x\right)}{\omega }_B\left(x_i\right)}\cdot Si{m}_B\left(x,x_i\right)-{\displaystyle \sum _{x_i\in {\left({\left[x\right]}_D\right)}^C\cap {\tau }_B\left(x\right)}{\omega }_B\left(x_i\right)}\cdot Si{m}_B\left(x,x_i\right)$ (12)

其中${\displaystyle \sum _{x_i\in {\left[x\right]}_D\cap {\tau }_B\left(x\right)}{\omega }_B\left(x_i\right)}\cdot Si{m}_B\left(x,x_i\right)$ 表示$x$ 和它$k$ 近邻对象中与$x$ 决策相同的对象的加权相似度，${\displaystyle \sum _{x_i\in {\left({\left[x\right]}_D\right)}^C\cap {\tau }_B\left(x\right)}{\omega }_B\left(x_i\right)}\cdot Si{m}_B\left(x,x_i\right)$ 表示$x$ 和它$k$ 近邻对象中与$x$ 决策不相同的对象的加权相似度。

$Si{m}_B\left(x,x_i\right)=1-d_B\left(x,x_i\right)$ ，其中$d_B\left(x,x_i\right)$ 表示$x$ 的$k$ 近邻对象$x_i$ 和$x$ 的公式(9)中的距离，${\omega }_B\left(x_i\right)=1-{\upsilon }_B\left(x_i\right)$ ，其中

${\upsilon }_B\left(x_i\right))={\left(\frac{1}{\left|B\right|}{\displaystyle \sum _{a_k\in B}{\left({\upsilon }_{a_k}\left(x_i\right)\right)}^2}\right)}^{\frac{1}{2}}$

${\upsilon }_{a_k}\left(x_i\right)=\{\begin{array}{l}\widehat{f}\left(x_i,a_k\right)-\overline{f}\left(x_i,a_k\right),a_k\in B_n\\ \frac{\left|{\left[x_i\right]}_D\cap {\left({\left[x_i\right]}_{a_k}\right)}^c\right|}{\left|{\left[x_i\right]}_D\right|},a_k\in B_c\end{array}$

$\overline{f}\left(x_i,a_k\right)=\frac{1}{\left|{\left[x_i\right]}_D\right|}{\displaystyle \sum _{x_j\in {\left[x_i\right]}_D}^{\left|{\left[x_i\right]}_D\right|}\widehat{f}\left(x_j,a_k\right)}$

在$x$ 的$k$ 近邻中，与$x$ 决策相同的对象越多，其对应的$E_B\left(x\right)$ 越大，表示对象$x$ 的邻域中与对象$x$ 决策相同的对象和决策不同的对象之间差异程度越大。因此，根据对象$x$ 的质量评价值，把评价函数值大的对象近似看作正域对象，认为和正域对象一样是可分的。

定义7 给定混合决策信息系统$HDIS=\left(U,A=C\cup D,V,f\right)$ 。对任意$B\subseteq C$ ，决策属性$D$ 在$X$ 上关于$B$ 的近似可分集表示为：

$S_B\left(D\right)=\left\{x|E_B\left(x\right)\ge \alpha \right\}$ (13)

则$D$ 关于$B$ 的近似正域表示为：

$APO{S}_B\left(D\right)={\underset{\_}{KN}}_B\left(D\right)={\displaystyle \underset{j=1}{\overset{r}{\cup }}\left({\underset{\_}{KN}}_B\left(D_j\right)\cup S_B\left(D_j\right)\right)}$ (14)

由于近似正域即为决策属性$D_j$ 关于属性集$B$ 的下近似和近似可分集的并集，且$k$ 近邻${\tau }_B\left(x_i\right)$ 的大小相对于$B$ 不是单调的，因此随着属性集$B$ 的增大，上面定义的近似正域不是单调的。但是单调函数更有利于设置属性约简的终止条件[20]为了简化属性约简，我们提出了一种计算近似正域的迭代策略，并将近似可分集考虑到计算中。

定义8 给定混合决策信息系统$HDIS=\left(U,A=C\cup D,V,f\right)$ 。$B_0=\varnothing$ ，$B_i=B_{i-1}\cup \left\{b\right\}$ ，$b\in C-B_{i-1}$ ，$i=1,2,\cdots ,\left|C\right|$ 。子集族$\left\{B_0,B_1,\cdots ,B_{\left|C\right|}\right\}$ 为$C$ 的集合序列，记为$I\left(C\right)$ 。决策类$D_j$ 的近似正域定义为：

$APO{S}_{B_i}\left(D_j\right)={\displaystyle \underset{k=1}{\overset{i}{\cup }}{\underset{\_}{KN}}_{B_i}\left(D_j,X_k\right)}\cup S_{B_i}\left(D_j,{\overline{KN}}_{B_i}\left(D_j,W_i\right)-{\displaystyle \underset{k=1}{\overset{i}{\cup }}{\underset{\_}{KN}}_{B_i}\left(D_j,X_k\right)}\right).$ (15)

其中$X_1=D_j$ ，$X_k=D_j-{\displaystyle \underset{h=1}{\overset{k-1}{\cup }}{\underset{\_}{KN}}_{B_h}\left(D_j,X_h\right)}\cup S_{B_h}\left(D_j,{\overline{KN}}_{B_h}\left(D_j,W_i\right)-{\displaystyle \underset{h=1}{\overset{k}{\cup }}{\underset{\_}{KN}}_{B_h}\left(D_j,X_h\right)}\right)$ ，$W_1=U$ ，

$W_i={\overline{KN}}_{B_{i-1}}\left(D_j\right)$ ，$k=1,2,\cdots ,i$ 且$i=1,2,\cdots ,\left|A\right|$ 。

则对任意$B_i\in I\left(C\right)$ ，$APO{S}_{B_i}\left(D\right)={\displaystyle \underset{j=1}{\overset{r}{\cup }}APO{S}_{B_i}\left(D_j\right)}$ 。

性质1 对任意$B_1,B_2\in I\left(C\right)$ ，$X\subseteq U$ ，若$B_1\subseteq B_2$ ，则有$APO{S}_{B_1}\left(D\right)\subseteq APO{S}_{B_2}\left(D\right)$ 。

证明：令$B_1=\left\{b_{l_1},b_{l_2},\cdots ,b_{l_k}\right\}$ ，$B_2=B_1\cup \left\{b_{m_1},b_{m_2},\cdots ,b_{m_t}\right\}$ ，根据定义8可得：

${\underset{\_}{KN}}_{B_1}\left(D_j\right)={\displaystyle \underset{k=1}{\overset{s}{\cup }}{\underset{\_}{KN}}_{\left\{b_{l_1},b_{l_2},\cdots ,b_{l_k}\right\}}\left(D_j,X_k\right)}$ ，其中$X_1=D_j$ ，$X_k=D_j-{\displaystyle \underset{h=1}{\overset{k-1}{\cup }}{\underset{\_}{R}}_{B_h}\left(D_j,X_h\right)}$ ，$k\ge 2$ ，则有

$\begin{array}{l}{\underset{\_}{KN}}_{B_2}\left(D_j\right)={\displaystyle \underset{k=1}{\overset{s}{\cup }}{\underset{\_}{KN}}_{\left\{b_{l_1},b_{l_2},\cdots ,b_{l_k}\right\}}\left(D_j,X_k\right)}\cup {\displaystyle \underset{k=1}{\overset{t}{\cup }}{\underset{\_}{KN}}_{B_1\cup \left\{b_{m_1},b_{m_2},\cdots ,b_{m_k}\right\}}\left(D_j,X_{s+k}\right)}\\ ={\underset{\_}{KN}}_{B_1}\left(D_j\right)\cup {\displaystyle \underset{k=1}{\overset{t}{\cup }}{\underset{\_}{KN}}_{B_1\cup \left\{b_{m_1},b_{m_2},\cdots ,b_{m_k}\right\}}}\left(D_j,X_{s+k}\right).\end{array}$

其中$X_{s+k}=D_j-X_k-{\displaystyle \underset{h=1}{\overset{k-1}{\cup }}{\underset{\_}{KN}}_{B_1\cup \left\{b_{m_1},b_{m_2},\cdots ,b_{m_k}\right\}}\left(D_j,X_{s+h}\right)}$ ，$X_k=D_j-{\displaystyle \underset{h=1}{\overset{k-1}{\cup }}{\underset{\_}{KN}}_{B_h}\left(D_j,X_h\right)}$ 。

因此${\displaystyle \underset{k=1}{\overset{s}{\cup }}{\underset{\_}{KN}}_{B_1}\left(D_j,X_k\right)}\subseteq {\displaystyle \underset{k=1}{\overset{s+t}{\cup }}{\underset{\_}{KN}}_{B_2}\left(D_j,X_k\right)}$ 。

又有$S_{B_i}\left(D_j,{\overline{KN}}_{B_i}\left(D_j,W_i\right)\right)-{\displaystyle \underset{k=1}{\overset{i}{\cup }}{\underset{\_}{KN}}_{B_i}\left(D_j,X_k\right)}\subseteq {\displaystyle \underset{k=1}{\overset{t}{\cup }}{\underset{\_}{KN}}_{B_1\cup \left\{b_{m_1},b_{m_2},\cdots ,b_{m_k}\right\}}\left(D_j,X_{s+k}\right)}$ ，

所以$APO{S}_{B_1}\left(D_j\right)\subseteq APO{S}_{B_2}\left(D_j\right),\forall D_j\in U/D$ 。即$APO{S}_{B_1}\left(D\right)\subseteq APO{S}_{B_2}\left(D\right)$ 。

定义9 给定混合决策信息系统$HDIS=\left(U,A=C\cup D,V,f\right)$ 。对任意$B\subseteq C$ ，决策属性$D$ 对于属性子集$B$ 的依赖度为：

${\gamma }_B\left(D\right)=\frac{\left|APO{S}_B\left(D\right)\right|}{\left|U\right|}$ (16)

性质2 给定混合决策信息系统$MDIS=\left(U,A=C\cup D,V,f\right)$ 。对任意$B_{i-1},B_i\in I\left(C\right)$ ，且$B_{i-1}\subseteq B_i$ ，${\gamma }_{B_{i-1}}^{\alpha }\left(D\right)$ 和${\gamma }_{B_i}^{\alpha }\left(D\right)$ 分别是$D$ 对于属性子集$B_{i-1}$ 和$B_i$ 的依赖度，则有${\gamma }_{B_{i-1}}^{\alpha }\left(D\right)\le {\gamma }_{B_i}^{\alpha }\left(D\right)$ 。

性质2表明，随着属性子集的增加，决策属性集$D$ 对于属性子集$B$ 的依赖度逐渐增大。这意味着在已有的属性子集中添加一个新属性，决策属性$D$ 对于属性子集$B$ 的依赖度的值不会减小。这为下文构造基于加权$k$ 近邻的属性约简算法提供了理论依据。

定义10 给定混合决策信息系统$HDIS=\left(U,A=C\cup D,V,f\right)$ ，对任意$B\subseteq C$ ，若$B$ 满足 ${\gamma }_B^{\delta }\left(D\right)={\gamma }_C^{\delta }\left(D\right)$ ，且对任意$a\in B$ ，${\gamma }_{B-\left\{a\right\}}^{\delta }\left(D\right)\ne {\gamma }_C^{\delta }\left(D\right)$ ，称$B$ 是混合决策信息系统的一个约简。

定义11 给定混合决策信息系统$HDIS=\left(U,A=C\cup D,V,f\right)$ ，对任意$B\subseteq C$ ，$a\in C-B$ ，则属性$a$ 关于属性子集$B$ 的重要度定义为：

$Sig\left(a,B,D\right)={\gamma }_{B\cup \left\{a\right\}}^{\alpha }\left(D\right)-{\gamma }_B^{\alpha }\left(D\right)$ (17)

我们可以得到$0\le Sig\left(a,B,D\right)\le 1$ 。

根据上述结论，可以构造下述启发式属性约简选择算法。该算法从空集开始，在每个步骤中添加一个重要度最大的属性，直到依赖度不变。具体过程见算法1。

算法1 加权k近邻的属性约简

输入：混合决策信息系统$MDIS=\left(U,C,f,D,g\right)$ ；

输出：约简结果$red$ 。

Step 1 设置初始值$B_k\leftarrow \varnothing$ ；

Step 2 $k=0$ ；

Step 3 计算属性全集的${\gamma }_C^{\alpha }\left(D\right)$ ；

Step 4 从$C-B_k$ 中选择$Sig\left(a,B_k,D\right)$ 最大的属性$a$ ；

Step 5 $k\leftarrow k+1$ ，$B_k\leftarrow B_{k-1}\cup \left\{a\right\}$ ，计算${\gamma }_{B_k}^{\alpha }\left(D\right)$ ；

Step 6 若${\gamma }_{B_k}^{\alpha }\left(D\right)\ge {\gamma }_C^{\alpha }\left(D\right)$ ，则转步骤8；

Step 7 否则转步骤4；

Step 8 $red\leftarrow B_k$

Step 9 输出约简结果$red$ 。

4. 实验

4.1. 实验环境

为验证本文算法的可行性，本文选取UCI上的3个数据集进行实验，3组数据均是含有数值型和分类型属性的混合决策数据集，但是部分存在缺失，在本文实验前已对数据进行预处理，表2所示为数据集的基本信息。

本文借鉴文献[20]，采用KNN (K = 3)和RBF-SVM两个经典分类器对属性约简算法进行了评价。在实验中，SVM的所有参数都被设置为默认值。实验比较采用十倍交叉验证进行。也就是说，一个数据集被随机分成十个部分。对于每个循环，一个部分用于测试，其他部分用于执行属性约简。对简化后的测试数据，计算了3NN和SVM的分类精度。经过10次循环后，计算分类精度的平均值作为最终结果。

Table 2. Experimental data sets

表2. 实验数据集

数据集	对象数	数值型属性数	符号型属性数	决策类数
German	1000	7	13	2
Heart1	270	7	6	2
Heart2	303	6	7	5

4.2. 参数分析

在本文提出的算法中，包含了邻域半径$\delta$ ，$k$ 和阈值$\alpha$ 三个参数。由于不同的参数取值对约简结果有不同的影响，为分析在不同数据集下$\delta$ ，$k$ 和阈值$\alpha$ 对分类准确率的影响，本组实验以0.1为步长在区

间$\left[0.1,0.4\right]$ 内选取邻域半径$\delta$ ，以0.01 N为步长在区间$\left[0.01N,0.1N\right]$ 内选取$k$ ，以1为步长在区间$\left[1,\frac{2k}{3}\right]$

内选取$\alpha$ ，评估$\delta$ ，$k$ 和$\alpha$ 在不同取值下的约简结果在KNN和SVM两个分类器上对数据集分类精度的影响。

图1为数据集在KNN分类器上的分类精度；图2为数据集在SVM分类器上的分类精度。

(a) German

(b) Heart1

(c) Heart2

Figure 1. KNN classification accuracy

图1. KNN分类器分类精度

(a) German

(b) Heart1

(c) Heart2

Figure 2. SVM classification accuracy

图2. SVM分类器分类精度

4.3. 对比分析

本实验将所提出的属性约简算法与文献[11]的NRS属性约简算法和文献[22]的NNRS属性约简算法分别进行实验，通过属性约简的长度和约简结果的分类精度来比较各个算法。

Table 3. Comparison of the length for attribute reductions

表3. 属性约简长度比较

数据集	原始数据	NRS		NNRS		本文算法
		KNN	SVM	KNN	SVM	KNN	SVM
German	20	11	12	12	11	10	10
Heart1	13	12	11	10	12	7	9
Heart2	13	10	10	10	9	9	7

表3给出约简结果属性数量的比较。从表中可以看出，本文算法相对于原始属性集有效地删除了冗余属性。相较于其他算法，本文算法在所选数据集下得到的属性数量更少一些。这是由于本文的算法充分考虑了边界域的有效信息，在属性约简时会提高一些属性的选择能力，所以结果较好一些。

Table 4. KNN classification accuracy of attribute reductions

表4. 属性约简的KNN分类精度

数据集	原始数据	NRS	NNRS	本文算法
German	70.3000	71.3000	71.5000	72.7000
Heart1	78.5185	79.6296	80.3704	81.8519
Heart2	50.6552	55.092	55.8034	56.8276

Table 5. SVM classification accuracy of attribute reductions

表5. 属性约简的SVM分类精度

数据集	原始数据	NRS	NNRS	本文算法
German	73.7000	74.4000	73.9000	74.6000
Heart1	81.4815	83.3333	84.0741	84.8148
Heart2	56.023	57.5287	58.092	58.1954

通过表4和表5观察可得，本文算法不管是在KNN分类器还是SVM分类器上都有较高的分类精度，因为本文的算法考虑了边界域中对象的有效信息，在属性约简时会提高一些属性的选择能力，有效地删除冗余的、无关的属性，并且不会降低邻域决策系统原有的分类性能，效果更好一些。

5. 结束语

本文针对混合决策信息系统，引入k近邻来描述混合决策信息系统中对象的粒化，通过定义边界域中对象的评价函数来判断其可分性，定义具有单调性的近似正域来反映邻域决策系统的分类能力，基于此定义新的属性依赖度，设计出一种启发式属性约简算法。本文主要针对完备的混合决策信息系统，之后将进一步研究不完备混合决策信息系统的属性约简。