A Complexity Model and a Polynomial Algorithm for Decision‐Tree‐Based Feature Construction
Raymond L. Major · Computational Intelligence · 2000
Using decision trees as a concept description language, we examine the time complexity for learning Boolean functions with polynomial‐sized disjunctive normal form expressions when feature construction is performed on an initial decision tree containing only primitive attributes. A shortcoming of several 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 concise trees within a standard amount of time. We introduce a practical algorithm that forms a finite number of features using a decision tree in a polynomial amount of time. We show empirically that our procedure forms many features that subsequently appear in a tree and the new features aid in producing simpler trees when concepts are being learned from certain problem domains. 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.