Online group streaming feature selection using entropy-based uncertainty measures for fuzzy neighborhood rough sets

Dynamic feature selection can be divided into feature selection with feature streams and data streams [13‐18]. Online feature selection with a feature stream assumes that features flow into the feature space in batches over time, which can be further segmented into individual streaming feature selection and group streaming feature selection based on the structural information of the features [19‐22].

Online individual streaming feature selection is characterized by features arriving in the feature space one by one [23‐28]. Perkins et al. [29] first implemented feature selection in an online manner using a fast gradient-based heuristic. Wu et al. [30] proposed a streaming feature selection framework consisting of both online correlation analysis and online redundancy analysis. Zhou et al. [31] considered the interactions between features and efficiently selected features with interactions. Eskandari et al. [32] first proposed a new streaming feature selection method based on rough sets theory and improved it in [33]. Lin et al. [34] introduced fuzzy mutual information in multilabel learning to evaluate the quality of features for streaming feature selection scenarios. You et al. [35] proposed a causal feature selection algorithm for online streaming feature selection scenarios. The above methods can only handle the scenarios where features arrive one by one but ignore the original group structure of the features [36]. For example, in the fields of drug localization [37] and image analysis [38], where features mostly arrive in the feature space as groups.

Online group streaming feature selection can consider the structural information of the features, and thus achieve better classification results [39, 40]. Li et al. [40] used entropy and mutual information to perform online group streaming feature selection. Wang et al. [41] proposed a framework for online feature selection using prior knowledge of group structure information, including intra-group feature selection and inter-group feature selection. Yu et al. [42] extended the scalable and accurate online feature selection approach to handle the group feature selection problem in the sparse case. Liu et al. [43] proposed a new framework based on group structure analysis for online multilabel group streaming feature selection. Zhou et al. [44] designed a new online group streaming feature selection algorithm focused on feature interaction based on mutual information. Unfortunately, the information present in the real world contains many subjective concepts, such as pretty, young, and moral, these concepts have no clear boundaries and thus create ambiguity and uncertainty [45‐50]. Existing streaming feature selection methods cannot deal well with tasks in the context of fuzziness and uncertainty.

The classification task learns a classification model, i.e., a classifier, from the existing training samples [51‐53]. When test data arrive, predictions can be made based on the classifier to map the new data items to one of the classes in the given category [52]. Recently, feature selection based on rough sets and fuzzy sets from algebra and information views has been frequently reported to measure uncertainty in classification tasks [54‐56]. Wang et al. [57] proposed a fuzzy neighborhood rough sets model (FNRS) using parameterized fuzzy neighborhood information granules that can effectively prevent the effect of noise. Shreevastava et al. [58] proposed a new intuitionistic fuzzy neighborhood rough sets model for heterogeneous datasets, which combined intuitionistic fuzzy sets and neighborhood rough sets. An et al. [53] proposed a relative fuzzy rough set model and designed a classifier based on the maximum positive domain for the problem of large differences in the class density of the data distribution. The above studies discussed feature selection from an algebraic view, where the significance of features can only state the consequence of features contained in the feature subset [55, 59]. Sang et al. [60] proposed a fuzzy dominant neighborhood rough sets model for possible noisy data in biased-ordered information systems. Xu et al. [61] redefined fuzzy neighborhood relations and introduced them into conditional entropy, proposing a new fuzzy neighborhood conditional entropy. Zhang et al. [62] proposed active incremental feature selection using the information entropy of introduced instances based on fuzzy rough sets. Nevertheless, the feature significance of these information view-based references merely interprets the influence of uncertainty classification on features [54, 62]. Sun et al. [63] combined the fuzzy neighborhood rough sets with the neighborhood multigranulation rough sets and proposed a fuzzy neighborhood multigranulation rough sets model. Xu et al. [64] fused the self-information measure into the fuzzy neighborhood in the upper and lower approximations and proposed a fuzzy neighborhood joint entropy based on fuzzy neighborhood self-information. Xu et al. [65] defined multilabel fuzzy neighborhood conditional entropy and approximation accuracy to solve the classification problem under a multilabel decision system. It is confirmed that the combination of algebra and information views can make the measurement mechanism more comprehensive [63, 65].

