Partie 3 : Algorithmes gloutons et k plus proches voisins

B.O. spécial n° 1 du 22 janvier 2019 - NSI Première

Contenus	Capacités attendues	Commentaires
Algorithmes gloutons.	Résoudre un problème grâce à un algorithme glouton.	L'utilisation de l'algorithme glouton ne garantit pas l'optimalité.
Algorithme des k plus proches voisins.	Écrire un algorithme qui prédit la classe d'un élément en fonction de la classe majoritaire de ses k plus proches voisins.	L'algorithme des k plus proches voisins est un exemple d'algorithme d'apprentissage.

1. Algorithmes gloutons

1.1 Principe

Un algorithme glouton (greedy algorithm) résout un problème en faisant, à chaque étape, le choix qui semble le meilleur localement, sans jamais revenir sur ses décisions.

C'est une stratégie naturelle et simple, mais qui ne garantit pas toujours la solution optimale.

1.2 Exemple 1 : le problème du rendu de monnaie

Problème : rendre une somme donnée avec le moins de pièces possible.

Système de pièces : 1, 2, 5, 10, 20, 50, 100, 200 centimes.

Stratégie gloutonne : à chaque étape, choisir la plus grande pièce possible.

def rendu_monnaie(somme, pieces):
    """Renvoie la liste des pièces à rendre (algorithme glouton)."""
    pieces_triees = sorted(pieces, reverse=True)
    resultat = []
    for piece in pieces_triees:
        while somme >= piece:
            resultat.append(piece)
            somme -= piece
    return resultat

>>> rendu_monnaie(63, [1, 2, 5, 10, 20, 50, 100, 200])
[50, 10, 2, 1]

Pour rendre 63 centimes : 50 + 10 + 2 + 1 = 4 pièces. C'est bien la solution optimale ici.

1.3 Exemple 2 : le problème du sac à dos (version simplifiée)

Problème : on a un sac pouvant contenir un poids maximal. On dispose d'objets avec un poids et une valeur. Quels objets prendre pour maximiser la valeur totale sans dépasser le poids maximal ?

Stratégie gloutonne : prendre en priorité les objets de meilleur rapport valeur/poids.

def sac_a_dos_glouton(objets, poids_max):
    """Résout le problème du sac à dos par un algorithme glouton.
    objets: liste de tuples (nom, poids, valeur)
    """
    # Trier par rapport valeur/poids décroissant
    tries = sorted(objets, key=lambda o: o[2] / o[1], reverse=True)

    sac = []
    poids_actuel = 0

    for nom, poids, valeur in tries:
        if poids_actuel + poids <= poids_max:
            sac.append(nom)
            poids_actuel += poids

    return sac

>>> objets = [
...     ("Livre", 2, 10),
...     ("Ordinateur", 5, 40),
...     ("Bouteille", 3, 6),
...     ("Cahier", 1, 8),
...     ("Lampe", 4, 12)
... ]
>>> sac_a_dos_glouton(objets, 8)
['Cahier', 'Ordinateur', 'Livre']

1.4 Quand l'algorithme glouton est-il optimal ?

Problème	Glouton optimal ?
Rendu de monnaie (système canonique €)	Oui
Rendu de monnaie (système arbitraire)	Non toujours
Sac à dos 0/1	Non
Ordonnancement de tâches (par date limite)	Oui

En résumé : l'algorithme glouton est simple et rapide, mais il faut vérifier au cas par cas s'il donne la solution optimale.

2. Algorithme des k plus proches voisins (KNN)

2.1 Principe

L'algorithme des k plus proches voisins (k-Nearest Neighbors, KNN) est un algorithme de classification : il prédit la catégorie d'un nouvel élément en regardant les catégories de ses voisins les plus proches dans un jeu de données existant.

Principe :

Calculer la distance entre le nouvel élément et tous les éléments connus
Sélectionner les k éléments les plus proches
Attribuer au nouvel élément la classe majoritaire parmi ces k voisins

2.2 La distance euclidienne

Pour mesurer la « proximité » entre deux points, on utilise la distance euclidienne :

