Télécharger le fichier pdf d’un mémoire de fin d’études
Procédure de sélection
Notion de distance, de similitude ou de « plus proches voisins »
Comme nous l’avons mentionné précédemment, nous somes amenés à définir la notion de similitude en introduisant une métrique avec la notion de distance. Il en existe plusieurs que l’on peut décliner de la façon suivante :
Étant donné un ensemble de n p points, {x1, x2, x3 ,…, x np }, la distance entre un point q et un Étant donné un ensemble de n p points, {x1, x2, x3,…, x np } (où chacun de ces points est à nd dimension, x i R nd pour i 1, 2,…, n p ) on cherche k points qui sont les « plus proches voisins » d’un point considéré, noté q. Ce point ’appartient pas, bien entendu, à l’ensemble des n p points constituants ses voisins. Considérons une partition de cet ensemble avec q, xi R nd pour 1 i n p . L’approche la plus simple pour déterminer les « plus proches voisins » dans cette partition est de calculer la distance entre le point q et chacun des points de la partition. C’est ce qu’on appelle méthode dans sa dénomination anglo-saxonne « Brute force ». Cette méthode a le principal avantage d’être simple dans sa mise en œu vre mais a ses limites lorsque la partition présente une taille importante en générant des coûts en temps de calcul rapidement exorbitant (Figure 1).
Des solutions intermédiaires existent pour conduire à des temps de calcul raisonnable. Proposé par Cheng et al [7] et utilisé par d’autres chercheurs [8,9,10], l’algorithme « recherche partielle de distance » propose une petite modification de l’algorithme « Brute force ». Lors du calcul de distance D 2 (x, q) , on peut aborder le calcul si la distance partielle, ∑npa 2 définie par i1 (xi, j q j ) pour n pa nd , dépasse la distance maximale pour qu’un point soit accepté comme plus proche voisin (Figure 2).
Toujours dans le but de réduire le temps de recherche du « plus proche voisin », d’autres techniques basées sur des algorithmes d’arborescence de type « branche d’arbre » sont également à noter. Ici, nous présentons deux techniques qui sont dans leurs dénominations anglo-saxonnes Principal Axis Tree (PAT), Depth-Only Axis Tree (DOPAT). Ces dernières basées sur l’établissement du principe d’arborescence conduisent à des séquençages de sélection au travers d’un ou plusieurs critères d’élimination sur l’intégralité de la base de données ou une partition de celle-ci. Le principe repose sur l’estimation d’une distance minimale ou « lower bound » entre un point et un groupe de points appartenant à une p artition avec des critères de rejet défini en fonction de la violation ou non d’un seuil de distance. L’avantage de ce type de méthode est de ne pas scruter l’ensemble des éléments d’une partition mais qu’une partie et d’interrompre en rejetant la totalité de la partition si le critère est violé. Détaillons ces critères de rejet couramment utilisés dans cette approche de sélection avec des algorithmes d’arborescence.
Amélioration de recherche complète:
Le principe de l’amélioration de recherche complèteou Full-Search improvement se base sur le calcul d’une ou plusieurs distances minimales entre un point et un autre point de la base de données dans son intégralité. Le but est de déterminer à l’intérieur de cette partition un hypercube contenant le point considéré et ses « plus proches voisins » [7,11,12,13,14]. Le coût moyen du temps de calcul pour déterminer cet hypercube contenant les « plus proches voisins » est proportionnel à n p soit un ordre O( n p ).
Recherche d’arbre ou Search-Tree:
Cette méthode part sur une division de la base de données en partition et de façon itérative on procède à une subdivision de chaque groupe ainsi constitué. Cette procédure de division en sous-groupe élémentaire se poursuit jusqu’à ce que le nombre d’éléments dans chacun des sous-groupes constitué soit inférieur àun nombre d’éléments préalablement définis. A chaque étape on calcule la distance plus courte du point considéré comme référence avec chacun des ensembles de points de chaque sous-groupe préalablement constitué. Le rejet est déclaré lorsque la valeur de la distance calculée ste supérieure à une distance seuil définie comme distance maximale acceptable pour la définition « plus proches voisins ». Le sous-groupe ne répondant donc pas à ce critère est donc rejetéet ainsi l’ensemble des points constitutifs de ce sous groupe peut être extrait de la base et cela sans avoir à calculer les distances avec chacun des points et le point de référence. Cette méthode deecherche d’arbre permet de s’affranchir du calcul de la valeur de la distance entre le point de référence et chacun des points appartenant à un sous-groupe simplement par une sélection par bloc[15,16,17,18,19,20].
Algorithme de répartition d’axe (Axis-partitioning Algorithm) :
Cet algorithme divise l’ensemble des données de la base en plusieurs hyperrectangles et calcule la distance minimale du point considéré àun point de l’ensemble. Lorsque cette distance est supérieure à un seuil bien déterminé on rejettetous les points de l’hyperrectangle en entier [7,15,16,17,21,22,23,24].
Inégalité du triangleTriangle( Inequality) :
L’inégalité du triangle est utilisée pour calculerla distance minimale entre un point et un autre point ou un groupe de point [25,26,18,19,21,27,28,29,30,31,32,33,34,35,36,37,38,39,40]. L’algorithme est initié par le calcul de la valeur de la distance notée D(a, q) du point de référence et un autre point « a » de la base de donées (le point « a » est considéré comme étant un autre point de référence). S’ensuit le calcul dela valeur de distance D(a, x i ) entre ce nouveau point de référence et chacun des pointsxi de la base de données. L’application de l’inégalité du triangle nous permet d’établir deux valeurs de distance « limite inférieure» entre le point de référence q et chacun des pointsxi de la base de données. Résumons-en le principe.
D(q, x i ) ³ D(a, q) – D(a, x i )(I-4)
et D(q, x i ) ³ D(a, x i ) – D(a, q) (I-5)
Ces deux équations peut être combinées pour ne donner qu’une seule équation :
D(q, x i ) ³ D(a, x i ) – D(a, q) (I-6)
Chacun des points xi de la base de données est rejeté comme n’étant pasun « plus proche voisin » si la valeur de la distance D(q, xi ) entre le point de référence q et le point considéréxi est inférieur à la valeur de D(a, x i ) – D(a, q) défini par la relation de l’inégalité du triangle.
En complément des techniques de sélection que l’onvient de décrire, on peut faire appel à un traitement préalable de la base de données parune réduction de la dimension en utilisant des méthodes de projection sur des sous espaces particuliers définies par les première composante principal de l’échantillon [41,42,43,44,45,46,47].
Autre algorithme de recherche des plus proches voisins rapide : Principal Axis Tree (PAT)
L’arbre d’axes principaux, aussi appeléPrincipal Axis Tree ou encore PAT, permet de diviser l’espace de points de manière efficace en terme de rapidité pour la détermination des « plus proches voisins ». Cette méthode de recherche des « plus proches voisins » a été développée par James Mc Names[4].
L’algorithme proposé permet d’effectuer des recherches sur le voisinage d’un point donné avec un temps de calcul de l’ordre O (log(n p )) et cela même pour des dimensions élevées. Cet algorithme de recherche se base sur un élagage (élimination des parties inutiles) très rapide de l’arbre, grâce à la puissance de son critère d’élimination, tout en limitant l’espace de stockage nécessaire en mémoire. Enfin, à l’intérieur d’une feuille« » donnée, l’algorithme utilise la recherche de la distance partielle pour accélérer ncore les calculs. L’algorithme présente les caractéristiques de temps de calculs et espace mémoire :
• Temps de calcul préparatoire (prétraitement) de O(n p log(n p ))
• Espace de stockage de O (n p )
• Temps de recherche moyen de O (log (n p ))
où np étant le nombre de points présents dans l’espace étudié.
Cet algorithme utilise l’analyse en composante principale (ACP) en construisant l’axe principal des données avec comme objectif de diviser l’ensemble de données en nc régions de même nombre de point. Ce processus se répète pour haquec sous-groupe jusqu’à ce que le nombre de points dans un sous-groupe soit inférieurà nc .
L’axe principal utilisé dans ce travail est construit par la méthode dite «power method » [4,48,49] (Annexe I).
L’algorithme de recherche des plus proches voisins rapide, PAT, comprend deux grandes parties :
– La construction de l’arbre
– La recherche dans l’arbre.
* Construction de l’arbre
La construction de l’arbre commence par la projection de tous les points de la base de données sur un axe principal. Schématiquement, ellese déroule en 6 étapes :
Phase test : Tester que le nombre de points initiaux est suffisant
1. Soient np points à classer dans un nœud, considéré comme nœud racine et nc le nombre de point maximum d’un nœud fils;
2. attribuer les np points au nœud racine. Le nœud racine devient le nœ ud en cours;
3. si le nombre de points assigné au nœud en cours est inférieur à nc , le nœud est dit nœud terminal et son traitement est terminé ; Phase de démarrage
4. sinon, construire l’axe principal pour les points en cours et projeter orthogonalement ces points sur cet axe (ce qui implique que l’on est fait une ACP). On ne projette que sur le premier axe.
5. Partitionner l’ensemble des points projetés sur l’axe en nc régions distinctes de manière à ce que chaque région contienne le mêmenombre de points à une unité près.
6. Attribuer à chaque région ainsi créée une étiquettede nœuds. Il y a en l’occurrence nc nœuds fils distinct composé chacun de la partie en tière de np . Puis une fois cette procédure accomplie on reprend à l’étape 3 pour n c chacun des nouveaux nœuds identifiés comme tels.
On obtient ainsi un arbre pour lequel l’ensemble des points est attribué à la racine. Ces points sont ensuite séparés en différentes régions,chacune correspondant à un fils de nœud racine. On peut, via l’axe principal qui a été sauvé à chaque étape, déterminer dans quelle région doit se situer un point de coordonnées données et oncd savoir à quel nœud fils il est associé. À partir de là, on peut déterminer dans quelle sous région il se trouve et ainsi de suite jusqu’à atteindre une région terminale. Cette région terminale est caractérisée par la présence de peu de points (moins de nc qui est généralement de l’ordre de 2 à une dizaine).
Cet arbre présente au premier abord deux avantages:
1. Aucune région de l’arbre n’est vide, même partiellement
2. L’axe principal sert à tout moment et est une droite, les problèmes sont donc réduits à des problèmes en dimension un * Recherche dans l’arbre
1. L’arbre est analysé depuis sa racine pour déterminedans quelle région (et donc dans quel nœud fils) se trouve le point dont on che rche le voisinage. Cette analyse est aisément effectuée en projetant ledit ointp sur l’axe principal associé au nœud racine et effectuant une recherche dichotomique parmi les limites des nc régions. Ce processus est répété sur le nœud correspondant à la région en question et ainsi de suite jusqu’à atteindre une feuille que nous appellons nœud terminal;
2. un algorithme de recherche de distance partielle est appliqué sur l’ensemble des points appartenant à ce nœud terminal. Rappelons qu ‘il y a, par construction, moins de nc points dans ce nœud;
3. l’algorithme remonte au nœud parent et tente d’éliminer les nœuds frères via le critère d’élimination.
1. Si le critère est satisfait, les nœuds frères sont éliminés et l’analyse remonte au nœud parent;
2. Si le critère n’est pas satisfait, l’algorithme descend dans le nœud frère le plus proche pour une analyse plus approfondie.
Lorsque le nœud racine est complètement analysé (avec un mélange d’exploration et d’élimination), le voisinage est considéré comme nstruitco.
En résumé, on part de la racine, on descend vers lenœud terminal correspondant au point dont on cherche le voisinage et on tente d’éliminerdes sections entières de l’arbre via le critère d’élimination.
Chaque nœud de l’arbre correspond à une région de l’espace. À partir d’informations fournies lors de la construction de l’arbre, le critère d’élimination est capable d’évaluer une distance minimum au-delà de laquelle se trouve n’importe quel point de la région. Si cette distance minimale est trop grande par rapport aux « plus proches voisins » déjà trouvés, la région entière peut être éliminée. Si les nœuds voisins sont encore plus loin, par construction de l’arbre, ces derniers sont eux aussi éliminés.
Sur la figure 3, la distance entre le point q et un point quelconque x situé dans la région 2 est supérieure à la distance entre le point q et l’hyperplan séparant la région 1 de la région. 2Cet hyperplan étant, par construction, perpendiculaire à l’axe principal, la distance peut être calculée rapidement le long de cet axe, soit en dimension 1. La distance dq 2 est donc la distance minimale entre le point q et tous les points contenus dans la région grisée2. Si ce minimum est supérieur à la distance seuil, la région grisée, larégion 5 et au-delà peuvent être éliminés sans avoir à regarder les points présents dans ces régions. Si le test échoue (la distance minimale n’est pas supérieure à la distance seuil), il faut regarder de plus prêt ce qui se passe dans la région grisée (c’est-à-dire descendre dans le nœud corresp ondant).
ANALYSE EN COMPOSANTES PRINCIPALES
Introduction
L’Analyse en Composantes Principales (ACP) est la plus simple et la plus connue des techniques d’analyse de données, qui a pour objectif de remplacer les variables initiales (numériques) par de nouvelles variables (également numériques) dites « Composantes Principales », qui ont les deux propriétés suivantes :
1) Elles peuvent être classées par ordre d’importance décroissante (on sait donner un sens précis à ce terme). Ainsi, les premières Composantes Principales (donc les plus importantes) suffisent pour rendre compte des données avec une perte minimale d’information. En d’autres termes, les données initiales peuvent être remplacées par de nouvelles données dans lesquelles figurent les mêmes individus, mais décrits par desvariables en plus petit nombre.
2) Ces nouvelles variables sont deux à deux décorrélées.
L’ACP peut donc être vue comme une technique de réduction de dimensionnalité.
On attend d’une ACP :
1. Une interprétation des premières Composantes Principales en termes « métier » plus pertinents (approprié, qui convient) que ceux attachés aux variables originales.
2. En conséquence, une interprétation des différenteszones des quelques plans de projection les plus importants.
3. Une aide à la clustering ou clusterisation visuelle des données.
Faire du clustering (ou « typologie », ou « regroupement », ou « classification automatique »), c’est partitionner une base de données en un petit nombre de sous bases, appelées « classes » et telles que :
• Deux individus appartenant à une même classe soient aussi semblables que possible.
• Deux individus appartenant à deux classes différentes soient aussi dissemblables que possible.
En d’autres termes, la clusterisation tente de décomposer le nuage global de points, représentant l’échantillon, en quelques nuages biencompacts et bien différenciés.
Présentation général de l’ACP
Dans la plupart des situations, on dispose de plusieurs observations sur chaque individu constituant la population d’étude. On a donc à prendre en compte p variables par individu, p étant strictement supérieur à un. L’étude séparée de chacune de ces variables donne quelques informations mais est insuffisante car elle laisse de côté les liaisons entre elles, ce qui est pourtant souvent ce que l’on veut étudier. L’analyse en composantes principales est une bonne méthode pour étudier les données multidimensionnelles, lorsque toutes les variables observées sont de type numérique, de préférence dans les mêmes unités et que l’on veut voir s’il y a des liens entre ces variables.
Dans la littérature, on trouve deux approches différentes de l’ACP:
1. Elle peut être présentée comme la recherche d’un sembleen réduit de variables non corrélées, combinaisons linéaires des variables initiales résumant avec précision les données (approche anglo-saxon)
2. Une autre interprétation repose sur la représentation des données initiales à l’aide de nuage de points dans un espace géométrique. L’objectif est alors de trouver des sous-espaces (droite, plan,…) qui représente au mieux le nuage initial.
Interprétation des résultats d’une ACP:
Pour un plan factoriel donné, on regarde la part d’inertie expliquée. On regarde donc la somme des parts d’inertie expliquée par chaque axe.Cette somme des parts d’inertie expliquée par chaque axe peut être interprétée comme un pourcentage de l’information du nuage initial retranscrite par le plan factoriel. Ainsi, un axe expliquant moins de 10% de l’inertie générale est rarement intéressant. Dans toutes les sorties des ogiciels, les axes sont rangés dans l’ordre décroissant d’inertie (en fait dans l’ordre décroissant des valeurs propres obtenues après diagonalisation, mais il y a correspondance), de telle manière que le premier plan factoriel constitué par les deux premiers axes factoriels – soit toujours celui qui est le plus riche en renseignements sur les propriétés du nuage étudié[50, 51, 52, 53,54].
Pour la prévision des trajectoires des cyclones tropicaux, l’ACP est utilisée pour calculer le premier axe principal de la population formée par les cyclones d’un bassin cyclonique. Avec ce premier axe la population peut être subdivisée ne plusieurs régions contenant de même nombre d’individus, selon le principe de PAT. L’ACP est donc un outil utilisé par PAT pour la recherche des analogues. L’ACP est encore utilisé pour réduire le nombre des entrées du réseau d’ondelettes linéaire local de la deuxième partie.
|
Table des matières
INTRODUCTION
PARTIE I
CHAPITRE I : METHODE DE SELECTION
I .1- Procédure de sélection
I.1.1- Notion de distance, de similitude ou de « plus proches voisins »
I.1.2- Autre algorithme de recherche des plus proches voisins rapide : Partial Axis Tree (PAT)
CHAPITRE II : ANALYSE EN COMPOSANTES PRINCIPALES (ACP)
II.1- Introduction
II.2- Présentation général de l’ACP
II.3- Formulation mathématique de l’ACP
II.4- Représentation des individus lors d’une ACP
II.5- Interprétation des résultats d’une ACP
CHAPITRE III : PREVISION DE TRAJECTOIRE D’UN CYCLONE
III.1- Structure des données
III.2- Modèle de prévision
III.3- Recherche des analogues
III.4- Modèle de calcul
III.5- Mesure d’erreur de prévision
III.6- Mesure de performance du modèle
III.7- Coefficient de variations des erreurs de prévisions
III.8- Comparaison de qualité de prévision
III.9 – Résultats des prévisions
III.9.1- Résultats des prévisions sur le bassin de l’Australie
III.9.2- Résultats des prévisions sur le bassin de sud ouest de l’océan indien
III.9.3- Résultats des prévisions sur le bassin atlantique
III.10- Conclusion
PARTIE II
CHAPITRE I : INTRODUCTION
CHAPITRES II : LES RESEAUX DE NEURONES
II.1- Les réseaux de neurones biologiques
II.2- Les réseaux de neurones artificiels
II.2.1- Historique
II.2.2- Présentation des avantages
II.2.3 – Modèle du neurone
II.2.4- Fonction d’activation
II.2.4.a- La fonction sigmoïde
II.2.4.b- Les fonctions radiales de base
II.2.5- Modélisations des réseaux
II.2.5.a- Réseaux de neurones feedforward
II.2.5.b- Réseaux récurrents
II.2.5.c- Fonctionnement d’un réseau de neurone artificiel
II.3- Apprentissage des réseaux de neurones artificiels de type feedforward
II.3.1- Apprentissage supervisé
II.3.2- Apprentissage renforcé
II.3.3- Apprentissage non supervisé
CHAPITRE III : LES RESEAUX D’ONDELETTES
III.1- Ondelette
III.2- Ondelettes multidimensionnelles
III.3- Réseau d’ondelettes
III.3.1- Réseau d’ondelettes à une dimension
III.3.2- Réseau d’ondelettes multidimensionnel
III.3.3- Structure d’un réseau d’ondelettes
III.3.4- Type de foction d’ondelette utilisé dans le réseau d’ondelettes
III.3.5- Initialisation des paramètres du réseau d’ondelettes
III.4- Réseau d’ondelettes linéaire local
CHAPITRE IV : PARTICLE SWARM OPTIMIZATION – OPTIMISATION PAR ESSAIM DE PARTICULES
IV.1- Introduction
IV.2- Algorithme
IV.3- Paramètres de l’algorithme
IV.3.1- Vitesse maximale
IV.3.2- Facteur d’inertie
IV.4- Voisinage
CHAPITRE V : PREVISION DES TRAJECTOIRES DES CYCLONES
V.1- Calcul
V.2- Résultats
V.2.1- Résultats des prévisions sur le bassin de l’Australie
V.2.2- Résultats des prévisions sur le bassin de sud ouest de l’océan indien
V.2.3- Résultats des prévisions sur le bassin atlantique
V.3- Conclusion
CONCLUSION GENERALE
REFERENCES BIBLIOGRAPHIQUES
ANNEXE
A N N E X E I : Organigramme de construction de l’axe principal par la méthode « power method »
ANNEXE II : Organigramme de “ Principal Axis Tree “
Télécharger le rapport complet
