机器学习笔记15——决策树(DT)、ID3算法、C4.5算法原理以及python实现案例_采用决策树分类模型(id3算法、c4.5算法),完成至少两个数据集(其中一个是西瓜集)的

1、概述

\quad \quad 作为机器学习中的一大类模型，树模型一直以来都颇受学界和业界的重视。目前无论是各大比赛各种大杀器的XGBoost、lightgbm、还是像随机森林、AdaBoost等典型集成学习模型，都是以决策树模型为基础的。传统的经典决策树算法包括ID3算法、C4.5算法以及GBDT的基分类器CART算法。

\quad \quad 三大经典决策树算法最主要的区别是其特征选择的准则不同。ID3算法选择特征的依据是信息增益、C4.5是信息增益比，而CART则是基尼指数。作为一种基础的分类和回归方法，决策树可以有以下两种理解方法：可以认为是if-then的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。

2、决策树模型

\quad \quad 定义： 分类决策树模型是一种描述对实例进行分类的树形结构。

\quad \quad 决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点，其中内部结点表示一个特征或属性，叶结点表示一个类。 一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点。叶结点对应于决策结果，其他每个结点则对应于一个属性测试。每个结点包含的样本集合根据属性测试的结果被划分到子结点中，根结点包含样本全集，从根结点到每个叶结点的路径对应了一个判定测试序列。在下图中，圆和方框分别表示内部结点和叶结点。决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。

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

\quad \quad 下图为决策树示意图，圆点——内部节点，方框——叶节点

\quad \quad 上节介绍的k-近邻算法可以完成很多分类任务，但是其最大的缺点是无法给出数据的内在含义，决策树的优势在于数据形式非常容易理解。

3、决策树学习

\quad \quad 假设给定训练数据集：

D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯ , ( x N , y N ) } D=\{ (x_1 ,y_1 ),(x_2,y_2 ),⋯,(x_N,y_N) \} D={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}
其中，$x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)}{)}^T$ 为输入实例，即特征向量，n为特征个数， y i ∈ { 1 , 2 , . . . , K } y_i \in \{ 1, 2, ..., K\} yi​∈{1,2,...,K} 为类标,$i=1,2,...,N;N为样本容量$。

• 决策树学习的目标：根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。

• 决策树学习的本质：从训练集中归纳出一组分类规则，或者说是由训练数据集估计条件概率模型。

• 决策树学习的损失函数：正则化的极大似然函数

• 决策树学习的策略：最小化损失函数

• 决策树学习的目标：在损失函数的意义下，选择最优决策树的问题。

\quad \quad 决策树学习算法通常是一个递归地选择最优特征， 并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。

1. 开始，构建根结点，将所有训练数据都放在根结点。选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。

2. 如果这些子集已经能够被基本正确分类，那么构建叶结点，并将这些子集分到所对应的叶结点中去，如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点。

3. 如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。

4. 最后每个子集都被分到叶结点上，即都有了明确的类。这就生成了一棵决策树。

基本算法如下：

输入：
\qquad 训练集： D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯ , ( x N , y N ) } D=\{ (x_1 ,y_1 ),(x_2,y_2 ),⋯,(x_N,y_N) \} D={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}
\qquad 属性(特征)集： A = { a 1 , a 2 , . . . , a d } A=\{ a_1,a_2,...,a_d \} A={a1​,a2​,...,ad​}
过程：
\qquad 函数$TreeGenerate(D,A)$
（ 1 ） 生成结点根node
（ 2 ） if D中样本全属于同一类别$C_k$ then
（ 3 ） \qquad 将node标记为$C_k$ 类叶节点； return
（ 4 ）end if
（ 5 ）if $A=\varnothing$ OR D中样本在 A 上取值相同 then
（ 6 ） \qquad 将node标记为叶结点，其类别标记为D中样本数最多的类 return
（ 7 ）end if
（ 8 ）从A中选择最优划分属性$a_{\ast }$
（ 9 ）for $a_{\ast }$ 的每一个值$a_{\ast }^v$ do
（10） \qquad 为node生成一个分支：令$D_v$表示D中在$a_{\ast }$上取值为$a_{\ast }^v$的样本子集
（11 ） \qquad if $D_v$为空 then
（12） \qquad \qquad 将分支结点标记为叶结点，其类别标记为D中样本最多的类
（13 ） \qquad else
（14 ） \qquad \qquad 以 T r e e G e n e r a t e ( D v , A − { a ∗ } ) TreeGenerate(D_v, A - \{a_*\}) TreeGenerate(Dv​,A−{a∗​})为分支结点
（15 ） \qquad end if
（16）end for
输出：
\qquad 以node为根节点的决策树

