CCP Informatique PSI 2019

Thème de l'épreuve Intelligence Artificielle - Application en médecine
Principaux outils utilisés requêtes SQL, tableaux, tri, probabilités, statistiques, bibliothèque numpy
Mots clefs intelligence artificielle, hernie discale, spondylolisthésis, méthode KNN, plus proches voisins, méthode naïve bayésienne, matrice de confusion, prédiction, apprentissage supervisé, apprentissage automatique

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                                   

Rapport du jury

(télécharger le PDF)
        

Énoncé obtenu par reconnaissance optique des caractères


SESSION 2019 C PSIINO7

CONCOURS
COMMUN
INP

ÉPREUVE SPÉCIFIQUE - FILIÈRE PSI

INFORMATIQUE

Vendredi3 mai:8h-11h

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.

Les calculatrices sont interdites

Le sujet est composé de trois parties indépendantes.

L'épreuve est à traiter en langage Python, sauf les questions sur les bases de 
données qui seront
traitées en langage SQL. La syntaxe de Python est rappelée en Annexe, page 12.

Les différents algorithmes doivent être rendus dans leur forme définitive sur 
la copie en respectant les
éléments de syntaxe du langage (les brouillons ne sont pas acceptés).

Il est demandé au candidat de bien vouloir rédiger ses réponses en précisant 
bien le numéro de la
question traitée et, si possible, dans l'ordre des questions. Bien que 
largement indépendante, la
partie [IT fait appel aux données et à la définition de fonctions définies dans 
la partie IT.

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.

Sujet : page 1 à page 11
Annexe : page 12

1/12
Intelligence Artificielle - Application en médecine

Partie I - Présentation

L'Intelhigence Artifñcielle est de plus en plus utilisée dans de nombreux 
domaines divers et variés.
Les techniques d'apprentissage machine, qui permettent à un logiciel 
d'apprendre automatiquement à
partir de données au lieu d'être explicitement programmé, fournissent des 
résultats impressionnants.
Les applications sont nombreuses dans la reconnaissance d'image, la 
compréhension de la parole ou
de textes, dans l'assistance à la décision, dans la classification de données, 
dans la robotique.
L'Intellhigence Artiñcielle progresse également dans le domaine de la santé. Le 
logiciel Watson déve-
loppé par IBM peut analyser les données d'un patient : ses symptômes, ses 
consultations médicales,
ses antécédents familiaux, ses données comportementales, ses résultats 
d'examen, etc. Il établit alors
une prévision de diagnostic le plus vraisemblable et propose des options de 
traitement en s'appuyant
sur une base de données établie sur un grand nombre de patients.

Objectif

L'objectif du travail proposé est de découvrir quelques techniques 
d'Intelligence Artificielle en
s'appuyant sur un problème médical. À partir d'une base de données comportant 
des propriétés
sur le bassin et le rachis lombaire (figures 1), on cherche à déterminer si un 
patient peut être
considéré comme « normal » ou bien si ces données impliquent un développement 
anormal de
type hernie discale (saillie d'un disque intervétébral) ou spondylolisthésis 
(glissement du corps
vertébral par rapport à la vertèbre sous-jacente).

(a) Normal (b) Hernie discale (c) Spondylolisthésis

Figures 1 -- Différentes configurations des vertèbres

Le sujet abordera les points suivants :
- analyse et représentation des données,
- prédiction à l'aide de la méthode KNN,
- apprentissage et prédiction à l'aide de la méthode dite « Naïve Bayes ».

Dans tout le sujet, il sera supposé que les modules python 
numpy,matplotlib.pyplot sont déjà
importés dans le programme.

2/12
Partie II - Analyse des données

La base de données médicale contient des informations administratives sur les 
patients et des infor-
mations médicales. Pour simplifier le problème, on considère deux tables : 
PATIENT et MEDICAL.

La table PATIENT contient les attributs suivants : ( PATIENT | { MEDICAL |
- id : identifiant d'un individu (entier), clé primaire ;
- nom : nom du patient (chaîne de caractères) ; id id
- prenom : prénom du patient (chaîne de caractères) ; renom a
- adresse : adresse du patient (chaîne de caractères) ; adresse h
- email : (chaîne de caractères) ; email idpatient
- naissance : année de naissance (entier). | naissance ) __ etat J

La table MEDICAL contient les attributs suivants :

- 1d : identifiant d'un ensemble de propriétés médicales (entier), clé primaire 
;
datal : donnée (flottant) ;
data? : donnée (flottant) ;

9

idpatient : identifiant du patient représenté par l'attribut 1d de la table 
PATIENT (entier) ;
etat : description de l'état du patient (chaîne de caractères).

Les attributs datal, data2.. sont des données relatives à l'analyse médicale 
souhaitée (dans notre cas

des données biomécaniques). L'attribut « etat » permet d'affecter un label à un 
ensemble de données

médicales : « normal », « hernie discale », « spondylolisthésis ».

Q1. Écrire une requête SQL permettant d'extraire les identifiants des patients 
ayant une « hernie
discale ».

Q2. Écrire une requête SQL permettant d'extraire les noms et prénoms des 
patients atteints de
« Spondylolisthésis ».

Q3. Écrire une requête SQL permettant d'extraire chaque état et le nombre de 
patients pour chaque
état.

Une telle base de données permet donc de faire de nombreuses recherches 
intéressantes pour essayer
de trouver des liens entre les données des patients et une maladie. Cependant, 
compte-tenu du nombre
d'informations disponibles, 1l est nécessaire de mettre en place des outils 
pour aider à la classification
de nouveaux patients. C'est l'objet des algorithmes d'Intelligence Artificielle 
développés dans la suite.
Pour l'étude qui va suivre, on extrait de la base de données les attributs 
biomécaniques de chaque
patient que l'on stocke dans un tableau de réels (codés sur 32 bits) à N lignes 
(nombre de patients)
et n colonnes (nombre d'attributs égal à 6 dans notre exemple). On nomme data 
ce tableau. L'état
de santé est stocké dans un vecteur de taille N contenant des valeurs entières 
(codées sur 8 bits)
correspondant aux différents états pris en compte (0 : normal, 1 : hernie 
discale, 2 : spondylolisthésis).
On le nomme : etat.

Les variables data et etat sont stockées dans des objets de type array de la 
bibliothèque Numpy.

Des rappels quant à l'utilisation de ce module Python sont donnés dans l' 
Annexe, page 12.

Q4. Citer un intérêt d'utiliser la bibliothèque de calcul numérique Numpy quand 
les tableaux sont
de grande taille.

Q5. Déterminer la quantité de mémoire totale en Mo (1 Mo = 1 000 000 octets) 
nécessaire pour
stocker le tableau et le vecteur des données s1 N = 100 000. On supposera que 
les données
sont représentées en suivant la norme usuelle IEEE 754.

3/12
Les 6 attributs considérés dans notre exemple (les n colonnes du tableau) sont 
définis ci-après
- angle d'incidence du bassin en ';

- angle d'orientation du bassin en ";

- angle de lordose lombaire en ";

- pente du sacrum en ";
- rayon du bassin en mm;

- distance algébrique de glissement de spondylolisthésis en mm.

Les labels de ces attributs sont stockés dans une liste nommée :

label_attributs
'pente_sacrum',

['incidence_bassin',
'rayon_bassin',

'orientation_bassin',
'glissement_spon'|.

Le tableau suivant montre les premières valeurs du tableau data.

'angle_lordose',

incidence bassin

orientation_ bassin

angle_lordose

pente_sacrum

rayon_bassin

glissement_spon

63,03

22,55

39,61

40,48

98,67

-- 0,25

39,06

10,06

25,02

29,0

114,41

4,56

68,83

22,22

50,09

46,61

105,99

-- 3,53

69,3

24,65

44,31

44,64

101,87

11,21

49,71

9,65

28,32

40,06

108,17

7,92

40,25

13,92

25,12

26,33

130,33

2,23

48,26

16,42

36,33

31,84

94,88

28,34

Tableau 1 -- Données (partielles) des patients à diagnostiquer

Avant de traiter les données pour réaliser une prédiction (ou diagnostic), 1l 
peut être intéressant de
les visualiser en traçant un attribut en fonction d'un autre attribut et en 
utilisant des motifs différents
selon les valeurs du vecteur etat.

On obtient, à partir des données exploitées, les courbes de la figure 2 (zoom 
sur la figure 3).

140 140 180 00
18 5 120F 5 120 * = 160! * JE 400!
£ & 100! 5 100! Ë E
£ ? © £ 140! 15 300}
" 2 80} E 80F £ a
" 8 5 % 120 1% 200|
15 5 60! g 60! $ * |S *
2 1 1 L * 1 " *
É 2 40! # aol 5 100 £ 100 + tt «
EUR £ a ü à À
L le 5 20} 3 20} = 80} 15 of x se
oO *
0 L 0 L 0 L L L 60 L L L L L L 00 L L L L L L
2 0 100 140 20 8 0 120 140 20 0 0 100 120 140 20 40 60 80 100 120 140 20 40 60 
80 100 120 140
20 incidence_bassin (deg) incidence_bassin (deg) 40 incidence_bassin (deg) 40 
incidence_bassin (deg) 180 incidence_bassin (deg) c00 incidence_bassin (deg)
*
5 120 - # 5 220} 3 120} & 160 ,* £ 400!
D EUR © © *
g 100! + * À È £ 100! Z 100E £ 140! "°° 44° £ 300!
'ü Er Li * sg (a £ £  « % ge * A * + °
ñ 80 ,% se v 8 50) So " à 120 "Te ee * % 200
2 * ++ D D Oo * # n F e x , ol
l L # * = L © L * e © * k
g 60 ,*, Re £ s, © 5, 50 ... Sibiiehss 00 Fee SR ee ee [5 00 . de,
& 40. e s É 2 40! £ 40 1" Ma ae S F Eu ee * + Ê [ # SE *
Z je  * S PB £ En ve * 3 Lorrt tn ÿ AM FR
y z = L * = E
E 20} 5 20} 2 20 LE x + 80 7, * 5 0 ed x *
0 L L L L L 0 0 L L L L 60 L L L L L L L 100 L L L L L L L
--20 --10 0 10 20 30 40 10 --2 1 --20 --10 10 20 0 50 60 --20 --10 0 10 20 30 
40 50 60 --20 --10 1 0 0 50 60
140 orientation bassin (deg) orientation bassin (deg) 70 orientation bassin 
(deg) 140 orientation bassin (deg) 180 c00 orientation bassin (deg)
* =
SG 120} . 19 +, ++ ny 604 = 120 160 JE 400! *
$ £ és a = ë E Ë
7 100 "à *. EUR "+ + D 5 50! D 100! £ =
£ « me £ de a+ 5 £ È 140! x 15 300!
ë 80} «+ Fran 8 Fe de CEE 8 40} E 80! + us £ 2
S è ee, 8, ARS « 2 5 + met ® 120 4/71 200!
w 601 #% A ls se" 5 30! B 60! * mé) ë È "
Y 2 * = 1 # +
& L x . # * * 2 L 2 L e D 5 1007 1£ 100 * # de tx
5%) x è re, 520 sl tee ë ù RTE
£ 20. 15 ° Z 10} 8 20 Xe + = 80. 15  0f *x*  e** e
0 L L L L L 0 0 L L L 60 L L 100 L L L
20 4 0 1 0 40 60 80 10 140 40 80 00 120 20 0 60 80 10 120 140 20 1 120 140 20 
40 60 80 1 120 140
140 angle lordose (deg) angle Jordose (deg) 140 100 angle_lordose (deg) 180 
angle lordose (deg) e00 angle Jordose (deg)
g 120; # 15 * "+ 5 120F y 160! " | E 400!
© 100! £ te * & 100! 5 Ê £
£ * EUR x et ©? En £ 140! l< 300} ü | ñ $ us oe | S c S ä 80 ® Rx " g 80 à a $ 8, xx ge * 8 2 & 120 * 1% 200} a! 60! s Ne + 5 60| v 4 ; & "+ + Ô _ * ! = * * e 5 * 5 £ 100! J£ 100! gx ÿ 4! 5 EU 3 40! Ë $ È , d her © 8 20! È + 8 ol Z Ê go! * 12 0! ee TT Oo 0 L L L L L L L 0 L L L L L L 60 L L L L L L 100 L L L L L L 20 40 60 80 100 0 40 60 80 100 140 20 40 60 80 100 120 140 20 40 60 80 100 120 4 20 40 60 80 100 120 140 20 40 60 80 100 120 140 20 pente _sacrum (deg) 140 pente_sacrum (deg) 140 pente _sacrum (deg) 150 pente _sacrum (deg) e00 pente _sacrum (deg) G 120 15 = 120 = 120 * JE | È ° È Laure 5 5 2 cn Y 100! EUR Font 2 100} " * . £ 100F È JE 300! G u CURE Te vo CA à £ oe © 8 80| 8 RER ® 80} gr us x 5 80 * à g ss * 8, ue » D * 14 * Las » © * + ** $ 1 200 w! 60} £ Lx $ GS 60! « Hs ..° % 60 ri à À & EUR " YU © ce * "© 1 ne ox ° * + Le jo * * L g ü 40. 5 À ° 2 40! De ,° £ 40 te LA: Ê 1£ 100 PT CE È Ë are E ae ë NS ce | 5 ë à EE £ 20 5 * 5 20} x » 2 20} ui + z 15 0 x . 0 L L L L L L 0 L L L L 0 L L L L L 00 L L L L L 60 80 100 120 140 0 100 120 140 180 60 80 100 120 140 160 180 60 80 100 120 140 160 180 80 100 120 140 160 0 60 80 100 120 140 160 180 120 rayon_bassin (mm) rayon_bassin (mm) 140 rayon_bassin (mm) 140 rayon_bassin (mm) 20 rayon_bassin (mm) Den rayon_bassin (mm) SG 120. 15 * - 120 = 120 * 8 * 5 ste 5 S & 160 2 200! x 100F E Sa Z 100F âets £ 100F E 140 re D ê È si a re E L et re 8 150 m 80. a . 80 À E 80! EUR * + & s * $, « $ fes 5 x 8 120 * 2 a! 60} + 5 * 5 60} " 8 60 Ze. ë ® 100! Ê ü w! x * * gl se" c'100! 5 CE ] % Dm 40} + 40 el © La £ D EUR * £ LA 5 "++ A Ps S 50! É 20! L S 20l * a 20! S 80! s* + Z TT oO 0 L L L L L L 0 L L L L L 0 L L L L L 60 L L L L L --100 0 100 200 300 0 100 200 300 500 --100 0 100 200 300 400 500 --100 0 100 200 300 400 500 --100 0 100 200 300 400 500 --100 0 100 200 300 400 500 glissement_spon (mm) glissement_spon (mm) glissement_spon (mm) glissement_spon (mm) glissement_spon (mm) glissement_spon (mm) Figure 2 -- Répartition des données 4/12 © © I ON 1 & © D NO DD A mn nm mm mm em em D nm OLD IA 1 À © D = © 70 60 | | y 60 ë 50 | 1 = 50 E | EE 5 uw 30 © 40 © n v 2, 20 1 © = 2 10 }- x TT] Q + OU £ 20 S OL JT o 2 g ë 10 5 10+ J O0 20 l l | l l | 20 40 60 80 100 120 140 0 20 40 60 80 100 120 140 incidence bassin (deg) incidence bassin (deg) Figure 3 -- Zoom sur les figures de coordonnées (1,1) et (1,2) de la matrice de répartition des données (figure 2) Cette figure est une matrice dont le terme (5, i) de la diagonale est l'histogramme des fréquences de l'attribut i et les termes extra-diagonaux (1, j) représentent l'attribut z en fonction de l'attribut j pour chaque ligne du tableau data. Sur les figures hors diagonale, on représente chaque donnée d'attribut : en fonction de l'attribut 7 à l'aide d'un symbole dépendant de l'état du patient (un rond 'o° si l'état du patient est normal, une croix 'X° Si l'état est hernie discale" et une étoile '*" s1 l'état est "'spondylolisthésis"). Pour réaliser cette figure, 1l faut séparer les données en fonction de l'état du patient afin d'aftecter un symbole par état. Ceci revient à classer les patients en plusieurs groupes. Q6. Écrire une fonction separationParGroupe(data,etat) qui sépare le tableau data en 3 sous-tableaux en fonction des valeurs du vecteur etat correspondantes (on rappelle que celui-c1 contient les valeurs 0, 1 et 2 uniquement). La fonction doit renvoyer une liste de taille 3 de sous-tableaux. Les sous-tableaux ne seront pas nécessairement représentés par un type array"; liste de listes', 'liste d'array" conviennent également. Pour définir la figure, les instructions suivantes sont exécutées : fig = plt.figure() mark = ['0°,°x",'*x°] label_attributs = ['incidence bassin (deg)', 'orientation_bassin (deg)', "angle _lordose (deg)', 'pente _ sacrum (deg)', "rayon_bassin (mm), glissement _spon (mm)"'| groupes = separationParGroupe(data ,etat) for 1 in range (len(groupes)): groupes{1] = array(groupes{i1l]) n=len(data[0|) for 1 in range(n): for j in range(n): axil = plt.subplot(ARGSI) pit.ylabel(label_attributs[j]]) #mettre un label à 1'axe y if TEST for k in rangel(len (groupes) ): pit.xlabel(label_attributs[1]) #mettre un label à 1'axe x axil.scatter (ARGS2) else : pit.xlabel("Nombre de patients") #mettre un label à l'axe x axil.h1st (ARGS3) pit.show() 5/12 Les instructions précédentes utilisent la fonction separationParGroupe définie à la question Q6, puis les éléments de la liste groupes sont convertis en array afin de pouvoir extraire les colonnes plus facilement. La documentation du module matplotl1b (plt) renseigne sur les arguments des fonctions subplot, scatterethist. jaxl = plt.subplot(a,b,k) Cette instruction permet de sélectionner parmi un tableau de figures de taille a (nombre de lignes), b (nombre de colonnes), la k° en numérotant les sous-figures de 1 à m x n en partant du haut gauche vers le bas droite (en allant de gauche à droite et de haut en bas). jaxl . Scatter(datax , datay , marker=mark![K |) Cette commande permet de tracer sur la sous-figure ax] un nuage de points d'abscisses un vecteur datax et d'ordonnées un vecteur datay avec un symbole à choisir parmi ceux de la liste mark. jaxl.hist(datax) Cette commande permet de tracer un histogramme des données datax sur la sous-figure ax. Q7. Définir les arguments ARGSI, ARGS2, ARGS3 ainsi que la condition TEST définis dans le script précédent permettant d'obtenir la figure 2. QS. Préciser l'utilité des diagrammes de la diagonale ainsi que celle des diagrammes hors diago- nale. Partie IIT - Apprentissage et prédiction III.1 - Méthode KNN La méthode KNN est une méthode d'apprentissage dite supervisée ; les données sont déjà classées par groupes clairement identifiés et on cherche dans quels groupes appartiennent de nouvelles données. Le principe de la méthode est simple. Après avoir calculé la distance euclidienne entre toutes les données connues des patients et les données d'un nouveau patient à classer, on extrait les K données connues les plus proches. L'appartenance du nouveau patient à un groupe est obtenue en cherchant le groupe majoritaire, c'est-à-dire, le groupe qui apparaît être le plus représentatif parmi les K données connues. On note X;, 1 EUR [0, n -- 11], le vecteur colonne : du tableau de données data, c'est-à-dire les valeurs prises par l'attribut : des données des patients déjà classées. On cherche à déterminer à quel groupe appartient un nouveau patient dont les attributs sont représentés par un n-uplet z de valeurs notées (Zo; Lis. Zn-1). Préparation des données Avant de calculer la distance euclidienne, 1l est préférable de normaliser les attributs pour éviter qu'un attribut ait plus de poids par rapport à un autre. On choisit de ramener toutes les valeurs des attributs entre 0 et I. Une technique de normalisation consiste à rechercher pour chaque attribut X le minimum (min(X)) qui est placé à 0 et le maximum (max(X)) qui est placé à 1. On note alors X,,,, un des vecteurs colonne X après normalisation (toutes les valeurs de X,,,, Sont donc comprises entre 0 et 1). 6/12 DO JAN 1 & © D SR D mm © DO IA Li R © D A © \O Q9. Proposer une expression de Xyorm; Un élément du vecteur X,,,n en fonction de l'élément x; du vecteur À correspondant et de min(X) et max(X). Q10. Ecrire une fonction min_max(X) qui retourne les valeurs du minimum et du maximum d'un vecteur À passé en argument. La fonction devra être de complexité linéaire. Q11. Écrire une fonction distance(z, data) qui parcourt les N lignes du tableau data et calcule les distances euclidiennes entre le n-uplet z et chaque n-uplet x du tableau de données connues (x représente une ligne du tableau). La fonction doit renvoyer une liste de taille N contenant les distances entre chaque n-uplet x et le n-uplet z. Détermination des K plus proches voisins Pour déterminer les K plus proches voisins avec K un entier choisi arbitrairement, 1l suffit d'utiliser un algorithme de tri efficace. La liste T à trier est une liste de listes à 2 éléments contenant : - la distance entre le n-uplet à classer et un n-uplet connu (on trie par ordre croissant sur ces valeurs) ; - Ja valeur de l'état correspondant au n-uplet connu. On retient l'algorithme suivant : def tri(T): if len(T) <= l!: return Î else : m = len(T)//2 tmpl = [] for x in range (m): tmpl.append(T[xl]) tmp2 = |] for x in range(m,len(T) ): tmp2.append(T[xl}]) return fct(tri(tmpl),tr1i(tmp2)) def fct(TI,T2): If T1 == |]: Léreeeeeeessseeeee #ligne 1 à compléter Léreeeeeeessseeeee #ligne 2 à compléter If TI[OÏJ[O] < T2[0][0]: return [TI[0O]|+fct(TI[1:],T2) else : Léreeeeeeessseeeee #ligne 3 à compléter Q12. Donner le nom de ce tri ainsi que son intérêt par rapport à un tri par insertion. Préciser un inconvénient du programme proposé par rapport à ce tri. Q13. Préciser les lignes 1 à 3 de la fonction fct pour que l'algorithme de tri soit fonctionnel. 7/12 DO JAN 1 & © D DD en mm mm mm nm nu mm © DO OO IN 1 R © D n © \O © KO © I ON A R © D + bd L'algorithme de la méthode KNN est décrit par la fonction python suivante : def KNN(data ,etat ,Zz,K,nb): #partie Î| T' = {|} dist -- distance(z,data) for 1 in range(len(dist)): T.append([ dist[11],11]) tri(T) #partie 2 select = [0]x+xnb for i in range(K): select[etat[T[1][1]]]+=1 #partie 3 ind = 0 res = select{[0] for Kk in range(l ,nb ): if select[k] > res:
res = selectIKk|
ind = Kk
return ind

