机器学习实战—树回归

线性回归包含了一些强大的方法，但这些方法创建的模型需要拟合所有的样本点（局部加权线性回归除外）。当数据拥有众多特征并且特征之间关系十分复杂时，构建全局模型的想法就太难了。一种可行的办法是将数据集切分成很多份易建模的数据，然后利用线性回归建模，如果首次切分后仍然难以拟合线性模型就继续切分，在这种切分方式下，树结构和回归法就很有用。

这里介绍一种即可用于分类还可以用于回归的CART树构建算法。之后引入一个更加高级的模型树算法，与回归树不同，该算法需要在每个叶节点上都构建出一个线性模型。

一、复杂数据的局部性建模

决策树是一种贪心算法，它要在给定时间内做出最佳选择，但是并不关心能否达到全局最优。

之前使用的树构建算法是ID3，ID3的做法是每次选取当前最佳的特征来分割数据，并按照该特征的所有可能取值来切分，一旦按某特征切分后，该特征在之后的算法执行过程中将不再起作用，这种切分算法过于迅速。另外一种方法是二元切分法。即每次把数据集切分成两份。如果数据的某特征值等于切分所要求的值，那么这些数据就进入树的左子树，反之则进入树的右子树。

二元切分法易于对树构建过程进行调整以处理连续型特征。具体处理方法是：如果特征值大于给定值就进入左子树，否则就进入右子树。

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

这里使用一部字典来存储树的数据结构，该字典包含以下4个元素：

待切分的特征、待切分的特征值、右子树（当不再需要切分的时候，也可以是单个值）、左子树（与右子树类似）

CART算法只做二元切分，所以这里可以固定树的数据结构。树包含左键和右键，可以存储另一颗子树或者单个值。字典还包含特征和特征值这两个键，它们给出切分算法所有的特征和特征值。

本文将构建两种树：第一种是回归树，其每个叶节点包含单个值；第二种是模型树，其每个叶节点包含一个线性方程。

构建树函数伪代码：

找到最佳的切分特征：

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

执行二元切分

在右子树调用createTree()方法

在左子树调用createTree()方法

CART算法的实现代码：

import numpy as np

#加载数据集
def loadDataSet(filename):
    dataSet = []
    fp = open(filename)
    for line in fp.readlines():
        curLine = line.strip().split('\t')
        #将每行中的数据映射为浮点数
        fltLine = list(map(float,curLine))
        dataSet.append(fltLine)
    return dataSet

#二值切分
def binSplitDataSet(dataSet, feature, value):
    #np.nonzero()函数返回数组中非零数据的索引值数组
    #利用数组过滤得到左子树集
    #返回左子树集的第一个样本，构建回归树时每次只需要返回集合中的第一条样本
    leftSet = dataSet[np.nonzero(dataSet[:,feature]>value)[],:]
    #返回左子树矩阵
    # leftSet = dataSet[np.nonzero(dataSet[:, feature] > value)[0], :][0]
    # 利用数组过滤得到右子树集
    # 返回右子树集的第一个样本
    rightSet = dataSet[np.nonzero(dataSet[:, feature] <= value)[],:]
    # 返回右子树矩阵
    # rightSet = dataSet[np.nonzero(dataSet[:, feature] <= value)[0], :][0]
    return leftSet,rightSet

三、将CART算法用于回归

为成功构建以分段常数为叶节点的树，需要度量出数据的一致性，事实上，在数据集上计算混乱度是非常简单的，首先计算所有数据的均值，然后计算每条数据的值到均值的差值。为了对正负值同等看待，一般使用绝对值或平方值来代替上述差值，上述做法有点类似于统计学中常用的方差计算。唯一不同的是，方差是平方误差的均值（均方差），二而这里需要的是平方误差的总值，总方差可以通过均方差乘以数据集中样本点的个数来得到。

1.构建树

回归树的切分函数：

