wikillm

Paper · 2022-01-29 · stat.ML, cs.LG, stat.AP, stat.ME

Geometry- and Accuracy-Preserving Random Forest Proximities

RF-GAP proximities for random forests: each point's weights come from in-bag points sharing its leaf, scaled by bootstrap counts and averaged over its out-of-bag trees. Proximity-weighted averages then reproduce the forest's out-of-bag predictions, proved for regression and pure-leaf classification. Author-reported: best average imputation rank on 17 UCI datasets.

Random forestRandom forest proximityMissing data imputationAnomaly detectionrandom-forestproximityimputationoutlier-detectionvisualization

arXivPDFCodeMarkdown14 min read

AI-compiled by claude-haiku-5-5 on 2026-11-13, not yet reviewed by a human. Every claim cites its source; check it when a detail matters.

In plain words

Random forests are built from many decision trees, each trained on a random resample of the data. Two data points count as similar when they end up in the same leaf of many trees. These similarity scores, called proximities, are used to find outliers, fill in missing values and draw maps of the data. The usual definitions do not match what the forest actually predicts, so those uses can mislead.

The paper proposes a new definition, called RF-GAP, built so that an average of training labels, weighted by these scores, gives back the forest's own out-of-bag predictions. A point's scores come from training points that shared its leaf, counted by how often each was drawn into that tree's resample. The authors show this is exact for regression, and for classification when the trees are grown until their leaves are pure.

In the authors' tests the new scores give better imputations than the older definitions. For visualisation and outlier detection they judge the pictures more faithful to the forest's errors, but they measure this by eye, not with a score.

TL;DR

RF-GAP is a random-forest proximity matrix whose rows sum to one, and a proximity-weighted average of training labels reproduces the forest's out-of-bag prediction, shown for regression and for pure-leaf classification §IV. Each weight is a leaf share counted with bootstrap multiplicities, averaged over the trees in which the point is out-of-bag §III, Def. 3. Author-reported: the lowest average imputation rank across 17 UCI datasets tab. II, while the visualisation and outlier results are qualitative only §VI.A, §VI.C. The author's Python code follows the paper's weight formula; the lab's R package and the outlier formulas differ from the paper, so check the Paper vs code section before implementing.

Problem

Breiman's proximity counts how often two points share a leaf, treating in-bag and out-of-bag points alike §III, Def. 1. Because trees are grown until pure, in-bag points of different classes never share a leaf, which over-separates the classes in the proximities §III. The out-of-bag variant uses only trees where both points are out of bag, which drops the in-bag points the forest actually predicts from §III, Def. 2. In both cases the proximity-weighted prediction drifts away from the forest's out-of-bag prediction, and imputation, outlier scores and MDS maps built on these proximities inherit the drift §I, §V. The alternative kernels (PBK, RFProxIH) were not designed to explain the forest; the authors use them as similarity measures only §V.

Method

Prose overview. The forest has T trees trained on N points. For each tree the bootstrap sample gives in-bag multiplicities, and out-of-bag points are those with multiplicity zero. The proximity between i and j is built from the trees in which i is out of bag, and from the in-bag points that share i's leaf in each such tree §III.

Notation §III:

  1. B(t) is the bootstrap multiset of tree t; O(t) is its out-of-bag index set.
  2. S_i = \{t : i \in O(t)\} is the set of trees in which i is out of bag; |S_i| is its size.
  3. v_i(t) is the set of training indices that share i's leaf in tree t.
  4. J_i(t) = v_i(t) \cap B(t) are the distinct in-bag points in that leaf; M_i(t) is the same set counted with multiplicity, so |M_i(t)| is the total in-bag count in the leaf.
  5. c_j(t) is the in-bag multiplicity of j in tree t; c_j(t) = 0 if j is out of bag.

Definitions:

p_{Or}(i,j) = \frac{1}{T} \sum_{t=1}^{T} I(j \in v_i(t)) §III, Def. 1

p_{OOB}(i,j) = \frac{\sum_{t \in S_i} I(j \in O(t) \cap v_i(t))}{\sum_{t \in S_i} I(j \in O(t))} §III, Def. 2

p_{GAP}(i,j) = \frac{1}{|S_i|} \sum_{t \in S_i} \frac{c_j(t)\, I(j \in J_i(t))}{|M_i(t)|} §III, Def. 3

