背景：线性回归需要拟合所有的数据才能生成模型，但是，当数据拥有众多的特征以及特征之间的关系十分复杂时，这种方法显得太难了。除此之外，实际生活中很多数据都是非线性的，不能使用全局线性模型进行拟合。因此提出树结构与回归法。

CART算法使用二元切分来处理连续性变量，ID3算法使用香农熵来度量集合的无组织程度，如果采用其他的度量就可以采用树构建算法完成回归树。回归树与分类树的思路类似，不过分类树的叶节点是离散型，回归树的叶节点是连续型。

将CART算法用于回归

from numpy import *
#加载数据
def loadDateSet(filename):
    fr = open(filename)
    dataMat = []
    for line in fr.readlines():
        currline = line.strip().split('\t')
        fltline = map(float,currline)
        dataMat.append(fltline)
    return dataMat
#切分数据，feature：待切分的特征，value:切分的特征值
def BinSplitDataSet(dataset,feature,value):
    #nonzero(a)返回元组a中非零元素的索引值，返回一个二维数组
    #第一个array从行维度来描述索引值；第二个array从列维度来描述索引值
    mat0 = dataset[nonzero(dataset[:,feature] > value)[0],:]
    mat1 = dataset[nonzero(dataset[:,feature] <= value)[0],:]
    return mat0,mat1

#负责生成叶节点，也就是目标变量的平均值
def regLeaf(dataSet):
    return mean(dataSet[:,-1])

#计算目标变量的平均误差
def regErr(dataSet):
    #var()是均方差函数，用均方差乘上样本个数即为总方差
    return var(dataSet[:,-1]) * shape(dataSet)[0]

def chooseBestSplit(dataSet,leafType=regLeaf,errType=regErr,ops=(1,4)):
    #tols与toln是用户指定的参数，用于控住函数的停止时机
    #tols是容许的误差下降值，toln是切分的最小样本数
    tols = ops[0];tolN = ops[1]
    #如果只剩下一种标签，则退出
    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;
    #对于每个特征
    for featIndex in range(n-1):
        #对于每个特征值
        for splitValue in set(dataSet[:,featIndex].T.A.tolist()[0]):
            #划分为两个数据集
            mat0,mat1 = BinSplitDataSet(dataSet,featIndex,splitValue)
            if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN):continue
            #计算总方差
            newS = errType(mat0) + errType(mat1)
            if newS < bestS:
                bestIndex = featIndex
                bestValue = splitValue
                bestS = newS
    #如果小于容许的误差下降值则返回空，不划分
    if (S - bestS) < tols:
        return None,leafType(dataSet)
    mat0,mat1 = BinSplitDataSet(dataSet,bestIndex,bestValue)
    #如果小于最小划分样本数同样返回空，不划分
    if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN):
        return None,leafType(dataSet)
    return bestIndex,bestValue

#利用CART算法建立回归树
#
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

myDat = loadDateSet('Ch09/ex00.txt')
myMat = mat(myDat)
myTree = createTree(myMat,ops=(0,1))
print myTree

实验结果：这里只截取了部分

 

树剪枝

剪枝：通过降低决策树的复杂度来避免过拟合的过程

剪枝分为预剪枝与后剪枝，预剪枝在构建树的过程中通过调整终止条件起到剪枝的过程，而后剪枝则是在决策树建立之后通过测试集与训练集进行修剪。这里只给出后剪枝的过程

#判断是否为一棵树，也就是判断当前处理的结点是不是叶节点
def isTree(obj):
    return (type(obj)==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

#后剪枝，tree:待剪枝的树，testData：剪枝所需要的测试数据
def prune(tree,testData):
    #如果测试数据为空，则返回均值
    if shape(testData)[0]==0:return getMean(tree)
     #若左右子树均不为叶节点，则划分左右子树
    if isTree(tree['left']) or isTree(tree['right']):
        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(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 '合并'
            return treeMean
        else:
            return tree
    else:
        return tree

实验结果：

模型树

除了把叶结点定位常数值外，还可以把叶节点定义为分段线性函数，所谓分段线性是指模型由多个线性片段组成。

这里只需要将前面的代码稍加修改就可以在叶节点生成模型，这里需要修改的CreateTree()中叶子节点的类型，以及误差的计算方法。这里的误差计算先用线性模型进行拟合，然后计算真实的目标值与预测值之间的差值。最后将这些差值的平方求和就得到所需的误差。 

#执行简单的线性回归拟合
def linearSolve(dataSet):
    m,n = shape(dataSet)
    X = mat(ones((m,n)));Y = mat(ones((m,1)))
    #将数据集拆分为目标变量y与自变量X
    X[:,1:n] = dataSet[:,0:n-1];Y = dataSet[:,-1]
    #计算权重weight
    xTx = X.T*X
    if linalg.det(xTx) == 0:
        print "无法求逆"
        return
    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))

myMat = mat(loadDateSet('Ch09/exp2.txt'))
tree = createTree(myMat,leafType=modelLeaf,errType=modelErr,ops=(1,10))
print tree

实验结果

有实验结果可以看到生成的线性模型分别是y=3.468x+1.1852与y=11.964x+0.00169，这与真实的数据y=3.5+1.0x与y=0+12x很接近。