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. Such algorithm is compared with other regression algorithms, according to an introduced optimal inference decision rule, and evaluated on certain real-world data sources, which are publicly available. Results are promising since the proposed AMR algorithm has comparable performance with the other algorithms, while in most cases it achieves better performance than the k-NN. The output results indicate that introduced AMR is an optimization of k-NN.
Introduction
The k-Nearest Neighbors (k-NN) algorithm is a fundamental, non-parametric workhorse in machine learning, valued for its flexibility and ability to capture local, non-linear patterns. However, k-NN's reliance on local neighborhood composition often leads to high variance and difficulty in capturing global linear trends. Furthermore, it can be highly sensitive to noise and outliers, particularly in small datasets. This research introduces Arithmetic Method Regression (AMR), a hybrid approach designed to optimize k-NN by mathematically injecting global linear trend awareness into its local predictions, thereby achieving a superior bias-variance tradeoff.
Methodology
The proposed framework consists of two primary components: the Arithmetic Method Algorithm (AMA) and the Arithmetic Method Regression (AMR) algorithm.
Arithmetic Method Algorithm (AMA)
AMA is a novel, deterministic mathematical approach to solving linear equations. Unlike standard Least Squares methods that rely on computationally intensive explicit matrix inversions, AMA utilizes direct arithmetic relations to compute polynomial coefficients. This results in a stable, low-variance global parametric model.
Arithmetic Method Regression (AMR)
AMR serves as the hybrid optimization of k-NN. It combines the global predictions of AMA with the local predictions of k-NN using a convex blending equation:
$y_{pr} = \alpha \cdot y_{AMA} + (1 - \alpha) \cdot y_{kNN}$
Key innovations within AMR include:
- Grid-Search Optimization: Blending weights ($\alpha$ and $\beta$) are optimized iteratively using leave-one-out cross-validation to minimize Mean Absolute Error (MAE).
- The Delta ($\delta$) Heuristic: Instead of a fixed $k$, AMR employs a $\delta$ multiplier against the distance of the closest neighbor ($dist_{min}$). Neighbors within the threshold ($dist_k < \delta \cdot dist_{min}$) are included, dynamically scaling the neighborhood based on local data density.
- Manhattan Distance: To enhance robustness against outliers in small datasets, AMR utilizes Manhattan (L1) distance rather than traditional Euclidean distance.
Experimental Evaluation
The authors evaluated AMR against 17 real-world datasets covering medical, environmental, and physical domains. These datasets ranged from 43 to 1,178 instances. Preprocessing involved removing missing values, numerical encoding of categorical variables, and dimensionality reduction to select highly predictive, low-intercorrelation features.
AMR was benchmarked against seven baseline algorithms: standard k-NN, Linear Regression (LR), Decision Trees (DT), Support Vector Regression (SVR), Random Forest (RF), XGBoost, and a 1D Convolutional Neural Network (CNN).
Results and Discussion
Experimental results demonstrate that AMR consistently achieved the lowest MAE, MSE, and RMSE across nearly all 17 datasets. Statistical significance was confirmed using a two-tailed permutation test (5,000 iterations), showing AMR's improvements over standard k-NN were significant ($p < 0.05$) in 15 out of 17 cases.
For instance, on breast cancer data (Data-3), AMR reduced the MAE to 25.84, significantly outperforming k-NN (36.49) and XGBoost (28.80). The success of AMR is attributed to the pairing of AMA’s low variance with k-NN’s low bias.
However, a notable trade-off is computational cost. AMR's iterative grid search and leave-one-out cross-validation lead to significantly higher execution times. On Data-3, AMR required approximately 1,615 seconds, whereas standard k-NN took only 4.9 seconds.
Conclusion
Arithmetic Method Regression (AMR) represents a significant optimization of the k-NN algorithm, successfully blending global linear stability with local flexibility. While computationally intensive, its superior predictive accuracy on real-world datasets makes it a robust choice for small-to-medium scale regression tasks. Future work will focus on improving scalability for larger datasets and exploring additional arithmetic methods to further refine the framework.
Summary updated