The Generalized Proximity Forest
Ben Shaw, Adam Rustad, Sofia Pelagalli Maia, Jake S. Rhodes, Kevin R. Moon · 2025
Read The Generalized Proximity Forest by Ben Shaw, Adam Rustad, Sofia Pelagalli Maia, Jake S. Rhodes, Kevin R. Moon (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-19487.txt.
Introduction
Ben Shaw and four co-authors generalize a trick from random forests: trees that send two cases to the same leaf mark them as close, giving a proximity measure. Such proximities help with outlier hunting, filling missing values, and visualization. Their catch is that they only work as well as the forest behind them, and forests are not ideal everywhere.
A distance-based model called the Proximity Forest had already carried the idea to time series. The generalized version extends it to every setting where supervised distance-based learning applies. It also adds a regression variant. As a meta-learner, it can give imputation skills to any pretrained classifier. Experiments show distinct gains over random forests and nearest neighbors.
Catalog record
| CREATOR | Ben Shaw, Adam Rustad, Sofia Pelagalli Maia, Jake S. Rhodes, Kevin R. Moon |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 29 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-19487
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Generalized Proximity Forest Ben Shaw, Adam Rustad, Sofia Pelagalli Maia, Jake S. Rhodes, Kevin R. Moon Abstract Recent work has demonstrated the utility of Random Forest (RF) proximities for various supervised machine learning tasks, including outlier detection, missing data imputation, and visualization. However, the utility of the RF proximities depends upon the success of the RF model, which itself is not the ideal model in all contexts. RF proximities have recently been extended to time series by means of the distance-based Proximity Forest (PF) model, among others, affording time series analysis with the benefits of RF proximities. In this work, we introduce the generalized PF model, thereby extending RF proximities to all contexts in which supervised distance-based machine learning can occur. Additionally, we introduce a variant of the PF model for regression tasks. We also introduce the notion of using the generalized PF model as a meta-learning framework, extending supervised imputation capability to any pre-trained classifier. We experimentally demonstrate the unique advantages of the generalized PF model compared with both the RF model and the k k -nearest neighbors model. I Introduction Random Forest (RF) proximities have proven useful for many applications, such as applications to financial data analysis, [ 12 ] . However, the utility of RF proximities is limited to cases in which the RF model can be applied–namely, for tabular data. Recently, Geometry- and Accuracy-Preserving (GAP) RF proximities [ 17 ] have been computed for time series models which exhibit a forest structure, such as the Proximity Forest (PF) model [ 13 ] , resulting in supervised outlier detection (of entire time series) [ 20 ] and supervised missing data imputation for time series [ 18 ] . This recent work raises the important question of how to apply GAP proximities in the presence of additional data types, such as graph-valued and/or other cross-sectional data. Pairwise distances can be considered for many types of data beyond tabular data: for example, Dynamic Time Warping (DTW) for time series data [ 22 ] , the Weisfeiler-Lehman distance for graph-valued data [ 5 ] , and STRAMSim for portfolio (cross-sectional) data [ 12 ] . Meanwhile, the PF model is a distance-based model, with splits determined not by features, as is the case with the RF model, but rather by proximity to chosen exemplars based on time series distances [ 13 ] . However, despite the fact that the original model was designed for univariate time series of equal length, the model logic is independent of the distance chosen. In this work, we consider the generalized proximity forest model, which modifies the original PF model in that it allows for the specification of custom distances in order to match the associated data, be it graph-valued, multivariate time series of unequal length, or ordinary tabular data. In so doing, we introduce GAP proximities to data domains not previously considered–any data domain, that is, for which pairwise distances may be considered. In addition to the specification or selection of distances, we also expand the PF model in two novel ways. First, we devise a modified algorithm for the case of regression tasks, as the original PF model accommodates only classification tasks. Second, we devise a model-informed distance, endowing the generalized PF model with the status of a meta-algorithm, used primarily for imputation informed by any pretrained model: that is, we endow any pretrained model with the functionality of an imputer using GAP-based imputation. This paper is organized as follows. In Section II , we provide background information for understanding our paper, including an overview of the PF model ( II-A ), GAP proximities ( II-B ), and GAP-based imputation ( II-C ). We discuss our methods in Section III , which contains an overview of the functionality of the generalized PF model ( III-A ) and a presentation on meta-learning for supervised imputation ( III-B ). Section IV contains our varied experiments, which experiments demonstrate the functionality of the generalized PF model as well as its advantages over existing methods. We then conclude with Section V . The source code, together with scripts for experiments, is available online. 1 1 1 https://github.com/KevinMoonLab/PF-GAP , “manifold” branch for results. II Background In this section, we will present background information for our work. Section II-A contains an overview of the PF model, and Section II-B gives an overview of RF proximities known as RF-GAP. Lastly, Section II-C provides an overview of GAP-based imputation. II-A Proximity Forests The Proximity Forest (PF) model was designed to be a scalable and accurate time series classifier [ 13 ] . One motivation for the PF model was that standard RF model does not generally perform well on raw time series (using values at individual time points as features). This is due to the many ways in which a time series can be trivially perturbed, which perturbations cause the features fed into an RF model to be drastically different than the unperturbed time series [ 10 ] . The PF model is similar to the RF model in that it is an ensemble of trees. In the PF model, the trees are ”proximity trees,” which are summarized as follows [ 13 ] . At each node, the number of branches created corresponds to the number of class labels present in the node. A random data sample, known as an ”exemplar,” is chosen for each class. Subsequently, the remaining data instances travel down the branch according to whichever exemplar they are most similar to, based on a pre-specified notion of distance. This step is repeated r times, where r is a hyperparameter, and the best of the r outcomes is chosen according to a given notion of child node purity such as the Gini purity, which we use. This process is repeated until purity in the child nodes is obtained. The original PF model was designed to accommodate 9 time series distances, which distances are randomly selected at each node or for each tree, according to the user selection [ 13 ] . Our modification of this algorithm gives a user full control over the distances used including the option of a single distance, allowing the PF algorithm to be applied more generally. Although KNN is another distance-based algorithm, one advantage the generalized PF model exhibits is its \mathcal{O}(\log(N)) inference complexity [ 13 ] compared with KNN’s \mathcal{O}(N) complexity, where N is the number of training points. Although there are many acceleration methods for KNN that can reduce this complexity, such as ball [ 16 ] and cover trees [ 2 ] , these methods typically rely on assumptions about the distance measure used, particularly the triangle inequality: we note, however, that the triangle inequality does not hold for many widely-used distance measures, including Dynamic Time warping and the Cosine distance. II-B Geometry- and Accuracy-Preserving (GAP) Proximities The development of a notion of tree-based similarity through random forest models was original work from Leo Breiman in the early 2000’s [ 4 ] . The general idea was to define similarity between two points according to colocation in terminal nodes, which define the decision space of random forests. To explicitly define similarity, the number of terminal nodes in which a pair