nearest neighbour concept
| Definition | A row at minimal distance from a query. A strictly increasing transform of the distance names the same nearest neighbours, so the classifier reads the distance's order and nothing else. Chapter 6. Also k-nearest. |
|---|---|
| Example | Among rows at distances 0.9, 0.4, and 1.2 from a query, the second is the nearest, under any increasing rescaling of the distances. |
| Book | Data Mining as Observation, draft 0.2, commit f3914f0; entry id nearest-neighbour, kind concept. |
| Status | no ledger row names this entry. Corrections: none recorded. |
| Defining equation | none |
| Assumptions and scope |
|
| Prior art | none recorded |
| Evidence | lean/DataMiningAsObservation/NearestNeighbour.lean, lean/DataMiningAsObservation/Graph.lean |
| Reviewed | not yet reviewed; generated 2026-09-10 from records at the commits on the provenance page. |
Equation
none
Conditions
- A row at minimal distance from a query under a chosen distance. A strictly increasing transform of the distance names the same nearest neighbours, so a nearest-neighbour classifier reads the distance’s order and nothing else, a row is its own nearest neighbour, and two nearest neighbours sit at the same distance.
- Under Euclidean distance the classifier reads every standardized coordinate equally and under cosine it reads the angle, so it inherits the distance’s quotient, and the rows that appear in many neighbour lists are the hubs.
Conditions are curated in entries.toml rather than read
from a record.
Ledger
none
First stated
Cover and Hart, nearest neighbor pattern classification, 1967, as
chapter 6 section 6.1 of Data Mining as Observation reads it,
with the neighbour lists of
openvector-bench/openvector_bench/hubness.py:41-100.
Measurements
none
Failures and corrections
none
Invariance envelope
none declared
Machine checked
lean/DataMiningAsObservation/NearestNeighbour.lean,
theorems nearest_comp, nearest_smul,
self_nearest, nearest_same_distance, at
observation-data-mining f3914f0; what the check covers is stated in the
book’s appendix
C.
lean/DataMiningAsObservation/Graph.lean,
theorems outDegree, mutual_symm,
mutual_sub, mutualNbrs_card_le,
mem_mutualNbrs, at observation-data-mining f3914f0; what
the check covers is stated in the book’s appendix
C.
Used in
Data Mining as Observation primer S, chapters 0, 3, 6, 8, 10, 11, 12.
Related
neighbourhood graph; hub; recall at k; Euclidean distance; cosine.
See also
Book equations stated beside the entry’s terms, not defining it: 3.1, 0.19, 10.3.
Ledger rows that cite the entry’s records without naming it: NEG-11.
Sources-table rows that share a record with the entry without naming it: chapter 3 section 3.5.
Status
Generated 2026-09-10 by encyclopedia/generate.py; book
at observation-data-mining f3914f0; the commit of every record is listed
in the encyclopedia’s provenance.