Imputing missing values with unsupervised random trees
This provides a faster, scalable solution for imputing missing values in large datasets when other methods are not feasible, but it is incremental as it builds on existing imputation approaches.
The paper tackles the problem of missing value imputation by proposing a non-iterative method using recursive semi-random hyperplane cuts to assign observations to overlapping buckets for weighted average imputations, resulting in a technique that is much faster than chained equations and scales easily to large datasets, though with sometimes lower quality.
This work proposes a non-iterative strategy for missing value imputations which is guided by similarity between observations, but instead of explicitly determining distances or nearest neighbors, it assigns observations to overlapping buckets through recursive semi-random hyperplane cuts, in which weighted averages are determined as imputations for each variable. The quality of these imputations is oftentimes not as good as that of chained equations, but the proposed technique is much faster, non-iterative, can make imputations on new data without re-calculating anything, and scales easily to large and high-dimensional datasets, providing a significant boost over simple mean/median imputation in regression and classification metrics with imputed values when other methods are not feasible.