# Improved Anomaly Detection by Using the Attention-Based Isolation Forest
## 3 Preliminaries
### Isolation Forest  
In this subsection, the main definitions of iForest are provided in accordance with the results given in [16; 17]. Suppose that there is a dataset \(\mathcal{D}=\{\mathbf{x}_{1},\ldots,\mathbf{x}_{n}\}\) consisting of \(n\) instances, where \(\mathbf{x}_{i}=(x_{i1},\ldots,x_{id})\in\mathbb{R}^{d}\) is a feature vector. The isolation tree is built by using a randomly generated subset \(\mathcal{D}^{*}\) of the dataset \(\mathcal{D}\). The dataset \(\mathcal{D}^{*}\) splits into two subsets to define a random node as follows. A feature is randomly selected by generating a random value \(q\) from the set \(\{1,\ldots,d\}\). Then, a split value \(p\) is randomly selected from the interval \([\min_{i=1,\ldots,n}x_{iq},\max_{i=1,\ldots,n}x_{iq}]\). With \(p\) and \(q\), the subset \(\mathcal{D}^{*}\) is recursively divided into two parts at each node by using the feature number \(q\) and the split value \(p\)--the left branch corresponds to the set with \(x_{iq}\leq p\), and the right branch corresponds to the set with \(x_{iq}>p\). Thus, the generated values \(q\) and \(p\) determine whether the data points at a node are sent down the left or the right branch. The above conditions determine the subsequent child nodes for a split node. The division stops in accordance with a rule--for example, when a branch contains a single point or when some limited depth of the tree is reached. The process of building the isolation tree begins again with a new random subsample to build another randomized tree. After building a forest consisting of \(T\) trees, the training process is complete.  
In the \(k\)-th isolation tree, an instance \(\mathbf{x}\) is isolated on one of the outer nodes. A path of length \(h_{k}(\mathbf{x})\) associated with this instance is defined as the number of nodes for which \(\mathbf{x}\) goes from the root node to the leaf. Anomalous instances are those with a shorter path length in the tree. This conclusion is motivated by the fact that normal instances are more concentrated than anomalies and, thus, require more nodes to be isolated. By having the \(T\) trained trees, i.e., the isolated forest, we can estimate the isolation measure as the expected path length \(E[h(\mathbf{x})]\), which is computed as the mean value of the path lengths over all trees in the forest. By having the expected path length \(E[h(\mathbf{x})]\), an anomaly score is defined as  
\[s(\mathbf{x},n)=2^{-\frac{E(h(\mathbf{x}))}{c(n)}}, \tag{4}\]where \(c(n)\) is the normalizing factor, which is defined as the average value of \(h(\mathbf{x})\) for a dataset of size \(n\), which is computed as  
\[c(n)=2H(n-1)-\frac{2(n-1)}{n}. \tag{5}\]  
Here, \(H(n)\) is the \(n\)-th harmonic number estimated from \(H(n)=\ln(n)+\delta\), where \(\delta\approx 0.577216\) is the Euler-Mascheroni constant. If \(n=2\), then \(c(n)=1\).  
The higher the value of \(s(\mathbf{x},n)\) is (closer to 1), the more likely it is for the instance \(\mathbf{x}\) to be anomalous. If we introduce a threshold \(\tau\in[0.1]\), then the condition \(s(\mathbf{x},n)>\tau\) indicates that the instance \(\mathbf{x}\) is detected as an anomaly. If the condition \(s(\mathbf{x},n)\leq\tau\) is valid, then the instance \(\mathbf{x}\) is likely to be normal. The threshold \(\tau\) in the original iForest is taken as 0.5.