K représente le nombre de voisins proches retenus, nb correspond au nombre 
d'état (3 dans notre
exemple) et z correspond aux attributs du patient à classer.

Q14. Expliquer ce que font globalement les parties 1 (lignes 3 à 7), 2 (lignes 
10 à 12) et 3 (lignes 15
à 21) de l'algorithme. Préciser ce que représentent les variables locales T, 
dist, select, ind.

Validation de l'algorithme

Pour tester l'alsorithme, on utilise un jeu de données supplémentaires 
normalisées dont l'état des
patients est connu (100 patients). On note datatest ces données et efattest le 
vecteur d'état connu
pour ces patients. On applique ensuite l'algorithme sur chaque élément de ce 
jeu de données pour une
valeur de K fixée.

On définit la fonction suivante qui renvoie une matrice appelée "'matrice de 
confusion".

def test KNN(datatest ,etattest , data ,etat ,K,nb):
etatpredit = {|
for 1 in range(len(datatest)):
res -- KNN(data ,etat , datatest[1],K,nb)
etatpredit.append(res)

mat = np.zeros((nb,nb))

for 1 in range(len(etattest)):
mat[etattest[1],etatpredit[1]] += Î

return mat

23 4 7
On obtient pour K = 8 la matrice suivante :| 7 IT
5 2 40

8/12
Q15. Indiquer l'information apportée par la diagonale de la matrice. Exploiter 
les valeurs de la
première ligne de cette matrice en expliquant les informations que l'on peut en 
tirer. Faire de
même avec la première colonne. En déduire à quoi sert cette matrice.

On peut également tracer l'efficacité de l'algorithme pour différentes valeurs 
de K sur le jeu de don-
nées test (100 éléments sur un échantillon de 310 données). On trace le 
pourcentage de réussite en
fonction de la valeur de K sur la figure 4.

80

Taux de réussite en (%)

65/................ Le Li D

60
0

Nombre de voisins (K)

Figure 4 -- Pourcentage de réussite de l'algorithme en fonction de K

Q16. Commenter la courbe obtenue et critiquer l'efficacité de l'algorithme.

IIL.2 - Méthode de classification naïve bayésienne

Une autre méthode simple à mettre en oeuvre et qui fournit de bons résultats, 
malgré l'hypothèse
forte utilisée, est la classification naïve bayésienne. Cette méthode 
d'apprentissage est supervisée
également. La méthode repose sur le théorème de Bayes qui suppose 
l'indépendance probabilistique
des caractéristiques d'un groupe donné.

On suppose que chaque attribut : (colonne de la matrice de données data) est 
modélisable par une
variable aléatoire notée X'; pour i EUR [0,n--11]. L'appartenance d'une donnée 
à un groupe est modélisée
par la variable aléatoire Y, dont les valeurs discrètes sont y, = 0 pour un 
sujet sain, y, = 1 pour un
sujet atteint d'une hernie discale et y; = 2 pour un sujet atteint de 
spondylolisthésis.

L'appartenance de la donnée k& (k° ligne de la matrice de données) est connue 
et indiquée dans Île
vecteur etat.

Le théorème de Bayes permet de déterminer la probabilité qu'une donnée 
appartienne à un groupe y;
connaissant ses attributs x;

PO = y;) X P(Xo = x0, À = X1, ., À ny = Xn-1|Y = y;)

