k-средних: как машина находит кластеры сама

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

Идея: минимизировать разброс внутри групп

Дано n точек и число кластеров k. Нужно расставить k центров (центроидов) \mu_1, \ldots, \mu_k и приписать каждую точку x_i одному из них так, чтобы суммарный разброс точек вокруг своих центров — инерция — был минимален:

J = \sum_{i=1}^{n} \big\lVert x_i - \mu_{c(i)} \big\rVert^2, \qquad c(i) = \arg\min_j \lVert x_i - \mu_j \rVert.

Перебрать все разбиения невозможно (их экспоненциально много). Но есть простой итеративный спуск — алгоритм Ллойда.

Алгоритм Ллойда: два шага по кругу

  1. Приписывание. Каждую точку относим к ближайшему центроиду. Пространство разбивается на ячейки Вороного.
  2. Обновление. Каждый центроид сдвигаем в среднее своих точек.

Повторяем, пока приписывания не перестанут меняться. Каждый шаг не увеличивает инерцию J, поэтому процесс сходится — но к локальному минимуму, зависящему от стартовых позиций центров.

Потрогайте кластеризацию

Точки внизу перекрашиваются по ближайшему центроиду, а звёзды-центроиды ползут к среднему своих точек — сходимость видна вживую. Кликните по полю, чтобы добавить точку. Перетащите центроид — алгоритм выбьется из равновесия и сойдётся заново, возможно, к другому разбиению. Поменяйте k — число групп.

УведомлениеПроблема старта

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

СоветГлавный инсайт

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

Где это работает

  • Сжатие изображений: кластеризуем цвета пикселей в k оттенков — палитра из k цветов вместо миллионов (векторное квантование).
  • Сегментация и предобработка: грубое разбиение данных перед более тонкой моделью; инициализация компонент в GMM.
  • Поиск похожего: центроиды как «прототипы» для быстрой приближённой кластеризации миллионов объектов.

Мини-батч k-means

У классического Ллойда есть слабое место: каждая итерация трогает все N точек — N\cdot k вычислений расстояний за проход. При миллионах точек это больно. Идея мини-батча (Sculley, 2010): на каждом шаге брать случайную пачку из b\ll N точек, приписывать их к ближайшим центроидам и сдвигать центроиды скользящим средним (шаг 1/\text{счётчик}). Стоимость шага — b\cdot k вместо N\cdot k.

На больших данных мини-батч k-means часто даёт близкую инерцию при существенно меньшей стоимости вычислений (а при больших N выигрыш по бюджету может достигать порядков). Цена — более шумная сходимость и возможное ухудшение итоговой инерции, особенно при маленьком размере пачки b или неудачной инициализации. Меняйте размер пачки b и смотрите на правый график: кривая мини-батча сваливается к оптимуму левее дорогих ступеней полного метода.

Именно мини-батч стоит за MiniBatchKMeans в scikit-learn и за кластеризацией в промышленных пайплайнах: когда точек миллионы, «потрогать все» на каждом шаге — непозволительная роскошь.

Связи

  • PCA (§ PCA и Eigenfaces): часто кластеризуют уже в сжатом PCA-пространстве.
  • MDS (§ Многомерное шкалирование): другой взгляд на геометрию данных — по расстояниям, а не по координатам.
  • Оптимизаторы (§ Как методы спускаются с горы): Ллойд — это покоординатный спуск по инерции, родственник методов из главы об оптимизации.
Наверх