Rapport de projet : Sélection de caractéristiques par l ...

De
Publié par

Rapport de projet : Sélection de caractéristiques par l'algorithme génétique pour la reconnaissance de formes Dans le cadre du cours : SYS843 : Réseaux de neurones et systèmes flous Remis à : Robert Sabourin Produit par : Richard Naud Le 4 février 2010, Montréal
  • calcul des angles intérieurs, de la distance inter-étoile et de l'aire
  • taille de la base d'entraînement
  • mlp
  • répartition des angles par classe
  • performances des chromosomes du front de pareto
  • analyse de l'art antérieur
  • triplets d'étoiles
  • angle
  • angles
  • répartition des données
  • étoiles
  • étoile
  • etoile
Publié le : mercredi 28 mars 2012
Lecture(s) : 52
Source : edds.etsmtl.ca
Nombre de pages : 42
Voir plus Voir moins






Rapport de projet :
Sélection de caractéristiques par l’algorithme
génétique pour la reconnaissance de formes


Dans le cadre du cours :
SYS843 : Réseaux de neurones et systèmes flous


Remis à :
Robert Sabourin


Produit par :
Richard Naud



Le 4 février 2010, Montréal
Sommaire
Depuis la première apparition de star tracker, apparu l’avènement des technologies
numériques CCD, ces dispositifs n’ont cessé d’évoluer. Junkins a présenté un premier
algorithme de classification de triplet d’étoiles au tout début des années 1980.
Depuis ce temps, plusieurs caractéristiques ont été analysées quant aux triplets
d’étoiles : angles internes, luminosité, distance inter-étoile, aire, périmètre, etc.
De vives critiques ont été portées à la performance des réseaux de neurones (e.g.
Hong). Cependant, il est à noter que la vitesse de classement est reliée intimement
au nombre de caractéristiques en entrée. Il serait donc intéressant de déterminer si
la cardinalité peut être diminuée, et si c’est le cas, quelle est la combinaison de
caractéristiques qui soit la plus discriminante?
L’ouvrage présenté ici présente une synthèse de ces caractéristiques utilisées depuis
Junkins. Ces caractéristiques seront utilisées pour apprendre un réseau de neurones
et procéder à la recherche de la meilleure combinaison de caractéristiques à l’aide
de l’algorithme génétique (étude de sensibilité). L’algorithme génétique (AG) se
basera sur un objectif multicritère, soit le nombre de gènes actifs (caractéristiques
incluses) et la performance de classification du MLP.
ii
Table des matières
Sommaire .................................................................................................................................................ii
Table des illustrations ............................................................................................................................... v
1. Introduction ..................................................................................................................................... 1
2. Analyse de l’art antérieur ................................................................................................................ 3
3. Algorithme de repérage .................................................................................................................. 8
4. Les données ..................................................................................................................................... 9
4.1 Pour le MLP ................................................................................................................................... 9
4.2 Pour l’AG ........................................................................................................................................ 9
4.3 Taille de la base d’entraînement ................................................................................................. 10
5. MLP ................................................................................................................................................ 11
5.1 Fonctionnement du MLP ............................................................................................................. 11
5.2 Paramétrage du MLP ................................................................................................................... 11
5.2.1 Nombre de neurones ........................................................................................................... 11
5.2.2 Déterminer le nombre de couches cachées ......................................................................... 12
5.2.3 Autres paramètres ................................................................................................................ 12
5.2.4 Critère d’arrêt ....................................................................................................................... 12
5.3 Résumé des paramètres du MLP ................................................................................................. 13
6. Algorithme génétique .................................................................................................................... 14
6.1 Initialisation de la population ...................................................................................................... 14
6.2 Fitness .......................................................................................................................................... 15
6.3 Sélection ...................................................................................................................................... 16
6.4 Croisement .................................................................................................................................. 17
6.5 Mutation ...................................................................................................................................... 18
6.6 Résumé des paramètres de l’AG ................................................................................................. 19
7. Attentes/hypothèses – Analyse triviale des données ................................................................... 20
7.1 Attente : Les caractéristiques retenues par l’AG. ........................................................................ 20
7.2 Autres constatations ................................................................................................................... 21
8. Présentation des résultats ............................................................................................................. 23
8.1 Explication : Front de Pareto ....................................................................................................... 23
8.2 Résultats : front de Pareto .......................................................................................................... 23
8.3 Les résultats en généralisation .................................................................................................... 28
9. Discussion ...................................................................................................................................... 30
10. Conclusion ................................................................................................................................. 31
iii
Annexe A ............................................................................................................................................... 32
Bibliographie.......................................................................................................................................... 36


