粗糙集理论^[1-2](rough set theory)是分析、处理不精确和不确定数据的有效工具。由于粗糙集理论中的等价关系在实际应用中局限性较大，各种基于二元关系的扩展粗糙集模型^[3-8]得以发展。目前，粗糙集理论已经广泛应用于数据挖掘、机器学习与模式识别等研究领域。

集值信息系统是重要的单值系统的扩展模型，其中集值是用来描述不精确和缺失的信息，集值信息系统在现实生活中的应用广泛。近年来，许多学者对集值系统做了深入、大量的研究工作。Guan等^[9]提出最大相容类的定义解决了同一相容类中对象不一定两两相似的问题，并且提出A-相对约简和E-相对约简。Qian等^[10]提出基于优势关系的合取型集值序信息系统和吸取型集值序信息系统并构建了两种粗糙集模型。杨习贝等^[11]在集值系统中提出模糊优势关系，考虑到了对象之间的优势程度。Huang等^[12]提出概率集值信息系统和基于巴氏距离的 $\lambda $ -相容关系，更合理地描述了在概率集值信息系统对象间的关系。Wei等^[13]基于模糊相似类和模糊相似度提出两种不同的模糊粗糙集模型。Zhang等^[14]将量化粗糙集和优势粗糙集结合，提出了一种基于大规模集值信息系统的特征选择和近似推理的通用框架。

Skowron等^[15]认为差别矩阵方法虽然可以求得数据集的所有约简，但是其效率相对于启发式算法较低，故应用性较差。由于现实生活中数据信息量的不断增大，集值系统中属性约简算法的效率需要做进一步研究。罗川等^[16]在集值序决策系统中通过计算粗糙近似提出了基于增加和删除策略的增量式算法；Zhang等^[17]在集值系统中提出了构造关系矩阵的基本方法并且通过研究属性集变化时关系矩阵变化的性质，得到了关系矩阵更新的增量式方法；刘莹莹等^[18]在集值信息系统中通过定义一种新的相似度，提出基于相似度的启发式算法；马建敏等^[19]在集值信息系统中引入信息量等概念，提出一种新的启发式约简算法。

1 基础知识 1.1 集值信息系统相关基础知识

定义1　集值信息系统是一个四元组SIS = $ (U, {\rm{AT}}, V, f)$ ，其中： $U$ 是非空有限对象的集合，称为论域；AT是非空有限属性的集合； ${V_a}$ 是条件属性值集合，有 $V = { \cup _{a \in {\rm{AT}}}}{V_a}$ ；对于 $\forall a \in {\rm{AT}}$ 满足 $f(x, a) \in {V_a}$ 的集值映射为 $f:U \times {\rm{AT}} \to {2^V}$ 。

若属性集合由条件属性集合 $C$ 和决策属性集合D组成， $D \cap C = \text{Ø} $ ， $f:U \times C \to {2^{{V_C}}}$ 为集值映射， $f:U \times D \to {V_D}$ 为单值映射，则该信息系统称为集值决策系统 ${\rm{SDS}} = (U, C \cup D, V, f)$ 。

为方便起见 ${V_D} = \{ 1,2, \cdots \! , r\} $ ， $U/{\rm{IND}}(D)=\{ {D_1}, $ $ {D_2}, \cdots \! ,{D_r}\} $ ，其中 ${\rm{IND}}(D) = \{ ({x_i}, {x_j})|({x_i}, {x_j}) \in {U^2}, f({x_i}, D) = $ $ f({x_j}, D)\} $ 。 $U/{\rm{IND}}(D)$ 表示D在U上的划分。

例1　 表1为集值决策系统 ${\rm{SDS}} = (U, C \cup D,V, f)$ ，其中： $U \!=\! \{ {x_1}, {x_2}, {x_3}, {x_4}, {x_5}, {x_6}, {x_7}, {x_8}\} $ 为论域，C = $\{ {a_1}, {a_2}, {a_3}, {a_4}, {a_5}\} $ 为条件属性集合， $D = \{ d\} $ 为决策属性集合。

定义2　集值信息系统 ${\rm{SIS}} = (U, {\rm{AT}}, V, f)$ ， $\forall A\subseteq $ AT，则 A 在U上的相容关系定义为

${{{T}}_A} = \{ (x, y) \in U \times U|\forall a \in A, a(x) \cap a(y) \ne \varnothing \}\text{。}$

