A grouping feature selection method based on feature interaction

Abstract

Feature interaction is crucial in the process of feature selection. In this paper, a grouping feature selection method based on feature interaction (GFS-NPIS) is proposed. Firstly, a new evaluation function measuring feature interaction is proposed. Secondly, a grouping strategy based on approximate Markov blanket is used to remove strong redundant features. Lastly, a new feature selection method called as GFS-NPIS is given. In order to verify the effectiveness of our method, we compare GFS-NPIS with other eight representative ones on three classifiers (SVM, KNN and CART). The experimental results on fifteen public data sets show that GFS-NPIS outperforms others in terms of classification accuracy and Macro-F1.

Keywords

Feature selection feature interaction strong redundant feature grouping strategy

1. Introduction

Feature selection is an important step in data mining and pattern recognition [1]. There are a large number of irrelevant and redundant features existing in data for practical applicating. These irrelevant and redundant features not only increase the computational cost but also have a negative impact on learning models [2]. As a result, it is necessary to identify and remove them. And the feature selection method based on them are more urgent.

Nowadays, in the field of feature selection, most scholars focus on the topic of feature evaluation function and search strategy [3]. For feature evaluation function, there are two common relationships among features, which are relevance and redundancy. Relevance is usually determined by the relationship between a feature and class label, whereas redundancy is determined by the relationship between two features [4]. Apart from relevance and redundancy, feature interaction is also used now. Among massive of feature selection algorithms, most of them only consider feature relevance and feature redundancy, but seldomly consider feature interaction [5]. As a matter of fact, different features may interact and collaborate together. Hence, feature interaction is very important and inescapable in the process of feature selection. If feature interaction is ignored, some very important features will be misjudged as redundant features removal. Therefore, this paper aims to propose an efficient interactive measurement criterion, which can be used in the process of removing redundant features to keep some redundant but interactive features and prevent important features from being removed, thus improving the final classification accuracy.

In the topic of search strategy, most feature methods use greedy ones. Obviously, they are computationally expensive [6]. For this problem. Yu and Liu proposed FCBF [7] method that selects predominant features and removes those highly correlated features through an approximate Markov blanket search strategy. Compared with greedy strategy, approximate Markov blanket is more efficient in execution time.

In this paper, we consider feature interaction into feature selection and use approximate Markov blanket as our search strategy. To sum up, our contributions are as follows. (1) A new concept, Normalized Pure Interaction Score (NPIS), is proposed to measure feature interaction; (2) Feature interaction is considered in removing strong redundant features by approximate Markov blanket search strategy; (3) A new feature selection method, A grouping feature selection method based on NPIS (GFS-NPIS), is proposed.

The rest of the paper is arranged as follows. Section 2 reviews the related works. Section 3 introduces the background theory involved. Section 4 introduces the proposed method in details. Section 5 is the experiments and the analysis of the experimental results. Section 6 is the summary and our future work.

2. Related works

Suppose we have a data set $D$ containing $n$ features. $F=\left\{{F_{1},F_{2}\ldots,F_{n}}\right\}$ is a full set of features, $F_{i}$ represents a candidate feature, $C$ represents the class label. $F_{j}$ represents a selected feature in the selected feature subset $S$ , and $m$ represents the dimension number of $S$ . The key point of feature selection is to select a feature subset $S$ that have a better classification accuracy.

Mutual Information Maximum (MIM) [8] algorithm is the earliest feature selection method using mutual information (MI). MIM uses $I\left({F_{i};C}\right)$ as evaluation function to select relevant features. Although MIM considers the relevancy between the feature and the class label, it does not consider the redundancy and interaction among features. There are a lot of redundant features in the selected feature subset of MIM, which makes the final classification accuracy low.

$\displaystyle\textit{MIM}=I\left({F_{i};C}\right)$ (1)

In terms of redundancy problems, many scholars have studied how to identify the redundancy features more accurately. In 2005, Peng and Ding proposed minimum Redundancy Maximum Relevance (mRMR) [9]. In mRMR, they not only used $I\left({X_{i};Y}\right)$ to evaluate the relevance but also used $\frac{1}{m}mathop\sum\nolimits_{F_{j}\in S}I\left({F_{i};F_{j}}\right)$ to evaluate the redundancy between different features.

$\displaystyle\textit{mRMR}=I\left({F_{i};C}\right)-\frac{1}{m}\mathop{\sum}% \nolimits_{F_{j}\in S}I\left({F_{i};F_{j}}\right)$ (2)

Based on mRMR, Conditional Informative Feature Extraction (CIFE) [10] and Feature Selection Based on Joint Mutual Information (JMI) [11] are proposed. In these two ones, the redundancy is further refined to the intra-class feature redundancy. And JMI uses $\frac{1}{m}$ to average the redundant parts of CIFE. The evaluation functions of CIFE and JMI are expressed as follows.

$\displaystyle\textit{CIFE}=I\left({F_{i};C}\right)-\mathop{\sum}\nolimits_{F_{% j}\in S}\left\{{I\left({F_{i};F_{j}}\right)-I\left({F_{j};F_{i}|C}\right)}\right\}$ (3) $\displaystyle\textit{JMI}=I\left({F_{i};C}\right)-\frac{1}{m}\mathop{\sum}% \nolimits_{F_{j}\in S}\left\{{I\left({F_{i};F_{j}}\right)-I\left({F_{j};F_{i}|% C}\right)}\right\}$ (4)

The above-mentioned algorithms utilize the different evaluation index to identify relevant features and redundant features, but they have two limitations. (1) They are computationally expensive with greedy search strategies; (2) They ignore the feature interaction among different features.

In order to solve the first problem, many researchers have done a lot of work. For example, Yu and Liu proposed Fast Relevance-Based Filter (FCBF) [7] method that determines the selected feature set through an approximate Markov blanket search strategy. FCBF uses $\textit{SU}\left({F_{i},C}\right)>0$ to select relevant features and uses $\textit{SU}\left({F_{i},C}\right)-\textit{SU}\left({F_{i},F_{j}}\right)\geqslant 0$ to identify redundancy features. But FCBF does not consider feature interaction, which leads to some of interactive features being misjudged as redundant features. The evaluation of FCBF can be shown as the two following formulas.

$\displaystyle\textit{FCBF}_{\textit{relevance}}=\textit{SU}\left({F_{i},C}\right)$ (5)

$\displaystyle\textit{FCBF}_{\textit{redundancy}}=\textit{SU}\left({F_{i},C}% \right)-\textit{SU}\left({F_{i},F_{j}}\right)$ (6)

In terms of feature interaction, more and more scholars have studied feature interaction to improve the classification accuracy. In 2020, a new feature selection algorithm based on relevance, redundancy and complementarity (FSRRC) [12] was proposed by Chao Li et al. FSRRC not only has the same search strategy as FCBF in relevancy and redundancy but also considers feature interaction in feature selection. FSRRC uses Eq. (9). to identify the interactive features. $F_{j}$ will be judged interactive of $F_{i}$ iff $\textit{Score}\left({F_{i},F_{j};C}\right)>0$ . Equation (9) uses CMI to subtract the information difference to evaluate feature interaction, which has a problem of multi-value tendency.

$\displaystyle\textit{FSRRC}_{\textit{relevance}}=\textit{SU}\left({F_{i},C}\right)$ (7) $\displaystyle\textit{FSRRC}_{\textit{redundancy}}=\textit{SU}\left({F_{i},C}% \right)-\textit{SU}\left({F_{i},F_{j}}\right)$ (8) $\displaystyle\textit{FSRRC}_{\textit{interaction}}=\textit{Score}\left(F_{i},F% _{j};C\right)=I\left(F_{i},F_{j}{|}C\right)-I\left(F_{i},C\right)$ (9)

Besides FSRRC, a filter-based feature selection by feature grouping (FFSG) [13] was proposed in 2020. FFSG uses strong approximate Markov blanket to remove redundant features. In FFSG, the redundant features are identified and removed by Eq. (10) firstly. Then, the interactive features are identified and retained by Eq. (11). Finally, the irrelevant features are removed by an evaluation function which are shown as Eq. (12). From Eq. (12), it can be seen that FFSG only considers the change of information between two features, but ignores the influence of the class label on feature interaction.

$\displaystyle\textit{FSSG}_{\textit{redundancy}}=\textit{SU}\left({F_{i},C}% \right)-\textit{SU}\left({F_{i},F_{j}}\right)$ (10) $\displaystyle\textit{FSSG}_{\textit{interaction}}=\textit{SU}\left({F_{i},F_{j% }}\right)-\frac{\mathop{\sum}\nolimits_{k=1}^{m}\mathop{\sum}\nolimits_{l\neq k% }^{m}\textit{SU}\left({F_{l},F_{k}}\right)}{m\left({m-1}\right)}$ (11) $\displaystyle\textit{FSSG}_{\textit{relevance}}=J\left(S\right)=\frac{m% \overline{\textit{SU}}\left({S,C}\right)}{\sqrt{m+m\left({m-1}\right)\overline% {\textit{SU}}\left(S,S\right)}}$ (12)

