Coder un anti-spam

Ebauche (en cours de validation)

Cette situation prend la suite de l’activité de classification proposée en collège. Rappelons la : on dispose de deux nuages de points, un nuages de points bleus et un nuages de points rouges. On veux déterminer la couleur d’un point dont on connait les coordonnées. Nous proposons dans ce document aux élèves de mettre en œuvre le même type de techniques d’apprentissage supervisée par classification.
Dans cette seconde étape, on choisit de contextualiser la situation en proposant de fabriquer un filtre anti-spam en utilisant uniquement trois informations :

• le nombre de destinataires du message (abscisse),
• le nombres de signalements du message (ordonnée)
• l’information si c’est un spam ou non.

Un choix de simplification

Afin que l’activité soit réalisable quelque soit la classe de lycée nous proposons d’utiliser la technique suivante.

• On détermine les points moyens de chacun des ensembles de données et  (spams) et (propres).
• On décide qu’un mail indéterminé est un spam s’il est plus proche de que de.
• Ainsi, la frontière de décision est alors la médiatrice du segment [].
• On peut décider avec que si un point est sur la frontière de décision, alors ce n’est pas un spam (on prend le moins de risques possibles).

Une proposition de scénario

La situation

Voici l’énoncé qui pourrait être proposé aux élèves.

Dévolution du problème

C’est une phase importante qui permet de s’assurer que tous les élèves ont compris quelle est la question ou quel est le problème. On peut demander aux élèves de reformuler la question. Normalement le passage par l’activité d’intelligence artificielle proposé par le groupe au niveau collège, à jouer en préalable en classe de seconde, crée un milieu favorable à la compréhension de la situation. Les élèves devraient penser à la représentation des couples de nombres sous la forme d’un nuage de points.

Nous pouvons obtenir les formulations suivantes :
"Nous devons donc proposer un algorithme et en proposer une programmation."
" Il nous faut proposer une technique ou un critère de décision pour déterminer si un message nouveau est un spam ou non. "

Débat avec les élèves pour décider d’une technique

Il est important de laisser les élèves proposer des solutions. Afin qu’ils puissent les faire, on peut laisser un dizaine de minutes pour les laisser en discuter avec leurs voisins.

Lors d’une première mise en commun on peut noter au tableau toutes les propositions, en les structurant, sans que le professeur donne son avis.

Pour autant, il va falloir guider les élèves vers une solution qu’ils seront capable de réaliser. Ensuite en tant que directeur de recherche le professeur va guider les élèves vers une réflexion, dans un premier temps, géométrique.

Nous proposons des questions cruciales qui sont l’outil principal de la direction d’une démarche d’investigation en mathématiques. Elles ne seront pas dévoilées en début de recherche , elle permettront au professeur de guider la réflexion des élèves. Nous espérons que la médiatrice émergera sans avoir besoin de poser toutes ces questions à l’oral.

1. Est-ce que vous vous rappelez l’activité avec des points rouges et des points bleus ? Peut-on s’en inspirer ?
2. Quelle droite pouvez-vous proposer comme frontière de décision ?
3. Comment résumer tous les points du data set considérés comme des spams ?
4. Comment résumer tous les points du data set considérés comme propres ?
5. Maintenant en utilisant les points moyens, quel critère de décision pouvez-vous proposer ?

Il faudra ensuite assurer une transition algébrique en utilisant les propriétés de la médiatrice sur la partition du plan.

Programmation

Un travail doit être fait avec les élèves de découpage du problème en sous-problèmes.

Avant que les élèves commencent à programmer il est nécessaire d’avoir décider des fonctions Python dont on a besoin. Une possibilité est proposée ci-dessous :

• Une fonction Python moyenne qui prend en paramètre une liste de couples et un entier entre (pour l’abscisse) et (pour l’ordonnée) et qui renvoie la moyenne des abscisses ou des ordonnées.
• Une fonction point_moyen qui prend en paramètre une liste de couples et renvoie les coordonnées du point moyen.
• Une fonction distance_carre qui prend en paramètre deux couples et renvoie la distance au carré entre ces points.[1]
• Une fonction est_spam qui prend en paramètre deux listes de couples (coordonnées de points), celle des points spam et celle non spam, et un couple (coordonnées du point dont on souhaite déterminer s’il est spam ou pas). Cette fonction renvoie un booléen : vraie si c’est un spam, faux sinon.

Il faudra aboutir aux fonctions décidées dans le code. Un exemple de programmation est donné en annexe.

Bilan final

Ce bilan final doit participer de l’institutionnalisation de connaissances d’algorithmique et programmation relevant des programmes de mathématiques :

• instruction conditionnelle,
• boucles,
• listes,
• liste par compréhension,

mais aussi de connaissances sur l’intelligence artificielles sur les notions :

• d’apprentissage supervisée,
• de classifications,
• d’ensemble de données d’apprentissage,
• phase d’apprentissage,
• phase de test.

Il faudra aussi insister sur la notion transversale de modélisation. En effet, un choix a été fait : résumer chaque nuage par son point moyenne et partitionner le plan par la médiatrice.

Limites de la stratégie proposée

Notion d’apprentissage supervisée

Les notion fondamentales de l’apprentissage supervisée sont :

1. Importer les données d’apprentissages (data set) qui doivent contenir les caractéristiques (feature) et la cible (target).
     (le nombre d’erreurs de syntaxes), (le nombre de liens dans le message), ... , sont les caractéristiques.
   y (est un spam) qui peut prendre deux valeurs True ou False ( 0 ou 1 ) est la cible.
2. Décider d’un modèle :
   • ◦ par régression (linéaire ou non), la descente de gradient étant la technique la plus classique ;
   • ◦ par classification

Le modèle est un choix humain. Le rôle de la machine est de trouver les paramètres de ce modèle.

3. Développer une fonction coût, qui mesure l’ensemble des erreurs entre notre modèle et le dataset (x , y ).
4. Développer un algorithme de minimisation de la fonction coût, qui trouve quels sont les paramètres optimaux pour notre modèle.
5. Utiliser un jeu de données de tests distinct de celui d’apprentissage afin de mesurer l’efficacité de l’algorithme.

Conclusion

On voit bien que notre stratégie ne passe pas par les étapes 3. 4. et 5.

Possibilités de poursuites

1. Amélioration de l’algorithme distinguant clairement un ensemble d’apprentissage et un ensemble de test distincts choisis au hasard dans une base de données. On pourra y développer des méthodes statistiques pour mesurer la performance (en seconde).
   La figure ci-dessous illustre une phase d’apprentissage (croix) suivie d’une phase de test (étoiles). Les spams sont codés en rouges et les propres en bleus. Sur cet exemple, 16 % des spams ont été mal classés contre 0% des propres. Ces performances sont à relativiser eût égard à la taille réduite des jeux de données utilisées.

2. Algorithme des k plus proches voisins (en première NSI).
3. En terminale, utiliser trois caractéristiques pour une modélisation dans l’espace (plan médiateur) et pour des bons élèves en n dimensions.

[1]Programmer le calcul de la distance au carré est préférable, car cela permet d’éviter de comparer des nombres flottants (argument informatique), de calculer des racines carrées (temps de calcul) et nous donne une raison de s’intéresser aux variations de la fonction carrée sur   : comparer des distances ou leur carré produit le même résultat.