Dichotomie, voisins et gloutons

8.1.2 La terminaison, par un variant

8.1.3 Ce que l'on gagne

Les chiffres disent l'écart mieux qu'une formule :

Figure : Nombre de comparaisons dans le pire des cas. Le parcours séquentiel suit la taille ; la dichotomie suit son logarithme.

8.2 Les $k$ plus proches voisins

Le programme le présente comme « un exemple d'algorithme d'apprentissage ». Le principe tient en une phrase : pour deviner à quelle catégorie appartient un nouvel individu, on regarde les $k$ individus connus qui lui ressemblent le plus, et on retient la catégorie la plus représentée parmi eux.

8.2.1 Mesurer la ressemblance

def distance(p, q):
    """Distance euclidienne entre deux points donnés par des p-uplets
    de même longueur.

    Précondition : len(p) == len(q).
    """
    assert len(p) == len(q), "dimensions differentes"
    somme = 0
    for i in range(len(p)):
        somme = somme + (p[i] - q[i]) ** 2
    return somme ** 0.5

8.2.2 L'algorithme

def k_plus_proches_voisins(exemples, point, k):
    """Classe prédite pour point, par vote majoritaire de ses k plus
    proches voisins.

    exemples est un tableau de couples (coordonnees, classe).
    Précondition  : 1 <= k <= len(exemples).
    Postcondition : le résultat est l'une des classes présentes dans exemples.
    """
    assert 1 <= k <= len(exemples), "k hors bornes"

    # 1. distance de chaque exemple au point
    mesures = [(distance(coord, point), classe) for coord, classe in exemples]

    # 2. les k plus proches (tri du chapitre 6 : on a le droit de l'utiliser)
    mesures = sorted(mesures, key=lambda couple: couple[0])
    voisins = mesures[:k]

    # 3. vote majoritaire (le compteur du chapitre 5)
    votes = {}
    for _, classe in voisins:
        votes[classe] = votes.get(classe, 0) + 1

    meilleure = None
    meilleur_score = 0
    for classe, n in votes.items():
        if n > meilleur_score:
            meilleure, meilleur_score = classe, n
    return meilleure

Figure : Les $k$ plus proches voisins. Rien n'est appris à l'avance : c'est au moment de la

question qu'on mesure la distance à tous les exemples connus.</div>

iRemarque

L'algorithme n'est fait que de briques déjà connues : un parcours pour les distances, un tri, un comptage par dictionnaire. C'est très souvent ainsi qu'un algorithme « savant » se révèle à l'usage — un assemblage d'opérations élémentaires bien choisies.

AttentionLe vote peut être nul

Avec $k=4$ et deux classes à deux voix chacune, la fonction renvoie la première rencontrée : un choix arbitraire, hérité de l'ordre du dictionnaire. Deux parades, à connaître : prendre $k$ impair quand il n'y a que deux classes, ou départager par la distance. La docstring doit dire ce qui a été choisi — c'est la règle du chapitre 5 sur les ex æquo.

ImportantCe que cet algorithme n'apprend pas

On parle d'« apprentissage », mais rien n'est appris au sens ordinaire : il n'y a aucune phase d'entraînement, aucun modèle construit. Toute la donnée est conservée, et le travail est fait au moment de la question. La conséquence pratique compte : prédire coûte cher, puisqu'il faut mesurer la distance à tous les exemples — le coût est linéaire en la taille du jeu de données, à chaque prédiction.

8.3 Les algorithmes gloutons

Capacité attendue

« Résoudre un problème grâce à un algorithme glouton. »

Définition 8.1Algorithme glouton

Un algorithme est glouton lorsqu'il construit une solution pas à pas, en faisant à chaque étape le choix qui paraît le meilleur sur le moment, sans jamais revenir sur une décision prise.

8.3.1 Le rendu de monnaie

def rendu_monnaie(somme, pieces):
    """Décomposition de somme avec les valeurs de pieces, par choix glouton.

    Précondition  : pieces est trié par ordre DÉCROISSANT et contient 1.
    Postcondition : la somme des valeurs rendues vaut exactement somme.
    """
    assert somme >= 0
    assert pieces == sorted(pieces, reverse=True), "pieces doit etre decroissant"
    assert 1 in pieces, "sans piece de 1, la decomposition peut echouer"

    rendu = []
    reste = somme
    for p in pieces:
        while reste >= p:          # variant : reste décroît strictement
            rendu.append(p)
            reste = reste - p
    assert sum(rendu) == somme
    return rendu

