Learning DNF concepts by constrained clustering of positive instances

In this paper, we define the conjunctive learnability of nominal-attribute instances space, and set up a propositional concept learning paradigm by clustering positive instances into multiple divisions. All divisions are conjunctive learnable against the total negative instances set. Similarity measuring is introduced to guide the clustering process, and a procedure to generate CNF rules for clusters is described. A post pruning procedure is designed to deal with the overfitting problem, and two criteria as minimum covering rate and minimum error rate are defined. Experiments are implemented on several data sets, and the performance of the proposed method is analyzed and compared with existing algorithms.