数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究什么是霍夫丁树算法？
霍夫丁树算法是一种用于流数据分类的决策树学习方法。它最初用于跟踪网络点击流并构建模型以预测用户可能访问哪些网络主机和网站。它通常以次线性时间运行，并生成与传统批量学习者生成的决策树几乎相同的决策树。
它使用霍夫丁树，该树利用这样的思想：一个小样本通常足以选择最佳分割属性。霍夫丁界（或加性切尔诺夫界）在数学上支持了这一思想。
假设我们对范围为R的随机变量r进行N次独立观察，其中r是一个属性选择度量。（对于概率，R为1，对于信息增益，它为log c，其中c是类的数量。）在霍夫丁树的情况下，r是信息增益。如果我们计算该样本的均值r’，则霍夫丁界指出，r的真实均值至少为r’−ε，概率为1−δ，其中δ是用户指定的，并且
$$\varepsilon=\sqrt{\frac{R^{2}ln\frac{1}{\delta}}{2N}} $$
霍夫丁树算法使用霍夫丁界来确定在选择分割属性时，在节点处需要满足高概率的最小示例数N。与大多数其他界限方程不同，霍夫丁界与概率分布无关。这是可取的，因为可能无法知道信息增益或使用的任何属性选择度量的概率分布。
该算法以属性A描述的一系列训练示例S和精度参数δ作为输入。提供评估函数G(Ai)，它可以是信息增益、增益率、基尼指数或其他一些属性选择度量。在决策树中的每个节点处，我们需要针对剩余属性Ai中的一个最大化G(Ai)。目标是找到满足霍夫丁界的最小元组数N。
该算法以属性A描述的一系列训练示例S和精度参数δ作为输入。提供评估函数G(Ai)，它可以是信息增益、增益率、基尼指数或其他一些属性选择度量。在决策树中的每个节点处，我们需要针对剩余属性Ai中的一个最大化G(Ai)。目标是找到满足霍夫丁界的最小元组数N。
对于给定节点，令Aa为达到最高G的属性，Ab为达到第二高G的属性。如果G(Aa) − G(Ab) > ε，其中ε是计算出来的。
霍夫丁树算法中必须维护的唯一统计数据是属性Ai的值vj与类标签yk的计数nijk。因此，如果d是属性的数量，v是任何属性的最大值的数量，c是类的数量，l是树的最大深度（或层数），则所需的总内存为O(ldvc)。
4K+ 浏览量
