Research Of Decision Tree Algorithms Based On Rough Set Theory

Knowledge Discovery in Databases (KDD) is an active research domain nowadays, and it is related to a few subjects such as artificial intelligence and database. Classification is an important research field in KDD. Decision tree is one of the models that are often used in classification, and it has been widely researched and applied since it was proposed in 1966. However, decision tree has some disadvantages such as variety bias, lack of anti-noise capability, etc, and optimization of decision tree has become a research hotspot.The dissertation focuses on optimization of decision tree algorithms based on rough set theory, and the main achievements are as follows:1. An overview and analysis of classical and optimized decision tree algorithms is put forward.2. The structures of hybrid decision tree and the RSH and the improved RSH2 algorithm based on the structure are proposed in the dissertation. RSH algorithm travels all the subsets of attributes and selects the attributes as few as possible which can classify more instances. RSH2 algorithm presorts the attributes in order that the best subset of attributes can be selected more quickly without traveling all the subsets.3. According to the problem that the anti-noise capability of traditional decision tree is not very well, VPRsDt algorithm is presented, which is based on variable precision rough set model. It makes use of rough set theory to select splitting attributes and prunes the decision tree. Variable precision positive region is used as the criterion of attributes selection, so the selection will be less influenced by noises. In addition, majority inclusion relation is used as the criterion to stop the splitting of decision tree so that exceptional instances are neglected and the predictive ability of the model will not be affected. The algorithm can avoid overfitting and the scale of decision tree can be decreased.4. Based on the research above, an experimental system is carried out, and the algorithms are validated both experimentally and theoretically.