波兰数学家Pawlak提出的粗糙集理论能有效处理信息系统中不精确、不确定信息^[1]，其在模式识别、市场决策、医疗诊断等领域广泛应用^[2-3]。经典Pawlak粗糙集理论的研究对象是完备的信息决策表。然而在现实生活中，往往很多决策系统存在多种数据类型，如连续型数据、不完备型数据和集值型数据等^[4-6]。由于经典粗糙集在处理连续型数据时需进行离散化预处理，将不可避免地造成信息的丢失，且对于含有不完备型数据的决策系统，传统的粗糙集模型较难直接处理。近年来，针对混合、模糊、不完备的粗糙集模型扩展及应用成为粒度计算研究的热点问题^[7-13]。

基于粒计算的属性约简研究已取得许多有意义的成果^[14-18]:文献[14]研究了混合数据下的知识发现及邻域粒化问题; 文献[15]提出了悲观多粒度粗糙集的概念，解决了利用“求同消异”的决策策略处理多个不可分辨关系之间存在相互独立的情况; 文献[16]将多粒度粗糙集扩展到邻域多粒度粗糙集; 为提高分类的效果，文献[17]在多粒度粗糙集的基础上引入了错误分类率的概念，即在允许一定程度分类率的前提下，寻找数据之间的相关性，以解决属性间不确定关系的数据分类问题; 对于不完备信息系统，文献[18]提出了一种基于容差关系的不完备可变精度多粒度粗糙集模型。

上述研究分别针对不完备粗糙集、变精度粗糙集进行研究。由于现实生活中同时存在大量的不完备、连续数值型、符号型属性数据的情况，现有的邻域粗糙集计算方法对上述情况和数据集的可控性调节划分的讨论相对较少。为此，本文结合多粒度粗糙集，分析了可变精度模型下不完备邻域决策系统的上、下近似算子及属性约简，并通过邻域粒化方法构建了广义邻域下可变精度的粗糙集模型; 在此基础上，构造了一种衡量属性重要度的方法，并设计了不完备邻域系统的属性约简算法; 最后，通过实例分析验证了算法的有效性。

1 基本知识

给定一个决策系统DS=(U, C, D, V)，其中：U={x₁, x₂, …, x_n}表示非空有限样本集合，称为论域; C是条件属性集合; D是决策属性，C∩D=ϕ, 若D=ϕ，则决策系统转换为信息系统。V为属性值域，对于∀a∈C，V_a为属性a的值域; x_i(a)为样本x_i在属性a上的取值。对于属性子集R⊆C，可得到R在U上的划分U/R={R₁, R₂, …, R_m}。

如果V中包含连续型和符号型等属性类型的对象，则该决策系统称为邻域决策系统。在邻域决策系统中，当部分样本的条件属性值缺失时，则该邻域决策系统称为不完备邻域决策系统，缺失值用“*”表示。

定义1^[14]    设DS=(U, C, D, V)是不完备邻域决策系统，对于∀x∈U，定义x在C∪D上的邻域信息粒子为N_A(x)={y|y∈U, ΔA(x, y)≤δ, δ≥0}，其中δ表示邻域半径，ΔA:U×U→R为U上的一定度量，满足以下性质：

1)∀x, y∈U, ΔA(x, y)≥0, 当ΔA(x, y)=0时, ∀a_i∈A, a_i(x)=a_i(y);

2)∀x, y∈U, ΔA(x, y)=ΔA(y, x);

3)∀x, y, z∈U, ΔA(x, z)≤ΔA(x, y)+ΔA(y, z)。

对于连续型的数据，采用欧式距离度量：

$ \Delta A\left( {x,y} \right) = \sqrt {\sum\limits_{{a_i} \in A} {{{\left| {{a_i}\left( x \right) - {a_i}\left( y \right)} \right|}^2}} } $

对于符号型的数据，可定义：

