Approach to Solving Attribute Reductions with Ant Colony Optimization
YU Hong1, YANG Da-Chun2
1.Institute of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065 2.Chongqing Research and Development Institute, Zhongxing Telecom Equipment Corporation, Chongqing 400060
Abstract：Attribute reduction is an important process in rough set theory. Minimal attribute reductions are expected to help clients make better decisions in some cases. In this paper, a heuristic approach for solving the minimal attribute reduction problem (MARP) is proposed based on the ant colony optimization (ACO) metaheuristic. Firstly, the MARP is transformed into an assignment which minimizes the cost in a constraint satisfaction model. Then, a preprocessing step is introduced that removes the redundant data in a discernibility matrix through the absorption operator to favor a smaller exploration of the search space at a lower cost. Next, an algorithm, R-ACO, is developed to solve the MARP. Finally, the simulation results show that the proposed approach finds more minimal attribute reductions efficiently in most cases.
[1] Pawlak Z. Rough Sets. International Journal of Computer and Information Sciences, 1982, 11: 341-356 [2] Wong S K M, Ziarko W. On Optimal Decision Rules in Decision Tables. Bulletin of Polish Academy of Sciences, 1985, 33: 693-696 [3] Wang Guoyin, Wu Yu, Fisher P S. Rule Generation Based on Rough Set Theory // Proc of the SPIE Conference on Data Mining and Knowledge Discovery: Theory, Tools, and Technology. Orlando, USA, 2000, II: 181-189 [4] 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) [5] Wang Jue, Wang Ju. Reduction Algorithms Based on Discernibility Matrix: The Ordered Attributes Method. Journal of Computer Science and Technology, 2001, 16(6): 489- 504 [6] Wu Weizhi, Zhang Mei, Li Huanzu, et al. Knowledge Reduction in Random Information Systems via Dempster-Shafer Theory of Evidence. Information Sciences: An International Journal, 2005, 174(3/4): 143-164 [7] Yao Yiyu, Zhao Yan. Discernibility Matrix Simplification for Constructing Attribute Reducts. Information Science: An International Journal, 2009, 179(7): 867-882 [8] Deng Tingquan, Yang Chengdong, Zhang Y T, et al. An Improved Ant Colony Optimization Applied to Attributes Reduction // Cao Bingyuan, Zhang Chengyi, Li Taifu, eds. Fuzzy Information and Engineering, Berlin, Germany: Springer, 2009: 1-6 [9] Jensen R, Shen Q. Finding Rough Set Reducts with Ant Colony Optimization // Proc of the UK Workshop on Computational Intelligence. Bristol, UK, 2003: 15-22 [10] Jiang Yuanchun, Liu Yezheng. An Attribute Reduction Method Based on Ant Colony Optimization // Proc of the 6th World Congress on Intelligent Control and Automation. Dalian, China, 2006: 3542-3546 [11] Ke Liangjun, Feng Zuren, Ren Zhigang. An Efficient Ant Colony Optimization Approach to Attribute Reduction in Rough Set Theory. Pattern Recognition Letters, 2008, 29(9): 1351-1357 [12] Zeng Huanglin, Huang Yan, Zeng Xiaohui. A New Approach of Attribute Reduction Based on Ant Colony Optimization // Proc of the 5th International Conference on Natural Computation. Tianjuan, China, 2009, Ⅲ: 3-7 [13] Wang Xiangyang, Yang Jie, Teng Xiaolong, et al. Feature Selection Based on Rough Sets and Particle Swarm Optimization. Pattern Recognition Letters, 2007, 28(4): 459-471 [14] Dorigo M, Sttzle T. Ant Colony Optimization. Cambridge, USA: MIT Press, 2004 [15] Solnon C. Ants Can Solve Constraint Satisfaction Problems. IEEE Trans on Evolutionary Computation, 2002, 6(4): 347-357 [16] Skowron A, Rauszer C. The Discernibility Matrices and Functions in Information Systems. Fundamenta Informaticae, 1991, 15(2): 331-362 [17] Tsang E PK. Foundations of Constraint Satisfaction. London, UK: Academic Press, 1993 [18] Liang Lin, Xu Guanghua. Reduction of Rough Set Attribute Based on Immune Clone Selection. Journal of Xian Jiaotong University, 2005, 39(11): 1231-1235 (in Chinese) (梁 霖,徐光华.基于克隆选择的粗糙集属性约简方法.西安交通大学学报, 2005, 39(11): 1231-1235) [19] UC Irvine Machine Learning Repository [DB/OL]. [2008-01]. http://archive.ics.uci.edu/ml/
2011, Vol. 24 