等价关系在集值信息系统不再成立， ${{{T}}_A}$ 满足自反性和对称性，不一定满足传递性。设 ${T_A}(x)$ 为相容类，定义 ${T_A}(x) = \{ y \in U|(x, y) \in {{{T}}_A}\} $ ，表示与对象 $x$ 关于相容关系 ${{{T}}_A}$ 的最大不可分辨对象集合。 $U/{{{T}}_A} = \{ {T_A}(x)|x \in U\} $ 形成对论域的一个覆盖，其中任意两个集合都可能相交。

定义3　集值信息系统 ${\rm{SIS}} = (U, {\rm{AT}}, V, f)$ ， $X \subseteq U$ ， $A \subseteq {\rm{AT}}$ ，则在相容关系A 下集合 X 的下、上近似分别为 $\underline A (X) = \{ x \in U|{T_A}(x) \subseteq X\} $ 和 $\overline A (X) = \{ x \in U|{T_A}(x)\cap $ $X\ne \varnothing \}$ 。

X 的下近似是在相容关系 A 下确定属于 X 的全体对象集合，而 X 的上近似是在相容关系 A 下可能属于 X 的全体对象集合。

根据定义3可得： ${\rm{POS}}_A(X) = \underline{A} (X),$ ${\rm{BN}}_A(X) = \overline A(X) -$ $ \underline{A} (X)。$ 。 ${\rm{POS}}_A(X)$ 称为在相容关系 A 下集合 X 的正域，它表示在相容关系 A 下可以确定划分到集合 X 里的对象集合； ${\rm{BN}}_A(X)$ 为在相容关系 A 下集合 X 的边界域，它表示在相容关系 A 下不能完全确定划分是否属于集合 X 的对象集合。

定义4　集值决策系统 ${\rm{SIS}} = (U, {\rm{AT}}, V, f)$ ， $A \subseteq {\rm{AT}}$ ， $U/{\rm{IND}}(D)=\{ {D_1}, {D_2}, \cdots , {D_r}\} $ ，则决策属性 D 在相容关系 A 的下、上近似分别为 $\underline{A} (D) = \{ x \in U|{D_j} \in U/{\rm{IND}}(D),$ ${T_A}(x) \subseteq {D_j}\} $ 和 $\overline A(D) = \{ x \in U|{D_j} \in U/{\rm{IND}}(D), {T_A}(x) \cap $ ${D_j}\ne \varnothing \} $ 。其中 $j \in \{ 1, 2, \cdots , |U/{\rm{IND}}(D)|\} $ 。 $\underline{A} (D)$ 也称为决策属性集合 D 在相容关系 A 下的正域， $\underline{A} (D) = {\rm{POS}}_A(D)$ 。

1.2 集值信息系统的正域约简算法

定义5　集值决策系统 ${\rm{SDS}} = (U, C \cup D, V, f)$ ， $A \subseteq C$ ，则决策属性集合D在相容关系A下的近似分类质量定义为

${\gamma _A}(D) = \frac{{|{\rm{POS}}_A(D)|}}{{|U|}}$

近似分类质量刻画了在相容关系A下可以正确划分到决策属性集合 $D$ 的对象集合数与论域个数的比重。

定义6　集值决策系统 ${\rm{SDS}} = (U, C \cup D, V, f)$ ， $A \subseteq C$ ，则集合 A 是集值决策系统的一个正区域保持属性约简当且仅当以下两个条件成立：

1) ${\gamma _A}(D) = {\gamma _C}(D)$ ；

2) $\forall B \subset A$ ， ${\gamma _B}(D) < {\gamma _A}(D)$ 。

定义7　集值决策系统 ${\rm{SDS}} = (U, C \cup D, V, f)$ ， $A \subseteq C$ ， $\forall a \in A$ 。条件属性 $a$ 的内部属性重要度定义为

${\rm{Sig}}^{{\rm{inner}}}(a, A, C, D, U) = {\gamma _A}(D) - {\gamma _{A - \{ a\} }}(D)$

内部属性重要度刻画了属性集合中的每个属性的初始重要度，用于选择不可缺少的属性子集，在算法中用于计算属性约简的核属性集合。

定义8　集值决策系统 ${\rm{SDS}} = (U, C \cup D, V, f)$ ， $A \subseteq C$ ， $\forall a \in C - A$ ，条件属性 $a$ 的外部属性重要度定义为

${\rm{Sig}}^{{\rm{outer}}}(a, A, C{\rm{, }}D, U) = {\gamma _{A \cup \{ a\} }}(D) - {\gamma _A}(D)$

