[理学]机器学习2.ppt

机器学习 五、决策树学习 是一种以实例为基础的归纳学习 决策树方法的起源是概念学习系统CLS，然后发展出ID3方法，最后又演化为能处理连续属性的C4.5。 最简单但最成功的学习算法之一 是应用最广的归纳推理算法之一 一种逼近离散值目标函数的方法 5.1 决策树 内部节点 对应一个属性值的测试 连接 标记可能的测试值 叶节点 应该返回的值，比如分类的结果或者决策结果 例：是否在餐馆等座位？ 属性 Alternate：附近是否有另一家餐馆 Bar：附近是否有酒吧 Fri/Sat：是不是周五或者周六 Hungry：是否饥饿 Patrons：餐馆中有多少顾客 Price：餐馆的价格范围 Raining：外面是否下雨 Reseration：有没有预约 Type：餐馆的种类 WaitEstimate：餐馆主人估计的等候时间 决定是否等座位的决策树 决策树的使用 输入 用属性集合描述的事物或情景 可以是离散的，也可以使连续的 过程 通过执行一个测试序列得到决策 输出 针对输入的决策值 餐馆坐满了顾客、估计需要等20分钟、很饿、没有预约、下雨、附近有餐馆、附近没有酒吧 要不要等下去？ 决策树的表达能力 可以转化为逻辑形式，例如： ?s, WillWait（s）?(P1(s) ?P2(s) ?…Pn(s)) ?s, WillWait（s）? (PatronsSome(s) ?（PatronsFull（s）?between（WaitEstimate（s），10，30 ）） ? Reservation（s）） ?……) 可以机械地转化为产生式规则 if(patrons is none) then return No if(patrons is some) then return Yes if( patrons is full and WaitEstimate 60 ) then return No …… 决策树的表达能力 能表达任意的布尔函数，例如： 假设空间 对于一个n属性的布尔函数，有多少个决策树？ 相当于布尔函数的数目 相当于具有2n行的真值表的数目： 例如，如果有6个属性，那么就有18446744073709551616个不同的树 有多少个纯合取的表达式（比如： Hungry ? ?Rain ）？ 每个属性要么出现以正的形式出现在表达式中，要么以负的形式出现在表达式中，要么不出现 所以：共有3n个不同的合取表达式 5.2 决策树的构造 准备训练数据 构造决策树 构造最小决策树 ID3算法 训练集与测试集 样本:一个具体样本的形式可为:( v1, v2, ..., vn; c );其中vi表示属性值,c表示类别。 训练样本:用于训练过程的样本 训练集：训练样本构成的集合 测试集：用于评估分类模型的准确率 训练集 CLS算法 创建树的Root结点，所有的数据构成的集合C都在Root节点. 如果C中全部实例为同一个类别，则建立一个相应类别的叶结点，并且停止。 否则选择一个属性A, 根据它的值v1, …, vn 建立决策树。将Root节点标记为A 属性的选择是基于一个启发式规则或者一个统计的度量 根据值V，将训练实例C划分为子集C1, …, Cn。 对每个集合Ci递归地应用此算法。 奥卡姆剃刀原则 “若无必要,不应该增加实在东西的数目” 对一种现象,如果存在多种解释,那么选择最简单的解释. 与训练集一致的最小决策树,是最有可能正确识别未知对象的决策树 如何选择属性 要构造尽可能小的决策树，关键在于选择恰当的逻辑判断或属性。 由于构造最小的树是NP-Hard问题，因此采取用启发式策略选择好的逻辑判断或属性。 信息增益——Information gain （ID3） 增益比率——Gain ration（C4.5） 信息熵 信息熵的定义 例如 条件熵与信息增益 选择哪一个属性？ 选择信息增益最大的属性 选择 “发色” 属性 用于分类 决策树 ID4算法 1986, Schlimmer 和 Fisher 设计了ID4学习算法, 是一种递增式学习算法。他们修改ID3算法，在每个可能的决策树结点创建一系列表。每个表由全部未检测属性值和每个值的正例和反例数组成。当处理一个新例时，每个属性值的正例或反例递增计量。 ID5算法 在ID4的基础上Utgoff提出了ID5学习算法(Utgoff 1988)。ID5 与ID4的差别在于检测属性。ID5抛弃旧的检测属性下面的子树，从下面选出检测属性形成树。这种方法的优点是在树操纵时重新计算正例和反例的数，不要对实例重新处理。 C4.5算法 C4.5是对ID3的改进算法 对连续值的处理 可以处理缺少属性值的训练样本 对决策树进行剪枝 规则的派生 K次迭代交叉验证 规则