Affiliations: [a] Instituto Nacional de Astrofísica, Óptica y Electrónica, Puebla, México | [b] Universidad Autónoma de San Luis Potosí, San Luis Potosí, México
Correspondence:
[*]
Corresponding author: Manuel S. Lazo-Cortés, INAOE. Luis E. Erro No. 1 Sta. Ma. Tonantzintla PUE C.P. 72840, Mexico. E-mail:mlazo@inaoep.mx
Abstract: Attribute reduction is a very important task in Rough Set Theory. In this context, in recent years several attribute reduction algorithms based on the discernibility matrix have been proposed. In this paper, we go back to the binary discernibility matrix and reformulate some basic concepts that allow us to build on them an algorithm for computing reducts. The proposed algorithm takes advantage of the binary representation used for the discernibility matrix and depending on the fulfillment of certain pruning properties several candidates can be jumped (pruned). In this way, the number of candidates to be tested is reduced. Additionally, from the binary discernibility matrix, we define a more compact and ordered matrix, which allows reducing even more the amount of candidates to be evaluated, and the cost of verifying each one of them. The proposed algorithm is able to compute all the reducts of an information table, but it can also be used to find a reduct, or a certain number of them. Experiments over standard datasets show that our algorithm has a good performance.
