Feature Selection with Test Cost Constraint through a Simulated Annealing Algorithm

Junxia Niu ； Hong Zhao ； William Zhu

《網際網路技術學刊》 17卷6期 (2016/11) Pp. 1133-1140

https://doi.org/10.6138/JIT.2016.17.6.20141119

摘要

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.

關鍵字

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