MerQuR+Statistics Glossary

Statistics Glossary → Number of nearest neighbours (k) and the neighbourhood graph

Number of nearest neighbours (k) and the neighbourhood graphconcept

The number of closest observations considered around a given observation, and the network that links each observation to those neighbours; together they define local structure in classification, outlier detection and dimension reduction.

In k-nearest-neighbour (kNN) classification, the class of a new observation is decided by a majority vote (or a distance-weighted vote) of its k closest training observations. The local outlier factor (LOF) compares a point's local density with the density of its k neighbours. Dimension-reduction methods such as UMAP build a neighbourhood graph linking each point to its k neighbours and try to preserve that graph in the low-dimensional representation. In all of these, 'closeness' depends on the chosen distance measure (Euclidean, Mahalanobis), which is why the variables are usually standardized first.

k governs a bias-variance trade-off. A small k gives very local, flexible decisions but is sensitive to noise (overfitting); a large k gives smoother decisions but can erase genuine local detail and small groups. In UMAP, a small n_neighbors emphasizes local clusters and a large value the global structure. In classification, k is often chosen by cross-validation, and an odd number is preferred in two-class problems to avoid ties. With very many variables, distances become similar to one another and the notion of a neighbourhood starts to lose its meaning (the curse of dimensionality).

An everyday example

You have just moved to a new neighbourhood and want to know which market is good. If you ask only your nearest neighbour (k = 1), you depend on that one person's taste; if you ask your 7 nearest neighbours and follow the majority, you get a more reliable answer. But if you ask the whole city (a very large k), you lose the knowledge specific to your neighbourhood.

In MerQur

It is set with the 'kNN: number of neighbours k' and distance-metric options for nonparametric classification in Discriminant Analysis, with 'Number of neighbors (n_neighbors)' in UMAP and with 'LOF neighbors' in Anomaly Detection. It is the core parameter of the k-Nearest Neighbors (KNN) analysis.

Analyses where this concept appears

Discriminant Analysis (LDA / QDA)UMAP (Uniform Manifold Approximation and Projection)Anomaly Detectionk-Nearest Neighbors (KNN)

Related concepts

Distance measure (Euclidean, Manhattan, Gower, great-circle)Perplexity (t-SNE effective number of neighbours)