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

1、分类: 基本概念与决策树,Dr. Haitao Xiong BTBU,分类: 定义,给定多条记录的集合 (数据集) 每一条记录都通过元组 (x, y)来表示，其中x是属性集 ，y 是记录类别 分类的任务: 通过学习得到一个分类模型，其将属性集 x 映射到某个类别 y,分类任务示例,构建分类模型的一般方法,分类技术,基本分类算法 决策树方法：Decision Tree based Methods 支持向量机：Support Vector Machines 基于规则的方法：Rule-based Methods 最近邻法：Nearest-neighbor 神经网络：Neural Networks 朴

2、素贝叶斯：Nave Bayes 集成学习算法 Boosting, Bagging, Random Forests,决策树方法分类任务学习,决策树方法分类任务学习,否,训练集,分类模型：决策树,决策树方法分类任务学习,是否有房,否,否,划分属性,否,是,训练集,分类模型：决策树,决策树方法分类任务学习,是否有房,婚姻状况,是,否,否,划分属性,否,是,未婚、离异,已婚,训练集,分类模型：决策树,决策树方法分类任务学习,是否有房,婚姻状况,月收入,是,否,否,否,划分属性,否,是,未婚、离异,已婚,训练集,分类模型：决策树,8000,8000,决策树方法分类任务学习,是否有房,婚姻状况,月收入,是

3、,否,否,否,划分属性,否,是,未婚、离异,已婚,训练集,分类模型：决策树,8000,8000,决策树方法分类任务学习,训练集,分类模型：决策树,婚姻状况,是否有房,月收入,是,否,否,对于一个数据集通过学习可以得到多个决策树,已婚,未婚、离异,是,否,8000,8000,决策树方法分类任务学习,是否有房,婚姻状况,月收入,拖欠=否,拖欠=否,拖欠=否,划分属性,否,是,未婚、离异,已婚,训练集,分类模型：决策树,8000,8000,拖欠=是,决策树方法分类任务学习,训练集,分类模型：决策树,婚姻状况,是否有房,月收入,拖欠=是,拖欠=否,拖欠=否,对于一个数据集通过学习可以得到多个决策树,已

4、婚,未婚、离异,是,否,8000,8000,决策树方法分类任务应用,将分类模型应用于测试集,是否有房,婚姻状况,月收入,拖欠=否,拖欠=否,拖欠=否,决策树分类模型,否,是,未婚、离异,已婚,从树的根节点开始,测试集,8000,8000,拖欠=是,将分类模型应用于测试集,是否有房,婚姻状况,月收入,拖欠=否,拖欠=否,拖欠=否,否,是,未婚、离异,已婚,测试集,8000,8000,拖欠=是,决策树分类模型,将分类模型应用于测试集,是否有房,婚姻状况,月收入,拖欠=否,拖欠=否,拖欠=否,否,是,未婚、离异,已婚,测试集,8000,8000,拖欠=是,决策树分类模型,将分类模型应用于测试集,是否

5、有房,婚姻状况,月收入,拖欠=否,拖欠=否,拖欠=否,否,是,未婚、离异,已婚,测试集,8000,8000,拖欠=是,决策树分类模型,将分类模型应用于测试集,是否有房,婚姻状况,月收入,拖欠=否,拖欠=否,拖欠=否,否,是,未婚、离异,已婚,测试集,8000,8000,拖欠=是,决策树分类模型,将分类模型应用于测试集,是否有房,婚姻状况,月收入,拖欠=否,拖欠=否,拖欠=否,否,是,未婚、离异,已婚,是否拖欠贷款预测为“否”,测试集,8000,8000,拖欠=是,决策树分类模型,决策树方法分类任务学习,决策树归纳,算法: Hunt 算法 (早期算法) CART ID3, C4.5 SLIQ,S

6、PRINT,Hunt 算法结构,设 Dt 是与结点t相关联的训练集 一般处理过程: 如果Dt 中所有记录都属于同一类别yt, 则t是叶节点，用yt标记 如果Dt 中包含属于多个类的记录, 则选择一个属性，将记录划分成较小的子集. 然后对于每个子女结点，递归的调用该算法.,Dt,?,Hunt 算法,决策树归纳的问题,如何划分训练样本? 表示属性测试条件的方法 取决于属性类型：二元属性，标称属性，序数属性 如何选择最佳划分的度量 何时停止划分? 分裂结点，直到所有的记录都属于同一类别 提前终止,表示属性测试条件的方法,依赖于属性类别 二元属性 Binary 标称属性 Nominal 序数属性 Or

7、dinal 连续属性 Continuous 依赖于划分的数目 二元划分 2-way split 多路划分 Multi-way split,标称属性的属性测试条件,多路划分: 输出数越多越好，取决于该属性不同属性值的个数. 二元划分: 将该属性的所有属性值划分为两个部分 需要寻找最优划分.,序数属性的属性测试条件,多路划分: 输出数越多越好，取决于该属性不同属性值的个数 二元划分: 将该属性的所有属性值划分为两个部分 需要寻找最优划分 不违背序数属性值的有序性,这种方式违背了序数属性值的有序性,连续属性的属性测试条件,连续属性划分,不同的处理方法 通过离散化形成一个序数分类属性 静态方法 在一开