$ \Delta A\left( {x,y} \right) = \left\{ \begin{array}{l} 0,\;\;\;\;\;{a_i}\left( x \right) = {a_i}\left( y \right)\\ \infty ,\;\;\;\;{a_i}\left( x \right) \ne {a_i}\left( y \right) \end{array} \right. $

当δ=0时，变为经典粗糙集模型。

定义2^[19]    将邻域等价关系扩展到符号型、连续型和缺失型等未知属性共存下的不完备模糊系统，可得到以下广义邻域关系：

$ \begin{array}{l} R\left( x \right) = \left\{ {\left( {x,y} \right) \in {U^2}:\forall a \in x \cap {f_1}\left( x \right) = } \right.\\ \;\;\;\;\;\;\;\;\;\;{f_1}\left( y \right),a\left( x \right) \in \delta \left( {y,a} \right) \cup a\left( y \right) \in \\ \;\;\;\;\;\;\;\;\;\;\left. {\delta \left( {x,a} \right) \cup a\left( x \right) = * \cup a\left( y \right) = * } \right\} \end{array} $

广义邻域关系满足自反性，但不一定满足对称性和传递性，因为任意样本与其自身是不可分辨的，所以任何等价关系均满足自反性。在这里放宽了对称性和传递性的限制，扩展了应用范围。

定义3^[19]    给定DS=(U, C, D, V)是不完备邻域决策系统，B⊆C, N(B)是DS上关于B的邻域关系所构成的邻域粒子族，对于∀x⊆U在B上的邻域，记为N_B(x)，则x在DS上的下近似和上近似分别为${\underline {{P_B}} }$(x)={x∈U|N_B(x)⊆x}, ${\overline {{P_B}} }$(x)={x∈U|N_B(x)∩x≠ϕ}，x的邻域近似边界为bnr_B(x)=${\underline {{P_B}} }$(x)-${\overline {{P_B}} }$(x)。

${\overline {{P_B}} }$(x)是可能包含x的邻域信息粒子组合的集合，${\underline {{P_B}} }$(x)是包含x的邻域信息粒子组合的集合，与x无关的邻域信息粒子集合为U－${\overline {{P_B}} }$(x), 记为~x。

定义4    给定DS=(U, C, D, V)是不完备邻域决策系统，X和Y是U上的两个非空子集，定义集合X关于集合Y的相对错误分类率：

$ e\left( {X,Y} \right) = \left\{ \begin{array}{l} 1 - \frac{{\left| {X \cap Y} \right|}}{{\left| X \right|}},\;\;\;\;\;\left| X \right| > 0\\ 0,\;\;\;\;\left| X \right| = 0 \end{array} \right. $

如果将集合X中的元素分到集合Y中，则出现分类错误的比例为e(X, Y)×100%。

2 不完备可变精度粗糙集模型

定义5    给定DS=(U, C, D, V)是不完备邻域决策系统，B⊆C，决策属性集合D={d₁, d₂, …, d_n}，0≤k < 0.5，在可变精度k下，属性集B相对于决策属性D的上、下近似分别为

$ \begin{array}{*{20}{c}} {\overline {P_B^k} \left( {{d_i}} \right) = \left\{ {x \in U\left| {e\left( {{N_B}\left( x \right),{d_i}} \right) < 1 - k} \right.} \right\}}\\ {\underline {P_B^k} \left( {{d_i}} \right) = \left\{ {x \in U\left| {e\left( {{N_B}\left( x \right),{d_i}} \right) \le k} \right.} \right\}} \end{array} $

在可变精度k下，属性集B相对于决策属性D的边界域为BN_B^k(d_i)=${\overline {{P_B}} }$(d_i)－${\underline {{P_B}} }$ (d_i)，负区域为NEG_B^k(d_i)=U－ ${\underline {{P_B}} }$(d_i)，正区域为POS_B^k=$\bigcup\limits_{i \le n} {\underline {{P_B}} \left({{d_i}} \right)} $。

决策属性值d_i在可变精度k的上近似是U中以不小于k的分类样本划分到d_i上的邻域信息粒子的集合，下近似是U中以不小于1－k的分类样本划分到d_i上的邻域信息粒子的集合。根据多粒度粗糙集的思想，在可变精度不完备邻域决策系统中，通过对邻域粒度δ和可变精度k的控制来区分不同的信息。邻域粒度δ越小，可变精度k取值越优，区分能力越强。

定理1    由定义5可得以下性质：

1) ${\underline {{P_B^k}} }$(d_i)⊆${\underline {{P_B}} }$(d_i)，${\overline {{P_B^k}} }$(d_i)⊆${\overline {{P^B}} }$(d_i);

2) 对于B′⊆B⊆A，则存在${\underline {{P_{B'}^k}} }$ (d_i)⊆${\underline {{P_B^k}} }$(d_i), ${\overline {{P_{B'}^k}} }$(d_i)⊆${\overline {{P_B^k}} }$(d_i)。

