This Website contains additional material to the paper
A. Fernández, V. López, M. Galar, M.J. del Jesus and F. Herrera, Analysing the Classification of Imbalanced Data-sets with Multiple Classes: Binarization Techniques and Ad-Hoc Approaches for Preprocessing and Cost Sensitive Learning. Submitted to Knowledge Based Systems Journal, according to the following summary:

1. Paper Content
2. Description of the Algorithms Selected in the Paper
   1. Preprocessing and Cost-Sensitive Learning
   2. Classification Algorithms
3. Data-sets partitions Employed in the Paper
4. Experimental Study
   1. Parameters
   2. Experimental Results
   3. Statistical Study

Paper Content

A. Fernández, V. López, M. Galar, M.J. del Jesus and F. Herrera, Analysing the Classification of Imbalanced Data-sets with Multiple Classes: Binarization Techniques and Ad-Hoc Approaches for Preprocessing and Cost Sensitive Learning. Submitted to Knowledge Based Systems Journal, according to the following summary:

Abstract: Within the real world applications of classification in engineering, there is a type of problem which is characterised by having a very different distribution of examples among their classes. This situation is known as the imbalanced class problem and it creates a handicap for the correct identification of the different concepts that are required to be learnt.

Traditionally, researches have addressed the binary class imbalanced problem, where there is a positive and a negative class. In this work, we aim to go one step further focusing our attention on those problems with multiple imbalanced classes. This condition imposes a harder restriction when the objective of the final system is to obtain the most accurate precision for each one of the different classes of the problem.

The goal of this work is to provide a throughout experimental analysis that will allow us to determine the behaviour of different approaches proposed in the specialized literature. First, we will make use of binarization schemes, i.e. one-vs-one and one-vs-all, in order to apply the standard approaches for solving binary class imbalanced problems. Second, we will apply several procedures which have been designed ad-hoc for the scenario of imbalanced data-sets with multiple classes.

This experimental study will include several well-known algorithms from the literature such as Decision Trees, Support Vector Machines and Instance-Based Learning, trying to obtain a global conclusion from different classification paradigms. The extracted findings will be supported by a statistical comparative analysis under more than 20 data-sets from the KEEL repository.

Summary:

1. Introduction.
2. Imbalanced Data-sets in Classification.
   1. The problem of imbalanced data-sets.
   2. Addressing the imbalanced problem: preprocessing and cost sensitive learning.
   3. Evaluation in imbalanced domains.
3. Solving Multiple Class Imbalanced Data-sets.
   1. Static-SMOTE.
   2. Global-CS.
   3. Synergy of standard approaches for imbalanced data-sets and binarization techniques.
      1. One-vs-One approach.
      2. One-vs-All approach.
4. Experimental Framework.
   1. Data-sets.
   2. Algorithms selected for the study.
   3. Web page associated to the paper.
5. Experimental Study.
   1. Analysis of the combination of preprocessing and cost sensitive approaches with multi-classification.
   2. Study of the use of OVO versus OVA for imbalanced data-sets.
   3. Comparative analysis for pairwise learning with preprocessing/cost sensitive learning and standard approaches in multiple class imbalanced problems.
      1. C4.5 Decision Tree.
      2. Support Vector Machines.
      3. k-Nearest Neighbour.
6. Lessons learned and future work.
7. Concluding Remarks.

Description of the Algorithms Selected in the Paper

Preprocessing and Cost Sensitive Learning

A large number of approaches have previously been proposed to deal with the class imbalance problem, both for standard learning algorithms and for ensemble techniques (M. Galar, A. Fernández, E. Barrenechea, H. Bustince, and F. Herrera, "A review on ensembles for class imbalance problem: Bagging, boosting and hybrid based approaches," IEEE Trans. Syst., Man, Cybern. C, 2012). These approaches can be categorised in three groups:

