决策树概述

分类预测：通过归纳和提炼现有数据所包含的规律，建立分类预测模型，用于对未来新数据的预测。

分类预测包括分类和回归。
分类模型：输出变量为分类型的分类预测模型；

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

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

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

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

通过对训练样本的学习，建立分类规则。
根据分类规则，实现对新样本的分类。
属于有指导（监督）式的学习方法，有两类变量：目标变量（输出变量）和属性变量（输入变量）

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

特点：
决策树体现了对样本不断分组的过程；

决策树分为分类树和回归树；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

决策树几何理解：

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

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

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

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

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

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

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

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

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

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

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

图2 决策树的修剪

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

经典决策树算法：CLS、ID3、CART、C4.5（C5.0）、CHAID、QUEST

原文地址：
数据小雄博客：http://www.zhangzhengxiong.com/?id=74