\quad \quad 以上方法生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据却未必有很好的分类能力，即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。具体地，就是去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点。如果特征数量很多，也可以在决策树学习开始的时候，对特征进行选择，只留下对训练数据有足够分类能力的特征。

\quad \quad 决策树通常有三个步骤：特征选择、决策树的生成、决策树的修剪。

使用决策树做预测需要以下过程：

• 收集数据：可以使用任何方法。比如想构建一个相亲系统，我们可以从媒婆那里，或者通过参访相亲对象获取数据。根据他们考虑的因素和最终的选择结果，就可以得到一些供我们利用的数据了。

• 准备数据：收集完的数据，我们要进行整理，将这些所有收集的信息按照一定规则整理出来，并排版，方便我们进行后续处理。

• 分析数据：可以使用任何方法，决策树构造完成之后，我们可以检查决策树图形是否符合预期。

• 训练算法：这个过程也就是构造决策树，同样也可以说是决策树学习，就是构造一个决策树的数据结构。

• 测试算法：使用经验树计算错误率。当错误率达到了可接收范围，这个决策树就可以投放使用了。

• 使用算法：此步骤可以使用适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。

4、决策树构建-三步骤

\quad \quad 使用决策树做预测的每一步骤都很重要，数据收集不到位，将会导致没有足够的特征让我们构建错误率低的决策树。数据特征充足，但是不知道用哪些特征好，将会导致无法构建出分类效果好的决策树模型。从算法方面看，决策树的构建是我们的核心内容。

\quad \quad 决策树要如何构建呢？通常，这一过程可以概括为3个步骤：特征选择、决策树的生成和决策树的修剪。

4.1 特征选择

\quad \quad 特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率，如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。

\quad \quad 特征选择的准则是信息增益(information gain)或信息增益比。

\quad \quad 那么，什么是信息增益？在讲解信息增益之前，让我们看一组实例，贷款申请样本数据表。

\quad \quad 希望通过所给的训练数据学习一个贷款申请的决策树，用以对未来的贷款申请进行分类，即当新的客户提出贷款申请时，根据申请人的特征利用决策树决定是否批准贷款申请。

\quad \quad 特征选择就是决定用哪个特征来划分特征空间。比如，我们通过上述数据表得到两个可能的决策树，分别由两个不同特征的根结点构成。

\quad \quad 图5.3(a)所示的根结点的特征是年龄，有3个取值，对应于不同的取值有不同的子结点。图5.3(b)所示的根节点的特征是工作，有2个取值，对应于不同的取值有不同的子结点。两个决策树都可以从此延续下去。问题是：究竟选择哪个特征更好些？这就要求确定选择特征的准则。直观上，如果一个特征具有更好的分类能力，或者说，按照这一特征将训练数据集分割成子集，使得各个子集在当前条件下有最好的分类，那么就更应该选择这个特征。信息增益就能够很好地表示这一直观的准则。

4.1.1 熵(entropy)

\quad \quad 在信息论与概率统计中，熵（entropy） 是表示随机变量 不确定性的度量。熵也指物体内部的混乱程度，熵值越高，混乱程度越高。

\quad \quad 设$X$是一个取有限个值的离散随机变量，其概率分布为:
$$P(X=x_i)=p_i,i=1,2,\cdots ,n$$
则随机变量$X$的熵定义为：
$$H(X)=-\sum _{i=1}^n{p}_{i}log{p}_i$$

