Real-world datasets are rarely pristine. Whether dealing with electronic health records (EHRs), industrial sensor logs, or large-scale demographic surveys, data scientists routinely encounter "holey" data. A patient might skip a lab test; a sensor might temporarily lose power; a survey respondent might decline to answer a sensitive question.
Faced with missing values, practitioners historically relied on two simple workarounds: dropping incomplete records entirely (complete-case analysis) or filling the gaps with global statistics like the feature's mean or median. Both approaches are deeply flawed. Dropping records throws away valuable data and shrinks sample sizes, while global imputation flattens variance, destroys natural correlations between features, and introduces severe statistical bias.
Similarity-based imputation—most notably $k$-Nearest Neighbors ($k$-NN) imputation—offers a elegant solution. Instead of looking at global averages, it leverages the local topology of the dataset to infer missing values.
The Core Intuition: Local Topology Preserves Structure
The foundational premise of similarity-based imputation is intuitive: if two instances are highly similar across their observed attributes, they are likely to be similar across their unobserved attributes as well.
Imagine a high-dimensional feature space where each point represents a patient's clinical profile. If Patient A is missing a specific biomarker value (such as platelet count), a $k$-NN imputer searches the feature space to find the $k$ closest patients who do have that biomarker recorded. By calculating an average or mode from these localized "donor" profiles, the system fills Patient A's gap with a highly contextualized estimate.
Global Mean Imputation (Flattens Variance):
[Value] ---> Collapses all missing points to the center of the distribution.
Similarity-Based Imputation (Preserves Structure):
[Value] ---> Pulls estimates from the immediate geometric neighborhood.
As Feijun Luo et al. demonstrate in Missing Value Imputation for Diabetes Prediction, this localized strategy frequently outperforms complex deep learning architectures and heavy statistical models when dealing with sparse clinical datasets. Because real-world medical records exhibit highly non-linear relationships, anchoring the imputation to local data structures prevents the model from introducing global distortion.
By preserving these local relationships, downstream machine learning models can be trained on complete datasets without discarding valuable records containing partial information, a benefit highlighted by Bogyeong Suh et al. in Interpretable Deep-Learning Approaches for Osteoporosis Risk Screening and Individualized Feature Analysis Using Large Population-Based Data: Model Development and Performance Evaluation and Wentai Zhang et al. in Machine Learning in Preoperative Prediction of Postoperative Immediate Remission of Histology-Positive Cushing’s Disease.
Why Local Imputation Works
To understand why neighborhood-based methods work so well, consider what happens to a dataset's joint distribution during imputation.
When you impute a missing value with a global mean, you create an artificial spike at the center of that feature's distribution. This attenuates the variance and masks the true covariance between features. In contrast, neighborhood-based similarity imputation draws values directly from the empirical distribution of similar entities. As Chunxi Yang et al. note in A Novel Paradigm for Parameter Optimization of Hydraulic Fracturing Using Machine Learning and Large Language Model, this preserves the original statistical distribution and mode of the parameters, ensuring the resulting dataset remains representative of the source data without introducing significant bias.
Furthermore, this preservation of local structure is vital for maintaining high sensitivity in diagnostic models. Shuyan Cai et al. in Fully-connected network-based prediction model for lymph node metastasis in clinical early-stage endometrial cancer: development and validation in two centers emphasize that local data structures are far more effective than global averages at keeping subtle, critical predictive signals intact. This allows high-dimensional physiological structures to remain viable for downstream analysis, as shown by David P. Chen et al. in Latent physiological factors of complex human diseases revealed by independent component analysis of clinarrays.
Remarkably, this geometric consistency holds true even under extreme data scarcity. In Imputation techniques on missing values in breast cancer treatment and fertility data, Xuetong Wu et al. show that nearest-neighbor imputation techniques remain highly effective and computationally efficient even when data missingness exceeds fifty percent, providing significant accuracy gains for downstream classification tasks.
Navigating Heterogeneity and Distance Metrics
The primary challenge of similarity-based imputation lies in defining what "close" means. In a pure, continuous numerical space, standard Euclidean distance suffices. However, real-world data is rarely homogeneous; it is frequently a messy mix of continuous variables (like blood pressure or age) and categorical attributes (like biological sex or smoking status).
To compute meaningful neighborhoods across heterogeneous data types, algorithms must employ specialized distance metrics. For instance, Deborah Maffezzoni et al. in Data-Driven Diagnostics for Pediatric Appendicitis: Machine Learning to Minimize Misdiagnoses and Unnecessary Surgeries utilize the Gower distance. Gower's metric scales each feature independently between 0 and 1, computing absolute differences for continuous variables and binary matches for categorical ones, before taking a weighted average. This prevents features with large numerical ranges from dominating the similarity calculation and ensures that categorical alignments are fairly weighted.
Refined Neighborhoods: Weights and Linear Combinations
Standard $k$-NN imputation treats all $k$ neighbors equally, taking a simple unweighted average of their values. However, intuition suggests that a neighbor sitting right next to the target instance should have more influence than a neighbor hovering on the outer periphery of the neighborhood.
To capture this nuance, advanced variations introduce distance-weighted mechanisms. Haojian Huang demonstrates in An efficient method to classification with missing data that estimating missing values using a weighted average—where each neighbor's influence is inversely proportional to its distance from the target sample—prioritizes more similar data points and significantly improves the accuracy of the filled values. This approach is echoed by Li-Li Tong et al. in Application of Bayesian network and regression method in treatment cost prediction, who use a weighted-distance proximity method to reduce interpolation errors compared to global averages.
Taking this concept a step further, Pilsung Kang shows in Missing Value Imputation based on Locally Linear Reconstruction for Improving Classification Performance that missing data points can be reconstructed via Locally Linear Reconstruction (LLR). Instead of a simple weighted average, LLR treats the target instance as a precise linear combination of its neighbors, reconstructing the missing coordinate by solving a localized optimization problem that preserves the exact geometry of the local patch.
Standard k-NN: Imputed Value = Simple Average of Neighbors
Distance-Weighted: Imputed Value = Closer Neighbors have Higher Weight
Locally Linear (LLR):Imputed Value = Solved Optimization preserving Local Geometry
Knowing When to Stop: Selective Imputation
While similarity-based imputation is powerful, it is not infallible. What happens if an incomplete record is an extreme outlier, sitting in an isolated region of the feature space far from any complete records? In such cases, forcing an imputation from distant "neighbors" introduces low-confidence noise into the dataset.
To address this vulnerability, Shichao Zhang et al. introduce a framework known as Parimputation in Parimputation: From Imputation and Null-Imputation to Partially Imputation. This strategy categorizes missing data into predictable and unpredictable groups based on the distance to their nearest neighbors.
By setting a strict proximity threshold, the algorithm only imputes values when it can find highly confident, close neighbors. Isolated missing values are left as null or routed to alternative strategies. This selective approach ensures that the integrity of the dataset is maintained, preventing the dilution of predictive signals with low-confidence guesses.