机器学习-5-决策树

Posted on | Post modified: | In
Words count in article: 6.1k

前言

决策树是一种基本的分类与回归方法。本文主要讨论用于分类的决策树。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程，它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据，利用决策树模型进行分类。

决策树学习包括三个步骤：特征选择、决策树的生成和决策树的修剪。

决策树模型与学习

决策树模型

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成，结点有两种类型：内部结点和叶结点。内部结点表示一个特征或属性，叶结点表示一个类。

用决策树分类，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至到达叶结点。最后将实例分到叶结点的类中。

决策树与if-then规则

可以将决策树看成一个if-then规则的集合。将决策树转换成if-then规则的过程是这样的：由决策树的根结点到叶结点的每一条路径构建一条规则；路径上内部结点的特征对应着规则的条件，而叶结点对应着规则的结论。决策树的路径是互斥并且完备的。即每一个实例都被一条路径或一条规则所覆盖，并且只被一条路径或一条规则所覆盖。

决策树与条件概率分布

决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分上。将特征空间划分为互不相交的单元或区域，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。

决策树学习

决策树学习，假设给定训练数据集$D=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}$，其中$x_{i}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \cdots, x_{i}^{(n)}\right)^{\mathrm{T}}$为输入实例，$n$为特征个数，$y_i \in \{1,2,\cdots,K\}$为类标记，$i=1,2,\cdots,N$，$N$为样本容量。学习的目标是根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。

决策树学习的本质是从给定的训练数据集中依据属性或特征归纳出一组分类规则。与给定的训练数据集相符合的分类规则可能有多个，决策树模型就是需要从多个符合的分类规则中找到损失最小的，泛化能力最好的一组分类规则。

决策树常用的损失函数是正则化的极大似然函数，决策树的学习策略是以损失函数为目标函数的最小化。由于所有可能的决策树组成的解空间较大，从中找到最优的决策树是NP完全问题，因此一般多采用启发式算法来近似求解。

决策树学习的算法通常是一个递归的选择最优特征的过程。从可选的特征集合中选出最优的特征（即依据该特征能最有效的将训练数据集分类），按照这一特征将数据集分割成子集，该特征作为这些子集的根节点。如果这些子集已经基本可以正确分类，那么构建叶节点，并将这些子集分到所对应的的叶节点中去。如果还有子集不能被正确分类，那么对这些子集选取新的最优特征，继续对其进行分割，直至所有训练数据都被正确分类。至此就构建出来一颗决策树。

通过上述步骤构建的决策树可以对训练数据集进行很好的分类，但是并不一定有很好的泛化能力，即可能发生过拟合现象。为了增强其泛化能力，我们需要对构建好的决策树进行自底向上的剪枝，即将树变得更简单一点。通过去掉决策树中过于细分的叶节点，使其回退到父节点甚至更高节点，用父节点或更高节点作为新的叶节点。

特征选择

特征选择在于选取对训练数据具有良好分类能力的特征，这样可以提高决策树的学习效率。通常特征选择的准则是信息增益或信息增益比。

信息增益

熵：表示随机变量不确定性的度量。设$X$是一个取有限个值的离散随机变量，其概率分布为

则随机变量$X$的熵定义为

熵越大，随机变量的不确定性就越大。$0\le H(X)\le logn$。

条件熵：条件熵$H(Y|X)$表示在已知随机变量$X$的条件下随机变量$Y$的不确定性。定义为$X$给定条件下$Y$的条件概率分布的熵对$X$的数学期望

其中$p_i=P(X=x_i),\quad i = 1,2,\cdots,n$。

当熵和条件熵重的概率由数据估计（极大似然估计） 得到时，所对应的熵与条件熵分别称为经验熵和经验条件熵。

信息增益：表示得知特征$X$的信息而使得类$Y$的信息的不确定性减少的程度。

特征$A$对训练数据集$D$的信息增益$g(D,A)$，定义为集合$D$的经验熵$H(D)$与给定条件下$D$的经验条件熵$H(D|A)$之差，即

信息增益等价于类与特征的互信息。

