PS：该系列数据都可以在图灵社区（点击此链接）中随书下载中下载（如下）

1 复杂数据的局部性建模

树回归 优点：可以对复杂和非线性的数据建模。 缺点：结果不易理解。 适用数据类型：数值型和标称型数据。

  之前决策树适用的算法是ID3，其做法是每次选取当前最佳的特征来分割数据，并按照该特征的所有可能取值来切分。也就是说，如果一个特征有4中取值，那么数据将被切成4份。一旦按某特征切分后，该特征在之后的算法执行过程中将不会再起作用，这种切分方式过于迅速。ID3算法也不能直接处理连续型变量。   另一种方法是二元切分法，即每次把数据集切成两份。易于对树构建过程进行调整以处理连续型特征，具体做法是：如果特征值大于给定值就走左子树，否则就走右子树。   CART（Classification And Regression Trees，分类回归树） 是十分著名的树构建算法，它使用二元切分来处理连续型变量。

2 连续和离散型特征的树的构建

  python中可以直接使用字典来存储树结构而无需另外自定义一个类，从而有效地减少代码量。下面会构建两种树：回归树（regression tree），其每个叶节点包含单个值；模型树（model tree），其每个叶节点包含一个线性方程。   共用函数createTree()伪代码：

找到最佳的待切分特征： 如果该节点不能再分，将该节点存为叶节点 执行二元切分 在右子树调用createTree()方法 在左子树调用createTree()方法

  创建文件regTrees.py，并在python命令行进行测试：

import numpy as np import matplotlib.pyplot as plt def loadDataSet(fileName): dataMat = [] with open(fileName, 'r') as fileObject: for line in fileObject.readlines(): curLine = line.strip().split('\t') fltLine = list(map(float, curLine)) dataMat.append(fltLine) return dataMat def binSplitDataSet(dataSet, feature, value): '''根据待切分的feature和值value执行二元切分''' mat0 = dataSet[np.nonzero(dataSet[:, feature] > value)[0], :] mat1 = dataSet[np.nonzero(dataSet[:, feature] <= value)[0], :] return mat0, mat1

3 将CART算法用于回归

  数据集混乱度计算：首先计算所有数据的均值，然后计算每条数据的值到均值的差值。为了对正负差值同等看待，一般使用绝对值或者平方值来代替上述差值，所以这里使用平方误差的总值（总方差）。

3.1 构建树

  需要编写函数chooseBestSplit()，该函数的目标是找到数据集切分的最佳位置。它遍历所有的特征及其可能的取值来找到使误差最小化的切分阈值。伪代码如下：

对每个特征： 对每个特征值： 将数据集切分成两份 计算切分的误差 如果当前误差小于当前最小误差，那么将当前切分设定为最佳切分并更新最小误差 返回最佳切分的特征和阈值

  添加代码，把数据文件拷贝到regTrees.py所在文件夹，并进行测试：

def regLeaf(dataSet): '''返回叶节点''' return np.mean(dataSet[:, -1]) def regErr(dataSet): '''返回平方误差''' return np.var(dataSet[:, -1]) * np.shape(dataSet)[0] def choseBestSplit(dataSet, leafType=regLeaf, errType=regErr, ops=(1, 4)): '''找到数据的最佳二元切分方式，生成相应的叶节点''' tolS = ops[0] #容许的误差下降值 tolN = ops[1] #切分的最少样本数 if len(set(dataSet[:, -1].T.tolist()[0])) == 1: #如果所有特征值相等则退出 return None, leafType(dataSet) m, n = np.shape(dataSet) S = errType(dataSet) bestS = float('inf') bestIndex = 0 bestValue = 0 #所有可能的特征和可能的取值上遍历 for featIndex in range(n-1): for splitVal in set((dataSet[:, featIndex].T.A.tolist())[0]): mat0, mat1 = binSplitDataSet(dataSet, featIndex, splitVal) if np.shape(mat0)[0] < tolN or np.shape(mat1)[0] < tolN: continue newS = errType(mat0) + errType(mat1) if newS < bestS: bestIndex = featIndex bestValue = splitVal bestS = newS if (S - bestS) < tolS: #如果误差减少不大则退出 return None, leafType(dataSet) mat0, mat1 = binSplitDataSet(dataSet, bestIndex, bestValue) if np.shape(mat0)[0] < tolN or np.shape(mat1)[0] < tolN: #如果切分出的数据集很小则退出 return None, leafType(dataSet) return bestIndex, bestValue def createTree(dataSet, leafType=regLeaf, errType=regErr, ops=(1, 4)): ''' 树构建函数 leafType: 建立叶节点的函数 errType: 误差计算函数 ops: 树构建所需其他参数的元组 ''' feat, val = choseBestSplit(dataSet, leafType, errType, ops) if feat == None:#满足停止条件时返回叶子节点 return val retTree = {} retTree['spInd'] = feat retTree['spVal'] = val lSet, rSet = binSplitDataSet(dataSet, feat, val) retTree['left'] = createTree(lSet, leafType, errType, ops) retTree['right'] = createTree(rSet, leafType, errType, ops) return retTree def plotSplitData(fileName): '''数据可视化''' myDat = loadDataSet(fileName) myMat = np.mat(myDat) createTree(myMat) if fileName == 'ex00.txt' or fileName == 'ex2.txt': plt.plot(myMat[:, 0], myMat[:, 1], 'ro') elif fileName == 'ex0.txt': plt.plot(myMat[:, 1], myMat[:, 2], 'ro') plt.show()

