A multi-label feature selection method based on an approximation of interaction information

Abstract

High-dimensional multi-label data is widespread in practical applications, which brings great challenges to the research field of pattern recognition and machine learning. Many feature selection algorithms have been proposed in recent years, among which the filtering feature selection algorithm is the most popular one because of its simplicity. Therefore, filtering feature selection has become a hot research topic, especially the multi-label feature selection algorithm based on mutual information. In the algorithm, the computation cost of high dimensional mutual information is expensive. How to approximate high order mutual information based on low order mutual information has become a major research direction. To our best knowledge, all existing feature selection algorithms that consider the label correlation will increase the computational cost greatly. Therefore, this paper proposes an approximation method of three-dimensional interaction information, which is applied to the calculation of correlation and redundancy. It can take the correlation of labels into account and don’t increase the computation cost significantly at the same time. Experiments analysis results show that the proposed method is effective.

Keywords

Multi-label feature selection interaction information mutual information

1. Introduction

With the rapid development of technology, data information became more and more complex, for example multi label, high dimension, multi-modal data [1]. The actual requirements are no longer limited to single label data. On the other hand, multi-label data is becoming more and more widespread. Therefore, in recent years, multi-label learning has attracted extensive attention in the fields of data mining and machine learning, such as text classification [2], image semantic annotation [3], gene classification [4], multi-media [5], and so on.

Due to the increasing number of features in multi-label data, multi-label learning also faces the problem of dimension curse [6]. High-dimensional multi-label data usually contains a large number of redundant and irrelevant features, which affects the performance of the multi-label classifier and increases the training cost of the classifier.

As a dimensionality reduction technique, multi-label feature selection can effectively solve the above problems. It can reduce the training cost of classifier, simplify the model, and prevent overfitting [1]. Multi-label feature selection is usually divided into three types, i.e. filter type, embedding type and wrapper type. In general, the wrapper algorithm can select high-quality features. However, considering the diversity of feature combinations and the classifier training for each selection, the computation cost of wrapper feature selection algorithm is very expensive. Embedding feature selection algorithm combines feature selection with classifier together. Filter feature selection is independent of classifier and selects feature subset through a specific evaluation metric, such as Cosine correlation [7], Pearson correlation coefficient [7], information theory [8, 9, 10, 11, 12, 13], ReliefF [14], symmetrical uncertainty [15] and so on.

Pearson correlation coefficient can only measure the linear correlation between the variables. Information measurement, for example mutual information, can measure both the linear correlation and the nonlinear correlation between the variables. Based on mutual information, many efficient multi-label feature selection algorithms have been proposed.

The goal of multi-label feature selection based on mutual information is to select a feature subset to maximize the mutual information between the feature subset and the label set. The mutual information between feature subset and label set is called joint mutual information. It is difficult to calculate the accurate joint mutual information value. The computational cost increases rapidly with the increase of feature dimensions. It cannot meet the requirements of practical application [8]. Therefore, the trends of multi-label feature selection based on mutual information is to approximate the high-dimensional mutual information, such as the joint mutual information between features and labels and that between features [8, 13, 9, 11, 10, 12]. However, the problem of these algorithms is that most of them ignore the correlation between labels [8, 16, 9]. In some algorithms, the correlation between labels is calculated directly through calculating the interactive information or three-dimensional joint entropy [13, 12]. These methods are computationally intensive. In addition, the redundancy is usually measured by calculating the mutual information accumulation between features, and the redundancy between selected feature set is not considered [8, 10, 16, 11]. Only a few algorithms take the correlation between feature sets into consideration, which also involves the calculation of high-dimensional joint entropy or high-dimensional joint probability [9]. They are computationally intensive also.

For realizing efficient multi-label feature selection, a new correlation measurement based on the proportion hypothesis is proposed in the paper. The label correlation is considered. A new correlation redundancy measurement method considering the correlation between selected feature sets is proposed also.

The main contributions of the paper are as follows:

1)
An approximate estimation method of 3D interaction information based on the assumption of information proportion is proposed.
2)
Based on the hypothesis of contributions 1), a correlation measure is proposed, which takes the correlation between labels into account and avoids the calculation of high-dimensional joint entropy or joint probability.
3)
Based on the hypothesis of contributions 1), a redundant measure is proposed, which takes the correlation between selected feature sets into account and avoids the calculation of high-dimensional joint entropy or joint probability.
4)
It is compared with state-of-the-art feature selection algorithms on 6 public data sets to prove the effectiveness of the proposed method.

The following is the arrangement of the contents of this paper. We cover the background information, the related formulas, and some definitions in Section 2. The related work is introduced in Section 3. In Section 4, the multi-label feature selection algorithm proposed in this paper is introduced. In Section 5, the experiment is designed and the experimental results are analyzed. In Section 6, some conclusions are summarized.
2. Preliminaries

The information theories used in this paper are all based on Shannon entropy [17], which measures the amount of information of a variable. Given discrete random variables $X=\{x_{1},x_{2},\ldots,x_{n}\}$ , $Y=\{y_{1},y_{2},\ldots,y_{m}\}$ , $x_{i}\in X$ , $y_{j}\in Y$ , $p(x_{i})$ and $p(y_{j})$ are probability mass functions. $p(x_{i},y_{j})$ is a joint probability, $p(x_{i}|y_{j})$ is a conditional probability. The entropy of $X$ is defined as:

$\displaystyle H(X)=-\sum_{i=1}^{n}{p(x_{i})\log p(x_{i})}$ (1)

The joint entropy measures the amount of information about two variables. The joint entropy is defined as follows:

$\displaystyle H(X,Y)=-\sum_{i=1}^{n}{\sum_{j=1}^{m}{p(x_{i},y_{j})}}\log p(x_{% i},y_{j})$ (2)

where $p(x_{i},y_{j})$ is the joint probability. Obviously, information entropy is symmetry, i.e.

$\displaystyle H(X,Y)=H(Y,X)$ (3)

Extending to multiple variables, the joint entropy is as follows.

$\displaystyle H(X_{1},X_{2},\ldots,X_{n})=-\sum_{i_{1}=1}^{n_{1}}{\sum_{i_{2}=% 1}^{n_{2}}\ldots\sum_{i_{k}=1}^{n_{k}}{p(x_{i_{1}},x_{i_{2}},\ldots,x_{i_{k}})% }}\log p(x_{i_{1}},x_{i_{2}},\ldots,x_{i_{k}})$ (4)

where $p(x_{i_{1}},x_{i_{2}},\ldots,x_{i_{k}})$ is the joint probability.

The conditional entropy quantifies the amount of information needed to describe the outcome of a random variable given that the value of another random variable is known. The conditional entropy is defined as follows:

$\displaystyle H(X|Y)=-\sum_{i=1}^{n}{\sum_{j=1}^{m}{p(x_{i},y_{j})}}\log p(x_{% i}|y_{j})$ (5)

