Premium
A Complexity Model and a Polynomial Algorithm for Decision‐Tree‐Based Feature Construction
Author(s) -
Major Raymond L.
Publication year - 2000
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/0824-7935.00105
Subject(s) - feature (linguistics) , time complexity , computer science , decision tree , tree (set theory) , limit (mathematics) , incremental decision tree , disjunctive normal form , id3 algorithm , decision tree model , artificial intelligence , decision tree learning , algorithm , theoretical computer science , mathematics , machine learning , combinatorics , mathematical analysis , philosophy , linguistics
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.