dataesr/scientific-paragraphs-categorization huggingface dataset:
A. TRAINING PHASE The main objective of the training phase is to build a forest of random and independent trees (itree). ψ and t are key parameters of IForest. IForest randomly selects a subset of ψ data which constitutes the sample used to build a single tree. This step is very important, because it is the key idea behind the performance and the efficiency of IForest. IForest randomly chooses ψ data from X without replacement. It is important to note that each sample is only used for one tree. Since the data are chosen randomly and the anomalous data are assumed to be very few in comparison with the normal data, the sample may contain only normal data or a mixture of mostly normal data. The isolation tree (itree) is a binary tree. The construction of the tree is realized as follows: Initially, the root node contains all of the sample data.
To build the t trees of the forest, these two steps (sampling and building a tree) are repeated t times. Thus, each tree has its dedicated sample. For each itree, the sample is chosen from the entire X dataset. The complexity of the training phase is given by O(tψ log ψ) because each item of the ψ data items of the t trees must be isolated or quasi-isolated in the associated tree. The number of trees t is a key parameter for the performance of IForest.
B. SCORING PHASE During the scoring phase, the score for each item of the X dataset is calculated. This score represents the similarity degree between this item and the other items (mostly composed of normal data). To calculate this score, the item x, has to be treated by each tree of the forest. At the end, the item x will certainly be placed in an external node of each tree, depending on the split criteria. The number of nodes crossed by x from the root node to reach its external node is called the path length of x, denoted h(x). The pseudo-code calculating the path length of x in a tree is given in the algorithm 2. Once x is processed by all the trees in the forest, IForest calculates the average length of the t paths of x denoted by E(h(x)). Using a well known result on Binary Search Tree (BST), the authors generate the score s(x, n) of x with the following formula: With this score formula, the authors classify the data as follows: s(x, n) = 2 -E(h(x)) C(n) ; C(n) = 2H (n -1) -(2(n -1)/n) is • If E(h(x)) → C(n), s → 0.
5. If all instances have a score of s ≈ 0. 5 then the dataset does not contain any identifiable anomaly; • If E(h(x)) → 0, s → 1. If an item x has score very close to 1 then it is an anomaly; • If E(h(x)) → n -1, s → 0. If an item x has a score s much lower than 0. 5 then it is normal data. A relatively short average path length E(h(x)) implies that the forest of t trees globally classifies x as an anomaly. The complexity of the scoring phase is given by O(nt log ψ) because each item of the dataset of size n is processed by the t trees in the forest to evaluate its path length and thus generate its average depth then its score. Hence, IForest has linear complexity, proportional to the size of the dataset (n), as t and ψ are two input constant parameters. Swamping and masking represent a real challenge for IForest, which handles them up to a certain limit.
Swamping consists of classifying normal data as anomalies because of similarity between these two types of data. When normal data q ← random choice of one attribute in Q (q ∈ Q) 6 p ← random choice of one value between the min and the max of x values for q 7 l ← filter(X , q < p) are very close to anomalies, the number of partitions required to separate anomalies increases, making it more difficult to distinguish anomalies from normal data. Masking is the existence of a large number of similar anomalies making it difficult to isolate them individually. When a group of anomalies is large and dense, the number of partitions needed to isolate each anomaly increases  [22]. These abnormal data may therefore be considered as normal. The fact that IForest relies on random samples and not on the entire dataset to build the forest of random trees helps handling masking and swamping.
To separate the different clusters, SCiForest establishes a split criterion for each node taking into account the standard deviation of the data for this node. Even if the processing of SCiForest is adapted to complex data, SCiForest has a high complexity which represents a major drawback for this method. In the same context about the manner to split data in the node, authors proposed in  [17]  the Extended IForest algorithm (EIF). EIF corrects the bias introduced in IForest because of the vertical or horizontal splitting of the nodes which creates an inconsistency in the scores provided by IForest. This method is further discussed in section IV. In  [31] , the authors recently proposed the FIF (Functional IForest) method to detect anomalies in functional datasets. Starting from the observation that IForest is not efficient for any dataset distribution,  [25]  proposed the Hybrid IForest (HIF) method.
They added a new decision criterion taking into account the similarity between the data of the same leaf node in order to consider the risk that abnormal data are located in a leaf node having a relatively long path. The main objective of this additional step is to reduce false negatives. In fact, in the original version of IForest, some anomalies can be missed because of their similarity: this is the masking effect previously explained. Combining supervised and unsupervised techniques, HIF is able to detect anomalies in various datasets with different distributions. However, it is not always easy to obtain the labels for a supervised anomaly detection. In  [8] , authors used IForest to compute the path length of each data in the trees and defined this metric as a new distance between two points.
Compared to other distance methods like Euclidean distance or Manhattan distance, it is more robust. It also offers an adaptation of IForest for categorical and missing data. Simulated Annealing IForest (SA-IForest)  [34]  is an improvement of IForest which consists of creating a more stable and stronger forest in the training phase. To do this, SA-IForest builds a first forest from IForest. Then they calculate the similarity between the trees in the forest. The precision of the trees is also calculated by cross validation. At the end of the process, only the trees with high precision are retained. The validation requires the labeling of the training data which is not always obvious and represents the limit of this semi-supervised method. To overcome the problem of inefficiency of IForest when the number of data dimensions increases, the Entropy IForest (E-IForest) method has been proposed in  [21].
This method also manages the lack of robustness of IForest in case of noisy data. According to the authors, the problem lies in the choice of the attribute of splitting of the data at the level of each node of the tree. Indeed, they proposed an evolution of IForest based on entropy. When splitting nodes, E-IForest chooses an attribute based on its entropy in the random sample. Different strategies have been explored in this paper for the choice of the best attribute. In  [36] , the authors noticed that although it is claimed that IForest is not based on any notion of distance or density, as it performs successive splits along random dimensions, it implicitly uses the Manhattan distance. IForest, in its original version, is therefore limited to this distance measure and cannot handle other distance measures.
Authors then proposed the generic framework called LSHIForest (Locality-Sensitive Hashing IForest  [36] ) that generalizes IForest to other measures of distance and data spaces. Sampling from an unbalanced dataset where normal data presents the majority is not obvious. There are several ways to balance the dataset before sampling. These methods can be classified into two categories: over-sampling (padding the minority class with synthetic datasets) or under-sampling (removing datasets from the majority class for a better balance). Over-sampling can be performed with a method called SMOTE. In  [37] , authors used IForest to identify categories of data and rank them. Then, with SMOTE, they created new padding data based on neighborhood information. Thus IForest-SMOTE makes it possible to balance a dataset by creating new data using a preselection from IForest and the SMOTE method.
B. DATA STREAM Neither IForest nor its different improvements mentioned above are suitable for the context of data streams, where data are received continuously and are volatile. Isolation Forest Algorithm for Streaming Data (IForest ASD)  [9] , Half-Space Trees (HSTrees)  [32]  and PCB-iforest  [18]  are adaptations of IForest to the context of data streams. IForest ASD uses a sliding window technique to retrieve data and in each window the IForest method is executed to detect anomalies based on a model previously created with data from the previous windows. In case of drift, this model is reinitialized. HSTrees is an evolution of IForest, designed for streaming. HSTrees splits the nodes using the average of the node items for the randomly selected attribute. As a result, unlike IForest ASD, HSTrees manages automatically the concept drift (  [12] ,  [13] ) without updating its model by a reinitialization.
Indeed, HSTrees is faster than IForest ASD and builds its model independently of the considered dataset. However IForest ASD, is closely related to the dataset. In fact, to manage the concept drift, IForest ASD maintains an input value (µ) which is the anomaly rate. When, in a given window, the anomaly rate exceeds µ, IForest ASD assumes that a change occurs in the normal behavior of the data (the drift) and therefore updates the model with the data of the current window. This update consists of deleting the model and rebuilding a new model based on the data from the current window. This approach is not very efficient because the whole history of the normal behavior is lost with each concept drift. Randomized space trees (RS-Forest)  [33]  is also a method of detecting anomalies in data flows based on the concept of isolation.
It is based on a density estimator used to decide if necessary to update the model to manage the concept drift. RS-Forest is based on the assumption that the anomalous data have a low density, which joins the hypothesis previously discussed on the scarcity of the anomalous data, their difference from each other and also from normal data. In  [2] , authors provided a recent global review on treebased methods for anomaly detection. In this part, we only focus on Isolation based anomaly detection methods. A summary of the previously described isolation-based anomaly detection methods is given in figure  3. The isolation-based anomaly detection methods have been implemented in several frameworks. The most known being scikit-learn 1 which focuses on static data. It implements the IForest algorithm.
An other implementation of IForest is provided by the H20 framework 2 which is also very well known in the machine learning domain. Some versions suitable for data streams like HSTrees  [32]  and IForest ASD  [9]  have been implemented in the open source framework scikit-learn multiflow  [27]  3 which is the streaming version of scikit-learn. A cloud-based anomaly detection framework is proposed in  [16]. It uses Spark cluster and some user interfaces, all managed by Kubernetes. Since the design of IForest in 2008, different improvements have been proposed. In this section, we presented all the extensions and adaptations of IForest existing in the literature. In this paper, we propose an improvement of IForest to reduce its execution time while maintaining the same detection efficiency. Unlike other methods, our proposed method does not need any additional computation.
IV. EXTENDED ISOLATION FOREST A. IFOREST LIMITATION ADDRESSED IForest is a powerful method, but it has some drawbacks. One of the limitations of IForest which has been addressed in the literature is its inconsistency in the classification of data. Indeed, IForest gives a score to each data. According to the definition of the anomaly, we expect that the more the data is different from the others, the higher is its score. But this is not always the case with the scores given by IForest. Thus, there is some inconsistency in the design of IForest scores. In order to illustrate this weakness, we considered in the figure 4 a 2-dimensional datasets uniformly distributed on a ring. Anomalies are placed in the center of the ring. This distribution is invariant by rotation. After executing IForest, we represented the heat map which corresponds to the scores assigned by IForest.
Areas with a high density points have a low score and are therefore considered as normal data areas. The homogeneous light color in the center of the heat map gives the impression that the data is distributed on a disc and ignores the ring shape with an almost empty center. Far from dense areas, scores become higher. We can clearly see the edge effect on the border areas, as well as darker areas which correspond to empty areas. However, the heat map does not have the same symmetry as the data. The heat map is not invariant by rotation. More precisely, the ring has turned into a square, and we can see the artificial appearance of four dark corners with very high scores. These areas are considered as anomalies. This situation is due to the way IForest splits the nodes during the training phase.
Indeed, IForest splits each node vertically or horizontally. This creates artificial areas of concentration as if other data were there. Figure  4  shows an example of splitting nodes when building a forest tree. Note that the different splits of the dataset form artificial rectangular areas of high density outside the ring of the dataset. 3 https://scikit-multiflow. readthedocs. io/en/stable/api/api. html An evolution of IForest that overcomes this problem is EIF. The key idea of EIF is to split the data of the node according to a randomly chosen direction (not necessarily horizontal or vertical like IForest). This eliminates the fictitious zones created by IForest and consequently improves the consistency of the scores.
B. THE EIF METHOD As explained in the section II, in case of 2-dimensional data, IForest splits each node horizontally or vertically (see figure  1 ). This breakdown creates a bias clearly visible on the heat map of the scores. The method called Extended Isolation Forest which aims to correct this inconsistency was proposed in  [17]. The major difference between EIF and IForest is the way to split the data in a node. EIF contains two stages, just like IForest: the training phase and the scoring phase. While the scoring phase remains the same for both methods, the training phase has changed significantly. Indeed, EIF splits the nodes according to a point and a direction randomly chosen by the combination of all the dimensions unlike IForest. An example of data splitting using EIF is shown in figure  5  where we can notice the oblique and random splitting of the nodes.
A heat map of the scores obtained for the same dataset is shown in this same figure. Just like for IForest, in this experiment, we used all of the data (normal and abnormal) to construct the tree samples, during the training phase. We can notice the perfect correspondence between the distribution of the data and the colors of the heat map. The circular shape is conserved by the heat map of the scores. The areas of fictitious concentration, previously visible with IForest, have disappeared. In addition, the color of the center of the ring (relatively dark) reflects clearly the ring shape and with data items in the center, and provides more precision than IForest. So, this heat map conforms to the real distribution of the initial dataset. In larger dimensions, EIF keeps the same operating principle.
The nodes are split according to a random hyperplane defined by a normal vector n and a point p called the intercept point. Node's data are distributed as follows: for any data x, if ( xp). n ≤ 0 then x is classified in the child node on the left otherwise it is assigned to the child node on the right. Although EIF addresses the inconsistency of IForest for the score, this method has some limitations that should be taken into account. EIF significantly reduces the false alert rate of IForest. However, in terms of anomaly detection it does not always outperform IForest. A comparison of the two methods is carried out in the subsection VIII.
A. PUBLIC DATASETS The real datasets considered are public and often used in the field of anomaly detection. They consist of labeled data containing identified anomalies. Since IForest is an unsupervised method, labels are not considered in the execution phase. They are used only for the evaluation of the results (specificity, ROC AUC. ). These datasets are taken from the UCI Machine Learning Archive  [10] , owned by the University of California. This archive is a very useful resource for testing, validating and comparing different Machine Learning algorithms. We selected four datasets with different characteristics in terms of size, number of dimensions and anomaly rate as shown in the table 1. HTTP and SMTP are datasets taken from the large KDD-CUP99 competition dataset. They describe networks intrusions.
Shuttle is a dataset of 9 attributes collected by NASA, containing information on radars. This is the dataset that contains the highest proportion of anomalies. ForestCover is a dataset describing trees in four different areas of the Roosevelt National Forest in Colorado. It contains 10 attributes giving information on tree type, shadow coverage, distance from nearby landmarks (roads, etc. ), soil type as well as local topography. We used the same dataset as in  [9] : The HTTP and the SMTP datasets have been pre-processed to keep only four relevant attributes (service, duration, src-bytes, dst-bytes) among the original 41 attributes. For these two datasets, anomalies refer to networks attacks. The pre-processed method is described in  [9]. The original KDD-CUP99 dataset contains 4,898,431 data, including 3,925,651 attacks (80.
B. SYNTHETIC DATASETS In order to test the behavior and sensitivity of IForest to different variations in data characteristics, we used synthetic datasets. Indeed, real datasets often contain anomalies carried by a single attribute and do not allow a detailed analysis of the impact of certain parameters. We thus varied, on the synthetic datasets, the dimensions of the data, the density of the normal and abnormal data as well as the distance between the anomalies and the normal data. These configurations make it possible to evaluate the limits of IForest and to adjust the choice of its input parameters. In the case of multivariate data, we have designed anomalies carried by all the dimensions at the same time, well enveloped in the normal data. The designed synthetic datasets are presented, in two dimensions, in the form of a ring where the normal data are uniformly distributed.
Abnormal data are located in the center of the ring, uniformly distributed on a disk of smaller radius. In three dimensions, the normal data are contained in the thick envelope of a sphere and anomalies are regrouped in the center of the sphere, uniformly distributed in a smaller sphere. The abnormal data are therefore each time surrounded by normal data. The anomalies are not trivial which makes it possible to test the limits of the detection algorithms. The different used datasets are presented in figures 6 and 7. Abnormal data are in red and normal data in blue. All datasets consist of 1500 normal data and 15 (1%) abnormal data. The coordinates of each data item are randomly chosen in the distribution described above. We variated the thickness of the ring and the radius of the central sphere to test different densities and distances between normal data and anomalies as shown in table 2.
The source code building the synthetic datasets can be found on github https://github. com/Elmecio/IForestStudyAndMVIForest. The dataset named Synthetic_1 is shown in figure  6. It is characterized by a high density of normal data and a small distance between normal data and anomalies. The dataset named Synthetic_2 is shown in figure  7a. Here, we just increased the thickness of the ring to evaluate the impact of decreasing the density of data on the performance of IForest. The distance between normal and abnormal data remains quite small. The Synthetic_3 dataset (figure  7b ) is characterized by a high density of normal data and a large distance between normal and abnormal data. In the Synthetic_4 dataset (figure  7c ), we kept the large distance between normal and abnormal data, this time with a low density of normal data.
The purpose of the Synthetic_5 dataset (figure  7d ), is to test the effect of the previously discussed masking. We therefore designed anomalies with a high similarity, by significantly reducing the radius of their disc. Anomalies are more concentrated in the center of the ring. We summarize the characteristics of these synthetic datasets in table 2. For each of these datasets, we also created the corresponding three-dimensional dataset as explained for Synthetic_1 in figure  6.
2) MEMORY REQUIREMENT IForest has a low memory requirement equal to O(tψ) (see  [24] ). The memory consumed is therefore constant, independent of the size of the dataset, which represents a considerable advantage of the method to process large data. 3) ROC AUC, RECALL, SPECIFICITY, F1 SCORE, FALSE ALARM RATE In the case of anomaly detection which is an exercise of binary classification in imbalanced datasets, there are only two possible classes: normal or abnormal. In this paper, we used scikit-learn  [29]  framework. However, unlike definitions implemented in scikit-learn, we consider here the following well known convention adopted by anomalies detection community: normal class is denoted by Negative and abnormal class refers to Positive. We used scikit-learn API to compute recall, ROC AUC and F1 score from the confusion matrix.
1) DECISION THRESHOLD IForest is based on a score, denoted by s(x) , which is calculated for each data x on the basis of the average length of its trajectory E(h(x)) in the different trees. In the original IForest paper  [22] , the authors recommend 0. 5 as the decision threshold applied to the s score. Indeed, • if E(h(x)) → 0 then s → 1. When s is very close to 1, x can be considered as an anomaly; • if E(h(x)) → n -1 then s → 0. When s 0. 5, x can be considered as normal data. There is clearly a lack of precision of the threshold from which a given data should be considered as abnormal. This weakness represents a first limitation of IForest.
2) CHOICE OF PARAMETERS OF IForest IForest has two input parameters: sample size and number of samples. In  [22]  and  [24] , the authors recommendation is to set ψ to 256. According to their experiences, ψ = 256 gives good results with low execution time and low memory requirement. The authors recommend to set t to 100 trees for stable results. They demonstrate that with 100 trees, the result is optimal and that beyond 100 trees, there is no gain in performance but the execution time and memory consumption increase logically. The experiments show that the performance of IForest at the detection level (specificity, recall, AUC) depends on these parameters. The optimal choice of these parameters depends on the characteristics of the considered dataset. Indeed, the sample size has a considerable effect on the performance of IForest.
On the one hand, a large sample size (or a high sampling rate) can engender an over-training. Indeed, we obtain in this case a great similarity between the trees, which is in contradiction with the forest of random and independent trees. On the other hand, a very low sampling rate generates a risk of under-learning (a sample not enough representative of the whole dataset and very shallow trees that could isolate any anomaly). It is therefore important to adjust the sample size, especially since it represents a key input parameter for the IForest method. We deal with this limit in the subsection VI-C.