Reducing decision tree fragmentation through attribute value grouping: A comparative study

Article type: Research Article

Authors: Ho, K.M. | Scott, P.D.

Affiliations: Department of Computer Science, University of Essex, Colchester, CO4 3SQ, UK. E-mail: hokokx@essex.ac.uk, scotp@essex.ac.uk

Abstract: The trees constructed by decision tree induction programs are often unnecessarily large and containing substantial degrees of duplication because such programs typically build a separate subtree for each value of a categorical attribute. Attribute value grouping procedures attempt to avoid this problem by partitioning attribute values into groups, each of which gives rise to only one subtree. In this paper we raise and attempt to answer a number of questions about the performance of such procedures. We review the limited amount of research that has been done in this area and propose a number of novel attribute value grouping procedures. We then present the results of a systematic comparative study in which eight alternative attribute grouping procedures were evaluated using both artificial and real data sets. We found that attribute value grouping can produce substantial reductions in tree size and that the best methods produce average reductions approaching 50% found that there was no effect on the classification accuracy of the trees produced but the time required to produce them was reduced. The most surprising finding was that global methods, which group attribute values once prior to tree construction were superior to local methods, which repartition values throughout tree construction: they produce substantially smaller trees in less time that are marginally more accurate classifiers.

Keywords: attribute value grouping, decision tree induction

DOI: 10.3233/IDA-2000-43-407

Journal: Intelligent Data Analysis, vol. 4, no. 3-4, pp. 255-274, 2000