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