证明    1)∀x∈${\underline {{P_B}} }$(d_i)，由定义4可得，至少∃B∈A，使得N_B(x)⊆X成立，再由定义3和定义5可知，e(N_B(x), d_i)≤k，于是x∈${\underline {{P_B}} }$ (d_i)，从而${\underline {{P_B^k}} }$ (d_i)⊆${\underline {{P_B}} }$(d_i)，类似可证${\overline {{P_B^k}} }$(d_i)⊆${\overline {{P_B}} }$(d_i)，证毕。

2) 由定义5可得，对于∀x∈U, 则有e(N_B(x), d_i) < 1-k成立，因为B′⊆B⊆A，则e(N_B′(x), d_i)=$1 -{\rm{ }}\frac{{\left| {{N_{B\prime }}\left(x \right) \cap {d_i}} \right|}}{{\left| {{N_{B\prime }}\left(x \right)} \right|}} < 1 -{\rm{ }}\frac{{\left| {{N_B}\left(x \right) \cap {d_i}} \right|}}{{\left| {{N_B}\left(x \right)} \right|}}$=e(N_B(x), d_i) < 1－k，即x∈${\underline {{P_B}} }$(d_i)，所以${\underline {{P_{B'}^k}} }$(d_i)⊆ ${\underline {{P_B^k}} }$(d_i)。类似可证${\overline {{P_{B'}^k}} }$(d_i)⊆${\overline {{P_B^k}} }$(d_i)，证毕。

从以上性质可知：随着可变精度k的增大，{d_i}的正区域和负区域减小，而边界域则增大; 反之，随着k的减小，{d_i}的正区域和负区域将增大，而边界域在缩小。如上所说，在一个合适的可变精度k范围下，d_i有较大的可分辨性。

性质1    在不完备邻域决策系统中，对缺失的条件属性值的判定：当决策属性值一致时，如果符号型条件属性取值相同，连续型属性取值在相同邻域内的对象归为同一类，否则视为不同类。

在不完备邻域决策系统DS=(U, C, D, V)中，条件属性集合为C={C₁, C₂, C₃, C₄}，决策属性集为D={d₁, d₂}，{C₁, C₂, C₃}为连续型数值属性，{C₄}为符号型属性，下面通过表 1的实例说明。

令δ=0.1，k=0.2，因为样本x₁与x₅的决策属性D取值不同，就算连续型的属性值都在邻域范围内，符号型条件属性取值相同，也不能视为同一类; 因为当k=0.2时，即两个样本在C₁, C₂, C₃, C₄属性中只能有一个属性取值不同或不在同一邻域中，所以x₁, x₂属于同一类，x₁与x₃, x₄不属于同一类。

定义6    给定DS=(U, C, D, V)是不完备邻域决策系统，B⊆C，决策属性集合D={d₁, d₂, …, d_n}，如果∀a∈B，γ_B－a^k(d)=γ_B^k(d)，称属性a对于集合B是冗余的; 如果γ_B－a^k(d) < γ_B^k(d)，则称a是必要的; 如果∀a∈B，属性a对于集合B都是必不可少的，称B是独立的。决策属性d_i对属性集合B的依赖度为

$ \gamma _B^k = \frac{{\left| {{\rm{POS}}_B^k\left( {{d_i}} \right)} \right|}}{{\left| U \right|}} $

定义7    给定DS=(U, C, D, V)是不完备邻域决策系统，决策属性集合D={d₁, d₂, …, d_n}，B⊆C，若属性子集B是不完备邻域决策系统的一个约简集，则B满足：

1) γ_B^k(d)=γ_C^k(d);

2) ∀a∈B, γ_B-a^k(d)≠γ_B^k(d)。

该定义的条件1) 保证了在可变精度k下，约简集与系统中含有全部条件属性时的集合具有相同的分辨能力; 条件2) 保证了属性子集B是独立的，所有的属性都是必不可少的，没有冗余的属性。这一定义与经典粗糙集模型中的定义在形式上是完全一致的。然而，由于该模型定义了数值空间中的粒化和逼近，而经典粗糙集是定义在离散空间的，因此适合于完全不同的应用场合。

