一、树回归介绍

线性回归包含了一些强大的方法，但这些方法创建的模型需要拟合所有的样本点（局部加权线性回归除外）。当数据拥有众多特征并且特征之间关系十分复杂时，构建全局模型的想法就显得太难了，也略显笨拙。而且，实际生活中很多问题都是非线性的，不可能使用全局线性模型来拟合任何数据。一种可行的方法是将数据集切分成很多份易建模的数据，然后利用第8章的线性回归技术来建模。如果首次切分后仍然难以拟合线性模型就继续切分。在这种切分方式下，树结构和回归法就相当有用。

1、ID3算法的弊端
决策树的树构建算法是ID3，ID3的做法是每次选取当前最佳的特征来分割数据，并按照该特征的所有可能取值来切分。也就是说，如果一个特征有4种取值，那么数据将被切分成4份。一旦按某特征切分后，该特征在之后的算法执行过程中将不会再起作用，所以有观点认为这种切分方式过于迅速。
除了切分过于迅速外，ID3算法还存在另一个问题，它不能直接处理连续型特征。只有事先将连续型特征离散化，才能在ID3算法中使用。但这种转换过程会破坏连续型变量的内在特性。

2、CART算法
与ID3算法相反，CART算法正好适用于连续型特征。CART算法使用二元切分法来处理连续型变量。而使用二元切分法则易于对树构建过程进行调整以处理连续型特征。具体的处理方法是：如果特征值大于给定值就走左子树，否则就走右子树。

CART算法有两步：

• 决策树生成：递归地构建二叉决策树的过程，基于训练数据集生成决策树，生成的决策树要尽量大；自上而下从根开始建立节点，在每个节点处要选择一个最好的属性来分裂，使得子节点中的训练集尽量的纯。不同的算法使用不同的指标来定义"最好"：
• 决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时损失函数最小作为剪枝的标准。
  决策树剪枝我们先不管，我们看下决策树生成。

在决策树的文章中，我们先根据信息熵的计算找到最佳特征切分数据集构建决策树。CART算法的决策树生成也是如此，实现过程如下：

• 使用CART算法选择特征
• 根据特征切分数据集合
• 构建树

下面将利用以下数据集实现cart算法

先看下根据特征切分数据集合的效果

上贴全文代码

from numpy import *
from matplotlib.font_manager import FontProperties
from tkinter import *
import matplotlib

# 将matplotlib后端设置为TkAgg
matplotlib.use('TkAgg')
import matplotlib.pyplot as plt
from matplotlib.backends.backend_tkagg import FigureCanvasTkAgg
from matplotlib.figure import Figure
from sklearn.tree import DecisionTreeRegressor


def load_data_set(file_name):
    """
        Function:
            加载数据
        Parameters:
            file_name - 文件名
        Returns:
            data_mat - 数据矩阵
        Modify:
            2018-10-30
    """
    data_mat = []
    fr = open(file_name)
    for line in fr.readlines():
        cur_line = line.strip().split('\t')
        flt_line = list(map(float, cur_line))
        data_mat.append(flt_line)
    return data_mat


# 根据特征切分数据集合
def bin_split_data_set(data_set, feature, value):
    """
        Function:
            根据特征切分数据集合
        Parameters:
            data_set - 数据集合
            feature - 待切分的特征
            value - 该特征的值
        Returns:
            mat0 - 切分的数据集合0
            mat1 - 切分的数据集合1
        Modify:
            2018-10-30
    """
    mat0 = data_set[nonzero(data_set[:, feature] > value)[0], :]
    mat1 = data_set[nonzero(data_set[:, feature] <= value)[0], :]
    return mat0, mat1


def reg_leaf(data_set):
    """
        Function:
            生成叶结点
        Parameters:
            data_set - 数据集合
        Returns:
            mean - 目标变量的均值
        Modify:
            2018-10-31
    """
    return mean(data_set[:, -1])


