In the meantime, I added deprecation warnings for the old behaviour, keywords and attributes.
(still need to update deprecation messages and the docs)

Some quick answers

Do you think this option will be useful (for efficiency, for error handling, or for quality assurance) after the deprecation is finished? If not, should it just be called legacy_mode?

See my (long) comment on the issue asking about this: #10521
Short answer: I personally don't really know if it (after deprecation) is worth its own option. Would appreciate input there (as indeed the design would change a bit then)

Does this setting affect the handling of n_values? Can one use encoded_input=True and categories together?

Good question, this is one of the things I didn't really think through yet. In principle, you can pass categories, but using the same format as for categorical input data does not make much sense (you would need to pass categories=[[0, 1, 2, 3, 4], [0, 1, 2]] for 5 and 3 categories, and we would need to check that it is consecutive range.
But changing the way to specify categories depending on encoded_input=True (eg by giving the number of categories like categories=[5, 3] like the current n_values) is also not the nicest API design (but maybe the better solution ..)

I'm sure Numpydoc doesn't handle this.

Yes I know, but wanted it to be very explicit now to see the consequences (for initial reviewing). I didn't bother yet fully updating the documentation as well.

Last commit added the logic to deal with all different case (to raise a warning or not, to use legacy mode or not). Still have to clean-up a lot, so don't review in detail, but could already take a look at _handle_deprecations method.

Test failing? Is this waiting for reviews?

This is waiting for your opinion about the general idea in #10521 (I would say, let's keep the general discussion there for now, would need to look back at this PR to know its actual status)

OK, made some small updates:

• some minor clean-up for pep8, doctests, correct cross-references (hopefully travis is happy now)
• suppressed warnings in RandomTreesEmbedding which was using a OneHotEncoder under the hood by adding a categories='auto' to that call (it is using integers, but the new behaviour should be identical in this case as the tree leave indices should be 0, 1, .. n)
• rebased for [MRG + 1] Ensuring that the OneHotEncoder outputs sparse matrix with given dtype #11034 #11042 (that dtype is honoured) and added similar tests for the new OneHotEncoder (which already passed)

@jnothman @amueller can we try to move this forward to include in the release?

I'm happy with it as it is iirc

I am also ok with deprecating categorical_features and delegate feature dispatching to ColumnTransformer. We can always revise that decision later.

I would also introduce a stub CategoricalEncoder class that raises a TypeError in its constructor with explicit error message telling to use OneHotEncoder.

Even if CategoricalEncoder was never part of a public scikit-learn release, I am affraid that is was already mentionned in several blog posts and even in a revised version of @ageron's book who we had the pleasure to chat with today. In @ageron's book there was a warning that it was an unreleased experimental feature but better be nice with the users and introduce that stub to help them upgrade their code quickly.

This PR doesn't yet remove CategoricalEncoder.

I'm okay with Olivier's suggestion:

class CategoricalEncoder:
    "Removed"
    def __init__(*args, **kwargs):
        raise RuntimeError('CategoricalEncoder briefly existed in 0.19dev. '
                           'Its functionality has been rolled into '
                           'OneHotEncoder and OrdinalEncoder. This stub '
                           'will be removed in version 0.21.')

The only problem I see with it is that an ImportError would warn sooner.

This PR doesn't yet remove CategoricalEncoder.

It does, but will add the stub as proposed above.

The only problem I see with it is that an ImportError would warn sooner.

Yeah, I was also thinking about that. But I don't see a way to both support from sklearn.preprocessing import CategoricalEncoder as from sklearn import preprocessing; preprocessing.CategoricalEncoder().
For the first I could add a CategoricalEncoder.py that raises an import error, but that doesn't work in the second case.

@amueller are you OK with going merging this as is? (thus, deprecating categorical_features keyword)

Great work !

nitpick: You may also want to update examples/compose/column_transformer_mixed_types.py
(done in 73b7d07)

Great work, @jorisvandenbossche!

Awesome! Thanks everyone for your work on this important change, and special thanks to @jnothman
and @ogrisel for adding the CategoricalEncoder stub, I really appreciate it. :)

yes, I'm ok with this for now ;) Thank you for all the work, this is great!