Aller au contenu

Un jeu de données sur le diabète☘

Ces exercices doivent être utilisés pour vous entraîner à programmer. Ils sont généralement accompagnés d'aide et de leur solution pour vous permettre de progresser.

Avant de vous précipiter sur ces solutions dès la première difficulté, n'oubliez pas les conseils suivants :

  • Avez-vous bien fait un schéma au brouillon pour visualiser le problème posé ?
  • Avez-vous essayé de rédiger un algorithme en français, avec vos propres mots, avant de vous lancer dans la programmation sur machine ?
  • Avez-vous utilisé des affichages intermédiaires, des print(), pour visualiser au fur et à mesure le contenu des variables ?
  • Avez-vous testé le programme avec les propositions de tests donnés dans l'exercice ?
  • Avez-vous testé le programme avec de nouveaux tests, différents de ceux proposés ?
Rappels
  • Pour exécuter ce programme, il suffit de le sauvegarder puis d'appuyer sur la touche [F5].
  • Le programme principal doit contenir un appel au module doctest : 
    ##----- Programme principal et tests -----##
if __name__ == '__main__':
    import doctest
    doctest.testmod()

Introduction☘

Les exercices de cette page sont issus d'une situation commune, décrite ci-après. Toutes les fonctions devront être sauvegardées dans le même fichier.

Téléchargez ce fichier à compléter ProgG06.60.py (clic droit -> [Enregistrer sous]) et enregistrez-le dans le dossier [G06_Algo_KNN].

Le problème☘

On dispose d'une base de données sur le diabète, à télécharger présentant huit colonnes de diverses mesures (insuline, âge, ...). La neuvième colonne présente des 0 et des 1 :

  • 1 signifie que la personne suit un traitement pour des problèmes liés au diabète,
  • 0 qu'elle n'en suit pas.

Il s'agit de nos deux classes pour ce problème.

Partie A - Préparer la base de données☘

Un patient est caractérisé par neuf données. Utiliser un dictionnaire pour décrire ce patient risque d'être laborieux (surtout à la lecture des attributs).

Dans cette partie, vous allez importer les données et les stocker dans un tableau de tableaux, où chaque sous-tableau sera de la forme [a, b, c, d, e, f, g, h, i] telle que a représente la valeur du premier attribut, b celle du deuxième attribut, etc...

  1. Complétez la définition de la fonction importation() en respectant ses spécifications. Seules les valeurs des attributs 'Body mass index (weight in kg/(height in m)^2)' et 'Diabetes pedigree function' doivent être flottantes, les autres doivent être entières.

    1
2
3
4
5
    def importation(nom_fichier):
    """
    nom_fichier - str, nom du fichier csv à importer
    Sortie: list - Tableau de tableaux représentant les données
    """
    Une piste

    Vous pouvez :

    • soit effectuer une importation à l'aide de la fonction importe_csv() mais il faut alors faire attention de ne pas perturber l'ordre des attributs...
    • soit travailler directement sur le fichier CSV à partir des méthodes étudiées dans ce chapitre.
    Une solution

    Solution avec la fonction importe_csv() : 

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
    def importation(nom_fichier):
    """
    nom_fichier - str, nom du fichier csv à importer
    Sortie: list - Tableau de tableaux représentant les données
    """
    base = importe_csv(nom_fichier)
    result = [[] for _ in range(len(base))]

    info = base[0]
    for clef in info:
        print(clef)
        for i in range(len(base)):
            if clef != 'Diabetes pedigree function' and clef != 'Body mass index (weight in kg/(height in m)^2)':
                result[i].append(int(base[i][clef]))
            else:
                result[i].append(float(base[i][clef]))
    return result

    Une autre solution

    Solution avec un traitement direct du fichier : 

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
    def importation(nom_fichier):
    """
    nom_fichier - str, nom du fichier csv à importer
    Sortie: list - Tableau de tableaux représentant les données
    """
    with open(nom_fichier, 'r', encoding='utf-8') as f_source:
        tab_lignes = f_source.readlines()
        tab_lignes.pop(0)

        result = []
        for ligne in tab_lignes:
            ligne.rstrip('\n')          # On enlève le saut en fin de ligne
            tab = ligne.split(',')      # On transforme la ligne en tableau
            for i in range(len(tab)):   # On transtype les éléments
                if i != 5 and i != 6:
                    tab[i] = int(tab[i])
                else:
                    tab[i] = float(tab[i])
            result.append(tab)
        return result

  2. Exécutez votre fonction en important la base diabete.csv puis vérifiez que les premiers tableaux de cette base sont ceux listés ci-dessous :

    1
