Study On Decision-theoretic Rough Set Attribute Reduction Algorithm

Rough sets theoretic proposed by Pawlak who is a polish mathematician is a math tools which is used to handle the fuzzy, uncertain and imprecise problem. The correct classification rules was got by rough sets theoretic without any priori knowledge or overhead information. In the early nineties, a decision-theoretic rough sets model was proposed by Canadian scholar Yao by adding the Bayesian risk decision into rough sets model. And positive domain and negative domain of rough sets was expanded into positive domain, negative domain and boundary domain. Then the decision rules of decision-theoretic rough sets were given in the principle of risk minimization. Attribute reduction which had been proved to be a NP-hard problem is a core problem of rough sets theoretic. The traditional attribute reduction algorithms are just used to solve the problem of low dimensionality and small-scale data. But the decision reduction algorithms based on intelligent optimization algorithms had achieved remarkable results and reduced the time complexity of obtaining the minimum reduction. However, the existing algorithms could not obtain all or more minimum reduction for attribute reduction problem with multiple minimum decisions because of the weak global optimization capability and not always find minimum reduction of a decision table. Therefore, an attribute reduction algorithm of decision-theoretic rough sets is proposed based on backtracking search algorithm in view of its strong global search performance. Finally, this problem aiming to minimum decision risk was studied and a series of achievement were achieved.1. The minimum risk Bayes decision was introduced into the traditional Pawlak algebraic rough set model to construct a decision-theoretic rough sets model which could tolerate noise. Then probability containment relationship was added into the upper and lower approximation set of the model and the method for determining the probability threshold was given according to minimum risk Bayes decision. Thus the researching boundaries and application filed of rough sets theoretic are broadened.2. The decision-theoretic rough sets are based on loss function and the probability threshold value used to differentiate positive domain, negative domain and boundarydomain is obtained in the light of minimum the loss of risk and the decision rules of decision-theoretic rough sets is constructed.3. Attribute reduction problem of decision-theoretic rough sets which was based on minimum the decision risk is defined and a formula which was based on minimum risk Bayes decision to compute the loss of risk is given. Then an attribute reduction problem which was based on minimum decision risk is proposed and is transformed into an optimization problem for solving it. Finally, a new fitness function is given and attribute reduction algorithm of decision-theoretic rough sets based on backtracking search algorithm is proposed.4. The actual numerical example is given to prove the effectiveness of attribute reduction algorithm the above mentioned. By comparing it with the existing algorithms, the algorithm’s global search performance is proved. Then, the UCI data sets is used to take experiment, and the results show that this algorithm not only obtain all or more minimal attribute reduction results but also not have greater volatility because of more runs, that is to say, the algorithm has higher stability.