The Research And Improvement Of Decision Tree Induction Based On Lookahead

Decision tree learning is one of the most widely used practical methods for inductive inference. The existing majority of the decision tree inductions are based on a top-down greedy algorithm, which make a locally optimal decision at each node. However, in most cases, the tree constructed by greedy algorithm is not optimal globally. Lookahead search is a well-known technique for improving greedy algorithms. Most people believe that the decision tree produced by lookahead search is better than greedy algorithms, and the deeper search, the better result. But, the result obtained by lookahead search is not the case in practice. Many literatures pointed out that lookahead would be harmful in decision tree learning through experiments.The decision tree algorithm based on lookahead is studied in this thesis and compared with the process of constructing tree by greedy algorithm. Compared with the classical ID3 algorithm through an example, the former can reduce the decision tree at the same time of making sure of improving classification accuracy in some certain problem. The shortcomings of decision tree algorithm based on lookahead are analyzed in this paper. Due to these defects in algorithm itself, the decision tree produced have no improvement essentially. To overcome this problem, an efficient way of incorporating rough sets reduction is presented in this paper—the constrained lookahead method. The improved algorithm restricts the search space. Instead of searching for the optimal split attribute within the whole attribute set, attribute reduction method is used to choose a subset of attributes, and then we find the optimal split attribute among the pre-selected attribute sets to construct the tree through a k-step lookahead. Experimental results show that the proposed method decreases the model size, and improves the test accuracy.