Source-linked AI summary
Random Forest Missing Data Algorithms
Fei Tang, Hemant Ishwaran
TL;DR
Existing imputation methods provide limited guidance and can struggle with high-dimensional, mixed, interactive, and nonlinear data. The paper evaluates diverse random-forest imputation algorithms across 60 data sets and missingness mechanisms. RF imputation is generally robust, with accuracy improving as feature correlation increases, while mForest substantially reduces computation relative to missForest.
Problem
Existing missing-data imputation methods can perform poorly in high-dimensional settings and may struggle with mixed data, interactions, and nonlinearity, while RF algorithms lacked comparative evaluation.
Method
The study evaluates proximity, random-splitting, unsupervised, missForest, and mForest random-forest imputation algorithms across 60 diverse data sets and missingness mechanisms.
Results
RF imputation accuracy generally improves with increasing feature correlation, and mForest can achieve up to a 10-fold reduction in compute time relative to missForest.
Takeaways & Limitations
RF imputation is generally robust across missingness settings, while mForest offers a more computationally efficient implementation of missForest.
Takeaways & Limitations
Unsupervised covariance-based splitting becomes unstable in high-dimensional trees with missing features and shrinking node sizes.
Abstract
from arXiv · showhide
Random forest (RF) missing data algorithms are an attractive approach for dealing with missing data. They have the desirable properties of being able to handle mixed types of missing data, they are adaptive to interactions and nonlinearity, and they have the potential to scale to big data settings. Currently there are many different RF imputation algorithms but relatively little guidance about their efficacy, which motivated us to study their performance. Using a large, diverse collection of data sets, performance of various RF algorithms was assessed under different missing data mechanisms. Algorithms included proximity imputation, on the fly imputation, and imputation utilizing multivariate unsupervised and supervised splitting---the latter class representing a generalization of a new promising imputation algorithm called missForest. Performance of algorithms was assessed by ability to impute data accurately. Our findings reveal RF imputation to be generally robust with performance improving with increasing correlation. Performance was good under moderate to high missingness, and even (in certain cases) when data was missing not at random.
1 Introduction
Missing-data imputation is needed because discarding incomplete observations can lose information, while existing methods face difficulties with high-dimensional, mixed-type, interactive, and nonlinear data. The study therefore compares multiple random-forest imputation algorithms across diverse data sets and missingness settings.
- Discarding missing values can lose valuable information and compromise inferential power, making imputation a more practical option for analyses requiring complete data.
- Many existing imputation methods perform poorly in high-dimensional and large-scale settings, where overparameterization and computational difficulties can arise.
- Mixed data, complex interactions, and nonlinear relationships can further challenge conventional imputation methods and implementation.
- Random forests are attractive because they handle mixed data, interactions, and nonlinearity while scaling to high dimensions and providing variable-importance measures.
- The study compares RF missing-data algorithms using 60 diverse data sets, measuring imputation accuracy and computational speed under missing-at-random and not-missing-at-random mechanisms.
- mForest groups variables into multivariate responses, replacing p regressions with approximately 1/α regressions to reduce computational cost.
- The forests use bootstrap samples, variable-type-specific splitting, optional unsupervised or multivariate splitting, and random feature selection.
2 RF approaches to imputation
RF imputation methods use three broad strategies—proximity updates, on-the-fly imputation, and prediction-based approaches—with variants that alter forest splitting. These methods differ in computational design and applicability, including multivariate unsupervised splitting and faster grouped-response prediction.
- General strategies: Three RF imputation strategies preimpute before forest growth and update by proximity, impute during forest growth, or predict each variable’s missing values using forests.These correspond to proximity imputation, OTFI, and missForest, respectively.
- Proximity imputation: Proximity imputation initializes missing values with medians or modal categories, fits a forest, uses its proximity matrix for updating values, and iterates.The proximity matrix records how frequently pairs of cases share terminal nodes; RFprx uses random splitting for computational speed.
- Proximity imputation: Random splitting evaluates only randomly selected split points, making it considerably faster than deterministic splitting; pure random splitting removes data adaptivity and is generally fastest.The pure-random proximity variant is denoted RFprxR, with iterated forms labeled by the number of iterations.
- Limitations and design choices: The proximity approach has biased OOB prediction-error estimates, which also biases measures based on them, and it is awkward to implement on missing test data.OTFI was devised to address these issues.
- On-the-fly imputation: OTFI temporarily draws inbag values only to assign cases to daughter nodes, resets them to missing, and imputes terminal-node values from OOB non-missing data.Integer-valued variables use a maximal class rule, while continuous variables use a mean rule.
- Unsupervised and grouped-response methods: RFunsv performs OTFI with multivariate unsupervised splitting, selecting pseudo-outcomes because it assumes no response variable; mForest accelerates missForest by grouping response variables.Multivariate splitting excludes missing response values, while mForest regresses mutually exclusive variable groups on the remaining variables.
3 Methods
The study evaluates imputation across nine experimental settings using diverse data sets, three missingness mechanisms, and standardized accuracy measures against a strawman benchmark.
- Experimental design: Nine experiments varied the target percentage of missing values and used MCAR, MAR, or NMAR mechanisms.MCAR ignores observed and missing values; MAR may depend on observed values; NMAR depends on both observed and missing values.
- Data sets: Sixty real and synthetic data sets spanned correlation, sample size, variable count, and information level.Information was measured as I = log10(n/p), while correlation was defined from the correlation matrix after removing diagonal and symmetric lower-diagonal contributions.
- Missingness mechanisms: Missingness was induced randomly for MCAR, through another covariate’s tail behavior for MAR, and through each variable’s own tail behavior for NMAR.The NMAR construction makes missingness depend on both observed and missing values, with greater probability in empirical-distribution tails.
- Accuracy assessment: Imputation accuracy used standardized RMSE for nominal variables and misclassification error for categorical variables.The error calculations compare imputed values with artificially missing true values across variables containing more than one induced missing value.
- Accuracy assessment: Relative imputation error compared each procedure with strawman imputation, with values below 100 indicating improvement over the strawman.The standardized RMSE denominator uses the variance of the artificially missing values, while its numerator is the corresponding mean-squared-error difference.
- Experimental settings: RF procedures used randomized splitting, mtry = √p, 500 trees, nodesize = 1, and repeated iterations for selected algorithms.KNN was included because of its speed in the 54,000-run-per-method experiment and its relationship to adaptive nearest-neighbor forests.
4 Results
Results show that correlation is a major determinant of RF imputation accuracy, while performance varies across algorithms, missingness mechanisms, and missing-data levels. Computational speed also differs substantially, with multivariate mForest variants reducing the cost of missForest.
- Imputation accuracy: Correlation was more informative than log-information for predicting relative imputation error across RF procedures.The analysis used a regression of log relative imputation error on standardized correlation, log-information, and RF procedure type.
- Correlation: In high-correlation data, mForest algorithms performed best and sometimes reached a relative imputation error of 50.mRF0.25 also performed well despite using only four regressions per cycle, while RFprxR.5 and RFunsv.5 were other strong performers.
- Missing data mechanism: Accuracy decreased systematically from MCAR to MAR and NMAR, with NMAR performance generally poor unless correlation was high.Except under 75% missingness, all RF procedures under MCAR and MAR outperformed strawman imputation.
- Heavy missingness: Accuracy degraded as missingness increased, but high correlation still allowed RF procedures to halve strawman error with up to 50% missingness.Under NMAR with 75% missingness, procedures were often no better than strawman regardless of correlation.
- Iterating RF algorithms: Iteration generally improved RF accuracy, except that performance sometimes worsened for NMAR data with low or medium correlation.
- Computational speed: KNN was about 1000 times faster than missForest, while mRF0.05 and mRF0.25 improved missForest speed by about a factor of 10.Some non-iterated procedures, such as RFotf, were 100 times faster than missForest and only 10 times slower than KNN.
5 Simulations
Simulations varied sample size in a ten-variable model with specified correlation structure and missingness mechanisms. They recorded relative imputation error over repeated experiments and displayed how error changes with sample size.
- Simulation goals: The simulations tested whether relative imputation error improves with sample size and whether algorithms converge to the same values.
- Simulation model: The simulation model contained 10 variables, including two correlated pairs with correlation coefficient 0.96 and several independent variables.Variables included normally and exponentially distributed features, with independent N(0, 0.5) noise.
- Simulation design: Sample sizes were n = 100, 200, 500, 1000, and 2000, with MCAR, MAR, and NMAR missingness fixed at 25%.Each experiment was repeated 500 times, recording relative imputation error and its standard deviation.
- Simulation results: Figure 6 reports mean relative imputation error ± standard deviation across the five sample sizes.
6 Conclusions
RF imputation performance improved with increasing feature correlation, including under heavy missingness except in the most complex scenarios. For big-data applications, computational speed favors faster alternatives to missForest despite its strong performance in highly correlated settings.
- Imputation performance improved with increasing feature correlation, even under heavy missingness except in the most complex missing-data scenarios.
- MissForest performed best when feature correlation was high, whereas RF algorithms outperformed KNN imputation at low to medium correlation.
- mForest achieved up to a 10-fold reduction in compute time relative to missForest.
- Unsupervised RF imputation procedures were recommended for big data because they delivered solid imputation performance and were 100’s of times faster than missForest.