什么是 Hoeffding 树算法？
Hoeffding树算法是一种用于流数据分类的决策树学习方法。它最初用于跟踪Web点击流并构建模型来预测用户可能访问哪些Web主机和网站。它通常在次线性时间内运行，并产生与传统批量学习器几乎相同的决策树。
它使用Hoeffding树，它利用小样本通常足以选择最佳分裂属性的想法。这个想法在数学上得到了Hoeffding界（或加性Chernoff界）的支持。
假设我们对范围为R的随机变量r进行N次独立观察，其中r是属性选择度量。（对于概率，R是1，对于信息增益，它是logc，其中c是类的数量。）在Hoeffding树的情况下，r是信息增益。如果我们计算此样本的均值r'，则Hoeffding界限表明r的真实均值至少为r'−ε，概率为1−δ，其中δ是用户指定的，并且
$$\varepsilon=\sqrt{\frac{R^{2}ln\frac{1}{\delta}}{2N}}$$
HoeffdingTree算法使用Hoeffding界来以高概率确定选择拆分属性时节点所需的最小示例数N。与大多数其他边界方程不同，Hoeffding边界与概率分布无关。这是可取的，因为可能无法知道信息增益的概率分布，或使用任何属性选择度量。
该算法将一系列训练示例S（由属性A描述）和准确度参数δ作为输入。提供了评估函数G(Ai)，它可以是信息增益、增益比、基尼指数或其他一些属性选择度量。在决策树中的每个节点，我们需要最大限度地提高G（A我）对剩余的属性之一，A我。目标是找到满足Hoeffding界限的最小元组数N。
该算法将一系列训练示例S（由属性A描述）和准确度参数δ作为输入。提供了评估函数G(Ai)，它可以是信息增益、增益比、基尼指数或其他一些属性选择度量。在决策树中的每个节点，我们需要最大限度地提高G（A我）对剩余的属性之一，A我。目标是找到满足Hoeffding界限的最小元组数N。
对于给定节点，设Aa为达到最高G的属性，而Abbe为达到第二高G的属性。如果G(Aa)−G(Ab)>ε，则计算ε。
在Hoeffding树算法中必须维护的唯一统计数据是具有类标签yk的属性Ai的值vj的计数nijk。因此，如果d是属性数，v是任何属性的最大值数，c是类数，l是树的最大深度（或级别数），那么所需的总内存是O(ldvc)。