定义1^[6] 称S=(U, A∪ D)为一个单尺度决策系统, 其中,

U={x₁, x₂, ···, x_n}

表示论域,

A={a₁, a₂, ···, a_m}

表示非空有限条件属性集, D={d}表示决策属性集, 满足

A∩ D=Ø .

对于∀ j=1, 2, ···, m, 令a_j∶ U→ V_j为一个映射, 其中

$V_{j}=\left\{a_{j}(x) \mid x \in U\right\}$

表示a_j的值域.同理, 对于∀ d∈ D, 也存在一个从U到值域V_d的映射, 即d∶ U→ V_d, 其中V_d表示决策属性d的值域.

对于任意非空子集B⊆A, 等价关系R_B定义如下:

$R_{B}=\{(x, y) \in U \times U \mid a(x)=a(y), \forall a \in B\}, $

其中, R_B将U中的对象划分为互不相交的等价类, 记作U/B, 即

$U / B=\left\{[x]_{B} \mid x \in U\right\}, $

其中

$[x]_{B}=\left\{y \in U \mid(x, y) \in R_{B}\right\}, $

表示包含元素x的等价类.

对于X⊆U, X关于B的下近似$\underline{R_{B}}(X)$与上近似$\overline{R_{B}}(X)$定义如下:

$\underline{R_{B}}(X)=\left\{x \in U \mid[x]_{B} \subseteq X\right\}, $

$\overline{R_{B}}(X)=\left\{x \in U \mid[x]_{B} \cap X \neq \emptyset\right\} . $

决策属性d决定的等价关系如下所示:

$R_{d}=\{(x, y) \in U \times U \mid d(x)=d(y)\}, $

则由d决定的U的划分

$U / D=\left\{D_{1}, D_{2}, \cdots, D_{r}\right\} . $

若R_A⊆R_d, 则称单尺度决策系统S=(U, A∪ D)是协调的; 否则称S是不协调的.

熵度量是刻画粗糙集不确定性的重要工具.为了定量分析可变精度多尺度决策系统中的信息, 本节回顾互补条件熵.

定义2^[24] 设U为一个非空有限集合,

$Q=\left\{Q_{1}, Q_{2}, \cdots, Q_{n_{1}}\right\}, P=\left\{P_{1}, P_{2}, \cdots, P_{n_{2}}\right\}$

均为U上等价关系诱导的划分, 其中, Q包含n₁个等价类Q₁, Q₂, ···, Qn1, P包含n₂个等价类P₁, P₂, ···, Pn2, 则Q关于P的互补条件熵定义如下:

$E(Q \mid P)=\sum_{i=1}^{n_{1}} \sum_{j=1}^{n_{2}}\left(\frac{\left|Q_{i} \cap P_{j}\right|}{|U|} \cdot \frac{\left|Q_{i}^{C} \cap P_{j}\right|}{|U|}\right), $

其中, ·表示集合的基数,

$Q_{i}^{C}=U-Q_{i}=\left\{x \in U \mid x \notin Q_{i}\right\}, $

表示Q_i在U中的补集.

定义3^[14] 称S=(U, A∪ D)为一个广义多尺度决策系统, 其中U={x₁, x₂, ···, x_n}表示论域, A={a₁, a₂, ···, a_m}表示非空有限条件属性集, 且每个属性a_j∈ A均表示多尺度属性.D={d}表示决策属性集, 决策属性d表示单尺度属性.设a_j有I_j个尺度层次, Vjk为a_j在第k尺度的值域, 则一个广义多尺度决策系统可表示如下:

$S=\left(U, \left\{a_{j}^{k} \mid k=1, 2, \cdots, I_{j}, j=1, 2, \cdots, m\right\} \cup D\right) .$

本文约定, 随着 ajk的上标k增大, a_j的尺度变细.因此, 对于I_j≥ k≥ 2, 存在一个满射

$g_{j}^{k, k-1}: V_{j}^{k} \longrightarrow V_{j}^{k-1}$,

使得

$a_{j}^{k-1}(x)=g_{j}^{k, k-1} 。\left(a_{j}^{k}(x)\right), $

即