Fuzzy rough sets theory and its applications are also widely used to solve some practical problems [66‐72]. Xu et al. [66] proposed a fuzzy rough uncertainty measure model for tumor diagnosis and microarray gene selection. Liu et al. [68] proposed a co-evolutionary model for crime inference based on fuzzy rough sets. These reported studies evaluate features by the consistency of conditional and decision features in information granularity, ignoring the separability of decision information granularity for different conditional features. Nonetheless, the separability of conditional features is closely related to their performance in classification tasks [73, 74]. Hu et al. [73] defined the aggregation degree of intraclass objects and the dispersion degree of between-class objects to measure the significance of features. The separability-based evaluation function has a profound impact on the improvement of accuracy and time efficiency. However, these fuzzy rough sets-based approaches are only applicable to traditional feature selection and cannot deal with feature selection in dynamic environments.

Motivated by this, to effectively deal with the streaming feature selection task in fuzzy and uncertainty contexts, this paper proposes some fuzzy neighborhood entropy-based uncertainty measures and investigates a novel online group streaming feature selection method, named FNE-OGSFS. The main innovation points are as follows:The remainder of this paper is organized as follows. “Preliminaries” reviews the related knowledge of FNRS and the coincidence degree. “Fuzzy neighborhood entropy-based uncertainty measures” presents the separability degree and some fuzzy neighborhood entropy-based uncertainty measures. “Online group streaming feature selection approach” develops a novel online group streaming feature selection approach. “Experimental results” provides the experimental analysis on thirteen datasets. “Conclusion and future work” concludes the paper with an outlook on the future.

Let \(DS = \left\langle {U,C,D} \right\rangle \) be a decision system, where \(U = \left\{ {{x_1},{x_2}, \ldots ,{x_n}} \right\} \) is a nonempty finite set called the theoretical domain, C is the set of conditional features of the sample, and D is the set of decision features of the sample. \(U/D = \left\{ {{D_1},{D_2}, \cdots ,{D_l}} \right\} \) means D divides U into l equivalence classes.

Let \(A \subseteq C\) be a subset of conditional features on U, and a fuzzy binary relation \({R_A}\) can be induced by A. Then, \({R_A}\) is called a fuzzy similarity relation when it satisfies both reflexivity and symmetry [57]: Let \(a \in A\) and \({R_a}\) be the fuzzy similarity relation obtained by a. Then, \({R_A}\) can be expressed as \({R_A} = \bigcap \nolimits _{\forall a \in A} {{R_a}} \).

The purpose of feature selection is to retain the features with high separability and strong approximation ability and to remove the trivial features [73]. If the coincidence degree of the original data from different categories is high and the coincidence degree of the selected data is low, then the importance of the retained features is high.

When \(\left| {\left[ {m_{{D_i}}^a,M_{{D_i}}^a} \right] \!\cup \!\left[ {m_{{D_j}}^a,M_{{D_j}}^a} \right] } \right| \!=\!0\) or \(\mid \left[ m_{D_{i}}^{a}, M_{D_{i}}^{a}\right] \) \(\cap \left[ m_{D_{j}}^{a}, M_{D_{j}}^{a}\right] =0\), \(\vartheta \) is a very small positive constant, and in other cases, \(\vartheta = 0\).

\(\mathrm{CD}\left( a \right) \) represents the coincidence degree of samples between different categories and evaluates the classification ability of feature a in terms of separability. In the process of feature selection, we need to select the feature that can decrease the coincidence degree.

Let \(\mathrm{OGDS} = \left( {U,G,D,h,t} \right) \) be an online group streaming decision system, \(U = \left\{ {{x_1},{x_2}, \ldots ,{x_n}} \right\} \) be the set of samples, \(G = \left\{ {{G_1},{G_2},..,{G_w}} \right\} \) is the set of stream features, \({G_i} = {\left\{ {{f_1},{f_2}, \ldots ,{f_{{m_t}}}} \right\} ^T}\) is a set of features in G containing \({m_t}\) features, and a new set of features \({G_t}\) is obtained with unknown feature space at each stamp t. D is the set of decision features, h is the feature-to-class mapping function, and t is the time stamp. The problem of online group streaming feature selection is to select an optimal feature subset S in the continuous inflow feature groups when the algorithm terminates.

The FNE-OGSFS can be divided into three parts: online intra-group selection and online interaction analysis, and online redundancy analysis.