3.2 运行代码

  第一幅图是基于CART算法构建回归树的简单数据集；第二幅图是用于测试回归树的分段常数数据集。

4 树剪枝

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

4.1 预剪枝

  这是ex2.txt中的数据集，它和上面ex00.txt的数据集相似，只是y轴数量级是ex00.txt的100倍，然后用该数据集构建一棵新的树会产生很多叶节点，而ex00.txt只会产生两个叶节点（见下图）。产生这一现象的原因在于，停止条件tolS对误差的数量级十分敏感。如果在选项中花费时间并对上述误差容忍度取平方值，或许也能得到仅有两个叶节点的树（见下图）。   然而，通过不断修改停止条件来得到合理结果并不是很好的办法。所以产生了利用测试集来对树进行剪枝的办法，即后剪枝是一个更理想化的剪枝方法。

4.2 后剪枝

  使用后剪枝方法需要将数据集分成测试集和训练集。首先指定参数，使得构建出的树足够大、足够复杂，便于剪枝。接下来从上而下找到叶节点，用测试集来判断将这些叶节点合并是否能降低测试误差。如果是的话就合并。   函数prune()的伪代码如下：

基于已有的树切分测试数据： 如果存在任一子集是一棵树，则在该子集递归剪枝规程 计算将当前两个叶节点合并后的误差 计算不合并的误差 如果合并会降低误差的话，就将叶节点合并 def isTree(obj): '''判断输入变量是否是一棵树''' return (type(obj).__name__ == 'dict') def getMean(tree): '''对树进行塌陷处理（即返回树平均值）''' if isTree(tree['right']): tree['right'] = getMean(tree['right']) if isTree(tree['left']): tree['left'] = getMean(tree['left']) return (tree['left'] + tree['right']) / 2.0 def prune(tree, testData): ''' 回归树剪枝函数 tree：待剪枝的树 testData：剪枝所需的测试数据 ''' if np.shape(testData)[0] == 0: return getMean(tree) #假设发生过拟合，采用测试数据对树进行剪枝 if isTree(tree['right']) or isTree(tree['left']): lSet, rSet = binSplitDataSet(testData, tree['spInd'], tree['spVal']) if isTree(tree['left']): tree['left'] = prune(tree['left'], lSet) if isTree(tree['right']): tree['right'] = prune(tree['right'], rSet) #剪枝后判断是否还有有子树的树 if not isTree(tree['left']) and not isTree(tree['right']): lSet, rSet = binSplitDataSet(testData, tree['spInd'], tree['spVal']) #对合并前后误差进行比较，如果合并后的误差比不合并的误差小就进行合并操作 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

  利用ex2test.txt测试集数据对之前构建的“过拟合”树进行剪枝会发现大量叶节点被剪枝掉了，但没有像预期的那样剪枝成两部分，这说明后剪枝可能不如预剪枝有效。一般地，为了寻求最佳模型可以同时使用两种剪枝技术。

5 模型树

  可以把叶节点设定为分段线性函数，这里所谓的分段线性（piecewise linear） 是指模型由很多线性片段组成。   考虑上图的数据，如果使用两条直线拟合会比使用一组常数来建模好。可以设计两条分别从0.0 ~ 0.3、从0.3 ~ 1.0的直线，于是就可以得到两个线性模型。   对于给定的数据集，应该先用线性的模型来对它进行拟合，然后计算真实的目标值与模型预测值间的差值。最后将这些差值的平方求和就得到了所需的误差。

def linearSolve(dataSet): '''线性回归处理''' m, n = np.shape(dataSet) #将X于Y中的数据格式化 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 increasting the second value of ops") ws = xTx.I * (X.T * Y) return ws, X, Y def modelLeaf(dataSet): '''生成叶节点模型''' ws, X, Y = linearSolve(dataSet) return ws def modelErr(dataSet): '''计算给定数据集的误差''' ws, X, Y = linearSolve(dataSet) yHat = X * ws return sum(np.power(Y - yHat, 2))

  可以看到代码以0.285477为界创建了两个模型：$y=3.468+1.1852x$和$y=0.0016985+11.96477x$，与生成该数据的真实模型非常接近。   评价模型树、回归树等模型好坏，可以用相关系数，也称$R^2$值。该相关系数可以使用numpy库中的命令np.corrcoef(yHat, y, rowvar=0)来求解，其中yHat是预测值，y是目标变量的实际值。

6 树回归与标准回归的比较

