Towards Class-Imbalance Aware Multi-Label Learning

1 Introduction

Under the multi-label learning setting, each example is represented by a single instance (feature vector) while associated with multiple class labels simultaneously [Tsoumakas et al., 2010; Zhang and Zhou, 2014]. Formally speaking, let X = Rd denote the input space of d-dimensional feature vectors and Y = {y1, y2, . . . , yq} denote the output space of q class labels. Given the multi-label training set D = {(xi, Yi) | 1 ≤ i ≤ N}, where xi ∈ X is a d-dimensional feature vector and Yi ⊆ Y is the set of labels associated with xi, the task is to learn a multi-label classifier h : X → 2Y from D which maps from the space of feature vectors to the space of label sets.

The key challenge to learn frommulti-label data lies in the huge number of possible label sets for prediction, which is exponential to the size of label space (i.e. 2q ). To take on this challenge, existing approaches mainly focus on exploiting correlations among class labels to facilitate the learning process [Tsoumakas et al., 2010; Zhang and Zhou, 2014]. Based on the order of correlations being considered, existing approaches can be roughly grouped into three categories, i.e. first-order approaches which assume independence among class labels, second-order approaches which consider correlations between a pair of class labels, and high-order approaches which consider correlations among all the class labels or subsets of class labels.

On the other hand, an inherent property of learning from multi-label data, i.e. the class-imbalance among labels, has not been fully taken into consideration by most existing approaches. For each class label yj ∈ Y, let D+ j = {(xi,+1) | yj ∈ Yi, 1 ≤ i ≤ N} and Dj = {(xi,-1) | yj /∈ Yi, 1 ≤ i ≤ N} denote the positive and negative training examples w.r.t. yj. Generally, the corresponding imbalance ratio ImRj = max(|D+ j |, |Dj |)/min(|D+ j |, |Dj |) would be high. 1 For instance, among the thirteen benchmark multilabel data sets used in this paper (Table 2), the average imbalance ratio across the label space (i.e. 1q ∑qj=1 ImRj ) ranges from 2.1 to 17.9 (with nine of them greater than 5.0), and the maximum imbalance ratio across the label space (i.e. max1≤j≤q ImRj) ranges from 3.0 to 50.0 (with eleven of them greater than 10.0).

Class-imbalance has long been regarded as one fundamental threat to compromise the performance of standard machine learning algorithms, which would also lead to performance degradation for most multi-label learning approaches [He and Garcia, 2009; Zhang and Zhou, 2014]. Therefore, a favorable practice towards designing multi-label learning algorithm should cautiously leverage the exploitation of label correlations as well as the exploration of class-imbalance. In this paper, a novel class-imbalance aware algorithm named COCOA, i.e. CrOss-COupling Aggregation, is proposed to learning from multi-label data. For each class label, COCOA builds one binary-class imbalance learner corresponding to the current label and also several multi-class imbalance learners coupling with other labels. After that, the final prediction on each class label is obtained by aggregating the outputs yielded by the binary learner and the multi-class learners. Comparative studies across thirteen publicly-available multi-label data sets show that COCOA achieves highly competitive performance, especially in terms of appropriate evaluation metrics under class-imbalance scenario.

1 In most cases, |D+ j | < |Dj | holds.

The rest of this paper is organized as follows. Section 2 presents technical details of the proposed COCOA approach. Section 3 discusses existing works related to COCOA. Section 4 reports the experimental results of comparative studies. Finally, Section 5 concludes.

2 The COCOA Approach

As shown in Section 1, the task of multi-label learning is to induce a multi-label classifier h : X → 2Y from the training set D = {(xi, Yi) | 1 ≤ i ≤ N}. This is equivalent to learn q real-valued functions fj : X → R (1 ≤ j ≤ q), each accompanied by a thresholding function tj : X → R. For any example x ∈ X, fj(x) returns the confidence of associating x with class label yj , and the predicted label set is determined according to:

Let Dj denote the binary training set derived from D for the j-th class label yj:

