arXiv:2403.19867v4 宣告类型: replace-cross 摘要: 在这项工作中，我们提出了数据流算法来计算决策树学习中的最优分割。特别地，给定一系列观测值 \(x_i\) 及其相应的标签 \(y_i\) 的数据流，不考虑独立同分布假设，目标是识别出能最小化均方误差（对于回归任务）或错误分类率和基尼不纯度（对于分类任务）的最优分割 \(j\)。我们提出了几种高效的流算法，这些算法需要亚线性空间，并且只需要少量遍历来解决这些问题。这些算法还可以扩展到MapReduce模型。我们的结果，虽然不直接可比，但补充了Domingos-Hulten (KDD 2000) 和 Hulten-Spencer-Domingos (KDD 2001) 的开创性工作。