News :: Erreur :: Visiteurs :: ClearType :: Imprimer ::

MÉTHODES NUMÉRIQUES | FRACTALES | SYSTÈMES LOGIQUES | CODES CORRECTEURS CRYPTOGRAPHIE | AUTOMATES | INFORMATIQUE QUANTIQUE

Dernière mise à jour de ce chapitre: 2017-01-31 10:13:20 | {oUUID 1.792}
Version:3.1 Révision 22 | Avancement: ~60%
vues depuis le 2012-01-01: 7'539

LISTE DES SUJETS TRAITÉS SUR CETTE PAGE

ANALYSE EN COMPOSANTES PRINCIPALES (A.C.P.)

L'analyse en composantes principales (A.C.P.) est une méthode mathématique d'analyse graphique de données qui consiste à rechercher les directions de l'espace qui représentent le mieux les corrélations entre n variables aléatoires (relations linéaires entre elles).

Simplement dit, une A.C.P. permet par exemple de trouver des similitudes de comportement d'achat entre les classes des données observées.

Même si l'A.C.P. est majoritairement utilisée pour visualiser des données, il ne faut pas oublier que c'est aussi un moyen:

- De décorréler ces données. Dans la nouvelle base, constituée des nouveaux axes, les points ont une corrélation nulle (nous le démontrerons).

- De classifier ces données en amas (clusters) corrélés (dans l'industrie c'est surtout cette possibilité qui est intéressante!).

Lorsque nous ne considérons que deux effets, il est usuel de caractériser leur effet conjoint via le coefficient de corrélation. Lorsque l'on se place en dimension deux, les points disponibles (l'échantillon de points tirés suivant la loi conjointe) peuvent être représentés dans un plan. Le résultat d'une A.C.P. dans ce plan consiste en la détermination des deux axes qui expliquent le mieux la dispersion des points disponibles.

Lorsqu'il y a plus de deux effets, par exemple trois effets, il y a trois coefficients de corrélations à prendre en compte. La question qui a donné naissance à l'A.C.P. est: comment avoir une intuition rapide des effets conjoints?

En dimension plus grande que deux, une A.C.P. va toujours déterminer les axes qui expliquent le mieux la dispersion du nuage des points disponibles.

L'objectif de l'A.C.P. est de décrire graphiquement un tableau de données d'individus avec leurs variables quantitatives de grande taille:

Afin de ne pas alourdir l'exposé de cette méthode et de permettre au lecteur de refaire complètement les calculs, nous travaillerons sur un exemple.

Considérons pour l'exemple une étude d'un botaniste qui a mesuré les dimensions de 15 fleurs d'iris (l'A.C.P. est aussi très utilisée en finance pour déterminer les éléments qui influence le plus la volatilité d'un portefeuille). Les trois variables  mesurées sont:

- : longueur du sépale

- : largeur du sépale

- : longueur du pétale

Les données sont les suivantes:

Pour nous un tel tableau de données sera tout simplement une matrice réelle à n lignes (les individus) et à p colonnes (les variables):

  (57.1)

Par la suite l'indice i correspondra à l'indice ligne et donc aux individus. Nous identifierons donc l'individu i avec le point ligne  qui sera considéré comme un point dans un espace affine (cf. chapitre de Calcul Vectoriel) de dimension p. L'indice j correspondra à l'indice colonne donc aux variables. Nous identifierons la variable j avec le vecteur-colonne:

  (57.2)

c'est donc un vecteur dans l'espace vectoriel de dimension n dans .

Nous nous placerons dans la suite suivant deux points de vue: soit nous prendrons le tableau de données comme n points dans un espace affine de dimension p, soit nous prendrons ce tableau comme p points d'un espace vectoriel de dimension n. Nous verrons qu'il y a des dualités entre ces deux points de vue.

L'outil mathématique que nous allons utiliser ici est l'algèbre linéaire (cf. chapitre d'Algèbre Linéaire), avec les notions de produit scalaire, de norme euclidienne et de distance euclidienne.

Afin de simplifier la présentation, nous allons dans un premier temps considérer que chaque individu, comme chaque variable, a la même importance, le même poids. Nous ne considérerons aussi que le cas de la distance euclidienne.

Nous allons commencer en centrant les données, c'est-à-dire mettre l'origine du système d'axes au centre de gravité du nuage de points. Ceci ne modifie pas l'aspect du nuage, mais permet d'avoir les coordonnées du point M égales aux coordonnées du vecteur  et donc de se placer dans l'espace vectoriel pour pouvoir y faire les calculs! Comme nous supposons dans toute la suite que les poids des individus sont identiques, nous prendrons donc  avec .

Nous considérons le repère orthonormé  dans la base canonique  de . Soit donc G le centre de gravité du nuage de points. Comme chaque variable ou chaque individu est supposé avoir le même poids, G a alors pour coordonnées dans le repère :

  (57.3)

avec:

  (57.4)

Nous avons alors pour l'instant sous forme graphique:

Figure: 57.1 - Points de mesures et centre de gravité

Nous appelons "matrice centrée" la matrice:

  (57.5)

Remarque: La matrice des données centrées contient les coordonnées centrées (que nous noterons ) des individus dans le repère . Nous nous placerons dans la suite toujours dans ce repère pour le nuage de points des individus et nous prendrons .

Pour notre exemple, nous avons:

  (57.6)

et pour la matrice centrée:

  (57.7)

et sous forme graphique:

Figure: 57.2 - Points de mesures centrés

Pour donner une importance identique à chaque variable afin que le type d'unités des mesures n'influence pas l'analyse, nous travaillerons avec les données centrées réduites (cf. chapitre de Statistiques). Pour cela, nous noterons d'abord:

  (57.8)

où le lecteur aura remarqué que nous avons pris la variance biaisée. Mais dans la réalité on prendraévidemment l'estimateur de la variance et donc on divisera par n - 1 plutôt que par n.

La variance d'échantillon de la variable centrée est donc égale à un facteur 1/n près à la norme de cette même variable mais centrée. La matrice des données centrées réduites (sans dimensions) est alors:

  (57.9)

Si nous notons  la matrice diagonale suivante:

  (57.10)

Nous avons alors:

  (57.11)

Nous définissons la "matrice des données centrées normées" par (nous parlons alors de "A.C.P. normée" ce qui n'est pas obligatoire mais simplifie l'interprétation):

  (57.12)

Soit encore (il s'agit simplement de l'erreur quadratique moyenne que nous avions introduite dans le chapitre de Statistiques):

  (57.13)

La terminologie vient bien évidemment du fait que la somme des carrées des composantes de chaque colonne de la matrice Z est de norme unitaire. En effet:

  (57.14)

Ce qui donne:

  (57.15)

Nous avons graphiquement:

Figure: 57.3 - Points de mesures centrés et réduits

Représenter le nuage de points des données centrées réduites ou centrées normées ne modifie rien à la forme de celui-ci. En effet, la différence entre les deux n'est qu'un changement d'échelle.

L'information intéressante pour les individus est la distance entre les points! En effet plus cette distance sera grande entre deux individus  et  plus les deux individus seront différents et mieux on pourra les caractériser. Mais il faut d'abord choisir une distance. Nous prendrons la distance euclidienne (cf. chapitre de Topologie):

  (57.16)

Les figures suivantes montrent les projections orthogonales dans l'espace de ce nuage de points respectivement dans les plans  et enfin dans  qui est la meilleure projection, appelée "plan factoriel" (ou parfois "diagramme des scores"), dans le sens où elle respecte le mieux les distances entre les individus (in extenso, elle déforme moins le nuage de points dans l'espace). L'objectif de l'A.C.P. est de déterminer ce meilleur plan et nous démontrerons comment.

Figure: 57.4 - Projection des points sur le plan horizontal du repère centré

Figure: 57.5 - Projection des points sur le plan vertical du repère centré

Figure: 57.6 - Projection des points sur le plan factoriel

Et la vue plane de chacune des projections:

Figure: 57.7 - Vue plane de chacune des projections

Avant de déterminer le plan factoriel, nous allons maintenant chercher à détecter les liens possibles entre les variables.

Nous rappelons (cf. chapitre de Statistiques) que la covariance entre deux variables  et  est donnée par:

  (57.17)

et que le coefficient de corrélation linéaire (cf. chapitre de Statistiques) est:

  (57.18)

Nous noterons par la suite:

   et       (57.19)

les matrices des variances-covariances et de corrélations carrées (toutes deux étant pour rappel des matrices carrées et symétriques) avec .

Nous voyons relativement facilement que la matrice des variances-covariances est au coefficient 1/n près, la matrice des produits scalaires canoniques des vecteurs de la matrice des données centrées (en d'autres termes, chaque composante de la matrice des variances-covariances est égale au produit scalaire des variables centrées). Nous en déduisons la relation suivante:

  (57.20)

La matrice des variances-covariances (puisque comme nous l'avons vu dans le chapitre de Statistiques, la diagonale contient les variances... pour rappel!) est un outil connu d'interprétation sur ce site. Par contre, ce qui est nouveau et va nous être très utile pour déterminer le plan factoriel est la matrice des corrélations linéaires qui peut aussi être écrite sous la forme suivante:

  (57.21)

Ce qui donne pour notre exemple où nous avons trois variables (très facile à calculer avec un tableur comme Microsoft Excel), la matrice carrée suivante (que les données soient centrées ou non les composantes de la matrice sont identiques):

  (57.22)

Pour continuer, toujours dans le but de déterminer le plan factoriel, définissons le concept d'inertie d'un nuage de points.

Définition: Nous appelons "inertie d'un nuage de points" la quantité:

  (57.23)

où G est le centre de gravité du nuage de points et  un point de  de coordonnées .

Ensuite, démontrons que nous avons la relation suivante:

  (57.24)

Démonstration:

  (57.25)

C.Q.F.D

Nous allons dans toute la suite travailler avec les données centrées normées, in extenso avec la matrice Z. Les points  auront donc ici comme coordonnées .

Le problème est maintenant de trouver le meilleur espace affine de dimension p dans le sens où il respecte au mieux les distances entre les points. Pour cela, nous allons rechercher la meilleure droite vectorielle  qui est parfaitement déterminée par le vecteur . Appelons  la projection orthogonale de  sur la droite . Alors notre problème est de trouver la droite (in extenso le vecteur ) qui fasse que la somme des carrés des distances entre les points  soit maximale. Nous écrirons le problème sous la forme d'un problème de programmation quadratique:

  (57.26)

Or ici, nous avons:

  (57.27)

En effet, le centre de gravité du nuage de points projetés est aussi l'origine. Par suite, notre problème peut s'écrire:

  (57.28)

Lui-même équivalant donc à:

  (57.29)

Résolvons donc ce problème:

Tout d'abord, puisque  est la projection orthogonale du point  sur  nous avons  pour tout i avec . Par suite les coordonnées des points  sur la droite  sont:

  (57.30)

Par suite, nous avons:

  (57.31)

Ici nous cherchons le vecteur unitaire . La matrice Z nous est parfaitement connue. Or, nous avons:

  (57.32)

La matrice de corrélation R est symétrique donc, selon le théorème spectral vu dans le chapitre d'Algèbre Linéaire, elle est diagonalisable dans une base orthonormée de vecteurs propres. Ainsi, nous avions démontré dans le théorème spectral que:

  (57.33)

est diagonale (libre à nous d'en choisir le contenu) si R est symétrique et S orthogonale (qui est donc dans notre exemple une matrice carrée !). Alors nous en déduisons la relation suivante qu'il est d'usage d'appeler la "décomposition spectrale":

  (57.34)

et comme S avait été démontrée comme étant orthogonale (et qu'il existe une famille de vecteurs propres pour cela!), nous avons (cf. chapitre d'Algèbre Linéaire):

  (57.35)

Donc:

  (57.36)

où nous choisissons pour la matrice diagonale des valeurs propres rangées en ordre décroissant: .

Nous avons donc:

  (57.37)

Dans la littérature, cette somme est souvent notée de la manière suivante (très souvent mentionée dans les logiciels statistiques sous le nom de "décomposition spectrale"):

  (57.38)

Mais S étant orthogonale, nous avons par conséquent:

  (57.39)

et ceci provient du fait que la matrice orthogonale est comme nous l'avions démontré dans le chapitre d'Algèbre Linéaire une isométrie (elle conserve donc la norme!).

Comme les valeurs propres sont dans l'ordre décroissant, nous écrirons:

  (57.40)

Or le terme entre parenthèses est strictement inférieur ou égal à1 de par l'implication précédente. Donc:

  (57.41)

Soit:

  (57.42)

Or rappelons que notre objectif est de maximiser cette inégalité. En d'autres termes de chercher  tel que l'égalité soit respectée. Nous voyons assez vite qu'il en sera ainsi si et que les autres termes soient nuls. Ainsi, une solution triviale de notre problème de maximisation est donc:

  (57.43)

soit puisque:

    (57.44)

qui est alors le premier vecteur propre de R (puisque R se diagonalise dans cette base) associé à la plus grande valeur propre . D'où le fait que cette solution soit souvent notée sous la forme:

    (57.45)

toujours avec  (il est donc relativement aisé de déterminer S avec des logiciels lorsque R et sont connus).

Une fois que l'on a trouvé la première droite vectorielle, nous cherchons une deuxième droite dans le sous-espace vectoriel orthogonal à la droite vectorielle qui maximise l'inertie du nuage de points projetés. Nous démontrons, et devinons, que la solution est donnée par la droite vectorielle dirigée par le vecteur propre associé à la deuxième valeur propre de la matrice de corrélation et ainsi de suite...

Ainsi, nous obtenons une nouvelle base  dont un des plans constitue le plan factoriel. Cependant, il nous faut connaître les composantes de Z dans cette base. Comme cette base a été construite sous la condition que R y est diagonalisable via la matrice S alors cette dernière matrice est l'application linéaire qui va nous permettre d'exprimer Z dans la base  via la relation:

  (57.46)

Ainsi, dans notre exemple les trois valeurs propres de la matrice de corrélation R sont (cf. chapitre d'Algèbre Linéaire):

  (57.47)

et donc:

  (57.48)

En ayant les trois valeurs propres, pour déterminer les trois vecteurs propres qui forment la base principale, il nous faut donc résoudre le système de trois équations à trois inconnues (cf. chapitre Algèbre Linéaire) suivant pour chaque valeur propre:

  (57.50)

Ce qui donne donc (nous nous passerons de ce calcul élémentaire qui peut être fait à la main ou avec un simple tableur) la matrice des vecteurs propres:

  (57.51)

qui vérifie donc:

  (57.52)

ou autrement écrit (suite à la remarque d'un lecteur qui a voulu vérifier les calculs et qui s'est fait piéger):

  (57.53)

Nous avons alors comme coordonnées des points  dans la base en utilisant:

  (57.54)

la matrice suivante:

  (57.55)

Les coordonnées des projections du nuage de points dans le meilleur plan défini par les vecteurs  sont donc les deux premières colonnes de la matrice précédente (correspondant donc à la longueur du sépale et la largeur du sépale).

Effectivement, nous voyons immédiatement que ce sont ces deux colonnes qui maximiseront la somme des normes dans le plan donné:

Figure: 57.8 - Plan factoriel déjà montré plus haut...

Un logiciel comme Minitab 15.1 (référence dans l'industrie de la gestion de la qualité) donne les informations suivantes pour les valeurs propres (info pas très utile sous forme graphique... à mon avis):

Figure: 57.9 - Valeurs propres pour l'ACP données par Minitab ("scree plot")

et le plan factoriel suivant (resterait à savoir comment les valeurs sont calculées car elles ne sont pas identiques à celles que nous avons obtenues ici... mais la forme graphique est bien juste et c'est le principal!):

Figure: 57.10 - Plan factoriel donné par Minitab

Pour clore ce sujet, signalons que de nombreux logiciels utilisent le fait que les vecteurs sont unitaires pour faire le produit scalaire qui correspond alors dans ce cas particulier simplement au cosinus entre les différents vecteurs tel que:

  (57.56)

et comme nous avons démontré plus haut que:

  (57.57)

Il vient alors:

  (57.58)

et comme dans notre exemple, nous avons 3 vecteurs , il y a donc 3 produits scalaires possibles si nous omettons les produits scalaires des vecteurs avec eux-mêmes. Donc la matrice:

  (57.59)

contient aussi les angles entre les vecteurs .

Enfin, signalons que l'A.C.P. étant sensible aux données aberrantes, il vaut mieux parfois transformer les valeurs du tableau d'origine en leurs rangs respectifs (cf. chapitre de Statistiques) et appliquer exactement le même algorithme. Nous parlons alors d'une "A.C.P. de rangs".

ANALYSE FACTORIELLE DES CORRESPONDANCES (A.F.C.)

L'analyse factorielle des correspondances, en abrégé A.F.C., est une méthode statistique d'analyse des données (très utilisée en biostatistique et dans l'analyse de sondages). La technique de l'A.F.C. est essentiellement utilisée pour de grands tableaux de données toutes comparables entre elles (si possible exprimées toutes dans la même unité, comme une monnaie, une dimension, une fréquence ou toute autre grandeur mesurable). Elle peut en particulier permettre d'étudier des tableaux de contingence (ou tableau croisé de co-occurrence) et de décrire la liaison entre deux variables qualitatives. Elle sert à déterminer et à hiérarchiser toutes les dépendances entre les lignes et les colonnes du tableau.

Le cas de plus de deux variables qualitatives est l'analyse de correspondance multiples (A.C.M.)

Attaquons la théorie directement avec un exemple. Pour cela nous considérons le tableau (avec deux variables qualitatives) suivant des superficies des types de peuplements d'arbres en Picardie en 1984 en hectares:

Les spécialistes du domaine appellent parfois les totaux des lignes et des colonnes respectivement les "marges de ligne" et "marges de colonne". Lorsque l'ensemble du tableau est mis sous forme de pourcentage, par rapport au total des totaux, on parle de "représentation en fréquences conjointes":

Nous souhaitons analyser s'il existe les degrés de ressemblance et de différence entre les variables. Remarquons, que nous ne cherchons pas à comparer l'égalité des moyennes ou des variances donc les outils statistiques vus dans le chapitre du même nom ne sont pas adaptés à ce genre d'analyse.

Si nous choisissons la distance euclidienne:

  (57.60)

sur les données brutes pour mesurer ces différences entre départements, nous obtenons les écarts suivants:

  (57.61)

et ainsi de suite pour les autres régions. Nous obtenons alors:

  (57.62)

Nous voyons en regardant le tableau et avant tout calcul que les départements de l'Aisne et l'Oise se ressemblent alors que le département de la Somme se diffère nettement. Les distances obtenues mettent en évidence cette observation.

Mais dans le tableau ci-dessus les profils de l'Oise et de la Somme, avec une forêt mixte très faible, sont pourtant très proches en proportion.

Dans ce contexte, nous voyons que la distance euclidienne transcrit les différences de masse entre les départements. En d'autres termes, l'Aisne et l'Oise se ressemblent car leurs superficies sont proches. Pour éliminer l'artefact lié aux ordres de grandeur, il nous faut transformer les données en pourcentage (pourcentages des régions). Nous obtenons alors:

où les spécialistes du domaine appellent parfois la colonne en pourcents des régions "profil marginal des lignes" ou "masse" (et respectivement quand ils indiquent la ligne des pourcents des arbres).

Si nous choisissons la distance euclidienne sur les proportions (données relatives), nous obtenons:

  (57.63)

soit:

  (57.64)

Cette fois, l'Oise et la Somme apparaissent bien comme se ressemblant le plus avec leurs forêts. Nous voyons que travailler avec les données relatives semble donc plus pertinent dans ce cas!

Maintenant, nous allons emprunter une idée aux économistes qui, lorsqu'ils ont des tableaux du même genre que le précédent, calculent ce qu'ils appellent "l'index" ou "élasticité" (souvent appelé "indice de spécificité" en statistiques et qui est donné par le rapports entre la fréquence conjointe et la fréquence marginale:

  (57.65)

Voici un exemple obtenu avec les tableaux croisés dynamiques de Microsoft Excel 11.8346
qui inclut la fonction Index. D'abord le tableau de départ:

Figure: 57.11 - Tableau croisé dynamique Microsoft Excel 11.8346 de départ

et en activant la fonction Index:

Figure: 57.12 - Tableau croisé dynamique Microsoft Excel 11.8346 avec la fonction Index

Pour voir d'où viennent ces valeurs, regardons par exemple l'article Desk dans la région Alberta. Il a un rendement (fréquence conjointe) de:

  (57.66)

par rapport à toutes les régions ce qui est au-dessus de la valeur de 33.33% qu'aurait comme rendement cet article toutes régions confondues s'il n'y avait pas de préférences de région!

La région Alberta a elle un rendement (fréquence marginale) de:

  (57.67)

par rapport à toutes les régions ce qui est en-dessous des 33.33% de rendement qu'elle aurait s'il n'y avait pas de préférences de région. Ainsi, ce tableau d'index permet de savoir si les différences sont qualitativement significatives!!

Le rapport donne donc:

  (57.68)

ce qui montre un fort décalage entre la valeur obtenue et la valeur que nous aurions si les proportions étaient respectées (surreprésentation de 283%).

C'est donc une sorte de calcul de conformité: si le rapport valait 1, c'est que le rendement régional des ventes de cet article particulier serait conforme par rapport à toutes les ventes de cette région relativement à un marché national. Il n'y aurait alors pas d'anomalies. Voyons cela par exemple pour nos arbres où nous avions les effectifs observés:

et pour lequel nous obtenons le tableau croisé dynamique des index effectifs observés suivant dans Microsoft Excel 11.8346 :

Figure: 57.13 - Tableau croisé dynamique Microsoft Excel 11.8346 avec la fonction Index

et nous voyons encore clairement à l'aide de ce tableau que ce sont l'Oise et la Somme qui se ressemblent le plus!

Avant de continuer, nous pourrions nous poser la question extrêmement importante suivante: Quels seraient les effectifs théoriques qui auraient été obtenus si les proportions des arbres dans les régions étaient rigoureusement équivalentes à la proportion d'ensemble (soit de telle manière à ce que les index soient tous unitaires)?

Eh bien simplement en faisant le calcul suivant (il s'agit simplement d'une règle de trois calculée dans chaque cellule) dont il faut bien - si possible - comprendre le sens sans l'appliquer bêtement:

Et nous obtenons avec ces nouvelles valeurs le tableau des index des effectifs théoriques suivant dans Microsoft Excel 11.8346:

Figure: 57.14 - Tableau croisé dynamique Microsoft Excel  11.8346 de l'index des effectifs théoriques

ce qui montre que les proportions sont maintenant respectées! Parenthèse fermée (mais sur laquelle nous reviendrons un peu plus loin)!

Eh bien quand nous voulons faire de l'analyse factorielle des correspondances, notre relation:

  (57.69)

devient alors:

  (57.70)

soit:

  (57.71)

Cette fois encore, l'Oise et la Somme apparaissent bien comme se ressemblant le plus.

La distance ci-dessus se nomme la "métrique du Khi-deux" car elle ressemble (mais c'est tout!) à la distance utilisée dans le test d'ajustement du même nom (cf. chapitre de Statistiques) mais ici, elle permet seulement de mettre en place une hiérarchie dans le cadre d'un tableau de contingences et d'observer les variables similaires de manière plus aisée!!

TEST D'INDÉPENDANCE DU KHI-2

Pendant l'introduction de la méthode précédente permettant de comparer des effectifs (valeurs) et détecter lesquels étaient les plus proches, nous avons donné le tableau des effectifs observés:

et nous avons montré comment trouver le tableau des effectifs théoriques (arrondis à l'entier le plus proche) dans les cas où les proportions auraient dû éventuellement être respectées:

La construction du dernier tableau ci-dessus présuppose par exemple que les trois régions sont dans des conditions identiques pour tout ce qui concerne la croissance et la multiplication des arbres et que le nombre d'arbres est en relation de cause à effet directe!!!! avec les régions et qu'il n'y a pas d'autres causes intermédiaires... ce qui est une hypothèse forte!

Mais sous cette hypothèse, supposons que nous souhaiterions savoir si les différences observées entre le nombre d'arbres et les régions sont statistiquement significatives ou purement aléatoires à cause de l'échantillon expérimental? En d'autres termes, nous voulons savoir si le nombre d'arbres dépend réellement des régions dans lesquelles ils poussent ou si ces valeurs ne sont que dues au hasard de l'échantillon? Raison pour laquelle ce test s'appelle le "test d'indépendance du Khi-deux".

Pour répondre à cette question il faut d'abord une référence. Et cette référence est justement l'hypothèse de lien causal direct (proportions respectées) que nous avons donnée juste précédemment.

Si nous considérons que chaque case du tableau des effectifs observés correspond à l'issue d'une variable aléatoire de loi inconnue et que chaque case du tableau théorique (du moins la classe d'effectifs) est considérée comme issue d'une variable aléatoire suivant une loi binomiale (et asymptotique d'une loi Normale) alors nous pouvons utiliser le test d'ajustement du Khi-deux:

  (57.72)

(cf. chapitre de Statistiques) pour avoir une bonne idée (mais qui reste quand même très approximative au vu des hypothèses!) si les différences entre les valeurs des effectifs observés sont dues au hasard ou sont réelles. Or, si D est petit, la probabilité que ce soit dû au hasard est grande mais si D est grand alors nous avons une différence réelle (donc nous utilisons le test d'ajustement du Khi-deux mais dans le sens inverse!).

Reste à déterminer le nombre de degrés de liberté de la loi  que suit cette somme dans ce type de configuration!

Dans le cas particulier (mais facilement généralisable par récurrence) d'une table à deux entrées avec deux variables catégorisées X avec l niveaux et Y avec c niveaux nous aurons respectivement l lignes et c colonnes.

Ainsi, la table aura bien évidemment  cellules. Dans la table des effectifs théoriques (dont chaque cellule est considérée comme une variable aléatoire) chaque cellule sera entièrement déterminée par la somme des autres de telle sorte que le nombre de degrés de liberté sera alors en toute logique comme nous l'avons vu dans le chapitre de Statistiques:

  (57.73)

Ainsi, en prenant notre exemple des forêts, c'est le total des totaux de 272'650 qui nous permet d'écrire cette dernière relation et ainsi de déterminer la valeur d'une cellule éventuellement vide, toutes les autres étant données!

Un test du Khi-deux sur ce type de table teste l'hypothèse d'indépendance contre l'hypothèse alternative de dépendance. Sous l'hypothèse d'indépendance nous estimons qu'il y a besoin de seulement:

  (57.74)

valeurs sur les N pour pouvoir en déterminer la totalité (en supposant implicitement connues les sommes par ligne et par colonne).

Ainsi, si vous avez une table de 2 lignes par 2 colonnes, il vous suffit si vous connaissez les totaux des lignes et des colonnes, d'avoir 2 valeurs (soit (2-1)+(2-1)) pour déterminer les 2 manquantes. Le raisonnement s'applique aussi pour une table de 3 lignes par 3 colonnes où il vous suffit d'avoir au moins 4 valeurs (soit (3-1)+(3-1)) pour déterminer les 5 manquantes.

Les degrés de liberté pour le Khi-deux sont alors:

  (57.75)

C'est cette relation qui nous dit (trivialement!) que si dans un tableau de 2 lignes par 2 colonnes comprenant donc 4 cellules (totaux des lignes et colonnes étant aussi connus!) qu'étant donnée une seule des valeurs (ddl valant 1), nous pouvons déterminer les 3 autres valeurs manquantes.

Voici donc une définition possible du nombre de degrés de liberté: C'est le nombre maximum de valeurs du modèle telles qu'aucune d'entre elles n'est calculable à partir des autres.

De même, pour un tableau de 3 lignes par 3 colonnes comprenant 9 cellules comme c'est le cas de notre exemple dans ce chapitre avec les forêts, la connaissance de 4 cellules seules permet grâce aux totaux en ligne et colonnes de déterminer les 5 autres qui seraient éventuellement non connues.

D'où la relation dans le cadre de l'application du Khi-deux de la relation finale:

  (57.76)

en faisant usage des notations utilisées dans l'industrie. Le terme:

  (57.77)

est souvent appelé "carré du résidu standardisé". Et le rapport:

  (57.78)

est souvent appelé "contribution au Khi-deux d'indépendance".

Dans le cadre de notre exemple, nous avons:

  (57.79)

et la p-value de cette valeur avec la loi du Khi-deux à quatre degrés de liberté:

  (57.80)

est tellement proche de zéro (non statistiquement significatif) que nous n'avons aucune chance de nous tromper en affirmant que les différences observées dans le tableau sont statistiquement significatives entre les 3 forêts et donc qu'il y a très probablement indépendance.

Nous obtenons un résultat similaire entre l'Oise et la Somme alors qu'avec l'AFC nous avons vu que ces deux forêts se ressemblaient beaucoup.

V DE CRAMER

Nous avons vu plus haut que le test d'indépendance du Khi-deux peut être utilisé pour mesurer le degré d'association de deux variables catégorielles dans une table de contingences de l lignes et c colonnes:

  (57.81)

et que cette distance suit une loi du Khi-deux à (l-1)(c-1) degrés de liberté. Nous allons démontrer de façon intuitive que la valeur maximum de la distance D est:

  (57.82)

et que cette valeur maximale n'est atteinte que si et seulement si chaque ligne ou chaque colonne contient une et une seule valeur non nulle. Sous cette dernière condition, nous pouvons toujours réarranger le tableau de contingences de façon à avoir tous les termes non nuls sur la diagonale du tableau.

Évidemment, si le tableau n'est pas carré comme ci-dessous:

le cas qui maximise D impose donc des termes en diagonale sur la dimension la plus petite en ligne ou colonne notée traditionnellement q. Dans le cas présent, nous avons donc:

  (57.83)

Dans ce cas extrême et bien évidemment théorique, les lignes ou colonnes qui n'ont que des zéros peuvent être mises de côté et dès lors tout tableau peut se résumer à:

Évidemment, faire abstraction des lignes ou colonnes qui n'ont que des valeurs nulles suppose que dans la distance D du Khi-deux nous posions que:

  (57.84)

ce qui est tout à fait discutable... Pour la suite, nous allons avoir besoin des relations suivantes:

  (57.85)

et:

  (57.86)

Dès lors, il vient:

  (57.87)

Nous définissons alors la valeur suivante:

  (57.88)

comme étant le "coefficient V de Cramer" (la majorité des logiciels donnent cependant la valeur de V au carré). Ce dernier est tel qu'il ne dépasse jamais 1 et permet une interprétation plus intuitive du degré d'association dans un tableau de contingences.

Dans le cas où le tableau est de dimension 2 en ligne et 2 en colonne, la relation précédente se réduit alors immédiatement à:

  (57.89)

Relation qu'il est de tradition de noter dans ce cas particulier sous la forme suivante:

  (57.90)

et de nommer "phi de Cramer".

Exemple:

Considérons le tableau suivant (même si les conditions ne sont pas satisfaites pour un test d'indépendance du Khi-deux):

avec les effectifs théoriques:

Nous avons alors:

  (57.91)

Et à un niveau de 95%, nous obtenons avec la version française de Microsoft Excel 14.0.6123:

  (57.92)

ou avec la p-value:

=1-LOI.KHIDEUX.N(4;1;1)=0.045   (57.93)

Il vient alors immédiatement:

  (57.94)

Nous sommes un peu limite ici... étant donné que la p-value est toute proche du seuil de 0.05. Cependant, prendre une décision dans le cas présent alors que de toute façon les effectifs sont si faibles reviendrait à conclure n'importe quoi et ce d'autant plus que l'outil est construit sur une cumulation d'approximations.

TEST EXACT DE FISHER

Lorsque les effectifs dans la table de contingences sont trop petits ou que les valeurs sont vraiment trop irrégulières, l'utilisation du Khi-deux (test de Pearson) n'est plus possible car les conditions d'application ne sont plus valables. Nous allons voir que le test exact de Fisher peut être formalisé analytiquement dans des tableaux de contingences de 2 lignes par 2 colonnes (la majorité des logiciels de statistiques ne gèrent que ce scénario particulier pour le test exact de Fisher) sinon quoi il faut recourir à des simulations de Monte-Carlo.

Le principe du "test exact de Fisher"  (utilisable aussi bien en unilatéral qu'en bilatéral même si ce dernier est largement plus courant dans la pratique), basé donc sur la fréquence de croisement, est de déterminer si la configuration observée dans le tableau de contingence est une situation extrême par rapport aux situations possibles. Comme nous allons le démontrer, ce test a pour propriété particulière que n'importe quelle case du tableau peut servir de référence pour le test car les distributions sous-jacentes (lois marginales) de probabilité sont équivalentes.

Pour étudier ce test, comme souvent dans ce chapitre, passons directement par un exemple. Considérons le tableau de contingence suivant (qui maintenant nous est connu...):

qui est donc en réalité pas adapté pour un test d'indépendance du Khi-deux puisque le contenu des cellules est inférieur à 10 unités et le nombre de degrés de liberté serait lui égal à l'unité.

Ce même tableau en pourcentages donnera (même si c'est inutile pour le test que nous étudions il arrive souvent que les logiciels de statistiques communiquent ces valeurs):

Les effectifs théoriques sont donnés par (même si c'est aussi inutile pour le test que nous étudions il arrive souvent que les logiciels de statistiques communiquent ces valeurs):

La question que nous allons commencer par nous poser est la suivante: connaissant les totaux pour chaque ligne et chaque colonne, quelle est la probabilité d'avoir les valeurs présentes actuellement dans chacune des cases!

Cette question peut être formalisée si nous changeons le tableau sous la forme générique suivante:

Explicitement et relativement à notre exemple en adoptant la notation d'usage de la loi hypergéométrique, la question est de savoir quelle était la probabilité d'avoir 8 (a=k) projets parmi les 18 (n) dont les délais ont été respectés par des chefs de projets certifiés sachant qu'il y a 9 projets (m) au total dont les délais ont été respectés et 12 projets (p) au total gérés par des chefs de projets certifiés.

Nous avons alors vu dans le chapitre de Statistiques que dans ce cas il s'agit d'un tirage exhaustif, il faut donc utiliser la loi hypergéométrique donnée par:

  (57.95)

Soit avec la version française de Microsoft Excel 11.8346:

=LOI.HYPERGEOMETRIQUE(k;p;m;n)
=LOI.HYPERGEOMETRIQUE(8;12;9;18)=0.06108597

où pour rappel (cf. chapitre de Statistiques), k est le nombre de succès dans l'échantillon, p est la taille de l'échantillon, m le nombre de succès dans la population et n la taille de la population.

Au fait les probabilités sont toutes égales quelle que soit la cellule choisie du tableau de contingences!! Cela peut se vérifier numériquement pour les sceptiques avec à nouveau un tableur comme la version française de Microsoft Excel 14.0.6123 en créant la structure suivante:

et donc à chaque fois que le lecteur appuiera sur la touche F9 de son clavier il pourra constater que toutes les probabilités sont toujours égales.

Cela peut se vérifier aussi formellement en choisissant une cellule du tableau et en écrivant:

  (57.96)

et pour une autre cellule de la même colonne, nous aurons:

  (57.97)

et donc:

  (57.98)

et ainsi de suite...

Bref, ceci étant dit, nous avons donc dans la case supérieure gauche la valeur 8 alors que l'effectif théorique est de 6. La première chose à laquelle nous pouvons répondre est de savoir si cette valeur de 8 est anormalement grande ou pas par rapport à l'effectif théorique. Pour cela, nous calculons par exemple en unilatéral la probabilité cumulée d'être inférieur ou égal à 8. Nous avons alors avec la version française de Microsoft Excel 14.0.6123 et ultérieur (le dernier paramètre à 1 de la fonction permettant d'indiquer au logiciel que nous voulons la probabilité cumulée):

=LOI.HYPERGEOMETRIQUE.N(8;12;9;18;1)=0.995475113

Il apparaît donc avec un seuil de 5% en unilatéral que cette valeur est anormalement grande. Nous sommes donc dans une situation extrême.

Par contre, même si les probabilités sont égales pour toutes les cases, la probabilité cumulée elle ne l'est pas! Ainsi, nous avons par exemple pour la valeur de la case inférieure gauche (afin de vérifier si elle est anormalement petite par rapport à l'effectif théorique de 6):

=LOI.HYPERGEOMETRIQUE.N(4;12;9;18;1)=0.06561086

Donc c'est une valeur qui n'est pas anormalement petite. Cependant, nous souhaiterions avoir un test permettant de conclure si l'ensemble du tableau est dans une configuration extrême ou pas. Or, en faisant le calcul case par case, nous n'allons pas arriver à grand-chose...

L'idée consiste alors à construire tous les tableaux dont les fréquences marginales sont de 9;9 et 12;6 et de calculer la probabilité d'une case donnée (l'avantage de cette technique est que la conclusion sera la même quelle que soit la case prise pour référence du calcul):

Soit pour résumer avec les valeurs de k (correspondantes à la cellule supérieure gauche):

Comme dans la colonne du tableau original avec laquelle nous venons de travailler la plus petite valeur est 4 et la plus grande 8, nous allons prendre les probabilités de queues pour savoir quelle est la p-value d'être au-dessus ou égal à 8 et en-dessous ou égal 4 (donc il s'agit d'un test en bilatéral). Nous avons alors:

Donc la p-value est de 13.12%. Nous ne pouvons dès lors pas dire que notre tableau d'origine est dans une configuration extrême si par exemple nous choisissons un seuil de 5%. De nombreux logiciels ne donnent que la p-value.

Enfin, pour clore, le lecteur pourra vérifier qu'il tombera sur le même résultat quelle que soit la case qu'il choisit comme référence.

Indiquons que le test exact de Fisher peut bien évidemment être utilisé en machine learning pour mesurer la performance de classification binaire!

KAPPA D'AGRÉMENT DE COHEN

Si nos jugements reflètent notre pensée, ils sont plus rarement en accord avec ceux d'autrui.

Cette variabilité interindividuelle bénéfique pour l'Homme, est cependant pénalisante dans de nombreuses disciplines scientifiques,  où il est souvent nécessaire d'évaluer et d'améliorer l'accord entre des informations de même nature appliquées au même objet dans une exigence de contrôle de la qualité ou d'assurance qualité ou encore d'analyse sensorielle.

Le test non paramétrique kappa de Cohen  permet par exemple de chiffrer l'accord binaire (dichotomique) entre deux ou plusieurs observateurs ou techniciens lorsque les jugements sont qualitatifs.

Prenons le cas dans le domaine médical où deux ou plusieurs praticiens examinant le même patient proposent des diagnostics différents ou des décisions thérapeutiques différentes. En l'absence d'une référence, cette multiplication des avis n'apporte pas la sécurité attendue d'un parfait accord diagnostique ou thérapeutique pour le médecin traitant et le patient. Il est donc important que l'accord dans une équipe de travail ou entre plusieurs équipes soit le meilleur possible pour garantir la qualité et la continuité des soins.

Une solution consiste ici à réaliser une séance de "mise en concordance" entre les médecins pour estimer leur taux d'accord par le coefficient kappa et d'étudier leurs désaccords pour y remédier.

Plus généralement, le test statistique Kappa est utilisé dans les études de reproductibilité qui nécessitent d'estimer l'agrément entre deux ou plusieurs cotations lorsqu'on étudie une variable discontinue.

Le "Kappa de Cohen" est un indicateur empirique permettant de comparer le degré de concordance entre deux observateurs (donneurs d'opinion). C'est un système basé sur l'analyse d'une table de contingences de données appariées (puisque les deux observateurs analysent les mêmes objets).

Pour illustrer le principe, considérons le cas très important où deux responsables qualité ont analysé 11 pièces pour les rejeter ou les accepter. Ils ont obtenu:

Les fréquences théoriques étant obtenues par une règle de trois (même calcul de règle de trois que pour le test d'indépendance du Khi-deux et le test exact de Fisher vus plus haut):

Le Kappa de Cohen est défini par le rapport:

  (57.99)

Cette valeur de 0.441 indique un accord modéré entre les deux responsables.

Si plutôt que d'avoir des fréquences, nous travaillons en pourcents (proportions) du total, le Kappa s'écrit alors:

  (57.100)

Ce qui donnera avec notre exemple:

  (57.101)

Ce qu'il est aussi d'usage d'écrire de manière plus condensée sous la forme:

  (57.102)

Avec:

  (57.103)

où +1 correspond à un accord parfait et -1 à un désaccord parfait. Évidemment, pour qu'il y ait accord parfait, il faut que les cellules (Rejeté, Rejeté) et (Accepté, Accepté) soient égales et que les autres soient nulles.

L'interprétation suivante est d'usage pour la partie positive (la négative ayant aucun intérêt):

TEST DE MCNEMAR

Le test de McNemar pourrait très bien se calculer en même temps que le Kappa de Cohen (le premier étant un test d'hypothèse statistiques et le deuxième un uniquement un estimateur ponctuel empirique de concordance). L'idée est que sous l'hypothèse nulle (appelée dans ce cas particulier "hypothèse de symétrie"), l'une des diagonales du tableau devrait avoir des valeurs égales.  En d'autres termes sous la forme des proportions et en ne nous concentrant que sur une des deux diagonales:

  (57.104)

ou de fréquences:

  (57.105)

Sachant que:

  (57.106)

et sous la condition que n est suffisamment grand, nous pouvons écrire en nous basant sur une loi Binomiale dont le comportement est asymptotiquement Normal:

  (57.107)

Nous pouvons nous rendre compte que cela équivaut à écrire:

  (57.108)

Dans la littérature spécialisée, nous retrouvons souvent cette dernière relation sous la forme:

  (57.109)

Pour en revenir à notre relation initiale, certains en prennent le carré et approximent alors le carré de Z comme une loi du Khi-deux à un degré de liberté (mais bon dans la réalité approximer une loi Normale centrée réduite par une loi du Khi-deux à un degré de liberté c'est un peu n'importe quoi...):

  (57.110)

qui est souvent la relation définie dans les livres (sans démonstration...) comme étant le "test de McNemar".

Le test est normalement effectué en bilatéral. L'avantage du test de McNemar est la facilité avec laquelle nous pouvons construire un intervalle de confiance de la différence de la diagonale. Effectivement, partons de l'estimateur de la différence:

  (57.111)

Dès lors en utilisant aussi la variance (et la covariance) démontrée lors de notre étude de la loi multinomiale dans le chapitre de Statistiques, il vient:

  (57.112)

et donc nous pouvons faire un intervalle de confiance approximatif si les conditions habituelles sont respectées sous la forme:

  (57.113)

Exemple:

Lors d'un audit social, un sondage est mené sur 200 salariées à propose de l'organisation du travail. Après des réaménagements, la même question est posée. Peut-on considérer qu'il y a eu de réels changements?

Nous avons alors en prenant arbitrairement la diagonale (25, 38) pour l'analyse:

  (57.114)

La majorité des logiciels de statistique ne vous donneront pas 2.683 car ils appliquent une correction empirique à cause de l'approximation grossière qu'est la loi de Khi-deux. Vous aurez alors sur l'écran des logiciels la valeur de 2.285. pour .

La p-value sera elle donnée (sans la correction) avec un logiciel comme la version française de Microsoft Excel 14.0.6123 par :

=1-LOI.KHIDEUX.N(2.683;1;1)=10.14%

et avec la correction elle donnerait environ 13%. Donc dans les deux cas la p-value étant supérieure au seuil de 5%, on ne peut alor rejetter l'hypothèse nulle comme quoi la différence des deux valeurs est grande.

Nous ne calculerons pas dans l'exemple ici présent l'intervalle de confiance de l'écart d car les logiciels de statistiques ont presque tous des méthodes différentes de calcul pour cette valeur.

Enfin, pour clore le sujet concernant le test de McNemar, signalons un indicateur empirique souvent utilisé est qui s'appelle le "coefficient de Yule" défini par:

  (57.115)

Ainsi, si Q vaut 1, il est certain que les valeurs concordent et donc que Y est positivement lié à X. Si Q vaut -1, il est respectivement certain que les valeurs sont discordantes et que Y est négativement lié à X. Lorsque les valeurs sont indépendantes, Q sera nul.

Encore une fois, insistons sur le fait qu'il faut cependant être très critique (comme toujours!) en utilisant ce type d'outil (coefficient de Yule ou test de McNemar). Comprendre sa construction permet aussi d'en identifier les faiblesses et hypothèses qui sont tout à fait discutables.

TEST DE COCHRAN-MANTEL-HAENZEL

Le "test logarithmique des rangs" appelé aussi "test de (Cochran)-Mantel-Haenzel à temps stratifié" ou encore "test de Mantel-Cox", ou encore "test du khi-2 de Cochran-Mantel-Heanzel" ou plus simplement encore "test CMH" ou encore "test des proportions multi-strates"... a pour objectif (principal dans la pratique) de tester l'hypothèse nulle comme quoi deux courbes de survies (groupe Contrôle versus groupe Test), comme celles visibles ci-dessous (où la population survivant a été normalisée sur l'axe des ordonnées), sont significativement différentes ou non sous les hypothèses que:

H1. Chaque strate est indépendante de la précédente

H2. À chaque strate on s'attend à ce que la proportion attendue de survivants/décès soit identique toute chose égale par ailleurs (voir plus loin si ce n'est pas clair).

H3. Chaque strate est distribuée selon une loi hypergéométrique.

H4. La loi hypergéométrique est approximable par une loi Normale (ce que nous allons le rappeler, ne peut être fait que sous certaines conditions).

Autrement dit, l'hypothèse nulle du test est que le traitement (médical, mécanique ou autre) n'a pas d'influence entre le groupe de Contrôle et le groupe de Test.

Figure: 57.15 - Courbes de survie type

Autrement dit, l'hypothèse nulle du test est que le traitement (médical, mécanique ou autre) n'a pas d'influence entre le groupe de Contrôle et le groupe de Test.

Pour introduire ce test, nous créons une table de contingence  pour chaque intervalle (strate) de temps  où  (chaque intervalle de temps peut aussi être assimilié à un hôpital différent pour une même étude clinique) qui aura la structure suivante:

Nous parlons alors de table générale stratifiée  ou de "tableau de contingence à trois dimensions"...

Ainsi, sous l'hypothèse que toutes les  choses sont égales par ailleurs (H2), et c'est là l'essence même du test!, le nombre d'individus attendus pour chaque cellule de la période i sera comme pour le test exact de Fisher ou le kappa d'agrément de Kohen égal à:

  (57.116)

Donc il faut bien comprendre que par exemple,  représente alors le nombre d'individus morts attendus  du groupe Contrôle si celui-ci ce comportait comme l'ensemble des individus Contrôle+Test. Donc si les deux groupes (courbes de survie) se comportent identiquement, la valeur attendue devrait être alors égale à la valeur observée.

Pour bien comprendre, illustrons le concept avec un exemple particulier:

Ici, les valeurs attendues donnent:

et nous remarquons que dans ce cas particulier, les valeurs attendues sont égales aux observées (simplement pour la raison que les rapports 800/1'000 et 1'120/1'400 représentent dans le tableau des observations le même pourcentage (la même proportion) de 80%). Évidemment, si la proportion des survivants observés pour les deux groupes sont égaux toutes choses égales par ailleurs, il en va de même pour les morts observés. Donc ce qu'il faut bien comprendre, quand nous faisons le test de MCH, c'est que nous sommes libre de choisir la colonne à analyser (puisque finalement cela revient au même!).

Nous remarquons que chacune des relations:

  (57.117)

représente en réalité l'espérance d'une loi binomiale ou hypergéométrique (cf. chapitre de Statistiques) puisque les deux lois ont la même expression pour l'espérance. Cependant, comme la taille des individus dans les cellules pourrait significative par rapport au total des lignes ou des colonnes, les tirages ne peuvent pas être indépendants. Nous devons alors nous rabattre sur la loi hypergéométrique (H3).

Nous voyons aussi que par symétrie des relations ci-dessus, que la variable d'intérêt soit l'attribut de colonne ou de ligne ne change absolument rien en réalité au résultat du calcul puisque (par exemple):

  (57.118)

La variance pour chaque cellule sera alors celle de la loi hypergéométrique que nous avons déjà démontré dans le chapitre de Statistiques comme étant donnée par:

  (57.119)

avec pour rappel . Si nous adaptons l'écriture du chapitre de Statistiques au cas de notre tableau ci-dessus, cela donne pour toutes les cellules (de par l'écriture de la variance de la loi hypergéométrique la variance a la même expression pour chaque cellule!):

  (57.120)

avec respectivement par exemple (pour ceux qui veulent faire l'analogie avec notre traitement de la loi hypergéométrique dans le chapitre de Statistiques):

  (57.121)

Là aussi, nous voyons que peu importe que la variable d'intérêt soit en ligne ou en colonne, la valeur calculée de la variance reste la même!!!

Et puis....??? En quoi cela va nous aider à comparer si les deux courbes de survie sont identiques à travers le temps (ou à travers différents hôpitaux s'il s'agit d'un test clinique)?!

Eh bien prenons comme exemple de départ le tableau des valeurs observées suivantes:

Nous avons alors pour les valeurs attendues:

Soit la différence:

Nous comprenons alors déjà mieux pourquoi cela n'a aucune influence de choisir une cellule en particulier pour faire le test. Nous prendrons simplement celle qui nous arrangera le plus (en fonction de ce qui va suivre...).

Et prenant donc au hasard (puisque le choix n'influence - du moins pour l'instant.... - pas le résultat du test comme nous l'avons montré dans les calculs précédents) la colonne des Survivants et particulièrement les observés du groupe de Test. Sa valeur attendue est alors:

La différence entre observés et attendus donne:

  (57.122)

Cette différence serait évidemment nulle si l'observé était égal aux attendus! Avec pour variance:

  (57.123)

Maintenant, sous les conditions

  (57.124)

vues dans le chapitre de Statistiques, la loi hypergéométrique peut être approximée par une loi Normale (H4).

Donc dans notre cas, cette approximation n'est pas acceptable (la troisième condition est disqualifiante) et donc le test ne peut être effectué (normalement on s'arrange pour prendre la colonne et la ligne qui permettent cette approximation puisque le choix n'influe pas sur la valeur du test mais sur l'autorisation de faire l'approximation mentionnée!). Mais si elle l'avait été, nous aurions pu approximer la loi hypergéométrique par une loi Normale (cf. chapitre de Statistiques):

  (57.125)

Ce qui peut ce ramener à une loi Normale centrée réduite si nous prenons dans notre cellule du tableau des observés:

  (57.126)

Et dès lors il suffit pour une strate i de savoir si nous sommes en dehors de l'intervalle de confiance que nous nous sommes fixés. Mais... nous avons plusieurs strates! L'idée est alors soit de sommer sur les T strates par indépendance (H1):

  (57.127)

ce qui est peu pratique (était du moins à l'époque où pas tout le monde avait un ordinateur), raison pour laquelle on préfère faire la somme suivante:

  (57.128)

Soit sous forme condensée (encore une fois! peu importe le choix de la cellule!):

  (57.129)

Et si les différences entre attendu et observé n'est pas trop grande à travers toutes les strates, la valeur de cette expression se trouvera dans un certain intervalle de confiance de la loi Normale. En dehors l'hypothèse d'égalité des deux courbes de survie sera rejetée.

Cependant, la majorité des logiciels de statistique prennent le carré de cette dernière relation.

Il vient alors que la carré suit une loi du khi-2 à un degré de liberté (nous l'avons démontré dans le chapitre de Statistiques) tel que nous trouvions la forme finale telle que l'on peut la trouver dans la littérature du test logarithmique des rangs:

  (57.130)

Il s'agit donc d'une statistique de Wald (cf. chapitre de Statistiques) et donc le test CMH appartient à la famille des tests de Wald.

Pour des raisons pratiques, nous ajoutons un terme 0.5 à la somme, ceci assure une meilleure approximation à la loi Normale. Donc:

  (57.131)

Exemple:

Considérons les valeurs observées suivantes  de deux hôpitaux A et B pour un test clinique:

Nous souhaiterions donc non pas savoir si les deux hôpitaux sont différents ou pas (là n'est pas le propos), mais de savoir si les différences entre le groupe de Contrôle et de Test sur l'ensemble des hôpitaux est significativement différent ou  non.

Bon nous devinons déjà le résultat intuitivement au vu des valeurs... mais faisons quand même les calculs.

Nous voyons déjà que pour l'hôpital A, la colonne des Survivants satisfait les trois conditions pour l'approximation par une loi Normale (ce qui n'est pas les cas pour la colonne des Morts):

  (57.132)

De même pour l'hôpital B (et c'est heureux car une fois une colonne choisie pour une strate, il faut que la condition d'approximation soit applicable à la même colonne de toutes les autres strates):

  (57.133)

Les valeurs attendues respectives donnent pour la colonne d'intérêt:

Ce qui donne pour les différences:

Nous voyons alors rapidement pourquoi une fois la colonne choisie, celui de la ligne n'a plus d'importance (soit une somme des valeurs négatives, soit on somme des valeurs positives et comme on prend le carré de la somme, cela ne change rien au final!). Choisissons arbitrairement la deuxième ligne. Nous avons alors:

  (57.134)

Et nous avons avec un tableur standard comme Microsoft Excel 14.0.6123 en unilatéral gauche à un seuil de risque de 5%:

  (57.135)

Donc sur le cumul des deux hôpitaux (strates) le groupe de Contrôle est significativement différent du groupe de Test. La p-value du test est typiquement donnée avec Microsoft Excel 14.0.6123:

1-LOI.KHIDEUX.N(31.845;1;1)=0.000002%   (57.136)

MÉTHODE DES DIFFÉRENCES FINIES

Dans le domaine des méthodes numériques, nous pouvons être amenés à rechercher la solution d'une équation aux dérivées partielles. Parmi les méthodes de résolution couramment pratiquées, la méthode des différences finies ou M.D.F. est la plus facile d'accès, puisqu'elle repose sur deux notions: la discrétisation des opérateurs de dérivation/différenciation (assez intuitive) d'une part, et la convergence du schéma numérique ainsi obtenu d'autre part.

Prenons deux exemples fameux (car très scolaires) qui ne sont que des cas particuliers et simplistes d'application de la M.D.F.

M.D.F À UNE DIMENSION SPATIALE

Rappelons que nous avons démontré dans le chapitre de Thermodynamique l'équation de la chaleur suivante (nous présentons ici cette équation réduite à une dimension spatiale):

  (57.137)

et remarquons que cette équation n'est pas très générale... (elle n'est pas relativiste et ne prend pas en compte la chaleur dégagée sous forme de rayonnement par le matériau considéré ni plein d'autres facteurs...).

Nous pouvons considérer (cf. chapitre de Calcul Différentiel Et Intégral) que:

  (57.138)

et:

  (57.139)

De même:

  (57.140)

L'équation de la chaleur devient alors:

  (57.141)

Après réarrangement, nous avons:

  (57.142)

Si nous regardons cette relation de plus près, nous observons qu'il s'agit d'une simple récursivité. Il suffit de connaître la distribution  pour déterminer ensuite toutes les autres valeurs puisque:

  (57.143)

et:

  (57.144)

etc.

Il est possible de mettre en oeuvre une telle simulation rien qu'avec un petit tableur et un peu de temps...

Pour information h et k sont appelés alors le "pas de maillage" du modèle et nous pouvons identifiquer un problème par rapport à ces deux derniers. Ce que s'ils sont tels que:

Pour le lecteur souhaitant s'entraîner... une barre de Fer longitudinale de 1 kilogramme a une capacité calorifique massique de , une densité de  et sa conductivité thermique est de .

M.D.F SPATIO-TEMPORELLE

La M.D.F. est donc une méthode numérique très importante dans la pratique car elle permet aussi de résoudre par exemple directement les équations de Maxwell dans le domaine temps et dans l'espace. Elle se classe alors dans la famille des méthodes 3D (discrétisation tridimensionnelle de l'espace) et temporelles et trouve ses principales applications dans les domaines de la conception (antennes et circuits), de la compatibilité électromagnétique, de la diffraction, de la propagation et de la dosimétrie électromagnétique (interaction ondes- matière vivante).

Nous allons présenter ici les bases du concept car dans la pratique, la programmation de la M.D.F. est un métier à lui seul (comme tout le reste du site bien évidemment mais il est parfois utile de le rappeler).

Dans un problème d'électrodynamique traité par M.D.F., la première opération nécessaire consiste à délimiter le volume V de l'espace et l'intervalle de temps I=[0,T] pour lesquels on souhaite effectuer cette résolution (il est illusoire d'espérer résoudre les équations de Maxwell dans l'espace infini et pour une durée illimitée!). Le volume de calcul contient l'objet (antenne, circuit, ...) que l'on souhaite caractériser, en réponse à une excitation donnée. Dans un deuxième temps, il convient de procéder à un échantillonnage de l'espace (maillage de V) et du temps (discrétisation de I) afin de permettre une implémentation numérique de la résolution. Le problème devient dès lors celui de la détermination du champ en tout point du maillage et pour tout instant discret de l'intervalle d'observation. Les échantillonnages spatial et temporel seront précisés dans la suite et découleront naturellement de la physique des équations à résoudre. Ils conditionnent bien évidemment à la fois la précision des résultats du calcul et les ressources informatiques requises pour le mener à bien.

La structuration du maillage M.D.F. et le cheminement de la résolution résultent directement des équations à résoudre.

Dans un milieu linéaire, homogène, isotrope, non dispersif et non magnétique (...), celles-ci s'écrivent explicitement en se basant sur la troisième équation de Maxwell (cf. chapitre d'Électrodynamique):

  (57.145)

Soit explicitement et avec le signe négatif passé de l'autre côté de l'égalité:

  (57.146)

Et nous utiliserons aussi la quatrième équation de Maxwell sans sources:

  (57.147)

Soit explicitement et réarrangé:

  (57.148)

Soit pour résumer:

  (57.149)

Dans la suite, nous nous intéresserons uniquement à la première équation, les autres conduisant à des développements similaires.

Afin de permettre un traitement sur calculateur, les différentes dérivées présentes dans l'équation doivent être approchées numériquement. Pour ce faire, nous utilisons le principe des différences finies centrées qui s'appuie sur les développements en série de Taylor suivants (cf. chapitre Suites Et Séries):

  (57.150)

Nous avons alors sur la base de ce principe:

  (57.151)

Si nous négligeons les termes du deuxième ordre, il vient en soustrayant les deux séries:

  (57.152)

où  est une erreur d'ordre 2, négligée par la suite (nous noterons que c'est le centrage qui , en permettant une compensation des dérivées secondes, minimise l'erreur dans l'approximation).

En appliquant ce principe aux dérivées temporelles et spatiales de:

  (57.153)

nous obtenons:

  (57.154)

ou encore après réarrangement:

  (57.155)

Cette relation montre que si nous connaissons les composantes  du champ électrique à l'instant t et la composante  du champ magnétique à l'instant antérieur , il est possible de déterminer  à l'instant . Bien évidemment la démarche est parfaitement identique pour toutes les composantes et montre le même décalage temporel. Ce résultat suggère donc d'utiliser une résolution numérique itérative, dans laquelle les champs électrique et magnétique sont évalués alternativement, respectivement aux instants discrets  et ,  étant le pas du temps. Il est d'usage dans la littérature spécialisée de noter  la composante du champ magnétique à l'instant .

Le même constat s'applique pour la distribution spatiale des points d'observation du champ. Ainsi, l'évaluation de  au point  s'appuie sur la connaissance de  aux points  et   et de  aux points  et   .

Nous pouvons donc résumer cela sous la forme géométrique suivante:

Figure: 57.16 - Cellule de Yee

Les composantes du champ électrique sont évaluées aux centres des arêtes du maillage et les composantes du champ magnétique aux centres des faces de façon à garantir l'alternance imposée par les équations (on appelle "cellule de Yee" la maille élémentaire dotée de cette répartition de points).

Et donc globalement, nous avons un maillage de l'espace qui peut être représenté sous la forme suivante:

Figure: 57.17 - Exemple de maillage par parallélépipède

Évidemment, nous pouvons exécuter les routines de calcul avec une valeur de la permittivité et de la perméabilité du vide non forcément égales dans toutes les cellules. Ce qui permet en plus de modéliser la propagation d'ondes électromagnétiques dans des milieux hétérogènes et non isotropes.

Enfin, il est important de noter que le pas d'échantillonnage spatial et temporel doit pouvoir être paramétrable par l'utilisateur qui exécute ce type de simulations. Ceci pour des raisons de temps de calculs et aussi de précision. Effectivement, nous n'effectuons pas les mêmes modélisations pour un système multiphysique dans le vide à basse fréquence que dans la matière non isotrope à haute fréquence et ce, que ce soit sur un ordinateur de bureau ou un supercalculateur.

CLUSTERING

En analyse de données statistiques, le clustering (data clustering pour les anglophones) décrit des méthodes empiriques de classification de données (méthode de regroupement hiérarchique ou méthode de partitionnement de données).

Il s'agit de techniques permettant typiquement la segmentation de l'ensemble des clients d'une entreprise en fonction de leur démographie ou de leurs habitudes d'achat, de grouper des documents pour des présentations, d'identifier de nouvelles espèces animales ou végétales, de regrouper de l'information ou des individus par par intérêts.

Nous considérons dans la pratique deux grandes familles de techniques de clustering (attention! même les spécialistes du domaine n'arrivent pas à se mettre d'accord sur une classification commune...):

1. Les "techniques non hiérachiques": c'est-à-dire où le nombre de classes (groupes) finales est choisi à l'avance.

2. Les "techniques hiérarchiques": c'est-à-dire où l'on aboutit à un classement par agrégations successives.

Parmi ces deux familles nous distinguons deux-sous familles:

S1. Les techniques qui font usage de données dont la propriété nominale de classification est connue à l'avance pour entraîner un modèle de prédiction: "machine learning" ou "apprentissage supervisé" ("supervised learning" en anglais). Nous y retrouvons la techniques de régression logistique binaire, les CRT, l'ID3, l'analyse discriminante, les réseaux bayésiens, les listes de décisions, les k-NN, les réseaux de neurones... Comme il n'y a pas de consensus au niveau des définitions, il est important que le lecteur sache aussi que les algorithmes "supervisés" sont les algorithmes par lequal il existe un mécanisme de correction des paramètres du modèle en fonction des erreurs produites.

S2. Les techniques qui font usage de données dont aucune propriété nominale connue à l'avance ne laisse supposer d'une classification et qui cherchent une classification possible (c'est ce qui au niveau du business est souvent le plus intéressant): "data mining" ou "apprentissage non supervisé" ("unspervised learning" en anglais) ou plus rarement "fouille de données", "forage de données", "prospection de données". Nous y retrouvons les techniques CAH, les k-means, etc.

L'utilisation industrielle ou opérationnelle de ce savoir dans le monde professionnel permet de résoudre des problèmes très divers, allant de la gestion de la relation client à la maintenance préventive, en passant par la détection de fraudes ou encore l'optimisation de sites web, la surveillance des marchés financiers, la prospection pro-active (préférences de consommation des clients), l'optimisation des chemins (analyse des routes à bouchons et à virages à gauche), ou choix des cibles (probabilité d'acquérir un nouveau prospect donné), anticiper l'identifications des terroristes, etc.

Nous allons voir ici quelques techniques triviales que nous compléterons avec le temps...

ARBRE DE RÉGRESSION ET DE CLASSIFICATION

Les arbres de régression et de classification (en anglais CART pour Classification and Regression Tree) sont un ensemble d'algorithmes heuristiques très utilisés en marketing ou dans les sciences sociales pour discriminer (catégoriser) une très grande population. Bien évidemment, ces algorithmes (qui font partie des techniques hiérarchiques) ne feront jamais mieux qu'un être humain... mais demandez aussi à un employé de créer des groupes dans une population de 5 millions de clients sur la base d'une dizaine de variables explicatives. Vous allez pouvoir attendre la réponse longtemps...

Bien que ces techniques automatisées de classification soient très utiles dans les situations susmentionnées, elles ont cependant un problème majeur qui fait que nous ne nous étendrons pas trop sur le sujet:

1. Ces techniques sont très sensibles à la population analysée et donnent des résultats très différents.

2. Les différentes techniques de classifications existantes donnent des résultats souvent totalement différents pour une même population.

Il vaut donc mieux être prudent quant aux conclusions que nous pouvons en tirer et comparer les résultats de plusieurs méthodes et en fonction du retour d'expérience choisir celle qui subjectivement semble la mieux adaptée.

Considérons un ensemble de variables catégorielles . Le partitionnement récursif a pour but de diviser l'espace des p variables en rectangles qui ne se chevauchent pas.

Par exemple, soit la variable  et une valeur  de cette variable, on trouve que le partitionnement où  et  sépare bien les données en deux ensembles disjoints. Ensuite, une des deux parties est à son tour divisée par une valeur de  ou par la valeur d'une autre variable. Nous aboutissons alors à trois rectangles et ainsi de suite...

L'idée est de créer n rectangles de telle sorte que l'ensemble de données contenues dans un rectangle soit homogène (c'est-à-dire ne contienne qu'une seule famille de points).

Pour traiter de ce sujet, considérons un cas pratique:

Un concessionnaire souhaiterait pour sa ville trouver un moyen de classer les familles qui sont à même d'acheter une voiture (propriétaires) et celles qui ne sont pas prêtes à en acheter (non-propriétaires). Un échantillon de 12 propriétaires (valeur "1" dans la figure ci-dessous) et 12 non propriétaires (valeur "2" dans la figure ci-dessous) est choisi. Les deux variables indépendantes sont  (revenus en kilo-francs) et  (surface de leur habitat):

Figure: 57.18 - Données à classifier

Nous voyons que nous avons autant de propriétaires que de non-propriétaires (fréquence d'apparition égale dans toute la population). Dès lors la probabilité d'appartenance à une classe est de 50%.

Soit graphiquement:

Figure: 57.19 - Représentation des points (revenus, surface)

Si nous appliquons l'algorithme CART sur ces données, nous voyons que nous devons choisir  (Surface) comme premier choix de division avec la valeur de division 19 (nous allons justifier pourquoi!). L'espace  est maintenant divisé en deux rectangles (il était facile de deviner cette étape de discrimination même sans faire appel aux mathématiques):

Figure: 57.20 - Première itération de la classification

Notez comment la division en deux rectangles a créé deux zones (split) qui sont plus homogènes que le graphique initial. Le rectangle supérieur contient des points qui sont davantage des propriétaires tandis que le rectangle inférieur contient davantage de non-propriétaires.

Pour déterminer cette division, l'algorithme CART a examiné chaque variable et toutes les valeurs possibles de division pour chaque variable de façon à trouver la meilleure division.

Ainsi, les points de division possible pour  sont (remarquez qu'il s'agit à chaque fois de la moyenne de deux valeurs connexes du tableau):

  (57.156)

et ceux pour  sont:

  (57.157)

Ces points sont ordonnés par l'algorithme d'après la façon dont ils réduisent "l'impureté" (hétérogénéité de composition) dans le rectangle que génère  le "split".

Il existe un grand nombre de façons empiriques de mesurer l'impureté. La plus commune à ce jour est l'utilisation d'un indicateur inspiré du coefficient de Gini (cf. chapitre de Techniques De Gestion). Ainsi, si nous dénotons les classes par  où C est le nombre total de classes à prédire, "l'indice d'impureté de Gini" pour le rectangle A est défini par:

  (57.158)

où  est la fraction d'observations dans le rectangle A qui appartiennent à la

classe k. Dans le cas qui nous concerne, nous avons toujours deux classes: Propriétaires/Non- Propriétaires.

Ensuite, l'indice de Gini global est défini comme la moyenne pondérée des indices de Gini.

Ainsi dans le cadre de notre exemple, nous avons deux classes, donc . Avant la séparation, nous avons:

  (57.159)

La séparation trouvée en 19 (voir le deuxième graphique) donne par exemple pour le rectangle supérieur de la première subdivision:

  (57.160)

Pour la partie inférieure:

  (57.161)

Le hasard faisant, l'impureté est la même pour les deux rectangles (du haut et du bas).

L'indice de Gini global est alors donné par:

  (57.162)

Remarquons avant de continuer que si la subdivision est parfaite (n'avoir qu'une seule famille de points dans un des rectangles), nous avons alors:

  (57.163)

donc l'impureté est nulle... Et si tous les points apparaissent en proportions égales dans chacun des rectangles (pire des cas en quelque sorte), la valeur est alors:

  (57.164)

Si nous généralisons à C classes (C dimensions spatiales), il vient immédiatement:

  (57.165)

ce qui est l'impureté maximale.

Donc l'impureté est toujours définie par une valeur dans l'intervalle:

  (57.166)

Maintenant, pour continuer avec notre exemple, même sans faire appel à un algorithme informatique et sans même calculer l'impureté, il est relativement aisé de deviner où va se trouver la prochaine discrimination: elle sera en  (revenus). Ce qui donnera:

Figure: 57.21 - Deuxième itération de la classification

Ce qui était aussi facile à deviner même sans faire appel aux calculs (essayez avec votre entourage, vous verrez que très souvent ils trouvent les deux premières discriminations).

L'impureté devra donc être calculée dans la nouvelle zone discriminée mise en évidence par un hachurage. Nous y avons donc:

  (57.167)

L'indice de Gini global est alors:

  (57.168)

Nous continuons, mais sachez que la suite est moins facile à deviner. La majorité des individus interrogés se trompent sans faire appel à la définition mathématique de l'impureté et proposent intuitivement  à tort l'une ou l'autre des discriminations suivantes:

Figure: 57.22 - Troisième itération de la classification

avec (vous pouvez faire le calcul) une impureté totale de 0.2727. Alors qu'en réalité, la discrimination optimale est:

avec une impureté totale de 0.2592. Effectivement:

  (57.169)

L'indice de Gini global est alors:

  (57.170)

À l'étape suivante, nous avons:

Figure: 57.23 - Quatrième itération de la classification

À l'étape suivante:

Figure: 57.24 - Cinquième itération de la classification

etc. jusqu'à obtenir au final:

Figure: 57.25 - Résultat final de la classification

où chaque rectangle est pur (ne contient des données que d'une des deux classes).

La raison pour laquelle la méthode est appelée algorithme d'arbre de classification est que chaque division peut être figurée comme la division d'un noeud en deux noeuds successeurs. La première division est montrée comme un branchement du noeud racine de l'arbre. Voici par exemple (faute de place sur la page) les six premières itérations de l'algorithme.

Figure: 57.26 - Représentation du résultat sous forme d'arbre/organigramme

et comme mentionné plus haut, nous nous arrêterons ici puisque l'ensemble des techniques empiriques forment un métier à part entier tellement elles sont nombreuses (et presque aucune ne donne le même résultat). Indiquons enfin qu'il existe également des réseaux de neurones (voir ci-après) spécialisés dans la classification.

K-MEANS

L'algorithme des K-moyennes ou "centres mobiles" ou "K-means" en anglais , appelé aussi parfois "classification avec méthode des nuées dynamiques", est en statistiques et en apprentissage automatique (plus précisément en apprentissage non supervisé), un algorithme de partitionnement de données, c'est-à-dire une méthode dont le but est de diviser des observations en K partitions (clusters) dans lesquelles chaque observation appartient à la partition avec la moyenne la plus proche.

Les étapes de base de l'algorithme sont les suivantes:

E1. Nous choisissons un partitionnement en K groupes

E2. Nous générons K moyennes (centres) au hasard

E3. Les données sont affectées au groupe dont le centre leur est le plus proche

E4. Nous calcule la moyenne de chaque groupe en utilisant les données affectées

E5. Nous retournons à l'étape E3

L'algorithme K-means (qui fait doncpartie des techniques non hiérarchiques) ne converge cependant pas forcément vers une solution optimale. Rappelons qu'un calcul d'optimisation globale est incompatible avec les volumes de données utilisés, quelle que soit la puissance des ordinateurs. Ainsi, les K-means vont utiliser des algorithmes itératifs permettant d'arriver à un optimum local. Ils vont tâtonner pour minimiser des matrices de varainces-covariances intra-classes. C'est aussi un algorithme qui va tenter de trouver les meilleurs K points initiaux.

Certains logiciels vous donnent la possibilité de paramétrer les valeurs initiales et cela va influencer la qualité finale de la typologie, tout en sachant qu'il n'existe pas UN bon choix initial. Cela varie en fonction de la configuration des données et même du hasard...

Il existe trois solutions fréquentes:

- 1ère solution: Le logiciel les détermine les K points initiaux aléatoirement. Il peut procéder à un certain nombre d'essais et il choisira le plus concluant.

- 2ème solution: L'avis d'expert, suppose que quelqu'un ait une assez bonne connaissance de la population étudiée pour rattacher à chaque classe un type idéal. Ce dernier peut être ou non un individu réel.

- 3ème solution: Le logiciel répartit les K points initiaux non aléatoirement mais selon certains algorithmes empiriques.

Plutôt que de présenter l'algorithme avec des équations mathématiques, il nous a semblé plus pédagogique de montrer comment implémenter cette technique dans un tableur comme Microsoft Excel 14.0.6123 car l'expérience nous montre que cela est beaucoup plus parlant et efficace.

Pour cela, nous allons considérer d'abord la structure suivante dont l'idée est de déterminer 3 centres (donc il s'agit d'un 3-means):

Figure: 57.27 - Structure de départ de base avec Microsoft Excel 14.0.6123

où nous avons à gauche des données d'une population basées sur caractéristiques X et Y avec un petit tableau qui affichera les coordonnées des trois centroïdes. Nous créons sur la même feuille le tableau suivant:

Figure: 57.28 - Tableau principal dans Micrsoft Excel 14.0.6123 pour l'algorithme

avec les formules triviales pour les trois colonnes N, O, P où l'on retrouve la norme de la distance euclidienne:

Figure: 57.29 - Formules correspondantes à la figure précédente

et les formules suivantes pour les deux colonnes restantes:

Figure: 57.30 - Formules pour l'assignation au cluster et la minimisation des distances

Ensuite, nous lançons le solveur de Microsoft Excel 14.0.6123 avec les paramètres suivants en faisant bien attention à prendre l'algorithme évolutionnaire ce qui fait que nous assumons qu'à chaque fois que nous pourrions avoir un résultat différent:

Figure: 57.31 - Paramétrages du solveur de Microsoft Excel 14.0.6123

et nous avons en lançant le solveur:

Figure: 57.32 - Résultat obtenu après lancement solveur

avec le tableau:

Figure: 57.33 - Tableau principal correspondant au résultat obtenu après exécution du solveur

Des logiciels spécialisés de statistiques comme Minitab 15.1.1 ou de Data Mining comme Tanagra 1.4.44 donnent en comparaison les valeurs des 3 centres et qui sont une fois reportées dans Microsoft Excel 14.0.6123:

Figure: 57.34 - Report du résultat de Minitab 15.1.1/Tanagra 1.4.44 dans Microsoft Excel 14.0.6123

avec le tableau:

Figure: 57.35 - Tableau principal correspondant aux centroïdes obtenus avec Minitab 15.1.1 et Tangra 1.4.44

La différence s'explique assez simplement! Un logiciel comme Microsoft Excel 14.0.6123 minimise la distance des points aux centres mais est incapable en même temps de maximiser la distance entre les centres. Par contre les logiciels de statistiques ont les algorithmes qu'il faut pour cela.

Minitab 15.1.1 ne donne pas de graphique mais Tanagra 1.4.44 lui donne:

Figure: 57.36 - Graphique obtenu avec Tanagra 1.4.44

Bien évidemment il est possible de trouver des logiciels faisant encore mieux!

DENDROGRAMME

Pour introduire cette autre technique de clustering, considérons directement l'exemple basé sur le tableau suivant:

Figure: 57.37 - Données de base pour l'étude des dendrogrammes

Nous souhaitons avoir une organisation hiérarchique de ressemblance des individus en fonction de leurs revenus et de leur surface d'habitation. Une technique consiste à définir une distance pour cette mesure de ressemblance. Par exemple, la distance euclidienne (si chaque individu à deux coordonnées):

est un choix particulier qui permettra d'associer deux individus dont la distance est minimale. Nous parlons alors dans le domaine du clustering de "lien simple".

Ainsi, nous pouvons facilement avec un tableur comme Microsoft Excel 14.0.6123 créer une "matrice des distances" qui est une matrice symétrique à diagonale nulle et qui relativement au tableau donné ci-dessus donnera:

Figure: 57.38 - Tableau des distances euclidiennes avec Microsoft Excel 14.0.6123

où nous avons mis dans la cellule D4 le calcul de la distance euclidienne:

=RACINE(($B4-D$2)^2+($C4-D$3)^2)

que nous avons ensuite tiré sur tout le reste du tableau jusqu'à la cellule AA27.

Ensuite, nous utilisons la méthode ascendante (agglomération) où nous combinons les groupes jusqu'à ce qu'il n'y ait plus qu'un seul groupe (contenant toutes les données).

Ce qui donnera sous forme tabulaire avec un logiciel comme Minitab 15.1.1.0 (les valeurs n'y sont par arrondies au centièmes contrairement au petit tableau donné précédemment):

où le niveau de similarité du groupe lié i, j est défini empiriquement par:

Ainsi, pour la première ligne nous avons par exemple:

La liste précédente est plus agréable à analyser si, comme il est d'usage, nous la représentons sous forme de "dendrogramme" (diagramme d'arrangement) suivant:

Figure: 57.39 - Graphique obtenu avec Minitab 15.1.1.0

RÉSEAUX DE NEURONES FORMELS

Les réseaux de neurones, fabriqués à partir de structures cellulaires artificielles, constituent une approche permettant d'aborder sous des angles nouveaux les problèmes de perception, de mémoire, d'apprentissage et de raisonnement non-linéaires (en d'autres termes... d'intelligence artificielle ou en abrégé "I.A.") au même titre que les algorithmes génétiques. Ils s'avèrent aussi des alternatives très prometteuses pour contourner certaines des limitations des méthodes numériques classiques. Grâce à leur traitement en parallèle de l'information et à leurs mécanismes inspirés des cellules nerveuses (neurones), ils infèrent des propriétés émergentes permettant de solutionner des problèmes jadis qualifiés de complexes.

Cependant, le problème majeur des neurones artificiels (à ma connaissance...), c'est qu'ils ne s'auto-organisent pas ni ne s'auto-structurent de manière intelligente. Il faut donc à ce jour, procéder de manière heuristique pour trouver la meilleure structure de réseau de neurones adaptée à un problème et c'est là leur grande faiblesse actuelle (on utilise soit la force brute via une base de données contenant des millions de modèles, soit les algorithmes génétiques que nous verrons un peu plus loin).

Nous aborderons ici les principales architectures des réseaux de neurones. Il ne s'agit pas de les étudier toutes, car elles sont trop nombreuses, mais plutôt d'en comprendre les mécanismes internes fondamentaux et de savoir comment et quand les utiliser. Nous aborderons également certaines notions relatives aux ensembles flous et à la logique (cf. chapitre de Logique Floue) dans la mesure où ces dernières sont incorporées dans certaines architectures de réseaux de neurones que nous étudierons.

Le cerveau humain contient environ 100 milliards de neurones. Ces neurones nous permettent entre autres, de lire un texte tout en maintenant une respiration régulière permettant d'oxygéner notre sang, en actionnant notre coeur qui assure une circulation efficace de ce sang pour nourrir nos cellules, etc. Ils nous permettent même de comprendre certaines idées (…)

Chacun de ces neurones est par ailleurs fort complexe. Essentiellement, il s'agit de tissu vivant et de chimie. Les neuro-physiciens commencent à peine à comprendre quelques-uns de leurs mécanismes internes. Nous pensons en général que leurs différentes fonctions neuronales, y compris celle de la mémoire sont stockées au niveau des connexions (synapses) entre les neurones. C'est ce genre de théorie qui a inspiré la plupart des architectures de réseaux de neurones artificiels (dits "formels"). L'apprentissage consiste alors soit à établir de nouvelles connexions, soit à en modifier des existantes (nous nous concentrerons en particulier sur cette dernière possibilité).

Ceci nous amène à poser une question fondamentale: en se basant sur nos connaissances actuelles, peut-on construire des modèles approximatifs de neurones et les entraîner pour, éventuellement, réaliser des tâches utiles ? Eh bien, la réponse courte est: oui !, même si les réseaux que nous allons développer ne possèdent qu'une infime fraction de la puissance du cerveau humain, et c'est l'objectif ici de montrer comment nous pouvons y arriver.

Les réseaux de neurones servent aujourd'hui à toutes sortes d'application dans divers domaines. Par exemple, il existe des réseaux de neurones développés pour les autopilotes d'avions, ou encore pour les systèmes de guidage pour automobiles, pour les systèmes de lecture automatique de chèques bancaires et d'adresses postales, pour le traitement du signal pour différentes applications militaires, pour la synthèse de la parole, pour bâtir des systèmes de vision par ordinateur, pour faire des prévisions sur les marchés monétaires, pour évaluer le risque financier ou en assurance, pour différents processus manufacturiers, pour le diagnostic médical, pour l'exploration pétrolière ou gazière, en robotique, en télécommunication, pour la classification et bien d'autres. Bref, les réseaux de neurones ont aujourd'hui un impact considérable et, il y a fort à parier, que leur importance ira grandissante dans le futur.

MODÈLE DU NEURONE

Le modèle mathématique d'un neurone artificiel, ou "perceptron", est illustré à la figure ci-dessous. Un neurone est essentiellement constitué d'un intégrateur qui effectue la somme pondérée de ses entrées (comme l'espérance statistique!). Le résultat n de cette somme est ensuite transformé par une fonction de transfert f qui produit la sortie a du neurone.

Les R entrées du neurone correspondent au vecteur noté traditionnellement en ligne (mais dans la pratique on représente sa transposée):

  (57.171)

alors que:

  (57.172)

représente le vecteur des poids du neurone (nous les distinguons pour préparer le terrain à des neurones un peu plus complexes).

Figure: 57.40 - Exemple de neurone formel à une couche avec vecteur d'entrée et scalaire de sortie

La sortie n de l'intégrateur est définie (car il s'agit d'une technique de l'ingénieur) par l'équation suivante:

  (57.173)

que nous pouvons aussi écrire sous forme matricielle (on pourrait aussi l'écrire sous forme tensorielle mais bon...):

  (57.174)

Cette sortie correspond à une somme pondérée des poids et des entrées moins que ce nous nommons "le biais b du neurone" (facteur correctif décidé par tâtonnement et souvent nul dans la pratique). La somme pondérée s'appelle le "niveau d'activation du neurone". Le biais b s'appelle aussi le "seuil d'activation du neurone". Lorsque le niveau d'activation atteint ou dépasse le seuil b, alors n, l'argument de f, devient nul ou bien évidemment positif. Sinon, il est négatif.

Nous pouvons faire un parallèle entre ce modèle mathématique et certaines informations que nous connaissons (ou que nous croyons connaître) à propos du neurone biologique. Ce dernier possède trois principales composantes: les dendrites, le corps cellulaire et l'axone:

Figure: 57.41 - Représentation simplifiée du vocabulaire des neurones humains

Les dendrites forment un maillage de récepteurs nerveux qui permettent d'acheminer vers le corps du neurone des signaux électriques en provenance d'autres neurones. Celui-ci agit comme une espèce d'intégrateur en accumulant des charges électriques. Lorsque le neurone devient suffisamment excité (lorsque la charge accumulée dépasse un certain seuil), par un processus électrochimique, il engendre un potentiel électrique qui se propage à travers son axone pour éventuellement venir exciter d'autres neurones. Le point de contact entre l'axone d'un neurone et la dendrite d'un autre neurone s'appelle le "synapse". Il semble que c'est l'arrangement spatial des neurones et leur axone, ainsi que la qualité des connexions synaptiques individuelles qui déterminent la fonction précise d'un réseau de neurones biologique. C'est en se basant sur ces connaissances que le modèle mathématique décrit ci-dessus a été défini.

Un poids d'un neurone artificiel représente donc en quelque sorte l'efficacité d'une connexion synaptique. Un poids négatif inhibe en quelque sorte une entrée, alors qu'un poids positif vient l'accentuer. Il importe de retenir que ceci est une grossière approximation d'une véritable synapse qui résulte en fait d'un processus chimique très complexe et dépendant de nombreux facteurs extérieurs encore mal connus. Il faut bien comprendre que notre neurone artificiel est un modèle pragmatique qui, comme nous le verrons plus tard, nous permettra d'accomplir des tâches intéressantes. La vraisemblance biologique de ce modèle nous importe peu. Ce qui compte est le résultat que ce modèle nous permettra d'atteindre.

Un autre facteur limitatif dans le modèle que nous nous sommes donnés concerne son caractère discret. En effet, pour pouvoir simuler un réseau de neurones, nous allons rendre le temps discret dans nos équations. Autrement dit, nous allons supposer que tous les neurones sont synchrones, c'est-à-dire qu'à chaque temps t, ils vont simultanément calculer leur somme pondérée et produire une sortie . Dans les réseaux biologiques, tous les neurones sont en fait asynchrones.

Revenons donc à notre modèle tel que formulé par l'équation précédente et ajoutons la fonction d'activation f pour obtenir la sortie du neurone:

  (57.175)

Il est temps maintenant de remplacer (parce que la notation est un peu lourde à la longue) par une matrice d'une seule ligne que nous noterons . Nous obtenons alors une forme générale que nous adopterons tout au long de notre étude:

  (57.176)

Cette équation nous amène à introduire un nouveau schéma plus formel de notre RNF (ou perceptron):

Figure: 57.42 - Exemple plus abouti du neurone formel

Nous y représentons les R entrées comme un rectangle noir (le nombre d'entrées est indiqué sous le rectangle). De ce rectangle sort le vecteur dont la dimension matricielle est . Ce vecteur est multiplié par une matrice W qui contient les poids (synaptiques) du neurone. Dans le cas d'un neurone simple, cette matrice possède la dimension . Le résultat de la multiplication correspond au niveau d'activation qui est ensuite comparé au seuil b (un scalaire) par soustraction. Finalement, la sortie du neurone est calculée par la fonction f. La sortie d'un neurone simple est alors toujours un scalaire.

Pour trouver les composantes de la matrice W (poids d'entrée du neurone), ainsi que le biais b nous utilisons des techniques de recherche opérationnelle (méthode du simplexe, méthode des gradients conjugués, algorithmes évolutionnaires, etc.) sur un échantillon des données de l'entreprise de taille n afin "d'entraîner le modèle du neurone". Il s'agira à l'aide de ce modèle de minimiser l'erreur donnée par:

  (57.177)

et ensuite de tester le résultat obtenu sur un échantillon test avant de faire de la simulation pour des données non encore existantes (nous ferons un exemple détaillé avec Microsoft Excel juste après avoir présenté les fonctions de transfert).

FONCTIONS DE TRANSFERT

Jusqu'à présent, nous n'avons pas spécifié la nature de la fonction d'activation de notre modèle. Il se trouve que plusieurs possibilités existent et celles-ci sont empiriques et à adapter en fonction des situations. Les plus courantes et les plus citées dans la littérature sont énumérées dans la figure ci-dessous:

Tableau: 57.34  - Types de fonctions de transfert pour les R.N.F.

Les trois les plus utilisées dans le domaine de l'ingénierie sont les fonctions "seuil" (a) (en anglais "hard limit"), "linéaire" (b) et "sigmoïde" (c) comme représentées ci-dessous:

Figure: 57.43 - Fonctions de transfert les plus utilisées à ce jour dans le domaine

Comme son nom l'indique, la fonction seuil applique un seuil sur son entrée. Plus précisément, une entrée négative ne passe pas le seuil, la fonction retourne la valeur 0 (faux), alors qu'une entrée positive ou nulle dépasse le seuil, et la fonction retourne 1 (vrai). Il est évident que ce genre de fonction permet de prendre des décisions binaires (cette fonction peut aussi être assimilée à la fonction de Heaviside pour ceux qui connaissent...).

La fonction linéaire est quant à elle très simple, elle affecte directement son entrée à sa sortie selon la relation . Il est évident que la sortie du neurone correspond alors à son niveau d'activation dont le passage à zéro (l'ordonnée à l'origine) se produit lorsque .

La fonction de transfert sigmoïde est quant à elle définie par la relation mathématique:

  (57.178)

elle ressemble soit à la fonction seuil, soit à la fonction linéaire, selon que nous sommes loin ou près de b respectivement. La fonction seuil est très non linéaire car il y a une discontinuité lorsque . De son côté, la fonction linéaire est tout à fait linéaire. Elle ne comporte aucun changement de pente. La sigmoïde est un compromis intéressant entre les deux précédentes. Notons finalement que la fonction "tangente hyperbolique" est une version symétrique de la sigmoïde.

ARCHITECTURE DE RÉSEAU

Par définition, un réseau de neurones est un maillage de plusieurs neurones, généralement organisés en couches. Pour construire une couche de S neurones, il s'agit simplement de les assembler comme dans la figure ci-dessous:

Figure: 57.44 - Illustration d'un réseau de neurones formel

Les S neurones d'une même couche sont tous branchés aux R entrées dans la figure ci-dessous. Nous disons alors que la couche est "totalement connectée". Mais c'est un cas particulier et non pas une généralité. Souvent, les entrées d'un neurone sont différentes de celles d'un autre neurone, etc.

Un poids est associé à chacune des connexions. Nous noterons toujours le premier indice par i et le deuxième par j (jamais l'inverse). Le premier indice (rangée) désigne toujours le numéro du neurone sur la couche, alors que le deuxième indice (colonne) spécifie le numéro de l'entrée. Ainsi, désigne le poids de la connexion qui relie le neurone i à son entrée j. L'ensemble des poids d'une couche forme donc une matrice W de dimension :

  (57.179)

Il faut bien sûr prendre en compte que dimensionnellement nous n'avons pas nécessairement dans le cas général (les nombres de neurones et d'entrées sont indépendants). Si nous considérons que les S neurones forment un vecteur de neurones, alors nous pouvons créer les vecteurs:

  (57.180)

Ceci nous amène à la représentation simplifiée illustrée ci-dessous:

Figure: 57.45 - Principe fonctionnel d'un réseau de neurones formel

Finalement, pour construire un réseau de neurones (ou PMC pour "Perceptron Multi-Couches"), il ne suffit plus que de combiner des couches comme ci-dessous:

Figure: 57.46 - Principe de construction d'un PMC

Cet exemple comporte R entrées et trois couches de neurones comptant respectivement neurones. Dans le cas général, de nouveau ces nombres ne sont pas nécessairement égaux. Chaque couche possède aussi sa propre matrice de poids , où k désigne l'indice de couche. Dans le contexte des vecteurs et des matrices relatives à une couche, nous emploierons toujours un exposant pour désigner cet indice. Ainsi, les vecteurs sont aussi associés à la couche k.

Il importe de remarquer dans cet exemple que les couches qui suivent la première ont comme entrée la sortie de la couche précédente. Ainsi, nous pouvons enfiler autant de couches que nous voulons, du moins en théorie. Nous pouvons fixer un nombre quelconque de neurones sur chaque couche. En pratique, nous verrons plus tard qu'il n'est cependant pas souhaitable d'utiliser trop de neurones. Notons aussi que rien ne nous empêche de changer de fonction de transfert d'une couche à l'autre. Ainsi, dans le cas général nous n'avons pas nécessairement .

Définition: La dernière couche est nommée "couche de sortie". Les couches qui précèdent la couche de sortie sont nommées "couches cachées".

Définition: "Entraîner" un réseau de neurones signifie modifier la valeur de ses poids et de ses biais pour qu'il réalise la fonction d'entrée sortie (I/O). Nous étudierons en détails différents algorithmes et méthodes d'approche heuristiques pour y parvenir dans différents contextes.

Exemple:

Une entreprise a mesuré pendant 14 semaines ses ventes réelles (Colonne: Valeur à prédire) en fonction des ventes prévisionnelles de cinq de ses succursales (Variable1, Variable2, etc.) et les a reproduites dans Microsoft Excel 14.0.6123:

Figure: 57.47 - Données d'entraînement pour le réseau de neurones

Signalons qu'il n'y a absolument aucune formule dans le tableau ci-dessus! Le retour d'expérience (et surtout l'emplacement...) nous dit qu'il vaudrait mieux faire une architecture de réseau à deux neurones, un premier avec les succursales {1,2,3} basé sur une sigmoïde et un deuxième avec les succursales {4,5} lui aussi basé sur une sigmoïde. De plus, l'ensemble devra avoir un seul et unique biais et les deux neurones devraient avoir un poids particulier en comparaison de l'un et l'autre.

Nous préparons alors le tableau suivant:

Figure: 57.48 - Poids, biais et pondérations à déterminer par recherche opérationnelle

Une fois le tableau des poids, biais et pondérations construit, nous écrivons notre réseau à deux neurones avec la fonction de sigmoïde par exemple juste à côté des données d'entraînement (ce qui facilitera la comparaison):

Figure: 57.49 - Poids, biais et pondérations à déterminer par recherche opérationnelle

Soit avec les formules explicites pour les trois dernières colonnes qui nous intéressent:

Figure: 57.50 - Le réseau de neurones avec les deux neurones, la fonction sigmoïde et la pondération à la sortie

Pour pouvoir appliquer une technique de recherche opérationnelle, il nous faut minimiser ou maximiser quelque chose. Dès lors, nous allons chercher à minimser la somme des erreurs quadratiques en créant la colonne suivante:

Figure: 57.51 - Ajout de la colonne avec l'erreur quadratique à minimiser

Soit avec les formules explicites (nous voyons bien que cela correspond au carré de la différence entre les mesures et le modèle):

Figure: 57.52 - Implémentation de la colonne avec l'erreur quadratique à minimiser

Il va s'agir maintenant avec le solveur de Microsoft Excel 14.0.6123 de minimiser le contenu de la cellule L36:

Figure: 57.53 - Ouverture du solveur et choix du GRG non linéaire

et il ne faut pas être trop regardant sur la précision des contraintes et il faut jouer un peu avec ce paramètre pour obtenir un résultat satisfaisant:

Figure: 57.54 - Options de précision des contraintes

Pour obtenir un résultat satisfaisant, il faudra mettre dans le cas présent une précision de 0.001. Ce qui donnera lors de l'exécution de la recherche par le solveur une erreur quadratique totale de 0.8479 (cellule L36) et pour les paramètres du réseau de neurones:

Figure: 57.55 - Paramètres du réseau de neurones

Des logiciels spécialisés feront mieux avec une erreur quadratique totale de 0.8405 (cellule L36) et pour les paramètres du réseau de neurones:

Figure: 57.56 - Paramètres du réseau de neurones

Nous pouvons comparer graphiquement les mesures utilisées pour entraîner le réseau de neurones et le résultat du modèle de réseau de neurones lui-même. Nous avons alors:

Figure: 57.57 - Comparaison réel/modèle

Ce qui est pas mal du tout pour un modèle non linéaire! Mais une fois le modèle entraîné, il faut voir s'il s'applique sur d'autres données:

Figure: 57.58 - Données de test pour voir si le modèle est bien entraîné

Toujours avec les mêmes formules:

Figure: 57.59 - Données de test pour voir si le modèle est bien entraîné

Et si nous comparons aussi graphiquement les données réelles et celles modélisées, nous obtenons:

Figure: 57.60 - Comparaison réel/modèle

et là nous voyons que le modèle est nettement moins bon. Mais c'est ainsi! La science prédictive n'est pas une science exacte mais une méthode heuristique...

ALGORITHMES GÉNÉTIQUES

Les algorithmes génétiques (AGs) sont des algorithmes d'optimisation stochastiques itérés fondés sur les mécanismes de la sélection naturelle et de la génétique appartenant à la famille des "algorithmes évolutionnaires". Il s'agit d'une technique d'optimisation qui s'est beaucoup répandue depuis le début du 21ème siècle grâce la version 14.0.6123 de Microsoft Excel où le solveur intègre un algorithme évolutionnaire par défaut comme en atteste la capture d'écran ci-dessous:

Figure: 57.61 - Capture d'écran du solveur de Microsoft Excel 14.0.6123

avec les options avancées correspondantes:

Figure: 57.62 - Options avancées de la résolution évolutionnaire du solveur de Microsoft Excel 14.0.6123

Le fonctionnement des algorithmes génétiques est relativement simple:

1. Nous partons avec une population de solutions potentielles (chromosomes) initiales arbitrairement choisies

2. Nous évaluons leur performance (fitness) relative

3. Sur la base de ces performances, nous créons une nouvelle population de solutions potentielles en utilisant des opérateurs évolutionnaires simples: la sélection, le croisement et la mutation.

4. Nous recommençons ce cycle jusqu'à ce que nous trouvions une solution satisfaisante.

Les AGs ont été initialement développés par John Holland (1975). C'est au livre de Goldberg (1989) que nous devons leur popularisation. Leurs champs d'application sont très vastes. Outre l'économie (minimisation du risque des portefeuilles), ils sont utilisés pour l'optimisation de fonctions, en finance, en théorie du contrôle optimal (recherche opérationnelle), ou encore en théorie des jeux répétés et différentiels (en l'occurrence dans les jeux évolutionnaires et le dilemme du prisonnier) et la recherche d'information (Google) ainsi que la recherche des plus courts chemins en théorie des graphes (routages Internet ou GPS). La raison de ce grand nombre d'applications est claire: simplicité et efficacité. Bien sûr, d'autres techniques d'exploration stochastiques existent, la méthode de Monte-Carlo peut être considérée comme un concept similaire.

Pour résumer, Lerman et Ngouenet (1995) distinguent quatre principales propriétés qui font la différence fondamentale entre ces algorithmes et les autres méthodes:

P1. Les algorithmes génétiques utilisent un codage des paramètres, et non les paramètres eux-mêmes.

P2. Les algorithmes génétiques travaillent sur une population de points, au lieu d'un point unique.

P3. Les algorithmes génétiques n'utilisent que les valeurs de la fonction étudiée, pas sa dérivée, ou une autre connaissance auxiliaire.

P4. Les algorithmes utilisent des règles de transition probabilistes, et non déterministes.

La simplicité de leurs mécanismes, la facilité de leur mise en application et leur efficacité même pour des problèmes complexes ont conduit à un nombre croissant de travaux ces dernières années.

Définitions:

D1. Un "algorithme génétique" est défini par un individu/chromosome/séquence et une solution potentielle au problème donné.

D2. Une "population" est un ensemble de chromosomes ou de points de l'espace de recherche

D3. "L'environnement" est assimilé à l'espace de recherche

D4. La fonction que nous cherchons à optimiser est appelée "fonction de fitness"

Avant d'aller plus loin, il faut définir de manière plus formelle les concepts précédents (mais sous l'hypothèse particulière ! de codage binaire).

Définition: Les organismes en compétition sont appelés "individus". Soit un alphabet , nous supposerons que chaque individu peut être représenté par un mot de longueur fixe l pris dans . Le mot A associé à un individu de la population sera appelé "chromosome" ou "séquence" (le terme n'est pas tout à fait équivalant à son homonyme biologique, cependant c'est une pratique courante que d'utiliser ce terme ici aussi) et donné donc par A de longueur l(A) avec (cause: hypothèse du codage binaire).

Dans la mesure où il n'y aura pas de risque de confusion, nous identifierons les termes individu et chromosome.

Les individus forment une population P de taille N, notée:

  (57.181)

Nous allons faire une autre assertion importante, c'est-à-dire, qu'il existe une fonction f d'une séquence à valeurs positives que nous noterons , dite "fonction de fitness" qui à tout associe un réel tel que:

  (57.182)

si et seulement si est mieux adapté au milieu que.

Remarquons que le terme "adapté" n'est pas défini. Pour cela, il faudrait caractériser le milieu dans lequel évoluent les individus, ce que nous ne ferons pas. En fait, puisque nous supposons l'existence d'une telle fonction et que nous posons l'équivalence avec le degré d'adaptation, celui-ci est automatiquement défini par la donnée de f.

Nous nommerons "génération" une population à un instant t, ce qu'il faut mettre en relation avec la notion de durée de vie ou d'âge. Cependant, nous nous placerons ici dans le cas particulier où chaque individu a une durée de vie égale à 1, donc la génération (t+1) est constituée d'individus différents de la génération t, nous les appellerons les "descendants". Réciproquement, les individus de la génération t seront les "ancêtres" des individus de la génération (t+1). Nous désignerons la génération t par P(t) soit la population à l'instant t.

Ainsi, un chromosome est vu comme une suite de bits en codage binaire appelée aussi "chaîne binaire". Dans le cas d'un codage non binaire, tel que le codage réel par exemple, alors la suite A ne contient qu'un point, nous avons avec .

Le but d'un algorithme génétique est alors simplement de trouver la chaîne qui maximise cette fonction f. Bien évidemment, chaque problème particulier nécessitera ses propres fonctions d et f.

Les AGs sont alors basés sur les phases suivantes:

1. Initialisation: une population initiale de N chromosomes est tirée aléatoirement

2. Évaluation: chaque chromosome est décodé puis évalué

3. Sélection: création d'une nouvelle population de N chromosomes par l'utilisation d'une méthode de sélection appropriée.

4. Reproduction: possibilité de croisement et mutation au sein de la nouvelle population

5. Retour à la phase d'évaluation jusqu'à l'arrêt de l'algorithme

CODAGE ET POPULATION INITIALE

Il existerait trois principaux types de codage: (1) Binaire, (2) Gray, (3) Réel. Nous pouvons facilement passer d'un codage à l'autre. Certains auteurs n'hésitent pas, par ailleurs, à faire le parallèle avec la biologie en parlant de génotype (cf. chapitre de Dynamique Des Populations) en ce qui concerne la représentation binaire d'un individu, et de phénotype (cf. chapitre de Dynamique Des Populations) pour ce qui est de sa valeur réelle correspondante dans l'espace de recherche.

Rappelons que la transformation la plus simple (fonction de décodage d) d'une chaîne binaire A en nombre entier x s'opère par la règle suivante (cf. chapitre sur les Nombres):

  (57.185)

où l est le nombre de chiffres de la chaîne -1.

Ainsi, le chromosome vaut trivialement:

  (57.186)

Évidemment, la fonction d sera adaptée (par tâtonnements!) selon le problème. Ainsi, si nous cherchons à maximiser une fonction une méthode possible serait la suivante (la taille du chromosome dépendant bien évidemment de la précision voulue):

  (57.187)

ce qui peut s'assimiler à une série harmonique. Pour une précision au cinquième chiffre après la virgule, nous imposerons puisque:

  (57.188)

Une autre façon de faire serait de choisir d telle que:

  (57.189)

Petite explicitation:

  (57.190)

Posons :

  (57.191)

Ainsi, avec nous avons et:

  (57.192)

Cette dernière règle peut se généraliser. Ainsi, admettons que nous cherchons à maximiser (normaliser serait un terme peut-être plus correct) f en fonction d'une variable réelle x. Soit , avec , l'espace de recherche permis avec et les bornes inférieures et supérieures. Soit prec la précision (chiffre après la virgule) avec laquelle nous cherchons x. Soit:

  (57.193)

la longueur de l'intervalle D. Nous devons alors diviser cet intervalle au pire en:

  (57.194)

sous-intervalles égaux afin de respecter la précision. Par exemple, soit nous avons donc si nous voulions une précision , alors il nous faut diviser cet intervalle en sous-intervalles.

Notons s l'entier naturel tel que , ce qui dans notre exemple implique puisque:

  (57.195)

la transformation d'une chaîne binaire en un nombre réel x peut alors s'exécuter en trois étapes:

1. Conversion (base 2 en base 10):

  (57.196)

2. Normalisation:

  (57.197)

3. Maximisation:

  (57.198)

ou ce qui revient au même directement en une seule étape par:

  (57.199)

Ainsi pour , et nous retrouvons bien:

  (57.200)

Pour ce qui est de la phase d'initialisation, la procédure est assez simple. Elle consiste en un tirage aléatoire de N individus dans l'espace des individus permis. En codage binaire, selon la taille l de la chaîne, nous effectuons pour un chromosome l tirages dans avec équiprobabilité.

OPÉRATEURS

Les opérateurs jouent un rôle prépondérant dans la possible réussite d'un AG. Nous en dénombrons trois principaux: l'opérateur de sélection, de croisement et de mutation. Si le principe de chacun de ces opérateurs est facilement compréhensible, il est toutefois difficile d'expliquer l'importance isolée de chacun de ces opérateurs dans la réussite de l'AG. Cela tient pour partie au fait que chacun de ces opérateurs agit selon divers critères qui lui sont propres (valeur sélective des individus, probabilité d'activation de l'opérateur, etc.).

OPÉRATEUR DE SÉLECTION

Cet opérateur est peut-être le plus important puisqu'il permet aux individus d'une population de survivre, de se reproduire ou de mourir. En règle générale, la probabilité de survie d'un individu sera directement reliée à son efficacité relative au sein de la population.

Il existe plusieurs méthodes pour la reproduction. La méthode la plus connue et utilisée est sans nul doute, la roue de loterie biaisée (roulette wheel) de Goldberg (1989). Selon cette méthode, chaque chromosome sera dupliqué dans une nouvelle population proportionnellement à sa valeur d'adaptation. Nous effectuons, en quelque sorte, autant de tirages avec remises qu'il y a d'éléments dans la population. Ainsi, dans le cas d'un codage binaire, la fitness d'un chromosome particulier étant f(d(A)), la probabilité avec laquelle il sera réintroduit dans la nouvelle population de taille N est:

  (57.201)

Les individus ayant une grande fitness ont donc plus de chance d'être sélectionnés. Nous parlons alors de "sélection proportionnelle".

L'inconvénient majeur de cette méthode repose sur le fait qu'un individu n'étant pas le meilleur pourrait tout de même dominer la sélection (imaginez la recherche du maxima d'une fonction dans , il peut y en avoir plusieurs - de maxima - et donc mauvaise sélection...), nous parlerons alors à juste titre de "convergence prématurée" et c'est l'un des problèmes les plus fréquents lors de l'utilisation des algorithmes génétiques. Elle peut aussi donc engendrer une perte de diversité par la domination d'un super individu. Un autre inconvénient est sa faible performance vers la fin quand l'ensemble des individus se ressemblent.

Une solution à ce problème ne tient pas dans l'utilisation d'une autre méthode de sélection mais dans l'utilisation d'une fonction de fitness modifiée. Ainsi, nous pouvons utiliser un changement d'échelle (scaling) afin de diminuer ou accroître de manière artificielle l'écart relatif entre les fitness des individus.

Brièvement, il existe d'autres méthodes, la plus connue étant celle du tournoi (tournament selection): nous tirons deux individus aléatoirement dans la population et nous reproduisons le meilleur des deux dans la nouvelle population. Nous refaisons cette procédure jusqu'à ce que la nouvelle population soit complète. Cette méthode donne de bons résultats. Toutefois, aussi importante que soit la phase de sélection, elle ne crée pas de nouveaux individus dans la population. Ceci est le rôle des opérateurs de croisement et de mutation.

OPÉRATEUR DE CROISEMENT

L'opérateur de croisement permet la création de nouveaux individus selon un processus fort simple. Il permet donc l'échange d'informations entre les chromosomes (individus). Tout d'abord, deux individus, qui forment alors un couple, sont tirés au sein de la nouvelle population issue de la reproduction. Puis un (potentiellement plusieurs) site de croisement est tiré aléatoirement (chiffre entre 1 et l-1). Enfin, selon une probabilité que le croisement s'effectue, les segments finaux (dans le cas d'un seul site de croisement) des deux parents sont alors échangés autour de ce site:

Figure: 57.63 - Exemple d'opérateur de croisement

Cet opérateur permet la création de deux nouveaux individus. Toutefois, un individu sélectionné lors de la reproduction ne subit pas nécessairement l'action d'un croisement. Ce dernier ne s'effectue qu'avec une certaine probabilité. Plus cette probabilité est élevée et plus la population subira de changement.

Quoi qu'il en soit, il se peut que l'action conjointe de la reproduction et du croisement soit insuffisante pour assurer la réussite de l'AG. Ainsi, dans le cas du codage binaire que nous avons choisi jusqu'ici, certaines informations (in extenso: caractères de l'alphabet) peuvent disparaître de la population. Ainsi aucun individu de la population initiale ne contient de 1 en dernière position de la chaîne, et que ce 1 fasse partie de la chaîne optimale à trouver, tous les croisements possibles ne permettront pas de faire apparaître ce 1 initialement inconnu. En codage réel, une telle situation peut arriver si utilisant un opérateur simple de croisement, il se trouvait qu'initialement toute la population soit comprise entre 0 et 40 et que la valeur optimale était de 50. Toutes les combinaisons convexes possibles de chiffres appartenant à l'intervalle [0,40] ne permettront jamais d'aboutir à un chiffre de 50. C'est pour remédier entre autres à ce problème que l'opération de mutation est utilisée.

OPÉRATEUR DE MUTATION

Le rôle de cet opérateur est de modifier aléatoirement, avec une certaine probabilité, la valeur d'un composant de l'individu. Dans le cas du codage binaire, chaque bit est remplacé selon une probabilité par son inverse . C'est ce qui est illustré à la figure ci-dessous. Tout comme plusieurs lieux de croisement peuvent être possibles, nous pouvons très bien admettre qu'une même chaîne puisse subir plusieurs mutations.

Figure: 57.64 - Principe de l'opérateur de mutation

La mutation est traditionnellement considérée comme un opérateur marginal bien qu'elle confère en quelque sorte aux algorithmes génétiques la propriété d'ergodicité (in extenso: tous les points de l'espace de recherche peuvent être atteints). Cet opérateur est d'une grande importance. Il a de fait un double rôle: celui d'effectuer une recherche locale et/ou de sortir d'une trappe (recherche éloignée).

Les opérateurs de l'algorithme génétique sont guidés par un certain nombre de paramètres fixés à l'avance. La valeur de ces paramètres influence la réussite ou non d'un algorithme génétique. Ces paramètres sont les suivants:

- La taille de la population N, et la longueur du codage de chaque individu l (dans le cas de codage binaire). Si N est trop grand, le temps de calcul de l'algorithme peut s'avérer très important, et si N est trop petit, il peut converger trop rapidement vers un mauvais chromosome.

- La probabilité de croisement . Elle dépend de la forme de la fonction de fitness. Son choix est en général heuristique (tout comme pour ). Plus elle est élevée, plus la population subit évidemment de changements importants. Les valeurs généralement admises sont comprises entre 0.5 et 0.9.

- La probabilité de mutation . Ce taux est généralement faible puisqu'un taux élevé risque de conduire à une solution sous-optimale.

Plutôt que de réduire , une autre façon d'éviter que les meilleurs individus soient altérés est d'utiliser la reconduite explicite de l'élite dans une certaine proportion. Ainsi, bien souvent, les meilleurs 5%, par exemple, de la population sont directement reproduits à l'identique, l'opérateur de reproduction ne jouant alors que sur les 95% restant. Cela est appelé une "stratégie élitiste".

Partant du constat que les valeurs des paramètres des différents opérateurs sont elles-mêmes inconnues et ne peuvent être améliorées au fur et à mesure que de manière expérimentale, certains auteurs, tels que Novkovic et Sverko (1997), proposent d'utiliser une sorte de méta-AG: l'un pour trouver l'individu optimal et l'autre pour trouver la valeur optimale des paramètres. Ces deux algorithmes tourneraient alors simultanément ou séquentiellement. Toutefois, il est inévitable que le temps de calcul (la complexité algorithmique) s'alourdisse en conséquence.

Voyons maintenant un exemple d'AG (exemple de Goldberg - 1989). Il consiste à trouver le maximum de la fonction sur l'intervalle [0,31] où x est un entier. La première étape consiste à coder la fonction. Par exemple, nous utilisons un codage binaire de x, la séquence (chromosome) contenant au maximum 5 bits. Ainsi, nous avons , de même . Nous recherchons donc le maximum d'une fonction de fitness (nous choisirons lui-même dans cet exemple simple) dans un espace de 32 valeurs possible de x.

1. Tirage et évaluation de la population initiale

Nous fixons la taille de la population à . Nous tirons donc de façon aléatoire 4 chromosomes sachant qu'un chromosome est composé de 5 bits, et chaque bit dispose d'une probabilité ½ d'avoir une valeur 0 ou 1. Le maximum, (au hasard) 16 est atteint par la deuxième séquence. Voyons comment l'algorithme va tenter d'améliorer ce résultat.

D'abord, nous obtenons le tableau suivant:

N°	Chromosome	Valeur	Fitness f(x)	Pi %
1	00101	5	5	14.3
2	10000	16	16	45.7
3	00010	2	2	5.7
4	01100	12	12	34.3
Total			35	100

Nous tournons donc quatre fois cette roue pour obtenir la séquence suivante:

Nous voyons bien ici le risque que nous aurions à perdre la séquence N° 2 dès le départ... c'est le problème de cette méthode. Elle peut converger moins vite que d'autres. Cependant, le lecteur remarquera que nous avons perdu la séquence N° 3.

Nous passons maintenant à la partie du croisement: les parents sont sélectionnés au hasard. Nous tirons aléatoirement un lieu de croisement ("site" ou "locus") dans la séquence. Le croisement s'opère alors à ce lieu avec une probabilité . Le tableau ci-dessous donne les conséquences de cet opérateur en supposant que les chromosomes 1 et 3, puis 2 et 4 sont appariés et qu'à chaque fois le croisement s'opère (par exemple avec ).

Nous passons maintenant à la partie mutation: dans cet exemple à codage binaire, la mutation est la modification aléatoire occasionnelle (de faible probabilité) de la valeur d'un bit (inversion d'un bit). Nous tirons ainsi pour chaque bit un chiffre aléatoire entre 0 et 1 et si ce chiffre est inférieur à alors la mutation s'opère. Le tableau ci-dessous avec met en évidence ce processus:

Anc. Chr.	Tirage aléa.	Nouveau bit	Nouveau Chr.
10001	15 25 36 04 12	1	10011
00100	26 89 13 48 59	-	00100
01000	32 45 87 22 65	-	01000
10100	47 01 85 62 35	1	11100

Maintenant que la nouvelle population est entièrement créée, nous pouvons à nouveau l'évaluer:

Le maximum est maintenant 28 (N° 4). Nous sommes donc passés de 16 à 28 après une seule génération. Bien sûr, nous devons recommencer la procédure à partir de l'étape de sélection jusqu'à ce que le maximum global, 31, soit obtenu, ou bien qu'un critère d'arrêt ai été satisfait.

- La modélisation du risque et les simulations de Monte-Carlo, H. Thiriez, Éditions Economica,
ISBN10: 2717848223 (221 pages) - Imprimé en 2003

- Recherche opérationnelle et management des entreprise, D. Thiel, Éditions Economica
ISBN10: 2717819304 (190 pages) - Imprimé en 1990

2   0

Notée par 11 visiteur(s) 12345 PageRater 0.5.0 Commentaires: [0]