Induction of decision trees by looking to data sequentially and using error correction rule

摘要

Decision trees are common algorithms in machine learning. Traditionally, these algorithms make trees recursively and at each step, they inspect data to induce the part of the tree. However decision trees are famous for their instability and high variance in error. In this paper a solution which adds error correction rule to a traditional decision tree algorithm is examined. In fact an algorithm which we call it, ECD3 is introduced. Algorithm of ECD3 inspects data sequentially in an iterative manner and updates tree only when it finds an erroneous observation. This method was first proposed by Dr. Utgoff but not implemented. In this paper, the method is developed and several experiments are performed to evaluate the method. We found that in most cases, performance of ECD3 is comparable to its predecessors. However ECD3 has some benefits over them. First, sizes of its trees are significantly smaller. Second, on average, variance of error in ECD3 is lower. Furthermore, ECD3 automatically chooses part of data for induction of the tree and sets aside others. This capability can be exploited for prototype selection in various learning algorithms. To explain these observations, we use inductive bias and margin definitions in our theories. We introduce a new definition of margin in ordinary decision trees based on shape, size and splitting criteria in trees. We show that how ECD3 expands the margins and enhances precision over test data.