fr en

Modèles de mélanges gaussiens : k-moyennes sous stéroïdes

Posté le Sat 22 December 2018 dans machine learning • 5 min de lecture

Cet article est le numéro 3 de la série "clustering" :

L' algorithme des k-moyennes suppose que les données sont générées par un mélange de Gaussiennes ayant chacune la même proportion, la même variance et aucune covariance. Ces hypothèses peuvent être allégées avec un algorithme plus générique : l'algorithme CEM appliqué à un mélange de Gaussiennes.

Pour illustrer cela, nous allons d’abord appliquer un algorithme de classification plus générique que les k-moyennes à neuf jeux de données synthétiques précédemment utilisés dans cette série. Le critère interne et une variation de celui-ci seront présentés ainsi que les algorithmes pour les optimiser. La complexité des algorithmes sera exposée : cela permet d'expliquer pourquoi l'utilisation de l'algorithme des k-moyennes est cohérente au lieu d'un algorithme plus générique.

Comportement du mélange gaussien

Commençons par appliquer un modèle de mélange gaussien à certains jeux de données. Pour cela, la bibliothèque Rmixmod (voir en particulier l'article sur Rxmimod dans le Journal of Statistical Software pour plus de détails) est utilisée avec ses paramètres par défaut (seul le nombre de clusters est spécifié).

library("Rmixmod")

processMixmod <- function(data) {
    d = data %>% select(x, y)
    x = mixmodCluster(d, 2)
    x["bestResult"]["partition"]
}

dataMixmod = data %>%
             group_by(dataset) %>%
             do(data.frame(., cluster = factor(processMixmod(.))))

scatterPlotWithLabels(dataMixmod)

algorithme CEM appliqué à 9 jeu de données.

Les graphiques montrent que les modèles de mélanges gaussiens s'adaptent mieux aux jeux de données que les k-moyennes, qui ne s’adapte bien qu'au premier jeu de données. En particulier, les cinq premiers jeux de données sont générés par un mélange de Gaussiennes, ce qui explique pourquoi les modèles de mélanges gaussiens fonctionnent bien. Les autres jeux de données, à l'exception de celui qui correspond à deux classes de points distribués uniformément, ne sont pas correctement ajustés car ils sont générés différemment (d'ailleurs, le dernier jeu de données ne présente aucune classe).

Le critère interne optimisé par l'algorithme utilisé, à savoir EM, explique pourquoi cela fonctionne pour le mélange de Gaussiennes.

Algorithmes EM et CEM

L'algorithme EM est un algorithme itératif qui est constitué de deux étapes : une étape "expectation" et une étape "maximisation", d'où son nom. L'algorithme CEM comprend une autre étape de "classification" entre les deux étapes de l'algorithme EM. Les deux algorithmes diffèrent aussi légèrement par leur critère.

Algorithme EM

Avec l'algorithme EM, nous cherchons à maximiser la log vraisemblance :

\begin{equation*} L_M(\theta) = log(\prod_{i}f(x_i, \theta))= \sum_i \log (\sum_{k=1}^K \pi_k \varphi_k (x_i, \alpha_k)) \end{equation*}

où :

\(K\) est le nombre de clusters ;
\(\theta = (\pi, \alpha)\) avec \(\pi\) est un vecteur de proportions et \(\alpha\) est un vecteur de paramètres d'une composante ;
\(\varphi_k(x_i, \alpha_k)\) est la densité d'une observation \(x_i\) issus de la \(k^{ème}\) composante.

Maximiser la vraisemblance signifie que nous voulons maximiser la plausibilité des valeurs des paramètres du modèle, en fonction des données observées. L'algorithme EM appliqué à un mélange de Gaussiennes essaie de trouver les paramètres du mélange (les proportions) et les Gaussiennes (les moyennes et les matrices de covariances) qui correspondent le mieux aux données. Les affectations aux clusters sont ensuite trouvées a posteriori : les points générés par une Gaussienne doivent être classés dans le même cluster.

Algorithme CEM

L'algorithme CEM considère les assignations aux clusters comme des paramètres à apprendre. Le critère optimisé par CEM est :

\begin{equation*} L_C(\theta) = log(f(x, \theta, z))= \sum_{i, k} z_{ik} \log (\pi_k \varphi_k (x_i, \alpha_k)) \end{equation*}

avec \(z_{ik} = 1\) si le point \(x_i\) est assigné au cluster \(k\) et \(0\) sinon.

