notebooks/wsd/clustering_tutorial.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Кластеризация"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Кластеризация - задача разбиения объектов на группы (кластеры). Кластеризация в отличие от регрессии и классификации не использует правильные ответы при обучении, поэтому это задача обучения без учителя. \n",
    "\n",
    "Основное предположение в кластеризации - объекты, близкие в признаковом пространстве, близки на самом деле. Все алгоритмы кластеризации так или иначе вычисляют близость между объектами (это может быть, например, косинусное расстояние) и стараются организовать кластеры так, чтобы между объектами одного кластера было небольшое расстояние."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Так как считать близости между всеми объектами может быть долго, данные могут распологаться в пространстве странным образом (без четких границ, например) или иметь выбросы, в конкретных алгоритмах кластеризации используются дополнительные предположения и разные трюки. Часто к ним привязывается гиперпараметр(ы), который нужно настраивать самому. Сделать это обычно непросто из-за того, что у нас нет конкретного критерия качества, а сами параметры могут быть непонятными. \n",
    "\n",
    "Есть метрики, которые оценивают качество кластеризации по каким-то внутренним критериям. Также есть способы оценивать качество кластеризации с использованием правильных ответов*. Однако они не всегда коррелируют с тем, что мы хотим получить и приходится оценивать просто на глаз.\n",
    "\n",
    "\\* У вас может возникнуть вопрос - а зачем использовать кластеризацию, когда есть правильные ответы? Это может быть нужно, когда размеченных данных мало относительно общего количества имеющихся данных. В классификации и регрессии мы смогли бы использовать только размеченную часть, а кластеризацию мы можем обучить на всех данных, проверив качество на размеченном куске."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Давайте попробуем кластеризовать заголовки объявлений на Авито, чтобы нагляднее увидеть сложности кластеризации."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = pd.read_csv('data.csv')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>item_id</th>\n",
       "      <th>user_id</th>\n",
       "      <th>region</th>\n",
       "      <th>city</th>\n",
       "      <th>parent_category_name</th>\n",
       "      <th>category_name</th>\n",
       "      <th>param_1</th>\n",
       "      <th>param_2</th>\n",
       "      <th>param_3</th>\n",
       "      <th>title</th>\n",
       "      <th>description</th>\n",
       "      <th>price</th>\n",
       "      <th>item_seq_number</th>\n",
       "      <th>activation_date</th>\n",
       "      <th>user_type</th>\n",
       "      <th>image</th>\n",
       "      <th>image_top_1</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>793dd3d5f0f0</td>\n",
       "      <td>9467e0341c0e</td>\n",
       "      <td>Алтайский край</td>\n",
       "      <td>Барнаул</td>\n",
       "      <td>Личные вещи</td>\n",
       "      <td>Детская одежда и обувь</td>\n",
       "      <td>Для девочек</td>\n",
       "      <td>Платья и юбки</td>\n",
       "      <td>146-152 см (10-12 лет)</td>\n",
       "      <td>Платье праздничное для девочки</td>\n",
       "      <td>Очень красивое торг</td>\n",
       "      <td>1500.0</td>\n",
       "      <td>106</td>\n",
       "      <td>2017-04-12</td>\n",
       "      <td>Company</td>\n",
       "      <td>ace7b2b7f066a6b6ff244f90d030c2c1a1bf118dd0e1ac...</td>\n",
       "      <td>573.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>f8c965d9b668</td>\n",
       "      <td>1905516660f5</td>\n",
       "      <td>Свердловская область</td>\n",
       "      <td>Каменск-Уральский</td>\n",
       "      <td>Для дома и дачи</td>\n",
       "      <td>Мебель и интерьер</td>\n",
       "      <td>Кровати, диваны и кресла</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>Кровать двухспальная</td>\n",
       "      <td>Двуспальная кровать 140х200 с металлическим ка...</td>\n",
       "      <td>5700.0</td>\n",
       "      <td>10</td>\n",
       "      <td>2017-04-15</td>\n",
       "      <td>Private</td>\n",
       "      <td>b38ef24dd5b876ed626bd98241e228e4e19e4160d33abe...</td>\n",
       "      <td>1439.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2f153c00d561</td>\n",
       "      <td>b4dc4849fdd4</td>\n",
       "      <td>Самарская область</td>\n",
       "      <td>Самара</td>\n",
       "      <td>Бытовая электроника</td>\n",
       "      <td>Телефоны</td>\n",
       "      <td>Samsung</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>Samsung S3 mini gt-i8190</td>\n",
       "      <td>Продам телефон самсунг 2 ядра, 1 гиг оперативн...</td>\n",
       "      <td>1500.0</td>\n",
       "      <td>6</td>\n",
       "      <td>2017-04-12</td>\n",
       "      <td>Private</td>\n",
       "      <td>8530cc0c8d5dc6d212497dffd610d89b92a7db952934db...</td>\n",
       "      <td>2932.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>7fc5eea56915</td>\n",
       "      <td>02c14d39fdb4</td>\n",
       "      <td>Саратовская область</td>\n",
       "      <td>Саратов</td>\n",
       "      <td>Личные вещи</td>\n",
       "      <td>Одежда, обувь, аксессуары</td>\n",
       "      <td>Женская одежда</td>\n",
       "      <td>Платья и юбки</td>\n",
       "      <td>44–46 (M)</td>\n",
       "      <td>Красивое платье на одно плечо, в идеале размер м</td>\n",
       "      <td>Заказывала в Сша, прекрасное качество, в деле ...</td>\n",
       "      <td>1000.0</td>\n",
       "      <td>1280</td>\n",
       "      <td>2017-04-13</td>\n",
       "      <td>Company</td>\n",
       "      <td>eb21745ba276d3b00b05856a58fe719e31a82419c0221a...</td>\n",
       "      <td>386.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>b01000d29ea3</td>\n",
       "      <td>b17f14110367</td>\n",
       "      <td>Удмуртия</td>\n",
       "      <td>Ижевск</td>\n",
       "      <td>Личные вещи</td>\n",
       "      <td>Детская одежда и обувь</td>\n",
       "      <td>Для мальчиков</td>\n",
       "      <td>Шапки, варежки, шарфы</td>\n",
       "      <td>NaN</td>\n",
       "      <td>Стильная панама</td>\n",
       "      <td>Состояние новой. Размер до года- полтора.  По ...</td>\n",
       "      <td>150.0</td>\n",
       "      <td>145</td>\n",
       "      <td>2017-04-14</td>\n",
       "      <td>Company</td>\n",
       "      <td>5bf1001fa681b96f121ad8047c85e3747f3dac37830dd0...</td>\n",
       "      <td>209.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "        item_id       user_id                region               city  \\\n",
       "0  793dd3d5f0f0  9467e0341c0e        Алтайский край            Барнаул   \n",
       "1  f8c965d9b668  1905516660f5  Свердловская область  Каменск-Уральский   \n",
       "2  2f153c00d561  b4dc4849fdd4     Самарская область             Самара   \n",
       "3  7fc5eea56915  02c14d39fdb4   Саратовская область            Саратов   \n",
       "4  b01000d29ea3  b17f14110367              Удмуртия             Ижевск   \n",
       "\n",
       "  parent_category_name              category_name                   param_1  \\\n",
       "0          Личные вещи     Детская одежда и обувь               Для девочек   \n",
       "1      Для дома и дачи          Мебель и интерьер  Кровати, диваны и кресла   \n",
       "2  Бытовая электроника                   Телефоны                   Samsung   \n",
       "3          Личные вещи  Одежда, обувь, аксессуары            Женская одежда   \n",
       "4          Личные вещи     Детская одежда и обувь             Для мальчиков   \n",
       "\n",
       "                 param_2                 param_3  \\\n",
       "0          Платья и юбки  146-152 см (10-12 лет)   \n",
       "1                    NaN                     NaN   \n",
       "2                    NaN                     NaN   \n",
       "3          Платья и юбки               44–46 (M)   \n",
       "4  Шапки, варежки, шарфы                     NaN   \n",
       "\n",
       "                                              title  \\\n",
       "0                    Платье праздничное для девочки   \n",
       "1                              Кровать двухспальная   \n",
       "2                          Samsung S3 mini gt-i8190   \n",
       "3  Красивое платье на одно плечо, в идеале размер м   \n",
       "4                                   Стильная панама   \n",
       "\n",
       "                                         description   price  item_seq_number  \\\n",
       "0                                Очень красивое торг  1500.0              106   \n",
       "1  Двуспальная кровать 140х200 с металлическим ка...  5700.0               10   \n",
       "2  Продам телефон самсунг 2 ядра, 1 гиг оперативн...  1500.0                6   \n",
       "3  Заказывала в Сша, прекрасное качество, в деле ...  1000.0             1280   \n",
       "4  Состояние новой. Размер до года- полтора.  По ...   150.0              145   \n",
       "\n",
       "  activation_date user_type  \\\n",
       "0      2017-04-12   Company   \n",
       "1      2017-04-15   Private   \n",
       "2      2017-04-12   Private   \n",
       "3      2017-04-13   Company   \n",
       "4      2017-04-14   Company   \n",
       "\n",
       "                                               image  image_top_1  \n",
       "0  ace7b2b7f066a6b6ff244f90d030c2c1a1bf118dd0e1ac...        573.0  \n",
       "1  b38ef24dd5b876ed626bd98241e228e4e19e4160d33abe...       1439.0  \n",
       "2  8530cc0c8d5dc6d212497dffd610d89b92a7db952934db...       2932.0  \n",
       "3  eb21745ba276d3b00b05856a58fe719e31a82419c0221a...        386.0  \n",
       "4  5bf1001fa681b96f121ad8047c85e3747f3dac37830dd0...        209.0  "
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data.head(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Возьмем ещё название категорий, чтобы попробовать через него оценивать качетство кластеризации."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = data[['category_name', 'title']]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(254219, 2)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "pd.set_option('display.max_rows', 500)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Импотируем разные алгоритмы кластеризации и метрики "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.cluster import AffinityPropagation, AgglomerativeClustering, DBSCAN, \\\n",
    "                            KMeans, MiniBatchKMeans, Birch, MeanShift, SpectralClustering\n",
    "from sklearn.metrics import adjusted_rand_score, adjusted_mutual_info_score, \\\n",
    "                            silhouette_score\n",
    "\n",
    "from sklearn.feature_extraction.text import CountVectorizer\n",
    "from sklearn.decomposition import TruncatedSVD\n",
    "from sklearn import metrics\n",
    "from sklearn.datasets import make_blobs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## AffinityPropagation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<img src=\"https://www.researchgate.net/publication/275558354/figure/fig12/AS:669589163745280@1536653905013/Affinity-propagation-demo-18.png\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import Image\n",
    "from IPython.core.display import HTML \n",
    "Image(url= \"https://www.researchgate.net/publication/275558354/figure/fig12/AS:669589163745280@1536653905013/Affinity-propagation-demo-18.png\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В AP хитрым образом ищутся \"экземпляры\", объекты в выборке которые могут использоваться как прототипы. Ближайшие к прототипам объекты записываются в этот кластер.\n",
    "\n",
    "Приемущества AP - не нужно подбирать количество кластеров.  \n",
    "Недостатки - медленно и тратится много памяти, параметры не очевидные."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "AffinityPropagation не очень с большими дасетами (10к + строчек), поэтому сделаем подвыборку"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# можно переопределить датасет его частью\n",
    "sample = data.sample(frac=0.01)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2542, 2)"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sample.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "С векторизацией пока не будем заморачиваться"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "cv = CountVectorizer(max_features=500)\n",
    "X = cv.fit_transform(sample['title'])\n",
    "\n",
    "y = sample['category_name']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2542, 500)"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "У AP два основных параметра - damping и preference. Второй влияет на количество находимых экземпляров (чем выше значение, тем больше кластеров). Первый не очень понятный, его нужно ставить от 0.5 до 1. Ещё можно поставить max_iter побольше 200, если пишет, что не сошлось."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Converged after 212 iterations.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "AffinityPropagation(affinity='euclidean', convergence_iter=15, copy=True,\n",
       "          damping=0.7, max_iter=400, preference=-5, verbose=2)"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cluster = AffinityPropagation(damping=0.7, preference=-5, \n",
    "                              max_iter=400, verbose=2)\n",
    "cluster.fit(X)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Метки кластеров для всех объектов в датасете лежат в cluster.labels_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "labels = cluster.labels_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Посмотрим сколько кластеров образовалось"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "n_clusters = len(set(labels))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "148"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(set(labels))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Давайте попробуем посчитать метрики "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Основная внутренняя метрика - силуэты. Она считает насколько близки объекты внутри кластера, а также насколько объекты одного кластера далеко от другого кластера."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Silhouette Coefficient: 0.292\n"
     ]
    }
   ],
   "source": [
    "print(\"Silhouette Coefficient: %0.3f\"\n",
    "      % metrics.silhouette_score(X, labels))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Метрики с учётом правильных ответов (в нашем случае категории). Подробно мы их разбирать не будем, основная идея всех метрик - сравнить разбиения без привязки к конкретным меткам. Для этого так или иначе используется информация о том, какие объекты относятся к одному классу и одному кластеру, и какие объекты относятся к разным классам и разным кластерам."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Про метрики можно почитать тут - https://nlp.stanford.edu/IR-book/html/htmledition/evaluation-of-clustering-1.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Homogeneity: 0.461\n",
      "Completeness: 0.396\n",
      "V-measure: 0.426\n",
      "Adjusted Rand Index: -0.001\n",
      "Adjusted Mutual Information: 0.272\n"
     ]
    }
   ],
   "source": [
    "# эти три метрки что-то вроде точности, полноты и ф-меры для кластеризации\n",
    "print(\"Homogeneity: %0.3f\" % metrics.homogeneity_score(y, labels)) # проверяет, что в кластере объекты одного класса\n",
    "print(\"Completeness: %0.3f\" % metrics.completeness_score(y, labels)) # проверяет, что объекты класса только в одном кластере\n",
    "print(\"V-measure: %0.3f\" % metrics.v_measure_score(y, labels)) # превращает обе метрики в одну \n",
    "\n",
    "print(\"Adjusted Rand Index: %0.3f\"\n",
    "      % metrics.adjusted_rand_score(y, labels))\n",
    "print(\"Adjusted Mutual Information: %0.3f\"\n",
    "      % metrics.adjusted_mutual_info_score(y, labels))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Сложно сказать, насколько хорошие или плохие это числа. Давайте попробуем посмотреть глазами"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "sample['cluster'] = cluster.labels_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>category_name</th>\n",
       "      <th>title</th>\n",
       "      <th>cluster</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>100705</th>\n",
       "      <td>Велосипеды</td>\n",
       "      <td>Велосипед</td>\n",
       "      <td>15</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>137695</th>\n",
       "      <td>Товары для детей и игрушки</td>\n",
       "      <td>Велосипед Forvard</td>\n",
       "      <td>15</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>176436</th>\n",
       "      <td>Велосипеды</td>\n",
       "      <td>Велосипед</td>\n",
       "      <td>15</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>73202</th>\n",
       "      <td>Товары для детей и игрушки</td>\n",
       "      <td>Велосипед 3-х колесный</td>\n",
       "      <td>15</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>249439</th>\n",
       "      <td>Товары для детей и игрушки</td>\n",
       "      <td>Велосипед двухколёсный 2402X MaxxPro Verona 24</td>\n",
       "      <td>15</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>116061</th>\n",
       "      <td>Велосипеды</td>\n",
       "      <td>Продаётся велосипед</td>\n",
       "      <td>15</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>42802</th>\n",
       "      <td>Велосипеды</td>\n",
       "      <td>Велосипед горный, взрослый - подростковый, 21 ...</td>\n",
       "      <td>15</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>101022</th>\n",
       "      <td>Велосипеды</td>\n",
       "      <td>Велосипед Spider</td>\n",
       "      <td>15</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>195078</th>\n",
       "      <td>Товары для детей и игрушки</td>\n",
       "      <td>Велосипед трёхколёсный \"Black Aqua\" -9р В наличии</td>\n",
       "      <td>15</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>65016</th>\n",
       "      <td>Товары для детей и игрушки</td>\n",
       "      <td>Трехколесный велосипед Lexus Trike с фарой</td>\n",
       "      <td>15</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                     category_name  \\\n",
       "100705                  Велосипеды   \n",
       "137695  Товары для детей и игрушки   \n",
       "176436                  Велосипеды   \n",
       "73202   Товары для детей и игрушки   \n",
       "249439  Товары для детей и игрушки   \n",
       "116061                  Велосипеды   \n",
       "42802                   Велосипеды   \n",
       "101022                  Велосипеды   \n",
       "195078  Товары для детей и игрушки   \n",
       "65016   Товары для детей и игрушки   \n",
       "\n",
       "                                                    title  cluster  \n",
       "100705                                          Велосипед       15  \n",
       "137695                                  Велосипед Forvard       15  \n",
       "176436                                          Велосипед       15  \n",
       "73202                              Велосипед 3-х колесный       15  \n",
       "249439     Велосипед двухколёсный 2402X MaxxPro Verona 24       15  \n",
       "116061                                Продаётся велосипед       15  \n",
       "42802   Велосипед горный, взрослый - подростковый, 21 ...       15  \n",
       "101022                                   Велосипед Spider       15  \n",
       "195078  Велосипед трёхколёсный \"Black Aqua\" -9р В наличии       15  \n",
       "65016          Трехколесный велосипед Lexus Trike с фарой       15  "
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sample[sample.cluster==15].head(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## AgglomerativeClustering"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<img src=\"https://www.datanovia.com/en/wp-content/uploads/dn-tutorials/003-hierarchical-clustering-in-r/figures/002-agglomerative-clustering-cutree-cut-dendrogram-1.png\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import Image\n",
    "from IPython.core.display import HTML \n",
    "Image(url= \"https://www.datanovia.com/en/wp-content/uploads/dn-tutorials/003-hierarchical-clustering-in-r/figures/002-agglomerative-clustering-cutree-cut-dendrogram-1.png\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В агломеративной кластеризации каждому объекту припывается свой кластер и потом ближайшие кластеры постепенно объединяются, пока не получится 1 кластер или не получится количество, заданное как параметр. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Когда рассказывают про этот вид кластеризации обычно рисуют вот такие картинки. Предполагается, что можно посмотреть на то, как объекты постепенно соединяются и найти оптимальное количество кластеров. Однако это сработает только на небольшом количестве объектов, больше 100 объектов нарисовать будет очень сложно."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Этот вид кластеризации может обработать немного побольше данных"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "sample = data.sample(frac=0.05)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(12711, 2)"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sample.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Аггломеративная кластеризация не умеет работать с sparse матрицами, можно понизить размерность через svd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "cv = CountVectorizer(max_features=500)\n",
    "svd = TruncatedSVD(50)\n",
    "X = cv.fit_transform(sample['title'])\n",
    "X_svd = svd.fit_transform(X)\n",
    "\n",
    "y = sample['category_name']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "47"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(y.unique())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(12711, 500)"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "AgglomerativeClustering(affinity='euclidean', compute_full_tree='auto',\n",
       "            connectivity=None, linkage='ward', memory=None, n_clusters=170,\n",
       "            pooling_func=<function mean at 0x103daa598>)"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# так как визуально мы не может найти оптимальное количество кластеров, придется подбирать\n",
    "# поставим число категорий\n",
    "cluster = AgglomerativeClustering(n_clusters=170)\n",
    "cluster.fit(X_svd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "170"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(set(cluster.labels_))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "labels = cluster.labels_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Давайте попробуем посчитать метрики "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Silhouette Coefficient: 0.271\n"
     ]
    }
   ],
   "source": [
    "print(\"Silhouette Coefficient: %0.3f\"\n",
    "      % metrics.silhouette_score(X, labels))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Homogeneity: 0.373\n",
      "Completeness: 0.354\n",
      "V-measure: 0.363\n",
      "Adjusted Rand Index: -0.001\n",
      "Adjusted Mutual Information: 0.310\n"
     ]
    }
   ],
   "source": [
    "# эти три метрки что-то вроде точности, полноты и ф-меры для кластеризации\n",
    "print(\"Homogeneity: %0.3f\" % metrics.homogeneity_score(y, labels)) # проверяет, что в кластере объекты одного класса\n",
    "print(\"Completeness: %0.3f\" % metrics.completeness_score(y, labels)) # проверяет, что объекты класса только в одном кластере\n",
    "print(\"V-measure: %0.3f\" % metrics.v_measure_score(y, labels)) # превращает обе метрики в одну \n",
    "\n",
    "print(\"Adjusted Rand Index: %0.3f\"\n",
    "      % metrics.adjusted_rand_score(y, labels))\n",
    "print(\"Adjusted Mutual Information: %0.3f\"\n",
    "      % metrics.adjusted_mutual_info_score(y, labels))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "sample['cluster'] = cluster.labels_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Можно проанализировать сколько разных категорий намешалось в один кластер (тем меньше, тем лучше)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15     245\n",
       "115    116\n",
       "30      35\n",
       "39      26\n",
       "27      22\n",
       "149     19\n",
       "161     18\n",
       "24      14\n",
       "7       12\n",
       "91      11\n",
       "124     10\n",
       "117      8\n",
       "155      5\n",
       "102      4\n",
       "113      4\n",
       "65       3\n",
       "48       3\n",
       "34       3\n",
       "158      3\n",
       "114      2\n",
       "94       1\n",
       "159      1\n",
       "140      1\n",
       "4        1\n",
       "Name: cluster, dtype: int64"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sample[sample.category_name=='Телефоны'].cluster.value_counts()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mean Shift"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<img src=\"https://www.researchgate.net/publication/326242239/figure/fig3/AS:645578044231681@1530929208053/Intuitive-description-of-the-mean-shift-procedure-find-the-densest-regions-in-the.png\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import Image\n",
    "from IPython.core.display import HTML \n",
    "Image(url= \"https://www.researchgate.net/publication/326242239/figure/fig3/AS:645578044231681@1530929208053/Intuitive-description-of-the-mean-shift-procedure-find-the-densest-regions-in-the.png\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "MS ищет плотные скопления объектов и ставит там кружочки определеного размера. Все, что попадает в кружочек, относится к кластеру. Количество кластеров задавать не нужно. \n",
    "\n",
    "Это первый их рассмотренных алгоритмов, который не относит к кластерам все объекты."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "sample = data.sample(frac=0.01)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2542, 2)"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sample.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "MS тоже не умеет работать с sparse матрицами"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "cv = CountVectorizer(max_features=2000)\n",
    "svd = TruncatedSVD(50)\n",
    "X = cv.fit_transform(sample['title'])\n",
    "X_svd = svd.fit_transform(X)\n",
    "\n",
    "y = sample['category_name']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.7429017812518477"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# bandwidth - как раз рамер этого кружка, но его сложно подбирать самому, т.к. в каждой задаче он будет свой\n",
    "# вот так можно узнать, что будет по умолчанию и начать с этого значения, постепенно уменьшая или увеличивая\n",
    "import sklearn\n",
    "sklearn.cluster.estimate_bandwidth(X_svd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "MeanShift(bandwidth=0.5, bin_seeding=False, cluster_all=False, min_bin_freq=1,\n",
       "     n_jobs=1, seeds=None)"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# cluster_all=False чтобы не записывать все объекты в кластеры\n",
    "cluster = MeanShift(cluster_all=False, bandwidth=0.5)\n",
    "cluster.fit(X_svd)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Посмотрим сколько кластеров образовалось"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "274"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(set(cluster.labels_))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "labels = cluster.labels_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Silhouette Coefficient: 0.012\n"
     ]
    }
   ],
   "source": [
    "print(\"Silhouette Coefficient: %0.3f\"\n",
    "      % metrics.silhouette_score(X, labels))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Homogeneity: 0.385\n",
      "Completeness: 0.376\n",
      "V-measure: 0.380\n",
      "Adjusted Rand Index: -0.004\n",
      "Adjusted Mutual Information: 0.218\n"
     ]
    }
   ],
   "source": [
    "# эти три метрки что-то вроде точности, полноты и ф-меры для кластеризации\n",
    "print(\"Homogeneity: %0.3f\" % metrics.homogeneity_score(y, labels)) # проверяет, что в кластере объекты одного класса\n",
    "print(\"Completeness: %0.3f\" % metrics.completeness_score(y, labels)) # проверяет, что объекты класса только в одном кластере\n",
    "print(\"V-measure: %0.3f\" % metrics.v_measure_score(y, labels)) # превращает обе метрики в одну \n",
    "\n",
    "print(\"Adjusted Rand Index: %0.3f\"\n",
    "      % metrics.adjusted_rand_score(y, labels))\n",
    "print(\"Adjusted Mutual Information: %0.3f\"\n",
    "      % metrics.adjusted_mutual_info_score(y, labels))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "sample['cluster'] = cluster.labels_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Алгоритмы кластеризация, которые умеют отфильтровывать выбросы, приписывают им -1 кластер."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>category_name</th>\n",
       "      <th>title</th>\n",
       "      <th>cluster</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>183142</th>\n",
       "      <td>Автомобили</td>\n",
       "      <td>Toyota Land Cruiser Prado, 1993</td>\n",
       "      <td>-1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>17609</th>\n",
       "      <td>Ремонт и строительство</td>\n",
       "      <td>Сруб в чашу или лапу, 5з8 и др размеры по желанию</td>\n",
       "      <td>-1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>185213</th>\n",
       "      <td>Мебель и интерьер</td>\n",
       "      <td>Софа-диван-кровать</td>\n",
       "      <td>-1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>18211</th>\n",
       "      <td>Детская одежда и обувь</td>\n",
       "      <td>Резиновые сапоги</td>\n",
       "      <td>-1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>171561</th>\n",
       "      <td>Детская одежда и обувь</td>\n",
       "      <td>Детские платья пакетом</td>\n",
       "      <td>-1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                 category_name  \\\n",
       "183142              Автомобили   \n",
       "17609   Ремонт и строительство   \n",
       "185213       Мебель и интерьер   \n",
       "18211   Детская одежда и обувь   \n",
       "171561  Детская одежда и обувь   \n",
       "\n",
       "                                                    title  cluster  \n",
       "183142                    Toyota Land Cruiser Prado, 1993       -1  \n",
       "17609   Сруб в чашу или лапу, 5з8 и др размеры по желанию       -1  \n",
       "185213                                 Софа-диван-кровать       -1  \n",
       "18211                                    Резиновые сапоги       -1  \n",
       "171561                             Детские платья пакетом       -1  "
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# так мы можем оценить, действительно ли отсеивается мусор или мы просто недокластеризуем\n",
    "sample[sample.cluster==-1].head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Spectral Clustering"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В SC перед тем как кластерозовать к объектам применяется какое-то преобразование. Это преобразование должно приводить странно организованные в пространстве объекты к более стандартному виду, который могут переварить простые алгоритмы кластеризации (по дефолту используется KMEANS - про него немного ниже)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Так как кластируется через kmeans нужно подбирать количество кластеров самому."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "metadata": {},
   "outputs": [],
   "source": [
    "sample = data.sample(frac=0.01)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2542, 2)"
      ]
     },
     "execution_count": 146,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sample.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Аггломеративная кластеризация не умеет работать с sparse матрицами, можно понизить размерность через svd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [],
   "source": [
    "cv = CountVectorizer(max_features=500)\n",
    "svd = TruncatedSVD(50)\n",
    "X = cv.fit_transform(sample['title'])\n",
    "X_svd = svd.fit_transform(X)\n",
    "\n",
    "y = sample['category_name']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2542, 500)"
      ]
     },
     "execution_count": 148,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "SpectralClustering(affinity='rbf', assign_labels='kmeans', coef0=1, degree=3,\n",
       "          eigen_solver=None, eigen_tol=0.0, gamma=1.0, kernel_params=None,\n",
       "          n_clusters=47, n_init=10, n_jobs=1, n_neighbors=10,\n",
       "          random_state=None)"
      ]
     },
     "execution_count": 149,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cluster = SpectralClustering(n_clusters=47)\n",
    "cluster.fit(X_svd)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Метки кластеров для всех объектов в датасете лежат в cluster.labels_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([38, 40,  1, ...,  3,  7,  1], dtype=int32)"
      ]
     },
     "execution_count": 150,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cluster.labels_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Посмотрим сколько кластеров образовалось"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "47"
      ]
     },
     "execution_count": 151,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(set(cluster.labels_))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [],
   "source": [
    "labels = cluster.labels_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Давайте попробуем посчитать метрики "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Silhouette Coefficient: 0.175\n"
     ]
    }
   ],
   "source": [
    "print(\"Silhouette Coefficient: %0.3f\"\n",
    "      % metrics.silhouette_score(X, labels))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Homogeneity: 0.298\n",
      "Completeness: 0.362\n",
      "V-measure: 0.327\n",
      "Adjusted Rand Index: -0.005\n",
      "Adjusted Mutual Information: 0.225\n"
     ]
    }
   ],
   "source": [
    "# эти три метрки что-то вроде точности, полноты и ф-меры для кластеризации\n",
    "print(\"Homogeneity: %0.3f\" % metrics.homogeneity_score(y, labels)) # проверяет, что в кластере объекты одного класса\n",
    "print(\"Completeness: %0.3f\" % metrics.completeness_score(y, labels)) # проверяет, что объекты класса только в одном кластере\n",
    "print(\"V-measure: %0.3f\" % metrics.v_measure_score(y, labels)) # превращает обе метрики в одну \n",
    "\n",
    "print(\"Adjusted Rand Index: %0.3f\"\n",
    "      % metrics.adjusted_rand_score(y, labels))\n",
    "print(\"Adjusted Mutual Information: %0.3f\"\n",
    "      % metrics.adjusted_mutual_info_score(y, labels))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Посмотрим на глаз"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {},
   "outputs": [],
   "source": [
    "sample['cluster'] = cluster.labels_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>category_name</th>\n",
       "      <th>title</th>\n",
       "      <th>cluster</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>153172</th>\n",
       "      <td>Земельные участки</td>\n",
       "      <td>Участок 7.8 сот. (СНТ, ДНП)</td>\n",
       "      <td>35</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>21443</th>\n",
       "      <td>Земельные участки</td>\n",
       "      <td>Участок 6 сот. (СНТ, ДНП)</td>\n",
       "      <td>35</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>15608</th>\n",
       "      <td>Земельные участки</td>\n",
       "      <td>Участок 6 сот. (СНТ, ДНП)</td>\n",
       "      <td>35</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>127016</th>\n",
       "      <td>Земельные участки</td>\n",
       "      <td>Участок 5.64 га (СНТ, ДНП)</td>\n",
       "      <td>35</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4234</th>\n",
       "      <td>Земельные участки</td>\n",
       "      <td>Участок 15 сот. (СНТ, ДНП)</td>\n",
       "      <td>35</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>54916</th>\n",
       "      <td>Земельные участки</td>\n",
       "      <td>Куплю участок (СНТ, ДНП)</td>\n",
       "      <td>35</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>202213</th>\n",
       "      <td>Земельные участки</td>\n",
       "      <td>Участок 7 сот. (СНТ, ДНП)</td>\n",
       "      <td>35</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>236993</th>\n",
       "      <td>Земельные участки</td>\n",
       "      <td>Участок 7 сот. (СНТ, ДНП)</td>\n",
       "      <td>35</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>144766</th>\n",
       "      <td>Земельные участки</td>\n",
       "      <td>Участок 8 сот. (СНТ, ДНП)</td>\n",
       "      <td>35</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3297</th>\n",
       "      <td>Земельные участки</td>\n",
       "      <td>Участок 7.8 сот. (СНТ, ДНП)</td>\n",
       "      <td>35</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>118944</th>\n",
       "      <td>Земельные участки</td>\n",
       "      <td>Участок 23.8 сот. (СНТ, ДНП)</td>\n",
       "      <td>35</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>250772</th>\n",
       "      <td>Земельные участки</td>\n",
       "      <td>Участок 8 сот. (СНТ, ДНП)</td>\n",
       "      <td>35</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "            category_name                         title  cluster\n",
       "153172  Земельные участки   Участок 7.8 сот. (СНТ, ДНП)       35\n",
       "21443   Земельные участки     Участок 6 сот. (СНТ, ДНП)       35\n",
       "15608   Земельные участки     Участок 6 сот. (СНТ, ДНП)       35\n",
       "127016  Земельные участки    Участок 5.64 га (СНТ, ДНП)       35\n",
       "4234    Земельные участки    Участок 15 сот. (СНТ, ДНП)       35\n",
       "54916   Земельные участки      Куплю участок (СНТ, ДНП)       35\n",
       "202213  Земельные участки     Участок 7 сот. (СНТ, ДНП)       35\n",
       "236993  Земельные участки     Участок 7 сот. (СНТ, ДНП)       35\n",
       "144766  Земельные участки     Участок 8 сот. (СНТ, ДНП)       35\n",
       "3297    Земельные участки   Участок 7.8 сот. (СНТ, ДНП)       35\n",
       "118944  Земельные участки  Участок 23.8 сот. (СНТ, ДНП)       35\n",
       "250772  Земельные участки     Участок 8 сот. (СНТ, ДНП)       35"
      ]
     },
     "execution_count": 160,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sample[sample.cluster==35]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## DBSCAN"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<img src=\"https://media.giphy.com/media/lCL2GQewp7fkk/giphy.gif\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import Image\n",
    "from IPython.core.display import HTML \n",
    "Image(url= \"https://media.giphy.com/media/lCL2GQewp7fkk/giphy.gif\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "DBSCAN похож на MS и Spectral Clustering. К данным применяется какое-то преобразование, чтобы скучковать близкие объекты и ещё дальше откинуть выбросы. Потом выбирается какой-то объект и в его окрестностях ищутся другие объекты. Если находятся, то эти объекты сливаются в один кластер и так далее. Если количество объектов в кластере меньше порога, то объекты считаются выбросами. (На самом деле там все немного сложнее чем на картинке, но это не так важно)\n",
    "\n",
    "DBSCAN сам находит количество кластеров и умеет отфильтровывать выбросы. Параметрами можно настраивать объём окрестности и таким оброзом влиять на кластеры."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Интерактивная визуализация есть тут - https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "sample = data.sample(frac=0.05)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(12711, 2)"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sample.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Аггломеративная кластеризация не умеет работать с sparse матрицами, можно понизить размерность через svd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "cv = CountVectorizer(max_features=2000)\n",
    "svd = TruncatedSVD(50)\n",
    "X = cv.fit_transform(sample['title'])\n",
    "X_svd = svd.fit_transform(X)\n",
    "\n",
    "y = sample['category_name']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(12711, 2000)"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "DBSCAN(algorithm='auto', eps=0.3, leaf_size=30, metric='euclidean',\n",
       "    metric_params=None, min_samples=10, n_jobs=1, p=None)"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# eps - задает максимальную для объединения дистанцию между объектами == размер окрестности\n",
    "# min_samples - минимальное количество объектов в классе\n",
    "\n",
    "cluster = DBSCAN(min_samples=10, eps=0.3) \n",
    "cluster.fit(X_svd)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Метки кластеров для всех объектов в датасете лежат в cluster.labels_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0,  0,  0, ..., 17, 85, 12])"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cluster.labels_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Посмотрим сколько кластеров образовалось"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "92"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(set(cluster.labels_))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Давайте попробуем посчитать метрики "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "labels = cluster.labels_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Silhouette Coefficient: 0.069\n"
     ]
    }
   ],
   "source": [
    "print(\"Silhouette Coefficient: %0.3f\"\n",
    "      % metrics.silhouette_score(X, labels))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Homogeneity: 0.286\n",
      "Completeness: 0.338\n",
      "V-measure: 0.310\n",
      "Adjusted Rand Index: -0.005\n",
      "Adjusted Mutual Information: 0.254\n"
     ]
    }
   ],
   "source": [
    "# эти три метрки что-то вроде точности, полноты и ф-меры для кластеризации\n",
    "print(\"Homogeneity: %0.3f\" % metrics.homogeneity_score(y, labels)) # проверяет, что в кластере объекты одного класса\n",
    "print(\"Completeness: %0.3f\" % metrics.completeness_score(y, labels)) # проверяет, что объекты класса только в одном кластере\n",
    "print(\"V-measure: %0.3f\" % metrics.v_measure_score(y, labels)) # превращает обе метрики в одну \n",
    "\n",
    "print(\"Adjusted Rand Index: %0.3f\"\n",
    "      % metrics.adjusted_rand_score(y, labels))\n",
    "print(\"Adjusted Mutual Information: %0.3f\"\n",
    "      % metrics.adjusted_mutual_info_score(y, labels))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "sample['cluster'] = cluster.labels_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>category_name</th>\n",
       "      <th>title</th>\n",
       "      <th>cluster</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>151391</th>\n",
       "      <td>Автомобили</td>\n",
       "      <td>ВАЗ 2106, 1989</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>246618</th>\n",
       "      <td>Автомобили</td>\n",
       "      <td>ВАЗ 2107, 2002</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>201694</th>\n",
       "      <td>Автомобили</td>\n",
       "      <td>ВАЗ 2112, 2001</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>209754</th>\n",
       "      <td>Автомобили</td>\n",
       "      <td>ВАЗ 2110, 2001</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9165</th>\n",
       "      <td>Автомобили</td>\n",
       "      <td>ВАЗ 21099, 2004</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "       category_name            title  cluster\n",
       "151391    Автомобили   ВАЗ 2106, 1989        5\n",
       "246618    Автомобили   ВАЗ 2107, 2002        5\n",
       "201694    Автомобили   ВАЗ 2112, 2001        5\n",
       "209754    Автомобили   ВАЗ 2110, 2001        5\n",
       "9165      Автомобили  ВАЗ 21099, 2004        5"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sample[sample.cluster==5].head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Есть еще HDBSCAN - оптимизированная версия DBSCAN. Его нет в sklearn, но есть отдельная библиотека с аналогичным интерфейсом - https://hdbscan.readthedocs.io/en/latest/how_hdbscan_works.html "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## KMeans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<img src=\"https://media.giphy.com/media/hgCM9JNzlqAr6/giphy.gif\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import Image\n",
    "from IPython.core.display import HTML \n",
    "Image(url= \"https://media.giphy.com/media/hgCM9JNzlqAr6/giphy.gif\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "KMeans наверное самый известный алгоритм кластеризации. Выбирается количество кластеров, случайно раскидываются центры этих кластеров, объекты относятся к ближайшим кластерам, центры кластеров пересчитываются в среднее значение попавших в него объектов."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Более интерактивную версию можно посмотреть вот тут - https://www.naftaliharris.com/blog/visualizing-k-means-clustering/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "KMeans достаточно быстрый"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [],
   "source": [
    "sample = data.sample(frac=0.1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(25422, 2)"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sample.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Kmeans и так и так может"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [],
   "source": [
    "cv = CountVectorizer(max_features=500)\n",
    "svd = TruncatedSVD(50)\n",
    "X = cv.fit_transform(sample['title'])\n",
    "X_svd = svd.fit_transform(X)\n",
    "\n",
    "y = sample['category_name']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "47"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(y.unique())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(25422, 500)"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "KMeans(algorithm='auto', copy_x=True, init='k-means++', max_iter=300,\n",
       "    n_clusters=47, n_init=10, n_jobs=1, precompute_distances='auto',\n",
       "    random_state=None, tol=0.0001, verbose=0)"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cluster = KMeans(n_clusters=47)\n",
    "cluster.fit(X_svd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [],
   "source": [
    "labels = cluster.labels_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Давайте попробуем посчитать метрики (данных теперь больше и силуэты долго будут считаться)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Silhouette Coefficient: 0.243\n"
     ]
    }
   ],
   "source": [
    "print(\"Silhouette Coefficient: %0.3f\"\n",
    "      % metrics.silhouette_score(X[:10000], labels[:10000]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Homogeneity: 0.298\n",
      "Completeness: 0.379\n",
      "V-measure: 0.334\n",
      "Adjusted Rand Index: 0.001\n",
      "Adjusted Mutual Information: 0.288\n"
     ]
    }
   ],
   "source": [
    "# эти три метрки что-то вроде точности, полноты и ф-меры для кластеризации\n",
    "print(\"Homogeneity: %0.3f\" % metrics.homogeneity_score(y, labels)) # проверяет, что в кластере объекты одного класса\n",
    "print(\"Completeness: %0.3f\" % metrics.completeness_score(y, labels)) # проверяет, что объекты класса только в одном кластере\n",
    "print(\"V-measure: %0.3f\" % metrics.v_measure_score(y, labels)) # превращает обе метрики в одну \n",
    "\n",
    "print(\"Adjusted Rand Index: %0.3f\"\n",
    "      % metrics.adjusted_rand_score(y, labels))\n",
    "print(\"Adjusted Mutual Information: %0.3f\"\n",
    "      % metrics.adjusted_mutual_info_score(y, labels))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [],
   "source": [
    "sample['cluster'] = cluster.labels_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>category_name</th>\n",
       "      <th>title</th>\n",
       "      <th>cluster</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>28940</th>\n",
       "      <td>Квартиры</td>\n",
       "      <td>Сниму 1-к квартиру</td>\n",
       "      <td>13</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>65749</th>\n",
       "      <td>Квартиры</td>\n",
       "      <td>Куплю 2-к квартиру</td>\n",
       "      <td>13</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>140302</th>\n",
       "      <td>Квартиры</td>\n",
       "      <td>Куплю 2-к квартиру</td>\n",
       "      <td>13</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>27500</th>\n",
       "      <td>Дома, дачи, коттеджи</td>\n",
       "      <td>Сниму дом</td>\n",
       "      <td>13</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>162460</th>\n",
       "      <td>Коммерческая недвижимость</td>\n",
       "      <td>Сниму помещение под кофейню</td>\n",
       "      <td>13</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                    category_name                        title  cluster\n",
       "28940                    Квартиры           Сниму 1-к квартиру       13\n",
       "65749                    Квартиры           Куплю 2-к квартиру       13\n",
       "140302                   Квартиры           Куплю 2-к квартиру       13\n",
       "27500        Дома, дачи, коттеджи                    Сниму дом       13\n",
       "162460  Коммерческая недвижимость  Сниму помещение под кофейню       13"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sample[sample.cluster==13].head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# MiniBatchKMeans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Kmeans работает и быстрее и переваривает больше данных, чем предыдущие алгоритмы. Но есть и ещё более мощный алгоритм - MiniBatchKmeans. По названию можно догадаться, что это тот же Kmeans только на батчах. Кластеры обновляются на батчах, что позволяет значительно ускорить схождение и уменьшить требования к памяти. MiniBatchKmeans может переварить огромные датасеты (никакого сэмпла тут делать не надо). Результат конечно будет отличаться от Kmeans в худшую сторону, но есть эксперименты, которые показывают, что отличие не значительное и перекрывается остальными преимуществами."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [],
   "source": [
    "cv = CountVectorizer(max_features=5000)\n",
    "svd = TruncatedSVD(200)\n",
    "X = cv.fit_transform(data['title'])\n",
    "X_svd = svd.fit_transform(X)\n",
    "\n",
    "y = data['category_name']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(254219, 5000)"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "47"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(y.unique())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Init 1/3 with method: k-means++\n",
      "Inertia for init 1/3: 750.054492\n",
      "Init 2/3 with method: k-means++\n",
      "Inertia for init 2/3: 750.253051\n",
      "Init 3/3 with method: k-means++\n",
      "Inertia for init 3/3: 720.099500\n",
      "Minibatch iteration 1/12715000: mean batch inertia: 0.192597, ewa inertia: 0.192597 \n",
      "Minibatch iteration 2/12715000: mean batch inertia: 0.134174, ewa inertia: 0.192551 \n",
      "Minibatch iteration 3/12715000: mean batch inertia: 0.256749, ewa inertia: 0.192601 \n",
      "Minibatch iteration 4/12715000: mean batch inertia: 0.270063, ewa inertia: 0.192662 \n",
      "Minibatch iteration 5/12715000: mean batch inertia: 0.300767, ewa inertia: 0.192747 \n",
      "Minibatch iteration 6/12715000: mean batch inertia: 0.221604, ewa inertia: 0.192770 \n",
      "Minibatch iteration 7/12715000: mean batch inertia: 0.214805, ewa inertia: 0.192787 \n",
      "Minibatch iteration 8/12715000: mean batch inertia: 0.288842, ewa inertia: 0.192863 \n",
      "Minibatch iteration 9/12715000: mean batch inertia: 0.171374, ewa inertia: 0.192846 \n",
      "[MiniBatchKMeans] Reassigning 50 cluster centers.\n",
      "Minibatch iteration 10/12715000: mean batch inertia: 0.149643, ewa inertia: 0.192812 \n",
      "Minibatch iteration 11/12715000: mean batch inertia: 0.160466, ewa inertia: 0.192786 \n",
      "Minibatch iteration 12/12715000: mean batch inertia: 0.260365, ewa inertia: 0.192840 \n",
      "Minibatch iteration 13/12715000: mean batch inertia: 0.168328, ewa inertia: 0.192820 \n",
      "Minibatch iteration 14/12715000: mean batch inertia: 0.154126, ewa inertia: 0.192790 \n",
      "Minibatch iteration 15/12715000: mean batch inertia: 0.207093, ewa inertia: 0.192801 \n",
      "Minibatch iteration 16/12715000: mean batch inertia: 0.170974, ewa inertia: 0.192784 \n",
      "Minibatch iteration 17/12715000: mean batch inertia: 0.268448, ewa inertia: 0.192843 \n",
      "Minibatch iteration 18/12715000: mean batch inertia: 0.170628, ewa inertia: 0.192826 \n",
      "Minibatch iteration 19/12715000: mean batch inertia: 0.176384, ewa inertia: 0.192813 \n",
      "[MiniBatchKMeans] Reassigning 50 cluster centers.\n",
      "Minibatch iteration 20/12715000: mean batch inertia: 0.224175, ewa inertia: 0.192838 \n",
      "Minibatch iteration 21/12715000: mean batch inertia: 0.260231, ewa inertia: 0.192891 \n",
      "Minibatch iteration 22/12715000: mean batch inertia: 0.198847, ewa inertia: 0.192895 \n",
      "Minibatch iteration 23/12715000: mean batch inertia: 0.240896, ewa inertia: 0.192933 \n",
      "Minibatch iteration 24/12715000: mean batch inertia: 0.215739, ewa inertia: 0.192951 \n",
      "Minibatch iteration 25/12715000: mean batch inertia: 0.165941, ewa inertia: 0.192930 \n",
      "Minibatch iteration 26/12715000: mean batch inertia: 0.172152, ewa inertia: 0.192914 \n",
      "Minibatch iteration 27/12715000: mean batch inertia: 0.231835, ewa inertia: 0.192944 \n",
      "Minibatch iteration 28/12715000: mean batch inertia: 0.311138, ewa inertia: 0.193037 \n",
      "Minibatch iteration 29/12715000: mean batch inertia: 0.176915, ewa inertia: 0.193024 \n",
      "[MiniBatchKMeans] Reassigning 50 cluster centers.\n",
      "Minibatch iteration 30/12715000: mean batch inertia: 0.183026, ewa inertia: 0.193017 \n",
      "Minibatch iteration 31/12715000: mean batch inertia: 0.192507, ewa inertia: 0.193016 \n",
      "Minibatch iteration 32/12715000: mean batch inertia: 0.202041, ewa inertia: 0.193023 \n",
      "Minibatch iteration 33/12715000: mean batch inertia: 0.221816, ewa inertia: 0.193046 \n",
      "Minibatch iteration 34/12715000: mean batch inertia: 0.205791, ewa inertia: 0.193056 \n",
      "Minibatch iteration 35/12715000: mean batch inertia: 0.170244, ewa inertia: 0.193038 \n",
      "Minibatch iteration 36/12715000: mean batch inertia: 0.241606, ewa inertia: 0.193076 \n",
      "Minibatch iteration 37/12715000: mean batch inertia: 0.269919, ewa inertia: 0.193137 \n",
      "Minibatch iteration 38/12715000: mean batch inertia: 0.208696, ewa inertia: 0.193149 \n",
      "Minibatch iteration 39/12715000: mean batch inertia: 0.338921, ewa inertia: 0.193264 \n",
      "[MiniBatchKMeans] Reassigning 50 cluster centers.\n",
      "Minibatch iteration 40/12715000: mean batch inertia: 0.214153, ewa inertia: 0.193280 \n",
      "Minibatch iteration 41/12715000: mean batch inertia: 0.204610, ewa inertia: 0.193289 \n",
      "Minibatch iteration 42/12715000: mean batch inertia: 0.252914, ewa inertia: 0.193336 \n",
      "Minibatch iteration 43/12715000: mean batch inertia: 0.181735, ewa inertia: 0.193327 \n",
      "Minibatch iteration 44/12715000: mean batch inertia: 0.155907, ewa inertia: 0.193297 \n",
      "Minibatch iteration 45/12715000: mean batch inertia: 0.129296, ewa inertia: 0.193247 \n",
      "Minibatch iteration 46/12715000: mean batch inertia: 0.190542, ewa inertia: 0.193245 \n",
      "Minibatch iteration 47/12715000: mean batch inertia: 0.167259, ewa inertia: 0.193224 \n",
      "Minibatch iteration 48/12715000: mean batch inertia: 0.282115, ewa inertia: 0.193294 \n",
      "Minibatch iteration 49/12715000: mean batch inertia: 0.170215, ewa inertia: 0.193276 \n",
      "[MiniBatchKMeans] Reassigning 50 cluster centers.\n",
      "Minibatch iteration 50/12715000: mean batch inertia: 0.158308, ewa inertia: 0.193249 \n",
      "Minibatch iteration 51/12715000: mean batch inertia: 0.162218, ewa inertia: 0.193224 \n",
      "Minibatch iteration 52/12715000: mean batch inertia: 0.184756, ewa inertia: 0.193218 \n",
      "Minibatch iteration 53/12715000: mean batch inertia: 0.169936, ewa inertia: 0.193199 \n",
      "Minibatch iteration 54/12715000: mean batch inertia: 0.199686, ewa inertia: 0.193204 \n",
      "Minibatch iteration 55/12715000: mean batch inertia: 0.251393, ewa inertia: 0.193250 \n",
      "Minibatch iteration 56/12715000: mean batch inertia: 0.164874, ewa inertia: 0.193228 \n",
      "Minibatch iteration 57/12715000: mean batch inertia: 0.221148, ewa inertia: 0.193250 \n",
      "Minibatch iteration 58/12715000: mean batch inertia: 0.212062, ewa inertia: 0.193265 \n",
      "Minibatch iteration 59/12715000: mean batch inertia: 0.192353, ewa inertia: 0.193264 \n",
      "[MiniBatchKMeans] Reassigning 50 cluster centers.\n",
      "Minibatch iteration 60/12715000: mean batch inertia: 0.170153, ewa inertia: 0.193246 \n",
      "Minibatch iteration 61/12715000: mean batch inertia: 0.214176, ewa inertia: 0.193262 \n",
      "Minibatch iteration 62/12715000: mean batch inertia: 0.216894, ewa inertia: 0.193281 \n",
      "Minibatch iteration 63/12715000: mean batch inertia: 0.161505, ewa inertia: 0.193256 \n",
      "Minibatch iteration 64/12715000: mean batch inertia: 0.192403, ewa inertia: 0.193255 \n",
      "Minibatch iteration 65/12715000: mean batch inertia: 0.193199, ewa inertia: 0.193255 \n",
      "Minibatch iteration 66/12715000: mean batch inertia: 0.128334, ewa inertia: 0.193204 \n",
      "Minibatch iteration 67/12715000: mean batch inertia: 0.181436, ewa inertia: 0.193195 \n",
      "Minibatch iteration 68/12715000: mean batch inertia: 0.202138, ewa inertia: 0.193202 \n",
      "Minibatch iteration 69/12715000: mean batch inertia: 0.180014, ewa inertia: 0.193191 \n",
      "[MiniBatchKMeans] Reassigning 50 cluster centers.\n",
      "Minibatch iteration 70/12715000: mean batch inertia: 0.293859, ewa inertia: 0.193271 \n",
      "Minibatch iteration 71/12715000: mean batch inertia: 0.219192, ewa inertia: 0.193291 \n",
      "Minibatch iteration 72/12715000: mean batch inertia: 0.257413, ewa inertia: 0.193341 \n",
      "Minibatch iteration 73/12715000: mean batch inertia: 0.190786, ewa inertia: 0.193339 \n",
      "Minibatch iteration 74/12715000: mean batch inertia: 0.214401, ewa inertia: 0.193356 \n",
      "Minibatch iteration 75/12715000: mean batch inertia: 0.191939, ewa inertia: 0.193355 \n",
      "Minibatch iteration 76/12715000: mean batch inertia: 0.219522, ewa inertia: 0.193375 \n",
      "Minibatch iteration 77/12715000: mean batch inertia: 0.287568, ewa inertia: 0.193450 \n",
      "Minibatch iteration 78/12715000: mean batch inertia: 0.220388, ewa inertia: 0.193471 \n",
      "Minibatch iteration 79/12715000: mean batch inertia: 0.252722, ewa inertia: 0.193517 \n",
      "[MiniBatchKMeans] Reassigning 50 cluster centers.\n",
      "Minibatch iteration 80/12715000: mean batch inertia: 0.210321, ewa inertia: 0.193531 \n",
      "Minibatch iteration 81/12715000: mean batch inertia: 0.351132, ewa inertia: 0.193655 \n",
      "Minibatch iteration 82/12715000: mean batch inertia: 0.242306, ewa inertia: 0.193693 \n",
      "Minibatch iteration 83/12715000: mean batch inertia: 0.280874, ewa inertia: 0.193761 \n",
      "Minibatch iteration 84/12715000: mean batch inertia: 0.175795, ewa inertia: 0.193747 \n",
      "Minibatch iteration 85/12715000: mean batch inertia: 0.191196, ewa inertia: 0.193745 \n",
      "Minibatch iteration 86/12715000: mean batch inertia: 0.179413, ewa inertia: 0.193734 \n",
      "Minibatch iteration 87/12715000: mean batch inertia: 0.181386, ewa inertia: 0.193724 \n",
      "Minibatch iteration 88/12715000: mean batch inertia: 0.157505, ewa inertia: 0.193696 \n",
      "Minibatch iteration 89/12715000: mean batch inertia: 0.263829, ewa inertia: 0.193751 \n",
      "[MiniBatchKMeans] Reassigning 50 cluster centers.\n",
      "Minibatch iteration 90/12715000: mean batch inertia: 0.219034, ewa inertia: 0.193771 \n",
      "Minibatch iteration 91/12715000: mean batch inertia: 0.186637, ewa inertia: 0.193765 \n",
      "Minibatch iteration 92/12715000: mean batch inertia: 0.254698, ewa inertia: 0.193813 \n",
      "Minibatch iteration 93/12715000: mean batch inertia: 0.114522, ewa inertia: 0.193751 \n",
      "Minibatch iteration 94/12715000: mean batch inertia: 0.163656, ewa inertia: 0.193727 \n",
      "Minibatch iteration 95/12715000: mean batch inertia: 0.169791, ewa inertia: 0.193708 \n",
      "Minibatch iteration 96/12715000: mean batch inertia: 0.179497, ewa inertia: 0.193697 \n",
      "Minibatch iteration 97/12715000: mean batch inertia: 0.231148, ewa inertia: 0.193727 \n",
      "Minibatch iteration 98/12715000: mean batch inertia: 0.264900, ewa inertia: 0.193783 \n",
      "[MiniBatchKMeans] Reassigning 50 cluster centers.\n",
      "Minibatch iteration 99/12715000: mean batch inertia: 0.280796, ewa inertia: 0.193851 \n",
      "Minibatch iteration 100/12715000: mean batch inertia: 0.177877, ewa inertia: 0.193838 \n",
      "Minibatch iteration 101/12715000: mean batch inertia: 0.141065, ewa inertia: 0.193797 \n",
      "Minibatch iteration 102/12715000: mean batch inertia: 0.209963, ewa inertia: 0.193810 \n",
      "Converged (lack of improvement in inertia) at iteration 102/12715000\n",
      "Computing label assignment and total inertia\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "MiniBatchKMeans(batch_size=100, compute_labels=True, init='k-means++',\n",
       "        init_size=5000, max_iter=5000, max_no_improvement=100,\n",
       "        n_clusters=1000, n_init=3, random_state=None,\n",
       "        reassignment_ratio=0.3, tol=0.0, verbose=1)"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cluster = MiniBatchKMeans(n_clusters=1000, init_size=5000, verbose=1, max_iter=5000, \n",
    "                          max_no_improvement=100, reassignment_ratio=0.3)\n",
    "cluster.fit(X_svd)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Метки кластеров для всех объектов в датасете лежат в cluster.labels_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [],
   "source": [
    "labels = cluster.labels_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Давайте попробуем посчитать метрики "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Silhouette Coefficient: 0.105\n"
     ]
    }
   ],
   "source": [
    "print(\"Silhouette Coefficient: %0.3f\"\n",
    "      % metrics.silhouette_score(X[:10000], labels[:10000]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Homogeneity: 0.561\n",
      "Completeness: 0.293\n",
      "V-measure: 0.385\n",
      "Adjusted Rand Index: 0.020\n",
      "Adjusted Mutual Information: 0.283\n"
     ]
    }
   ],
   "source": [
    "# эти три метрки что-то вроде точности, полноты и ф-меры для кластеризации\n",
    "print(\"Homogeneity: %0.3f\" % metrics.homogeneity_score(y, labels)) # проверяет, что в кластере объекты одного класса\n",
    "print(\"Completeness: %0.3f\" % metrics.completeness_score(y, labels)) # проверяет, что объекты класса только в одном кластере\n",
    "print(\"V-measure: %0.3f\" % metrics.v_measure_score(y, labels)) # превращает обе метрики в одну \n",
    "\n",
    "print(\"Adjusted Rand Index: %0.3f\"\n",
    "      % metrics.adjusted_rand_score(y, labels))\n",
    "print(\"Adjusted Mutual Information: %0.3f\"\n",
    "      % metrics.adjusted_mutual_info_score(y, labels))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Как найти отптимальное количество кластеров?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Такой вопрос часто задают на собеседованиях. Правильный ответ - методом локтя. Нужно перебрать разные значения количества кластеров и посчитать какую-то метрику. Затем нарисовать график или просто посмотреть на числа - оптимально выбрать число кластеров, после которого метрика перестала улучшаться (или даже стала ухудшаться). На графике это выглядит как локоть, поэтому так и называется"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [],
   "source": [
    "from tqdm import tqdm\n",
    "import numpy as np\n",
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [],
   "source": [
    "sample = data.sample(frac=0.1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(25422, 2)"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sample.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [],
   "source": [
    "cv = CountVectorizer(max_features=1000)\n",
    "svd = TruncatedSVD(50)\n",
    "X = cv.fit_transform(sample['title'])\n",
    "X_svd = svd.fit_transform(X)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(25422, 1000)"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 60/60 [06:32<00:00,  6.54s/it]\n"
     ]
    }
   ],
   "source": [
    "scores = []\n",
    "# tqdm._instances.clear()\n",
    "for i in tqdm(range(5, 3000, 50)):\n",
    "    cluster = MiniBatchKMeans(n_clusters=i, init_size=i*3)\n",
    "    cluster.fit(X)\n",
    "    # силуэты считать на всех данных считать долго\n",
    "    # можно взять внутреннюю метрику кминса\n",
    "    # она большая, поэтому можно взять корень\n",
    "    scores.append(np.sqrt(cluster.inertia_))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x140f8ab00>]"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAsYAAAEvCAYAAABGywdiAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8li6FKAAAgAElEQVR4nOzdd3Rc1bn+8e/WjIrVrV4sW7It9265YVOM6RgMFwgdQocQQhKS3JDkJuHmJr+EhBBIQg099EACpsVgio1xQe5dki0XWVavVtdo//7Q2BFGVpdG0jyftWbpaJ9zZl77LGk9Pt7n3cZai4iIiIiIt/PxdAEiIiIiIv2BgrGIiIiICArGIiIiIiKAgrGIiIiICKBgLCIiIiICKBiLiIiIiADg9HQBAFFRUTY5OdnTZYiIiIjIILd+/foia210a/v6RTBOTk4mPT3d02WIiIiIyCBnjNl/on3tTqUwxiQZYz4xxuwwxmw3xtztHv+9MWaXMWaLMeafxpjwFufca4zJMsbsNsac3TN/DBERERGR3tOROcaNwD3W2gnAXOBOY8wE4ENgkrV2CpAB3Avg3ncFMBE4B3jEGOPojeJFRERERHpKu8HYWnvYWrvBvV0J7AQSrbXLrLWN7sPWAMPc20uAV6y1ddbabCALmN3zpYuIiIiI9JxOdaUwxiQD04G1x+26EXjfvZ0IHGyxL8c9JiIiIiLSb3U4GBtjgoE3gO9aaytajP+U5ukWL3bmg40xtxpj0o0x6YWFhZ05VURERESkx3UoGBtjfGkOxS9aa99sMf5NYDFwtbXWuocPAUktTh/mHvsKa+0T1to0a21adHSrHTNERERERPpMR7pSGOApYKe19o8txs8BfgRcaK2tbnHK28AVxhh/Y0wKkAqs69myRURERER6Vkf6GM8HrgW2GmM2ucd+AjwM+AMfNmdn1lhrb7fWbjfGvAbsoHmKxZ3WWlfPly4iIiIi0nPaDcbW2s8B08qu99o459fAr7tRl4iIiIhIn+pUV4rBpKK2gVe/PMDewiOeLkVERERE+gGvDcY19S7++42trMoq8nQpIiIiItIPeG0wjgnxZ4ivg+yi6vYPFhEREZFBz2uDsTGGEZGB7Cuu8nQpIiIiItIPeG0wBkiJCmJfkYKxiIiIiHh5ME6OCuJgaTWNriZPlyIiIiIiHubdwTgykAaXJbes1tOliIiIiIiHeXkwDgIgW/OMRURERLyeVwfjlKjmYLxfwVhERETE63l1MI4O8SfQz0G2HsATERER8XpeHYybW7apM4WIiIiIeHkwBkiJCmRfsRb5EBEREfF2Xh+MkyODOFiilm0iIiIi3k7BODKIxibLobIaT5ciIiIiIh6kYOzuTKEH8ERERES8m4JxVCAA+zXPWERERMSreX0wjg72J0gt20RERES8ntcH42Mt27TIh4iIiIhX8/pgDM0r4KmXsYiIiIh3UzCmeZ5xTmkNDWrZJiIiIuK1FIyBEUdbtpWqZZuIiIiIt1IwpnkqBUC25hmLiIiIeC0FY5oX+QDYr3nGIiIiIl5LwRiICvYjyM/BPvUyFhEREfFaCsY0t2xLjgpSL2MRERERL6Zg7JYcpV7GIiIiIt5MwdgtJTJILdtEREREvJiCsduIyEBcTZYctWwTERER8UoKxm5HW7ZpBTwRERER76Rg7JZ8NBhrnrGIiIiIV1IwdosM8iPY36k7xiIiIiJeSsHYrbllWyDZ6mUsIiIi4pUUjFtIjgzSHWMRERERL6Vg3EJyZBA5pdXUN6plm4iIiIi3aTcYG2OSjDGfGGN2GGO2G2Pudo9HGGM+NMZkur8OdY8bY8zDxpgsY8wWY8yM3v5D9JTkqCCaLOSUajqFiIiIiLfpyB3jRuAea+0EYC5wpzFmAvBjYLm1NhVY7v4e4Fwg1f26FXi0x6vuJSlRgYA6U4iIiIh4o3aDsbX2sLV2g3u7EtgJJAJLgOfchz0HXOTeXgI8b5utAcKNMfE9XnkvSI482stYd4xFREREvE2n5hgbY5KB6cBaINZae9i9Kw+IdW8nAgdbnJbjHuv3IoL8CPF36o6xiIiIiBfqcDA2xgQDbwDftdZWtNxnrbWA7cwHG2NuNcakG2PSCwsLO3Nqr2lu2RZEtjpTiIiIiHidDgVjY4wvzaH4RWvtm+7h/KNTJNxfC9zjh4CkFqcPc499hbX2CWttmrU2LTo6uqv197jkqCDdMRYRERHxQh3pSmGAp4Cd1to/ttj1NnC9e/t64K0W49e5u1PMBcpbTLno95IjAzlUWqOWbSIiIiJextmBY+YD1wJbjTGb3GM/AX4LvGaMuQnYD3zDve894DwgC6gGbujRintZcmRzy7aDpdWMig72dDkiIiIi0kfaDcbW2s8Bc4Ldi1o53gJ3drMuj0mOOtqZokrBWERERMSLaOW746S4g7EewBMRERHxLgrGxxka6EtIgJP9xeplLCIiIuJNFIyPY4whRZ0pRERERLyOgnErkiPVy1hERETE2ygYtyI5MpDcshrqGl2eLkVERERE+oiCcSuSo9wt20pqPF2KiIiIiPQRBeNWtGzZJiIiIiLeQcG4FcmR7mCsB/BEREREvIaCcSuGBvoSGuBUMBYRERHxIgrGrTjWsq1IvYxFREREvIWC8QkkR6llm4iIiIg3UTA+gRGRQeSWq2WbiIiIiLdQMD6BlKhArIWDJZpOISIiIuINFIxP4GhnimzNMxYRERHxCgrGJ3CsZZvmGYuIiIh4BQXjExga5EfYEF+1bBMRERHxEgrGbUiOClIwFhEREfESCsZtSIkMVC9jERERES+hYNyGoy3bahvUsk1ERERksFMwbkNKVJBatomIiIh4CQXjNiRHHW3ZpnnGIiIiIoOdgnEbkiMDAfQAnoiIiIgXUDBuQ3igH+GBvuwr1lQKERERkcFOwbgdyZFBWuRDRERExAsoGLcjOTJQwVhERETECygYtyM5Kojc8lq1bBMREREZ5BSM25Hi7kxxQC3bRERERAY1BeN2JEeqZZuIiIiIN1AwbsfRYKx5xiIiIiKDm4JxO8ICfRka6MvqvcVsO1SuucYiIiIig5TT0wUMBDNHRPDRznw+3V2Iw8cwMiqIcfGhjIsLaX7Fh5IQFoAxxtOlioiIiEgXKRh3wOPXziS7qIpdeRXszqtk5+FKNh4oZenm3GPHhAQ4GR8XyrTh4VwzZwTD3avmiYiIiMjAYKy1nq6BtLQ0m56e7ukyOq2ytoGM/OagvCuvgl2HK9mcU4aryXLe5HhuP3UUkxLDPF2miIiIiLgZY9Zba9Na26c7xt0QEuDLzBERzBwRcWwsv6KWp1dl89KaA7yz5TALRkdx+6mjmD86UlMtRERERPox3THuJRW1Dby09gBPf55NQWUdExNCue3UUZw3KQ6nQ888ioiIiHhCW3eM201oxpinjTEFxphtLcamGWPWGGM2GWPSjTGz3ePGGPOwMSbLGLPFGDOj5/4YA0togC+3nzqKlf+9kN9dMpmaBhffeXkjCx/4lOdX76OmXt0tRERERPqTjty6fBY457ix+4H7rLXTgJ+7vwc4F0h1v24FHu2ZMgcuf6eDy2cN56Pvncrj184kKtifn7+1nfm/+5hPdhd4ujwRERERcWs3GFtrVwAlxw8Doe7tMOBoe4YlwPO22Rog3BgT31PFDmQ+PoazJ8bx5h0n8frt84gLDeCW59J5a9MhT5cmIiIiInR9gY/vAr83xhwE/gDc6x5PBA62OC7HPSZuxhhmJUfw6m1zmTliKN99dRMvrN7n6bJEREREvF5Xg/EdwPestUnA94CnOvsGxphb3fOT0wsLC7tYxsAVEuDLczfOZtG4GP7nre38eXkm/eFBSBERERFv1dVgfD3wpnv7dWC2e/sQkNTiuGHusa+x1j5hrU2z1qZFR0d3sYyBLcDXwaPXzOS/pifywIcZ/OqdnTQ1KRyLiIiIeEJXg3EucKp7+3Qg0739NnCduzvFXKDcWnu4mzUOar4OH/5w2VS+eVIyT6/K5of/2EKjq8nTZYmIiIh4nXYX+DDGvAycBkQZY3KAXwC3AA8ZY5xALc0dKADeA84DsoBq4IZeqHnQ8fEx/OKCCQwN9OPBjzKoqG3gz1dOJ8DX4enSRERERLyGFvjoZ577Yh+/eHs7c0dG8OR1aYQE+Hq6JBEREZFBo1sLfEjfuv6kZB66Yhrp+0q56sm1FB+p83RJIiIiIl5BwbgfWjItkSeum0lGfiWXPb6aQ2U1ni5JREREZNBTMO6nTh8Xyws3zaGwoo7LHv2CvYVHPF2SiIiIyKCmYNyPzU6J4OVb51Lb2MQ3Hl/NzsMVni5JREREZNBSMO7nJiWG8dpt83D6+HD546vZcKDU0yWJiIiIDEoKxgPA6JhgXr99HhFBflzzt7WsyirydEkiIiIig46C8QCRFBHIa7fPI2loIDc88yXLtud5uiQRERGRQUXBeACJCQng1dvmMj4hlDte3MA/N+Z4uiQRERGRQUPBeIAJD/TjxZvnMDs5gu+9upkXVu/zdEkiIiIig4KC8QAU7O/kmRtmccb4GP7nre088mmWp0sSERERGfAUjAeoAF8Hj14zkyXTErj/g9389v1d9IflvUVEREQGKqenC5Cu83X48OA3phHs7+Sxz/ZQ2+DilxdO9HRZIiIiIgOS7hgPcD4+hv+7aBJXzxnOs1/s42BJtadLEhERERmQFIwHAWMMt586CoB3thz2cDUiIiIiA5OC8SCRFBHI1KRw3tmS6+lSRERERAYkBeNB5IIp8WzPrSC7qMrTpYiIiIgMOArGg8j5U+IBeGez7hqLiIiIdJaC8SASHzaEWclDNc9YREREpAsUjAeZxVMS2J1fSWZ+padLERERERlQFIwHmXMnx+FjYKnuGouIiIh0ioLxIBMTEsCclEje2Zzb7ZXw1u4tVl9kERER8RoKxoPQ4qnx7C2qYsfhii6/R155Ldc+tY6f/WtbD1YmIiIi0n8pGA9C506Kx+FjuvUQ3hMr9lLvauLzrCKKj9T1YHUiIiIi/ZOC8SAUEeTH/NFRvLOla9Mpio7U8dK6/UwfHo6ryfL+trxeqFJERESkf1EwHqQWT4nnYEkNW3LKO33u31ZmU9fYxB8um8romGDeVl9kERER8QIKxoPU2RPi8HWYTi8RXVpVzwur97F4SgKjooO5cGoCX+4r4XB5Te8UKiIiItJPKBgPUmGBvpySGs27Ww7T1NTx6RTPrMqmqt7FnQtHAXDB1ASshXfV/k1EREQGOQXjQWzx1Hhyy2vZeLC0Q8dX1DbwzBf7OHtiLOPiQgFIiQpicmIYSzWdQkRERAY5BeNB7Izxsfg5fVi6uWN3e5//Yh+VtY3cdXrqV8YvmBrP5pxy9hVV9UaZIiIiIv2CgvEgFhLgy8Kx0by79TCudqZTVNU18tTn2SwcG82kxLCv7Fs8JQGg0/OVRURERAYSBeNBbvGUBAor61iXXdLmcS+u3U9pdQN3LUr92r6E8CHMSh6q7hQiIiIyqCkYD3KLxscwxNfR5t3e2gYXT6zIZsHoKGYMH9rqMRdOTSAj/wi78yp7q1QRERERj1IwHuQC/ZwsGh/DB9vyaHQ1tXrMK+sOUHSkjm+fPvqE73Pu5Hh8DLy9+VBvlSoiIiLiUQrGXmDxlASKq+pZvbf4a/vqGl089tleZidHMHdk5AnfIyrYn/mjo1i6+XCXVtMTERER6e/aDcbGmKeNMQXGmG3Hjd9ljNlljNlujLm/xfi9xpgsY8xuY8zZvVG0dM5pY6MJ9nfyTivdKf6xPoe8ilruWnTiu8VHXTA1gQMl1Wzuwmp6IiIiIv1dR+4YPwuc03LAGLMQWAJMtdZOBP7gHp8AXAFMdJ/ziDHG0ZMFS+cF+Do4c0IsH2zPo77xP9MpGlxNPPrpHqYlhbNgdFS773P2xDj8HD7qaSwiIiKDUrvB2Fq7Aji+pcEdwG+ttXXuYwrc40uAV6y1ddbabCALmN2D9UoXLZ4ST3lNA6uyio6N/WvjIXJKa7jr9NEYY9p9j7Ahvpw6Npp3tuS22/6tNVtzyjn/4ZUcKK7u9LkiIiIiva2rc4zHACcbY9YaYz4zxsxyjycCB1scl+MeEw87OTWa0ADnsbu9ribLI5/uYWJCKKePi+nw+1wwNYH8ijq+3Nd2+7fjHalr5K6XN7A9t4J/rD/Y/gkiIiIifayrwdgJRABzgR8Cr5mO3HJswRhzqzEm3RiTXlhY2MUypKP8nD6cPTGOZTvyqW1w8c6WXLKLqjp8t/ioM9zt3zrb0/gXb23nQEk1wyMCeWeLHuATERGR/qerwTgHeNM2Wwc0AVHAISCpxXHD3GNfY619wlqbZq1Ni46O7mIZ0hkXTE3gSF0jn+4u4K+fZDEmNpizJsR16j0C/ZycMSGW97cepuEE7d+O99amQ7yxIYdvLxzNHaeNYm9RFdtzK7ryRxARERHpNV0Nxv8CFgIYY8YAfkAR8DZwhTHG3xiTAqQC63qiUOm+k0ZFEhHkx/8u3UFG/hHuXDgaH59O3egH4IIp8ZRWN/B5i/nKJ3KwpJqf/XMbM4aH851FqZwzMQ6nj+GdLV/vkCEiIiLiSR1p1/YysBoYa4zJMcbcBDwNjHS3cHsFuN5993g78BqwA/gAuNNa6+q98qUznA4fzpkUR255LSlRQSyektCl9zl1bDQhLeYrn0ijq4m7X9kIwENXTMfp8GFokB8LUqNYujlX0ylERESkX+lIV4orrbXx1lpfa+0wa+1T1tp6a+011tpJ1toZ1tqPWxz/a2vtKGvtWGvt+71bvnTWRdOan4X89sLROLpwtxjA3+ngnIlxLNvePF/5RB7+OIsNB8r4v4snkRQReGx88ZQEDpXVsPFgWZc+X0RERKQ3aOU7LzM7JYLl95zKf83oXrOQC6f9Z75ya9Zll/CXjzO5ZMYwlkz76medNTEWP4dPqwuOiIiIiHiKgrEXGhUd3KlOFK2ZNzKSqGA/lrYSbsurG/juKxsZHhHIfUsmfm1/aEBzP+R3t+bS1IV+yCIiIiK9QcFYusTp8OG8yfF8tDOfI3WNx8attdz7zy0UVNbx0BXTCfZ3tnp+V/shi4iIiPQWBWPpsgumJlDX2MRHO/KPjb2WfpD3tuZxz1ljmZoUfsJzF42LIcDXh6VbtLy0iIiI9A8KxtJlM4cPJT4s4NhiH1kFR/jl2zs4aVQkt50yss1zg/ydLBofy/tb82jsYD9kERERkd6kYCxd5uNjuGBqAisyCimoqOXuVzYS4OvDg5dP61B/5AumJFBcVc/qvcV9UK2IiIhI2xSMpVsumJJAY5Plqr+tZXtuBfdfOpXY0IAOnXva2GiC/Z3qTiEiIiL9goKxdMukxFBSooLIKjjCtXNHcOaE2A6fG+Dr4KwJsby/7TD1jZpOISIiIp6lYCzdYozh5pNTWDA6ip+eP77T5y+eGk9FbSMrMwt7oToRERGRjlMwlm67es4I/n7zHAJ8HZ0+d8HoaMKG+PLOFk2nEBEREc9SMBaP8nP6uJeXzmtzeWkRERGR3qZgLB53wdQEqupdJ1xeWkRERKQvKBiLx80dGUFkUOvLS4uIiIj0FQVj8bijy0sv35VPVYvlpUVERET6koKx9AsXTE2gtqGJj3bmt3+wiIiISC9weroAEYC0EUOJCw1g6ebDLJmW6OlyuszVZDlYUs2uvEoy8ivZnVfJ7vxKyqobuGlBCjfMT+5S9w4RERHpfQrG0i/4+BjOnxLPC6v3U17TQNgQX0+X1K7aBhdf7itpDr/uAJyRX0ltw38WKxkeEciY2BDqw5v43Qe7eGndfn5y7njOmRSHMe0vmy0iIiJ9R8FY+o3FU+J56vNslm3P47K0JE+X06YGVxNXPrmGjQfKAIgK9mdcXAhXzR7BuLgQxsSFkBoTTJD/f37EPs8s4lfv7OCOFzcwOyWCny+ewKTEME/9EUREROQ4CsbSb0xLCmfY0CG8s+Vwvw/GDyzLYOOBMn510STOmxRHZLB/u+csSI3i3e8s4NX0gzywLIML/vI5l80cxg/OGktMaEAfVC0iIiJt0cN30m8YY1g8JYHPs4ooqar3dDkntCKjkMc+28OVs4dz7dwRHQrFRzkdPlw9ZwSf/OA0bjl5JP/ceIiFf/iUv36SpQVOREREPEzBWPqVC6bG42qyfLAtz9OltKqwso7vv7aZMbHB/HzxhC6/T9gQX35y3ng+/N6pzB8dxe//vZtFD3zGO1tysdb2YMUiIiLSUQrG0q9MiA9lZFQQSzfnerqUr2lqsnz/tU1U1jbwl6tmMMSv+90lkqOCeOK6NF66eQ4hAU6+/dJGnvtiX/eLFRERkU7THGPpV4wxLJ6awJ8/zqSgopaY0ADqGl0UVNSRX1FLXkUteeW17u068strCQ5wcvmsJBaNi8Hp6L1/6z25ci8rM4v49cWTGBMb0qPvfdLoKN79zslc+tgXvLBmP9eflKyuFSIiIn1MwVj6nQumxPPw8kwufuQLahpcrc439nf6EBcWQGxoADsPV3DbC+uJDwvgqtnDuXx2EjEhPfsw26aDZfz+37s5d1IcV80e3qPvfZTDx3B5WhI/fnMrGw+WMWP40F75HBEREWmdgrH0O6mxIVw3bwQ5pTXEhgYQFxpAXJh/83ZY8/dhQ3yP3VFtdDWxfFcBf1+znwc+zOCh5ZmcMymOa+aOYE5KRLfvvFbUNnDXyxuIDQ3gt/81pVfv5J4/JZ77lu7g9fSDCsYiIiJ9zPSHB33S0tJsenq6p8uQQWBv4RFeXHuA19MPUlHbSGpMMNfOG8HF0xMJCej8oiHWWr7zyibe23qY126bx8wRvR9Wv//aJpZtz+fLn57RI/OYRURE5D+MMeuttWmt7dPDdzKojIwO5n8WT2DtT87g/kum4O/rw8/f2s7c3yznp//cSmZ+Zafe7/X0HJZuzuX7Z47pk1AMcNnMJI7UNfLB9sN98nkiIiLSTHeMZVCz1rI5p5wXVu9n6ZZc6hubODk1ihvmJ3PamBh8fE48LSKroJIL/ryKGSPCef7GOTjaOLYnNTVZTvvDpwwbOoSXbpnbrfdK31fC7z7YxbyRkZw1MY6JCaF6qE9ERLxaW3eMFYzFaxQfqePldQd4Yc1+8ivqSIkK4vp5I7g0LYlg/69Ot69tcHHRX1dRWFnH+3ef3Ocr0z28PJM/fpjByh8tJCkisEvvYa3l4ke+YHdeJXWNLposJIYP4cwJsZw1MZbZyRG92sVDRESkP1IwFmmhwdXE+9vyePrzbDYdLCPE38llaUl886Rkhkc2h9Cfv7WN51fv55kbZrFwbEyf13iorIYFv/uY75yeyvfOHNOl91iRUch1T6/j1xdP4txJ8Szfmc+yHfmsyCikrrGJ8EBfTh8Xw9kT4zglNVrzmUVExCsoGIucwMYDpTz7xT7e3XIYl7UsGhfL9OHh/P7fu7l5QQo/68bqdt11zd/Wkl1UxcofLWxzykdrrLVc+thqcstq+PSHp+Hv/E/ora5vZEVGEct25LF8ZwHlNQ0E+Ppwcmo0t54yklnJET39RxEREek3FIxF2pFfUcvf1+znxbUHKKmqZ3JiGG/ccRJ+Ts9NNXhr0yHufmUTL908h5NGR3Xq3FVZRVz9t7X8aslErp2XfMLjGlxNfLmvhGXb83l362EKK+u4aFoC9543ntg+nj4iIiLSFxSMRTqotsHFx7sKSBsxtM/nFbdWy6xff8SicTH86YrpnTr3G4+vZn9xFZ/9cCEBvh2bIlFd38gjn+zhiRV78XUY7lqUyo3zUzz6jwMREZGepnZtIh0U4OvgvMnxHg/FR2u5cGoC72/Lo6K2ocPnrd5TzLrsEu44dVSHQzFAoJ+TH5w9lg+/fwrzRkXy2/d3cc6fVvBZRmFXyhcRERlwFIxF+rFvpCVR19jEO5s73tP44eWZRIf4c0UXl64eERnE366fxTM3zMIC1z+9jlueT+dAcXWX3k9ERGSgaDcYG2OeNsYUGGO2tbLvHmOMNcZEub83xpiHjTFZxpgtxpgZvVG0iLeYMiyMMbHBvL7+YIeOX5ddwuq9xdzeybvFrVk4NoYPvnsyPzpnLKuyijjjwc/447Ld1NS7uvW+IiIi/VVH7hg/C5xz/KAxJgk4CzjQYvhcINX9uhV4tPslingvYwyXzUxi44EysgraX7Xv4eWZRAX7c1UX7xYfz9/p4Funjebje07jnIlxPPxxFmf88TNWZRX1yPuLiIj0J+0GY2vtCqCklV0PAj8CWj69twR43jZbA4QbY+J7pFIRL3XR9EQcPobX03PaPG79/hI+zyritlNG9nhP4riwAB6+cjqv3joXf6cPd7+yidoG3TkWEZHBpUtzjI0xS4BD1trNx+1KBFr+n2+Oe0xEuig6xJ/Tx8Xw5sZDNLqaTnjcQ8uziAjy4+q5PXO3uDVzRkby64snU3Skjle/7Nj0DhERkYGi08HYGBMI/AT4eXc+2BhzqzEm3RiTXliop95F2nLZzGEUVtadsEPExgOlrMgo5JaTRxLo52z1mJ4yd2QEaSOG8vhne6hvPHFQFxERGWi6csd4FJACbDbG7AOGARuMMXHAISCpxbHD3GNfY619wlqbZq1Ni46O7kIZIt5j4bgYooL9eC299bu0Dy/PZGigL9fNG9HrtRhjuPP00eSW1/Kvja3+eIuIiAxInQ7G1tqt1toYa22ytTaZ5ukSM6y1ecDbwHXu7hRzgXJrbcf7TIlIq3wdPlw8PZHlOwsoPlL3lX1bcsr4ZHchN588kiD/3r1bfNRpY6KZlBjKo5/twdXUd4sEvbvlMMt35vfZ54mIiHfpSLu2l4HVwFhjTI4x5qY2Dn8P2AtkAU8C3+qRKkWEy9KSaGyy/GtT7lfGH16eSdiQvrlbfJQxhjtPG012URXvbu2bf/vuL67iu69u5Kbn0nlmVXaffKaIiHiXjnSluNJaG2+t9bXWDrPWPnXc/mRrbZF721pr77TWjrLWTrbWap1nkR4yJjaEqcPCeD39IEeXct92qJyPdhZw04IUQgJ8+7SesyfGMTommEc+yaKpD+4a3//BbnwdPiwcG819S3fw4IcZx/4eREREeoJWvhMZQC5NS8GShzUAACAASURBVGJXXiXbDlUA8OePMwkJcPLN+cl9XouPj+Fbp41iV14ly3cV9OpnbThQyrtbD3PrKSN58ro0Lp05jIeWZ3Lf0h19EspFRMQ7KBiLDCAXTk3A3+nD6+sPsvNwBf/ens+N81MI7eO7xS3rSYoYwl8+yeq1u7fWWn7z7k6iQ/y55eSROB0+3H/JFG5ekMKzX+zjntc309BGGzsREZGOUjAWGUDChvhy9sQ43tqUywPLdhPi7+TG+Skeq8fp8OH2U0ex+WAZq7KKe+Uz/r09j/T9pXz/zDHHHi708TH89Pzx/PDssfxz4yFuf2G9FhwREZFuUzAWGWAuSxtGeU0DH+0s4JvzkwkL9Mzd4qMunTmM2FB//vJJZo+/d4Orid99sJvUmGAumznsK/uMMdy5cDS/umgSH+8u4Lqn1lFR29DjNYiIiPdQMBYZYE4aFUVi+BCC/BzctMBzd4uP8nc6uOXkkazZW8L6/a2tHt91L609QHZRFfeeNw6no/VfV9fOHcFDV0xnw4FSrnh8DYWVda0eJyIi0h4FY5EBxuFj+MNlU/nL1TMID/TzdDkAXDVnOBFBfvzl46wee8+K2gYeWp7JvJGRLBwb0+axF05N4G/Xp7G36AjfeHw1OaXVPVaHiIh4DwVjkQFo3qj2w2JfCvRzcuP8ZD7ZXci2Q+U98p6PfbqHkqp6fnLeeIwx7R5/2tgY/n7THIqP1HHpo6vJzK/skTpERMR7KBiLSI+47qRkQgKcPPJp9+8a55bV8NTn2Vw0LYHJw8I6fF5acgSv3jaPxibLFU+s4XB5TbdrERER76FgLCI9IjTAl+vnJfP+tjyyCrp3t/aBZRlY4Adnj+30uePjQ3nl1jnUNLj47iub+nTJahERGdgUjEWkx9y4IIUAp4NHPt3T5ffYkVvBmxtzuOGkZIYNDezSe4yOCeFXSyaxNrukx+Y9/2N9Duuye/bhQhER6V8UjEWkx0QE+XHVnOG8tSmXA8VdewDu/72/k7Ahvnxr4ehu1XLJzGH81/REHlqewdq93eux/Pzqffzg9c3c+OyXZBdVdeu9RESk/1IwFpEedespI3EYw2MrOn/X+LOMQlZmFnHX6amEDel+f+b/vWgSwyMCufuVTZRW1XfpPT7Ylscv3t7OyalROB2Gb724oc8XE7HW9trKgiIi8h8KxiLSo2JDA7g0bRj/SM8hr7y2w+e5miz/772dDI8I5Nq5I3qklmB/J3+5agbFVXX88B+bOx0u0/eVcPcrG5mWFM4T16bx4DemsfNwBfct3d4j9XXExgOlLPjdJ8z5zXJ+8Ppmlm7O7XLIFxGRtikYi0iPu+PUUbis5cmVezt8zhsbctiVV8mPzhmLn7PnfjVNSgzj3nPH89HOAp77Yl+Hz8sqOMJNz6WTED6Ep66fxRA/BwvHxXDHaaN4ed1B/rkxp8dqPJE3N+Rw+RNr8PGB2SkRfLQzn7te3siM//uQi/66igc/zGD9/lI9YCgi0kOcni5ARAafpIhAlkxN4JlV2Xyxp5hpSWFMHRbO1KRwUmOCv7aKXU29iweW7WZaUjjnT47v8XpumJ/MqqwifvPeLtKSI5iU2HYLuIKKWq5/eh2+DsNzN8wmIug/C6ncc+YY1u8r5SdvbmNSQhipsSE9Xq+ryfK7D3bxxIq9zBsZySNXz2BokB+uJsuWnDI+yyjks4xC/vxxJg8tzyRsiC8LUqM4NTWa08ZGExMa0OM1iYh4A9Mf5q2lpaXZ9PR0T5chIj2ovLqBp1Zls+lgGZsPllFe0wDAEF8HkxPDmJoUxpRh4UxLCudfGw/xwIcZvH77PGYlR/RKPSVV9Zz30EqG+DlYetcCgv1bvy9wpK6Ryx9fTXZRFa/eOq/VPsr5FbWc99BKIoL8eOvb8wn067l7DOU1DXzn5Y18llHIdfNG8D+LJ+B7guWwy6rr+TyriM92Nwflgso6jIHZyRFcMDWB8ybHfyXUi4gIGGPWW2vTWt2nYCwivc1ay/7iajbnlB0LyttyK6hvbDp2zFkTYnniulZ/T/WYNXuLuerJNVw0PZE/fmPa1/bXNzZx03Nf8sWeYp66Po3T2lhd8PPMIq59ei0XT0/kgcumdmh1vvbsLTzCzc+nc6C4mv9dMomr5gzv8LnWWnblVfLv7Xm8vTmXvYVVOHwMC0ZHccHUBM6aGEtoQPcfaBQRGegUjEWk32lwNbE7r5JNB8vIKjjCLaeMJDF8SK9/7oMfZvDQ8kz++I2p/NeMYcfGrbXc8/pm3txwiN9fOoXL0pLafa8/fZTBnz7K5P5LpvCNWe0f35bPMgr59ksb8HX48OjVM5gzMrLL72WtZefhSt7enMvSzbkcKqvBz+nDwrHRXDA1gUXjYhni5+hWvSIiA5WCsYiIW6Oriav+tpZth8p5564FjIwOBuD3/97FXz/Zw/fPHMN3FqV26L1cTZbrn17Hl/tK+Ned8xkfH9rpeqy1PPV5Nr95bydjYkN48ro0kiK6trDJid5/48Ey3t6Uy7tbD1NYWUegn4NF42M5OTWKeSMje/TzRET6OwVjEZEWDpfXcO5DK0kMH8Kb3zqJ19Nz+Nm/tnHl7OH85uJJnZoWUVhZx/kPryTI38nb355PSCemK9Q2uPjpP7fxxoYczp0Uxx8um0rQCeY+9wRXk2VtdjFLNx/m39vzKHG3fUsMH8LckZHMHRnBXAVlERnkFIxFRI7z0Y58bn4+nfmjI1m9p5jTx8Xw2DUzv9YxoyPW7i3myifXcN7keP585fR2g3VuWQ2r9xTz/Op9bM4p57tnpPKd01Px8en+POWOamqyZBYcYc3e4mOv0urmBySPD8rDhg7pkTnUIiL9gYKxiEgr7lu6nWdW7WNqUjgv3zKnW90lHvk0i/s/2M2vLpr0tQVKCivrWL23mNV7ili9p5h97uWyI4P8+L+LJnFuL7So66y2grKvwzA00K/5FeRLRJAf4YF+RAT6MTTIj4ggX8ID/UiNCWbYUN1tFpH+TcFYRKQVdY0uXkvP4fweaGvW1GS56bkvWZVVzDM3zKKytpHVe4r4Yk8xmQVHAAjxdzJnZATzRjXP7R0XF9Knd4k742hQXptdTG5ZLWXV9ZRU1VNaXU9pdQOl7u2Wa4sYA+dOiuP2U0cxZVi454oXEWmDgrGISB8orarn/IdXkuteCnuIr4NZKRHMGxnJSaMimZgQ2qWpGv1VU5OlsraREndoXr4znxfW7KeytpGTRkVy+6mjODk1StMwRKRfUTAWEekju/Iq+HhXAbOTI5gyLLxHl7ceCCprG3h53QGe+jyb/Io6JsSHctupIzl/cvyg+keBiAxcCsYiItKn6hpdvLUpl8c/28OewiqSIoZwy8kjuWxmknooi4hHKRiLiIhHNDVZPtqZz2Of7WHDgTIigvy4bOYw/H0dVNU1Ul3fyJE6F1V1jRypa6Tq6KveRU29i9TYYM4YH8vp42IYFxeiaRki0m0KxiIi4lHWWtL3l/LYp3tYvqsAgCA/B0H+ToL9nQT6Owjya94O8ncS5O/Az+HDxoNlbMkpByAhLIDTx8ewaFws80ZFEuCrO88i0nkKxiIi0m/UNbrw9fHpcEeOgopaPtldwPKdBazMLKKmwcUQXwfzR0exaHwMp4+LITY0oJerFpHBQsFYREQGhdoGF2v2FvPxruagfKisBoDzJ8fz8JXTcfTT9nci0n+0FYx7b+1RERGRHhbg6+C0sTGcNjaG+y60ZOQf4c0NOTy+Yi9JEYH8+Nxxni5RRAYwBWMRERmQjDGMjQvh3vPGU1XfyGOf7WFSYiiLpyR4ujQRGaDUVFJERAa8ny+eyMwRQ/nh61vYlVfh6XJEZIBSMBYRkQHPz+nDo1fPICTAyW0vrKe8usHTJYnIANRuMDbGPG2MKTDGbGsx9ntjzC5jzBZjzD+NMeEt9t1rjMkyxuw2xpzdW4WLiIi0FBMawKPXzCC3rIa7X92Iq8nzD5eLyMDSkTvGzwLnHDf2ITDJWjsFyADuBTDGTACuACa6z3nEGKNGkyIi0idmjojglxdO5NPdhfzpowxPlyMiA0y7wdhauwIoOW5smbW20f3tGmCYe3sJ8Iq1ts5amw1kAbN7sF4REZE2XTV7OJenJfHnj7P4YFuep8sRkQGkJ+YY3wi8795OBA622JfjHhMREekTxhjuWzKRqUnh3PPaJrIKKj1dkogMEN0KxsaYnwKNwItdOPdWY0y6MSa9sLCwO2WIiIh8RYCvg8eumcEQPwe3Pr+eilo9jCci7etyMDbGfBNYDFxt/7N83iEgqcVhw9xjX2OtfcJam2atTYuOju5qGSIiIq2KDxvCX6+awYGSar7/6iaa9DCeiLSjS8HYGHMO8CPgQmttdYtdbwNXGGP8jTEpQCqwrvtlioiIdN6ckZH8z+IJfLSzgD9/nOXpckSkn2t35TtjzMvAaUCUMSYH+AXNXSj8gQ+NMQBrrLW3W2u3G2NeA3bQPMXiTmutq7eKFxERac9180awOaeMBz/KYFJiKIvGx3q6pC6rqXex8UAp6/aVsH5/KakxIfzonLEE+KoBlEhPMP+ZBeE5aWlpNj093dNliIjIIFXb4OLSx75gT0EV50yK4/RxMZwyJpqwIb6eLq1NpVX1pO8v5ct9JazLLmHboXIamyzGwOjoYDILjjApMZRHr55JUkSgp8sVGRCMMeuttWmt7lMwFhERb5BXXsv9/97FJ7sKKK1uwOFjmJU8lEXjYjl9fAwjo4Jw/y9or2twNVFV10hVvav5a10j1fUujtQ1Ul7TwOaDZXy5r4SM/CMA+Dl8mJoUxqzkCGalRDBzxFBCA3xZvjOf7726CWMMf7p8GgvHxfRJ/SIDmYKxiIiIm6vJsulgKct3FvDxrgJ25TW3c0uODOT0cbEsGh/DrOQI/Jzd72hqrWVddglvbMhh9d5iKmsbqa5zUe9qavO8YH8nM0cMZXZKBLOSI5gyLOyE0yUOFFdz+9/XszOvgrtOT+XuRak4fDof8K215JbXkhAW0Gf/QBDxBAVjERGREzhUVsPHuwr4eGc+q/YUU9/YRLC/k5NGRXLKmGhOSY1meGTnpikcLKnmjQ05vLnhEAdKqgn0c3Da2Giigv0J9HMS7O8g0M9JkL+DIH8nQX5OAv2at4P9nSRFBHYq3NY2uPjZv7bxj/U5nDImmocun8bQIL8On/vOlsM8v3ofW3LKuXlBCj9bPKFTf16RgUTBWEREpAOq6xv5IquY5bsKWJFRyKGyGqD5bvIpY6I5OTWaeaMiCfb/+rPrR+oaeW/rYd5Yn8Pa7BKMgXkjI7lkxjDOmRRHUCvn9CRrLa98eZBfvLWd6BB/Hrl6BlOTwk94fG5ZDS+u3c/L6w5SUlXPqOggUqKC+WhnPv+zeAI3LUjp1XpFPEXBWEREpJOstewtqmJlRiErM4tYvbeY6noXTh/DjBFDOXVMNCenRlFZ28g/1ufwwbY8ahpcpEQFccmMRC6eMYzE8CF9XveWnDLu+PsGCivr+OWFE7lydtKxqRHWWtZml/DcF/tYtiOfJms5Y3ws189LZv7oSJosfOvF9Szbkc9fr5rBeZPj+7x+kd6mYCwiItJNdY0u1u8vZWVmESsyCtmeW3FsX0iAkwumJnDJjGHMGB7u8Tm6pVX13P3qJlZkFHLJjGH89PzxfLAtj+dX72NXXiVhQ3y5YlYS18wd8bVuFrUNLq7+21q2Hirn7zfNYXZKRJfr+HBHPm+sz8HhMPg7fPD39cHP4YOf0wd/pwM/Z/O2n8OHIH8Hs1MiSYkK6uafXqRtCsYiIiI9rOhIHauyivB1+HD6uJh+10vY1WR5aHkmDy/PxBiwFsbHh/LNk0Zw4dREhviduN7SqnouefQLiqvqeeOOeYyOCen0Zz+wbDePfLqHuNAAAv0d1Dc2UdfYRL37VdfoorXFCMfEBnPWhDjOmhjL5MQwj/8jQwYfBWMREREv9enuAj7dXch5k+OZlTy0w0HzYEk1Fz/yBf5OH/75rZOICQ3o0HmlVfV855WNrMws4srZw/nlhRPwd7YewhtdTdS7moNyaXUDn+wqYNmOPNZll9BkIT4sgLMmxHLWxDhmp0Tg6+h+pxARBWMRERHptK055Vz+xGpSooJ49bZ5rT502NL23HJue2E9BRV1/O+SiVwxe3iXPrekqp6PdxWwbHseKzILqW1oIjTAyaLxsZw9MZZ5o6L6/eIs0n8pGIuIiEiXfLK7gJufS2f+6Cieuj7thHdt/7XxED9+cwvhQ/x49JoZTB8+tEc+v6bexcrMQpbtyOejnfmUVTcAMDwikEmJoUxKDGNSQhiTEsOI6GCLOvFuCsYiIiLSZa9+eYD/fmMrl84cxu8vnfKV6RgNriZ+895Onlm1j9kpEfz1qhlEh/j3Sh2NribS95eyfn8p23PL2XqonIMlNcf2J4YPYWJCKJMTm4Py9OHhhAcqLMtXtRWMe7epooiIiAx4l88aTm5ZLQ8tzyQhfAjfP3MMAIWVddz50gbWZZdw4/wU7j1vXK/OA3Y6fJg7MpK5IyOPjZVXNxwLydtyK9h2qJxlO/IBCPD14VunjebWU0b2u4cjpX9SMBYREZF2ffeMVA6X1/Dw8kziwwIYGxfCHX9fT3lNA3+6fBoXTU/0SF1hgb6cNDqKk0ZHHRurrG1ge24FL6zezx8/zODVLw/y0/PHc+6kOHW5kDZpKoWIiIh0SIOriZufS+fzrCIcxhAb5s9j18xkYkKYp0s7odV7irlv6XZ25VUyb2Qkv7hwAuPiQj1dlniQ5hiLiIhIj6iqa+SGZ78kNMDJHy6bOiDm8Da6mnj5y4M8sGw3FTUNXDN3BN8/c0yHa7fWsr+4mu25FcwYEU58WN+vaCg9R8FYREREvF5ZdT0PfpjBC2v2EzrEl3vOHMOVs4fjPG5edFVdI5tzyth4oIyNB0rZeKCM4qp6AKJD/Hnp5jmkxnZu0RPpPxSMRURERNx25VVw39s7WL23mHFxIdxz1lgqahrYcKCUDQfK2J1XcWxVvlHRQcwYPpTpw4eSOHQIP3h9M01NlhdvmaMpGQOUgrGIiIhIC9ZaPtiWx/+9u5NDZc0t30L8nUwbHs704UOZPjyc6Ulfb/e2t/AIVz25lrpGF3+/eU635lfX1Lv4LKOQuLAAUmOCCWpnARXpGQrGIiIiIq2obXCxMrOI4RGBjI4JxuHTfteK/cVVXPnEGqrqXfz9pjlMHtb5cLzxQCn3vLaZvUVVx8aGRwQyNi6EsbEhjI0LYVxcCMlRQVoKu4cpGIuIiIj0oIMl1Vz55BrKaxp4/sbZHV7pr76xiYeXZ/LIp1nEhQbwiwsnYi1k5FeyO6+S3fmVZBdV4XLP5fBz+DAyOoixcSEEOB3UNrqoa2iittFFbYOL2oYmahtc1Dc2f61tbCI1JpgHL59GQrgeEmyNgrGIiIhIDztUVsNVT66h+Eg9z94wi7TkiDaP351Xyfde3cSOwxVcOnMYP79gAqEBvl87rrbBxZ7CI2TkV7IrrzkwZ+YfocHVRICvgwBfn+avTgf+vj74O/8z5uvwYenmXPydPvzlqhnMGxXZSiXeTcFYREREpBfklddy1ZNryKuo5ZlvzmLOyK8HUVeT5cmVe/njsgxChzj5zcWTOWtiXK/VlFVwhNteSGdfcTU/OW88N85P1sImLbQVjDVpRURERKSL4sICeOXWuSSED+H6Z9bxRVbRV/bvL67i8sdX89v3d3H6uBj+/d1TejUUA4yOCeZfd85n0bgYfvXODr776iZq6l29+pmDhYKxiIiISDfEhAbw8i1zGRERxA3PfsmKjEKstfx9zX7OfWglu/MrefDyqTx6zQwig/37pKaQAF8eu2YmPzhrDG9vzuWSR7/gYEl1n3z2QKapFCIiIiI9oKSqnqv/tpY9BUeYmhTGl/tKOTk1it9dMsWjD8J9sruAu1/eiI+P4c9XTufk1GiP1dIfaCqFiIiISC+LCPLj5VvmMDYuhG2HKvjVkok8f+Nsj3eHWDg2hre/vYDYkACuf3odj322h/5wY7Q/0h1jERERkR5U39hEVV0jQ4P82j+4D1XVNfKjN7bw7pbDnD85nvsvndJri4pYazlS10hJVT3FVfWUur+WtHj98sKJBHtgUZO27hhriRURERGRHuTn9MHP2b9CMUCQv5O/XDmdqcPC+O37u9iVV8E3T0rm7ElxxIQEdPl96xub+DyrkHe2HGbn4UpK3cG33tXU6vF+Th8ig/wor2nwSDBui+4Yi4iIiHiZVVlF/PLt7WQWHMEYmJ0cwflT4jmngyG5vrGJVXuKeHfLYZZtz6OitpHQACezkiOIDPYjIsifiCBfIoL8iQzyI6LFK9DP4dH2cepjLCIiIiJfk5FfybtbDvPe1sPthuQGVxNf7Cnm3S25/Ht7PuU1DYQEODl7YhznT4ln/qgo/Jz9//E1BWMRERERaVNmfiXvbm0OyRn5zSF5VnIEZ02IJavgCB9sz6OsuoEQfydnToxl8ZR45o+Owt/p8HTpnaJgLCIiIiIddnxIDvJzcOaEWM6fksApYwZeGG5JwVhEREREuuRQWQ2RQX4E+A7cMNySulKIiIiISJckergPc1/q/zOkRURERET6QLvB2BjztDGmwBizrcVYhDHmQ2NMpvvrUPe4McY8bIzJMsZsMcbM6M3iRURERER6SkfuGD8LnHPc2I+B5dbaVGC5+3uAc4FU9+tW4NGeKVNEREREpHe1G4yttSuAkuOGlwDPubefAy5qMf68bbYGCDfGxPdUsSIiIiIivaWrc4xjrbWH3dt5QKx7OxE42OK4HPeYiIiIiEi/1u2H72xzv7dO93wzxtxqjEk3xqQXFhZ2twwRERERkW7pajDOPzpFwv21wD1+CEhqcdww99jXWGufsNamWWvToqOju1iGiIiIiEjP6Gowfhu43r19PfBWi/Hr3N0p5gLlLaZciIiIiIj0W+0u8GGMeRk4DYgyxuQAvwB+C7xmjLkJ2A98w334e8B5QBZQDdzQCzWLiIiIiPS4doOxtfbKE+xa1MqxFrizu0WJiIiIiPQ105xlPVyEMYU033nua1FAkQc+V9qna9N/6dr0X7o2/ZeuTf+la9O/9cb1GWGtbfUBt34RjD3FGJNurU3zdB3ydbo2/ZeuTf+la9N/6dr0X7o2/VtfX59ut2sTERERERkMFIxFRERERFAwfsLTBcgJ6dr0X7o2/ZeuTf+la9N/6dr0b316fbx6jrGIiIiIyFHefsdYRERERATw0mBsjDnHGLPbGJNljPmxp+vxRsaYfcaYrcaYTcaYdPdYhDHmQ2NMpvvrUPe4McY87L5eW4wxMzxb/eBjjHnaGFNgjNnWYqzT18MYc737+ExjzPWtfZZ0zgmuzS+NMYfcPz+bjDHntdh3r/va7DbGnN1iXL/3epAxJskY84kxZocxZrsx5m73uH5u+oE2ro9+djzMGBNgjFlnjNnsvjb3ucdTjDFr3X/Prxpj/Nzj/u7vs9z7k1u8V6vXrFustV71AhzAHmAk4AdsBiZ4ui5vewH7gKjjxu4Hfuze/jHwO/f2ecD7gAHmAms9Xf9gewGnADOAbV29HkAEsNf9dah7e6in/2wD/XWCa/NL4AetHDvB/TvNH0hx/65z6Pder1yXeGCGezsEyHD//evnph+82rg++tnx/LUxQLB72xdY6/6ZeA24wj3+GHCHe/tbwGPu7SuAV9u6Zt2tzxvvGM8Gsqy1e6219cArwBIP1yTNlgDPubefAy5qMf68bbYGCDfGxHuiwMHKWrsCKDluuLPX42zgQ2ttibW2FPgQOKf3qx/cTnBtTmQJ8Iq1ts5amw1k0fw7T7/3epi19rC1doN7uxLYCSSin5t+oY3rcyL62ekj7p+BI+5vfd0vC5wO/MM9fvzPztGfqX8Ai4wxhhNfs27xxmCcCBxs8X0Obf+wSO+wwDJjzHpjzK3usVhr7WH3dh4Q697WNfOMzl4PXae+9W33f8k/ffS/69G18Qj3f+1Op/nOl35u+pnjrg/oZ8fjjDEOY8wmoIDmfwzuAcqstY3uQ1r+PR+7Bu795UAkvXRtvDEYS/+wwFo7AziX/9/e/YNGEUQBGP8eRkFUVFBEiIVIwDKlIkga0wsisVARC4tYWNsIamGjrYUoiPiHgIpBRBvTa2GhxiaFgkESUNTCKvFZzCQeMacGY+7Ifb9m93aWY7jH2323M3MHgxGxt7ExyziJP5nSJoxH27kM7AB6gQ/AxdZ2p3NFxFrgLnAqM782tpk3rTdPfMydNpCZ05nZC3RTnvLubHGXZnViYTwObGt43V2PaQll5njdTgL3KYkxMTNFom4n6+nGrDUWGg/jtEQyc6LeWL4DV/g5fGhsllBErKQUXTcz8149bN60ifniY+60l8z8DIwAuynTi7pqU+PnPBuD2r4e+Mh/ik0nFsbPgZ66+nEVZSL3cIv71FEiYk1ErJvZB/qBV5Q4zKzIPgo8qPvDwJG6qnsX8KVhqFL/z0Lj8QToj4iNdXiyvx7TIpszx34/JX+gxGagruLeDvQAz/C6t+jqHMerwJvMvNTQZN60gWbxMXdaLyI2R8SGur8a2EeZAz4CHKinzc2dmZw6ADytozHNYvZPuv58yvKSmVMRcZJy4VkBXMvM1y3uVqfZAtwv1y26gFuZ+TgingNDEXEceAccrOc/oqzoHgO+AceWvsvLW0TcBvqATRHxHjgDXGAB8cjMTxFxjnIjATibmX+7aExNNIlNX0T0Uobp3wInADLzdUQMAaPAFDCYmdP1fbzuLa49wGHgZZ0rCXAa86ZdNIvPIXOn5bYC1yNiBeUB7VBmPoyIUeBORJwHXlC+2FC3NyJijLIQeQB+H7N/4T/fSZIkSXTmVApJkiTpFxbGkiRJEhbGkiRJEmBhLEmSJAEWxpIkSRJgYSxJkiQBFsaSi1OMJwAAABBJREFUJEkSYGEsSZIkAfAD/5og+bM5eawAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 864x360 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.figure(figsize=(12, 5))\n",
    "plt.plot(list(range(5, 3000, 50)), scores)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В реальности метод локтя работает так себе (где на картинке локоть сказать сложно). И честным ответом на \"как найти оптимальное количество кластеров\" будет - а спросите что-нибудь попроще."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Домашнее задание"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. На нескольких алгоритмах кластеризации, умеющих работать с sparse матрицами, проверьте, что работает лучше Count_Vectorizer или TfidfVectorizer (попробуйте выжать максимум из каждого - попробуйте нграммы, символьные нграммы, разные значения max_features и min_df) (3 балла)\n",
    "\n",
    "2. На нескольких алгоритмах кластеризации проверьте, какое матричное разложение (TruncatedSVD или NMF) работает лучше для кластеризации. (3 балла)\n",
    "\n",
    "3. С помощью алгоритмов, умеющих выделять выбросы, попробуйте найти необычные объявления (необычные - это такие, которые непонятно к какой категории можно вообще отнести, что-то с ошибками или вообще какая-то дичь). В этом задании можно использовать любую векторизацию. (4 балла)\n",
    "\n",
    "Используйте те же данные, что и в семинаре (колонки - title и category_name)\n",
    "\n",
    "Делайте соответствующие вашими ресурсам и потребностям алгоритма подвыборки из всего датасета. Для сравнения используйте любую из метрик, которые есть в семинаре. Оценивать на глаз тоже можно, но тогда нужно объяснить, почему вы считаете одну кластеризацию лучше. \n",
    "\n",
    "НЕ ЗАБЫВАЙТЕ подбирать параметры в кластеризации. **За использование всех параметров по умолчанию, оценка будет снижаться** (под использованием всех параметров по умолчанию я имею в виду что-то такое -  `cluster = DBSCAN()`) \n",
    "\n",
    "Если получится, используйте метод локтя. (1 бонусный балл)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}