Research On Quick Algorithm For Attribute Reduct Based On Rough Set Theory

Attribute reduction is a common problem in rough set theory as there usually are many candidate attributes collected to represent recognition problems. Data expand quickly not only in the rows (objects) but also in the column (attributes) nowadays. Nevertheless, some of attributes are irrelevant to the recognition tasks. Experiments show irrelative attributes will deterioratethe performance of the learning algorithms for the curse of dimensionality, increase training and test times. Therfore attribute reduction determines the effection of rules derivation and decision aidance. Furhermore, The quality of rules is directly decided by the result and speed of attribute reduction. However, it is the speed of attribute redute that restricts the advance and application of rough set theory by far. Therfore it is the important theory sense and application value investating the quick attribute reduct algorithm.Three rough set based attribute reduction algorithm are proposed in this paper, the main content of the paper is shown as follows.(1) The existing discernibility matrices are analyzed,by which attribute reduct in the algebra view can only be obtained. Moreover, a new discernibility matrix in the information view is proposed. Thus an algorithm based on the discernibility matrix is constructed, by means of which we can acquire the reducts and the core of a decision table in the information view. The numerical experiment shows that the algorithm in this paper can obtain the same reduct as Hu's algorithm, and the time consuming of this algorithm is less than the one of Hu's algorithm.(2) The change mechanism of Shannon entropy is given by author when the positive region is deleted from a decision table, by which a quick algorithm of attribute reduct is proposed. In this algorithm the positive region in some certain attribute set is removed form the discoursed universe, and the set of remained objects is regarded as a new discoursed universe. Therefore, the amount of objects which appear in the procession of computing reducts becomes smaller. The experiment result illustrate that the algorithm in this paper achieve the same result of attribute reducts. Meanwhile, the consuming time is much less than the algorithm CEBARKCC.(3) For the hybrid data, the change mechanism of Shannon entropy is presented, by means of which a new algorithm of computing attribute reducts is originally constructed. In this algorithm, the amount of objects gradually becomes smaller among the attribute reduction process. The numerical experiment shows that the reducts obtained through using the quick attribute reduct algorithm are same as the one by Hu's algorithm. Furhtermore, the new algorithm consumes much less time than Hu's algorithm.All these results will be useful for rough set theory based data mining and knowledge discovering, and provide some new approaches for them.