For the FNE-OGSFS algorithm, the sample space is \(U = \left\{ {{x_1},{x_2}, \ldots ,{x_n}} \right\} \), the set of features arriving at time t is \({G_t} = {\left\{ {{f_1},{f_2}, \ldots ,{f_{{m_t}}}} \right\} ^T}\), the set of selected features is \({S_{t - 1}}\), and the set of selected features within the group is \(S_{t}^{\prime }\). Each feature in \({G_t}\) is traversed to calculate its significance in the intra-group feature selection phase, where the computation of the parameterized fuzzy neighborhood information granule has the most important impact on the complexity and the time complexity is approximated by \(O\left( {{m_t}n} \right) \). The time complexity of the inter-group feature selection phase increases with the size of the selected feature subset \({S_{t - 1}}\). Let the number of features in \({S_{t - 1}}\) be \(\left| {{S_{t - 1}}} \right| \) and the number of features selected within the group be \(\left| {S_{t}^{\prime }} \right| \); then, the worst-case time complexity is \(O\left( {\left| {{S_{t - 1}}} \right| *\left| {S_t^{\prime }} \right| *{n^2}} \right) \). In addition, the time complexity of the Lasso algorithm is \(O\left( n \right) \). Therefore, the worst-case time complexity of the FNE-OGSFS algorithm is \(O\left( {\left| {{S_{t - 1}}} \right| *\left| {S_t^{\prime }} \right| *{n^2}} \right) \).

The evaluation framework for feature selection is outlined in Fig. 1. The details of each stage of the experiment are depicted below.

First, the dataset is divided and preprocessed. To verify the feasibility and stability of the developed algorithm, the FNE-OGSFS method is used on thirteen public datasets in our experiments, including four UCI datasets,¹ seven DNA microarray datasets² and two NIPS 2003 datasets.³ All datasets in detail are listed in Table 1. For the missing values in a dataset, such as the LYMPHOMA dataset, the conditional mean completer is used [16]. The 10-fold cross-validation approach is adopted for evaluating the classification performance under different classifiers.

Second, the feature selection methods are selected. In this subsection, FNE-OGSFS is compared with eight state-of-the-art feature selection methods, including two online group streaming feature selection methods (OGSFS-FI [44], Group-SAOLA [42]), three online individual streaming feature selection methods (Alpha-investing [25], SFS-FI [31], OFS-A3M [26]) and three FNRS-based method (FNRS [57], FNCE [67], FNPME-FS [63]). Note that the FNRS-based methods cannot deal with the online feature selection task, and some parameters contained in the above comparison methods need to be specified in advance; here, we refer to the parameter value or value range corresponding to the original thesis.

Finally, the classifier and evaluation metrics are determined. Four classical classifiers, including support vector machine (SVM), naive Bayes (NB), K-nearest neighbor (KNN, \(k=3\)) and classification and regression tree (CART), are used to evaluate the classification performance of the selected features. The parameters of the classifier are set to the default of MATLAB except for changing the data distribution in the NB classifier to the kernel distribution. We take the predictive accuracy, number of selected features and running time as evaluation metrics of the comparative experiment. Furthermore, the Friedman test and the corresponding post-hoc tests are performed to systematically investigate the statistical performance of the FNE-OGSFS method and its rivals in terms of predictive accuracy.

It should be noted that the comparison experiments are based on the same design approach. All experiments are performed in MATLAB R2016a and run in a hardware environment with an Intel Core i5-3470 CPU at 3.20 GHz and 4.0 GB RAM under Windows 10.

There are two parameters \(\mathrm{{\delta }}\) and G in the FNE-OGSFS algorithm. The parameter \(\mathrm{{\delta }}\) is used to adjust the size of the fuzzy neighborhood, and the parameter G is applied to control the size of the group. We set the value of \(\mathrm{{\delta }}\) from 0.1 to 1 with an interval of 0.05 [60]. Since the dataset does not have a priori group structure information, the experiment obtains the information on the group structure through the artificially specified group size to improve the time efficiency. The values of G are set to 5, 10, 20, 30, and 60 for low-dimensional datasets and 50, 100, 200, 400, and 800 for high-dimensional datasets [44]. In this subsection, we focus on the effect of different parameters on the predictive accuracy, number of selected features and running time.

