Multiple decision tree induction using multi-objective particle swarm optimization - Santos, Roselyn Dela Paz (2006)
Decision tree induction is the process of learning useful knowledge hidden in data that is used in predicting outcomes of future (unknown) instances. The objectives in inducing decision trees are to generate trees that provide accurate predictions of future instances and that are simple enough for humans to follow. These goals in accuracy and simplicity are conflicting and could be satisfied by multiobjective optimization. In this thesis, we present an approach in inducing decision trees using multiobjective evolutionary algorithm that applies the concept of Pareto dominance in satisfying the decision tree's objectives of accuracy and complexity. This approach provides the user with options to choose from more than one optimal decision tree. We use a recently formulated evolutionary algorithm called Multi-Objective Particle Swarm Optimization using Crowding Distance (MOPSO-CD) in inducing multiple decision trees that are Pareto optimal on multiple objectives, the tree's accuracy and complexity. In this evolutionary algorithm, the population is composed of decision trees that are possible solutions to the classification learning problem. After evolution, the algorithm produces a set of decision trees that are Pareto optimal on two important and well-chosen objectives, the classification error and complexity based on the Minimum Description Length (MDL). This has been evaluated on several commonly used benchmark datasets, and the results show that MOPSO-CD is indeed a potential algorithm in inducing multiple decision trees that are accurate and/or simple.