Decision tree learning system with switching evaluator

摘要

In this paper, we introduce the notion of the local strategy of constructing decision trees that includes the information theoretic entropy algorithm in ID3 (or C4.5) and any other local algorithms. Simply put, given a smaple, a local algorithm constructs a decisiontree in the top-down manner using an evaluation function. We propose a new local algorithm that is very different from the entropy algorithm. We analyze behaviors of the two algorithms on a simple model. Based on these analyses, we propose a lerning system of decision trees which can change an evaluation function while constructing decision trees, and verify the effect of the system by experiments with real databases. The system not only achieves a high accuracy, but also produces well-balanced decision trees, which have the advantage of fast classification.