一渺绒、樹回歸介紹

線性回歸包含了一些強(qiáng)大的方法歹叮，但這些方法創(chuàng)建的模型需要擬合所有的樣本點(diǎn)（局部加權(quán)線性回歸除外）哗讥。當(dāng)數(shù)據(jù)擁有眾多特征并且特征之間關(guān)系十分復(fù)雜時(shí)包颁，構(gòu)建全局模型的想法就顯得太難了瞻想，也略顯笨拙。而且娩嚼，實(shí)際生活中很多問題都是非線性的蘑险，不可能使用全局線性模型來(lái)擬合任何數(shù)據(jù)。一種可行的方法是將數(shù)據(jù)集切分成很多份易建模的數(shù)據(jù)岳悟，然后利用第8章的線性回歸技術(shù)來(lái)建模佃迄。如果首次切分后仍然難以擬合線性模型就繼續(xù)切分。在這種切分方式下贵少，樹結(jié)構(gòu)和回歸法就相當(dāng)有用呵俏。

1、ID3算法的弊端
決策樹的樹構(gòu)建算法是ID3滔灶，ID3的做法是每次選取當(dāng)前最佳的特征來(lái)分割數(shù)據(jù)普碎，并按照該特征的所有可能取值來(lái)切分。也就是說(shuō)录平，如果一個(gè)特征有4種取值麻车，那么數(shù)據(jù)將被切分成4份缀皱。一旦按某特征切分后，該特征在之后的算法執(zhí)行過(guò)程中將不會(huì)再起作用动猬，所以有觀點(diǎn)認(rèn)為這種切分方式過(guò)于迅速啤斗。
除了切分過(guò)于迅速外，ID3算法還存在另一個(gè)問題枣察，它不能直接處理連續(xù)型特征争占。只有事先將連續(xù)型特征離散化，才能在ID3算法中使用序目。但這種轉(zhuǎn)換過(guò)程會(huì)破壞連續(xù)型變量的內(nèi)在特性臂痕。

2、CART算法
與ID3算法相反猿涨，CART算法正好適用于連續(xù)型特征握童。CART算法使用二元切分法來(lái)處理連續(xù)型變量。而使用二元切分法則易于對(duì)樹構(gòu)建過(guò)程進(jìn)行調(diào)整以處理連續(xù)型特征叛赚。具體的處理方法是：如果特征值大于給定值就走左子樹澡绩，否則就走右子樹。

CART算法有兩步：

• 決策樹生成：遞歸地構(gòu)建二叉決策樹的過(guò)程俺附，基于訓(xùn)練數(shù)據(jù)集生成決策樹肥卡，生成的決策樹要盡量大；自上而下從根開始建立節(jié)點(diǎn)事镣，在每個(gè)節(jié)點(diǎn)處要選擇一個(gè)最好的屬性來(lái)分裂步鉴，使得子節(jié)點(diǎn)中的訓(xùn)練集盡量的純。不同的算法使用不同的指標(biāo)來(lái)定義"最好"：
• 決策樹剪枝：用驗(yàn)證數(shù)據(jù)集對(duì)已生成的樹進(jìn)行剪枝并選擇最優(yōu)子樹璃哟，這時(shí)損失函數(shù)最小作為剪枝的標(biāo)準(zhǔn)氛琢。
  決策樹剪枝我們先不管，我們看下決策樹生成随闪。

在決策樹的文章中阳似，我們先根據(jù)信息熵的計(jì)算找到最佳特征切分?jǐn)?shù)據(jù)集構(gòu)建決策樹。CART算法的決策樹生成也是如此铐伴，實(shí)現(xiàn)過(guò)程如下：

• 使用CART算法選擇特征
• 根據(jù)特征切分?jǐn)?shù)據(jù)集合
• 構(gòu)建樹

下面將利用以下數(shù)據(jù)集實(shí)現(xiàn)cart算法

先看下根據(jù)特征切分?jǐn)?shù)據(jù)集合的效果

上貼全文代碼

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

# 將matplotlib后端設(shè)置為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:
            加載數(shù)據(jù)
        Parameters:
            file_name - 文件名
        Returns:
            data_mat - 數(shù)據(jù)矩陣
        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


