教材配套教学——第2章基本数据挖掘技术.ppt

清华大学出版社 第2章 基本数据挖掘技术 之一 决策树 本章目标 决策树 了解决策树的概念； 了解C4.5决策树建立过程、关键技术、和决策树规则； 了解其他决策树算法。 关联规则 了解关联规则； 掌握Apriori关联分析过程。 聚类分析 掌握K-均值算法。 了解数据挖掘技术的选择考虑。 * 第*页，共28页 2.1 决策树 决策树学习 从数据产生决策树的机器学习技术称为决策树学习，简称决策树（Decision Tree）。 决策树是数据挖掘中最常用的一种分类和预测技术，使用其可建立分类和预测模型。 决策树模型是一个树状结构，树中每个节点表示分析对象的某个属性，每个分支表示这个属性的某个可能的取值，每个叶节点表示经历从根节点到该叶节点这条路径上的对象的值。模型通过树中的各个分支对对象进行分类，叶节点表示的对象值表达了决策树分类的结果。决策树仅有一个输出，若需要有多个输出，可以建立多棵独立的决策树以处理不同输出。 * 第*页，共28页 2.1.1 决策树算法的一般过程（C4.5） （1）给定一个表示为“属性-值”格式的数据集T。数据集由多个具有多个输入属性和一个输出属性的实例组成。 （2）选择一个最能区别T中实例的输入属性，C4.5使用增益率来选择该属性。 （3）使用该属性创建一个树节点，同时创建该节点的分支，每个分支为该节点的所有可能取值。 （4）使用这些分支，将数据集中的实例进行分类，成为细分的子类。 （5）将当前子类的实例集合设为T，对数据集中的剩余属性重复（2）（3）步，直到满足以下两个条件之一时，该过程终止，创建一个叶子节点，该节点为沿此分支所表达的分类类别，其值为输出属性的值。 该子类中的实例满足预定义的标准，如全部分到一个输出类中，分到一个输出类中的实例达到某个比例； 没有剩余属性。 * 第*页，共28页 【例2.1】 给定如表2.1所示的数据集T，建立一棵决策树，用于预测某个学生是否决定去打篮球。 表2.1 一个假想的打篮球数据集 * 第*页，共28页 序号 Weather Temperature/?C Courses Partner Play 1 Sunny 20~30 4 Yes Yes 2 Sunny 20~30 4 No Yes 3 Rain 10~0 1 Yes Yes 4 Sunny 30~40 5 Yes Yes 5 Rain 20~30 8 No No 6 Sunny -10~0 5 Yes Yes 7 Sunny -10~0 7 No No 8 Rain 20~30 2 Yes Yes 9 Rain 20~30 6 Yes No 10 Sunny 10~20 6 Yes No 11 Rain 10~20 3 No No 12 Rain 10~20 1 Yes No 13 Sunny 10~20 8 Yes No 14 Sunny 0~10 3 Yes Yes 15 Rain 0~10 2 Yes No 决策树 使用15个实例进行有训练，其中Weather、Temperature、Courses和Partner作为输入属性，Play作为输出属性。 * 第*页，共28页 图2.1 打篮球决策树 2.1.2 决策树算法的关键技术 三项关键技术 （1）选择最能区别数据集中实例属性的方法 （2）剪枝方法 （3）检验方法 * 第*页，共28页 1、 选择最能区别数据集中实例属性的方法 C4.5使用了信息论（Information Theory）的方法，即使用增益率（Gain Ratio）的概念来选择属性； 目的是使树的层次和节点数最小，使数据的概化程度最大化。 C4.5选择的基本思想 选择具有最大增益率的属性作为分支节点来分类实例数据。 * 第*页，共28页 1）信息熵 1948年，克劳德·香农（Claude Shannon）提出“信息熵”（Information?Entropy）的概念 信息变化的平均信息量称为“信息熵”（信息量化） 在信息论中，信息熵是信息的不确定程度的度量。熵越大，信息就越不容易搞清楚，需要的信息量就越大，能传输的信息就越多。 * 第*页，共28页 2）信息增益（?Information?Gain） 信息增益表示当x取属性xi值时，其对降低x的熵的贡献大小。 信息增益值越大，越适于对x进行分类。 C4.5使用信息量和信息增益的概念计算所有属性的增益，并计算所有属性的增益率，选择值最大的属性来划分数据实例。 * 第*页，共28页 计算属性A的增益率的公式 其中，对于一组 I 实例，计算Gain(A) —— 2）信息增益（?Information?Gain） Info(I) 为当前数据集所有实例所表达的信息量 * 第*页，共28页  Info(I,A) 为根据属性 A 的 k 个