1. 基本流程

决策树是基于树结构的决策算法，包括一个根结点，若干个内部节点和叶子结点。叶子结点对应于决策结果，其他每个节点对应于一个属性测试。如图所示：

决策树的生成是一个递归过程，在决策树基本算法中，有三种情形会导致递归返回：

（1）当前节点包含的样本全属于同一类别；

（2）当前属性集为空，或是所有样本在所有属性集上取值相同；

（3）当前节点包含的样本集合为空。

2. 划分选择

2.1信息增益

信息熵
“信息熵”是衡量样本集合纯度的一种指标。
假设当前集合D中第k类样本所占的比例为$p_k(k=1,2,....,n)$,则信息熵定义为：
$$Ent(D)=-\sum _{k=1}^n{p}_{k}lo{g}_2{p}_k$$

假设离散属性a有V个可能的取值，那么使用属性a进行划分，产生V个分支节点，第v个分支节点的样本记为$D^v$,那么属性a对集合D划分所得的“信息增益”为：
$$Gain(D,a)=Ent(D)-\sum _{v=1}^V\frac{\left|D^v\right|}{\left|D\right|}Ent(D^v)$$

我们使用信息增益来进行节点划分，信息增益越大，使用该属性进行划分越好。（ID3）

2.2信息增益率

信息增益对可取值数目较多的属性有所偏好，信息增益率避免了这一点，信息增益率定义如下：

$$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$$

固有值函数$IV(a)$来计算属性a的固有值，使该函数满足：属性可取值数目越多，固有值越大:

$$IV(a)=-\sum _{v=1}^V\frac{\left|D^v\right|}{\left|D\right|}lo{g}_2\frac{\left|D^v\right|}{\left|D\right|}$$

注意：信息增益率对可取值数目较少的属性有所偏好，C4.5并不是直接选择信息增益率最大的属性，而是使用了一个启发式：先从候选划分属性中找到信息增益高于平均水平的属性，再选择增益率最高的。

2.3基尼指数

数据集D的纯度使用基尼值来度量：
$$Gini(D)=\sum _{k=1}^n\sum _{k^{{}^{\prime }}\ne k}{p}_k{p}_{k^{{}^{\prime }}}$$
属性a的基尼指数定义为：
$$Gini\_index(D,a)=\sum _{v=1}^V\frac{\left|D^v\right|}{\left|D\right|}Gini(D^v)$$
基尼指数反映了从数据集D中随机抽取两个样本，其类别不一致的概率。

划分时，选择那个使得划分后基尼指数最小的那个属性，CART决策树使用基尼指数来划分属性。

3. 解决过拟合

3.1剪枝

预剪枝
预剪枝是指在决策树生成过程中，对每个节点在划分前进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分节点并将当前节点标记为叶节点。
缺点：欠拟合
后剪枝
先生成完整的决策树，自底向上，若将该节点对应的子树替换为叶子节点能带来决策树泛化性能提升，则将该子树替换为叶节点。
优点：欠拟合风险小
缺点：生成完全决策树，所有非叶子节点进行考察，训练时间开销大。

3.2正则化

L1,L2正则化也可以使用，详细后补

4.多变量决策树

决策树的决策边界一般是线性的，如果想要解决非线性问题可以使用多变量决策树，对复杂边界进行分段近似。即每个节点的划分不再是根据单一属性，而是根据某些属性的线性组合。

在多变量决策树的学习过程中，不是为每个非叶节点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。

5.决策树回归

CART是一个典型的可用于回归的决策树。
当数据集的因变量为连续性数值时，该树算法就是一个回归树，可以用叶节点观察的均值作为预测值；
该算法是一个二叉树，即每一个非叶节点只能引伸出两个分支，所以当某个非叶节点是多水平(2个以上)的离散变量时，该变量就有可能被多次使用。