树回归

柔情只为你懂 2022-06-01 01:21 241阅读 0赞

前面有篇讲过ID3决策树对标称型分类，其存在两大缺点：

1 每个特性只能参与一次切分，对后续切分不再起作用。

2 不能直接处理连续型特性。

本篇介绍的树回归，本质上也是通过二叉树的方式来进行分类回归，但是解决了ID3决策树中的这些缺点。

树回归分为3部分：树结构、叶子算法、树修剪。

树结构是骨干，描述了你的树是个什么样子的树，维护所有的迭代，有哪些重要的节点，预留了哪些需要实现的算法。

叶子算法是核心算法，每个叶子最终维护的内容是什么，如何进行误差判断和择优。

树修剪是树回归完成后是否满足需要，对枝叶进行修修剪剪。

树结构：

这里采用的是CART Classification And Regression Trees，分类回归树，使用二元切分来处理连续型变量

核心函数createTree()的伪代码大致如下：

找到最佳的待切分特征：

如果该节点不能再分，将该节点存为叶节点

执行二元切分

在右子树调用createTree()方法

在左子树调用createTree()方法

Python代码如下：

#与前面功能略有不同的是特性集和结果集都保存在dataMat中
    def loadDataSet (fileName) :
        numFeat = len(open(fileName).readline().split('\t'))
        dataMat = []
        fr = open(fileName)
        for line in fr.readlines() :
            lineArray = []
            oneLine = line.strip().split('\t')
            for i in range(numFeat) :
                lineArray.append(float(oneLine[i]))
            dataMat.append(lineArray)
        return dataMat
    
    #好理解，根据feature属性的value值做二分
    #小的分支放mat0里，大的分支放mat1里
    def binSplitDataSet(dataSet, feature, value):
        t = nonzero(dataSet[:,feature]<=value)
        tt = t[0]
        #如果a是一个高维数组，则索引值数组有两个array，第一个array从行维度来描述索引值；
        # 第二个array从列维度来描述索引值。
        #nonzero返回的不是数据本身，是索引
        mat0 = dataSet[nonzero(dataSet[:, feature] <= value)[0],:]
        mat1 = dataSet[nonzero(dataSet[:, feature] > value)[0], :]
        return mat0, mat1
    
    #获取最优的分割点
    def chooseBestSplit(dataSet, leafType=regLeaf, errType=regErr, ops=(1,4)):
        #变量tolS是容许的误差下降值，tolN是切分的最少样本数。
        tolS = ops[0]
        tolN = ops[1]
        #tolist将矩阵转为list,set这里用它的去重作用
        #如果dataSet的结果集都相等，直接返回
        if len(set(dataSet[:,-1].T.tolist()[0]))==1 :
            return None, leafType(dataSet)
        m,n = shape(dataSet)
        #未拆分前的均方差
        S = errType(dataSet)
        bestS = inf
        bestIndex = 0
        bestValue = 0
        #最后一列为结果集，这里要遍历特性集，所以要-1
        for featIndex in range(n-1) :
            #遍历某特性集的所有值
            #上下两个for循环想象下真是个巨大的计算量
            for splitValue in set(dataSet[:,featIndex].T.tolist()[0]) :
                #二分
                lSet, rSet = binSplitDataSet(dataSet, featIndex, splitValue)
                #如果两边有一个已经拆分的足够小，continue
                if shape(lSet)[0]<tolN or shape(rSet)[0]<tolN :
                    continue
                #为什么拆出来的均方差越小越优先选择？
                #均方差越小，说明拆出来的越‘平衡’
                newS = errType(lSet)+errType(rSet)
                if newS<bestS :
                    bestIndex = featIndex
                    bestValue = splitValue
                    bestS = newS
        #拆出来的结果不理想，直接结束
        if (S - bestS)<tolS :
            return None,leafType(dataSet)
        #利用最优的分发拆分
        lSet, rSet = binSplitDataSet(dataSet, bestIndex, bestValue)
        if shape(lSet)[0] < tolN or shape(rSet)[0] < tolN:
            return None, leafType(dataSet)
        #返回按哪个特性拆，按哪个值来拆
        return bestIndex,bestValue
    
    
    
    
    
    #二分的递归函数，chooseBestSplit和binSplitDataSet的递归
    #leafType是对创建叶节点的函数的引用，
    # errType是对总方差计算函数的引用
    # ops是一个用户定义的参数构成的元组，用以完成树的构建。
    def createTree(dataSet, leafType=regLeaf, errType=regErr, ops=(1,4)):
        #切分
        feat, val = chooseBestSplit(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

核心方法有2个：

如何决定拆分策略chooseBestSplit，这个里面就涉及到前面讲的叶子算法部分，不同的叶子算法拆分策略不同。但是逻辑主体都是一样的，只要拆分的粒度不够细（tolN）、只要还能减少足够大的误差（tolS），就要一直拆分下去，拆分是贪心的（最小误差法）

如何拆分为新的二叉树binSplitDataSet，这个是CART固定的套路，可以看得出一个特性将会参与多次拆分，避免了ID3中拆分过快的问题。

叶子算法：

叶子算法主要是为了弥补chooseBestSplit中的空缺，是拆分策略的核心算法，这里主要介绍两种：回归树和模型树

回归树，最终的叶子节点是常量，也就是说最终的回归结果是将某一部分相邻的样本归类为同一个常量值。

Python代码：

#构建常量型叶子节点
    def regLeaf(dataSet) :
        #最后一列求均值
        return mean(dataSet[:,-1])
    
    #常量型叶子节点误差
    def regErr(dataSet):
        #var = mean(abs(x - x.mean()) ** 2)
        #求均方差
        return (var(dataSet[:,-1]))*(shape(dataSet)[0])

测试代码（本文的测试用例都在git https://github.com/yejingtao/forblog/tree/master/MachineLearning/trainingSet/regTree上）：

dataMat = loadDataSet('C:\\2017\\提高\\机器学习\\训练样本\\regTree\\ex0.txt')
    dataMat = mat(dataMat)
    retTree  = createTree(dataMat)
    print(retTree)

结果：

{'spInd': 1, 'spVal': 0.39435, 'left': {'spInd': 1, 'spVal': 0.197834, 'left': -0.023838155555555553, 'right': 1.0289583666666666}, 'right': {'spInd': 1, 'spVal': 0.582002, 'left': 1.980035071428571, 'right': {'spInd': 1, 'spVal': 0.797583, 'left': 2.9836209534883724, 'right': 3.9871631999999999}}}

测试结果看得出是 5 个节点的树，每层树分割点和最终的常量结果都描述的很清楚。

模型树，最终的叶子结点是一个线性模型，也就是说将整体样本拆分成了N个局部线性。

假如我现在的数据是这个样子的，很明显呈现了局部线性，通过拐点出可以将其拆分成2个直线。

![20180116170517349][]

Python代码只需要替换2个叶子节点的算法:

#这是个典型的普通线性回归处理方式
    def linearSolve(dataSet) :
        m,n = shape(dataSet)
        X = mat(ones((m,n)))
        Y = mat(ones((m,1)))
        X[:,1:n] = dataSet[:,0:n-1]
        Y = dataSet[:,-1]
        xTx = X.T*X
        if linalg.det(xTx) ==0.0:
            raise NameError('This matrix is singular')
        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(power(Y-yHat,2))

结果：

trainingDataMat = loadDataSet('C:\\2017\\提高\\机器学习\\训练样本\\regTree\\exp2.txt')
    trainingDataMat = mat(trainingDataMat)
    myTree = createTree(trainingDataMat,modelLeaf,modelErr,(1,10))
    print(myTree)

{'spInd': 0, 'spVal': 0.285477, 'left': matrix([[ 3.46877936],
            [ 1.18521743]]), 'right': matrix([[  1.69855694e-03],
            [  1.19647739e+01]])}

对照着上图，在x= 0.285477出进行了2叉，左树为y=3.46877936+1.18521743\*x这条线；右树为y=1.69855694e-03+1.19647739e+01\*x这条线。左线x斜率为1.18，右线斜率为11.9，与图基本相符。

树修剪：

通过降低决策树的复杂度来避免过拟合的过程称为剪枝（pruning）。树修剪分为预剪枝和后剪枝。

预剪枝：在计算钱预先根据经验值的判断给与程序干预参数。其实前面演示的代码都属于预剪枝，我们在函数里添加了入参tolS和tolN，一个代表着每次修建的最小优化量，一个代表着修剪的最小叶子元素数，虽然上面案例产出的回归树比较理想，那是建立在准确的预剪枝参数基础上的，所以预剪枝虽然实现方便，但是对入参要求太高了。

后剪枝：将数据集分为训练集和测试集两部分，将训练集构建成足够“繁茂”的树然后用测试集去计算误差并进行修剪合并。如何构建足够“繁茂”的树？将ops设置为(0,1)就是了，每个样本都单独构成一个叶子。

后剪枝需要添加一个“剪刀”，python代码：

#判断当前处理对象是否为一棵树，如果不为数那就是叶子节点
    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) :
        if shape(testData)[0]==0 :
            return getMean(tree)
        #如果左右是分支，那么用其拆解测试集
        if (isTree(tree['right'])) or (isTree(tree['left'])) :
            #用训练集的拆分测率来拆解测试集
            lSet, rSet = binSplitDataSet(testData,tree['spInd'], tree['spVal'])
        #左递归prune
        if isTree(tree['left']) :
            #修剪左半支
            tree['left'] = prune(tree['left'],lSet)
        # 右递归prune
        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(power(lSet[:,-1]-tree['left'],2)) + sum(power(rSet[:,-1]-tree['right'],2))
            treeMean = (tree['left']+tree['right'])/2.0
            errorMerge = sum(power(testData[:,-1]-treeMean,2))
            if errorMerge < errorNoMerge :
                print('mering')
                return treeMean
            else :
                return tree
        else :
            return tree

