{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在决策树学习中，为了尽可能正确地分类训练样本，节点划分过程将不断重复，有时会造成决策树分支过多，从而导致过拟合。譬如下面这样的例子，通过 sklearn 的 `datasets.make_moons` 生成的样本："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX8AAAD8CAYAAACfF6SlAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAHU1JREFUeJzt3X2MXFd5x/HvE8eQpa28CTYkWXvrpE0Dea1hFV5cVWlcGhKaxA0hTfiDUBFZtI1oUymqUSVjRariNFKjpqFFhiKCVEJMAGOKkdvGICrapFmT2E4IBhOg7DoiIRC3CJf65ekfcwfPzt6ZuTP3zL3n3vv7SNbOzlzPPXt39pkzz3nOOebuiIhIs5xSdgNERKR4Cv4iIg2k4C8i0kAK/iIiDaTgLyLSQAr+IiINpOAvItJACv4iIg0UJPib2UfN7Hkze6rH45eb2WEzezL5tynEeUVEZDSnBnqejwH3Ax/vc8y/ufvvZn3C5cuX++rVq3M2S0SkWfbs2fNDd18x6Lggwd/dv2Jmq0M8V9vq1auZnZ0N+ZQiIrVnZt/LclyROf83mdleM/uimV2YdoCZbTCzWTObfeGFFwpsmohIsxQV/L8G/LK7Xwr8LbA97SB33+ruM+4+s2LFwE8tIiIyokKCv7v/t7v/JLm9E1hqZsuLOLeIiCxWSPA3szPNzJLblyXnfbGIc4uIyGJBBnzN7EHgcmC5mc0BHwCWArj7h4AbgD80s2PAEeAm10YCIiKlCVXtc/OAx++nVQoqIiIRCFXnLzW2/Yl57tl1gEMvHeHsyQnuuPJ81q+ZKrtZIpKDgn/NhA7U25+Y5/2f2c+Ro8cBmH/pCO//zH4AvQGIVJjW9qmRdqCef+kIzslAvf2J+ZGf855dB34e+NuOHD3OPbsO5GytiJRJwb9GxhGoD710ZKj7RaQaFPxrZByB+uzJiaHuF5FqUPCvkXEE6juuPJ+JpUsW3DexdAl3XHn+yM8pIuVT8K+RcQTq9WumuOv6i5manMCAqckJ7rr+Yg32ilScqn1qpB2QQ5dlrl8zpWAvUjMK/jWjQC0iWSjtIyLSQAr+IiINpOAvItJACv4iIg2k4C8i0kAK/iIiDaTgLyLSQAr+IiINpOAvItJAmuHbANqJS0S6KfjXnHbiEpE0SvvUnHbiEpE0Cv41p524RCSN0j41d/bkBPMpgV47cdWLxnVkWOr515x24qq/9rjO/EtHcE6O62x/Yr7spknEFPxrTjtx1Z/GdWQUSvs0gDZ4qTeN68goFPylFpqc89a4joxCaR+pvKbnvDWuI6NQz18qr1/Ou7P3X9dPB+2foY4/m4yPgr8MJcYAmiXnPcxM51F+xrKvi8Z1ZFhK+0hmsaZXeuW2O+/PWhEzys8Y63UR6UfBXzKLtaQwS847a0XMKD9jrNdFpJ8gwd/MPmpmz5vZUz0eNzO7z8wOmtk+M3tdiPNKWNufmGftlt2cs/ELrN2ye1HPNdaSwixzGbJ8OoDRfsZYr4tIP6Fy/h8D7gc+3uPxq4Dzkn9vAP4++SqRyJITj7mkcFDO+44rz1/w80F6RcwoP2PM10WklyA9f3f/CvCjPodcB3zcWx4FJs3srBDnljCypC6qXFKYdabzKD9jla+LNFdR1T5TwPc7vp9L7nuuoPPLAFlSF90lhZOvWIo73P7Qk9yz60AUlT/9ZKmIGaVsUqWWUkVFBX9Luc8XHWS2AdgAMD09Pe42SYesqYt2AK3zJjGjlE32+j9ll4CK9FJUtc8csKrj+5XAoe6D3H2ru8+4+8yKFSsKaprA8KkLVbgMphJQiVlRwX8H8K6k6ueNwGF3V8onIsOu/qkKl8FCv0EOqsYSGUaQtI+ZPQhcDiw3szngA8BSAHf/ELATuBo4CPwU+IMQ5627olMGw6Q7VOEyWMg3yDqn2aQcQYK/u9884HEH/jjEuZoi9j/2rKWTTRbyDTLr+kUiWWmGb6Riz6lrk5jBQpaAKs0moWlht0hV4Y9di4n1F7IEVGk2CU3BP1Kx/bGrZHE0od4glWaT0JT2iVRMs0ZVslg+pdkkNPX8IxV61miennulBxv3bYNH7oTDc7BsJazbBJfcWHarRpLrU0SNroOEoeAfsVApg7yVQ1UYf0i1bxt8/n1wNGnn4e+3vocoA9/YUmsVuw5SDKV9GiBv5VDW5ZCj88idJwNe29EjrfsjM9bUWoWugxRHwX+MYpmRmbfnHtP4w1AOzw13f4nGWtpboesgxVHwH5OYBknz9twrO9i4bOVw95dorKm1Cl0HKY6C/5jENEkrRM99/ZopvrrxCr6z5W18deMV8Qd+gHWbOLbktAV3HVtyWmuwMzJjTa2t2wRLu55n6USU16Gx9m2Dey+CzZOtr/u2jf2UCv5jEtMgaWV77jltP76WjUdvZe7Eck64MXdiORuP3sr242vLbtoiY02tXXIjXHMfLFsFWOvrNfdpsDcW7QH5w98H/OSA/JjfAKy17E58ZmZmfHZ2tuxmjGztlt2pk7SmJif46sYrSmjRYnWfuJXldxDTNYipLVKgey9KAn+XZavg9tRt0fsysz3uPjPoOJV6BtL9h/tbr1nBp/fMRzsjM/aF40IY9OkrtmvQPbejnSKsy+9DeihpQF5pnwDSBnc/vWeet79+KtpUS0xjEuMyKI8e2zWIqUhAClTSgLx6/gH0CiJf+sYL0aR4uo06JlFkaiLvuQathxPTuAxUfCZ17GKe4bxu08JJeFDIgLyCfwCxBZEsRlk4rsg0SYhzDVoiI7bF86r4OqqE2Gc4t9tQ8JuTgn8AsQWRLEZZJbLInmmoc/VbIiO2lTKr+DqqhH4znGMI/tBqR8FtUc4/gCrOgB2l/LPInmkR54qtBLaKr6NK0AznVOr5BxB6Bc6iDLtwXJE90yb2gqv6OorespU9SimbPcNZwT+QJuxqVWSapIhzxVbq2T5v3V9HhStpQDV2SvtIZkWmSYo4V2ylnjImmuGcSjN8pbHO2fgF0l79Bnxny9sW3a8ZuFIFWWf4qucvxShh4apBhllMTROwpG4U/GX8Slq4apBhqmuUIpK60YBvCRqXPoi0znqY6hpNwJK6UfAvWIwVJmMXcZ111uqaJpaeSr0p7VOwRqYParCTlCZgSd0o+BeskemDGuwklVZ6+vbXT3HPrgOl79EsMgqlfQrWiPRB2gqK19wX76qKGXWmiBqZvpNaUfAvWJmLiRUy0NxrBcVr7htpV6JYafllqToF/0CyBtay1m8prKcaaWVPaI1M30mtKPgHMGxgLWP9lsJ6qhFX9oTUiPSd1JoGfAfY/sQ8a7fs7juoV4UKnsJ6qjWo7MmizOqfLK9JkUGCBH8ze6uZHTCzg2a2MeXxd5vZC2b2ZPLv1hDnHbesU/qrkAIYZimDXGpQ2ZNFWXsBaJkJCSV32sfMlgAfBN4CzAGPm9kOd/9616EPufttec9XpKypkiqkAAobaC5pS7oy1Dp9J7UXIud/GXDQ3Z8FMLNPAtcB3cG/crL26GPbDjBNoQPNJWxJ1xRV+JQp1RAi+E8BndvkzAFvSDnu7Wb2m8A3gdvdPWVrnXBClDVm7dFXZQcmbRRSfb1ek6eYsf2Jef1+JbMQwd9S7uteJv3zwIPu/jMzey/wAHDFoicy2wBsAJienh65QaHKGofp0SuwShHSXpMAx901yUyGEmLAdw5Y1fH9SuBQ5wHu/qK7/yz59sPA69OeyN23uvuMu8+sWLFi5AaFqr6JbYNvkfZrcokt7nPFVmEmcQvR838cOM/MzgHmgZuAd3YeYGZnuftzybfXAs8EOG9PIfOi6tFLbNavmeL2h55MfUy5f8kqd8/f3Y8BtwG7aAX1be7+tJndaWbXJoe9z8yeNrO9wPuAd+c9bz+FlTU2SYQ7cTWZXuOSV5A6f3ff6e6/5u6/4u5/mdy3yd13JLff7+4Xuvul7v5b7v6NEOftJdQEHE2mSUS6E1eTaYlpyauWyzuEqL7Rqo0dGrJeT5WM+hpv3C5y0pO5dxfmxGFmZsZnZ2dLO//aLbtTS+qmJif46sZFhUr1tnmSxQVcAAabXyq6NY0SMlh3d2ig9WlBRQz1YmZ73H1m0HFa26cHTabp0JD1emKz/Yl57vjU3gVLOdzxqb0jpx+rsAaVFEfBv0Nnjv+UlFI6aOiAWkPW64nN5h1Pc/TEwk9cR084m3c8PdLzqUMjnRT8E90LZh1PSYc1dkDtkhtbm7EsWwVY6+s19ynfP2YvHTk61P2DqEJIOtVywHcUaR+JAZaYccJdg2Nar6fyqrAGlRRHwT/R66PvCXe+s+VtBbdGBE5/xVJ+/NPFvfzTX7F0pOeryhpUUgwF/0QVlmWWZvnANRdyx8N7OXr8ZApy6RLjA9dcOPJzDj1jfd+2RizP3UTK+SfyTprRhDAJbf2aKe654dIFa0vdc8OlxfXUNbmv1lTn32HUmmrVT5dEvdLxuveiJPB3WbYKbn+q+PZIJlnr/GuX9skzKWbURdy0u1IJ2r3S9szjdq8U0t8A9EYxvMNzw90vlVKr4F/Wkgyqny7BMEtODPtGIS3LVvbo+Y9/cp+WoRi/WuX8y5rBqPrpEgzTK+33RiG9rdvEsSWnLbjr2JLTxj65T5vUF6NWwb+sHrhWWCzBMEtOKH0xku3H17Lx6K3MnVjOCTfmTixn49Fb2X587VjPq2UoilGrtE9Z5Zqqny7Buk0LUznQe8mJEtMXVXbPrgPM/9+beZg3L7j/P8Y8lqU0ajFqFfzLnMGoHb8K1s7VZxnEHeaNQn6urCCsOTfFqFXwVw+8YbIuOTHMG4UArbz7KWapa1yNOwhrGYpi1Cr4g3rg0oPWJsqsPeBa1uKGlevEVbSMuHbBX0Ty6bfIYVETF0vrxA0byCtcRlyrah8Rya/fIofR9r5DGGU5iwqXESv4i8gCjZ23Mkogr3AZsYK/iCzQ2HkrowTyCm9xquAvIgusXzPFXddfvGA10UYsUjhKIK/wFqca8BWRRRpZNTfKfJAKlxEr+ItIc3VX91z6TvjWPw8XyCtaRqzgLyLNlFamufcTcM19lQzmw1LOX0SaqcJlmiEo+Dfdvm2tHZs2T7a+Fr1FX9nnl+aqcJlmCEr7lKj0DSvKnp1Y9vkroPTXSJ01fLVX9fxLEsWGFWV/7C37/JGL4jVSZyHLNCv4CVbBvyRRbFhR9sfess8fuSheI3V2yY2twd1lqwBrfR1lsHeUZSEioLRPSaLYsKLsj71lnz9yUbxG6i5EmeYw+0lHJEjP38zeamYHzOygmW1MefzlZvZQ8vhjZrY6xHmrLIr1U8qenVj2+SMXxWtEBqvoJ9jcwd/MlgAfBK4CLgBuNrMLug57D/Bjd/9V4F7g7rznrboo1k8J9bG3quePXBSvERmsouv7hEj7XAYcdPdnAczsk8B1wNc7jrkO2Jzcfhi438zMPWW3iIbIs2FF0AqQsmcnln3+iBW2qUlFNyOJRkW3CQ0R/KeAzsTtHPCGXse4+zEzOwy8EvhhgPNX1ijrp7QrQNoDge0KkPbzSb0seI3s2waPvA8+FzBIq9w2v4qu7xMi+FvKfd09+izHYGYbgA0A09PT+VtWQ/0qQBT8a2xcQXrIwUrNO+ih3yfYSD9ZhRjwnQNWdXy/EjjU6xgzOxVYBvyo+4ncfau7z7j7zIoVKwI0rX5UAVJBIWrAxzUnYojBSs07GEHEZaAhgv/jwHlmdo6ZvQy4CdjRdcwO4Jbk9g3A7ibn+/NQBUjFhPrjH1dFyRCDlZnnHVRwwtPYRDyRMXfwd/djwG3ALuAZYJu7P21md5rZtclh/wC80swOAn8GLCoHlWxUAVIxof74x1VRMkS5baZPnRH3dEsRcRlokEle7r4T2Nl136aO2/8LvCPEuZqusAqQqootv9rnj3+o/Pm4KkqGGKw8e3KC+ZQ3gAWfOocZQ4jtdzUOEU9k1AzfCopil6UY/3BjqlxpX5/FdQ0A/HTizOGqtsZZUZKx3PaOK89f0GZI+dSZtacb0+9qnCIuA1Xwl+HF9Ifb+SZkp4AvzEmXMs2++/p0WzrBXx39/eGrtkqeE5HpU2fWnm5Fl0QYWsRloAr+MrxY/nC7g2x34G8rOr+adn3alq2CdZt44BO/kPpw7FVbAz91Zu3pRpwLDy7SiYxa1VOGF8sfbr8g26no/GrP62Bw+1NwyY31rdrKumRHRZdEqBMFfxleLH+4Wd5sysivZrg+ta7auuTG1pvc5pd+/ma3iBb1K52Cvwwvlj/cXkHWllDqQnEZrs/6NVPcdf3FTE1OYMDU5AR3XX9x+QP5RdGifqWzWOdazczM+OzsbNnNkF7yVvuEqBZKG1hdOhFHEImxGkoawcz2uPvMwOMU/KVwIYO2gmx4uqaVpuAv8br3oh7lgKtaOeI6qVogje3TVJHXr2q/qx6yBn/l/KV4sVQLjVsVlzqIaS2aIq9fFX9XOSn4S/FiqRYat5gCaVYxvTEXef2q+LvKScFfihe6WijWVSRjCqRZxfTGXOT1q+LvKicFfyleyDK/mD+uxxRIs4qljBeKvX5V/F3lpOAv5cgyESiLmD+uxxRIs4qp/r7I61fF31VOWttHqi3mj+sRL+rVVyxr0RR5/ar6u8pBpZ5SbU0qG41ZTcok60ClntIMDfy4Hp1Yx11iLQSIhIK/VFtMOeqminHcJdY3pIgo5y/VF0uOukpCpmliHHeJZc+JiKnnL9I0oXvFMZZJxviGFBkFf5GmCZ2miXHcJcY3pMgo+Is0TehecYzjLjG+IUVGOX+Rpsm6yfowYhx3OXXi5CeciTPgqrvja2OJ1PMXaZq694rbYxpHfnTyvmMZ9npuGAV/kaaJMU0TUoylpxFS2kckj6rObI0xTROKKn0yUc9fZFSDSiY1w7QcqvTJRMFfZFT90guaYVqeuo9pBKLgL9Ita4+9X3pBeefy1H1MIxDl/EU6dW9g3u6xw+Lg0a9kMpa8c1XHJPKq85hGIOr5i3QapsfeL70QQ95ZqSfpQ8FfpNMwPfZ+6YUY8s5KPUkfSvuIdBp29muv9EIMO0PFknqSKOUK/mZ2BvAQsBr4LnCju/845bjjwP7k2/9y92vznFdkbNZtWpjzh9F77GXnncexjIPURt60z0bgEXc/D3gk+T7NEXf/9eSfAr/Eq06VIjGkniRaedM+1wGXJ7cfAL4M/HnO5xQZXsiqlrJ77KHEkHqSaOUN/q929+cA3P05M3tVj+NOM7NZ4Biwxd235zyvyEnDlGc2TV3eyCS4gcHfzP4VODPlob8Y4jzT7n7IzM4FdpvZfnf/dsq5NgAbAKanp4d4emk0bdnXDE2dszAmA4O/u/92r8fM7AdmdlbS6z8LeL7HcxxKvj5rZl8G1gCLgr+7bwW2AszMzHimn0BEVS31p093weUd8N0B3JLcvgX4XPcBZna6mb08ub0cWAt8Ped5RU6KYUKVjJfmLASXN/hvAd5iZt8C3pJ8j5nNmNlHkmNeC8ya2V7gS7Ry/gr+Eo6qWupPn+6CyzXg6+4vAutS7p8Fbk1u/ztwcZ7ziPQ1qKpFueLq05yF4DTDV+qhV1WLcsX1EHLynQBa20fqTrnieqjT5LtIqOcv9aZccX1ozkJQ6vlLvakSSCSVgr/UmyqBRFIp+Eu9KVcskko5f6k/5YpFFlHPX0SkgRT8RUQaSMFfRKSBFPxFRBpIwV9EWvZtg3svgs2Tra/7tpXdIhkjVfuINE3aQnegNZAaRsFfpEl6LXR36oR2Q2sYBX+RJum10F33fW1aA6m2lPMXaZJhg7nWQKotBX+RosQwoNormE+cMZ41kGL4mSWVgr9IEdq59sPfB/xkrr3oYNhrobur7g6/BlIsP7OkUs5fpAj9NpUpckB10JaXIdsSy88sqRT8RYoQ06YyRS10F9PPLIso7SNShCZuKtPEn7lCFPxFijDKpjJVHyzVRjpRU9pHpAiDcu3dek3G6nyu2A37M0uhzN3LbkOqmZkZn52dLbsZIuW496KkSqbLslVw+1PFt0cqw8z2uPvMoOOU9hGJkQZLZcwU/EVipMFSGTMFf6mfqg+UggZLZew04Cv1UoeBUtBgqYydgr/US51mlRY1GUsaSWkfqZciB0rrkF6SxlLwl3opaqBUi5ZJxSn4S70UNVDaL70kUgEK/lIvl9wYfmniNKrDl4rLNeBrZu8ANgOvBS5z99QpuWb2VuBvgCXAR9x9S57zivRVxEDpspU9ZuCqDl+qIW/P/yngeuArvQ4wsyXAB4GrgAuAm83sgpznFSmX6vCl4nIFf3d/xt0PDDjsMuCguz/r7v8HfBK4Ls95RUpXVHpJZEyKqPOfAjo/H88Bb0g70Mw2ABsApqenx98ykTxUhy8VNjD4m9m/AmemPPQX7v65DOewlPtSlxJ1963AVmit6pnhuUVEZAQDg7+7/3bOc8wBqzq+XwkcyvmcIiKSQxGlno8D55nZOWb2MuAmYEcB5xURkR5yBX8z+z0zmwPeBHzBzHYl959tZjsB3P0YcBuwC3gG2ObuT+drtoiI5JFrwNfdPwt8NuX+Q8DVHd/vBHbmOZeIiISjGb4iIg2k4C8i0kDRbuBuZi8A3+u4aznww5Kak0Xs7YP42xh7+yD+Nqp9+cXexkHt+2V3XzHoSaIN/t3MbDbLjvRlib19EH8bY28fxN9GtS+/2NsYqn1K+4iINJCCv4hIA1Up+G8tuwEDxN4+iL+NsbcP4m+j2pdf7G0M0r7K5PxFRCScKvX8RUQkkGiDv5m9w8yeNrMTZtZzZNvMvmtm+83sSTNL3Ums5Pa91cwOmNlBM9tYVPuSc59hZv9iZt9Kvp7e47jjyfV70szGvu7SoGtiZi83s4eSxx8zs9XjbtOQ7Xu3mb3Qcc1uLbh9HzWz583sqR6Pm5ndl7R/n5m9LrL2XW5mhzuuX+E74JjZKjP7kpk9k/wd/0nKMaVdx4zty3cd3T3Kf7S2hjwf+DIw0+e47wLLY2wfrW0rvw2cC7wM2AtcUGAb/wrYmNzeCNzd47ifFNimgdcE+CPgQ8ntm4CHImvfu4H7i37NdZz/N4HXAU/1ePxq4Iu0llN/I/BYZO27HPinsq5f0oazgNclt38J+GbK77m065ixfbmuY7Q9f8+2S1hpMrav7F3MrgMeSG4/AKwv8Ny9ZLkmne1+GFhnZmn7QpTVvlK5+1eAH/U55Drg497yKDBpZmcV07pM7Suduz/n7l9Lbv8PrUUnp7oOK+06ZmxfLtEG/yE48M9mtifZCSwmabuYBf0FDvBqd38OWi8m4FU9jjvNzGbN7FEzG/cbRJZr8vNjvLUq7GHglWNu16JzJ3r9zt6epAIeNrNVKY+XqezXXRZvMrO9ZvZFM7uwzIYkacU1wGNdD0VxHfu0D3JcxyK2cewpwC5hAGvd/ZCZvQr4FzP7RtLziKF9mXcxG1W/Ng7xNNPJNTwX2G1m+93922FauEiWazL269ZHlnN/HnjQ3X9mZu+l9SnlirG3LLsyr18WX6O1BMFPzOxqYDtwXhkNMbNfBD4N/Km7/3f3wyn/pdDrOKB9ua5jqcHf8+8ShreWj8bdnzezz9L62B4k+Ado39h3MevXRjP7gZmd5e7PJR9Xn+/xHO1r+KyZfZlWL2NcwT/LNWkfM2dmpwLLKC6NMLB97v5ix7cfBu4uoF3DiHr3vM4g5u47zezvzGy5uxe6no6ZLaUVWP/R3T+Tckip13FQ+/Jex0qnfczsF8zsl9q3gd8BUisMSlL2LmY7gFuS27cAiz6tmNnpZvby5PZyYC3w9TG2Kcs16Wz3DcBuT0a4CjCwfV1532tp5WNjsgN4V1Kt8kbgcDv9FwMzO7M9hmNml9GKQy/2/1/B22DAPwDPuPtf9zistOuYpX25r2NRo9cjjHb/Hq133p8BPwB2JfefDexMbp9LqxpjL/A0rXRMNO3zkxUD36TVky6sfcm5Xwk8Anwr+XpGcv8M8JHk9puB/ck13A+8p4B2LbomwJ3Atcnt04BPAQeB/wTOLfi6DWrfXcnrbS/wJeA1BbfvQeA54GjyGnwP8F7gvcnjBnwwaf9++lTLldS+2zqu36PAm4tsX9KG36CVwtkHPJn8uzqW65ixfbmuo2b4iog0UKXTPiIiMhoFfxGRBlLwFxFpIAV/EZEGUvAXEWkgBX8RkQZS8BcRaSAFfxGRBvp/RNEY8SiTfQkAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from sklearn import datasets\n",
    "\n",
    "X, y = datasets.make_moons(noise=0.25, random_state=666)\n",
    "\n",
    "plt.scatter(X[y==0, 0], X[y==0, 1])\n",
    "plt.scatter(X[y==1, 0], X[y==1, 1])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们使用不带任何限制的决策树对样本进行分类，可以看到为了让决策树的每个节点包含的样本纯度达到最高，最极端的情况就是每个节点只包含一个类别。虽然这样对样本数据的分类准确度非常高，但这是典型的过拟合情况，模型的泛化能力非常差。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/home/aneasystone/anaconda3/lib/python3.7/site-packages/matplotlib/contour.py:1000: UserWarning: The following kwargs were not used by contour: 'linewidth'\n",
      "  s)\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYQAAAD8CAYAAAB3u9PLAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAIABJREFUeJzt3XuQHeV55/Hvo5kBDdJYgxBE4mIJHOwN3mDLqMAOZMEmGFDFIBNcBv8RXGVbxWZhd10xXiiqFBe1W4CpXRcBZ7OCUJFTu/hCMBaxVLKNsezsLjdFIG6xuRTEsmSGy2oYiRHM5dk/Th9x5sy5d5/ut7t/nyqVzm1Ov9NnTj/dz/u872vujoiIyIKsGyAiImFQQBAREUABQUREIgoIIiICKCCIiEhEAUFERICEAoKZ3WVmY2b2VJPnzzGzcTN7PPq3IYntiohIcgYTep+/BW4HvtXiNb9w9z9OaHsiIpKwRK4Q3P3nwBtJvJeIiGQjqSuETnzMzJ4A9gBfcfen619gZuuB9QCLDj/8tJOXL0+xeVIGA8teBuCX75zC7755IOPWpOv59yziA4c9M+/xXvZFdT9KeHbs4DV3P7qXn7Wkpq4ws1XAP7j7v27w3HuAWXffb2ZrgVvd/eRW77d61Sp/8PrrE2mbSNXol9YD8PGXH+f7P3ok49ak69OfPJ0HV3543uO97IvqfpTwmLHD3df08rOpVBm5+5vuvj+6vQUYMrNlaWxbREQ6k0pAMLPlZmbR7dOj7b6exrZFRKQzifQhmNndwDnAMjPbDfwFMATg7n8NXAr8WzObBiaBy1zTrIqIBCWRgODul7d5/nYqZakiIhIojVQWEREg3bJTyaktE8Pc9sYIv50eYPngDFcvnWDtyGTWzRKRhCkgFEg/DtxbJoa54dUlHPTKxeTe6UFueHUJgIKCSMEoZVQQ1QP33ulBHDt04N4yMRzrfW97Y+RQMKg66Au47Y2RWO8rIuFRQCiIfh24fzs90NXjIpJfCggF0a8D9/LBma4eF5H8UkAoiH4duK9eOsFCm53z2EKb5eqlE7HeV0TCo4BQEP06cK8dmWTD0eOsGJzGcFYMTrPh6HF1KIsUkKqMCqJ6gO5HeejakUkFAJESUEAoEB24RSQOpYxERARQQBARkYgCgoiIAAoIIiISUUAQERFAAUFERCIKCCIiAiggiIhIRAFBREQAjVQuPK12JiKdUkAoMK12JiLdUMqowLTamYh0QwGhwLTamYh0QwGhwLTamYh0QwGhwLTaWXltmRjmwpePYfULK7jw5WPYMjGcdZMkB9SpXGD9XDRHwtWsmGDxrw7AyowbJ0FTQCg4LZpTPs2KCaYefhPOy6hRkgtKGYkUTLOigZn96juS1hQQpFCUO29eNDCwWNVl0poCghRGNXe+d3oQxw7lzssWFJoVExx5xnsyapHkhQKCFEanA/Hu23k2//J3e/t2FZH1VcrakUk2HD3OisFpDGfF4DQbjh5n5P2LUm2H5I86laUrIc+N1MlAvPt2ns11917NzNQM1FxFwPzpPHr5XUOZLqRRMcEdqW1d8kpXCNKx0FMynQzEu2XbFUxOLZzzfKOriF5/V00XInmmgCCHtEt1hH6w62Qg3p59yxr+bP3VRa+/q6YLkTxTQBCgszPi0A92zXLntamTY0dfa/iz9VcXvf6umi5E8iyRgGBmd5nZmJk91eR5M7O/NLPnzWyXmX0kie1Kcjo5I87DwW7tyCRbV46x83172bpybF4e/ZrzNzE8dHDOY42m8+j1d9V0IZJnSV0h/C1wQYvnLwROjv6tB/57QtuVhHRyRlyEg9261du58ZLbGFg80PQqAnr/XTu5ShEJVSJVRu7+czNb1eIlFwPfcncHHjKzUTNb4e57k9i+xLd8cIa90/P/HGrPiOvnRlqyYBZ3uH5slNveGAmq4qiVdau3c+vSW/n+jx5p+po480BpuhDJq7TKTo8Dfl1zf3f02JyAYGbrqVxBcPzSpSk1TaByRlxbLgmNz4irB7tQyiv7KekDe8gluyKQXqeyNXjM5z3gvtHd17j7mmUjYVSulEW3qY7QK45CE3rJrgikd4WwGzih5v7xwJ6Uti0d6uaMOPSKo9C0CqC9XiXoikOSltYVwmbgT6Nqo48C4+o/aC3r6Q/ayUPFUUiSDqC64pB+SKrs9G7g/wIfMLPdZvYFM7vSzK6MXrIFeBF4nsoI+j9LYrtFlYcvexEqjtKUdABVyk76Iakqo8vbPO/Av0tiW2XQj/RC0rQaW3c67bTvlFJ20g+a3C5Aefmyq7yyc0kH0E7KhEW6pYAQoBC/7OrAjC/JAJr0FYcIaC6jIIWWn89Dn0bZaES09IOuEALUj/x8nDP8PPRplFGsK45dg/DAQhg37l70GYaGPsHUotOSbaDkjgJCoJJML8QdVZyXPo1Whg7sYOHEVvjaCCxxzv3Qj4ElWTerqb6m6HYNwv3DMFUZL7r8wCu43cNboKBQckoZlUDcEsW8jzkYOrCDI8bvYWBmH2AwvoCv/O+vM3RgR9ZNa6jvKboHFh4KBlXmU5WAKaWmgNAHoQ0qi3uGH1qfRrcWTmzFfGruYzNvB3sA7PsYg/FGM8nAgpl9yby/5JZSRgkLcdK3uFVLeR9z0OxAF+oBsO8puiXeMCjMDowm8/6SW7pCSFiII0iTOMNvt/BMyJod6EI9APY9RXfuQRiaO7ek2xAHRy5M5v0lt3SFkLAQO2DzfoYf18GRCzl83z0M8m7aaHLB4cwGegDs+xiDU6eByUNVRr9dtJwRVRmFq6YijCVeCeinTvdlUwoICQtxUBk0rloqy2CzH8yexY6pUb488D2OtdfZ40dxy8xnOWP2FNYS3u+bSgA/dRpO3Q/A5S//ouViQZKhuoowxq1yn8m+BAUFhJjqD6pnDR/k/v1HBD+CNMS+jn657Y0R9s78IX8/84dzHn/kjelDv2towVHTggjQsCKMKas8HgX0JKkPIYZG5YH37z+CTy1+K/gRpCH2dfRLuzReqCOxQ6tWkww0qQhr+nhMukKIodlB9R8nF7J15VhGrepMr30doZ1Jd6JdGi/EkdhluoKTFppUhLFk3oKTidAVQgwhdiB3qpdKlizOpJM4S25UZWWDdiiNF+LnWKYruEztGoRvLK6MYP/G4sr9kDSoCGMo6ljuAwWEGPI8greXUtS0D1JJBaC5E8HNctzoGEedPXroTDvEzzHEIFU41Q7b8QVUR7Bz/3BYQeHUafjUJCyZBbzy/6f606EMShnFkucpiHupZEn7IJVkKqfaSTv6pfUAfPzlx+GlynMhfo6hVqsVSsodtj2rqQjrNwWEGPJe399tJUvaB6m0AlCIn2OIQapwUu6wzQMFhJjKVB6Y9kGqzGfJIQapwkm5wzYPFBCkY2kfpNIKQKFW9JTpZCMT5x6cO+gL+tphmwcKCNKVNA9SaQWgEMtOJQV1U3j0e1qIPFBAkI5VO2TT9LnoXz/10leRx/EY0kCKHbZ5oLJTKb1uy05DHdksEpcCgqQj4AFA3Y7J0KAxKapwvpUlUNo0Q8ozNnar274KDRqTolJASEmolSypyMEAoG46y8tcDivFppRRSkqdZijYAKC8rzEt0owCQkpKnWZoNtAnpwOA5s6N5IwumOFwnOvHRjVNteSaUkYpKVWaoX7Jv5On4InDCjUAqJpiKnUqUApHVwgpyTrNkNpiK41mkHziMPjQO6nN2JimUqcCpXB0hZCSLOemSfUstlkH8nND8OUwOpCTVOpUoBSOAkJM3ZSSZjU3TapTMxSsA7mdUqUCpfCUMoohLyNWUz2LLVgHcjtZpwJFkqSA0EQnOfe85I9TXREs5SX/slZfcbRicJoNR4+ndiWYWt+QlEIiKSMzuwC4FRgA7nT3m+qe/zxwC/Cb6KHb3f3OJLbdD53m3POSP051HYMSziCZVSpQFU6StNgBwcwGgG8C5wG7gUfNbLO7P1P30u+4+1Vxt5eGTnPueckfp96hrRkkU6FpuyVpSVwhnA487+4vApjZt4GLgfqAkBudnvnnaZlDLbZSPHm5QpX8SKIP4Tjg1zX3d0eP1fsTM9tlZveY2QmN3sjM1pvZY2b22GsT3R9Uk8qndppzzzp/LOXW7O/UQf0J0pMkAkKjesL6kpL7gVXufirwE2BTozdy943uvsbd1ywb6a5jNsmKn24qR9aOTLJ15Rg737eXrSvHFAwkNY3+TivCrXiTsCUREHYDtWf8xwN7al/g7q+7+9vR3TuA0xLY7hxJVvzozF/yoPbvdP45WJgVbxK2JPoQHgVONrMTqVQRXUbdqodmtsLd90Z3LwKeTWC7cySdT1XOXfKg+ne6+oUVDUKC+hOkO7EDgrtPm9lVwDYqZad3ufvTZnYD8Ji7bwb+vZldBEwDbwCfj7vdenmp+MmroQM7KiudlaSUNG/09y9JSGRgmrtvcff3u/v73P2/RI9tiIIB7n6du3/Q3T/k7h93939OYru1khwxqsE+cw0d2MER4/fMnbDu/uGglsEsO42YliQU5hudVK29BvvMt3BiK+ZTcx8MbMWzsuv17/++nWfzLz/cy+r9K8q1rKs0VJiAAMnk/TXYZ74FM/saP1HQCetC1W4ixW7//u/beTbX3Xs1M1Mz1FYmVd9LykdzGdXRYJ/5ZgdGGz9R0AnrQrRlYpgNY3PLqjeMxSsrvWXbFUxOLZzzmCqTyk0BoU6qE8HlxMGRC3EbmvtggSesC9HNr76H6bqv6zQLuPnV9/T8nnv2LWv4eJlPfspOAYG5nciTs8Yg6pyrNbXoNN5acmkhVzzLi3Fv/FVt9ngnjh19reHjZT75KbvSB4T6Ec77ZgcwjCU2o0FpNaYWnVZZ8exrE5X/FQxy75rzNzE8NPcqr+wnP2VXqE7lXjTqRJ7COGLA2b5yb5OfEknX6IJZ9s3OT+WMLmg0dUVn1q3eDsCf//BaZvdPq8pIFBDUiSx58NVlb/IXY6NM1UwdNoTz1WVvxnrfdau3c+vSW/n+jx7p+Gc0SLG4Sh8Q4o7w7GZNZZFepb6mRROHBilWr6rHrTJIEfUpFUHpA0KcNQ00iE3SFML8WhqkWGylDwhxzrw0iC0QuwZLtWRnljRIsdgKERDipm16PfNS/0MAdg1WUhZT0QGpVQqjJnDcvegzDA19olI9JR2bHRhloFFQ0CDFQsh92WmSC+N0S4PYAvDAwneDQVU1hVGrGjiiCfqWH3iFI8bvqXSQSsceGrqYST9s7oMpDVK8b+fZnHnTXZx47WbOvOku7tt5dt+3WTa5v0LIMm2TpzWVC6tZqqL+8QaBw3yKhRNbdZXQoS0Tw9wwfh6ftEV8dfC7HGuvs5elvDTwx3zw4d+Hh/u87Zrv2m/2HcO13/1z3nrwi0rPzrO+55/MfUDIMm0TSuVHqS3xxkGhPoXRJHA0zYnLPNWTr81+FpvfOevQ4ytmptl61Fgq266l/rrk5T4gZL0wSAiVH6V27sG5fQjQOIXRJHA0nbhP5sny5Ev9denIfR+CFgYpuVOnK/MqtZtn6dyDlUBRw22IgyMXptfWnMuyz0z9denI/RWC0jbCqdPta+BPnQYmD1UZ/XbRckZUZdSVs4YP8r2JRVAzWjqtky/116Uj9wEBlLaRDtUEjstf/kVX0zWU3ZaJYe7ffwS1wQCcTy1+K5XvXl5P/IYO7GDhxFYWzOxjdmCUgyMXBn0SUoiAICL91ahTF4x/nFwIxJtPqVNZn/h1e3CvTvNRHdk9MLOPI8bv4S0INiiYe5gDSlavWuUPXn991s3ItdEv9V5+JlLrxGs34w26HA1n5/sazwpcqL+/+gGQUOmTarUuyDcWR+Ne6iyZrUwh3ydm7HD3Nb38bO47lUWk/0q/mE6nAyBrdTpGJiAKCCLSVukX0+nl4N5sOo+Ap/lQQBCRttat3s6Nl9zGcaNj5VxJsJeDe4NS59DXIlensoh0ZN3q7axbvZ19d2zMuinp63QAZK26Uuc8zMSrgCAi0kj9tOofegeeG+ru4N7JGJmAKCCIiNRrNK36E4e1rioqAPUhiIjU66WqqAB0hSDZ04pnEpoclowmQQEhI3FXeUtECAfiblY8K7n7dp7NLduuYM++ZRw7+hrXnL+Jdau3Z92sYup0WvWCUUDIQP1iH9VV3oD0gkIoB+JWl+Y56ozrt/t2ns11917N5FQlZfGbfcdw3b1XAygo9EMvVUWthHDy1QH1IWSg1WIfqQklR1rSS/Nu3bLtikPBoGpyaiG3bLsioxYVXKfTqneibvlWxhdU7u8K73w8vBaVQFqLfbSqF18y/hUaHXJ9fAHjKdaZjwz854aLts8MHMnEHf81tXaEbs++o5s+XspxAWlIqmQ0R1fBukLIQAiLfTRbKSztFcQOjlyI29Ccx7RwzXwh/M1Ij3J0FayAkIEQVnkL5UA8teg03lpyKTMDozgwMzDKW0suDXZ64KyE8DcjPcrRnEaJpIzM7ALgVmAAuNPdb6p7/nDgW8BpwOvAZ939pSS2nUdxFvvopjqp7fTDdR1ddu44i079H13/Pkka4E0WkW0bQvQ54IhAqoyUoupS0h3UfRQ7IJjZAPBN4DxgN/ComW1292dqXvYF4P+5+++a2WXAzcBn4247z3pZ7CPx6qScDasvu+pcQn2Xk4qY3MjRnEZJXCGcDjzv7i8CmNm3gYuB2oBwMfC16PY9wO1mZh7q6jyBalWdVJpZJ6WiXwftUMqRiyYnJ19JBITjgF/X3N8NnNHsNe4+bWbjwFHAnFU3zGw9sB7g+KVLE2hasaRVnSSB6+dBu4eKmCAGWeZZQFdkSQSEhtWLPbwGd98IbITKEprxm1Ysywdn2Ds9/yNTpUmOJPHl72cZY5cVMa3SmJ+rfWFAB72gBHZFlkSV0W7ghJr7xwN7mr3GzAaBJcAbCWy7VFRpknNJDVDqZxljlxUxHQ2yzNHArNSFMkA0kkRAeBQ42cxONLPDgMuAzXWv2QxUh1ReCvxU/QfdWzsyyYajx1kxOF3OVavyLqkvfz/LGLtc5aujNGZgB72gBDZGIXaIjvoErgK2USk7vcvdnzazG4DH3H0z8DfA35nZ81SuDC6Lu92y6qU6qZRCTFG0+PJ3NXFdP8sYu6yI6SiN2c1BL8TPrZ8Cm0QvkWs2d98CbKl7bEPN7YPAZ5LYlgQk1C9vYHnZQ5p8+d8aPqy7iev6XcbYRUXM1Usn5vQhQIM0ZqcHvVA/t34KbIyCknjSm5C/vKHNHVMbOHHm1FgMOV+f+mzTieuaXiVkWMY4+qX1fPzlxw/dX/yrA0w9/CYz+2cYWDzA4jOO5I73v/fdTuVOD3qhfW5pCGyMggKC9Ca0L++cg24TWeRl6wMncKjALvryb/pfFzT80T37lvW/fT16cOWH372zksqw1GY6PegFlk9PTUBjFBQQpDchfXkbHnQbyCIv2yhwYpXplL9cOQgcu+U1frPvmHk/euzoa/Mey61ODnqB5dPLSJPbSW9CmrCr4UG3TlZ52Q4C5zXnb2J4aG7bhocOcs35m/rZsvB0WeEkyVNAkN6E9OVtelXixF7cJK4OAue61du58ZLbOG50DGOW40bHuPGS28q3ElqSi9JIT5Qykt6E1BnWKtXw5Yxzsx12qKY2cV3oAsqnl5ECgvQu7pc3qbLVwEr35ggpcPYq1PJiSZwCgmQjybLV0A+61cBZPbDeOwwPBNbGZkItL04zSJUoICogSDaSLlsNPdUQ6oG1ndDKiyHdfZnXz61H6lSWbIRUtpqGvM7nE+LnlOa+zOvn1iMFBMlGSGWraQjxwNqJED+nNPdlXj+3HikgSDaSLlvdNQjfWAxfG6n8H9rUyiEeWDsRUnlxVZr7Mq+fW48UECQbSdac52G+/RAPrJ0IcWxAmvsyr59bjwL6xkjpJNURHGLHZ73QK6FaCa3DPs19mefPrQcKCJJ/ecnzhnZgzbM092WJPjcFBMk/TYoWplDr90NtVwDUhyD5V7I8by6E2q8TarsCoYAg+Rdix2fZhVq/H2q7AqGwKMVQojxvXySdRgm1XyfUdgVCVwgiZdePNEqo9fuhtisQCggiZdePNEqo/TqhtisQShmJlF0/0iih1u+H2q5AKCCIlF2/ynZD7NdRyWlLShmJlF1Z0igqOW1LAUGk7MpStquS07YUGkWSkud0RIjpnaSp5LQtBQSRJLRbWSvPwaIoNMVJW0oZiSShVTpCueswlKWvJAYFBJEktEpHKHcdhrL0lcSgUxSRZrpJ87RKRyh3HY4y9JXEoIAg0ki7PoF65x6c+3p4Nx1RDSr1sshdqy9DWlDKSKSRbtM8rdIRoeSu1ZchbegvQaSRXtI8zdIRoUyXkIelRiVTCggijSRdohhC7lp9GdJGrJSRmS01sx+b2XPR/0c2ed2MmT0e/dscZ5siqQglzZMkTf0sbcTtQ7gWeMDdTwYeiO43MunuH47+XRRzmyL9V8QSxSIGOUlU3JTRxcA50e1NwM+A/xTzPUV6l2QVTQhpniSF0pchwYobEH7H3fcCuPteMzumyesWmtljwDRwk7vf1+hFZrYeWA9w/NKlMZsmpdNtqWgZFS3ISaLaBgQz+wmwvMFT13exnfe6+x4zOwn4qZk96e4v1L/I3TcCGwFWr1qlxKZ0R1U05aSxFYlpGxDc/Y+aPWdmr5jZiujqYAUw1uQ99kT/v2hmPwNWA/MCgkgsqqIpH10VJipup/Jm4Iro9hXAD+pfYGZHmtnh0e1lwJnAMzG3KzKfqmjKR/NEJSpuQLgJOM/MngPOi+5jZmvM7M7oNb8HPGZmTwAPUulDUECQ5KmKpnx0VZioWJ3K7v46cG6Dxx8Dvhjd/j/A78fZjkhH2lXRKNdcPFrjIFEaqSzF0qyKRrnmYmo1qaB0TZPbSTko11xMRRxAmCFdIUg5KNdcXBpbkRhdIUg5qAJJpC0FBCkHVSCJtKWUkZSD5vERaUsBQcpDuWaRlpQyEhERQAFBREQiCggiIgIoIIiISESdyiLSmOZ+Kh0FBBGZT3M/lZICgkjZNboS0OpzpaSAIFJmza4Eppq8XnM/FZo6lUXKrNmVQLPjvuZ+KjRdIYhkIZQO22Zn/E5lrietM1AqCggiaQupw7bVimPVvoSkg1YowVDmUUAQSVtIHbatVhzrx9xPIQVDmUd9CCJpC2mxnrRXHNPKdUHTFYJI2kJbGD7NWWBDCoYyj64QRNJW5sV6tHJd0HSFIJK2XhfrKUJnbKs+C8mcAoJIFrpN0xSlM1Yr1wVNAUEkD0KqTIpLK9cFS30IInmgzlhJgQKCSB6oM1ZSoJSRFFcROmGr1BkrKVBAkGIqSidslTpjJQUKCFJMReqErVJnrPSZAoIUU5qdsEVKTUmpqVNZiimtTthqamp8AWCV/+8frjwukjMKCFJMaU0PocnapEB0GiPFlFYnrMYHSIEoIEhxpdEJG9rMpSIxxEoZmdlnzOxpM5s1szUtXneBmf3SzJ43s2vjbFMkKGWeuVQKJ24fwlPAJcDPm73AzAaAbwIXAqcAl5vZKTG3KxKGtBeYEemjWCkjd38WwKxlvvR04Hl3fzF67beBi4Fn4mxbJBgaHyAFkUYfwnHAr2vu7wbOaPRCM1sPrI/uvn3k+vVP9bltSVgGvJZ1IxpaP+deuO2cS+1MltqZnDy0EeADvf5g24BgZj8Bljd46np3/0EH22h0+dCwx83dNwIbo+0+5u5N+yVCoXYmS+1MltqZnDy0ESrt7PVn2wYEd/+jXt88shs4oeb+8cCemO8pIiIJS2Ng2qPAyWZ2opkdBlwGbE5huyIi0oW4ZaefNrPdwMeAH5rZtujxY81sC4C7TwNXAduAZ4HvuvvTHbz9xjhtS5HamSy1M1lqZ3Ly0EaI0U5z1wAaERHRXEYiIhJRQBARESCggNDFNBgvmdmTZvZ4nPKqXuVlug4zW2pmPzaz56L/j2zyuploXz5uZql19rfbP2Z2uJl9J3r+YTNblVbb6trRrp2fN7NXa/bhFzNo411mNmZmDcftWMVfRr/DLjP7SNptjNrRrp3nmNl4zb7ckEEbTzCzB83s2eh7/h8avCbz/dlhO7vfn+4exD/g96gMqPgZsKbF614CloXcTmAAeAE4CTgMeAI4JeV2fh24Nrp9LXBzk9ftz2Aftt0/wJ8Bfx3dvgz4TqDt/Dxwe9ptq2vDvwE+AjzV5Pm1wFYqY4I+CjwcaDvPAf4h4325AvhIdHsE+FWDzzzz/dlhO7ven8FcIbj7s+7+y6zb0U6H7Tw0XYe7vwNUp+tI08XApuj2JmBdyttvpZP9U9v+e4Bzrc0cKX0QwufYlrv/HHijxUsuBr7lFQ8Bo2a2Ip3WvauDdmbO3fe6+z9FtyeoVEYeV/eyzPdnh+3sWjABoQsO/MjMdkRTXYSo0XQdsT+sLv2Ou++Fyh8PcEyT1y00s8fM7CEzSytodLJ/Dr3GK6XL48BRqbSuQRsizT7HP4lSB/eY2QkNns9aCH+PnfqYmT1hZlvN7INZNiRKU64GHq57Kqj92aKd0OX+THU9hASmwQA40933mNkxwI/N7J+jM4/EpDldRxyt2tnF27w32p8nAT81syfd/YVkWthUJ/snlX3YRidtuB+4293fNrMrqVzVfKLvLetOCPuyE/8ErHT3/Wa2FrgPODmLhpjZYuDvgf/o7m/WP93gRzLZn23a2fX+TDUgePxpMHD3PdH/Y2b2fSqX9YkGhATamcp0Ha3aaWavmNkKd98bXc6ONXmP6v580cx+RuVMo98BoZP9U33NbjMbBJaQfrqhbTvd/fWau3cAN6fQrm7lYvqY2gOau28xs78ys2XunuqEcmY2ROUg+z/d/d4GLwlif7ZrZy/7M1cpIzNbZGYj1dvAJ6msyRCaEKbr2AxcEd2+Aph3ZWNmR5rZ4dHtZcCZpDMteSf7p7b9lwI/9ainLEVt21mXO76ISi43NJuBP42qYz4KjFfTiSExs+XVfiIzO53K8en11j+VeBsM+BvgWXf/b01elvn+7KSdPe3PtHvHW/Saf5pK5H0beAXYFj1+LLAlun0SlUqPJ4CnqaRwgmunv1uJ8CsqZ9tZtPMo4AHguej/pdHja4A7o9v+b7KgAAAAnElEQVR/ADwZ7c8ngS+k2L55+we4Abgour0Q+B7wPPAIcFJGf5ft2nlj9Lf4BPAg8K8yaOPdwF5gKvrb/AJwJXBl9LxRWaTqhehzblrFl3E7r6rZlw8Bf5BBG8+ikv7ZBTwe/Vsb2v7ssJ1d709NXSEiIkDOUkYiItI/CggiIgIoIIiISEQBQUREAAUEERGJKCCIiAiggCAiIpH/Dw3raGPUZw7HAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "from sklearn.tree import DecisionTreeClassifier\n",
    "\n",
    "dt_clf = DecisionTreeClassifier()\n",
    "dt_clf.fit(X, y)\n",
    "\n",
    "def plot_decision_boundary(model, axis):\n",
    "    X0, X1 = np.meshgrid(\n",
    "        np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),\n",
    "        np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1),\n",
    "    )\n",
    "    X_grid_matrix = np.c_[X0.ravel(), X1.ravel()]\n",
    "    \n",
    "    y_predict = model.predict(X_grid_matrix)\n",
    "    y_predict_matrix = y_predict.reshape(X0.shape)\n",
    "    \n",
    "    from matplotlib.colors import ListedColormap\n",
    "    my_colormap = ListedColormap(['#EF9A9A', '#40E0D0', '#FFFF00'])\n",
    "    \n",
    "    plt.contourf(X0, X1, y_predict_matrix, linewidth=5, cmap=my_colormap)\n",
    "\n",
    "plot_decision_boundary(dt_clf, axis=[-1.5, 2.5, -1.0, 1.5])\n",
    "plt.scatter(X[y==0, 0], X[y==0, 1])\n",
    "plt.scatter(X[y==1, 0], X[y==1, 1])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "解决过拟合通常使用 **剪枝**（pruning）策略，最简单的一种方法是限制决策树的深度，我们给 `DecisionTreeClassifier` 增加一个参数 `max_depth=2` 来看下效果："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/home/aneasystone/anaconda3/lib/python3.7/site-packages/matplotlib/contour.py:1000: UserWarning: The following kwargs were not used by contour: 'linewidth'\n",
      "  s)\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYQAAAD8CAYAAAB3u9PLAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAHsRJREFUeJzt3X+QXeV93/H3V7uLtIjNLkIQCUGQcUlqp1EqS4PtQGoahYI0NSIYj3H+CJ7iaGgKbT0TEjx0FA+TDhDP1JMIN6lMmMidxnZMCJZaaaiNMW6T4iIZEL+c8GPssZDwAqqWFdrF++PbP+65Yvfu/XHuPeee85xzPq8Zzd69e3TPs+fuPd9zvs/3eR5zd0RERJbl3QAREQmDAoKIiAAKCCIiElFAEBERQAFBREQiCggiIgKkFBDM7H4zGzezZ1v8/AozmzCzp6J/O9PYr4iIpGcwpdf5C+Be4Mtttvlf7v4vU9qfiIikLJU7BHf/LnA8jdcSEZF8pHWHEMeHzexp4Cjwu+7+XOMGZrYD2AGwcvnyTZesWZNh80QkroHVP8q7CdLCoUO84e7n9vJ/swoI3wcucveTZrYNeAi4pHEjd98N7AbYuH69P3rHHRk1T0S6MfbbO/JugrRgRs/ROpMqI3d/y91PRo/3A0NmtjqLfYuISDyZBAQzW2NmFj2+NNrvm1nsW0RE4kklZWRmXwGuAFab2RHgD4AhAHf/M+B64F+b2SwwBdzgmmZVRCQoqQQEd/9kh5/fS60sVUREAqWRyiIiAmRbdioFtX9ymF3HR3htdoA1g3PcumqSbSNTeTdLRFKmgFAi/Thx758c5s7XR5n22s3ksdlB7nx9FEBBQaRklDIqifqJ+9jsII6dPnHvnxxO9Lq7jo+cDgZ1076MXcdHEr2uiIRHAaEk+nXifm12oKvnRaS4FBBKol8n7jWDc109LyLFpYBQEv06cd+6apIVNr/ouRU2z62rJhO9roiERwGhJPp14t42MsXOcydYOziL4awdnGXnuRPqUBYpIVUZlUT9BN2P8tBtI1MKACIVoIBQIjpxi0gSShmJiAiggCAiIhEFBBERARQQREQkooAgIiKAAoKIiEQUEEREBFBAEBGRiAKCiIgAGqlcelrtTETiUkAoMa12JiLdUMqoxLTamYh0QwGhxLTamYh0QwGhxLTamYh0QwGhxLTaWXXtnxxm64/OY+PLa9n6o/PYPzmcd5OkANSpXGL9XDRHwqViAumVAkLJadGc6mlXTKC/BWlHKSORklExgfRKAUFKRblzFRNI7xQQpDTqufNjs4M4djp3XrWgoGIC6ZUCgpRG3IF4/b6LyPsuZdvIFDvPnWDt4CyGs3Zwlp3nTqj/QDpSp7J0JeS5keLkzrupwOnldw2lwkfFBNIL3SFIbKGnZOLkzru5i+jld9V0IVJkCghyWqdUR+gnuzi587gVOL3+rqrwkSJTykiAeKmO0E92cQbirRmc49js0j/7xruLXn/XuK8vEqJU7hDM7H4zGzezZ1v83MzsT8zsJTM7bGYfSGO/kp44V8RFKGfcNjLFgYvGefK9xzhw0fiSPHrcCpxef1dV+EiRpZUy+gvg6jY/3wpcEv3bAfxpSvuVlMS5Ii7DyS5uBU6vv6sqfKTIUkkZuft3zWx9m022A192dwceN7MxM1vr7sfS2L8kFyfV0ZiSGV02jzvcMT7GruMjQVUctROnAifJPFCq8JGiyqoPYR3w4wXfH4meWxQQzGwHtTsILli1KqOmCdSuiBf2IUDzK+L6yS6U8sp+SvvEHnLJrghkV2VkTZ7zJU+473b3ze6+efVIGJUrVdFtqiP0iqPQhF6yKwLZ3SEcAS5c8P0FwNGM9i0xdXNFHHrFUWj6MQOp7jgkbVndIewFfiuqNvoQMKH+g/bynv6gkyJUHIUk7QCqOw7ph7TKTr8C/B/gF8zsiJndZGY3m9nN0Sb7gVeAl4AvAb+Txn7Lqggf9jJUHGUp7QCqlJ30Q1pVRp/s8HMH/k0a+6qCIixwotXYuhO30z4upeykHzRSOUBF+bCrvDK+tAOoRkRLPyggBCjED7s6MJNLM4CmfcchAprcLkih5eeL0KdRNRoRLf2gO4QA9SM/n+QKvwh9GlWU5I5j6O1DrJg8wLK5E8wPjDE9spWZlZtSbqEUjQJCoNJMLyQdVVyUPo12inYC7GeKbujtQ5w58QDmMwAMzJ3gzIkHOAVBHxPpP6WMKiBpiWLRxxzUT4ADcycw3j0BDr19KO+mNdXvFN2KyQOng0Gd+QwrJg+k8vpSXAoIfRDaoLKkV/ih9Wl0q2gnwH6PMVg2d6Kr56U6lDJKWYiTviWtWir6mIOinQD7naKbHxhjoMnvPj8wlsrrS3HpDiFlIY4gTeMKv9PCMyFrdaIL9QTY7xTd9MhW3IYWPec2xPTI1lReX4pLdwgpC7EDtuhX+ElNj2xl+YkHGOTdtNEsQ7wT6Amw32MMZlZu4hQUqpO90g4PwiMrYMJg1GHLNGyY7cuuFBBSFuKgMmhetVSVwWbfmL+cQzNjfGbg65xvb3LUz+ELcx9n0/w/YRvh/b5ZBPCZlZsUAIrg8CDsG4aZaAWBCat9z1RfgoICQkKNJ9XLh6fZd/LM4EeQhtjX0S+7jo9wbO5X+eu5X130/N8dnz39u4YWHDUtiAC1O4OZhuVkZqz2/IaTqe9OfQgJNCsP3HfyTD561qngR5CG2NfRL53SeKGOxA6tWk1yMNFsbbE2zyekO4QEWp1U//fUCg5cNJ5Tq+Lpta8jtCvpODql8UIciV2lOzhpY9Sbn/xHlyw4mQrdISQQYgdyXL1UsuRxJZ3GVXKnKqsQ38cq3cHl6vAgfOEs+NxI7evhwK6Rt0zDUMPJfyjqWO4DBYQEijyCt5dS1KxPUmkFoE4TwYX4PoYYpEqn3mE7sQyw2td9w2EFhQ2z8NEpGJ0HvPb1o/3pUAaljBIp8hTEvVSyZH2SSjOV066TNsT3MdRqtVLJuMO2ZxtmM2uPAkICRa/v77aSJeuTVFYBKMT3McQgVToZd9gWgQJCQlUqD8z6JFXlq+QQg1TpZNxhWwQKCBJb1ieprAJQqBU9VbrYyMWW6cWDvqCvHbZFoIAgXcnyJJVVAAqx7FQysGEWmMpsWogiUECQoGURgHrpqyjieAxpIsMO2yJQ2alUXrdlp6GObBZJSgFBMjH09iFGXvtDRl/9XUZe+8OgVivrdkyGBo1JWSlllKGqphlCX8O3274KDRqTslJAyEiolSxZaLeEZQgBAbrrq6hyOayUm1JGGalymqFoS1h2UvQ1pkVaUUDISJXTDEVbwrKTxrmRxpbNsRznjvExTVMthaaUUUaqlGYYevvQouUZZ854H8umDy5KGxV9Dd96iqnKqUApH90hZCTvNENWi63UO5AH5k5g1DqQl08f5J0Vm5kbGMOBuYExTo1eH0z/QRJVTgVK+egOISN5zk2T5VVsqw7koZ++wOSa/5DqvkJQ5VSglI8CQkLdlJLmNTdNllMzlK0DuZMqpQKl/JQySqAoI1azvIotWwdyJ3mnAkXSpIDQQpyce1Hyx1muCDY9shW3oUXPFb0DuZ1Oq7H1W1Z9Q1INqaSMzOxq4I+BAeA+d7+74eefAj4PvBo9da+735fGvvshbs69KPnjLNcxmFm5iVOwqMpoemRrKTqQW8krFagKJ0lb4oBgZgPAF4ErgSPAE2a2192fb9j0a+5+S9L9ZSFuzr0o+eOsO7RnVm4qdQAIhabtlrSlcYdwKfCSu78CYGZfBbYDjQGhMOJe+RdpmUMttlI+RblDleJIow9hHfDjBd8fiZ5r9DEzO2xmD5jZhc1eyMx2mNlBMzv4xmT3J9W08qlxc+5554+l2lr9nTqoP0F6kkZAaLYideOipPuA9e6+AfgWsKfZC7n7bnff7O6bV4901zGbZsVPN5Uj20amOHDROE++9xgHLhpXMJDMNPs7rQm34k3ClkZAOAIsvOK/ADi6cAN3f9Pd34m+/RKQeoI5zYofXflLESz8O116DRZmxZuELY0+hCeAS8zsPdSqiG4AfnPhBma21t2PRd9eA7yQwn4XSTufqpy7FEH973Tjy2ubhAT1J0h3EgcEd581s1uAh6mVnd7v7s+Z2Z3AQXffC/xbM7sGmAWOA59Kut9GRan4KarGCevKXkpaNPr7lzSkMjDN3fe7+8+7+3vd/T9Gz+2MggHu/ll3/0V3/2V3/+fu/oM09rtQmiNGNdhnsWYT1p058UBQy2BWnUZMSxpKM5dRWrX2GuyzVBFWPKu6Xv/+q7qsqzRXmoAA6eT9NdhnqapNWBeqTifvbv/+dfEjjTSXUQMN9lmqahPWhWj/5DA7xxeXVe8cT1ZWWpS5uCQ7CggNspwIriiqNmFdiO55/WeYbfi4zrKMe17/mZ5fUxc/0qhUKaNeLbwVH102zyDziz58Ve+cq+KEdaGZ8ObXbq2ej0OVSdKo8gGhMY96Yn6AIZxRm+MtX6aOtogmrCufIs3FJdmofEBolkedwThzwHnsomMt/pdItsaWzXNifmkqZ2xZs6kr4slzWVcJU+UDgvKoUgS/t/ot/mB8jJkFU4cN4fze6rcSvW4vlXlDbx+CL5wFEwajDlumYcNsonZIGCofEJLmUVXHLVkI5Wq+PkiR+l31hMG+YWBKQaEEKh8QkuRRVcctWQphfq1mgxSZMXhkBWw4mU+jJDWVDwhJrrw0iC0MmmcpOy0HI040mwVfiqYUASFp2qbXKy/1P+SvnsKoX7XW51k6BUuCggJHcvMDYww0CwqjzeZalaIp/MC0NBfG6ZYGseWv3TxLC2mCvnQ8PrSdKT9j8ZNDUcdynz305Ee47O77ec/te7ns7vt56MmP9H2fVVP4gJDn8HvNMJm/uPMsxQ0c0tr+yWFumriS35/5NEfmVzPvxqt+Dk/80vq+dyg/9ORH+OyDt/LqifNwlvHqifP47IO3KiikrPApozzTNqFUflRZqxRG4zxLmqAvufrF116/nL0/vfz08+ueH+dvr/lXfd335x++kamZFYuem5pZwecfvpFrNz7W131XSeEDQt7D70Oo/Kiy6ZGti/oQoPk8S3EDh7TW6iLr6InVfd93q31kse8qKXzKSGmbaptZuYlTo9czNzCGA3MDY5wavX5JZ7Em6Euu1UXW+WNv9H3frfaRxb6rpPB3CErbSJx5ljRBX3KXD0/z9cmVsGC09PDQNLddtafv+77tqj189sFbF6WNstp3lRQ+IIDSNhKPJujr3f7JYfadPJOFwcCY52ObvplJDr++j88/fCNHT6zm/LE3uO2qPeH3HxwerA3aK8g0H6UICCLSX82q+ZxlPPqDDwL/JZM2XLvxsXwDQLcn98ODtWk9ZqIgWoBpPhQQSmzst3fk3QQpiddu39v0+cp06vZycn9kxbvb1wU+zUfhO5VFpP8q36nb7uTeSqvpPAKe5kMBQUQ6uu2qPQwPLR6NXKlO3V5O7q2m8wh4mg8FBBHp6NqNj3HXdbtYNzaOMc+6sXHuum5X+J26aenl5L5lujatx0IZTfPRK/UhiEgsuXfq5mnL9OI+BOh8ct8wC0ypykhEpPAaq4p++afw4lB3J/cNs8F2IDejgCAi0qhZVdHTZ8BHwy0ZTYP6EEREGvVSVVQCukOQ/BVsNKdUQAFLRtOggJCTpKu8pSKEE3EBR3Pm5aEnP1K8qRuKatSbn/wDLhlNgwJCDuqrvNWnAqiv8gZkFxRCOREXcDRnHuoLxNQnd6svEAMoKPRDL1VF7YRw8RWD+hBykOcqb6eFkiOt6K15t9otECN9sGG21oE8Og947WuvHcr1i6+JZYDVvu4brj0fmPBaVAF5rvJ2Wign4oremndLC8TkIK2S0QLdBesOIQetFhrJapU3IJxh9QUczZmHys8lVGShXHzFoICQgyBWeQvlRJzmrXmJVX4uoSIL5eIrhlRSRmZ2NfDHwABwn7vf3fDz5cCXgU3Am8An3P2Haey7iJKs8pZadVJIw+oLNpozD4VdIEbS76Duo8QBwcwGgC8CVwJHgCfMbK+7P79gs5uA/+fu/8jMbgDuAT6RdN9F1ssqb6lXJ+lEXCiZzSVUkIqYwgjp4quDNO4QLgVecvdXAMzsq8B2YGFA2A58Lnr8AHCvmZm7h3fPFLB21UlaQrRi+nXSDqUcuWwKcvGVRkBYB/x4wfdHgA+22sbdZ81sAjgHWNQjZmY7gB0AF6xalULTyiWI6iTJXz9P2j1UxGjAXEIB3ZGlERCadZU3XvnH2QZ33w3sBti4fr3uHhqsGZzj2OzStyzT6iRJJo0Pfz/LGLusiIk9YC6gk15QArsjS6PK6Ahw4YLvLwCOttrGzAaBUeB4CvuulCCqk6R3aQ1Q6mcZY5cVMbEGzBVoYFbmQhkgGkkjIDwBXGJm7zGzM4AbgMYVufcC9b+Q64Fvq/+ge9tGpth57gRrB2cxnLWDs+w8d0L9B0WR1oe/n2WMXZYjxxowF9hJLyiBjVFIHKKjPoFbgIeplZ3e7+7PmdmdwEF33wv8OfBfzewlancGNyTdb1X1Up1USSGmKNp8+LvKw/ezjLHLipjzx97g1RPnNX3+tG5OeiG+b/0U2Ej9VO7Z3H0/sL/huZ0LHk8DH09jXxKQUD+8geVlT2vx4T81fEZ3E9f1u4yxi4qY267as6jt0GTAXNyTXqjvWz8FNkZBSTzpTcgf3tDmjlkYOHEW1VgMOX8084mWefiWdwmBlDHGGjAX96QX2vuWhcDGKCggSG9C+/AuOum2kEdetjFwAqcL7KIP/56/vLrpfy3KxHUdB8zFPekFlk/PTCDBHRQQpFchfXibnnSbyCMv2yxwYrU5mz5TOwmcvz9GHr7o4pz0AsunV5Emt5PehDRhV9OTboO88rIxAqcmrouEMuFihSkgSG9C+vC2vCtxcp9BNUbgvHbjY9x13S7WjY1jzLNubJy7rttVvdG+mvk2d0oZSW9C6gxrl2r4TM652ZgdqplNXBe6gPLpVaSAIL1L+uFNq2w1sNK9RUIKnL0KtbxYUqeAIPlIs2w19JNuPXDWT6wPDsMjgbWxlVDLi7MMUhUKiAoIko+0y1ZDTzWEemLtJLTyYsj2WBb1feuROpUlHyGVrWahqPP5hPg+ZXksi/q+9UgBQfIRUtlqFkI8scYR4vuU5bEs6vvWIwUEyUfaZauHB+ELZ8HnRmpfQ5taOcQTaxwhlRfXZXksi/q+9UgBQfKRZs15EebbD/HEGkeIYwOyPJZFfd96FNAnRionrY7gEDs+G4VeCdVOaB32WR7LIr9vPVBAkOIrSp43tBNrkWV5LCv0vikgSPFpUrQwhVq/H2q7AqA+BCm+iuV5CyHUfp1Q2xUIBQQpvhA7Pqsu1Pr9UNsVCIVFKYcK5Xn7Iu00Sqj9OqG2KxC6QxCpun6kUUKt3w+1XYFQQBCpun6kUULt1wm1XYFQykik6vqRRgm1fj/UdgVCAUGk6vpVthtiv45KTttSykik6qqSRlHJaUcKCCJVV5WyXZWcdqTQKJKWIqcjQkzvpE0lpx0pIIikodPKWkUOFmWhKU46UspIJA3t0hHKXYehKn0lCSggiKShXTpCueswVKWvJAFdooi00k2ap106QrnrcFShryQBBQSRZjr1CTTaMr14e3g3HVEPKo3yyF2rL0PaUMpIpJlu0zzt0hGh5K7VlyEd6C9BpJle0jyt0hGhTJdQhKVGJVcKCCLNpF2iGELuWn0Z0kGilJGZrTKzb5rZi9HXs1tsN2dmT0X/9ibZp0gmQknzpElTP0sHSfsQbgcecfdLgEei75uZcvd/Gv27JuE+RfqvjCWKZQxykqqkKaPtwBXR4z3Ad4DfT/iaIr1Ls4omhDRPmkLpy5BgJQ0IP+vuxwDc/ZiZnddiuxVmdhCYBe5294eabWRmO4AdABesWpWwaVI53ZaKVlHZgpykqmNAMLNvAWua/OiOLvbzc+5+1MwuBr5tZs+4+8uNG7n7bmA3wMb165XYlO6oiqaaNLYiNR0Dgrv/equfmdlPzGxtdHewFhhv8RpHo6+vmNl3gI3AkoAgkoiqaKpHd4WpStqpvBe4MXp8I/CNxg3M7GwzWx49Xg1cBjyfcL8iS6mKpno0T1SqkgaEu4ErzexF4Mroe8xss5ndF23zPuCgmT0NPEqtD0EBQdKnKprq0V1hqhJ1Krv7m8CWJs8fBD4dPf474JeS7Ecklk5VNMo1l4/WOEiVRipLubSqolGuuZzaTSooXdPkdlINyjWXUxkHEOZIdwhSDco1l5fGVqRGdwhSDapAEulIAUGqQRVIIh0pZSTVoHl8RDpSQJDqUK5ZpC2ljEREBFBAEBGRiAKCiIgACggiIhJRp7KINKe5nypHAUFEltLcT5WkgCBSdc3uBLT6XCUpIIhUWas7gZkW22vup1JTp7JIlbW6E2h13tfcT6WmOwSRPITSYdvqit+pzfWkdQYqRQFBJGshddi2W3Gs3peQdtAKJRjKEgoIIlkLqcO23Ypj/Zj7KaRgKEuoD0EkayEt1pP1imNauS5oukMQyVpoC8NnOQtsSMFQltAdgkjWqrxYj1auC5ruEESy1utiPWXojG3XZyG5U0AQyUO3aZqydMZq5bqgKSCIFEFIlUlJaeW6YKkPQaQI1BkrGVBAECkCdcZKBpQykvIqQydsnTpjJQMKCFJOZemErVNnrGRAAUHKqUydsHXqjJU+U0CQcsqyE7ZMqSmpNHUqSzll1QlbT01NLAOs9nXfcO15kYJRQJByymp6CE3WJiWiyxgpp6w6YTU+QEpEAUHKK4tO2NBmLhVJIFHKyMw+bmbPmdm8mW1us93VZvb3ZvaSmd2eZJ8iQanyzKVSOkn7EJ4FrgO+22oDMxsAvghsBd4PfNLM3p9wvyJhyHqBGZE+SpQycvcXAMza5ksvBV5y91eibb8KbAeeT7JvkWBofICURBZ9COuAHy/4/gjwwWYbmtkOYEf07Ttn79jxbJ/blobVwBt5N6KpHYu+C7edi6md6VI701OENgL8Qq//sWNAMLNvAWua/OgOd/9GjH00u31o2uPm7ruB3dF+D7p7y36JUKid6VI706V2pqcIbYRaO3v9vx0Dgrv/eq8vHjkCXLjg+wuAowlfU0REUpbFwLQngEvM7D1mdgZwA7A3g/2KiEgXkpad/oaZHQE+DPwPM3s4ev58M9sP4O6zwC3Aw8ALwF+5+3MxXn53krZlSO1Ml9qZLrUzPUVoIyRop7lrAI2IiGguIxERiSggiIgIEFBA6GIajB+a2TNm9lSS8qpeFWW6DjNbZWbfNLMXo69nt9huLjqWT5lZZp39nY6PmS03s69FP/+ema3Pqm0N7ejUzk+Z2esLjuGnc2jj/WY2bmZNx+1YzZ9Ev8NhM/tA1m2M2tGpnVeY2cSCY7kzhzZeaGaPmtkL0ef83zXZJvfjGbOd3R9Pdw/iH/A+agMqvgNsbrPdD4HVIbcTGABeBi4GzgCeBt6fcTv/CLg9enw7cE+L7U7mcAw7Hh/gd4A/ix7fAHwt0HZ+Crg367Y1tOGfAR8Anm3x823AAWpjgj4EfC/Qdl4B/Pecj+Va4APR4xHgH5q857kfz5jt7Pp4BnOH4O4vuPvf592OTmK28/R0He7+U6A+XUeWtgN7osd7gGsz3n87cY7PwvY/AGyxDnOk9EEI72NH7v5d4HibTbYDX/aax4ExM1ubTeveFaOduXP3Y+7+/ejxJLXKyHUNm+V+PGO2s2vBBIQuOPA/zexQNNVFiJpN15H4zerSz7r7Maj98QDntdhuhZkdNLPHzSyroBHn+JzexmulyxPAOZm0rkkbIq3ex49FqYMHzOzCJj/PWwh/j3F92MyeNrMDZvaLeTYkSlNuBL7X8KOgjmebdkKXxzPT9RBSmAYD4DJ3P2pm5wHfNLMfRFceqclyuo4k2rWzi5f5ueh4Xgx828yecfeX02lhS3GOTybHsIM4bdgHfMXd3zGzm6nd1fxa31vWnRCOZRzfBy5y95Nmtg14CLgkj4aY2VnAXwP/3t3favxxk/+Sy/Hs0M6uj2emAcGTT4OBux+Nvo6b2d9Qu61PNSCk0M5Mputo104z+4mZrXX3Y9Ht7HiL16gfz1fM7DvUrjT6HRDiHJ/6NkfMbBAYJft0Q8d2uvubC779EnBPBu3qViGmj1l4QnP3/Wb2n81stbtnOqGcmQ1RO8n+N3d/sMkmQRzPTu3s5XgWKmVkZivNbKT+GPgX1NZkCE0I03XsBW6MHt8ILLmzMbOzzWx59Hg1cBnZTEse5/gsbP/1wLc96inLUMd2NuSOr6GWyw3NXuC3ouqYDwET9XRiSMxsTb2fyMwupXZ+erP9/0q9DQb8OfCCu/+nFpvlfjzjtLOn45l173ibXvPfoBZ53wF+AjwcPX8+sD96fDG1So+ngeeopXCCa6e/W4nwD9SutvNo5znAI8CL0ddV0fObgfuix78CPBMdz2eAmzJs35LjA9wJXBM9XgF8HXgJ+L/AxTn9XXZq513R3+LTwKPAP86hjV8BjgEz0d/mTcDNwM3Rz43aIlUvR+9zyyq+nNt5y4Jj+TjwKzm08XJq6Z/DwFPRv22hHc+Y7ez6eGrqChERAQqWMhIRkf5RQBAREUABQUREIgoIIiICKCCIiEhEAUFERAAFBBERifx/VodyMidI3LYAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "dt_clf2 = DecisionTreeClassifier(max_depth=2)\n",
    "dt_clf2.fit(X, y)\n",
    "\n",
    "plot_decision_boundary(dt_clf2, axis=[-1.5, 2.5, -1.0, 1.5])\n",
    "plt.scatter(X[y==0, 0], X[y==0, 1])\n",
    "plt.scatter(X[y==1, 0], X[y==1, 1])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "明显过拟合有所改善，除此之外，还有很多其他限制方法可以避免决策树过拟合：\n",
    "\n",
    "* `min_samples_split=10`：每个节点至少有10个数据时才会继续拆分下去\n",
    "* `min_samples_leaf=6`：每个叶子节点至少要有6个样本数据\n",
    "* `max_leaf_nodes=4`：决策树的最大叶子节点个数为4\n",
    "* 其他参数参考 [DecisionTreeClassifier 文档](https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html#sklearn.tree.DecisionTreeClassifier)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面的剪枝策略简单粗暴，但是在很多任务中非常有效，而且训练速度也非常快。不过也由于其简单性，在处理复杂的决策树时可能得到的泛化性能不是很高，可以引入评估泛化性能的方法，在生成决策树的过程中或生成决策树之后评估剪枝是否能提升泛化性能，从而决定是否剪枝，一般分为 **预剪枝**（prepruning）和 **后剪枝**（postpruning）。\n",
    "\n",
    "### 预剪枝\n",
    "\n",
    "预剪枝是指在决策树生成过程中，对每一个节点在划分前先进行估计，若当前节点的划分不能带来泛化性能的提升，则停止划分，并将当前节点标记为叶节点。\n",
    "\n",
    "如何判定决策树的泛化性能是否提升呢？通常将数据集划分为训练集和验证集两部分，使用训练集训练数据，使用验证集进行性能评估。\n",
    "\n",
    "预剪枝本质上是一种贪心算法，可以禁止很多分支展开，不仅降低了过拟合的风险，而且减少了决策树训练时间开销和测试时间开销；不过，它有可能会欠拟合。\n",
    "\n",
    "### 后剪枝\n",
    "\n",
    "后剪枝是指先从训练集生成一颗完整的决策树，然后**自底向上**的对非叶节点进行考察，若将该节点对应的子树替换为叶节点能提升决策树的泛化性能，则将该子树替换为叶节点。\n",
    "\n",
    "一般情况下，后剪枝欠拟合的风险很小，泛化性能优于预剪枝；但后剪枝过程是在生成一颗完整的决策树之后进行的，而且要自底向上对树中所有非叶节点进行考察，因此训练时间开销要大得多。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 参考\n",
    "\n",
    "1. 周志华.《机器学习》\n",
    "2. http://www.devtalking.com/articles/machine-learning-16/"
   ]
  }
 ],
 "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.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
