分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内部结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或属性(features)，叶结点表示一个类(labels)。
用决策树对需要测试的实例进行分类：从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分配到叶结点的类中。
根节点(root node)：它代表整个群体或样本，并且会进一步被划分为两个或更多个同质集合。
分裂(splitting)：这是将节点划分为两个或更多个子节点的过程。
决策节点(decision node)：当子节点拆分为更多的子节点时，称为决策节点。
叶/终端节点(leaf/terminal node)：节点不分裂称为叶节点或终端节点。
修剪(prunning)：当我们删除决策节点的子节点时，这个过程称为修剪。 你可以说分裂的相反过程。
分支/子树(branch/sub-tree)：整个树的子部分称为分支或子树。
父子节点(parent and child node)：被划分为子节点的节点被称为子节点的父节点，其中子节点是父节点的子节点。
熵（entropy）： 熵指的是体系的混乱的程度，在不同的学科中也有引申出的更为具体的定义，是各领域十分重要的参量。
信息论（information theory）中的熵（香农熵）： 是一种信息的度量方式，表示信息的混乱程度，也就是说：信息越有序，信息熵越低。例如：火柴有序放在火柴盒里，熵值很低，相反，熵值很高。
信息增益（information gain）： 在划分数据集前后信息发生的变化称为信息增益。
容易理解(Easy to Understand)：决策树输出非常容易理解，即使对于非分析背景的人。它不需要任何统计知识来阅读和解释它们。它的图形表示非常直观，用户可以很容易联系到他们的假设。
在数据探索中有用(Useful in Data Exploration)：决策树是识别最重要变量和两个或更多变量之间关系的最快方法之一。在决策树的帮助下，我们可以创建具有更好的预测目标变量的能力的新变量/特征。你可以参考这篇文章(Trick to enhance power of Regression model)。它也可以用于数据探索阶段。例如，我们正在处理一个问题，其中我们有数百个变量，决策树将有助于识别出其中最重要的变量。
更少的数据清理(Less data cleaning required)：与其他一些建模技术相比，它需要更少的数据清理。它一定程度上不受异常值和错误值的影响。
数据类型不是约束(Data type is not a constraint)：它可以处理数值和分类变量。
非参数方法(Non Parametric Method)：决策树被认为是一个非参数方法。这意味着决策树没有关于空间分布和分类器结构的假设。
过拟合(Over fitting)：过拟合是决策树模型最实际的困难之一。 通过设置模型参数和修剪的约束（下面将详细讨论）解决这个问题。
不适合连续变量(Not fit for continuous variables)：当使用连续数值变量时，决策树在将变量分类到不同类别时会丢失信息。
Decision_Tree_2.png
如何构造一个决策树? 使用 createBranch() 方法，如下所示：
def createBranch(): ''' 此处运用了迭代的思想。 感兴趣可以搜索 迭代 recursion， 甚至是 dynamic programing。 ''' 检测数据集中的所有数据的分类标签是否相同: If so return 类标签 Else: 寻找划分数据集的最好特征（划分之后信息熵最小，也就是信息增益最大的特征） 划分数据集 创建分支节点 for 每个划分的子集 调用函数 createBranch （创建分支的函数）并增加返回结果到分支节点中 return 分支节点决策树 算法特点
优点：计算复杂度不高，输出结果易于理解，数据有缺失也能跑，可以处理不相关特征。 缺点：容易过拟合。 适用数据类型：数值型和标称型。
1.1、树回归 原理概述
为成功构建以分段常数为叶节点的树，需要度量出数据的一致性。第3章使用树进行分类，会在给定节点时计算数据的混乱度。那么如何计算连续型数值的混乱度呢？
在这里，计算连续型数值的混乱度是非常简单的。首先计算所有数据的均值，然后计算每条数据的值到均值的差值。为了对正负差值同等看待，一般使用绝对值或平方值来代替上述差值。
上述做法有点类似于前面介绍过的统计学中常用的方差计算。唯一不同就是，方差是平方误差的均值(均方差)，而这里需要的是平方误差的总值(总方差)。总方差可以通过均方差乘以数据集中样本点的个数来得到。 1.2、树构建算法 比较
ID3 的做法是每次选取当前最佳的特征来分割数据，并按照该特征的所有可能取值来切分。也就是说，如果一个特征有 4 种取值，那么数据将被切分成 4 份。一旦按照某特征切分后，该特征在之后的算法执行过程中将不会再起作用，所以有观点认为这种切分方式过于迅速。另外一种方法是二元切分法，即每次把数据集切分成两份。如果数据的某特征值等于切分所要求的值，那么这些数据就进入树的左子树，反之则进入树的右子树。
除了切分过于迅速外， ID3 算法还存在另一个问题，它不能直接处理连续型特征。只有事先将连续型特征转换成离散型，才能在 ID3 算法中使用。但这种转换过程会破坏连续型变量的内在性质。而使用二元切分法则易于对树构造过程进行调整以处理连续型特征。具体的处理方法是: 如果特征值大于给定值就走左子树，否则就走右子树。另外，二元切分法也节省了树的构建时间，但这点意义也不是特别大，因为这些树构建一般是离线完成，时间并非需要重点关注的因素。
CART 是十分著名且广泛记载的树构建算法，它使用二元切分来处理连续型变量。对 CART 稍作修改就可以处理回归问题。使用香农熵来度量集合的无组织程度。如果选用其他方法来代替香农熵，就可以使用树构建算法来完成回归。
回归树与分类树的思路类似，但是叶节点的数据类型不是离散型，而是连续型。
1.2.1、附加 各常见树构造算法的划分分支方式
还有一点要说明，构建决策树算法，常用到的是三个方法: ID3, C4.5, CART. 三种方法区别是划分树的分支的方式:
ID3 是信息增益分支 C4.5 是信息增益率分支 CART 做分类工作时，采用 GINI 值作为节点分裂的依据；回归时，采用样本的最小方差作为节点的分裂依据。工程上总的来说:
CART 和 C4.5 之间主要差异在于分类结果上，CART 可以回归分析也可以分类，C4.5 只能做分类；C4.5 子节点是可以多分的，而 CART 是无数个二叉子节点；
以此拓展出以 CART 为基础的 “树群” Random forest ， 以 回归树 为基础的 “树群” GBDT 。
1.3、树回归 工作原理
1、找到数据集切分的最佳位置，函数 chooseBestSplit() 伪代码大致如下:
对每个特征: 对每个特征值: 将数据集切分成两份（小于该特征值的数据样本放在左子树，否则放在右子树） 计算切分的误差 如果当前误差小于当前最小误差，那么将当前切分设定为最佳切分并更新最小误差 返回最佳切分的特征和阈值2、树构建算法，函数 createTree() 伪代码大致如下:
找到最佳的待切分特征: 如果该节点不能再分，将该节点存为叶节点 执行二元切分 在右子树调用 createTree() 方法 在左子树调用 createTree() 方法1.4、树回归 算法特点
优点：可以对复杂和非线性的数据建模。 缺点：结果不易理解。 适用数据类型：数值型和标称型数据。
