Сегодня мы узнаем
Метод k ближайших соседей (k nearest neighbours, k-NN) является одним из простейших алгоритмов машинного обучения. Несмотря на свою простоту, k-NN может превзойти более мощные алгоритмы и используется во множестве приложений, таких как экономическое прогнозирование, сжатие данных и генетика. Например, k-NN использовалась в исследовании по функциональной геномике в 2006 году, где гены определялись на основе их профилей экспрессии.
Начнем с введения некоторых определений и обозначений.
k-NN входит в число supervised алгоритмов или алгоритмов «обучения с учителем». Это означает, что нам предоставляется набор данных $(x_1, y_1), \ldots, (x_n, y_n)$, в котором приведены признаки и верные ответы для $n$ каких-то объектов. Целью является на основе предоставляемой выборки найти связь между $x$ и $y$, то есть восстановить функцию $h: X \rightarrow Y$. Имея такую функцию, мы можем предсказать $y$ по имеющемуся наблюдению $x$.
Для нового объекта с вектором признаков $x_{new}$ алгоритм k-NN находит $k$ ближайших к $x_{new}$ точек среди $x_1, \ldots, x_n$. Пусть они имеют индексы $i_1, \ldots, i_k$. Для задачи регрессии в качестве $h(x)$ используется среднее соответствующих значений $y$, то есть
$$h(x)=\frac{1}{k}\sum_{i=1}^k y_{i_k}.$$Для задачи классификации в качестве $h(x)$ используется то значение $y$, которое встречается среди $y_{i_1}, \ldots, y_{i_k}$ чаще всего (если таких значений несколько, выбирается какое-то одно из них — например, самое маленькое для какого-то порядка на классах).
Чтобы лучше понять, как работает kNN, реализуем его «вручную». Наша реализация будет довольно неэффективной — для реальной работы мы будем использовать реализацию в библиотеке scikit-learn, которая использует хитрые структуры данных для быстрого поиска ближайшего соседа. Мы же будем банально сортировать все элементы по близости к новому и выбирать k самых близких. Это дико неэффективно (в серьёзных приложениях используются k-d деревья, но зато понятно, как работает.
import numpy as np
Пусть $d=2$ и у нас есть три объекта в обучающей выборке. Зададим их как-нибудь.
x_train = np.array([[2, 3],
[1, 5],
[0, 0]])
y_train = np.array([10, 20, 30])
Есть также новый объект, для которого мы хотим построить предсказание.
x_new = np.array([1, 2])
Во-первых, нам нужно найти расстояния между x_new
и остальными объектами в x_train
. Проще всего это сделать так: найти их разности, затем найти нормы этих разностей. Получатся квадраты расстояний, но нам нужно их просто сравнить. Затем нужно использовать np.linalg.norm
, чтобы найти их нормы. Вам придётся передать ему правильное значение параметра axis
, чтобы были посчитаны нормы каждого из векторов, записанных по строкам.
Воспользуемся функцией np.argsort
. Она выдаёт набор индексов, такой, что если брать элементы с этими индексами, то массив окажется отсортированным. Например.
np.argsort(np.array([4, 100, 12, 3, 2, 10]))
array([4, 3, 0, 5, 2, 1])
Самый маленький элемент имеент индекс 4, следующий по малости — 3, потом 0 и т.д.
Если использовать массив индексов в качестве аргумента квадратных скобок, будут выбраны элементы, соответствующие этим индексам.
arr = np.array([0, 10, 20, 30, 40])
arr[np.array([1, 0, 1, 2])]
array([10, 0, 10, 20])
Получаем для нашей задачи:
def kNN_regression(x_train, y_train, x_new, k=1):
"""
x_train is np.array with shape (n, d) (matrix with n rows, d columns)
y_train is np.array with shape (n, ) (1-dimensional array with n elements)
x_new is np.array with shape (d,) (1-dimensional array with d elements)
"""
# YOUR CODE HERE
pass
kNN_regression(x_train = np.array([[12, 3],
[4, 5],
[1, 5]]),
y_train = np.array([10, 20, 30]),
x_new = np.array([11, 4]),
k = 2)
15.0
Посмотрим, как работает k-NN на примере синтезированных данных. Пусть реальная зависимость $y$ и $x$ задаётся правилом $y=x^2+\varepsilon$, где $\varepsilon$ — некоторый шум с нулевым матожиданием.
Точнее, мы будем рассматривать следующую модель:
\begin{gather} X \sim Uniform(-1, 1);\\ \varepsilon \sim \mathcal N(0, \varepsilon_0^2)\\ Y = X^2 + \varepsilon, \end{gather}где $Uniform(-1, 1)$ — равномерное распределение на отрезке $[-1, 1]$, переменные $X$ и $\varepsilon$ независимы.
n = 10
np.random.uniform(low=-1, high=1, size=(n, 1))
array([[-0.49069251], [-0.91693958], [-0.01299215], [ 0.92879661], [ 0.33796647], [ 0.46056795], [ 0.90023528], [-0.4392232 ], [-0.74121161], [-0.77583399]])
def f(x):
return x ** 2
# Y | X = X^2 + \eps
def make_data(n, eps0):
"""
Return x, y
x.shape == (n, 1)
y.shape == (n,)
"""
# YOUR CODE
return x, y
Как обсуждалось на лекции, наилучшим предсказанием $y$ для данного $x$ с точки зрения минимизации ожидаемой ошибки для квадратичной функции потерь является условное матожидание $E[Y\mid X=x]$. Для нашей модели
$$E[Y\mid X=x]=x^2.$$import matplotlib.pyplot as plt
%matplotlib inline
Посмотрим, как работает k-NN для наших данных.
X, Y = make_data(30, 0.1)
def plot_kNN(X, Y, k, **kwargs):
plt.plot(X[:, 0], Y, 'o', label="data", **kwargs)
x_grid = np.linspace(-1, 1, 200)
plt.plot(x_grid, f(x_grid), color='tomato', lw=2, label="$E[Y\mid X=x]$")
plt.plot(x_grid, [kNN_regression(X, Y, x_new, k) for x_new in x_grid],
'g-', label="{}-NN prediction".format(k), lw=2)
plt.legend()
plt.xlabel("X")
plt.ylabel("Y")
plot_kNN(X, Y, 1)
plot_kNN(X, Y, 2)
plot_kNN(X, Y, 15)
Что будет, если увеличить количество данных?
X, Y = make_data(100, 0.1)
plot_kNN(X, Y, 1)
plot_kNN(X, Y, 5, alpha=0.5)
plot_kNN(X, Y, 15, alpha=0.5)
X, Y = make_data(1000, 0.1)
plot_kNN(X, Y, 35, markersize=3, alpha=0.03)
Теорема. Если $f(x)=E[Y\mid X=x]$ является непрерывной функцией от $x$, при некоторых дополнительных условиях, k-NN-регрессия стремится к $f(x)$ при $k, N \to \infty$, т.ч. $k/N\to 0$.
Основная идея: если данных очень много, то можно выбрать такое большое $k$, которое было бы при этом мало по сравнению с $N$. При этом $k$ ближайших соседей для точки $x_{new}$ будут лежать очень близко к ней, и, за счёт того, что $k$ большое, k-NN оценка будет достаточно близкой к истинному матожиданию $f(x_{new})$.
**
¶def foo(x, y):
print(f"x = {x}, y = {y}")
foo(3, 4)
x = 3, y = 4
foo(x=2, y=3)
x = 2, y = 3
params = {'x': 2, 'y': 3}
foo(x=params['x'], y=params['y'])
x = 2, y = 3
Вот так можно сделать это коротко:
foo(**params)
x = 2, y = 3
def EPE(f, L, make_data, data_args, f_args):
X_new, Y_new = make_data(**data_args)
return sum(L(y_new, f(x_new, **f_args))
for x_new, y_new in zip(X_new, Y_new)) / len(X_new)
def f(x, k):
return kNN_regression(X, Y, x, k)
def L(y, y_hat):
return (y - y_hat) ** 2
n_train = 300
eps0 = 0.3
X, Y = make_data(n=n_train, eps0=eps0)
k = range(1, n_train)
# построить зависимость приближения к EPE от k для k \in [1, n_train]
X, Y = make_data(n=n_train, eps0=eps0)
X_train = X[:n_train * 2 // 3]
Y_train = Y[:n_train * 2 // 3]
X_test = X[n_train * 2 // 3:]
Y_test = Y[n_train * 2 // 3:]
def kv_loss(k):
return sum(L(y_new, kNN_regression(X_train, Y_train, x_new, k=k))
for x_new, y_new in zip(X_test, Y_test)) / len(X_test)
k = range(1, 300)
plt.plot(k, [kv_score(k_) for k_ in k])
[<matplotlib.lines.Line2D at 0x7fd1115932b0>]
Напишите функцию kNN_classifier(x_train, y_train, x_new, k=1)
по аналогии с kNN_regression
. Вместо взятия среднего нужно выбрать значение $y$, которое встречается среди $k$ ближайших соседей чаще всего. (Подсказка: оно называется модой.)
def kNN_classifier(x_train, y_train, x_new, k=1):
# YOUR CODE HERE
pass