# 根據(jù)特征切分?jǐn)?shù)據(jù)集合
def bin_split_data_set(data_set, feature, value):
    """
        Function:
            根據(jù)特征切分?jǐn)?shù)據(jù)集合
        Parameters:
            data_set - 數(shù)據(jù)集合
            feature - 待切分的特征
            value - 該特征的值
        Returns:
            mat0 - 切分的數(shù)據(jù)集合0
            mat1 - 切分的數(shù)據(jù)集合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:
            生成葉結(jié)點(diǎn)
        Parameters:
            data_set - 數(shù)據(jù)集合
        Returns:
            mean - 目標(biāo)變量的均值
        Modify:
            2018-10-31
    """
    return mean(data_set[:, -1])


def reg_err(data_set):
    """
        Function:
            生成葉結(jié)點(diǎn)
        Parameters:
            data_set - 數(shù)據(jù)集合
        Returns:
            var - 目標(biāo)變量的總方差
        Modify:
            2018-10-31
    """
    # var()計(jì)算平方誤差
    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:
            找到數(shù)據(jù)的最佳二元切分方式函數(shù)
        Parameters:
            data_set - 數(shù)據(jù)集合
            leaf_type - 生成葉結(jié)點(diǎn)
            err_type - 誤差估計(jì)函數(shù)
            ops - 用戶定義的參數(shù)構(gòu)成的元組
        Returns:
            best_index - 最佳切分特征
            best_value - 最佳特征值
        Modify:
            2018-10-31
    """
    # tol_s允許的誤差下降值撮奏，tol_n切分的最少樣本數(shù)
    tol_s = ops[0]
    tol_n = ops[1]
    # 將數(shù)組或者矩陣轉(zhuǎn)換成列表，統(tǒng)計(jì)不同剩余特征值的數(shù)目
    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]):
            # 根據(jù)特征和特征值切分?jǐn)?shù)據(jù)集
            mat0, mat1 = bin_split_data_set(data_set, feat_index, split_val)
            # 如果數(shù)據(jù)少于tol_n,則退出
            if (shape(mat0)[0] < tol_n) or (shape(mat1)[0] < tol_n): continue
            # 計(jì)算誤差估計(jì)
            new_s = err_type(mat0) + err_type(mat1)
            # 如果誤差估計(jì)更小,則更新最佳特征索引值和特征值
            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)
    # 根據(jù)最佳的切分特征和特征值切分?jǐn)?shù)據(jù)集合
    mat0, mat1 = bin_split_data_set(data_set, best_index, best_value)
    # 如果切分出的數(shù)據(jù)集很小則退出
    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:
            構(gòu)建回歸樹
        Parameters:
            data_set - 數(shù)據(jù)集合
            leaf_type - 建立葉結(jié)點(diǎn)的函數(shù)
            err_type - 誤差計(jì)算函數(shù)
            ops - 包含樹構(gòu)建所有其他參數(shù)的元組
        Returns:
            ret_tree - 構(gòu)建的回歸樹
        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:
            繪制數(shù)據(jù)集
        Parameters:
            file_name - 文件名
        Returns:
            無(wú)
        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數(shù)據(jù)集
        xcord.append(data_mat[i][0])
        ycord.append(data_mat[i][1])
        # ex0.txt數(shù)據(jù)集
        # 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:
            判斷測(cè)試輸入變量是否是一棵樹
        Parameters:
            obj - 判斷對(duì)象
        Returns:
            是否是一棵樹
        Modify:
            2018-11-02
    """
    return (type(obj).__name__ == 'dict')


