The Research On Efficient Heuristic Attribute Reduction Algorithm Based On Rough Set

With the rapid development of the database technology and data warehouse technology, the data stored in the rapid growth, the traditional data query and analysis methods have been unable to meet the people desire the knowledge implicit in the data.Knowledge discovery is to study how to quickly and accurately mining the potential of useful information in the chaotic mass data and used to predict future behavior.In1982, Polish scholar Pawlak.Z, proposed a rough set theory, as a new data mining method, in the case of maintaining the same classification ability, through attribute reduction to achieve the purpose of knowledge acquisition and simplify, and it became a new hot research problem.However rough set attribute reduction is an NP-hard problem.Common heuristic attribute reduction algorithm such as based on discernibility matrix reduction algorithm, based on information entropy reduction algorithm, based on genetic reduction algorithm and based on attribute importance attribute reduction algorithm.This article describes two improved heuristic attribute reduction algorithm, one of which is the improved discernibility matrix (DMI algorithm) and attributes frequency as the importance combined algorithm, can greatly reduce the computational complexity of the discernibility matrix.The second is based on conditional entropy and no-computing core attribute reduction algorithm for a no core-attribute of the decision-making table, according to computing the conditional entropy of condition attibute which add to reduction set relative to the dicision attibute and that is decreasing, so as to obtain relative reduction. By some examples analyzied the the pocess of implementation and feasibility of these two algorithms, and also put forward their limitations.In order to solve the problem of incompatible data in the decision-making table, this paper presents a new attribute reduction algorithm:Firstly, the method based on equivalence partitioning, re-divide the objects which the same condition attributes but different decision attribute as an object,thus eliminate incompatible data.And then calculate the upper and lower approximation of the attributes set, obtain the rate of the boundary region of the attributes set, select the minimum rate of boundary region attribute and add it to the reduction set, and then shrinking the domain until it is empty so far.Finally, in the resulting reduction set, determine whether each attribute is redundant, resulting in a relative reduction of the decision table.In addition, analyze of the time complexity of the algorithm, and show that the method is efficient and feasible through the experimental data, compared with the front of two algorithms, have been greatly improved in performance. The algorithm obtained the reduction is generally the optimal solution or suboptimal solution. Finally, this algorithm is applied to the teaching evaluation system, obtained the main factors to affect the quality of teaching from the analysis of teaching ratings data, which verifies the rough set attribute reduction has applications significance.