The Extended Research On ID3 Algorithm

Decision tree induction has been applied to the area of automatic knowledge acquisition, which is learned from a set of cases to generate decision trees. ID3 is the typical decision tree induction algorithm. It uses the information entropy as heuristic to build a crisp decision tree, which is based on assumption that the attribute's values and classification are crisp all. But, fuzzy decision tree induction is an important way for learning from examples with fuzzy representation. It is a special case of fuzzy decision tree induction extracting rules from the data, which have symbol features and crisp classes. Because building optimal fuzzy decision trees is NP-hard, it is necessary to study the heuristics. In this thesis, we mainly research on ID3 algorithm and extend it to Fuzzy ID3 based on the fuzzy representation of examples. Then we compare Fuzzy ID3 with other fuzzy decision tree generation algorithms. The already existing fuzzy extension of ID3 algorithm can be regarded as a special case of this thesis. Both the theoretical analysis and the experimental comparison show that the fuzzy ID3 algorithm given in this thesis is better than the existing fuzzy decision tree generation algorithms such as min-Ambiguity algorithm in the aspects of training accuracy, testing accuracy and tree size.