分类挖掘：决策树

2019/8/29决策树算法概述•决策树算法最早源于人工智能的机器学习技术，用以实现数据内在规律的探究和新数据对象的分类预测。•决策树算法属于有指导的学习。根结点叶结点内部结点兄弟结点2叉树多叉树分类预测•分类预测，就是通过向现有数据学习，使模型具备对未来新数据的分类预测能力。•数据包含：•输入变量•输出变量•分类和预测•分类：分类型输出变量•预测：数值型输出变量决策树算法概述•决策树的种类：•分类决策树：树叶结点所含样本的输出变量的众数就是分类结果。•回归决策树：树叶结点所含样本的输出变量的平均值就是预测结果。•利用决策树进行分类预测：•对新数据进行分类预测时，只需按照决策树的层次，从根结点开始依次对新数据输入变量值进行判断并进入不同的决策树分支，直至叶结点为止。•特点：分类预测是基于逻辑的。•IFTHEN•每个叶节点对应一条推理规则1建立决策树，利用训练样本生成决策树模型。开始，数据都在根节点递归的进行数据分片2修剪决策树去掉一些可能是噪音或者异常的数据3使用决策树对未知数据进行分类按照决策树上采用的分割属性逐层往下，直到一个叶子节点判定树分类算法output训练集决策树input2019/8/29决策树的核心问题•第一，决策树的生长，即利用训练样本集完成决策树的建立过程；1.如何从众多的输入变量中选择一个当前最佳的分组变量；2.如何从分组变量的众多取值中找到一个最佳的分割点。决策树的核心问题•第二，决策树的修剪，即利用检验样本集对形成的决策树进行优化处。•过度拟和（Overfitting）•预修剪（pre-pruning）、后修剪（post-pruning）训练集(Train)：数据库中为建立模型而被分析的数据元组形成训练集。训练集中的单个元组称为训练样本,每个训练样本有一个类别标记。一个具体样本的形式可为:(v1,v2,...,vn;c);其中vi表示属性值,c表示类别。测试集(Test)：用于模型参数的估计，评估分类模型的准确率。验证集(Validation):用于模型误差的估计。2019/8/29a.模型训练阶段训练集b.使用模型分类阶段评估准确率（测试集）对类标号未知的新数据分类2019/8/29•基本算法–自上而下分而治之的方法–开始时，所有的数据都在根节点–所有记录用所选属性递归的进行分割–属性的选择是基于一个启发式规则或者一个统计的度量(如,informationgain)•停止分割的条件–一个节点上的数据都是属于同一个类别–没有属性可以再用于对数据进行分割2019/8/29建树阶段MakeTree(TrainingDataT)Partition(T);Partition(DataS)if(allpointsinSareinthesameclass)thenreturn;evaluatesplitsforeachattributeAUsebestsplitfoundtopartitionSintoS1andS2;Partition(S1);Partition(S2);2019/8/29属性选择度量标准－－分支指标•信息增益——Informationgain（ID3）•增益比率——Gainration（C4.5,C5.0）•基尼指数——Giniindex(SLIQ，SPRINT)…………2019/8/291、信息是用来消除随机不确定性的度量。信息量的大小可由所消除的不确定性大小来计量。信息量的数学定义：2、信息熵是信息量的数学期望，是信源发出信息前的平均不确定性，也称先验熵，信息熵的数学定义为：信息论的基本概念)(log)(1log)(22iiiuPuPuI)(log)()(1log)()(22iiiiiiuPuPuPuPUEnt1、信源熵H(X)信源熵是度量整个信源X整体的平均不确定性，也称先验熵。2、条件熵H(X/Y)条件熵是一个确定值，表示收信者在收到Y后，信源X仍然存在的不确定度，也称为后验熵。3、互信息量熵差H(X)－H(X/Y)是不确定性的消除，即互信息才是接收端所获得的信息量。2019/8/29ID3算法是借用信息论中的互信息寻找训练集具有最大信息量的属性字段，建立决策树的一个节点，再根据该属性字段的不同取值建立树的分支;在每个分支子集中重复建立树的下层节点和分支过程。2019/8/2922(,)loglogppnnIpnpnpnpnpn2019/8/29ID3Tree(T，T-attributelist)T为样本空间，T-attributelist为属性集。(1)创建根结点N。(2)IFT都属于同一类C，则返回N为叶结点，标记为类C。(3)IFT-attributelist为空或T中所剩的样本数少于某给定值，则返回N为叶结点，标记为T中出现最多的类。(4)FOREACHT-attributelist中的属性，计算信息增益informationgain。(5)结点N的分裂属性为T-attributelist中具有最高信息增益的属性。(6)FOREACH由结点N长出的新结点{IF该结点对应的样本子集只有唯一的一种决策类别，则将该结点标记为该类别的叶结点;ELSE在该结点上执行ID3Tree(T’，T’-attributelist)，对它继续进行分裂;}其中，T’为由结点N划分而来的子集，T’-attributeslit为去除被选分裂属性后的属性集。2019/8/29用决策树考察某顾客是否会购买PC年龄收入是否学生信用购买PC=30高否中否=30高否优否31~40高否中是40中否中是40低是中是40低是优否31~40低是优是=30中否中否=30低是中是40中是中是=30中是优是31~40中否优是31~40高是中是40中否优否顾客数据表2019/8/29类标号属性为购买PC，它有两个不同的值(“是”、“否”)，即有两个不同的类，m=2；设p对应“是”，n对应“否”，则p=9，n=5。1)创建根结点先计算对给定样本分类所需的期望信息。=0.94下面计算每个属性的熵。从年龄开始计算。年龄=“=30”：p11=2，n11=3I(p11，n11)=0.971年龄=“30~40”：p12=4，n12=0I(p12，n12)=0年龄=“40”：p13=3，n13=2I(p13，n13)=0.971如果样本按年龄划分，对一个给定的样本分类所需的期望信息如下=0.694因此，这种划分的信息增益是：Gain(年龄)=I(P，N)-E(年龄)=0.246。同理可得Gain(收入)=0.029Gain(是否学生)=0.151Gain(信用)=0.048在所有的属性中，年龄的信息增益最高，被选作测试属性。创建一个根结点，用年龄标记，并对每个属性值引出一个分支。22(,)loglogppnnIpnpnpnpnpn2019/8/292)分支建立考虑分支“年龄=‘=30’”的结点。因为Gain(收入)=0.571Gain(学生)=0.971Gain(信用)=0.02所以分支“年龄=‘=30’”结点的测试属性为“学生”。考虑分支“年龄=31~40”的结点，由于所有记录属于同一类别“是”，所以分支“年龄=‘31~40’”的结点为叶结点。考虑分支“年龄=‘40’”的结点。因为Gain(收入)=0.02Gain(学生)=0.02Gain(信用)=0.971所以分支“年龄=‘40’”结点的测试属性为“信用”。考虑分支“学生=‘否’”的结点，由于所有记录属于同一类别“否”，所以分支“学生=‘否’”的结点为叶结点。考虑分支“学生=‘是’”的结点，由于所有记录属于同一类别“是”，所以分支“学生=‘是’”的结点为叶结点。考虑分支“信用=‘优’”的结点，由于所有记录属于同一类别“否”，所以分支“信用=‘否’”的结点为叶结点。考虑分支“信用=‘中’”的结点，由于所有记录属于同一类别“是”，所以分支“信用=‘是’”的结点为叶结点。2019/8/29建立的决策树：2019/8/292019/8/29C4.5(C5.0)算法1993年由Quinlan提出，采用信息增益比(信息率)来选择属性。克服偏向选择取值较多属性的缺点用阈值对属性划分，即把训练集中该属性的所有值划分到不同的区间中。用最常见值代替未知值规则存于二维数组中如：视为youth;视为middle_aged;视为senior.30age~[30,40]age40age？信息增益度量偏向于有许多输出的测试，即它倾向于选择具有大量值的属性。举个极端的例子：考虑充当唯一标识的属性PID。对PID的分裂将产生大量划分（与样本个数一样多），每个分类只包含一个样本，且每个划分都是纯的。2()111×(log)14110PIDInfoD()()()0.940PIDGainPIDInfoDInfoD对属性PID划分得到的信息增益最大，显然，这种划分对分类没有用处。使用分裂信息(splitinformation)将信息增益规范化。4.5C21()*logvjjAjDDSplitInfoDDD该值表示数据集按属性测试的个划分产生的信息。DAv增益率：()()()AGainAGainRatioASplitInfoD选择具有最大信息率的属性作为分裂属性。增益率income222()44×log141466×log141444×log14141.557incomeSplitInfoD()0.029()0.019()1.557incomeGainincomeGainRatioincomeSplitInfoD其他属性的信息率可类似求出。•在实际通信之前（决策树建立之前），输出变量对信宿来讲是完全随机的，其平均不确定性为：•决策树建立过程中，随着信宿接收到信息（输入变量如T1），则条件熵为：•信息增益：•T1作为最佳分组变量而非T3940.0)145(log145)149(log149)(log)()(1log)()(2222iiiiiiuPuPuPuPUEnt694.0))52(log52)53(log53(145))40(log40)44(log44(144))53(log53)52(log52(145))1|(log)1|(()1()1|(2222222jiijijjtuPtuPtPTUEnt将输出变量（是否购买）看作信源发出的信息U输入变量看作是信宿接收到的一系列信息V246.0694.0940.0)1|()()1,(TUEntUEntTUGains048.0892.0940.0)3|()()3,(TUEntUEntTUGains类别值多的输入变量比少的有更多的机会成为当前最佳分组变量C5.0算法:信息增益率686867.0))52(log52)53(log53(145))40(log40)44(log44(144))21(log21)21(log21(142))32(log32)31(log31(143))1|(log)1|(()1()1|(222222222jiijijjtuPtuPtPTUEnt253133.069686867.0940.0)1|()()1,(TUEntUEntTUGains信息增益率的数学定义为：)(/),(),(VEntVUGainVUGainsR132.0924174.1/2531.0))145(log145)144(log144)142(log142)143(log143/(2531.0)1,(2222TUGainsR•数值型输入变量•首先对它进行分组处理，分组方法采用基于MDLP的熵分组方法2、C5.0算法：数值型输入变量把连续值属性的值域分割为离散的区间集合。基于MDLP的熵分组方法。（Minim