ajk-1(x)= gjk, k-1( ajk(x)), x∈ U,

其中 gjk, k-1表示信息粒度变换.

定义4^[14] 设S=(U, A∪ D)为一个广义多尺度决策系统.对于属性a_j∈ A, 若取其第l_j个尺度标记, 1≤ l_j≤ I_j, j=1, 2, ···, m, 则K=(l₁, l₂, ···, l_m)为S的一个尺度组合.该组合下的属性集记为

A^K={ a1l1, a2l2, ···, amlm},

由K形成的单尺度决策系统记为S^K=(U, A^K∪ D).S中所有尺度组合的集合称为尺度组合全集, 记为

$\Omega^{+}=\left\{\left(l_{1}, l_{2}, \cdots, l_{m}\right) \mid 1 \leqslant l_{j} \leqslant I_{j}, j=1, 2, \cdots, m\right\} . $

由于 ajk的上标k增大时a_j的尺度变细, 故最细尺度组合

I=(I₁, I₂, ···, I_m),

最粗尺度组合

CSC=(1, 1, ···, 1).

设

K=(l₁, l₂, ···, l_m)∈ Ω ⁺,

$K^{\prime}=\left(l_{1}^{\prime}, l_{2}^{\prime}, \cdots, l_{m}^{\prime}\right) \in \Omega^{+}, $

若对∀ j=1, 2, ···, m, 有l_j≥ l'_j, 则称K比K'细, 或K'比K粗, 记作K⪰K'.若K⪰K'且至少存在一个j使l_j> l'_j, 则称K严格细于K', 或K'严格粗于K, 记作K≻K'.若K和K'满足K⪰K'或K'⪰K, 称二者可比; 否则不可比.

命题1 设S=(U, A∪ D)为一个广义多尺度决策系统.对于任意尺度组合K∈ Ω ⁺, 由A^K决定的等价关系定义如下:

$\begin{array}{l} R_{A^{K}}= \left\{(x, y) \in U \times U \mid a_{j}^{l_{j}}(x)=a_{j}^{l_{j}}(y), j=1, 2, \cdots, m\right\}, \end{array}$

则由A^K决定的U的划分表示如下:

$U / A^{K}=\left\{[x]_{A^{K}} \mid x \in U\right\}, $

其中

$[x]_{A^{K}}=\left\{y \in U \mid(x, y) \in R_{A^{K}}\right\} . $

假设K∈ Ω ⁺, K'∈ Ω ⁺且K⪰K', 则

$R_{A^{K}} \subseteq R_{A^{K^{\prime}}}, [x]_{A^{K}} \subseteq[x]_{A^{K^{\prime}}} $.

现有广义多尺度决策系统的上、下近似多基于Pawlak粗糙集, 缺乏对噪声数据的容错能力, 因此在实际含噪数据处理中鲁棒性受限.为此, 将可变精度引入广义多尺度决策系统, 提升模型的泛化能力.

定义5^[18] 设S=(U, A∪ D)为一个广义多尺度决策系统, 对于K∈ Ω ⁺, 0.5< β ≤ 1, X⊆U, 则X关于A^K的β 下近似与β 上近似定义如下:

$\underline{R_{A^{K}}^{\beta}}(X)=\left\{x \in U \mid P\left(X \mid[x]_{A^{K}}\right) \geqslant \beta\right\}, $

$\overline{R_{A^{K}}^{\beta}}(X)=\left\{x \in U \mid P\left(X \mid[x]_{A^{K}}\right)> 1-\beta\right\}, $

其中

$P\left(X \mid[x]_{A^{K}}\right)=\frac{\left|[x]_{A^{K}} \cap X\right|}{\left|[x]_{A^{K}}\right|} . $

对于U/D={D₁, D₂, ···, D_r}, 有

$\underline{R_{A^{K}}^{\beta}}(D)=\bigcup_{i=1}^{r} \underline{R_{A^{K}}^{\beta}}\left(D_{i}\right), $

$\overline{R_{A^{K}}^{\beta}}(D)=\bigcup_{i=1}^{r} \overline{R_{A^{K}}^{\beta}}\left(D_{i}\right) . $

D关于A^K的β 正域定义如下:

