# A Filter Feature Selection Algorithm Based on Mutual Information for Intrusion Detection
## 3 Filter Feature Selection Algorithm  
This section consists of two parts. The first part introduces a new filter feature selection algorithm. The second part presents the theoretical analysis of the new algorithm and the comparison between the new algorithm and other algorithms. In the process of feature selection, many types of features containing sufficient information are selected from the original data to determine the output class. In MI-based feature selection proposed by [PERSON] [19], the task maximizes the relevance between the selected features from the original data and the output class and minimizes the redundancy of the selected features. In order to maximize the relevance between the selected features from the original data and the output class, \(I(C,f_{i})\) is computed. In order to minimize the redundancy of the selected features, the function of the redundant penalty between features (RPF) can be calculated as:  
\[RPF(f_{i},s_{j})=\frac{I(C,s_{j})}{I(C,f_{i})}\ I(f_{i},s_{j}) \tag{9}\]  
where \(I(C,f_{i})\) is the MI of class C and candidate feature \(f_{i}\). \(I(C,s_{j})\) is the MI of class \(C\) and selected feature \(s_{j}\); \(I(f_{i},s_{j})\) is the MI of candidate feature \(f_{i}\) and selected feature \(s_{j}\). Therefore, the feature selection criterion is:  
\[f^{+}=\text{argmax}\ _{f_{i}\in F}\{I(C,f_{i})-\frac{1}{|s|}\sum_{s_{j}\in S} RPF(f_{i},s_{j})\} \tag{10}\]  
where \(F=\{f_{1},f_{2},...,f_{n}\}\) is the original feature set of the input data, \(S=\{s_{1},s_{2},...,s_{k}\}\) is the selected feature set from the original feature set \(F\), \(|S|\) is the number of selected features in \(S\) and \(C=\{c_{1},c_{2},...,c_{n}\}\) is the class set of the output. Our algorithm named as the redundant penalty between features mutual information algorithm (RPFMI) can be described in Algorithm 1. ```
Input:\(F\leftarrow\) [initial set of all \(n\) original features], \(S\leftarrow\) [empty set] Output:\(S\gets S\cup\left\{f^{+}\right\}\)
01 for\(i=1;i\leq n;i++\)do
02 calculate \(H(C)\), \(H(f_{i})\), \(H(C,f_{i})\) and \(I(C,f_{i})\)
03 endfor
04 select the feature \(f^{*}\in F\) that maximizes \(I(C,f_{i})\)
05\(F\gets F\backslash\{f^{*}\}\) and \(S\leftarrow\{f^{*}\}\)
06 for\(f_{i}\in F\) and \(s_{j}\in S\)do
07 compute \(I(f_{i},s_{j})\) and \(I(C,s_{j})\)
08 endfor
09 while\(F\
eq\phi\)do
10 select the feature \(f^{+}\in F\) using Equation (10)
11\(F\gets F\backslash\{f^{+}\}\) and \(S\gets S\cup\left\{f^{+}\right\}\)
12 if\(F\
eq\phi\)do
13 for\(f_{i}\in F\) and \(s_{j}\in S\)do
14 compute \(I(f_{i},s_{j})\) and \(I(C,s_{j})\)
15 endfor
16 endif
17 endwhile
```  
**Algorithm 1** The Proposed New Algorithm. In Algorithm 1, \(H(C)\) is the information entropy of classes \(C\). \(H(f_{i})\) is the information entropy of candidate feature \(f_{i}\). \(H(C,f_{i})\) is the joint entropy of classes \(C\) and candidate feature \(f_{i}\). \(I(C,f_{i})\) is the MI of classes \(C\) and candidate feature \(f_{i}\). \(I(C,s_{j})\) is the MI of classes \(C\) and selected feature \(s_{j}\). \(I(f_{i},s_{j})\) is the MI of candidate feature \(f_{i}\) and selected feature \(s_{j}\). Given the importance of features and the relevance between features, the proposed selection feature algorithm can only rank the features and cannot optimally select the subset of the selected features. Therefore, we start with the best feature and incrementally add features to the classifier one by one. The final optimal feature subset is selected in the training data [32]. On the one hand, the proposed RPFMI algorithm is based on MI, which is the same as other algorithms, such as MIFS [19], mRMR [20], MIFS-U [21], CIMI [22], MMIFS [32] and FMIFS [33] methods. If other algorithms are valid, the proposed RPFMI algorithm is valid. The effectiveness of the proposed algorithm will be demonstrated with experimental results in Section 4.