A set-cover-based approach for the test-cost-sensitive attribute reduction problem

作者：Tan, Anhui^*; Wu, Weizhi; Tao, Yuzhi

来源：Soft Computing, 2017, 21(20): 6159-6173.

DOI：10.1007/s00500-016-2173-3

• Attribute reduction
• Decision table
• Rough set
• Set cover problem
• Test cost

In data mining application, the test-cost-sensitive attribute reduction is an important task which aims to decrease the test cost of data. In operational research, the set cover problem is a typical optimization problem and has a long investigation history compared to the attribute reduction problem. In this paper, we employ the methods of set cover problem to deal with the test-cost-sensitive attribute reduction. First, we equivalently transform the test-cost-sensitive reduction problem into the set cover problem by using a constructive approach. It is shown that computing a reduct of a decision system with minimal test cost is equal to computing an optimal solution of the set cover problem. Then, a set-cover-based heuristic algorithm is introduced to solve the test-cost-sensitive reduction problem. In the end, we conduct several numerical experiments on data sets from UCI machine learning repository. Experimental results indicate that the set-cover-based algorithm has superior performances in most cases, and the algorithm is efficient on data sets with many attributes.

• 出版日期2017-10
• 单位浙江海洋大学