Fork me on GitHub

在线随机森林代码解析

在线随机森林(ORF)[1]给出了一种基于数据流来不断更新的决策模型。它主要面向目标追踪任务,并能提供并行,易于理解的,与离线随机森林性能相近的二元分类模型。为了适配连续型的标记,我阅读了ORF的源码[2]并给出我阅读的心得。我从main开始读起,记录了某些关键行的意思。

有意思的是ORF并没有按RF算法来写,RF中test的数量应该等于随机选择的特征数X特征的值的数量。 而在ORF中,作者设定了test的数量,它随机的选择一个特征,以这个特征最大最小值之间的一个随机值作为分割的值。使用者可以设定test的数量,比如10000,这样来得到尽可能多的test。用这种方式可以避免每加进来一个样本就要建立一个新的test的麻烦,也算是online方法的一种改进。

  1. OMCBoost.cpp::main
    1. 57-110 , 参数处理
    2. 111,读取配置文件为hp
    3. 112-127,读取数据集
    4. 128-157,根据hp初始化模型
    5. 158-168,训练与测试模型
    6. 169-174,结束
  2. 【1.4】Online_rf.cpp::OnlineRF::OnlineRF
    1. 初始化对象参数
    2. 根据hp初始化树,初始化树时初始化根节点,初始化根节点时会初始化10000个random test
  3. 【1.5】experimenter.cpp::train
    1. 20-22,计时部分
    2. 23-25,声明随机索引,每次训练的样本比例和训练误差
    3. 26-45,进入周期loop与样本loop进行模型的建立
      a. 27,建立随机的样本索引,即打乱样本顺序
      b. 29-36,计算模型的训练误差。用当前模型评估当前样本的结果,如果结果与真实值不符则训练误差加1
      c. 37,用当前样本更新模型
      d. 38-49,输出训练误差与总时间
  4. 【3.3.c】 online_rf.cpp:OnlineRF::update [gdb: b OnlineRF::update]
    1. 219-223,RF样本数+1,初始化样本结果变量,树结果变量和样本更新次数
    2. 224-230,进入tree loop,使用poisson分布,确定样本在这棵树中的更新次数
    3. 231-239,如果更新次数大于0,则用当前样本更新树,如更新次数小于0,则样本用于计算树的OOBE
    4. 240-246,为样本在各树的OOBE求和得到RF的OOBE
  5. 【4.3】 online_rf.cpp::OnlineTree::update -> online_rf.cpp::OnlineNode::update
    1. 100-101,节点样本数+1,节点正/负样本数+1
    2. 103-139,判断是否为叶子节点,若是则
      a. 104-108,使用当前样本更新这个节点的所有test
      b. 110,更新节点label
      c. 113,判断节点是否达到online split的条件
      d. 114,达到split条件之后,先将叶子结果标记改为false.
      e. 116-126,遍历所有的test结果,找到score最小的test作为最优test
      f. 127-131,删除节点其它test,只保留最优test.
      g. 134-139,建立子节点并将父节点的统计结果分成子节点
    3. 140-146,如果不是叶子节点,就根据当前节点的最优test判断样本应该去左节点还是右节点,并将样本分到子节点中去update。
  6. 【2.2 + 5.2.a】online_rf.cpp:RandomTest::RandomTest/update/score
    1. 17-20,每个test随机选择一个特征,选择这个特征最大最小值之间的随机值作为特征的值
    2. 30,每个新来的样本只会影响test的结果,不会新加test.
    3. 34-49,使用gini index来计算若基于此split后的左右子节点的纯度加权和。选择纯度最小的那个进行split越可

[1] A. Saffari, C. Leistner, J. Santner, M. Godec, and H. Bischof. On-line Random Forests. In 12th International Conference on Computer Vision Workshops (ICCV), pp. 1393–1400, 2009.
[2] OnlineForest-0.11.tar.gz, http://www.ymer.org/amir/software/online-random-forests

No pain, No gain