---
kind: concept
slug: random-forest-proximity
title: Random forest proximity
summary: >-
  Similarity between training points, counted from shared leaves in a random forest. Three definitions differ in which trees and which in-bag points they use. Only RF-GAP makes a proximity-weighted average equal the forest's out-of-bag prediction, shown for regression and pure-leaf classification. Imputation gains are author-reported; outlier and map uses are unverified.
tags: [random-forest, proximity, imputation, outlier-detection, visualization]
papers: ["2201.12682"]
related: [random-forest, missing-data-imputation, anomaly-detection, bagging]
status: draft
updated_at: 2026-11-15
---

## Overview

In a random forest, two training points are similar when they land in the same
leaf of many trees. Counting these shared leaves gives a proximity matrix,
which is then used for imputation, outlier scores and two-dimensional maps
[arxiv:2201.12682 §I] [arxiv:2201.12682 §III]. The paper's main complaint is
that the common definitions do not match what the forest itself predicts, so
every use built on them inherits the mismatch [arxiv:2201.12682 §I]
[arxiv:2201.12682 §III].

The variants differ in two choices: which trees count for a pair of points,
and how the in-bag points inside a shared leaf are weighted. Each choice gives
a different matrix, so numbers from one definition do not carry over to
another.

## Variants

### Breiman's proximity

The count of trees in which two points share a leaf, using every tree and
treating in-bag and out-of-bag points alike [arxiv:2201.12682 §III]. The paper
argues that trees grown until their leaves are pure keep in-bag points of
different classes apart, which over-separates the classes in this matrix
[arxiv:2201.12682 §III]. Its proximity-weighted predictions drift from the
forest's out-of-bag predictions. In the paper's regression-slope table it
scores 2.434, where 1 is the target, in the row labelled "Original"
[arxiv:2201.12682 tab. I].

### Out-of-bag proximity

Counts shared leaves only in trees where both points are out of bag
[arxiv:2201.12682 §III]. This drops the in-bag points that the forest actually
predicts from, so it misses part of the forest's behaviour
[arxiv:2201.12682 §III]. It does better than Breiman's proximity in the paper's
tests: a regression slope of 1.543 [arxiv:2201.12682 tab. I] and an average
imputation rank of 2.30 to 2.55 [arxiv:2201.12682 tab. II].

### RF-GAP

Each point's weights come from the trees in which that point is out of bag.
In each such tree, every in-bag point in its leaf gets its bootstrap count
divided by the leaf's total in-bag count, and the weights are averaged over
those trees [arxiv:2201.12682 §III]. The rows are non-negative and sum to one,
and the diagonal is zero by construction [arxiv:2201.12682 §IV].

The central identity: a proximity-weighted average of training labels equals
the forest's out-of-bag prediction for regression, for any training set
[arxiv:2201.12682 §IV]. For classification, the out-of-bag class equals the
class with the largest weighted vote, but only when every leaf is pure
[arxiv:2201.12682 §IV]. With larger minimum node sizes the paper reports ties
and only near-matches [arxiv:2201.12682 app. A.4]. The empirical checks agree
at each sample size tested [arxiv:2201.12682 app. A.2].

Author-reported results, on 24 datasets with a 70/30 split repeated five times
for the regression table [arxiv:2201.12682 §V]: a regression slope of 1.040
[arxiv:2201.12682 tab. I]. For imputation on 17 UCI datasets with 5% to 75%
missing values, an average rank of 1.10 to 1.65, the best of the variants
tested [arxiv:2201.12682 tab. II]. For one iteration at 5% missing, the mean
squared error on Sonar is 3.044 against 3.211 for out-of-bag and 3.246 for
Breiman's, with a standard error of 0.13. On Hill Valley it is 1.418 against
1.673 and 2.052, with a standard error of 0.20 [arxiv:2201.12682 app. A.8].
The Sonar gap is small next to its standard error.

The paper's visual results for maps and outliers are qualitative. It says
RF-GAP's misclassified points sit on cluster borders, and it lists a
quantified evaluation of outlier detection as future work
[arxiv:2201.12682 §VI.A] [arxiv:2201.12682 §VII].

The other two kernels in the comparison, PBK and RFProxIH, were not built to
explain forest predictions and are used only as similarity measures
[arxiv:2201.12682 §V]. Neither has a card in this wiki.

## When to use which

