11-决策树.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2020/1/12,#,决策树,王秋月,中国人民大学信息学院,K,近邻：,模型就是训练数据,拟合训练数据很快,只是存储数据,预测比较慢,需要计算大量的距离,判定边界较灵活,Y,X,不同分类器的特点,逻辑回归：,模型就是参数,拟合训练数据可能较慢,必须找到最优参数,预测较快,计算期望值,判定边界较简单，缺乏灵活性,X,0.0,1.0,Proba,b,i,l,it,y,0.5,1,=,1+,(,0,+,1,+,),不同分类器的特点,Day,Outlook,Temperature,Humidity,Wind,PlayTennis,D1,Sunny,Hot,High,Weak,No,D2,Sunny,Hot,High,Strong,No,D3,Overcast,Hot,High,Weak,Yes,D4,Rain,Mild,High,Weak,Yes,D5,Rain,Cool,Normal,Weak,Yes,D6,Rain,Cool,Normal,Strong,No,D7,Overcast,Cool,Normal,Strong,Yes,D8,Sunny,Mild,High,Weak,No,D9,Sunny,Cool,Normal,Weak,Yes,D10,Rain,Mild,Normal,Weak,Yes,D11,Sunny,Mild,Normal,Strong,Yes,D12,Overcast,Mild,High,Strong,Yes,D13,Overcast,Hot,Normal,Weak,Yes,D14,Rain,Mild,High,Strong,No,决策树介绍,想要根据,temperature,humidity,wind,outlook,来预测是否打网球,决策树介绍,想要根据,temperature,humidity,wind,outlook,来预测是否打网球,使用特征来划分数据，进而预测结果,决策树介绍,Play,Tennis,No,Tennis,Temperature:,=,Mild想要根据,temperature,humidity,wind,outlook,来预测是否打网球,使用特征来划分数据，进而预测结果,决策树介绍,Play,Tennis,No,Tennis,Temperature:,=,Mild,No,de,s,Leaves,想要根据,temperature,humidity,wind,outlook,来预测是否打网球,使用特征来划分数据，进而预测结果,决策树介绍,Play,Tennis,No,Tennis,No,Tennis,Temperature:,=,Mild,Humidity:,=,Normal,No,de,s,Leaves,想要根据,temperature,humidity,wind,outlook,来预测是否打网球,使用特征来划分数据，进而预测结果,预测类别结果的,决策树,决策树介绍,Play,Tennis,No,Tennis,No,Tennis,Temperature:,=,Mild,Humidity:,=,Normal,预测连续值的回归树,例如：使用喜马拉雅山脉的坡度和高度,预测平均降水量（连续值）,48.50,in.,13.67,in,.,55.42,in.,Elevation:,7900,ft.,S,l,o,p,e:,2.5,预测连续值的回归树,例如：使用喜马拉雅山脉的坡度和高度,预测平均降水量（连续值）,48.50,in.,1367,in.,55.42,in.,Elevation:,7900,ft.,S,l,o,p,e:,=,Mild,No,Tennis,Play,Tennis,Lea,ve,s,创建最优决策树,使用贪婪搜索：每一步寻找最优划分,什么是最优划分？,Temperature:,=,Mild,No,Tennis,Play,Tennis,Lea,ve,s,创建最优决策树,使用贪婪搜索：每一步寻找最优划分,什么是最优划分？,最大化不纯度减小量的划分,Temperature:,=,Mild,No,Tennis,Play,Tennis,Lea,ve,s,创建最优决策树,使用贪婪搜索：每一步寻找最优划分,什么是最优划分？,最大化不纯度减小量的划分,如何度量不纯度？,Temperature:,=,Mild,No,Tennis,Play,Tennis,Lea,ve,s,创建最优决策树,分类错误公式：,2,Yes,2,No,6,Yes,2,No,Play,Tennis,8,Yes,4,No,No,Tennis,Temperature:,=,Mild,基于分类错误的划分,分类错误公式：,基于分类错误的划分,划分前的分类错误：,1,8/12,=,0.3333,2,Yes,2,No,6,Yes,2,No,Play,Tennis,8,Yes,4,No,No,Tennis,Temperature:,=,Mild,分类错误公式：,基于分类错误的划分,划分后左边的分类错误：,1,2/4,=,0.,5000,2,Yes,2,No,6,Yes,2,No,Play,Tennis,8,Yes,4,No,No,Tennis,Temperature:,=,Mild,0.3333,分类错误公式：,基于分类错误的划分,划分后右边的分类错误：,1,6/8,=,0.,2500,2,Yes,2,No,6,Yes,2,No,Play,Tennis,8,Yes,4,No,Temperature:,=,Mild,0.3333,No,Tennis,0.5000,分类错误公式：,基于分类错误的划分,分类错误的变化：,0.3333,4/12,05000,8/12,0.2500,2,Yes,2,No,No,Tennis,0.5000,Play,Tennis,0.2500,6,Yes,2,No,8,Yes,4,No,Temperature:,=,Mild,0.3333,分类错误公式：,基于分类错误的划分,分类错误的变化：,0.3333,4/12,0.5000,8/12,0.2500,=0,2,Yes,2,No,No,Tennis,0.5000,Play,Tennis,0.2500,6,Yes,2,No,8,Yes,4,No,Temperature:,=,Mild,0.3333,使用分类错误，分裂停止,问题：叶子节点仍然不是同质的,尝试另外一个性能指标？,2,Yes,2,No,6,Yes,2,No,Play,Tennis,8,Yes,4,No,No,Tennis,Temperature:,=,Mild,基于分类错误的划分,2,Yes,2,No,6,Yes,2,No,Play,Tennis,8,Yes,4,No,No,Tennis,Temperature:,=,Mild,基于熵的划分,熵的公式：,熵的公式,:,基于熵的划分,2,Yes,2,No,6,Yes,2,No,Play,Tennis,No,Tennis,Temperature:,=,Mild,8,Yes,4,No,划分前的熵：,8/12,*,2,(,8/12,),4/12,*,2,(,4/12,),=0.9183,基于熵的划分,划分后左边的熵：,2/4,*,2,(,2/4,),2/4,*,2,(,2/4,),=,1,.,0000,2,Yes,2,No,6,Yes,2,No,Play,Tennis,No,Tennis,Temperature:,=,Mild,8,Yes,4,No,0.9183,熵的公式,:,基于熵的划分,划分后右边的熵：,6/8,*,2,(,6/8,),2/8,*,2,(,2/8,),=,0,.,8113,2,Yes,2,No,6,Yes,2,No,Play,Tennis,Temperature:,=,Mild,8,Yes,4,No,0.9183,No,Tennis,1.0000,熵的公式,:,基于熵的划分,熵的变化：,0.9183,4/12,1.0000,8/12,0.8113,=0.0441,2,Yes,2,No,6,Yes,2,No,Temperature:,=,Mild,8,Yes,4,No,0.9183,No,Tennis,1.0000,Play,Tennis,0.8113,熵的公式,基于熵的划分允许继续分裂下去,最终达到叶子节点同质的目标,为什么熵可以达到这一目标，而分类错误不行？,2,Yes,2,No,6,Yes,2,No,Play,Tennis,No,Tennis,Temperature:,=,Mild,8,Yes,4,No,基于熵的划分,分类错误是一个平坦函数，在中心点达到最大值,分类错误,vs,熵,0.0,0.,5,P,u,r,i,t,y,1.,0,Classification,Error,Error,分类错误是一个平坦函数，在中心点达到最大值,中心点表示的是,50/50,的歧义划分,分类错误,vs,熵,0.0,0.,5,P,u,r,i,t,y,1.,0,Classification,Error,Error,分类错误是一个平坦函数，在中心点达到最大值,中心点表示的是,50/50,的歧义划分,分类指标偏向于远离中心点的结果,分类错误,vs,熵,0.0,0.,5,P,u,r,i,t,y,1.,0,Classification,Error,Error,熵具有相同的最大值，但是弯曲的曲线,0.0,0.,5,P,u,r,i,t,y,1.,0,Classification,Error,Cross,Entropy,Error,分类错误,vs,熵,熵具有相同的最大值，但是弯曲的曲线,曲度使得分裂可以继续到叶子节点纯了为止,0.0,0.,5,P,u,r,i,t,y,1.,0,Classification,Error,Cross,Entropy,Error,分类错误,vs,熵,熵具有相同的最大值，但是弯曲的曲线,曲度使得分裂可以继续到叶子节点纯了为止,为什么？,0.0,0.,5,P,u,r,i,t,y,1.,0,Classification,Error,Cross,Entropy,Error,分类错误,vs,熵,使用分类错误，函数是平坦的,分裂带来的信息增益,分裂带来的信息增益,使用分类错误，函数是平坦的,分裂带来的信息增益,使用分类错误，函数是平坦的,最终的平均分类错误很有可能与父节点的分类错误相等,分裂带来的信息增益,使用分类错误，函数是平坦的,最终的平均分类错误很有可能与父节点的分类错误相等,从而导致提前停止,使用熵，函数有个“鼓包”,分裂带来的信息增益,分裂带来的信息增益,使用熵，函数有个“鼓包”,使得子节点的平均熵少于父节点的熵,分裂带来的信息增益,使用熵，函数有个“鼓包”,使得子节点的平均熵少于父节点的熵,从而产生信息增益，使得分裂可以继续,实际中，常使用基尼指数做分裂,基尼指数,0.0,1.,0,Classification,Error,Cross,Entropy,Gini,Index,Error,0.,5,Purity,实际中，常使用基尼指数做分裂,其函数类似于熵,-,也有“鼓包”,基尼指数,0.0,1.,0,Classification,Error,Cross,Entropy,Gini,Index,Error,0.,5,Purity,实际中，常使用基尼指数做分裂,其函数类似于熵,-,也有“鼓包”,没有对数,基尼指数,0.0,1.,0,Classification,Error,Cross,Entropy,Gini,Index,Error,0.,5,Purity,问题：决策树容易过拟合,数据微小的变化能对预测结果产生较大的影响,-,high variance,决策树高方差（,high variance,）,问题：决策树容易过拟合,数据微小的变化能对预测结果产生较大的影响,-,high variance,解决方案,:,修剪决策树,修剪决策树,问题：决策树容易过拟合,数据微小的变化能对预测结果产生较大的影响,-,high variance,解决方案,:,修剪决策树,预剪枝,后剪枝,修剪决策树,在,决策树构建过程中,，依据预先设定的条件，提前终止树的生长。,Scikit-Learn,中：,决策树的最大深度（,max_depth,）,决策树的最大叶子数（,max_leaf_nodes,）,可分裂节点应包含的最少样例数（,min_samples_split,）,叶节点应包含的最少样例数（,min_samples_leaf,）,不纯度减少的最小量（,min_impurity_decrease,）,预剪枝,在,决策树构建完成之后,进行剪枝，得到一棵简化的树。,自底向上地考察每个非叶节点，如果将其子树剪去，成为一个叶节点，能带来决策树泛化性能提升，则将该子树替换为叶节点,错误率降低剪枝,(reduced-error pruning,REP),后剪枝,Scikit-Learn,从,0.22,版本开始实现了代价复杂度剪枝（,cost-complexity,CCP,）策略,为子树中叶节点的个数,和,分别是剪枝前后该子树的预测错误（或者所有叶节点的不纯度之和）,计算树中每个非叶节点的,值,然后循环剪掉具有最小,值的子树,直到最小,值大于用户预先给定的参数值,ccp_alpha,为止。,后剪枝,一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝训练时间比未剪枝和预剪枝决策树都要大得多。,预剪枝,vs.,后剪枝,容易实现和解释,“,if then else,”逻辑,可以处理任何数据类型,二值,序数,连续值,无需数据预处理和缩放,决策树的优点,导入包含分类方法的类：,from sklearn.tree import,DecisionTreeClassifier,创建该类的一个对象：,DTC,=,DecisionTreeClassifier,(criterion=gini,max_features=10,max_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,(X_train,y_train),y_predict=,DTC,.,predict,(X_test),决策树分类器的语法,决策树参数,scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html,导入包含分类方法的类：,from sklearn.tree import,DecisionTreeClassifier,创建该类的一个对象：,DTC,=,DecisionTreeClassifier,(criterion=gini,max_features=10,max_depth=5),拟合训练数据，并预测：,DTC,=,DTC,.,fit,(X_train,y_train),y_predict=,DTC,.,predict,(X_test),决策树分类器的语法,用交叉验证来调参，使用,DecisionTreeRegressor,做回归,criterion,测试条件选择标准,DecisionTreeClassifier,的缺省值是“,gini,”，即用基尼指数作为衡量指标，也可以是“,entropy,”，即使用熵作为衡量指标；,DecisionTreeRegressor,的缺省值是“,mse,”，即使用均方差作为衡量指标，也可以是“,mae,”，即使用平均绝对值误差作为衡量指标。,splitter,测试条件选择策略,缺省值是“,best,”，即选取最优划分条件，也可以是“,random,”，表示随机选取划分条件。,max_depth,决策树的最大深度,缺省值是没有深度限制。设置树的最大深度是为了防止过拟合。,min_samples_split,节点可分裂的最少样例数,缺省值是,2,。一个节点可以进一步分裂必须最少包含,min_samples_split个样例。为了防止过拟合，可以增大此值。,min_samples_leaf,叶子节点的最少样例数,缺省值是,1,。一个叶子节点必须最少包含,min_samples_leaf,个样例。如果增大此值，可以及早停止过于细分叶子节点，防止过拟合。,max_features,选择测试条件可考虑的最大特征数,缺省值是没有最大特征数的限制，即可以考虑数据集中的所有特征。减少考虑的特征数，一来可以减少决策树的生成时间；二来可以增大决策树的随机性，有利于提升随机森林等集成学习模型的效果。,max_leaf_nodes,最大叶节点个数,缺省值是不限制叶节点的个数。它和树的最大深度类似，可以防止过拟合。,min_impurity_decrease,最小不纯度减少量,如果用某一测试条件划分节点带来的不纯度的减少量小于这个阈值，则不用此测试条件划分该节点。,演示,第,11,章,-,决策树,.ipynb,