Метод k ближайших соседей: k-NN

Метод k ближайших соседей (k-NN (k-Nearest Neighbors)) представляет собой один из наиболее интуитивных и легко понимаемых ML-алгоритмов с которого обычно и начинают изучать машинное обучение. Этот метод, основанный на идее близости объектов в пространстве признаков, часто используется для задач классификации и регрессии.

k-NN является непараметрическим методом машинного обучения, что означает отсутствие жестко заданных параметров модели, таких как веса и смещение, присущие линейной регрессии. Вместо этого модель «запоминает» обучающие данные и применяет их напрямую к новым точкам данных для принятия решений.

Такой процесс называют ленивым методом обучения (lazy learning). Это означает, что модель не строит явную функцию или модель на основе обучающих данных во время этапа обучения. Вместо этого она хранит данные и выполняет вычисления только в момент применения модели к новым данным. Такой подход обеспечивает гибкость и адаптивность модели, поскольку она может адаптироваться к новым данным без необходимости переобучения.

Кроме своей простоты, k-NN обладает невероятной эффективностью в решении разнообразных задач, к примеру:

1. Проблемы классификации: Этот метод помогает определить, к какому классу принадлежит объект, например, это спам-письмо или обычное сообщение.
2. Рекомендательные системы: k-NN используется для поиска похожих пользователей или товаров, чтобы предложить что-то подходящее, например, похожие фильмы на те, что вы уже смотрели.
3. Регрессионный анализ: С его помощью можно предсказать значения, например, стоимость недвижимости, основываясь на характеристиках квартиры (площадь, расстояние до метро и т.д.).
4. Здравоохранение и медицина: k-NN помогает определить вероятность заболевания у пациента, сравнивая его данные с данными других пациентов.

В статье мы разберем, как k-NN применяют в задачах классификации и регрессии.

Как работает k-NN?

В основе метода k-NN лежит интуитивная идея: «похожие объекты находятся рядом». Если мы можем измерить, насколько близки объекты, то мы можем использовать эту информацию для принятия решений.

Давайте представим, что у нас есть задача классификации животных на котов и собак. У нас есть данные о размерах тела и длине шерсти для каждого животного. И наша цель научить компьютер отличать котов от собак на основе этих данных, используя метод k ближайших соседей (k-NN).

Теперь представим, что появляется новое животное, и мы хотим определить, является ли оно котом или собакой. И например, если мы выбрали k = 3 (три ближайших соседа), то мы находим три ближайших точки к новому животному.

Если две из этих точек относятся к котам, а одна – к собаке, то мы классифицируем новое животное как кота, так как большинство его ближайших соседей – это коты.

Интерактивная вставка доступна по ссылке

После вводного ликбеза – перейдем к более формальному изложению алгоритма и строго сформулируем в чем заключается метод k-ближайших соседей. Начнем с рассмотрения задачи многоклассовой классификации, а регрессией займемся позже.

k-NN: классификация

Дана обучающая выборка [math]X [/math], представленная набором пар [math]X = (x_i, y_i)_{i = 1}^N[/math], где:
— [math]N[/math] – размер обучающей выборки, то есть количество пар объект-метка;
— [math]x_i[/math] – объекты из пространства [math]\mathbb{X}[/math], где [math]\mathbb{X}[/math] – множество всех возможных объектов;
— [math]y_i[/math] – метки классов, где [math]y_i \in \mathbb{Y} = \{1, \dots, K\}[/math], и [math]K[/math] – общее количество классов.

Таким образом, обучающая выборка состоит из [math]N[/math] пар, где каждая пара представляет объект [math]x_i [/math] и соответствующую ему метку класса [math]y_i [/math].

И пусть также задана некоторая симметричная¹ по своим аргументам функция расстояния [math]p:\mathbb{X} \times \mathbb{X} \to [0, +\infty)[/math]. Здесь [math]\mathbb{X}[/math] представляет собой пространство признаков, а функция расстояния [math]p[/math] измеряет “расстояние” между двумя объектами в этом пространстве. Эта функция должна удовлетворять нескольким требованиям:

1. Положительность: Расстояние не может быть отрицательным: ([math]p(x, y) \geq 0 [/math] для всех [math]x, y \in \mathbb{X}[/math].
2. Идентичность: Расстояние между объектом и самим собой равно нулю: [math]p(x, x) = 0[/math] для всех [math]x \in \mathbb{X}[/math].
3. Симметрия: Расстояние от объекта [math]x[/math] до объекта [math]y[/math] должно быть таким же, как расстояние от [math]y[/math] до [math]x[/math]: [math] p(x, y) = p(y, x) [/math] для всех [math]x, y \in \mathbb{X}[/math].

Так предположим, что требуется классифицировать новый объект [math]\color{#1DA74D}{u}[/math]. Для этого найдём [math]k[/math] наиболее близких к [math]u[/math] в смысле расстояния объектов обучающей выборки:

Метку класса объекта [math]\color{#FFBC00}{x_{\rm in}}[/math] будем обозначать [math]\color{#FFBC00}{y^{(i)}}[/math]. Класс нового объекта тогда естественным образом определим как наиболее часто встречающийся класс среди объектов из [math]X_k(\color{#1DA74D}{u})[/math]:$$a(\color{#1DA74D}{u}) = \underset{y\in \mathbb{Y}}{\operatorname{arg max}} \sum_{i=1}^k \mathbb{I}[\color{#FFBC00}{y_u^{(i)}} = y] $$Формула может показаться страшной, но на самом деле все довольно просто:

• [math]a(\color{#1DA74D}{u})[/math]- это класс нового объекта [math]\color{#1DA74D}{u}[/math], который мы хотим определить.
• [math]\mathbb{Y} [/math] – это множество всех возможных классов.
• [math]y_u^{(i)}[/math] – это класс [math]i[/math]-го ближайшего соседа объекта [math]u[/math].
• [math]\mathbb{I}[\color{#FFBC00}{y_u^{(i)}} = y][/math] – это индикаторная функция, которая равна [math]1[/math], если класс [math]i[/math]-го ближайшего соседа равен [math]y[/math], и [math]0[/math] в противном случае.
• [math] \sum_{i=1}^k \mathbb{I}[\color{#FFBC00}{y_u^{(i)}} = y][/math] – это сумма индикаторов для всех [math]k[/math] ближайших соседей объекта [math]u[/math] с классом [math]y[/math]. Это количество ближайших соседей объекта [math]u[/math] с классом [math]y[/math].
• [math]\underset{y \in \mathbb{Y}}{\operatorname{argmax}}[/math] – это оператор, который выбирает класс [math]y[/math] из множества всех классов [math] \mathbb{Y}[/math], который максимизирует сумму индикаторов.

Таким образом, формула говорит о том, что мы выбираем класс [math]y[/math], который максимально представлен среди ближайших соседей объекта [math]u[/math].

И для каждой метки класса [math]y \in \mathbb{Y}[/math] количество соседей [math]u[/math] с такой меткой можно посчитать, просто просуммировав по всем соседям индикаторы событий, соответствующих тому, что метка соседа равна [math]u[/math]

Подробное описание примера можно найти по этой ссылке.

Также легко заметить, что этот алгоритм позволяет также оценивать вероятности классов. Для этого достаточно просто посчитать частоты классов соседей:$$\mathbb{P}(\color{#1DA74D}{u}\sim y) = \frac{\sum_{i=1}^k \mathbb{I}[\color{#FFBC00}{y_u^{(i)}} = y]}k$$Стоит, однако, понимать, что, хоть такая функция и удовлетворяет свойствам вероятности (она неотрицательна, аддитивна и ограничена единицей), это есть не более чем эвристика.

Несмотря на то что формально фаза обучения отсутствует, алгоритм может легко переобучиться. Вы можете убедиться в этом сами, использовав маленькое количество соседей (например, 1 или 2), — границы классов оказываются довольно сложными. Происходит это из-за того, что параметрами алгоритма можно считать всю обучающую выборку, довольно большую по размеру. Из-за этого алгоритму легко подстроиться под конкретные данные.

Выбор метрики

Вопрос о выборе подходящей функции расстояния [math]ρ[/math] важен для различных задач. В большинстве случаев евклидово расстояние [math]\rho(x, y) = \sqrt{\sum_i (x_i – y_i)^2} [/math] действительно является хорошим выбором, особенно когда данные представлены в евклидовом пространстве и имеют нормальное распределение. Это позволяет учитывать все измерения с одинаковым весом.

Однако существуют ситуации, когда использование других функций расстояния более предпочтительно. Эти функции не обязательно должны соответствовать строгому математическому определению метрики², но мы будем называть их «метриками» для удобства. Рассмотрим несколько из них ниже.

Манхэттенская метрика

$$\rho(x, y) = \sum_i \vert x_i – y_i \vert$$Манхэттенская метрика часто применяется в высокоразмерных пространствах из-за её лучшей устойчивости к выбросам. В случае почти идентичных объектов в пространстве большой размерности, но с существенным отличием в одном признаке, манхэттенская метрика более надежно отражает их близость, в отличие от евклидового расстояния, которое увеличит различия из-за квадрата разности.

Метрика Минковского

$$\rho(x, y) = \left(\sum_i \vert x_i – y_i\vert^p\right)^{1/p}$$Метрика Минковского представляет собой обобщение евклидовой (при [math]p = 2[/math]) и манхэттенской (при [math]p = 1[/math]) метрик. Это обобщение позволяет адаптировать метрику под конкретные требования задачи: чем меньше значение ([math]p[/math]), тем более устойчивой к выбросам и большим различиям становится метрика, что полезно в некоторых высокоразмерных пространствах. При ([math]p = 2[/math]) мы возвращаемся к евклидовой метрике, а при ([math]p = 1[/math]) – к манхэттенской. Этот параметр ([math]p[/math]) дает гибкость выбора степени влияния отдельных признаков на общее расстояние.

Косинусное расстояние

$$\rho(x,y) = 1 – \cos \theta = 1 – \frac{x \cdot y}{|x| |y|}$$Косинусное расстояние измеряет сходство между двумя векторами в многомерном пространстве и часто применяется в анализе текста и задачах машинного обучения для оценки схожести между документами или текстовыми фрагментами. Эта метрика не зависит от нормирования векторов, поскольку вычисляется как косинус угла между ними. Нормирование векторов изменяет их длины, но не влияет на угол, и поэтому не влияет на результат косинусного расстояния.

Значения косинусного расстояния лежат в диапазоне от [math]-1 [/math] до [math] 1 [/math]: [math]1 [/math] указывает на полное совпадение векторов, [math]0 [/math] – на ортогональность, а [math]-1 [/math] – на противоположность. Чем ближе значение к [math]1 [/math], тем более схожи векторы по направлению.

Расстояние Жаккара

$$\rho(A, B) = 1 – \frac{|A\cap B|}{|A\cup B|}$$

Расстояние Жаккара, также известная как коэффициент Жаккара, представляет собой метрику сходства между двумя множествами и вычисляется как отношение размера пересечения множества к их общему размеру. Она широко используется в области информационного поиска, биоинформатики, а также в задачах оценки схожести множеств.

Коэффициент Жаккара принимает значения от [math]0[/math] до [math]1[/math]. [math]0[/math] означает полное отсутствие схожести между множествами, а [math]1[/math] – полное совпадение.

Пример:
Пусть у нас есть множества [math]A = {1, 2, 3}[/math] и [math]B = {2, 3, 4}[/math].

Тогда:
[math] |A \cap B| = {2, 3} [/math]- размер пересечения,
[math] |A \cup B| = {1, 2, 3, 4} [/math] – размер объединения.

И коэффициент Жаккара будет равен:
$$J(A, B) = \frac{|A \cap B|}{|A \cup B|} = \frac{2}{4} = 0.5$$
Таким образом, коэффициент Жаккара для этих двух множеств составляет [math]0.5[/math], что указывает на среднюю степень их схожести.

Взвешенный k-NN

В начале мы отметили, что основой алгоритма k-NN является идея того, что объекты, находящиеся близко друг к другу в пространстве признаков, обычно обладают схожими свойствами. Однако у оригинального алгоритма есть существенный недостаток: он не учитывает расстояния до соседних объектов, что может быть важной информацией.

Давайте разработаем способ устранения этого недостатка. Нам нужно как-то увеличивать влияние близких объектов и уменьшать влияние дальних. Мы можем заметить, что все индикаторы в формуле учитываются с одинаковыми коэффициентами. Из этого следует идея: присвоить индикаторам веса [math](w_i)[/math], которые будут тем выше, чем ближе объект к целевому. Таким образом, мы получаем следующую формулу:$$a(\color{#1DA74D}{u}) = \underset{y\in \mathbb{Y}}{\operatorname{arg max}} \sum_{i=1}^k w_i\mathbb{I}[\color{#FFBC00}{y_u^{(i)}} = y]$$Это нововведение приводит к появлению Взвешенного k-NN (WKNN), где каждый сосед учитывается с индивидуальным весом.

Существует множество вариантов выбора весов для объектов, которые можно разделить на две основные группы. В первой группе веса зависят только от порядкового номера объекта в отсортированном массиве [math]X_k(\color{#1DA74D}{u})[/math] по его близости к [math]u[/math]. Обычно используются линейно [math]\left( w_i = \frac{k+1-i}{k} \right)[/math] или экспоненциально [math] \left( w_i = q^i, \ 0 < q < 1\right)[/math] затухающие веса.

Во второй группе методов вес является некоторой функцией от расстояния. Давайте подумаем, какие должны быть свойства у этой функции. Очевидно, она должна быть положительной на своей области определения, иначе модель будет поощрять несовпадение с некоторыми ближайшими соседями. Также необходимо, чтобы функция монотонно не возрастала, чтобы вес близких соседей был больше, чем далёких. Таким образом вводится так называемая ядерная функция (kernel function) [math]K : \mathbb{R} \to \mathbb{R}[/math], обладающая перечисленными выше свойствами, с помощью которой и высчитывается вес каждого соседа:$$a(\color{#1DA74D}{u}) = \underset{y\in \mathbb{Y}}{\operatorname{arg max}} \sum_{i=1}^k K\left(\frac{\color{#D10000}{\rho}(\color{#1DA74D}{u}, \color{#FFBC00}{x_u^{(i)}})}{h}\right)\mathbb{I}[\color{#FFBC00}{y_u^{(i)}} = y]$$где [math]h[/math] — некое положительное число, которое называется шириной окна.

От выбора ядра зависит гладкость аппроксимации, но на её качество этот выбор почти не влияет. Примеры ядерных функций в порядке увеличения их гладкости:

1. [math]K(x) = \frac12 \mathbb{I} \left[ \vert x \vert \leqslant 1\right][/math] — прямоугольное ядро;
2. [math]K(x) = \left(1 – \vert x \vert \right)\mathbb{I}\left[\vert x \vert \leqslant 1\right][/math] — треугольное ядро (непрерывное);
3. [math]K(x) = \frac34\left(1 – x^2\right) \mathbb{I}\left[ \vert x \vert \leqslant 1\right][/math] — ядро Епанечникова (гладкое везде, кроме –1 и 1);
4. [math]K(x) = \frac{15}{16}\left(1 – x^2\right)^2\mathbb{I}\left[\vert x \vert \leqslant 1\right][/math] — биквадратное ядро (гладкое везде);
5. [math]K(x) = \frac{1}{\sqrt{2\pi}}e^{-2x^2}[/math] — гауссовское ядро (бесконечно гладкое везде).

На практике часто выбирают прямоугольное окно для упрощения или гауссовское окно, особенно когда важна гладкость модели, как в случае регрессии. Выбор ширины окна имеет значительное воздействие на качество модели. Если ширина слишком мала, модель может слишком сильно подстраиваться под обучающую выборку и терять способность обобщения. С другой стороны, при слишком большой ширине окна модель может становиться слишком простой. Нет универсального значения ширины окна, поэтому ее необходимо подбирать индивидуально для каждой задачи.

k-NN: регрессия

Алгоритм K ближайших соседей (KNN) можно успешно расширить на задачу регрессии. Для получения прогнозов существуют два основных метода. Первый подход предполагает использование простого среднего значения целевых переменных для k ближайших соседей:$$a(\color{#1DA74D}{u}) = \frac1k \sum_{i=1}^k \color{#FFBC00}{y_u^{(i)}}$$Второй метод включает в себя взвешенное среднее, где каждый сосед вносит свой вклад в прогноз с учетом веса, вычисленного на основе ядерной функции [math]K[/math]от расстояния до соседа. Эта формула известна как формула Надарая-Ватсона для взвешенного среднего и представляет собой следующее выражение:$$a(\color{#1DA74D}{u}) = \frac{\sum_{i=1}^k K\left(\frac{\color{#D10000}{\rho}(\color{#1DA74D}{u}, \color{#FFBC00}{x_u^{(i)}})}{h}\right) \color{#FFBC00}{y_u^{(i)}}}{\sum_{i=1}^k K\left(\frac{\color{#D10000}{\rho}(\color{#1DA74D}{u}, \color{#FFBC00}{x_u^{(i)}})}{h}\right)} $$Этот метод является одним из непараметрических методов восстановления регрессии, объединенных под названием ядерная регрессия (kernel regression). Здесь [math]\color{#D10000}{\rho}(\color{#1DA74D}{u}, \color{#FFBC00}{x_u^{(i)}})[/math] – расстояние между объектами, [math]h[/math] – параметр, определяющий ширину окна, а [math]K[/math] – ядерная функция. Эти методы предоставляют гибкие варианты для прогнозирования значений в задаче регрессии с использованием алгоритма KNN.

1. Симметричность означает, что порядок аргументов не влияет на значение функции расстояния ↩︎
2. Метрика в математике представляет собой функцию расстояния, которая обычно должна удовлетворять трем основным свойствам:
   — Неотрицательность: [math]d(x, y) \geq 0[/math] для всех [math]x[/math] и [math]y[/math], причем [math]d(x, y) = 0[/math] тогда и только тогда, когда [math]x = y[/math].
   — Симметричность: [math]d(x, y) = d(y, x)[/math] для всех [math]x[/math] и [math]y[/math].
   — Неравенство треугольника: [math]d(x, y) + d(y, z) \geq d(x, z)[/math] для всех [math]x[/math], [math]y[/math] и [math]z[/math]. ↩︎