## 4 Materials and Methods
### Decision Trees and Random Forest  
Decision trees (DTs) can be used to solve both classification and regression problems and are particularly useful when the data have complex non-linear relationships. DT can be a powerful tool for building intrusion detection technologies, such as firewalls and IDS [45; 46; 47]. However, DT can be prone to overfitting and can have high variance, which can be addressed by techniques such as pruning or the ensemble method. In this research, we have implemented two DT algorithms--ID3 and CART--and a random forest composed from a set of CART-types trees.  
The ID3 (Iterative Dichotomiser 3) algorithm uses Information Gain (IG) to find the best feature to split the data at each node of the decision tree. Information Gain is a measure of the reduction in entropy that can be achieved by splitting the data on a particular feature. The feature with the highest IG was chosen as the split feature at each node, as it is expected to provide the most useful discrimination between the different classes.  
\[Entropy(S)=-\sum_{i=1}^{n}p_{i}\cdot log_{2}(p_{i}), \tag{4}\]  
where \(S\) represents the dataset that entropy is calculated, \(i\) represents the classes in set, and \(p_{i}\) represents the proportion of data points that belong to class \(i\) to the number of total data points in set \(S\). The Information Gain formula is provided below:  
\[IG(S,A)=Entropy(S)-\sum_{v\in Values(A)}\frac{|S_{v}|}{|S|}Entropy(S_{v}), \tag{5}\]  
where \(S_{v}\) is the set of rows in \(S\) for which the feature column \(A\) has value \(v\), \(\mid S_{v}\mid\) is the number of rows in \(S_{v}\) and likewise \(\mid S\mid\) is the number of rows in \(S\).  
CART (Classification and Regression Trees) is another DT algorithm that can handle both categorical and continuous input variables and is less prone to overfitting than ID3. CART is used for binary splitting, which involves splitting the data into two groups based on the value of a single input variable. To perform binary splitting, the algorithm first evaluates the _Gini_ impurity index:  
\[Gini=1-\sum_{i=1}^{C}(p_{i})^{2}, \tag{6}\]where \(C\) is the total number of classes, and \(p_{i}\) probability of selecting a data point with class \(i\). The \(Gini\) impurity of a pure node (the same class) is equal to zero.  
A random forest (RF) is a decision tree-based algorithm that uses an ensemble of decision trees to make predictions [48]. Moreover, it is a very popular technique for network intrusion detection [46; 49]. In our case, employing RF, several CART-type decision trees were created using randomly selected subsets of training data and features. Each tree in the forest made a prediction based on the values of the features and provided a class label. The final prediction of the random forest was the dominant class.  
\[RF=f(DT_{1},DT_{2},\dots,DT_{n}) \tag{7}\]  
where \(f=\textit{mode}\), n-number of trees \(DT\) in random forest. The _mode_ function returns the most frequently occurring predicted class across all trees.  
Theoretically, the \(RF\) algorithm has several advantages over a single decision tree in that it can handle high-dimensional, less balanced datasets with many attributes and can reduce overfitting. For this purpose, regularization, bagging and boosting techniques have been applied, as well as pre-pruning methods, which involve setting conditions for the growth of decision trees during the construction of the forest.