Judged by Its Own Crowd

The rough version of the Local Outlier Factor divides a point's reach by its neighbours' average reach. The full formula keeps that idea, but averages over all $k$ neighbours and smooths the distances. Your job is to implement it exactly.

Points are lists of coordinates (any number of dimensions, no two identical), and $d(p, o)$ is the Euclidean distance between them.

k-distance. $\text{kdist}(p)$ is the distance from $p$ to its $k$ -th nearest other point.
Neighbourhood. $N(p)$ is every other point whose distance from $p$ is at most $\text{kdist}(p)$ . When several points tie, this can hold more than $k$ points: keep them all.
Reachability distance from $p$ to one of its neighbours $o$ :

\text{reach}(p, o) = \max\big(\text{kdist}(o),\ d(p, o)\big)

This is the smoothing: any point inside $o$ 's own k-distance counts as exactly that far from $o$ , so tiny distances inside a crowd don't swing the result.

Local reachability density, one over the average reach:

\text{lrd}(p) = \frac{|N(p)|}{\sum_{o \in N(p)} \text{reach}(p, o)}

Local Outlier Factor, the neighbours' average density compared with $p$ 's own:

\text{LOF}(p) = \frac{1}{|N(p)|} \sum_{o \in N(p)} \frac{\text{lrd}(o)}{\text{lrd}(p)}

Task: write lof_scores(points, k) returning one LOF per point, in the order given, each rounded to 4 decimal places. You may assume $1 \le k <$ the number of points.

A score near 1 means the point is as crowded as its own neighbours, so it fits its region, however sparse that region is. A score well above 1 means it has far more empty space around it than they do.

Judged by Its Own Crowd

Examples

Hints