MinReduct: A new algorithm for computing the shortest reducts

• Published in: Pattern recognition letters 2020-10, Vol.138, p.177-184
• Main Authors: Rodríguez-Diez, Vladímir, Martínez-Trinidad, José Fco, Carrasco-Ochoa, J Ariel, Lazo-Cortés, Manuel S, Olvera-López, J Arturo
• Format: Article
• Language: English
• Subjects: Algorithms; Binary cumulative operations; Evaluation; Rough sets; Shortest reducts; Size reduction
• ISSN: 0167-8655; 1872-7344
• DOI: 10.1016/j.patrec.2020.07.004

•A new algorithm for computing all the shortest reducts of a decision system is introduced.•Some of the most effective pruning properties for computing all reducts are adapted to compute only the shortest reducts.•Our algorithm uses binary cumulative operations and a fast candidate evaluation process unlike other algorithms.•Our proposal is the fastest in decision systems whose simplified binary discernibility matrices have medium or high density. 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.