where $p(x_{i}|y_{j})$ is a conditional probability. Based on the above definition, we can get the relationship:

$\displaystyle H(X,Y)=H(X)+H(Y|X)$ (6)

In a similar way

$\displaystyle H(X,Y,Z)=H(X,Y|Z)+H(Z)=H(X,Z|Y)+H(Y)=H(Y,Z|X)+H(X)$ (7)

Mutual information measures the amount of information shared between two variables. It is defined as follows.

$\displaystyle I(X;Y)=-\sum_{i=1}^{n}{\sum_{j=1}^{m}{p(x_{i},y_{j})\log\frac{p(% x_{i})p(y_{j})}{p(x_{i},y_{j})}}}$ (8)

The relationship between mutual information and entropy is as follows.

$\displaystyle I(X,Y)=H(X)-H(X|Y)$ (9)

In a similar way

$\displaystyle I(X,Y)=H(Y)-H(Y|X)$ (10)

It is easy get the following result.

$\displaystyle I(X,Y)=H(X)+H(Y)-H(X,Y)$ (11)

The conditional mutual information measures the correlation between two random variables $X$ and $Y$ given that the random variable $Z$ is known. It is defined as follows.

$\displaystyle I(X;Y\mid Z)=H(X\mid Z)-H(X\mid Y,Z)$ (12)

The joint mutual information measures the correlation between two random variables ( $X, Y$ ) and another random variable $Z$ . It is defined as follows.

$\displaystyle I(X,Y;Z)=H(Z)-H(Z\mid X,Y)$ (13)

It is easy get the following result.

$\displaystyle I(X,Y;Z)=I(X;Z)+I(Y;Z\mid X)=I(Y;Z)+I(X;Z\mid Y)$ (14)

The interaction information is used to measure the correlation among three random variables. And it is defined as follows:

$\displaystyle I(X;Y;Z)=I(X;Z)+I(Y;Z)-I(X,Y;Z)$ (15)

It is easy to get the following result:

$\displaystyle I(X;Y;Z)=I(Y;Z)-I(Y;Z\mid X)=I(X;Z)-I(X;Z\mid Y)=I(X;Y)-I(X;Y% \mid Z)$ (16)

Entropy, conditional entropy, joint entropy, mutual information, joint mutual information and conditional mutual information are all none negative values, but interaction information can be positive or negative or zero. When the interaction information is negative, the random variables X and Y together can provide Z with information that they cannot provide alone, so it is called synergy. When the interaction information is positive, it means the common information between them, so it is redundant. When the interaction information is zero, it is considered that the introduction of one variable will not affect the relationship between the other two variables.

3. Related works

3.1 Multi label classification

Up to now, many multi-label learning algorithms have been proposed. These algorithms fall into three broad categories based on the use of label correlation [18], i.e. first-order strategy, second-order strategy, high-order strategy. First-order strategy does not consider the babel dependencies. The multi-label classification problem is usually transformed into several independent binary classification problems. For example, binary relevance (BR) approach [3], ML-kNN [19], and sparse weighted instance-based multilabel (SWIM) [20]. The advantages of first-order strategy are easy calculation and easy to model. However, it does not consider the correlation between labels, which may eventually lead to poor performance. Second-order strategy considers pair-to-pair label relationships, for example, RankSVM [4], Calibrated Multilabel Perceptrons (CMLPC) [21], Correlative Multi-label (CML) [22]. The generalization performance of second-order strategy is usually excellent. But some application scenarios may have high-order label correlation, which is contrary to the assumption that only second-order label correlation exists. In the high-order strategy, the model can usually express the label correlation better, but the complexity of the model will be higher, for example classifier chains (CCs) [21], ensembles of pruned set (EPS) [22].

3.2 Multi-label feature selection

Up to now, multi-label feature selection algorithms (filter, embedding, wrapper) have developed quickly. In terms of wrapper methods, Gharroudi et al. proposed Binary Relevance Random Forest (BRRF), which ignores the correlation between labels. In the method, multi-label data sets are first converted to multiple single-label data sets, and random forest classifier is adopted. Zhang et al. proposed Multi-Label Naive Bayes method (MLNB) [23], which applies the principal component analysis to determine correlated and redundant features and select the best features with the genetic algorithm.

In terms of embedding methods, Zhang et al. proposed LIFT [24], which is based on the assumption that each label has its own specific features. Ma et al. proposed SFUS [25] method, which combines sparse feature selection and label correlation to select the optimal feature subset. Jian et al. proposed Multi-label Informed Feature Selection (MIFS) [26] method, which selects the most discriminative features based on label sparsity and label correlation. Huang et al. proposed Joint Feature Selection and Classification for Multilabel Learning (JFSC) [27] method. This method utilizes pair label correlation to learn the specific correlation features and the shared features between labels. It is based on Fisher discriminant-based regularization the inner-class distance and maximize the intraclass distance for each label.

In terms of filter methods, Lee et al. proposed AMI [8], which is based on Shearer’s inequality scaling [28]. The feature selection criterion is defined as follows.

$\displaystyle J(f)=\max_{f_{k}\in F-S}\left[\sum_{l\in L}{I(f_{k};l)-\sum_{f% \in S}{I(f_{k};f)}}\right]$ (17)

where $J(\cdot)$ is the evaluation criterion, $f_{k}$ is a candidate feature, $F$ is an unselected feature, and $L$ is a label set.

The disadvantage of the algorithm is that it does not consider the correlation of labels, and its advantages are computation low, simple and practical.

Lee et al. proposed a multi-label feature selection method called Pairwise Multi-label Utility (PMU) [12] based on three-dimensional interaction information. The maximization criterion is as follows.

$\displaystyle J(f_{k})=\sum_{l_{i}\in L}{I(f_{k};l_{i})-\sum_{f_{j}\in S}{\sum% _{l_{i}\in L}{I(f_{k};f_{j};l_{i})}-}}\sum_{l_{i}\in L}{\sum_{l_{j}\in L}{I(f_% {k};l_{i};l_{j})}}$ (18)

This algorithm is highly explanatory but it need computing the three-dimensional interaction information repeatedly. The computation cost is very expensive.

Lin et al. proposed MDMR [9], which applied the principle of maximum correlation and minimum redundancy of single-label feature selection MRMR [29] to the multi label feature selection. The maximization criterion of feature selection is as follows:

$\displaystyle J(f_{k})=\sum_{f_{j}\in S}{\sum_{l_{i}\in L}{[I(f_{k};l_{i})-I(f% _{k};l_{i};f_{j})]}}$ (19)

The disadvantage of the algorithm is that it needs calculating the conditional mutual information, which requires a large amount of computation, and does not consider the correlation between labels. Lee et al. proposed SCLS [11], which uses variable coefficient contraction between redundancy and correlation, and the feature selection criterion is defined as follows.

