Heterarchy in Constructing Decision Trees – Parallel ACDT

In this paper, a novel decision tree construction algorithm that utilizes the Ant Colony Optimization (ACO) is presented. The ACO is a population based metaheuristic inspired by the foraging behavior of real ants. It consists in searching for optimal solutions by considering both local heuristic and accumulated (in the form of pheromone trails) knowledge.

In this paper we study a parallel version of the Ant Colony Decision Trees (ACDT) algorithm developed for constructing decision trees. Decision tree induction is a widely used technique to generate classifiers from training data through a process of recursively splitting the data attribute space. The main idea of this paper is to speed up the tree construction process by dividing the population of ants into subpopulations for which calculations are carried out in parallel. The exchange of information between ants is possible through direct and indirect communication channels on the local and global (inter-subpopulation) levels. Ants cooperating in this way form a structure called heterarchy.

A detailed study of the proposed algorithm, focusing both on the computation time and the quality of results, is carried out using data sets from the UCI Machine Learning repository. Proposed scheme of parallelization of the ACDT demonstrates the possibility to improve not only the computation time, but also the quality of results.