iv
Table des illustrations et tableaux
Figure 1 : Le calcul des angles intérieurs, de la distance inter-étoile et de l’aire (Diaz, 2006) ............... 3
Figure 2 : Les 3 paramètres extraits par Liebe : 2 distances inter-étoiles, ............................. 4
Figure 3: La méthode pour former le vecteur caractéristique avec la grille. (Padgett & Delgado, 1997)
................................................................................................................................................................. 5
Figure 4: Les différents paramètres de base du triplet ........................................................................... 6
Figure 5: Exemple de segmentation ........................................................................................................ 8
Figure 6: Illustration de 10-fold ............................................................................................................... 9
Figure 7: Le MLP; ici à une seule couche cachée. (Demuth & Beale, 1998) .......................................... 11
Figure 8: Exemple de répartition des données : il n'y a pas deux catégories pour représenter une
classe. Ici, la distribution des données pour l'angle A pour les 3 différentes classes. .......................... 12
Figure 9: Apprentissage du MLP ............................................................................................................ 13
Figure 10: Diagramme de flux de l'AG ................................................................................................... 14
Figure 11: Exemple de RWS (Dalton, 2007)........................................................................................... 16
Figure 12: Le croisement (exemple avec un point de croisement) ....................................................... 18
Figure 13: Répartition des données ...................................................................................................... 20
Figure 14: Explication, front de Pareto (PEST, 2010) ............................................................................ 23
Figure 15: Front de Pareto : les meilleurs pour chaque valeur de A ..................................................... 24
Figure 16: Front de Pareto : les 5 meilleurs à chaque valeur de A ........................................................ 25
Figure 17 : Front de Pareto : les 5 meilleurs à chaque valeur de A (ZOOM) ......................................... 26
Figure 18: Performances des chromosomes du front de Pareto, en généralisation ............................ 28
Figure 19 : Répartition des angles par classe (valeurs normalisées) ..................................................... 32
Figure 20: Répartition des distances inter-étoiles par classe (valeurs normalisées) ............................ 33
Figure 21: Répartition du périmètre, de l'aire et de la luminosité de A (valeurs normalisées) ............ 34
Figure 22: Répartition de la luminosité de B et C, ainsi que la somme de la luminosité de A-B-C
(valeurs normalisées) ............................................................................................................................ 35

Tableau 1: Les différents algorithmes et leurs caractéristiques 6
Tableau 2: Résumé des paramètres ...................................................................................................... 13
Tableau 3: Exemple de valeurs pour le fitness (10 individus évalués) .................................................. 15
Tableau 4: Viabilité des approches........................................................................................................ 21
Tableau 5 : Les meilleures solutions ...................................................................................................... 27
Tableau 6: Comparatif des performances en learn et en généralisation des éléments sur le front de
Pareto .................................................................................................................................................... 28


v
1. Introduction

L’ouvrage présenté ici concerne l’implémmeentation d’un algorithme génétique (AG)
pour faire la sélection de caractéristiques. Afin d’amenuiser le nombre de
cccaaarrraaaccctttééérrriiissstttiiiqqquuueeesss nnnéééccceeessssssaaaiiirrreeesss pppooouuurrr fffaaaiiirrreee lllaaa dddiiissscccrrriiimimmiinnnaaatttiiiooonnn dddeee fffooorrrmemmeesss cccooompmmppllleeexxxeee,,, ooouuu
avec une grande cardinalité, l’AG est un outil intéressant. En effet, l’AG permme et
d’étudier la relation entre les différentes caractéristiques et proposer une banque de
donnée allégée.
En analysant l’art antérieur (Mortari & SpSpratling, 2009), il est possible de constater que
pppllluuusssiiieeeuuurrrsss cccaaarrraaaccctttééérrriiissstttiiiqqquuueeesss sssooonnnttt dddiiissspppooonnniiibbbllleeesss pppooouuurrr fffaaaiiirrreee lll’’’iiidddeeennntttiiifffiiicccaaatttiiiooonnn dddeee tttrrriiipppllleeettt
d’étoiles. Cependant, quelle est la memeilleure combinaison de caractéristiques? C’est
ce que l’AG permettra de déterminer.
L’AG sera utilisé pour faire une étude de sensibilité, puisqu’il n’y aura qu’un seul
perceptron mumulticouche avec rétropropagation d’utilisé, plus commmmunément
aaappppppeeelllééé bbbaaaccckkkppprrrooopppaaagggaaatttiiiooonnn mmmuuullltttiiilllaaayyyeeerrr pppeeerrrccceeeppptttrrrooonnn (((MMMLLLPPP)))... LLLeee mmmeeeiiilllllleeeuuurrr MMMLLLPPP ssseeerrraaa
sélectionné parmi 10 différents MLP, par l’erreur en généralisation, repérée à l’aide
de la base de test.
• Avec l'artt antérieur, déterminer toutes les caractéristitiques disponibles
eett qquuii sseerroonntt ccoonntteennuueess ddaannss llaa bbaassee ddee ddoonnnnééee
Données
• Apprentissage de MLP avec toutes les caractéristiques
• Sélection du meilleur réseau MLP créé (appris avec les 10 folds)
MLP
• Analyse de sensibilité en faisantt varier les entrées actti ivées ett en le
présentant t au MLP
AG • Sélectition de la meilleure combinaision d'entrées
• Vis-à-vis les hypotthhèses ett les résultats, discuter des disparités ett
similitudesDiscussion