$\displaystyle\max_{f_{k}\in\{F-S\}}\left[\sum_{l\in L}{I(f_{k};l)}-\sum_{f-S}{% \sum_{l\in L}{\frac{I(f_{k};l)}{H(f_{k})}}}I(f_{k};f)\right]$ (20)

where $H(\cdot)$ is entropy. The disadvantage of this algorithm is that the correlation between labels is not considered, and the advantage is that the computation cost is low.

Zhang et al. proposed LRFS [16], which is based on conditional mutual information, and the maximization criterion of feature selection is as follows.

$\displaystyle J(f_{k})=\sum_{l_{i}\in L}\left\{\sum_{l_{i}\neq l_{j},l_{j}\in L% }{I}(f_{k};l_{j}\mid l_{i})-\frac{1}{|S|}\sum_{f_{j}\in S}{I}(f_{k};f_{j})\right\}$ (21)

The advantage of this algorithm is that it considers the correlation of labels, but the disadvantage is that it needs calculating the conditional mutual information, which requires a large amount of computation. Seo et al. proposed GICS [30], which is based on the general form of entropy, and the maximization criterion of feature selection is as follows.

$\displaystyle J(f_{k})\propto|S|\sum_{l\in L}{I}(f_{k};l)-|L|I(f_{k};f)\propto I% (f_{k};l)-\frac{|L|}{|S|}I(f_{k};f)$ (22)

where $|.|$ is an indication function, $|L|$ is the number of elements in the label sets, and $|S|$ is the number of selected feature set elements.

Due to the $k$ -cardinality entropy involved in the algorithm, the fixed $k$ may not be applicable to all data sets, which has the advantage of low computation cost. Paniri et al. proposed MLACO [7], which is the first time to operate multi labels feature selection with ant colony optimization (ACO) algorithm and utilize the Pearson correlation coefficient and cosine correlation to measure the redundancy and the relevance. The algorithm has the advantage that it does not need to discretize features. Its disadvantage is that it is based on Pearson correlation coefficient and cosine correlation coefficients that can only measure the linear correlation and cannot measure the nonlinear correlation effectively.

Zhang et al. proposed MCMFS [10], which is based on the method of label clustering. The correlation between the feature and the label sets is approximated, and the maximum mutual information between the candidate feature and the label replaces the correlation between the label sets, and the maximization criterion of feature selection is as follows.

$\displaystyle J(f_{k})=\max_{l_{j}\in L}I(f_{k};l_{j})-\frac{1}{|S|}\sum_{f_{j% }\in S}{I}(f_{k};f_{j})$ (23)

The model complexity of the algorithm is low, and it is simple and efficient. However, some features may provide information for multiple labels, the algorithm possibly ignore these features.

4. The proposed method

4.1 Proportion-based interaction information estimation

To single label feature selection, Nojun Kwak and Chong-Ho Choi proposed MIFS-U (Mutual information feature selection under uniform information distribution) [31], which is based on the assumption of uniform information distribution. The approximate estimation formula of conditional mutual information is designed based on information Venn diagram, and the validity is proven by some experiments. Given random variables $X$ , $Y$ , $Z$ , the information Venn diagram is shown in Fig. 1.

Figure 1.

Venn diagram illustrates the relation between $X$ , $Y$ and $Z$ .

The equation $\frac{H(X|Z)}{H(X)}\approx\frac{I(X;Y|Z)}{I(X;Y)}$ given in MIFS-U is equivalent to $\frac{e+c}{a+c+d+e}\approx\frac{c}{c+d}$ in the Venn diagram. Approximate calculation of conditional mutual information as follow:

$\displaystyle I(X;Y|Z)\approx\frac{H(X|Z)}{H(X)}I(X;Y)=\frac{H(X)-I(X;Z)}{H(X)% }I(X;Y)$ (24)

According to the above formula, we can get

$\displaystyle I(X;Y;Z)\approx I(X;Y)-I(X;Y|Z)=\left[1-\frac{H(X)-I(X;Z)}{H(X)}% \right]I(X;Y)=\frac{I(X;Y)I(X;Z)}{H(X)}$ (25)

Similarly, we can get the symmetry estimation, i.e.

$\displaystyle I(X;Y;Z)\approx\frac{I(X;Y)I(Y;Z)}{H(Y)}$ (26)

To avoid overestimating the redundancy, we take the minimum value, i.e.

$\displaystyle I(X;Y;Z)\approx\min\left\{\frac{I(X;Y)I(X;Z)}{H(X)},\frac{I(X;Y)% I(Y;Z)}{H(Y)}\right\}$ (27)

The advantage of this estimation is that the calculation of 3D joint entropy is avoided and the computation cost is reduced. It is suitable to model more complicated problems.

4.2 Measures of relevance and redundancy

In the incremental search, most of the existing algorithms are based on relevance minus redundancy. $F$ represents features set, $S$ represents the set of selected features. In the frame form of relevance minus redundancy, we select the feature $f$ by maximizing the following criterion.

$\displaystyle\max_{f\in\{F-S\}}[\textit{Rel}(f)-\textit{Red}(f)]$ (28)

where $\textit{Rel}(f)$ usually represents the correlation between a feature and set of labels, which is called relevance. $\textit{Red}(f)$ usually represents the correlation between the feature to be selected and the set of selected features, which is called redundancy.

The traditional correlation measurement usually does not consider the correlation between labels, for example, the correlation $\sum_{l\in L}{I(f;l)}$ . This paper proposes a correlation measurement of second-order labels.

For the sake of analysis advantage, we first consider the case that the labels set has only two labels. Given two labels $l_{i}$ and $l_{j}$ , $l_{i}$ , $l_{j}\in L$ , $i\neq j$ , the Venn diagram, which is used to illustrate the relation between $l_{i}$ , $l_{j}$ and $f$ , is shown as Fig. 2.

Figure 2.

Venn diagram which is used to illustrate the relation between $l_{i}$ , $l_{j}$ and $f$ .

According to Section 4.1, we can get the interaction information

$\displaystyle d=I(f;l_{i};l_{j})\approx\min\left\{\frac{I(l_{i};l_{j})I(l_{i};% f)}{H(l_{i})},\frac{I(l_{i};l_{j})I(l_{j};f)}{H(l_{j})}\right\}$ (29)

In the calculation of the interaction information, the label $l_{i}$ will be ignored when $H(l_{i})=0$ because that $l_{i}$ carries no information.

Our goal is to measure the correlation between features and labels. The correlation between two labels and features is known as the regions $a+d+b$ . The corresponding interaction information is the intersecting part of the feature and the labels in the Venn diagram, that is region $d$ . The intersecting part will be repeatedly calculated when traverse the redundancy of all labels and features. If the value of region $d$ is positive, i.e. the value of interaction information is positive, one more calculation will lead to the introduction of redundancy in the measurement. If the value of region $d$ is negative at this time, that is, the value of interaction information is negative, the more calculation will miss the synergy between the feature and labels. Therefore, we need to subtract the interactive information items to achieve the purpose of correction. Extending to the correlation between the entire set of labels and features, we can get

