人工智能与机器学习11-决策树

决策树王秋月中国人民大学信息学院K近邻：模型就是训练数据拟合训练数据很快只是存储数据预测比较慢需要计算大量的距离判定边界较灵活YX不同分类器的特点逻辑回归：模型就是参数拟合训练数据可能较慢必须找到最优参数预测较快计算期望值判定边界较简单，缺乏灵活性X0.01.0Probability0.5𝑦𝛽1𝑥 =1+𝑒−(𝛽0+𝛽1𝑥+ε

)不同分类器的特点DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainMildHighStrongNo决策树介绍想要根据temperature,humidity,wind,

outlook来预测是否打网球决策树介绍想要根据temperature,humidity,wind,

outlook来预测是否打网球使用特征来划分数据，进而预测结果决策树介绍Play

TennisNo

TennisTemperature:>=

Mild想要根据temperature,humidity,wind,

outlook来预测是否打网球使用特征来划分数据，进而预测结果决策树介绍Play

TennisNo

TennisTemperature:>=

MildNodesLeaves想要根据temperature,humidity,wind,

outlook来预测是否打网球使用特征来划分数据，进而预测结果决策树介绍Play

TennisNo

TennisNo

TennisTemperature:>=

MildHumidity:=

NormalNodesLeaves想要根据temperature,humidity,wind,

outlook来预测是否打网球使用特征来划分数据，进而预测结果预测类别结果的决策树决策树介绍Play

TennisNo

TennisNo

TennisTemperature:>=

MildHumidity:=

Normal预测连续值的回归树例如：使用喜马拉雅山脉的坡度和高度预测平均降水量（连续值）48.50

in.13.67

in.55.42

in.Elevation:<7900

ft.Slope:<

2.5º预测连续值的回归树例如：使用喜马拉雅山脉的坡度和高度预测平均降水量（连续值）48.50

in.13.67

in.55.42

in.Elevation:<7900

ft.Slope:<

2.5º预测连续值的回归树例如：使用喜马拉雅山脉的坡度和高度预测平均降水量（连续值）叶子节点的值是其所有成员的平均值0Source:

/stable/auto_examples/tree/plot_tree_regression.html1312345-1.0-2.00.01.02.0预测连续值的回归树012345-1.0-2.00.01.02.0max_depth=214预测连续值的回归树Source:

/stable/auto_examples/tree/plot_tree_regression.html012345-1.0-2.00.01.02.0max_depth=2max_depth=515预测连续值的回归树Source:

/stable/auto_examples/tree/plot_tree_regression.html选取一个特征，把数据分成两部分，构成一个二叉树创建一个决策树创建一个决策树选取一个特征，把数据分成两部分，构成一个二叉树继续选取特征，划分数据创建一个决策树选取一个特征，把数据分成两部分，构成一个二叉树继续选取特征，划分数据直到：叶子节点纯了---仅包含一类实例何时停止分裂直到：叶子节点纯了---仅包含一类实例达到最大深度何时停止分裂直到：叶子节点纯了---仅包含一类实例达到最大深度达到某一性能指标何时停止分裂使用贪婪搜索：每一步寻找最优划分Temperature:>=

MildNo

TennisPlay

TennisLeaves创建最优决策树使用贪婪搜索：每一步寻找最优划分什么是最优划分？Temperature:>=

MildNo

TennisPlay

TennisLeaves创建最优决策树使用贪婪搜索：每一步寻找最优划分什么是最优划分？最大化不纯度减小量的划分Temperature:>=

MildNo

TennisPlay

TennisLeaves创建最优决策树使用贪婪搜索：每一步寻找最优划分什么是最优划分？最大化不纯度减小量的划分如何度量不纯度？Temperature:>=

MildNo

TennisPlay

TennisLeaves创建最优决策树分类错误公式：2

Yes2

No6

Yes2

NoPlay

Tennis8

Yes4

NoNo

TennisTemperature:>=

