k-Nearest Neighbors — Visual Lab

final class KNN
{
    /** Every training point: ['x' => float, 'y' => float, 'label' => int] */
    private array $points = [];

    public function __construct(
        private int $k = 5,                    // how many neighbours get a vote
        private string $metric = 'euclidean',  // how we measure "close"
        private bool $weighted = false         // should closer neighbours count more?
    ) {}

    // ---- "TRAINING" --------------------------------------------------------
    // KNN is a *lazy learner*: training is literally just remembering the data.
    // There are no weights, no equations, no iterations. All the work happens
    // later, at prediction time.
    public function fit(array $points): void
    {
        $this->points = array_values($points);
    }

    // ---- STEP A: how far apart are two points? -----------------------------
    public function distance(array $a, array $b): float
    {
        $dx = $a['x'] - $b['x'];
        $dy = $a['y'] - $b['y'];

        if ($this->metric === 'manhattan') {
            return abs($dx) + abs($dy);        // walk along city blocks
        }
        return sqrt($dx * $dx + $dy * $dy);    // straight line (Pythagoras)
    }

    // ---- STEP B: measure the distance to EVERY training point, then sort ---
    // $exclude lets us skip one point (used for leave-one-out testing below).
    public function rankNeighbors(array $query, ?int $exclude = null): array
    {
        $ranked = [];
        foreach ($this->points as $i => $p) {
            if ($i === $exclude) continue;
            $ranked[] = [
                'index'    => $i,
                'label'    => $p['label'],
                'distance' => $this->distance($query, $p),
            ];
        }
        usort($ranked, fn($a, $b) => $a['distance'] <=> $b['distance']);
        return $ranked;                        // nearest first
    }

    // ---- STEP C + D: keep the k nearest, and let them vote -----------------
    // Returns [label => votes], highest first.
    // Ties: PHP's sort is stable, so on a tie the label that appeared first
    // (i.e. belongs to the nearer neighbour) wins.
    public function vote(array $ranked, ?int $k = null): array
    {
        $k ??= $this->k;
        $votes = [];
        foreach (array_slice($ranked, 0, $k) as $n) {
            $weight = $this->weighted ? 1 / ($n['distance'] + 1e-9) : 1;
            $votes[$n['label']] = ($votes[$n['label']] ?? 0) + $weight;
        }
        arsort($votes);
        return $votes;
    }

    // ---- Everything together: point in, label out --------------------------
    public function predict(array $query): int
    {
        if (!$this->points) return -1;
        $votes = $this->vote($this->rankNeighbors($query));
        return (int) array_key_first($votes);
    }

    // ---- How good is each k? (Leave-One-Out cross-validation) --------------
    // For every point: hide it, predict it from the others, check if we were
    // right. Do that for k = 1..maxK. This is how you *choose* k.
    public function leaveOneOutAccuracy(int $maxK): array
    {
        $n = count($this->points);
        $correct = array_fill(1, $maxK, 0);
        foreach ($this->points as $i => $p) {
            $ranked = $this->rankNeighbors($p, exclude: $i);   // sort once...
            for ($k = 1; $k <= $maxK; $k++) {                  // ...reuse for every k
                if ((int) array_key_first($this->vote($ranked, $k)) === $p['label']) {
                    $correct[$k]++;
                }
            }
        }
        return array_map(fn($c) => $n ? $c / $n : 0.0, $correct);
    }

    public function points(): array { return $this->points; }
}