决策树简单介绍及python实战

1.介绍

简介

决策树是一种预测模型,代表的是对象属性与对象值之间的映射关系。决策树是一种树形结构,其中:

  • 每个内部结点表示一个属性的测试

  • 每个分支表示一个测试输出

  • 每个叶结点代表一种类别

分类

预测结果的差异,决策树学习可细分两类。

  • 分类树,其预测结果仅限于一组离散数值。树的每个分支对应一组由逻辑与连接的分类特征,而该分支上的叶节点对应由上述特征可以预测出的分类标签。

  • 回归树,其预测结果为连续值(例如实数)。

发展历程(分裂特征),决策树学习可细分五(三)类。

  • CLS是最早的决策树算法。

  • ID3是主流的决策树算法之一,基于信息增益进行特征的选择和树的生长

  • C4.5是ID3的改进,基于信息增益率来选择最优属性。

  • CART是可用于分类与回归任务的二叉决策树,广泛使用。

  • RF(Random Forest,随机森林)是把决策树并行集成的组合算法。

  • GBDT/XGBoost/LightGBM/catboost:boosting系列模型,可以基于树模型做串行集成。

选题意义

依据不同算法的用途,可以用于不同的问题。

后文结构描述

  • 首先介绍了相关理论

  • 其次使用ID3和C4.5做了一个实例。

  • 最后做了一个总结

2.相关理论

涉及数学原理

  • 贝叶斯定理

  • 贝叶斯概率

  • 真值表

  • 马尔可夫链

问题定义

公式

  • 信息熵,它是消除不确定性所需信息量的度量,也是未知事件可能含有的信息量,可以度量样本集合「纯度」。

    对应到机器学习中,假定当前数据集 D 中有 y 类,其中第 k类样本占比为 p_k ,则信息熵的计算公式如下:

$$
Ent(D) = - \sum_{K = 1}^{|y|} p_klog_{2}{p_k}
$$

 

计算信息熵时约定:

若 p = 0 ,则 plog_2 {p} = 0 ;

Ent(D) 的最小值为0,最大值为 log_2{|y|}

Ent(D)的值越小,则D的“ 纯度 ” 越高。

但 P_k 取值为 1 的时候,信息熵 为 0 ,(很显然这时候概率 1 表示确定事件 ,没有任何不确定性) ;而当 p_k 是均匀分布的时候 ,信息熵取最大值 log(|y|) (此时所有候选同等概率,不确定性最大)

  • 信息增益,它衡量的是我们选择某个属性进行划分时信息熵的变化(可以理解为基于这个规则划分,不确定性降低的程度)。

$$
Gain(D,a) = Ent(D) - \sum_{v=1}^v \frac{|D^v|}{|D|}Ent(D^v)
$$

 

信息增益描述了一个特征带来的信息量的多少。在决策树分类问题中,信息增益就是决策树在进行属性选择划分前和划分后的信息差值。典型的决策树算法ID3就是基于信息增益来挑选每一节点分支用于划分的属性(特征)的。

但是信息增益有一个问题,它偏向取值较多的特征。原因是,当特征的取值较多时,根据此特征划分更容易得到纯度更高的子集,因此划分之后的熵更低,由于划分前的熵是一定的。因此信息增益更大,因此信息增益比较偏向取值较多的特征。

  • 信息增益率,相比信息增益,多了一个衡量本身属性的分散程度的部分作为分母。

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

 

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

 

启发式:先从候选划分属性中找出信息增益高干平均水平的,再从中选取增益率最高的。

  • 基尼系数 ,来表示数据集的不纯度。基尼指数越大,表示数据集越不纯。

$$
Gini(D) = \sum_{k=1}^{|y|}\sum_{k’\not=k}p_kp_{k’} = 1-\sum_{k=1}^{|y|}p_k^2
$$

 

Gini(D) 越小,数据集 D 的纯度越高。

3.算法描述

算法流程

决策树学习通常包括3个步骤:特征选择、决策树的生成和决策树的修剪。

这里使用ID3算法做一个简单的实例。

贷款申请样本数据表


ID 年龄 有工作 有自己的房子 信贷情况 类别
1 青年 一般
2 青年
3 青年
4 青年 一般
5 青年 一般
6 中年 一般
7 中年
8 中年
9 中年 非常好
10 中年 非常好
11 老年 非常好
12 老年
13 老年
14 老年 非常好
15 老年 一般

在编写代码之前,我们先对数据集进行属性标注。不对数据集进行属性标注也可以。

  • 年龄:0代表青年,1代表中年,2代表老年;

  • 有工作:0代表否,1代表是;

  • 有自己的房子:0代表否,1代表是;

  • 信贷情况:0代表一般,1代表好,2代表非常好;

  • 类别(是否给贷款):no代表否,yes代表是。

核心代码

from math import log
import operator
import pickle
import json
import pandas as pd

