Toward an intelligent classification-tree approach to problem-solving

The objective of this thesis is to design a new classification-tree algorithm which will outperform current algorithms with superior decision trees. The problem of generating a classification tree with the minimum path length is shown to be NP-complete. Therefore, there is no computationally efficient algorithm, only heuristic algorithms are available. One prevalent heuristic algorithm ID3 is analyzed. Since this algorithm selects the locally best attributes, adding a new variable may deteriorate the classification performance if this variable is too closely related to previously selected attributes. A new algorithm IDA is designed. In contrast to ID3, IDA considers the global dependency structure of variables and explores more local alternatives. An analysis on the time complexity of both algorithms shows that when the size of the input instance is large, IDA requires only one half of the computing time taken by ID3. Besides the computational efficiency, this new algorithm has a better performance than ID3 over a variety of situations examined in a simulation study. The number of variables, the number of levels, the distance parameter between the population means, the variance-covariance matrix, and the sample size are five important factors determining the performance of a classification-tree algorithm.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Business Administration

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Tu, Pei-Lei

Contributors dc:contributor

• Blair, Charles E.

• Business Administration, General
• Information Science
• Artificial Intelligence

Statement dc:rights

• Copyright 1989 Tu, Pei-Lei

Language dc:language

eng

Identifier

AAI9011059
(UMI)AAI9011059

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/21889