## 4 A Novel Bagging Method Based on Ensemble Margin
### A Novel Bagging Method Based on Ensemble Margin  
The proposed ensemble margin based imbalance learning method is inspired by SMOTEBagging [8], a major oversampling method which has been defined in the previous section. It combines under sampling, ensemble and margin concepts. Our method pays more attention to low margin instances. It could overcome the shortcomings of both _SMOTEBagging_[8] and _UnderBagging_[38]. This method has lower computational complexity than _SMOTEBagging_ and focuses more on important instances for classification tasks than _UnderBagging_. The proposed method has three main steps:  
1. Computing the ensemble margin values of the training samples via an ensemble classifier. 2. Constructing balanced training subsets by focusing more on small margin instances. 3. Training base classifiers on balanced training subsets and constructing a new ensemble with a better capability for imbalance learning. Denote \(S=\{X,Y\}=\{x_{i},y_{i}\}_{i=1}^{n}\) as training samples. The first step of our method involves a robust ensemble classifier: _bagging_ which is constructed using the whole training set. The margin value of each training instance is then calculated. In the second phase, we aim to select the most significant training samples for classification to form several new balanced training subsets. Suppose \(L\) is the number of classes and \(N_{i}\) the number of training instances of the \(ith\) class. We sort those classes in descending order according to their number of instances. Therefore, \(N_{L}\) is the training size of class \(L\), which is the smallest, and \(N_{1}\) is the training size of class \(1\) which is the largest. The training instances of each class, \(1\leqslant c\leqslant L\), are sorted in descending order according to the margin based importance evaluation function (Equation (5)) previously introduced. For each class \(c\), the higher the importance value \(W(x_{i})\) of an instance \(x_{i}\in c\), the more important this instance is for classification decision. Then, as in _SMOTEBagging_[8], a resampling rate \(a\) is used to control the amount of instances which should be chosen in each class to contract a balanced data set. All the instances of the smallest class are kept. The detailed steps of our method are shown in Algorithm 1. The range of \(a\) is set from 10 to 100 first. For each class \(c\
eq L\), \(L\) representing the smallest class, \(N_{L}\) instances are bootstrapped from the first \(N_{1}\cdot a\%\) of the importance ordered samples of class \(c\) to construct subset \(S_{c1}\). All the subsets are balanced. When the amount of class \(c\) (\(2\leqslant c\leqslant L-1\)) is under \(N_{1}\cdot a\%\), \(N_{L}\) instances are bootstrapped from the first \(N_{c}\) samples of class \(c\), which is the same as in _UnderBagging_. Then the \(N_{L}\) smallest class samples are combined with \(S_{c1}\) (\(c=1,...,L-1\)) to construct the first balanced data. In the next phase, the first base classifier is built using the obtained balanced training set. Figure 3 presents the flowchart of our method with an ensemble size \(T\) and a range of 10-100% for \(a\). The elements in the range of \(a\) could construct an arithmetic progression denoted as \(A\). If we build \(T=100\) classifiers as ensemble members, every 10 classifiers will be built with different  
Figure 2: Shift procedure for sum operation based margin. resampling rates \(a\) ranging from 10% to 100%, as in _SMOTEBagging_. However, while _SMOTEBagging_ uses \(N_{1}\), the training size of the largest class 1, as a standard for carrying out oversampling (SMOTE) on other relative minority classes, our method use \(N_{L}\), the training size of the smallest class \(L\), as a standard for performing an instance importance based undersampling on other relative majority classes. **Training phase Inputs:**  
1. Training set \(S=(x_{1},y_{1}),(x_{2},y_{2},),\cdots,(x_{n},y_{n})\);
2. Number of classes \(L\);
3.