Bags of Projected Nearest Neighbours: Competitors to Random Forests?
Authors: David P. Hofmeyr
Venue: Accepted by TMLR ()

Abstract: In this paper we introduce a simple and intuitive adaptive k nearest neighbours classifier, and explore its utility within the context of bootstrap aggregating (“bagging”). The approach is based on finding discriminant subspaces which are computationally efficient to compute, and are motivated by enhancing the discrimination of classes through nearest neighbour classifiers. This adaptiveness promotes diversity of the individual classifiers fit across different bootstrap samples, and so further leverages the variance reducing effect of bagging. Extensive experimental results are presented documenting the strong performance of the proposed approach in comparison with Random Forest classifiers, as well as other nearest neighbours based ensembles from the literature, plus other relevant benchmarks.

Published in Transactions on Machine Learning Research (10/2025)
Bags of Projected Nearest Neighbours: Competitors to Ran- dom Forests?
David P. Hofmeyr
d.p. Ap.hofmmegrllanosseer..c
School of Mathematical Sciences
Lancaster Universily, United Kingdom
Reviewed on OpenReview: https: opwpe/veepeeeeeeee.mm net/ forun? id= 2XL,200Ca0
Abstract
In this paper we introduce simple and intuitive adaptive k nearest neighbours classifier, and explore its utility within the context of bootstrap aggregating ("bagging"). The ap- proach is based on finding discriminant subspaces which are computationally efficient to compute, and are motivated by enhancing the discrimination of classes through nearest neighbour classifiers. This adaptiveness promotes diversity of the individual classifiers fit across different bootstrap samples, and so further leverages the variance reducing effect of bagging. Extensive experimental results are presented documenting the strong performance of the proposed approach in comparison with Random Forest classifiers, nearest neighbours based ensembles from the literature, plus other relevant benchmarks. Code to implement the proposed approach is available in the form of an R package from
well other
1 Introduction
Bootstrap aggregating (Breiman 1996), or "bagging", is the approach of combining the outputs of several predictive models, each fit different bootstrap samples from a set of data, into a single ensemble predic- tive model. Bagging has remarkable potential for improving the prediction performance of high variance predictors, due to the variance reducing effect of model averaging. However, it is well understood that not all high variance predictors are able to leverage this effect equally, due to some being "Loo stable" across different bootstrap samples. Bagged ensembles of Decision Tree (DT) based models have undeniably shown the greatest promise to date, to the extent that bagging is sometimes categorisod as a decision tree basod approach (Hastie 2009). The remarkable success of Random Forest (Breiman) 2001 RF) based models has only further entrenched DTs as the de facto "optimally baggable" model. Trees RFs differ from regular DI's only through the addition of a randomisation step preceding each stage in the standard Classification And Regression Trees (Breiman 2017 CART) algorithm. However, this simple modification has a remark- able "destabillssig" effect on the already highly variable trees, and so enables further variance reduction through averaging.
Attempts have been made to emulate the success RFs and bagged DTs with other non- con-parametric models, such as those based on nearest. neighbours (Zhou Yu! 2005 Cannings & Samworth 2017 Gul et al. 2018) However, is questionable whether any of these approaches has the potential to be a real competitor to RFs across many different settings, partly due to limited experimental results having been documented.
A necessary condition for the success of bagged ensemble is substantial diversity in the models (Krogh & Vedelsby 1994). However, existing approaches for inducing this diversity in nearest neighbours (NN) based ensembles have largely been based on randomisation alone (Zhou & Yu, 2005 Domeniconi & Yan 2004
Deegalla et al. 2022), possibly owing to the successful application of randomisation within RFs. But purely randomised methods can only be beneficial if the resulting increase in diversity across models substantially outweighs the decrease in accuracy of the individual models caused by the extra randomness. Where RFs are fundamentally advantaged over these NN ensembles, however, is in the adaptive way in which DTs

---

