MinReduct: A new algorithm for computing the shortest reducts

This paper deals with the problem of computing the shortest reducts of a decision system. The shortest reducts are useful for attribute reduction in classification problems and data size reduction. Unfortunately, finding all the shortest reducts is an NP-hard problem. There are some algorithms reported in the literature to overcome the complexity of computing the shortest reducts. However, most of these algorithms relay on costly operations for candidate evaluation. In this paper, we propose a new algorithm for computing all the shortest reducts; based on binary cumulative operations over a pair-wise comparison matrix, and a fast candidate evaluation process. Binary cumulative operations save computation time by avoiding repetitive calculations. Furthermore, unlike other algorithms reported in the literature, our candidate evaluation process relays on low-cost operations which reduce the runtime in most cases. Our experiments over synthetic and real-world decision systems show that our proposal is faster than state of the art algorithms in most decision systems.