kNN и кластеризация

Два способа опереться на расстояния между объектами: kNN предсказывает по ближайшим соседям с метками, а k-means находит группы там, где меток нет вовсе. Обе идеи просты, и именно на их подводных камнях любят ловить на собеседованиях.

kNN: скажи мне, кто твой сосед

Метод k ближайших соседей (k-nearest neighbors, kNN) — самая честная модель «по аналогии»: чтобы классифицировать новый объект, найди k ближайших к нему точек обучающей выборки и устрой голосование их меток (для регрессии — усредни значения). Обучения как такового нет: модель просто запоминает выборку, за что её называют ленивым обучением (lazy learning). Вся работа переносится на момент предсказания — и это больно: наивный поиск соседей стоит O(n) на каждый запрос.

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

Второй враг — проклятие размерности (curse of dimensionality): в пространстве из сотен признаков расстояния между всеми парами точек становятся почти одинаковыми, и «ближайший сосед» теряет смысл. Спасают снижение размерности (PCA) и приближённый поиск соседей — тот самый ANN из векторного поиска.

Кластеризация: учимся без меток

Кластеризация (clustering) — задача обучения без учителя (unsupervised learning): меток нет, нужно самим найти группы похожих объектов — сегменты пользователей, дубликаты документов, темы новостей. Классика — k-means: разбить точки на k кластеров, минимизировав инерцию (inertia) — сумму квадратов расстояний от точек до центров их кластеров:

Алгоритм — чередование двух шагов, каждый из которых не увеличивает J:

• Assign: каждую точку приписать к ближайшему центроиду (centroid);
• Update: каждый центроид передвинуть в среднее своих точек.

Когда назначения перестают меняться — алгоритм сошёлся. Сходимость гарантирована, но только к локальному минимуму: неудачная стартовая расстановка центров может «склеить» два облака и разрезать третье. Поэтому на практике делают несколько перезапусков и умную инициализацию k-means++ (первые центры разбрасываются далеко друг от друга — с вероятностью, пропорциональной квадрату расстояния до уже выбранных).

Как выбрать k и когда k-means ломается

Инерция монотонно падает с ростом k (в пределе k = n она нулевая — каждый в своём кластере), поэтому «минимизировать инерцию по k» нельзя. Классический приём — метод локтя (elbow method): рисуем J(k) и ищем излом, после которого добавление кластера почти ничего не даёт. Дополнительно смотрят silhouette score — насколько точка ближе к своему кластеру, чем к чужим.

k-means предполагает выпуклые, примерно сферические кластеры сопоставимого размера — усреднение до центроида другого не умеет. Кластеры-полумесяцы, кольца, группы очень разной плотности он режет неправильно. Для таких форм есть DBSCAN: плотностная кластеризация, которая растит кластеры из плотных областей, сама находит их число и помечает выбросы как шум. И, как и kNN, вся эта механика зависит от масштаба признаков — стандартизация обязательна.

Где это живёт в практике AI-инженера

Обе идеи сегодня чаще всего встречаются поверх эмбеддингов. Поиск похожих документов в RAG — это kNN в пространстве векторов текста, только через приближённые индексы (ANN), потому что честный перебор миллионов векторов слишком дорог. Кластеризация эмбеддингов помогает находить темы в куче обращений в поддержку, дедуплицировать обучающие данные и строить сегменты пользователей. Так что «старые» алгоритмы никуда не делись — они просто переехали в новые пространства признаков.