É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 valeurs sur une durée totale . 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 à 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 jusqu'à la fréquence (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 :
avec où est la fréquence porteuse et la bande de fréquences de modulation.
Figure 1 - Exemple de signal émis de type CHIRP
Q2. Écrire une fonction chirp(temps, , Deltafe, ) qui renvoie un vecteur de taille N correspondant au signal émis défini sur [ [ avec temps le vecteur défini précédemment et f 0 , Deltafe, les paramètres intervenant dans le système d'équations définissant .
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 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 noté s . La période d'échantillonnage de ce signal est .
Pour obtenir les intervalles de temps utilisés dans la méthode, on sélectionne un instant particulier ( ) et instants. Ces instants seront répartis autour de la valeur avant et après). Pour extraire la portion de signal intéressante, on multiplie 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 et un vecteur de nombres complexes (de taille ) dont le module correspond au spectre de Fourier. On répète le processus en décalant l'intervalle de temps sélectionné de valeurs (pour un chevauchement de ).
Finalement, on obtient alors une fonction discrète de deux variables où est un vecteur de fréquences de taille (le même pour toutes les fenêtres), est un vecteur contenant les valeurs de retenues de taille et l'ensemble des modules pour chaque fréquence et chaque instant . Le tracé du module de en fonction des deux vecteurs et 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 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 le résultat de la transformée de Fourier discrète du signal numérique en précisant bien les arguments retenus, sachant que l'on souhaite un recouvrement de , que le nombre de valeurs retenues autour de chaque instant est et qu'on choisit une fenêtre de type Hamming. Donner également la taille des grandeurs , S obtenues en retour en fonction de et .
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 et .
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 : avec la fonction issue de l'analyse par transformée de Fourier locale et une fonction représentant un ensemble de fenêtres localisées autour de la zone d'intérêt dans le spectrogramme (de tailles et ). est un entier variant de 0 à , permettant d'obtenir un ensemble fini de valeurs de l'enveloppe ( est un paramètre de l'analyse qui sera choisi par la suite).
On note et .
La fonction est définie par :
Q5. Écrire une fonction , eta) qui renvoie 1 ou 0 en fonction des valeurs de et eta . On supposera que les paramètres , et sont connus et utilisables directement dans la fonction (variables globales notées et Df.
On note les valeurs du temps, i variant de 0 à et les valeurs de fréquences, j variant de 0 à avec où et sont respectivement des pas de temps et de fréquence. La fonction à intégrer est notée avec et variant respectivement de 0 à et 0 à . Pour intégrer numériquement la fonction discrète , on utilise la formule : avec 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 et . Le tableau numpy S contient les valeurs de la fonction discrète et le tableau numpy p contient les valeurs des poids .
Pour chaque expérience (fonction de l'obstacle et de l'angle d'incidence de l'onde émise), on construit cette enveloppe. En prenant , 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 en ramenant le maximum à 1 et le minimum à 0 par une fonction affine.
Q7. Proposer une fonction normalisation(P) qui renvoie un vecteur de valeurs comprises entre 0 et 1 . On pourra utiliser les fonctions et 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 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 : .
Q10. Donner la représentation en Python de l'arbre défini sur la figure 5(a).
Soit une donnée non classée .
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 lignes et 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 nombres parmi la liste des numéros de colonnes ( var ) et qui renvoie une liste de taille 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 . Par exemple, si on choisit p_var avec , 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 (noté ) est calculé à l'aide de la formule suivante: Gini où est le nombre de classes possibles, ici 2 (0 ou 1), est la proportion des éléments du jeu de données appartenant à la classe . 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 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 .
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,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
Test de prédiction 2
Test de prédiction 3
Temps moyen
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 . Taille de en fonction de et
Q4 - Intérêt du spectrogramme
Q5 - Fonction , 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 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
CCINP Informatique Commune PSI 2020 - Version Web LaTeX | WikiPrépa | WikiPrépa
