k ближайших соседей

Класс новой точки — голосование k ближайших: «скажи, кто твои соседи».

время O(n) на запроспамять O(n)уровень: начальный

Что происходит сейчас0/0

Нажмите Play, чтобы запустить сценарий

TypeScript — активная строка подсвечена шагом

1function knn(pts: Array<[x: number, y: number, c: 0 | 1]>, q: [number, number], k: number): 0 | 1 {
2  const ranked = pts
3    .map((p) => ({ c: p[2], d: Math.hypot(p[0] - q[0], p[1] - q[1]) }))
4    .sort((a, b) => a.d - b.d)
5    .slice(0, k)
6 
7  const votes = ranked.filter((r) => r.c === 0).length
8  return votes > k / 2 ? 0 : 1 // большинство
9}

Проблема

Класс новой точки — голосование k ближайших: «скажи, кто твои соседи».

Что вы видите

Все точки с расстояниями; топ-k голосуют классами A или B.

Как это работает

Ленивое обучение: никакого тренировочного этапа, только память + метрика. k маленькое — шум, большое — огрубление. Выбор метрики и k решает всё.

Пошаговый разбор

01
Расстояния
От точки до всех.
02
Топ-k
Ближайшие соседи.
03
Голосование
Большинство решает.

Complexity и ограничения

time

O(n) на запрос

space

O(n)

Сложность см. в шапке страницы.

Edge cases

Пустой вход
Корректная тривиальная обработка.
Вырожденный случай
Минимум работы — сразу ответ.

Где встречается в реальности

Кредитный скоринг

Профили заёмщиков.

Распознавание

Базовый классификатор признаков.

Связанные алгоритмы

Линейная регрессия k-means

Shorts

«Классификация без обучения: kNN»

Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.

Shorts 9:16

Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.

Классификация без обучения: kNN

Нажмите Play

Бит 1/6 · 0–2 с

Hook

script-setup.ru/algorithms/knn