4.1.2 条件熵(entropy)

\quad \quad 条件熵$H(Y|X)$表示在已知随机变量$X$的条件下随机变量$Y$的不确定性。

\quad \quad 设有随机变量$(X,Y)$其联合概率分布为：
$$P(X=x_i,Y=y_j)=p_{ij},i=1,2,...,n;j=1,2,...,m$$

随机变量$X$给定的条件下随机变量$Y$的条件熵（conditional entropy）$H(Y|X)$，定义为$X$给定条件下$Y$的条件概率分布的熵对$X$的数学期望：
$$H(Y|X)=\sum _{i=1}^n{p}_{i}H(Y|X=x_i)$$

其中，$p_i=p(X=x_i),i=1,2,...,n$

\quad \quad 当熵和条件熵中的概率由数据估计（如极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）。此时，如果有0概率，令$0log0=0$。

4.1.3 信息增益

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

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

$$g(D,A)=H(D)-H(D|A)$$

一般地，熵$H(Y)$与条件熵$H(Y|X)$之差称为互信息（mutual information）。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

根据信息增益准则的特征选择方法：

\quad \quad 对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。

算法（信息增益算法）
输入：训练数据集$D$和特征$A$
输出：特征$A$对训练数据集$D$的信息增益$g(D,A)$

\quad \quad 其中，$H(D)$是数据集$D$的熵，$H(D_i)$是数据集$D_i$的熵，$H(D|A)$是数据集$D$对特征$A$的条件熵。 $D_i$是$D$中特征$A$取第$i$个值的样本子集，$C_k$是$D$中属于第$k$类的样本子集。$n$是特征$A$取 值的个数，$K$是类的个数。

根据此公式计算经验熵$H(D)$，分析贷款申请样本数据表中的数据。最终分类结果只有两类，即放贷和不放贷。根据表中的数据统计可知，在15个数据中，9个数据的结果为放贷，6个数据的结果为不放贷。所以数据集D的经验熵H(D)为：

$$H(D)=-\frac{9}{15}lo{g}_2\frac{9}{15}-\frac{6}{15}lo{g}_2\frac{6}{15}=0.971$$

4.1.4 信息增益比

\quad \quad 以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比可以对这个问题进行校正，这是特征选择的另一个标准。

定义：

\quad \quad 特征$A$对训练数据集$D$的信息增益比$g_R(D,A)$定义为其信息增益$g(D,A)$与训练数据集$D$关于特征A的值的经验熵$H_A(D)$之比：
$$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$$

其中，$$H_A(D)=-\sum _{i=1}^n\frac{|D_i|}{|D|}lo{g}_2\frac{|D_i|}{|D|},n是特征A取值的个数。$$

【代码实现经验熵、信息增益、信息增益比】

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inline
import math
import operator
from matplotlib.font_manager import FontProperties
from math import log
import pprint
from sklearn.datasets import load_iris
from collections import Counter

"""
函数说明:计算经验熵(香农熵)

Parameters:
    datasets - 数据集
    j-数据集第j列
Returns:
     ent - 经验熵(香农熵)
     当j=-1时，返回训练数据集D的经验熵
     当j为其他时，返回训练数据集关于第j特征的值的熵
"""
def single_ent(datasets,j):
    data_length = len(datasets)#返回数据集的行数即样本个数
    label_count = {}#保存每个标签(Label)出现次数的字典
    for i in range(data_length):
        label = datasets[i][j]#数据集的最后一列
        if label not in label_count:#如果标签(Label)没有放入统计次数的字典,添加进去
            label_count[label] = 0
        label_count[label] += 1#Label计数
    ent = -sum([(p / data_length) * log(p / data_length, 2)#计算经验熵
                for p in label_count.values()])
    return ent#返回经验熵