L'algorithme CEM est souvent préférable à EM lors d'un clustering car il vise directement à apprendre l'assignation des clusters, et non pas a posteriori. Il converge souvent plus rapidement en pratique que EM. C'est aussi une généralisation des k-moyennes.

L'algorithme CEM en tant qu'extension des k-moyennes

L'algorithme CEM appliqué pour un mélange de Gaussiennes avec certaines hypothèses sur les Gaussiennes (pas de covariance et variance égale) et sur le mélange (proportions égales) est en fait le même que l'algorithme des k-moyennes. Avec ces hypothèses, les critères sont les mêmes (voir le post précédent sur les k-moyennes), et il est possible de montrer que les étapes sont également les mêmes.

Voyons cela lorsque nous entrainons CEM en imposant un mélange de Gaussiennes avec des matrices de variance diagonales et des volumes égaux, des proportions et formes égales (voir page 25 du manuel de référence de Rmixmod) :

library("Rmixmod")

processMixmod2 <- function(data) {
    d = data %>% select(x, y)
    x = mixmodCluster(d, 2,
                      models=mixmodGaussianModel(listModels=c("Gaussian_p_L_I")),
                      strategy=new("Strategy", algo="CEM"))
    x["bestResult"]["partition"]
}

dataMixmod = data %>%
             group_by(dataset) %>%
             do(data.frame(., cluster = factor(processMixmod2(.))))

scatterPlotWithLabels(dataMixmod)

L'algorithme CEM appliqué aux 9 jeux de données avec les hypothèses des k-moyennes.

Nous obtenons les mêmes résultats qu'avec les k-moyennes.

Puisque les modèles de mélanges gaussiens sont plus généraux, on pourrait penser qu'il n’y a aucune raison d’utiliser les k-moyennes. Cependant, l'algorithme des k-moyennes a moins de paramètres à estimer et est donc plus rapide et nécessite moins de mémoire. Explorons ceci.

Nombre de paramètres à estimer

Lors de l'entrainement d'un mélange de Gaussiennes, nous devons estimer les proportions du mélange et les paramètres de chaque Gaussiennne :

Comme la somme des proportions doit être égale à un, il suffit d'estimer \(K-1\) proportions, avec \(K\) le nombre de Gaussiennes.
Nous devons également estimer une moyenne pour chaque Gaussienne, donc \(K d\) paramètres avec \(d\) le nombre de dimensions.
La matrice de covariance est une matrice carrée de dimensions \(d \times d\) symétrique (les entrées situées au-dessous de la diagonale principale sont identiques à celles qui sont au-dessus). Nous avons donc \(\frac{d (d-1)}{2}\) valeurs à estimer pour chaque Gaussienne.

Globalement, nous avons, pour la forme générale du mélange de Gaussiennes (sans aucune condition) \(K-1 + Kd + \frac{Kd(d-1)}{2}\) paramètres à estimer avec :

\(K\) le nombre de Gaussiennes (ou classes) ;
\(d\) le nombre de variables.

Si nous imposons des conditions sur le modèle, nous pouvons réduire le nombre de paramètres à estimer. Par exemple, si nous supposons que les matrices de covariance sont diagonales avec une variance égale (un scalaire fois la matrice identité) et que les proportions du mélange sont les mêmes, nous avons alors d + 1 paramètres à estimer. Cela correspond aux hypothèses des k-moyennes.

Pour résumer

Les modèles de mélanges gaussiens avec l'algorithme CEM peuvent être vus comme une généralisation des k-moyennes : alors que les données des k-moyennes sont supposées être générées par un mélange de Gaussiennes ayant les mêmes proportions et des matrices de covariance diagonales, les modèles de mélanges gaussiens permettent d'avoir d'autres hypothèses sur les proportions du mélange et sur les matrices de covariance des Gaussiennes.
Imposer des conditions sur les paramètres des Gaussiennes et sur le mélange permet de réduire le nombre de paramètres à estimer et donc de réduire le temps d’exécution de l’algorithme.
Plusieurs algorithmes ont pour but de s’adapter à un mélange de Gaussiennes. Par exemple, l'algorithme EM estime les paramètres du mélange et les classes sont obtenues a posteriori. L’algorithme CEM estime les paramètres et les affectations aux clusters simultanément, permettant ainsi de réduire le temps d’exécution.

Previous Post Next Post