A new algorithm for computing reducts based on the binary discernibility matrix
Autor: | Manuel S. Lazo-Cortés, Guillermo Sanchez Diaz, J. Fco. Martínez-Trinidad, Jesús Ariel Carrasco-Ochoa |
---|---|
Rok vydání: | 2016 |
Předmět: |
Reduct
Binary number 020206 networking & telecommunications Context (language use) 02 engineering and technology Theoretical Computer Science Reduction (complexity) Matrix (mathematics) Artificial Intelligence 0202 electrical engineering electronic engineering information engineering Table (database) 020201 artificial intelligence & image processing Computer Vision and Pattern Recognition Pruning (decision trees) Rough set Algorithm Mathematics |
Zdroj: | Intelligent Data Analysis. 20:317-337 |
ISSN: | 1571-4128 1088-467X |
Popis: | 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. |
Databáze: | OpenAIRE |
Externí odkaz: |