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