Regroupement avec K-Means et EM: comment sont-ils liés?

50

J'ai étudié des algorithmes permettant de regrouper des données (apprentissage non supervisé): EM et k-means. Je continue à lire ce qui suit:

k-means est une variante de EM, avec l'hypothèse que les grappes sont sphériques.

Quelqu'un peut-il expliquer la phrase ci-dessus? Je ne comprends pas ce que signifie sphérique, ni comment sont liés kmeans et EM, car l’une effectue une assignation probabiliste et l’autre d’une manière déterministe.

Aussi, dans quelle situation vaut-il mieux utiliser la classification en k-means? ou utiliser le clustering EM?

Myna
la source
Sphérique signifie des matrices de variance-covariance identiques pour chaque grappe (en supposant une distribution gaussienne), également connue sous le nom de grappage basé sur un modèle. Quelle approche considérez-vous comme déterministe?
chl
2
Ce serait bien si vous donniez la source de la citation.
ttnphns
1
k-signifie "suppose" que les grappes sont des nuages ​​plus ou moins ronds et solides (pas fortement allongés, courbes ou simplement annelés) dans l'espace euclidien. Ils ne sont pas obligés de provenir de distributions normales . EM a bien besoin de cela (ou au moins un type spécifique de distribution doit être connu).
ttnphns

Réponses:

38

K signifie

  1. Difficile d’attribuer un point de données à un cluster particulier sur la convergence.
  2. Il utilise la norme L2 lors de l'optimisation (point de norme Min {Theta} L2 et ses coordonnées centroïdes).

EM

  1. Soft assigne un point aux clusters (il donne donc une probabilité qu'un point appartienne à un centroïde).
  2. Cela ne dépend pas de la norme L2, mais est basé sur l'espérance, c'est-à-dire la probabilité que le point appartienne à un cluster particulier. Cela rend les K-moyens biaisés vers les amas sphériques.
Sharan Srinivasan
la source
57

Il n'y a pas "d'algorithme de k-moyennes". Il y a l'algorithme MacQueens pour k-means, l'algorithme Lloyd / Forgy pour k-means, la méthode Hartigan-Wong, ...

Il n'y a pas non plus "l'algorithme EM". Il s’agit d’un schéma général qui consiste à s’attendre de manière répétée aux probabilités, puis à maximiser le modèle. La variante la plus populaire de l'EM est également connue sous le nom de «modélisation de mélange gaussien» (GMM), où le modèle est constitué de distributions gaussiennes à plusieurs variables.

L'algorithme de Lloyds peut être composé de deux étapes:

  • l'étape E, où chaque objet est affecté au centroïde de sorte qu'il soit affecté au cluster le plus probable.
  • l'étape M, où le modèle (= centroïdes) est recalculé (= optimisation des moindres carrés).

Comme le fait Lloyd, itérer ces deux étapes en fait un exemple du schéma général de la SE. Il diffère de GMM que:

  • il utilise le partitionnement dur, c'est-à-dire que chaque objet est affecté à exactement un cluster
  • le modèle est uniquement centroïde, aucune covariance ou variance n’est prise en compte
Anony-Mousse
la source
Pouvez-vous développer un peu sur les variantes de -means? J'ai jeté un coup d'œil dans Les éléments de l'apprentissage statistique (Hastie, Tibshirani, Friedman), chapitre 14 ... Ils soutiennent l'idée de l'existence d'un " algorithme moyen". kkk
Elvis
10
Beaucoup de livres égalent k-means avec l'algorithme lloyds, mais il ne l'a jamais appelé k-means. MacQueen a introduit le nom k-means. Désolé, beaucoup de livres utilisent des noms incorrects ici . k-means est le problème, lloyd n'est qu'une solution populaire. En fait, R exécutera Hartigan-Wong par défaut pour résoudre les kméens.
Anony-Mousse
4

Voici un exemple, si je le faisais avec mplus, ce qui pourrait être utile et compléter des réponses plus complètes:

Disons que j'ai 3 variables continues et que je veux identifier les grappes basées sur celles-ci. Je spécifierais un modèle de mélange (plus spécifiquement dans ce cas, un modèle de profil latent), en supposant une indépendance conditionnelle (les variables observées sont indépendantes, compte tenu de l'appartenance à un cluster) comme:

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

J'exécutais ce modèle plusieurs fois, en spécifiant à chaque fois un nombre différent de clusters et en choisissant la solution qui me plaisait le plus (pour cela, il s'agit d'un vaste sujet en soi).

Pour ensuite exécuter k-means, je spécifierais le modèle suivant:

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

Ainsi, l'appartenance à une classe est uniquement basée sur la distance à la moyenne des variables observées. Comme indiqué dans d'autres réponses, les écarts n'ont rien à voir avec cela.

La bonne chose à faire avec mplus est que ce sont des modèles imbriqués, ce qui vous permet de vérifier directement si les contraintes entraînent un ajustement plus difficile ou non, en plus de pouvoir comparer la discordance de classification entre les deux méthodes. Soit dit en passant, ces deux modèles peuvent être estimés à l'aide d'un algorithme EM. La différence réside donc davantage dans le modèle.

Si vous pensez en 3D, les 3 moyens font un point ... et les variances les trois axes d'un ellipsoïde passant par ce point. Si les trois variations sont identiques, vous obtiendrez une sphère.

DL Dahly
la source
Merci pour cet exemple. Cela aide beaucoup à corriger certaines idées.
Myna