#因为在进行二元划分时，最后一次划分的每个子集不一定就只含有一个数据样本，大多数情况都是子集中有多个样本
#但是叶节点值却只能为一个，所以在创建叶节点时需要使用函数对叶节点值进行计算并指定，回归树中的叶节点值为最终子节样本目标值的均值
#计算叶节点值的函数
def regLeaf(dataSet):
    return np.mean(dataSet[:,-])

def regErr(dataSet):
    #返回此数据集中目标值列的总方差和（均方误差和*集合样本数）
    return np.var(dataSet[:,-])*np.shape(dataSet)[]

#寻找最佳切分特征及切分值函数
def chooseBestSplit(dataSet,leafType=regLeaf,errType=regErr,ops=(,)):
    #获取参数中的误差减少限度
    tolS = ops[]
    #获取划分子集最小样本数量
    tolN = ops[]
    #数据集划分停止条件：
    #1.划分子集中的目标值相同，则不需要继续划分
    if (len(set(dataSet[:,-].T.tolist()[]))==):
        return None,leafType(dataSet)
    m,n = np.shape(dataSet)
    #计算为划分数据集的总方差和
    S = errType(dataSet)
    #定义最小方差和为无穷
    bestS = np.inf
    #初始化最佳特征索引值和最佳划分值
    bestIndex = 
    bestValue = 
    #遍历所有特征,数据集中最后一列是目标值，不是特征列
    for featIndex in range(n-):
        #遍历每一个特征的所有取值
        #for splitValue in set(dataSet[:,featIndex]):   #python2.x用法
        for splitValue in set(dataSet[:,featIndex].T.A.tolist()[]):  #python3.x用法
            #进行二值划分
            matLeft,matRight = binSplitDataSet(dataSet,featIndex,splitValue)
            #如果划分的数据集样本数小于指定数，则重新划分
            if ((np.shape(matLeft)[]<tolN) or (np.shape(matRight)[])<tolN):
                continue
            #计算划分后的总误差
            newS = errType(matLeft)+errType(matRight)
            #判断是否为最小误差，如果是，将相应信息保存
            if newS < bestS:
                bestIndex = featIndex
                bestValue = splitValue
                bestS = newS
    #遍历完成之后，判断另外两个切分停止条件
    #2.划分后的最小划分相对与原始误差和的减小幅度小于1则停止划分
    if (S - bestS) < tolS:
        return None,leafType(dataSet)
    #3.如果根据选择出的最佳特征和最佳划分值划分的子集样本数小于一定值，则停止划分
    mat0,mat1 = binSplitDataSet(dataSet,bestIndex,bestValue)
    if ((np.shape(mat0)[]<tolN) or (np.shape(mat1)[]<tolN)):
        return None,leafType(dataSet)
    #如果没有在之前跳出，则说明可划分
    return bestIndex,bestValue

#创建回归树,输入参数中leafType=regLeaf(指定叶节点值的函数引用),errType=regErr(指定误差函数的引用)
#ops=(1,4)(ops[0]指定为切分误差总和与切分后误差总和的变化停止限度),ops[1]指定切分数据集的最小样本数量
def createTree(dataSet,leafType=regLeaf,errType=regErr,ops=(,)):
    #获取最佳划分特征和划分值
    feat,val = chooseBestSplit(dataSet,leafType,errType,ops)
    #设置递归停止条件
    if feat == None:
        return val
    #定义树，树的存储结构为字典
    retTree = {}
    retTree['spInd'] = feat
    retTree['spVal'] = val
    leafSet,rightSet = binSplitDataSet(dataSet,feat,val)
    #递归创建树节点
    retTree['left'] = createTree(leafSet,leafType,errType,ops)
    retTree['right'] = createTree(rightSet,leafType,errType,ops)
    return retTree

四、树剪枝

完成回归树的构建后，需要某种措施来检查构建过程是否得当。树剪枝技术通过对决策树剪枝来达到更好的预测效果。

通过降低决策树的复杂度来避免过拟合的过程称为剪枝，在函数ChooseBestSplit()中的提前终止条件，实际上是在进行一种所谓的预剪枝操作，另一种形式的剪枝是需要使用测试集和训练集，称作后剪枝。

