An Efficient Attribute Reduction Algorithm Based on Discernibility Object Pair Set
XU ZhangYan1,2, YANG BingRu1, SONG Wei1
1. School of Information Engineering, University of Science and Technology Beijing, Beijng 100083 2. Department of Computer, Guangxi Normal University, Guilin 541004
Abstract：The definition of discernibility object pair set and the corresponding definition of attribute reduction are introduced. It is proved that the definition of attribute reduction is equivalent to the one based on positive region. Since U/C is important for computing the discernibility object pair set, an algorithm for computing U/C is designed, whose time complexity is cut down to O(｜C｜｜U｜). Under this condition, an efficient attribute reduction algorithm is proposed, whose time and space complexity are cut down to O(｜C｜｜U｜)+O(｜C｜(｜U/C｜2)) and O(｜U｜)+O(｜U/C｜2) respectively. Finally, an example is used to illustrate the efficiency of the new algorithm.
[1] Pawlak Z. Rough Sets. International Journal of Computer and Information Sciences, 1982, 11(5): 341-356 [2] 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 [3] Hu X H, Cercone N. Learning in Relational Databases: A Rough Set Approach. Computational Intelligence, 1995, 11(2): 323-338 [4] Ye Dongyi. An Improvement to Jelonek’s Attribute Reduction Algorithm. Acta Electronica Sinica, 2000, 28(12): 81-82 (in Chinese) (叶东毅.Jelonek属性约简算法的一个改进.电子学报, 2000, 28(12): 81-82) [5] 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) [6] 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) [7] Liu Wenjun, Gu Yundong, Feng Yanbin, 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) [8] Zheng Z, Wang G Y, Wu Y. Objects’ Combination Based Simple Computation of Attribute Core // Proc of the 17th IEEE International Symposium on Intelligent Control. Vancouver, Canada, 2002: 514-519 [9] Wang J, Wang J. Reduction Algorithms Based on Discernibility Matrix: the Ordered Attributes Method. Journal of Computer Science and Technology, 2001, 16(6): 489-504 [10] Liu Shaohui, Sheng Qiujian, Shi Zhongzhi. A New Method for Fast Computing Positive Region. Journal of Computer Research and Development, 2003, 40(5): 637-642 (in Chinese) (刘少辉,盛秋戬,史忠植.一种新的快速计算正区域的方法.计算机研究与发展, 2003, 40(5): 637-642) [11] Hu Keyun, Lu Yuchang, Shi Chunyi. Advances in Rough Set Theory and Its Applications. Journal of Tsinghua University: Science and Technology, 2001, 41(1): 64-68 (in Chinese) (胡可云,陆玉昌,石纯一.粗糙集理论及其应用进展. 清华大学学报:自然科学版, 2001, 41(1): 64-68)
2006, Vol. 19 
