数据挖掘：决策树算法及应用拓展.ppt

决策树生成 基本思想： 用途：提取分类规则，进行分类预测 决策树示意图 使用决策树进行分类 决策树 一个树性的结构 内部节点上选用一个属性进行分割 每个分叉都是分割的一个部分 叶子节点表示一个分布 决策树生成算法分成两个步骤 树的生成 开始，数据都在根节点 递归的进行数据分片 树的修剪 去掉一些可能是噪音或者异常的数据 决策树使用: 对未知数据进行分割 按照决策树上采用的分割属性逐层往下，直到叶子节点 决策树算法 基本算法（贪心算法） 自上而下分而治之的方法 开始时，所有的数据都在根节点 属性都是种类字段 (如果是连续的，将其离散化) 所有记录用所选属性递归的进行分割 属性的选择是基于一个启发式规则或者一个统计的度量 (如, information gain) 停止分割的条件 一个节点上的数据都是属于同一个类别 没有属性可以再用于对数据进行分割 伪代码(Building Tree) Procedure BuildTree(S) 用数据集S初始化根节点R 用根结点R初始化队列Q While Q is not Empty do { 取出队列Q中的第一个节点N if N 不纯 (Pure) { for 每一个属性 A 估计该节点在A上的信息增益 选出最佳的属性，将N分裂为N1、N2 } } 属性选择的统计度量 信息增益——Information gain (ID3/C4.5) 所有属性假设都是种类字段 经过修改之后可以适用于数值字段 基尼指数——Gini index (IBM IntelligentMiner) 能够适用于种类和数值字段 信息增益度度量(ID3/C4.5) 任意样本分类的期望信息： I(s1,s2,……,sm)=－∑Pi log2(pi) (i=1..m) 其中，数据集为S，m为S的分类数目， Pi Ci为某分类标号，Pi为任意样本属于Ci的概率， si为分类Ci上的样本数 由A划分为子集的熵： E(A)= ∑(s1j+ ……+smj)/s * I(s1j+ ……+smj) A为属性，具有V个不同的取值 信息增益：Gain(A)= I(s1,s2,……,sm) － E(A) 训练集(举例) 使用信息增益进行属性选择 Class P: buys_computer = “yes” Class N: buys_computer = “no” I(p, n) = I(9, 5) =0.940 Compute the entropy for age: Hence Similarly Decision Tree (结果输出) 贝叶斯分类器 描述用到的符号 练 习 一个销售的顾客数据集，对购买计算机的人员进行分类： 字段为：年龄（取值：30，30~40 ， 40）; 收入（高，中，低） ; 学生否（Y，N） ; 信用（一般，很好） ; 购买计算机否（Y，N） ; 记录为14人，具体数据如下： x1=（30, 高, N ,一般, N）; x2=（30, 高, N ,很好, N）; x3=（30~40, 高, N ,一般, Y ）; x4=（40, 中, N ,一般, Y）; x5=（40, 低, Y ,一般, Y ）; x6=（ 40, 低, Y ,很好, N）; x7=（30~40,低, Y ,高, Y ）; x8=（30, 中, N ,一般, N）; x9=（30,低, Y ,一般, Y ）; x10=（40, 中, Y ,一般, Y）; x11=（30, 中, Y,很好, Y ）; x12=（30~40, 中, N ,很好, Y）; x13=（30~40, 高, Y ,一般, Y ）; x14=（40, 中, N ,很好, N）; 实验结果 70.0 99.5 83.9 87.1 87.4 测试精度 0.055 0.010 71.0 96 871 TIC-TAC-TOE 0.003 0.000 99.5 727 6546 Mushroom 0.033 0.005 86.1 28 251 heart 0.053 0.011 89.2 16 148 Hatehi 0.056 0.003 91.4 63 571 BALANCE 标准差 标准差 训练精度 测试样例 训练样例 数据库 结果分析 从上面的实验结果我们可以得到朴素贝叶斯分类器的以下几个特点: 训练精度≈测试精度 意义明确,便于理解 时间复杂度低,可以应用大型数据库 易于实现增量 * * 判定树分类