Repository: scikit-learn/scikit-learn
Pull request: [MRG+2] Moves Imputation out of Preprocessing
<!--
Thanks for contributing a pull request! Please ensure you have taken a look at
the contribution guidelines: https://github.com/scikit-learn/scikit-learn/blob/master/CONTRIBUTING.md#pull-request-checklist
-->

#### Reference Issues/PRs
<!--
Example: Fixes #1234. See also #3456.
Please use keywords (e.g., Fixes) to create link to the issues or pull requests
you resolved, so that they will automatically be closed when your pull request
is merged. See https://github.com/blog/1506-closing-issues-via-pull-requests
-->
Fixes #9726 


#### What does this implement/fix? Explain your changes.
Changes done as per suggestions

#### Tasks

- [x] copy `sklearn/preprocessing/imputation.py` to `sklearn/impute.py`, as well as the corresponding tests.
- [x] deprecate `Imputer` in `sklearn/preprocessing/imputation.py` to be removed in v0.22.
- [x] create a `sklearn.impute` section in `doc/modules/classes.rst`
- [x] update the deprecated section at the bottom of `doc/modules/classes.rst`
- [x] update `sklearn/__init__.py's __all__`
- [x] move imputation documentation from `doc/modules/preprocessing.rst` to `doc/modules/impute.rst`
- [x] we might also want to rename Imputer in the new module to SimpleImputer, DummyImputer or something
- [x] update any references to Imputer (in sklearn/, doc/ or examples/) to refer to the new location.


<!--
Please be aware that we are a loose team of volunteers so patience is
necessary; assistance handling other issues is very welcome. We value
all user contributions, no matter how minor they are. If we are slow to
review, either the pull request needs some benchmarking, tinkering,
convincing, etc. or more likely the reviewers are simply busy. In either
case, we ask for your understanding during the review process.
For more information, see our FAQ on this topic:
http://scikit-learn.org/dev/faq.html#why-is-my-pull-request-not-getting-any-attention.

Thanks for contributing!
-->


Problem statement:
Move imputation out of preprocessing
While we're considering additional imputers, I've wondered whether preprocessing is the right place for it. Yes, it is a preprocessing step before other learning, but it often makes use of other supervised and unsupervised learners and hence is a learning task of its own. And preprocessing is getting a bit cramped.

We could also do as with other models and have imputers appear in modules on the basis of how they work rather than function: `KNNImputer` could appear in neighbors for instance. `MICE` could appear where..? And the basic `Imputer` in dummy? probably not.

In practice I think it is more useful for users to `import sklearn.impute`, akin to our clusterers and decomposition, and unlike our predictors and outlier detectors that are grouped by algorithm.

Hints from issue discussion:
> modules on the basis of how they work rather than function

I don't like this (even though we've done that in the past - inconsistently. Why is LDA and LinearSVC not in linear models?)

I'm +.5 for ``sklearn.impute``, possibly moving when when we add the next class (KNNImputer I guess?).
Actually, given that MICE is not that far away, should be +1
MICE is not far away at all. `sklearn.impute` would be useful, but importing it would conceivably import `neighbors`, `linear_model`, `ensemble` and `tree` if we had implementations of MICE, KNN and forest-based imputation there. We have decidedly scattered anomaly detection around the place. I am uncomfortable about putting MICE and KNNImputer in preprocessing, but I'm not *entirely* certain that sklearn.impute is the right solution.

If we make sklearn.impute, do we rename Imputer to `sklearn.impute.BasicImputer` or `FeaturewiseImputer` or some such?
Of course we could just make KNNImputer live under neighbors and MICE live under ?ensemble.

I've wondered whether in some ways it would make sense to have a pseudo-module sklearn.classifiers, sklearn.regressors, sklearn.imputers, etc, that import from the relevant implementation locations...
Yeah... I would prefer a semantic organization, but it's not how we have done things in the past. I guess you suggest having that in parallel to the current structure? I wouldn't be opposed, but it's a big change. Is the goal to keep two places to import from long-term? That seems slightly confusing....
it's not entirely true that we haven't done semantic organisation in the
past, sklearn.cluster,decomposition,manifold...

On 9 Dec 2017 5:59 am, "Andreas Mueller" <notifications@github.com> wrote:

> Yeah... I would prefer a semantic organization, but it's not how we have
> done things in the past. I guess you suggest having that in parallel to the
> current structure? I wouldn't be opposed, but it's a big change. Is the
> goal to keep two places to import from long-term? That seems slightly
> confusing....
>
> —
> You are receiving this because you authored the thread.
> Reply to this email directly, view it on GitHub
> <https://github.com/scikit-learn/scikit-learn/issues/9726#issuecomment-350343951>,
> or mute the thread
> <https://github.com/notifications/unsubscribe-auth/AAEz6yLh_frd5DWue1XE_rdsyqIfjCXoks5s-YbzgaJpZM4PSgEV>
> .
>

True, we have done a really weird mix. The fact that we have ``SGDClassifier`` which implements many losses, and ``LogisticRegression`` which implements many solvers shows that we're not the best with the consistency ;)
but for the users it's moot, as long as they can find stuff.

