《数据仓库与数据挖掘》课件 第9章 决策树与随机森林

第9章

决策树与随机森林本章主要内容9.1决策树9.2回归树9.3随机森林9.4课后习题9.1决策树9.1.1决策树的原理决策树：用于解决分类问题生活中的例子：母亲给女儿介绍一个男朋友，女儿根据各种信息判断是否同意去相亲叶子节点中间节点根节点9.1.2如何建立一棵决策树思路一：基于信息熵建树ID3、C4.5CART思路二：基于基尼系数建树9.1.2如何建立一棵决策树——信息熵信息熵是用来衡量一个随机变量出现的期望值。信息的不确定性越大，熵的值也就越大，出现的各种情况也就越多。例如“下一届国际足联男子世界杯冠军”这个句话的信息熵就大于“下一届国际乒联男子世界杯冠军”，因为前者在事件没有发生时的不确定性很高，冠军可能的情况包括法国队、巴西队、阿根廷队、德国队、英格兰队、意大利队......，而后者在事件没有发生时的不确定性很低，冠军可能的情况只有中国队。信息熵的计算公式为：

，其中X是所有发生的可能性，x是某一种可能性。以“2022年国际足联男子世界杯冠军”这个事件为例，假设共有8支队伍有可能夺冠，每支队伍夺冠的可能性都是1/8。则“2022年国际足联男子世界杯冠军”这件事的信息熵为：决策树的两种子方法ID3和C4.5就是使用信息熵作为建树的理论依据。9.1.2如何建立一棵决策树——ID3建树过程

ID3使用了基于信息熵计算的信息增益方法，信息增益公式为：

其中Gain(X)表示某一个特征的信息增益，ci表示第i中分类，xi表示某一特征的第i种数值步骤1：info(c)部分计算，即针对标签（是否买电脑）的信息熵计算：买电脑的样本为9，即买电脑的概率是9/14，不买电脑的概率是5/14。因此：info(c)=-9/14log2(9/14)-5/14log2(5/14)≈0.9409.1.2如何建立一棵决策树——ID3建树过程

ID3使用了基于信息熵计算的信息增益方法，信息增益公式为：

其中Gain(X)表示某一个特征的信息增益，ci表示第i中分类，xi表示某一特征的第i种数值步骤2：info(c|年龄)的计算，即针对年龄特征和标签的条件信息熵的计算：在年龄特征，一共分为三种情况：<30、30-40、>40

情况1：当年龄<30时，一共有5个样本，其中2个买电脑了，3个没买，即info(c|x<30)=-2/5log2(2/5)-3/5log2(3/5)

情况2：当30<=年龄<=40时，一共有4个样本，其中3个买电脑了，1个没买，即info(c|30<=x<=30)=-3/4log2(3/4)-1/4log2(1/4)情况3：当年龄>40时，一共有5个样本，其中3个买电脑了，2个没买，即info(c|x>40)=-3/5log2(3/5)-2/5log2(2/5)9.1.2如何建立一棵决策树——ID3建树过程

ID3使用了基于信息熵计算的信息增益方法，信息增益公式为：

其中Gain(X)表示某一个特征的信息增益，ci表示第i中分类，xi表示某一特征的第i种数值步骤3：计算Gain(年龄)Gain(年龄)=

info(c)

-5/14*info(c|x<30)

-4/14*info(c|30<=x<=40)

-5/14*info(c|x>40)

≈0.1509.1.2如何建立一棵决策树——ID3建树过程

ID3使用了基于信息熵计算的信息增益方法，信息增益公式为：

其中Gain(X)表示某一个特征的信息增益，ci表示第i中分类，xi表示某一特征的第i种数值步骤4：根据前三步计算方法，分别计算出：

Gain(年龄)

≈0.150

Gain(收入)

≈0.090

Gain(学生)

≈0.016

Gain(信用)

≈0.048其中“年龄”的信息增益是最大的9.1.2如何建立一棵决策树——ID3建树过程

ID3使用了基于信息熵计算的信息增益方法，信息增益公式为：

其中Gain(X)表示某一个特征的信息增益，ci表示第i中分类，xi表示某一特征的第i种数值第五步：根据第四步结果：选择信息增益最大的特征“年龄”作为根节点根据年龄将样本进行了区分：年龄小于30的节点落在了左侧面年龄在30到40之间的节点落在了中间年龄大于40的节点落在了右侧。9.1.2如何建立一棵决策树——ID3建树过程

9.1.2如何建立一棵决策树——ID3建树过程