定义8    给定DS=(U, C, D, V)是不完备邻域决策系统，B⊆C，对于∀a∈C-B，则属性a相对于B的重要性计算方式为

$ {\rm{SIG}}\left( {a,B,D} \right) = \gamma _{B \cup \left\{ a \right\}}^k\left( D \right) - \gamma _B^k\left( D \right) $

3 变精度下不完备邻域系统的属性约简 3.1 变精度下不完备邻域系统的属性约简算法

当处理高维的大规模数据时，为减少计算时间和保证知识获取的简洁，去除冗余属性尤为必要。为此，本文针对不完备邻域决策系统，在可变精度粗糙集模型下，提出了一种基于属性重要度指标的属性约简算法。首先，根据决策属性对原样本集合做初步划分，再根据可变精度k值和邻域半径δ值，计算邻域关系N_A及对应属性依赖度γ_Ci^k(D)，然后采用贪心式搜索方法，每次计算剩余属性的属性重要度，从中选择属性重要度最大的属性加入约简集合中，直到约简结果中属性集合的重要度等于原始属性集的重要度，即得到不完备邻域决策系统的属性约简结果。由此，变精度下不完备邻域系统的属性约简算法描述如下。

输入    不完备邻域决策系统DS=(U, C, D, V)，邻域半径δ，可变精度k。

输出    属性约简结果RED。

1) 初始化RED=ϕ;

2) 根据决策属性D的值对论域U进行划分U/D={D₁, D₂, …, D_m};

3) 根据可变精度k值和邻域半径δ值，计算邻域关系N_A及对应属性依赖度γ_Ci^k(D);

4) 选取γ_Ci^k(D)中的最大值，令RED=C_i;

5) 对于∀C_i∈C－RED，根据定义6和定义7计算属性的重要度SIG(C_i, RED, D)= γ_RED∪{Ci}^k(D)－γ_RED^k(D)，选取属性重要度最大的条件属性:其满足SIG(C_i, RED, D)= max{SIG(C_i, RED, D)}，并将属性C_i放入RED;

6) 如果γ_RED^k(D)≠γ_C^k(D)，则算法回到5)，否则执行7);

7) 输出约简RED，算法结束。

算法复杂度分析：

算法的第1步的时间复杂度为O(1), 第2步的时间复杂度为O(|U|)，第3步的最坏时间复杂度为O(|C|²|U|log₂|U|)，第4步的时间复杂度为O(1)，第5步的最坏时间复杂度为O(|C-RED|²。|U|log₂|U|), 第6和第7步的时间复杂度为O(1)。由上述分析可知，本算法的时间复杂度主要由步骤3和步骤6的计算耗时所决定，因此该算法的最坏时间复杂度为O(|C|²|U|log₂|U|); 由于算法无需额外的储存空间，可知算法的最坏空间复杂度为O(|U||C|+|U|)。文献[12]在完备决策系统下设计了变精度悲观多粒度粗糙集的下近似分布粒度约简算法，其时间复杂度为O(|U|²|C|²); 文献[13]在信息观下提出了基于不一致邻域矩阵的属性约简算法，其时间复杂度为O(|U|²|C|³)，空间复杂度为O(|U|²|C|)。本文的算法在计算效率和存储空间上具有一定优势，且能处理不完备的邻域数据，算法的扩展性较好。

3.2 与经典粗糙集及邻域模型比较

与经典粗糙集及邻域模型相比较，本文提出的变精度不完备邻域系统的属性约简模型具有以下优点：

1) 经典粗糙集的属性约简适用于离散型属性约简，需先离散化连续型数据，这将不可避免地造成信息的丢失。而变精度不完备邻域系统的属性约简模型既可处理离散型属性约简，也可直接用于连续型属性约简。本文的属性约简模型是对经典粗糙集模型的扩展。

2) 对于含有不完备型数据的决策系统，经典的粗糙集模型较难直接处理，而本文提出的属性约简模型可直接对数据进行分析，并在可变精度的调节下，能得到数据不同层次的信息粒度。

3) 变精度不完备邻域系统的属性约简模型是对邻域模型的进一步扩展，基于邻域的属性约简需计算各样本的邻域，而本文的属性约简模型因为在可变精度的调控下先对样本进行初步筛选，再进行邻域计算，有效减少了计算量。

4 实例分析

