Research On Computation Approach For Dynamic Reduct

Rough set theory is a new mathematical tool to deal with vagueness and uncertainty. It has been successfully applied in many fields. Dynamic reduct is an effective reduction method, and the advantages have been proved. But the computation of dynamic reduct is too complex to gain it effectively. Based on rough set theory, this thesis mainly focuses on the problem of optimized computation for dynamic reduct.After describing the process of creating and reducing discernibility function in details, the disadvantages of discernibility matrix and truth table method are pointed out. In the view of Boolean operation, the effective discernibility information of objects in domain is obtained, and the minimal conjunctive normal form of discernibility function is also constructed directly. According to the unique features of reduction, reduction tree model is given and optimized. The problem of calculating reduction is converted into traversing reduction tree. Based on reduction tree, an improved basic reduction algorithm is proposed. All the reductions of information system are obtained effectively, so it is helpful to calculate dynamic reduct.The advantages and disadvantages of dynamic reduct are analyzed, and dynamic reduct model is developed by weakening the restrictive conditions. For judging whether a sub-table reduction is dynamic reduct, a judgement theorem is presented. It is the theoretical foundation of screening dynamic reduct. Based on dividing and conquering thought, a fast generalized dynamic reduct algorithm is put forward. The algorithm overcomes the shortcomings of traditional algorithm. Within the stability degree threshold limit, no more than |F|/2 sub-tables need to be calculated, which improves the efficiency of getting dynamic reduct greatly.UCI dataset is used for testing our methods. Experimental results and performance analyses denote that they are feasible and effective.