Data level solutions: the objective consists in rebalancing the class distribution by sampling the data space to diminish the effect caused by their class imbalance acting as a external approach (N.V. Chawla, K. W. Bowyer, L. O. Hall, and W. P. Kegelmeyer, "Smote: Synthetic minority over-sampling technique," J. Artif. Intell. Res., vol. 16, pp. 321–357, 2002, G. E. A. P. A. Batista, R. C. Prati, and M. C. Monard, "A study of the behaviour of several methods for balancing machine learning training data," SIGKDD Explor. Newsl., vol. 6, no. 1, pp. 20–29, 2004., Y. Tang, Y.-Q. Zhang, and N. V. Chawla, "SVMs modeling for highly imbalanced classification,” IEEE Trans. Syst., Man, Cybern. B, vol. 39, no. 1, pp. 281–288, 2009.).
Algorithmic level solutions: these solutions try to adapt several classification algorithms to reinforce the learning towards the positive class. Therefore, they can be defined as internal approaches that create new algorithms or modify existing ones to take the class imbalance problem into consideration (B. Zadrozny and C. Elkan, “Learning and making decisions when costs and probabilities are both unknown,” in Proceedings of the 7th International Conference on Knowledge Discovery and Data Mining (KDD’01), 2001, pp. 204–213.,R. Barandela, J. S. Sánchez, V. García, and E. Rangel, “Strategies for learning in class imbalance problems,” Pattern Recogn., vol. 36, no. 3, pp. 849–851, 2003., C. Diamantini and D. Potena, “Bayes vector quantizer for class imbalance problem,” IEEE Trans. Knowl. Data Eng., vol. 21, no. 5, pp. 638–651, 2009.).
Cost sensitive solutions: this type of solutions incorporate approaches at the data level, at the algorithmic level, or at both levels jointly, considering higher costs for the misclassification of examples of, the positive class with respect to the negative class, and therefore, trying to minimise higher cost errors (P. Domingos, “Metacost: a general method for making classifiers cost sensitive,” in Advances in Neural Networks, International Journal of Pattern Recognition and Artificial Intelligence, 1999, pp. 155–164., K. M. Ting, “An instance-weighting method to induce cost-sensitive trees,” IEEE Trans. Knowl. Data Eng., vol. 14, no. 3, pp. 659–665, 2002., B. Zadrozny, J. Langford, and N. Abe, “Cost-sensitive learning by cost-proportionate example weighting,” in Proceedings of the 3rd IEEE International Conference on Data Mining (ICDM’03), 2003, pp. 435–442., Y. Sun, M. S. Kamel, A. K. C. Wong, and Y. Wang, “Cost-sensitive boosting for classification of imbalanced data,” Pattern Recogn., vol. 40, pp. 3358–3378, 2007., H. Zhao, “Instance weighting versus threshold adjusting for cost sensitive classification.” Knowl. Inf. Syst., vol. 15, no. 3, pp. 321–334, 2008., Z.-H. Zhou and X.-Y. Liu, “On multi-class cost-sensitive learning,” Comput. Intell., vol. 26, no. 3, pp. 232–257, 2010.).

The advantage of the data level solutions is that they are more versatile, since their use is independent of the classifier selected. Furthermore, we may preprocess all data-sets before-hand in order to use them to train different classifiers. In this manner, we only need to prepare the data once. There exists different rebalancing methods for preprocessing the training data, that can be classified into three groups:

Undersampling methods that create a subset of the original data-set by eliminating some of the examples of the majority class.
Oversampling methods that create a superset of the original data-set by replicating some of the examples of the minority class or creating new ones from the original minority class instances.
Hybrid methods that combine the two previous methods, eliminating some of the minority class examples expanded by the oversampling method in order to eliminate overfitting.

Regarding algorithmic level approaches, the idea is to choose an appropriate inductive bias given a specific classifier. Also, recognition-based one-class learning is used to model a system by using only the examples of the target class in the absence of the counter examples. This approach does not try to partition the hypothesis space with boundaries that separate positive and negative examples, but it attempts to make boundaries which surround the target concept, for example in SVMs.

Cost sensitive learning takes into account the variable cost of a misclassification of the different classes. The cost sensitive learning process tries to minimise the number of high cost errors and the total error of misclassification. Therefore, cost sensitive learning supposes that there is a cost matrix available for the different type of errors; however, given a data-set, this matrix is not usually given (Y. Sun, M. S. Kamel, A. K. C. Wong, and Y. Wang, “Cost-sensitive boosting for classification of imbalanced data,” Pattern Recogn., vol. 40, pp. 3358–3378, 2007.,Y. Sun, A. K. C. Wong, and M. S. Kamel, “Classification of imbalanced data: A review,” International Journal of Pattern Recognition and Artificial Intelligence, vol. 23, no. 4, pp. 687–719, 2009.).

In order to develop our experimental study, we have selected from the specialised literature several representative methods that deals with imbalanced classification for the aforementioned families. Specifically we have chosen four undersampling and four oversampling techniques, and a cost sensitive learning approach which are described below. We must also stress that all these mechanisms are available within the KEEL software tool http://www.keel.es (J. Alcalá-Fdez, L. Sánchez, S. García, M. J. del Jesus, S. Ventura, J. M. Garrell, J. Otero, C. Romero, J. Bacardit, V. M. Rivas, J. C. Fernández, and F. Herrera, “KEEL: A software tool to assess evolutionary algorithms to data mining problems,” Soft Comp., vol. 13, no. 3, pp. 307–318, 2009.).

Synthetic Minority Oversampling Technique (SMOTE) (N. V. Chawla, K. W. Bowyer, L. O. Hall, and W. P. Kegelmeyer, “Smote: Synthetic minority over-sampling technique,” J. Artif. Intell. Res., vol. 16, pp. 321–357, 2002.). Since the next two oversampling approaches are based on this technique, in what follows we will explain it in detail its main features.

With this approach, the positive class is over-sampled by taking each minority class sample and introducing synthetic examples along the line segments joining any/all of the k minority class nearest neighbours. Depending upon the amount of over-sampling required, neighbours from the k nearest neighbours are randomly chosen. This process is illustrated in the following Figure, where $x_i$ is the selected point, $x_i1$ to $x_i4$ are some selected nearest neighbours and $r_1$ to $r_4$ the synthetic data points created by the randomized interpolation. The implementation of this work uses only one nearest neighbour with the euclidean distance, and balances both classes to 50% distribution.

Synthetic samples are generated in the following way: Take the difference between the feature vector (sample) under consideration and its nearest neighbour. Multiply this difference by a random number between 0 and 1, and add it to the feature vector under consideration. This causes the selection of a random point along the line segment between two specific features. This approach effectively forces the decision region of the minority class to become more general. An example is detailed in the next Figure.

In short, the main idea is to form new minority class examples by interpolating between several minority class examples that lie together. In contrast with the common replication techniques (for example random oversampling), in which the decision region usually become more specific, with SMOTE the overfitting problem is somehow avoided by causing the decision boundaries for the minority class to be larger and to spread further into the majority class space, since it provides related minority class samples to learn from. Specifically, selecting a small k-value could also avoid the risk of including some noise in the data.

 

• SMOTE + Edited Nearest Neighbour (SMOTE+ENN) (G. E. A. P. A. Batista, R. C. Prati, and M. C. Monard, “A study of the behaviour of several methods for balancing machine learning training data,” SIGKDD Explor. Newsl., vol. 6, no. 1, pp. 20–29, 2004.). When applying SMOTE, class clusters may be not well defined in cases where some majority class examples invade the minority class space. The opposite can also be true, since interpolating minority class examples can expand the minority class clusters, introducing artificial minority class examples too deeply into the majority class space. Inducing a classifier in such a situation can lead to overfitting. For this reason, the ``SMOTE + ENN'' hybrid approach, applies the Wilson's ENN rule (D. Wilson, “Asymptotic properties of nearest neighbor rules using edited data,” IEEE Transactions on Systems, Man, and Communications, vol. 2, no. 3, pp. 408–421, 1972.) after the SMOTE application to remove from the training set any example misclassified by its three nearest neighbours.
• Safe-Level SMOTE (C. Bunkhumpornpat, K. Sinapiromsaran, and C. Lursinsap, “Safe-level- SMOTE: Safe-level-synthetic minority over-sampling TEchnique for handling the class imbalanced problem.” in Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD09), ser. Lecture Notes in Computer Science, T. Theeramunkong, B. Kijsirikul, N. Cercone, and T. B. Ho, Eds., vol. 5476. Springer, 2009, pp. 475–482.). As we described previously, SMOTE randomly synthesises the minority instances along a line joining a minority instance and its selected nearest neighbours, ignoring nearby majority instances. On the contrary, Safe-Level SMOTE carefully samples minority instances along the same line with different weight degree, called safe level. The safe level is computed by using k-nearest neighbour minority instances. Then, if the safe level of an instance is close to 0, the instance is nearly noise. If it is close to k, the instance is considered safe.
• Random-Oversampling (G. E. A. P. A. Batista, R. C. Prati, and M. C. Monard, “A study of the behaviour of several methods for balancing machine learning training data,” SIGKDD Explor. Newsl., vol. 6, no. 1, pp. 20–29, 2004.). It is a non-heuristic method that aims to balance class distribution through the random replication of minority class examples. The hitch in this method is that it can increase the likelihood of occurring overfitting, since it makes exact copies of existing instances.
• Random-Undersampling (G. E. A. P. A. Batista, R. C. Prati, and M. C. Monard, “A study of the behaviour of several methods for balancing machine learning training data,” SIGKDD Explor. Newsl., vol. 6, no. 1, pp. 20–29, 2004.). Random-Undersampling is a non-heuristic method that aims to balance class distribution through the random elimination of majority class examples. The major drawback of Random-Undersampling is that this method can discard potentially useful data that could be important for the induction process.
• Neighbourhood Cleaning Rule (NCL) (D. Wilson, “Asymptotic properties of nearest neighbor rules using edited data,” IEEE Transactions on Systems, Man, and Communications, vol. 2, no. 3, pp. 408–421, 1972.). For a two-class problem, this cleaning algorithm can be described in the following way: for each example ei in the training set, its three nearest neighbours are found. If ei belongs to the majority class and the classification given by its three nearest neighbours contradicts the original class of ei, then ei is removed. If ei belongs to the minority class and its three nearest neighbours misclassify $e_i$, then the nearest neighbours that belong to the majority class are removed.
• Tomek Links (I. Tomek, “Two modifications of CNN,” IEEE Transactions on Systems Man and Communications, vol. 6, pp. 769–772, 1976.). Given two examples ei and ej belonging to different classes, being d(ei,ej) the distance between ei and ej, a (ei,ej) pair is called a Tomek link if there is not an example el, such that d(ei,el) < d(ei,ej) or d(ej ,el) < d(ei,ej). If two examples form a Tomek link, then either one of these examples is noise or both examples are borderline. Tomek links can be used as an under-sampling method or as a data cleaning method. As an under-sampling method, only examples belonging to the majority class are eliminated, and as a data cleaning method, examples of both classes are removed.
• One-Sided Selection (OSS) (M. Kubat and S. Matwin, “Addressing the curse of imbalanced training sets: one-sided selection,” in International Conference on Machine Learning, 1997, pp. 179–186.). It is an under-sampling method resulting from the application of Tomek links followed by the application of the Condensed Nearest Neighbour (CNN) rule (P. Hart, “The condensed nearest neighbor rule,” IEEE Trans. Inf. Theory, vol. 14, pp. 515–516, 1968.). Tomek links are used as an under-sampling method and to remove noisy and borderline majority class examples. Borderline examples can be considered ``unsafe'' since a small amount of noise can make them fall on the wrong side of the decision border. CNN aims to remove examples from the majority class that are distant from the decision border. The remainder examples, i.e. ``safe'' majority class examples and all minority class examples are used for learning.
• Instance Weighting (Cost sensitive learning) (P. Domingos, “Metacost: a general method for making classifiers cost sensitive,” in Advances in Neural Networks, International Journal of Pattern Recognition and Artificial Intelligence, 1999, pp. 155–164., K. M. Ting, “An instance-weighting method to induce cost-sensitive trees,” IEEE Trans. Knowl. Data Eng., vol. 14, no. 3, pp. 659–665, 2002.,H. Zhao, “Instance weighting versus threshold adjusting for costsensitive classification.” Knowl. Inf. Syst., vol. 15, no. 3, pp. 321–334, 2008.). In this approach different types of instances in the training data-set are weighted according to the misclassification costs during classifier learning, such that the classifier strives to make fewer errors of the more costly type, resulting in lower overall cost. Specifically, for identifying the costs associated to the misclassification of training examples we define the following scheme: if one positive example is classified as a negative one, the cost implied of this wrong classification is the IR of the data-set; whereas if one negative example is classified as if it were a positive class one, the associated cost is only one. Obviously, the cost of performing an accurate classification is consider to be 0, since in this case classifying correctly must not penalise the output model.

