分类挖掘决策树.pptx

分类挖掘：决策树;决策树算法概述;分类预测;决策树算法概述;1 建立决策树，利用训练样本生成决策树模型。 开始，数据都在根节点 递归的进行数据分片 2 修剪决策树 去掉一些可能是噪音或者异常的数据 3 使用决策树对未知数据进行分类 按照决策树上采用的分割属性逐层往下，直 到一个叶子节点 ;决策树的核心问题;决策树的核心问题;训练集(Train)：数据库中为建立模型而被分析的数据元组形成训练集。 训练集中的单个元组称为训练样本,每个训练样本有一个类别标记。一个??体样本的形式可为:( v1, v2, ..., vn; c );其中vi表示属性值,c表示类别。 测试集(Test)：用于模型参数的估计，评估分类模型的准确率。 验证集(Validation):用于模型误差的估计。;a.模型训练阶段 训练集 b.使用模型 分类阶段 评估准确率〔测试集〕 对类标号未知的新 数据分类 ;根本算法 自上而下分而治之的方法 开始时，所有的数据都在根节点 所有记录用所选属性递归的进行分割 属性的选择是基于一个启发式规那么或者一个统计的度量 (如, information gain) 停止分割的条件 一个节点上的数据都是属于同一个类别 没有属性可以再用于对数据进行分割; 建树阶段 MakeTree (Training Data T) Partition (T);Partition (Data S) if (all points in S are in the same class) then return; evaluate splits for each attribute A Use best split found to partition S into S1 and S2; Partition (S1); Partition (S2);;属性选择度量标准－－分支指标; 1、信息是用来消除随机不确定性的度量。信息量的大小可由所消除的不确定性大小来计量。 信息量的数学定义： 2、信息熵是信息量的数学期望，是信源发出信息前的平均不确定性，也称先验熵，信息熵的数学定义为： ;1、信源熵H(X) 信源熵是度量整个信源X整体的平均不确定性，也称先验熵。 2、条件熵H(X/Y) 条件熵是一个确定值，表示收信者在收到Y后，信源X仍然存在的不确定度，也称为后验熵。 3、互信息量 熵差H(X)－H(X/Y)是不确定性的消除，即互信息才是接收端所获得的信息量。 ; ID3算法是借用信息论中的互信息寻找训练集具有最大信息量的属性字段，建立决策树的一个节点，再根据该属性字段的不同取值建立树的分支;在每个分支子集中重复建立树的下层节点和分支过程。 ;?;ID3Tree (T，T-attributelist) T为样本空间，T-attributelist为属性集。 (1) 创立根结点N。 (2) IF T都属于同一类C，那么返回N为叶结点，标记为类C。 (3) IF T-attributelist为空或T中所剩的样本数少于某给定值，那么返回N为叶结点，标记为T中出现最多的类。 (4)??FOR EACH T-attributelist中的属性，计算信息增益information gain。 (5) 结点N的分裂属性为T-attributelist中具有最高信息增益的属性。 (6)??FOR EACH由结点N长出的新结点{ IF 该结点对应的样本子集只有唯一的一种决策类别， 那么将该结点标记为该类别的叶结点; ELSE 在该结点上执行ID3Tree (T’，T’-attributelist)，对它继续进行分裂;} 其中，T’为由结点N划分而来的子集，T’-attributeslit为去除被选分裂属性后的属性集。 ; 用决策树考察某顾客是否会购置PC; 类标号属性为购置PC，它有两个不同的值(“是〞、“否〞)，即有两个不同的类，m=2；设p对应“是〞，n对应“否〞，那么p=9，n=5。 1) 创立根结点 先计算对给定样本分类所需的期望信息。 = 0.94 下面计算每个属性的熵。从年龄开始计算。 年龄=“=30〞： p11=2，n11=3 I (p11，n11)=0.971 年龄=“30~40〞： p12=4，n12=0 I (p12，n12)=0 年龄=“40〞： p13=3，n13=2 I (p13，n13)=0.971 如果样本按年龄划分，对一个给定的样本分类所需的期望信息如下