wikillm

Concept · 1 paper · updated 2026-11-15

Random forest proximity

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.

random-forestproximityimputationoutlier-detectionvisualization

Markdown5 min read

AI-compiled overview, updated 2026-11-15, not yet reviewed by a human. Every claim cites its source; check it when a detail matters.

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 2201.12682 §I 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 2201.12682 §I 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 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 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" 2201.12682 tab. I.

Out-of-bag proximity

Counts shared leaves only in trees where both points are out of bag 2201.12682 §III. This drops the in-bag points that the forest actually predicts from, so it misses part of the forest's behaviour 2201.12682 §III. It does better than Breiman's proximity in the paper's tests: a regression slope of 1.543 2201.12682 tab. I and an average imputation rank of 2.30 to 2.55 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 2201.12682 §III. The rows are non-negative and sum to one, and the diagonal is zero by construction 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 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 2201.12682 §IV. With larger minimum node sizes the paper reports ties and only near-matches 2201.12682 app. A.4. The empirical checks agree at each sample size tested 2201.12682 app. A.2.

Author-reported results, on 24 datasets with a 70/30 split repeated five times for the regression table 2201.12682 §V: a regression slope of 1.040 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 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 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 2201.12682 §VI.A 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 2201.12682 §V. Neither has a card in this wiki.

When to use which

SituationUseWhy
You need the proximity-weighted prediction to match the forest's own out-of-bag prediction, for regressionRF-GAPOnly RF-GAP has this identity 2201.12682 §IV, Thm. 1
You need the same match for classificationRF-GAP with pure leavesThe identity holds only when every leaf is pure 2201.12682 §IV, Thm. 2
You want exact matching but use a minimum node size above 1Grow trees to node size 1The paper reports only near-matches above that 2201.12682 app. A.4
Imputing missing values with a forestRF-GAP; out-of-bag secondLowest average imputation rank in the paper's tests; out-of-bag ranks second 2201.12682 tab. II
Quick exploratory similarity with no need to match predictionsBreiman's countSimplest of the three, and the paper's baseline; the paper finds it drifts from the forest's predictions 2201.12682 §III 2201.12682 §V
Outlier scores or two-dimensional mapsAny; validate on your own dataThe paper's evidence for these uses is visual, and quantified evaluation is future work 2201.12682 §VI.A 2201.12682 §VII
Very large training setsPlan for a dense matrixRF-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 2201.12682 §VII
Forests built without bootstrap samplingNot covered by the identitiesThe identities are stated for the bootstrap in-bag counts 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 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 2201.12682 §III 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 2201.12682 §III 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 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 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 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 2201.12682 §VI.A 2201.12682 §VII.

Papers

Source and license

Compiled from the papers listed on this page, all published under CC BY, CC BY-SA or CC0, with citations. See each paper's page for its authors and license.