Abstract: This paper studies the test-cost sensitive reduction on the positive region of decision theoretic rough sets (DTRS). Based on the traditional positive region-based reduction, this paper takes test cost into account for the purpose of discovering the positive region-based reduction with the minimum total test cost, and adopts the simulated annealing algorithm combined with traditional positive region-based reduction of DTRS algorithm to search for the result of the positive region-based reduction with the minimum test cost. Furthermore, this paper proposes a test-cost sensitive positive region-based reduction algorithm for DTRS (TCSPR), and analyzes the time complexity of the algorithm. The experimental results confirm the effectiveness of TCSPR that can find a positive region reduction with fewer attributes and less test cost in polynomial time, and whose solution is generally the optimum solution or second-best solution of the optimization objective, viz. the positive region-based reduction with the minimum total test cost, and whose classification ability is hardly reduced in part of the data sets.

Key words: decision theoretic rough sets (DTRS), cost sensitive, attribute reduction

摘要： 对测试代价敏感的决策粗糙集（decision theoretic rough sets，DTRS）正域约简问题进行了研究。在传统正域约简的基础上将测试代价考虑进来，希望找到测试代价总和最小的正域约简。采用模拟退火算法结合传统决策粗糙集正域约简算法来搜索测试代价总和最小的正域约简结果。提出了一种测试代价敏感的决策粗糙集正域约简算法TCSPR（test-cost sensitive positive region-based reduction algorithm for DTRS），并分析了该算法的时间复杂度。实验结果验证了TCSPR算法的有效性，该算法能在多项式时间内找到一个属性更少、测试代价更小的正域约简，找到的解一般为优化目标的最优解或次优解，即测试代价总和最小的正域约简,并且该算法在部分数据集上的分类能力几乎不减。

关键词: 决策粗糙集（DTRS）, 代价敏感, 属性约简