$\displaystyle\textit{Rel}(f)=\sum_{l\in L}{I(f;l)}-\frac{1}{2}\sum_{l_{i}\in L% }{\sum_{l_{j}\in L,i\neq j}{I(f;l_{i};l_{j})}}$ (30)

where $I(f;l_{i};l_{j})$ is calculated according to Eq. (29), coefficient $\frac{1}{2}$ is used to prevent redundant items from repeating statistics.

Next, we consider the redundancy between the selected features. The traditional measure of redundancy between features does not consider the influence of the selected features. For the sake of analysis, the analysis is based on the information Venn diagram in Fig. 3.

The traditional form of the redundancy measure is that $\sum_{f_{i}\in S}{I(f;f_{i})}$ approximates $I(f;S)$ [8, 10, 16], i.e. $\textit{Red}(f)=I(f;S)\approx\sum_{f_{i}\in S}{I(f;f_{i})}$ . Assume that the only two selected features are $f_{k}$ and $f_{j}$ , based on the traditional method we can get $\textit{Red}(f)=I(f;S)\approx\sum_{f_{i}\in S}{I(f;f_{i})}=a+d+d+b$ . As shown in Fig. 3, the actual value is $\textit{Red}(f)=I(f;S)=a+d+b$ . Obviously, this result is not precise because that the region $d$ is repetitively counting. Therefore, when we measure redundancy, we only need to measure region $d$ , i.e., interaction information $I(f;f_{k};f_{j})$ . Since the calculation of $I(f;f_{k};f_{j})$ involves the estimation of 3-dimensional entropy, in order to reduce the computational cost, we will do the same operation as Eq. (29), i.e.

$\displaystyle I(f;f_{k};f_{j})\approx\min\left\{\frac{I(f_{k};f_{j})I(f_{k};f)% }{H(f_{k})},\frac{I(f_{k};f_{j})I(f_{j};f)}{H(f_{j})}\right\}$ (31)

Similar to Eq. (30), we will approximate it as follows.

$\displaystyle\textit{Red}(f)=I(f;S)\approx\sum_{f_{i}\in S}{I(f;f_{i})}-\frac{% 1}{2}\sum_{f_{k}\in S}{\sum_{f_{j}\in S,f_{k}\neq f_{j}}{I(f;f_{k};f_{j})}}$ (32)

where $S$ is the selected feature set. $I(f;f_{k};f_{j})$ is calculated according to Eq. (31).

Figure 3.

Venn diagram which is used to illustrate the relation between $f_{k}$ , $f_{j}$ and $f$ .

Therefore, the criterion of the feature selection under the framework of maximum correlation and minimum redundancy is

$\displaystyle J(f)=\textit{Rel}(f)-\textit{Red}(f)$ (33)

At the beginning of feature selection, the number of selected feature sets is relatively small and the number of elements in the label set remains unchanged. The measurement of the relevant part may only consider the measurement of the relevant part and ignore the measurement of the redundant part if the number of label elements is too large, which will render a large error [11]. Therefore, this paper simply gives the corresponding scale coefficient according to the number of feature sets and label sets, i.e.

$\displaystyle J(f)=\frac{1}{|L|}\textit{Rel}(f)-\frac{1}{|S|}\textit{Red}(f)$ (34)

where $\textit{Rel}(f)$ is calculated according to Eq. (30) and $\textit{Red}(f)$ is calculated according to Eq. (32).

The pseudo codes of the proposed algorithm can be described by Algorithm 1.

Algorithm 1: Proposed multi-label feature selection algorithm
Input: A training sample $D$ with a full feature set $F=\{f_{1},f_{2},\ldots,f_{d}\}$ and the label set $L=\{l_{1},l_{2},\ldots,l_{q}\}$ , The number of selected features $b$
Output: The already-selected feature subset $S$
1: $S=\text{{\O}}$
2: for $i=1:b$ do
3: if $i==1$ then
4: Select the feature $f_{j}$ with $\text{max}_{l_{h}\in L}I(f_{j};l_{h})$ ;
5: $i=i+1$ ;
6: $S=S\cup\{f_{j}\}$ ;
7: $F=F-\{f_{j}\}$ ;
8: else
9: for each candidate feature $f_{k}\in F$ do
10: Calculate the the Eq. (34) $J(f_{k})$ ;
11: end for
12: Select the feature $f_{k}$ with the largest $J(f_{k})$ ;
13: $i=i+1$
14: $S=S\cup\{f_{j}\}$ ;
15: $F=F-\{f_{j}\}$ ;
16: end if
17: end for
18: Output the set $S$ ;

4.3 Time complexity analysis

Since each filtering feature $f$ needs to traverse the whole $F$ , in order to prevent repeated calculation, we calculate $I(f;l)$ , $I(l_{i};l_{j})$ , $H(f)$ and $H(l)$ in advance, and the corresponding time complexity is $O(\textit{dqn})$ , $O(q^{2}n)$ , $O(dn)$ and $O(qn)$ , where $n$ is the number of training set samples, $d$ is the number of features, $b$ is the number of features to be selected and $q$ is the number of labels. The calculation of $\sum_{f_{i}\in S}{I(f;f_{i})}$ can avoid repetition. For example, Unselected feature set $F=\{f_{1},f_{2},f_{3}\}$ , selected feature set $S=\{f_{4}\}$ . In this case, $I(f_{1};f_{4})$ , $I(f_{2};f_{4})$ and $I(f_{3};f_{4})$ needs to be calculated. Suppose we choose the best feature $f_{3}$ in this round. $F$ and $S$ are updated accordingly. $F=\{f_{1},f_{2}\}$ , $S=\{f_{3},f_{4}\}$ . We only need to calculate $I(f_{1};f_{3})$ and $I(f_{2};f_{3})$ , because $I(f_{1};f_{4})$ and $I(f_{2};f_{4})$ have been calculated in the last round, so we only need to store them and call them directly. Generally, we only need to calculate $d-i+1$ mutual information when screening the $i$ -th feature. Calculation amount required for $b$ filters: $\sum_{i=1}^{b}{(d-i+1)}=bd+b-\frac{b(b-1)}{2}\leqslant bd$ , when $b\geqslant 3$ Generally, $b\ll d$ . Therefore, the time complexity required here is $O(\textit{bdn})$ . Follow the same strategy, The time complexity is $O(\textit{dqn}+q^{2}n+dn+qn+\textit{bdn}+bq+dq^{2}+db^{2})$ . Remove the lower order term, the final time complexity is $O(\textit{dqn}+q^{2}n+\textit{bdn}+dq^{2}+db^{2})$ . Similarly, time complexity of PMU is $O(\textit{bdqn}+dq^{2}n)$ . Time complexity of LRFS is $O(dq^{2}n+\textit{bdn})$ , and time complexity of MDMR is $O(\textit{bdqn})$ . The proposed algorithm transforms the fourth-order time complexity into third-order time complexity. Other algorithms involving interactive information or three-dimensional entropy have fourth-order time complexity, and usually, the number of samples in the dataset is much larger than the number of features and labels so the algorithm proposed in this paper has obvious advantages.

