Нашли ошибку?

Подбор k без подглядывания

СложнаяНайти ошибку2 ошибкиГлава 10
Нашли ошибку?

#k ближайших соседей#классификация#оценка качестваid: ga-choose-k

Какое k выбрать для классификатора? Способ «исключи по одному» (leave-one-out): каждую точку по очереди убираем из выборки, классифицируем по остальным и сравниваем с настоящей меткой. Доля угаданных — точность для данного k. Функция best_k(data, candidates) должна вернуть k с наибольшей точностью, а при равенстве — наименьшее. Классификатор classify написан верно, но в loo_accuracy и best_k есть по одной ошибке. Найдите и исправьте их.

Пример

data = [
    ([0, 0], "A"), ([0, 1], "A"), ([1, 0], "A"), ([1, 1], "A"),
    ([5, 5], "B"), ([5, 6], "B"), ([6, 5], "B"), ([6, 6], "B"),
    ([0.5, 0.5], "B"),  # шум внутри скопления A
]
loo_accuracy(data, 1)     # 0.444…: шум сбивает всех соседей из A
loo_accuracy(data, 3)     # 0.888…
best_k(data, [1, 3, 5])   # 3 — у k = 3 и k = 5 точность одинаковая, берём меньшее

Решение

import math


def classify(train: list[tuple[list[float], str]], query: list[float], k: int) -> str:
    """Голосование k ближайших; при ничьей — метка ближайшего из лидеров."""
    neighbors = sorted(train, key=lambda item: math.dist(item[0], query))[:k]
    votes: dict[str, int] = {}
    for _, label in neighbors:
        votes[label] = votes.get(label, 0) + 1
    top = max(votes.values())
    return next(label for _, label in neighbors if votes[label] == top)


def loo_accuracy(data: list[tuple[list[float], str]], k: int) -> float:
    """Точность «исключи по одному» для заданного k."""
    correct = 0
    for i, (features, label) in enumerate(data):
        others = data
        if classify(others, features, k) == label:
            correct += 1
    return correct / len(data)


def best_k(data: list[tuple[list[float], str]], candidates: list[int]) -> int:
    """k с наибольшей точностью; при равенстве — наименьшее."""
    best, best_acc = candidates[0], -1.0
    for k in sorted(candidates):
        acc = loo_accuracy(data, k)
        if acc >= best_acc:
            best, best_acc = k, acc
    return best

Можно решать и в своём редакторе: «Скопировать с тестами» и запустите python3 choose_k.py — тесты те же, результат покажет ✓ / ✗ и итог.