Abstract: Attribute reduction is an important problem in rough set theory. According to a decision-theoretic rough set model, the minimal attribute reductions problem is transformed to a minimal risk of decision making problem and a new computing method of fitness function is given to get more and more stable minimal attribute reduction result. On this basis, a decision-theoretic rough set attribute reduction algorithm based on backtracking search algorithm is proposed by using the global search capability of backtracking search algorithm. The experimental result of UCI data sets and Comparison of results with other algorithms show that more minimal attribute reduction results are got by using this algorithm and the stability in quantity of the reduction results could be kept during multiple runs.

Key words: attribute reduction, Backtracking Search Algorithm（BSA）, Decision-theoretic Rough Set（DTRS）, fitness function

摘要： 属性约简是粗糙集理论的核心问题，为了获得更多更稳定的最小属性约简，根据决策粗糙集模型将最小属性约简问题转化为决策风险最小化问题，并给出了新的适应度函数计算方法；在此基础上利用回溯搜索算法较强的全局搜索性能，提出了基于回溯搜索算法的决策粗糙集属性约简算法；对UCI数据集的实验结果以及与其他约简算法的比较表明，该算法能够得到更多的最小属性约简，而且能够在多次运行中保持约简结果个数的稳定性。

关键词: 属性约简, 回溯搜索算法, 决策粗糙集, 适应度函数