<jupyter_start><jupyter_text>树回归简单的线性回归是一种构建全局模型的想法，面对非线性的数据将束手无策。我们将数据切分为多份易建模的数据，再进行回归。所以树回归 = 决策树 + 回归分析CART（Classification And Regression Tree）分类回归树，既用于分类，还用于回归。 决策树算法* ID3 (Iterative Dichotomister,迭代二分法)，每次选取最佳的特征分隔，并按该特征的所有取值切分。所以无法区分连续型数据，只能转换为连续型。* 二元切分法 优化ID3算法，特征值小于给定值就走左子树，大于就走右子树，易于处理连续型数据。  回归树的构建伪代码    找到最佳的特征分割：        如果该节点无法再分，则保存为叶节点返回        执行二元切分        左子树调用构造方法         右子树调用构造方法 特征值的选取伪代码    对每个特征        对每个特征值            将数据预分成两份            计算切分后的误差            如果此误差小于当前最小误差，则更新误差和切分记录    返回最佳切分特征和特征值<jupyter_code>import numpy as np
def load_data(filename):
    data_mat = []
    fr = open(filename)
    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
mydata = np.mat(load_data('ex00.txt'))
mydata
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(mydata[:, 0].T.A[0], mydata[:, 1].T.A[0])
def bin_split(dataset, feature, value):
    mat0 = dataset[np.nonzero(dataset[:,feature] > value)[0],:]
    mat1 = dataset[np.nonzero(dataset[:,feature] <= value)[0],:]
    return mat0,mat1

def reg_leaf(dataset):#returns the value used for each leaf
    return np.mean(dataset[:,-1])

def reg_err(dataset):
    return np.var(dataset[:,-1]) * np.shape(dataset)[0]

def choose_best_split(dataset, leaf_type=reg_leaf, err_type=reg_err, ops=(1,4)):
    tol_s = ops[0]; tol_n = ops[1]
    if len(set(dataset[:,-1].T.tolist()[0])) == 1: 
        return None, leaf_type(dataset)
    m,n = np.shape(dataset)
    s = err_type(dataset)
    best_s = np.inf; best_index = 0; best_value = 0
    for feat_index in range(n-1):
        for split_val in set(dataset[:,feat_index].T.tolist()[0]):
            mat0, mat1 = bin_split(dataset, feat_index, split_val)
            if (np.shape(mat0)[0] < tol_n) or (np.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(dataset)
    mat0, mat1 = bin_split(dataset, best_index, best_value)
    if (np.shape(mat0)[0] < tol_n) or (np.shape(mat1)[0] < tol_n):  
        return None, leaf_type(dataset)
    return best_index,best_value

def create_tree(dataset, leaf_type=reg_leaf, err_type=reg_err, ops=(1,4)):
    feat, val = choose_best_split(dataset, leaf_type, err_type, ops)
    if feat == None: return val 
    ret_tree = {}
    ret_tree['index'] = feat
    ret_tree['value'] = val
    lset, rset = bin_split(dataset, feat, val)
    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  
create_tree(mydata)
mydata = np.mat(load_data('ex0.txt'))
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(mydata[:, 1].T.A[0], mydata[:, 2].T.A[0])
create_tree(mydata)<jupyter_output><empty_output><jupyter_text>树剪枝后剪枝伪代码：    基于已有的树：        如果子集是子树，则递归剪枝        计算两个叶子节点合并后的误差        计算不合并的误差        如果合并降低误差，则更新<jupyter_code>def is_tree(obj):
    return isinstance(obj, dict)

def get_mean(tree):
    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, testdata):
    if np.shape(testdata)[0] == 0:
        return get_mean(tree)
    if (is_tree(tree['right'])) or (is_tree(tree['left'])):
        lset, rset = bin_split(testdata, tree['index'], tree['value'])
    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(testdata, tree['index'], tree['value'])
        err_no_merge = sum(np.power(lset[:, -1] - tree['left'], 2)) + sum(np.power(rset[:, -1] - tree['right'], 2))
        tree_mean = (tree['left'] + tree['right']) / 2.0
        err_merge = sum(np.power(testdata[:, -1] - tree_mean, 2))
        if err_merge < err_no_merge:
            print('merging')
            return tree_mean
        else:
            return tree
    else:
        return tree
    