Yamada et al. [14] proposed HSIC Lasso algorithm a kernel-based mRMR, which is a non-linear feature selector. Instead of mutual information, HSIC Lasso employs the HSIC [15] to measure dependency between two variables. In addition, it uses a penalty term to select a small number of features. This results in a convex optimization problem, for which one can therefore find a globally optimal solution. HSIC Lasso considers a feature-wise kernelized Lasso for capturing nonlinear input-output dependency [16]. HSIC of two variables $X$ and $Y$ is shown as follows.

$\displaystyle\textit{HSIC}\left({X,Y}\right)=\mathbb{E}_{x,x^{\prime},y,y^{% \prime}}K[(x,x^{\prime})L(y,y^{\prime})]+\mathbb{E}_{x,x^{\prime}},[K(x,x^{% \prime})]\mathbb{E}_{y,y^{\prime}}[L(y,y^{\prime})]-2\mathbb{E}_{x,y}[K(x,x^{% \prime})L(y,y^{\prime})]$ (13)

Where, $K:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}$ and $L:y\times y\to\mathbb{R}$ are positive definite kernels, and $\mathbb{E}_{x,x^{\prime},y,y^{\prime}}$ denotes the expectation over independent pairs $(x,y)$ and $(x^{\prime},y^{\prime})$ drawn from $p(x,y)$ . $\textit{HSIC}(X,Y)$ is equal to 0 if $X$ and $Y$ are independent, and is non-negative otherwise.

3. Background theory

3.1 Information theory

Entropy, mutual information and conditional mutual information are the most popular metrics in feature selection. Entropy is used to evaluate the uncertainty of a random variable. The entropy of a random variable $X$ is defined as Eq. (14) [17].

$\displaystyle H\left(X\right)=-\mathop{\sum}\nolimits_{x\in X}p\left(x\right)% \log p\left(x\right)$ (14)

Where $p\left(x\right)$ is the probability density function and $0\leqslant H\left(X\right)\leqslant 1$ .

For any two random variables, the concept of entropy can be extended to joint entropy and conditional entropy. Joint entropy of two random variables $X$ and $Y$ is defined as Eq. (15). Conditional entropy of two random variables $X$ and $Y$ is defined as Eq. (16).

$\displaystyle H\left({X,Y}\right)=-\mathop{\sum}\nolimits_{x\in X}\mathop{\sum% }\nolimits_{y\in Y}p\left({xy}\right)\log p\left({xy}\right)$ (15) $\displaystyle H\left({X{|}Y}\right)=-\mathop{\sum}\nolimits_{y\in Y}\mathop{% \sum}\nolimits_{x\in X}p\left({xy}\right)\log p\left({x{|}y}\right)$ (16)

where $p\left({xy}\right)$ is the joint prior probability distribution function of $X$ and $Y$ , and $p(x|y)$ is the conditional probability of $X$ given $Y$ .

As is known to all, mutual information (MI) is widely applied in feature selection. MI can be used to measure the degree of the relevance between two random variables and how much information one variable contains about another one. MI of two variables $X$ and $Y$ can be described as follows [18].

$\displaystyle I\left({X;Y}\right)=\mathop{\sum}\nolimits_{x\in X}\mathop{\sum}% \nolimits_{y\in Y}p\left({x,y}\right)\log\frac{p\left({x,y}\right)}{p\left(x% \right)p\left(y\right)}$ (17)

$I\left({X;Y}\right)$ can be regarded as the reduction of uncertainty of $Y$ under the condition of given $X$ . By deduction, the relationship between MI and entropy can be shown as follows.

