机器学习之决策树（ID3 C4.5 CART）

2019-01-26 本文已影响6人 Athenaearl

优缺点和适用范围：

优点：

计算不那么费时
便于人类的理解
可处理非相关特征

缺点：

容易过拟合（关于如何尽量避免这种缺点带来的影响，本篇文章后期（剪枝）有介绍和相关代码）

适用范围：

数值型和非数值型数据均可

决策树的构型其实也是在模拟人的的思维过程：
一个人在获得一个结论的过程中总是需要多步判断。
比如：举个不算恰当的例子，假设这个女生偏好身高高的男生，其次还有点颜控，最后对性格有点要求，那么她做出选择的决策树可能就是这样的。

面对男生求婚时女孩子的选择
但是在开始学习决策树之前应该先了解一些信息论的知识
假设x 为一种分类， p(x) 为这种分类在总的分类中出现的概率
1. 信息的概念：
信息是指人类社会中传播的一切内容。我们显然需要将信息进行量化度量，香农于1948年提出了信息熵（或称香农熵）的概念，用于量化信息
2. 信息熵：
信息的大小很大程度上依赖于信息的不确定性。这也是信息论一个基本的思想，即，一件小概率事件的发生要比一件大概率事件的发生提供更多的信息。信息的不确定性越大，其背后隐藏的信息更大。
3. 信息(或称“自信息”）的计算：
信息则被定义为I(x) = -log(p(x)) ，其中log以2为底。用于表示该标签单独的信息大小
4. 信息熵的计算：
而熵则被定义为 H = SUM(I(x) * p(x)) 即, 对于所有的标签，I(x) * p(x) 的加和。即每一种标签的出现的概率和这种标签下信息的乘积
5. 条件熵：
已知了一种分类条件，首先计算在该分类条件下分得的每一类的信息熵 * 这一类出现概率。最后将所有的进行加和得到了条件熵。理论上来讲，不管哪一种分类方式，条件熵都会比样本的信息熵要小，一是，公式中可以直接看出来。二是，如果将一个数据集进行了分类，显然数据在向着有序的方向在进行。但是，哪一种分类方式能使得当前数据的混乱程度最小呢？？因此引出了信息增益的概念
6. 信息增益：
信息增益则被定义为熵 - 条件熵
因此信息增益为正代表着数据向着有序的方向进行
而决策树所做的事情就是绘出一个能让熵下降最快的树，因此每次都要选择在当前情况下信息增益最大的分类方法

一. ID3决策树

有了以上的知识：我们可以开始对于ID3决策树怎么创建进行理解了
决策树的建立是一个递归的过程，事实上如果大家对于树这种结构有一些了解的话可以很快理解为什么这应该是一个递归的过程，因此不再赘述。
首先我们拿到了一个用于训练的样本集合，计算得到了该样本的信息熵。然后以每一个feature分别做分类，获得了每种分类的条件熵。从而计算得到每一种分类的信息增益，其中信息增益最大的那一种对应的就是数据混乱程度下降最快的方向，因此使用这一种的分类，这一分类即为这一点上的决策节点。然后基于这种分类将数据划分成多个子集合，分别再将这些子集合进行如上操作。从而建立决策树

以下代码来自《机器学习实战》为便于理解，增加了部分注释，同时由于笔者使用的是python 3.6，因此对书中部分代码有小部分修改
首先创建一个文件 trees.py
tree_plotter为我们自己建立的包，在后面会有相应的代码

from math import log
import operator
import tree_plotter

计算熵的代码如下：

# 表现数据的混乱程度的方法 一种是计算熵 一种是计算尼基不纯度
# 计算熵，信息：l(xi) = log(p(xi)) log 是以2为底的对数 p(xi) 为这个分类出现的概率
# 熵：H = SUM(p(xi) * l(xi)) 熵越大则混合的数据越多，需要添加更多的分类
def calc_shannon_ent(data_set):
    num_entries = len(data_set)  # 获得数据量
    label_counts = {}  # 为标签出现次数计数，字典
    for feat_vec in data_set:
        current_label = feat_vec[-1]  # 获得数据的标签，因为数据的最后一项是标签
        if current_label not in label_counts.keys():
            label_counts[current_label] = 0
        label_counts[current_label] += 1  # 计数
    shannon_ent = 0.0
    for key in label_counts:
        prob = float(label_counts[key])/num_entries  # 计算每一项出现的概率
        shannon_ent -= prob * log(prob, 2)  # 计算香农熵
    return shannon_ent

那么在一系列数据中想要知道怎样决策，熵下降最快，依靠如下代码计算哪一个特征最适合做数据划分：
思想比较简单，就是分别根据每一个特征进行数据集的划分，找到熵最小的，这个就是决策树的头节点

# axis 表示这个特征的那个轴， value 表示要抽取的元素这个特征下的那个轴的值
# 这个函数的功能其实就是将要的值抽取出来
def split_data_set(data_set, axis, value):
    ret_data_set = []
    for feat_vec in data_set:
        if feat_vec[axis] == value:  # 找到要抽取的那一行
            reduced_feat_vec = feat_vec[:axis]
            # extend 和 append 功能类似，不同在于extend将容器内的东西一个一个加入，而append将一个容器作为一个元素加入
            reduced_feat_vec.extend(feat_vec[axis+1:])
            # 以上两步的意义在于将axis那个值去掉
            ret_data_set.append(reduced_feat_vec)
    return ret_data_set


# 选择最好的数据集分类方式
# 只是把所有的特征都尝试一遍，尝试的事情：按照这个特征下的值做分类，一个值就是一个分类，找到熵最大的一种分类方式
def choose_best_feature_to_split(data_set):
    num_features = len(data_set[0]) - 1  # 列数减1，因为最后一项是标签
    base_entropy = calc_shannon_ent(data_set)  # 初始熵
    best_info_gain = 0.0  # 信息增益
    best_feature = -1
    for i in range(num_features):
        feat_list = [example[i] for example in data_set]  # data_set i 那一列的数据
        unique_vals = set(feat_list)  # 将其生成set 这样没有重复数据
        new_entropy = 0.0
        # 这个循环是用来计算new_entropy 即，条件熵
        for value in unique_vals:
            sub_data_set = split_data_set(data_set, i, value)
            prob = len(sub_data_set)/float(len(data_set))
            new_entropy += prob * calc_shannon_ent(sub_data_set)
        info_gain = base_entropy - new_entropy  # 计算信息增益
        if info_gain>best_info_gain:
            best_info_gain = info_gain
            best_feature = i
    return best_feature

创建决策树：

# 创建决策树
def create_tree(data_set, lables):
    class_list = [example[-1] for example in data_set]  # 获得了所有的标签
    # 如果 class_list[0] 在 class_list 中出现的次数 和 class_list 的长度相同，即，所有的标签完全相同
    if class_list.count(class_list[0]) == len(class_list):
        return class_list[0]
    # 已经遍历了所有的特征，这个时候返回出现次数最高的类别
    if len(data_set[0]) == 1:
        return majority_cnt(class_list)
    best_feat = choose_best_feature_to_split(data_set)
    best_feat_label = lables[best_feat]
    my_tree = {best_feat_label: {}}
    del(lables[best_feat])
    feat_values = [example[best_feat] for example in data_set]
    unique_vals = set(feat_values)
    # 在不同情况下分别建立子树
    for value in unique_vals:
        sub_labels = lables[:]
        my_tree[best_feat_label][value] = create_tree(split_data_set(data_set, best_feat, value), sub_labels)
    return my_tree


# 获得出现次数最多的分类名称
def majority_cnt(class_list):
    class_count = {}
    for vote in class_list:
        if vote not in class_count.keys():
            class_count[vote] = 0
        class_count[vote] += 1
    sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)
    return sorted_class_count[0][0]


