Ant colony optimization to minimal test cost reduction

Minimal test cost attribute reduction is an important issue in cost-sensitive learning. Recently, an information gain based heuristic algorithm has been designed to this problem. However, the algorithm does not often find the optimal solution. In this paper, we develop an ant colony optimization algorithm to deal with this problem. First, the attribute set is represented as a graph with each vertex corresponding to an attribute and each edge concerning pheromone. Second, a population of artificial ants are generated. Third, each ant takes the set of core attributes, and travels a number of vertexes according to test costs of vertexes and pheromone of edges, until the positive region condition is met. Finally, a number of reducts are constructed from the last part of the ant colony and the one with least test cost is selected. The algorithm is tested with three representative test cost distributions on four UCI datasets. The experimental results indicate that our algorithm is significantly better than the existing one, especially on the mushroom dataset.