PaperlayerView exact revision on arXiv

Source-linked AI summary

Geometry- and Accuracy-Preserving Random Forest Proximities

Jake S. Rhodes, Adele Cutler, Kevin R. Moon

arXiv:2201.12682v2stat.MLcs.LGstat.APstat.ME

TL;DR

Existing random forest proximities do not accurately reflect the geometry learned by the forest, limiting their interpretability in downstream applications. The paper introduces RF-GAP, whose proximity-weighted predictions exactly reproduce out-of-bag forest predictions, and reports improvements in imputation, outlier detection, and visualization.

  • Problem

    Existing random forest proximity definitions do not match the data geometry learned by the random forest, limiting their interpretability in applications such as visualization and imputation.

  • Method

    RF-GAP defines proximities from in-bag observations sharing terminal nodes with out-of-bag observations, using them as weights for proximity-based prediction.

  • Results

    RF-GAP proximity-weighted regression sums and classification votes exactly match out-of-bag random forest predictions, with empirical improvements over existing definitions across applications.

  • Takeaways & Limitations

    RF-GAP provides a proximity geometry that remains faithful to random forest learning in prediction, imputation, outlier detection, and visualization.

  • Takeaways & Limitations

    The classification proof requires pure terminal nodes; with pruning, RF-GAP may not always match classification predictions, although it remains closer than alternatives.

Abstract

from arXiv · show

Random forests are considered one of the best out-of-the-box classification and regression algorithms due to their high level of predictive performance with relatively little tuning. Pairwise proximities can be computed from a trained random forest and measure the similarity between data points relative to the supervised task. Random forest proximities have been used in many applications including the identification of variable importance, data imputation, outlier detection, and data visualization. However, existing definitions of random forest proximities do not accurately reflect the data geometry learned by the random forest. In this paper, we introduce a novel definition of random forest proximities called Random Forest-Geometry- and Accuracy-Preserving proximities (RF-GAP). We prove that the proximity-weighted sum (regression) or majority vote (classification) using RF-GAP exactly matches the out-of-bag random forest prediction, thus capturing the data geometry learned by the random forest. We empirically show that this improved geometric representation outperforms traditional random forest proximities in tasks such as data imputation and provides outlier detection and visualization results consistent with the learned data geometry.

1 INTRODUCTION

Random forest proximities provide supervised similarity measures used across learning applications, but existing definitions may not preserve the geometry learned by the forest. RF-GAP addresses this by making proximity-weighted predictions exactly match random forest predictions.

  • Random forests: Random forests combine binary decision trees into predictors that handle classification and regression with little tuning across varied data conditions.They support mixed variable types, nonlinear interactions, missing values, and noisy variables.
  • Existing proximities: Random forest proximities encode supervised similarity through the decision-tree partitioning induced by task-specific splits.They have been applied to visualization, outlier detection, data imputation, and other similarity-based methods.
  • Motivation: Existing proximities should recover random forest predictive ability, but proximity-weighted predictions do not match out-of-bag predictions under Breiman’s original definition.This inconsistency limits interpretability and negatively affects visualization and imputation.
  • RF-GAP contribution: RF-GAP defines proximities so proximity-weighted predictions exactly match random forest predictions for both regression and classification.For out-of-bag observations, proximities are computed using in-bag observations from the same tree-generating samples.
  • RF-GAP contribution: RF-GAP preserves the random forest’s learned geometry and empirically outperforms existing proximity definitions in visualization, imputation, and outlier detection.The method is designed to match the forest’s predictions while retaining a common schema for classification and regression.

2 RANDOM FOREST PROXIMITY APPLICATIONS

