lecture4-分类基本原理与决策树.ppt

数据挖掘导论 * 1 分类: 基本概念与决策树 Dr. Haitao Xiong BTBU 数据挖掘导论 * 2 分类: 定义 l给定多条记录的集合 (数据集) 每一条记录都通过元组 (x, y)来表示，其中x是 属性集 ，y 是记录类别 l分类的任务: 通过学习得到一个分类模型，其将属性集 x 映 射到某个类别 y 数据挖掘导论 * 3 分类任务示例 任务属性集, x类标签, y 邮件分类特征提取：电子邮件消息 头和内容 垃圾邮件 正常邮件 识别肿瘤细 胞 特征提取：核磁共振扫描 良性肿瘤 恶性肿瘤 星系分类特征提取：天文望远镜图 像 椭圆状星系 形状不规则星系等 数据挖掘导论 * 4 构建分类模型的一般方法 数据挖掘导论 * 5 分类技术 l基本分类算法 决策树方法：Decision Tree based Methods 支持向量机：Support Vector Machines 基于规则的方法：Rule-based Methods 最近邻法：Nearest-neighbor 神经网络：Neural Networks 朴素贝叶斯：Nave Bayes l集成学习算法 Boosting, Bagging, Random Forests 数据挖掘导论 * 6 决策树方法分类任务学习 数据挖掘导论 * 7 决策树方法分类任务学习 否 训练集分类模型：决策树 数据挖掘导论 * 8 决策树方法分类任务学习 是否有房 否否 划分属性 否是 训练集分类模型：决策树 数据挖掘导论 * 9 决策树方法分类任务学习 是否有房 婚姻状况 是 否 否 划分属性 否是 未婚、离异已婚 训练集分类模型：决策树 数据挖掘导论 * 10 决策树方法分类任务学习 是否有房 婚姻状况 月收入 是否 否 否 划分属性 否是 未婚、离异已婚 训练集分类模型：决策树 80008000 数据挖掘导论 * 11 决策树方法分类任务学习 是否有房 婚姻状况 月收入 是否 否 否 划分属性 否是 未婚、离异已婚 训练集分类模型：决策树 80008000 数据挖掘导论 * 12 决策树方法分类任务学习 训练集分类模型：决策树 婚姻状况 是否有房 月收入 是否 否 否 对于一个数据集通过学习可以得到多个决策树 已婚未婚、离异 是否 80008000 数据挖掘导论 * 13 决策树方法分类任务学习 是否有房 婚姻状况 月收入 拖欠=否 拖欠=否 拖欠=否 划分属性 否是 未婚、离异已婚 训练集分类模型：决策树 80008000 拖欠=是 数据挖掘导论 * 14 决策树方法分类任务学习 训练集分类模型：决策树 婚姻状况 是否有房 月收入 拖欠=是拖欠=否 拖欠=否 拖欠=否 对于一个数据集通过学习可以得到多个决策树 已婚未婚、离异 是否 80008000 数据挖掘导论 * 15 决策树方法分类任务应用 数据挖掘导论 * 16 将分类模型应用于测试集 是否有房 婚姻状况 月收入 拖欠=否 拖欠=否 拖欠=否 决策树分类模型 否是 未婚、离异已婚 从树的根节点开始 测试集 80008000 拖欠=是 数据挖掘导论 * 17 将分类模型应用于测试集 是否有房 婚姻状况 月收入 拖欠=否 拖欠=否 拖欠=否 否是 未婚、离异已婚 测试集 80008000 拖欠=是 决策树分类模型 数据挖掘导论 * 18 将分类模型应用于测试集 是否有房 婚姻状况 月收入 拖欠=否 拖欠=否 拖欠=否 否是 未婚、离异已婚 测试集 80008000 拖欠=是 决策树分类模型 数据挖掘导论 * 19 将分类模型应用于测试集 是否有房 婚姻状况 月收入 拖欠=否 拖欠=否 拖欠=否 否是 未婚、离异已婚 测试集 80008000 拖欠=是 决策树分类模型 数据挖掘导论 * 20 将分类模型应用于测试集 是否有房 婚姻状况 月收入 拖欠=否 拖欠=否 拖欠=否 否是 未婚、离异已婚 测试集 80008000 拖欠=是 决策树分类模型 数据挖掘导论 * 21 将分类模型应用于测试集 是否有房 婚姻状况 月收入 拖欠=否 拖欠=否 拖欠=否 否是 未婚、离异已婚 是否拖欠贷款预测为“否” 测试集 80008000 拖欠=是 决策树分类模型 数据挖掘导论 * 22 决策树方法分类任务学习 数据挖掘导论 * 23 决策树归纳 l算法: Hunt 算法 (早期算法) CART ID3, C4.5 SLIQ,SPRINT 数据挖掘导论 * 24 Hunt 算法结构 l设 Dt 是与结点t相关联的训练集 l一般处理过程: 如果Dt 中所有记录都属于同 一类别yt, 则t是叶节点，用yt 标记 如果Dt 中包含属于多个类的 记录, 则选择一个属性，将 记录划分成较小的子集. 然 后对于每个子女结点，递归 的调用该算法. Dt ? 数据挖掘导论 * 25 Hunt 算法 数据挖掘导论 * 26 决策树归纳的问题 l如何划分训练样本? 表示属性测试条件的方法 u 取决于属性类型：二元属性，标称属性，序数属性 如何选择最佳划分的度量 l何时停止划分? 分裂结点，直到所有的记录都属于同一类别 提前终止 数据挖掘导论 * 27 表示属性测试条件的方法 l依赖于属性类别 二元属性 Binary 标称属性 Nominal 序数属性 Ordinal 连续属性 Continuous l依赖于划分的数目 二元划分 2-way split 多路划分 Multi-way split 数据挖掘导论 * 28 标称属性的属性测试条件 l多路划分: 输出数越多越好，取决于该属性 不同属性值的个数. l二元划分: 将该属性的所有属性值划分为两 个部分 需要寻找最优划分. 数据挖掘导论 * 29 序数属性的属性测试条件 l多路划分: 输出数越多越好，取决 于该属性不同属性值的 个数 l二元划分: 将该属性的所有属性值 划分为两个部分 需要寻找最优划分 不违背序数属性值的有 序性 这种方式违背了 序数属性值的有 序性 数据挖掘导论 * 30 连续属性的属性测试条件 数据挖掘导论 * 31 连续属性划分 l不同的处理方法 通过离散化形成一个序数分类属性 u 静态方法 在一开始进行离散化 u 动态方法范围可以通过等深分箱,等比分箱,或聚类 等方法 二元方式: (A v) 或者 (A v) u 考虑所有的划分方式，并从中选择一个最优的 u 可以处理密集型计算 数据挖掘导论 * 32 如何选择最优划分 划分前: 10 条记录是类 0, 10 条记录是类 1 哪一种测试条件是最优的? 数据挖掘导论 * 33 l贪婪方法: 选择纯度更高的结点来进行划分 l需要表明划分后子女结点不纯性的度量: 高不纯性低不纯性 如何选择最优划分 数据挖掘导论 * 34 结点不纯性度量 lGini指标值 lEntropy熵 lClassification error 分类误差 数据挖掘导论 * 35 寻找最优划分 1.计算划分前的不纯性度量值(P) 2.计算划分后的不纯性度量值(M) l计算每个子节点的不纯性度量 l计算子节点的平均不纯性度量(M) 3.选择具有最大增益的属性作为属性测试条件 也就是，具有划分后具有最小不纯性度量值的属 性(M) Gain = P M 数据挖掘导论 * 36 寻找最优划分 B? YesNo Node N3Node N4 A? YesNo Node N1Node N2 划分前:P M11M12M21M22 M1M2 Gain = P M1 vs P M2 数据挖掘导论 * 37 不纯性度量: GINI l结点t的 Gini 指标值的计算公式如下: (注意: p( j | t) 表示给的结点t中属于类别j的记录所占的比例). 最大值 (1 - 1/nc) ：当各个样本等可能的属于各个类别, 意味着蕴含最少信息 最小值 (0.0) ：当所有记录都属于同一类别, 意味着蕴 含最多信息 数据挖掘导论 * 38 计算单个结点的Gini指标值 P(C1) = 0/6 = 0 P(C2) = 6/6 = 1 Gini = 1 P(C1)2 P(C2)2 = 1 0 1 = 0 P(C1) = 1/6 P(C2) = 5/6 Gini = 1 (1/6)2 (5/6)2 = 0.278 P(C1) = 2/6 P(C2) = 4/6 Gini = 1 (2/6)2 (4/6)2 = 0.444 数据挖掘导论 * 39 计算一组结点的Gini指标值 l当结点p被划分为k个划分部分时(子结点) 其中,ni = 子结点i中的样本记录数目, n = 父节点p中的样本记录数目. l选择具有最小值的子结点加权平均Gini指标值的属性进行 划分 lCART, SLIQ, SPRINT决策树算法使用GINI指标值来进行 划分 数据挖掘导论 * 40 二元属性: 计算GINI指标值 l划分为两个部分 l需要进行加权平均，是因为: 寻求更大、更纯的划分. B? YesNo Node N1Node N2 Gini(N1) = 1 (5/6)2 (1/6)2 = 0.278 Gini(N2) = 1 (2/6)2 (4/6)2 = 0.444 Gini(Children) = 6/12 * 0.278 + 6/12 * 0.444 = 0.361 数据挖掘导论 * 41 标称属性: 计算Gini指标值 l对于每一个属性值, 计算数据集中每一个类别的样本数量 l使用计数矩阵进行决策 多路划分二元划分 (寻找最优划分) 数据挖掘导论 * 42 连续属性: 计算Gini指标值 l进行二元决策 l有多个划分点可供选择 可能的划分点的数目 = 不同的属性值的数目 l每一个划分点都有一个计数矩阵与之关 联 每一个划分中不同类别样本的数目, A v 和 A v l选择最优v的简单方法 对于每一个候选v, 扫描数据库获得 计数矩阵并计算相应的 Gini 指标值 缺点： u计算效率低下! u重复的工作. 数据挖掘导论 * 43 连续属性: 计算Gini指标值 l更高效的计算方式: 首先对某一属性值进行排序 从两个相邻的排过序的属性值中选择中间值作为候选划分 点，计算其Gini指标值 重复这样的计算，直到算出所有后续的Gini指标值，最佳划 分点对应于最小Gini指标值的点 划分点 排序后的值 数据挖掘导论 * 44 不纯性度量: 熵Entropy l结点t的熵Entropy的计算公式如下: (注意: p( j | t) 表示给的结点t中属于类别j的记录所占的比例). u最大值(log nc) ：当各个样本等可能的属于各个类别,意味 着蕴含最少信息 u最小值 (0.0) ：当所有记录都属于同一类别, 意味着蕴含 最多信息 数据挖掘导论 * 45 计算单个结点的熵Entropy P(C1) = 0/6 = 0 P(C2) = 6/6 = 1 Entropy = 0 log 0 1 log 1 = 0 0 = 0 P(C1) = 1/6 P(C2) = 5/6 Entropy = (1/6) log2 (1/6) (5/6) log2 (1/6) = 0.65 P(C1) = 2/6 P(C2) = 4/6 Entropy = (2/6) log2 (2/6) (4/6) log2 (4/6) = 0.92 数据挖掘导论 * 46 计算划分后的信息增益 l信息增益 Information Gain: 父节点p被划分为k个划分部分; ni 是划分部分i中的记录数目 最大化增益 经典决策树算法ID3和C4.5都使用信息增益来进行划分 数据挖掘导论 * 47 采用信息增益进行划分带来的问题 l信息增益倾向于将样本记录划分为最大数量的部分 ，每一个部分中的样本的类别都是小而纯的： Customer ID 具有最高的信息增益，因为它的 所有子结点的熵都是0 数据挖掘导论 * 48 增益率 Gain Ratio l增益率: 父节点p被划分为k个划分部分; ni 是划分部分i中的记录数目 通过划分的熵调整信息增益 (SplitINFO). u高entropy的划分往往不是一个好的划分 (划分的数量过多) 在C4.5算法里被使用 可克服信息增益的不足 数据挖掘导论 * 49 不纯性度量: 分类误差 l结点t的分类误差不纯性度量计算公式如下 : 最大值 (1 - 1/nc) ：当各个样本等可能的属于各个类别, 意味着蕴含最少信息 最小值 (0.0) ：当所有记录都属于同一类别, 意味着蕴含 最多信息 数据挖掘导论 * 50 计算单个结点的分类误差 P(C1) = 0/6 = 0 P(C2) = 6/6 = 1 Error = 1 max (0, 1) = 1 1 = 0 P(C1) = 1/6 P(C2) = 5/6 Error = 1 max (1/6, 5/6) = 1 5/6 = 1/6 P(C1) = 2/6 P(C2) = 4/6 Error = 1 max (2/6, 4/6) = 1 4/6 = 1/3 数据挖掘导论 * 51 不纯性度量之间的比较 对于二元分类问题: 数据挖掘导论 * 52 分类误差 vs Gini指标值 A? YesNo Node N1Node N2 Gini(N1) = 1 (3/3)2 (0/3)2 = 0 Gini(N2) = 1 (4/7)2 (3/7)2 = 0.489 Gini(Children) = 3/10 * 0 + 7/10 * 0.489 = 0.342 Gini improves but error