{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "provenance": [] }, "kernelspec": { "name": "python3", "display_name": "Python 3" }, "language_info": { "name": "python" } }, "cells": [ { "cell_type": "markdown", "source": [ "# **Метод k-ближайших соседей**\n", "\n", "▶ k-Nearest Neighbor, kNN\n", "\n", "\n", "* Используется в задачах как классификации, так и регрессии\n", "* Входит в семейство алгоритмов обучения с учителем:\n", "> Дан размеченный набор данных, состоящий из обучающих наблюдений $(x,y)$. \n", "> Требуется выявить зависимость между $x$ и $y$: определить функцию $f:X→Y$ так, чтобы по наблюдению $x$ функция $f(x)$ могла наиболее достоверно предсказать целевое значение $y$.\n", "\n", "---\n" ], "metadata": { "id": "HouWVph7xDQN" } }, { "cell_type": "markdown", "source": [ "В условиях **классификации** алгоритм kNN по существу сводится к **формированию большинства голосов между k экземплярами** (*данными наблюдений, использованных при обучении*), наиболее похожими на вновь рассматриваемое «невидимое» (*не используемое при обучении*) наблюдение. \n", "Сходство определяется в соответствии с **метрикой расстояния** между двумя точками данных.\n", "\n", "Пусть $x_i$ - экземпляр наблюдения с $p$ параметрами (*характеристиками, \"фичами\"*): \n", "\n", "$$x_i = (x_{i1}, x_{i2},..., x_{ip})$$\n", "\n", "$n$ - общее число наблюдений: $$i = (1, 2, ..., n)$$\n", "\n", "**Евклидово расстояние** между наблюдениями $x_i$ и $x_l$ :\n", "\n", "$$d(x_i, x_l) = \\sqrt{(x_{i1} - x_{l1})^2 + (x_{i2} - x_{l2})^2 + ... + (x_{ip} - x_{lp})^2 }$$\n", "\n", "$$d(x_i, x_l) = \\sqrt{\\sum_{j=1}^{p}(x_{ij} - x_{lj})^2}$$\n", "\n", "\n", "---\n", "\n" ], "metadata": { "id": "Tpv9GeNExLca" } }, { "cell_type": "markdown", "source": [ "🔎***Альтернативные метрики расстояния***:\n", "\n", "* **Манхэттенское расстояние** (расстояние Городских кварталов):\n", "$$d(x_i, x_l) = \\sum_{j=1}^{p}|x_{ij} - x_{lj}|$$\n", "* **Расстояние Чебышева** (максимальное расстояние):\n", "$$d(x_i, x_l) = \\max_{j}|x_{ij} - x_{lj}|$$\n", "* **Расстояние Хэмминга** (для бинарных векторов длины p):\n", "$$d(x_i, x_l) = \\sum_{j=1}^{p}(x_{ij} \\oplus x_{lj})$$\n", "где ⊕ - операция побитового XOR" ], "metadata": { "id": "UyvJIqhZxN3y" } }, { "cell_type": "markdown", "source": [ "# **Алгоритм для классификации**\n", "\n", "\n", "1. Выбрать число соседей $k$ и метрику расстояния для определения дистанции между наблюдениями $D(x_i, x_l) = distance(x_i, x_l)$.\n", "2. Для нового наблюдения $x_i$ отобрать $k$ ближайших соседей согласно метрике расстояния.\n", "3. Среди отобранных наблюдений рассчитать число объектов в каждом классе.\n", "4. Класс, в котором оказалось наибольшее число соседей, назначается для рассматриваемого наблюдения.\n", "\n", "\n", "\n", "Если среди $k$ соседей окажется равное количество экземпляров, принадлежащих разным классам, то возникает неоднозначность в определении класса для нового экземпляра.\n", "\n", "В таком случае **kNN** может применять различные стратегии для разрешения этой неоднозначности, например:\n", "\n", "\n", "* **Случайный выбор**\n", "> В случае равного количества соседей для разных классов, можно случайным образом выбрать один из классов из набора классов с наибольшим количеством соседей.\n", "* **Взвешенное голосование** \n", "> Можно применить взвешенное голосование, где каждый сосед имеет вес, зависящий, например, от расстояния до нового экземпляра. Это означает, что ближайшие соседи могут иметь больший вес при определении класса.\n", "---\n", "\n", "\n", "\n", "\n" ], "metadata": { "id": "nwdVK7xkxU-B" } }, { "cell_type": "markdown", "source": [ "**Как оценить результаты: Точность (Accuracy)** \n", ">**Смысл**: Доля правильных предсказаний (верно классифицированных объектов) среди всех предсказаний. \n", "\n", "$$\\text{Accuracy} = \\frac{\\text{число правильных предсказаний}}{\\text{общее число предсказаний}}\n", "= \\frac{\\sum_{i=1}^{N} \\mathbf{1}\\{y_i = \\hat{y}_i\\}}{N}$$" ], "metadata": { "id": "-rVu_eCSyFZt" } }, { "cell_type": "markdown", "source": [ "# **Алгоритм для регрессии**\n", "\n", "\n", "1. Выбрать число соседей $k$ и метрику расстояния для определения дистанции между наблюдениями $D(x_i, x_l) = distance(x_i, x_l)$.\n", "2. Для нового наблюдения $x_i$ отобрать $k$ ближайших соседей согласно метрике расстояния.\n", "3. Прогнозирование целевого значения $y_i$ осуществляется путем усреднения (или взвешивания) значений целевой переменной для $k$ ближайших соседей:\n", "$$\\hat{y} = \\frac{1}{k} \\sum_{neighbor=1}^{k} y_{neighbor}$$" ], "metadata": { "id": "Am6YOh1ewyzS" } }, { "cell_type": "markdown", "source": [ "# **Классификация**" ], "metadata": { "id": "xBusNe73nS9M" } }, { "cell_type": "markdown", "source": [ "### **Датасет**\n", "Датасет **Iris** - это набор данных, часто используемый в машинном обучении и статистике. Он содержит информацию о 150 образцах ирисов, по 50 образцов из каждого из трех видов ирисов:\n", "\n", "* Ирис щетинистый (Iris setosa)\n", "* Ирис версиколор (Iris versicolor)\n", "* Ирис виргинский (Iris virginica) \n", "\n", "Каждый образец ириса измеряется по четырем характеристикам (признакам):\n", "\n", "* Длина чашелистника (sepal length) в сантиметрах.\n", "* Ширина чашелистника (sepal width) в сантиметрах.\n", "* Длина лепестка (petal length) в сантиметрах.\n", "* Ширина лепестка (petal width) в сантиметрах. \n", "\n", "Датасет Iris часто используется для задач классификации и кластеризации, а также в учебных целях для демонстрации различных методов машинного обучения." ], "metadata": { "id": "hrnNu7VNLyVw" } }, { "cell_type": "markdown", "source": [ "\n" ], "metadata": { "id": "s9y4roQaLs-1" } }, { "cell_type": "code", "source": [ "from sklearn.datasets import load_iris\n", "from sklearn.model_selection import train_test_split\n", "import numpy as np\n", "from collections import Counter\n", "from sklearn.metrics import accuracy_score" ], "metadata": { "id": "RmwqMWuOp6ES" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "### 1. Загрузка данных и разбиение" ], "metadata": { "id": "YZixM-oWqJhG" } }, { "cell_type": "code", "source": [ "# Загружаем данные\n", "X, y = load_iris(return_X_y=True, as_frame=True)\n", "\n", "# Разделяем на обучающую и тестовую выборки\n", "X_train, X_test, y_train, y_test = train_test_split(X.values, y.values, random_state=0)\n", "\n", "print(\"Размеры:\", X_train.shape, X_test.shape)" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "HhNyXjnHqDsN", "outputId": "2e09b268-3867-45e5-f534-ea474893aac4" }, "execution_count": null, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "Размеры: (112, 4) (38, 4)\n" ] } ] }, { "cell_type": "code", "source": [ "X" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 424 }, "id": "yHY4jUrHz7kT", "outputId": "b328097f-2062-4f56-8032-84cc03244039", "collapsed": true }, "execution_count": null, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ " sepal length (cm) sepal width (cm) petal length (cm) petal width (cm)\n", "0 5.1 3.5 1.4 0.2\n", "1 4.9 3.0 1.4 0.2\n", "2 4.7 3.2 1.3 0.2\n", "3 4.6 3.1 1.5 0.2\n", "4 5.0 3.6 1.4 0.2\n", ".. ... ... ... ...\n", "145 6.7 3.0 5.2 2.3\n", "146 6.3 2.5 5.0 1.9\n", "147 6.5 3.0 5.2 2.0\n", "148 6.2 3.4 5.4 2.3\n", "149 5.9 3.0 5.1 1.8\n", "\n", "[150 rows x 4 columns]" ], "text/html": [ "\n", "
| \n", " | sepal length (cm) | \n", "sepal width (cm) | \n", "petal length (cm) | \n", "petal width (cm) | \n", "
|---|---|---|---|---|
| 0 | \n", "5.1 | \n", "3.5 | \n", "1.4 | \n", "0.2 | \n", "
| 1 | \n", "4.9 | \n", "3.0 | \n", "1.4 | \n", "0.2 | \n", "
| 2 | \n", "4.7 | \n", "3.2 | \n", "1.3 | \n", "0.2 | \n", "
| 3 | \n", "4.6 | \n", "3.1 | \n", "1.5 | \n", "0.2 | \n", "
| 4 | \n", "5.0 | \n", "3.6 | \n", "1.4 | \n", "0.2 | \n", "
| ... | \n", "... | \n", "... | \n", "... | \n", "... | \n", "
| 145 | \n", "6.7 | \n", "3.0 | \n", "5.2 | \n", "2.3 | \n", "
| 146 | \n", "6.3 | \n", "2.5 | \n", "5.0 | \n", "1.9 | \n", "
| 147 | \n", "6.5 | \n", "3.0 | \n", "5.2 | \n", "2.0 | \n", "
| 148 | \n", "6.2 | \n", "3.4 | \n", "5.4 | \n", "2.3 | \n", "
| 149 | \n", "5.9 | \n", "3.0 | \n", "5.1 | \n", "1.8 | \n", "
150 rows × 4 columns
\n", "| \n", " | target | \n", "
|---|---|
| 0 | \n", "0 | \n", "
| 1 | \n", "0 | \n", "
| 2 | \n", "0 | \n", "
| 3 | \n", "0 | \n", "
| 4 | \n", "0 | \n", "
| ... | \n", "... | \n", "
| 145 | \n", "2 | \n", "
| 146 | \n", "2 | \n", "
| 147 | \n", "2 | \n", "
| 148 | \n", "2 | \n", "
| 149 | \n", "2 | \n", "
150 rows × 1 columns
\n", "