Regarding all these methodologies, we must discuss the differences between heuristic and non-informed techniques. The former are more sophisticated approaches which aim to perform oversampling (mostly based on the SMOTE) or undersampling (based on CNN) of instances taking into account the distribution of the instances within the space of the problem. Hence, these procedures try to identify the most significant examples in the borderline areas for enhancing the classification of the positive class. The latter selects random examples from the training set so that the distribution of examples is set to the desired value of the user (normally a completely balanced distribution). We must point out that in spite the first aforementioned techniques were developed to obtain more robust results, the quality of those "random" approaches is very high, in spite of their simplicity.

On the other hand, when considering what is a priori preferrable, whether to "add" or "remove" instances from the training set, several authors have shown the goodness of the oversampling approaches over undersampling and cleaning techniques (G. E. A. P. A. Batista, R. C. Prati, and M. C. Monard, “A study of the behaviour of several methods for balancing machine learning training data,” SIGKDD Explor. Newsl., vol. 6, no. 1, pp. 20–29, 2004., Fernández A, García S, del Jesus MJ, Herrera F (2008) A study of the behaviour of linguistic fuzzy rule based classification systems in the framework of imbalanced data–sets. Fuzzy Sets and Systems 159(18):2378–2398.). This may be due to the generation of a better defined borderline between the classes by adding more minority class examples in the overlapping areas. Furthermore, since cost sensitive learning based on instance weighting follows a similar scheme than oversampling, its behaviour is expected to be competitive with this kind of techniques.

However, the advantage of undersampling techniques lies in the reduction of the training time, which is especially significant in the case of high imbalanced data-sets with a large number of instances. Another positive feature of these approaches is their aim for smoothing the discrimination areas of the classes, which works also quite well in conjunction with the oversampling techniques, as we have introduced previously, i.e. SMOTE+ENN.

Classification Algorithms

C4.5 Decision Tree
C4.5 (Quinlan, J. R., 1993. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, San Mateo–California.) is a decision tree generating algorithm. It induces classification rules in the form of decision trees from a set of given examples. The decision tree is constructed top-down using the normalised information gain (difference in entropy) that results from choosing an attribute for splitting the data. The attribute with the highest normalised information gain is the one used to make the decision.

Support Vector Machine
An SVM (Vapnik, V., 1998. Statistical Learning Theory. Wiley, New York, U.S.A.) constructs a hyperplane or set of hyperplanes in a high-dimensional space. A good separation is achieved by the hyperplane that has the largest distance to the nearest training data-points of any class (so-called functional margin), since in general the larger the margin the lower the generalization error of the classifier.

In order to solve the quadratic problem that arises from SVMs, there are many techniques mostly reliant on heuristics for breaking the problem down into smaller, more-manageable chunks. A common method for solving the quadratic problem is the Platt's Sequential Minimal Optimization algorithm (Platt, J., 1998. Fast training of support vector machines using sequential minimal optimization. In: Schlkopf, B., Burges, C., Smola, A. (Eds.), Advances in Kernel Methods – Support Vector Learning. MIT Press, Cambridge, MA, pp. 42–65.), which breaks the problem down into 2-dimensional sub-problems that may be solved analytically, eliminating the need for a numerical optimization algorithm (Fan, R.-E., Chen, P.-H., Lin, C.-J., 2005. Working set selection using the second order information for training SVM. Journal of Machine Learning Research 6, 1889–1918.).\newline

k-Nearest Neighbour
kNN (McLachlan,G. J., 2004. Discriminant Analysis and Statistical Pattern Recognition, John Wiley and Sons) is a type of instance-based learning, or lazy learning where the function is only approximated locally and all computation is deferred until classification. The k-nearest neighbor algorithm is amongst the simplest of all machine learning algorithms: an object is classified by a majority vote of its neighbors, with the object being assigned to the class most common amongst its k nearest neighbors (k is a positive integer, typically small). If k = 1, then the object is simply assigned to the class of its nearest neighbor.

The training phase of the algorithm consists only of storing the feature vectors and class labels of the training samples. In the classification phase, k is a user-defined constant, and an unlabelled vector (a query or test point) is classified by assigning the label which is most frequent among the k training samples nearest to that query point.

Usually Euclidean distance is used as the distance metric; however this is only applicable to continuous variables. Regarding this fact, in this work we make use of the Heterogeneous Value Difference Metric (HVDM) (Wilson, D.R., Martinez, T.R., 1997. Improved heterogeneous distance functions. Journal of Artificial Intelligence Research 6 , 1-34. ). This metric computes the distance between two input vectors x and y as follows:

$$HVDM(x,y)=\sqrt{\displaystyle\sum_{a=1}^{m}d_a^2(x_a,y_a)}$$

where m is the number of attributes. The function d_a(x,y) returns a distance between the two values x and y for attribute a and is defined as:

$$d_a(x,y)=$$

$$1, \ if \ x \ or \ y \ is \ unknown; \ otherwise...$$

$$normalized\_vdm_a(x,y), \ if \ a \ is \ nominal$$

$$normalized\_diff_a(x,y), \ if \ a \ is \ linear$$

The function d_a(x,y) uses one of two functions (defined below), depending on whether the attribute is nominal or linear. Note that in practice the square root in is not typically performed because the distance is always positive, and the nearest neighbor(s) will still be nearest whether or not the distance is squared.

Since the distance for each input variable is given in the range (0,1), distances are often normalized by dividing the distance for each variable by the range of that attribute. For the new heterogeneous distance metric HVDM, the situation is more complicated because the nominal and numeric distance values come from different types of measurements: numeric distances are computed from the difference between two linear values, normalized by standard deviation, while nominal attributes are computed from a sum of C differences of probability values (where C is the number of output classes). It is therefore necessary to find a way to scale these two different kinds of measurements into approximately the same range to give each variable a similar influence on the overall distance measurement.

Since 95% of the values in a normal distribution fall within two standard deviations of the mean, the difference between numeric values is divided by 4 standard deviations to scale each value into a range that is usually of width 1. The function normalized_diff is therefore defined as shown below (being &sigma_a) is the standard deviation of the numeric values of attribute a):

$$normalized\_diff_a(x,y)=\frac{|x-y|}{4\sigma_a}$$

For the function normalized_vdm were considered an analogous formula to using Euclidean distance instead of Manhattan distance:

$$normalized\_vdm2_a(x,y)=\sqrt{|\frac{N_{a,x,c}}{N_{a,x}}-\frac{N_{a,y,c}}{N_{a,y}}|}$$

Data-sets partitions employed in the paper