def reg_err(data_set):
    """
        Function:
            生成叶结点
        Parameters:
            data_set - 数据集合
        Returns:
            var - 目标变量的总方差
        Modify:
            2018-10-31
    """
    # var()计算平方误差
    return var(data_set[:, -1]) * shape(data_set)[0]


def choose_best_split(data_set, leaf_type=reg_leaf, err_type=reg_err, ops=(1, 4)):
    """
        Function:
            找到数据的最佳二元切分方式函数
        Parameters:
            data_set - 数据集合
            leaf_type - 生成叶结点
            err_type - 误差估计函数
            ops - 用户定义的参数构成的元组
        Returns:
            best_index - 最佳切分特征
            best_value - 最佳特征值
        Modify:
            2018-10-31
    """
    # tol_s允许的误差下降值，tol_n切分的最少样本数
    tol_s = ops[0]
    tol_n = ops[1]
    # 将数组或者矩阵转换成列表，统计不同剩余特征值的数目
    if len(set(data_set[:, -1].T.tolist()[0])) == 1:
        return None, leaf_type(data_set)
    m, n = shape(data_set)
    s = err_type(data_set)
    # 分别为最佳误差，最佳特征切分的索引值，最佳特征值
    best_s = float('inf')
    best_index = 0
    best_value = 0
    # 遍历所有特征列
    for feat_index in range(n - 1):
        # 遍历所有特征值
        for split_val in set(data_set[:, feat_index].T.A.tolist()[0]):
            # 根据特征和特征值切分数据集
            mat0, mat1 = bin_split_data_set(data_set, feat_index, split_val)
            # 如果数据少于tol_n,则退出
            if (shape(mat0)[0] < tol_n) or (shape(mat1)[0] < tol_n): continue
            # 计算误差估计
            new_s = err_type(mat0) + err_type(mat1)
            # 如果误差估计更小,则更新最佳特征索引值和特征值
            if new_s < best_s:
                best_index = feat_index
                best_value = split_val
                best_s = new_s
    # 如果误差减少不大则退出
    if (s - best_s) < tol_s:
        return None, leaf_type(data_set)
    # 根据最佳的切分特征和特征值切分数据集合
    mat0, mat1 = bin_split_data_set(data_set, best_index, best_value)
    # 如果切分出的数据集很小则退出
    if (shape(mat0)[0] < tol_n) or (shape(mat1)[0] < tol_n):
        return None, leaf_type(data_set)
    # 返回最佳切分特征和特征值
    return best_index, best_value


def create_tree(data_set, leaf_type=reg_leaf, err_type=reg_err, ops=(1, 4)):
    """
        Function:
            构建回归树
        Parameters:
            data_set - 数据集合
            leaf_type - 建立叶结点的函数
            err_type - 误差计算函数
            ops - 包含树构建所有其他参数的元组
        Returns:
            ret_tree - 构建的回归树
        Modify:
            2018-10-31
    """
    feat, val = choose_best_split(data_set, leaf_type, err_type, ops)
    if feat == None: return val
    ret_tree = {}
    ret_tree['spInd'] = feat
    ret_tree['spVal'] = val
    lset, rset = bin_split_data_set(data_set, feat, val)
    # print(lset)
    # print(rset)
    ret_tree['left'] = create_tree(lset, leaf_type, err_type, ops)
    ret_tree['right'] = create_tree(rset, leaf_type, err_type, ops)
    return ret_tree


def plot_data_set(file_name):
    """
        Function:
            绘制数据集
        Parameters:
            file_name - 文件名
        Returns:
            无
        Modify:
            2018-10-31
    """
    font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=14)
    data_mat = load_data_set(file_name)
    n = len(data_mat)
    xcord = []
    ycord = []
    for i in range(n):
        # ex00.txt、ex2.txt、exp2.txt数据集
        xcord.append(data_mat[i][0])
        ycord.append(data_mat[i][1])
        # ex0.txt数据集
        # xcord.append(data_mat[i][1])
        # ycord.append(data_mat[i][2])
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.scatter(xcord, ycord, s=20, c='blue', alpha=0.5)
    # plt.title('data_set')
    # plt.xlabel('X')
    ax_xlabel_text = ax.set_xlabel(u'骑自行车的速度', FontProperties=font)
    ax_ylabel_text = ax.set_ylabel(u'智商（IQ）', FontProperties=font)
    plt.show()


