Study On Efficiency Of Knowledge Reduction Based On Rough Set Theory

Rough set theory ,which is another math theory processing the uncertainty data after probability theory , fuzzy theory and evidence theory ,proposed by Z.Pawlak in 1982. This theory analyzes and processes the inaccurate, imperfection and inconsistent data effectively, discovers hidden knowledge, reveals potential rules and reduces knowledge without any additional information or transcendental knowledge. Rough set theory is used successfully in many field such as data mining, machine learning ,pattern recognition and decision analysis.Knowledge reduction based on rough set theory's attribute reduction is one of most important contents about data preprocessing, it is proved that the minimum reduction problem for all the property is an NP-hard problem. At present ,time complexity of the methods of finding core and attribute reduction is still complicated, therefore, it's needed for the study about how to find algorithms that can improve the efficiency of attribute reduction.In this paper, after summing up the results of previous research for knowledge reduction, studied and designed a method which calculates attribute core by data coding and the pruning strategy of candidate record set for improving the algorithm efficiency of calculating the attribute code of decision table; then proposed a method which can block the discernable matrix by using attribute core, that greatly decreased the time complexith of calculating frequency of attribute. Based ont the results obtained, constructed a high efficient knowledge reduction algorithm, which used a heuristic function that using the frequency of attribute as the importance of attribute.By analyzing theory and the results of simulated experiments, it is verified that the algorithm in this paper is feasible and with high efficiency .