Research On Attribute Reduction Algorithm For Decision Tables In Rough Sets

Rough sets proposed by Pawlak was one of the researching fuzzy and uncertain tools of the maths. In all research of the rough sets, attribute reduction algorithm was very importance.In this paper, we were systematic study of attribute reduction algorithm for decision tables in rough sets. Now, there were three problems in attribute reduction algorithm for decision tables: Firstly, looking for all reductions of the decision tables was NP-hard. Secondly, looking for the smallest reduction of the decision tables was NP-hard too. At last, existing reduction algorithm of the decision tables was lower efficiency, and blocked the development of the rough sets.In order to solve these problem, We proposed three algorithms: Firstly, we proposed the breadth first algorithm based on the graph of the lattice's Hasse. The strategy of the algorithm was to use heuristic search. Comparing with the Pawlak's algorithm, the time complexity was lower. Secondly, Attribute significance was redefined, and a smallest algorithm for attribute reduction in decision tables based on discernibility matrix was introduced. It had multinomial time complexity. The time complexity of the algorithm in the worst case was min(O(|C|²|U|⁴),O(|C|²2^2|C|)). At last, we gave efficient algorithm based on discernibility matrix. The time complexity of the algorithm was O(|C||Uj²). |C| was the amount of the condition attributes, |U| was the amount of the object in univase.