树回归： 线性回归模型需要拟合所有样本（局部加权线性回归除外），当数据拥有众多特征且特征间关系复杂时，构建全局模型就显得太难了。一种可行的方法是将数据集切分成很多份易建模的数据，然后利用线性回归技术建模。如果首次切分后仍难以拟合线性模型就继续切分，
在这种切分模式下，树结构和回归法相当有用。 CART（Classification And Regression Trees，分类回归树）算法，即可用于分类，也可用于回归。其中的树剪枝技术用于防止树的过拟合。 决策树不断将数据切分成小数据集，直到所有目标变量完全相同，或者数据不能再切分为止。决策树是一种贪心算法，它要在给定的时间内做出最佳选择，但不关心能否达到全局最优。
优缺点： 优点：可以对复杂和非线性的数据建模 缺点：结果不易理解
CART是十分著名的树构建算法，它使用二元切分来处理连续性变量，对其稍作修改就可处理回归问题。CART算法也使用一个字典来存储树的数据结构，该字典含： 待切分的特征 待切分的特征值 右子树，不需切分时，也可是单个值 左子树，右子树类似 CART可构建两种树：回归树（regression tree），其每个叶节点包含单个值；模型树（model tree），其每个叶节点包含一个线性方程。创建树的函数createTree()的伪代码大致如下： 找到最佳的待切分特征 : 如果该节点不能再分，将该节点存为叶节点 执行二元切分 在右子树调用createTree()方法 在左子树调用createTree()方法构建树：
对每个特征 : 对每个特征值 : 将数据集切分成两份 计算切分的误差 如果当前误差小于当前最小误差，那么将当前切分设定为最佳切分并更新最小误差 返回最佳切分的特征和阈值终止条件： 1.剩余特征值的数目为1 2.如果切分数据集后的误差提升不大，不应进行切分操作，而直接创建叶节点 3.两个切分后的子集中的一个的大小小于用户定义的参数tolN时
代码：
def binSplitDataSet(dataSet, feature, value): mat0 = dataSet[nonzero(dataSet[:,feature] > value)[0],:] mat1 = dataSet[nonzero(dataSet[:,feature] <= value)[0],:] return mat0, mat1 def loadDataSet(fileName): dataMat = [] file = open(fileName) for line in file.readlines(): lineMat = line.strip().split('\t') lineArr = map(float, lineMat) dataMat.append(lineArr) return dataMat def regLeaf(dataSet): return mean(dataSet[:, -1]) def regErr(dataSet): return var(dataSet[:,-1])*shape(dataSet)[0] def chooseBestSplit(dataSet, leafType = regLeaf, errType = regErr, ops = (1, 4)): tolS = ops[0]#容许误差下降值 tolN = ops[1]#最小样本 n = shape(dataSet)[1] if len(set(dataSet[:, -1].T.tolist()[0]))==1: return None, leafType(dataSet) S = errType(dataSet) bestS = inf bestf = 0 bestv = 0 for i in range(n-1): for j in set(dataSet[:, i].T.tolist()[0]): mat0, mat1 = binSplitDataSet(dataSet, i, j) if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN): continue newS = errType(mat0) + errType(mat1) if newS < bestS: bestf = i bestv = j bestS = newS if (S - bestS) < tolS: print '***1***' return None, leafType(dataSet) mat0, mat1 = binSplitDataSet(dataSet, bestf, bestv) if (shape(mat0)[0] < tolN )or( shape(mat1)[0] < tolN): print '***2***' return None, leafType(dataSet) return bestf, bestv def creatTree(dataSet, leafType = regLeaf, errType = regErr, ops = (0, 1)): 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'] = creatTree(lSet, leafType, errType, ops) retTree['right'] = creatTree(rSet, leafType, errType, ops) return retTree