A new algorithm for reduct computation based on gap elimination and attribute contribution

Attribute reduction is a key aspect of Rough Set Theory. Finding the complete set of reducts is important for solving problems such as the assessment of attribute relevance, multi-objective cost-sensitive attribute reduction and dynamic reduct computation. The main limitation in the application of Rough Set methods is that finding all reducts of a decision system has exponential complexity regarding the number of attributes. Several algorithms have been reported to reduce the cost of reduct computation. Unfortunately, most of these algorithms relay on high cost operations for candidate evaluation. Therefore, in this paper, we propose a new algorithm for computing all reducts of a decision system, based on the pruning properties of gap elimination and attribute contribution, that uses simpler operations for candidate evaluation in order to reduce the runtime. Finally, the proposed algorithm is evaluated and compared with other state of the art algorithms, over synthetic and real decision systems.