def is_tree(obj):
    """
        Function:
            判断测试输入变量是否是一棵树
        Parameters:
            obj - 判断对象
        Returns:
            是否是一棵树
        Modify:
            2018-11-02
    """
    return (type(obj).__name__ == 'dict')


def get_mean(tree):
    """
        Function:
            对树进行塌陷处理(即返回树平均值)
        Parameters:
            tree - 树
        Returns:
            树的平均值
        Modify:
            2018-11-02
    """
    if is_tree(tree['right']):
        tree['right'] = get_mean(tree['right'])
    if is_tree(tree['left']):
        tree['left'] = get_mean(tree['left'])
    return (tree['left'] + tree['right']) / 2.0


def prune(tree, test_data):
    """
        Function:
            后剪枝
        Parameters:
            tree - 树
            test_data - 测试集
        Returns:
            后剪枝的树
        Modify:
            2018-11-02
    """
    # 如果测试集为空，则对树进行塌陷处理
    if shape(test_data)[0] == 0:
        return get_mean(tree)
    # 如果有左子树或者右子树，则切分数据集
    if (is_tree(tree['right']) or is_tree(tree['left'])):
        lset, rset = bin_split_data_set(test_data, tree['spInd'], tree['spVal'])
    # 处理左子树(剪枝)
    if is_tree(tree['left']):
        tree['left'] = prune(tree['left'], lset)
    # 处理右子树(剪枝)
    if is_tree(tree['right']):
        tree['right'] = prune(tree['right'], rset)
    # 如果当前结点的左右结点为叶结点
    if not is_tree(tree['left']) and not is_tree(tree['right']):
        lset, rset = bin_split_data_set(test_data, tree['spInd'], tree['spVal'])
        # 计算没有合并的误差
        error_nomerge = sum(power(lset[: -1] - tree['left'], 2)) + sum(power(rset[:, -1] - tree['right'], 2))
        # 计算合并的均值
        tree_mean = (tree['left'] + tree['right']) / 2.0
        # 计算合并的误差
        error_merge = sum(power(test_data[:, -1] - tree_mean, 2))
        # 如果合并的误差小于没有合并的误差，则合并
        if error_merge < error_nomerge:
            return tree_mean
        else:
            return tree
    else:
        return tree


def liner_solve(data_set):
    """
        Function:
            模型树叶节点生成
        Parameters:
            data_set - 数据集
        Returns:
            ws -回归系数
            x - 数据集矩阵
            y - 目标变量值矩阵
        Modify:
            2018-11-03
    """
    m, n = shape(data_set)
    # 构建大小为(m,n)和(m,1)的矩阵
    x = mat(ones((m, n)))
    y = mat(ones((m, 1)))
    # 数据集矩阵的第一列初始化为1，偏置项
    x[:, 1:n] = data_set[:, 0:n - 1]
    # 每个样本目标变量值存入Y
    y = data_set[:, -1]
    # 对数据集矩阵求内积
    x_t_x = x.T * x
    # 计算行列式值是否为0，即判断是否可逆
    if linalg.det(x_t_x) == 0.0:
        # 不可逆，打印信息
        raise NameError('This matrix is singular, cannot du inverse, \ntry increasing the second value of ops')
    # 可逆，计算回归系数
    ws = x_t_x.I * (x.T * y)
    return ws, x, y


def model_leaf(data_set):
    """
        Function:
            模型树的叶节点模型，当数据不再需要切分时生成叶节点的模型
        Parameters:
            data_set - 数据集
        Returns:
            ws -回归系数
        Modify:
            2018-11-03
    """
    ws, x, y = liner_solve(data_set)
    return ws


