Aller au contenu

TP : L'algorithme de recommandation — Comment TikTok/YouTube vous connaît

Thème : Arbres de décision et algorithmes de recommandation

Contexte

En 2026, les algorithmes de recommandation sont omniprésents : TikTok, YouTube, Spotify, Netflix... Ces plateformes utilisent des arbres de décision pour prédire vos goûts et vous proposer du contenu personnalisé.

Dans ce TP, vous allez construire un mini-système de recommandation de films basé sur un arbre binaire de décision.

Partie 1 : Comprendre l'arbre de décision

Un arbre de décision pose des questions binaires (oui/non) pour classifier des données.

Exemple

                    Aimes-tu l'action ?
                      /            \
                   OUI              NON
                    |                |
          Aimes-tu la SF ?    Aimes-tu la romance ?
            /        \           /         \
          OUI        NON       OUI         NON
           |          |         |           |
      "Matrix"   "Die Hard"  "Titanic"   "Le Parrain"

Questions préliminaires

  1. Quel film sera recommandé à quelqu'un qui aime l'action mais pas la SF ?

  2. Combien de questions faut-il poser au maximum pour recommander un film ?

  3. Si on veut recommander 16 films différents, combien de questions faudra-t-il poser au maximum ? (Indice : pensez à la hauteur de l'arbre)

Partie 2 : Modélisation avec une classe

Nous allons créer une classe NoeudDecision pour représenter notre arbre.

Structure d'un nœud

Un nœud peut être : - Un nœud interne : il contient une question et deux sous-arbres (oui/non) - Une feuille : elle contient une recommandation (un film)

Exercice 1 : Compléter la classe

class NoeudDecision:
    def __init__(self, question=None, film=None):
        """
        Crée un nœud de l'arbre de décision.

        Si film is not None : c'est une feuille (recommandation)
        Sinon : c'est un nœud interne avec une question

        Paramètres:
            question (str): La question à poser (None si feuille)
            film (str): Le film à recommander (None si nœud interne)
        """
        self.question = question
        self.film = film
        self.oui = None  # Sous-arbre si réponse = oui
        self.non = None  # Sous-arbre si réponse = non

    def est_feuille(self):
        """Retourne True si ce nœud est une feuille (recommandation)."""
        # À compléter
        pass

    def __str__(self):
        """Représentation textuelle du nœud."""
        if self.est_feuille():
            return f"Film: {self.film}"
        else:
            return f"Question: {self.question}"

Partie 3 : Construction de l'arbre

Exercice 2 : Construire l'arbre d'exemple

Complétez la fonction suivante pour construire l'arbre de décision présenté en partie 1.

def construire_arbre_films():
    """Construit et retourne l'arbre de recommandation de films."""

    # Création des feuilles (recommandations)
    matrix = NoeudDecision(film="Matrix")
    die_hard = NoeudDecision(film="Die Hard")
    titanic = NoeudDecision(film="Titanic")
    parrain = NoeudDecision(film="Le Parrain")

    # Création des nœuds internes (questions)
    # À compléter...

    # Retourner la racine de l'arbre
    pass

Exercice 3 : Tester la construction

# Créer l'arbre
arbre = construire_arbre_films()

# Vérifier la structure
print(arbre)  # Doit afficher la question racine
print(arbre.oui)  # Doit afficher la question sur la SF
print(arbre.oui.oui)  # Doit afficher "Film: Matrix"

Partie 4 : Parcours et recommandation

Exercice 4 : Fonction de recommandation interactive

Complétez la fonction suivante qui parcourt l'arbre en posant les questions à l'utilisateur :

def recommander(noeud):
    """
    Parcourt l'arbre de décision en posant des questions à l'utilisateur.
    Retourne le film recommandé.
    """
    # Cas de base : on est sur une feuille
    if noeud.est_feuille():
        return noeud.film

    # Afficher la question et récupérer la réponse
    print(noeud.question)
    reponse = input("Votre réponse (oui/non) : ").lower().strip()

    # Suivre la branche correspondante
    # À compléter...
    pass

Exercice 5 : Programme principal

def main():
    print("=== Système de recommandation de films ===\n")

    arbre = construire_arbre_films()
    film = recommander(arbre)

    print(f"\n>>> Je vous recommande : {film}")

# Lancer le programme
main()

Partie 5 : Enrichir l'arbre

Exercice 6 : Ajouter des films

Modifiez la fonction construire_arbre_films() pour ajouter au moins 4 films supplémentaires en créant de nouvelles questions.

Suggestions de questions : - "Préférez-vous les films récents (après 2010) ?" - "Aimez-vous les films avec beaucoup d'humour ?" - "Préférez-vous les films européens ?"

Exercice 7 : Affichage de l'arbre

Écrivez une fonction qui affiche l'arbre de manière indentée :

def afficher_arbre(noeud, niveau=0):
    """
    Affiche l'arbre de décision de manière indentée.

    Exemple de sortie attendue:
    Aimes-tu l'action ?
    ├── OUI: Aimes-tu la SF ?
    │   ├── OUI: Matrix
    │   └── NON: Die Hard
    └── NON: Aimes-tu la romance ?
        ├── OUI: Titanic
        └── NON: Le Parrain
    """
    # À compléter
    pass

Partie 6 : Statistiques sur l'arbre

Exercice 8 : Hauteur de l'arbre

Écrivez une fonction récursive qui calcule la hauteur de l'arbre de décision.

def hauteur(noeud):
    """Retourne la hauteur de l'arbre."""
    # À compléter
    pass

Exercice 9 : Nombre de films

Écrivez une fonction qui compte le nombre de films (feuilles) dans l'arbre.

def nombre_films(noeud):
    """Retourne le nombre de films (feuilles) dans l'arbre."""
    # À compléter
    pass

Exercice 10 : Liste de tous les films

Écrivez une fonction qui retourne la liste de tous les films de l'arbre.

def tous_les_films(noeud):
    """Retourne la liste de tous les films de l'arbre."""
    # À compléter
    pass

Partie 7 : Pour aller plus loin (Bonus)

Réflexion : vers le Machine Learning

En réalité, les algorithmes de recommandation modernes apprennent automatiquement l'arbre à partir de données.

Question de réflexion :

Imaginez que vous avez une base de données de 1000 utilisateurs avec : - Leurs réponses aux questions (oui/non) - Le film qu'ils ont finalement aimé

Comment pourriez-vous automatiquement construire le "meilleur" arbre de décision ?

Indice : Il faudrait choisir à chaque nœud la question qui "sépare" le mieux les utilisateurs selon leurs préférences.

Recherche

L'algorithme ID3 (Iterative Dichotomiser 3) est un algorithme classique pour construire des arbres de décision.

  1. Faites une recherche sur cet algorithme.
  2. Qu'est-ce que l'entropie dans ce contexte ?
  3. Comment ID3 choisit-il la meilleure question à poser à chaque nœud ?

Résumé des notions travaillées

Notion Application dans ce TP
Arbre binaire Structure de l'arbre de décision
Nœud / Feuille Questions / Recommandations
Parcours d'arbre Fonction recommander()
Récursivité Hauteur, comptage, affichage
POO Classe NoeudDecision

Auteur : Florian Mathieu

Licence CC BY NC

Licence Creative Commons
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.