4.1. Размещение баннеров (кластеризация).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Задание"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Представим, что международное круизное агентство Carnival Cruise Line решило себя разрекламировать с помощью баннеров и обратилось для этого к вам. Чтобы протестировать, велика ли от таких баннеров польза, их будет размещено всего 20 штук по всему миру. Вам надо выбрать 20 таких локаций для размещения, чтобы польза была большой и агентство продолжило с вами сотрудничать.\n",
    "Агентство крупное, и у него есть несколько офисов по всему миру. Вблизи этих офисов оно и хочет разместить баннеры — легче договариваться и проверять результат. Также эти места должны быть популярны среди туристов.\n",
    "\n",
    "Для поиска оптимальных мест воспользуемся базой данных крупнейшей социальной сети, основанной на локациях — Foursquare.\n",
    "\n",
    "Часть открытых данных есть, например, на сайте archive.org:\n",
    "\n",
    "https://archive.org/details/201309_foursquare_dataset_umn"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Процессинг данных"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Загрузим данные.     \n",
    "Для удобной работы с этим документом преобразуем его к формату csv, удалив строки, не содержащие координат — они неинформативны для нас:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import csv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 3.5 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "with open('checkins.dat') as input_file:        \n",
    "    newLines = []\n",
    "    for line in input_file:\n",
    "        newLine = [x.strip() for x in line.split('|')]\n",
    "        if len(newLine) == 6 and newLine[3] and newLine[4]:\n",
    "            newLines.append(newLine)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 779 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "with open('checkins.csv', 'w') as output_file:\n",
    "    file_writer = csv.writer(output_file)\n",
    "    file_writer.writerows(newLines)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "С помощью pandas построим DataFrame и убедимся, что все 396634 строки с координатами считаны успешно."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 653 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "data = pd.read_csv('checkins.csv', header=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "396634"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>id</th>\n",
       "      <th>user_id</th>\n",
       "      <th>venue_id</th>\n",
       "      <th>latitude</th>\n",
       "      <th>longitude</th>\n",
       "      <th>created_at</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>984222</td>\n",
       "      <td>15824</td>\n",
       "      <td>5222</td>\n",
       "      <td>38.895112</td>\n",
       "      <td>-77.036366</td>\n",
       "      <td>2012-04-21 17:43:47</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>984234</td>\n",
       "      <td>44652</td>\n",
       "      <td>5222</td>\n",
       "      <td>33.800745</td>\n",
       "      <td>-84.410520</td>\n",
       "      <td>2012-04-21 17:43:43</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>984291</td>\n",
       "      <td>105054</td>\n",
       "      <td>5222</td>\n",
       "      <td>45.523452</td>\n",
       "      <td>-122.676207</td>\n",
       "      <td>2012-04-21 17:39:22</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>984318</td>\n",
       "      <td>2146539</td>\n",
       "      <td>5222</td>\n",
       "      <td>40.764462</td>\n",
       "      <td>-111.904565</td>\n",
       "      <td>2012-04-21 17:35:46</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>984232</td>\n",
       "      <td>93870</td>\n",
       "      <td>380645</td>\n",
       "      <td>33.448377</td>\n",
       "      <td>-112.074037</td>\n",
       "      <td>2012-04-21 17:38:18</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>984483</td>\n",
       "      <td>1030290</td>\n",
       "      <td>955969</td>\n",
       "      <td>32.221743</td>\n",
       "      <td>-110.926479</td>\n",
       "      <td>2012-04-21 17:58:54</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>984685</td>\n",
       "      <td>304253</td>\n",
       "      <td>23558</td>\n",
       "      <td>40.650000</td>\n",
       "      <td>-73.950000</td>\n",
       "      <td>2012-04-21 18:19:34</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>984470</td>\n",
       "      <td>720850</td>\n",
       "      <td>749715</td>\n",
       "      <td>33.448377</td>\n",
       "      <td>-112.074037</td>\n",
       "      <td>2012-04-21 17:02:47</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>984610</td>\n",
       "      <td>1639666</td>\n",
       "      <td>442605</td>\n",
       "      <td>33.414768</td>\n",
       "      <td>-111.909309</td>\n",
       "      <td>2012-04-21 18:04:58</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>984653</td>\n",
       "      <td>1647192</td>\n",
       "      <td>23558</td>\n",
       "      <td>42.358431</td>\n",
       "      <td>-71.059773</td>\n",
       "      <td>2012-04-21 18:23:22</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "       id  user_id  venue_id   latitude   longitude           created_at\n",
       "0  984222    15824      5222  38.895112  -77.036366  2012-04-21 17:43:47\n",
       "1  984234    44652      5222  33.800745  -84.410520  2012-04-21 17:43:43\n",
       "2  984291   105054      5222  45.523452 -122.676207  2012-04-21 17:39:22\n",
       "3  984318  2146539      5222  40.764462 -111.904565  2012-04-21 17:35:46\n",
       "4  984232    93870    380645  33.448377 -112.074037  2012-04-21 17:38:18\n",
       "5  984483  1030290    955969  32.221743 -110.926479  2012-04-21 17:58:54\n",
       "6  984685   304253     23558  40.650000  -73.950000  2012-04-21 18:19:34\n",
       "7  984470   720850    749715  33.448377 -112.074037  2012-04-21 17:02:47\n",
       "8  984610  1639666    442605  33.414768 -111.909309  2012-04-21 18:04:58\n",
       "9  984653  1647192     23558  42.358431  -71.059773  2012-04-21 18:23:22"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data.head(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Теперь необходимо кластеризовать данные координаты, чтобы выявить центры скоплений туристов. Поскольку баннеры имеют сравнительно небольшую площадь действия, нам нужен алгоритм, позволяющий ограничить размер кластера и не зависящий от количества кластеров. \n",
    "Используйте MeanShift, указав bandwidth=0.1, что в переводе из градусов в метры колеблется примерно от 5 до 10 км в средних широтах."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Примечание: на 396634 строках кластеризация будет работать долго. Быть очень терпеливым не возбраняется — результат от этого только улучшится. Но для того, чтобы сдать задание, понадобится сабсет из первых 100 тысяч строк. Это компромисс между качеством и затраченным временем. Обучение алгоритма на всём датасете занимает около часа, а на 100 тыс. строк — примерно 2 минуты, однако этого достаточно для получения корректных результатов."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Примечание: на 396634 строках кластеризация будет работать долго. Быть очень терпеливым не возбраняется — результат от этого только улучшится. Но для того, чтобы сдать задание, понадобится сабсет из первых 100 тысяч строк. Это компромисс между качеством и затраченным временем. Обучение алгоритма на всём датасете занимает около часа, а на 100 тыс. строк — примерно 2 минуты, однако этого достаточно для получения корректных результатов.\n",
    "\n",
    "Некоторые из получившихся кластеров содержат слишком мало точек — такие кластеры не интересны рекламодателям. Поэтому надо определить, какие из кластеров содержат, скажем, больше 15 элементов. Центры этих кластеров и являются оптимальными для размещения.\n",
    "\n",
    "При желании увидеть получившиеся результаты на карте можно передать центры получившихся кластеров в один из инструментов визуализации. Например, сайт mapcustomizer.com имеет функцию Bulk Entry, куда можно вставить центры полученных кластеров в формате: 38.8951118,-77.0363658"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как мы помним, 20 баннеров надо разместить близ офисов компании. Найдем на Google Maps по запросу Carnival Cruise Line адреса офисов: 33.751277, -118.188740 (Los Angeles) и т.д."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import sklearn.cluster as cluster"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "X = data.values[0:100000, 3:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "cluster1 = cluster.MeanShift(bandwidth=0.1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "MeanShift(bandwidth=0.1, bin_seeding=False, cluster_all=True, min_bin_freq=1,\n",
       "     n_jobs=1, seeds=None)"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cluster1.fit(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3230"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "labels = cluster1.labels_\n",
    "cluster_centers = cluster1.cluster_centers_\n",
    "\n",
    "labels_unique = np.unique(labels)\n",
    "n_clusters_ = len(labels_unique)\n",
    "n_clusters_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([  33.44943805, -112.00213969])"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cluster_centers[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "d = {}\n",
    "for label in labels:\n",
    "    if label not in d.keys():\n",
    "        d[label] = 1\n",
    "    else:\n",
    "        d[label] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "593\n"
     ]
    }
   ],
   "source": [
    "count = 0\n",
    "for key in d.keys():\n",
    "    if d[key] > 15:\n",
    "        count += 1\n",
    "print(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "clusters_select = np.ndarray(shape=(count,2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[  3.93203654e-315,   3.05592566e-316],\n",
       "       [  1.00131040e-307,   4.45061456e-308],\n",
       "       [  1.33510679e-306,   6.23035620e-307],\n",
       "       ..., \n",
       "       [  8.90077926e-308,   4.45061456e-308],\n",
       "       [  7.78796646e-308,   1.22381779e-307],\n",
       "       [  6.23035619e-307,   1.39071700e-307]])"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clusters_select"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "i = 0\n",
    "j = 0\n",
    "while i < len(cluster_centers):\n",
    "    if d[i] > 15:\n",
    "        clusters_select[j] = cluster_centers[i]\n",
    "        j += 1\n",
    "    i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "593"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(clusters_select)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 40.7177164 , -73.99183542])"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clusters_select[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как мы помним, 20 баннеров надо разместить близ офисов компании. Найдем на Google Maps по запросу \"Carnival Cruise Line\" адреса офисов:   \n",
    "33.751277, -118.188740 (Los Angeles)   \n",
    "25.867736, -80.324116 (Miami)   \n",
    "51.503016, -0.075479 (London)   \n",
    "52.378894, 4.885084 (Amsterdam)   \n",
    "39.366487, 117.036146 (Beijing)   \n",
    "-33.868457, 151.205134 (Sydney)   \n",
    "Осталось определить 20 ближайших к ним центров кластеров. Т.е. посчитать дистанцию до ближайшего офиса для каждой точки и выбрать 20 с наименьшим значением.   \n",
    "Примечание: при подсчете расстояний и в кластеризации можно пренебречь тем, что Земля круглая, так как в точках, расположенных близко друг к другу погрешность мала, а в остальных точках значение достаточно велико.\n",
    "\n",
    "Для сдачи задания выберите из получившихся 20 центров тот, который наименее удален от ближайшего к нему офиса. Ответ в этом задании — широта и долгота этого центра, записанные через пробел."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "offices = np.ndarray(shape=(6,2))\n",
    "offices[0] = np.array([33.751277, -118.188740])\n",
    "offices[1] = np.array([25.867736, -80.324116])\n",
    "offices[2] = np.array([51.503016, -0.075479])\n",
    "offices[3] = np.array([52.378894, 4.885084])\n",
    "offices[4] = np.array([39.366487, 117.036146])\n",
    "offices[5] = np.array([-33.868457, 151.205134])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def distance(point1, point2):\n",
    "    return ((point1[0] - point2[0])**2 + (point1[1] - point2[1])**2)**0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "20.892897123756782"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distance(offices[0], clusters_select[123])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "answer_index = 0\n",
    "min_dist = 0\n",
    "i = 0\n",
    "while i < len(clusters_select):\n",
    "    distances = [distance(xx, clusters_select[i]) for xx in offices]\n",
    "    if min_dist == 0:\n",
    "        min_dist = min(distances)\n",
    "        answer_index = i\n",
    "    else:\n",
    "        if min_dist > min(distances):\n",
    "            min_dist = min(distances)\n",
    "            answer_index = i\n",
    "    i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "410"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer_index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.007834758163107856"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ -33.86063043,  151.20477593])"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clusters_select[answer_index]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def write_answer(center):\n",
    "    with open(\"answer.txt\", \"w\") as f:\n",
    "        f.write(str(center[0]) + ' ' + str(center[1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "write_answer(clusters_select[answer_index])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}