An incremental learning algorithm for constructing Boolean functions from positive and negative examples
This paper introduces an incremental algorithm for learning a Boolean function from examples. The functions are constructed in the disjunctive normal form (DNF) or the conjunctive normal form (CNF) and emphasis is placed in inferring functions with as few clauses as possible. This incremental algorithm can be combined with any existing algorithm that infers a Boolean function from examples. In this paper it is combined with the one clause at a time (OCAT) approach (Comput. Oper. Res. 21(2) (1994) 185) and (J. Global Optim. 5(1) (1994) 64) which is a non-incremental learning approach. An extensive computational study was undertaken to assess the performance characteristics of the new approach. As examples, we used binary vectors that represent text documents from different categories from the TIPSTER collection. The computational results indicate that the new algorithm is considerably more efficient and it derives more accurate Boolean functions. As it was anticipated, the Boolean functions (in DNF or CNF form) derived by the new algorithm are comprised by more clauses than the functions derived by the non-incremental approach. Scope and purpose There is a growing need for methods that can analyze information and infer patterns in a way that can be useful to the analyst. This is the core of data mining and knowledge discovery from databases. Such methods often infer a Boolean function from observations that belong to different classes. This paper presents a methodology that infers a Boolean function in an incremental setting. The proposed approach can be used in conjunction with existing algorithms that infer a Boolean function from examples. The paper presents both algorithmic developments and also an extensive empirical study. The results presented in the paper suggest that the proposed incremental approach is highly promising.
boolean functions data mining incremental and non-incremental learning learning from examples dnf and cnf form machine learning the one clause at a time (ocat) approach for inferring a boolean function