Several ensemble methods of binary classification are presented. They are based on the use of decision theory tools at the stage of aggregating the results of binary classification and obtaining refined solutions to classification problems. Results of software implementation and computational experiments on benchmark instances are presented. The experiment conducted on unbalanced benchmark instances from KEEL-dataset repository demonstrates a noticeable improvement in the quality characteristics of binary classification such as accuracy and balanced accuracy. The presented approach is expected to be promising for complex classification instances such as unbalanced classification ones.
accurate solution to the problem. That is, in this case, the solution accuracy is a higher priority than the resources of computers used. In particular, in supervised machine learning, which deals with two main problems – classification and regression – the direction of the so-called aggregation or ensemble methods has been developed last years, where the same problem is solved in several ways, and then the results obtained are aggregated, and the final solution is formed. In this paper, we will present several ensemble methods for solving the binary classification problem based on the local priority vector, traditionally used in the Analytic Hierarchy Process [8, 9, 10].
It will be shown that these approaches to aggregation are promising and, in some cases, give a significant improvement in the quality of classification compared to the results of applying standard methods of conventional classification.
A classification problem
(CP) [11, 12] is a problem of identifying to which class a new instance belongs based on available class membership for samples in a training set (TS).
Instances
to
which
classification
is
applied
form
a
test
set
(TeS).
represented by a feature tuple, while a class label is unknown and needs to be found.
TS-instance is given by a feature tuple and a class label . At the same time, a TeS-instance is
can
be
a
numeric
vector
but
not
necessarily
since
features
presented
-components characterize certain instance’ properties, categorical, ordinal, integer-valued, or
realvalued. If categorical or ordinal features are present, a preprocessing stage is required to map into
Let us assume that the mapping (
, ∈ ′ . instances’ space into a class label space :
A classification algorithm (CA) is intended to train a classifier , which is a function mapping an
→ ∈ ⊂ ℝ .
TS: {⟨ , ⟩} ∈ ;
TeS: { ′} ∈ ′ , ∶
→ . = { 0, ..., }
= 0
Let be a set of classes. To
we will refer to as an instances’ space and to a set as a class label space (hereafter, 0 = {0, ..., }).
The following division of classification problems (CPs) is common [11, 12, 13, 14]: 1. Depending on the number of classes: a) Binary classification problems (Binary CPs, BCPs) if the number of classes is two, i.e., = 1; cally insignificant; ence is significant. 2. Depending on the proportions of the classes’ sizes: b) Multi-class classification problems (Multiclass CPs, MCPs) if > 1 ; a) Balanced classification problems (BaCPs), if the diference in classes’ sizes is statistib) Imbalanced classification problems (class imbalance problems, ICPs) if this difer
Quality of classification is assessed by diferent metrics [11, 15, 16] such as the accuracy, balanced accuracy, recall, precision, -score, -mean, etc., which utilize a confusion matrix.
A confusion matrix (CM) is a matrix of the dimension + 1. Each its row represents the instances in an actual class (with an actual label), while its column represents the instances in a predicted class (with a predicted label). Namely,
= ( ), ∈ 0 , Let
The number of is called the true prediction of the class ( ∈ 0). label
and a predicted label ). where is a number of instances from an actual class , whose predicted class is (with an actual (7) (8) (9) (10) ′ = ∑ , ∈ ,
0 = ∑ = ′
∑ .
, =0 =0
After replacing by the later becomes = ′ , ∈ 0; = ∑ , ∈ 0. =
∑ , ∈ .
0 satisfies a relation be a distribution of the classes in , where ′ be a class -size. Then the number of all -instances In these notations, the listed above classification metrics are represented as follows. Classification accuracy (accuracy) is calculated as a sum of all true predictions divided by :
is inadequate in reflecting the classifier’s performance on classifying each single class, especially on small classes [17, 16]. That is why, in ICPs, other metrics are more commonly used. Among them are the following two: (F-measure) for a class [18]:
, By themselves, neither of these two characteristics are adequate in reflecting the performance of any are called a recall (the true positive rate, TPR) and a precision of a class , respectively. classifier on the class . Therefore, they are commonly integrated in a metric called the F-score = 2 ⋅ ⋅ + , ∈ .
0 A peculiarity of F-score is that it is high if both the recall and precision are high.
If we are interested in the performances of all classes, the classification performance of each class should be equally represented in the evaluation metric. G-mean [19] is such a measure, which is the geometric mean of recall values of every class:
Another metric is the balanced classification accuracy : The formula (8) can be rewritten as follows: 1 are called a true positive and a false negative for a class , respectively ( ∈ 0).
Note, if ≠ , then the value is an error of prediction for an -instance that it elongs to a class i.e., it is a sum of elements of a CM except for the row
Using this terminology, formulas (7), (8), and (10) become: and column
In these notations, a sum across the whole row is ′ = + . A false positive for , denoted , is a sum of a column excluding . A true negative for is = − ( − − ) If BCPs are solved, a positive class is considered as the main class
= 1 ∑ =0 ; = + = + , ∈ ; , ∈ .
0 0 = 1, a recall, and a precision: and the subindex is omitted in formulas (11)-(15) yielding most common expression for an accuracy, = 1 ( + ) , (11) (12) (13) (14) (15)
Respectively, in these notations, the expressions for , -score, and are as follows: (19) (20) (21) (22) where is on y-axis and FPR is on the x-axis.
AUC (Area Under The Curve) is an area under the ROC curve [21].
Combining classifiers and, as a consequence, combining results of classification, is one of the commonly accepted methods for improving the quality of classification and increasing the reliability of these results [22, 23, 24].
Combining methods are widely used in regression [22] and classification [23, 24] problems. These methods are called ensemble algorithms (EAs). Two subclasses in this group of methods can be singled out – classification EAs ( ECAs) and regression EAs (ERAs).
Collections of EAs used together are called ensemble systems (ESs) [23]. Among them are classification ESs (ECSs) and regression ESs (ERSs). ESs are designed not only for a formation of a collection of predictions obtained in diferent combining ways, but also for analysis and comparison of these results in order to form a single solution to a prediction problem under consideration.
EAs utilize an idea ”the more diverse the training set, base classifiers, and feature set, the better the performance of the ES” [23].
Based on that, in [25], six strategies were described for designing an EAs:
2. diferent parameter choice; 3. diferent architecture; 4. diferent classifiers; 5. diferent training sets; 6. diferent feature sets.
Two of the listed strategies are most commonly used, namely, diferent training sets (also known as Homogeneity Scenario [26] and diferent classifiers (known as Heterogeneity Scenario). Respectively, ESs are divided into homogeneous ESs (HoESs) and heterogeneous ESs (HeESs). Thus, ECSs can be either classification HoESs ( HoECSs) or classification HeESs ( HeECSs).
Further, we will focus on ECSs. Elements of HoECSs and HeECSs we will call homogeneous ECAs (HoECAs) and heterogeneous ECAs (HeECAs), respectively.
In a HoECA, base classifiers are generated from applying a base CA on diferent training sets formed from the original training set. The predicted labels obtained by these classifiers are then combined in final predicted labels of the test set. In this category of ensemble methods are Random Forest, Adaptive Boosting, Bagging, Random Subspace (see [23] and references therein), etc.
In contrast to HoECAs, in a HeECA, diferent CAs are applied on the same training set, thus producing a set of diferent base classifiers, which outputs are called meta-data [27]. Then metadata are combined in final predicted labels obtained as a result of applying this HeECA.
Remark 1. Note that HoECAs involve a large number of diferent ”weak” classifiers. Therefore, a base CA should not be fine-tuned. At the same time, HeECAs commonly utilize a small number of ”strong” classifiers, hence involved base CAs need a preliminary tuning. Both groups of ECAs utilize probabilities, i.e., they deal with probabilistic CAs [13], thus preventing involving deterministic (non-probabilistic) CAs such as SVM, SGB, Kernel Logistic Regression, Logistic Model Trees etc. [28].
HeECAs are also divided into two groups – fixed
HeECAs and trainable HeECAs [23]. The main diference between these two is that, when combining, fixed ones do not take into consideration the label information in the meta-data of training set while trainable methods do.
Fixed HeECAs combines base classifiers’ results by sum, product, min, max, median, majority vote rules etc. [29]. Among trainable HeECAs are the Stacking Algorithm, Inference-based Combiner, Multiple Response Linear Regression, SCANN, Decision Template (see [23] and references therein) and so on. existing ones.
In this research, we set the task of constructing a universal HeECA consisting of fixed and trainable HeECAs and involving deterministic and probabilistic CAs. We expect that using well-known HoECAs along with standard CAs will result in designing a highly strong classifier, which outperforms 2. The proposed heterogeneous ensemble classification system
Let us introduce some notations • = {1, ..., } ,
0 = ∪ {0}; • •
• { } ∈
} { = {
= ∈
{ =
} ′ ′∈ ′
} ′ ′∈ ′
– is a set of base classification algorithms (CAs); – is a set of instances (observations, examples, samples, statistical units);
– is a set of our ensemble classification algorithms (methods) ( EAMs), which is a HeECS (further referred to as an expert assessment based heterogeneous ensemble classification system, a expert assessment based HeECS, EA-HeECS) .
– is a set of our ensemble classification algorithms ( EAMs, ECAs); • ⟨ | ⟩ – is a tuple of observations on samples and their labels: – (explanatory) variables; = ( ) ∈ = ( ) ∈ , ∈ – is a real-valued matrix of observations on independent (23) (24) (25) (26) (27) (28) (29) (30) – ̂ = ( ̂ ) ∈ – is a vector of actual labels thus – is a vector of predicted labels such that
∈ , ∈ .
̂ = ( ) ∈ , ∈ .
• – is a K-fold split of , i.e., it is a partition of into subsets of nearly equal size: The partition (25) induces
pairs of test sets: and training sets: such that = { } ∈ ∶
⋃ = , ∩ ′ = ∅, ∀ ≠ ; where ≈ ′ , ∀ ≠ , = | |, ∈ .
′ ′ =1
, ∈ , , ∈ ,
= { , } ∈ , = { , } ∉ , ∈ , CAs yield predictions of labels, namely,
The collection (26) defines a partition of the dataset ⟨ , a decomposition of the tuple, where each sample ⟨ , ⟩ ∈ ⟨ , ⟩ is presented − 1 times.
⟩. At the same time, the sets (27) defines ′ ̂ , ̂ ′ , ∈ , ∈ , ′ ∈ ′ , will be a predicted label of obtained by ∈ or ′ ∈ − , respectively.
Note that since in CAs classification models are built and optimized on training sets, values are real predictions, while are labels’ predictions are compatible with the actual labels ′ ′ ̂ , ̂ ′ , ∈ , ∈ ,
∈ ′ , ∈ , ̂ , ̂ ′ , ∉ , ∈ ,
∈ ′ , ∈ , ′ ′ , ∉ , ∈ , Therefor, they can be used for evaluating quality of classification on training sets and tuning CAs if necessary.
Let us unite the predictions (29) matrices: = ( ̂
′ ′ ) ∈ , ∈ , = ( ̂ ) ∈ , ′∈ ′
Note that, in ICPs, an imbalanced ratio can be given prior. In this case, is reasonably to use instead of (33).
Also, in some ECAs, weights of CAs playing a role of experts in solving CPs are used. The weights can also be assigned prior, but we will use a posterior information obtained as a result of comparison of (30) with (31). Namely, we introduce vectors of relative weights of CAs for a fold :
The vectors (34) must satisfy the following conditions: on a training set
. where is a weight of a , which depends on a quality of classification achieved by this method = ,
∈ , = ( ) ∈ , ∈ , ≥ 0, ‖ ‖‖ = 1, ∈ .
‖ ‖
‖1 where on a
;
They can be found in diferent ways depending on our preferences, either the accuracy, balanced accuracy, recall, precision, G-mean, F-score, AUC, or another classification measure M we aim to
All these approaches can be combined in the following way. Let be values of AC, BAC, R, P, G-mean, F-score, AUC, and the metric ∈ [0, 1] achieved by a applied be a vector of weights of the listed metrics.
Then the vector (34) is defined as follows: where
1 = ( 1
‖
= ‖‖ 1
= 2 = (
= 1 = (
Fix ∈ and ∈ . To the vector a local priority vector (LPV) [9, 10, 30] is associated such that ̂ = ( ̂
) ∈ , = (
) ∈ , ‖‖‖ ‖‖‖1 = 1. / ′ = ⎨ ( ) ⎪ ⎪ ⎪⎩ 1, ⎧⎪ , if ∈ 1, ′ ∈ 0; otherwise; −1 , if ∈ 0, ′ ∈ 1; (, ′ ∈ ) equal to Remark 2. A vector will have at most 2 diferent coordinates, therefore, in order to find it, an auxiliary vector can be formed with unit coordinates for instances with 0 predicted label and the rest coordinates . Then, this vector needs a normalization yielding a vector satisfying (41) and (42).
Based on an assumption that is an imbalanced ratio for same for training and test sets, we split the test set into classes 0, 1 such that
, i.e., imbalanced ratios are the | 0| = 0, | 1| = 1 ∶ 1 =
⌈ 1 + ⌉ , 0 = − 1. 2.2.1. ECA1 (based on utilizing the geometric mean of expert estimates) The LPVs (40) are combined in the following way: • Find an auxiliary vector
′ ′ 1 = ( 1) ∈
′ ∶ 1 =
( =1 ∏ ) 1/ , ∈ . • Find a threshold value • Assign ′
′ ℎ 1 ∶ 11 ≥ 21 ≥ ... ≥ 1 1 = ℎ 1 > ′ 1+11 ≥ ... ≥ 1
.
′ ′ 2.2.2. ECA2 (based on using the weighted geometric mean of expert estimates) First, we generalize (45), (46) in the following way: ′
′ ℎ ′ ∶ 1 ′ ≥ 2 ′ ≥ ... ≥ ′ ̂ ′ = { 1, ′ ≥ ℎ ′ ; 0, ℎ .
′ ′ 1 ′ = ℎ ′ > ′ 1+1 ′ ≥ ... ≥ ′ ; ′ ( ∈ ) , where ′ ∈ ′ , thus replacing in the formulas the sub-index 1 by ′.
Now, for ECA2, the LPVs (40) are combined using the weights (34), formulas (47), (48) are applied ′ ′ ′ = 3; ′ ′ 4
′ = ( 4) ∈ ′
∶ 4 = ∑ =1 ̂ , ∈ ; ℎ 4 = ℎ 3 = 2 , (45) (46) (47) (48) (49) (50) (51) (52) and the auxiliary vector is ′ = 2, 2.2.3. ECA3 (the majority voting) Here, we first assign then find a vector of votes and a threshold: ′ ′ ′ = 2 = ( 2) ∈ ′
′ • find a vector of weighted votes and a threshold: Let 0 be a set of iterations and ∈
0 be an iteration index,
For the vector (54), constraints similar to (35) hold, namely, be a vector of the weights of CAs for a fold on iteration ( ∈ 0 , ∈ ).
Remark 3. ECA3 and ECA4 can be implemented in a slightly diferent way in a manner of ECA1, ECA2, if the formula (47) is used for deriving ℎ
3 , ℎ 4 instead of (51), (53). 2.2.5. ECA5 (the iterative method of finding experts estimates) Set ′ where vectors , ∈ , are found by (40). • Step 0. Initialization. = 0, all the weights (55) are equal, thus • Step 1. Set = + 1. • Step 2. Find an estimate of on iteration denoted by
in the following way: 2.2.6. ECA5 outline • Input. ∈ , > 0, a matrix (54) (55) (56) (57) (58) ̂ ( ) = ( ̂ ( )
) ∈ ̂ ( ) = −1.
( ) = ( ̂ ( ) )
( ), = ( ( ))−1 ( ) ̂ ( ). • Step 3. A vector is evaluated based on −1
for those ∈
, whose vectors of estimates ̂ of CAs. For that, an auxiliary parameter
in a such a way that its components increases are closer to (57), and become lower for the rest (58): where ∈ ℝ is a vector of units, is calculated first. Then is found with the help of (57), • Step 4. If the given accuracy is not achieved yet, i.e., ‖ ‖ ( ) − ̂ ( −1)‖ ‖ ̂ ‖ ‖ ‖ ̂ ( −1)‖ ‖1
‖1 > , then go to Step 1. Otherwise, set = and terminate.
• Outputs are: Then (47), (48) are applied.
To an approach of assigning the CAs’ weights described earlier in this section, where the whole training set
is used for that, we will refer to as Approach 1 (A1). Another approach to assign weights of CAs, that can be uses in ECAs (further referred to as Approach 2, A2), is based on an observation that, to be more realistic, it might be beneficial to split, in addition, the training sets (27) into auxiliary test and training sets: ′
′ , ∶
′ ′ ∪ = , ′
′ ∩ = ∅, ∈ , by for instance, making a 10%/90% split, additionally perform training on weights depending on the quality of classification achieved on ′ . In this case, (34) is replaced ′ , and then assign the ′ ′ = ( Now, for Approach 2, the formula (36) becomes: on an auxiliary training set ′ .
, which reflects a quality of classification reached on the auxiliary test 4, which use the weights of CAs, can be adapted to usage of (64), namely, (49) ′ ′ ′ 2 = ( 2) ∈ ′ ′ 4 = ( 4) ∈
′
Remark 4. We will refer to these modifications as
For validating of the proposed ensemble approaches, 7 conventional classification algorithms implemented in R were selected: 1. Linear Logistic Regression (GLM) [31]; 2. k-Nearest Neighbors (KNN) [32]; 3. Linear Support Vector Machine (SVM) [33]; 4. Kernel SVM (KSVM) [34]; 5. Naive Bayes (NB) [35]; 6. Decision Tree (DT) – C4.5 [36], CART [2]; 7. Random Forest (RF) [2] and 2 unbalanced benchmark instances from KEEL–dataset repository [37] were used – Pima Indians Diabetes (Pima) and Haberman Breast Cancer (Haberman) for which standard classification algorithm gives rather low quality – accuracy around 70%.
As a result of application of our ensemble approaches, accuracy and balanced accuracy was improved by 1% and 6%, respectively. The best method is ECA2.
Acknowledgments In this paper, we ofer new ensemble methods for binary classification which use Decision Theory tools for combining conventional classifiers’ results. Our aggregative techniques work better on datasets, where standard methods are weak such as Haberman and Pima. Thus, the proposed approaches are promising for application in complex real-world classification problems. The work was partially supported by Beethoven Grant No. DFG NCN 2016/23/G/ST1/04083. [6] L. Kirichenko, O. Pichugina, T. Radivilova, K. Pavlenko, Application of wavelet transform for machine learning classification of time series, in: S. Babichev, V. Lytvynenko (Eds.), Lecture Notes in Data Engineering, Computational Intelligence, and Decision Making, Lecture Notes on Data Engineering and Communications Technologies, Springer International Publishing, 2023, pp. 547–563. doi:10.1007/978-3-031-16203-9_31. [7] L. Kirichenko, O. Pichugina, H. Zinchenko, Clustering time series of complex dynamics by features, in: Selected Papers of the VIII International Scientific Conference “Information Technology and Implementation" (IT&I-2021). Conference Proceedings, volume 3132 of CEUR Workshop Proceedings, 2021, pp. 83–93. ISSN: 1613-0073. [8] O. Pichugina, Decision Making Tools For Choice Software Development Environment, in: 2020 IEEE KhPI Week on Advanced Technology (KhPIWeek), 2020, pp. 450–454. doi:10.1109/ KhPIWeek51551.2020.9250109. [9] T. L. Saaty, J. M. Alexander, Conflict Resolution: The Analytic Hierachy Approach, Praeger Pub,
New York, 1989. [10] T. L. Saaty, Analytic Hierarchy Process, in: S. I. Gass, M. C. Fu (Eds.), Encyclopedia of Operations Research and Management Science, Springer US, 2013, pp. 52–64. doi:10.1007/ 978-1-4419-1153-7_31. [11] C. Drummond, Classification, in: C. Sammut, G. I. Webb (Eds.), Encyclopedia of Machine Learning, Springer US, Boston, MA, 2010, pp. 168–171. doi:10.1007/978-0-387-30164-8_111. [12] E. Alpaydin, Introduction to machine learning, Adaptive computation and machine learning, 2nd ed., MIT Press, Cambridge, Mass, 2010. OCLC: ocn317698631. [13] C. C. Aggarwal, Data Classification: Algorithms and Applications, 1st ed., Chapman & Hall/CRC, 2014. [14] N. Japkowicz, S. Stephen, The class imbalance problem: A systematic study, Intelligent Data
Analysis (2002) 429–449. [15] I. H. Witten, E. Frank, M. A. Hall, C. J. Pal, Data Mining: Practical Machine Learning Tools and
Techniques, 4th ed., Morgan Kaufmann, Amsterdam, 2016. [16] Y. Sun, M. S. Kamel, Y. Wang, Boosting for Learning Multiple Classes with Imbalanced Class Distribution, in: Sixth International Conference on Data Mining (ICDM’06), 2006, pp. 592–602. doi:10.1109/ICDM.2006.29, iSSN: 2374-8486. [17] C. Drummond, R. C. Holte, Severe Class Imbalance: Why Better Algorithms Aren’t the Answer, in: J. Gama, R. Camacho, P. B. Brazdil, A. M. Jorge, L. Torgo (Eds.), Machine Learning: ECML 2005, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 2005, pp. 539– 546. doi:10.1007/11564096_52. [18] D. Lewis, W. A. Gale, Training text classifiers by uncertainty sampling, in: Proceedings of the Seventeenth Annual International ACM SIGIR Conference on Research and Development in Information, NY, New York, 1998, pp. 73– 79. URL: /paper/Training-text-classifiers-by-uncertainty-sampling-Lewis-Gale/ d9d4c586b985af2ec42e4fec24cd1806d9aefaf. [19] M. Kubat, R. C. Holte, S. Matwin, Machine Learning for the Detection of Oil Spills in Satellite
Radar Images, Machine Learning 30 (1998) 195–215. doi:10.1023/A:1007452223027. [20] L. Abdi, S. Hashemi, To combat multi-class imbalanced problems by means of oversampling and boosting techniques, Soft Computing 19 (2015) 3369–3385. doi:10.1007/ s00500-014-1291-z. [21] A. P. Bradley, The use of the area under the ROC curve in the evaluation of machine learning algorithms, Pattern Recognition 30 (1997) 1145–1159. doi:10.1016/S0031-3203(96)00142-2. [22] L. Abdi, S. Hashemi, To Combat Multi-Class Imbalanced Problems by Means of Over-Sampling