A Novel Data Representation for Effective Learning in Class Imbalanced Scenarios

1 Introduction

Class imbalance problem occurs when the number of samples in one class (majority class) greatly outnumbers the number of samples in the other class (minority class). Conventional classifiers such as artificial neural networks (ANNs), support vector machines (SVMs), etc., when trained on imbalanced data tend to get biased towards the majority class, ignoring the minority class [Wu and Chang, 2005]. This problem is often encountered in wide range of domains for example, computational biology and bio-informatics [Dubey et al., 2014], anomaly detection [Tavallaee et al., 2010], image annotation [Liu and Chen, 2005], etc, thus signifying the importance of solving this problem.

In literature, several approaches have been proposed to alleviate the effect of class imbalance problem. The most common approach is to use sampling-based methods, which involves either undersampling the majority class [Liu et al., 2009] or oversampling the minority class [Chawla et al., 2002] to obtain a balanced class distribution. These methods suffer from either the loss of useful information (undersampling) or the heavy dependency on the choice of samples to be duplicated (oversampling) which can lead to overfitting. Another approach is to use ensemble-based methods [Zhou, 2012; Galar et al., 2012], which use the sampling-based techniques more effectively by employing an ensemble of classifiers, whose outputs are combined (usually by voting or by fusion of classifier scores) to obtain the final decision. But, an efficient way to combine these ensemble of classifiers is still an open problem [Wu et al., 2017].

As an alternative to the sampling-based techniques, costsensitive learning based methods [Thai-Nghe et al., 2010] are developed. These methods use a different cost parameter for the errors associated with the minority and the majority class samples. But selecting an appropriate value of the cost parameter is critical for the performance of these methods.

In this work, we propose a novel approach to address the class imbalance problem in which two arbitrary samples are simultaneously considered from the training set to train the classifier. First, a modified representation of the training set is obtained by considering the feature-based representation of two arbitrary samples simultaneously. Then we select the architecture of the classifier (in this work, multilayer perceptron (MLP) is used as the base classifier) so as to handle the modified data representation format. Finally to test the classifier, we developed a mechanism of combining the test sample with a set of reference samples on which majority voting based decision is obtained using only a single base classifier. We refer to the proposed data representation as simultaneous two sample (s2s) representation, and our approach for addressing the class imbalance problem as simultaneous two sample learning (s2sL) [Dumpala et al., 2017]. The main contributions of this work are

• Novel data representation format to address the class imbalance problem.
• Selecting an appropriate MLP architecture to handle the proposed data representation.
• Mechanism to obtain the output label of the test sample using majority voting method by considering only a single base classifier.

2 RelatedWork

Previous approaches addressing the class imbalance problem can be classified into three broad categories [Wu et al., 2017] namely, (1) Sampling-based methods, (2) Ensemble-based methods and (3) Cost-sensitive learning based methods.

Sampling-based methods: Generic sampling-based techniques randomly either select a fraction of samples from the majority class (undersampling) [Liu et al., 2009] or oversample the minority class samples using synthetic minority oversampling technique (SMOTE) [Chawla et al., 2002]. Critical SMOTE (CSMOTE) [Nanni et al., 2015] and majority weighted minority oversampling technique (MWMOTE) [Barua et al., 2014] are the most recent advancements of SMOTE. CSMOTE generates synthetic samples by using only the border and edge samples of the minority class whereas MWMOTE uses weighted informative minority class samples to generate synthetic patterns. These methods require significant amount of undersampling or oversampling for higher levels of class imbalance.

Ensemble-based methods: These methods use boosting and bagging algorithms to address the class imbalance problem. Generally, these methods obtain enhanced performance by using sampling-based techniques (for preprocessing the data) prior to the boosting/bagging algorithms [Błaszczy´nski et al., 2010]. RUSBoost [Seiffert et al., 2010], EUSBoost [Galar et al., 2013] and more recently uncorrelated costsensitive multiset learning (UCML)[Wu et al., 2017] are ensemble-based methods using undersampling as a preprocessing step. UCML uses multiset feature learning (MFL) to address highly imbalanced class problem. Hard ensemble (HE) [Nanni et al., 2015] is also an ensemble-based method which uses ensemble of ensembles strategy in which both, undersampling and oversampling based methods are combined to address class imbalance.

