Pourquoi choisir impair avec deux classes

Le cas d'égalité parfaite.

PROCHES = [((0, 0), "A"), ((0, 2), "A"), ((2, 0), "B"), ((2, 2), "B")]
milieu = (1, 1)
for c, _ in PROCHES:
    assert abs(distance(c, milieu) - 2 ** 0.5) < 1e-12   # les QUATRE a egale distance

assert k_plus_proches_voisins(PROCHES, milieu, 4) == "A"

inverse = [((2, 0), "B"), ((2, 2), "B"), ((0, 0), "A"), ((0, 2), "A")]
assert k_plus_proches_voisins(inverse, milieu, 4) == "B"

Mêmes données, même point, même $k$ — et deux réponses opposées. Seul l'ordre des lignes a changé. C'est la conséquence du if n > meilleur_score avec un $>$ strict : à égalité, la première classe rencontrée l'emporte, et « la première » dépend de l'ordre du dictionnaire des votes, lui-même hérité de l'ordre des exemples. Un algorithme dont le résultat dépend de l'ordre de saisie n'est pas déterministe au sens où l'utilisateur l'entend.

$k$ impair, à deux classes, rend l'égalité impossible : deux entiers de somme impaire ne peuvent pas être égaux. La parade est gratuite, et c'est celle du cours. Elle ne vaut cependant que pour deux classes : avec trois classes et $k=6$, on peut avoir $2$-$2$-$2$.

Départager pour de bon.

def knn_departage(exemples, point, k):
    """Vote majoritaire ; en cas d'egalite, la classe dont les voisins sont
    globalement les plus proches (plus petite somme des distances)."""
    assert 1 <= k <= len(exemples)
    mesures = sorted([(distance(c, point), cl) for c, cl in exemples],
                     key=lambda x: x[0])
    voisins = mesures[:k]
    votes, cumul = {}, {}
    for d, classe in voisins:
        votes[classe] = votes.get(classe, 0) + 1
        cumul[classe] = cumul.get(classe, 0) + d
    maxi = max(votes.values())
    exaequo = [c for c, n in votes.items() if n == maxi]
    if len(exaequo) == 1:
        return exaequo[0]
    return min(exaequo, key=lambda c: cumul[c])

Un cas où les deux règles diffèrent vraiment.

decale = [((1, 0), "A"), ((9, 9), "A"), ((2, 2), "B"), ((3, 3), "B")]
p = (1, 1)
assert k_plus_proches_voisins(decale, p, 4) == "A"   # la classe du PLUS PROCHE
assert knn_departage(decale, p, 4) == "B"            # la plus proche EN MOYENNE

$A$ possède le voisin le plus proche ($1,0$) mais aussi le plus lointain ($11,31$) ; $B$ a ses deux représentants à distance moyenne. Les deux règles sont défendables — ce qui ne l'est pas, c'est de ne pas dire laquelle on applique. Le choix appartient à la spécification, pas au hasard de l'ordre des données.