Construction Of Minimal Decision Tree Based On Sample Pair

With the progress of social life, learning and daily production and the rapid development of the Internet technology, massive and potentially valuable data appeared. How to discover valuable knowledge from the massive data with tools and methods effectively, accurately and economically and extract potentially useful rules to provide services for produce and life has become one of the hot spots in the field of data mining. Classification algorithm as one of the data mining algorithms has widely application in the commercial areas, meanwhile, decision tree learning algorithm is the core one. ID3 decision tree algorithm is a classical algorithm, but there are some problems in ID3 algorithm, such as the inherent bias, the resulting need for tree pruning and so on.A new algorithm about how to construct a decision tree is presented in this paper. The studies in view of consistent and inconsistent decision tables are as follows:(1) For the consistent decision tables, firstly, a minimal feature is defined. Because features in the minimal set are necessary, the minimal decision tree constructed by the features in this set does not include redundant features, at the same time, rules are consistent. Secondly we give a way to calculate the minimal feature set and an algorithm to construct the minimal decision tree. At last, the feasibility and effectiveness of the algorithm is verified by examples.(2) For inconsistent decision tables, first we build a consistent set of ? distribution based on ? distribution and define a discernibility relationship for conditions characteristic. Because each minimal feature corresponds to an equivalence class of a conditions characteristic, the whole minimal features can be discovered by the equivalence classes. Moreover, a minimal feature set can be built with the features. Then, combined with recognition relation and equivalence class, this paper presents a method to find all minimal features and an algorithm to build minimal decision tree. This are verified by examples. Compared with the traditional ID3 algorithm, the minimal decision tree presented in this paper has neither the inherent bias nor the tree pruning process.