Clustering com K-Means e EM: como eles estão relacionados?

50

Estudei algoritmos para agrupar dados (aprendizado não supervisionado): EM e k-means. Eu continuo lendo o seguinte:

O k-means é uma variante do EM, com as suposições de que os clusters são esféricos.

Alguém pode explicar a frase acima? Eu não entendo o que significa esférico e como kmeans e EM estão relacionados, uma vez que um faz uma atribuição probabilística e o outro de uma maneira determinística.

Além disso, em que situação é melhor usar o cluster de k-means? ou usar o clustering EM?

Myna
fonte
Esférico significa matrizes de variância-covariância idênticas para cada cluster (assumindo distribuição gaussiana), que também é conhecida como cluster baseado em modelo. Qual abordagem você considera determinista?
chl
2
Seria bom se você der a fonte da citação.
ttnphns
11
k-significa "assume" que os aglomerados são mais ou menos redondos e sólidos (não muito alongados, curvados ou apenas com anéis) de nuvens no espaço euclidiano. Eles não precisam vir de distribuições normais . O EM exige isso (ou pelo menos tipo específico de distribuição a ser conhecido).
ttnphns

Respostas:

38

K significa

  1. Atribua um ponto de dados a um cluster específico na convergência.
  2. Ele utiliza a norma L2 ao otimizar (ponto da norma Min {Theta} L2 e suas coordenadas do centróide).

EM

  1. Soft atribui um ponto a aglomerados (portanto, fornece uma probabilidade de qualquer ponto pertencente a qualquer centróide).
  2. Não depende da norma L2, mas é baseada na expectativa, ou seja, na probabilidade do ponto pertencer a um cluster específico. Isso faz com que os meios K tendam para clusters esféricos.
Sharan Srinivasan
fonte
57

Não existe um "algoritmo k-means". Existe o algoritmo MacQueens para k-means, o algoritmo Lloyd / Forgy para k-means, o método Hartigan-Wong, ...

Também não existe "o" algoritmo EM. É um esquema geral de esperar repetidamente as probabilidades e depois maximizar o modelo. A variante mais popular do EM também é conhecida como "Modelagem de Mistura Gaussiana" (GMM), onde o modelo é distribuições gaussianas multivariadas.

Pode-se considerar que o algoritmo Lloyds consiste em duas etapas:

  • a etapa E, em que cada objeto é atribuído ao centróide, de forma que seja atribuído ao cluster mais provável.
  • a etapa M, onde o modelo (= centróide) é recalculado (= otimização de mínimos quadrados).

... iterar essas duas etapas, como feito por Lloyd, torna isso efetivamente uma instância do esquema geral de EM. Difere do GMM que:

  • usa particionamento rígido, ou seja, cada objeto é atribuído a exatamente um cluster
  • o modelo é apenas centróide, nenhuma covariância ou variação é levada em consideração
Anony-Mousse
fonte
kk
10
Muitos livros igualam k-means ao algoritmo lloyds, mas ele nunca o chamou de k-means. MacQueen introduziu o nome k-means. Desculpe: muitos livros usam nomes incorretos aqui . k-means é o problema, Lloyd apenas uma solução popular. De fato, o R executará o Hartigan-Wong por padrão para resolver kmeans.
Anony-Mousse
4

Aqui está um exemplo, se eu estivesse fazendo isso no mplus, o que poderia ser útil e complementar respostas mais abrangentes:

Digamos que eu tenho 3 variáveis ​​contínuas e quero identificar clusters com base nelas. Eu especificaria um modelo de mistura (mais especificamente neste caso, um modelo de perfil latente), assumindo independência condicional (as variáveis ​​observadas são independentes, dada a associação ao cluster) como:

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

Eu executaria esse modelo várias vezes, sempre especificando um número diferente de clusters, e escolheria a solução que eu mais gosto (fazer isso por si só é um vasto tópico).

Para executar o k-means, eu especificaria o seguinte modelo:

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

Portanto, a participação na turma é baseada apenas na distância das médias das variáveis ​​observadas. Como afirmado em outras respostas, as variações não têm nada a ver com isso.

O bom de fazer isso no mplus é que esses são modelos aninhados e, portanto, você pode testar diretamente se as restrições resultam em pior ajuste ou não, além de poder comparar discordâncias na classificação entre os dois métodos. A propósito, ambos os modelos podem ser estimados usando um algoritmo EM, então a diferença é realmente mais sobre o modelo.

Se você pensa no espaço 3D, o 3 significa fazer um ponto ... e as variações nos três eixos de um elipsóide que atravessa esse ponto. Se todas as três variações forem iguais, você obteria uma esfera.

DL Dahly
fonte
Obrigado por este exemplo. Ajuda muito a consertar algumas idéias.
Myna