dimanche 9 mars 2008

Classification automatique - Algorithme EM

Les modèles de mélanges traduisent une fonction de densité régissant la distribution de données à l'aide d'une combinaison linéaire de fonctions de densité élémentaires. L'approche la plus connue est le modèle de mélange gaussien où les densités élémentaires sont des lois normales multidimensionnelles.

Cette technique peut être utilisée pour décrire la distribution des données en classification automatique. Chaque classe (groupe, cluster, etc.) est décrite par une loi de distribution normale, paramétrée par son centre de gravité et sa matrice de variance covariance. Pour estimer les paramètres des distributions élémentaires, l'algorithme EM (Expectation-Maximization) est certainement le plus connu. L'objectif est de maximiser la logvraisemblance de l'échantillon de données compte tenu d'un nombre de cluster défini au préalable.

Dans ce didacticiel, nous montrons l'intérêt de cette approche sur des données artificielles. Malgré la difficulté du problème proposé, l'algorithme EM trouve parfaitement la solution adéquate. Nous donnons des indications également pour détecter au mieux, de manière raisonnée en tous les cas, le bon nombre de groupes, un problème récurrent de la classification automatique.

Malgré sa puissance, cette technique est peu diffusée, peu utilisée, peu enseignée, peut être parce qu'elle est rarement implémentée dans les logiciels de Data Mining.

Mots clés : classification automatique, algorithme EM, modèle de mélange gaussien, maximisation de la vraisemblance, choix du nombre de classes
Composants : EM-Clustering, K-Means, EM-Selection, scatterplot
Lien : fr_Tanagra_EM_Clustering.pdf
Données : two_gaussians.xls
Références :
Wikipédia (fr) -- Algorithme espérance-maximisation
Wikipédia (en) -- Expectation-maximization algorithm