| Situation | Use | Why |
|---|---|---|
| You need the proximity-weighted prediction to match the forest's own out-of-bag prediction, for regression | RF-GAP | Only RF-GAP has this identity [arxiv:2201.12682 §IV, Thm. 1] |
| You need the same match for classification | RF-GAP with pure leaves | The identity holds only when every leaf is pure [arxiv:2201.12682 §IV, Thm. 2] |
| You want exact matching but use a minimum node size above 1 | Grow trees to node size 1 | The paper reports only near-matches above that [arxiv:2201.12682 app. A.4] |
| Imputing missing values with a forest | RF-GAP; out-of-bag second | Lowest average imputation rank in the paper's tests; out-of-bag ranks second [arxiv:2201.12682 tab. II] |
| Quick exploratory similarity with no need to match predictions | Breiman's count | Simplest of the three, and the paper's baseline; the paper finds it drifts from the forest's predictions [arxiv:2201.12682 §III] [arxiv:2201.12682 §V] |
| Outlier scores or two-dimensional maps | Any; validate on your own data | The paper's evidence for these uses is visual, and quantified evaluation is future work [arxiv:2201.12682 §VI.A] [arxiv:2201.12682 §VII] |
| Very large training sets | Plan for a dense matrix | RF-GAP gives a dense N by N matrix; the paper calls it practical for a few thousand observations and names a sparse version as future work [arxiv:2201.12682 §VII] |
| Forests built without bootstrap sampling | Not covered by the identities | The identities are stated for the bootstrap in-bag counts [arxiv:2201.12682 §III]; the paper does not analyse other sampling schemes |

## Implementation sketch

The core of RF-GAP, in Python-flavoured pseudocode. Each step's citation is
on the line above it.

```pseudocode
# leaf:  (N, T) leaf id of each training point in each tree
# count: (N, T) bootstrap count of each point in each tree, 0 if out-of-bag
def rfgap(leaf, count):
    n, num_trees = leaf.shape
    prox = zeros((n, n))
    for i in range(n):
        # Trees in which point i is out-of-bag [arxiv:2201.12682 §III]
        oob = [t for t in range(num_trees) if count[i, t] == 0]
        for t in oob:
            # Points sharing i's leaf in tree t [arxiv:2201.12682 §III]
            same = leaf[:, t] == leaf[i, t]
            # Leaf's in-bag total, counting repeats [arxiv:2201.12682 §III]
            mass = count[same, t].sum()
            if mass == 0:
                continue  # case not addressed in the paper
            # Count / mass, averaged over the out-of-bag trees
            # [arxiv:2201.12682 §III]
            prox[i, same] += count[same, t] / (mass * len(oob))
    return prox
```

Where the variants and the paper's uses differ:

- **Repeats.** Bootstrap draws that repeat a point count each time in the leaf
  total and in that point's weight [arxiv:2201.12682 §III]. Checking this with
  a small forest in which one point is drawn twice is a useful test.
- **Diagonal.** The definition gives zero. For similarity uses, the paper fills
  the diagonal by passing a duplicate of the observation through the forest
  with out-of-bag status [arxiv:2201.12682 §III] [arxiv:2201.12682 §IV].
- **Symmetry.** Rows sum to one but the matrix is not symmetric. The paper
  symmetrises it, as (p(i,j) + p(j,i)) / 2, before the two-dimensional map
  [arxiv:2201.12682 §III] [arxiv:2201.12682 §VI.A].
- **Imputation.** Start from the in-class median or mode, train a forest,
  build RF-GAP, then fill each missing cell from the weighted observed values.
  The paper says one iteration often suffices [arxiv:2201.12682 §VI.B].
- **Outlier score.** For each point, sum the same-class proximities as
  n / prox² over the other points of its class. Then centre each score on its
  class median and scale it by the class mean absolute deviation
  [arxiv:2201.12682 §VI.C]. Leave the diagonal out of this sum.
- **Published code.** The paper's card records differences between the
  published implementations and the paper's text. Check the Paper vs code
  section of [its card](/papers/2201.12682) before copying any formula.

## Contradictions

None known. The wiki has one source for this concept, so the paper's numbers
have no independent check here. Its outlier and map results rest on visual
judgement, not on a score [arxiv:2201.12682 §VI.A] [arxiv:2201.12682 §VII].

## Papers

- [Geometry- and Accuracy-Preserving Random Forest Proximities](/papers/2201.12682): defines RF-GAP, whose weighted averages reproduce the forest's out-of-bag predictions, and compares it with Breiman's and out-of-bag proximities on regression, imputation and visual tasks.