信息增益大的特征具有更强的分类能力。根据信息增益准则进行特征选择：对训练数据集（或子集），计算其每个特征的信息增益，选择信息增益最大的特征。

信息增益比

以信息增益作为选择特征的准则，存在偏向于选择取值较多的特征的问题。即当一个特征可能的取值较多时，其计算出来的信息增益可能会较高，但是并不一定就一定是一个更有效的分类特征。采用信息增益比可以对这一问题进行校正，这是特征选择的另一准则。

特征$A$对训练数据集$D$的信息增益比$g_R(D,A)$定义为其信息增益$g(D,A)$与训练数据集$D$的经验熵$H(D)$之比：

其中$H_{A}(D)=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \log _{2} \frac{\left|D_{i}\right|}{|D|}$，$n$是特征$A$取值的个数。

决策树的生成

$ID3$算法

在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。

算法：$ID3$算法

输入：训练数据集$D$，特征集$A$，阈值$\epsilon$；

输出：决策树$T$。

（1）若$D$中所有实例属于同一类$C_k$，则$T$为单结点树，并将类$C_k$作为该结点的类标记，返回$T$；

（2）若$A=\emptyset$，则$T$为单结点树，并将$D$中实例数最大的类$C_k$作为该结点的类标记，返回$T$；

（3）否则，计算$A$中各特征对$D$的信息增益，选择信息增益最大的特征$A_g$；

（4）如果$A_g$的信息增益小于阈值$\epsilon$，则置$T$为单结点树，并将$D$中实例数最大的类$C_k$作为该结点的类标记，返回$T$；

（5）否则，对$A_g$的每一个可能值$a_i$，依$A_g=a_i$将$D$分割为若干非空子集$D_i$，将$D_i$中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树$T$，返回$T$；

（6）对第$i$个子结点，以$D_i$为训练集，以$A-\{A_g\}$为特征集，递归地调用步（1）~（5），得到子树$T_i$，返回$T_i$。

$C4.5$算法

$C4.5$算法对$ID3$算法进行了改进，使用信息增益比来选择特征。

算法：$C4.5$算法

输入：训练数据集$D$，特征集$A$，阈值$\epsilon$；

输出：决策树$T$。

（1）若$D$中所有实例属于同一类$C_k$，则$T$为单结点树，并将类$C_k$作为该结点的类标记，返回$T$；

（2）若$A=\emptyset$，则$T$为单结点树，并将$D$中实例数最大的类$C_k$作为该结点的类标记，返回$T$；

（3）否则，计算$A$中各特征对$D$的信息增益比，选择信息增益比最大的特征$A_g$；

（4）如果$A_g$的信息增益小于阈值$\epsilon$，则置$T$为单结点树，并将$D$中实例数最大的类$C_k$作为该结点的类标记，返回$T$；

（5）否则，对$A_g$的每一个可能值$a_i$，依$A_g=a_i$将$D$分割为若干非空子集$D_i$，将$D_i$中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树$T$，返回$T$；

（6）对第$i$个子结点，以$D_i$为训练集，以$A-\{A_g\}$为特征集，递归地调用步（1）~（5），得到子树$T_i$，返回$T_i$。

决策树的剪枝

通过前边决策树生成算法的步骤生成的决策树可能对训练数据有很好的拟合效果，但是由于分支过细，可能会包含太多训练集中的信息，导致泛化能力很差，对未知的数据没有准确的分类。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化。

剪枝是从已生成的树上裁掉一些子树或叶结点，并将其根结点或父节点作为新的叶结点，从而简化分类树模型。通过极小化决策树整体的损失函数或代价函数来实现。

设树$T$的叶结点个数为$|T|$，$t$是树$T$的叶结点，该叶结点有$N_t$个样本点，其中$k$类的样本点有$N_{tk}$个，则损失函数可以定义为：

其中右边第一项为经验熵表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，$T$表示模型复杂度，参数$\alpha \ge0$控制两者之间的影响。较大的$\alpha$促使选择较简单的模型，较小的$\alpha$促使选择较复杂的模型。