Steps of RF-GAP:

  1. For each point i, go through the trees in S_i, where i is out of bag §III, Def. 3.
  2. In each such tree, find the in-bag points in i's leaf and their total count |M_i(t)| §III.
  3. Give each in-bag point j the weight c_j(t) / |M_i(t)| for that tree §III, Def. 3.
  4. Average these weights over the |S_i| trees. Set p_{GAP}(i,i) = 0 §IV, Prop. 1.
  5. The rows are non-negative and sum to one, so no normalisation is needed as weights §IV, Prop. 1.

Prediction identities (the core claims):

\hat{y}_i = \frac{1}{|S_i|} \sum_{t \in S_i} \frac{1}{|M_i(t)|} \sum_{j \in J_i(t)} c_j(t)\, y_j = \sum_{j} p_{GAP}(i,j)\, y_j §IV, Thm. 1. The left side is the forest's out-of-bag regression prediction, which the proof writes as the average over trees of the in-bag mean in each tree's leaf §IV. The paper proves the identity for any training set; the empirical checks agree at every sample size tested app. A.2.

Classification §IV, Thm. 2: the forest's out-of-bag class equals the class with the largest p_{GAP}-weighted vote. The proof needs every leaf to be pure, so that all in-bag points in a leaf share one class.

Similarity use §III, §IV: the diagonal is zero by construction, which suits prediction but not similarity. For similarity, the paper builds the diagonal by passing a duplicate of the observation through the forest with out-of-bag status. For MDS the matrix is symmetrised: (p(i,j) + p(j,i))/2 §III, §VI.A.

Computation pseudocode (the paper gives the definition, not an algorithm; this is a direct reading of §III, Def. 3):

Pseudocode
# RF-GAP proximities  [§III, Def. 3]
# Input:  leaves (N, T) leaf ids; inbag_counts (N, T) multiplicities c_j(t)
# Output: prox (N, N); rows are non-negative and sum to one [§IV, Prop. 1]

def rfgap_proximities(leaves, inbag_counts):
    num_obs, num_trees = leaves.shape                    # (N, T)
    prox = zeros((num_obs, num_obs))
    for i in range(num_obs):
        # Trees where i is out-of-bag: S_i  [§III]
        oob_trees = [t for t in range(num_trees)
                     if inbag_counts[i, t] == 0]
        for t in oob_trees:
            # Points sharing i's leaf in tree t  [§III, v_i(t)]
            in_leaf = leaves[:, t] == leaves[i, t]
            # Total in-bag count in that leaf, with repeats: |M_i(t)|  [§III]
            leaf_mass = sum(inbag_counts[in_leaf, t])
            for j in where(in_leaf):
                # Add c_j(t) / |M_i(t)|, averaged over |S_i|  [§III, Def. 3]
                prox[i, j] += (inbag_counts[j, t] / leaf_mass
                               / len(oob_trees))
    return prox

Imputation §VI.B. The paper fills missing values of one variable at a time:

  1. Initialise the missing cells: the median of the observed values in the same class for a continuous variable, the most frequent value in the same class for a categorical variable. For regression, the paper computes these over all observations §VI.B, step 1.
  2. Train a forest on the filled-in data and build its proximities §VI.B, steps 2–3.
  3. For a continuous variable, replace each missing value with the proximity-weighted sum of the observed values. For a categorical variable, use the proximity-weighted majority vote §VI.B, step 4.
  4. Repeat steps 2–4 as needed; the paper says one iteration often suffices §VI.B, step 5.
Pseudocode
# Random-forest imputation of one variable j  [§VI.B]
# Input:  data (N, d) with NaNs; labels (N,); prox_type
# Output: data with the missing cells of variable j filled

def impute_variable(data, labels, j, prox_type):
    # Initial fill: in-class median or mode  [§VI.B, step 1]
    filled = initialise_in_class(data, labels, j)
    # Train a forest on the filled data and build proximities  [§VI.B, 2-3]
    forest = train_random_forest(filled, labels)
    prox = build_proximities(forest, filled, prox_type)
    observed = not_missing(data[:, j])
    for i in missing_rows(data[:, j]):
        if is_continuous(j):
            # Weighted sum over observed rows, normalised over them  [§VI.B]
            # (the code normalises; the paper does not say so)
            weights = prox[i, observed] / sum(prox[i, observed])
            filled[i, j] = sum(weights * data[observed, j])
        else:
            # Proximity-weighted majority vote  [§VI.B, step 4]
            filled[i, j] = weighted_vote(prox[i, observed],
                                         data[observed, j])
    return filled