外部属性重要度刻画了属性在信息系统的重要程度，用于在搜索过程中选择属性，在迭代过程中，每轮选择外部属性重要度最大的属性加入到候选属性集合中，直到候选属性子集满足终止条件，从而获得属性约简。

对于给定集值决策系统 ${\rm{SDS}} = (U, C \cup D, V, f)$ ， $a \in C$ ，若 ${\rm{Sig}}^{{\rm{inner}}}(a, C, C, D, U) > 0$ ，则 $a$ 属于集值决策系统 ${\rm{SDS}}$ 的核属性。

根据文献[20]给出集值信息系统下经典正域属性约简算法(positive region reduction algorithm，PRRA)，见算法1。

算法 1　PRRA

输入　集值决策系统 ${\rm{SDS}} = (U, C \cup D, V, f)$ ；

输出　集值决策系统SDS的一个属性约简 R。

1) $R = \varnothing $ 。

2)计算 ${\rm{Sig}}^{{\rm{inner}}}({a_i}, C, C, D, U)$ ， $i \in {\rm{\{ 1, 2, }} \cdots , |C|{\rm{\} }}$ ，如果 ${\rm{Sig}}^{{\rm{inner}}}({a_i}, C, C, D, U) > 0$ ，则将 ${a_i}$ 存入 R 中。

3)若 ${\gamma _R}(D) = {\gamma _C}(D)$ ，则终止；否则对条件属性 $C - R$ 进行如下操作：

计算 ${\rm{Sig}}^{{\rm{outer}}}({a_0}, R, C, D, U) = \max\{ {\rm{Sig}}^{{\rm{outer}}}({a_k},C, D, R,$ U)}， $R \leftarrow R \cup \{ {a_0}\} $ ，其中 ${a_k} \in C - R$ 。若有多个最大值，则选择与 R 组合数最少的属性。

4)对 R 中的每个条件属性 ${a_i}$ 进行如下操作：

①计算 ${\gamma _{R - \{ {a_i}\} }}(D)$ ；

②若 ${\gamma _{R - \{ {a_i}\} }}(D) \!=\! {\gamma _C}(D)$ ，则 ${a_i}$ 为冗余属性， $R \!=\! R \!-\! \{ {a_i}\} $ ，否则 ${a_i}$ 为非冗余属性，R 保持不变。

5)返回 R。

由算法1可得，在3)迭代的过程中，每次选取一个属性重要度最大的属性加入到 R 中，在这个过程中需要不断地计算整个论域上的正域，从而使得算法计算量非常大，效率不够理想，很难应用在大规模数据集下。

例2　 表1为集值决策系统 ${\rm{SDS}} \!=\! (U, C \cup D,V, f)$ ，其中， $U = \{ {x_1}, {x_2}, {x_3}, {x_4}, {x_5}, {x_6}, {x_7}, {x_8}\} $ 为论域， $C = \{ {a_1},{a_2}, $ $ {a_3}, {a_4}, {a_5}\} $ 为条件属性集合， $D = \{ d\} $ 为决策属性集合。

采用PRRA算法对表1约简过程如下。

1)表1中经求其核属性集为 $R = \{ {a_3}, {a_4}\} $ ，决策属性D相对于条件属性C的近似分类质量为 ${\gamma _C}(D) = 0.625$ ；

2)对 $C - R$ 中每个条件属性重复进行如下操作：

根据定义8计算 $C - R$ 中属性的重要度，其中， ${\rm{Sig}}^{{\rm{outer}}}({a_1}, R, C, D, U) = 0.125$ ， ${\rm{Sig}}^{{\rm{outer}}}({a_2}, R, C, D, U) = $ 0， ${\rm{Sig}}^{{\rm{outer}}}({a_3}, R, C, D, U) = 0.125$ 。

由于属性 ${a_1}$ 和属性 ${a_3}$ 的外部属性重要度Sig^outer $({a_1}, R, C, D, U) = $ ${\rm{Sig}}^{{\rm{outer}}}({a_3}, R, C, D, U) = $ 0.125，故选择与 R 组合数最少的属性 ${a_1}$ 。根据算法1中步骤3)将 ${a_1}$ 加入 R 中，得 $R = R \cup \{ {a_1}\} = $ $ \{ {a_1}, {a_3}, {a_4}\} $ ，且 ${\gamma _R}(D) = $ ${\gamma _C}(D) = 0.625$ ，终止步骤3)。

