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

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