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.
- 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.
- 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