${POS}_{A^{K}}^{\beta}(D)=\underline{R_{A^{K}}^{\beta}}(D) . $

然而, 上述经典可变精度广义多尺度粗糙集模型不具备单调性.具体而言, 当尺度组合由粗变细时, 其上、下近似与正域并不呈现单调的变化规律, 这为最优尺度组合的选择带来挑战.为了解决此问题, 学者提出单调的可变精度多尺度粗糙集模型.

定义6^[20] 设S=(U, A∪ D)为一个广义多尺度决策系统, 对于K∈ Ω ⁺, 0.5< β ≤ 1, X⊆U, 最细尺度组合I, 则X关于A^K的β 下近似、 β 上近似和β 正域定义如下:

$\underline{M R_{A^{K}}^{\beta}}(X)=\underline{R_{A^{K}}}\left(\underline{R_{A^{I}}^{\beta}}(X)\right), $

$\overline{M R_{A^{K}}^{\beta}}(X)=\overline{R_{A^{K}}}\left(\overline{R_{A^{I}}^{\beta}}(X)\right), $

${MPOS}_{A^{K}}^{\beta}(X)=M R_{A^{K}}^{\beta}(X) . $

定理1 设S=(U, A∪ D)为一个广义多尺度决策系统, 对于0.5< β ≤ 1, I=(I₁, I₂, ···, I_m), X⊆U, 若K∈ Ω ⁺, K'∈ Ω ⁺满足K⪰K', 则如下性质成立:

1) $\underline{M R_{A^{K^{\prime}}}^{\beta}}(X) \subseteq \underline{M R_{A^{K}}^{\beta}}(X)$,

2) $\overline{M R_{A^{K^{\prime}}}^{\beta}}(X) \supseteq \overline{M R_{A^{K}}^{\beta}}(X) $,

3) ${MPOS}_{A^{K^{\prime}}}^{\beta}(X) \subseteq {MPOS}_{A^{K}}^{\beta}(X)$ .

为了刻画粗糙集上的不确定性与模糊性, 并降低噪声影响, Liang等^[24]提出互补条件熵并用于冗余特征约简.然而, 可变精度的引入虽提升广义多尺度决策系统的泛化性与鲁棒性, 却破坏单调性.为此, 基于互补条件熵与单调的可变精度粗糙集模型, 提出单调的可变精度互补条件熵.

定义7 设S=(U, A∪ D)为一个广义多尺度决策系统, 对于K∈ Ω ⁺, 0.5< β ≤ 1, 最细尺度组合I, U/D={D₁, D₂, ···, D_r}, 则D关于A^K的可变精度正域互补条件熵定义如下:

$\begin{array}{l} {VPPE}_{\beta}\left(D \mid A^{K}\right)= \\ \qquad \sum_{i=1}^{p} \sum_{j=1}^{r}\left(\frac{\left|\widetilde{X}_{i} \cap D_{j}^{\beta}\right|}{|{POS}|} \cdot \frac{\left|\widetilde{X}_{i} \cap\left(D_{j}^{\beta}\right)^{c}\right|}{|{POS}|}\right), \end{array}$

其中,

Djβ=PO SAIβ(D_j),

表示最细尺度组合I下决策类D_j的β 正域, 且

${POS}={POS}_{A^{I}}^{\beta}(D)=\bigcup_{j=1}^{r} D_{j}^{\beta}, $

$\widetilde{X}=P O S / A^{K}=\left\{[x]_{A^{K}} \mid x \in P O S\right\}, $

满足

$\bigcup_{i=1}^{p} \widetilde{X}_{i}=P O S . $

需要注意的是, 下文始终假设关于最细尺度组合I的决策属性D的β 正域为非空集.

命题2 设S=(U, A∪ D)为一个广义多尺度决策系统, 对于0.5< β ≤ 1, 最细尺度组合I, K∈ Ω ⁺, 则有

1) ${VPPE}_{\beta}\left(D \mid A^{I}\right)=0, $

2). ${VPPE}_{\beta}\left(D \mid A^{K}\right) \geqslant 0 . $

证明 对于1), 在最细尺度组合I下, 记

