Метод ближайших соседей дерево решений

У нас есть тестовый образец в виде зеленого круга. Синие квадраты мы обозначим как класс 1, красные треугольники – класс 2.
Зеленый круг должен быть классифицирован как класс 1 или класс 2. Если рассматриваемая нами область является малым кругом, то объект классифицируется как 2-й класс, потому что внутри данного круга 2 треугольника и только 1 квадрат.
Если мы рассматриваем большой круг (с пунктиром), то круг будет классифицирован как 1-й класс, так как внутри круга 3 квадрата в противовес 2 треугольникам.

Теоретическая составляющая алгоритма k-NN

Помимо простого объяснения, необходимо понимание основных математических составляющих алгоритма k-ближайших соседей.

Евклидова метрика (евклидово расстояние, или же Euclidean distance) – метрика в евклидовом пространстве, расстояние между двумя точками евклидова пространства, вычисляемое по теореме Пифагора. Проще говоря, это наименьшее возможное расстояние между точками A и B. Хотя евклидово расстояние полезно для малых измерений, оно не работает для больших измерений и для категориальных переменных. Недостатком евклидова расстояния является то, что оно игнорирует сходство между атрибутами. Каждый из них рассматривается как полностью отличный от всех остальных.

Формула вычисления Евклидова расстояния:

Другой важной составляющей метода является нормализация. Разные атрибуты обычно обладают разным диапазоном представленных значений в выборке. К примеру, атрибут А представлен в диапазоне от 0.01 до 0.05, а атрибут Б представлен в диапазоне от 500 до 1000). В таком случае значения дистанции могут сильно зависеть от атрибутов с бо́льшими диапазонами. Поэтому данные в большинстве случаев проходят через нормализацию. При кластерном анализе есть два основных способа нормализации данных: MinMax-нормализация и Z-нормализация.

Читайте также: Срок жизни дерева ясень

MinMax-нормализация осуществляется следующим образом:

в данном случае все значения будут находиться в диапазоне от 0 до 1; дискретные бинарные значения определяются как 0 и 1.

где σ – среднеквадратичное отклонение. В данном случае большинство значений попадает в диапазон.

Каков порядок действий?

Загрузите ваши данные.
Инициализируйте k путем выбора оптимального числа соседей.
Для каждого образца в данных:

Вычислите расстояние между примером запроса и текущим примером из данных.
Добавьте индекс образца в упорядоченную коллекцию, как и его расстояние.

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

Реализация на языке Python

Для демонстрации мы будем использовать самое распространенное соревнованию-песочницу на Kaggle: Titanic. Данные вы можете найти здесь. Мы стремимся использовать python-библиотеку для машинного обучения scikit-learn. Мы используем набор данных «Титаник» для логистической регрессии.

Набор данных состоит из 15 столбцов, таких как sex (пол), fare (плата за проезд), p_class (класс каюты), family_size (размер семьи), и т. д. Главным признаком, который мы и должны предсказать в соревновании, является survived (выжил пассажир или нет).

Дополнительный анализ показал, что находящиеся в браке люди имеют больший шанс на то, чтобы быть спасенными с корабля. Поэтому были добавлены еще 4 столбца, переименованные из Name (Имя), которые обозначают мужчин и женщин в зависимости от того, были они женаты или нет (Mr, Mrs, Mister, Miss).

Чтобы наглядно продемонстрировать функциональность k-NN для предсказания выживания пассажира, мы рассматриваем только два признака: age (возраст), fare (плата за проезд).

Как видите, на графике показаны 20 ближайших соседей, 14 из которых связаны с теми, кто не выжил (вероятность 0,7 – 70%), а 6 связаны с выжившими (вероятность 0,3 – 30%).

Мы можем просмотреть первые 20 ближайших соседей для заданных параметров при помощью следующего кода:

Выбор Оптимального значения для k-NN

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

Низкое значение k, например, 1 или 2, может привести к эффекту недообучения модели.
Высокое значение k на первый взгляд выглядит приемлемо, однако возможны трудности с производительностью модели, а также повышается риск переобучения.

Преимущества и Недостатки

Алгоритм прост и легко реализуем.

Не чувствителен к выбросам.

Нет необходимости строить модель, настраивать несколько параметров или делать дополнительные допущения.

Алгоритм универсален. Его можно использовать для обоих типов задач: классификации и регрессии.

Алгоритм работает значительно медленнее при увеличении объема выборки, предикторов или независимых переменных.

Из аргумента выше следуют большие вычислительные затраты во время выполнения.

Всегда нужно определять оптимальное значение k.

В заключение

Метод k-ближайших соседей (k-nearest neighbors) – это простой алгоритм машинного обучения с учителем, который можно использовать для решения задач классификации и регрессии. Он прост в реализации и понимании, но имеет существенный недостаток – значительное замедление работы, когда объем данных растет.

Алгоритм находит расстояния между запросом и всеми примерами в данных, выбирая определенное количество примеров (k), наиболее близких к запросу, затем голосует за наиболее часто встречающуюся метку (в случае задачи классификации) или усредняет метки (в случае задачи регрессии).

Хочу освоить алгоритмы и структуры данных, но сложно разобраться самостоятельно. Что делать?

Алгоритмы и структуры данных действительно непростая тема для самостоятельного изучения: не у кого спросить и что-то уточнить. Поэтому мы запустили курс «Алгоритмы и структуры данных», на котором в формате еженедельных вебинаров вы:

изучите сленг, на котором говорят все разработчики независимо от языка программирования: язык алгоритмов и структур данных;
научитесь применять алгоритмы и структуры данных при разработке программ;
подготовитесь к техническому собеседованию и продвинутой разработке.

Курс подходит как junior, так и middle-разработчикам.

Источник