CI n°3 – Tableaux, listes chaînées, listes – Piles et files

Bienvenue dans ce troisième CI… Très abstrait, que les TPs devraient éclaircir !

Le pdf complet des chapitres 4 et 5 :

Chapitre 4 : Tableaux et listes chaînées, listes de python

cm 2020-04-06 CI3 01cm 2020-04-06 CI3 02cm 2020-04-06 CI3 03cm 2020-04-06 CI3 04cm 2020-04-06 CI3 05

Chapitre 5 : Piles et files et leurs primitives … à implémenter de trois manières

cm 2020-04-06 CI3 06cm 2020-04-06 CI3 07cm 2020-04-06 CI3 08cm 2020-04-06 CI3 09cm 2020-04-06 CI3 10cm 2020-04-06 CI3 11cm 2020-04-06 CI3 12cm 2020-04-06 CI3 13

Un essai vidéo, c’est pas le top, mais on fait ce qu’on peut…

cm 2020-04-06 CI3 14cm 2020-04-06 CI3 15cm 2020-04-06 CI3 16cm 2020-04-06 CI3 17cm 2020-04-06 CI3 18cm 2020-04-06 CI3 19

Des projets NSI ?

Je vais vous évaluer au troisième trimestre, si… si…, et votre projet sera une clé de voûte de cette évaluation.

A combien ?

A deux ou à trois, c’est mieux qu’à un, même si ce n’est pas interdit au vu de la situation sanitaire.

Et c’est quoi ?

Un programme python.

  • bien découpé en sous-fonctions, bien documenté,
  • avec des tâches bien réparties entre les membres du groupe.

Ça peut être un jeu, une animation pygame qui met en lumière des algorithmes au programme…

Je n’ai pas d’idée !

Alors tu peux :

Ok, on est un équipe, on a une idée !

Alors inscrivez-vous via les commentaires !

 

Un exemple d’algorithme d’apprentissage : algorithme des k plus proches voisins

L’exercice pour aujourd’hui préparait la suite, on commence par le corriger.

Figure_1

Introduction

L’algorithme des k plus proches voisins appartient à la famille des algorithmes d’apprentissage automatique (machine learning).

L’idée d’apprentissage automatique ne date pas d’hier, puisque le terme de machine learning a été utilisé pour la première fois par l’informaticien américain Arthur Samuel en 1959.

Les algorithmes d’apprentissage automatique ont connu un fort regain d’intérêt
au début des années 2000 notamment grâce à la quantité de données disponibles sur internet.

L’algorithme des k plus proches voisins est un algorithme d’apprentissage supervisé, il est nécessaire d’avoir des données labellisées.

À partir d’un ensemble E de données labellisées, il sera possible de classer (déterminer le label) d’une nouvelle donnée (donnée n’appartenant pas à E).

Stop ! Arrêtez le jargon !

Ok, vous savez ce qu’est la reconnaissance faciale sur un téléphone ? Un « Captcha » ? Ou vous avez entendu parler d’une voiture qui détecterait toute seule les passages pour piétons ?

Bienvenue dans le monde du « machine learning » ou « apprentissage automatique ».

En gros, on va donner une belle quantité de données à une machine, en disant « ça c’est tel label » ou « ceci tel autre label »pour qu’elle décide si une nouvelle donnée est d’un certain « label » ou pas.

Ah ok. Et comment on va s’y prendre ?

Comme dans le TP pour aujourd’hui. Et après, on découvre un nouvel algorithme … au programme … qu’on programme !

Dans le vif du sujet : nos données

Le TP que je propose est une version simplifiée d’un TP proposé par de nombreuses sources, officielles ou pas.
C’est une histoire de classification de fleurs, des iris, avec des labels. Ne vous étonnez pas d’en voir partout.

On a déjà travaillé avec des fichiers csv. Celui du jour est .

On va utiliser le même code que pour le « mignon » pour représenter graphiquement nos données.

Exemple 1 :

En gros, pour bien poser la problématique : le nouvel élément représenté en noir ci-dessous, avec le label « nouveau » mérite-t-il

  • le label « setosa »,
  • le label « virginica »,
  • le label « versicolor » ?

Figure_1

Sans hésitation, le point noir étant dans un nuage de points rouges, nous tranchons : le label « virginica ».

Exemple 2 :

Et là ?

Figure_2

Oh, et bien, le point noir étant « très proche » du nuage de points verts, nous tranchons : le label « setosa ».

Comment ça « dans un nuage » ou « très proche » ?

Pour nous, c’est instantané et très visuel avec une telle représentation graphique, mais comment un ordinateur peut-il être programmé pour ça ?