5. Experiments

In this part, we compare the performance of seven algorithms. These algorithms are PMU [12], MDMR [9], LRFS [16], AMI [8], MCMFS [10], SCLS [11], MLACO [7].

5.1 Evaluation criteria

Four multi-label classification evaluation criteria are used to evaluate the performance of the proposed method, i.e. Average Precision (AP), Ranking Loss (RL), Coverage (CV), and One-error(OE) [18].

Let $T=\{(x_{i},y_{i})\}_{i=1}^{m}$ be the test set, where $y_{i}=\{(0,1)\}^{t}$ is the label vector of the $i$ th sample, $y_{ij}$ represents the $j$ th element of the label vector of the $i$ th sample of the test set. $L=\{l_{1},l_{2},\ldots l_{t}\}$ , $t$ is the number of label sets.

AveragePrecision (AP): AP measures average value of a label order over a particular label. It is defined as follows.

$\displaystyle AP=\frac{1}{m}\sum_{i=1}^{m}{\frac{1}{\|y_{i}\|_{0}}}\sum_{j\in% \{q|y_{iq}=1\}}{\frac{|\mathcal{R}(x_{i},l_{j})|}{\textit{rank}(x_{i},l_{j})}}$ (35)

$\mathcal{R}(x_{i},l_{j})=\{y_{ik}\mid\textit{rank}(x_{i},l_{k})\leqslant% \textit{rank}(x_{i},l_{j}),y_{ik}=1\}$ , $|.|$ means an indication function, $\|.\|_{0}$ is $\ell_{0}$ -norm. $\textit{rank}(x_{i},l_{j})=|\{k|f_{ik}\geqslant f_{ij}\}|$ , where $f_{ij}$ is the probability of the algorithm’s prediction on the $j$ th label $l_{j}$ of sample $x_{i}$ , represents the descending ranking of sample $x_{i}$ on the prediction probability of label $l_{j}$ .

Coverage (CV): CV denotes the difference between the predicted rank label and the real rank label. It is defined as follows.

$\displaystyle CV=\frac{1}{t}\sum_{i=1}^{t}{\max_{j\in\{q|y_{iq}=1\}}}\textit{% rank}(x_{i},l_{j})-1$ (36)

Ranking Loss (RL): The RL measures that the classifier gives the proportion that the prediction probability of the corresponding ground truth corresponding to the positive case is less than that of the corresponding the negative case. The RL is defined as follows.

$\displaystyle RL=\frac{1}{m}\sum_{i=1}^{m}{\frac{1}{\|y_{i}\|_{0}(l-\|y_{i}\|_% {0})}|\{(p,q)|f_{ip}\leqslant f_{iq},y_{ip}=1,y_{iq}=0\}|}$ (37)

One Error (OE): This OE measures the proportion of the label with the highest predictive probability given by the classifier that is not the ground-truth label. It is defined as follows.

$\displaystyle OE=\frac{1}{m}\sum_{i=1}^{m}{\left|\left\{y_{ij}|\mathop{\text{% argmax}}\limits_{y_{ij}\in y_{i}}f_{ij}\neq 1\right\}\right|}$ (38)

Macro F1: Macro F1 measures recall and precision of integrated quality. It is defined as follows.

$\displaystyle\textit{Macro }F_{1}=\frac{1}{t}\sum_{i=1}^{t}{\frac{2p_{i}r_{i}}% {p_{i}+r_{i}}}$ (39)

Where $p_{i}$ is the precision for $i$ th label and $r_{i}$ is the recall for $i$ th label.

5.2 Experimental data and experimental Settings

To evaluate the classification performance of the proposed method, we compare it with other algorithms on six datasets. These data sets are download from Mulan Library [32]. The characteristics of the datasets are shown in Table 1.

The datasets Arts, Recreation, Social, Health, Computer are from Yahoo text datasets, which are widely used to text categorization. The Emotions dataset is from music domain.

Table 1
Description of data sets

NO.	Dataset	#Instances	#Features	#Labels	#Training	#Test
1	Arts	5000	462	26	2000	3000
2	Recreation	5000	606	22	2000	3000
3	Emotions	593	72	6	391	202
4	Social	5000	1047	39	2000	3000
5	Health	5000	612	32	2000	3000
6	Computer	5000	681	33	2000	3000

The multi-label classification algorithm MLKNN [19] is selected to be the multi-label classifier for evaluation. All continuous features are discretized into four bins according to equal-width strategy, as recommend in [12]. Additionally, the number of the nearest neighbors $k$ is set to 10, the number of selected features $b$ increases from 1 to 50 with a step size 1.

5.3 Analysis of experimental results

All methods are implemented using python on an Intel Core-i5 CPU with 16 GB of RAM in the Microsoft Windows 10 operating system.

In each table, bold characters represent the optimal experimental results under the data set. Each number in the table is the average result of 50 groups of feature subsets under the classifier, where the parentheses represent the standard deviation. The last row “Average” records the average results of all data sets. In each table, bold characters represent the optimal experimental results under the data set.

The classification results in Tables 4–6 show that our proposed algorithm is superior to the others. For example, for Macro F1 evaluation criteria, the analysis results of three data sets are optimum, our proposed average value is 0.1933 and higher than PMU, MDMR, LRFS, AMI, MCMFS, SCLS, MLACO corresponding evaluation criteria of 0.1263, 0.1867, 0.1827, 0.1827, 0.1870, 0.1825, 0.1612. Because the proposed algorithm considers the correlation between labels and is suitable in the description of correlation and redundancy, it is generally superior to other algorithms in the global performance.

From their average results corresponding to the Macro F1 evaluation criteria, other ranking algorithms for PMU, MDMR, LRFS, SCLS, MCMFS, AMI, MLACO. SCLS algorithm with a scalable coefficient between correlation and redundancy has good performance when choosing a small number of features. MLACO may not be able to describe the actual correlation well because the correlation and redundancy measures are linear, shown as in Table 4.

In order to show the classification performance more clearly, Figs 4 and 5 gives a more detailed description of 2 datasets. The X-axis indicates the number of selected features, and the Y-axis indicates the classification result of the different evaluation criteria. Different colored lines in the figure represent different algorithms.

For datasets health and computer, shown as in Figs 4 and 5. As more and more features are selected, the advantages of our algorithm become more and more obvious. For example, in Fig. 5, evaluation criteria Coverage Error, when the number of selected features is less than or equal to 10, the advantage of our algorithm is not obvious compared with other algorithms. When the number of selected features is more than 10, our algorithm is obviously better than other algorithms.

