A complexity model and a polynomial algorithm for decision-tree-based feature construction

Using decision trees as a concept description language, we examine the time complexity for learning Boolean functions with polynomial-sized disjunctiv e normal form expressions when feature construction is performed on an init ial decision tree containing only primitive attributes. A shortcoming of se veral feature-construction algorithms found in the literature is that it is difficult to develop time complexity results for them. We illustrate a way to determine a limit on the number of features to use for building more co ncise trees within a standard amount of time. We introduce a practical algo rithm thar forms a finite number of features using a decision tree in a pol ynomial amount of time. We show empirically that our procedure forms many f eatures that subsequently appear in a tree and the new features aid in prod ucing simpler trees when concepts are being learned from certain problem do mains. Expert systems developers can use a method such as this to create a knowledge base of information that contains specific knowledge in the form of If-Then rules.