Thanks.
Does anyone have experience with using non-complete samples to do knn imputation? There is an R package, but it is unclear to me what it is doing.

Thanks @amueller @jnothman for the comment! I will modify the code.

I just did a speed test by using make_classification function to create dataset. 40% of samples have 1 missing feature, 40% of samples have 2 missing features and the rest is full. KNN imputation used 6 neighbors.

10000 samples, 20 features:
-mean: 0.0036s
-@jnothman 's method: 3.3282s (block query, block = 100 samples)
-default KNN: 14.3168s

10000 samples, 200 features:
-mean: 0.0296s
-@jnothman 's method: 36.8256s (block query, block = 100 samples)
-default KNN: 68.7889s

Btw, it would be cool to have a graph that shows the runtime for block queries with varying block size or varying number of features and samples.

have a look at the cool plots here: #4852

There is also a test error on older numpy.

Well I reckon my solution was fun but not clever. The better solution groups X by which features are missing, then for each group uses KNeighborsRegressor over the other features. This batches the work, does not necessarily require O(n^2 d) memory, reuses existing infrastructure/optimisations (and can use nearest neighbor trees if the number of queries for a particular field subset is sufficient to justify their construction), does not constrain to Euclidean...

I won't write it out, but to pull out groupings you can either use a lexsort over np.isnan(X).T and itertools.groupby, or the hackier np.unique(np.isnan(X).astype('u1').view((np.void, X.shape[1])), return_inverse=True), or perhaps there's a less obfuscated solution.

@jnothman do you think grouping by missing values would work in practice? I think it depends a lot on the number of samples and features whether the same pattern of missingness happens even twice... The stupidly batched version seems to work ok.

well, we could bench it for different values of n_samples or n_features with MAR data. Maybe it makes sense for points where exactly one value is missing, and then stupidly batch the rest? I'm not sure that the speed will warrant the complexity, though.

Making it feasible with non-Euclidean isn't enough reason?

On 13 June 2015 at 01:29, Andreas Mueller notifications@github.com wrote:

well, we could bench it for different values of n_samples or n_features
with MAR data. Maybe it makes sense for points where exactly one value is
missing, and then stupidly batch the rest? I'm not sure that the speed will
warrant the complexity, though.

—
Reply to this email directly or view it on GitHub
#4844 (comment)
.

I'm not sure how common / important that is.... and we can use pairwise_distances without using trees, right?

Indeed, my suggestion currently implemented could be simplified using pairwise_distances where a batch of queries with NaN replaced with 0 is X and the entire index is Y, except that:

• pairwise_distances won't currently accept inputs containing NaN, necessary to this approach (wherein we don't select columns in order to process in batch)
• replacing NaN with 0 only works for some metrics

I don't know whether grouping by set of missing values will be efficient in practice. There are obviously 2**n_features possible groups, which is bad, but as long as data is not missing at random, and only a fraction of data is missing, you'd expect very few of these combinations to actually exist. We'd need some real datasets to try it. Or just go with the batched approach.

Yeah, I'm not sure what would be the right assumption on missingness. Theory usually does missing completely at random but I would expect that not to be the case in practice. I have no source of actual data, so not sure how to test this.

can you also please fix the doctests (see travis output on python 3).

@jnothman That's a fair point. On a separate note, how would you recommend continuing the work on this pull request? It seems to have been inactive for a while, so presumably a lot of things outside this PR would have changed. What would be the ideal way forward? Thanks.

I don't think this PR has the right design or the right implementation, so you should basically start from scratch. The right design, IMO, is an extra parameter to Imputer, n_neighbors, which defaults to None, but otherwise only applies the strategy (mean, median or mode) over nearest neighbors (not that I'm sure median is useful when the nearest neighbors are euclidean). Ideally the implementation would make use of the neighbors subpackage (if only to ensure edge cases are correctly handled), which is why I suggest implementing a new metric for euclidean distance with features missing in sklearn.metrics.pairwise. It may be possible to take some of the example code from this PR. Does that sound doable?

I don't know if I understood you correctly, but wouldn't such an approach restrict our ability to work with "mixed" datasets that might, for instance, contain both continuous as well as nominal variables? Or is the idea here to see how things turn out with this approach first and consider a separate knn "strategy" in the future?

Ahh, I thought you literally meant euclidean only. In any case, the reason I brought that up is due to the VIM R-package (noted above) that uses the Gower distance for KNN imputation. Their implementation appears to allow handling of mixed datasets composed of "binary, categorical, ordered, continuous and semi-continuous" features. It would be interesting to know what you thought about their methodology (if you have the time to take a look at the linked paper that is). If that is not of interest then I'll proceed forward with what you have suggested above.