PT = yifXo = x0, À = X1,., À] = Xn-1) =
I PXo = Xo, À = X1, ., À] = Xn-1)

9/12
= PO = y;lXo = xo, Xi = X1,....., Xn-1 = Xh-1) est la probabilité d'appartenir 
au groupe y; sachant
que les diftérentes variables aléatoires X; prennent respectivement les valeurs 
x;,

- P(Y = y;) est la probabilité d'appartenir au groupe y;

- P(Xo = xo, À = x1,..., X 51 = Xn1lY = y;) est la probabilité que les 
différentes variables
aléatoires X; prennent respectivement les valeurs x; sachant que la donnée 
appartient au groupe
 j»

- P(Xo = x, Xi = Xi, Àn_1 = Xh_1) est la probabilité que les différentes 
variables aléatoires X;
prennent respectivement les valeurs x;.

L'hypothèse naïve bayésienne suppose que tous les attributs sont indépendants 
et donc que :

P(X6 = Xo, Xi = Xi, .., Xp = Xn-1|Y = y;) = | [Pr = xiY = y;).

Comme le dénominateur P(X5 = xo, Xi = X1,....., Xy_1 = Xn_1) est indépendant du 
groupe considéré et
donc constant, on ne considère que le numérateur :
PO = y;) X P(Xo = %0, À = Xi, Xp = Xn-1|Y = yj).
Pour déterminer le groupe le plus probable auquel appartient une donnée z à 
classer, représentée par
le n-uplet (Zo, Z1, ....., Z-1), On choisit la probabilité maximale P(Y = y;) x 
IE P(X; = z|Y = y;) parmi
i

