Scalable Decision Tree Construction

Cornell University, Ithaca NY

Investigators

Abstract

Data mining is one of the very promising information technologies today. This project studies decision trees, one of the most widely used data mining models. The approach addresses three complementary components of decision tree construction: Bias in split selection, pruning, and regression tree construction. Bias in split selection is a very important problem, as the choice of the "wrong" split attribute destroys the interpretability of the decision tree, and users can no longer trust the information from the tree. Through a large experimental study and a theoretical investigation, this project develops a framework to devise split selection methods with absolutely zero bias. The new methods will permit users of decision trees to interpret the tree without any doubt of misinformation. The second topic addresses pruning of decision trees. Through a large experimental study of pruning of decision trees for large datasets, the project investigates the computational and qualitative trade-offs between different pruning methods, solving an ongoing debate about how to prune with large datasets. Third, this research investigates scalable regression tree construction, developing methods to construct regression trees with linear models in the leaf nodes of the tree and multivariate splits at intermediate nodes - all completely scalable over very large datasets with millions of records. The results are implemented in a publicly available decision tree construction tool and performance testbed and software contribution to the research community. This research has many applications in electronic commerce, scientific data analysis, and computational biology.