决策树学习的适用问题.ppt

第二讲 机器学习的方法 第三章 决策树学习 3.2 决策树表示法 决策树的基本结构 3.3 决策树学习的适用问题 实例由“属性-值”对(pair)表示 目标函数具有离散的输出值 可能需要析取的描述(disjunctive description) 训练数据可以包含错误 (DT具有一定的鲁棒性) 训练数据可以包含缺少属性值的实例 3.4 基本的决策树学习算法(1) 原型：concept learning systems(CLS)(实验归纳一书) [Hoveland, Hunt, 1950s; Hunt, Marin and Stone, 1966] CART system [Friedman, 1977; Breiman et al., 1984] （由基尼系数--Gini Index—决定最佳的分割测试变量和阈值） ID3[J.R. Quilan, 1979,1983,1986] ASSISTANT 86 [Cestnik,Kononenko et al., 1987] (based on ID3，改进：1)属性分割的二值化，2)可实现不同层次的修剪[Mingers,1989;Cestnik,Bratko,1991]) C4.5 /Unix [J.R. Quilan，1993] See 5.0/Windows(C5.0/Unix) [J.R. Quilan，1997，适用于大型数据集的分类，采用分类器集成的方式，投票决定分类结果] 3.4 基本的决策树学习算法(2) 什么是C4.5 ? 一个基于Unix系统的应用软件 该应用软件的作用：通过C4.5设定的算法/准则生成决策树，对数据分类、分析 该设定的算法/准则：信息增益率准则(information gain ratio criterion) 3.4.1哪个属性是最佳的分类属性 从ID3到C4.5共同之处： 通过自顶向下构造决策树进行学习； 构造过程的开始：哪一个属性将在树的根节点被测试？ 区别：选择测试属性时的准则 ID3: 增益准则(Gain criterion )—衡量给定属性区分训练样例的能力。 C4.5: 增益率准则(Gain ratio criterion) ID3: Gain Criterion（1） 假设条件： 样本集 T, 包含 k 类样本: , 表示 中第 类样例的数目， 表示 中包含的样本总数。 ID3: Gain Criterion（2） 从样本中随机抽取一个样例 ，属于 类样例的概率为 。 可传达的信息为： bits。 ID3: Gain Criterion（3） 则 的熵为 bits。 是度量识别 中各类别需要的平均信息量 ，刻画了样本集的纯度(purity)。 信息论中熵的解释 熵确定了要编码集合 中任意成员（即以均匀的概率随机抽出的一个成员）的分类所需要的最少信息。 例： 若 中仅有一类，则接收者知道抽出的样例必为该类，所以不必发任何消息，此时的熵为0。 若 中含n类，若各类占比例相同，则对所需的消息进行编码时，所需的信息量为最大值 ，这也是最不确定的情况。 关于信息论中熵的更详细的内容：[A mathematical theory of communication, C.E. Shannon,1948 ] ID3: Gain Criterion（4） 若 被某个测试(test) 分割为 个子集 ，则得到的期望信息为各个子集的熵的加权和： 则 在测试 的划分下得到的信息增益为： ID3: Gain Criterion（5） 当测试 将 完全分类正确时， 此时信息增益达到最大值： 信息增益反映的是与分类相关的信息--随着划分更符合目标分布情况而增长。 ID3:各属性划分的信息增益 ID3: Gain Criterion（6） 另外一种不期望的情况也会产生,那就是当测试 将样本集 分为很多小子集时也可以使得信息增益增加。极端的情况：每一个子集只包含一个样例。此时同样有： 信息增益准则的内在偏置：偏袒具有较多值的属性。 C4.5: Gain Ratio Criterion（1） 若测试 将 划分为