Coverage decreased (-0.04%) when pulling cc3eb48 on MatthieuBizien:categorical_split into 1775095 on scikit-learn:master.

Each feature could have up to 32 classes, because we will have to test all the combinaisons, so 2**31 cases.

Can you explain this part a bit more? You're testing all permutations of subsets of the data?

Yes, I have to test all permutations. Because of the symmetry of the problem, without any loss of generality, we can assume the first class is in the left leaf, so we have to test 2**31 cases in the worst case (i.e. 32 classes), and not 2**32.

2**31 is a lot, but it is still computable, and it is the worst case, when the user provide 32 classes. If the number of classes is less important, or if the tree had already been split on this feature, the complexity would be less important. I assume that for most real world cases, the number of classes will be small.

We can imagine some heuristics if we have many classes (it is "just" discrete optimization), but it is, I think, too soon.

Do you have any thoughts on how you'd handle the case when the user provides more than 32 categories? I'm thinking of my own work where almost everything has more than 32 categories (e.g. country or postal codes)

At the beginning, I think it is easier not to handle that case, to raise an exception and to ask the user to use dummy variables. When this pull request will be working and merged, it will be possible to start working on heuristics for finding the best split, without testing all combinaisons. I am not a specialist of discrete optimization, but I am sure there are efficient algorithms for that. The underlying structure will also need to be different because we will no longer be able to store a split in an int32.

Contrary to many algorithms, that can only use dummy variables, decision
trees can behave differently for categorical data.

The expressive power of the tree is identical whether or not these are
handled specially. As far as I can tell the difference by introducing such
a feature is that it can drastically affect max_depth criteria, etc.

On 11 July 2014 06:57, MatthieuBizien notifications@github.com wrote:

At the beginning, I thing it is easier not to handle that case, to raise
an exception and to ask the user to use dummy variables. When this pull
request will be working and merged, it will be possible to start working on
heuristics for finding the best split, without testing all combinaisons. I
am not a specialist of discrete optimization, but I am sure there are
efficient algorithms for that. The underlying structure will also need to
be different, because we will no longer be able to store a split in an
int32.

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

The expressive power of the tree is identical whether or not these are
handled specially.

Not exactly. By assuming numerical features, we assume that categorical features are ordered, which restricts the sets of candidate splits and therefore the expressive power of the tree (for a finite learning set).

Thanks for you contribution @MatthieuBizien !

A few comments though before you proceed further:

• The API for this has already been subject to debate. We have never settled to something that pleases everyone. I would like to hear some core developers opinion on the proposed API? As I understand, the interface is here similar to what we already have for OneHotEncoder. CC: @ogrisel @larsmans @jnothman @GaelVaroquaux
• In terms of algorithms.
  i) 2**31 is way too large. In R, they restrict the number of combinations to 2**8. If the number of categories is larger, then 2**8 combinations are sampled at random.
  ii) In binary classification or in regression, there exists an optimal linear algorithm for finding the best split. It basically boils down to replace the categories by their probability, use these probabilities as a new ordered feature and apply the usual algorithm for finding the best split. You can find details about this in Section 3.6.3.2 of http://orbi.ulg.ac.be/handle/2268/170309

In terms of internal interface, this may also be the opportunity to try to factor out code from Splitters. What is your opinion on this @arjoly ?

@glouppe You're welcome. Thanks for your advices in term of algorithm, I will use that.

In terms of internal interface, this may also be the opportunity to try to factor out code from Splitters. What is your opinion on this @arjoly ?

Yeah, this would a great opportunity. This could already be done outside this pull request.

Not exactly. By assuming numerical features, we assume that categorical
features are ordered, which restrict the sets of candidate splits and
therefore the expressive power of the tree.

(But assuming infinite depth is allowed, the expressiveness is identical.)

On 11 July 2014 20:51, MatthieuBizien notifications@github.com wrote:

@glouppe https://github.com/glouppe You're welcome. Thanks for your
advices in term of algorithm, I will use that.

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

