IARF分类器，构造了一个包含多棵决策树的集合，IARF分类器中每棵决策树即为增量超树。每棵增量超树采用增量随机森林分类器（IRF）的设计基本思想，基于训练样本集合，采用传统的自上而下的方式进行构造。

4.6.5.1　构造单棵增量超树

构造单棵增量超树的算法见算法1.

算法1.构造增量超树（s，i）。

输入：一个训练样本s，树索引。

输出：增量超树ti。

（1）if增量超树ti的根节点不存在；

（2）生成一个新的叶节点R，该叶子节点标记值为训练样本s的标记值；

（3）返回一个根节点为R的决策树ti；

（4）end if；

（5）样本s经超树分类后落到叶节点L上；

（6）存储样本s到叶节点L的样本列表中；

（7）更新叶节点L上所有样本类别的数量；

（8）if类别纯度系数G＞Split thresholdΔ；

（9）产生一个新的树节点T，T为构造一棵新的子增量超树；

（10）if L是根节点，则将T作为新的根节点；

（11）else将T替换掉L，作为PL的子节点，其中PL是L的父节点；

（12）end if；

（13）删除叶节点L；

（14）end if；

（15）返回增量超树ti。

增量超树中的每个叶节点都维护一个样本列表，用来存储分类到该叶节点上的样本，同时统计当前该叶节点上所有样本标记值的数量分布。当一个新的训练样本到达时，首先经过当前的增量超树分类，到达某一叶节点后被存储到该叶节点上的样本列表中，同时该样本对应的类别标记总数加1。选择存储样本的原因是在后续过程中可以重复利用这些已获知的样本，用来进行增量超树的构造和扩展，即便是在获得很少样本的情况下仍然可以有效地构造增量超树。当叶节点上存储的样本集合到达一定的混乱程度后，即对当前叶节点进行分裂，构造新的决策节点和相应的后继叶节点，从而达到扩展生长整个增量超树的目的。所有增量超树各树节点的构造和扩展都是相互独立的。

4.6.5.2　子增量超树（子决策树）构造

当叶节点上的类别纯度系数G超出了设定的阈值区域时，我们即认为当前叶节点上的样本集合达不到要求的纯度，或被认为样本集合的混乱程度达到给定的上限，这时需要分裂当前叶节点，利用存储的样本构造新的子增量超树。子增量超树构造过程见算法2。

当有新的叶节点生成时，在当前叶节点上构造一个样本列表，统计并存储样本信息。当一个叶节点分裂时，按照该决策树的随机属性序列排序选取决策属性，同时构造一个新的决策节点并生成相应的后继叶节点。分裂前的叶节点上存储的样本按照相应的决策属性和分裂测试进行划分，得到相应的样本子集合，分别存储到对应的新生后继叶节点上，同时对类别标记的数量重新统计。随着时间推移，叶节点上存储的样本会逐渐增多，这样既会造成过重的空间负载，又会存在分类器对数据描述不够准确的隐患。为此，我们采用Least－Recent－Used替换策略来减少陈旧的样本，着重关注当前的样本，在算法的实现过程中，每个样本被赋予一个时间戳，当样本的时间戳小于给定时刻，即被丢弃。

算法2.构造子增量超树（S）。

输入：输入数据流窗口数据分裂集合S＝I1∪I2，其中I1为带类标记数据集，I2为不带类标记数据集，I1∩I2＝φ，以I1为样本训练集。

输出：增量超树t

（1）if：（Ⅰ）｜I1｜＜nmin，nmin为设定的小样本数，or

①I1中所有的候选属性都不变，or(www.daowen.com)

②I1中所有的输出变量都一致

（2）生成一个新的叶节点t。

（3）存储I1中所有样本在节点t上。

（4）统计I1中所有类别标记的数量分布并存储在节点t。

（5）返回叶节点t，t对应的标记值根据类别标记数量来确定。

（6）else：

（7）将I1划分为两个子集Se和Sr，决策属性按该决策树的随机属性排列顺序选取。

（8）根据子集Sl和Sr分别构造子树ti为子增量超树（Si）和子树tr为子增量超树（Sr）。

（9）根据分裂测试s*生成决策节点t，将tl和tr分别作为t的左子树和右子树。

（10）end if。

（11）返回超树节点t。

4.6.5.3　构造更新增量超树

数据流概念漂移会导致决策树分类精度下降，虽然可以对叶节点进行继续分裂，形成新的子增量超树，但会造成叶节点数目过多和过深，造成产生的决策树过大。因此，更新决策树，构造适合于数据流概念漂移的决策树是一个不可缺少的环节。

算法3.构造更新增量超树。

输入：输入数据流窗口数据分裂集合带类标记数据集I1。

输出：更新增量超树t。

（1）if：增量超树（s，i）的边数＞tmax，tmax是设定的最大边数。

（2）构造更新增量超树t。

（3）更新超树t替换增量超树（s，i）。

（4）else：

（5）返回增量超树（s，i）。

（6）end if。

4.6.5.4　IARF分类器

构建N个决策树，形成增量自适应随机森林分类器。

输入新样本x，每个决策树给出分类结果，并记录每棵决策树分类结果的成绩，即对具有类标的样本记录单棵决策树（s，ti）分类结果的准确率ki（i＝1，2，…，

N）。

建立IARF分类器的投票规则。对单棵决策树（s，i）的投票结果进行加权，权值为ki。统计加权投票结果的众数，即得该样本的分类结果。

对分类成绩差，并低于规定阈值的单棵增量超树，或单棵增量超树的边数大于tmax（规定的阈值）时，将该决策树丢弃，并构建新的单棵增量超树。