回归算法原理
CART(Calssification and Regression Tree)算法是目前决策树算法中最为成熟的一类算法，应用范围也比较广泛。它即可用于分类，也可用于预测。
西方预测理论一般都是基于回归的，CART是一种通过决策树方法实现回归的算法，它有很多其他全局回归算法不具有的特性。
在创建回归模型时，样本的取值分为观察值和输出值两种，观察值和输出值都是连续的，不像分类函数那样有分类标签，只有根据数据集的数据特征来创建一个预测的模型，反映曲线的变化趋势。在预测中，CART使用最小剩余方差（Squared Residuals Minimization）来判定回归树的最优划分，这个准则期望划分之后的子树与样本点的误差方差最小。这样决策树将数据集切分成很多子模型数据，然后利用线性回归技术来建模。如果每次切分后的数据子集仍然难以拟合，就继续切分。在这种切分方式下创建出的预测树，每个叶子节点都是一个线性回归模型。这些线性回归模型反映了样本集合（观测集合）中蕴含的模式，也被称为模型书。因此，CART不仅支持整体预测，也支持局部模式的预测，并有能力从整体中找到模式，或根据模式组合成一个整体。整体与模式之间的相互结合，对于预测分析有重要的价值。
CART算法的流程：
（1）决策树主函数：决策树的主函数是一个递归函数。该函数的主要功能是按照CART的规则生长出决策树的各个分支节点，并根据终止条件结束算法。
a.输入需要分类的数据集和类别标签。
b.使用最小剩余方差判定回归树的最优划分，并创建特征的划分节点--最小剩余方差子函数。
c.在划分节点划分数据集为两部分--二分数据集子函数
d.根据二分数据的结果构建出新的左右节点，作为树生长出的两个分支。
e.检验是否符合递归的终止条件
f.将划分的新节点包含的数据集和类别标签作为输入，递归执行上述步骤。
（2）使用最小剩余方差子函数，计算数据集各列的最优划分方差、划分列、划分值。
（3）二分数据集：根据给定的分格列和分隔值将数据集一分为二，分别返回。
（4）剪枝策略：使用先剪枝和后剪枝策略对计算出的决策树进行剪枝。
最小剩余方差法
在回归树种，数据集均为连续性的。连续数据的处理方法与离散数据不同，离散数据是按每个特征的取值来划分，而连续特征则要计算出最优划分点。但在连续数据交集上计算线性相关度非常简单，算法思想来源于最小二乘法。
CART选择最优划分节点的方法--最小剩余方差法。
首先求取划分数据列的均值和总方差。总方差的计算方法有两种
1.求取均值std,计算每个数据点与std的方差，然后将n个点求和。
2.求取方差var,然后var_sum = var * n, n为数据集数据数目
每次最佳分支特征的选取过程如下：
1.先令最佳方差为无限大：bestVar = inf.
2.依次遍历所有特征列及每个特征列的所有样本点（这是一个二重循环），在每个样本点上二分数据集。
3.计算二分数据集后的总方差currentVar(划分后左、右数据集的总方差之和)。如果currentVar < bestVar,则bestVar = currentVar.
4.返回计算的最优分支特征列、分支特征值（连续特征则为划分点的值），以及左右分支子数据集到主程序。
模型树
使用CART进行预测是把叶子节点设定为一系列的分段线性函数，这些分段线性函数是对原数据曲线的一种模拟，每个线性函数都被称为一颗模型树。
模型树的优点如下：
1.一般而言，样本总体的重复性不会很高，但局部模式经常重复，也就是我们所说的历史不会简单的重复，但会重演。模型比总体对未来的预测而言更有用。
2.模型给出了数据的范围，它可能是一个时间范围，也可能是一个空间范围；而且模型还给出了变化的趋势，可以是曲线，也可以是直线，这依赖于使用的回归算法。这些因素使模型具有很强的可解释性。
3.传统的回归方法，无论是线性回归还是非线性回归，都不如模型树包含的信息丰富，因此模型树具有更高的预测准确度。
剪枝策略
因为使用了连续性数据，CART可以生长出大量的分支树，为了避免过拟合的问题，预测树采用了剪枝的方法。剪枝方法有很多，主流的方法有两种：先剪枝和后剪枝。
先剪枝给出一个预定义的划分阈值，当节点的划分子集某个标准低于预定义的阈值时，子集划分将终止。但是选取适当的阈值比较困难，过高会导致过拟合，而过低会导致欠拟合，因此需要人工反复地训练样本才能得到很好的效果。优势：由于不必生成整棵决策树，且算法简单、效率高，适合大规模问题的粗略估计。
后剪枝，也称为悲观剪枝。后剪枝是指在完全生成的决策树上，根据一定的规则标准，剪掉树中不具备一般代表性的子树，使用叶子节点取而代之，进而形成一课规模较小的新树。后剪枝递归估算每个内部节点所覆盖样本节点的误判率，也就是计算决策树内部节点的误判率。如果内部节点的误判率低于这个值，就将其变成叶子节点，该叶子节点的类别标签由原内部节点的最优叶子节点所决定。
代码实现：sklearn-CART预测
# cart决策树 import matplotlib.pyplot as plt from numpy import * from sklearn.tree import DecisionTreeClassifier # 加载数据集 def loadDataSet(fileName): X = []; Y = [] fr = open(fileName, 'r') content = fr.read() fr.close() rowlist = content.splitlines() # 按行转换为一维表 recordlist = array([row.split(" ") for row in rowlist if row.strip()]) for line in recordlist: line = array(line) X.append(float(line[0])) Y.append(float(line[-1])) return X, Y def plotfigure(X, X_test, y, yp): plt.figure() plt.scatter(X, y, c = "k", label = "data") plt.plot(X_test, yp, c = "r", label = "max_depth=5", linewidth = 2) plt.xlabel("data") plt.ylabel("target") plt.title("Decision Tree Regression") plt.legend() plt.show() x = linspace(-5, 5, 200) # test1 siny = sin(x) # 给出y与x的基本关系 X = mat(x).T y = siny * 1000 + random.rand(1, len(siny)) * 1.5 * 1000 # 加入噪声的点集 y = y.tolist()[0] y = array(y, dtype=int) print(y) clf = DecisionTreeClassifier(max_depth=4) # max_depth选取最大的树深度，类似先剪枝 clf.fit(X, y) # predict X_test = arange(-5.0, 5.0, 0.05)[:, newaxis] yp = clf.predict(X_test) plotfigure(array(X), array(X_test), y, yp)
结果如下