Visualisation §VI.A: metric MDS applied to \sqrt{1 - \text{prox}} after symmetrisation, in two dimensions. The text calls this metric MDS (see Paper vs code for the figure files).

Outlier score §VI.C:

  1. For each observation i, compute the raw score as the sum over same-class j of n / \text{prox}^2(i,j) §VI.C, step 1.
  2. Within each class, take the median and the mean absolute deviation of the raw scores §VI.C, step 2.
  3. Centre each raw score on its class median and scale it by that class's mean absolute deviation §VI.C, step 3.
Pseudocode
# Within-class outlier score  [§VI.C]
# Input:  prox (N, N); labels (N,)
# Output: score (N,)

def outlier_scores(prox, labels):
    num_obs = len(labels)
    raw = zeros(num_obs)
    for i in range(num_obs):
        # Same-class points other than i; the paper is silent on
        # the self term, whose proximity is zero under RF-GAP
        others = (labels == labels[i]) & (indices != i)
        # Raw score: sum of n / prox(i, j)^2  [§VI.C, step 1]
        raw[i] = sum(num_obs / prox[i, others] ** 2)
    score = zeros(num_obs)
    for c in unique(labels):
        members = labels == c
        # Median and mean absolute deviation within the class  [§VI.C, 2]
        centre = median(raw[members])
        spread = mean(abs(raw[members] - centre))
        # Centre and scale the raw scores  [§VI.C, step 3]
        score[members] = (raw[members] - centre) / spread
    return score

The pseudocode follows the paper's text. The author code differs in several places; see Paper vs code.

Hyperparameters

NameValueWhereNotes
trees in comparison experiments500 (default)app. A.5"default value of 500 trees" for all other experiments
tree counts swept5, 10, 50, 100, 250app. A.5RF-GAP matches RF in regression at all sizes
minimum node size swept1, 5, 10, 20, 50§IV, fig. 2 app. A.4regression matches are exact at every size
minimum node size in main experimentsnot stated§V"default hyperparameters"; the package and its defaults are not named
mtrynot stated§IIIthe paper names the parameter but gives no value used
train / test split70% / 30%§V24 datasets; each run repeated five times
validation repeats5 runs§V, fig. 3 fig. 4errors averaged over runs; random seeds not stated
imputation missingness5%, 10%, 25%, 50%, 75% MCAR§VI.BMCAR created with the missMethods R package §VI.B
imputation repeats, single iteration100 repetitions§VI.B tab. II app. A.8the same missing cells are used for each proximity type
imputation repeats, multi-iteration curves5 repetitions, 10 iterations§VI.B fig. 6iteration 0 is the median/mode fill
synthetic sample sizes100, 200, 500, 1000, 2000, 5000, 10000app. A.2binary labels, 10 Gaussian features, 20 repeats
symmetry check500 observations, 10 replicatesapp. A.3same synthetic set as above
Sonar out-of-bag error14.9%§VI.A fig. 5used to illustrate MDS
bootstrapassumed§IIIthe paper does not state sampling with replacement or the sample fraction

Results

Author-reported. Setup: 24 datasets from the UCI repository and one Kaggle set (Titanic), 70/30 split, five runs, default hyperparameters §V, app. A.5. For imputation: 17 datasets, MCAR missingness from 5% to 75%, 100 repetitions for the single-iteration table §VI.B. Hardware is not stated.

SettingMetricBaselineThis paperSource
Slope of training vs test error (24 datasets)regression slope, closer to 1 is betterOriginal 2.434; OOB 1.543; PBK 2.287; RFProxIH 2.147RF-GAP 1.040tab. I
Sonar, training: gap between proximity prediction and RF out-of-bag errorabsolute difference (RF out-of-bag error 0.184)Original 0.163; OOB 0.104; PBK 0.156; RFProxIH 0.171RF-GAP 0.004app. A.1
Hill Valley, training: same gap (RF out-of-bag error 0.419)absolute differenceOriginal 0.331; OOB 0.213; PBK 0.298; RFProxIH 0.317RF-GAP 0.001app. A.1
Imputation, average rank across 17 datasets, 5% to 75% missingrank (lower is better)OOB 2.30–2.55; Original 2.35–2.70; RFProxIH 3.20–3.40RF-GAP 1.10–1.65tab. II
Sonar, imputation 5% MCAR, one iterationmean MSE (SE 0.13)Original 3.246; OOB 3.211; RFProxIH 3.264RF-GAP 3.044app. A.8
Hill Valley, imputation 5% MCAR, one iterationmean MSE (SE 0.20)Original 2.052; OOB 1.673; RFProxIH 2.232RF-GAP 1.418app. A.8

