Binary decision tree synthesis: splitting criteria and the algorithm listbb
Vladimir Donskoy · CyberLeninK (CyberLeninka) · 2013
In our days, interest to the class of inductors on the basis of decision trees does not weaken, especially in the context of Data Mining paradigm . At the same time most widespread Quinlan algorithms ID3 and C4.5, as we show in the paper, are not the best. It is therefore possible to see the successful attempts of creation another heuristic splitting criteria for the algorithms of synthesis of decision trees. Comparative definition of different splitting criteria used for the synthesis of binary decision trees is the purpose of the paper. We included the criteria D, ⌦, Z1 and other which were developed by the author yet at 1979-80 years. These criteria define combined splitting principle which is used in the algorithm LISTBB. Introduction The idea to use decisions trees for machine learning and recognition appeared in the articles of Hunt and Hoveland at the end of 50th past century. But the central work came into notice of mathematicians and programmers to this scientific direction all over the world there was the book of Hunt, Marine, and Stone published in 1966 [8]. In the Soviet union the scientific direction related to the decision trees began to develop approximately at the same time at A. Blokh [25] scientific school. From numerous works of this school it is necessary to pay the special attention to the paper of V. Orlov [39]. In this Orlov’s paper, yet at the beginning of 70th last century ??? more than on 10 years before J. R. Quinlan ??? an entropy splitting criterion and the algorithm for decision tree synthesis was presented, which on principle did not differ from the widely in-use algorithm ID3. In our days, interest to the class of inductors on the basis of decision trees does not weaken, especially in the context of paradigm of Data Mining. At the same time most widespread Quinlan’s algorithms ID3 and C4.5 , as possible to see below, are not the best. It is therefore possible to find out the successful attempts of creation another heuristic algorithms for synthesis decision trees by precedent information [15, 14]. The aim of the present paper is comparative description of the different splitting criteria used for the synthesis of binary decision trees (BDT), including the criteria developed by the author yet in 1979-80 years which underlay the algorithm LISTBB.