Research And Application Of Improving Decision Trees Based On Ant Colony Optimization

Decision tree algorithm is one of the typical algorithms in machine learning field, which has many advantages, such as the high classification speed, the high precision, the simple building process and the simple rules. It has been applied to data mining, risk assessment and some other fields. But there are also some drawbacks with the decision tree algorithm. It is sensitive to noise and inclined to choose the property with more values in the attribute selection process.Ant colony algorithm is a kind of bionic algorithms, which is famous for simulating foraging behavior of real ants. Its features include distributed computing, pheromone feedback and heuristic search. Some optimization algorithms with high performance can be got when ant colony algorithm is combined with other algorithms.A lot of researchers have tried to use the ant colony algorithm to optimize decision tree algorithm, and they have got some improving decision tree algorithms with high performance, for example, classification and regression tree algorithm. It has very high prediction accuracy, but there are also some shortcomings:first, it is only applied to continuous attributes; second, it does not take full advantage of the heuristic information feature in ant colony algorithm.This paper proposes a new decision tree algorithm based on ant colony optimization. In the proposed algorithm, the ant colony algorithm is applied to build the decision tree. It makes full use of the pheromone feedback and heuristic search features. Consequently, the size of the decision tree is reduced and the prediction accuracy is improved. In the process of selecting the attribute branch, the improved algorithm uses the pheromone feedback and information gain ratio to instead the Gini index in CART in order to improve the prediction accuracy of the attribute branch. In the process of searching the optimal solution, the improved algorithm adopts the pheromone updating method in max min ant algorithm, which enhances the ability of searching the optimal solution and improves the prediction accuracy of the decision tree.Two experiments are designed in order to verify the performance of the improved algorithm. The first experiment is that the improved algorithm is compared against C4.5and CART in15classic UCI data sets. The second experiment is that a new intrusion detection system based on the improved algorithm is designed and implemented to be compared against the intrusion detection system based on C4.5. The second experiment uses the KDD CUP99dataset. The experimental results show that the improved decision tree algorithm based on ant colony optimization can effectively improve the prediction accuracy, reduce the size of the decision tree and enhance the intelligibility.