MinReduct: A new algorithm for computing the shortest reducts
| Autor: | J. Arturo Olvera-López, Manuel S. Lazo-Cortés, Vladimir Rodríguez-Diez, J. Ariel Carrasco-Ochoa, José Fco. Martínez-Trinidad |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Computer science
Computation Process (computing) 02 engineering and technology 01 natural sciences Reduction (complexity) Matrix (mathematics) Artificial Intelligence 0103 physical sciences Signal Processing 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Computer Vision and Pattern Recognition State (computer science) Rough set 010306 general physics Algorithm Software |
| Zdroj: | Pattern Recognition Letters. 138:177-184 |
| ISSN: | 0167-8655 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect