k ближайших соседей и наивный байесовский классификатор

Эти два алгоритма ставят рядом не случайно. Они — противоположные полюса того, как вообще можно строить классификатор, и понимание этой оппозиции даёт каркас для всего остального курса.

kNN не учится вообще. Он запоминает выборку и откладывает всю работу до момента запроса. Никакой «модели» в смысле параметров нет — есть данные и метрика. Это ленивое (lazy), непараметрическое обучение: сложность гипотезы растёт вместе с объёмом данных.

Наивный Байес учится за один проход и сжимает выборку в горстку чисел — априорные вероятности классов и таблицу условных вероятностей признаков. Это жадное (eager), параметрическое, к тому же генеративное обучение: модель описывает, как данные порождаются, P(x, y), а не только где проходит граница, P(y | x).

Оба алгоритма живут в проде в 2026 году. kNN — потому что вся индустрия векторного поиска (RAG, семантический поиск, рекомендации, дедупликация, антифрод) это kNN с приближённым индексом. Наивный Байес — потому что на разреженных текстовых признаках он даёт 90 % качества за 1 % вычислительного бюджета и остаётся эталонным baseline, который обязан быть побит любой более сложной моделью.

Предполагается, что вы уже прошли https://courses.digitable.life/post/machine-learning/02-data-and-features/ (масштабирование и утечки здесь критичны как нигде) и https://courses.digitable.life/post/machine-learning/03-linear-and-logistic-regression/ (логистическая регрессия — прямой дискриминативный «двойник» наивного Байеса).

Часть I. Метод k ближайших соседей

Интуиция: «скажи мне, кто твой сосед»

Гипотеза, на которой стоит kNN, называется гипотезой гладкости (smoothness assumption): близкие в пространстве признаков объекты с большой вероятностью имеют близкие ответы. Если рядом с новым пациентом в пространстве «возраст, давление, холестерин» стоят семь человек, шестеро из которых заболели — разумно предсказать болезнь. Это тот же принцип, по которому риелтор оценивает квартиру по ценам пяти похожих квартир в том же районе; kNN — формализация этого бытового рассуждения.

Формально

Дана обучающая выборка D = {(x₁, y₁), …, (x_n, y_n)}, метрика d(·, ·) и число k. Для запроса x:

1. Найти N_k(x) — множество k объектов выборки с наименьшим d(x, xᵢ).
2. Классификация: ŷ = argmax_c Σ_{i ∈ N_k(x)} w_i · [yᵢ = c].
3. Регрессия: ŷ = (Σ w_i · yᵢ) / (Σ w_i).

Веса w_i — либо все единицы (uniform), либо 1 / d(x, xᵢ) (distance), либо ядро (гауссово, Епанечникова). Вариант с ядром и фиксированным радиусом вместо фиксированного k называется ядерной регрессией Надарая — Ватсона и является непрерывным родственником kNN.