3)去除集合 R 中的冗余属性，由于 ${\gamma _{R - \{ {a_1}\} }}(D) \ne $ $ {\gamma _C}(D)$ ，故集合 R 中无冗余属性，算法终止。

故算法PRRA得到约简， $R = \{ {a_1}, {a_3}, {a_4}\} $ 。

2 集值系统的快速正域约简

Qian等^[21-22]提出了正向近似的加速原理。本节在文献[21-22]算法的基础上介绍集值信息系统下的正域属性约简算法的加速原理以及相关性质，给出了算法的伪代码描述和两个算法的时间复杂度对比与分析。

定理 1　集值决策系统 ${\rm{SDS}} = (U, C \cup D, V, f)$ ，设属性子集 $P$ 、 $Q$ 满足 $P \subset Q \subseteq C$ ，则 ${\rm{POS}}_P(D) \subseteq {\rm{POS}}_Q(D)\text{。}$

该定理表明，如果两个属性集合存在包含关系，则这两个属性集合相对于决策属性D的正域也存在包含关系。证略。

定理 2　集值决策系统 ${\rm{SDS}} = (U, C \cup D, V, f)$ ，条件属性集合 $C = \{ {a_1}, {a_2}, \cdots , {a_{|C|}}\} $ ，属性集合 ${P_i} = $ $ \{ {a_1}, {a_2}, \cdots , {a_i}{\rm{\} }}$ ， $i = 1, 2, \cdots , |C|$ ，则定义：

${\rm{POS}}_{{P_{i + 1}}}(U, D) = {\rm{PO}}{{\rm{S}}_{{P_i}}}(U, D) \cup {\rm{PO}}{{\rm{S}}_{{P_{i + 1}}}}({U_{i + 1}}, D)\text{。}$

式中： ${U_1} = U$ ， ${U_{i + 1}} = U - {\rm{PO}}{{\rm{S}}_{{P_i}}}(U, D)$ 。

定理3　集值决策系统 ${\rm{SDS}} = (U, C \cup D, V, f)$ ， $A, B \subseteq C$ ，若 $U/{{{T}}_A} = U/{{{T}}_B}$ ，则 ${\rm{PO}}{{\rm{S}}_A}(U, D)={\rm{PO}}{{\rm{S}}_B}(U, D)$ 。

证明　设 $U/{{{T}}_A} \!=\! \{ {X_1}, {X_2}, \cdots \! , {X_{|U|}}\} $ ， $U/{{{T}}_B} \!=\! \{ {Y_1}, {Y_2}, \cdots \! , $ $ {Y_{|U|}}\} $ ，如果 $U/{{{T}}_A} = U/{{{T}}_B}$ ，则 ${X_i} = {Y_i}$ ， $i = 1, 2, \cdots , |U|$ ，那么 ${\rm{PO}}{{\rm{S}}_A}(U, D) = {\rm{PO}}{{\rm{S}}_B}(U, D)$ ，证毕。

定理4　集值决策系统 ${\rm{SDS}} = (U, C \cup D, V, f)$ ， $A\!\! \subseteq \!\!C$ ， $\forall a \!\!\in\!\! C \!\!-\!\! A$ ，如果 $U/{{{T}}_A} \!\!=\!\! U/{{{T}}_{A \cup \{ a\} }}$ ，那么 ${\rm{PO}}{{\rm{S}}_A}(U, D) \!=\! $ ${\rm{PO}} {\rm{PO}}{{\rm{S}}_{A \cup \{ a\} }}(U, D)\,$ ，则属性 a 为冗余属性。

证明　设 $U/{{{T}}_A} = \{ {X_1}, {X_2}, \cdots \! , {X_{|U|}}\} $ ， $U/{{{T}}_{A \cup \{ a\} }} = \{ {Y_1}, $ ${Y_2}, \cdots \! ,{Y_{|U|}}\} $ ，因为 $U/{{{T}}_A} = U/{{{T}}_{A \cup \{ a\} }}$ ，即 ${\rm{PO}}{{\rm{S}}_A}(U, D) = $ $ {\rm{PO}}{{\rm{S}}_{A \cup \{ a\} }}(U, D)$ ，因此对于任意 $b \in $ $C - A - \{ a\} $ ，有 ${\rm{PO}}{{\rm{S}}_{A \cup \{ b\} }}$ $(U, D) = {\rm{PO}}{{\rm{S}}_{A \cup \{ b\} \cup \{ a\} }}(U, D)$ 。所以 $a$ 是约简过程中的冗余属性，可以被删除。证毕。

