Attribute Reduction Algorithm Based on Common Discernibility Degree
TENG Shu-Hua1, ZAN De-Cai2,SUN Ji-Xiang1,TAN Zhi-Guo1
Institution of Electronic Science and Engineering,National University of Defense Technology,Changsha 410073 Department of Computer Network,Hebei Engineering and Technical College,Cangzhou 061001
Abstract：From the point of knowledge classifications ability, the definition of common discernibility degree and the corresponding properties are introduced. By utilizing common discernibility degree to depict the relative importance of attribute in information system, a heuristic reduced algorithm based on information viewpoint is proposed and proved. It can be directly applied to both complete and incomplete information systems to reduce attributes without pretreatment. The approach ensures the relatively high reduction rate and simultaneously makes the worst time complexity in complete information system fall to 公式 Finally, results of numerical experiments are used to illustrate the high efficiency of the algorithm in incomplete and complete information systems.
[1] Pawlak Z. Rough Sets: Theoretical Aspects of Reasoning about Data. London, UK: Kluwer Academic Publisher, 1991 [2] Pawlak Z, Skowron A. Rudiments of Rough Sets. Information Sciences, 2007, 177(1): 3-27 [3] Skowron A, Rauszer C. The Discernibility Matrices and Functions in Information Systems // Slowinski R, ed. Intelligent Decision Support: Handbook of Applications and Advances of the Rough Sets Theory. Dordrecht, Netherlands: Kluwer, 1992: 331-362 [4] Hu Xiaohua, Cercone N. Learning in Relational Databases: A Rough Set Approach. Computational Intelligence, 1995, 11(2): 323-338 [5] Ye Dongyi. An Improvement to Jeloneks Attribute Reduction Algorithm. Acta Electronica Sinica, 2000, 28(12): 81-82 (in Chinese) (叶东毅.Jelonek属性约简算法的一个改进.电子学报, 2000, 28(12): 81-82) [6] Ye Dongyi, Chen Zhaojiong. A New Discernibility Matrix and the Computation of a Core. Acta Electronica Sinica, 2002, 30(7): 1086-1088 (in Chinese) (叶东毅,陈昭炯.一个新的差别矩阵及其求核方法.电子学报, 2002, 30(7): 1086-1088) [7] Wang Guoyin. Calculation Method for Core Attributes of Decision Table. Chinese Journal of Computers, 2003, 26(5): 611-615 (in Chinese) (王国胤.决策表核属性的计算方法.计算机学报, 2003, 26(5): 611-615) [8] Liu Wenjun, GuYundong, FengYanbin, et al. An Improve Attribute Reduction Algorithm of Decision Table. Pattern Recognition and Artificial Intelligence, 2004, 17(1): 119-123 (in Chinese) (刘文军,谷云东,冯艳宾,等.基于可辨识矩阵和逻辑运算的属性约简算法的改进.模式识别与人工智能, 2004, 17(1): 119-123) [9] Yang Ming. An Incremental Updating Algorithm for Attribute Reduction Based on Improved Discernibility Matrix. Chinese Journal of Computers, 2007, 30(5): 815-822 (in Chinese)
(杨 明.一种基于改进差别矩阵的属性约简增量式更新算法.计算机学报, 2007, 30(5): 815-822) [10] Liu Shaohui, Sheng Qiujian, Wu Bin, et al. Research on Efficient Algorithms for Rough Set Methods. Chinese Journal of Computers, 2003, 26(5): 524-529 (in Chinese) (刘少辉,盛秋戬,吴 斌,等.Rough集高效算法的研究.计算机学报, 2003, 26(5): 524-529) [11] Xu Zhangyan, Yang Bingru, Song Wei. An Efficient Attribute Reduction Algorithm Based on Discernibility Object Pair Set. Pattern Recognition and Artificial Intelligence, 2006, 19(5): 572-577 (in Chinese) (徐章艳,杨炳儒,宋 威.基于区分对象对集的高效属性约简算法.模式识别与人工智能, 2006, 19(5): 572-577) [12] Wang Guoyin, Yu Hong, Yang Dachun. Decision Table Reduction Based on Conditional Information Entropy. Chinese Journal of Computers, 2002, 25(7): 759-766 (in Chinese) (王国胤,于 洪,杨大春.基于条件信息熵的决策表约简.计算机学报, 2002, 25(7): 759-766) [13] Miao Duoqian, Hu Guirong. A Heuristic Algorithm for Reduction of Knowledge. Computer Research Development, 1999, 36(6): 681-684 (in Chinese) (苗夺谦,胡桂荣.知识约简的一种启发式算法. 计算机研究与发展, 1999, 36(6): 681-684) [14] Miao Duoqian, Wang Jue. On the Relationships between Information Entropy and Roughness of Knowledge in Rough Set Theory. Pattern Recognition and Artificial Intelligence, 1998, 11(1): 34-40 (in Chinese) (苗夺谦,王 珏.粗糙集理论中知识粗糙性与信息熵关系的讨论.模式识别与人工智能, 1998, 11(1): 34-40) [15] Wang Guoyin. Rough Set Theory and Knowledge Acquisition. Xian, China: Xian Jiaotong University Press, 2001 (in Chinese) (王国胤.粗糙集理论与知识获取.西安:西安交通大学出版社, 2001) [16] Teng Shuhua, Zhou Shilin, Sun Jixiang, et al. Attribute Reduction Algorithm Based on Conditional Entropy under Incomplete Information System. Journal of National University of Defense Technology, 2010, 32(1): 90-94 (in Chinese) (滕书华,周石琳,孙即祥,等.基于条件熵的不完备信息系统属性约简算法.国防科技大学学报, 2010, 32(1): 90-94) [17] Kryszkiewicz M. Rules in Incomplete Information Systems. Information Sciences: An International Journal, 1999, 113(3): 271-292 [18] Kryszkiewicz M. Rough Set Approach to Incomplete Information Systems. Information Sciences: An International Journal, 1998, 112(1/2/3/4): 39-49 [19] Liu Qihe, Li Fan, Min Fan, et al. An Efficient Knowledge Reduction Algorithm Based on New Conditional Information Entropy. Control and Decision, 2005, 20(8): 878-882 (in Chinese) (刘启和,李 凡,闵 帆,等.一种基于新的条件信息熵的高效知识约简算法.控制与决策, 2005, 20(8): 878-882)
2010, Vol. 23 