def get_mean(tree):
    """
        Function:
            對(duì)樹進(jìn)行塌陷處理(即返回樹平均值)
        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 - 測(cè)試集
        Returns:
            后剪枝的樹
        Modify:
            2018-11-02
    """
    # 如果測(cè)試集為空定拟，則對(duì)樹進(jìn)行塌陷處理
    if shape(test_data)[0] == 0:
        return get_mean(tree)
    # 如果有左子樹或者右子樹，則切分?jǐn)?shù)據(jù)集
    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)
    # 如果當(dāng)前結(jié)點(diǎn)的左右結(jié)點(diǎn)為葉結(jié)點(diǎn)
    if not is_tree(tree['left']) and not is_tree(tree['right']):
        lset, rset = bin_split_data_set(test_data, tree['spInd'], tree['spVal'])
        # 計(jì)算沒有合并的誤差
        error_nomerge = sum(power(lset[: -1] - tree['left'], 2)) + sum(power(rset[:, -1] - tree['right'], 2))
        # 計(jì)算合并的均值
        tree_mean = (tree['left'] + tree['right']) / 2.0
        # 計(jì)算合并的誤差
        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:
            模型樹葉節(jié)點(diǎn)生成
        Parameters:
            data_set - 數(shù)據(jù)集
        Returns:
            ws -回歸系數(shù)
            x - 數(shù)據(jù)集矩陣
            y - 目標(biāo)變量值矩陣
        Modify:
            2018-11-03
    """
    m, n = shape(data_set)
    # 構(gòu)建大小為(m,n)和(m,1)的矩陣
    x = mat(ones((m, n)))
    y = mat(ones((m, 1)))
    # 數(shù)據(jù)集矩陣的第一列初始化為1青自，偏置項(xiàng)
    x[:, 1:n] = data_set[:, 0:n - 1]
    # 每個(gè)樣本目標(biāo)變量值存入Y
    y = data_set[:, -1]
    # 對(duì)數(shù)據(jù)集矩陣求內(nèi)積
    x_t_x = x.T * x
    # 計(jì)算行列式值是否為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')
    # 可逆延窜，計(jì)算回歸系數(shù)
    ws = x_t_x.I * (x.T * y)
    return ws, x, y


def model_leaf(data_set):
    """
        Function:
            模型樹的葉節(jié)點(diǎn)模型恋腕，當(dāng)數(shù)據(jù)不再需要切分時(shí)生成葉節(jié)點(diǎn)的模型
        Parameters:
            data_set - 數(shù)據(jù)集
        Returns:
            ws -回歸系數(shù)
        Modify:
            2018-11-03
    """
    ws, x, y = liner_solve(data_set)
    return ws


def model_err(data_set):
    """
        Function:
            模型樹的誤差計(jì)算函數(shù)
        Parameters:
            data_set - 數(shù)據(jù)集
        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 - 數(shù)據(jù)集
            tree - 模型樹
        Returns:
            無(wú)
        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:
            用樹回歸進(jìn)行預(yù)測(cè)代碼
        Parameters:
            model - 樹回歸模型
            in_dat - 輸入數(shù)據(jù)
        Returns:
            回歸樹的葉節(jié)點(diǎn)為float型常量
        Modify:
            2018-11-12
    """
    return float(model)


def model_tree_eval(model, in_dat):
    """
        Function:
            模型樹的葉節(jié)點(diǎn)浮點(diǎn)型參數(shù)的線性方程
        Parameters:
            model - 模型樹模型
            in_dat - 輸入數(shù)據(jù)
        Returns:
            浮點(diǎn)型的回歸系數(shù)向量
        Modify:
            2018-11-12
    """
    # 獲取輸入數(shù)據(jù)的列數(shù)
    n = shape(in_dat)[1]
    # 構(gòu)建n+1維的單列矩陣
    x = mat(ones((1, n + 1)))
    # 第一列設(shè)置為1逆瑞，線性方程偏置項(xiàng)b
    x[:, 1:n + 1] = in_dat
    return float(x * model)


def tree_fore_cast(tree, in_data, model_eval=reg_tree_eval):
    """
        Function:
            樹預(yù)測(cè)
        Parameters:
            tree - 樹回歸模型
            in_dat - 輸入數(shù)據(jù)
            model - 模型樹模型
        Returns:
            浮點(diǎn)型的回歸系數(shù)向量
        Modify:
            2018-11-13
    """
    # 如果當(dāng)前樹為葉節(jié)點(diǎn)荠藤，生成葉節(jié)點(diǎn)
    if not is_tree(tree): return model_eval(tree, in_data)
    # 非葉節(jié)點(diǎn)，對(duì)該子樹對(duì)應(yīng)的切分點(diǎn)對(duì)輸入數(shù)據(jù)進(jìn)行切分
    if in_data[tree['spInd']] > tree['spVal']:
        # 該樹的左分支為非葉節(jié)點(diǎn)類型
        if is_tree(tree['left']):
            # 遞歸調(diào)用treeForeCast函數(shù)繼續(xù)樹預(yù)測(cè)過(guò)程获高，直至找到葉節(jié)點(diǎn)
            return tree_fore_cast(tree['left'], in_data, model_eval)
        else:
            # 左分支為葉節(jié)點(diǎn)哈肖，生成葉節(jié)點(diǎn)
            return model_eval(tree['left'], in_data)
    # 小于切分點(diǎn)值的右分支
    else:
        # 非葉節(jié)點(diǎn)類型
        if is_tree(tree['right']):
            # 非葉節(jié)點(diǎn)類型
            return tree_fore_cast(tree['right'], in_data, model_eval)
        else:
            # 葉節(jié)點(diǎn)，生成葉節(jié)點(diǎn)類型
            return model_eval(tree['right'], in_data)


def create_fore_cast(tree, test_data, model_eval=reg_tree_eval):
    """
        Function:
            創(chuàng)建預(yù)測(cè)樹
        Parameters:
            tree - 樹回歸模型
            test_data - 測(cè)試數(shù)據(jù)
            model - 模型樹模型
        Returns:
            預(yù)測(cè)值
        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:
            以用戶輸入的終止條件為參數(shù)繪制樹
        Parameters:
            tol_s - 允許的誤差下降值
            tol_n - 切分的最少樣本數(shù)
        Returns:
            無(wú)
        Modify:
            2018-11-14
    """
    # 清空之前的圖像
    re_draw.f.clf()
    re_draw.a = re_draw.f.add_subplot(111)
    # 檢查復(fù)選框是否選中念秧，選中就構(gòu)建模型樹淤井，選中默認(rèn)構(gòu)回歸樹
    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)
    # 繪制真實(shí)值
    re_draw.a.scatter(re_draw.raw_dat[:, 0].tolist(), re_draw.raw_dat[:, 1].tolist(), s=5)
    # 繪制預(yù)測(cè)值
    re_draw.a.plot(re_draw.test_dat, y_hat, linewidth=2.0)
    re_draw.canvas.show()


def get_inputs():
    """
        Function:
            從文本輸入框中獲取樹創(chuàng)建終止條件，沒有則用默認(rèn)值
        Parameters:
            無(wú)
        Returns:
            tol_s - 允許的誤差下降值
            tol_n - 切分的最少樣本數(shù)
        Modify:
            2018-11-14
    """
    try:
        tol_n = int(tol_n_entry.get())
    # 清除錯(cuò)誤的輸入并用默認(rèn)值替換
    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按鈕時(shí)摊趾，開始繪圖
        Parameters:
            無(wú)
        Returns:
            無(wú)
        Modify:
            2018-11-14
    """
    # 從文本輸入框中獲取樹創(chuàng)建終止條件
    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)


    # 預(yù)剪枝
    # 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('回歸樹相關(guān)系數(shù):', relation_reg_tree)
    # print('模型樹相關(guān)系數(shù):', relation_model_tree)
    # print('線性方程相關(guān)系數(shù):', relation_linear_solve)

    # root = Tk()
    #
    # # 標(biāo)簽部件
    # # 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('模型樹相關(guān)系數(shù):', relation_reg_tree)

