loadingPage en cours de chargement
    ACCUEIL | TÉLÉCHARGER | QCM | DON | ANNONCES | CHAT | FORUM | LIVRE D'OR | PARTENAIRES | CONTACT | BLOG
 
  Rechercher
  separation
  Introduction
  Arithmétique
  Algèbre
  Analyse
  Géométrie
  Mécanique
  Électrodynamique
  Atomistique
  Cosmologie
  Chimie
  Informatique Théorique
  Maths. Sociales
  Ingénierie
  separation
  Biographies
  Références
  Liens
  separation
  Humour
  Serveur d'exercices
  separation
  Parrains
6 connectés
News News :: Erreur Erreur :: Statistiques Visiteurs :: ClearType ClearType :: Imprimer Imprimer :: Bookmark and Share

Informatique Théorique

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

57. MÉTHODES NUMÉRIQUES (2/2)

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

Table des matières 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!).

Remarque: Il existe plusieurs versions de l'A.C.P. connues sous le nom de "transformée de Karhunen-Loève" ou de "transformée de Hotelling" et qui peuvent aussi bien être appliquées sans programmation V.B.A. dans Microsoft Excel que dans des logiciels spécialisés (où le temps de calcul sera par contre plus bref... et les résultats plus précis aussi...).

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:

individus/variables

equation

equation

equation

Tableau: 57.1  - Représentation-type d'un tableau A.C.P.

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 equation mesurées sont:

- equation: longueur du sépale

- equation: largeur du sépale

- equation: longueur du pétale

Les données sont les suivantes:

Fleur n°

equation

equation

equation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5.1
4.9
4.7
4.6
5.0
7.0
6.4
6.9
5.5
6.5
6.3
5.8
7.1
6.3
6.5

3.5
3.0
3.2
3.1
3.6
3.2
3.2
3.1
2.3
2.8
3.3
2.7
3.0
2.9
3.0

1.4
1.4
1.3
1.5
1.4
4.7
4.5
4.9
4.0
4.6
6.0
5.1
5.9
5.6
5.8

Tableau: 57.2  - Exemple pratique de données tabulaires A.C.P.

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

