2022/seminars/sem3_sklearn_knn/sem03-sklearn-knn.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Введение в sklearn. KNN"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Общая схема решения задачи машинного обучения\n",
    "\n",
    "__Вспомнить из лекции:__\n",
    "* Что такое задача машинного обучения? Что дано и что необходимо найти?\n",
    "* Какие бывают типы признаков в машинном обучении?\n",
    "* Какие бывают виды задач в машинном обучении?\n",
    "* Что такое функционал качества? Для чего он нужен?\n",
    "\n",
    "Вспомним общую схему решения задачи машинного обучения:\n",
    "\n",
    "<div>\n",
    "<img src=\"scheme.png\" width=\"500\"/>\n",
    "</div>\n",
    "\n",
    "Из исходной базы данных после предобработки мы получаем обучающую выборку $X, Y$. Матрица объекты-признаки $X$ имеет размер (число объектов) $\\times$ (число признаков). Одна строка этой матрицы соответствует одному объекту обучающей выборки, заданному как вектор длины (число признаков). Признаки - числовые характеристики объекта. Вектор правильных ответов $Y$ имеет длину (число объектов). \n",
    "\n",
    "На этапе обучения на основе обучающей выборки $X, Y$ строится (обучается) алгоритм $a(x)$. Это некая функция, которая берет на вход признаки объекта и возвращает предсказание для этого объекта: $y \\approx a(x)$. Алгоритм $a$ может делать предсказания для любых допустимых объектов; его можно применять как к обучающим объектам, так и к тем, которых алгоритм никогда не видел. В этом и состоит цель машинного обучения: выявить такие закономерности в обучающей выборке, которые позволят делать качественные (довольно точные) предсказания на новых объектах $x$. \n",
    "\n",
    "Тому, как обучать такие алгоритмы $a(x)$ по обучающей выборке, во многом ипосвящен наш курс. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Интерфейс Scikit-Learn\n",
    "\n",
    "Scikit-Learn, или коротко Sklearn - библиотека, в которой реализованы практически все используемые сегодня алгоритмы машинного обучения. Нам необходимо познакомиться с интерфейсом библиотеки, чтобы понимать, как ее можно использовать на практике. Далее в курсе мы будем не только использовать готовые реализации из sklearn, но иногда и сами реализовывать алгоритмы в том же духе, в котором это сделано в этой библиотеке (с тем же интерфейсом).\n",
    "\n",
    "Для реализации алгоритмов машинного обучения в sklearn всегда используется один интерфейс - класс с функциями fit(X, Y) для обучения модели по обучающей выборке $X, Y$ и predict(X) для возвращения предсказаний на выборке $X$. При создании класса можно указывать дополнительные параметры, влияющие на работу алгоритма машинного обучения.\n",
    "\n",
    "Например, такова будет логика работы класса линейной регрессии, которую мы подробно изучим на следующих семинарах:\n",
    "* При создании класса нужно запомнить коэффициент регуляризации;\n",
    "* Задача функции fit - по выборке X и Y найти веса w и сохранить их внутри класса в self.w;\n",
    "* Задача функции predict - по весам self.w и X вернуть предсказания $Y$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinearRegressor:\n",
    "    def __init__(self, reg_coef: float = None) -> None:\n",
    "        self.lambda_ = reg_coef\n",
    "    \n",
    "    def fit(self, X_train: np.array, y_train: np.array) -> None:\n",
    "        self.w =  # формула для вычисления весов, X, y и self.lambda_\n",
    "    \n",
    "    def predict(self, X_test: np.array) -> np.array:\n",
    "        y_pred =  # функция от X и self.w\n",
    "        \n",
    "        return y_pred"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Если бы не использовали класс, нам пришлось бы передавать веса w в функцию predict каждый раз, когда мы захотели бы сделать предсказания, это неудобно (особенно если таких вспомогательных переменных много). А так веса хранятся внутри класса, и мы можем даже не догадываться об их существовании (если класс писали не мы).\n",
    "\n",
    "Пример импорта классификатора из sklearn:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.dummy import DummyClassifier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Помимо алгоритмов обучения и предсказания для разных методов, в sklearn реализовано много вспомогательного функционала для предобработки данных, визуализации данных, вычисления метрик качества и т. д. В ходе следующих семинаров мы постепенно познакомимся с этим функционалом библиотеки.\n",
    "\n",
    "Сегодня мы познакомимся с методами предобработки данных и их реализацией в sklearn.\n",
    "\n",
    "### Предобработка данных\n",
    "Для демонстраций загрузим набор данных [Automobile Data Set](https://archive.ics.uci.edu/ml/datasets/Automobile). В данных присутствуют категориальные, целочисленные и вещественнозначные признаки."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_raw = pd.read_csv(\n",
    "    \"http://archive.ics.uci.edu/ml/machine-learning-databases/autos/imports-85.data\", \n",
    "    header=None, \n",
    "    na_values=[\"?\"]\n",
    ")\n",
    "X_raw.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Разделим признаки и целевую переменную:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "y = X_raw[25]\n",
    "X_raw = X_raw.drop(25, axis=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Заполнение пропусков\n",
    "В матрице объекты-признаки могут быть пропущенные значения, и это вызовет исключение при попытке передать такую матрицу в функцию обучения модели или даже предобработки. Если пропусков немного, можно удалить объекты с пропусками из обучающей выборки. Заполнить пропуски можно разными способами:\n",
    "* заполнить средними (mean, median);\n",
    "* предсказывать пропущенные значения по непропущенным.\n",
    "\n",
    "Последний вариант сложный и применяется редко. Для заполнения константами можно использовать метод датафрейма fillna, для замены средними - класс `impute.SimpleImputer`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.impute import SimpleImputer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# для удобства работы с нашим датасетом создаем маску, указывающую на столбцы с категориальными признаками\n",
    "# категориальные признаки имеют тип \"object\"\n",
    "cat_features_mask = (X_raw.dtypes == \"object\").values\n",
    "\n",
    "# для вещественнозначных признаков заполним пропуски средними\n",
    "X_real = X_raw[X_raw.columns[~cat_features_mask]]\n",
    "mis_replacer = SimpleImputer(strategy=\"mean\")\n",
    "X_no_mis_real = pd.DataFrame(data=mis_replacer.fit_transform(X_real), columns=X_real.columns)\n",
    "\n",
    "# для категориальных - пустыми строками\n",
    "X_cat = X_raw[X_raw.columns[cat_features_mask]].fillna(\"\")\n",
    "X_no_mis = pd.concat([X_no_mis_real, X_cat], axis=1)\n",
    "\n",
    "X_no_mis.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Всегда нужно анализировать, случайны ли пропуски в каком-то признаке. Иногда факт отсутствия информации о значении признака может сам быть важным признаком, который необходимо добавить к другим признакам.\n",
    "\n",
    "__Пример:__ предсказание возраста пользователя по данным с его телефона. Поскольку люди старшего возраста чаще пользуются простыми телефонами, факт отсутствия каких-то данных (например, истории посещенных интернет-страниц), скорее всего, будет хорошим признаком.\n",
    "\n",
    "Для категориальных признаков рекомендуется создавать отдельную категорию, соответствующую пропущенному значению. В наши данных пропусков в категориальных признаках нет.\n",
    "\n",
    "### Преобразование нечисловых признаков\n",
    "Практически все методы машинного обучения требуют, чтобы на вход функции обучения подавалась вещественная матрица. В процессе обучения используются свойства вещественных чисел, в частности, возможность сравнения и применения арифметических операций. Поэтому, даже если формально в матрице объекты-признаки записаны числовые значения, нужно всегда анализировать, можно ли относиться к ним как к числам. \n",
    "\n",
    "__Пример:__ некоторые признаки могут задаваться целочисленными хешами или id (например, id пользователя соц. сети), однако нельзя сложить двух пользователей и получить третьего, исходя из их id (как это может сделать линейная модель).\n",
    "\n",
    "Это пример категориального признака, принимающего значения из неупорядоченного конечного множества $K$. К таким признакам обычно применяют [one-hot encoding](http://scikit-learn.org/stable/modules/preprocessing.html#encoding-categorical-features) (вместо одного признака создают $K$ бинарных признаков - по одному на каждое возможное значение исходного признака). В sklearn это можно сделать с помощью классов LabelEncoder + OneHotEncoding, но проще использовать функцию `pd.get_dummies`.\n",
    "\n",
    "Следует заметить, что в новой матрице будет очень много нулевых значений. Чтобы не хранить их в памяти, можно задать параметр `OneHotEncoder(sparse = True)` или `.get_dummies(sparse=True)`, и метод вернет [разреженную матрицу](http://docs.scipy.org/doc/scipy/reference/sparse.html), в которой хранятся только ненулевые значения. Выполнение некоторых операций с такой матрицей может быть неэффективным, однако большинство методов sklearn умеют работать с разреженными матрицами."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(f\"Shape before encoding: {X_no_mis.shape}\")\n",
    "X_dum = pd.get_dummies(X_no_mis, drop_first=True)\n",
    "X_dum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Помимо категориальных, преобразования требуют, например, строковые признаки. Их можно превращать в матрицу частот слов [CountVectorizer](http://scikit-learn.org/stable/modules/generated/sklearn.feature_extraction.text.CountVectorizer.html#sklearn.feature_extraction.text.CountVectorizer), матрицу частот буквосочетаний фиксированной длины, можно извлекать другие признаки (например, длина строки).\n",
    "\n",
    "### Масштабирование признаков\n",
    "При начале работы с данными всегда рекомендуется приводить все признаки к одному масштабу. Это важно для численной устойчивости при работе с матрицей объекты-признаки (рядом с нулем чисел с плавающей точкой больше, чем с области больших чисел). Кроме того, у каждого метода машинного обучения есть свои особенности, требующие масштабирования признаков. Например, для линейных моделей - это ускорение обучения и повышение интерпретируемости модели.\n",
    "\n",
    "Первый популярный способ масштабирования - нормализация: вычитание среднего из каждого признака и деление на стандартное отклонение (`StandardScaler` в sklearn). Второй популярный способ: вычитание минимума из каждого признака, а затем деление на разницу максимального и минимального значения (`MinMaxScaler` в sklearn)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn import preprocessing\n",
    "\n",
    "normalizer = preprocessing.MinMaxScaler()\n",
    "X_real_norm_np = normalizer.fit_transform(X_dum)\n",
    "X = pd.DataFrame(data=X_real_norm_np)\n",
    "X.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Пример реализации\n",
    "\n",
    "Реализуем класс для нормализации данных по аналогии с интерфейсом sklearn для нормализации.\n",
    "\n",
    "Предобработка данных в sklearn реализована по похожему шаблону, что и обучение моделей: функция `.fit(X)` запоминает внутренние переменные, а функция `.transform(X)` выполняет преобразование выборки. y здесь не нужен, потому что в нормализации целевые переменные не участвуют (как и почти во всей предобработке данных).\n",
    "\n",
    "Параметров у класса нет, так что функцию `__init__` мы пропускаем. Функция `.fit()` считает статистики - среднееи стандартное отклонение каждого признака (по обучающей выборке), а функция `.tranform()` вычитает среднее и делит на стандартное отклонение. Для вычисления статистик используем numpy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Normalizer:\n",
    "    def fit(self, X: np.array) -> None:\n",
    "        self.mu = X.mean(axis=0)\n",
    "        self.sigma = X.std(axis=0)\n",
    "        \n",
    "    def transform(self, X: np.array) -> np.array:\n",
    "        return (X - self.mu[np.newaxis, :]) / self.sigma[np.newaxis, :]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Создаем случайные данные X и y для тестирования нашего класса:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_obj_train = 20\n",
    "num_obj_te = 10\n",
    "num_feat = 4\n",
    "X_train = np.random.randint(-5, 5, size=(num_obj_train, num_feat))\n",
    "X_train.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_test = np.random.randint(-5, 5, size=(num_obj_te, num_feat))\n",
    "X_test.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_train"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Создаем объект класса и трансформируем выборку:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "normalizer = Normalizer()\n",
    "normalizer.fit(X_train)\n",
    "X_train_transformed = normalizer.transform(X_train)\n",
    "X_test_transformed = normalizer.transform(X_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Fit нужно вызывать именно на обучающих данных, чтобы ничего не подсмотреть в контрольной выборке. А transform можно вызывать много раз для любых выборок (с уже посчитанным статистиками, которые хранятся внутри класса)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_train_transformed"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Метрические методы. k Nearest Neighbours\n",
    "\n",
    "### Теоретическая часть\n",
    "\n",
    "\n",
    "__Вспомнить из лекции:__\n",
    "* Как в методе k ближайших соседей выполняются предсказания в задаче классификаци и регрессии?\n",
    "* Что такое гипотеза компактности?\n",
    "* Какие функции расстояния можно использовать для вещественных признаков, категориальных признаков, строковых признаков, множественнозначных признаков?\n",
    "\n",
    "#### Задача 1.\n",
    "Предположим, мы решаем задачу классификации на три класса по двум признакам и используем метод k ближайших соседей с k=3 и манхэттанской метрикой. Мы имеем следующую обучающую выборку:\n",
    "\n",
    "| Признак 1 | Признак 2 | Класс |\n",
    "|-----------|-----------|-------|\n",
    "| 1         | -1        | 1     |\n",
    "| 2         | 2         | 1     |\n",
    "| 3         | 2         | 2     |\n",
    "| 1         | 0         | 3     |\n",
    "| 2         | -2        | 3     |\n",
    "\n",
    "Каковы будут предсказания для объекта $x=(2, -1)$?\n",
    "\n",
    "__Решение.__\n",
    "\n",
    "Алгоритм предсказания kNN для задачи классификации:\n",
    "1. Вычислить расстояние от каждого объекта обучающей выборки до тестового объекта.\n",
    "1. Найти k объектов обучающей выборки (соседей) с наименьшим расстоянием до тестового объекта.\n",
    "1. Вернуть наиболее встречающийся класс среди k соседей.\n",
    "\n",
    "Вычислим расстояния. Расстояние от первого объекта в обучении до тестового объекта $x$ (манхэттэнская метрика):\n",
    "\n",
    "$$|1-2| + |-1-(-1)| = 1.$$\n",
    "\n",
    "Аналогично для 2-5 объектов: получатся расстояния 3, 4, 2, 1.\n",
    "\n",
    "Находим 3 ближайших объекта: это объекты с номерами 1, 4, 5 (расстояния 1, 2, 1 соответственно). Эти три объекта относятся к классам 1, 3, 3. Чаще всего встречается класс 3, поэтому предсказываем 3.\n",
    "\n",
    "#### Задача 2.\n",
    "Визуализируйте разделяющую поверхность между классами для следующей выборки:\n",
    "\n",
    "| Признак 1 | Признак 2 | Класс |\n",
    "|-----------|-----------|-------|\n",
    "| 2         | 2        | 1     |\n",
    "| 3         | 2         | 1     |\n",
    "| 2         | 0         | 2     |\n",
    "| 1         | -1         | 3     |\n",
    "| 1        | 1        | 3     |\n",
    "\n",
    "Используйте k=1 и евклидово расстояние.\n",
    "\n",
    "__Решение.__\n",
    "\n",
    "В задачах классификации с двумя признаками мы можем изобразить признаковое пространство на плоскости и раскрасить его в разные цвета в соответствии с классом каждой точки плоскости. В этом и состоит сейчас наша задача.\n",
    "\n",
    "Для начала отобразим на плоскости обучающую выборку - пять точек - в соответствии с их координатами.\n",
    "\n",
    "При $k=1$ каждая точка плоскости будет относиться к тому же классу, что и ближайший к ней объект обучающей выборки. Если нам даны две точки разных классов, то чтобы провести между ними границу классов, нужно построить серединный перпендикудяр. Для случая с несколькими точками нужно построить несколько серединных перпендикуляров, найти их точки пересечения и определить, какие области к каким классам относятся. Более строго такая конструкция задается с помощью [Диаграммы Вороного](https://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%B0%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0_%D0%92%D0%BE%D1%80%D0%BE%D0%BD%D0%BE%D0%B3%D0%BE), но мы не будем вдаваться в ее детали.\n",
    "\n",
    "<div>\n",
    "<img src=\"classifi.png\" width=\"350\"/>\n",
    "</div>\n",
    "\n",
    "#### Задача 3.\n",
    "Предположим, мы решаем задачу регрессии по двум признакам и используем метод k ближайших соседей с k=3 и манхэттанской метрикой. Мы имеем следующую обучающую выборку:\n",
    "\n",
    "| Признак 1 | Признак 2 | Ответ |\n",
    "|-----------|-----------|-------|\n",
    "| 1         | -1        | 3.5     |\n",
    "| 2         | 2         | 2.3     |\n",
    "| 3         | 2         | 1.7     |\n",
    "| 1         | 0         | -0.4     |\n",
    "| 2         | -2        | 0.1     |\n",
    "\n",
    "Каковы будут предсказания для объекта $x=(2, -1)$?\n",
    "\n",
    "__Решение.__\n",
    "Предсказания kNN для регрессии отличаются от предсказаний для классификации только финальным шагом: вместо поиска наиболее часто встречающегося класса нужно усреднить ответы на соседях. Признаки в этой задаче те же, что в задаче 1, поэтому соседей мы уже знаем: это объекты с номерами 1, 4, 5. На них мы имеем ответы 3.5, -0.3, 0.1. Усредним их: (3.5-0.4+0.1)/3 = 1.1. Предсказываем 1.1.\n",
    "\n",
    "#### Вопрос: каковы параметры и гиперпараметры метода kNN?\n",
    "__Ответ:__\n",
    "\n",
    "Параметры - это величины, которые мы настраиваем в процессе обучения по обучающей выборке. В методе kNN нет как такового обучения - это очень простой эвристический алгоритм. Под параметрами в kNN можно понимать обучающую выборку. В другой трактовке у метода нет параметров.\n",
    "\n",
    "Гиперпараметры - это величины, которые мы должны установить до начала обучения модели. Гиперпараметры не настраиваются по обучающей выборке в процессе обучения модели. Два самых важных гиперпараметры метода kNN - это число соседей k и метрика. Используя разные комбинации этих гиперпараметров, можно получать совершенно разное качество работы алгоритма. Гиперпараметры обычно настраивают по валидационной выборке или используя кросс-валидацию.\n",
    "\n",
    "#### Какова динамика качества работы kNN при увеличении k?\n",
    "\n",
    "__Ответ:__\n",
    "\n",
    "При $k=1$ вокруг каждого объекта обучающей выборки создается область его класса. Если, к примеру, в \"большую\" область одного класса случайно попал один шумовой объект другого класса, вокруг этого шумового объекта будет \"остров\" предсказания другого класса. Это нелогично и говорит о переобучении.\n",
    "\n",
    "При $k$, равном числу объектов в выборке, для всех объектов будет предсказываться одно и то же, что вновь говорит о низком качестве работы классификатора. Получается, что качество kNN при увеличении $k$ должно сначала расти, а потом падать, и оптимум будем где-то посередине.\n",
    "\n",
    "Рассмотрим синтетический пример: на рисунке визуализирована обучающая выборка (\"настоящая\" разделяющая поверхность - прямая) и разделяющая поверхность kNN по аналогии с задачей 2, и на разных графиках используется разное число соседей $k$:\n",
    "\n",
    "<div>\n",
    "<img src=\"k_grid.png\" width=\"550\"/>\n",
    "</div>\n",
    "\n",
    "При использовании малых $k$ разделяющая поверхность слишком сложная, на нее оказывают сильное воздействие шумовые объекты. Далее поверхность становится все ровнее и ровнее и при $k=50$ выглядит наиболее разумно. При большем k разделяющая поверхность уходит от линейной, и оранжевый класс \"захватывает\" синий.\n",
    "\n",
    "#### Почему при использовании kNN важно нормировать данные?\n",
    "\n",
    "__Ответ:__\n",
    "\n",
    "Рассмотрим для примера манхэттэнскую метрику. Если один признак будет иметь масштаб около 1000, а другой - около 1, то когда мы будем складывать модули разностей для этих двух признаков, второй признак практически не будет иметь влияния на ответ. Если же признаки отнормировать, но они все будут в одной шкале.\n",
    "\n",
    "### Практическая часть"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import sklearn\n",
    "\n",
    "# изображения цифр\n",
    "from sklearn.datasets import load_digits\n",
    "# классификатор\n",
    "from sklearn.neighbors import KNeighborsClassifier\n",
    "# шаффлер данных\n",
    "from sklearn.utils import shuffle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "clf = KNeighborsClassifier(n_neighbors=3)\n",
    "\n",
    "data = load_digits()\n",
    "X = data.images\n",
    "y = data.target\n",
    "\n",
    "X.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# вытягиваем квадратное изображение в вектор, чтобы получить матрицу объекты-признаки\n",
    "X = X.reshape(X.shape[0], -1)\n",
    "\n",
    "# перемешиваем данные\n",
    "X, y = shuffle(X, y)\n",
    "print(f\"Features shape: {X.shape},\\nTarget shape: {y.shape}\")\n",
    "print(f\"Target samples: {y[:10]}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_train, y_train = X[:700, :], y[:700]\n",
    "X_val, y_val = X[700:1300, :], y[700:1300]\n",
    "X_test, y_test = X[1300:, :], y[1300:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Обучаем классификатор и делаем предсказания\n",
    "clf.fit(X_train, y_train)\n",
    "y_predicted = clf.predict(X_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Вычисляем простейшую метрику качества алгоритма - долю правильных ответов\n",
    "print(\"Accuracy is: \", np.mean(y_test==y_predicted))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Учитывая, что у нас 10 классов, то вероятность угадать правильный ответ много раз очень мала. Поэтому полученное значение accuracy - очень хороший результат!\n",
    "\n",
    "Попробуем использовать разные значения гиперпараметра k. Сравнивать разные значения k по обучающей выборке бесполезно: каждый объект является ближайшим сам к себе и оптимальное k будет равно 1. Будем сравнивать разные k по качеству на валидационной выборке:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Подбор k на валидационной выборке:\n",
    "k_best = -1\n",
    "best_accuracy = 0\n",
    "\n",
    "for k in range(1, 20):\n",
    "    y_predicted = KNeighborsClassifier(n_neighbors=k).fit(X_train, y_train).predict(X_val)\n",
    "\n",
    "    val_accuracy = np.mean(y_predicted==y_val)                      \n",
    "    print(f\"k = {k}; accuracy = {val_accuracy:.3f}\")\n",
    "                           \n",
    "    if val_accuracy > best_accuracy:\n",
    "        best_accuracy = val_accuracy\n",
    "        k_best = k\n",
    "\n",
    "k_best"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Сравним accuracy на обучении, валидации и тесте для найденного лучшего значения k:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "clf = KNeighborsClassifier(n_neighbors=k_best)\n",
    "clf.fit(X_train, y_train)\n",
    "\n",
    "for X_data, y_data in zip([X_train, X_val, X_test], [y_train, y_val, y_test]):\n",
    "    y_predicted = clf.predict(X_data)\n",
    "    print(f\"Accuracy: {np.mean(y_predicted==y_data):.3f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Качество на обучающей выборке самое лучшее, но оно обманчиво, ведь алгоритм уже знает эти объекты.\n",
    "На валидационной выборке мы тоже использовали ответы - уже для подбора гиперпараметра k, так что этот показатель тоже не совсем честный. \n",
    "И действительно, качество на тестовой выборке (ответы для которой мы нигде не подсматривали) может оказаться хуже, чем на валидационной выборке.\n",
    "\n",
    "_Вывод_: оценивать качество алгоритма нужно на отложенной выборке, которая не используется нигде в обучении и не используется в подборе гиперпараметров."
   ]
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}