This is because that SCLS, MCMFS, AMI are not sophisticated enough to measure redundancy and relevance. Therefore, when a few features are selected at the beginning, the error between the redundant items and the relevance items of algorithm SCLS, MCMFS, AMI are not significantly enlarged. But as the number of features selected increases, the error of redundant items and relevance items will be larger and larger, the corresponding performance will get worse and worse. MDMR, LRFS both have considered the correlation of the pairwise labels, but the estimation of the redundant term is not precise enough and the two redundant items of PMU have overlapping parts, so the accumulated error of these algorithms when selecting features will become larger and larger.

Table 2
Experimental results of multi-label feature selection methods in terms of Average Precision (AP) (mean $\pm$ std)

Dataset	PMU	MDMR	LRFS	AMI	SCLS	MCMFS	MLACO	Proposed
Arts	0.4436 $\pm$ 0.0142	0.4889 $\pm$ 0.0118	0.4862 $\pm$ 0.0141	0.5029 $\pm$ 0.0157	0.5013 $\pm$ 0.0186	0.5057 $\pm$ 0.0162	0.4744 $\pm$ 0.0254	0.5046 $\pm$ 0.0178
Recreation	0.4254 $\pm$ 0.0124	0.4864 $\pm$ 0.0217	0.4968 $\pm$ 0.0211	0.5176 $\pm$ 0.0265	0.4883 $\pm$ 0.0226	0.5175 $\pm$ 0.0288	0.4556 $\pm$ 0.0499	0.5235 $\pm$ 0.0294
Emotions	0.6892 $\pm$ 0.0332	0.7286 $\pm$ 0.0109	0.7266 $\pm$ 0.0129	0.7019 $\pm$ 0.0060	0.7227 $\pm$ 0.0312	0.7124 $\pm$ 0.0106	0.7296 $\pm$ 0.0159	0.7378 $\pm$ 0.0156
Social	0.6707 $\pm$ 0.0062	0.6947 $\pm$ 0.0127	0.6947 $\pm$ 0.0102	0.7067 $\pm$ 0.0147	0.6966 $\pm$ 0.0124	0.7008 $\pm$ 0.0117	0.6364 $\pm$ 0.0182	0.7006 $\pm$ 0.0155
Health	0.6278 $\pm$ 0.0074	0.6941 $\pm$ 0.0192	0.6883 $\pm$ 0.0192	0.7062 $\pm$ 0.0213	0.7006 $\pm$ 0.0219	0.7074 $\pm$ 0.0223	0.6815 $\pm$ 0.0202	0.7111 $\pm$ 0.0205
Computer	0.5844 $\pm$ 0.0055	0.6028 $\pm$ 0.0077	0.5954 $\pm$ 0.0061	0.6150 $\pm$ 0.0095	0.6019 $\pm$ 0.0066	0.6092 $\pm$ 0.0060	0.6084 $\pm$ 0.0079	0.6214 $\pm$ 0.0130
Average	0.5735	0.6159	0.6147	0.6251	0.6186	0.6255	0.5977	0.6332

Table 3

Experimental results of multi-label feature selection methods in terms of Ranking Loss (RL) (mean $\pm$ std)

Dataset	PMU	MDMR	LRFS	AMI	SCLS	MCMFS	MLACO	Proposed
Arts	0.1892 $\pm$ 0.0075	0.1789 $\pm$ 0.0053	0.1800 $\pm$ 0.0050	0.1797 $\pm$ 0.0037	0.1763 $\pm$ 0.0052	0.1756 $\pm$ 0.0039	0.1861 $\pm$ 0.0092	0.1780 $\pm$ 0.0044
Recreation	0.2277 $\pm$ 0.0075	0.2116 $\pm$ 0.0087	0.2075 $\pm$ 0.0110	0.1945 $\pm$ 0.0046	0.2164 $\pm$ 0.0094	0.1987 $\pm$ 0.0051	0.2154 $\pm$ 0.0137	0.1919 $\pm$ 0.0051
Emotions	0.2954 $\pm$ 0.0415	0.2261 $\pm$ 0.0123	0.2297 $\pm$ 0.0167	0.2667 $\pm$ 0.0159	0.2482 $\pm$ 0.0383	0.2524 $\pm$ 0.0180	0.2300 $\pm$ 0.0178	0.2233 $\pm$ 0.0163
Social	0.0838 $\pm$ 0.0040	0.0811 $\pm$ 0.0045	0.0792 $\pm$ 0.0057	0.0785 $\pm$ 0.0043	0.0796 $\pm$ 0.0034	0.0823 $\pm$ 0.0031	0.0807 $\pm$ 0.0013	0.0752 $\pm$ 0.0029
Health	0.0783 $\pm$ 0.0028	0.0682 $\pm$ 0.0038	0.0685 $\pm$ 0.0042	0.0675 $\pm$ 0.0037	0.0678 $\pm$ 0.0045	0.0666 $\pm$ 0.0041	0.0708 $\pm$ 0.0045	0.0663 $\pm$ 0.0040
Computer	0.1169 $\pm$ 0.0059	0.1106 $\pm$ 0.0040	0.1129 $\pm$ 0.0055	0.1117 $\pm$ 0.0026	0.1113 $\pm$ 0.0057	0.1078 $\pm$ 0.0022	0.1083 $\pm$ 0.0027	0.1053 $\pm$ 0.0030
Average	0.1652	0.1461	0.1463	0.1498	0.1499	0.1472	0.1486	0.1400

Table 4

Experimental results of multi-label feature selection methods in terms of Coverage (CV) (mean $\pm$ std)