1.后剪枝

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

基于已有的树切分测试数据：

如果存在任一子集是一棵树，则在该子集递归剪枝过程

计算将当前两个叶节点合并后的误差

计算不合并的误差

如果合并会降低误差的话，就将叶节点合并

回归树剪枝函数：

#后剪纸操作，利用训练集创建好树之后。根据测试数据集进行后剪枝处理
#测试输入对象是否为树
def isTree(obj):
    #树结构是用python中的字典存储的，所以只用判断该对象类型是否为dict
    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'])/

#树剪枝函数
def prune(tree,testSet):
    #如果测试集样本数为空，则对树进行塌陷处理，返回树节点的均值，剪枝到最后测试集空的情况
    if (np.shape(testSet)[]==):
        return getMean(tree)
    #如果测试集不为空，如果左子树或者右子树还是树的话，则对测试集进行切分，将切分数据传入剪枝函数中对树结构进行递归剪枝
    #获取到下一次递归中的测试数据集
    if( isTree(tree['right'])or isTree(tree['left']) ):
        lSet, rSet = binSplitDataSet(testSet,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(testSet, tree['spInd'], tree['spVal'])
        #计算没有合并的误差和
        notMergeErr = sum(np.power(lSet[:,-] - tree['left'],)) + sum(np.power(rSet[:,-] - tree['right'],))
        #计算合并的话节点值,已经到了叶节点，所以之间计算平均值
        meanNodeNum = (tree['left'] + tree['right'])/
        #计算合并后的误差和
        mergeErr = sum(np.power(testSet[:,-] - meanNodeNum,))
        #如果合并后的误差方和减少了，则合并
        if mergeErr < notMergeErr:
            print("merge")
            return meanNodeNum
        #否则，返回该树
        else:
            return tree
    #最后返回完成剪枝之后的树
    else:
        return tree

五、模型树

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

模型树的叶节点生成函数：

#在创建树函数中，叶节点的模式函数和误差计算函数参数是通过函数引用给出的，模式树的构建过程与回归树的构建过程是一致的
#只是模式树的节点不是数值，而是回归函数（叶节点模式），误差计算函数也和回归树中误差计算不一样，所以模式树构建只需要传入这两个函数的应用就可实现树的构建
#对数据集进行标准线性回归，返回系数向量X矩阵和Y矩阵
def linearSlove(dataSet):
    #dataSet中包含了目标值列,标准线性回归中需要加入一列1，是为了将截距b的值加入ws向量中一起求出
    #获取数据集的行列大小
    m,n = np.shape(dataSet)
    #创建m*n大小的全1矩阵,这里相当于覆盖x矩阵中的最后一列
    X = np.mat(np.ones((m,n)))
    Y = np.mat(np.ones((m,)))
    X[:,:n] = dataSet[:,:n-]
    Y = dataSet[:,-]
    xtx = X.T*X
    if np.linalg.det(xtx) == :
        raise NameError("矩阵不可逆")
    ws = xtx.I * (X.T*Y)
    return ws,X,Y

#叶节点模式函数
def modelLeaf(dataSet):
    ws,X,Y = linearSlove(dataSet)
    #叶节点模式函数返回回归系数向量
    return ws

#计算误差函数
def modelErr(dataSet):
    ws, X, Y = linearSlove(dataSet)
    #预测
    yHat = X * ws
    return sum(np.power(Y - yHat,))

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

用树回归进行预测的代码：

#回归树预测
def regTreeEval(model,inDat):
    return float(model)

#模型树预测,inDat是单个样本向量
def modelTreeEval(model,inDat):
    n = np.shape(inDat)[]
    X = np.mat(np.ones((,n+)))
    X[:,:n+] = 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,)))
    #遍历整个样本集，对每个测试样本进行预测
    for i in range(m):
        yHat[i,] = treeForeCast(tree,np.mat(testData[i]),modelEval)
    return yHat

注：以上函数测试都在main函数中进行，main函数如下：

