Ленивый алгоритм: предсказание — это голосование k ближайших объектов .
Ключевые тезисы
- Обучения нет, вся стоимость переносится на .
- Требует масштабирования и разумного выбора метрики расстояния.
- Сильно страдает от проклятия размерности: в высоких размерностях все точки равноудалены.
Какую задачу решает
отказывается от обучения вовсе: модель — это сама . Чтобы предсказать ответ для нового объекта, алгоритм находит ближайших известных объектов и берёт их большинство (для классификации) или среднее (для регрессии).
Такая ленивость даёт неожиданно сильное свойство: граница решения может быть какой угодно сложной, никаких предположений о форме зависимости не делается. Цена — вся работа переносится на предсказания, и качество целиком определяется тем, насколько осмысленна выбранная метрика расстояния.
Объекты описаны возрастом (18–80) и доходом (20 000–500 000). Евклидово расстояние между двумя людьми почти целиком определяется разницей в доходе: 50 лет разницы в возрасте дают вклад 2500, а 50 000 разницы в доходе — 2.5 миллиарда. Фактически модель видит только один . После приведения обоих к нулевому среднему и единичной вклад становится сопоставимым, и качество на таких данных обычно подскакивает на десятки процентов. Для — не гигиена, а часть алгоритма.
Подробный разбор
- Посчитать расстояние от нового объекта до всех объектов .
- Взять ближайших.
- Для классификации — голосование большинством, для регрессии — среднее их ответов.
Малое даёт изрезанную границу и (при модель просто запоминает выборку), большое — слишком гладкую и . обычно берут нечётным, чтобы избежать ничьих в бинарной задаче.
, . Манхэттенское расстояние: . Евклидово: .
- Косинусное — для текстов и , когда важно направление, а не длина.
- Хэмминга — для бинарных и категориальных .
- Махаланобиса — учитывает .
Масштабирование обязательно: без него «доход» полностью определит расстояние, а «возраст» станет невидимым.
Наивное предсказание стоит на объект: при миллионе объектов и сотне это сотни миллионов операций на один запрос.
| Структура | Идея | Когда работает |
|---|---|---|
| KD-дерево | рекурсивное разбиение по осям | |
| Ball-дерево | разбиение на шары | средние размерности |
| LSH | : близкие объекты → одна корзина | высокие размерности |
| HNSW | многослойный соседства | стандарт для векторного поиска |
LSH через случайные проекции: берут случайный и кодируют объект битом . Несколько таких битов дают хеш, а близкие объекты с большой вероятностью получают одинаковый код.
Где применяется
- Поиск похожихРекомендации «похожие товары», поиск дубликатов, подбор по фотографии.
- поиск и Современное воплощение метода: ANN-индекс по — сердце .
- Заполнение пропусковKNN-импьютация подставляет значение по похожим наблюдениям.
- Быстрая проверка того, есть ли в данных вообще локальная структура.
- Few-shot классификацияКлассы, у которых по несколько примеров: обучать нечего, а сравнивать можно.
Плюсы, минусы и альтернативы
Плюсы
- Обучения нет: добавление данных не требует .
- Граница решения произвольной формы, без предположений о зависимости.
- Естественная многоклассовость и понятное объяснение: «вот похожие случаи».
- Одинаково работает для классификации, регрессии и поиска.
- С ANN-индексами масштабируется до миллиардов объектов.
Минусы
- Предсказание дорого: нужно сравнить объект со всей выборкой.
- Хранит всю обучающую выборку — память растёт с данными.
- Разваливается в высокой размерности без .
- Требует : без неё метрика бессмысленна.
- Плохо переносит нерелевантные — они портят расстояние.
- Чувствителен к дисбалансу классов: большой класс побеждает большинством.
Брать, если
- Задача формулируется как «найди похожие».
- Размерность невелика или есть хорошие .
- Данные постоянно пополняются и переобучать неудобно.
- Нужно объяснение через прецеденты.
Не брать, если
- сотни и они сырые — расстояние перестаёт что-либо значить.
- Жёсткие требования к при большой выборке и без ANN-индекса.
- Много нерелевантных , отобрать которые нечем.
Чем заменяют
Связанные темы
Метрические и ядровые методы
SVM65%
Метод опорных векторов · Классическое машинное обучениеИщет гиперплоскость с максимальным зазором между классами; ядровой трюк добавляет нелинейность без явного перехода в новое пространство.
k-Means65%
k-средних · Классическое машинное обучениеРазбивает объекты на k кластеров, минимизируя суммарное расстояние до центроидов.
Distance65%
Расстояние · Математический справочникМера непохожести объектов — основа кластеризации, k-NN и поиска.
Norm65%
Норма · Математический справочникМера длины вектора; выбор нормы определяет геометрию задачи.
Normalization & Standardization65%
Нормализация и стандартизация · ДанныеПриведение признаков к сопоставимым масштабам, без которого расстояния, градиенты и регуляризация работают некорректно.
Metric spaces65%
Метрические пространства · Топологический анализ данныхМножество с функцией расстояния. Любой TDA-пайплайн начинается с выбора метрики.
Всё, что названо в описании, разобрано здесь же или в соседней теме — переходы под каждым определением.
Метрика расстояния
Евклидова, манхэттенская, косинусная. Главный выбор в методе: она задаёт, что считать похожим.
Разбор ниже: Метрики расстоянияОбязательная нормализация
с большим масштабом подавляет все остальные в формуле расстояния.
Разбор ниже: Метрики расстоянияПроклятие размерности
В высокой размерности все расстояния становятся почти одинаковыми, и понятие «сосед» теряет смысл.
Разбор ниже: Сложность и быстрый поиск соседейПриближённый поиск (ANN)
HNSW и IVF ищут почти за логарифмическое время — так k-NN работает на миллиардах .
Разбор ниже: Сложность и быстрый поиск соседейСпрашивают на собеседовании: Wildberries — Каталог, поиск и атрибуты, Wildberries — Спрос, цены и акции, Магнит — Ассортимент и спрос, Lamoda — Рекомендации и поиск, Спортмастер — Закупка и ассортимент, Циан — Оценка недвижимости.
Глава «Классическое машинное обучение» последний раз правилась . Нашли ошибку — напишите.