Cost-sensitive learning based methods: Cost-sensitive multi-layer perceptron (CSMLP) method [Castro and Braga, 2013] is used to train MLP directly on the imbalanced data, which assigns higher cost to errors corresponding to minority class compared to that of majority class. Granular SVM (GSVM) [Tang et al., 2009] is an asymmetric classifier which do not focus exclusively on assigning a different cost parameter. GSVM uses repetitive undersampling to achieve data cleaning and also to avoid loss of data.

Our approach to address class imbalance problem is motivated by co-ordination learning [Guo et al., 2005], in which samples belonging to two different classes are considered in pairs to train classifiers such as SVMs. Co-ordination learning helps the classifiers to better learn the dependencies existing between samples across different classes [Guo et al., 2005]. We show that learning these dependencies will improve the classifier performance in a class imbalanced scenario. Our approach mainly differs from co-ordination learning in terms of (a) not restricting the pair of samples to belong to different class, (b) re-purposing our data representation to address class imbalance problem, and (c) the approach adopted for testing the classifier, which are explained in Section 3. These are the major contributions of this paper. To the best of our knowledge, this is the first time s2s-based representation is used for addressing the class imbalance problem.

Proposed approach is very different from other approaches addressing class imbalance problem. Our approach neither eliminates the majority class samples nor generates duplicate/synthetic minority class samples. Moreover, majority voting based output is obtained in our approach using only a single base classifier but not an ensemble of classifiers.

3 Proposed Approach

The proposed approach to address the class imbalance problem is explained in three steps i.e., (1) data representation, (2) classifier training and (3) classifier testing. In this work, we use MLP architecture (as shown in Figure 1) as the base classifier. We refer to this MLP architecture as s2s-MLP.

3.1 Data Representation

Consider a two-class classification task with C = {C1,C2} denoting the set of class labels, and let N1 and N2 be the number of samples corresponding to C1 and C2, respectively. In general, to train a classifier, the samples in the training set are provided as an input-output pair as follows.

where ⃗xij ∈ Rd×1 refers to the d-dimensional feature vector representing the j th sample in ith class, and Ci ∈ C refers to output label of ith class. T refers to the transpose of a vector.

In the proposed s2s data representation, we will simultaneously consider two samples as follows.

where ⃗xij, ⃗xkl ∈ Rd×1 refer to the d-dimensional feature vectors representing the j th sample in ith class and lth sample in the kth class, respectively. (Ci, Ck) ∈ C refers to the output labels of ith and kth class, respectively.

Hence, in s2s representation, we will have an input feature vector of length 2d i.e., [⃗xij, ⃗xkl] ∈ R2d×1 , and output class labels as either [C1,C1], [C1,C2], [C2,C1] or [C2,C2]. By representing the data in the s2s format, the number of samples in the train set increases from (N1 + N2) to (N1 + N2)2 samples. Additionally, s2s representation is hypothesized to provide the classifier with a better scope to learn the intraclass and inter-class variations [Guo et al., 2005].

Class imbalance condition: Now let us consider the case where the two classes C1 and C2 are imbalanced with C1 being the majority class and C2 being the minority class, and N1 = M and N2 = N such that M ≫ N. In s2s-based data representation (as in eq. (2)), the number of samples generated by simultaneously considering two samples is (M+N)2 .

The distribution of the samples across different combinations in s2s data representation is explained by taking an example case where M = 75 and N = 25. The four blocks, as shown in Figure 2, represent the four possible combinations that can be obtained by simultaneously considering the majority and minority class samples i.e., majority-majority, majority-minority, minority-majority and minority-minority class combinations with sizes M × M = 5625, M × N = 1875, N ×M = 1875 and N ×N = 625, respectively. Note that the total number of samples generated using s2s representation is (M +N)2 = 10000 from (M +N) = 100 samples, where the total number of samples carrying majority class information are: (M × M) + (M × N) + (N × M) = 9375 while the total samples carrying minority class information are: (N ×N) + (M ×N) + (N ×M) = 4375. Note that, here the class imbalance problem still persists.