Published in Transactions on Machine Learning Research (10/2025)
determine their "smoothing neighbourhoods", with the additional randomisation being a secondary factor. The adaptiveness of DTss simultaneously is a primary source of diversity in the models beyond the randomness of the bootstrap sampling, and also reduces the amount by which the added randomness of RFss impacts on the quality of the individual models.
In this paper we introduce an intuitive adaptive Nearest Neighbours (&NN) classifier which computa- tionally efficient to compute, and explore its utility within bagged ensembles. Our main objectives with this piece of work are (i) to illustrate the importance of, and potential offered by, including an adaptive learning step within each model in a bagged ANN ensemble; and (ii) to support this illustration with rigorous and extensive set of experiments.
The remainder of this paper is organised as follows. In the next section we provide some background on bagging, with particular focus on its application to ANN based models. In Section 3 we describe our approach, as well as some of the practicalities surrounding implementation and useful outputs from the resulting models. In Section | we document the results from experiments using all 162 data sets in the Penn Machine Learning Benchmarks repository (Olson et al. 2017, PMLB). Here we compare the performance of the proposed approach with RFs, well as numerous other models for context. RF classifiers are viewed by many as excellent general purpose models; seldom much worse than any others, and frequently among the best performing models on data from extremely diverse domains. In order to support any new model as a realistic alternative in this regard, there should therefore be no possibility of data set selection bias (whether conscious or unconscious) which possible whenever any subset of available data sets without a clear and justifiable selection criterion is used.
2 Bagging, KNN, and What's Been Tried
In this section we provide light technical background on bootstrap aggregating, and discuss some of its applications to ANN based classifiers. Let D == {(x1, 91), (X2,, ........ (Xn, )n)] be sample of realisations from distribution Fx,y, on Rd x [K], where [K] = {I...., K}. That is, the response variables (or "class labels"), yo E [n)] each takes on one of К known and distinct values, and the associated observations of the covariates, x;; i E [n). are each d-dimensional real vectors. This training sample, D, is then used to fit a model, (), which is used to predict the class label for any given query point, x Rd.
Bagging operates by resampling from D multiple times to produce B bootstrup samples, Di...., DB, and then combining the resulting models, g(- (D); b = ...,, B, to obtain final predictive model. Note that whether each bootstrap sample is obtained by sampling with without replacement often has relatively little impact on the performance of the overall model. For ease of exposition we assume sampling without replacement, and in such a way that each bootstrap sample contains ng = [Bn] observations, where Tв E (0, 1).
2.1 Bagging and Variance Reduction
Bagging can be remarkably effective in reducing the variance of flexible predictive models. This is most conveniently communicated when combining the individual models through averaging, i.e., when using
g (bgg) (x
Σ g(x D.). b=1
(1)
B
It is straightforward to show that Hastic 2009
Var (bag) (xl = Var(g(x(D)) (o+ 1-0) B
(x
(2)
where (or(g(((D). Note that although each Do; E [B], has the same distribution as an H sample of the same size drawn directly from the underlying population, it is not the case that the joint distributions of any pair Do Dryj b, + by are the same as those of pairs of independent samples from
I recall that consider resampling without replacement.
2

---

Published in Transactions on Machine Learning Research (10/2025)
the population due to the (potential) overlap of the bootstrap samples. It is this fact which results in Cor(g(x ())) (2)) generally being greater than zero. Bagging is beneficial, therefore, when the bias and variance of g(x Di) are similar to those of g(x)D), iee, using a smaller sample does not affect accuracy too substantially, and where (I)
is relatively small.
Where bagging really shines is when applied to flexible, low-bias models, between which the correlation due to overlapping samples is relatively low. Generally speaking the class of non-parametric smoothing models can be made extremely flexible by selecting small "smoothing parameter". For example, the ANN model bases its prediction for point, x, only the properties of the nearest & points to x from among the x; i [n]. However, ANN, and other so-called "lazy learners", have been referred to as "too stable" from the point of view of bagging, because the correlation induced by overlapping bootstrap samples is substantial. This can be intuited by considering the region of influence of an observation, say X,, as the subset of R to which x; is one of the & nearest from among the sample. Note that this region is completely independent of the obscrvations of the response variable, and may depend on only a very small number of other sample points. This independence of the responses means the standard &NN model is not able to leverage the relationships between the covariates and the response in order to improve its fit (hence the term "lazy learner"). The extreme localisation implicd by the fact that the region of influence of a point depends on so few other points is also why the ANN predictions from two samples with substantial overlap are so correlated. Decision trees, on the other hand, are adaptive non-parametric smoothers, and aggressively exploit the relationships between the covariates and response in how they recursively split up the input space to actively determine the regions of influence of each point. In this way the region of inftuence of each point can be dependent on every other point in the sample. As a result the non-overlapping parts of two bootstrap samples are able to differentiate their respective models sufficiently to induce lower correlation between their predictions.
Remark 1 Although the intuition underlying the effectiveness of bogging is most easily communicated from model averaging perspective, it is worth pointing out that directly averaging class labels is nonsensical. Nonetheless, the formulation in Eq. i applics to the classification context if we use one of the following formulations:
1. The outputs of the individual models, g(x Do);b E [B], are estimates for the full conditional dis- tribution of Y|X xx Taking the average of such outputs is therefore also an estimate for this conditional distribution, and classifying according to the mode of this distribution is Bayes oplimal.
2. The oulpuls of the individual models are indicalor veclors for the predicted class of x. Averaging these indicator vectors and assigning the final classification using the mode is in this case equivalent to the "majority vote" rule. Here the quantity g (hoa) (x\D) not an estimate for the distribution of Y|X- xx but rather an estimate for the distribution of g(x Du), where Do is a sample of size nB draum directly from the underlying population.
2.2 Bagged KNN Classifiers
Although standard KNN models are seen to be stable from the point of view of bagging, there is prevailing opinion that they can be "destabilised" by adding randomisation to the way in which the neighbours of each point are determined. This can be achieved in multiple ways, such as only computing distances on a (random) subset of the variables in Rd (Domeniconi & Yan 2004); by randomly projecting the observations before computing distances (Deegalla et al., (202]]; or by using a random selection of the value of p within the Lo-norm derived distance function itself (Zhou & Yu 2005). By modifying the distance metric a greater variety of points can have an impact on the regions of influence of others. However, none of these approaches is adaptive to the relationships between the covariates and the response, and there is insufficient evidence is
that purely randomised approaches are useful in general. Since the dominant term in equal to pV ar (r(g((((x))))) (D)), a modification such as this can only be beneficial if the reduction in outweighs the increase in the variance of the individual models. However this may be substantial if the modification is purely random.
Nearest neighbours models can be made adaptive by actively learning distance metric to enhance discrim- ination of classes, either globally (Goldberger et al. 2004) or locally (Hastie & Tibshirani 1995). As far
3

---

Published in Transactions on Machine Learning Research (10/2025)
are aware, however, such approaches have been explored within the context of bagging, likely because of the computational demand of fitting a large number of such models. Somewhere between fully adaptive and randomised is the approach of selecting from among multiple ANN models arising from different random projections of the observations. This approach has shown success in the context of bagging (Cannings & Samworth 2017,, however the number of individual ANN models is equal to the product of the number of bootstrap samples and the number of random projections from among which to select each model in the ensemble. This results in considerable computational restriction. A related method (Gul et al. 20188), which also uses selection from multiple randomised ANN models works as follows. First a large collection of models is fit to different bootstrap samples, with each using its own random selection of the variables in R.. Then a fixed proportion of these is selected for inclusion in the ensemble. However, since the selection of each model in the final ensemble is from the same collection of candidates, the models in the ensemble are strongly dependent. To counteract this, the selection of models is not purely based on their apparent prodictive ability, but is also made to ensure some level of diversity in the predictions across models. Al- though the total number of models to be fit is substantially fewer than when fully independent selection is made for each model in the ensemble, this approach is still substantially slower than alternatives. Moreover, this approach loses the statistical "niceness" of bagging, and in particular does not provide any Out-Of-Bag (OOB) estimates for performance. This further limits its applicability when any substantial hyperparameter search is needed to obtain a good model.
3 Bagging Adaptive KNN Classifiers Based on Discriminant Projections
The benefits of adaptive learning (as applied in fitting DTs)) within the context of bagging are at least two- fold: (i) it enables the models to exploit the relationships between the covariates and the response; and (ii) it allows the region of influence of a point to depend on the entire sample, and not only on points which are very local to it. This latter fact induces further differentiation across the out of models fit to different bootstrap samples, and so reduces their correlation.
Making ANN classifiers adaptive by optimising the distance metric used in the nearest neighbour search is intuitively pleasing, and in principle has the potential to achieve the same benefits as those described above for DTs. However, most adaptive ANN methods are considcrably more computationally demanding than is fitting DTS. This limits their application within the computationally intensive bagging framework. What seems largely to have been overlooked, however, is that adaptively modifying the distance metric to enhance class discrimination does not have to be performed in a fully optimal manner in order to leverage the benefits mentioned above. We therefore explore this potential through more computationally efficient alternative, based on finding discriminant subspaces designed to enhance class discrimination as determined by kNN classifiers.
3.1 A Simple Discriminant Subspace for ANN
Discriminant subspaces are subspaces of Rd within which the classes are (relatively) easily separated from one another. Depending on the classifier being applied after projection, different formulations of the discriminant subspace will be more/less appropriate. For example, the well known Linear Discriminant Analysis [Rao 1948 LDA) model, in which each class is modelled with a Gaussian distribution and all classes share a com- mon covariance matrix, has a so-called "sufficient subspace" given by the eigenvectors of $- S0, associated with its non-zero eigenvalues. Here E.p is the pooled within-class covariance estimate and En -" 3-- where Where Σ is the overall data covariance. The more flexible Mixture Discriminant Analysis (Hastie & Tibshirani,
1996 MDA) models each class with Gaussian mixture. If all mixture components across all classes share common covariance matrix, then a similar discriminant subspace can be obtained. When more general formulations are adopted, discriminant subspaces can be obtained by maximising the a classification likeli- hood objective (Peltonen & Kaski 2003), or by maximising some measure of divergence of the distribution with all classes combined from the average within class distribution (Zhu & Hastic (003),, with densities estimated on the projected data. These latter approaches require numerical optimisation, and are thus not computationally competitive with those which can be obtained using highly optimised eigen-solvers.
4

---

Published in Transactions on Machine Learning Research (10/2025)
Generally speaking, however, discriminant subspaces can be thought of as pushing points into high density regions within their own classes, and into low density regions within other classes; and the appropriateness of a subspace depends on how density is being modelled. Motivated by this simple but principled idea, we adopt the following heuristic, which has some similarity with a fully non-parametric MDA. For each i, we let in be the k-th nearest observation to x; from within its own class, and i/2 the k-th nearest observation to x; from among those in other classes. We then define
Ein == 1 1=1
1
x xx,) - (xx)- xT, Emntt == 1 Σ Xi xi: [x: -x;)
(3)
For unit vector u R2; ||u|| the quantity u E,n u (respectively u Lowtu) is then the average squared distance from each point to its k-th same class neighbour (respectively other class neighbour), measured along direction u. Such unit vectors which lead to small values of u Em u and large values of u Eoue u are thus desirable discriminant directions for a kNN classifier. A sensible discriminant subspace is therefore formed by simply taking the leading eigenvectors of E Eout.
Remark 2 Although the quantities u Xi, and u u'xy, will tend not to be preciscly the k-th nearest in- and out- of class neighbours to auT x; (i.c., the ordering of distances changes after projection onto u), they nonetheless lend to be from among the neurer in- and out-of-class points, and so minimising the post-projeclion in-class and mazimising the post-projection out-of-class distonces still has the desired effect.
Remark 3 It is of course possible to combine KNN with alternative discriminant subspaces within a bagged ensemble. However, as described above, the appropriateness of a subspace for discriminating classes depends on how the classes are to be modelled within that subspace. A subspace focused on minimising the near neighbour in-class distonces and marimising the near neighbour out-of-class distances is therefore better suited for classification with kNN than would be, for ezample, the LDA subspace, which is only based on the first and second order structure of the class distributions.
Remark 4 The quantity Emn can be seen as capturing the average local within class covariance, and similar to the overage within component covariance malrir used in MDA with very large number of components. A directly analogous subspace would thus arise from the eigenvectors of Sm ($- E.n). However, we have found substantially superior performance using the eigenvectors of S. E--1Eout- We believe this is at least partly due to the fact that 5 uses a greater amount of information from the sample than does Eig Eij), and therefore intuitively leads to greater diversity across bootstrup samples.
Remark 5 It is worth noting that we use only the k-th in- and out-of-class neighbours of each point when determining the discriminant subspace despite the fact that the classification of a point after its projection is based on all of its k nearest neighbours. This is ultimately because the density, as quantified by KNN, is based only on the k-th neighbour distance. Perhaps more inluilively, minimising the k-th in-class neighbour distance has the effect of making the ball containing all k nearest neighbours as small as possible.
3.1.1 Additional Diversity Through Randomised Variable Selection
As described previously, additional randomness across different models (c.g. through randomised variable selection) can be beneficial if the resulting decrease accuracy of the models arising from this randomness (which may also be seen as a reduction in information) outweighed by the effect of additional diversifi- cation of the individual models. Adaptive models mitigate the reduction in accuracy arising from reduced information, when compared with lazy learners, as they better exploit what information is available and are better suited to filtering out noise.
In our preliminary experiments it became clear that restricting the discriminant subspaces each to lie within their own randomly determined higher dimensional subspace does indeed improve performance in general. How we achieve this is simply by only using information from a (random) subset of covariates in each model in an ensemble. Specifically, let Q C [d] be a subset of the total covariates (which in practice is determined randomly), with IQI = go; and let IQ E Rdx have as columns the cardinal basis vectors for the
5

---

Published in Transactions on Machine Learning Research (10/2025)
dimensions in Q. Then define is and E/ as before, except with distances only computed with the variables in Q. We then define the discriminanl matrix, whose eigenvectors define the discriminant subspace, simply by Á : To [ (oSinTo) Io)
-1 (T) To PouTTo To-
Note that an additional benefit of this simple modification is that it can greatly reduce computational cost. This is because nearest ncighbour search and matrix inversion only ever need to be performed in dimension at most 40, and for large we have found Qo x v is more than adequate to achieve high accuracy.
3.2 A Full Model
Here we give a brief overview of our approach, which follows a standard format for the bagging framework. With settings for e N, the number of neighbours; go E [d], the number of randomly selected covariates usod in model; and q E [go], the dimension of cach discriminant subspace, do the following for cach b E [B]:
1. Draw Dj = ((x1,,8))),....... (Xng) Mag without replacement from D.
2. Draw Qs of size qu without replaccment from [d].
3. For each [na] find e and ih the k-th in- and out-of-class neighbours of 12 x, from among
(Ta, Xye belmeldzi-
4. Compute the discriminant matrix,
n
ng Xxx X (x,) -xx))
Â IQu [
x -xx) X2 xxx)(xxx (xxxx-xxx))
I
nB
nB
and let Ås = U, be its cigen-decomposition.
Form Dbx based on the class labels of the k nearest neighbours of 1 from (U X1, Ug (0.1:gXx11 high either by taking the proportions in each class or the indicator vector for the most frequent class. Here we have used Ub.1. Raxa to denote the first g columns of U,
Then obtain the final prediction by taking the mode of 1
3.2.1 Additional Useful Outputs
Interpretability of fioxible predictive models is increasingly a point of focus, as modern methods typically rely on intricate relationships between the covariates and the response variable which may not be explicitly expressed within the model in any intelligible form. Variable importance scores are measures of the overall contribution of the covariates to the predictions made by model. Although far from encapsulating the entirety of what model has captured in the data these are nonetheless useful diagnostics for understanding which are the important variables driving the model's predictions.
Variable Importance
The discriminant subspace framework offers an intuitive means by which the contribution of each variable to the model predictions may be quantified. In particular, if a variable lies within the discriminant subspace from one of the models in the ensemble, then it is natural to view that variable as important to the predictions from that particular model. On the other hand if variable lies in the orthogonal complement of the subspace then this variable is unimportant. In general none of the variables will lie entirely within/ within/withoutt without any of the discriminant spaces, but there will be some non-zero angles between them. If U has columns normalised (not necessarily orthogonal) basis for a subspace, then the cosines of the principal angles between the subspace and each of the variables in the cardinal basis can be seen as capturing the importance ance of each variable to the subspace and lie in the diagonal elements of UUT, To further capture the relative discriminatory information in the dimensions of the subspace, we weigh the basis vectors, which arisc from the spectral decomposition of the discriminant matrix, by the eigenvalues. To determine the importance of the j-th variable to the entire ensemble then average its importance values from each of the subspaces

---

Published in Transactions on Machine Learning Research (10/2025)
(a) Subspace from single model using the proposed ap- (b) Subspace from the propused ensemble, using the PCA basis from the averaged projections
proach
(c) Linear Discriminant Analysis subspace
(d) Mixture Discriminant Analysis subspace
Figure 1: 2-Dimensional projections of the cen-based recognition of handwritten digits data set (left pair of plots in each subfigure) and the segmentation data set (right pairs).
in the model. Specifically, we take the importance of the j-th variable to the predictions from the ensemble to be 2/8 (Vo( Dis where V, E Rd has as columns the first g columns U,A!! 1/2 where U, and A contain the eigenvectors and eigenvalues of the b-th discriminant matrix, Å
Visualisation A further advantage of discriminant subspaces is the fact that they reduce the dimen- sionality of the observations. This can be beneficial for obtaining visualisations of the classes, and their separations from others, as well as the predictions made by model. However, single discriminant ma- trix within an ensemble, bb; e [B], is subject to fairly high variation. Moreover how to select from among multiple discriminant subspaces to obtain a single visualisation is not immediately obvious. We therefore aggregale the information from all discriminant subspaces, by determining the ensemble projection P : Eh=1 1b,1.g 1 matrix. To obtain a visualisation of the observations in the aggregated discrim- inant subspace project them onto the principal components basis vectors computed from the aggregate projected observations {
Px,
Figure shows two examples, where projections of two of the data sets used in our experiments are shown. Each sub-figure contains four plots, with the left pair showing the first four discriminant projections of the sixteen dimensional pen-based recognition of handwritten digits data set (Alpaydin & Alimoglu 1996). and the right pair those of the nineteen dimensional segmentation data set (imal 1990). The points depict the projections of independent test set separate from the "training" set used to obtain the actual projection directions, and the colours and point characters represent the individual classes. Figure [(a] shows the result from single discriminant subspace using all training observations and all variables to compute Σ Sout. while Figure [bb shows the aggregated discriminant subspace from an ensemble of 100 models with qu [0.75d] and = 0.5go] In both cases & was set to three. Both show fairly clear separation of the majority of classes from others, with the ensemble showing these more clearly. For comparison we have also included the discriminant projections arising from LDA and MDA Figure [(c) and Figure [(d] respectively. LDA shows good separation of the segmentation data set, but less so for the digits data set, while for MDA is the reverse.
[(a]]sows

---

Published in Transactions on Machine Learning Research (10/2025)
4 Experimental Results
4.1 Data Sets
For our experiments we considered all 162 classification data sets in the Penn Machine Learning Benchmarks database (Olson et al.) 2017]. We repeatedly sampled training and test sets from each data set, with training sets constituting 70% and test sets the remaining 30%. The number of times sampling training/tes splits varied by overall sample size, n, as follows: 0 n < 500 : 50 times; 500 I
1000 20 times; 1000 < 5000 10 times; and 5000 S n: 5 times. The one exception is that, due to the very large amount of compute time required for all experiments, training sets were capped at 7000 points and test sets at 3000 points (however, different total 10 000 points was used in each training /tsst combination, where relevant).
Before passing the data sets to the different algorithms and models for fitting and prediction, all categorical variables were first ennooee. The only exception to this was in the case the random forest models, since dccision trees are able to handle categorical variables directly.
4.2 Classification Models and Tuning
Below we give a brief overview of the different models used for comparison, as well as how model sclection was conducted for each. Although our primary interest is in the comparison between the proposed approach and the Random Forest models, we also include number of alternatives for additional benchmarks and context.
1. BOPNN: The proposed approach (Bag Of Projected Nearest Neighbours), where each ensemble com- prised a bag of 100 ANN models (i.e., B = 100). For each data set and training sample, thirty values for & (the number of neighbours); 4o (the size of the random subset of covariates sampled for each model); and (the number eigenvectors of each ÅS retained) were sampled uniformly as k ~ U(f1,..., 5.),:))): (((.p!/2),..., [[ ),,p)/) and gl40 ~ Uf( - 1}) respectively. Models were fit for each set- ting of these hyperparameters and with the size of each bootstrap sample being 0.63 times the size of the training set (TB = 0.63). The model with the highest Out-Of- estimate for classification accuracy was then applied on the test set.
2. BOpNN: Equivalent to above, except no discriminant subspace was found for each model (or equivalently was always set to 9o). This variant is included primarily to give clear indication of the benefit of including an adaptive learning step (the determination of a discriminant subspace) within a bagged model of otherwise lazy learners.
3. BNNx: A bagged 1-NN model where the proportion of the sample included each bootstrap sample is set equal to
2
2
F+4
WB
2r
2
p
K
where & is an estimate of the optimal value for lo in a single &NN model, based on the leave-one-out cross- validation estimate for classification accuracy. This setting is a plug-in estimate for the asymptotically optimal value (Samworth 2012). Note that for & = this proportion is greater than one, and in this case
we simply set BB = 0.9.
4. BNN: As above except where Th is tuned using OOB performance. This is included for comparison with BNN to test the appropriateness of the plug-in estimate for the asymptotically optimal value for πn.
5. ANN: A single &NN model with h selected using the leave-onc-out vross-validation estimate of classification accuracy.
The KNN ensemble which combines a selection from a large number of models fit to different bootstrap samples with different random subsets of the covariates (Gul al. 2018)). Unlike the baggod models above, this approach suffers unless the total number of &NN models is very large. Moreover, since relevant. OOB estimates for performance are available, the compute time required for this approach was
6. ESANN:
8

---

Published in Transactions on Machine Learning Research (10/2025)
substantially greater than any of the other methods. As result, we used single 25% validation set for estimating performance and only selected & from the set {1,.... 10}. We fixed all other parameters equal to their defaults in the ESKNN packag These settings deviated from the approach used by Gul et al. (2018) only in that a single validation set, as opposed to cross-validation, was performed to select k, and we used 501 initial models (as the default in the package) instead of 1001. Even with these changes, experiments with this approach required substantially larger compute time than any of the other methods. We also did not observe appreciably superior performance when using 1001 models instead of 501.
7. RF: The random forest classifier, implemented in the R [R. Core Team 2024 package randomForestsRG (Ishwaran & Kogalur 2019), available on CRAN. Following the same approach as for BOPNN, hyperparameter selection was conducted from 30 random selections based on OOB performance. The parameters which were tuned are "mtry" (the number of randomly selected covariates selected as candi- dates for each split in a tree), which was selected from the interval [0.1p!/2 min 10p1/2]]; }]; and the minimum size of leaf node in tree, from (1,...10])
8. SVM: The Support Vector Machine classifier, where multiple classes were handled using the one-vs- one approach. We used the LiquidSVM implementation (Steinwart & Thomann 2017), which uses fast technique to approximate the kernel matrix but has nonetheless shown excellent performance in comparison with exact methods (Steinwart & Thomann 2017). We used the default tuning grid and cross-validation settings provided in the implementation.
9. RDA: Regularised Discriminant Analysis (Friedman 1989) where each class is modelled using Gaussian distribution and class probabilities are determined using Bayes' rule. The means of the component distri- butions, f A,k are determined by the sample means of the points from each class, while the covariance matrix of the j-th component is set equal
= : +
2 2trace(2;()))) P
Σy()) A)nz + An
1-X
(x. - (x-xx))(x - Ab) + Σ ky:=j
A 1- x
Σ (xi P,y - )
where À and y are hyperparameters which must be chosen, and for which we used 5-fold cross cross-validation
4.3 Summarising Classification Performance
Here we provide an overview of the classification performance of all methods across the collection of 162 data sets used for comparison. To combine the results from different data sels, which may have vastly different characteristics and represent classification tasks of varying difficulty, we first standardise the results. We consider two standardisations, and apply them to the classification accuracy values from the collection of models obtained on each data set, and each repetition of the sampling of training/ test splits. For each model and each data set, we then take the two averages of its standardised accuracy values across the different test sets its performance for that data set. Specifically, if Am,it is the accuracy of the m-th model the t-th train/ /aint/ Lest split from the i-th data set, then we compute
A = Am,it - min, Ao,
A = Am,tt - A s s(A,;,))
max, Ao.i.t min, Ao.itt"
where at and s(,, are the average and standard deviation of the accuracy values from all methods on the t-th train/test split of data set In the case of A this simply maps the accuracy values to the interval [o, 1], while A is the common studentised value for Am,it- The performance values for each method on given data set then just the averages of these standardised accuracies over t.
9

---

Published in Transactions on Machine Learning Research (10/2025)
8
8OPNN
80ptiN
BKALIT
BRN
ROA
ESOIN
(a) Accuracy values mapped to the [0.1] interval
(b) Studentised accuracy values
Figure 2: Boxplots accuracy distributions for different classification models, using two different standard- isations.
4.3.1 Accuracy Distributions
The distributions of standardised accuracy measures across all 162 data sets are shown in Figure The main take-aways are summarised
The average performances of BOPNN and RF are extremely similar, with BOPNN having slightly higher average but with RF having wider distributions. This is noteworthy since RF classifiers have commonly been referred to as excellent general purpose models; seldom substantially worse than any alternatives. These results suggest BOPNN similarly enjoys this feature, with arguably better "worst-case" than RF due to a similar average and narrower distribution.
1.
SVM outperforms all methods except the bagged models of adaptive non- non-parametric smoothers (BOPNN and RF).
2.
3. BOpNN is substantially inferior to BOPNN, showing the importance of the adaptive learning step within the bagged model.
4. BOpNN is substantially superior BNN. Although these two bagged models were tuned over disjoint collections of hyperparameters, the magnitude of the difference in performance is some indication that the purely randomised variable "selection" does indeed offer improvement over its exclusion.
5. BNN is substantially superior to BNN.c. This suggests either that it is inappropriate to rely on the asymplotic theory for relatively small samples, or that the estimate for the asymplotically optimal TB itself is too unreliable.
6. ESANN performed very poorly, and was the worst performing model on a large proportion of the data s
4.3.2 Pairwise Comparisons
Figure shows the standardised accuracy values of all methods across all data sets. It is noteworthy that the dendrogram along the top axis of each sub- nab-figure shows the performance of BOPNN is most similar to that of SVM. This is interesting since the average performances of BOPNN and RF are much more similar to one another than is either to the average from SVM. Yet, BOPNN seemns to perform well/poorly on many of the same data sets as SVM, and to the extent that this overcomes the closer similarity of its average performance
Prreviously the Comprehensive R Archvive Network (CRAN), and taken from https://ccaa..--rrjjjeee wttppoottcttootooe///o org/src/ Doatrib/Archive/ESSee
"It worth noting that the code released by the authors (previously CRAN) included minor errors, such populating arrays though they lists. Although we took to correct these appropriately, impossible that errors made.
10

---

Published in Transactions on Machine Learning Research (10/2025)
Color Key
Color Key
Vele
Velue
RDW
SW
gra
nopen
MAR
n
SWM
(a) Accuracy values mapped to the [0. [] in- terval
(b)
Studentised accuracy values
Figure 3: Standardised classification accuracy across all data sets
BOPNN
BOPNN
Tea
RF
SVM
SVM
(a) Accuracy values mapped to the [0, 1] interval
(b) Studentised accuracy values
Figure 4: Pairwise plots of standardised accuracy for the three top performing methods: BOPNN, RF and SVM
that of RF. This can also be seen in Figure 4 where pairwise plots of the standardised accuracy values for these three models are shown. Interestingly the studentised performances of BOPNN and RF negalively correlated whereas those of BOPNN and SVM more less uncorrelated.
In addition Table [ shows the number of times, out of the total 162, the method listed row-wisc achieved significantly superior performance to the method listed column-wis on given data set. Significance was determined based on a paired Wilcoxon signed rank test (Wilcoxon, 1992) with test size 0.05 Once again we are particularly interested the comparison between BOPNN and Random Forests. Although the average performance of BOPNN is slightly superior, as shown in the previous subsection, we see here that RF outperformed BOPNN more frequently than the reverse. What interesting to note is that RF both
We acknowledge the arbitrariness of this test size, and do not to indicate any statistical relevance of these compar- isons. Rather, appropriatcly accounting for some of the randomness inherent such comparison. It also worth pointing that this the smallest commonly used size which is achievable sample of size 5, and we repeated the training teattng/ttsttte test splits larger data sets five times.
only give seuse of the frequency with which each method outperforms each other method, while
11

---

Published in Transactions on Machine Learning Research (10/2025)
BOPNN RF
SVM
BOPNN
BNN
ANN
BNN
RDA
EISENNN
ROPNN
0
37
53
60
107
46
57
71
101
101
114
SVM
33
35
62
105
100
BOpNN
6
19
33
23
73
76
92
92
BNN
4
13
26
U
66
72
84
84
ANN
6
19
21
7
25
0
16
72
81
BNN
3
15
17
20
8
0
64
85
RDA
9
18
15
29
41
44
45
0
64
ESANN
S
11
17
21
31
41
45
55
Table 1: Pairwise comparative accuracy. Values in table indicate the number of times the method listed
row-wise significantly outperformed the method listed column-wise. For example, BOPNN significantly out- performed RF 37 times, while RF significantly outperformed BÖPNN 46 times. Significance was determined using a paired Wilcoxon signed rank test, with size 0.05.
outperforms the majority of the other methods more often than does BOPNN, and is also more frequently outperformed by them; indicated by greater values in the RF row and column than those of BOPNN.
4.4 Relationships between Performance and "Meta-data"
Here we investigate the relationships between the relative performance of the different methods, and the characteristics of the data sets, Each data set is characterised by six variables, n: the number of observations; d: the total number of variables after one-hot encoding; cat_prop: the proportion of binary variables in the one-hot encoded data; K: the number of classes; imbal: the class imbalance, defined as the variance of the class proportions; and compl: a measure of the complexity of the class decision boundaries, defined ANe), where AINN the leave-one-out cross-validation estimate for the accuracy of the 1-nearest- neighbour classifier on the data, and ANC that of the nearest centroid classifie To capture dependence we computed the marginal correlations between the studentised accuracy of each method over all data sets and the data set characteristics (after log- transforioigng and d). well as the Ordinary Least Squares (OLS) linear regression coefficients after standardising all variables These OLS coefficients give indication of the correlations between the data set characteristics and the studentised performance after accounting for the values of the other data set characteristics.
as log( log(Arww),
Figure shows healmaps indicating the strengths of these relationships, with the marginal correlations in the left heatmap and the OLS coefficients in the right. Because these relationships are determined from a standardised accuracy mcasure, they give an indication of the relationships between the diffcrent methods and data set characteristies relative to the other melhods considered. For example, we expect all methods will perform relatively better larger data sets, all other things being equal. This would correspond with light colours in the first column of the right heatmap (positive OLS coefficients), however some methods are better/ worse at leveraging larger samples than others and this is reflected by both positive AND negative OLS coefficients in the renships with standardised accuracy. The lightest colours this column indicate that RF, SVM and BOPNN might benefit more from larger samples than the other methods (with SVM benefiting the most). This is unsurprising as these are all very flexible models. Also unsurprisingly the parametric RDA does not leverage large samples well in comparison with the other models being considered. The "lazy" non-parametric ANN based models also do not leverage large samples well the adaptive models. ESANN has an element of adaptiveness, in its selection from multiple randomised models, however the level of adaptiveness may not be sufficient. to leverage larger samples particularly well. Some other noteworthy take-aways, for the purpose of this investigation, are:
1. BOPNN performs relatively very poorly in the context of class imbalance. This may be a result of the fact that the adaptive component of BOPNN comprises a linear transformation, and so applies globally, and
The nearest centroid classifier simply classifies point to the class whose mean vector closest. we used studentised performance instead of the [0, 1] mapped performance their distributions are closer Gaussian and, all other things being equal, may therefore be appropriate when used quantifying linear relationships. This is also the for log-trand tagnsfonnoo n and d.
12

---

Published in Transactions on Machine Learning Research (10/2025)
Color Key
-0.6
-0.2
0.6
BNN
BNN_
BOPNN
KNN
BOPNN
RDA
ESKNN
SVM
cat prop
Imbal
compl
cat, prop
imbai
compl
Figure 5: Relationships between studentised accuracy and data set characteristics. Left: marginal correla-
tions, Right: standardised OLS coefficients
with the current implementation will be dominated by the larger classes. The local, more flexible component of BOPNN comes subsequently from the application of &NN on the transformed data.
2. BOPNN has strong positive relationship with the "complexity" of the decision boundaries. However, it is possible that this result is somewhat artificial, given that the measure of complexity is governed by the performance of the 1NN model. Having said this, this performance is quantified relative to the other methods being compared, which includes numerous other nearest neighbour based methods.
3. The simplistic one- mue-hot-encoding followed by Euclidean distance calculation currently employed in BOPNN may be inappropriale, as indicated by comparatively poor performance when a large number of categorical variables are present.
4. Although BOPNN performed reasonably well data sets with large number of classes (light colour in the left meatmap for BOPNN and K), this appears to be almost fully delermined by the other characteristics of those data sets with large K since it has strong negative OLS coefficient for K.
5. Compared with Random Forcsts, BOPNN may be better suited to higher dinensional examples but may leverage larger samples less well.
4.4.1 "Meta-data" Distributions
For completeness here we also provide illustrations of the (marginal) distributions of the data set character- istics. Figure G shows all the values of all six data set characteristics across the 162 data sets. In addition, the performance of BOPNN indicated via the sizes of the points, with larger points aligning with instances where BOPNN performed well relative to the other methods considered.
5 Concusions
In this paper we discussed the importance of including an adaptive learning step within the context of bootstrap aggregating, or "bagging", and proposed simple adaptive ANN model for use within "baggod" ensembles. The adaptive step achieved by finding discriminant subspaces which enhance the class separa- tion, captured by &NN classifiers. The discriminant subspace framework naturally leads to measures of
13

---

Published in Transactions on Machine Learning Research (10/2025)
1.0
1000
collgonical proporton
0.8
1000
066
Do
0,4
100
0.2
0.0
25
0.4
0.3
complesitt
K
0.2
0.0 0.1
7
Figure Distributions of "meta-data", with n and d on a. log scale. The sizes of points are related performance of BOPNN with larger points corresponding with botter BOPNN performance, relative to the other methods considered.
variable importance and offers instructive visualisations of the classes through projections into the discrimi- nant subspaces (or aggregated variant incorporating the entire ensemble).
In an extensive set of experiments we documented the strong potential offered by the proposed approach. Noteworthy findings are that across varied contexts the proposed approach is more or less on par with Random Forests, on average, but that the particular data sets on which the proposed approach may be more or less suited in fact align better with Support Vector Machines. Potential directions for improvement of BOPNN include an alternative, but computationally efficient, way incorporate categorical variables, well strategies to enhance performance with highly imbalanced class proportions.
Acknowledgements
We would like to thank the reviewers for their valuable comments which helped to improve the quality of this work.
References
Statlog (Image Sogmentation).
UCI Machine
Learning
Repository,
1990.
DOI:
CC501G..
E. Alpaydin and Fevzi. Alimoglu. Pen-Based Recognition of Handwritten Digits. UCT Machine Learning Repository, 1996. DOI: http:://ddi.org/002222..... CCMA...
Leo Breiman. Bagging predictors. Machine learning, 24:123 140, 1996.
Leo Breiman. Random forests. Machine learning, 45:5-32, 2001.
Leo Breiman. Classification and regression trees. Routledge, 2017.
Timothy I Cannings and Richard Samworth. Random ensemble classification, Journal of the Royal Statistical Sociely Series B: Statistical Melhodology, 79(4):959-1035 2017.
14

---

Published in Transactions on Machine Learning Research (10/2025)
Sampath Deegalla, Keerthi Walgama, Panagiotis Papapetrou, and Henrik Boström. Random subspace and random projection nearest neighbor ensembles for high dimensional data. Espert systems with applications. 191:116078, 2022.
Carlotta Domeniconi and Bojun Yan. Nearest neighbor ensemble. Tn Proceedings of the 17th International Conference Pattern Recognition, 2004. ICPR 2004., volume 1, pp. 228-231. IEEE, 2004.
Jerome H Friedman. Regularized discriminant analysis. Journal of the American statistical association, 84
(405):165-175, 1989.
Jacob Goldberger, Geoffrey E Hinton, Sam Roweis, and Russ R. Salakhutdinov. Neighbourhood components analysis. Advances in neural information processing systems, 17, 2004.
Asma Gul, Aris Perperoglou, Zardad Khan, Osama Mahmoud, Miftahuddin Miftahuddin, Werner Adler, and Berthold Lausen. Ensemble of subset of k nn classifiers. Advances in data analysis and classificalion, 12:827-808 840, 2018.
Trevor Hastie. The elements of statistical learning: data mining, inference, and prediction, 2009.
Trevor Hastie and Robert Tibshirani. Discriminant adaptive nearest neighbor classification and regression. Advances in neural information processing systems, 8, 1995.
Trevor Hastie and Robert Tibshirani. Discriminant analysis by gaussian mixtures. Journal of the Royal Statistical Society Series B: Statistical Methodology, 58(1):155-176, 1996.
Hemant Ishwaran and Udaya B Kogalur. Fast unified random forests for survival, regression, and classification (rf-src). R package version, 2(1), 2019.
Anders Krogh and Jesper Vedelsby. Neural network ensembles, cross validation, and active learning. Advances in neural informalion processing systems, 7, 1994.
Randal S. Olson, William La Cava, Patryk Orzechowski, Ryan J. Urbanowicz, and Jason H. Moore. Pmlb: a large benchmark suite for machine learning evaluation and comparison. BioData Mining, 10(36):1 13, Dec 2017. ISSN 1756-0381. doi: 10.1180//133400-07--11444 URL https://doi. arg/10. 1 813040-017-0154-
Jaakko Peltonen and Samuel Kaski. Discriminative components of data. IEEE Transactions on Neural Networks, (6(1):68-83, 2005.
R Core Team. R: A Language and Environment for Statistical Computing. Computing, Vienna, Austria, 2024. URL https://www. R- projject.... org/
R. Foundation for Statistical
C Radhakrishua Rao. The utilization of multiple measurements problems of biological classification.
Journal of the Royal Statisticnl Society. Series B (Methodological), 10(2):159 203, 1948.
Richard J. Samworth. Optimal weighted nearest neighbour classifiers. The Annals of Statistics, 40(5):2733 2763, 2012. doi: 00.1214/12-AO1108 URL https: wtt.:///r....111112-0000.000000
Ingo Steinwart and Philipp Thomann. liquidsvm: A fast and versatile svm package. ar preprint wwXiv:1702.0666 06899, 2017.
Frank Wilcoxon. Individual comparisons by ranking methods. In Breakthroughs stofistics: Methodology and distribution, pp. 196 202. Springer, 1992.
Zhi-Hua Zhou and Yang Yu. Adapt bagging to nearest neighbor classifiers. Journal of Computer Science and Technology, 20(1):48-54 2005.
Mu Zhu and Trevor Hastie. Feature extraction for nomparametric discriminant analysis. Journal of Computational and Graphical Statistics, 12(1):101-120, 2003.
15

---

Published in Transactions on Machine Learning Research (10/2025)
A Additional Experimental Results
A.1 Alternative "Discriminant Subspaces"
As mentioned in Section 3.1 it is possible to pair kNN classifiers with other dimensionality reduction tech- ggques/discrmmiaan subspaces within bagged ensemble. However, we discussed, the appropriateness of different subspaces will depend on the type of classifier being used, and the proposed approach is motivated specifically by minimising the in-class and maximising the out-of-class near neighbour distances and so we anticipate that this will pair particularly well with ANN. It is also the case that the discriminant matrices used within the proposed approach use much finer detail in the data than, c.g. the LDA discriminant matrix, and so we expect greater differentiation the individual models across bootstrap samples; a key factor in leveraging the benefits of the model averaging framework.
Here we present experiments documenting the improved performance using the proposed approach, and bagged ensembles of kNN models fit within LDA discriminant subspaces and Principal Components (PCA) subspaces. We include PCA for illustrative purposes, it represents fundamental unsuperwised dimension reduction model, and so it represents an alternative which is not completely randomised but is not adaptive to the relationships between the response and covariates. non-arbitrary dimensions in the LDA subspace, when using more than - 1 discriminant dimensions we combined the L.DA subspace with the leading PCA dimensions within their orthogonal complement. For as direct comparison as possible used exactly the same tuning strategy for these variants as for BOPNN.
addition, since there are only at most K
The distributions of standardised accuracy measures shown in Figure 7 We only show the better per- forming and most relevant models from the point of view of these comparisons, however the standardisations were determined using the entire collection of (now 11) methods. Of note is that (i) using the LDA subspace (BOLDANN) leads to performance similar to that of SVM, on average; (ii) applying PCA appears to be detrimental to performance, in general, as the performance of BOPCANN is inferior to that of BOpNN; and (iii) after including these two additional models the average studentised performance of RF is now marginally above that of BOPNN, however the the other points of comparison are unchanged, and also the average performances of RF and BOPNN remain extremely similar.
00 02 0- 0.6 0.8 10
7
BOLDAYN
BONNN
BOPCANN
BOşNN
(a) Accuracy values mapped to the [0, 1] interval
(b) Studentised accuracy values
Figure 7: Standardised accuracy distributions relevant for comparison with the alternative bagged KNN mod- els applied on "discriminant subspaces".
A.2 Default Settings and the Effect of Varying k
In preliminary experiments with BOPNN we worked with default seitings of go = (0.55, 5vd) [0.5go] and A = 3, and found these to be fairly reliable. However, unlike with RFs where the dimensionality restriction through randomised variable relection/restrictte
only applies locally (i.e. separately at each node in the troes), the expressiveness of cach of the models in BOPNN is fundamentally limited by the value of q (and hence du as well). In particular when the number of classes, K, is reasonably large then it may be impossible to separate all classes accurately in even the theoretically optimal subspace if its dimension is
16

---

Published in Transactions on Machine Learning Research (10/2025)
80PM/
5VM
BOPAN7
5UN0
(a)
Accuracy values mapped to the [0, 1] interval
(b) Studentised accuracy values
Figure 8: Standardised accuracy distributions relevant for comparison with default settings.
too low. is likely, therefore, that settings of qo and q should also depend on K. It may also simply be that this limitation in expressiveness unavoidable in any general sense, and that some degree of tuning is necessary consistently yield very good performance.
Here present results analogous to those in Section A.1 except that we have included default variants of RF and SVM (named RF0 and SVMO below) as well as BOPNN models with the above settings of and and for k = 2, 3, 4 and 5. The distributions of standardised accuracy values are shown in Figure S As before the standardisations have been determined using all (now 16 models; 9 main models plus two defaults from competing methods and 5 fixed settings for BOPNN) methods, but we only show the most relevant ones here.
Noteworthy observations that (i) none of the fixed setting BOPNN models is competitive with the tuned RF, SVM and BOPNN models; (ii) default settings for RF leads to similar overall performance to that of tuned SVM; (iii) the fixed setting of k 2 provided the best overall performance of BOPNN (however whether this is generalisable to potentially improved defaults for 4o and q is unclear); (iv) the default variant of SVM and the best fixed BOPNN model (BOPNN2) have very similar overall performance; and (v) although not directly apparent from these figures RFO, SVMO and BOPNNI-4 all outperform all of the other (Luned) models not included these plots and only BOpNN outperforms BOPNN5 from among them.
One other point is that, performance of RF is greater than that of BOPNT (in their luned variants). However, it is worth pointing out that studentisation in the context where there is high degree of correlation will tend to "over standardise" the performance of groups of models whose performance highly correlated. The reason for this that on data sets where the performance of these models is either well above or below the others, this over over/under "achievement" normalised by the presence of multiple models with similar extreme performance. Tn particular, if only include one default setting of BÖPNN (any of the five) in the standardisations, then the average studentised performance of BOPNN remains above that of RF.
saw in Scction A.1 upon including additional models the average studentisod
A.3 Computational Complexity and Running Times
The worst case complexity of BOPNN O qo + (8)), since the main computational steps within each of the B models in the ensemble involve finding the in- and out-of-class neighbours in dimension go, and for
17

---

Published in Transactions on Machine Learning Research (10/2025)
RF
BОPNN
dg
Wall-clock
CPU
Wall-clock
1600
1000
1969
3.8
19.4
121.9
7000
16
3.6
16.8
10.5
7000
784
864
14.6
81.0
102.2
Table 2: Average running times of RF and BOPNN three of the larger data sets used in our experiments.
inversion and eigen-decomposiiionn of go x %o matrices. However, when do relatively small the running time of nearest neighbour search is closer log(n) than to n², meaning that for cases of moderate dimensionality the running time is close to (lkn log(n))). A potential avenue for improvement computationally is to include variable screening stage, to obtain heuristic variable importance scores for non-uniform sampling of covarariates so that can be set relatively small even when the total dimension is large. It is worth pointing out that in order for the OOB estimates of performance to be valid, these variable importance scores would need to be computed within each model in the ensemble.
To illustrate the poor scaling with dimension, we here report the empirical running times of BOPNN and RF (with their default settings) on three of the larger data sels used in the experiments; one with very large d, with fairly large n and small d, and one with fairly large and d. We only consider the larger data sets as these are the most critical when it comes to running time comparisons. It is worth pointing out that our implementation of BOPNN has not been optimised for speed, and runs in serial on a single thread. On the other hand the RF implementation in the package randomF FresttRC is highly optimised and parallelised. As result we report both the wall-clock time of RF and the total CPU time, whereas for BOPNN these are course very similar and we only report wall-clock time.
The average rumning times from ten to be the number of raw covariates and d to be the number of covariates after onc-hot-encoding. We include both since RF handles categorical variables directly, and operates in dimension do- Aside from the very high dimensional example the total CPU time required for fitting RF models and BOPNN models is similar, however the multithreading used in the implementation of RFs in randomForestsRG means the actual running times are not currently comparable. Nonetheless these experiments indicate that BOPNN has the palential to be computationally competitive with efficient RF implementations, potentially with the exception of when the number of covariates is very large.
each data set shown in Table 2 Here have used do
18


Reviews:
[{"review_id": "xVwjdFOhTe", "reviewer": "Reviewer_RcFn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes BOPNN, bags of projected nearest neighbors classifier, for improving the performance of kNN with bagging. The authors formulate a k-nearest neighbor covariance matrix, which is the covariance matrix of sample x to its k-th NN, and find the projection direction that maximizes the within-class covariance and minimizes the inter-class covariance. \n\nStrength:\n1. The idea is simple and straightforward.\n2. The paper conducted quite thorough experiments on 162 ML datasets. The empirical evaluation is very solid to support the claims.\n\nWeakness:\n1. The paper lacks theoretical results. It is mostly am empirical paper.\n2. As an empirical paper, the experiments should be more comprehensive. I appreciate that the authors tested a lot of datasets, which is impressive. However, more ablation study is needed to better understand what's going on. \n\nFor example, the core idea for the proposed method is to \"destabalize\" individual kNN classifiers. This is done by projecting original data on lower dimensional subspace with a similar idea to LDA or RDA (here the paper uses k-NN covariance matrices). As such, individual learners should be weaker, right? It would be interesting to see the performance of individual classifiers, too.\n\nAlso, there should be more detailed breakdown of the results. What's the impact on parameter k? You set k = 1,2,3,4,5, but what's the best choice? How about combining them together instead of just using a single k? This is an important aspect to understand the benefit of proposed metrics in (3).\n\n3. Are there more competing methods in this kind? I assume most dimensionality reduction methods can also be used here, like random projections or PCA, or just LDA/QDA? Can we also compare with these?", "claims_and_evidence_yn": "No", "claims_explanation": "See comments above.", "audience_yn": "Yes", "audience_explanation": "Bagging and random forest are popular ML tools, so many people will be interested.", "requested_changes": "I would like to see discussions/changes/additional experiments related to my questions and suggestions above.", "broader_impact_concerns": "NA", "additional_comments": "NA", "extra_scores": {}, "extra_text": {}}, {"review_id": "J2MozIul93", "reviewer": "Reviewer_HiVK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "# Summary\nThe paper proposes BOPNN, a new bagging approach based on kNN classifiers. For each bootstrap sample, the method applies an adaptive learning framework using discriminant subspaces. The authors claim that this could increase the diversity of the base learners without reducing their individual performance. Extensive experiments on 162 datasets show that BOPNN performs on average comparably to Random Forests.\n\n＃Strength\n* The experimental evaluation is large-scale and thorough, covering a wide range of benchmark datasets.\n* Results indicate that BOPNN performs on par with Random Forests, which are widely considered strong general-purpose classifiers. This finding is potentially valuable for practitioners.\n\n# Weakness\n* The validity of the core idea itself, the adaptive learning step via discriminant subspaces, is not sufficiently validated. Although the final classification performance has been verified by many benchmark problems, there are no quantitative verification that the proposed method directly solves the problems pointed out in the introduction. In addition to testing the final performance, it would be useful to examine how the proposed procedure affects the base learners. In particular, it should be shown that the procedure does not reduce the accuracy of each weak learner, and how it increases variance across weak learners. Controlled experiments with synthetic data could help to make this clear, and would be valuable for future work.\n* The writing is complex and hard to follow at least for non-natives.  Many sentences are long and contain multiple clauses and modifiers. This structure makes it difficult to follow the argument. Shorter and simpler sentences would improve clarity.", "claims_and_evidence_yn": "No", "claims_explanation": "As noted in the \"Weakness\" section, the paper does not directly test whether the proposed idea actually solves the problems of bagging for kNN that were described in the Introduction. In a method paper, overall performance is important, but it is equally important to provide direct evidence that the key idea itself is effective.", "audience_yn": "Yes", "audience_explanation": "Ensemble learning and kNN are fundamental techniques. New approaches to improve them are likely to attract interest from readers.", "requested_changes": "* Please add a section that directly and quantitatively tests the proposed idea. For example, how does the procedure affect the accuracy of the weak learners? How does it change their variance? Controlled experiments, possibly with synthetic data, would make this clear.\n\n* Please improve the writing style. Avoid long sentences with many clauses, and aim for shorter, simpler, and clearer descriptions.", "broader_impact_concerns": "This work concerns a potential improvement to a basic algorithm. It is necessary to discuss broad impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "fvbHvjz8aD", "reviewer": "Reviewer_oaht", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Summary: \n\nThis paper proposes BOPNN (Bag Of Projected Nearest Neighbors), a novel approach that integrates adaptive discriminant subspaces into bagged kNN classifiers. By projecting data into subspaces that enhance class separation, BOPNN improves the discriminatory power of kNN ensembles while maintaining interpretability. The authors provide extensive experiments on 162 datasets, showing that BOPNN performs comparably to Random Forests and aligns well with SVM performance in certain settings. The framework also allows for visualization of class structure and assessment of variable importance.\n\nStrengths:\n\n- Introduces a computationally feasible method for adaptive kNN within bagging.\n\n- Extensive empirical evaluation on a large and diverse set of datasets.\n\n- Provides interpretable visualizations and insights into variable importance.\n\n- Demonstrates competitive performance with standard baselines (RF, SVM).\n\nWeaknesses:\n\n- No code release; reproducibility may be limited.\n\n- As mentioned in the paper, performance degrades on datasets with high class imbalance or many categorical variables.\n\n- Requires tuning multiple hyperparameters (k, subspace size, number of eigenvectors).\n\n- Visualization aggregates subspaces, which may obscure individual discriminant directions in the ensemble.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper provides convincing empirical evidence through extensive experiments on 162 datasets, including comparisons with multiple baseline methods (RF, SVM, etc.) and detailed visualizations. The claims about BOPNN’s performance relative to other methods are supported by charts, tables, and statistical tests.\n\nHowever, since no code or implementation details are released, the results cannot be independently verified, which slightly weakens the reproducibility aspect.", "audience_yn": "Yes", "audience_explanation": "The paper introduces a novel bagged adaptive kNN approach (BOPNN) that performs comparably to Random Forests and SVMs in many cases, which would be of interest to researchers and practitioners in machine learning, especially those working on ensemble methods and nearest-neighbor models.", "requested_changes": "Critical changes:\n- Code or Reproducibility Materials: Provide code or detailed instructions to reproduce all experiments.\n- Clarification on Limitations: Expand discussion on performance with imbalanced classes and high proportions of categorical variables.\n\nOther suggestions:\n- Parameter Sensitivity & Computational Cost: Include analysis of hyperparameter effects and training/prediction time relative to Random Forests.\n- Additional Visualizations: Show class separation and ensemble projections for datasets with differing performance.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UOGouVF3LV", "reviewer": "Reviewer_yi1y", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In their paper \"Bags of projected nearest neighbours: competitors to random forests?\", the authors suggest a new approach to bagging kNN classifiers. The authors argue that in bagging it is important that models are sufficiently adaptive to the relationship between X and y, and kNN classifier does not satisfy this property, which is why bagged kNN classifiers perform poorly. To remedy that, the authors suggest to use a modified kNN classifier, where neighbors are identified in a low-dimensional subspace identified in a supervised way similarly to LDA. They conductive a massive benchmark using 100+ datasets and show that this approach performs similarly to random forests and outperforms other bagging+kNN strategies. \n\nStrengths: I enjoyed reading the paper. The introduction is very clear, the experiments are comprehensive, the authors do reasonable ablation experiments. The results are strong. Good work.\n\nDisclaimer: I was not familiar with any papers in the related work section or with any other work on bagging kNN classifiers.\n\nWeaknesses: I suggest some clarifications and some additional visualizations/analysis.\n\nOverall, this can definitely be published in TMLR after a minor revision.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Claims are supported by clear comprehensive experiments.", "audience_yn": "Yes", "audience_explanation": "Interesting topic relevant for machine learning community.", "requested_changes": "MAJOR COMMENTS\n\n* Section 3.1: I am not sure how the classifier is working exactly, I feel something is missing from this section. The section explains how to construct a low-dimensional subspace based on parameter $k$. What happens then? You project the entire dataset onto this subspace and perform kNN classification inside that subspace? I.e. the kNN neighbors are identified in the subspace? Is the subspace constructed using only the training data, and both train+test are then projected there? Please spell all of this out in Section 3.1.\n\n* Subspace construction depends on $k$ as a parameter. Then later you are going to use kNN classifier which also has parameter $k$. Why is the same value of $k$ used in these two contexts? Also, kNN classifier uses all neighbors from 1st to kth. But in equation (3) you only use the kth neighbors. Why?\n\n* Could one instead of Equation (3) simply take standard LDA within- and between- class covariances? Without any notion of k? So first project the data onto LDA subspace, then perform kNN classification? Would this be a reasonable strategy for bagging? If not, could you discuss why not?\n\n* Section 4.1: please add some information about the collection of 162 datasets. What is the distribution of sample sizes (min / mean / max), feature dimensionality, number of classes, etc. Maybe add it as a table.\n\n* Compute time: first, please report the total compute time required for all your experiments. Second, discuss runtime of BOPNN vs RF.\n\n* I would suggest to move Appendix A into section 4.2. Currently section 4.2 is unclear without looking into Appendix A, and you don't have space limits in TMLR.\n\n* Section 4.2: BNN is unclear. Also it was not described in Related Work section, why not? \n\n* On the other hand, Related Work described Cannings & Samworth 2017 but you are not comparing against it, why not?\n\n* It could be nice to add scatter plots of accuracy achieved e.g. by BOPNN vs RF across datasets (so 162 points on the scatter plot). Also maybe of BOPNN vs BOpNN or kNN -- that would show that BOPNN is superior. It's just a different way of visualizing these comparisons.\n\n* You used a search over 30 param combinations for BOPNN. Do you have a sense for which are sensible defaults? E.g. k=5, qo = sqrt(p), q = q0/2 or something. Can you discuss that? Can you report the performance of hyperparam-free BOPNN where all these hyperparams are fixed to sensible defaults?\n\n\nMINOR COMMENTS\n\n* I would reformulate the title into a statement: \"Bags of projected nearest neighbours are competitive with random forests\"\n\n* The phrase \"computationally efficient to compute\" appears at least twice and should be reformulated.\n\n* Section 2.2: I would appreciate a bit more detail about Cannings & Samworth 2017 and Gul et al 2018. Can you explain in more detail how they work? These two papers seem to be most relevant for your work.\n\n* Section 4.1: \"number of repetitions\": clarify what is meant by \"repetition\", otherwise readers may be confused and think you are talking about bootstrap repetitions.\n\n* Section 4.3.2: Wilcoxon signed rank test: unclear what exactly was tested. For each given dataset and a pair of algorithms what were you testing exactly?\n\n* Appendix A: kNN classifier, what was the grid for k values?\n\n* Appendix A: I did not understand BNN_inf or BNN. More details needed.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)