def regTreeEval(model, inDat): '''回归树节点''' return float(model) def modelTreeEval(model, inDat): '''模型树节点''' n = np.shape(inDat)[1] X = np.mat(np.ones((1, n+1))) X[:, 1:n+1] = inDat return float(X * model) def treeForeCast(tree, inData, modelEval=regTreeEval): '''对于输入的单个数据点或行向量，返回一个预测值''' if not isTree(tree): return modelEval(tree, inData) if inData[tree['spInd']] > tree['spVal']: if isTree(tree['left']): return treeForeCast(tree['left'], inData, modelEval) else: return modelEval(tree['left'], inData) else: if isTree(tree['right']): return treeForeCast(tree['right'], inData, modelEval) else: return modelEval(tree['right'], inData) def createForeCast(tree, testData, modelEval=regTreeEval): '''对数据进行树结构建模''' m = len(testData) yHat = np.mat(np.zeros((m, 1))) for i in range(m): yHat[i, 0] = treeForeCast(tree, np.mat(testData[i]), modelEval) return yHat

  从测试结果可以看到，该数据集下，标准线性回归方法在$R^2$值上的表现不如两种树的回归方法，树的回归方法中模型树好于回归树。

7 使用Python的Tkinter库创建GUI

7.1 用Tkinter创建GUI

  Tinker的GUI由一些小部件（Widget）组成。所谓小部件，指的是文本框（Text Box）、按钮（Button）、标签（Label）和复选按钮（Check Button）等对象。

from tkinter import * root = Tk() myLabel = Label(root, text="Hello World") myLabel.grid() root.mainloop()

  上述代码就能创建一个GUI窗口，显示Hello World。

7.2 集成Matplotlib和Tkinter

  通过修改Matplotlib后端（设置后端为TkAgg）可以达到在Tkinter的GUI上绘图的目的。TkAgg可以在所选GUI框架上调用Agg（Agg是一个C++的库，可以从图像创建光栅图），把Agg呈现在画布上。   创建新的Python文件treeExplore.py：

import numpy as np from tkinter import * import regTrees import matplotlib #将TkAgg和Matplotlib库图链接起来 matplotlib.use("TkAgg") from matplotlib.backends.backend_tkagg import FigureCanvasTkAgg from matplotlib.figure import Figure def reDraw(tolS, tolN): reDraw.f.clf() reDraw.a = reDraw.f.add_subplot(111) #根据复选框是否被选中,确定构建模型树还是回归树 if chkBtnVar.get(): if tolN < 2: tolN = 2 myTree = regTrees.createTree(reDraw.rawDat, regTrees.modelLeaf, regTrees.modelErr, (tolS, tolN)) yHat = regTrees.createForeCast(myTree, reDraw.testDat, regTrees.modelTreeEval) else: myTree = regTrees.createTree(reDraw.rawDat, ops=(tolS, tolN)) yHat = regTrees.createForeCast(myTree, reDraw.testDat) reDraw.a.scatter(np.array(reDraw.rawDat[:, 0]), np.array(reDraw.rawDat[:, 1]), s=5) reDraw.a.plot(reDraw.testDat, yHat, linewidth=2.0) reDraw.canvas.draw() def getInputs(): try: tolN = int(tolNentry.get()) except: #清除错误的输入并用默认值替换 tolN = 10 print("enter Integer for tolN") tolNentry.delete(0, END) tolNentry.insert(0, '10') try: tolS = float(tolSentry.get()) except: tolS = 1.0 print("enter Float for tolS") tolSentry.delete(0, END) tolSentry.insert(0, '1.0') return tolN, tolS def drawNewTree(): tolN, tolS = getInputs() reDraw(tolS, tolN) root = Tk() reDraw.f = Figure(figsize=(5, 4), dpi=100) reDraw.canvas = FigureCanvasTkAgg(reDraw.f, master=root) reDraw.canvas.draw() reDraw.canvas.get_tk_widget().grid(row=0, columnspan=3) Label(root, text="tolN").grid(row=1, column=0) #文本输入框 tolNentry = Entry(root) tolNentry.grid(row=1, column=1) tolNentry.insert(0, '10') Label(root, text="tolS").grid(row=2, column=0) tolSentry = Entry(root) tolSentry.grid(row=2, column=1) tolSentry.insert(0, '1.0') Button(root, text="ReDraw", command=drawNewTree).grid(row=1, column=2, rowspan=3) #按钮整数值 chkBtnVar = IntVar() #复选按钮 chkBtn = Checkbutton(root, text="Model Tree", variable=chkBtnVar) chkBtn.grid(row=3, column=0, columnspan=2) reDraw.rawDat = np.mat(regTrees.loadDataSet('sine.txt')) reDraw.testDat = np.arange(min(reDraw.rawDat[:, 0]), max(reDraw.rawDat[:, 0]), 0.01) reDraw(1.0, 10) root.mainloop()

  通过命令python treeExplore.py运行上述代码：   勾选Model Tree框之后绘制模型树曲线如下：   还可以修改tolN，tolS等值观察执行效果。

小结

  数据集中经常包含一些复杂的相互关系，使得输入数据和目标变量之间呈现非线性关系。对这些复杂的关系建模，一种可行的方式是使用树来对预测值分段，包括分段常数或分段直线，相应地，若叶节点使用的模型是分段常数则称回归树，若叶节点使用的模型是线性回归方程则称模型树。   CART算法可以用于构建二元树并处理离散型或连续型数据的切分