决策树课件(共66张课件).pptxVIP

决策树;决策树;1.1决策树模型与学习;1.1.1决策树模型;决策树学习算法的特点;决策树学习的主要算法;例1.找对象;1.1.2决策树与if-then规则;1.1.3决策树与条件概率分布;1.1.4决策树学习;1.1.4决策树学习;1.2特征选择

特征选择问题;ID;1.2.2信息增益;熵-就分类而言，所有成员都属于一类，熵为零；不同类别

数目相等，则熵等于1，类别数目不等，则熵介于0,1之间。;条件熵;信息增益;信息增益的具体公式;信息增益算法;例1.3对表1.1所给的训练数据集D,

根据信息增益准则选择最优特征。;1.2.3信息增益比;1.3决策树的生成

1.3.1ID3算法;例1.4对表1.1的训练数据集，利用ID3算法建立决策树;?;;补充：如何解决决策树的过拟合问题;补充：如何解决决策树的过拟合问题——概念;二.产生过度拟合数据问题的原因有哪些？;三.如何解决过度拟合数据问题？;1.3.2C4.5的生成算法;1.4决策树的剪枝;算法1.4树的剪枝算法;关于剪枝的补充——先剪枝;补充：关于剪枝——先剪枝;解决决策树过拟合的另一种方法——随机森林

根据总投票人数，250可能有所调整

定义一个阈值，当达到某个结点的实例个数小于该阈值时就可以停止决策树的生长；

女儿：长的帅不帅？(长相)

???母亲：挺帅的。

对于样本的误差率e，我们可以根据经验把它估计成各种各样的分布模型，比如是二项式分布，比如是正态分布。

补充：如何解决决策树的过拟合问题

CART假设决策树是二叉树，内部结点特征的取值为“是”和“否。

2特征选择

特征选择问题

1所给的训练数据集D,

根据信息增益准则选择最优特征。

C4.

现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：

决策树由结点和有向边组成。

那么一棵树错误分类一个样本值为1，正确分类一个样本值为0，该树错误分类的概率（误判率）为e（e为分布的固有属性,可以通过;补充：关于剪枝的准则;补充：关于剪枝的准则;REP——错误率降低剪枝;Pesimistic-ErrorPruning(PEP,悲观错误剪枝）;PEP——悲观错误剪枝;PEP续

的标准误差内。对于样本的误差率e，我们可以根据经验把它估计成各种各样的分布模型，比如是二项式分布，比如是正态分布。

那么一棵树错误分类一个样本值为1，正确分类一个样本值为0，该树错误分类的概率（误判率）为e（e为分布的固有属性,可以通过

统计出来），那么树的误判次数就是伯努利分布，我们可以估计出该树的误判次数均值和标准差：;PEP续

把子树替换成叶子节点后，该叶子的误判次数也是一个伯努利分布，其概率误判率e为(E+0.5)/N，因此叶子节点的误判次数均值为

使用训练数据，子树总是比替换为一个叶节点后产生的误差小，但是使用校正后有误差计算方法却并非如此，当子树的误判个数大过对应叶节点的误判个数一个标准差之后，就决定剪枝：

这个条件就是剪枝的标准。当然并不一定非要大一个标准差，可以给定任意的置信区间，我们设定一定的显著性因子，就可以估算出误判次数的上下界。;PEP——小例题;Cost-ComplexityPruning（CCP，代价复杂度剪枝);例子;CCP续;CCP续;几种后剪枝方法的比较;1.5CART（分类与回归树）算法;1.5.1CART生成;GINI指数;1.5.2CART剪枝;记原始数据为D，长度为N(即图中有N个离散点)

解决决策树过拟合的另一种方法——随机森林

*当然可以使用决策树作为基本分类器

本质仍然是分类问题：对于某个电影，有N个决策树，每个决策树对该电影有1个分类(1、2、3、4、5类)，求这个电影应该属于哪一类(可以是小数：分类问题变成了回归问题)

*在所有属性上，对这n个样本建立分类器(ID3、C4.

T4这棵子树的误差率：

但是基于损失函数找到全局最优决策树是NP-完全问题。

有多种不同的方式可以让决策树停止生长，下面介绍几种停止决策树生长的方法：

*从所有属性中随机选择k个属性，选择最佳分割属性

R：该电影的用户投票的平均得分(Rating)

把一棵子树（具有多个叶子节点）的分类用一个叶子节点来替代的话，在训练集上的误判率肯定是上升的，但是在新数据上不一定。

这些分类器组成的“总分类器”，仍然叫做随机森林。

*将数据放在这m个分类器上，最后根据这m个分类器

不同类别

数目相等，则熵等于1，类别数目不等，则熵介于0,1之间。

r（t）为结点t的错分样本率，p（t）为落入结点t的样本占所有样本的比例；

使用训练数据，子树总是比替换为一个叶节点后产生的误差小，但