第三周决策树和Boosting-ToStu.ppt

1 分类 基本概念 分类 基本概念决策树基于规则分类贝叶斯分类方法提高分类准确率的技术小结 2 什么是分类 分类 分类器银行贷款员需要分析数据 以便搞清楚哪些贷款申请者是 安全的 医学研究人员分析癌症数据 以便选择治疗方案数据分析任务都是分类 都需要构造一个分类器来预测类标号数值预测 预测器销售经理希望预测一位给定的顾客在双11的一次购物期间将花多少钱数据分析任务就是数值预测 所构造的模型 预测器 预测一个连续值函数或有序值 而不是类标号 3 分类预测类标号 离散的或标称的 基于训练集和类标号构建分类器 并对新的数据进行分类数值预测所构造的模型预测一个连续值函数 而不是类标号典型应用信用卡 贷款批准 医疗诊断 肿瘤是良性的还是恶性的欺诈检测 一次交易是否是欺诈的网页分类 属于哪一类 预测问题 分类与数值预测 4 分类 一个两阶段过程 两阶段 学习阶段 构建分类模型 和分类阶段 使用模型预测给定数据的类标号 分类模型构建 学习阶段 描述预先定义的类假设每个元组都属于一个预先定义的类 由类标号属性确定 类标号属性是离散值的和无序的用于模型构建的元组集合称为训练集模型用分类规则 决策树 或数学公式表示模型使用 分类阶段 用于分类未知对象评估模型的准确性检验样本的已知标签与模型的分类结果比较准确率是被模型正确分类的检验样本所占的百分比检验集是独立于训练集的 否则过分拟合 如果准确性是可接受的 则使用模型来分类新的数据 5 监督和无监督学习 监督学习 分类 监督 提供了每个训练元组的类标号即分类器的学习在被告知每个训练元组属于哪个类的 监督 下进行的新的数据基于训练集被分类无监督学习 聚类 每个训练元组的类标号是未知的要学习的类的个数或集合也可能事先不知道 6 阶段 1 模型构建 训练数据 分类算法 IFrank professor ORyears 6THENtenured yes 分类器 模型 学习 用分类算法分析训练数据 7 阶段 2 使用模型预测 分类器 检验数据 新数据 Jeff Professor 4 Tenured 分类 检验数据用于评估分类规则的准确率 8 分类 基本概念 分类 基本概念决策树基于规则分类贝叶斯分类方法提高分类准确率的技术小结 9 决策树 从有类标号的训练元组中学习决策树树结构每个内部结点 非树叶结点 表示在一个属性上的测试每个分枝代表该测试的一个输出每个树叶结点存放一个类标号树的最顶层结点是根结点如何使用决策树分类 给定一个类标号未知的元组X 在决策树上测试该元组的属性值 跟踪一条由根到叶结点的路径 该叶结点就存放着该元组的类预测 10 决策树归纳 一个例子 训练数据集 Buys computer决策树 11 决策树归纳算法 基础算法 贪心算法 决策树以自顶向下递归的分治方式构造从训练元组集和它们相关联的类标号开始构造决策树所有属性是具有类别的 如果是连续数值型的 则它们需要事先离散化 基于选择的属性对元组进行递归划分测试属性基于统计学度量来选择 例如 信息增益 停止划分的条件给定结点的所有元组都属于同一个类没有剩余属性可以用来进一步划分元组给定的分枝没有元组 算法基本策略 三个参数 D为数据分区 开始时 它是训练元组和它们相应类标号的完全集 参数attribute list是描述元组属性的列表 参数Attribute selection method用来选择可以按类 最好地 区分给定元组的属性 该过程使用一种属性选择度量 信息增益或基尼指数 树从单个结点N开始 N代表D中的训练元组如果D中的元组都为同一类 则结点N变成树叶 并用该类标记它否则 算法调用Attribute selection method确定分裂准则 分裂准则指定分裂属性 并且也指出分裂点或分裂子集对分裂准则的每个输出 由结点N生长一个分枝 根据分裂属性A的类型 有三种可能的情况A是离散值的 结点N的测试输出直接对应于A的已知值A是连续值的 结点N的测试有两个可能的输出 分别对应于条件Asplit point 其中split point是分裂点A是离散值并且必须产生二叉树 在结点N的测试形如 A SA 其中SA是A的分裂子集 算法 Generate decision tree 由数据分区D中的训练元组产生决策树 输入 数据分区D 训练元组和他们对应类标号的集合attribute list 候选属性的集合 Attribute selection method 一个确定 最好地 划分数据元组为个体类的分裂准则的过程 这个准则由分裂属性 splitting attribute 和分裂点或划分子集组成 输出 一棵决策树 方法 1 创建一个结点N 2 ifD中的元组都在同一类C中then 3 返回N作为叶结点 以类C标记 4 ifattribute list为空then 5 返回N作为叶结点 标记为D中的多数类 多数表决 6 使用Attribute selection method D attribute list 找出 最好的 splitting criterion 7 用splitting criterion标记结点N 8 ifsplitting attribute是离散值的 并且允许多路划分then 不限于二叉树 9 从attribute list中删除分裂属性 10 forsplitting criterion的每个输出j 划分元组并对每个分区产生子树 11 设Dj是D中满足输出j的数据元组的集合 一个分区 12 ifDj为空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类元组的集合 选择具有最高信息增益的属性A作为结点N的分裂属性对D中的元组分类所需要的期望信息由下式给出 基于按A划分对D的元组分类所需要的期望信息 按属性A划分的信息增益 Pi用 Ci D D 估计 15 属性选择 信息增益 ClassP buys computer yes ClassN buys computer no 意思为14个样本中有5个 age 30 的人 其中2个为 Yes 3个为 No 因此类似地 16 计算连续值属性的信息增益 假设A是一个连续值属性必须确定A的最佳分裂点首先将A的值按递增顺序排序每对相邻值的中点被看做可能的分裂点 ai ai 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具有最大增益率的属性作为分裂属性 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 将数据集划分为D1 10个元组 和D2 4个元组 Gini low high 是0 458 Gini medium high 是0 450 因此在income的子集 low medium 上划分 因为它的基尼指数最小 20 过分拟合与树剪枝 过分拟合 树创建时 由于数据中的噪声和离群点 会过分拟合训练数据有很多分枝 一些是由于噪声和离群点导致的异常预测准确率下降两种方法来避免过分拟合先剪枝 如果划分一个结点后的元组低于预定义阈值 则提前停止树的构建选取一个适当的阈值是困难的后剪枝 由 完全生长 的树剪去子树 用回溯方式去除树的一些点Useasetofdatadifferentfromthetrainingdatatodecidewhichisthe bestprunedtree 21 分类 基本概念 分类 基本概念决策树基于规则分类贝叶斯分类方法提高分类准确率的技术小结 22 使用IF THEN规则分类 以IF THEN规则的形式表示学习得到的模型R IFage youthANDstudent yesTHENbuys computer yes IF 部分称为规则前件或前提 THEN 部分称为规则的结论在规则前件 条件由一个或多个用逻辑连接词AND连接的属性测试组成 规则的结论包含一个类预测对于给定的元组 如果规则前件中的条件都成立 则规则覆盖了该元组规则的评价 覆盖率和准确率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 fair X满足规则R 触发该规则 如果R是唯一满足的规则 则该规则激活 返回X的类预测注意 触发并不总意味激活 因为可能有多个规则被满足如果多个规则被触发 则需要解决冲突规模序 把最高优先权赋予具有 最苛刻 要求的被触发的规则 即 具有最多属性测试的 规则序 预先确定规则的优先次序 基于类的序 按类的普遍性降序排序基于规则的序 决策表 根据规则质量的度量 规则被组织成一个优先权列表 最先出现在决策表中的被触发的规则具有最高优先权 因此激活它的类预测 24 例子 从buys computer决策树提取规则R1 IFage youngANDstudent noTHENbuys computer noR2 IFage youngANDstudent yesTHENbuys computer yesR3 IFage mid ageTHENbuys computer yesR4 IFage oldANDcredit rating excellentTHENbuys computer noR5 IFage oldANDcredit rating fairTHENbuys computer yes 由决策树提取规则 与决策树相比 IF THEN规则可能更容易理解 尤其是当决策树非常大时对每条从根到树叶结点的路径创建一个规则给定路径上的每个分裂准则的逻辑AND形成规则的前件 IF 部分 存放类预测的树叶结点形成规则的后件 THEN 部分 规则是互斥的和穷举的 25 规则归纳 顺序覆盖算法 顺序覆盖算法 直接从训练集中提取规则典型的顺序覆盖算法 FOIL AQ CN2 RIPPER规则被顺序地学习 给定类的每个规则覆盖该类的许多元组 并且希望不覆盖其他类的元组 步骤 一次学习一个规则每学习一个规则 就删除该规则覆盖的元组在剩下的元组上重复该过程 直到满足终止条件 例如 不再有训练元组 或返回规则的质量低于用户指定的阈值与决策树对比 决策树归纳是同时学习一组规则 26 基本顺序覆盖算法 算法 顺序覆盖 学习一组IF THEN分类规则 输入 D 类标记元组的数据集合 Att vals 所有属性与它们可能值的集合 输出 IF THEN规则的集合 方法 Rule set 学习的规则集初始为空for每个类cdorepeatRule Learn One Rule D Att vals c 从D中删除被Rule覆盖的元组 until终止条件满足 Rule set Rule set Rule 将新规则添加到规则集endfor返回Rule set 27 如何Learn One Rule 从最一般的规则开始 condition empty 条件为空 通过采用一种贪心的深度优先策略添加新的属性选择最能提高规则质量的属性规则质量度量 同时考虑覆盖率和准确率Foil gain inFOIL RIPPER 用下式估计扩展条件而获得的信息偏向于具有高准确率并且覆盖许多正元组的规则 28 分类 基本概念 分类 基本概念决策树基于规则分类贝叶斯分类方法提高分类准确率的技术小结 29 贝叶斯定理 基础 贝叶斯定理 X表示数据元组 类标号未知H为某种假设 如数据元组X属于某个特定类C分类是确定P H X 即后验概率 在条件X下 H的后验概率 例如 X是一位35岁的顾客 其收入为4万美元 令H为某种假设 如顾客将购买计算机 则P H X 反映当我们知道顾客的年龄和收入时 顾客X将购买计算机的概率 P H 先验概率 H的先验概率如 任意给定顾客将购买计算机的概率P X X的先验概率 如顾客集合中的年龄为35岁并且收入为4万美元的概率P X H 在条件H下 X的后验概率例如 已知顾客X将购买计算机 该顾客是35岁并且收入为4万美元的概率 30 分类就是导出最大后验概率 设D是训练元组和它们相关联的类标号的集合 每个元组用一个n维属性向量X x1 x2 xn 表示假定有m个类C1 C2 Cm 分类法将预测X属于具有最高后验概率的类 即 最大的P Ci X 如果P Ci X 在所有k个类的P Ck X 中最大 则预测X属于类Ci每个类的后验概率可根据以下贝叶斯定理计算得到由于P X 对所有类为常数 所以只需要最大化 31 朴素贝叶斯分类 简单假定 属性有条件地相互独立 即属性之间不存在依赖关系 如果Ak是分类属性 则P xk Ci 是D中属性Ak的值为xk的Ci类的元组数除以D中Ci类的元组数 Ci D 如果Ak是连续值属性 P xk Ci 通常基于均值 和标准差 的高斯分布计算 假定连续值属性服从均值为 标准差为 的高斯分布 由下式定义 32 朴素贝叶斯分类 Class C1 buys computer yes C2 buys computer no 待分类数据 X age 30 Income medium Student yes Credit rating Fair 33 朴素贝叶斯分类 例子 P Ci P buys computer yes 9 14 0 643P buys computer no 5 14 0 357为每个类计算P X Ci P age 30 buys computer yes 2 9 0 222P age 30 buys computer no 3 5 0 6P income medium buys computer yes 4 9 0 444P income medium buys computer no 2 5 0 4P student yes buys computer yes 6 9 0 667P student yes buys computer no 1 5 0 2P credit rating fair buys computer yes 6 9 0 667P credit rating fair buys computer no 2 5 0 4X age 30 income medium student yes credit rating fair P X Ci P X buys computer yes 0 222x0 444x0 667x0 667 0 044P X buys computer no 0 6x0 4x0 2x0 4 0 019P X Ci P Ci P X buys computer yes P buys computer yes 0 028P X buys computer no P buys computer no 0 007因此 X属于类 buys computer yes 34 避免零概率问题 朴素贝叶斯分类预测需要每个条件概率是非零的 否则 预测概率将会为零例如 假设一个具有1000个元组的数据集 income low 0 income medium 990 和income high 10 使用拉普拉斯校准 或拉普拉斯估计法 每个组元组数加1Prob income low 1 1003Prob income medium 991 1003Prob income high 11 1003 校准的 概率估计与对应的 未校准的 估计很接近 35 朴素贝叶斯分类 评价 优点易于实施大部分情况下可以获得好的结果缺点假设 类条件独立 因此损失准确性实际中 属性之间经常存在依赖性属性之间存在依赖的情况不能通过朴素贝叶斯分类建模怎么处理这些依赖性 贝叶斯信念网络 36 分类 基本概念 分类 基本概念决策树基于规则分类贝叶斯分类方法提高分类准确率的技术小结 组合方法 提高分类准确率 组合方法把k个学习得到的模型 M1 M2 Mk 组合在一起 旨在创建一个改进的复合分类模型M 流行的组合方法装袋 在一组分类器上平均预测提升 基于一组分类器的加权表决 37 给定一个待分类元组X 它收集由基分类器返回的类标号预测 并输出占多数的类 装袋 自助聚集 类似 基于多个医生多数表决的诊断训练每次迭代i d个元组的训练集Di采用有放回抽样从原始数据集D抽取从每个训练集Di学习一个分类器模型Mi分类 对一个未知元组X分类每个分类器Mi返回它的类预测装袋分类器M 统计得票 并将得票最高的类赋予X预测 通过取给定元组的每个预测的平均值 装袋也可以用于连续值的预测