Article Preview
TopIntroduction
Social networks, mobile applications, and IoT produce an avalanche of data on a large scale and in an unpredictable way. Digital data explosion has forced researchers to find new ways to analyze and exploit the world, to manage new scalability issues about the capture, storage, analysis, and representation of data.
One interesting characteristic of these data is the big flows generated, arriving sequentially and at high speed. The analysis has to take place in real-time to handle these flows. A data stream is a real-time, continuous, and orderly sequence of elements. It is impossible to control the order in which data arrives, nor to locally store a stream in its entirety because the instances arrive at a high rate leading to a massive volume of data or even infinite (Rutkowski et al., 2020).
Data Stream Mining, or the exploration of data streams, is currently a very active field of research and is developing rapidly (Amudha et al., 2021, Bahri et al., 2021). Predictive analytics on data streams plays a primary role in modern data analytics. Data is streaming in and needs to be analyzed in real-time to make a future decision. One of the most common data mining methods for prediction is classification. The purpose of classification is to build a function, called a classifier, based on the data provided for training, which associates each element of data with a label, and then uses the classifier to classify (or predict) new unlabeled data. A spam filter is a good example where we want to predict if new emails are considered spam or not.
The decision tree is a data mining tool commonly used in data classification tasks. In the data stream field, The Hoeffding tree (HT) (Domingos and Hulten, 2000) is currently considered as the main decision tree. It is an incremental decision tree induction algorithm that is capable of learning from massive data streams. Hoeffding trees exploit the fact that a small sample can often be enough to choose an optimal splitting attribute. The approach was applied to different problems, such as (Choudhury (2020), Deepa et al. (2020), and Soe et al. (2020)).
Several researchers have been interested and are still interested in improving the Hoeffding tree algorithm according to various criteria (accuracy, execution time, memory usage, etc.). In this paper, the authors propose to explore the most recent related works on the Hoeffding tree algorithm. They are particularly interested in the Hoeffding AnyTime Tree algorithm (HATT) (Manapragada et al., 2018), which is considered the latest most promising algorithm in the literature. HATT attempts to select and perform a division as soon as it is confident enough that the division is useful. Then unlike HT, it will revisit that decision after some examples when a potential better division is available.
In this work, the authors intend to further enhance the performances of the HATT algorithm by proposing three improvements, which better exploit the ability to revise decisions. The authors test their variants through several experiments. The results show a precision very close to the original algorithm while considerably reducing the additional processing time.
The remainder of this paper proceeds as follows. It first introduces some basic concepts related to this work, more precisely, data stream characteristics and decision trees. The authors then present the Hoeffding Tree algorithm and its implementation, namely, Very Fast Decision Tree (VFDT). They discuss in the related work section the most relevant improvements of VFDT. The paper also presents some variants of the Hoeffding criteria. In the contribution section, the authors propose three improvements to the Hoeffding Anytime Tree. They then discuss their experimental results. Finally, they conclude and present some potential future works.