引言
在我前面一篇博客预测数值型数据：回归一文中提到了线性回归包含了一些强大的方法，但除了加权线性回归，其余线性回归方法创建的模型需要拟合所有的数据样本即构建一个全局的模型，但实际应用场景下，很多问题是非线性的，特征不仅多而且趋于复杂，不可能用全局线性模型来拟合任何数据。
那么我们该如何解决这个问题呢？有人提出了将数据集切分成很多很多份易于建模的数据，然后利用前面提到的线性回归技术来建模。
那么本文就介绍了一种树构建算法CART(Classification And Regression Trees,分类回归树）。本文先利用CART算法构建回归树并介绍其中的剪枝技术，并引入更高级的模型树算法。
复杂数据的局部性建模
我们在学习决策树的时候发现，决策树不断地将数据切分成小数据集，知道所有目标变量完全相同，或者数据不能再切分为止。它本质上是一种贪心算法，并不关心数据是否可以达到全局最优。那么对于树回归，它的优缺点及适用数据类型又有哪些呢？
树回归优点：可以对复杂和非线性的数据建模
缺点：结果不易理解
适用数据类型：数值型和标称型数据
决策树算法如ID3，它是每次选取当前最佳特征来分割数据，并按照该特征的所有可能取值来切分。有人认为这种切分方法太迅速，因为数据根据当前特征切分后，该特征就不再起作用。所以有观点提出了二元切分法，如果数据的某个特征值等于切分所要求的值，那么这些数据就进入树的左子树，反之则进入树的右子树。另外ID3又有不能处理连续型特征的问题，二元切分法同样能解决这个问题。
CART树构建算法就是使用二元切分法来处理连续型变量，对CART稍作修改使其能处理回归问题，回归树与分类树的思路类似，但叶子节点的数据类型不是离散型而是连续型。
树回归的一般方法
- 收集数据：采用任意方法收集数据
- 准备数据：需要数值型数据，标称型数据应该映射成二值型数据
- 分析数据：绘出数据的二维可视化显示结果，以字典方式生成树
- 训练算法：大部分时间都花费在叶节点树模型的构建上
- 使用算法：使用训练出的树做预测，预测结果还可以用来做很多事
连续和离散型特征的树的构建
我们使用字典来存储树的数据结构，也可以用面向对象的编程模式来实现数据结构，如下所示：
class treeNode():
def __init__(self,feat,val,right,left):
featureToSplitOn = feat
valueOfSplit = val
rightBranch = right
leftBranch = left
本文构建树的伪代码如下所示：
找到最佳的待切分特征：
如果该节点不能再分，将该节点存为叶节点
执行二元切分
在左子树调用createTree( )方法
在右子树调用createTree( )方法
CART算法的实现代码：
from numpy import *
def loadDataSet(fileName): #general function to parse tab -delimited floats
dataMat = [] #assume last column is target value
fr = open(fileName)
for line in fr.readlines():
curLine = line.strip().split('\t')
fltLine = map(float,curLine) #map all elements to float()
dataMat.append(fltLine)
return dataMat
def binSplitDataSet(dataSet, feature, value):
mat0 = dataSet[nonzero(dataSet[:,feature] > value)[0],:]
mat1 = dataSet[nonzero(dataSet[:,feature] <= value)[0],:]
return mat0,mat1
def createTree(dataSet, leafType=regLeaf, errType=regErr, ops=(1,4)):#assume dataSet is NumPy Mat so we can array filtering
feat, val = chooseBestSplit(dataSet, leafType, errType, ops)#choose the best split
if feat == None: return val #if the splitting hit a stop condition 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
将CART算法用于回归
我们知道决策树可以用来分类，核心思想是计算给定节点的信息熵增益，那么如何将树应用到回归呢，那么我们可以将问题这样定义：如何计算连续性数值的信息熵增益。 具体思路如下：
step1.计算所有数据的均值
step2.计算每条数据的值到均值的差值的绝对值
上述两个步骤就是误差计算准则，前面一节我们又讲述了树的构建算法，那么接下来我们就正式进入到回归树的构建中。回归树的构建中对chooseBestSplit()函数的实现最困难，该函数主要目的是找到数据集切分的最佳位置。核心思想的伪代码如下：
对每个特征：
-对每个特征：
- -将数据集切分成两份
- -计算切分的误差
- -如果当前误差小于当前最小误差，那么当前切分设定为最佳切分并更新最小误差
剪枝
一棵树如果节点过多，表明该模型很可能对数据过拟合了（overfitting），对应的为了避免过拟合，降低决策树的复杂度，提出了一种剪枝（pruning）的方法。树剪枝分为两种，一种叫预剪枝，一种叫后剪枝，预剪枝一般是在选择节点时加入的提前中止条件，这种方法存在些许不足，对误差的数量级敏感。后剪枝则是一个比较理想的方法，主要通过训练集来分割叶节点，用测试集来判断如果合并叶节点是否有降低误差。
模型树
上面我们用树建模时是将叶节点简单地设定为常数值，但是还有一种方法是将叶节点设定为分段线性函数。即所谓的分段线性模型。也就是所谓的模型树
