Research Of Incremental Updating Algorithm For Attribute Reduction

Rough Set theory is a mathematics tool for processing vague and imprecision knowledge,which is proposed by Poland scientist Z.Pawlak in 1982.Rough set theory is based on the indiscernibility relation that describes indistinguishable objects and can be approached by two accurate sets,the lower and upper approximation.Not needing other information this theory can analyze and process the imprecise, uncertain and incomplete data problems.In recent years,rough sets theory has been successfully implemented in Data Mining,Artificial Intelligence,Pattern Recognition, decision analysis,etc.Attribute reduction is one of main topics in rough set theory.The reduction of attributes can highly enhance the efficiency of data processing by removing redundant conditional attributes.So to study more effective algorithms to get the better attribute reduction and to decrease the time complexity becomes an important point in rough set theory.Computing core is one of important parts of attributes reduction because many attributes reduction algorithms begin core,so exploring effective computing core algorithm has an important practical value.Many existing algorithms mainly aim at the case of stationary information system or decision table,very little work has been done in updating of an attribute reduction.The got attribute reduction could be no longer valid because real-world data are generated dynamically and the objects that in information system or decision table change constantly,so requires dynamic modifications attribute reduction.The algorithm of computing core has the same problem as attributes reduction.The main contributions of this paper are as follows:1.Analysis found that the improved discernibility matrix presented by Professor Yang Ming exist unnecessary calculation.Therefore an improved discernibility matrix definition together with a method for computing the core is introduced.This paper introduces an incremental updating algorithm of the computation of a core based on improved discernibility matrix in the case of the problem of core updating when dynamic increase objects.2.Improved fast updating algorithm is proposed base a fast updating algorithm for computing an attributes core based on discernibility matrix,which mainly consider core updating problem when dynamic delete objects.3.Proposed an effective incremental updating attribute reduction algorithm which has nearly linear time and linear space complexity base on 1 after analysis found that the existing incremental updating algorithm for attribute reduction has high time and space complexity.