Research Of Attribute Reduction Algorithm Based On Decision Table Decomposition And Tolerance Relation

Attribute reduction is one of the key topic in the research of intelligent information processing.In recent years,rough set theory proposed by Pawlak shows a huge advantage in terms of attribute reduction.However,many existing reduction algorithms are inefficient when the data set is large,how to obtain reduction result quickly and efficiently is an important problem. In addition,most of reduction algorithms can only deal with complete information system.But in practical applications,datasets are often incomplete.To overcome these two shortcomings,this paper study attribute reduction algorithm based on rough set theory from complete and incomplete information system.(1) For complete information system,there exist many attribute reduction algorithms,but the solution process of these algorithms based on the entire table. To solve this problem,a new attribute reduction algorithm based on decision table decomposition was proposed.After each iteration,the algorithm decomposed the original decision table,so in the next iteration,the amount of computation were greatly reduced,therefore the complexity of the algorithm was dropped.Experiment results show that the algorithm have been improved both in the reduction rate and time complexity,and it can be used for attribute reduction in complete information system. (2) For incomplete information system,there have some theoretical achievements,but the relative attribute reduction algorithm is less.This paper introduces the relative concepts in the incomplete information system, analyses and study the distinctive between the incomplete information system and complete information system.Then a new attribute reduction algorithm combined with the tolerance relation is proposed,which can handle incomplete information system.This paper illustrate the calculation of the algorithm through a example and analyses the time complexity.A simulation experiment which selected six groups datasets from the UCI database has been done.The results show that the algorithm not only can handle discrete datasets but also can handle continuous datasets, and can get a better reduction sets.