U/A^I={X₁, X₂, ···, X_p}.

根据可变精度粗糙集的定义, 决策类D_j的β 下近似

$D_{j}^{\beta}={POS}_{A^{I}}^{\beta}\left(D_{j}\right)=\left\{x \in U: P\left(D_{j} \mid[x]_{A^{I}}\right) \geqslant \beta\right\}, $

正域

${ POS }=\bigcup_{j=1}^{r} D_{j}^{\beta} . $

对于∀ X_i∈ U/A^I, 若X_i⊆POS, 则存在唯一的j使得X_i⊆ Djβ.因此, 在正域划分POS/A^I中, 每个$\widetilde{X}_{i}$必然完全包含于某个 Djβ.于是, 对于每个$\widetilde{X}_{i}$和每个j, 若$\widetilde{X}_{i} \subseteq D_{j}^{\beta}$, 则

$\left|\widetilde{X}_{i} \cap D_{j}^{\beta}\right|=\left|\widetilde{X}_{i}\right|, \left|\widetilde{X}_{i} \cap\left(D_{j}^{\beta}\right)^{c}\right|=0. $

对于 j'≠ j, 则

$\left|\widetilde{X}_{i} \cap D_{j^{\prime}}^{\beta}\right|=0 . $

代入定义7得

${VPPE}_{\beta}\left(D \mid A^{I}\right)=0 . $

对于2), ∀ K∈ Ω ⁺, 由定义可知, $\left|\widetilde{X}_{i} \cap D_{j}^{\beta}\right|$与$\left|\widetilde{X}_{i} \cap\left(D_{j}^{\beta}\right)^{c}\right|$均为非负整数, 且$|{POS}|> 0$.因此, 定义式中的每项均为非负实数, 其有限和仍为非负, 即

${VPPE}_{\beta}\left(D \mid A^{K}\right) \geqslant 0 . $ 证毕.

定理2 设S=(U, A∪ D)为一个广义多尺度决策系统, 对于0.5< β ≤ 1, 若K∈ Ω ⁺, K'∈ Ω ⁺, 满足K⪰K', 则

${VPPE}_{\beta}\left(D \mid A^{K}\right) \leqslant {VPPE}_{\beta}\left(D \mid A^{K^{\prime}}\right) . $

证明 记

${POS}={POS}_{A^{I}}^{\beta}(D)=\bigcup_{j=1}^{r} D_{j}^{\beta}$

为最细尺度组合I的β 正域,

$\widetilde{X}=P O S / A^{K}=\left\{\widetilde{X}_{1}, \widetilde{X}_{2}, \cdots \widetilde{X}_{p}\right\}$

为K在POS下划分出的等价类,

$\widetilde{X}^{\prime}=\operatorname{POS} / A^{K^{\prime}}=\left\{\widetilde{X}_{1}^{\prime}, \widetilde{X}_{2}^{\prime}, \cdots, \widetilde{X}_{p^{\prime}}^{\prime}\right\}$

为K'在POS下划分出的等价类.

由于K⪰K', 由命题1可知对∀ x∈ U有 [x]AK⊆ [x]AK', 因此对于 X˜'中任意等价类 X˜'_i, 存在下标集合I_i⊆{1, 2, ···, p}, 使得

$\widetilde{X}_{i}^{\prime}=\bigcup_{t \in I^{i}} \widetilde{X}_{t}$.

考虑乘积项:

$T_{K}(t, j)=\left|\widetilde{X}_{t} \cap D_{j}^{\beta}\right| \cdot\left|\widetilde{X}_{t} \cap\left(D_{j}^{\beta}\right)^{c}\right|, $

$T_{K^{\prime}}(i, j)=\left|\widetilde{X}_{i}^{\prime} \cap D_{j}^{\beta}\right| \cdot\left|\widetilde{X}_{i}^{\prime} \cap\left(D_{j}^{\beta}\right)^{c}\right| . $

当 X˜'_i⊆ Djβ时, 有 X˜t⊆ X˜'_i⊆ Djβ, 因此有