Therefore, the derived binary training set consists of a subset of positive training examples (D+ j ) and a subset of negative training examples (Dj ), i.e. Dj = D+ j ⋃ Dj . To deal with the issue of having skewed distribution between D+ j and Dj , one straightforward solution is to apply some binaryclass imbalance learner B on Dj to induce a binary classifier gj, i.e. gj ← B(Dj). Let gj(+1 | x) denote the predictive confidence that x should be regarded as a positive example for yj, the real-valued function fj(·) can then be instantiated as fj(x) = gj(+1 | x). In addition, the thresholding function tj(·) can be simply set to some constant function such as tj (x) = 0.

In the above class-imbalance handling strategy, the predictive model fj(·) for each class label yj is built in an independent manner. To incorporate label correlations into the learning process, we choose to randomly couple another class label yk (k ̸= j) with yj as follows. Given the label pair (yj, yk), a multi-class training set Djk can be derived from D:

Table 1: The pseudo-code of COCOA.

Inputs:

• D: the multi-label training set {(xi, Yi) | 1 ≤ i ≤ N} (xi ∈ X , Yi ⊆ Y, X = Rd , Y = {y1, y2, . . . , yq})
• B: the binary-class imbalance learner
• M: the multi-class imbalance learner
• K: the number of coupling class labels
• x: the test example (x ∈ X)

Outputs:

• Y : the predicted label set for x

Process:

• 1: for j = 1 to q do
• 2: Form the binary training set Dj according to Eq.(2);
• 3: gj ←B(Dj);
• 4: Draw a random subset IK ⊂ Y \ {yj} containing K class labels;
• 5: for yk ∈ IK do
• 6: Form the tri-class training set Dtri jk according to Eq.(4);
• 7: gjk ← M(Dtri jk );
• 8: end for
• 9: Set the real-valued function fj(·) according to Eq.(5);
• 10: Set the constant thresholding function tj(·), with the constant aj being determined according to Eq.(6);
• 11: end for
• 12: Return Y = h(x) according to Eq.(1);

Here, the class label ψ(Yi, yj, yk) for the derived four-class learning problem is determined by the joint assignment of yj and yk w.r.t. Yi.

Note that although label correlations can be exploited by making use of Djk in the learning process, the issue of classimbalance may be amplified by jointly considering yj and yk. Without loss of generality, suppose that positive examples D+ j (D+ k ) correspond to the minority class in the binary training set Dj (Dk). Accordingly, the first class (ψ(Yi, yk, yk) = 0) and the fourth class (ψ(Yi, yk, yk) = +3) in Djk would contain the largest and the smallest number of examples. Compared to the original imbalance ratios ImRj and ImRk in binary training sets Dj and Dk, the imbalance ratio between the largest class and the smallest class would roughly turn into ImRj ·ImRk in four-class training set Djk. To deal with this potential problem, COCOA transforms the four-class data set Djk into a tri-class data set Dtri jk by merging the third class and the fourth class (both with positive assignment for yj):

Here, for the newly-merged class (ψtri (Yi, yj, yk) = +2), its imbalance ratios w.r.t. the first class (ψtri (Yi, yj, yk) = 0) and the second class (ψtri (Yi, yj, yk) = +1) would roughly be ImRj·ImRk 1+ImRk and ImRj 1+ImRk , which is much smaller than the worst-case imbalance ratio ImRj · ImRk in the four-class training set.

By applying some multi-class imbalance learner M on Dtri jk , one multi-class classifier gjk can be induced, i.e. gjk ← M(Dtri jk ). Correspondingly, let gjk(+2 | x) denote the predictive confidence that x should have positive assignment w.r.t. yj, regardless of x having positive or negative assignment w.r.t. yk. For each class label yj, COCOA draws a random subset of K class labels IK ⊂ Y \ {yj} for pairwise coupling. The real-valued function fj(·) is then instantiated by aggregating the predictive confidences of one binary-class imbalance learner and K multi-class imbalance learners:

For the thresholding function tj(·), COCOA chooses to set it as a constant function tj(x) = aj. By accompanying the constant aj with fj, any example x is predicted to be positive for yj if fj(x) > aj, and negative otherwise. Specifically, the "goodness" of aj is evaluated based on certain metric which measures how well fj can classify examples in Dj by using aj as the bipartition threshold. In this paper, we employ the F-measure metric (i.e. harmonic mean of precision and recall) which is popular for evaluating the performance of binary classifier, especially for the case of skewed class distribution. Let F(fj, a,Dj) denote the F-measure value achieved by applying {fj , a} over the binary training set Dj , the thresholding constant aj is determined by maximizing the corresponding F-measure:

Table 1 summarizes the complete procedure of the proposed COCOA approach. For each class label yj ∈ Y, one binary-class imbalance learner (Steps 2-3) and K coupling multi-class imbalance learners (Steps 4-8) are induced by manipulating the multi-label training set D. After that, the predictive model for yj is produced by aggregating the predictive confidences of the induced binary and multi-class classifiers (Steps 9-10). Finally, the predicted label set for the test example is obtained by querying the predictive models of all class labels (Step 12).

It is worth noting that although pairwise coupling (Step 6) only considers second-order correlations among labels, the overall label correlations exploited by COCOA are actually high-order as controlled by the parameter K. Here, COCOA fulfills high-order label correlations by imposing pairwise coupling for K times instead of combining all K coupling labels simultaneously, as the latter strategy may lead to severe class-imbalance due to the combinatorial effects.

3 RelatedWork

In this section, we briefly discuss existing works related to COCOA. More comprehensive reviews on multi-label learning can be found in survey literatures such as [Tsoumakas et al., 2010; Zhang and Zhou, 2014; Gibaja and Ventura, 2015].

As mentioned in Section 2, one intuitive solution towards class-imbalance multi-label learning is to firstly decompose the multi-label learning problem into q independent binary learning problems, one per class label (a.k.a. binary relevance). And then, for each decomposed binary learning problem, the skewness between the positive and negative training examples can be dealt with via popular binary imbalance learning techniques such as random or synthetic undersampling/oversampling [Spyromitros-Xioufis et al., 2011; Tahir et al., 2012]. However, useful information regarding label correlations will be ignored in this decomposition process.

Different from binary decomposition, one can also transform the multi-label learning problem into a multi-class problem by treating any distinct label combinations appearing in the training set as a new class (a.k.a. label powerset). After that, the skewness among the transformed classes can be dealt with via off-the-shelf multi-class imbalance learning techniques [Wang and Yao, 2012; Liu et al., 2013]. Although label correlations can be exploited in this transformation process, the number of transformed classes (upper-bounded by min(N, 2q )) may be too large for any multi-class learner to work well.

Besides applying class-imbalance learning techniques to the transformed binary or multi-class problems, one can also make the multi-label learning algorithm be aware of the class-imbalance issue via parameter tuning. For COCOA, the thresholding constant is calibrated by maximizing imbalance-specific metric such as F-measure based on the training set, which could also be calibrated based on some held-out validation set [Fan and Lin, 2007] or be optimized with an extra learning procedure [Quevedo et al., 2012; Pillai et al., 2013]. Furthermore, instead of only tuning the thresholding parameter, another sophisticated choice is to design multi-label learning algorithms directly optimizing the macro-averaging F-measure [Dembczy´nski et al., 2013; Petterson and Caetano, 2010].

In view of the randomness in pairwise coupling, COCOA makes use of ensemble learning to aggregate the predictions of K randomly-generated imbalance learners. There have been multi-label learning methods which also utilize ensemble learning to deal with their inherent random factors, such as ensembling chaining classifier with random order [Read et al., 2011] or ensembling multi-class learner derived from random k-labelsets [Tsoumakas et al., 2011a]. Furthermore, ensemble learning can be employed as a meta-strategy to improve generalization with homogeneous [Shi et al., 2011] or heterogeneous [Tahir et al., 2010] component multi-label learners.

4 Experiments

4.1 Experimental Setup

Data Sets

To serve as a solid basis for performance evaluation, a total of thirteen benchmark multi-label data sets have been collected for experimental studies. For each multi-label data set S, we use |S|, L(S), dim(S) and F(S) to represent its number of examples, number of class labels, number of features and feature type respectively. In addition, several multi-label statistics are further used to characterize properties of S, whose definitions can be found in [Read et al., 2011] while not detailed here due to page limit.