Mild基于分类错误的划分分类错误公式：基于分类错误的划分划分前的分类错误：1−8/12

=

0.33332

Yes2

No6

Yes2

NoPlay

Tennis8

Yes4

NoNo

TennisTemperature:>=

Mild分类错误公式：基于分类错误的划分划分后左边的分类错误：1−2/4

=

0.50002

Yes2

No6

Yes2

NoPlay

Tennis8

Yes4

NoNo

TennisTemperature:>=

Mild0.3333分类错误公式：基于分类错误的划分划分后右边的分类错误：1−6/8

=

0.25002

Yes2

No6

Yes2

NoPlay

Tennis8

Yes4

NoTemperature:>=

Mild0.3333No

Tennis0.5000分类错误公式：基于分类错误的划分分类错误的变化：0.3333−4/12

∗0.5000−8/12

∗0.25002

Yes2

NoNo

Tennis0.5000Play

Tennis0.25006

Yes2

No8

Yes4

NoTemperature:>=

Mild0.3333分类错误公式：基于分类错误的划分分类错误的变化：0.3333−4/12

∗0.5000−8/12

∗0.2500=02

Yes2

NoNo

Tennis0.5000Play

Tennis0.25006

Yes2

No8

Yes4

NoTemperature:>=

Mild0.3333使用分类错误，分裂停止问题：叶子节点仍然不是同质的尝试另外一个性能指标？2

Yes2

No6

Yes2

NoPlay

Tennis8

Yes4

NoNo

TennisTemperature:>=

Mild基于分类错误的划分2

Yes2

No6

Yes2

NoPlay

Tennis8

Yes4

NoNo

TennisTemperature:>=

Mild基于熵的划分熵的公式：熵的公式:基于熵的划分2

Yes2

No6

Yes2

NoPlay

TennisNo

TennisTemperature:>=

Mild8

Yes4

No划分前的熵：−8/12*𝑙𝑜𝑔2(8/12)−4/12*𝑙𝑜𝑔2(4/12)=0.9183基于熵的划分划分后左边的熵：−2/4*𝑙𝑜𝑔2(2/4)−2/4*𝑙𝑜𝑔2(2/4)=1.00002

Yes2

No6

Yes2

NoPlay

TennisNo

TennisTemperature:>=

Mild8

Yes4

No0.9183熵的公式:基于熵的划分划分后右边的熵：−6/8*𝑙𝑜𝑔2(6/8)−2/8*𝑙𝑜𝑔2(2/8)=0.81132

Yes2

No6

Yes2

NoPlay

TennisTemperature:>=

Mild8

Yes4

No0.9183No

Tennis1.0000熵的公式:基于熵的划分熵的变化：0.9183−4/12∗1.0000−8/12∗0.8113=0.04412

Yes2

No6

Yes2

NoTemperature:>=

Mild8

Yes4

No0.9183No

Tennis1.0000Play

Tennis0.8113熵的公式基于熵的划分允许继续分裂下去最终达到叶子节点同质的目标为什么熵可以达到这一目标，而分类错误不行？2

Yes2

No6

Yes2

NoPlay

TennisNo

TennisTemperature:>=

Mild8

Yes4

No基于熵的划分分类错误是一个平坦函数，在中心点达到最大值分类错误vs熵0.0

0.

5Purity1.

0Classification

ErrorError分类错误是一个平坦函数，在中心点达到最大值中心点表示的是50/50的歧义划分分类错误vs熵0.0

0.

5Purity1.

0Classification

ErrorError分类错误是一个平坦函数，在中心点达到最大值中心点表示的是50/50的歧义划分分类指标偏向于远离中心点的结果分类错误vs熵0.0

0.

5Purity1.

0Classification

ErrorError熵具有相同的最大值，但是弯曲的曲线0.0

0.

5Purity1.

0Classification

ErrorCross

EntropyError分类错误vs熵熵具有相同的最大值，但是弯曲的曲线曲度使得分裂可以继续到叶子节点纯了为止0.0

