(11)决策树随机森林adaboost

《(11)决策树随机森林adaboost》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、决策树、随机森林、adaboost七月算法龙老师2016年5月28日主要内容复习信息熵熵、互信息决策树学习算法信息增益ID3、C4.5、CARTBagging与随机森林提升Adaboost/GDBT4月机器学习算法班julyedu.com2/51熵与互信息熵是对平均不确定性的度量平均互信息：得知特征Y的信息而使得对标签X的信息的不确定性减少的程度。4月机器学习算法班julyedu.com3/51熵与互信息4月机器学习算法班julyedu.com4/51各个熵之间的关系4月机器学习算法班julyedu.com5/51决策树根节点

2、父节点子节点叶子节点分叉属性标签4月机器学习算法班julyedu.com6/51决策树(DecisionTree)决策树学习采用的是自顶向下的递归方法，其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶节点中的实例都属于同一类。有监督学习4月机器学习算法班julyedu.com7/51决策树学习的生成算法建立决策树的关键，即在当前状态下选择哪个属性作为分类依据。根据不同的目标函数，建立决策树主要有一下三种算法。ID3C4.5CART4月机器学习算法班julyedu.com8/51信息增

3、益特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D

4、A)之差，即：g(D,A)=H(D)–H(D

5、A)显然，这即为训练数据集D和特征A的互信息。遍历所有特征，选择信息增益最大的特征作为当前的分裂特征4月机器学习算法班julyedu.com9/51其他目标信息增益率：gr(D,A)=g(D,A)/H(A)C4.5Gini系数：CART4月机器学习算法班julyedu.com10/51关于Gini系数的讨论考察Gini系数的图像、熵、分类误差率三者之间的关系将f(x)=-

6、lnx在x=1处一阶展开，忽略高阶无穷小，得到f(x)≈1-x4月机器学习算法班julyedu.com11/51三种决策树学习算法ID3：取值多的属性，更容易使数据更纯，其信息增益更大。训练得到的是一棵庞大且深度浅的树：不合理。C4.5CART一个属性的信息增益(率)/gini指数越大，表明属性对样本的熵减少的能力更强，这个属性使得数据由不确定性变成确定性的能力越强4月机器学习算法班julyedu.com12/51决策树的评价4月机器学习算法班julyedu.com13/514月机器学习算法班julyedu.com14/514月机器学习

7、算法班julyedu.com15/514月机器学习算法班julyedu.com16/514月机器学习算法班julyedu.com17/514月机器学习算法班julyedu.com18/514月机器学习算法班julyedu.com19/514月机器学习算法班julyedu.com20/514月机器学习算法班julyedu.com21/514月机器学习算法班julyedu.com22/514月机器学习算法班julyedu.com23/51决策树的过拟合决策树对训练属于有很好的分类能力，但对未知的测试数据未必有好的分类能力，泛化能力弱，即可能发生过拟合

8、现象。剪枝随机森林4月机器学习算法班julyedu.com24/51剪枝三种决策树的剪枝过程算法相同，区别仅是对于当前树的评价标准不同。信息增益、信息增益率、基尼系数剪枝总体思路：由完全树T0开始，剪枝部分结点得到T1，再次剪枝部分结点得到T2…直到仅剩树根的树Tk；在验证数据集上对这k个树分别评价，选择损失函数最小的树Tα4月机器学习算法班julyedu.com25/51剪枝系数的确定根据原损失函数：叶结点越多，决策树越复杂，损失越大，修正：当α=0时，未剪枝的决策树损失最小；当α=+∞时，单根结点的决策树损失最小。假定

9、当前对以r为根的子树剪枝：剪枝后，只保留r本身而删掉所有的叶子考察以r为根的子树：令剪枝后的损失函数=剪枝前的损失函数，求得a4月机器学习算法班julyedu.com26/51剪枝算法对于给定的决策树T0：计算所有内部节点的剪枝系数；查找最小剪枝系数的结点，剪枝得决策树Tk；重复以上步骤，直到决策树Tk只有1个结点；得到决策树序列T0T1T2…TK；使用验证样本集选择最优子树。使用验证集做最优子树的标准，可以使用评价函数4月机器学习算法班julyedu.com27/51BootstrapingBootstraping的名称来自

10、成语“pullupbyyourownbootstraps”，意思是依靠你自己的资源，称为自助法，它是一种有放回的抽样方法。