决策树归纳的理论介绍

光环大数据，拥有16年的程序员培训经验，上市公司品牌，口碑极好，一线名师授课，强大的教研团队研制开发最新的课程，与中关村软件园战略合作保障人才输出，与学员签订就业协议保障就业问题！真正的靠谱品牌！
 

什么是分类？

银行贷款员需要分析数据，以便搞清楚哪些贷款申请者是“安全”那些是“有风险”的。销售经理需要数据分析，以便帮助他猜测哪些顾客会购买计算机。再或者医学研究人员需要分析乳腺癌数据，以便预测病人应当接受三种治疗中的哪一种。在上面的例子中，数据分析任务都是分类，都需要构造一个模型来预测一个类别型数据。譬如安全或者不安全、会购买与不会购买、那种治疗都是类别型。分类是一种重要的数据分析形式，它提取刻画重要数据类的模型，用来预测（离散的、无序的）类标号。

决策树是一种类似于流程图的树结构，其中，每个内部节点(非树叶节点）表示在一个属性上的测试，每个分支代表该测试的一个输出，而每个树叶节点（或终端节点）存放一个类标号。树的最顶层节点是根节点。

比如我们想要决定要不要给一个用户贷款，第一个分裂准则可以定义为age年龄，年龄底下有三个分枝，Youth，middle_aged和Senior。年轻人中再以是否为大学生作为一个分裂节点，如果是学生就给贷款，yes就是这条枝子上的叶子节点，也就是最后的类标号。

数据分类过程：a) 学习，及建立树的阶段。用分类算法分析训练数据，学习的模型以分类规则（Splitting criterian）或者叫属性选择度量形式提供；b) 分类。检验数据用于评估分类规则的准确率，如果准确率是可以接受的，则规则用于新的数据元组分类。

属性选择度量是一种选择分裂标准，把给定类标记的训练元组的数据分区D“最好地”划分成单独类的启发方式，比如量——信息增益、增益率和基尼指数。

1、用信息增益进行决策树归纳

看不懂公式可以直接看下面例子

该度量基于Claude Shannon在研究消息的值或“信息内容”的信息论方面的先驱工作。设计节点N代表或存放分区D的元组。选择具有最高信息增益的属性作为节点N的分裂属性。该属性使结果分区中对元组分类所需要的信息量最小，并反映这些分区中的最小随机性或“不纯性”。这种方法使得对一个对象的分类所需要的期望测试数目最小，并确保找到一颗简单的（但不必是最简单的）树。

现在我们假设要按某属性A划分D中的元组，其中属性A根据训练数据的观测具有v个不同的值｛a1,a2, …, av｝。理想情况下我们希望该划分产生的元组的准确分类，即我们希望每个分区都是纯的。然而这些分区多半是不纯的（例如，分区可能包含来自不同类而不是来自单个类的元组）。为了得到准确的分类，我们需要下式度量：

例子：

首先使用（8.1）式计算D中元组分类所需要的期望信息：

Info(D)=-log₂(9/14)*(9/14)-log₂(5/14)*(5/14)=0.94

下一步计算每个属性的期望信息需求。从属性age开始，需要对age的每个类考察Yes和NO元组的分布。对于age的类“youth”，有2个yes和3个no元组。同样的，middle_aged有4个yes和0个no，senior有3个yes和2个No。使用（8.2）式，如果元组根据age划分，则对D中的元组进行分类所需要的期望信息为：

类似的，可以计算Gain(Income)= 0.02, Gain(Student)= 0.151, Gain(credit_rating)=0.048。由于age属性中具有最高的信息增益，所以它被选作分裂属性。注意，落在分区age = middle_aged的元组都属于相同的类，即分类都是yes， 所以在该分支的端点是一个叶子节点。

这样一次分裂就完成了。所以对于youth和senior可以用刚才的步骤进行下一步的分裂，直到结束。

基尼指数进行决策树归纳的总体做法是跟上面的信息增益一式一样的，只不过公式不同，再次不再作详细的介绍。有兴趣的童靴可以参考上面给出的书籍。不过基尼指数强制树是二叉树。

决策树归纳的步骤：

这一部分我放在最后是因为放在一开始可能不利于理解。看完了上面的例子相信你可以更好地理解决策树归纳的步骤：

~我们称原始的数据集为D。开始，它是训练元组和他们相应类标号的完全集。参数Attribute_list是描述元组属性的列表。Attribute_selection_method指定选择属性的启发式过程，用来选择可以按类“最好地”区分给定元组的属性。该过程使用一种属性选择度量，如信息增益或基尼指数（Gini Index）。树是否是严格的二叉树由属性选择度量决定。比如基尼指数强制结果树是二叉树。信息增益并非如此，它允许多路划分（即从一个节点生长两个或多个分枝）。

~树从单个节点N开始，N代表D中的训练元组。

~如果D中的元组都为同一类，则节点N变为树叶，并用类标记它。

~否则调用Atrribute_selection_method确定分裂准则，使得每一个分枝上的输出分区都尽可能“纯”。一个分区是纯的，如果它的所有元组都属于同一类。换言之，如果根据分裂准则的互斥输出划分D中的元组，则希望结果分区尽可能纯。

~分裂时有三种可能的情况，离散、连续、离散且必须产生二叉树。比如color作为分枝节点，它的子节点是离散的，比如red,green,blue等等；income是连续的, 这是我们的子节点可以分成两支，对应于>=split_point和<split_point。比如income>= 10k和income<10k。其中的split_point作为分裂点；而在基尼指数中必须产生二叉树，比如要限定Color的子节点为两个, 我们就可以定义一个集合S，比如S={red,green}，凡属于这个集合的形成一个树枝，不属于的形成另一个。

~对于分区D的每个结果分区上的元组，算法使用同样的过程递归地形成决策树。

~递归划分步骤仅当下列种植条件之一成立时停止：

1. 分区D的所有元组都属于同一个类，如上面的middle_aged例子；

2. 没有剩余属性可以用来进一步划分元组，在此情况下使用多数表决，创建叶子节点，并用多数类来标记它；

3. 给定的分枝没有元组，即分区为空，那就要用D中的多数类创建一个树叶。

~返回结果决策树。

剪枝

由于数据中的噪声和离群点，可能会产生过分拟合的数据问题，剪枝就可以很好地解决。有两种常见的剪枝方法：先剪枝和后剪枝。

先剪枝：通过提前停止树的构建（例如，通过决定在给定的节点不再分裂或划分训练元组的子集）而对树“剪枝”。一旦停止，节点就成为树叶。该树叶可以持有子集元组中最频繁的类，或者这些元组的概率分布。

在构造树时，可以使用诸如统计显著性、信息增益、基尼指数等度量来评估划分的优劣。如果划分一个节点的元组导致低于预定义阈值的划分，则给定子集的进一步划分将停止。然而，选取一个适当的阈值是困难的。更常用的方法是后剪枝。

后剪枝：它有“完全生长”的树减去子树，通过删除节点的分枝并用叶子节点取代。该树叶的类标号用子树中最频繁的类标记。CART使用的代价复杂度剪枝算法是后剪枝方法的一个实例。该方法把树的复杂度看作树中树叶节点的个数和树的错误率的函数（错误率是树误分类的元组占的百分比）。它从树的底部开始。对于每个内部节点，计算它的子树的代价复杂度和该子树剪枝后的该节点字数的代价复杂度，比较两个值取较小的代价复杂度。

数据挖掘培训，大数据培训，就选光环大数据！

原创文章，转载请注明出处：光环大数据 http://hadoop.aura.cn