2012/09/25 by Fan Min, Qinghua Hu, William Zhu
Computer Science · #Data Management and Algorithms #Data Mining Algorithms and Applications #Rough Sets and Fuzzy Logic #cs.AI #cs.LG
paper · pdf · doi:10.1016/j.ijar.2013.04.003
23 pages
arxiv created 2012/09/25 · openalex publication_date 2013/04/17 · arxiv updated 2013/05/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Feature selection is an important preprocessing step in machine learning and data mining. In real-world applications, costs, including money, time and other resources, are required to acquire the features. In some cases, there is a test cost constraint due to limited resources. We shall deliberately select an informative and cheap feature subset for classification. This paper proposes the feature selection with test cost constraint problem for this issue. The new problem has a simple form while described as a constraint satisfaction problem (CSP). Backtracking is a general algorithm for CSP, and it is efficient in solving the new problem on medium-sized data. As the backtracking algorithm is not scalable to large datasets, a heuristic algorithm is also developed. Experimental results show that the heuristic algorithm can find the optimal solution in most cases. We also redefine some existing feature selection problems in rough sets, especially in decision-theoretic rough sets, from the viewpoint of CSP. These new definitions provide insight to some new research directions.