# Adaptive Decision Forest: An Incremental Machine Learning Framework

Md Geaur Rahman<EMAIL_ADDRESS>Md Zahidul Islam<EMAIL_ADDRESS>School
of Computing and Mathematics, Charles Sturt University, Australia

###### Abstract

In this study, we present an incremental machine learning framework called
Adaptive Decision Forest (ADF), which produces a decision forest to classify
new records. Based on our two novel theorems, we introduce a new splitting
strategy called iSAT, which allows ADF to classify new records even if they
are associated with previously unseen classes. ADF is capable of identifying
and handling concept drift; it, however, does not forget previously gained
knowledge. Moreover, ADF is capable of handling big data if the data can be
divided into batches. We evaluate ADF on five publicly available natural data
sets and one synthetic data set, and compare the performance of ADF against
the performance of eight state-of-the-art techniques. Our experimental
results, including statistical sign test and Nemenyi test analyses, indicate a
clear superiority of the proposed framework over the state-of-the-art
techniques.

###### keywords:

Incremental learning, Decision forest algorithm, Concept drift, Big data,
Online learning

††journal: Pattern Recognition

##  1 Introduction

Nowadays information is considered the backbone of all organizations and is
critical for their success. In real applications, big data often arrive as
batches over time [1]. Let us consider a scenario of an undergraduate
admission system of a university where the admission authority can identify
those applicants who have a high chance of completing the degree. The
likelihood of success of an applicant can be determined by comparing the
applicant’s information (such as academic record, age, gender, nationality,
etc.) with similar information from successful graduates. The yearly list of
both successful and unsuccessful students can be considered as the batch
training data and the yearly undergraduate admission applicants can be
considered as the batch testing data, as shown in Fig. 1. Moreover, the batch
testing data may follow not only the distribution of current batch training
data but also the distributions of some previous batches of training data. In
Fig. 1 we can see that a group of students obtained their qualification (i.e.
completed Year 12 degree) in the current year and another group of students
obtained the qualification in previous years. Both groups of students are
generally eligible to apply for the admission. The batch testing data of the
year 2019 (i.e. Test batch 3) may have the students who obtained the admission
qualification in the years 2017, 2018 and 2019.

Figure 1: An example of an undergraduate admission system of a university
where both training and testing data arrive yearly as batches and the
incremental classifier is updated (marked with the dotted box) each year based
on the batch training data.

Traditional machine learning algorithms such as Random Forest (RF) [2] build
recognition models based on training data, which are available at a time, to
classify test data. Since all the training data in many real applications may
not be available at a time, traditional machine learning algorithms are unable
to build good models [3]. Accurate recommendations and recognition are also an
important challenge for the algorithms since they are not capable of adapting
to dynamic changes in real applications [4, 3]. Dynamic changes in data are
also known as concept drifts. To adapt to the concept drifts, the models of
traditional algorithms need to be retrained from scratch, which leads to large
waste of time and memory [4, 3]. Also, the data can be so big that it may not
fit in a memory to be processed by traditional machine learning algorithms
[3].

Thus, to adapt concept drifts and to handle big data that often arrive as
batches over time, it is crucial to have learning algorithms that are capable
of learning incrementally and building a knowledge base over time for ensuring
accurate classification of test batches that follow the distributions of
current and previous batches [3]. In Fig. 1 we can see that an incremental
classifier is built by the authority to assess the possibility of applicants
to be successful graduates. Moreover, the classifier is updated incrementally
based on the yearly batch training data.

A number of methods have been proposed recently in the literature for
incremental learning [5, 3, 6, 7, 8]. An existing method called Nearest Class
Mean Classifier (NCMC) [6] classifies a new record based on the centroids. It
computes the centroid of the records labeled with a class and for a new
unlabeled record it assigns the class value for the centroid of which is the
closest to the record among all centroids. It updates the centroids based on
the records that arrive over time. Although the method requires a low
execution time for adapting the model with new records, it suffers with a low
classification accuracy if the initial training data set is small [5, 9].

The classification accuracy is increased significantly in a recent technique
called CIRF [3], which is capable of updating an incremental classifier based
on the current batch data only. CIRF first builds a decision forest by
applying the RF [2] on the initial batch data. It also identifies the boundary
of the decision forest by considering the records as a box, which is also
known as the Axis Aligned Minimum Bounding Box (AABB) [10] (see Definition 1).
A sample AABB of a set of data points is illustrated in Fig. 2a. Using the
AABB, CIRF calculates two vectors called minimum and maximum vectors, where
the $j$th element of the minimum vector is the minimum value of the $j$the
attribute and the $j$th element of the maximum vector is the maximum value of
the $j$the attribute.

Figure 2: (a) An Axis Aligned Minimum Bounding Box (AABB) of a set of data
points represented by black stars. (b) Two AABBs are illustrated in a
2-dimensional form where attributes $A_{i}$ and $A_{j}$ are projected on
x-axis and y-axis, respectively. (c) ${AABB}_{2}$ contains records having
multiple class values. (d) There is an overlap between ${AABB}_{1}$ and
${AABB}_{2}$ due to the mixture of known (black stars) and unknown (red
triangles) classes.

For a new batch data having known class values111Known class values: the class
values that appeared in the previous batches and hence previous forests were
built from the batches having these class values., CIRF updates a decision
tree of the decision forest just by assigning the records into leaves they
belong to. However, for a new batch data having unknown class values222Unknown
class values: the class values that do not appear in the previous batches and
hence previous forests were built from the batches not having these class
values., CIRF updates a decision tree by adding a root where the previous tree
is considered as a child of the root and the new batch data are used to create
another child of the root. CIRF uses an existing splitting strategy called
Separating Axis Theorem (SAT) [11] (see Theorem 1) to determine the split
attribute as follows. Let ${AABB}_{1}$ and ${AABB}_{2}$ be two boxes that are
represented by the records of previous batches and the records of current
batch, respectively (as shown in Fig. 2b). CIRF calculates the minimum and
maximum vectors for both ${AABB}_{1}$ and ${AABB}_{2}$. Using the vectors, the
method then calculates the distance between ${AABB}_{1}$ and ${AABB}_{2}$ for
all numerical attributes. For example, in Fig. 2b $d_{1}$ is the distance
between AABB1 and AABB2 for the attribute $A_{i}$ which is projected on the
x-axis. The attribute which has the maximum distance is chosen as the split
attribute (see Eq. (19) for details). It is reported that CIRF outperforms
state-of-the-art incremental learning algorithms in terms of both
classification accuracy and execution time [3].

We argue that CIRF has three main shortcomings. First, CIRF considers only the
numerical attributes while calculating the minimum and maximum vectors and
thereby, categorical attributes are never considered as the split attributes.
Second, for a new batch having multiple unknown class values (such as
${AABB}_{2}$ Fig. 2c) CIRF adapts the decision tree by creating new a leaf
under the root of the tree. Due to the heterogeneity in the new leaf, CIRF
leads to a low classification accuracy. Third, if a new batch contains records
with a mix of known and unknown classes (such as ${AABB}_{2}$ Fig. 2d), there
will be an overlap between the AABBs (as shown in Fig 2d) resulting is a high
heterogeneity in the newly created leaf. Thus, CIRF suffers with a low
classification accuracy (see Fig. 5).

The existing methods therefore have room for further improvement. We propose a
novel incremental learning framework called Adaptive Decision Forest (ADF) in
this paper. In the ADF framework, we build decision forests by using one of
the three techniques: RF [2], HT [12] and SysFor [13], and thereby obtain
three variants called ADF-R, ADF-H and ADF-S, respectively. The ADF framework
is adapted for the training batch data that arrive over time. During
adaptation, ADF makes use of our proposed novel splitting strategy called
improved Separating Axis Theorem (iSAT) to find the best split attribute. In
iSAT, we use both SAT and entropy-based strategies. For a new batch having a
mix of known and unknown classes, ADF can find two sub-AABBs (as shown in Fig
2d and Fig. 8) based on our proposed theorems (see Theorem 2 and Theorem 3)
where a sub-AABB contains records with a minimum number of a mix of known and
unknown classes and the other sub-AABB has records with new class values. For
the first sub-AABB, we use the entropy based splitting strategy and for the
second sub-AABB, we consider SAT based splitting strategy.

The main contributions of this paper can be summarized as follows. 1) We
present a novel splitting strategy called improved separating axis theorem
(iSAT), which makes use of the separating axis theorem (SAT) [11] and our
proposed two theorems (Theorem 2 and Theorem 3) to find the best split
attribute which can be either numerical or categorical. 2) We present a
framework called Adaptive Decision Forest (ADF) which can identify and handle
concept drifts and preserve previously acquired knowledge by introducing a set
of forests (see Section 3.1.3). 3) ADF can handle all scenarios (as shown in
Fig. 3) that may occur for the new batches that arrive over time. 4) ADF is
also applicable to big data applications where the data can be divided into
batches (see section 4.6).

We evaluate ADF variants on five real data sets [14] and one synthetic data
set by comparing its performance with the performance of eight high quality
existing techniques including HT [12], CIRF [3], and ARF [7]. We also compare
the performance of ADF variants with the performance of two non-incremental
existing algorithms such as SysFor [13] and RF [2]. Our experimental results
indicate that ADF variants achieve a higher classification accuracy than the
existing methods.

The rest of the paper is organized as follows. Section 2 presents the problem
formulation and assumptions and a background study on incremental learning
methods. Our proposed incremental framework is presented in Section 3. Section
4 presents empirical evaluations, and Section 5 gives concluding remarks.

##  2 Problem Formulation and Related Work

###  2.1 Problem Formulation and Assumptions

Let $D$ be an input data set which we consider as a two dimensional table,
where rows represent records $X=\\{X_{1},X_{2},\ldots X_{n}\\}$ and columns
represent attributes $A=\\{A_{1},A_{2},\ldots A_{m}\\}$. There are $m$
attributes i.e. $|A|=m$ and $n$ records i.e. $|D|=|X|=n$. $X_{ij}$ represents
the $j$th attribute value of the $i$th record. An attribute $A_{j}\in A$ can
be categorical or numerical. The domain of a categorical attribute $A_{j}$ can
be $\\{a_{j}^{1},a_{j}^{2},\ldots a_{j}^{k}\\}$ meaning the domain size of
$A_{j}$ is $|A_{j}|=k$. Similarly, the domain of a numerical attribute $A_{p}$
can be $[a_{p}^{low},a_{p}^{up}]$, where $a_{p}^{low}$ and $a_{p}^{up}$ are
the lower and upper limits of the domain, respectively. Let $Y\in A$ be the
class attribute having a set of class values $C=\\{C_{1},C_{2},\ldots
C_{k}\\}$. A classifier $T$ is a function $T\leftarrow f(X):D\rightarrow Y$
that maps records $X\in D$ to the class values. The notations that we use in
this paper are presented in Table 1.

Table 1: Notations and their meanings. Notations | Meaning | Notations | Meaning
---|---|---|---
$D$ | Data set | $P(X)$ |  Probability of $X$
$D_{train}$ | Training data set | $P(Y|X)$ |  Probability of $Y$ given $X$
$D_{test}$ | Test data set | $P(Y|\neg X)$ |  Probability of $Y$ with changes $X$
$D^{t^{i}}_{B}$ |  Batch data set at time $t^{i}$ | $P(X,Y)$ |  Probability distribution of $X$ and $Y$
${D^{t^{i}}_{B_{train}}}$ |  Training batch data set at time $t^{i}$ | $\Psi$ | Set of parameters
$D^{t^{i}}_{B_{test}}$ |  Test batch data set at time $t^{i}$ | $\theta$ | Repairable threshold
$X$ |  Set of records in $D$ | $\lambda$ | Concept drift threshold
$X_{i}$ |  $i$-th record in $D$ | $\gamma$ | Reserve window threshold
$|D|=|X|=n$ |  Number of records in $D$ | $T$ | Classifier/decision forest
$|{D^{t^{i}}_{B_{train}}}|=n_{B}$ |  Number of records in ${D^{t^{i}}_{B_{train}}}$ | $l$ | Number of leaves of a tree
$A$ |  Set of attributes in $D$ | $T^{A}$ | Active Forest (AF)
$|A|=m$ |  Number of attributes in $D$ | $T^{P}$ | Permanent Forest (PF)
$A_{j}$ |  $j$-th attribute in $D$ | $T^{T}$ | Temporarily Forest (TF)
$|A_{j}|$ |  Domain size of $j$-th attribute in $D$ | $L^{A}$ |  Leaves statistics of $T^{A}$
$a_{j}^{low}$ |  Lower limit of $j$-th numerical attribute | $L^{P}$ |  Leaves statistics of $T^{P}$
$a_{j}^{up}$ |  Upper limit of $j$-th numerical attribute | $L^{T}$ |  Leaves statistics of $T^{T}$
$Y$ |  Class attribute in $D$ | $D^{W}$ | Reserve window data set
$C$ |  Set of class values in $D$ | $P^{A}$ |  Perturbed leaves of $T^{A}$
$C_{k}$ |  $k$-th class value in $C$ | $P^{U}$ |  Perturbed leaves of $T^{P}$
$M$ | Number of trees | $P^{R}$ |  Perturbed leaves of $T^{T}$
$\epsilon$ | Error tolerance threshold |  |

Let $D_{train}=\\{X_{i},Y_{i}\\},X_{i}\in X,Y_{i}\in C$ and
$D_{test}=\\{X^{\prime}_{i}\\},X^{\prime}_{i}\in
X^{\prime}\>{X\cap}X^{\prime}\rightarrow\emptyset$ be the training data set
and test data set, respectively, where the test data set does not have the
class attribute. Traditional supervised learning algorithms assume that the
whole training data set $D_{train}$ is available during training, and both
$D_{train}$ and $D_{test}$ follow the same probability distribution
$P(X,Y)=P(Y|X).P(X)$. The goal of the supervised learning algorithms is to
build a classifier $T$, from $D_{train}$, which is capable of classifying the
records of the test data set $D_{test}$ with a high classification accuracy.

Sometimes the scenario can be more complex where the whole input data set
$D_{train}$ is not available during building the classifier $T$. Sometimes
although the whole data is available, it may not fit in a single memory due to
its size being too big. Many incremental learning algorithms assume that data
arrive as batches over time [3, 5]. Moreover, the distribution
$P(X,Y)=P(Y|X).P(X)$ of a training data set may change over time and may cause
concept drift i.e. $P(Y|\neg X)$ which may have a serious impact on
classification accuracy. However, the test data sets may follow both current
and previous distributions. Let $D^{t^{0}}_{B_{train}}$,
$D^{t^{1}}_{B_{train}}$ and $D^{t^{2}}_{B_{train}}$ be three batches of
training data with the class attribute arrive at time $t^{0}$, $t^{1}$, and
$t^{2}$, respectively and $D^{t^{0}}_{B_{test}}$, $D^{t^{1}}_{B_{test}}$ and
$D^{t^{2}}_{B_{test}}$ be three corresponding test batches at time $t^{0}$,
$t^{1}$, and $t^{2}$, respectively. The test batch $D^{t^{2}}_{B_{test}}$
contains data that may follow the distributions of $D^{t^{2}}_{B_{train}}$,
$D^{t^{1}}_{B_{train}}$ and $D^{t^{0}}_{B_{train}}$ (as discussed in Section 1
and demonstrated in Fig 1). Thus, it is essential to adapt the classifier over
time to achieve a high classification accuracy. Our proposed incremental
framework is formulated under the following assumptions: 1) Data arrive as
batches over time. Let $D^{t^{i}}_{B_{train}}$ and $D^{t^{j}}_{B_{train}}$ be
the batches of data arriving at time $t^{i}$ and $t^{j}$, respectively. 2) The
set of class values $C$ may change over time. Let $C^{t^{i}}$ and $C^{t^{j}}$
be the sets of class values of $t^{i}$ and $t^{j}$, respectively, where
$C^{t^{i}}$ and $C^{t^{j}}$ may differ. 3) The class attribute ${Y}^{i}$ in
the training batch data set ${D^{t^{i}}_{B_{train}}}$ at $t^{i}$ is available,
thus, it is possible to adapt the classifier $T^{i}$ over time. 4)
$D^{t^{i}}_{B_{test}}$ follows the distributions of training batch data sets
arriving at times ${\\{t^{j}\\}}^{\gamma}_{j=i}$.

Under such assumptions, the goal of our proposed framework is to define an
incremental classifier $T^{i}\leftarrow
f^{i}(X^{i}|T^{i-1},D^{t^{i}}_{B_{train}},D^{t^{i}}_{B_{test}},\Psi)$ based on
a decision forest which will achieve an accurate classification for the test
batch data set $D^{t^{i}}_{B_{test}}$ at time $t^{i}$ by adapting the
classifier $T^{i-1}$ at time $t^{i-1}$ with the training batch data set
$D^{t^{i}}_{B_{train}}$ and the set of parameters $\Psi$.

###  2.2 Related Work

A number of methods have been proposed for incremental learning [5, 3, 6].
Incremental learning methods process records one by one or batch by batch that
arrive over a period of time [1]. An important challenge of the methods is to
handle dynamic changes that may occur in real applications. Generally dynamic
changes can happen in two ways: 1) changes in data distribution $\&$ feature
dimensions, and 2) changes in class values [3].

For handling the changes in data distribution $\&$ feature dimensions, a
number of feature incremental learning algorithms [4, 15] have been proposed.
An existing method called FLSSVM [15] that makes use of a least square support
vector machine algorithm to adapt a classifier with the new batch data set.
For the initial batch data set, the method builds a classifier using an
existing least square support vector machine algorithm [16]. With the
previously learned structural parameters, FLSSVM then adapts the data of the
new attributes. Although FLSSVM requires comparatively low training time and
memory, it is difficult to find a suitable kernel function for SVM for
achieving a good accuracy [16].

For handling the changes in class values a number of class incremental
learning algorithms [5, 3, 17] have been proposed. An existing class
incremental learning method called NCMC [6] adapts the new batch records
$X_{j}\in D^{t^{j}}_{B}$ based on the mean vectors $V_{C_{k}}\forall k$ of
class values $C$. For each class value $C_{k}\in C$ of the initial data set,
NCMC first calculates the mean vector $V_{C_{k}}$ of the records $X_{C_{k}}$
belonging to the class $C_{k}\in C$ as follows.

$\displaystyle V_{C_{k}}={\frac{1}{|X_{C_{k}}|}}{\sum_{X_{i}\in
X_{C_{k}}}{X_{i}}}$ (1)

For a new record $X_{j}\in D^{t^{j}}_{B}$ the method then calculates distances
separately between the new record and the means of the class values. The
Euclidean distance $d^{j}_{k}$ between $X_{j}\in D^{t^{j}}_{B}$ and mean
vector $V_{C_{k}};C_{k}\in C$ is calculated as follows.

$\displaystyle d^{j}_{k}=\left\|X_{j}-V_{C_{k}}\right\|_{2}$ (2)

The record $X_{j}\in D^{t^{j}}_{B}$ is classified by assigning the class value
$C_{k}\in C$ which has the minimum distance. The method then recalculates
$V_{C_{k}}\forall k$ based on the records that arrive over time. Although the
method requires a low execution time for adapting the model with new records,
it suffers with a low classification accuracy if the initial training data set
does not have enough records [5, 9].

This problem is addressed in an existing method called NCMF [9] which we
discussed in the Introduction section. NCMF first builds a decision forest $T$
by applying an existing decision forest algorithm called Random Forest (RF)
[2] on the initial batch data $D^{t^{i}}_{B}$. The decision forest $T$ is then
updated for the batch data sets that arrive over time. For a batch data set
$D^{t^{j}}_{B}$, NCMF updates the decision forest $T$ as follows. NCMF first
assigns the records $X_{j}\in D^{t^{j}}_{B}$ in the leaves of a tree $t\in T$
the records belong to. If a leaf $l$ contains records having multiple class
values, NCMF calculates the mean vectors $V_{|C|}$ by using the Eq. 1. NCMF
then translates the mean vectors into two class values $e\in\\{+ve,-ve\\}$ by
randomly assigning the mean vectors either into Positive or Negative. The
splitting function $f(X_{j})$ for assigning a record $X_{j}\in D^{t^{j}}_{B}$
is defined as follows [9].

$\displaystyle
f(X_{j})=e_{C_{k}^{*}(X_{j})}~{}~{}~{}~{}~{}~{}~{}~{}where~{}~{}~{}C_{k}^{*}(X_{j})=\underset{C_{K}\in
C}{argmin}\left\|X_{j}-V_{C_{k}}\right\|_{2}$ (3)

Using the splitting function $f(X_{j})$, NCMF splits the leaf $l$ into two
sets where one set is considered as the left child and the other set is
considered as the right child. It continues this splitting process if the size
of any child is greater than a user-defined threshold. It is reported that
NCMF achieves a high accuracy over some existing methods including NCMC and
RF. However, during the splitting process the method requires all previous
data, resulting is a high computational time [5].

The computational time is reduced in a recent technique called CIRF [3] that
first builds a decision forest $T$ by applying the RF on the initial batch
data $D^{t^{i}}_{B}$. The decision forest $T$ is then updated by using only
the records of the current batch data set $D^{t^{j}}_{B}$. The procedure of
updating the decision forest $T$ is discussed in detail in the Introduction
section. Although CIRF outperforms state-of-the-art incremental learning
algorithms in terms of both classification accuracy and execution time, the
method has three main limitations (that are also mentioned in the Introduction
section) resulting in a low classification accuracy. Therefore, the existing
methods have room for further improvement.

##  3 Our Proposed Incremental Learning Framework: Adaptive Decision Forest
(ADF)

In this section, we present our proposed incremental learning framework called
Adaptive Decision Forest (ADF), which produces a decision forest to classify
new data. ADF takes as input the data that arrive as batches over time. We
consider a batch data set $D^{t^{i}}_{B}$ that arrives at time $t^{i}$. We
also consider that the batch data $D^{t^{i}}_{B}$ has a set of class values
$C^{t^{i}}=\\{C^{t^{i}}_{1},C^{t^{i}}_{2},\ldots C^{t^{i}}_{k}\\}$ where a
class value $C^{t^{i}}_{v}$ is associated with a record $X_{i}\in
D^{t^{i}}_{B}$. Let $T^{i}$ be a decision tree which is built on
$D^{t^{i}}_{B}$. Thus, the class values $C^{t^{i}}\in D^{t^{i}}_{B}$ are
considered to be known to $T^{i}$.

At time $t^{j}$, ADF receives another batch data set $D^{t^{j}}_{B}$ which we
assume has the same attributes $A=\\{A_{1},A_{2},\ldots A_{m}\\}$. However,
$D^{t^{j}}_{B}$ can have a different set of class values
$C^{t^{j}}=\\{C^{t^{j}}_{1},C^{t^{j}}_{2},\ldots C^{t^{j}}_{k}\\}$. The class
values $C^{t^{j}}$ are considered to be new (or unknown) to the decision tree,
$T^{i}$. The class values $C^{t^{j}}$ of a new batch $D^{t^{j}}_{B}$ can be
categorized into five scenarios, namely single known class (SKC), multiple
known class (MKC), single unknown class (SUC), multiple unknown class (MUC)
and a mixture of known and unknown classes (MKUC). The scenarios are defined
in Eq. 9.

