Примеры задач/вопросов по k-NN

Задача 1

Пусть на плоскости дано два объекта двух разных классов.
Покажите, что если выполнять классификацию методом 1-NN с евклидовым расстоянием, то разделяющей границей между классами будет прямая линия.

Задача 2

Пусть даны следующие точки в одномерном пространстве: $$X = [1,2,4,8,16,32]$$ с соответствующими метками классов: $$y = [1,2,2,1,2,1]$$

Обозначим через $x^*$ объект, для которого необходимо выполнить классификацию, а через $a(x)$ - алгоритм, в соответствии с которым выполняется классификация.

Найдите и выпишите границы классов, если $a(x)$ это

  1. 1-NN
  2. 2-NN
  3. 2-NN, с весами обратно пропорциональными расстоянию до ближайших соседей
  4. 3-NN

Для всех $a(x)$ мера близости - евклидова. В случае равнозначности, выставляется класс с наименьшей меткой.

Задача 3

Перечислите все числовые гиперпараметры метода k-NN и определите как они влияют на переобучение/недообучение

Задача 4

По графику ниже выполните регрессию точки с координатой в $x=3.5$ с помощью взвешенного метода k-NN, где $k=3$, расстояние - евклидово, а вес $i$-го ближайшего соседа определяется как $$w_i = \frac{k - i + 1 }{ k }$$.

In [9]:
plt.show()

Задача 5

Оцените вычислительную сложность предсказания с помощью метода $k$-NN по данным с $N$ объектами и $D$ признаками