5 февр. 2021 г. 4 min read Основы

Метод K-ближайших соседей (kNN)

Метод K-ближайших соседей – это алгоритм Машинного обучения (ML), который используют для решения задач классификации и регрессии.

Алгоритм Контролируемого обучения (Supervised Learning), в отличие от Неконтролируемого (Unsupervised Learning), полагается на размеченные входные данные для получения соответствующего результата с новыми данными без Ярлыков (Label).

Представьте, что компьютер – это ребенок, а мы – это учителя. Обучая ребенка узнавать лошадь, мы покажем ему несколько разных картинок, причем на некоторых из них действительно изображены эти животные, а остальные могут быть изображениями чего угодно (кошек, собак и проч.). Когда мы видим лошадь, мы говорим «лошадь!», а когда видим другого зверя – «Нет, не лошадь!» Спустя какое-то количество изображений ребенок (компьютер) будет правильно (в большинстве случаев) узнавать парнокопытное на картинках. Это контролируемое Машинное обучение с целью классификации изображений по видам животных.

Задача классификации имеет дискретное значение на выходе. Например, «любит пиццу с ананасами» и «не любит пиццу с ананасами» дискретны. Здесь нет никакого промежуточного варианта:

Классификация любителей пиццы на основе возраста (1 – любит)

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

Алгоритм kNN предполагает, что похожие Наблюдения (Observation), в данном случае потребители пиццы, существуют в непосредственной близости:

Результат классификации kNN – сегментированные кластеры наблюдений

В большинстве случаев похожие наблюдения расположены близко друг к другу. 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%-й уверенностью алгоритм отнес к неверной группе, поскольку располагаются они далеко, на самой темно-зеленой части графика: