Кластеризация с K-Means и EM: как они связаны?

50

Я изучал алгоритмы кластеризации данных (обучение без учителя): EM и k-means. Я продолжаю читать следующее:

К-среднее является вариантом EM, с предположениями, что кластеры являются сферическими.

Может кто-нибудь объяснить вышеприведенное предложение? Я не понимаю, что означает сферическое, и как связаны kmeans и EM, поскольку одно выполняет вероятностное назначение, а другое - детерминистическим образом.

Кроме того, в какой ситуации лучше использовать кластеризацию k-средних? или использовать EM кластеризацию?

Майна
источник
Сферический означает идентичные дисперсионно-ковариационные матрицы для каждого кластера (при условии гауссовского распределения), который также известен как кластеризация на основе моделей. Какой подход вы считаете детерминированным?
chl
2
Было бы неплохо, если бы вы дали источник цитирования.
ttnphns
1
k-означает «предполагает», что скопления являются более или менее круглыми и сплошными (не сильно вытянутыми, не изогнутыми или просто кольцевыми) облаками в евклидовом пространстве. Они не обязаны поступать из нормальных дистрибутивов. EM действительно требует этого (или, по крайней мере, конкретный тип распределения должен быть известен).
ttnphns

Ответы:

38

К означает

  1. Трудно назначить точку данных для одного конкретного кластера при конвергенции.
  2. При оптимизации используется норма L2 (точка нормы Min {Theta} L2 и ее координаты центроида).

ЭМ

  1. Софт назначает точку кластерам (таким образом, она дает вероятность любой точки, принадлежащей любому центроиду).
  2. Он не зависит от нормы L2, но основан на ожидании, т. Е. Вероятности точки, принадлежащей конкретному кластеру. Это делает K-средства смещенными к сферическим кластерам.
Шаран Шринивасан
источник
57

Не существует «алгоритма k-средних». Есть алгоритм MacQueens для k-средних, алгоритм Ллойда / Форги для k-средних, метод Хартиган-Вонга, ...

Также не существует "ЭМ-алгоритма". Это общая схема многократного ожидания вероятностей и последующего максимизации модели. Наиболее популярный вариант EM также известен как «моделирование гауссовой смеси» (GMM), где модели представляют собой многомерное распределение Гаусса.

Можно считать, что алгоритм Ллойда состоит из двух шагов:

  • электронный шаг, где каждый объект назначается центроиду так, что он назначается наиболее вероятному кластеру.
  • M-шаг, где модель (= центроиды) пересчитывается (= оптимизация по методу наименьших квадратов).

... повторение этих двух шагов, как это сделал Ллойд, фактически делает это примером общей схемы EM. От GMM отличается тем, что:

  • он использует жесткое разбиение, т.е. каждый объект назначается ровно одному кластеру
  • модель - только центроиды, никакие ковариации или отклонения не принимаются во внимание
Anony-Мус
источник
kk
10
Многие книги равны k-средних с алгоритмом lloyds, но он никогда не называл это k-средних. Маккуин ввел название k-means. Извините: многие книги используют неправильные названия здесь . К-средним является проблема, Ллойд только одно популярное решение. На самом деле R по умолчанию будет запускать Hartigan-Wong для решения kmeans.
Anony-Mousse
4

Вот пример, если бы я делал это в mplus, что могло бы быть полезным и дополнить более полные ответы:

Скажем, у меня есть 3 непрерывные переменные, и я хочу определить кластеры на их основе. Я бы определил смешанную модель (более конкретно в данном случае модель скрытого профиля), предполагая условную независимость (наблюдаемые переменные являются независимыми, учитывая членство в кластере) как:

Model: 
%Overall%
v1* v2* v3*;  ! Freely estimated variances
[v1 v2 v3];   ! Freely estimated means

Я бы запускал эту модель несколько раз, каждый раз задавая разное количество кластеров, и выбирал решение, которое мне больше всего нравится (для этого сама по себе обширная тема).

Чтобы потом запустить k-means, я бы указал следующую модель:

Model: 
%Overall%
v1@0 v2@0 v3@0;  ! Variances constrained as zero
[v1 v2 v3];      ! Freely estimated means

Таким образом, членство в классе основывается только на расстоянии до средних значений наблюдаемых переменных. Как указано в других ответах, отклонения не имеют к этому никакого отношения.

Хорошая особенность этого в mplus - это то, что они являются вложенными моделями, и поэтому вы можете непосредственно проверить, приводят ли ограничения к худшему соответствию или нет, в дополнение к возможности сравнить расхождения в классификации между двумя методами. Кстати, обе эти модели могут быть оценены с использованием EM-алгоритма, так что разница действительно больше в модели.

Если вы думаете в трехмерном пространстве, 3 средства составляют точку ... и отклонения трех осей эллипсоида, проходящего через эту точку. Если все три отклонения одинаковы, вы получите сферу.

DL Dahly
источник
Спасибо за этот пример. Это очень помогает исправить некоторые идеи.
Майна