Comment savoir si un choix de est bon

def evaluer(exemples, k):
    """Laisse-un-de-cote : chaque exemple est predit par TOUS LES AUTRES."""
    justes = 0
    for i in range(len(exemples)):
        autres = exemples[:i] + exemples[i + 1:]
        if knn(autres, exemples[i][0], k) == exemples[i][1]:
            justes += 1
    return justes / len(exemples)

JEU2 = [((1, 1), "A"), ((1, 2), "A"), ((2, 1), "A"), ((2, 2), "A"),
        ((7, 7), "B"), ((7, 8), "B"), ((8, 7), "B"), ((8, 8), "B")]

assert [evaluer(JEU2, k) for k in [1, 3, 5, 7]] == [1.0, 1.0, 1.0, 0.0]

Le zéro absolu de la dernière colonne mérite qu'on s'y arrête. Avec huit exemples, quatre par classe, et $k=7$ : chaque exemple est prédit par les sept autres, dont trois de sa classe et quatre de l'autre. La majorité désigne donc systématiquement la classe opposée — le taux de bonnes réponses tombe à $0\%$, pas à $50\%$. L'algorithme ne devient pas « aléatoire » : il devient systématiquement faux.

Pourquoi l'exemple doit être retiré du jeu. Si on le laissait, il serait son propre plus proche voisin, à distance nulle, et l'évaluation serait beaucoup trop optimiste — parfaite à $k=1$, toujours. « Laisse-un-de-côté » n'est pas une élégance : c'est ce qui rend la mesure honnête. On n'évalue jamais un prédicteur sur les données qui ont servi à le construire.

Un jeu moins net.

melange = JEU2 + [((4, 4), "A"), ((4.5, 4.5), "B")]
assert evaluer(melange, 1) < 1.0

Deux points ajoutés au milieu, de classes opposées : chacun a l'autre pour plus proche voisin, et les deux sont mal prédits. C'est la situation réelle — les données ne sont jamais parfaitement séparées — et c'est là que le choix de $k$ commence à compter.