# 使用决策树的分类函数
def classify(input_tree, feat_labels, test_vec):
    # first_str = input_tree.key()[0]
    first_str = next(iter(input_tree))
    second_dict = input_tree[first_str]
    feat_index = feat_labels.index(first_str)
    for key in second_dict.keys():
        if test_vec[feat_index] == key:
            if type(second_dict[key]).__name__ == 'dict':
                class_label = classify(second_dict[key],feat_labels,test_vec)
            else:
                class_label = second_dict[key]
    return class_label

其他：
在这里并没有用到⬇️：

# 决策树的存储
def store_tree(input_tree, filename):
    import pickle
    fw = open(filename, 'w')
    pickle.dump(input_tree, fw)
    fw.close()


def grab_tree(filename):
    import pickle
    fr = open(filename)
    return pickle.load(fr)

画出决策树：
在同目录下新创建一个名为tree_plotter.py的文件

# 在python 中使用 Matplotlib 注解绘制树形图
# 注解工具annotations, 可以在数据图形上添加文本注释
import matplotlib.pyplot as plt
# 使用文本绘制树节点
decision_node = dict(boxstyle="sawtooth", fc="0.8")  # fc 是用来表示颜色的，boxstyle 是用来表示box的形状的，比如这里的“sawtooth”为边缘锯齿的box
leaf_node = dict(boxstyle="round4", fc="0.8")
arrow_args = dict(arrowstyle="<-")


