数据挖掘原理与spssclementine应用宝典元昌安主编邓松.ppt

第9章　决策树算法 数据挖掘原理与SPSS Clementine应用宝典 元昌安 主编　 邓　松　李文敬　刘海涛　编著 电子工业出版社 第9章 决策树算法 本章大纲： 决策树算法原理 常用决策树算法 决策树剪枝 由决策树提取分类规则 应用实例分析 9.1 决策树算法原理 优点： 使用者不需要了解很多背景知识，只要训练事例能用属性→结论的方式表达出来，就能用该算法学习； 决策树模型效率高，对训练集数据量较大的情况较为适合； 分类模型是树状结构，简单直观，可将到达每个叶结点的路径转换为IF→THEN形式的规则，易于理解； 决策树方法具有较高的分类精确度。 9.1 决策树算法原理 传统的数据分类操作通常有以下两个步骤: 模型训练阶段：根据给定的训练集，找到合适的映射函数H:→C的表示模型。 使用上一步训练完成的函数模型预测数据的类别，或利用该函数模型，对数据集中的每一类数据进行描述，形成分类规则。 9.1 决策树算法原理 工作过程： 9.1 决策树算法原理 定义 9.1 给定一个训练数据集D＝，其中每个实例，称为例子，训练数据集中包含以下属性A=。同时给定类别集合C。对于训练数据集D，决策树是指具有以下性质的树： 每个内部节点都被标记一个属性Ai。 每个弧都被标记一个值，这个值对应于相应父结点的属性。 每个叶节点都被标记一个类Cj。 9.1 决策树算法原理 定义9.2 分裂准则 定义为在决策树算法中将训练数据集D中的元组划分为个体类的最好的方法与策略，它告诉我们在节点N上测试哪个属性合适，如何选择测试与测试的方法，从节点N上应该生长出哪些分支。 定义9.3 分裂属性Xi定义为决策树中每个内部节点都对应的一个用于分裂数据集的属性。Xi A= 9.1 决策树算法原理 定义9.4 如果Xi是连续属性，那么分裂准则的形式为Xi，其中，就称为节点n的分裂点。 定义9.5 如果Xi是离散属性，那么的形式为，其中，就称为节点n的分裂子集。 注意：分裂准则与分裂属性、分裂点、分裂子集并不等同，它们是四个不同的概念，并且分裂子集分裂点分裂属性分裂准则 9.1 决策树算法原理 将上面的定义结合实际的决策树例子可得决策树图如下图9-1，图9-2，图9-3所示，图中设X为分裂属性，是属性X的已知值。 9.1 决策树算法原理 9.1 决策树算法原理 图9-4 按照分裂子集划分而成的决策树（只能是二叉树）图与相关的具体例子图 9.1 决策树算法原理 目前主要使用如下几个量化评估标准 (1)预测准确性 (2)模型强健性 (3)描述的简洁性 (4)计算复杂性 (5)处理规模性 9.2 常用决策树算法 ID3算法 ID3是Quinlan于1986年提出的，是机器学习中一种广为人知的一个算法，它的提出开创了决策树算法的先河，而且是国际上最早最有影响的决策树方法，在该算法中，引入了信息论中熵的概念，利用分割前后的熵来计算信息增益，作为判别能力的度量。 9.2.1 ID3算法 定义9.6 信息熵 自信息量只能反映符号的不确定性，而信息熵可以用来度量整个信源X整体的不确定性。设某事物具有n种相互独立的可能结果(或称状态)： ，每一种结果出现的概率分别为 且有： （9.1） 那么，该事物所具有的不确定量为： （9.2） 9.2.1 ID3算法 上式即为著名的香农信息量公式。注意到式中的对数以2为底，当n=2时且时，熵=1比特。由此可见，一个等概率的二选一事件具有1比特的不确定性。所以，可以把一个等概率的二选一事件所具有信息量定为信息量的单位。任何一个事件能够分解成n个可能的二选一事件，它的信息量就是n比特。 9.2.1 ID3算法 Quinlan的