"""
函数说明:计算各个特征对于训练集的条件经验熵

Parameters:
    datasets - 数据集
    j - 数据集第j列即特征值索引
Returns:
     cond_ent - 条件经验熵(香农熵)
"""
# 经验条件熵$ H(D|A)$
def cond_ent(datasets, j):#参数j：指定特征
    data_length = len(datasets)
    feature_sets = {}
    for i in range(data_length):
        feature = datasets[i][j]
        if feature not in feature_sets:#如果特征没有放入统计次数的字典,添加进去
            feature_sets[feature] = []
        feature_sets[feature].append(datasets[i])#划分数据集
    cond_ent = sum(
        [(len(p) / data_length) * single_ent(p,-1) for p in feature_sets.values()])
    return cond_ent
"""
函数说明:计算某特征对于训练集的信息增益

Parameters:
    datasets - 数据集
    j - 数据集第j列即特征值索引
Returns:信息增益
    
"""

# 信息增益
def info_gain(datasets, j):
    return single_ent(datasets,-1)-cond_ent(datasets,j)
"""
函数说明:计算某特征对于训练集的信息增益比

Parameters:
   datasets - 数据集
    j - 数据集第j列即特征值索引
Returns:信息增益比
    
"""
# 信息增益比
def info_gain_ratio(datasets,j):
    return 0 if single_ent(datasets,j)==0 else info_gain(datasets,j)/single_ent(datasets,j)


"""
函数说明:输出所有特征信息增益，并选择信息增益最大的特征，为根结点特征
Parameters:
    datasets - 数据集
Returns:
    bestFeature - 信息增益最大的(最优)特征的索引值

"""
def info_gain_bestfeature(datasets):
    count = len(datasets[0]) - 1  #特征数量
    features = [] #记录各个特征的信息增益
    for c in range(count):
        c_info_gain = info_gain(datasets,c)#信息增益
        features.append((c, c_info_gain))
        print('特征({}) - 信息增益 - {:.3f}'.format(labels[c], c_info_gain))
    # 比较大小
    best_ = max(features, key=lambda x: x[-1])
    bestFeature=best_[0]
    return '特征({})的信息增益最大，选择为根节点特征'.format(labels[best_[0]])

"""
函数说明:输出所有特征信息增益比，并选择信息增益比最大的特征，为根结点特征
Parameters:
    datasets - 数据集
Returns:
    bestFeature - 信息增益最大的(最优)特征的索引值

"""

def info_gain_ratio_bestfeature(datasets):
    count = len(datasets[0]) - 1  #特征数量
    features1 = [] #记录各个特征的信息增益
    for c in range(count):
        c_info_gain_ratio = info_gain_ratio(datasets,c)#信息增益比
        features1.append((c, c_info_gain_ratio))
        print('特征({}) - 信息增益比 - {:.3f}'.format(labels[c], c_info_gain_ratio))
    # 比较大小
    best_ = max( features1, key=lambda x: x[-1])
    bestFeature=best_[0]
    return '特征({})的信息增益比最大，选择为根节点特征'.format(labels[best_[0]])
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

实现上述案例表5.1

1、创建数据集

def create_data():
    datasets = [['青年', '否', '否', '一般', '否'],
               ['青年', '否', '否', '好', '否'],
               ['青年', '是', '否', '好', '是'],
               ['青年', '是', '是', '一般', '是'],
               ['青年', '否', '否', '一般', '否'],
               ['中年', '否', '否', '一般', '否'],
               ['中年', '否', '否', '好', '否'],
               ['中年', '是', '是', '好', '是'],
               ['中年', '否', '是', '非常好', '是'],
               ['中年', '否', '是', '非常好', '是'],
               ['老年', '否', '是', '非常好', '是'],
               ['老年', '否', '是', '好', '是'],
               ['老年', '是', '否', '好', '是'],
               ['老年', '是', '否', '非常好', '是'],
               ['老年', '否', '否', '一般', '否'],
               ]
    labels = [u'年龄', u'有工作', u'有自己的房子', u'信贷情况', u'类别']
    # 返回数据集和每个维度的名称
    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()
train_data = pd.DataFrame(datasets, columns=labels)
train_data
1
2
3