def model_err(data_set):
    """
        Function:
            模型树的误差计算函数
        Parameters:
            data_set - 数据集
        Returns:
            返回误差平方和，平方损失
        Modify:
            2018-11-03
    """
    ws, x, y = liner_solve(data_set)
    y_hat = x * ws
    return sum(power(y - y_hat, 2))


def plot_model_data_set(data_set, tree):
    """
        Function:
            绘制模型树
        Parameters:
            data_set - 数据集
            tree - 模型树
        Returns:
            无
        Modify:
            2018-10-31
    """
    n = len(data_set)
    xcord = []
    ycord = []
    xcord_1 = []
    xcord_2 = []
    for i in range(n):
        xcord.append(data_set[i][0])
        ycord.append(data_set[i][1])
        if data_set[i][0] <= tree['spVal']:
            xcord_1.append(data_set[i][0])
        else:
            xcord_2.append(data_set[i][0])
    xcord_1_mat = mat(xcord_1)
    xcord_2_mat = mat(xcord_2)
    ws_1 = tree['right']
    ws_2 = tree['left']
    y_hat_1 = ws_1[0] + ws_1[1] * xcord_1_mat
    y_hat_2 = ws_2[0] + ws_2[1] * xcord_2_mat
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.plot(xcord_1_mat.flatten().A[0], y_hat_1.flatten().A[0], c='red')
    ax.plot(xcord_2_mat.flatten().A[0], y_hat_2.flatten().A[0], c='red')
    ax.scatter(xcord, ycord, s=20, c='blue', alpha=0.5)
    plt.title('data_set')
    plt.xlabel('X')
    plt.show()


def reg_tree_eval(model, in_dat):
    """
        Function:
            用树回归进行预测代码
        Parameters:
            model - 树回归模型
            in_dat - 输入数据
        Returns:
            回归树的叶节点为float型常量
        Modify:
            2018-11-12
    """
    return float(model)


def model_tree_eval(model, in_dat):
    """
        Function:
            模型树的叶节点浮点型参数的线性方程
        Parameters:
            model - 模型树模型
            in_dat - 输入数据
        Returns:
            浮点型的回归系数向量
        Modify:
            2018-11-12
    """
    # 获取输入数据的列数
    n = shape(in_dat)[1]
    # 构建n+1维的单列矩阵
    x = mat(ones((1, n + 1)))
    # 第一列设置为1，线性方程偏置项b
    x[:, 1:n + 1] = in_dat
    return float(x * model)


def tree_fore_cast(tree, in_data, model_eval=reg_tree_eval):
    """
        Function:
            树预测
        Parameters:
            tree - 树回归模型
            in_dat - 输入数据
            model - 模型树模型
        Returns:
            浮点型的回归系数向量
        Modify:
            2018-11-13
    """
    # 如果当前树为叶节点，生成叶节点
    if not is_tree(tree): return model_eval(tree, in_data)
    # 非叶节点，对该子树对应的切分点对输入数据进行切分
    if in_data[tree['spInd']] > tree['spVal']:
        # 该树的左分支为非叶节点类型
        if is_tree(tree['left']):
            # 递归调用treeForeCast函数继续树预测过程，直至找到叶节点
            return tree_fore_cast(tree['left'], in_data, model_eval)
        else:
            # 左分支为叶节点，生成叶节点
            return model_eval(tree['left'], in_data)
    # 小于切分点值的右分支
    else:
        # 非叶节点类型
        if is_tree(tree['right']):
            # 非叶节点类型
            return tree_fore_cast(tree['right'], in_data, model_eval)
        else:
            # 叶节点，生成叶节点类型
            return model_eval(tree['right'], in_data)


def create_fore_cast(tree, test_data, model_eval=reg_tree_eval):
    """
        Function:
            创建预测树
        Parameters:
            tree - 树回归模型
            test_data - 测试数据
            model - 模型树模型
        Returns:
            预测值
        Modify:
            2018-11-13
    """
    m = len(test_data)
    # 初始化行向量各维度值为1
    y_hat = mat(zeros((m, 1)))
    for i in range(m):
        y_hat[i, 0] = tree_fore_cast(tree, mat(test_data[i]), model_eval)
    return y_hat