$\left|\widetilde{X}_{i}^{\prime} \cap\left(D_{j}^{\beta}\right)^{c}\right|=0, \left|\widetilde{X}_{t} \cap\left(D_{j}^{\beta}\right)^{c}\right|=0 . $

从而有

$T_{K}(t, j)=0, T_{K^{\prime}}(i, j)=0 . $

当 X˜'_i⊄ Djβ时, 有

$\left|\widetilde{X}_{i}^{\prime} \cap\left(D_{j}^{\beta}\right)^{c}\right|> 0, $

因为 X˜t⊆ X˜'_i , 所以有

$T_{K}(t, j) \leqslant T_{K^{\prime}}(i, j) . $

综合上述两种情况, 对∀ X˜'_i∈ X˜', t∈ I_i及j, 均有

$T_{K}(t, j) \leqslant T_{K^{\prime}}(i, j) $

对于下标集合I_i, 有

$\begin{array}{l} \sum_{t=1}^{p} \sum_{j=1}^{r}\left|\widetilde{X}_{t} \cap D_{j}^{\beta}\right| \cdot\left|\widetilde{X}_{t} \cap\left(D_{j}^{\beta}\right)^{c}\right|= \\ \quad \sum_{i=1}^{p^{\prime}} \sum_{t \in I_{i}} \sum_{j=1}^{r}\left|\widetilde{X}_{t} \cap D_{j}^{\beta}\right| \cdot\left|\widetilde{X}_{t} \cap\left(D_{j}^{\beta}\right)^{c}\right| \leqslant \\ \quad \sum_{i=1}^{p^{\prime}} \sum_{t \in I_{i}} \sum_{j=1}^{r}\left|\widetilde{X}_{i}^{\prime} \cap D_{j}^{\beta}\right| \cdot\left|\widetilde{X}_{i}^{\prime} \cap\left(D_{j}^{\beta}\right)^{c}\right|= \\ \quad \sum_{i=1}^{p^{\prime}}\left|I_{i}\right| \sum_{j=1}^{r}\left|\widetilde{X}_{i}^{\prime} \cap D_{j}^{\beta}\right| \cdot\left|\widetilde{X}_{i}^{\prime} \cap\left(D_{j}^{\beta}\right)^{c}\right| \leqslant \\ \quad \sum_{i=1}^{p^{\prime}} \sum_{j=1}^{r}\left|\widetilde{X}_{i}^{\prime} \cap D_{j}^{\beta}\right| \cdot\left|\widetilde{X}_{i}^{\prime} \cap\left(D_{j}^{\beta}\right)^{c}\right| . \end{array}$

根据定义7, 得

${VPPE}_{\beta}\left(D \mid A^{K}\right) \leqslant {VPPE}_{\beta}\left(D \mid A^{K^{\prime}}\right) . $ 证毕.

定理2表明, 随着尺度组合由粗变细, 可变精度正域互补条件熵具有单调性, 因此可使用局部的思想定义最优尺度组合.

定义8 设S=(U, A∪ D)为一个广义多尺度决策系统, K=(l₁, l₂, ···, l_m)∈ Ω ⁺.对于任意满足l_j> 1的属性a_j (1≤ j≤ m), 将a_j的尺度变粗一级后得到的子尺度组合K'_j定义如下:

$K_{j}^{\prime}=\left(l_{1}, \cdots, l_{j-1}, l_{j}-1, l_{j+1}, \cdots, l_{m}\right) . $

K在Ω ⁺中所有子尺度组合集合定义如下:

${Child}_{\Omega^{+}}(K)=\left\{K_{j}^{\prime} \in \Omega^{+} \mid\right.$

$\left.K_{j}^{\prime}=\left(l_{1}, \cdots, l_{j-1}, l_{j}-1, l_{j+1}, \cdots, l_{m}\right), j=1, 2, \cdots, m\right\} . $

定义9 设S=(U, A∪ D)为一个广义多尺度决策系统, 0.5< β ≤ 1, 若K^* ∈ Ω ⁺, 且K^* 符合如下条件, 则称K^* 为S的可变精度互补条件熵最优尺度组合:

1)K^* 是关于S的可变精度互补条件熵协调的尺度组合, 即

