机器学习之决策树：原理及ID3算法手动实现，sklearn.tree.DecisionTreeClassifier参数详解

1. 决策树简介

决策树是一种基本的分类与回归方法，本文主要讨论用于分类的决策树。决策树模型是一种树形结构，在分类问题中表示基于特征对实例进行分类的过程。决策树的学习主要包括3个步骤：特征选择，决策树的生成，决策树的剪枝。
决策树的学习策略是损失函数最小化，这个损失函数通常是正则化的极大似然函数。

1.1 决策树模型

1.1.1 决策树模型——$Y=DTree(X)$

分类决策树是一种描述对实例分类的树形结构，决策树由节点和有向边组成，节点分为叶节点(leaf node)和内部节点(internal node)，内部节点表示一个特征(根节点也是一个内部节点)，而叶节点表示一个类。如图：

一般一个内部节点N（含根节点）包含一个数据集$D_i$（根节点包含全数据集D）以及一个特征x，这个节点发出的有向边代表该特征的取值$x_i$，有向边指向的节点为上一个节点包含数据集Di中满足x=$x_i$的样本。
对于一棵训练好的决策树，输入一个用于预测的实例X，该实例会从根节点的属性开始，依据它自身该属性的取值划分到下一个子节点，直到最后划分到了一个叶节点就停止，而每个也节点都有一个对应的标签Y。所以决策树模型可以表示为 $Y=DTree(X)$，其中的DTree就是决策树所代表的规则，这个规则没法像线性回归那样写 成具体形式，不同的数据集、不同的属性都对应不同的规则，但总之这个规则就像一棵树，每个实例都能找到对应的那条从根节点到叶节点的路径，从而将实例分好类， 而一个决策树模型也正是要通过训练数据学习这个规则。

1.1.2 决策树的规则可以理解为if-then规则

可以将决策树看成是一个if-then规则的集合。由决策树的根节点到每一个叶节点的这条路径都对应着一条规则，内部节点就是对应着规则的条件，而最后叶节点就是符合这条规则的结论。决策树的路径是互斥且完备的，也就是说每条路径都不一样，且每个实例都能也只能被一条路径所覆盖。

1.1.3 决策树与条件概率分布

决策树还可以表示给定特征的条件下，类的条件概率分布。决策树将特征空间划分为互不相交的区域，每一条路径对应一个区域，在每一个区域都都有一个类的概率分布，而这个概率分布依托于特征X。对于给定的X，类Y的依概率取到某些类，这个条件概率可以表示为$P(Y|X)$，而这个区域的标签则是其中条件概率最大的那个类。(一个区域或者是一条路径对应的数据集可以不全是同一类的，有可能是因为一些噪声（相同的X不同的Y），也有可能是为了防止过拟合而不继续往下分了)。所以决策树模型可以理解为$P(Y|X)=DTree(X)$，其中的DTree就是决策树所代表的规则，相比上面的DTree少了一步强行将条件概率最大的类设置为叶的标签。

1.2 决策树的学习策略与算法

决策树的学习策略就是学习一个树规则所采用的依据，决策树的学习过程就是决策树的生成过程，在每个节点选择特征，开枝散叶，直到满足叶节点条件才停止这个节点的扩张。那么从这个学习过程我们能发现两个主要需要解决的问题：

1. 在每一个节点都需要考虑选择一个特征，依据该特征的取值进行分叉延伸。那么在每个节点，应该选择哪个特征比较好？这就是特征选择问题。
2. 那么一条路径一直延伸下去，什么时候才能停止？即如何判断一个节点是否可以划分为叶节点，结束一条路径。

如果知道了在每个节点该如何选择一个特征，也知道了如何才能将一个节点标记为叶节点，那么就自然而然能生成一个决策树。

直观上，我们应该选择什么样的特征来对数据集进行划分呢？我们的目的是依据X找到对应的类别Y。如果有一个特征具有很强的区分度，通过这一个特征的取值划分就能够将数据完美地划分为若干类别，每个特征对应一类，那么这个特征就是我们想要的，一个区分度很高的特征能够将数据集提纯，划分的几个子数据集纯度很高。