D’autant plus que même pour nous, ce n’est pas toujours évident 😦

Exemple 3 :

Figure_3

Programmons !

Je vous mets à nouveau à disposition un fichier csv, téléchargeable ici (bouton droit, enregistrer sous, iris_3col.csv). A l’aide de ce fichier, réaliser les graphiques ci-dessus :

Il faut placer le nouveau avec :

# nouveau
# x_new, y_new = 6, 2       # cas 1 simplissime
# x_new, y_new = 2, 0.5    # cas 2 facile
x_new, y_new = 2.5, 0.75  # cas 3 problématique
plt.scatter([x_new], [y_new], color = 'black', label = 'nouveau')

Correction à la fin du billet en cliquant sur « lire la suite ».

Comment décider du label du « nouveau » ?

Ok, il faut un critère de décision :

  • moins subjectif qu’un « dans un nuage » ou un « très proche »,
  • algorithmique pour qu’une machine puisse décider.

L’algorithme « k-NN » des k plus proches voisins

« k – NN » car en anglais, il s’appelle « knearest neighbors algorithm ».

Les plus proches ?

cm 2020-04-06 knn_à_la_recherche_d_une_idee

On voit bien dans le décompte des voisins que le choix du nombre k est important ! Ça fait partie des « leviers » de tous les spécialistes du « deep learning ».

Influence de k. Pour :

  • k == 1 on dirait que le nouveau devrait avoir le label versicolor car on a 1 voisin bleu et 0 voisin vert,
  • k == 2 on ne saurait dire quel label devrait avoir le nouveau car on a 1 voisin bleu et 1 voisin vert,
  • k == 3 on dirait que le nouveau devrait avoir le label setosa car on a 1 voisin bleu et 0 voisin vert,
  • etc.

Programmons !

Voici le principe de l’algorithme des k plus proches voisins :

  • Il nous faut une distance. Écrire une fonction distance(x1, y1, x2, y2) qui calcule et renvoie la distance entre deux points de coordonnées (x1, y1) et (x2, y2) dans un repère orthonormé (formule de seconde).
    Pendant le cours, on a écrit :

    from math import sqrt
    
    def distance(x1, y1, x2, y2):
        sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
  • On calcule les distances entre le nouveau et chaque donnée de notre fichier csv à l’aide de la fonction programmée
  • On retient les k données du jeu de données les plus proches de nouveau.
    Pendant le cours, on a proposé :

    • de trier la liste en prenant cette distance comme critère, par ordre croissant,
    • de garder les k premier éléments de cette liste.
  • On attribue à nouveau la classe qui est la plus fréquente parmi les k données les plus proches.

Allons-y : à vous ! Je ne proposerai pas de correction ici mais accompagnerai toutes celles et tous ceux qui voudront aller au bout de ce travail, un peu comme un « devoir maison » pendant ces congés à venir… Mercredi, on reprend avec des pages web 😀

Ces trois appels de ma fonction k_plus_proches_voisins avec notre couple x_new, y_new = 2.5, 0.75

k_plus_proches_voisins(x_new, y_new, 3)
k_plus_proches_voisins(x_new, y_new, 5)
k_plus_proches_voisins(x_new, y_new, 42)

donnent :

Algorithme des 3 plus proches voisins.

Les 3 plus proches voisins sont de label
versicolor à la distance 0.6103277807866851
setosa à la distance 0.6946221994724903
setosa à la distance 0.8139410298049854

Le label le plus représenté est setosa
Il a atteint le maximum, 2 occurences, en premier
Notre choix est donc le label setosa

Algorithme des 5 plus proches voisins.

Les 5 plus proches voisins sont de label
versicolor à la distance 0.6103277807866851
setosa à la distance 0.6946221994724903
setosa à la distance 0.8139410298049854
versicolor à la distance 0.8381527307120104
versicolor à la distance 0.8381527307120104

Le label le plus représenté est versicolor
Il a atteint le maximum, 3 occurences, en premier
Notre choix est donc le label versicolor

Algorithme des 42 plus proches voisins.

Les 42 plus proches voisins sont de label
versicolor à la distance 0.6103277807866851
setosa à la distance 0.6946221994724903
setosa à la distance 0.8139410298049854
versicolor à la distance 0.8381527307120104
versicolor à la distance 0.8381527307120104
setosa à la distance 0.8381527307120106
setosa à la distance 0.873212459828649
...
setosa à la distance 1.2298373876248845
setosa à la distance 1.2298373876248845

Le label le plus représenté est setosa
Il a atteint le maximum, 36 occurences, en premier
Notre choix est donc le label setosa
>>>

Lire la suite