Research On Optimization Computation Approach For Reduct Based On Rough Set

Rough Set Theory is a new mathematical tool to reason about uncertain and vague information. It has been rapidly developed and widely applied in many fields. Reduct is the most important concept in rough set, whose main purpose is to remove the redundant information and preserves classification accuracy of original information system. Facing with huge amounts of data, the old algorithms for reduct is not feasible. It is necessary to optimize the computation theory, and proposes some practical algorithms to improve the efficiency of reduct. Based on rough set theory, the thesis mainly focuses on the problems of optimized computation for reduct.Not only the advantages and disadvantages of three kinds of reduct in rough set but also their relations have been compared and analysed. Through improving discernibility matrix, the information for core and reduct without inclusion relation is gained in the process of comparing objects. Based on this information, a new heuristic algorithm for reduct is proposed. The experimental results indicate that the reduct of new heuristic algorithm is identical with the minimal reduct, showing the efficiency of new algorithm.With deeply studying the completeness of reduct algorithm, the incompleteness of existing algorithms for reduct is pointed out, and the thesis also provides the proof to prove the completeness of new heuristic algorithm for reduct. Then, under the Pawlak's definition for reduct, it is certified that the number of reduct in any decision information system is the combination function of condition attribute. Based on this property, a non-exponential algorithm is put forward to compute all reducts, which is less than other algorithms in the complexity of time and space. The conclusion is helpful to improve the efficiency of reduct and enhance rough set's capacity of analysis to larger dataset.