New Research On Several Problems For Attribute Reduction Of Information Table

The rough set theory, which is an excellent data analysis tool to handle uncertain information, such as imprecise, inconsistent, incomplete and so on, is one of the hardest fields. It has received much attention of the researchers around the world. Rough set theory has been applied to many areas successfully including pattern recognition, machine learning, decision support, knowledge discovery, fault diagnosis, forecast modeling and so on. Attribution reduction is one of the basic contents in rough set theory, key technology of rough set theory applied and important research contents in knowledge discovery, becoming one of the hottest research fields. Efficient and effective algorithms for attribution reduction are the foundation of rough set theory applied, also the guarantee of rough set theory applied on a large scale. Surrounding the one key problems of the rough set theory i.e. attribute reduction, the following three works have been done: attribute reduction in information table, attribute reduction in consistent decision table, attribute reduction in inconsistent decision table.First, A rough set model is established to supervise the absolute attribute reduction for information table on the basis of studying the separating capacity. And a novel conception is proposed, which is called discernibility -quality based on decision , on the basis of exploring the relations between the ability of discernibility and classifying , this novel conception is an important criterion which supervises the relative attribute reduction for decision table. In addition, several related conclusions are drawn by theoretical analyses in studying discernibility-quality, approximate quality and discernibility -quality based on decision. A comparison experiment shows that discernibility-quality based on decision is finer than approximate quality for describing the ability of classifying.Second, A new algorithm for all the attribute reductions is proposed on the basis of the structure for rough attribute vector tree (RAVT), the theoretical analyses show that the time complexity of the new algorithm is less than that of the traditional algorithm based on discerniblity-matrix and its improved algorithm. A comparison experiment on computational efficiency proves that this new algorithm is more efficient than the traditional algorithm and its improved algorithm. Third, Skowron's discernibility-matrix for computing attribute reduction of an in consistent decision table may lead to mistakes. At present ,several methods by modifying discernibily- matrix's definition are not fully reasonable to improve this problem in some papers, So a novel solution is presented in this paper.Finally, A new algorithm for the simplified discernibility-matrix is proposed in this paper.This algorithm takes the idea of Bucket Sorts to construct attribute-buckets .then, the elements in discernibility-matrix is established while discernibility-matrix is being simplified by use of this attribute-buckets without being sorted. This can bring on the speed of simplifying discernibility-maxtrix ,and obtain the ordered and simplified discernibility–matrix finally; At the same time, A new criterion of significance of attributes is put forward based on the three aspects which are the weight of element containing the attribute, the frequence and the absorptive ability of the attribute in the discernibility-matrix. Therefore A new method for attribute reduction is introduced on the basis of the novel criterion of the significance of attributes and the ordered and simplified discernibility-matrix,, the theoretical analysis proves that the worst time complexity of the new method is less than the other algorithms based on discernibility-matrix . One comparative experiment on computational efficiency shows that this new simplified discernibility-matrix algorithm is more efficient than the homogeneous algorithm. In addition, another comparative experiment in attribute reduction display that this method for attribute reduction can largely find out a minimal attribute reduction.