title: Impute multiple missing values in a feature-vector
body: <p><strong>Edited post</strong></p>
  
  <p>This is a short and somewhat clarified version of the original post. </p>
  
  <ol>
  <li>We've got a training dataset (some features are significantly correlated). The feature space has 20 dimensions (all continuous). </li>
  <li>We need to train a nonparametric (most features form nonlinear subspaces and we can't assume a distribution for any of them) imputer (kNN or tree-based regression) using the training data.</li>
  <li>We need to predict multiple missing values in query data (a query feature-vector can have up to 13 missing features, so the imputer should handle any combination of missing features) using the trained imputer. <strong>NOTE</strong> the imputer should not be in any way retrained/fitted using the query data (like it is done in all mainstream R packages I've found so far: <code>Amelia</code>, <code>impute</code>, <code>mi</code> and <code>mice</code>...). That is the imputation should be based solely on the training data. </li>
  <li>The purpose for all this is described below. </li>
  <li>A small data sample is down below. </li>
  </ol>
  
  <p><strong>Original post (TL;DR)</strong></p>
  
  <p>Simply put, I've got some sophisticated data imputing to do. We've got a training dataset of ~100k 20D samples and a smaller testing dataset. Each feature/dimension is a continuous variable, but the scales are different. There are two distinct classes. Both datasets are very NA-inflated (NAs are not equally distributed across dimensions). I use <code>sklearn.ensemble.ExtraTreesClassifier</code> for classification and, although tree ensembles can handle missing data cases, there are three reasons to perform imputation</p>
  
  <ol>
  <li>This way we get votes from all trees in a forest during classification of a query dataset (not just those that don't have a missing feature/features).</li>
  <li>We don't loose data during training.</li>
  <li><code>scikit</code> implementation of tree ensembles (both <code>ExtraTrees</code> and <code>RandomForest</code>) do not handle missing values. But this point is not that much important. If it wasn't for the former two I would've just used <code>rpy2</code> + some nice R implementation.</li>
  </ol>
  
  <p>Things are quite simple with the training dataset because I can apply class-specific median imputation strategy to deal with missing values and this approach has been working fine so far. Obviously this approach can't be applied to a query - we don't have the classes to begin with. Since we know that the classes will likely have significantly different shares in the query we can't apply a class-indifferent approach because that might introduce bias and reduce classification performance, therefore we need to impute missing values from a model. </p>
  
  <p>Linear models are not an option for several reasons: </p>
  
  <ol>
  <li>all features are correlated to some extent; </li>
  <li>theoretically we can get all possible combinations of missing features in a sample feature-vector, even though our tool requires at least 7 non-missing features we end up with ~1^E6 possible models, this doesn't look very elegant if you ask me. </li>
  </ol>
  
  <p>Tree-based regression models aren't good for the very same reason. So we ended up picking kNN (k nearest neighbours), ball tree or LSH with radius threshold to be more specific. This approach fits the task quite well, because dimensions (ergo distances) are correlated, hence we get nice performance in extremely NA-rich cases, but there are several drawbacks:</p>
  
  <ol>
  <li>I haven't found a single implementation in Python (including <code>impute</code>, <code>sklearn.preprocessing.Imputer</code>, <code>orange</code>) that  handles feature-vectors with different sets of missing values, that is we want to have only one imputer for all possible combinations of missing features.</li>
  <li>kNN uses pair-wise point distances for prediction/imputation. As I've already mentioned our variables have different scales, hence the feature space must be normalised prior to distance estimations. And we need to know theoretic max/min values for each dimension to scale it properly. This is not as much of a problem, as it is a matter architectural simplicity (a user will have to provide a vector of min/max values). </li>
  </ol>
  
  <p>So here is what I would like to hear from you:</p>
  
  <ol>
  <li>Are there any classic ways to address the kNN-related issues given in the list above? I believe this must be a common case, yet I haven't found anything specific on the web. </li>
  <li>Is there a better way to impute data in our case? What would you recommend? Please, provide implementations in Python (R and C/C++ are considered as well).</li>
  </ol>
  
  <p><strong>Data</strong></p>
  
  <p>Here is a small sample of the training data set. I reduced the number of features to make it more readable. The query data has identical structure, except for the obvious absence of <code>category</code> information. </p>
  
  <pre><code>v1  v2  v3  v4  v5  category
  0.40524 0.71542 NA  0.81033 0.8209  1
  0.78421 0.76378 0.84324 0.58814 0.9348  2
  0.30055 NA  0.84324 NA  0.60003 1
  0.34754 0.25277 0.18861 0.28937 0.41394 1
  NA  0.71542 0.10333 0.41448 0.07377 1
  0.40019 0.02634 0.20924 NA  0.85404 2
  0.56404 0.5481  0.51284 0.39956 0.95957 2
  0.07758 0.40959 0.33802 0.27802 0.35396 1
  0.91219 0.89865 0.84324 0.81033 0.99243 1
  0.91219 NA  NA  0.81033 0.95988 2
  0.5463  0.89865 0.84324 0.81033 NA  2
  0.00963 0.06737 0.03719 0.08979 0.57746 2
  0.59875 0.89865 0.84324 0.50834 0.98906 1
  0.72092 NA  0.49118 0.58814 0.77973 2
  0.06389 NA  0.22424 0.08979 0.7556  2
  </code></pre>