PDF(614 KB)
PDF(614 KB)
PDF(614 KB)
基于冲突域渐减的属性约简算法
Attribute reduction algorithm based on conflict region decreasing
针对因决策表中存在不一致对象造成的约简求解错误,同时为了进一步提高约简算法求解效率, 首先,给出简化决策表的定义,并证明了简化决策表的核属性和属性约简与原始决策表的核属性和属性约简是等价的. 然后,提出冲突域的概念,分析冲突域的性质,以冲突域中冲突对象个数的变化为度量依据, 研究核属性和属性重要性的性质,同时设计相应的核属性和属性重要性求解算法;在此基础上, 设计基于冲突域渐减式属性约简算法,算法的时间和空间复杂度分别为O(|C|2|U/C|)和O(|U|). 最后的实例和实验结果表明该方法是正确的,高效的.
In order to resolve the errors of reduction algorithms for the existence of inconsistent objects in the decision table and enhance the efficiency of reduction algorithm, firstly, the definition of simplied decision table is proposed, and it is proved that the core and attribute reduction acquired from the method are equivalent to the core and attribute reduction of original decision table. Then, the notion and characters of the conflict region are given. The features of the core attribute and attribution importance based on the change of the number of conflict objects are studied, and the corresponding algorithms of computing core attributes and attribute importance are designed respectively. On the basis of above, an attribute reduction algorithm based on conflict region decreasing is designed, which time complexity and space complexity of the algorithm are O(|C|2|U/C|) and O(|U|). Finally, an example and the experimental results show that the algorithm is correct and efficient.
粗糙集 / 正区域 / 冲突域 / 属性约简 / 核属性 {{custom_keyword}} /
rough set / positive region / conflict region / attribute reduction / core attribute {{custom_keyword}} /
[1] Pawlak Z. Rough sets[J]. International Journal of Computer and Information Science, 1982, 11(5): 341-356.
[2] Wong S K M, Ziarko W. On optimal decision rules in decision tables[M]. Computer Science Department, University of Regina, 1985.
[3] Hu X H, Cercone N. Learning in relational databases: A rough set approach[J]. Computational Intelligence, 1995, 11(2): 323-337.
[4] Skowron A, Rauszer C. The discernibility matrices and functions in information systems[C]//Intelligent Decision Support-Handbook of Applications and Advances of the Rough Sets Theory, Dordrecht: Kluwer Academic Publisher, 1992: 331-362.
[5] 叶东毅,陈昭炯.一个新的差别矩阵及其求核方法[J].电子学报, 2002, 30(7): 1086-1088.Ye D Y, Chen Z J. A new discernibility matrix and the computation of a core[J]. Acta Electronica Sinica, 2002, 30(7): 1086-1088.
[6] 张文修,吴伟志,梁吉业,等.粗糙集理论与方法[M].北京:科学出版社, 2001.Zhang W X, Wu W Z, Liang J Y, et al. Theory and method of rough set[M]. Beijing: Science Press, 2001.
[7] 刘文军,谷云东,冯艳宾,等.基于可辨识矩阵和逻辑运算的属性约简算法的改进[J].模式识别与人工智能, 2004, 17(1): 119-123.Liu W J, Gu Y D, Feng Y B, et al. An improved attribute reduction algorithm of decision table[J]. Pattern Recognition and Artificial Intelligence, 2004, 17(1): 119-123.
[8] 徐章艳,杨炳儒,宋威.基于简化差别矩阵的完备属性约简算法[J].计算机工程与应用, 2006(26): 167-169.Xu Z Y, Yang B R, Song W. A complete reduction algorithm based on simple discernibility matrix[J]. Computer Engineering and Applications, 2006(26): 167-169.
[9] 高学东,丁军.基于简化差别矩阵的属性约简算法[J].系统工程理论与实践, 2006, 26(6): 101-107.Gao X D, Ding J. An attribution reduction algorithm based on simple discernibility matrix[J]. Systems Engineering-Theory & Practice, 2006, 26(6): 101-107.
[10] 杨明.一种基于改进差别矩阵的属性约简增量式更新算法[J].计算机学报, 2007, 30(5): 815-822.Yang M. An incremental updating algorithm for attribute reduction based on improved discernibility matrix[J]. Chinese Journal of Computers, 2007, 30(5): 815-822.
[11] 刘少辉,盛秋戬,吴斌,等. Rough 集高效算法的研究[J].计算机学报, 2003, 26(5): 524-529.Liu S H, Sheng Q J, Wu B, et al. Research on efficient algorithms for rough set methods[J]. Chinese Journal of Computers, 2003, 26(5): 524-529.
[12] 徐章艳,刘作鹏,杨炳儒,等.一个复杂度为max(O(|C||U|),O(|C|2|U/C|))的快速属性约简算法[J].计算机学报, 2006, 29(3): 391-399.Xu Z Y, Liu Z P, Yang B R, et al. A quick attribute reduction algorithm with complexity of max(O(|C||U|), O(|C|2|U/C|))[J]. Chinese Journal of Computers, 2006, 29(3): 391-399.
[13] 葛浩,李龙澍,杨传健.改进的快速属性约简算法[J].小型微型计算机系统, 2009, 30(2): 308-312.Ge H, Li L S, Yang C J. Improvement to quick attribution reduction algorithm[J]. Journal of Chinese Computer Systems, 2009, 30(2): 308-312.
[14] 刘勇,熊蓉,褚健. Hash快速属性约简算法[J].计算机学报, 2009, 32(8): 1493-1499.Liu Y, Xiong R, Chu J. Quick attribute reduction algorithm with Hash[J]. Chinese Journal of Computers, 2009, 32(8): 1493-1499.
[15] Wang G Y, Zhao J, An J J, et al. A comparative study of algebra viewpoint and information viewpoint in attribute reduction[J]. Fundamenta Informaticae, 2005, 68(6): 289-301.
[16] 赵军,王国胤,吴中福,等.一种高效的属性核计算方法[J].小型微型计算机系统, 2003, 24(11): 1950-1953.Zhao J, Wang G Y, Wu Z F, et al. An efficient approach to computer feature core[J]. Mini-Micro Systems, 2003, 24(11): 1950-1953.
[17] 葛浩,李龙澍,杨传健.一种核属性快速求解算法[J].控制与决策, 2009, 24(5): 738-742.Ge H, Li L S, Yang C J. Quick algorithm for computing core attribute[J]. Control and Decision, 2009, 24(5): 738-742.
安徽省自然科学基金(1308085QF114);安徽高校省级自然科学研究项目(KJ2012A212,KJ2013A015);安徽省高校省级优秀青年人才基金(2011SQRL123);滁州学院科学研究项目(2011KJ003Z)
/
| 〈 |
|
〉 |
