★★★ 本文源自AlStudio社区精品项目，【点击此处】查看更多精品内容 >>>

前言：

你是否玩过二十个问题的游戏，游戏的规则很简单:参与游戏的一方在脑海里想某个事物，其他参与者向他提问题，只允许提20个问题，问题的答案也只能用对或错回答。问问题的人通过推断分解，逐步缩小待猜测事物的范围。决策树的工作原理与20个问题类似，用户输人一系列数据，然后给出游戏的答案。

我们经常使用决策树处理分类问题,近来的调查表明决策树也是最经常使用的数据挖掘算法。它之所以如此流行，一个很重要的原因就是使用者基本上不用了解机器学习算法，也不用深究它是如何工作的。

在进行决策树的正式讲解之前，我们先来思考一个生活中常见的小问题。

问题：周末是否看电影？

思考过程：

（1）今天是否是周末？如果不是就不去看电影，如果是就继续思考下一个问题。

（2）工作是否完成？如果还没有完成就不去看电影，如果已经完成就继续思考下一个问题。

（3）今天是晴天吗？如果不是晴天就不去看电影，如果是晴天就继续思考下一个问题。

（4）今天能不能在电影院找到好位置？如果不能就不去看电影，如果能就去看电影。

一、决策树的定义

• 决策树(Decision Tree)是从一组无次序、无规则，但有类别标号的样本集中推导出的、树形表示的分类规则。

• 一般的，一棵决策树包含一个根结点、若干个内部结点（中间结点）和若干个叶子结点。

• 树的叶子结点表示类别标号，即分类属性的取值，也可以说是决策结果；树的内部结点为条件属性，每个结点包含的样本集合根据属性测试结果被划分到子结点中；根结点包含样本全集。从树根到叶子结点的一条路径称为一条决策规则，它可以对未知数据进行分类或预测。每条有向边都用其出点的属性值标记，如“晴天”“多云”“雨天”是其出点“天气”属性的三种取值。

• 通常，一个属性有多少种取值，就从该结点引出多少条有向边，每一条边代表属性的一种取值。

• 树深度是树根到树叶的最大层数，通常作为决策树模型复杂度的一种度量。

几个小问题
思考：谁来作为根结点？为什么根结点是天气而不是湿度或者风力？

问题1：如何选择条件属性（内部结点）进行划分？

问题2：什么情况下可以选择结束划分？

一般而言，划分数据集的最大原则是：将无序的数据变得更加有序。

将原始数据集通过条件属性被划分为两个或两个以上的子集后，划分的各个子集更“纯”，即划分后的任意一个数据集里面的样本都尽可能地属于同一个类别。

那么，如何衡量集合的“纯”度呢？决策树算法采用了在划分数据集之前或之后使用信息论度量信息的内容。如何使用信息论来度量集合的纯度呢？决策树算法使用了信息熵这个度量指标来衡量集合的纯度。

二、熵和信息熵的相关概念

• 熵（Entropy）这个概念最早出现在热力学中。它的物理意思表示该体系的混乱程度。简单地说，如果该体系下的分子运动杂乱程度增加，则该体系的熵也随之增加。

• 在熵这个概念普及之后，1948年，信息论之父克劳德·艾尔伍德·香农提出了信息熵的概念，用来描述信息的混乱程度或者信息的不确定度。（据说香农的墓碑上只刻了信息熵的计算公式。）

2.1 信息熵的简单理解

熵（entropy）表示随机变量不确定性的度量，也就是熵越大，变量的不确定性就越大。设是一个有限值的离散随机变量，其概率分布为：

$$P（X=x_i）=p_i,i=1,2,\dots ,n$$

假设变量X的随机取值为 X = { x 1 , x 2 , . . . , x n } X=\{x_1,x_2,...,x_n\} X={x1​,x2​,...,xn​}，每一种取值的概率分别是 { p 1 , p 2 , p 3 , . . . p n } \{p_1,p_2,p_3,...p_n \} {p1​,p2​,p3​,...pn​}，则变量X 的熵为：
$$H(X)=-\sum _{i=1}^n{p}_{i}lo{g}_2^{p_i}$$

• 如果有4个球，1个颜色。
  则该颜色的球所占比例为1，可计算该集合的信息熵$=-1\ast lo{g}_2(1)=0$
• 如果有4个球，4个不同颜色。
  则每种颜色的球所占比例为1/4，可计算该集合的信息熵$=-4\ast 1/4\ast lo{g}_2(1/4)=2$
• 如果有8个球，8个不同颜色。
  则每种颜色的球所占比例为1/8，可计算该集合的信息熵$=-8\ast 1/8\ast lo{g}_2(1/8)=3$

可见，系统的熵最小为0，最大可以无穷。熵越小，说明集合的纯度越高。

2.2 条件熵

条件熵H（Y|X）表示在已知随机变量X条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵为：
$$H(Y|X)=\sum _{i=1}^n{p}_{i}H(Y|X=x_i),p_i=P(X=x_i)$$

2.3 经典的决策树算法

• Hunt算法：最早的决策树算法是由Hunt等人于1966年提出，Hunt算法是许多决策树算法的基础，包括ID3、C4.5和CART等。
• ID3：1979年由澳大利亚的计算机科学家罗斯·昆兰所发表。其他科学家也根据ID3算法相继提出了ID4和ID5等算法。
• C4.5：考虑到ID4等名已被占用，昆兰只好将1993年更新的ID3算法命名为C4.5算法。
• CART：Classification and Regression Tree，可解决分类和回归问题。

三、ID3算法

3.1 划分选择或划分标准——信息增益

• 集合S的信息熵计算（划分前的信息熵）

设有限个样本点集合S，分类属性为 C = { C 1 , C 2 , … , C k } C=\{C_1, C_2,…, C_k\} C={C1​,C2​,…,Ck​}，假设当前样本集合S中第i类（即Ci）样本所占的比例（或称其为概率）为$pi(i=1,2,...,k)$，则样本集S的信息熵为：
$$E(S)=-\sum _{i=1}^k{p}_{i}lo{g}_2^{p_i}$$