Exemple 8.2

Avec le système européen [200, 100, 50, 20, 10, 5, 2, 1] et une somme de $67$ centimes, l'algorithme rend $50+10+5+2$, soit quatre pièces. C'est bien le minimum.

8.3.2 Là où le glouton se trompe

AttentionUn algorithme glouton n'est pas toujours optimal

C'est le point essentiel de la section, et il vaut mieux le découvrir ici qu'à l'examen.

Prenons un système de pièces imaginaire : [6, 4, 1], et une somme de $8$.

• Le glouton prend d'abord $6$, puis complète : $6+1+1$, soit trois pièces.
• L'optimum est $4+4$, soit deux pièces.

L'algorithme rend une décomposition correcte — la somme est juste, la postcondition est respectée — mais pas la meilleure. Et il n'a aucun moyen de s'en apercevoir, puisqu'il ne revient jamais sur ses choix.

Le système européen, lui, a la propriété d'être « canonique » : le glouton y est toujours optimal. Ce n'est pas un hasard, c'est une propriété du jeu de valeurs — pas de l'algorithme.

Figure : Un algorithme glouton donne toujours une solution correcte — la somme est juste —

mais pas nécessairement la meilleure. Et il n'a aucun moyen de s'en apercevoir.</div>

8.3.3 Le sac à dos

Le second exemple cité par le programme. On dispose d'objets ayant chacun un poids et une valeur, et d'un sac de capacité limitée ; on veut emporter le plus de valeur possible.

def sac_a_dos_glouton(objets, capacite):
    """Sélection gloutonne par valeur massique décroissante.

    objets est un tableau de p-uplets (nom, poids, valeur).
    Précondition  : poids > 0 pour chaque objet, capacite >= 0.
    Postcondition : le poids total emporté ne dépasse pas capacite.
    Renvoie les noms choisis et la VALEUR totale emportée.
    """
    assert capacite >= 0
    assert all(poids > 0 for _, poids, _ in objets)

    tries = sorted(objets, key=lambda o: o[2] / o[1], reverse=True)
    choisis = []
    restant = capacite
    valeur_totale = 0
    for nom, poids, valeur in tries:
        if poids <= restant:
            choisis.append(nom)
            restant = restant - poids
            valeur_totale = valeur_totale + valeur
    assert restant >= 0, "le poids emporte depasse la capacite"
    return choisis, valeur_totale

Exemple 8.3Le glouton se trompe encore

Capacité $10$, et trois objets : $A$ (poids 6, valeur 30), $B$ (poids 5, valeur 20), $C$ (poids 5, valeur 20).

Les valeurs massiques valent $5$ pour $A$, $4$ pour $B$ et $C$. Le glouton prend donc $A$, puis ne peut plus rien ajouter — il reste $4$ de capacité : total 30. L'optimum est $B+C$, de poids $10$ et de valeur 40.

ImportantAlors à quoi bon ?

Parce que trouver l'optimum du sac à dos coûte, pour les meilleures méthodes connues, un temps qui explose avec le nombre d'objets, tandis que le glouton donne une réponse honnête en un tri. Sur beaucoup de problèmes réels, une bonne solution tout de suite vaut mieux que la meilleure trop tard.

Le programme situe d'ailleurs la chose : « les algorithmes gloutons constituent une méthode algorithmique parmi d'autres qui seront vues en terminale ». On y verra comment obtenir l'optimum — au prix d'un travail bien supérieur.

Piste de projet : Comparer les stratégies

Programmer, sur le rendu de monnaie ou le sac à dos, deux résolutions : la gloutonne, et l'exhaustive qui essaie toutes les combinaisons. Comparer les résultats et les temps, pour des tailles croissantes. Chercher, pour le rendu de monnaie, des systèmes de pièces où le glouton échoue — il en existe une infinité.

L'exhaustive devient impraticable très vite ; c'est justement ce qu'il faut mesurer et montrer.

Continuer sur Adloun : animation, QCM, fiches, exercices