为了验证该方法的有效性，我们选择了一个不完备邻域决策系统进行详细分析，表 2中共有10个样本对象，条件属性集为{ C₁, C₂, C₃, C₄}, 决策属性为{D}。设置邻域半径δ=0.1，即两样本之间的邻域半径小于等于0.1;可变精度k=0.2，即两个样本在条件属性集中只能有一个属性取值不同或不在同一邻域中。

首先根据算法第2) 步可计算出不完备邻域决策系统在决策属性D下的划分为{D₁, D₂}，即

$ {D_1}\left( x \right) = \left\{ {{x_3},{x_4},{x_5},{x_8},{x_9}} \right\} $

$ {D_2}\left( x \right) = \left\{ {{x_1},{x_2},{x_6},{x_7},{x_{10}}} \right\} $

根据邻域半径δ=0.1和可变精度k=0.2，通过算法的第3) 步可分别计算每个属性的邻域关系和所对应的依赖度，即

$ \gamma _{{C_1}}^{0.2}\left( D \right) = \frac{1}{2}\;\;\;\;\;\gamma _{{C_2}}^{0.2}\left( D \right) = \frac{4}{5} $

$ \gamma _{{C_3}}^{0.2}\left( D \right) = \frac{7}{{10}}\;\;\;\;\;\gamma _{{C_4}}^{0.2}\left( D \right) = \frac{1}{{10}} $

根据算法第4) 步，因为{γ_Ci^k(D)}中依赖度的最大值所对应的属性为C₂，则令RED={C₂}。继续执行算法第5) 步，在{C－RED}条件属性集中，依次计算剩余属性的重要度，可得

$ {\rm{SIG}}\left( {{C_1},{\rm{RED,}}D} \right) = \gamma _{{C_1} \cup {\rm{RED}}}^{0.2}\left( D \right) - \gamma _{{\rm{RED}}}^{0.2}\left( D \right) = \frac{1}{{10}} $

$ {\rm{SIG}}\left( {{C_3},{\rm{RED,}}D} \right) = \gamma _{{C_3} \cup {\rm{RED}}}^{0.2}\left( D \right) - \gamma _{{\rm{RED}}}^{0.2}\left( D \right) = \frac{1}{5} $

$ {\rm{SIG}}\left( {{C_4},{\rm{RED,}}D} \right) = \gamma _{{C_4} \cup {\rm{RED}}}^{0.2}\left( D \right) - \gamma _{{\rm{RED}}}^{0.2}\left( D \right) = 0 $

则可知C₃为所对应的属性重要度最大的属性，将属性C₃放入RED中，有RED={C₂, C₃}。

再根据算法第6) 步，由于此时γ_RED^k(D)≠γ_C^k(D)，则算法回到5)，同样可计算出C₁为剩余属性中属性重要度最大的属性，将属性C₁放入RED中，有RED={C₂, C₃, C₁}。转至算法的第6) 步，由于此时γ_RED^k(D)=γ_C^k(D)，则算法转至第7)，输出属性约简结果。因此，按照以上算法步骤, 当δ=0.1时，不完备邻域决策系统的属性约简为{C₁, C₂, C₃}。

上述实例是对10组样本对象进行的计算和分析，本文算法中可变精度k值和邻域半径δ值是可变的，在现实应用中可根据具体需求设定可变精度和邻域半径以满足知识的细化程度。

通过上述实例分析，利用本文的算法计算属性约简结果需执行O(|C|²|U|log₂|U|₂)次，文献[12]中的算法需要执行O(|C|²|U|²)次，本文在一定程度降低了算法的计算复杂性。在存储空间上，本文算法需50个储存空间，而文献[13]构建矩阵需400个空间用于存储邻域矩阵元素，本文算法占用的空间相对较少。因此，本文所提出的算法在计算效率上具有优势，并较好地减少算法对存储空间的消耗。

5 结束语

针对不完备邻域决策系统的属性约简问题，本文通过邻域粒化的方法，构建了广义邻域下可变精度的粗糙集模型，同时构造了一种属性重要度的评价方法，并设计了不完备邻域系统的属性约简算法。通过实例分析，该方法能对不完备的数值型和符号型混合数据进行属性约简。在大数据时代，数据的不断产生，需实时更新信息系统，下一步将在此背景下研究，当不完备邻域决策系统中的数据动态变化时如何对属性约简进行增量更新。