那么如何能够比较各个特征的区分度呢？一般比较的是这个特征对数据集划分后带来的纯度提升，如果划分后的数据集纯度提升越大，那么这个特征的区分度也就越大。那么问题变成如何衡量数据集的纯度呢？决策树用信息熵或者基尼系数来衡量数据集的纯度，下面会介绍两者。

那么如何判断一个节点是否为叶节点呢？ 一般有三个条件，满足其中之一就能将该节点归为叶节点，不再进行划分子集了，而是贴上标签。

• 当前节点包含的实例全为同一类，没必要再进行划分了。
• 到当前节点时，所有的特征都已经用完了，没有可用的特征来对当前节点包含的数据集进行划分了。
• 当前节点所有可用的特征划分子集后带来的纯度提升小于某个阈值，因为划分子集会提升树的深度，增加模型的复杂度与计算的需求，所以如果用一个特征进行划分后与划分前的纯度只提升了一点点，那么权衡之下就不进行划分了，直接归为叶节点

1.2.1 决策树的学习

给定一个训练集D ，决策树学习的目标就是根据D构建一个决策树模型，使它能对实例进行正确的分类。
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征将训练数据集进行分割。决策树学习算法包括特征选择，决策树的生成，决策树的剪枝这三个学习过程。决策树的学习算法通常有ID3、C4.5、CART。下面利用例子依次介绍这些学习过程。首先将数据集导入：

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
# %matplotlib notebook

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from collections import Counter
import math
from math import log
import pprint
1
2
3
4
5
6
7
8
9
10
11

def create_data():
    datasets = [['青年', '否', '否', '一般', '否'],
               ['青年', '否', '否', '好', '否'],
               ['青年', '是', '否', '好', '是'],
               ['青年', '是', '是', '一般', '是'],
               ['青年', '否', '否', '一般', '否'],
               ['中年', '否', '否', '一般', '否'],
               ['中年', '否', '否', '好', '否'],
               ['中年', '是', '是', '好', '是'],
               ['中年', '否', '是', '非常好', '是'],
               ['中年', '否', '是', '非常好', '是'],
               ['老年', '否', '是', '非常好', '是'],
               ['老年', '否', '是', '好', '是'],
               ['老年', '是', '否', '好', '是'],
               ['老年', '是', '否', '非常好', '是'],
               ['老年', '否', '否', '一般', '否'],
               ]
    labels = ['年龄', '有工作', '有自己的房子', '信贷情况', '类别']
    # 返回数据集和每个维度的名称
    return datasets, labels
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

datasets, labels = create_data()
datasets = np.array(datasets)
df = pd.DataFrame(datasets, columns=labels)
1
2
3

数据集如下：这是银行贷款是否通过的一个数据集，总共有4个特征，共两类——是（表示通过）和否（表示不通过）两类。要依据这个数据集利用学习算法构建一棵决策树

2.特征选择

2.1 特征选择问题

所谓特征选择就是在对数据集D进行划分时，有很多特征可以作为划分的依据，比如上面可以选择将数据集按年龄划分为3个子数据集，也可以按是否有工作划分为两个子数据集，那么应该选择哪一个特征呢？这就涉及到特征选择，旨选择那个最具有分类能力的特征。直觉上，如果一个特征，将数据集划分成几个子集，每个子集的大部分样本都属于某一类，使得这个子集下类的不确定性小，那么这个特征就明显有较强分类能力；相反，如果一个特征对数据集划分的几个子集，自己里的样本分类参差不齐，类还是有很大的不确定性，那么这个特征就没起到什么作用，无明显分类能力。

通过上面例子可以看到，如果选择年龄作为划分依据，将数据集划分为3个子集，每个子集里的类依然有点模糊，不确定主要是那一类，因此年龄分类能力不强。而"有自己的房子"这个特征，将数据划分为两个子集，“有自己的房子”=>“是” 对应的这个子数据集，都是属于“是”这一类，没有不确定性，而"有自己的房子"=>“否” 对应的这个子数据集，大部分都是属于“否”这一类，有较强的分类能力，数据集D利用这个特征来划分可以减少不确定性。

