Алгоритм KNN (k ближайших соседей)

Записаться

Исходные данные: обучающая выборка

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

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

Далее идут два признака, по которым мы будем оценивать каждый фрукт:

• Сладость — насколько фрукт сладкий.
• Кислость — насколько фрукт кислый.

Эти признаки выражены числовыми оценками. Например, у лимона оценки 1 и 9 (несладкий, но очень кислый), у банана — 9 и 1 (сладкий и некислый).

Последний столбец — целевая переменная, или тип фрукта. Это правильный ответ, который мы должны предсказывать. В нашем примере есть три класса:

1. Кислый (лимон, грейпфрут, апельсин, малина).
2. Сладкий (вишня, банан, виноград, арбуз, клубника).
3. Никакой (авокадо).

Это задача мультиклассовой классификации с непересекающимися классами: фрукт не может быть одновременно кислым и сладким.

Важно понимать, что эта таблица заполнена экспертом на основе его опыта. Наша цель — научить машину (модель) воспроизводить этот принцип.

Постановка задачи

Нам поступает новый объект — инжир с оценками: сладость — 7, кислость — 3. Наша задача — определить, к какому классу он принадлежит, используя только данные из обучающей выборки.

В этой простой задаче ответ очевиден: инжир — сладкий. Но представьте, что признаков не два, а сотни или тысячи, и они не такие интуитивно понятные (например, параметры движения звезд). В таких случаях эксперт может классифицировать объекты, опираясь на сложные, неочевидные закономерности, которые он сам не может формализовать. Задача алгоритма машинного обучения — выявить эти скрытые принципы из данных и автоматически классифицировать новые объекты.

Принцип работы алгоритма k-NN

В основе алгоритма лежит понятие расстояния между объектами. Мы предполагаем, что похожие объекты (находящиеся близко друг к другу в пространстве признаков) принадлежат к одному классу.

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

Формула для двух признаков:
Расстояние = √((x1_новый – x1_{известный})² + (x2_новый – x2_{известный})²)

Шаги алгоритма

1. Расчет расстояний: Вычисляем евклидово расстояние от нового объекта (инжира) до каждого объекта из обучающей выборки.
2. Сортировка: Сортируем все объекты по возрастанию расстояния до нашего нового объекта.
3. Выбор соседей: Отбираем k первых (самых близких) объектов из отсортированного списка.
4. Голосование: Смотрим, какой класс встречается чаще всего среди этих k соседей. Этот класс и присваивается новому объекту.

Демонстрация в Excel

1. В таблицу добавляется столбец «Расстояние».
2. В первую ячейку вводится формула для расчета расстояния от инжира до лимона. Координаты (оценки) инжира фиксируются с помощью клавиши F4 (абсолютная ссылка), чтобы они не менялись при растягивании формулы.
3. Формула растягивается на все остальные фрукты. Теперь для каждого фрукта рассчитано его расстояние до инжира.
4. Таблица сортируется по столбцу «Расстояние» по возрастанию (с помощью фильтра).
5. Смотрим на первых k объектов. Возьмем k=4. Четыре ближайших соседа инжира — это сладкие фрукты. Все они принадлежат к классу «сладкий».

Вывод: так как все 4 ближайших соседа — сладкие, мы классифицируем инжир как сладкий.

Выбор параметра k

Параметр k (количество соседей) мы выбираем сами. При k=4 результат однозначен. Если взять k=5, то, возможно, среди соседей окажется один кислый фрукт, и уверенность снизится.

Значение k должно быть осмысленным:

• Слишком большое k захватит объекты из других классов, что приведет к неверной классификации.
• Слишком маленькое k делает выборку непоказательной и чувствительной к шумам.

В нашем случае k=4 — разумный выбор.

Применение алгоритма

Алгоритм k-NN, несмотря на свою простоту, очень эффективен для многих задач мультиклассовой классификации. Принцип, лежащий в его основе — «похожие объекты относятся к одному классу» — естественен и понятен. Этот же алгоритм без изменений можно применять к гораздо более сложным задачам с сотнями признаков, где нет очевидных закономерностей и где невозможно использовать простой человеческий опыт для классификации.

Краткие итоги

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

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

Главный практический вызов при использовании этого метода — корректный выбор количества «соседей» (параметра k). Этот параметр напрямую управляет балансом между точностью и устойчивостью классификации. Небольшое значение делает модель чувствительной к локальным особенностям данных и возможному шуму, в то время как слишком большое — приводит к размыванию границ между классами и принятию решений на основе глобального, а не локального сходства. Осознанный выбор этого параметра требует понимания структуры данных и целей конкретной задачи.

Таким образом, рассмотренный алгоритм представляет собой мощный и универсальный инструмент. Его сила — в способности к обучению на основе примеров и масштабировании на задачи высокой размерности, где человеческая интуиция бессильна. Простота реализации и интерпретируемость результата делают его хорошей отправной точкой для решения многих прикладных задач анализа данных.