2
3
4
5
6
7
8
9
    >>> for tab in BASE_DE_DONNEES:
...     print(tab)

[6, 148, 72, 35, 0, 33.6, 0.627, 50, 1]
[1, 85, 66, 29, 0, 26.6, 0.351, 31, 0]
[8, 183, 64, 0, 0, 23.3, 0.672, 32, 1]
[1, 89, 66, 23, 94, 28.1, 0.167, 21, 0]
[0, 137, 40, 35, 168, 43.1, 2.288, 33, 1]
[5, 116, 74, 0, 0, 25.6, 0.201, 30, 0]

Partie B - Classifier un nouveau patient☘

Un nouveau patient est caractérisé par les mesures suivantes :

1
nouveauPatient = [1, 89, 67, 24, 80, 23.0, 0.6, 65]

Ce client devra-t-il suivre un traitement ?

  1. Complétez la définition de la fonction distance() qui doit renvoyer la distance euclidienne entre deux données (représentées par des tableaux) sur les NB_DONNEES premiers éléments de chaque tableau.

    1
2
3
4
5
    def distance(donnee1, donnee2):
    """
    donnee1, donnee2 - list, tableaux dont on cherche la distance
    Sortie: float - Distance euclidienne entre les deux données
    """

    Exemple de test

    >>> donnee1 = [1, 121, 78, 39, 74, 39.0, 0.261, 28, 0]
>>> donnee2 = [2, 127, 46, 21, 335, 34.4, 0.176, 22, 0]
>>> distance(donnee1, donnee2)
263.7483027907478
    Une piste

    La distance distance euclidienne entre A(x, y, z, t) et B(a, b, c, d) est : \sqrt{(x-a)^2 + (y-b)^2 + (z-c)^2 + (t-d)^2}.

    Une solution
    1
2
3
4
5
6
7
8
9
    def distance(donnee1, donnee2):
    """
    donnee1, donnee2 - list, tableaux dont on cherche la distance
    Sortie: float - Distance euclidienne entre les deux données
    """
    somme = 0
    for i in range(NB_DONNEES):
        somme += (donnee1[i] - donnee2[i])**2
    return sqrt( somme )
    Remarque

    Dans ce qui précède, on calcule des distances en utilisant des coordonnées qui ne sont pas comparables a priori (unités différentes, significations différentes, ...). Ce qui ne semble pas avoir beaucoup de sens a priori.

    Nous avons en fait simplifié l'ensemble en passant sous-silence tout le travail de prétraitement des données qui est nécessaire mais trop technique pour nous concentrer seulement sur le principe, au risque de conclusions non pertinentes !

  2. Complétez la définition de la fonction k_plus_proches() qui doit renvoyer le tableau des k données de la base les plus proches de la donnée à classifier.

    1
2
3
4
5
6
7
8
9
    def k_plus_proches(k, a_classer, BDD):
    """
    k - int, entier strictement positif (nombre de voisins)
    a_classer - list, tableau contenant NB_DONNEES éléments
    BDD - list, Tableau de tableaux contenant (NB_DONNEES + 1) éléments

    Sortie: list - tableau des k tableaux contenus dans BDD
                   les plus "proches" de a_classer
    """

    Exemple de test

    >>> nouveauPatient = [1, 89, 67, 24, 80, 23.0, 0.6, 65]
>>> k_plus_proches(1, nouveauPatient, BASE_DE_DONNEES)
[[7, 94, 64, 25, 79, 33.3, 0.738, 41, 0]]