针对这个表继续计算，每个特征的信息增益，Gain(收入)≈0.971Gain(学生)≈0.420Gain(信用)≈0.020。因此使用“收入”进行下一步分裂此次判断已经有了最终结果，即“买”或“不买”，这就是叶子节点。其他节点以此类推9.1.2如何建立一棵决策树——C4.5建树过程ID3算法并不是完美的，在上面的例子中将“年龄”、“收入”、“学生”、“信用”作为特征构建决策树。如果将“序号”也含在特征中，看看“序号”的信息增益。如果将“序号”也含在特征中，看看“序号”的信息增益。info(c)≈0.940Info(c|x=1)=-1/1*log2(1/1)-0/1*log2(0/1)=0Info(c|x=2)=-1/1*log2(1/1)-0/1*log2(0/1)=0Info(c|x=3)=-1/1*log2(1/1)-0/1*log2(0/1)=0......Info(c|x=14)=-1/1*log2(1/1)-0/1*log2(0/1)=0所以Gain(序号)=info(c)-0≈0.940这时发现序号的信息增益最大，应该首先以序号为根节点进行判断，可是这没有意义，序号列信息增益大的原因完全是因为序号的种类“太琐碎了”，从而导致条件信息熵是0。9.1.2如何建立一棵决策树——C4.5建树过程为了解决这个中由于某一个属性取值种类太多造成的问题，又引入了信息增益率的概念。信息增益率的公式为：GainRatio(X)=Gain(X)/SplitInfo(X)。其中SplitInfo(X)是针对X特征本身的信息熵计算SplitInfo(年龄)，年龄3种可能的概率分别是

小于30岁：5/1430到40岁：4/14大于40岁：5/14

则SplitInfo(年龄)=-5/14*log2(5/14)-4/14*log2(4/14)-5/14*log2(5/14)≈0.189由ID3计算过程可知：Gain(年龄)≈0.150所以GainRatio(年龄)=0.150/0.189≈0.7949.1.2如何建立一棵决策树——C4.5建树过程

序号列的信息增益率呢？序号列一共有14种取值，每种取值概率都是1/14，因此SplitInfo(序号)=-1/14*log2(1/14)-1/14*log2(1/14)......-1/14*log2(1/14)≈3.8由前面（PPT第12页）计算可知：Gain(序号)=0.940所以GainRatio(序号)=0.940/3.8≈0.247选择信息增益率大的特征作为优选的判断特征。年龄的信息增益率（0.794）大于序号的信息增益率（0.247)，因此年龄列比序号列更适合优先作为判断节点。其他特征的信息增益率及比较方法相同，每次迭代选取信息增益率最大的特征作为判断属性，建立决策树，这种算法叫做C4.5算法。现在选用信息熵作为建树依据的方法多数都是选择C4.5作为默认算法。9.1.2如何建立一棵决策树——CART建树过程除了信息熵，基尼系数（Gini）也可以作为建树的依据，基尼系数也可以体现出事物的不确定性（不纯度）。基尼系数的公式：其中I是所有的可能，i是某一种可能。某一属性Gini系数增益的公式为：针对“年龄”列进行统计：

Gini(买|年龄)=1-(2/8)2

-(3/8)2

-(3/8)2

≈0.656Gini(不买|年龄)=1-(3/6)2

-(1/6)2

-(2/6)2

≈0.611Gain(年龄)=9/14*Gini(买|年龄)+5/14*Gini(不买|年龄)

≈0.6409.1.2如何建立一棵决策树——CART建树过程基尼系数的公式：其中I是所有的可能，i是某一种可能。某一列Gini系数增益的公式为：针对“收入”列进行统计：Gini(买|收入)=1-(2/9)2-(5/9)2-(2/9)2≈0.592Gini(不买|收入)=1-(2/5)2-(1/5)2-(2/5)2≈0.64Gain(收入)=9/14*Gini(买|收入)+5/14*Gini(不买|收入)

=9/14*0.592+5/14*0.64

≈0.6099.1.2如何建立一棵决策树——CART建树过程基尼系数的公式：其中I是所有的可能，i是某一种可能。某一列Gini系数增益的公式为：针对“学生”列进行统计：Gini(买|学生)=1-(5/9)2-(4/9)2≈0.494Gini(不买|学生)=1-(2/5)2-(3/5)2≈0.48Gain(学生)=9/14*Gini(买|学生)+5/14*Gini(不买|学生)≈0.4899.1.2如何建立一棵决策树——CART建树过程基尼系数的公式：其中I是所有的可能，i是某一种可能。某一列Gini系数增益的公式为：针对“信用”列进行统计：Gini(买|信用)=1-(3/9)2-(6/9)2≈0.444Gini(不买|信用)=1-(3/5)2-(2/5)2≈0.48Gain(信用)=9/14*Gini(买|信用)+5/14*Gini(不买|信用)