二币狠、實(shí)現(xiàn)CART算法

可以看到，切分的最佳特征為第1列特征砾层，最佳切分特征值為0.48813漩绵，這是根據(jù)誤差估計(jì)的大小，我們選擇的這個(gè)特征值可以使誤差最小化肛炮。

有了最佳的切分的特征和特征值渐行，接下來(lái)就是利用選出的這兩個(gè)變量創(chuàng)建回歸樹了。根據(jù)切分的特征和特征值切分出兩個(gè)數(shù)據(jù)集铸董，然后將兩個(gè)數(shù)據(jù)集分別用于左子樹的構(gòu)建和右子樹的構(gòu)建，直到無(wú)法找到切分的特征為止肴沫∷诤Γ可以通過(guò)遞歸實(shí)現(xiàn)這個(gè)過(guò)程。

從上圖可知颤芬，這棵樹只有兩個(gè)葉結(jié)點(diǎn)悲幅。
再看一個(gè)多次切分的例子，數(shù)據(jù)集如下：

第0列的數(shù)據(jù)都是1.0站蝠，為了可視化方便汰具，我們將第1列作為x軸數(shù)據(jù)，第2列作為y軸數(shù)據(jù)菱魔。對(duì)數(shù)據(jù)進(jìn)行可視化留荔。