def re_draw(tol_s, tol_n):
    """
        Function:
            以用户输入的终止条件为参数绘制树
        Parameters:
            tol_s - 允许的误差下降值
            tol_n - 切分的最少样本数
        Returns:
            无
        Modify:
            2018-11-14
    """
    # 清空之前的图像
    re_draw.f.clf()
    re_draw.a = re_draw.f.add_subplot(111)
    # 检查复选框是否选中，选中就构建模型树，选中默认构回归树
    if chk_btn_val.get():
        if tol_n < 2: tol_n = 2
        my_tree = create_tree(re_draw.raw_dat, model_leaf, model_err, (tol_s, tol_n))
        y_hat = create_fore_cast(my_tree, re_draw.test_dat, model_tree_eval)
    else:
        my_tree = create_tree(re_draw.raw_dat, ops=(tol_s, tol_n))
        y_hat = create_fore_cast(my_tree, re_draw.test_dat)
    # 绘制真实值
    re_draw.a.scatter(re_draw.raw_dat[:, 0].tolist(), re_draw.raw_dat[:, 1].tolist(), s=5)
    # 绘制预测值
    re_draw.a.plot(re_draw.test_dat, y_hat, linewidth=2.0)
    re_draw.canvas.show()


def get_inputs():
    """
        Function:
            从文本输入框中获取树创建终止条件，没有则用默认值
        Parameters:
            无
        Returns:
            tol_s - 允许的误差下降值
            tol_n - 切分的最少样本数
        Modify:
            2018-11-14
    """
    try:
        tol_n = int(tol_n_entry.get())
    # 清除错误的输入并用默认值替换
    except:
        tol_n = 10
        print('enter Integer for tol_n')
        tol_n_entry.delete(0, END)
        tol_n_entry.insert(0, '10')
    try:
        tol_s = float(tol_n_entry.get())
    except:
        tol_n = 10
        print('enter Integer for tol_s')
        tol_n_entry.delete(0, END)
        tol_n_entry.insert(0, '1.0')
    return tol_n, tol_s


def draw_new_tree():
    """
        Function:
            按下re_draw按钮时，开始绘图
        Parameters:
            无
        Returns:
            无
        Modify:
            2018-11-14
    """
    # 从文本输入框中获取树创建终止条件
    tol_n, tol_s = get_inputs()
    re_draw(tol_s, tol_n)


