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

Data presents a great many varieties in practical applications,such as an increase of object,an extension of dimension and a change of attribute value.In Rough set theory,acquiring attribute reducts of dynamic data sets has attracted extensive attention.Many effective and efficient attribute reduction algorithms have been proposed,but most of them are suitable for dealing with static data sets.To deal with the problem of attribute reduction in dynamic data sets,the existing algorithms often regard the updated decision table as a starting point to calculate the reduction,which utilizes little of the existing knowledge.Clearly it is very time-consuming and even impossible.In order to improve the efficiency and effectiveness of attribute reduction,incremental attribute reduction algorithms based on discernibility matrix in decision table have been proposed.In this algorithm,the incremental information is used to update the discernibility matrix,and then all the reduction is calculated.However,it should be noted that objects in the same equivalence class have same condition attributes so that the corresponding positions of these elements in the matrix are exactly same,which greatly reduces the updating speed of the matrix.Taking all the analysis above into consideration,this paper proposed a corresponding incremental reduction algorithm for the three types of dynamic data.The main works are as follows:1.Aiming at the increase of objects dynamically,three matrices in the sense of Positive region,Shannon and Complement were defined.Analyzing the updating mechanism of the three representative discernibility matrix when objects grow dynamically,an incremental attribute algorithm based on discernibility matrix in compacted decision table was proposed.2.With respect to the extension of dimension and variation of attribute values dynamically,this paper firstly analyzed the updating mechanism of discernibility matrix in the sense of Positive Region,Shannon and Complement,and then introduced the incremental algorithm based on discernibility matrix in decision table.3.In order to further improve the performance of incremental algorithm for extension of dimension and variation of attribute values,this paper defined a new compacted decision table,constructed three kinds of discernibility matrix,analyzed the updating mechanism of discernibility matrix,and then introduced the incremental algorithm based on discernibility matrix in compacted decision table.