Optimizing Weighted Nearest Neighbors via Metric Learning

Learning Feature-Specific Distance Weights with Batch Gradient Descent

Yuelin Liu

Department of Computer Science, University of Nottingham Ningbo China

📄 Read the Full Paper (PDF)

---

Abstract

Nearest neighbor algorithms have been widely used in machine learning, but often yield suboptimal performance in multivariate regression where feature attributes contribute unequally. Performance is strongly determined by the choice of distance metric. The weighted nearest neighbor (wNN) algorithm assigns feature-specific weights during distance calculation to account for variable influence.

In this work, we propose a metric learning-based wNN optimization framework that iteratively learns optimal distance metric parameters via Batch Gradient Descent (BGD) to minimize Mean Squared Error (MSE). The proposed method is evaluated on synthetic data and three benchmark datasets from the UC Irvine Machine Learning Repository (QSAR Fish Toxicity, Boston Housing, and CCPP), demonstrating up to an 80.65% reduction in MSE compared to conventional wNN models.

Keywords: multiple regression · distance metric learning · weighted nearest neighbors · batch gradient descent · optimization

---

Method in Brief

Standard kNN treats every feature as equally informative. wNN instead scales each feature by a learned weight $\gamma_k \ge 0$ inside the distance computation, so that features with little bearing on the response are effectively shrunk out of the neighborhood definition:

$$d(x_i, x_j) = \sqrt{\sum_{k=1}^{m} \gamma_k \left(x_{ik} - x_{jk}\right)^2}, \qquad w_{ij} = \exp\left(-d(x_i, x_j)\right)$$

Predictions are the weight-normalized average over the training set $T$:

$$\hat{y}_j = n_j \sum_{i \in T} w_{ij}, y_i, \qquad n_j = \Big(\sum_{i \in T} w_{ij}\Big)^{-1}$$

Because the training and test samples are fixed, the prediction — and therefore the squared-error loss with shrinkage penalty

$$L = \frac{1}{|U|} \sum_{j \in U} \left(y_j - \hat{y}_j\right)^2 + \lambda \gamma$$

— depends on the data only through $\gamma$. Choosing a good distance metric thus reduces to a smooth optimization problem in $\gamma$. The paper derives the exact partial derivatives $\partial L / \partial \gamma_k$ in closed form (Section 1.3.2) and minimizes $L$ by batch gradient descent, updating all weights against the full training set at each epoch.

---

Results

Table 1. Reduction in MSE loss of BGD-wNN relative to a conventional wNN baseline ($\gamma_k = 1$ for all features), on three benchmark datasets from the UC Irvine Machine Learning Repository. Higher is better.

Dataset	Instances	Features	Improvement (Training)	Improvement (Testing)
QSAR Fish Toxicity	908	6	30.16%	32.87%
Boston Housing	505	14	38.96%	46.15%
Combined Cycle Power Plant (CCPP)	9 568	4	84.40%	80.65%
Synthetic simulation data	—	—	≈80%	≈80%

Experimental caveat. The implementation is unoptimized reference Python — full-batch gradients over all training samples, no tensorization, no GPU. The full 9 568-instance CCPP set did not complete after three hours on the author's machine, so CCPP figures are the mean of nine independent runs on disjoint 1 000-instance subsamples, which together cover the whole dataset. Simulation-data figures are likewise averaged over ten runs to limit sampling noise. Absolute runtimes are therefore not reported and should not be inferred from these results.

Setup. Learning rate initialized at 0.01 with dynamic updating, maximum 100 epochs, features normalized during preprocessing. Both normalization and the adaptive learning rate proved necessary: without them the model converged slowly to a poor solution and the loss curve fluctuated (Figure 5.5).

---

Key Findings

• Learned metrics substantially beat uniform weighting. BGD-wNN improves on conventional wNN across every dataset tested, from 32.87% on QSAR to 80.65% on CCPP. The gain holds across datasets differing in size and dimensionality, which is evidence that the method is portable rather than tuned to one benchmark.
• The optimization is well behaved. Training- and test-set improvements track each other closely on all three datasets, and the loss curves descend smoothly — no overfitting and no fluctuation once preprocessing and learning-rate updating are in place.
• Preprocessing is not optional. On raw, unnormalized QSAR data a fixed learning rate $\eta \in (0,1)$ has no good setting: too large and the loss oscillates into a local optimum, too small and convergence stalls. Normalization plus an adaptive rate resolves both failure modes.
• Neighborhood size dominates the other kNN hyperparameters. A grid search over 1 500 parameter combinations returned $k=3$, Minkowski $p=2$, distance-based weighting — but the gain over a naive baseline came almost entirely from $k$. On the simulation data $R^2$ peaks at 0.87 for $k=2$ and decays to 0.74 by $k=30$, confirming a genuine critical value of $k$ while $p$ contributes little.
• Full-batch gradients are the scaling bottleneck. Every epoch recomputes gradients over the entire training set, so cost grows sharply with dataset size — the practical limit encountered on CCPP, and the motivation for the tensorized/GPU and adaptive-optimizer extensions proposed in Section 6.2.

---

Contents

Section	Topic
1	Introduction — the curse of dimensionality, kNN for regression, wNN model specification, distance metric learning, and gradient descent
2	Related work — margin-maximizing metric learning and its computational cost
3	Design — data preprocessing, training loop, predictor, and demonstrator
4	Implementation — ordinary kNN, grid-search cross-validation, BGD, and the wNN class
5	Evaluation — simulation data and three UCI benchmark datasets
6	Summary and conclusion — contributions, limitations, and future work
7	Bibliography

Implementation. An object-oriented Python architecture (wNN class) encapsulates the matrix operations, feature normalization, dynamic learning-rate updates, and evaluation workflow described in Sections 3–4.

Future work. Section 6.2 identifies four extensions: tensorized/GPU-accelerated computation (PyTorch, JAX), adaptive optimizers (Adam, RMSprop) in place of plain BGD, integration with dimensionality reduction for ultra-high-dimensional problems, and evaluation against $R^2$, MAE, and runtime alongside MSE.

---

Citation

@techreport{liu2020wnn,
  title       = {Optimization of Weighted Nearest Neighbors Algorithm via
                 Metric Learning and Batch Gradient Descent},
  author      = {Liu, Yuelin},
  institution = {Department of Computer Science,
                 University of Nottingham Ningbo China},
  year        = {2020},
  type        = {Technical Working Paper},
  address     = {Ningbo, China}
}

---

License

The paper is made available for academic and educational use. Please cite the work if you reference it. The benchmark datasets used in Section 5 (QSAR Fish Toxicity, Boston Housing, Combined Cycle Power Plant) are the property of their original contributors and are distributed by the UC Irvine Machine Learning Repository.