CART算法 回归与模型树 树剪枝算法
完整代码及注解线性回归包含了一些强大的方法，但这些方法创建的模型需要拟合所有的样本点(局部加权线性回归除外)。当数据拥有众多特征并且特征之间关系十分复杂时，构建全局模型的想法就显得太难了,也咯显笨拙。而且，实际生活中很多问题都是非线性的，不可能使用全局线性模型来拟合任何数据。
一种可行的方法是将数据集切分成很多份易建模的数据，然后利用线性回归技术来建模。如果首次切分后仍然难以拟合线性模型就继续切分。在这种切分方式下，树结构和回归法就相当有用。 本文首先介绍一个新的叫做CART ( Cassifcation And Regression Trees,分类回归树)的树构建算法。该算法既可以用于分类还可以用于回归，因此非常值得学习。然后利用Python来构建并显示CART树。代码会保持足够的灵活性以便能用于多个问题当中。接着，利用CART算法构建回归树并介绍其中的树剪枝技术(该技术的主要目的是防止树的过拟合)。 之后引入了一个更高级的模型树算法。与回归树的做法(在每个叶节点上使用各自的均值做预测)不同，该算法需要在每个叶节点上都构建出一个线性模型。在这些树的构建算法中有一些需要 调整的参数, 所以还会介绍如何使用Python中的Tkinter模块建立图形交互界面。最后，在该界面的辅助下分析参数对同归效果的影晌
1.1、复杂数据的局部性建模 决策树概念 决策树实现使用决策树分类。决策树不断将数据切分成小数据集，直到所有目标变量完全相同，或者数据不能再切分为止。决策树是一种贪心算法，它要在给定时间内做出最佳选择，但并不关心能否达到全局最优。
ID3的做法是每次选取当前最佳的特征来分割数据，并按照该特征的所有可能取值来切分。也就是说，如果一个特征有4种取值, 那么数据将被切成4份。一旦按某特征切分后，该特征在之后的算法执行过程中将不会再起作用，所以有观点认为这种切分方式过于迅速。另外一种方法是二元切分法，即每次把数据集切成两份。如果数据的某特征值等于切分所要求的值，那么这些数据就进人树的左子树，反之则进人树的右子树。除了切分过于迅速外，ID3算法还存在另一个问题，它不能直接处理连续型特征。只有事先将连续型特征转换成离散型，才能在ID3算法中使用。 但这种转换过程会破坏连续型变量的内在性质。而使用二元切分法则易于对树构建过程进行调整以处理连续型特征。具体的处理方法是:如果特征值大于给定值就走左子树，否则就走右子树。另外,二元切分法也节省了树的构建时间，但这点意义也不是特别大，因为这些树构建一般是离线完成， 时间并非需要重点关注的因素。 CART是十分著名且广泛记载的树构建算法，它使用二元切分来处理连续型变量。对CART稍作修改就可以处理回归问题。ID3中使用香农熵来度量集合的无组织程度。如果选用其他方法来代替香农熵,就可以使用树构建算法来完成回归。
下面将实观CART算法和回归树。回归树与分类树的思路类似，但叶节点的数据类型不是离散型，而是连续型。
树回归的一般方法
- (1)收集数据:采用任意方法收集数据。
- (2)准备数据:需要数值型的数据，标称型数据应该映射成二值型数据。
- (3)分析数据:绘出数据的二维可视化显示结果，以字典方式生成树。
- (4)训练算法:大部分时间都花費在叶节点树模型的构建上。
- (5)测试算法:使用测试数据上的R2值来分析模型的效果。
- (6)使用算法:使用训练出的树做预测，预测结果还可以用来做很多事情
有了思路之后就可以开始写代码了。下一节将介绍在Pyhon中利用CART算法构建树的最佳方法。
1.2、连续和离散型特征的树的构建在树的构建过程中，需要解决多种类型数据的存储问题。与第3章类似，这里将使用一部字典来存储树的数据结构，该字典将包含以下4个元素。
- 待切分的特征。
- 待切分的特征值。
- 右子树。当不再需要切分的时候，也可以是单个值。
- 左子树。与右子树类似。
这与第3章的树结构有一点不同。第3章用一部字典来存储每个切分,但该字典可以包含两个或两个以上的值。而CART算法只做二元切分，所以这里可以固定树的数据结构。树包含左键和右键，可以存储另一棵子树或者单个值。字典还包含特征和特征值这两个键，它们给出切分算法所有的特征和特征值。
本文将构建两种树:第一种是1.4节的回归树( regression tree),其每个叶节点包含单个值;第二种是1.5节的模型树( model tree ),其每个叶节点包含一个线性方程。创建这两种树时，我们将尽量使得代码之间可以重用。
下面先给出两种树构建算法中的一些共用代码。 1.3、将CART算法用于回归要对数据的复杂关系建模,我们已经决定借用树结构来帮助切分数据,那么如何实现数据的切分呢?怎么才能知道是否已经充分切分呢?这些问题的答案取决于叶节点的建模方式。 回归树假设叶节点是常数值,这种策略认为数据中的复杂关系可以用树结构来概括。为成功构建以分段常数为叶节点的树,需要度量出数据的一致性。 决策树中使用树进行分类，会在给定节点时计算数据的混乱度。
那么如何计算连续型数值的混乱度呢? 事实上，在数据集上计算混乱度是非常简单的。首先计算所有数据的均值，然后计算每条数据的值到均值的差值。为了对正负差值同等看待，一般使用绝对值或平方值来代替上述差值。上述做法有点类似于前面介绍过的统计学中常用的方差计算。唯一的不同就是， 方差是平方误差的均值(均方差),而这里需要的是平方误差的总值(总方差)。总方差可以通过均方差乘以数据集中样本点的个数来得到。
有了上述误差计算准则和上一节中的树构建算法，下面就可以开始构建数据集上的回归 树了。
1.3.1构建树
# 该函数的目标是找到数据集切分的最佳位置。它遍历所有的特征及其可能的取值来找到使误差最小化的切分阈值。
# 该函数的伪代码大致如下:
# 对每个特征:
# 对每个特征值:
# 将数据集切分成两份
# 计算切分的误差
# 如果当前误差小于当前最小误差,那么将当前切分设定为最佳切分并更新最小误差
# 返回最佳切分的特征和阈值
def chooseBestSplit(dataSet, leafType=regLeaf, errType=regErr, ops=(1, 4)):
'''
给定某个误差计算方法，该函数会找到数据集上最佳的二元切分方式。
另外，该函数还要确定什么时候停止切分，一旦停止切分会生成一个叶节点。
因此，函数chooseBestSplitl) 只需完成两件事:用最佳方式切分数据集和生成相应的叶节点。
:param dataSet:
:param leafType: 对创建叶节点的函数的引用
:param errType: 总方差计算函数的引用
:param ops: 一个用户定义的参数构成的元组，用以完成树的构建
:return:
'''
# 开始为ops设定了tolS和to1N这两个值。它们是用户指定的参数,用于控制函数的停止时机。
# 其中变量tolS是容许的误差下降值，to1N是切分的最少样本数。
tolS = ops[0];
tolN = ops[1]
# if all the target variables are the same value: quit and return value
if len(set(dataSet[:, -1].T.tolist()[0])) == 1: # exit cond 1
return None, leafType(dataSet)
m, n = shape(dataSet)
# the choice of the best feature is driven by Reduction in RSS error from mean
S = errType(dataSet) # 误差
bestS = inf;
bestIndex = 0;
bestValue = 0
# 计算了当前数据集的大小和误差
for featIndex in list(range(n - 1)):
#for splitVal in set((dataSet[:, featIndex])[0]): TypeError: unhashable type: 'matrix'
for splitVal in set(dataSet[:, featIndex].T.tolist()[0]):
print("splitVal: ===>", splitVal)
mat0, mat1 = binSplitDataSet(dataSet, featIndex, splitVal)
if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN): continue
newS = errType(mat0) + errType(mat1)
# 误差S将用于与新切分误差进行对比，来检查新切分能否降低误差
if newS < bestS:
bestIndex = featIndex
bestValue = splitVal
bestS = newS
# if the decrease (S-bestS) is less than a threshold don't do the split
# 如果切分数据集后效果提升不够大,那么就不应进行切分操作而直接创建叶节点
if (S - bestS) < tolS:
return None, leafType(dataSet) # exit cond 2
mat0, mat1 = binSplitDataSet(dataSet, bestIndex, bestValue)
# 另外还需要检查两个切分后的子集大小，如果某个子集的大小小于用户定义的参数tolN,那么也不应切分
if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN): # exit cond 3
return None, leafType(dataSet)
# 最后，如果这些提前终止条件都不满足，那么就返回切分特征和特征值
return bestIndex, bestValue # returns the best feature to split on
# and the value used for that split
一棵树如果节点过多,表明该模型可能对数据进行了 “过拟合”。那么，如何判断是否发生了过拟合?前面章节中使用了测试集上某种交叉验证技术来发现过拟合,决策树亦是如此。本节将对此进行讨论，并分析如何避免过拟合。 通过降低决策树的复杂度来避免过拟合的过程称为剪枝( pruning )。其实本章前面已经进行过剪枝处理。在函数chooseBestsplit ()中的提前终止条件,实际上是在进行一种所谓的预剪枝(prepruning )操作。另一种形式的剪枝需要使用测试集和训练集，称作后剪枝(postpruning )。本节将分析后剪枝的有效性，但首先来看一下预剪枝的不足之处。
上节两个简单实验的结果还是令人满意的，但背后存在一些问题。树构建算法其实对输人的 参数to1s和tolN非常敏感,如果使用其他值将不太容易达到这么好的效果。为了说明这-一点， 在Python提示符下输人如下命令:
>>> regTrees . createTree (myMat, ops=(0,1))
与上节中只包含两个节点的树相比，这里构建的树过于臃肿，它甚至为数据集中每个样本都 分配了一个叶节点。
图9-3中的散点图，看上去与图9-1非常相似。但如果仔细地观察y轴就会发现，前者的数量级 是后者的100倍。这将不是问题，对吧?现在用该数据来构建一棵新的树(数据存放在ex2.txt中),
myDat2 = loadDataSet('ex2.txt')
myMat2 = mat(myDat2)
myTree2 = createTree(myMat2)
print("myTree2", myTree2)
不知你注意到没有，从图9-1 数据集构建出来的树只有两个叶节点，而这里构建的新树则有很多叶节点。产生这个现象的原因在于，停止条件tols对误差的数量级十分敏感。如果在选项中花费时间并对上述误差容忍度取平方值，或许也能得到仅有两个叶节点组成的树:
>>> regTrees . createTree (myMat2, ops= (10000,4))
{ 'spInd': 0，'spVal': matrix([[ 0.49917111)， 'right': -2.6377193297872341,
'left' : 101 .35815937735855 }
然而，通过不断修改停止条件来得到合理结果并不是很好的办法。事实上，我们常常甚至不确定到底需要寻找什么样的结果。这正是机器学习所关注的内容，计算机应该可以给出总体的概貌。下节将讨论后剪枝，即利用测试集来对树进行剪枝。由于不需要用户指定参数，后剪枝是一个更理想化的剪枝方法。
1.4.2、后剪枝使用后剪枝方法需要将数据集分成测试集和训练集。首先指定参数,使得构建出的树足够大、足够复杂，便于剪枝。接下来从上而下找到叶节点，用测试集来判断将这些叶节点合并是否能降低测试误差。如果是的话就合并。
