How do we measure whether two data points are truly alike? In low-dimensional, continuous spaces, standard geometric metrics like Euclidean distance work perfectly well. However, when data scales to thousands of dimensions, or mixes continuous numbers with categorical tags, geometric metrics break down. Due to the curse of dimensionality, points in high-dimensional spaces tend to become equidistant from one another, and irrelevant, noisy features easily drown out the true signal.
To solve this, a powerful paradigm shift repurposes tree ensembles—such as Random Forests and Gradient Boosted Trees—not as predictive black boxes, but as adaptive, task-driven similarity kernels. Instead of calculating distances in the raw feature space, we pass data points through a trained forest and measure how frequently they land in the exact same leaf nodes. This approach, known as leaf-node co-occurrence similarity, transforms tree structures into highly localized, context-aware distance metrics.
The Core Mechanism: Leaf Co-Occurrence
To understand why this works, consider how a single decision tree operates. A tree recursively splits the feature space into axis-aligned boxes (leaf nodes) to maximize information gain relative to a target variable. If two distinct data points land in the same leaf node, the tree's learned logic has deemed them indistinguishable for the task at hand.
By averaging this behavior across an entire ensemble of trees, we obtain a continuous similarity metric. Formally, given two data points $x$ and $x'$, and an ensemble of $T$ trees, the similarity kernel $K(x, x')$ is defined as the fraction of trees in which both points share a terminal leaf node:
$$K(x, x') = \frac{1}{T} \sum_{t=1}^T \mathbb{I}\big(L_t(x) = L_t(x')\big)$$
where $L_t(x)$ represents the leaf index of point $x$ in tree $t$, and $\mathbb{I}$ is the indicator function.
As highlighted by Dimitris Bertsimas et al. in From Predictive to Prescriptive Analytics, this formulation reveals that tree ensemble predictions are fundamentally weighted linear combinations of historical training labels. Rather than just outputting a static prediction, the forest acts as an exemplar-based weighting function.
This metric possesses three remarkable properties that standard geometric distances lack:
- Implicit Feature Selection: If a feature is irrelevant noise, the trees will rarely split on it. Consequently, noisy features do not distort the similarity score.
- Local Adaptivity: In regions of the feature space where the target function changes rapidly, trees make frequent, narrow splits, creating a highly localized neighborhood. Where the function is flat, the neighborhoods naturally expand.
- Native Mixed-Type Support: Because trees handle categorical, continuous, and hierarchical data natively, the derived kernel computes distances across heterogeneous data types without requiring arbitrary scaling or embedding steps.
Smoothing the "Blocky" Predictions of Forests
Standard random forests are fundamentally "blocky." Because they predict by taking a simple average of training observations within a single leaf, their output surface resembles a jagged step function. Repurposing the forest as an adaptive kernel allows researchers to smooth out these predictions.
Instead of computing a simple average within the final leaf, the leaf co-occurrence weights can inform a localized parametric model. Rina Friedberg et al. introduced this concept with Local Linear Forests. By using the forest-derived weights to fit a local linear regression rather than a local constant, they combined the high-dimensional adaptability of random forests with the local smoothness of kernel methods, drastically reducing bias near data boundaries.
Standard Forest: [Leaf Average] ──> Jagged Step Function
Kernel Forest: [Co-occurrence Weights] ──> Local Linear Regression ──> Smooth Curve
This smoothing capability is equally potent in non-parametric statistical estimation. For instance, Alexander Hanbo Li et al. developed the Censored Quantile Regression Forest to handle complex, censored survival data by treating the forest as an adaptive kernel method. In a similar vein, George H. Chen demonstrated in Nearest Neighbor and Kernel Survival Analysis: Nonasymptotic Error Bounds and Strong Consistency Rates that using random survival forests to define data-driven proximity metrics yields robust, consistent estimators that routinely outperform classical survival models.
Opening the Black Box via Example-Based Explanations
If a forest's prediction for a new query point is merely a weighted average of the training data, we can interpret the model by identifying exactly which training points are receiving the most weight. This realization has led to powerful frameworks for interpretability and uncertainty estimation.
In Model Agnostic Supervised Local Explanations, Gregory Plumb et al. introduced MAPLE, a framework that uses leaf co-occurrence to define a "supervised neighborhood." By fitting a transparent local linear model over this neighborhood, MAPLE generates highly faithful local explanations capable of detecting complex global patterns like discontinuities.
Furthermore, Henrik Boström demonstrated in Example-Based Explanations of Random Forest Predictions that these proximity weights can be drastically pruned. By retaining only the top 10 or 20 most influential training examples, the model provides concise, human-readable "evidence" for its decisions without sacrificing predictive accuracy. This exact intuition was applied practically by Wei Ma et al. in An Interpretable Produce Price Forecasting System for Small and Marginal Farmers in India using Collaborative Filtering and Adaptive Nearest Neighbors, where forest-derived nearest neighbors were used to provide farmers with historical precedents to justify price forecasts.
Beyond explanations, knowing which training points are structurally close to a query point allows for robust uncertainty estimation. Jonathan Brophy et al. developed IBUG in Instance-Based Uncertainty Estimation for Gradient-Boosted Regression Trees. IBUG uses the leaf-membership affinity of a gradient-boosted ensemble as a distance metric to extract the $k$-nearest training examples, using the variance among those neighbors to supply state-of-the-art probabilistic uncertainty intervals.
Conquering High-Dimensional and Mixed-Variable Spaces
The robustness of forest-based kernels makes them highly effective in domains where traditional distance metrics fail entirely, such as high-dimensional, low-sample-size (HDLSS) problems, mixed-variable optimization, and unstructured data clustering.
High-Dimensional, Low-Sample-Size Data
In fields like radiomics and genomics, datasets often contain thousands of features but only a handful of patient samples. Hongliu Cao et al. showed in Dynamic voting in multi-view learning for radiomics applications that tree-based dissimilarity measures provide far more reliable neighborhood definitions for local adaptation in medical imaging than standard geometric metrics.
To exploit this mathematically, Lucca Portes Cavalheiro et al. developed a hybrid approach in Random forest kernel for high-dimension low sample size classification, extracting the similarity matrix from a random forest and feeding it directly into a Support Vector Machine (SVM) as a custom kernel. This scales effectively even to massive genomic studies, as seen in the distributed MapReduce architecture proposed in Random forests on Hadoop for genome-wide association studies of multivariate neuroimaging phenotypes.
Mixed-Variable Optimization
Bayesian optimization typically relies on Gaussian Processes (GPs), which struggle when the search space contains a mix of continuous parameters and discrete categorical choices. Alexander Thebelt et al. resolved this in Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces by using tree ensemble leaf co-occurrence as the core kernel for a GP. This allows the GP to model complex, constrained, mixed-variable spaces naturally. A similar strategy is utilized in Mixed-Variable Black-Box Optimisation Using Value Proposal Trees, where randomized tree structures map distances across intricate discrete-continuous spaces to avoid local optima.
Downstream Clustering and Hashing
The applications of forest kernels extend across a wide variety of unstructured and sparse data domains:
- Causal Inference: Trevor Hastie et al. utilize tree-based proximity scoring in Assessment of Heterogeneous Treatment Effect Estimation Accuracy via Matching to match similar control and treatment units in high-dimensional covariate spaces.
- Algorithm Selection: Kevin Leyton-Brown et al. leverage the internal geometry of forests in OASC-2017: *Zilla Submission to perform nearest-neighbor searches for dynamic algorithm scheduling.
- Multimodal Clustering: In Video Semantic Clustering with Sparse and Incomplete Tags, Jingya Wang et al. combine visual features and sparse text tags within a random forest, using the resulting affinity matrix for spectral clustering. Similarly, Concetto Spampinato et al. apply forest co-occurrence in PeRCeiVe Lab@UNICT at MediaEval 2014 Diverse Images: Random Forests for Diversity-based Clustering to capture non-linear image relationships for diversity-based filtering.
- Cybersecurity Hashing: In EMBERSim: A Large-Scale Databank for Boosting Similarity Search in Malware Analysis, Dragos-Georgian Corlatescu et al. repurpose the leaf indices of gradient-boosted trees as a fast similarity hash, enabling rapid, large-scale malware variant detection without requiring heavy embedding models.
By shifting our perspective from what tree ensembles predict to how they partition, leaf-node co-occurrence similarity unlocks a rich, task-aware metric space. It bridges the gap between the robust, non-linear feature selection of tree models and the smooth, interpretable elegance of kernel methods.
Key Foundational Work
A Discriminative Distance Learning-Based CBIR Framework for Characterization of Indeterminate Liver Lesions (2011) — contributed 2 concept elements to this direction.
Neighbourhood Approximation Forests (2012) — contributed 1 concept elements to this direction.