·1206· 智能系统学报 第14卷 小析取范式时，MGDRDM算法也将占用更小空 某些情况下，添加属性求解约简反而会使耗 间。当选定特定类为全部决策类时，MGDRDM 时减少，这可能是因为在添加属性之后构造差别 算法将退化为全决策类约简，占用空间不会减小。 矩阵的过程中产生了较添加属性之前更短的非空 表4差别矩阵非空属性集占比 属性集，这使得构造区分函数以及求取极小析取 Table 4 The proportion of non-empty attribute sets in the 范式的过程耗时减少，所以在某些情况添加属性 discernibility matrix 反而求解更快。 全决策类 单特定类 多特定类 ID 数据集 0.8 0 单特定类（决策值2） 占比%决策值占比%决策值占比% 0.7 多特定类（决策值2,4） 0.6 △一全决策类 Zoo 75.7 2 11.2 2.4 20.1 Audiology 85.0 4 9.6 1,4,6,11 22.9 量8 Glass 71.3 6 5.8 5.6 10.2 0.2 House 22.2 0 3.1 0,2 6.7 0.1 5 Connectionist 90.8 0 8.3 0.2 16.6 6 810 121416 属性数量 6 Yeast 53.5 5 4.3 58 7.1 (a)Zoo 20 单特定类（决策值：4） 3.3约简效率对比 18 0 多特定类（决策值：1,4,6,11） 本节将6组数据集，依据随属性数目递增的 16 。一全决策类 14 时间消耗进行经典不完备决策系统广义决策约简 10 与MGDRDM算法之间约简效率对比。约简效率 12 8 如图1所示，其中“全决策类”表示经典全类不完 6 备决策系统广义决策约简算法随属性数目增加的 3 约简耗时变化曲线，“单特定类”和“多特定类”则 10 20304050 60 表示MGDRDM算法分别选定一个和多个特定类 属性数量 随属性数目增加的约简耗时变化曲线，“决策值” (b)Audiology 表示选定特定类所表现的决策值。 0.9 0 单特定类（决策值：5 0.8 多特定类（决策值：5,6） 由图1可知，选取特定类数量相对全部决策 0.7 。一全决策类 类数量较少时，约简效率相较对比算法会有明显 的提升，这是由于多特定类广义决策约简的差别 0.5 0.4 矩阵中非空属性集的数目小于全决策类广义决策 0.3 约简的差别矩阵中非空属性集的数目，所以MG 0.2 0.1 DRDM算法在构造差别矩阵时耗时会有所减 少。另外，因多特定类广义决策约简的差别矩阵 0 345678910 属性数量 中非空属性集数目偏少，所以构造区分函数以及 (c)Glass 求取极小析取范式耗时相对较少，因此约简效率 5.0 0 单特定类（决策值0） 4.5 。-多特定类（决策值0,2） 更高。除此之外，随着属性数目的增加，算法之 4.0 4一全决策类 间耗时差距越发明显，这是由于随着属性数目的 3.5 3.0 增加，差别矩阵也愈加复杂，使得构造区分函数 2.5 以及计算极小析取范式时计算量增大，而且MG DRDM算法构造差别矩阵中非空属性集数目较 1.0 少，所以耗时增长缓慢，两个算法之间耗时差距 0.5 越明显。当多特定类选择为所有决策类时，算法 4. 1012 属性数量 退化为全类约简，此时约简效率并无明显提升。 (d)House小析取范式时，MGDRDM 算法也将占用更小空 间。当选定特定类为全部决策类时，MGDRDM 算法将退化为全决策类约简，占用空间不会减小。 表 4 差别矩阵非空属性集占比 Table 4 The proportion of non-empty attribute sets in the discernibility matrix ID 数据集 全决策类 单特定类 多特定类 占比/% 决策值 占比/% 决策值 占比/% 1 Zoo 75.7 2 11.2 2,4 20.1 2 Audiology 85.0 4 9.6 1,4,6,11 22.9 3 Glass 71.3 6 5.8 5,6 10.2 4 House 22.2 0 3.1 0,2 6.7 5 Connectionist 90.8 0 8.3 0,2 16.6 6 Yeast 53.5 5 4.3 5,8 7.1 3.3 约简效率对比 本节将 6 组数据集，依据随属性数目递增的 时间消耗进行经典不完备决策系统广义决策约简 与 MGDRDM 算法之间约简效率对比。约简效率 如图 1 所示，其中“全决策类”表示经典全类不完 备决策系统广义决策约简算法随属性数目增加的 约简耗时变化曲线，“单特定类”和“多特定类”则 表示 MGDRDM 算法分别选定一个和多个特定类 随属性数目增加的约简耗时变化曲线，“决策值” 表示选定特定类所表现的决策值。 由图 1 可知，选取特定类数量相对全部决策 类数量较少时，约简效率相较对比算法会有明显 的提升，这是由于多特定类广义决策约简的差别 矩阵中非空属性集的数目小于全决策类广义决策 约简的差别矩阵中非空属性集的数目，所以 MG￾DRDM 算法在构造差别矩阵时耗时会有所减 少。另外，因多特定类广义决策约简的差别矩阵 中非空属性集数目偏少，所以构造区分函数以及 求取极小析取范式耗时相对较少，因此约简效率 更高。除此之外，随着属性数目的增加，算法之 间耗时差距越发明显，这是由于随着属性数目的 增加，差别矩阵也愈加复杂，使得构造区分函数 以及计算极小析取范式时计算量增大，而且 MG￾DRDM 算法构造差别矩阵中非空属性集数目较 少，所以耗时增长缓慢，两个算法之间耗时差距 越明显。当多特定类选择为所有决策类时，算法 退化为全类约简，此时约简效率并无明显提升。 某些情况下，添加属性求解约简反而会使耗 时减少，这可能是因为在添加属性之后构造差别 矩阵的过程中产生了较添加属性之前更短的非空 属性集，这使得构造区分函数以及求取极小析取 范式的过程耗时减少，所以在某些情况添加属性 反而求解更快。 2 4 6 8 10 12 14 16 属性数量 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 约简耗时/s 单特定类 (决策值:2) 多特定类 (决策值:2,4) 全决策类 10 20 30 40 50 60 属性数量 0 2 4 6 8 10 12 14 16 18 20 约简耗时/s 单特定类 (决策值:4) 多特定类 (决策值:1,4,6,11) 全决策类 (a) Zoo 1 2 3 4 5 6 7 8 9 10 属性数量 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 约简耗时/s 单特定类(决策值:5) 多特定类(决策值:5,6) 全决策类 (c) Glass (b) Audiology 单特定类 (决策值:0) 多特定类 (决策值:0,2) 全决策类 2 4 6 8 10 12 属性数量 0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0 约简耗时/s (d) House ·1206· 智 能 系 统 学 报 第 14 卷