$\displaystyle I\left({X;Y}\right)\left\{{{\begin{array}[]{l}{H\left(X\right)-H% \left({X{|}Y}\right)}\hfill\\ {H\left(Y\right)-H\left({Y{|}X}\right)}\hfill\\ {H\left(X\right)+H\left(Y\right)-H\left({X,Y}\right)}\hfill\\ \end{array}}}\right.$ (18)

Here, $H\left(X\right)$ and $H\left(Y\right)$ are the entropy of $X$ and $Y$ respectively, $H\left({X,Y}\right)$ is the joint entropy of $X$ and $Y$ , and $H(X|Y)$ describes the conditional entropy of $X$ when the variable $Y$ is known, $H(Y|X)$ describes the conditional entropy of $Y$ when the variable $X$ is known.

In fact, MI tends to favor features with more values. Therefore, Symmetrical Uncertainty (SU) is introduced in many studies. SU is the normalized MI, which is defined as follows [19].

$\displaystyle\textit{SU}\left({X,Y}\right)=\frac{2I\left({X,Y}\right)}{H\left(% X\right)+H\left(Y\right)}$ (19)

Conditional Mutual Information (CMI) is an extension of MI for measuring the conditional dependence between two variables given a third variable [20]. CMI of two random variables $X$ and $Y$ given $Z$ can be defined as follows.

$\displaystyle I\left({X;Y{|}Z}\right)=\left\{\begin{array}[]{l}{H\left({X{|}Z}% \right)+H\left({X{|}Y,Z}\right)}\hfill\\ {H\left({X{|}Z}\right)+H\left({X{|}Y,Z}\right)}\hfill\\ {H\left({X{|}Z}\right)+H\left({Y{|}Z}\right)-H\left({X,Y{|}Z}\right)}\hfill\\ \end{array}\right.$ (20)

3.2 Grouping strategy

In this paper, we use a grouping strategy to remove strong redundant features. There are three related concepts about grouping strategy, which are approximate Markov blanket, predominant feature and predominant group.

To understand approximate Markov blanket better, it is required to learn about the concept of Markov blanket. Markov blanket is proposed by Koller and Sahami [21]. Markov blanket is defined as follows.

Definition 1 (Markov blanket) [21]. For a feature set $F\left\{{F_{1},F_{2},\ldots,F_{n}}\right\}$ , a class label $C$ , a feature $F_{i}\in F(i=1,2,\ldots,n)$ and a set $M_{i}\left({i=1,2,\ldots,n;M_{i}\subset F;F_{i}\notin M_{i}}\right)$ , $M_{i}$ forms a Markov blanket for $F_{i}$ if the following Eq. (21) is satisfied.

$\displaystyle F_{i}\bot\left\{{F-M_{i}-\left\{{F_{i}}\right\},C}\right\}|M_{i}$ (21)

Here, $\bot$ represents an independent relationship, $|M_{i}$ means that $M_{i}$ is the condition. From the definition of Markov blanket, given a set $M_{i}$ , $M_{i}$ forms a Markov blanket for $F_{i}$ if $F_{i}$ is independent of the feature set $\left\{{F-M_{i}-\left\{{F_{i}}\right\}}\right\}$ and class label $C$ .

MB is calculated by the feature subset, and the involved calculation amount is relatively large. Therefore, a method called as approximate Markov blanket is proposed by Yu and Liu [7]. Approximate Markov blanket is defined as follows.

Definition 2 (Approximate Markov blanket) [7]. For two features of $F_{i}$ and $F_{j}\left({i\neq j}\right)$ , $F_{j}$ forms an approximate Markov blanket for $F_{i}$ iff $\textit{SU}\left({F_{i},C}\right)>\textit{SU}\left({F_{j},C}\right)$ and $\textit{SU}\left({F_{i},F_{j}}\right)\geqslant\textit{SU}\left({F_{j},C}\right)$ .

Based on Approximate Markov blanket, predominant feature is defined as follows.

Definition 3 (Predominant feature) [7]. A relevant feature is predominant iff it does not have any approximate Markov blanket in the current set.

Detecting all correlated subsets is a combinatorial problem since it requires to take into account $2^{d}$ subsets. Because of the intractability of this problem, the concept of predominant group is proposed as follows by Miguel et al [22].

Definition 4 (Predominant group) [22]. A feature subset $G$ is a predominant group if $G_{i}\neq\left\{\emptyset\right\}$ and $\exists!F_{i}\in G_{i}$ : $F_{i}$ is a predominant feature.

By grouping relevant features, the feature space can be split into some groups so that each group is composed of redundant features. Predominant features are relevant and not redundant, so that each group $G_{i}\left({i=1,2,\ldots,k}\right)$ can be generated by considering a predominant feature $F_{i}\left({i=1,2,\ldots,k}\right)$ along with all its corresponding redundant features $F_{j}\left({j=1,2,\ldots,k;j\neq i}\right)$ . Assume that the number of predominant features is $k$ , the feature space can be divided into $\left\{{G_{1},G_{2},\ldots,G_{k}}\right\}$ . Meanwhile, each group $G_{i}\left({i=1,2\ldots,k}\right)$ is composed of a predominant feature and its corresponding redundant features.

4. Proposed method

4.1 Problem

In Section 2 (Related works), we introduced seven feature selection algorithms. MIM uses the mutual information to measure feature relevance. The larger the value of mutual information, the higher the correlation between features and categories. However, MIM doesn’t consider feature redundancy and feature interactivity, which leads to a large number of redundant features in the selected feature set, and the final classification accuracy is very low.

Compared with MIM, the four algorithms (mRMR, CIFE, JMI, FCBF) not only consider feature correlation but also consider feature redundancy. They used different evaluation functions to evaluate the importance of features, but ignored feature interaction. Feature interaction means that two features working together could provide more information than the sum of their individual information. Even if two features are redundant, their combination may be more informative, and their cooperation may provide additional information in some cases. Therefore, neglecting the interaction between features may lose some meaningful information. The loss of important features will eventually reduce the final classification accuracy.

The above algorithms do not consider feature interaction, and there are two algorithms (FSRRC, FFSG) that consider feature interaction. In FSRRC, Eq. (9) is used to evaluate feature interaction. Equation (9) uses CMI to subtract the information difference to evaluate feature interaction, which has a problem of multi-value tendency. FFSG, they used Eq. (12) to identify the interactive features. From Eq. (19), it can be seen that FFSG only considers the change of information between two features, but ignores the influence of the class label on feature interaction.

Generally speaking, the current feature selection methods either don’t consider feature interaction or the evaluation of feature interaction are too single and need to be further improved. Therefore, this paper aims to study feature interaction in the process of feature selection. Taking feature interaction into the process of removing redundant features can prevent some important features from being misjudged as redundant features.

4.2 Method

It is well known that feature selection aims to select the features that are highly relevant with the category. Thus, the influence of class label on feature interaction can’t be ignored. And an effective feature interaction criterion is very important for feature interaction. After analyzing Eq. (9), we know that CMI subtracts the information difference can measure feature interaction. However, they ignored the difference of relevancy between two features in Eq. (9). In our view, if the difference value of relevancy between two features is smaller than the value of CMI, we think that $F_{j}$ is interactive to $F_{i}$ . Based on these, Normalized Pure Interaction Score (NPIS) is proposed to evaluate the feature interaction. NPIS is defined as Definition 5.

Without considering the information difference between two features of $F_{i}$ and $F_{j}$ , NPIS uses CMI to subtract the information difference to evaluate feature interaction. Then, we use $H\left({F_{i},F_{j},C}\right)$ to normalize NPIS in order to solve the problem that MI tends to select features with more values.

Definition 5 (Normalized Pure Interaction Score). Given the category $C$ , NPIS is defined as shown in Eq. (22).

$\displaystyle\textit{NPIS}\left({F_{i},F_{j};C}\right)=\frac{I\left({F_{i},F_{% j}{|}C}\right)-\left[{I\left({F_{i},C}\right)-I\left({F_{j},C}\right)}\right]}% {H\left({F_{i},F_{j},C}\right)}$ (22)

Here, $(F_{i},F_{j}|C)$ is the CMI of two features $F_{i}$ , $F_{j}$ and the category $C$ . $H\left({F_{i},F_{j},C}\right)$ is the joint entropy of two features $F_{i}$ , $F_{j}$ and category $C$ . $I\left({F_{i},C}\right)$ represents the mutual information between $F_{i}$ and $C$ , $I\left({F_{j},C}\right)$ represents the mutual information between $F_{j}$ and $C$

In the proposed method, NPIS is used to measure feature interaction and feature interaction is considered in the process of removing redundancy features. Therefore, we also put forward a concept of strong redundant feature. Strong redundant feature can be defined as follows.

Definition 6 (Strong redundant features). Given the category $C$ , $F_{j}$ can be regarded as a strong redundant feature of $F_{i}$ if $F_{i}$ and $F_{j}$ meet the following three conditionsï¼š

$\displaystyle\textit{SU}\left({F_{i},C}\right)\geqslant\textit{SU}\left({F_{j}% ,C}\right)$ (23) $\displaystyle\textit{SU}\left({F_{i},F_{j}}\right)\geqslant\textit{SU}\left({F% _{j},C}\right)$ (24) $\displaystyle\textit{NPIS}\left({F_{i},F_{j},C}\right)<0$ (25)

Figure 1.

Flow chart of GFS-NPIS.

When a candidate feature $F_{j}$ is regard as a strong redundant feature of a selected feature $F_{i}$ , it can be considered that $F_{j}$ forms an AMB about $F_{i}$ . Afterwards, a grouping strategy is used to remove strong redundant features in our method. In the process of removing the strong redundant features, the first feature in the sorted feature subset is a predominant feature since it does not have an AMB. Then, we check whether the first predominant feature forms an AMB for any of the features in the list. If so, the strong redundant feature will be added to its predominant group. Once all features have been checked, the algorithm selects as next predominant feature, the next relevant one with the highest SU that do not belong to any predominant group. Moreover, it is checked if the remaining features in the list are redundant with respect to the predominant feature. This process is repeated until no predominant feature is found.

Compared with FSRRC and FFSG, NPIS measures feature interaction more comprehensively to retain important interactive features and improve the final classification accuracy.

4.3 GFS-NPIS algorithm

In this section, we propose a new feature selection method called as GFS-NPIS. Figure 1 shows the flow chart of the proposed method and the detail pseudo-code of the proposed method is shown as in Table 1 (Algorithm1). GFS-NPIS algorithm mainly consists of three steps. Step1 pre-filters and sorts the features to determine the search sequence (Algorithm1, lines 1–7). Step2 uses NPIS to identify interactive features and uses a grouping tactics to remove the strong redundant features by approximate Markov blanket (Algorithm1, lines 8–21). Step3 is to remove irrelevant features by an evaluation function (Algorithm1, lines 22–30).

Table 1
Pseudo-code of GFS-NPIS

Algorithm1: GFS-NPIS

Input: A feature set

F=\left\{{f_{1},f_{1},\ldots,f_{n}}\right\}

; the class label

C

Output: The selected feature set

E

1. Initialization:

S\leftarrow\emptyset;S^{\prime}\leftarrow\emptyset;G\leftarrow\emptyset;E% \leftarrow\emptyset;E^{\prime}\leftarrow\emptyset

;

t=1

;

G_{t}\leftarrow\emptyset

2. For each

f_{i}\in F

do:

3. If

\textit{SU}\left({fi,C}\right)>0

S=S\mathop{\cup}\nolimits^{\{}fi

}

5. End if

6. End For

S\leftarrow\textit{sort}\left(S\right):\textit{SU}\left({f_{i},C}\right)% \geqslant\textit{SU}\left({f_{j},C}\right),\forall i<j

8. While

\left|G\right|\neq\left|S\right|

do:

9. For each

f_{i}\in S:\left({f_{i}\notin G}\right)

10.

G_{t}\leftarrow f_{i}

11. For each

f_{j}\in S:(f_{j}\notin G;i<j)

12. If

\textit{SU}\left({f_{i},f_{j}}\right)\geqslant\textit{SU}\left({f_{j},C}\right)

and

\textit{NPIS}\left({f_{i},f_{j},C}\right)<0

13.

G_{t}\leftarrow f_{j}

14. End if

15. End for

16.

G\leftarrow G_{t}\mathop{\cup}\nolimits^{G}

17. End for

19.

t=t+1

20. End

21.

S^{\prime}\leftarrow

the first feature of each group

G_{t}

22.

E\leftarrow

the first feature of

S^{\prime}

;

E^{\prime}\leftarrow

the first feature of

S^{\prime}

23. While

J\left({E^{\prime}}\right)\geqslant J\left(E\right)

and

\left|E\right|\neq\left|{S^{\prime}}\right|

do:

24.

j\leftarrow\textit{argmax}J\left({Ef_{j}}\right)\left({f_{j}\notin E}\right)

25.

E^{\prime}\leftarrow E\cup f_{j}

26. If

J\left({E^{\prime}}\right)\geqslant J\left(E\right)

27.

E\leftarrow E^{\prime}

28. End if

29. End

30. Output the final feature subset:

E

In Algorithm1, $S$ is a feature set in descending order of SU, and $S\subseteq F$ . $f_{i}$ and $f_{j}$ represent two features belonging to $F$ and $i\neq j$ , $t$ is the iteration counter, $G$ is the grouping result of the feature set $F$ , Gt is the $t-$ th group, and $S^{\prime}$ is the set of the first element of each group. $\left|G\right|$ and $\left|S\right|$ represent the number of elements of $G$ and $S$ . $E$ is the selected feature subset by Step1 and Step1, $E^{\prime}$ is a superset of $E$ for determining whether $E$ still requires extension, and $\left|E\right|$ and $\left|{S^{\prime}}\right|$ represent the number of elements of $E$ and $S^{\prime}$ . If two or more features have the same value in line 24, the feature with the smallest subscript is selected.

5. Experimental evaluation

5.1 Experiment setup

We build and train the model using three popular classifiers, which are Support Vector Machine(SVM) [23], K-Nearest Neighbor(KNN) [24] and Classification and regression tree(CART) [25]. SVM adopts the linear kernel. The number of the neighbors is set to be 3 as KNN classifier. Decision tree classifier chooses Gini coefficient as the measurement index.

Before feature selection begins, we preprocess the data sets. Concretely, we standardize the original data [26] and discrete the continuous data into 10 equal size bins [27]. In addition, we adopt the following strategy in order to ensure the fairness of the experiment in GFS-NPIS. If the number of the selected features is less than 50, the contrast algorithms will choose the same number as GFS-NPIS. If not, all algorithms set the number of selected features as 50. Finally, fifteen data sets and the ten-fold cross method are used to verify the performance of GFS-NPIS. Besides these, it is worth noting that we use classification accuracy and Macro-F1 to evaluate the feature subsets selected by different methods [28].

5.2 Data sets

Experiments were performed on fifteen public data sets, which were selected from the public University of California Irvine (UCI) Repository and Kaggle website [29]. The detail descriptions of the data sets are shown in Table 2, in which they are sorted in ascending order according to the number of features. The number of samples from 72 to 9298, the number of features ranges from 60 to 7070 and the number of class label ranges from 2 to 40.

Table 2
Description of data sets

Dataset	Abbr	#Features	#Instances	#Classes	Keywords	Missing value?	Unbalance ratio
Synthetic-control	Syn	60	600	6	Continuous,multi-class	No	1
Semeion	Sem	256	1593	10	Continuous, multi-class	No	1.05
USPS	Usp	256	9298	10	Continuous, multi-class	Yes	2.19
Lung_discrete	Lud	325	73	7	Discrete, multi-class	Yes	4.20
Musk-1	Mus	475	166	2	Continuous, binary	No	1.31
Isolet	Iso	617	1560	26	Continuous, multi-class	No	1.00
Yale	Yal	1024	165	15	Continuous, multi-class	No	1.00
ORL	Orl	1024	400	40	Continuous, multi-class	No	1.00
COIL20	Coi	1024	1440	20	Continuous, multi-class	No	1.00
WarPIE10P	War	2420	210	10	Continuous, multi-class	No	1.00
Lung	Lun	3312	203	5	Continuous, multi-class	Yes	23.17
Lymphoma	Lym	4026	96	9	Discrete, multi-class	Yes	23.00
RELATHE	Rel	4322	1427	2	Discrete, binary	No	1.20
TOX-171	Tox	5749	171	4	Continuous, multi-class	Yes	1.15
Leukemia	Leu	7070	72	2	Discrete, binary	Yes	1.88

The column named “Abbr” is the abbreviation of data set name. The column named “Missing value?” can help us clearly know which data set has missing values. For the missing values, we used the average value of the column where the missing values are located to fill up the missing values. The column named “Unbalance ratio” is an indicator for evaluating the degree of data set balance. Unbalance Ratio can be calculated as follows.

$\displaystyle\textit{Unbalance ratio}=\frac{n_{\max}}{n_{\min}}$

Where, $n_{\max}$ is the maximum number of categories, $n_{\min}$ is the minimum number of categories. The minimum value of Unbalance ratio is 1, which shows that the data set is completely balanced. The larger the value of Unbalance ratio, the more unbalanced the data set is. As can be seen from Table 2, most of the used data sets are balanced.

5.3 Experimental results and discussions

To verify the effectiveness of GFS-NPIS, eight popular feature selection algorithms (FFSG, FSRRC, FCBF, mRMR, JMI, MIM, CIFE and HSIC-Lasso) are used to contrast. In the experiment results, as shown in Tables 4–5, the maximum value of each row is marked by bold fonts and red color. And if the accuracy gap between two methods is within 0.5, the two algorithms will be supposed to be same performance. The row in the table “Avg” indicates the average value of the corresponding algorithm on all data sets. Finally, we use a Kolmogorov-Smirnov-test [30] to make the test. And in the experimental results, ‘ $+$ ’, ‘ $=$ ’ and ‘ $-$ ’ show that GFS-NPIS performs ‘better’, ‘equal’ or ‘worse’ than others. The row named as “W/T/L” shows the results that other methods win/tie/loss compared with GFS-NPIS.

5.3.1 Accuracy assessment

Table 4 shows the average classification accuracy of nine algorithms under SVM classifier. From Table 4, we can see that GFS-NPIS only does not achieve the highest accuracy on two data sets (WarPIE10P and Lung). Compared with FFSG, GFS-NPIS is better than FFSG on all 15 data sets, especially on Lung_discrete, Musk-1 and Isolet. The reason is that FFSG ignores the influence of the category $C$ on inter-feature interaction. It can be seen that the average classification accuracy of GFS-NPIS performs best among nine algorithms, and the average classification accuracies of FFSG and FSRRC are the second and third respectively. The reason why the other six algorithms do not perform as well as these three algorithms clearly is that inter-feature interaction is considered only in GFS-NPIS, FFSG and FSRRC. And from the experimental results, we can draw the conclusion that the evaluation function of feature interaction in GFS-NPIS is more comprehensive and applicable than those of FFSG and FSRRC.

Table 4 shows the classification accuracy under KNN classifier. Under KNN, GFS-NPIS does not achieve the highest on four data sets (USPS, Yale, Lung, RELATHE). And we can conclude that the algorithm can obtain different accuracy under different classifiers (USPS and REALTHE), GFS-NPIS achieves the highest accuracy under SVM. But it is inferior to FSRRC and FCBF under KNN.

Table 5 shows the classification accuracy under CART classifier. We can see that the average classification accuracy of our method (GFS-NPIS) is obviously higher than those of other eight algorithms.

Figure 2 is a histogram of the average classification accuracy of nine algorithms under three classifiers (SVM, KNN, CART). It can be clearly seen that GFS-NPIS performs better than other eight algorithms under all three classifiers. Comparing the three classifiers, each algorithm performs best under SVM classifier, followed by KNN and CART in sequence.

Furthermore, nine representative line charts of average classification accuracy using SVM are shown in Fig. 3. As shown in Fig. 3, the x-axis indicates the number of selected features, the y-axis is the average classification accuracy, and different colors indicate different feature selection methods. It can be discovered that GFS-NPIS outperforms other baselines in terms of average classification accuracy in Fig. 3. This is because feature redundancy and feature interaction are both considered in GFS-NPIS and NPIS is a more effective for evaluating feature interaction.

Table 3
Classification accuracy (mean $\pm$ std.) using SVM

Dataset	HSIC-Lasso	MIM	CIFE	FCBF	mRMR	JMI	FSRRC	FFSG	GFS-NPIS
Syn	86.11 $\pm$ 0.03(=)	73.66 $\pm$ 0.05(+)	86.29 $\pm$ 0.04(+)	77.78 $\pm$ 0.05(+)	89.23 $\pm$ 0.03(=)	89.09 $\pm$ 0.03(=)	77.78 $\pm$ 0.05(+)	89.72 $\pm$ 0.03(=)	89.94 $\pm$ 0.03
Sem	67.05 $\pm$ 0.03(+)	60.62 $\pm$ 0.03(+)	64.92 $\pm$ 0.03(+)	74.91 $\pm$ 0.04(+)	67.21 $\pm$ 0.03(+)	65.18 $\pm$ 0.04(+)	75.53 $\pm$ 0.03(=)	74.55 $\pm$ 0.03(+)	75.07 $\pm$ 0.03
Usp	80.78 $\pm$ 0.02(+)	76.03 $\pm$ 0.01(+)	83.56 $\pm$ 0.02(+)	86.82 $\pm$ 0.02(+)	85.78 $\pm$ 0.02(+)	84.58 $\pm$ 0.01(+)	87.02 $\pm$ 0.02(=)	86.76 $\pm$ 0.02(+)	87.04 $\pm$ 0.02
Lud	80.20 $\pm$ 0.12(+)	81.41 $\pm$ 0.11(+)	76.07 $\pm$ 0.13(+)	85.59 $\pm$ 0.10(+)	88.65 $\pm$ 0.10(+)	88.82 $\pm$ 0.10(+)	85.59 $\pm$ 0.10(+)	87.17 $\pm$ 0.10(+)	90.82 $\pm$ 0.09
Mus	64.19 $\pm$ 0.11(+)	66.02 $\pm$ 0.13(+)	64.50 $\pm$ 0.13(+)	63.89 $\pm$ 0.11(+)	67.38 $\pm$ 0.11(+)	63.87 $\pm$ 0.10(=)	63.89 $\pm$ 0.11(+)	60.65 $\pm$ 0.06(+)	72.06 $\pm$ 0.08
Iso	56.73 $\pm$ 0.05(+)	55.14 $\pm$ 0.05(+)	64.08 $\pm$ 0.04(+)	77.48 $\pm$ 0.05(=)	72.22 $\pm$ 0.05(+)	70.23 $\pm$ 0.06(+)	77.48 $\pm$ 0.05(=)	78.41 $\pm$ 0.06(+)	80.86 $\pm$ 0.05
Yal	46.57 $\pm$ 0.11(+)	57.58 $\pm$ 0.12(+)	45.70 $\pm$ 0.11(+)	64.49 $\pm$ 0.13(+)	67.36 $\pm$ 0.13(=)	58.11 $\pm$ 0.12(+)	64.49 $\pm$ 0.13(+)	64.67 $\pm$ 0.11(+)	67.09 $\pm$ 0.14
Orl	75.54 $\pm$ 0.06(+)	79.79 $\pm$ 0.06(+)	61.93 $\pm$ 0.06(+)	78.94 $\pm$ 0.05(+)	80.77 $\pm$ 0.05(+)	80.52 $\pm$ 0.05(+)	86.27 $\pm$ 0.04(+)	85.64 $\pm$ 0.05(=)	86.91 $\pm$ 0.05
Coi	70.37 $\pm$ 0.07(+)	66.87 $\pm$ 0.08(+)	74.29 $\pm$ 0.06(+)	81.10 $\pm$ 0.07(=)	82.33 $\pm$ 0.08(+)	82.73 $\pm$ 0.08(+)	81.10 $\pm$ 0.07(=)	84.80 $\pm$ 0.06(=)	85.52 $\pm$ 0.07
War	90.65 $\pm$ 0.08(+)	85.79 $\pm$ 0.13(+)	91.74 $\pm$ 0.07(=)	82.48 $\pm$ 0.12(+)	90.89 $\pm$ 0.10(+)	90.18 $\pm$ 0.11(+)	93.95 $\pm$ 0.05(-)	90.03 $\pm$ 0.09(+)	92.72 $\pm$ 0.08
Lun	86.48 $\pm$ 0.06(+)	92.17 $\pm$ 0.05(+)	88.87 $\pm$ 0.06(+)	92.46 $\pm$ 0.04(+)	95.57 $\pm$ 0.03(-)	84.65 $\pm$ 0.05(+)	92.46 $\pm$ 0.04(+)	94.57 $\pm$ 0.04(+)	94.52 $\pm$ 0.04
Lym	77.03 $\pm$ 0.18(+)	79.67 $\pm$ 0.12(+)	74.61 $\pm$ 0.16(+)	86.70 $\pm$ 0.10(+)	90.77 $\pm$ 0.10(+)	92.53 $\pm$ 0.10(+)	86.70 $\pm$ 0.10(+)	93.01 $\pm$ 0.08(=)	93.54 $\pm$ 0.08
Rel	56.42 $\pm$ 0.01(+)	62.11 $\pm$ 0.05(+)	66.30 $\pm$ 0.06(+)	75.88 $\pm$ 0.05(=)	75.35 $\pm$ 0.05(+)	64.30 $\pm$ 0.05(+)	75.35 $\pm$ 0.05(+)	67.50 $\pm$ 0.05(+)	76.83 $\pm$ 0.05
Tox	51.97 $\pm$ 0.12(+)	60.75 $\pm$ 0.12(+)	52.79 $\pm$ 0.11(+)	63.41 $\pm$ 0.14(+)	64.53 $\pm$ 0.12(=)	63.30 $\pm$ 0.13(=)	62.17 $\pm$ 0.12(+)	63.70 $\pm$ 0.16(=)	64.68 $\pm$ 0.24
Leu	66.40 $\pm$ 0.15(+)	96.44 $\pm$ 0.10(+)	94.52 $\pm$ 0.10(+)	98.01 $\pm$ 0.10(=)	97.96 $\pm$ 0.05(=)	97.99 $\pm$ 0.05(=)	98.01 $\pm$ 0.04(=)	97.18 $\pm$ 0.06(+)	98.41 $\pm$ 0.04
Avg	70.43	72.94	72.68	79.33	81.07	78.41	80.52	81.22	83.73
W/T/L	14/1/0	15/0/0	14/1/0	11/4/0	10/4/1	11/4/0	10/4/1	10/5/0

Table 4

Classification accuracy (mean $\pm$ std.) using 3KNN

Dataset	HSIC-Lasso	MIM	CIFE	FCBF	mRMR	JMI	FSRRC	FFSG	GFS-NPIS
Syn	85.89 $\pm$ 0.03(=)	84.21 $\pm$ 0.03(+)	87.37 $\pm$ 0.03(+)	85.33 $\pm$ 0.03(+)	88.17 $\pm$ 0.03(=)	87.73 $\pm$ 0.03(=)	85.33 $\pm$ 0.03(+)	90.06 $\pm$ 0.03(=)	90.19 $\pm$ 0.03
Sem	54.93 $\pm$ 0.03(+)	56.44 $\pm$ 0.07(+)	62.63 $\pm$ 0.06(+)	71.03 $\pm$ 0.07(+)	63.51 $\pm$ 0.07(+)	61.47 $\pm$ 0.07(+)	71.46 $\pm$ 0.03(=)	69.57 $\pm$ 0.07(+)	72.91 $\pm$ 0.06
Usp	81.13 $\pm$ 0.02(+)	76.86 $\pm$ 0.03(+)	83.77 $\pm$ 0.04(+)	88.08 $\pm$ 0.03(-)	85.76 $\pm$ 0.03(+)	84.55 $\pm$ 0.02(+)	88.22 $\pm$ 0.01(-)	87.38 $\pm$ 0.03(+)	87.58 $\pm$ 0.03
Lud	74.12 $\pm$ 0.12(+)	79.01 $\pm$ 0.11(+)	69.12 $\pm$ 0.14(+)	82.36 $\pm$ 0.10(+)	87.22 $\pm$ 0.10(=)	86.72 $\pm$ 0.10(+)	82.36 $\pm$ 0.10(+)	84.92 $\pm$ 0.10(+)	88.40 $\pm$ 0.10
Mus	69.15 $\pm$ 0.10(+)	67.90 $\pm$ 0.09(+)	66.66 $\pm$ 0.10(+)	66.59 $\pm$ 0.11(+)	66.72 $\pm$ 0.11(+)	68.96 $\pm$ 0.10(=)	66.59 $\pm$ 0.11(+)	65.08 $\pm$ 0.10(+)	70.75 $\pm$ 0.08
Iso	45.74 $\pm$ 0.04(+)	47.84 $\pm$ 0.09(+)	48.61 $\pm$ 0.07(+)	72.35 $\pm$ 0.10(+)	66.29 $\pm$ 0.08(+)	64.05 $\pm$ 0.09(+)	72.35 $\pm$ 0.10(+)	74.24 $\pm$ 0.10(=)	75.88 $\pm$ 0.10
Yal	39.26 $\pm$ 0.12(+)	54.94 $\pm$ 0.34(+)	38.97 $\pm$ 0.26(+)	54.67 $\pm$ 0.30(+)	61.27 $\pm$ 0.29(-)	51.34 $\pm$ 0.27(+)	54.67 $\pm$ 0.30(+)	55.82 $\pm$ 0.32(+)	58.90 $\pm$ 0.29
Orl	64.41 $\pm$ 0.07(+)	71.72 $\pm$ 0.12(+)	50.65 $\pm$ 0.12(+)	68.60 $\pm$ 0.13(+)	73.54 $\pm$ 0.11(+)	72.50 $\pm$ 0.15(+)	78.70 $\pm$ 0.06(+)	81.55 $\pm$ 0.10(-)	81.11 $\pm$ 0.11
Coi	76.99 $\pm$ 0.06(+)	75.19 $\pm$ 0.15(+)	80.97 $\pm$ 0.09(+)	86.04 $\pm$ 0.13(+)	85.93 $\pm$ 0.13(+)	86.74 $\pm$ 0.13(+)	86.04 $\pm$ 0.13(+)	87.61 $\pm$ 0.11(=)	88.80 $\pm$ 0.11
War	88.61 $\pm$ 0.10(+)	83.32 $\pm$ 0.13(+)	88.22 $\pm$ 0.08(+)	68.74 $\pm$ 0.23(+)	90.48 $\pm$ 0.10(+)	90.41 $\pm$ 0.10(+)	93.66 $\pm$ 0.05(+)	88.88 $\pm$ 0.10(+)	91.95 $\pm$ 0.07
Lun	83.78 $\pm$ 0.07(+)	91.84 $\pm$ 0.08(+)	82.72 $\pm$ 0.12(+)	92.58 $\pm$ 0.11(=)	94.33 $\pm$ 0.08(-)	81.31 $\pm$ 0.13(+)	92.58 $\pm$ 0.11(=)	93.14 $\pm$ 0.12(-)	93.11 $\pm$ 0.11
Lym	71.20 $\pm$ 0.16(+)	76.27 $\pm$ 0.11(+)	68.93 $\pm$ 0.15(+)	81.10 $\pm$ 0.11(+)	89.21 $\pm$ 0.09(+)	89.64 $\pm$ 0.09(=)	81.10 $\pm$ 0.11(+)	89.67 $\pm$ 0.10(=)	90.31 $\pm$ 0.10
Rel	56.23 $\pm$ 0.01(+)	61.72 $\pm$ 0.04(+)	60.17 $\pm$ 0.03(+)	68.44 $\pm$ 0.04(-)	66.20 $\pm$ 0.05(=)	63.77 $\pm$ 0.05(+)	68.40 $\pm$ 0.05(-)	67.70 $\pm$ 0.05(=)	66.26 $\pm$ 0.05
Tox	46.76 $\pm$ 0.09(+)	55.22 $\pm$ 0.20(+)	45.72 $\pm$ 0.26(+)	60.95 $\pm$ 0.20(=)	60.55 $\pm$ 0.24(=)	63.86 $\pm$ 0.23(+)	57.02 $\pm$ 0.12(+)	58.47 $\pm$ 0.26(+)	60.99 $\pm$ 0.24
Leu	67.66 $\pm$ 0.15(+)	97.06 $\pm$ 0.06(+)	94.69 $\pm$ 0.09(+)	98.23 $\pm$ 0.04(+)	98.66 $\pm$ 0.03(+)	98.03 $\pm$ 0.04(=)	98.23 $\pm$ 0.04(+)	98.29 $\pm$ 0.04(+)	98.94 $\pm$ 0.03
Avg	67.06	71.99	68.61	76.34	78.52	76.74	78.45	79.49	81.07
W/T/L	14/1/0	15/0/0	15/0/0	11/2/2	9/4/2	11/4/0	11/2/2	8/5/2

Table 5

Classification accuracy (mean $\pm$ std.) using CART

Dataset	HSIC-Lasso	MIM	CIFE	FCBF	mRMR	JMI	FSRRC	FFSG	GFS-NPIS
Syn	83.56 $\pm$ 0.04(+)	76.86 $\pm$ 0.05(+)	85.41 $\pm$ 0.04(=)	78.46 $\pm$ 0.04(+)	85.29 $\pm$ 0.04(=)	84.17 $\pm$ 0.04(+)	78.79 $\pm$ 0.04(+)	86.16 $\pm$ 0.04(=)	86.14 $\pm$ 0.04
Sem	53.72 $\pm$ 0.04(+)	57.19 $\pm$ 0.04(+)	62.12 $\pm$ 0.04(+)	68.10 $\pm$ 0.03(=)	62.33 $\pm$ 0.04(+)	60.67 $\pm$ 0.04(+)	68.29 $\pm$ 0.03(+)	68.46 $\pm$ 0.03(-)	67.96 $\pm$ 0.03
Usp	75.37 $\pm$ 0.02(+)	71.99 $\pm$ 0.02(+)	77.12 $\pm$ 0.02(+)	81.56 $\pm$ 0.02(+)	80.50 $\pm$ 0.02(+)	78.81 $\pm$ 0.02(+)	81.61 $\pm$ 0.02(+)	81.51 $\pm$ 0.02(=)	81.97 $\pm$ 0.02
Lud	64.93 $\pm$ 0.12(+)	64.93 $\pm$ 0.12(+)	71.44 $\pm$ 0.16(=)	64.33 $\pm$ 0.13(+)	69.60 $\pm$ 0.57(+)	70.14 $\pm$ 0.14(=)	64.33 $\pm$ 0.13(+)	68.08 $\pm$ 0.14(+)	71.83 $\pm$ 0.60
Mus	64.47 $\pm$ 0.08(=)	66.77 $\pm$ 0.08(=)	69.86 $\pm$ 0.08(-)	67.74 $\pm$ 0.08(=)	66.58 $\pm$ 0.11(=)	69.35 $\pm$ 0.08(=)	67.74 $\pm$ 0.08(=)	66.23 $\pm$ 0.10(=)	69.14 $\pm$ 0.08
Iso	37.35 $\pm$ 0.05(+)	43.28 $\pm$ 0.05(+)	47.83 $\pm$ 0.05(+)	63.41 $\pm$ 0.07(+)	62.24 $\pm$ 0.05(+)	57.04 $\pm$ 0.05(+)	63.41 $\pm$ 0.07(+)	67.50 $\pm$ 0.06(+)	70.02 $\pm$ 0.06
Yal	39.86 $\pm$ 0.11(+)	52.12 $\pm$ 0.12(+)	40.21 $\pm$ 0.09(+)	52.86 $\pm$ 0.11(+)	55.47 $\pm$ 0.12(=)	49.47 $\pm$ 0.11(+)	52.86 $\pm$ 0.11(+)	53.71 $\pm$ 0.13(=)	54.18 $\pm$ 0.14
Orl	47.83 $\pm$ 0.07(=)	56.13 $\pm$ 0.07(=)	37.51 $\pm$ 0.06(+)	58.13 $\pm$ 0.07(=)	55.50 $\pm$ 0.08(=)	52.55 $\pm$ 0.07(+)	60.81 $\pm$ 0.07(+)	57.10 $\pm$ 0.07(=)	57.54 $\pm$ 0.07
Coi	71.64 $\pm$ 0.06(+)	70.75 $\pm$ 0.07(+)	70.97 $\pm$ 0.05(+)	77.57 $\pm$ 0.07(+)	78.73 $\pm$ 0.06(+)	78.56 $\pm$ 0.06(+)	77.57 $\pm$ 0.07(+)	82.04 $\pm$ 0.06(+)	82.17 $\pm$ 0.06
War	78.63 $\pm$ 0.13(+)	77.25 $\pm$ 0.13(+)	72.47 $\pm$ 0.12(+)	71.65 $\pm$ 0.13(+)	77.93 $\pm$ 0.15(=)	77.70 $\pm$ 0.13(=)	77.79 $\pm$ 0.13(=)	75.70 $\pm$ 0.15(+)	78.30 $\pm$ 0.14
Lun	80.77 $\pm$ 0.8(+)	85.07 $\pm$ 0.8(+)	82.31 $\pm$ 0.09(+)	85.34 $\pm$ 0.07(+)	87.85 $\pm$ 0.07(+)	72.61 $\pm$ 0.09(+)	85.34 $\pm$ 0.07(+)	88.56 $\pm$ 0.08(=)	88.40 $\pm$ 0.07
Lym	60.32 $\pm$ 0.16(+)	71.67 $\pm$ 0.13(+)	74.03 $\pm$ 0.10(+)	72.61 $\pm$ 0.16(+)	76.80 $\pm$ 0.11(=)	79.28 $\pm$ 0.10(-)	72.61 $\pm$ 0.16(+)	74.11 $\pm$ 0.13(+)	76.43 $\pm$ 0.10
Rel	61.68 $\pm$ 0.05(+)	61.68 $\pm$ 0.05(+)	64.37 $\pm$ 0.05(+)	76.66 $\pm$ 0.04(+)	76.38 $\pm$ 0.05(+)	64.88 $\pm$ 0.05(+)	70.08 $\pm$ 0.05(+)	67.82 $\pm$ 0.05(+)	78.03 $\pm$ 0.05
Tox	43.55 $\pm$ 0.11(+)	50.27 $\pm$ 0.77(+)	44.12 $\pm$ 0.12(+)	50.72 $\pm$ 0.10(=)	52.04 $\pm$ 0.11(=)	51.80 $\pm$ 0.12(=)	52.46 $\pm$ 0.11(=)	53.10 $\pm$ 0.10(=)	54.93 $\pm$ 0.53
Leu	60.41 $\pm$ 0.15(+)	95.97 $\pm$ 0.06(=)	99.89 $\pm$ 0.00(-)	96.23 $\pm$ 0.07(=)	97.69 $\pm$ 0.05(=)	97.20 $\pm$ 0.05(-)	96.20 $\pm$ 0.07(=)	95.59 $\pm$ 0.07(=)	95.51 $\pm$ 0.07
Avg	61.61	66.80	66.64	71.02	72.33	69.62	71.33	72.38	74.17
W/T/L	13/2/0	12/3/0	12/2/1	10/5/0	7/8/0	9/4/2	11/4/0	6/8/1

Figure 2.

Average classification accuracy.

Figure 3.

Accuracy comparison on nine feature selection methods.

5.3.2 Macro-F1 assessment

Table 6 shows the Macro-F1 values of nine algorithms on SVM classifier. It can be seen that GFS-NPIS does not get the highest Macro-F1 on two data sets (WarPIE10P and Lung). Table 7 shows the Macro-F1 values of nine algorithms under 3KNN classifier. It can be found that GFS-NPIS performs not as well on 3KNN as SVM. But it also can be seen that GFS-NPIS achieved the highest average Macro-F1 from the last row. Table 8 shows the Macro-F1 of nine algorithms under CART classifier. It can be seen that GFS-NPIS do not get the highest Macro-F1 only on four data sets (Lung_discrete, Yale, ORL, Leukemia). And GFS-NPIS still achieved the highest average Macro-F1 among nine algorithms. We can draw a conclusion that GFS-NPIS performs better than other eight algorithms in terms of Macro-F1 under three different classifiers.

Table 6
Macro-F1 using SVM

Dataset	HSIC-Lasso	MIM	CIFE	FCBF	mRMR	JMI	FSRRC	FFSG	GFS-NPIS
Syn	85.68%	73.22%	86.11%	77.42%	89.66%	88.97%	77.42%	89.55%	89.84%
Sem	55.98%	58.93%	63.93%	73.81%	66.06%	64.13%	74.40%	73.60%	74.09%
Usp	78.63%	72.29%	81.38%	84.84%	83.92%	82.49%	85.27%	84.90%	85.23%
Lud	69.57%	74.17%	65.59%	80.28%	84.34%	84.12%	80.28%	83.06%	84.99%
Mus	62.85%	63.85%	61.26%	61.41%	65.03%	61.86%	61.41%	54.85%	71.07%
Iso	55.45%	53.43%	62.74%	76.49%	70.96%	69.07%	76.49%	77.45%	79.81%
Yal	40.29%	52.83%	37.70%	58.35%	60.45%	51.19%	58.35%	57.70%	60.89%
Orl	70.82%	75.97%	55.17%	74.94%	76.91%	76.67%	83.33%	82.84%	84.21%
Coi	67.97%	62.49%	71.50%	78.62%	80.29%	80.62%	78.62%	82.91%	83.55%
War	89.85%	84.81%	91.12%	81.38%	89.96%	88.96%	93.42%	87.02%	92.14%
Lun	70.44%	83.22%	73.58%	84.53%	89.88%	63.23%	84.53%	87.70%	88.06%
Lym	64.99%	66.33%	56.57%	76.43%	84.84%	87.92%	76.43%	89.65%	90.19%
Rel	42.86%	52.60%	64.70%	75.34%	74.96%	58.28%	65.76%	61.05%	76.49%
Tox	49.00%	58.14%	50.79%	61.66%	63.15%	61.67%	60.54%	62.02%	62.99%
Leu	57.17%	96.20%	93.31%	97.83%	97.76%	97.82%	97.83%	96.94%	98.27%
Avg	64.10%	68.56%	67.70%	76.22%	78.54%	74.47%	76.94%	78.08%	81.46%

Table 7

Macro-F1 using 3KNN

Dataset	HSIC-Lasso	MIM	CIFE	FCBF	mRMR	JMI	FSRRC	FFSG	GFS-NPIS
Syn	85.69%	84.03%	87.05%	85.17%	88.04%	87.61%	85.17%	89.94%	90.09%
Sem	53.50%	54.82%	61.37%	69.80%	62.46%	60.43%	70.26%	68.20%	71.95%
Usp	79.22%	74.29%	81.89%	86.85%	84.34%	82.88%	87.00%	85.95%	86.75%
Lud	62.99%	69.74%	56.50%	74.92%	81.86%	80.40%	74.92%	79.06%	83.68%
Mus	68.48%	67.60%	65.72%	67.09%	66.38%	68.47%	67.09%	66.10%	70.63%
Iso	44.91%	46.54%	47.30%	71.46%	64.97%	62.88%	71.46%	73.54%	73.90%
Yal	31.95%	49.02%	31.52%	47.46%	54.56%	43.79%	47.46%	48.83%	54.14%
Orl	43.23%	66.66%	43.23%	63.32%	68.22%	67.02%	74.41%	77.94%	77.29%
Coi	75.25%	73.39%	79.14%	84.85%	84.62%	85.64%	84.85%	86.58%	87.80%
War	87.80%	81.70%	87.64%	66.03%	89.56%	89.17%	93.12%	87.74%	91.05%
Lun	64.60%	83.89%	59.63%	85.07%	88.03%	60.41%	85.07%	85.14%	84.71%
Lym	53.80%	62.60%	47.21%	70.31%	82.77%	83.31%	70.31%	84.04%	84.23%
Rel	40.56%	50.10%	54.66%	61.23%	58.08%	53.65%	60.27%	60.01%	57.95%
Tox	35.02%	52.17%	42.12%	60.55%	59.67%	62.31%	56.09%	56.62%	60.05%
Leu	58.80%	96.90%	93.12%	98.14%	98.20%	97.91%	98.14%	98.16%	98.85%
Avg	59.05%	67.56%	62.54%	72.82%	75.45%	72.39%	75.11%	76.52%	78.20%

Table 8

Macro-F1 using CART

Dataset	HSIC-Lasso	MIM	CIFE	FCBF	mRMR	JMI	FSRRC	FFSG	GFS-NPIS
Syn	83.46%	76.60%	85.32%	78.58%	85.01%	83.99%	78.58%	86.03%	86.00%
Sem	52.45%	55.52%	61.23%	66.71%	61.32%	59.59%	67.11%	67.35%	67.15%
Usp	73.47%	69.73%	74.89%	79.89%	78.72%	76.80%	79.96%	79.69%	80.31%
Lud	46.32%	53.12%	61.26%	52.56%	58.56%	61.45%	52.56%	56.02%	60.40%
Mus	63.17%	65.52%	68.05%	66.35%	64.89%	68.32%	66.35%	65.10%	67.98%
Iso	36.49%	42.43%	47.03%	62.66%	61.71%	56.15%	62.66%	66.89%	69.61%
Yal	33.65%	45.99%	34.72%	46.57%	49.26%	42.36%	46.57%	47.45%	47.52%
Orl	41.32%	49.91%	31.34%	51.97%	49.38%	45.75%	54.65%	50.96%	51.18%
Coi	70.37%	69.19%	69.25%	76.26%	77.38%	77.32%	76.26%	81.08%	80.93%
War	76.85%	75.41%	70.03%	69.66%	76.45%	75.58%	75.93%	73.77%	76.24%
Lun	64.27%	76.56%	67.24%	76.69%	77.57%	52.03%	76.69%	78.30%	78.17%
Lym	40.28%	51.33%	55.51%	54.89%	60.08%	62.29%	54.89%	58.67%	62.04%
Rel	45.56%	53.08%	63.32%	76.25%	76.08%	59.69%	65.75%	61.75%	77.75%
Tox	31.49%	50.27%	44.12%	50.72%	52.04%	51.79%	52.46%	53.10%	53.19%
Leu	54.33%	95.53%	99.88%	95.81%	97.18%	96.83%	95.79%	94.98%	95.03%
Avg	54.23%	62.01%	62.21%	67.04%	68.37%	64.66%	67.08%	68.08%	70.23%

Table 9

Comparison of time complexity

Algorithms	HSIC Lasso	MIM	CIFE	FCBF	mRMR	JMI	FSRRC	FFSG	GFS-NPIS
Complexity	$O\left({nm^{2}}\right)$	$O\left({mn}\right)$	$O\left({kmn}\right)$	$O\left({n^{2}}\right)$	$O\left({mn^{2}}\right)$	$O\left({kmn}\right)$	$O\left({n^{2}}\right)$	$O\left({mn^{2}}\right)$	$O\left({gn^{2}}\right)$

Figure 4 is a histogram of average Macro-F1 for nine algorithms under SVM, KNN and CART respectively. It can be clearly seen that the Macro-F1 of GFS-NPIS is higher than those of other algorithms under three classifiers, and each algorithm performs best on SVM, followed by KNN and CART in sequence.

Figure 4.

Average Macro-F1.

5.3.3 Complexity analysis

A good feature selection algorithm has not only higher classification accuracy but also less time complexity [31]. Table 8 gives the time complexity of nine algorithms. In Table 8, the number of features selected is $k$ , $m$ represents the number of instances in the data sets, the total number of features is $n$ , and g represents the number of groups for GFS-NPIS. From Table 9, it can be concluded that FSRRC, FCBF and MIM perform best among nine algorithms. Although FSRRC, MIM and FCBF attain the best time complexity, their classification accuracies are not as good as their time complexity. The time complexity of our method is $O\left({gn^{2}}\right)$ , which is acceptable than other methods.

In GFS-NPIS, the time complexity of Step1 is $O\left({n+\textit{nlogn}}\right)=O\left(\textit{nlogn}\right)$ ; The time complexity of Step2 is $O\left({gn^{2}}\right)$ ; The time complexity of Step3 is $O\left({g^{4}}\right)$ . Overall, the time complexity of GFS-NPIS is $O\left({\textit{nlogn}+gn^{2}+g^{4}}\right)$ . Commonly, it is true that $g<<n$ ; Hence, the time complexity of the GFS-NPIS method is approximately $O\left({gn^{2}}\right)$ . To sum up, the time complexity of our method is acceptable than other methods.

6. Conclusions and future work

Feature selection aims to remove redundant features and retain useful features [32]. At present, most feature selection methods only considered feature relevance and feature redundancy, but ignored feature interaction. Our study focuses on feature interaction as well as feature relevance and feature redundancy. In this paper, a new algorithm feature selection method GFS-NPIS is proposed. While removing irrelevant and redundant features, GFS-NPIS can select interactive features. The experiment on the fifteen public datasets illustrated that GFS-NPIS could select more important and useful features than HSIC-Lasso, MIM, CIFE, FCBF, mRMR, JMI, FSRRC and FFSG in most cases. Therefore, combining feature relevance, feature redundancy and feature interaction can help to define more important information from the different data set for improving the final classification performance.

In addition, there still exist some problems. For example, it is too complex in the process of calculating NPIS, which leads to time-consuming on some high-dimensional data set (USPS, Tox-171, Leukemia). In a word, our future work is improving the computational performance of NPIS to improve our algorithm GFS-NPIS in terms of accuracy and time consuming.

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

CRediT authorship contribution statement

Hongfang Zhou: Conceptualization; Methodology; Writing original draft. Lei An: Software; Validation; Formal analysis; Writing original draft. Rourou Zhu: Investigation; Writing original draft.

Footnotes

Acknowledgments

The corresponding author would like to thank the support from the National Key Research and Development Plan under the Grant of 2017YFB1402103, the National Natural Science Foundation of China under the Grant of 61971347, the Key Research and Development Program of Shaanxi under the Grant of 2021JZ-49, the Education Department of Shaanxi Province Key Laboratory Project under the Grant of 15JS079, Xi’an Science Program Project under the Grant of 2022GXFW0075.

References

Zhou

H.F.

Zhang

J.W.

Zhou

Y.Q.

Guo

X.J.

and Ma

Y.M.

, A feature selection algorithm of decision tree based on feature weight, Expert Syst Appl 164(4) (2021), 113842.

Tang

Dai

and Xiang

, Feature selection based on feature interactions with application to text categorization, Expert Syst Appl 120 (2019), 207–216.

Lxwa

Syja

and Syja

, A feature selection method via analysis of relevance, redundancy, and interaction, Expert Syst Appl (2021).

Jakulin

and Bratko

, Analyzing Attribute Dependencies, in: 7th European Conferenc on Priciples and Practice of Knowledge Discovery, 2003.

Lin

Ren

Luo

and Qi

, A new feature selection method based on symmetrical uncertainty and interaction gain, Comput Biol Chem 83.

Zeng Yin

Zhang

and Rui

, A novel feature selection method considering feature interaction, Pattern Recognition: The Journal of the Pattern Recognition Society 48(8) (2015), 2656–2666.

and Liu

, Efficient Feature Selection via Analysis of Relvance and Redundancy, J Mach Learn Res 5(12) (2004), 1205–1224.

Lewis

D.D.

, Feature selection and feature extraction for text categorization, in: Workshop on Speech & Natural Language, 1992.

Peng

Long

and Ding

, Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy, IEEE Transactions on Pattern Analysis & Machine Intelligence 27(8) (2005), 1226–1238.

10.

Lin

and Tang

, Conditional Infomax Learning: An Integrated Framework for Feature Extraction and Fusion, in: European Conference on Computer Vision, 2006.

11.

Bennasar

Hicks

and Setchi

, Feature selection using joint mutual information maximisation, Expert Syst Appl 42(22) (2015), 8520–8532.

12.

Luo

Gao

and Lin

, A new feature selection algorithm based on relevance, redundancy and complementarity, Comput Biol Med 119 (2020), 103667.

13.

Hua

Zhou

Hua

and Zhang

, Strong approximate Markov blanket and its application on filter-based feature selection, Appl Soft Comput 87 (2020), 105957.

14.

Yamada

Jitkrittum

Sigal

Xing

E.P.

and Sugiyama

, High-dimensional feature selection by feature-wise kernelized lasso, Neural Comput 26(1) (2014), 185–207.

15.

Gretton

Bousquet

Smola

and Schölkopf

, Measuring statistical dependence with Hilbert-Schmidt norms, in: International conference on algorithmic learning theory, Springer, 2005, pp. 63–77.

16.

Héctor

C.G.

Chloé-Agathe

Samuel

and Makoto

, Block HSIC Lasso: model-free biomarker detection for ultra-high dimensional data, Bioinformatics (14) (2019), i427–i435.

17.

Shannon

C.E.

, A mathematical theory of communication, ACM SIGMOBILE Mobile Computing and Communications Review 5(1) (2001), 3–55.

18.

Cover

T.M.

, Elements of information theory, John Wiley & Sons, 1999.

19.

Teukolsky

S.A.

Flannery

B.P.

Press

W.H.

and Vetterling

W.T.

, Numerical Recipes in C, SMR. 693(1) (1992), 59–70.

20.

Wyner

A.D.

, A definition of conditional mutual information for arbitrary ensembles, Information and Control 38(1) (1978), 51–59.

21.

Koller

and Sahami

, Toward optimal feature selection, in: Stanford InfoLab, 1996.

22.

García-Torres

Gómez-Vela

Melián-Batista

and Moreno-Vega

J.M.

, High-dimensional feature selection via feature grouping: A Variable Neighborhood Search approach, Inform Sciences 326 (2016), 102–118.

23.

Cortes

and Vapnik

, Support-vector networks, Mach Learn 20(3) (1995), 273–297.

24.

Altman

N.S.

, An introduction to kernel and nearest-neighbor nonparametric regression, The American Statistician 46(3) (1992), 175–185.

25.

Loh

W.Y.

, Classification and regression trees, Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 1(1) (2011), 14–23.

26.

Vinh

N.X.

Zhou

Chan

and Bailey

, Can high-order dependencies improve mutual information based feature selection? Pattern Recogn 53 (2016), 46–58.

27.

Fayyad

and Irani

, Multi-interval discretization of continuous-valued attributes for classification learning, 1993.

28.

Zhou

Wang

and Zhang

, Feature selection based on weighted conditional mutual information, Applied Computing and Informatics, 2020.

29.

Asuncion

and Newman

, UCI machine learning repository, in: Irvine, CA, USA, 2007.

30.

Demšar

, Statistical comparisons of classifiers over multiple data sets, The Journal of Machine Learning Research 7 (2006), 1–30.

31.

Cai

Luo

Wang

and Yang

, Feature selection in machine learning: A new perspective, Neurocomputing 300 (2018), 70–79.

32.

Gao

Zhao

Zhang

and Wang

, Feature selection considering two types of feature relevancy and feature interdependency, Expert Syst Appl 93 (2018), 423–434.

A grouping feature selection method based on feature interaction

Abstract

Keywords

1. Introduction

2. Related works

3.1 Information theory

4.1 Problem

4.2 Method

Table 1 Pseudo-code of GFS-NPIS

5.1 Experiment setup

5.2 Data sets

Table 2 Description of data sets

5.3.1 Accuracy assessment

Table 3 Classification accuracy (mean ± std.) using SVM

Table 6 Macro-F1 using SVM

6. Conclusions and future work

Declaration of competing interest

CRediT authorship contribution statement

Footnotes

Acknowledgments

References

Table 1
Pseudo-code of GFS-NPIS

Table 2
Description of data sets

Table 3
Classification accuracy (mean $\pm$ std.) using SVM

Table 6
Macro-F1 using SVM