那么如何来量化特征的“分类能力呢”？通过刚刚的例子，可以利用对数据集不确定性的减少量来评判一个特征的分类能力，在信息论与概率统计中，利用熵(entropy)来表示随机变量的不确定性。

2.2 信息增益

2.2.1 熵(entropy)的定义

若X是一个取有限个值的离散随机变量，其概率分布为：
$$P(X=x_i)=p_i,i=1,2,...,n$$
则随机变量X的熵定义为：
$$H(X)=-\sum _{i=1}^n{p}_i\ast {\log }_2{p}_i$$
从公式可以看出，随机变量X的熵只依赖X的分布，而与X的取值无关。所以一般也将X的熵记为：
$$H(p)=-\sum _{i=1}^n{p}_i\ast {\log }_2{p}_i$$
熵越大，说明随机变量的取值越模糊，不确定性越大。比如二分类任务时，取正类与负类的概率一样，都是0.5，那么这时类的不确定性是最大的，取出来也完全没法确定是正还是负，熵这时最大。如果正类概率是1，负类概率是0，那么类就完全没有不确定性，取出来一定是正例，熵这时最小。而像上面的数据集，取“是”类的有9个，概率是9/15，取“否”类有6个，概率是6/15，那么这个数据集的熵就是:
$$H(D)=-9/15\ast {\log }_2(9/15)-6/15\ast {\log }_2(6/15)=0.971$$
下面是二分类时p从0取到1时熵值的变化图。

2.2.2 条件熵

条件熵是指随机变量X在知道了某个条件下的熵。比如上面数据集D的熵为H(D)=0.971,只考虑了D的类，而没考虑类对应的特征信息。如果已知每一个样本所对应的A特征的信息，利用A特征将D划分为一些子集，一般就可以减少不确定性。不妨先让A特征为“有自己的房子”，在已知每一类下是否有自己的房子，就可以根据这个特征将D划分，如果能完全将类分开，那么就不存在不确定性了。

条件熵的定义：
$$H(D|A)=\sum _{i=1}^n{p}_i\ast H(D|A=A_i)i=1,2,...,n$$
这里A是数据集D的某个特征，A取值有n个，$p_i$为A的第i个取值出现的频率，比如上面“有自己的房子”取值有两个——“是”和“否”，n=2，特征为“是”的有6个样本，频率就是6/15，“否”有9个样本，频率就是9/15。$H(D|A=A_i)$是当A取第i个值时的子数据集的熵，比如上面“有自己的房子” =>“是”，总共有6个样本，这6个样本的当成一个子集，它只有一个分类——“是”，所以这个子集的熵是0，再乘上它对应的权重6/15，就是这个子集贡献的不确定性。而另一个子集“有自己的房子” =>“否”正类有3个，负类有6个，熵是$H(D|A="否")=-6/9\ast {\log }_2(6/9)-3/9\ast {\log }_2(3/9)=0.918$，再乘上它的权重9/15，就是这个子集贡献的不确定性。

所以在已知特征A“有自己的房子”情况下，D的条件熵为：
$H(D|A)=6/15\ast H(D|A="是")+9/15\ast H(D|A="否")=6/15\ast 0+9/15\ast 0.918=0.551$
所以条件熵就是数据集D，在已知某个特征的条件下，将D分为若干个子集，把每个子集的熵加权平均之后就是D在已知A下的条件熵。

2.2.3 经验熵

当熵中的概率由数据估计(特别是最大似然估计)得到时，所对应的熵称为经验熵(empirical entropy)。什么叫由数据估计？比如有10个数据，一共有两个类别，A类和B类。其中有7个数据属于A类，则该A类的概率即为十分之七。其中有3个数据属于B类，则该B类的概率即为十分之三。浅显的解释就是，这概率是我们根据数据数出来的。经验就是指从训练数据中得到的信息。
虽然我们想要依据新数据的熵（期望熵）来进行特征选择，但是我们无法获取到新数据的信息，只能用训练数据的经验熵作为期望熵的估计值，通过最小化经验条件熵来进行特征选择

2.2.4 信息增益定义