定理5　集值决策系统 ${\rm{SDS}} = (U, C \cup D, V, f)$ ， $A \subseteq C$ ，如果 $\forall a, b \in C - A - A'$ ，并且 ${\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}(a, A, C, D, U) - $ $ {\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}(b, A, C, D, U) \geqslant 0$ ，那么 ${\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}(a, A, C', D, {U^ * }) - $ $ {\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}(b, A, C', D, {U^ * }) \geqslant 0$ 。其中，属性集合 $C' = C - A'$ ， $A' = \{ c|{\rm{POS}}_A^C(U, D) = {\rm{POS}}_{A \cup \{ c\} }^C(U, D), c \in C - A\} $ ， ${U^ * } = U - $ $ {\rm{POS}}_A^C(U, D)$ 。

证明　根据定义 ${\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}(a, A, C, D, U) = {\gamma _{A \cup \{ a\} }}(D) - $ ${\gamma _A}(D)$ ，要度仅取决于 ${\gamma _A}(D) = |{\rm{PO}}{{\rm{S}}_A}(D)|/|U|$ 。由于U^* = $ U - {\rm{POS}}_A^C(U, D)$ ，所以 ${\rm{POS}}_A^C({U^ * }, D)=\varnothing $ ， ${\rm{POS}}_{A \cup \{ a\} }^C({U^ * }, $ $D)= {\rm{POS}}_{A \cup \{ a\} }^C(U, D) \!-\! {\rm{POS}}_A^C(U, D)$ 。又因为 $C' \!\cap\! A' \!=\! \varnothing $ ， $A \subset C'$ ，故 ${\rm{POS}}_A^{C'}({U^ * }, D) = {\rm{POS}}_A^C({U^ * }, D)$ 。因此

$\begin{array}{c}\displaystyle\frac{{{\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}(a, A, C, D, U)}}{{{\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}(a, A, C', D, {U^ * })}}= \displaystyle\frac{{\gamma _{A \cup \{ a\} }^{(C, U)}(D) - \gamma _A^{(C, U)}(D)}}{{\gamma _{A \cup \{ a\} }^{(C', {U^ * })}(D) - \gamma _A^{(C', {U^ * })}(D)}} = \\ \displaystyle\frac{{{\rm{|}}{U^ * }{\rm{|}}}}{{{\rm{|}}U{\rm{|}}}}\frac{{{\rm{|POS}}_{A \cup \{ a\} }^C(U, D){\rm{|}} - {\rm{|POS}}_A^C(U, D){\rm{|}}}}{{{\rm{|POS}}_{A \cup \{ a\} }^{C'}({U^ * }, D){\rm{|}} - {\rm{|POS}}_A^{C'}({U^ * }, D){\rm{|}}}} = \\ \displaystyle\frac{{{\rm{|}}{U^ * }{\rm{|}}}}{{{\rm{|}}U{\rm{|}}}}\frac{{{\rm{|POS}}_{A \cup \{ a\} }^C(U, D){\rm{|}} - {\rm{|POS}}_A^C(U, D){\rm{|}}}}{{{\rm{|POS}}_{A \cup \{ a\} }^C({U^ * }, D){\rm{|}} - {\rm{|POS}}_A^C({U^ * }, D){\rm{|}}}} = \\ \displaystyle\frac{{{\rm{|}}{U^ * }{\rm{|}}}}{{{\rm{|}}U{\rm{|}}}}\frac{{{\rm{|POS}}_{A \cup \{ a\} }^C(U, D){\rm{|}} - {\rm{|POS}}_A^C(U, D){\rm{|}}}}{{{\rm{|POS}}_{A \cup \{ a\} }^C(U, D){\rm{|}} - {\rm{|POS}}_A^C(U, D){\rm{|}}}} = \displaystyle\frac{{{\rm{|}}{U^ * }{\rm{|}}}}{{{\rm{|}}U{\rm{|}}}}\end{array}$

因为 $|{U^ * }|/|U| \! \geqslant \! 0$ ，若 ${\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}(a, A, C, D, U) \! \geqslant \! {\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}(b,$ $ A, C, D, U)$ ，则 ${\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}(a, A, C', D, {U^ * }) \geqslant {\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}(b, A,C', D,$ $ {U^ * })$ 。证毕。

定理2表明，计算属性重要度时由于删除正域和冗余属性集合后属性重要度保持不变，这样在计算属性约简时，每次迭代过程中可以删除候选集合产生的正域和冗余属性集合，使得算法效率提升。

算法 2　QPRRA

输入　集值决策系统 ${\rm{SDS}} = (U, C \cup D, V, f)$ ；

输出　集值决策系统 SDS 的一个属性约简 R。

1)令 $i = 1$ ， ${R_1} = R$ ， ${U_1} = U$ ， ${C_1} = C$ ， ${C_d} = \varnothing$ ， $R =\varnothing$ 。

2)对条件属性 ${C_i} - R$ 进行如下操作：计算 ${\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}$ $ ({a_0}, R, {C_i}, D, {U_i}) \!\!=\!\! \max \{ {\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}({a_k}, R, {C_i},D, {U_i})\} $ ， $R \leftarrow $ $ R \cup \{ {a_0}\} $ ，其中 ${a_k} \in {C_i} - R$ 。若有多个最大值，则选择与 R 组合数最少的属性。

3)计算 ${U_{i + 1}} = {U_i} - {\rm{POS}}_R^{{C_i}}({U_i}, D)$ 。