Dataset	PMU	MDMR	LRFS	AMI	SCLS	MCMFS	MLACO	Proposed
Arts	6.4995 $\pm$ 0.2233	6.2954 $\pm$ 0.1950	6.3024 $\pm$ 0.1604	6.3611 $\pm$ 0.1325	6.2391 $\pm$ 0.1351	6.2614 $\pm$ 0.1544	6.5065 $\pm$ 0.2323	6.3495 $\pm$ 0.1627
Recreation	5.8795 $\pm$ 0.1940	5.5906 $\pm$ 0.2088	5.5300 $\pm$ 0.2777	5.2397 $\pm$ 0.1044	5.7212 $\pm$ 0.2314	5.3822 $\pm$ 0.1553	5.6033 $\pm$ 0.2722	5.2026 $\pm$ 0.1041
Emotions	2.5261 $\pm$ 0.1714	2.1914 $\pm$ 0.0634	2.1808 $\pm$ 0.0862	2.3828 $\pm$ 0.0838	2.2896 $\pm$ 0.1937	2.2938 $\pm$ 0.0924	2.1848 $\pm$ 0.0869	2.1662 $\pm$ 0.0910
Social	4.2642 $\pm$ 0.1986	4.2082 $\pm$ 0.2138	4.1345 $\pm$ 0.2876	4.1138 $\pm$ 0.2119	4.1294 $\pm$ 0.1810	4.2478 $\pm$ 0.1696	4.1312 $\pm$ 0.0561	3.9279 $\pm$ 0.1424
Health	3.9682 $\pm$ 0.1152	3.6269 $\pm$ 0.1529	3.6359 $\pm$ 0.1826	3.6182 $\pm$ 0.1576	3.6060 $\pm$ 0.1938	3.5673 $\pm$ 0.1681	3.7338 $\pm$ 0.1549	3.5779 $\pm$ 0.1604
Computer	5.3734 $\pm$ 0.2625	5.1686 $\pm$ 0.1491	5.2451 $\pm$ 0.2493	5.2115 $\pm$ 0.1041	5.1707 $\pm$ 0.2426	5.0111 $\pm$ 0.1059	5.0662 $\pm$ 0.1197	4.9074 $\pm$ 0.1294
Average	4.7518	4.5135	4.5048	4.4879	4.5260	4.4606	4.5376	4.3553

Table 5

Experimental results of multi-label feature selection methods in terms of One-error (OE) (mean $\pm$ std)

Dataset	PMU	MDMR	LRFS	AMI	SCLS	MCMFS	MLACO	Proposed
Arts	0.6981 $\pm$ 0.0297	0.6387 $\pm$ 0.0277	0.6391 $\pm$ 0.0328	0.6185 $\pm$ 0.0314	0.6218 $\pm$ 0.0352	0.6122 $\pm$ 0.0356	0.6566 $\pm$ 0.0435	0.6144 $\pm$ 0.0360
Recreation	0.7214 $\pm$ 0.0228	0.6377 $\pm$ 0.0363	0.6242 $\pm$ 0.0338	0.6014 $\pm$ 0.0400	0.6318 $\pm$ 0.0394	0.6001 $\pm$ 0.0458	0.6840 $\pm$ 0.0693	0.5944 $\pm$ 0.0443
Emotions	0.4314 $\pm$ 0.0572	0.4022 $\pm$ 0.0158	0.4077 $\pm$ 0.0193	0.4274 $\pm$ 0.0117	0.3947 $\pm$ 0.0383	0.4228 $\pm$ 0.0145	0.3982 $\pm$ 0.0290	0.3786 $\pm$ 0.0215
Social	0.4123 $\pm$ 0.0119	0.3793 $\pm$ 0.0200	0.3810 $\pm$ 0.0159	0.3590 $\pm$ 0.0242	0.3764 $\pm$ 0.0194	0.3649 $\pm$ 0.0203	0.4891 $\pm$ 0.0364	0.3735 $\pm$ 0.0266
Health	0.4780 $\pm$ 0.0120	0.3746 $\pm$ 0.0273	0.3849 $\pm$ 0.0257	0.3542 $\pm$ 0.0295	0.3650 $\pm$ 0.0306	0.3556 $\pm$ 0.0322	0.3951 $\pm$ 0.0251	0.3499 $\pm$ 0.0271
Computer	0.4881 $\pm$ 0.0068	0.4744 $\pm$ 0.0059	0.4839 $\pm$ 0.0067	0.4528 $\pm$ 0.0157	0.4750 $\pm$ 0.0057	0.4709 $\pm$ 0.0076	0.4670 $\pm$ 0.0101	0.4484 $\pm$ 0.0184
Average	0.5382	0.4845	0.4868	0.4689	0.4775	0.4711	0.5150	0.4599

Table 6

Experimental results of multi-label feature selection methods in terms of Macro F1 (mean $\pm$ std)

Dataset	PMU	MDMR	LRFS	AMI	SCLS	MCMFS	MLACO	Proposed
Arts	0.0511 $\pm$ 0.0197	0.1020 $\pm$ 0.0326	0.0950 $\pm$ 0.0264	0.1072 $\pm$ 0.0273	0.1109 $\pm$ 0.0361	0.0998 $\pm$ 0.0266	0.0773 $\pm$ 0.0360	0.1073 $\pm$ 0.0286
Recreation	0.0765 $\pm$ 0.0244	0.1293 $\pm$ 0.0306	0.1425 $\pm$ 0.0306	0.1447 $\pm$ 0.0298	0.1334 $\pm$ 0.0325	0.1546 $\pm$ 0.0384	0.0901 $\pm$ 0.0509	0.1478 $\pm$ 0.0317
Emotions	0.3985 $\pm$ 0.0700	0.5160 $\pm$ 0.0406	0.5037 $\pm$ 0.0271	0.4613 $\pm$ 0.0368	0.5034 $\pm$ 0.0744	0.4664 $\pm$ 0.0258	0.5031 $\pm$ 0.0417	0.5118 $\pm$ 0.0468
Social	0.0655 $\pm$ 0.0094	0.0997 $\pm$ 0.0220	0.0939 $\pm$ 0.0239	0.0999 $\pm$ 0.0247	0.1014 $\pm$ 0.0219	0.0981 $\pm$ 0.0279	0.0536 $\pm$ 0.0237	0.1060 $\pm$ 0.0239
Health	0.1129 $\pm$ 0.0140	0.1719 $\pm$ 0.0297	0.1738 $\pm$ 0.0325	0.1832 $\pm$ 0.0350	0.1722 $\pm$ 0.0296	0.1803 $\pm$ 0.0328	0.1532 $\pm$ 0.0377	0.1840 $\pm$ 0.0356
Computer	0.0534 $\pm$ 0.0204	0.1011 $\pm$ 0.0415	0.0873 $\pm$ 0.0309	0.1001 $\pm$ 0.0330	0.1008 $\pm$ 0.0413	0.0957 $\pm$ 0.0325	0.0900 $\pm$ 0.0285	0.1033 $\pm$ 0.0361
Average	0.1263	0.1867	0.1827	0.1827	0.1870	0.1825	0.1612	0.1933

Figure 4.

The classification performance on Health data set: (a): Average Precision, (b): Ranking Loss, (c): Coverage Error, (d): One-Error, (e): Macro F1.

Figure 5.

The classification performance on Computer data set: (a): Average Precision, (b): Ranking Loss, (c): Coverage Error, (d): One-Error, (e): Macro F1.

6. Conclusions

In this paper, a multi-label feature selection algorithm based on proportional second-order relevance and redundancy is proposed, which takes the correlation between labels into account, and adjusts the variable scaling coefficient of correlation and redundancy so as to describe the correlation between features and label sets better.

