第四章 决策树
1. 概述2. 特征选择2.1 信息增益2.2 信息增益率2.3 基尼指数
3. 决策树生成4. 决策树剪枝4.1 预剪枝4.2 后剪枝
5. 连续与缺失值5.1 连续值处理5.2 缺失值处理
6. 多变量决策树7. sklearn中决策树模型参数释义8. 实际使用技巧9. 课后练习参考答案
1. 概述
决策树（decision tree）是一种基本的分类与回归方法。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合（互斥并且完备），也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据利用决策树模型进行分类。决策树学习通常包括三个步骤：特征选择、决策树的生成和决策树的修剪。
特征选择：从训练数据的特征中选择一个特征作为当前节点的分裂标准（特征选择的标准不同产生了不同的特征决策树算法）。决策树生成：根据所选特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止声场。决策树剪枝：决策树容易过拟合，需要剪枝来缩小树的结构和规模（包括预剪枝和后剪枝）。
决策树学习的本质是从训练数据集中归纳出一组分类规则或者说是条件概率模型，与训练数据集不相矛盾的决策树可能有多个或者一个没有，我们需要找到一个与训练数据集矛盾较小的决策树，同时具有很好的泛化能力。换句话说，我们选择的条件概率模型应该不仅对现有的训练数据集有很好的拟合效果，而且能够对未知的数据有很好的预测（泛化能力）。实现的方法通过以上的三个方法。 决策树特点：
优点：
计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。准确性高: 挖掘出来的分类规则准确性高, 便于理解, 决策树可以清晰的显示哪些字段比较重要, 即可以生成可以理解的规则。可以处理连续和离散字段不需要任何领域知识和参数假设适合高维数据 缺点：对于各类别样本数量不一致的数据, 信息增益偏向于那些更多数值的特征容易过拟合忽略属性之间的相关性
适用数据类型：数值型和标称型
2. 特征选择
特征选择决定用哪个特征来划分空间，即如何选择最优划分属性。在划分的过程中，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。 特征选择的准则：信息增益、信息增益比（增益率）、基尼指数
数据集
2.1 信息增益
熵是表示随机变量不确定性的度量。熵只依赖于D的分布，与D的取值无关。
信息增益表示在得知特征D的属性对应的属性值的种类和个数a后，而使得类信息不确定性的减少程度。 熵（不确定性）与条件熵（知道信息以后可确定的部分）之差称为互信息，决策树学习中的信息增益等价于训练数据集中类与特征的互信息。 信息增益准则的特征选择方法：对于训练集，计算每个特征D的信息增益，选择信息增益最大的特征作为特征选择的属性。
2.2 信息增益率
为什么引入信息增益率？ 这是为了解决信息增益的使用过程中，对属性值种类较多的属性比较偏好，这个问题，所以引入信息增益率。比如当误把编号当成属性时，此时条件熵为0，信息增益达到最大，因此将选择编号作为分类的一个属性，这显然是不合理的。
需要注意的是，信息增益率对属性值较少的属性比较偏好，因此，C4.5算法并不是直接选择增益率最大的作为候选划分属性，而是使用一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性（保证属性值多的属性被选择），再从中选择增益率最高的（在属性值多的属性中挑属性值少的属性），这样是保证了相对准确。
2.3 基尼指数
3. 决策树生成
决策树生成算法：
输入：训练数据集D，特征集A，阈值ε（预剪枝用，后剪枝不需要此项）；
输出：决策树T。
（1）若D中所有样本属于同一类
C
k
C_k
Ck,则 T 为单结点树，并将
C
k
C_k
Ck作为该结点的类标记，返回T；
（2）若A = Ø,则T为单结点树，并将D中样本数最多的类
C
k
C_k
Ck作为该结点的类标记，返回T；
（3）否则，计算A中各个特征对D的信息增益或者信息增益比，选择信息增益或信息增益比最大的特征
A
g
A_g
Ag；
（4）如果
A
g
A_g
Ag 的信息增益或信息增益比小于阈值ε，则置T为但结点树，并将D中样本数最多的类Ck作为该结点的类标记，返回T；（后剪枝没有这步）
（5）如果
A
g
A_g
Ag的每一种可能值
a
i
a_i
ai，依
A
g
=
a
i
A_g = a_i
Ag=ai 将D分割为若干非空子集
D
i
D_i
Di，将
D
i
D_i
Di中样本数最多的类作为标记，构建子结点，由结点及其子结点构成树T，返回T；
（6）对第i个子结点，以
D
i
D_i
Di为训练集，以
A
−
A
g
A-{A_g}
A−Ag为特征集，递归地调用步骤（1）~（5），得到子树
T
i
T_i
Ti，返回
T
i
T_i
Ti 。
ID3算法 在决策树生成过程中，以信息增益为特征选择的准则。
C4.5算法 在决策树生成过程中，以信息增益比为特征选择的准则。
CART算法 在决策树生成过程中，以基尼指数为特征选择的准则。
4. 决策树剪枝
首先剪枝的目的是为了避免决策树模型的过拟合。因为决策树算法在学习的过程中为了尽可能的正确的分类训练样本，不停地对结点进行划分，因此这会导致整棵树的分支过多，也就导致了过拟合。决策树的剪枝策略最基本的有两种：预剪枝和后剪枝。
预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；
后剪枝是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则该子树替换为叶结点。
如何判断决策树泛化性能是否提升呢？可以选择一种性能评估方法（留出法、交叉验证法、自助法等）。
将数据集划分为训练集和验证集
4.1 预剪枝
基于信息增益准则，我们会选择属性“脐部”来对训练集进行划分，并产生3个分支。在划分前，所有样例集都在根结点，若不进行划分，并假设将叶节点标记为“好瓜”，用表4.2的验证集对这个单节点决策树进行评估，则编号为{4,5,8}的样例被分类正确，于是验证集精度为 3/7*100% = 42.9%。在用属性“脐部”划分之后：
预剪枝的特点：
预剪枝使得决策树的很多分支都没有展开，直接被剪枝。
优点：降低过拟合的风险，显著减少了决策树的训练时间开销和测试时间开销。缺点：欠拟合，有些分支的当前划分虽然不能提高泛化能力，但是后续的一些分支有可能导致性能的显著提高，这样直接基于当前属性的信息增益准则去剪枝，容易带来欠拟合的风险。
4.2 后剪枝
后剪枝先从训练集生成一棵完整的决策树，然后利用验证集的精度和奥卡姆剃刀准则进行剪枝。
后剪枝的特点：
后剪枝使得决策树完全展开（先可能产生过拟合，然后再剪枝），剪枝过程通过自底向上地对树中的所有非叶节点进行逐一考察。
优点：降低欠拟合的风险，泛化性能往往优于预剪枝决策树。缺点：训练时间和测试时间要比预剪枝决策树大的多
5. 连续与缺失值
5.1 连续值处理
当属性中存在连续值属性（比率变量），连续属性离散化技术可派上用场，C4.5决策树算法中采用二分法对连续属性进行处理。 假定样本集D和连续属性a，假定属性a有n个不同的取值，对n进行排序{
a
1
,
a
2
,
…
,
a
n
{a^1,a^2,…,a^n}
a1,a2,…,an}，用二分法基于划分点t可将D划分成两个子集，比如在
a
1
a^1
a1与
a
2
a^2
a2之间的划分点
t
=
a
1
+
a
2
2
t = \frac{a^1+a^2}{2}
t=2a1+a2，根据值的个数，可以找到n-1个候选的划分点集合：
T
a
=
{
a
i
+
a
i
+
1
2
∣
1
≤
i
≤
n
−
1
}
T_a =\lbrace \frac{a^i+a^{i+1}}{2}|1\leq i\leq n-1\rbrace
Ta={2ai+ai+1∣1≤i≤n−1}
比较每个划分点的信息增益，选择信息增益最大的划分点。
G
a
i
n
(
D
,
a
)
=
max
t
∈
T
a
G
a
i
n
(
D
,
a
,
t
)
=
max
t
∈
T
a
E
n
t
(
D
)
−
∑
λ
∈
{
−
,
+
}
∣
D
t
λ
∣
D
E
n
t
(
D
t
λ
)
Gain(D,a) = \max_{t\in T_a} Gain(D,a,t) =\max_{t\in T_a} Ent(D)-\sum_{\lambda\in\lbrace-,+\rbrace}\frac{|D_t^\lambda|}{D} {Ent(D_t^\lambda)}
Gain(D,a)=t∈TamaxGain(D,a,t)=t∈TamaxEnt(D)−λ∈{−,+}∑D∣Dtλ∣Ent(Dtλ)
其中
G
a
i
n
(
D
,
a
,
t
)
Gain(D,a,t)
Gain(D,a,t)是样本集D基于划分点 t 二分后的信息增益。
需要注意的是，与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性，例如在父节点上使用了“密度<=0.381”,不会禁止在子节点上使用“密度<=0.294”。
这样可以解决什么问题呢？
采用二分法去离散连续属性，这样得到的仅是两个值，也许使用三个值或者四个值就可以将类别完全区分开，因此这时可以在子节点再次使用二分法，相当于使用三个值或者四个值进行分类。
5.2 缺失值处理
解决两个问题： （1）如何在属性值缺失的情况下进行属性选择？ 去掉该属性缺失的属性值对应的样本，然后计算信息增益，然后用无缺失值的样本所占比例乘以去除缺失值的属性的信息增益。 （2）在给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？ 如果样本在该属性上的值缺失，那将该样本放到所有的分支中，并赋以不同的权重，权重为各分支的样本数占排除该属性值为缺失的样本总数比例。C4.5算法就是采用了这一方式。
注意：初始根节点的各样本权重为1。
6. 多变量决策树
决策树所形成的分类边界有个明显的特点：轴平行，即它的分类边界由若干个与坐标轴平行的分段组成。这样的分类边界使得学习结果有较好的可解释性，因为每一段划分都直接对应了某个属性取值。 但是此时决策树会相当复杂，由于要进行大量的属性测试，预测时间开销会很大。
这时引入多变量决策树，可以实现斜划分甚至更复杂的划分形式。 以实现斜划分的多变量决策树为例，非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试，也就是说试图在非叶节点处建立一个合适的线性分类器。
公式参考: [https://mp.csdn.net/mdeditor/90483885#]
7. sklearn中决策树模型参数释义
'''
scikit-learn中有两类决策树，它们均采用优化的CART决策树算法。
'''
from sklearn
.tree
import DecisionTreeRegressor
'''
回归决策树
'''
DecisionTreeRegressor
(criterion
="mse",
splitter
="best",
max_depth
=None,
min_samples_split
=2,
min_samples_leaf
=1,
min_weight_fraction_leaf
=0.,
max_features
=None,
random_state
=None,
max_leaf_nodes
=None,
min_impurity_decrease
=0.,
min_impurity_split
=None,
presort
=False)
'''
参数含义：
1.criterion:string, optional (default="mse")
它指定了切分质量的评价准则。默认为'mse'(mean squared error)。
2.splitter:string, optional (default="best")
它指定了在每个节点切分的策略。有两种切分策咯：
(1).splitter='best':表示选择最优的切分特征和切分点。
(2).splitter='random':表示随机切分。
3.max_depth:int or None, optional (default=None)
指定树的最大深度。如果为None，则表示树的深度不限，直到
每个叶子都是纯净的，即叶节点中所有样本都属于同一个类别，
或者叶子节点中包含小于min_samples_split个样本。
4.min_samples_split:int, float, optional (default=2)
整数或者浮点数，默认为2。它指定了分裂一个内部节点(非叶子节点)
需要的最小样本数。如果为浮点数(0到1之间)，最少样本分割数为ceil(min_samples_split * n_samples)
5.min_samples_leaf:int, float, optional (default=1)
整数或者浮点数，默认为1。它指定了每个叶子节点包含的最少样本数。
如果为浮点数(0到1之间)，每个叶子节点包含的最少样本数为ceil(min_samples_leaf * n_samples)
6.min_weight_fraction_leaf:float, optional (default=0.)
它指定了叶子节点中样本的最小权重系数。默认情况下样本有相同的权重。
7.max_feature:int, float, string or None, optional (default=None)
可以是整数，浮点数，字符串或者None。默认为None。
(1).如果是整数，则每次节点分裂只考虑max_feature个特征。
(2).如果是浮点数(0到1之间)，则每次分裂节点的时候只考虑int(max_features * n_features)个特征。
(3).如果是字符串'auto',max_features=n_features。
(4).如果是字符串'sqrt',max_features=sqrt(n_features)。
(5).如果是字符串'log2',max_features=log2(n_features)。
(6).如果是None，max_feature=n_feature。
8.random_state:int, RandomState instance or None, optional (default=None)
(1).如果为整数，则它指定了随机数生成器的种子。
(2).如果为RandomState实例，则指定了随机数生成器。
(3).如果为None，则使用默认的随机数生成器。
9.max_leaf_nodes:int or None, optional (default=None)
(1).如果为None，则叶子节点数量不限。
(2).如果不为None，则max_depth被忽略。
10.min_impurity_decrease:float, optional (default=0.)
如果节点的分裂导致不纯度的减少(分裂后样本比分裂前更加纯净)大于或等于min_impurity_decrease，则分裂该节点。
个人理解这个参数应该是针对分类问题时才有意义。这里的不纯度应该是指基尼指数。
回归生成树采用的是平方误差最小化策略。分类生成树采用的是基尼指数最小化策略。
加权不纯度的减少量计算公式为：
min_impurity_decrease=N_t / N * (impurity - N_t_R / N_t * right_impurity
- N_t_L / N_t * left_impurity)
其中N是样本的总数，N_t是当前节点的样本数，N_t_L是分裂后左子节点的样本数，
N_t_R是分裂后右子节点的样本数。impurity指当前节点的基尼指数，right_impurity指
分裂后右子节点的基尼指数。left_impurity指分裂后左子节点的基尼指数。
11.min_impurity_split:float
树生长过程中早停止的阈值。如果当前节点的不纯度高于阈值，节点将分裂，否则它是叶子节点。
这个参数已经被弃用。用min_impurity_decrease代替了min_impurity_split。
12.presort： bool, optional (default=False)
指定是否需要提前排序数据从而加速寻找最优切分的过程。设置为True时，对于大数据集
会减慢总体的训练过程；但是对于一个小数据集或者设定了最大深度的情况下，会加速训练过程。
属性：
1.feature_importances_ : array of shape = [n_features]
特征重要性。该值越高，该特征越重要。
特征的重要性为该特征导致的评价准则的（标准化的）总减少量。它也被称为基尼的重要性
2.max_feature_:int
max_features推断值。
3.n_features_：int
执行fit的时候，特征的数量。
4.n_outputs_ : int
执行fit的时候，输出的数量。
5.tree_ : 底层的Tree对象。
Notes：
控制树大小的参数的默认值（例如``max_depth``，``min_samples_leaf``等）导致完全成长和未剪枝的树，
这些树在某些数据集上可能表现很好。为减少内存消耗，应通过设置这些参数值来控制树的复杂度和大小。
方法：
1.fit(X,y):训练模型。
2.predict(X):预测。
'''
from sklearn
.tree
import DecisionTreeClassifier
'''
分类决策树
'''
DecisionTreeClassifier
(criterion
="gini",
splitter
="best",
max_depth
=None,
min_samples_split
=2,
min_samples_leaf
=1,
min_weight_fraction_leaf
=0.,
max_features
=None,
random_state
=None,
max_leaf_nodes
=None,
min_impurity_decrease
=0.,
min_impurity_split
=None,
class_weight
=None,
presort
=False)
'''
参数含义：
1.criterion:string, optional (default="gini")
(1).criterion='gini',分裂节点时评价准则是Gini指数。
(2).criterion='entropy',分裂节点时的评价指标是信息增益。
2.max_depth:int or None, optional (default=None)。指定树的最大深度。
如果为None，表示树的深度不限。直到所有的叶子节点都是纯净的，即叶子节点
中所有的样本点都属于同一个类别。或者每个叶子节点包含的样本数小于min_samples_split。
3.splitter:string, optional (default="best")。指定分裂节点时的策略。
(1).splitter='best',表示选择最优的分裂策略。
(2).splitter='random',表示选择最好的随机切分策略。
4.min_samples_split:int, float, optional (default=2)。表示分裂一个内部节点需要的做少样本数。
(1).如果为整数，则min_samples_split就是最少样本数。
(2).如果为浮点数(0到1之间)，则每次分裂最少样本数为ceil(min_samples_split * n_samples)
5.min_samples_leaf: int, float, optional (default=1)。指定每个叶子节点需要的最少样本数。
(1).如果为整数，则min_samples_split就是最少样本数。
(2).如果为浮点数(0到1之间)，则每个叶子节点最少样本数为ceil(min_samples_leaf * n_samples)
6.min_weight_fraction_leaf:float, optional (default=0.)
指定叶子节点中样本的最小权重。
7.max_features:int, float, string or None, optional (default=None).
搜寻最佳划分的时候考虑的特征数量。
(1).如果为整数，每次分裂只考虑max_features个特征。
(2).如果为浮点数(0到1之间)，每次切分只考虑int(max_features * n_features)个特征。
(3).如果为'auto'或者'sqrt',则每次切分只考虑sqrt(n_features)个特征
(4).如果为'log2',则每次切分只考虑log2(n_features)个特征。
(5).如果为None,则每次切分考虑n_features个特征。
(6).如果已经考虑了max_features个特征，但还是没有找到一个有效的切分，那么还会继续寻找
下一个特征，直到找到一个有效的切分为止。
8.random_state:int, RandomState instance or None, optional (default=None)
(1).如果为整数，则它指定了随机数生成器的种子。
(2).如果为RandomState实例，则指定了随机数生成器。
(3).如果为None，则使用默认的随机数生成器。
9.max_leaf_nodes: int or None, optional (default=None)。指定了叶子节点的最大数量。
(1).如果为None,叶子节点数量不限。
(2).如果为整数，则max_depth被忽略。
10.min_impurity_decrease:float, optional (default=0.)
如果节点的分裂导致不纯度的减少(分裂后样本比分裂前更加纯净)大于或等于min_impurity_decrease，则分裂该节点。
加权不纯度的减少量计算公式为：
min_impurity_decrease=N_t / N * (impurity - N_t_R / N_t * right_impurity
- N_t_L / N_t * left_impurity)
其中N是样本的总数，N_t是当前节点的样本数，N_t_L是分裂后左子节点的样本数，
N_t_R是分裂后右子节点的样本数。impurity指当前节点的基尼指数，right_impurity指
分裂后右子节点的基尼指数。left_impurity指分裂后左子节点的基尼指数。
11.min_impurity_split:float
树生长过程中早停止的阈值。如果当前节点的不纯度高于阈值，节点将分裂，否则它是叶子节点。
这个参数已经被弃用。用min_impurity_decrease代替了min_impurity_split。
12.class_weight:dict, list of dicts, "balanced" or None, default=None
类别权重的形式为{class_label: weight}
(1).如果没有给出每个类别的权重，则每个类别的权重都为1。
(2).如果class_weight='balanced'，则分类的权重与样本中每个类别出现的频率成反比。
计算公式为：n_samples / (n_classes * np.bincount(y))
(3).如果sample_weight提供了样本权重(由fit方法提供)，则这些权重都会乘以sample_weight。
13.presort:bool, optional (default=False)
指定是否需要提前排序数据从而加速训练中寻找最优切分的过程。设置为True时，对于大数据集
会减慢总体的训练过程；但是对于一个小数据集或者设定了最大深度的情况下，会加速训练过程。
属性:
1.classes_:array of shape = [n_classes] or a list of such arrays
类别的标签值。
2.feature_importances_ : array of shape = [n_features]
特征重要性。越高，特征越重要。
特征的重要性为该特征导致的评价准则的（标准化的）总减少量。它也被称为基尼的重要性
3.max_features_ : int
max_features的推断值。
4.n_classes_ : int or list
类别的数量
5.n_features_ : int
执行fit后，特征的数量
6.n_outputs_ : int
执行fit后，输出的数量
7.tree_ : Tree object
树对象，即底层的决策树。
方法:
1.fit(X,y):训练模型。
2.predict(X):预测
3.predict_log_poba(X):预测X为各个类别的概率对数值。
4.predict_proba(X):预测X为各个类别的概率值。
'''
8. 实际使用技巧
对于拥有大量特征的数据决策树会出现过拟合的现象。获得一个合适的样本比例和特征数量十分重要，因为在高维空间中只有少量的样本的树是十分容易过拟合的。考虑事先进行降维( PCA , ICA ，使您的树更好地找到具有分辨性的特征。通过 export 功能可以可视化您的决策树。使用 max_depth=3 作为初始树深度，让决策树知道如何适应您的数据，然后再增加树的深度。请记住，填充树的样本数量会增加树的每个附加级别。使用 max_depth 来控制输的大小防止过拟合。通过使用 min_samples_split 和 min_samples_leaf 来控制叶节点上的样本数量。当这个值很小时意味着生成的决策树将会过拟合，然而当这个值很大时将会不利于决策树的对样本的学习。所以尝试 min_samples_leaf=5 作为初始值。如果样本的变化量很大，可以使用浮点数作为这两个参数中的百分比。两者之间的主要区别在于 min_samples_leaf 保证叶结点中最少的采样数，而 min_samples_split 可以创建任意小的叶子，尽管在文献中 min_samples_split 更常见。在训练之前平衡您的数据集，以防止决策树偏向于主导类.可以通过从每个类中抽取相等数量的样本来进行类平衡，或者优选地通过将每个类的样本权重 (sample_weight) 的和归一化为相同的值。还要注意的是，基于权重的预修剪标准 (min_weight_fraction_leaf) 对于显性类别的偏倚偏小，而不是不了解样本权重的标准，如min_samples_leaf。
9. 课后练习参考答案
[https://blog.csdn.net/icefire_tyh/article/details/52081556]
参考文献： [1] [统计学习-李航] [2] [机器学习西瓜书-周志华] [3][Python大战机器学习]
