09机器学习实战-第9章 树回归.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": true
   },
   "source": [
    "<h1>Table of Contents<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#第九章-树回归\" data-toc-modified-id=\"第九章-树回归-1\">第九章 树回归</a></span><ul class=\"toc-item\"><li><span><a href=\"#树回归-概述\" data-toc-modified-id=\"树回归-概述-1.1\">树回归 概述</a></span></li><li><span><a href=\"#树回归-场景\" data-toc-modified-id=\"树回归-场景-1.2\">树回归 场景</a></span></li><li><span><a href=\"#树回归-算法特点\" data-toc-modified-id=\"树回归-算法特点-1.3\">树回归 算法特点</a></span></li><li><span><a href=\"#树回归-开发流程\" data-toc-modified-id=\"树回归-开发流程-1.4\">树回归 开发流程</a></span></li><li><span><a href=\"#树构建算法，函数-createTree()-伪代码大致如下:\" data-toc-modified-id=\"树构建算法，函数-createTree()-伪代码大致如下:-1.5\">树构建算法，函数 createTree() 伪代码大致如下:</a></span></li><li><span><a href=\"#找到数据集切分的最佳位置，函数-chooseBestSplit()-伪代码大致如下:\" data-toc-modified-id=\"找到数据集切分的最佳位置，函数-chooseBestSplit()-伪代码大致如下:-1.6\">找到数据集切分的最佳位置，函数 chooseBestSplit() 伪代码大致如下:</a></span></li><li><span><a href=\"#树剪枝\" data-toc-modified-id=\"树剪枝-1.7\">树剪枝</a></span><ul class=\"toc-item\"><li><span><a href=\"#预剪枝(prepruning)\" data-toc-modified-id=\"预剪枝(prepruning)-1.7.1\">预剪枝(prepruning)</a></span></li><li><span><a href=\"#后剪枝(postpruning)\" data-toc-modified-id=\"后剪枝(postpruning)-1.7.2\">后剪枝(postpruning)</a></span></li><li><span><a href=\"#模型树\" data-toc-modified-id=\"模型树-1.7.3\">模型树</a></span><ul class=\"toc-item\"><li><span><a href=\"#模型树-简介\" data-toc-modified-id=\"模型树-简介-1.7.3.1\">模型树 简介</a></span></li></ul></li></ul></li><li><span><a href=\"#树回归与标准回归的比较\" data-toc-modified-id=\"树回归与标准回归的比较-1.8\">树回归与标准回归的比较</a></span><ul class=\"toc-item\"><li><span><a href=\"#项目概述\" data-toc-modified-id=\"项目概述-1.8.1\">项目概述</a></span></li></ul></li><li><span><a href=\"#附加-Python-中-GUI-的使用\" data-toc-modified-id=\"附加-Python-中-GUI-的使用-1.9\">附加 Python 中 GUI 的使用</a></span><ul class=\"toc-item\"><li><span><a href=\"#使用-Python-的-Tkinter-库创建-GUI\" data-toc-modified-id=\"使用-Python-的-Tkinter-库创建-GUI-1.9.1\">使用 Python 的 Tkinter 库创建 GUI</a></span></li><li><span><a href=\"#用-Tkinter-创建-GUI\" data-toc-modified-id=\"用-Tkinter-创建-GUI-1.9.2\">用 Tkinter 创建 GUI</a></span></li><li><span><a href=\"#集成-Matplotlib-和-Tkinter\" data-toc-modified-id=\"集成-Matplotlib-和-Tkinter-1.9.3\">集成 Matplotlib 和 Tkinter</a></span></li><li><span><a href=\"#用treeExplore-的GUI构建的模型树示例图\" data-toc-modified-id=\"用treeExplore-的GUI构建的模型树示例图-1.9.4\">用treeExplore 的GUI构建的模型树示例图</a></span></li><li><span><a href=\"#这里简单介绍一下Tkinter：\" data-toc-modified-id=\"这里简单介绍一下Tkinter：-1.9.5\">这里简单介绍一下Tkinter：</a></span></li></ul></li><li><span><a href=\"#总结\" data-toc-modified-id=\"总结-1.10\">总结</a></span></li></ul></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第九章 树回归\n",
    "\n",
    "**本章内容**\n",
    ">CART算法      \n",
    "回归与模型树   \n",
    "树剪枝算法   \n",
    "Python中GUI的使用   \n",
    "\n",
    "## 树回归 概述\n",
    "我们本章介绍 CART(Classification And Regression Trees， 分类回归树) 的树构建算法。该算法既可以用于分类还可以用于回归。\n",
    "\n",
    "## 树回归 场景\n",
    "我们在第 8 章中介绍了线性回归的一些强大的方法，但这些方法创建的模型需要拟合所有的样本点（局部加权线性回归除外）。当数据拥有众多特征并且特征之间关系十分复杂时，构建全局模型的想法就显得太难了，也略显笨拙。而且，实际生活中很多问题都是非线性的，不可能使用全局线性模型来拟合任何数据。\n",
    "\n",
    "一种可行的方法是将数据集切分成很多份易建模的数据，然后利用我们的线性回归技术来建模。如果首次切分后仍然难以拟合线性模型就继续切分。在这种切分方式下，树回归和回归法就相当有用。\n",
    "\n",
    "除了我们在 第3章 中介绍的 决策树算法，我们介绍一个新的叫做 CART(Classification And Regression Trees, 分类回归树) 的树构建算法。该算法既可以用于分类还可以用于回归。\n",
    "\n",
    "## 树回归 算法特点\n",
    ">优点：可以对复杂和非线性的数据建模。  \n",
    "缺点：结果不易理解。  \n",
    "适用数据类型：数值型和标称型数据。   \n",
    "\n",
    "\n",
    "我们在 第3章 中使用的树构建算法是 ID3 。ID3 的做法是每次选取当前最佳的特征来分割数据，并按照该特征的所有可能取值来切分。也就是说，如果一个特征有 4 种取值，那么数据将被切分成 4 份。一旦按照某特征切分后，该特征在之后的算法执行过程中将不会再起作用，所以有观点认为这种切分方式过于迅速。另外一种方法是二分切分法，即每次把数据集切分成两份。如果数据的某特征值等于切分所要求的值，那么这些数据就进入树的左子树，反之则进入树的右子树。\n",
    "\n",
    "除了切分过于迅速外， ID3 算法还存在另一个问题，它不能直接处理连续型特征。只有事先将连续型特征转换成离散型，才能在 ID3 算法中使用。但这种转换过程会破坏连续型变量的内在性质。而使用二元切分法则易于对树构造过程进行调整以处理连续型特征。具体的处理方法是: 如果特征值大于给定值就走左子树，否则就走右子树。另外，二分切分法也节省了树的构建时间，但这点意义也不是特别大，因为这些树构建一般是离线完成，时间并非需要重点关注的因素。\n",
    "\n",
    "CART 是十分著名且广泛记载的树构建算法，它使用二元切分来处理连续型变量。对 CART 稍作修改就可以处理回归问题。第 3 章中使用香农熵来度量集合的无组织程度。如果选用其他方法来代替香农熵，就可以使用树构建算法来完成回归。\n",
    "\n",
    "回归树与分类树的思路类似，但是叶节点的数据类型不是离散型，而是连续型。\n",
    "\n",
    "\n",
    "\n",
    "## 树回归 开发流程\n",
    ">(1) 收集数据：采用任意方法收集数据。   \n",
    "(2) 准备数据：需要数值型数据，标称型数据应该映射成二值型数据。  \n",
    "(3) 分析数据：绘出数据的二维可视化显示结果，以字典方式生成树。   \n",
    "(4) 训练算法：大部分时间都花费在叶节点树模型的构建上。    \n",
    "(5) 测试算法：使用测试数据上的$R^2$值来分析模型的效果。   \n",
    "(6) 使用算法：使用训练处的树做预测，预测结果还可以用来做很多事情。   \n",
    "\n",
    "\n",
    "## 树构建算法，函数 createTree() 伪代码大致如下:\n",
    "```\n",
    "找到最佳的待切分特征:\n",
    "    如果该节点不能再分，将该节点存为叶节点\n",
    "    执行二元切分\n",
    "    在右子树调用 createTree() 方法\n",
    "    在左子树调用 createTree() 方法 \n",
    "```\n",
    "\n",
    "## 找到数据集切分的最佳位置，函数 chooseBestSplit() 伪代码大致如下:\n",
    "```\n",
    "对每个特征:\n",
    "    对每个特征值: \n",
    "        将数据集切分成两份（小于该特征值的数据样本放在左子树，否则放在右子树）\n",
    "        计算切分的误差\n",
    "        如果当前误差小于当前最小误差，那么将当前切分设定为最佳切分并更新最小误差\n",
    "返回最佳切分的特征和阈值\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from numpy import *\n",
    "\n",
    "def loadDataSet(fileName):      #general function to parse tab -delimited floats\n",
    "    dataMat = []                #assume last column is target value\n",
    "    fr = open(fileName)\n",
    "    for line in fr.readlines():\n",
    "        curLine = line.strip().split('\\t')\n",
    "        # python3不适用：fltLine = map(float,curLine) 修改为：\n",
    "        fltLine = list(map(float, curLine))#将每行映射成浮点数，python3返回值改变，所以需要\n",
    "        dataMat.append(fltLine)\n",
    "    return dataMat\n",
    "\n",
    "\n",
    "def binSplitDataSet(dataSet, feature, value):\n",
    "    \"\"\"binSplitDataSet(将数据集，按照feature列的value进行 二元切分)\n",
    "        Description：在给定特征和特征值的情况下，该函数通过数组过滤方式将上述数据集合切分得到两个子集并返回。\n",
    "    Args:\n",
    "        dataMat 数据集\n",
    "        feature 待切分的特征列\n",
    "        value 特征列要比较的值\n",
    "    Returns:\n",
    "        mat0 小于等于 value 的数据集在左边\n",
    "        mat1 大于 value 的数据集在右边\n",
    "    Raises:\n",
    "    \"\"\"\n",
    "    # # 测试案例\n",
    "    # print 'dataSet[:, feature]=', dataSet[:, feature]\n",
    "    # print 'nonzero(dataSet[:, feature] > value)[0]=', nonzero(dataSet[:, feature] > value)[0]\n",
    "    # print 'nonzero(dataSet[:, feature] <= value)[0]=', nonzero(dataSet[:, feature] <= value)[0]\n",
    "\n",
    "    # dataSet[:, feature] 取去每一行中，第1列的值(从0开始算)\n",
    "    # nonzero(dataSet[:, feature] > value)  返回结果为true行的index下标\n",
    "    mat0 = dataSet[nonzero(dataSet[:, feature] > value)[0], :]\n",
    "    mat1 = dataSet[nonzero(dataSet[:, feature] <= value)[0], :]\n",
    "    #下面原书代码报错 index 0 is out of bounds,使用上面两行代码\n",
    "    #mat0 = dataSet[nonzero(dataSet[:, feature] > value)[0], :][0]\n",
    "    #mat1 = dataSet[nonzero(dataSet[:, feature] <= value)[0], :][0]\n",
    "    return mat0, mat1\n",
    "\n",
    "def regLeaf(dataSet):#returns the value used for each leaf\n",
    "    return mean(dataSet[:,-1])\n",
    "\n",
    "def regErr(dataSet):\n",
    "    return var(dataSet[:,-1]) * shape(dataSet)[0]\n",
    "\n",
    "# 1.用最佳方式切分数据集\n",
    "# 2.生成相应的叶节点\n",
    "def chooseBestSplit(dataSet, leafType=regLeaf, errType=regErr, ops=(1, 4)):\n",
    "    \"\"\"chooseBestSplit(用最佳方式切分数据集 和 生成相应的叶节点)\n",
    "\n",
    "    Args:\n",
    "        dataSet   加载的原始数据集\n",
    "        leafType  建立叶子点的函数\n",
    "        errType   误差计算函数(求总方差)\n",
    "        ops       [容许误差下降值，切分的最少样本数]。\n",
    "    Returns:\n",
    "        bestIndex feature的index坐标\n",
    "        bestValue 切分的最优值\n",
    "    Raises:\n",
    "    \"\"\"\n",
    "\n",
    "    # ops=(1,4)，非常重要，因为它决定了决策树划分停止的threshold值，被称为预剪枝（prepruning），其实也就是用于控制函数的停止时机。\n",
    "    # 之所以这样说，是因为它防止决策树的过拟合，所以当误差的下降值小于tolS，或划分后的集合size小于tolN时，选择停止继续划分。\n",
    "    # 最小误差下降值，划分后的误差减小小于这个差值，就不用继续划分\n",
    "    tolS = ops[0]\n",
    "    # 划分最小 size 小于，就不继续划分了\n",
    "    tolN = ops[1]\n",
    "    # 如果结果集(最后一列为1个变量)，就返回退出\n",
    "    # .T 对数据集进行转置\n",
    "    # .tolist()[0] 转化为数组并取第0列\n",
    "    if len(set(dataSet[:, -1].T.tolist()[0])) == 1: # 如果集合size为1，不用继续划分。\n",
    "        #  exit cond 1\n",
    "        return None, leafType(dataSet)\n",
    "    # 计算行列值\n",
    "    m, n = shape(dataSet)\n",
    "    # 无分类误差的总方差和\n",
    "    # the choice of the best feature is driven by Reduction in RSS error from mean\n",
    "    S = errType(dataSet)\n",
    "    # inf 正无穷大\n",
    "    bestS, bestIndex, bestValue = inf, 0, 0\n",
    "    # 循环处理每一列对应的feature值\n",
    "    for featIndex in range(n-1): # 对于每个特征\n",
    "        # [0]表示这一列的[所有行]，不要[0]就是一个array[[所有行]]\n",
    "        # for splitVal in set(dataSet[:,featIndex]): python3报错修改为下面\n",
    "        for splitVal in set((dataSet[:, featIndex].T.A.tolist())[0]):#遍历每个特征里不同的特征值\n",
    "             # 对该列进行分组，然后组内的成员的val值进行 二元切分\n",
    "            mat0, mat1 = binSplitDataSet(dataSet, featIndex, splitVal)\n",
    "            # 判断二元切分的方式的元素数量是否符合预期\n",
    "            if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN):\n",
    "                continue\n",
    "            newS = errType(mat0) + errType(mat1)\n",
    "            # 如果二元切分，算出来的误差在可接受范围内，那么就记录切分点，并记录最小误差\n",
    "            # 如果划分后误差小于 bestS，则说明找到了新的bestS\n",
    "            if newS < bestS:\n",
    "                bestIndex = featIndex\n",
    "                bestValue = splitVal\n",
    "                bestS = newS\n",
    "    # 判断二元切分的方式的元素误差是否符合预期\n",
    "    # if the decrease (S-bestS) is less than a threshold don't do the split\n",
    "    if (S - bestS) < tolS:\n",
    "        return None, leafType(dataSet)\n",
    "    mat0, mat1 = binSplitDataSet(dataSet, bestIndex, bestValue)\n",
    "    # 对整体的成员进行判断，是否符合预期\n",
    "    # 如果集合的 size 小于 tolN \n",
    "    if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN): # 当最佳划分后，集合过小，也不划分，产生叶节点\n",
    "        return None, leafType(dataSet)\n",
    "    return bestIndex, bestValue\n",
    "\n",
    "\n",
    "# assume dataSet is NumPy Mat so we can array filtering\n",
    "# 假设 dataSet 是 NumPy Mat 类型的，那么我们可以进行 array 过滤\n",
    "def createTree(dataSet, leafType=regLeaf, errType=regErr, ops=(1, 4)):\n",
    "    \"\"\"createTree(获取回归树)\n",
    "        Description：递归函数：如果构建的是回归树，该模型是一个常数，如果是模型树，其模型师一个线性方程。\n",
    "    Args:\n",
    "        dataSet      加载的原始数据集\n",
    "        leafType     建立叶子点的函数\n",
    "        errType      误差计算函数\n",
    "        ops=(1, 4)   [容许误差下降值，切分的最少样本数]\n",
    "    Returns:\n",
    "        retTree    决策树最后的结果\n",
    "    \"\"\"\n",
    "    # 选择最好的切分方式： feature索引值，最优切分值\n",
    "    # choose the best split\n",
    "    feat, val = chooseBestSplit(dataSet, leafType, errType, ops)\n",
    "    # if the splitting hit a stop condition return val\n",
    "    # 如果 splitting 达到一个停止条件，那么返回 val\n",
    "    if feat is None:\n",
    "        return val\n",
    "    retTree = {}\n",
    "    retTree['spInd'] = feat\n",
    "    retTree['spVal'] = val\n",
    "    # 大于在右边，小于在左边，分为2个数据集\n",
    "    lSet, rSet = binSplitDataSet(dataSet, feat, val)\n",
    "    # 递归的进行调用，在左右子树中继续递归生成树\n",
    "    retTree['left'] = createTree(lSet, leafType, errType, ops)\n",
    "    retTree['right'] = createTree(rSet, leafType, errType, ops)\n",
    "    return retTree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX8AAAD8CAYAAACfF6SlAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAH8JJREFUeJztnX+MZldZx7/PTGcok1bEd4o0wLxDk5JQiUJ3Qmg0iAG0rsnWxGpKptgKOuk0aKPGpGQTITUbicaYBSnLio3rzitU+ANWLGmkQCDGFqZCS1tT2dadpaGx260WZFHb7eMf933Zd+/cc+85955z7j3v/X6Sm3nf+94f57zv7vc893me8xxRVRBCCOkXc203gBBCSHwo/oQQ0kMo/oQQ0kMo/oQQ0kMo/oQQ0kMo/oQQ0kMo/oQQ0kMo/oQQ0kMo/oQQ0kMuaLsBJpaXl3V1dbXtZhBCSFLcf//9T6vqJVXHdVb8V1dXsb293XYzCCEkKURkx+Y4un0IIaSHUPwJIaSHUPwJIaSHUPwJIaSHUPwJIaSHUPwJSZXRCFhdBebmsr+jUdstIgnR2VRPQkgJoxGwsQGcOZO939nJ3gPA+np77SLJQMufkBTZv/+c8E84cybbT4gFFH9CUuTkSbf9hOSg+BOSIisrbvsJyUHxJyRFDhwAlpbO37e0lO0nxAKKPyEpsr4OHD4MDIeASPb38GEGe4k1zPYhJFXW1yn2pDa0/AkhpIdQ/AkhpIdQ/AkhpId4EX8RuUNEnhKRhwyfv0VEnhWRb4y3P/RxX0IIIfXwZfn/NYCrK475iqq+frzd5um+hHQD1tkhieEl20dVvywiqz6uRUhysM4OSZCYPv+rROQBEfmciPxE0QEisiEi2yKyferUqYhNI6QBrLNDEiSW+P8LgKGq/hSADwH4dNFBqnpYVddUde2SSyoXnyekG7DODkmQKOKvqt9V1f8ev74LwIKILMe4NyHBYZ0dkiBRxF9EXi4iMn79xvF9T8e4NyHBYZ0dkiBeAr4i8nEAbwGwLCJPAHgfgAUAUNVDAK4FsCkizwP4AYDrVFV93JuQ1pkEdffvz1w9KyuZ8DPYSzqMdFWD19bWdHt7u+1mENIvRiMOYokjIver6lrVcSzsRgjJYMpqr2B5B0Ji09UJYUxZ7RW0/AmJSZeta6as9gpa/oTE5JZbumtdM2W1V1D8CYnFaAScNmQ4d8G6Zspqr6D4ExKLMuu+C9Y1l4bsFRR/QmJRZt2brGub4LDPAPL6OnDiBPDCC9lfCv/MQvEnJBYm634wKBbZSXB4ZwdQPRccnhZ3m2Nmka5mTCUExZ+QWJh86gcPFh9vk3rpkp45K4LZ1wHPMxR/QmLh6lO3Sb20Tc+0fYpwHRyaDCh1z+V8BD+oaie3PXv2KCG9ZjhUzaT6/G04dDvG5ritLdWlpfM/W1rK9puoc46Pc0WK+yJSfW4PALCtFhrbusibNoo/6T02AmkrokViOS2YtoPINHXOCXnuYFB9bg+wFX+6fQjpKjZuIptjRqPssyImQeg6s3ubzAhucu6BA8DCwu793/se/f4OsKonIbPO6mrm488jAhw9mg0UpmOGwyzl0+W6Zef4OBcAlpeLJ8zZnj/D2Fb1pOVPSFv4zr4xXc9kTauee0KoM7u3yYzgprOJn3mmeH8XZkqngo1vqI2NPn8y05h89ZubmU9bJPtrEwAtu97Wlr1/fXKsy73rnOPj3CYxg9Btaxkw4EtIhzGJVz6TxTYDpkwMm2TWdJWiPi0uZkHfpoId+/vyPNBQ/AnpMqZ0RVMWy0QcBoNigatKf2zLQg/JdLsGA9WFBT+CHfqpYpoAAw3Fn5CYuAqkSWBcN1fXTp1+1cn/jz1Y+Ox/zHkEAX43ij8hsfA1QcrlaSCWa8dVnNpyMfkU7JiWf4CBhuJPSCzqikXeQt7c3C2cNlsd147tsa7iFFM4Q9035gBGy5/iTxLGp/WW92PbWv6u97AVN1dxaqv0QlGfFhbqB4Bjua7o86f4k4QxiXRTa9cmLlBHKFwE3VWcmlqyvgLTg0GW/RPb/VQHZvtQ/EmCbG3tzjIBMuFpKjRlMYAmQuFqnbu6k9oo9panLfdTB7AVf5Z3IKQJpjIFgwHw9NNhrt20hEGo604YjbLyyidPZrWDDhwwl62ePnZuDjh71k+75uYyuc8jkq1SNsOwvAMhMTCVEzCVH3Ah1ILqoRdqt10KcjQC3vWuc2sMFAk/UK9kg2nVtKZrJc/KgjgA3T6ENCLVMgNdmLgVKqCtWu5CKuq7zfeRyExp0OdPSGC2tooFrIOC4AXfA4aN8Df5Lk0iX5QVZBMcTiSOQPEnJCRFIgJkg8GsCr9vq7dM9E0DTNMByGVmdV7UE1lBjOJPSEgSsQK9UWemb5VIm9w+phW5TAMuoDo/n02Sq8JlFnVe1BP5zW3FnwFfQurQZCWqCSkFD136a7NYPAAcPFi8ItfkGnmKFm6fcPYs8JGPADffbO4D4BbwVT3/dwkZKB+NsgVqRLJteTn8vwebEaKNjZY/6TQ+JjP5nJEaGpf+VpWXzpe0sI2b2Fjt8/Pl/bD1+ZvaEqKExtZW8f0XFmr9GwDdPoQExNYHbhKAULN3Q+Hi8y8T6aJr2M6QtvXX2/TFlO1TNqi4zjZuWkKjpkuJ4k9IaPLlBPJWe5l1b+t37pI/2daSNYnZ/Lx9v4HdPvcyn7+t5V9F1cDVdHAv+j2rnmgcofgTEguTleci8rYCWKdt0+2IkY1k+j5c+26qNVRmKdsEfcuoerrIL6xT5K4p+92Lfs+ye4o4/14Uf0Ji4WthFlsBtCVk3aGie+V9+XmL2PQ9DQb10kg3N889Tdhm+9j0o85A1XRAK4s5OP4biCr+AO4A8BSAhwyfC4APAjgO4EEAV1Zdk+JPkqHuIix5AfRdhdKnD7sMl/iHy6xb1zb4moC2teXuorLZygK4W1vm8xyf/mKL/5sBXFki/nsBfG48CLwJwH1V16T4k2RoavlPLDvfM2irBiUXH3ad/pe5bXxmNIWYgGZ6amo6wJfhaR5BdLcPgNUS8f8ogHdMvX8UwKVl16P4k2SwdRX4tO5tRNRmUJoWlroiWnb9GISYfFXliqmzVVnwngaxron/ZwH8zNT7ewCslV2P4k+SoioQWWbd2xYVmw405q1SkxVfZb1OC1JdETW5SJpm3tgSouyC6bvI32thQfWii+zE32Yw8vBk1DXx/4cC8d9TcNwGgG0A2ysrK86dJqQ1psU/LxBl1puNtWf7ZGFys5Rln0y7IuqKaAjL30UEQ1j+ZS6zonbVGZwD0TXxp9uHzC5F4jwRDx/CZRtTKBNpm1mkdUXUt/i6uj9CzJb2MYPbd2zDkq6J/y/lAr5frboexZ8kQxOhsLG2bbOJqu5XNZO2rs/Zd8C1zveZt7ybxlaa9qkv4g/g4wCeBPAcgCcAvBvATQBuGn8uAD4M4DEA36zy9yvFn6REE5+zL8vfRphs2ukaf5gc4zPnvqkP39eTSF0BD5F95AAneRESiyZiY+MyKjpmcdHdrVE2ycqlWFndxVBsqQqc+xjkQhIiBuEAxZ+QWPhyEUwLf/46PtwIpkGkKCPIVAbCZU5D3fkLVQHuqu+2ZfFte/Ch+BMSk7LyBkVF34qwrW7ps51lmUB1yypPi51pYCwq/1DUzqqBxdTHNtfapeVP8Sc9pY7l6nF6vxNVYp4XLFfL3zZf3uTGqmtFxwi4mu5Bnz/Fn/QUm2qeLqIa0mKsEnObssplPv+6dY8m57ftwjFRJfB9yfYJsVH8SZKUWfBlolomkiGFo+opxbY+j0nsmtQ9mlynLSu6TMA7PA+A4k9IG9iKna3lX1UMzAemWcA+RLYsm8l2gGzDiq4adJoEdQMPaBR/QtrARtiKFujwIQhNRbJu3SHX625u1i9XEYsqy76J5R/YlUXxJ6QNbC3/IpoIbQhrcnNz92Am4m/RFNdMo/z5IZ8Gqiz7Jt934FRQij8hbWBThC2ERRuivk6ZSPkQW1ObqxaaiREHsPk+6w5AtPwp/mRGsZm05Rvf1mTVE4wPoarb5hgZQCEHmI74/OdACPHL+jpw4kT23/roUWA4BESyv4cPZ5/7ZmXFbX8VJ082+9yGum023btOm0YjYHUVmJvL/o5G2f719ey3CvHbhby2CzYjRBsbLX9CHKg7k9ZEDMu/rgXss3BbmzOBAwG6fQjpGTZZNbbiVha78CmQdfzmvkS7qxPIGkLxJ6RPFIlombi5lG6eBGGnzw3R3pjnq7ZegC0UtuIv2bHdY21tTbe3t9tuBiHdZzQCNjaAM2fO7VtaOv99nvznS0vh/M6jEbB/f+aTX1kB9u4FjhyJd38Tq6vAzs7u/cNhFrNJFBG5X1XXqo5jwJeQ1Nm/f7fQnzkDzM8XHz8/X3z8/v3+2zYZmHZ2Mrt6Zwc4dCje/cs4cCAbdKZZWsr2x8YUeA4IxZ+Q1DFluZw9WyxuZ8+6XacJRQOTydsQ4v5ldCXrpmiA3NgIPgBQ/AlJHVNq5ETM8uI2HLpdpwkugu7z/nlL+uabzSmdJ04AL7yQ/Y0t/ID5yS30k5BNYKCNjQFfQtQ+MOuS/RIzxdG2nr9LFlKd7yNkxlJTPAeewWwfQhLHRaRds198Lrhehs/5B7bfR93Kqm3hOeWU4k9I6oTKQ489uclXETbb78O1ZHTbeP49bMWfPn9CuorPMgbTxPYx+/Kr234ftrGDEDEOG/LxCKCVwDPFn5Cu4rtez4RQg0pobL+PohTOPG2mdBZl9gDRA88Uf0K6Sqg89FCDSmhsv4+iFM7NzfZTOoH2MnuKsPENtbHR50+Ihlm0JOWCZi0ujO6FCCUlQJ8/ITNAiDz0rkxuqkMX8vKrKJut26GnLoo/IbOCS4mAFEQ0Rapm63aopATFn5BZoKUSASRHlU+/Q09drOpJyCwwoxUqk2Nurrh2kUj2lBUBVvUkpE+kmr45a3TIp18FxZ+QWSAh0ZlpOuTTr4LiT8gsEFN0Wqg9nwwd8ulXQfEnZBaIJToxAsupDy6JZFIx4EsIsSd0YNm0JGVHrecuwoAvIcQ/oQPLXSp/MONQ/Akh9oQOLBc9VZTtJ7XxIv4icrWIPCoix0Xk1oLPbxSRUyLyjfH2mz7uSwiJTOjActmi88QrjcVfROYBfBjALwK4AsA7ROSKgkPvVNXXj7ePNb0vIaQFQgeWTYvLm/aT2lzg4RpvBHBcVR8HABH5BIBrADzi4dqEkK6xvh4u+DocmgPKxCs+3D6vAPDtqfdPjPfl+RUReVBEPiUir/JwX0LIrJHQJKnU8SH+UrAvnz/69wBWVfUnAXwewJHCC4lsiMi2iGyfOnXKQ9MIIUmR0CSp1Gmc5y8iVwF4v6r+wvj9ewFAVf/YcPw8gGdU9SVl12WePyGEuBMzz/9rAC4XkVeLyCKA6wAcyzXm0qm3+wD8q4f7EkIIqUnjgK+qPi8i7wFwN4B5AHeo6sMichuy5cSOAfgdEdkH4HkAzwC4sel9CSGE1IflHQghZIZgeQcbUi8gRQghNfGR558m+QJSk+qEADMLCCEzT38tfxaQIoT0mP6KP5e9I4T0mP6KP5e9I4T0mP6KP6eRE0J6TH/Fn9PICSE9pr/iDySz1iapgCm7hDjT31RPMhswZZeQWvTb8ifNadvqZsouIbWg+MekbaH0zcTq3tkBVM9Z3TH7xZRdQmpB8Y9FF4TSN12wupmyS0gtKP6x6IJQ+qYLVjdTdgmpBcU/Fl0QSt90wepmyi4htaD4x6ILQlkXU6yiK1Y3U3YJcYbiH4uuCKUrZbEKWt2EJAsXc4nJaJT5+E+ezCz+Awe6L5Srq5ng5xkOMyubENIpuJhLTGxTOFN0T8xirIIQQvFvTKopnLYDlo9YxazNbyBkBqD4N8VHCmdscXQZsJrGKorudf31wPIyBwFC2kRVO7nt2bNHk0BENZO18zcRu/O3tlSXls4/d2kp2x+K4bC4zcOhuY3DYdan4dCtbaZ7xegnIT0EwLZaaCwt/6a4ukXyVv4tt7g9Ofh4SnD149eJVUzaWRQsnnDmDHDDDXwCIKQFKP5NcXGLFLlATp8uvm6REPuKL4SeczDdzirOnk0jRkLIjNFv8fdhRbvkuhfFB0wUCbGvEhGh5xy49BNIv8wFIQnS3zz/fB14IBPAkJOU5uYyi70KUztM54tkLhkXQs45sO3nNHX6QAjZBfP8q2ij0JrJrSJy/vsXv9jt/DrumpBzDkztGQyA+Xm3cwghQeiv+LcxeanI3QLstpJPny72g6dSIsLUzoMHgSNH0ugDITNOf8W/jUJr+fiAyQoGip9CJucPBuf2mZ4S2qQsDsJ6QIR0A5t80Da24Hn+PvLrm+S/q5rnCJjmCmxtqQ4GzJcnhBhB7/P8qzJ5mlqgPtIuq54ypj+f3K8oNXRWs2VYFoKQcNiMEG1sjSz/GLNmXWfJ2rbT1N6ymbIuM4pToY2Zz4TMAOi15R8jk8cUGN7ZsbdSp58+gHMxgKKnkKpAtO9YRdtWd8jfsO2+EdIFbEaINrbalv/WVrmFXHaei/++yhKP9aQR4l5dsLqb1kwy0YW+ERIQWFr+rYu8aasl/mVulMlW9J+8TBBMg4LNvVxcQHX7Nhg0E66i/vlwadW57zSh2hCjb4S0SD/Fv8oaN/0nN503GJRbiWVCaWulujxxNM0uKrpeUf9CxxVsrG+fFvr099aXmAnpLf0U/6rUSdN/cpvzygaQutZk2y4IU7vn5+v1p4qqwTJ/fR+Dnc0TGi1/MkPYiv9sBXxtgp5Fx7gGS/PB1717i48z7Z/QRomJaUxB5LNn/c/Ctan0mW+PjxIUtkXmqn4rQmYML+IvIleLyKMiclxEbi34/EUicuf48/tEZNXHfXdhKp8wwSRgpnIE0zNpp8kPFnfdVXycaf+EttfHNQ16k2yjsjkQrhkzNiIcYna17XdZ9VsRMmvYPB6UbQDmATwG4DIAiwAeAHBF7pibARwav74OwJ1V122U7TNxFQwG2VbXn27rlqmbmRIi+OgaQ6jjdqoTIK9yrYVyd9nEgejzJzMEYvn8AVwF4O6p9+8F8N7cMXcDuGr8+gIAT2NcTtq0dWYZR9OgML2vqORCGz7/Oter41evEyCv8vWHinPQ5096RkzxvxbAx6bevxPAX+SOeQjAK6fePwZgueBaGwC2AWyvrKyE/YbqUiQmi4uqCwvVomszkDQRQZcniSb3rRMgbzO4nX8aXFxspx2ERCCm+P9qgfh/KHfMwwXiPyi7bmcs/zxlVm+ZmMYQP1v3U9O22LpS8vf3napal660g5AA0O0Tii77923dT01dMKbBo677ixDiDVvx95Ht8zUAl4vIq0VkcRzQPZY75hiAG8avrwXwhXEj06PuOgC+M3tsF4MvynAqu6dNdVJTRdSDB+1SRLtUW6dLbSEkJjYjRNUGYC+Af0Pmztk/3ncbgH3j1xcC+CSA4wC+CuCyqmt21vJ3dZm4Tmyyxcb1Yir9UHcmtA1VLpW2J7Z1tS2EeAK9nOEbC1ufcVWmSROhsQm6mgTcJgNGJIxvvEu1dbrUFkI8QfHvAiHTG22s97I4RNUTSVVdo7qEqtYZsi0MEJOEsBX/2SrvEJI6vmGTb12kfrmCCVWzmYHyOMSkdMLWVrGfHghTeqKNtZNN2LTFx4pthHQRmxGija1Tln9d33Bot0LV2gW2FmqRZetioTedVTy5l4tVHarom+0KanQNkY4Cun3G+BCJLlftLJt3EOK6RZU3684qnhZ+l+8nVLnnon8fXXJTEWIBxV/Vn0g0EYDQ/uJQA4ztdZtYxnXPjWmN0/IniUHxV/X3H7frAhBqgLG5rsnlVDUwbm7WPzeENW7qK9NBSWJQ/FX9iUQfBcBG+MtiA2UDY5nwt2H5V8UhNjeZ7UOSgeKv6lck+pTu19TlA5R/P6aVwtrw+Vf1ow8DPZkpKP6q/bTYfWA7aJZNNCv7jsuENma2j00/uubiI6QCW/Gf7Tx/Uw2aJvn1fcC2DlFZbn7ZfID5efN+29/GZolH27kZNnMMYq2uRkgkZlv8AT/rwPYN24lYZWv6lonlxkbx/gsv9FdgzWVyVtMJc4QkyOyLP3HHtKZxXuzX18vXOTZZ3rffDmxunnsCmJvLXn//+9VCbUvRmsGmGcrTT4hA9pQ4TdPF6wnpIja+oTa2Ts3w9UkqgeP86lemtZBNcZXNTft4S4hU2i7PzSAkIGDAt4OkGIC2aXORWLoIeoi8/a7PzSAkELbiL9mx3WNtbU23t7fbboZfVlczl0ae4TCLR3SRum2em8vkNo9IFn+xucdgAFx0URY/WFnJXC+2MZuJz3/a9bO0xIA/mXlE5H5VXas6jj7/mPhezSsGddvsUr2zKMawuAh897v1q2ky04uQUij+dai79F+XyhnbUrfNtkFjoFioL74YeO65849zLSnNTC9CjFD8XWlS391FELtC3Ta7Wt55oX7mmeLjuvyUREhK2AQG2tg6G/BtGkhMMZOkjTYzYEtILcAZvp7Iu3iKApOAvUWaoiuijTbv3eu2nxDixAVtN6DT5DNGdnYyF0ZRFkuX/fYpctddbvsJIU7Q8i+jaJaoarMZoHWDxaGv1TVSzIwiJCEo/mWYhEZ1dyATqBZin4uBz/rC4ilmRhGSEBT/MkxCMz+fWfoTHzhgJ8Qu9WaqqHOtlJ4UUsyMIiQlbKLCbWydyPYpKm1QVOKgaf37OmUMXK9lWq1qc9P93rFIMTOKkJYBs308MMlVL6o/P21lN61/X8eV4XotU/zi0KH4TwC2TyA+a/YTQs7HZoRoY+uE5T+hysq2tfx9FnZzvVbZalUxc+fb/A4I6QFgVU+PVIm7iwj5dGW4XKtsndom1TNd8Tl5ixPBCNmFrfizqqcNNhUiR6PMtVKnAmUMRiPgne8snqMQs6qoS7XPmNciZEZgVU+f2NSp6frM3fV14Kab2l+lqs24ByHkh1D8+8TttwNHj7Zb5thnCifTQQmpj41vqI2tUz5/Bhb90lbcg5AeAPr8PZLiClyEkF5Cn79P+lpnhjn0hMwsFH8b+hhYnPXaQYT0HIq/DX0MLPqsQ0QI6RyNxF9EfkxE/lFEvjX++1LDcWdF5Bvj7ViTe7ZCHxcD76uri5Ce0NTyvxXAPap6OYB7xu+L+IGqvn687Wt4z3boeh6/b/ro6iKkRzQV/2sAHBm/PgLglxtej3SFPrq6COkRTcX/x1X1SQAY/32Z4bgLRWRbRO4VEQ4QKdBHVxchPaJyDV8R+TyAlxd85BL5W1HV74jIZQC+ICLfVNXHCu61AWADAFboXmif9XWKPSEzSqX4q+rbTJ+JyH+IyKWq+qSIXArgKcM1vjP++7iIfAnAGwDsEn9VPQzgMJBN8rLqASGEEGeaun2OAbhh/PoGAJ/JHyAiLxWRF41fLwP4aQCPNLwvmTU4oYyQqDQV/w8AeLuIfAvA28fvISJrIvKx8TGvBbAtIg8A+CKAD6gqxZ+cgxPKCIkOa/uQ9mHtJEK8wdo+JB04oYyQ6FD8SftwQhkh0aH4k/bhhDJCokPxJ+3DCWWERKcyz5+QKHBCGSFRoeVPCCE9hOJPCCE9hOJPCCE9hOJPCCE9hOJPCCE9pLPlHUTkFICCOf/WLAN42lNzUoF97gfscz+o2+ehql5SdVBnxb8pIrJtU99ilmCf+wH73A9C95luH0II6SEUf0II6SGzLP6H225AC7DP/YB97gdB+zyzPn9CCCFmZtnyJ4QQYiBp8ReRq0XkURE5LiK3Fnz+IhG5c/z5fSKyGr+VfrHo8++JyCMi8qCI3CMiwzba6Zuqfk8dd62IqIgknxli02cR+bXx7/2wiPxt7Db6xuLf94qIfFFEvj7+N763jXb6QkTuEJGnROQhw+ciIh8cfx8PisiV3m6uqkluAOYBPAbgMgCLAB4AcEXumJsBHBq/vg7AnW23O0Kffw7A0vj1Zup9tu33+LiLAXwZwL0A1tpud4Tf+nIAXwfw0vH7l7Xd7gh9Pgxgc/z6CgAn2m53wz6/GcCVAB4yfL4XwOcACIA3AbjP171TtvzfCOC4qj6uqv8H4BMArskdcw2AI+PXnwLwVhGRiG30TWWfVfWLqnpm/PZeAK+M3MYQ2PzWAPBHAP4EwP/EbFwgbPr8WwA+rKr/CQCq+lTkNvrGps8K4EfGr18C4DsR2+cdVf0ygGdKDrkGwN9oxr0AflRELvVx75TF/xUAvj31/onxvsJjVPV5AM8CGERpXRhs+jzNu5FZDalT2W8ReQOAV6nqZ2M2LCA2v/VrALxGRP5JRO4VkaujtS4MNn1+P4DrReQJAHcB+O04TWsN1//z1qS8mEuRBZ9PXbI5JiWs+yMi1wNYA/CzQVsUh9J+i8gcgD8HcGOsBkXA5re+AJnr5y3InvC+IiKvU9X/Cty2UNj0+R0A/lpV/0xErgJwdNznF8I3rxWCaVjKlv8TAF419f6V2P0I+MNjROQCZI+JZY9YXcemzxCRtwHYD2Cfqv5vpLaFpKrfFwN4HYAvicgJZL7RY4kHfW3/fX9GVZ9T1X8H8CiywSBVbPr8bgB/BwCq+s8ALkRWA2dWsfo/X4eUxf9rAC4XkVeLyCKygO6x3DHHANwwfn0tgC/oOIqSKJV9Hrs/PopM+FP3AU8o7beqPquqy6q6qqqryGId+1R1u53mesHm3/enkQX4ISLLyNxAj0dtpV9s+nwSwFsBQERei0z8T0VtZVyOAfj1cdbPmwA8q6pP+rhwsm4fVX1eRN4D4G5kWQJ3qOrDInIbgG1VPQbgr5A9Fh5HZvFf116Lm2PZ5z8FcBGAT45j2ydVdV9rjfaAZb9nCss+3w3g50XkEQBnAfyBqp5ur9XNsOzz7wP4SxH5XWTujxtTNuhE5OPI3HbL4zjG+wAsAICqHkIW19gL4DiAMwB+w9u9E/7eCCGE1CRltw8hhJCaUPwJIaSHUPwJIaSHUPwJIaSHUPwJIaSHUPwJIaSHUPwJIaSHUPwJIaSH/D+PaArUYDc6eAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "({'spInd': 0,\n",
       "  'spVal': 0.48813,\n",
       "  'left': 1.0180967672413792,\n",
       "  'right': -0.04465028571428572},\n",
       " None)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myDat=loadDataSet(\"./input&code/Ch09/ex00.txt\")\n",
    "myMat=mat(myDat)\n",
    "mM=createTree(myMat)\n",
    "import matplotlib.pyplot as plt  \n",
    "plt.plot(myMat[:,0],myMat[:,1],'ro') \n",
    "mM,plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAW4AAAD8CAYAAABXe05zAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAHitJREFUeJzt3W2MXFd5B/D/s+PZwsRJqWddCZHsLEhQESG14BUKimhpQFW6ReQLqkBr44aolnerylWLKqT90Dftl0qldSVixyo2xjsF+iK1UeSqaksi2ogE1iW8pqBAvSYFNc4akjimeL1++uHszdy9c8+959y5rzP/nzTa3dk7954bb54585znnCOqCiIiao6pqhtARER+GLiJiBqGgZuIqGEYuImIGoaBm4ioYRi4iYgahoGbiKhhGLiJiBqGgZuIqGH2FHHSmZkZnZubK+LURERj6cKFC8+r6n6XYwsJ3HNzc1hfXy/i1EREY0lENlyPZaqEiKhhGLiJiBqGgZuIqGEYuImIGoaBm4ioYRi4iaga/T4wNwdMTZmv/X7VLWqMQsoBiYgS9fvAkSPAtWvm540N8zMALC5W166GYI+biMq3sjII2oFr18zzlIqBm4jKd+mS3/O0CwM3EZVvdtbvedqFgZuIyre6CnQ6u5/rdMzzlIqBm4jKt7gInDoF9HqAiPl66hQHJh0xcBNRNRYXgYsXgZs3zde0oM3ywVewHJCI6o/lg7uwx01E9WcrHzx4cCJ73wzcRFR/SWWCQe97lODdsDQMAzcR1V9ameAok3eCNMzGBqCazxtBwRi4iaj+4soHo7JO3mngLE4GbiKqv3D5oE3WyTt5zOIsOdXCwE1E9ZAW/ILywbW1fCfvjDqLs4JUCwM3EVXPJ/jlOXmn3weuXh1+3ueNoIJUCwM3EVXPN/j5Tt4JC3r2IsChQ8Dm5u7fd7vxbwS2TwQVLJjFwE1E1Ssr+IV79oDp3Uf96EcmoIeDc9InggoWzGLgJqLq7dsX/3yW4JeUK4/r2Udtbw8H56RPBBUsmMXATUTV6veBF18cfn7PHv/gF9czPngQmJkxv/PtwQfBOekTQQULZjFwE1E5bD3hlRVga2v4+Bs33M8ROHYsvke9uWkCuq1nn+TSJXvPf2rKPIKed5acexaqmvvjwIEDSkT0irU11U5H1fSDzaPTMc+L7H4+/Oj13M4R/N52nvAjer3g51bL3oa4a0cf4bZkAGBdHWOsaFxyPoaItACsA/gfVX1v0rHz8/O6vr4++rsKEY2HubnBgGBYMKEm7neAST3cvJl8jlYLOHvW9Hpt54k7r6q5fpCOOXZsuMKk0xmkPYJc96VLppe9vT183m4XeP55tzYMNUkuqOq8y7E+qZJjAJ7O1CIimmxJOeLVVRNI44RTFLZzbG/vrhRxEQTtixfNz0eOpJcFhksQgzeTqM1NYHnZvR0ZOQVuEbkdwK8B+Ktim0NEYympZG5xETh6dDh4RyszkipM0ipF4gRvBLZKk7177bnqpLacPFmbKe9/AeD3AVjeZgAROSIi6yKyfvny5VwaR0RjIq1k7sEHgXPnkiszXBaa8hEE3yw15EnVLqqFL1CVGrhF5L0AnlPVC0nHqeopVZ1X1fn9+/fn1kAiGgMuJXNpsyGDc7Ra/tdP6s37TqAJct1JCpw1Cbj1uO8G8D4RuQjgMwDuEZG1QltFROMlPLA3O2uCZpaSucVFMxDp0/PudEwqxvam4TOBJjrz0qbAWZMA/MoBAbwLwCNpx7EckIhekVbGl/WcSaV5vZ4p8wtK+WznCI7rds0j7TW9Xnq5YcZ7QxHlgAAgIu8C8BFlOSARuUoqBQyqOrKYmRmuBAHcSvKimw8Du0v/bKam4tc3AUxvfoRPE0WVA0JVH0sL2kREuxS1gNTx40C7vfu5dts8nybrUqy2FMgtt5igvrEBHD5ceEkgp7wTUbGKWj1vcRE4c2Z37vrMGbfebtY3k7h8eKsFvPzyYELO9jZw4kShwZuBm4iKVeTqeVnX5c76ZhJXHWObjHPqlFtbMmDgJqJiuZQC+u7ZOOoej1nfTKLVMQsL9px33JT4vLiOYvo8WFVCRM58q07yqlIJV5UkVZIkXTdpgaxWy6s5KKqqxBWrSojImW/VSVFVKmls17VZWjIzQh0VVlVCRJSZ756NGxuj7fGYNZ3i2844t9ziFbR97SnszEREgWjddLAtGGByxXE9WZHB8y7HhwcWk66XNICZtZ3hzEWnAzz0kP0aeXDNqfg8mOMmol1sMw5tmxTYcse246M57qTr5dnOTkd1ackvV24Bjxw3AzcRFc8WiEXM76MDhUm718QdHw2WadfLq52jTNuP8AncHJwkouKVPQCZ9fVVDXyCg5NE9TdqHXLT+NZNjzppJ+vri5wslCfXrrnPg6kSogRFrJbXBFnqpkdJS2R9fYHpkCRgqoSoxir8ON5Yea3nXWM+qRKWAxKVrajV8sZV1tK+McYcN1HZilotb1xlXYJ1jDFwE5WtKQNgdcFPKEMYuInK5rJaHg3wE8oQBm6iKmRdR3oS8RPKEAZuonEyjvXh/IQyhIGbaFwE1RcbG6Y6PKi+sAXvJgV5fkLZhYGbqCxFB0qf6gvfIE+1wgk4RGWI1iIDJk+b50f+qan4bbREhvdF5CSg2uFaJUR1k1ctclKv3af6giV2jcbATVSGPAJlWnrDp/qCJXaNxsBNVIY8AqWt1374sAnePtUXo5TYRXv9y8vNGeQcF66rUfk8uDogUUTWFQHDK9XZNhcoa5dz233k0RbiDjhEtRQESkC11dJdW2LZjk8LknHbcq2tqXa7g+e73fwCadLuND5bhNEQn8DNqhKiMvlUl9gqP2xEgHPngPvvB7a2hn8HmLDaapk2ZNmF3Fa5EteWaCULJWJVCVFd+VSX+FZ4zM6a80SDNjDoCwPA9jZw4oTJTaeJ5rP37XNri+txlElq4BaRV4nIF0XkKyLyDRH5ozIaRjSWfKpLfCs8Fhb8gv2pU+arrcQwrorlpZeAdtuvXZQ7lx73TwDco6o/D+AXANwrIncV2yyiMeVTXRJX+ZHk/Hm/YL+9HR+cDx0yqY7Dh4c/HVy/Dtx226ByxebKFfd2kLfUwL2TN7+682N755F/YpxoEviU4UXL+9JcuuS3Yl6rFZ+6CadU4ly5Mlg3pNuNP4apkkI55bhFpCUiTwF4DsC/qOqTxTaLaAwF+yZeu2aCJpC+0l14caVeL/n8s7Pm+KUlt/YcOZJtpqRLr/6HP2Rdd5Fcy092qk9eA+BRAG+J+d0RAOsA1mdnZ4uunCFqljx2dk8qD4yeK1x6GPfYu9ccFy4bdHlEr5NWX866bmcoso4bwB8A+EjSMazjJoqwBVHfeue8asGD2m6XwN1q2SfpsK47Nz6B26WqZL+IvGbn+1cDeA+A/yqg8080vvJa1ClInagCN26Yr8FqfnGVIUGePJqL3tw0qZLNzeTrdTrA2bP2dbBdB1C5eFWuXHLcrwXwqIh8FcCXYHLcjxTbLKIxYxuscx3EiyvZC54TMZUgtsWnFheBvXuHzxnOtcdptQY15rY8dXQA1XY+Ll6VL9euuc+DqRKiCFtKottNf+3ammq7vft1U1Oq09Pu6YmkXHQ0ldJuD587nKcOr3HS7ZpHkEpZWho9lz+hwCnvRDXjs8lB1MxMekojTvjcSRsnrK6aXvWlS6ZnfPVq/PWCdEtSWzodU/99/vzgfKurE7/VmAufKe97im4MEcEEsLjA6ZJCyBK0o+deXY1fIyUIquHAOmXJoLq049o1E7S5i06huFYJURlGWf86i3Z797nDuWggOX89aj7aZ2EsyoSBm6gMPpscRNlmJya57bbhcy8uDt5AglmRcZsE+061j0oa8KRcMHATlSU8CzKphC/q+HFgetrvWra1QlxWJ4x7k/F587BNlafcMHATVSFt/8iwxUXg9On0krswW7rDtZ48+iZz/Lh7Lzxtaj6NjIGbqAq+u76HA2laFUpS7twW0NPqyeN64UtL5ebt6RUM3ERVsA3guQzsJQ0epuXOV1fj19N+6aX0xaCivfAHH8yet6eRsI6bqAp79sTnglstM5U9ic/2Z3FsdeG9Hsv4KsSty4jqzjaA5zKwN0qFCmAfuOR6Io3BCThEVej17DMZXUQnzfgYZTIQ1QJ73ERVKHtCTl2uTblg4CaqwqjpjqZem3LBwUkiohrg4CQR0Rhj4CYiahgGbiKihmHgpskVtx0YUQMwcNN4SgvKPos8EdUMAzeNH5eg7LvIE1GNMHDT+HEJykmLPDF1QjXHwE3jx2XN6aQ1rZk6oZpj4KbxY1tzI/y8y2JOSakTDmxShRi4afzY1uJYWBgEW9d9EeN67xzYpIoxcNP4iVuL4x3vAE6eHARb130R43aG4cAmVYyBm8ZTeLeW1VXgc58zATuq1TLBvds1mxtEvfjicE/add9GooIwcFMz+eSYV1bigzZget6zs2Zzgbi9HLe2hnvSLjl0ogIxcFPzxOWY77/fbMkVF8jTesLBeWyb8EZfz/WsqWIM3NQ8cTnmrS2zj2IQyD/0oUEgnxrxz3x2dncPf2UFOHx4eD1rgJUmVAoGbmoel1zyzZuDQO46EBlHxFSjRHv4Z8+aHnaw4/njjwOHDrHShEqRGrhF5A4ReVREnhaRb4jIsTIaRmRVZi5ZFTh/PrmKpN83FSvRPDorTaggLj3uGwB+T1XfDOAuAL8lIncW2ywaW3lMXInLMRel10uvIkka/GSlCRUgNXCr6g9U9T93vn8JwNMAXld0w2gM5TVxJVqn7ZrD9s11BwOOaVUkScGZlSZUAK+/ZBGZA/BWAE8W0Rgac1knrsT10sN12p/6FDA9nXyOTsdeNRJnamqwgW5aFYktOIuw0oQK4Ry4RWQvgL8H8Duq+mLM74+IyLqIrF++fDnPNtK4SEs5LC+bSTAi5uvyslsvfXEROH16d5XH0tJw1Uev597WcJBP2xV9YSH+HPfcw53TqRBOu7yLSBvAIwD+WVU/lnY8d3mnWHNz9uVUp6eB69eHn9+7F7h6dfj5Xs/0uH30+6byw+Fv3usatvvK0kaaWLnu8i4iAuATAJ52CdpEVkmDinFBG4gP2kC2Qb/FReDoUdNrduF6DU6Bp5K5pEruBnAIwD0i8tTOw/LZkChBkHJwXZkvSdZBvwcfBM6dG6Q9ut3Rr8Ep8FSymFV1dlPV/wDg2EUhStDvm4HIUSbEAKNNLw/acOmSCay2Hr3PwOLqqsm7hwdeOQWeCpQauIlyEQwyRqtKsggPDI7SBlu+HTB5cNdrBMeF3xBWVzkwSYXhlHcqR1wpYBa9XvaA6NMGWwWKbQJRuDzx4kUGbSoUAzeVI4+BuuguNr4zL13bYEtzcOcbqgkGbipH1oG6YKODXs+syHf2rHvgjPaO43azAcwAZVyNdvT1x45x5xuqBQZuKkeW9UU6HROog/RD2mJPgX7fLOl68ODuIP/ii8MzLDsd4Pjx4TRHXO96czO+nUm5cqICMHBTOaKzD5PEzU4E7KmOjY1Br3h52QTcuCC7tQXceqt9BmSYTz48j/JGIg9OMyd9ceYkpcoy2zBp5mVAJHlmpIjbmiVTU+4zLAG/Y4li5DpzkqgQWbb/ckm3pAXQUSfVxPFZA4UoBwzcVI20hZtcXuPLZ1JM3JvE9DTQbmc/J1FOmCqh5rKlTuLSJd2uGYT0qa+OzrIMAjQn2lABfFIlDNzUXHGzMTsdUzZ4/jyDKzWKT+DmlHdqLk41pwnFHHfV8tiDcZJxqjlNIPa4qxS36NGRI+Z7BiAismCPu0pZ92CsK356ICoFe9xVGqedU/jpgag07HFXaZx2Thm3Tw9ENcbAXaUsswcDdUtLjNOnB6KaY+CuUpbZg0A914Uep08PRDXHCThNlGWBpqLZJsNk3WaMaMJwkamm8U171DEtkfXTAxF5Y+CuWpa0x6hpiaLy45wMQ1QKBu6qZanGyDKoGQRrEeDQoXrlx4nICwN31VzSHtEeMuCXlgj36oHhlfNYtkfUKJyAU7XZ2fiBxqmpQS84OrHl0CHg6FH3gUiXbbhYtkfUGOxxV822q8v2tgnYcTuLqwInT7qnN1yCsm0HdCKqHQbuqgXVGHEbzl67Zt9ZXNU9vVF1LXXdJgsRNRwDdx0sLrptYBvlmt5w2avxyhX/6weSAnMdJwsRNRwDd13YesXdrv01rumNcI217/XTpAVmrmFClDsG7rqwlfgdPw7s3Tv6+YMa67W14eu028DVq9lSGWmBOW7gNel5IkqVGrhF5LSIPCciXy+jQRMraebhyy/HvyZLeiO4Trgnv7VlculZUhm2dM3GhjlHXO4esD9PRKlcetyfBHBvwe0gwD7zsIgFnH78Y/vvfFIZSW04csRUx8SxPU9EqVIDt6p+HsAII1c0slGWf42TZ1130sDntWv2nnVSvp2IEuWW4xaRIyKyLiLrly9fzuu01O8PAm0QBEddwMklKLv25oPUi832dr5vOkSUX+BW1VOqOq+q8/v378/rtJMtOlU9CIKrq6Mt4ORSjXL1qt8gpUj888GbDFcNJMoNq0rqrIhSun4feOml9OM2N90GKft94PDh4fVPABOogzcZrhpIlBsG7jrLsu522izFlRXg+vXh103F/ClE3ySi515eTh6AVGWQJiqASzngpwF8AcDPicizIvJA8c2aQHEB17eaxGWWoi3o22ZuBsfHnfvEieRBTg5AEhXCparkg6r6WlVtq+rtqvqJMho2UWwBd2HBb2DPJbViC/pxPW5gkA93qURxbScRjYSpkjqwBdzz5/0G9lxSK7bSwle/OrmNPsu+tlocgCQqEAN3HSQFXJ+BPZfUim2Gpq03HczO9Jnsc/YsgzZRgRi468AWFPft81sO1XWiTtybQVrQd1lhEDBT6Rm0iQrFwF0HcUGx3TZlez7LoY6y03pa0I+eu9sFpqeHjz9+PP1aRDQaVc39ceDAASVPa2uqvZ6qiPna7aqakL370euV14a1teTjANVWa9Au2/FElArAujrGWNG4iRMjmp+f1/X19dzPO1GmpuyTWrJsupCXoAImnBMXMW3t9Uaf1Uk0oUTkgqrOuxzLVEldFbEiYB7iKmCCNxjubkNUCgbuusp7RcC8pJUFcncbosIxcNfVKAONRXLp8fvUfBORNwbuOqvj4kwuZYFVp3OIxhwDN/mJbjwcXc61DukcojHHwE3+gk8CqsC5c/VL5xCNuT1VN4AabnGRgZqoZOxxExE1DAM3EVHDMHATETUMAzcRUcMwcBMRNQwDNxFRwzBwExE1DAM3EVHDjE/g7vf9tvnK6zrLy+Vcl4hox3jMnOz3gQ9/GLh+3fy8sWF+BvKd1RfdRGBjAzhxYvD7YD3qvK9LRBRSnx73KD3mY8cGQTtw/bp5Pk9xmwhEcT1qIipYPXrccT1Zn57r5qbf81m5rjPN9aiJqED16HHH9WSTeq7R3nle0nr9rutM79tXXs6diCZOPQK3rYcafj4IhCLAoUOmV65qvtp0u+nXTjpvdP9El00EAOCFF4D7708+FxFRRvUI3Gkb4waplCBIu+xM324Dx4+b187MmMAsYr4PAmjaeaO9/rjtxPbuHb72jRvA1tbwuQ4eNNefmWFPnIiyU9XcHwcOHFAva2uqnY6qCZ3m0emY51VVe73dv7M9ej1VEfN1bc08pqeHj2u3ze9cziuS3G6XdiU9wvdJRBMLwLo6xli3g4B7AXwLwDMAPpp2vHfgVh0E0nDgDYi4Be2opMDc7WY/b9De6JtN1ke36//fi4jGik/gTk2ViEgLwMcB/CqAOwF8UETuzL3rv7hocsizsya3vbIySCOkDQrG7XPY7yfnvzc3zSBiknYbuHo1Pq2RVBo4PW1e42pzkykTInLmEl3eDuAZVf2uql4H8BkA9+XeknC+WSMDenGDgsEmtXH7HAbncpE02Li1ZYJq0J5Dh8xMSSC55O+d7wT2eFZasvabiBy5BO7XAfhe6Odnd57LV1JJYNyg4LlzJqBevDhc6+0yUQYArlzZfd5uN7mnrAqcPGneGJI+BTz22PCEoDSs/SYiRy6BW2KeGyrrEJEjIrIuIuuXL1/2b4ktcG1smF5usLP4zZvxwdrlXFGzs7vPu3ev+ZpEFTh8ODkNs73tdv1oW4iIHLgE7mcB3BH6+XYA348epKqnVHVeVef379/v35KkwHXixCBFMeq5AkFePDxRJikYh6UF5lbL7TzRthAROXAJ3F8C8EYReb2ITAP4AICHc29J2uSWhx4a7VzT0yYVEqRaTp0yz4fz6nnodMw5k3LyS0u70z7RHD0RURKX0hMACwC+DeA7AFbSjs9UDqiaXhcdV+9sKyNMKi8MuNaHuzyyXJ+IaAc8ygFF8+pphszPz+v6+nq2F+/ZY09F9HomHx2ILk4FmJ6uaw92aiqfnna0XUREnkTkgqrOuxxbjynvYUllfNFBR9/FqaLyGBBkfpqISla/wH333YN8cFQ00LosThUnGJB0HYy0ERm8UXACDRGVpF6BO0h9xKUv4nq2aYtTJV0jKWi327sHMuMWkgIG7eTqf0RUonoFbtvEmVYrPm8dVz2SlrpIukYQqM+cAZ5/flAz/vLL6W3nzjdEVJJ67IATsKU4bIOVQSBfWTGvnZ01QTvL5JybN+2Tb2Zn3dIqnP1IRCWoV487KcVhS0X4zKhMukbStRcW7Hl313MQEeWkXoE7aRJOXqkI3/RKvw+cPetWNriwMHr7iIhS1CtwB4tJ2eSRiohbsCqp7tt1wSoAOH9+9PYREaWo3wQcwF6qV8VEF59JOiLpi1QREcVo9gQcIFu1SFF88tbMcRNRCeoZuH3TGUWKexNpt82iVWGcQUlEJaln4Ab8q0WKbEf0TeTMGeD06Xq8sRDRxKlnjpuIaMI0P8ftIrwBQnQjXyKiMVavmZOuosu5BmuFAExXENHYa2aPe9TlXImIGqyZgTvrcq5ERGOgmYE7y3ojRERjopmBu04TdIiIStbMwF2nCTpERCVrZlUJYII0AzURTaBm9riJiCYYAzcRUcMwcBMRNQwDNxFRwzBwExE1TCGrA4rIZQAO26LvMgPg+dwbU3+TeN+858kwifcMZL/vnqrudzmwkMCdhYisuy5pOE4m8b55z5NhEu8ZKOe+mSohImoYBm4iooapU+A+VXUDKjKJ9817ngyTeM9ACfddmxw3ERG5qVOPm4iIHJQeuEXkXhH5log8IyIfjfn9T4nIZ3d+/6SIzJXdxrw53PPvisg3ReSrIvJvItKrop15S7vv0HHvFxEVkcZXILjcs4j8+s6/9zdE5K/LbmPeHP6+Z0XkURH58s7f+EIV7cyTiJwWkedE5OuW34uI/OXOf5Ovisjbcm2Aqpb2ANAC8B0AbwAwDeArAO6MHLMM4OTO9x8A8Nky21jRPf8ygM7O90tNv2fX+9457lYAnwfwBID5qttdwr/1GwF8GcDP7Pz8s1W3u4R7PgVgaef7OwFcrLrdOdz3LwJ4G4CvW36/AOCfAAiAuwA8mef1y+5xvx3AM6r6XVW9DuAzAO6LHHMfgLM73/8dgHeLiJTYxryl3rOqPqqqwSaaTwC4veQ2FsHl3xoA/gTAnwL4vzIbVxCXe/5NAB9X1R8CgKo+V3Ib8+Zyzwrgtp3vfxrA90tsXyFU9fMAriQcch+AT6nxBIDXiMhr87p+2YH7dQC+F/r52Z3nYo9R1RsAXgDQLaV1xXC557AHYN6pmy71vkXkrQDuUNVHymxYgVz+rd8E4E0i8riIPCEi95bWumK43PMfAjgoIs8COA/gt8tpWqV8/7/3UvZGCnE952hZi8sxTeJ8PyJyEMA8gF8qtEXlSLxvEZkC8OcAfqOsBpXA5d96D0y65F0wn6z+XUTeoqo/KrhtRXG55w8C+KSq/pmIvAPAuZ17vll88ypTaBwru8f9LIA7Qj/fjuGPTa8cIyJ7YD5aJX0kqTuXe4aIvAfACoD3qepPSmpbkdLu+1YAbwHwmIhchMkDPtzwAUrXv+9/VNUtVf1vAN+CCeRN5XLPDwD4GwBQ1S8AeBXMeh7jzOn/+6zKDtxfAvBGEXm9iEzDDD4+HDnmYQCHd75/P4DP6U62v6FS73knZfAQTNBues4zkHjfqvqCqs6o6pyqzsHk9t+nquvVNDcXLn/f/wAzGA0RmYFJnXy31Fbmy+WeLwF4NwCIyJthAvflUltZvocBfGinuuQuAC+o6g9yO3sFo7ELAL4NMxK9svPcH8P8TwuYf9S/BfAMgC8CeEPVI8gl3PO/AvhfAE/tPB6uus1l3Hfk2MfQ8KoSx39rAfAxAN8E8DUAH6i6zSXc850AHoepOHkKwK9U3eYc7vnTAH4AYAumd/0AgKMAjob+nT++89/ka3n/bXPmJBFRw3DmJBFRwzBwExE1DAM3EVHDMHATETUMAzcRUcMwcBMRNQwDNxFRwzBwExE1zP8DZYEdMV4SmugAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "({'spInd': 1,\n",
       "  'spVal': 0.39435,\n",
       "  'left': {'spInd': 1,\n",
       "   'spVal': 0.582002,\n",
       "   'left': {'spInd': 1,\n",
       "    'spVal': 0.797583,\n",
       "    'left': 3.9871632,\n",
       "    'right': 2.9836209534883724},\n",
       "   'right': 1.980035071428571},\n",
       "  'right': {'spInd': 1,\n",
       "   'spVal': 0.197834,\n",
       "   'left': 1.0289583666666666,\n",
       "   'right': -0.023838155555555553}},\n",
       " None)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt \n",
    "myDat1=loadDataSet('./input&code/Ch09/ex0.txt') \n",
    "myMat1=mat(myDat1) \n",
    "mM1=createTree(myMat1) \n",
    "plt.plot(myMat1[:,1],myMat1[:,2],'ro') \n",
    "mM1,plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 树剪枝\n",
    "一棵树如果节点过多，表明该模型可能对数据进行了 “过拟合”。\n",
    "\n",
    "通过降低决策树的复杂度来避免过拟合的过程称为 剪枝（pruning）。在函数 chooseBestSplit() 中提前终止条件，实际上是在进行一种所谓的 预剪枝（prepruning）操作。另一个形式的剪枝需要使用测试集和训练集，称作 后剪枝（postpruning）。\n",
    "\n",
    "### 预剪枝(prepruning)\n",
    "顾名思义，预剪枝就是及早的停止树增长，在构造决策树的同时进行剪枝。\n",
    "\n",
    "所有决策树的构建方法，都是在无法进一步降低熵的情况下才会停止创建分支的过程，为了避免过拟合，可以设定一个阈值，熵减小的数量小于这个阈值，即使还可以继续降低熵，也停止继续创建分支。但是这种方法实际中的效果并不好。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAD8CAYAAAB0IB+mAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3W1sJVd5B/D/Y69N5Q202euAIsB2QEFq4EOaWBGoFQWBINpKpEiAgkwaQlSDgSpqq0qJ/AHUaj80CCHRQsC0EWl8gaSVKCsaSmlKRVU1wF0B6RI1ZYH1EhKRzS4vQZuSze7TD3Nvdjyel3Nmzjlz5s7/J13Zvh7PnJm7+8yZ57yJqoKIiKbfTNsFICKiMBjwiYh6ggGfiKgnGPCJiHqCAZ+IqCcY8ImIeoIBn4ioJxjwiYh6ggGfiKgn9rVdgLTFxUVdWVlpuxhERJ1y5MiRJ1T1kqrtogr4KysrGI1GbReDiKhTRGTHZDumdIiIeoIBn4ioJxjwiYh6ggGfiKgnGPCJiHqCAZ+oi4ZDYGUFmJlJvg6HbZeIOiCqbplEZGA4BNbXgTNnkp93dpKfAWBtrb1yUfRYwyfqms3NC8F+4syZ5H2iEgz4RF1z4oTd+0RjDPhEXbO0ZPc+0RgDPlHXHDoELCzsfm9hIXmfqAQDPlHXrK0BW1vA8jIgknzd2mKDLVViLx2iLlpbY4Ana6zhExH1BAM+EVFPMOATEfUEAz4RUU8w4BMR9QQDPhFRTzDgExH1BAM+EVFPGAd8EblTRB4XkaOp9z4oIj8WkW+PXwdTv7tNRI6JyMMi8kbXBSciIjs2NfxPA7g25/2PqOqV49d9ACAiVwC4HsDLx3/zcRGZbVpYIiKqzzjgq+rXAJw23Pw6AJ9T1V+p6g8BHANwTY3yERGRIy5y+O8XkQfHKZ+Lx++9EMCPUts8Mn6PiIha0jTg3wHgpQCuBPAYgA+P35ecbTVvByKyLiIjERmdPHmyYXGIiKhIo4Cvqj9R1XOqeh7Ap3AhbfMIgBenNn0RgEcL9rGlqququnrJJZc0KQ4REZVoFPBF5NLUj28GMOnBcxjA9SLyHBG5DMDlAL7R5FhERNSM8Xz4IvJZAK8BsCgijwD4AIDXiMiVSNI1xwG8GwBU9bsici+AhwA8A+B9qnrObdGJiMiGqOam1luxurqqo9Go7WIQEXWKiBxR1dWq7TjSlmhaDYfAygowM5N8HQ7bLhG1jEscEk2j4RBYXwfOnEl+3tlJfga4NGKPsYZPNI02Ny8E+4kzZ5L3qbcY8IlCCZliOXHC7n3qBQZ8ohAmKZadHUD1QorFV9BfWrJ7n3qBAZ8ohNAplkOHgIWF3e8tLCTvN8GG4HoiuW4M+EQhhE6xrK0BW1vA8jIgknzd2mrWYBv6KaWOSALrLhFdN/bDJwphZSX5j561vAwcPx66NPXEfg7ZnklA8lTT9EbXVIDrxn74RDHxlWIJKfaG4Fh7JkV03RjwiULwkWIJLfaG4IgC67OGwyS9lKeF68aAT+RDXi55bS15hD9/PvlqE+xjyE3H/pQS2w1pkmI6lzONWFvXTVWjeV199dVK1Hnb26oLC6pJE13yWlhI3o9hf01sb6suL6uKJF/bKEORmK6TanJ90mWZvGZnnZcJwEgNYiwbbYlcc91IF3tjaUyGwyRnf+JEUrM/dKi9tNnMTBLis0SSpzyHTBttGfCJXHP9Hz1g4CCHAt6o2UuHqC0ucsnpnH1EjX5kIcI2DwZ8ItcOHkxq32k2/9GzA3ViavQjcxH2zGLAJ3JpOATuumt3CkYEuPFG8//oef3JAWB2NprAQYYmPbPuvjv5+YYbOLUC0dTIC9aqwH33me+jqN/4+fP1unQWiaGrZx9ENLUCAz6RS1WDf0yCbIj+5DZBiDeGZmIaAWzSdzPUi/3wqfOK+l5P+qyb9BMP0Z+8rJyhyzItisYoiORfaxFnh4ZhP/zWg3z6xYBPnVcWIE2D7GQ/Pgc45ZVj8kqzKbMrVefexuAvkzK5+NxrYsAnaktbNT2bQDg7m1+W2dnd2wWone45h7InijaeOEyO6eLJrgEGfKJQTAOtz5qebVCJtYZfdbw2njhMjll1Y/T8VMKATxSCTaD1WdOzTRcV1fDzcvjz87u3mZ9vVuay4FcVOE2eOFwHV5NjDgbhb0QppgGfvXSImrDpgVE0EAdo3gvGdGrgOjM4qpb/bKOqd1BVD6Wq3/voAmlyzCef3Pv7ubn4BseZ3BVCvVjDp85pmuN2Ves3reHbzuDoOoVStb+q67Gxsfeap3/vI+VTVaaiYw4G9Y9pCUzpEAXQNMC4ClAmN47t7fxj5d2gynqX2NzQspqkZPLOUSS5Cdjsv44maSjT/TTAgE8UQtMaussAVRZM8spZdIOp2jbvhhSi4drkb9vo+hrBmAYGfKJQmgSOUL1Oymrrk6BTVasve3Jw2XDdpFtrG4PbTPfl8bNmwCfqgu1t1bm53QFgbs59v/KiYAlcCPZVtfpJcNrY2B2QbXuo2D6J2A5gMrkBu9yX6XYexzQw4BN1gY9uj3nq9m/Pbmt6Y6gbyEINYCq7AU6C9saG2xQMa/gM+NRzoVI6VcGyLACmty2qzbs6h6qbR930WfbvbM6j7AZkgzl8BnzqOVeP+SaBMLtNOjVTNBArHdw2NswDYp1Atr1dfD1cd6ucn9+bSrN9VZ1j3mfCXjoM+NRjLmr4dWqOJqmZ7Bw2ZU8Bg0HzQFZ0LUSaBcayfvKTMjep6ecJPOcPAz5RF7gIDHVuGmUDsPKCdlWOP90Xvq6ywOtjv+mnKJM2jKp9pAWe88c04HNqBaI2uVj31HRaBZPfFa2qVbYvIFnWsenCKEVTGCwv+9lv+v28Bceb7LvOZxKAccAXkTtF5HEROZp674CIfEVEvjf+evH4fRGRj4rIMRF5UESu8lF4ola5Wglqsu5p3eUL66yQZfs3VattNVnBaXIdd3b2/s7FfDR5wTw7b1D6xgvsXYR+bg6Yny/fR1rR9dq/37zcPpg8BiRPDHg1gKsAHE29dzuAW8ff3wrgL8ffHwTwJQAC4JUAvm5yDKZ0qDPamJfdZVls/8Yk5193dHDZfrNdVF310qn6u3S//0mD9mCQvEz65Jf1AnKR/sqAjxw+gJVMwH8YwKXj7y8F8PD4+08CeHvedmUvBnzqjBA5WpsgVScQNgmCrs7dtP//5Pghb7K+GsMn19thT51QAf9nmd//dPz1iwB+J/X+/QBWq/bPgE+d4XvCrJieIHyWzaSHzOSaBm4IddoYXvZy8Lm2HfD/KSfgX12wz3UAIwCjpaWlRidNFIzpdAImMzzmCR3cbPmeeCzvnEMvt2gyGjd73nW7eDb8XJnSIfIlbzoEIH8OnLp9y0MHt7ZUpUDqznVvOxAtLz9fZyI51907DYUK+B/KNNrePv7+9zKNtt8w2T8DPnVC2UCerLIaX53UQCw1fJeqAm96OxczYZpOEbF/v9lo3PRnUnYDm51VvegiL5+r84AP4LMAHgNwFsAjAG4GMBina743/npgvK0A+BiA7wP4b5P8vTLgU1fY1L7LanxltbqioJWdqTIv2HkYum/NVzmazoRpM/kbkDzJTW5App9j3dlAG/BSw/f9YsCnTiiqHebV8JvMD5M3901VzdW2q6WrqX+z27fZ4Fx2Q66TcjGZUdRnF1EDDPhEvpgG/LI8sI91a8umS7BNe9huZ1NOG3WCY9nx6zSqpmfqNG1vCIwBn8iXuisvTf6ubq2u6rhlwcy0cTEblOsEb5czgNZ5Uij7uyY1/Mm+XY9FcIABn8gXkyDoo9G1bg0/79imQblO8HZ17k32U9QQPBjk97Davz95mdbaI+tFZRrwOXkakS2TuVl8TJ5VddyqCcDSxzadM6fO3Dom18dEk2s4mZ/o7ruBp54CTp1KQvLk62BwYbK67W3gl79MXtvbZhPZ1Z1zqG0md4VQL9bwqTOqcsu+ulUWHdckXVHVfdDlYt8uGiZdXMOm+yi73i4XQW94rcCUDlGLQvZUMelqWBTMffTSccXFNWySejHpz9/0ujj6d8KAT9S2UIGyrHdO2/3xm2p6DZvU8F11w/RVvhTTgC/JtnFYXV3V0WjUdjGI3BsOk/niT5xI8ryHDtnPe19kZiYJE1kiyRz7fTYcAuvryXz9EwsLZovMFF1X2/3UOYblZyciR1R1tfJwVoUjInuToLOzk/zn3tkBbroJWFzMXzzFdmGVoobCAweSY4gkr8XF5qtSdU2dFcUm17+qMmy66EvZ5xm68dfkMSDUiykdmko2k3C5moN9bk513769x8mb4C2kWKZ+KGI79UJVW4BJOwBz+ERTxHR05/Jy/ZxuNpCWTQ7W1gRsbU+5YMJ2YFbVtTT5PAP20mEOn8i3ovVasybrqOb9n7TNx5fln9vK7Rddh+XlpM98DMqu28KCfVtAoPYV5vCJYlE1IGpiacldTrfOAua++RiM5lrRtZnk/m3aAsr219JnwIBP5Fu24XAwAObnd28zGYlqO0q1qEHw0KG9xwCAuTn7Ea+u1Al+Ng3Yto3decqu/2T07vnzyVeT3jmuRh27YpL3CfViDp96o2rOdNMBUTYLfQwG7TfY2k7fbLp93rbpuezbnL44QEM1mMMnmnJdyIln2YxHsDk/k3YSF/3mI8UcPtG0iy0nbpJSsUmL2JyfyTmb9pt3yUWaySEGfKKuiqlBMG9w2fp6swBnc36m5xzyZujjmjTEgE/UVTE1CG5u7u6yCDSvUducn01PqFB8XJOGGPCJuqrOtAG++EgvlZ1fNlUC7O0JNTe3e3+hb4axpdwANtoSkQMhG5BNJ0TzOWGdicXFZMGVLA/XhI22RBROyPSSaaqkTr95V4ZD4Mkn977f5jgIMOATkQsh00sRpkr22NwEnn567/vPe16r3UIZ8InIjVA16ph6J6Wl2xWKxgScPh20SFkM+ETULTH1TprIdsEs0vJNiQGfiMLI9qx573vrDUqKqXfSRF67QlbbNyUw4BNRCHmDkO64w3xQUl43zLYaZPOUtR/EclMCu2USUQimawLkdVlssi5tKC3Pa8RumUQUD9MeNHnb2Y5YbWP+mhjbFXIw4BORf6aNlXnblXXDzGsXaGP+mhjbFXIwpUNE/uWlZbKK0jRF6ZLBAHjqqd37FMnvJRPzlNEOMKVDRPHIqwFvbJjViIvSJcDeG0hRBTamQVkt2td2AYioJ9bW6qU4Jn+TnRfnhhvM99H2oKxIsIZPRPHLG8VbFMRFdv8cYeNpWxjwiaibilI973lP9I2nbWFKh4i6qSjVw+BeiAGfiLqrbrtATzkJ+CJyHMCTAM4BeEZVV0XkAIB7AKwAOA7gbar6UxfHIyIiey5z+K9V1StTfUFvBXC/ql4O4P7xz0RE1BKfjbbXAbhr/P1dAH7f47GIiKiCq4CvAP5FRI6IyPr4vReo6mMAMP76/Lw/FJF1ERmJyOjkyZOOikNERFmuGm1/W1UfFZHnA/iKiPyP6R+q6haALSCZWsFReYiIKMNJDV9VHx1/fRzA5wFcA+AnInIpAIy/Pu7iWEREVE/jgC8i+0XkuZPvAbwBwFEAhwHcON7sRgBfaHosokJtTIlL1DEuUjovAPB5SYYz7wPwGVX9ZxH5JoB7ReRmACcAvNXBsYj2ys7EOJkSF2AfbaIUTo9M3dfyakNEbeP0yNQfZQtkENGzGPDJj5A59aJZEzklLtEuDPg22DBoZpJTD7XMXEfWEyVqGwO+qdBBrMtsF51uqiPriRK1jQHfVOggFhPbJ5s2cup5C2QQ0S4M+Kb62jBY58mGOXWiKDHgm+prEKvzZMOcOlGUGPBN9TWI1XmyYU6dKEoM+Kb6GsTqPtkwp04UHQZ8G30MYn14smF3W+oJBnwTfQ4I0/5kw+621COcS6dKdmIuIKnhTlPQ6zPOw0NTgHPpuNLn/vd9UNYo3ecnO5pKDPhV+tr/vi+KGp8PHGCqh6YOA36Vvva/j4XvWnZRozTAJzuaOgz4VfrQSyVWIRpUixqlT5/O355PdtRhDPhVmvZSGQ6BxcXkb0WS75kWMBOq/SSvuy2f7GgKMeCbqNv/fjgEbroJOHXqwnunTgHveheDvomi2nRerxrX+GRHU4gB36fNTeDs2b3vP/00c8EmimrTIv5vmNM+/oB6iQHfp7J8b4hccAzdCpuU4dChJNhmqZrfMJscv48jq2m6qWo0r6uvvlqnyvKyahKe9r6Wl+vtc3s7+VuR5Ov2dvF2Cwu7j7mwULy9Dy7KUHT9RMIcn6gDAIzUIMa2HuTTr6kL+NvbqnNze4PV/Hy9oGMTwIpuNnVvNHW4KEOTfZj8rekNlChiDPix2N5WHQwuBJvBoH5QsQl+IvnbmtSMXXFRhia19Krj8wmApoRpwGcO37e1NeCJJy6ElCeeqJ8Lthn1e+BA/rYhuxW66NpYp/F0krfXgnmiJsfntBnUMwz4rvlsKDUNoMMh8Itf7N1ufj5st8ImXRvT13FzM/kbk8bT9GCtPOnjc9oM6huTx4BQr86ndHynCEz3X5T6GQzclMO2zLY58ibXsaqhPL2PGNo5iBwAc/glfDXUhQggJmWPIX/fRJPraHPutjcWNvBSpBjwi/ishccSaLtec21yHW3PvUvdXIkKmAb87ufwbXPmPhvqYpl/pevTAjS5jqbnPvl3c8MNyc93313ePsAGXpoGJneFUC/rGn6dWpfPWnhMtcBQ6Qcfx2l6HavKFNu/G6KG0IuUTp3Uhe90h0mwyf6+q7lhnzc4n9ckxn83RA30I+DXqXWVBSnfgTfv2HNzycjbGJ4KbHU1CLr+d0PUMtOA3+0cfp1cb9FAHsD/Yht5eeCzZ5PZM9PayA3XGT/gqx+770nfTP7dZNcxuOUW4MYbOXsmdZvJXSHUK0gOP/236dp8evoDX7XVoppl27nhutfRRw0/RE266hiu50Ai8gy9SOmouhvYEyLwlg0KajMtUjdwmwRn28+nbNCYq3Rb1fxGPmY5JfKoPwG/DtvA6yq3HyKHX6esZeff5Hgue8NkX3WvkUmZysrAXjkUoWgCPoBrATwM4BiAW8u2DRbwbYLKxobbFENegNzYUJ2dTfY9O5v8XLRt1b7zyrqxUb6fybGzr9nZeuc44bI3jKvatkmZWMOnjoki4AOYBfB9AC8BMA/gOwCuKNq+9Rp+XtogRDfOoiBte6MpKmv2BpfdT5MafpmyG6vNU4HL2rZJDx3m8KljYgn4rwLw5dTPtwG4rWj7oHPpmAZT0y58dfvXFwXpolp32eIdpjVj0xpt3k3N5qmjqCG8KpCaNqhPymgThE3P1eU6BkSexRLw3wLgb1I/3wDgr4u2DzpbZjaoFKU9TFdNqpubt+m5k77R5B2zbi8g0xugzY1ye3vv+Ze9ymbyrKr1247CZX96mjKxBPy35gT8v8pssw5gBGC0tLTk9aIUqhqMVRUgmuSd69bwTWvPpuVo8jSS9yRg+8QBVH9GrnLrXR3ZTFQgloAfZ0onqyqQVQWIJv3r6+Twt7ebBfu6NVqbEaq2Ty5VAb9OGbIY6GlKxRLw9wH4AYDLUo22Ly/avrWA33RirKY9S4oCUdH7dWrP6VfdQOeihj8zk/++6eIsPscMEHVUFAE/KQcOAvjfcW+dzbJto63hV3HZv96kFlqn9mx7TqbnWZbDL3pyyfaAmZvzn4Pv6rw/RAaiCfg2L28BvyqIuqj91e2lU6ccdWv4Lmq0Nudk++Riuv86qRlOb0xTjAF/wqYHStv5XZsug6Z91dP7sKlFt3EtfKZdyq5tDJ89UQMM+BMuH+V9Bwbb9VgnZSnq0VMnaLaZ6/aZdnE5wI0oMgz4E64e5UMEwroBzySnbxo028x1+0675N2wmdunKWAa8Ls9H74JV+vMhljTtM5atMNhMm98FdM56n3NcW/C95rAa2vJurXnz19Yv7bN8yUKbPoDvkkQNVlwI0RgKFqcpWiRjeEwWaTl3LnqfZsGTRdBt+4CJm0svh7LwvNEIZg8BoR6tdJLx3SGyRALpFSVNcu0t46LHP7kegAX2gx89HgK3YDK/vk0BcAcviHTGSbn5/f2H8+uktQ0UNkGnzqzUZqWIzvPUFGvINNpJmLOibOXDnUcA74pm0FMRasuuaol2gbLUMG16kkifTxfNyEiKmQa8CXZNg6rq6s6Go3CHnRlJVmw3IRI0uBnuo/l5aRx0NTMTBIaTY87yeGnG5MXFtwvrl1UrrTJ74uuhcjuffgoJ1FPicgRVV2t2m76G22r5DUUiuRvW9SQ56pB17YB0baRt66qBkyRCw2zRdcze8M4cwa45ZZ6jbtEVI/JY0CoV2tz6ZjkrMtSNK5SK200IJpOZVA1sje7PkB6n6Yps1CNpczZ05QBc/gN2c4Z4ypQhwxGtpOhlQXvssFRTWcTrXNetr2yGPSpwxjwQ2tz/pm6x63zZFLnb2zm/mk6qrYqoHexFxFRBQb8PmhaW60zlUHdY25sXOi/Pzurun+/n8BbFdDLehExxUMdZRrw2Whro+4IUl+aTvdQZ5RpnYbi4RC4664LI4LPnQPOngXm5nZv52JUbVUDetm5qSY9jNbX2/9siXwwuSuEekVdw48x99t0srFQ51RU6y4a1+DjWJMavml6iSke6hCwhu9YiMnTbJ8gms4DE6pbZ1Gt+/TpvZOZ2cpes4MHy+fjyZ6zbZmJuszkrhDqFXUNP8TUvba17dieOooakH01lJrOg1RnPiLW8KlDwEZbx1wEhrIeNXX3H0uf8rKbT90bU9W51e0x1GTMBVGEGPBdczELZNnfd33NVZPcuc2NyeR6214zF08ERBFiwPfBZ593H6mFkLV/k+DrYurn9PWIdbI5osAY8GNTFRBd5+ND5/fr9I7Jlid9Q8jbV94NxMV00l15iiIqwIAfG5PapcsaeejabNMRrnW7S7p+aiDqIAb82ISucbdRmy0LvlXlMZlvp+n1KrqpDAbM21OnmQZ89sMPJVSf94k21mrNWyTctDxl/d5dXa/JZzAY7H7/1CmOrqVeYMAPqSwgutbGguBNylN0Q1hednu91taAiy7a+77rQXREEWLAn1ahnyialifkDcrVgjVEHcOAH0Jbk66FfKJoWp6QN6g20l1EEWDA922y7uzOTtJEyNkYi2+AoW5QsaW7iAJhwPctxKRrXRLDDTC2dBdRIJL06InD6uqqjkajtovh1sxMEtiyRJKabN+srCRBPmt5OanVE5E1ETmiqqtV27GG7xvzxbuxwZSoNQz4vjFfvBtvgEStYcD3jfni3XgDJGrNvrYL0Atra/0N8FmT67C5maRxlpaSYM/rQ+QdAz6FxxsgUSsapXRE5IMi8mMR+fb4dTD1u9tE5JiIPCwib2xeVCIiasJFDv8jqnrl+HUfAIjIFQCuB/ByANcC+LiIzDo4FsWorZHERGTFV6PtdQA+p6q/UtUfAjgG4BpPx6I2xTCQioiMuAj47xeRB0XkThG5ePzeCwH8KLXNI+P3aNpwJDFRZ1QGfBH5VxE5mvO6DsAdAF4K4EoAjwH48OTPcnaVO6RXRNZFZCQio5MnT9Y8DWoNB1IRdUZlLx1Vfb3JjkTkUwC+OP7xEQAvTv36RQAeLdj/FoAtIJlaweRYFJGlpfypEjiQiig6TXvpXJr68c0Ajo6/PwzgehF5johcBuByAN9ociyKFAdSEXVG0374t4vIlUjSNccBvBsAVPW7InIvgIcAPAPgfap6ruGxKEYcSEXUGZwtk4io4zhbJhER7cKAT0TUEwz4REQ9wYBPRNQTDPhERD0RVS8dETkJIGcUj5FFAE84LE5X8Lz7hefdL6bnvayql1RtFFXAb0JERibdkqYNz7tfeN794vq8mdIhIuoJBnwiop6YpoC/1XYBWsLz7heed784Pe+pyeETEVG5aarhExFRic4FfBG5drww+jERuTXn988RkXvGv/+6iKyEL6V7Buf9JyLy0Hj1sftFZLmNcrpWdd6p7d4iIioiU9GTw+S8ReRt48/8uyLymdBl9MHg3/mSiHxVRL41/rd+sI1yujZeMfBxETla8HsRkY+Or8uDInJVrQOpamdeAGYBfB/ASwDMA/gOgCsy27wXwCfG318P4J62yx3ovF8LYGH8/UZfznu83XMBfA3AAwBW2y53oM/7cgDfAnDx+Ofnt13uQOe9BWBj/P0VAI63XW5H5/5qAFcBOFrw+4MAvoRkNcFXAvh6neN0rYZ/DYBjqvoDVX0awOeQLJiedh2Au8bf/wOA14lI3pKLXVJ53qr6VVWdLC77AJJVxrrO5PMGgL8AcDuA/wtZOI9MzvsPAXxMVX8KAKr6eOAy+mBy3grgeePvfx0FK+l1jap+DcDpkk2uA/B3mngAwG9kFqAy0rWAb7I4+rPbqOozAH4OYBCkdP7YLgp/M5LaQNdVnreI/BaAF6vqFzE9TD7vlwF4mYj8p4g8ICLXBiudPybn/UEA7xCRRwDcB+CPwhStdbYxIFfTFa9CM1kc3XgB9Q6xWRT+HQBWAfyu1xKFUXreIjID4CMA3hmqQIGYfN77kKR1XoPkae4/ROQVqvozz2XzyeS83w7g06r6YRF5FYC7x+d93n/xWuUkrnWthm+yOPqz24jIPiSPfWWPSl1gtCi8iLwewCaAN6nqrwKVzaeq834ugFcA+HcROY4kt3l4ChpuTf+df0FVz6rqDwE8jOQG0GUm530zgHsBQFX/C8CvIZlvZtoZxYAqXQv43wRwuYhcJiLzSBplD2e2OQzgxvH3bwHwbzpu9eiwyvMepzY+iSTYT0M+F6g4b1X9uaouquqKqq4gabt4k6p2fZ1Mk3/n/4ikoR4isogkxfODoKV0z+S8TwB4HQCIyG8iCfgng5ayHYcB/MG4t84rAfxcVR+z3UmnUjqq+oyIvB/Al5G06N+pyYLpfw5gpKqHAfwtkse8Y0hq9te3V2I3DM/7QwAuAvD34zbqE6r6ptYK7YDheU8dw/P+MoA3iMhDAM4B+DNVPdVeqZszPO8/BfApEfljJCmNd05BhQ4i8lkk6bnFcfvEBwDMAYCqfgJJe8VBAMcAnAFwU63jTMG1IiIiA11L6RARUU0M+ET6idkOAAAAKUlEQVREPcGAT0TUEwz4REQ9wYBPRNQTDPhERD3BgE9E1BMM+EREPfH/sMIH6Ga+FgAAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "({'spInd': 0,\n",
       "  'spVal': 0.499171,\n",
       "  'left': {'spInd': 0,\n",
       "   'spVal': 0.729397,\n",
       "   'left': {'spInd': 0,\n",
       "    'spVal': 0.952833,\n",
       "    'left': {'spInd': 0,\n",
       "     'spVal': 0.965969,\n",
       "     'left': {'spInd': 0,\n",
       "      'spVal': 0.968621,\n",
       "      'left': 86.399637,\n",
       "      'right': 98.648346},\n",
       "     'right': {'spInd': 0,\n",
       "      'spVal': 0.956951,\n",
       "      'left': {'spInd': 0,\n",
       "       'spVal': 0.958512,\n",
       "       'left': {'spInd': 0,\n",
       "        'spVal': 0.960398,\n",
       "        'left': 112.386764,\n",
       "        'right': 123.559747},\n",
       "       'right': 135.837013},\n",
       "      'right': {'spInd': 0,\n",
       "       'spVal': 0.953902,\n",
       "       'left': {'spInd': 0,\n",
       "        'spVal': 0.954711,\n",
       "        'left': 82.016541,\n",
       "        'right': 100.935789},\n",
       "       'right': 130.92648}}},\n",
       "    'right': {'spInd': 0,\n",
       "     'spVal': 0.759504,\n",
       "     'left': {'spInd': 0,\n",
       "      'spVal': 0.763328,\n",
       "      'left': {'spInd': 0,\n",
       "       'spVal': 0.769043,\n",
       "       'left': {'spInd': 0,\n",
       "        'spVal': 0.790312,\n",
       "        'left': {'spInd': 0,\n",
       "         'spVal': 0.806158,\n",
       "         'left': {'spInd': 0,\n",
       "          'spVal': 0.815215,\n",
       "          'left': {'spInd': 0,\n",
       "           'spVal': 0.833026,\n",
       "           'left': {'spInd': 0,\n",
       "            'spVal': 0.841547,\n",
       "            'left': {'spInd': 0,\n",
       "             'spVal': 0.841625,\n",
       "             'left': {'spInd': 0,\n",
       "              'spVal': 0.944221,\n",
       "              'left': {'spInd': 0,\n",
       "               'spVal': 0.948822,\n",
       "               'left': {'spInd': 0,\n",
       "                'spVal': 0.949198,\n",
       "                'left': {'spInd': 0,\n",
       "                 'spVal': 0.952377,\n",
       "                 'left': 100.649591,\n",
       "                 'right': 73.520802},\n",
       "                'right': 105.752508},\n",
       "               'right': 69.318649},\n",
       "              'right': {'spInd': 0,\n",
       "               'spVal': 0.85497,\n",
       "               'left': {'spInd': 0,\n",
       "                'spVal': 0.936524,\n",
       "                'left': {'spInd': 0,\n",
       "                 'spVal': 0.937766,\n",
       "                 'left': 100.120253,\n",
       "                 'right': 119.949824},\n",
       "                'right': {'spInd': 0,\n",
       "                 'spVal': 0.934853,\n",
       "                 'left': 65.548418,\n",
       "                 'right': {'spInd': 0,\n",
       "                  'spVal': 0.925782,\n",
       "                  'left': 115.753994,\n",
       "                  'right': {'spInd': 0,\n",
       "                   'spVal': 0.910975,\n",
       "                   'left': {'spInd': 0,\n",
       "                    'spVal': 0.912161,\n",
       "                    'left': {'spInd': 0,\n",
       "                     'spVal': 0.915263,\n",
       "                     'left': 92.074619,\n",
       "                     'right': 96.71761},\n",
       "                    'right': 85.005351},\n",
       "                   'right': {'spInd': 0,\n",
       "                    'spVal': 0.901444,\n",
       "                    'left': {'spInd': 0,\n",
       "                     'spVal': 0.908629,\n",
       "                     'left': 106.814667,\n",
       "                     'right': 118.513475},\n",
       "                    'right': {'spInd': 0,\n",
       "                     'spVal': 0.901421,\n",
       "                     'left': 87.300625,\n",
       "                     'right': {'spInd': 0,\n",
       "                      'spVal': 0.892999,\n",
       "                      'left': {'spInd': 0,\n",
       "                       'spVal': 0.900699,\n",
       "                       'left': 100.133819,\n",
       "                       'right': {'spInd': 0,\n",
       "                        'spVal': 0.896683,\n",
       "                        'left': 109.188248,\n",
       "                        'right': 107.00162}},\n",
       "                      'right': {'spInd': 0,\n",
       "                       'spVal': 0.888426,\n",
       "                       'left': 82.436686,\n",
       "                       'right': {'spInd': 0,\n",
       "                        'spVal': 0.872199,\n",
       "                        'left': {'spInd': 0,\n",
       "                         'spVal': 0.883615,\n",
       "                         'left': {'spInd': 0,\n",
       "                          'spVal': 0.885676,\n",
       "                          'left': 94.896354,\n",
       "                          'right': 108.045948},\n",
       "                         'right': {'spInd': 0,\n",
       "                          'spVal': 0.872883,\n",
       "                          'left': 95.348184,\n",
       "                          'right': 95.887712}},\n",
       "                        'right': {'spInd': 0,\n",
       "                         'spVal': 0.866451,\n",
       "                         'left': 111.552716,\n",
       "                         'right': {'spInd': 0,\n",
       "                          'spVal': 0.856421,\n",
       "                          'left': 94.402102,\n",
       "                          'right': 107.166848}}}}}}}}}}},\n",
       "               'right': {'spInd': 0,\n",
       "                'spVal': 0.84294,\n",
       "                'left': {'spInd': 0,\n",
       "                 'spVal': 0.847219,\n",
       "                 'left': 89.20993,\n",
       "                 'right': 76.240984},\n",
       "                'right': 95.893131}}},\n",
       "             'right': 60.552308},\n",
       "            'right': {'spInd': 0,\n",
       "             'spVal': 0.838587,\n",
       "             'left': 115.669032,\n",
       "             'right': 134.089674}},\n",
       "           'right': {'spInd': 0,\n",
       "            'spVal': 0.823848,\n",
       "            'left': 76.723835,\n",
       "            'right': {'spInd': 0,\n",
       "             'spVal': 0.819722,\n",
       "             'left': 59.342323,\n",
       "             'right': 70.054508}}},\n",
       "          'right': {'spInd': 0,\n",
       "           'spVal': 0.811602,\n",
       "           'left': 118.319942,\n",
       "           'right': {'spInd': 0,\n",
       "            'spVal': 0.811363,\n",
       "            'left': 99.841379,\n",
       "            'right': 112.981216}}},\n",
       "         'right': {'spInd': 0,\n",
       "          'spVal': 0.799873,\n",
       "          'left': 62.877698,\n",
       "          'right': {'spInd': 0,\n",
       "           'spVal': 0.798198,\n",
       "           'left': 91.368473,\n",
       "           'right': 76.853728}}},\n",
       "        'right': {'spInd': 0,\n",
       "         'spVal': 0.786865,\n",
       "         'left': {'spInd': 0,\n",
       "          'spVal': 0.787755,\n",
       "          'left': 110.15973,\n",
       "          'right': 118.642009},\n",
       "         'right': {'spInd': 0,\n",
       "          'spVal': 0.785574,\n",
       "          'left': 100.598825,\n",
       "          'right': {'spInd': 0,\n",
       "           'spVal': 0.777582,\n",
       "           'left': 107.024467,\n",
       "           'right': 100.838446}}}},\n",
       "       'right': 64.041941},\n",
       "      'right': 115.199195},\n",
       "     'right': {'spInd': 0,\n",
       "      'spVal': 0.740859,\n",
       "      'left': {'spInd': 0,\n",
       "       'spVal': 0.757527,\n",
       "       'left': 81.106762,\n",
       "       'right': 63.549854},\n",
       "      'right': {'spInd': 0,\n",
       "       'spVal': 0.731636,\n",
       "       'left': 93.773929,\n",
       "       'right': 73.912028}}}},\n",
       "   'right': {'spInd': 0,\n",
       "    'spVal': 0.640515,\n",
       "    'left': {'spInd': 0,\n",
       "     'spVal': 0.642373,\n",
       "     'left': {'spInd': 0,\n",
       "      'spVal': 0.642707,\n",
       "      'left': {'spInd': 0,\n",
       "       'spVal': 0.665329,\n",
       "       'left': {'spInd': 0,\n",
       "        'spVal': 0.706961,\n",
       "        'left': {'spInd': 0,\n",
       "         'spVal': 0.70889,\n",
       "         'left': {'spInd': 0,\n",
       "          'spVal': 0.716211,\n",
       "          'left': 110.90283,\n",
       "          'right': {'spInd': 0,\n",
       "           'spVal': 0.710234,\n",
       "           'left': 103.345308,\n",
       "           'right': 108.553919}},\n",
       "         'right': 135.416767},\n",
       "        'right': {'spInd': 0,\n",
       "         'spVal': 0.698472,\n",
       "         'left': {'spInd': 0,\n",
       "          'spVal': 0.69892,\n",
       "          'left': {'spInd': 0,\n",
       "           'spVal': 0.699873,\n",
       "           'left': {'spInd': 0,\n",
       "            'spVal': 0.70639,\n",
       "            'left': 106.180427,\n",
       "            'right': 105.062147},\n",
       "           'right': 115.586605},\n",
       "          'right': 92.470636},\n",
       "         'right': {'spInd': 0,\n",
       "          'spVal': 0.689099,\n",
       "          'left': 120.521925,\n",
       "          'right': {'spInd': 0,\n",
       "           'spVal': 0.666452,\n",
       "           'left': {'spInd': 0,\n",
       "            'spVal': 0.667851,\n",
       "            'left': {'spInd': 0,\n",
       "             'spVal': 0.680486,\n",
       "             'left': 112.378209,\n",
       "             'right': 110.367074},\n",
       "            'right': 92.449664},\n",
       "           'right': {'spInd': 0,\n",
       "            'spVal': 0.665652,\n",
       "            'left': 120.014736,\n",
       "            'right': 105.547997}}}}},\n",
       "       'right': {'spInd': 0,\n",
       "        'spVal': 0.661073,\n",
       "        'left': 121.980607,\n",
       "        'right': {'spInd': 0,\n",
       "         'spVal': 0.652462,\n",
       "         'left': 115.687524,\n",
       "         'right': 112.715799}}},\n",
       "      'right': 82.500766},\n",
       "     'right': 140.613941},\n",
       "    'right': {'spInd': 0,\n",
       "     'spVal': 0.613004,\n",
       "     'left': {'spInd': 0,\n",
       "      'spVal': 0.623909,\n",
       "      'left': {'spInd': 0,\n",
       "       'spVal': 0.628061,\n",
       "       'left': {'spInd': 0,\n",
       "        'spVal': 0.637999,\n",
       "        'left': 82.713621,\n",
       "        'right': {'spInd': 0,\n",
       "         'spVal': 0.632691,\n",
       "         'left': 91.656617,\n",
       "         'right': 93.645293}},\n",
       "       'right': {'spInd': 0,\n",
       "        'spVal': 0.624827,\n",
       "        'left': 117.628346,\n",
       "        'right': 105.970743}},\n",
       "      'right': {'spInd': 0,\n",
       "       'spVal': 0.618868,\n",
       "       'left': 87.181863,\n",
       "       'right': 76.917665}},\n",
       "     'right': {'spInd': 0,\n",
       "      'spVal': 0.606417,\n",
       "      'left': 168.180746,\n",
       "      'right': {'spInd': 0,\n",
       "       'spVal': 0.513332,\n",
       "       'left': {'spInd': 0,\n",
       "        'spVal': 0.533511,\n",
       "        'left': {'spInd': 0,\n",
       "         'spVal': 0.548539,\n",
       "         'left': {'spInd': 0,\n",
       "          'spVal': 0.553797,\n",
       "          'left': {'spInd': 0,\n",
       "           'spVal': 0.560301,\n",
       "           'left': {'spInd': 0,\n",
       "            'spVal': 0.599142,\n",
       "            'left': 93.521396,\n",
       "            'right': {'spInd': 0,\n",
       "             'spVal': 0.589806,\n",
       "             'left': 130.378529,\n",
       "             'right': {'spInd': 0,\n",
       "              'spVal': 0.582311,\n",
       "              'left': {'spInd': 0,\n",
       "               'spVal': 0.585413,\n",
       "               'left': 98.674874,\n",
       "               'right': 125.295113},\n",
       "              'right': {'spInd': 0,\n",
       "               'spVal': 0.571214,\n",
       "               'left': 82.589328,\n",
       "               'right': {'spInd': 0,\n",
       "                'spVal': 0.569327,\n",
       "                'left': 114.872056,\n",
       "                'right': 108.435392}}}}},\n",
       "           'right': 82.903945},\n",
       "          'right': {'spInd': 0,\n",
       "           'spVal': 0.549814,\n",
       "           'left': 120.857321,\n",
       "           'right': 137.267576}},\n",
       "         'right': {'spInd': 0,\n",
       "          'spVal': 0.546601,\n",
       "          'left': 83.114502,\n",
       "          'right': {'spInd': 0,\n",
       "           'spVal': 0.537834,\n",
       "           'left': {'spInd': 0,\n",
       "            'spVal': 0.543843,\n",
       "            'left': 96.319043,\n",
       "            'right': 98.36201},\n",
       "           'right': 90.995536}}},\n",
       "        'right': {'spInd': 0,\n",
       "         'spVal': 0.51915,\n",
       "         'left': {'spInd': 0,\n",
       "          'spVal': 0.531944,\n",
       "          'left': 129.766743,\n",
       "          'right': 124.795495},\n",
       "         'right': 116.176162}},\n",
       "       'right': {'spInd': 0,\n",
       "        'spVal': 0.508548,\n",
       "        'left': 101.075609,\n",
       "        'right': {'spInd': 0,\n",
       "         'spVal': 0.508542,\n",
       "         'left': 93.292829,\n",
       "         'right': 96.403373}}}}}}},\n",
       "  'right': {'spInd': 0,\n",
       "   'spVal': 0.457563,\n",
       "   'left': {'spInd': 0,\n",
       "    'spVal': 0.465561,\n",
       "    'left': {'spInd': 0,\n",
       "     'spVal': 0.467383,\n",
       "     'left': {'spInd': 0,\n",
       "      'spVal': 0.483803,\n",
       "      'left': {'spInd': 0,\n",
       "       'spVal': 0.487381,\n",
       "       'left': {'spInd': 0,\n",
       "        'spVal': 0.487537,\n",
       "        'left': 11.924204,\n",
       "        'right': 5.149336},\n",
       "       'right': 27.729263},\n",
       "      'right': 5.224234},\n",
       "     'right': {'spInd': 0,\n",
       "      'spVal': 0.46568,\n",
       "      'left': -9.712925,\n",
       "      'right': -23.777531}},\n",
       "    'right': {'spInd': 0,\n",
       "     'spVal': 0.463241,\n",
       "     'left': 30.051931,\n",
       "     'right': 17.171057}},\n",
       "   'right': {'spInd': 0,\n",
       "    'spVal': 0.455761,\n",
       "    'left': -34.044555,\n",
       "    'right': {'spInd': 0,\n",
       "     'spVal': 0.126833,\n",
       "     'left': {'spInd': 0,\n",
       "      'spVal': 0.130626,\n",
       "      'left': {'spInd': 0,\n",
       "       'spVal': 0.382037,\n",
       "       'left': {'spInd': 0,\n",
       "        'spVal': 0.388789,\n",
       "        'left': {'spInd': 0,\n",
       "         'spVal': 0.437652,\n",
       "         'left': {'spInd': 0,\n",
       "          'spVal': 0.454312,\n",
       "          'left': {'spInd': 0,\n",
       "           'spVal': 0.454375,\n",
       "           'left': 9.841938,\n",
       "           'right': 3.043912},\n",
       "          'right': {'spInd': 0,\n",
       "           'spVal': 0.446196,\n",
       "           'left': {'spInd': 0,\n",
       "            'spVal': 0.451087,\n",
       "            'left': -20.360067,\n",
       "            'right': -28.724685},\n",
       "           'right': -5.108172}},\n",
       "         'right': {'spInd': 0,\n",
       "          'spVal': 0.412516,\n",
       "          'left': {'spInd': 0,\n",
       "           'spVal': 0.418943,\n",
       "           'left': {'spInd': 0,\n",
       "            'spVal': 0.426711,\n",
       "            'left': {'spInd': 0,\n",
       "             'spVal': 0.428582,\n",
       "             'left': 19.745224,\n",
       "             'right': 15.224266},\n",
       "            'right': -21.594268},\n",
       "           'right': 44.161493},\n",
       "          'right': {'spInd': 0,\n",
       "           'spVal': 0.403228,\n",
       "           'left': -26.419289,\n",
       "           'right': {'spInd': 0,\n",
       "            'spVal': 0.391609,\n",
       "            'left': -1.729244,\n",
       "            'right': 3.001104}}}},\n",
       "        'right': {'spInd': 0,\n",
       "         'spVal': 0.385021,\n",
       "         'left': 21.578007,\n",
       "         'right': 24.816941}},\n",
       "       'right': {'spInd': 0,\n",
       "        'spVal': 0.335182,\n",
       "        'left': {'spInd': 0,\n",
       "         'spVal': 0.370042,\n",
       "         'left': {'spInd': 0,\n",
       "          'spVal': 0.378965,\n",
       "          'left': -29.007783,\n",
       "          'right': {'spInd': 0,\n",
       "           'spVal': 0.373501,\n",
       "           'left': {'spInd': 0,\n",
       "            'spVal': 0.377383,\n",
       "            'left': 13.583555,\n",
       "            'right': 5.241196},\n",
       "           'right': -8.228297}},\n",
       "         'right': {'spInd': 0,\n",
       "          'spVal': 0.35679,\n",
       "          'left': -32.124495,\n",
       "          'right': {'spInd': 0,\n",
       "           'spVal': 0.350725,\n",
       "           'left': {'spInd': 0,\n",
       "            'spVal': 0.351478,\n",
       "            'left': -19.526539,\n",
       "            'right': -0.461116},\n",
       "           'right': {'spInd': 0,\n",
       "            'spVal': 0.350065,\n",
       "            'left': -40.086564,\n",
       "            'right': {'spInd': 0,\n",
       "             'spVal': 0.342761,\n",
       "             'left': -1.319852,\n",
       "             'right': {'spInd': 0,\n",
       "              'spVal': 0.342155,\n",
       "              'left': -31.584855,\n",
       "              'right': {'spInd': 0,\n",
       "               'spVal': 0.3417,\n",
       "               'left': -16.930416,\n",
       "               'right': -23.547711}}}}}}},\n",
       "        'right': {'spInd': 0,\n",
       "         'spVal': 0.324274,\n",
       "         'left': {'spInd': 0,\n",
       "          'spVal': 0.32889,\n",
       "          'left': {'spInd': 0,\n",
       "           'spVal': 0.331364,\n",
       "           'left': {'spInd': 0,\n",
       "            'spVal': 0.3349,\n",
       "            'left': 2.768225,\n",
       "            'right': 18.97665},\n",
       "           'right': -1.290825},\n",
       "          'right': 39.783113},\n",
       "         'right': {'spInd': 0,\n",
       "          'spVal': 0.309133,\n",
       "          'left': {'spInd': 0,\n",
       "           'spVal': 0.310956,\n",
       "           'left': {'spInd': 0,\n",
       "            'spVal': 0.318309,\n",
       "            'left': -13.189243,\n",
       "            'right': -27.605424},\n",
       "           'right': -49.939516},\n",
       "          'right': {'spInd': 0,\n",
       "           'spVal': 0.131833,\n",
       "           'left': {'spInd': 0,\n",
       "            'spVal': 0.138619,\n",
       "            'left': {'spInd': 0,\n",
       "             'spVal': 0.156067,\n",
       "             'left': {'spInd': 0,\n",
       "              'spVal': 0.166765,\n",
       "              'left': {'spInd': 0,\n",
       "               'spVal': 0.193282,\n",
       "               'left': {'spInd': 0,\n",
       "                'spVal': 0.211633,\n",
       "                'left': {'spInd': 0,\n",
       "                 'spVal': 0.228473,\n",
       "                 'left': {'spInd': 0,\n",
       "                  'spVal': 0.25807,\n",
       "                  'left': {'spInd': 0,\n",
       "                   'spVal': 0.284794,\n",
       "                   'left': {'spInd': 0,\n",
       "                    'spVal': 0.300318,\n",
       "                    'left': 8.814725,\n",
       "                    'right': {'spInd': 0,\n",
       "                     'spVal': 0.297107,\n",
       "                     'left': -18.051318,\n",
       "                     'right': {'spInd': 0,\n",
       "                      'spVal': 0.295993,\n",
       "                      'left': -1.798377,\n",
       "                      'right': {'spInd': 0,\n",
       "                       'spVal': 0.290749,\n",
       "                       'left': -14.988279,\n",
       "                       'right': -14.391613}}}},\n",
       "                   'right': {'spInd': 0,\n",
       "                    'spVal': 0.273863,\n",
       "                    'left': 35.623746,\n",
       "                    'right': {'spInd': 0,\n",
       "                     'spVal': 0.264926,\n",
       "                     'left': -9.457556,\n",
       "                     'right': {'spInd': 0,\n",
       "                      'spVal': 0.264639,\n",
       "                      'left': 5.280579,\n",
       "                      'right': 2.557923}}}},\n",
       "                  'right': {'spInd': 0,\n",
       "                   'spVal': 0.228628,\n",
       "                   'left': {'spInd': 0,\n",
       "                    'spVal': 0.228751,\n",
       "                    'left': {'spInd': 0,\n",
       "                     'spVal': 0.232802,\n",
       "                     'left': -20.425137,\n",
       "                     'right': 1.222318},\n",
       "                    'right': -30.812912},\n",
       "                   'right': -2.266273}},\n",
       "                 'right': {'spInd': 0,\n",
       "                  'spVal': 0.222271,\n",
       "                  'left': {'spInd': 0,\n",
       "                   'spVal': 0.2232,\n",
       "                   'left': 19.425158,\n",
       "                   'right': 15.501642},\n",
       "                  'right': {'spInd': 0,\n",
       "                   'spVal': 0.218321,\n",
       "                   'left': -9.255852,\n",
       "                   'right': {'spInd': 0,\n",
       "                    'spVal': 0.217214,\n",
       "                    'left': 1.410768,\n",
       "                    'right': -3.958752}}}},\n",
       "                'right': {'spInd': 0,\n",
       "                 'spVal': 0.202161,\n",
       "                 'left': {'spInd': 0,\n",
       "                  'spVal': 0.203993,\n",
       "                  'left': {'spInd': 0,\n",
       "                   'spVal': 0.206207,\n",
       "                   'left': -8.332207,\n",
       "                   'right': -12.619036},\n",
       "                  'right': -22.379119},\n",
       "                 'right': {'spInd': 0,\n",
       "                  'spVal': 0.199903,\n",
       "                  'left': -1.983889,\n",
       "                  'right': -3.372472}}},\n",
       "               'right': {'spInd': 0,\n",
       "                'spVal': 0.176523,\n",
       "                'left': 18.208423,\n",
       "                'right': 0.946348}},\n",
       "              'right': {'spInd': 0,\n",
       "               'spVal': 0.156273,\n",
       "               'left': {'spInd': 0,\n",
       "                'spVal': 0.164134,\n",
       "                'left': {'spInd': 0,\n",
       "                 'spVal': 0.166431,\n",
       "                 'left': -14.740059,\n",
       "                 'right': -6.512506},\n",
       "                'right': -27.405211},\n",
       "               'right': 0.225886}},\n",
       "             'right': {'spInd': 0,\n",
       "              'spVal': 0.13988,\n",
       "              'left': 7.557349,\n",
       "              'right': 7.336784}},\n",
       "            'right': -29.087463},\n",
       "           'right': 22.478291}}}}},\n",
       "      'right': -39.524461},\n",
       "     'right': {'spInd': 0,\n",
       "      'spVal': 0.124723,\n",
       "      'left': 22.891675,\n",
       "      'right': {'spInd': 0,\n",
       "       'spVal': 0.085111,\n",
       "       'left': {'spInd': 0,\n",
       "        'spVal': 0.108801,\n",
       "        'left': {'spInd': 0,\n",
       "         'spVal': 0.11515,\n",
       "         'left': -1.402796,\n",
       "         'right': 13.795828},\n",
       "        'right': {'spInd': 0,\n",
       "         'spVal': 0.10796,\n",
       "         'left': -16.106164,\n",
       "         'right': {'spInd': 0,\n",
       "          'spVal': 0.085873,\n",
       "          'left': -1.293195,\n",
       "          'right': -10.137104}}},\n",
       "       'right': {'spInd': 0,\n",
       "        'spVal': 0.084661,\n",
       "        'left': 37.820659,\n",
       "        'right': {'spInd': 0,\n",
       "         'spVal': 0.080061,\n",
       "         'left': -24.132226,\n",
       "         'right': {'spInd': 0,\n",
       "          'spVal': 0.068373,\n",
       "          'left': {'spInd': 0,\n",
       "           'spVal': 0.079632,\n",
       "           'left': 2.229873,\n",
       "           'right': 29.420068},\n",
       "          'right': {'spInd': 0,\n",
       "           'spVal': 0.061219,\n",
       "           'left': -15.160836,\n",
       "           'right': {'spInd': 0,\n",
       "            'spVal': 0.044737,\n",
       "            'left': {'spInd': 0,\n",
       "             'spVal': 0.053764,\n",
       "             'left': {'spInd': 0,\n",
       "              'spVal': 0.055862,\n",
       "              'left': 6.695567,\n",
       "              'right': -3.131497},\n",
       "             'right': -13.731698},\n",
       "            'right': {'spInd': 0,\n",
       "             'spVal': 0.028546,\n",
       "             'left': {'spInd': 0,\n",
       "              'spVal': 0.039914,\n",
       "              'left': 3.855393,\n",
       "              'right': 11.220099},\n",
       "             'right': {'spInd': 0,\n",
       "              'spVal': 0.000256,\n",
       "              'left': -8.377094,\n",
       "              'right': 9.668106}}}}}}}}}}}}},\n",
       " None)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myDat2=loadDataSet(\"./input&code/Ch09/ex2.txt\")\n",
    "myMat2=mat(myDat2)\n",
    "mM2=createTree(myMat2,ops=(0,1))\n",
    "import matplotlib.pyplot as plt  \n",
    "plt.plot(myMat2[:,0],myMat2[:,1],'ro') \n",
    "mM2,plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAD8CAYAAAB0IB+mAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3W1sJVd5B/D/Y69N5Q202euAIsB2QEFq4EOaWBGoFQWBINpKpEiAgkwaQlSDgSpqq0qJ/AHUaj80CCHRQsC0EWl8gaSVKCsaSmlKRVU1wF0B6RI1ZYH1EhKRzS4vQZuSze7TD3Nvdjyel3Nmzjlz5s7/J13Zvh7PnJm7+8yZ57yJqoKIiKbfTNsFICKiMBjwiYh6ggGfiKgnGPCJiHqCAZ+IqCcY8ImIeoIBn4ioJxjwiYh6ggGfiKgn9rVdgLTFxUVdWVlpuxhERJ1y5MiRJ1T1kqrtogr4KysrGI1GbReDiKhTRGTHZDumdIiIeoIBn4ioJxjwiYh6ggGfiKgnGPCJiHqCAZ+oi4ZDYGUFmJlJvg6HbZeIOiCqbplEZGA4BNbXgTNnkp93dpKfAWBtrb1yUfRYwyfqms3NC8F+4syZ5H2iEgz4RF1z4oTd+0RjDPhEXbO0ZPc+0RgDPlHXHDoELCzsfm9hIXmfqAQDPlHXrK0BW1vA8jIgknzd2mKDLVViLx2iLlpbY4Ana6zhExH1BAM+EVFPMOATEfUEAz4RUU8w4BMR9QQDPhFRTzDgExH1BAM+EVFPGAd8EblTRB4XkaOp9z4oIj8WkW+PXwdTv7tNRI6JyMMi8kbXBSciIjs2NfxPA7g25/2PqOqV49d9ACAiVwC4HsDLx3/zcRGZbVpYIiKqzzjgq+rXAJw23Pw6AJ9T1V+p6g8BHANwTY3yERGRIy5y+O8XkQfHKZ+Lx++9EMCPUts8Mn6PiIha0jTg3wHgpQCuBPAYgA+P35ecbTVvByKyLiIjERmdPHmyYXGIiKhIo4Cvqj9R1XOqeh7Ap3AhbfMIgBenNn0RgEcL9rGlqququnrJJZc0KQ4REZVoFPBF5NLUj28GMOnBcxjA9SLyHBG5DMDlAL7R5FhERNSM8Xz4IvJZAK8BsCgijwD4AIDXiMiVSNI1xwG8GwBU9bsici+AhwA8A+B9qnrObdGJiMiGqOam1luxurqqo9Go7WIQEXWKiBxR1dWq7TjSlmhaDYfAygowM5N8HQ7bLhG1jEscEk2j4RBYXwfOnEl+3tlJfga4NGKPsYZPNI02Ny8E+4kzZ5L3qbcY8IlCCZliOXHC7n3qBQZ8ohAmKZadHUD1QorFV9BfWrJ7n3qBAZ8ohNAplkOHgIWF3e8tLCTvN8GG4HoiuW4M+EQhhE6xrK0BW1vA8jIgknzd2mrWYBv6KaWOSALrLhFdN/bDJwphZSX5j561vAwcPx66NPXEfg7ZnklA8lTT9EbXVIDrxn74RDHxlWIJKfaG4Fh7JkV03RjwiULwkWIJLfaG4IgC67OGwyS9lKeF68aAT+RDXi55bS15hD9/PvlqE+xjyE3H/pQS2w1pkmI6lzONWFvXTVWjeV199dVK1Hnb26oLC6pJE13yWlhI3o9hf01sb6suL6uKJF/bKEORmK6TanJ90mWZvGZnnZcJwEgNYiwbbYlcc91IF3tjaUyGwyRnf+JEUrM/dKi9tNnMTBLis0SSpzyHTBttGfCJXHP9Hz1g4CCHAt6o2UuHqC0ucsnpnH1EjX5kIcI2DwZ8ItcOHkxq32k2/9GzA3ViavQjcxH2zGLAJ3JpOATuumt3CkYEuPFG8//oef3JAWB2NprAQYYmPbPuvjv5+YYbOLUC0dTIC9aqwH33me+jqN/4+fP1unQWiaGrZx9ENLUCAz6RS1WDf0yCbIj+5DZBiDeGZmIaAWzSdzPUi/3wqfOK+l5P+qyb9BMP0Z+8rJyhyzItisYoiORfaxFnh4ZhP/zWg3z6xYBPnVcWIE2D7GQ/Pgc45ZVj8kqzKbMrVefexuAvkzK5+NxrYsAnaktbNT2bQDg7m1+W2dnd2wWone45h7InijaeOEyO6eLJrgEGfKJQTAOtz5qebVCJtYZfdbw2njhMjll1Y/T8VMKATxSCTaD1WdOzTRcV1fDzcvjz87u3mZ9vVuay4FcVOE2eOFwHV5NjDgbhb0QppgGfvXSImrDpgVE0EAdo3gvGdGrgOjM4qpb/bKOqd1BVD6Wq3/voAmlyzCef3Pv7ubn4BseZ3BVCvVjDp85pmuN2Ves3reHbzuDoOoVStb+q67Gxsfeap3/vI+VTVaaiYw4G9Y9pCUzpEAXQNMC4ClAmN47t7fxj5d2gynqX2NzQspqkZPLOUSS5Cdjsv44maSjT/TTAgE8UQtMaussAVRZM8spZdIOp2jbvhhSi4drkb9vo+hrBmAYGfKJQmgSOUL1Oymrrk6BTVasve3Jw2XDdpFtrG4PbTPfl8bNmwCfqgu1t1bm53QFgbs59v/KiYAlcCPZVtfpJcNrY2B2QbXuo2D6J2A5gMrkBu9yX6XYexzQw4BN1gY9uj3nq9m/Pbmt6Y6gbyEINYCq7AU6C9saG2xQMa/gM+NRzoVI6VcGyLACmty2qzbs6h6qbR930WfbvbM6j7AZkgzl8BnzqOVeP+SaBMLtNOjVTNBArHdw2NswDYp1Atr1dfD1cd6ucn9+bSrN9VZ1j3mfCXjoM+NRjLmr4dWqOJqmZ7Bw2ZU8Bg0HzQFZ0LUSaBcayfvKTMjep6ecJPOcPAz5RF7gIDHVuGmUDsPKCdlWOP90Xvq6ywOtjv+mnKJM2jKp9pAWe88c04HNqBaI2uVj31HRaBZPfFa2qVbYvIFnWsenCKEVTGCwv+9lv+v28Bceb7LvOZxKAccAXkTtF5HEROZp674CIfEVEvjf+evH4fRGRj4rIMRF5UESu8lF4ola5Wglqsu5p3eUL66yQZfs3VattNVnBaXIdd3b2/s7FfDR5wTw7b1D6xgvsXYR+bg6Yny/fR1rR9dq/37zcPpg8BiRPDHg1gKsAHE29dzuAW8ff3wrgL8ffHwTwJQAC4JUAvm5yDKZ0qDPamJfdZVls/8Yk5193dHDZfrNdVF310qn6u3S//0mD9mCQvEz65Jf1AnKR/sqAjxw+gJVMwH8YwKXj7y8F8PD4+08CeHvedmUvBnzqjBA5WpsgVScQNgmCrs7dtP//5Pghb7K+GsMn19thT51QAf9nmd//dPz1iwB+J/X+/QBWq/bPgE+d4XvCrJieIHyWzaSHzOSaBm4IddoYXvZy8Lm2HfD/KSfgX12wz3UAIwCjpaWlRidNFIzpdAImMzzmCR3cbPmeeCzvnEMvt2gyGjd73nW7eDb8XJnSIfIlbzoEIH8OnLp9y0MHt7ZUpUDqznVvOxAtLz9fZyI51907DYUK+B/KNNrePv7+9zKNtt8w2T8DPnVC2UCerLIaX53UQCw1fJeqAm96OxczYZpOEbF/v9lo3PRnUnYDm51VvegiL5+r84AP4LMAHgNwFsAjAG4GMBina743/npgvK0A+BiA7wP4b5P8vTLgU1fY1L7LanxltbqioJWdqTIv2HkYum/NVzmazoRpM/kbkDzJTW5App9j3dlAG/BSw/f9YsCnTiiqHebV8JvMD5M3901VzdW2q6WrqX+z27fZ4Fx2Q66TcjGZUdRnF1EDDPhEvpgG/LI8sI91a8umS7BNe9huZ1NOG3WCY9nx6zSqpmfqNG1vCIwBn8iXuisvTf6ubq2u6rhlwcy0cTEblOsEb5czgNZ5Uij7uyY1/Mm+XY9FcIABn8gXkyDoo9G1bg0/79imQblO8HZ17k32U9QQPBjk97Davz95mdbaI+tFZRrwOXkakS2TuVl8TJ5VddyqCcDSxzadM6fO3Dom18dEk2s4mZ/o7ruBp54CTp1KQvLk62BwYbK67W3gl79MXtvbZhPZ1Z1zqG0md4VQL9bwqTOqcsu+ulUWHdckXVHVfdDlYt8uGiZdXMOm+yi73i4XQW94rcCUDlGLQvZUMelqWBTMffTSccXFNWySejHpz9/0ujj6d8KAT9S2UIGyrHdO2/3xm2p6DZvU8F11w/RVvhTTgC/JtnFYXV3V0WjUdjGI3BsOk/niT5xI8ryHDtnPe19kZiYJE1kiyRz7fTYcAuvryXz9EwsLZovMFF1X2/3UOYblZyciR1R1tfJwVoUjInuToLOzk/zn3tkBbroJWFzMXzzFdmGVoobCAweSY4gkr8XF5qtSdU2dFcUm17+qMmy66EvZ5xm68dfkMSDUiykdmko2k3C5moN9bk513769x8mb4C2kWKZ+KGI79UJVW4BJOwBz+ERTxHR05/Jy/ZxuNpCWTQ7W1gRsbU+5YMJ2YFbVtTT5PAP20mEOn8i3ovVasybrqOb9n7TNx5fln9vK7Rddh+XlpM98DMqu28KCfVtAoPYV5vCJYlE1IGpiacldTrfOAua++RiM5lrRtZnk/m3aAsr219JnwIBP5Fu24XAwAObnd28zGYlqO0q1qEHw0KG9xwCAuTn7Ea+u1Al+Ng3Yto3decqu/2T07vnzyVeT3jmuRh27YpL3CfViDp96o2rOdNMBUTYLfQwG7TfY2k7fbLp93rbpuezbnL44QEM1mMMnmnJdyIln2YxHsDk/k3YSF/3mI8UcPtG0iy0nbpJSsUmL2JyfyTmb9pt3yUWaySEGfKKuiqlBMG9w2fp6swBnc36m5xzyZujjmjTEgE/UVTE1CG5u7u6yCDSvUducn01PqFB8XJOGGPCJuqrOtAG++EgvlZ1fNlUC7O0JNTe3e3+hb4axpdwANtoSkQMhG5BNJ0TzOWGdicXFZMGVLA/XhI22RBROyPSSaaqkTr95V4ZD4Mkn977f5jgIMOATkQsh00sRpkr22NwEnn567/vPe16r3UIZ8InIjVA16ph6J6Wl2xWKxgScPh20SFkM+ETULTH1TprIdsEs0vJNiQGfiMLI9qx573vrDUqKqXfSRF67QlbbNyUw4BNRCHmDkO64w3xQUl43zLYaZPOUtR/EclMCu2USUQimawLkdVlssi5tKC3Pa8RumUQUD9MeNHnb2Y5YbWP+mhjbFXIw4BORf6aNlXnblXXDzGsXaGP+mhjbFXIwpUNE/uWlZbKK0jRF6ZLBAHjqqd37FMnvJRPzlNEOMKVDRPHIqwFvbJjViIvSJcDeG0hRBTamQVkt2td2AYioJ9bW6qU4Jn+TnRfnhhvM99H2oKxIsIZPRPHLG8VbFMRFdv8cYeNpWxjwiaibilI973lP9I2nbWFKh4i6qSjVw+BeiAGfiLqrbrtATzkJ+CJyHMCTAM4BeEZVV0XkAIB7AKwAOA7gbar6UxfHIyIiey5z+K9V1StTfUFvBXC/ql4O4P7xz0RE1BKfjbbXAbhr/P1dAH7f47GIiKiCq4CvAP5FRI6IyPr4vReo6mMAMP76/Lw/FJF1ERmJyOjkyZOOikNERFmuGm1/W1UfFZHnA/iKiPyP6R+q6haALSCZWsFReYiIKMNJDV9VHx1/fRzA5wFcA+AnInIpAIy/Pu7iWEREVE/jgC8i+0XkuZPvAbwBwFEAhwHcON7sRgBfaHosokJtTIlL1DEuUjovAPB5SYYz7wPwGVX9ZxH5JoB7ReRmACcAvNXBsYj2ys7EOJkSF2AfbaIUTo9M3dfyakNEbeP0yNQfZQtkENGzGPDJj5A59aJZEzklLtEuDPg22DBoZpJTD7XMXEfWEyVqGwO+qdBBrMtsF51uqiPriRK1jQHfVOggFhPbJ5s2cup5C2QQ0S4M+Kb62jBY58mGOXWiKDHgm+prEKvzZMOcOlGUGPBN9TWI1XmyYU6dKEoM+Kb6GsTqPtkwp04UHQZ8G30MYn14smF3W+oJBnwTfQ4I0/5kw+621COcS6dKdmIuIKnhTlPQ6zPOw0NTgHPpuNLn/vd9UNYo3ecnO5pKDPhV+tr/vi+KGp8PHGCqh6YOA36Vvva/j4XvWnZRozTAJzuaOgz4VfrQSyVWIRpUixqlT5/O355PdtRhDPhVmvZSGQ6BxcXkb0WS75kWMBOq/SSvuy2f7GgKMeCbqNv/fjgEbroJOHXqwnunTgHveheDvomi2nRerxrX+GRHU4gB36fNTeDs2b3vP/00c8EmimrTIv5vmNM+/oB6iQHfp7J8b4hccAzdCpuU4dChJNhmqZrfMJscv48jq2m6qWo0r6uvvlqnyvKyahKe9r6Wl+vtc3s7+VuR5Ov2dvF2Cwu7j7mwULy9Dy7KUHT9RMIcn6gDAIzUIMa2HuTTr6kL+NvbqnNze4PV/Hy9oGMTwIpuNnVvNHW4KEOTfZj8rekNlChiDPix2N5WHQwuBJvBoH5QsQl+IvnbmtSMXXFRhia19Krj8wmApoRpwGcO37e1NeCJJy6ElCeeqJ8Lthn1e+BA/rYhuxW66NpYp/F0krfXgnmiJsfntBnUMwz4rvlsKDUNoMMh8Itf7N1ufj5st8ImXRvT13FzM/kbk8bT9GCtPOnjc9oM6huTx4BQr86ndHynCEz3X5T6GQzclMO2zLY58ibXsaqhPL2PGNo5iBwAc/glfDXUhQggJmWPIX/fRJPraHPutjcWNvBSpBjwi/ishccSaLtec21yHW3PvUvdXIkKmAb87ufwbXPmPhvqYpl/pevTAjS5jqbnPvl3c8MNyc93313ePsAGXpoGJneFUC/rGn6dWpfPWnhMtcBQ6Qcfx2l6HavKFNu/G6KG0IuUTp3Uhe90h0mwyf6+q7lhnzc4n9ckxn83RA30I+DXqXWVBSnfgTfv2HNzycjbGJ4KbHU1CLr+d0PUMtOA3+0cfp1cb9FAHsD/Yht5eeCzZ5PZM9PayA3XGT/gqx+770nfTP7dZNcxuOUW4MYbOXsmdZvJXSHUK0gOP/236dp8evoDX7XVoppl27nhutfRRw0/RE266hiu50Ai8gy9SOmouhvYEyLwlg0KajMtUjdwmwRn28+nbNCYq3Rb1fxGPmY5JfKoPwG/DtvA6yq3HyKHX6esZeff5Hgue8NkX3WvkUmZysrAXjkUoWgCPoBrATwM4BiAW8u2DRbwbYLKxobbFENegNzYUJ2dTfY9O5v8XLRt1b7zyrqxUb6fybGzr9nZeuc44bI3jKvatkmZWMOnjoki4AOYBfB9AC8BMA/gOwCuKNq+9Rp+XtogRDfOoiBte6MpKmv2BpfdT5MafpmyG6vNU4HL2rZJDx3m8KljYgn4rwLw5dTPtwG4rWj7oHPpmAZT0y58dfvXFwXpolp32eIdpjVj0xpt3k3N5qmjqCG8KpCaNqhPymgThE3P1eU6BkSexRLw3wLgb1I/3wDgr4u2DzpbZjaoFKU9TFdNqpubt+m5k77R5B2zbi8g0xugzY1ye3vv+Ze9ymbyrKr1247CZX96mjKxBPy35gT8v8pssw5gBGC0tLTk9aIUqhqMVRUgmuSd69bwTWvPpuVo8jSS9yRg+8QBVH9GrnLrXR3ZTFQgloAfZ0onqyqQVQWIJv3r6+Twt7ebBfu6NVqbEaq2Ty5VAb9OGbIY6GlKxRLw9wH4AYDLUo22Ly/avrWA33RirKY9S4oCUdH7dWrP6VfdQOeihj8zk/++6eIsPscMEHVUFAE/KQcOAvjfcW+dzbJto63hV3HZv96kFlqn9mx7TqbnWZbDL3pyyfaAmZvzn4Pv6rw/RAaiCfg2L28BvyqIuqj91e2lU6ccdWv4Lmq0Nudk++Riuv86qRlOb0xTjAF/wqYHStv5XZsug6Z91dP7sKlFt3EtfKZdyq5tDJ89UQMM+BMuH+V9Bwbb9VgnZSnq0VMnaLaZ6/aZdnE5wI0oMgz4E64e5UMEwroBzySnbxo028x1+0675N2wmdunKWAa8Ls9H74JV+vMhljTtM5atMNhMm98FdM56n3NcW/C95rAa2vJurXnz19Yv7bN8yUKbPoDvkkQNVlwI0RgKFqcpWiRjeEwWaTl3LnqfZsGTRdBt+4CJm0svh7LwvNEIZg8BoR6tdJLx3SGyRALpFSVNcu0t46LHP7kegAX2gx89HgK3YDK/vk0BcAcviHTGSbn5/f2H8+uktQ0UNkGnzqzUZqWIzvPUFGvINNpJmLOibOXDnUcA74pm0FMRasuuaol2gbLUMG16kkifTxfNyEiKmQa8CXZNg6rq6s6Go3CHnRlJVmw3IRI0uBnuo/l5aRx0NTMTBIaTY87yeGnG5MXFtwvrl1UrrTJ74uuhcjuffgoJ1FPicgRVV2t2m76G22r5DUUiuRvW9SQ56pB17YB0baRt66qBkyRCw2zRdcze8M4cwa45ZZ6jbtEVI/JY0CoV2tz6ZjkrMtSNK5SK200IJpOZVA1sje7PkB6n6Yps1CNpczZ05QBc/gN2c4Z4ypQhwxGtpOhlQXvssFRTWcTrXNetr2yGPSpwxjwQ2tz/pm6x63zZFLnb2zm/mk6qrYqoHexFxFRBQb8PmhaW60zlUHdY25sXOi/Pzurun+/n8BbFdDLehExxUMdZRrw2Whro+4IUl+aTvdQZ5RpnYbi4RC4664LI4LPnQPOngXm5nZv52JUbVUDetm5qSY9jNbX2/9siXwwuSuEekVdw48x99t0srFQ51RU6y4a1+DjWJMavml6iSke6hCwhu9YiMnTbJ8gms4DE6pbZ1Gt+/TpvZOZ2cpes4MHy+fjyZ6zbZmJuszkrhDqFXUNP8TUvba17dieOooakH01lJrOg1RnPiLW8KlDwEZbx1wEhrIeNXX3H0uf8rKbT90bU9W51e0x1GTMBVGEGPBdczELZNnfd33NVZPcuc2NyeR6214zF08ERBFiwPfBZ593H6mFkLV/k+DrYurn9PWIdbI5osAY8GNTFRBd5+ND5/fr9I7Jlid9Q8jbV94NxMV00l15iiIqwIAfG5PapcsaeejabNMRrnW7S7p+aiDqIAb82ISucbdRmy0LvlXlMZlvp+n1KrqpDAbM21OnmQZ89sMPJVSf94k21mrNWyTctDxl/d5dXa/JZzAY7H7/1CmOrqVeYMAPqSwgutbGguBNylN0Q1hednu91taAiy7a+77rQXREEWLAn1ahnyialifkDcrVgjVEHcOAH0Jbk66FfKJoWp6QN6g20l1EEWDA922y7uzOTtJEyNkYi2+AoW5QsaW7iAJhwPctxKRrXRLDDTC2dBdRIJL06InD6uqqjkajtovh1sxMEtiyRJKabN+srCRBPmt5OanVE5E1ETmiqqtV27GG7xvzxbuxwZSoNQz4vjFfvBtvgEStYcD3jfni3XgDJGrNvrYL0Atra/0N8FmT67C5maRxlpaSYM/rQ+QdAz6FxxsgUSsapXRE5IMi8mMR+fb4dTD1u9tE5JiIPCwib2xeVCIiasJFDv8jqnrl+HUfAIjIFQCuB/ByANcC+LiIzDo4FsWorZHERGTFV6PtdQA+p6q/UtUfAjgG4BpPx6I2xTCQioiMuAj47xeRB0XkThG5ePzeCwH8KLXNI+P3aNpwJDFRZ1QGfBH5VxE5mvO6DsAdAF4K4EoAjwH48OTPcnaVO6RXRNZFZCQio5MnT9Y8DWoNB1IRdUZlLx1Vfb3JjkTkUwC+OP7xEQAvTv36RQAeLdj/FoAtIJlaweRYFJGlpfypEjiQiig6TXvpXJr68c0Ajo6/PwzgehF5johcBuByAN9ociyKFAdSEXVG0374t4vIlUjSNccBvBsAVPW7InIvgIcAPAPgfap6ruGxKEYcSEXUGZwtk4io4zhbJhER7cKAT0TUEwz4REQ9wYBPRNQTDPhERD0RVS8dETkJIGcUj5FFAE84LE5X8Lz7hefdL6bnvayql1RtFFXAb0JERibdkqYNz7tfeN794vq8mdIhIuoJBnwiop6YpoC/1XYBWsLz7heed784Pe+pyeETEVG5aarhExFRic4FfBG5drww+jERuTXn988RkXvGv/+6iKyEL6V7Buf9JyLy0Hj1sftFZLmNcrpWdd6p7d4iIioiU9GTw+S8ReRt48/8uyLymdBl9MHg3/mSiHxVRL41/rd+sI1yujZeMfBxETla8HsRkY+Or8uDInJVrQOpamdeAGYBfB/ASwDMA/gOgCsy27wXwCfG318P4J62yx3ovF8LYGH8/UZfznu83XMBfA3AAwBW2y53oM/7cgDfAnDx+Ofnt13uQOe9BWBj/P0VAI63XW5H5/5qAFcBOFrw+4MAvoRkNcFXAvh6neN0rYZ/DYBjqvoDVX0awOeQLJiedh2Au8bf/wOA14lI3pKLXVJ53qr6VVWdLC77AJJVxrrO5PMGgL8AcDuA/wtZOI9MzvsPAXxMVX8KAKr6eOAy+mBy3grgeePvfx0FK+l1jap+DcDpkk2uA/B3mngAwG9kFqAy0rWAb7I4+rPbqOozAH4OYBCkdP7YLgp/M5LaQNdVnreI/BaAF6vqFzE9TD7vlwF4mYj8p4g8ICLXBiudPybn/UEA7xCRRwDcB+CPwhStdbYxIFfTFa9CM1kc3XgB9Q6xWRT+HQBWAfyu1xKFUXreIjID4CMA3hmqQIGYfN77kKR1XoPkae4/ROQVqvozz2XzyeS83w7g06r6YRF5FYC7x+d93n/xWuUkrnWthm+yOPqz24jIPiSPfWWPSl1gtCi8iLwewCaAN6nqrwKVzaeq834ugFcA+HcROY4kt3l4ChpuTf+df0FVz6rqDwE8jOQG0GUm530zgHsBQFX/C8CvIZlvZtoZxYAqXQv43wRwuYhcJiLzSBplD2e2OQzgxvH3bwHwbzpu9eiwyvMepzY+iSTYT0M+F6g4b1X9uaouquqKqq4gabt4k6p2fZ1Mk3/n/4ikoR4isogkxfODoKV0z+S8TwB4HQCIyG8iCfgng5ayHYcB/MG4t84rAfxcVR+z3UmnUjqq+oyIvB/Al5G06N+pyYLpfw5gpKqHAfwtkse8Y0hq9te3V2I3DM/7QwAuAvD34zbqE6r6ptYK7YDheU8dw/P+MoA3iMhDAM4B+DNVPdVeqZszPO8/BfApEfljJCmNd05BhQ4i8lkk6bnFcfvEBwDMAYCqfgJJe8VBAMcAnAFwU63jTMG1IiIiA11L6RARUU0M+ET6idkOAAAAKUlEQVREPcGAT0TUEwz4REQ9wYBPRNQTDPhERD3BgE9E1BMM+EREPfH/sMIH6Ga+FgAAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "({'spInd': 0,\n",
       "  'spVal': 0.499171,\n",
       "  'left': 101.35815937735848,\n",
       "  'right': -2.637719329787234},\n",
       " None)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myDat2=loadDataSet(\"./input&code/Ch09/ex2.txt\")\n",
    "myMat2=mat(myDat2)\n",
    "mM2=createTree(myMat2,ops=(10000,4))\n",
    "import matplotlib.pyplot as plt  \n",
    "plt.plot(myMat2[:,0],myMat2[:,1],'ro') \n",
    "mM2,plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### 后剪枝(postpruning)\n",
    "决策树构造完成后进行剪枝。剪枝的过程是对拥有同样父节点的一组节点进行检查，判断如果将其合并，熵的增加量是否小于某一阈值。如果确实小，则这一组节点可以合并一个节点，其中包含了所有可能的结果。合并也被称作 塌陷处理 ，在回归树中一般采用取需要合并的所有子树的平均值。后剪枝是目前最普遍的做法。\n",
    "\n",
    "后剪枝 prune() 的伪代码如下:\n",
    "```\n",
    "基于已有的树切分测试数据:\n",
    "    如果存在任一子集是一棵树，则在该子集递归剪枝过程\n",
    "    计算将当前两个叶节点合并后的误差\n",
    "    计算不合并的误差\n",
    "    如果合并会降低误差的话，就将叶节点合并\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "#判断输入是否为一棵树\n",
    "def isTree(obj):\n",
    "    return (type(obj).__name__=='dict') #判断为字典类型返回true\n",
    "#返回树的平均值\n",
    "def getMean(tree):\n",
    "    if isTree(tree['right']):\n",
    "        tree['right'] = getMean(tree['right'])\n",
    "    if isTree(tree['left']):\n",
    "        tree['left'] = getMean(tree['left'])\n",
    "    return (tree['left']+tree['right'])/2.0\n",
    "\n",
    "\n",
    "#树的后剪枝\n",
    "def prune(tree, testData):#待剪枝的树和剪枝所需的测试数据\n",
    "    if shape(testData)[0] == 0: return getMean(tree)  # 确认数据集非空\n",
    "    #假设发生过拟合，采用测试数据对树进行剪枝\n",
    "    if (isTree(tree['right']) or isTree(tree['left'])): #左右子树非空\n",
    "        lSet, rSet = binSplitDataSet(testData, tree['spInd'], tree['spVal'])\n",
    "    if isTree(tree['left']): tree['left'] = prune(tree['left'], lSet)\n",
    "    if isTree(tree['right']): tree['right'] = prune(tree['right'], rSet)\n",
    "    #剪枝后判断是否还是有子树\n",
    "    if not isTree(tree['left']) and not isTree(tree['right']):\n",
    "        lSet, rSet = binSplitDataSet(testData, tree['spInd'], tree['spVal'])\n",
    "        #判断是否merge\n",
    "        errorNoMerge = sum(power(lSet[:, -1] - tree['left'], 2)) + \\\n",
    "                       sum(power(rSet[:, -1] - tree['right'], 2))\n",
    "        treeMean = (tree['left'] + tree['right']) / 2.0\n",
    "        errorMerge = sum(power(testData[:, -1] - treeMean, 2))\n",
    "        #如果合并后误差变小\n",
    "        if errorMerge < errorNoMerge:\n",
    "            print(\"merging\")\n",
    "            return treeMean\n",
    "        else:\n",
    "            return tree\n",
    "    else:\n",
    "        return tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'spInd': 0,\n",
       " 'spVal': 0.499171,\n",
       " 'left': {'spInd': 0,\n",
       "  'spVal': 0.729397,\n",
       "  'left': {'spInd': 0,\n",
       "   'spVal': 0.952833,\n",
       "   'left': {'spInd': 0,\n",
       "    'spVal': 0.965969,\n",
       "    'left': 92.5239915,\n",
       "    'right': {'spInd': 0,\n",
       "     'spVal': 0.956951,\n",
       "     'left': {'spInd': 0,\n",
       "      'spVal': 0.958512,\n",
       "      'left': {'spInd': 0,\n",
       "       'spVal': 0.960398,\n",
       "       'left': 112.386764,\n",
       "       'right': 123.559747},\n",
       "      'right': 135.837013},\n",
       "     'right': 111.2013225}},\n",
       "   'right': {'spInd': 0,\n",
       "    'spVal': 0.759504,\n",
       "    'left': {'spInd': 0,\n",
       "     'spVal': 0.763328,\n",
       "     'left': {'spInd': 0,\n",
       "      'spVal': 0.769043,\n",
       "      'left': {'spInd': 0,\n",
       "       'spVal': 0.790312,\n",
       "       'left': {'spInd': 0,\n",
       "        'spVal': 0.806158,\n",
       "        'left': {'spInd': 0,\n",
       "         'spVal': 0.815215,\n",
       "         'left': {'spInd': 0,\n",
       "          'spVal': 0.833026,\n",
       "          'left': {'spInd': 0,\n",
       "           'spVal': 0.841547,\n",
       "           'left': {'spInd': 0,\n",
       "            'spVal': 0.841625,\n",
       "            'left': {'spInd': 0,\n",
       "             'spVal': 0.944221,\n",
       "             'left': {'spInd': 0,\n",
       "              'spVal': 0.948822,\n",
       "              'left': 96.41885225,\n",
       "              'right': 69.318649},\n",
       "             'right': {'spInd': 0,\n",
       "              'spVal': 0.85497,\n",
       "              'left': {'spInd': 0,\n",
       "               'spVal': 0.936524,\n",
       "               'left': 110.03503850000001,\n",
       "               'right': {'spInd': 0,\n",
       "                'spVal': 0.934853,\n",
       "                'left': 65.548418,\n",
       "                'right': {'spInd': 0,\n",
       "                 'spVal': 0.925782,\n",
       "                 'left': 115.753994,\n",
       "                 'right': {'spInd': 0,\n",
       "                  'spVal': 0.910975,\n",
       "                  'left': {'spInd': 0,\n",
       "                   'spVal': 0.912161,\n",
       "                   'left': 94.3961145,\n",
       "                   'right': 85.005351},\n",
       "                  'right': {'spInd': 0,\n",
       "                   'spVal': 0.901444,\n",
       "                   'left': {'spInd': 0,\n",
       "                    'spVal': 0.908629,\n",
       "                    'left': 106.814667,\n",
       "                    'right': 118.513475},\n",
       "                   'right': {'spInd': 0,\n",
       "                    'spVal': 0.901421,\n",
       "                    'left': 87.300625,\n",
       "                    'right': {'spInd': 0,\n",
       "                     'spVal': 0.892999,\n",
       "                     'left': {'spInd': 0,\n",
       "                      'spVal': 0.900699,\n",
       "                      'left': 100.133819,\n",
       "                      'right': 108.094934},\n",
       "                     'right': {'spInd': 0,\n",
       "                      'spVal': 0.888426,\n",
       "                      'left': 82.436686,\n",
       "                      'right': {'spInd': 0,\n",
       "                       'spVal': 0.872199,\n",
       "                       'left': 98.54454949999999,\n",
       "                       'right': 106.16859550000001}}}}}}}}},\n",
       "              'right': {'spInd': 0,\n",
       "               'spVal': 0.84294,\n",
       "               'left': {'spInd': 0,\n",
       "                'spVal': 0.847219,\n",
       "                'left': 89.20993,\n",
       "                'right': 76.240984},\n",
       "               'right': 95.893131}}},\n",
       "            'right': 60.552308},\n",
       "           'right': 124.87935300000001},\n",
       "          'right': {'spInd': 0,\n",
       "           'spVal': 0.823848,\n",
       "           'left': 76.723835,\n",
       "           'right': {'spInd': 0,\n",
       "            'spVal': 0.819722,\n",
       "            'left': 59.342323,\n",
       "            'right': 70.054508}}},\n",
       "         'right': {'spInd': 0,\n",
       "          'spVal': 0.811602,\n",
       "          'left': 118.319942,\n",
       "          'right': {'spInd': 0,\n",
       "           'spVal': 0.811363,\n",
       "           'left': 99.841379,\n",
       "           'right': 112.981216}}},\n",
       "        'right': 73.49439925},\n",
       "       'right': {'spInd': 0,\n",
       "        'spVal': 0.786865,\n",
       "        'left': 114.4008695,\n",
       "        'right': 102.26514075}},\n",
       "      'right': 64.041941},\n",
       "     'right': 115.199195},\n",
       "    'right': 78.08564325}},\n",
       "  'right': {'spInd': 0,\n",
       "   'spVal': 0.640515,\n",
       "   'left': {'spInd': 0,\n",
       "    'spVal': 0.642373,\n",
       "    'left': {'spInd': 0,\n",
       "     'spVal': 0.642707,\n",
       "     'left': {'spInd': 0,\n",
       "      'spVal': 0.665329,\n",
       "      'left': {'spInd': 0,\n",
       "       'spVal': 0.706961,\n",
       "       'left': {'spInd': 0,\n",
       "        'spVal': 0.70889,\n",
       "        'left': {'spInd': 0,\n",
       "         'spVal': 0.716211,\n",
       "         'left': 110.90283,\n",
       "         'right': {'spInd': 0,\n",
       "          'spVal': 0.710234,\n",
       "          'left': 103.345308,\n",
       "          'right': 108.553919}},\n",
       "        'right': 135.416767},\n",
       "       'right': {'spInd': 0,\n",
       "        'spVal': 0.698472,\n",
       "        'left': {'spInd': 0,\n",
       "         'spVal': 0.69892,\n",
       "         'left': {'spInd': 0,\n",
       "          'spVal': 0.699873,\n",
       "          'left': {'spInd': 0,\n",
       "           'spVal': 0.70639,\n",
       "           'left': 106.180427,\n",
       "           'right': 105.062147},\n",
       "          'right': 115.586605},\n",
       "         'right': 92.470636},\n",
       "        'right': {'spInd': 0,\n",
       "         'spVal': 0.689099,\n",
       "         'left': 120.521925,\n",
       "         'right': {'spInd': 0,\n",
       "          'spVal': 0.666452,\n",
       "          'left': 101.91115275,\n",
       "          'right': 112.78136649999999}}}},\n",
       "      'right': {'spInd': 0,\n",
       "       'spVal': 0.661073,\n",
       "       'left': 121.980607,\n",
       "       'right': {'spInd': 0,\n",
       "        'spVal': 0.652462,\n",
       "        'left': 115.687524,\n",
       "        'right': 112.715799}}},\n",
       "     'right': 82.500766},\n",
       "    'right': 140.613941},\n",
       "   'right': {'spInd': 0,\n",
       "    'spVal': 0.613004,\n",
       "    'left': {'spInd': 0,\n",
       "     'spVal': 0.623909,\n",
       "     'left': {'spInd': 0,\n",
       "      'spVal': 0.628061,\n",
       "      'left': {'spInd': 0,\n",
       "       'spVal': 0.637999,\n",
       "       'left': 82.713621,\n",
       "       'right': {'spInd': 0,\n",
       "        'spVal': 0.632691,\n",
       "        'left': 91.656617,\n",
       "        'right': 93.645293}},\n",
       "      'right': {'spInd': 0,\n",
       "       'spVal': 0.624827,\n",
       "       'left': 117.628346,\n",
       "       'right': 105.970743}},\n",
       "     'right': 82.04976400000001},\n",
       "    'right': {'spInd': 0,\n",
       "     'spVal': 0.606417,\n",
       "     'left': 168.180746,\n",
       "     'right': {'spInd': 0,\n",
       "      'spVal': 0.513332,\n",
       "      'left': {'spInd': 0,\n",
       "       'spVal': 0.533511,\n",
       "       'left': {'spInd': 0,\n",
       "        'spVal': 0.548539,\n",
       "        'left': {'spInd': 0,\n",
       "         'spVal': 0.553797,\n",
       "         'left': {'spInd': 0,\n",
       "          'spVal': 0.560301,\n",
       "          'left': {'spInd': 0,\n",
       "           'spVal': 0.599142,\n",
       "           'left': 93.521396,\n",
       "           'right': {'spInd': 0,\n",
       "            'spVal': 0.589806,\n",
       "            'left': 130.378529,\n",
       "            'right': {'spInd': 0,\n",
       "             'spVal': 0.582311,\n",
       "             'left': 111.9849935,\n",
       "             'right': {'spInd': 0,\n",
       "              'spVal': 0.571214,\n",
       "              'left': 82.589328,\n",
       "              'right': {'spInd': 0,\n",
       "               'spVal': 0.569327,\n",
       "               'left': 114.872056,\n",
       "               'right': 108.435392}}}}},\n",
       "          'right': 82.903945},\n",
       "         'right': 129.0624485},\n",
       "        'right': {'spInd': 0,\n",
       "         'spVal': 0.546601,\n",
       "         'left': 83.114502,\n",
       "         'right': {'spInd': 0,\n",
       "          'spVal': 0.537834,\n",
       "          'left': 97.3405265,\n",
       "          'right': 90.995536}}},\n",
       "       'right': {'spInd': 0,\n",
       "        'spVal': 0.51915,\n",
       "        'left': {'spInd': 0,\n",
       "         'spVal': 0.531944,\n",
       "         'left': 129.766743,\n",
       "         'right': 124.795495},\n",
       "        'right': 116.176162}},\n",
       "      'right': {'spInd': 0,\n",
       "       'spVal': 0.508548,\n",
       "       'left': 101.075609,\n",
       "       'right': {'spInd': 0,\n",
       "        'spVal': 0.508542,\n",
       "        'left': 93.292829,\n",
       "        'right': 96.403373}}}}}}},\n",
       " 'right': {'spInd': 0,\n",
       "  'spVal': 0.457563,\n",
       "  'left': {'spInd': 0,\n",
       "   'spVal': 0.465561,\n",
       "   'left': {'spInd': 0,\n",
       "    'spVal': 0.467383,\n",
       "    'left': {'spInd': 0,\n",
       "     'spVal': 0.483803,\n",
       "     'left': {'spInd': 0,\n",
       "      'spVal': 0.487381,\n",
       "      'left': 8.53677,\n",
       "      'right': 27.729263},\n",
       "     'right': 5.224234},\n",
       "    'right': {'spInd': 0,\n",
       "     'spVal': 0.46568,\n",
       "     'left': -9.712925,\n",
       "     'right': -23.777531}},\n",
       "   'right': {'spInd': 0,\n",
       "    'spVal': 0.463241,\n",
       "    'left': 30.051931,\n",
       "    'right': 17.171057}},\n",
       "  'right': {'spInd': 0,\n",
       "   'spVal': 0.455761,\n",
       "   'left': -34.044555,\n",
       "   'right': {'spInd': 0,\n",
       "    'spVal': 0.126833,\n",
       "    'left': {'spInd': 0,\n",
       "     'spVal': 0.130626,\n",
       "     'left': {'spInd': 0,\n",
       "      'spVal': 0.382037,\n",
       "      'left': {'spInd': 0,\n",
       "       'spVal': 0.388789,\n",
       "       'left': {'spInd': 0,\n",
       "        'spVal': 0.437652,\n",
       "        'left': -4.1911745,\n",
       "        'right': {'spInd': 0,\n",
       "         'spVal': 0.412516,\n",
       "         'left': {'spInd': 0,\n",
       "          'spVal': 0.418943,\n",
       "          'left': {'spInd': 0,\n",
       "           'spVal': 0.426711,\n",
       "           'left': {'spInd': 0,\n",
       "            'spVal': 0.428582,\n",
       "            'left': 19.745224,\n",
       "            'right': 15.224266},\n",
       "           'right': -21.594268},\n",
       "          'right': 44.161493},\n",
       "         'right': {'spInd': 0,\n",
       "          'spVal': 0.403228,\n",
       "          'left': -26.419289,\n",
       "          'right': 0.6359300000000001}}},\n",
       "       'right': 23.197474},\n",
       "      'right': {'spInd': 0,\n",
       "       'spVal': 0.335182,\n",
       "       'left': {'spInd': 0,\n",
       "        'spVal': 0.370042,\n",
       "        'left': {'spInd': 0,\n",
       "         'spVal': 0.378965,\n",
       "         'left': -29.007783,\n",
       "         'right': {'spInd': 0,\n",
       "          'spVal': 0.373501,\n",
       "          'left': {'spInd': 0,\n",
       "           'spVal': 0.377383,\n",
       "           'left': 13.583555,\n",
       "           'right': 5.241196},\n",
       "          'right': -8.228297}},\n",
       "        'right': {'spInd': 0,\n",
       "         'spVal': 0.35679,\n",
       "         'left': -32.124495,\n",
       "         'right': {'spInd': 0,\n",
       "          'spVal': 0.350725,\n",
       "          'left': -9.9938275,\n",
       "          'right': -26.851234812500003}}},\n",
       "       'right': {'spInd': 0,\n",
       "        'spVal': 0.324274,\n",
       "        'left': 22.286959625,\n",
       "        'right': {'spInd': 0,\n",
       "         'spVal': 0.309133,\n",
       "         'left': {'spInd': 0,\n",
       "          'spVal': 0.310956,\n",
       "          'left': -20.3973335,\n",
       "          'right': -49.939516},\n",
       "         'right': {'spInd': 0,\n",
       "          'spVal': 0.131833,\n",
       "          'left': {'spInd': 0,\n",
       "           'spVal': 0.138619,\n",
       "           'left': {'spInd': 0,\n",
       "            'spVal': 0.156067,\n",
       "            'left': {'spInd': 0,\n",
       "             'spVal': 0.166765,\n",
       "             'left': {'spInd': 0,\n",
       "              'spVal': 0.193282,\n",
       "              'left': {'spInd': 0,\n",
       "               'spVal': 0.211633,\n",
       "               'left': {'spInd': 0,\n",
       "                'spVal': 0.228473,\n",
       "                'left': {'spInd': 0,\n",
       "                 'spVal': 0.25807,\n",
       "                 'left': {'spInd': 0,\n",
       "                  'spVal': 0.284794,\n",
       "                  'left': {'spInd': 0,\n",
       "                   'spVal': 0.300318,\n",
       "                   'left': 8.814725,\n",
       "                   'right': {'spInd': 0,\n",
       "                    'spVal': 0.297107,\n",
       "                    'left': -18.051318,\n",
       "                    'right': {'spInd': 0,\n",
       "                     'spVal': 0.295993,\n",
       "                     'left': -1.798377,\n",
       "                     'right': {'spInd': 0,\n",
       "                      'spVal': 0.290749,\n",
       "                      'left': -14.988279,\n",
       "                      'right': -14.391613}}}},\n",
       "                  'right': {'spInd': 0,\n",
       "                   'spVal': 0.273863,\n",
       "                   'left': 35.623746,\n",
       "                   'right': {'spInd': 0,\n",
       "                    'spVal': 0.264926,\n",
       "                    'left': -9.457556,\n",
       "                    'right': {'spInd': 0,\n",
       "                     'spVal': 0.264639,\n",
       "                     'left': 5.280579,\n",
       "                     'right': 2.557923}}}},\n",
       "                 'right': {'spInd': 0,\n",
       "                  'spVal': 0.228628,\n",
       "                  'left': {'spInd': 0,\n",
       "                   'spVal': 0.228751,\n",
       "                   'left': -9.601409499999999,\n",
       "                   'right': -30.812912},\n",
       "                  'right': -2.266273}},\n",
       "                'right': 6.099239},\n",
       "               'right': {'spInd': 0,\n",
       "                'spVal': 0.202161,\n",
       "                'left': -16.42737025,\n",
       "                'right': -2.6781805}},\n",
       "              'right': 9.5773855},\n",
       "             'right': {'spInd': 0,\n",
       "              'spVal': 0.156273,\n",
       "              'left': {'spInd': 0,\n",
       "               'spVal': 0.164134,\n",
       "               'left': {'spInd': 0,\n",
       "                'spVal': 0.166431,\n",
       "                'left': -14.740059,\n",
       "                'right': -6.512506},\n",
       "               'right': -27.405211},\n",
       "              'right': 0.225886}},\n",
       "            'right': {'spInd': 0,\n",
       "             'spVal': 0.13988,\n",
       "             'left': 7.557349,\n",
       "             'right': 7.336784}},\n",
       "           'right': -29.087463},\n",
       "          'right': 22.478291}}}}},\n",
       "     'right': -39.524461},\n",
       "    'right': {'spInd': 0,\n",
       "     'spVal': 0.124723,\n",
       "     'left': 22.891675,\n",
       "     'right': {'spInd': 0,\n",
       "      'spVal': 0.085111,\n",
       "      'left': {'spInd': 0,\n",
       "       'spVal': 0.108801,\n",
       "       'left': 6.196516,\n",
       "       'right': {'spInd': 0,\n",
       "        'spVal': 0.10796,\n",
       "        'left': -16.106164,\n",
       "        'right': {'spInd': 0,\n",
       "         'spVal': 0.085873,\n",
       "         'left': -1.293195,\n",
       "         'right': -10.137104}}},\n",
       "      'right': {'spInd': 0,\n",
       "       'spVal': 0.084661,\n",
       "       'left': 37.820659,\n",
       "       'right': {'spInd': 0,\n",
       "        'spVal': 0.080061,\n",
       "        'left': -24.132226,\n",
       "        'right': {'spInd': 0,\n",
       "         'spVal': 0.068373,\n",
       "         'left': 15.824970500000001,\n",
       "         'right': {'spInd': 0,\n",
       "          'spVal': 0.061219,\n",
       "          'left': -15.160836,\n",
       "          'right': {'spInd': 0,\n",
       "           'spVal': 0.044737,\n",
       "           'left': {'spInd': 0,\n",
       "            'spVal': 0.053764,\n",
       "            'left': {'spInd': 0,\n",
       "             'spVal': 0.055862,\n",
       "             'left': 6.695567,\n",
       "             'right': -3.131497},\n",
       "            'right': -13.731698},\n",
       "           'right': 4.091626}}}}}}}}}}}"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myTree=createTree(myMat2,ops=(0,1))\n",
    "myDataTest=loadDataSet(\"./input&code/Ch09/ex2test.txt\")\n",
    "myMat2Test=mat(myDataTest)\n",
    "\n",
    "prune(myTree,myMat2Test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 模型树\n",
    "#### 模型树 简介\n",
    "用树来对数据建模，除了把叶节点简单地设定为常数值之外，还有一种方法是把叶节点设定为分段线性函数，这里所谓的 分段线性（piecewise linear） 是指模型由多个线性片段组成。\n",
    "\n",
    "我们看一下图 9-4 中的数据，如果使用两条直线拟合是否比使用一组常数来建模好呢？答案显而易见。可以设计两条分别从 0.00.3、从 0.31.0 的直线，于是就可以得到两个线性模型。因为数据集里的一部分数据（0.00.3）以某个线性模型建模，而另一部分数据（0.31.0）则以另一个线性模型建模，因此我们说采用了所谓的分段线性模型。\n",
    "\n",
    "决策树相比于其他机器学习算法的优势之一在于结果更易理解。很显然，两条直线比很多节点组成一棵大树更容易解释。模型树的可解释性是它优于回归树的特点之一。另外，模型树也具有更高的预测准确度。\n",
    "\n",
    "![](./image/Ch09.TreeRegression/1.jpg)\n",
    "\n",
    "将之前的回归树的代码稍作修改，就可以在叶节点生成线性模型而不是常数值。下面将利用树生成算法对数据进行划分，且每份切分数据都能很容易被线性模型所表示。这个算法的关键在于误差的计算。\n",
    "\n",
    "那么为了找到最佳切分，应该怎样计算误差呢？前面用于回归树的误差计算方法这里不能再用。稍加变化，对于给定的数据集，应该先用模型来对它进行拟合，然后计算真实的目标值与模型预测值间的差值。最后将这些差值的平方求和就得到了所需的误差。\n",
    "\n",
    "**模型树叶节点生成函数代码**\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 得到模型的ws系数：f(x) = x0 + x1*featrue1+ x3*featrue2 ...\n",
    "# create linear model and return coeficients\n",
    "def modelLeaf(dataSet):\n",
    "    \"\"\"\n",
    "    Desc:\n",
    "        当数据不再需要切分的时候，生成叶节点的模型。\n",
    "    Args:\n",
    "        dataSet -- 输入数据集\n",
    "    Returns:\n",
    "        调用 linearSolve 函数，返回得到的 回归系数ws\n",
    "    \"\"\"\n",
    "    ws, X, Y = linearSolve(dataSet)\n",
    "    return ws\n",
    "\n",
    "\n",
    "# 计算线性模型的误差值\n",
    "def modelErr(dataSet):\n",
    "    \"\"\"\n",
    "    Desc:\n",
    "        在给定数据集上计算误差。\n",
    "    Args:\n",
    "        dataSet -- 输入数据集\n",
    "    Returns:\n",
    "        调用 linearSolve 函数，返回 yHat 和 Y 之间的平方误差。\n",
    "    \"\"\"\n",
    "    ws, X, Y = linearSolve(dataSet)\n",
    "    yHat = X * ws\n",
    "    # print corrcoef(yHat, Y, rowvar=0)\n",
    "    return sum(power(Y - yHat, 2))\n",
    "\n",
    "\n",
    " # helper function used in two places\n",
    "def linearSolve(dataSet):\n",
    "    \"\"\"\n",
    "    Desc:\n",
    "        将数据集格式化成目标变量Y和自变量X，执行简单的线性回归，得到ws\n",
    "    Args:\n",
    "        dataSet -- 输入数据\n",
    "    Returns:\n",
    "        ws -- 执行线性回归的回归系数 \n",
    "        X -- 格式化自变量X\n",
    "        Y -- 格式化目标变量Y\n",
    "    \"\"\"\n",
    "    m, n = shape(dataSet)\n",
    "    # 产生一个关于1的矩阵\n",
    "    X = mat(ones((m, n)))\n",
    "    Y = mat(ones((m, 1)))\n",
    "    # X的0列为1，常数项，用于计算平衡误差\n",
    "    X[:, 1: n] = dataSet[:, 0: n-1]\n",
    "    Y = dataSet[:, -1]\n",
    "\n",
    "    # 转置矩阵*矩阵\n",
    "    xTx = X.T * X\n",
    "    # 如果矩阵的逆不存在，会造成程序异常\n",
    "    if linalg.det(xTx) == 0.0:\n",
    "        raise NameError('This matrix is singular, cannot do inverse,\\ntry increasing the second value of ops')\n",
    "    # 最小二乘法求最优解:  w0*1+w1*x1=y\n",
    "    ws = xTx.I * (X.T * Y)\n",
    "    return ws, X, Y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD8CAYAAABn919SAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAGOZJREFUeJzt3X2MXFd5x/Hfs2NvydhuwbNLRQmeBfFSoggJWFXQSjStoYpclPQPhEBr19hRLXslarWqBNX+0aqV1aqvclVsY1E7rvc2QKO2RIhWkJQoFSJpN00KIbwWvCaFkrWXItKleLN++seZYWdnZ+beuXPnzsyd70da7cvc2TnXa//2+LnPOdfcXQCA0Tcx6AEAALJBoANAQRDoAFAQBDoAFASBDgAFQaADQEEQ6ABQEAQ6ABQEgQ4ABbEjzxebmprymZmZPF8SAEbe448/fs3dp+OOyzXQZ2ZmtLS0lOdLAsDIM7PlJMdRcgGAgiDQAaAgCHQAKIjYQDezC2b2rJk91fC1PzazL5nZ58zs783shf0dJgAgTpIZ+r2S7mz62qck3e7ur5P0FUm/nfG4AABdig10d39E0mrT1z7p7s/XPn1U0q19GBsAjJ4okmZmpImJ8D6KcnvpLNoWj0r6SAbfBwBG2/y8dO6cVL8T3PKydOxY+Hhuru8v39NFUTNbkPS8pLa/gszsmJktmdnSyspKLy8HAMMriraGed3amnT4cC4z9tSBbmaHJb1d0px3uDGpu59391l3n52ejl3oBACjaWFhe5jXbWyEx+oz9j6FeqpAN7M7Jb1P0l3uvpbtkABgBF29muy4tbUQ/n2QpG3xPkmflfQaM3vGzO6R9JeS9kj6lJk9aWbn+jI6ABgFURRKKkklDf8uxV4Udfd3t/jyX/VhLAAwepovhCaxb19fhsJKUQBIq92F0DinTvVlOAQ6AKTV6UJoO5VK31oYCXQASKvbWni5LJ0+3Z+xiEAHgO7VV4N2MzuvVqXz5/u6wCjXG1wAwMiLotBLvpawY3tyUrpwYfhXigLA2FlYaB/mlYq0a9fWz3MKc4kZOgB0p13d3Ey6di3fsTRhhg4A3WjXQ96n3vJuEOgA0I1Tp0K3SqNyuW+95d0g0AGgWeOe5lNT4a2+W6IUulWq1VBmyaF7JSlq6ADQqLmL5fr1zcfquyWePy9duTKQ4XXCDB0AGnXqYpH6ultirwh0AGiUZPVnn3ZL7BWBDgCNknSrDEFHSysEOgA0atXF0shsKDpaWiHQAYyHxs6VTvf2nJsLFz0rle2PmUnHjw9FR0srBDqA4qt3riwvb97b88iRre2IjQE/NxdWfS4ubm1PvHxZOnNmYKcRxzrc3zlzs7OzvrS0lNvrAYCkENjLy52PKZeHpp+8mZk97u6zcccxQwdQfEm6Uoa4HTEpAh1AcXW7b/mQtiMmxUpRAMUURaFOvr6e/Dl79/ZvPDlghg6gmE6e7C7MC4BAB1BMjXuwJLW6mv04ckSgAyiOxl7zNIZ0BWhS1NABFEO39/psNiR7mveCGTqAYojbJbGTIdrTvBfM0AEUQ5qWw0pl4PcBzRIzdADF0K7+bSadONH6tnGnT/d/XDki0AGMnlYbbb3yla2PdQ/llMOHh/K2cVmi5AJgtDRf/FxeDmG9sdH+ORsb0qVLhQzxRszQAYyWVhc/O4V5XQH2aolDoAMYLXG7JnYy4nu1xCHQAYyOKAo18LRGfOFQHAIdwOhYWEi+c2KzAiwcikOgAxhOrTpZui2ZlErhfUG7WprR5QJg+LTqZDl2LGxv22nTLTPp5s18xjiEmKEDGD6tOlnqnzcvEGpU8Bp5nNhAN7MLZvasmT3V8LW9ZvYpM/tq7f2L+jtMAGOlXWlldTWUTiqV7Y+NQY08TpIZ+r2S7mz62vslPeTur5L0UO1zAEivsWbebvvbfftCHfzaNWlxsfArP7sVW0N390fMbKbpy3dLuqP28SVJD0t6X4bjAjBO5uels2c3P2+1UKh5Bj43N/YB3ixtDf0n3f3bklR7/+LshgRgrETR1jBvpVJhBp5A3y+KmtkxM1sys6WVlZV+vxyAUZN0OT5hHittoH/HzF4iSbX3z7Y70N3Pu/usu89OT0+nfDkAhZWktzzN/UHHUNpAf0DS4drHhyV9LJvhABg7Y95qmKUkbYv3SfqspNeY2TNmdo+kP5T0NjP7qqS31T4HgHjNK0APHJAmJwc9qkJI0uXy7jYP7c94LACKrtUK0HPnpNe+Vnr66fbPa9V3jm1YKQogPydPbl8B6t45zHfuLNyt4vqFQAeQjyhKd3Hz4kU6XBIi0AHkI83dgqpVwrwLBDqA/mi++NntnYbYm6VrBDqA7EWRdORICHH35GHO3iw9YT90ANk7eVJaX+/uOdWqdOVKX4YzLpihA8hetxc/Ka9kgkAHMFiUVzJDyQVAb6IodLBcvRqW8R84kPy5ZpRZMkSgA0iv3crPpNjHJVOUXACk1+ren+7JnkvdPHMEOoDu1XvMu+0tNwvvqZv3BSUXAN1pLrN04/JlQryPmKED6E6rMksSLOPvOwIdQHeS3GGoXlqpo16eCwIdQHfiOlPKZen4cZbxDwA1dADJvfWtrS+EmoXulmo1zMQJ74Fghg6gs3pHi5n00EPbH5+cDBc73cMiIcJ8YJihA2gtisImW3H7sty4sbnXOWE+UAQ6gO26bU1cXg7HS4T6AFFyAbBdmtbEtbV0dyVCZgh0ANslaU3M8nnIBIEOYLu0m2ax2dZAEegANjXu0dK8OKhRpRL6zRuxeGjgCHQAQf1CaL3PvN2uieWydPp0WCzE4qGhQpcLgKDdhdBKRdq9e/MGFo0LhwjwoUKgAwiz83Zb4a6uSteu5TsepELJBRhXjStADx1qf9zevbkNCb1hhg6Mm1YrQJPeZQhDjUAHxkmam1OsrvZvPMgUJRdgnKRZAUpv+cgg0IFxkuYeoPSWjwwCHRgXUdR5sVAzs3CjCloTRwaBDoyLhYX4i5+VyuZCocuXpTNn8hkbMsFFUWBcJCm30G8+0pihA+OiVOr8eLWazzjQNwQ6UET1RUMTE+F9FEkbG+2PZ2OtQugp0M3sN8zsC2b2lJndZ2YvyGpgAGK0Cu0okqampIMHQ4nFffNuQpVK6+9TKrGxVkGkrqGb2Usl/bqk29z9B2b2UUnvknRvRmMD0E7zAqHlZeno0RDg6+vbj19bk265JczEG/vQy2XCvEB6LbnskHSLme2QVJb0rd6HBCBWqwVCN260DvO61VW2vC241DN0d/8vM/sTSVcl/UDSJ939k5mNDEB7aW71tm9fCG8CvLBSz9DN7EWS7pb0ckk/JWmXmR1scdwxM1sys6WVlZX0IwWwqdvl+Fz0HAu9lFzeKukb7r7i7uuS/k7SzzYf5O7n3X3W3Wenp6d7eDkAP3LqVLgYmkSlQmllTPSysOiqpDeZWVmh5LJf0lImowLQXhSFJfk3b8YfW6mwWGiMpJ6hu/tjku6X9O+SPl/7XuczGheAVurdLc89F39s/d6fGBs9dbm4+++4+0+7++3ufsjdf5jVwICx1aq/vC7p9rd0sIwlVooCw6Q+A29cFHTkSFgsZJZsP5bFRenKFcJ8DBHowDBpNQNfX996u7hO9u8nyMcYgQ4MkzT95VKYvZ84IT34YLbjwUgh0IFhkuZ2b4uLoeOFvcvHHoEODJNTp0J3SlLVKiUW/Ag3uACGST2cD25bdL0dqz/RhBk6MGzm5uJvNkFbIlog0IFh1Kr0Ui6Herk7bYloiUAHBql5EdH8fHh/6FDYv7zxps3MyBGDGjowKK1uUnH27Obj16+HWfnlywQ5EmGGDgzKyZPxy/jX1sJiIyABAh0YhPn55Ks/0y42wtgh0IG8RdHW0kqcNIuNMJYIdCAv9QugSXrM6+g1RxcIdKBfGjtYpqbCrolJdks0C+/pbEGX6HIB+qG5gyVpvbxSCTelIMSRAoEO9EPSG1E02r2b28WhJ5RcgH7otjNlclI6d64/Y8HYINCBfti7N/mx1ap04QJlFvSMkgswSNVq2JcFyAAzdCBrUcSiIQwEgQ70otXmWseOJX8+i4aQIUouQFqtNtc6dy5sb5vEzp0sGkKmmKEDabVqTewU5rt3b35cqUgXL3IhFJlihg6k1U39m4ufyAEzdCCtdvXv+tL9OvZjQU4IdKBb9Quhy8utw/v48TAj505DyBklF6AbzRdCG2vm1WqYiRPeGBBm6EA32u3RYkaYY+AIdCCJxjJLK+7cKg4DR8kFiNNcZmmHVZ8YMGboQJykW+Gy6hMDRqAD7cSVWRrRmoghQMkFaGV+Pvky/lKJ1kQMBWboQKMoCvf/PHs2WZiXy9KlS4Q5hgIzdIy3KJJOnky+3W0jZuYYMgQ6xlcUSUePSjdudP/ccpkwx9DpqeRiZi80s/vN7Etm9kUze3NWAwP6onH/8sOH04V5pUKYYyj1OkM/Lemf3P0dZjYpqZzBmID+aO4n39hI93127ybMMZRSB7qZ/bikt0h6jyS5+w1JKaY7QE6S9pPHYQERhlQvJZdXSFqRdNHMnjCzD5nZrozGBWQvqyBmARGGVC+BvkPSGySddffXS/pfSe9vPsjMjpnZkpktrays9PByQAqNNfOJFH/d2dscI6SXQH9G0jPu/ljt8/sVAn4Ldz/v7rPuPjs9Pd3DywFdqPeTHzwYVnq6t66ZT06Ge3u2wt7mGDGpa+ju/t9m9k0ze427f1nSfklPZzc0IKW4zbRKJenmzVA6qc+2FxZC8JdKIfjZ2xwjqNcul/dKimodLl+XdKT3IQE9irv4efNmeGtEcKMAeupDd/cna+WU17n7r7j7d7MaGJBa3MXPiYkwiwcKhr1cUDxxXSgbG6EkQ6ijYAh0FM+pU+GCZidra9xhCIVDoKN45ubCsv5SqfNxLBBCwRDoKJ4oClvaxi3tZ4EQCoZARzE0b7oVt8SfBUIoIAIdo29+Xjp0qPMCojoWCKHA2A8doy2Kkt8qrlqVrlzp+5CAQWGGjtG2sJD8VnGUWFBwBDpGW6dOlVKJEgvGCiUXjLZ9+0LtvJkZN2/G2GGGjtEVRdJzz23/ulnYJZEwx5hhho7R1G5HxUpFOn2aMMdYYoaO0dRuR0Xu94kxRqBjNLW7GMpyfowxAh2joXEl6MyMtHdv6+NYzo8xRg0dwyuKNu8kZLbZb768HG4bNzkp3bixeTy95hhzzNAxeM2z7ygKb0ePbrYkNi8eWl+X9uzhfp9AA2boGKzmbpXl5XBj58YZeTurq9K1a/0fIzAimKFjsNp1qyRZzk+9HNiCQEf+GkssrVZ5JkG9HNiGkgvy1W5BUDeq1RDm1MuBLQh05KtdiSWpSoUtcIE2KLkgX70s/Nm5MyzrB9ASgY58pb2QWalIFy9SZgE6INCRrwMH4o+pVLb2ly8uhvZEwhzoiBo68vWJT8Qf8853SmfO9H8sQMEwQ0e+ktTQk4Q+gG0IdOQrSQ2dHROBVAh05KO+mCjJQiJWgAKpUENHf0WRdPKkdP16suNZAQqkxgwd2Wpc1j81FXZMTBrm7JgI9IQZOrLTvKw/aZBLoUWRFaBAT5ihIzu9LOunbg70jEBH77q54NkKdXMgEwQ6ejM/Lx061F2Y794dVoNypyEgU9TQkV4USefOJbsZhVkoq7DtLdA3BDrSW1hIFubVKhc8gRz0XHIxs5KZPWFmH89iQBghSVZ0Uh8HcpNFDf2kpC9m8H3GVxSFnm2z8DY1Fb7Wj9ep94jPzPT2GkmeWypRHwdy1FOgm9mtkn5Z0oeyGc4YiiLpyJGtPdvXr4cFOVmGer1HfHk5lEmWl8PnaV6j/r3iyi03bxLmQI7Mk9RA2z3Z7H5JfyBpj6Tfcve3dzp+dnbWl5aWUr9eIXVq96tUwj7g/XydNPXtqalki4aonQOZMLPH3X027rjUM3Qze7ukZ9398ZjjjpnZkpktrayspH254upUh75+PbtZervX6bZ3PIqShTm1cyB3vZRcfk7SXWZ2RdKHJf2imS02H+Tu59191t1np6ene3i5AoqiUM/uZGGh8/OT1sQ7rcQslUI/eRKdxlNXqVA7BwbB3Xt+k3SHpI/HHffGN77RC21x0b1adTcL7xcXOx87OekeKtHt38zaP79c3n6s5F6phLfGcSwubj7e7u3Eifjz6fQ9JiY6nzOAVCQteYIs7qmGXmdmd2jca+jNG1NJoezQbqaatA5dqYSVlVevSnv3hq+troZZ+cZGNmOvK5Wk558PH8/Pb180VC5Lt9zSftxm4UIogEz1vYbeyN0fjgvzoZFl616jVhtTra1JBw+G8J6a2vqaScJ8507p+9/f7Ey5fj28uWcf5lL4nlEk7dkjnT27vYulfn5mrZ/PBlvAQI3XXi6N+460at1LEvbtjom7uFkP4vprJlEqSTduJD+/Xk1MhHbJ555rf8zqqnT8+PZQ5yIoMHhJ6jJZvaWqoXdTl+703Eqlfe23VAr14+aadLm89fVa1a0ba9Zx9fBhf9u1K/6YarX3nwuArihhDX24A71dgNYvzHUKknbP7XTxMS7AJibaP3/HjsEHcr/fzAhuYACSBvpwl1za3TDBPbxfXg41arPtJZJub7ZQ/57Nrl4N3/fo0c4X/OoXE7NkFkoZeSmVOj9+/DitiMAQG+5AT7L5U11zPbyb53YyMRFucpxnLbvu+PHQJVOtbu7z0k61Kp04sf0XwI4dm88rlcIx7WxsSJOTrR87cUI6c6a78QPI1XAHerddE2tr0uHDIYTjFuwktbHR3b0xs7J/fwjQubmwfL7T/w7q9+M8c2brL4BqVbr33vBc9/C/iDNnwtdbqValCxdCq2RdpSItLhLmwAgY7kA/dar7ksPGRgivfrT19SKunFEqbYbw4qL04IPbj2n3C67x642/AK5caV0iafXnWu9SmZsL+8fUK+fXrlFmAUbEcAf63FyYce7ePeiRdFaphJ7xdsrlUA5q98upXJYuXeocwlLnIO5G/c+1cSbPUn1g5A13oNfltfqwXN5abmhUqbQuRdRnsRcvbgZk/djGsGwsh0ibM/ZuwjTLIE4ykwcwUjJZ+p9UqqX/vdxNvhuVinT6dPi4myX8ANBnuS7976tO3SqNNed2M+tdu7aXKSYnt86gFxc3a8WUIwCMqOG/SfS+fclvzHDkiLS+vvn5zp3SBz8YPl5YCL8cktx5vh7sADBChj/QT51qXQJpvhBYD+B2wU1AAyi44Q/0uKBuPpbgBjCmhj/QJYIaABIY/ouiAIBECHQAKAgCHQAKgkAHgIIg0AGgIHJd+m9mK5LSrOOfknQt4+EMO855fIzjeXPO3am6+3TcQbkGelpmtpRkH4Mi4ZzHxzieN+fcH5RcAKAgCHQAKIhRCfTzgx7AAHDO42Mcz5tz7oORqKEDAOKNygwdABBjqALdzO40sy+b2dfM7P0tHv8xM/tI7fHHzGwm/1FmK8E5/6aZPW1mnzOzh8ysOohxZinunBuOe4eZuZmNfDdEknM2s3fWftZfMLO/yXuMWUvwd3ufmX3azJ6o/f0+MIhxZsnMLpjZs2b2VJvHzcz+ovZn8jkze0OmA3D3oXiTVJL0n5JeIWlS0n9Iuq3pmHlJ52ofv0vSRwY97hzO+RcklWsfnxiHc64dt0fSI5IelTQ76HHn8HN+laQnJL2o9vmLBz3uHM75vKQTtY9vk3Rl0OPO4LzfIukNkp5q8/gBSf8oySS9SdJjWb7+MM3Qf0bS19z96+5+Q9KHJd3ddMzdki7VPr5f0n4zsxzHmLXYc3b3T7t7/e4ej0q6NecxZi3Jz1mSfl/SH0n6vzwH1ydJzvnXJH3A3b8rSe7+bM5jzFqSc3ZJP177+CckfSvH8fWFuz8iabXDIXdL+msPHpX0QjN7SVavP0yB/lJJ32z4/Jna11oe4+7PS/qepDY3Ex0JSc650T0Kv91HWew5m9nrJb3M3T+e58D6KMnP+dWSXm1mnzGzR83sztxG1x9Jzvl3JR00s2ckfULSe/MZ2kB1+2++K8N0g4tWM+3mFpwkx4ySxOdjZgclzUr6+b6OqP86nrOZTUj6c0nvyWtAOUjyc96hUHa5Q+F/Yf9iZre7+//0eWz9kuSc3y3pXnf/UzN7s6TLtXO+2f/hDUxfM2yYZujPSHpZw+e3avt/wX50jJntUPhvWqf/3gy7JOcsM3urpAVJd7n7D3MaW7/EnfMeSbdLetjMrijUGR8Y8QujSf9uf8zd1939G5K+rBDwoyrJOd8j6aOS5O6flfQChf1OiizRv/m0hinQ/03Sq8zs5WY2qXDR84GmYx6QdLj28Tsk/bPXrjSMqNhzrpUfPqgQ5qNeV5Viztndv+fuU+4+4+4zCtcN7nL3pcEMNxNJ/m7/g8IFcJnZlEIJ5uu5jjJbSc75qqT9kmRmr1UI9JVcR5m/ByT9aq3b5U2Svufu387suw/6qnCLK8BfUbg6vlD72u8p/IOWwg/8byV9TdK/SnrFoMecwzk/KOk7kp6svT0w6DH3+5ybjn1YI97lkvDnbJL+TNLTkj4v6V2DHnMO53ybpM8odMA8KemXBj3mDM75PknflrSuMBu/R9JxSccbfs4fqP2ZfD7rv9usFAWAghimkgsAoAcEOgAUBIEOAAVBoANAQRDoAFAQBDoAFASBDgAFQaADQEH8PzyEfgM9PR6WAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "({'spInd': 0, 'spVal': 0.285477, 'left': matrix([[1.69855694e-03],\n",
       "          [1.19647739e+01]]), 'right': matrix([[3.46877936],\n",
       "          [1.18521743]])}, None)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myMat3=mat(loadDataSet('./input&code/Ch09/exp2.txt'))\n",
    "mM3=createTree(myMat3,modelLeaf,modelErr,(1,10))\n",
    "import matplotlib.pyplot as plt  \n",
    "plt.plot(myMat3[:,0],myMat3[:,1],'ro') \n",
    "mM3,plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  树回归与标准回归的比较\n",
    "### 项目概述\n",
    "前面介绍了模型树、回归树和一般的回归方法，下面测试一下哪个模型最好。\n",
    "\n",
    "这些模型将在某个数据上进行测试，该数据涉及人的智力水平和自行车的速度的关系。当然，数据是假的。\n",
    "\n",
    "\n",
    "数据格式：\n",
    "```\n",
    "3.000000\t46.852122\n",
    "23.000000\t178.676107\n",
    "0.000000\t86.154024\n",
    "6.000000\t68.707614\n",
    "15.000000\t139.737693\n",
    "```\n",
    "![](./image/Ch09.TreeRegression/2.jpg)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 回归树测试案例\n",
    "# 为了和 modelTreeEval() 保持一致，保留两个输入参数\n",
    "def regTreeEval(model, inDat):\n",
    "    \"\"\"\n",
    "    Desc:\n",
    "        对 回归树 进行预测\n",
    "    Args:\n",
    "        model -- 指定模型，可选值为 回归树模型 或者 模型树模型，这里为回归树\n",
    "        inDat -- 输入的测试数据\n",
    "    Returns:\n",
    "        float(model) -- 将输入的模型数据转换为 浮点数 返回\n",
    "    \"\"\"\n",
    "    return float(model)\n",
    "\n",
    "\n",
    "# 模型树测试案例\n",
    "# 对输入数据进行格式化处理，在原数据矩阵上增加第0列，元素的值都是1，\n",
    "# 也就是增加偏移值，和我们之前的简单线性回归是一个套路，增加一个偏移量\n",
    "def modelTreeEval(model, inDat):\n",
    "    \"\"\"\n",
    "    Desc:\n",
    "        对 模型树 进行预测\n",
    "    Args:\n",
    "        model -- 输入模型，可选值为 回归树模型 或者 模型树模型，这里为模型树模型\n",
    "        inDat -- 输入的测试数据\n",
    "    Returns:\n",
    "        float(X * model) -- 将测试数据乘以 回归系数 得到一个预测值 ，转化为 浮点数 返回\n",
    "    \"\"\"\n",
    "    n = shape(inDat)[1]\n",
    "    X = mat(ones((1, n+1)))\n",
    "    X[:, 1: n+1] = inDat\n",
    "    # print X, model\n",
    "    return float(X * model)\n",
    "\n",
    "\n",
    "# 计算预测的结果\n",
    "# 在给定树结构的情况下，对于单个数据点，该函数会给出一个预测值。\n",
    "# modelEval是对叶节点进行预测的函数引用，指定树的类型，以便在叶节点上调用合适的模型。\n",
    "# 此函数自顶向下遍历整棵树，直到命中叶节点为止，一旦到达叶节点，它就会在输入数据上\n",
    "# 调用modelEval()函数，该函数的默认值为regTreeEval()\n",
    "def treeForeCast(tree, inData, modelEval=regTreeEval):\n",
    "    \"\"\"\n",
    "    Desc:\n",
    "        对特定模型的树进行预测，可以是 回归树 也可以是 模型树\n",
    "    Args:\n",
    "        tree -- 已经训练好的树的模型\n",
    "        inData -- 输入的测试数据\n",
    "        modelEval -- 预测的树的模型类型，可选值为 regTreeEval（回归树） 或 modelTreeEval（模型树），默认为回归树\n",
    "    Returns:\n",
    "        返回预测值\n",
    "    \"\"\"\n",
    "    if not isTree(tree):\n",
    "        return modelEval(tree, inData)\n",
    "    if inData[tree['spInd']] <= tree['spVal']:\n",
    "        if isTree(tree['left']):\n",
    "            return treeForeCast(tree['left'], inData, modelEval)\n",
    "        else:\n",
    "            return modelEval(tree['left'], inData)\n",
    "    else:\n",
    "        if isTree(tree['right']):\n",
    "            return treeForeCast(tree['right'], inData, modelEval)\n",
    "        else:\n",
    "            return modelEval(tree['right'], inData)\n",
    "\n",
    "\n",
    "# 预测结果\n",
    "def createForeCast(tree, testData, modelEval=regTreeEval):\n",
    "    \"\"\"\n",
    "    Desc:\n",
    "        调用 treeForeCast ，对特定模型的树进行预测，可以是 回归树 也可以是 模型树\n",
    "    Args:\n",
    "        tree -- 已经训练好的树的模型\n",
    "        inData -- 输入的测试数据\n",
    "        modelEval -- 预测的树的模型类型，可选值为 regTreeEval（回归树） 或 modelTreeEval（模型树），默认为回归树\n",
    "    Returns:\n",
    "        返回预测值矩阵\n",
    "    \"\"\"\n",
    "    m = len(testData)\n",
    "    yHat = mat(zeros((m, 1)))\n",
    "    # print yHat\n",
    "    for i in range(m):\n",
    "        yHat[i, 0] = treeForeCast(tree, mat(testData[i]), modelEval)\n",
    "        # print \"yHat==>\", yHat[i, 0]\n",
    "    return yHat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--------------\n",
      "\n",
      "回归树: -0.8775461454371768\n",
      "模型树: -0.962132224495778\n",
      "线性回归: 0.9434684235674766\n"
     ]
    }
   ],
   "source": [
    "trainMat = mat(loadDataSet('./input&code/Ch09/bikeSpeedVsIq_train.txt'))\n",
    "testMat = mat(loadDataSet('./input&code/Ch09/bikeSpeedVsIq_test.txt'))\n",
    "    # # 回归树\n",
    "myTree1 = createTree(trainMat, ops=(1, 20))\n",
    "# print(myTree1)\n",
    "yHat1 = createForeCast(myTree1, testMat[:, 0])\n",
    "print(\"--------------\\n\")\n",
    "    # print yHat1\n",
    "    # print \"ssss==>\", testMat[:, 1]\n",
    "print(\"回归树:\", corrcoef(yHat1, testMat[:, 1],rowvar=0)[0, 1])\n",
    "\n",
    "    # 模型树\n",
    "myTree2 = createTree(trainMat, modelLeaf, modelErr, ops=(1, 20))\n",
    "yHat2 = createForeCast(myTree2, testMat[:, 0], modelTreeEval)\n",
    "# print(myTree2)\n",
    "print(\"模型树:\", corrcoef(yHat2, testMat[:, 1],rowvar=0)[0, 1])\n",
    "\n",
    "    # 线性回归\n",
    "ws, X, Y = linearSolve(trainMat)\n",
    "# print(ws)\n",
    "m = len(testMat[:, 0])\n",
    "yHat3 = mat(zeros((m, 1)))\n",
    "for i in range(shape(testMat)[0]):\n",
    "    yHat3[i] = testMat[i, 0]*ws[1, 0] + ws[0, 0]\n",
    "print(\"线性回归:\", corrcoef(yHat3, testMat[:, 1],rowvar=0)[0, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 附加 Python 中 GUI 的使用\n",
    "### 使用 Python 的 Tkinter 库创建 GUI\n",
    "如果能让用户不需要任何指令就可以按照他们自己的方式来分析数据，就不需要对数据做出过多解释。其中一个能同时支持数据呈现和用户交互的方式就是构建一个图形用户界面(GUI，Graphical User Interface)，如图9-7所示。\n",
    "\n",
    "![](./image/Ch09.TreeRegression/3.jpg)\n",
    "\n",
    "\n",
    "### 用 Tkinter 创建 GUI\n",
    "Python 有很多 GUI 框架，其中一个易于使用的 Tkinter，是随 Python 的标准版编译版本发布的。Tkinter 可以在 Windows、Mac OS和大多数的 Linux 平台上使用。\n",
    "\n",
    "### 集成 Matplotlib 和 Tkinter\n",
    "MatPlotlib 的构建程序包含一个前端，也就是面向用户的一些代码，如 plot() 和 scatter() 方法等。事实上，它同时创建了一个后端，用于实现绘图和不同应用之间接口。\n",
    "\n",
    "通过改变后端可以将图像绘制在PNG、PDF、SVG等格式的文件上。下面将设置后端为 TkAgg (Agg 是一个 C++ 的库，可以从图像创建光栅图)。TkAgg可以在所选GUI框架上调用Agg，把 Agg 呈现在画布上。我们可以在Tk的GUI上放置一个画布，并用 .grid()来调整布局。\n",
    "\n",
    "### 用treeExplore 的GUI构建的模型树示例图\n",
    "\n",
    "![](./image/Ch09.TreeRegression/4.jpg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "import _tkinter\n",
    "import tkinter\n",
    "tkinter._test()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import _tkinter\n",
    "import tkinter\n",
    "from tkinter import *\n",
    "root=Tk() #创建一个空的tk窗口，注意弹出后不要关闭，然后继续输入下一行\n",
    "myLabel=Label(root,text=\"hello,Tkinter!\")\n",
    "myLabel.grid()#输入以上两行，框内显示文字\n",
    "#使程序完整：\n",
    "root.mainloop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 这里简单介绍一下Tkinter： \n",
    "Tkinter是由很多组件（Widget）组成的，包括文本框，按钮，标签（刚才用的Label）等。其中.grid()是把组件的放入一种二维表格的布局管理器中。默认0行0列。 \n",
    "下面将tk与matplotlib集成"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\ipykernel_launcher.py:7: UserWarning: \n",
      "This call to matplotlib.use() has no effect because the backend has already\n",
      "been chosen; matplotlib.use() must be called *before* pylab, matplotlib.pyplot,\n",
      "or matplotlib.backends is imported for the first time.\n",
      "\n",
      "The backend was *originally* set to 'module://ipykernel.pylab.backend_inline' by the following code:\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\runpy.py\", line 193, in _run_module_as_main\n",
      "    \"__main__\", mod_spec)\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\runpy.py\", line 85, in _run_code\n",
      "    exec(code, run_globals)\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\ipykernel_launcher.py\", line 16, in <module>\n",
      "    app.launch_new_instance()\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\traitlets\\config\\application.py\", line 658, in launch_instance\n",
      "    app.start()\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\ipykernel\\kernelapp.py\", line 478, in start\n",
      "    self.io_loop.start()\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\zmq\\eventloop\\ioloop.py\", line 177, in start\n",
      "    super(ZMQIOLoop, self).start()\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\tornado\\ioloop.py\", line 888, in start\n",
      "    handler_func(fd_obj, events)\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\tornado\\stack_context.py\", line 277, in null_wrapper\n",
      "    return fn(*args, **kwargs)\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\zmq\\eventloop\\zmqstream.py\", line 440, in _handle_events\n",
      "    self._handle_recv()\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\zmq\\eventloop\\zmqstream.py\", line 472, in _handle_recv\n",
      "    self._run_callback(callback, msg)\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\zmq\\eventloop\\zmqstream.py\", line 414, in _run_callback\n",
      "    callback(*args, **kwargs)\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\tornado\\stack_context.py\", line 277, in null_wrapper\n",
      "    return fn(*args, **kwargs)\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\ipykernel\\kernelbase.py\", line 283, in dispatcher\n",
      "    return self.dispatch_shell(stream, msg)\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\ipykernel\\kernelbase.py\", line 233, in dispatch_shell\n",
      "    handler(stream, idents, msg)\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\ipykernel\\kernelbase.py\", line 399, in execute_request\n",
      "    user_expressions, allow_stdin)\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\ipykernel\\ipkernel.py\", line 208, in do_execute\n",
      "    res = shell.run_cell(code, store_history=store_history, silent=silent)\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\ipykernel\\zmqshell.py\", line 537, in run_cell\n",
      "    return super(ZMQInteractiveShell, self).run_cell(*args, **kwargs)\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\IPython\\core\\interactiveshell.py\", line 2666, in run_cell\n",
      "    self.events.trigger('post_run_cell', result)\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\IPython\\core\\events.py\", line 88, in trigger\n",
      "    func(*args, **kwargs)\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\ipykernel\\pylab\\backend_inline.py\", line 160, in configure_once\n",
      "    activate_matplotlib(backend)\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\IPython\\core\\pylabtools.py\", line 311, in activate_matplotlib\n",
      "    matplotlib.pyplot.switch_backend(backend)\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\matplotlib\\pyplot.py\", line 231, in switch_backend\n",
      "    matplotlib.use(newbackend, warn=False, force=True)\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\matplotlib\\__init__.py\", line 1410, in use\n",
      "    reload(sys.modules['matplotlib.backends'])\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\importlib\\__init__.py\", line 166, in reload\n",
      "    _bootstrap._exec(spec, module)\n",
      "  File \"C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\matplotlib\\backends\\__init__.py\", line 16, in <module>\n",
      "    line for line in traceback.format_stack()\n",
      "\n",
      "\n",
      "  import sys\n",
      "C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\ipykernel_launcher.py:55: MatplotlibDeprecationWarning: The FigureCanvasTk.show function was deprecated in version 2.2. Use FigureCanvasTk.draw instead.\n",
      "C:\\Users\\x1c\\Anaconda3\\lib\\site-packages\\ipykernel_launcher.py:25: MatplotlibDeprecationWarning: The FigureCanvasTk.show function was deprecated in version 2.2. Use FigureCanvasTk.draw instead.\n"
     ]
    }
   ],
   "source": [
    "from numpy import *\n",
    "\n",
    "from tkinter import *\n",
    "# import regTrees\n",
    "import matplotlib\n",
    "\n",
    "matplotlib.use('TkAgg') #设置后端TkAgg\n",
    "#将TkAgg和matplotlib链接起来\n",
    "from matplotlib.backends.backend_tkagg import FigureCanvasTkAgg\n",
    "from matplotlib.figure import Figure\n",
    "\n",
    "\n",
    "def reDraw(tolS, tolN):\n",
    "    reDraw.f.clf()  #清空之前的图像\n",
    "    reDraw.a = reDraw.f.add_subplot(111)#重新添加新图\n",
    "    if chkBtnVar.get():#检查选框model tree是否被选中\n",
    "        if tolN < 2: tolN = 2\n",
    "        myTree = createTree(reDraw.rawDat, modelLeaf,modelErr, (tolS, tolN))\n",
    "        yHat = createForeCast(myTree, reDraw.testDat, modelTreeEval)\n",
    "    else:\n",
    "        myTree = createTree(reDraw.rawDat, ops=(tolS, tolN))\n",
    "        yHat = createForeCast(myTree, reDraw.testDat)\n",
    "    reDraw.a.scatter(reDraw.rawDat[:, 0].tolist(), reDraw.rawDat[:, 1].tolist(), s=5)    # 绘制真实值\n",
    "    reDraw.a.plot(reDraw.testDat, yHat, linewidth=2.0)  # 绘制预测值\n",
    "    reDraw.canvas.show()\n",
    "\n",
    "\n",
    "def getInputs():#获取输入\n",
    "    try:#期望输入是整数\n",
    "        tolN = int(tolNentry.get())\n",
    "    except:#清楚错误用默认值替换\n",
    "        tolN = 10\n",
    "        print(\"enter Integer for tolN\")\n",
    "        tolNentry.delete(0, END)\n",
    "        tolNentry.insert(0, '10')\n",
    "    try:#期望输入是浮点数\n",
    "        tolS = float(tolSentry.get())\n",
    "    except:\n",
    "        tolS = 1.0\n",
    "        print(\"enter Float for tolS\")\n",
    "        tolSentry.delete(0, END)\n",
    "        tolSentry.insert(0, '1.0')\n",
    "    return tolN, tolS\n",
    "\n",
    "\n",
    "\n",
    "def drawNewTree():\n",
    "    tolN, tolS = getInputs()  # 从输入文本框中获取参数\n",
    "    reDraw(tolS, tolN)  #绘制图\n",
    "    \n",
    "root = Tk()\n",
    "\n",
    "reDraw.f = Figure(figsize=(5, 4), dpi=100)  # 创建画布\n",
    "reDraw.canvas = FigureCanvasTkAgg(reDraw.f, master=root)\n",
    "reDraw.canvas.show()\n",
    "reDraw.canvas.get_tk_widget().grid(row=0, columnspan=3)\n",
    "\n",
    "Label(root, text=\"tolN\").grid(row=1, column=0)\n",
    "tolNentry = Entry(root)\n",
    "tolNentry.grid(row=1, column=1)\n",
    "tolNentry.insert(0, '10')\n",
    "Label(root, text=\"tolS\").grid(row=2, column=0)\n",
    "tolSentry = Entry(root)\n",
    "tolSentry.grid(row=2, column=1)\n",
    "tolSentry.insert(0, '1.0')\n",
    "Button(root, text=\"ReDraw\", command=drawNewTree).grid(row=1, column=2, rowspan=3)\n",
    "chkBtnVar = IntVar()\n",
    "chkBtn = Checkbutton(root, text=\"Model Tree\", variable=chkBtnVar)\n",
    "chkBtn.grid(row=3, column=0, columnspan=2)\n",
    "\n",
    "reDraw.rawDat = mat(loadDataSet('./input&code/Ch09/sine.txt'))\n",
    "reDraw.testDat = arange(min(reDraw.rawDat[:, 0]), max(reDraw.rawDat[:, 0]), 0.01)\n",
    "reDraw(1.0, 10)\n",
    "\n",
    "root.mainloop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 总结 \n",
    "数据集中会包含一些复杂的相互关系，使输入数据和目标变量之间存在非线性的关系。对于这种复杂关系的建模，可以采用树模型来对预测进行分段，包括分段常数（回归树）和分段直线（模型树）。\n",
    "\n",
    "回归分类树CART算法用于构建二元树对离散/连续型数据进行切分。根据使用的不同误差准则方法，可以通过CART算法构建模型树和回归树。但是该算法构建的树倾向于过拟合，可采用剪枝的方法解决。剪枝方法分为预剪枝（在树的构建过程中人工设置参数预防过拟合）和后剪枝（树构建完毕进行删除/合并分支）。\n",
    "\n",
    "Tkinter是python的一个最常用的GUI工具包，结合matplotlib可以构建更强大的GUI。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": true,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}