≈0.4579.1.2如何建立一棵决策树——CART建树过程选择基尼增益小的特征作为判断特征，显然“信用”的信息增益系数最小，表示不纯度最小，所以通过信用特征来判断的结果能相对较“纯”。Gain(年龄)

≈0.640Gain(收入)≈0.609Gain(学生)≈0.489Gain(信用)≈0.457各子节点依据以上方式继续迭代9.1.2如何建立一棵决策树——信息熵VS基尼系数无论是信息熵、信息增益、信息增益率还是基尼系数，中心思想都是找到判断事务条件的不纯度。越“纯”的条件，判断得越“靠谱”。在实际使用中，信息熵和基尼系数的效果基本相同。信息熵的计算比基尼系数缓慢一些，因为基尼系数的计算不涉及对数。另外，因为信息熵对不纯度更加敏感，决策树的生长会更加“精细”，但更容易过拟合，但当模型拟合程度不足的时候，可以使用信息熵。实战中一般先选基尼系数，效果不好再换成信息熵9.1.3sklearn中的决策树实现#第一步：导入数据#导入numpy和pandas数据包importnumpyasnpimportpandasaspd#从boston_lishi.csv文件中导入原始数据df=pd.read_csv(r'E:\ruxian_lishi.csv',index_col='Patien')#X为原始数据中不包括target列部分，是由历史数据中“非结果列”组成的数据X=df.loc[:,(df.columns!='target')]#Y为原始数据中target列部分，是由历史数据中“结果列”组成的数据Y=df.loc[:,df.columns=='target']9.1.3sklearn中的决策树实现#第二步：数据预处理#缺失值处理df.dropna()#其他数据预处理将在第6次课介绍9.1.3sklearn中的决策树实现#第三步,建模#将历史数据按照8：2的比例分随机分为训练集和测试集fromsklearn.model_selectionimporttrain_test_splitXtrain,Xtest,Ytrain,Ytest=train_test_split(X,Y,test_size=0.2,random_state=420)#导入决策树工具包fromsklearn.treeimportDecisionTreeClassifierasDT#创建模型clf=DT()#训练模型clf.fit(Xtrain,Ytrain)9.1.3sklearn中的决策树实现#第四步，用测试集检验模型预测效果#使用predict方法，根据Xtest预测测试集的结果result=clf.predict(Xtest)#将测试集真实结果和预测结果进行对比df=pd.DataFrame({'真实结果':Ytest.loc[:,'target'],'预测结果':pd.Series(result,index=Ytest.index)})print(df)9.1.3sklearn中的决策树实现#第四步，用测试集检验模型预测效果#可以使用一些指标来评价模型表现，例如使用R2值评价多元线性回归score=clf.score(Xtest,Ytest)print(score)#其他指标（混淆矩阵、recall、AUC值等）与逻辑回归中的实现方法完全一致，不再赘述9.1.3sklearn中的决策树实现——决策树模型的重要属性#feature_importances：查看每个特征在构建决策树时的重要程度。实现方法如下：#查看每个特征的重要程度df=pd.read_csv(r'E:\ruxian_lishi.csv',index_col='Patien')#feature_importances_返回建模时，每个特征的重要程度fi=pd.Series(clf.feature_importances_,index=df.columns[0:-1])print(fi)9.1.4决策树调参——决策树的剪枝什么是剪枝？如果数据够复杂，建立的决策树也会很复杂，各种判断条件和判断结果“枝繁叶茂、层出不穷”，这样做会出现连个问题。第一、过拟合，因为训练得“太细”，导致整个模型过分依赖训练数据；第二、计算性能低，因为树结构太复杂，计算时需要占用大量资源，导致计算效率下降。为了避免树结构过于复杂，可以采用剪枝的方法。剪枝顾名思义，就是删除树中的一部分节点和叶子。左图为剪枝前的决策树，右图为剪之后的决策树。9.1.4决策树调参——决策树中可以实现剪枝的参数max_depth，参数内容是整数。max_depth就是指定树的最大深度，超过这个深度的中间节点和叶子节点统统砍掉，砍掉部分将变成一个叶子节点，这个节点的分类结果是砍掉部分样本数最多的分类。调参时也可以使用学习曲线+交叉验证的方法。min_samples_split，内容是整数，也是一个剪枝参数，一个节点必须要包含至少min_samples_split个样本，否则不再进行分枝。还有一个类似的参数：min_samples_leaf，也是一个剪枝参数，一个节点在分枝后的每个子节点都必须包含至少min_samples_leaf个训练样本，否则不会在分枝，注意min_samples_leaf既可以是一个整数，表示样本个数，也可以是一个浮点小数，表示样本的比例。调参时也可以使用学习曲线+交叉验证的方法。如果说max_depth是在原有树基础上大刀阔如的砍掉太深的节点，那min_samples_split和min_samples_leaf就是在建树的过程中就小心翼翼的把握着树的结构，所以用max_depth剪枝的方法叫后剪枝，即在建树后剪枝；min_samples_split和min_samples_leaf叫先剪枝，即在建树的过程中就控制树的结构。二者可以配合使用。9.1.4决策树调参——决策树其他重要参数criterion，参数内容是是两个可选数值：gini（基尼系数）和entropy（信息熵），也就是之前介绍的两种建树方法，默认值是基尼系数。在实战中，一般先用基尼系数，如果结果不满意，再换成信息熵。random_state，参数内容是数值型。在使用维度较高（特征较多）的数据建树时，sklearn并不是将所有的特征都纳入建树过程，而是随机的挑选一些建树，random_state就是一种随机状态，不同随机状态挑选的特征不同，也就相当于建立了不同的决策树。Splitter，参数内容是两个可选值，best和random。上面提到random_state是在众多特征中挑选一部分特征建树，如果splitter参数选择的是best，那么选择的特征将更倾向于“重要的特征”（详见feature_importance_属性），如果splitter参数选择的是random，那就是“彻底”的随机选择特征建树了class_weight：