equation   (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 equation 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:

equation   (57.2)

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

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 equation 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 equation avec equation.

Nous considérons le repère orthonormé equation dans la base canonique equation de equation. 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 equation:

equation   (57.3)

avec:

equation   (57.4)

Nous avons alors pour l'instant sous forme graphique:

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

Nous appelons "matrice centrée" la matrice:

equation   (57.5)

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

Pour notre exemple, nous avons:

equation   (57.6)

et pour la matrice centrée:

equation   (57.7)

et sous forme graphique:

equation
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:

equation   (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:

equation   (57.9)

Si nous notons equation la matrice diagonale suivante:

equation   (57.10)

Nous avons alors:

equation   (57.11)

Remarque: Chaque composante de la matrice Y est donc de moyenne nulle et de variance unitaire (ce qui revient à dire que la norme de la variable centrée réduite est unitaire comme nous allons de suite le démontrer).

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):

equation   (57.12)

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

equation   (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:

equation   (57.14)

Ce qui donne:

equation   (57.15)

Nous avons graphiquement:

equation
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 equation et equation 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):

equation   (57.16)

Les figures suivantes montrent les projections orthogonales dans l'espace de ce nuage de points respectivement dans les plans equation et enfin dans equation 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.

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

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

equation
Figure: 57.6 - Projection des points sur le plan factoriel

Et la vue plane de chacune des projections:

equation
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 equation et equation est donnée par:

equation   (57.17)

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

equation   (57.18)

Nous noterons par la suite:

equation    et    equation   (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 equation.

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 equation (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:

equation   (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:

equation   (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):

equation   (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é:

equation   (57.23)

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

Remarque: Le carré de la distance est pris par anticipation des développements qui vont suivre.

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

equation   (57.24)

Démonstration:

equation   (57.25)

equationC.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 equation auront donc ici comme coordonnées equation.

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 equation qui est parfaitement déterminée par le vecteur equation. Appelons equation la projection orthogonale de equation sur la droite equation. Alors notre problème est de trouver la droite (in extenso le vecteur equation) qui fasse que la somme des carrés des distances entre les points equation soit maximale. Nous écrirons le problème sous la forme d'un problème de programmation quadratique:

equation   (57.26)

Or ici, nous avons:

equation   (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:

equation   (57.28)

Lui-même équivalant donc à:

equation   (57.29)

Résolvons donc ce problème:

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

equation   (57.30)

Par suite, nous avons:

equation   (57.31)

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

equation   (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:

equation   (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 equation !). Alors nous en déduisons la relation suivante qu'il est d'usage d'appeler la "décomposition spectrale":

equation   (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):

equation   (57.35)

Donc:

equation   (57.36)

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

Nous avons donc:

equation   (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"):

equation   (57.38)

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

equation   (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:

equation   (57.40)

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

equation   (57.41)

Soit:

equation   (57.42)

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

equation   (57.43)

soit puisque:

equation    (57.44)

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

equation    (57.45)

toujours avec equation (il est donc relativement aisé de déterminer S avec des logiciels lorsque R et equation 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 equation 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 equation via la relation:

equation   (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):

equation   (57.47)

et donc:

equation   (57.48)

Remarque: Certains logiciels indiquent les poids en % respectifs et cumulés pour chacune des valeurs propres. Ainsi, nous avons dans le cas présent les poids respectifs suivants en % du total:

equation   (57.49)

Donc la première composante explique 66.67% de l'effet. Les deux premières composantes en expliquent 96.15%, etc. C'est ainsi par exemple en finance que l'on va prendre parmi une dizaine ou plus de composantes, seulement celles qui mènent à "expliquer" le 95%.

En ayant les trois valeurs propres, pour déterminer les trois vecteurs propres equation 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:

equation   (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:

equation   (57.51)

qui vérifie donc:

equation   (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):

equation   (57.53)

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

equation   (57.54)

la matrice suivante:

equation   (57.55)

Les coordonnées des projections du nuage de points dans le meilleur plan défini par les vecteurs equation 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é:

equation
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):

equation
equation
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!):

equation
Figure: 57.10 - Plan factoriel donné par Minitab

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

equation   (57.56)

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

equation   (57.57)

Il vient alors:

equation   (57.58)

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

equation   (57.59)

contient aussi les angles entre les vecteurs equation.

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:

 

Feuillus

Résineux

Mixtes

Total par dép.

L'Aisne (A)

106'500

3'380

1'470

111'350

L'Oise (O)

101'700

10'000

0

111'700

La Somme (S)

45'200

4'350

50

49'600

Total

253'400

17'730

1'520

272'650

Tableau: 57.3  - Tableau de contingences (tableau croisé) de l'A.F.C.

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":

 

Feuillus

Résineux

Mixtes

Total par dép.

L'Aisne (A)

39.06%

1.24%

0.54%

40.84%

L'Oise (O)

37.30%

3.67%

0%

40.97%

La Somme (S)

16.58%

1.60%

0.02%

18.19%

Total

92.93%

6.50%

0.56%

100%

Tableau: 57.4 - Tableau des fréquences conjointes de l'A.F.C.

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:

equation   (57.60)

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

equation   (57.61)

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

equation   (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:

 

Feuillus

Résineux

Mixtes

%Région

Aisne

95.6

3.0

1.3

40.8

Oise

91.0

9.0

0.0

41.0

Somme

91.1

8.8

0.1

18.2

Tableau: 57.5  - Transformation du tableau de contingences en pourcents

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:

equation   (57.63)

soit:

equation   (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:

equation   (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:

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

et en activant la fonction Index:

equation
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:

equation   (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:

equation   (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:

equation   (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:

 

Feuillus

Résineux

Mixtes

Total par dép.

L'Aisne (A)

106'500

3'380

1'470

111'350

L'Oise (O)

101'700

10'000

0

111'700

La Somme (S)

45'200

4'350

50

49'600

Total

253'400

17'730

1'520

272'650

Tableau: 57.6  - Tableau de contingences (tableau croisé) de l'A.F.C.

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

equation
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:

 

Feuillus

Résineux

Mixtes

Aisne

=(253'400/272'650)*111'350
=103'488

=(17'730/272'650)*111'350
=7'241

=(1'520/272'650)*111'350
=621

Oise

=(253'400/272'650)*111'700
=103'813

=(17'730/272'650)*111'700
=7'264

=(1'520/272'650)*111'700
=623

Somme

=(253'400/272'650)*49'600
=46'098

=(17'730/272'650)*49'600
=3'225

=(1'520/272'650)*49'600
=276

Total 253'400 17'730 1'520
Tableau: 57.7  - Respect des proportions de l'A.F.C.

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

equation
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:

equation   (57.69)

devient alors:

equation   (57.70)

soit:

equation   (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!!

Remarque: Il existe une autre manière de calculer une AFC en se basant sur une distance euclidienne mais en ayant pris soin au préalable de transformer les données du tableau de contingences de manière particulière et ce pour que le calcul soit identique qu'en lorsqu'on utilise la métrique du Khi-deux.

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:

 

Feuillus

Résineux

Mixtes

Total par dép.

L'Aisne (A)

106'500

3'380

1'470

111'350

L'Oise (O)

101'700

10'000

0

111'700

La Somme (S)

45'200

4'350

50

49'600

Total

253'400

17'730

1'520

272'650

Tableau: 57.8  - Tableau de contingences de l'A.F.C.

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:

 

Feuillus

Résineux

Mixtes

Total par dép.

L'Aisne (A)

103'488

7'241

621

111'350

L'Oise (O)

103'813

7'264

623

111'700

La Somme (S)

46'098

3'225

276

49'600

Total

253'400

17'730

1'520

272'650

Tableau: 57.9  - Tableau de contingences avec effectifs théoriques

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".

Remarque: Le test d'indépendance du Khi-deux est recommandé en analyse sensorielle par la norme ISO 8588-1987 sous le nom de "test A-Non A".

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:

equation   (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 equation 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 equation 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:

equation   (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:

equation   (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:

equation   (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:

equation   (57.76)

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

equation   (57.77)

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

equation   (57.78)

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

Remarque: Pour utiliser ce test à bon escient, il faudrait donc vérifier d'abord que les différences (numérateur) suivent une loi Normale ou que l'ensemble des termes de la somme forment une loi du Khi-deux ou approximativement (asymptotiquement) une loi Normale centrée réduite.

Dans le cadre de notre exemple, nous avons:

equation   (57.79)

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

equation   (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.

Remarque: Dans la pratique il est souvent d'usage de prendre le p-value à 5% pour considérer la probabilité attachée aux écarts observés comme statistiquement significative ou non significative.

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:

equation   (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:

equation   (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:

Ligne/Colonne

c1

c2

...

c4

Total

l1

equation

0

0

0

equation

l2

0

equation

0

0

equation

l3

0

0

equation

0

equation

l4

0

0

0

equation

equation

l5

0

0

0

0

0

Total

equation

equation

equation

equation

N

Tableau: 57.10 - Tableau de contingences rectangulaire

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:

equation   (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 à:

Ligne/Colonne

c1

c2

...

cq

Total

l1

equation

0

...

0

equation

l2

0

equation

...

0

equation

l3

0

0

...

0

equation

...

...

...

...

...

...

lq

0

0

...

equation

equation

Total

equation

equation

...

equation

N

Tableau: 57.11 - Tableau de contingences rectangulaire transformé en carré

É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:

equation   (57.84)

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

equation   (57.85)

et:

equation   (57.86)

Dès lors, il vient:

equation
  (57.87)

Nous définissons alors la valeur suivante:

equation   (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 à:

equation   (57.89)

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

equation   (57.90)

et de nommer "phi de Cramer".

exempleExemple:

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

Projets

Chefs de projet certifiés

Chefs de projet non certifiés

Total

Délais respectés

8

1

9

Délais non respectés

4

5

9

Total

12

6

18

Tableau: 57.12 - Un exemple de tableau de contingences pour le calcul du V de Cramer

avec les effectifs théoriques:

Projets

Chefs de projet certifiés

Chefs de projet non certifiés

Total

Délais respectés

(12/18)*9=6

(6/18)*9=3

9

Délais non respectés

(12/18)*9=6

(6/18)*9=3

9

Total

12

6

18

Tableau: 57.13 - Tableau de contingences de l'exemple avec effectifs théoriques

Nous avons alors:

equation   (57.91)

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

equation   (57.92)

ou avec la p-value:

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

Il vient alors immédiatement:

equation   (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...):

Projets

Chefs de projet certifiés

Chefs de projet non certifiés

Total

Délais respectés

8

1

9

Délais non respectés

4

5

9

Total

12

6

18

Tableau: 57.14 - Tableau de contingences de départ pour l'étude du test exact de Fisher

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):

Projets

Chefs de projet certifiés

Chefs de projet non certifiés

Total

Délais respectés

88.88%

11.12%

50%

Délais non respectés

44.44%

55.56%

50%

Total

66.66%

33.34%

100%

Tableau: 57.15 - Même tableau avec les pourcentages marginaux

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):

Projets

Chefs de projet certifiés

Chefs de projet non certifiés

Total

Délais respectés

(12/18)*9=6

(6/18)*9=3

9

Délais non respectés

(12/18)*9=6

(6/18)*9=3

9

Total

12

6

18

Tableau: 57.16 - Toujours le même tableau mais avec les effectifs théoriques (règle de trois)

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:

Projets

Chefs de projet certifiés

Chefs de projet non certifiés

Total

Délais respectés

a=k

b

a+b=m

Délais non respectés

c

d

c+d

Total

a+c=p

b+d

a+b+c+d=n

Tableau: 57.17 - Représentation algébrique du contenu du tableau

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:

equation   (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:

equation

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:

equation   (57.96)

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

equation   (57.97)

et donc:

equation   (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):

Projets

Chefs de projet certifiés

Chefs de projet non certifiés

Total

Délais respectés

9

0

9

Délais non respectés

3

6

9

Total

12

6

18

=LOI.HYPERGEOMETRIQUE(9;12;9;18)=0.004524887

Projets

Chefs de projet certifiés

Chefs de projet non certifiés

Total

Délais respectés

8

1

9

Délais non respectés

4

5

9

Total

12

6

18

=LOI.HYPERGEOMETRIQUE(8;12;9;18)=0.06108597

Projets

Chefs de projet certifiés

Chefs de projet non certifiés

Total

Délais respectés

7

2

9

Délais non respectés

5

4

9

Total

12

6

18

=LOI.HYPERGEOMETRIQUE(7;12;9;18)=0.244343891

Projets

Chefs de projet certifiés

Chefs de projet non certifiés

Total

Délais respectés

6

3

9

Délais non respectés

6

3

9

Total

12

6

18

=LOI.HYPERGEOMETRIQUE(6;12;9;18)=0.380090498

Projets

Chefs de projet certifiés

Chefs de projet non certifiés

Total

Délais respectés

5

4

9

Délais non respectés

7

2

9

Total

12

6

18

=LOI.HYPERGEOMETRIQUE(5;12;9;18)=0.244343891

Projets

Chefsde projet certifiés

Chefs de projet non certifiés

Total

Délais respectés

4

5

9

Délais non respectés

8

1

9

Total

12

6

18

=LOI.HYPERGEOMETRIQUE(4;12;9;18)=0.061085973

Projets

Chefs de projet certifiés

Chefs de projet non certifiés

Total

Délais respectés

3

6

9

Délais non respectés

9

0

9

Total

12

6

18

=LOI.HYPERGEOMETRIQUE(3;12;9;18)=0.004524887

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

k

Probabilité

9

0.00452489

8

0.06108597

7

0.24434389

6

0.3800905

5

0.24434389

4

0.06108597

3

0.00452489

Somme:

1

Tableau: 57.18 - Probabilités de la loi Hypergéométrique correspondantes à la combinaison

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:

k

Probabilité

9

0.00452489

8

0.06108597

4

0.06108597

3

0.00452489

Somme:

0.131221719

Tableau: 57.19 - Sélection des valeurs d'intérêt

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.

Remarque: Le choix des bornes est discutable avec ce test car si nous choisissons par exemple de nous concentrer sur la probabilité cumulée d'être dans l'intervalle borné fermé de 4 à 8 (donc inclus!), nous aurions un résultat de 99.09% et donc il faudrait considérer que nous sommes dans une configuration extrême à un seuil de 5%. Donc le choix des bornes avec une loi discrète est toujours délicat dans un test contrairement à un test basé sur une loi continue qui ne souffre absolument pas de ce problème. La majorité des logiciels de statistiques que nous connaissons prennent un intervalle borné ouvert pour l'intervalle (ce qui correspond alors premier calcul que nous avons effectué avec la p-value de 13.12%).

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:

 

Bob

Rejeté

Accepté

Total

Alice

Rejeté

3

2

5

Accepté

1

5

6

Total

4

7

11

Tableau: 57.20 - Tableau de contingences dichotomique d'exemple

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):

 

Bob

Rejeté

Accepté

Total

Alice

Rejeté

(4/11)*5=1.82

(7/11)*5=3.18

5

Accepté

(4/11)*6=2.18

(7/11)*6=3.82

6

Total

4

7

11

Tableau: 57.21 - Fréquences théoriques

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

equation   (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:

equation   (57.100)

Ce qui donnera avec notre exemple:

equation   (57.101)

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

equation   (57.102)

Avec:

equation   (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):

Intervalle

Interprétation

entre 0.8 et 1

Très bon accord

entre 0.6 et 0.8

Bon accord

entre 0.4 et 0.6

Accord modéré

entre 0.2 et 0.4

Accord faible

entre 0.0 et 0.2

Accord nul

Tableau: 57.22 - Interprétations d'usage

Il faut cependant être très critique (comme toujours!) en utilisant ce type d'outil. Comprendre sa construction permet aussi d'en identifier les faiblesses et hypothèses qui sont tout à fait discutables.

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

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:

equation   (57.104)

ou de fréquences:

equation   (57.105)

Sachant que:

equation   (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:

equation   (57.107)

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

equation   (57.108)

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

equation   (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...):

equation   (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:

equation   (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:

equation   (57.112)

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

equation   (57.113)

exempleExemple:

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?

 

Oui avant

Non avant

Oui après

55

25

Non après

38

82

Tableau: 57.23 - Sondage avant/après (apparié)

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

equation   (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 equation.

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:

equation   (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.

equation
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 equation pour chaque intervalle (strate) de temps equation où equation (chaque intervalle de temps peut aussi être assimilié à un hôpital différent pour une même étude clinique) qui aura la structure suivante:

 

Morts observés

Survivants observés

Total

Groupe 1
(contrôle)

equation

equation

equation

Groupe 2
(test)

equation

equation

equation

Total

equation

equation

equation

Tableau: 57.24 - Tableau de contingence type pour le test CMH

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

Remarque: Rappelons que si nous avons qu'une seule et unique table et que nous voulons seulement comparer la proportion de survivants ou morts pour les deux groupes, un test des différences des proportions sera appliqué (cf. chapitre de Statistiques). Nous pourrons aussi faire un test du Khi-deux si nous avons toujours qu'une seule et unique table (voir plus haut) et que les conditions ad hoc sont réunies. Ou encore un test exact de Fisher si les conditions du test du Khi-deux ne sont pas réunies. C'est la raison pour laquelle dans les logiciels de statistiques (comme Minitab par exemple), ces trois tests sont disponibles les uns à côté des autres.

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 à:

equation   (57.116)

Donc il faut bien comprendre que par exemple, equation 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:

 

Morts observés

Survivants observés

Total

Contrôle

200

800

1000

Test

280

1'120

1'400

Total

480

1'920

2'400

Tableau: 57.25 - Cas particulier de valeurs observées

Ici, les valeurs attendues donnent:

 

Morts observés

Survivants observés

Contrôle

200

800

Test

280

1'120

Tableau: 57.26 - Valeurs attentues correspondantes au tableau précédent

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:

equation   (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):

equation   (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:

equation   (57.119)

avec pour rappel equation. 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!):

equation   (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):

equation   (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!!!

Remarque: Une question qui revient souvent de ceux qui étudient ce test est de savoir pourquoi nous ne pouvons pas simplement faire la somme de toutes les strates dans une seule et unique table (car ce serait bien plus simple évidemment...)? Eh bien nous ne pouvons mettre réunir les tables dans une une seule car elles ne suivant pas forcémement la même loi (non identiquement distribuées dans le sens que la loi hypergéométrique n'a pas les mêmes paramètres d'une table à l'autre) et malheureusement la loi hypergéométrique n'est pas stable par l'addition.

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:

 

Morts observés

Survivants observés

Total

Contrôle

200

900

1'100

Test

280

1'120

1'400

Total

480

2'020

2'500

Tableau: 57.27 - Exemple particulier de valeurs observées

Nous avons alors pour les valeurs attendues:

 

Morts observés

Survivants observés

Total

Contrôle

211.2

888.8

1'100

Test

268.8

1'131.2

1'400

Total

480

2'020

2'500

Tableau: 57.28 - Valeurs attendues correspondantes au tableau précédent

Soit la différence:

 

Morts observés

Survivants observés

Contrôle

-11.2

11.2

Test

11.2

-11.2

Tableau: 57.29 - Différences entre valeurs attendues et observées

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:

Survivants observés

equation

Tableau: 57.30 - Valeurs attendue de la callule Tests-Survivants

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

equation   (57.122)

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

equation   (57.123)

Maintenant, sous les conditions

equation   (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):

equation   (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:

equation   (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):

equation   (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:

equation   (57.128)

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

equation   (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:

equation   (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:

equation   (57.131)

exempleExemple:

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

A

Morts observés

Survivants observés

Total

Contrôle

288

4

292

Test

400

50

450

Total

688

54

742


B

Morts observés

Survivants observés

Total

Contrôle

300

10

310

Test

450

40

490

Total

750

50

800

Tableau: 57.31 - Test clinique stratifié sur deux niveaux (valeurs observées)

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):

equation   (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):

equation   (57.133)

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

A

Survivants observés

Total

Contrôle

21.25

292

Test

32.75

450

Total

54

742


B

Survivants observés

Total

Contrôle

19.38

310

Test

30.62

490

Total

50

800

Tableau: 57.32 - Valeurs attendues de la colonne d'intérêt du test clinique sur deux niveaux

Ce qui donne pour les différences:

A

Survivants observés

Contrôle

-17.25

Test

17.25


B

Survivants observés

Contrôle

-9.38

Test

9.38

Tableau: 57.33 - Différences valeurs observées-attendues de la colonne d'intérêt

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:

equation   (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%:

equation   (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):

equation   (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:

equation   (57.138)

et:

equation   (57.139)

De même:

equation   (57.140)

L'équation de la chaleur devient alors:

equation   (57.141)

Après réarrangement, nous avons:

equation   (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 equation pour déterminer ensuite toutes les autres valeurs puisque:

equation   (57.143)

et:

equation   (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 equation, une densité de equation et sa conductivité thermique est de equation.

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):

equation   (57.145)

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

equation   (57.146)

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

equation   (57.147)

Soit explicitement et réarrangé:

equation   (57.148)

Soit pour résumer:

equation   (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):

equation   (57.150)

Nous avons alors sur la base de ce principe:

equation   (57.151)

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

equation   (57.152)

equation 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:

equation   (57.153)

nous obtenons:

equation
  (57.154)

ou encore après réarrangement:

equation
  (57.155)

Cette relation montre que si nous connaissons les composantes equation du champ électrique à l'instant t et la composante equation du champ magnétique à l'instant antérieur equation, il est possible de déterminer equation à l'instant equation. 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 equation et equation, equation étant le pas du temps. Il est d'usage dans la littérature spécialisée de noter equation la composante du champ magnétique à l'instant equation.

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

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

equation
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:

equation
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.

Remarque: Attention à ne pas confondre en toute rigueur les notions de classification, segmentation et association. Bien que les deux premiers soient souvent confondus (classification/segmentation) car de nombreux algorithmes font les deux à la fois, la classification est la prédiction d'une ou plusieurs variables discrètes basée sur la valeur des autres champs du jeu de données alors que la segmentation divise les données en groupes d'éléments ayant des propriétés les plus identiques possible. Quant à l'association il est bien évident que de nombreux algorithmes de segmentation montre qui est associé avec quoi mais l'idée à proprement parler de l'association est de quantifier par un scalaire le degré d'association entre deux jeux de données.

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 equation. 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 equation et une valeur equation de cette variable, on trouve que le partitionnement où equation et equation sépare bien les données en deux ensembles disjoints. Ensuite, une des deux parties est à son tour divisée par une valeur de equation 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 equation (revenus en kilo-francs) et equation (surface de leur habitat):

equation
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:

equation
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 equation (Surface) comme premier choix de division avec la valeur de division 19 (nous allons justifier pourquoi!). L'espace equation est maintenant divisé en deux rectangles (il était facile de deviner cette étape de discrimination même sans faire appel aux mathématiques):

equation
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 equation sont (remarquez qu'il s'agit à chaque fois de la moyenne de deux valeurs connexes du tableau):

equation   (57.156)

et ceux pour equation sont:

equation   (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 equation où C est le nombre total de classes à prédire, "l'indice d'impureté de Gini" pour le rectangle A est défini par:

equation   (57.158)

equation 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 equation. Avant la séparation, nous avons:

equation   (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:

equation   (57.160)

Pour la partie inférieure:

equation   (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:

equation   (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:

equation   (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:

equation   (57.164)

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

equation   (57.165)

ce qui est l'impureté maximale.

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

equation   (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 equation (revenus). Ce qui donnera:

equation
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:

equation   (57.167)

L'indice de Gini global est alors:

equation   (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:

equation
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:

equation

avec une impureté totale de 0.2592. Effectivement:

equation   (57.169)

L'indice de Gini global est alors:

equation   (57.170)

À l'étape suivante, nous avons:

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

À l'étape suivante:

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

etc. jusqu'à obtenir au final:

equation
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.

equation
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):

equation
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:

equation
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:

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

et les formules suivantes pour les deux colonnes restantes:

equation
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:

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

et nous avons en lançant le solveur:

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

avec le tableau:

equation
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:

equation
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:

equation
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:

equation
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:

equation
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):

equation

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:

equation
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):

equation

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

equation

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

equation

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:

equation
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):

equation   (57.171)

alors que:

equation   (57.172)

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

equation
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:

equation   (57.173)

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

equation   (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:

equation
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 equation. 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:

equation   (57.175)

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

equation   (57.176)

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

equation
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 equation dont la dimension matricielle est equation. 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 equation. 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:

equation   (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 equationde 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:

equation
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:

equation
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 equation. 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 equation.

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

equation   (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 equation. 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:

equation
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.

Remarque: Si u nréseau de neurones a uniquement une couche masquée et S neurones non interconnectés entre-eux (comme c'est le cas dans la figure ci-dessus), c'est-à-dire indépendants, nous parlons alors de "machine de Boltzmann restreinte" (RBM en anglais pour "Restricted Boltzmann Machine").

Un poids equation 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, equation 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 equation:

equation   (57.179)

Il faut bien sûr prendre en compte que dimensionnellement nous n'avons pas nécessairement equation 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:

equation
  (57.180)

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

equation
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:

equation
Figure: 57.46 - Principe de construction d'un PMC

Cet exemple comporte R entrées et trois couches de neurones comptant respectivement equation 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 equation, 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 equation sont aussi associés à la couche k.

Remarque: Une superposition de RBM forment ce qu'il est d'usage d'appeller un: DBN pour "Deep Beliefs Net".

 

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 equation.

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".

Remarque: Les réseaux multicouches sont beaucoup plus puissants que les réseaux simples à une seule couche bien évidemment. En utilisant deux couches, à condition d'employer une fonction d'activation sigmoïde sur la couche cachée, nous pouvons "entraîner" un réseau à produire une approximation de la plupart des fonctions, avec une précision arbitraire. Sauf dans de rares cas, les réseaux de neurones formels exploitent deux ou trois couches.

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.

exempleExemple:

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:

equation
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:

equation
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):

equation
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:

equation
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:

equation
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):

equation
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:

equation
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:

equation
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:

equation
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:

equation
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:

equation
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:

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

Toujours avec les mêmes formules:

equation
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:

equation
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:

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

avec les options avancées correspondantes:

equation
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 equation, nous supposerons que chaque individu peut être représenté par un mot de longueur fixe l pris dans equation. 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 equation (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:

equation   (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 equation, dite "fonction de fitness" qui à tout equation associe un réel tel que:

equation   (57.182)

si et seulement si equation est mieux adapté au milieu queequation.

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 equation avec equation.

Remarque: La fitness (efficacité) est donc donnée par une fonction à valeurs positives réelles. Dans le cas d'un codage binaire, nous utiliserons souvent une fonction de décodage d qui permettra de passer d'une chaîne binaire à un chiffre à valeur réelle:

equation   (57.183)

La fonction de fitness est alors choisie telle qu'elle transforme cette valeur en valeur positive soit:

equation   (57.184)

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):

equation   (57.185)

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

Ainsi, le chromosome equation vaut trivialement:

equation  (57.186)

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

equation   (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 equation puisque:

equation   (57.188)

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

equation   (57.189)

Petite explicitation:

equation   (57.190)

Posons equation:

equation   (57.191)

Ainsi, avec equation nous avons equation et:

equation   (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 equation, avec equation, l'espace de recherche permis avec equation et equation les bornes inférieures et supérieures. Soit prec la précision (chiffre après la virgule) avec laquelle nous cherchons x. Soit:

equation   (57.193)

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

equation   (57.194)

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

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

equation   (57.195)

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

1. Conversion (base 2 en base 10):

equation   (57.196)

2. Normalisation:

equation   (57.197)

3. Maximisation:

equation   (57.198)

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

equation   (57.199)

Ainsi pour equation, et equation nous retrouvons bien:

equation   (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 equation 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:

equation   (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 equation, 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é equation 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:

equation
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 equation est remplacé selon une probabilité equation par son inverse equation. 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.

equation
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 equation. Elle dépend de la forme de la fonction de fitness. Son choix est en général heuristique (tout comme pour equation). 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 equation. Ce taux est généralement faible puisqu'un taux élevé risque de conduire à une solution sous-optimale.

Plutôt que de réduire equation, 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 equation 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 equation, de même equation. Nous recherchons donc le maximum d'une fonction de fitness (nous choisirons equation 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 à equation. 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:

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

Tableau: 57.35  - Évolution (mutation) des chromosomes

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

Tirage

Chromosome

1

10000

2

01100

3

00101

4

10000

Tableau: 57.36  - Séquence tirage des chromosomes

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é equation. 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 equation).

 

l=2

l=3

Séquences d'origine

100|00

01|100

001|01

10|000

Séquences croisées

10001

01000

00100

10100

Tableau: 57.37  - Croisement des chromosomes

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 à equation alors la mutation s'opère. Le tableau ci-dessous avec equation 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

Tableau: 57.38  - Mutation des chromosomes

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

Chromosome

Valeur

Fitness f(x)

Pi %

1

10011

19

19

32.2

2

00100

4

4

6.8

3

01000

8

8

13.5

4

11100

28

28

47.5

Total

   

59

100

Tableau: 57.39  - Évaluation de la mutation des chromosomes

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.

Remarque: Il est possible de démontrer mathématiquement, ce qui est remarquable !!!, que les portions de chromosomes qui se retrouvent chez les meilleurs individus vont avoir tendance à se reproduire...

En Savoir Plus

- 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


Haut de page

METHODES NUMERIQUES (1/2)FRACTALES


Like2   Dislike0
50.91% sur 100%
Notée par 11 visiteur(s)
12345
Commentaires: [0] 
 
 


W3C - HTMLW3C - CSS Firefox
Ce travail est dans le domaine public
2002-2017 Sciences.ch

Haut de page