Research On Attribute Reduction Algorithms Based On Rough Sets Theory

Rough sets theory , presented in 1982 by Polish mathematician Z.Pawlak , is a powerful mathematical tool to deal with imprecise , incomplete and uncertain data . It is based on the indiscernibility relation that describes indistinguishable objects , and concepts are represented by using lower and upper approximations . Rough sets theory is widely used in many fields such as attribute reduction , data mining , machine learning , pattern identifying and decision-making .The attribute reduction of information system is the main topic in rough sets theory . Getting the best reduction or all reduction is a NP problem . Heuristic algorithm based on the attribute importance had been made to get better reduction .In the process of attribute reduction , attribute reduction algorithms based on discernibility matrix is proposed . Because of its high time complexity , (1) the absorptivity in the proposition calculation is used to the process of constructing the discernibility matrix , then the effectless repeated elements are deleted , thus the first efficiency of attribute reduction algorithm is improved ; (2) the second improved algorithm which is based on the frequency of attribute is proposed ; (3) the third algorithm defined the attribute importance using the information entropy . The effectiveness and the feasibility of the three algorithms in this paper are clearly demonstrated by the example analysis (experiment results) .The information system isn't a simplest one after attribute reduction . It includes some redundancy information and needs value reduction . The general algorithm and its improved algorithms are proposed in this paper .Using these algorithms we can reduce the complexity of the original attribute reduction algorithm and value reduction algorithm greatly and finally acquire the optimal decision-making rules of the information system .At last, the reduction algorithms are applied (used) to the method of data mining . The experiment results indicate this method is very efficient.