[精选]决策树基本概念教材

《[精选]决策树基本概念教材》由会员分享，可在线阅读，更多相关《[精选]决策树基本概念教材（44页珍藏版）》请在金锄头文库上搜索。

1、1,分类: 基本概念,分类: 基本概念 决策树 基于规则分类 贝叶斯分类方法 提高分类准确率的技术 小结,2,什么是分类？,分类，分类器 银行贷款员需要分析数据，以便搞清楚哪些贷款申请者是“安全的”；医学研究人员分析癌症数据，以便选择治疗方案 数据分析任务都是分类，都需要构造一个分类器来预测类标号 数值预测，预测器 销售经理希望预测一位给定的顾客在双11的一次购物期间将花多少钱 数据分析任务就是数值预测，所构造的模型（预测器）预测一个连续值函数或有序值，而不是类标号,3,分类 预测类标号 (离散的或标称的) 基于训练集和类标号构建分类器，并对新的数据进行分类 数值预测 所构造的模型预测一个连续

2、值函数，而不是类标号 典型应用 信用卡/贷款批准: 医疗诊断: 肿瘤是良性的还是恶性的 欺诈检测: 一次交易是否是欺诈的 网页分类: 属于哪一类,预测问题: 分类与数值预测,4,分类一个两阶段过程,两阶段：学习阶段（构建分类模型）和分类阶段（使用模型预测给定数据的类标号） 分类模型构建(学习阶段): 描述预先定义的类 假设每个元组都属于一个预先定义的类，由类标号属性确定，类标号属性是离散值的和无序的 用于模型构建的元组集合称为训练集 模型用分类规则，决策树，或数学公式表示 模型使用(分类阶段): 用于分类未知对象 评估模型的准确性 检验样本的已知标签与模型的分类结果比较 准确率是被模型正确分类

3、的检验样本所占的百分比 检验集是独立于训练集的 (否则过分拟合) 如果准确性是可接受的，则使用模型来分类新的数据,5,监督和无监督学习,监督学习 (分类) 监督:提供了每个训练元组的类标号 即分类器的学习在被告知每个训练元组属于哪个类的“监督”下进行的 新的数据基于训练集被分类 无监督学习 (聚类) 每个训练元组的类标号是未知的 要学习的类的个数或集合也可能事先不知道,6,阶段 (1): 模型构建,训练数据,分类算法,IF rank = professor OR years 6 THEN tenured = yes,分类器 (模型),学习：用分类算法分析训练数据,7,阶段 (2): 使用模型预

4、测,分类器,检验数据,新数据,(Jeff, Professor, 4),Tenured?,分类：检验数据用于评估分类规则的准确率,8,分类: 基本概念,分类: 基本概念 决策树 基于规则分类 贝叶斯分类方法 提高分类准确率的技术 小结,9,决策树,从有类标号的训练元组中学习决策树 树结构 每个内部结点（非树叶结点）表示在一个属性上的测试 每个分枝代表该测试的一个输出 每个树叶结点存放一个类标号 树的最顶层结点是根结点 如何使用决策树分类？ 给定一个类标号未知的元组X，在决策树上测试该元组的属性值。跟踪一条由根到叶结点的路径，该叶结点就存放着该元组的类预测。,10,决策树归纳: 一个例子,训练数

5、据集: Buys_computer 决策树:,11,决策树归纳算法,基础算法 (贪心算法) 决策树以自顶向下递归的分治方式构造 从训练元组集和它们相关联的类标号开始构造决策树 所有属性是具有类别的 (如果是连续数值型的，则它们需要事先离散化) 基于选择的属性对元组进行递归划分 测试属性基于统计学度量来选择 (例如, 信息增益) 停止划分的条件 给定结点的所有元组都属于同一个类 没有剩余属性可以用来进一步划分元组 给定的分枝没有元组,算法基本策略,三个参数：D为数据分区，开始时，它是训练元组和它们相应类标号的完全集。参数attribute_list是描述元组属性的列表。参数Attribute_s

6、election_method用来选择可以按类“最好地”区分给定元组的属性，该过程使用一种属性选择度量（信息增益或基尼指数）。 树从单个结点N开始，N代表D中的训练元组 如果D中的元组都为同一类，则结点N变成树叶，并用该类标记它 否则，算法调用Attribute_selection_method确定分裂准则。分裂准则指定分裂属性，并且也指出分裂点或分裂子集 对分裂准则的每个输出，由结点N生长一个分枝。根据分裂属性A的类型，有三种可能的情况 A是离散值的: 结点N的测试输出直接对应于A的已知值 A是连续值的: 结点N的测试有两个可能的输出，分别对应于条件Asplit_point, 其中split

7、_point是分裂点 A是离散值并且必须产生二叉树: 在结点N的测试形如“A SA？”，其中SA是A的分裂子集,算法: Generate_decision_tree。由数据分区D中的训练元组产生决策树。 输入: 数据分区D, 训练元组和他们对应类标号的集合 attribute_list, 候选属性的集合。 Attribute_selection_method, 一个确定“最好地”划分数据元组为个体类的分裂准则的过程。这个准则由分裂属性(splitting_attribute)和分裂点或划分子集组成。 输出: 一棵决策树。 方法: (1) 创建一个结点N； (2) if D中的元组都在同一类C中

8、 then (3) 返回N作为叶结点, 以类C标记; (4) if attribute_list为空 then (5) 返回N作为叶结点, 标记为D中的多数类; /多数表决 (6) 使用Attribute_selection_method (D, attribute_list), 找出“最好的”splitting_criterion; (7) 用splitting_criterion标记结点N; (8) if splitting_attribute是离散值的，并且允许多路划分 then /不限于二叉树 (9) 从attribute_list中删除分裂属性 ； (10) for splittin

