## 2 Methods
### Feature Selection Algorithm  
This section describes the design of the FS algorithm based on MCMI. According to the analysis in Section 2.2, the algorithm consists of two processes: a greedy search and redundancy elimination, the framework of which is shown in Figure 1. In the first phase, a greedy search strategy is used to search for the candidate feature subset. In the second phase, a redundancy elimination strategy is utilized to eliminate redundant features from the candidate feature subset.  
Algorithm 1 presents the pseudocode for the FS algorithm based on MCMI. Below, a simplified description is provided to illustrate the process, along with explanations for each step's purpose:  
1. Initialization (line 1): Calculate the maximal mutual information (maxR) between the original feature set \(F\) and the target class \(c\), serving as a benchmark for the best possible mutual information. Initialize two sets: \(F_{list}\) to hold candidate features, and \(F_{opt}\) to store the optimal features selected through the algorithm.  
2. Candidate Selection (lines 2-4): Calculate the MI between each feature \(f_{i}\) in \(F\) and the target class \(c\), add features with MI > 0 to \(F_{list}\), and sort \(F_{list}\) by descending MI values. This ensures only informative features are considered.  
3. Greedy Search (lines 5-12): Iteratively select the feature with the highest conditional MI \(MI(c;f_{i}|F_{opt})\) from \(F_{list}\), add it to \(F_{opt}\), and remove features from \(F_{list}\) with conditional MI = 0. Repeat until \(MI(c;F_{opt})\) equals maxR. This ensures the selected feature set is the minimal subset with maximal relevance to the target class \(c\).  
4. Redundancy Elimination (lines 13-15): Evaluate each feature in \(F_{opt}\) for redundancy and remove features that do not significantly contribute to MI when conditioned on the remaining features. This ensures the final feature set is maximum relevant and non-redundant.  
5. Return the Optimal Feature Set (line 16): Return \(F_{opt}\) as the optimal feature set.  
As shown in Algorithm 1, the greedy search strategy involves a major part of computational effort, and its time complexity has a non-linear relationship with the number of original features (dimensionality \(N\)). In the best case, the time complexity of the greedy search is \(O(N)\) when only one feature is selected as a candidate feature. In the worst case, it has a time complexity of \(O(N^{2})\) when all features are selected as candidate features. However, in general, the time complexity of the greedy search strategy is much lower than the sequential forward selection (SFS) strategy because, in each iteration, irrelevant or conditionally irrelevant features are removed and not passed to the next iteration. This characteristic significantly reduces the computational burden compared to SFS, especially for high-dimensional datasets. In addition, the time complexity of the greedy search strategy is also influenced by the interdependence of the features in the original feature set. The more features are deleted in earlier iterations, the faster the greedy search strategy becomes. On the other hand, the redundancy elimination strategy has a linear time complexity in terms of the number of candidate features selected by the greedy search strategy.  
Figure 1: Framework of FS.