可以看到，這個(gè)數(shù)據(jù)集是分段的澜倦，針對(duì)此數(shù)據(jù)集創(chuàng)建回歸樹聚蝶。

可以看到杰妓，該數(shù)的結(jié)構(gòu)中包含5個(gè)葉結(jié)點(diǎn)。

到現(xiàn)在為止碘勉，已經(jīng)完成回歸樹的構(gòu)建巷挥，但是需要某種措施來(lái)檢查構(gòu)建過(guò)程否得當(dāng)。下面將介紹樹剪枝（tree pruning）技術(shù)验靡，它通過(guò)對(duì)決策樹剪枝來(lái)達(dá)到更好的預(yù)測(cè)效果倍宾。

四、預(yù)剪枝

一棵樹如果節(jié)點(diǎn)過(guò)多胜嗓，表明該模型可能對(duì)數(shù)據(jù)進(jìn)行了“過(guò)擬合”高职。通過(guò)降低決策樹的復(fù)雜度來(lái)避免過(guò)擬合的過(guò)程稱為剪枝（pruning），在函數(shù)chooseBestSplit()中的提前終止條件兼蕊，實(shí)際上是在進(jìn)行一種所謂的預(yù)剪枝（prepruning）操作初厚。另一種形式的剪枝需要使用測(cè)試集和訓(xùn)練集，稱作后剪枝（postpruning）孙技。

4.11产禾、預(yù)剪枝

樹構(gòu)建算法其實(shí)對(duì)輸入的參數(shù)tol_s和tol_n非常敏感，如果使用其他值將不太容易達(dá)到這么好的效果牵啦，預(yù)剪枝有一定的局限性亚情，比如我們現(xiàn)在使用一個(gè)新的數(shù)據(jù)集。

可以看到哈雏，這個(gè)數(shù)據(jù)集與使用的第一個(gè)數(shù)據(jù)集很相似楞件，但是區(qū)別在于y的數(shù)量級(jí)差100倍，數(shù)據(jù)分布相似裳瘪，因此構(gòu)建出的樹應(yīng)該也是只有兩個(gè)葉結(jié)點(diǎn)土浸，我們使用默認(rèn)tol_s和tol_n參數(shù)創(chuàng)建樹：

可以看到，構(gòu)建出的樹有很多葉結(jié)點(diǎn)彭羹。產(chǎn)生這個(gè)現(xiàn)象的原因在于黄伊，停止條件tol_s對(duì)誤差的數(shù)量級(jí)十分敏感。如果在選項(xiàng)中花費(fèi)時(shí)間并對(duì)上述誤差容忍度取平均值派殷，或許也能得到僅有兩個(gè)葉結(jié)點(diǎn)組成的樹：

可以看到还最，將參數(shù)tol_s修改為10000后，構(gòu)建的樹就是只有兩個(gè)葉結(jié)點(diǎn)毡惜。然而拓轻，顯然這個(gè)值，需要我們經(jīng)過(guò)不斷測(cè)試得來(lái)经伙，顯然通過(guò)不斷修改停止條件來(lái)得到合理結(jié)果并不是很好的辦法扶叉。事實(shí)上，我們常常甚至不確定到底需要尋找什么樣的結(jié)果。因?yàn)閷?duì)于一個(gè)很多維度的數(shù)據(jù)集辜梳，你也不知道構(gòu)建的樹需要多少個(gè)葉結(jié)點(diǎn)粱甫。

