Reference Issues/PRs

Supersedes #12866 #4899 and #7068 , #3346

What does this implement/fix? Explain your changes.

Implements splitting rules when categorical data is given in a decision tree classifier/regressor.

• Tree data structures are moved to maintain the cimport/import sequence (ParentInfo, SplitRecord, Node) -> _utils.pxd
• Adds partitioning of samples given a category (this complements nicely the partitioning of samples given a numerical threshold)
• Adds splitting logic given a category
• Adds a bitset cache (i.e. a uint64_t memory view) that allows us to compute the category split as we traverse the tree

Open Questions / TODO

1. Should breiman_shortcut be part of Splitter? It is completely unused by RandomSplitter, so it seems weird to pass in an argument that is unnecessary. Otoh, if we specialize the breiman_shortcut only for BestSplitter, then we need to also specialize how breiman_shortcut is passed in BaseDecisionTree.
2. Add unit-testing for splitting on categories vs one-hot-encoder -> shallower trees for 8 categories
3. Understand the bitset operations and merge these with the HistGradientBoosting bitset operations
4. benchmark experiments to determine splitting on categories vs not in terms of fit time, accuracy, etc.

Any other comments?

May be related to #24967

Would be nice to merge in #29458

Notes:

1. breiman_shortcut should either be in only BestSplitter, or a special method of the Partitioner, or even a private function, which is optionally used. It's a private method for use during splitting, so maybe not part of Partitioning.
2. I think we can enable support for Sparse categories in the next PR
3. Perhaps information about categories should be passed from parent node since the Tree technically has information about the n_categories, so we can trim down the number of categories. I think this can be implemented last and then benchmarked to determine if this optimization is useful or not. I suspect it is since for categorical splits, there is time involved to "count the unique categories", which seems unnecessary. This is conceptually similar to tracking constant features