测试代码：

trainingDataMat = loadDataSet('C:\\2017\\提高\\机器学习\\训练样本\\regTree\\ex2.txt')
    trainingDataMat = mat(trainingDataMat)
    myTree = createTree(trainingDataMat,ops=(0,1))
    testDataMat = loadDataSet('C:\\2017\\提高\\机器学习\\训练样本\\regTree\\ex2test.txt')
    testDataMat = mat(testDataMat)
    tree = prune(myTree,testDataMat)
    print(tree)

相关系数比较回归效果：

如何评价一个回归算法效果的好坏？这个在前一篇线性回归时已经介绍过了，需要引入相关系数。

添加两个函数，用于根据回归树对测试集进行预测：

#常量型预测
    def regTreeEval(tree, inDat):
        return float(tree)
    #线性预测
    def modelTreeEval(tree, inDat):
        n = shape(inDat)[1]
        X = mat(ones((1,n+1)))
        X[:,1:n+1] = inDat
        return float(X*tree)
    
    def treeForeCast(tree, inData, modelEval=regTreeEval) :
        if not isTree(tree) :
            return modelEval(tree, inData)
        if inData[tree['spInd']] > tree['spVal'] :
            if isTree(tree['right']) :
                return treeForeCast(tree['right'],inData, modelEval)
            else :
                return modelEval(tree['right'],inData)
        else :
            if isTree(tree['left']) :
                return treeForeCast(tree['left'],inData,modelEval)
            else :
                return modelEval(tree['left'],inData)
    
    def createForeCast(tree,testData, modelEval=regTreeEval) :
        m = len(testData)
        yHat = mat(zeros((m,1)))
        for i in range(m) :
            yHat[i,0] = treeForeCast(tree,mat(testData[i]),modelEval)
        return yHat