def calcShannonEnt(dataSet):
    # 统计数据数量
    numEntries = len(dataSet)
    # 存储每个label出现次数
    label_counts = {}
    # 统计label出现次数
    for featVec in dataSet:
        current_label = featVec[-1]
        if current_label not in label_counts:  # 提取label信息
            label_counts[current_label] = 0  # 如果label未在dict中则加入
        label_counts[current_label] += 1  # label计数
    shannon_ent = 0  # 经验熵
    # 计算经验熵
    for key in label_counts:
        prob = float(label_counts[key]) / numEntries
        shannon_ent -= prob * log(prob, 2)
    return shannon_ent
def calcFeaturesEnt(dataSet,i):
    FeaturesEnt = 0
    numEntries = len(dataSet)
    dict = {}
    for key in [x[i] for x in dataSet]:         
        dict[key] = dict.get(key, 0) + 1
        
    for keys in dict:
        FeaturesEnt  += -(dict[keys]/numEntries)*log(dict[keys]/numEntries,2)
        
    return FeaturesEnt

def splitDataSet(data_set, axis, value):
    ret_dataset = []
    for feat_vec in data_set:
        if feat_vec[axis] == value:
            reduced_feat_vec = feat_vec[:axis]
            reduced_feat_vec.extend(feat_vec[axis + 1:])
            ret_dataset.append(reduced_feat_vec)
    return ret_dataset


def chooseBestFeatureToSplit(dataSet,算法类别):
    if 算法类别 == 'ID3':
        # 特征数量
        num_features = len(dataSet[0]) - 1
        # 计算数据香农熵
        base_entropy = calcShannonEnt(dataSet)
        # 信息增益
        best_info_gain = 0.0
        # 最优特征索引值
        best_feature = -1
        # 遍历所有特征
        for i in range(num_features):

            # 获取dataset第i个特征
            feat_list = [exampel[i] for exampel in dataSet]
            # 创建set集合,元素不可重合
            unique_val = set(feat_list)
            # 经验条件熵
            new_entropy = 0.0
            # 计算信息增益
            for value in unique_val:
                # sub_dataset划分后的子集
                sub_dataset = splitDataSet(dataSet, i, value)
                # 计算子集的概率
                prob = len(sub_dataset) / float(len(dataSet))
                # 计算经验条件熵
                new_entropy += prob * calcShannonEnt(sub_dataset)
            # 信息增益
            info_gain = base_entropy - new_entropy
            # 打印每个特征的信息增益
            print("第%d个特征的信息增益为%.3f" % (i, info_gain))
            # 计算信息增益
            if info_gain > best_info_gain:
                # 更新信息增益
                best_info_gain = info_gain
                # 记录信息增益最大的特征的索引值
                best_feature = i
        print("最优索引值:" + str(best_feature))
        print()
        return best_feature
    elif 算法类别 == 'C4.5':
        return chooseBestFeatureToSplit_1(dataSet)
    else:
        print('还没写好这个算法!')
        return 0

def chooseBestFeatureToSplit_1(dataSet):
    # 特征数量
    num_features = len(dataSet[0]) - 1
    # print(num_features)
    # 计算数据香农熵
    base_entropy = calcShannonEnt(dataSet)
    # 信息增益
    info_gain = 0.0
    # 信息增益比
    info_gain_rate = 0.0
    # 最优特征索引值
    best_feature = -1
    # 存储 信息增益 和 信息增益比
    info_gain_dict = {}
    info_gain_rate_dict = {}
    sum_info_gain = 0
    for i in range(num_features):
        # 获取dataset第i个特征
        feat_list = [exampel[i] for exampel in dataSet]

        # 创建set集合,元素不可重合
        unique_val = set(feat_list)

        # 经验条件熵
        new_entropy = 0.0

        # 计算信息增益
        for value in unique_val:
            # sub_dataset划分后的子集
            sub_dataset = splitDataSet(dataSet, i, value)
            # 计算子集的概率
            prob = len(sub_dataset) / float(len(dataSet))
            # 计算经验条件熵
            new_entropy += prob * calcShannonEnt(sub_dataset)
        # 信息增益
        info_gain = base_entropy - new_entropy
        sum_info_gain += info_gain
        info_gain_dict[i] = info_gain
        # 信息增益比
        info_gain_rate = info_gain/calcFeaturesEnt(dataSet,i)
        info_gain_rate_dict[i] = info_gain_rate
        # 打印每个特征的信息增益和增益比
        print("第%d个特征的信息增益为%.3f,信息增益比为%.3f" % (i, info_gain,info_gain_rate))
    info_gain_avg = sum_info_gain/num_features
    print('平均信息增益为',info_gain_avg)
    for i in range(num_features):
        if info_gain_dict[i] < info_gain_avg:
            del info_gain_rate_dict[i]
    best_feature =  max(info_gain_rate_dict,key=info_gain_rate_dict.get)
    print("最优索引值:" + str(best_feature))
    print()
    return best_feature

