Tools and Techniques for Decision Tree Learning (1996)

Decision tree learning is an important field of machine learning.In this study we examine both formal and practical aspects of decision tree learning.We aim at answering to two important needs: The need for better motivated decision tree learners and an environment facilitating experimentation with inductive learning algorithms.As results we obtain new practical tools and useful techniques for decision tree learning.First, we derive the practical decision tree learner Rank based on the Findmin protocol of Ehrenfeucht and Haussler.The motivation for the changes introduced to the method comes from empirical experience, but we prove the correctness of the modifications in the probably approximately correct learning framework.The algorithm is enhanced by extending it to operate in the multiclass situations, making it capable of working within the incremental setting, and providing noise tolerance into it.Together these modifications entail practicability through a formal development process, which constitutes an important technique for decision tree learner design.The other tool that comes out of this work is TELA, a general testbed for all inductive learners using attribute representation of data, not only for decision tree learners.This system guides and assists its user in taking new algoritms to his disposal, operating them in an easy fashion, designing and executing useful tests with the algorithms, and in interpreting the outcome of the tests.We present the design rationale, current composition, and future development directions of TELA.Moreover, we reflect on the experiences that have been gathered in the initial usage of the system.The tools that come about are evaluated and validated in empirical tests over many real-world application domains.Several successful inductive algorithms are contrasted with the Rank algorithm in experiments that are carried out using TELA.These experiments let us evaluate the success of the new decision tree learner with respect to its established equivalents and validate the utility of the developed testbed.The tests prove successful in both respects: Rank attains the same overall level of prediction accuracy as C4.5, which is generally considered to be one of the best empirical decision tree learners, and TELA eases the execution of the experiments substantially.i First and foremost, I thank my advisor Esko Ukkonen for his continued guidance and support of this project.Without him this dissertation would never have seen the light of day.I am, also, grateful to Esko for the opportunity to do research together with him.Feedback from Pekka Orponen has been most helpful in finalizing this thesis.Heikki Mannila has had an off and on advisory role in my post-graduate studies.Also, Martti Tienari has shown interest to my progress.Kai Koskimies and Jukka Paakki initially introduced me to scientific work and set me to the path that led to this dissertation.I am gravely indebted to all those that I have been fortunate enough to collaborate with during the years.In particular, I owe a great deal to those people that have contributed to the research that is reported in this dissertation.Section 3.4 extends work that was carried out together with Jyrki Kivinen.In addition, Jyrki