$\displaystyle{Scenario(C^{t^{i}},C^{t^{j}})}_{i\neq
j}=\left\\{\begin{array}[]{l l}\text{SKC}&\quad\text{if $|C^{t^{j}}|=1$ \&
$C^{t^{j}}_{k}\in C^{t^{i}}$}\\\ \text{MKC}&\quad\text{if $|C^{t^{j}}|>1$ \&
$C^{t^{j}}_{k}\in C^{t^{i}}$;$\forall{k}$}\\\ \text{SUC}&\quad\text{if
$|C^{t^{j}}|=1$ \& $C^{t^{j}}_{k}\notin C^{t^{i}}$}\\\
\text{MKC}&\quad\text{if $|C^{t^{j}}|>1$ \& $C^{t^{j}}_{k}\notin
C^{t^{i}}$;$\forall{k}$}\\\ \text{MKUC}&\quad\text{if $|C^{t^{j}}|>1$ \&
$C^{t^{j}}_{k}\in C^{t^{i}}$;$\forall{k}$ \& $C^{t^{j}}_{v}\notin
C^{t^{i}}$;$\forall{v}$}\\\ \end{array}\right.;\forall{i,j}$ (9)

The categorization of class values of a new batch data is shown in Fig. 3. To
the best of our knowledge, traditional class incremental learning methods
including CIRF [3] usually focus on the SUC scenario and do not consider other
scenarios. ADF is capable of handling all five scenarios by integrating our
novel $iSAT$ splitting strategy with an existing decision forest algorithm
such as RF [2].

Figure 3: Categorization of class values of a new batch data.

###  3.1 Basic Concept of ADF

Incremental decision forest algorithms (such as CIRF [3] and ARF [7]) can
adapt the decision trees continuously and perform better than the traditional
(non-incremental) decision forest algorithms (such as RF [2] and SysFor [13])
in terms of classification accuracy and training time [3]. We observe the
following three issues that play a vital role in achieving high accuracy by an
incremental decision forest algorithm which is also susceptible to handling
all five scenarios as shown in Eq. 9 and Fig. 3.

The first issue is to identify the best split for a new batch data
$D^{t^{i}}_{B}$. The commonly used splitting strategies are entropy [18], Gini
index [19] and axis aligned [2]. An existing algorithm called CIRF [3] makes
use of an existing splitting strategy called Separating Axis Theorem (SAT)
[11] to find the best split. However, we argue that CIRF does not perform well
on $D^{t^{i}}_{B}$ if it contains records with a mix of known and unknown
classes (MKUC). To find the best split for a batch that follows the MKUC
scenario, we propose a novel splitting strategy called improved separating
axis theorem (iSAT) (see section 3.1.1) by which it is expected to achieve a
high classification accuracy.

We illustrate the argument by considering three toy batch data sets as shown
in Fig. 4a, Fig. 4b and Fig. 4c. Each batch data set contains 10 records and
three attributes, namely “Area of a House in square meter (Area)”, “number of
bedrooms (Beds)” and “House rent category (Rent)”. Figure 4d shows a decision
tree which is built from the batch data $B0$ (as shown in Fig. 4a). The
decision tree is repaired based on the SAT splitting strategy for the batch
data $B1$ (see Fig. 4b) which follows the MKUC scenario. The repaired decision
tree is shown in Fig. 4e. Figure 5 shows that the classification accuracy of
the repaired decision tree (as shown in Fig. 4b) is lower than the
classification accuracy of the decision trees as shown in Fig. 4h and Fig. 4k
that are repaired based on the splitting strategies, namely entropy and iSAT
(see section 3.1.1), respectfully. Besides, the decision tree with the iSAT
splitting strategy achieves high classification accuracy for all batches.

Figure 4: Construction of trees on toy batches in terms of SAT, Entropy and
iSAT splitting strategies. Figure 5: Comparison of classification accuracies
on toy batches in terms of SAT, Entropy and iSAT splitting strategies.

The second issue is to decide whether the decision trees are required to
repair or not. Moreover, if the trees are required to repair then an important
task is to decide how many of the trees should be repaired by considering the
cost of modification. To address the issue, we introduce a repairable strategy
in section 3.1.2 to find an optimal repairable threshold for achieving a high
accuracy with a low cost.

The third issue is to handle concept drifts and preserving historical
information that are gained from the previous batches. In dynamic data
structure, data distribution may change over time and this situation is known
as concept drift, which may generally be categorized in two types, namely
Temporary Concept Drift (TCD)333TCD: If the concept drift occurs in only one
or a few consecutive batches. and Sustainable Concept Drift (SCD)444SCD: If
the concept drift sustains over a period of time.. To handle TCD, if a
decision forest is rebuilt by considering only the current batch
$D^{t^{i}}_{B}$ then it is most likely that the historical information of the
forest will be lost. We argue that the decision forest is unable to classify
the records if they are drawn from the distribution of the previous batches
and may lead to a low classification accuracy. We also argue that the
classification accuracy may be increased if the decision forest is rebuilt
only for the SCD instead of the TCD. A strategy for identifying a SCD is
presented in Section 3.1.4. Moreover, to achieve a high accuracy, a number of
consecutive batches called window (discussed in Section 3.1.5) instead of just
the current batch can be used while rebuilding the decision forest.

We also argue that the historical information may be preserved by building a
set of forests called Permanent Forest ($PF$), Active Forest ($AF$), and
Temporary Forest ($TF$) which are discussed in Section 3.1.3. ADF can update
$PF$, $AF$ and $TF$ in parallel and achieves a high accuracy by keeping the
historical information.

To address the issues, in ADF we consider a number of strategies that are
summarized as follows: improved separating axis theorem (iSAT) based splitting
strategy (in Section 3.1.1), decision trees repairable strategy (in Section
3.1.2), the use of a set of decision forests (in Section 3.1.3),
identification of SCD strategy (in Section 3.1.4), and the use of a window of
batches strategy (in Section 3.1.5). We now discuss each of these strategies
as follows.

####  3.1.1 Improved Separating Axis Theorem (iSAT) Splitting Strategy

We propose a novel splitting strategy called iSAT to find a splitting
attribute and value for a node of a decision tree. Our proposed splitting
strategy $iSAT$ handles the problems of an existing method CIRF [3] which
makes use of an existing algorithm called Axis Aligned Minimum Bounding Box
(AABB) [10] and an existing theorem called Separating Axis Theorem (SAT) [11]
to find the best split attribute and value. We first briefly introduce AABB
and SAT before $iSAT$.

######  Definition 1.

In geometry, the smallest surrounding box of a set of data points is known as
the minimum bounding box [10] where all the data points are surrounded by the
box.

A sample AABB of a set of data points is illustrated in Fig. 2a. If two
minimum bounding boxes are not intersected then it can be concluded that no
overlap exists between the corresponding sets of data points. For example, Fig
2b shows two sets of data points: black stars and red triangles. The smallest
surrounding boxes for the black stars and red triangles are marked with
${AABB}_{1}$ and ${AABB}_{2}$ where the boxes are overlapped at axis $A_{j}$
but not at $A_{i}$. Thus, the black stars and red triangles are separated by
${AABB}_{1}$ and ${AABB}_{2}$ at axis $A_{i}$.

The strategy of separating two sets of data points can be used for the
incremental expansion of a decision tree by inserting a parent of a node. For
example, Fig. 4 demonstrates that the decision tree shown in Fig. 4d is
expanded by adding a parent node “Area” at the root node and the resulting
tree is shown in Fig. 4e. Using AABBs, a decision tree can be represented as a
hierarchical form of nested bounding boxes [3]. For $D^{t^{i}}_{B}$ with new
class values, it is crucial to identify the best split attribute and value.
The issue can be addressed by using the SAT [11] as follows.

######  Theorem 1.

Separating Axis Theorem (SAT) [11, 3, 20]: If two nonempty convex objects are
disjoint then there exists an axis on which the projection of the convex
objects will not overlap.

###### Proof.

Let $R$ be a set of real numbers and $R^{n}$ be a set of real n-vectors. Also
let $z\in R^{n}$ be a normal vector and $b\in R$ be a real number. We now
consider two nonempty convex objects Q and S where $Q\cap S=\emptyset$. Then
there exist $z\neq 0$ and $b$ such that $x|z^{T}x\leq b;\forall x\in Q$ and
$x|z^{T}x\geq b;\forall x\in S$. That is the affine function, $f(x)=z^{T}x-b$
is nonpositive on Q and nonnegative on S. The hyperplane, $h$,
$\\{x|z^{T}x=b\\}$ is considered as the separating hyperplane for the two
objects Q and S. In other words, the hyperplane, $h$, separates the convex
objects Q and S which is illustrated in Fig. 6.

Figure 6: Construction of a separating hyperplane, $h$, $\\{x|z^{T}x=b\\}$
between two disjoint convex objects Q and S [20]. (a) The hyperplane, $h$,
separates the convex objects Q and S. The affine function $z^{T}x-b$ is
nonpositive on Q and nonnegative on S. (b) The points $q\in Q$ and $s\in S$
are the pair points in the two sets that are closest to each other, where the
line segment $\overline{qs}$ between q and s is bisected by the separating
hyperplane $h$ and $h\perp z$. (c) For a point $u\in S$, the affine function
$f(u)$ is nonnegative on S and for a point $v\in Q$, the affine function
$f(v)$ is nonpositive on Q.

Let $u\in S$ and $v\in Q$ be two points. The Euclidean distance between the
points is calculated as

$\displaystyle dist(u,v)={\left\|u-v\right\|}_{2}$ (10)

We consider a vector $DIST$ that contains the distances between the points of
Q and S. There exists points $q\in Q$ and $s\in S$ which has the minimum
distance between Q and S that is

$\displaystyle mindist(Q,S)=\inf\\{DIST\\}$ (11)

We now define

$z=s-q$, $b=\frac{\left\|s\right\|_{2}^{2}-\left\|q\right\|_{2}^{2}}{2}$

Thus by substituting the value of $z$ and $b$, the affine function
$f(x)=z^{T}x-b$ can be expressed as

$\displaystyle f(x)=(s-q)^{T}(x-\frac{s+q}{2})$ (12)

The goal is to show that $f(x)$ is nonpositive on Q and nonnegative on S that
is the hyperplane, $h$, $\\{x|z^{T}x=b\\}$ is perpendicular to the normal
vector $z$ and bisects the line segment $\overline{qs}$ between q and s as
shown in Fig. 6.

We first prove that $f(x)$ is nonnegative on S. For any point $u\in S$ (as
shown in Fig. 6), the affine function $f(u)$ can be written as

$\displaystyle f(u)=(s-q)^{T}(u-\frac{s+q}{2})>0$ (13)

The affine function $f(u)$ can also be expressed as

$\displaystyle
f(u)=(s-q)^{T}(u-s+\frac{s-q}{2})=(s-q)^{T}(u-s)+\frac{\left\|s-q\right\|_{2}^{2}}{2}$
(14)

Now the Euclidean distance between $u\in S$ and $q\in Q$ can be calculated by
taking the derivative of $f(u)$ for a closed interval $t$ (with $t$ as close
to zero) as follows

$\displaystyle\frac{d}{dt}\left\|s+t(u-s)-q\right\|_{2}^{2}|_{t=0}=2(s-q)^{T}(u-s)>0$
(15)

So for some small $t~{}(0<t\leq 1)$, we have

$\displaystyle\left\|s+t(u-s)-q\right\|_{2}>\left\|s-q\right\|_{2}$ (16)

that is the point $s+t(u-s)$ is closer to s than q. Since S is convex and
contains s and u, we have $s+t(u-s)\in S$. Thus, the affine function
$f(x)\forall x\in S$ is nonnegative on S. Similarly, for any point $x\in Q$,
the affine function $f(x)\forall x\in Q$ is nonpositive on Q. Hence, the
hyperplane, $h$ separates the convex objects S and Q. Therefore, there exists
an axis $z\neq 0$ on which the projection of two disjoint convex objects S and
Q does not overlap. ∎

To illustrate Theorem 1, we consider two dimensional AABBs as shown in Fig 2b
where two attributes $A_{i}$ and $A_{j}$ are projected on the x-axis and
y-axis, respectively. ${AABB}_{1}$ is created based on black stars and
${AABB}_{2}$ is created based on red triangles. From the figure we can see
that there is no overlap between ${AABB}_{1}$ and ${AABB}_{2}$ for the $A_{j}$
attribute. According to SAT, the x-axis is the separating axis between
${AABB}_{1}$ and ${AABB}_{2}$ and thus $A_{i}$ is the splitting attribute.
Moreover, if multiple attributes have no overlap then the attribute having the
maximum gap will be considered as the splitting attribute. Let $d_{1}$ be the
gap between ${AABB}_{1}$ and ${AABB}_{2}$ on the x-axis (i.e. attribute
$A_{i}$ ) and $d_{2}$ be the gap between ${AABB}_{1}$ and ${AABB}_{2}$ on the
y-axis (i.e. attribute $A_{j}$ ) then the split attribute $A_{s}$ is
determined based on Eq. (19) [3].

$\displaystyle A_{s}=\left\\{\begin{array}[]{l l}A_{i}&\quad\text{if
$d_{1}>d_{2}$ \& $d_{1}>0$}\\\ A_{j}&\quad\text{if $d_{2}>d_{1}$ \&
$d_{2}>0$}\\\ \end{array}\right.;\forall{i,j}$ (19)

For the x-axis (attribute $A_{i}$), let $V^{i,1}_{min}$ and $V^{i,1}_{max}$ be
the minimum and maximum values of ${AABB}_{1}$, and $V^{i,2}_{min}$ and
$V^{i,2}_{max}$ be the minimum and maximum values of ${AABB}_{2}$. Similarly,
for the y-axis (attribute $A_{j}$), let $V^{j,1}_{min}$ and $V^{j,1}_{max}$ be
the minimum and maximum values of ${AABB}_{1}$, and $V^{j,2}_{min}$ and
$V^{j,2}_{max}$ be the minimum and maximum values of ${AABB}_{2}$. Thus, the
split value $SV$ for $A_{s}$ is calculated by using Eq. (24) [3].

$\displaystyle SV=\left\\{\begin{array}[]{l
l}\frac{V^{i,1}_{max}+V^{i,2}_{min}}{2}&\quad\text{if $d_{1}>d_{2}$ \&
$V^{i,1}_{max}>V^{i,2}_{min}$}\\\
\frac{V^{i,2}_{max}+V^{i,1}_{min}}{2}&\quad\text{if $d_{1}>d_{2}$ \&
$V^{i,2}_{min}>V^{i,1}_{max}$}\\\
\frac{V^{j,1}_{max}+V^{j,2}_{min}}{2}&\quad\text{if $d_{2}>d_{1}$ \&
$V^{j,1}_{max}>V^{j,2}_{min}$}\\\
\frac{V^{j,2}_{max}+V^{j,1}_{min}}{2}&\quad\text{if $d_{2}>d_{1}$ \&
$V^{j,2}_{min}>V^{j,1}_{max}$}\\\ \end{array}\right.;\forall{i,j}$ (24)

Using the SAT based splitting strategy, incremental decision forest algorithms
(such as CIRF [3]) find the split attribute which has the maximum distance
among all numerical attributes. For example, the two bounding boxes
${AABB}_{1}$ and ${AABB}_{2}$ are separated by the attribute $A_{i}$ in Fig
2a. However, the algorithms do not perform well on $D^{t^{i}}_{B}$ with MKUC
scenario (as discussed in Section 3.1). Moreover, the algorithms fail to find
a split if the bounding boxes are non-separable. For example, Fig. 2d shows
that two bounding boxes ${AABB}_{1}$ and ${AABB}_{2}$ that are not separated
by any attributes.

We argue that the accuracy of such algorithms can be improved if it is
possible to find the best split in the case of overlapping bounding boxes. We
propose an improved separating axis theorem (iSAT) where we propose a
definition and two theorems. In iSAT we first define a sub-box called Sub Axis
aligned minimum bounding box (Sub-AABB) as follows.

######  Definition 2.

If we have a set of data points then a Sub-AABB is the smallest axis aligned
minimum bounding box of a subset of the set of data points.

Three sample Sub-AABBs of an AABB are illustrated in Fig. 7a where the Sub-
AABBs are marked with the dotted red rectangles. According to the Definition
2, two overlapping AABBs (as shown in Fig. 2d) can have a number of
overlapping and non-overlapping Sub-AABBs as illustrated in Fig. 7b.

Figure 7: (a) A 2-dimensional illustration of Sub-AABBs. (b) The ${AABB}_{1}$
and ${AABB}_{2}$ consist of sub-AABBs ${Sub-AABB}_{1}$ and ${Sub-AABB}_{2}$,
respectively. (c) The hyperplane separates the two sub-AABBs ${Sub-AABB}_{1}$
and ${Sub-AABB}_{2}$.

######  Theorem 2.

If there are two overlapping AABBs then it is possible to have non-overlapping
Sub-AABBs of the two AABBs.

###### Proof.

We consider two nonempty convex objects ${AABB}_{1}$ and ${AABB}_{2}$ where
${AABB}_{1}\cap{AABB}_{2}\neq\emptyset$ as illustrated in Fig. 2d. According
to Definition 2, both ${AABB}_{1}$ and ${AABB}_{2}$ may have a number of Sub-
AABBs. Let ${Sub-AABB}_{1}$ and ${Sub-AABB}_{2}$ be two Sub-AABBs where ${Sub-
AABB}_{1}\cap{Sub-AABB}_{2}=\emptyset$ as illustrated in Fig. 7b. Then there
exist $z\neq 0$ and $b$ such that $x|z^{T}x\leq b;\forall x\in{Sub-AABB}_{1}$
and $x|z^{T}x\geq b;\forall x\in{Sub-AABB}_{2}$. That is the affine function,
$f(x)=z^{T}x-b$ is nonpositive on ${Sub-AABB}_{1}$ and nonnegative on ${Sub-
AABB}_{2}$. The hyperplane, $h$, $\\{x|z^{T}x=b\\}$ is considered as the
separating hyperplane for the two objects ${Sub-AABB}_{1}$ and ${Sub-
AABB}_{2}$. According to Theorem 1, for any point $x\in{Sub-AABB}_{2}$ the
affine function $f(x)\forall x\in{Sub-AABB}_{2}$ is nonnegative on ${Sub-
AABB}_{2}$. Similarly, for any point $x\in{Sub-AABB}_{1}$, the affine function
$f(x)\forall x\in{Sub-AABB}_{1}$ is nonpositive on ${Sub-AABB}_{2}$. Hence,
the hyperplane, $h$, separates the sub-AABBs ${Sub-AABB}_{1}$ and ${Sub-
AABB}_{2}$. Therefore, there exists an axis $z\neq 0$ on which the projection
of two disjoint sub-AABBs ${Sub-AABB}_{1}$ and ${Sub-AABB}_{2}$ does not
overlap which is illustrated in Fig. 7c. ∎

######  Theorem 3.

If there are two overlapping AABBs, then there will be at least two
overlapping Sub-AABBs of the two AABBs.

###### Proof.

We again consider two nonempty convex objects ${AABB}_{1}$ and ${AABB}_{2}$
where ${AABB}_{1}\cap{AABB}_{2}\neq\emptyset$ as illustrated in Fig. 2d.
According to Definition 2, both ${AABB}_{1}$ and ${AABB}_{2}$ may have a
number of Sub-AABBs. Let ${Sub-AABB}_{3}$ and ${Sub-AABB}_{4}$ be two Sub-
AABBs where ${Sub-AABB}_{3}\cap{Sub-AABB}_{4}\neq\emptyset$ as illustrated in
Fig. 8a. For simplicity, we consider a two dimensional projection of ${Sub-
AABB}_{3}$ and ${Sub-AABB}_{4}$ on the x-axis and y-axis as shown in Fig. 8b.
On the x-axis, let $x_{1}$ and $x_{3}$ be the lower bound and upper bound,
respectively of ${Sub-AABB}_{3}$ and $x_{2}$ and $x_{4}$ be the lower bound
and upper bound, respectively of ${Sub-AABB}_{4}$ such that
$x_{1}<x_{2}<x_{3}<x_{4}$. On the y-axis, let $y_{1}$ and $y_{3}$ be the lower
bound and upper bound, respectively of ${Sub-AABB}_{4}$ and $y_{2}$ and
$y_{4}$ be the lower bound and upper bound, respectively of ${Sub-AABB}_{3}$
such that $y_{1}<y_{2}<y_{3}<y_{4}$. Let $u$ and $v$ be two points of ${Sub-
AABB}_{3}$ and ${Sub-AABB}_{4}$, respectively. If
$\left\|v\right\|_{2}^{2}<\left\|u\right\|_{2}^{2}$ for any points $u\in{Sub-
AABB}_{3}$ and $v\in{Sub-AABB}_{4}$ then there does not exist any axis for
which the two Sub-AABBs are separable.

On the x-axis, let $u=x_{3}$ and $v=x_{2}$. Since $x_{2}<x_{3}$ then
$\left\|v\right\|_{2}^{2}<\left\|u\right\|_{2}^{2}$. Thus, ${Sub-AABB}_{3}$
and ${Sub-AABB}_{4}$ are not separable on the x-axis.

Similarly, on the y-axis, let $u=y_{3}$ and $v=y_{2}$. Since $y_{2}<y_{3}$
then $\left\|v\right\|_{2}^{2}<\left\|u\right\|_{2}^{2}$. Thus, ${Sub-
AABB}_{3}$ and ${Sub-AABB}_{4}$ are not separable on the y-axis. Therefore, it
can be concluded that the two overlapping AABBs consist at least two
overlapping Sub-AABBs.

∎

Figure 8: (a) The ${AABB}_{1}$ and ${AABB}_{2}$ consist of overlapping Sub-
AABBs. (b) The boundaries of AABBs and Sub-AABBs are projected on the x-axis
and y-axis. (c) ${Sub-AABB}_{1}$ and ${Sub-AABB}_{2}$ are overlapping.

Following Theorem 2 and Theorem 3 we realise that the best split-attribute
($A_{s}$) and split-value ($SV$) can be determined by considering the
overlapping and non-overlapping Sub-AABBs. For non-overlapping Sub-AABBs, we
use the SAT based splitting strategy to find the best $A_{s}$ and $SV$. On the
other hand, for overlapping Sub-AABBs, we first identify the Sub-AABB which
has the minimum number of records that have a mix of class values. For
example, in Fig 8c, we can see that ${Sub-AABB}_{4}$ has the minimum number of
records that have a mix of class values. For ${Sub-AABB}_{4}$ we use the
entropy based splitting strategy to find the best $A_{s}$ and $SV$. The steps
of the iSAT is shown in Algorithm 3. The experimental results on the toy data
set (see Fig.5) also justifies the use of both SAT and entropy based splitting
strategies while modifying the classifier $T$ incrementally.

####  3.1.2 Decision Trees Repairable Strategy

We propose a novel strategy in our framework ADF to decide whether a decision
forest, $T$ is repairable or not. We first calculate the confidence of all
leaves of the decision forest, $T$. Let $L^{c^{t^{i}}}_{pq}$ be the confidence
of the $q$-th leaf of the $p$-th tree for the batch data set $D^{t^{i}}_{B}$
at time $t^{i}$. For a new batch data set $D^{t^{j}}_{B}$ at time $t^{j}$, we
also calculate the confidence of all leaves of the decision forest, $T$. Let
$L^{c^{t^{j}}}_{pq}$ be the confidence of the $q$-th leaf of the $p$-th tree
for $D^{t^{j}}_{B}$. We then calculate a repairable matrix $F$ for $T$ by
comparing confidences that are calculated from the batch data sets
$D^{t^{i}}_{B}$ and $D^{t^{j}}_{B}$. A zero value in an element $F_{pq}\in F$
indicates that the $q$-th leaf of the $p$-th tree is not perturbed, whereas a
non-zero value indicates that the $q$-th leaf of the $p$-th tree is perturbed.
The value of the elements $F_{pq}\in F$ is calculated by using Eq. 27.

$\displaystyle F_{pq}=\left\\{\begin{array}[]{l l}1&\quad\text{if
$L^{c^{t^{i}}}_{pq}>(L^{c^{t^{j}}}_{pq}+\epsilon)$}\\\
0&\quad\text{Otherwise}\\\ \end{array}\right.;\forall{p,q}$ (27)

where $\epsilon$ is an error tolerance threshold.

We now calculate the ratio of perturbed leaves of the decision forest, $T$.
Let $l$ be the total leaves of a tree and $l_{total}$ be the total leaves of
the decision forest. Also let $F_{total}\leftarrow\sum_{\forall p,q}{F_{pq}}$
be the total number of perturbed leaves in $T$. We calculate the ratio of
perturbed leaves $\vartheta\leftarrow F_{total}/l_{total}$ in $T$. If the
value of $\vartheta$ is less than or equal to a user-defined threshold,
$\theta$ (also called as the repairable threshold) then $T$ is considered as
repairable.

(a) LDPA dataset

(b) Avila dataset

Figure 9: Justification of repairable threshold $\theta$ and error tolerance
threshold $\epsilon$ on LDPA and Avia data sets in terms of classification
accuracy.

We test the influences of different repairable threshold ($\theta$) and error
tolerance threshold ($\epsilon$) values on two real data sets, namely LDAP
[14], and Avila [14] in terms of classification accuracy. From the data sets,
we create 34 batches of training data and testing data (for details see
Section 4.3). We incrementally apply ADF on the training and testing batches
and calculate the classification accuracies. We use the user-defined $\theta$
that varies between 0 and 1, and $\epsilon$ that varies between 0.0 and 0.1.
For each combination of $\theta$ and $\epsilon$, we calculate average
classification accuracy (from all 34 batches). The average classification
accuracies on two data sets are presented in Fig. 9. Note that the perfect
combination of $\theta$ and $\epsilon$ enables the ADF to perform the best. It
is clear from the Fig. 9 that we get the best classification accuracy (marked
with circles) when $\theta$ is between 0.2 and 0.4 and $\epsilon$ is between
0.01 and 0.03 for both data sets.

####  3.1.3 Handling concept drifts using three parallel forests

We explained in the basic concept (see Section 3.1) that the distribution of
data in dynamic situations may change over time, and Temporary Concept Drift
(TCD) and Sustainable Concept Drift (SCD) may occur. In ADF, we handle both
TCD and SCD by introducing three parallel decision forests, namely Permanent
Forest (PF), $T^{P}$, Active Forest (AF), $T^{A}$, and Temporary Forest (TF),
$T^{T}$. The main motivation of the parallel forests is to keep historical
knowledge leading to a high classification accuracy.

The mechanism of ADF in parallel learning $T^{P}$, $T^{A}$ and $T^{T}$ is
shown in Fig. 10. For every new batch, $T^{P}$ is adapted. Besides, if $T^{A}$
is repairable, we adapt $T^{A}$ for the new batch; otherwise we check the
adaptability of $T^{T}$, if $T^{T}$ is repairable, we adapt $T^{T}$ with the
new batch; otherwise, we build a $T^{T}$ using a window of batches (see
Section 3.1.5). Among the three forests, ADF suggests the user with the forest
which achieves the best classification accuracy.

Figure 10: Parallel incremental learning of $T^{P}$, $T^{A}$ and $T^{T}$.

We test the use of parallel forests on the LDPA data set. We create 34 batches
of training and test data as described in Section 4.2. The performances of PF,
PF, TF, and ADF on the LDPA data set is shown in Fig. 11. We can see that TF
achieves the highest accuracy for the batches where AF is not repairable.
Although AF is repaired for some batches (27 to 29), PF achieves the highest
accuracy. The experimental result indicates the importance of the use of
parallel forests in ADF.

Figure 11: Classification accuracies of PF, AF, TF and ADF on LDPA data set
and the identification of temporary concept drift (TCD) and sustainable
concept drift (SCD).

####  3.1.4 Identification of Sustainable Concept Drift (SCD)

The repairable strategy of ADF (see Section 3.1.2) enables it to determine the
event of Sustainable Concept Drift (SCD) which is discussed in Section 3.1.
Let $cdf$ be the counter which counts the number of consecutive batches for
which the active forest $AF$ (see Section 3.1.3) is not repairable. The event
of SCD is determined by using Eq. 30.

$\displaystyle SCD=\left\\{\begin{array}[]{l l}true&\quad\text{if
$cdf>\lambda$}\\\ false&\quad\text{Otherwise}\\\ \end{array}\right.$ (30)

where, $\lambda$ be the user-defined concept drift threshold. The default
value of $\lambda$ is set to 3. Once a SCD is determined, we replace $T^{A}$
with $T^{T}$. However, if $cdf\leq\lambda$ and $T^{A}$ is repairable, we reset
$cdf$ and $T^{T}$. Figure 11 shows the detection of SCD on LDPA data set.

####  3.1.5 Analysis of impact of using a window of batches

For handling SCD, we replace active forest, $T^{A}$, with temporary forest,
$T^{T}$ which is rebuilt in case of TCD (see Section 3.1.3). We argue that if
the data of a current batch are drawn from the distribution of the previous
batches, the newly build $T^{T}$ may not classify the records correctly and
may lead to a low classification accuracy. Therefore, to keep the accuracy
high, we rebuild $T^{T}$ based on a window of batches. In ADF, we introduce a
user-defined threshold $\gamma$ which is the size of the window. The default
value of $\gamma$ is 3.

We test the influence of using a window of batches in ADF on a synthetic data
set (see Table 3) by creating 8 batches of training data and testing data (for
details see Section 4.3). For a batch $D^{t^{i}}_{B}$, we build a decision
forest by applying SysFor [13] on ${D^{t^{i}}_{B_{train}}}$ and noted the
execution time. The accuracy of the forest is calculated by classifying the
records of $D^{t^{i}}_{B_{test}}$. Similarly, we apply SysFor [13] on a window
that contains the last $\gamma$ number of batches and calculate the
classification accuracy and execution time. Figure 12 shows that SysFor (with
a window of batches) achieves a higher classification accuracy at the expense
of a slightly higher execution time. The result indicates the importance of
using the window of batches while rebuilding $T^{T}$ in ADF.

(a) Classification accuracies of SysFor [13] and SysFor (Window) methods on
Synthetic data set

(b) Execution time of SysFor and SysFor (Window) methods on Synthetic data set

Figure 12: Classification accuracies and execution times of SysFor [13] and
SysFor (Window) methods on Synthetic data set.

###  3.2 Incremental Tree Growing Mechanism of ADF

To accommodate all scenarios as shown in Eq. 9 and Fig. 3, in ADF we propose
an incremental tree growing mechanism, which is presented in Algorithm 1.

At time $t^{0}$, ADF takes a batch data set ${D^{t^{0}}_{B_{train}}}$ (which
is renamed as $D^{B}$ for simplicity) as input. It also takes a number of
parameters as shown in Algorithm 1. Initially, the user-defined thresholds are
initialised with their default values (see Section 3.1.2, Section 3.1.4 and
Section 3.1.5) and the forests and the statistics are set to $null$. For
$D^{B}$, ADF makes use of Algorithm 1 to build decision forests and calculate
their statistics. ADF finds the best forest and recommends it for the user.

At time $t^{i}$, for $D^{B}$ (which is actually ${D^{t^{i}}_{B_{train}}}$) ADF
updates the forests and statistics by using Algorithm 1 and recommends the
best forest for the user. ADF repeats this process for the remaining batches.

We now present the main steps of Algorithm 1 as follows. In Step 1, we build
$T^{P}$ (if it is $null$) by applying an existing decision forest algorithm
such as RF [2] on $D^{B}$. We also make a copy of $T^{P}$ to $T^{A}$. In Step
2, we first identify the perturbed leaves $F^{P}$ by using Eq. (27). We then
repair $T^{P}$ by using a procedure called RepairForest() which is presented
in Algorithm 2. RepairForest() takes $T^{P}$, $D^{B}$, $L^{P}$, $F^{P}$ and
$\theta$ as input and returns updated permanent forest ($T^{P\prime}$) and
updated leaf statistics ($L^{P\prime}$) as output. In Step 3, we again find
the perturbed leaves $F^{A}$ for $T^{A}$ by using Eq. 27 and then calculate
the percentage of perturbed leaves $\vartheta^{A}$ based on the process
discussed in Section 3.1.2. If $\vartheta^{A}$ is less than or equal to
$\theta$, we consider that $T^{A}$ is repairable. We then repair $T^{A}$ by
using the procedure RepairForest() that returns updated active forest
($T^{A\prime}$) and updated leaf statistics ($L^{A\prime}$) as output.

In Step 4, we update the window of batches $D^{W}$. Let $w=|D^{W}|$ be the
number of batches that are currently stored in $D^{W}$. If $w$ is greater than
or equal to $\lambda$, we first remove the oldest batch from $D^{W}$ and the
add $D^{B}$ to $D^{W}$. In Step 5, we build $T^{T}$,
$T_{k}^{T}$,$k=1,2,\ldots,M$ (if $T^{T}$ is null) by applying RF on $D^{B}$.
Similar to Step 3, in Step 6 we repair $T^{T}$ if it is repairable. We find
the perturbed leaves $F^{T}$ of $T^{T}$ and then calculate the percentage of
perturbed leaves $\vartheta^{T}$. If $\vartheta^{T}$ is less than or equal to
$\theta$, we consider that $T^{T}$ is repairable. We then repair $T^{T}$ by
using procedure RepairForest() that returns updated temporary forest
($T^{T\prime}$) and updated leaf statistics ($L^{T\prime}$) as output.
Finally, in step 7, Algorithm 1 returns all updated classifiers, statistics
and parameters.

Input : Batch data set $D^{B}$, Permanent Forest (PF) $T^{P}$, Active Forest
(AF) $T^{A}$, Temporary Forest (TF) $T^{R}$, Statistics of PF leaves $L^{P}$,
Statistics of AF leaves $L^{A}$, Statistics of TF leaves $L^{T}$, Reserve
window $D^{W}$, Concept Drift Flag ($cdf$) Concept Drift Threshold
($\lambda$), Repairable Threshold ($\theta$), Error Tolerance Threshold
($\epsilon$) and Reserve Window Size ($\gamma$).

Output : Updated $T^{P^{\prime}}$, $T^{A^{\prime}}$, $T^{T^{\prime}}$,
$L^{P^{\prime}}$, $L^{A^{\prime}}$, $L^{T^{\prime}}$, $D^{W^{\prime}}$, and
$cdf$.

Step 1:

if  _$T^{P}$ is $null$_ then

Apply an existing decision forest algorithm such as RF [2] on $D^{B}$ to build
PF, $T_{m}^{P}$,$m=1,2,\ldots,M$; /* PF is built with M trees */

Set $T^{A}\leftarrow T^{P}$;

$Goto~{}Step~{}7$;

end if

end

Step 2:

Find perturbed leaves, $F^{P}\leftarrow
FindPerturbedLeaves(D^{B},T^{P},\epsilon,L^{P})$; /* Find perturbed leaves in
$T^{P}$ */

$T^{P^{\prime}},L^{P^{\prime}}\leftarrow
RepairForest(T^{P},D^{B},L^{P},F^{P},\theta)$;

end

Step 3:

Find perturbed leaves, $F^{A}\leftarrow
FindPerturbedLeaves(D^{B},T^{A},\epsilon,L^{A})$; /* Find faulty leaves in
$T^{A}$ */

Calculate, $\vartheta^{A}\leftarrow CalculatePerturbedLeavesRatio(F^{A})$; /*
Calculate the percentage of faulty leaves in $T^{A}$ */

if  _$\vartheta^{A}\leq\theta$_ then

$T^{A^{\prime}},L^{A^{\prime}}\leftarrow
RepairForest(T^{A},D^{B},L^{A},F^{A},\theta)$;

$Goto~{}Step~{}7$;

end if

end

Step 4:

if  _$|D^{W}|\geq\gamma$_ then

Find the oldest batch in $D^{W}$ and set to $D^{O}$;

$D^{W}\leftarrow D^{W}\cap D^{O}$;

end if

$D^{W^{\prime}}\leftarrow D^{W}\cup D^{B}$;

$cdf\leftarrow cdf+1$;

end

Step 5:

if  _$T^{T}$ is $null$_ then

Apply RF on $D^{W^{\prime}}$ to build TF, $T_{m}^{T}$, $m=1,2,\ldots,M$;

$Goto~{}Step~{}7$;

end if

end

Step 6:

Find perturbed leaves, $F^{T}\leftarrow
FindPerturbedLeaves(D^{B},T^{T},\epsilon,L^{T})$; /* Find faulty leaves in
$T^{R}$ */

Calculate, $\vartheta^{R}\leftarrow CalculatePerturbedLeavesRatio(F^{T})$; /*
Calculate the percentage of perturbed leaves in $T^{T}$ */

if  _$\vartheta^{T}\leq\theta$_ then

$T^{T^{\prime}},L^{T^{\prime}}\leftarrow
RepairForest(T^{T},D^{B},L^{T},F^{T},\theta)$;

end if

else

Apply RF on $D^{W^{\prime}}$ to build TF, $T_{m}^{T}$, $m=1,2,..,M$;

if  _$cdf >\lambda$_ then

$T^{A^{\prime}}\leftarrow T^{T^{\prime}}$;
$T^{T^{\prime}}\leftarrow\emptyset$; $cdf\leftarrow 0$;
$L^{A^{\prime}}\leftarrow L^{T^{\prime}}$;

end if

end if

end

Step 7:

Return $T^{P^{\prime}}$, $T^{A^{\prime}}$, $T^{T^{\prime}}$, $L^{P^{\prime}}$,
$L^{A^{\prime}}$, $L^{T^{\prime}}$, $D^{W^{\prime}}$ and $cdf$.

end

Algorithm 1 LearnADF()

Input : Decision forest, $T$, Batch data set, $D^{B}$, Leaves statistics, $L$,
Perturbed leaves $F$ and Repairable threshold $\theta$.

Output : Updated decision forest $T^{\prime}$, updated leaves statistics,
$L^{\prime}$.

Step 1:

Set $T^{\prime}\leftarrow\emptyset$;

Set $L^{\prime}\leftarrow\emptyset$;

for  _$k=1$ to $M$_ do

calculate, $\vartheta\leftarrow CalculatePerturbedLeavesRatio(F_{k})$;
/*Calculate the percentages of perturbed leaves of the $k^{th}$-tree,
$T_{k}$.*/

if  _$\vartheta >\theta$_ then

$T^{\prime}_{k}\leftarrow iSAT(T_{k},D^{B})$; /*Repair $T_{k}$ by using our
proposed improved separating axis theorem (iSAT).*/

for  _each leaf, $l\in T^{\prime}_{i}$_ do

Set $D^{l}\leftarrow FindRecords(T_{k},D^{B},l)$;

if  _$isPure(D^{l})==false\ &isPerturbed(l)\&SizeOf(D^{l})>MinLeafSize$_ then

Expand leaf $l$ using Entropy based splitting strategy;

end if

end for

end if

calculate, $L^{\prime}_{k}\leftarrow
UpdateLeafStatistics(T^{\prime}_{k},D^{B},L)$;

$L^{\prime}\leftarrow L^{\prime}\cup L^{\prime}_{k}$ $T^{\prime}\leftarrow
T^{\prime}\cup T^{\prime}_{k}$

end for

end

Step 2:

Return $T^{\prime}$;

end

Algorithm 2 Procedure RepairForest()

Input : Decision tree, $t$, Batch data set, $D^{B}$

Output : Updated decision tree, $t^{\prime}$

Step 1:

set $LB^{t}\leftarrow min(t)$;/*Find lower boundary of $t$ for all numerical
attributes. */

set $UB^{t}\leftarrow max(t)$; /*Find upper boundary of $t$ for all numerical
attributes. */

set $LB^{B}\leftarrow min(D^{B})$; /*Find lower boundary of $D^{B}$ for all
numerical attributes. */

set $UB^{B}\leftarrow max(D^{B})$; /*Find upper boundary of $D^{B}$ for all
numerical attributes. */

set $Dist_{1}\leftarrow LB^{B}-UB^{t}$; $Dist_{2}\leftarrow LB^{t}-UB^{B}$;

set $Max_{1}\leftarrow max(Dist_{1})$; $Max_{2}\leftarrow max(Dist_{2})$;

end

Step 2:

/*If there is no overlapping between $t$ and $D^{B}$. */

if  _( $Max_{1}>0\&Max_{1}\geq Max_{2}$) OR ($Max_{2}>0\&Max_{2}\geq Max_{1}$)
_ then

if  _$Max_{1} >0\&Max_{1}\geq Max_{2}$_ then

Set $splitAttr\leftarrow findAttributeWithMaxDistance(Dist_{1},Max_{1})$;

set $SplitValue\leftarrow(LB^{B}[splitAttr]+UB^{t}[splitAttr])/2$;

Create a node, $node\leftarrow CreateNode(splitAttr,SplitValue)$;

Add $t$ as the left child of $t^{\prime}$ ;

Add $node$ as the right child of $t^{\prime}$;

end if

else if  _$Max_{2} >0\&Max_{2}\geq Max_{1}$_ then

Set $splitAttr\leftarrow findAttributeWithMaxDistance(Dist_{2},Max_{2})$;

set $SplitValue\leftarrow(LB^{t}[splitAttr]+UB^{B}[splitAttr])/2$;

Create a node, $node\leftarrow CreateNode(splitAttr,SplitValue)$;

Add $t$ as the right child of $t^{\prime}$ ;

Add $node$ as the left child of $t^{\prime}$;

end if

end if

/*If there is overlapping exists between $t$ and $D^{B}$. */

else

Update $Dist_{1}\leftarrow UB^{B}-UB^{t}$;

Update $Max_{1}\leftarrow max(Dist_{1})$;

if  _$Max_{1} >0$_ then

Set $splitAttr\leftarrow findAttributeWithMaxDistance(Dist_{1},Max_{1})$;

set $SplitValue\leftarrow UB^{t}[splitAttr]$;

Create a node, $node\leftarrow CreateNode(splitAttr,SplitValue)$;

Add $t$ as the left child of $t^{\prime}$ ;

Add $node$ as the right child of $t^{\prime}$;

end if

Update $Dist_{2}\leftarrow LB^{t}-LB^{B}$;

Update $Max_{2}\leftarrow max(Dist_{2})$;

if  _$Max_{2} >0$_ then

Set $splitAttr\leftarrow findAttributeWithMaxDistance(Dist_{2},Max_{2})$;

set $SplitValue\leftarrow LB^{t}[splitAttr]$;

Create a node, $node\leftarrow CreateNode(splitAttr,SplitValue)$;

Add $t$ as the right child of $t^{\prime}$ ;

Add $node$ as the left child of $t^{\prime}$;

end if

end if

end

Step 3:

Return updated decision tree, $t^{\prime}$;

end

Algorithm 3 Procedure iSAT()

###  3.3 Complexity Analysis of ADF

We now analyse the computational complexity of ADF. We consider a batch data
set with $n$ records, and $m$ attributes. We also consider that the ensemble
size is $M$ where a tree can have $l$ leaves. Although, ADF iteratively
updates the trees based on each training batch data using Algorithm 1, we
present a complexity analysis of the algorithm for an iteration as follows.

In Step 1 of Algorithm 1, we build a decision forest by using an existing
algorithm such as RF [2] which has a complexity $O(Mnm^{2})$ [21]. In Step 2,
we find the number of perturbed leaves using Eq. 27 which has a complexity
$O(Mnml)$. In this step, we also repair the trees one by one by using the
RepairForest procedure (see Algorithm 2). For $M$ trees, the complexity of the
RepairForest() is $O(M(nm+\theta nm^{2}))\approx O(Mnm^{2})$. Thus, the
complexity of Step 2 of Algorithm 1 is $O(Mnml+Mnm^{2})\approx O(Mnm^{2})$ for
a small $l$. Step 3 of the algorithm has the same complexity.

In Step 4 of Algorithm 1, we update the window of batches that has a
complexity $O(\gamma{n})$. Similar to Step 1, Step 5 has a complexity
$O(M{n}m^{2})$ for a small $\gamma$. In Step 6, we either repair trees or
build new trees. The complexity of these operations is $O(Mnm^{2})$. Thus, the
overall complexity of Algorithm 1 is $O(Mnm^{2})$. This variant of ADF is
known as ADF-R.

ADF can also build a decision forest by using a decision tree algorithm such
as the Hoeffding Tree (HT) algorithm [12]. The complexity of the HT algorithm
is $O(nmlcv)$ [7], where $c$ is the number of class values and $v$ is the
maximum domain size of an attribute. Thus, for $M$ trees, ADF requires a
complexity $O(Mnmlcv)$. This variant of ADF is known as ADF-H. Typically, $c$,
$v$ and $l$ values are very small, especially compared to $n$. Therefore, the
complexity of ADF-H is $O(Mnm)$. We present the complexities of ADF variants,
CIRF, RF and ARF in Table 2.

Table 2: Complexity analysis. Proposed Method | Computational complexity | Existing Method | Computational complexity
---|---|---|---
ADF-R | $O(Mnm^{2})$ | RF |  $O(Mnm^{2})$ [21]
|  | CIRF |  $O(Mnm^{2})$ [3]
ADF-H | $O(Mnm)$ | ARF |  $O(Mnm(log(m)))$ [7]

##  4 Experimental Results and Discussion

We carry out a set of experiments to evaluate our proposed framework ADF. We
compare the performance of ADF with eight state-of-the-art machine learning
and incremental learning techniques, comprising two non-incremental forest
algorithms (namely RF [2] and SysFor [13]), two incremental tree algorithms
(namely Hoeffding Tree (HT) [12] and Hoeffding Adaptive Tree (HAT) [22] and
four incremental forest algorithms (namely LeveragingBag [23], OzaBag [8],
CIRF [3] and ARF [7]).

We implement ADF in the Java programming language using the Massive Online
Analysis (MOA) API [24]. The source code of ADF is available at GitHub
(https://github.com/grahman20/ADF). We test the ADF framework by using one of
the three techniques: RF [2], HT [12] and SysFor [13], and thereby obtain
three variants called ADF-R, ADF-H and ADF-S, respectively. We also implement
an existing technique called CIRF [3]. For implementing the RF and SysFor, we
use the Java code from the Weka platform [25]. All other methods are already
available in the MOA framework. We use the default settings of the methods
while running the experiment.

###  4.1 Data Sets

We apply the incremental learning techniques on five real data sets and one
synthetic data set, as shown in Table 3. The real data sets are available
publicly in the UCI Repository [14].

Table 3: Data sets at a glance. Data set | Records | Attributes | Number of class values | Classification accuracy | Data source
---|---|---|---|---|---
LDPA | 164,860 | 6 | 11 | 56% | UCI
UIFWA | 149,332 | 5 | 22 | 40% | UCI
EB | 45,781 | 5 | 31 | 66% | UCI
AReM | 42,239 | 7 | 7 | 63% | UCI
Avila | 20,867 | 11 | 12 | 51% | UCI
House | 300,000 | 10 | 7 | 80% | Synthetic

###  4.2 Simulation of Training and Test Batch Data Sets

For each data set, we artificially create 34 training and test batch data sets
in which we implement the five scenarios, namely SKC, MKC, SUC, MUC and MKUC
as discussed in Section 3 and presented in Eq. (9) and in Fig. 3. The process
of simulating scenarios and batches is summarized in Table 4.

We first divide a data set into two sub data sets, where each sub data set
contains approximately half of the total records of the data set and
approximately half of the class values. From the first sub data set, we create
3 batches (having the numbers from 9 to 11) that follow the SKC scenario in
which each batch contains records having a single class value. Similarly, from
the second sub data set, we create 3 batches (having the numbers from 12 to
14) which follow the SUC scenario as shown in Table 4.

We then build two decision trees: $T_{1}$ and $T_{2}$ by applying SysFor [13]
on the first and second sub data sets, respectfully. Using $T_{1}$ and
$T_{2}$, we then create the remaining 28 batches where the source of records
of each batch is described in the third column of Table 4. For each batch, we
create training and test batch data sets, where the test batch contains 20% of
records in which 10% of records are taken from the current batch and the
remaining 10% of records are taken from the previous two batches. Note that
all records in the training and test batches are chosen randomly.

Table 4: Simulation of batch data sets. Scenario | Batches | Source of records
---|---|---
MKC-1 | 1-4 |  |  25% of records are taken from the largest two leaves of $T_{1}$ and
---
75% of records are taken from the remaining leaves of $T_{1}$
MKC-2 | 5-8 |  |  75% of records are taken from the largest two leaves of $T_{1}$ and
---
25% of records are taken from the remaining leaves of $T_{1}$
SKC | 9-11 | Each batch contains records (from the first sub data set) having a single class value
SUC | 12-14 | Each batch contains records (from the second sub data set) having a single class value
MUC-1 | 15-18 |  |  25% of records are taken from the largest two leaves of $T_{2}$ and
---
75% of records are taken from the remaining leaves of $T_{2}$
MUC-1 | 19-22 |  |  75% of records are taken from the largest two leaves of $T_{2}$ and
---
25% of records are taken from the remaining leaves of $T_{2}$
MKUC-1 | 23-26 |  75% of records are taken from $T_{1}$ and 25% of records are taken from $T_{2}$
MKUC-2 | 27-30 |  25% of records are taken from $T_{1}$ and 75% of records are taken from $T_{2}$
MKUC-3 | 31-34 |  50% of records are taken from $T_{1}$ and 50% of records are taken from $T_{2}$

###  4.3 Experimental Settings

In our experiment, we use a number of parameters for ADF variants and existing
techniques. Most of the techniques use two common parameters, namely ensemble
size and minimum leaf size (or grace period). The ensemble size is set to 10
and the minimum leaf size for large data sets (i.e. the size of the data set
is greater than 100000) is set to 100; otherwise it is set to 20. For ADF, we
set the default values for $\lambda$, $\theta$, $\epsilon$, and $\gamma$ at
3,0.4, 0.02, and 3, respectively. Moreover, we use the majority voting [26]
method to calculate the final output of a decision forest.

###  4.4 Detail Experimental Results and Performance Analysis

We present the performances of ADF variants (ADF-H, ADF-R and ADF-S) and eight
existing techniques on 34 batches that are created from the LDPA data set in
Table 5. In the case of incremental methods, a classifier is built by applying
a method on the first batch training data and the classifier is repaired and
updated incrementally for the remaining batches. However, for non-incremental
methods, we rebuild the classifier for each batch training data. For both
types of methods, we obtain a classier for batch training data
${D^{t^{i}}_{B_{train}}}$. We then use the classifier to classify batch test
data $D^{t^{i}}_{B_{test}}$ and obtain classification accuracy. Bold values in
the table indicate the best results. Out of 34 batches, ADF-S performs the
best in 25 batches.

For each method, we also calculate the average classification accuracy which
is shown in the last row of Table 5. The average classification accuracies of
ADF-R and ADF-S are 0.640 and 0.682, respectively. From the experimental
results, it is clear that ADF-R and ADF-S outperform other methods on the LDPA
data set.

Table 5: Classification performances of ADF variants and existing methods on 34 batches of LDPA data set. Scenario | Batch No. | Batch Size | Non-incremental Forest | Incremental Tree | Incremental Forest
---|---|---|---|---|---
Training Data | Test Data | SysFor | RF | HT | HAT | LeveragingBag | OzaBag | CIRF | ARF | ADF-H | ADF-R | ADF-S
MKC-1 | 1 | 2613 | 803 | 0.707 | 0.690 | 0.247 | 0.247 | 0.247 | 0.247 | 0.707 | 0.262 | 0.690 | 0.690 | 0.707
2 | 3216 | 802 | 0.766 | 0.717 | 0.069 | 0.069 | 0.070 | 0.069 | 0.743 | 0.080 | 0.721 | 0.722 | 0.749
3 | 3205 | 801 | 0.758 | 0.730 | 0.213 | 0.705 | 0.664 | 0.642 | 0.742 | 0.690 | 0.720 | 0.727 | 0.740
4 | 3194 | 801 | 0.782 | 0.754 | 0.738 | 0.738 | 0.705 | 0.705 | 0.744 | 0.729 | 0.738 | 0.742 | 0.770
MKC-2 | 5 | 3391 | 845 | 0.783 | 0.773 | 0.749 | 0.749 | 0.737 | 0.753 | 0.756 | 0.753 | 0.749 | 0.748 | 0.750
6 | 3391 | 845 | 0.807 | 0.806 | 0.263 | 0.175 | 0.174 | 0.392 | 0.793 | 0.180 | 0.775 | 0.776 | 0.786
7 | 3360 | 845 | 0.793 | 0.786 | 0.199 | 0.176 | 0.180 | 0.299 | 0.780 | 0.196 | 0.759 | 0.761 | 0.759
8 | 3329 | 845 | 0.808 | 0.792 | 0.683 | 0.142 | 0.062 | 0.657 | 0.798 | 0.063 | 0.765 | 0.765 | 0.774
SKC | 9 | 4001 | 968 | 0.885 | 0.885 | 0.885 | 0.885 | 0.885 | 0.861 | 0.882 | 0.885 | 0.885 | 0.886 | 0.883
10 | 4001 | 968 | 0.551 | 0.551 | 0.551 | 0.551 | 0.551 | 0.550 | 0.614 | 0.551 | 0.476 | 0.699 | 0.745
11 | 1898 | 484 | 0.500 | 0.500 | 0.500 | 0.500 | 0.500 | 0.502 | 0.310 | 0.500 | 0.625 | 0.635 | 0.644
SUC | 12 | 4080 | 968 | 0.500 | 0.500 | 0.500 | 0.500 | 0.500 | 0.500 | 0.210 | 0.500 | 0.458 | 0.600 | 0.655
13 | 296 | 169 | 0.503 | 0.503 | 0.503 | 0.503 | 0.503 | 0.503 | 0.271 | 0.503 | 0.541 | 0.611 | 0.612
14 | 3904 | 968 | 0.500 | 0.500 | 0.500 | 0.500 | 0.500 | 0.500 | 0.276 | 0.500 | 0.692 | 0.590 | 0.590
MUC-1 | 15 | 3685 | 920 | 0.450 | 0.340 | 0.180 | 0.251 | 0.274 | 0.180 | 0.213 | 0.302 | 0.398 | 0.416 | 0.489
16 | 3685 | 920 | 0.549 | 0.505 | 0.495 | 0.297 | 0.297 | 0.490 | 0.340 | 0.272 | 0.495 | 0.641 | 0.660
17 | 3682 | 920 | 0.572 | 0.502 | 0.067 | 0.096 | 0.105 | 0.072 | 0.404 | 0.097 | 0.386 | 0.514 | 0.638
18 | 3679 | 920 | 0.524 | 0.501 | 0.316 | 0.172 | 0.150 | 0.316 | 0.395 | 0.155 | 0.368 | 0.517 | 0.629
MUC-2 | 19 | 3746 | 933 | 0.660 | 0.548 | 0.403 | 0.251 | 0.170 | 0.403 | 0.467 | 0.195 | 0.432 | 0.592 | 0.702
20 | 3746 | 933 | 0.662 | 0.606 | 0.027 | 0.098 | 0.099 | 0.027 | 0.525 | 0.107 | 0.414 | 0.599 | 0.712
21 | 3685 | 933 | 0.663 | 0.581 | 0.323 | 0.297 | 0.273 | 0.323 | 0.531 | 0.287 | 0.402 | 0.640 | 0.735
22 | 3624 | 933 | 0.554 | 0.544 | 0.066 | 0.194 | 0.136 | 0.066 | 0.466 | 0.134 | 0.407 | 0.583 | 0.680
MKUC-1 | 23 | 4714 | 1177 | 0.466 | 0.371 | 0.295 | 0.295 | 0.302 | 0.295 | 0.453 | 0.299 | 0.394 | 0.604 | 0.641
24 | 4714 | 1177 | 0.556 | 0.472 | 0.427 | 0.427 | 0.130 | 0.427 | 0.452 | 0.134 | 0.469 | 0.637 | 0.659
25 | 4714 | 1177 | 0.520 | 0.577 | 0.104 | 0.104 | 0.110 | 0.104 | 0.500 | 0.098 | 0.579 | 0.663 | 0.693
26 | 4714 | 1177 | 0.605 | 0.578 | 0.557 | 0.557 | 0.524 | 0.557 | 0.488 | 0.555 | 0.590 | 0.664 | 0.692
MKUC-2 | 27 | 4704 | 1176 | 0.554 | 0.418 | 0.177 | 0.177 | 0.253 | 0.177 | 0.508 | 0.221 | 0.413 | 0.603 | 0.671
28 | 4704 | 1176 | 0.561 | 0.429 | 0.026 | 0.026 | 0.103 | 0.026 | 0.530 | 0.131 | 0.420 | 0.599 | 0.655
29 | 4691 | 1176 | 0.558 | 0.442 | 0.016 | 0.110 | 0.119 | 0.016 | 0.431 | 0.102 | 0.329 | 0.557 | 0.625
30 | 4683 | 1176 | 0.554 | 0.389 | 0.168 | 0.201 | 0.159 | 0.168 | 0.500 | 0.143 | 0.317 | 0.566 | 0.607
MKUC-3 | 31 | 4920 | 1229 | 0.579 | 0.407 | 0.234 | 0.150 | 0.136 | 0.234 | 0.530 | 0.138 | 0.362 | 0.599 | 0.632
32 | 4811 | 1209 | 0.560 | 0.392 | 0.285 | 0.037 | 0.070 | 0.285 | 0.526 | 0.074 | 0.383 | 0.596 | 0.634
33 | 5338 | 1256 | 0.569 | 0.450 | 0.171 | 0.160 | 0.104 | 0.171 | 0.522 | 0.102 | 0.410 | 0.629 | 0.651
34 | 5814 | 1292 | 0.557 | 0.484 | 0.106 | 0.135 | 0.098 | 0.106 | 0.480 | 0.101 | 0.385 | 0.594 | 0.629
Average | 0.615 | 0.559 | 0.325 | 0.308 | 0.291 | 0.342 | 0.526 | 0.295 | 0.528 | 0.640 | 0.682

Similar to LDPA, for the remaining five data sets ADF variants achieve higher
classification accuracies than other existing techniques. Due to space
limitation, we present the average classification accuracies (see Table 6) and
execution times (see Table 7) of the ADF variants and eight existing
techniques on six data sets. Bold values in the tables indicate the best
results. From Table 6, we can see that ADF-R and ADF-S outperform the other
techniques in terms of classification accuracy for all data sets. However,
while ADF variants perform better than other techniques, the variants take
slightly more time than the ARF, CIRF, RF and SysFor. As accurate
classification is the primary goal in real applications, for handling dynamic
changes in both class and data distribution, ADF-R can be recommended over the
eight state-of-the-art techniques by considering the classification accuracy
and execution time.

Table 6: Overall classification accuracy of ADF variants and other existing methods on all data sets. Data set | Non-incremental Forest | Incremental Tree | Incremental Forest
---|---|---|---
SysFor | RF | HT | HAT | LeveragingBag | OzaBag | CIRF | ARF | ADF-H | ADF-R | ADF-S
LDPA | 0.615 | 0.559 | 0.325 | 0.308 | 0.291 | 0.342 | 0.526 | 0.295 | 0.528 | 0.640 | 0.682
UIFWA | 0.484 | 0.504 | 0.186 | 0.191 | 0.195 | 0.182 | 0.393 | 0.205 | 0.416 | 0.591 | 0.550
EB | 0.627 | 0.619 | 0.407 | 0.315 | 0.343 | 0.409 | 0.629 | 0.516 | 0.626 | 0.722 | 0.705
AReM | 0.714 | 0.729 | 0.327 | 0.311 | 0.285 | 0.346 | 0.650 | 0.289 | 0.522 | 0.838 | 0.818
Avila | 0.685 | 0.719 | 0.382 | 0.376 | 0.328 | 0.395 | 0.643 | 0.350 | 0.582 | 0.788 | 0.825
House | 0.801 | 0.802 | 0.390 | 0.339 | 0.354 | 0.402 | 0.720 | 0.351 | 0.853 | 0.860 | 0.867
Table 7: Overall execution time (ms) of ADF variants and other existing methods on all data sets. Data set | Non-incremental Forest | Incremental Tree | Incremental Forest
---|---|---|---
SysFor | RF | HT | HAT | LeveragingBag | OzaBag | CIRF | ARF | ADF-H | ADF-R | ADF-S
LDPA | 2651 | 1791 | 20 | 30 | 281 | 103 | 2062 | 938 | 1415 | 2901 | 3589
UIFWA | 1591 | 1584 | 70 | 185 | 369 | 657 | 1785 | 1149 | 1226 | 3287 | 3528
EB | 511 | 500 | 44 | 45 | 102 | 82 | 444 | 710 | 960 | 1357 | 1426
AReM | 790 | 427 | 62 | 103 | 363 | 137 | 929 | 477 | 654 | 959 | 1011
Avila | 288 | 222 | 28 | 37 | 157 | 70 | 808 | 424 | 506 | 643 | 917
House | 2673 | 2829 | 27 | 65 | 350 | 167 | 2292 | 1211 | 2135 | 3184 | 3395

To demonstrate the effectiveness of ADF framework, we also carry out
experimentation by rearranging the scenarios of the batches on LDPA and UIFWA.
In the new arrangement, we have 28 batches where the training and test batches
are created randomly. Table 8 presents the details about the rearrangement of
scenarios, and classification accuracies of ADF variants and existing
techniques on the LDPA data set. Bold values in the table indicate that ADF-S
performs the best in all batches.

Table 8: Accuracies of ADF variants and existing methods by rearranging the scenarios of the batches on LDPA data set. Scenario | Batch No. | Batch Size | Non-incremental Forest | Incremental Tree | Incremental Forest
---|---|---|---|---|---
Training Data | Test Data | SysFor | RF | HT | HAT | LeveragingBag | OzaBag | CIRF | ARF | ADF-H | ADF-R | ADF-S
MKC-1 | 1 | 2981 | 917 | 0.662 | 0.614 | 0.325 | 0.325 | 0.320 | 0.310 | 0.662 | 0.323 | 0.578 | 0.614 | 0.662
2 | 3669 | 916 | 0.689 | 0.624 | 0.107 | 0.107 | 0.180 | 0.218 | 0.664 | 0.175 | 0.592 | 0.652 | 0.689
3 | 3641 | 916 | 0.663 | 0.634 | 0.162 | 0.097 | 0.121 | 0.154 | 0.669 | 0.119 | 0.615 | 0.652 | 0.691
4 | 3613 | 916 | 0.638 | 0.549 | 0.393 | 0.540 | 0.512 | 0.400 | 0.632 | 0.550 | 0.541 | 0.607 | 0.662
MKC-2 | 5 | 4130 | 1029 | 0.739 | 0.704 | 0.335 | 0.227 | 0.230 | 0.333 | 0.731 | 0.225 | 0.702 | 0.725 | 0.758
6 | 4130 | 1029 | 0.765 | 0.758 | 0.732 | 0.756 | 0.756 | 0.703 | 0.781 | 0.750 | 0.756 | 0.765 | 0.786
7 | 4047 | 1029 | 0.794 | 0.777 | 0.511 | 0.052 | 0.056 | 0.511 | 0.811 | 0.055 | 0.777 | 0.791 | 0.814
8 | 3964 | 1029 | 0.794 | 0.779 | 0.751 | 0.779 | 0.779 | 0.724 | 0.796 | 0.779 | 0.780 | 0.787 | 0.810
MKUC-1 | 9 | 5457 | 1361 | 0.700 | 0.670 | 0.654 | 0.654 | 0.647 | 0.642 | 0.691 | 0.630 | 0.656 | 0.695 | 0.724
10 | 5457 | 1361 | 0.652 | 0.604 | 0.079 | 0.061 | 0.062 | 0.063 | 0.622 | 0.065 | 0.588 | 0.646 | 0.660
11 | 5457 | 1361 | 0.616 | 0.555 | 0.151 | 0.096 | 0.096 | 0.140 | 0.552 | 0.086 | 0.531 | 0.589 | 0.644
12 | 5457 | 1361 | 0.531 | 0.588 | 0.042 | 0.191 | 0.181 | 0.150 | 0.597 | 0.182 | 0.553 | 0.620 | 0.652
MKUC-2 | 13 | 5456 | 1361 | 0.526 | 0.482 | 0.172 | 0.159 | 0.080 | 0.133 | 0.491 | 0.097 | 0.357 | 0.478 | 0.589
14 | 5456 | 1361 | 0.582 | 0.445 | 0.258 | 0.202 | 0.217 | 0.247 | 0.453 | 0.238 | 0.266 | 0.525 | 0.600
15 | 5534 | 1361 | 0.580 | 0.519 | 0.155 | 0.244 | 0.055 | 0.149 | 0.425 | 0.265 | 0.285 | 0.525 | 0.609
16 | 5612 | 1361 | 0.589 | 0.506 | 0.179 | 0.245 | 0.051 | 0.195 | 0.405 | 0.259 | 0.300 | 0.544 | 0.598
MUC-1 | 17 | 4207 | 1049 | 0.557 | 0.459 | 0.214 | 0.046 | 0.079 | 0.187 | 0.410 | 0.269 | 0.341 | 0.582 | 0.605
18 | 4207 | 1049 | 0.594 | 0.470 | 0.331 | 0.097 | 0.152 | 0.291 | 0.396 | 0.131 | 0.380 | 0.583 | 0.605
19 | 4205 | 1049 | 0.520 | 0.501 | 0.362 | 0.238 | 0.310 | 0.308 | 0.418 | 0.384 | 0.425 | 0.609 | 0.619
20 | 4203 | 1049 | 0.575 | 0.447 | 0.417 | 0.421 | 0.409 | 0.416 | 0.404 | 0.407 | 0.410 | 0.624 | 0.628
MUC-2 | 21 | 4230 | 1056 | 0.631 | 0.618 | 0.342 | 0.303 | 0.086 | 0.331 | 0.517 | 0.080 | 0.398 | 0.634 | 0.667
22 | 4230 | 1056 | 0.696 | 0.599 | 0.277 | 0.325 | 0.147 | 0.270 | 0.564 | 0.149 | 0.402 | 0.666 | 0.726
23 | 4136 | 1056 | 0.632 | 0.563 | 0.334 | 0.186 | 0.252 | 0.363 | 0.578 | 0.272 | 0.386 | 0.677 | 0.728
24 | 4047 | 1056 | 0.635 | 0.656 | 0.349 | 0.194 | 0.325 | 0.323 | 0.580 | 0.281 | 0.366 | 0.671 | 0.728
MKUC-3 | 25 | 5740 | 1433 | 0.581 | 0.479 | 0.266 | 0.278 | 0.227 | 0.262 | 0.518 | 0.207 | 0.293 | 0.617 | 0.639
26 | 5618 | 1413 | 0.580 | 0.402 | 0.233 | 0.246 | 0.137 | 0.238 | 0.524 | 0.118 | 0.346 | 0.620 | 0.640
27 | 6242 | 1469 | 0.543 | 0.447 | 0.280 | 0.212 | 0.170 | 0.251 | 0.500 | 0.191 | 0.372 | 0.611 | 0.630
28 | 6817 | 1513 | 0.538 | 0.484 | 0.231 | 0.295 | 0.264 | 0.293 | 0.499 | 0.249 | 0.398 | 0.601 | 0.606
Average | 0.629 | 0.569 | 0.309 | 0.271 | 0.246 | 0.307 | 0.568 | 0.269 | 0.478 | 0.633 | 0.670

By rearranging the scenarios, we present the overall accuracies of ADF
variants and other existing methods on the LDPA and UIFWA data sets in Table
9. It is clear that ADF-R and ADF-S also outperform other techniques in terms
of classification accuracy after rearranging the scenarios of the batches.

Table 9: Overall accuracies of ADF variants and other methods on LDPA and UIFWA data sets by rearranging the scenarios. Data set | Non-incremental Forest | Incremental Tree | Incremental Forest
---|---|---|---
SysFor | RF | HT | HAT | LeveragingBag | OzaBag | CIRF | ARF | ADF-H | ADF-R | ADF-S
LDPA | 0.629 | 0.569 | 0.309 | 0.271 | 0.246 | 0.307 | 0.568 | 0.269 | 0.478 | 0.633 | 0.670
UIFWA | 0.493 | 0.518 | 0.114 | 0.092 | 0.112 | 0.119 | 0.409 | 0.117 | 0.413 | 0.565 | 0.540

###  4.5 Statistical Analysis of the Experimental Results

We now analyze the results by using a statistical non-parametric sign test
[27] and Nemenyi [28] test for all 34 batches to evaluate the statistical
significance of the superiority of ADF variants over the existing methods.

We carry out a sign test on the results of ADF-S with other methods (one by
one) at the right-tailed by considering significance level $\alpha=0.025$
(i.e. 97.5% significance level) as shown in Fig. 13. In the figure, each bar
represents the z-value of the comparison between ADF-S and an existing method,
whereas the line represents the z-ref value (which is obtained from a table
[27]). The sign test results (see Fig. 13) indicate that ADF-S performs
significantly better than the other methods (at $z>1.96$, $p<0.025$) on all
data sets. The cases where the performance of ADF-S is not significantly
superior are marked with down arrow signs on top of the bars. We also get
similar results for ADF-R.

Figure 13: Statistical analysis based on sign test on all datasets.

We also carry out the Nemenyi test on the results of ADF-S with other methods
(one by one) at the right-tailed by considering significance level
$\alpha=0.025$ (i.e. 97.5% significance level). The Nemenyi test results
indicate that both ADF-S and ADF-R perform significantly better than the other
techniques (at $p<0.025$) on all data sets.

###  4.6 Experimentation in Handling Big data using ADF

ADF can handle big data where the data can be divided into batches. For this
task, we consider two big data sets, namely LDPA and UIFWA (see Table 3).

For the LDPA data set, we create a training data set having 80% of the records
that are selected randomly, and a test data set having the remaining records.
To calculate the accuracy of the benchmark method such as Sysfor [13], we
build a decision tree by applying Sysfor [13] on the training data set and the
tree is used to classify the test records. The accuracy of the benchmark
method on the LDPA data set is 65.86% as shown in Table 10. Besides, for ADF,
we create 34 equal batch data sets where the records are chosen randomly from
the training data set of the LDPA data set. We build a decision tree by
applying Sysfor on Batch 1. The tree is then updated incrementally for the
remaining 33 batches. The final tree is used to classify the test records. The
classification accuracy of ADF on the LDPA data set is 61.88% (see Table 10).
We also calculate the accuracy of CIRF on the LDPA data set, which is 53.77%.

Similarly, for the UIFWA data set, the accuracies of the benchmark method,
CIRF and ADF are 45.90%, 35.77% and 40.91%, respectively, as reported in Table
10. For both data sets, the performance of ADF is better than CIRF and is
closer to the benchmark method. The experimental results on two data sets
indicate the effectiveness of ADF over CIRF for handling big data.

Table 10: Classification accuracy of ADF, CRIF and Benchmark methods on two big data sets. Data set | Benchmark (SysFor) | CIRF | ADF | Data set | Benchmark (SysFor) | CIRF | ADF
---|---|---|---|---|---|---|---
LDPA | 65.86% | 53.77% | 61.88% | UIFWA | 45.09% | 35.77% | 40.91%

##  5 Conclusion and future work

This paper introduced ADF, an incremental machine learning framework, which
produces a decision forest to classify new data. ADF can learn from new data
that arrive as batches over time and the data can have new classes. As
accurate classification is the primary goal in real applications, we argue
that an incremental decision forest algorithm can achieve high accuracy based
on three factors: identification of the best split, determination of trees
that need to be repaired, and identification and management of concept drift.
Based on our two novel theorems (see Theorem 2 and Theorem 3), we introduce a
novel splitting strategy called iSAT (see Section 3.1.1) which can find the
best split for new batch data. We also introduce a repairable strategy (see
section 3.1.2) to find trees that need to be repaired. Moreover, we build a
set of forests (see Section 3.1.3) to identify and handle concept drift and
preserve previously acquired knowledge.

The effectiveness of ADF is also reflected in the experimental results. In the
ADF framework, we build decision forests by using one of the three techniques:
RF [2], HT [12] and SysFor [13], and thereby obtain three variants called
ADF-R, ADF-H and ADF-S, respectively. We evaluate ADF variants on five
publicly available natural data sets [14] and one synthetic data set by
comparing its performance with the performance of eight state-of-the-art
techniques including HT [12], CIRF [3], and ARF [7]. From Table 6, we can see
that in all data sets ADF-R and ADF-S outperform the other techniques in terms
of classification accuracy, while the variants require a comparable execution
time. Statistical sign test and Nemenyi test results (see Fig. 13) indicate
that ADF-R and ADF-S perform significantly better than the other methods,
except one case, at $z>1.96$, $p<0.025$ on all data sets.

Our initial experimentation on two data sets (see Table 10) indicates that ADF
is also applicable to big data applications where the data can be divided into
batches. In future work, we plan to explore the applicability of ADF for the
non-dividable big data applications.

## References

  * [1] J. Gama, I. Žliobaitė, A. Bifet, M. Pechenizkiy, A. Bouchachia, A survey on concept drift adaptation, ACM computing surveys (CSUR) 46 (4) (2014) 44.
  * [2] L. Breiman, Random forests, Machine learning 45 (1) (2001) 5–32.
  * [3] C. Hu, Y. Chen, L. Hu, X. Peng, A novel random forests based class incremental learning method for activity recognition, Pattern Recognition 78 (2018) 277–290.
  * [4] C. Hu, Y. Chen, X. Peng, H. Yu, C. Gao, L. Hu, A novel feature incremental learning method for sensor-based activity recognition, IEEE Transactions on Knowledge and Data Engineering 31 (6) (2018) 1038–1050.
  * [5] M. Ristin, M. Guillaumin, J. Gall, L. Van Gool, Incremental learning of random forests for large-scale image classification, IEEE transactions on pattern analysis and machine intelligence 38 (3) (2015) 490–503.
  * [6] T. Mensink, J. Verbeek, F. Perronnin, G. Csurka, Distance-based image classification: Generalizing to new classes at near-zero cost, IEEE transactions on pattern analysis and machine intelligence 35 (11) (2013) 2624–2637.
  * [7] H. M. Gomes, A. Bifet, J. Read, J. P. Barddal, F. Enembreck, B. Pfharinger, G. Holmes, T. Abdessalem, Adaptive random forests for evolving data stream classification, Machine Learning 106 (9-10) (2017) 1469–1495.
  * [8] N. C. Oza, Online bagging and boosting, in: 2005 IEEE international conference on systems, man and cybernetics, Vol. 3, Ieee, 2005, pp. 2340–2345.
  * [9] M. Ristin, M. Guillaumin, J. Gall, L. Van Gool, Incremental learning of ncm forests for large-scale image classification, in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2014, pp. 3654–3661.
  * [10] J. Arvo, Transforming axis-aligned bounding boxes, in: Graphics gems, Academic Press Professional, Inc., 1990, pp. 548–550.
  * [11] S. Gottschalk, Separating axis theorem, Tech. rep., Technical Report TR96-024, Department of Computer Science, UNC Chapel Hill (1996).
  * [12] P. Domingos, G. Hulten, Mining high-speed data streams, in: Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, 2000, pp. 71–80.
  * [13] M. Z. Islam, H. Giggins, Knowledge discovery through sysfor: a systematically developed forest of multiple decision trees, in: Proceedings of the Ninth Australasian Data Mining Conference-Volume 121, Australian Computer Society, Inc., 2011, pp. 195–204.
  * [14] A. Frank, A. Asuncion, UCI machine learning repository, accessed August 25, 2020 (2010).
  * [15] X. Liu, G. Zhang, Y. Zhan, E. Zhu, An incremental feature learning algorithm based on least square support vector machine, in: International Workshop on Frontiers in Algorithmics, Springer, 2008, pp. 330–338.
  * [16] J. A. Suykens, J. Vandewalle, Least squares support vector machine classifiers, Neural processing letters 9 (3) (1999) 293–300.
  * [17] H. He, S. Chen, K. Li, X. Xu, Incremental learning from stream data, IEEE Transactions on Neural Networks 22 (12) (2011) 1901–1914.
  * [18] J. R. Quinlan, Induction of decision trees, Machine learning 1 (1) (1986) 81–106.
  * [19] L. Breiman, J. Friedman, R. Olshen, C. Stone, Classification and regression trees–crc press, Boca Raton, Florida.
  * [20] S. Boyd, L. Vandenberghe, Convex optimization, Cambridge university press, 2004\.
  * [21] J. Su, H. Zhang, A fast decision tree learning algorithm, in: Proceedings of the National Conference on Artificial Intelligence, Vol. 21, Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2006, p. 500.
  * [22] A. Bifet, R. Gavaldà, Adaptive learning from evolving data streams, in: International Symposium on Intelligent Data Analysis, Springer, 2009, pp. 249–260.
  * [23] A. Bifet, G. Holmes, B. Pfahringer, Leveraging bagging for evolving data streams, in: Joint European conference on machine learning and knowledge discovery in databases, Springer, 2010, pp. 135–150.
  * [24] A. Bifet, G. Holmes, R. Kirkby, B. Pfahringer, MOA: massive online analysis, J. Mach. Learn. Res. 11 (2010) 1601–1604.
  * [25] E. Frank, M. A. Hall, I. H. Witten, The weka workbench. online appendix for ”data mining: Practical machine learning tools and techniques” (2016).
  * [26] N. Jamali, C. Sammut, Majority voting: Material classification by tactile sensing using surface texture, IEEE Transactions on Robotics 27 (3) (2011) 508–521.
  * [27] R. D. Mason, D. A. Lind, W. G. Marchal, Statistics: an introduction, Duxbury Press, 1994.
  * [28] J. Demšar, Statistical comparisons of classifiers over multiple data sets, Journal of Machine learning research 7 (Jan) (2006) 1–30.