对回归树、模型树、普通线性 3 中算法进行实测：

trainingDataMat = loadDataSet('C:\\2017\\提高\\机器学习\\训练样本\\regTree\\bikeSpeedVsIq_train.txt')
    trainingDataMat = mat(trainingDataMat)
    testDataMat = loadDataSet('C:\\2017\\提高\\机器学习\\训练样本\\regTree\\bikeSpeedVsIq_test.txt')
    testDataMat = mat(testDataMat)
    #回归树进行训练
    myNomalTree = createTree(trainingDataMat,ops=(1,20))
    #回归树的预测
    yHat = createForeCast(myNomalTree,testDataMat[:,0])
    #求回归树的相关系数
    print('NomalTree: ',corrcoef(yHat,testDataMat[:,1],rowvar=0)[0,1])
    #0.964085231822
    #模型树进行训练
    myModelTree = createTree(trainingDataMat,modelLeaf,modelErr,ops=(1,20))
    #模型树的预测
    yHat = createForeCast(myModelTree,testDataMat[:,0],modelTreeEval)
    #求模型树的相关系数
    print('ModelTree: ',corrcoef(yHat,testDataMat[:,1],rowvar=0)[0,1])
    #普通线性回归
    ws,X,Y = linearSolve(trainingDataMat)
    #普通线性回归的预测
    m= shape(testDataMat)[0]
    newX = mat(ones((m,2)))
    newX[:,1] = testDataMat[:,0]
    yHat = newX*ws
    #求普通线性回归的相关系数
    print('Base regreesion: ',corrcoef(yHat,testDataMat[:,1],rowvar=0)[0,1])

