二元决策树的构建

信号/本底二元决策树的构建背景•数据挖掘是从数据中发现隐含着的有用的信息或知识的技术，它是随着人类进入信息社会以来对信息的价值认识不断提高而不断发展的，是为满足和解决当前“数据太多，信息不足”问题的技术。数据挖掘有着广泛的应用，如数据库营销、客户群体划分、客户流失性预测、欺诈检测和客户信用记分等。分类法是数据挖掘中的一个非常重要的技术。分类的目标是要根据属性的值为每个类推导出一个简洁的模型或描述。这个模型用于对那些类未知的记录进行分类，赋予每个记录相应的类标签。常见的分类方法有贝叶斯分类、神经网络、遗传算法和决策树分类器，在这些分类方法中，决策树分类器在大规模的数据挖掘环境中已经获得了最为广泛的应用。1.1决策树法的基本思想•决策树（又称树分类器或分类树）是模式识别中进行分类的一种有效方法。利用树分类器可以把一个复杂的多类别分类问题转化为若干个简单的分类问题来解决。它不是企图用一个决策规则把多个类别的样本一次分开，而是采用分级的方法，使分类问题逐步得到解决。总结起来，决策树就是一个将输入空间逐步分割的过程，它把输入空间分为一组互不相交的子区域，其中某个类别的样本占有优势的区域标记为该样本的类别。•决策树示意图•一般地，一个决策树由一个根节点n1,一组非终止节点ni,和一些终止节点（也称叶节点、叶子）tj构成，每个叶节点标以相应的样本类别标签，不同的叶节点可以有相同的类别标签。•二元决策树决策树的一种简单形式是二叉树，二叉树结构的分类器可以把一个复杂的多类别分类问题化为多级、多个两类问题来解决，在每个节点都把样本集分为左右两个子集。分出的每个部分任然可能包含多个类别的样本，在下一级的节点，把每个部分再分为两个子集，依此进行，直到最后分出的每个部分只包含同一类别的样本，或某一类别样本占优势为止。优点：概念简单、直观，便于解释。在各个节点上可以选择不同的特征和采用不同的决策规则。二叉决策树示意图1.3.11.2信号/本底二元决策树的构建•信号/本底二元决策树的构建，即解决信号和本底的两类事例的分类问题。求解这类问题的过程，就是利用一个训练样本集来构建（训练）一个决策树的过程。训练样本集中包含信号和本底两类事例。训练从根节点开始，到满足某种终结条件时停止。在每一个非终止节点的判选后，输入事例被区分为“类信号事例”和“类本底事例”两部分，其中“类信号事例”中信号事例的比例高于判选前的信号事例的比例，而“类本底事例”部分则相反。叶节点被分为信号和本底节点两类，其中到达信号事例占优的被指定为信号节点，反之为本底节点。这样一个决策树就构造完成了。当一个待分类的样本集输入决策树，则落入信号叶节点的事例被判定为“信号事例”，落入本底叶节点的事例被判定为“本底事例”。一个区分信号/本底的二元决策树的示意图1.3几个核心问题•在实际操作中，若要构建一个信号/本底二元决策树，以下几个问题需要被讨论：1.如何选取变量和分割值?2.什么时候一个节点可以停止被划分，最终成为一个叶节点?3.如何优化这个树的结构?下面我们将依次考虑这些问题。1.3.21.3.31.3.1如何选取变量和分割值?•在决策树的构建过程中，每个非终止节点上只选择一个变量进行判别，这个变量应该是区分信号和本底能力最强的那个变量，同一个变量可在不同层次的节点中被重复使用。选定最优变量之后，需要找出与变量相应的决策阈值，同一个变量在不同层次的节点中相应的决策阈值也可以不同。这样，我们就找到了对于每个非终止节点的分割率，即变量+阈值的组合。p5•为了生成一个简单的紧凑的二叉树，我们在每个节点寻找的分割率应该使得经过分割后到达下一级别的节点的数据尽可能的纯净，即使数据尽可能属于同一类。这里列出四种衡量节点中数据不纯程度的方法：信息熵：定义为Gini指数：定义为误判误差：定义为统计显著性：定义为以上几个量被称为（信号/本底）判别指数，用符号I表示。其中，nS,nB分别为输入该节点的信号和本底事例数；p为信号事例纯度，表达式为；)1log()1(logpppp)1(pp)1,max(1ppBSSnnn)/(BSSnnnp•在决策树的训练过程中，每个节点上存在一个最优的分割率可使节点的不纯程度降低的最多，即使得该节点的判别指数与它的两个子节点的判别指数的加权和的增量达到最大，该增量用公式表示为式中，I,I1,I2,分别为母节点和两个子节点的判别指数；nint,n1,n2,分别为母节点和两个子节点的输入事例数。I•在实际训练过程中，一般将每个变量（x1,x2,…xn）的值域分为ncuts个小区间，这ncuts个区间的中心值作为ncuts个阈值对增量进行计算，取其中的最大增量作为该变量的最大增量。在所有n个变量（x1,x2,…xn）的最大增量中，数值最大的那个变量xj作为本节点的判别变量，其最大增量对应的阈值xthj与xj一起构成该节点的最优（变量+阈值）组合。•经验表明ncuts取为20是个比较适当的选择，它是计算量和精细程度之间的一个比较适当的平衡，过大的ncuts值并不能提升二叉树的信号/本底判别性能，反而不必要的增加了计算量。1.3I1.3.2终止条件•在选出最好的分割之后，我们可以将数据划分为两个子集，并在每个自己中重复同样的选择分割率和分割空间的步骤。但是我们将面临怎么时候停止分割的问题，如果我们生成一个完全树，其每个叶子节点都只包含一个类即不纯程度为0，则这个树模型很有可能过度拟合了数据。相反如果我们太早的停止分割，训练误差还不够小会使模型的准确性下降。•由此可见，不合适的终止条件会使构造的决策树过大或过小，造成决策树不能达到理想的分类效果。设定合适的终止条件就是在树的大小和准确率之间寻找平衡点。•以下给终止训练过程的几种方法:法1.设定一个最大的叶节点数，当训练过程已经形成的叶节点数等于大于该数值则训练停止。法2.设定一个最小的事例数NL，当输入事例数小于NL，该节点的训练停止。法3.当一个节点的输入事例为同一类事例时，该节点的训练终止。法4.根据所有节点的增量值来决定训练是否终止，当节点增量满足则该节点的训练终止。1.3p17I)0(,常数I1.3.3决策树结构的优化•在决策树法中，除去分类的正确性应当放在第一位给予考虑之外，决策树的复杂程度是另外一个需要考虑的重要因素。我们的目标是构造—颗结构简单的决策树，简化决策树的方法很多，这里我们主要讨论从控制树的大小来简化决策树的一些方法。这些方法不仅能够简化决策树，而且能够改进决策树分类的正确性。•控制树的大小，这是最常用的简化决策树的方法。它主要通过在训练过程中明确地控制树的大小来简化决策树。它主要包括预剪枝和后剪枝两种方法，以及其他的后处理方法。预剪枝•预剪枝算法中不要求以每个叶结点中的训练实例都属于同一个类（错误率为0）作为算法的停止条件，而是在这个标准得到满足之前就停止继续扩展决策树。具体在什么时候停止决策树的扩展就成为这个方法的主要研究内容和难点。•一种最为简单的方法就是在决策树达到一定高度的情况下就停止决策树的扩展，即终止条件中法1、法2。•另一种更为普遍的做法是计算每次扩展对系统性能的增量值，如果这个增量值小于某个阈值则不进行扩展。如果在最好情况下的扩展增量值都小于阈值，则即使有些叶结点的实例集不属于同一类，算法也停止。即终止条件中法4。p15•预剪枝的一个根本缺点是很难确定多大的终止门限是合理的。其另外一个缺点是视野效果问题。也就是说在相同标准下，也许当前的扩展不能满足要求，但是更进一步的扩展能够满足要求。而预剪枝将会因为过早地停止决策树的构造导致很大的误差，后剪枝将克服这些缺点。•但是由于预剪枝不必生成整棵决策树，使得其算法效率很高，适合解决大规模问题，所以这种方法仍然得到广泛的应用。后剪枝•前面已经讨论过了，构建一棵完全树来对样本集进行分类往往是不够合理的。后剪枝法就是在先构建一个完全树的基础上，通过一些准则剪除对于有效分辨信号/本底用处不大的节点，从而形成一个结构简化，效果优化的决策树。•一种有效的后剪枝策略是利用最小复合费用的准则对完全树进行自下而上的修剪：在二叉树的每个节点，训练样本的误判率定义为：，该节点的复合费用定义为，其中Rsub表示该节点以下的那部分二叉树的总误判率，Nsub表示该节点以下的那部分二叉树包含的叶节点数。)1,max(1ppR)1()(subsubNRR•一颗二叉树中，假定复合费用ρ最小的节点称为节点t,当它的复合费用小于给定的修剪量ρPS，即ρtρPS则节点t以下的部分二叉树被剪除，而节点t变成一个“新的”叶节点。这种修剪不断进行，直到不再出现这样的叶节点为止，整棵二叉树的修剪得以完成。•修剪量ρPS的大小可以如下确定：将训练样本集分为两个样本数足够大的子集，子集1专用于构建二叉树T（ρPS），子集2专用于对这个二叉树进行性能测试，这样就可得二叉树性能与ρPS的函数关系，从而可得二叉树错误率与ρPS的函数关系，取使得错误率最小的ρPS就是最优的修剪量。•与自下而上的修剪方式相对的是自上而下的后剪枝方式，自上而下的算法是从根结点开始向下逐个考虑每个结点是否应被剪枝。直到某结点满足剪枝的标准而被修剪为止。•如果一棵子树的任何—个子结点都不满足剪枝标准，那么自上而下剪枝方法可以避免将这个结点修剪掉，也就是可以避免视野效果的问题。而对于自下而上的算法，则不能避免这个问题，而会产生与预剪枝相同的问题。•明显经过剪枝的决策树对于训练实例集的错误率已经不为0，但是由于在这种剪枝算法当中位于底层的子树将被优先剪枝，而这些结点都是只包含很少实例的，所以这种方法将减少噪声对决策树构造的影响。所以经过剪枝的决策树一般情况下会提高决策树对整个实例空间分类的正确性。•后剪枝算法的另外一个优点是，它能够产生一组而不是一棵决策树，这将使得专家有可能在其中作出自己的选择而不是由计算机武断地作出选择，因为专家往往有可能不同意计算机所作出的选择。增量树学习•在一般情况下，为了解决内存空间的问题，利用增量树学习的方法，通过逐步增加训练样本增量式地构造决策树。在递归调用剪枝算法的过程中，因为大的样本集对于剪枝是有好处的，所以如果增加训练样本的时候重新考虑以前进行剪枝的决定是有一定好处的。•另一种增量式学习方法是动态剪枝或者叫做虚剪枝。在这种方法中，也是根据前面的方法以统计的方法建立树。不同的是并不是整个树的所有节点都用来分类。而是有一部分叶节点作为虚节点，不对样本进行分类，而只有实节点对样本进行分类。•虚节点可以被看作已经被修剪的节点。而叶节点在虚节点与实节点之间的转换是在决策树积累实例的过程中动态决定的，所以当将一个叶节点剪枝时只是将它变为虚节点，而不会带来不可修复的变化。•可以看出增量式学习在保持决策树学习其它优点的同时可以使得决策树有一个较为理想的大小。应用举例•当生成一个二叉树模型后，如何应用这个树进行分析预测？对未知样本的分类可以从根节点开始，首先根据根节点的分割律，未知物对应的分割变量的值将被检查并与分割值比较，基于比较的结果，未知样本沿着合适的分支到达下一代节点，从二叉树的结构可知，对于未知样本，有一个且只能沿着一个分支到达后代节点。其次，在合适的后代节点中，我们要做类似的决策，判断未知样本应该沿着那条分支继续下去。重复这个过程直到样本到达不再被分割的叶节点，则未知样本的类就是它所到达的叶节点做代表的类。总结•决策树方法在近30年里发展迅速，各种各样的决策树算法被提出和广泛应用，如ID3，CART，C4.5等。•决策树是一种简单而强大的方法，尤其在处理大型数据的时候。首先其模型是稳健的，孤立点对它的影响不是很大。因为很多数据库都有可能包含有疑问的数据，无法保证完全的正确性，所以对孤立点的稳健性在数据分析中是很重要的。其次决策树还是处理高维数据的一种有效的方法，因为它可以在生成树的过程中自动的选取重要的变量，执行速度快又准确率高；另外它的一个重要的优点是模型具有可解释性，它用树逻辑表达发现知识，使得结果易于解释。•然而，决策树也有其不可避免的缺陷，它对