2、套用上述模块

info_gain_bestfeature(np.array(datasets))
1

查看结果，与李航统计学习方法书上例题5.2答案一样。

info_gain_ratio_bestfeature(np.array(datasets))
1

4.2 决策树算法

\quad \quad 构建决策树的算法有很多，比如C4.5、ID3和CART。

4.2.1 ID3 算法

\quad \quad ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。

具体方法是：

1）从根结点(root node)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征。

2）由该特征的不同取值建立子节点，再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止；

3）最后得到一个决策树。

算法步骤：

算法 5.2 （ID3）算法
输入：训练数据集D，特征集A，阈值$\epsilon$;
输出：决策树T
（1）若D中所有实例属于同一类$C_k$，则T为单结点树，并将类$C_k$作为该结点的类标记，返回T；
（2）若$A=\varnothing$,则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 } A-\{A_g\} A−{Ag​}为特征集，递归地调用步（1）~（5），得到子树$T_i$，返回$T_i$。

决策树ID3算法的局限性
　　
　　ID3算法虽然提出了新思路，但是还是有很多值得改进的地方。

a) ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。

b) ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。如果校正这个问题呢？

c) ID3算法对于缺失值的情况没有做考虑

d) 没有考虑过拟合的问题

\quad \quad ID3 算法的作者昆兰基于上述不足，对ID3算法做了改进，这就是C4.5算法，下面我们就来聊下C4.5算法。

4.2.2 C4.5算法

\quad \quad 上一节我们讲到ID3算法有四个主要的不足，一是不能处理连续特征，第二个就是用信息增益作为标准容易偏向于取值较多的特征，最后两个是缺失值处理的问和过拟合问题。昆兰在C4.5算法中改进了上述4个问题:

• 对于第一个问题，不能处理连续特征， C4.5的思路是将连续的特征离散化。比如m个样本的连续特征A有m个，从小到大排列为$a_1,a_2,...,a_m$,则C4.5取相邻两样本值的平均数，一共取得m-1个划分点，其中第i个划分点Ti表示为：$T_I=\frac{a_i+a_{i+1}}{2}$。对于这m-1个点，分别计算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的增益最大的点为$a_t$,则小于$a_t$的值为类别1，大于$a_t$的值为类别2，这样我们就做到了连续特征的离散化。要注意的是，与离散属性不同的是，如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程。
• 对于第二个问题，信息增益作为标准容易偏向于取值较多的特征的问题。我们引入一个信息增益比,用信息增益比选择特征。
• 对于第三个缺失值处理的问题，主要需要解决的是两个问题，一是在样本某些特征缺失的情况下选择划分的属性，二是选定了划分属性，对于在该属性上缺失特征的样本的处理。
• 对于第4个问题，C4.5引入了正则化系数进行初步的剪枝。

决策树C4.5算法的局限性
　　　
　 \quad \quad C4.5虽然改进或者改善了ID3算法的几个主要的问题，仍然有优化的空间。

1)由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。剪枝的算法有非常多，C4.5的剪枝方法有优化的空间。思路主要是两种，一种是预剪枝，即在生成决策树的时候就决定是否剪枝。另一个是后剪枝，即先生成决策树，再通过交叉验证来剪枝。剪枝算法见下篇。

2)C4.5生成的是多叉树，即一个父节点可以有多个节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。

3)C4.5只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。

4)C4.5由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。如果能够加以模型简化可以减少运算强度但又不牺牲太多准确性的话，那就更好了。

\quad \quad 这4个问题在CART树里面部分加以了改进。所以目前如果不考虑集成学习话，在普通的决策树算法里，CART算法算是比较优的算法了。scikit-learn的决策树使用的也是CART算法。在下篇里我们会重点聊下CART算法的主要改进思路，上篇就到这里。

4.2.3 手写python实现ID3、C4.5算法

\quad \quad 由于 ID3 算法与C4.5算法相似，因此可以写一个python模板，只不过增加一个选方法的函数。

