Finding Decision Tree Splits in Streaming and Massively Parallel Models

arXiv:2403.19867v1 Announce Type: cross
Abstract: In this work, we provide data stream algorithms that compute optimal splits in decision tree learning. In particular, given a data stream of observations $x_i$ and their labels $y_i$, the goal is to find the optimal split point $j$ that divides the data into two sets such that the mean squared error (for regression) or misclassification rate (for classification) is minimized. We provide various fast streaming algorithms that use sublinear space and a small number …

abstract algorithms arxiv compute cs.ai cs.ds cs.lg data data stream decision labels split streaming tree type work