To overcome this problem, we constrain the majoritymajority sample combinations by combining each of the M samples corresponding to class C1 with only MN (where MN = N) randomly chosen samples corresponding to class C1 (as represented by the shaded portion bounded by the dotted line, labeled as M ×MN, in Figure 2). This modifies the number of majority-majority samples in the s2s data representation to M ×MN = 1875 while the number of samples in other class combinations remain the same. This modification in s2s representation is called as majority-constrained s2s results in a total of (M×MN)+(M×N)+(N×M) = 5625

samples carrying majority class information while maintaining a total of 4375 samples carrying minority class information. Thus, the majority-constraint reduces the proportion of samples carrying majority class information.

3.2 Classifier Training

MLP is one of the most common feed forward neural network which has been successfully used in various classification tasks. We will consider MLP as the base classifier to validate our s2s data representation. To train MLP on s2s data representation, the following architecture of MLP (see Figure 1) is considered.

• Input layer have 2×d linear units to accept the two samples i.e., ⃗xij and ⃗xkl, simultaneously.
• The number of units in the hidden layer is selected empirically by varying the hidden units from 2 to 4 × d (twice the length of the input layer) and then selecting the number of units with the best performance on the validation set. Rectified linear units (ReLU) are used as the activation function for the hidden layers. We considered a single hidden layer for most of the experiments.
• The output layer will consist of units equal to twice the considered number of classes in the classification task i.e, the output layer will have four units for two-class classification task. Sigmoid activation function (not softmax) is used for the output units as the output labels in the proposed s2s data representation will have more than one unit active at a time (not one-hot encoded output).

As can be seen from Figure 1, the output layer has outputs ⃗yi and ⃗yk corresponding to the output labels associated with the input feature vectors ⃗xij and ⃗xkl, respectively. For a two-class classification task, the output layer will have 4 output units with the possible output labels as [0, 1, 0, 1], [0, 1, 1, 0], [1, 0, 0, 1], [1, 0, 1, 0] corresponding to the class labels [C1,C1], [C1,C2], [C2,C1] and [C2,C2], respectively. Note that in s2sL, s2s-based data representation is used for training the s2s-MLP to address the class imbalance problem.

For training s2s-MLP, we use Adam algorithm with an initial learning rate of 0.001. Binary cross-entropy is used as the cost function. The batch size and other hyper-parameters are selected considering the performance on the validation set.

3.3 Classifier Testing

Generally, the feature vector corresponding to the test sample is provided as input to the trained MLP in the testing phase and the class label is decided based on the output obtained. In case of ensemble-based methods, the same test sample is provided as input to an ensemble of classifiers and the final class label is obtained using majority voting on the outputs obtained from the ensemble of classifiers.

In s2sL method, the feature vector corresponding to the test sample should also be converted to the s2s-based representation for testing the s2s-MLP. We obtain the s2s representation of the test sample by concatenating the test sample with a set of pre-selected reference samples, whose class label is known a priori, as follows.

Highly Imbalanced Datasets

where ⃗ti ∈ Rd×1 , ⃗rj ∈ Rd×1 refer to the d-dimensional feature vector corresponding to the ith test sample and j th reference sample, respectively. S and R refers to the considered number of test and reference samples, respectively. The preselected reference samples can belong to either majority or minority class. But better performance is obtained when the reference samples are selected from the majority class samples. Also, the performance obtained by selecting the reference samples from train set is similar to that obtained when samples are unseen by the network during training.

For testing the s2s-MLP (as shown in Figure 3), each test sample ⃗ti is combined with all the R reference samples (⃗r1,⃗r2, · · · ,⃗rR) to formR different instances of the same test sample ⃗ti. The corresponding outputs (di1, di2, · · · , diR) obtained from s2s-MLP for the R generated instances of ⃗ti are combined by majority voting approach to obtain the final decision Di. The class label with maximum number of votes is considered as the output label. It is important to note that the majority voting based decision is obtained using a single base classifier but not an ensemble of classifiers.

