Research Of Attribute Reduction Algorithm Based On Rough Set

Rough set is one of the methods of data mining. It is an effective tool to deal with inaccurate, inconsistent, incomplete information. Attribute reduction is a research focus in rough set theory. Under the condition of maintaining the classification and decision making ability of information systems constant, deleting irrelevant or unimportant attributes and forming tidy rule base to help people making the right and concise decisions. Currently looking for the minimum reduction of an information system is exponential complexity, so it is still the main research to search for fast and efficient algorithms for attribute reduction of rough set theory. It has important application significance in the information system analysis and data mining.This paper systematically studied the attribute reduction algorithms based on rough set and proposed an improved reduction algorithm based on attribute frequency and a new attribute reduction algorithm based on simplified discernibility matrix.This paper studied HORAFA and HORAFA-A algorithm and made the following improvements as for the disadvantages of HORAFA-A algorithm proposed by HU YU. It designed algorithm with simplified discernibility matrix, which greatly reduced the time for generating the matrix and the storage space which matrix elements occupied; it designed a weighting formula to measure the attribute discernibility, when there are more than one attribute having the greatest frequency at one time,choosing the attribute which has the largest weighted value into reduction sets to ensure obtaining the simplest and largest coverage of rules. It proved that the improved algorithm is complete, and can obtain the minimum reduction for compatible and incompatible information systems. The experimental results show that the algorithms is better than HORAFA-A algorithm and effective.In the existing attribute reduction algorithms based on discernibility matrix, the discernibility matrix is usually obtained first, these algorithms have higher time and space complexity. In order to reduce the complexity of such algorithms, this paper designed a function to calculate the attribute frequency in the simplified discernibility matrix, and gave the rapid calculation algorithm of the function which does not calculate the discernibility matrix and can directly calculate the frequency value of attributes. On this basis, an attribute reduction algorithm with heuristic information of attribute frequency was designed. It proved that the algorithm is complete, and can obtain the minimum reduction for compatible or incompatible information systems. The experimental results show that the algorithm has rapid reduction speed and small space cost, it is applicable to large data sets of attribute reduction, and is obviously better than HORAFA-A algorithm.