${VPPE}_{\beta}\left(D \mid A^{K^{* }}\right)={VPPE}_{\beta}\left(D \mid A^{I}\right)=0 . $

2)对∀ K∈ Chil dΩ+(K^* )都不是关于S的可变精度互补条件熵协调的尺度组合, 即

${VPPE}_{\beta}\left(D \mid A^{K}\right) \neq {VPPE}_{\beta}\left(D \mid A^{I}\right) . $

在广义多尺度决策系统中, 传统基于正域变化的单尺度属性重要性评价方法对噪声较敏感, 而常规约简算法通常依赖最优尺度组合.为了提高计算效率, 本文在最优尺度选择前进行属性约简, 并基于可变精度正域互补条件熵设计协调的与分类驱动的属性约简方法.

定义10 设S=(U, A∪ D)为一个广义多尺度决策系统, 对于任意属性子集B⊆A, 设

B={ as1, as2, ··· ast}, t= B,

则可得到一个新的广义多尺度决策系统S^B=(U, B∪ D), S^B中所有尺度组合的集合记为 ΩB+, 即

$\Omega_{B}^{+}=\left\{\left(l_{s_{1}}, l_{s_{2}}, \cdots, l_{s_{t}}\right) \mid 1 \leqslant l_{s_{j}} \leqslant I_{s_{j}}, j=1, 2, \cdots, t\right\}, $

其中最细尺度组合I_B=( Is1, Is2, ···, Ist), 最粗尺度组合CSC_B=(1, 1, ···, 1).对于任意尺度组合

K_B=( ls1, ls2, ···, lst)∈ ΩB+,

在K_B下构成的属性集记为 BKB={ as1ls1, as2ls2, ··· astlst}, 在 BKB下形成的单尺度决策系统记为

SBKB=(U, BKB∪ D).

定理3 设S=(U, A∪ D)为一个广义多尺度决策系统, 对于B₁⊆A, B₂⊆A, 0.5< β ≤ 1, KB1∈ ΩB1+, KB2∈ ΩB2+, 若有B₁⊆B₂, 则

${VPPE}_{\beta}\left(D \mid B_{2}^{K_{B_{2}}}\right) \leqslant {VPPE}_{\beta}\left(D \mid B_{1}^{K_{B_{1}}}\right) . $

证明 由于B₁⊆B₂, S^K=(U, A^K∪ D)为一个单尺度决策系统, 任取(x, y)∈ RB2, 由定义知∀ a∈ RB2, a(x)=a(y), 因此上述条件对∀ a∈ B₁也成立, 即∀ a∈ B₁, a(x)=a(y)有(x, y)∈ RB2.因此 RB2⊆ RB1.从而可知对∀ x∈ U有, [x ]B2KB2⊆[x ]B1KB1, 后续证明和定理2类似, 此处略.

定理3表明, 属性子集之间的可变精度正域互补条件熵是具有单调性的, 因此可使用局部的思想定义属性约简.

定义11 设S=(U, A∪ D)为一个广义多尺度决策系统, 0.5< β ≤ 1, 若属性子集B⊆A, 且B符合如下条件, 则称B为S的可变精度互补条件熵约简:

1)B是关于S的一个可变精度互补条件协调集, 即

${VPPE}_{\beta}\left(D \mid B^{I_{B}}\right)={VPPE}_{\beta}\left(D \mid A^{I}\right)=0 ; $

2)B的真子集都不是关于S的一个可变精度互补条件协调集, 即对于∀ c∈ B, 有

${VPPE}_{\beta}\left(D \mid\{B-c\}^{I_{\{B-c\}}}\right) \neq {VPPE}_{\beta}\left(D \mid A^{I}\right) . $

在广义多尺度决策系统中, 由命题2可知, 最细尺度组合本身是可变精度正域互补条件熵协调的, 并包含系统的最完整信息.鉴于此, 判断属性冗余性时, 可使用最细尺度组合下的条件熵作为参考:若某属性在最细尺度下不提供额外信息, 其对决策的贡献可忽略, 从而可从约简子集中删除.通过逐步选择那些能显著降低互补条件熵的属性, 得到协调的约简子集.

基于上述定义及相关定理, 本文进一步设计前向启发式协调的属性约简算法, 具体步骤如下.