• 各个自己的信息熵之和（划分后的信息熵）
  假设条件属性A有V个可能的取值 { a 1 , a 2 , … , a v } \{a_1, a_2, …, a_v\} {a1​,a2​,…,av​}，若使用A来对样本集S进行划分，则会产生V个分支结点，即得到S的V个子集 { S 1 , S 2 , … , S v } \{S_1, S_2, …, S_v\} {S1​,S2​,…,Sv​}，其中，$S_i(i=1,2,...,v)$中包含了S中所有在属性a上取值为ai的样本。可根据上面给出的式子计算出 Si的信息熵，再考虑到不同分支结点所包含的样本数不同，给分支结点赋予权重$\frac{|S_i|}{|S|}$，即样本数越多的分支结点的影响越大，从而可得用属性A对样本集S进行划分后的信息熵。我把这个熵理解为所有子集的信息熵之和。

• 信息增益（划分前-划分后）
  为了测试条件属性A的效果，需要比较父结点与子结点之间的纯度差异，这种差异越大，则说明该测试条件越好，即该条件属性的分类能力越强，而信息增益(information gain)则是这种差异的判断标准。用条件属性A划分样本集合S所得的信息增益为：
  $$Gain(S,A)=E(S)-E(S,A)$$

一般而言，信息增益越大，则意味着使用属性A来进行划分所获得的“纯度提升”更大。因此，可采用信息增益来进行决策树的划分属性选择。

经过计算可得：

$Gain(S,A=”今天是否周末”)=E(S)-E(S,A=”今天是否周末”)=1-0.39=0.61$

$Gain(S,A=”今天心情如何？”)=E(S)-E(S,A=”今天心情如何？”)=1-0.2754=0.7246$

因为$0.61<0.7246$，所以选择“今天心情如何？”作为样本集S的划分特征。接下来，递归调用算法。

示例：

在编写代码之前，我们先对数据集进行属性标注。

• 年龄：0代表青年，1代表中年，2代表老年；
• 有工作：0代表否，1代表是；
• 有自己的房子：0代表否，1代表是；
• 信贷情况：0代表一般，1代表好，2代表非常好；
• 类别(是否给贷款)：no代表否，yes代表是。

# 数据集
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=['年龄','有工作','有自己的房子','信贷情况']

3.2 计算经验熵（香农熵）

$$P（X=x_i）=p_i,i=1,2,\dots ,n$$

$$H(X)=-\sum _{i=1}^{n}lo{g}_2{p}_i(若p_i=0,定义0log0=0)$$

# 计算经验熵（香农熵）
from math import log
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
print("输出结果为：",calcShannonEnt(dataSet))

输出结果为： 0.9709505944546686

3.3 计算信息增益

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

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):
    # 特征数量
    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
chooseBestFeatureToSplit(dataSet)

第0个特征的信息增益为0.083
第1个特征的信息增益为0.324
第2个特征的信息增益为0.420
第3个特征的信息增益为0.363
最优索引值：2






2

3.4 树的生成

import operator
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]
    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

creat_tree(dataSet, labels, featLabels)

第0个特征的信息增益为0.083
第1个特征的信息增益为0.324
第2个特征的信息增益为0.420
第3个特征的信息增益为0.363
最优索引值：2

第0个特征的信息增益为0.252
第1个特征的信息增益为0.918
第2个特征的信息增益为0.474
最优索引值：1






{'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}

3.5 树的深度和广度计算

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
my_tree = creat_tree(dataSet, labels, featLabels)
print('树的深度为:', get_tree_depth(my_tree))
print('树的广度为：', get_num_leaves(my_tree))

第0个特征的信息增益为0.083
第1个特征的信息增益为0.324
第2个特征的信息增益为0.420
第3个特征的信息增益为0.363
最优索引值：2

第0个特征的信息增益为0.252
第1个特征的信息增益为0.918
第2个特征的信息增益为0.474
最优索引值：1

树的深度为: 2
树的广度为： 3

3.6 未知数据的预测

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

# 测试
testVec = [0, 1, 1, 1]
my_tree = creat_tree(dataSet, labels, featLabels)
result = classify(my_tree, featLabels, testVec)

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

第0个特征的信息增益为0.083
第1个特征的信息增益为0.324
第2个特征的信息增益为0.420
第3个特征的信息增益为0.363
最优索引值：2

第0个特征的信息增益为0.252
第1个特征的信息增益为0.918
第2个特征的信息增益为0.474
最优索引值：1

放贷

3.7 树的存储与读取（以二进制形式存储）

import pickle
def storeTree(input_tree, filename):
    # 存储树
    with open(filename, 'wb') as fw:
        pickle.dump(input_tree, fw)


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

3.8 完整代码

from math import log
import operator
import pickle


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 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):
    # 特征数量
    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


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]
    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)


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


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, 0, 'yes'],
               [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)
    print(myTree)
    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)

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