les j groupes.
Des lois de probabilités diverses sont utilisées pour estimer P(X; = z;|Y = 
y;); nous utiliserons une
loi de distribution gaussienne.

Apprentissage

La première étape consiste à séparer les données selon les groupes auxquels 
elles appartiennent. On
réutilise pour cela la fonction separationParGroupe(data,etat) définie à la 
question Q6.

Pour calculer la probabilité conditionnelle P(X; = z;|Y = y;) d'une donnée z 
représentée par le n-uplet
(Zo, Z1, .. Zn_1), On utilise une distribution gaussienne de la forme

Ï exp - (Z = |
Er 207,
2

OÙ Hx,y, ets, y, SOnt la moyenne et la variance de la variable aléatoire X;, 
estimées à partir des valeurs
d'attribut des données de la i-ième colonne du tableau data pour le groupe 
correspondant à y;.

Dia > DER Gin)
n n

Q17. Ecrire deux fonctions de complexité linéaire moyenne(x) et variance(x) 
permettant de ren-
voyer la moyenne et la variance d'un vecteur x de dimension quelconque.

P(Xi = zilY = y;) =

On rappelle que, pour un vecteur x de dimension n, u =

Q18. Proposer une fonction synthese(data,etat) qui renvoie une liste composée 
de doublets
[moyenne, variance] pour chaque attribut de la matrice data en les regroupant 
selon les valeurs
du vecteur etat :

[LU x vo » © x0,0 [x vos x vod ..... [Uxs vos xs 50
[LU xo y: , © roy [x y, , x vd ...... [Us y, , xs y 1:
LU xo y » © 10,2 d [x y © xd ...... [Us y» © 5,32 1].

10/12
Cette fonction appliquée au tableau data complet (non normalisé) renvoie une 
liste qui contient les
valeurs suivantes :

XI X2 X3 X4 X5 X6
etat=0 [51.68, 12.3] 112.82, 6.74] | [43.54, 12.29] | [38.86, 9.57] 1123.89, 
8.96] [2.18, 6.27]
etat=Î| 147.63, 10.6] 117.39, 6.95] 135.46, 9.68 | [30.23, 7.49] 1116.47, 9.27] 
[2.48, 5.48]
etat=2 || [71.51, 15.05] | [20.74, 11.46] | [64.11, 16.34] | [50.76, 12.27] | 
[114.51, 15.52] | [S1.89, 39.97]
Prédiction

On considère pour la deuxième étape une donnée z à classer représentée par le 
n-uplet (20, Z1, ......, Zn_1).
Pour réaliser la prédiction, 1l faut tout d'abord calculer la probabilité 
d'appartenance à un groupe
selon la loi gaussienne choisie P(X; = z;|YY = y;) en fonction de l'attribut 
considéré, puis multiplier

ces probabilités pour un même groupe y; pour obtenir

ELA EN)

Q19. Écrire une fonction gaussienne(a, moy, v) qui calcule la probabilité selon 
une loi gaussienne
de moyenne moy et de variance v pour un élément a de KR.

Q20.

Déduire de la description de l'algorithme de classification naïve bayésienne 
une fonction

probabiliteGroupe(z,data,etat) prenant en argument le vecteur z qui contient le
n-uplet de la donnée z, le tableau des données connues data et le vecteur 
d'appartenance à
un groupe de chacune de ces données etat. Cette fonction renvoie la probabilité 
d'apparte-
nance à chacun des nb = 3 groupes sous la forme d'une liste de trois valeurs. 
On utilisera la
fonction synthese(data,etat) et la fonction gaussienne(a,moy, v).

Sur le patient dont les caractéristiques sont les suivantes : 48,26, 16,42, 
36,33, 31,84, 94,88, 28,34,
on obtient les probabilités suivantes : appartenance au groupe 0 : 1,1 - 107!°, 
appartenance au groupe
1:7,4-107'%, appartenance au groupe 2 : 5,4 - 107.

La décision de l'appartenance à un groupe particulier est prise en déterminant 
le maximum parmi les
probabilités de groupes déterminées.

Q21. Ecrire une fonction prediction, dont vous préciserez les arguments, qui 
renvoit le numéro
du groupe auquel appartient un élément z.

Usuellement la méthode naïve bayésienne est utilisée dans un espace 
logarithmique ; c'est-à-dire
qu'au lieu de calculer la probabilité d'appartenance à un groupe comme vu 
précédemment, on calcule
le logarithme de cette quantité.

Q22. Proposer une explication qui justifie cette utilisation du logarithme.

L'algorithme mis en place peut être testé sur le jeu de 100 données test 
utilisé pour l'algorithme KNN
dont on connaît déjà l'appartenance à chacun des groupes. On obtient alors la 
matrice de confusion

suivante :

23 9 8
9 10 1!
10 1 49

Q23. Calculer le pourcentage de réussite de la méthode KNN, à partir de la 
matrice de confusion
pour K = 8 (page 8), ainsi que celui de la méthode naïve bayésienne à partir de 
la matrice
ci-dessus. Discuter de la pertinence de chacune des deux méthodes sur l'exemple 
traité.

FIN

11/12

ANNEXE
Rappels des syntaxes en Python

Remarque : sous Python, l'import du module numpy permet de réaliser des 
opérations pratiques sur les ta-
bleaux : 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[®] également)