Random forest proximities support supervised visualization, outlier detection, imputation, variable-importance analysis, and multi-view learning. Because existing definitions do not match learned forest geometry, RF-GAP is proposed as a more faithful replacement for these applications.

  • Visualization: Random forest proximities have supported visualization through dimensionality reduction and clustering, including classical and metric MDS.The cited approaches used existing proximity definitions that may not represent the forest’s learned geometry accurately.
  • Other applications: Existing proximity methods have also been used for supervised outlier detection, data imputation, variable-importance assessment, and multi-modal or multi-view problems.Applications include within-class proximity scores, proximity-weighted replacement of missing values, and combined proximity matrices.
  • Motivation: Existing applications generally rely on proximity definitions that do not match the data geometry learned by the random forest.This mismatch motivates replacing them with RF-GAP proximities.
  • RF-GAP applications: RF-GAP is reported to improve data visualization, outlier scores, and random forest imputations by more accurately reflecting learned geometry.The paper presents these improvements experimentally relative to existing definitions.

3 RANDOM FOREST PROXIMITIES

Random forest proximities derive supervised similarity from observations sharing terminal nodes, but standard definitions can distort the geometry learned by the forest. RF-GAP incorporates bootstrap status and in-bag multiplicities so proximity-weighted predictions reproduce the forest’s OOB predictions.

  • Random forest structure: Random forests train recursively partitioned trees on bootstrap samples, selecting feature subsets for splits that optimize purity or residual error.In-bag observations are sampled with replacement; OOB observations are those excluded from a tree’s bootstrap sample.
  • Existing proximities: The original proximity is the proportion of trees in which two observations occupy the same terminal node, regardless of bootstrap status.For observation i, v_i(t) contains observations sharing its terminal node, and the indicator records whether j belongs to that set.
  • Existing proximities: Because original proximities weight in-bag and OOB observations equally, they overstate class separation and can overfit training data in proximity-weighted prediction.Trees grown to purity place in-bag observations from different classes in different nodes, producing exaggerated separation.
  • Existing proximities: OOB proximities avoid in-bag observations but generally fail to characterize random forest predictions because they omit training labels and terminal-node multiplicities.Their proximity-weighted predictors generally have higher error rates than the forest’s OOB error rate.
  • RF-GAP: RF-GAP weights in-bag observations by their bootstrap multiplicities within shared terminal nodes, preserving the geometry learned by the forest.The definition uses the in-bag set J_i(t), the multiset M_i(t), and multiplicity c_j(t) across trees where the observation is OOB.
  • RF-GAP: RF-GAP proximity-weighted sums for regression and majority votes for classification reproduce the random forest’s OOB predictions for all sample sizes, including test points.This makes the forest’s prediction function recoverable from the proximities and keeps applications aligned with the derived forest.

4 RANDOM FORESTS AS PROXIMITY-WEIGHTED PREDICTORS

RF-GAP proximities reconstruct random forest out-of-bag predictions as weighted sums for regression and weighted-majority votes for classification. Their nonnegative, sum-to-one weights directly preserve the forest’s learned geometry, with classification equivalence requiring pure terminal nodes.

  • Proximity properties: RF-GAP proximities are nonnegative and sum to one, so they can directly serve as classification or regression weights.Other proximity definitions require row normalization before use as weights.
  • Proximity properties: Setting pGAP(i, i) = 0 prevents an observation from contributing its own label to proximity-weighted prediction.For similarity applications, diagonal entries can instead be constructed using an identical duplicate assigned out-of-bag status.
  • Regression: RF-GAP proximity-weighted sums exactly reconstruct random forest out-of-bag regression predictions.The result follows from using RF-GAP proximities as weights over in-bag observations sharing terminal nodes.
  • Classification: RF-GAP weighted-majority votes reconstruct random forest out-of-bag classification predictions.The theorem applies to classification labels using RF-GAP proximities as voting weights.
  • Classification: Classification equivalence formally requires trees with pure terminal nodes, whereas regression predictions match regardless of node size.With pruned classification trees, RF-GAP remains closer to random forest predictions, but differences increase as node size grows because ties become more likely.

5 EXPERIMENTAL VALIDATION OF PROXIMITY-WEIGHED PREDICTION