if __name__ == '__main__':
    # test_mat = mat(eye(4))
    # mat0, mat1 = bin_split_data_set(test_mat, 1, 0.5)
    # print('原始集合:\n', test_mat)
    # print('mat0:\n', mat0)
    # print('mat1:\n', mat1)

    # file_name = './machinelearninginaction/Ch09/ex00.txt'
    # plot_data_set(file_name)

    # data_set = load_data_set('./machinelearninginaction/Ch09/ex00.txt')
    # data_mat = mat(data_set)
    # best_feat, val = choose_best_split(data_mat)
    # print(best_feat)
    # print(val)


    # data_set = load_data_set('./machinelearninginaction/Ch09/ex00.txt')
    # data_mat = mat(data_set)
    # my_tree = create_tree(data_mat)
    # print(my_tree)

    # file_name = './machinelearninginaction/Ch09/ex0.txt'
    # plot_data_set(file_name)

    # data_set = load_data_set('./machinelearninginaction/Ch09/ex0.txt')
    # data_mat = mat(data_set)
    # my_tree = create_tree(data_mat)
    # print(my_tree)


    # 预剪枝
    # file_name = './machinelearninginaction/Ch09/ex2.txt'
    # plot_data_set(file_name)

    # data_set = load_data_set('./machinelearninginaction/Ch09/ex2.txt')
    # data_mat = mat(data_set)
    # my_tree = create_tree(data_mat, ops=(1000, 4))
    # print(my_tree)

    # 后剪枝
    # print('剪枝前：')
    # train_data = load_data_set('./machinelearninginaction/Ch09/ex2.txt')
    # train_mat = mat(train_data)
    # tree = create_tree(train_mat)
    # print(tree)
    # print('\n剪枝后：')
    # test_data = load_data_set('./machinelearninginaction/Ch09/ex2test.txt')
    # test_mat = mat(test_data)
    # print(prune(tree, test_mat))


    # file_name = './machinelearninginaction/Ch09/exp2.txt'
    # plot_data_set(file_name)

    # data_set = load_data_set('./machinelearninginaction/Ch09/exp2.txt')
    # data_mat = mat(data_set)
    # tree = create_tree(data_mat, model_leaf, model_err, (1, 10))
    # print(tree)

    # data_set = load_data_set('./machinelearninginaction/Ch09/exp2.txt')
    # data_mat = mat(data_set)
    # tree = create_tree(data_mat, model_leaf, model_err, (1, 10))
    # plot_model_data_set(data_set, tree)


    # plot_data_set('./machinelearninginaction/Ch09/bikeSpeedVsIq_train.txt')


    # train_mat = mat(load_data_set('./machinelearninginaction/Ch09/bikeSpeedVsIq_train.txt'))
    # test_mat = mat(load_data_set('./machinelearninginaction/Ch09/bikeSpeedVsIq_test.txt'))
    # # 回归树
    # reg_tree = create_tree(train_mat, ops=(1, 20))
    # # 模型树
    # model_tree = create_tree(train_mat, model_leaf, model_err, ops=(1, 20))
    # y_hat_reg_tree = create_fore_cast(reg_tree, test_mat[:, 0])
    # y_hat_model_tree = create_fore_cast(model_tree, test_mat[:, 0], model_tree_eval)
    # relation_reg_tree = corrcoef(y_hat_reg_tree, test_mat[:, 1], rowvar=0)[0, 1]
    # relation_model_tree = corrcoef(y_hat_model_tree, test_mat[:, 1], rowvar=0)[0, 1]
    # # 线性方程
    # ws, x, y = liner_solve(train_mat)
    # m = shape(test_mat)[0]
    # y_hat = mat(zeros((m, 1)))
    # for i in range(m):
    #     y_hat[i] = test_mat[i, 0] * ws[1, 0] + ws[0, 0]
    # relation_linear_solve = corrcoef(y_hat, test_mat[:, 1], rowvar=0)[0, 1]
    # print('回归树相关系数:', relation_reg_tree)
    # print('模型树相关系数:', relation_model_tree)
    # print('线性方程相关系数:', relation_linear_solve)

    # root = Tk()
    #
    # # 标签部件
    # # Label(root, text='Plot Place Holder').grid(row=0, columnspan=3)
    # re_draw.f = Figure(figsize=(5, 4), dpi=100)
    # re_draw.canvas = FigureCanvasTkAgg(re_draw.f, master=root)
    # re_draw.canvas.show()
    # re_draw.canvas.get_tk_widget().grid(row=0, columnspan=3)
    # # 文本输入框部件tol_n
    # Label(root, text='tol_n').grid(row=1, column=0)
    # tol_n_entry = Entry(root)
    # tol_n_entry.grid(row=1, column=0)
    # tol_n_entry.insert(0, '10')
    # # 文本输入框部件
    # Label(root, text='tol_s').grid(row=2, column=0)
    # tol_n_entry = Entry(root)
    # tol_n_entry.grid(row=2, column=0)
    # tol_n_entry.insert(0, '1.0')
    # # 按钮部件
    # Button(root, text='re_draw', comman=draw_new_tree).grid(row=1, column=2, rowspan=3)
    # chk_btn_val = IntVar()
    # chk_btn = Checkbutton(root, text='Model Tree', variable=chk_btn_val)
    # chk_btn.grid(row=3, column=0, columnspan=2)
    # re_draw.raw_dat = mat(load_data_set('./machinelearninginaction/Ch09/sine.txt'))
    # re_draw.test_dat = arange(min(re_draw.raw_dat[:, 0]), max(re_draw.raw_dat[:, 0]), 0.01)
    #
    # re_draw(1.0, 10)
    # root.mainloop()

    train_mat = mat(load_data_set('./machinelearninginaction/Ch09/bikeSpeedVsIq_train.txt'))
    test_mat = mat(load_data_set('./machinelearninginaction/Ch09/bikeSpeedVsIq_test.txt'))
    reg_tree = DecisionTreeRegressor(max_depth=4)
    reg_tree = reg_tree.fit(train_mat[:, 0], train_mat[:, 1])
    y_hat_reg_tree = reg_tree.predict(test_mat[:, 0])
    relation_reg_tree = corrcoef(y_hat_reg_tree, test_mat[:, 1], rowvar=0)[0, 1]
    print('模型树相关系数:', relation_reg_tree)