if __name__ == "__main__":
    #造数据，对二元划分函数进行测试
    # testMat = np.eye()
    # print("testMat:\n",testMat)
    # leftSet, rightSet = binSplitDataSet(testMat,,)
    # print("leftSet:\n",leftSet)
    # print("rightSet:\n",rightSet)

    #创建回归树,ex00.txt文件数据
    # dataMat = loadDataSet('ex00.txt')
    # dataMat = np.mat(dataMat)
    # myTree_0 = createTree(dataMat)
    # print("myTree_0:\n",myTree_0)

    #ex0.txt文件数据
    # dataMat = loadDataSet('ex0.txt')
    # dataMat = np.mat(dataMat)
    # myTree_1 = createTree(dataMat)
    # print("myTree_1:\n", myTree_1)

    #后剪枝测试
    # dataMat2 = loadDataSet('ex2.txt')
    # dataMat2 = np.mat(dataMat2)
    # dataMat2Test = loadDataSet('ex2test.txt')
    # dataMat2Test = np.mat(dataMat2Test)
    # #构建最复杂的树结构，用来进行后剪枝操作
    # myTree_2 = createTree(dataMat2,ops=(,))
    # myTree_pruned = prune(myTree_2,dataMat2Test)
    # print("myTree_pruned:\n",myTree_pruned)

    #模型树的构建
    # dataSet = np.mat(loadDataSet('exp2.txt'))
    # myTree_model = createTree(dataSet,modelLeaf,modelErr,(,))
    # print("myTree_model:\n",myTree_model)
    # trainSet = np.mat(loadDataSet('bikeSpeedVsIq_train.txt'))
    # testSet = np.mat(loadDataSet('bikeSpeedVsIq_test.txt'))
    #
    # #回归树预测
    # myTree = createTree(trainSet,ops=(,))
    # #数据集中最后一列是目标值
    # yHat = createForeCast(myTree,testSet[:,])
    # corr = np.corrcoef(yHat,testSet[:,],rowvar=)[,]
    # print("regTreeCorr:", corr)

    # #进行标准线性回归
    # ws,X,Y = linearSlove(trainSet)
    # print("ws:",ws)
    # yHat = np.zeros((np.shape(testSet)[],))
    # for i in range(np.shape(testSet)[]):
    #     yHat[i] = testSet[i,] * ws[,] + ws[,]
    # corr = np.corrcoef(yHat,testSet[:,],rowvar=)[,]
    # print("linerCorr:",corr)


    #进行模型树回归
    trainSet = np.mat(loadDataSet('bikeSpeedVsIq_train.txt'))
    testSet = np.mat(loadDataSet('bikeSpeedVsIq_test.txt'))

    # 回归树预测
    myTree = createTree(trainSet,modelLeaf,modelErr,ops=(, ))
    # 数据集中最后一列是目标值
    yHat = createForeCast(myTree, testSet[:, ],modelTreeEval)
    corr = np.corrcoef(yHat, testSet[:, ], rowvar=)[, ]
    print("modelTreeCorr:", corr)

七、使用Python的Tkinter库创建GUI及集成Matplotlib和Tkinter

使用Python来构建GUI，这里使用易于使用的Tkinter，Tkinter的GUI由一些小部件组成。

用于构建树管理器界面的Tkinter小部件、Matplotlib和Tkinter代码集成

from numpy import *

from tkinter import *
import treeRegression.treeReg

import matplotlib

#将matplotlib后端设置为TkAgg
matplotlib.use('TkAgg')
#将tkinter和matplotlib关联起来
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()
    if chkBtnVar.get():
        if tolN < : tolN = 
        myTree = treeRegression.treeReg.createTree(reDraw.rawDat,treeRegression.treeReg.modelLeaf, \
                                                   treeRegression.treeReg.modelErr, (tolS, tolN))
        yHat = treeRegression.treeReg.createForeCast(myTree, reDraw.testDat, \
                                                     treeRegression.treeReg.modelTreeEval)
    else:
        myTree = treeRegression.treeReg.createTree(reDraw.rawDat, ops=(tolS, tolN))
        yHat = treeRegression.treeReg.createForeCast(myTree, reDraw.testDat)
    #绘制散点图
    reDraw.a.scatter(reDraw.rawDat[:, ].tolist(), reDraw.rawDat[:, ].tolist(), s=)  # use scatter for data set
    #绘制连续图
    reDraw.a.plot(reDraw.testDat, yHat, linewidth=)  # use plot for yHat
    reDraw.canvas.show()


