Feature Selection with Test Cost Constraint through a Simulated Annealing Algorithm

10.6138/JIT.2016.17.6.20141119

Junxia Niu；Hong Zhao；William Zhu

Cost-sensitive learning ； Constraint satisfaction problem ； Feature selection ； Granular computing ； Test cost

網際網路技術學刊

17卷6期（2016 / 11 / 01）

1133 - 1140

英文

Cost-sensitive feature selection is one of the most fundamental problems in data mining applications. In real-world situations, we need to pay test cost for acquiring feature values of objects. Due to limited money or time, we also have a constraint on the total test cost. This issue has been formalized as the feature selection with test cost constraint problem, which is treated as a constraint satisfaction problem. An information gain based heuristic algorithm and a genetic algorithm have been adopted to deal with the problem. However, the two algorithms do not produce the optimal solution in most cases. In this paper, on the one hand, we built a constraint satisfaction problem model for the feature selection with test cost constraint problem. On the other hand, a simulated annealing algorithm is designed to solve the feature selection with test cost constraint problem. The proposed algorithm which takes advantage of both the test cost information and the search potential of the simulated annealing algorithm. It also adjusts atoms according to the constraint to ensure the convergence of the algorithm. These algorithms are compared based on performance and results by eight UCI datasets and two representative test cost distributions. The experimental results show that the proposed algorithm is more effective and efficient than the previous algorithms.