二、实现CART算法

可以看到，切分的最佳特征为第1列特征，最佳切分特征值为0.48813，这是根据误差估计的大小，我们选择的这个特征值可以使误差最小化。

有了最佳的切分的特征和特征值，接下来就是利用选出的这两个变量创建回归树了。根据切分的特征和特征值切分出两个数据集，然后将两个数据集分别用于左子树的构建和右子树的构建，直到无法找到切分的特征为止。可以通过递归实现这个过程。

从上图可知，这棵树只有两个叶结点。
再看一个多次切分的例子，数据集如下：

第0列的数据都是1.0，为了可视化方便，我们将第1列作为x轴数据，第2列作为y轴数据。对数据进行可视化。

可以看到，这个数据集是分段的，针对此数据集创建回归树。

可以看到，该数的结构中包含5个叶结点。

到现在为止，已经完成回归树的构建，但是需要某种措施来检查构建过程否得当。下面将介绍树剪枝（tree pruning）技术，它通过对决策树剪枝来达到更好的预测效果。

四、预剪枝

一棵树如果节点过多，表明该模型可能对数据进行了“过拟合”。通过降低决策树的复杂度来避免过拟合的过程称为剪枝（pruning），在函数chooseBestSplit()中的提前终止条件，实际上是在进行一种所谓的预剪枝（prepruning）操作。另一种形式的剪枝需要使用测试集和训练集，称作后剪枝（postpruning）。

4.11、预剪枝

树构建算法其实对输入的参数tol_s和tol_n非常敏感，如果使用其他值将不太容易达到这么好的效果，预剪枝有一定的局限性，比如我们现在使用一个新的数据集。

可以看到，这个数据集与使用的第一个数据集很相似，但是区别在于y的数量级差100倍，数据分布相似，因此构建出的树应该也是只有两个叶结点，我们使用默认tol_s和tol_n参数创建树：

可以看到，构建出的树有很多叶结点。产生这个现象的原因在于，停止条件tol_s对误差的数量级十分敏感。如果在选项中花费时间并对上述误差容忍度取平均值，或许也能得到仅有两个叶结点组成的树：

可以看到，将参数tol_s修改为10000后，构建的树就是只有两个叶结点。然而，显然这个值，需要我们经过不断测试得来，显然通过不断修改停止条件来得到合理结果并不是很好的办法。事实上，我们常常甚至不确定到底需要寻找什么样的结果。因为对于一个很多维度的数据集，你也不知道构建的树需要多少个叶结点。

可见，预剪枝有很大的局限性。接下来，我们讨论后剪枝，即利用测试集来对树进行剪枝。由于不需要用户指定参数，后剪枝是一个更理想化的剪枝方法。

4.2后剪枝

后剪枝的剪枝过程是删除一些子树，然后用其叶子节点代替，在剪枝过程中, 将一些子树删除而用叶节点代替,这个叶节点所标识的类别用这棵子树中大多数训练样本所属的类别来标识。

使用后剪枝方法需要将数据集分成测试集和训练集。首先指定参数，使得构建出的树足够大、足够复杂，便于剪枝。剪枝的过程是对拥有同样父节点的一组节点进行检查，判断如果将其合并，熵的增加量是否小于某一阈值。如果确实小，则这一组节点可以合并一个节点，其中包含了所有可能的结果。后剪枝是目前最普遍的做法。