The MissingnessIndicator (#8075) should also live in this module, which may help users.
I'd like another opinion, but I think this should happen. Make sklearn.impute and move Imputer and all the open imputation-related PRs to this module.

Commit message: all references to preprocessing.impute changed to impute

Patch to review:
diff --git a/doc/glossary.rst b/doc/glossary.rst
index bea57117f7cbf..55355f0d5d44c 100644
--- a/doc/glossary.rst
+++ b/doc/glossary.rst
@@ -480,7 +480,7 @@ General Concepts
 
     missing values
         Most Scikit-learn estimators do not work with missing values. When they
-        do (e.g. in :class:`preprocessing.Imputer`), NaN is the preferred
+        do (e.g. in :class:`Imputer`), NaN is the preferred
         representation of missing values in float arrays.  If the array has
         integer dtype, NaN cannot be represented. For this reason, we support
         specifying another ``missing_values`` value when imputation or
diff --git a/doc/modules/classes.rst b/doc/modules/classes.rst
index 5977e2f01a9b3..1b201ca92ba9e 100644
--- a/doc/modules/classes.rst
+++ b/doc/modules/classes.rst
@@ -609,6 +609,25 @@ Kernels:
    isotonic.check_increasing
    isotonic.isotonic_regression
 
+.. _impute_ref:
+
+:mod:`sklearn.impute`: Impute
+=============================
+
+.. automodule:: sklearn.impute
+   :no-members:
+   :no-inherited-members:
+
+**User guide:** See the :ref:`Impute` section for further details.
+
+.. currentmodule:: sklearn
+
+.. autosummary::
+   :toctree: generated/
+   :template: class.rst
+
+   impute.Imputer
+
 .. _kernel_approximation_ref:
 
 :mod:`sklearn.kernel_approximation` Kernel Approximation
@@ -1399,6 +1418,16 @@ Recently deprecated
 ===================
 
 
+To be removed in 0.22
+---------------------
+
+.. autosummary::
+   :toctree: generated/
+   :template: deprecated_class.rst
+
+   preprocessing.Imputer
+
+
 To be removed in 0.21
 ---------------------
 
diff --git a/doc/modules/impute.rst b/doc/modules/impute.rst
new file mode 100644
index 0000000000000..017e22e650010
--- /dev/null
+++ b/doc/modules/impute.rst
@@ -0,0 +1,54 @@
+
+.. _impute:
+
+Imputation of missing values
+============================
+
+For various reasons, many real world datasets contain missing values, often
+encoded as blanks, NaNs or other placeholders. Such datasets however are
+incompatible with scikit-learn estimators which assume that all values in an
+array are numerical, and that all have and hold meaning. A basic strategy to use
+incomplete datasets is to discard entire rows and/or columns containing missing
+values. However, this comes at the price of losing data which may be valuable
+(even though incomplete). A better strategy is to impute the missing values,
+i.e., to infer them from the known part of the data.
+
+The :class:`Imputer` class provides basic strategies for imputing missing
+values, either using the mean, the median or the most frequent value of
+the row or column in which the missing values are located. This class
+also allows for different missing values encodings.
+
+The following snippet demonstrates how to replace missing values,
+encoded as ``np.nan``, using the mean value of the columns (axis 0)
+that contain the missing values::
+
+    >>> import numpy as np
+    >>> from sklearn.preprocessing import Imputer
+    >>> imp = Imputer(missing_values='NaN', strategy='mean', axis=0)
+    >>> imp.fit([[1, 2], [np.nan, 3], [7, 6]])
+    Imputer(axis=0, copy=True, missing_values='NaN', strategy='mean', verbose=0)
+    >>> X = [[np.nan, 2], [6, np.nan], [7, 6]]
+    >>> print(imp.transform(X))                           # doctest: +ELLIPSIS
+    [[ 4.          2.        ]
+     [ 6.          3.666...]
+     [ 7.          6.        ]]
+
+The :class:`Imputer` class also supports sparse matrices::
+
+    >>> import scipy.sparse as sp
+    >>> X = sp.csc_matrix([[1, 2], [0, 3], [7, 6]])
+    >>> imp = Imputer(missing_values=0, strategy='mean', axis=0)
+    >>> imp.fit(X)
+    Imputer(axis=0, copy=True, missing_values=0, strategy='mean', verbose=0)
+    >>> X_test = sp.csc_matrix([[0, 2], [6, 0], [7, 6]])
+    >>> print(imp.transform(X_test))                      # doctest: +ELLIPSIS
+    [[ 4.          2.        ]
+     [ 6.          3.666...]
+     [ 7.          6.        ]]
+
+Note that, here, missing values are encoded by 0 and are thus implicitly stored
+in the matrix. This format is thus suitable when there are many more missing
+values than observed values.
+
+:class:`Imputer` can be used in a Pipeline as a way to build a composite
+estimator that supports imputation. See :ref:`sphx_glr_auto_examples_plot_missing_values.py`.
\ No newline at end of file
diff --git a/examples/plot_missing_values.py b/examples/plot_missing_values.py
index 17a256fa4fa2f..50d509b62f85b 100644
--- a/examples/plot_missing_values.py
+++ b/examples/plot_missing_values.py
@@ -28,7 +28,7 @@
 from sklearn.datasets import load_boston
 from sklearn.ensemble import RandomForestRegressor
 from sklearn.pipeline import Pipeline
-from sklearn.preprocessing import Imputer
+from sklearn.impute import Imputer
 from sklearn.model_selection import cross_val_score
 
 rng = np.random.RandomState(0)
diff --git a/sklearn/__init__.py b/sklearn/__init__.py
index 5f2278d1c8c37..ff86901bd20ec 100644
--- a/sklearn/__init__.py
+++ b/sklearn/__init__.py
@@ -143,7 +143,7 @@ def config_context(**new_config):
                'mixture', 'model_selection', 'multiclass', 'multioutput',
                'naive_bayes', 'neighbors', 'neural_network', 'pipeline',
                'preprocessing', 'random_projection', 'semi_supervised',
-               'svm', 'tree', 'discriminant_analysis',
+               'svm', 'tree', 'discriminant_analysis', 'impute',
                # Non-modules:
                'clone']
 