Оценка вероятности класса — просто доля соседей: P̂(y = c | x) = Σ w_i [yᵢ = c] / Σ w_i. При k = 5 разрешение этой оценки — 0.2, и никакой третьей значащей цифры в ней нет; это важно помнить, когда вероятности идут в бизнес-правило (см. https://courses.digitable.life/post/machine-learning/10-model-evaluation/).

Теоретическая гарантия. Классический результат Ковера и Харта (1967): при n → ∞ ошибка правила 1-NN не превышает удвоенной байесовской, R_Bayes ≤ R_1NN ≤ 2·R_Bayes (Cover & Hart), а при k → ∞ и k/n → 0 kNN состоятелен — сходится к байесовскому классификатору. То есть kNN не игрушка, а универсальный аппроксиматор; проблема не в теории, а в том, что «n → ∞» в размерности 300 означает астрономические объёмы данных.

Выбор k: bias-variance в чистом виде

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

Эффективное число степеней свободы kNN примерно n / k — прямой аналог числа параметров. Подробный разбор компромисса — в https://courses.digitable.life/post/machine-learning/11-overfitting-and-regularization/.

Практические правила:

• Подбирайте k кросс-валидацией, а не по формуле. Стартовая сетка — [1, 3, 5, 11, 21, 51] (логарифмическая, а не линейная: разница между 5 и 6 не значима, между 5 и 50 — да).
• Для бинарной задачи берите нечётное k, чтобы не ловить ничьи.
• Эвристика k ≈ √n — только для «прикинуть порядок» на старте.
• При сильном дисбалансе классов большие k вытесняют миноритарный класс полностью: среди 50 соседей просто не окажется ни одного положительного. Либо уменьшайте k, либо используйте weights='distance', либо взвешивайте голоса обратно частоте класса.

Метрика — это и есть модель

Главное непонимание новичков: они считают выбор k основным решением. На самом деле основное решение — метрика, потому что она задаёт само понятие «похожести».

Про L1 против L2 в высокой размерности: Aggarwal, Hinneburg, Keim (2001) показали, что при росте d метрики с меньшим p сохраняют контраст лучше. Если евклидово расстояние «не работает» на 100 признаках — попробуйте манхэттенское, это бесплатный эксперимент.

Махаланобис эквивалентен евклидову расстоянию после «отбеливания» данных (умножения на S^{-1/2}), то есть сам убирает и разницу масштабов, и корреляции. Обобщение этой идеи — metric learning: выучить M в d(x,z) = √((x−z)ᵀ M (x−z)) так, чтобы объекты одного класса стягивались, а разных — расталкивались (NCA, LMNN — Weinberger & Saul, JMLR 2009). Современный вариант — обучить эмбеддинги контрастивным лоссом и делать kNN уже в них: практически весь векторный поиск сегодня — это metric learning + kNN.

Масштабирование обязательно

Это ошибка номер один. Признак «годовой доход» в рублях (0–5 000 000) и признак «возраст» (18–80) в евклидовой метрике дают вклад, различающийся на пять порядков: расстояние фактически считается только по доходу.

# НЕПРАВИЛЬНО: kNN на сырых признаках разных масштабов
KNeighborsClassifier().fit(X_train, y_train)

# ПРАВИЛЬНО: масштабирование внутри пайплайна, чтобы статистики
# считались только по train-фолду и не текли из валидации
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

model = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=11))

StandardScaler подходит для примерно нормальных признаков, RobustScaler — когда есть выбросы, MinMaxScaler — когда границы известны и жёсткие. Подробности и подводные камни — в https://courses.digitable.life/post/machine-learning/02-data-and-features/.

Второй по частоте промах — one-hot кодирование категорий с высокой кардинальностью. После one-hot 500 городов расстояние между двумя разными городами всегда √2, независимо от того, соседние это города или разные континенты. Геометрия разрушена. Лучше: целевое кодирование, обучаемые эмбеддинги или метрика Gower.

Проклятие размерности

При росте d расстояния между случайными точками концентрируются: разница между ближайшим и дальнейшим соседом стремится к нулю относительно самого расстояния. Формально (Beyer et al., 1999): если моменты распределения расстояний ведут себя разумно, то (D_max − D_min) / D_min → 0 при d → ∞. Понятие «ближайший» теряет смысл.

import numpy as np

rng = np.random.default_rng(0)
for d in (2, 10, 100, 1000):
    X = rng.normal(size=(2000, d))          # равномерное облако без структуры
    q = rng.normal(size=d)
    dist = np.linalg.norm(X - q, axis=1)
    # относительный контраст: во сколько раз дальний сосед дальше ближнего
    print(f"d={d:5d}  контраст = {dist.max() / dist.min():.2f}")

# d=    2  контраст = 90.05
# d=   10  контраст = 4.61
# d=  100  контраст = 1.48
# d= 1000  контраст = 1.14   <- «ближайший» почти неотличим от «дальнего»

