Skip to content

02. Идея KNN: модель без обучения ​

В этом уроке мы разберём, что вообще такое K-ближайших-соседей (KNN), почему его называют «моделью» хотя бы ни одного веса она не обучает, и разберём скелет класса KNN из knn.py, чтобы понимать, что и куда будем вкладывать в следующих уроках.

Проблема, которую решает KNN ​

У нас есть обучающая выборка: тысячи изображений цифр с метками 0..9. Нужно предсказать метку для нового изображения. Классическая нейросеть «обучает» миллионы весов. KNN делает по-другому:

Весь алгоритм KNN: при «обучении» просто запомни обучающую выборку. При предсказании найди в ней k ближайших соседей нового примера и отдай голос большинству их меток.

Собственного параметра, который меняется, нет — единственный «гиперпараметр» это k. Поэтому говорят, что KNN — ленивый классификатор (lazy learning): вся работа (расчёт расстояний) перенесена в момент предсказания, а не обучения.

Как считать «близость»: метрики расстояния ​

Для KNN нужна мера расстояния между двумя точками (в нашем случае — между «векторами-изображениями»). Две основные:

  • L1 (манхэттенское) — сумма по модулям разниц: L1=∑i|xi−yi|
  • L2 (евклидово) — корень из суммы квадратов: L2=∑i(xi−yi)2

В задании используется L1 (см. докстринг класса: «K-neariest-neighbor classifier using L1 loss»). Это наглядно видно по формуле: np.sum(np.abs(...)).

Ручной пример в 2D ​

Пусть есть две точки: A=(1,2) и B=(4,6).

  • L1: |1−4|+|2−6|=3+4=7
  • L2: (1−4)2+(2−6)2=9+16=25=5

Обратите внимание: для разных точек L1 и L2 дают разные числа. Но! Для ранжирования соседей (кто ближе, а кто дальше) это часто не критично — важен именно порядок. (Формально — не всегда одинаковый, но на практике порядки близки.)

Что такое k и зачем его выбирать ​

k — количество соседей, чьим голосам доверяем.

  • k=1 — доверяем самому близкому соседу. Максимально гибко, но очень чувствительно к шуму: один выброс рядом с новой точкой ломает предсказание.
  • k=5, k=10 — голосуем большинством из нескольких. Гладит шум, но может «размывать» границу между классами (соседи из разных классов смешиваются).

Это классический баланс bias–variance: маленький k — низкий bias, высокая дисперсия (много «ямок» в границе решения); большой k — наоборот. Подбирать k будем в уроке 06 через кросс-валидацию.

Интерактив: почувствуйте границу решения ​

На стенде ниже — плоскость 2D с обучающими точками двух классов (синие и красные). Кликните по пустому месту — там появится «новая точка». Стенд подсветит её ближайших соседей и раскрасит карту решений: каждый пиксель плоскости — метка, которую KNN дал бы этой позиции. Крутите слайдер k и переключайте метрику (L1/L2) — и смотрите, как деформируется граница.

Наглядно увидите: при k=1 граница «рваная» и прыгает от одного выброса, при большом k — гладкая.

Кликните по плоскости, чтобы задать тестовую точку.

Разбор скелета knn.py ​

Разберём структуру класса, чтобы дальше не запутаться. Ключевое: fitничего не обучает — просто запоминает. Вся логика предсказания разбита на блоки, каждый из которых — отдельный TODO.

python
class KNN:
    """K-neariest-neighbor classifier using L1 loss"""
    def __init__(self, k=1):
        self.k = k

    def fit(self, X, y):
        self.train_X = X
        self.train_y = y

    def predict(self, X, num_loops=0):
        # 1) выбрать реализацию расчёта расстояний по num_loops
        if num_loops == 0:
            dists = self.compute_distances_no_loops(X)
        elif num_loops == 1:
            dists = self.compute_distances_one_loop(X)
        else:
            dists = self.compute_distances_two_loops(X)
        # 2) выбрать голосование по типу меток
        if self.train_y.dtype == np.bool:
            return self.predict_labels_binary(dists)
        else:
            return self.predict_labels_multiclass(dists)