算法1 多尺度决策系统中基于可变精度正域互补条件熵的前向协调的属性约简算法

输入 S=(U, A∪ D), 精度β , 最细尺度组合I

输出 协调的约简子集B

B=Ø ; // 初始化已选属性子集为空

while VPPE_β (D| BIB)> 0 do

VPPE_min=∞ , a_best=None; // 初始化最小目标函数值与最优属性

for (each a∈ A-B) do

计算 ${VPPE}_{\beta}\left(D \mid\{B \cup\{a\}\}^{I_{\{B \cup\{a\}\}}}\right)$;

// 计算加入候选属性后的可变精度正域互补条件熵

if ${VPPE}_{\beta}\left(D \mid\{B \cup\{a\}\}^{I_{\{B \cup\{a\}\}}}\right)＜{VPPE}_{\min }$

then

VPPE_min=VPPE_β (D| {B⋃{a}}I{B⋃{a}});

a_best=a;

end if

end for

if a_best=None then

break; // 没有属性可以降低条件熵

end if

B← B∪ {a_best};

VPPE_β (D| BIB)=VPPE_min;

end while

return B

在算法1中, 计算可变精度互补条件熵的时间复杂度在最坏情况下为O(n²), 其中n=|U|表示论域对象总数.算法1的核心循环为for语句, 每轮需要对所有候选属性计算一次熵的值, 最多有m=|A|个候选属性, 每轮时间复杂度为O((m-|B|)n²).整个循环最多进行m轮选择, 因此算法1的最坏时间复杂度为:

$O\left(\sum_{i=0}^{m-1}(m-i) n^{2}\right)=O\left(m^{2} n^{2}\right) . $

算法1实现多尺度决策系统中在最优尺度选择之前的协调的属性约简.在迭代过程中, 算法依据可变精度互补条件熵的下降程度逐步选取属性, 并最终返回一个按照属性贡献度排序的属性集合.需要注意的是, 算法1返回的结果是一个协调的属性集, 该属性集仍可能包含冗余特征.正如Yang等^[27]指出:即使属性集是协调的, 其分类性能不一定最优; 通过去除部分冗余属性, 属性集的分类精度反而可能得到提升.基于此启发及算法1, 对约简子集进行优化, 寻找分类效果最优的属性子集, 设计如下算法2.

算法2 多尺度决策系统中的最优属性约简算法

输入 算法1得到的B={ as1, as2, ···, ast},

最细尺度组合I

输出 最优约简子集B^*

令B₁={ as1}, B₂={ as1, as2}, ···, B_t={ as1, as2, ··· ast};

for i=1 to t do

使用选定的分类器计算Acc( BiIBi);

end for

if Acc( Bi0IBi0)= max1≤i≤t(Acc( BiIBi)) then

B^* ← Bi0;

end if

return B^*

算法2基于算法1所得约简子集进行增量构造.若某候选特征子集的可变精度正域互补条件熵不为0, 并能实现最高分类精度, 则将其作为最优近似约简.根据定义11, 协调的约简子集可保证与最细尺度组合是保持协调的.然而, 对于包含大量对象的单尺度决策系统, 算法1往往会选择全部特征, 导致关键属性难以识别.因此, 算法2在协调的约简基础上进一步筛选特征, 获得更适于分类的近似约简子集.

在算法2中, 针对单尺度决策系统S=(U, A∪ D)使用选定分类器进行分类, 分类精度定义为正确预测样本所占比例:

Acc(A)= NCNT,

其中, N_C表示正确预测样本数, N_T表示总样本数.时间复杂度主要取决于分类器的训练与验证过程.在最坏情况下, 算法2的时间复杂度为

O(KmT_max(n, m)),

其中, n表示样本数, m表示属性个数, K表示交叉验证折数, T_max(n, m)表示分类器T在样本和属性中训练与测试的最坏时间复杂度.

在广义多尺度决策系统中, 最优尺度组合的选择直接影响知识表示粒度及分类性能.现有方法通常基于完整属性集进行尺度选择, 默认与最细尺度组合是保持协调的.然而, 在实际应用中, 经过属性约简, 尤其是基于分类性能的约简后, 约简子集与最细尺度组合可能不再保持协调.因此, 本研究基于可变精度互补条件熵, 提出基于属性子集的最优尺度组合定义及选择算法.