Важная поправка: проклятие бьёт по неинформативным размерностям. Реальные данные почти всегда лежат на многообразии меньшей размерности (внутренняя размерность картинок 28×28 измеряется десятками, а не 784), и kNN на хороших эмбеддингах прекрасно работает при d = 768. Убивает не размерность как таковая, а шумовые признаки: добавьте к двум полезным признакам сто случайных — kNN развалится, тогда как решающее дерево их проигнорирует. Отсюда практика: перед kNN делайте отбор признаков или снижение размерности (https://courses.digitable.life/post/machine-learning/09-dimensionality-reduction/) — PCA/UMAP до 20–50 компонент часто поднимает качество сильнее любого тюнинга k.

Алгоритм и сложность

функция kNN_predict(X_train, y_train, x, k, d):
    heap ← max-куча размера k по расстоянию
    для каждого (xi, yi) в X_train:
        r ← d(x, xi)
        если |heap| < k:  push(heap, (r, yi))
        иначе если r < top(heap).r:
            pop(heap); push(heap, (r, yi))
    вернуть мажоритарный класс среди heap

Полный перебор: обучение O(1) по времени и O(n·d) по памяти (данные надо хранить целиком), предсказание одного запроса — O(n·d) времени и O(k) дополнительной памяти. Для m запросов сразу выгоднее матричное умножение: ‖x − z‖² = ‖x‖² − 2⟨x, z⟩ + ‖z‖², что сводит всё к одному GEMM размера m×d×n — на BLAS это в десятки раз быстрее наивных циклов, хотя асимптотика та же.

import numpy as np
from scipy.stats import mode


class SimpleKNN:
    """Учебная реализация kNN. Обучение — запоминание, вся работа в predict."""

    def __init__(self, k: int = 5, weights: str = "uniform"):
        self.k = k
        self.weights = weights

    def fit(self, X: np.ndarray, y: np.ndarray) -> "SimpleKNN":
        self.X_ = np.asarray(X, dtype=np.float64)   # O(n·d) памяти
        self.y_ = np.asarray(y)
        return self

    def _dists(self, Q: np.ndarray) -> np.ndarray:
        # ‖q − x‖² = ‖q‖² − 2⟨q, x⟩ + ‖x‖² — один GEMM вместо двойного цикла
        q2 = np.einsum("ij,ij->i", Q, Q)[:, None]
        x2 = np.einsum("ij,ij->i", self.X_, self.X_)[None, :]
        d2 = q2 - 2.0 * Q @ self.X_.T + x2
        return np.sqrt(np.maximum(d2, 0.0))          # клип от численного шума

    def predict(self, Q: np.ndarray) -> np.ndarray:
        Q = np.asarray(Q, dtype=np.float64)
        D = self._dists(Q)                            # O(m·n·d)
        # argpartition даёт k наименьших за O(n) вместо O(n log n) полной сортировки
        idx = np.argpartition(D, self.k - 1, axis=1)[:, : self.k]
        rows = np.arange(len(Q))[:, None]
        nb_lbl = self.y_[idx]                         # метки соседей
        if self.weights == "uniform":
            return mode(nb_lbl, axis=1, keepdims=False).mode
        w = 1.0 / np.maximum(D[rows, idx], 1e-12)     # защита от деления на ноль
        classes = np.unique(self.y_)
        scores = np.stack([((nb_lbl == c) * w).sum(axis=1) for c in classes], axis=1)
        return classes[scores.argmax(axis=1)]

Ключевая деталь — argpartition: нам не нужен полный порядок соседей, нужны только k наименьших. Это разница между O(n log n) и O(n) на каждый запрос.

Ускорение: пространственные индексы

kd-дерево рекурсивно режет пространство осепараллельными гиперплоскостями (обычно по медиане самого «широкого» признака). Поиск идёт вниз до листа, а затем при возврате вверх проверяет: пересекает ли шар радиуса «текущее лучшее расстояние» плоскость среза? Если нет — всё поддерево отсекается. Построение O(n·d·log n), средний запрос O(log n) — но только при малой d. При d ≳ 20 шар пересекает почти все срезы, отсечений нет, и дерево работает медленнее полного перебора (лишние переходы по указателям).

ball-дерево режет не плоскостями, а вложенными гиперсферами; терпит размерность чуть лучше и работает с произвольной метрикой (kd-дерево требует, чтобы метрика была покоординатно разложима). В sklearn algorithm='auto' выбирает между brute, kd_tree и ball_tree эвристически — и почти всегда для d > 30 честно откатывается на brute.

Приближённый поиск (ANN) — это то, что реально используют в проде. Мы соглашаемся находить не точных соседей, а 95–99 % из них, и получаем на два порядка меньшую латентность:

• HNSW — многослойный навигируемый граф малого мира. Логарифмический поиск, отличный recall, но индекс живёт в RAM (Malkov & Yashunin, arXiv:1603.09320).
• IVF-PQ — разбиение на ячейки Вороного + квантование остатков произведением. Сжимает вектор с 3 КБ до 32 байт, позволяет держать миллиарды векторов (Jégou et al., «Product Quantization for NN Search»).
• LSH — семейства хеш-функций, у которых коллизии вероятнее для близких точек. Сейчас проигрывает графам по recall/latency, но остаётся удобным для стриминга и дедупликации.

Реализации: FAISS, hnswlib, ScaNN, а также векторные СУБД — pgvector, Qdrant, Milvus, Weaviate.

Приём с переранжированием (rerank) стоит запомнить: ANN достаёт 100 кандидатов быстро и неточно, затем на них считается точное расстояние (или тяжёлая cross-encoder модель) — и качество почти как у точного поиска при цене приближённого.

Как kNN выглядит в продакшене

Операционные тонкости, о которых не пишут в туториалах:

• Индекс — это состояние. Его надо версионировать вместе с моделью-энкодером. Смена энкодера без перестроения индекса = поиск в мусоре, потому что старые и новые векторы живут в разных пространствах. Это частая и очень дорогая авария (см. https://courses.digitable.life/post/machine-learning/15-mlops/).
• Удаление объектов в HNSW — мягкое (tombstone). Без периодической перестройки индекс распухает и деградирует.
• Нормализация. Косинусное расстояние = евклидово на L2-нормированных векторах; многие библиотеки требуют, чтобы вы нормировали сами, и молча считают inner product иначе.
• Дрейф. Мониторьте распределение расстояний до 1-го соседа: рост среднего означает, что запросы уходят из области, покрытой индексом.
• Память. 10 млн векторов float32 по 768 измерений — это 30 ГБ. Отсюда float16, скалярное квантование и PQ.

Другие применения kNN, кроме классификации

• Импутация пропусков — sklearn.impute.KNNImputer заполняет пропуск средним по соседям; часто заметно лучше медианы.
• Детекция аномалий — расстояние до k-го соседа как score; отсюда алгоритм LOF (Local Outlier Factor), нормирующий это расстояние на локальную плотность.
• Балансировка классов — SMOTE синтезирует новые объекты миноритарного класса, интерполируя между соседями.
• Полу-обучение — распространение меток по графу соседства.
• Отладка датасета — найдите ближайших соседей объектов, на которых модель ошибается: почти всегда обнаружатся дубликаты, битые метки или утечка между train и test.

Типичные ошибки в kNN

1. Забыли масштабировать. Первая и главная.
2. Масштабировали до сплита. Классическая утечка: scaler.fit(X) на всех данных завышает метрику. Только внутри Pipeline.
3. Дубликаты между train и test. kNN находит сам себя и показывает 0.99 accuracy, которая рассыпается в проде. Всегда проверяйте выборку на точные и почти-точные дубли.
4. k подобрано на тесте. Тест использован как валидация — оценка смещена.
5. Косинус на ненормированных счётчиках. Длина документа начинает доминировать.
6. kNN на 500 one-hot признаках. Геометрия разрушена, см. выше.
7. Игнорируют цену предсказания. Модель «обучается за 0 секунд», зато каждый запрос стоит O(n·d) — и на 10 млн объектов сервис не укладывается в SLA.

Часть II. Наивный байесовский классификатор

От правила Байеса к классификатору

Мы хотим P(y = c | x). Напрямую оценить его сложно, а вот обратное направление — как выглядят признаки внутри класса — оценить легко. Это и делает теорема Байеса:

P(c | x) = P(x | c) · P(c) / P(x)

Знаменатель P(x) одинаков для всех классов, поэтому для выбора победителя он не нужен:

ŷ = argmax_c  P(c) · P(x₁, x₂, …, x_d | c)

Проблема в том, что совместное распределение P(x₁ … x_d | c) для d бинарных признаков требует 2^d − 1 параметров на класс. При d = 30 это миллиард чисел — оценить их не из чего.

Наивное допущение

Предположим, что признаки условно независимы при известном классе:

P(x₁, …, x_d | c) = Π_j P(x_j | c)

Число параметров падает с экспоненциального до d · c. Это и есть «наивность»: в графе зависимостей мы стираем все рёбра между признаками, оставляя только рёбра «класс → признак». В реальности слова «нигерийский» и «принц» в спаме, разумеется, зависимы; допущение почти всегда ложно.

Почему же оно работает? Ключевое наблюдение из работы Domingos & Pazzani (1997), «On the Optimality of the Simple Bayesian Classifier under Zero-One Loss»: для классификации нам не нужны верные вероятности — нужен верный порядок классов. Наивный Байес может выдавать вероятность 0.9999 там, где истинная 0.6, и всё равно принимать правильное решение, потому что argmax не меняется. Ошибки оценки, вызванные зависимостью признаков, часто действуют в одну сторону для всех классов и взаимно сокращаются.

Практическое следствие: используйте NB для решений, не доверяйте его вероятностям. Он патологически переуверен (значения липнут к 0 и 1), потому что каждый коррелированный признак засчитывается как независимое свидетельство. Если вероятности нужны — калибруйте изотонической регрессией или Платтом, см. https://courses.digitable.life/post/machine-learning/10-model-evaluation/.

Логарифмы вместо произведений

Произведение тысячи вероятностей порядка 10⁻³ мгновенно даёт машинный ноль. Поэтому всегда работают в логарифмах:

log P(c | x) ∝ log P(c) + Σ_j log P(x_j | c)

Умножения превращаются в сложения — это ещё и быстрее. Обратно в вероятности переходят через устойчивый logsumexp: p_c = exp(s_c − logsumexp(s)).

Заодно видно родство с линейными моделями: для бинарных признаков log P(c|x) — линейная функция от x. Наивный Байес — линейный классификатор в логарифмическом пространстве, просто его веса оцениваются подсчётом частот, а не оптимизацией лосса.

Варианты и их распределения

MultinomialNB. Документ — мешок слов, P(w | c) = доля вхождений слова w среди всех слов класса. Стандарт для текстов.

BernoulliNB. Документ — вектор из «слово есть / слова нет». Отличие принципиальное: модель явно штрафует отсутствие характерных слов через множитель (1 − P(w|c)). На коротких текстах (заголовки, твиты, поисковые запросы) часто выигрывает у мультиномиальной.

GaussianNB. Каждый признак внутри класса — нормальный со своими μ_{jc}, σ²_{jc}. Для сильно скошенных признаков сначала примените log1p или QuantileTransformer, иначе гауссово допущение грубо нарушается.

ComplementNB. Оценивает параметры по дополнению класса; выведен как исправление известных перекосов мультиномиальной модели на несбалансированных корпусах (Rennie et al., ICML 2003, «Tackling the Poor Assumptions of Naive Bayes Text Classifiers»). На перекошенных данных берите его по умолчанию.

CategoricalNB. Для чистых категориальных признаков без one-hot.

Смешанные типы? Считайте лог-правдоподобия отдельными моделями и складывайте: они всё равно складываются в логарифмическом пространстве. Это законно ровно в рамках того же наивного допущения.

Сглаживание: борьба с нулевыми вероятностями

Если слово «квантовый» ни разу не встретилось в спаме, то P(«квантовый» | спам) = 0, и любое письмо с этим словом получает нулевую апостериорную вероятность спама — одно неудачное слово перечёркивает всю остальную улику. В логарифмах это −∞.

Лечится аддитивным сглаживанием (Лапласа при α = 1, Лидстона при α ∈ (0,1)):

P(w | c) = (count(w, c) + α) / (Σ_v count(v, c) + α · |V|)

Байесовская интерпретация: это MAP-оценка с сопряжённым априорным распределением Дирихле, то есть «мы заранее видели каждое слово α раз». α — гиперпараметр регуляризации: больше α → оценки ближе к равномерным → сильнее сглаживание → выше смещение. Подбирайте на сетке [0.01, 0.1, 0.5, 1.0]; на больших словарях оптимум обычно ниже 1.

Реализация с нуля

import numpy as np
from scipy.sparse import csr_matrix
from scipy.special import logsumexp


class MultinomialNaiveBayes:
    """Мультиномиальный наивный Байес в лог-пространстве. Работает с разреженной матрицей."""

    def __init__(self, alpha: float = 1.0):
        self.alpha = alpha

    def fit(self, X: csr_matrix, y: np.ndarray) -> "MultinomialNaiveBayes":
        self.classes_ = np.unique(y)
        n_docs, n_feats = X.shape

        # априорные вероятности классов: log P(c)
        counts = np.array([(y == c).sum() for c in self.classes_], dtype=np.float64)
        self.class_log_prior_ = np.log(counts / counts.sum())

        # суммарные счётчики слов по классам: матрица (n_classes, n_feats)
        # один проход по данным -> обучение O(nnz), где nnz = число ненулевых элементов
        fc = np.vstack([np.asarray(X[y == c].sum(axis=0)).ravel() for c in self.classes_])

        # аддитивное сглаживание + нормировка по строке
        smoothed = fc + self.alpha
        self.feature_log_prob_ = (
            np.log(smoothed) - np.log(smoothed.sum(axis=1, keepdims=True))
        )
        return self

    def joint_log_likelihood(self, X: csr_matrix) -> np.ndarray:
        # log P(c) + Σ_j x_j · log P(w_j | c) — одно разреженное умножение матриц
        return X @ self.feature_log_prob_.T + self.class_log_prior_

    def predict(self, X: csr_matrix) -> np.ndarray:
        return self.classes_[self.joint_log_likelihood(X).argmax(axis=1)]

    def predict_proba(self, X: csr_matrix) -> np.ndarray:
        jll = self.joint_log_likelihood(X)
        # устойчивая нормировка: вычитаем logsumexp, а не делим экспоненты
        return np.exp(jll - logsumexp(jll, axis=1, keepdims=True))

Обратите внимание: и обучение, и предсказание — по одному проходу и одному матричному умножению. Никаких итераций, никакого градиентного спуска. Именно поэтому NB обучается на корпусе в миллионы документов за секунды и легко работает в режиме partial_fit (онлайн-обучение — достаточно инкрементально обновлять счётчики).

Сложность

Сравните с kNN: у NB память не зависит от n (выборка сжата в таблицу счётчиков), а предсказание не зависит от размера обучающей выборки вовсе. Это противоположный инженерный профиль.

Практический пример: классификация текста

from sklearn.datasets import fetch_20newsgroups
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.naive_bayes import ComplementNB
from sklearn.pipeline import make_pipeline
from sklearn.model_selection import GridSearchCV, StratifiedKFold
from sklearn.metrics import classification_report

cats = ["sci.med", "sci.space", "comp.graphics", "talk.politics.guns"]
# remove=... убирает заголовки и цитаты — иначе будет утечка:
# модель выучит адреса рассылок вместо тематики
train = fetch_20newsgroups(subset="train", categories=cats,
                           remove=("headers", "footers", "quotes"))
test = fetch_20newsgroups(subset="test", categories=cats,
                          remove=("headers", "footers", "quotes"))

pipe = make_pipeline(
    TfidfVectorizer(sublinear_tf=True,   # 1 + log(tf): гасит повторы слов
                    min_df=2,            # выбрасываем хвост опечаток
                    ngram_range=(1, 2)),
    ComplementNB(),
)

grid = GridSearchCV(
    pipe,
    {"complementnb__alpha": [0.01, 0.1, 0.3, 1.0],
     "tfidfvectorizer__min_df": [1, 2, 5]},
    cv=StratifiedKFold(5, shuffle=True, random_state=42),
    scoring="f1_macro",
    n_jobs=-1,
)
grid.fit(train.data, train.target)

print(grid.best_params_, round(grid.best_score_, 4))
print(classification_report(test.target, grid.predict(test.data),
                            target_names=test.target_names))
# {'complementnb__alpha': 0.01, 'tfidfvectorizer__min_df': 1}  cv f1_macro = 0.907
# macro-F1 на тесте ≈ 0.88 при обучении меньше секунды на CPU —
# именно тот baseline, который трансформер обязан побить, чтобы оправдать себя.
# Обратите внимание: оптимальная alpha = 0.01, а не дефолтная 1.0

Приём TfidfVectorizer + MultinomialNB формально нарушает мультиномиальную модель (tf-idf — не счётчики), но эмпирически почти всегда работает лучше сырых счётчиков. Это тот случай, когда практика опережает теорию; та же работа Rennie et al. разбирает, почему нормировка по длине документа так помогает.

NB против логистической регрессии

Пара «наивный Байес — логистическая регрессия» — канонический пример пары «генеративная модель — дискриминативная модель с той же параметрической формой». Обе задают одинаковое семейство линейных разделяющих поверхностей, но оценивают параметры по-разному: NB — подсчётом частот (максимизирует P(x, y)), ЛР — оптимизацией (максимизирует P(y | x)).

Ng & Jordan (NIPS 2001) показали: у генеративной модели выше асимптотическая ошибка, но она сходится к своему пределу как O(log d / n) против O(d / n) у дискриминативной. Практический вывод:

• мало данных → NB выигрывает (быстрее «наедается»);
• много данных → логистическая регрессия обгоняет и уже не отдаёт лидерство;
• точка пересечения кривых обучения — обычно сотни–тысячи примеров.

Отсюда рецепт из работы Wang & Manning (ACL 2012), NBSVM: взять лог-отношения частот из NB как веса признаков и подать в линейный SVM — гибрид, который годами держался в топе на задачах анализа тональности и до сих пор служит сильным baseline. Про SVM подробно — в следующей статье, https://courses.digitable.life/post/machine-learning/05-svm/.

Типичные ошибки в наивном Байесе

1. Доверять predict_proba без калибровки. Вероятности NB систематически переуверены.
2. Дублирующие признаки. Добавили один и тот же сигнал под тремя именами — он получил тройной вес. NB не имеет механизма подавления коллинеарности (в отличие от L2-регрессии).
3. Забыть про сглаживание или, наоборот, оставить alpha=1 на словаре в миллион слов, где это сильно пересглаживает.
4. GaussianNB на скошенных признаках без предварительного преобразования.
5. Пренебречь дисбалансом. На соотношении 1:1000 априорная вероятность подавляет правдоподобие; помогают ComplementNB, ручная подмена class_prior_ или сдвиг порога.
6. Утечки в текстовых полях. Служебные заголовки, ID, шаблонные подписи дают почти идеальное качество на валидации и ноль в проде.

Что выбрать: сравнение

Интерпретируемость у обоих — недооценённое достоинство. kNN объясняет решение примерами («отказали, потому что вот пять похожих клиентов не вернули кредит») — это часто убедительнее SHAP-графиков для бизнес-заказчика. NB раскладывает решение в сумму вкладов признаков, которые можно прямо показать: «слова „выигрыш“, „бесплатно“, „срочно“ дали +6.1 к логиту спама».

Мини-итог и чеклист

• kNN не учится — он ищет. Качество определяется метрикой и представлением, а не k.
• Масштабируйте признаки. Внутри Pipeline. Всегда.
• Проверяйте дубликаты между train и test — иначе kNN покажет фантастическую и ложную метрику.
• В высокой размерности снижайте её (PCA/UMAP) или учите эмбеддинги; сырые kNN на сотнях шумных признаков не работают.
• В проде kNN = ANN-индекс (HNSW/IVF-PQ) + переранжирование; индекс версионируется вместе с энкодером.
• Наивный Байес — линейная модель, чьи веса получены подсчётом частот. Обучение за один проход, предсказание не зависит от n.
• Всегда сглаживайте; подбирайте alpha кросс-валидацией.
• ComplementNB — разумный дефолт для текста, особенно при дисбалансе.
• Вероятностям NB не верьте без калибровки; порядку классов верьте.
• Оба алгоритма — обязательные baseline. Пока трансформер не побил TfidfVectorizer + NB на вашей задаче, он не оправдан.

Источники

• T. Cover, P. Hart. Nearest Neighbor Pattern Classification, IEEE Trans. IT, 1967.
• K. Beyer et al. When Is «Nearest Neighbor» Meaningful?, ICDT, 1999.
• C. Aggarwal et al. On the Surprising Behavior of Distance Metrics in High Dimensional Space, ICDT, 2001.
• K. Weinberger, L. Saul. Distance Metric Learning for Large Margin Nearest Neighbor Classification, JMLR, 2009.
• Y. Malkov, D. Yashunin. Efficient and Robust ANN Search Using HNSW Graphs, arXiv:1603.09320.
• H. Jégou et al. Product Quantization for Nearest Neighbor Search, IEEE TPAMI, 2011.
• P. Domingos, M. Pazzani. On the Optimality of the Simple Bayesian Classifier under Zero-One Loss, Machine Learning, 1997.
• J. Rennie et al. Tackling the Poor Assumptions of Naive Bayes Text Classifiers, ICML, 2003.
• A. Ng, M. Jordan. On Discriminative vs. Generative Classifiers, NIPS, 2001.
• S. Wang, C. Manning. Baselines and Bigrams: Simple, Good Sentiment and Topic Classification, ACL, 2012.
• T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning, гл. 2 и 13.
• C. Manning, P. Raghavan, H. Schütze. Introduction to Information Retrieval, гл. 13 (Text classification and Naive Bayes) и 14.
• Документация scikit-learn: Nearest Neighbors, Naive Bayes.
• FAISS wiki: Guidelines to choose an index.

Что дальше

Мы разобрали два алгоритма, которые обходятся без оптимизации: один запоминает выборку, другой считает частоты. Следующий шаг — модель, которая, наоборот, целиком строится на задаче оптимизации с явным геометрическим смыслом: максимизировать зазор между классами. А ядерный трюк покажет, как получить нелинейные границы, ни разу не выйдя в пространство высокой размерности явно.

Читайте дальше: Метод опорных векторов и ядерный трюк.