ayouter un élément

L.append(5) uniquement sur les listes

tableau à deux dimensions (matrice)

M=array(([1,2,3],[3,4,5]))

accéder à un élément

M[1,2] donne 5

extraire une portion de tableau (2 premières co-

M[:,0:21
lonnes)
extraire la colonne 1 M[:,1]
extraire la ligne 1 M[1,:]

tableau de 0 ( 2 lignes, 3 colonnes)

zeros((2,3))

dimension d'un tableau T de taille (5, j)

T.shape donne [i,j]

produit matrice-vecteur

a = array ([[1,2,31,[4,5,6]1,[17,8,91]1])
b = array([1,2,3])

print(a.dot(b))

>>> array ([14,32,50])

séquence équirépartie quelconque de 0 à 10.1 (ex-
clus) par pas de 0.Ï

arange(®0,160.1,6.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]

for 1 in range(l0O):
boucle For | |

print(i)

1f (13>3):
condition If print(1)

else :

print("hello")

définir une fonction qui possède un argument et ren-
voie 2 résultats

def f(param):
a = param
b = param+xparam
return a,b

tracé d'une courbe de deux listes de points x et y

plot(x,y)

tracé d'une courbe de trois listes de points x, y et z

gca(projection='3d').plot(x,y,2z)

ajout d'un titre sur les axes d'une figure

xlabel(texte)
ylabel(texte)

ajout d'un titre principe sur une figure

title(texte)

12/12

IMPRIMERIE NATIONALE - 191157 - D'après documents fournis

Extrait du corrigé obtenu par reconnaissance optique des caractères



CCINP Informatique PSI 2019 -- Corrigé
Ce corrigé est proposé par Benjamin Monmege (enseignant-chercheur à 
l'université) ; il a été relu par Virgile Andreani (ENS Ulm) et Guillaume Batog 
(professeur
en CPGE).

Ce sujet propose l'utilisation de méthodes d'intelligence artificielle, et plus 
précisément d'apprentissage automatique, afin d'aider au diagnostic médical. 
L'exemple
applicatif choisi est celui de la détection d'un développement anormal de la 
colonne
vertébrale type hernie discale ou spondylolisthésis. Il s'agit d'un problème 
d'apprentissage supervisé, où l'on dispose de données biométriques sur un grand 
nombre de
patients étiquetés sains ou malades. On utilise ensuite ces données étiquetées 
pour
aider au diagnostic de nouveaux patients. Le sujet est composé de deux parties.
· Une première partie introduit les données biométriques et administratives 
connues sur les patients. Des requêtes SQL sont utilisées pour extraire de 
l'information des bases stockant ces différentes données. Quelques questions 
permettent
ensuite de mieux visualiser les données, pour pouvoir les utiliser dans l'aide 
au
diagnostic.
· La seconde partie propose deux méthodes d'apprentissage automatique 
appliquées au problème de diagnostic médical.
La méthode KNN des plus proches voisins est d'abord présentée. L'idée est
de prendre une décision de diagnostic fondée sur les K plus proches voisins,
chaque donnée étant représentée par un point dans un espace n-dimensionnel.
Pour calculer les plus proches voisins, une fonction de tri est implémentée.
L'algorithme est validé en étudiant sa matrice de confusion.
La méthode probabiliste de classification naïve bayésienne est ensuite 
introduite. Elle utilise la formule de Bayes reliant les probabilités 
conditionnelles et
les probabilités marginales de deux évènements A et B :
Pr(B | A) Pr(A)
Pr(A | B) =
Pr(B)
On l'emploie pour estimer la probabilité qu'un nouveau patient soit sain, 
atteint d'une hernie discale ou d'une spondylolisthésis, à partir d'une estimée
gaussienne de la loi de probabilité de chaque donnée biométrique dans le cas
d'un patient typique de l'un des trois groupes (sain, hernie discale ou 
spondylolisthésis).
Ce sujet est complet, regroupant de traditionnelles questions de programmation
en Python avec des questions d'écriture de requêtes de bases de données en SQL.
Il permet de retravailler les algorithmes de base de recherche du maximum d'un
tableau, de tri d'une liste et d'affichage de graphiques à l'aide de la 
bibliothèque
matplotlib. L'originalité tient à la découverte de deux algorithmes 
d'apprentissage
automatique, permettant de toucher aux thématiques d'intelligence artificielle 
qui
sont au coeur de recherches actives.

Indications
Partie II
1 Utiliser une requête SELECT avec un test d'égalité entre un champ et une 
chaîne
de caractères.
2 Joindre les deux tables en identifiant la clé primaire id et le champ 
idpatient.
3 On peut compter un nombre d'éléments dans une colonne à l'aide de la fonction
d'agrégation COUNT.
6 Si on souhaite utiliser la fonction append permettant d'ajouter des éléments 
à la
fin d'une liste, il est préférable de renvoyer une liste de listes de tableaux 
Numpy.
7 Attention au décalage d'indice : le i-ième attribut est ainsi représenté dans 
les
colonnes et lignes d'indice i - 1 de la matrice de diagrammes.
Partie III
9 Trouver une opération affine permettant de passer de X à Xnorm .
11 On pourra charger la fonction sqrt de la bibliothèque math.
14 Attention, l'énoncé n'est pas cohérent avec la spécification qu'il a donnée 
de la
fonction tri qui était censée trier une liste de listes à deux éléments où le 
second
élément de chaque liste est la valeur de l'état, et non l'indice du patient 
dans la
liste data.
15 Essayer de faire apparaître les notions de taux de réussite, de faux 
positifs et de
faux négatifs.
17 Pour calculer la variance, profiter de la fonction moyenne juste écrite.
18 Utiliser la fonction separationParGroupe, ainsi que les fonctions de la 
question 17.
19 L'énoncé est imprécis : il s'agit plutôt de calculer la valeur que prend en 
a la
fonction de densité de la loi gaussienne de moyenne moy et de variance v.
20 On peut estimer le terme Pr(Y = yj ) à l'aide de la proportion de patients 
d'état yj .
23 Comparer les taux de réussite, ainsi que les taux de faux positifs et de faux
négatifs.

Dans ce corrigé, on suppose chargées les bibliothèques Numpy (comme le
suggère l'annexe) et matplotlib (comme le suggère le code donné pour la
question 7) à l'aide du code
from numpy import *
import matplotlib.pyplot as plt

II. Analyse des données
1 L'état d'un patient, ainsi que son identifiant, se trouvent dans la table 
medical.
Il suffit donc d'extraire l'identifiant idpatient de tous les enregistrements 
dont l'état
vaut « hernie discale » :
SELECT idpatient FROM medical
WHERE etat = "hernie discale";
2 Les noms et prénoms sont stockés dans la table patient alors que l'état se
trouve dans la table medical. Il faut donc procéder à une jointure reliant la 
clé
primaire id de la table patient au champ idpatient de la table medical. On 
filtre
en même temps pour ne conserver que les enregistrements de la jointure où l'état
vaut « spondylolisthésis » :
SELECT nom,prenom FROM patient
JOIN medical
ON patient.id = medical.idpatient
WHERE etat = "spondylolisthésis";
3 Pour compter le nombre de patients d'un état particulier, on peut utiliser la
fonction COUNT, en prenant soin de grouper les enregistrements par etat à 
l'aide du
mot clé GROUP BY :
SELECT etat, COUNT(idpatient) FROM medical
GROUP BY etat;
L'énoncé ne spécifie pas précisément ce qu'il entend par « nombre de patients
pour chaque état ». En particulier, si un même patient apparaît plusieurs fois
dans la table medical, avec le même état, chaque occurrence est comptée
par COUNT(idpatient). Pour éviter ces doublons, on peut utiliser la requête
suivante utilisant le mot-clé DISTINCT :
SELECT etat, COUNT(DISTINCT idpatient) FROM medical
GROUP BY etat;
4 La gestion des tableaux Numpy de grande taille est plus efficace que celle 
des listes
Python. Par exemple, le parcours de tableaux est plus rapide en Numpy. La 
bibliothèque Numpy contient également de nombreuses fonctions vectorielles 
(somme, produit matrice/colonne, etc.) implémentées, en particulier pour les 
tableaux de grandes
tailles, bien plus rapides que celles qu'on pourrait obtenir via un parcours de 
listes
(ou de listes de listes). Pour résumer,
La gestion des tableaux de grandes tailles par la bibliothèque Numpy est plus 
efficace que par les listes Python.
Une raison principale de l'efficacité de Numpy, vis-à-vis des listes Python, est
l'hétérogénéité possible des listes Python : une même liste peut contenir dans

différentes cases des entiers, des nombres à virgule flottante, des chaînes de
caractères, etc. Cela force Python à stocker ces listes à l'aide de pointeurs. 
Au
contraire, la bibliothèque Numpy force les tableaux à ne contenir qu'un seul
type d'éléments, que ce soit des entiers ou des nombres à virgule flottante :
chaque élément est donc stocké dans un même nombre de bits, ce qui permet
à Numpy d'utiliser des blocs consécutifs en mémoire, évitant le stockage de
pointeurs. Un tableau Numpy prend donc moins d'espace mémoire que le
même tableau géré par une liste Python, et il est plus facile à parcourir
efficacement.
5 Le tableau data est une matrice contenant N = 100 000 lignes et n = 6 
colonnes,
chaque case contenant un réel codé sur 32 bits, c'est-à-dire 4 octets. Ainsi, 
il requiert
au total N × n × 4 octets de mémoire, c'est-à-dire 2,4 Mo.
Le tableau etat est un vecteur de taille N contenant des valeurs entières codées
sur 8 bits, c'est-à-dire 1 octet. Ainsi, la quantité de mémoire nécessaire pour 
le stocker
est de N octets, c'est-à-dire 0,1 Mo. Au total,
Stocker les tableaux data et etat avec N = 100 000 patients requiert 2,5 Mo.
L'indication de l'énoncé de « supposer que les données sont représentées en
suivant la norme usuelle IEEE 754 » semble inutile, puisque l'énoncé précise
plus haut que les réels sont représentés par des nombres à virgules flottantes
codés sur 32 bits. Par ailleurs, le programme ne stipule aucune connaissance
requise sur cette norme.
6 On choisit de renvoyer une liste groupes de trois listes de tableaux Numpy,
permettant d'ajouter en fin de chacune des trois listes des éléments à l'aide 
de la
méthode append, ce qu'on ne peut pas faire facilement avec des tableaux Numpy.
Après avoir ainsi créé la liste de trois listes vides, on parcourt les éléments 
du tableau
data pour les ajouter un à un à la liste convenable selon l'état qu'on trouve 
dans la
case correspondante du tableau etat.
def separationParGroupes(data, etat):
groupes = [[] for _ in range(3)]
for i in range(len(data)):
groupes[etat[i]].append(data[i])
return groupes
On a utilisé le symbole _ dans la définition par compréhension de la liste de
listes groupes : ce symbole peut remplacer une variable qu'on n'utiliserait
pas par la suite, permettant ainsi à l'utilisateur de ne pas avoir à réfléchir à
un nom de variable significatif.
7 Après avoir séparé les données par groupes, et avoir transformé la liste de 
données
associées à chaque état en un tableau Numpy, le code entre dans une double 
boucle
permettant de dessiner indépendamment chaque graphique de coordonnées (i, j),
pour i, j  [[ 0 ; n-1 ]]. On commence donc par sélectionner le graphique 
correspondant
dans la matrice à l'aide de la ligne
ax1 = plt.subplot(n, n, i*n+j+1)
puisqu'il y a une matrice de graphique contenant n lignes et n colonnes, et que 
le
graphique de coordonnées (i, j) est le (in + j + 1)-ième en allant de gauche à 
droite
et de haut en bas.