决策树，顾名思义，它是一棵能对问题做出决策的树。
决策树是线性模型，既可以处理分类问题，也能解决回归问题，属于有监督学习的一种。
决策树的每一个非叶子结点都是对数据个体某一个特征的判断。
决策树的叶子节点决定了判定的类别，对分类任务采用简单投票法，对回归任务采用简单平均法。
每次决策后，希望子节点的“纯度”得到提升，即“熵“减小。
因此，构造决策树的问题就聚焦于”如何选择结点的顺序？“。对于下图来说，即”色泽在前还是根蒂在前好呢？“。
如何选择节点的顺序
- 信息增益：
- 信息增益越高，即熵越小，意味着子节点的”纯度“提升越大
- 信息增益对可取值数目较多的属性有所偏好
- ID3决策树算法以信息增益作为选择准则
- 增益率：
- 增益率对可取值数目较少的属性有所偏好
- 它使用了启发式选择方法：先从候选结点中找出信息增益高于平均水平的属性，再从中选择增益率最高的
- C4.5决策树算法以信息率作为选择准则
- 基尼指数：
- 基尼指数越小，意味着子节点的”纯度“提升越大
- CART决策树以基尼指数作为选择准则
如何避免过拟合
- 采取预剪枝和后剪枝的手段
- 预剪枝会带来欠拟合的风险
- 后剪枝的泛化性能往往优于预剪枝，但训练开销更大
单变量决策树的划分边界平行于坐标轴。
多变量决策树的划分边界可以是斜直线。