Right. What I appreciated about their implementation has to do with how they handle mixed datasets and not so much their handling of missing covariates during imputation. In fact, when I looked at their R code, I ran into this comment: "# TODO: find better way to handle missing in distance variables", which presumably means their current approach is probably not worth pursuing. I am currently aware of two other ways of handling such situations. First, the obvious one, used in the "impute" R-package from Bioconductor (which is also the original inspiration for this pull request I believe), which is using distances measured over existing variables: "Each candidate neighbor might be missing some of the coordinates used to calculate the distance. In this case we average the distance from the non-missing coordinates." A second method is an EM based sequential KNN imputation in the vein of MICE (i.e. in the sense of using an iterative procedure). And I think you also allude to this algorithm above. Additionally, I believe the paper also examines a non-iterative one time sequential KNN imputation.

I am interested in this problem and have some time/energy to contribute. While using the euclidean metric on the non-null features scaled by the (square root of the) inverse of the number of features used seems better than not scaling, I'm not sure this is ideal. For example suppose we have the data u = (1, 1, nan, 5, 7), v = (1, 1, 2, nan, nan), w = (1, 1, 8, 4.9, 7). Should v or w be deemed closer to u? In my opinion w should. Perhaps there should be some parameter specifying the minimum number or proportion of non-null features that must be used in the distance calculation?

The paper's approach, as reflected in their latest R package, is that if a given row is missing more than 50% of the columns (by default, but user can pass their own value), those rows are NOT used in knn imputation and their own missing columns are imputed to have the column means. Further, if any column has more than 80% values missing (again, this is an adjustable default) then the program throws an error and simply terminates execution.

Hi all, so you might have noted that I recently added a pull request that implements a kNN imputation algorithm. I would very much welcome and appreciate any feedback/suggestions/criticism you might have regarding the code. Also, it would be super if anybody wanted to join in, as the development is not yet complete.
With regards to the progress, I am happy to report that the implementation works fine in cases where the same data matrix is passed in fit() and transform(). And by "works fine", I mean in comparison to the R-package Impute that this implementation is inspired from. Some other things remain, and I hope to complete them in the coming days. Anyway, I look forward to hearing back from the community. Thanks! :)

Nice work. I also started working on this (https://github.com/ekorman/scikit-learn/blob/knn-impute/sklearn/metrics/pairwise.py), but my strategy was to change euclidean_distance in pairwise.py to allow for null entries and then use sklean.neighbors to do imputation. I think it may be useful to have this generality since presumably there are cases beyond imputation where it would be useful to use KNN on data with some null values.

Oh, cool! I don't know the approach you are taking, but the matrix formula used in my PR for calculating euclidean distance between all vector pairs in a matrix with NaN values (or between vectors in one matrix to those of another matrix with NaNs) might potentially be of interest to your work (it is contained in the function _get_knn()). In any case, I would be happy to change my code to incorporate the "NaN-enabled" sklearn.neighbors after you finish working on it.

Agreed. As @ekorman noted, the incorporation of a NaN handling pairwise distance calculator is useful beyond this particular use-case.

@ekorman By the way, please feel free to let me know if I can be of any use to help wrap things up faster unless, of course, if the remaining workload isn't that much and/or you prefer working by yourself.

Hey @ekorman , sorry to bother you again but was just wondering if you were still continuing your work with the NaN-enabled pairwise distance calculator. And in case if it is not feasible for you to work on it at the moment, please let me know and I can give it a try. Thanks.

@ashimb9 sorry for not responding sooner, some stuff came up but I should be able to start thinking about this again in the next few days. I definitely welcome any help. However, I think the code I wrote to compute the distances when there are NaN's is more or less the same code you wrote.

No worries man. Let me know how I can help.

@jnothman Hey Joel, as per our discussion here, I just created a PR which implements a NaN enabled euclidean distance calculator within sklearn.metrics and leverages that to get the nearest neighbors. I look forward to your feedback.

@ekorman Hi Eric, since I have not heard back from you in a while, I went ahead with the modification. I really had to get the ball rolling on this one as it has been stalled for a while. I hope you don't mind.

@lesteve @jnothman Hey just saw that the status of this was recently changed to "help wanted". Shouldn't this rather be closed in light of PR 9212?

Yes, okay. Current PR at #9212