4 Experiments and Results

Experiments are conducted on ten standard two-class imbalanced datasets, with different degree of imbalance, belonging to wide range of domains: computational biology and bio-informatics (Pima, Ecoli, Yeast and Abalone), document classification (Pageblock), image annotation (Vehicle) and object classification (Glass). All datasets used in this work are obtained from KEEL dataset repository [Fern´andez et al., 2008]. Table 1 summarizes the details of the datasets using original/generic representation and s2s (majority-constrained s2s) based representation. The datasets are listed in the increasing order of their imbalance ratio (IR). Datasets with IR between 1.5 and 9 are considered as relatively low imbalanced datasets, and datasets with IR above 9 are considered as highly imbalanced datasets [Fern´andez et al., 2008]. Attributes (d) refers to the number of feature attributes. In s2s representation, #Majority and #Minority refer to the number of samples carrying majority class information and minority class information, respectively. We can observe from Table 1 that in generic representation, the majority class samples heavily outnumber the minority class samples in most datasets. Whereas in s2s representation with majorityconstraint, #Majority and #Minority are comparable. Further, the actual number of minority class samples are very low in most of the datasets (which make it difficult for the classifiers to learn the characteristics of the minority class) but are increased to a higher value in s2s approach.

For each dataset, we use 5-fold (the folds as provided in the KEEL dataset repository are directly used) cross-validation approach to compare the performance of all the methods considered for analysis. In KEEL dataset repository, each fold is obtained by randomly selecting the samples from the dataset but maintaining the same IR value across all folds as in the original dataset and there is no overlap between any of the two folds. Hence, at any time 80% of the data is used for training (75% as train set and 5% as validation set) and remaining 20% of the data is used for testing. The validation set is used for selecting network architecture and for hyperparameter tuning. It is to be noted that the s2s-based representation is obtained separately on the train, validation and test sets, respectively. Majority-constrained s2s-based data representation is obtained on train set considering MN = N; and for the test set, majority voting is used, where R = 20 randomly selected majority class samples from the training set are used as the pre-selected reference set. The choice of R = 20 is obtained empirically by experimenting with different values of R.

We employed the widely used F - measure (Fβ) as a metric which is defined as:

where Precision refers to the ratio of number of minority class samples correctly classified to the total number of samples classified as minority class by the classifier, and Recall refers to the ratio of the number of minority class samples that are correctly classified to the total number of minority class samples in the test set. In eq. (4), a higher value of β indicates higher importance to Recall over Precision. In this paper, we will consider the widely used F1 (when β = 1) along with F2 (when β = 2) as performance metrics, as previously used in [Maratea et al., 2014; Wu et al., 2017]. The higher the values of Fβ, the better is the performance of the system. Fβ values reported in this paper are the mean scores obtained from the 5-fold cross validation.

Methods for comparison: We compare the performance of our proposed s2sL based approach with nine state-of-theart methods, namely, Sampling-based methods (CSMOTE (CSM) [Nanni et al., 2015], MWMOTE (MWM) [Barua et al., 2014]), ensemble-based methods (RUSBoost (RUSB) [Seiffert et al., 2010], EUSBoost (EUSB) [Galar et al., 2013], UCML [Wu et al., 2017] and Hard-Ensemble (HE) [Nanni et al., 2015]) and cost-sensitive learning based methods (CSMLP (CMLP) [Castro and Braga, 2013] and GSVM [Tang et al., 2009]).

Further, a conventional MLP is also considered to show the significance of s2s-based data representation in handling the class imbalance problem. Proposed s2sL along with MLP and CSMLP techniques are implemented using Keras deep learning toolkit [KER, 2016], and most of the other methods are implemented as provided in KEEL software [Fern´andez et al., 2008].

4.1 Results and Analysis

