Statistical learning methods - Chapter 5, decision tree model and learning (Part 1)

Author's brief introduction ： The most important part of the whole building is the foundation , The foundation is unstable , The earth trembled and the mountains swayed . And to learn technology, we should lay a solid foundation , Pay attention to me , Take you to firm the foundation of the neighborhood of each plate .
Blog home page ： Qigui's blog
Included column ：《 Statistical learning method 》 The second edition —— Personal notes
From the south to the North , Don't miss it , Miss this article ,“ wonderful ” May miss you la
Triple attack( Three strikes in a row ):Comment,Like and Collect—>Attention

The previous completed articles are about 《 Statistical learning method 》 Second edition article , At the same time, practical cases are also attached .
A friend asked the author ： The second edition of the book has a lot more content than the first edition , I bought the first edition at that time , Will the blogger update this book completely ？
The author answers the original words ： Ah ha ha , Almost. , Not only do you have to understand , Also want Xiaobai to understand , Learn knowledge , I hope Xiaobai can learn something .
I am not talented , Although there is no Li Hang 、 zhou 、 Huang haiguang 、 Lu Wei and other excellent teachers are so talented , But fortunately , I can absorb knowledge from my predecessors , When the author learns knowledge and can understand , Also hope to help some beginners get started AI, Learn this route better .
（ Others may say that training institutions 、 Education platform , There are many better than the author AI Professional teachers , Why read the author's article ？ It depends on your choice , After all, what suits you is the best ）

The author makes a suggestion here （ If you don't like it, please find another place ）： The educational level of training institutions is certainly high , But knowledge is unchanging . At Chinese Universities , Wisdom Tree ,B standing ,CSDN And nuggets and other major platforms can be enough to arm your knowledge brain ; To assemble , Then take a look at the blog , Many bloggers also summarized the knowledge framework of all aspects , How to extract its essence depends on you .

Decision tree model

Decision tree concept

• The classification decision tree model is a tree structure that represents the classification of instances based on features .

• The decision tree is composed of nodes and directed edges . among , There are two types of nodes ：

  • Internal nodes , The internal node represents the feature or attribute
  • leaf , A leaf node represents a class .

• Decision tree is a tree structure （ It could be a binary tree or a non-binary tree ）. A tree is a recursive structure .

The idea of decision tree algorithm

-  Classification by decision tree , Start at root , Test a feature of the instance , According to the test results , Assign an instance to its child nodes ; At this time , Each sub node corresponds to a value of the feature .
-  So recursively test the instance and assign , Until the leaf node is reached , Finally, the instance is divided into leaf node classes , Take the category stored in the leaf node as the decision result .（ If you have learned tree structure in data structure , It is easier to solve the decision-making process of policy tree ）
-  Each internal node represents a test on a feature attribute , Each branch represents the output of the feature property in a codomain , Each leaf node stores a category .

• Decision tree is divided into classification tree and regression tree , Classification trees make decision trees for discrete variables , Regression trees make decision trees for continuous variables

Decision tree and if-then The rules

As a yard farmer , In the process of typing code, we frequently knock if-else sentence , In fact, my mind has already been filled with the idea of decision tree , So compared with the naive Bayesian classification algorithm in the previous article , Do you think the decision tree has been calculated “ cordial ” More . therefore , The decision tree can be transformed into a if-then Set of rules .

Decision tree learning

Petition —— How to make decisions

• The goal of decision tree learning is to build a decision tree model according to a given training data set , Enable it to correctly classify instances .

  • The essence of decision tree is to induce a set of classification rules from the training data set . That is, there may be more than one decision tree that can correctly classify the training data , Or maybe none of them .

• therefore , Decision tree learning requires not only better fitting of input data , We should also be able to correctly predict the future category marks .

  • therefore , The goal of the training algorithm is to establish a model with good generalization ability , That is to establish a model that can accurately predict the future sample category marks .