diff --git a/sklearn/impute.py b/sklearn/impute.py
new file mode 100644
index 0000000000000..6a24a3044d59d
--- /dev/null
+++ b/sklearn/impute.py
@@ -0,0 +1,375 @@
+# Authors: Nicolas Tresegnie <nicolas.tresegnie@gmail.com>
+# License: BSD 3 clause
+
+import warnings
+
+import numpy as np
+import numpy.ma as ma
+from scipy import sparse
+from scipy import stats
+
+from .base import BaseEstimator, TransformerMixin
+from .utils import check_array
+from .utils.sparsefuncs import _get_median
+from .utils.validation import check_is_fitted
+from .utils.validation import FLOAT_DTYPES
+
+from .externals import six
+
+zip = six.moves.zip
+map = six.moves.map
+
+__all__ = [
+    'Imputer',
+]
+
+
+def _get_mask(X, value_to_mask):
+    """Compute the boolean mask X == missing_values."""
+    if value_to_mask == "NaN" or np.isnan(value_to_mask):
+        return np.isnan(X)
+    else:
+        return X == value_to_mask
+
+
+def _most_frequent(array, extra_value, n_repeat):
+    """Compute the most frequent value in a 1d array extended with
+       [extra_value] * n_repeat, where extra_value is assumed to be not part
+       of the array."""
+    # Compute the most frequent value in array only
+    if array.size > 0:
+        mode = stats.mode(array)
+        most_frequent_value = mode[0][0]
+        most_frequent_count = mode[1][0]
+    else:
+        most_frequent_value = 0
+        most_frequent_count = 0
+
+    # Compare to array + [extra_value] * n_repeat
+    if most_frequent_count == 0 and n_repeat == 0:
+        return np.nan
+    elif most_frequent_count < n_repeat:
+        return extra_value
+    elif most_frequent_count > n_repeat:
+        return most_frequent_value
+    elif most_frequent_count == n_repeat:
+        # Ties the breaks. Copy the behaviour of scipy.stats.mode
+        if most_frequent_value < extra_value:
+            return most_frequent_value
+        else:
+            return extra_value
+
+
+class Imputer(BaseEstimator, TransformerMixin):
+    """Imputation transformer for completing missing values.
+
+    Read more in the :ref:`User Guide <imputation>`.
+
+    Parameters
+    ----------
+    missing_values : integer or "NaN", optional (default="NaN")
+        The placeholder for the missing values. All occurrences of
+        `missing_values` will be imputed. For missing values encoded as np.nan,
+        use the string value "NaN".
+
+    strategy : string, optional (default="mean")
+        The imputation strategy.
+
+        - If "mean", then replace missing values using the mean along
+          the axis.
+        - If "median", then replace missing values using the median along
+          the axis.
+        - If "most_frequent", then replace missing using the most frequent
+          value along the axis.
+
+    axis : integer, optional (default=0)
+        The axis along which to impute.
+
+        - If `axis=0`, then impute along columns.
+        - If `axis=1`, then impute along rows.
+
+    verbose : integer, optional (default=0)
+        Controls the verbosity of the imputer.
+
+    copy : boolean, optional (default=True)
+        If True, a copy of X will be created. If False, imputation will
+        be done in-place whenever possible. Note that, in the following cases,
+        a new copy will always be made, even if `copy=False`:
+
+        - If X is not an array of floating values;
+        - If X is sparse and `missing_values=0`;
+        - If `axis=0` and X is encoded as a CSR matrix;
+        - If `axis=1` and X is encoded as a CSC matrix.
+
+    Attributes
+    ----------
+    statistics_ : array of shape (n_features,)
+        The imputation fill value for each feature if axis == 0.
+
+    Notes
+    -----
+    - When ``axis=0``, columns which only contained missing values at `fit`
+      are discarded upon `transform`.
+    - When ``axis=1``, an exception is raised if there are rows for which it is
+      not possible to fill in the missing values (e.g., because they only
+      contain missing values).
+    """
+    def __init__(self, missing_values="NaN", strategy="mean",
+                 axis=0, verbose=0, copy=True):
+        self.missing_values = missing_values
+        self.strategy = strategy
+        self.axis = axis
+        self.verbose = verbose
+        self.copy = copy
+
+    def fit(self, X, y=None):
+        """Fit the imputer on X.
+
+        Parameters
+        ----------
+        X : {array-like, sparse matrix}, shape (n_samples, n_features)
+            Input data, where ``n_samples`` is the number of samples and
+            ``n_features`` is the number of features.
+
+        Returns
+        -------
+        self : Imputer
+        """
+        # Check parameters
+        allowed_strategies = ["mean", "median", "most_frequent"]
+        if self.strategy not in allowed_strategies:
+            raise ValueError("Can only use these strategies: {0} "
+                             " got strategy={1}".format(allowed_strategies,
+                                                        self.strategy))
+
+        if self.axis not in [0, 1]:
+            raise ValueError("Can only impute missing values on axis 0 and 1, "
+                             " got axis={0}".format(self.axis))
+
+        # Since two different arrays can be provided in fit(X) and
+        # transform(X), the imputation data will be computed in transform()
+        # when the imputation is done per sample (i.e., when axis=1).
+        if self.axis == 0:
+            X = check_array(X, accept_sparse='csc', dtype=np.float64,
+                            force_all_finite=False)
+
+            if sparse.issparse(X):
+                self.statistics_ = self._sparse_fit(X,
+                                                    self.strategy,
+                                                    self.missing_values,
+                                                    self.axis)
+            else:
+                self.statistics_ = self._dense_fit(X,
+                                                   self.strategy,
+                                                   self.missing_values,
+                                                   self.axis)
+
+        return self
+
+    def _sparse_fit(self, X, strategy, missing_values, axis):
+        """Fit the transformer on sparse data."""
+        # Imputation is done "by column", so if we want to do it
+        # by row we only need to convert the matrix to csr format.
+        if axis == 1:
+            X = X.tocsr()
+        else:
+            X = X.tocsc()
+
+        # Count the zeros
+        if missing_values == 0:
+            n_zeros_axis = np.zeros(X.shape[not axis], dtype=int)
+        else:
+            n_zeros_axis = X.shape[axis] - np.diff(X.indptr)
+
+        # Mean
+        if strategy == "mean":
+            if missing_values != 0:
+                n_non_missing = n_zeros_axis
+
+                # Mask the missing elements
+                mask_missing_values = _get_mask(X.data, missing_values)
+                mask_valids = np.logical_not(mask_missing_values)
+
+                # Sum only the valid elements
+                new_data = X.data.copy()
+                new_data[mask_missing_values] = 0
+                X = sparse.csc_matrix((new_data, X.indices, X.indptr),
+                                      copy=False)
+                sums = X.sum(axis=0)
+
+                # Count the elements != 0
+                mask_non_zeros = sparse.csc_matrix(
+                    (mask_valids.astype(np.float64),
+                     X.indices,
+                     X.indptr), copy=False)
+                s = mask_non_zeros.sum(axis=0)
+                n_non_missing = np.add(n_non_missing, s)
+
+            else:
+                sums = X.sum(axis=axis)
+                n_non_missing = np.diff(X.indptr)
+
+            # Ignore the error, columns with a np.nan statistics_
+            # are not an error at this point. These columns will
+            # be removed in transform
+            with np.errstate(all="ignore"):
+                return np.ravel(sums) / np.ravel(n_non_missing)
+
+        # Median + Most frequent
+        else:
+            # Remove the missing values, for each column
+            columns_all = np.hsplit(X.data, X.indptr[1:-1])
+            mask_missing_values = _get_mask(X.data, missing_values)
+            mask_valids = np.hsplit(np.logical_not(mask_missing_values),
+                                    X.indptr[1:-1])
+
+            # astype necessary for bug in numpy.hsplit before v1.9
+            columns = [col[mask.astype(bool, copy=False)]
+                       for col, mask in zip(columns_all, mask_valids)]
+
+            # Median
+            if strategy == "median":
+                median = np.empty(len(columns))
+                for i, column in enumerate(columns):
+                    median[i] = _get_median(column, n_zeros_axis[i])
+
+                return median
+
+            # Most frequent
+            elif strategy == "most_frequent":
+                most_frequent = np.empty(len(columns))
+
+                for i, column in enumerate(columns):
+                    most_frequent[i] = _most_frequent(column,
+                                                      0,
+                                                      n_zeros_axis[i])
+
+                return most_frequent
+
+    def _dense_fit(self, X, strategy, missing_values, axis):
+        """Fit the transformer on dense data."""
+        X = check_array(X, force_all_finite=False)
+        mask = _get_mask(X, missing_values)
+        masked_X = ma.masked_array(X, mask=mask)
+
+        # Mean
+        if strategy == "mean":
+            mean_masked = np.ma.mean(masked_X, axis=axis)
+            # Avoid the warning "Warning: converting a masked element to nan."
+            mean = np.ma.getdata(mean_masked)
+            mean[np.ma.getmask(mean_masked)] = np.nan
+
+            return mean
+
+        # Median
+        elif strategy == "median":
+            if tuple(int(v) for v in np.__version__.split('.')[:2]) < (1, 5):
+                # In old versions of numpy, calling a median on an array
+                # containing nans returns nan. This is different is
+                # recent versions of numpy, which we want to mimic
+                masked_X.mask = np.logical_or(masked_X.mask,
+                                              np.isnan(X))
+            median_masked = np.ma.median(masked_X, axis=axis)
+            # Avoid the warning "Warning: converting a masked element to nan."
+            median = np.ma.getdata(median_masked)
+            median[np.ma.getmaskarray(median_masked)] = np.nan
+
+            return median
+
+        # Most frequent
+        elif strategy == "most_frequent":
+            # scipy.stats.mstats.mode cannot be used because it will no work
+            # properly if the first element is masked and if its frequency
+            # is equal to the frequency of the most frequent valid element
+            # See https://github.com/scipy/scipy/issues/2636
+
+            # To be able access the elements by columns
+            if axis == 0:
+                X = X.transpose()
+                mask = mask.transpose()
+
+            most_frequent = np.empty(X.shape[0])
+
+            for i, (row, row_mask) in enumerate(zip(X[:], mask[:])):
+                row_mask = np.logical_not(row_mask).astype(np.bool)
+                row = row[row_mask]
+                most_frequent[i] = _most_frequent(row, np.nan, 0)
+
+            return most_frequent
+
+    def transform(self, X):
+        """Impute all missing values in X.
+
+        Parameters
+        ----------
+        X : {array-like, sparse matrix}, shape = [n_samples, n_features]
+            The input data to complete.
+        """
+        if self.axis == 0:
+            check_is_fitted(self, 'statistics_')
+            X = check_array(X, accept_sparse='csc', dtype=FLOAT_DTYPES,
+                            force_all_finite=False, copy=self.copy)
+            statistics = self.statistics_
+            if X.shape[1] != statistics.shape[0]:
+                raise ValueError("X has %d features per sample, expected %d"
+                                 % (X.shape[1], self.statistics_.shape[0]))
+
+        # Since two different arrays can be provided in fit(X) and
+        # transform(X), the imputation data need to be recomputed
+        # when the imputation is done per sample
+        else:
+            X = check_array(X, accept_sparse='csr', dtype=FLOAT_DTYPES,
+                            force_all_finite=False, copy=self.copy)
+
+            if sparse.issparse(X):
+                statistics = self._sparse_fit(X,
+                                              self.strategy,
+                                              self.missing_values,
+                                              self.axis)
+
+            else:
+                statistics = self._dense_fit(X,
+                                             self.strategy,
+                                             self.missing_values,
+                                             self.axis)
+
+        # Delete the invalid rows/columns
+        invalid_mask = np.isnan(statistics)
+        valid_mask = np.logical_not(invalid_mask)
+        valid_statistics = statistics[valid_mask]
+        valid_statistics_indexes = np.where(valid_mask)[0]
+        missing = np.arange(X.shape[not self.axis])[invalid_mask]
+
+        if self.axis == 0 and invalid_mask.any():
+            if self.verbose:
+                warnings.warn("Deleting features without "
+                              "observed values: %s" % missing)
+            X = X[:, valid_statistics_indexes]
+        elif self.axis == 1 and invalid_mask.any():
+            raise ValueError("Some rows only contain "
+                             "missing values: %s" % missing)
+
+        # Do actual imputation
+        if sparse.issparse(X) and self.missing_values != 0:
+            mask = _get_mask(X.data, self.missing_values)
+            indexes = np.repeat(np.arange(len(X.indptr) - 1, dtype=np.int),
+                                np.diff(X.indptr))[mask]
+
+            X.data[mask] = valid_statistics[indexes].astype(X.dtype,
+                                                            copy=False)
+        else:
+            if sparse.issparse(X):
+                X = X.toarray()
+
+            mask = _get_mask(X, self.missing_values)
+            n_missing = np.sum(mask, axis=self.axis)
+            values = np.repeat(valid_statistics, n_missing)
+
+            if self.axis == 0:
+                coordinates = np.where(mask.transpose())[::-1]
+            else:
+                coordinates = mask
+
+            X[coordinates] = values
+
+        return X
diff --git a/sklearn/model_selection/tests/test_search.py b/sklearn/model_selection/tests/test_search.py
index 87093699a5c38..cfaaad98af88f 100644
--- a/sklearn/model_selection/tests/test_search.py
+++ b/sklearn/model_selection/tests/test_search.py
@@ -63,7 +63,7 @@
 from sklearn.metrics import accuracy_score
 from sklearn.metrics import make_scorer
 from sklearn.metrics import roc_auc_score