def create_plot(in_tree):
    fig = plt.figure(1, facecolor='white')  # 画布1
    fig.clf()  # clear the figure
    axprops = dict(xticks=[], yticks=[])
    create_plot.ax1 = plt.subplot(111, frameon=False, **axprops)  # 这里是subplot 最后一个参数是**name 形式，它拿到的是字典axprops原本的样子。frameon 如果不设置为FALSE，后绘制上去的图层会覆盖下面的图层
    plot_tree.total_w = float(get_num_leafs(in_tree))  # plot_tree.total_w为一种全局变量的表示方法，这里是指获得叶子结点的数量
    plot_tree.total_d = float(get_tree_depth(in_tree))  # 获得树的深度
    plot_tree.x_off = -0.5/plot_tree.total_w
    plot_tree.y_off = 1.0
    plot_tree(in_tree, (0.5, 1.0), '')
    plt.show()


def plot_node(node_txt, center_pt, parent_pt, node_type):
    create_plot.ax1.annotate(node_txt, xy=parent_pt, xycoords='axes fraction', xytext=center_pt,
                             textcoords='axes fraction', va="center", ha="center", bbox=node_type,
                             arrowprops=arrow_args)


def get_num_leafs(my_tree):
    num_leafs = 0
    first_str = next(iter(my_tree))
    second_dict = my_tree[first_str]
    for key in second_dict.keys():
        if type(second_dict[key]).__name__ == 'dict':
            num_leafs += get_num_leafs(second_dict[key])
        else:
            num_leafs += 1
    return num_leafs


def get_tree_depth(my_tree):
    max_depth = 0
    first_str = next(iter(my_tree))
    second_dict = my_tree[first_str]
    for key in second_dict.keys():
        if type(second_dict[key]).__name__ == 'dict':
            this_depth = 1 + get_tree_depth(second_dict[key])
        else:
            this_depth = 0
        if max_depth < this_depth:
            max_depth = this_depth
    return max_depth


def plot_mid_text(centr_pt, parent_pt, txt_string):
    x_mid = (parent_pt[0]-centr_pt[0])/2.0 + centr_pt[0]
    y_mid = (parent_pt[1]-centr_pt[1])/2.0 + centr_pt[1]
    create_plot.ax1.text(x_mid, y_mid, txt_string)