【代码实现,构建决策树】

第一部分：构建决策树

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inline
import math
import operator
from matplotlib.font_manager import FontProperties
from math import log
import pprint
from sklearn.datasets import load_iris
from collections import Counter

"""
函数说明:计算经验熵(香农熵)

Parameters:
    datasets - 数据集
    j-数据集第j列
Returns:
     ent - 经验熵(香农熵)
     当j=-1时，返回训练数据集D的经验熵
     当j为其他时，返回训练数据集关于第j特征的值的熵
"""
def single_ent(datasets,j):
    data_length = len(datasets)#返回数据集的行数即样本个数
    label_count = {}#保存每个标签(Label)出现次数的字典
    for i in range(data_length):
        label = datasets[i][j]#数据集的最后一列
        if label not in label_count:#如果标签(Label)没有放入统计次数的字典,添加进去
            label_count[label] = 0
        label_count[label] += 1#Label计数
    ent = -sum([(p / data_length) * log(p / data_length, 2)#计算经验熵
                for p in label_count.values()])
    return ent#返回经验熵
"""
函数说明:计算各个特征对于训练集的条件经验熵

Parameters:
    datasets - 数据集
    j - 数据集第j列即特征值索引
Returns:
     cond_ent - 条件经验熵(香农熵)
"""
# 经验条件熵$ H(D|A)$
def cond_ent(datasets, j):#参数j：指定特征
    data_length = len(datasets)
    feature_sets = {}
    for i in range(data_length):
        feature = datasets[i][j]
        if feature not in feature_sets:#如果特征没有放入统计次数的字典,添加进去
            feature_sets[feature] = []
        feature_sets[feature].append(datasets[i])#划分数据集
    cond_ent = sum(
        [(len(p) / data_length) * single_ent(p,-1) for p in feature_sets.values()])
    return cond_ent
"""
函数说明:计算某特征对于训练集的信息增益

Parameters:
    datasets - 数据集
    j - 数据集第j列即特征值索引
Returns:信息增益
    
"""

# 信息增益
def info_gain(datasets, j):
    return single_ent(datasets,-1)-cond_ent(datasets,j)
"""
函数说明:计算某特征对于训练集的信息增益比

Parameters:
   datasets - 数据集
    j - 数据集第j列即特征值索引
Returns:信息增益比
    
"""
# 信息增益比
def info_gain_ratio(datasets,j):
    return 0 if single_ent(datasets,j)==0 else info_gain(datasets,j)/single_ent(datasets,j)


"""
函数说明:选取最有特征
Parameters:
    datasets - 数据集
    method-选择最优特征准则：ID3：依据信息增益；C4.5:依据信息增益比
Returns:
    bestFeature - 信息增益最大的(最优)特征的索引值

"""
def bestfeature(datasets,method='ID3'):
    assert method in ['ID3','C4.5'],"method 须为id3或c45"
    def calcEnt(datasets,j):
        if method=='ID3':
            return info_gain(datasets,j)
        if method=='C4.5':
            return info_gain_ratio(datasets,j)
    count = len(datasets[0]) - 1  #特征数量   
    features = [] #记录各个特征的信息增益
    
    for c in range(count):
        c_info_gain = calcEnt(datasets,c)#信息增益
        features.append((c, c_info_gain))
        #print('特征({}) - 信息增益 - {:.3f}'.format(labels[c], c_info_gain))
    # 比较大小
    best_ = max(features, key=lambda x: x[-1])
    bestFeature=best_[0]
    return bestFeature

"""
函数说明:统计classList中出现最多的类标签

Parameters:
    classList - 类标签列表
Returns:
    sortedClassCount[0][0] - 出现此处最多的元素(类标签)

"""
def majorityCnt(classList):
    classCount = {}
    for vote in classList:                                        #统计classList中每个元素出现的次数
        if vote not in classCount.keys():classCount[vote] = 0   
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True)        #根据字典的值降序排序
    return sortedClassCount[0][0]   #返回classList中出现次数最多的元素