上面已经介绍了熵与条件熵，熵就是数据集分类的不确定性，条件熵就是数据集在已知某个特征下的不确定性，如果在已知某个特征条件下，能使熵下降很多（或者说使不确定性下降很多），那么这个特征就对分类起到了很大作用，或者说这个特征的信息增益很大。决策树就是选择信息增益最大的特征，以这个特征进行子集划分。

信息增益： 特征A对数据集D的信息增益$g(D,A)$定义为数据集D的熵与给定A下的条件熵的差值（信息增益也就是不确定性减少）：
$$g(D,A)=H(D)-H(D|A)$$
如果A为“有自己的房子”，那么它对D的信息增益为$0.971-0.551=0.420$，信息增益非负，当一个特征对数据集$D$划分的每个子集$D_i$中的类别比例与$D$完全一样，则信息增益为0，说明这个特征划分的节点并没有提高类别的“纯度”。

2.2.5 信息增益比定义

为什么需要信息增益比？它比信息增益好在哪？
信息增益可能会带来一个不好的结果，如果选择唯一ID作为划分属性，那么会得到n个类别，每个类别都只包含一个样本，每个节点的纯度都是最高的，纯度提升也是最大的，带来的信息增益也是最高的，条件熵直接降为了0。但是这样的划分是没有意义的，因为我们训练模型是为了应用于新样本，如果模型这样划分显然没有泛化能力。
信息增益比是某个特征的信息增益除以这个特征本身的熵。特征的熵是什么，是这个特征取值不确定性的度量，也就是说，特征的取值越不确定，越分散，熵越大。特征的取值越集中，熵越小。假设有这样两个特征，一个熵很大，取值很不确定，一个熵很小，取值较为集中在某个值。但是两者提供的信息增益却是一样的，你会选择谁？显然选择取值不确定性小的那个，信息增益比可以理解为，某特征每单位不确定性带来的对数据集信息增益的提升。显然对于熵小的那个特征，每单位的不确定性能提供更多的信息增益。（也可以这样理解，极端情况下，每个特征取值概率都相等，那么熵为logn，那么取值越多的熵越大，信息增益比可以理解为每个特征的取值对于信息增益的贡献。
C4.5算法进行特征选择所用的就是信息增益比，但是使用信息增益比又会造成在特征选择时偏向那些取值较少的特征，于是一般先从候选属性中选择那些信息增益高于平均水平的属性，然后再从中选出信息增益比最高的那个特征进行子集划分。

2.2.6 基尼系数定义

数据集D的基尼系数定义为：
$Gini(D)=\sum _{k=1}^n\sum _{j\ne k}^n{p}_k{p}_j$
其中n为数据集D的类别数量。化简后得到：
$Gini(D)=1-\sum _{k=1}^n{p}_k^2$

基尼系数有什么含义呢？可以理解为从数据集D中，随机选取两个样本，它们不属于同一类的概率。两个样本属于同一类的概率为$\sum _{k=1}^n{p}_k^2$，所以，基尼系数和熵类似，也代表了数据集的”纯度“，基尼系数越大，说明选择的两个随机样本是同一类的给率越小，样本纯度越低。

信息增益时决策树在生成一颗树时如何选择特征的依据，当然还有其他依据，比如信息增益比(对应C4.5算法)，基尼系数(CART算法),而信息增益是ID3算法在生成树时使用的特征选择依据。下面我将介绍ID3算法的过程，以及代码实现。

3. ID3算法介绍及手动实现

ID3算法的核心是在决策树各个节点上使用信息增益准则选择特征，递归的构建决策树。具体是这样：首先，从根节点开始，对节点计算所有特征的信息增益，取其中信息增益最大的特征作为划分依据，根据这个特征的不同取值将数据集划分为若干子集从而建立子节点，再对子节点递归地使用以上方法，构建决策树，直到所有特征的信息增益都很小了（小于阈值），或者没有特征可以选择了就结束。

ID3算法：
输入：数据集D；特征集A，阈值$ϵ$
输出:决策树T

