An algorithm for reduct cardinality minimization

This is devoted to the consideration of a new algorithm for reduct cardinality minimization. This algorithm transforms the initial table to a decision table of a special kind, simplify this table, and use a dynamic programming algorithm to finish the construction of an optimal reduct. Results of computer experiments with decision tables from UCI ML Repository are discussed.

I. Introduction

The problem of construction of a reduct with minimum cardinality for a given decision table is one of the key problems in the rough set theory [6], [7], [8] which is closely related to granular computing [9]. It is well known that this problem is NP-hard. Based on results of Feige for the set cover problem [3], it is possible to show that, under some natural assumptions about the class N P, the approximation ratio of the best approximate polynomial algorithm for reduct optimization is near to the natural logarithm on the number of pairs of rows (objects) with different decisions in the decision table [4]. Therefore, the improvement of exact algorithms for reduct optimization continue to be an important issue.