"""
函数说明:按照给定特征划分数据集

Parameters:
    datasets - 待划分的数据集
    axis - 划分数据集的特征
    value - 需要删除的特征的值
Returns:
    无

"""
def splitDataSet(datasets, axis, value):       
    retDataset = []                                        #创建返回的数据集列表
    for featVec in datasets:                             #遍历数据集
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]                #去掉axis特征
            reducedFeatVec.extend(featVec[axis+1:])     #将符合条件的添加到返回的数据集
            retDataset.append(reducedFeatVec)
    return retDataset                                      #返回划分后的数据集



"""
函数说明:创建决策树

Parameters:
    datasets - 训练数据集
    labels - 分类属性标签
    featLabels - 存储选择的最优特征标签
Returns:
    myTree - 决策树

"""
def createTree(datasets, labels, featLabels):
    classList = [example[-1] for example in datasets]            #取分类标签(是否放贷:yes or no)
    if classList.count(classList[0]) == len(classList):            #1、如果类别完全相同则停止继续划分
        return classList[0]
    if len(datasets[0]) == 1:                                   #2、如果特征集为空即数据集只有1列
        return majorityCnt(classList)                          #遍历完所有特征时返回出现次数最多的类标签
    bestFeat = bestfeature(datasets,method='ID3')                #3、选择最优特征，方法可以更改
    bestFeatLabel = labels[bestFeat]                            #最优特征的标签
    featLabels.append(bestFeatLabel)
    myTree = {bestFeatLabel:{}}                                    #根据最优特征的标签生成树
    del(labels[bestFeat])                                        # 已经选择的特征不再参与分类
    featValues = [example[bestFeat] for example in datasets]        #得到训练集中所有最优特征的属性值
    uniqueVals = set(featValues)                                #去掉重复的属性值
    for value in uniqueVals:                                    #遍历特征，创建决策树。                       
        myTree[bestFeatLabel][value] = createTree(splitDataSet(datasets, bestFeat, value), labels, featLabels)
    return myTree


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

第二部分：决策树可视化

"""
函数说明:获取决策树叶子结点的数目

Parameters:
    myTree - 决策树
Returns:
    numLeafs - 决策树的叶子结点的数目

"""
def getNumLeafs(myTree):
    numLeafs = 0                                                #初始化叶子
    firstStr = next(iter(myTree))                                #python3中myTree.keys()返回的是dict_keys,不在是list,所以不能使用myTree.keys()[0]的方法获取结点属性，可以使用list(myTree.keys())[0]
    secondDict = myTree[firstStr]                                #获取下一组字典
    for key in secondDict.keys():
        if type(secondDict[key]).__name__=='dict':                #测试该结点是否为字典，如果不是字典，代表此结点为叶子结点
            numLeafs += getNumLeafs(secondDict[key])
        else:   numLeafs +=1
    return numLeafs
"""
函数说明:获取决策树的层数

Parameters:
    myTree - 决策树
Returns:
    maxDepth - 决策树的层数
"""
def getTreeDepth(myTree):
    maxDepth = 0                                                #初始化决策树深度
    firstStr = next(iter(myTree))                                #python3中myTree.keys()返回的是dict_keys,不在是list,所以不能使用myTree.keys()[0]的方法获取结点属性，可以使用list(myTree.keys())[0]
    secondDict = myTree[firstStr]                                #获取下一个字典
    for key in secondDict.keys():
        if type(secondDict[key]).__name__=='dict':                #测试该结点是否为字典，如果不是字典，代表此结点为叶子结点
            thisDepth = 1 + getTreeDepth(secondDict[key])
        else:   thisDepth = 1
        if thisDepth > maxDepth: maxDepth = thisDepth            #更新层数
    return maxDepth

