Appearance
02. Идея KNN: модель без обучения
В этом уроке мы разберём, что вообще такое K-ближайших-соседей (KNN), почему его называют «моделью» хотя бы ни одного веса она не обучает, и разберём скелет класса KNN из knn.py, чтобы понимать, что и куда будем вкладывать в следующих уроках.
Проблема, которую решает KNN
У нас есть обучающая выборка: тысячи изображений цифр с метками 0..9. Нужно предсказать метку для нового изображения. Классическая нейросеть «обучает» миллионы весов. KNN делает по-другому:
Весь алгоритм KNN: при «обучении» просто запомни обучающую выборку. При предсказании найди в ней
kближайших соседей нового примера и отдай голос большинству их меток.
Собственного параметра, который меняется, нет — единственный «гиперпараметр» это k. Поэтому говорят, что KNN — ленивый классификатор (lazy learning): вся работа (расчёт расстояний) перенесена в момент предсказания, а не обучения.
Как считать «близость»: метрики расстояния
Для KNN нужна мера расстояния между двумя точками (в нашем случае — между «векторами-изображениями»). Две основные:
- L1 (манхэттенское) — сумма по модулям разниц:
- L2 (евклидово) — корень из суммы квадратов:
В задании используется L1 (см. докстринг класса: «K-neariest-neighbor classifier using L1 loss»). Это наглядно видно по формуле: np.sum(np.abs(...)).
Ручной пример в 2D
Пусть есть две точки:
- L1:
- L2:
Обратите внимание: для разных точек 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 + bincount | 05 |
| Как оценить качество | precision/recall/F1/acc | 05 |
Как подобрать k | 5-fold кросс-валидация | 06 |
Практика
1. Для точек
2. У вас 3 ближайших соседа тестовой точки, их метки: [0, 0, 1]. Что вернёт KNN при k=3? А если метки [0, 1, 1]? Что, если ровно 50/50 (например, соседи [0, 1] при k=2)? Как это разрешить в коде?
3. Откройте стенд WwKnnLab выше. Кликните в область, где синие и красные точки перемешаны. Какой k даст «стабильное» (не прыгающее при перемещении точки) предсказание именно в этой зоне? Почему?
Показать решения
1. L1 = (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.