决策树，一种常见的机器学习方法，有种类似于流程图那样的。就是对一个样本按其某个特征的取值将其划分到一个集合中，并递归下去
基本算法
Input: 训练集\(D=\\{(\mathbf{x_1},y_1),(\mathbf{x_2},y_2),...,(\mathbf{x_m},y_m)\\}\); 属性集\(A=\\{a_1,a_2,...,a_d\\}\)
Output: 以node为根结点的一颗决策树
简单过程：
以某一划分标准，选择最优的特性来划分样本，这样递归下去，最终得到决策树的分支结点
重要的是找到一当前的最优划分属性，使决策树的分支结点所包含的样本尽可能属于同一类别，即结点的纯度越高
基本套路
信息熵与信息增益
假定当前样本集合D中第k类样本所占的比例为\(p_k \ (k=1,2,3,...,\vert y\vert)\)，则D的信息熵定义为：
\[Ent(D) = -\sum_{k=1}^{\vert y\vert} p_k\log_{2}p_k\]
其中约定，若\(p=0\),则\(p\log_{2}p = 0\)，有\(0 \le Ent(D) \le \log_{2}\vert y\vert\)，\(Ent(D)\)的值越小，则D的纯度越小
若属性a有V个可能的取值\(\\{a^1,a^2,...,a^V\\}\)，用a对样本集D进行划分会产生V个分支结点，其中第v个分支结点包含了D中所有在属性a上取值为\(a^v\)的样本，即为\(D^v\)，则可得用属性a对样本集进行划分所获得的信息增益为：
\[Gain(D,a) = Ent(D)-\sum_{v=1}^V \frac{\vert D^v\vert}{\vert D\vert} Ent(D^v)\]
一般来说，信息增益越大，则意味着使用属性a进行划分所得到的纯度提升越大，所以我们可以采用信息增益来作为划分准则，这就是ID3决策树学习算法
增益率
在上面中，我们采用了信息增益来作为我们的划分准则，但信息增益偏好于选择类别较多的属性来进行划分，假若我们有一个特征列为id，则信息增益会优先选择id这一特征进行划分，但这并非我们的目的。为此，我们考虑在信息增益的基础上加上一个与类别个数成正比的正则项，这就得到了增益率（又称信息增益比）：
\[ \begin{aligned} Gain\_raito(D,a) = \frac{Gain(D,a)}{IV(a)} \\ IV(a) = -\sum_{v=1}^V \frac{\vert D^v\vert}{\vert D\vert} \log_{2}\frac{\vert D^v\vert}{\vert D\vert} \end{aligned} \]
增益率准则偏好于选择取值较少的属性，而C4.5决策树算法则以增益率为基础加入了一个启发式设计，即先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的
基尼系数
信息熵是衡量信息不确定性的指标，实际上也是衡量信息纯度的指标，而基尼系数也是衡量这一方面的指标，计算如下：
\[ \begin{aligned} Gini(D) & = \sum_{k=1}^{\vert y\vert} \sum_{k‘ \neq k} p_kp_{k’} \\ & = \sum_{k=1}^{\vert y\vert} p_k(1-p_k) \\ & = 1-\sum_{k=1}^{\vert y\vert} {p_k}^2 \end{aligned} \]
其中\(p_k\)表示样本属于第k类的概率，Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此Gini(D)越小，则数据集D的纯度越高
对于属性a的基尼系数，为属性a取值的基尼系数加权和，即：
\[Gini\_index(D,a) = \sum_{v=1}^V \frac{\vert D^v\vert}{\vert D\vert} Gini(D^v)\]
故在候选属性集A中，我们应该选择那个使得划分后基尼系数最小的属性作为最优划分属性：
\[a_* = argmin_{a \in A} Gini\_index(D,a)\]
基于基尼系数来进行划分的即为CART决策树算法
优化处理
对于决策树的过拟合处理，主要有前剪枝和后剪枝两种方法
前剪枝
前剪枝是指在决策树构造过程中，对每个结点在划分前后进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分并将当前结点作为叶结点
后剪枝
后剪枝则是在决策树构造完成之后，自底向上地对非叶子结点进行检查，若将该结点对应的子树替换为叶子结点能带来泛化性能的提升，则将该子树替换为叶子结点
前后剪枝的比较
| 项目 | 前剪枝 | 后剪枝 |
|---|---|---|
| 训练时间开销 | 小 | 大 |
| 测试时间开销 | 小 | 小 |
| 过拟合风险 | 小 | 小 |
| 欠拟合风险 | 大 | 小 |
泛化性能方面：后剪枝优于前剪枝
Scikit-learn应用
具体API参数查看官网：
sklearn.tree.DecisionTreeClassifier
致谢
周志华的西瓜书，李航的统计学习方法