完成 ID3、C4.5、CART 决策树构建，阈值限制，连续属性划分，剪枝，缺省值处理。

什么是决策树

直观理解：通过自顶向下的方式，构造一棵数据不断被纯化的树，可用来分类、回归，有监督学习的一种。

构造过程：递归构造

核心问题：划分的选择（决策依据）

来自SGUWOOM 的博客 `

决策树学习采用的是自顶向下的递归方法，其基本思想是以信息熵为度量构造一颗熵值下降最快的树，到叶子节点处，熵值为 \(0\)。其具有可读性、分类速度快的优点，是一种有监督学习。最早提及决策树思想的是 Quinlan 在 1986 年提出的 ID3 算法和 1993 年提出的 C4.5 算法，以及 Breiman 等人在 1984 年提出的 CART 算法

随着划分不断进行，决策树的分支节点应趋向于属于同一类别，样本集合属于同一类别的程度用“纯度”（purity）表示。

基本概念

信息熵

“信息熵”（Information entropy），衡量样本集合纯度最常用的一种方法，公式：

\[Ent(D) = - \sum_{k=1}^{ |y|} p_k \log_2 p_k\]

其中\(p_k\) 为第\(k\) 类样本占该样本集的比例。

甚至可以联想热学熵，熵值越低应该越好（纯度越高），从公式易知熵值范围应是\([ 0 , \log_2 |D|]\)。

信息增益

对于该集合的一种划分（实践上我们尝试通过对某一列属性是否相同，即该属性上的等价关系，对集合进行划分），我们会产生一个商集。

如西瓜书上所假设，离散属性\(a\)有\(V\)个可能的取值\(\{ a^1,a^2, \cdots , a^n \}\)，用该属性对样本集进行划分，会产生\(V\)个分支节点，属性值与分支节点对应关系为\(a^v \rightarrow D^v\)，对这\(V\)个分支节点分别计算信息熵并赋予权重\(\frac{ |D^v| }{ | D | }\)，与原样本集合的信息熵作比较我们就可以得出信息增益，公式：

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

ID3 决策树学习算法采用信息增益为准则决定划分属性。

信息增益率

对于信息增益，我们很容易发现其偏好属性值可取值较多的属性有偏好（因为分后各分支节点样本都趋近于完全纯和），在一些数据集中会丧失泛化能力。

信息增益率在信息增益的基础上，增加了“固有值”（Intrinsic Value）的概念，可取值越多的属性，其固有值 IV 常常会越大，计算增益率的公式为：

\[Gain\_radio(D,a) = \frac{Gain(D,a)}{IV(a)}\]

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

C4.5 决策树算法采用信息增益率来选择最优的划分属性，不过由于增益率准则对可取数目较少的属性有所偏好反过来了，因此，C4.5 算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式算法，先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

基尼指数

CART 决策树使用“基尼指数”来选择划分属性，公式：

\[Gini(D) = \sum_{ k=1 }^{ |y| } \sum_{ k' k } p_k p_{k'}\]

概率公式，更常用的是下面：

\[Gini(D) = 1- \sum_{k=1}^{|y|} p_k^2\]

通过某一属性进行划分，则属性\(a\)的基尼指数定义为：

\[Gini\_index(D,a) = \sum_{v=1}^{V} \frac{ |D^v| }{ | D | } Gini(D^v)\]

我们选择所有属性中使得划分后基尼指数最小的属性作为最优划分属性。

需要说明的是 CART 决策树是从属性集中抽取两个相互对立的集合（即\(V=2\)），离散型属性应为等于和不等于，连续型属性应是小于和大于等于，利用上式计算\(Gini\_index\)，对每个可能可能取得值均取一遍，选取最小得\(Gini\_index\)值作为该属性的代表值。

程序流程图

tree1

整体代码

#!/usr/bin/env python
# coding: utf-8

# In[1]:


from math import log
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import matplotlib
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
matplotlib.rcParams['font.family'] = 'SimHei'


# In[99]:


class DecisionTree:
    """
    DecisionTree 决策树类
    详情见API文档

    """

    label_name = []
    raw_data = []
    raw_label = []
    train_data = []
    train_label = []
    test_data = []
    test_label = []
    tree = []

    def __init__(self, input_data, input_label, input_name):
        """
        __init__ 构造函数初始化决策树对象

        :param self: 类方法自带
        :param input_data: 输入数据集
        :param input_label: 输入标签集
        :param input_name: 输入属性名称
        """
        self.raw_data = np.array(input_data, dtype=object)
        self.raw_label = np.array(input_label, dtype=object)
        self.label_name = np.array(input_name, dtype=object)

    def loadTrainData(self, type=0):
        """
        loadTrainData 构建训练集

        :param self: 类方法自带
        :param type: 加载方法
        """
        if(type == 0):
            self.train_data = np.array(self.raw_data, dtype=object)
            self.train_label = np.array(self.raw_label, dtype=object)

    def calcGini(self, labels):
        """
        calcGini 计算给定数据集的基尼指数Gini(D)

        :param self: 类方法自带
        :param labels: 输入的标签集或属性集
        :return: 计算的基尼指数
        """
        label_values = set(labels)
        ans = 1.0

        for value in label_values:
            p = labels[labels == value].size / labels.size
            ans -= p**2
        return ans

    def calcEntropy(self, labels):
        """
        calcEntropy 计算给定数据集的经验熵Ent(D)

        :param self: 类方法自带
        :param labels: 输入的标签集或属性集
        :return: 计算的Ent熵
        """
        label_values = set(labels)
        ans = 0.0
        for value in label_values:
            p = labels[labels == value].size / labels.size
            ans -= p*log(p, 2)
        return ans

    def calcSumEnt(self, data, labels):
        """
        calcSumEnt 计算给定数据集的经验熵Ent(D)

        :param self: 类方法自带
        :param data: 输入的数据集
        :param labels: 输入的标签集
        :return: sum_ent: 计算的Ent熵
        :return: max_point: 对于连续型属性 最佳分割点
        """
        features = np.array(data, dtype=object)
        labels = np.array(labels, dtype=object)

        feature_values = list(set(features))

        num = features.size
        max_point = -float('inf')
        sum_ent = 0.0
        if type(features[0]) != float and type(features[0]) != int:
            # 对于离散值属性，分类方向确定，计算Gain即可
            for value in feature_values:
                p = features[features == value].size/num
                sum_ent += p*self.calcEntropy(labels[features == value])
        else:
            # 对于连续性属性，分类方向不确定，还需要多做一次分割点确认
            sum_ent = float('inf')
            # 排序
            feature_values.sort()
            cnt = len(feature_values)
            # 寻找最合适的划分中点
            for j in range(cnt-1):
                point_ent = 0
                point = float(feature_values[j] + feature_values[j+1])/2
                # 划分成小于和大于等于两个子集
                p1 = features[features < point].size / num
                p2 = features[features >= point].size / num
                point_ent += p1*self.calcEntropy(labels[features < point])
                point_ent += p2*self.calcEntropy(labels[features >= point])
                if point_ent < sum_ent:
                    sum_ent = point_ent
                    max_point = point
        return sum_ent, max_point

    def calcInfoGain(self, data, labels):
        """
        calcInfoGain 计算指定数据集选定属性的信息熵增益（ID3）

        :param self: 类方法自带
        :param data: 输入的数据集（选定指定属性）
        :param labels: 输入的标签集或属性集
        :return: 信息熵增益
        """
        sum_ent, max_point = self.calcSumEnt(data, labels)
        return self.calcEntropy(labels) - sum_ent, max_point

    def calcInfoGainRatio(self, data, labels):
        """
        calcInfoGainRatio 计算指定数据集选定属性的信息熵增益率（C4.5）

        :param self: 类方法自带
        :param data: 输入的数据集（选定指定属性）
        :param labels: 输入的标签集或属性集
        :return: 信息熵增益率
        """
        iv = self.calcEntropy(data)
        if iv == 0:
            return 0, 0
        else:
            info_gain, max_point = self.calcInfoGain(data, labels)
            return info_gain/iv, max_point

    def calcInfoGini(self, data, labels):
        """
        calcInfoGini 计算指定数据集选定属性的基尼指数（CART）

        :param self: 类方法自带
        :param data: 输入的数据集（选定指定属性）
        :param labels: 输入的标签集或属性集
        :return: sum_gini: 指定属性的基尼指数和
        :return: 最佳分割点
        """

        features = np.array(data, dtype=object)
        labels = np.array(labels, dtype=object)
        feature_values = list(set(features))

        num = features.size
        max_point = -float('inf')
        best_gini = float('inf')
        best_value = ""

        if type(features[0]) != float and type(features[0]) != int:
            # 对于离散值属性，分类方向确定，计算Gain即可
            for value in feature_values:
                p1 = features[features == value].size / num
                p2 = features[features != value].size / num
                tmp_gini = p1 * \
                    self.calcGini(labels[features == value]) + \
                    p2*self.calcGini(labels[features != value])
                if tmp_gini < best_gini:
                    best_gini = tmp_gini
                    best_value = value
        else:
            # 对于连续性属性，分类方向不确定，还需要多做一次分割点确认
            best_gini = float('inf')
            # 排序
            feature_values.sort()
            cnt = len(feature_values)
            # 寻找最合适的划分中点
            for j in range(cnt-1):
                point_gini = 0
                point = float(feature_values[j] + feature_values[j+1])/2
                # 划分成小于和大于等于两个子集
                p1 = features[features < point].size / num
                p2 = features[features >= point].size / num
                point_gini += p1*self.calcGini(labels[features < point])
                point_gini += p2*self.calcGini(labels[features >= point])
                if point_gini < best_gini:
                    best_gini = point_gini
                    max_point = point

        return best_gini, best_value, max_point

    def chooseBest(self, data, labels, names, method='id3'):
        """
        chooseBest 选择最佳分割属性

        :param self: 类方法自带
        :param data: 当前数据集
        :param labels: 当前标签集合
        :param names: 当前数据集的属性名集合
        :param method: 信息增益计算方法（ID3/C4.5）
        :return: best_feature_index 最佳分割属性索引
        :return: best_feature_name: 最佳分割属性名
        :return: best_info_improve: 最佳分割后信息增益值
        :return: best_point: 对于连续值最佳分割点
        """
        data = np.array(data, dtype=object)
        labels = np.array(labels, dtype=object)
        names = np.array(names, dtype=object)
        feature_num = data.shape[1]

        # 筛选最优特征
        if method == 'id3' or method == 'c4.5':
            best_info_improve = -float('inf')
        elif method == 'cart':
            best_info_improve = float('inf')
        best_feature_index = -1
        best_point = -float('inf')
        best_value = ""

        for feature_index in range(feature_num):
            if method == 'id3':
                now_info_improve, now_point = self.calcInfoGain(
                    data[:, feature_index], labels)
                if now_info_improve > best_info_improve:
                    best_info_improve = now_info_improve
                    best_point = now_point
                    best_feature_index = feature_index

            elif method == 'c4.5':
                now_info_improve, now_point = self.calcInfoGainRatio(
                    data[:, feature_index], labels)
                if now_info_improve > best_info_improve:
                    best_info_improve = now_info_improve
                    best_point = now_point
                    best_feature_index = feature_index

            elif method == 'cart':
                now_info_improve, now_value, now_point = self.calcInfoGini(
                    data[:, feature_index], labels)
                if now_info_improve < best_info_improve:
                    best_info_improve = now_info_improve
                    best_point = now_point
                    best_feature_index = feature_index
                    best_value = now_value
        best_feature_name = names[best_feature_index]
        return best_feature_index, best_feature_name, best_value, best_info_improve, best_point

    def splitData(self, data, labels, names, feature_index, feature_name, cart_value, point, method):
        """
        splitData 根据最佳分割，讲数据集标签集划分为不同子集

        :param self: 类方法自带
        :param data: 当前数据集
        :param labels: 当前标签集合
        :param names: 当前数据集的属性名集合
        :param feature_index: 分割属性索引
        :param point: 对于连续属性的分割点
        :return: data_set: 不同属性对应的子数据集的集合
        :return: label_set: 不同属性对应的子标签集的集合
        :return: name_set: 子集属性名集合
        """
        data = np.array(data, dtype=object)
        labels = np.array(labels, dtype=object)
        names = np.array(names, dtype=object)

        # 取特征列预备向量运算
        features_col = data[:, feature_index]

        data_set = {}
        label_set = {}
        if method == 'id3' or method == 'c4.5':
            # 删除特征列
            data = np.delete(data, feature_index, 1)
            name_set = np.delete(names, feature_index)
            if(type(features_col[0]) != float and type(features_col[0] != int)):

                # 统计所有出现的特征值 按特征名称为键值储存在 data_set中
                features_values = set(features_col)
                for value in features_values:
                    data_set[value] = data[features_col == value]
                    label_set[value] = labels[features_col == value]
            else:
                data_set[('<', point)] = data[features_col < point]
                label_set[('<', point)] = labels[features_col < point]
                data_set[('>=', point)] = data[features_col >= point]
                label_set[('>=', point)] = labels[features_col >= point]
        elif method == 'cart':
            name_set = names
            if(type(features_col[0]) != float and type(features_col[0] != int)):
                # 离散值分等于与不等于
                # 等于集合
                data_set[('=', cart_value)] = data[features_col == cart_value]
                label_set[('=', cart_value)
                          ] = labels[features_col == cart_value]
                # 不等于集合
                data_set[('!=', cart_value)] = data[features_col != cart_value]
                label_set[('!=', cart_value)
                          ] = labels[features_col != cart_value]
            else:
                # 小于指定点
                data_set[('<', point)] = data[features_col < point]
                label_set[('<', point)] = labels[features_col < point]
                # 大于指定点
                data_set[('>=', point)] = data[features_col >= point]
                label_set[('>=', point)] = labels[features_col >= point]

        return data_set, label_set, name_set

    def startCreateTree(self, method='id3', min_sample=1):
        """
        startCreateTree 根据设定的信息增益标准以及阈值限制，构建决策树

        :param self: 类方法自带
        :param method: 选定方法，默认为ID3
        :param min_sample: 最少样本数阈值，默认为1
        """
        self.tree = self.createTree(
            self.train_data, self.train_label, self.label_name, method, min_sample)

    def majLabel(self, labels):
        """
        majLabel 当前标签集的选择主要类别

        :param self: 类方法自带
        :param labels: 输入标签集
        :return: 主要类别名
        """
        labels = np.array(labels, dtype=object)
        label_values = set(labels)
        label_map = {}
        for value in label_values:
            label_map[value] = labels[labels == value].size
        return max(label_map, key=label_map.get)

    def createTree(self, data, labels, names, method, min_sample):
        """
        createTree 构建当前树结点

        :param self: 类方法自带
        :param data: 输入数据集
        :param labels: 输入标签集
        :param names: 输入属性名集合
        :param min_sample: 最小样本数量阈值
        :return: 返回建立的节点
        """
        data = np.array(data, dtype=object)
        labels = np.array(labels, dtype=object)
        names = np.array(names, dtype=object)
        # 相同类别
        if len(set(labels)) == 1:
            return labels[0]
        # 剩余样本量小于阈值
        if data.size == 0 or labels.size <= min_sample:
            return self.majLabel(labels)
        # 选取最优特征
        best_feature_index, best_feature_name, best_value, best_ent, best_point = self.chooseBest(
            data, labels, names, method)

        # 建立节点
        node = {"feature_name": best_feature_name}
        # 函数内删除不会影响外部情况，所以不会造成回溯时改变
        child_data_set, child_label_set, child_name_set = self.splitData(
            data, labels, names, best_feature_index, best_feature_name, best_value, best_point, method)
#         print(child_data_set)
#         print(child_label_set)
        for feature_value in child_data_set.keys():
            node[feature_value] = self.createTree(
                child_data_set[feature_value], child_label_set[feature_value], child_name_set, method, min_sample)
        return node


# In[84]:


def createDataSet(type=0):
    """
    createTree 构建数据集

    :param type: 选择数据集类型（默认为0）
    :return: data: 数据集
    :return: label: 标签集
    :return: label_names: 属性名集合
    """
    if type == 0:
        data = [
            ['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑'],
            ['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑'],
            ['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑'],
            ['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑'],
            ['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑'],
            ['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘'],
            ['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘'],
            ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑'],
            ['乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑'],
            ['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘'],
            ['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑'],
            ['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘'],
            ['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑'],
            ['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑'],
            ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘'],
            ['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑'],
            ['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑']
        ]
        # labels记录样本标签
        labels = ['是', '是', '是', '是', '是', '是', '是', '是',
                  '否', '否', '否', '否', '否', '否', '否', '否', '否']
        # label_names中记录的是特征的名称
        label_names = ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']

    elif type == 1:
        data = np.array([[0.697, 0.46],
                         [0.774, 0.376],
                         [0.634, 0.264],
                         [0.608, 0.318],
                         [0.556, 0.215],
                         [0.403, 0.237],
                         [0.481, 0.149],
                         [0.437, 0.211],
                         [0.666, 0.091],
                         [0.243, 0.267],
                         [0.245, 0.057],
                         [0.343, 0.099],
                         [0.639, 0.161],
                         [0.657, 0.198],
                         [0.36, 0.37],
                         [0.593, 0.042],
                         [0.719, 0.103, ]], dtype=object)
        labels = np.array(['是', '是', '是', '是', '是', '是', '是', '是',
                           '否', '否', '否', '否', '否', '否', '否', '否', '否'], dtype=object)
        label_names = np.array(["密度", "含糖率"], dtype=object)
    if type == 2:
        data = np.array([['1', '青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑'],
                         ['2', '乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑'],
                         ['3', '乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑'],
                         ['4', '青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑'],
                         ['5', '浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑'],
                         ['6', '青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘'],
                         ['7', '乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘'],
                         ['8', '乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑'],
                         ['9', '乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑'],
                         ['10', '青绿', '硬挺', '清脆', '清晰', '平坦', '软粘'],
                         ['11', '浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑'],
                         ['12', '浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘'],
                         ['13', '青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑'],
                         ['14', '浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑'],
                         ['15', '乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘'],
                         ['16', '浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑'],
                         ['17', '青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑']], dtype=object)
        labels = np.array(['是', '是', '是', '是', '是', '是', '是', '是',
                           '否', '否', '否', '否', '否', '否', '否', '否', '否'], dtype=object)
        label_names = np.array(
            ['ID', '色泽', '根蒂', '敲声', '纹理', '脐部', '触感'], dtype=object)
    return data, labels, label_names


# In[36]:

# 定义判断结点形状,其中boxstyle表示文本框类型,fc指的是注释框颜色的深度
decisionNode = dict(boxstyle="round4", color='r', fc='0.9')
# 定义叶结点形状
leafNode = dict(boxstyle="circle", color='m')
# 定义父节点指向子节点或叶子的箭头形状
arrow_args = dict(arrowstyle="<-", color='g')


def plot_node(node_txt, center_point, parent_point, node_style):
    """
    plot_node 绘制父子节点，节点间的箭头，并填充箭头中间上的文本

    :param node_txt: 文本内容
    :param center_point: 文本中心点
    :param parent_point: 指向文本中心的点
    """
    createPlot.ax1.annotate(node_txt,
                            xy=parent_point,
                            xycoords='axes fraction',
                            xytext=center_point,
                            textcoords='axes fraction',
                            va="center",
                            ha="center",
                            bbox=node_style,
                            arrowprops=arrow_args,
                            weight='demi')


def get_leafs_num(tree_dict):
    """
    get_leafs_num 递归计算叶节点的个数

    :param tree_dict: 决策树的字典形式
    :return: tree_dict: 叶节点总个数
    """
    # tree_dict的叶节点总数
    leafs_num = 0

    for key, value in tree_dict.items():
        if key == 'feature_name':
            continue
        # 检测子树是否字典型
        elif type(value).__name__ == 'dict':
            # 子树是字典型，则当前树的叶节点数加上此子树的叶节点数
            leafs_num += get_leafs_num(value)
        else:
            # 子树不是字典型，则当前树的叶节点数加1
            leafs_num += 1

    # 返回tree_dict的叶节点总数
    return leafs_num


def get_tree_max_depth(tree_dict):
    """
    get_tree_max_depth 求树的最深层数

    :param tree_dict: 树的字典存储
    :return: tree_dict: 最深层数
    """
    # tree_dict的最深层数
    max_depth = 0
    for key, value in tree_dict.items():
        # 树的当前分支的层数
        this_path_depth = 0
        # 检测子树是否字典型
        if type(value).__name__ == 'dict':
            # 如果子树是字典型，则当前分支的层数需要加上子树的最深层数
            this_path_depth = 1 + get_tree_max_depth(value)
        else:
            # 如果子树不是字典型，则是叶节点，则当前分支的层数为1
            this_path_depth = 1
        if this_path_depth > max_depth:
            max_depth = this_path_depth
    return max_depth


def plot_mid_text(center_point, parent_point, txt_str):
    """
    plot_mid_text 计算父节点和子节点的中间位置，并在父子节点间填充文本信息

    :param center_point: 文本中心点
    :param parent_point: 指向文本中心点的点
    """

    x_mid = (parent_point[0] - center_point[0])/2.0 + center_point[0]
    y_mid = (parent_point[1] - center_point[1])/2.0 + center_point[1]
    createPlot.ax1.text(x_mid, y_mid, txt_str)
    return


def plotTree(tree_dict, parent_point, node_txt):
    """
    plotTree 绘制树

    :param tree_dict: 树
    :param parent_point: 父节点位置
    :param node_txt: 节点内容
    """
    leafs_num = get_leafs_num(tree_dict)
    # root = list(tree_dict.keys())[0]
    root = tree_dict['feature_name']
    # plotTree.totalW表示树的深度
    center_point = (plotTree.xOff+(1.0+float(leafs_num)) /
                    2.0/plotTree.totalW, plotTree.yOff)
    # 填充node_txt内容
    plot_mid_text(center_point, parent_point, node_txt)
    # 绘制箭头上的内容
    plot_node(root, center_point, parent_point, decisionNode)

    plotTree.yOff = plotTree.yOff-1.0/plotTree.totalD
    # 因从上往下画，所以需要依次递减y的坐标值，plotTree.totalD表示存储树的深度
    for key, value in tree_dict.items():
        if key == 'feature_name':
            continue
        elif type(value).__name__ == 'dict':
            plotTree(value, center_point, str(key))
        else:
            plotTree.xOff = plotTree.xOff+1.0/plotTree.totalW
            plot_node(value, (plotTree.xOff, plotTree.yOff),
                      center_point, leafNode)
            plot_mid_text((plotTree.xOff, plotTree.yOff),
                          center_point, str(key))
    # h绘制完所有子节点后，增加全局变量Y的偏移
    plotTree.yOff = plotTree.yOff+1.0/plotTree.totalD

    return


def createPlot(tree_dict):
    """
    createPlot 绘制决策树图形

    :param tree_dict: 决策树的字典形式
    """
    # 设置绘图区域的背景色
    fig = plt.figure(figsize=(8, 8), facecolor='white')
    # 清空绘图区域
    fig.clf()
    # 定义横纵坐标轴,注意不要设置xticks和yticks的值!!!
    axprops = dict(xticks=[], yticks=[])
    createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)
    # 由全局变量createPlot.ax1定义一个绘图区，111表示一行一列的第一个，frameon表示边框,**axprops不显示刻度
    plotTree.totalW = float(get_leafs_num(tree_dict))
    plotTree.totalD = float(get_tree_max_depth(tree_dict))
    plotTree.xOff = -0.5/plotTree.totalW
    plotTree.yOff = 1.0
    plotTree(tree_dict, (0.5, 1.0), '')
    plt.show()

测试效果

ID3、C4.5、CART 决策树显示

使用课本 P76 西瓜数据集（不带序号）

测试代码

from DecisionTree import createDataSet, DecisionTree, createPlot

data, label, names = createDataSet(0)
mtree = DecisionTree(data, label, names)
mtree.loadTrainData()
print("打印ID3决策树字典形式")
mtree.startCreateTree(method='id3')
print(mtree.tree)
createPlot(mtree.tree)

print("打印C4.5决策树字典形式")
mtree.startCreateTree(method='c4.5')
print(mtree.tree)
createPlot(mtree.tree)


print("打印CART决策树字典形式")
mtree.startCreateTree(method='cart')
print(mtree.tree)
createPlot(mtree.tree)

测试结果

打印ID3决策树字典形式
{'feature_name': '纹理', '清晰': {'feature_name': '根蒂', '蜷缩': '是', '硬挺': '否', '稍蜷': {'feature_name': '色泽', '乌黑': {'feature_name': '触感', '软粘': '否', '硬滑': '是'}, '青绿': '是'}}, '模糊': '否', '稍糊': {'feature_name': '触感', '软粘': '是', '硬滑': '否'}}

tree2

打印C4.5决策树字典形式
{'feature_name': '纹理', '清晰': {'feature_name': '触感', '软粘': {'feature_name': '色泽', '乌黑': '否', '青绿': {'feature_name': '根蒂', '硬挺': '否', '稍蜷': '是'}}, '硬滑': '是'}, '模糊': '否', '稍糊': {'feature_name': '触感', '软粘': '是', '硬滑': '否'}}

tree3

打印CART决策树字典形式
{'feature_name': '纹理', ('=', '清晰'): {'feature_name': '触感', ('=', '软粘'): {'feature_name': '色泽', ('=', '乌黑'): '否', ('!=', '乌黑'): {'feature_name': '根蒂', ('=', '硬挺'): '否', ('!=', '硬挺'): '是'}}, ('!=', '软粘'): '是'}, ('!=', '清晰'): {'feature_name': '色泽', ('=', '乌黑'): {'feature_name': '敲声', ('=', '浊响'): '是', ('!=', '浊响'): '否'}, ('!=', '乌黑'): '否'}}

tree4

结果分析

如图，均成功构建了不同的决策树。

ID3、C4.5 的属性偏好

使用课本 P76 西瓜数据集（带序号），尝试反应 ID3 和 C4.5 使用信息增益对于属性值取值多少的偏好

测试代码

from DecisionTree import createDataSet, DecisionTree, createPlot

data, label, names = createDataSet(2)
mtree = DecisionTree(data, label, names)
mtree.loadTrainData()
mtree.startCreateTree(method='id3')
createPlot(mtree.tree)


mtree.startCreateTree(method='c4.5')
createPlot(mtree.tree)

测试结果

tree5

tree6

结果分析

如预测，ID3 划分依据喜好多属性值的属性，在一些情况下会导致泛化性过差，C4.5 采用的信息增益率对属性值少的更偏好，我的代码并没有完整复现 C4.5 的思想，正如课本 P78 所说。

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

阈值限制测试

使用不带 id 的西瓜数据集，生成 ID3 决策树，代码中加入了 min_sample 的限制，当样本数量小于一定时选择里面的 major 类别代表该集合的类别，不再进一步划分。

测试代码

from DecisionTree import createDataSet, DecisionTree, createPlot

data, label, names = createDataSet(2)
mtree = DecisionTree(data, label, names)
mtree.loadTrainData()
mtree.startCreateTree(method='id3', min_sample=2)
createPlot(mtree.tree)


mtree.startCreateTree(method='id3', min_sample=3)
createPlot(mtree.tree)

测试结果

tree7

tree8

结果分析

确实实现了一定程度上的简化

连续值处理实现

对于现有集合的该连续值属性排序，然后枚举相邻两值的中点作为分界 point，属性值小于 point 的为一个集合，属性值大于 point 的为一个集合。然后计算两部分的信息增益（率），取该值最高的分界 point 作为该属性的分界 point 并返回。

数据集采用密度，含糖量集合，使用 ID3 决策树。

测试代码

from DecisionTree import createDataSet, DecisionTree, createPlot

data, label, names = createDataSet(1)
mtree = DecisionTree(data, label, names)
mtree.loadTrainData()
mtree.startCreateTree(method='id3')
createPlot(mtree.tree)

测试结果

tree9

结果分析

可以看到对连续值属性也做了分割，通过间值选择了最佳的分割位置。

拓展

预剪枝

实现代码

def createPrecutTree(self, train_data, train_label, test_data, test_label, names, method, min_sample):
    """
    createPrecutTree 构建当前预剪枝树结点

    :param self: 类方法自带
    :param train_data: 输入训练数据集
    :param train_label: 输入训练标签集
    :param test_data: 输入测试数据集
    :param test_label: 输入测试标签集
    :param names: 输入属性名集合
    :param min_sample: 最小样本数量阈值
    :return: 返回建立的节点
    """
    train_data = np.array(train_data, dtype=object)
    train_label = np.array(train_label, dtype=object)
    test_data = np.array(test_data, dtype=object)
    test_label = np.array(test_label, dtype=object)
    names = np.array(names, dtype=object)
    # 相同类别
    if len(set(train_label)) == 1:
        return train_label[0]
    # 剩余样本量小于阈值
    if train_data.size == 0 or train_label.size <= min_sample:
        return self.majLabel(train_label)
    # 选取最优特征
    best_feature_index, best_feature_name, best_value, best_ent, best_point = self.chooseBest(
        train_data, train_label, names, method)

    # 建立节点
    node = {"feature_name": best_feature_name}
    child_train_data_set, child_train_label_set, child_name_set = self.splitData(
        train_data, train_label, names, best_feature_index, best_feature_name, best_value, best_point, method)

    main_train_label = self.majLabel(train_label)

    # 预剪枝衡量
    if test_data is None:
        for feature_value in child_train_data_set.keys():
            # 注意这里也要修改，不然后面节点都是无剪枝的
            node[feature_value] = self.createPrecutTree(
                child_train_data_set[feature_value], child_train_label_set[feature_value], None, None, child_name_set, method, min_sample)
    else:
        child_test_data_set, child_test_label_set, child_name_set = self.splitData(
            test_data, test_label, names, best_feature_index, best_feature_name, best_value, best_point, method)
        # 划分前比率
        pre_cut_ratio = test_label[test_label ==
                                   main_train_label].size/test_label.size
        pos_cut_num = 0

        for feature in child_train_label_set.keys():
            if feature not in child_test_label_set.keys():
                continue
            now_test_label = child_test_label_set[feature]
            now_majority_label = self.majLabel(now_test_label)
            pos_cut_num += now_test_label[now_test_label ==
                                          now_majority_label].size
        pos_cut_ratio = pos_cut_num / test_label.size
        print("pre:  "+str(pre_cut_ratio) +
              "   post:   "+str(pos_cut_ratio))

        if(pre_cut_ratio >= pos_cut_ratio):
            # 验证机精确度没有提升
            return main_train_label

    for feature_value in child_train_data_set.keys():
        # 注意这里也要修改，不然后面节点都是无剪枝的
        node[feature_value] = self.createPrecutTree(
            child_train_data_set[feature_value], child_train_label_set[feature_value], child_test_data_set[feature_value], child_test_label_set[feature_value], child_name_set, method, min_sample)
    return node

测试代码

from DecisionTree import createDataSet, DecisionTree, createPlot

data, label, names = createDataSet(0)
mtree = DecisionTree(data, label, names)
mtree.loadTrainData(type=1, sz=0.4)

mtree.startCreateTree(cut_type=0, method='id3')
createPlot(mtree.tree)

mtree.startCreateTree(cut_type=1, method='id3')
createPlot(mtree.tree)

测试结果

tree10

tree11