决策树概述

作者:数据小雄 , 分类:算法研究 , 浏览:1835 , 评论:0
分类预测:通过归纳和提炼现有数据所包含的规律,建立分类预测模型,用于对未来新数据的预测。


分类预测包括分类和回归。
  • 分类模型:输出变量为分类型的分类预测模型;

  • 回归模型:输出变量为连续数值型的分类预测模型。


经典案例:电信客户流失、药物研究


        决策树(Decision Tree)模型也称规则推理模型、判定树模型,其分析结论展示类似一棵倒置的树,为分类预测算法之一。

目标:建立分类模型或回归模型。


通过对训练样本的学习,建立分类规则。
根据分类规则,实现对新样本的分类。

属于有指导(监督)式的学习方法,有两类变量:目标变量(输出变量)和属性变量(输入变量)


根节点:最上层节点为根节点,一棵决策树仅有一个根节点。
叶节点:没有下层的节点,在最下层,一棵决策树可有多个叶节点。
中间节点:位于根节点下且还有下层的节点,可分布在多个层中。
同层节点称为兄弟节点。上层节点为下层节点的父节点,下层节点为上层节点的子节点。根节点没有父节点,叶节点没有子节点。
二叉树:每个节点最多只能生长出两个分枝,即父节点只能有两个子节点。

多叉树:长出不止两个分枝,即父节点有两个以上子节点。


特点:
  • 决策树体现了对样本不断分组的过程;

  • 决策树分为分类树和回归树;

分类树:分类型输出变量值的预测,某个叶节点的预测值,是该样本输出变量值的众数类别;
回归树:数值型输出变量值的预测,某个叶节点的预测值,是该样本输出变量值的平均值。
  • 决策树体现了输入变量和输出变量的取值之间的逻辑关系。最大特点:其分类预测是基于逻辑的。

优点:
  • 方便理解:构造简单,表示方法直观,易于理解,可表示成If Then形式。

  • 准确性高:挖掘出的分类规则准确性高,可清晰显示哪些字段重要。

  • 数据属性多样:能够同时处理数据型和常规型属性。 

  • 计算量小:计算量相对来说不是很大,且容易转化成分类规则。

  • 数据准备简单:对于决策树,数据的准备往往是简单或者是不必要的。其他的技术往往要求先把数据一般化,比如去掉多余的或者空白的属性。

  • 白盒模型:若给定一个观察的模型,则根据所产生的决策树很容易推出相应的逻辑表达式。

  • 易于评测:易于通过静态测试来对模型进行评测。表示有可能测量该模型的可信度。

  • 速度快:在相对短的时间内能够对大型数据源做出可行且效果良好的结果。

  • 效率高:决策树只需要一次构建,反复使用,每一次预测的最大计算次数不超过决策树的深度。

缺点:
  • 缺乏伸缩性:由于进行的是深度优化搜索,故算法受内存大小限制,难于处理大训练集。

  • 连续性的字段比较难预测,当类别较多时,错误可能会增加的比较快。一般算法在分类时,只是根据一个属性来分类。

  • 在有噪声时,完全拟合将导致过分拟合,导致预测性能不好。

  • 可能产生子树复制和碎片问题。


决策树几何理解:


决策树核心问题:
  • 建树:用训练样本集完成决策树的建立过程;

  • 剪枝:用测试样本集对所形成的决策树进行精简。

1、建树
       对训练样本集的不断分组过程,决策树的各个分枝就是在该过程中逐渐长出来的。当对某组数据的继续分组无意义时,它所对应的分枝即停止生长;当所有数据组的继续分组均无意义时,决策树生长就结束,即一棵完整的决策树形成了。其核心算法就是确定其分枝准则。

Image1.png

图1  决策树生长过程的示意图

分枝准则的确定:
  • 如何从众多输入变量中选择一个当前最佳的分组变量;

  • 如何从分组变量的众多取值中找到一个最佳的分割点。


2、剪枝
       过拟合:Overfitting,虽然完整决策树能准确反映训练样本集数据特征,但有可能失去一般代表性而无法对新数据进行分类预测。解决该问题的方法就是对决策树进行剪枝。
常用的剪枝技术:
先剪枝:用来限制决策树的充分生长。
  1. 事先指定决策树生长的最大深度,决策树生长到指定深度后就不再生长;

  2. 事先指定样本量的最小值,节点样本量不应低于该值,否则不再生长。

后剪枝:待决策树充分生长后再修剪。
  1. 待决策树充分生长后,根据一定规则,剪去决策树中不具代表性的子树,边修剪边检验。

  2. 事先指定一个允许的最大误差,修剪过程不断计算当前决策子树对输出变量的预测误差,高于允许最大误差时,停止剪枝,否则继续。

通常拿测试样本集对决策树进行修剪,不用训练样本集在于决策树是在训练样本集基础上构建的。

Image2.png

图2  决策树的修剪

       图2 中,生长初期,决策树在训练和测试样本集上的预测误差快速减少。随着树深度的增加,预测误差减少速度开始放缓。当树达到一定深度后,训练样本集上的误差仍继续减少,但在测试样本集上开始增大,出现过拟合。后剪枝应停止在预测误差较小且过拟合未出现时。


经典决策树算法:CLS、ID3、CART、C4.5(C5.0)、CHAID、QUEST、


参考文献:

1、薛薇:《基于Clementin的数据挖掘》

2、算法杂货铺——分类算法之决策树(Decision tree)

3、分类:基本概念、决策树与模型评估

4、维基百科:决策树


—————————————————————————

【版权申明】

如非注明,本站文章均为 数据小雄 原创,转载请注明出处:数据小雄博客,并附带本文链接,谢谢合作!

本文地址:http://zhangzhengxiong.com/?id=74。

—————————————————————————

亲!有什么想法呢?
  • 流泪

    0

  • 打酱油

    2

  • 开心

    2

  • 鼓掌

    0

  • 恐怖

    0

 

发表评论

必填

选填

选填

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

额 本文暂时没人评论 来添加一个吧
新浪微博
米店
标签列表
@数据小雄 | 专注于数据分析、挖掘、可视化案例分享