可見，預(yù)剪枝有很大的局限性作瞄。接下來(lái)茶宵，我們討論后剪枝，即利用測(cè)試集來(lái)對(duì)樹進(jìn)行剪枝宗挥。由于不需要用戶指定參數(shù)乌庶，后剪枝是一個(gè)更理想化的剪枝方法。

4.2后剪枝

后剪枝的剪枝過(guò)程是刪除一些子樹契耿，然后用其葉子節(jié)點(diǎn)代替瞒大，在剪枝過(guò)程中, 將一些子樹刪除而用葉節(jié)點(diǎn)代替,這個(gè)葉節(jié)點(diǎn)所標(biāo)識(shí)的類別用這棵子樹中大多數(shù)訓(xùn)練樣本所屬的類別來(lái)標(biāo)識(shí)。

使用后剪枝方法需要將數(shù)據(jù)集分成測(cè)試集和訓(xùn)練集搪桂。首先指定參數(shù)透敌，使得構(gòu)建出的樹足夠大、足夠復(fù)雜踢械，便于剪枝酗电。剪枝的過(guò)程是對(duì)擁有同樣父節(jié)點(diǎn)的一組節(jié)點(diǎn)進(jìn)行檢查，判斷如果將其合并内列，熵的增加量是否小于某一閾值撵术。如果確實(shí)小，則這一組節(jié)點(diǎn)可以合并一個(gè)節(jié)點(diǎn)话瞧，其中包含了所有可能的結(jié)果嫩与。后剪枝是目前最普遍的做法。

可以看到交排，大量的節(jié)點(diǎn)已經(jīng)被剪枝掉了划滋，但沒有像預(yù)期的那樣剪枝成兩部分，這說(shuō)明后剪枝可能不如預(yù)剪枝有效埃篓。一般地古毛，為了尋求最佳模型可以同時(shí)使用兩種剪枝技術(shù)。

剪枝作為決策樹后期處理的重要步驟都许，是必不可少的。沒有剪枝嫂冻，就是一個(gè)完全生長(zhǎng)的決策樹胶征，是過(guò)擬合的，需要去掉一些不必要的節(jié)點(diǎn)以使得決策樹模型更具有泛化能力桨仿。

五睛低、模型樹

用樹來(lái)對(duì)數(shù)據(jù)建模，除了把葉節(jié)點(diǎn)簡(jiǎn)單地設(shè)定為常數(shù)值之外，還有一種方法是把葉節(jié)點(diǎn)設(shè)定為分段線性函數(shù)钱雷，這里所謂的分段線性（piecewise linear）是指模型由多個(gè)線性片段組成骂铁。

考慮上圖中的數(shù)據(jù)，如果使用兩條直線擬合是否比使用一組常數(shù)來(lái)建模好呢 罩抗？答案顯而易見拉庵。可以設(shè)計(jì)兩條分別從0.0～0.3套蒂、從0.3～1.0的直線钞支，于是就可以得到兩個(gè)線性模型。因?yàn)閿?shù)據(jù)集里的一部分?jǐn)?shù)據(jù)（0.0～0.3）以某個(gè)線性模型建模操刀，而另一部分?jǐn)?shù)據(jù)（0.3～1.0）則以另一個(gè)線性模型建模烁挟，因此我們說(shuō)采用了所謂的分段線性模型。

可以看到骨坑，該以0.285477為界創(chuàng)建了兩個(gè)模型撼嗓，而圖9-4的數(shù)據(jù)實(shí)際在0.3處分段。create_tree() 生成的這兩個(gè)線性模型分別是y=3.468+1.1852 和y=0.0016985+11.96477x欢唾，與用于生成該數(shù)據(jù)的真實(shí)模型非常接近且警。

模型樹、回歸樹以及線性回歸里的其他模型匈辱，哪一種模型更好呢振湾？一個(gè)比較客觀的方法是計(jì)算相關(guān)系數(shù)，也稱為R2值亡脸。該相關(guān)系數(shù)可以通過(guò)調(diào)用NumPy庫(kù)中的命令corrcoef(y_hat, y,rowvar=0)來(lái)求解押搪，其中y_hat是預(yù)測(cè)值，y是目標(biāo)變量的實(shí)際值浅碾。

