{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Майнор по Анализу Данных, Группа ИАД-2\n",
    "## 26/04/2017  Алгоритмы кластеризации"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "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,5)\n",
    "\n",
    "# Для кириллицы на графиках\n",
    "font = {'family': 'Verdana',\n",
    "        'weight': 'normal'}\n",
    "plt.rc('font', **font)\n",
    "\n",
    "try:\n",
    "    from ipywidgets import interact, IntSlider, fixed, FloatSlider\n",
    "except ImportError:\n",
    "    print u'Так надо'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Пищевая ценность продуктов"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Загрузите файл `food.txt`. В нем содержится информация о пищевой ценности разных продуктов"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "# \"Name\" is the name of the item.\n",
    "#\n",
    "# \"Energy\" is the number of calories.\n",
    "#\n",
    "# \"Protein\" is the amount of protein in grams.\n",
    "#\n",
    "# \"Fat\" is the amount of fat in grams.\n",
    "#\n",
    "# \"Calcium\" is the amount of calcium in milligrams.\n",
    "#\n",
    "# \"Iron\" is the amount of iron in milligrams."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Подготовте данные к кластеризации - выполните нормализацию признаков\n",
    "* Сделайте иерарническую кластеризацию этого набора данных.\n",
    "* Изобразите дендрограмму\n",
    "* Выверите число кластеров и интерпретируйте их\n",
    "\n",
    "Почему перед применением кластеризации признки необходимо нормализовать?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from scipy.cluster.hierarchy import dendrogram, fcluster, linkage"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "df = pd.read_csv('food.txt', sep=' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Name</th>\n",
       "      <th>Energy</th>\n",
       "      <th>Protein</th>\n",
       "      <th>Fat</th>\n",
       "      <th>Calcium</th>\n",
       "      <th>Iron</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>Braised beef</td>\n",
       "      <td>340</td>\n",
       "      <td>20</td>\n",
       "      <td>28</td>\n",
       "      <td>9</td>\n",
       "      <td>2.6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>Hamburger</td>\n",
       "      <td>245</td>\n",
       "      <td>21</td>\n",
       "      <td>17</td>\n",
       "      <td>9</td>\n",
       "      <td>2.7</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>Roast beef</td>\n",
       "      <td>420</td>\n",
       "      <td>15</td>\n",
       "      <td>39</td>\n",
       "      <td>7</td>\n",
       "      <td>2.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>Beefsteak</td>\n",
       "      <td>375</td>\n",
       "      <td>19</td>\n",
       "      <td>32</td>\n",
       "      <td>9</td>\n",
       "      <td>2.6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>Canned beef</td>\n",
       "      <td>180</td>\n",
       "      <td>22</td>\n",
       "      <td>10</td>\n",
       "      <td>17</td>\n",
       "      <td>3.7</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "           Name  Energy  Protein  Fat  Calcium  Iron\n",
       "0  Braised beef     340       20   28        9   2.6\n",
       "1     Hamburger     245       21   17        9   2.7\n",
       "2    Roast beef     420       15   39        7   2.0\n",
       "3     Beefsteak     375       19   32        9   2.6\n",
       "4   Canned beef     180       22   10       17   3.7"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## K-means, метод \"локтя\" и меры качества кластеризации"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Загрузите данные по ирисам\n",
    "* Определите количество кластеров для метода k-means с помощью метода \"локтя\"\n",
    "* Выполните кластеризацию и получите вектор с метками кластеров\n",
    "* Оцените качество кластеризации с помощью\n",
    "    * ARI\n",
    "    * Силуэта"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sklearn.datasets import load_iris\n",
    "from sklearn.metrics import adjusted_rand_score, silhouette_samples, silhouette_score\n",
    "from sklearn.cluster import KMeans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Применение K-means на профилях с интересами"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Загрузите [данные](https://github.com/brenden17/sklearnlab/blob/master/facebook/snsdata.csv) в которых содержится описание интересов профилей учеников старшей школы США."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "df_sns = pd.read_csv('snsdata.csv', sep=',')\n",
    "df_sns.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Данные устроены так: \n",
    "* Год выпуска\n",
    "* Пол\n",
    "* Возраст\n",
    "* Количество друзей\n",
    "* 36 ключевых слов, которые встречаются в профилe facebook (интересы, сообщества, встречи)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Удалите все признаки кроме 36 ключевых слов.\n",
    "* Нормализуйте данные - из каждого столбца вычтите его среднее значение и поделите на стандартное отклонение.\n",
    "* Используйте метод k-means чтобы выделить 9 кластеров\n",
    "* Интерпретируйте каждый кластер проанализировав полученные центройды"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sklearn.cluster import KMeans\n",
    "from sklearn.feature_extraction.text import TfidfTransformer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "## Your Code Here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Геоданные"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Загрузите геоданные из `geo_data.txt` (uid, timestamp, lat, lon, location_id).\n",
    "\n",
    "Будем пытаться кластеризовать данные с помощью DBSCAN и меры [haversine](https://en.wikipedia.org/wiki/Haversine_formula)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import mpl_toolkits.basemap as bm\n",
    "from sklearn.cluster import DBSCAN\n",
    "from sklearn.neighbors import NearestNeighbors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "df_geo = pd.read_csv('geo_data.txt', sep='\\t', header=None,\n",
    "                     names=['lat', 'lon'])/10000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "df_geo.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def plot_geo(lat, lon, labels=None):    \n",
    "    try:\n",
    "        lllat, lllon = lat.min()-1, lon.max()+1\n",
    "        urlat, urlon = lat.max()+1, lon.min()-1\n",
    "\n",
    "        plt.figure(figsize=(10, 10))\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(urlon, lllon, 10)\n",
    "        m.drawmeridians(meridians,labels=[0,0,0,1],fontsize=10)\n",
    "\n",
    "        m.scatter(lon, lat, latlon=True, cmap=plt.cm.jet,\n",
    "              zorder=3, lw=0, c=labels)\n",
    "    except:\n",
    "        print 'что-то пошло не так'\n",
    "        plt.scatter(x=lon, y=lat, c=labels, cmap=plt.cm.jet)\n",
    "        plt.axis('equal')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для начала нарисуем все точки на карте"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "plot_geo(df_geo.lat.values, df_geo.lon.values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Мы будем использовать расстояние haversine - на входе требуются координаты в **радианах**. Выход тоже будет в радианах. Чтобы перейти от градусов в радианты мы можем вспомнить тригонометрию, а можем воспользоваться функцией `np.radians`.\n",
    "\n",
    "Для кого, чтобы не терять связь с реальностью, будем иметь ввиду, что расстояние в 1 радиан на земном шаре равно примерно 6371.0088 километрам.\n",
    "\n",
    "Создайте матрицу X с координатами в радианах"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "km_in_radian = 6371.0088\n",
    "X = ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как же определить, какие параметры для DBSCAN выставлять? Наибольшую проблемы представляет параметр eps.\n",
    "\n",
    "Будем считать, что MinPts нам дан свыше (например MinPts = 20). Воспользуемся эвристикой, схожей с методом локтя для оценки eps:\n",
    "\n",
    "* Расчитайте среднее расстояние до k=MinPts ближайших соседей каждой точки (класс `NearestNeighbors` и метод `kneighbors`)\n",
    "* Отсортируйте полученный массив и выведите его на график\n",
    "* Выберите такое расстояние, где будет наблюдаться \"перегиб\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "nn = NearestNeighbors(n_neighbors=20, algorithm='ball_tree', metric='haversine')\n",
    "nn.fit(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "## Your Code Here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Определим eps мы можем начать кластеризацию\n",
    "\n",
    "* Создайте экземпляр класса DBSCAN, кластеризуйте данные\n",
    "* Выведите полученные метки кластеров и их частоты\n",
    "* Изобразите координаты точек, не попавших в кластер выбросов (метка -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "dbscan = DBSCAN(...)\n",
    "## Your Code Here"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.13"
  },
  "livereveal": {
   "theme": "serif",
   "transition": "concave",
   "width": "1024px"
  },
  "nav_menu": {},
  "toc": {
   "navigate_menu": true,
   "number_sections": false,
   "sideBar": false,
   "threshold": 6,
   "toc_cell": false,
   "toc_section_display": "block",
   "toc_window_display": false
  },
  "toc_position": {
   "height": "32px",
   "left": "9px",
   "right": "1379px",
   "top": "33px",
   "width": "212px"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}