Classification rule induction with an ant colony optimization algorithm

Abstract

Ant colony optimization is a meta-heuristic approach inspired from the behavior of natural ants. It has been applied to solve a variety of combinatorial optimization problems because of its advantages with cooperation and adaptation. Applied to classification rule induction, an ant colony optimization system may be able to perform a flexible, robust search for a set of high-quality classification rules.

In this thesis, a new ant colony optimization system called Ant-Rule is proposed to learn a set of unordered classification rules from a training data set. Ant-Rule implements three different heuristic functions and two different fitness functions. The roles played by the heuristic function and the fitness function in rule induction with Ant- Rule are investigated. Experiments show that applying the Laplace estimate error function for both the heuristic function and the fitness function produces the best predictive accuracy for most of the data sets studied in this thesis. The performance of Ant-Rule is also compared to Ant-Miner, the first ant colony optimization algorithm for classification rule induction, and CN2, a well-known rule induction algorithm. Results show that Ant-Rule achieves the same or better performance in classification rule induction than both CN2 and Ant-Miner in the data sets tested in this thesis, which provides evidence that ant colony optimization is a viable approach to the classification rule induction problem.