def plot_tree(my_tree, parent_pt, node_txt):
    num_leafs = get_num_leafs(my_tree)
    depth = get_tree_depth(my_tree)
    first_str = next(iter(my_tree))
    cnter_pt = (plot_tree.x_off + (1.0 + float(num_leafs))/2.0/plot_tree.total_w, plot_tree.y_off)
    plot_mid_text(cnter_pt,parent_pt,node_txt)
    plot_node(first_str,cnter_pt,parent_pt,decision_node)
    second_dict = my_tree[first_str]
    plot_tree.y_off = plot_tree.y_off - 1.0/plot_tree.total_d
    for key in second_dict.keys():
        if type(second_dict[key]).__name__ =='dict':
            plot_tree(second_dict[key], cnter_pt, str(key))
        else:
            plot_tree.x_off = plot_tree.x_off + 1.0/plot_tree.total_w
            plot_node(second_dict[key], (plot_tree.x_off, plot_tree.y_off), cnter_pt, leaf_node)
            plot_mid_text((plot_tree.x_off, plot_tree.y_off), cnter_pt, str(key))
    plot_tree.y_off = plot_tree.y_off + 1.0/plot_tree.total_d

效果：

二. C4.5 决策树

实际上，ID3决策树还是存在一些问题的，比如，假设有n个样本，如果有一个特征（比如：编号，1，2，3.....n）对于每一个样本都不一样。在计算熵时候，显然，根据这个特征获得的条件熵最小，信息增益最大，所以编号就会成为这棵树的根结点，然后，这个结点会有n个分支，每一个分支指向一个叶子结点（即一个样本）
这显然不是我们想要的，因为这样的决策树，只适用于测试样本，无法适应新的样本。
为解决这个问题出现了 C4.5
C4.5 引出了一个新的概念：
增益率：
前面我们已经介绍了信息增益：这里信息增益用 $Gain(D, a)$ 表示，其中D表示样本集合，a表示所选定的分类标准。
1. 分类标准（或者说属性）的“固有值”（intrinsic value)定义为：

$IV(a) = - \sum_{v=1}^V\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}$

其中：
$|B|$ 这种表示方式，表达的是B这个集合中元素的数量
$D^v$ 表示的是a这一特征中的取v的样本的集合
如果定义: $p(v) = \frac{|D^v|}{|D|}$
则 $IV(a)$ 可以被写为：

$IV(a) = -\sum_{v=1}^Vp(v)log_2p(v)$

有没有觉得上式有一些眼熟，没错，如果a不是分类标准而是样本的最终类别的话，IV(a)就是信息熵
信息熵用于描述数据的不确定性，因此，如果a这一特征下的的数据取值数目越多，IV(a)越大。举个例子：甜度这一属性：取值为甜、不甜的与取值为甜、还好、不甜的相比IV(a)更小

2. 增益率定义为：

$Gain\_ratio(D, a) = \frac{Gain(D, a)}{IV(a)}$

这样的设定之后会发现，增益率同时考虑了信息增益和可取值数量的问题。但是由于公式的原因，实际上，增益率更加偏好可取值数目少的属性。因此C4.5 决策树并没有直接使用增益率，而是先挑出信息增益高于平均值的属性，然后在从其中挑出增益率最高的
修改代码：

def calc_shannon_ent(data_set, pos):
    num_entries = len(data_set)  # 获得数据量
    label_counts = {}  # 为标签出现次数计数，字典
    for feat_vec in data_set:
        current_label = feat_vec[pos]  # 获得数据的标签，因为数据的最后一项是标签
        if current_label not in label_counts.keys():
            label_counts[current_label] = 0
        label_counts[current_label] += 1  # 计数
    shannon_ent = 0.0
    for key in label_counts:
        prob = float(label_counts[key])/num_entries  # 计算每一项出现的概率
        shannon_ent -= prob * log(prob, 2)  # 计算香农熵
    return shannon_ent


def calculate_gain_ratio(gain, data_set, feat_pos):
    iv = calc_shannon_ent(data_set, feat_pos)
    return gain/float(iv)