For our experimental study we have selected twenty-four data sets from KEEL data-set repository. In all the experiments, we have adopted a 10-fold cross-validation model, i.e., we have split the data-set randomly into 10 folds, each one containing the 10% of the patterns of the data-set. Thus, nine folds have been used for training and one for test. Table 1 summarizes the properties of the selected data-sets. It shows, for each data-set, the number of examples (#Ex.), the number of attributes (#Atts.), the number of classes (#Cl.) and the imbalance ratio (IR). Furthermore, we show the number of instances per class in Table 2.

In the case of presenting missing values (autos, cleveland, dermatology and post-operative) we have removed the instances with any missing value before partitioning. The last column of this table contains a link for downloading the 10-fold cross validation partitions for each data-set in KEEL format. You may also download all data-sets by clicking here.

Table 1. Summary Description of the Data-Sets

id	Data-set	#Ex.	#Atts.	#Cl.	IR	Download.
Aut	Autos	159	25	6	16.00
Bal	Balance Scale	625	4	3	5.88
Cle	Cleveland	467	13	5	12.62
Con	Contraceptive Method Choise	1,473	9	3	1.89
Der	Dermatology	358	33	6	5.55
Eco	Ecoli	336	7	8	71.50
Fla	Flare	1,066	11	6	7.70
Gla	Glass Identification	214	9	6	8.44
Hay	Hayes-Roth	160	4	3	2.10
Led	Led7digit	500	7	10	1.54
Lym	Lymphography	148	18	4	40.5
New	New-thyroid	215	5	3	5.00
Nur	Nursery	12,690	8	5	2160.00
Pag	Page-blocks	5,472	10	5	175.46
Pos	Post-operative	87	8	3	62
Sat	Satimage	6,435	36	7	2.45
Shu	Shuttle	57,999	9	5	4558.60
Spl	Splice	3,190	60	3	2.16
Thy	Thyroid	7,200	21	3	40.16
Win	Wine	178	13	3	1.48
Wqr	Wine-Quality-Red	1,599	11	11	68.10
Wqw	Wine-Quality-White	4,898	11	11	439.60
Yea	Yeast	1,484	8	10	92.60
Zoo	Zoo	101	16	7	10.25

Table 2. Number of instances per class

Data	Examples	C1	C2	C3	C4	C5	C6	C7	C8	C9	C10
aut	159	46	13	48	29	20	3	-	-	-	-
bal	625	49	288	288	-	-	-	-	-	-	-
cle	467	164	36	35	55	13	164	-	-	-	-
con	1473	629	333	511	-	-	-	-	-	-	-
der	358	60	111	71	48	48	20	-	-	-	-
eco	336	143	77	2	2	35	20	5	42	-	-
fla	1066	331	239	211	147	95	43	-	-	-	-
gla	214	70	76	17	13	9	29	-	-	-	-
hay	160	65	64	31	-	-	-	-	-	-	-
led	500	45	37	51	57	52	52	47	57	53	49
lym	148	61	81	4	2	-	-	-	-	-	-
new	215	150	35	30	-	-	-	-	-	-	-
nur	12690	2	4320	4266	328	4044	-	-	-	-	-
pag	5472	4913	329	87	115	28	-	-	-	-	-
pos	87	62	24	1	-	-	-	-	-	-	-
sat	6435	1358	626	707	1508	703	1533	-	-	-	-
shu	57999	8903	45586	3267	49	171	13	10	-	-	-
spl	3190	767	768	1655	-	-	-	-	-	-	-
thy	7200	6666	368	166	-	-	-	-	-	-	-
win	178	59	71	48	-	-	-	-	-	-	-
wre	1599	681	638	199	53	18	10	-	-	-	-
wwh	4898	2198	1457	880	175	163	20	5	-	-	-
yea	1484	244	429	463	44	35	51	163	30	20	5
zoo	101	41	13	10	20	8	5	4	-	-	-

Experimental Study

Parameters

Next, we detail the parameters values for the different algorithms selected in this study, which have been set considering the recommendation of the corresponding authors, which is the default parameters' setting included in the KEEL software (J. Alcalá-Fdez, L. Sánchez, S. García, M. del Jesus, S. Ventura, J. Garrell, J. Otero, C. Romero, J. Bacardit, V. Rivas, J. Fernández, and F. Herrera, "KEEL: A software tool to assess evolutionary algorithms to data mining problems," Soft Computing, vol. 13, no. 3, pp. 307–318, 2009).

• C4.5

For C4.5 we have set a confidence level of 0.25, the minimum number of item-sets per leaf was set to 2 and the application of pruning for the final tree.

• SVM

For the SVM we have chosen gaussian reference functions, with an internal parameter of 0.25 of each kernel function and a penalty parameter of the error term of 100.0.

• kNN

In this case we have selected 3 neighbours for determining the output class, applying the HVDM as distance metric.

Regarding preprocessing techniques, the cleaning procedures employ 3 neighbours to determine whether an instance corresponds to noise or not. In the case of SMOTE and related preprocessing techniques, we will consider the 5-nearest neighbours of the minority class to generate the synthetic samples, and balancing both classes to the 50% distribution. In our preliminary experiments we have tried several percentages for the distribution between the classes and we have obtained the best results with a strictly balanced distribution.

Experimental Results

In this section, we present the empirical analysis of our methodology for multiple-class imbalanced problems. This section is divided into two parts, each one devoted for the results with the average accuracy metric and for the mean f-measure respectively.

Average Accuracy Metric

Tables 3 to 8 show the results in training and test for all data-sets with the Average Accuracy measure for the three algorithms, namely C4.5, SVM and kNN. These tables can be downloaded as an Excel document by clicking on the following link

Table 3. Results for the C4.5 decision tree with the Average Accuracy metric for the OVO methodology. Including the results for the global cost-sensitive and static-smote approaches.

	Base		OVO		Global-CS		Static-SMT		NCL		OSS		RUS		TMK		ROS		SafeL.		SMT-ENN		SMOTE		OVO-CS
Data	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst
aut	94.19	80.76	88.09	76.25	97.68	84.26	94.86	82.04	51.52	49.36	69.12	58.75	86.29	70.24	60.11	51.49	96.08	81.42	97.01	80.53	88.09	76.25	95.37	80.11	96.28	81.31
bal	72.90	55.55	63.33	56.93	93.54	55.93	84.63	55.30	79.84	55.23	78.15	59.22	72.05	55.74	78.47	57.64	92.23	55.57	93.14	54.90	77.50	52.35	80.98	54.29	93.09	54.20
cle	70.58	29.24	64.07	24.61	98.08	27.65	76.99	24.91	48.65	27.40	56.00	33.61	67.03	28.31	64.91	29.56	86.50	28.95	90.90	32.46	49.19	29.06	71.66	33.89	89.36	27.35
con	71.66	51.72	66.27	50.08	80.36	49.83	78.61	47.19	56.51	48.61	57.19	50.11	65.63	52.88	65.06	52.34	74.54	48.05	75.28	49.82	63.43	52.31	73.27	50.09	74.77	49.74
der	98.01	93.48	98.42	95.65	99.61	93.56	98.56	94.83	98.34	96.21	94.96	91.21	97.54	95.24	98.35	95.37	98.80	95.71	98.82	95.37	98.66	95.65	98.76	95.61	98.89	96.33
eco	69.80	70.72	61.74	59.69	99.07	66.28	78.82	65.15	58.85	60.63	59.08	68.74	69.89	69.02	59.18	59.99	86.28	72.89	88.30	71.48	66.24	70.97	74.64	70.99	95.00	73.65
fla	65.56	59.24	61.30	59.09	82.09	64.20	78.04	64.01	61.30	59.09	33.33	33.33	69.74	63.47	61.12	59.19	76.43	64.39	77.72	62.97	61.30	59.09	75.63	64.74	77.18	63.72
gla	92.83	63.71	88.81	65.45	97.06	70.95	92.07	63.71	83.75	67.07	77.66	67.85	85.29	65.82	86.91	72.59	93.47	68.81	94.77	64.76	87.65	70.58	92.38	70.84	94.85	65.44
hay	90.76	83.49	90.76	83.49	90.76	83.49	90.03	86.03	73.48	72.22	86.44	85.71	90.76	83.49	89.52	85.48	90.77	82.86	90.87	83.49	80.31	70.08	90.87	83.49	90.76	83.49
led	77.26	71.40	77.33	70.52	77.90	69.43	78.25	72.55	71.57	65.98	73.72	70.69	77.24	70.89	76.30	70.82	77.38	71.59	77.64	71.34	76.06	71.32	77.36	71.64	77.83	70.72
lym	90.93	67.67	66.41	61.28	96.47	69.27	93.42	67.81	62.67	58.31	62.15	65.59	61.08	64.78	64.94	64.63	96.36	72.51	85.38	62.86	79.25	61.95	84.97	60.91	96.27	70.77
new	97.30	91.39	97.11	92.28	99.68	91.67	98.01	90.56	97.94	93.11	97.35	91.61	94.53	89.61	97.16	88.28	99.06	90.11	99.31	91.44	96.53	90.33	98.17	92.50	99.31	91.44
nur	75.43	88.30	75.42	88.45	99.04	93.51	85.30	87.76	75.92	88.35	73.75	87.62	70.19	83.39	74.96	88.63	90.98	93.33	93.06	93.69	77.88	92.79	93.05	94.07	99.03	93.58
pag	91.50	84.53	91.37	83.80	99.50	88.28	95.09	85.55	93.77	87.87	92.33	86.82	94.31	90.26	92.30	85.32	98.39	91.52	98.63	90.87	96.00	89.88	97.44	90.24	98.73	90.69
pos	35.81	46.62	35.00	48.33	91.44	38.90	30.06	21.34	35.00	48.33	35.80	48.33	35.57	48.89	35.00	48.33	87.26	37.13	38.70	48.89	36.01	47.78	37.35	48.33	87.93	31.92
sat	97.02	83.19	96.98	83.70	99.04	83.73	97.02	83.19	94.13	85.65	85.95	78.27	94.41	84.13	95.49	84.87	98.15	84.28	98.85	84.02	93.85	84.74	97.83	84.18	98.83	84.08
shu	97.04	92.19	99.77	97.98	99.99	98.55	99.51	95.05	99.44	98.25	91.07	90.54	95.63	93.27	99.21	98.17	99.84	96.69	99.84	96.69	99.65	94.70	100.00	96.84	99.95	96.79
spl	96.44	94.11	96.33	94.90	96.44	94.11	96.32	94.33	95.59	94.52	92.50	91.74	96.05	94.85	95.89	94.44	96.40	94.90	96.55	94.81	95.85	94.61	96.30	94.88	96.52	94.92
thy	99.44	98.65	99.54	98.32	99.90	98.94	99.87	98.65	99.64	98.94	99.30	98.62	98.77	98.71	99.66	97.76	99.89	99.02	99.90	98.94	99.39	98.28	99.72	99.28	99.89	98.93
win	98.92	94.98	99.16	91.24	98.94	94.32	98.81	94.24	96.60	87.17	94.87	87.46	98.62	93.71	97.44	89.24	99.12	91.24	99.22	92.27	97.36	87.75	99.08	92.02	99.18	91.35
wqr	75.48	31.87	42.55	27.05	97.17	34.01	75.48	31.87	52.23	33.17	46.78	32.17	59.61	38.32	49.80	31.43	91.88	33.30	94.28	34.25	59.51	32.57	80.76	34.01	94.82	35.84
wqw	69.08	38.78	57.25	32.32	69.08	38.78	69.08	38.78	52.84	34.31	48.08	31.09	55.69	33.83	57.35	34.96	92.82	41.41	96.29	41.20	55.52	36.64	78.36	42.35	96.29	40.49
yea	74.62	50.24	64.48	48.18	95.74	47.66	82.93	51.77	61.20	47.02	62.10	52.29	69.47	53.91	65.28	50.48	85.30	50.72	87.24	50.98	66.22	50.70	78.50	52.10	87.54	52.30
zoo	96.26	88.83	93.48	89.73	100.00	96.69	97.51	87.64	57.14	82.14	14.29	20.69	89.35	84.32	86.23	82.76	95.87	90.11	95.67	88.45	93.48	89.73	95.43	88.45	95.07	87.73
Avg	83.28	71.28	78.12	69.97	94.11	72.25	86.22	70.18	73.25	68.29	70.08	65.92	78.95	71.13	77.11	69.74	91.83	72.35	90.31	72.35	78.96	70.84	86.16	72.74	93.23	71.95

 

 

 

 

Mean f-Measure Metric

Tables 9 to 14 show the results in training and test for all data-sets with the Mean f-Measure for the three algorithms, namely C4.5, SVM and kNN. These tables can be downloaded as an Excel document by clicking on the following link

Table 9. Results for the C4.5 decision tree with the Mean f-Measure metric for the OVO methodology. Including the results for the global cost-sensitive and static-smote approaches.

	Base		OVO		Global-CS		Static-SMT		NCL		OSS		RUS		TMK		ROS		SafeL.		SMT-ENN		SMOTE		OVO-CS
Data	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst
aut	.92410	.80727	.88548	.75115	.96323	.83613	.94273	.81506	.45567	.39804	.60282	.50484	.82624	.69517	.56246	.45764	.95690	.81281	.96365	.79475	.94887	.78992	.94887	.78992	.95522	.80293
bal	.74538	.54382	.60909	.54685	.84956	.57946	.81956	.56402	.71813	.55590	.67684	.57354	.61509	.53380	.75586	.57710	.84801	.56679	.84916	.56836	.74955	.53819	.78303	.55747	.84811	.56119
cle	.73575	.26624	.66800	.23199	.95580	.26317	.79359	.22377	.41392	.22827	.48902	.29325	.60877	.28307	.62538	.26503	.86512	.27458	.90363	.31149	.51089	.27471	.75227	.31301	.88175	.26288
con	.71858	.51647	.66922	.50388	.78462	.49050	.78764	.47096	.50746	.43587	.51606	.45516	.64051	.51796	.62519	.50778	.73511	.47662	.73894	.49352	.62500	.51384	.72368	.49613	.73407	.49234
der	.97852	.93205	.98440	.95857	.99551	.93351	.98419	.94394	.98265	.96222	.94076	.90062	.96567	.94187	.98299	.95507	.98838	.95717	.98828	.95422	.98704	.95857	.98813	.95728	.98910	.96295
eco	.68793	.69823	.54155	.50999	.98357	.65140	.79784	.64292	.50377	.49696	.50291	.61268	.61033	.65795	.51227	.50135	.85730	.71253	.84809	.69599	.64380	.69263	.73214	.68894	.90559	.71971
fla	.66473	.58354	.60453	.58032	.76866	.61341	.74238	.61255	.60453	.58032	.59204	.56948	.66073	.60109	.59204	.56948	.72398	.61344	.72540	.59818	.71039	.61348	.71039	.61348	.72153	.60596
gla	.93841	.60665	.91077	.64000	.95585	.68614	.93300	.60665	.75620	.60196	.67101	.58196	.78875	.60456	.84394	.67324	.93904	.67296	.95032	.63386	.87706	.68276	.93356	.68058	.94960	.63942
hay	.90736	.83302	.90736	.83302	.90736	.83302	.89780	.85629	.67504	.64789	.85683	.84594	.90736	.83302	.89207	.85014	.90732	.82925	.90833	.83231	.79894	.69279	.90833	.83231	.90736	.83302
led	.77218	.69850	.77305	.68847	.77788	.68137	.78207	.70882	.69137	.62328	.73057	.69308	.77153	.69380	.76036	.69007	.77345	.69936	.77536	.69745	.75283	.69042	.77299	.69950	.77727	.69084
lym	.86913	.66954	.65258	.59078	.94940	.69336	.91362	.67168	.59840	.55169	.56852	.62999	.55768	.63263	.63255	.62394	.96140	.71930	.84886	.61184	.78915	.60286	.84467	.59304	.96023	.70603
new	.98004	.90356	.97928	.92489	.99094	.92255	.98064	.89682	.96605	.91293	.94388	.89042	.88649	.85963	.97610	.90005	.98542	.90616	.98063	.91664	.96417	.91247	.98028	.92900	.98063	.91664
nur	.76283	.89211	.76268	.89313	.94814	.91157	.82770	.88808	.74420	.86577	.70012	.83305	.61731	.73431	.75512	.89157	.89705	.91667	.89343	.91826	.76378	.90557	.89299	.92012	.93146	.91760
pag	.92528	.84541	.92410	.84031	.95028	.85159	.93629	.83952	.88740	.84155	.81902	.77720	.72778	.70191	.91512	.85632	.90386	.84571	.90452	.83924	.86449	.80387	.92004	.84349	.90646	.83497
pos	.30770	.39321	.29133	.40209	.88384	.37306	.26163	.18440	.29133	.40209	.29279	.38755	.29161	.39828	.29133	.40209	.74850	.37359	.33128	.41078	.31022	.40107	.31890	.40495	.74731	.33029
sat	.97247	.83322	.97335	.84268	.98656	.83500	.97247	.83322	.92988	.85302	.82632	.76069	.92977	.83496	.95012	.84841	.98114	.84723	.98620	.84211	.93652	.84660	.97826	.84402	.98603	.84239
shu	.98271	.92182	.99881	.97634	.92853	.92351	.99700	.94781	.97246	.96201	.84468	.84275	.77523	.76959	.99211	.96865	.91886	.89848	.91887	.89847	.97885	.92832	.98784	.94714	.91959	.89900
spl	.95885	.93526	.95897	.94472	.95885	.93526	.95578	.93521	.94849	.93823	.91524	.90747	.95321	.94142	.95230	.93868	.95796	.94331	.95927	.94233	.95099	.93888	.95705	.94271	.95892	.94359
thy	.99178	.97927	.99185	.97263	.98544	.97732	.99113	.97502	.98625	.97765	.94243	.94372	.86966	.86356	.98895	.96865	.98414	.97271	.98430	.97313	.97856	.96974	.98383	.97703	.98419	.97220
win	.98894	.94912	.99251	.91687	.98901	.94285	.98880	.94389	.96168	.86773	.94160	.86493	.98580	.93862	.97203	.89346	.99195	.91749	.99195	.92454	.97116	.87673	.99137	.92740	.99202	.91727
wqr	.78410	.31458	.41306	.25125	.93524	.33167	.78410	.31458	.50214	.32424	.39644	.29350	.37444	.29349	.52404	.31121	.91769	.33993	.93263	.34539	.57791	.30416	.78131	.31425	.93381	.36046
wqw	.70235	.39008	.52539	.32067	.70235	.39008	.70235	.39008	.41807	.29973	.41310	.30787	.34090	.27583	.50871	.33127	.92326	.44197	.92112	.43120	.53933	.34217	.74699	.39911	.92218	.42557
yea	.76759	.49978	.66203	.48600	.92797	.45234	.82510	.50018	.60118	.45344	.58035	.48532	.57903	.49604	.65241	.49410	.83648	.50747	.85107	.50469	.65630	.49685	.77975	.51327	.85254	.51924
zoo	.96463	.87175	.93541	.88294	1.00000	.96016	.97617	.86175	.49507	.75405	.49507	.75405	.86424	.81521	.84252	.78361	.96056	.88563	.95871	.86341	.95666	.86341	.95666	.86341	.95278	.85627
Avg	.83464	.70352	.77562	.68706	.91994	.71118	.85807	.69280	.69214	.64728	.67744	.65454	.71450	.66324	.75442	.67746	.89845	.71380	.87975	.70842	.78510	.69333	.84889	.71032	.90407	.70886

 

 

 

 

 

Table 14. Results for the k-Nearest Neighbour with the Mean f-Measure metric for the OVA methodology. Including the results for the global cost-sensitive and static-smote approaches.

	Base		OVA		Global-CS		Static-SMT		NCL		OSS		RUS		TMK		ROS		SafeL.		SMT-ENN		SMOTE		OVA-CS
Data	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst	Train	Tst
aut	.47105	.54773	.58905	.62928	.70821	.75204	.70022	.77862	.58570	.61862	.52204	.52335	.46917	.52417	.62259	.68178	.73765	.75287	.74081	.77747	.69012	.64351	.82153	.76859	.73985	.75954
bal	.59605	.58952	.58244	.58283	.55437	.56275	.55568	.55658	.63494	.60431	.60811	.58451	.64045	.61419	.63083	.60972	.56602	.57517	.56621	.56673	.80442	.60921	.81556	.58637	.56269	.56654
cle	.26489	.24507	.25710	.26020	.29900	.28877	.28380	.28074	.33505	.26510	.32484	.29704	.32499	.32382	.34566	.32783	.31567	.29412	.32106	.29114	.64145	.27583	.59897	.29879	.32202	.29583
con	.42633	.42181	.43443	.42878	.42452	.42289	.42298	.42284	.48987	.41397	.47025	.43419	.45031	.45798	.50638	.44639	.42950	.43191	.43044	.43216	.58075	.45145	.45181	.43519	.43139	.42199
der	.96598	.96594	.96052	.96296	.94970	.94799	.95130	.95060	.97730	.96923	.96766	.94769	.94855	.95285	.96577	.96705	.94977	.94584	.95073	.94362	.98472	.95985	.97037	.94973	.95099	.94362
eco	.56432	.71218	.55083	.69935	.56181	.71027	.54838	.69454	.57051	.71997	.54649	.71329	.47392	.62348	.57671	.73443	.55861	.70091	.56051	.71505	.68441	.72487	.71769	.73077	.55942	.70749
fla	.48365	.49472	.52679	.49399	.58176	.56259	.58726	.56916	.57546	.54357	.55339	.53748	.55876	.56532	.59595	.56810	.54793	.51221	.54365	.51027	.57732	.53547	.57992	.52361	.54724	.51867
gla	.61217	.63625	.65010	.65406	.67100	.69242	.69600	.71985	.64309	.62930	.67748	.70179	.66221	.70084	.68006	.68400	.68381	.72491	.67951	.69437	.77783	.69958	.80033	.73241	.68159	.70230
hay	.30766	.25393	.37611	.40257	.43699	.49884	.43392	.48642	.66318	.58637	.42702	.42585	.44051	.44326	.38755	.39469	.47135	.51244	.44177	.49644	.70731	.64091	.47186	.46216	.45021	.47207
led	.37781	.38161	.31473	.30732	.38761	.39151	.40268	.39917	.39940	.36116	.19430	.21033	.36150	.35683	.35943	.34806	.10044	.08417	.10678	.09095	.42313	.32743	.46838	.34893	.16567	.15240
lym	.42601	.67340	.63141	.74469	.82884	.77681	.82826	.83758	.56609	.67768	.46657	.61006	.43094	.62664	.62019	.71023	.78529	.82063	.85313	.76616	.84649	.74821	.86535	.76849	.86269	.81147
new	.92136	.90191	.92681	.91663	.95359	.95426	.96344	.96791	.93582	.91561	.89387	.89907	.92411	.92783	.92688	.91072	.95088	.95458	.95802	.96784	.97062	.93702	.97242	.95156	.95867	.96784
nur	.68622	.82019	.78128	.93505	.92819	.93219	.87039	.97209	.76097	.90822	.70998	.85011	.77606	.93379	.76085	.90522	.79085	.94896	.88820	.95389	.75401	.89443	.87093	.94630	.88826	.95382
pag	.77438	.77069	.84224	.82999	.82388	.82885	.83531	.83794	.84258	.82219	.79146	.78194	.67446	.64819	.85868	.83538	.84837	.81233	.84812	.82069	.82244	.80842	.84549	.81940	.82591	.81960
pos	.27086	.37321	.36733	.41424	.30087	.38778	.34922	.39809	.14799	.16712	.28258	.29826	.15800	.13798	.33089	.33258	.35012	.41833	.36088	.45537	.38005	.37504	.39322	.36810	.33989	.36727
sat	.89666	.89485	.89776	.89566	.89470	.89491	.89537	.89562	.90588	.89013	.90409	.89143	.88103	.88036	.91119	.89847	.89484	.89396	.89475	.89437	.92395	.88566	.93767	.89677	.89473	.89453
shu	.90806	.90339	.92476	.91578	.92153	.90639	.91338	.91290	.94088	.92953	.78909	.79205	.68054	.65340	.94547	.92438	.95718	.89667	.95627	.89720	.96443	.94014	.96757	.94423	.91725	.90392
spl	.75501	.75388	.95150	.95039	.92762	.92604	.88897	.88749	.94494	.94046	.92998	.92829	.93596	.93584	.94735	.94378	.94383	.93973	.94157	.93656	.93418	.92903	.95679	.94524	.94142	.93655
thy	.63110	.62318	.71439	.70460	.65428	.65002	.72355	.72390	.76645	.72947	.70954	.74144	.60485	.60856	.74013	.71846	.71419	.71032	.71445	.70980	.80967	.72711	.82667	.73406	.71422	.70980
win	.96693	.95639	.96953	.96864	.97675	.97902	.96873	.96830	.97697	.97377	.97784	.97936	.96046	.96237	.97092	.96864	.96766	.96864	.96922	.96305	.97584	.95678	.97645	.96817	.96503	.96830
wqr	.27219	.26048	.26642	.26630	.26366	.26203	.26730	.27057	.27971	.25127	.27522	.26471	.26803	.27572	.28839	.27026	.27470	.27340	.27574	.27346	.48259	.29551	.47015	.28389	.27221	.27896
wqw	.25953	.28740	.27245	.29200	.27844	.29859	.28116	.30172	.27541	.25573	.26181	.28887	.24076	.25631	.30241	.30478	.28015	.30409	.27935	.30410	.47280	.33644	.44870	.32752	.27962	.30437
yea	.54362	.50864	.53199	.50680	.51334	.48665	.52791	.49510	.59287	.53969	.48039	.46106	.34306	.35289	.57702	.54374	.50572	.48154	.51126	.47625	.69010	.48704	.69541	.48108	.51135	.47604
zoo	.80465	.87127	.78713	.85529	.90736	.89238	.88532	.89048	.86739	.94524	.77468	.73095	.56648	.79076	.83060	.85529	.85616	.83283	.85088	.83283	.88174	.89156	.88122	.85172	.86049	.83283
Avg	.59110	.61865	.62946	.65073	.65617	.66692	.65752	.67576	.65327	.65240	.60578	.62055	.57396	.60639	.65341	.66183	.64503	.65794	.65181	.65707	.74085	.67002	.74185	.67180	.65178	.65691

 

Statistical Study

Introduction to statistical tests for performance comparison

In this paper, we use the hypothesis testing techniques to provide statistical support for the analysis of the results (S. García, A. Fernández, J. Luengo, and F. Herrera, “A study of statistical techniques and performance measures for genetics-based machine learning: Accuracy and interpretability,” Soft Comp., vol. 13, no. 10, pp. 959–977, 2009, D. Sheskin, Handbook of Parametric and Nonparametric Statistical Procedures, 2nd ed. London, U.K.: Chapman & Hall/CRC, 2006.). Specifically, we will use non-parametric tests, due to the fact that the initial conditions that guarantee the reliability of the parametric tests may not be satisfied, causing the statistical analysis to lose credibility with these type of tests (J. Demsar, “Statistical comparisons of classifiers over multiple data sets,” J. Mach. Learn. Res., vol. 7, pp. 1–30, 2006.).

We apply the Wilcoxon signed-rank test (D. Sheskin, Handbook of Parametric and Nonparametric Statistical Procedures, 2nd ed. London, U.K.: Chapman & Hall/CRC, 2006.) as a non-parametric statistical procedure for performing pairwise comparisons between two algorithms, as the analogous of the paired t-test. This procedure computes the differences between the performance scores of the two classifiers on i-th out of N_ds data-sets. The differences are ranked according to their absolute values, from smallest to largest, and average ranks are assigned in case of ties. We call R⁺ the sum of ranks for the data-sets on which the second algorithm outperformed the first, and R^- the sum of ranks for the opposite. Let T be the smallest of the sums, T = min(R⁺,R^-). If T is less than or equal to the value of the distribution of Wilcoxon for N_ds degrees of freedom (Table B.12 in Zar, J. H., 1999. Biostatistical Analysis. Prentice Hall), the null hypothesis of equality of means is rejected.

This statistical test allows us to know whether a hypothesis of comparison of means could be rejected at a specified level of significance α. It is also very interesting to compute the p-value associated to each comparison, which represents the lowest level of significance of a hypothesis that results in a rejection. In this manner, we can know whether two algorithms are significantly different and how different they are.

In addition, we consider the method of aligned ranks of the algorithms in order to show graphically how good a method is with respect to its partners. The first step to compute this ranking is to obtain the average performance of the algorithms in each data set. Next, we compute the subtractions between the accuracy of each algorithm minus the average value for each data-set. Then, we rank all these differences in a descending way and, finally, we average the rankings obtained by each algorithm. In this manner, the algorithm which achieves the lowest average ranking is the best one.

These tests are suggested in the studies presented in (J. Demsar, “Statistical comparisons of classifiers over multiple data sets,” J. Mach. Learn. Res., vol. 7, pp. 1–30, 2006., S. García, A. Fernández, J. Luengo, and F. Herrera, “A study of statistical techniques and performance measures for genetics-based machine learning: Accuracy and interpretability,” Soft Comp., vol. 13, no. 10, pp. 959–977, 2009, S. García and F. Herrera, “An extension on “statistical comparisons of classifiers over multiple data sets for all pairwise comparisons,” J. Mach. Learn. Res., vol. 9, pp. 2677–2694, 2008.), where its use in the field of machine learning is highly recommended. Any interested reader can find additional information on the Website http://sci2s.ugr.es/sicidm/, together with the software for applying the statistical tests.

Study of the use of OVO versus OVA for imbalanced data-sets

In this part of this experimental study, our aim is to analise when the cooperation between the multi-classification approach and preprocessing has a more positive effect, whether for the OVO or OVA scheme. In order to contrast the previous findings, we carry out three different statistical analysis (Wilcoxon tests), one for each learning algorithm. This study is shown in Tables 15 (average accuracy) and 16 (mean f-measure), which are divided into three parts, the first one shows the results for C4.5, the next one for SVM and finally for kNN. For all these tests, we compare OVO and OVA for each preprocessing mechanism, showing the sum of the ranks for the OVO approach in R⁺ and the one for OVA in R^-.

Table 15. Wilcoxon test for the comparison between OVO and OVA approaches with the C4.5, SVM and kNN algorithms according to the average accuracy performance results. R⁺ corresponds to the sum of the ranks for the OVO methodologies and R^- to the OVA ones

Algorithm	Preprocessing	R+ (OVO)	R- (OVA)	p-value
C4.5
	ROS	276.0	24.0	0.000301
	SL	275.0	25.0	0.000336
	SMT-ENN	266.0	34.0	0.000873
	SMT	264.0	36.0	0.00107
	CS	258.0	42.0	0.001935
SVM
	ROS	187.0	113.0	0.283977
	SL	193.5	82.5	0.087314
	SMT-ENN	171.0	129.0	0.539027
	SMT	194.0	106.0	0.203576
	CS	205.0	95.0	0.112804
kNN
	ROS	217.0	83.0	0.053784
	SL	214.0	86.0	0.06535
	SMT-ENN	154.0	146.0	0.897697
	SMT	177.0	123.0	0.432035
	CS	201.0	99.0	0.141175

Table 16. Wilcoxon test for the comparison between OVO and OVA approaches with the C4.5, SVM and kNN algorithms according to the mean f-measure performance results. R⁺ corresponds to the sum of the ranks for the OVO methodologies and R^- to the OVA ones

Algorithm	Preprocessing	R+ (OVO)	R- (OVA)	p-value
C4.5
	ROS	275.0	25.0	0.000336
	SL	262.0	38.0	0.001308
	SMT-ENN	244.0	56.0	0.006934
	SMT	244.0	56.0	0.006934
	CS	251.0	49.0	0.003732
SVM
	ROS	180.0	120.0	0.38352
	SL	206.0	94.0	0.106465
	SMT-ENN	146.0	154.0	0.897697
	SMT	173.0	127.0	0.501948
	CS	206.0	94.0	0.106465
kNN
	ROS	178.0	122.0	0.415481
	SL	159.0	141.0	0.786061
	SMT-ENN	94.0	206.0	0.106465
	SMT	118.0	182.0	0.353111
	CS	161.5	138.5	0.730782

Comparative analysis for pairwise learning with preprocessing/cost sensitive learning and standard approaches in multiple class imbalanced problems

Table 17. Wilcoxon test for the comparison between OVO+preprocessing/CS and the basic approaches for multiple class learning with the C4.5 algorithm according to the average accuracy performance results. R⁺ corresponds to the sum of the ranks for the OVO methodologies and R^- to the standard ones

Algorithm	Preprocessing	R+ OVO	R- Std-Method	p-value
C4.5
	ROS vs. Base	224.0	76.0	0.03329
	ROS vs. Std-OVO	211.0	65.0	0.025385
	ROS vs. Global-CS	160.0	140.0	0.764177
	ROS vs. Static-SMT	238.0	62.0	0.011453
C4.5
	SL vs. Base	209.0	67.0	0.029655
	SL vs. Std-OVO	217.0	59.0	0.015607
	SL vs. Global-CS	148.0	128.0	0.749456
	SL vs. Static-SMT	211.0	89.0	0.078893
C4.5
	SMT-ENN vs. Base	160.0	140.0	0.764177
	SMT-ENN vs. Std-OVO	194.0	106.0	1.0000
	SMT-ENN vs. Global-CS	111.0	189.0	1.0000
	SMT-ENN vs. Static-SMT	157.0	143.0	0.830324
C4.5
	SMT vs. Base	229.0	71.0	0.023121
	SMT vs. Std-OVO	243.0	57.0	0.007553
	SMT vs. Global-CS	192.0	108.0	0.224639
	SMT vs. Static-SMT	223.0	77.0	0.035729
C4.5
	CS vs. Base	210.0	90.0	0.083886
	CS vs. Std-OVO	221.0	79.0	0.041067
	CS vs. Global-CS	143.0	157.0	1.0000
	CS vs. Static-SMT	234.0	66.0	0.015766

 

Table 18. Wilcoxon test for the comparison between OVO+preprocessing/CS and the basic approaches for multiple class learning with the C4.5 algorithm according to the mean f-measure performance results. R⁺ corresponds to the sum of the ranks for the OVO methodologies and R^- to the standard ones

Algorithm	Preprocessing	R+ OVO	R- Std-Method	p-value
C4.5
	ROS vs. Base	221.0	79.0	0.041067
	ROS vs. Std-OVO	228.0	72.0	0.024906
	ROS vs. Global-CS	160.0	140.0	0.764177
	ROS vs. Static-SMT	235.0	65.0	0.014572
C4.5
	SL vs. Base	192.0	108.0	0.224639
	SL vs. Std-OVO	217.0	83.0	0.053784
	SL vs. Global-CS	150.0	150.0	0.988602
	SL vs. Static-SMT	196.0	104.0	0.183989
C4.5
	SMT-ENN vs. Base	124.0	176.0	1.0000
	SMT-ENN vs. Std-OVO	165.0	111.0	0.402924
	SMT-ENN vs. Global-CS	103.0	197.0	1.0000
	SMT-ENN vs. Static-SMT	140.0	160.0	1.0000
C4.5
	SMT vs. Base	203.0	97.0	0.126371
	SMT vs. Std-OVO	252.0	48.0	0.003405
	SMT vs. Global-CS	176.0	124.0	0.448964
	SMT vs. Static-SMT	213.0	87.0	0.069634
C4.5
	CS vs. Base	180.0	96.0	0.196137
	CS vs. Std-OVO	185.0	91.0	0.148539
	CS vs. Global-CS	132.0	144.0	1.0000
	CS vs. Static-SMT	217.0	83.0	0.053784

 

Table 19. Wilcoxon test for the comparison between OVO+preprocessing/CS and the basic approaches for multiple class learning with the SVM algorithm according to the average accuracy performance results. R⁺ corresponds to the sum of the ranks for the OVO methodologies and R^- to the standard ones

Algorithm	Preprocessing	R+ OVO	R- Std-Method	p-value
SVM
	ROS vs. Std-OVO	225.5	74.5	0.029316
	ROS vs. Global-CS	100.0	176.0	1.0000
	ROS vs. Static-SMT	211.5	88.5	0.211326
SVM
	SL vs. Std-OVO	232.0	68.0	0.018416
	SL vs. Global-CS	120.5	179.5	1.0000
	SL vs. Static-SMT	195.5	104.5	0.465099
SVM
	SMT-ENN vs. Std-OVO	222.0	78.0	0.038319
	SMT-ENN vs. Global-CS	92.0	184.0	1.0000
	SMT-ENN vs. Static-SMT	177.0	99.0	0.2296
SVM
	SMT vs. Std-OVO	242.0	58.0	0.008221
	SMT vs. Global-CS	113.5	186.5	1.0000
	SMT vs. Static-SMT	208.0	92.0	0.094637
SVM
	CS vs. Std-OVO	232.0	68.0	0.018416
	CS vs. Global-CS	131.0	169.0	1.0000
	CS vs. Static-SMT	210.0	90.0	0.083886

 

Table 20. Wilcoxon test for the comparison between OVO+preprocessing/CS and the basic approaches for multiple class learning with the SVM algorithm according to the mean f-measure performance results. R⁺ corresponds to the sum of the ranks for the OVO methodologies and R^- to the standard ones

Algorithm	Preprocessing	R+ OVO	R- Std-Method	p-value
SVM
	ROS vs. Std-OVO	140.0	160.0	1.0000
	ROS vs. Global-CS	126.0	150.0	1.0000
	ROS vs. Static-SMT	121.5	178.5	1.0000
SVM
	SL vs. Std-OVO	131.0	169.0	1.0000
	SL vs. Global-CS	142.5	157.5	1.0000
	SL vs. Static-SMT	97.5	178.5	1.0000
SVM
	SMT-ENN vs. Std-OVO	123.0	177.0	1.0000
	SMT-ENN vs. Global-CS	109.0	167.0	1.0000
	SMT-ENN vs. Static-SMT	98.5	201.5	1.0000
SVM
	SMT vs. Std-OVO	148.0	152.0	1.0000
	SMT vs. Global-CS	132.0	144.0	1.0000
	SMT vs. Static-SMT	119.5	180.5	1.0000
SVM
	CS vs. Std-OVO	128.0	148.0	1.0000
	CS vs. Global-CS	144.5	135.5	1.0000
	CS vs. Static-SMT	112.0	164.0	1.0000

 

Table 21. Wilcoxon test for the comparison between OVO+preprocessing/CS and the basic approaches for multiple class learning with the kNN algorithm according to the average accuracy performance results. R⁺ corresponds to the sum of the ranks for the OVO methodologies and R^- to the standard ones

Algorithm	Preprocessing	R+ OVO	R- Std-Method	p-value
kNN
	ROS vs. Base	246.0	54.0	0.005831
	ROS vs. Std-OVO	212.0	64.0	0.023457
	ROS vs. Global-CS	213.0	87.0	0.069634
	ROS vs. Static-SMT	182.0	118.0	0.353111
kNN
	SL vs. Base	249.0	51.0	0.004471
	SL vs. Std-OVO	226.0	74.0	0.028837
	SL vs. Global-CS	226.0	74.0	0.028837
	SL vs. Static-SMT	192.0	108.0	0.224639
kNN
	SMT-ENN vs. Base	226.0	74.0	0.028837
	SMT-ENN vs. Std-OVO	170.0	130.0	0.558068
	SMT-ENN vs. Global-CS	166.0	134.0	0.637335
	SMT-ENN vs. Static-SMT	155.0	145.0	0.875132
kNN
	SMT vs. Base	259.0	41.0	0.001757
	SMT vs. Std-OVO	244.0	56.0	0.006934
	SMT vs. Global-CS	232.0	68.0	0.018416
	SMT vs. Static-SMT	200.0	100.0	0.149061
kNN
	CS vs. Base	233.0	67.0	0.017046
	CS vs. Std-OVO	200.0	100.0	0.149061
	CS vs. Global-CS	192.0	108.0	0.224639
	CS vs. Static-SMT	167.0	133.0	0.617075

 

Table 22. Wilcoxon test for the comparison between OVO+preprocessing/CS and the basic approaches for multiple class learning with the kNN algorithm according to the mean f-measure performance results. R⁺ corresponds to the sum of the ranks for the OVO methodologies and R^- to the standard ones

Algorithm	Preprocessing	R+ OVO	R- Std-Method	p-value
kNN
	ROS vs. Base	231.0	69.0	0.019882
	ROS vs. Std-OVO	146.0	130.0	0.796
	ROS vs. Global-CS	172.0	128.0	0.520317
	ROS vs. Static-SMT	146.0	154.0	1.0000
kNN
	SL vs. Base	235.0	65.0	0.014572
	SL vs. Std-OVO	145.0	155.0	1.0000
	SL vs. Global-CS	177.0	123.0	0.432035
	SL vs. Static-SMT	147.0	153.0	1.0000
kNN
	SMT-ENN vs. Base	185.5	87.5	0.119451
	SMT-ENN vs. Std-OVO	124.0	176.0	1.0000
	SMT-ENN vs. Global-CS	111.0	189.0	1.0000
	SMT-ENN vs. Static-SMT	109.0	191.0	1.0000
kNN
	SMT vs. Base	243.0	57.0	0.007553
	SMT vs. Std-OVO	170.0	130.0	0.558068
	SMT vs. Global-CS	175.0	125.0	0.466264
	SMT vs. Static-SMT	140.0	160.0	1.0000
kNN
	CS vs. Base	212.5	87.5	0.070848
	CS vs. Std-OVO	116.0	184.0	1.0000
	CS vs. Global-CS	147.0	153.0	1.0000
	CS vs. Static-SMT	117.0	183.0	1.0000

---

Page Maintained by A. Fernández