9、g_criterion的每个输出 j / 划分元组并对每个分区产生子树 (11) 设Dj是D中 满足输出 j 的数据元组的集合； /一个分区 (12) if Dj为空 then (13) 加一个树叶到结点N, 标记为D中的多数类 ； (14) else 加一个由Generate_decision_tree (Dj, attribute_list)返回的结点到N； endfor (15) 返回N；,14,属性选择度量: 信息增益 (ID3/C4.5),符号定义 ：设数据分区D为标记类元组的训练集。假定类标号属性具有m个不同值，定义m个不同类。设Ci,D是D中Ci类元组的集合。 选择具有最高信息增

10、益的属性A作为结点N的分裂属性 对D中的元组分类所需要的期望信息由下式给出: 基于按A划分对D的元组分类所需要的期望信息: 按属性A划分的信息增益,Pi用|Ci,D|/|D| 估计,15,属性选择: 信息增益,Class P: buys_computer = “yes” Class N: buys_computer = “no”,意思为14个样本中有5个 “age =30” 的人，其中2个为 “Yes”, 3个为 “No”. 因此 类似地,16,计算连续值属性的信息增益,假设A是一个连续值属性 必须确定A的最佳分裂点 首先将A的值按递增顺序排序 每对相邻值的中点被看做可能的分裂点 (ai+ai

11、+1)/2 是A的值ai 和 ai+1 之间的中点 对于A的每个可能分裂点, 计算InfoA(D), 具有最小期望信息需求的点选做A的分裂点 分裂: D1 是满足A split-point的元组集合, 而 D2 是满足A split-point的元组集合.,17,属性选择: 增益率 (C4.5),信息增益度量倾向于选择具有大量值的属性 C4.5 (ID3的后继) 采用增益率来克服这个问题 (规范化信息增益) GainRatio(A) = Gain(A)/SplitInfo(A) Ex. gain_ratio(income) = 0.029/1.557 = 0.019 具有最大增益率的属性作为分

12、裂属性,18,基尼指数 (CART),如果一个数据集D包含n个类，则D的基尼指数定义为 其中 pj 是D中元组属于类 j 的概率, 并用|Ci,D|/|D|估计 如果数据集D基于属性 A 被划分成两个子集D1 和 D2, 则基尼指数定义为 不纯度降低: 对于离散值属性, 选择该属性产生最小基尼指数的子集作为它的分裂子集；对于连续值属性，选择产生最小基尼指数的点作为分裂点；产生最小基尼指数（或最大不纯度降低）的属性选为分裂属性,19,基尼指数的计算,例如数据集D 有 9 个buys_computer = “yes”的元组和 5 个 “no”的元组 假设按income属性子集low, medium

13、将数据集划分为D1(10个元组)和D2(4个元组) Ginilow,high 是 0.458; Ginimedium,high 是 0.450. 因此在income的子集 low,medium上划分, 因为 它的基尼指数 最小,20,过分拟合与树剪枝,过分拟合: 树创建时，由于数据中的噪声和离群点，会过分拟合训练数据 有很多分枝，一些是由于噪声和离群点导致的异常 预测准确率下降 两种方法来避免过分拟合 先剪枝: 如果划分一个结点后的元组低于预定义阈值，则提前停止树的构建 选取一个适当的阈值是困难的 后剪枝: 由 “完全生长”的树剪去子树用回溯方式去除树的一些点 Use a set of dat

14、a different from the training data to decide which is the “best pruned tree”,21,分类: 基本概念,分类: 基本概念 决策树 基于规则分类 贝叶斯分类方法 提高分类准确率的技术 小结,22,使用IF-THEN 规则分类,以 IF-THEN 规则的形式表示学习得到的模型 R: IF age = youth AND student = yes THEN buys_computer = yes “IF” 部分称为规则前件或前提, “THEN” 部分称为规则的结论 在规则前件，条件由一个或多个用逻辑连接词AND连接的属性测试

15、组成；规则的结论包含一个类预测 对于给定的元组，如果规则前件中的条件都成立，则规则覆盖了该元组 规则的评价: 覆盖率和准确率 ncovers 表示规则R覆盖的元组数 ncorrect 表示规则R正确分类的元组数 coverage(R) = ncovers /|D| /* D: 训练数据集*/ accuracy(R) = ncorrect / ncovers,23,使用IF-THEN 规则分类,如何使用基于规则的分类来预测给定元组X的类标号？ 如果规则被X满足，则称该规则被触发。 例如，X=(age=youth, income=medium, student=yes, credit_rating

16、=fair) X满足规则R，触发该规则。 如果R是唯一满足的规则，则该规则激活，返回X的类预测 注意，触发并不总意味激活，因为可能有多个规则被满足 如果多个规则被触发，则需要解决冲突 规模序: 把最高优先权赋予具有“最苛刻”要求的被触发的规则 (即, 具有最多属性测试的) 规则序: 预先确定规则的优先次序。 基于类的序: 按类的普遍性降序排序 基于规则的序 (决策表): 根据规则质量的度量，规则被组织成一个优先权列表。最先出现在决策表中的被触发的规则具有最高优先权，因此激活它的类预测。,24,例子: 从 buys_computer 决策树提取规则 R1: IF age = young AND student = no THEN buys_computer = no R2: IF age = young AND student = yes THEN buys_computer = yes R3: IF age = mid-age THEN buys_computer = yes R4: IF age = old AND credit_rating = excellent THEN buy