Propositional Satisfiability Algorithm to Find Minimal Reducts for Data Mining

A fundamental problem in data mining is whether the whole information available is always necessary to represent the information system (IS). Reduct is a rough set approach in data mining that determines the set of important attributes to represent the IS. The search for minimal reduct is based on the assumption that within the dataset in an IS, there are attributes that are more important than the rest. An algorithm in finding minimal reducts based on Propositional Satisfiability (SAT) algorithm is proposed. A branch and bound algorithm is presented to solve the proposed SAT problem. The experimental result shows that the proposed algorithm has significantly reduced the number of rules generated from the obtained reducts with high percentage of classification accuracy.

Keywords:

• Rough Set
• Reduct
• Binary Integer Programming (BIP)
• Conjunctive Normal Forms (CNF)
• Propositional Satisfiability (SAT)
• Data Mining