1. 判断若D中所有实例属于同一类$C_k$,则T为单节点树，并将$C_k$作为该叶节点的标签，返回T
2. 若$A=\varnothing$,则T为单节点树，并将D中实例出现频率最大的类作为该节点标签，返回T
3. 否则，按2.2.3 计算各特征对D的信息增益，选择信息增益最大的特征$A_g$
4. 如果$A_g<ϵ$,则T为单节点树，并将D中实例出现频率最大的类作为该节点标签，返回T
5. 否则，对$A_g$的每一可能值$a_i$，依$A_g=a_i$将D划分为若干非空子集$D_i$，将$D_i$中出现频率最大的类作为该节点标签，构建子节点，由节点及其子节点构成树T，返回T
6. 对第i个子节点，以$D_i$为训练集，$A-A_g$为特征集，递归地调用前5步，得到子树$T_i$,返回$T_i$

下面我将用代码，完整地演示一遍ID3算法的实现过程。

不过在实现决策树的过程时，有一个先行步骤很重要，那就是要先建立一个记录节点信息的工具，比如上面，给定数据集D，构建树的过程中，要不断地构建节点。一个节点可能是叶节点，并带有标签，也可能是内部节点，带着一个特征。

在生成树的过程中，要不断判断这个点的属性，比如是否是叶节点，如果是的话标签是什么？不是的话特征是什么，分为几个子集。所以为了记录这个信息，要首先定义一个“节点”类，来记录这些信息，而且在预测的时候也要不断地判断节点是否是叶节点，不是就得继续向下找子节点，所以记录下节点信息很重要。所以先构建一个节点类，来记录节点的信息。

class Node:  

    """
    每一个节点都有一些属性，比如是否是叶节点root，如果是(root=True),那么必须有label,
    且feature_name和feature为None
    """


    def __init__(self, root=True, label=None, feature_name=None, feature=None):
        self.root = root  # 叶节点否，True为叶节点
        self.label = label   # 标签是什么？只有叶节点才有标签
        self.feature_name = feature_name  # 若该node是非叶节点，那么这个节点是哪个特征？
        self.feature = feature  # # 若该node是非叶节点，那么这个节点特征index是几？
        self.tree = {}   #  若该node是非叶节点，则由该节点的特征不同取值划分了一些子集，作为该节点的子树
        self.result = {'label': self.label,'feature': self.feature,'tree': self.tree} 

    def __repr__(self):
        return '{}'.format(self.result)


    def add_node(self, val, node):  
        """
        当进行到步骤5时，要依据当前节点构建一些子节点时，就需要用到增加节点的方法
        val是当前节点的特征，node是子节点
        """
        self.tree[val] = node


    def predict(self, features):
        # 如果root为True，即为叶节点，必有label，直接返回label。
        if self.root is True:
            return self.label
        # 如果当前不是叶节点，则必有tree(分叉)，
        # self.tree[features[self.feature]]是转到了下一个属于x的node，再次判断这个节点是否是root，
        # 不是的话再转下一个，直到找到叶节点。
        return self.tree[features[self.feature]].predict(features) # 这里也用到了函数递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

这样就构建好了一个记录节点信息的Node类，下面开始用ID3算法生成决策树：