-from sklearn.preprocessing import Imputer
+from sklearn.impute import Imputer
 from sklearn.pipeline import Pipeline
 from sklearn.linear_model import Ridge, SGDClassifier
 
diff --git a/sklearn/model_selection/tests/test_validation.py b/sklearn/model_selection/tests/test_validation.py
index 3863fe03740f4..c4f0cbac65518 100644
--- a/sklearn/model_selection/tests/test_validation.py
+++ b/sklearn/model_selection/tests/test_validation.py
@@ -64,7 +64,8 @@
 from sklearn.svm import SVC
 from sklearn.cluster import KMeans
 
-from sklearn.preprocessing import Imputer
+from sklearn.impute import Imputer
+
 from sklearn.preprocessing import LabelEncoder
 from sklearn.pipeline import Pipeline
 
diff --git a/sklearn/preprocessing/imputation.py b/sklearn/preprocessing/imputation.py
index 43c5089e16626..a8963f13300d4 100644
--- a/sklearn/preprocessing/imputation.py
+++ b/sklearn/preprocessing/imputation.py
@@ -10,6 +10,7 @@
 
 from ..base import BaseEstimator, TransformerMixin
 from ..utils import check_array
+from ..utils import deprecated
 from ..utils.sparsefuncs import _get_median
 from ..utils.validation import check_is_fitted
 from ..utils.validation import FLOAT_DTYPES
