针对非线性问题无法通过全局线性模型来拟合，通常将该非线性问题切分成多个便于线性建模的数据，而分类回归树（CART）就是解决方案之一，大致流程如下：

1.找到最佳的待切分特征；

2.执行二元切分，左子树和右子树；

3.如果节点不能切分，存为叶节点；

# 创建分类回归树
def createTree(dataSet, leafType=regLeaf, errType=regErr, ops=(1,4)):feat, val = chooseBestSplit(dataSet, leafType, errType, ops)    #寻找最优切分特征与特征值if feat == None: return valretTree = {}retTree['spInd'] = featretTree['spVal'] = vallSet, rSet = binSplitDataSet(dataSet, feat, val)    #二元切分retTree['left'] = createTree(lSet, leafType, errType, ops)    #左子树retTree['right'] = createTree(rSet, leafType, errType, ops)    #右子树return retTree#寻找最优切分特征与特征值
def chooseBestSplit(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 = shape(dataSet)S = errType(dataSet)bestS = inf; bestIndex = 0; bestValue = 0for featIndex in range(n-1):for splitVal in set(dataSet[:,featIndex]):mat0, mat1 = binSplitDataSet(dataSet, featIndex, splitVal)if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN): continuenewS = errType(mat0) + errType(mat1)if newS < bestS:bestIndex = featIndexbestValue = splitValbestS = newSif (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#二元切分
def binSplitDataSet(dataSet, feature, value):mat0 = dataSet[nonzero(dataSet[:,feature] > value)[0],:][0]mat1 = dataSet[nonzero(dataSet[:,feature] <= value)[0],:][0]return mat0,mat1

分类回归树，按照叶节点的数据格式可分为：1.回归树（节点上存单个值）；2.模型树（节点上存线性方程）

当树的节点过多时，需要进行剪枝操作，代码实践如下：

# 测试输入是否为一棵树
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'])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.0errorMerge = sum(power(testData[:, -1] - treeMean, 2))if errorMerge < errorNoMerge:print"merging"return treeMeanelse:return treeelse:return tree