class DTree:


    def __init__(self, epsilon=0.1):
        # epsilon是阈值，默认为0.1
        self.epsilon = epsilon
        self._tree = {}


    # 计算熵
    @staticmethod
    def entropy(data):
        c = [ ]
        data = np.array(data)  # 因为开始还是列表，转成数组好运算
        a = np.array(data[:,-1]) # 取出类序列
        for i in range(len(np.unique(a))):
            c.append(sum(a == np.unique(a)[i]))
        c = np.array(c) # 每一类出现的频数组成的数组
        p = c/sum(c)  # 每一类出现的频率组成的数组
        logp = np.log2(p)
        ent = sum(-p*logp)
        return ent


    # 计算条件熵
    def con_entropy(self,data,axis=0):
        # axis是要计算的特征对应的index，年龄是0，有工作是1...
        feature_sets = {} # 构建一个字典，key是axis=0对应特征的各个取值，value是各个取值下的数据子集
        data_length = len(data) # 获取到样本数量
        for i in range(data_length):
            feature = data[i][axis] # 获取到当前遍历样本的特征取值
            if feature not in feature_sets:
                feature_sets[feature] = [ ]
            feature_sets[feature].append(data[i])
        con_ent = sum([(len(p) / data_length) * self.entropy(p) for p in feature_sets.values()])
        return con_ent


    # 计算信息增益
    @staticmethod
    def info_gain(ent, con_ent):
        return ent - con_ent


    def info_gain_train(self, data):
        count = len(data[0]) - 1  # 特征数量
        ent = self.entropy(data)
        best_feature = []  # 元素为双值元祖，记录每个特征的index以及对应的信息增益
        for c in range(count):
            c_info_gain = self.info_gain(ent, self.con_entropy(data, axis=c))
            best_feature.append((c, c_info_gain))
        best_ = max(best_feature, key=lambda x: x[-1])  # 返回信息增益最大的特征index以及其信息增益
        return best_


	# ID3算法生成树
    def train(self, train_data):
        """
        input:数据集train_data(DataFrame格式)，特征集A，阈值eta
        output:决策树T
        """
        x_trian, y_train, features = train_data.iloc[:, :-1], train_data.iloc[:,-1], train_data.columns[:-1]
        
        
        # 1,若D中实例属于同一类Ck，则T为单节点树，并将类Ck作为结点的类标记，返回T
        if len(y_train.value_counts()) == 1:
            return Node(root=True, label=y_train.iloc[0])  
        
        # 2, 若A为空，则T为单节点树，将D中实例树最大的类Ck作为该节点的类标记，返回T
        if len(features) == 0:
            return Node(root=True,label=y_train.value_counts().sort_values(ascending=False).index[0])
        
         # 3,计算最大信息增益 同5.1,Ag为信息增益最大的特征
        max_feature, max_info_gain = self.info_gain_train(np.array(train_data))
        max_feature_name = features[max_feature]  # 第几个
        
         # 4,Ag的信息增益小于阈值eta,则置T为单节点树，并将D中是实例数最大的类Ck作为该节点的类标记，返回T
        if max_info_gain < self.epsilon:
            return Node(root=True, label=y_train.value_counts().sort_values(ascending=False).index[0])
        
        # 5,否则，构建Ag子集，说明肯定要分叉了，这个node对应的特征有划分价值，下面生成一棵子树
        node_tree = Node(root=False, feature_name=max_feature_name, feature=max_feature)
        feature_list = train_data[max_feature_name].value_counts().index
        for f in feature_list:
            sub_train_df = train_data.loc[train_data[max_feature_name] ==f].drop([max_feature_name], axis=1)
            # 同时划分了子集以及把这个划分的特征从df里删除
            # 注意，6在5的循环里
        # 6, 递归生成树
            sub_tree = self.train(sub_train_df)  # 递归 ，这个函数的内部再次调用这个函数，
            # 可能是一个叶节点，也可能不是
            node_tree.add_node(f, sub_tree)  # 这个node下，
            # 每一个特征值f（如这个node特征是年龄。特征值'青年'下 又对应着一个node，可能是叶节点，
            # 也可能继续用其他特征划分
        return node_tree


    def fit(self, train_data):  # 返回一棵用train_data训练好的决策树
        self._tree = self.train(train_data)
        return self._tree

    def predict(self, X_test):
        return self._tree.predict(X_test)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

datasets, labels = create_data()
df = pd.DataFrame(datasets, columns=labels)
dt = DTree(epsilon=0.1)  # 创建一个决策树对象
tree = dt.fit(df)   # 用数据集去训练出一棵决策树，返回训练好的决策树
print(tree) 
tree.predict(['老年', '否', '否', '一般'])  #  输出"否"
1
2
3
4
5
6

4. 决策树的剪枝（只考虑后剪枝）

决策树的生成是直到不能继续下去才停止，这样产生的树往往对训练数据的分类很准确，但是对未知的测试数据分类却没有那么准确，即会出现过拟合的现象。出现过拟合现象的原因是决策树在生成的过程中，只考虑如何才能提高对训练数据分类的准确性，从而会构建出过于复杂的决策树。所以像许多模型一样，为了降低过拟合，不仅仅要考虑模型本身的性能，也要考虑模型的复杂度，对复杂度施加惩罚，以此来简化模型。决策树降低过拟合的方法称为决策树的剪枝，这里考虑的是更常用的后剪枝，即对已经生成的决策树再进行剪枝。

