Imputation with Random Forests I have two questions on using random forest (specifically randomForest in R) for missing value imputation (in the predictor space). 
1) How does the imputation algorithm work - specifically how and why is the class label required for imputation? is the proximity matrix which serves to weight the average value to impute a missing value defined separately by class?
2) If the class label is needed to impute missing values - how can this be used to impute missing values for new data that you are trying to predict?
 A: I have tried using Random Forest for multiple imputation in MICE to handle missing data in survival analysis. I used bootstrapping to account for sampling variability in the imputation models. I found that Random Forest MICE performed better than parametric MICE when there were interactions between predictor variables that were not included in the imputation model.
The CALIBERrfimpute package provides a function for Random Forest imputation in MICE:
http://cran.r-project.org/web/packages/CALIBERrfimpute/index.html
This is an article describing tests of the method on simulated data and a real epidemiological dataset:
http://dx.doi.org/10.1093/aje/kwt312
A: The basic idea is to do a quick replacement of missing data and then iteratively improve the missing imputation using proximity.  To work with unlabeled data, just replicate the data with all labels, and then treat it as labeled data.
The fraction of trees for which a pair of observations share a terminal node gives the proximity matrix, and so explicitly uses the class label.
Training set:


*

*Replace missing values by the average value.

*Repeat until satisfied:
a. Using imputed values calculated so far, train a random forest.
b. Compute the proximity matrix.
c. Using the proximity as the weight, impute missing values as the weighted average of non-missing values.
Test set:


*

*If labels exist, use the imputation derived from test data.

*If data is unlabeled, replicate the test set with a copy for each class label and proceed as with labeled data.


Here, (weighted) average refers to (weighted) median for numerical variables and (weighted) mode for categorical variables.  4-6 iterations are recommended in the references.
R documentation (pdf), Breiman's manual v4.0 (pdf), Breiman's RF page
