{"action":"created","issue":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/4899","repository_url":"https://api.github.com/repos/scikit-learn/scikit-learn","labels_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/4899/labels{/name}","comments_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/4899/comments","events_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/4899/events","html_url":"https://github.com/scikit-learn/scikit-learn/pull/4899","id":91037873,"number":4899,"title":"NOCATS: Categorical splits for tree-based learners","user":{"login":"jblackburne","id":7388984,"avatar_url":"https://avatars.githubusercontent.com/u/7388984?v=3","gravatar_id":"","url":"https://api.github.com/users/jblackburne","html_url":"https://github.com/jblackburne","followers_url":"https://api.github.com/users/jblackburne/followers","following_url":"https://api.github.com/users/jblackburne/following{/other_user}","gists_url":"https://api.github.com/users/jblackburne/gists{/gist_id}","starred_url":"https://api.github.com/users/jblackburne/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jblackburne/subscriptions","organizations_url":"https://api.github.com/users/jblackburne/orgs","repos_url":"https://api.github.com/users/jblackburne/repos","events_url":"https://api.github.com/users/jblackburne/events{/privacy}","received_events_url":"https://api.github.com/users/jblackburne/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":69,"created_at":"2015-06-25T18:15:47Z","updated_at":"2016-05-29T20:10:58Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/4899","html_url":"https://github.com/scikit-learn/scikit-learn/pull/4899","diff_url":"https://github.com/scikit-learn/scikit-learn/pull/4899.diff","patch_url":"https://github.com/scikit-learn/scikit-learn/pull/4899.patch"},"body":"NOCATS stands for \"Near-Optimal Categorical Algorithm Technology System\". (What can I say? My coworker came up with it.) It adds support for categorical features to tree-based learners (e.g., `DecisionTreeRegressor` or `ExtraTreesClassifier`).\r\n\r\nThis PR is very similar to #3346, but allows for more categories, particularly with extra-randomized trees (see below).\r\n\r\n### How it works ###\r\n\r\nWe've replaced the threshold attribute of each node (a `float64`) with a union datatype containing a `float64 threshold` field and a `uint64 cat_split` field. When splitting on non-categorical features, we use the `threshold` field and everything works as before.\r\n\r\nBut when a feature is marked as categorical, the `cat_split` field is used instead. In a decision tree, each of its 64 bits indicates which direction a certain category goes; this implies a hard maximum of 64 categories in any feature. Which is fine, because finding the best way to split 64 categories during the tree-building step is very expensive, and the practical limit will certainly be less than 64.\r\n\r\nIn an extra-randomized tree, however, the expensive process of finding the very best split is bypassed, so it would be nice to allow more categories. So for these trees we use `cat_split` in a completely different way: when building the tree we randomly choose a set of categories to go left, then store only the minimum information needed to regenerate that set during tree evaluation. The information that we store is a random seed (in the most significant 32 bits) ~~and the number of draws to perform (in the next 31 bits)~~ \\[Edit: We now flip a virtual coin for each category, so the number of draws is no longer necessary\\]. By recreating the split information as needed in each node rather than storing it explicitly, we are able to support large numbers of categories without causing the classifiers to balloon in size.\r\n\r\nHow does a tree know which type it is? We encode that information in the least significant bit of `cat_split`. If the LSB is 0, we treat it as a flag field; if it is 1, we treat it as a random seed and number of draws. We do not lose generality by forcing category 0 to always go right, since there is a left-right symmetry.\r\n\r\nOne last detail: to avoid regenerating the random split for every sample during tree evaluation, we allocate a temporary buffer for each node large enough to serve as a bit field. The buffers are freed when evaluation finishes.\r\n\r\n### How to use it ###\r\n\r\nThe `fit` method of the relevant learners has a new optional parameter `categorical`. You can give it an array of feature indices, a boolean array of length `n_features`, or the strings `'None'` (the default) or `'All'`. Categorical feature data will be rounded to the nearest integer, then those integers will serve as the category labels. (Internally they are mapped to `range(n_categories)`).\r\n\r\n### Comments, caveats, etc. ###\r\n\r\n1. ~~`RandomSplitter` generates a random categorical split by first generating a random seed, then generating a number of draws to make. To simulate flipping a coin for each category, the number of draws should come from a Binomial distribution, but currently we use a uniform distribution. I welcome comments on how desirable it would be to change this into a Binomial draw.~~ \\[Edit: `RandomSplitter` now sends each category left or right using a simple coin flip. This is equivalent to the Binomial draw.\\]\r\n\r\n2. When building the tree, each node generates its split using the full set of categories for the feature in question rather than the subset of categories represented by the node's samples. For the `BestSplitter`s, this means it will take longer to find the split. For the `RandomSplitter`, it means there is a chance that the current subset will all be sent in the same direction. This contrasts with the non-categorical behavior, where a non-trivial split is guaranteed for non-constant features. The chance is generally small (and it's smaller if we use a Binomial draw rather than a uniform draw). I made this choice because it would introduce a lot of new complexity and storage requirements to split based on the current subset of categories. ~~One alternative would be to have the `RandomSplitter` generate random splits until a non-trivial split is achieved.~~ \\[Edit: This is now implemented. Random splits are generated until a non-trivial split is found, or until a maximum of 20 tries (to limit the worst case runtime). This change renders this whole bullet point essentially meaningless aside from runtime speed considerations.\\] Comments on this are also welcome.\r\n\r\n3. Categorical features are not supported for sparse inputs. This is because I did most of this work before the support for sparse inputs was added, and I am not as familiar with that part of the code. Plus, it seems that sparse inputs become less necessary when you are not using one-hot encoding."},"comment":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/comments/222380115","html_url":"https://github.com/scikit-learn/scikit-learn/pull/4899#issuecomment-222380115","issue_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/4899","id":222380115,"user":{"login":"raghavrv","id":9487348,"avatar_url":"https://avatars.githubusercontent.com/u/9487348?v=3","gravatar_id":"","url":"https://api.github.com/users/raghavrv","html_url":"https://github.com/raghavrv","followers_url":"https://api.github.com/users/raghavrv/followers","following_url":"https://api.github.com/users/raghavrv/following{/other_user}","gists_url":"https://api.github.com/users/raghavrv/gists{/gist_id}","starred_url":"https://api.github.com/users/raghavrv/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/raghavrv/subscriptions","organizations_url":"https://api.github.com/users/raghavrv/orgs","repos_url":"https://api.github.com/users/raghavrv/repos","events_url":"https://api.github.com/users/raghavrv/events{/privacy}","received_events_url":"https://api.github.com/users/raghavrv/received_events","type":"User","site_admin":false},"created_at":"2016-05-29T20:10:57Z","updated_at":"2016-05-29T20:10:57Z","body":"I think he would be able to help you with it. Something similar to that was done recently in another PR..."}}
{"actor":{"display_login":"raghavrv"}}