Détection d'obstacles par le sonar d'un sous-marin : spectrogramme, arbres de décision et forêts aléatoires
Afficher ou masquer la section
Le sujet d'informatique CCINP PSI 2020 cherche à distinguer une roche d'un objet métallique à partir des mesures d'un sonar. Après une introduction, la partie II traite le signal (signal modulé en fréquence, transformée de Fourier locale, enveloppe normalisée, lecture d'un fichier de données) et la partie III construit des arbres de décision avec l'indice de Gini, puis une forêt aléatoire.
1Partie I : introductionPrésentation du problème de classification des obstacles et des algorithmes d'intelligence artificielle étudiés.
2Partie II : analyse des donnéesCréation du vecteur des instants et du signal émis, spectrogramme par transformée de Fourier locale, intégration numérique et normalisation de l'enveloppe, lecture d'un fichier et taille mémoire des données (Q1 à Q9).
3Partie III : méthode des forêts aléatoiresReprésentation d'un arbre de décision par des listes, séparation des données avec l'indice de Gini, construction récursive de l'arbre, puis prédiction par vote majoritaire sur plusieurs arbres (Q10 à Q20).
Accessible. Le jury indique que l'épreuve a été bien réussie par la majorité des candidats, avec peu d'erreurs de syntaxe Python.
Deux tiers des copies environ (moyenne ± écart-type)
Votre note sur 20 à ce sujet, en conditions de concours.
Source : document officiel du concours, épreuve du 4 juillet 2020. Notes publiées par le concours (après harmonisation le cas échéant). Courbe : estimation par une loi normale.
Ce qu'a observé le jury
6 erreurs relevées
Confusion entre arange et linspace · Initialisation du tableau renvoyé · Arguments de la fonction de transformée de Fourier
Afficher ou masquer la section
L'épreuve parcourait une large part du programme d'informatique de CPGE et a été bien réussie par la majorité des candidats. Le document réponse, introduit cette session, a été globalement bien utilisé. Les erreurs récurrentes portent sur les indices décalés de un, les variables non définies, la représentation des nombres et la confusion entre listes et tableaux numpy.
Les erreurs les plus sanctionnées
1
Confusion entre arange et linspaceQ1
La création du tableau des instants a souvent échoué : pas et nombre de valeurs confondus, dernière valeur incluse ou exclue mal gérée.
« confusion entre arange et linspace (pas versus nombre de valeurs, dernière valeur exclue versus incluse par défaut) »
2
Initialisation du tableau renvoyéQ2
Des candidats ajoutent des éléments à un array vide ou ne remplissent pas toutes les cases d'un empty(N) ; le jury préfère zeros(). La définition du signal sur deux intervalles est aussi souvent oubliée.
3
Arguments de la fonction de transformée de FourierQ3
Presque aucun candidat ne passe les bons arguments, en particulier le premier ; beaucoup appliquent la transformée au vecteur des temps.
« pratiquement aucun candidat ne met les bons arguments dans la fonction et notamment le premier argument »
4
Normalisation et complexitéQ7
Peu de candidats trouvent la fonction affine à appliquer ; le calcul du minimum et du maximum laissé dans la boucle alourdit fortement la complexité.
5
Taille mémoire d'un flottantQ9
La plupart ignorent la place occupée par un réel en double précision et confondent bits et octets.
« une grande majorité des candidats ne connaissent pas l'espace nécessaire pour stocker un réel en double précision »
6
Récursivité et tirage sans répétitionQ12, Q16, Q18
Le test d'absence d'une valeur déjà tirée est souvent mal écrit alors que « in » suffisait ; dans la fonction récursive de prédiction, les return des appels récursifs sont souvent oubliés.
Ce qui a été bien réussi
Peu d'erreurs de syntaxe Python ont été relevées.
Les questions Q5, Q10, Q17 et Q20 sont bien traitées, ainsi que Q6 et Q13 dans l'ensemble.
Les rares candidats ayant abordé Q19 l'ont en général bien réussie.
Conseils du jury
Utiliser une encre d'une autre couleur que le noir pour compléter le code sur le document réponse.
Préparer la réponse au brouillon, choisir des noms de variables explicites et soigner l'indentation.
Ne pas confondre l'indice et l'élément dans une boucle for.
Connaître les bases de la représentation des informations en mémoire, qui feront toujours l'objet de questions.
Prendre le temps de comprendre ce que doit faire une fonction avant de la compléter.
Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.
ÉPREUVE MUTUALISÉE AVEC E3A-POLYTECH
ÉPREUVE SPÉCIFIQUE - FILIÈRE PSI
INFORMATIQUE
Mercredi 6 mai : 8 h-11 h
N.B. : le candidat attachera la plus grande importance à la clarté, à la précision et à la concision de la rédaction. Si un candidat est amené à repérer ce qui peut lui sembler être une erreur d'énoncé, il le signalera sur sa copie et devra poursuivre sa composition en expliquant les raisons des initiatives qu'il a été amené à prendre.
RAPPEL DES CONSIGNES
Utiliser uniquement un stylo noir ou bleu foncé non effaçable pour la rédaction de votre composition ; d'autres couleurs, excepté le vert, peuvent être utilisées, mais exclusivement pour les schémas et la mise en évidence des résultats.
Ne pas utiliser de correcteur.
Écrire le mot FIN à la fin de votre composition.
Les calculatrices sont interdites
Le sujet est composé de trois parties indépendantes.
L'épreuve est à traiter en langage Python. La syntaxe de Python est rappelée en Annexe, page 8 du Document Réponse.
Les différents algorithmes doivent être rendus dans leur forme définitive sur le document réponse dans l'espace réservé à cet effet en respectant les éléments de syntaxe du langage (les brouillons ne sont pas acceptés).
La réponse ne doit pas se cantonner à la rédaction de l'algorithme sans explication, les programmes doivent être expliqués et commentés.
Énoncé : page 1 à page 12
Document réponse et Annexe : page 1 à page 8
Seul le Document Réponse est à rendre.
Détection d'obstacles par un sonar de sous-marin
Partie I - Introduction
Pour détecter des obstacles sous l'eau, en l'absence de visuel direct, les sous-marins sont équipés de sonars. L'onde ultrasonore émise par le sonar est réfléchie sur l'obstacle et le signal en retour est détecté et analysé pour obtenir la distance de l'obstacle au sous-marin. Une des difficultés rencontrée lors de l'analyse du signal de retour est de déterminer si l'obstacle est une roche ou un objet métallique donc un danger potentiel.
Il existe des techniques d'aide à la décision faisant partie des algorithmes dits d'Intelligence Artificielle permettant d'analyser le signal de retour d'un sonar et de déterminer de quelle nature est l'obstacle.
Objectif
L'objectif du travail proposé est de découvrir des algorithmes d'Intelligence Artificielle en s'appuyant sur ce problème de détection d'obstacle. À partir d'une base de données comportant des mesures de sonar réalisées sur des roches et sur du métal, il s'agira d'être capable de déterminer à partir d'une mesure inconnue, si l'objet situé devant le sous marin est une roche ou un objet métallique.
Le sujet abordera les points suivants :
analyse et représentation des données,
construction des arbres de décisions,
prédiction par la méthode «random forest».
Dans tout le sujet, il sera supposé que les modules python numpy, matplotlib.pyplot sont déjà importés dans le programme (cf. Annexe), on utilisera donc les fonctions de ces modules sans préciser l'origine de celles-ci. Lorsqu'il est demandé de définir des vecteurs ou des matrices, il est demandé d'utiliser le type array du module numpy.
Partie II - Analyse des données
II. 1 - Présentation
Les données utilisées pour l'apprentissage de l'algorithme ont été obtenues suite à une campagne d'essais réalisés dans l'océan à partir des mesures d'un sonar situé à environ 10 mètres d'un cylindre métallique ou d'un cylindre en pierre pour différentes incidences angulaires du signal émis par le sonar.
Le signal émis par le sonar et le signal reçu sont numériques et représentés avec N valeurs sur une durée totale T_f. Les variables Tf et N sont définies dans le programme.
Q1. Écrire une instruction permettant de définir la variable temps, vecteur décrivant les instants de 0 à T_f uniformément répartis (exclu).
Le signal émis par le sonar (appelé CHIRP) est un signal modulé en fréquence linéairement en partant d'une fréquence f_0 jusqu'à la fréquence f_1 (figure 1), ceci permet d'atteindre de grandes portées et une bonne réception du signal lors du retour de l'onde malgré les bruits de mesure.
L'expression du signal émis est la suivante :
{e(t) = E_0 sin(2πf_e(t)t), si 0 ≤ t ≤ T; 0, si T < t < T_f
avec f_e(t) = f_0 + t/TΔf_e où f_0 est la fréquence porteuse et Δf_e la bande de fréquences de modulation.
Figure 1 - Exemple de signal émis de type CHIRP
Q2. Écrire une fonction chirp(temps, f ⊕, Deltafe, T, E ⊕ ) qui renvoie un vecteur de taille N correspondant au signal émis défini sur [ 0, T_f [ avec temps le vecteur défini précédemment et f 0 , Deltafe, T, E0 les paramètres intervenant dans le système d'équations définissant e(t).
La réponse obtenue après réflexion sur un obstacle est de la forme donnée sur la figure 2.
Figure 2 - Exemple de signal de retour (extrait de travaux de recherche)
Pour analyser ce signal et notamment savoir sur quel type de support a eu lieu la réflexion, une transformation de Fourier (discrète) est pertinente car elle permet de connaître les composantes fréquentielles importantes dans le signal. Cependant, compte tenu des bruits et de la localisation du signal de retour, on préfère utiliser une transformation de Fourier dite locale qui consiste à appliquer la transformée de Fourier non pas sur tout l'intervalle de temps d'étude mais uniquement sur plusieurs courtes périodes temporelles qui se chevauchent.
Description de l'algorithme de transformée de Fourier locale
On note s_r(t) le signal temporel de retour mesuré après réflexion sur l'obstacle. Le signal numérique correspondant est représenté par un vecteur de taille N noté s . La période d'échantillonnage de ce signal est t_e = (T_f)/N.
Pour obtenir les intervalles de temps utilisés dans la méthode, on sélectionne un instant particulier ( τ ) et n < N instants. Ces instants seront répartis autour de la valeur τ(n//2 avant et n//2 après). Pour extraire la portion de signal intéressante, on multiplie s_r(t) par une fonction particulière qui peut être un simple créneau centré autour de τ ou des fonctions mathématiquement plus intéressantes comme celle de la figure 3 (fonction de Hamming).
En appliquant la transformée de Fourier (FFT) au signal obtenu, on extrait un vecteur de fréquences de taille n_f = N//(n//2) et un vecteur de nombres complexes (de taille n_f ) dont le module correspond au spectre de Fourier. On répète le processus en décalant l'intervalle de temps sélectionné de n//2 valeurs (pour un chevauchement de 50% ).
Finalement, on obtient alors une fonction discrète de deux variables S(f, t) où f est un vecteur de fréquences de taille n_f (le même pour toutes les fenêtres), t est un vecteur contenant les valeurs de τ retenues de taille n_f et S l'ensemble des modules pour chaque fréquence et chaque instant τ. Le tracé du module de S en fonction des deux vecteurs f et t est appelé spectrogramme (figure 4).
Figure 3 - Principe de la transformée de Fourier locale d'un signal : sélection d'une partie du signal autour de t = τ en multipliant le signal à analyser par une fonction de Hamming
La fonction stft utilisée pour réaliser la transformée de Fourier locale est disponible dans le module scipy.signal. Un extrait de la documentation est proposé sur la page suivante.
Q3. À partir des indications précédentes et de la documentation, donner l'instruction permettant de stocker dans les variables notées f, t, S le résultat de la transformée de Fourier discrète du signal numérique s en précisant bien les arguments retenus, sachant que l'on souhaite un recouvrement de 50%, que le nombre de valeurs retenues autour de chaque instant est n et qu'on choisit une fenêtre de type Hamming. Donner également la taille des grandeurs f, t, S obtenues en retour en fonction de n et N.
Description de la fonction stft
scipy.signal.stft(x, fs=1.0, window='hann', nperseg=256, noverlap=None)
Compute the Short Time Fourier Transform (STFT).
STFTs can be used as a way of quantifying the change of a nonstationary
signal's frequency and phase content over time.
Parameters:
x : array_like
Time series of measurement values.
fs : float
Sampling frequency of the x time series. This value is used to define
array of frequencies which length is equal to x length // (nperseg//2)
. Defaults to 1.0.
window : str
Desired window to use. If window is a string, it is passed to get_window
to generate the window values. Available windows are : boxcar, triang,
hamming, hann, kaiser... Defaults to a Hann window.
nperseg : int
Length of each window. Defaults to 256.
noverlap : int, optional
Number of points to overlap between segments.
If None, noverlap = nperseg // 2.
Returns:
f : ndarray
Array of sample frequencies.
t : ndarray
Array of segment times which length is equal to x length // (nperseg//2).
S : ndarray
STFT of x.
On teste la fonction sur le signal à analyser de la figure 3. Ce signal, qui a la même allure qu'une mesure expérimentale, a été construit à partir d'une fonction mathématique à laquelle un bruit a été rajouté.
Les spectrogrammes obtenus sont donnés sur la figure 4.
Q4. Commenter l'intérêt du spectrogramme pour analyser le contenu fréquentiel du signal d'origine et analyser succinctement la répartition obtenue entre f et t.
Figure 4 - Spectrogramme d'un signal bruité et d'un signal non bruité
Pour pouvoir comparer les résultats d'essais entre eux, il est préférable d'extraire l'enveloppe des spectrogrammes. Pour cela, on réalise une intégration numérique du signal tracé sur le spectrogramme : P(η) = ∫_t∫_f S(t, f)w(t, f, η)df dt avec S(t, f) la fonction issue de l'analyse par transformée de Fourier locale et w une fonction représentant un ensemble de fenêtres localisées autour de la zone d'intérêt dans le spectrogramme (de tailles ΔT et Δf ). η est un entier variant de 0 à m − 1, permettant d'obtenir un ensemble fini de m valeurs de l'enveloppe ( m est un paramètre de l'analyse qui sera choisi par la suite).
On note t_η = (ΔT)/2 + ηT et f_η = (Δf)/2 + ηΔf.
La fonction w(t, f, η) est définie par :
{w(t, f, η) = 1, si − ΔT/2 < t − t_η < ΔT/2 et − Δf/2 < f − f_η < Δf/2; w(t, f, η) = 0, sinon
Q5. Écrire une fonction w(t, f, eta) qui renvoie 1 ou 0 en fonction des valeurs de t, f et eta = η. On supposera que les paramètres ΔT, T, et Δf sont connus et utilisables directement dans la fonction (variables globales notées DT, T et Df).
On note t_i les valeurs du temps, i variant de 0 à n_f − 1 et f_j les valeurs de fréquences, j variant de 0 à n_f − 1 avec t_i = i dt, f_j = j df où dt et df sont respectivement des pas de temps et de fréquence. La fonction à intégrer est notée S_(ij) avec i et j variant respectivement de 0 à n_f − 1 et 0 à n_f − 1. Pour intégrer numériquement la fonction discrète S_(ij), on utilise la formule : P_η = ∑_i∑_j p_(ij)S_(ij)w(t_i, f_j, η)df dt avec p_(ij) poids (valeurs connues).
Q6. Écrire une fonction enveloppe(eta, S,p,dt,df) qui renvoie la valeur de l'intégrale numérique en fonction de la valeur de eta = η. On supposera connus les pas dt et df. Le tableau numpy S contient les valeurs de la fonction discrète S_(ij) et le tableau numpy p contient les valeurs des poids p_(ij).
Pour chaque expérience (fonction de l'obstacle et de l'angle d'incidence de l'onde émise), on construit cette enveloppe. En prenant m = 60, on obient 60 valeurs qui caractérisent une expérience. Ces valeurs seront utilisées dans les algorithmes de prédiction décrits dans la suite pour classer une nouvelle mesure.
De manière à pouvoir comparer les enveloppes, on normalise le vecteur P_η en ramenant le maximum à 1 et le minimum à 0 par une fonction affine.
Q7. Proposer une fonction normalisation(P) qui renvoie un vecteur de m valeurs comprises entre 0 et 1 . On pourra utiliser les fonctions min(x) et max(x) avec x un vecteur.
II. 2 - Lecture des données
Les données à utiliser sont stockées dans un fichier texte où une ligne représente l'ensemble des valeurs associées à une expérience. Une expérience est caractérisée par 60 valeurs issues du traitement de la mesure (chaque valeur est un nombre réel entre 0 et 1 ) et un caractère donnant le groupe d'appartenance (un caractère M pour métal et R pour roche).
Premières lignes partielles du fichier, les points de suspension permettent de cacher les 56 données intermédiaires pour chaque ligne :
On souhaite lire ce fichier de données pour créer un tableau de type liste contenant des listes. Pour la dernière colonne, le caractère " R ", respectivement " M ", sera converti en la valeur 0.0 , respectivement 1.0. La fonction suivante permet de lire le fichier de données et renvoie les données au format souhaité.
def lire_donnees(nom_fichier):
donnees = []
with open (nom_fichier, 'r') as fichier
for ligne in fichier:
a = ligne.split(',')
b = []
for i in range(len(a)-1):
b.append(float(a[i]))
if a[-1].strip() == "R":
b.append(0.0)
else :
b.append(1.0)
donnees.append(b)
return donnees
Q8. À partir de la fonction lire_donnees, préciser la valeur de la variable donnees en se limitant aux deux premières lignes lues. Les fonctions usuelles sur les fichiers et chaînes de caractères et leur documentation sont rappelées dans l'Annexe.
Le fichier de données comporte n_x = 208 enregistrements.
Q9. Donner la taille mémoire minimale nécessaire en octets pour stocker les données. On rappelle que Python stocke les nombres réels en format double précision par défaut.
Partie III - Méthode des forêts aléatoires
La méthode des forêts aléatoires est une amélioration de la méthode des arbres de décision.
III. 1 - Arbre de décision
Un arbre de décision est une représentation qui permet de séparer les données en deux groupes, appelés nœuds de l'arbre, selon un critère objectif. Les sous-groupes (ou nœuds) sont ensuite séparés en deux selon un autre critère, puis on sépare à nouveau jusqu'à obtenir un nœud terminal appelé feuille.
Pour classer une nouvelle donnée, il suffit ensuite de suivre les différentes règles issues de la construction de l'arbre pour savoir dans quelle catégorie la placer.
Le principal problème rencontré est qu'un arbre de décision peut vite conduire à du surapprentissage si l'on tente de décrire parfaitement le jeu de données initial avec une donnée unique par feuille. Dans ce cas, il ne sera pas forcément possible de classer une nouvelle donnée. Il est donc souvent nécessaire d'arrêter la construction à un nombre maximal de séparations, on parle d'élaguer l'arbre.
Illustrons ces notions sur le jeu de données aléatoires suivant, la dernière colonne représentant le groupe d'appartenance :
(a) Arbre de décision associé au jeu de données précédent
(b) Exemple d'arbre de décision pour illustrer la représentation en Python
Figure 5 - Différents arbres de décision
Un arbre est représenté sur la figure 5(a). Cet arbre est composé de nœuds représentés par des cercles, des liens représentés par des flèches avec condition et des feuilles représentées par des rectangles composés de 1 ou de 0 .
Un nœud contient l'indice d'une des colonnes du tableau de données (les colonnes sont numérotées à partir de 0 ). Les liens permettent de parcourir l'arbre de décision. Pour une ligne du tableau de données, on prend la valeur de la colonne d'indice indiqué par le nœud et on évalue la condition du lien. Si la valeur est strictement plus petite que la valeur indiquée sur le lien, on descend vers la gauche, sinon on va vers la droite. Lorsqu'on ne peut aller plus loin en descendant, on aboutit à une feuille représentant le type d'obstacle détecté ( 0 pour roche, 1 pour métal).
En Python, on choisit de représenter un nœud par une liste de 4 éléments [ind, val, gauche, droite]. Le premier élément est l'indice de la colonne du tableau de données, le deuxième élément est la valeur permettant de faire le test pour descendre à droite ou à gauche. Le troisième élément est :
soit le nœud de la branche de gauche (représentée elle-même par une structure de type nœud)
soit la valeur terminale 0 ou 1 pour définir le groupe.
De même, le quatrième élément est soit le nœud de la branche de droite, soit la valeur terminale.
Par exemple, l'arbre de la figure 5(b) sera représenté en Python par la liste suivante : [2, 0.39, [6, 0.19, 1, 0], 1].
Q10. Donner la représentation en Python de l'arbre défini sur la figure 5(a).
Soit une donnée non classée a = [0.5, 0.2, 0.7, 0.4, 0.9, 0.25, 0.7, 0.7, 0.9, 0.2].
Q11. Déterminer, en justifiant, dans quel groupe cette donnée sera classée en utilisant l'arbre de la figure 5(a). Expliquer le chemin parcouru dans l'arbre.
III. 2 - Construction d'un arbre
Pour construire l'arbre, la principale question à laquelle il faut répondre est de savoir comment séparer les données à chaque itération. Il existe différentes méthodes, souvent statistiques, qui permettent de réaliser cette séparation. Nous allons ici étudier l'algorithme CART («classification and regression trees »), qui se base sur une grandeur appelée indice de concentration de Gini qui sera définie par la suite. Cet indicateur permettra de choisir la colonne et la valeur pour faire la séparation.
La fonction suivante permet de séparer les données en deux groupes en utilisant l'indice de concentration de Gini. Nous allons détailler dans la suite les fonctions intervenant dans cette fonction. Pour rappel, la variable donnees est un tableau constitué de n_x lignes et m + 1 colonnes, la dernière colonne contient la classe à laquelle appartient la ligne (qui correspond à une expérience).
def separe(donnees, p_var):
#Initialisation des parametres
b_ind,b_val,b_gini = inf, inf, inf
b_g, b_d = [],[]
m = len(donnees[0])-1
#extractions d'indices aléatoires
ind_var = indices_aleatoires(m,p_var)
for ind in ind_var:
for ligne in donnees:
#séparation des données en deux groupes
[gauche,droite]=test_separation(ind,ligne[ind],donnees)
gini = Gini_groupes([gauche,droite])
if gini < b_gini:
b_ind,b_val,b_gini = ind,ligne[ind],gini
b_g,b_d = gauche,droite
return [b_ind, b_val, b_g, b_d]
La fonction renvoie l'indice de la colonne et la valeur retenus pour faire le test de séparation ainsi que les deux groupes gauche et droite (la structure identique à la valeur renvoyée par la fonction lire_donnees rappelée avant la question Q8).
Q12. Écrire une fonction indices_aleatoires(m,p_var) qui prend en arguments le nombre m correspondant au nombre de colonnes disponibles et p_var un nombre permettant de tirer aléatoirement p_(var) nombres parmi la liste des numéros de colonnes ( p_var < m ) et qui renvoie une liste de taille p_(var) contenant les numéros de colonnes tirés aléatoirement. Un numéro de colonne ne doit apparaître qu'une seule fois dans cette liste.
On utilisera la fonction randrange (p) qui renvoie un entier aléatoirement entre 0 et p − 1. Par exemple, si on choisit p_var = 4 avec m = 60, on pourrait obtenir la liste d'indices aléatoires suivante [10, 50, 3, 24].
Q13. Écrire une fonction [gauche,droite]=test_separation(ind, val, donnees) qui prend en argument ind un numéro de colonne, val une valeur permettant de séparer les données et donnees le tableau contenant les données. Cette fonction renvoie une liste de deux éléments du même type que donnees : les lignes, dont la valeur de la colonne ind est inférieure strictement à val, sont stockées dans le groupe gauche et les autres dans le groupe droite. Les groupes gauche ou droite peuvent être vides.
L'indice de concentration de Gini pour un jeu de données d'un groupe gr (noté Gini_(gr) ) est calculé à l'aide de la formule suivante: Gini _(gr) = ∑_(i = 0)^(k − 1)1 − p_i^2 où k est le nombre de classes possibles, ici 2 (0 ou 1), p_i est la proportion des éléments du jeu de données appartenant à la classe i. On rappelle que la valeur de la classe est contenue dans la dernière colonne du tableau de données.
Pour obtenir l'indice de concentration de Gini total pour les deux groupes (gauche et droite), on réalise une somme des deux indices de concentration Gini _(gr) pondérée d'un coefficient de taille relative : taille du jeu de données du groupe divisé par le nombre de données des deux groupes (nombre de données totales).
Q14. Compléter les instructions notées 1 à 5 de la fonction Gini_groupes donnée sur le document réponse qui prend en argument groupes la liste contenant les deux groupes à tester et qui renvoie l'indice de concentration de Gini.
Lors de la construction de l'arbre, on peut fixer plusieurs critères permettant d'arrêter la construction en calculant une feuille :
premier critère : quand le nombre de données à séparer est inférieur à une valeur que l'on notera taille_min,
deuxième critère : quand le nombre de séparations a atteint une valeur maximale notée sep_max.
On donne à la feuille associée au jeu de données restant en fin de séparation la valeur du groupe majoritaire. Si la majorité des données est dans la classe 0 (roche) alors la feuille prendra la valeur 0 , sinon elle prendra la valeur 1 (métal).
Q15. Écrire une fonction feuille(data) qui prend en argument un jeu de données data et qui renvoie la valeur de la classe majoritaire. La variable data est du même format que la variable donnees.
La fonction permettant de lancer la construction de l'arbre est la suivante :
data_train des données dont on connaît déjà la classe;
sep_max : le nombre de séparations maximales pouvant être effectuées avant de placer une feuille;
taille_min : le nombre de données minimales sous lequel on impose de mettre une feuille plutôt que de séparer les données en deux;
p_var : le nombre de valeurs à tirer aléatoirement pour le calcul de l'indice de concentration de Gini.
La construction de l'arbre est réalisée récursivement avec la fonction construit (arbre, sep_max, taille_min, p_var, ind_rec) après avoir créé un arbre initial à deux branches avec la fonction separe.
La fonction construit prend en argument entre autres :
arbre : structure de type noeud constituée de 4 éléments [ind, val, gauche, droite];
sep_max;
taille_min;
p_var;
ind_rec : l'indice de récursivité donnant le nombre de séparations déjà effectuées.
La fonction separe peut renvoyer un groupe gauche ou droite vide ([]), cela signifie qu'il n'y a pas eu de critères permettant de séparer les données en deux groupes. Dans ce cas, il faut calculer la feuille terminale associée au groupe non vide et imposer la valeur de cette feuille à droite et à gauche. Les variables gauche et droite peuvent être des nombres 0 ou 1 (feuilles) ou des structures de type nœud (cf. question Q10).
Dans la fonction récursive, la variable arbre de type nœud est modifiée au cours des appels successifs.
Q16. Compléter les conditions numérotées 1 à 4 de la fonction récursive construit donnée sur le document réponse.
III. 3 - Test d'une prédiction sur un arbre simple
À partir des fonctions présentées précédemment, il est possible de construire un arbre de décision classique en prenant en compte toutes les colonnes disponibles pour faire les séparations. Pour le cas que l'on traite, on prendra ainsi p_var = 60.
Pour tester les performances de prédiction dans ce cas, on utilise un jeu de 100 données connues pour construire l'arbre. On réalise ensuite une prédiction sur un jeu de 50 données (non utilisées pour la construction mais dont on connait la classe) : pour chaque donnée, on parcourt l'arbre jusqu'à arriver sur une feuille qui donnera le groupe prédit. On compare cette prédiction à la classe connue. On compte le nombre de succès pour en déduire un taux de réussite. On recommence cette analyse en faisant une nouvelle construction d'arbre à partir des 100 données (ce qui correspond aux prédictions notées 1,2 et 3). On étudie également l'influence du nombre de données pour construire l'arbre en effectuant la même démarche pour des jeux de 125 et 150 données.
Arbre construit à partir de 100 données
Arbre construit à partir de 125 données
Arbre construit à partir de 150 données
Test de prédiction 1
79 %
74 %
88 %
Test de prédiction 2
76 %
78 %
84 %
Test de prédiction 3
74 %
78 %
77 %
Temps moyen
0, 42 s
0, 64 s
0,86 s
Tableau 1 - Pourcentages de réussite obtenus et temps de prédiction
Le tableau 1 liste une synthèse des pourcentages de réussite obtenus ainsi que le temps pour réaliser une prédiction.
Q17. Au vu de ces quelques résultats d'analyse de la méthode des arbres de décision, indiquer de quels problèmes semblent souffrir cette méthode.
III. 4 - Algorithme des forêts aléatoires : «random forest»
Pour palier les problèmes observés précédemment, on utilise un algorithme des forêts aléatoires. L'idée de l'algorithme des forêts aléatoires est de construire plusieurs arbres de décision (n_arbres) basés sur une vision partielle du problème en se limitant à quelques variables (d'où l'introduction de la fonction indice_aleatoire dans la partie précédente). En pratique, on utilise la racine carrée du nombre de variables, soit 7 au lieu de 60 dans notre exemple.
Ensuite, on réalise une prédiction sur les différents arbres construits et on associe à la donnée à classer la classe majoritaire issue des différentes prédictions élémentaires.
On suppose que l'on dispose des fonctions : construire_foret qui renvoie une liste d'arbres (non détaillée ici) et prediction qui pour un arbre connu et une donnée renvoie la valeur de sa classe.
Q18. Compléter les 4 instructions manquantes de la fonction récursive prediction(arbre,donnee) donnée sur le document réponse qui prend en argument un arbre de décision noté arbre de type nœud et une donnée à classer donnee. La fonction isinstance(var, type) renvoie True si var est du type type.
On note :
data_train, les données d'entraînement de l'algorithme qui vont servir à construire les arbres;
data_test, les données permettant de tester l'efficacité de l'algorithme en comparant le classement proposé par rapport à la valeur connue.
Q19. Écrire une fonction random_forest(data_train, data_test, sep_max, taille_min, n_arbres, p_var) qui renvoie une liste contenant la classe de chaque donnée contenue dans la variable data_test.
Conclusion
On réalise des tests de prédiction comme cela a été présenté en sous-partie III.3.
Le tableau 2 liste une synthèse des pourcentages de réussite obtenus ainsi que le temps pour réaliser une prédiction avec une forêt de 20 arbres.
Arbre construit à partir
de 100 données
Arbre construit à partir
de 125 données
Arbre construit à partir
de 150 données
Test de prédiction 1
88%
84%
91%
Test de prédiction 2
91%
86%
91%
Test de prédiction 3
86%
83%
88%
Temps moyen
0, 23 s
0, 35 s
0, 5 s
Tableau 2 - Pourcentages de réussite et temps de prédiction pour une forêt de 20 arbres
Q20. Conclure sur l'intérêt de cet algorithme des forêts aléatoires.
FIN
DOCUMENT RÉPONSE
Q1 - Instruction pour la création de la variable temps ◻
Q2 - Fonction chirp(temps, £0,Deltafe, T,EQ) ◻
Q3 - Instructions pour stocker f, t, S. Taille de f, t, S en fonction de n et N ◻
Q4 - Intérêt du spectrogramme
Q5 - Fonction w(t, f, eta )
Q6 - Fonction enveloppe(eta, S, p, dt, df)
±
-
-
-
-
-
-
-
-
|
◻
-
- (-)
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Q7 - Fonction normalisation(P)
Q8 - Valeur de la variable donnees (deux premières lignes lues seulement)
Q9 - Taille mémoire minimale pour stocker les données
Q10 - Représention en Python de l'arbre de la figure 5(a)
Q11 - Classification de la donnée. Justification
Q12 - Fonction indices_aleatoires(m,p_var)
Q13 - Fonction [gauche, droite] = test_separation(ind,val,donnees)
Q14 - Compléter les instructions notées 1 à 5
def Gini_groupes(groupes):
#nombre de données total
n_donnees = #instruction1
gini = 0.0 #somme pondérée des indices Gini de chaque groupe
for donnees in groupes:
taille = len (donnees) #taille d'un groupe
if taille != 0:
gini_gr = 0.0
for val in [0,1]:
p=0
for ligne in donnees :
if ligne[-1] == val:
#instruction2
#instruction3
gini_gr += #instruction4
#ajout de gini_gr avec le poids relatif
gini += #instruction5
return gini
NE RIEN ÉCRIRE DANS CE CADRE
Q15 - Fonction feuille(data)
Q16 - Compléter les conditions numérotées 1 à 4 de la fonction récursive construit
def prediction(arbre, donnee):
[ind,val,gauche,droite]=arbre
if donnee[ind] < val:
if isinstance (gauche, list):
#instruction1
else:
#instruction2
else:
if isinstance(droite, list):
#instruction3
else:
#instruction4
Q19 - Fonction random_forest(data_train, data_test, sep_max, taille_min, n_arbres, p_var)
Q20 - Conclusion sur l'intérêt de l'algorithme des forêts aléatoires
ANNEXE
Rappels des syntaxes en Python
Remarque : sous Python, l'import du module numpy permet de réaliser des opérations pratiques sur les tableaux : from numpy import *. Les indices de ces tableaux commencent à 0 .
Python
tableau à une dimension
L=[1,2,3] (liste)
v=array([1,2,3]) (vecteur)
accéder à un élément
v [0] renvoie 1 (L [0] également)
ajouter un élément
L. append(5) uniquement sur les listes
séquence équirépartie quelconque de 0 à 10.1 (exclus) par pas de 0.1
arange(0,10.1,0.1)
définir une chaîne de caractères
mot='Python'
taille d'une chaîne
len(mot)
extraire des caractères
mot[2:7]
éliminer le ∖n en fin d'une ligne
ligne.strip()
découper une chaîne de caractères selon un caractère passé en argument. On obtient une liste qui contient les caractères séparés
mot.split(',')
ouverture d'un fichier en lecture
with open ('nom_fichier', 'r') as file: instructions avec file
Questions fréquentes
4 questions
Sur quoi porte le sujet d'informatique CCINP PSI 2020 ?
Afficher ou masquer la section
Sur quoi porte le sujet d'informatique CCINP PSI 2020 ?
+
Il traite de la classification d'obstacles détectés par un sonar : traitement du signal avec numpy et spectrogramme, lecture de données, puis arbres de décision et forêts aléatoires programmés en Python.
Quelles erreurs le jury a-t-il relevées en informatique CCINP PSI 2020 ?
+
Décalages d'indices, variables non définies, confusion entre listes et tableaux numpy, mauvais arguments pour la transformée de Fourier (Q3) et méconnaissance de la taille d'un réel en double précision (Q9).
Même année, MinesMines Informatique Commune MP PC PSI 2020Mines · 2020Corrigé
Même année, CentraleCentrale Informatique Commune MP PC PSI TSI 2020Centrale · 2020Sujet seul
Même chapitre : Récursivité (+1)X ENS Informatique Commune MP PC PSI 2019X-ENS · 2019Corrigé
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
