Attribute Reduction in Time-cost-sensitive Decision Systems through Backtracking
Li Li · Journal of Information and Computational Science · 2014
Research in machine learning, statistics and related fields has produced a wide variety of algorithms for cost-sensitive learning. Some of these algorithms are devoted to minimal test cost reduction for money cost. In this paper, we consider attribute reduction based on time-cost-sensitive decision systems and propose a backtrack algorithm to find an optimal reduct. Time cost consists of testing time cost and waiting cost, where waiting cost can be overlapped with others. We prove that taking tests in non-ascending order of waiting time can minimize the total time cost. We also propose a backtrack algorithm with two pruning techniques to obtain an optimal reduct. Experimental results show that the pruning techniques are effective, and the algorithm is efficient on the Mushroom dataset.