WIT Press

A Propositional Satisfiability Approach In Mining Compact Rules


Free (open access)

Paper DOI








401 kb


A A Bakar, M N Sulaiman, M Othman & M H Selamat


This paper proposes a means of generating classification rules in rough classification theory by using a propositional satisfiability (SAT) approach. The proposed method introduces a theoretical formalism that translates the discernibility relations of classes in a decision system into the SAT problem. The SAT representation is then formulated as an Integer Programming (1P) model called SAT_IP to solve the minimal reduct computation problem. First, a set of rules is generated from the reducts and these will then be used to solve the classification problem. The method generates a minimum set of rules, which are shorter in length, and there is also greater accuracy in the classification. 1 Introduction The enormous number of rules generated to facilitate knowledge in data mining often makes the process of solving the decision problem difficult. It is therefore, important to have a simple model that is able to simplify the representation of real world problems and yet at the same time generate quality knowledge essential for good decision-making. In other words, an expert classification model should contain a manageable number of rules that do not use too many attributes. Such a model is able to fit a large number of objects with good predictive capabilities [1] [2]. The main challenge in developing a good compact model is to determine whether the whole knowledge in the Information System (IS) or Decision System (DS) is always necessary to represent the system. This problem arises in many practical applications and is referred to as the knowledge