4)计算 $C_d^{{U_i}} = \{ a \in {C_i} - R:U/{{{T}}_R} = U/{{{T}}_{R \cup \{ a\} }}\} $ ， ${C_{i + 1}} = $ $ {C_i} - C_d^{{U_i}}$ ，令 $i = i + 1$ 。

5)若 $\gamma _R^{{U_i}}(D) = \gamma _{{C_i}}^{{U_i}}(D)$ ，转到6)，否则转到2)。

6)对 $C - R$ 中的每个条件属性 ${a_k}$ ，进行如下操作：

①计算 ${\gamma _{R - \{ {a_k}\} }}(D)$ ；

②若 ${\gamma _{R - \{ {a_k}\} }}(D) = {\gamma _C}(D)$ ，则 ${a_k}$ 为冗余属性，R = $ R - \{ {a_k}\} $ ，否则 ${a_k}$ 为非冗余属性，R 保持不变。

7)返回R。

在算法2中，候选属性集合的正域随着每轮迭代过程选择属性重要度最大的属性加入而增大，因此在计算正域时，可以通过叠加的方式计算，无需重新直接计算新的D关于约简属性集合的正域，证略。

算法2原理流程如图1所示。集值信息系统的快速正域约简算法(quick positive region reduction algorithm，QPRRA)。

算法2无需首先求出核属性，直接迭代选择属性重要度最大的属性加入候选属性集合，因此对于无核的数据集算法效率提升。在约简过程中，根据属性重要度的保序性，即定理5，算法在每轮迭代过程中删除正域和冗余属性，使得数据集规模缩小，算法效率提升。在图1中，A对应算法步骤2)，计算当前轮次需评估的属性重要度，B对应算法步骤3)，删除当前轮次的正域，C对应算法步骤4)，删除当前轮次的冗余属性集合。

下面比较分析PRRA算法和QPRRA算法的时间复杂度。令 ${T_1}$ 和 ${T_2}$ 分别为PRRA算法和QPRRA算法的时间复杂度。令 $|C| = m$ 表示数据集条件属性数， $|U| = n$ 表示数据集对象数， $|{C_i}| = {m_i}$ 表示第i轮需评估的属性数(已删除第 $i - 1$ 轮所求冗余属性数)， $|{U_i}| = {n_i}$ 为第i轮剩余的对象数。在算法2中，计算去掉正区域并且删除冗余属性集合将最大属性重要度的属性加入到当前约简的时间复杂度为 $O(\sum\limits_{i = 1}^{|C|} {{{({m_i} - i + 1)}^2}{n_i}} )$ ，去冗余过程时间复杂度为 $O({m^2}n)$ 。而在算法1中，计算核属性的时间复杂度为 $O({m^2}n)$ ，计算最大属性重要度的属性加入到当前约简的时间复杂度为 $O{(\sum\limits_{i = 1}^{|C|} {(m} - i + 1)^2}n)$ 。去冗余过程时间复杂度为 $O({m^2}n)$ 。PRRA算法时间复杂度为 ${T_1} = O{({m^2}n + \sum\limits_{i = 1}^{|C|} {(m - i} + 1)^2}n)$ ，QPRRA算法时间复杂度为 ${T_2} = O({m^2}n + \sum\limits_{i = 1}^{|C|} {{{({m_i} - i + 1)}^2}{n_i}} )$ 。QPRRA算法效率优于PRRA算法。

