《人工智能和机器学习--PPT11-决策树》由会员分享，可在线阅读，更多相关《人工智能和机器学习--PPT11-决策树（67页珍藏版）》请在金锄头文库上搜索。
1、决策树王秋月中国人民大学信息学院K近邻：近邻： 模型就是训练数据模型就是训练数据 拟合训练数据很快拟合训练数据很快 只是存储数据只是存储数据 预测比较慢预测比较慢 需要计算大量的距离需要计算大量的距离 判定边界较灵活判定边界较灵活YX不同分类器的特点逻辑回归：逻辑回归： 模型就是参数模型就是参数 拟合训练数据可能较慢拟合训练数据可能较慢 必须找到最优参数必须找到最优参数 预测较快预测较快 计算期望值计算期望值 判定边界较简单，缺乏灵判定边界较简单，缺乏灵活性活性X0.01.0Probability0.5𝑧𝛽1𝑦 =1+𝑒(
2、0573;0+ 𝛽1𝑦 + )不同分类器的特点DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainMil
3、dNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainMildHighStrongNo决策树介绍 想要根据想要根据temperature, humidity, wind,outlook来预测是否打网球来预测是否打网球决策树介绍 想要根据想要根据temperature, humidity, wind,outlook来预测是否打网球来预测是否打网球 使用特征来划分数据，进使用特征来划分数据，进而预测结果而预测结果决策树介绍PlayTennisNoT
4、ennisTemperature:= Mild 想要根据想要根据temperature, humidity, wind,outlook来预测是否打网球来预测是否打网球 使用特征来划分数据，进使用特征来划分数据，进而预测结果而预测结果决策树介绍PlayTennisNoTennisTemperature:= MildNodesLeaves 想要根据想要根据temperature, humidity, wind,outlook来预测是否打网球来预测是否打网球 使用特征来划分数据，进使用特征来划分数据，进而预测结果而预测结果决策树介绍PlayTennisNo TennisNoTennisTempera
5、ture:= MildHumidity:= NormalNodesLeaves 想要根据想要根据temperature, humidity, wind,outlook来预测是否打网球来预测是否打网球 使用特征来划分数据，进使用特征来划分数据，进而预测结果而预测结果 预测类别结果的预测类别结果的决策树决策树决策树介绍PlayTennisNo TennisNoTennisTemperature:= MildHumidity:= Normal预测连续值的回归树 例如：使用喜马拉雅山脉例如：使用喜马拉雅山脉的坡度和高度的坡度和高度 预测平均降水量（连续值）预测平均降水量（连续值）48.50 in.13
6、.67 in.55.42 in.Elevation: 7900ft.Slope: 2.5预测连续值的回归树 例如：使用喜马拉雅山脉例如：使用喜马拉雅山脉的坡度和高度的坡度和高度 预测平均降水量（连续值）预测平均降水量（连续值）48.50 in.13.67 in.55.42 in.Elevation: 7900ft.Slope:= MildNo TennisPlay TennisLeaves创建最优决策树 使用贪婪搜索：每一步使用贪婪搜索：每一步寻找最优划分寻找最优划分 什么是最优划分？什么是最优划分？Temperature:= MildNo TennisPlay TennisLeaves创建最
7、优决策树 使用贪婪搜索：每一步使用贪婪搜索：每一步寻找最优划分寻找最优划分 什么是最优划分？什么是最优划分？ 最大化不纯度减小量的最大化不纯度减小量的划分划分Temperature:= MildNo TennisPlay TennisLeaves创建最优决策树 使用贪婪搜索：每一步使用贪婪搜索：每一步寻找最优划分寻找最优划分 什么是最优划分？什么是最优划分？ 最大化不纯度减小量的最大化不纯度减小量的划分划分 如何度量不纯度？如何度量不纯度？Temperature:= MildNo TennisPlay TennisLeaves创建最优决策树分类错误公式：分类错误公式：2Yes2 No6Yes2
8、 NoPlayTennis8Yes4 NoNo TennisTemperature:= Mild基于分类错误的划分分类错误公式：分类错误公式：基于分类错误的划分划分前的分类错误：划分前的分类错误：1 8/12 = 0.33332Yes2 No6Yes2 NoPlayTennis8Yes4 NoNo TennisTemperature:= Mild分类错误公式：分类错误公式：基于分类错误的划分划分后左边的分类错误：划分后左边的分类错误：1 2/4= 0.50002Yes2 No6Yes2 NoPlayTennis8Yes4 NoNo TennisTemperature:= Mild0.3333分
9、类错误公式：分类错误公式：基于分类错误的划分划分后右边的分类错误：划分后右边的分类错误：1 6/8= 0.25002Yes2 No6Yes2 NoPlayTennis8Yes4 NoTemperature:= Mild0.3333No Tennis0.5000分类错误公式：分类错误公式：基于分类错误的划分分类错误的变化：分类错误的变化：0.3333 4/12 0.5000 8/120.25002Yes2 NoNo Tennis0.5000PlayTennis0.25006Yes2 No8Yes4 NoTemperature:= Mild0.3333分类错误公式：分类错误公式：基于分类错误的划分
10、分类错误的变化：分类错误的变化：0.3333 4/12 0.5000 8/120.2500= 02Yes2 NoNo Tennis0.5000PlayTennis0.25006Yes2 No8Yes4 NoTemperature:= Mild0.3333 使用分类错误，分裂停止使用分类错误，分裂停止 问题：叶子节点仍然不是问题：叶子节点仍然不是同质的同质的 尝试另外一个性能指标？尝试另外一个性能指标？2Yes2 No6Yes2 NoPlayTennis8Yes4 NoNo TennisTemperature:= Mild基于分类错误的划分2Yes2 No6Yes2 NoPlayTennis8Y
11、es4 NoNo TennisTemperature:= Mild基于熵的划分熵的公式：熵的公式：熵的公式熵的公式:基于熵的划分2Yes2 No6Yes2 NoPlayTennisNo TennisTemperature:= Mild8Yes4 No划分前的熵：划分前的熵：8/12*𝑙𝑜𝑔2(8/12)4/12*𝑙𝑜𝑔2(4/12)= 0.9183基于熵的划分划分后左边的熵：划分后左边的熵：2/4*𝑙𝑜𝑔2(2/4)2/4*𝑙w
12、900;𝑔2(2/4)= 1.00002Yes2 No6Yes2 NoPlayTennisNo TennisTemperature:= Mild8Yes4 No0.9183熵的公式熵的公式:基于熵的划分划分后右边的熵：划分后右边的熵：6/8*𝑙𝑜𝑔2(6/8)2/8*𝑙𝑜𝑔2(2/8)= 0.81132Yes2 No6Yes2 NoPlayTennisTemperature:= Mild8Yes4 No0.9183No Tennis1.0000熵的公式熵的公式:基于熵的划分熵的变化：
13、熵的变化：0.9183 4/121.0000 8/120.8113= 0.04412Yes2 No6Yes2 NoTemperature:= Mild8Yes4 No0.9183No Tennis1.0000PlayTennis0.8113熵的公式熵的公式 基于熵的划分允许继续基于熵的划分允许继续分裂下去分裂下去 最终达到叶子节点同质最终达到叶子节点同质的目标的目标 为什么熵可以达到这一为什么熵可以达到这一目标，而分类错误不行？目标，而分类错误不行？2Yes2 No6Yes2 NoPlayTennisNo TennisTemperature:= Mild8Yes4 No基于熵的划分 分类错误是
14、一个平坦函数，分类错误是一个平坦函数，在中心点达到最大值在中心点达到最大值分类错误 vs 熵0.00.5Purity1.0Classification ErrorError 分类错误是一个平坦函数，分类错误是一个平坦函数，在中心点达到最大值在中心点达到最大值 中心点表示的是中心点表示的是50/50的的歧义划分歧义划分分类错误 vs 熵0.00.5Purity1.0Classification ErrorError 分类错误是一个平坦函数，分类错误是一个平坦函数，在中心点达到最大值在中心点达到最大值 中心点表示的是中心点表示的是50/50的的歧义划分歧义划分 分类指标偏向于远离中心分类指标偏向于
15、远离中心点的结果点的结果分类错误 vs 熵0.00.5Purity1.0Classification ErrorError 熵具有相同的最大值，但熵具有相同的最大值，但是弯曲的曲线是弯曲的曲线0.00.5Purity1.0Classification Error Cross EntropyError分类错误 vs 熵 熵具有相同的最大值，但熵具有相同的最大值，但是弯曲的曲线是弯曲的曲线 曲度使得分裂可以继续到曲度使得分裂可以继续到叶子节点纯了为止叶子节点纯了为止0.00.5Purity1.0Classification Error Cross EntropyError分类错误 vs 熵 熵具有
16、相同的最大值，但熵具有相同的最大值，但是弯曲的曲线是弯曲的曲线 曲度使得分裂可以继续到曲度使得分裂可以继续到叶子节点纯了为止叶子节点纯了为止 为什么？为什么？0.00.5Purity1.0Classification Error Cross EntropyError分类错误 vs 熵 使用分类错误，函数是平坦的使用分类错误，函数是平坦的分裂带来的信息增益分裂带来的信息增益 使用分类错误，函数是平坦的使用分类错误，函数是平坦的分裂带来的信息增益 使用分类错误，函数是平坦的使用分类错误，函数是平坦的 最终的平均分类错误很有可能最终的平均分类错误很有可能与父节点的分类错误相等与父节点的分类错误相等分
17、裂带来的信息增益 使用分类错误，函数是平坦的使用分类错误，函数是平坦的 最终的平均分类错误很有可能最终的平均分类错误很有可能与父节点的分类错误相等与父节点的分类错误相等 从而导致提前停止从而导致提前停止 使用熵，函数有个“鼓包”使用熵，函数有个“鼓包”分裂带来的信息增益分裂带来的信息增益 使用熵，函数有个“鼓包”使用熵，函数有个“鼓包” 使得子节点的平均熵少于父使得子节点的平均熵少于父节点的熵节点的熵分裂带来的信息增益 使用熵，函数有个“鼓包”使用熵，函数有个“鼓包” 使得子节点的平均熵少于父使得子节点的平均熵少于父节点的熵节点的熵 从而产生信息增益，使得分从而产生信息增益，使得分裂可以继续裂
18、可以继续 实际中，常使用基尼指数实际中，常使用基尼指数做分裂做分裂基尼指数0.01.0Classification Error Cross EntropyGini IndexError0.5Purity𝐺𝑖𝑛𝑖 t = 𝑖=1𝑛𝑝 𝑖 𝑡1 𝑝 𝑖 𝑡= 1 𝑖=1𝑛𝑝(𝑖|𝑡)2 实际中，常使用基尼指数实际中，常使用基尼指数
19、做分裂做分裂 其函数类似于熵其函数类似于熵-也有也有“鼓包”“鼓包”基尼指数0.01.0Classification Error Cross EntropyGini IndexError0.5Purity𝐺𝑖𝑛𝑖 t = 𝑖=1𝑛𝑝 𝑖 𝑡1 𝑝 𝑖 𝑡= 1 𝑖=1𝑛𝑝(𝑖|𝑡)2 实际中，常使用基尼指数实际中，常使用基尼指
20、数做分裂做分裂 其函数类似于熵其函数类似于熵-也有也有“鼓包”“鼓包” 没有对数没有对数基尼指数0.01.0Classification Error Cross EntropyGini IndexError0.5Purity𝐺𝑖𝑛𝑖 t = 𝑖=1𝑛𝑝 𝑖 𝑡1 𝑝 𝑖 𝑡= 1 𝑖=1𝑛𝑝(𝑖|𝑡)2 问题：决策树容易过拟合
21、问题：决策树容易过拟合 数据微小的变化能对预数据微小的变化能对预测结果产生较大的影响测结果产生较大的影响-high variance决策树高方差（high variance） 问题：决策树容易过拟合问题：决策树容易过拟合 数据微小的变化能对预数据微小的变化能对预测结果产生较大的影响测结果产生较大的影响-high variance 解决方案解决方案: 修剪决策树修剪决策树修剪决策树 问题：决策树容易过拟合问题：决策树容易过拟合 数据微小的变化能对预数据微小的变化能对预测结果产生较大的影响测结果产生较大的影响-high variance 解决方案解决方案: 修剪决策树修剪决策树 预剪枝预剪枝 后剪
22、枝后剪枝修剪决策树 在在决策树构建过程中决策树构建过程中，依据预先，依据预先设定的条件，提前终止树的生长。设定的条件，提前终止树的生长。 Scikit-Learn中：中： 决策树的最大深度决策树的最大深度（max_depth） 决策树的最大叶子数决策树的最大叶子数（max_leaf_nodes） 可分裂节点应包含的最少样例可分裂节点应包含的最少样例数（数（min_samples_split） 叶节点应包含的最少样例数叶节点应包含的最少样例数（min_samples_leaf） 不纯度减少的最小量不纯度减少的最小量（min_impurity_decrease）预剪枝 在在决策树构建完成之后决策树
23、构建完成之后进行剪枝，进行剪枝，得到一棵简化的树。得到一棵简化的树。 自底向上地考察每个非叶节点，自底向上地考察每个非叶节点，如果将其子树剪去，成为一个叶如果将其子树剪去，成为一个叶节点，能带来决策树泛化性能提节点，能带来决策树泛化性能提升，则将该子树替换为叶节点升，则将该子树替换为叶节点 错误率错误率降低剪枝降低剪枝 (reduced-error pruning, REP) 后剪枝 Scikit-Learn从从0.22版本开始版本开始实实现现了代价了代价复杂复杂度剪枝（度剪枝（cost-complexity, CCP）策略）策略𝑇𝑡为子树中叶节点的个数C(&#
24、119879;𝑡)和C(t)分别是剪枝前后该子树的预测错误（或者所有叶节点的不纯度之和） 计算树计算树中每个非叶节点的中每个非叶节点的 值值, 然后循环剪掉具有最小然后循环剪掉具有最小 值的值的子子树树, 直到最小直到最小 值大于用户预先值大于用户预先给定的参数值给定的参数值ccp_alpha 为止为止。后剪枝 =)C(t) C(𝑇𝑡𝑇𝑡 1 一般一般情形下，后剪枝决策树的欠情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝训练于预剪枝决策树。但后剪枝训练时间比
25、未剪枝和预剪枝决策树都时间比未剪枝和预剪枝决策树都要大得多要大得多。预剪枝 vs. 后剪枝 容易实现和解释容易实现和解释 “if then else”逻辑”逻辑 可以处理任何数据类型可以处理任何数据类型 二值二值, 序数序数, 连续值连续值 无需数据预处理和缩放无需数据预处理和缩放决策树的优点导入包含分类方法的类：导入包含分类方法的类：from sklearn.tree import DecisionTreeClassifier创建该类的一个对象：创建该类的一个对象：DTC = DecisionTreeClassifier(criterion=gini,max_features=10, max
26、_depth=5)拟合训练数据，并预测：拟合训练数据，并预测：DTC = DTC.fit(X_train, y_train)y_predict = DTC.predict(X_test)决策树分类器的语法导入包含分类方法的类：导入包含分类方法的类：from sklearn.tree import DecisionTreeClassifier创建该类的一个对象：创建该类的一个对象：DTC = DecisionTreeClassifier(criterion=gini,max_features=10, max_depth=5)拟合训练数据，并预测：拟合训练数据，并预测：DTC = DTC.fit(
27、X_train, y_train)y_predict = DTC.predict(X_test)决策树分类器的语法决策树决策树参数参数http:/scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html导入包含分类方法的类：导入包含分类方法的类：from sklearn.tree import DecisionTreeClassifier创建该类的一个对象：创建该类的一个对象：DTC = DecisionTreeClassifier(criterion=gini,max_features
28、=10, max_depth=5)拟合训练数据，并预测：拟合训练数据，并预测：DTC = DTC.fit(X_train, y_train)y_predict = DTC.predict(X_test)决策树分类器的语法用交叉验证来调参，使用用交叉验证来调参，使用DecisionTreeRegressor做回归做回归criterion测试条件选择标准测试条件选择标准DecisionTreeClassifier的缺省值是“gini”，即用基尼指数作为衡量指标，也可以是“entropy”，即使用熵作为衡量指标；DecisionTreeRegressor的缺省值是“mse”，即使用均方差作为衡量指标
29、，也可以是“mae”，即使用平均绝对值误差作为衡量指标。splitter测试条件选择策略测试条件选择策略缺省值是“best”，即选取最优划分条件，也可以是“random”，表示随机选取划分条件。max_depth决策树的最大深度决策树的最大深度缺省值是没有深度限制。设置树的最大深度是为了防止过拟合。min_samples_split节点可分裂的最少样例数节点可分裂的最少样例数缺省值是2。一个节点可以进一步分裂必须最少包含min_samples_split个样例。为了防止过拟合，可以增大此值。min_samples_leaf叶子节点的最少样例数叶子节点的最少样例数缺省值是1。一个叶子节点必须最少
30、包含min_samples_leaf个样例。如果增大此值，可以及早停止过于细分叶子节点，防止过拟合。max_features选择测试条件可考虑的最大特征数选择测试条件可考虑的最大特征数缺省值是没有最大特征数的限制，即可以考虑数据集中的所有特征。减少考虑的特征数，一来可以减少决策树的生成时间；二来可以增大决策树的随机性，有利于提升随机森林等集成学习模型的效果。max_leaf_nodes最大叶节点个数最大叶节点个数缺省值是不限制叶节点的个数。它和树的最大深度类似，可以防止过拟合。min_impurity_decrease最小不纯度减少量最小不纯度减少量如果用某一测试条件划分节点带来的不纯度的减少量小于这个阈值，则不用此测试条件划分该节点。演示第11章-决策树.ipynb