Experimental results obtained on low and highly imbalanced datasets are provided in Table 2 and Table 3, respectively. It is to be noted that the results for the proposed approach (in Table 2 and 3) are obtained by considering majority-constrained s2sL method. It can be observed that the s2sL approach outperforms all the state-of-the-art methods across all the datasets (for both low and highly imbalanced datasets). Also, s2sL achieves a huge improvement in performance compared to the other methods on highly imbalanced datasets. This is evident from the large difference in Fβ values obtained between s2sL and the other methods, for highly imbalanced datasets. Higher F1 and F2 values obtained by the s2sL approach compared to the other methods signifies that the proposed approach not only classifies the minority class samples accurately, but also has a good performance on the majority class samples which is reflected by the higher values of F2. The class-wise accuracies (in %) obtained for highly imbalanced datasets using s2sL (as provided in Table 4) further validate this analysis. These class-wise accuracies are obtained using 5-fold cross validation. Moreover, the results in Tables 2 and 3 are analyzed by conducting statistical tests [Hodges et al., 1962; Demˇsar, 2006]. These test results indicate that the s2sL approach makes a statistically significant difference in comparison to other methods.

The enhanced performance of s2sL compared to previous approaches may be attributed to the s2s-based data representation. s2s-based data representation seems to help the classifiers not only to learn the independent class-specific information (as in generic data representation) but in addition the "similarities and differences" that might exist between the classes [Guo et al., 2005].

4.2 Significance of Majority Constraint

In the proposed s2sL approach, constraining the [majority, majority] combinations is one of the main component. Here, we will discuss the significance of this component on the performance of s2sL approach. Proposed approach without considering majority constraint (i.e., MN = N) is referred to as s2sLC . s2sL method considering majority constraint (i.e., MN =M) is represented as s2sLC (Note: s2sLC ≡ s2sL) in Table 5.

Table 5 provides the performance obtained for s2sLC and s2sLC on 5 datasets. ∆F1 is computed as: ∆F1 = F1(s2sLC) - F1(s2sLC ). It can be observed that the majority constraint improves the performance of the s2sL approach by large margin (∆F1 are higher across all datasets as shown in Table 5. This shows the importance of the proposed majority constraint on s2sL for addressing the class imbalance problem.

4.3 Computational Complexity

Generally, the quadratic increase in the number of training samples generated by the proposed s2s-based data representation, and the increase in the number of input and output layer units of the MLP (i.e., s2s-MLP) may raise concerns about the computational complexity of the proposed s2sL approach. Computational time taken by s2sL to train the s2s-MLP for a single epoch may be higher compared to that taken to train MLP and CSMLP, but the s2sL based system converges much faster and to a better local minima compared to MLP and CSMLP as can be observed from Figure 4. Figure 4 shows the loss (binary cross-entropy) obtained on the train and test sets, of Yeast6 dataset, at every epoch for MLP, CSMLP and s2sL based systems. It can be observed from Figure 4 that s2sL requires lower number of epochs (23 epochs) to reach the minima of the training loss (loss = 0.017) compared to MLP (which required 132 epochs to reach the minima of the training loss = 0.062) and CSMLP (which required 124 epochs to reach the minima of the training loss of 0.056). Further, the average training time (in seconds) for convergence (using i5-3210M 3.1GHz cpu with 4-GB RAM) on Yeast6 for different techniques are: 98.7 (s2sL), 38.5 (MLP), 43.7 (CS-MLP), 213.8 (CSM), 95.3 (GSVM), 146.4 (EUSB). This shows that s2s is not that computationally complex compared to other state-of-the-art techniques.

5 Summary and Conclusions

In this paper, we proposed a novel approach of data representation, called s2s to address the class imbalance problem. Our proposed s2sL approach increases the number of training sample instances quadratically by simultaneously considering two samples to train the classifier (MLP). For training, we considered the architecture of MLP which we referred to as s2s-MLP to handle the s2s data representation. During testing, multiple instances of the same test sample are generated by concatenating the test sample with a set of pre-selected reference samples. Further, in s2sL approach, a single base classifier is used and is sufficient to obtain majority voting based decision on these test sample instances. Experiments conducted on ten bench-mark datasets, with different degrees of imbalance, illustrate the significance of the proposed s2sL approach over the existing state-of-the-art approaches.