def majority_cnt(class_list):
    class_count = {}
    # 统计class_list中每个元素出现的次数
    for vote in class_list:
        if vote not in class_count:
            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 creat_tree(dataSet, labels, featLabels,算法类别):
    # 取分类标签(是否放贷:yes or no)
    class_list = [exampel[-1] for exampel in dataSet]
    # 如果类别完全相同则停止分类
    if class_list.count(class_list[0]) == len(class_list):
        return class_list[0]
    # 遍历完所有特征时返回出现次数最多的类标签
    if len(dataSet[0]) == 1:
        return majority_cnt(class_list)
    # 选择最优特征
    best_feature = chooseBestFeatureToSplit(dataSet,算法类别)
    # 最优特征的标签
    best_feature_label = labels[best_feature]
    # print(best_feature_label)
    featLabels.append(best_feature_label)
    # 根据最优特征的标签生成树
    my_tree = {best_feature_label: {}}
    # 删除已使用标签
    del(labels[best_feature])
    # 得到训练集中所有最优特征的属性值
    feat_value = [exampel[best_feature] for exampel in dataSet]
    # 去掉重复属性值
    unique_vls = set(feat_value)
    for value in unique_vls:
        my_tree[best_feature_label][value] = creat_tree(splitDataSet(dataSet, best_feature, value), labels, featLabels,算法类别)
    return my_tree


def get_num_leaves(my_tree):
    num_leaves = 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_leaves += get_num_leaves(second_dict[key])
        else:
            num_leaves += 1
    return num_leaves


def get_tree_depth(my_tree):
    max_depth = 0       # 初始化决策树深度
    firsr_str = next(iter(my_tree))     # python3中myTree.keys()返回的是dict_keys,不在是list,所以不能使用myTree.keys()[0]的方法获取结点属性,可以使用list(myTree.keys())[0]
    second_dict = my_tree[firsr_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 = 1
        if this_depth > max_depth:
            max_depth = this_depth      # 更新层数
    return max_depth


def classify(input_tree, feat_labels, test_vec):
    # 获取决策树节点
    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 storeTree(input_tree, filename):
    # 存储树
    with open(filename, 'wb') as fw:
        pickle.dump(input_tree, fw)

# 错误的
#     with open(filename, 'w') as fw:
#         temp = json.dumps(input_tree, indent=4,ensure_ascii=False)
#         fw.write(temp)


def grabTree(filename):
    # 读取树
    fr = open(filename, 'rb')
    return pickle.load(fr)

# 错误的
#     f = open(filename, 'r')
#     temp = json.loads(f.read())
#     return temp


if __name__ == "__main__":
    # 数据集
    dataSet = [[0, 0, 0, 0, 'no'],
               [0, 0, 0, 1, 'no'],
               [0, 1, 0, 1, 'yes'],
               [0, 1, 1, 0, 'yes'],
               [0, 0, 0, 0, 'no'],
               [1, 0, 0, 0, 'no'],
               [1, 0, 0, 1, 'no'],
               [1, 1, 1, 1, 'yes'],
               [1, 0, 1, 2, 'yes'],
               [1, 0, 1, 2, 'yes'],
               [2, 0, 1, 2, 'yes'],
               [2, 0, 1, 1, 'yes'],
               [2, 1, 0, 1, 'yes'],
               [2, 1, 0, 2, 'yes'],
               [2, 0, 0, 0, 'no']]
    # 分类属性
    labels = ['年龄', '有工作', '有自己的房子', '信贷情况']

    print(dataSet)
    print()
    print(calcShannonEnt(dataSet))
    print()

    featLabels = []
    myTree = creat_tree(dataSet, labels, featLabels,'C4.5')
    print('树的深度为',get_tree_depth(myTree))
    print('树的广度为',get_num_leaves(myTree))

    #测试数据
    testVec = [0, 1, 1, 1]
    result = classify(myTree, featLabels, testVec)


    if result == 'yes':
        print('放贷')
    if result == 'no':
        print('不放贷')

    # 存储树
    storeTree(myTree,'classifierStorage.txt')


    # 读取树
    myTree2 = grabTree('classifierStorage.txt')
    print(myTree2)
    print(json.dumps(myTree2, indent=4,ensure_ascii=False))

    testVec2 = [1, 0]
    result2 = classify(myTree2, featLabels, testVec)
    if result2 == 'yes':
        print('放贷')
    if result2 == 'no':
        print('不放贷')

参数解释

注释以及比较详细了

4.应用

可以用到一些分类问题。

实验

运行了上述代码。

结果分析

信息增益比作为特征选择的时候,比信息增益更加“公平”。

但是这里没什么区别,可以换数据集查看效果。

5.结论

算法一直在改进。

6.参考文献

THE END