def prune(tree, testData):
    if np.shape(testData)[0] == 0: return get_mean(tree) #if we have no test data collapse the tree
    if (is_tree(tree['right']) or is_tree(tree['left'])):#if the branches are not trees try to prune them
        lSet, rSet = bin_split(testData, tree['index'], tree['value'])
    if is_tree(tree['left']): tree['left'] = prune(tree['left'], lSet)
    if is_tree(tree['right']): tree['right'] =  prune(tree['right'], rSet)
    #if they are now both leafs, see if we can merge them
    if not is_tree(tree['left']) and not is_tree(tree['right']):
        lSet, rSet = bin_split(testData, tree['index'], tree['value'])
        errorNoMerge = sum(np.power(lSet[:,-1] - tree['left'],2)) +\
            sum(np.power(rSet[:,-1] - tree['right'],2))
        treeMean = (tree['left']+tree['right'])/2.0
        errorMerge = sum(np.power(testData[:,-1] - treeMean,2))
        if errorMerge < errorNoMerge: 
            print("merging")
            return treeMean
        else: return tree
    else: return tree
mymat = np.mat(load_data('ex00.txt'))
mytree = create_tree(mymat, ops=(0,1))
mytest = np.mat(load_data('ex2test.txt'))
prune(mytree, mytest)<jupyter_output>merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging
merging<jupyter_text>模型树上节的树只是简单地将叶节点设定为均值，本节的树是将叶子节点设定为分段线性函数。模型树的可解释性是它优于回归树的特点之一。<jupyter_code>mymat2 = np.mat(load_data('exp2.txt'))
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(mymat2[:, 0].T.A[0], mymat2[:, 1].T.A[0])
def linear_solve(dataset):   
    m,n = np.shape(dataset)
    X = np.mat(np.ones((m,n))); Y = np.mat(np.ones((m,1)))
    X[:,1:n] = dataset[:,0:n-1]; Y = dataset[:,-1]
    xTx = X.T*X
    if np.linalg.det(xTx) == 0.0:
        raise NameError('This matrix is singular, cannot do inverse,\n\
        try increasing the second value of ops')
    ws = xTx.I * (X.T * Y)
    return ws,X,Y

def model_leaf(dataset):
    ws,X,Y = linear_solve(dataset)
    return ws

def model_err(dataset):
    ws,X,Y = linear_solve(dataset)
    yHat = X * ws
    return sum(np.power(Y - yHat,2))
create_tree(mymat2, model_leaf, model_err, (1,10))<jupyter_output><empty_output><jupyter_text>树回归和标准回归的比较<jupyter_code>def reg_tree_eval(model, indata):
    return float(model)


def model_tree_eval(model, indata):
    n = np.shape(indata)[1]
    x = np.mat(np.ones((1, n+1)))
    x[:, 1: n+1] = indata
    return float(x * model)


def tree_forecast(tree, indata, model_eval = reg_tree_eval):
    if not is_tree(tree):
        return model_eval(tree, indata)
    if indata[tree['index']] > tree['value']:
        if is_tree(tree['left']):
            return tree_forecast(tree['left'], indata, model_eval)
        else:
            return model_eval(tree['left'], indata)
    else:
        if is_tree(tree['right']):
            return tree_forecast(tree['right'], indata, model_eval)
        else:
            return model_eval(tree['right'], indata)

        
def create_forecast(tree, testdata, model_eval = reg_tree_eval):
    m = len(testdata)
    yhat = np.mat(np.zeros((m, 1)))
    for i in range(m):
        yhat[i, 0] = tree_forecast(tree, np.mat(testdata[i]), model_eval)
    return yhat
train_mat = np.mat(load_data('bikeSpeedVsIq_train.txt'))
test_mat = np.mat(load_data('bikeSpeedVsIq_test.txt'))
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(train_mat[:, 0].T.A[0], train_mat[:, 1].T.A[0])<jupyter_output><empty_output><jupyter_text>创建回归树<jupyter_code>mytree1 = create_tree(train_mat, ops=(1,20))
yhat1  = create_forecast(mytree1, test_mat[:, 0])
np.corrcoef(yhat1, test_mat[:, 1], rowvar=0)[0, 1]<jupyter_output><empty_output><jupyter_text>创建模型树<jupyter_code>mytree2 = create_tree(train_mat, model_leaf, model_err, (1,20))
yhat2 = create_forecast(mytree2, test_mat[:, 0], model_tree_eval)
np.corrcoef(yhat2, test_mat[:, 1], rowvar=0)[0, 1]
ws,x,y = linear_solve(train_mat)
ws
for i in range(np.shape(test_mat)[0]):
    yhat[i] = test_mat[i, 0] * ws[1,0] + ws[0,0]
np.corrcoef(yhat, test_mat[:, 1], rowvar=0)[0, 1]<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.15345969399406256, 'fraction_numerical': 0.017469741950216944, 'mean_word_length': 3.7889557135046474, 'pattern_counts': {'":': 0, '<': 33, '<?xml version=': 0, '>': 26, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '387755', 'license': 'MIT', 'n_tokens_mistral': 3673, 'n_tokens_neox': 3775, 'n_words': 657, 'path': 'CART/CART.ipynb', 'repo_name': 'Dream-Fu/ML_In_Action', 'size': '8758'}