Feature Selection Of Dynamic Incomplete Data Based On The Limited Tolerance Relation

The classical rough set theory is a mathematical tool which only deals with complete data.Due to the measurement errors and limitations on data extraction,incomplete and uncertain data can be seen everywhere and the data changes dynamically with time in real life.So the application of classical rough set theory is limited.Therefore,how to deal with the dynamic data efficiently and find an appropriate rough set extension model is for current researchers one of the key research topics.In rough set theory,attribute reduction is the key and core of knowledge acquisition.Traditional attribute reduction algorithms are used to solve attribute reduction of dynamic data,which consumes a large amount of computing time and memory capacity.It finally leads to slow operation speed and can't achieve the desired effect.How to update attribute reduction dynamically and improve attribute reduction algorithm under dynamic incomplete data is one of the important issues in the field of data mining.In this paper,based on rough set theory and acquired knowledge for the purpose,the attribute reduction methods of dynamic incomplete information systems are deeply studied and discussed.The main work of this paper includes:Firstly,based on the limited tolerance relation model,the different degrees of missing attribute values lead to the differences of incomplete information systems.We make use of the definition of completeness degree,a rough set extension model of the limited tolerance relationship between objects is given.The theoretical and practical proof of the model is given.Secondly,we use the definition of positive region,a new equivalent formula of positive region is proposed.When the attribute set changes dynamically,the updating formula of positive region is analyzed.We combine with the definition of attribute importance,the incremental feature selection algorithms for adding and deleting attribute sets(AIAR algorithm and DIAR algorithm)are given.The time complexity of the algorithm is analyzed to show the rationality of the algorithm.In addition,the computing method of the new positive region is discussed when a single object changes dynamically.By using the definition of attribute importance,an incremental feature selection algorithm is presented when a single object changes dynamically.According to the dynamic change of a single object,this paper also studies the updating formula of the positive region when multiple objects are added or deleted.We combine with the definition of attribute importance,an incremental feature selection algorithm is proposed when multiple objects are changed dynamically.By discussing the time complexity,the effectiveness of these two algorithms is illustrated.Finally,four incomplete data sets in UCI database are selected to validate the proposed algorithm.The efficiency and rationality of the proposed algorithm are illustrated.