决策树是一种逻辑简单的机器学习算法，具有一种树形结构，因此得名。决策树是最简单的机器学习算法，它易于实现，可解释性强，完全符合人类的直观思维，有着广泛的应用。决策树模型既可以做分类也可以做回归。
- 对于分类问题。测试样本点到达的叶子节点上所有类别中样本点最多的类别，即为测试样本点的类别；
- 对于回归问题。测试样本点到达的叶子节点上所有样本点输出值的平均值，即为测试样本点的输出值；
| 节点 | 内容 |
|---|---|
| 根节点 | 包含样本全集 |
| 内部节点 | 对应特征属性 |
| 叶节点 | 决策结果 |
决策树有三个步骤 1. 特征选择
特征选择决定了使用哪些特征来做判断。在训练数据集中，每个样本的属性可能有很多个，不同属性的作用有大有小。因而特征选择的作用就是筛选出跟分类结果相关性较高的特征，也就是分类能力较强的特征。在特征选择中通常使用的准则是：信息增益。
- 决策树生成
选择好特征后，就从根节点触发，对节点计算所有特征的信息增益，选择信息增益最大的特征作为节点特征，根据该特征的不同取值建立子节点；对每个子节点使用相同的方式生成新的子节点，直到信息增益很小或者没有特征可以选择为止。
- 决策树剪枝
剪枝的主要目的是对抗“过拟合”，通过主动去掉部分分支来降低过拟合的风险。
决策树分类
根据使用的特征选择算法不同，我们将决策树分为三类
ID3 使用信息增益作为特征选择，只能处理分类问题，loss函数的评价是使用信息熵
C4.5 它是ID3的改进版本，使用信息增益比作为特征选择依据。只能处理分类问题，理由同上
CART(Classification and Regression Tree) 采用Gini系数时可以处理分类问题，采用variance系数时可以用于回归问题，如果是一个回归问题，那么每一次特征选择后，其方差更小，那么叶节点内的均值就是一个回归值。
决策树的样本处理
Gini系数
假设我们在使用Gini系数处理分类问题，对于连续特征值的特征，通过取相邻样本的平均值作为划分点，比如m个样本的连续特征A有m个，从小到大排列为\(a_1,a_2,\dots a_m\)则CART算法取相邻两样本值的平均数，一共取得m-1个划分点，其中第i个划分点\(T_i\)表示为 \(T_i = \frac{a_i + a_{i+1}}{2}\),然后就是对于这m-1个点，分别计算以该点作为二元分类点时的基尼系数。选择基尼系数最小的点作为该连续特征的二元离散分类点。比如取到的基尼系数最小的点为𝑎𝑡,则小于𝑎𝑡的值为类别1，大于𝑎𝑡的值为类别2，这样我们就做到了连续特征的离散化。要注意的是，与ID3或者C4.5处理离散属性不同的是，如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程。
对于CART分类树离散值的处理问题，采用的思路是不停的二分离散特征。
回忆下ID3或者C4.5，如果某个特征A被选取建立决策树节点，如果它有A1,A2,A3三种类别，我们会在决策树上一下建立一个三叉的节点。这样导致决策树是多叉树。但是CART分类树使用的方法不同，他采用的是不停的二分，还是这个例子，CART分类树会考虑把A分成{𝐴1}和{𝐴2,𝐴3}, {𝐴2}和{𝐴1,𝐴3}, {𝐴3}和{𝐴1,𝐴2}三种情况，找到基尼系数最小的组合，比如{𝐴2}和{𝐴1,𝐴3},然后建立二叉树节点，一个节点是A2对应的样本，另一个节点是{A1,A3}对应的节点。同时，由于这次没有把特征A的取值完全分开，后面我们还有机会在子节点继续选择到特征A来划分A1和A3。这和ID3或者C4.5不同，在ID3或者C4.5的一棵子树中，离散特征只会参与一次节点的建立。
在真实世界中，常常会面临样本具有特征缺失的情况。我们需要解决两个问题 (1)如何在属性值缺失的情况下进行划分属性选择 (2)给定划分属性，若样本在该属性上的值缺失，如何对样本划分？
variance系数
分类时，如果待分类样本有缺失变量，而决策树决策过程中没有用到这些变量，则决策过程和没有缺失的数据一样；否则，如果决策要用到缺失变量，决策树也可以在当前节点做多数投票来决定。回归的话，多数投票会换成局部回归等类似的方法。这样决策树就能给缺失变量的样本一个预测了。