# Machine Learning and Deep Learning Methods for Intrusion Detection Systems: A Survey
## 3 Common Machine Learning Algorithms in IDS
### Machine Learning Models
#### 3.1.1 Shallow Models
Kernel tricks are widespread among both SVMs and other machine learning algorithms. **K-Nearest Neighbor (KNN)**. The core idea of KNN is based on the manifold hypothesis. If most of a sample's neighbors belong to the same class, the sample has a high probability of belonging to the class. Thus, the classification result is only related to the top-k nearest neighbors. The parameter \(k\) greatly influences the performance of KNN models. The smaller k is, the more complex the model is and the higher the risk of overfitting. Conversely, the larger \(k\) is, the simpler the model is and the weaker the fitting ability. **Naive Bayes**. The Naive Bayes algorithm is based on the conditional probability and the hypothesis of attribute independence. For every sample, the Naive Bayes classifier calculates the conditional probabilities for different classes. The sample is classified into the maximum probability class. The conditional probability formula is calculated as shown in Formula (1). \[P(X=x|Y=c_{k})=\prod_{i=1}^{n}P(X^{(i)}=x^{(i)}|Y=c_{k}) \tag{1}\]  
When the attribute independence hypothesis is satisfied, the Naive Bayes algorithm reaches the optimal result. Unfortunately, that hypothesis is difficult to satisfy in reality; hence, the Naive Bayes algorithm does not perform well on attribute-related data. **Logistic Regression (LR)**. The LR is a type of logarithm linear model. The LR algorithm computes the probabilities of different classes through parametric logistic distribution, calculated as shown in Formula (2). \[P(Y=k|x)=\frac{e^{\imath\
u_{k}x}}{1+\sum_{k}^{K-1}e^{\imath\
u_{k}x}} \tag{2}\]  
where \(k\) = 1,2...\(K-1\). The sample \(x\) is classified into the maximum probability class. An LR model is easy to construct, and model training is efficient. However, LR cannot deal well with nonlinear data, which limits its application. **Decision tree**. The decision tree algorithm classifies data using a series of rules. The model is tree like, which makes it interpretable. The decision tree algorithm can automatically exclude irrelevant and redundant features. The learning process includes feature selection, tree generation, and tree pruning. When training a decision tree model, the algorithm selects the most suitable features individually and generates child nodes from the root node. The decision tree is a basic classifier. Some advanced algorithms, such as the random forest and the extreme gradient boosting (XGBoost), consist of multiple decision trees. **Clustering**. Clustering is based on similarity theory, i.e., grouping highly similar data into the same clusters and grouping less-similar data into different clusters. Different from classification, clustering is a type of unsupervised learning. No prior knowledge or labeled data is needed for clustering algorithms; therefore, the data set requirements are relatively low. However, when using clustering algorithms to detect attacks, it is necessary to refer external information. K-means is a typical clustering algorithm, where K is the number of clusters and the means is the mean of attributes. The K-means algorithm uses distance as a similarity measure criterion. The shorter the distance between two data objects is, the more likely they are to be placed in the same cluster. The K-means algorithm adapts well to linear data, but its results on nonconvex data are not ideal. In addition, the K-means algorithm is sensitive to the initialization condition and the parameter \(K\). Consequently, many repeated experiments must be run to set the proper parameter value. **Ensembles and Hybrids**. Every individual classifier has strengths and shortcomings. A natural approach is to combine various weak classifiers to implement a strong classifier. Ensemble methods train multiple classifiers; then, the classifiers vote to obtain the final results. Hybrid methods are designed as many stages, in which each stage uses a classification model.