EM-алгоритм и смеси гауссиан (GMM)

Мягкая вероятностная кластеризация: вместо «эта точка в кластере №2» — «эта точка на 70% во втором и на 30% в третьем». Смесь гауссиан (GMM) описывает кластеры эллипсами разной формы и наклона, а EM-алгоритм подгоняет их к данным, шаг за шагом наращивая правдоподобие.

Интуиция: где ломается k-means

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

Смесь гауссиан (Gaussian Mixture Model, GMM) снимает оба ограничения. Она говорит: данные порождены не точками-центрами, а несколькими гауссианами (нормальными распределениями). У каждой гауссианы свой центр μ, своя ковариация Σ (задаёт форму и наклон эллипса) и свой вес π (какая доля всех точек ей принадлежит). Точка не приписывается кластеру жёстко — вместо этого считается вероятность принадлежности (responsibility, ответственность): мягкое число от 0 до 1, и по всем кластерам они суммируются в единицу.

Как это работает: EM-алгоритм

Проблема курицы и яйца: знали бы мы параметры гауссиан — легко посчитали бы, кому какая точка принадлежит; знали бы принадлежности — легко оценили бы параметры. Не знаем ни того, ни другого. EM-алгоритм (Expectation-Maximization) разрывает круг чередованием двух шагов, каждый при фиксированной половине неизвестных:

• E-шаг (Expectation): параметры фиксированы — считаем ответственности. Для точки x ответственность кластера j — это его доля в общей плотности:
  r_j(x) = π_j·N(x | μ_j, Σ_j) / Σ_m π_m·N(x | μ_m, Σ_m)
• M-шаг (Maximization): ответственности фиксированы — обновляем параметры как взвешенные средние (вес точки = её ответственность). Новый центр — взвешенное среднее точек, новая ковариация — взвешенный разброс вокруг него, новый вес π_j — средняя ответственность кластера.

Ключевое свойство: каждый полный цикл E→M гарантированно не уменьшает лог-правдоподобие (log-likelihood) — вероятность данных при текущих параметрах. Поэтому процесс сходится. Но сходится он в локальный оптимум: как и k-means, EM чувствителен к инициализации. Отсюда те же лекарства — умный старт (k-means++) и несколько запусков с выбором лучшего по правдоподобию.

Латентная переменная и связь с вероятностным подходом

За мягким отнесением стоит красивая идея. У каждой точки есть латентная переменная (latent variable) — скрытый, не наблюдаемый номер гауссианы, которая её породила. Мы его не знаем, поэтому не можем оптимизировать напрямую. E-шаг оценивает распределение этой скрытой переменной (те самые ответственности — вероятности «точка родилась из кластера j»), а M-шаг максимизирует правдоподобие, усредняя по этой оценке. Именно поэтому GMM — это генеративная модель: она задаёт полный процесс порождения данных, и из неё можно сэмплировать новые точки, а не только раскрашивать имеющиеся.

Сколько компонент брать и почему k-means — частный случай

Число гауссиан k задаётся заранее, и просто «максимизировать правдоподобие по k» нельзя: чем больше компонент, тем выше правдоподобие (в пределе — по гауссиане на точку). Поэтому используют критерии с штрафом за сложность — BIC (Bayesian Information Criterion) и AIC (Akaike Information Criterion): они прибавляют к минус-правдоподобию штраф за число параметров и ищут баланс. Меньший BIC/AIC — лучше.

И финальная связка: k-means — это частный случай GMM. Зафиксируй у всех гауссиан одинаковую сферическую ковариацию Σ = σ²I и устреми σ → 0 — мягкие ответственности выродятся в жёсткие (0 или 1), а M-шаг превратится в обычное усреднение точек кластера. Тогда GMM буквально становится k-means. Поэтому «полный» GMM с ковариациями — это k-means, которому разрешили эллипсы, наклон и границы принадлежности.