目录
一、基本流程
二、划分选择
2.1 信息增益
2.2 增益率
2.3 基尼指数
三、剪枝处理
四、连续值和缺失值处理
4.1 连续值处理
4.1.1 二分法
4.2 缺失值处理
五、多变量决策树
六、sklearn 训练决策树
六、决策树特点总结
一、基本流程
一般的，一棵决策树包含一个根结点，若干个内部结点和若干个叶结点；在叶结点给出决策结果，其它结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点之中。从根节点到每个叶结点的路径都对应一个判定的序列。决策树的基本流程遵循简单且直观的“分而治之”策略。
输入：
训练集：
属性集：
函数 TreeGenerate(D, A)
从 A 中选择最优划分属性 ai;
for ai 的每一个值 aij do
为结点生成一个分支; 令 Dj 表示 D 在 ai 上取值为 aij 的样本子集;
if Dj 为空 then
将分支结点作为叶结点，其类别标记为 D 中样本最多的类; return
else
以 TreeGenerate(Dj, A {ai}) 为分支结点
endif
endfor
决策树基本算法的递归返回原因：
- 当前结点包含的样本属于同一类别无法划分
- 当前属性集为空或者所有样本在属性上的取值相同无法划分，此时标记为叶结点，并将类别设置为该结点所含样本最多的类别。
- 当前结点包含的样本集合为空无法划分，将其设置为叶结点并将其类别设置为父结点所含样本最多的类别。
二、划分选择
2.1 信息增益
信息熵是用于度量样本集合纯度的指标。假定当前样本集合 D 中第 k 类（样本共有 n 个类别）样本具有的比例是 ，则样本 D 的信息熵定义为：
Ent(D) 的值越小，说明 D 的纯度越高。
若离散属性 a 有 V 个可能的取值 ，用 a 来对样本 D 划分可以得到 V 个分支结点，其中第 v 个分支结点包含了 D 所有在属性 a 上取值为 的样本并将其记作 ；考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重 ，则可以计算出根据属性 a 划分时得到的信息增益：
信息增益越大，则说明使用属性 a 划分所获得的纯度提升越大，因此可以通过信息增益来进行决策树的划分属性选择，即选择所有属性中信息增益最大的属性作为当前的根结点。
2.2 增益率
但实际上信息增益对可取值数目较多的属性有所偏好，为了减少这种偏好带来的负面影响，可以通过增益率代替信息增益作为最优属性的选择依据。增益率的定义如下：
其中 IV(a) 称作属性 a 的固有值，其定义如下：
可见当 a 的取值数目越多， IV(a) 通常会越大。
但增益率对取值数目较少的属性有所偏好，因此可以采用先从划分属性中找出信息增益高于平均水准的属性，再从中选择增益率最高的。
2.3 基尼指数
数据集 D 的基尼指数如下定义：
基尼指数反映了从数据集 D 中抽取两个样本时，这两个样本类别不一致的概率，因此基尼指数越小，样本集 D 的纯度越高。
对于属性 a 的基尼指数定义如下：
由此可选择划分后基尼指数最小的属性作为当前的根结点。
三、剪枝处理
在决策树的训练过程中，为尽可能正确的分类样本，会不断的重复结点划分过程，有时可能导致决策树分支过多，即导致过拟合训练样本，因此可以通过主动剪枝来降低过拟合风险。
剪枝可以分为预剪枝和后剪枝两种策略：
- 预剪枝：在决策树的生成过程中，对每个结点划分前进行估计，若当前结点的划分无法带来决策树泛化性能的提升，则停止划分。
- 后剪枝：先根据训练集生成一棵完整的决策树，然后自底向上地对非叶节点进行考察，若将当前结点标记为叶结点可以带来决策树的泛化性能提升，则将该子树替换为叶结点。
预剪枝和后剪枝的优缺点如下：
| 优点 | 缺点 | |
|---|---|---|
| 预剪枝 | 降低了过拟合的风险； 减少了决策树的训练开销； | 有些分支的当前划分可能无法带来泛化性能的提升，但在后续划分中可能提高决策树的性能； 基于贪心地禁止分支的展开，可能导致欠拟合 |
| 后剪枝 | 欠拟合风险较小，泛化性能往往优于预剪枝； | 训练开销打 |
四、连续值和缺失值处理
4.1 连续值处理
由于连续属性的可取值数目不再有限，因此不能根据连续属性的可取值对其划分。
4.1.1 二分法
给定样本集 D 和连续属性 a ，假定 a 在 D 上出现了 n 个不同的取值，将这些值从小到大排序得到 ，基于划分点 t 可将 D 分为子集 和 ，前者代表着在属性 a 上取值小于 t 的样本，后者包含在属性 a 上取值大于 t 的样本。
由此，对连续属性 a 可以考察 n-1 个候选划分点集合
可以参考离散属性值一样来考察这些划分点并从中选取最优划分点，例如根据信息增益可得到改造公式如下：
需要注意，若当前结点划分属性为连续属性，该属性还可以做为后代结点的划分属性。
4.2 缺失值处理
缺失值处理需要解决两个问题：
- 如何在属性值缺失的情况下进行划分属性选择
- 给定划分属性，若样本在该属性上的值缺失如何对样本划分
给定训练集 D 和属性 a ，令 表示 D 在属性 a 上没有缺失值的样本子集，对问题1即可根据 来判断属性 a 的优劣，假定 a 有 V 个可取值 ，令 表示 中在属性 a 上取值为 的样本子集， 表示 中第 k 类的样本；假定为每个样本 x 赋予一个权重 ，且定义：
由此可以将信息增益的计算式推广为：
其中
对于问题2，若样本 x 在划分属性 a 上的取值位置，则将 x 划分到所有的子结点中，且样本权值在属性值 对应的子节点中调整为 ，可以理解为将同一样本以不同的概率划分到不同的子结点中去。
五、多变量决策树
决策树中对样本分类意味着找不同类样本之间的分类边界，决策树所形成的分类边界有一个明显的特点即轴平行，也就是分类边界是由若干个与坐标轴平行的分段组成；若真实分类比较复杂，则必须使用很多段的划分才能获得较好的近似，从而构造了一个相对复杂的决策树。
因此可以通过使用斜的划分边界，将决策树模型简化，即所谓的“多变量决策树”；此时非叶结点不再是单独的某个属性，而是属性的一种线性组合，即一个形如 的线性分类器。其中 是属性 的权重， 和 t 可以在该结点所包含的样本集和属性集上学习得到。
六、sklearn 训练决策树
首先导入数据集：
from sklearn.datasets import load_iris from sklearn.tree import DecisionTreeClassifier from sklearn.tree import export_graphviz iris = load_iris() X = iris.data y = iris.target
对数据集做一个简单的分析：
可以看到所有的鸢尾花被分为 3 种，并转化成数字 0，1，2 来表示，同时样本有 4 种属性，共有 150 个样本。
根据该样本构建一棵决策树并预览该树的代码如下：
tree_clf = DecisionTreeClassifier(max_depth=3)
tree_clf.fit(X, y)
export_graphviz(tree_clf,
out_file="./iris_tree3.dot",
feature_names=iris.feature_names,
class_names=iris.target_names,
rounded=True, filled=True)
得到的决策树模型如下：
samples 属性统计对应的训练实例数量，gini 属性对应其不纯度。
可以输入一组花的数据来对其预测。
print(tree_clf.predict_proba([[4.9, 3. , 1.4, 0.2]]))
决策树很可能过拟合，所以需要对其正则化。在 Scikit-Learn 中，有以下几种正则化方式来控制决策树：
- max_depth：最大深度
- min_samples_split：分裂前节点必须有的最小样本数
- min_samples_leaf：叶结点必须有的最小样本数
- min_weight_fraction_leaf：加权实例总数的占比
- max_leaf_nodes：最大叶结点数量
- max_feaatures：分裂每个结点评估的最大特征数量