那么一个枝条什么时候才要剪掉呢？ 决策树剪枝的时候考虑的是整颗树对数据集的分类能力以及整颗树的叶节点个数。一颗决策树将数据集分为若干子集，每条路径有一个叶节点，对应着一个贴着标签的子集。一个树的分类能力可以用所有子集的熵的加权来表示。树的分类能力只是一方面，为了降低过拟合，还需要考虑树的复杂度，一颗树的路径越少，模型就越简单。所以一棵树的复杂度可以用叶节点的个数$|T|$来表示。决策树希望找到一个对训练集具有较好的分类能力，同时树的复杂度比较低的模型。

4.1 决策树剪枝的损失函数

我们知道决策树想要找一个什么样的模型，即分类能力强且简单。分类能力表示为C(T)，是由整棵决策树分成的所有子集熵的加权平均得到。我们知道叶节点的个数就是整棵树分成的子集个数，所以分类能力可以表示为:
$$C(T)=\sum _{i=1}^{|T|}{N}_t{H}_t(T)$$
其中$H_t(T)$为叶节点t对应的经验熵，$H_t(T)=-\sum _{k=1}^K{p}_{tk}log(p_{tk})$，$p_{tk}$为叶节点t对应数据集中类别为k的频率。$N_t$为叶节点t所包含的样本数量。

决策树的复杂度可以用叶节点个数$|T|$表示，那么为了权衡树的分类能力与复杂度，会在$|T|$前加一个系数$\alpha$，$\alpha$越大表示模型越在意复杂度，越希望得到简单的模型，反之越在意分类能力,当$\alpha =0$时，模型不剪枝，与先前生成的模型一致。

决策树剪枝时候的损失函数为:
$$C_{\alpha }(T)=\sum _{i=1}^{|T|}{N}_t{H}_t(T)+\alpha |T|=H_t(T)+\alpha |T|$$

对比剪枝前后的树的$C_{\alpha }(T)$，决定要不要剪枝。若剪完枝的树的$C_{\alpha }(T)$比剪之前的小，说明要剪枝，反之亦然。

决策树的生成只考虑局部最优，也就是说只考虑在当前节点的信息增益，而不会考虑整体上的效果，或者说只考虑这个点的经验熵H(D)以及这个点的条件熵H(D|A)，如果有改进超过阈值，就会继续生成枝条。

而决策树的剪枝（后剪枝）则考虑全局最优，比较的是所有叶节点的熵之和以及复杂度，剪与不剪都是从整棵树的角度出发的，而上面生成树时，生与不生都是从当前节点出发的。

5. sklearn.tree.DecisionTreeClassifier参数详解

参考官方文档

• criterion：{“gini”, “entropy”}, default=”gini”。特征选择标准，可选参数，默认是gini，也可以设置为entropy。ID3算法使用的是entropy，CART算法使用的则是gini。

• splitter ：{“best”, “random”}, default=”best”。特征划分点选择标准，可选参数，默认是best，可以设置为random。criterion可以理解为什么样的特征才是最优的，而这个参数可以理解为最优的特征从哪里选出来？best表示从全局特征中选，即遍历所有特征的基尼系数，从中选择best的。但是当一个数据集的特征数量非常大或者样本数量非常大时，需要计算所有特征的基尼系数很耗时，这时不遍历所有的特征了，而是随机random取一部分特征，从中选出最好的那个。

• min_samples_split：int or float, default=2。内部节点再划分所需最小样本数，可选参数，默认是2。当取整数时，比如当取2时，这个节点代表的数据集必须>=2时才可能继续往下分；如果min_samples_split为浮点数，那么min_samples_split就是一个百分比，表示只有节点代表的数据集必须>=这个百分比时才可能继续往下分，模型会计算ceil(min_samples_split * n_samples)，作为是否划分的依据。