可以是None、balanced、或者字典类型。主要用于指定样本各类别的的权重，这样可以防止类不平衡问题（例如对于银行欺诈行为的统计数据，可能1000个人当中只有1个骗子，如果按照原始数据建模，骗子的数据会非常少，很难真正找到骗子的特征，而且即使对于骗子预测失败，把所有人都当好人，模型的准确率依然很好，因为有999个好人，准确率就是99.9%）。可以选用“balanced”，则算法会自己计算权重，样本量少的类别所对应的样本权重会高；还可以使用None，所有类别的权重都一样，也可以通过字典型指定各个样本的权重；。9.1.5决策树的重要属性和方法（1）属性feature_importances_（2）apply()方法9.2回归树9.2.1回归树的工作原理决策树主要是用于解决分类预测问题，决策树的建树方法还可以用于解决回归问题。这就会可以使用回归树。假设有根据历史数据建立如下回归树，目标是通过x1和x2的值预判y的取值：当一个被预测样本x1=40，x2=38，求这个样本的y值。这个被预测样本应该落在左数第二个叶子节点上，这个叶子上有三个历史y值，应该选哪个作为结果呢？答案是这个叶子节点所有历史y值的平均值，即26。9.2.1回归树的工作原理——回归树的损失函数回归树为什么使用叶子节点所有样本的平均值作为预测结果呢？这是通过回归树损失函数优化过程求得的。假设使用均方误差作为损失函数评断的依据，则损失函数如公式：其中f(xi)是通过回归树对样本xi进行预测的值，yi是样本xi的真实数值，i从1到n表示n个样本。设f(xi)为其中m表示某个叶子号，Cm表示m号叶子返回的值，I表示是某片叶子是否和这个样本发生关系，如果不发生关系I相当于0。所以f(xi)返回了所有和这个样本相关叶子节点的返回值。将f(xi)代入损失函数得

，此时的J便是回归树的损失函数。目标为求J最小值时Cm取值

9.2.1回归树的工作原理——回归树的损失函数损失函数这个公式的意思是对于一个样本i，找到所有(M个)和它有关的叶子，计算叶子返回值和真实值的方差，然后计算所有（n个）样本的均方差。既然我们理解了这个公式的意思是，可以给它进行一个变形。我们可以针对某一个叶子，计算叶子返回值C和这个叶子所有相关样本真实值的方差，然后再累加所有叶子节点上的方差，再除以样本数，结果同样是所有样本的均方误差。此时损失函数变为什么样的Cm能让这个损失函数最小呢？我们可以针对损失函数关于Cm求导，因为前面的M和n都是常数，所以求导时可以忽略不计，则损失函数J关于关于Cm求导，为：此时损失函数优化的目标就变成了求此导数等于0时的解。假设叶子中和样本i相关的样本有Nm个，则原公式变为

