二元决策树的构建课件.pptVIP

信号/本底二元决策树的构建

背景?数据挖掘是从数据中发现隐含着的有用的信息或知识的技术，它是随着人类进入信息社会以来对信息的价值认识不断提高而不断发展的，是为满足和解决当前“数据太多，信息不足”问题的技术。数据挖掘有着广泛的应用，如数据库营销、客户群体划分、客户流失性预测、欺诈检测和客户信用记分等。分类法是数据挖掘中的一个非常重要的技术。分类的目标是要根据属性的值为每个类推导出一个简洁的模型或描述。这个模型用于对那些类未知的记录进行分类，赋予每个记录相应的类标签。常见的分类方法有贝叶斯分类、神经网络、遗传算法和决策树分类器，在这些分类方法中，决策树分类器在大规模的数据挖掘环境中已经获得了最为广泛的应用。

1.1决策树法的基本思想?决策树（又称树分类器或分类树）是模式识别中进行分类的一种有效方法。利用树分类器可以把一个复杂的多类别分类问题转化为若干个简单的分类问题来解决。它不是企图用一个决策规则把多个类别的样本一次分开，而是采用分级的方法，使分类问题逐步得到解决。总结起来，决策树就是一个将输入空间逐步分割的过程，它把输入空间分为一组互不相交的子区域，其中某个类别的样本占有优势的区域标记为该样本的类别。

?决策树示意图?一般地，一个决策树由一个根节点n,一组非终止节点ni1,和一些终止节点（也称叶节点、叶子）t构成，每个叶j节点标以相应的样本类别标签，不同的叶节点可以有相同的类别标签。

?二元决策树决策树的一种简单形式是二叉树，二叉树结构的分类器可以把一个复杂的多类别分类问题化为多级、多个两类问题来解决，在每个节点都把样本集分为左右两个子集。分出的每个部分任然可能包含多个类别的样本，在下一级的节点，把每个部分再分为两个子集，依此进行，直到最后分出的每个部分只包含同一类别的样本，或某一类别样本占优势为止。优点：概念简单、直观，便于解释。在各个节点上可以选择不同的特征和采用不同的决策规则。

二叉决策树示意图

1.2信号/本底二元决策树的构建?信号/本底二元决策树的构建，即解决信号和本底的两类事例的分类问题。求解这类问题的过程，就是利用一个训练样本集来构建（训练）一个决策树的过程。训练样本集中包含信号和本底两类事例。训练从根节点开始，到满足某种终结条件时停止。在每一个非终止节点的判选后，输入事例被区分为“类信号事例”和“类本底事例”两部分，其中“类信号事例”中信号事例的比例高于判选前的信号事例的比例，而“类本底事例”部分则相反。叶节点被分为信号和本底节点两类，其中到达信号事例占优的被指定为信号节点，反之为本底节点。这样一个决策树就构造完成了。

当一个待分类的样本集输入决策树，则落入信号叶节点的事例被判定为“信号事例”，落入本底叶节点的事例被判定为“本底事例”。一个区分信号/本底的二元决策树的示意图

1.3几个核心问题?在实际操作中，若要构建一个信号/本底二元决策树，以下几个问题需要被讨论：1.如何选取变量和分割值?2.什么时候一个节点可以停止被划分，最终成为一个叶节点?3.如何优化这个树的结构?下面我们将依次考虑这些问题。

1.3.1如何选取变量和分割值??在决策树的构建过程中，每个非终止节点上只选择一个变量进行判别，这个变量应该是区分信号和本底能力最强的那个变量，同一个变量可在不同层次的节点中被重复使用。选定最优变量之后，需要找出与变量相应的决策阈值，同一个变量在不同层次的节点中相应的决策阈值也可以不同。这样，我们就找到了对于每个非终止节点的分割率，即变量+阈值的组合。p5

?为了生成一个简单的紧凑的二叉树，我们在每个节点寻找的分割率应该使得经过分割后到达下一级别的节点的数据尽可能的纯净，即使数据尽可能属于同一类。这里列出四种衡量节点中数据不纯程度的方法：信息熵：定义为Gini指数：定义为误判误差：定义为统计显著性：定义为以上几个量被称为（信号/本底）判别指数，用符号I表示。其中，n,n分别为输入该节点的信号和本底事例SB数；p为信号事例纯度，表达式为；

?在决策树的训练过程中，每个节点上存在一个最优的分割率可使节点的不纯程度降低的最多，即使得该节点的判别指数与它的两个子节点的判别指数的加权和的增量达到最大，该增量用公式表示为式中，I,I,I,分别为母节点和两个子节点的判别指数；12n,n,n,分别为母节点和两个子节点的输入事例数。int12

??在实际训练过程中，一般将每个变量（x,x,…x）12n的值域分为n个小区间，这n个区间的中心值作为cutscuts进行计算，取其中的最大增量作为n个阈值对增量cuts该变量的最大增量。在所有n个变量（x,x,…x）的最12n大增量中，数值最大的那个变量x作为本节点的判别变量，j其最大增量对应的阈值xthj