Abstract
Linear regression analysis focuses on predicting a numeric regressand value based on certain regressor values. In this context, k-Nearest Neighbors (k-NN) is a common non-parametric regression algorithm, which achieves efficient performance when compared with other algorithms in literature. In this research effort, an optimization of the k-NN algorithm is proposed by exploiting the potentiality of an introduced arithmetic method, which can provide solutions for linear equations involving an arbitrary number of real variables. Specifically, an Arithmetic Method Algorithm (AMA) is adopted to assess the efficiency of the introduced arithmetic method, while an Arithmetic Method Regression (AMR) algorithm is proposed as an optimization of k-NN adopting the potentiality of AMA. Results indicate that the proposed AMR algorithm has comparable performance with other algorithms, while in most cases it achieves better performance than the k-NN, suggesting that AMR is a successful optimization of the k-NN approach.
Introduction
The k-Nearest Neighbors (k-NN) algorithm is a fundamental non-parametric method for regression, valued for its simplicity and local adaptability. However, its reliance on local data points makes it highly sensitive to neighborhood composition, often resulting in high variance and susceptibility to outliers. While complex models like deep neural networks or ensemble methods can offer higher accuracy, they often require massive datasets and significant computational resources, which may lead to overfitting on smaller datasets. This paper introduces Arithmetic Method Regression (AMR), a hybrid algorithm designed to optimize k-NN by integrating it with a deterministic global linear model, thereby balancing local flexibility with global stability.
Methodology
The core contribution of this work is the Arithmetic Method Regression (AMR) algorithm, which blends two distinct predictive components:
1. Arithmetic Method Algorithm (AMA)
AMA is a newly introduced deterministic, algebraic method for solving linear equations. It acts as an approximate left-inverse operator (similar to the Moore-Penrose pseudo-inverse) to capture global linear relationships in the data. Because it is algebraically derived, AMA exhibits very low estimator variance, providing a stable global baseline.
2. k-NN Component
The standard k-NN algorithm is utilized to capture non-linear, local dependencies. While k-NN offers low bias, it typically suffers from high variance.
The Hybrid Approach
AMR combines the predictions of AMA and k-NN using a convex blending weight $\alpha$: $$\hat{y}_{AMR} = \alpha \cdot \hat{y}_{AMA} + (1 - \alpha) \cdot \hat{y}_{kNN}$$
To find the optimal parameters, the algorithm employs leave-one-out cross-validation (LOOCV) to perform a discrete grid search. This search identifies the optimal $\alpha$ and a neighborhood expansion heuristic $\delta$—a multiplier applied to the distance of the nearest neighbor to dynamically include relevant data points. To ensure robustness against outliers, the optimization process utilizes Manhattan distance (L1) and Mean Absolute Error (MAE).
Experimental Design
The AMR algorithm was evaluated against seven benchmark algorithms: k-NN, Linear Regression, Decision Trees (DT), Support Vector Regression (SVR), Random Forest (RF), XGBoost, and 1D-CNN. The evaluation spanned 17 publicly available real-world datasets across various domains, including medicine, finance, and environmental science. These included 12 "small" datasets (43 to 297 instances) and 5 "medium" datasets (398 to 1178 instances). All datasets underwent preprocessing for missing values and dimensionality reduction to select highly correlated regressors.
Results and Discussion
Predictive Accuracy
AMR consistently outperformed the benchmark algorithms, achieving the lowest MAE on 14 out of the 17 datasets. For instance, on breast cancer data (Data-3), AMR achieved an MAE of 25.84 compared to k-NN's 36.49. On low birth weight data (Data-8), AMR reached 475.00 versus k-NN's 534.85. Statistical significance was confirmed using a 5,000-iteration two-tailed permutation test, proving AMR's improvements over k-NN, DT, and CNN are significant ($p < 0.05$) in the majority of cases.
Computational Trade-offs
While AMR offers superior accuracy, it incurs a significantly higher computational cost. The iterative LOOCV grid search required for tuning $\alpha$ and $\delta$ increases execution time (ET) substantially. For example, on Data-3, AMR required approximately 1,615 seconds to execute, compared to just 4.9 seconds for the standard k-NN.
Conclusion
The Arithmetic Method Regression (AMR) algorithm represents a successful optimization of k-NN, effectively balancing global linear trends with local adaptability. While its computational complexity makes it less suitable for time-sensitive applications, its high accuracy on small-to-medium datasets makes it a valuable tool for high-precision regression tasks. Future research will explore more efficient optimization strategies and evaluate the algorithm's performance on larger, high-dimensional datasets.
Summary updated