# Forgetful Forests: Data Structures for Machine Learning on Streaming Data under Concept Drift
## Appendix C Algorithms for Forgetful Random Forests  
```
Input : \(F\), all features in data data \(\mathit{MatStream}\), the \(\mathit{stream}\) of data including two components \(X\) (features) and \(Y\) (labels) \(\mathit{trees}\), the list of decision trees that are actively updated \(\mathit{allParams}\), the parameters that will be updated for each tree in \(\mathit{trees}\), including \(iRate\), \(\mathit{oddsStarup}\), \(\mathit{warmSize}\), \(\mathit{lastAcc}\), \(\mathit{lastSize}\) and \(\mathit{maxHeight}\) allConsiders, the features that will be considered for each tree in \(\mathit{trees}\) \(\boldsymbol{G}(\cdot)\), a function to score the fitness of a feature for splitting \(\boldsymbol{E}(\cdot)\), the stopping criteria, returns boolean \(nTree\), the number of decision trees that are actively updated \(\mathit{thresh}\), the threshold for discarding trees
1 begin
2\(\mathit{nTree},\mathit{thresh}\leftarrow\mathit{initial\ values}\); \(\mathit{Aco},\mathit{Size}_{0}\leftarrow\mathit{0}\); \(\boldsymbol{E}(\cdot)\leftarrow\mathit{MaximumTreeHeight}(\cdot)\) ; \(\boldsymbol{G}(\cdot)\leftarrow\mathit{Entropy}(\cdot)\); \(trees\leftarrow\) build \(\mathit{nTree}\) new decision trees; for each tree in \(\mathit{trees}\)do //Initialize \(\mathit{allConsiders}\) of each tree \(\mathit{nConsider}\gets\mathit{U}(\lfloor\sqrt{\mathit{size}(F)}\rfloor+1, \mathit{size}(F))\) ; // \(\mathit{U}\) refers to draw one number with uniform distribution \(\mathit{allConsiders}[tree]\leftarrow\) uniformly and randomly draw \(\mathit{nConsider}\) features from \(F\) without replacement; \(\mathit{allParams}[tree]\leftarrow\mathit{initial\ values}\);  end while while receiving new batch \(X^{i},Y^{i}\) from \(\mathit{dataStream}\)do \(\mathit{UpdateForest}(X^{i},Y^{i},\mathit{Aco}_{i-1},\mathit{Size}_{i-1}, \mathit{trees},\mathit{allConsiders},\mathit{allParams},\boldsymbol{E}( \cdot))\);  end while  end while
```  
**Algorithm 3**ForgetfulRandomForest  
Figure 10: Main function of the forgetful random forest. The value \(\mathit{nConsider}\) is the size of the subset of features considered for any given tree. ```
Input :\((X^{i},Y^{i})\), incoming training data for current node Globals :\(trees\), the list of decision trees that are actively updated \((Acc_{i-1},Size_{i-1})\), the accuracy and data size of testing of of previous update \(allParams\), the parameters that will be updated for each tree in \(trees\) allConsiders, the features that will be considered for each tree in \(trees\)\(G(\cdot)\), a function to score the fitness of a feature for splitting \(E(\cdot)\), the stopping criteria, returns boolean \(nTree\), the number of decision trees that are actively updated \(tThresh\), the threshold for discarding trees
1 begin
2\(newAcc\leftarrow\textit{{fraction}}\textit{{Correct}}(trees,X^{i},Y^{i})-1/nClasses; //nClasses is the number of classes in \(Y^{i}\), \(1/nClasses\) is the accuracy of random guessing if\(2 Sample\textit{{Test}}(Acc_{i-1},newAcc,Size_{i-1},\|X^{i}\|,Size_{i-1})>tThresh\)then
3 if\(Acc_{i}<Acc_{i-1}\)then
4\(Discard((Acc_{i-1}-newAcc)/Acc_{i-1})*nTree,trees,allParams,allConsiders)\);
5 end if\(Size_{i}\leftarrow\|X^{i}\|\);
6\(Acc_{i}\gets newAcc\);
7
8 else
9\(Acc_{i}\leftarrow\frac{Acc_{i-1}*Size_{i-1}+newAcc*\|X^{i}\|}{Size_{i-1}+\|X^{i}\|}\);
10 // \(Acc_{i}\) is calculated based on a weighted average,
11 // which is weighted by the size of the new data compared to the previous data. \(Size_{i}\gets Size_{i-1}+\|X^{i}\|\);
12
13 end if
14 for each \(tree\) in \(trees\)do
15\(AdapParameters(allParams[tree])\);
16\(UpdateSubTree\textit{{RF}}(Bagging(X^{i},Y^{i}),tree,allParams[tree],allConsiders[tree])\);
17
18 end for
19
20 end for
```  
**Algorithm 4**UpdateForest  
As for the forgetful decision tree main routine, the forgetful random forest main routine (Figure 18) is called initially and then each time an incremental batch of data is received. The routine will make predictions with the random forest before the batch and then update the random forest.