例3　 表1为集值决策系统 ${\rm{SDS}} = (U, C \cup D,$ V, f )，其中， $U = \{ {x_1}, {x_2}, {x_3}, {x_4}, {x_5}, {x_6}, {x_7}, {x_8}\} $ 为论域，C = $ \{ {a_1}, {a_2}, {a_3}, {a_4}, {a_5}\} $ 为条件属性集合， $D = \{ d\} $ 为决策属性集合。

采用QPRRA算法对表1进行3轮约简。

第1轮迭代过程：计算 ${C_1} - R$ 中属性的重要度，分别为 ${\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}({a_1},\;$ $ R, {C_1}, D, {U_1}) = 0$ ， ${\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}({a_2}, R, {C_1},$ $D, {U_1}) = 0$ ， ${\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}({a_3},$ $ R, {C_1}, D, {U_1}) \!\!=\!\! 0$ ， ${\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}({a_4}, R, {C_1}, $ $ D, {U_1}) = 0.375$ ， ${\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}({a_5}, $ $ R, {C_1}, D, {U_1}) = 0$ 。由于 ${\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}$ $({a_4},R, {C_1}, D, {U_1}) = 0.375$ 最大，故 R = $ R \cup \{ {a_4}\} = \{ {a_4}\} $ ， ${U_2} = {U_1} - {\rm{POS}}_R^{{C_1}}({U_1}, D){\rm{ = \{ }}{x_1}, {x_3}, {x_5}{\rm{, }}{x_6}{\rm{, }}{x_7}{\rm{\} }}$ ， ${C_2} = {C_1} - C_d^{{U_1}} = $ $ {\rm{\{ }}{a_1}, {a_2}, {a_3}, {a_4}, {a_5}{\rm{\} }}$ ，无冗余属性，且 $\gamma _R^{{U_1}}(D) \ne $ $ \gamma _{{C_1}}^{{U_1}}(D)$ ，继续循环。

第2轮迭代过程：计算 ${C_2} - R$ 中属性的重要度，分别为 ${\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}({a_1}, $ $ R, {C_1}, D, {U_2}) = 0$ ， ${\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}({a_2}, R, {C_1},$ $D, {U_2}) = 0$ ， ${\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}({a_3}, R, $ $ {C_1},D, {U_2}) = 0.4$ ， ${\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}({a_5}, R, {C_1},$ $D, {U_2})= 0$ 。由于 ${\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}({a_3}, R, {C_1}, D, {U_2}) = 0.4$ 最大，故 $R = $ $R \cup \{ {a_3}\} \!=\! \{ {a_3}, {a_4}\}, $ ${U_3} \!=\! {U_2} \!-\! {\rm{POS}}_R^{{C_2}}({U_2}, D){\rm{ = \{ }}{x_1}, {x_3}, {x_5}{\rm{\} }},\;$ ${C_3} \!= $ ${C_2} \!-\! C_d^{{U_2}}{\rm{ = \{ }}{a_1}, {a_2}, {a_3}, {a_5}{\rm{\} }}$ ，无冗余属性。且 $\gamma _R^{{U_2}}(D) \ne $ $\gamma _{{C_2}}^{{U_2}}(D)$ ，继续循环。

第3轮迭代过程：计算 ${C_3} - R$ 中属性的重要度，分别为 ${\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}({a_1}, R, {C_1}, D, {U_3}) \!=\! 0.33$ ， ${\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}({a_2},R, {C_1}, $ $D, {U_3}) \!=\! 0$ ， ${\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}({a_5}, $ $ R, {C_1}, D, {U_3}) = 0.33$ 。由于 Sig^outer $({a_1}, R, {C_1}, D, {U_3}) = $ ${\rm{Si}}{{\rm{g}}^{{\rm{outer}}}}({a_5},$ $R, {C_1}, D, {U_3}) = 0.33$ ，故选择与 $R$ 组合数最少的属性 ${a_1}$ 。故 $R = R \cup \{ {a_1}\} = \{ {a_1}, $ ${a_3}, {a_4}\} $ ， ${U_4} = {U_3} - $ $ {\rm{POS}}_R^{{C_3}}({U_3}, D){\rm{ = \{ }}{x_3}, {x_5}\} $ ， ${C_4} = {C_3} - C_d^{{U_3}}=$ $ {\rm{ \{ }}{a_1}, {a_5}{\rm{\} }}$ ，删除冗余属性 ${a_2}$ 。且 $\gamma _R^{{U_3}}(D) = \gamma _{{C_3}}^{{U_3}}(D)$ ，终止循环。