决策树的生成只考虑通过提高信息增益（或信息增益比）对训练数据进行更好的拟合，而决策树剪枝通过优化损失函数还考虑了减小模型复杂度。决策树生成学习局部的模型，而决策树剪枝学习整体的模型。

算法：树的剪枝算法

输入：生成算法产生的整个树$T$，参数$\alpha$；

输出：修剪后的子树$T_\alpha$。

（1）计算每个结点的经验熵；

（2）递归地从树的叶结点向上回缩；设一组叶结点回缩到其父结点之前与之后的整体树分别为$T_B$与$T_A$，其对应的损失函数值分别为$C_\alpha(T_B)$与$C_\alpha(T_A)$，如果 $C_\alpha(T_A) \le C_\alpha(T_B)$则进行剪枝，即将父结点变为新的叶结点；

（3）返回（2），直至不能继续为止，得到损失函数最小的子树$T_\alpha$。

CART算法

CART可以用于分类也可以用于回归。CART在给定输入随机变量$X$条件下输出随机变量$Y$的条件概率分布的学习方法。它假设决策时是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支，这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。

CART算法由两步组成：

（1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；

（2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

CART生成

决策树的生成就是递归地构建二叉决策树的过程，对回归树用平方误差最小化准确，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树。

回归树的生成

算法：最小二乘回归树生成算法

输入：训练数据集$D$；

输出：回归树$f(x)$。

在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树。

（1）选择最优切分变量$j$与切分点$s$，求解

遍历变量$j$，对固定的切分变量$j$扫描切分点$s$，选择使上式达到最小值的对$(j,s)$。

（2）用选定的对$(j,s)$划分区域并决定相应的输出值：

（3）继续对两个子区域调用步骤（1），（2），直至满足停止条件。

（4）将输入空间划分为$M$个区域$R_1,R_2,\cdots,R_M$，生成决策树：

分类树的生成

分类树用基尼指数最小选择最优特征，同时决定该特征的最优二值切分点。

基尼指数：分类问题中，假设有$K$个类，样本点属于第$k$类的概率为$p_k$，则概率分布的基尼指数定义为：

对于给定的样本集合$D$，其基尼指数为：

这里$C_k$是$D$中属于第$k$类的样本子集，$K$是类的个数。

如果样本集合$D$根据特征$A$是否取某一可能值$a$被分割成$D_1$和$D_2$两部分，则在特征$A$的条件下，集合$D$的基尼指数为：

基尼指数越大，样本集合的不确定性越大。

算法：CART生成算法

输入：训练数据集$D$，停止计算的条件；

输出：CART决策树。

根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树：

（1）设结点的训练数据集为$D$，计算现有特征对该数据集的基尼指数。对每一个特征，对其每一个可能取值$a$，根据样本点对$A$是否等于$a$将$D$分割成$D_1$和$D_2$两部分，利用上式计算$A=a$时的基尼指数。

（2）在所有可能的特征$A$以及它们所有可能的切分点$a$中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。

（3）对两个子结点递归地调用（1）（2），直至满足停止条件。

（4）生成CART决策树。

算法停止的条件是结点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值（样本基本属于同一类），或者没有更多特征。

CART的剪枝

CART剪枝主要由两步构成：

（1）首先从生成算法产生的决策树$T_0$底端开始不断剪枝，直到$T_0$的根结点，形成一个子树序列$\{T_0,T_1,\cdots,T_n\}$；

（2）通过交叉验证的方式在独立的验证数据集上对子树序列进行测试，从中选择最优子树。

算法：CART剪枝算法

输入：CART算法生成的决策树$T_0$；

输出：最优决策树$T_\alpha$。

（1）设$k=0,~T=T_0$；

（2）设$\alpha = +\infty$；

（3）自下而上地对各内部结点$t$计算$C(T_t)$，$|T_t|$以及

其中$T_t$表示以$t$为根结点的子树，$C(T_t)$是对训练数据的预测误差，$|T_t|$是$T_t$的叶结点个数，$g(t)$表示剪枝后整体损失函数减少的程度。

