·1172· 智能系统学报 第14卷 潜在约简集合中，直至满足约束条件则终止算法。 学者的重视。如Yang与Yao2提出的集成选择 因此，接下来需要给出属性重要度的表达式。 器极大地丰富了约简的求解策略：随后，Li等2刃 Sig,(ai.A.D)=y(AUlal,D)-y(A.D)(7) 利用这一思想设计了基于调和平均的多准则属性 SigENT(ai,A,D)=ENT(A,D)-ENT(AU(ai),D)(8) 约简。Lu等进一步利用集成思想，将其扩展 对于近似质量（利用式(7）来计算属性重要 应用到半监督领域中。一般来说，多准则启发式 度)，a的重要度越大，表示a:对其值的提升效果 算法可由算法2实现。 越明显。而对于条件熵而言（利用式(8）来计算属 算法2多准则启发式算法 性重要度)，a,的重要度越大，则表示a,对其值的 输入决策系统DS=<U,ATUD>,半径6 降低效果越明显。 输出一个多准则约简：A 定义5给定一个决策系统DS,YA仁AT,A是 1)计算p(AT,D),p2(AT,D),,pm(AT,Di DS中的一个关于o的约简当且仅当： 2)A←-中 (1)p(4,D)满足约束条件： 3) (2)YA'≤A,(A',D)不满足约束条件。 (1)For1≤k≤m 在定义5中，“o”可以是“y”也可以是“ENT”。 Ha,∈AT-A,计算属性a,的重要度Sig,(a,A,D) 当=y时，约束条件可以定义为4，D)≥AT,D), 选出重要度最大的属性哈 它表示利用约简A中的属性计算的近似质量值应 End For 不低于利用全部属性(AT)计算的近似质量值；而 (2)在{，，…，}中选择一个出现频次最高 当O=ENT时，约束条件则定义为ENT(A,D)≤ 的属性b; ENT(AT,D),它表示利用约简A中的属性计算的 (3)A=AU{b} 条件熵值应不高于利用全部属性(AT)计算的条 (4)计算p(AD),p2(A,D),p(A,D) 件熵值。 4)如果对于任意的1≤k≤m),P(A,D)满足 算法1给出了一个求解定义5所示0约简的 约束条件，则直接转至步骤5)，否则转至步骤3)： 启发式框架型描述。 5)返回A。 算法1启发式算法 算法2的时间复杂度为O(mAT)。在每 输入决策系统DS=<U,ATUD>,半径6 次迭代过程，3)将m个准则下重要度最大的属性 输出一个关于0的约简：A 分别选择出来并记录每个属性出现的频次，选取 1)计算p(AT,D) 频次最高的属性加入到潜在约简集合中：1)如果 2)A←-φ 出现频次最高的属性是唯一的，则直接将其加入 3): 到潜在约简集合中；2)否则，出现频次最高的属 (I)Ya,eAT-A,计算属性a,的重要度Sig(an 性发生冲突情况，即两个或多个属性的频次同 A.D); 时达到最高，则需要进行选择，为了保证算法的 (2)选出一个重要度最大的属性b,令A=AU{b: 稳定性，将位置靠前的属性加入到潜在约简集 (3)计算p(A,D: 合中。 4)如果p(4,D)满足约束条件，则直接转至5) 5)返回A 3一致性采样约简 算法1的时间复杂度为OU·AT),其中 显然，第2节所示的两个算法都是基于扫描 为论域中样本数目，AT为条件属性数目。 数据中的全部样本来实现的。但当数据体量较大 算法1是基于单准则设计的，而运用基于单 时，这种求解策略的时间消耗较高。为了进一步 准则的算法得到的约简往往仅能满足一个约束条 压缩算法的时间消耗，可以将样本选择的方法引 件，而此约简结果可能无法满足其他约束条件。 入到约简求解过程中。不同的样本选择方法会选 例如：仅使用近似质量得到的约简满足自身的约 取不同的样本，进而产生不同的分类效果。本文 束条件，但它往往无法同时提高分类能力，这主 将一致性从样本间距离与样本的决策属性值角度 要是因为近似质量是用来描述数据中的确定性程 出发，目的是使得算法可以利用选择出的样本获 度，而与数据的分类关系不大。为了弥补这一局 取更高的分类精度。算法大致分为两个主要部 限，近年来，根据多准则设计的约简也开始受到 分：1)要全部样本组成的决策系统上进行采样处潜在约简集合中，直至满足约束条件则终止算法。 因此，接下来需要给出属性重要度的表达式。 Sigγ (ai ,A,D) = γ(A∪{ai},D)−γ(A,D) (7) SigENT (ai ,A,D) = ENT(A,D)−ENT(A∪{ai},D) (8) 对于近似质量 (利用式 (7) 来计算属性重要 度)，ai 的重要度越大，表示 ai 对其值的提升效果 越明显。而对于条件熵而言 (利用式 (8) 来计算属 性重要度)，ai 的重要度越大，则表示 ai 对其值的 降低效果越明显。 定义 5 给定一个决策系统 DS, ∀ A ⊆ AT, A 是 DS 中的一个关于 φ 的约简当且仅当： (1) φ(A, D) 满足约束条件； (2) ∀ A' A ⊆ , φ(A', D) 不满足约束条件。 在定义 5 中，“φ”可以是“γ”也可以是“ENT”。 当 φ=γ 时，约束条件可以定义为 γ(A, D)≥γ(AT, D), 它表示利用约简 A 中的属性计算的近似质量值应 不低于利用全部属性 (AT) 计算的近似质量值；而 当 φ=ENT 时，约束条件则定义为 ENT(A, D)≤ ENT (AT, D), 它表示利用约简 A 中的属性计算的 条件熵值应不高于利用全部属性 (AT) 计算的条 件熵值。 算法 1 给出了一个求解定义 5 所示 φ 约简的 启发式框架型描述。 算法 1 启发式算法 输入 决策系统 DS=<U, AT∪D>, 半径 δ 输出 一个关于 φ 的约简：A 1) 计算 φ(AT, D); 2) A←ϕ; 3)： (1) ∀ ai∈AT−A,计算属性 ai 的重要度 Sigφ (ai , A, D); (2) 选出一个重要度最大的属性 b, 令 A=A∪{b}; (3) 计算 φ(A, D); 4) 如果 φ(A, D) 满足约束条件，则直接转至 5) 5) 返回 A 算法 1 的时间复杂度为 O(|U| 2 ·|AT|2 )，其中 |U|为论域中样本数目，|AT|为条件属性数目。 算法 1 是基于单准则设计的，而运用基于单 准则的算法得到的约简往往仅能满足一个约束条 件，而此约简结果可能无法满足其他约束条件。 例如：仅使用近似质量得到的约简满足自身的约 束条件，但它往往无法同时提高分类能力，这主 要是因为近似质量是用来描述数据中的确定性程 度，而与数据的分类关系不大。为了弥补这一局 限，近年来，根据多准则设计的约简也开始受到 学者的重视。如 Yang 与 Yao[26] 提出的集成选择 器极大地丰富了约简的求解策略；随后，Li 等 [27] 利用这一思想设计了基于调和平均的多准则属性 约简。Liu 等 [21] 进一步利用集成思想，将其扩展 应用到半监督领域中。一般来说，多准则启发式 算法可由算法 2 实现。 算法 2 多准则启发式算法 输入 决策系统 DS=<U, AT∪D>, 半径 δ 输出 一个多准则约简：A 1) 计算 φ ··· 1 (AT, D), φ2 (AT, D), , φm(AT, D); 2) A←ϕ; 3) (1) For 1 ≤ k ≤ m ∀ Sigφk (ai ,A,D) a j k ai∈AT−A，计算属性 ai 的重要度 ; 选出重要度最大的属性 ; End For a j 1 a j 2 , ··· a j (2) 在{ , , }m 中选择一个出现频次最高 的属性 b; (3) A=A∪{b}; (4) 计算 φ ··· 1 (A, D), φ2 (A, D), , φm(A, D); 4) 如果对于任意的 k(1≤k≤m), φk (A, D) 满足 约束条件，则直接转至步骤 5); 否则转至步骤 3); 5) 返回 A。 算法 2 的时间复杂度为 O(m·|U| 2 ·|AT|2 )。在每 次迭代过程，3) 将 m 个准则下重要度最大的属性 分别选择出来并记录每个属性出现的频次，选取 频次最高的属性加入到潜在约简集合中：1) 如果 出现频次最高的属性是唯一的，则直接将其加入 到潜在约简集合中；2) 否则，出现频次最高的属 性发生冲突情况，即两个或多个属性的频次同 时达到最高，则需要进行选择，为了保证算法的 稳定性，将位置靠前的属性加入到潜在约简集 合中。 3 一致性采样约简 显然，第 2 节所示的两个算法都是基于扫描 数据中的全部样本来实现的。但当数据体量较大 时，这种求解策略的时间消耗较高。为了进一步 压缩算法的时间消耗，可以将样本选择的方法引 入到约简求解过程中。不同的样本选择方法会选 取不同的样本，进而产生不同的分类效果。本文 将一致性从样本间距离与样本的决策属性值角度 出发，目的是使得算法可以利用选择出的样本获 取更高的分类精度。算法大致分为两个主要部 分：1) 要全部样本组成的决策系统上进行采样处 ·1172· 智 能 系 统 学 报 第 14 卷