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

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

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

Пример классификации k-ближайших соседей.

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

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

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

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

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

         d(p, q) = d(q, p) = sqrt{(q_1 - p_1)^2 + (q_2 - p_2)^2 + ...+ (q_n - p_n)^2} =sqrt{sum_{i=1}^n(q_i - p_i)^2}     

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

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

         x' = (x - min[X])/(max[X] - min[X])     

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

Z-нормализация:

         x' = (x - M[X])/σ[X]     

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

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

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

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

• Отсортируйте упорядоченную коллекцию расстояний и индексов от наименьшего до наибольшего, в порядке возрастания.
• Выберите первые 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 (плата за проезд).

         # Загружаем данные train_df = pd.read_csv('/kaggle/input/titanic/train_data.csv')  # Избавляемся от двух столбцов без нужной информации train_df = train_df.drop(columns=['Unnamed: 0', 'PassengerId'])  from sklearn.neighbors import KNeighborsClassifier  predictors = ['Age', 'Fare']  outcome = 'Survived'   new_record = train_df.loc[0:0, predictors]  X = train_df.loc[1:, predictors]  y = train_df.loc[1:, outcome]   kNN = KNeighborsClassifier(n_neighbors=20)  kNN.fit(X, y)  kNN.predict(new_record) print(kNN.predict_proba(new_record))   #[результат/вывод]: [[0.7 0.3]]     

Здесь вероятность выживания составляет 0.3 – 30%.

Далее мы настраиваем алгоритм k-NN на поиск и использование 20 ближайших соседей, чтобы оценить состояние пассажира. Для наглядности выводим 20 первых соседей новой записи с помощью импортированного метода kneighbors. Реализация выглядит следующим образом:

         nbrs = knn.kneighbors(new_record) maxDistance = np.max(nbrs[0][0])  fig, ax = plt.subplots(figsize=(10, 8)) sns.scatterplot(x = 'Age', y = 'Fare', style = 'Survived',                  hue='Survived', data=train_df, alpha=0.3, ax=ax) sns.scatterplot(x = 'Age', y = 'Fare', style = 'Survived',                  hue = 'Survived',                  data = pd.concat([train_df.loc[0:0, :], train_df.loc[nbrs[1][0] + 1,:]]),                  ax = ax, legend=False) ellipse = Ellipse(xy = new_record.values[0],                    width = 2 * maxDistance, height = 2 * maxDistance,                   edgecolor = 'black', fc = 'None', lw = 1) ax.add_patch(ellipse) ax.set_xlim(.25, .29) ax.set_ylim(0, .03)  plt.tight_layout() plt.show()     

Результат работы кода:

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

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

         nbrs = knn.kneighbors(new_record) nbr_df = pd.DataFrame({'Age': X.iloc[nbrs[1][0], 0],                           'Fare': X.iloc[nbrs[1][0], 1],                          'Survived': y.iloc[nbrs[1][0]]}) nbr_df     

Результатом будет таким:

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

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

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

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

Преимущества:

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

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

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

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

Недостатки:

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

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

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

В заключение

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

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