{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 内容概要\n",
    "- 如何使用K折交叉验证来搜索最优调节参数\n",
    "- 如何让搜索参数的流程更加高效\n",
    "- 如何一次性的搜索多个调节参数\n",
    "- 在进行真正的预测之前，如何对调节参数进行处理\n",
    "- 如何削减该过程的计算代价"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. K折交叉验证回顾\n",
    "**交叉验证的过程**\n",
    "- 选择K的值（一般是10），将数据集分成K等份\n",
    "- 使用其中的K-1份数据作为训练数据，另外一份数据作为测试数据，进行模型的训练\n",
    "- 使用一种度量测度来衡量模型的预测性能\n",
    "\n",
    "**交叉验证的优点**\n",
    "- 交叉验证通过降低模型在一次数据分割中性能表现上的方差来保证模型性能的稳定性\n",
    "- 交叉验证可以用于选择调节参数、比较模型性能差别、选择特征\n",
    "\n",
    "**交叉验证的缺点**\n",
    "- 交叉验证带来一定的计算代价，尤其是当数据集很大的时候，导致计算过程会变得很慢"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. 使用GridSearchCV进行高效调参\n",
    "GridSearchCV根据你给定的模型自动进行交叉验证，通过调节每一个参数来跟踪评分结果，实际上，该过程代替了进行参数搜索时的for循环过程。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sklearn.datasets import load_iris\n",
    "from sklearn.neighbors import KNeighborsClassifier\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "from sklearn.grid_search import GridSearchCV"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# read in the iris data\n",
    "iris = load_iris()\n",
    "\n",
    "# create X (features) and y (response)\n",
    "X = iris.data\n",
    "y = iris.target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]\n"
     ]
    }
   ],
   "source": [
    "# define the parameter values that should be searched\n",
    "k_range = range(1, 31)\n",
    "print k_range"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'n_neighbors': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]}\n"
     ]
    }
   ],
   "source": [
    "# create a parameter grid: map the parameter names to the values that should be searched\n",
    "# 下面是构建parameter grid，其结构是key为参数名称，value是待搜索的数值列表的一个字典结构\n",
    "param_grid = dict(n_neighbors=k_range)\n",
    "print param_grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "knn = KNeighborsClassifier(n_neighbors=5)\n",
    "# instantiate the grid\n",
    "# 这里GridSearchCV的参数形式和cross_val_score的形式差不多，其中param_grid是parameter grid所对应的参数\n",
    "# GridSearchCV中的n_jobs设置为-1时，可以实现并行计算（如果你的电脑支持的情况下）\n",
    "grid = GridSearchCV(knn, param_grid, cv=10, scoring='accuracy')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们可以知道，这里的grid search针对每个参数进行了10次交叉验证，并且一共对30个参数进行相同过程的交叉验证"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "GridSearchCV(cv=10, error_score='raise',\n",
       "       estimator=KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',\n",
       "           metric_params=None, n_neighbors=5, p=2, weights='uniform'),\n",
       "       fit_params={}, iid=True, loss_func=None, n_jobs=1,\n",
       "       param_grid={'n_neighbors': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]},\n",
       "       pre_dispatch='2*n_jobs', refit=True, score_func=None,\n",
       "       scoring='accuracy', verbose=0)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid.fit(X, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[mean: 0.96000, std: 0.05333, params: {'n_neighbors': 1},\n",
       " mean: 0.95333, std: 0.05207, params: {'n_neighbors': 2},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 3},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 4},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 5},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 6},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 7},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 8},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 9},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 10},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 11},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 12},\n",
       " mean: 0.98000, std: 0.03055, params: {'n_neighbors': 13},\n",
       " mean: 0.97333, std: 0.04422, params: {'n_neighbors': 14},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 15},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 16},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 17},\n",
       " mean: 0.98000, std: 0.03055, params: {'n_neighbors': 18},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 19},\n",
       " mean: 0.98000, std: 0.03055, params: {'n_neighbors': 20},\n",
       " mean: 0.96667, std: 0.03333, params: {'n_neighbors': 21},\n",
       " mean: 0.96667, std: 0.03333, params: {'n_neighbors': 22},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 23},\n",
       " mean: 0.96000, std: 0.04422, params: {'n_neighbors': 24},\n",
       " mean: 0.96667, std: 0.03333, params: {'n_neighbors': 25},\n",
       " mean: 0.96000, std: 0.04422, params: {'n_neighbors': 26},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 27},\n",
       " mean: 0.95333, std: 0.04269, params: {'n_neighbors': 28},\n",
       " mean: 0.95333, std: 0.04269, params: {'n_neighbors': 29},\n",
       " mean: 0.95333, std: 0.04269, params: {'n_neighbors': 30}]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# view the complete results (list of named tuples)\n",
    "grid.grid_scores_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'n_neighbors': 1}\n",
      "[ 1.          0.93333333  1.          0.93333333  0.86666667  1.\n",
      "  0.86666667  1.          1.          1.        ]\n",
      "0.96\n"
     ]
    }
   ],
   "source": [
    "# examine the first tuple\n",
    "print grid.grid_scores_[0].parameters\n",
    "print grid.grid_scores_[0].cv_validation_scores\n",
    "print grid.grid_scores_[0].mean_validation_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.95999999999999996, 0.95333333333333337, 0.96666666666666667, 0.96666666666666667, 0.96666666666666667, 0.96666666666666667, 0.96666666666666667, 0.96666666666666667, 0.97333333333333338, 0.96666666666666667, 0.96666666666666667, 0.97333333333333338, 0.97999999999999998, 0.97333333333333338, 0.97333333333333338, 0.97333333333333338, 0.97333333333333338, 0.97999999999999998, 0.97333333333333338, 0.97999999999999998, 0.96666666666666667, 0.96666666666666667, 0.97333333333333338, 0.95999999999999996, 0.96666666666666667, 0.95999999999999996, 0.96666666666666667, 0.95333333333333337, 0.95333333333333337, 0.95333333333333337]\n"
     ]
    }
   ],
   "source": [
    "# create a list of the mean scores only\n",
    "grid_mean_scores = [result.mean_validation_score for result in grid.grid_scores_]\n",
    "print grid_mean_scores"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.text.Text at 0x6e34090>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZEAAAEPCAYAAACDTflkAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xm8nFWd5/HPNyGBLCwJIQtJIAESCAkkIRCSIHoRkaiA\nijNgdAZURunpZmmlu1lcCNrdA92CRnk1i6CNjig9tgi0jUArl+nu3OyX7Athm2wESMxGIOtv/jhP\nkUqlqu5TT9VT2/29X6/7ulXPcuo8qdz61Tm/55wjM8M555xLokutK+Ccc65xeRBxzjmXmAcR55xz\niXkQcc45l5gHEeecc4l5EHHOOZdYqkFE0lRJKyS9JOnmPPv7SHpc0kJJsyWNztr3VUlLJC2W9Kik\nw6PtfSU9J2mVpGclHZPmNTjnnCsstSAiqStwLzAVOB2YJmlUzmG3AQvMbCxwFTAjOncwcD0wwczO\nALoCn43OuQV4zsxGAr+PnjvnnKuBNFsiE4HVZvaame0Bfgl8MueYUcDzAGa2Ehgm6bho32FAT0mH\nAT2BddH2y4BHosePAJ9K7xKcc84Vk2YQGQysyXq+NtqWbSFwOYCkicCJwBAzWwfcDfw/YD2w1cz+\nLTpngJltjB5vBAakU33nnHMdSTOIxJlP5U7gGEntwHVAO7BPUh9Ci2MYcDzQS9LnD3mBMGeLz9vi\nnHM1cliKZa8DhmY9H0pojbzPzLYDX8o8l/Qq8ArwMeBVM9sUbf81MAX4ObBR0kAze0PSIODNfC8u\nyYOLc86VyMxUyvFptkTmASMkDZPUHbgSeDL7AElHR/uQ9GXgBTPbAbwOTJLUQ5KAjwDLotOeBK6O\nHl8N/KZQBcysKX9uv/32mtehma/vt78NDdxrr23O6/v2t8P1PfhgZctdsiSU29JS2+tL+6fW71+a\nP0mkFkTMbC+hi+oZQgB4zMyWS7pW0rXRYacDiyWtAC4GbozOnQP8ClgALIqOfTD6fSdwkaRVwIej\n585VzMyZ8NGPht/NKK3rmzkTunWDrVsrW66rb2l2Z2FmTwNP52x7IOtxG3BqgXOnA9PzbN9MaJk4\nl4q2NrjhBvj852HbNjjqqFrXqHL274dZs+Cxx8I1VlJbG1x8MSxfXtlyXX3zEesNqKWlpdZVSFUt\nr2/vXpgzB84/H846C2bPrvxr1PL6VqyAvn3hwgth/XrYtKlyZc+cCVdcAfv2tVSu0DrU7H9/pfIg\n0oCa/T9xLa9vyRIYMiR80E6ZEr5dV1otr6+tLVxX164wcWJolVTCpk0hKE2dCps3t1Sm0DrV7H9/\npfIg4lyWmTNh8uTwePLk5suLZF/flCmVu75Zs0JQ6tcvtOa2batMua7+eRBxLsvMmeHDFcKH7axZ\nIY/QLHKvr1JBJFOuBEOHwpo1HZ/jmoMHEeeyZLp7APr3h+OOa55E8ebNsG4djBkTnk+aBPPmhZZD\nubL/3TyIdC4eRJyLbNwYPmhPO+3Atmbq0po1C845Bw6L7sns0yd84C9aVPy8juzdC3PnwrnnhudD\nh8LatcXPcc3Dg4hzkba28O28S9ZfRVrJ9VrIbi1kVOL6Fi2CE04IQQnCjQneEuk8PIg4F8lOOmc0\nU0sk3/VVIrne1nZwud6d1bl4EHEukp10zhgzpvLjKWoh0+U0adLB2ysRJHP/3TyIdC4eRJwDdu+G\n9vZwm2q2rl1DX3+lxlPUSvb4l2ynnhqmKdmwIXnZud1kHkQ6Fw8izhECyCmn5J/ipBm6tPJ1ZUHI\n/0yenDwvsmEDbNkCI0ce2JZJrCecz881GA8izpE/6ZzRDMn1YtdXThDJ5EOyb0Y46qjwfMuWZGW6\nxuJBxDkKf1OH0J01d25lxlPUSrHrKye5nptUz/Aurc7Dg4hz5E+qZ/TpE25hLXc8Ra3kG/+SbeJE\nePFF2LWr9LIL/bt5EOk8PIi4Tm/NmpBYP/nkwsc0cpdWvi6nbL17h5xGe3tp5e7aBQsXHnozAngQ\n6Uw8iLhOL9PVoyKLgjZycr1YV1ZGki6t9nYYMSIEoVw+ar3z8CDiOr1iSeeMRm+JdHR9SZLrxboA\nfdR65+FBxHV6cb6pjxwZ7jYqZzxFLRQa/5Ir0xIp5bbcQkl18O6szsSDiOvU3n0Xli6Fs88ufly5\n4ylqJTP+5cgjix83fDjs2xf/g9+seEvEg0jn4UHEdWrz5sHo0dCzZ8fHNmKXVpyuLAj5oFLyPmvW\nhKAzfHj+/T7gsPPwIOI6tThdWRmNmFwv5fpKSa53dDNCr17Qo0fjzznmOuZBxHVqcb+pQ8grLFyY\nbDxFrZRyfaV01xXrysrw5Hrn4EHEdVod9evnSjqeolYy419OOine8RMmwLJlsHNnx8cWS6pneF6k\nc/Ag4jqtV16B7t3Dh11cjdSlFWf8S7YePeCMM0KeqJidO0OwmTCh+HEeRDoHDyKu0yqlFZLRSMn1\nUrqyMuIEyXnzQrDp0aP4cR5EOgcPIq7TKiXpnJH5kG2Eu46SXF+cIBm3XB+13jl4EHGdVpJv6qWO\np6iVuONfcsUJknFbcJ5Y7xw8iLhOaft2WL0axo8v7TypMuuSp23evLC0b0ddTrmGDAnnrF6df79Z\nvKQ6eHdWZ5FqEJE0VdIKSS9JujnP/j6SHpe0UNJsSaOj7adKas/62SrphmjfdElrs/ZNTfMaXHOa\nMwfGjQuJ9VI1QnI9SVdWRrEurdWrQ5AZMqTjcoYMgXXrYP/+ZPVwjSG1ICKpK3AvMBU4HZgmaVTO\nYbcBC8xsLHAVMAPAzFaa2XgzGw9MAHYCj0fnGHBPZr+Z/S6ta3DNK0lSPaMRkutJuuoyigXJUv7d\nevQIqxy++WayerjGkGZLZCKw2sxeM7M9wC+BT+YcMwp4HkLgAIZJOi7nmI8AL5tZdsM45k2LzuVX\nzjf1UsZT1EJm/EsaLZG4XVkZnlxvfmkGkcFA9gf/2mhbtoXA5QCSJgInArkN5c8Cj+Zsuz7qAntY\n0jGVq7LrDPbvh1mzkn/IHnFEvPEUtfLKK3D44aWNf8k2bhy8/DJs23bovlJbcJ5cb35pBpE4N0He\nCRwjqR24DmgH9mV2SuoOXAr8n6xz7gOGA+OADcDdlaqw6xxWrIC+fWHgwORl1HNyvZyuOoBu3eCs\ns2D27IO3b9sWAtTYsfHL8uR68zssxbLXAdnfhYYSWiPvM7PtwJcyzyW9CrySdcjHgPlm9lbWOW9m\nHf8Q8FShCkyfPv39xy0tLbS0tJR4Ca4Zldolk8/kyfCzn1WmPpVWTldWRqZL66KLDmybPTsEl1Ju\nRvAgUt9aW1tpbW0tq4w0g8g8YISkYcB64EpgWvYBko4G3jWz3ZK+DLxgZjuyDpkG/CLnnEFmllka\n6NPA4kIVyA4izmWU+00dwof0n/5pyD/EnVakWtra4ItfLK+MyZPhvvsO3pbk323oUHjxxfLq4tKT\n++X6jjvuKLmM1LqzzGwvoYvqGWAZ8JiZLZd0raRro8NOBxZLWgFcDNyYOV9SL0JS/dc5Rd8laZGk\nhcCHgK+mdQ2uOVWiJdLReIpayYx/GTeuvHImTw4tj+zbc5P8u3livfml2RLBzJ4Gns7Z9kDW4zbg\n1ALnvgP0y7P9qgpX03UimzeH7pUzzii/rEyXz4gR5ZdVKXPmhAGUSca/ZOvfH/r1g+XLw6JdmZsR\nfvrT0srxxHrz8xHrrlOZNSusC3JYBb4+1WNyvRJddRnZ64ssXw7HHReCSykGDw7r0u/b1/GxrjF5\nEHGdSiW6sjLqceR6JZLqGdlBMmm5hx8e7oR7443K1MnVHw8irlOp5Df1cePCLa/5xlPUQrnjX3Ll\nBpGk/25+h1Zz8yDiOo29e2HuXJg0qTLlFRpPUSuZ8S8DBlSmvNGjQ1fUpk3lteA8ud7cPIi4TmPJ\nktBH37dv5cqsp3m0ypkvK5+uXUP+6Le/hfXrw6zASXhyvbl5EHGdRiW7sjLqKbmexvVNngzf+x6c\ne24IKkl4d1Zz8yDiOo1KJtUzJk0KeYh6mO68kkn1jClTwmDBcsr1INLcUh0n4hzA22+HD9lSbw+t\ntJkz4dZbK1tm//7h1teHHoJBgypbdil27QprdyTtciokkz8qp4VT7SCyZw+8/jqcckr1XrMz8yDi\nUved74QPufvvr10dNm4MAw1PO63yZd94IzxVcAa36rnppsqMf8l2zDHw9a/DeeclL6PaifUnnoC/\n//v6ueGh2cmKLaYMSLoHeNjMllanSpUhyTq6Nlcd55wTgsiiRbWrw29+Aw88AE8/3fGxrrL27IFe\nvcL6K5UOcvl87Wvwi1+EO8tcaSRhZiXNBhcnJ7IceFDSHEl/Ek2a6FwsO3eGBZxeeQW2bq1dPdJI\nOrt4unULXX7r11fn9WbODC3P3bur83qdXYdBxMx+ZGbnEZavHUaYMPFRSRekXTnX+ObNC/30Z50V\n5nWqlTSS6i6+auVF3nsPFi8O836tW5f+67mYd2dF66WfRljO9i3CioRfk/RYinVzTSDTAqjlrbC7\nd0N7exjz4GqjWkFk/nwYNSpMiukDHKujwx5KSd8jrC74B+BvzCzzffIuSSvTrJxrfG1t8PnPhzmU\nctenqJYXX4STT4ajjqrN67vqJdczLc633vLbiqslTktkETDWzL6SFUAyzk2hTq5JmB1oiUyeXLvx\nFJ4Pqb1qjVrPvNc+NqV64gSRrUC3zBNJx0j6FICZbUmrYq7xrV4dFm4aMuTAeIrly6tfDw8itVeN\nD3WzAy0RDyLVEyeI3J4dLKLH01OrkWsaucnsWk2d7kn12qvGh/prr4Wlik880efrqqY4QSTfPcMJ\nZ9FxnUluC6AWyfU1a8IYlZNPru7ruoNVI4hk/r9JPnNwNcUJIvMl3SPpZEmnRIn2+WlXzDW+fC2R\nas94m6mDSho+5Spt4MAwY0CaYzey/795d1b1xAki1wN7gMeAXwLvAX+WZqVc49u2DV5+OSzclDFm\nTBhwtmlT9erh+ZD60LVrCCRpjt3Ifq/79w//B997L73Xc0GcwYY7zOxmMzs7+rnVzN6pRuVc45o9\nOwww7N79wLauXcOU4rNmVa8eHkTqR5qtgx07YOXK8H8OoEsXOP5479Kqhg6DiKT+kr4r6V8lPR/9\n/KEalXONq1Ayu5rJ9XffhaVL4eyzq/N6rrg0g8jcuTB2bBiPlOHJ9eqI0531c2AFcBLhrqzXgHnp\nVck1g0ItgGom1+fNC0u89uhRnddzxaUZRPL9f/PkenXECSLHmtlDwG4ze8HMvgh8OOV6uQa2f3/o\nzsrXEjn33PDhvndv+vXwW3vrS5of6vnea0+uV0ecIJK5n+INSZdIOgvok2KdXINbvhyOPTb/IlR9\n+sAJJ1RnWnjPh9SXtLqXsgcZZvMgUh1xgshfSzoGuAn4C+Ah4Kup1so1tI4+vKdMSf9W3+wpV1x9\nSOtDfdUqOPLIkEivxuu5gxUNItHsvSPNbIuZLTazFjM7y8yerFL9XAPqqBupGsn1V14Jd4YNHZru\n67j40vpQL/RlwRPr1VE0iJjZPmBalerimkSclkjaQcRbIfUnM3bj3XcrW26h99oT69URpzvrPyTd\nK+l8SWdJmhDlRZw7xKZNYUDhmDGFjxk5MqxymObypTNnelK93nTpAoMHV37AYaGWb79+YWXNnTsr\n+3ruYHGCyHhgNPBt4G7gu9HvDkmaKmmFpJck3Zxnfx9Jj0taKGm2pNHR9lMltWf9bJV0Q7Svr6Tn\nJK2S9GyUr3F1YtassPhT1yKzq3Xpkv4UKG1t3hKpR5XuYtqyBV5/Hc4889B9kndpVUOcEestZnZB\n7k9H50X5lHuBqcDpwDRJo3IOuw1YYGZjCcvvzohec6WZjTez8cAEYCfweHTOLcBzZjYS+H303NWJ\nuN1IaSbXt28P09CPH59O+S65SudFZs+GCRPCOu7VeD13qDgrG94OGGE2X8tsN7Nvd3DqRGC1mb0W\nlfNL4JNA9ooSo4A7o/JWShom6TgzeyvrmI8AL5tZ5r/CZcCHosePAK14IKkbbW3wl3/Z8XGTJ8M3\nv5lOHebMCXN2ZU+54upDpT/UO/rS4i2R9MXpznon+tkB7Ac+DgyLcd5gIPvtWxtty7YQuBxA0kTg\nRGBIzjGfBR7Nej7AzDZGjzcCA2LUxVXB3r1h+olJkzo+duJEWLgwTNNeaZ5Ur1+VDiIddVt6cj19\nHbZEzOy72c8l/T3wbIyyreNDuBOYIakdWAy0A/uyXqs7YX33Q/IpUd1MUsHXmT59+vuPW1paaGlp\niVEll9SiReGPtk+Moai9e8OIEdDeHi/olGLmTPjKVypbpquMoUPh6acrU9a+faE7q9j/n6FDYcGC\nyrxeM2ptbaW1tbWsMjoMInn04tAWRT7rgOy79IcSWiPvM7PtwJcyzyW9CrySdcjHgPk53VsbJQ00\nszckDQLeLFSB7CDi0ldqMjtzq28lg8j+/SG5/5OfVK5MVzmV7F5aujRML9+vX+Fjhg6FJ56ozOs1\no9wv13fccUfJZcSZxXdx1s9SYCVRArwD84ARUZ6jO3AlcNAgRUlHR/uQ9GXgBTPbkXXINOAXOeU+\nCVwdPb4a+E2MurgqKLUbKY3k+ooVoSU0cGBly3WVUcnurDhzo3liPX1xWiKXZj3eC2w0sz0dnWRm\neyVdBzxDWE73YTNbLunaaP8DhLu2/jHqkloCXJM5X1IvQlL9yzlF3wn8k6RrCDMKXxHjGlwVtLXB\nN74R//jJk+Gv/ipMUVKplQf91t761q9fGGz4zjvQq1d5Zc2cCeedV/wYT6ynT2bFUxeSJgHLzGxb\n9PwoYJSZza5C/RKTZB1dm6ucDRvCtOtvvx3GgcRhBoMGhbupTjihMvW45ppwy+ef/mllynOVN2IE\nPPUUnHZaeeWMHAm//nXxga1mIf+2YQMcdVR5r9cZSMLMSvpKF+fP/X7CnVkZ70TbnHtfW1vIbcQN\nIBBaH5WeR8tHqte/Stwx9dZb8OabcPrpxY+T/A6ttMX6kzez/VmP9xG6p5x7X9JupErOo7V5c/iw\nOOOMypTn0lGJLqa2trA2TZwvLZ4XSVecIPKqpBskdZPUXdKNHHwHlXOJx2ZUMrk+axaccw4cluSe\nQ1c1lfhQL2XBMQ8i6YoTRP4EOI9wy+5aYBLgd+G79+3aBS++GAYQlmrCBFi2rDKT5HlSvTFU4kO9\nlC8tnlxPV5y5szaa2ZVm1j/6mWZmBcdmuM6nvT0kOXv3Lv3cI44I3U/z5pVfDx+p3hjKDSJ79oQB\nhOeeG//1PCeSnjjjRH6aPVNuNPPuj9Otlmsk5SazK5Fc37s33OVV6dHvrvLK/VBfuBCGDYOjj47/\net4SSU+c7qwzzWxL5omZ/RHw9UTc+8rtRqpEcn3JktBt0bdveeW49JXbvVRqi9ODSLriBBFJ6pv1\npC9+d5aLVGIt88zaIuUM6/FbextHnz6h5bhtW7LzS0mqw4Eg4sPG0hEniNwNtEn6jqS/BtqAv0+3\nWq5RrFkTPhCGD09expAh0KNHWAMkKU+qN47M2I2krYNSv7QcdVS4FXjLlo6PdaWLk1j/KWG69jeB\nN4BPR9uce/8PutxpS8q91deT6o0laRBZty5MmTJiROmv58n1dMQdbLjUzH4I/A74TDQRo3MV60Yq\nJ7m+cWMYaFjuNBquepJ+qGe6skr90uJ5kfTEuTtrsKSvSZpLmCSxK2GhKOcq1o1UTkskyZQrrraS\nJteT/n/zIJKegn92kq6V1EpYfvZYwgy7G8xsupktrk71XD17550wUHDChPLLGjcOXn45WbLVk+qN\nJ+mHetL32oNIeop9d7s32v85M/u6mS2qUp1cg5g3L8yg2qNH+WV16wZnnRVWqiuV50MaT5IP9ffe\nC6tnnnNO6a/no9bTUyyIDCIsCPVdSauiO7O6VadarhFU+o6oJF1au3eHEfNJplxxtZMkiCxYAKNG\nJVuHxBPr6SkYRMzsbTO7z8w+BFwIbCEsTbtC0t9WrYaublW6GylJcr29HU45xdeKaDSZD/VSxm6U\n8//Nu7PSE/furDVm9l0zmwBcBryXbrVcvTOrfEtk8uTQnbV/f8fHZvj4kMaUZOxGOe91kqDl4in5\nfhYzW2Vm306jMq5xrF4dJk8cMqRyZfbvD8ceC8uXxz/Hk+qNq5TWQWZmhKTvda9e4f/rpk3JzneF\n+U2RLpG0ktmlzqPlSfXGVUoQee21MDbkxBOTv54n19Phy/ekpLUV7r671rVIz4oVcN11lS93yhS4\n80548smOj923LyTWTz658vVw6TvhBPj61+H+GIttv/VW+TMjZLq0xo9PXsYtt8Dtt1fmjsRsjz4a\nRuEnufOs1goGEUkTAAMU/T6ImS1IsV4N73e/C10zn/lMrWuSnpaWypf53/97+MYYt+96yJDyp1xx\ntfGtb4UbI+IaO7a81ys3ub5+Pdx1F3z84/DBD5ZXl1w//CFcemmTBRHCxIsG9AAmAJlxImcC8wDv\niS5izRqYOjX8x3Dx9eoFl1xS61q4ahgypLI5tY6UG0Qyt5/PnFnZIPLeezB/fhhw24iK3eLbYmYX\nAOuBs8xsQnR31vhomyti7drq/oE454qrRBAZN668iULzWbAgrNbYqONY4iTWT8ue5sTMlgCj0qtS\nc1izJvyndc7Vh0oshnXTTeF3JW8VnjkTzjuvcZP+cYLIIkkPSWqRdIGkHwEL065YI9u/P0xZ7S0R\n5+pHOaPWd+0Ky/J+6lPlr32Ta+ZMuOKK5g4iXwSWATcCN0SPv5hmpRrdm2+G9Z+POKLWNXHOZQwZ\nEr7clTKYNWPBAjj1VOjd+8BKnJWQGbR76aWwc2f4aTRxFqV6F7gfuNXMPm1m3zMzH7FehHdlOVd/\nevSAI48MtwuXKns8UqljmYrJjH8ZNgwGD27M1kic9UQuA9oJC1IhabykGHfxd16eVHeuPiVNrmdP\nuVLuKpz5ys0sGdyIyfU43VnTgXOBPwKYWTtwUpzCJU2NJmx8SdLNefb3kfS4pIWSZksanbXvGEm/\nkrRc0jJJ50bbp0taK6k9+pkapy7V5C0R5+pTkuS6Gfznfx6YcmXs2ORr3+TKnsqlUSeJjBNE9phZ\n7jRpHfYqSupKWJNkKnA6ME1S7l1dtwELzGwscBUwI2vfDOBfzWwUYWzKimi7AfeY2fjo53cxrqGq\nPIg4V5+SfNt//fXwe9iw8Lt79+Rr3+TK7iZr5iCyVNLngcMkjZD0QyBOj+BEYLWZvWZme4BfAp/M\nOWYU8DyAma0Ehkk6TtLRwPlm9uNo314z25p1Xl2PUfYg4lx9SvJBnW9d90ok13fsgJUrQ0BKWrd6\nECeIXA+MBnYRFqnaBvx5jPMGA9n/JGujbdkWApcDSJoInAgMAYYDb0n6iaQFkn4kqWd2naIusIcl\nHROjLlXlQcS5+pTkgzrfJJ+VSK7PnRu6xg4/PDwfMqQxcyJxJmD8uJndRuh6AkDSfwX+TwfnxRmO\ncycwQ1I7sJiQwN8HdAfOAq4zs7mSvg/cAnwLuA/ITEX/HcL0LNfkK3z69OnvP25paaEljcme8vDE\nunP1KWkQmTbt4G2TJ8MXvhBuF+6ScC703PVRatESaW1tpbW1tawyZB0MvZTUbmbjO9qW57xJwHQz\nmxo9vxXYb2Z3FTnnVeAMoDfQZmbDo+0fAG4xs0tyjh8GPGVmZ+Qpyzq6tjTs2wc9e8L27aHv1DlX\nP155BS644ECeoyPvvBPWudm06dBxX6ecAk88AaNH5z+3I5dcAl/84oFJWjdvhpNOKm2hrkqThJmV\nlC4oNovvx4CPA4Ml/YADeYgjgT0xyp4HjIg+6NcDVwIHxfMo9/Gume2W9GXgBTPbAeyQtEbSSDNb\nBXwEWBqdM8jMNkRFfJrQgqkbb7wBfft6AHGuHg0eDBs2hC97Xbt2fPzcuXDmmfkHDme6tJIEkcwg\nwwcfPLCtT58wh9b27WE8S6Mo1hBbD8wnLIU7P+vnSeDijgo2s73AdcAzhFHuj5nZcknXSro2Oux0\nYLGkFVGZN2YVcT3wc0kLCXdnZdZ1v0vSomj7h4CvxrrSKvF8iHP16/DDw5e8jRvjHZ9JqudTTnJ9\n1aoQKI4//sC2zFiRRkuuF2yJmNlCYKGkR81sd5LCzexp4OmcbQ9kPW4DTi3y+ofMrm9mVyWpS7V4\nEHGuvmU+qLM/wAuZOROuvjr/vilTYMaM/PvilJtvRc5Mcv3005OVWwtxUkLDokF/yyS9Gv28knrN\nGpQn1Z2rb3G/7We6nAotvzxmTOgaS7Jue6FyG7ElEieI/IQwd9ZeoAV4BPh5inVqaN4Sca6+xf2g\nfumlsEhaoRZL165hJcJZs0qvQ/ZI9SR1qydxgkgPM/s3wp1cr5vZdOAT6VarcXkQca6+xR2PUajL\nKVuS8SJbtoS7w84889B9zRpE3oumMFkt6TpJlwO9Uq5Xw/Ig4lx9i/tBXSypnpEkuT57NkyYAN26\nJa9bPYkTRP4c6ElYS+Rs4L8BBVJNzoOIc/Ut7gd1nJbIpEnhNuC9e+O/frFyG3HUepz1ROaY2XYz\nW2NmXzCzy80sQS9g89uzJ6xVMGhQrWvinCskThDZuhVefTVMS1JMnz5wwgmwuITRasWS9Zm61WCc\ndGLFBhs+lfXUODDY0ADM7LIU69WQNmwIo1sPizOZjHOuJgYNCquP7t1b+G+1WJdTrsmTQ+tifNE5\nPIJ9+0LZkybl33/00WG8yNatcEzdzQqYX7GWyN3RzyvAu8CDwI+Ad6JtLod3ZTlX/7p1g+OOC1/6\nConTlZVRSnJ96VIYOBD69St8TKPlRQoGETNrNbNW4ANmdqWZPWVmT5rZNOD8qtWwgXgQca4xdPRB\nHSepnlFKcj1OuU0TRLL0lHRy5omkkwiJdpfDg4hzjaHYB/W+fWHsR9wgcuqp4bbdYi2bjDgtnEZL\nrscJIl8Fnpf0gqQXCItIxVlPpNPx0erONYZiQWTZMhgwIHR5xdGlS/zWSJwg0nQtkWj52ZGEyRFv\nAEaa2TNpV6wReUvEucZQ7IO6lK6sjDhB5K23wk9H82I1TRCRdGH0+zOEKeFPBk4BPhENOHQ5PIg4\n1xiKdRk/NWgAAAAWUElEQVSVklTPiJNcb2uDc8/teBGrRgsixW5G/SDwe+BS8q9S+OtUatTAPIg4\n1xg6aol87WullTdxIrz4IuzadWC523zlxmnhNE0QMbPbo99fqFptGtiuXWFlsgEDal0T51xHCn1Q\nv/12WFiu1IWmeveGkSOhvb3wGJCZM+HrX++4rEwrySyMGal3xQYb3pRnc2bQoZnZPanVqgGtXx8G\nMcVZLc05V1sDB4Yvfbt3H7wKaabLKcnfcaZLK18Q2bMH5s8PZXekd+/Qmtm8GY49tvR6VFux3rkj\nCWudZ/8cmfXjsnhXlnONo2vXEEjWrTt4e5Kkekax5PrChTB8eBiRHkcjdWkV686aXsV6NDwPIs41\nlky30fDhB7bNnAm33pqsvClT4Oab83dDlZqszwSRceOS1aWaOpzlSVIP4BrCeug9ODB31pfSrVpj\n8SDiXGPJ/bZfSpdTPsOHh/m41qwJkzJma2uDiy9OXrd6Fmew4c+AAcBUoBUYCuxIsU4NyYOIc40l\n94N60SI48cTkEx9KhW/1LbUl0kij1uMEkVPM7JvADjN7hDBmJGGsbl4+Wt25xpIbRJKMD8mVL4is\nWwfvvAMjRiSvWz2LE0R2R7+3SjoDOAaIOSFA5+EtEecaS+4HdTlJ9Yx8yfVMuaXcrttsQeRHkvoC\n3wCeBJYBf5dqrRqQBxHnGktul1ElWiITJoS5t3buLK/cpggikpZJ+gbwBzPbbGYvmNlwMzvOzO6v\nYh3r3rvvwvbt8Sdsc87VXvYH9fr14W945MjyyuzRA8aMgXnzDmxL0sIZMiR0g+3fX159qqFYS+Rz\nhLEhz0qaK+mrko6vUr0aytq1MHhwx3PiOOfqR//+sG0bvPdesi6nQrLzIu+9FxL255xTWhk9eoRB\nh2+/XX590lZsUaoXzewWMzsZuB44EZgl6XlJX6laDRuAJ9WdazxdusDxx4e/30p0ZWVkB5H582HU\nKOjVq/RyGqVLK9Z3ZzObRVhX5GqgD3BvmpVqNJ4Pca4xZT6oK5FUz8gk183KK7dpgoikiZLuAV4H\npgP3A96tlcWDiHONacgQePnlMC1JqV1Oxcrs0QNWry6vhdPwQUTS30p6GfgHYB0wxcw+ZGb3m1ms\nnjpJUyWtkPSSpJvz7O8j6XFJCyXNljQ6a98xkn4laXmU5J8Ube8r6TlJqyQ9Kynh0KDK8SDiXGMa\nOhSeeCIscdu7d+XKnTw5BJDO3hLZBUw1s7PN7G4zWyvpkrgFS+pK6PaaSpgyZZqkUTmH3QYsMLOx\nwFXAjKx9M4B/NbNRwJnA8mj7LcBzZjaSsN7JLXHrlBYPIs41pqFD4ZlnKpcPyZgyBR59NCTqTzwx\nWRmNMmq9WGL9DjN7KWfzd0ooeyKw2sxeM7M9wC+BT+YcM4qwZjtmthIYJuk4SUcD55vZj6N9e81s\na3TOZcAj0eNHgE+VUKdUeGLducY0dGiYMyuNIPLss+F30ju+mqElUq7BQPY/wdpoW7aFwOUQci+E\nO8CGAMOBtyT9RNICST+S1DM6Z4CZbYwebyTM65XY5s1hQalyeEvEucaU+butVFI9Y+xYOOKI8spt\nlCDS4Sy+Oa4t4dh8S+rmuhOYIakdWAy0A/uA7sBZwHVmNlfS9wndVt866AXMTFLB15k+ffr7j1ta\nWmhpaTnkmE99Cr75Tbjoohi1zeOdd8K94I2weIxz7mAnnQQf/SgMG1bZcrt3hyuvDGUnNXgwbNgA\n+/alt9hda2srra2tZZUhs+Kf9ZKuAH5nZtskfZPw4f4dM1vQwXmTgOlmNjV6fiuw38zuKnLOq8AZ\nhEGObWY2PNp+PnCzmV0iaQXQYmZvSBoEPG9mp+Upyzq6Ngjz//fsCbff3uGhea1YAZddBqtWJTvf\nOecKGTgQFiwI41mqQRJmVlIHXJzurG9GAeQDwIXAw8B9Mc6bB4yQNExSd+BKwtxb2RU+OtqHpC8D\nL5jZDjN7A1gjKTMJwYXA0ujxk4TxKkS/fxOjLgVNmVJ4NbI4vCvLOZeWRkiuxwki+6LflwA/MrN/\nIXQ3FWVme4HrgGcIkzY+ZmbLJV0rKdMtdjqwOGpdXAzcmFXE9cDPJS0k3J31t9H2O4GLJK0CPhw9\nT2zyZJg1K/kcNZ5Ud86lpRHyInFyIuskPQhcBNwp6Qjij3R/Gng6Z9sDWY/bgFMLnLsQOGT4j5lt\nBj4S5/Xj6N8f+vWD5cth9OiOj8/lLRHnXFoaIYjECQZXEFoTHzWzLYRpT/4y1VpVWaHVyOLwIOKc\nS0uzBJGBwG/N7CVJFxCCypx0q1VdmdGlSXgQcc6lpVmCyK+BvZJOAR4gjON4NNVaVVk5yXUPIs65\ntDRLYn1/lCS/HPihmf0lMCjdalXXmDFhUZpNm0o/1xPrzrm0NEtLZLekzxHmtvqXaFu39KpUfV27\nwsSJ4S6tUmzbFgYCHVPzKSCdc83o+ONh40bYu7fWNSksThD5EjAZ+Bsze1XSScDP0q1W9SVJrme6\nsiqxGppzzuXq1i0su71hQ61rUliHQcTMlgJ/ASyRNAZYU2zUeaNKklz3fIhzLm313qXV4TgRSS2E\n2XJfjzadIOlqM3shzYpV26RJMG9eaDYeFnNGMQ8izrm01XtyPU531j2EMSIfNLMPAh8Fvpdutaqv\nTx844QRYtCj+OZ5Ud86lrd5bInGCyGHRWh8AmNkqSp/9tyFk1kaOy1sizrm0NUMQmS/pIUktki6Q\n9BBhcsWmU2py3YOIcy5tzRBE/oSwNO0NhEkRlwL/M81K1Yq3RJxz9abeg0jR9UQkHQYsybdeR72L\nu55Itv37w2SMS5fCoA6GU5pB797wxhtw5JFlVNQ554pYuzaMY1u/Pv3Xqvh6ItFI9ZWSEi4131i6\ndInfGtmyJdzF5QHEOZemQYPg7bdh9+5a1yS/ON1ZfYGlkv4g6ano58kOz2pQcYOId2U556qha9ew\nwmE1WiJJxLnL6ps5z0vrI2owU6aENdc74kHEOVctmbxIpdeCr4SCQUTSCGCAmbXmbP8AUMeD8Msz\ncSK8+CLs2gWHH174OA8izrlqqefkerHurO8D2/Js3xbta0q9e8PIkdDeXvw4DyLOuWqp51HrxYLI\nADM7ZPx2tG14elWqvTjjRXy0unOuWhq1JVJsgvMjKl2RehInue4tEedctTRqEJkn6Su5GyV9GZif\nXpVqL9MSKTbMxIOIc65a6jmIFBxsKGkg8DiwmwNBYwJwOPBpM6vr5HqSwYYZZuGWurlzw6SM+fb3\n7BlWQuzZs8yKOudcB954A848E958M93XSTLYsODdWWb2hqQpwAXAGMKtvf9iZn8or5r1TzrQGskX\nRN5+OwQPDyDOuWro3x+2boX33oMj6iyZ0NGIdTOzP5jZD8zsh50hgGQUS657Ut05V01duoSlctet\nq3VNDhVnxHqnVCy57vkQ51y11WtexINIARMmwLJlsHPnofs8iDjnqs2DSIPp0QPGjAlL5ubyIOKc\nqzYPIg2oUF7Eg4hzrtqGDq3PUeupBhFJUyWtkPSSpJvz7O8j6XFJCyXNljQ6a99rkhZJapc0J2v7\ndElro+3tkqamVf9CQcQT6865ahsypJO1RCR1Be4FpgKnA9Mkjco57DZggZmNBa4CZmTtM6DFzMab\n2cSc7fdE28eb2e/SuoZMcj13uIm3RJxz1dYZu7MmAqvN7DUz2wP8EvhkzjGjgOcBzGwlMEzScVn7\nCw16KWkwTFJDhoTcyOrVB7bt3x9us/OWiHOumjpjEBkMZF/y2mhbtoXA5QCSJgInApmPZwP+TdK8\naKqVbNdHXWAPSyo2x1fZcm/1ffNNOPro+hvw45xrbv36hbtF890xWktpBpE4c47cCRwjqR24DmgH\n9kX7PmBm44GPAX8m6fxo+32EWYTHEdY1ubuitc6RmxfxriznXC1I9TklfJyVDZNaB2R/3A4ltEbe\nZ2bbgS9lnkt6FXgl2rc++v2WpMcJ3WP/bmZvZh3/EPBUoQpMnz79/cctLS20tLSUfBFTpsDDDx94\n7kl151ytZJLrI0dWprzW1lZaW1vLKqPgBIzlknQYsBK4EFgPzAGmmdnyrGOOBt41s91Rl9V5ZvYF\nST2Brma2XVIv4FngDjN7VtKgzOSPkr4KnGNmn8vz+oknYMy2ezf07RvWNz7qKPjBD2DVKrj33rKL\nds65klx1FXz4w/CFL6RTfkUnYCyXme2VdB3wDNAVeNjMlku6Ntr/AOGurX+UZMAS4Jro9AHA45Iy\ndfy5mT0b7btL0jhCd9mrwLVpXQNA9+5w1lkwezZcdJF3Zznnaqcek+tpdmdhZk8DT+dseyDrcRtw\nap7zXiXkPPKVeVWFq9mhTHI9E0TGj692DZxzLgSRBQtqXYuD+Yj1GLKT694Scc7VSj2OWvcgEsPk\nyTBrVhgj4ol151yt1OOodQ8iMfTvH+7RXrIkrDA2OHe0i3POVUE95kQ8iMQ0ZQo8/ni4U6t791rX\nxjnXGfXpA3v2wPbtta7JAR5EYpo8GR57zPMhzrnakeqvNeJBJKYpU2D5cg8izrnaqrfkugeRmMaM\ngd69PanunKutekuupzpOpJl07QrnnustEedcbQ0dCo8+Wj+BxINICb7zHRg0qNa1cM51Zp/7HHSp\noz6k1ObOqrVKzZ3lnHOdRZK5s+oonjnnnGs0HkScc84l5kHEOedcYh5EnHPOJeZBxDnnXGIeRJxz\nziXmQcQ551xiHkScc84l5kHEOedcYh5EnHPOJeZBxDnnXGIeRJxzziXmQcQ551xiHkScc84l5kHE\nOedcYh5EnHPOJeZBxDnnXGIeRJxzziWWahCRNFXSCkkvSbo5z/4+kh6XtFDSbEmjs/a9JmmRpHZJ\nc7K295X0nKRVkp6VdEya1+Ccc66w1IKIpK7AvcBU4HRgmqRROYfdBiwws7HAVcCMrH0GtJjZeDOb\nmLX9FuA5MxsJ/D563qm0trbWugqp8utrbH59nUuaLZGJwGoze83M9gC/BD6Zc8wo4HkAM1sJDJN0\nXNb+fAvGXwY8Ej1+BPhURWvdAJr9P7FfX2Pz6+tc0gwig4E1Wc/XRtuyLQQuB5A0ETgRGBLtM+Df\nJM2T9OWscwaY2cbo8UZgQKUr7pxzLp7DUizbYhxzJzBDUjuwGGgH9kX7PmBm66OWyXOSVpjZvx/0\nAmYmKc7rOOecS4HM0vkMljQJmG5mU6PntwL7zeyuIue8CpxhZjtytt8ObDezeyStIORK3pA0CHje\nzE7LU5YHF+ecK5GZ5UsjFJRmS2QeMELSMGA9cCUwLfsASUcD75rZ7qjL6gUz2yGpJ9DVzLZL6gV8\nFLgjOu1J4Grgruj3b/K9eKn/EM4550qXWhAxs72SrgOeAboCD5vZcknXRvsfINy19Y9Rq2EJcE10\n+gDgcUmZOv7czJ6N9t0J/JOka4DXgCvSugbnnHPFpdad5Zxzrvk13Yj1jgY4NrpCgzAblaQfS9oo\naXHWtqYZUFrg+qZLWhu9h+2SptayjklJGirpeUlLJS2RdEO0vSnevyLX1yzv3xHRIO8Xo+ubHm0v\n6f1rqpZINMBxJfARYB0wF5hmZstrWrEKim4+mGBmm2tdl0qQdD6wA/ipmZ0Rbfs74G0z+7voi0Af\nM2vIQaUFru/9G0VqWrkySRoIDDSzFyX1BuYTxm19kSZ4/4pc3xU0wfsHIKmnme2UdBjwH8CNwGco\n4f1rtpZInAGOzaBpbhqIbtv+Y87mphlQWuD6oAneQzN7w8xejB7vAJYTxoI1xftX5PqgCd4/ADPb\nGT3sDnQjDM0o6f1rtiASZ4Bjoys0CLOZdIYBpddHc8Y93KjdPdmiuzDHA7Npwvcv6/pmRZua4v2T\n1EXSi4T36Vkzm0OJ71+zBZHm6Zsr7DwzGw98DPizqLukaVnob2229/U+YDgwDtgA3F3b6pQn6ur5\nZ+BGM9ueva8Z3r/o+n5FuL4dNNH7Z2b7zWwcYaaQcyWNydnf4fvXbEFkHTA06/lQQmukaZjZhuj3\nW8DjhC68ZrMx6o8mGlD6Zo3rU1Fm9qZFgIdo4PdQUjdCAPmZmWXGbDXN+5d1ff87c33N9P5lmNlW\nwjyGF1Pi+9dsQeT9AY6SuhMGOD5Z4zpVjKSeko6MHmcGYS4uflZDygwohSIDShtV9IeZ8Wka9D1U\nGMj1MLDMzL6ftasp3r9C19dE71+/TFecpB7ARYS8T0nvX1PdnQUg6WPA9zkwwPF/1bhKFSNpOKH1\nAQcGYTb09Un6BfAhoB+h//VbwBPAPwEnEA0oNbMttapjOfJc3+1AC6ErxIBXgWuz+qAbhqQPAP8X\nWMSBLo9bgTk0wftX4PpuI8y80Qzv3xmExHlXQoPiMTP7a0l9KeH9a7og4pxzrnqarTvLOedcFXkQ\ncc45l5gHEeecc4l5EHHOOZeYBxHnnHOJeRBxzjmXmAcR19Ak/UHSR3O2/bmkfyhyTqukCSnX6xfR\n3Eo35myfLumm6PER0ZTb38pz/n+VtEzS78uow46sxx+XtFLSCVEd3pF0XIFj90v6btbzv4hmHnbu\nEB5EXKP7BfDZnG1XAo8WOSfV+ZyiKSPONrOxZjYj32tHMyr8MzDXzL6dp5hrgP9hZhfGfM18q5Ra\ntO9CYAYw1cz+X7TvbeCm3GMju4FPSzo2zz7nDuJBxDW6fwY+kfkQjWZbPd7M/kPSfZLmZi+4kyvn\nG/h/kfST6PFxkn4laU70MyXPuUdI+onCImELJLVEu54FBkcLFn0gz8t2IyxTsNLMbstT7reA84Af\nS7pL0uH5XkfSFyQ9GbVWnitwfR8EHgQ+YWavRpsN+DFwZYEZaPdE53w1X5nOZfMg4hpatDjXHODj\n0abPAo9Fj28zs3OAscCHomkeDimiwOMZwPfMbCLwXwgT7eX6M2CfmZ1JmArjkaiFcSnwspmNN7P/\nyDlHwF8Bu8zsawWu6duEeeA+Z2Y3A9fleZ3Do8PHA58xswvyFHUEYZqcT5rZqpx9OwiB5M/z1QH4\nB+Dzko4qsN85wIOIaw7ZXVpXRs8hfNOeDywARgOjSijzI8C9ktoJc3kdKalnzjHnAf8bwMxWAq8D\nIym+YJERVpCbImlEzLoUeh0Dnisyr9Fu4D+B/1GgHj8Aro6mOj94Z5jS/afADTHr6DopDyKuGTwJ\nXChpPNDTzNqjySpvAj5sZmOB3xK+mefKbn30yHos4NyoNTHezIZmrQJHznGl+r+ErqKnM1Nux1Do\ndd4pcs5+wlKuEyXdmlteNP33o4SWTj7fJ+RmesWso+uEPIi4hhctFPQ88BMOJNSPInzAbpM0gLCI\nVz4bJZ0mqQthWu9MUHmWrG/hksblOfffgc9H+0cSZj1dGbPOvwa+C/xO0tEdHJ7vdVYQI4CZ2XvA\nJwhdU1/Kc8g9wLWEWaFzz/0jYTbXa/DkuivAg4hrFr8Azoh+Y2YLgXbCh+3PCV1I+dwC/Auh22d9\n1vYbgLOj23SXAl/Jc+4/AF0kLSIkyq82sz3RvmIfuhbV8X5CzuLJrBxHPoVep6O7zDKv80dgKvAN\nSZfm7NsE/JqwxvZB50XuJkxj71xePhW8c865xLwl4pxzLjEPIs455xLzIOKccy4xDyLOOecS8yDi\nnHMuMQ8izjnnEvMg4pxzLjEPIs455xL7/0Z6IwVDOiWpAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x6e19eb0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# plot the results\n",
    "plt.plot(k_range, grid_mean_scores)\n",
    "plt.xlabel('Value of K for KNN')\n",
    "plt.ylabel('Cross-Validated Accuracy')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.98\n",
      "{'n_neighbors': 13}\n",
      "KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',\n",
      "           metric_params=None, n_neighbors=13, p=2, weights='uniform')\n"
     ]
    }
   ],
   "source": [
    "# examine the best model\n",
    "print grid.best_score_\n",
    "print grid.best_params_\n",
    "print grid.best_estimator_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. 同时对多个参数进行搜索\n",
    "这里我们使用knn的两个参数，分别是n_neighbors和weights，其中weights参数默认是uniform，该参数将所有数据看成等同的，而另一值是distance，它将近邻的数据赋予更高的权重，而较远的数据赋予较低权重。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# define the parameter values that should be searched\n",
    "k_range = range(1, 31)\n",
    "weight_options = ['uniform', 'distance']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'n_neighbors': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30], 'weights': ['uniform', 'distance']}\n"
     ]
    }
   ],
   "source": [
    "# create a parameter grid: map the parameter names to the values that should be searched\n",
    "param_grid = dict(n_neighbors=k_range, weights=weight_options)\n",
    "print param_grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "GridSearchCV(cv=10, error_score='raise',\n",
       "       estimator=KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',\n",
       "           metric_params=None, n_neighbors=5, p=2, weights='uniform'),\n",
       "       fit_params={}, iid=True, loss_func=None, n_jobs=1,\n",
       "       param_grid={'n_neighbors': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30], 'weights': ['uniform', 'distance']},\n",
       "       pre_dispatch='2*n_jobs', refit=True, score_func=None,\n",
       "       scoring='accuracy', verbose=0)"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# instantiate and fit the grid\n",
    "grid = GridSearchCV(knn, param_grid, cv=10, scoring='accuracy')\n",
    "grid.fit(X, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[mean: 0.96000, std: 0.05333, params: {'n_neighbors': 1, 'weights': 'uniform'},\n",
       " mean: 0.96000, std: 0.05333, params: {'n_neighbors': 1, 'weights': 'distance'},\n",
       " mean: 0.95333, std: 0.05207, params: {'n_neighbors': 2, 'weights': 'uniform'},\n",
       " mean: 0.96000, std: 0.05333, params: {'n_neighbors': 2, 'weights': 'distance'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 3, 'weights': 'uniform'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 3, 'weights': 'distance'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 4, 'weights': 'uniform'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 4, 'weights': 'distance'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 5, 'weights': 'uniform'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 5, 'weights': 'distance'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 6, 'weights': 'uniform'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 6, 'weights': 'distance'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 7, 'weights': 'uniform'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 7, 'weights': 'distance'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 8, 'weights': 'uniform'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 8, 'weights': 'distance'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 9, 'weights': 'uniform'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 9, 'weights': 'distance'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 10, 'weights': 'uniform'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 10, 'weights': 'distance'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 11, 'weights': 'uniform'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 11, 'weights': 'distance'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 12, 'weights': 'uniform'},\n",
       " mean: 0.97333, std: 0.04422, params: {'n_neighbors': 12, 'weights': 'distance'},\n",
       " mean: 0.98000, std: 0.03055, params: {'n_neighbors': 13, 'weights': 'uniform'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 13, 'weights': 'distance'},\n",
       " mean: 0.97333, std: 0.04422, params: {'n_neighbors': 14, 'weights': 'uniform'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 14, 'weights': 'distance'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 15, 'weights': 'uniform'},\n",
       " mean: 0.98000, std: 0.03055, params: {'n_neighbors': 15, 'weights': 'distance'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 16, 'weights': 'uniform'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 16, 'weights': 'distance'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 17, 'weights': 'uniform'},\n",
       " mean: 0.98000, std: 0.03055, params: {'n_neighbors': 17, 'weights': 'distance'},\n",
       " mean: 0.98000, std: 0.03055, params: {'n_neighbors': 18, 'weights': 'uniform'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 18, 'weights': 'distance'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 19, 'weights': 'uniform'},\n",
       " mean: 0.98000, std: 0.03055, params: {'n_neighbors': 19, 'weights': 'distance'},\n",
       " mean: 0.98000, std: 0.03055, params: {'n_neighbors': 20, 'weights': 'uniform'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 20, 'weights': 'distance'},\n",
       " mean: 0.96667, std: 0.03333, params: {'n_neighbors': 21, 'weights': 'uniform'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 21, 'weights': 'distance'},\n",
       " mean: 0.96667, std: 0.03333, params: {'n_neighbors': 22, 'weights': 'uniform'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 22, 'weights': 'distance'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 23, 'weights': 'uniform'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 23, 'weights': 'distance'},\n",
       " mean: 0.96000, std: 0.04422, params: {'n_neighbors': 24, 'weights': 'uniform'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 24, 'weights': 'distance'},\n",
       " mean: 0.96667, std: 0.03333, params: {'n_neighbors': 25, 'weights': 'uniform'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 25, 'weights': 'distance'},\n",
       " mean: 0.96000, std: 0.04422, params: {'n_neighbors': 26, 'weights': 'uniform'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 26, 'weights': 'distance'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 27, 'weights': 'uniform'},\n",
       " mean: 0.98000, std: 0.03055, params: {'n_neighbors': 27, 'weights': 'distance'},\n",
       " mean: 0.95333, std: 0.04269, params: {'n_neighbors': 28, 'weights': 'uniform'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 28, 'weights': 'distance'},\n",
       " mean: 0.95333, std: 0.04269, params: {'n_neighbors': 29, 'weights': 'uniform'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 29, 'weights': 'distance'},\n",
       " mean: 0.95333, std: 0.04269, params: {'n_neighbors': 30, 'weights': 'uniform'},\n",
       " mean: 0.96667, std: 0.03333, params: {'n_neighbors': 30, 'weights': 'distance'}]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# view the complete results\n",
    "grid.grid_scores_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.98\n",
      "{'n_neighbors': 13, 'weights': 'uniform'}\n"
     ]
    }
   ],
   "source": [
    "# examine the best model\n",
    "print grid.best_score_\n",
    "print grid.best_params_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. 使用最佳参数做出预测"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1])"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# train your model using all data and the best known parameters\n",
    "knn = KNeighborsClassifier(n_neighbors=13, weights='uniform')\n",
    "knn.fit(X, y)\n",
    "\n",
    "# make a prediction on out-of-sample data\n",
    "knn.predict([3, 5, 4, 2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**这里使用之前得到的最佳参数对模型进行重新训练，在训练时，就可以将所有的数据都作为训练数据全部投入到模型中去，这样就不会浪费个别数据了。**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1])"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# shortcut: GridSearchCV automatically refits the best model using all of the data\n",
    "grid.predict([3, 5, 4, 2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. 使用RandomizeSearchCV来降低计算代价\n",
    "- RandomizeSearchCV用于解决多个参数的搜索过程中计算代价过高的问题\n",
    "- RandomizeSearchCV搜索参数中的一个子集，这样你可以控制计算代价\n",
    "![](Image/grid_vs_random.jpeg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sklearn.grid_search import RandomizedSearchCV"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# specify \"parameter distributions\" rather than a \"parameter grid\"\n",
    "param_dist = dict(n_neighbors=k_range, weights=weight_options)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[mean: 0.97333, std: 0.03266, params: {'n_neighbors': 18, 'weights': 'distance'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 8, 'weights': 'uniform'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 24, 'weights': 'distance'},\n",
       " mean: 0.98000, std: 0.03055, params: {'n_neighbors': 20, 'weights': 'uniform'},\n",
       " mean: 0.95333, std: 0.04269, params: {'n_neighbors': 28, 'weights': 'uniform'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 9, 'weights': 'uniform'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 5, 'weights': 'distance'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 5, 'weights': 'uniform'},\n",
       " mean: 0.97333, std: 0.03266, params: {'n_neighbors': 19, 'weights': 'uniform'},\n",
       " mean: 0.96667, std: 0.04472, params: {'n_neighbors': 20, 'weights': 'distance'}]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# n_iter controls the number of searches\n",
    "rand = RandomizedSearchCV(knn, param_dist, cv=10, scoring='accuracy', n_iter=10, random_state=5)\n",
    "rand.fit(X, y)\n",
    "rand.grid_scores_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.98\n",
      "{'n_neighbors': 20, 'weights': 'uniform'}\n"
     ]
    }
   ],
   "source": [
    "# examine the best model\n",
    "print rand.best_score_\n",
    "print rand.best_params_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.98, 0.98, 0.973, 0.98, 0.98, 0.98, 0.98, 0.98, 0.98, 0.98, 0.98, 0.973, 0.98, 0.98, 0.98, 0.973, 0.98, 0.98, 0.973, 0.973]\n"
     ]
    }
   ],
   "source": [
    "# run RandomizedSearchCV 20 times (with n_iter=10) and record the best score\n",
    "best_scores = []\n",
    "for _ in range(20):\n",
    "    rand = RandomizedSearchCV(knn, param_dist, cv=10, scoring='accuracy', n_iter=10)\n",
    "    rand.fit(X, y)\n",
    "    best_scores.append(round(rand.best_score_, 3))\n",
    "print best_scores"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**当你的调节参数是连续的，比如回归问题的正则化参数，有必要指定一个连续分布而不是可能值的列表，这样RandomizeSearchCV就可以执行更好的grid search。**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 参考资料\n",
    "- scikit-learn documentation: [Grid search](http://scikit-learn.org/stable/modules/grid_search.html), [GridSearchCV](http://scikit-learn.org/stable/modules/generated/sklearn.grid_search.GridSearchCV.html), [RandomizedSearchCV](http://scikit-learn.org/stable/modules/generated/sklearn.grid_search.RandomizedSearchCV.html)\n",
    "- Timed example: [Comparing randomized search and grid search](http://scikit-learn.org/stable/auto_examples/model_selection/randomized_search.html)\n",
    "- scikit-learn workshop by Andreas Mueller: [Video segment on randomized search (3 minutes)](https://www.youtube.com/watch?v=0wUF_Ov8b0A&feature=youtu.be&t=17m38s), [related notebook](http://nbviewer.ipython.org/github/amueller/pydata-nyc-advanced-sklearn/blob/master/Chapter%203%20-%20Randomized%20Hyper%20Parameter%20Search.ipynb)\n",
    "- Paper by Yoshua Bengio: [Random Search for Hyper-Parameter Optimization](http://www.jmlr.org/papers/volume13/bergstra12a/bergstra12a.pdf)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}