Partager :

Concepts Fondamentaux en Statistique


Data Mining :

Des Techniques Performantes de Segmentation :

La Classification Généralisée EM et les k-Moyennes



Sommaire :


Principes Fondamentaux

Les méthodes proposées dans le module Classification Généralisée EM et k-Moyennes de STATISTICA s'apparentent à celles mises en oeuvre par l'algorithme des k-Moyennes du module classique de Classifications, et nous vous invitons à consulter la rubrique k-Moyennes - Introduction pour une présentation générale de ces techniques et de leurs applications. L'objectif de ces techniques consiste généralement à détecter des classes d'observations (ou de variables), et d'affecter ces observations aux classes (clusters).

C'est l'application par excellence que nous pouvons rencontrer dans les études de marché où nous mesurons un certain nombre de variables comportementales (habitudes de consommation) sur un large échantillon de consommateurs ; l'objectif de l'analyse consiste à mettre en évidence des "segments de marché", c'est-à-dire des groupes de consommateurs assez homogènes (au sein de la même classe) par rapport aux individus "appartenant" aux autres classes. En outre, lorsque nous parvenons à identifier ces classes, nous souhaitons généralement déterminer dans quelle mesure ces classes sont différentes les unes des autres, c'est-à-dire, quelles sont les variables ou dimensions spécifiques sur lesquelles les membres des différentes classent varient, et dans quelle mesure.

Classification par les k-Moyennes. L'algorithme classique des k-Moyennes a été vulgarisé et affiné par Hartigan (1975 ; voir aussi Hartigan et Wong, 1978). Plus précisément, STATISTICA utilise la méthode de Lloyd pour mettre en oeuvre son algorithme des k-Moyennes. Le principe de cet algorithme est assez simple : compte tenu d'un nombre déterminé (souhaité ou supposé) de k classes, nous allons affecter les observations à ces différentes classes de telle sorte que les moyennes par classe (pour l'ensemble des variables) soient aussi différentes que possible d'une classe à l'autre (voir aussi la rubrique Différences entre les Algorithmes k-Moyennes du Module Classification Généralisée EM & k-Moyennes et du Module Classifications pour plus d'informations concernant les algorithmes de calcul spécifiques qui sont utilisés dans ces deux modules de STATISTICA).

Extensions et généralisations. Les méthodes utilisées dans le module Classification Généralisée EM et k-Moyennes de STATISTICA permettent d'améliorer cette approche élémentaire de la classification à trois égards :

  1. Au lieu d'affecter les observations aux classes en cherchant à maximiser les différences entre les moyennes des variables continues, l'algorithme de classification EM (expectation maximization) va calculer les probabilités d'appartenance aux différentes classes sur la base d'une ou plusieurs distributions de probabilité. L'objectif de l'algorithme de classification consiste alors à maximiser la probabilité ou la vraisemblance globale des données, compte tenu des classes (finales).

  2. Contrairement à l'algorithme classique des k-Moyennes du module Classifications, les algorithmes k-Moyennes et EM du module Classification Généralisée EM et k-Moyennes peuvent s'appliquer à la fois sur des variables catégorielles et continues.

  3. L'un des principaux inconvénients de l'algorithme classique des k-Moyennes réside dans le fait que vous devez spécifier le nombre de classes avant de démarrer l'analyse (c'est-à-dire que le nombre de classes doit être connu a priori) ; le module Classification Généralisée EM et k-Moyennes utilise une version modifiée du schéma de validation croisée par v-ensembles (v-fold) (proche de celle qui est utilisée dans les modules Arbres de Décision [Classification], Modèles d'Arbres de Classification et de Régression et Modèles CHAID) afin de déterminer le nombre optimal de classes à produire. Cette extension rend le module Classification Généralisée EM et k-Moyennes particulièrement utile comme outil de data mining dans le cadre de l'apprentissage non-supervisé et pour détecter des structures.

Witten et Frank (2000) présentent les différentes techniques de classification dans le cadre du data mining. Les paragraphes suivants présentent en détail les méthodes contenues dans ce module.

Apprentissage Supervisé vs. Apprentissage Non-Supervisé

Une distinction importante en machine learning que l'on retrouve également en data mining, concerne les algorithmes d'apprentissage supervisé par opposition aux algorithmes d'apprentissage non-supervisé. Le terme "apprentissage supervisé" fait généralement référence aux situations où nous connaissons déjà une classification donnée que nous avons enregistrée dans un échantillon d'apprentissage ; nous cherchons alors à construire un modèle pour prévoir ces classifications (dans un nouvel échantillon de test). Par exemple, nous pouvons disposer d'un jeu de données dans lequel nous connaissons, parmi une liste d'individus ciblés pour une promotion commerciale particulière, ceux qui ont répondu et ceux qui n'ont pas répondu à l'offre ; l'objectif de la classification consiste alors à créer un modèle qui va nous permettre de prévoir (à partir d'une liste de nouveaux prospects) ceux qui ont le plus de chances de donner suite à la même offre (ou à une offre similaire) dans le futur. Vous pouvez examiner les méthodes présentées dans les modules Modèles d'Arbres de Classification et de Régression (GC&RT), Modèles CHAID (GCHAID), Analyse Discriminante et Modèles Généraux d'Analyse Discriminante (GDA), ou encore dans le module STATISTICA Réseaux de Neurones Automatisés pour plus d'informations concernant les différentes techniques permettant de construire ou ajuster des modèles dans lesquels la variable de sortie étudiée (par exemple, le prospect a répondu ou n'a pas répondu à une offre commerciale) est observée. Ces méthodes sont regroupées sous la dénomination d'algorithmes d'apprentissage "supervisé", dans la mesure où l'apprentissage (ajustement de modèles) est "guidé" ou "supervisé" par les classifications observées que nous avons enregistrées dans le fichier de données.

La situation est différente avec l'apprentissage non-supervisé. Ici, la variable qui nous intéresse n'est pas (ou ne peut pas être) observée. Nous souhaitons mettre en évidence une certaine "typologie" dans nos données que nous n'avons pas pu observer de façon évidente. Par exemple, vous pouvez disposer d'une base de données contenant divers indicateurs démographiques ou économiques qui peuvent se révéler pertinents pour étudier un comportement d'achat ultérieur. Votre objectif va alors consister à identifier des segments de marché, c'est-à-dire des groupes d'individus relativement proches sur un certain nombre de variables ; une fois que vous avez identifié ces segments de marché, vous allez pouvoir déterminer la meilleure manière d'approcher cette ou ces classes d'individus en proposant différents biens ou services adaptés, pour lesquels vous pensez qu'il peut exister un potentiel ou un intérêt pour les individus de ce segment (classe). Ce type de tâche fait appel à un algorithme d'apprentissage non-supervisé, dans la mesure où l'apprentissage (ajustement de modèles) ne peut pas être dicté par une classification connue a priori ; ce n'est qu'après avoir identifié certaines classes que vous allez pouvoir commencer à libeller les classes, par exemple, sur la base d'études ultérieures (par exemple, après avoir identifié un groupe de clients "jeunes et à risque"). Parmi les autres méthodes d'apprentissage non-supervisé (en dehors de la classification généralisée k-Moyennes ou EM), citons notamment l'Analyse Factorielle, l'ACP "à la Française", l'Analyse de Proximité, l'Analyse des Correspondances, les Cartes Auto-Organisatrices de Kohonen (SOFM), etc...

L'Algorithme des k-Moyennes

L'algorithme classique des k-Moyennes est présenté dans les rubriques d'Introduction du module Classifications ; Hartigan et Wong (1978) proposent par ailleurs une approche complète et détaillée. Pour réitérer, la logique de l'algorithme classique des k-Moyennes est assez simple : compte tenu d'un nombre donné de classes k, l'algorithme va chercher à déplacer les observations d'une classe à une autre afin de maximiser les distances entre les centres des classes ; les centres de gravité des classes sont généralement définis par un vecteur des moyennes de toutes les variables (continues) de l'analyse.

Classification de variables catégorielles. Le module Classifications de STATISTICA utilise l'algorithme classique des k-Moyennes, qui ne peut s'appliquer qu'à des variables continues. Dans le module Classification Généralisée EM et k-Moyennes, vous pouvez également spécifier des variables catégorielles pour vos analyses. Au lieu de définir le centre de gravité d'une classe particulière par les moyennes des variables (continues) respectives (des observations de cette classe), nous allons déterminer, dans le cas de variables catégorielles, la classe (modalité de la variable catégorielle) à laquelle la majorité des observations de la classe appartient. Ainsi, par exemple, si une classe particulière d'une analyse comportant une variable Sexe contient une majorité (>50%) d'hommes, le centre de cette classe sera la modalité Homme.

Mesure des distances. L'algorithme des k-Moyennes du module Classifications calcule toujours les distances entre les classes sur la base des distances euclidiennes (au carré) entre les centres de gravité des classes (vecteurs de moyennes des variables continues utilisées dans les analyses). Dans le module Classification Généralisée EM et k-Moyennes, vous pouvez choisir entre un certain nombre de mesures des distances pour vos analyses : Euclidienne, Euclidienne au Carré, City-Block et Chebychev. Ces différentes mesures des distances sont décrites dans la rubrique Classification Ascendante Hiérarchique - Introduction - Mesure des Distances du module Classifications et sont toujours calculées pour des distances normalisées ; voir aussi la rubrique Différences entre les Algorithmes k-Moyennes du Module Classification Généralisée EM & k-Moyennes et du Module Classifications. Remarque : pour les variables catégorielles, les distances ne peuvent être égales qu'à 0 (zéro) ou 1 (un) : 0 si la classe à laquelle une observation particulière appartient est la même que celle qui se retrouve avec la plus forte fréquence dans la classe respective (voir aussi le paragraphe précédent), et 1 si elle est différente de cette classe. Par conséquent, sauf pour la distance de Chebychev, les différentes mesures des distances vont produire des résultats identiques pour les variables catégorielles.

L'Algorithme EM

L'algorithme de classification EM est décrit en détail dans l'ouvrage de Witten et Frank (2001). L'approche et la logique de cette méthode de classification sont les suivantes : Imaginons que nous ayons mesuré une variable continue dans un grand échantillon d'observations. Supposons que cet échantillon soit constitué de deux classes d'observations avec des moyennes différentes (et peut-être des écarts-types différents) ; au sein de chaque échantillon, la distribution des valeurs de la variable continue suit la Loi Normale. La distribution des valeurs (dans la population) peut avoir l'aspect suivant :

Combinaison de distributions. L'illustration ci-dessus représente deux distributions normales avec des moyennes et des écarts-types différents, ainsi que la somme des deux distributions. Imaginons que nous ne pouvons observer que le résultat (la somme) des deux distributions normales (de moyennes et d'écarts-types différents). L'objectif de la classification EM va consister à estimer les moyennes et écarts-types de chaque classe, de sorte à maximiser la vraisemblance des données observées (distribution). En d'autres termes, l'algorithme EM va chercher à approcher les distributions observées des valeurs sur la base de combinaisons de distributions différentes dans les différentes classes.

L'algorithme EM du module Classification Généralisée EM et k-Moyennes vous permet de sélectionner les distributions suivantes pour les variables continues : normale, log-normale et de Poisson. Vous pouvez sélectionner des distributions différentes pour les différentes variables, et donc obtenir des classes pour des mélanges de différents types de distributions.

Variables catégorielles. L'algorithme EM de STATISTICA peut également traiter des variables catégorielles. Le programme va tout d'abord affecter au hasard différentes probabilités (des poids pour être précis) à chaque catégorie, pour chacune des classes ; au cours des itérations successives, ces probabilités sont affinées (ajustées) afin de maximiser la vraisemblance des données, compte tenu du nombre de classes spécifié.

Probabilités de classification au lieu des classifications. Les résultats de la classification EM sont différents de ceux produits par la classification k-Moyennes : cette dernière va affecter les observations aux classes en cherchant à maximiser les distances entre les classes. L'algorithme EM ne calcule pas les véritables affectations des observations aux classes, mais des probabilités de classification. En d'autres termes, chaque observation appartient à une classe avec une certaine probabilité. Ce n'est que dans la boîte de dialogue finale des Résultats que vous pouvez examiner l'affectation des observations aux classes, sur la base des probabilités (les plus fortes) de classification.

Trouver le Nombre Optimal de Classes : La Validation Croisée par v-Ensembles (v-Fold)

Les techniques de classification disponibles dans le module Classification Généralisée EM et k-Moyennes ont été spécifiquement optimisées et adaptées pour traiter des problématiques courantes en data mining. La métaphore du data mining fait référence aux situations où l'analyste va chercher des structures et des "pépites" exploitables dans les données, sans aucun a priori quant aux résultats qu'il pourra découvrir (par opposition à l'approche des tests d'hypothèses, courants en recherche scientifique). En pratique, l'analyste ne connaît généralement pas à l'avance le nombre de classes qu'il va pouvoir identifier dans l'échantillon. C'est la raison pour laquelle le programme intègre un algorithme de validation croisée par v-ensembles (v-fold) afin de déterminer automatiquement le nombre de classes dans les données.

Cet algorithme est extrêmement utile dans toutes les tâches générales de "détection de structure". Notamment, pour déterminer le nombre de segments de marché dans une étude marketing, le nombre de comportements d'achat distincts dans des études relatives aux habitudes de consommation, le nombre de classes de symptômes médicaux différents, le nombre de types (classes) de documents différents en text mining, le nombre d'influences climatiques en recherche météorologique, la typologie des éléments défectueux sur des circuits imprimés, et ainsi de suite.

L'algorithme de validation croisée v-ensembles (v-fold) s'applique également à la classification. Vous trouverez un descriptif complet de l'algorithme de validation croisée v-ensembles (v-fold) dans le cadre des modules Arbres de Décision [Classification], Modèles d'Arbres de Classification et de Régression (GC&RT) et Modèles CHAID. L'idée générale de cette méthode consiste à répartir l'échantillon global en un certain nombre v d'ensembles, ou de tirer au hasard des sous-échantillons. La même analyse est alors appliquée successivement à toutes les observations des v-1 ensembles (échantillons d'apprentissage), et les résultats des analyses sont ensuite appliqués à l'échantillon v (échantillon ou ensemble qui n'a pas été utilisé pour estimer les paramètres, construire l'arbre de décision, déterminer les classes, etc... ; il s'agit plus précisément de l'échantillon de test) afin de calculer un indice de la validité prédictive. Les résultats des v réplications sont ensuite agrégés (on en détermine la moyenne) afin de produire une mesure synthétique de la robustesse du modèle respectif, c'est-à-dire, de la validité du modèle pour prévoir de nouvelles observations.

Comme indiqué précédemment, la classification est une technique d'apprentissage non-supervisé où nous ne sommes pas en mesure d'observer le (véritable) nombre de classes dans les données. Nous pouvons toutefois remplacer la notion habituelle (applicable à l'apprentissage supervisé) de "précision" par celle de "distance" : D'une manière générale, nous pouvons appliquer la méthode de la validation croisée par v-ensembles (v-fold) à un certain intervalle de nombre de classes, et la distance moyenne des observations (dans les échantillons de test ou de validation croisée) à leurs centres de classes (dans la classification par les k-Moyennes) ; en classification EM, la mesure équivalente est la (log-) vraisemblance négative moyenne que nous calculons pour les observations dans les échantillons de test.

Étudions à présent les résultats de la validation croisée v-ensembles. Un graphique est plus parlant pour illustrer notre propos.

Ci-dessus, les résultats de l'analyse d'un jeu de données qui comporte trois classes d'observations (plus précisément, il s'agit du fichier de données Iris rapporté par Fisher, 1936, et largement référencé dans la littérature sur l'analyse discriminante ; voir aussi la rubrique Analyse Discriminante - Exemple). Vous pouvez également voir (sur le graphique de droite) les résultats de l'analyse de nombres aléatoires normaux. Les "véritables données" (sur le graphique de gauche) révèlent un tracé caractéristique qui s'apparente au tracé des valeurs propres (voir également le module d'Analyse Factorielle), dans lequel la fonction de coût (dans ce cas, 2 fois la log-vraisemblance des données de validation croisée, compte tenu des paramètres estimés) décroît rapidement à mesure que le nombre de classes augmente, puis (au delà de 3 classes) se stabilise, et enfin, augmente, ce qui révèle un sur-ajustement des données. À l'inverse, les nombres aléatoires ne présentent pas cette structure, et en fait, il n'existe quasiment aucune diminution dans la fonction de coût, qui va rapidement augmenter à mesure que le nombre de classes augmente (et que le sur-ajustement survient).