def choose_best_feature_to_split(data_set):
    num_features = len(data_set[0]) - 1
    base_entropy = calc_shannon_ent(data_set, -1)
    best_gain_ratio = 0.0
    best_feature = -1
    entropy_list = [0] * num_features
    for i in range(num_features):
        feat_list = [example[i] for example in data_set]
        unique_vals = set(feat_list)
        new_entropy = 0.0
        for value in unique_vals:
            sub_data_set = split_data_set(data_set, i, value)
            prob = len(sub_data_set)/float(len(data_set))
            new_entropy += prob * calc_shannon_ent(sub_data_set, -1)
        info_gain = base_entropy - new_entropy
        entropy_list[i] = info_gain
    average_info_gain = sum(entropy_list)/float(num_features)
    for i in range(num_features):
        if entropy_list[i] > average_info_gain:
            new_gain_ratio = calculate_gain_ratio(entropy_list[i], data_set, i)
            if new_gain_ratio > best_gain_ratio:
                best_gain_ratio = new_gain_ratio
                best_feature = i
    return best_feature

对比ID3和C4.5：
数据：

1,young,myope,no,reduced,no lenses
2,young,myope,no,normal,soft
3,young,myope,yes,reduced,no lenses
4,young,myope,yes,normal,hard
5,young,hyper,no,reduced,no lenses
6,young,hyper,no,normal,soft
7,young,hyper,yes,reduced,no lenses
8,young,hyper,yes,normal,hard
9,pre,myope,no,reduced,no lenses
10,pre,myope,no,normal,soft
11,pre,myope,yes,reduced,no lenses
12,pre,myope,yes,normal,hard
13,pre,hyper,no,reduced,no lenses
14,pre,hyper,no,normal,soft
15,pre,hyper,yes,reduced,no lenses
16,pre,hyper,yes,normal,no lenses
17,presbyopic,myope,no,reduced,no lenses
18,presbyopic,myope,no,normal,no lenses
19,presbyopic,myope,yes,reduced,no lenses
20,presbyopic,myope,yes,normal,hard
21,presbyopic,hyper,no,reduced,no lenses
22,presbyopic,hyper,no,normal,soft
23,presbyopic,hyper,yes,reduced,no lenses
24,presbyopic,hyper,yes,normal,no lenses

ID3:

ID3
C4.5:

C4.5

从以上可以清晰的看见C4.5使用增益率的效果

三. CART决策树

以上两种决策树都是通过计算熵来表现数据的混乱程度
而这里即将介绍的是利用“基尼指数”（Gini index）来选择划分属性
基尼值：随机抽取两个样本，其标识不一样的概率
$Gini(D) = \sum_{k=1}^{|y|}\sum_{k'\not=k}p_kp_{k'} = 1 - \sum_{k=1}^{|y|}p_k^2$
基尼值越小，代表，随机抽取两个样本，其标识一样的概率越大。因此，数据纯度越高
基尼指数：对应于条件熵，表现在某种分类下的对应的尼基值
$Gini_index(D,a)=\sum_{v=1}^{V}\frac{|D|}{|D^v|}Gini(D^v)$
相比于以上两种决策树，唯一改变的就是计算方式
因此不再对于代码赘述

四.剪枝(pruning)处理

剪枝处理分为了：预剪枝和后剪枝两种处理方式

预剪枝：在建立树之前剪枝
后剪枝：在建立树之后剪枝

怎么剪枝？？
剪枝的思想很简单，只要判断如果这个结点作为了子树根结点相比于直接将这个结点处理成叶子结点的准确率是否有提升：
如果有提升：这个结点将会成为子树根结点
如果没有提升：这个结点将会成为该分支下数据集的出现最多的类别

预剪枝：
在即将在这个点上确定结点之前，将这个点是根结点和这个点是叶子结点两种情况分别建立出来。然后分别用测试集判断准确率。比较两种准确率，哪种的准确率高，用哪种。

后剪枝：
在已经建立好的树中，倒着遍历每一个根结点，判断这个结点适合是根结点还是叶子结点，对树做修改

虽然说决策树大多数场合适用于离散值情况，但是并不代表不能应用于连续值情况，一般来说，连续值情况，决策树的处理方式是利用二分将连续值分成两类，进行决策，此类不再赘述