@@ -60,6 +61,8 @@ def _most_frequent(array, extra_value, n_repeat):
             return extra_value
 
 
+@deprecated("Imputer was deprecated in version 0.20 and will be "
+            "removed in 0.22. Import Imputer from sklearn instead.")
 class Imputer(BaseEstimator, TransformerMixin):
     """Imputation transformer for completing missing values.
 
diff --git a/sklearn/tests/test_calibration.py b/sklearn/tests/test_calibration.py
index e4499e35d5a67..c872d5bb43c7e 100644
--- a/sklearn/tests/test_calibration.py
+++ b/sklearn/tests/test_calibration.py
@@ -17,7 +17,7 @@
 from sklearn.ensemble import RandomForestClassifier, RandomForestRegressor
 from sklearn.svm import LinearSVC
 from sklearn.pipeline import Pipeline
-from sklearn.preprocessing import Imputer
+from sklearn.impute import Imputer
 from sklearn.metrics import brier_score_loss, log_loss
 from sklearn.calibration import CalibratedClassifierCV
 from sklearn.calibration import _sigmoid_calibration, _SigmoidCalibration
diff --git a/sklearn/tests/test_cross_validation.py b/sklearn/tests/test_cross_validation.py
index 4d756bdaa0cf8..af63fccacba8c 100644
--- a/sklearn/tests/test_cross_validation.py
+++ b/sklearn/tests/test_cross_validation.py
@@ -45,7 +45,7 @@
 from sklearn.svm import SVC
 from sklearn.cluster import KMeans
 
-from sklearn.preprocessing import Imputer
+from sklearn.impute import Imputer
 from sklearn.pipeline import Pipeline
 
 
diff --git a/sklearn/tests/test_grid_search.py b/sklearn/tests/test_grid_search.py
index f3c003e8c5be5..55464dd7da3a6 100644
--- a/sklearn/tests/test_grid_search.py
+++ b/sklearn/tests/test_grid_search.py
@@ -52,7 +52,7 @@
                                      ParameterGrid, ParameterSampler)
     from sklearn.cross_validation import KFold, StratifiedKFold
 
-from sklearn.preprocessing import Imputer
+from sklearn.impute import Imputer
 from sklearn.pipeline import Pipeline
 
 
diff --git a/sklearn/tests/test_impute.py b/sklearn/tests/test_impute.py
new file mode 100644
index 0000000000000..395e17e34d25f
--- /dev/null
+++ b/sklearn/tests/test_impute.py
@@ -0,0 +1,366 @@
+
+import numpy as np
+from scipy import sparse
+
+from sklearn.utils.testing import assert_equal
+from sklearn.utils.testing import assert_array_equal
+from sklearn.utils.testing import assert_array_almost_equal
+from sklearn.utils.testing import assert_raises
+from sklearn.utils.testing import assert_false
+
+from sklearn.impute import Imputer
+from sklearn.pipeline import Pipeline
+from sklearn.model_selection import GridSearchCV
+from sklearn import tree
+from sklearn.random_projection import sparse_random_matrix
+
+
+def _check_statistics(X, X_true,
+                      strategy, statistics, missing_values):
+    """Utility function for testing imputation for a given strategy.
+
+    Test:
+        - along the two axes
+        - with dense and sparse arrays
+
+    Check that:
+        - the statistics (mean, median, mode) are correct
+        - the missing values are imputed correctly"""
+
+    err_msg = "Parameters: strategy = %s, missing_values = %s, " \
+              "axis = {0}, sparse = {1}" % (strategy, missing_values)
+
+    assert_ae = assert_array_equal
+    if X.dtype.kind == 'f' or X_true.dtype.kind == 'f':
+        assert_ae = assert_array_almost_equal
+
+    # Normal matrix, axis = 0
+    imputer = Imputer(missing_values, strategy=strategy, axis=0)
+    X_trans = imputer.fit(X).transform(X.copy())
+    assert_ae(imputer.statistics_, statistics,
+              err_msg=err_msg.format(0, False))
+    assert_ae(X_trans, X_true, err_msg=err_msg.format(0, False))
+
+    # Normal matrix, axis = 1
+    imputer = Imputer(missing_values, strategy=strategy, axis=1)
+    imputer.fit(X.transpose())
+    if np.isnan(statistics).any():
+        assert_raises(ValueError, imputer.transform, X.copy().transpose())
+    else:
+        X_trans = imputer.transform(X.copy().transpose())
+        assert_ae(X_trans, X_true.transpose(),
+                  err_msg=err_msg.format(1, False))
+
+    # Sparse matrix, axis = 0
+    imputer = Imputer(missing_values, strategy=strategy, axis=0)
+    imputer.fit(sparse.csc_matrix(X))
+    X_trans = imputer.transform(sparse.csc_matrix(X.copy()))
+
+    if sparse.issparse(X_trans):
+        X_trans = X_trans.toarray()
+
+    assert_ae(imputer.statistics_, statistics,
+              err_msg=err_msg.format(0, True))
+    assert_ae(X_trans, X_true, err_msg=err_msg.format(0, True))
+
+    # Sparse matrix, axis = 1
+    imputer = Imputer(missing_values, strategy=strategy, axis=1)
+    imputer.fit(sparse.csc_matrix(X.transpose()))
+    if np.isnan(statistics).any():
+        assert_raises(ValueError, imputer.transform,
+                      sparse.csc_matrix(X.copy().transpose()))
+    else:
+        X_trans = imputer.transform(sparse.csc_matrix(X.copy().transpose()))
+
+        if sparse.issparse(X_trans):
+            X_trans = X_trans.toarray()
+
+        assert_ae(X_trans, X_true.transpose(),
+                  err_msg=err_msg.format(1, True))
+
+
+def test_imputation_shape():
+    # Verify the shapes of the imputed matrix for different strategies.
+    X = np.random.randn(10, 2)
+    X[::2] = np.nan
+
+    for strategy in ['mean', 'median', 'most_frequent']:
+        imputer = Imputer(strategy=strategy)
+        X_imputed = imputer.fit_transform(X)
+        assert_equal(X_imputed.shape, (10, 2))
+        X_imputed = imputer.fit_transform(sparse.csr_matrix(X))
+        assert_equal(X_imputed.shape, (10, 2))
+
+
+def test_imputation_mean_median_only_zero():
+    # Test imputation using the mean and median strategies, when
+    # missing_values == 0.
+    X = np.array([
+        [np.nan, 0, 0, 0, 5],
+        [np.nan, 1, 0, np.nan, 3],
+        [np.nan, 2, 0, 0, 0],
+        [np.nan, 6, 0, 5, 13],
+    ])
+
+    X_imputed_mean = np.array([
+        [3, 5],
+        [1, 3],
+        [2, 7],
+        [6, 13],
+    ])
+    statistics_mean = [np.nan, 3, np.nan, np.nan, 7]
+
+    # Behaviour of median with NaN is undefined, e.g. different results in
+    # np.median and np.ma.median
+    X_for_median = X[:, [0, 1, 2, 4]]
+    X_imputed_median = np.array([
+        [2, 5],
+        [1, 3],
+        [2, 5],
+        [6, 13],
+    ])
+    statistics_median = [np.nan, 2, np.nan, 5]
+
+    _check_statistics(X, X_imputed_mean, "mean", statistics_mean, 0)
+    _check_statistics(X_for_median, X_imputed_median, "median",
+                      statistics_median, 0)
+
+
+def safe_median(arr, *args, **kwargs):
+    # np.median([]) raises a TypeError for numpy >= 1.10.1
+    length = arr.size if hasattr(arr, 'size') else len(arr)
+    return np.nan if length == 0 else np.median(arr, *args, **kwargs)
+
+
+def safe_mean(arr, *args, **kwargs):
+    # np.mean([]) raises a RuntimeWarning for numpy >= 1.10.1
+    length = arr.size if hasattr(arr, 'size') else len(arr)
+    return np.nan if length == 0 else np.mean(arr, *args, **kwargs)
+
+
+def test_imputation_mean_median():
+    # Test imputation using the mean and median strategies, when
+    # missing_values != 0.
+    rng = np.random.RandomState(0)
+
+    dim = 10
+    dec = 10
+    shape = (dim * dim, dim + dec)
+
+    zeros = np.zeros(shape[0])
+    values = np.arange(1, shape[0] + 1)
+    values[4::2] = - values[4::2]
+
+    tests = [("mean", "NaN", lambda z, v, p: safe_mean(np.hstack((z, v)))),
+             ("mean", 0, lambda z, v, p: np.mean(v)),
+             ("median", "NaN", lambda z, v, p: safe_median(np.hstack((z, v)))),
+             ("median", 0, lambda z, v, p: np.median(v))]
+
+    for strategy, test_missing_values, true_value_fun in tests:
+        X = np.empty(shape)
+        X_true = np.empty(shape)
+        true_statistics = np.empty(shape[1])
+
+        # Create a matrix X with columns
+        #    - with only zeros,
+        #    - with only missing values
+        #    - with zeros, missing values and values
+        # And a matrix X_true containing all true values
+        for j in range(shape[1]):
+            nb_zeros = (j - dec + 1 > 0) * (j - dec + 1) * (j - dec + 1)
+            nb_missing_values = max(shape[0] + dec * dec
+                                    - (j + dec) * (j + dec), 0)
+            nb_values = shape[0] - nb_zeros - nb_missing_values
+
+            z = zeros[:nb_zeros]
+            p = np.repeat(test_missing_values, nb_missing_values)
+            v = values[rng.permutation(len(values))[:nb_values]]
+
+            true_statistics[j] = true_value_fun(z, v, p)
+
+            # Create the columns
+            X[:, j] = np.hstack((v, z, p))
+
+            if 0 == test_missing_values:
+                X_true[:, j] = np.hstack((v,
+                                          np.repeat(
+                                              true_statistics[j],
+                                              nb_missing_values + nb_zeros)))
+            else:
+                X_true[:, j] = np.hstack((v,
+                                          z,
+                                          np.repeat(true_statistics[j],
+                                                    nb_missing_values)))
+
+            # Shuffle them the same way
+            np.random.RandomState(j).shuffle(X[:, j])
+            np.random.RandomState(j).shuffle(X_true[:, j])
+
+        # Mean doesn't support columns containing NaNs, median does
+        if strategy == "median":
+            cols_to_keep = ~np.isnan(X_true).any(axis=0)
+        else:
+            cols_to_keep = ~np.isnan(X_true).all(axis=0)
+
+        X_true = X_true[:, cols_to_keep]
+
+        _check_statistics(X, X_true, strategy,
+                          true_statistics, test_missing_values)
+
+
+def test_imputation_median_special_cases():
+    # Test median imputation with sparse boundary cases
+    X = np.array([
+        [0, np.nan, np.nan],  # odd: implicit zero
+        [5, np.nan, np.nan],  # odd: explicit nonzero
+        [0, 0, np.nan],    # even: average two zeros
+        [-5, 0, np.nan],   # even: avg zero and neg
+        [0, 5, np.nan],    # even: avg zero and pos
+        [4, 5, np.nan],    # even: avg nonzeros
+        [-4, -5, np.nan],  # even: avg negatives
+        [-1, 2, np.nan],   # even: crossing neg and pos
+    ]).transpose()
+
+    X_imputed_median = np.array([
+        [0, 0, 0],
+        [5, 5, 5],
+        [0, 0, 0],
+        [-5, 0, -2.5],
+        [0, 5, 2.5],
+        [4, 5, 4.5],
+        [-4, -5, -4.5],
+        [-1, 2, .5],
+    ]).transpose()
+    statistics_median = [0, 5, 0, -2.5, 2.5, 4.5, -4.5, .5]
+
+    _check_statistics(X, X_imputed_median, "median",
+                      statistics_median, 'NaN')
+
+
+def test_imputation_most_frequent():
+    # Test imputation using the most-frequent strategy.
+    X = np.array([
+        [-1, -1, 0, 5],
+        [-1, 2, -1, 3],
+        [-1, 1, 3, -1],
+        [-1, 2, 3, 7],
+    ])
+
+    X_true = np.array([
+        [2, 0, 5],
+        [2, 3, 3],
+        [1, 3, 3],
+        [2, 3, 7],
+    ])
+
+    # scipy.stats.mode, used in Imputer, doesn't return the first most
+    # frequent as promised in the doc but the lowest most frequent. When this
+    # test will fail after an update of scipy, Imputer will need to be updated
+    # to be consistent with the new (correct) behaviour
+    _check_statistics(X, X_true, "most_frequent", [np.nan, 2, 3, 3], -1)
+
+
+def test_imputation_pipeline_grid_search():
+    # Test imputation within a pipeline + gridsearch.
+    pipeline = Pipeline([('imputer', Imputer(missing_values=0)),
+                         ('tree', tree.DecisionTreeRegressor(random_state=0))])
+
+    parameters = {
+        'imputer__strategy': ["mean", "median", "most_frequent"],
+        'imputer__axis': [0, 1]
+    }
+
+    l = 100
+    X = sparse_random_matrix(l, l, density=0.10)
+    Y = sparse_random_matrix(l, 1, density=0.10).toarray()
+    gs = GridSearchCV(pipeline, parameters)
+    gs.fit(X, Y)
+
+
+def test_imputation_pickle():
+    # Test for pickling imputers.
+    import pickle
+
+    l = 100
+    X = sparse_random_matrix(l, l, density=0.10)
+
+    for strategy in ["mean", "median", "most_frequent"]:
+        imputer = Imputer(missing_values=0, strategy=strategy)
+        imputer.fit(X)
+
+        imputer_pickled = pickle.loads(pickle.dumps(imputer))
+
+        assert_array_almost_equal(
+            imputer.transform(X.copy()),
+            imputer_pickled.transform(X.copy()),
+            err_msg="Fail to transform the data after pickling "
+            "(strategy = %s)" % (strategy)
+        )
+
+
+def test_imputation_copy():
+    # Test imputation with copy
+    X_orig = sparse_random_matrix(5, 5, density=0.75, random_state=0)
+
+    # copy=True, dense => copy
+    X = X_orig.copy().toarray()
+    imputer = Imputer(missing_values=0, strategy="mean", copy=True)
+    Xt = imputer.fit(X).transform(X)
+    Xt[0, 0] = -1
+    assert_false(np.all(X == Xt))
+
+    # copy=True, sparse csr => copy
+    X = X_orig.copy()
+    imputer = Imputer(missing_values=X.data[0], strategy="mean", copy=True)
+    Xt = imputer.fit(X).transform(X)
+    Xt.data[0] = -1
+    assert_false(np.all(X.data == Xt.data))
+
+    # copy=False, dense => no copy
+    X = X_orig.copy().toarray()
+    imputer = Imputer(missing_values=0, strategy="mean", copy=False)
+    Xt = imputer.fit(X).transform(X)
+    Xt[0, 0] = -1
+    assert_array_almost_equal(X, Xt)
+
+    # copy=False, sparse csr, axis=1 => no copy
+    X = X_orig.copy()
+    imputer = Imputer(missing_values=X.data[0], strategy="mean",
+                      copy=False, axis=1)
+    Xt = imputer.fit(X).transform(X)
+    Xt.data[0] = -1
+    assert_array_almost_equal(X.data, Xt.data)
+
+    # copy=False, sparse csc, axis=0 => no copy
+    X = X_orig.copy().tocsc()
+    imputer = Imputer(missing_values=X.data[0], strategy="mean",
+                      copy=False, axis=0)
+    Xt = imputer.fit(X).transform(X)
+    Xt.data[0] = -1
+    assert_array_almost_equal(X.data, Xt.data)
+
+    # copy=False, sparse csr, axis=0 => copy
+    X = X_orig.copy()
+    imputer = Imputer(missing_values=X.data[0], strategy="mean",
+                      copy=False, axis=0)
+    Xt = imputer.fit(X).transform(X)
+    Xt.data[0] = -1
+    assert_false(np.all(X.data == Xt.data))
+
+    # copy=False, sparse csc, axis=1 => copy
+    X = X_orig.copy().tocsc()
+    imputer = Imputer(missing_values=X.data[0], strategy="mean",
+                      copy=False, axis=1)
+    Xt = imputer.fit(X).transform(X)
+    Xt.data[0] = -1
+    assert_false(np.all(X.data == Xt.data))
+
+    # copy=False, sparse csr, axis=1, missing_values=0 => copy
+    X = X_orig.copy()
+    imputer = Imputer(missing_values=0, strategy="mean",
+                      copy=False, axis=1)
+    Xt = imputer.fit(X).transform(X)
+    assert_false(sparse.issparse(Xt))
+
+    # Note: If X is sparse and if missing_values=0, then a (dense) copy of X is
+    # made, even if copy=False.


Code review comments:
diff_hunk: @@ -60,6 +61,8 @@ def _most_frequent(array, extra_value, n_repeat):
             return extra_value
 
 
+@deprecated("Imputer was deprecated in version 0.20 and will be "
+            "removed in 0.22. Import Imputer from sklearn instead.")
path: sklearn/preprocessing/imputation.py
text: @user1:
sklearn.impute

diff_hunk: @@ -480,7 +480,7 @@ General Concepts
 
     missing values
         Most Scikit-learn estimators do not work with missing values. When they
-        do (e.g. in :class:`preprocessing.Imputer`), NaN is the preferred
+        do (e.g. in :class:`Imputer`), NaN is the preferred
path: doc/glossary.rst
text: @user1:
This still needs to be impute.Imputer