def getInputs():
    try:
        tolN = int(tolNentry.get())
    except:
        tolN = 
        print
        "tolN请输入整数值"
        tolNentry.delete(, END)
        tolNentry.insert(, '10')
    try:
        tolS = float(tolSentry.get())
    except:
        tolS = 
        print
        "tolS请输入浮点值"
        tolSentry.delete(, END)
        tolSentry.insert(, '1.0')
    return tolN, tolS


def drawNewTree():
    tolN, tolS = getInputs()  # 从输入框中获得输入值
    reDraw(tolS, tolN)

#创建跟部件
root = Tk()

reDraw.f = Figure(figsize=(, ), dpi=)  # 创建画布
reDraw.canvas = FigureCanvasTkAgg(reDraw.f, master=root)
reDraw.canvas.show()
reDraw.canvas.get_tk_widget().grid(row=, columnspan=)

#第二行标签
Label(root, text="tolN").grid(row=, column=)
tolNentry = Entry(root)
tolNentry.grid(row=, column=)
tolNentry.insert(, '10')
#第二行标签
Label(root, text="tolS").grid(row=, column=)
tolSentry = Entry(root)
tolSentry.grid(row=, column=)
tolSentry.insert(, '1.0')
#按钮
Button(root, text="ReDraw", command=drawNewTree).grid(row=, column=, rowspan=)
#复选框变量
chkBtnVar = IntVar()
chkBtn = Checkbutton(root, text="Model Tree", variable=chkBtnVar)
chkBtn.grid(row=, column=, columnspan=)
#获取变量
reDraw.rawDat = mat(treeRegression.treeReg.loadDataSet('sine.txt'))
reDraw.testDat = arange(min(reDraw.rawDat[:, ]), max(reDraw.rawDat[:, ]), )
reDraw(, )

root.mainloop()

总结：

1.数据集中经常包含一些复杂的相互关系，使得输入数据和目标变量之间呈现非线性关系。对这些复杂的关系建模，一种可行的方法是使用树来对预测值分段，包含分段函数或分段直线。一般采用树结构来对这种数据建模哦。如果使用的模型的叶节点是分段常数，那么这个模型是回归树；如果使用的模型的叶节点是线性回归方程，那么这个模型是模型树。

2.CART算法可以用于构建二元树并处理离散型或连续型数据的切分，若使用不同的误差测试，就可以通过CART算法构建模型树和回归树，该算法构建出的树会倾向于对数据过拟合，一颗过拟合的树常常十分复杂，剪枝技术的出现就是为了解决这个问题。

机器学习实战—树回归

继续阅读

简单文档分类——朴素贝叶斯算法朴素贝叶斯算法简单文档分类实例步骤总结朴素贝叶斯分类调用(sklearn)

【分类算法】什么是分类算法定义分类与聚类分类过程方法

分类算法的评价指标

K-近邻算法以及图像分类应用

weka之NB算法

使用weka的select attribute

weka中分类器算法

在weka中集成自己的算法

【多变量线性回归】学习记录序思路实现终

申请评分模型拒绝推断（RI）方法申请评分模型拒绝推断（RI）方法

【人工智能行业大师访谈1】吴恩达采访 Geoffery Hinton

【趋高机器视觉】机器视觉技术原理解析及解决方案

吴恩达 coursera ML 第七课总结+作业答案前言目录正文模型表示作业答案

XGBoost Plotting API以及GBDT组合特征实践 XGBoost Plotting API以及GBDT组合特征实践

解码器用于语义分割：数据依赖的解码可以实现灵活的特征聚合

2021-2025年中国运动疗法（KT）带行业市场供需与战略研究报告