chap4_决策树.ppt

DataMining第四章 分类 基本概念 决策树和模型评估 4 1预备知识4 2解决分类问题的一般方法 分类例子 预测癌细胞是良性还是恶性将信用卡交易分为合法和欺诈 分类 定义 给定一个记录集每个记录包含一个属性集 通常最后一个属性是该记录的分类 class 属性 目标 找到一个模型 从其余属性值到分类属性的转换函数 实现对未知分类的记录进行尽可能精确地分类 通常 将给定的数据集分为训练集 trainingset 和检验集 testset 训练集用来创建模型 检验集用来验证模型的有效性 分类性能度量 分类过程 分类技术 基于决策树的方法DecisionTreebasedMethods基于规则的方法Rule basedMethods基于记忆的推理Memorybasedreasoning神经网络NeuralNetworks朴素贝叶斯和贝叶斯信念网络Na veBayesandBayesianBeliefNetworks支持向量机SupportVectorMachines 决策树定义 决策树是由结点和有向边组成的层次结构 树中包含三种结点 根结点内部结点叶结点 非终结点 包含属性测试条件 用于分开不同特性的记录 每个叶结点都赋予一个类标号 决策树例1 二元属性 分类属性 连续属性 分类标号 训练数据 模型 决策树 决策树例2 对于相同的数据 能构造多种不同的决策树 决策树应用过程 使用模型测试数据 1 检验数据 从树根开始 使用模型测试数据 2 TestData 使用模型测试数据 3 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K TestData 使用模型测试数据 4 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K TestData 使用模型测试数据 5 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K TestData 使用模型测试数据 6 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K TestData 将Cheat赋值为 No 决策树构造算法 多种算法 Hunt算法 最早方法之一 CART classificationandregressiontrees ID3 C4 5SLIQ SPRINT Hunt算法结构 Hunt算法的思想是将训练记录相继划分成 较纯 的子集 以递归方式建立决策树 假设t表示结点 Dt表示与结点t相关联的训练记录集 y y1 y2 yc 是类标号Hunt算法的递归定义 如果Dt中所有记录都属于同一个类yt 则t就是叶子节点 并用yt标号如果Dt是一个空集 那么t就是叶子节点 其标号为其父结点上训练记录中的多数类 如果Dt中包含属于多个类的记录 则选择一个属性测试条件 将记录划分成若干个子集 并对每个子集进行递归分类 例P93 P95预测拖欠银行贷款的贷款者 如何生成决策树 贪婪策略 每次选择属性划分条件时 选择划分数据的最优标准 决策树归纳的设计问题问题1 如何分裂记录 1 1定义属性测试条件 给不同类型的属性指定测试条件的方法1 2找到最好的划分方法 对每种测试条件进行评估测量问题2 何时停止分裂过程 决策树归纳的设计问题1 1 1定义属性测试条件 4 4 3表示属性测试条件的方法根据属性类型标称型Nominal序数型Ordinal连续型Continuous按划分路数二元划分2 waysplit多路划分Multi waysplit 标称属性的划分方法 数据集见P122习题2 多路划分法 划分成几个不同的值 输出数取决于该属性不同属性值的个数 二分法 划分为两个不同的值 需要找到最佳的划分方法 OR 多路划分法二分法 分组必须保留属性值之间的序关系 注意 第三种划分方法合理吗 序数属性的划分方法 OR 连续属性的划分方法 多路划分 离散化属性值 每个离散化区间赋予一个新的序数值二分法 A v or A v 需要从所有可能的划分点中选择产生最佳划分的点 决策树归纳的设计问题1 1 2找到最好划分方法 划分前 数据集有20个记录 标号为class0和class1的各有10个 哪个划分测试条件最佳 为了度量不同的测试条件 常用划分前和划分后记录的类分布定义 p i t 表示结点t中 属于类i的记录所占的比例 常简记为pi 在二元分类问题中 任意结点的类分布可以记作 p0 p1 其中p1 1 p0 选择最佳划分的度量 选择最佳划分的度量通常是根据划分后子女结点不纯性的程度 不纯的程度越低 类分布就越倾斜 划分就越好 不同类 具有较高的不纯度 同类 具有较低的不纯度 结点不纯度的度量方法 熵Entropy基尼指数GiniIndex分类差错率Classificationerror 计算不纯性方法1 熵 结点t的熵 其中 c为结点t中不同类标号个数p i t 是给定结点t中属于类i的记录所占比例 简记为pi结点熵值的取值范围 当记录均匀分布于各分类时 将取得最大值 lognc 当所有记录都属于同一分类时 将取得最小值 0 例 分别计算3个结点的熵 P C0 0 6 0P C1 6 6 1Entropy 0 log0 1 log1 0 0 0 P C0 1 6P C1 5 6Entropy 1 6 log2 1 6 5 6 log2 5 6 0 65 P C0 2 6P C1 4 6Entropy 2 6 log2 2 6 4 6 log2 4 6 0 92 练习1 已知 数据见课本表4 7 P122题2 采用熵作为结点的不纯度度量 问题 整个训练样本集的不纯度是多少 如果对数据按车型属性进行多路划分 则 车型 运动 的结点的不纯度是多少 车型 豪华 的结点的不纯度是多少 车型 家用 的结点的不纯度是多少 计算不纯性方法2 基尼指数 gini 结点t的吉尼指数 其中 c为结点t中不同类标号个数p i t 是给定结点t中属于类i的记录所占比例 简记为pi结点Gini指数的取值范围 当记录均匀分布于各分类时 将取得最大值 1 1 nc 当所有记录都属于同一分类时 将取得最小值 0 例 分别计算3个结点的Gini指数 P C0 0 6 0P C1 6 6 1Gini 1 P C0 2 P C1 2 1 0 1 0 P C0 1 6P C1 5 6Gini 1 1 6 2 5 6 2 0 278 P C0 2 6P C1 4 6Gini 1 2 6 2 4 6 2 0 444 练习2 已知 数据见课本表4 7 P122题2 采用Gini指数作为结点的不纯度度量 问题 整个训练样本集的不纯度是多少 如果对数据按车型属性进行多路划分 则 车型 运动 的结点的不纯度是多少 车型 豪华 的结点的不纯度是多少 车型 家用 的结点的不纯度是多少 计算不纯性方法3 分类差错率 节点t的分类差错率 p i t 是给定结点t中属于类i的记录所占比例 简记为pi结点分类误差率指数的取值范围 当记录均匀分布于各分类时 将取得最大值 1 1 nc 当所有记录都属于同一分类时 将取得最小值 0 例 分别计算3个子女结点的分类差错率 P C0 0 6 0P C1 6 6 1Error 1 max 0 1 1 1 0 P C0 1 6P C1 5 6Error 1 max 1 6 5 6 1 5 6 1 6 P C0 2 6P C1 4 6Error 1 max 2 6 4 6 1 4 6 1 3 练习3 已知 数据见课本表4 7 P122题2 采用分类误差率作为结点的不纯度度量 问题 整个训练样本集的不纯度是多少 如果对数据按车型属性进行多路划分 则 车型 运动 的结点的不纯度是多少 车型 豪华 的结点的不纯度是多少 车型 家用 的结点的不纯度是多少 二元分类问题结点不纯性度量之间的比较 利用不纯性度量 选择最佳划分 方法 分别比较父节点 划分前 的不纯程度和子女结点 划分后 的不纯程度 它们的差值越大 测试条件的效果就越好 用增益 来作为确定划分效果的标准其中 I 是结点不纯性度量 N是父节点上的记录总数 k是父节点的分支数 N vj 是子女结点vj的记录个数 决策树归纳算法 通常就是选择最大化增益 的测试条件 作为当前节点的属性测试条件 利用增益 来选择最佳划分示意 B Yes No NodeN3 NodeN4 A Yes No NodeN1 NodeN2 划分前 比较增益 A M父亲 MA vs B M父亲 MB 计算不纯性 计算不纯性 计算不纯性 计算不纯性 加权平均 加权平均 练习4 已知 数据见课本表4 7 P122题2 问题 a g 熵和Gini指数等不纯度趋向有利于具有大量不同值的属性产生大量输出测试条件 从而导致与每个划分关联的记录很少 极端情况如 以顾客ID进行划分 比其他划分方法能得到更 纯 的派生结点 改进方法 信息增益 熵差 ni 孩子节点i的记录数n 节点p的记录数用于ID3和C4 5算法 增益率 将父节点p划分为k部分n表示p的记录数ni表示第i部分 p的第i个节点 的记录数调整信息增益 引入划分信息SplitInfo 把属性测试条件产生的输出数也考虑进去 如果一个属性产生了大量的划分 它的划分信息SplitInfo将会很大 从而增益率降低 用于C4 5算法 比较不同类型的属性的划分 以Gini指数为例 二元属性标称属性离散属性 基于GINI指数的二元属性划分方法 划分为两部分 B Yes No NodeN1 NodeN2 Gini N1 1 5 7 2 2 7 2 0 194Gini N2 1 1 5 2 4 5 2 0 528 Gini Children 7 12 0 194 5 12 0 528 0 333 基于GINI指数的标称属性划分方法 用矩阵帮助选择最佳划分 Multi waysplit Two waysplit findbestpartitionofvalues 基于GINI指数的连续属性划分方法 问题 需要选择候选划分点方法1 穷举法将记录中所有的属性值作为候选划分点 计算每个候选的Gini指标 并从中选择具有最小值的候选划分点 效率低计算代价昂贵 改进方法 根据划分属性 先对记录进行排序从两个相邻的排过序的属性值中选择中间值作为候选划分点 55 65 72 80 在计算相邻结点时值 部分类分布保持不变 减少计算量 进一步优化 仅仅考虑位于具有不同类标号的两个相邻记录之间的候选划分点 55 80 97 计算其Gini指数 决策树归纳的设计问题2 如何停止分裂过程 停止方法 方法1 当所有记录都属于同一分类时 停止划分方法2 当所有记录都有相似 相同 属性值时 停止划分方法3 提前终止 4 3 5决策树归纳算法 算法输入 训练记录集E和属性集F 算法输出 构造的决策树主要函数 createNode 建立一个新结点 结点要么表示一个测试条件 node test cond 要么表示一个类标号 node label find best split 从剩余属性中挑选一个属性作为结点的测试条件 Classify 为叶子结点确定类标号 多数情况下 left label stopping cond 测试是否应该决策树的增长 TreeGrowth算法框架 P101 ifstopping cond E F truethenleft createNode left lable Classify returnleafelseroot createNode root test cond find best split E F 令V v v是root test cond的一个可能输出 for每个v VdoEv e root test cond e v并且e E child TreeGrowth Ev F 将child作为root派生结点加到树中 将边 root child 记为vendforendifreturnroot 案例学习 4 3 6Web机器人检测 阅读课本例子 回答下列问题 什么是Web使用挖掘 Web使用挖掘的数据源是什么 这些数据是如何得到的 为什么说在Web挖掘中 区分正常用户访问和Web机器人访问时重要的 本例子中 决策树模型是如何建立起来的 请你用1分钟长度的时间 叙述其建立的过程 根据课本的决策树模型 正常用户访问有何特征 4 3 7决策树归纳的特点 是一种构建分类模型的非参数方法大多决策树算法都采用启发式的方法来简化搜索决策树容易构建 对未知样本的分类也快决策树相对容易理解对于噪声的干扰具有相当好的鲁棒性冗余属性不会对决策树的准确率造成不利影响对于数据碎片问题 可以通过规定阈值来检测和解决可能会产生子树在决