Title | ||
---|---|---|
An efficient algorithm for finding optimal gain-ratio multiple-split tests on hierarchical attributes in decision tree learning |
Abstract | ||
---|---|---|
Given a set of training examples S and a tree-structured attribute x, the goal in this work is to find a multiple-split test defined on x that maximizes Quinlan's gain-ratio measure. The number of possible such multiple-split tests grows exponentially in the size of the hierarchy associated with the attribute. It is, therefore, impractical to enumerate and evaluate all these tests in order to choose the best one. We introduce an efficient algorithm for solving this problem that guarantees maximizing the gain-ratio over all possible tests. For a training set of m examples and an attribute hierarchy of height d, our algorithm runs in time proportional to dm, which makes it efficient enough for practical use. |
Year | Venue | Keywords |
---|---|---|
1996 | AAAI/IAAI, Vol. 1 | training example,multiple-split test,practical use,optimal gain-ratio multiple-split test,decision tree learning,gain-ratio measure,possible test,tree-structured attribute,efficient algorithm,m example,efficient enough,attribute hierarchy,hierarchical attribute |
Field | DocType | ISBN |
Decision tree,Computer science,C4.5 algorithm,Artificial intelligence,Hierarchy,ID3 algorithm,Training set,Mathematical optimization,Algorithm,Information gain ratio,Decision tree learning,Machine learning,Incremental decision tree | Conference | 0-262-51091-X |
Citations | PageRank | References |
7 | 3.95 | 8 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hussein Almuallim | 1 | 547 | 138.58 |
Yasuhiro Akiba | 2 | 143 | 24.43 |
Shigeo Kaneda | 3 | 69 | 26.85 |