"""
函数说明:绘制结点

Parameters:
    nodeTxt - 结点名
    centerPt - 文本位置
    parentPt - 标注的箭头位置
    nodeType - 结点格式
Returns:
    无
"""
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
    arrow_args = dict(arrowstyle="<-")                                            #定义箭头格式
    font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=14)        #设置中文字体
    createPlot.ax1.annotate(nodeTxt, xy=parentPt,  xycoords='axes fraction',    #绘制结点
        xytext=centerPt, textcoords='axes fraction',
        va="center", ha="center", bbox=nodeType, arrowprops=arrow_args, FontProperties=font)

"""
函数说明:标注有向边属性值

Parameters:
    cntrPt、parentPt - 用于计算标注位置
    txtString - 标注的内容
Returns:
    无

"""
def plotMidText(cntrPt, parentPt, txtString):
    xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]                                            #计算标注位置                   
    yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]
    createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)

"""
函数说明:绘制决策树

Parameters:
    myTree - 决策树(字典)
    parentPt - 标注的内容
    nodeTxt - 结点名
Returns:
    无

"""
def plotTree(myTree, parentPt, nodeTxt):
    decisionNode = dict(boxstyle="sawtooth", fc="0.8")                                        #设置结点格式
    leafNode = dict(boxstyle="round4", fc="0.8")                                            #设置叶结点格式
    numLeafs = getNumLeafs(myTree)                                                          #获取决策树叶结点数目，决定了树的宽度
    depth = getTreeDepth(myTree)                                                            #获取决策树层数
    firstStr = next(iter(myTree))                                                            #下个字典                                                 
    cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff)    #中心位置
    plotMidText(cntrPt, parentPt, nodeTxt)                                                    #标注有向边属性值
    plotNode(firstStr, cntrPt, parentPt, decisionNode)                                        #绘制结点
    secondDict = myTree[firstStr]                                                            #下一个字典，也就是继续绘制子结点
    plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD                                        #y偏移
    for key in secondDict.keys():                               
        if type(secondDict[key]).__name__=='dict':                                            #测试该结点是否为字典，如果不是字典，代表此结点为叶子结点
            plotTree(secondDict[key],cntrPt,str(key))                                        #不是叶结点，递归调用继续绘制
        else:                                                                                #如果是叶结点，绘制叶结点，并标注有向边属性值                                             
            plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW
            plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
            plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
    plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD

"""
函数说明:创建绘制面板

Parameters:
    inTree - 决策树(字典)
Returns:
    无
"""
def createPlot(inTree):
    fig = plt.figure(1, facecolor='white')                                                    #创建fig
    fig.clf()                                                                                #清空fig
    axprops = dict(xticks=[], yticks=[])
    createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)                                #去掉x、y轴
    plotTree.totalW = float(getNumLeafs(inTree))                                            #获取决策树叶结点数目
    plotTree.totalD = float(getTreeDepth(inTree))                                            #获取决策树层数
    plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0;                                #x偏移
    plotTree(inTree, (0.5,1.0), '')                                                            #绘制决策树
    plt.show()                                                                                 #显示绘制结果     


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

案例：

if __name__ == '__main__':
    datasets, labels = create_data()#上一例子已创建
    featLabels = []
    myTree = createTree(datasets, labels, featLabels)
    print(myTree)
    createPlot(myTree)  
1
2
3
4
5
6

{‘有自己的房子’: {‘是’: ‘是’, ‘否’: {‘有工作’: {‘是’: ‘是’, ‘否’: ‘否’}}}}

4.3 决策树的剪枝

见此文

总结

优点：

• 计算复杂度不高；
• 对中间缺失值不敏感；
• 解释性强，在解释性方面甚至比线性回归更强；
• 与传统的回归和分类方法相比，决策树更接近人的决策模式，可以用图形表示，非专业人士也可以轻松理解；
• 可以直接处理定性的预测变量而不需创建哑变量。

缺点：

• 决策树的预测准确性一般比回归和分类方法弱，但可以通过用集成学习方法组合大量决策树，显著提升树的预测效果；

• 可能会产生过度匹配的问题

适用数据类型：数值型和标称型

参考资料：
1、李航《统计学习方法》
2、https://blog.csdn.net/c406495762/article/details/76262487