Chapter IV decision tree summary

Catalog

Chapter four Decision tree summary

1. The basic flow

 2. Divide and choose

ID3 Decision tree ： Use information gain to divide attributes

C4.5 Decision tree ： Use information gain rate to divide attributes

CART Decision tree ： Use Gini index to divide attributes

  3. Pruning

pre-pruning :

After pruning :

4. Continuous and missing values

---

Chapter four Decision tree summary

This chapter mainly includes the basic process 、 Divide and choose 、 Pruning 、 Continuous and missing values, etc .

 

1. The basic flow

What is a decision tree ?

Decision tree is based on the structure of tree to deal with decision , The generation of decision tree is a recursive process , As shown in the example below .

 2. Divide and choose

  Different decision trees are divided in different ways ：

• ID3 Decision tree ： Use information gain to divide attributes

 

  shortcoming ： Tend to choose more attribute categories , But for those with more attribute median classification , Not representative .

• C4.5 Decision tree ： Use information gain rate to divide attributes

Be careful ： Because the gain rate has a preference for attributes with a small number of values , because C4.5 The algorithm is not enough to directly select the candidate partition attribute with the largest gain rate , Instead, a heuristic is used to find the attributes with higher than average information gain from the candidate partition attributes , Then choose the one with the highest gain rate .

• CART Decision tree ： Use Gini index to divide attributes

  3. Pruning

pre-pruning :

From the top down , Compare the accuracy of the verification set before and after partition , To determine whether to divide the current node . If after division , Accuracy not improved , No further division .

advantage ： Make some branches of the decision tree not expand , Reduce the risk of over fitting , Save training time .

shortcoming ： There is a possibility of under fitting .

After pruning :

Bottom up , First train the whole tree , Then prune upward from the leaf node , Determine whether to prune according to the accuracy of the verification set （ That is, whether to replace the current node with a leaf node ）.

advantage ： The risk of under fitting is very small , Generalization performance is also very high .

shortcoming ： The training time is longer than the pre pruning time .

4. Continuous and missing values

Continuous value processing ：

Use dichotomy to deal with continuous attributes , Calculate the information gain of the bisection region respectively .

Missing value processing ：

1. When calculating the information gain with missing attributes , First, calculate the information gain of the samples without missing parts , Then multiply the weight （ The proportion of absence in the total ）;

2. When the sample without this attribute enters the branch , Enter different branches with different weights （ The weight is the proportion of the branch sample to the total sample ）.