Fast Attribute Reduction Algorithms For The Incomplete Information System

There are many items in rough sets theory,and the attribute reduction is one of the most important research of rough sets theory.As the increasing of the scale of data,the classification efficiency of rough set model is greatly reduced.So the attribute reduction is important in this situation.In reality,the completeness of the data set cannot be guaranteed,so the data sets used to analyze are always incomplete.Then the incomplete information systems come up.But the classical rough sets cannot deal with the incomplete information systems,so there are a lot of research about incomplete information systems.Nowadays,there are two main research directions of dealing with incomplete information systems,one is the discernibility matrices model and the other is approximation relations model.But these two methods is of high time complexity.So this paper is focused on research of attribute reduction of incomplete information system in a low time complexity.This paper introduce the neighborhood rough set model into incomplete information systems,and conduct the attribute reduction based on dependency degree.By introducing the buckets into the attribute reduction the time complexity is reduced and the accuracy of the classification is increased in the same time.The results of the quick attribute reduction algorithm of incomplete information systems based on extended neighborhood rough sets is depend on the neighborhood size.And the neighborhood size is set without theoretical basis.In order to solve this problem this paper is conduct an algorithm of attribute reduction of incomplete information system based on the maximal nearest-neighborhood.The maximal nearest-neighborhood is gained from the data set itself,so the estimating of samples’ neighborhood using the maximal nearest-neighborhood has the theoretical basis.And this algorithm reduces the time complexity and increases the accuracy of the classification in the same time.