Probabilistic induction of decision trees and disjunctive normal forms

The authors develop a theory for general decision tree induction based on both the logical structure of concepts and the probability distribution of examples. The discrete function is the common analytic representation of decision trees and decision tables (rules). One of the most important classes of discrete functions is the disjunctive normal forms (DNF). Disjunctiveness of concepts has a great effect on the accuracy and speed of concept learning. A theory for general decision trees is developed based on Shannon´s expansion of the discrete DNF. The function-equivalence, the structural manipulations, and irreducible DNFs and trees are studied. For optimizing decision trees in the context of induction, the functional and structural criteria are investigated