（4）自上而下地访问内部结点$t$，如果有$g(t)=\alpha$，进行剪枝，并对叶结点$t$以多数表决法决定其类，得到树$T$。

（5）设$k=k+1$，$\alpha_k=\alpha$，$T_k=T$。

（6）如果$T$不是由根结点单独构成的树，则回到步骤（4）。

（7）采用交叉验证法在子树序列$T_0,T_1,\cdots,T_n$中选取最优子树$T_\alpha$。

例5.2 根据信息增益选择最优特征

例5.3 ID3算法生成决策树

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
import numpy as np
import pandas as pd

## 例5.2 根据信息增益选择最优特征
def create_date():
    datasets = [['青年', '否', '否', '一般', '否'],
                ['青年', '否', '否', '好', '否'],
                ['青年', '是', '否', '好', '是'],
                ['青年', '是', '是', '一般', '是'],
                ['青年', '否', '否', '一般', '否'],
                ['中年', '否', '否', '一般', '否'],
                ['中年', '否', '否', '好', '否'],
                ['中年', '是', '是', '好', '是'],
                ['中年', '否', '是', '非常好', '是'],
                ['中年', '否', '是', '非常好', '是'],
                ['老年', '否', '是', '非常好', '是'],
                ['老年', '否', '是', '好', '是'],
                ['老年', '是', '否', '好', '是'],
                ['老年', '是', '否', '非常好', '是'],
                ['老年', '否', '否', '一般', '否'],
                ]
    labels = [u'年龄', u'有工作', u'有自己的房子', u'信贷情况', u'类别']
    return datasets, labels

# 熵的计算
def calc_ent(datasets):
    data_length = len(datasets)
    label_count = {}
    for i in range(data_length):
        label = datasets[i][-1]
        if label not in label_count:
            label_count[label] = 0
        label_count[label] += 1
    ent = -sum([(p/data_length) * np.log2(p/data_length) for p in label_count.values()])
    return ent

# 经验条件熵
def cond_ent(datasets, axis=0):
    # axis代表选定的特征列
    data_length = len(datasets)
    feature_sets = {}
    for i in range(data_length):
        feature = datasets[i][axis]
        if feature not in feature_sets:
            feature_sets[feature] = []
        feature_sets[feature].append(datasets[i])
    cond_ent = sum(len(p) / data_length * calc_ent(p) for p in feature_sets.values())
    return cond_ent

# 信息增益
def info_gain(ent, cond_ent):
    return ent - cond_ent

# 获取最优特征
def info_gain_train(datasets):
    count = len(datasets[0]) - 1
    ent = calc_ent(datasets)
    best_feature = []
    for c in range(count):
        c_info_gain = info_gain(ent, cond_ent(datasets, axis=c))
        best_feature.append((c, c_info_gain))
        print("特征({}) - info_gain - {:.3f}".format(labels[c], c_info_gain))
    best_ = max(best_feature, key=lambda x:x[-1])
    return '特征({})的信息增益最大，选择为根节点特征'.format(labels[best_[0]])

## 例5.3 ID3算法生成决策树
# 定义结点类 二叉树
class Node:
    def __init__(self, root=True, label=None, feature_name=None, feature=None):
        self.root = root
        self.label = label
        self.feature_name = feature_name
        self.feature = feature
        self.tree = {}
        self.result = {
            'label:': self.label,
            'feature': self.feature,
            'tree': self.tree
        }

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

    def add_node(self, val, node):
        self.tree[val] = node

    def predict(self, features):
        if self.root is True:
            return self.label
        return self.tree[features[self.feature]].predict(features)

