A Hybrid Ant Colony Optimization Algorithm For Cost-sensitive Attribute Reduction

With the rapid development of computer application,the amount of collected data in different fields increases exponentially.Attribute reduction can help people make decisions efficiently through reducing data dimension and preserving the classification capacity of the decision system.Cost-sensitive learning is one of the ten most challenging problems in data mining.The purpose of its related reduct problems is to obtain the minimal test cost,time cost,misclassification cost,etc.Considering the cost-sensitive attribution reduction,many bionic algorithms have been proposed.Bee colony algorithm is fast.However,it often obtains a local optimal solution due to the phenomenon of premature convergence.Ant colony algorithm can obtain better solutions,but is time-consuming.In this paper,we propose a hybrid ant colony optimization general framework(HA),which consists of partial and complete searching strategies.In the partial searching strategy,each pioneer ant selects exactly k attributes,where k is an empirical valve and determined by the size of an initial reduct.Because many operations,such as computing the positive region and deleting reductant attributes,are eliminated,partial searching strategy makes HA efficient.In the complete searching strategy,each harvester ant searches for complete solutions.Pheromone is updated by both types of ants to optimize the route.Basing on the general framework,we design and implement the corresponding specific algorithms for minimal test cost and minimal time cost reduct problems.Experiments are performed using four UCI datasets.Cost in these datasets is generated with three different distributions.Through a large number of experiments on parameter learning and algorithm comparison,we find that:1)parameter configuration is fundamental to efficiency and quality;2)to obtain the similar level of quality measures such as finding optimal factor,our algorithm is faster;3)with similar runtime,our algorithm obtains significantly better finding optimal factor as well as other quality measures.