>>> k_plus_proches(3, nouveauPatient, BASE_DE_DONNEES)
[[7, 94, 64, 25, 79, 33.3, 0.738, 41, 0],
 [5, 96, 74, 18, 67, 33.6, 0.997, 43, 0],
 [3, 89, 74, 16, 85, 30.4, 0.551, 38, 0]]

>>> k_plus_proches(5, nouveauPatient, BASE_DE_DONNEES)
[[7, 94, 64, 25, 79, 33.3, 0.738, 41, 0],
 [5, 96, 74, 18, 67, 33.6, 0.997, 43, 0],
 [3, 89, 74, 16, 85, 30.4, 0.551, 38, 0],
 [1, 95, 74, 21, 73, 25.9, 0.673, 36, 0],
 [7, 83, 78, 26, 71, 29.3, 0.767, 36, 0]]
    Une piste

    Vous pouvez creer un tableau vide, à remplir avec des couples constitués de chaque donnée et de sa distance avec la donnée a_classer.

    Triez ensuite ce tableau selon les distances puis renvoyez un tableau des k premières données (sans les distances).

    Une solution

    On définit une fonction supplémentaire comme critère de tri. 

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
    def critere_2nd_elt(couple):
    return couple[1]


def k_plus_proches(k, a_classer, BDD):
    """
    k - int, entier strictement positif (nombre de voisins)
    a_classer - list, tableau contenant NB_DONNEES éléments
    BDD - list, Tableau de tableaux contenant (NB_DONNEES + 1) éléments

    Sortie: list - tableau des k tableaux contenus dans BDD
                   les plus "proches" de a_classer
    """
    tab_couples = []
    for donnee in BDD:
        dist = distance(a_classer, donnee)
        tab_couples.append( (donnee, dist) )

    tab_couples.sort(key=critere_2nd_elt)

    result = []
    for i in range(k):
        result.append(tab_couples[i][0])
    return result

  3. Terminez cette parte en complétant la définition de la fonction classification() puis conclure en répondant à la question initiale : « ce client devra-t-il suivre un traitement ? ».

    1
2
3
4
5
6
7
8
    def classification(k, a_classer, BDD):
    """
    k - int, entier strictement positif (nombre de voisins)
    a_classer - list, tableau contenant NB_DONNEES éléments
    BDD - list, Tableau de tableaux contenant (NB_DONNEES + 1) éléments

    Sortie: str - classe de a_classer obtenue selon le principe k-NN
    """

    Exemple de test

    >>> nouveauPatient = [1, 89, 67, 24, 80, 23.0, 0.6, 65]
>>> classification(1, nouveauPatient, BASE_DE_DONNEES)
'0'

>>> classification(3, nouveauPatient, BASE_DE_DONNEES)
'0'

>>> classification(5, nouveauPatient, BASE_DE_DONNEES)
'0'

>>> nouveauPatient = [6, 148, 72, 35, 0, 33.6, 0.627, 50]
>>> classification(5, nouveauPatient, BASE_DE_DONNEES)
'1'

>>> classification(7, nouveauPatient, BASE_DE_DONNEES)
'0'

>>> classification(9, nouveauPatient, BASE_DE_DONNEES)
'1'
    Une piste

    Faîtes appel au dictionnaore DICO défini dans les constantes pour décompter les classes parmi les voisins les plus proches.

    N'oubliez pas de réinitialiser le dictionnaire en fin d'appel de la fonction...

    Une solution
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
    def classification(k, a_classer, BDD):
    """
    k - int, entier strictement positif (nombre de voisins)
    a_classer - list, tableau contenant NB_DONNEES éléments
    BDD - list, Tableau de tableaux contenant (NB_DONNEES + 1) éléments

    Sortie: str - classe de a_classer obtenue selon le principe k-NN
    """
    kppv = k_plus_proches(k, a_classer, BDD)

    for donnee in kppv:
        DICO[str(donnee[-1])] += 1

    max = 0
    for clef in DICO.keys():
        if DICO[clef] > max:
            max = DICO[clef]
            classe = clef
    # On ré-initialise le dictionnaire
    for clef in DICO.keys():
        DICO[clef] = 0
    return classe