In order to prove the validity of the proposed algorithm in this paper, the seven other multi label based on correlation and redundancy measure feature selection algorithms (PMU, MDMR, LRFS, AMI, MCMFS SCLS, MLACO) are compared. In the 6 well-known multi-label datasets, five evaluation criteria (Average Precision, Ranking Loss, Coverage, One-error, Macro F1) were compared using the same multi-label feature selection classifier MLKNN. The final experimental results show that the proposed algorithm has obvious advantages.

In our future work, we are going to study higher-order correlation and redundancy, not just at second order. We are also talking about improving the way of search, rather than the traditional forward incremental search.

Footnotes

Acknowledgments

This paper was partially supported by National Defense Basic Research Program (JCKY2019413D001), Medical Engineering Cross Project of USST (10-21-302-413) and (10-202-302-424).

References

Kashef

Nezamabadi-pour

and Nikpour

, Multilabel feature selection: A comprehensive review and guiding experiments, Wiley Interdisciplinary Reviews-Data Mining and Knowledge Discovery 8(2) (2018), 1–29.

Lewis

D.D.

Yang

Rose

T.G.

and Li

, RCV1: A new benchmark collection for text categorization research, Journal of Machine Learning Research 5 (2004), 361–397.

Boutell

M.R.

Luo

Shen

and Brown

C.M.

, Learning multi-label scene classification, Pattern Recognition 37(9) (2004), 1757–1771.

Elisseeff

and Weston

, A kernel method for multi-labelled classification, in: International Conference on Neural Information Processing Systems: Naturaland Synthetic, 2002, pp. 681–687.

Turnbull

Barrington

Torres

and Lanckriet

, Semantic annotation and retrieval of music and sound effects, IEEE Transactions on Audio, Speech and Language Processing 16(2) (2008), 467–476.

Spolaôr

Monard

M.C.

Tsoumakas

and Lee

H.D.

, A systematic review of multi-label feature selection and a new method based on label construction, Neurocomputing 180(C) (2016), 3–15.

Paniri

Dowlatshahi

M.B.

and Nezamabadi-pour

, MLACO: A multi-label feature selection algorithm based on ant colony optimization, Knowledge-Based Systems 192 (2020), 105285.

Lee

Lim

and Kim

D.W.

, Approximating mutual information for multi-label feature selection, Electronics Letters 48(15) (2012), 929–930.

Lin

Liu

and Duan

, Multi-label feature selection based on max-dependency and min-redundancy, Neurocomputing 168 (2015), 92–103.

10.

Zhang

Gao

and Li

, Multi-label feature selection based on high-order label correlation assumption, Entropy 22(7) (2020), 1–24.

11.

Lee

and Kim

D.W.

, SCLS: Multi-label feature selection based on scalable criterion for large label set, Pattern Recognition 66 (2017), 342–352.

12.

Lee

and Kim

D.W.

, Feature selection for multi-label classification using multivariate mutual information, Pattern Recognition Letters 34(3) (2013), 349–357.

13.

Lee

and Kim

D.W.

, Mutual Information-based multi-label feature selection using interaction information, Expert Systems with Applications 42(4) (2015), 2013–2025.

14.

Reyes

Morell

and Ventura

, Scalable extensions of the ReliefF algorithm for weighting and selecting features on the multi-label learning context, Neurocomputing 161 (2015), 168–182.

15.

Kashef

Nezamabadi-pour

and Nikpour

, FCBF3Rules: A Feature Selection Method for Multi-Label Datasets, in: 2018 3rd Conference on Swarm Intelligence and Evolutionary Computation (CSIEC), 2018, pp. 1–5.

16.

Zhang

Liu

and Gao

, Distinguishing two types of labels for multi-label feature selection, Pattern Recognition 95 (2019), 72–82.

17.

Shannon

C.E.

, A mathematical theory of communication, Bell System Technical Journal 27(4) (1948), 623–656.

18.

Zhang

M.L.

and Zhou

Z.H.

, A review on multi-label learning algorithms, IEEE Transactions on Knowledge and Data Engineering 26(8) (2014), 1819–1837.

19.

Zhang

M.L.

and Zhou

Z.H.

, ML-KNN: A lazy learning approach to multi-label learning, Pattern Recognition 40(7) (2007), 2038–2048.

20.

Wang

L.L.

Wang

and Zhang

, Learning instance correlation functions for multilabel classification, IEEE Transactions on Cybernetics 1(2) (2018), 424–439.

21.

Read

Pfahringer

Holmes

and Frank

, Classifier chains for multi-label classification, in: Proceedings of The European Conference on Machine Learning, 2009, pp. 254–269.

22.

Read

Pfahringer

and Holmes

, Multi-label classification using ensembles of pruned sets, in: Proceedings of IEEE International Conference on Data Mining, 2008, pp. 995–1000.

23.

Zhang

M.L.

Peña

J.M.

and Robles

, Feature selection for multi-label naive Bayes classification, Information Sciences 179(19) (2009), 3218–3229.

24.

Zhang

and Wu

, LIFT: Multi-label learning with label-specific features, IEEE Transactions on Pattern Analysis and Machine Intelligence 37(1) (2015), 107–120.

25.

Nie

Yang

Uijlings

J.R.R.

and Sebe

, Web image annotation via subspace-sparsity collaborated feature selection, IEEE Transactions on Multimedia 14(4) (2012), 1021–1030.

26.

Jian

Shu

and Liu

, Multi-label informed feature selection, in: IJCAI International Joint Conference on Artificial Intelligence, 2016, pp. 1627–1633.

27.

Huang

and Wu

, Joint feature selection and classification for multilabel learning, IEEE Transactions on Cybernetics 48(3) (2018), 876–889.

28.

Chung

F.R.K.

Graham

R.L.

Frankl

and Shearer

J.B.

, Some intersection theorems for ordered sets and graphs, Journal of Combinatorial Theory, Series A 43(1) (1986), 23–37.

29.

Hanchuan Peng

C.D.

and Long

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

30.

Seo

Kim

D.W.

and Lee

, Generalized information-theoretic criterion for multi-label feature selection, IEEE Access 7 (2019), 122854–122863.

31.

Kwak

and Choi

C.H.

, Input feature selection for classification problems, IEEE Transactions on Neural Networks 13(1) (2002), 143–159.

32.

Tsoumakas

Spyromitros-Xioufis

Vilcek

and Vlahavas

, MULAN: A Java library for multi-label learning, Journal of Machine Learning Research 12 (2011), 2411–2414.

A multi-label feature selection method based on an approximation of interaction information

Abstract

Keywords

1. Introduction

3.1 Multi label classification

3.2 Multi-label feature selection

4.1 Proportion-based interaction information estimation

5. Experiments

5.1 Evaluation criteria

Table 1 Description of data sets

Table 2 Experimental results of multi-label feature selection methods in terms of Average Precision (AP) (mean ± std)

Footnotes

Acknowledgments

References

Table 1
Description of data sets

Table 2
Experimental results of multi-label feature selection methods in terms of Average Precision (AP) (mean $\pm$ std)