{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Майнор по Анализу Данных, Группа ИАД-2\n",
    "## 08/02/2017 Метод kNN, введение в sklearn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "%matplotlib inline\n",
    "\n",
    "plt.style.use('ggplot')\n",
    "plt.rcParams['figure.figsize'] = (12,8)\n",
    "\n",
    "# Для кириллицы на графиках\n",
    "font = {'family': 'Verdana',\n",
    "        'weight': 'normal'}\n",
    "plt.rc('font', **font)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     2,
     16,
     30
    ],
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "try:\n",
    "    from ipywidgets import interact, IntSlider, fixed\n",
    "    from utils import *\n",
    "except ImportError:\n",
    "    print u'Так надо'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Метод k-ближайших соседей\n",
    "Вспомним теоретическую базу метода kNN.\n",
    "\n",
    "## Общая постановка задачи МО\n",
    "* Множество объектов $O$\n",
    "* Каждому объекту $o \\in O$ можно поставить в соответствие набор признаков $(x, y)$ где\n",
    "    * $x \\in X$ - вектор описательных признаков\n",
    "    * $y \\in Y$ - целевой признак\n",
    "* Существует неизвестная зависимость $f:X \\rightarrow Y$\n",
    "\n",
    "**Задачи:**\n",
    "1. Используя конечный набор примеров $(x, y)$, найти алгоритм (решающую функцию) $a(x) = (\\hat{y})$, аппроксимирующую $f(x)$\n",
    "2. Применить алгоритм $a(x)$ на новых объектах\n",
    "\n",
    "## Как постросить $a(x)$ из семейства метрических методов (kNN)?\n",
    "\n",
    "* Гипотеза компактности: \"Похожим объектам соответстуют похожие ответы\" \n",
    "* Необходимо ввести функцию расстояния между объектами (не обязательно метрику)\n",
    "* Запоминаем обучающую выборку и используем для расчета расстояния\n",
    "\n",
    "### Самые популярные меры расстояния\n",
    "\n",
    "$$ d(a, b) = \\sum\\limits_{i=1}^{D}(a_i - b_i)^2 \\text{: euclidean distance} $$\n",
    "\n",
    "$$ d(a, b) = \\sum\\limits_{i=1}^{D}|a_i - b_i| \\text{: manhattan distance} $$\n",
    "\n",
    "$$ d(a, b) = 1 - \\frac{\\langle a,b \\rangle}{||a||_2\\cdot||b||_2} \\text{: cosine distance} $$\n",
    "\n",
    "### Алгоритм (kNN)\n",
    "\n",
    "Вход: Обучающая выборка $X=(x_i,y_i)$, мера близости $d(\\cdot, \\cdot)$ и объект $\\tilde{x}$<br/>\n",
    "\n",
    "Найти $k$ ближайших объекта в $X$ c помощью $d(\\tilde{x},\\cdot)$ \n",
    "* (регрессия) вернуть среднее значение* $$\\hat{y} = \\frac{1}{k}\\sum\\limits_{j=1}^k y_{(j)}$$\n",
    "* (классификация) вернуть наиболее частую метку класса $$\\hat{y} = \\arg \\max\\limits_{y \\in \\{-1, 1\\}}\\sum\\limits_{j=1}^k [y_{(j)} == y] $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Пример для регрессии"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "x_true = np.arange(-5, 5, 0.2)\n",
    "x = x_true + np.random.rand(x_true.shape[0]) - 0.5\n",
    "y_true = np.sin(x_true)+x_true/3\n",
    "y = y_true + np.random.rand(x_true.shape[0]) - 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "plt.plot(x_true, y_true, c='g', label='$f(x)$')\n",
    "plt.scatter(x, y, label='actual data')\n",
    "plt.xlabel('x')\n",
    "plt.ylabel('y')\n",
    "plt.legend(loc=2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "try:\n",
    "    plot_linreg(x_true, y_true, x, y)\n",
    "except:\n",
    "    print u'Смотрите на доску'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "try:\n",
    "    fig = interact(plot_knn, \n",
    "                   x_true=fixed(x_true), y_true=fixed(y_true), x=fixed(x), y=fixed(y), \n",
    "                   k=IntSlider(min=1, max=10, value=1))\n",
    "except:\n",
    "    print u'Увы, вновь на доске'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Разберемся c sklearn  и сами построим такой график"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sklearn.neighbors import KNeighborsRegressor\n",
    "\n",
    "## Разбираемся"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Пример для классификации"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sklearn.datasets import make_moons\n",
    "X_moons, y_moons = make_moons(noise=0.3, random_state=1234)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "plt.scatter(X_moons[:,0], X_moons[:,1], c=y_moons, s=200)\n",
    "plt.xlabel('$x_1$')\n",
    "plt.ylabel('$x_2$')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "try:\n",
    "    fig = interact(plot_knn_class,\n",
    "                   X_moons=fixed(X_moons), y_moons=fixed(y_moons),\n",
    "                   k=IntSlider(min=1, max=10, value=1))\n",
    "except:\n",
    "    print u'Доскааааа'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Задание\n",
    "\n",
    "Попробуйте сами нарисовать такой график. С этим вам могут помочь функции `np.meshgrid()` и `plt.contourf()`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sklearn.neighbors import KNeighborsClassifier\n",
    "\n",
    "## Your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Взвешенный kNN\n",
    "\n",
    "Вход: Обучающая выборка $X=(x_i,y_i)$, мера близости $d(\\cdot, \\cdot)$ и объект $\\tilde{x}$<br/>\n",
    "\n",
    "Найти $k$ ближайших объекта в $X$ c помощью $d(\\tilde{x},\\cdot)$ \n",
    "\n",
    "* (регрессия) вернуть среднее взвешенное значение* $$\\hat{y} = \\frac{\\sum\\limits_{j=1}^k w_{(j)} y_{(j)}}{\\sum\\limits_{j=1}^k w_{(j)}}$$\n",
    "* (классификация) вернуть наиболее частую метку класса c учетом веса $$\\hat{y} = \\arg \\max\\limits_{y \\in \\{-1, 1\\}}\\sum\\limits_{j=1}^k w_{(j)} [y_{(j)} == y] $$\n",
    "\n",
    "## Варианты весов\n",
    "* $w_{(j)} = \\frac{k - j + 1}{k}$\n",
    "* $w_{(j)} = 1/d(\\tilde{x},x_{(j)})$\n",
    "* $w_{(j)} = K(\\frac{d(\\tilde{x},x_{(j)})}{h}) $ Парзеновское окно (Parzen Window).\n",
    "    * $K$ - ядро, $h$ - ширина окна\n",
    "    \n",
    "## Ядра\n",
    "* $K(d, h) \\propto \\exp(- \\frac{d^2}{2h^2})$ - gaussian kernel\n",
    "* $K(d, h) \\propto 1 if x < d$ - tophat kernel\n",
    "* $K(d, h) \\propto 1 - \\frac{d^2}{h^2}$ - epanechnikov kernel\n",
    "* $K(d, h) \\propto \\exp(-d/h)$ - exponential kernel\n",
    "* $K(d, h) \\propto 1 - d/h if d < h$ - linear kernel\n",
    "* $K(d, h) \\propto \\cos(\\frac{\\pi d}{2h}) if x < h$ - linear kernel\n",
    "\n",
    "<center><img src='http://scikit-learn.org/stable/_images/sphx_glr_plot_kde_1d_0021.png'></center>    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Задание\n",
    "\n",
    "Реализуйте взвешенный kNN с гауссовским ядром для предыдущей задачи"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "## Your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Задание (Дома в Калифорнии)\n",
    "\n",
    "Есть довольно известный набор данных о стоимости домов в штате Калифорния. <br/>Каждое домохозяйство (дом) описывается рядом признаков. Требуется найти зависимость между этими признаками и  стоимостью дома."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sklearn.datasets import fetch_california_housing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "data = fetch_california_housing()\n",
    "\n",
    "X = data.data\n",
    "y = data.target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print data.DESCR"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Возьмем подвыборку\n",
    "lllat, lllon = 33, -125\n",
    "urlat, urlon = 42, -114\n",
    "\n",
    "idx = (X[:, -1] <= urlon) & (X[:, -1] >= lllon) &\\\n",
    "      (X[:, -2] <= urlat) & (X[:, -2] >= lllat)\n",
    "\n",
    "X = X[idx]\n",
    "y = y[idx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Нарисуем это дело\n",
    "plt.figure(figsize=(10, 10))\n",
    "try:\n",
    "    import mpl_toolkits.basemap as bm\n",
    "\n",
    "    m = bm.Basemap(\n",
    "        llcrnrlon=lllon,\n",
    "        llcrnrlat=lllat,\n",
    "        urcrnrlon=urlon,\n",
    "        urcrnrlat=urlat, \n",
    "        projection='merc',\n",
    "        resolution='h'\n",
    "    )\n",
    "\n",
    "    m.drawcoastlines(linewidth=0.5)\n",
    "    m.drawmapboundary(fill_color='#47A4C9', zorder=1)\n",
    "    m.fillcontinents(color='#EBC4D8',lake_color='#47A4C9', zorder=2)\n",
    "\n",
    "    parallels = np.linspace(lllat, urlat, 10)\n",
    "    m.drawparallels(parallels,labels=[1,0,0,0],fontsize=10)\n",
    "    # draw meridians\n",
    "    meridians = np.linspace(lllon, urlon, 10)\n",
    "    m.drawmeridians(meridians,labels=[0,0,0,1],fontsize=10)\n",
    "\n",
    "    m.scatter(X[:, -1], X[:, -2], latlon=True, cmap=plt.cm.hot,\n",
    "              zorder=3, lw=0, c=y)\n",
    "except ImportError:\n",
    "    print u'Не судьба =('\n",
    "    plt.scatter(X[:, -1], X[:, -2], cmap=plt.cm.hot, c=y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Будем использовать только геолокацию домов в качестве признаков.\n",
    "\n",
    "* Мера качества - MSE (mean squared error)\n",
    "* Зафиксируем все гиперпараметры, кроме числа ближайших соседей.\n",
    "* Разбейте данные случайным образом на 3 части - обучающую, валидационную и контрольную в пропорции 70/15/15.\n",
    "* Переберите значение `k` от 1 до 15, выведите на графике ошибку при каждом `k` на обучающей и контрольной выборке\n",
    "* Выберите \"оптимальное\" значение `k`. Является ли результат при этом `k` лучшим на контрольной выборке?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "### Your code here"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "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.12"
  },
  "nav_menu": {},
  "toc": {
   "navigate_menu": true,
   "number_sections": false,
   "sideBar": true,
   "threshold": 6,
   "toc_cell": false,
   "toc_section_display": "block",
   "toc_window_display": true
  },
  "widgets": {
   "state": {
    "60a1d3cc58024e38800da7a9337a1186": {
     "views": [
      {
       "cell_index": 14
      }
     ]
    },
    "eef12fb8bd6d4257b92b2cb148bbb7a1": {
     "views": [
      {
       "cell_index": 8
      }
     ]
    }
   },
   "version": "1.2.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}