[[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']]

0.9709505944546686

第0个特征的信息增益为0.083
第1个特征的信息增益为0.324
第2个特征的信息增益为0.420
第3个特征的信息增益为0.363
最优索引值：2

第0个特征的信息增益为0.252
第1个特征的信息增益为0.918
第2个特征的信息增益为0.474
最优索引值：1

{'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}
2
3
放贷
{'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}
放贷

3.9 ID3算法的优缺点

ID3算法根据信息增益来选择划分属性，该算法的主要优缺点有：

• 优点：

  • 模型简单
  • 分类速度快

• 缺点：

  • 没有剪枝策略，容易过拟合。
  • 只能处理离散属性数据。
  • 不能处理有缺失的数据。
  • 仅是局部最优的决策树：ID3采用贪心算法，结果非全局最优。
  • 偏好取值种类多的属性：ID3采用信息增益作为选择分裂属性的度量标准，但大量的研究分析与实际应用发现，信息增益偏向于选择属性值个数较多的属性，而属性取值个数较多的属性并不一定是最优或分类能力最强的属性。例如：以“生日”或“身份证号”作为划分属性。（信息增益很大，但过拟合，预测效果差）

四、C4.5算法

C4.5算法是对ID3的一个改进，它根据信息增益率来选择划分属性。

主要优点：C4.5 相对于 ID3 的缺点对应有以下改进方式：

• 引入悲观剪枝策略进行后剪枝；
• 引入信息增益率作为划分标准；
• 将连续特征离散化；
• 空值（缺失值）处理。

主要缺点：

• 剪枝策略可以再优化；
• 用的是多叉树，用二叉树效率更高；
• 只能用于分类
• 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

4.1 信息增益率

定义：设有限个样本点集合S，根据条件属性A划分S所得子集为 { S 1 , S 2 , … , S v } \{S_1,S_2,…,S_v\} {S1​,S2​,…,Sv​}，则定义A划分样本集S的信息增益率为：
$$GainRatio(S,A)=Gain(S,A)/IV(A)$$
其中，$Gain(S,A)$的计算公式见式 $Gain(S,A)=E(S)-E(S,A)$，IV(A)如下：
$$IV(A)=-\sum _{j=1}^v\frac{|S_j|}{|S|}lo{g}_2(\frac{|S_j|}{|S|})$$
称为属性A的“固有值”，属性A的取值数目越多，即v越大，则IV(A)的值通常会越大。

需注意的是，增益率准则对可取值数目较少的属性有所偏好。因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式[Quinlan,1993]：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

4.2 C4.5的剪枝

过拟合原因：
为了尽可能正确分类训练样本，节点的划分过程会不断重复直到不能再分，这样就可能对训练样本学习的“太好”了，把训练样本的一些特点当做所有数据都具有的一般性质，从而导致过拟合。

解决办法：通过剪枝处理去掉一些分支来降低过拟合的风险。

剪枝的基本策略有“预剪枝”（prepruning）和“后剪枝”（post-pruning）。

4.3 ID3和C4.5的结果比较

采用C4.5算法，经过计算，以87.5为分割点时信息增益最大。因此将湿度87.5及其以下数据标记为湿度“小”，反之标记为湿度“大”。

连续属性的离散化方法是否合理，直接影响C4.5生成的决策树质量以及所生成的分类规则质量。

五、CART算法

5.1 CART树

CART 树（分类回归树）分为分类树和回归树。顾名思义，分类树用于处理分类问题；回归树用来处理回归问题。我们知道分类和回归是机器学习领域两个重要的方向。分类问题输出特征向量对应的分类结果，回归问题输出特征向量对应的预测值。

分类树和 ID3、C4.5 决策树相似，都用来处理分类问题。不同之处是划分方法。分类树利用基尼指数进行二分。如图所示就是一个分类树。

回归树用来处理回归问题。回归将已知数据进行拟合，对于目标变量未知的数据可以预测目标变量的值。如图 所示就是一个回归树，其中 s 是切分点，x 是特征，y 是目标变量。可以看出图 2 利用切分点 s 将特征空间进行划分，y 是在划分单元上的输出值。回归树的关键是如何选择切分点、如何利用切分点划分数据集、如何预测 y 的取值。

5.2 划分选择或划分标准——Gini系数

• Gini系数又称为基尼系数或者基尼指数
• Gini系数的小故事：1905年，统计学家洛伦茨提出了洛伦茨曲线。为了用指数来更好的反映社会收入分配的平等状况，1912年，意大利经济学家基尼根据洛伦茨曲线计算出一个反映收入分配平等程度的指标，称为基尼系数G。
• 图中横轴是人口比例的累积分布，竖轴是财富比例的累积分布。

Gini系数的定义：

• CART算法采用Gini系数来衡量结点的不纯度，如果某个结点所包含的样本集均属于同一个类别，则该结点就是“纯”的，其Gini系数=0。
• 定义：设有限个样本点集合S，分类属性C={C1, C2,…, Ck}。假设当前样本集合S中第i类（即Ci）样本所占的比例（或称其为概率）为pi(i=1,2,…,k)，则衡量S纯度的基尼系数为：

• Gini系数越小，数据集S的纯度越高。

如果要使用属性A来划分数据集S，且划分为两部分（因为CART算法要求决策树为二叉树），则需要确定选择何种二元划分方式来构造分支。假设属性A有v个可能的取值 { a 1 , a 2 , … , a v } \{a_1, a_2, …, a_v\} {a1​,a2​,…,av​}，从中选择第$i$个值$a_i$作为划分标准，即该分支所对应的判别条件分别为$A=a_i,A\ne a_i$。根据这两个判别条件可将S划分为两个子集$S_1$和$S_2$，该划分所对应的基尼系数为：

5.3 Gini系数计算举例

5.4 CART算法的优缺点

• CART树是根据Gini系数来衡量结点的不纯度，选择产生最小Gini系数的特征作为划分属性。

• 主要优点：ID3 和 C4.5 虽然在对训练样本集的学习中可以尽可能多地挖掘信息，但是其生成的决策树分支、规模都比较大，CART 算法的二分法可以简化决策树的规模，提高生成决策树的效率。

• CART使用Gini系数作为变量的不纯度量，减少了大量的对数运算；

• CART包含的基本过程有分裂，剪枝和树选择。

  • 分裂：分裂过程是一个二叉递归划分过程，其输入和预测特征既可以是连续型的也可以是离散型的，CART没有停止准则，会一直生长下去；
  • 剪枝：采用“基于代价复杂度剪枝”方法进行剪枝，从最大树开始，每次选择训练数据熵对整体性能贡献最小的那个分裂结点作为下一个剪枝对象，直到只剩下根结点。CART 会产生一系列嵌套的剪枝树，从中选出一颗最优的决策树；
  • 树选择：用单独的测试集评估每棵剪枝树的预测性能（也可以用交叉验证）。

• CART在C4.5的基础上进行了很多提升，例如：

  • C4.5为多叉树，运算速度慢；CART为二叉树，运算速度快；
  • C4.5只能分类，CART既可以分类也可以回归；
  • CART采用代理测试来估计缺失值，而C4.5以不同概率划分到不同节点中；
  • CART采用“基于代价复杂度剪枝”方法进行剪枝，而C4.5采用悲观剪枝方法。

5.5 其他比较

（1）划分标准的差异：ID3使用信息增益偏向特征值多的特征；C4.5使用信息增益率克服信息增益的缺点，偏向于特征值小的特征；CART使用基尼指数克服C4.5需要求log的巨大计算量，偏向于特征值较多的特征。

（2）使用场景的差异：ID3和C4.5都只能用于分类问题，CART可以用于分类和回归问题；ID3和C4.5是多叉树，速度较慢，CART是二叉树，计算速度很快；

（3）样本数据的差异：ID3只能处理离散数据且缺失值敏感，C4.5和CART可以处理连续性数据且有多种方式处理缺失值；从样本量考虑的话，小样本建议C4.5、大样本建议CART。C4.5处理过程中需对数据集进行多次扫描排序，处理成本耗时较高，而CART本身是一种大样本的统计方法，小样本处理下泛化误差较大；

（4）样本特征的差异：ID3和C4.5层级之间只使用一次特征，CART可多次重复使用特征；

（5）剪枝策略的差异：ID3没有剪枝策略，C4.5是通过悲观剪枝策略来修正树的准确性，而 CART是通过代价复杂度剪枝。

5.6 连续值的处理

还是这张表格，C4.5采用了二分法来处理连续值。

• 步骤1：将训练集中的样本在连续属性A上的取值从小到大排序。假设训练样本集中属性A有v个不同的取值，按非递减方式排序结果记为 { a 1 ， a 2 ， … ， a v } \{a_1，a_2，…，a_v\} {a1​，a2​，…，av​}；
• 步骤2：按照顺序将两个相邻的平均值$a^{avg}=\frac{a_i+a_{i+1}}{2}(i=1,2,...,v-1)$作为分割点，共获得v-1个分割点，且每个分割点都将样本集划分为两个子集，分别包含在A上取值$\le a^{avg}$和$>a^{avg}$的样本。
• 步骤3：计算v-1个分割点划分样本集的信息增益，选择具有最大信息增益的分割点$v^{\prime }$，将样本集划分为$A\le v^{\prime }$和$A>v^{\prime }$两个子集。（CART算法选择具有最小Gini系数的分割点）

5.7 CART分类树示例

数据集：

依旧为上一次用到的Titanic数据集，在此不做过多介绍分析了。

与上次的区别在于为了形成一个二叉树，所有特征离散化后在子叶点分类时只分为了1和非1两类

import csv
import operator
import copy
import numpy as np


# 0PassengerId：乘客的ID                               不重要
# 1Survived：乘客是否获救，Key：0=没获救，1=已获救
# 2Pclass：乘客船舱等级（1/2/3三个等级舱位）
# 3Name：乘客姓名                                       不重要
# 4Sex：性别
# 5Age：年龄
# 6SibSp：乘客在船上的兄弟姐妹/配偶数量
# 7Parch：乘客在船上的父母/孩子数量
# 8Ticket：船票号                                         不重要
# 9Fare：船票价
# 10Cabin：客舱号码                                        不重要
# 11Embarked：登船的港口                                   不重要


# 读入数据集
def loadDataset(filename):
    with open(filename, 'r') as f:
        lines = csv.reader(f)
        data_set = list(lines)
    if filename != 'titanic.csv':
        for i in range(len(data_set)):
            del(data_set[i][0])
    # 整理数据
    for i in range(len(data_set)):
        del(data_set[i][0])
        del(data_set[i][2])
        data_set[i][4] += data_set[i][5]
        del(data_set[i][5])
        del(data_set[i][5])
        del(data_set[i][6])
        del(data_set[i][-1])

    category = data_set[0]

    del (data_set[0])
    # 转换数据格式
    for data in data_set:
        data[0] = int(data[0])
        data[1] = int(data[1])
        if data[3] != '':
            data[3] = float(data[3])
        else:
            data[3] = None
        data[4] = float(data[4])
        data[5] = float(data[5])
    # 补全缺失值 转换记录方式 分类
    for data in data_set:
        if data[3] is None:
            data[3] = 28
        # male : 1, female : 0
        if data[2] == 'male':
            data[2] = 1
        else:
            data[2] = 0
        # age <25 为0, 25<=age<31为1，age>=31为2
        if data[3] < 60: # 但是测试得60分界准确率最高？？？！！！
            data[3] = 0
        else:
            data[3] = 1
        # sibsp&parcg以2为界限，小于为0，大于为1
        if data[4] < 2:
            data[4] = 0
        else:
            data[4] = 1
        # fare以64为界限
        if data[-1] < 64:
            data[-1] = 0
        else:
            data[-1] = 1
    return data_set, category

# 计算gini系数
def gini(data, i):

    num = len(data)
    label_counts = [0, 0, 0, 0]

    p_count = [0, 0, 0, 0]

    gini_count = [0, 0, 0, 0]

    for d in data:
        label_counts[d[i]] += 1

    for l in range(len(label_counts)):
        for d in data:
            if label_counts[l] != 0 and d[0] == 1 and d[i] == l:
                p_count[l] += 1

    print(label_counts)
    print(p_count)

    for l in range(len(label_counts)):
        if label_counts[l] != 0:
            gini_count[l] = 2*(p_count[l]/label_counts[l])*(1 - p_count[l]/label_counts[l])

    gini_p = 0
    for l in range(len(gini_count)):
        gini_p += (label_counts[l]/num)*gini_count[l]

    print(gini_p)

    return gini_p

# 取得节点划分的属性
def get_best_feature(data, category):
    if len(category) == 2:
        return 1, category[1]

    feature_num = len(category) - 1
    data_num = len(data)

    feature_gini = []

    for i in range(1, feature_num+1):
        feature_gini.append(gini(data, i))

    min = 0

    for i in range(len(feature_gini)):
        if feature_gini[i] < feature_gini[min]:
            min = i

    print(feature_gini)
    print(category)
    print(min+1)
    print(category[min+1])

    return min+1, category[min + 1]

# 树的生成
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]


class Node(object):
    def __init__(self, item):
        self.name = item
        self.lchild = None
        self.rchild = None

# 树的生成
def creat_tree(data, labels, feature_labels=[]):
# 三种结束情况
    # 取分类标签(survivor or death)
    class_list = [exampel[0] for exampel in data]

    if class_list == []:
        return Node(0)
    # 如果类别完全相同则停止分类
    if class_list.count(class_list[0]) == len(class_list):
        return Node(class_list[0])
    # 遍历完所有特征时返回出现次数最多的类标签
    if len(data[0]) == 1:
        return Node(majority_cnt(class_list))

    # 最优特征的标签
    best_feature_num, best_feature_label = get_best_feature(data, labels)

    feature_labels.append(best_feature_label)

    node = Node(best_feature_label)

    ldata = []
    rdata = []

    for d in data:
        if d[best_feature_num] == 1:
            del(d[best_feature_num])
            ldata.append(d)
        else:
            del(d[best_feature_num])
            rdata.append(d)

    labels2 = copy.deepcopy(labels)
    del(labels2[best_feature_num])

    tree = node
    tree.lchild = creat_tree(ldata, labels2, feature_labels)
    tree.rchild = creat_tree(rdata, labels2, feature_labels)

    return tree

# 树的遍历
def breadth_travel(tree):
    """广度遍历"""
    queue = [tree]
    while queue:
        cur_node = queue.pop(0)
        print(cur_node.name, end=" ")
        if cur_node.lchild is not None:
            queue.append(cur_node.lchild)
        if cur_node.rchild is not None:
            queue.append(cur_node.rchild)
    print()

# 预测
def prediction(t_tree, test, labels):
    result = []
    for data in test:
        l = copy.deepcopy(labels)
        tree = t_tree
        for i in range(len(labels)):
            if tree.name == 1 or tree.name == 0:
                result.append(tree.name)
                break
            if len(data) == 1:
                result.append(0)
                break
            j = 1
            while j < len(data)-1:
                if tree.name == l[j]:
                    break
                j += 1

            if data[j] == 1:
                tree = tree.lchild
            else:
                tree = tree.rchild
            del(l[j])
            del(data[j])
    return result


if __name__ == "__main__":

    test_set, category = loadDataset('titanic_test.csv')
    train_set, category = loadDataset('titanic_train.csv')

    print(category)
    print(train_set)
    print()
    print(test_set)


    my_tree = creat_tree(train_set, category)
    print(my_tree)
    breadth_travel(my_tree)
    print(category)
    print(test_set)

    test = copy.deepcopy(test_set)

    result = prediction(my_tree, test_set, category)
    print(len(test_set))

    print(result)

    counts = 0

    for i in range(len(test_set)):
        if test_set[i][0] == result[i]:
            counts += 1

    print(counts)
    accurancy = counts/len(test_set)  # 计算准确率
    print(accurancy)

5.8 CART回归树示例

原理分析

CART回归树预测回归连续型数据，假设X与Y分别是输入和输出变量，并且Y是连续变量。在训练数据集所在的输入空间中，递归的将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树。

选择最优切分变量j与切分点s：遍历变量j，对规定的切分变量j扫描切分点s，选择使下式得到最小值时的(j,s)对。其中Rm是被划分的输入空间，cm是空间Rm对应的固定输出值。

用选定的(j,s)对，划分区域并决定相应的输出值

继续对两个子区域调用上述步骤，将输入空间划分为M个区域R1,R2,…,Rm，生成决策树。

当输入空间划分确定时，可以用平方误差来表示回归树对于训练数据的预测方法，用平方误差最小的准则求解每个单元上的最优输出值。

数据集
此次使用forestfires的数据集，共有12列特征

# 1. Montesinho公园地图内的X-x轴空间坐标：1到9
# 2. Montesinho公园地图内的 Y-y轴空间坐标：2到9
# 3.每年的月份-月：“ jan”到“ dec'
# 4.每天-星期几：从“周一”到“星期日”
# 5.FFMC
# - FWI系统中的FFMC指数：18.7至96.20 6. DMC-FWI系统中的DMC指数：1.1至291.3 7. DC- FWI系统的DC指数：7.9至860.6
# 8. ISI-FWI系统的ISI指数：0.0至56.10
# 9. temp- 摄氏温度：2.2至33.30
# 10. RH-相对湿度（％）：15.0至100
# 11。风-以km / h为单位的风速：0.40至9.40
# 12.雨量-外部雨量，单位为mm / m2：0.0到6.4
# 13.面积-森林的燃烧面积（以ha为单位）：0.00到1090.84
# （此输出变量非常偏向0.0，因此使用对数变换）

# 完整代码
import csv
import copy
import calendar
from math import log1p
from math import sqrt
from graphviz import Digraph



# 1. Montesinho公园地图内的X-x轴空间坐标：1到9
# 2. Montesinho公园地图内的 Y-y轴空间坐标：2到9
# 3.每年的月份-月：“ jan”到“ dec'
# 4.每天-星期几：从“周一”到“星期日”
# 5.FFMC
# - FWI系统中的FFMC指数：18.7至96.20 6. DMC-FWI系统中的DMC指数：1.1至291.3 7. DC- FWI系统的DC指数：7.9至860.6
# 8. ISI-FWI系统的ISI指数：0.0至56.10
# 9. temp- 摄氏温度：2.2至33.30
# 10. RH-相对湿度（％）：15.0至100
# 11。风-以km / h为单位的风速：0.40至9.40
# 12.雨量-外部雨量，单位为mm / m2：0.0到6.4
# 13.面积-森林的燃烧面积（以ha为单位）：0.00到1090.84
# （此输出变量非常偏向0.0，因此使用对数变换）

# 加载数据集
def loadDataset(filename):
    with open(filename, 'r') as f:
        lines = csv.reader(f)
        data_set = list(lines)
    for i in range(len(data_set)):
        del(data_set[i][0])
    # 整理数据
    for i in range(len(data_set)):
        del(data_set[i][3])

    category = data_set[0]

    del(data_set[0])

    for i in range(len(data_set)):
        for j in range(len(data_set[0])):
            if j == 2:
                data_set[i][j] = str.capitalize(data_set[i][j])
                data_set[i][j] = list(calendar.month_abbr).index(data_set[i][j])
            data_set[i][j] = float(data_set[i][j])
            if j == 11:
                data_set[i][j] = log1p(data_set[i][j]+1)

    return data_set, category

# area与特征值分离
def split_data(data):

    data_set = copy.deepcopy(data)

    data_mat = []
    label_mat = []
    for i in range(len(data_set)):
        label_mat.append(data_set[i][-1])
        del(data_set[i][-1])
        data_mat.append(data_set[i])

    print(data_mat)
    print(label_mat)

    return data_mat, label_mat

# 误差计算
def mse(data_set, split_value, result):
    left_num = 0
    left_sum = 0
    left_list = []
    right_num = 0
    right_sum = 0
    rigth_list = []

    for i in range(len(data_set)):
        if data_set[i] <= split_value:
            left_num += 1
            left_sum += result[i]
            left_list.append(result[i])
        else:
            right_num += 1
            right_sum += result[i]
            rigth_list.append(result[i])

    c1 = left_sum/left_num
    c2 = right_sum/right_num

    m = 0
    for i in range(len(left_list)):
        m += pow((left_list[i]-c1), 2)
    for i in range(len(rigth_list)):
        m += pow((rigth_list[i]-c2), 2)

    return m

# 划分节点的数据
def get_best_split_value(data, result):

    data_set = set(data)
    data_set = list(data_set)
    data.sort()
    length = len(data_set)
    if length == 1:
        return float("Inf"), float("Inf")
    print(data_set)
    split_value = []

    for i in range(length-1):
        split_value.append((data_set[i+1] + data_set[i])/2)

    # if len(split_value) == 2:
    #     return (split_value[0]+split_value[1])/2, mse(data, (split_value[0]+split_value[1])/2, result)

    m = []

    for i in range(len(split_value)):
        m.append(mse(data, split_value[i], result))

    min_mse = 0

    for i in range(len(m)):
        if m[i] < m[min_mse]:
            min_mse = i

    print(m)

    return split_value[min_mse], m[min_mse]

# 特征获取
def get_best_feature(data, category):
    length = len(category)-1

    data_set, result = split_data(data)

    feature_mse = []

    split_feature_value = []

    feature_values = []

    for i in range(length):
        feature_mse.append(0)
        split_feature_value.append(0)

        feature_values.append([])
        for j in range(len(data_set)):
            feature_values[i].append(data_set[j][i])

    for i in range(length):
         split_feature_value[i], feature_mse[i] = get_best_split_value(feature_values[i], result)

    min_f = 0
    for i in range(length):
        if feature_mse[i] < feature_mse[min_f]:
            min_f = i

    print(feature_mse)

    return min_f, split_feature_value[min_f]

# 树结点的创建（链表式）
class Node(object):
    def __init__(self, category, item):
        self.name = category
        self.elem = item
        self.lchild = None
        self.rchild = None

# 叶子节点回归值的计算
def leaf_value(data):
    sum = 0
    for i in range(len(data)):
        sum += data[i][-1]

    return sum/len(data)



# 生成树
def creat_tree(data, labels, feature_labels=[]):
# 结束情况
    if len(labels) == 1:
        return Node('result', leaf_value(data))

    if len(data) < 0.05*len(train_set):
        return Node('result', leaf_value(data))


    # 最优特征的标签
    best_feature_num, best_feature_value = get_best_feature(data, labels)

    feature_labels.append(labels[best_feature_num])

    node = Node(labels[best_feature_num], best_feature_value)

    ldata = []
    rdata = []

    for d in data:
        if d[best_feature_num] <= best_feature_value:
            del(d[best_feature_num])
            ldata.append(d)
        else:
            del(d[best_feature_num])
            rdata.append(d)

    labels2 = copy.deepcopy(labels)
    del(labels2[best_feature_num])

    tree = node
    tree.lchild = creat_tree(ldata, labels2, feature_labels)
    tree.rchild = creat_tree(rdata, labels2, feature_labels)

    return tree

# 树的遍历
def breadth_travel(tree):
    """广度遍历"""
    queue = [tree]
    while queue:
        cur_node = queue.pop(0)
        print(cur_node.name, end=" ")
        print(cur_node.elem, end=" ")
        if cur_node.lchild is not None:
            queue.append(cur_node.lchild)
        if cur_node.rchild is not None:
            queue.append(cur_node.rchild)
    print()

# 预测
def prediction(t_tree, test, labels):
    result = []
    test_mat, x = split_data(test)
    for data in test_mat:
        l = copy.deepcopy(labels)
        tree = t_tree
        for i in range(len(labels)):
            if tree.name == "result":
                result.append(tree.elem)
                break
            j = 0
            while j:
                if tree.name == l[j]:
                    break
                j += 1

            if data[j] <= tree.elem:
                tree = tree.lchild
            else:
                tree = tree.rchild
            del(l[j])
            del(data[j])
    return result

# “链表”式树转化为字典树
def tree_to_dict(tree, tree_dict):
    if tree.lchild == None and tree.rchild == None:
        tree_dict[tree.name+str(tree.elem)] = str(tree.elem)
        return tree_dict[tree.name+str(tree.elem)]

    tree_dict[tree.name+str(tree.elem)] = {}

    if tree.lchild != None:
        tree_to_dict(tree.lchild, tree_dict[tree.name+str(tree.elem)])
    if tree.rchild != None:
        tree_to_dict(tree.rchild, tree_dict[tree.name+str(tree.elem)])

    return tree_dict

# 树的可视化
def plot_model(tree, name):
    g = Digraph("G", filename=name, format='png', strict=False)
    first_label = list(tree.keys())[0]
    g.node("0", first_label)
    _sub_plot(g, tree, "0")
    g.view()


root = "0"


def _sub_plot(g, tree, inc):
    global root

    first_label = list(tree.keys())[0]
    ts = tree[first_label]

    if type(ts).__name__ != 'dict':
        root = str(int(root) + 1)
        g.node(root, str(tree[first_label]))
        g.edge(inc, root, str(ts))
        return

    for i in ts.keys():
        if isinstance(tree[first_label][i], dict):
            root = str(int(root) + 1)
            g.node(root, list(tree[first_label][i].keys())[0])
            g.edge(inc, root, str(i))
            _sub_plot(g, tree[first_label][i], root)
        else:
            root = str(int(root) + 1)
            g.node(root, str(tree[first_label][i]))
            g.edge(inc, root, str(i))


if __name__ == "__main__":
    test_set, category = loadDataset('forestfires_test.csv')
    train_set, category = loadDataset('forestfires_train.csv')


    print(category)
    print(train_set)
    print(test_set)

    # a, b = get_best_feature(train_set, category)
    # print(a)
    # print(b)
    

    my_tree = creat_tree(train_set, category)

    breadth_travel(my_tree)

    result = prediction(my_tree, test_set, category)

    sme = 0
    for i in range(len(result)):
        sme += pow(abs(result[i]-test_set[i][-1]), 2)

    print(sqrt(sme/len(result)))

    tree_dict = {}

    tree_dict = tree_to_dict(my_tree, tree_dict)

    print(tree_dict)

    plot_model(tree_dict, "forestfires.gv")

六、Python实现案例

案例1：鸢尾花Iris数据集

莺尾花数据集介绍：

鸢尾花数据集是一类多重变量分析的数据集，常用于分类实验。该数据集由150个数据样本组成，分为3类，每类50个数据，每个数据包含4个属性。可通过花萼长度，花萼宽度，花瓣长度，花瓣宽度4个属性预测鸢尾花卉属于（Setosa，Versicolour，Virginica）三个种类中的哪一类。其它比较流行的数据集还有Adult,Wine,Car Evaluation等。

鸢尾花数据集的特点是包含了4个属性：sepal.length（花萼长度），sepal.width（花萼宽度）和petal.length（花瓣长度）和petal.width（花瓣宽度）。这些属性可以用来预测鸢尾花卉属于哪个种类。此外，鸢尾花数据集还包含了3个线性可分离的特征：sepal.Length-Petal.Width（花萼长度-花瓣宽度），sepal.Length-Sepal.Width（花萼长度-花萼宽度）和sepal.Length-Petal.Length（花萼长度-花瓣长度）。

鸢尾花数据集常用于分类实验，因为它可以提供多个有用的特征来区分不同的种类。在使用鸢尾花数据集时，需要注意的是，该数据集只包含了3个种类，因此如果需要进行更复杂的分类任务，可能需要使用其他数据集或方法。

代码实现：

import numpy as np
from sklearn.tree import DecisionTreeClassifier
import sklearn.datasets as datasets
from sklearn.model_selection import train_test_split

iris=datasets.load_iris()
print(iris['target_names'])
X=iris['data']
y=iris['target']

X_train,X_test,y_train,y_test=train_test_split(X,y,test_size=0.2,random_state=0)
clf=DecisionTreeClassifier(max_depth=1)
clf.fit(X_train,y_train) #训练模型
print(clf.score(X_test,y_test))#预测模型,等价于下面两行代码
#y_t=clf.predict(X_test)
#print((y_t==y_test).mean())
X_new=np.array([[0.6,0.34,0.5,0.55]])
y_new=clf.predict(X_new)#预测新样本
print(iris['target_names'][y_new])

['setosa' 'versicolor' 'virginica']
0.5666666666666667
['setosa']

上述我们使用clf=DecisionTreeClassifier()函数的时候设置参数max_depth=1，其实DecisionTreeClassifier是一个用于构建决策树模型的Python库。以下是该函数的参数解释：

• criterion（标准化度量）：指定使用哪种标准化度量方法，可选值包括“entropy”（信息熵）和“gini”（基尼系数）。默认值为“entropy”。
• min_samples_leaf（叶子节点最小样本数）：如果一个叶子节点的样本数小于这个值，则将其视为噪声点，并在训练集中删除。默认值为3。
• max_depth（最大深度）：指定决策树中的最大深度。深度越大，越容易过拟合，推荐树的深度为5-20之间。默认值为None。
• random_state（随机种子）：用于生成均匀分布的随机数。如果不提供，则会使用当前时间作为随机种子。默认值为None。

如果我们将上述函数的参数设置为2，即clf=DecisionTreeClassifier(max_depth=2)，那么预测的精度就会发生改变，这是由于树的深度越大，越容易发生过拟合。也就是我们上面所说的，下面我们看下设置为参数设置为2的时候的精度变化。

import numpy as np
from sklearn.tree import DecisionTreeClassifier
import sklearn.datasets as datasets
from sklearn.model_selection import train_test_split

iris=datasets.load_iris()
print(iris['target_names'])
X=iris['data']
y=iris['target']

X_train,X_test,y_train,y_test=train_test_split(X,y,test_size=0.2,random_state=0)
clf=DecisionTreeClassifier(max_depth=2)
clf.fit(X_train,y_train) #训练模型
print(clf.score(X_test,y_test))#预测模型,等价于下面两行代码
#y_t=clf.predict(X_test)
#print((y_t==y_test).mean())
X_new=np.array([[0.6,0.34,0.5,0.55]])
y_new=clf.predict(X_new)#预测新样本
print(iris['target_names'][y_new])

['setosa' 'versicolor' 'virginica']
0.9666666666666667
['setosa']

如果我们继续实验下去会发现，当参数设置为5的时候，那么预测的score就是高达1，那么很有可能就会发生过拟合。所以我们预测的时候参数要设置到合适的值。

七、决策树的可视化

好奇：决策树在每一层都做了哪些事情？

在学习使用scikitlearn的决策树方法时候，会产生一个dot格式的文件来表示最终的结果。我想把这个dot树可视化，也即可视化决策树的工作过程。

• 可视化方法1：安装graphviz库。不同于一般的Python包，graphviz需要额外下载可执行文件，并配置环境变量。
• 可视化方法2：安装pydotplus包也可以。

【代码展示】在prompt里，输入pip install pydotplus。联网安装pydotplus，可视化决策树的工作过程。

# 安装所需模块
!pip install graphviz
!pip install pydotplus #pydotplus 绘制决策树

#剪枝案例
# -*- coding: utf-8 -*-
from sklearn.datasets import load_iris
from sklearn import tree
import numpy as np
import pydotplus

#from sklearn.externals.six import StringIO
from six import StringIO #StringIO模块实现在内存缓冲区中读写数据
import pydotplus
#----------------数据准备----------------------------
iris = load_iris()                          # 加载数据
X = iris.data
y = iris.target
#---------------模型训练---------------------------------
clf = tree.DecisionTreeClassifier(min_samples_split=10,ccp_alpha=0)        
clf = clf.fit(X, y)     
#-------计算ccp路径-----------------------
pruning_path = clf.cost_complexity_pruning_path(X, y)
#-------打印结果---------------------------    
print("\n====CCP路径=================")
print("ccp_alphas:",pruning_path['ccp_alphas'])
print("impurities:",pruning_path['impurities']) 

====CCP路径=================
ccp_alphas: [0.         0.00415459 0.01305556 0.02966049 0.25979603 0.33333333]
impurities: [0.02666667 0.03082126 0.04387681 0.07353731 0.33333333 0.66666667]

对以上输出的解释如下：
0<α<0.00415时，树的不纯度为 0.02666，0.00415< α<0.01305时，树的不纯度为 0.03082，0.01305<α<0.02966时，树的不纯度为 0.04387，…其中，树的不纯度指的是损失函数的前部分， 也即所有叶子的不纯度（gini或者熵）加权和。

ccp_path只提供树的不纯度，如果还需要alpha对应的其它信息，则可以将alpha代入模型中训练，从训练好的模型中获取。

根据树的质量，选定alpha进行剪树. 我们根据业务实际情况，选择一个可以接受的树不纯度，找到对应的alpha,例如，我们可接受的树不纯度为0.0735，

则alpha可设为0.1(在0.02966与0.25979之间）对模型重新以参数ccp_alpha=0.1进行训练，即可得到剪枝后的决策树。

#------设置alpha对树后剪枝-----------------------
clf = tree.DecisionTreeClassifier(min_samples_split=10,random_state=0,ccp_alpha=0.1)        
clf = clf.fit(X, y) 
#------自行计算树纯度以验证-----------------------
is_leaf =clf.tree_.children_left ==-1
tree_impurities = (clf.tree_.impurity[is_leaf]* clf.tree_.n_node_samples[is_leaf]/len(y)).sum()
#-------打印结果--------------------------- 
print("\n==设置alpha=0.1剪枝后的树纯度：=========\n",tree_impurities)

==设置alpha=0.1剪枝后的树纯度：=========
 0.0735373054213634

dot_data = StringIO()
print(type(dot_data))
file_name="/home/aistudio/work/iris2.dot"  # 路径自己设置
tree.export_graphviz(clf, out_file=file_name,
                         feature_names=iris.feature_names,
                         class_names=iris.target_names, #filled：布尔，默认=假。当设置为 True 时，绘制节点以指示分类的多数类、回归值的极值或 multi-output 的节点纯度。
                         filled=True, rounded=True, #rounded：布尔，默认=假，当设置为 True 时，绘制圆角节点框。
                         special_characters=True)  #此函数生成决策树的 GraphViz 表示，然后将其写入 out_file
with open(file_name)as f:
    dot_graph=(type(dot_data))(f.read())
    graph = pydotplus.graph_from_dot_data(dot_graph.getvalue())#决策树可视化
    print(dot_graph)
    graph.write_pdf('/home/aistudio/work/iris2.pdf')  # # 路径自己设置

<class '_io.StringIO'>
<_io.StringIO object at 0x7f3d5a6f9910>

这时候我们就可以去对应的/home/aistudio/work/iris2.pdf路径下打开我们所绘制的可视化pdf文件，进行查看。

总结

• 决策树是机器学习中非常重要的一门算法，我们进行机器学习需熟练掌握并将其融会贯通进行使用。
• 学习决策树，从ID3算法开始学起，直到CART算法，CART算法与ID3算法和C4.5算法的关键区别在于，CART的树结构是二叉树并且可以同时运用于分类和回归，而ID3和C4.5是多叉树并且只能运用于分类。
• 进行决策树的可视化可以帮助我们更加清楚的了解决策树的分类过程。