数据挖掘：决策树算法及应用拓展.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=1m) 其中，数据集为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),训练集(举例),ID3算法,使用信息增益进行属性选择,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 (结果输出),age?,overcast,student?,credit rating?,no,yes,fair,excellent,=30,40,no,no,yes,yes,yes,3040,符号描述 贝叶斯理论 贝叶斯分类器 实验结果与分析,贝叶斯分类器,=A1A2.Am，是由所有未知类别的可能样本组成的集合； c=A1A2.AmC是由所有已知类别的样本组成的集合。D c是训练样例集合。 中的元素x表示为x = 。 c中的元素x表示为x = 。其中ai表示第i个属性的某个取值。,描述用到的符号,我们用Ai表示第i个属性，C表示决策属性；aik表示第i个属性的第k个取值，cj表示第j类；加上绝对值则表示相应的个数，如|Ai|表示第i个属性的取值个数，|cj|表示第j类样例个数。,设x是一个类别未知的数据样本，cj为某个类别，若数据样本x属于一个特定的类别cj，那么分类问题就是决定P(cj|x)，即在获得数据样本x时，确定x的最佳分类。所谓最佳分类，一种办法是把它定义为在给定数据集D中不同类别cj先验概率的条件下最可能（most probable）分类。贝叶斯理论提供了计算这种可能性的一种直接方法,更精确地讲，贝叶斯法则基于假设的先验概率、给定假设下观察到不同数据的概率，提供了一种计算假设概率的方法,贝叶斯定理,贝叶斯公式,先验概率P(cj),联合概率P(x|cj),后验概率P(cj|x),如果没有这一先验知识，那么可以简单地将每一候选类别赋予相同的先验概率。不过通常我们可以用样例中属于cj的样例数|cj|比上总样例数|D|来 近似，即,先验概率P(cj),P(cj)代表还没有训练数据前，cj拥有的初始概率。P(cj)常被称为cj的先验概率(prior probability) ，它反映了我们所拥有的关于cj是正确分类机会的背景知识,它应该是独立于样本的。,联合概率是指当已知类别为cj的条件下，看到样本x出现的概率。,联合概率P(x|cj),若设x = 则P(x|cj)= P(a1,a2am| cj),后验概率P(cj |x),即给定数据样本x时cj成立的概率,而这正是我们所感兴趣的,P(cj|x )被称为C的后验概率（posterior probability），因为它反映了在看到数据样本x后cj成立的置信度,贝叶斯分类,我们现在计算 P(cMAP|x) = max P(cj|x) j(1,|C|),则P(cMAP|x)称为最大后验概率 然后我们就把x分到cMAP类中,朴素贝叶斯分类器一,设x = ，为一个有m个属性的样例,= max P(a1,a2am|cj)P(cj) (1),P(cMAP|x)= max P(cj|x) j(1,|C|),= max P(cj|a1,a2am),朴素贝叶斯分类器基于一个简单的假定：在给定目标值时属性值之间相互条件独立。换言之，该假定说明给定实例的目标值情况下，观察到联合的a1,a2am的概率正好是对每个单独属性的概率乘积,朴素贝叶斯分类器二,(2),将(2) 式其代入(1)式中，可得到朴素贝叶斯分类器，如下,朴素贝叶斯分类器三,概括地讲，朴素贝叶斯学习方法需要估计不同的P(cj)和P(ai|cj)项，也就是它们在训练数据上的频率。然后使用公式(3)来分类新实例。,CNB=argmax P(cj),（3）,其中CNB表示朴素贝叶斯分类器输出的目标值。注意在朴素贝叶斯分类器中，须从训练数据中估计的不同P(ai|cj)项的数量只是不同的属性值数量乘以不同目标值数量这比要估计P(a1,a2am|cj)项所需的量小得多,举例说明,目标概念Play Tennis的训练样例,第一步统计个数,表1 类别为cj及在cj条件下Ai取ai的样例数,估计先验概率和条件概率,表2 先验概率P(cj) 和条件概率P(ai|cj),样例判别,现在假设有一个样例x x = Sunny,Hot,High,Weak,等于yes的概率 P(Yes|x) = p(Yes)*p(Sunny|Yes)* p(Hot|Yes)* p(High|Yes)* p(Weak|Yes)* =0.643*0.222*0.222*0.333*0.667 =0.007039,等于No的概率 P(No|x) = p(No)*p(Sunny| No)* p(Hot| No)* p(High| No)* p(Weak| No)* =0.357*0.6*0.4*0.8*0.4 =0.027418,max (P(Yes|x), P(No|x) ) = P(No|x) ,所以我们把x分类为No,概率为零,在大多数情况下，观察到的比例P(ai|cj)是对其真实概率的一个良好估计，但当|Ai=aiC=cj|很小时估计较差。特别是当|Ai=aiC=cj|等于0时，P(ai|cj)也等于0，如果将来的待估样例中，包含第i个属性的取值ai时，此概率项会在分类器中占统治地位。,概率为零之m-估计,一般采用m-估计来解决这个问题。 m-估计定义如下：,pi是将要确定的概率P(ai|cj)的先验概率，而m是等效样本大小的常量，它确定了对于观察到的数据如何衡量pi的作用。在缺少其他信息是选择p的一种典型方法是假定pi =1/|Ai|。也就是将nj个实际观察扩大，加上m个按pi分布的虚拟样本。,概率为零之个数比较,在本次实现中我们采用的不是m-估计，而是下面一种简单的0个数比较法。即下面的几条规则。在公式（3）中，对每一个类别j，统计P(ai|cj)=0的个数，记为zj。然后按以下3条规则得到CNB。,1.如果对任意的j，zj都为0，则直接按公式（3）得到CNB,3.如果对任意的j，zj不为0且不相等，则取zj最小者对应的类别作为CNB。若zj最小者不唯一，则对这些最小值对应的j采用第二条规则进行判别。,2.如果对任意的j，zj不为0且相等，则按公式（3）计算时只计算P(ai|cj)为非零的项,然后得到CNB,实验结果,结果分析,从上面的实验结果我们可以得到朴素贝叶斯分类器的以下几个特点:,训练精度测试精度 意义明确,便于理解 时间复杂度低,可以应用大型数据库 易于实现增量,练 习,一个销售的顾客数据集，对购买计算机的人员进行分类： 字段为：年龄（取值：40）; 收入（高，中，低） ; 学生否（Y，N） ; 信用（一般，很好） ; 购买计算机否（Y，N） ; 记录为14人，具体数据如下： x1=（40, 中, N ,一般, Y）; x5=（40, 低, Y ,一般, Y ）; x6=（ 40, 低, Y ,很好, N）; x7=（40, 中, Y ,一般, Y）; x11=（40, 中, N ,很好, N）;,第一步统计个数,表1 类别为cj及在cj条件下Ai取ai的样例数,估计先验概率和条件概率,表2 先验概率P(cj) 和条件概率P(ai|cj),样例判别,现在假设有一个样例x x = 年龄30，收入=中，学生否=Y，信用=一般,等于yes的概率 P(Yes|x) = p(Yes)*p(30|Yes)* p(收入=中|Yes)* p(学生=Y|Yes)* p(