Améliorer les k plus proches voisins en pondérant chaque vote par…

def knn_pondere(exemples, point, k):
    """Chaque voisin vote avec un poids 1/(distance + eps)."""
    assert 1 <= k <= len(exemples)
    eps = 1e-9                       # evite la division par zero sur un point connu
    mesures = sorted([(distance(c, point), cl) for c, cl in exemples],
                     key=lambda x: x[0])
    poids = {}
    for d, classe in mesures[:k]:
        poids[classe] = poids.get(classe, 0) + 1 / (d + eps)
    return max(poids, key=lambda c: poids[c])

LOIN = [((0, 0), "A"), ((10, 10), "B"), ((11, 11), "B")]
assert knn(LOIN, (0.5, 0.5), 3) == "B"           # 2 voix contre 1
assert knn_pondere(LOIN, (0.5, 0.5), 3) == "A"   # le tres proche l'emporte

Le cas est volontairement caricatural, et il le fallait. Le point est à $0,7$ du seul $A$, et à plus de $13$ des deux $B$. Le vote simple, qui compte les têtes, choisit $B$ : deux voix contre une. Le vote pondéré donne au $A$ un poids de $1,4$ contre $0,15$ à chaque $B$, et choisit $A$. Une majorité de voisins lointains l'emporte sur un voisin manifestement pertinent — c'est ce défaut que la pondération corrige.

Le eps n'est pas une coquetterie. Si le point à classer figure exactement dans les exemples, sa distance est nulle et $1/0$ lèverait ZeroDivisionError. L'ajouter donne à ce voisin un poids énorme mais fini — ce qui est le comportement voulu : un point connu doit être classé comme lui-même.

Le prix à payer. La pondération introduit un choix arbitraire de plus — pourquoi $1/d$ et non $1/d^2$ ? Chaque réglage supplémentaire est une décision à documenter, et une occasion de tromperie si on l'ajuste jusqu'à obtenir le résultat qui arrange.