定义
决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。
分类
决策树分为两大类。
第一类分类树，其目标变量是标称或分类变量，即输出的是样本的类标；
第二类是回归树，其目标变量是连续变量，即输出的是一个实数。
决策树构造步骤
决策树算法构造决策树来发现数据中蕴涵的分类规则。决策树构造可以分两步进行。
第一步 决策树的生成：由训练样本集生成决策树的过程。
第二步 决策树的剪枝：决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修下的过程，主要是将那些影响预衡准确性的分枝剪除。
决策树的实现
决策树主要有三种实现，分别是ID3算法，CART算法和C4.5算法。CART决策树的生成就是递归地构建二叉决策树的过程。CART决策树既可以用于分类也可以用于回归。
本文我们仅讨论用于分类的CART。对分类树而言，CART用Gini系数最小化准则来进行特征选择，生成二叉树。
定义
Classification And Regression Tree，即分类回归树算法，简称CART算法，它是一种二分递归分割技术，把当前样本拆分为两个子样本，使得生成的每个非叶子结点都有两个分支，因此CART算法生成的决策树是结构简洁的二叉树，它在每一步的决策时只能是“是”或者“否”。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。
步骤
Step1 对训练数据集递归划分进行建树
Step2 用验证数据进行剪枝并选择最优子树
设x1，x2，…，xn代表单个样本的n个属性，y代表所属类别。CART算法则通过递归的方法将n维的空间划分为不重叠的矩形。划分步骤大致如下：
步骤一
选一个自变量xi，再选取xi的一个值vi，vi把维空间划分为两部分，一部分的所有点都满足xi < v或xi = vii，另一部分的所有点都满足xi > vi，对非连续变量来说属性值的取值只有两个，即等于该值或不等于该值。
步骤二
递归处理，将上面得到的两部分按步骤一重新选取一个属性继续划分，直到把整个维空间都划分完。
“在划分时候有一个问题，它是按照什么标准来划分的呢？”
对于一个变量属性来说，它的划分点是一对连续变量属性值的中点。假设m个样本集合的一个属性有m个连续的值，那么则会有个m-1分裂点，每个分裂点为相邻两个连续值的均值。每个属性的划分按照能减少的杂质的量来进行排序，而杂质的减少量定义为划分前的杂质减去划分后的每个节点的杂质量划分所占比率之和。
而杂质度量方法常用Gini指标，假设一个样本共有C类，那么一个节点A的Gini不纯度可定义为：
其中pi表示属于i类的概率，当Gini(A)=0时，所有样本属于同类，所有类在节点中以等概率出现时，Gini(A)最大化，且等于C(C-1)/2。
有了上述理论基础，实际的递归划分过程是这样的：如果当前节点的所有样本都不属于同一类或者只剩下一个样本，那么此节点为非叶子节点，所以会尝试样本的每个属性以及每个属性对应的分裂点，尝试找到杂质变量最大的一个划分，该属性划分的子树即为最优分支。
分数越高，意味着对应的参数越优，因此我们能够通过图像选择出最优的参数。