• max_depth ：int，default=None。决策树最大深度，可选参数，默认是None。这个参数是这是树的层数的。因为有的数据集特征数量特别多，成千上万，那么一条路径可能用上特别多的特征。如果用了1000个特征，那么这条路径深度为1001，可能太"深"了，所以要限制，比如最大深度为100，一个可以减少计算量，一个也能降低过拟合。但是如果特征数量很少直接就不管了，默认为None就行。

• min_samples_leaf ：int or float, default=1。叶子节点最少样本数，可选参数，默认是1。和参数min_samples_split类似，min_samples_split是考虑当前要划分的节点最少要有多少个样本，而min_samples_leaf是当前节点划分后的子节点最少要有多少个样本。如果划分后的子集样本数太少，小于这个阈值，那么当前节点就不进行划分，或者将划分后的子集剪枝。如果设置为1，哪怕这个类别只有1个样本，决策树也会构建出来。这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝。叶结点需要最少的样本数，也就是最后到叶结点，需要多少个样本才能算一个叶结点。如果设置为1，哪怕这个子集只有1个样本，决策树也会构建出来。如果min_samples_leaf是整数，那么min_samples_leaf作为最小的样本数。如果是浮点数，那么min_samples_leaf就是一个百分比，同上。如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值。

• min_weight_fraction_leaf ：float, default=0.0。

• max_features： int, float or {“auto”, “sqrt”, “log2”},default=None。划分时考虑的最大特征数，可选参数，默认是None。寻找最佳切分时考虑的最大特征数(n_features为总共的特征数)，有如下6种情况：

  • 如果max_features设为None，那么max_features = n_features，也就是所有特征都用；
  • 如果max_features是整型的数，则考虑max_features个特征；
  • 如果max_features是浮点型的数，则考虑int(max_features * n_features)个特征；
  • 如果max_features设为auto，那么max_features = sqrt(n_features)；
  • 如果max_features设为sqrt，那么max_featrues = sqrt(n_features)，跟auto一样；
  • 如果max_features设为log2，那么max_features = log2(n_features)；
    这个参数是考虑特征太多时，取部分特征来控制划分时考虑的最大特征数，以控制决策树的生成时间。

• random_state：int, RandomState instance or None, default=None。可选参数，默认是None。随机数种子，用来在每个划分时随机化特征的顺序。

• max_leaf_nodes ：int, default=None。最大叶子节点数，可选参数，默认是None。通过限制最大叶子节点数，可以防止过拟合。如果加了限制，算法会建立在最大叶子节点数内最优的决策树。如果特征不多，可以不考虑这个值，但是如果特征分成多的话，可以加以限制，具体的值可以通过交叉验证得到。

• min_impurity_split（已弃用） ：float, default=0。这个值限制了决策树的增长，如果某节点的不纯度(基尼系数，信息增益，均方差，绝对差)小于这个阈值，则该节点不再生成子节点。即为叶子节点 。最新版本已经弃用，用min_impurity_decrease替代该参数。

• min_impurity_decrease ：float, default=0.0。A node will be split if this split induces a decrease of the impurity greater than or equal to this value.一个节点如果分割之后，带来数据集的不纯度的下降不小于这个值，那么就能继续分割，反之就不分割了，设置为叶节点。这个不纯度在分类中可以是熵或者基尼系数，回归时可以是均方误差，平均绝对误差。

• class_weight ： dict, list of dict or “balanced”, default=None。类别权重，可选参数，默认是None，也可以字典、字典列表、balanced。指定样本各类别的的权重，主要是为了防止训练集某些类别的样本过多，导致训练的决策树过于偏向这些类别。类别的权重可以通过{class_label：weight}这样的格式给出，这里可以自己指定各个样本的权重，或者用balanced，如果使用balanced，则算法会自己计算权重，样本量少的类别所对应的样本权重会高。当然，如果你的样本类别分布没有明显的偏倚，则可以不管这个参数，选择默认的None。

• ccp_alpha ：non-negative float, default=0.0。ccp为Cost-Complexity Pruning，剪枝时作用于复杂度|T|的系数，即$\alpha$。

参考：李航博士《统计学习方法》第二版
谢谢大家阅读，大家有什么问题欢迎留言，沟通，请多多指教。