• Use the loss function to express this goal . The loss function of decision tree is usually the regularized maximum likelihood function .

  • The strategy of decision tree learning is to minimize the loss function as the objective function . After determining the loss function , It is the problem of choosing the optimal decision tree in the sense of loss function .

• Usually, the best feature is selected recursively , The training data are segmented according to this feature , Make the best classification process for each sub data set , This process corresponds to the division of feature space , It also corresponds to the construction of decision tree .

  • The constructed decision tree may have a good generalization ability for the training data , But it may not have a good classification ability for future test data , That is, fitting phenomenon may occur .
  • At this time, the generated decision tree needs to be pruned from bottom to top , Make it have good generalization ability .

• If there are many features , Or at the beginning of decision tree learning , Select features , It is also acceptable to leave only features with sufficient classification ability for training data .

• Here's a chestnut ：

  • Using training data , According to the principle of minimizing the loss function, a decision tree model is established ; When predicting , For new data , Use decision model to classify .

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn import metrics

iris = load_iris()
feature = iris.data
labels = iris.target

clf = DecisionTreeClassifier(criterion='entropy')  #  Information entropy 
x_train, x_test, y_train, y_test = train_test_split(feature, labels, test_size=0.2, random_state=0)
clf.fit(x_train, y_train)

y_pre = clf.predict(x_test)
accuracy = metrics.accuracy_score(y_test, y_pre)
print("The accuracy is %.3f" % accuracy)

episode —— Relieve boredom

After reading the previous decision tree and the general decision process , Let's simulate a real scene , In order to better solve the decision-making process of policy tree ： Mom forced you to go on a blind date again ~~

• If you are Mike, You are considering whether you want to allow your family to go on a blind date , What information will you use to decide whether to date ？
  • You may consider whether the other person's age is suitable
  • Will consider each other's appearance
  • You may also have to consider the other party's income .
• Mike Based on these factors , To judge whether you go on a blind date .

in real life , We will also face a variety of choices , And these choices are basically based on our previous experience . If the logic behind the judgment is arranged into a structure diagram , You will find that it is actually a tree view .

When we are making a decision tree , There are two stages ： Structure and pruning

From the chestnuts above , We can see that a decision tree is in the process of construction , There are three kinds of nodes ：

• Root node
  • The first selection point
• Internal nodes and branches
  • The middle process
• leaf
  • The final decision result

Thus, a complete decision tree is generated according to these three nodes . Simply speaking , The process of construction is the process of choosing what attribute is the node , So in the process of constructing the decision tree , Three main problems to be solved ：

• Which attribute to choose as the root node
• Which attributes are selected as child nodes
• When to end the classification and get the decision result

How to choose the root node ？

• The goal is ：
  • Pass a measure , To calculate the classification situation after branch selection through different features , Find the best one as the root node , And so on .
  • And this measure is ： entropy （ Next update ）

Last, last ——> summary

• Decision tree learning aims to build a model that fits well with the training data , And the complexity of the decision tree is very small .
• The decision tree learning algorithm is mainly composed of three parts
  • feature selection
    • It refers to selecting a feature from a large number of features in the training data as the branching standard of the current node , How to choose the characteristics with many different quantitative evaluation criteria , Thus, different decision tree algorithms are derived . For example, the commonly used algorithms are ID3、C4.5 and CART.
  • Decision tree generation
    • Evaluate criteria based on selected characteristics , Recursively generate child nodes from top to bottom , Stop the growth of the decision tree until the data set is indivisible .（ Use the recursive structure of the tree to understand ）
  • Pruning of the decision tree
    • Decision trees are easy to overfit , Generally speaking, it needs pruning , Reduce tree structure rules , Ease of overfitting , There are two kinds of pruning techniques: pre - pruning and post - pruning .
    • pre-pruning
      • At the same time, the decision tree is established and the pruning operation is carried out （ More practical ）, Pre pruning requires limiting the depth , Number of leaf nodes , Number of leaf node samples , Information gain, etc
    • After pruning
      • When the decision tree is established, prune , By a certain measure （ The more leaf nodes , The greater the loss ）