六大州、示例：樹回歸與標(biāo)準(zhǔn)回歸的比較

上面介紹了模型樹、回歸樹和一般的回歸方法垂谢，下面測(cè)試一下哪個(gè)模型最好厦画。這些模型將在某個(gè)數(shù)據(jù)上進(jìn)行測(cè)試，該數(shù)據(jù)涉及人的智力水平和自行車的速度的關(guān)系滥朱。這里的數(shù)據(jù)是非線性的根暑，不能簡(jiǎn)單地使用全局線性模型建模。

R2值越接近1.0越好徙邻，所以從上面的結(jié)果可以看出排嫌，這里模型樹的結(jié)果比回歸樹好，而標(biāo)準(zhǔn)的線性回歸在R2值上的表現(xiàn)上不如上面兩種樹回歸方法缰犁。所以淳地，樹回歸方法在預(yù)測(cè)復(fù)雜數(shù)據(jù)時(shí)會(huì)比簡(jiǎn)單的線性模型更有效怖糊。

七、使用tikinfer創(chuàng)建GUI

python中有很多GUI框架颇象，而tkinder是其中易于使用的一個(gè)伍伤。tkinder的GUI有一些小部件（Widget）組成。包括文本框（Test Box）遣钳，文本輸入框（Entry）按鈕（Button）扰魂，標(biāo)簽（Label）沒和復(fù)選按鈕（Check Button）等對(duì)象。此外耍贾，當(dāng)對(duì)象調(diào)用grid()方法時(shí)阅爽，就等于把該對(duì)象告訴布局管理器，grid()方法將小部件安排在一個(gè)二維的表格中荐开，用戶可以設(shè)定每個(gè)小部件所在的行列位置付翁。

接下來(lái)，就結(jié)合matplotlib和tkinder來(lái)將圖像直接放在GUI上晃听，即通過(guò)修改Matplotlib后端百侧，達(dá)到在tkinder的GUI上繪圖的目的。先用畫布來(lái)替換繪制占位符能扒，刪除對(duì)應(yīng)標(biāo)簽并添加以下代碼：

回歸樹效果：

模型樹效果：

八佣渴、應(yīng)用scikit-learn構(gòu)建樹回歸

可以看出，scikit-learn構(gòu)建的回歸樹的R^2更接近1初斑，效果比之前的實(shí)現(xiàn)的代碼更好辛润。

九、小結(jié)见秤、

數(shù)據(jù)集中經(jīng)常包含一些復(fù)雜的相互關(guān)系砂竖，使得輸入數(shù)據(jù)和目標(biāo)變量之間呈現(xiàn)非線性關(guān)系。對(duì)這些復(fù)雜的關(guān)系建模鹃答，一種可行的方式是使用樹來(lái)對(duì)預(yù)測(cè)值分段乎澄，包括分段常數(shù)或分段直線。一般采用樹結(jié)構(gòu)來(lái)對(duì)這種數(shù)據(jù)建模测摔。相應(yīng)地置济，若葉節(jié)點(diǎn)使用的模型是分段常。數(shù)則稱為回歸樹锋八，若葉節(jié)點(diǎn)使用的模型是線性回歸方程則稱為模型樹浙于。

CART算法可以用于構(gòu)建二元樹并處理離散型或連續(xù)型數(shù)據(jù)的切分。若使用不同的誤差準(zhǔn)則挟纱，就可以通過(guò)CART算法構(gòu)建模型樹和回歸樹路媚。該算法構(gòu)建出的樹會(huì)傾向于對(duì)數(shù)據(jù)過(guò)擬合。一棵過(guò)擬合的樹常常十分復(fù)雜樊销，剪枝技術(shù)的出現(xiàn)就是為了解決這個(gè)問題整慎。兩種剪枝方法分別是預(yù)剪枝（在樹的構(gòu)建過(guò)程中就進(jìn)行剪枝）和后剪枝（當(dāng)樹構(gòu)建完畢再進(jìn)行剪枝），預(yù)剪枝更有效但需要用戶定義一些參數(shù)围苫。