In terms of predictive accuracy, the variation in predictive accuracy with parameters for thirteen datasets on SVM is shown in Figs. 2 and 3, where four datasets in Fig. 2 are low-dimensional datasets and nine datasets in Fig. 3 are high-dimensional datasets. The experimental results obtained using KNN, NB, and CART are roughly consistent with SVM. Figure 2 indicates that the different parameters have a certain impact on the classification performance of low-dimensional datasets. In detail, the parameter \(\mathrm{{\delta }}\) has a deeper influence on some datasets, such as the Sonar and Ionosphere datasets, where the predictive accuracies are generally higher when \(\mathrm{{\delta }}\) is less than 0.5. The classification performance of the Wdbc and Wpbc datasets obviously depends more on the parameter G, which can achieve higher predictive accuracies when G is larger, and the influence of \(\mathrm{{\delta }}\) is not significant. As seen in Fig. 3, the predictive accuracy on most of the high-dimensional datasets has a significant trend change with parameter changes. The DLBCL, LYMPHOMA and Lung Cancer datasets can achieve better predictive accuracies when both G and \(\mathrm{{\delta }}\) are larger. The predictive accuracies of the LEUKEMIA, Ovarian Cancer, ARCENE and MADELON datasets are more influenced by parameter G; when parameter \(\mathrm{{\delta }}\) is constant, the predictive accuracy improves significantly with increasing G. The applicability of parameter \(\mathrm{{\delta }}\) varies greatly for different datasets, e.g., dataset COLON is more suitable for smaller \(\mathrm{{\delta }}\), and dataset SRBCT is more suitable for larger \(\mathrm{{\delta }}\). Obviously, all datasets can achieve higher predictive accuracy in most regions.

In terms of running time and number of selected features, due to space limitation, three different types of datasets (Wpbc, LEUKEMIA, and ARCENE) are selected as representatives in this subsection to test the experimental effects under different parameters, and the results are shown in Figs. 4 and 5, respectively. Figure 4 shows that the running time increases significantly only when \(\mathrm{{\delta }}\) is small in the low-dimensional dataset. The running time and parameter G are closely related in the high-dimensional dataset. This is because as the group size increases, more complex matrix operations occur in the calculation of the fuzzy neighborhood information granule, which in turn consumes more time. Figure 5 indicates that these datasets show better results in terms of compactness (i.e., fewer features are selected in feature selection). Different datasets have different preferences for the parameter \({{\delta }}\). Fewer features are selected when G is small because fewer relevant features are considered calculating the fuzzy neighborhood information granule; hence, more features are discarded in the intra-group feature selection.

Overall, the experimental result demonstrates the effectiveness of FNE-OGSFS in selecting the optimal feature subsets for different types of datasets. It should be noted that the parameters corresponding to the best predictive accuracy are different for the thirteen datasets. Therefore, the parameters need to be determined in advance before feature selection for the datasets to achieve the maximum balance among higher accuracy, smaller running time, and greater compactness.

In this subsection, the performance of FNE-OGSFS and its rivals in terms of the predictive accuracy, number of selected features and running time are analyzed.

Tables 2, 3, 4 and 5 show the predictive accuracies of the KNN, SVM, NB, and CART classifiers. The last two rows list the win/tie/lose (abbreviated as W/T/L) counts and the average predictive accuracies of the algorithms on all datasets, with bold font indicating the highest predictive accuracy. Tables 6 and 7 show the number of selected features and running times of the nine algorithms, respectively. Specifically, we discuss the following.

To more intuitively confirm the algorithm effectiveness, we plotted spider web graphs to depict the average predictive accuracy on each classifier, as shown in Fig. 6, where the red line represents the predictive accuracy of our proposed algorithm on each dataset. Tables 2, 3, 4 and 5 and Fig. 6 show that FNE-OGSFS performs significantly better than the other comparison algorithms in terms of overall classification performance. The average predictive accuracy reaches the maximum on all classifiers, and the win counts achieve the highest among all comparison algorithms. By intra-group feature selection, our proposed algorithm select features with high significance. During the online interaction analysis, FNE-OGSFS leave the features with interaction. The experimental results show that this strategy is effective and the selected features can achieve high prediction accuracy. Compared with online streaming feature selection methods, the FNE-OGSFS method performs significantly better on genetic datasets. Because the algorithm can handle the fuzziness and uncertainty of genetic datasets well by using the uncertainty measures based on fuzzy neighborhood symmetric uncertainty. Compared with the FNRS-based feature selection methods, our algorithm has a significant advantage because our algorithm incorporates the coincidence degree that allows the selection of highly separability features, which is beneficial for classification.

Compared with the number of selected features, we find that the proposed algorithm can achieve feature reduction. In the last part of FNE-OGSFS, namely, online redundancy analysis, redundant features can be effectively eliminated, which is helpful in selecting fewer features. Although Group-SAOLA and SFS-FI select fewer features, they are far less accurate than our proposed algorithm and other comparison algorithms. The features removed in the redundancy analysis phase of our algorithm also do not degrade the classification performance.