Pour deux points $(x_1, y_1)$ et $(x_2, y_2)$ :

$d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$

import math

def distance(point1, point2):
    """Calcule la distance euclidienne entre deux points (x, y)."""
    return math.sqrt((point2[0] - point1[0])**2 + (point2[1] - point1[1])**2)

Pour des données avec plus de 2 dimensions :

$d = \sqrt{\sum_{i=1}^{n} (a_i - b_i)^2}$

def distance_n(point1, point2):
    """Distance euclidienne en n dimensions."""
    somme = 0
    for i in range(len(point1)):
        somme += (point2[i] - point1[i]) ** 2
    return math.sqrt(somme)

2.3 Implémentation complète

def knn(donnees, nouveau_point, k):
    """Prédit la classe d'un nouveau point par KNN.

    donnees: liste de tuples ((x, y), classe)
    nouveau_point: tuple (x, y) à classifier
    k: nombre de voisins à considérer

    Precondition: k <= len(donnees)
    """
    # Calculer la distance entre le nouveau point et chaque donnée
    distances = []
    for coordonnees, classe in donnees:
        d = distance(nouveau_point, coordonnees)
        distances.append((d, classe))

    # Trier par distance croissante
    distances.sort(key=lambda x: x[0])

    # Prendre les k plus proches
    k_voisins = distances[:k]

    # Compter les classes
    compteur = {}
    for _, classe in k_voisins:
        if classe in compteur:
            compteur[classe] += 1
        else:
            compteur[classe] = 1

    # Renvoyer la classe majoritaire
    classe_predite = max(compteur, key=compteur.get)
    return classe_predite

2.4 Exemple concret

On a des fleurs caractérisées par la longueur et la largeur de leurs pétales :

fleurs = [
    ((1.4, 0.2), "Setosa"),
    ((1.3, 0.3), "Setosa"),
    ((1.5, 0.2), "Setosa"),
    ((4.5, 1.5), "Versicolor"),
    ((4.7, 1.4), "Versicolor"),
    ((4.2, 1.3), "Versicolor"),
    ((6.0, 2.5), "Virginica"),
    ((5.8, 2.2), "Virginica"),
    ((6.3, 1.8), "Virginica"),
]

# Classifier une nouvelle fleur (3.5, 1.0)
resultat = knn(fleurs, (3.5, 1.0), 3)
print(resultat)    # "Versicolor"

2.5 Choix de k

Le choix de k influence le résultat :

k petit (ex: 1)	k grand (ex: n)
Très sensible au bruit	Trop lissé, perd le détail
Risque de se tromper sur un point atypique	Tend vers la classe la plus fréquente

2.6 Importance de la normalisation

Si les données ont des échelles très différentes (ex : âge en années et salaire en euros), la dimension avec les plus grandes valeurs domine le calcul de distance. Il faut normaliser les données pour que chaque dimension ait la même importance.

def normaliser(donnees):
    """Normalise les données entre 0 et 1."""
    n_dim = len(donnees[0][0])
    mins = [min(d[0][i] for d in donnees) for i in range(n_dim)]
    maxs = [max(d[0][i] for d in donnees) for i in range(n_dim)]

    resultat = []
    for coords, classe in donnees:
        coords_norm = tuple(
            (coords[i] - mins[i]) / (maxs[i] - mins[i])
            if maxs[i] != mins[i] else 0
            for i in range(n_dim)
        )
        resultat.append((coords_norm, classe))
    return resultat

À retenir

Un algorithme glouton fait le choix localement optimal à chaque étape. Il est simple et rapide mais ne garantit pas toujours la solution optimale.
Le rendu de monnaie avec le système euro est un exemple où le glouton est optimal.
Le sac à dos est un exemple où le glouton peut échouer.
L'algorithme KNN classe un élément en fonction de la classe majoritaire de ses k plus proches voisins.
La distance euclidienne mesure la proximité entre deux points.
Le choix de k influence la qualité de la prédiction : k impair, entre 3 et 10 en général.
La normalisation des données est importante quand les dimensions ont des échelles différentes.