Cross Split Decision Trees for pattern classification

One of the most important problems of decision trees is instability. It means that small changes in the dataset can result in different trees and different predictions. In this paper we introduce Cross Split Decision Tree (CSDT) which is a new decision tree learning algorithm with improved stability. This new algorithm uses multiple attributes as the split test in the internal nodes, in spite of the classical decision tree learning algorithms which use a single attribute. We have employed a heuristic based on the hoeffding bound to select the best attributes in the internal nodes. The experimental results show that in comparison with the well-known C4.5 decision tree learning algorithm, the proposed algorithm creates shallower decision trees with comparable accuracy.