Nous voyons ainsi, à partir de cette simple illustration, comment la validation croisée par v-ensemble (v-fold) appliquée à la classification par les k-Moyennes et à la classification EM permet de déterminer efficacement le nombre optimal de classes dans les données.

Quelques Défauts : les Minima Locaux et les Mauvaises Valeurs de Départ

Si, dans la plupart des cas, le programme va trouver rapidement et efficacement des solutions rapides et valides à la classification, il existe des cas dans lesquels les algorithmes itératifs peuvent échouer.

Minima locaux. Les solutions de la classification ne sont pas uniques. Les algorithmes de la classification par les k-Moyennes comme de la classification EM convergent dans la plupart des cas sur une solution optimale, mais il n'est pas toujours garanti que cette solution soit la meilleure possible. Ces techniques sont de nature itérative, contrairement, par exemple, à la régression linéaire multiple, où nous pouvons (généralement) calculer une solution analytique unique. Dans certains cas, il se peut que le programme converge sur une solution optimale locale (par opposition à une solution optimale globale). En pratique, si vous examinez attentivement les résultats (par exemple, les centres de gravité des classes dans une classification par les k-Moyennes), vous allez rapidement identifier ce problème (par exemple, une différence importante entre les moyennes, mais uniquement sur une des nombreuses variables de l'analyse). Par ailleurs, si vous répétez vos analyses en utilisant différentes valeurs de départ (d'autres poids ou centres initiaux de classes) et que vous obtenez des résultats (classes) très différents, c'est également le signe qu'un problème s'est produit.

Mauvaises valeurs de départ. Même si vos données "contiennent" des classes clairement identifiables, il se peut que la solution finale ne parvienne pas à identifier ces classes si vous choisissez de mauvais centres initiaux de classes (pour la classification par les k-Moyennes) ou de mauvaises probabilités de classification a priori (pour la classification EM). Par exemple, si vous choisissez, dans la classification par les k-Moyennes, des centres de classe initiaux identiques, l'algorithme risque d'échouer ; si vous choisissez des centres de classe initiaux qui sont quasiment identiques, l'algorithme risque de converger sur un minimum local (voir les paragraphes précédents). À nouveau, dans la pratique, il est assez facile d'identifier ces problèmes, en examinant attentivement la solution finale : Ainsi, par exemple, s'il n'existe pas véritablement d'opposition claire sur les moyennes des différentes classes, vous avez de bonnes raisons de penser que la solution respective n'est pas stable, c'est-à-dire qu'elle ne sera pas reproductible sur d'autres fichiers de données. En répétant l'analyse plusieurs fois, ou en appliquant les méthodes de validation croisée par v-ensembles (v-fold) évoquées précédemment, ce problème est généralement résolu rapidement.

Présentation du Programme

Le module Classification Généralisée EM et k-Moyennes intègre et étend le champ des techniques de classification par les k-Moyennes et par EM (expectation maximization). Vous pouvez spécifier à la fois des variables catégorielles et continues pour vos analyses. Pour la classification par les k-Moyennes, vous pouvez spécifier différentes mesures des distances : Euclidienne, Euclidienne au Carré, City-Block (Manhattan) et Chebychev (pour plus d'informations, voir aussi la rubrique Classification Ascendante Hiérarchique - Introduction - Mesure des Distances). Pour la classification EM, vous pouvez choisir parmi plusieurs distributions pour les variables continues : normale, log-normale et Poisson.

Le programme utilise une version modifiée du schéma de validation croisée par v-ensembles (v-fold) (proche de celle utilisée dans les modules Arbres de Décision [Classification], Modèles d'Arbres de Classification et de Régression et Modèles CHAID) afin de déterminer le nombre optimal de classes. Cette extension rend le module Classification Généralisée EM et k-Moyennes particulièrement utile comme outil de data mining pour l'apprentissage non-supervisé et pour la détection de structures. Il existe différentes options de génération de code (C/C++/C#, Visual Basic et PMML) pour déployer les solutions de la classification dans un environnement de data mining. Voir aussi la rubrique Utiliser du Code C/C++/C# pour le Déploiement.

Les résultats statistiques permettent à l'utilisateur d'apprécier l'adéquation de la solution de classification finale, d'examiner l'affectation finale des observations aux classes, ou encore d'enregistrer l'appartenance aux différentes classes ainsi que d'autres statistiques pour poursuivre ses analyses.

L'implémentation des méthodes de classification dans le module Classification Généralisée EM et k-Moyennes permet de traiter de très grosses volumétries.

Différences entre les Algorithmes k-Moyennes du Module 'Classification

Généralisée EM & k-Moyennes' et du Module 'Classifications'

Les algorithmes de classification par les k-Moyennes du module Classification et du module Classification Généralisée EM & k-Moyennes sont assez proches, et sont décrits en détail par Hartigan (1975 ; Hartigan et Wong, 1978). Toutefois, les distances entre les observations et les classes (centres de gravité des classes) sont calculées différemment dans ces deux modules, et les différences peuvent conduire à des résultats assez, voire très différents.

Distances dans le module Classifications. Dans le module Classifications de STATISTICA, l'algorithme des k-moyennes utilise les distances Euclidiennes au carré non réduites comme mesure des distances ; par exemple, la distance D(i,k) d'une observation i au centre de gravité k, pour M variables continues Xj se calcule comme suit :

représente la moyenne de la variable j dans la classe k

Remarque : dans cette équation, les valeurs Xj ne sont pas réduites ; par conséquent, les distances globales sont fortement affectées par les variables possédant une étendue importante par rapport aux autres variables dans une même analyse de classification. Par exemple, si vous mesurez la Taille et le Poids des individus, et que vous exprimez la Taille en millimètres (la plupart des individus mesurant entre 1.500 et 2.000 millimètres) et le Poids en kilogrammes (la plupart des individus pesant entre 48 et 100 kilogrammes), les distances finales (et la classification) vont largement dépendre de la taille des individus (dans la mesure où l'étendue des valeurs est beaucoup plus importante).

Distances dans le module Classification Généralisée EM & k-Moyennes. La méthode de classification par les k-moyennes du module Classification Généralisée EM & k-Moyennes vous offre diverses options pour calculer les distances entre les observations et les centres de classe. En outre, vous pouvez utiliser des variables catégorielles pour la classification. Ceci est possible, comme nous l'avons décrit dans la rubrique Classification Généralisée (Panneau de Démarrage) - Onglet k-Moyennes, dans la mesure où les distances calculées dans ce module sont toujours des distances normalisées, c'est-à-dire que les valeurs varient dans l'intervalle 0 à 1. Plus précisément, pour toutes les variables continues, les distances se calculent sur les valeurs Xi transformées (réduites), de sorte que :

Min(Xj ) et Max(Xj ) représentent les valeurs minimum et maximum de la variable i. Pour les variables catégorielles, les distances ne peuvent prendre que les valeurs 0 (zéro) ou 1 (un) ; 0 si la classe à laquelle une observation particulière appartient est la même que celle qui se retrouve avec la plus forte fréquence dans la classe respective, et 1 si elle est différente de cette classe (voir aussi la rubrique Classification Généralisée EM et par les k-Moyennes - Principes Fondamentaux pour plus d'informations concernant le traitement des variables catégorielles dans la classification par les k-moyennes et dans la classification EM).

Remarque : dans ces calculs, nous "éliminons" les différences d'échelle (ordres de grandeur) des variables grâce à la transformation de normalisation illustrée précédemment. Pour revenir à notre petit exemple, si nous mesurons la Taille en millimètres et le Poids en kilogrammes, les deux variables vont "contribuer" de la même manière aux distances à partir desquelles la solution de la classification sera déterminée. Ainsi, nous pouvons nous attendre à trouver des résultats différents lorsque nous réalisons une classification par les k-moyennes dans le module Classification et dans le module Classification Généralisée EM & k-Moyennes.

Remarque relative à la classification EM. Comme indiqué dans la rubrique Principes Fondamentaux du module Classification Généralisée EM & k-Moyennes, l'algorithme EM ne repose pas sur les distances. En revanche, le programme va calculer des probabilités pour chaque observation appartenant à chacune des classes en fonction de la distribution choisie (par défaut, la distribution normale) ; l'objectif de l'algorithme de classification EM consiste alors à trouver les solutions de classification qui vont maximiser la probabilité globale des données, compte tenu de la solution finale de classification avec le nombre souhaité de classes. Par conséquent, dans la classification EM, toutes les différences d'échelle ou d'étendues dans les variables choisies pour les analyses, ne vont pas affecter les résultats.

Comment interpréter les différences dans les résultats. Compte tenu des différences dans la manière dont les différents modules calculent les distances pour la classification par les k-moyennes, on peut se demander : "quelle méthode est la bonne" ?  Comme toujours, il n'existe pas de réponse universelle. Si les différences dans les étendues de valeurs des variables ont un sens pour l'analyse, la normalisation réalisée dans le module Classification Généralisée EM & k-Moyennes va supprimer ces différences. Par exemple, si votre analyse porte sur des réponses à un ensemble de questions dans une enquête, chacune étant appréciée sur une échelle à 5 points, les différences dans l'étendue des valeurs pour les différentes questions peuvent avoir un sens. En revanche, dans l'exemple présenté plus haut, lorsque nous mesurons la Taille et le Poids (exprimées dans des unités de mesure totalement différentes), ces différences (relatives à l'ordre de grandeur des valeurs) n'apportent rien à l'analyse (dans la mesure où elles sont arbitraires, et entièrement imputables au choix de l'unité de mesure utilisée par le chercheur).  

Réduire les variables avant l'analyse dans le module Classifications. Si vous utilisez les fonctionnalités de classification par les k-moyennes du module Classifications, et que vous décidez que les différences dans l'ordre de grandeur des valeurs des différentes variables n'est pas important, il est conseillé de réduire les valeurs de ces variables. Vous pouvez utiliser la même formule que celle présentée ci-dessus dans le paragraphe Distances dans le module Classification Généralisée EM & k-Moyennes, c'est-à-dire réduire les variables de sorte que les valeurs de chacune soient ramenées dans l'intervalle de 0 à 1 ; vous pouvez également centrer-réduire vos données (voir la rubrique Centrer-Réduire (Standardisation)), qui sera alors suffisante pour le module Classification puisque seules les variables continues sont autorisées dans ce module (et il n'y a donc pas à se poser la question pour les variables catégorielles).

Notes et Informations Techniques : L'Algorithme des k-Moyennes

L'algorithme des k-moyennes est une méthode de classification permettant de répartir un ensemble d'objets en k groupes (classes) en fonction de la mesure des distances spécifiée. L'algorithme va réaliser un processus itératif en deux temps.

1. Calcul des centres de gravité des classes

a. Les centres de gravité initiaux sont déterminés en fonction de la méthode choisie par l'utilisateur. Il existe trois méthodes pour choisir les centres initiaux des classes : choisir N observations afin de maximiser la distance initiale, choisir N observations au hasard, et enfin, choisir les N premières observations. Ici, N représente k.

b. Après avoir affecté tous les objets au centre de gravité le plus proche, le programme va recalculer les nouveaux centres de gravité à partir de l'ensemble des membres appartenant aux classes correspondantes. Pour les variables continues, la valeur du centre de gravité est simplement égale à la moyenne des valeurs de tous les membres composant la classe. Pour les variables catégorielles, la valeur du centre de gravité est égale au mode de l'ensemble des membres constituant la classe.

2. Affectation de chaque objet au centre de gravité le plus proche

a. Le centre de gravité le plus proche est déterminé par la mesure des distances spécifiée par l'utilisateur. Les valeurs des variables continues sont toutes normalisées avant les calculs. Remarque : c représente un centre de gravité et x représente une observation.

i. Si la i-ième variable est catégorielle, la distance (xi - ci) est égale à 0 si le centre de gravité et l'observation prennent la même valeur ; dans les autres cas, la distance est égale à 1.

ii. Si la i-ième variable est continue, xi et ci sont tout d'abord normalisés en utilisant les valeurs minimum et maximum de cette variable.

Distance Euclidienne :

distance( x,  c ) = {åi (xi - ci)2 }½

Distance Euclidienne au carré :

distance( x,  c ) = åi (xi - ci)2

Distance du City-block (Manhattan) :

distance( x,  c ) = åi |xi - ci|

Distance de Chebychev :

distance( x,  c ) = Maximum|xi - ci|

b. Si toutes les observations appartiennent à la même classe que celle à laquelle elles appartenaient avant cette itération, le processus itératif prend fin. De la même manière, si le nombre d'itérations est égal à celui qui est spécifié par l'utilisateur, le processus itératif se termine. Les centres de gravité sont alors définitifs et vous pouvez accéder à la classification finale.

Pour plus d'informations, voir la rubrique Principes Fondamentaux.

Notes et Informations Techniques : L'Algorithme EM

L'algorithme EM est une méthode généraliste permettant de trouver l'estimation du maximum de vraisemblance des paramètres des distributions sous-jacentes à partir d'un jeu de données particulier. Toutes les variables sont supposées indépendantes entre elles et toutes les données sont issues de k distributions jointes. L'algorithme réalise ses itérations en deux temps.

1. L'algorithme M (la phase Maximization)

2. L'algorithme E (la phase Expectation)

ui représente la moyenne de la distribution i. représente la variance de la distribution i. représente le poids (probabilité) estimé de l'observation j appartenant à la classe i.  ci représente la classe i.  p(xj) représente la probabilité.

Si l'augmentation de la valeur de la vraisemblance est inférieure à la valeur que vous avez spécifiée, le processus itératif s'arrête et vous obtenez la classification finale. De même, si le nombre d'itérations est égal au nombre maximum d'itérations, le processus itératif prend fin et vous pouvez accéder à la classification finale.

Pour plus d'informations, voir aussi la rubrique Principes Fondamentaux.




Sélection Automatique du Nombre optimal de Classes à Partir des Données

Introduction. Cet exemple s'appuie sur un jeu de données classique reporté par Fisher (1936), qui est largement référencé dans la littérature relative à l'analyse discriminante. La section Exemples du module STATISTICA Analyse Discriminante présente également une analyse portant sur ce fichier de données. Le fichier de données contient la longueur et la largeur des sépales et des pétales pour trois types d'iris (Sétosa, Versicol et Virginic). L'objectif de l'analyse discriminante menée sur ces données consiste généralement à déterminer la meilleure manière de discriminer entre ces trois types d'iris, sur la base des quatre mesures de longueur/largeur des pétales/sépales. Dans cet exemple, nous allons montrer comment les méthodes du module Classification Généralisée EM et k-Moyennes de STATISTICA visant à déterminer le nombre optimal de classes dans les données, permettent d'identifier les différents types d'iris si nous ne savons pas a priori qu'il existe trois types d'iris.

En d'autres termes, imaginons que nous ne disposions que des mesures relatives aux 150 différents types de fleurs (iris), et que nous cherchions à savoir si ces fleurs peuvent se regrouper "naturellement" en un certain nombre de classes sur la base des mesures dont nous disposons. En termes plus généraux, imaginons que nous disposons d'un ensemble de mesures issues d'un grand échantillon d'observations, et que nous cherchions à savoir s'il existe des classes d'observations dans l'échantillon, et dans l'affirmative, combien. Vous pouvez être confronté(e) à ce type de question dans différents domaines, par exemple en recherche marketing où vous allez vous intéresser à des classes de profils ou de segments de marché ; dans les applications de contrôle qualité ou de production, vous pouvez vous intéresser à des classes ou à des typologies de défaillances ou de défauts survenant sur le produit final (par exemple, sur des plaques de silicium), etc...

Spécifier l'Analyse

Fichier de données. Le fichier de données utilisé dans cette analyse est le fichier Irisdat.sta. Vous trouverez ci-dessous un extrait de ce fichier. Ouvrez ce fichier de données à l'aide de la commande Ouvrir du menu Fichier ; ce fichier se situe dans le dossier /Exemples/Fichiers de données de STATISTICA.

Ouvrez le module Classification Généralisée EM & k-Moyennes à l'aide de la commande correspondante du menu Data Mining. Dans la boîte de dialogue Classification Généralisée (Panneau de Démarrage), sélectionnez les variables 1 à 4 comme variables continues : Lonsepal, Larsepal, Lonpetal et Larpetal. Remarque : nous ne sélectionnons pas la variable Typeiris. Comme indiqué dans l'introduction de cet exemple (voir le paragraphe Introduction, ci-dessus), nous allons supposer ici que nous ne disposons d'aucune connaissance préalable quant au "véritable" nombre de classes (types d'iris) de notre fichier de données.

Spécifier la validation croisée v-ensembles (v-fold). Cliquez sur l'onglet Validation, et cochez l'option Validation croisée, v-ensembles (v-fold). Comme indiqué dans la rubrique Principes Fondamentaux (voir aussi la description de l'onglet Validation), cette technique va répartir l'échantillon de 150 fleurs en v "ensembles" ou échantillons sélectionnés au hasard de même taille approximativement. STATISTICA va ensuite réaliser des classifications répétées pour chacun des v-1 échantillons (c'est-à-dire en gardant un échantillon de côté), et réaliser la classification (affecter les observations aux différentes classes) sur les observations de l'échantillon n'ayant pas été utilisées pour calculer la solution de classification respective. Cet échantillon sera traité comme un échantillon de test, sur lequel nous allons mesurer la distance moyenne des observations à leur centre de classe respectif (auquel elles auront été affectées). Nous calculons alors la moyenne de cet indicateur "d'erreur de classement" ou "coût" pour l'ensemble des v réplications de l'analyse. STATISTICA va continuer à réaliser ces calculs pour un nombre croissant de classes jusqu'à ce que, au cours des solutions successives de la classification (avec k et k+1 classes), le pourcentage de diminution de l'erreur de classement devienne inférieur à la valeur Plus faible diminution du %age, spécifiée dans l'onglet Validation ; à ce stade, c'est k qui sera retenu comme nombre optimal de classes dans les données.

Cliquez à présent sur le bouton OK pour démarrer les calculs. La validation croisée par v-ensembles peut nécessiter des ressources de calcul importantes, et il se peut que la boîte de dialogue des Résultats prenne un certain temps pour apparaître.

Étude des Résultats

Comme indiqué dans la rubrique Principes Fondamentaux, les résultats de votre analyse peuvent diverger de ceux produits ici en raison d'une affectation aléatoire initiale différente des observations (qui est fonction de l'amorce du générateur de nombres aléatoires) ; il vous suffit de spécifier la même amorce que dans l'illustration précédente pour le générateur de nombres aléatoires afin d'obtenir les mêmes résultats.

Dans notre cas, le programme a identifié 4 classes dans nos données.

Tracé de la séquence des coûts. Examinons tout d'abord le Tracé de la séquence des coûts. Comme indiqué dans la rubrique Principes Fondamentaux et dans la rubrique Résultats - onglet Base, ce tracé représente la fonction d'erreur (distance moyenne des observations dans les échantillons de test aux centres des classes auxquelles les observations ont été affectées) pour les différentes solutions de la classification.

Il apparaît que la fonction d'erreur diminue fortement entre la solution à 2 classes et la solution à 3 classes, puis elle se stabilise ensuite. En utilisant la même logique que celle que nous utilisons pour le Tracé des valeurs propres dans l'Analyse Factorielle (pour déterminer le nombre optimal de facteurs), nous pourrions ici choisir d'étudier la solution à 3 ou à 4 classes. Dans cet exemple, acceptons la solution à 4 classes proposées par le programme.

Tracé des moyennes (variables continues). Cliquez sur le bouton Tracé des moyennes (variables continues) afin de produire un tracé curviligne représentant les moyennes réduites des différentes classes pour l'ensemble des variables continues. Ces moyennes sont calculées de la manière suivante :

représente la moyenne transformée (réduite) de la variable continue i dans la classe j

 représente la moyenne arithmétique ("non réduite") de la variable continue i dans la classe

représentent les valeurs observées maximum et minimum de la variable continue i

En d'autres termes, les valeurs qui sont tracées représentent les moyennes réduites en fonction des étendues globales des valeurs observées des variables continues respectives.

Il apparaît que la structure des moyennes de la Classe 1 se singularise assez fortement de celle des autres classes. Vous pouvez à cet effet cliquer sur le bouton Distances entre les classes afin de vérifier que la distance entre la Classe 1 et toutes les autres est plus importante que la distance entre les classes 2, 3 et 4.

Autres résultats. Vous pouvez maintenant examiner en détail la structure des moyennes des variables de l'analyse ainsi que la distribution des observations affectées aux différentes classes. Ces résultats particulièrement intéressants de la classification par les k-Moyennes sont décrits en détail dans la rubrique Introduction du module Classifications et dans l'Exemple 2.

Comparaison de la solution finale de la classification avec les véritables types d'iris. Dans cet exemple, nous avons délibérément écarté la variable Typeiris, c'est-à-dire la connaissance préalable que nous avions quant au nombre de classes présentes dans notre échantillon. Il est intéressant de regarder si nous avons réussi à identifier les différents types d'iris à l'aide de notre analyse de classification. Dans d'autres applications, nous pourrions chercher à affecter des libellés explicites aux classes finales en réalisant d'autres analyses pour rapprocher l'affectation des observations aux différentes classes avec d'autres variables intéressantes. Dans notre cas, nous allons simplement produire un tableau croisé de l'affectation aux différentes classes en fonction de la variable Typeiris de notre fichier de données Irisdat.sta.

Dans la boîte de dialogue Résultats - onglet Base, cliquez sur le bouton Enregistrer les classifications & distances, puis sélectionnez la variable Typeiris comme variable à enregistrer avec les résultats de la classification (affectation finale des observations aux classes, distances aux centres de gravité des classes). Ci-dessous, un extrait de la feuille de données créée.

Cette feuille de données est automatiquement créée comme une feuille de données active pour les analyses suivantes (voir aussi l'option Données - Feuille de Données Active). Sélectionnez la commande Statistiques Élémentaires dans le menu Statistiques, sélectionnez la commande Tableaux et tris croisés afin d'accéder à la boîte de dialogue Tableaux et Tris Croisés, puis réalisez un tri croisé de la variable Typeiris selon la Classification finale.

Ci-dessus, le tableau de synthèse ainsi que les pourcentages (en ligne) d'observations de chacun des types d'iris (modalités de la variable Typeiris) affectés aux classes correspondantes. Comme nous pouvions nous y attendre, la Classe 1 (celle qui se singularise le plus des autres, avec la plus forte distance) est la plus différente. 100% des fleurs de type Setosa ont été correctement classées dans un groupe (classe) séparé. La Classe 3 et la Classe 4 ont apparemment réussi à identifier les fleurs de type Versicol et Virginic les plus aisément "classables", alors que la Classe 2 contient à la fois des fleurs de type Versicol et Virginic. Il apparaît que la distinction entre ces deux types de fleurs n'est pas simple, ce qui confirme les résultats obtenus dans la rubrique Analyse Discriminante - Exemple.

Synthèse

L'objectif de cet exemple consiste à montrer l'utilité du module Classification Généralisée EM & k-Moyennes pour déterminer automatiquement le nombre "optimal" de classes à partir des données, à l'aide des techniques de validation croisée v-ensembles (v-fold). Cette extension des méthodes traditionnelles de classification en fait une technique extrêmement puissante pour l'apprentissage non-supervisé et pour la reconnaissance de structure, qui sont des tâches courantes en Data Mining.




Illustration de la Classification EM sur un Fichier de Données Synthétique

Introduction. L'objectif de cet exemple consiste à illustrer la méthode de classification EM en créant un fichier de données possédant des propriétés connues (nombre de classes, types de distributions), puis à analyser ce fichier de données afin d'extraire ces propriétés à partir des données générées. D'une certaine manière, nous allons "injecter" dans les données une solution de classification particulière puis chercher à extraire cette solution en utilisant le module Classification Généralisée EM & k-Moyennes. Vous allez sans doute ainsi mieux comprendre le type d'information que la classification EM est en mesure de détecter dans les données. Pour plus d'informations concernant les calculs réalisés dans la classification par les k-moyennes, voir aussi les rubriques Principes Fondamentaux et Notes et Informations Techniques.

Création du fichier de données. Commençons par sélectionner la commande Nouveau dans le menu Fichier et créons un fichier de données constitué de 3000 observations et de 3 variables. Après l'apparition de la feuille de données vierge, sélectionnez la commande Formules de Transformation par Lot dans le menu Données afin de calculer les valeurs des trois variables comme suit :

Cliquez ensuite sur le bouton OK pour appliquer ces formules. Les résultats devraient avoir (approximativement) l'aspect suivant :

La première variable contient trois valeurs entières : 1 (pour les observations 1 à 1000), 2 (pour les observations 1001 à 2000) et 3 (pour les observations 2001 à 3000). La variable 2 contient des valeurs aléatoires normales de moyennes et écarts-types 5 et 1 (pour les observations 1 à 1000) environ, 10 et 2 (pour les observations 1001 à 2000) environ, et 15 et 3 (pour les observations 2001 à 3000) environ. La variable 3 contient des valeurs aléatoires de Poisson avec (approximativement) des valeurs de 5 (pour les observations 1 à 1000), 10 (pour les observations 1001 à 2000) et 15 (pour les observations 2001 à 3000) pour le paramètre.

Spécifier l'analyse. Ouvrez le module Classification Généralisée EM & k-Moyennes à l'aide de la commande respective du menu Data Mining. Dans la boîte de dialogue Classification Généralisée (Panneau de Démarrage), sélectionnez comme variables continues les variables Var2 et Var3. Sélectionnez ensuite EM comme Algorithme dans l'onglet Base, puis spécifiez 3 dans le champ Nombre de classes.

Dans l'onglet EM, cliquez sur le bouton Distribution des variables continues ; spécifiez la variable 2 (Var2) dans la liste des variables Normales, et la variable 3 dans la liste des variables de Poisson.

Cliquez à présent sur le bouton OK afin de démarrer l'analyse.  Après quelques instants, la boîte de dialogue des Résultats apparaît.

Étude des paramètres de la distribution pour chaque classe. Dans la boîte de dialogue des Résultats, sélectionnez l'onglet Avancé, puis cliquez sur le bouton Tracé des distributions.

Ci-dessus, les résultats des deux variables Var2 et Var3. L'estimation finale des paramètres des différentes distributions (associées à chacune des classes) sont reportées en titre de chacun des graphiques, qui spécifie les fonctions de répartition respectives représentées dans chaque graphique.  Comme vous pouvez le constater, les paramètres que nous avons "injecté" dans nos données en générant des nombres aléatoires issus de distributions connues (avec des paramètres différents pour chacune des trois classes) sont raisonnablement bien reproduits. En d'autres termes, la combinaison de 3 distributions normales et de 3 distributions de Poisson a pu être convenablement estimée à partir des données, et nous avons su extraire les classes que nous attendions. Cet exemple illustre le "mécanisme" de l'algorithme de classification EM, tel que nous l'avons présenté dans la rubrique Principes Fondamentaux.

Didacticiels

Vous pouvez visionner l'intégralité de la série de tutoriels Le Data Mining en 35 Leçons avec STATISTICA en remplissant le formulaire d'inscription. Vous serez alors notifié(e) automatiquement de la disponibilité des nouveaux épisodes et recevrez d'autres informations utiles.

StatSoft propose par ailleurs une série de didacticiels et présentations interactives décrivant pas-à-pas différentes opérations que vous pouvez réaliser à l'aide de STATISTICA. Si vous souhaitez voir aborder un thème particulier, merci de nous écrire.