A new algorithm for computing reducts based on the binary discernibility matrix

作者：Lazo Cortes Manuel S^*; Martinez Trinidad J Fco; Carrasco Ochoa J A; Sanchez Diaz Guillermo

来源：Intelligent Data Analysis, 2016, 20(2): 317-337.

DOI：10.3233/IDA-160807

• Rough sets
• reduct
• binary discernibility matrix
• attribute reduction

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.

• 出版日期2016