资源描述:
《决策树(完整)》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、《机器学习》周志华第4章决策树第5章神经网络和深度学习第6章支持向量机第8章集成学习第9章聚类关联规则学习第4章决策树根据训练数据是否拥有标记信息学习任务决策树(decisiontree)模型常常用来解决分类和回归问题。常见的算法包括CART(ClassificationAndRegressionTree)、ID3、C4.5等。半监督学习:输入数据部分被标识,部分没有被标识,介于监督学习与非监督学习之间。分类、回归聚类监督学习(supervisedlearning)无监督学习(unsupervisedlearning)半监督学习(semi-supe
2、rvisedlearning)强化学习(reinforcementlearning)二分类学习任务属性属性值根结点:包含全部样本叶结点:对应决策结果“好瓜”“坏瓜”内部结点:对应属性测试决策树学习的目的:为了产生一颗泛化能力强的决策树,即处理未见示例能力强。无需划分无法划分不能划分无需划分无法划分不能划分Hunt算法:1,2,3,4,5,6,8,10,151,2,3,4,56,8,151068,15815第(2)种情形:设定为该结点所含样本最多的类别利用当前结点的后验分布第(3)种情形:设定为其父结点所含样本最多的类别把父结点的样本分布作为当前结点
3、的先验分布决策树学习的关键是算法的第8行:选择最优划分属性什么样的划分属性是最优的?我们希望决策树的分支结点所包含的样本尽可能属于同一类别,即结点的“纯度”越来越高,可以高效地从根结点到达叶结点,得到决策结果。三种度量结点“纯度”的指标:信息增益增益率基尼指数1.信息增益香农提出了“信息熵”的概念,解决了对信息的量化度量问题。香农用“信息熵”的概念来描述信源的不确定性。信息熵对于二分类任务一个事件的信息量就是这个事件发生的概率的负对数。信息熵是跟所有事件的可能性有关的,是平均而言发生一个事件得到的信息量大小。所以信息熵其实是信息量的期望。假设我们已
4、经知道衡量不确定性大小的这个量已经存在了,不妨就叫做“信息量”不会是负数不确定性函数是概率的单调递减函数;可加性:两个独立符号所产生的不确定性应等于各自不确定性之和,即同时满足这三个条件的函数是负的对数函数,即信息增益一般而言,信息增益越大,则意味着使用属性a来进行划分所获得的“纯度提升”越大。决策树算法第8行选择属性著名的ID3决策树算法举例:求解划分根结点的最优划分属性根结点的信息熵:以属性“色泽”为例计算其信息增益数据集包含17个训练样例:8个正例(好瓜)占9个反例(坏瓜)占对于二分类任务用“色泽”将根结点划分后获得3个分支结点的信息熵分别为
5、:属性“色泽”的信息增益为:若把“编号”也作为一个候选划分属性,则属性“编号”的信息增益为:根结点的信息熵仍为:用“编号”将根结点划分后获得17个分支结点的信息熵均为:则“编号”的信息增益为:远大于其他候选属性信息增益准则对可取值数目较多的属性有所偏好2.增益率增益率准则对可取值数目较少的属性有所偏好著名的C4.5决策树算法综合了信息增益准则和信息率准则的特点:先从候选划分属性中找出信息增益高于平均水平的属性,再从中选择增益率最高的。3.基尼指数基尼值基尼指数著名的CART决策树算法过拟合:学习器学习能力过于强大,把训练样本自身的一些特点当作了所有
6、潜在样本都会具有的一般性质,导致泛化性能下降。欠拟合:学习器学习能力低下,对训练样本的一般性质尚未学好。过拟合无法彻底避免,只能做到“缓解”。剪枝,即通过主动去掉一些分支来降低过拟合的风险。预剪枝决策树的剪枝策略后剪枝预剪枝:在决策树生成过程中,对每个结点在划分前先进行估计,若当前结点的划分不能带来决策树泛化性能提升,则停止划分并将当前结点标记为叶结点后剪枝:先从训练集生成一棵完整的决策树,然后自底向上地对非叶结点进行考察,若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升,则将该子树替换为叶结点。留出法:将数据集D划分为两个互斥的集合:训练
7、集S和测试集T且预剪枝1,2,3,14训练集:好瓜坏瓜1,2,3,6,7,10,14,15,16,176,7,15,1710,16精度:正确分类的样本占所有样本的比例4,5,13(T,T,F)8,9(T,F)11,12(T,T)验证集:4,5,8,9,11,12,13不足:基于“贪心”本质禁止某些分支展开,带来了欠拟合的风险预剪枝使得决策树的很多分支都没有“展开”优点:降低过拟合的风险减少了训练时间开销和测试时间开销后剪枝先从训练集生成一棵完整的决策树,然后自底向上地对非叶结点进行考察,若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升,则将
8、该子树替换为叶结点。验证集:4,5,8,9,11,124,13(T,F)5(F)9(F)8(F)11,12(T,T)验证集