0.

5Purity1.

0Classification

ErrorCross

EntropyError分类错误vs熵熵具有相同的最大值，但是弯曲的曲线曲度使得分裂可以继续到叶子节点纯了为止为什么？0.0

0.

5Purity1.

0Classification

ErrorCross

EntropyError分类错误vs熵使用分类错误，函数是平坦的分裂带来的信息增益分裂带来的信息增益使用分类错误，函数是平坦的分裂带来的信息增益使用分类错误，函数是平坦的最终的平均分类错误很有可能与父节点的分类错误相等分裂带来的信息增益使用分类错误，函数是平坦的最终的平均分类错误很有可能与父节点的分类错误相等从而导致提前停止使用熵，函数有个“鼓包”分裂带来的信息增益分裂带来的信息增益使用熵，函数有个“鼓包”使得子节点的平均熵少于父节点的熵分裂带来的信息增益使用熵，函数有个“鼓包”使得子节点的平均熵少于父节点的熵从而产生信息增益，使得分裂可以继续实际中，常使用基尼指数做分裂基尼指数0.0

1.

0Classification

ErrorCross

EntropyGini

IndexError0.

5Purity

实际中，常使用基尼指数做分裂其函数类似于熵---也有“鼓包”基尼指数0.0

1.

0Classification

ErrorCross

EntropyGini

IndexError0.

5Purity

实际中，常使用基尼指数做分裂其函数类似于熵---也有“鼓包”没有对数基尼指数0.0

1.

0Classification

ErrorCross

EntropyGini

IndexError0.

5Purity

问题：决策树容易过拟合数据微小的变化能对预测结果产生较大的影响---highvariance决策树高方差（highvariance）问题：决策树容易过拟合数据微小的变化能对预测结果产生较大的影响---highvariance解决方案:修剪决策树修剪决策树问题：决策树容易过拟合数据微小的变化能对预测结果产生较大的影响---highvariance解决方案:修剪决策树预剪枝后剪枝修剪决策树在决策树构建过程中，依据预先设定的条件，提前终止树的生长。Scikit-Learn中：决策树的最大深度（max_depth）决策树的最大叶子数（max_leaf_nodes）可分裂节点应包含的最少样例数（min_samples_split）叶节点应包含的最少样例数（min_samples_leaf）不纯度减少的最小量（min_impurity_decrease）预剪枝在决策树构建完成之后进行剪枝，得到一棵简化的树。自底向上地考察每个非叶节点，如果将其子树剪去，成为一个叶节点，能带来决策树泛化性能提升，则将该子树替换为叶节点错误率降低剪枝(reduced-errorpruning,REP)后剪枝

后剪枝

一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝训练时间比未剪枝和预剪枝决策树都要大得多。预剪枝vs.后剪枝容易实现和解释“if…then…else”逻辑可以处理任何数据类型二值,序数,连续值无需数据预处理和缩放决策树的优点导入包含分类方法的类：fromsklearn.treeimport

DecisionTreeClassifier创建该类的一个对象：DTC=

DecisionTreeClassifier(criterion='gini’,max_features=10,

max_depth=5)拟合训练数据，并预测：DTC=DTC.fit(X_train,

y_train)y_predict=

DTC.predict(X_test)决策树分类器的语法导入包含分类方法的类：fromsklearn.treeimport

DecisionTreeClassifier创建该类的一个对象：DTC=

DecisionTreeClassifier(criterion='gini’,max_features=10,

max_depth=5)拟合训练数据，并预测：DTC=DTC.fit(X_train,

y_train)y_predict=

DTC.predict(X_test)决策树分类器的语法决策树参数/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html导入包含分类方法的类：fromsklearn.treeimport

DecisionTreeClassifier创建该类的一个对象：DTC=

DecisionTreeClassifier(criterion='gini’,max_features=10,

max_depth=5)拟合训练数据，并预测：DTC=DTC.fit(X_train,

y_train