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)
        

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.