测试结果：

NomalTree:  0.964085231822
    ModelTree:  0.976041219138
    Base regreesion:  0.943468423567

看得出至少对于这个测试用例，模型树表现是最好的。

学习了那么多回归方式，也知道了每种回归的优劣，怎么才能更直观的通过数据来判断我们需要采取哪种回归方式呢？

1 自己用matplotlib.pyplot写一个辅助类，打印二维坐标，但是这个仅满足展示，需要人肉分析，例如：

#二维打印
    def showData(xMat,yMat) :
        import matplotlib.pyplot as plt
        fig = plt.figure()
        ax = fig.add_subplot(111)
        ax.scatter(xMat[:, 0].flatten().A[0], yMat[:, 0].flatten().A[0])
        plt.show()

2 Tkinter模块，代码比较复杂，主要分前台控件和后台运算两部分，代码如下：

from tkinter import *
    from numpy import *
    import matplotlib
    matplotlib.use('TkAgg')
    from matplotlib.backends.backend_tkagg import FigureCanvasTkAgg
    from matplotlib.figure import Figure
    from regressTree import regTree
    
    
    
    #test
    def showTkinter() :
        root = Tk()
        myLabel = Label(root, text='Hello World')
        myLabel.grid()
        root.mainloop()
    
    def reDraw(tolS, tolN) :
        reDraw.f.clf()
        reDraw.a = reDraw.f.add_subplot(111)
        if chkBtnVar.get() :
            if tolN<2 :
                tolN = 2
            myTree = regTree.createTree(reDraw.rawDat, regTree.modelLeaf,regTree.modelErr,(tolS,tolN))
            yHat = regTree.createForeCast(myTree,reDraw.testDat,regTree.modelTreeEval)
        else :
            myTree = regTree.createTree(reDraw.rawDat,ops=(tolS,tolN))
            yHat = regTree.createForeCast(myTree, reDraw.testDat)
        t = reDraw.rawDat;
        reDraw.a.scatter(reDraw.rawDat[:,0].flatten().A[0],reDraw.rawDat[:,1].flatten().A[0],s=5)
        reDraw.a.plot(reDraw.testDat, yHat, linewidth=2.0)
        reDraw.canvas.show()
    
    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)
    
    trainingDataMat = regTree.loadDataSet('C:\\2017\\提高\\机器学习\\训练样本\\regTree\\sine.txt')
    root = Tk()
    #Label(root,text='plot place holder').grid(row=0,columnspan=3)
    reDraw.f = Figure(figsize=(5,4),dpi=100)
    reDraw.canvas = FigureCanvasTkAgg(reDraw.f, master=root)
    reDraw.canvas.show()
    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 = mat(trainingDataMat)
    reDraw.testDat = arange(min(reDraw.rawDat[:,0]),max(reDraw.rawDat[:,0]),0.01)
    reDraw(1.0,10)
    root.mainloop()
     效果如下： 上面两张图也直观的展示了模型树和回归树的回归效果，修改tolS和tolN也会对回归产生影响。

[20180116170517349]: /images/20220601/64a1cce51e5a438fb2cb9b4c0f50ae16.png