Study Of Decision Tree Algorithm On Learning From Examples

Decision tree classification learning algorithm is one of the most widely used and very practical inductive inference methods. It is of much theoretical and practical significance in the artificial intelligence kingdom such as machine learning and data mining.In the many decision tree learning algorithms, the most influential one is the ID3, which takes the descending velocity of the information entropy as test attribute selection criterion. However, as is well known, ID3 has the shortage such as learning logical expressions and leaning to the attribute which takes more values. Base on ID3 algorithm, this thesis attempts to impove on learning logical expressions.We first introduce extensive matrix theory in learning from examples and the optimization problem in decision tree learning, the information theory principle and the implementation of ID3 algorithm and the pruning principle of C4.5 algorithm. Then, aiming at the ID3's defect on learning logical expressions, we put forward a decision tree simplification algorithm based on inclusion rule (DTSA-BOIR, abbr., BOIR) to simplify the decision tree constructed with ID3. BOIR traverses each node of the ID3 decision tree in preorder, compares its subtrees and, if the root attributes of each subtree are the same and some corresponding branches of all the subtrees are identical, changes the hierarchical relationship of the correlative attributes in the decision tree and merges the identical branches respectively.This thesis implements the algorithm BOIR for learning logical expressions and tests BOIR with some datasets in the FAMn family, and the data got from the experiment validates the validity of the algorithm.