Qualitative results: the proximity-weighted predictions with RF-GAP match the forest up to tie-breaks for every sample size tested app. A.2. The symmetry of RF-GAP increases with the number of trees app. A.3. In the MDS and outlier figures, RF-GAP misclassified points sit on cluster borders, while the other proximities show more separation than the forest's error rate justifies §VI.A, fig. 5 app. A.7. Outlier detection is not measured with a score in the paper; the authors list quantifying it as future work §VII.

Paper vs code

The paper names no code. The author's Python repository, jakerhodes/RF-GAP-Python at code_commit, cites this paper in its README and was the primary source here. Also checked: KevinMoonLab/RF-GAP (the co-author's lab; R package), commit a56c25e4211c56e840d6b5666f50a9cccd0af774. Citations in this section marked R/... refer to that R repository; citations marked rfgap/... refer to the Python repository. Searches: the paper and its arXiv metadata for code links; GitHub repository search for "RF-GAP"; the authors' GitHub profile. A third-party port (NicolasHolt/Py-RF-GAP) was excluded. Both primary repositories are GPL-3.0, so this card cites lines and paraphrases only.

  1. Bootstrap multiplicity in the weights. Paper: c_j(t) / |M_i(t)|, with M_i(t) counting repeated in-bag points §III, Def. 3. Python: uses the bootstrap counts and the inverse leaf mass directly rfgap.py. R: builds an in-bag indicator (0 or 1), then gives each distinct in-bag point in the leaf the share 1/k, where k counts distinct points, so repeated draws get one share get_rfgap.R. Inferred from the formulas, not tested: the R version breaks the exact identity when a bootstrap draw repeats a point that shares a leaf. The Python version follows the paper.

  2. Diagonal. Paper: p_{GAP}(i,i) = 0 for prediction, and a duplicate observation is passed through the forest to build a non-zero similarity diagonal §III, §IV. Python: zero by default, with an optional virtual diagonal that the user can switch on rfgap.py rfgap.py. R: no duplicate construction; the diagonal stays zero get_rfgap.R.

  3. MDS variant. Paper: "metric MDS" applied to \sqrt{1 - \text{prox}} §VI.A. R: default mds_type = 'nonmetric', which calls non-metric MDS (isoMDS), with metric MDS as the other option rf_mds.R rf_mds.R. The source file names for the MDS figures all contain non-metric-mds fig. 5. Which variant produced the figures is therefore not settled by the text; the figure filenames suggest non-metric.

  4. Outlier raw score. Paper: sum over same-class j of n / \text{prox}^2(i,j) §VI.C, step 1. R: n divided by the sum of squared same-class proximities, after each row is scaled by its largest absolute value rf_outliers.R helpers.R. Python baseline: n divided by the sum of squared same-class proximities rfgap_baseline.py. The two orders of sum and division give different values, and the row scaling in R changes them further.

  5. Spread and sign. Paper: mean absolute deviation, and step 3 subtracts the median without an absolute value §VI.C, steps 2–3. R: stats::mad, which is a median absolute deviation, and an absolute value of the deviation rf_outliers.R. Python baseline: median of absolute deviations and an absolute value rfgap_baseline.py. The Python baseline also defaults to min-max scaling to [0, 1] rfgap_baseline.py rfgap_baseline.py.

  6. Imputation weights. Paper: the weighted sum uses the RF-GAP weights directly, which already sum to one over all N points §IV, Prop. 1 §VI.B, step 4. R: divides by the sum over observed rows only, so rows with other missing values are renormalised rf_impute.R.

  7. Regression initialisation and the classification switch. Paper: for regression, the initial median or mode is taken over all observations §VI.B, step 1. R: takes the in-class median by matching responses exactly, which for continuous responses selects almost nothing and falls back to the global median rf_impute.R. R also treats a response with 20 or fewer distinct values as a class label rf_impute.R.

  8. Imputation iterations and initialisation defaults. Paper: the table uses one iteration; the curves use ten §VI.B. R: n_iters = 1 by default rf_impute.R. Python: n_iters=10, initialization='median' and global_initialization=False, so the initial fill is in-class by default impute.py.

  9. Bootstrap enforcement. Paper: bootstrap sampling assumed, not stated as a requirement §III. Python: forces bootstrap=True and max_samples=None for OOB and RF-GAP proximities rfgap.py. The R code takes the forest as given.

