[GitHub] spark pull request: [SPARK-5688] Randomize splits for categorical ...

[srowen <gi...@git.apache.org>]

Github user srowen commented on the pull request:

    https://github.com/apache/spark/pull/4475#issuecomment-73542338
  
    (Add `[MLLIB]` after `SPARK-5688` in the title?)
    
    I think there is an issue here, but maybe a simpler solution in the short term. Since you can't test all 2^n - 2 possible splits, I'm accustomed to sorting the categorical values according to some heuristic. E.g. for regression: sort by mean value of the target for each category; I think the PLANET paper even said that was guaranteed to contain the optimal split. Then you only consider the n-1 splits that are prefixes of this sorted list. For example if the category values were `b d c a` then you'd consider splits `b`, `b d`, `b d c`
    
    The current logic considers something like `a`, `b`, `a b`, `c`, `a c`, ... which is indeed very biased. Better would be to try `a`, `b`, `c` or `a`, `a b`, `a b c`, ... If evaluating fewer than n-1 bins, then you could pick randomly from among these choices. I think those are a priori no better or worse than truly choosing at random from all possible subsets, and might be simpler in code, and, might lend itself more directly to the heuristic later.
    
    @jkbradley can weigh in. I may have missed something about how the impl works now.


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---

---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org