Le document suivant dresse donc la démarche suivie pour l’obtention d’un MLP, de
l’aspect évolutionnaire et des résultats obtenus. Dans la prochaine section, une
analyse de l’art antérieur, proposant les différentes caractéristiques qui seront
contenues dans les patrons en entrée. La section 3 expose et explicite l’algorithmme e
1 de segmentation utilisé. La section 4 détermine la formation des différentes bases de
données. La section 5 discute de la procédure pour élaborer le MLP. La section 6
explicite la démarche pour l’obtention de la meilleure combinaison. La section 7
expose les attentes avant d’obtenir les résultats (section 8). La section 8 s’attarde à
discuter des disparités et des similitudes entre les résultats et les attentes. Finalement,
une brève conclusion bouclera l’ouvrage.
2
2. Analyse de l’art antérieur

L’article de Mortari et Spratling liste les différentes pratiques pour faire la
reconnaissance de forme d’étoiles. Voici donc un bref résumé des approches
traitées.
Vers 1981, Junkins a proposé un système se basant sur la technologie CCD pour
repérer un triplet d’étoiles, et calculer les angles à l’intérieur de ce triangle. Le
majeur problème étant qu’il y avait un chevauchement de données. Il était donc
nécessaire de connaître la position à priori pour chercher dans un catalogue plus
restreint. Dans un deuxième temps, c’est la méthode que Groth a suggéré en 1986.
Basé sur ce même principe, il calcule le périmètre du triangle, ce qui semble
invariable et discriminant, pour repérer l’identité du triplet dans la base de données.
En 1987, Sasaki quant à lui, a proposé d’utiliser l’aire du triplet d’étoiles et d’inclure la
somme de la luminosité.

Figure 1 : Le calcul des angles intérieurs, de la distance inter-étoile et de l’aire (Diaz, 2006)
En 1989, Van Bezooijen propose d’utiliser davantage les informations données dans
les images, afin d’améliorer la rapidité de recherche et la qualité de la
reconnaissance. Entre autres, il discute de la relation directe entre le nombre
d’étoiles analysées et la quantité d’information.
En 1992, Liebe propose de prendre les deux étoiles les plus rapprochées, et de
déterminer l’angle avec un troisième plus près. Pour ce qui est d’utiliser la luminosité,
il stipule que cette mesure est inutile, puisque la luminosité de chaque étoile est
beaucoup trop près de la valeur de seuillage.
3

Figure 2 : Les 3 paramètres extraits par Liebe : 2 distances inter-étoiles,
ainsi qu’un angle (Liebe, 1992).
En 1993, plutôt que d’utiliser les étoiles les plus rapprochées, qui ont généralement
une luminosité faible, Baldini va à contre courant de Liebe en utilisant la luminosité.
En effet, il utilise l’étoile avec le plus de luminosité. Suivant les recommandations de
Van Bezooijen, qui estime qu’il faut plus d’étoiles pour plus d’informations, il calculera
l’angle de séparation de 5 étoiles. Ultimement, il calcule 12 caractéristiques
(luminosité, angles et distances). Il n’utilise toutefois que 9 caractéristiques pour faire
la première identification.
En 1995, Ketchum utilise aussi un filtrage séquentiel. Cependant, elle utilise la
luminosité de l’étoile la plus brillante pour trouver des ressemblances dans le
voisinage. Par la suite, elle utilise une liste pour la seconde plus brillante étoile. Plus
tard dans la même année, Scholl présente un algorithme plus linéaire qui n’utilise
qu’une seule base de données : elle considère la luminosité pour éviter la
permutation possible entre les angles inter-étoiles.
Plus tard, en 1997, Padgett présente un nouveau type d’algorithme pour la
reconnaissance de constellations. Grossièrement, il utilise une grille de basse
résolution pour construire un vecteur caractéristique. Voir figure 3.

4

Figure 3: La méthode pour former le vecteur caractéristique avec la grille. (Padgett & Delgado, 1997)
Pour sa part, en 2003, Samaan utilise l’angle interne d’un triplet d’étoiles, afin de
limiter les effets de la distorsion de la lentille. C’est somme toute la même approche
que Junkins, en d’autres termes.
Les réseaux de neurones ont refait apparition pour la reconnaissance de triplet en
2000 avec Hong. Il utilise le même vecteur caractéristique que Scholl pour
l’identification des constellations. Le seul problème, c’est qu’il nécessite beaucoup
de calculs (un quart de million de multiplications).
Voici donc un tableau qui résume les principales techniques utilisées, ainsi que la
description sommaire des caractéristiques contenues dans le vecteur à comparer :

5

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.