8、始进行离散化 动态方法范围可以通过等深分箱,等比分箱,或聚类等方法 二元方式: (A v) 或者 (A v) 考虑所有的划分方式，并从中选择一个最优的 可以处理密集型计算,如何选择最优划分,划分前: 10 条记录是类 0, 10 条记录是类 1,哪一种测试条件是最优的?,贪婪方法: 选择纯度更高的结点来进行划分 需要表明划分后子女结点不纯性的度量:,高不纯性,低不纯性,如何选择最优划分,结点不纯性度量,Gini指标值 Entropy熵 Classification error 分类误差,寻找最优划分,计算划分前的不纯性度量值(P) 计算划分后的不纯性度量值(M) 计算每个子节点的不纯性度量 计

9、算子节点的平均不纯性度量(M) 选择具有最大增益的属性作为属性测试条件也就是，具有划分后具有最小不纯性度量值的属性(M),Gain = P M,寻找最优划分,B?,Yes,No,Node N3,Node N4,A?,Yes,No,Node N1,Node N2,划分前:,Gain = P M1 vs P M2,不纯性度量: GINI,结点t的 Gini 指标值的计算公式如下: (注意: p( j | t) 表示给的结点t中属于类别j的记录所占的比例). 最大值 (1 - 1/nc) ：当各个样本等可能的属于各个类别,意味着蕴含最少信息 最小值 (0.0) ：当所有记录都属于同一类别, 意味着蕴

10、含最多信息,计算单个结点的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,计算一组结点的Gini指标值,当结点p被划分为k个划分部分时(子结点) 其中,ni = 子结点i中的样本记录数目, n = 父节点p中的样本记录数目. 选择具有最小值的子结点加权平均Gini指标值的属性进

11、行划分 CART, SLIQ, SPRINT决策树算法使用GINI指标值来进行划分,二元属性: 计算GINI指标值,划分为两个部分 需要进行加权平均，是因为: 寻求更大、更纯的划分.,B?,Yes,No,Node N1,Node 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,标称属性: 计算Gini指标值,对于每一个属性值, 计算数据集中每一个类别的样本数量 使用计数矩阵进行决策,多路划分,二

12、元划分 (寻找最优划分),连续属性: 计算Gini指标值,进行二元决策 有多个划分点可供选择 可能的划分点的数目 = 不同的属性值的数目 每一个划分点都有一个计数矩阵与之关联 每一个划分中不同类别样本的数目, A v 和 A v 选择最优v的简单方法 对于每一个候选v, 扫描数据库获得计数矩阵并计算相应的 Gini 指标值 缺点： 计算效率低下! 重复的工作.,连续属性: 计算Gini指标值,更高效的计算方式: 首先对某一属性值进行排序 从两个相邻的排过序的属性值中选择中间值作为候选划分点，计算其Gini指标值 重复这样的计算，直到算出所有后续的Gini指标值，最佳划分点对应于最小Gini指标

13、值的点,排序后的值,不纯性度量: 熵Entropy,结点t的熵Entropy的计算公式如下: (注意: p( j | t) 表示给的结点t中属于类别j的记录所占的比例). 最大值(log nc) ：当各个样本等可能的属于各个类别,意味着蕴含最少信息 最小值 (0.0) ：当所有记录都属于同一类别, 意味着蕴含最多信息,计算单个结点的熵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)

14、 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,计算划分后的信息增益,信息增益 Information Gain: 父节点p被划分为k个划分部分; ni 是划分部分i中的记录数目 最大化增益 经典决策树算法ID3和C4.5都使用信息增益来进行划分,采用信息增益进行划分带来的问题,信息增益倾向于将样本记录划分为最大数量的部分，每一个部分中的样本的类别都是小而纯的： Customer ID 具有最高的信息增益，因为它的所有子结点的熵都是0,增益率 Gain R

15、atio,增益率: 父节点p被划分为k个划分部分; ni 是划分部分i中的记录数目 通过划分的熵调整信息增益 (SplitINFO). 高entropy的划分往往不是一个好的划分 (划分的数量过多) 在C4.5算法里被使用 可克服信息增益的不足,不纯性度量: 分类误差,结点t的分类误差不纯性度量计算公式如下 : 最大值 (1 - 1/nc) ：当各个样本等可能的属于各个类别,意味着蕴含最少信息 最小值 (0.0) ：当所有记录都属于同一类别, 意味着蕴含最多信息,计算单个结点的分类误差,P(C1) = 0/6 = 0 P(C2) = 6/6 = 1 Error = 1 max (0, 1) =

16、 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,不纯性度量之间的比较,对于二元分类问题:,分类误差 vs Gini指标值,A?,Yes,No,Node N1,Node 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 remains t