Let ImRj denote the imbalance ratio on the j-th class label (1 ≤ j ≤ q), the level of class-imbalance on S can be characterized by the average imbalance ratio ( 1q ∑qj=1 ImRj ), minimum imbalance ratio (min1≤j≤q ImRj ) and maximum imbalance ratio (max1≤j≤q ImRj) across the label space. As a common practice in class-imbalance studies [He and Garcia, 2009], extreme imbalance is not considered in this paper. Specifically, any class label with rare appearance (less than 20 positive examples) or with overly-high imbalance ratio (ImRj ≥ 50) is excluded from the label space.

Table 2 summarizes characteristics of the experimental data sets, which are roughly ordered according to |S|. As shown in Table 2, the thirteen data sets exhibit diversified properties from different aspects. These data sets cover a broad range of scenarios, including music (CAL500, Emotions), image (Scene, Corel5k), video (Mediamill), biology (Yeast), and text (the others). Here, dimensionality reduction is performed on text data sets by retaining features with high document frequency.

Comparing Algorithms

In this paper, COCOA is compared against two series of algorithms. As discussed in Section 3, the first series include several approaches which are capable of dealing with the classimbalance issue in multi-label data:

• Undersampling (USAM): The multi-label learning problem is decomposed into q binary learning problems, and the majority class in each binary problem is randomly undersampled to form the new binary training set.
• SMOTE: The multi-label learning problem is decomposed into q binary learning problems, and the minority class in each binary problem is oversampled via the SMOTE method [Chawla et al., 2002] to form the new binary training set.

Considering that COCOA utilizes ensemble learning in its learning process, an ensemble version of USAM and SMOTE are also employed for comparison (named as USAM-EN and SMOTE-EN).

• RML: Besides integrating binary decomposition with undersampling/oversampling, another way to handle class-imbalance is to design learning system which can directly optimize imbalance-specific metric. Here, the RML approach [Petterson and Caetano, 2010] is employed as another comparing algorithm, which maximizes macro-averaging F-measure on multi-label data via convex relaxation.

In addition to the above algorithms, the second series include several well-established multi-label learning algorithms [Zhang and Zhou, 2014], including first-order approach MLKNN [Zhang and Zhou, 2007], second-order approach CLR [F¨urnkranz et al., 2008], and high-order approaches ECC [Read et al., 2011] and RAKEL [Tsoumakas et al., 2011a].

In this paper, all the comparing algorithms are instantiated as follows: 1) For USAM, SMOTE and their ensemble versions, decision tree is used as the base learner due to its popularity in class-imbalance studies [He and Garcia, 2009]. Specifically, these algorithms adopt implementations provided by the widely-used Weka platform with J48 decision tree (C4.5 implementation in Weka) as their base learner [Hall et al., 2009]; 2) For RML, the original implementation provided in the literature is used; 3) For the second series of algorithms (ML-KNN, CLR, ECC and RAKEL), we adopt their canonical implementations provided by the MULAN multi-label learning library (upon Weka platform) with suggested parameter configurations [Tsoumakas et al., 2011b]; 4) For COCOA, both the binary-class and multi-class imbalance learners (B and M) are implemented in Weka using J48 decision tree with undersampling [Hall et al., 2009]. Furthermore, the number of coupling class labels is set as K = min(q - 1, 10). For fair comparison, the ensemble size for USAM-EN and SMOTE-EN is also set to be 10.

4.2 Experimental Results

Under class-imbalance scenarios, F-measure and Area Under the ROC Curve (AUC) are the mostly-used evaluation metrics which can provide more insights on the classification performance than conventional metrics such as accuracy [He and Garcia, 2009]. In this paper, the multi-label classification performance is accordingly evaluated by macroaveraging the metric values across all class labels [Zhang and Zhou, 2014]. For either macro-averaging metric, the higher the metric value the better the performance.

