k-NN

1. Посчитать расстояние от нового объекта до всех объектов обучающей выборки.
2. Взять $k$ ближайших.
3. Для классификации — голосование большинством, для регрессии — среднее их ответов.

Малое $k$ даёт изрезанную границу и переобучение (при $k=1$ модель просто запоминает выборку), большое — слишком гладкую и недообучение. $k$ обычно берут нечётным, чтобы избежать ничьих в бинарной задаче.

• Косинусное — для текстов и эмбеддингов, когда важно направление, а не длина.
• Хэмминга — для бинарных и категориальных векторов.
• Махаланобиса — учитывает корреляции признаков.

Наивное предсказание стоит $O(n\cdot d)$ на объект: при миллионе объектов и сотне признаков это сотни миллионов операций на один запрос.

LSH через случайные проекции: берут случайный вектор $r$ и кодируют объект битом $\mathrm{sign}(⟨r,x⟩)$. Несколько таких битов дают хеш, а близкие объекты с большой вероятностью получают одинаковый код.