Across 24 datasets, RF-GAP proximity-weighted predictions most closely reproduce random forest predictions, while several traditional proximities overfit training data. RF-GAP also generally yields the lowest test errors and remains the closest match across forest sizes.

  • Node-size robustness: For regression, RF-GAP predictions perfectly match random forest predictions regardless of node size.For classification, RF-GAP differences increase with node size but remain smaller than those of the other proximities.
  • Prediction agreement: Across 24 datasets, RF-GAP proximity-weighted error rates nearly exactly match random forest out-of-bag error rates.Small discrepancies are attributed to random tie-breaking.
  • Prediction agreement: RF-GAP generally produces the lowest test errors among the compared proximity definitions.Figure 3 compares training and test errors, while Figure 4 shows close agreement with random forest predictions on both splits.
  • Overfitting comparison: The original proximities, PBK, and RFProxIH typically overfit training data, producing lower training errors than the random forest.Their larger regression slopes and points above y = x indicate training-data overfitting.
  • Forest-size robustness: RF-GAP predictions remain the most accurate match to random forest predictions when forests contain fewer trees.The comparison included forests with 5, 10, 50, 100, and 250 trees.
  • Comparison across proximities: RF-GAP predictions differ most from other proximity-weighted predictions, especially on training data.This follows from defining RF-GAP to match random forest out-of-bag predictions rather than the alternative proximity objectives.

6 COMPARISON OF COMMON PROXIMITY-BASED APPLICATIONS

The paper evaluates RF-GAP across visualization, imputation, and outlier detection, finding that it better represents random-forest geometry and generally improves application performance.

  • Visualization using Multi-Dimensional Scaling: RF-GAP MDS embeddings better reflect the Sonar forest’s 14.9% OOB error by placing misclassified observations near class boundaries or within opposing clusters.Other proximities overstate class separation and can appear nearly linearly separable.
  • Data imputation: The imputation experiments removed 5%, 10%, 25%, 50%, and 75% of values at random and compared single-iteration and iterative mean MSE.Single-iteration results averaged 100 repetitions; iterative results averaged 5 repetitions at each of 10 iterations.
  • Data imputation: RF-GAP achieved the best imputation rankings across all compared proximity definitions and percentages of missing values.The comparison used RF-GAP, OOB, original, and RFProxIH proximities across UCI datasets.
  • Data imputation: Across 17 datasets, RF-GAP generally outperformed other proximity definitions at each iteration, though convergence was not guaranteed with at least 75% missingness or small datasets.The experiments recorded mean MSE and standard errors over 10 iterations.
  • Outlier detection: RF-GAP outlier visualizations assign higher scores to points outside their class clusters and identify visually unusual MNIST observations.In the cancer dataset, point sizes were scaled proportionally to the outlier measure.

7 CONCLUSION

The conclusion presents RF-GAP as a geometry-preserving proximity definition whose weighted-nearest-neighbor predictions match random-forest out-of-bag results and improve several applications.

  • Conclusion: RF-GAP characterizes random-forest out-of-bag predictions using a weighted nearest-neighbor predictor and exactly matches those predictions.The paper reports both a proof and empirical demonstration of this relationship.
  • Conclusion: RF-GAP captures random-forest-learned data geometry and improves proximity-weighted prediction, missing-data imputation, outlier detection, and visualization relative to existing definitions.These improvements are reported empirically across the listed applications.
  • Conclusion: Future work includes quantifying outlier-detection performance, comparisons with non-tree-based methods, variable-importance assessment, and multi-view learning.The paper also identifies visualization and manifold-alignment applications for future exploration.
  • Conclusion: RF-GAP is currently useful for datasets with a few thousand observations, motivating sparse implementations for larger datasets.The authors identify scalability as an additional area of improvement.

APPENDIX A ADDITIONAL EXPERIMENTAL RESULTS

The appendix introduces additional experimental results using RF-GAP.

  • Additional experimental results: The appendix presents additional experimental results using RF-GAP.

