数学建模_决策树.ppt

* * * 决策树的优点 可以生成可以理解的规则； 计算量相对来说不是很大； 可以处理连续和离散字段； 可以处理残缺数据 决策树可以清晰的显示哪些字段比较重要 不足之处 对连续性的字段比较难预测 当类别太多时，错误可能会增加的比较快 一般的算法分类的时候，只是根据一个属性来分类。 不是全局最优。 随机森林的定义 随机森林是一个树型分类器{h(x,?k),k=1,…}的集合。其中元分类器h(x,?k)是决策树；森林的输出采用简单多数投票法（针对分类）或单颗树输出结果的简单平均（针对回归）得到。 随机森林算法 随机选取训练样本集：使用Bagging方法形成每颗树的训练集 随机选取分裂属性集：假设共有M个属性，指定一个属性数F≤M，在每个内部结点，从M个属性中随机抽取F个属性作分裂属性集，以这F个属性上最好的分裂方式对结点进行分裂（在整个森林的生长过程中， F的值一般维持不变） 每颗树任其生长，不进行剪枝 随机森林算法 Bagging(Breiman,1996)? 在训练的每一轮中，均从原始样本集S中有放回地随机抽取训练样本集T（T的样本个数同S），这样一个初始样本在某轮训练中可能出现多次或根本不出现（ S中每个样本未被抽取的概率为(1-1/|S|)|S|≈0.368，当|S|很大时）。 最终的分类规则为简单多数投票法或简单平均法 影响随机森林分类性能的主要因素 森林中单颗树的分类强度（Strength）：每颗树的分类强度越大，则随机森林的分类性能越好。 森林中树之间的相关度（Correlation）：树之间的相关度越大，则随机森林的分类性能越差。 随机森林的特点 两个随机性的引入，使得随机森林不容易陷入过拟合 两个随机性的引入，使得随机森林具有很好的抗噪声能力 对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化。 * 决策树 概要 简介 决策树表示法 决策树学习的适用问题 基本的决策树学习算法 决策树学习中的假想空间搜索 决策树学习的常见问题 简介 决策树方法是应用最广的归纳推理算法之一 一种逼近离散值目标函数的方法 对噪声数据有很好的健壮性且能学习析取表达式 决策树的表示法 决策树通过把实例从根节点排列到某个叶子节点来分类实例，叶子节点即为实例所属的分类。树上的每一个节点说明了对实例的某个属性的测试，并且该节点的每一个后继分支对应于该属性的一个可能值 图 表达式 决策树学习的适用问题 实例是由属性-值对表示的 目标函数具有离散的输出值 训练数据可以包含错误 训练数据可以包含缺少属性值的实例 属性选择 构造好的决策树的关键在于如何选择好的逻辑判断或属性。对于同样一组例子，可以有很多决策树能符合这组例子。人们研究出，一般情况下或具有较大概率地说，树越小则树的预测能力越强。要构造尽可能小的决策树，关键在于选择恰当的逻辑判断或属性。由于构造最小的树是NP-难问题，因此只能采取用启发式策略选择好的逻辑判断或属性。 用熵度量样例的均一性（纯度） 熵的定义 举例 用信息增益度量期望熵最低 举例 ID3算法(Iterative Dichotomiser 3) 创建树的Root结点 如果Examples都为正，那么返回label=+中的单结点Root 如果Examples都为反，那么返回lable=-单结点树Root 如果Attributes为空，那么返回单节点树Root，lable=Examples中最普遍的目标属性值 否则开始 A?Attributes中分类能力最好的属性 Root的决策属性?A 对于每个可能值 在Root下加一个新的分支对应测试A=vi 令Example-vi为Examples中满足A属性值为vi的子集 如果Examples-vi为空 在这个新分支下加一个叶子结点，节点的lable=Examples中最普遍的 目标属性值 否则在这个新分支下加一个子树ID3(example-vi,target- attribute,attributes-|A| 结束 返回 Root Example 2 Factors affecting sunburn S = [3+, 5-] Entropy(S) = -(3/8)log2(3/8) – (5/8)log2(5/8) = 0.95443 Find IG for all 4 attributes: Hair, Height, Weight, Lotion For attribute ‘Hair’: Values(Hair) : [Blonde, Brown, Red] S = [3+,5-] SBlonde = [2+,2-] E(SBlonde) = 1 SBrown =