Abstract Existing heuristic attribute reduction algorithms generally fail to get a minimum entropy-based attribute reduction of a decision table. Some stochastic optimization algorithms are discussed to solve the problem of entropy-based attribute reduction. Firstly, a proper fitness function is defined to transform the minimum attribute reduction problem into a fitness optimization problem without additional constraints and the equivalence of transformation is proved. Then, the solving efficiency and the solution quality of some stochastic optimization algorithms are studied such as Genetic Algorithm, Particle Swarm Optimization, Tabu search and Ant Colony Optimization. Some UCI datasets are applied to test those performances. The experimental results show that the fully informed PSO based attribute reduction algorithm with refine scheme has a higher probability to find a minimum entropy-based attribute reduction and good performance.
MA Sheng-Lan,YE Dong-Yi. Research on Computing Minimum Entropy Based Attribute Reduction via Stochastic Optimization Algorithms[J]. , 2012, 25(1): 96-104.
[1] Swiniarski R W,Skowron A. Rough Set Methods in Feature Selection and Recognition.Pattern Recognition Letters,2003,24(6): 833-849 [2] Chouchoulas A,Shen Q.Rough Set-Aided Keyword Reduction for Text Categorization.Applied Artificial Intelligence,2001,15(9): 843-873 [3] Skowron A,Rauszer C.The Discernibility Matrices and Functions in Information Systems // Huang Shiyu,ed.Intelligent Decision Support: Handbook of Application and Advances of the Rough Sets Theory.New York,USA: Springer,1992: 331-362 [4] Hu Xiaohua.Knowledge Discovery in Databases: An Attribute-Oriented Rough Set Approach.Ph.D Dissertation.Saskatchewan,Canada: University of Regina,1995 [5] Wong S K M,Ziarko W.On Optimal Decision Rules in Decision Tables.Bulletin of the Polish Academy of Sciences,1985,33(11/12): 693-696 [6] Wroblewski J.Finding Minimal Reducts Using Genetic Algorithms // Proc of the 2nd Annual Join Conference on Information Sciences.Warsaw,Poland,1995: 186-189. [7] Jensen R,Shen Qiang.Finding Rough Set Reducts with Ant Colony Optimization // Proc of the UK Workshop on Computational Intelligence.Bristol,UK,2003: 15-22 [8] Hedar A R,Wang Jue,Fukushima M.Tabu Search for Attribute Reduction in Rough Set Theory.Soft Computing: A Fusion of Foundations,Methodologies and Applications,2008,12(9): 909–918 [9] Ye Dongyi,Liao JianKun.Minimum Attribute Reduction Algorithm Based on Binary Particle Swarm Optimization.Pattern Recognition and Artificial Intelligence,2007,20(3): 295-300 (in Chinese) (叶东毅,廖建坤.基于二进制粒子群优化的最小属性约简算法.模式识别与人工智能,2007,20(3): 295-300) [10] Ye Dongyi,Chen Zhaojiong,Liao Jiankun.A New Algorithm for Minimum Attribute Reduction Based on Binary Particle Swarm Optimization with Vaccination // Proc of the 11th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining.Nanjing,China,2007: 1029-1036 [11] 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) [12] Wang Guoyin.Rough Set Theory and Knowledge Acquisition.Xian,China: Xian Jiaotong University Press,2001 (in Chinese) (王国胤.Rough集理论与知识获取.西安:西安交通大学出版社,2001) [13] Zhang Wenxiu,Liang Yi,Wu Weizhi.Information System and Knowledge Discovery.Beijing,China: Science Press,2003 (in Chinese) (张文修,梁 怡,吴伟志.信息系统与知识发现.北京:科学出版社,2003) [14] Liang Yanchun.Swarm Intelligence Optimization Algorithms Theory and Applications.Beijing,China: Science Press,2009 (in Chinese) (梁艳春.群智能优化算法理论与应用.北京:科学出版社,2009) [15] Spall J C.Introduction to Stochastic Search and Optimization.London,UK: John Wiley Sons,2003. [16] Kennedy J,Eberhart R C.Particle Swarm Optimization // Proc of the IEEE International Conference on Neural Networks.Perth,Australia,1995: 1942-1948 [17] Kennedy J,Eberhart R C.A Discrete Binary Version of the Particle Swarm Algorithm // Proc of the IEEE International Conference on Systems,Man and Cybernetics.Piscataway,USA,1997: 4104-4109 [18] Holland J H.Adaptation in Natural and Artificial Systems.London,UK: MIT Press,1992 [19] Glover F.Tabu Search-Part I.ORSA Journal on Computing,1989,1(3): 190-206 [20] Dorigo M,Maniezzo V,Colorni A.The Ant System: Optimization by a Colony of Cooperating Agents.IEEE Trans on Systems,Man and Cybernetics,1996,26(1): 29-41 [21] Mendes R,Kennedy J,Neves J.The Fully Informed Particle Swarm: Simpler,Maybe Better.IEEE Trans on Evolutionary Computation,2005,1(1): 204-210 [22] Deng Tingquan,Yang Chengdong.An Improved Ant Colony Optimization Applied to Attributes Reduction.Advances in Soft Computing,2009,54: 1-6 [23] Montgomery D C,Runger G C.Applied Statistics and Probability for Engineers.3rd Edition.London,UK: John Wiley Sons,2003: 278-326
2012, Vol. 25 
