《决策树原理与应用：C5.0》由会员分享，可在线阅读，更多相关《决策树原理与应用：C5.0（17页珍藏版）》请在金锄头文库上搜索。
1、决策树原理与应用：C5.0 分类预测指通过向现有数据的学习，使模型具备对未来新数据的预测能力。对于分类预测有这样几个重要，一是此模型使用的方法是归纳和提炼，而不是演绎。非数据挖掘类的软件的基本原理往往是演绎，软件能通过一系列的运算，用已知的公式对数据进行运算或统计。分类预测的基本原理是归纳，是学习，是发现新知识和新规律；二是指导性学习。所谓指导性学习，指数据中包含的变量不仅有预测性变量，还有目标变量；三是学习，模型通过归纳而不断学习。事实上，预测包含目标变量为连续型变量的预测和目标变量为分在变量的分类预测。两者虽然都是预测，但结合决策树算法和我们之前介绍过的时间序列算法知，二者还是有明显的差别
2、的。Clementine决策树的特点是数据分析能力出色，分析结果易于展示。决策树算法是应用非常广泛的分类预测算法。1.1决策树算法概述1.11什么是决策树决策树算法属于有指导的学习，即原数据必须包含预测变量和目标变量。决策树之所以如此命名，是因为其分析结果以一棵倒置的树的形式呈现。决策树由上到下依次为根节点、内部节点和叶节点。一个节点对应于数据中的一个字段，即一个字段即Question对数据进行一次划分。决策树分为分类决策树（目标变量为分类型数值）和回归决策树（目标变量为连续型变量）。分类决策树叶节点所含样本中，其输出变量的众数就是分类结果；回归树的叶节点所含样本中，其输出变量的平均值就是预测
3、结果。这一点需要格外注意。与其它分类预测算法不同的是，决策树基于逻辑比较（即布尔比较）。可以简单描述为：If（条件1）Then（结果1）；If（条件2）Then（结果2）。这样，每一个叶节点都对应于一条布尔比较的推理规则，对新数据的预测就正是依靠这些复杂的推理规则。在实际应用中，一个数据产生的推理规则是极为庞大和复杂的，因此对推理规则的精简是需要关注的。1.12决策树的几何理解将训练样本集（即操作中常说的Training Data）看做一个n维空间上的一个点，则上面我们提到的布尔比较后的推理规则就像是存在于这个n维空间中的“线”。决策树建立的过程形象上看，就是倒置的树生长的过程，其几何意义上是
4、，每个分枝（每条推理规则）完成对n维空间区域划分的过程。决策树正式生成，则n维空间正式划分完毕，则每一个小区域，代表一个叶节点。通常n维空间不易于理解，故采用倒置的树来表示此结果。需要注意的一点是，在划分过程中，要尽量做到不同类别的结果归于不同的“区域”。1.13决策树的核心问题：生成与修剪决策树核心问题有二。一是利用Training Data完成决策树的生成过程；二是利用Testing Data完成对决策树的精简过程。即前面我们提到的，生成的推理规则往往过多，精简是必需的。一、决策树的生长决策树生长过程的本质是对Training Data反复分组（分枝）的过程，当数据分组（分枝）不再有意义注
5、意，什么叫分组不再有意义时，决策树生成过程停止。因此，决策树生长的核心算法是确定数据分析的标准，即分枝标准。何为有意义呢？注意，当决策树分枝后结果差异不再显著下降，则继续分组没有意义。也就是说，我们分组的目的，是为了让输出变量在差异上尽量小，到达叶节点时，不同叶节点上的输出变量为相同类别，或达到用户指定的决策树停止生成的标准。这样，分枝准则涉及到两方面问题：1、如果从众多输入变量中选择最佳分组变量；2、如果从分组变量的众多取值中找到最佳分割点。不同的决策树算法，如C4.5、C5.0、Chaid、Quest、Cart采用了不同策略。二、决策树的修剪完整的决策树并不是一棵分类预测新数据对象的最佳树
6、。其原因是完整的决策树对Training Data描述过于“精确”。我们知道，随着决策树的生长，决策树分枝时所处理的样本数量在不断减少，决策树对数据总体珠代表程度在不断下降。在对根节点进行分枝时，处理的是全部样本，再往下分枝，则是处理的不同分组下的分组下的样本。可见随着决策树的生长和样本数量的不断减少，越深层处的节点所体现的数据特征就越个性化，可能出现如上推理规则：“年收入大于50000元且年龄大于50岁且姓名叫张三的人购买了此产品”。这种过度学习从而精确反映Training Data特征，失去一般代表性而无法应用于新数据分类预测的现象，叫过度拟合（Overfitting）或过度学习。那我们应
7、该怎么办呢？修剪！常用的修剪技术有预修剪（Pre-Pruning）和后修剪（Post-Pruning）。Pre-Pruning可以事先指定决策树的最大深度，或最小样本量，以防止决策树过度生长。前提是用户对变量聚会有较为清晰的把握，且要反复尝试调整，否则无法给出一个合理值。注意，决策树生长过深无法预测新数据，生长过浅亦无法预测新数据。Post-pruning是一个边修剪边检验的过程，即在决策树充分生长的基础上，设定一个允许的最大错误率，然后一边修剪子树，一边计算输出结果的精度或误差。当错误率高于最大值后，立即停止剪枝。基于Training Data的Post-Pruning应该使用Testing
8、 Data。决策树中的C4.5、C5.0、CHAID、CART和QUEST都使用了不同 剪枝策略。2.2Clementine的C5.0的算法及应用C5.0是C4.5的商业化版本，因此算法细节因版权问题尚未公开，本节讨论的是与C5.0算法核心相同的C4.5算法。C4.5是在决策树老鼻祖算法ID3算法的基础上发展起来的，ID3算法自1979年由Quinlan提出，经不断改善形成具有决策树里程碑意义的C4.5算法。需要注意的是C5.0用于生成多分支决策树，输入变量可以是分类型，也可以是数值型，输出变量为分类型。注意不同的决策树算法对输入和输出数据类型的要求。正如1.1节提到的，决策树的核心问题之一是
9、决策树分枝准则的确定。C5.0以信息增益率为标准确定最佳分组变量和最佳分割点。其核心概念是信息熵。1.2.1信息熵和信息增益一、信息熵信息熵是信息论中的基本概念。信息论由Shannon于1948年提出并发展起来，用于解决信息传递过程中的问题，也称统计通信理论。它认为：1、信息传递由信源、信道和信宿组成；2、传递系统存在于一个随机干扰环境中，因此传递系统对信息的传递是随机误差的。如果把发送信息记为U而接收到信息记 V，由信道可记为通信模型，为P(U|V)。信道模型是一个条件概率矩阵P(U|V)。信道模型可以看作是一个条件概率矩阵，信源也往往被理解为某种随机序列，也具有某种发生概率，且其概率求和为
10、1。在实际通信前，信宿信源会发出什么信息不可能知道，称为信宿对信源状态具有不确定性，由于这种不确定性是发生在通信之前的，故称为先验不确定性。在收到信息后的不确定性，称为后验不确定性。如果先验不确定性等于后验不确定性，则表示信息量为零；如果后验不确定性等于零，则表示信宿收到了信源的全部信息。可见：信息是指对不确定性的消除。信息量由消除的不确定性来确定。数据定义为：-Log2P(Ui)。信息量单位是bit，是以2为底的对数形式。信息熵是信息量的数学期望，其表示式由于过于复杂而不写。如果P（U）差别越小，信息熵越大，平均不确定性越大；P(U)差别越在，信息熵越小，平均不确定性越小。如：信息熵等于0，
11、则表示只存在一种信息发送可能，没有发送的不确定性。如果P(U）=1/K，即K个信源概率相同，则信息熵差别最大，不确定性最大。二、信息增益信息熵又称为先验熵，是在信息发送前信息量的数学期望；后验熵指在信息发送后，人信宿角度对信息量的数学期望。一般先验熵大于后验熵，先验熵与后验熵估差，即所谓的信息增益。信息增益，反映的是信息消除随机不确定性的程度。2.2.2 C5.0的决策树生长算法一、如何从众多的分组变量中选择一个最佳的分组变量C5.0以信息论为指导，以信息增益率为标准确定最佳分组变量和分割点。决策树将输出变量（是否购买）看做信源发出的信息U，将输入变量看成信宿收到的信息V。则在实际通信之前，也
12、即是决策树建立之前，输出变量做为信源发出的信息，完全随机，其平均不确定性即为P0.在实际通信过程中添加变量1后，其平均不确定性为P1，则添加变量1产生的信息增益为P0-P1，其它变量如此。则根据信息增益大小判断哪个变量为最佳分组变量。这里有个问题，即类别值多的输入变量较类别值少的输入变量更有机会成为最佳分组变量。为解决此问题，提出将信息增益量除以信息熵，由抵消了类别值的影响，即有信息增益率来表征。那么，如何评价数值型输入变量消除平均不确定性的能力呢？一般对其进行分箱处理，然后根据上述方法判定。分箱不采用了MDLP的熵分组方法，Clementine中C5.0节点本身包含了MDLP算法，它将自动完
13、成数值型输入变量的分箱处理。二、输入变量带有缺失值时如何选择最佳分组变量C5.0在选择最佳分组变量时，通常将带有缺失值的样本当作临时剔除样本看待，并进行权数调整处理。三、如何从分组变量的众多取值中找到一个最佳的分割点在确定了最佳分组变量后，C5.0将继续确定最佳分组变量的分割点。如果分组变量是分类型变量，由按分组变量的K个取值进行分组，形成K个分枝。如果分组变量是数值型变量，则先通过MDLP分箱法或ChiMerge分箱法进行分箱处理，然后分组。如果分组变量中存在缺失值，那怎么办呢？你无法判定此样本分到哪个组中去，C5.0的处理是将其分到所有组中去。但其权重不再为1，而为此组样本数占总样本数的比
14、例。2.2.3 C5.0的剪枝算法C5.0采用Post-Pruning法从叶节点向上逐层剪枝，其关键是误差的估计及剪枝标准的设置。一、误差估计一般决策树的检验应该使用Testing Data，但C5.0使用了统计的置信区间的估计方法，直接在Training Data中估计误差。二、剪枝标准在得到误差的估计后，C5.0将按照“减少误差”判断是否剪枝。首先，计算待剪子树中叶节点的加权误差，然后与父节点的误差进行比较，如果大于则可以剪掉，否则不能剪掉。2.2.4 C5.0的推理规则集C5.0不有够构建决策树，同时还可以生成推理规则集。但是从决策树导入推理规则集非常烦锁，推理规则集通常有自己生成算法，
15、即PRISM。该算法gf1987rh提出，是一种“覆盖”算法，对Training Data100%正确。2.2.5 C5.0的基本应用示例下面对一个使用了C5.0的挖掘案例进行介绍，这里不再像之前介绍案例似的步步介绍，现在只对重点部分进行介绍。主要是C5.0的面板设置及C5.0呈现的结果。下图为C5.0的面板设置。模型名称：可以自动，亦可以自定义。在平时练习时默认自动即可，在商业活动中为避免重名或混乱，一律要自定义命名，这是数据挖掘的基本规范。使用分区数据：英文Use Partitioned data。勾选表示利用Partition变量将样本集进行分割。但C5.0并不在Testing Data
16、上进行模型检验，还需要Partition吗？需要，Partition的目的是比较同一模型在不同样本集上的稳健性。输出类型：英文Output Type。Decision Tree表示得不到成决策树和由决策树得到的推理规则；Rule Set表示输出推理规则集，这个推理规则集并非由Decision Tree生成，而是由PRISM法生成的。这里首先输出决策树。组符号：英文Group Symbolics。选中表示使用ChiMerge分箱法检查当前分组变量的各个类别能否合并，如果可以应先合并再分枝，此方法得到的Decision Tree相对精简。否则，对K个分类型分组变量将生成K叉树，对数值型分组变量将生成二叉树。使用推进：英文Use Boosting。表示采用推进方法建立模型以提高模型预测的稳健性。交叉验证：英文Cross-validate。表示将采用交叉验证的方法构建模型。模式：英文Mode。决定决策树的剪枝策
