常见面试算法：树回归、树剪枝
树回归 概述
我们本章介绍 CART(Classification And Regression Trees， 分类回归树) 的树构建算法。该算法既可以用于分类还可以用于回归。
树回归 场景
我们在第 8 章中介绍了线性回归的一些强大的方法，但这些方法创建的模型需要拟合所有的样本点（局部加权线性回归除外）。当数据拥有众多特征并且特征之间关系十分复杂时，构建全局模型的想法就显得太难了，也略显笨拙。而且，实际生活中很多问题都是非线性的，不可能使用全局线性模型来拟合任何数据。
一种可行的方法是将数据集切分成很多份易建模的数据，然后利用我们的线性回归技术来建模。如果首次切分后仍然难以拟合线性模型就继续切分。在这种切分方式下，树回归和回归法就相当有用。
除了我们在 第3章 中介绍的 决策树算法，我们介绍一个新的叫做 CART(Classification And Regression Trees, 分类回归树) 的树构建算法。该算法既可以用于分类还可以用于回归。
1、树回归 原理
1.1、树回归 原理概述
为成功构建以分段常数为叶节点的树，需要度量出数据的一致性。第3章使用树进行分类，会在给定节点时计算数据的混乱度。那么如何计算连续型数值的混乱度呢？
在这里，计算连续型数值的混乱度是非常简单的。首先计算所有数据的均值，然后计算每条数据的值到均值的差值。为了对正负差值同等看待，一般使用绝对值或平方值来代替上述差值。
上述做法有点类似于前面介绍过的统计学中常用的方差计算。唯一不同就是，方差是平方误差的均值(均方差)，而这里需要的是平方误差的总值(总方差)。总方差可以通过均方差乘以数据集中样本点的个数来得到。
1.2、树构建算法 比较
我们在 第3章 中使用的树构建算法是 ID3 。ID3 的做法是每次选取当前最佳的特征来分割数据，并按照该特征的所有可能取值来切分。也就是说，如果一个特征有 4 种取值，那么数据将被切分成 4 份。一旦按照某特征切分后，该特征在之后的算法执行过程中将不会再起作用，所以有观点认为这种切分方式过于迅速。另外一种方法是二元切分法，即每次把数据集切分成两份。如果数据的某特征值等于切分所要求的值，那么这些数据就进入树的左子树，反之则进入树的右子树。
除了切分过于迅速外， ID3 算法还存在另一个问题，它不能直接处理连续型特征。只有事先将连续型特征转换成离散型，才能在 ID3 算法中使用。但这种转换过程会破坏连续型变量的内在性质。而使用二元切分法则易于对树构造过程进行调整以处理连续型特征。具体的处理方法是: 如果特征值大于给定值就走左子树，否则就走右子树。另外，二元切分法也节省了树的构建时间，但这点意义也不是特别大，因为这些树构建一般是离线完成，时间并非需要重点关注的因素。
CART 是十分著名且广泛记载的树构建算法，它使用二元切分来处理连续型变量。对 CART 稍作修改就可以处理回归问题。第 3 章中使用香农熵来度量集合的无组织程度。如果选用其他方法来代替香农熵，就可以使用树构建算法来完成回归。
回归树与分类树的思路类似，但是叶节点的数据类型不是离散型，而是连续型。
1.2.1、附加 各常见树构造算法的划分分支方式
还有一点要说明，构建决策树算法，常用到的是三个方法: ID3, C4.5, CART. 三种方法区别是划分树的分支的方式:
- ID3 是信息增益分支
- C4.5 是信息增益率分支
- CART 做分类工作时，采用 GINI 值作为节点分裂的依据；回归时，采用样本的最小方差作为节点的分裂依据。
工程上总的来说:
CART 和 C4.5 之间主要差异在于分类结果上，CART 可以回归分析也可以分类，C4.5 只能做分类；C4.5 子节点是可以多分的，而 CART 是无数个二叉子节点；
以此拓展出以 CART 为基础的 “树群” Random forest ， 以 回归树 为基础的 “树群” GBDT 。
1.3、树回归 工作原理
1、找到数据集切分的最佳位置，函数 chooseBestSplit() 伪代码大致如下:
对每个特征:
对每个特征值:
将数据集切分成两份（小于该特征值的数据样本放在左子树，否则放在右子树）
计算切分的误差
如果当前误差小于当前最小误差，那么将当前切分设定为最佳切分并更新最小误差
返回最佳切分的特征和阈值2、树构建算法，函数 createTree() 伪代码大致如下:
找到最佳的待切分特征:
如果该节点不能再分，将该节点存为叶节点
执行二元切分
在右子树调用 createTree() 方法
在左子树调用 createTree() 方法1.4、树回归 开发流程
(1) 收集数据：采用任意方法收集数据。
(2) 准备数据：需要数值型数据，标称型数据应该映射成二值型数据。
(3) 分析数据：绘出数据的二维可视化显示结果，以字典方式生成树。
(4) 训练算法：大部分时间都花费在叶节点树模型的构建上。
(5) 测试算法：使用测试数据上的R^2值来分析模型的效果。
(6) 使用算法：使用训练处的树做预测，预测结果还可以用来做很多事情。1.5、树回归 算法特点
优点：可以对复杂和非线性的数据建模。
缺点：结果不易理解。
适用数据类型：数值型和标称型数据。1.6、回归树 项目案例
1.6.1、项目概述
在简单数据集上生成一棵回归树。
1.6.2、开发流程
收集数据：采用任意方法收集数据
准备数据：需要数值型数据，标称型数据应该映射成二值型数据
分析数据：绘出数据的二维可视化显示结果，以字典方式生成树
训练算法：大部分时间都花费在叶节点树模型的构建上
测试算法：使用测试数据上的R^2值来分析模型的效果
使用算法：使用训练出的树做预测，预测结果还可以用来做很多事情收集数据：采用任意方法收集数据
data1.txt 文件中存储的数据格式如下:
完整代码地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/9.RegTrees/regTrees.py
测试算法：使用测试数据上的R^2值来分析模型的效果
使用算法：使用训练出的树做预测，预测结果还可以用来做很多事情
2、树剪枝
一棵树如果节点过多，表明该模型可能对数据进行了 “过拟合”。
通过降低决策树的复杂度来避免过拟合的过程称为 剪枝（pruning）。在函数 chooseBestSplit() 中提前终止条件，实际上是在进行一种所谓的 预剪枝（prepruning）操作。另一个形式的剪枝需要使用测试集和训练集，称作 后剪枝（postpruning）。
2.1、预剪枝(prepruning)
顾名思义，预剪枝就是及早的停止树增长，在构造决策树的同时进行剪枝。
所有决策树的构建方法，都是在无法进一步降低熵的情况下才会停止创建分支的过程，为了避免过拟合，可以设定一个阈值，熵减小的数量小于这个阈值，即使还可以继续降低熵，也停止继续创建分支。但是这种方法实际中的效果并不好。
2.2、后剪枝(postpruning)
决策树构造完成后进行剪枝。剪枝的过程是对拥有同样父节点的一组节点进行检查，判断如果将其合并，熵的增加量是否小于某一阈值。如果确实小，则这一组节点可以合并一个节点，其中包含了所有可能的结果。合并也被称作 塌陷处理 ，在回归树中一般采用取需要合并的所有子树的平均值。后剪枝是目前最普遍的做法。
后剪枝 prune() 的伪代码如下:
基于已有的树切分测试数据:
如果存在任一子集是一棵树，则在该子集递归剪枝过程
计算将当前两个叶节点合并后的误差
计算不合并的误差
如果合并会降低误差的话，就将叶节点合并
2.3、剪枝 代码回归树剪枝函数
完整代码地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/9.RegTrees/regTrees.py
3、模型树
3.1、模型树 简介
用树来对数据建模，除了把叶节点简单地设定为常数值之外，还有一种方法是把叶节点设定为分段线性函数，这里所谓的 分段线性（piecewise linear） 是指模型由多个线性片段组成。
我们看一下图 9-4 中的数据，如果使用两条直线拟合是否比使用一组常数来建模好呢？答案显而易见。可以设计两条分别从 0.00.3、从 0.31.0 的直线，于是就可以得到两个线性模型。因为数据集里的一部分数据（0.00.3）以某个线性模型建模，而另一部分数据（0.31.0）则以另一个线性模型建模，因此我们说采用了所谓的分段线性模型。
决策树相比于其他机器学习算法的优势之一在于结果更易理解。很显然，两条直线比很多节点组成一棵大树更容易解释。模型树的可解释性是它优于回归树的特点之一。另外，模型树也具有更高的预测准确度。
完整代码地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/9.RegTrees/regTrees.py
3.3、模型树 运行结果
4、树回归 项目案例
4.1、项目案例1: 树回归与标准回归的比较
4.1.1、项目概述
前面介绍了模型树、回归树和一般的回归方法，下面测试一下哪个模型最好。
这些模型将在某个数据上进行测试，该数据涉及人的智力水平和自行车的速度的关系。当然，数据是假的。
4.1.2、开发流程
收集数据：采用任意方法收集数据
准备数据：需要数值型数据，标称型数据应该映射成二值型数据
分析数据：绘出数据的二维可视化显示结果，以字典方式生成树
训练算法：模型树的构建
测试算法：使用测试数据上的R^2值来分析模型的效果
使用算法：使用训练出的树做预测，预测结果还可以用来做很多事情收集数据: 采用任意方法收集数据
准备数据：需要数值型数据，标称型数据应该映射成二值型数据
数据存储格式:
完整代码地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/9.RegTrees/regTrees.py
测试算法：使用测试数据上的R^2值来分析模型的效果
R^2 判定系数就是拟合优度判定系数，它体现了回归模型中自变量的变异在因变量的变异中所占的比例。如 R^2=0.99999 表示在因变量 y 的变异中有 99.999% 是由于变量 x 引起。当 R^2=1 时表示，所有观测点都落在拟合的直线或曲线上；当 R^2=0 时，表示自变量与因变量不存在直线或曲线关系。
所以我们看出， R^2 的值越接近 1.0 越好。
使用算法：使用训练出的树做预测，预测结果还可以用来做很多事情
5、附加 Python 中 GUI 的使用
5.1、使用 Python 的 Tkinter 库创建 GUI
如果能让用户不需要任何指令就可以按照他们自己的方式来分析数据，就不需要对数据做出过多解释。其中一个能同时支持数据呈现和用户交互的方式就是构建一个图形用户界面(GUI，Graphical User Interface)，如图9-7所示。
5.2、用 Tkinter 创建 GUI
Python 有很多 GUI 框架，其中一个易于使用的 Tkinter，是随 Python 的标准版编译版本发布的。Tkinter 可以在 Windows、Mac OS和大多数的 Linux 平台上使用。
5.3、集成 Matplotlib 和 Tkinter
MatPlotlib 的构建程序包含一个前端，也就是面向用户的一些代码，如 plot() 和 scatter() 方法等。事实上，它同时创建了一个后端，用于实现绘图和不同应用之间接口。
通过改变后端可以将图像绘制在PNG、PDF、SVG等格式的文件上。下面将设置后端为 TkAgg (Agg 是一个 C++ 的库，可以从图像创建光栅图)。TkAgg可以在所选GUI框架上调用Agg，把 Agg 呈现在画布上。我们可以在Tk的GUI上放置一个画布，并用 .grid()来调整布局。
5.4、用treeExplore 的GUI构建的模型树示例图
完整代码地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/9.RegTrees/treeExplore.py
6、树回归 小结
数据集中经常包含一些复杂的相关关系，使得输入数据和目标变量之间呈现非线性关系。对这些复杂的关系建模，一种可行的方式是使用树来对预测值分段，包括分段常数或分段直线。一般采用树结构来对这种数据建模。相应地，若叶节点使用的模型是分段常数则称为回归树，若叶节点使用的模型师线性回归方程则称为模型树。
CART 算法可以用于构建二元树并处理离散型或连续型数据的切分。若使用不同的误差准则，就可以通过CART 算法构建模型树和回归树。该算法构建出的树会倾向于对数据过拟合。一棵过拟合的树常常十分复杂，剪枝技术的出现就是为了解决这个问题。两种剪枝方法分别是预剪枝（在树的构建过程中就进行剪枝）和后剪枝（当树构建完毕再进行剪枝），预剪枝更有效但需要用户定义一些参数。
Tkinter 是 Python 的一个 GUI 工具包。虽然并不是唯一的包，但它最常用。利用 Tkinter ，我们可以轻轻松松绘制各种部件并安排它们的位置。另外，可以为 Tkinter 构造一个特殊的部件来显示 Matplotlib 绘出的图。所以，Matplotlib 和 Tkinter 的集成可以构建出更强大的 GUI ，用户可以以更自然的方式来探索机器学习算法的奥妙。
https://github.com/apachecn/AiLearning/blob/dev/blog/ml/9.%E6%A0%91%E5%9B%9E%E5%BD%92.md