By comparing the time used by the algorithms, FNE-OGSFS can achieve high efficiency when dealing with low-dimensional datasets. However, its performance is poor when dealing with high-dimensional datasets such as the Lung Cancer and Ovarian Cancer datasets because the process of computing fuzzy neighborhood granules consumes considerable time. This situation is more evident in all three comparison algorithms based on FNRS. Our algorithm requires re-evaluation of the selected features and thus runs slower. However, since we evaluate the interactivity and redundancy of the selected features, we select more favorable and fewer features for classification, which performs better in terms of compactness and accuracy.

In conclusion, FNE-OGSFS provides the best overall performance on four classical classifiers. Although FNE-OGSFS has a slightly longer running time, it achieves the highest average prediction accuracy and effectively removes redundant features. It has been verified that FNE-OGSFS is superior to the other compared algorithms on different types of datasets.

To further explore the generalization ability of the FNE-OGSFS algorithm systematically, the Friedman test and Nemenyi post-hoc test are performed in this subsection to assess the statistical significance of the algorithm [76]. The average predictive accuracies of each algorithm on the thirteen datasets shown in Tables 4, 5, 6 and 7 are ranked from lowest to highest before using the Friedman test, and the rankings are divided equally when the performance is the same. The Friedman statistic is described aswhere n and h are the number of datasets and algorithms, respectively, and \({R_j}\left( {j = 1,2, \ldots ,h} \right) \) denotes the average ranking of the j th algorithm over all datasets. The variable \(\chi _F^2\) obeys the \({\chi ^2}\) distribution with \(h - 1\) degrees of freedom, and the variable \({F_F}\) obeys the F distribution with \(h - 1\) and \(\left( {h - 1} \right) \left( {n - 1} \right) \) degrees of freedom. To further obtain the difference between the algorithms, the critical difference (CD) of the mean rankings in the Nemenyi test is calculated bywhere \(\alpha \) represents the significance level of the Nemenyi test and \({q_\alpha }\) represents the critical value corresponding to the number of comparison algorithms at a particular significance level.

The average rankings of predictive accuracy of a particular algorithm on all datasets were acquired according to the statistical tests provided in [76]. For the predictive accuracy on thirteen datasets in Tables 2, 3, 4 and 5, the Friedman tests were achieved by the comparison of FNE-OGSFS with the other algorithms. The null hypothesis of the Friedman test is established when all algorithms are equal in metrics of predictive accuracy. Table 8 describes the average ranking of the nine algorithms and the values of \(\chi _F^2\) and \({F_F}\) on the four classifiers.

The \({F_F}\) distribution has 8 and 96 degrees of freedom when \(n = 13\) and \(h = 9\), respectively. By checking the table, we can obtain the value of \(\chi _F^2\left( 8 \right) \) in the \(\chi _F^2\) distribution as 13.36 and \(F\left( {8,96} \right) \) in the F distribution as 1.74 when the significance level is \(\mathrm{{\alpha }} = 0.1\). From the results in Table 8, we can see that the values of \(\chi _F^2\) and \({F_F}\) on four classifiers are greater than their values on \(\chi _F^2\left( 8 \right) \) and \(F\left( {8,96} \right) \). That is, all null hypotheses are rejected, which demonstrates that the performances of these algorithms are significantly different. Further post-hoc tests are performed next to obtain the difference between the algorithms. The critical value \({q_{0.1}}\) is 2.855 when \(h = 9\) and then the critical range \(C{D_{0.1}}\) is 3.0663. To more intuitively compare the differences of the algorithms, a graph is introduced to connect the methods that do not differ significantly from each other, in which the critical values among all algorithms can be clearly illustrated. Fig. 7 shows the comparison of FNE-OGSFS with the other algorithms on four classifiers, where the critical value and its range are shown above the axis, the coordinate axis plots the average ranking values for each algorithm, and the average ranking of the left-hand side is the lowest. The horizontal lines are used to connect the algorithms with no significant difference, which indicates that any two algorithms with a difference in average ranking less than the value of CD are connected by the red line.

As shown in Fig. 7, the significant difference among the nine algorithms are obvious. FNE-OGSFS performs significantly better than the other algorithms on four classifiers. In some cases, the significance of the algorithms on different classifiers is slightly different, e.g., Group-SAOLA has the lowest average ranking on NB and CART classifiers, but not on the other classifiers. FNE-OGSFS has the same group as FNPME-FS and OGSFS-FI, which means the differences among the three algorithms are not obvious. However, the difference in their average rankings is very close to the critical value on most classifiers, so it can still be concluded that FNE-OGSFS excels against the two compared methods. In summary, FNE-OGSFS outperforms the other eight compared algorithms overall.