On 07/12/2014 11:26 AM, jnothman wrote:

Not exactly. By assuming numerical features, we assume that categorical
features are ordered, which restrict the sets of candidate splits and
therefore the expressive power of the tree.

(But assuming infinite depth is allowed, the expressiveness is
identical.)

Yes. But even then, the resulting decision surface would most likely not
be the same.

I'm enthusiastic about this feature. One usecase is to do hyper-parameter optimization (as in hyperopt) over categorical hyper-parameters.

Note that pandas 0.15 will have a native data type for categories encoding:

http://pandas-docs.github.io/pandas-docs-travis/whatsnew.html#categoricals-in-series-dataframe

We could make the decision trees able to deal with dataframe features natively. That would make it more natural to use for the user: no need to pass a feature mask.

However that would require some refactoring to support lazy, per-column __array__ conversion instead of doing it globally for the whole datafreame in the check_X_y call.

Yes. But even then, the resulting decision surface would most likely not be the same.

Also it would make the graphical export of a single decision tree much easier to understand. Many users are interested by the structure of the learned trees when applied to categorical data.

totally - the same applies to partial dependence plots as well

2014-08-13 16:25 GMT+02:00 Olivier Grisel notifications@github.com:

Yes. But even then, the resulting decision surface would most likely not
be the same.

Also it would make the graphical export of a single decision tree much
easier to understand. Many users are interested by the structure of the
learned trees when applied to categorical data.

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

Peter Prettenhofer

Hello,

It seems like there hasn't been development on this PR in awhile. Is there any idea of how far it is from completion? I would love to use it.

^ +1

Thanks,
Michael J. Bommarito II, CEO
Bommarito Consulting, LLC
Web: http://www.bommaritollc.com
Mobile: +1 (646) 450-3387

On Tue, Apr 28, 2015 at 10:52 AM, spitz-dan-l notifications@github.com
wrote:

Hello,

It seems like there hasn't been development on this PR in awhile. Is there
any idea of how far it is from completion? I would love to use it.

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

I think this is a somewhat significant addition, and it doesn't look like anyone worked on it recently. I think most sklearn people are excited about it, but no-one had the time to work on it. Help welcome.

I don't have time to work on it for the moment. It wasn't so for away from completeness, but there had been some major changes in the master code.

+1 for this. Especially in combination with the pandas categorial data type

I am 90% certain that the input will not be the pandas categorical data type, at least in the first iteration. I'm sure @GaelVaroquaux has opinions about this ^^

Some people might argue that a dataframe is a much better common denominator, as mixed datatypes are the norm, and homogeneous datatypes are a special case that only appears in some obscure imaging techiques ;)

Hi,
I was wondering if there was any progress on the issue of telling a Decision Tree (or Ensemble) which features are categorical so it can split differently than numerical?

#4899 is the latest news

On 31 March 2016 at 22:06, Eyal notifications@github.com wrote:

Hi,
I was wondering if there was any progress on the issue of telling a
Decision Tree (or Ensemble) which features are categorical so it can split
differently than numerical?

—
You are receiving this because you were mentioned.
Reply to this email directly or view it on GitHub
#3346 (comment)

I have been working on fairly large (millions of rows) problems with features that have large numbers (1000's) of categories. H2O is working pretty well but I would greatly prefer to stick with scikit-learn only.

I believe that H2O is using the algorithm described in A Streaming Parallel Decision Tree Algorithm. I am thinking it would probably be easier to add SPDT rather than modify random forest.

Should this be closed in favor of continuing the discussion in #4899 ?

I suppose so.

Just checking in to see if there is any progress on this issue?

Any update on this issue?

Hi everyone, I was not able to work on that PR for a long time, and when I went back there were a lot of things had have changed in the Scikit-learn codebase. I also have less available time than when I started the PR, so I have to stop here. You can use catboost, wait for #12866 (or try to continue where I left 😉).