可以看到，大量的节点已经被剪枝掉了，但没有像预期的那样剪枝成两部分，这说明后剪枝可能不如预剪枝有效。一般地，为了寻求最佳模型可以同时使用两种剪枝技术。

剪枝作为决策树后期处理的重要步骤，是必不可少的。没有剪枝，就是一个完全生长的决策树，是过拟合的，需要去掉一些不必要的节点以使得决策树模型更具有泛化能力。

五、模型树

用树来对数据建模，除了把叶节点简单地设定为常数值之外，还有一种方法是把叶节点设定为分段线性函数，这里所谓的分段线性（piecewise linear）是指模型由多个线性片段组成。

考虑上图中的数据，如果使用两条直线拟合是否比使用一组常数来建模好呢 ？答案显而易见。可以设计两条分别从0.0～0.3、从0.3～1.0的直线，于是就可以得到两个线性模型。因为数据集里的一部分数据（0.0～0.3）以某个线性模型建模，而另一部分数据（0.3～1.0）则以另一个线性模型建模，因此我们说采用了所谓的分段线性模型。

可以看到，该以0.285477为界创建了两个模型，而图9-4的数据实际在0.3处分段。create_tree() 生成的这两个线性模型分别是y=3.468+1.1852 和y=0.0016985+11.96477x，与用于生成该数据的真实模型非常接近。

模型树、回归树以及线性回归里的其他模型，哪一种模型更好呢？一个比较客观的方法是计算相关系数，也称为R2值。该相关系数可以通过调用NumPy库中的命令corrcoef(y_hat, y,rowvar=0)来求解，其中y_hat是预测值，y是目标变量的实际值。

六、示例：树回归与标准回归的比较

上面介绍了模型树、回归树和一般的回归方法，下面测试一下哪个模型最好。这些模型将在某个数据上进行测试，该数据涉及人的智力水平和自行车的速度的关系。这里的数据是非线性的，不能简单地使用全局线性模型建模。

R2值越接近1.0越好，所以从上面的结果可以看出，这里模型树的结果比回归树好，而标准的线性回归在R2值上的表现上不如上面两种树回归方法。所以，树回归方法在预测复杂数据时会比简单的线性模型更有效。

七、使用tikinfer创建GUI

python中有很多GUI框架，而tkinder是其中易于使用的一个。tkinder的GUI有一些小部件（Widget）组成。包括文本框（Test Box），文本输入框（Entry）按钮（Button），标签（Label）没和复选按钮（Check Button）等对象。此外，当对象调用grid()方法时，就等于把该对象告诉布局管理器，grid()方法将小部件安排在一个二维的表格中，用户可以设定每个小部件所在的行列位置。

接下来，就结合matplotlib和tkinder来将图像直接放在GUI上，即通过修改Matplotlib后端，达到在tkinder的GUI上绘图的目的。先用画布来替换绘制占位符，删除对应标签并添加以下代码：

回归树效果：

模型树效果：

八、应用scikit-learn构建树回归

可以看出，scikit-learn构建的回归树的R^2更接近1，效果比之前的实现的代码更好。

九、小结、

数据集中经常包含一些复杂的相互关系，使得输入数据和目标变量之间呈现非线性关系。对这些复杂的关系建模，一种可行的方式是使用树来对预测值分段，包括分段常数或分段直线。一般采用树结构来对这种数据建模。相应地，若叶节点使用的模型是分段常。数则称为回归树，若叶节点使用的模型是线性回归方程则称为模型树。

CART算法可以用于构建二元树并处理离散型或连续型数据的切分。若使用不同的误差准则，就可以通过CART算法构建模型树和回归树。该算法构建出的树会倾向于对数据过拟合。一棵过拟合的树常常十分复杂，剪枝技术的出现就是为了解决这个问题。两种剪枝方法分别是预剪枝（在树的构建过程中就进行剪枝）和后剪枝（当树构建完毕再进行剪枝），预剪枝更有效但需要用户定义一些参数。