No other discrepancies found in the proof-to-code correspondence for the prediction identities, beyond items 1 and 2.

Pitfalls

  • Bootstrap multiplicity. The paper's weights count repeated in-bag points; the R package counts distinct points only. Implement the paper's c_j(t) / |M_i(t)|. The Python code does this. Test it with a small forest where one point is drawn twice into the same leaf.
  • Identity needs pure leaves for classification. The classification equivalence §IV, Thm. 2 is proved for pure leaves. With minimum node sizes above 1 the paper reports ties and only near-matches §IV app. A.4.
  • Leaves with no in-bag mass. |M_i(t)| can be zero in a leaf that holds only out-of-bag points. The paper does not address this. The R code skips such trees (its count k is zero, so nothing is added), and the row then sums to less than one. Python behaviour not checked.
  • Bootstrap is required. The identities depend on the in-bag multiset. The Python code enforces bootstrap sampling for these proximities rfgap.py. Subsampling without replacement is not analysed in the paper.
  • Zero diagonal. The matrix from the definition has a zero diagonal, so the outlier sum must skip j = i or it divides by zero. For MDS and any similarity use, decide how to fill the diagonal (the duplicate construction or the Python option) and report it.
  • Asymmetry. Rows sum to one, but the matrix is not symmetric. Symmetrise before MDS §III. The paper shows symmetry improves with more trees app. A.3.
  • Memory and scale. The definition yields a dense N \times N matrix. The paper calls it practical for a few thousand observations and names a sparse version as future work §VII. The Python code defaults to a sparse matrix rfgap.py.
  • Outlier score is not validated numerically. The paper gives plots only and lists quantified evaluation as future work §VII. The formula itself differs between paper and code (items 4–5 above).
  • MDS type. The text says metric MDS; the figure filenames say non-metric; the R default is non-metric (Paper vs code, item 3). Pick one and state it.
  • Imputation iterations. The authors say that for high missingness (about 75%) or small datasets, iterations may not converge and the error can rise §VI.B. The Python default of ten iterations differs from the single iteration in the table.
  • Imputation normalisation. Whether weights are renormalised over observed rows changes the imputed values when other rows are missing (Paper vs code, item 6).
  • Unstated experiment settings. The forest package, the minimum node size, m_{try}, random seeds and hardware are not stated for the experiments §V. The R code uses ranger while the paper cites the R randomForest package §III; the experiments do not say which was used.
  • Evidence is author-reported. Several cells in the appendix tables are NA where a proximity type does not apply to the dataset (for example RFProxIH with categorical features). PBK was omitted from imputation because of its cost §VI.B.
  • Appendix labels are inferred. Appendix letters (A, A.1 to A.8, B) are read from the source's section order and have not been checked against a rendered PDF.

Lineage

  • Builds on: Breiman's random forests and the original proximity §I, §III, Def. 1 (no card); the OOB proximity as implemented in the R randomForest package §III, Def. 2 (no card); Lin and Jeon's view of forests as adaptive nearest-neighbour predictors, which the RF-GAP weights generalise §III (no card).
  • Compared against: PBK, a branch-count kernel for proximities §III, §V (no card); RFProxIH, an instance-hardness dissimilarity from Cao et al. §III, §V (no card).
  • Superseded by: none known from wiki content. The Python README cites a later paper, arXiv:2601.02735, which has no card here.

Source and license

Adapted from “Geometry- and Accuracy-Preserving Random Forest Proximities” by Jake S. Rhodes, Adele Cutler, Kevin R. Moon (arXiv:2201.12682), used under CC BY 4.0. Changes: condensed and restructured for implementation, with tables, equations and algorithms taken from the paper and its code, each cited to its source. Not affiliated with or endorsed by the authors. Code citations refer to https://github.com/jakerhodes/RF-GAP-Python at commit 1b870e54c586 (GPL-3.0). Any quoted code is shown under that license.