第3期 尹继亮，等：不协调区间值决策系统的最大分布约简 ·477· % PRADM 提出的算法是在可辨识矩阵基础上的，其时间和空 80 70 -MDRADM 间复杂度较高，不利于在实际应用中推广，故提出 高效率的约简算法是未来研究方向之一。 0 酒3 参考文献： 0 10 [1]PAWLAK Z.Rough sets[J].International journal of com- 100200300400500600700800900 对象数量 puter information sciences,1982,11(5):341-356. [2]PAWLAK Z.Rough sets:theoretical aspects of reasoning 图5约简效率对比(a=0.8) about data[M].Boston:Kluwer Academic Publishers,1992 Fig.5 Comparison of reduction efficiency(a=0.8) [3)]王国胤，姚一豫，于洪.粗糙集理论与应用研究综述).计 图1~5中虚线表示PRADM随着对象数量增 算机学报，2009,32(7八：1229-1246. 加运行时间变化曲线，空心圆点实线表示MDRADM WANG Guoyin.YAO Yiyu,YU Hong.A survey on rough 随着对象数量增加运行时间变化曲线，交叉点实线 set theory and applications[J].Chinese journal of computers, 表示DRADM随着对象数量增加运行时间变化曲 2009.32(7):1229-1246 线。实验结果表明，在对象数较少情况下，由于差 [4]QIAN Yuhua,LIANG Jiye,PEDRYCZ W,et al.Positive 别矩阵较简单，PRADM、DRADM和MDRADM运 approximation:an accelerator for attribute reduction in 行时间几乎没有差别，但随着对象数量的增加，3种 rough set theory[J].Artificial intelligence,2010,174(9/10): 算法的运行时间差异越来越明显：由于MDRADM 597-618. 差别元素是DRADM差别元素的一个子集，PRA- [5]WANG Feng,LIANG Jiye,QIAN Yuhua.Attribute reduc- DM的差别矩阵为非对称矩阵，故MDRADM的运 tion:A dimension incremental strategy[J].Knowledge- based systems,2013,39:95-108. 行时间小于PRADM和DRADM运行时间。当a分 [6]CHEN Hongmei,LI Tianrui,RUAN Da,et al.A rough-set 别取0.5、0.6、0.7、0.8时，Mammographic Mass数据 based incremental approach for updating approximations 集随着对象的增加，3个算法的耗时差距增大，这是 under dynamic maintenance environments[J].IEEE transac- 由于随着对象的增加差别矩阵愈加复杂，计算量越 tions on knowledge and data engineering,2013,25(2): 大造成的；当α=0.4时，也呈现这样的趋势，但当对 274-284. 象数达到900时，利用吸收率和结合律运算的差别 [7]HU Qinghua,YU Daren,XIE Zongxia.Information-pre- 矩阵较简单，造成时间增长率减小。当取3.5，α分 serving hybrid data reduction based on fuzzy-rough tech- 别取0.4、0.5、0.6、0.7、0.8时，3个算法的时间耗费 niques[J].Pattern recognition letters,2006,27(5):414-423 情况跟λ取2.4时的折线图大致相同，所以本文不作 [8]SKOWRON A,RAUSZER C.The discernibility matrices 详细描述。 and functions in information systems[M]//SLOWINSKI R Intelligent Decision Support.Dordrecht:Springer,1992,11: 4结束语 331-362 [9]KRYSZKIEWICZ M.Rough set approach to incomplete in- 属性约简是粗糙集理论研究的热点问题之一， formation systems[J].Information sciences,1998,112(1/2/3/4): 在实际应用中具有重要意义，主要作用有：1)提取 39-49 更加泛化的规则；2)针对应用中的海量数据，能够 [10]邓大勇，黄厚宽，李向军.不一致决策系统中约简之间的 压缩数据集规模。分布保持约简能够保持信息系统 比较U.电子学报，2007,35(2)：252-255. 在约简前后置信度不变，而人们往往只关注置信度 DENG Dayong,HUANG Houkuan,LI Xiangjun.Compar- 最大的规则，具有广泛的应用价值。 ison of various types of reductions in inconsistent 本文在相关研究成果的基础上，在不协调区间 systems[J].Acta electronica sinica,2007,35(2):252-255. 值决策系统中提出最大分布约简的概念，构造了基 [11]MIAO Duoqian,ZHAO Yan,YAO Yiyu,et al.Relative re- ducts in consistent and inconsistent decision tables of the 于可辨识矩阵的最大分布约简算法，该算法保持了 Pawlak rough set model[J].Information sciences,2009, 在知识约简前后各个规则的最大置信度不变。实验 17924):4140-4150. 选取8组UCI数据集将本文算法与已有的两种约 [12]ZHOU Jie,MIAO Duogian,PEDRYCZ W,et al.Analysis 简算法的约简结果和效率进行对比。实验结果表 of alternative objective functions for attribute reduction in 明，分布约简包含最大分布约简，并且最大分布约 complete decision tables[J].Soft computing,2011,15(8): 简算法比其他两种算法具有更高的效率。由于本文 1601-1616.60 70 90 80 50 40 30 20 10 0 运行时间/s 100 200 300 400 500 600 700 800 900 对象数量 PRADM DRADM MDRADM 图 5 约简效率对比 (α= 0.8 ) Fig. 5 Comparison of reduction efficiency (α= 0.8 ) α α = 0.4 λ 3.5 α λ 2.4 图 1～5 中虚线表示 PRADM 随着对象数量增 加运行时间变化曲线，空心圆点实线表示 MDRADM 随着对象数量增加运行时间变化曲线，交叉点实线 表示 DRADM 随着对象数量增加运行时间变化曲 线。实验结果表明，在对象数较少情况下，由于差 别矩阵较简单，PRADM、DRADM 和 MDRADM 运 行时间几乎没有差别，但随着对象数量的增加，3 种 算法的运行时间差异越来越明显；由于 MDRADM 差别元素是 DRADM 差别元素的一个子集，PRA￾DM 的差别矩阵为非对称矩阵，故 MDRADM 的运 行时间小于 PRADM 和 DRADM 运行时间。当 分 别取 0.5、0.6、0.7、0.8 时，Mammographic Mass 数据 集随着对象的增加，3 个算法的耗时差距增大，这是 由于随着对象的增加差别矩阵愈加复杂，计算量越 大造成的；当 时，也呈现这样的趋势，但当对 象数达到 900 时，利用吸收率和结合律运算的差别 矩阵较简单，造成时间增长率减小。当 取 ， 分 别取 0.4、0.5、0.6、0.7、0.8 时，3 个算法的时间耗费 情况跟 取 时的折线图大致相同，所以本文不作 详细描述。 4 结束语 属性约简是粗糙集理论研究的热点问题之一， 在实际应用中具有重要意义，主要作用有：1) 提取 更加泛化的规则；2) 针对应用中的海量数据，能够 压缩数据集规模。分布保持约简能够保持信息系统 在约简前后置信度不变，而人们往往只关注置信度 最大的规则，具有广泛的应用价值。 本文在相关研究成果的基础上，在不协调区间 值决策系统中提出最大分布约简的概念，构造了基 于可辨识矩阵的最大分布约简算法，该算法保持了 在知识约简前后各个规则的最大置信度不变。实验 选取 8 组 UCI 数据集将本文算法与已有的两种约 简算法的约简结果和效率进行对比。实验结果表 明，分布约简包含最大分布约简，并且最大分布约 简算法比其他两种算法具有更高的效率。由于本文 提出的算法是在可辨识矩阵基础上的，其时间和空 间复杂度较高，不利于在实际应用中推广，故提出 高效率的约简算法是未来研究方向之一。 参考文献： PAWLAK Z. Rough sets[J]. International journal of com￾puter & information sciences, 1982, 11(5): 341–356. [1] PAWLAK Z. Rough sets: theoretical aspects of reasoning about data[M]. Boston: Kluwer Academic Publishers, 1992. [2] 王国胤, 姚一豫, 于洪. 粗糙集理论与应用研究综述[J]. 计 算机学报, 2009, 32(7): 1229–1246. WANG Guoyin, YAO Yiyu, YU Hong. A survey on rough set theory and applications[J]. Chinese journal of computers, 2009, 32(7): 1229–1246. [3] QIAN Yuhua, LIANG Jiye, PEDRYCZ W, et al. Positive approximation: an accelerator for attribute reduction in rough set theory[J]. Artificial intelligence, 2010, 174(9/10): 597–618. [4] WANG Feng, LIANG Jiye, QIAN Yuhua. Attribute reduc￾tion: A dimension incremental strategy[J]. Knowledge￾based systems, 2013, 39: 95–108. [5] CHEN Hongmei, LI Tianrui, RUAN Da, et al. A rough-set based incremental approach for updating approximations under dynamic maintenance environments[J]. IEEE transac￾tions on knowledge and data engineering, 2013, 25(2): 274–284. [6] HU Qinghua, YU Daren, XIE Zongxia. Information-pre￾serving hybrid data reduction based on fuzzy-rough tech￾niques[J]. Pattern recognition letters, 2006, 27(5): 414–423. [7] SKOWRON A, RAUSZER C. The discernibility matrices and functions in information systems[M]//SŁOWIŃSKI R. Intelligent Decision Support. Dordrecht: Springer, 1992, 11: 331–362. [8] KRYSZKIEWICZ M. Rough set approach to incomplete in￾formation systems[J]. Information sciences, 1998, 112(1/2/3/4): 39–49. [9] 邓大勇, 黄厚宽, 李向军. 不一致决策系统中约简之间的 比较[J]. 电子学报, 2007, 35(2): 252–255. DENG Dayong, HUANG Houkuan, LI Xiangjun. Compar￾ison of various types of reductions in inconsistent systems[J]. Acta electronica sinica, 2007, 35(2): 252–255. [10] MIAO Duoqian, ZHAO Yan, YAO Yiyu, et al. Relative re￾ducts in consistent and inconsistent decision tables of the Pawlak rough set model[J]. Information sciences, 2009, 179(24): 4140–4150. [11] ZHOU Jie, MIAO Duoqian, PEDRYCZ W, et al. Analysis of alternative objective functions for attribute reduction in complete decision tables[J]. Soft computing, 2011, 15(8): 1601–1616. [12] 第 3 期 尹继亮，等：不协调区间值决策系统的最大分布约简 ·477·