去除 R 中的冗余属性，由于 ${\gamma _{R - \{ {a_i}\} }}(D) \ne {\gamma _C}(D)$ ， $i = 1, 3, 4$ ，故 R 中无冗余属性，算法终止。故算法QPRRA得到约简，即 $R = \{ a{}_1, {a_3}, {a_4}\} $ 。

3 实验分析

为了证明提出算法的有效性，实验选取了6组UCI标准数据库(http://archive.ics.uci.edu/m-l/)中的数据集，为了得到集值数据集对这6组数据集进行预处理，在条件属性集上随机对10%的数据进行对应属性上的并集操作，如表2所示。

所有实验在PC机上进行，操作系统为Microsoft Windows 7(64 b)，处理器及其型号为Inter Core i5-2450M，内存为4 GB，所有算法均使用MATLAB7.11.0(R2010b)编写实现。在实验中，分别用上述2种约简算法对6组UCI数据集进行处理，比较它们约简所耗费的时间。实验中，将上述6组数据集分别分为10等份，用来记录两个算法的时间差异。例如，假设数据集有1 000个对象，第1号数据集用来表示1~100个对象，第2号数据集用来表示1~200个对象，以此类推，第10号数据集用来表示1~1 000个对象。实验一共分为3个部分。第1部分为算法PRRA、算法QPRRA、基于相似度的集值信息系统属性约简算法^[18](SRA)和基于信息量的集值信息系统属性约简算法^[19](IRA)的约简结果长度和计算时间的比较。第2部分为算法PRRA、QPRRA、SRA和IRA随着论域的增大算法计算时间变化的实验。第3部分为数据集Lung Cancer迭代过程中对象和属性的变化。

表2给出了6组数据集的对象数、特征数和类别数的对比，从表中可以看出，本文选取了不同规模的数据集，最大规模数据集为QSAR Bio-degradation，对象数有1 044个，最小规模数据集为Lung Cancer，对象数有32个，最大特征数数据集SCADI，特征数有206个，而Flag的特征数为29个，在数据集中为特征数最少的。6组数据集有不同的类别数，最大类别数数据集QSAR Biodegrada-tion，类别数为9，数据集Lung Cancer和Molecular Biology类别数最小为2。表3给出了算法PRRA、QPRRA、IRA和SRA的计算时间和选择特征数的对比，可以看出，算法QPRRA和PRRA约简结果长度优于算法SRA和IRA，算法QPRRA效率明显优于算法PRRA和IRA。图2为4种算法的实验对比。

从图2和表3可以看出，算法QPRRA效率优于其他3个算法效率，在数据集QSAR Biodegra dation上，算法SRA略优于算法QPRRA。例如，对于数据集Lung Cancer，算法PRRA时间耗费为37.9 s，算法QPRRA时间耗费为5.2 s，加速比达到了7.2，实验效果明显。因为对于核为空的数据集而言，QPRRA算法无需计算核属性集合，节省了算法求核的时间，并且在每轮迭代过程中，不仅删除了当前轮次候选属性集合产生的正域，也删除了当前轮次产生的冗余属性集合，使得数据集规模不断变小，算法运行时间缩短。从表4可得，Lung Cancer数据集核为空，在每轮迭代过程中删除了正域和冗余属性，使得数据集规模缩小，算法效率提升。

4 结束语

本文提出了一种在集值信息系统下的正域属性保持约简快速算法，算法无需计算核属性集合，直接开始迭代选择属性重要度最大的属性加入候选属性集合，每轮迭代过程中删除一部分正域，使得数据集对象数不断减少，算法效率提升，在删除一部分正域的同时，删除冗余的属性集合，使得算法的效率进一步提升。实验选取6组UCI数据集对提出算法的有效性进行验证，实验表明：提出算法的效率优于经典算法效率，实现了对经典算法的优化，尤其是在无核数据集上加速效果明显，因为省去了计算核属性集的时间，这使得该算法能更好地应用于较大规模数据的处理。本文是基于删除正域和冗余属性机制基础上进行的研究，对每次迭代过程中产生正域和冗余属性较少的数据集加速效果不够明显，故提出算法的普遍适用性是未来研究方向之一。