Важные наблюдения:

  • predict — это «оркестратор». Он сам не считает расстояния и не голосует — он лишь выбирает нужный метод и вызывает его. Поэтому все TODO лежат «под ним», а не в predict.
  • num_loops выбирает как считать расстояния: 0 — без циклов (векторинг, самый быстрый), 1 — один цикл, 2 — два цикла (самый медленный, но самый прозрачный). Все три должны давать одинаковый результат dists.
  • Тип меток выбирает как голосовать: если train_y.dtype == np.bool (бинарная задача: например, «0 vs 9»), вызывается predict_labels_binary, иначе — predict_labels_multiclass (10 классов).

Почему np.bool? В бинарном режиме метки — True/False, и предсказание тоже возвращается как bool-массив. Это упрощает метрики урока 05 (TP/FP/FN/TN считаются именно для бинарного предсказания).

Как устроена «матрица расстояний» dists ​

Это центральный объект KNN. После расчёта dists — это матрица размера (num_test, num_train):

  • строка i — расстояния от i-го тестового примера до всех обучающих;
  • dists[i, j] — расстояние между тестовым X[i] и обучающим train_X[j].

Затем для предсказания i-го примера нам нужны индексы k самых мелких элементов в строке dists[i] — это и есть его k ближайших соседей.

Что мы уже умеем и что впереди ​

ВопросОтветУрок
Что делает fitзапоминает train_X, train_yэтот
Что такое kсколько соседей голосуютэтот
Как считается расстояние (L1)np.sum(np.abs(x - x'))этот / 03–04
Как построить distsтри реализации03, 04
Как «выбрать k ближайших» и проголосоватьargpartition + bincount05
Как оценить качествоprecision/recall/F1/acc05
Как подобрать k5-fold кросс-валидация06

Практика ​

1. Для точек A=(0,0), B=(3,4) вычислите L1 и L2 расстояния вручную. Какое из них больше? При каком расположении точек L1 и L2 дают равные значения? (Подсказка: подумайте о точках на одной прямой через начало координат.)

2. У вас 3 ближайших соседа тестовой точки, их метки: [0, 0, 1]. Что вернёт KNN при k=3? А если метки [0, 1, 1]? Что, если ровно 50/50 (например, соседи [0, 1] при k=2)? Как это разрешить в коде?

3. Откройте стенд WwKnnLab выше. Кликните в область, где синие и красные точки перемешаны. Какой k даст «стабильное» (не прыгающее при перемещении точки) предсказание именно в этой зоне? Почему?

Показать решения

1. L1 = |0−3|+|0−4|=3+4=7. L2 = 32+42=5. L1 больше. L1 и L2 равны, когда все, кроме одной, координат совпадают (тогда разница — в одной координате: |d|=d2=|d|). Например, (0,0) и (5,0): L1=5, L2=5.

2. [0,0,1] → большинство 0 → предсказание 0. [0,1,1] → большинство 1 → 1. При 50/50 голосов — ничья; в коде её разрешает argmax (берёт первый максимальный), так что результат зависит от порядка классов. В задании такая ситуация маловероятна при чётном k и 2 классах, но имейте в виду.

3. В перемешанной зоне с маленьким k предсказание прыгает (каждый сосед решает всё). Большой k усредняет множество точек и даёт устойчивую метку. Ответ зависит от конкретного расклада — попробуйте на стенде.

Итоги урока ​

  • KNN — «ленивый» классификатор: fit только запоминает, вся работа — в predict;
  • Задание использует метрику L1 (np.sum(np.abs(...)));
  • k балансирует bias/variance: маленький — чувствителен к шуму, большой — размывает границу;
  • dists — матрица (num_test, num_train); предсказание строки i — из k минимальных её элементов;
  • predict — оркестратор: num_loops выбирает расстояния, тип меток — голосование;
  • Бинарный режим определяется по train_y.dtype == np.bool.

Следующий урок — 03. Матрица расстояний: циклы: реализуем два «циклических» метода dists.