# The Random Forest Kernel and other kernels for big data from random partitions

arXiv: https://arxiv.org/abs/1402.4293 · HTML: https://mlsanity.com/paper/1402.4293/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2014.

## Built on by (most cited first, 18 of 18)

- [Training Data Influence Analysis and Estimation: A Survey](https://mlsanity.com/paper/2212.04612/) (2022)
- [Geometry- and Accuracy-Preserving Random Forest Proximities](https://mlsanity.com/paper/2201.12682/) (2022)
- [Adapting and Evaluating Influence-Estimation Methods for Gradient-Boosted Decision Trees](https://mlsanity.com/paper/2205.00359/) (2022)
- [Why do Random Forests Work? Understanding Tree Ensembles as Self-Regularizing Adaptive Smoothers](https://mlsanity.com/paper/2402.01502/) (2024)
- [Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces](https://mlsanity.com/paper/2207.00879/) (2022)
- [Instance-Based Uncertainty Estimation for Gradient-Boosted Regression Trees](https://mlsanity.com/paper/2205.11412/) (2022)
- [Towards a Unified Framework for Uncertainty-aware Nonlinear Variable Selection with Theoretical Guarantees](https://mlsanity.com/paper/2204.07293/) (2022)
- [BARK: A Fully Bayesian Tree Kernel for Black-box Optimization](https://mlsanity.com/paper/2503.05574/) (2025)
- [Autoencoding Random Forests](https://mlsanity.com/paper/2505.21441/) (2025)
- [A Scalable Approach to Covariate and Concept Drift Management via Adaptive Data Segmentation](https://mlsanity.com/paper/2411.15616/) (2024)
- [Consistent Interpolating Ensembles via the Manifold-Hilbert Kernel](https://mlsanity.com/paper/2205.09342/) (2022)
- [Revisiting Forest Proximities via Sparse Leaf-Incidence Kernels](https://mlsanity.com/paper/2601.02735/) (2026)
- [A Framework for an Assessment of the Kernel-target Alignment in Tree Ensemble Kernel Learning](https://mlsanity.com/paper/2108.08752/) (2021)
- [Simple Calibration via Geodesic Kernels](https://mlsanity.com/paper/2201.13001/) (2022)
- [Embracing Uncertainty Flexibility: Harnessing a Supervised Tree Kernel to Empower Ensemble Modelling for 2D Echocardiography-Based Prediction of Right Ventricular Volume](https://mlsanity.com/paper/2403.03229/) (2024)
- [Minimax Rates and Spectral Distillation for Tree Ensembles](https://mlsanity.com/paper/2605.11841/) (2026)
- [Kernel of Partition Paths: A Unified Representation for Tree Ensembles](https://mlsanity.com/paper/2606.18853/) (2026)
- [Extreme classification: beating chance with one training example from each class](https://mlsanity.com/paper/2609.20897/) (2026)

## Abstract (arXiv)

We present Random Partition Kernels, a new class of kernels derived by demonstrating a natural connection between random partitions of objects and kernels between those objects. We show how the construction can be used to create kernels from methods that would not normally be viewed as random partitions, such as Random Forest. To demonstrate the potential of this method, we propose two new kernels, the Random Forest Kernel and the Fast Cluster Kernel, and show that these kernels consistently outperform standard kernels on problems involving real-world datasets. Finally, we show how the form of these kernels lend themselves to a natural approximation that is appropriate for certain big data problems, allowing O(N) inference in methods such as Gaussian Processes, Support Vector Machines and Kernel PCA.