Метод K-ближайших соседей (kNN)
Метод K-ближайших соседей – это алгоритм Машинного обучения (ML), который используют для решения задач классификации и регрессии.
Алгоритм Контролируемого обучения (Supervised Learning), в отличие от Неконтролируемого (Unsupervised Learning), полагается на размеченные входные данные для получения соответствующего результата с новыми данными без Ярлыков (Label).
Представьте, что компьютер – это ребенок, а мы – это учителя. Обучая ребенка узнавать лошадь, мы покажем ему несколько разных картинок, причем на некоторых из них действительно изображены эти животные, а остальные могут быть изображениями чего угодно (кошек, собак и проч.). Когда мы видим лошадь, мы говорим «лошадь!», а когда видим другого зверя – «Нет, не лошадь!» Спустя какое-то количество изображений ребенок (компьютер) будет правильно (в большинстве случаев) узнавать парнокопытное на картинках. Это контролируемое Машинное обучение с целью классификации изображений по видам животных.
Задача классификации имеет дискретное значение на выходе. Например, «любит пиццу с ананасами» и «не любит пиццу с ананасами» дискретны. Здесь нет никакого промежуточного варианта:

На этом изображении – базовый пример данных классификации. У нас есть Переменная-предиктор (Predictor Variable), или набор таковых, и репрезентативные метки 1 и 0. Мы попытаемся предсказать, любит ли человек пиццу с ананасами, используя его возраст.
Алгоритм kNN предполагает, что похожие Наблюдения (Observation), в данном случае потребители пиццы, существуют в непосредственной близости:

В большинстве случаев похожие наблюдения расположены близко друг к другу. kNN улавливает идею сходства (иногда называемого расстоянием, близостью или близостью), благодаря, как правило, вычислению Евклидова расстояния (Euclidean Distance) между точками на графике.
Стандартная последовательность
- Загрузите данные
- Выберите число k, характеризующее количество соседей в кластере
- Вычислите Евклидово расстояние между всеми точками попарно. Отсортируйте получившийся набор расстояний от наименьшего к наибольшему. Затем выберите первые k записей из отсортированной коллекции.
- Для задач классификации определите Моду (Mode) – наиболее распространенную метку кластера.
Метод k-ближайших соседей и Scikit-learn
Для демонстрации работы метода используем специальный игрушечный датасет, который генерируется с помощью встроенного метода make_moons
. Для начала импортируем необходимые библиотеки:
import plotly
import plotly.graph_objects as go
import numpy as np
import sklearn
from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
Загрузим игрушечный датасет. make_moons сгенерирует два перекрещивающихся полукруга на двумерном графике для демонстрации возможностей классификатора:
# Переменная повлияет на сглаженность разделительных границ
mesh_size = .2
# Параметр повлияет на ширину каждой из зон на графике
margin = 0.25
# noise добавляет реалистичный шум
X, y = make_moons(noise = 0.3, random_state = 0)
# Разделим датасет на учебную и тестовую части
X_train, X_test, y_train, y_test = train_test_split(
X, y.astype(str), test_size = 0.25, random_state = 0)
Конечно, луны – это метафора, выглядят эти пересекающиеся наборы точек примерно так:

Создадим и параметризируем двумерную сетку. Для этого определим минимальное и максимальное значение по осям x и y и добавим margin по краям, чтобы в зоне видимости оказались все наблюдения:
# X[:, 0].min() выберет из всех значений координат x минимальное значение
x_min, x_max = X[:, 0].min() - margin, X[:, 0].max() + margin
y_min, y_max = X[:, 1].min() - margin, X[:, 1].max() + margin
# np.arange создаст вектор, где каждое следующее значение равноудалено
# от предыдущего (шаг – mesh_size). Это ляжет в основу шкал на осях.
xrange = np.arange(x_min, x_max, mesh_size)
yrange = np.arange(y_min, y_max, mesh_size)
# np.meshgrid() создаст координатную матрицу
xx, yy = np.meshgrid(xrange, yrange)
# Создадим классификатор и классифицируем тренировочные данные
# weights = 'uniform' означает, что у всех точек
# одинаковое влияние на границы классификации
clf = KNeighborsClassifier(15, weights = 'uniform')
clf.fit(X, y)
# Ось z – это непосредственно предсказания
# np.c_ соединит последовательности координат в столбец
# ravel() сделает из этого столбца одномерный массив
Z = clf.predict_proba(np.c_[xx.ravel(), yy.ravel()])[:, 1]
Z = Z.reshape(xx.shape)
Отобразим график – "карту уверенности" с исходными точками "лун":
# Обозначим учебные и тренировочные данные разными маркерами для наглядности
trace_specs = [
[X_train, y_train, '0', 'Train', 'square'],
[X_train, y_train, '1', 'Train', 'circle'],
[X_test, y_test, '0', 'Test', 'square-dot'],
[X_test, y_test, '1', 'Test', 'circle-dot']
]
fig = go.Figure(data = [
go.Scatter( # специальная обертка Plotly: наслоим для наглядности "луны"
x = X[y == label, 0], y = X[y == label, 1],
# Настроим легенду графика
name = f'{split} Split, Label {label}',
mode = 'markers', marker_symbol = marker
)
for X, y, label, split, marker in trace_specs
])
# Зададим размер маркера, толщину обводки и цвет
fig.update_traces(
marker_size = 12, marker_line_width = 1.5,
marker_color = "white"
)
fig.add_trace(
go.Contour( # Теперь отобразим саму карту "уверенности"
x = xrange, # Шкалы размечаются с помощью равноудаленных точек
y = yrange,
z = Z, # Третье измерение – это цвет как степень уверенности
showscale = False,
colorscale = 'aggrnyl', # Предустановленная цветовая схема
opacity = 1,
name = 'Score',
hoverinfo = 'skip'
)
)
fig.show()
Мы получим контур, характеризующий степени уверенности алгоритма в принадлежности той или иной точки к сгенерированным группам (точки каждой группы как бы расположились в форме т.н. полулуний). Обратите внимание на тестовые маркеры с точками в центре: модель не всегда классифицирует их верно; попадаются те, что со 100%-й уверенностью алгоритм отнес к неверной группе, поскольку располагаются они далеко, на самой темно-зеленой части графика:

Ноутбук, не требующий дополнительной настройки на момент написания статьи, можно скачать здесь.
Фото: @patschrei