Tables 3 and 4 give the detailed experimental results in terms of each evaluation metric respectively. Each data set is randomly split for training and testing, where 50% examples are chosen to form the training set and the remaining ones form the test set. The random train/test splits are repeated for ten times and the mean metric value as well as the standard deviation are recorded.

Furthermore, to show whether COCOA performs significantly better/worse than the comparing algorithm, pairwise t-test at 1% significance level is conducted. Accordingly, a win/loss is counted and a marker ·/◦ is shown in the table whenever COCOA achieves significantly superior/inferior performance on one data set. Otherwise, a tie is counted and no marker is given. The overall win/tie/loss counts across all data sets are summarized at the last column of each table.

In terms of MACRO-F (Table 3), COCOA significantly outperforms the comparing algorithms in 46.2% (RML), 76.9% (SMOTE, SMOTE-EN), 84.6% (USAM-EN), 92.3% (USAM, ML-KNN, ECC) and 100% (CLR, RAKEL) cases, and hasn't been outperformed by algorithms in the second series. These results indicate that COCOA is capable of achieving good balance between predictive exactness (precision) and completeness (recall) in handling class-imbalance multi-label learning.

In terms of MACRO-AUC (Table 4), COCOA significantly outperforms the comparing algorithms in 61.5% (CLR), 92.3% (ECC) and 100% (USAM, USAM-EN, SMOTE, SMOTE-EN, ML-KNN, RAKEL) cases, while has only been outperformed by CLR twice. These results indicate that the real-valued functions fj(·) (1 ≤ j ≤ q) learned by COCOA is capable of yielding reasonable predictive confidence, and better classification performance can be further expected if it is combined with more sophisticated thresholding strategy other than the constant function (Table 1, Step 10).

To further investigate how COCOA works under different levels of imbalance ratios, we roughly group the imbalance ratio ImRj into five intervals Ik (1 ≤ k ≤ 5) in ascending orders, i.e. I1 = [1, 5], I2 = [5, 10], I3 = [10, 15], I4 = [15, 25] and I5 = [25, 50]. Given one multi-label data set, let Ak denote the average performance of COCOA over class labels whose imbalance ratios fall into Ik, and Bk denote the average performance of another comparing algorithm over class labels in the same interval. Accordingly, the percentage of performance gain, i.e. PGk = [(Ak-Bk)/Bk]×100%, is computed to reflect the relative performance between COCOA and the comparing algorithm within the given interval.

Figure 1 illustrates how PGk changes as the imbalance level Ik moves from I1 to I5. Due to page limit, the performance is evaluated by choosing the F-measure metric ( 1 |Ik | ∑ImRj∈Ik Fj ) and two data sets Enron and Eurlex-sm are considered. For brevity, the relative performance against four comparing algorithms (USAM-EN, SMOTE-EN, ECC and RAKEL) has been depicted. Similar trends can be observed for other evaluation metrics and comparing algorithms.

As shown in Figure 1, COCOA maintains good relative performance against the comparing algorithms across different imbalance levels, where the curves hardly drop below the baseline (PGk = 0). Furthermore, it is interesting that the performance advantage of COCOA becomes more pronounced when the level of imbalance ratio is high (for I4 = [15, 25] and I5 = [25, 50]). These results indicate that COCOA can provide robust and preferable solutions in diverse class-imbalance scenarios.

5 Conclusion

In this paper, the class-imbalance issue in learning from multi-label data is studied. Accordingly, a novel classimbalance multi-label learning algorithm named COCOA is proposed, which works by leveraging the exploitation of label correlations and the exploration of class-imbalance. Specifically, one binary-class imbalance learner and several coupling multi-class imbalance learners are combined to yield the predictive model. Extensive experiments across thirteen benchmark data sets show that COCOA performs favorably against the comparing algorithms, especially in terms of imbalancespecific metrics such as MACRO-F and MACRO-AUC.

Acknowledgments

The authors wish to thank the anonymous reviewers for their insightful comments and suggestions. This work was supported by the National Science Foundation of China (61175049, 61222309, 61473087), the Natural Science Foundation of Jiangsu Province (BK20141340), and the MOE Program for New Century Excellent Talents in University (NCET-13-0130).