A.1 Empirical Validation of Theorems 1 and 2

Additional experiments validate that RF-GAP proximity-weighted predictions reproduce random-forest results, including out-of-bag comparisons.

  • Empirical validation: RF-GAP error rates match those of the random forest in the additional experimental results.
  • Empirical validation: Across regression and classification experiments, RF-GAP proximity predictions nearly perfectly match random-forest predictions.The table reports random-forest MSE or error rates alongside prediction differences or mismatch proportions.
  • Empirical validation: Using the training set, RF-GAP predictions most reliably match the random forest’s out-of-bag predictions among the compared proximity definitions.

A.2 Proximity-Weighted Predictions and Sample Size

Across sample sizes and forest sizes, RF-GAP proximity-weighted predictions match random forest predictions, with exact matches for regression and only tie-break differences for classification. Other proximity definitions show less consistent agreement and can diverge in their training and test behavior.

  • Sample size: RF-GAP predictions match random forest predictions up to tie breaks regardless of sample size.Original and OOB proximity matches improve with sample size but do not converge to exact agreement.
  • Sample size: Original and OOB proximities match random forest predictions differently on test and OOB training predictions as sample size increases.Original proximities better approximate test predictions, whereas OOB proximities better match OOB predictions.
  • Minimum node size: Both random forest and proximity-weighted training errors tend to increase as minimum node size increases.The comparison covers minimum node sizes 1, 5, 10, 20, and 50.
  • Number of trees: Regression matches are exact across forest sizes, while classification matches decrease with fewer trees because tie-breaking becomes more frequent.The comparison uses forests with 5, 10, 50, 100, 250, and 500 trees across 24 datasets.
  • Agreement across proximities: RF-GAP differs most from other proximities in agreement comparisons, especially for training predictions.Original, OOB, and PBK have the highest agreement for test predictions, while training predictions show larger discrepancies.
  • MDS and outlier structure: RF-GAP embeddings place random forest misclassified points near class-cluster borders, while other proximities can exaggerate class separation.The border pattern is reported for the Ionosphere data and is consistent with RF-GAP’s geometry-focused representation.

A.8 Data Imputation

RF-GAP generally improves random-forest-proximity imputation across datasets and missingness settings, but performance becomes noisier for smaller datasets and less reliable when 75% of values are missing. The appendix also reports related visualization and outlier-detection examples.

  • Experimental design: The extended imputation study removes 5%, 10%, 25%, 50%, or 75% of values completely at random and records average MSE with standard deviations.The results cover 100 trials across 17 UCI datasets using four proximity measures.
  • Visualization and outliers: RF-GAP and OOB MDS embeddings can show looser clusters, border misclassifications, and outlier structure that differ from other proximity definitions.Additional examples include Ionosphere, Parkinson’s, E. coli, Iris, Seeds, and Wine datasets.
  • Experimental scope: Some imputation comparisons exclude PBK because of computational inefficiency and exclude RFProxIH for datasets with continuous responses or categorical features.Datasets already containing missing values and larger datasets were also excluded in the extended study.
  • Single-iteration imputation: RF-GAP has almost universally lower imputation MSE than the other evaluated proximity definitions.When it does not win, RF-GAP usually ranks second; it outperforms every other definition on several named datasets.
  • Multiple-iteration imputation: RF-GAP generally outperforms other proximity-weighted imputations across ten iterations.Imputation is noisier for smaller datasets and less reliable for large missing-value percentages, especially 75%.

APPENDIX B DATASET DESCRIPTIONS

The experiments primarily use datasets from the UCI repository, with dataset dimensions reported after removing observations with missing values and uniquely identifying variables.

  • Dataset sources: Most datasets used in the paper come directly from the UCI repository.A full dataset list is provided in Table B.1.
  • Dataset preprocessing: Table B.1 reports observation counts after removing rows with missing values and column counts after removing uniquely identifying variables.The table describes the datasets used in the experiments.
Loading 2201.12682v2…