定义12 设S=(U, A∪ D)为一个广义多尺度决策系统, 0.5< β ≤ 1, B⊆A, I_B为S^B=(U, B∪ D)的最细尺度组合.若 KB*∈ ΩB+, 且符合如下条件, 则称 KB*为S^B的可变精度互补条件熵最优尺度组合:

1) KB*是关于S^B的可变精度互补条件熵协调的尺度组合, 即

${VPPE}_{\beta}\left(D \mid B^{K_{B}^{* }}\right)={VPPE}_{\beta}\left(D \mid B^{I_{B}}\right) $

2)对∀ K_B∈ Chil dΩ+( KB*)都不是关于S^B的可变精度互补条件熵协调的尺度组合, 即

${VPPE}_{\beta}\left(D \mid B^{K_{B}}\right) \neq {VPPE}_{\beta}\left(D \mid B^{I_{B}}\right) . $

逐步式最优尺度组合选择方法虽然能在大规模数据集上获得最优尺度组合, 但其从细到粗逐一检验尺度的搜索策略容易引入冗余计算, 且多数方法未充分考虑属性贡献度排序对尺度搜索效率的影响.

为此, 本文提出结合二分查找策略与属性贡献度排序的最优尺度选择算法, 具体步骤如下.

算法3 基于约简子集的最优尺度组合选择算法

输入 S=(U, A∪ D), 精度β , 最细尺度组合I, 最粗尺度组合CSC, 最优约简子集B^*

输出 关于B^* 的可变精度互补条件熵最优尺度组合 KB* *

计算VPPE_β (D| (B* )IB*);

lower← CSC=(1, 1, ···, 1),

upper← I=(I₁, I₂, ···, I_m); // 初始化尺度组合搜索区间

while true do

mid← 「(lower+upper)/2⌉;

计算VPPE_β (D| (B* )midB*);

if ${VPPE}_{\beta}\left(D \mid\left(B^{*}\right)^{\operatorname{mid}_{B} *}\right)={VPPE}_{\beta}\left(D \mid\left(B^{*}\right)^{I_{B} *}\right)$

then

upper← mid;

else

lower← mid;

end if

new_mid← 「(lower+upper)/2⌉;

if new_mid=mid then

break;

end if

end while

KB* *← mi dB*;

for(each a∈ B^* ) do //按约简顺序

while K*(a)> CSC(a) do

//属性a的尺度大于其最粗尺度

K'(a)← K*(a)-1; //将属性a的尺度减1

计算${VPPE}_{\beta}\left(D \mid\left(B^{*}\right)^{K^{\prime}(a)_{B^{*}}}\right)$;

if ${VPPE}_{\beta}\left(D \mid\left(B^{*}\right)^{K^{\prime}(a) B^{*}}\right)={VPPE}_{\beta}\left(D \mid\left(B^{*}\right)^{I_{B^{*}}}\right)$

then

K^* (a)← K'(a);

else

break;

end if

end while

end for

return KB* *

算法3主要包括两个阶段.第一阶段通过二分查找策略确定一个协调的尺度组合; 第二阶段依据算法2得到的属性贡献度顺序, 对约简子集B^* 中的各属性尺度逐一进行调整, 获得最终的最优尺度组合.在第一阶段中, 每次迭代均将搜索空间缩小一半, 因此最多进行O(log₂K)次迭代, 其中K表示最细尺度组合I中的最大尺度值.第二阶段按照属性约简子集B^* 中的顺序进行尺度调整.在最坏情况下, 对于任意属性a∈ B^* , 其尺度需要从初始值K^* (a)逐步调整至最粗尺度CSC(a), 最多进行K^* (a)-CSC(a)次尝试.综合上述两部分, 算法3的总体时间复杂度为:

$O\left(n^{2}\left(\log _{2} K+\sum_{a \in B^{* }}\left(K^{* }(a)-\operatorname{CSC}(a)\right)\right)\right) . $