{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 决策树\n",
    "\n",
    "决策树是一种树型结构的机器学习算法,它每个节点验证数据一个属性,根据该属性进行分割数据,将数据分布到不同的分支上,直到叶子节点,叶子结点上表示该样本的label. 每一条从根节点到叶子节点的路径表示分类[回归]的规则. 下面我们先来看看sklearn中决策树怎么用.\n",
    "\n",
    "## sklearn 接口"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from sklearn.datasets import load_iris, load_boston\n",
    "from sklearn import tree\n",
    "\n",
    "from sklearn.model_selection import train_test_split"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Classifier Score: 1.0\n"
     ]
    }
   ],
   "source": [
    "# 分类树\n",
    "X, y = load_iris(return_X_y=True)\n",
    "\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)\n",
    "\n",
    "clf = tree.DecisionTreeClassifier()\n",
    "clf = clf.fit(X_train, y_train)\n",
    "\n",
    "print (\"Classifier Score:\", clf.score(X_test, y_test))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAD8CAYAAAB0IB+mAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi40LCBodHRwOi8vbWF0cGxvdGxpYi5vcmcv7US4rQAAIABJREFUeJzs3X9cVFX++PHXAUZ+aJrgKvs1xTJLRcXfimSCfFzThTT8mOwnk9boU1u5H+yHYrmhpvxoC9RNW13dcK0Yty01QhNSwHWEVEhXtFZWhdTUdIiAgAnhfP8YmUBEBYf5xXk+HjzQy3DPec+5nDn3fc89V0gpURRFURyfk7UroCiKoliG6vAVRVHaCdXhK4qitBOqw1cURWknVIevKIrSTqgOX1EUpZ1QHb6iKEo7oTp8RVGUdsLF2hVQlNZwd3e/UF1d3cPa9TA3Nze3i1VVVd7WrofimIS601axR0II6YjHrhACKaWwdj0Ux6RSOoqiKO2ESukoDu29995j2LBhfPjhh/j7+3P8+HEmTJjArl27MBgMLFq0iIiICLRabZPfra2txdnZ+br7zczMZP/+/dxxxx38/ve/N21/5plneOKJJ8jNzaWuro4HH3yQkSNHtll8itISqsNXHNpjjz1GREQEjz/+OBqNBn9/f4YPH87w4cN59dVXcXV1ZejQoabX19bWkp6ezpEjRxg2bBh+fn6mD4OOHTvy1FNPARAUFMSDDz7IsmXLTL/78ccfExgYCICnpyfffvstV65csVywinITqsNXHFplZSWurq5cvnyZX/7yl6bt69at49FHH23y+h07dpCamsrLL79Mv379uHDhQrP7fuONN0wfAAD/+te/uHz5MufOnePFF18EYPny5YwdO9aMESlK66kOX3Foa9euJSEhgfXr1+Ph4YGbmxufffYZGRkZuLi44Ofn1+j1oaGhTJkyhbS0NAoLC5k6dSpRUVFN9rtu3TpOnTpFTk4OQ4cOpaysjCVLlpCVlYWbmxtpaWkcOnSIe++911KhKspNqVk6il1qzSydgoIC8vLyiIiIMG0zGAysWLGiUWrGmtQsHaUtqQ5fsUtqWqaitJyalqm0C0VFRY1m4pjjw0Kv17No0aJGZwcXLlxg2bJlvP/++0gpiYuL480336S2tpa3336bJ598ks8///y2y1aU1lA5fMWhaLVazp8/T6dOndBoNJSWlnLu3DlCQkLIzs6mV69eJCcnExERQWpqKlJKYmJimDVrFhMnTiQ4OJj09HTCw8PJzs5m9uzZVFZWsn79elMZ8+bNw9nZmaysLCIjI8nMzKSkpARPT08+/PBDunTpgpOTE0ePHuXcuXOmPP7zzz/PkiVLCAoKstbbo7RzaoSvOJR9+/bRtWtXysvLAZg5cyZeXl74+PgwYcIEevbsSVBQEBqNhqCgIAIDAykoKGDw4MHMnTuXrKwsXFxc2LJlC2FhYS0uv6amhilTpvDVV19x5coVhgwZQt++fcnPz6empgYnJ6dm5/YrSltTHb7iUMaPH49er+e+++4DMHWuXl5e6HQ6zpw5g5OTE76+vmRmZpKVlcWgQYM4cuQISUlJBAYGEhISwunTp/Hw8ADAw8ODqKgo01f9PgMDA9m4cSPnz5/H09MTrVbLww8/zObNm3FycmLIkCGcOnWKvXv3ct9995Gens6vfvUr67wxioK6aKvYKXNftI2Pjyc6OhqANWvWMHbsWEaMGGG2/d8qddFWaUtqhK8oYOrs4+Pjee6551rc2RcVFTF9+nQuXLhAaWkp4eHh/O1vfwNg6dKlREdH8/3335u93orSEuqireKQVq9eTYcOHXjkkUfQarWcOnWKVatWMW3aNHr37k3//v05ceIE8+fPZ9myZdx9991ERkYCkJGRQX5+PhqNBh8fHy5dusS4ceMYMmRIsxdw+/Tpw/Tp0wFwcnKia9euVFZWotfrueuuu5gwYQKZmZmtui6gKOaiRviKQxowYAAlJSUYDAaklJSUlFBWVsaoUaMICwvDz88Pb2/jsvNjxowhNDSUAwcOALB792569OhBRUUFvr6+VFRUUF1dfctld+7cmXfeeQeDwUBFRUWbxKcoraFG+IpDKi0tBaC8vJyqqipqamqoq6vDxcUFIYTpO4BOp+PkyZNERUXx1VdfERwcTF5eHv369UOv19O5c2dOnjzJ6NGjTRdwr6XX60lPT0ev1/Poo4/y/vvv891339G7d2/OnTvHxo0bWbBggUXfA0W5lrpoq9glc120LSoqIjc3l/DwcDPU6vapi7ZKW1IdvmKX1NIKitJyKoevKIrSTqgcvuKQGs6rb6nk5GS6dOmCEIJDhw4xceJE/Pz8ePPNN3F3d+e1115r9PoXXniB3r17Ex4ezv79+zl58iT33nsvjzzyiOk1paWlPPPMM0ydOpU5c+awdOlSqqqqWLhwIenp6UgpbSatpDgu1eErdq2+Y4+NjSUgIICcnBwGDhwI/Jyf9/b2xtXVldTUVNzd3ZkxYwYDBw5sdoolgL+/P0ePHkWj0VBdXX3ddXPqeXl5UVFRgZOTE4WFhSxcuJCEhIRG9bzRVM0xY8aQm5trgXdLae9USkexa/fccw/bt29nyJAhlJeX0717d/Ly8gBTPpza2lpqamo4e/Ys3t7eFBcX39K+J02aRExMDPn5+U1+1nCa5quvvsq8efPYsmWLaeYPwJUrV6itrQXUVE3FNqgRvmLXQkJCmDBhAvv37+ftt9/G09PT9BxZb29vvvjiC9MNWL169cJgMNCvXz+AZqdY1tu3bx9ZWVl06dKFwMBA3nrrLdzd3enatSt//OMfTdMs//znP/Of//yHxx57jNOnT/PHP/6R+++/n08++YTBgwfTr18/zpw50+xUzR9++KHt3yhFQc3SUexUW87S2bNnDwaDgSlTplz351euXOHHH3+kS5cuN9zP5cuX6dat203LS01NpWvXrjzwwANqlo7SptQIX7FLbm5uF4UQPaxdD3Nzc3O7aO06KI5LjfCVdkcI4QLsBf4upVxppn2+BjwAPCSlrDPHPhXF3NRFW6U9WgT8CKw24z5jgTuAeWbcp6KYlRrhK+2KEGI0kAoMl1KeM/O++wK5QJCUssCc+1YUc1AjfKXdEEJ0At4DnjN3Zw8gpTwJLATeF0K4mnv/inK71AhfaTeEEOsAVynlE21YhgA+Ak5KKV9uq3IUpTXULB2lXRBCPAxMAoa2ZTlSSimE+F/giBDCC9gmpfykLctUlFulUjqKwxNCeAPrgDlSyjILFNkBKAbCgSALlKcot0R1+IrDElcBG4GNUsp9Fir6PLABqAMeslCZinJTKoevOCwhRBQwHvAB/KWUNRYuvxPQW0p53JLlKkpz1AhfcWSBQAjghjHNYlFSygrV2Su2RI3wFYclhLiA8QarCAumcxTFZqkOX3FYQog7gR/Mscqau7v7herqaodYu8fNze1iVVWVt7XroVie6vAV5RY40jN01Yqc7ZfK4SuKorQT6sYrpc3YcxqkNWmP9957j2HDhvHhhx/i7+/P8ePHCQsL46OPPqK8vJzo6GgiIiLQarVNfre2ttb0eMVrHT58mOjoaD777DPTtm3btnH8+HGqqqrw8vKirq6OBx98kJEjR7YwUqU9UR2+0maqq6t72GsapDVr7T/22GNERETw+OOPo9Fo8Pf3x8fHB09PT86dO4erqytDh/58o29tbS3p6ekcOXKEYcOG4efnZ/ow6NixI0899RQAQ4cOJTAwsFFZ06dPx2Aw4OvrS35+Pt9++63pSV+K0hyV0lFsRlFRUaPRrzk+LPR6PYsWLWLZsmWmbSdOnCAmJoaVK82yFL5JZWUlrq6uXL58udH2J554gr59+zZ5/Y4dO9i6dSszZsxg8uTJLS7v6NGjDBo0iDlz5hAdHc3nn3/e6ror7YMa4SsWp9VqOX/+PJ06dUKj0VBaWsq5c+cICQkhOzubXr16kZycTEREBKmpqUgpiYmJYdasWUycOJHg4GDS09MJDw8nOzub2bNnU1lZyfr1601lzJs3D2dnZ7KysoiMjCQzM5OSkhI8PT1JS0tj8eLFJCYmmjWutWvXkpCQwPr16/Hw8MDNzY0DBw6QkZHBjz/+2OT1oaGhTJkyhbS0NAoLC5k6dep1n7F7+vRpdDodW7ZsYfjw4ZSVlXHPPffg6ekJQFpaGocOHeLee+81azyK41EdvmJx+/btY+TIkaYOeObMmWzevBkfHx8mTJhAz549CQoKQqPREBQURF1dHQUFBQwePJi5c+eyadMmXFxc2LJlC88++6y1wzF5+WXj4pjR0dEUFBSQl5dHREQEo0ePBsBgMFBZWdnod1xcXJg2bdoN93v33XeTmpraZPsLL7wAwK9//Wt+/etfmyMExcGplI5icePHj0ev13PfffcBmC5Wenl5odPpOHPmDE5OTvj6+pKZmUlWVhaDBg3iyJEjJCUlERgYSEhICKdPn8bDwwMADw8PoqKiTF/1+wwMDGTjxo2cP38eT09PtFotU6dOZcWKFbi5ubVZjIMGDSIiIqJRmsrV1ZWlS5fe9r6vl6batm0bixcvZs+ePbe9f8VxqXn4Spsx99z1+Ph4oqOjAVizZg1jx45lxIgRZtt/Q9fOVb9ZLDdKU2m1WmbPnm22NNVHH33E0KFDyczMJCwsDE9PTzIyMti/fz+jRo1i6tSpLYpNaT/UCF+xG/WdPcBzzz3XZp19a+zbt4+uXbtSXl4OwMyZM/Hy8mo2TRUYGNgoTZWVlWVKU4WFhbW4/EmTJhETE0N+fr65Q1MciOrwFbsRHx/fqt87fPgwzz77LNu2bePKlStER0cTHR1NbW2t2epm7TTVvn37WL58OV26dDFbTIrjUSkdpc00lwZZvXo1HTp04JFHHkGr1XLq1ClWrVrFtGnT6N27N/379+fEiRPMnz+fZcuWcffddxMZGcmmTZsYMWIE+fn5aDQafHx8uHTpEuPGjWPIkCHNpkCOHz/Opk2b8PPz4/7776e0tBQpJZ6engwfPry5urcopdNalkxT1VMpnfZLjfAVixswYAAlJSUYDAaklJSUlFBWVsaoUaMICwvDz88Pb2/jTa5jxowhNDSUAwcOALB792569OhBRUUFvr6+VFRUUF1dfcPyBg4cSEJCAqdOnWrz2FrKltNUiuNRHb5icaWlpQCUl5dTVVVFTU0NdXV1uLi4IIQwfQfQ6XR88MEHjBo1CoDg4GAuXLhAv3790Ov1dO7cmZMnTwLNp0COHj1KXFwctbW1+Pn58fnnn7N79278/PysEL1Ra9NTRUVFTJ8+nQsXLjRJTyUlJfHaa6/xn//8x8y1VRyFSukobeZ20yBFRUXk5uYSHh5uxlrdmltN6Vg6PQWQnJzMQw89xLlz5xqlpzIyMpg/fz5r1qxh/vz5txyb0n6oG68Um9WnTx/69Olj7Wrc0IABAzh48OB101MBAQFoNBrKyozPTR8zZgxjxoxplJ7q378/33zzDb6+vnz66ac3TU/diBDCdGakKNejUjqKVbQ2pQHGEe7WrVsb3Wx0vZuR6m3cuJHY2Fh0Ol2j7df+zu9+9zsuXLjQorpYOj2l1+tJT0/n/fffb5Ke0mg0LF++nNDQ0BbFoLQfKqWjtBkhhIyLiyM6OprY2FgCAgLIyclh4MCBHD9+nPDwcHJzc/H29sbV1ZXU1FTc3d2ZMWMGAwcObDatUZ/SOHr0qOlmo6qqqiY3I9VLSEhg4cKFpu/1rr2B6ZNPPuGhhx7C29vb7LN0rJmeupZK6bRfaoSvtKl77rmH7du3M2TIEMrLy+nevTt5eXmAqeOhtraWmpoazp49i7e3N8XFxbe07xvdbNQwNdIwzfHTTz+ZZRXOlurTp49NdPZK+6Y6fKVNhYSEsHz5ciZPnkxhYSHOzs6mddu9vb354osv2LVrFxqNhl69emEwGOjXrx/QfFqjXsObjRrejNS1a1dWr15tel23bt2Ii4vjgQceYMOGDaa7Ya+9gam1zJGeutGSzZGRkaxcuZLKyspm01M3urksISGB3NzcVtdRcRzqoq3Spjw8PDh48CDAdWeONOzg/P39b2mfvXv35ssvv2TKlCk88MADpu2xsbEAXLlyhaefftq0fe7cuaZ/33///XTu3Bkw3gVb/zsA58+fv+GCavU3SV2bnoKfUzYtTU/Vx52SktLsks1eXl78+OOPCCG4fPkyr7zyCgkJCQQEBJhe06FDB+644w4qKys5cuQIkyZNQkrJkSNHGDNmzC29r4rjUx2+0mbc3NwutubJUdb0yiuvAMa6AwghhgHPQPPpKXd39+ump8aPH09xcbHpQ6ElDAYDrq6ugPEaxJEjR/j888+bpKc0Gg1CCNPNZcuXL+f++++/6f6FEJ2llGUtrphi11RKR2kzVVVV3lJKYW9fQMfq6upFQogvgG3AN9C26amGSzbr9Xo2b95s+tkbb7zBhg0bGD58eLPpqVbcXFYkhPjz1Q80pZ1Qs3QU5SohxEDgaWA2sB/4M/CZlLK2rdbS2bNnDwaDgSlTppi2VVRUoNFoTCP85ly+fJlu3brdtIyNGzcyfvx408JuV88S/h8wF/hf4DzGWP8upaxsbj+K/VMdvtKuCSFcgTCMaZt+wEZgg5Sy0VQhd3f3C9XV1XaVnmqOm5vbxaqqKm8AIYQzMAVj/GOB94B1UsqvrFhFpY2oDl9pl4QQfTGObp8AjmIc4W6XUtZYs17WJITwwfiezAX+jfE92SqlNFi1YorZqA5faTeEEC5AKMbR7HBgE8bRbKFVK2ZjhBAaYBrG92kw8C6wXkppe8uNKi2iOnzF4Qkh7gIir34VYRy5/kNK2fqFa9oJIcR9GEf9EUAexvfuUynlFatWTGkV1eErDkkI4QT8CuMo9UHgA4yj+aNWrZidEkK4A/+N8f30ATZgvNZx1qoVU1pEdfiKQ7k67/+3GEel3wPvAFopZYVVK+ZAhBBDMM5m+g2wF+N7nCGlrLNqxZSbUh2+YveEcZ7hBIyjz8nAR8CfpZSHrFoxByeE6ISx0/8dcCewDnhXSvmdVSumNEt1+IrdEkJ4AnMwdvS1GEea70kpS61asXbm6gfuSIztEAZ8hjHXv7dNbl5QWk11+Ipdudq5jMHYuUwHPsXYuehU52J9Qog7gccxjvoFxrb5m5Tye6tWTAFUh6/YCSHEHcD/YOzo78CYPkiWUl6yasWU67r6wTweY3tNBbZi7PwPqA9m61EdvmLThBB+GDuNWUAmxk5jt7pAaD+EEN0x3uD2NFCGsQ0/kFKWW7Ne7ZHq8BWbIYS4GzgDaIBHMXb0dwHrgY1Sym+tWD3lNl2dKvtfGNs1ENBinCp7RAjhDZSqeyPalurw7Zw9r/FyzZouI4F04GOMufkvMI4Ed6qbfByPEKIn8CTwFMYP+fNARyCkYXs7yvFtK1SHb+faahVHS6h/turVP/7TVzenA89LKYusVzPFUq4udzEbWATchzFd918Nfm73x7e169GQegCKYgtKgFVAKWBQnX37IaW8IoTYD2wHJD9/8CttQI3w7dyNRkDvvfcew4YN48MPP8Tf35/jx48zYcIEdu3ahcFgYNGiRURERKDVapv8bm1tbZOHdDSUkpJCcXEx0dHRAPz1r3+ltLQUHx8fnJ2dOXToEBMnTmTixIk3qrvNjYAU22Irx/fGjRtND5vp06eP3R7faoTvwB577DEiIiJ4/PHH0Wg0+Pv7M3z4cIYPH86rr76Kq6srQ4cONb2+traW9PR0jhw5wrBhw/Dz8zP9sXTs2JGnnnoKgGPHjvHLX/6S4uKfl4z/5ptvWLJkCU899RSPPvooGo2G6mp1/U1pO5Y8vmtra7l48SKDBw+mY8eOdnt8q0ccOrDKykpcXV25fPlyo+3r1q3j0UcfbfL6HTt2sHXrVmbMmMHkyZOb3W9OTg6HDx9Gp9OZtgUHB7N69Wq6dOnCpEmTiImJIT8/33zBKMo1LHl819XVERcXx8mTJ+36+FYjfAe2du1aEhISWL9+PR4eHri5ufHZZ5+RkZGBi4tLk+edhoaGMmXKFNLS0igsLGTq1KlERUU12W9kZCQA1dXVFBYWUlZWRl1dHdXV1UybNo19+/aRlZVFly5dLBKn0j5Z8viurKzkrbfeokePHnZ9fKscvp271VkMBQUF5OXlERERYdpmMBhYsWIFy5Yta8sqNssWc5yKbVHHt3mpDt/O3ewPoqioiNzcXMLDwwGQUtY/xLrV9Ho9b775Ju7u7rz22msAHD58mOjoaD777DOqqqp444036N69O8888wwvvfQSQgiefPJJBgwY0LDuNvcHodgWWzm+T5w4wfvvv0/Xrl2Jiori4MGDrF+/nnfeeYc1a9Zw6tQpYmNj6dixY8O629zxrVI6DkKr1XL+/Hk6deqERqOhtLSUc+fOERISQnZ2Nr169SI5OZmIiAhSU1ORUhITE8OsWbOYOHEiwcHBpKenEx4eTnZ2NrNnz6ayspL169ebypg3bx7Ozs5kZWURGRlJZmYmJSUleHp6MnToUAIDAwHIyMigrq4OZ2dnhBCUl5cjpaRHD7u8f0axAdY+vtPS0li8eDGJiYlUVlZSUFBA3759cXFxYcSIEeh0uhvO+rEV6qKtg9i3bx9du3Y1TR2bOXMmXl5e+Pj4MGHCBHr27ElQUBAajYagoCACAwMpKChg8ODBzJ07l6ysLFxcXNiyZQthYWG3VZcrV64QEBCAwWCguLiY8ePHM2/ePP75z3+aI1SlHbKl4/vAgQN899136HQ6zp49ywMPPMDjjz/e5OKxLVIjfAcxfvx4zp49y/3338/ly5dNow0vLy90Oh09e/bEyckJX19fXn/9ddMIaOnSpSQlJREWFoaHhwcrV67Ew8MDAA8Pj+te1AoMDOStt97C3d0dT09PtFotY8aMQafTsWXLFn71q1+RkJBAXV0d3t7e6HQ6jh49ytNPP23R90RxHNY+vqdOncqKFSvo2rUrgYGBBAYGIqXE1dWV2NhYiouLmTBhgkXfk9ZQOXw7d7u3nsfHx5tuLlmzZg1jx45lxIgR5qreDdlijlOxLer4Ni/V4ds5tdaI4sjU8W1eKoevNBIfH9+q3zt8+DDPPvss27ZtA+DgwYOmOxcVxVa09vgG2LlzJ9HR0UgpiYuL480336S2ttaMtWt7KofvoFavXk2HDh145JFH0Gq1nDp1ilWrVjFt2jR69+5N//79OXHiBPPnz2fZsmXcfffdphtOMjIyyM/PR6PR4OPjw6VLlxg3bhxDhgxpdmZDhw4duOOOO6isrGw0i0FR2oKlj++LFy9SWVnJnXfeydGjRzl37hz33nuvtcJvNTXCd1ADBgygpKQEg8GAlJKSkhLKysoYNWoUYWFh+Pn54e1tXKp7zJgxhIaGcuDAAQB2795Njx49qKiowNfXl4qKipuuGzJw4EASEhI4depUk1kMimJulj6+9+7dyzfffINOp6O0tJQhQ4bQt29fu1teQY3wHVRpaSkA5eXlVFVVUVNTQ11dHS4uLgghTN8BdDodJ0+eJCoqiq+++org4GDy8vLo168fer2ezp07c/LkSUaPHt3szIajR4/y6aefUltb22gWw1133WXRuJX2wdLH98yZMwHj3bvjxo1jx44dFBYWsnjxYssFbQbqoq2du92LWtfeqWhJtnhRS7Et6vg2L9Xh2zk1i0FxZOr4Ni+Vw1cURWknVIfvwG5nClpycjJbt27lxIkTxMTEsHLlyiav+f777wkKCgIgKSmJ5cuXN1pDHBpP1zQYDFY5tVYcU1sf3ytXrmy2jLi4OLRaLdu2bWPx4sXs2bMHvV5vmglkq9RFWwdQfzdhbGwsAQEB5OTkMHDgQODnHKa3tzeurq6kpqbi7u7OjBkzGDhwYLPT0AD8/f1JSUkxLRp1La1Wy6RJkwD44YcfWLBgAYsWLSIgIMD0mobTNa99ApGi3AprHd9RUVHX7fCzs7MZPHgwFRUVjZ5+5eXlZfNTNdUI3wHcc889bN++nSFDhlBeXk737t3Jy8sDTHlEamtrqamp4ezZs3h7ezd6fFtLGAwGwLiEbFFRETk5OeTm5jJy5Eg2bNhAt27d+Omnn6jPuzacrqkorWGN4/taDadt5uXlceDAAXQ6nd09/UqN8B1ASEgIEyZMYP/+/bz99tt4enpy5coVALy9vfniiy9MN6n06tULg8FAv379gOYXkKrXcNEovV7P1q1biYyMxMvLi4SEBOLj4xk7diyffPIJP/74I2FhYWzYsIHZs2fTuXPnRtM1FaU1rHF8g/FB5jqdjuLiYlJSUkxr8rzwwgumMwt7e/qVmqVj59pqFsOePXswGAxMmTLFtK2iogKNRoOrq+sNf/fy5ct069atyfZrn0Bki7MYFNtiK8d3c8d0Q3q9no0bN7JgwQLANo9v1eHbOXd39wvV1dV2+WQRNze3i1VVVd7Wrodiu9TxbV6qw3cAQojJwF+BzcBrUsqfrFylJoQQo4H3gX8C/yelLLdylRQHJIRYB3SQUv7WTPvrBeQBU6WUh8yxT2tSF23tmBDCTQiRBPwFmC2ljLbFzh5ASnkAGAbUAV8KIcZYuUqKgxFCPAxMAv7PXPuUUp4B5gHvCyE63uz1tk6N8O2UEGIQ8AHwb+BpKWWJlat0y4QQM4C1wJ+AOCmluqKr3BYhhDfwJfDfUkrdzV7fiv1vBsqllM+ae9+WpDp8OyOMK0I9D7wGvAxsssd7z4UQdwGbgA4Yz05aN49Oafeu/k18CuRLKf/QRmV0AY4Az0opd7RFGZagUjp25OooZgcwG/CXUibbY2cPIKU8i/H0eztwUAjxGytXSbFDQggP4BmgO7CsrcqRUv4AzAE2CCG6t1U5bU2N8G2cEKIT8CPwa4y5+r8Ar0spa6xaMTMSQgzDmJ46hPHspVZKWWHdWim2TgjRB9gJdAMCpJQnLFBmHDAQmG6Pgy01wrdhQogOwGGMs1veBh6VUr7mSJ09gJTyS2AEUIEx3lQhxGzr1kqxA37APRiPm+EWKjMG6AXY9qI5zVAdvm17DfABfIEwKeU/rVyfNiOlrJRS/g74DBgL/EkI4W7laim27UHgJ2Ah8He8dL4QAAAgAElEQVRLFHh1FtxsIFYI0f9qmtVuqA7fto3GOPPgU+CSletiKTrgH0AVxg86RWnOS0BnKeXfpZR1lipUSnkcWI7xOP2Hpco1B5XDVxRFaSEhxC5gFOAmpfSwdn1ulRrhK4qitNw0YCUghRB2swhluxrhq3U57Ie9tVV7ax9QbWSP2lWHr56PaT/sra3aW/uAaiN7ZDenIoqiKG3F3s5WGmrJmYvK4V/13nvvcezYMZYsWcKuXbtISkqiuLiYxMREli5desPnsd7o4R6HDx/moYcearTtn//8J2+88QZ79+5t9ExM5cYs2UZLlixh5cqVnDhxgpUrV5KYmMihQ3a/WKLFXK+tioqKmD59OhcuXGh1Wx09epQ333yTVatWmbZt27aNZ5555rbqW11d3UNKiT1+teSDSo3wr3rssceIiIjg8ccfR6PR4O/vj4+PD56enpw7d67J81hra2tJT0/nyJEjDBs2DD8/P7RaLQAdO3bkqaeeAmDo0KEEBgY2KuuTTz6hd+/eODk5NXompnJjlmwjLy8vysrKAPD09OTbb781PWVJubnrtVWfPn2YPn06QKvbavDgwezcuZOqqirT706fPp2vv/7agtHZLzXCv6r+IduXL19utP2JJ56gb9++TV6/Y8cOtm7dyowZM5g8eXKLyiorK2PevHmkp6fb3TMxrcmSbTRv3jwWLVrEP/7xD+bMmUN0dDSff/75bdW/PWmurZrTkrZasGABnTt3Nkc1W62oqMj0gQSYnuF8O/R6PYsWLTI9EQ7gxIkTxMTEsHLlytveP6gRvsnatWtJSEhg/fr1eHh44ObmxoEDB8jIyODHH39s8vrQ0FCmTJlCWloahYWFTJ069brPzjx9+jQ6nY4tW7YwfPhwysrKmDx5MomJifj4+NjdMzGtyZJtdOLECY4dO8YDDzxAWloahw4d4t5777VEmA7hem2l1+tJT09Hr9fz4osvNnr9rbZVRkYGOTk5eHh4UFhYSFlZGZWVleh0OnQ6HQEBAWaNQ6vVcv78eTp16oRGo6G0tJRz584REhJCdnY2vXr1Ijk5mYiICFJTU5FSEhMTw6xZs5g4cSLBwcGkp6cTHh5OdnY2s2fPprKykvXr15vKmDdvHs7OzmRlZREZGUlmZiYlJSV4enqSlpbG4sWLSUxMNEs8apbOdRQUFJCXl0dERIRp27XPY7W09jbD4GZtZWtt1N7aB+zv7+lGbdRcLM8//zwjR440dcCTJk1i8+bNhIeHk5uby9ixY9m/fz99+/bl+++/p66uDi8vL7Zt28bChQvZtGkTdXV11NbW8uyzz+Lh4dFsh//RRx8xdOhQMjMzCQsLw9PTk6SkJJ5//nkSExNZuHBhi+O6lkrpXKOoqIiCggLTwVl/ELi6urb64LyVU7WDBw+a8pRRUVGNTheVxizVRgApKSnEx8cDsHPnTqKjo4HG7aU01TDlMWjQIObMmdPo561pK2u00fjx49Hr9dx3330AODs7A8ZrPDqdjjNnzuDk5ISvry+ZmZlkZWUxaNAgjhw5QlJSEoGBgYSEhHD69Gk8PIw35Hp4eBAVFWX6qt9nYGAgGzdu5Pz583h6eqLVapk6dSorVqzAzc3ttuKo125TOrZ0qlZZWUlBQYEpDx0VFUVubq613hqbYe02OnbsGL/85S8pLi7m4sWLVFZWcueddzZpr/bM0dto1qxZTbbVf6D86U9/arQ9ISHB9O8HH3zQ9Lo1a9Ywd+7cm5bl5eVFbGys6f/1s5iWLFnS4no3p92O8Pft20fXrl0pLzc+S3vmzJl4eXnh4+PDhAkT6NmzJ0FBQWg0GoKCgggMDKSgoIDBgwczd+5csrKycHFxYcuWLYSFhd1WXQ4cOMB3332HTqfj7Nmz5gjPIVi7jXJycjh8+DA6nY69e/fyzTffoNPp+Pzzz1V7XaXa6PrqO3uA5557jhEjRli8DtfTbkf448eP5+zZs9x///1cvny5yalaz549Tadqr7/+umlksnTpUpKSkggLC8PDw4OVK1c2OVW7VmBgIG+99Rbu7u5NTtW6du1KYGAggYGBSCm56667iIuL4+uvv2by5Ml07drVou+LLbF2G0VGGpc8r66uZubMmYAx9/zwww/z8MMPm9qrPVNtdH3x8fGNOv2W2LlzJ9nZ2SxYsIBNmzZx5swZddG2NcxxK3jDhlyzZg1jx461yKd3e7soeDttZY02am/tA47VRs3Fsnr1ajp06MAjjzyCVqvl1KlTrFq1imnTptG7d2/69+/PiRMnmD9/PsuWLePuu+8mMjKSTZs2MWLECPLz89FoNPj4+HDp0iXGjRvHkCFDmk1bXbx4kX379lFYWEh0dDSpqan84x//YNOmTa2K61rtdoTfWteeqim2R7WR7bOXNhowYAAHDx7EYDAgpaSkpISysjJGjRpFQEAAGo3GdIPemDFjGDNmDAcOHABg9+7d9O/fn2+++QZfX18+/fTTm95guXfvXs6ePYtOp6OsrIzQ0FC+++47DAYDrq6utx1Pu83hm0P9zIDWqJ9N8MMPP/DSSy/x3HPPodfrzVg7paHWtlVVVRVLly7lnXfeMXONlGu1to0aLq9hbqWlpQCUl5dTVVVFTU0NdXV1uLi4IIQwfQfQ6XR88MEHjBo1CoDg4GAuXLhAv3790Ov1dO7cmZMnTwLNz9SZOXMm8+fPJyAggAsXLhAXF2c6SzAHNcKn9adtYLwRpDWnbfWzCZydnSktLUUIwZ133mmtt8BuWLqtMjIyqKurM/1BKjdn6TZquLyGudVfFwDw9f35AWwNz1DGjh1LUVERU6dONc2sqf/5pEmTTK9ryU1h9b+/aNGi1lW8GWqEj/G0raSk5LqnbWFhYfj5+eHtbVyMbsyYMYSGhjY6bevRowcVFRX4+vpSUVFxS6dt9bMJTp06xaxZswgNDaWgoKDNY7V3lm6rK1euEBAQgMFg4NKl9vKUydtj6TaC5pfXsJQ+ffo0uxicLVEjfFp+2nby5EmioqL46quvCA4OJi8vr8lp2+jRo5udbdBwNkGPHj1Yt24dHTp0ICYmxnJB2ylLt1VQUBAJCQnU1dXh6elp0VjtlaXb6EbLa5jD7cy4SU5OpkuXLvj6+vL+++/TtWvXJjEkJSXx/fffM2fOnCbLd6SkpFBcXMxvfvMbPvroI8rLy4mOjiYiIqJ1N2dae2lPS34Zw22906dPy5SUlNvaR2tdrbvV30NLfdlbW7W39pEO1kaAjIuLk1JKuWLFCpmVlSXj4uLk9u3bZVxcnKmumZmZcv/+/XLRokVy2bJl8tixY1JKKX/88UeZlJRk+rpy5YqUUsp3331Xnj9/XiYmJsqffvpJxsfHN6lXfHy8NBgMMjExsdH2goICmZmZaarXu+++K1944QUppTRtu1lc136pEX4L9OnThz59+li7GsotUG1l+2ytje655x62b9/OkCFDKC8vp3v37uTl5eHu7l4/9ZHa2lpqamo4e/Ys48ePp7i4mIEDB7a4rIazboQQpjOe6upq0zIKOTk5VFRUoNPpAGPaau3atbcVo8rhN3A7s26Sk5PZunXrDZcz/f777wkKCgLgb3/7Gy+//DIbNmxo9JqGD+PQ6/Wmi1nKz9qynerq6oiNjeXpp5++bs4+Li4OrVZLcXHxddMLilFb/y2tXLnyumVs27aNJUuW8MEHH7S4jUJCQli+fDmTJ0+msLAQZ2dn0zMQvL29+eKLL9i1axcajYZevXphMBjo168f0Pysm3oN18TR6/Vs3rzZ9DONRsPy5csJDQ1tFGtkZCRRUVEEBARw4MABVqxYcdt3DbfLEX59Ti42NpaAgABycnJMn9JFRUXk5ubi7e2Nq6srqampuLu7M2PGDAYOHNjsTAEAf39/UlJSml3OVKvVmq7az5kzh8TExCa3kzd8GIeXl1e7XpLXGu3k5OTEK6+8QnJyMqWlpfziF78w/Sw7O5vBgwdTUVGBj4+P6cJje2atv6WoqKjrdvjTp08nODiYtWvXtriNPDw8OHjwIADz589v8vOGnbG/v/8t7bN37958+eWXTJkyxbQmTkVFBY8//rjpNQ3Lut4Ar/76wejRowHj2UFlZeUtlX+tdjnCb+7UDbjuqZu3tzfFxcWtKstgMADG0XpRURE5OTmmhdHqF4BST7u6Pmu0E8DXX39NeXk5/fr1a9Q2eXl5HDhwwHSKrVivjRpq2Ea1tbW88cYb/O53v2vRvt3c3C7Wp1bM+RUcHMzUqVMbbbvjjjtwc3O77ut/8Ytf3HSfbm5uvP766w3/f/FW42yXHb41Tt28vLxISEggICCAsWPHcuzYMQYNGgQ0Hjk0fBhHe2eNdqqpqSEyMpLa2lrOnDnTqG1eeOEF5s6da/aHbNgza6VBUlJS0Ol0FBcXN2qjP/zhDxgMBnJycloUR1VVlbeUUtjj160+wBzUWjpms2fPHgwGA1OmTDFtq6ioQKPR3PSW6MuXL9OtW7cm2/V6PRs3bmTBggXtbq2WtmqrlrZTc21TXFxMWloazz77bH1921X7gGoje9SuOnx3d/cLLXnCuy1xc3O72JJPcntnb23V3toHVBvZo3bV4beUEKIrcAT4XynlZ2bYn+fV/c2VUmbc7v4UEEI4A9nAx1LK215DVgjhAuwDPpBSrr7d/SlGQoi/AE5SyifNtL93gZ+klE+bY3/therwb0AI8QGgl1LOM+M+/wtIBvyklGq1tNskhHgFCAYmSSnrzLTPe4EcIFBKecwc+2zPhBDTgbeAoVLKcjPtszNwGIiSUn5ijn22B6rDb4YQ4n+AxcBIKWXr5kA1v+9EoDcws80uKrQDQoiRQBowQkpp1scaCSGeBOYBY6SU158eotyUEOKXwJfAI1LKll1Jvfm+A4B/AMOklBfMuW9HpTr86xBC+AAHgYeklPltsH+3q/t/U0rZ/JMNlGYJIToC+cAfpJR/b4P9C+BjoFBKucDc+28Prr6HO4ADUso2WShKCPE6MBwIUYOnm1Md/jWu5oR3AzullAk3e/1tlDPkajljpJSn2qocRyWEWAt0klLOacMyumG85jJbSpnZVuU4KiHEc8Ac4AEpZU0blaEB9gN/lVKqhxbchOrwryGEWAD8Gpgopaxt47JeAMIw5oqvtGVZjkQI8WvgbYw54R/auKyHgHXAX4Bkc6eOHJUQYgCwFxgnpSxs47Lux3ihfbyU8uu2LMvetcsbr5ojhBgGvATMaevO/qqVgAFYaIGyHIIQojvGzndOW3f2V50CTgPPAOMtUJ7dE0J0AN4HXm3rzh5ASvlv4A/A+1fLVpqhOvyrhBDuGA/S+VLK1t373UJXZ5VEAP8nhBhliTLt2dWc8AaMI+1/WqjYUuAHoCcwzUJl2rulwFmMH8yWsg44D6iHStyASukAQogkoAvgDvyPpS/+CCEeBV4HcoHfW2jkaleEEP+HsdMNBvyllD9ZuPwwoEZKmWrJcu2JEOJhYAzwW4zptu8sXH4PjFM1/wrkqrZqSo3wjX4LTAf+baUr/SXAj0AIMMgK5duD3wDPAUeBNrkAeCNSyo9VB3JTIRinsuYD1lgRsPpq2fMwXodTrtHuO/yrd9N2wdjpZlmpGscx5oo9gSk3eW17NRTj9Y5davqdzZoMuAL/BMxyg1ULlWG8UOwKPGSF8m1eu0/pCCGcgCcw5oXNcqfmbdTlV8BpS1zosjdCiDnA36WUZh05qvVgzOfqHbVfSCnPW7ke/w8YLaXcZs162KJ23+Er7VtbrqDaFtSKj8rtaPcpHUVRlPbCJh5xaG+n1Q3d6BTb3uK6WbrA3uKB1qdA3nvvPYYNG8aHH36Iv78/x48fZ8KECezatQuDwcCiRYuIiIhAq9U2+d3a2tomD/Oot23bNg4dOsTEiROZOHGiafszzzzDE088QW5uLnV1dTz44IOMHDmypdUG7K+dHO24s+W0m010+NXV1T3s6bS6oatTwa7L3uK6USxgf/HAzWNqzmOPPUZERASPP/44Go0Gf39/hg8fzvDhw3n11VdxdXVl6NChptfX1taSnp7OkSNHGDZsGH5+fqYPg44dO/LUU0+Z/q3RaBo9lu/jjz82PcfY09OTb7/91vTUqNawt3ZytOOutcecJdhlSqeoqKjRyMocB4Ner2fRokUsW7bMtO3EiRPExMQ0eoRaW3C0eMD+Y6qsrMTV1ZXLly832r5u3ToeffTRJq/fsWMHW7duZcaMGUyePLnZ/U6aNImYmBjy839ek+9f//oX+/btQ6fTMWfOHKKjo/n888/NF0wz7L2NrscRYzInmxjhN0er1XL+/Hk6deqERqOhtLSUc+fOERISQnZ2Nr169SI5OZmIiAhSU1ORUhITE8OsWbOYOHEiwcHBpKenEx4eTnZ2NrNnz6ayspL169ebypg3bx7Ozs5kZWURGRlJZmam6eHiaWlpLF68mMTE236uhkPG46gxAaxdu5aEhATWr1+Ph4cHbm5ufPbZZ2RkZODi4oKfn1+j14eGhjJlyhTS0tIoLCxk6tSpREVFNdnvvn37yMrKokuXLhQWFlJWVsaSJUvIysrCzc2NtLQ0Dh06xL333mu2WByxjRwxJkuw6Q5/3759jBw50vQmz5w5k82bN+Pj48OECRPo2bMnQUFBaDQagoKCqKuro6CggMGDBzN37lw2bdqEi4sLW7ZsMT3XUsVjXo4YE8DLL78MQHR0NAUFBeTl5REREcFDDxmndxsMBiorGz8mwcXFhWnTbrz6wgMPPMADDzzQZHt9Sgfg17827z1DjthGjhiTJdh0Smf8+PHo9Xruu+8+ANOFMC8vL3Q6HWfOnMHJyQlfX18yMzPJyspi0KBBHDlyhKSkJAIDAwkJCeH06dN4eHgA4OHhQVRUlOmrfp+BgYFs3LiR8+fP4+npiVarZerUqaxYsQI3NzcVTzuKqV59emDQoEFEREQ0Sg+4uro2OsW/VddLDwCkpKQQHx8PwM6dO4mOjgbg4MGDpvx/azliGzliTJZgE/PwzT0XOj4+3vQHs2bNGsaOHcuIESPMtv+GbjQv2lxxWSqem83xNmc72VJMKSkpzaYHtFots2fPNlt64KOPPmLo0KFkZmYSFhaGp6cnx44d49KlS+Tm5vLb3/6Wffv2UVhYyO9//3u2bNnCxYsXTe/VrczDV8dd8ywRky3fK+GQHb4lWaLDtxRL/uFZyq3E9NxzzzVKD0yaNInNmzcTHh5Obm4uY8eOZf/+/fTt25fvv/+euro6vLy82LZtGwsXLmTTpk3U1dVRW1vLs88+i4eHR4s6/A0bNlBRUcHu3buZM2cOZ8+eZc+ePTz11FN89dVX7Nu3j3feeYe77rrLoh2+pTjacWfLHb5Np3Raq/7UuDXqT6cvXLjAypUrmTx5MhUVFWasXeu1Nq6ioiKmT5/OhQu299jP1sZUXFxMYmIiS5cuve06WDs9EBkZSVRUFAEBAcycOZP58+cTEBDAww8/zMKFCwkICOCuu+667Thbq7VtlJ+fT1xcHEuWLDFvhczAEf+WboVNX7RdvXo1HTp04JFHHkGr1XLq1ClWrVrFtGnT6N27N/379+fEiRPMnz+fZcuWcffddxMZGQlARkYG+fn5aDQafHx8uHTpEuPGjWPIkCHNjr4uXrxIZWUld955J97e3kRFRaHX6+nUqZNdx9WnTx+mT59u1hisHZOPjw+enp6cO3futus+a9asJtvqT/v/9Kc/NdqekPDzUy8ffPDBRumBuXPn3rQsLy8vYmNjTf8PDw9vUuaN/n07LN1GDe9baCuO+LfUlmx6hD9gwABKSkowGAxIKSkpKaGsrIxRo0YRFhaGn58f3t7GG9rGjBlDaGgoBw4cAGD37t306NGDiooKfH19qaioaHSzy/Xs3buXb775Bp1OR1lZGfn5+QwbNszu47IEa8T0xBNP0Ldv3zaN60YadsTPPfdcm10nMhdrtFFz9y3Yc0z2zKZH+KWlpQCUl5dTVVVFTU0NdXV1uLi4IIQwfQfQ6XScPHmSqKgovvrqK4KDg8nLy6Nfv37o9Xo6d+7MyZMnGT16tOl0+1ozZ84EjFPuOnfuzI4dO0zT8+w5Lr1eT3p6Onq9nhdffNHs8VgjpgMHDpCRkcGPP/7YJvG0VsOLgi1RXFzMRx99RHl5OTExbfPQJku30Y3uW7DXmCzxt9SWHOKibVFREbm5uY1Ojy2lLS/aWjouS1w8s5eYWpsq2LRpEyNGjGhxqgAgOTmZo0eP8tZbb7U6nhvFdKvspY1awpIx2fJFW5se4d+qPn360KdPH2tXw+wcMS57iWnAgAEcPHjwuqmCgIAANBoNZWVlgDFVMGbMmEapgv79+/PNN9/g6+vLp59+esspqrVr17ZpXLfCXtqoJRwxptZwiA5fUcxNpagUhySltPqXsRrXFxcX1+zPbubdd9+VH3/8sfz3v/8tX3vtNZmUlNTkNSUlJTIwMFBKKeWmTZvkSy+9JP/yl780ek3D36+urpazZs0y/exq3W0ursTERPmHP/xBFhYWNtr+5ZdfysmTJ0sppbx8+bJ88sknbymWm8VjzZj+9a9/yT/+8Y9y5cqVZo/pZk6fPi1TUlJuax8tcbN4pI0ed3v27JHLly+Xq1atsrvjLikp6bplZGdny7i4OLlx48ZGMd1KG1nry2ZG+PUXu2JjYwkICCAnJ4eBAwcCP+ffvL29cXV1JTU1FXd3d2bMmMHAgQNvmBf19/cnJSWl2YWOtFotkyZNAmDOnDkkJiYSFhbW6DUNF0q6dllcW43rp59+YvHixaxZs4b58+ebtg8dOtS0bouXl1erFumytZgGDx7Mzp07qaqqanVMrWWrqQJba6OgoCAefPBBli1bZnfHXVRU1HXn7efk5BAdHU1CQoLFj7vWsplpmffccw/bt29nyJAhlJeX0717d/Ly8gDTRRBqa2upqanh7NmzeHt7U1xc3KqyDAYDYLziXlRURE5ODrm5uQCmuy3NNT3LGnHV77s+5WDuqWa2GNOCBQvo3LlzKyNq3u3cxJecnMzWrVubXUq3rq6O2NhYnn76aS5dutToZ1lZWaYLjMXFxddNA92ILbbRG2+8cVvrAlkrpoYaxlQfpz2xmQ4/JCSE5cuXM3nyZAoLC3F2djY9BMLb25svvviCXbt2odFo6NWrFwaDgX79+gHN39VYr+FCR3q9ns2bNwPGEW5CQgIBAQGMHTuWY8eOMWjQIIBGf5y3s1CSNeIC0Gg0LF++nNDQ0EaxnD59Gp1Ox5YtW1oci63GlJGRwbJly5qsXtkS9R17bGws2dnZxMfH88knnwA/L6KWlZVFTk4Or7zyCq+//jrHjx8HjGvnr1y50vRVW1tr2q+/v7/pDPHaTsTJyYlXXnkFf39/0zWDeoGBgaYzSR8fH9Nc8ltla220bt06Tp06RU5OTovisIWYUlJS0Ol0FBcXN4pp7NixJCQk0L1791bHZGk2MS3T3h5h1pB6xKFtu1lM9VP+/v73v+Pq6mrqCL777juKi4txd3fnN7/5Dfv376d79+5oNBo2bNjA+PHjueuuu5gyZUqz6YLk5GQeeughUlJSeP7550lMTGThwoUYDAZcXV0B+Prrr8nIyGDevHlUV1c3GlQ0nNNf/+9bmfJnb+3kaMedesThTdjqm3O7HC0uR4unoZCQECZMmMD+/ft5++238fT0bDJ6rJ+X39zosTn1o8euXbui1+vZunUrkZGR1NTUEBkZyX//939z5swZ3n//fVMHf+TIEXQ6HTt37mTKlCktisXR2snR4rEmmxjhK4q1tOVKjHv27MFgMDTqsCsqKtBoNKYRfkOXL1+mW7duTbYXFxeTlpbGs88+a9M39Si2T3X4Srum0gVKe6I6fEW5RUKIscB2YJiU8tvb3JcLsBf4u5TSvp6Erdgt1eEryi0QQnQCDgMLpJQfm2mffYFcYKKU8qg59qkoN6I6fEW5BUKIvwDOUsqbL3rfsv3+FpgPjJZSOvbavIrVqQ5fUW5CCDEdeAsYKqUsN/O+BfAP4LSU8iVz7ltRrqU6fEW5ASHEL4EvgTAp5f42KqMbcASYI6Xc3RZlKArY0J22imJrro6+/wqsb6vOHkBKeRmYC7wrhOjaVuUoihrhK0ozhBDPARFAgJSyxgLlrQZ6AOFtdnOA0q6pDl9RrkMIMQD4JzBOSnnCQmW6A3lArJTyPUuUqbQvNrG0gqLYCiHEncD9wFrgVUt19gBSyiohxGNAuhCiEPhBSvm1pcpXHJ/K4StKY/8NrAd+AJItXbiU8ktgM/A34BVLl684NjXCV5TGJgKDgO+A/wectmThQggnYBzQB2j5etyKcgNqhK8ojVVhHNnfK6W0aGcPIKWsw9jhvwhcsHT5imNTF20VRVHaCTXCVxRFaSdUDl+xSY62bLG9xQNqKWZHpFI6ik1qyweTtIWbPZjE3uKBm8ek2B+V0lEURWknVIev2LWioiK0Wq3p/+YYRev1ehYtWsSyZctM206cOEFMTAwrV7b9s0ocMSbFNqgcvmIXtFot58+fp1OnTmg0GkpLSzl37hwhISFkZ2fTq1cvkpOTiYiIIDU1FSklMTExzJo1i4kTJxIcHEx6ejrh4eFkZ2cze/ZsKisrWb9+vamMefPm4ezsTFZWFpGRkWRmZlJSUoKnpydpaWksXryYxMREFZNit9QIX7EL+/bto2vXrpSXG5ejnzlzJl5eXvj4+DBhwgR69uxJUFAQGo2GoKAgAgMDKSgoYPDgwcydO5esrCxcXFzYsmULYWFhVo7GyBFjUmyb6vAVuzB+/Hj0ej333XcfAM7OzgB4eXmh0+k4c+YMTk5O+Pr6kpmZSVZWFoMGDeLIkSMkJSURGBhISEgIp0+fxsPDAwAPDw+ioqJMX/X7DAwMZOPGjZw/fx5PT0+0Wi1Tp05lxYoVuLmZ7+ZXR4xJsW1qlo5ik8w1qxMLsjgAAARNSURBVCU+Pp7o6GgA1qxZw9ixYxkxYsRt7/dalpylYysxKfZHdfiKTTL3NMaGnWRL5Ofns2vXLgwGA0uWLGn2ddaYltnamIqKioiKiuLPf/4z3t7NT7NXHb7jURdtFbuyevVqOnTowCOPPIJWq+XUqVOsWrWKadOm0bt3b/r378+JEyeYP38+y5Yt4+677yYyMhKAjIwM8vPz0Wg0+Pj4cOnSJcaNG8eQIUOavdg5fPhwhg8fzquvvuowMfXp04fp06e3WTyK7VI5fMWuDBgwgJKSEgwGA1JKSkpKKCsrY9SoUYSFheHn52catY4ZM4bQ0FAOHDgAwO7du+nRowcVFRX4+vpSUVFBdXX1Tctct24djz76qEPFpLRPaoSv2JXS0lIAysvLqaqqoqamhrq6OlxcXBBCmL4D6HQ6Tp48SVRUFF999RXBwcHk5eXRr18/9Ho9nTt35uTJk4wePdp0sfNan332GRkZGbi4uODn5+cQMen1etLT09Hr9bz44ottEpNim1QOX7FJt5vzLioqIjc3l/DwcDPWqnmWyOHbWkyK/VEdvmKT7G3tGbWWjmIPVA5fURSlnVAdvmJ34uPjW/27ycnJbN26tdl1ZOrq6oiNjeXpp5/m0qVLjX62d+9e4uPj+etf/4perzfNlDGHtowJICkpiddee43//Oc/jbYfPnyYhx56CMDsMSm2R120VWxW/Tzz2NhYAgICyMnJYeDAgcDP+Wxvb29cXV1JTU3F3d2dGTNmMHDgwGanJAL4+/uTkpJy3XVknJyceOWVV0hOTqa0tJRf/OIXpp/l5OQQHR1NQkICXl5e3HvvvXYRE8BPP/3E4sWLWbNmDfPnzzdtHzp0KIGBgQCtjkmxH2qEr9ise+65h+3btzNkyBDKy8vp3r07eXl5gCm/TG1tLTU1NZw9exZvb2+Ki4tbVZbBYDD9++uvv6a8vJx+/fo1muJYP1PmdlgrJiGEqf5q2mb7pTp8xWaFhISwfPlyJk+eTGFhIc7Ozly5cgUAb29vvvjiC3bt2oVGo6FXr14YDAb6/f/27tBGgSAMw/BvNjRA6IAeaAFBF9RABRiKQKG2CdzWsQLLOgwhJKe4HCFnLrnA5nseOVmxv3nFZDIzn1fV73fKPPy8R2YYhjocDlVVdbvdar1e1/1+r9Pp9LQ9slgsarfb1Ww2G9VMVVVN09R2u63VavU0U9/31XVdtW3755kYD6d0+Ej/darleDzW9Xqt5XL5vXa5XKppmppMJi/fn8/nmk6nL+vDMNR+v6/NZvP437ed0nnXTIyP4PORxvYGrDdtGQPBBwhhDx8ghOADhBB8gBCCDxBC8AFCCD5ACMEHCCH4ACEEHyCE4AOEEHyAEIIPEELwAUIIPkAIwQcIIfgAIQQfIITgA4QQfIAQgg8QQvABQgg+QAjBBwgh+AAhBB8ghOADhBB8gBCCDxBC8AFCCD5ACMEHCPEFWxu6kfVyMaYAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "tree.plot_tree(clf.fit(X, y)) \n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Regression Score: 0.4830393038746458\n"
     ]
    }
   ],
   "source": [
    "# 回归树\n",
    "X, y = load_boston(return_X_y=True)\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)\n",
    "clf = tree.DecisionTreeRegressor()\n",
    "clf = clf.fit(X_train, y_train)\n",
    "\n",
    "print (\"Regression Score:\", clf.score(X_test, y_test))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX4AAAD9CAYAAAC7iRw+AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi40LCBodHRwOi8vbWF0cGxvdGxpYi5vcmcv7US4rQAAIABJREFUeJzsnXl8HMd157+FYw7wGoAgCYCkCIqkBIiWTUmkSEkUyY8Ta5PIsnxJUeLNJ3cUOxvntNe5r81pe72bjTfrJBs72fVms1nFifdOnISUMBRJiTJlipfMAyABcEBSwEAEgRkARO0f3dWsqame6TkwA5D9+3z6M93VVa9evXpV00e9XwspJSFChAgR4s5BQ70VCBEiRIgQtUU48YcIESLEHYZw4g8RIkSIOwzhxB8iRIgQdxjCiT9EiBAh7jCEE3+IECFC3GEIJ/4QIUIAEI/HU0IIWWiLx+OpeusZonKIcB1/iBAhAIQQsq+vj6amJtavX8/s7CxCCIaHh2loaGDZsmX09vYipRT11jVEZQgn/hAhQgDOxJ9KpWhvb+fGjRssX77cliec+G8DNNVbgRAhQtQGQohGYC2w0Wfj9OnTXv7e3l7OnTtHQ0MDkUiE1tZWJScJXLBsg1LK2Zo1KETZCK/4Q4S4TSCEEMBq/Cf2dcA17JP2BaD/pZdeYmRkhFWrViGlpLu7m0QiwdmzZ5mdnWXXrl0Ae33krwaGgH4f+SkZTjgLAuEVf4gQiwhCiATOJNtN/sTbDUyRO9keBV5w9weklJkCsrl58ybbt29ncHCQLVu2cPnyZVKpFJlMhlgsBoCU8kXgRUv5KHCXoc9T2vFSIcQAPn86wFj4x1AbhFf8IUIsIAgh4tgndbU1U+CKXUr5drl1x+PxVCaTWVMoTywWG5mamuooR74QYimF2yYp3LYb5dQbIh/hxB8iRA0hhGgG1pN7VaxPfq3ARfyviq/djlfF7mOqNvzvZjYAb5NvD7V/UUo5XWu9FyvCiT9EiCpCCNEAdOJ/ZdsJpPB/Dj4spZyrtd4LHa5dO7DbtBvoAkbwv2O4LKW8WXPFFyjCiT9EiBJgXJnatrvIvzLVt0vhlWn14d5JrcO/X1qBS/j3y215J+WHcOIPEcKA+yzabwLpBuYo/Cx6svZahygE993JBvz7NUL+4yNvq+TdyUJEOPGHWDQI8vIRir+AdFef6JNAN7mTwBLyJwDvWEo5Vkk7Qiw8CCFWkP8Hrx9nsL9zUX/2vquloHq+Wy2EE3+IRQMhRKC7cT26VAjxaZzHL1luDeJVwCD+V3gjd9Jtf4jCcB/vrcL/DnA9MMot/5HApJTyeU1Gyb47nwgn/hCLBopL5ubNmzQ2NrJs2TI6OjoYHR1lfHycSCTCAw88YE78/w+HjPC/cGtgDoURpiGqBTciuotbfwYfBFZLKR/R8sh/+qd/Ih6PezxIK1asIJ1Ok0qlaGtrY8uWLTWb+MMArhALEtpV1mZ32wSQTqdZunQpY2NjzM7O0tHRQTabJZvNAvDSSy+p8j8JnAV+AufxTLYOzQhxB8BdLXTJ3V4E/syWb2Jigrm5OY4dO8b27du5du0a165do6GhgdHR0VqqHE78IeoHbemjPrlv1rZpnMn7nPvLihUrcigFpqam6O7u5tixY8zMzPD4448r8XcDT7hy7hJCpDQ5+nY+DAwKUQskEgnPd0+dOkV3dzf33Xcfb775Jtu2baupLuGjnhDzCvc2eD32iX0TMI59Qj5nvkQVQsj9+/fT3d3tUQqMjY2RTqc9SoGdO3fm3S4LIZpwnvPbdLgb5/msnw7j82OZEHcSbL47NDRES0sLV65cYW5ujr1794bP+EMsHrhrqDeQO6GqrRu4Sv6kqq62r5dQT9VfkLl3HWvxv+uY1PQ1/xxGw5fAIYIgfLkbYlFCCBHDeXFlm9zX4bAy2ib3C1LKqWroUOslce57hjXk36VsBrbgrN7IuUPQ9sOVQSEAZ6loLBYbzWQyRb94GC7nDFFzCCGWkH/Fq7bVOBwy3yR/ch+406JRtQhe006bcP4U4lgeHbm/QyEtw50DIcRW4O+ArVLKtE+eTwIf0FcCzatO4cR/Z8Gl9fWb3FcA57FPVpfCJZDB4QYE+dm5FX87XwztHGK+EU78txncK9GV2CecTUAM/2fWIUFYDeDeWd2NvY/W4NxZ2e4WLtxpd1Yh5gfhxF9DVJFyQOAwFdom9s3kP3vWtyvhs+eFC+NdinnHsB4Yxv9FedF3KfPNuX+nodrvnWr1Hiuc+GuIMikHPo5zBR/n1kSwidzVJjmblLK20SAhaoICq6c24fxZXCPXF7YAvyilvKzJKOqD4QfVg6Paq3VqtfonDOCqMZLJJMuXL2flypXMzs6yatUqrly5Qn9/v7cO3cBPAW/hfD7vLwnXl9+xkFLOcGtSz4EbL7GO3D+E7wf6gC/qeffv308kEqG7u5vZ2VmEEAwPDwMQiUTmtxG3Ifbv38+yZcvo7OxkdnYWKSWpVMo7bxnTReXp1A6RSITx8XFSqRQtLS3s2LGjYp3Dib/GSKfTZLNZLl26xJIlS4jFYqTTaeLxOFNTUxw+fDgnv5RyY51UDbGI4NIGDLjbP7jJn7DlnZiYoKWlxaMOGBu7FSf39tu3FftwTaCoGEZGRti+fTuXL18mHo8zMzPDzZulf/vFpHYYGhpiZmaGWCzG5GR1GL/DRz01gvtcfm4hBXGEuLMghNiAQyFcLF/ofwERPuoJYYUQohX4HuB5gL6+vhyume7ubhKJBN/4xjeIRCLebaEQ4t8DX5BSvl4/7UMsdrgXHN8C/AvgcYAXXnghx/9WrlzJwMAAExMTuv/9DvAfpJT99dJ9scBvTB87doxHH32U5ubmiuW1trZy9uxZtm7dSjQarVjnopFkIUqHcLBLCPFFHBrgR4EfA9i9ezft7e1s2LCBpqYm4vE4/f393rPVgYEBJWYE+J9CiENCiO8TQrTUoSkhFimEEMuFED8OnAL+NfC/cfiK2L59O42NjfT29pLJZDhx4gQTExNkMjnfEokArwoh/lYI8YRLbRHCgps3b+bYdHR0lNOnT7N69WoOHjxYsbx0Os2pU6fIZDJcvHixKjqHj3qqCCHEcuCfAz8CLAX+CPiSlPIKlL5UyyUX+w6cu4VdwJdx7gJOzFcbQixuuFGiPwY8B/w98AdAn3p+UMpyTjfe4Ltx7hZiwOeBPwsXFtxCuJzzDoYQYjvO5PxhnBdrXwD+oZrBUO7z2R8GfgAnmOcLwH8v9sm3ELc/3GWeT+NM+PfiXHD8kZRyuEryBbDblf/PgP8KfF5K+UY15C9muBdnZ4F3SynPG+f+BMhIKf9FBfL/EdglpazqHX848ZcJ94Pc34Uz4bfjDLYv6mum56neZuApt94Hgf+EcxdwZj7rDbHwIITowLkYeB7nkeIfAF+Zz+heIUQnzh3tj+DwNn0e+Bt3qWmIKkMIsQmH4+erVZUbTvylQQjxDPAx4F04X9v5AvB37nK6WuuyCWfgfz9wEmfwfyy8C7i9IYT4UeD7cK7u/xvw72u9CMC9APkAzl3AJpx3Uk9V6y4jxDxDSnnHbrFYLIVDb1Bwi8ViKVUG+BLwBrCu3vprOkWAj7j6PlVJ+8Kt9luQfjJ88Ms4gVmJeuvu6vMunCDD7yilTYvB9yptRyl9W0ub3dFX/Avt4wjVxu3evtsFtyONwu3ie5W2o5S+NfNOT09bI6mrYbM7fh1/Mpmkra2NlpYWxsfH6ejoYGBggMnJSbq7u+nv76+3ihUhmUzS1NTkhX+r8PxMJlO18O8QlSOZTBKLxfLC/jOZDGvWFF3ksSDh16a5uTkaGxt5+OGH661iICSTSdrb21m2bFkezUo8Hi/aDnMMrlixgnQ6TX9/f17fJpNJnnnmGS5fLvyqMB6Pp8JVPWVCCCFHR0dZsmQJN27coLW11S/fgr4q8YNqXywWY2ZmhuXLl/vlW5Ttu10ghJCpVIr29nZu3Lhh7afF1ke3i+9V2o5S+lbV1dbWxnzfAd7xV/zHjx/PMXJvby/Xr19ncHDQ66zFAnfFxcPADvfX2j7zA+Vu2d8CjgCvSCmHaq78HY7Tp097+6qPMpkMmUyGJUuW1FGz8lHI98B5lLEYYGvH5cuXGR8f967+C8Hs26GhIaanp8lkMtx99915dYE9enflypUMDg7S09NTcZvu+Gi8PXv20NjYyLVr1xBCcOrUKZqamti2bRuZTGbB3o4KIVYIIb5FCPFzQoi/FkIM4rx0/igwB/w7gIaGBq9tAFNTU3R0dHjPDzXmwGmcFULHhBBDQoi/EUL8ghDiPS7tRIh5gLs6Js8HY7EYmzZtQkpZFtHXQoDN97q6uojFYuzYsYPHH3+8zhoGg60d3d3dSCnZsmULe/fuLVje7Nu2tjZ6e3tZtmwZ69evz8m7Z88ewB69e/78ecbHqxM7d8df8cMtIw8ODrJlyxYuX77sPV998803662e+jjHNm5dye/AoeD9Os5V+n8DfhbnC01SK+fbNvOlkZTyV90yAofzXdXzi8CDQojLwCtufa8AX5dV+oj6nQohxGPAH0K+D46NjTE0NMSSJUsYHR1V+b8b+ItAbxsXAGxtOn/+PJlMhpdeeqnohLlQYLZjaGjIo10+evRoUdplmx1OnTplfXF74MAB1q1bx759+wrKjMViI2U3iDv8GX+twqNLgcur3kvuI5te4DS5E+9JWeTbrFX84pfSSf/juQ84Y+h0ophOIUAI0Q78Lk4U7E/HYrHfD0CjMJrJZC4BozixGqcL5a834vH4SCaTWV0s30L/2lelY6gUioyazkf1Xie7kDbgqzhrZT9Qo/oEzpeTngU+AxwAruNMqP8Z+DjwCBCvt20suseAncCPA3+OQwY2gbO+/HM4Uc2bcS8uwk2C82j1h4Erro2Wl1i+CfgJnC9t/SbQUu82FdD1992x1Gw51+ie+y/11rOE9nwR+Bnt+KM4d1+lyPh5nEeqawLk/Rugzd3/LPBENdtzR1/xm3Bvpf8l8D4p5UCx/GXIX03uVfMOIItztextUsp0teuuBYQQK4CHyL1baQFe5dZdwStynmktFiKEEN8P/AbOh9Q/JqU8VoGsLhzGzaeBX5ZSfro6WlYPLptno/ShcnA5bqSsQ8R7vSCEeBj4finlR+uuSzjxzw+EEMtwJkF9ol/BrQleraC5rUPc3ZVG6k9O2eEG2h8B8Kq8zRkfhRCfxYlwfUJWibxPCPE54LSU8gvVkBfizkE48VcBQogo8E5yJ7gNwDe4NcEdwfkQ+h1tcPfl8d3k3hVsAwbJtdXrMuQcChFiXhBO/C6KvVjRX6i45Gi/AryNM3FtxaFm1SeuE363uSFy4d72byX3ruBeHOK5y8BVKeUPqPwL5aV8KS/u5kuHUvWphk7Vqmeh9GMp+pTyIjZI3mg0SjabLSRjLpPJFFx2X4597viJPx6Pp6SUa7LZLAcPHmRubo5ly5bR0dHB+Pg4KpLunnvuQbqRckKITwC/jvOyRi1tXDyRXosA7hfHtuEwoW6QUj6unZN9fX05YfDNzc1cunTJe3m1a9eueY8KVXro4fxqPPX397N3796aRqYqfRoaGnL8eHR0lJGRW6v/9u3bV5FONvsLITh//jyxWIyGhgZ27NhRtO2F9B0fH0cIwdTUVMX6VtIuKSX9/f1eoOOuXbuQbpRtX19fHiVFOp32AtT27dtHLBYbyWQya8y5RbVx165dHDp0KI/O4eLFi0SjUXbu3MnJkyetlDI9PT2cPn26LPvc8RO/EMIzQDab9aVuWOih5XcSgoTBu/nmfeJfSFQLtaIgqRYdw0KjTCmVXiFIXgW/uUUIweTkpK8dhRAF5yVdp1LaGgZwaXj55Ze9/d7eXs6dO0dDwx0f3Lwg4UdxkM1mEULUjHyuUDj+XXfdVRMddNjoBc6dO0dbWxtXrlxh9eqiS+vLrmdsbIxUKkUsFsuZ9MrRt6Ghgenp6ZoT1Nn8SrXJnAtsedPpNJFIhKVLl+bkNecWnbriyJEjOefMecdWNpVK0dDQYA0CC4JwVtNghmXff//9zM3dWoAhhHhehB89XxCwURyoMPrt27fXTY+2tjZ6enpIJBJs2LChZnoo2OgF3vGOd9DU1MTu3bu59957562etWvXkkgk2LFjR2CqE5ucrVu3kslkeOyxx7jnnnuqom9Q2Pxq27ZtViZbW96enh4aGhrYvHlzoLxgn3cUrYVf2YceegigbEqZO3LiF0I0CCG+TQjxf6PR6Fw0GgWgvb2dDRs20NTURDwe59y5cyxZsoRMxltc8h3AgBDit4QQa+ulfwg7l4miojh79mzN9Fi/fj0dHR3eZD8wMMDJkyeJRqN1uVs07ZLJZDh58iTDw8M5V5bzUc+JEydIp9O88sorFcm5cOEC4FAU1xo2vzp9+jSTk5MMDOSG9uh9v3z5clKpFP39/WQyGW8iV9QKtnaqOwbbvJNOpzl69GhePYlEglQqxYkTJ5ibmwt8Z5WHekfE1XLDCSb6UZwo09dxPl8Xk7L412/UV29wolF/Hyd0/svAjnq3607agEQsFpsu1Fdmn83XVuqXs+bZLh+JRqNzAe2Snu92B2n7QvtKV4lfy7pWQl5fudFotJiMm/Nhn5oO2nptOIRmvw1cxQmF3keFVAJAAvhpoB9IAs8ATfVu6+28AT04Ie//Dmgoku8t4OUa6NSGQ7Ox0j3+v8Cf1NAmLTjxImeBdwTIvw3n28zHgGiVdPg/wPUyy0rgk5b0H3TPNdbJ1x4FbgJ/XEDv3/E597qfPYATrtyokd4I/KO75fk20ImzgrALOFrx/FUPo9aw83YCf4Fzdf5vgU3zUEcT8EGcD68P4LBkLohvod5uG/Ag8HdY+F8seb8b+PN661wDmzzk/vFsKKHMPW6ZrVXS4RHgUgV9mjeJ4fBYPVhHuz4MTAGf8zn/fr8LPfei8D0+55I4keuxevrNbbec02U+/BYcMqtOnMcyfyprQAkghHgI+EngSeC/4HyY/TVZpRD9ECFChKgGbseJXwLngE8AX5V1IIFySbQ+isNl/x+llD9Uax1ChAgRwhf1vN0IspX6Ag3n5WvRRwE1ul1cDywtty13yjbfdqmG/IAyir6IC9qWWvpKqXUFzV9Du1d1zNRCb/2lrvmC1/bCt9hL4FJtseCv+P3C81OplPfNThVGXWdVi8KvLQMDA2SzWaLRKI888siiaEs1oewyOztLU1NTTli7EIJUKlVR2L5feL36ylo8Hmfnzp0F5SsZzc3NrFu3jtnZWSKRCGfOnMkJ5+/r60MIQXd3d14Yf1dXF1u2bAkUaelXn1pSuHPnzqpFtNrsoygwwLk41MeYEEImk0mee+45L48fTHusWrWKI0eOEIvFaGpqYvv27UXt/uqrr+b1W1tbG6Ojo1W1g07fYtpe1xuKzzn6WH/mmWe4cuVKHiePqmPnzp05dDHvete78uy2YcMGq2+lUimEECxfvpyenp7AtlgUE/9CCouvBEFC3RdLW6qJIKH7ldilGj4UtO+qRSVRS78v1S+FEHJycpKWlhb279/v5ent7WV4eJhsNsu2bduIxWJU6u+qrkqoIYJCp2+ppr+0tDgxn7qt9u3bh35ep2UQQuTZzZbmU28gWywKygZbWPzMzIz30ePFBFuI+vXr17l27ZoeKHbHwWaXgYEB5ubmqmIXP2oFIDAtgE3Hy5cvk06nvSvBYiH/pVBJmLKUPUrROSj8/HJwcNBrmw4VDHbt2jVWrVqFlJKpqSk2b97M4OAgKijSz2axWMz7bm0xmJQGQ0ND3mSqfqsNP9vHYjHi8XggGWbbGxsbGRkZYdWqVXnndVoGW1lbmkn9UMo4WRSRu7aweBV6vnbt4gigVVQPthD1NWvWMD097f2Lu18vuqNgs0tvby9Lly5lz549Fcu3+VBvby+zs7OBfcim46ZNm4hEIl4IvV94fSwWK5lKwpS1evVqenp6aGpqYt26daUZoIy2tbe3exQMNt2AvCjXoaEhxsfHC8rdtGkTo6OjPProo4F0s/VdR0cHmUxm3sa/n+0BtmzZEkjGnj17PDtBbgQu3LKNWZ9+To/MVfJM/9q6dav3OC4oFsUVv/mV+suXL3tXUZcvL+yv+AkhWnGohT8O9rYMDAwQjUZ5++23VbHjQojfxfmm5x3B6W/aZWhoiIGBARobGzl+/HjV5V++fJmRkRHm5uY4ePBg2TLGx8dpaGjw6AXMPGNjYxw9epSWlhbOnj0beNIAZ6IQQnhyMpkM3/jGN4hEIjQ1VXfo2vQ+ffo0s7OzVgqG9evX09XVVfSO2yb3xIkTNDQ08MYbbwTSTbfD0NAQqVSKdDpNPB6vKi1GLBYbUc/4bf6o3gm9+OKLgeQdOHCA7u5uurq6eOutt/JsperQ9wcHB/OOdZ/x80EhhHeXFQjVfBs+H9tiXQmDE2H3aZzgsS8B9wVtC/Ae4B9wAsI+Diypd3sWcx+Hq3qqW1eNV/VcqfX4vxNW9dR90JeyAXcBs8Dv1VuXAjreA/wxzoT/b4C7KpD1MPACcAX4ZaCt3u2rgf1+ELiEEzVZlQhonHB4Cfy4kd7upn+0RHkjOJxPWeBhnzz/w92ywIoy9ZbAz2vH2920dfNo/43ABHAtQN5Odzy+H7hRJO+341CmlBS16rb3zyzpO91z++bRFk1u+x7BoVlYWaacHwDSwPPAW5bzy3GoSP4Q+BN3f4l77iPANeCYlj8OTLrpT5Sj04Jf1aNDCPE4DjVCk6xDYFYhuFG7n8LhAfo88AdSymtVkt0DfBJngH0J+NdSysFqyL5TIIT4ceAPpZSzRvqHcT723l8XxQpACPEgztfdZKG02xnuI8/fkVKOWc79Mg4tR3/NFasyhBBHgBjQDIxKKR+b1/oWm/8IIRrkAqFAEELEgXfj0DT0AP8ah9RpYp7qWw/8FA6r6N8AfwQcWSj2CBEiRHkQzltc9SZXzvcf+6Kb+BcShBBv4DzaeR74spRyukb1rgR+DPg14DNSyk/Uot4QIULcJpiv52PV3Gr1oqsMeojVwPJ62QWHbtp7XrrYXoSb+gZ5geWnfyVt9yvrp0+xl3FB21EOH321+1iXV0jvUl84Fnp5WY3+ng972GSVqmNQGX72UfvFzlfa3gV/xR+Px1OZTGZNMT2rEb0nhJC1qGe+sNj0N/V1dStWxqp/JW33K+unj5le7NhPF6BoPlPvavexLq+Q3rZzQfMHtWMBOQUjZKtlD5usUnUMKkMIwYYNGzwKDtNWfvarhs1gEazjz2Qya8AJd162bFkOZwdAf38/e/furVp9yWQSKSV33303s7OzCCEYHh6mra2NiYl5eXRfVRTSf3h4uN7q5SGZTLJ06VISiQTg9HMkEsnjI2loaGDZsmUFZR06dIi77rorhyNHfQav2LdJv/a1rxGPx3N4ggBOnTpFU1MTU1NTdHR0eAO1r6/Ps7HSW/mnahfAxo0bc3h2zIGbTCa5efMmjY2NOXWPj48zOzvrydeh193c3MzFixeJx+NMTU2xc+fOIGbPwf79+70I2OPHj7Ny5UqPn+bKlSv09/dbdS3UTr0/AF5//XUSiQTj4+N0dHT4yuzo6MiJqg6qv+4zOq9OqR8j122r/pxffPHFHP3UpyEjkQgPPPBAnoyXX36ZbDbrBZqpdi5fvtyzLcDAwAAHDhxg7969JJPJHF+CW76n20/Jgls2X7lyZeCYCIVFEyE6MTHB+Pg4x44dIxaL5Xxj1fwWZiVIp9NMT09z7NgxLly4QDQaJRKJMDo6ah2ECw02/RsaGhgeHraG3tcbisBMBWlNTEyQyWS8fs5kMiQSCebm5oqGyk9OTnrtjsfjTE5OAk606JtvvlmwbHNzM2NjY4yNOYtHFKHW1atXOXPmDGNjY5w6dcr7gLpuY6W38k/Vrmw26+VpaGggFovlXa2l02mklNa65+bmrAFSet2NjY3EYjGmpqYAyvre8MTEhHdRc/XqVU/29evXGRsb8/zGpqutnWqCUv2h8h0/ftwrt2LFCl+Z6k8o6HgzfebNN9+ko6OD6elp2traSrKFOXaAPP3Un0lTU5N17pmZmWFiYsLzGdVO3bYKKgAtnU5z8+ZNrz1wy/fUeTVGTJvfuHGD9vZ2IDhtw6KZ+BOJBGNjYyxdupRTp06RSCTo6emhpaWF9evXV62eJ598kkgkwtTUVE6IeE9PT10+nl0qVqxY4dkJblEfJBIJb0AuJDz55JM0NjZ6k53Zz7FYjK6uLu+D1IVg9ltXV5fXbxs3bixYVumgyipb7dmzh0QikRMmb9Zl6q3aZeqTSCTYunWrN8DB6a9r1655dB2K0iAWi/HYY49Z22yT29PTQywWY9OmTUHMngOlu012a2urRzGg95Vqt62d6o9Cpdvsq/LY2r927VqklIEpLmxzQ2dnJ3NzcyXPDWZbbLqr+SCdTnt3NDoaGhpybGSzk4LyBXVetQdu+Z6ug7KZOcZXr15Ne3t74Kcf4TP+XBmL6hm5grsU7EPAXwV8tny3lPJCwYw1QPiMP3zGHz7jD5/xWzE1NdUhhJADAwM5/BSZTMa7ranmM364xbGh15fNZgMN0lpDCLEL+CywBOy6j4+PE4/HPWZH4FUhxJ8CvyUtgTG1hK6veaz0T6fTtLe3F33HYvqIYoBUPPillFW+ZdPHzB+kHYpF0bwV98sHzm27zbf1uoPkLwalg00fxRxrO+env2LdVHradPazr24n9Xw8qP46r05LSwupVMr6qKwUWabu6v1DJpMhFotZ36kEsZNKGxwcZPfu3Tl9oP4MbP3i115dp0AotuxnIWwLdTlnPTec0Pq/BAZxAroaS+AC6sShlRjB4QKKLIR+rXA550gFZcPlnEX0Dpdzlt8/C3E5Z90nsBInu6e49XhqLbBjnuuLAtF6t9vQqRX4DA5Pxy8CLRXIegfwf4BvAh9Qtq1j21rcTQA/5DpyIJ2ACPAfMD67Cfw08HgJOix1dWgM4g8+acPAKU1exO0337YAa3DC9WMU4YQBvgXYqR03Ax+vgv2fVzYHZtz9ZT55A9lCS5fA4zhPGaJAg5GnDeedY7t5LqDu36XKufp/VwV2EGoxckycAAAgAElEQVQS1dI24MbMAPcGlNPgttX0yRZ93Lp1/bF2/GdaP0gcni5PH3f/S+75suaoBf+MP4QDIUQj8DLQDXwF+BUpZbAvWRSX/QTOn0kT8EUp5aerIbcSuO19XEq5v966lAohxCZgTi6A9yilwLX5binlAZd7aq2U8qtVkv1u4J/kIplw3DExIaUMxtldWV2P4pCwTbrHS4B3SCkPCyF2A68Au4FZt2+2A9+UUo77Sy1S5yLphzseQohO4BTwYSnl1+ZBfiMOm+RNKeVT1ZYfIkSIBYRKbw+rvVWL97zUZ/FBn3WWK7+CttbtncJ86Vfo2X6pz5mL6VOoDYWezZfz3DXoc/AgaaW0tdJ+Koc7PiiffJD8JbQ30LifD/qOIDqW8nw+qP/YzldjflpwV/wlLM8Kkifwssugy9rKlV+szvmsp1zMl35+yzi7u7sZGBjwtX05/VKoDYWWYdr2C51XS/PMuoIugyx3SaiUUlTST/py6e7ublKplLdeXEdQW+jHen8WW5JYQnuL5tH1LSLLs4eyQ6GyxeovZSlmIf/R+yEajZLNZnPOV2N+WpDLOZPJJFNTU3kh9Pq3PJPJJEuWLGH16tXMzs7S2trKyZMnyWazZX+jVYVaQ36Y9ujoKNPT02Sz2ZI+mF0MKlx+3bp1ORQL8Xicd77znVWrp1zYQupV5GElH0FPJpO0tbV5IenJZNJbxrZ//35Wr15NIpHICcFX53R7qX4HfOkKbG1QvqRTNejHkBsyr8Lo9dB6Pa+ue2dnJ8uWLfPyHThwgC1btuRQjejUACpND+tXsuLxOOvXr8/Jd/36dW7cuFG0jaOjo0UnCTXZ9fX15bRBobe3lzVr1uTQOtgoBfTxoo71ZYm6jmpfUQ7oNjZpWdTSUBU8aY5LfSmjaQ+dIkGnn7AtecxkMmtM+gS9z5QeNv8bHh72ltQqOgV9LlE+ofepaT9lK30cKH3087otpbxFzbJixQrS6TQXL17Ul237YkGGoqbT6bwQevVPrjg80uk0o6OjXtjy1NQUsViMFStWcPjw4bLqVaHW4Pzrm/WPjY0xOTlZVli8H1S4vAo3Vw42NTXFpUuXqlZPubCF1MdiMRKJREXffb3vvvvyQtIVJiYmSKVSnk3OnDnjDVbTXmfPnvX+IPxoGfyoBiCfqkEdQ27IvPILPbRez6vrPjQ05OkHTnSmTiUBudQAKk0P61eybty4kUNfkclkkFLmRWHb2jg1NcX4+HjOBZMfdG4c84Peut11W+j2MevW/2yUvZSOQA7lgPIjk5ZFyWpoaGDVqlXWenToH143KRKuX79OOp0uGBtg0ifo/ePnf+fPn8+JKVKTvT6XKJ9Q++pPW7efrrepjw41D5rULNlslnQ6zerVqwONy/BRj6Xe8FGPV3dNH/UUu01fyI96FBbbox4hhFR6+9m/FFuYeXTZC/lRj7JhoTrm81GPgs1uOm7rRz19fX2MjIywatUq75nXypUrOX78uMffYcuTSCT4xje+wSOPPFJRvYXkX7x4kfvvv7/iNgq3R231tLW18eabby6IRz02/VpbWzl+/HhRxsugstV+sTr9zq1cuZJz58752suvjHnO1EnXy9TPltdWVylpNpvYfHBgYCCvrX42++Y3v8mDDz4YqC8UbFGmtr7y0zWIvYLYRI2FK1eueBxEfn359a9/nd27dxe0hzmHmFCPUYL6i94n6ilA0Hab+4X00VFsnOi6FMKCfNRz8+ZNtm/fTmNjI729vaTTaU6cOAHAwYMHffOcPn2aSCTiPWcrt16b/NHRUU6fPu0xPlYCIUQHzkfU8+rJZDKcPHmS2dlZj7pWON9ZrQtsdu7v76epqcnri0plq/1169b51qmoEvx8Q7EzBm3D0aNH884BrF+/3nsccODAAY/kS/3qabr+6hmuWZcus6enx5NtS1Oy1bFN79dff52pqak8VkibH6lnyIo2wQY34tmzfzQaZd++fXR3d7N7927WrFlj7SszTW+PrT8L5fezSSqV4o033vAoI/zaefToUWKxmDdebPmGh4c5ceIE09PTnD9/3mqHffv2WcuOjo5684/fvDAzM5PTVj8/8dtX/nPgwIGcflAMobp/+bVRPfrW8/hCyvov4dS323k5J06k3UdwqBJ+M2Bb08AV4DeoURSxq+cvBbTzTZxvDgeO+g2Xc4bLOcvs23A5Z4m+4TvG6z3RF5h8OoCfd/fXAL9QIO9BnC/TV6vux10D3g1ccve7K5R5D/BV4DjwUIllO4G/dcvuZZ6pFYCrwBDQGSDvBuAt4HwF9W0E3gdsBXa49r4XOAuc8SnzDA4dwj8PWMePAk+5+03An6CF0gPn3Hp7gEYcttNvw6FaUJQDGSDh7n8c+FN3/zPu7+eAOXf/x9zfVq2Op5QOWtqTaFQkmk13A8/i/Al/0JXVUaSNfw2s145/DfhICf2w3m33EuAHfPJ8zNXlr3E4oqSrvwQO49BVHNPyC5wLnSTOBYx02yZdm58wfcfVYRPwaAFdPwQsB76nQJ6fAt7p7n8H8FyJfrnP9YdngRXGuXfjUJ6826fsCeCC5i9jwD+4+8+5Pv+U6/MPuemncOhTJLfmoKuazGY3LYvD0yVxLrokDuFi8LaVO1gX0gbsBD5WRXlx4LPu/vfiPJbJ424pQd592sRQ1lW7O4C+25XzK/Nszx8DNpeQ/37gh6pUdxT4nLv/EeDbauRDH8GhwmjyOf/nwCfd/V/F+d7xXcCvuP37P91B/FvAH+JwSf1alXRrBX6nFnYIoEsXToT3bhwOos8By3Auap4CfhDYa5R5DucP7nngr9wJ7CuuzZ/F+DO8HTbVLnfc/ld3TH2ra6eVRt4o8DfAd7pj/Cuujf4K+BGLH34KeNT1ubuA3wbaStFvwa3quR3hvsh9RFaB90MIcT8wKOtMpxwiRIhFjHr/M5byfNF27LdVg0qgkNyFQrcQVI+FRG1d6Flopc+/y3lWXOrz6iCygz7n9quvGlTG5TyvLse2pY7RoPYOmlZKfaXkKdZH5diuWu8PKx3Pdb/iL7YGudj65unpaesHlStdX64CWkzZ1Vg7XU0E1QOgFvqWEodRbH24md/vuFDeYnmmp6eJRqN5etjymuUUIpGId6xkBV37XmgNvK0d1VrfX6p80076+ChkM5udgto7aFrQ9fWFUKiOoP5nm5sUbH5h5oFb9sR5JOydFEJ4E5GUcrrS+WdBrOM/deoULS0tjI+P09HRwcDAAJOTk3S7X5zRz+vH27dvz1nqpcP2Z1AIkUjkLXBCoZ9++mnefvttb4mWCRX0kkwmaW9v98LzV65cydmzZ8lmszQ3N5dUfyVIJpM0NTV5of2K9kGfkFQ+IQTd3d05oeiRSMS3reXq09bWltOninJDRam+/PLLXt5nn33W21e/zc3NXli82UZ13NDQwNzcnBe+r6JMDx8+7NmitbWV1157jdbWVqampjxah2QyyQc+8AEvUvLMmTMe3YDSaXh42Dt++umnvf33ve99XL9+HXAiNM2+1pe5qjapCE3VB/o50791O5h2NG2hUzmkUqk86gLVLp22QC0FtY07gCNHjni2b2pq4p3vfKcXhfryyy/z1FNP8fbbb3vflrX1z9q1axkeHvZso6JQVX5Vt7KX8knzWJVPJpPEYjGPzkHvZ7PPV65cydGjR4lGo56tzbaOjo5y5coVEomE15cvv/xyjj+ZfaHqN220cuVK3njjDc/mZtsVdJ9/5plnGB0dzZkrlD2bm5uZmZnJCiG85ZzgRIo3NDR4UcSmH0QiEY/PRy1P9sV8P4ootjkqSJlKpaQNgMxms3J0dNQ7VvnVvl+5UvUAPLmFZCv5o6OjcnJyUo6Pj1dFh3I2pfPs7GxBPWqlr6pH7zNbPdls1tPJtL2pp9nGQnUABduoy0O7LVZldJ1UXpuOuo/ox0qW6acqTbVNl6XymfXZ2hi0v1Vf+NnCb9zZyuhtU/1mtl/vs0K2Mes26/Or32yz2WfF/LqQP/rZw88n/eoz22e23ebzZj69vH7OJi+oH9i2BXHF/+KLLyKl5PTp0wBewIV5dWjmB3jhhRfyIuwKBawUg9IB/CP4lPzjx4/n3Lb19vb6kkbNJ3Sde3t7uX79OoODg7S0tNDe3u6ds+k7MDBAJBLJ4QipFLZ6zO8kqz49fvx4XjvM8mYb/epQ/C2K0E1Pz2Qy3Lhxg9WrV1vl6WWUTipK0qajgh5JacrS/VSl6XorWab/q/psbTR1ULaNxWJMTk7ywAMP+LZLt4WtXiXfLKPDHIu6jcw+s9lGpdls46ezrc1mPrPM0NAQDQ0NOXcqNjvod1KmPfR6zfbZ7Kpk+LXd5vNmPnWs5jW/fDabqCDHYpxEsEAidxsaGjxSKHDIpTZv3szo6CiQSxoFsGfPHu9Wxi/Ct1zot0h6JGEikSCVSnHy5EkvOtGm99133+3pWCuYpFpNTU1s27aNSCTChg0bvHw2fe+55x4AHn/88arpo/pH1ymRSHh2VDqrvHo7bOXNNvrVoW6Bbend3d1Eo1E2b96cU5dpQ10nFQFp01HBFiVptiNomqpfPRaxtdHWvkQiQUdHBw0NDXmTr80Wiv7A5g+ANa1Y+802+NnGzG/qaNO5WJrtfFtbG5s2bfKVqeywYsUKj5bCtEehPvLzPdN3bLbT/cnMp471aPJC8kw/UFQd9957b15+HQviil+FHitukMuXL5NKpbwBoJ/Xy6xbt857D2BCfzYWBLFYbCSTyaxRcq9eveoru5De6hmb+uevBUw9xsbGPPqCl156qaC+ig3Uj9myHCiuFyFEjl1SqRRdXV1ALgXCunXrGBwczAl318ubuvvVodqyfv16L31oaIiBgQEmJia8Z8MqT1dXF2+99RbZbNYro9DZ2YkK4dd11MsBOWH1gCdL11HpXyxN1e9nB5O2Qu/vVCrF1NRUHqmXbguVr5AcIC/NtJPZflsb1q1bl2cbW35TR5tetnbo+Wxlrl+/zokTJ3KoFPTz586d8+5AL168aPWbQn1k5lW+p/uO6Re6LDXHmPnUsbKNOucnT2+TrodJ6ZEHv2dAtdoW8XLOt+ZDh/nSOVzOmdPOcDlnuJwzcB2343LOuk/8niLO3cdBnHDxB4Gv+uQZAf6fe7wL+H2c0OrPVFmf/+Ua8BHLOeGe+1Wfsqvc879RQ/vtAb7s7v8h8MEC+f6Xu79X7c+TTv/ErZD5r2GhqgAOuba63/09ixPFeA2HkuEmbhS1m/9ngD8CHtD64jxw3JD7OPB7wPspTPfx28AvAe93jy8AJ7Tz/xfno9vgRNBKnAjU/+3u7ywg+wfdPPe6v8e4Fba/A4feYRD4T27a08AM8Mda2wZdG72EQ4fQoMn/AvA9wE8U6YcITsTnvwS+1ccGc8BPaml/j0ObsBp40VLml4BJYIORHndlDbn6/zHwRV1vy1i6CYy7/TWBSxWCQ8sggbvd4xU4VAWbgD/V0iTwpnv8ORyqirx2uud/CPgF4FMF7PUp4OeBH9bSfsStp8f9fc1N/zzwm1joJfChknHTdZ//6QrH2XIgDXwpcJn5GPDzueGExP9qDer5BXegbfQ5v8/Pmd3z9wOr622vhb7h8NwM4VABXHIniU+6A7gBeBXoKiLjx4E/rJI+fw58r3b8KPD37n4LzuQdA37R1bu7gKyom38NzgT+eeDX3XJ3Af3uRPbjrq9tw5nkN2oyfg74LM7k/Mvz1AfPuvU/UUKZ9wN/bUlvUu0KKEcAp3H+aJ4D/sKQdRRoL2LjS8B/nGc/VX3Z4fbl7wco8+3YL2B/z7V3F/A60FIF/f6IEmhr6h7AFSJEiBAhaosFsaqnGhDmW60QIUKECGHHfN4e+W3lcKRXwOE9ry95aymrmMxqv/CqVhtLfeFaCf970LQg+6Xaqty+9vsWRKltrrYflGqLMl6E57yELrUfKslfLE85L5Tn209KmVOKyajLox4hhHz11Ve98GsVVh+Lxdi1axf79++nqamJZcuW8a53vYvOzk4uX75MX19fTij/hg0b6Ovry6MrGB0dJZ1OE4/H2blzJzIg/0w8Hk9JKddks1kOHTqUFxI/NTXF1NQUDzzwQGBeGyGEtMnq7++npaWFHTt2lMyRY9pPSod6YdeuXZw8eZKWlha6u7vp6+vLCXNvbm7m4sWLtLW1cc899+TZs7W1lZMnTyKE4OGHHy67jaoPhBBMTU3l9el73/terly54pVXYfx9fX0eVUJfXx/t7e309PSQTCZ57LHHvL7etWsXyWSS5557zvsgvekHyjd0Sg3dX3bt2oWUkmQyye7du+nr60MIwWOPPcbBgwf58Ic/zPDwMNFolGw26+mmljX6oa+vLycc37as2ExX8pVep0+f5j3veQ+XLl3K0Uvvr7Vr13L48GGv7yKRCGfOnEEIwd69e0kmk3R3d7N27Vr6+vry6C0eeughrl696tWt20n5ya5du3Lq3LlzJ4ODg3m23r17d04/xGIxtm/f7umg6CKOHDlCLBbjgx/8oGdb1f5Dhw559ek+YBvvej8cPHiQubm5nD5Udar8qu27d+/28is7rFmzJmecKHspeWaf6/1kjq8NGzZw6NAhnnnmGc8eCrb+NulT0uk06XSarq4u7rnnHt+xJ4SQfX19fOd3fqe37NSGaDRKJpOxj996XPFD4VByk6JBbbaw7WrSEOh1BQn7r7St5ehYSKYrx5f6wMxbLdsVa2OhPgXkgQMHPH3Mvlay/dL279/v6xuF/MXPVkpXXbaSpfb379/vbSMjI/LrX/+6PHToUF4bVLv82mvzbb1tpl4mbUWhvjUpKGzUD2YdNn8y6/Szq96HSt9C+pk2MGksbHqZ9i3m72bbTT+0jQNdB10Xpa/eT7b6dL/UfcTs70rGnm6HAwcOFPRHPxl1C+AyQ56Hh4e9f1UzLFzBFrZtC2sfHh5mfHzci6arhn5DQ0O8/fbbxGIxLwipXFkqgKapqYmlS5dWRT8VsKGHwvtRSqjAuCDUCuXqMzY2lkMD4denQI4+CnpfK9m2NBVJafONYv7iZyulqx6FqstqbGz0qDxOnTpFt/uRa7MNql1+7dVha5upVyGaCZOOwU+GbotC55WPmnWaaUqWzadsY1y9ijNtYOtjGw2Ebl8o7O+2NJO6wZZH6aDrovQtpp/ul4rqxYx+tpXV58Ag85ayQ0NDQw6tjGI9KEZbU7eXu2a4cWtrK1u3bs07V6gM+NM9RCIRHnyw/G+U20LAt23bxvT0tMfQV66sRCLBxo0buXbtmhflWal+ioNGD4W3hfy3tbV5UYE2223atInp6emSKSdsIew9PT0eA6Nfn4I/NYIeHu+XpiI3g4b52+xj7puy9TSlr/nBbzUh6BOa30evC4Xfm3WVQm2g0zGYFBQ2Wyj4+YGtTj+7qjYpWbZ8ra2teVHLpn1tbTepOmy6F8pfiGrBL4+pi9K3kF31MiaVjAmbzTdu3EhLSwvvete78vKb0KkhzLrOnz9flJ2zblf8esizCrdX4cZmeL4e0m+GcvvREMzNzXH+/PmSdIrFYiPSfcZv6jc+Ps6VK1eIRCI0NZVmNlvYfH9/P+B/VViOTIVCIf8DAwNe3X62a2pq4uzZsyXp40cjMDk5mafv2rVrc66mVRg/4L3P0cPx1Z+jmdbV1ZUzkRTzDd0mhfZ1OhD1jF+n8tD1tdnBLxxfb69f+L3etuHh4Ty99HFh+kAmk8mZiJU80w9sNAx+/qnXuX79ei5dupSXv6ury7NJIRqFsbExTp8+nUdpoNNcKPsNDg5aqTuUj6h3KIXaaaYV8wmdjsHWl8Xsqved6jOFIHQL4+PjJd1p67QiNhSkrfF7BjSfW7iqpzIdw1U94aqecFVPuKqnEhl1mfhzFHAi9k4Duy3nPg/8P+Ar7nE/TmjyFpzQ7l9005uA68BG4MvA31ZRv78FxoBIBTI+5naGWkX1j8CpCvX6PWBSO34FeNXI8xZOlGEEhwrgzy1y7nVtGcWhqfhyhXr9b5yQ/biRLtGia90+lPhHRh/HiXB9Boca4AngHPA2TjRtFoeu4DBwWbPt88AbwB9pst4PnAD+u5a2CzgD/IN7nAZexInKven65b8FZoFerdyngGl8KAG0fO928/18ifb7drfcz7jtuOimC9fH3wS+A5jiFs3EX+BQHsQs8v7StXMCh27gTSAJfMCS92vu9q8s574BfBAnSnarm/YakAEaLfkj7rj5Ck409k1gbYD2nwRuAA+4Pvu7OB+z/yaQ1PKtdv3hddc2a906vgh04lB/HNPyx9y0M0Ajznjx/MbNs8HN86p7fAkYBXpxxsintLz3ub7xb4HNrn6HtfO/6OrTWaS9P+H2d9kfnMehNzlcUplKBnmtN9e5Z939E1QpTL9InUfQwsgrkCMKHc+HTNehbuDwH80BHTWw1+vuRNNmpC+x5M1L0849hzPJ/wvgqps25g6mp3D/9NzB/+lK7ejaajcO98uc618vuPuPanl/39Xhu4rIfNbN9/kSdflet9xncf74fsFNb3DT33KPR4Hn3f0D+FzscIsXpnse+nrQlW29KAL+G/Ayzp+oBO4LIPOqa/NvdX8DXYi4E7EEvhYw/3ngd4rkuQ7MuPungX+nnXvU1S+PtsI9H3H7q6dIHb/r5vuhCvphCvhnpZQJKRtChAgR4g7DbUPZECJEiBAhAqLat3+FNr+XWMWOg740qjfXdbW48XXZlcgs94VgubYr1W7V9IdK0ir1l/kaI8X6p5T+LOXFaAUvLm8GyFPS+Cv15X7Qvg/iU0FsW+hl8Hz60qLi4wekgr5f6HjDhg3WfRsKnTPyBNazFDlByxXLp8suRaayTzQa9RzRIrdQnYH10rdYLJay1VdMhs0fNmzYkKO7eWzqqvZLTbP5lbKbbYIoNrDVn2+QfIXsp+us66X3r55mg22cFDoO4ie2/rBtep6gtlDtt/ltob4s5BvF0grJNPdtfuAn2yxTTT+Rmr9UOtfVfB1/Mpn0ggu+9rWvEY/HWbZsWc65u+66C3Ci8lREajKZ9Pb3799PZ2enxy2iOGbA4dK4++67Pc6RiYkJhoeHicVi7Ny5syQ9p6amPP06Ojo8/pnx8XHfcocOHeKuu+7K4d/IZDI0NDSwY8cO33wA4+PjvlF+K1euzOFRiUQizM7O5sgcGBjgwIED7N2710vbv38/8XjcW5v84osv0tjY6LXp1KlT3kft9+/fTzQazeEyuXDhAvF4nHe+852+bc5kMmvUvm5/xdkDzgegdb3Mtqn69U/Gmcfqe8Jwq39UPvO8SksmkyxZsiQvTfclP7spqLXSepoeablt2zZisZhngwMHDnh9aubdtWuXl8+0n9JBtc3Ua2BgwNNB6WTzDX3M3Lx50xtvyWQSKaX3XWjTnnpem38eOHAgx25m+x544AFrH+r5otEoZ86coampiYceemiN3n4dym/h1gfMk8mkd76vry+vHrVu/cCBAzntNdMANm7cmFeP7hdq3+YHZjkVRavaHtRPgtjGBmUv2zx4/vx5a8CYiZo/40+n015QT3NzM2NjY943NNU59b1YffDojZmYmGBoaIhjx44Ri8U4d+6cFzI/PT3NsWPHuHDhAo2Njdy4cYNYLEYmkynpu7LpdDpPv2w2Szqdtk7OCkp/NWGqNkxOTubUb+ZLp9NEo1GWL1+eJ/Pq1as5bYrFYrS0tDA3N+cF2iiYAWETExPcuHEjx6Z6mxKJhKfjxMQE09PTjI2N0dHRkdNusx4/6PbXA3QAzpw549s2Vb+pu5lXyVD9o+fTz6u0dDrt/fnoaWYdpt2CRKyqaPMLFy7klPWLJl+xYoXVZno5s21+euk20X1DD9pJp9Nef6tj1T82e+p5Tf+E3Ghbmy10e/rlS6fT3HfffV5Etx+U38KteSCdTnu+ND09nZdfpSk9VXvNtGw2m+Nzqh6dfE/5iF/EuV7u6tWrOW0P6ifl2kbXwZwH1UXmhg0bCpat+cT/5JNPEolEAKfh2WzWM6o6pyZWPez4ySef9PYTiQRjY2MsXbrUM6yiUVDlTaNHIhHvXz4IVqxYwbVr17yJeGpqiu7ubmKxGI8//rhvOVv9PT09LF26lHvuucc3XyKRoKOjI8+h/fKuXbuWWCzm3R0pmKHwuq0g1+ZKluIsSSQSXpsVBYCynVlP0PYnEgl6enoAcqIvzfyqflN3HXv27PHSnnzySc8/VJp+Xs+n/E1PM+sw7aaHwtvSVHj8iRMn8u4AbZQOR48eLXinqOugfK+QXgp636o/GAVlIzWhmePLZk+V1+xHlaawfv16Ojo66OnpoaOjw4scN/vMZosTJ04UpRRQfgu35oEVK1Z4abouKr+ymTpny2/aQK9Hl6l8xOYHfuV0X7L5iXklbuYbHR3l/PnzRf3E1EGfB3t6ekgkEnmRwyZq/qinUAi6LXRaD11XodyF6B78zjU2NnpXUUFgozNQIdWvvPJK4HJjY2McO3aM9vb2nCt+U8+BgQEmJiasXDZmiHx/fz8XL16ko6Mj54pw3bp11lB4M6Rcr3dkZIS33367oO2gMLVEMaqLVCpFLBazylD5le1UiLySpVMLqDyQ70d+afq+nk+nATHtBrm39Sq9UHh8LBYbAZBSrgmSz0zTyykfUlQIijZC6al0ymazeb42NDSUR/eg7Ot3bDvnR4Gh+sdvYtH7LKjNVPtVuknFoPefnqb7ii3/7t27vUc8pj+YtBK6TDUfmZQI+rjyoxTR+6hQm8vxE/1cJpNZY6N9UONVfwxmQ03X8QshpKrP5XrXz/ke++1b5PueM/IU5JjX9SxFTtByQEE9ddmVyCxm40J5i+nlc74ku1XTHypJq6TN1YafDW26ltKfQe1ZTl1l5Ak8/oL0Wzl9X8gGxdoRRHa5bQ+KcucohZpe8cdisREhxBpw/j31q9tCx377Jgqd03UoRc9S5FLG8TUAACAASURBVJRSrlA+XXYlMovZuFDeYnr5nS/FbtX0h0rSKmlzteFnQ5uupfRnUHuWU5em+5wQouDj41LHX5B+K6fv/coFaWsQ2eW2PSjKnaM8+C33qcUGfBJn+dKnKbD0CIeXReKG+HNr2dMf2Mqh8cRgcMaUqN99aLQCwCYMKoIK279G219NFWgcXFnvd+3jKw+H6uCkJV3oWxl1fxuw1JD3wRJlHHH1/4B7nHGPl2t5Lrtpj7q/q7lFF/GU+zuLwx0kgR8D/pW7/+/d389pvvQzhXywHhuw1dXtkpbW6qbd0NKaNVs3B5Ttu9yv0Dn3fLubZ12N7DAL/GfXtyQOR5PEoaqYcvdXuHl/wD3+R23eeML9jbh+8wqwzk1bpdUz4frLjHsuj/vIopuawxS9h8Thl5KUyJ9TgX1+xK3v74KWqStlg3D+ItfidMYaKeWwT74OICqlHHCP1+M09DKwWkp5uUYqLxoIIdZLKS8VON8KTEspb9RQrUAQQiwF7pJSnnSP1+AMwgEtz0ogIaU8p9oqhFiOQwR2SghxFw7/zhgOEZ36gofyt/vdNPVxhSGgS0rp/y27OkAIcQ8OV9GYltYNTEkpy76CVGNISpn3xY5C57Q86wqdrybc/h+VUs4IIdbh9NVWHL6dZWi+4c4p78AhW1uBO28ofV2/mZRSTpltEEKswuGHakWbb4roJnB86QywEmiSUl4UQtyHQ7A3UVBAFaC3WUrpv+RQL1PPiT9EiBAhQtQBtbgVUVsx3vEgYc9wKzS8GhQE1aBZKDX83a89hcpVIzy/XqH5pu2qQZsQsN+C6FkVmoFaj59KfLAWFAbl2rMQjUc1ZBWba6rZloW81bYykFLmh5SrfT1ND8fWf/WQaT2/iULn9DzVyGdrS6l6FEsLUr8eLm47H0Rmufr65Mnpd1t5XXdz0PlRJ9goHUwfKTVP0LbM92YL57fROfjomLevjk36B9P2pny/PvKbAP3qLqBr4DnCr/9svuLX/7oNbG0qRMdgwpybzDpr8SdRKe1Dzdfx6yHdyWTSCz5RodQqjFwPDd+3b19eSP2hQ4e88y0tLaxbt86jCRgedl4VmPQE/f39xGIxpqamcoKpCtEzqCANXceNGzcyOzvLypUrOXHihHdOrRU2Q+Nt5QYHB7317SqPOq/iDfSwecilQ3AHCRcvXgTg9ddf98LF9+3bl2MXZSdVz+zsrLc227SRyqOoM3TqiWw269VrUjMMDw8TiUSYmZnh4Ycfzut3sy06XcCpU6fyqABsNAnmumc9xB7I8xFVvlgenTpE9f3IyAixWCzHT2oBnb5B2Vr3/5dffplsNktbW5unqwr4UX0Ouf0D+XQeOs2Ffk6nOVB2UfltdATRaJREIpFHfaB8bHZ2lqamJi5duuTRjBTDyy+/bKVqUXYx26D7iukjOu2L6WM6LYNJx6DseODAAa8dUkpSqVTe3KSjVLqOcmHzk1Lqq3nkrh7SnU6nvWg29auHkcOtqD0z+EfRPkxMTDAxMeGFLavAEXDuZnR6gkgk4hlJj6Kz0TNkMhnS6XROxJ4e7n3hwgVu3LjhBXWokHe1r4fG28qBE3mnvrGpn1d16mHzkEuHEI/HyWQyXmSxao+KXtTtots9nU5z8+ZNXwoHlcdGPbFixQovstikZkgkEkxPTyOltH6v12yL3s8q5F31t05JUOgj7WYkpC1AzKQQsOWx9b2i+bhy5Upe/lrApH1Qes/MzDAxMcHY2BinTp2ira3N80HV55DbP7pMBZ3mQj+n0xwou+j5bTQD6rzya93HLly4QFNTE9FolIaGBubm5oq2fWZmxtsv1Mc2XzGhT4pm23VaBvO8yqO3Ix6P5wT52eorl66jXJRNDzIv2hSAHtKth90rRfUwcsiNitOhh0nbwpYhn56gtbWVTZs2EYvFciIP9XB1PW9PT0+Oo6kQcD1EftOmTda26Pls5dauXcvk5CSPPfaY1x5biLxKg/zw/LVr1+bRW6hoQpOqwaQw0Mvp7Tbz6Pbo6OjwroTM87FYjJ6eHqanp61RnWZb9H7WbWxSEujUACZM5zZ9RG93oTx+fd/W1sa9996bl78WMKkClN4NDQ05NCc6TYNJI6DbW5eh8oLTD/o5G6WKnr8QVYOq2+bvd999Nzdv3gxElKh0UrJMuygoXWznFGyTs0nd4UdzAnYKlkL1BaX1qBZstA9Hjx4tSolRl8hd5Yyqbr9oO5VHP69g5rfU5XtOz6PrUW6+QlF/JUT0FUwL0la/KMJi6cV0CaKvTx5r9LHNXjaf0I/1NAU/nygnT9C2zDeEEOpBt1l/YH+39bOS6TeubOOv0PgMWncBXa32tM0Rfv3nN1foKJRWaG4p1JZi9ZXT7lJh85NS6qsLV4/Oh6G4NNSvnufq1as5UXE6V4Z6zqY4RnROHfX4pNA5nQzNL9/s7CyrVq0qmE91vI33xOQg0jlV0ul0zjPPgYGBHLk2OXqesbGxnHcEAwMDdHV15eljs7OfTFu9uj0ymYxHhmeWE8Khq25vb/dI33To+W320vsbbvGi6ANLv83OZrM55VTecvP4tdd29zKfULw1Zrtt/ar8QEG3qWnvdevWeW1XbVbo7Ows6MdqX8mwwc//TX9/4IEHitpAnyMK9Z/NV/z6f3BwkM7OTo8Xy2yTPrf42XFoaIiZmRk6Ozu9d4B6fbpONlQ7ctf0k5Lqq9Zb5qBvorGsVAiXc4bLOYPK8pNZgZ7hcs4iMsLlnAvfN0rd6lcxvOoa70Pu8RTw98BeN/0MToTl8SJypt38T7u/y4zzDcC73f13A41F5O1HC4f3yfMR97cJ+E7LeQn8EvB77v6fuukbgPXA3ThRoma5GPAQsBy4X0s/4cr5Vrc9W/XzhoxNwBqg0z3+Bbdss1aHBL5XOa+bvgXoQKORcNMPAuM+dT2DS6MAvM8sa8mvIgzv59ZjxkZXj48Af6VsV6IvfdUt9zMF8rzh5nmiQJ4xN09HvcZFCW3ejkNBsNP0aW7RFjS4/iaBd7jn7gHuMfpEAn/MrQlN9c3/wKEvULQXPwkswYmE7izQx3PAl9zjfuDNMtuofON7gL9093+lTFnH3PIfcH9ngWatXd5YMMqlcKhAet08eeN2MW71dtxP44RGg8Mvs9Ht7N/B4WD5VuCdReR8yJ3cmoHnq6DXJuCpCmX8IBB3J9LPAhsqlPcI8Ls44eCllm0DvsdHv5/F/RMrUP5e4Ml59oWPuv2+GfgMJfIhuTp+BpevxSfPrmI2xOGC+XU18S3WDeeC5Hnt+KNAQ4H8HwTuAr4P+Ektfb07vnqK2deQ9wHl88DDwO4q+Mbd7lhqL1PODpwLsWbg54APu+nfi0Pt8HHg+yzldgM73P2PLXbfUFtI2RAiRIgQdxrq+a9je2ZZ6nO1IM8Ey30XUI3n6n5pQZ+vl/PsVt8v9VlmOc/9y3leejs/P631OCllv1R/r/Yz8SD9GvS9WzXsaJFb9P3h7eCfNb/iF0JEAKSU0+Yyv+npaaLRKMV0ct9kq9fpWZU/yHKzQuemp6dzPr9WynJRU46tHcWWvZlpppxiyzGLLcFT7Ssk15a/2BK9cpb5+ellsb/vsgXdl+Y7Tz1hjhM3rWj/BVmSqa9u031Cpau0cvrY7E+jTKF+lZX6hpbPOt/ocuFWXFChcVNqOxYyarqcMxKJvNXc3Nw2MzPjLXs6deoUTzzxhPcJNXBCqZubmz0ahtbWVk6ePOnJcSkNsuBE+R0+fNgL9Eomkwgh6O7uzqE2sKWryL1kMsnTTz+dE/WroGTrstSHx5PJJO3t7bznPe/JkaOi/sw69bapfRXSvmzZspy0D33oQ94nEZUc0zamDIAjR47w3ve+F4CDBw/m6ZXNZr36jx496i3P1G24du1aj/ZCIZlM0tTU5NlCCJGT58yZMyxbtszrr/Pnz+fJVTKeeeYZq142CCFkNBodyWQyHXq6zZdMRCKRuebm5oZK88RisZGpqakO68kaQbevrf+ULcGhPHjqqae8dN3f1O+zzz7L8PCwd05Fy6qyyvdUGjhjtaWlhfHxcTo6OhgaGsqrW5fth0KfQI3H4yldZjm+oaB8pKGhIWf8mGNBjxQGx//1vLZ5Qde33r5RFmp5e4F7i6Sg9vV0QI6OjsrJyUk5Pj4ubcC45VJ5/coCMpVKydnZ2TyZ6pyul37OTw9dptJDydGP9TrNMqOjozKbzcrR0dGctmezWascs32mDKWvbheVx7SxaTd937RFIfsVspNf39jsVQju+YK+5FeuWnnM+mu52exrs61qi+4/us2VvVVes/1mWVOelFKmUqk82+h167LLsWc1fMOUZc4tZpopr1ptWchbzQO4wCGQGhlxYgtefPHFnHSA48ePq44DcomHVACWjiNHjnj7trIAp0+fzpOnSKXUuRdeeIFVq1YhpfQCOHTZvb29OUFgusxixzY9TF390gqVMY91fdX+8ePHvTRlY7+8er6RkREvgM1sy9jYmBfkZpZX9jXTTV11mXp9yv6KzK4QgpSrVp56wrSvmab3sbpCV+nK5sreKq/uCy+88EJeWVPeiy++iJTSk6P00OvWZVdiz2r4hg59bjHT9HGvo1ptWYioOVcP5PKx6Lwcivtiz549eWRQra2t9Pb2eo9EdOhkTTbSIj2PLq+rq8s7B+RxbNjKJRKJHC6gQiRRZtliuuppQdun28rUwUZwp/OLmOX0ek2uGLMtsVjM4z3ys6+f7jZ7mZwjmUyGo0ePev3nhyDcKDY+k9deey0nj85Bk0gkSKVSvPHGG1aOoHogiC/peRWUf+jpJj8P3OJ4snG86OVseuhjWJdt9qdisg3aXoVKZSkZpq4qTZetQ9lU943ly5eTyWQWlG+Ug5p/bF1KuUanMtVDsvV01dl6GH0qlcphIwQnxHr9+vXeRGgrV0geOB3b1dVlDc9XsvUyihlUyezq6mJ4eJibN296bdH10kPr9T89UydT5ltvvUU2m/Uto+zX3d3ttV+1Remjyug2VmH7ut30/XXr1uXRzZp2GB8fJ5VKeXc/ZltUe219Y7OXWZ/pN7Y005cseeaklA1B8tj6vlD9tYbNV0zbKmoCfV+nH1D+oMac8gUgJ49OkaD8T5VTvqb3sY1ioZDNTZoDHbFYbCSTyaypxDf0c1LKNXCLutmcb6LRaN64N+240H2jLNTzOVO4nDP4crpS6wyXc94+W7icszq+ES7nvLXVXQFPEWh3DTqgpUXdtJ8NKGOHm38XDvXDzwKPGnl+HiciMY8WACdK8FPAEiN9M/AzwAPAj1rKfRsOZcRPu8fPunp8RTv/CWCbVuZRV+ZenMhcCWzXzj8BvBf4OS3tnJtvNfAunEjLn3DPLXXPXXWPPwH8S5wQ+kvuuTbgAvC6JjPhnrvsHn8S+KS7PwR83WjrL+NEMz5rsYMAfgUn2nOnce5ncagENgP3uXUe0+qcYRFQJdR703y0RUv7PrevVwNfcG37kzgRt5/AiYpf6aZfBL7m7n+7+/u2pZ433XPrtLSX3LR3u79jRplGV7efco+n3HxlR7vijOmfBb61ynZc4+p2vkCeGTfPD7u/f17v/q9a++utgGbkJhz+nl/V0gTwNxj8OwVkCOAFYGWd29KNww3yXMD8K129Cw4Qd1I9isu7Y5xrAF4GPmM59xvAK+7A/D40Ths37TDw25Zyv8k80DUAy4DXtAliO/Af6u2Dt8PmTubH0C4y3HQ1vn4d+H43TyfwIvB5i5yfc30tqqU975ZbBSSBf1NElz8DvlZvm/jo1uzaw5cXCvivODxF97ntfl+99a7WFlI2hAgRIsQdhrqs6gkRIkSIEPXDgpz44/F4SgghC23xeDyl8sVisZxz6tgvPei+X1rQ/MXqKFeHoHX65S1Hp1KOi+ka5Jzez/X2x3pBHwfF+qpQ+nzZ1U+/SurzG9Ohb1QZ9XzOFIvFUn6rPU6ePCn7+/vl66+/LkdGRuSRI0fkoUOHZH9/vzx06JCXv6+vz/tVZQB5+PBhCchXX31VDg0NyYGBgRy5qszBgwe9/VdffTVnXy/X19cn9+/f79WXTCbl0NCQJ3PdunU5KwF0uWpfL9PV1ZVX76FDh7zzKn39+vWeXD3vwYMHZVdXV06dp0+f9tqul1N1mTY27XHy5EmrjQ4fPpyjl94O006qb/r6+rx9m33UvpI1MDAg+/v75bFjx+T+/fvl4cOHpXSeQ8p6Pw+t12bzy/3793t2t9lWHw+dnZ05q3L0TfcHvU9s47FQOeUPqu91v/PbCq2G0f1YjZ2+vj5vHnjttdfkoUOHPDuUOt+Y/m/R7WYxOwVpx0Lf6vqMXwjnu5EHDhxQne6tt81ms9y4cSPn48ZGWQBSqRQdHR2Mjo6yZMkSbty4QVtbG5OTk7S0tDA5OcnMzAzLly/3iJdGRkZyykSjUUZHR4nFYrS0tJBKpWhvb+fGjRteOZv8mZkZVqxYQTab9dYmHzhwgL1793ppeh16GQVVV1NTU855Pd2W11an3mb1UXQF08aqjG4PJVNP022h66WOTfuqunV7Snnr26RKD9XPenm/fpaLlAirUgghpOmXa9asybGz7geQOx7a2tqAW/6hQ/cHcKJw16xZA8D+/fu9dHMNvelHpv8qv9Nl9Pb2Eo1GOXPmDE1NTTz00EO+fSqEkLoPqTFnmwdK9Q0hhFS2MPVTzAC7du3yba8t72L1zbpQNphoaGjIoQeA3NBxk7Jhw4YN3jk9DF3vIBXOblIRqLBzs4wttF3VXUi+qauK9lNpejlTF7Mu/bxJ/2Cm2er0a7PKo9tYldHtYYbm2/Qwj826dJoIJUOn5VB62MrrVBrpdJqVK1fmteNOg+mXyv7KbibFgknLALlRvXqaTkOgR0g3NjbmjUdbOb0+XSeAa9eu5chuaWlh+fLlgaJdbT4EufOAihgvFcoWpn6bN2+2UjDY7OSXdzFhQTzjN+kBwE4B0NPTQ1tbW04knS2cXE/X5UAubYAezq6n28LSTaoEP5oEFeVYSK4OP9qEIHnNOm3n/Gysypj6mXYx7Rfk2GZnUw+zTXo/d3Z20tTUxObNm/PacafB1hdqX/9VMGkZIJeaQU8zaRAUdIqCQuX8dAKsFAuKBqUYClFEqHnA9mcWBDaaBkUPolN42Nqr6D5OnjxZlEpkoaOuV/y2sHtFJ1CIYmFgYMDLrzu1PqkoKmCdasDMY4azB6FSUP/0Zn4zvFzVb5MLuWHhus5qArVRN9hC9PU6bfpks1k6OzsxbayOTf387KLa7WdP3S42O5u6mrQRigIglUrx9ttve+Rvdzr8fFT3L72vTVoGnZpAh40GwaRv0NP8yvmNg0poDmxjWo3FoaEhUqkUDz74YCERvvXu27dvjY2mQcszJ6X0/lXKpYtY8Kj3S4ZCL2EKbbFYLOX3ssYvzLzUMHe/tKD5SwmfL0WHUkLrg4boF9Pp/7d3rrFxXNcd/13xsUuVEGlLMumaqmjZskU7ftRybaU2bBpBkKAKkPaDG6RPuAYKFGj7MV8MFEgQF7WBFCgCNGiQOEUDtGgKN3VTp27tOEuDSmnDsonItCi3kURZtkjKFpcSRe5SpE4/zNzx3cuZ3dnlYynO+QED7p25j3PP3L07vDPnP/Wk04bxb/Ww+LX8HqSRX0gjy7CWfk0jl1Jve2luwOrYWP3WdANqGhi84HgJ5yXQCfnuApaBfySIKhSCF0gL8Crwr8B5IB/mvxt4GXiOIOK3BHxIELG4RPAS5s8D/wU867Rzf7jv2wRLZWXgTHjsu+F+94XVfxPWd2do3x+F9lj7rgI/C+2+Ctwb5v/fsPw3CV4+/22nzhPAePj5ea9fLcAk8N/AC2Gd/eGxM8AiMS/eJohknAb+A3gptO+W0OajwPfCz78W9nsY+FPgr8PyL4R25ML090Of/npY7jthf18F/jmm/R8AP8WRCNCtwj8GmCeIJn0qHCO/H/rsAvAH4fFPh/mfC/3+IDBGFWmCNbJvMGzvb4F3ws/5Vdb5Y28cvtXs87BVtk1xc7cGCwSTVa1FtasEk/ClcCsRLGUthOmLwIsiUgIQkZ8DnwUwwfpJKcx3OWyvLCIvEUyCESLyJvC5sFyL0yYi8mSMXV8HfpdgAH9EEMb+xbA9W/5iWEc5zLcQ7kNE/iymziLBxEpY7sdOv5aNMf9CEI5fCuu0Tx5cJNDmWYGIXDHG/JBATqE1LEtYfjZsZxG4KiJXCfR6XGaBH4mIfV3SVwn0hpbCOuZE5AyBzktc+78dt1+JMAQ+/hrB+Fsk8OvTBPo8JeCUiNi7vRfDPMsEFx9/vM72WXvmQjtXvjijfubCegyffE+UNUAlGxRFUTLGpniqR1EURdk4tvTEXyvkfTUSBo3IRNQKPfelKuptu97w9lrSGPXY1aiMhIbmV6ea72v5XX2qJNLsmwxxW5yUg7/Zp3riQtJtGiqlA6z8AHwiY+CXc/PbUHRXqsGVP3BlJdz8w8PDFXIKbtq30Q8Nt+1bSYTx8fEKuQQbzi4iFSH8fX19FXXa+mqFnif5wU9bH9i+2j5BpTyF20+7L85XvlyGL90wPj4eSTeE/W36uGzG96DWeIJPpD5c6Yabbrpp3Z+Kifv+rbY9W+dWl0xo9tZ0A2KNCk/s0NCQFAqFaJuampK33367QqvH5ktKX7hwQebn5wWQyclJWVpaSizn57HlyuWyXLhwYUU5EZHJyUmRwOiKdvw6/XaSbLb2zs7ORnXaz25fbNtJ/bE+89OuH9P4z27WB7avbp/K5XJkX5w/43x14cKFqJztx+zsrMSR1Yk/afz4aXeM+OfRP+/FYlFef/11OXr06Kr9Wm3c+d/XUqmUqr16+pDVcbEW26Z+qidtuLQfxeemk6QY4sr5eZLC4n25Az+MvpbMQTWbq0lD+DIIbj6/Tht2b4kLUa9li0uSNIB7zJUJ8PP5vqomkWHD8gGVbaB+2QxL3PenHumEtMSNu927d3P8+HH6+/vZuXMnp06darjupD4ojbOp1/j9cOliscjY2NiKMHU/JN1NJ4W8x5Xz89QqV00mwq8zrm9x6bg64yQm/Hx+nb40Qpwfa9kS5xdfmsH9HPeDkWRvkiyEDcsfGBigra1NZRuoPZ7i5D0gXpZhbGyMixfX9qlId7y4cg9W5O/dd99t+IcmTjLhgw8+4Pbbb18r8zPJprzij5NyiMsDYPO5oeU2XS6XE0Pe+/r6VoSyu1IRNr9fzpU/sHW7Mgr2rxtGv2fPnkh6wbfRTcfV6co0uH3x81m7bJ2uNAKQGKLul4uzzZfQcPtoZSf8frvlLP6PkT0WJ9swPT1Nd3dsyEFmyOfzU6VSqSdOlsEfX8YY9uzZw/T0NOVyORrftepfrX3+9281Ug1unTa9ZSUTmk2z15rWc6sV8u5vq5FVaEQywW72JpUvVVFv22naSPLPau1qVEZCQ/PTj+G05159qlutrekGbGhnA0mBnwO/QxAdexg4Cbwfk/cpgmjE24AZghczPxGW+wyB/MHpMO8hgmhFm34f+AWB5EMZ+HK4/y+BK4QSCjVsbSeIRv5+mJ4K63wKyIXHniN4UfscQTTvNuAN4GIDvjkKzKTI91w4eXSE6a+EfrqHIDJ5lEBKYAH4vFPuM+G+J4C3gaJzrEjw8vUnQ3891uyxshm30Idl4Ikw/Reh728J0y+Gx1tjztf2Ztuv2+bZNvUa/1oSyjLsAu4AHgDywH3AzUBfTJGHgXPA/xHIHNxNMMHnCfR09gB7AURkRES6RKQ/LNsH7JNA8mGJQC8Fgkm7FdiXwuTdBKHqj4Rt9IjILSLyNNAbHhsUkY9FpFNEuiWQUriTQDOoXj4FdBtjao2JPw//3hTa9SyBzs/tBD9CnyLobx74VafcveG+TwMDwLecY38HDIjIdwl+8O5pwP4scDfQLiLfC9MPAR+KyC/C9IME/nPfwmMlP27aGBOVa4FMSTbYSU1ErhpjWiTQtYn2eXkNgX+u1lMupp1tbh4/ndbetMfC/SJ1nthqbcXljetTnJ+8cq7vIht9X6f1TxZx/eP6zR6D+DGhPlVcMjXxK4qiKJv8cc5mkEbGIEkKYq3kCNLUv1GyB7UkA1bTJ5UWSEc950B9qqSi2TcZ1nNzX+oQJ0dAwtMQe/fuFb+c/4SKxc/vpm0+Nx23xT0949bv1+Hu9z8nEeZZ4Z80T4DEtb93796q0hNxfvbtrdc/WdzsmLBYX7lp3+/qU91qbZvyOf61olQq9QwNDfHoo49G+wqFQvRscKFQiPYPDAzQ0xM8PjwxMYFfDqjYVygU6OjoiM3vpo8cOcLExMSKtmx06r333ks+n+/x7XXrt3W4ddr99ln4I0eOsLS0xP79+1laWmL37t1MT09Hr6tM8k+cHzzbKBQKUR8GBwcje3yf2LRIsHzoxiZYu23wkduHOP/kcjlOnDhBa2srBw8ejJ7rzhr2HA0PD7Nv377I78eOHWPnzp1R2vpvcHCw4nxZksackk22/FKPH03qRj26kaj+y5PjolDdfXNzc1y+fDkxv03bF0zHRafeeeedK0LZbTm3fluHX2exWIwm2WKxyPLyMqOjo5w6dYpLly4xMzNDd3d3zffX+n649dZb6erqioJy5ubmoj647Sf1263Pt3t+fh4gkmRI8k+xWOSOO+5g+/btKLC4uMjo6GiUPn/+fEXajd51z1fci8rfe++9jTVe2XRs+Ym/mhyBL2NQrZy/r7u7m5mZmZrtdHV1Rem48Pmkdt36Dx8+HFvn4cOHo8m4q6uLmZkZOjs7gWAC37dvH5cvX+ahhx5K8E68H06ePFkR1m8jaP32k/pt64vzhe1Te3v7ir5thLzAtUp7e3vFxYmftlIJUHm+fJ+Oj4/ri+wVXePHW5NG1/h1jX8TbbrGr9t6bPo4p4cxRk6fPs3Zs2fZv38/586dwxjDzMwM/f39kRZJoVCI0m7+1fzGrwAACPVJREFUnp6eimP2sz0+MzNDsVhkcXGR9vZ2Dh06hIgY34akOh5++OForV1EGBoaitZ13XbOnTvH7OwsuVyO66+/nttuu21FO2n9Ede+31apVGLbtm10d3fHthXXpzi7rX8Aent76e/vb8jurUTcOXDHnNU32r59Ow888ECiT0ulUuT/rPs06+jE79HR0TFpb6jFYYWhbB4rBmdx0/6xpPoWFhZ6k2xIqn8t2kmD74+17NN62r2VqOccqE+VNOjEXwVjjABVr46MMc8Q6NX8E/DlcPc2AmmGRbe8MWYCuCIiqbWGw+jMdoJ/0dsIdHmuikiLMeY3gR8CxwikJzqBR4Eh4LyI3JC6s+lsaSWQimgVkQVjzADwLnCdiBSrl66o5yCB9tEHYX2/TKBD8xNgQUT0jm4CxpgFAumLXSLysTHmK8AzcWPUGPMk8B3gZyJS/UaPkim29OOca8AgwcRUja8CY8C/A98EOiX4Nb1ijPkNAuEyy6PUeUM9rMtewi0aY74A2Gc0XwB+DxgGdhDoA71mjHkceKeedlLaYu8KXgnTx40xj9Uz6Ye8BXyJQNANAh2fnwK/BZxKKqQAgV5Uv4hYje9vAP+TkPfvCcbOqxtgl3INoVf8iqIoGWPLP87ZTGrJP8SFz9symyH0vlGZBZUFWD8aGVOK4qMTv0dHR8dkrcmto6Nj2Z0I/UnR/i2VSj179+6t2p44bxuC4KaxiFAulxERbHkbTJXL5aLPItIT1/5aTQbWFtce+7fW5t8gd/1qbV4vu7caru/sOUkaV7lcDhHp0R8GpRq6xu+RUsZgG6yUcBgcHMSVXBgcHIykFtwlNbe+Q4cOrbDBtu1LNbhyE3FSCTZPQjsNhegXCgVuuCG4R/zKK69EdnV2dtLd3c3s7Cy9vb1MTExEUblxWL9ulN1bCXdMDg4OMjIykihzYYO34saclcF48MEHM+/TrKNX/AnUkjGASrkCGy5v97kvv/ZlDNz64rAh975Ug1+ni5vHbefmm29elezB3NxcpPfT1tYW2VUsFjl27FgUidvW1kY+nwdIvBqtx+5q/skqNhra/sD6PnOjpePGXEtLCzt27Nhgq5XNiN7c9XAe4ayWB5vH/+z/TVOX+yieMUaS6oprz+LmSdNOGqwtTvmqbdTq10bZvdXwfVfNZ42MOSV76FJPAhMTEyuid9vb2zlw4ECUZ2hoqCK/u8+m7b64SEp3AnQZHh6uSCfVmZTHj95dzY/78PAwU1NTK+yy+3fv3o2I0N/fT3d3N2fOnOGuu+5KrC+N3dY/Vs9HCbDn354H32euEmvSmFMUYGtr9TSypdGvyefzy3G6P/5fQPr6+qrWlcvlxG0fkEKhIPavLZ/UXlz7CTbXrc0CyOnTp2V4eFjsZ0ItmEKhEB2bmpqS0dFRGRkZkZGRETdfrF/X2+6ttvlj0h0XceMpxfjNvE+zvulSzzpSS/4BVobP2zKbIfS+UZmFjbAtqzQyphTFRyf+DcIYswS0ANskpdONMf8GfBH4E+BbBFfRTbkh78pXGGM+SyAb8BLwI+BzwB+KyD80w7asYox5FXgM+JKI/KDZ9ijXDrrGv3E8DfSknfRDvkHw5NULwD3Ax9WzryvPAL8EICIv253GmGcJJBz+s0l2ZZm/ItBuerlWRkVx0St+RVGUjKHP8StViZNt0KhQRbm20Sv+dcYY0w4gIouNlGmk/FoS9yw/BO+ABVY8cqnPiK8/zR4TyrWPXvGvI+3t7R+3tbWVgXLaK2RbJpfLlY0xUm/5tbYf4Pjx49Ez5EeOHGHXrl10dnaSy+UwxlRsEPxY6JX/+tDImFIUH73iX0fSRgFLTISrLVcrUnY9r7Bd+6empujt7WVycjJ6qXez7MoyjYwpRfHRp3o2gOeff74iwnXnzp2cPXu2Igo4Dhuh2Wj5teK1116LJprx8fEK+/zoXWubsr6o75XVoEs9G8D9999PS0sLAwMDlEolxsbGWFhYqFlueXl5Rflischbb73FpUuX1tvsiEceeSQSAHOFwJaXl1fYNjY2VpFHWR9835dKJY4ePZpqXCmKXvGvI/l8fkpEevr7+6vmiSsDMDg4SC6Xo57ya0k+n58qlUo9VvcFggmnr6+P8+fPRxLRG21XlrHjQ32vrAZd41eqEifbUA2VC1CUzY8u9ShVWVhY6BURIyKmVCoZ4DVgFvg6MA/8ij0uIkYnfUXZ/OjEr9TL14BhYBR4UUTeb7I9iqLUiS71KIqiZAy94lcURckYOvErVXG1etLo9WjUqKJsfnSpR6mKMUZGRkZ4/PHHmZ6eplwu8+abb3LjjTeytLSEiFAsFimVSnR1dTEwMKBRo4qyydGJX6mKMUbm5+fZvn17tG9+fp4rV66wY8eOuPw68SvKJkcDuJSavPHGG4npgYEBPvzwQ8rlMvl8fqNNUxSlAXSNX6mJL8HQ0tLCRx99hDGG48ePc91113HgwAG2bdPhpCjXAvpNVWpiZRpyuVyU9jV6JiYmaGtra7KliqKkQdf4laq4kg1QW7ZBJRsUZfOjV/xKVVzJBuC5crl8Fdgbpt8BSkCLSjYoyrWDTvxKPfQBBugK07uAHDqOFOWaQpd6FEVRMoZeqSmKomQMnfgVRVEyhk78SlU6OjomXX2efD6vej2Kco2ja/xKVYwxAlAoFACi1y3aNATRu7lcjhMnTtDa2srBgwdVtkFRNjF6xa+kwkbrWmzkLsDCwgItLS3s2LGD++67r1kmKoqSEp34lVTYaF2LH7l78uRJisViEy1UFCUtutSjVKWjo2NSRHpstK6VbdDoXUW5dtGJX1EUJWPoUo+iKErG0IlfURQlY+jEryiKkjF04lcURckYOvEriqJkDJ34FUVRMoZO/IqiKBlDJ35FUZSMoRO/oihKxtCJX1EUJWPoxK8oipIxdOJXFEXJGDrxK4qiZAyd+BVFUTKGTvyKoigZQyd+RVGUjKETv6IoSsbQiV9RFCVj6MSvKIqSMXTiVxRFyRg68SuKomQMnfgVRVEyhk78iqIoGUMnfkVRlIyhE7+iKErG0IlfURQlY/w/TuH6FMyQo0wAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "tree.plot_tree(clf.fit(X, y)) \n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 决策树详解\n",
    "### 信息论基础\n",
    "首先先来几个概念,我们后面介绍决策树原理的时候会提到,这里可以先扫一眼,用到的时候再回来看.\n",
    "1. 熵和信息熵\n",
    "\n",
    "熵，热力学中表征物质状态的参量之一，用符号S表示，其物理意义是体系混乱程度的度量. 可以看出,熵表示的是体系的不确定性大小. 熵越大, 物理的不确定性越大. 1948年，香农提出了“信息熵”的概念，才解决了对信息的量化度量问题. 同理, 信息熵越小,数据的稳定性越好,我们更加相信此时数据得到的结论. 换言之, 我们现在目的肯定熵越小,机器学习得到的结果越准确. \n",
    "\n",
    "信息熵表示随机变量不确定性的度量,设随机标量X是一个离散随机变量，其概率分布为:\n",
    "$$P(X=x_i)=p_i, i=1,2,...,n$$\n",
    "则随机变量X的熵定义为:\n",
    "$$H(X)=-\\sum_{i=1}^{n}p_ilog{p_i}$$\n",
    "熵越大，随机变量的不确定性就越大，当$p_i=\\frac{1}{n}$时，\n",
    "随机变量的熵最大等于logn，故$0 \\leq H(P) \\leq logn$.\n",
    "\n",
    "2. 条件熵\n",
    "\n",
    "条件熵就是在给定X的条件的情况下，随机标量Y的条件，记作$H(Y|X)$，可以结合贝叶斯公式进行理解，定义如下\n",
    "$$H(Y|X)=\\sum_{i=1}^{n}p_iH(Y|X=x_i)$$\n",
    "这里$p_i=P(X=x_i),i=1,2,...,n$.\n",
    "一般在基于数据的估计中，我们使用的基于极大似然估计出来的经验熵和经验条件熵.\n",
    "\n",
    "3. 联合熵\n",
    "\n",
    "联合熵是相对两个及其以上的变量而言的, 两个变量X和Y的联合信息熵为:\n",
    "\n",
    "$$ H(X,Y)=-\\sum_x \\sum_y P(x,y)log_2[P(x,y)] $$\n",
    "\n",
    "其中: x和y是X和Y的特定值, 相应地, 是这些值一起出现的联合概率, 若为0, 则定义为0.\n",
    "\n",
    "对于两个以上的变量$X_1,...,X_n$,一般形式位:\n",
    "$$H(X_1,...,X_n)=-\\sum_{x_1}\\cdot \\cdot \\cdot\\sum_{x_n}P(x1,...,x_n)log_2[P(x_1,...,x_n)]$$\n",
    "\n",
    "性质:\n",
    "- 大于每个独立的熵\n",
    "$$H(X,Y) \\geq max(H(X),H(Y))$$\n",
    "$$H(X_1,...,X_n) \\geq max(H(X_1),...,H(X_n))$$\n",
    "- 小于独立熵的和\n",
    "$$H(X_1,...,X_n) \\leq sum(H(X_1),...,H(X_n))$$\n",
    "- 和条件熵的关系\n",
    "$$H(Y|X)=H(X,Y)-H(X)$$\n",
    "- 和互信息的关系\n",
    "$$I(Y;X)=H(X)+H(Y)-H(X,Y)=H(Y)-(H(X,Y)-H(X))$$\n",
    "\n",
    "\n",
    "4. 信息增益\n",
    "\n",
    "信息增益又叫**互信息**,它表示的是在的得知特征X的信息后,使得类Y的信息的不确定性(熵)减少的程度. \n",
    "$$g(Y,X)=H(Y)-H(Y|X)$$\n",
    "\n",
    "\n",
    "5. 基尼指数\n",
    "\n",
    "基尼指数又称基尼系数或者基尼不纯度,基尼系数是指国际上通用的、用以衡量一个国家或地区居民收入差距的常用指标. 在信息学中,例如分类问题, 假设有K个类,样本点属于第k类的概率是$p_k$,则该概率分布的基尼指数定义为:\n",
    "$$Gini(p)=\\sum_k^Kp_k(1-p_k)=1-\\sum_k^Kp_k^2$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 决策树解释\n",
    "\n",
    "决策树是什么东西？就是我们平常所说的if-then条件，我们把它组合成树的结构. 决策树中有两种结点，叶子结点和非叶子结点. 其中非叶节点代表的条件，叶子结点表示的实例所属的类别. \n",
    "\n",
    "我们如何生成这个决策树呢，最主要的一点就是选择那个特征作为当前树的分割结点，这就叫做特征选择，有了特征选择就有了决策树的生成，最后我们还有进行决策树剪枝(后面会提到为什么剪枝). \n",
    "\n",
    "看个统计学习方法上的例子:\n",
    "\n",
    "现在我们有下面一张表的数据，想生成一个决策树模型，预测某个人是否符合贷款条件. \n",
    "<center><img src=\"https://i.ibb.co/xm7d5LV/Screenshot-from-2018-12-27-17-32-10.png\" border=\"0\"></center>\n",
    "\n",
    "现在假如我们通过\"某种方法\"构造了一颗下面的决策树. 从下图可以看到特征对应的是非叶子结点，如果这个被分到这个叶节点，就预测为这个叶节点的类别. 从图中我们可以知道以下两点:\n",
    "1. 每一个叶子节点都对应一条从根节点到叶节点的规则，这表示决策树是if-then规则的集合\n",
    "2. 如果一个实例到达了某个叶节点，一定表示它满足了从根节点到该叶子节点的所有条件，而后才得到类别，这不就是先满足条件再得到概率嘛，我们一般叫做条件概率分布. \n",
    "<center><img src=\"https://i.ibb.co/3TQDgwH/Screenshot-from-2018-12-27-17-47-01.png\" alt=\"Screenshot-from-2018-12-27-17-47-01\" border=\"0\"></center>\n",
    "\n",
    "> 问题来了，为什么我们要选择是否有房子作为第一个构造特征呢？我们构造学习模型，会遵守经验风险最小化或者似然函数极大规则，选择损失函数，我们如何根据风险最小化，选择特征呢？\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ID3&C4.5\n",
    "\n",
    "### 数据\n",
    "\n",
    "给定训练数据集\n",
    "\n",
    "$$T=\\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\\}$$\n",
    "\n",
    "其中，$x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)})^T$特征向量，n是特征的个数，$y_i \\in \\{1,2,...,K\\}$表示类别. N是样本个数. 基于这个数据生成决策树模型. \n",
    "\n",
    "### 决策树\n",
    "\n",
    "常见的决策树模型有以下三种(CART决策树既可以做分类也可以做回归):\n",
    "\n",
    "```\n",
    "1. ID3: 使用信息增益准则选择特征, 相当于用极大似然法进行概率模型选择. \n",
    "2. C4.5: 和ID3算法相似, 只是用信息增益比选择特征. \n",
    "3. CART: 递归构建二叉决策树, 回归树:使用平方误差; 分类树:使用基尼指数. \n",
    "```\n",
    "\n",
    "| model | feature select | 树的类型 |计算公式|\n",
    "|:-----:|:--------------:|:------:|:------:|\n",
    "|ID3    |{分类:信息增益}|多叉树|$g(D,A)=H(D)-H(D\\|A)$|\n",
    "|C4.5   |{分类:信息增益比}|多叉树|$g_R(D,A)=\\frac{g(D,A)}{H_A(D)}$|\n",
    "|CART   |{回归:平方误差;分类:基尼指数}|二叉树|$Gini(p)=\\sum_{k=1}^{K}p_k(1-p_k)=1-\\sum_{k=1}^{K}p_k^2$|\n",
    "\n",
    "其中, $H_A(D)=H(D|A)$.\n",
    "\n",
    "从表格中，我们总结(ID3,C4.5)决策树算法伪代码:\n",
    "1. 输入:数据集D，特征集合A，阈值e\n",
    "2. 输出:决策树T\n",
    "3. 如果D中所有实例输出同一类$C_k$, 则T作为单节点树，并将类$C_k$作为该节点的类标记，返回T;\n",
    "4. 若$A=\\varnothing$,则T为单节点树，将D中实例数最多的类$C_k$作为该节点的类标记，返回T；\n",
    "5. 否则，根据**信息增益**(ID3)或者**信息增益比**(C4.5)计算特征A对D的值，选择当前最优的特征$A_g$;\n",
    "6. 如果$A_g$的信息增益小于阈值e，则置T为单节点数，并将D中实例最多的类$C_k$作为当前的类标记，返回T；\n",
    "7. 否则，根据$A_g$中的每一个不同的$a_i$,根据$A_g=a_i$将D分成若干个非空子集，对于第i个子节点，以$D_i$为数据集，以$A-{A_g}$为特征集，递归(重复3-6)构造决策树$T_i$,返回$T_i$.\n",
    "8. 对决策树模型T进行剪枝.\n",
    "\n",
    "### 过拟合和剪枝\n",
    "\n",
    "决策树建立的过程中,只考虑经验损失最小化,没有考虑结构损失. 因此可能在训练集上表现良好,但是会出现过拟合问题.(我们构造决策树的时候，是完全的在训练数据上得到最优的模型. 这就是过拟合问题，训练误差很小，但是验证集上就不怎么好用.) 为了解决过拟合,我们从模型损失进行考虑:\n",
    "\n",
    "$$模型损失=经验风险最小化+正则项=结构风险最小化$$\n",
    "\n",
    "思路很简单,给损失函数加上正则项再进行优化. 正则项表示树节点的个数,因此有如下公式:\n",
    "\n",
    "$$C_{\\alpha}(T)=C(T)+\\alpha|T|$$\n",
    "\n",
    "进一步详细定义,解决问题:\n",
    "\n",
    "\n",
    "重新定义损失函数，树的叶子节点个数|T|,t是树T的叶节点，该叶节点有$N_t$个样本，其中k类的样本点有$N_{tk}$个，k=1,2，...,K, $H_t(T)$是叶子节点t经验熵，$\\alpha \\leq 0$是参数,平衡经验损失和正则项，得到计算公式如下:\n",
    "$$C_{\\alpha}(T)=\\sum_{t=1}^{|T|}N_tH_t(T)+\\alpha|T|$$\n",
    "其中，经验熵为:\n",
    "$$H_t(T)=-\\sum_{k}\\frac{N_{tk}}{H_t}log\\frac{N_{tk}}{H_t}$$\n",
    "这是有:\n",
    "$$C_{\\alpha}=C(T)+\\alpha|T|$$\n",
    "决策树剪枝优化过程考虑了在训练数据上的经验风险最小化和减小模型复杂度两个方向. 因为加了正则项，所有我们基于贪心的思想进行剪枝，因为当剪掉一个树节点，虽然经验风险增加了，但是模型复杂度降低了，我们基于两个方面的平衡进行剪枝，如果剪掉之后，总的风险变小，就进行剪枝.       \n",
    "算法:       \n",
    "输入: 算法产生的整个决策树，参数$\\alpha$        \n",
    "修剪之后的树$T_{\\alpha}$        \n",
    "1. 计算每个节点的经验熵\n",
    "2. 递归从树的叶节点向上回溯，假设将某个叶节点回缩到其父节点前后的整体树对应的$T_B$和$T_A$,对应的损失分别是$C_{\\alpha}(T_B)$和$C_{\\alpha}(T_A)$，如果:\n",
    "   $$C_{\\alpha}(T_A) \\leq C_{\\alpha}(T_B)$$\n",
    "    表示，剪掉之后，损失减小，就进行剪枝.\n",
    "3. 重复2，直到不能继续为止，得到损失函数最小的子树$T_{\\alpha}$. \n",
    "\n",
    "\n",
    "\n",
    "**4. 动态规划剪枝**.\n",
    "\n",
    "可以看出来上述算法是一个递归问题,存在很多重复项计算,这里我们使用dfs+备忘录进行加速计算,这种方法和动态规划类似.\n",
    "\n",
    "算法:       \n",
    "输入: 算法产生的整个决策树，参数$\\alpha$        \n",
    "修剪之后的树$T_{\\alpha}$ \n",
    "1. dp[所有树的节点] = {0}; 保留所有几点的信息熵\n",
    "2. 计算每个cur_node节点的经验熵, {if dp[cur_node] 直接返回, 否则, 执行2}\n",
    "3. 递归从树的叶节点向上回溯，假设将某个叶节点回缩到其父节点前后的整体树对应的$T_B$和$T_A$,对应的损失分别是$C_{\\alpha}(T_B)$和$C_{\\alpha}(T_A)$，如果:\n",
    "   $$C_{\\alpha}(T_A) \\leq C_{\\alpha}(T_B)$$\n",
    "    表示，剪掉之后，损失减小，就进行剪枝.\n",
    "    \n",
    "$$dp[cur_node] = C_{\\alpha}(T_A)$$\n",
    "4. 重复2，直到不能继续为止，得到损失函数最小的子树$T_{\\alpha}$. \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## CART\n",
    "分类与回归树(classification and regression tree, CART)与上述决策树的不同，\n",
    "1. 既可以做分类又可以做回归. \n",
    "2. 是二叉树，内部节点特征取值，只有yes和no两个选项      \n",
    "同样地，先进行决策树构造，在基于验证集上进行CART决策树的剪枝，既然是回归和分类树，我们就分别介绍回归和分类两种情况.\n",
    "+ 分类: gini指数\n",
    "+ 回归: 平方误差\n",
    "定义数据格式:\n",
    "$$D={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$$\n",
    "其中，$x_i$是向量，当回归问题时，$y_i$是连续变量; 分类问题时，$y_i$是离散变量. \n",
    "\n",
    "### 回归树(Regerssion Tree)\n",
    "算法:       \n",
    "在训练数据上，根据某一个特征将每个区域划分为两个子区域并决定每个子区域的输出值，递归构建二叉树.\n",
    "1. 选择最优切分变量j和切分点s，求解\n",
    "$$min_{j,s}[min_{c_1}\\sum_{x_i \\in R_1(j,s)}(y_i-c_1)^2 + min_{c_2}\\sum_{x_i \\in R_2(j,s)}(y_i-c_2)^2]$$\n",
    "遍历变量j，对固定的切分变量j扫描所有的s，找到使得上式最小的对(j,s).\n",
    "2. 使用选定的(j,s)划分区域并决定相应的输出值:\n",
    "   $$R_1(j,s)=\\{x|x^{(j)} \\leq s \\}, R_2(j,s)=\\{x|x^{(j)} > s \\},$$\n",
    "   $$c_m=\\frac{1}{N_m}\\sum_{x_i \\in R_m(j,s)}y_i, x \\in R_m, m=1,2$$\n",
    "3. 继续对两个子区域调用1和2，知道满足条件\n",
    "4. 将输入空间划分为M个区域$R_1,R_2,...,R_m$,生成决策树:\n",
    "   $$f(x)=\\sum_{m=1}^{M}c_mI(x \\in R_m)$$\n",
    "\n",
    "### 分类树(classification tree)\n",
    "基尼指数计算公式如下:\n",
    "$$Gini(p)=\\sum_{k=1}^{K}p_k(1-p_k)=1-\\sum_{k=1}^{K}p_k^2$$\n",
    "基于数据D，得到:\n",
    "$$Gini(D)=1-\\sum_{k=1}^{K}p_k^2$$\n",
    "其中,$C_k$是D中所属第k类的样本子集，K是类的个数.        \n",
    "如果样本集合D根据特征A是否取某一可能取值a被被划分成$D_1$和$D_2$两个部分.\n",
    "$$D_1=\\{(x,y) \\in D | A(x)=a \\}, D_2= D-D_1$$\n",
    "在特征A的条件下，集合D的基尼指数定义为:\n",
    "$$Gini(D,A)=\\frac{|D_1|}{D}Gini(D_1)+\\frac{|D_2|}{D}Gini(D_2)$$\n",
    "基尼指数和熵一样，同样表示集合D的不确定性，基尼指数(Gini(D,A))表示根据调教A=a后的集合D的不确定性，基尼指数越大，表示数据D的不确定性越大.\n",
    "\n",
    "算法:       \n",
    "输入:训练数据D，停止计算的条件      \n",
    "输出:CART决策树     \n",
    "1. 计算所有特征A的每一个值a对应的条件基尼指数的值，选择最优的划分得到$D_1$和$D_2$.\n",
    "2. 递归对两个数据集$D_1$和$D_2$继续调用1，知道满足条件.\n",
    "3. 生成CART树的分类树. \n",
    "4. 预测的时候，根据决策树，x落到的叶子节点对应的类别表示这个预测x的类别.\n",
    "\n",
    "### CART剪枝\n",
    "从上面两个算法的不同可以看出，只是在label的设置和决策节点选择的方式不同，整个架构依然是决策树的常用的架构. 而且上面的树的构建过程，都是基于训练数据的经验风险最小化，没有使用带有正则项的结构风险最小化，这样的模型容易发生过拟合，为了不让模型过拟合，我们需要进行模型的剪枝.\n",
    "\n",
    "**CART树的剪枝有很多难点和有意思的地方让我们开慢慢解开这层面纱**\n",
    "CART剪枝算法有两步组成:\n",
    "1. 从生成算法产生的决策树$T_0$底端开始不断剪枝，直到$T_0$的根节点，形成一个子树序列$\\{T_0,T_1,...,T_n\\}$.\n",
    "2. 通过交叉验证的方法在独立的验证数据集上堆子序列进行测试，得到最优子树\n",
    "\n",
    "损失函数:\n",
    "$$C_{\\alpha}(T)=C(T)+\\alpha|T|$$\n",
    "其中，T为任意子树，$C(T)$是在训练数据上的预测误差，|T|是树的叶子节点的个数,$\\alpha \\geq 0$是参数，$C_{\\alpha}(T)$是参数$\\alpha$是的子树T的整体的损失，参数$\\alpha$是平衡训练数据拟合程度和模型复杂度的权重.             \n",
    "对于固定的$\\alpha$,一定存在使损失函数$C_{\\alpha}(T)$最小的子树，将其记作$T_{\\alpha}$. 我们可以理解为每一个$\\alpha$都对应一个最有子树和最小损失. \n",
    "\n",
    "**而且**已经得到证明，可以用递归的方法对树进行剪枝. 将$\\alpha$从小增大，$0=\\alpha_0<\\alpha_1<...<\\alpha_n<+\\infty$,产生一系列的区间$[\\alpha_i,\\alpha_{i+1}),i=0,1,...,n$；剪枝得到的子树序列对应着区间$\\alpha \\in [\\alpha_i,\\alpha_{i+1}),i=0,1,...,n$的最有子树序列$\\{T_0,T_1,...,T_n\\}$. \n",
    "\n",
    "我们给出算法:       \n",
    "输入: CART算法生成的决策树T_0.      \n",
    "输出: 最优的决策树T_{\\alpha}        \n",
    "1. 设k=0, T=$T_0$.\n",
    "2. 设 $\\alpha=+\\infty$.\n",
    "3. 自下而上地对各个**内部节点t**计算$C(T_t),|T_t|$以及\n",
    "   $$g(t)=\\frac{C(t)-C(T_t)}{|T_t|-1}$$\n",
    "   $$\\alpha=min(\\alpha,g(t))$$\n",
    "    这里，$T_t$表示以t为根节点的子树，$C(T_t)$是对训练数据的预测误差，$|T_t|$是$T_t$的叶子节点个数.\n",
    "4. 自上而下地访问内部节点t，如果有$g(t)=\\alpha$,进行剪枝，并堆叶节点t以多数表决方法决定其类(分类，回归使用平均值)，得到树T.\n",
    "5. 设$k=k+1,\\alpha=\\alpha,T_k=T$.\n",
    "6. 如果T不是由根节点单独构成的树，则回到步骤4. \n",
    "7. 采用交叉验证法在子树序列$\\{T_0,T_1,...,T_n\\}$中选取最优子树$T_{\\alpha}$.\n",
    "\n",
    "接下面，我们不去看算法，来看书中给的一段文字的截图，这里截图是因为我要画图，进行比较解释，图中自由理论(哈哈):\n",
    "<center><img src=\"https://i.ibb.co/RjszN94/cart.png\" alt=\"cart\" border=\"0\"></center>\n",
    "\n",
    "看懂这个图之后，再看算法一气呵成，因为我们假设每一次得到的树都有可能是最优的，所以不能直接去最后一个树，要使用交叉验证选择最有的决策树结构. \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题精选\n",
    "1. 决策树和条件概率分布的关系？\n",
    "> 决策树可以表示成给定条件下类的条件概率分布. 决策树中的每一条路径都对应是划分的一个条件概率分布. 每一个叶子节点都是通过多个条件之后的划分空间，在叶子节点中计算每个类的条件概率，必然会倾向于某一个类，即这个类的概率最大.\n",
    "2. 为什么使用信息增益，越大越能得到好的模型？\n",
    "> 上面提到过，信息熵表示数据的混乱的程度，信息增益是信息熵和条件信息熵的差值，表示的熵减少的程度，信息增益越大，代表根据我们的决策树规则得到的数据越趋向于规整，这就是我们划分类别的目的. \n",
    "3. 为什么从信息增益变到信息增益比，目的何在？\n",
    "> 信息增益根据特征之后的条件信息熵，这样的话偏向于特征取值较多的特征的问题，因此使用信息增益比对这个问题进行校正. \n",
    "4. 为什么要进行剪枝？\n",
    "> 在构造决策树的过程中，我们的两个停止条件是，子集只有一个类别和没有可以选择的特征，这是我们全部利用了数据中的所有可以使用的信息，但是我们知道数据是可能有误差了，而且数据不足，我们需要得到更鲁棒的模型，剪枝的意义就是是的深度减小，这样的就相当于减少规则的情况下，决策树的性能反而不差，使其更加鲁棒.\n",
    "5. ID3和C4.5算法可以处理实数特征吗？如果可以应该怎么处理？如果不可以请给出理由？\n",
    "> ID3和C4.5使用划分节点的方法分别是信息增益和信息增益比，从这个公式中我们可以看到 这是处理类别特征的方法，实数特征能够计算信息增益吗？我们可以定义X是实数特征的信息增益是，$$G(D|X:t)=H(D)-H(D|X:t)$$\n",
    "其中\n",
    "$$H(D|X:t)=H(D|x \\leq t)p(x \\leq t)+H(D|x>t)p(x>t)$$ $$G(D|X)=max_t=G(D|X:t)$$\n",
    "对于每一个实数可以使用这种方式进行分割. 除此之外,我们还可以使用特征的分桶，将实数特征映射到有限个桶中，可以直接使用ID3和C4.5算法.\n",
    "6. 基尼系数存在的问题? \n",
    "> 基尼指数偏向于多值属性;当类数较大时，基尼指数求解比较困难;基尼指数倾向于支持在两个分区中生成大小相同的测试。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## sklearn 决策树参数\n",
    "\n",
    "我们掌握理论之后,就去看看sklearn中决策树的实现.\n",
    "\n",
    "DecisionTreeClassifier: sklearn中多分类决策树的接口.\n",
    "\n",
    "Paramters: \n",
    "```\n",
    "criterion : str, 可选参数(default=\"gini\")\n",
    "    这个参数表示使用什么度量划分的质量. gini: 表示使用基尼指数.\n",
    "    entropy: 表示使用的是信息增益.\n",
    "splitter : str, optional(default=\"best\")\n",
    "    选择分割节点的策略. 支持最优(best)和随机(random)两种方式.\n",
    "\n",
    "max_depth : int or None, optional(dafault=None)\n",
    "    表示决策树的最大深度. None: 表示不设置深度,可以任意扩展,\n",
    "    直到叶子节点的个数小于min_samples_split个数.\n",
    "min_samples_split : int, float, optional(default=2)\n",
    "    表示最小分割样例数.\n",
    "    if int, 表示最小分割样例树,如果小于这个数字,不在进行分割.\n",
    "    if float, 表示的比例[0,1],最小的分割数字=ceil(min_samples_split * n_samples)\n",
    "\n",
    "min_samples_leaf : int, float, optional (default=1)\n",
    "    表示叶节点最少有min_samples_leaf个节点树,如果小于等于这个数,直接返回.\n",
    "    if int, min_samples_leaf就是最小样例数.\n",
    "    if float, 表示的比例[0,1],最小的样例数=ceil(min_samples_leaf * n_samples)\n",
    "    \n",
    "min_weight_fraction_leaf : float, optional (default=0.) \n",
    "    \n",
    "max_features : int, float, str or None, optional(default=None)\n",
    "    进行最优分割时,特征的最大个数.\n",
    "    if int, max_features是每次分割的最大特征数\n",
    "    if float, int(max_features * n_features)作为最大特征数\n",
    "    if \"auto\", 则max_features=sqrt(n_features)\n",
    "    if \"sqrt\", 则max_features=sqrt(n_features)\n",
    "    if \"log2\", 则max_features=log2(n_features)\n",
    "    if None, 则max_features=n_features\n",
    "    \n",
    "random_state : int, RandomState instance or None, optional (default=None)\n",
    "    随机化种子, if None,使用np.random随机产生\n",
    "    \n",
    "max_leaf_nodes : int or None, optional (default=None)\n",
    "    最大的叶子节点个数,如果大于这个值,需要进行继续划分. None则表示没有限制.\n",
    "\n",
    "min_impurity_decrease : float, optional (default=0.)\n",
    "    分割之后基尼指数大于这个数,则进行分割.\n",
    "    N_t / N * (impurity - N_t_R / N_t * right_impurity\n",
    "                    - N_t_L / N_t * left_impurity)\n",
    "                    \n",
    "min_impurity_split : float, default=1e-7\n",
    "    停止增长的阈值,小于这个值直接返回.\n",
    "```\n",
    "\n",
    "DecisionTreeRegressor: sklearn中回归树的接口.\n",
    "```\n",
    "criterion : str, optional (default=”mse”)\n",
    "    其他参数和分类树类似.\n",
    "    mse: mean squared error, which is equal to variance reduction as feature selection criterion and minimizes the L2 loss using the mean of each terminal node,\n",
    "    mae: mean absolute error, which minimizes the L1 loss using the median of each terminal node.\n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 代码实现\n",
    "\n",
    "使用cart树的分类和回归两个接口,接口参考sklearn.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "import copy\n",
    "import numbers\n",
    "import warnings\n",
    "from math import ceil\n",
    "\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "from scipy.sparse import issparse"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 184,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DecisionTree(object):\n",
    "    \"\"\"自定的树结构,用来保存决策树.\n",
    "    \n",
    "    Paramters:\n",
    "    ----------\n",
    "    col: int, default(-1)\n",
    "        当前使用的第几列数据\n",
    "    \n",
    "    val: int or float or str, 分割节点\n",
    "        分割节点的值, \n",
    "        int or float : 使用大于进行比较 \n",
    "        str : 使用等于模式\n",
    "    \n",
    "    LeftChild: DecisionTree\n",
    "        左子树, <= val\n",
    "    \n",
    "    RightChild: DecisionTree\n",
    "        右子树, > val\n",
    "    \n",
    "    results: \n",
    "    \"\"\"\n",
    "    def __init__(self, col=-1, val=None, LeftChild=None, RightChild=None, result=None):\n",
    "        self.col = col\n",
    "        self.val = val\n",
    "        self.LeftChild = LeftChild\n",
    "        self.RightChild = RightChild\n",
    "        self.result = result\n",
    "\n",
    "\n",
    "class DecisionTreeClassifier(object):\n",
    "    \"\"\"使用基尼指数的分类决策树接口.\n",
    "    \n",
    "    Paramters:\n",
    "    ---------\n",
    "    max_depth : int or None, optional(dafault=None)\n",
    "        表示决策树的最大深度. None: 表示不设置深度,可以任意扩展,\n",
    "        直到叶子节点的个数小于min_samples_split个数.\n",
    "\n",
    "    min_samples_split : int, optional(default=2)\n",
    "        表示最小分割样例数.\n",
    "        if int, 表示最小分割样例树,如果小于这个数字,不在进行分割.\n",
    "\n",
    "    min_samples_leaf : int, optional (default=1)\n",
    "        表示叶节点最少有min_samples_leaf个节点树,如果小于等于这个数,直接返回.\n",
    "        if int, min_samples_leaf就是最小样例数.\n",
    "\n",
    "    min_impurity_decrease : float, optional (default=0.)\n",
    "        分割之后基尼指数大于这个数,则进行分割.\n",
    "        N_t / N * (impurity - N_t_R / N_t * right_impurity\n",
    "                        - N_t_L / N_t * left_impurity)\n",
    "\n",
    "    min_impurity_split : float, default=1e-7\n",
    "        停止增长的阈值,小于这个值直接返回.\n",
    "    \n",
    "    Attributes\n",
    "    ----------\n",
    "    classes_ : array of shape (n_classes,) or a list of such arrays\n",
    "        表示所有的类\n",
    "    \n",
    "    feature_importances_ : ndarray of shape (n_features,)\n",
    "        特征重要性, 被选择最优特征的次数,进行降序.\n",
    "    \n",
    "    tree_ : Tree object\n",
    "        The underlying Tree object.\n",
    "    \"\"\"\n",
    "    def __init__(self,\n",
    "                 max_depth=None,\n",
    "                 min_samples_split=2,\n",
    "                 min_samples_leaf=1,\n",
    "                 min_impurity_decrease=0.,\n",
    "                 min_impurity_split=1e-7):        \n",
    "        self.max_depth = max_depth\n",
    "        self.min_samples_split = min_samples_split\n",
    "        self.min_samples_leaf = min_samples_leaf\n",
    "        self.min_impurity_decrease = min_impurity_decrease\n",
    "        self.min_impurity_split = min_impurity_split\n",
    "        self.classes_ = None\n",
    "        self.max_features_ = None\n",
    "        self.decision_tree = None\n",
    "        self.all_feats = None\n",
    "    \n",
    "    \n",
    "    def fit(self, X, y, check_input=True):\n",
    "        \"\"\"使用X和y训练决策树的分类模型.\n",
    "        \n",
    "        Parameters\n",
    "        ----------\n",
    "        X : {array-like} of shape (n_samples, n_features)\n",
    "            The training input samples. Internally, it will be converted to\n",
    "            ``dtype=np.float32``\n",
    "            \n",
    "        y : array-like of shape (n_samples,) or (n_samples, n_outputs)\n",
    "            The target values (class labels) as integers or strings.\n",
    "        \n",
    "        check_input : bool, (default=True)\n",
    "            Allow to bypass several input checking.\n",
    "        \n",
    "        Returns\n",
    "        -------\n",
    "        self : object\n",
    "            Fitted estimator.\n",
    "        \"\"\"\n",
    "        if isinstance(X, list):\n",
    "            X = self.__check_array(X)\n",
    "        if isinstance(y, list):\n",
    "            y = self.__check_array(y)\n",
    "        if X.shape[0] != y.shape[0]:\n",
    "            raise ValueError(\"输入的数据X和y长度不匹配\")\n",
    "        \n",
    "        self.classes_ = list(set(y))\n",
    "        if isinstance(X, pd.DataFrame):\n",
    "            X = X.values\n",
    "        if isinstance(y, pd.DataFrame):\n",
    "            y = y.values\n",
    "        \n",
    "        data_origin = np.c_[X, y]\n",
    "#         print (data_origin)\n",
    "        self.all_feats = [i for i in range(X.shape[1])]\n",
    "        self.max_features_ = X.shape[0]\n",
    "        \n",
    "        data = copy.deepcopy(data_origin)\n",
    "        self.decision_tree = self.__build_tree(data, 0)\n",
    "\n",
    "\n",
    "    def __predict_one(self, input_x):\n",
    "        \"\"\"预测一个样例的返回结果.\n",
    "        \n",
    "        Paramters:\n",
    "        ---------\n",
    "        input_x : list or np.ndarray\n",
    "            需要预测输入数据\n",
    "        \n",
    "        Returns:\n",
    "        -------\n",
    "        class : 对应的类\n",
    "        \"\"\"\n",
    "        \n",
    "        tree = self.decision_tree\n",
    "        #============================= show me your code =======================\n",
    "        # here\n",
    "        pre_y = \n",
    "        #============================= show me your code =======================\n",
    "        return pre_y\n",
    "    \n",
    "    \n",
    "    def predict(self, test):\n",
    "        \"\"\"预测函数,\n",
    "        \n",
    "        Paramters:\n",
    "        ---------\n",
    "        test: {array-like} of shape (n_samples, n_features)\n",
    "        \n",
    "        Returns:\n",
    "        result : np.array(list) \n",
    "        \"\"\"\n",
    "        result = []\n",
    "        for i in range(len(test)):\n",
    "            result.append(self.__predict_one(test[i]))\n",
    "        return np.array(result)\n",
    "    \n",
    "    \n",
    "    def score(self, vali_X, vali_y):\n",
    "        \"\"\"验证模型的特征,这里使用准确率.\n",
    "        Parameters\n",
    "        ----------\n",
    "        vali_X : {array-like} of shape (n_samples, n_features)\n",
    "            The training input samples. Internally, it will be converted to\n",
    "            ``dtype=np.float32``\n",
    "\n",
    "        vali_y : array-like of shape (n_samples,) or (n_samples, n_outputs)\n",
    "            The target values (class labels) as integers or strings.\n",
    "        \n",
    "        Returns:\n",
    "        -------\n",
    "        score : float, 预测的准确率\n",
    "        \"\"\"\n",
    "        vali_y = np.array(vali_y)\n",
    "        pre_y = self.predict(vali_X)\n",
    "        pre_score = 1.0 * sum(vali_y == pre_y) / len(vali_y)\n",
    "        return pre_score\n",
    "    \n",
    "    \n",
    "    def __build_tree(self, data, depth):\n",
    "        \"\"\"创建决策树的主要代码\n",
    "        \n",
    "        Paramters:\n",
    "        ---------\n",
    "        data : {array-like} of shape (n_samples, n_features) + {label}\n",
    "            The training input samples. Internally, it will be converted to\n",
    "            ``dtype=np.float32``\n",
    "        \n",
    "        depth: int, 树的深度\n",
    "        \n",
    "        Returns:\n",
    "        -------\n",
    "        DecisionTree\n",
    "            \n",
    "        \"\"\"        \n",
    "        labels = np.unique(data[:,-1])\n",
    "        # 只剩下唯一的类别时,停止,返回对应类别\n",
    "        if len(labels) == 1:\n",
    "            return DecisionTree(result=list(labels)[0])\n",
    "        \n",
    "        # 遍历完所有特征时,只剩下label标签,就返回出现字数最多的类标签\n",
    "        if not self.all_feats:\n",
    "            return DecisionTree(result=np.argmax(np.bincount(data[:,-1].astype(int))))\n",
    "\n",
    "        # 超过最大深度,则停止,使用出现最多的参数作为该叶子节点的类\n",
    "        if self.max_depth and depth > self.max_depth:\n",
    "            return DecisionTree(result=np.argmax(np.bincount(data[:,-1].astype(int))))\n",
    "\n",
    "        # 如果剩余的样本数大于等于给定的参数 min_samples_split,\n",
    "        # 则不在进行分割, 直接返回类别中最多的类,该节点作为叶子节点\n",
    "        if self.min_samples_split >= data.shape[0]:\n",
    "            return DecisionTree(result=np.argmax(np.bincount(data[:,-1].astype(int))))\n",
    "\n",
    "        # 叶子节点个数小于指定参数就进行返回,叶子节点中的出现最多的类\n",
    "        if self.min_samples_leaf >= data.shape[0]:\n",
    "            return DecisionTree(result=np.argmax(np.bincount(data[:,-1].astype(int))))\n",
    "        \n",
    "        # 根据基尼指数选择每个分割的最优特征\n",
    "        best_idx, best_val, min_gini = self.__getBestFeature(data)\n",
    "#         print (\"Current best Feature:\", best_idx, best_val, min_gini)\n",
    "        # 如果当前的gini指数小于指定阈值,直接返回\n",
    "        if min_gini < self.min_impurity_split:\n",
    "            return DecisionTree(result=np.argmax(np.bincount(data[:,-1].astype(int))))\n",
    "        \n",
    "        leftData, rightData = self.__splitData(data, best_idx, best_val)\n",
    "        \n",
    "        #============================= show me your code =======================\n",
    "        # here\n",
    "        \n",
    "        #============================= show me your code =======================\n",
    "        \n",
    "        return DecisionTree(col=best_idx, val=best_val, LeftChild=leftDecisionTree, RightChild=rightDecisionTree)\n",
    "\n",
    "    \n",
    "    def __getBestFeature(self, data):\n",
    "        \"\"\"得到最优特征对应的列\n",
    "        Paramters:\n",
    "        ---------\n",
    "        data: np.ndarray\n",
    "            从data中选择最优特征\n",
    "            \n",
    "        Returns:\n",
    "        -------\n",
    "        bestInx, val, 最优特征的列的索引和使用的值.\n",
    "        \"\"\"\n",
    "        best_idx = -1\n",
    "        best_val = None\n",
    "        min_gini = 1.0                \n",
    "        # 遍历现在可以使用的特征列\n",
    "        #============================= show me your code =======================\n",
    "\n",
    "        # here\n",
    "        \n",
    "        #============================= show me your code =======================\n",
    "        # 删除使用过的特征\n",
    "        self.all_feats.remove(best_idx)\n",
    "        \n",
    "        return best_idx, best_val, min_gini\n",
    "        \n",
    "    \n",
    "    def gini(self, labels):\n",
    "        \"\"\"计算基尼指数.\n",
    "        \n",
    "        Paramters:\n",
    "        ----------\n",
    "        labels: list or np.ndarray, 数据对应的类目集合.\n",
    "        \n",
    "        Returns: \n",
    "        -------\n",
    "        gini : float ``` Gini(p) = \\sum_{k=1}^{K}p_k(1-p_k)=1-\\sum_{k=1}^{K}p_k^2 ```\n",
    "        \n",
    "        \"\"\"\n",
    "        #============================= show me your code =======================\n",
    "\n",
    "        # here\n",
    "        \n",
    "        #============================= show me your code =======================\n",
    "        return gini\n",
    "    \n",
    "    \n",
    "    def __splitData(self, data, featColumn, val):\n",
    "        '''根据特征划分数据集分成左右两部分.\n",
    "        Paramters:\n",
    "        ---------\n",
    "        data: np.ndarray, 分割的数据\n",
    "        \n",
    "        featColumn : int, 使用第几列的数据进行分割\n",
    "        \n",
    "        val : int or float or str, 分割的值\n",
    "            int or float : 使用比较方式\n",
    "            str : 使用相等方式\n",
    "        \n",
    "        Returns:\n",
    "        -------\n",
    "        leftData, RightData\n",
    "            int or left: leftData <= val < rightData\n",
    "            str : leftData = val and rightData != val\n",
    "        '''\n",
    "        if isinstance(val, str):\n",
    "            leftData = data[data[:, featColumn] == val]\n",
    "            rightData = data[data[:, featColumn] != val]\n",
    "        elif isinstance(val, int) or isinstance(val, float):\n",
    "            leftData = data[data[:, featColumn] <= val]\n",
    "            rightData = data[data[:, featColumn] > val]\n",
    "        return leftData, rightData\n",
    "    \n",
    "    \n",
    "    def __check_array(self, X):\n",
    "        \"\"\"检查数据类型\n",
    "        Parameters:\n",
    "        ----------\n",
    "        X : {array-like} of shape (n_samples, n_features)\n",
    "            The training input samples.\n",
    "        \n",
    "        Retures\n",
    "        -------\n",
    "        X: {array-like} of shape (n_samples, n_features)\n",
    "        \"\"\"\n",
    "        if isinstance(X, list):\n",
    "            X = np.array(X)\n",
    "        if not isinstance(X, np.ndarray) and not isinstance(X, pd.DataFrame):\n",
    "            raise ValueError(\"输出数据不合法,目前只支持np.ndarray or pd.DataFrame\")\n",
    "        return X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<__main__.DecisionTree object at 0x7f6b1339cd68>\n",
      "Classifier Score: 0.9666666666666667\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from sklearn.datasets import load_iris\n",
    "from sklearn.model_selection import train_test_split\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    # 分类树\n",
    "    X, y = load_iris(return_X_y=True)\n",
    "\n",
    "    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)\n",
    "\n",
    "    clf = DecisionTreeClassifier()\n",
    "\n",
    "    clf.fit(X_train, y_train)\n",
    "\n",
    "    print (\"Classifier Score:\", clf.score(X_test, y_test))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 参考\n",
    "1. 统计学习方法-决策树\n",
    "2. https://blog.csdn.net/fool_ran/article/details/86257713\n",
    "3. https://baike.baidu.com/item/%E7%86%B5/101181?fr=aladdin\n",
    "4. https://github.com/datawhalechina/Datawhale_Learning/blob/master/doc/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0/%E5%88%9D%E7%BA%A7%E7%AE%97%E6%B3%95%E6%A2%B3%E7%90%86/%E5%AD%A6%E4%B9%A0%E4%BB%BB%E5%8A%A1/Task3.md\n",
    "5. https://baike.baidu.com/item/%E5%9F%BA%E5%B0%BC%E7%B3%BB%E6%95%B0?fromtitle=%E5%9F%BA%E5%B0%BC%E6%8C%87%E6%95%B0&fromid=360504\n",
    "6. https://baike.baidu.com/item/%E8%81%94%E5%90%88%E7%86%B5/22709235?fr=aladdin\n",
    "7. https://github.com/datawhalechina/Daily-interview/blob/master/machine-learning/DecisionTree.md\n",
    "8. https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeRegressor.html#sklearn.tree.DecisionTreeRegressor\n",
    "9. https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeRegressor.html#sklearn.tree.DecisionTreeRegressor\n",
    "10. https://github.com/michaeldorner/DecisionTrees/blob/master/03_Python%20Code/implementation.py"
   ]
  }
 ],
 "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.8"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "184px"
   },
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}