class DTree:
    def __init__(self, epsilon=0.1):
        self.epsilon = epsilon
        self._tree = {}

    # 熵
    @staticmethod
    def calc_ent(datasets):
        data_length = len(datasets)
        label_count = {}
        for i in range(data_length):
            label = datasets[i][-1]
            if label not in label_count:
                label_count[label] = 0
            label_count[label] += 1
        ent = -sum([(p / data_length) * np.log2(p / data_length) for p in label_count.values()])
        return ent
    # 经验条件熵
    def cond_ent(self, datasets, axis=0):
        # axis代表选定的特征列
        data_length = len(datasets)
        feature_sets = {}
        for i in range(data_length):
            feature = datasets[i][axis]
            if feature not in feature_sets:
                feature_sets[feature] = []
            feature_sets[feature].append(datasets[i])
        cond_ent = sum(len(p) / data_length * calc_ent(p) for p in feature_sets.values())
        return cond_ent

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

    # 获取最优特征
    def info_gain_train(self, datasets):
        count = len(datasets[0]) - 1
        ent = calc_ent(datasets)
        best_feature = []
        for c in range(count):
            c_info_gain = info_gain(ent, cond_ent(datasets, axis=c))
            best_feature.append((c, c_info_gain))
            print("特征({}) - info_gain - {:.3f}".format(labels[c], c_info_gain))
        best_ = max(best_feature, key=lambda x: x[-1])
        print('特征({})的信息增益最大，选择为节点特征'.format(labels[best_[0]]))
        return best_

    def train(self, train_data):
        _, 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,计算A中各特征对D的信息增益，选择最大信息增益的特征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_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)
            # 6 递归生成树
            sub_tree = self.train(sub_train_df)
            node_tree.add_node(f, sub_tree)

        return node_tree

    def fit(self, train_data):
        self._tree = self.train(train_data)
        return self._tree

    def predict(self, X_test):
        return self._tree.predict(X_test)

if __name__ == '__main__':
    # 例5.2
    print("\n例题5.2==")
    datasets, labels = create_date()
    train_data = pd.DataFrame(datasets, columns=labels)
    print(info_gain_train(np.array(datasets)))

    # 例5.3
    print("\n例题5.3==")
    datasets, labels = create_date()
    data_df = pd.DataFrame(datasets, columns=labels)
    dt = DTree()
    tree = dt.fit(data_df)
    print(tree)
    res = dt.predict(['老年', '否', '否', '一般'])
    print(res)

输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
例题5.2==
特征(年龄) - info_gain - 0.083
特征(有工作) - info_gain - 0.324
特征(有自己的房子) - info_gain - 0.420
特征(信贷情况) - info_gain - 0.363
特征(有自己的房子)的信息增益最大，选择为根节点特征

例题5.3==
特征(年龄) - info_gain - 0.083
特征(有工作) - info_gain - 0.324
特征(有自己的房子) - info_gain - 0.420
特征(信贷情况) - info_gain - 0.363
特征(有自己的房子)的信息增益最大，选择为节点特征
特征(年龄) - info_gain - 0.252
特征(有工作) - info_gain - 0.918
特征(有自己的房子) - info_gain - 0.474
特征(有工作)的信息增益最大，选择为节点特征
{'label:': None, 'feature': 2, 'tree': {'否': {'label:': None, 'feature': 1, 'tree': {'否': {'label:': '否', 'feature': None, 'tree': {}}, '是': {'label:': '是', 'feature': None, 'tree': {}}}}, '是': {'label:': '是', 'feature': None, 'tree': {}}}}
否

sklearn实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import numpy as np
import pandas as pd

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier

def create_data():
    iris = load_iris()
    df = pd.DataFrame(iris.data, columns=iris.feature_names)
    df['label'] = iris.target
    df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']
    data = np.array(df.iloc[:100, [0,1,-1]])
    return data[:,:2], data[:,-1]

if __name__ == '__main__':
    X,y = create_data()
    X_train, X_test, y_train, y_test = train_test_split(X, y,test_size=0.3)
    clf = DecisionTreeClassifier()
    print(clf.fit(X_train, y_train))
    print(clf.score(X_test, y_test))

参考文献
统计学习方法. 李航
https://github.com/fengdu78/lihang-code/tree/master/%E7%AC%AC05%E7%AB%A0%20%E5%86%B3%E7%AD%96%E6%A0%91

Donate comment here
------------The End------------
0%