，求解得：由此可见当Cm取值为叶子中相关样本值的平均值时损失函数可以取极值。9.2.2回归树建树过程假设有如下数据：第一步：将原始数据按照X1小打到排序，则原数据表变为如下：9.2.2回归树建树过程第一步生成的新数据表：第二步：以X1列中前2个数的平均值（5和10的平均值）7.5为分界线，将样本分成两部分，X1<7.5的样本在左，X1>7.5的样本在右9.2.2回归树建树过程第三步：计算所有样本方差此时，左面叶子的返回值是20，右面叶子的返回值是其他样本y值的平均值

。然后将第一步得到新表中各个样本根据x1取值放入指定叶子，例如第一行样本x1等于5，小于7.5，所以被分到左边叶子，计算该样本y值与该叶子返回值之间的方差（20-20）2，即0；第二行样本x1为10，大于7.5，所以被分到右边叶子，计算该样本y值与叶子返回值之间的方差（15-）2

；第三行样本x1为20，大于7.5，所以落在叶子，计算该样本y值18与叶子返回值的方差是（18-

）2。以此类推，计算所有样本的均方差。9.2.2回归树建树过程步骤四：以x1列第2和第3个数的平均值（10和20的平均值是15）为分界线，将数据分成两部分，x1<15的落在左侧，x1>15的落在右侧，同样计算所有样本的均方差。步骤五：将X1列所有可能分枝的均方差都求出来步骤六：将X2和X3列所有可能分枝的均方差都求出来步骤七：找出均方差最小的分枝可能进行分枝，将数据的各个样本分到左侧和右侧节点。步骤八：针对左侧节点和右侧节点的数据，按照步骤一到步骤六，计算所有可能分枝的均方差，找到最小均方差的分枝方法继续分枝。步骤九：在新的分枝中不断再分枝，直到符合停止分枝的条件（如分到了叶子节点、树层数限制、分枝样本条件数限制等）。9.2.3回归树的实现#第一步：导入数据#导入numpy和pandas数据包importnumpyasnpimportpandasaspd#从boston_lishi.csv文件中导入原始数据df=pd.read_csv(r'E:\boston_lishi.csv',index_col='id')#X为原始数据中不包括target列部分，是由历史数据中“非结果列”组成的数据X=df.loc[:,(df.columns!='target')]#Y为原始数据中target列部分，是由历史数据中“结果列”组成的数据Y=df.loc[:,df.columns=='target']9.2.3回归树的实现#第二步：数据预处理#缺失值处理df.dropna()#其他数据预处理将在第6次课介绍9.2.3回归树的实现#第三步建模与模型评估#导入回归树工具包fromsklearn.treeimportDecisionTreeRegressorasDT#创建模型reg=DT()#除之前多次演示的模型表现评估方法外，也可以直接使用交叉验证进行评估fromsklearn.model_selectionimportcross_val_score#可以通过scoring="neg_mean_squared_error"，使用均方误差（其实是“负均方误差”）来衡量回归模型表现score_test=cross_val_score(reg,X,Y,cv=10,scoring="neg_mean_squared_error")print("模型整体均方误差：{0}".format(score_test.mean()))9.3随机森林集成算法所谓集成算法是建立多个评估器（单独的分类模型或者回归模型），综合考虑这些模型的预测结果，以此来获取比单个模型更好的回归或分类表现。在集成算法中，每一个单个评估器叫做弱评估器或基评估器，多个弱评估器和基评估器整合而成强评估器或者集成评估器。通常来说，集成算法包括装袋法（Bagging）和提升法（Boosting）。9.3.1随机森林工作原理随机决策森林是一种装袋法，装袋法是将各个弱评估器放在一起，每一个弱评估器计算出一个结果，然后各个弱评估器结果以“少数服从多数”（有些算法可能会对部分结果进行加权）的原则得出一个统一的结果。这种方法避免了单个评估器的偶然性。随机森林，顾名思义，就是好多决策树聚在一起，然后将这些决策树的结果汇总后得到一个统一的结果。9.3.2随机森林实现随机森林的实现步骤与决策树等模型基本一致，只是导入工具包和建模不同fromsklearn.ensembleimportRandomForestClassifierclf=RandomForestClassifier()随机森林的思想也可以用于回归问题，成为回归森林，导入包与建模如下fromsklearn.ensembleimportRandomForestRegressorreg=RandomForestRegressor()9.3.3重要参数前面提到的决策树常用参数在随机决策