Partie C - Fiabilité de la méthode☘

On aimerait avoir une idée de la fiabilité de la méthode.

Pour cela, on découpe les données en deux parties :

  • une partie BD qui contiendra une certaine proportion des données du fichier. Par exemple 90 % des données.
  • une partie TEST qui contiendra le reste des données.

Comme on connaît la classe des individus de TEST, on peut vérifier la proportion de bonnes réponses par la méthode sur les éléments de TEST en utilisant BD comme jeu de données.

  1. Complétez la définition de la fonction extraction() qui renvoie le couple (BD, TEST).
    Vous utiliserez l'extraction aléatoire suivante : pour chaque donnée de BASE_DE_DONNEES, cette donnée est placée une fois sur dix dans le tableau TEST, sinon elle est placée dans BD.

    1
2
3
4
5
6
7
8
    def extraction(BDD):
    """
    BDD - list, Tableau de tableaux contenant (NB_DONNEES + 1) éléments

    Sortie: tuple - couple de tableaux,
                    le premier est constitué d'environ 90% des tableaux de BDD
                    le second est constitué des tableaux restant
    """
    Une solution

    On fait appel à la fonction randint() du module random. 

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
    def extraction(BDD):
    """
    BDD - list, Tableau de tableaux contenant (NB_DONNEES + 1) éléments

    Sortie: tuple - couple de tableaux,
                    le premier est constitué d'environ 90% des tableaux de BDD
                    le second est constitué des tableaux restant
    """
    BD = []
    TEST = []
    for donnee in BDD:
        if randint(1, 10) == 1:
            TEST.append(donnee)
        else:
            BD.append(donnee)
    return BD, TEST

    Une autre solution

    On mélange la BASE_DE_DONNEES à l'aide de la fonction shuffle() présente dans le module random puis on garde 90% des lignes à partir du début pour la table BD et les 10% restant pour la table TEST.

    A vous de l'implémenter...

  2. Complétez la définition de la fonction fiabilite() qui renvoie le pourcentage des données de TEST qui obtiennent une bonne classification quand on les compare avec leurs k plus proches voisins dans la base BD, où k est un paramètre de la fonction. 

    1
2
3
4
5
6
7
8
    def fiabilite(k, BD, TEST):
    """
    k - int, entier strictement positif (nombre de voisins)
    BD, TEST - list, tableaux de tableaux contenant (NB_DONNEES+1) éléments
    Sortie: float - Renvoie le pourcentage de bonnes classifications
                    lorsqu'on teste les données de la liste TEST
                    avec le reste des données présentes dans BD
    """

    Exemple de test

    >>> BD, TEST = extraction(BASE_DE_DONNEES)
>>> for k in range(1, 11):
...     print(fiabilite(k, BD, TEST))

0.6153846153846154
0.717948717948718
0.6282051282051282
0.7307692307692307
0.6923076923076923
0.7307692307692307
0.7051282051282052
0.7564102564102564
0.7307692307692307
0.7307692307692307
    Une solution

    Attention au type des données renvoyé par la fonction classification(). 

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
    def fiabilite(k, BD, TEST):
    """
    k - int, entier strictement positif (nombre de voisins)
    BD, TEST - list, tableaux de tableaux contenant (NB_DONNEES+1) éléments
    Sortie: float - Renvoie le pourcentage de bonnes classifications
                    lorsqu'on teste les données de la liste TEST
                    avec le reste des données présentes dans BD
    """
    nb_succes = 0 # nombre de bonnes réponses
    for test in TEST:
        reponse = classification(k, test, BD)
        if reponse == str(test[-1]): 
            nb_succes += 1
    return nb_succes/len(TEST)

    Conclusion

    Le mélange des données permet que la partie extraite servant de base de référence soit modifiée à chaque exécution de la fonction extraction(). On obtient des taux de succès entre 60% et 90% en faisant quelques essais avec k = 10.

    A vous de faire des essais avec d'autres valeurs de k.