The paper briey introduces multiple classier systems and describes a new algorithm, which improves classication accuracy by means of recommendation of a proper algorithm to an object classication. This recommendation is done assuming that a classier is likely to predict the label of the object correctly if it has correctly classied its neighbors. The process of assigning a classier to each object is based on Formal Concept Analysis. We explain the idea of the algorithm with a toy example and describe our rst experiments with real-world datasets.
The topic of Multiple Classier Systems (MCSs) is well studied in machine
learning community [
The underlying idea of all these systems is to train several (base) classiers
on a training set and to combine their predictions in order to classify objects
from a test set [
Among the most popular MCSs are bagging [
In this paper, we present one more algorithm of such type Recommenderbased Multiple Classier System (RMCS). Here the underlying proposition is that a classier is likely to predict the label of the object from a test set correctly if it has correctly classied its neighbors from a training set.
The paper is organized as follows. In chapter 2, we discuss bagging, boosting and stacking. In Section 3, we introduce basic denitions of Formal Concept Analysis (FCA). Section 4 provides an example of execution of the proposed RMCS algorithm on a toy synthetic dataset. Then, Section 5 describes the RMCS algorithm itself. Further, the results of the experiments with real data are presented. Section 7 concludes the paper. 2
In this chapter, we consider several well-known multiple classier systems. 2.1
The bootstrap sampling technique has been used in statistics for many years. Bootstrap aggregating , or bagging, is one of the applications of bootstrap sampling in machine learning. As suciently large data sets are often expensive or impossible to obtain, with bootstrap sampling, multiple random samples are created from the source data by sampling with replacement. Samples may overlap or contain duplicate items, yet the combined results are usually more accurate than a single sampling of the entire source data achieves.
In machine learning the bootstrap samples are often used to train classiers. Each of these classiers can classify new instances making a prediction; then predictions are combined to obtain a nal classication.
The aggregation step of bagging is only helpful if the classiers are dierent.
This only happens if small changes in the training data can result in large changes
in the resulting classier that is, if the learning method is unstable [
The idea of boosting is to iteratively train classiers with a weak learner (the
one with error better than 50% but worse than 0%) [
Boosting was originally proposed by Schapire and Freund [
Freund and Schapire proved that, if the base classier used by AdaBoost
has an error rate of just slightly less than 50%, the training error of the
metaclassier will approach zero exponentially fast [
In stacked generalization , or stacking, each individual classier is called a
level-0 model. Each may vote, or may have its output sent to a level-1 model
another classier that tries to learn which level-0 models are most reliable.
Level-1 models are usually more accurate than simple voting, provided they are
given the class probability distributions from the level-0 models and not just the
single predicted class [
A formal context in FCA is a triple K = (G; M; I), where G is a set of objects, M is a set of attributes, and the binary relation I G M shows which object possesses which attribute. gIm denotes that object g has attribute m. For subsets of objects and attributes A G and B M Galois operators are dened as follows:
A0 = fm 2 M j gIm 8g 2 Ag;
B0 = fg 2 G j gIm 8m 2 Bg:
A pair (A; B) such that A G; B M; A0 = B and B0 = A, is called a formal
concept of a context K. The sets A and B are closed and called the extent and
the intent of a formal concept (A; B) respectively. For the set of objects A the
set of their common attributes A0 describes the similarity of objects of the set
A and the closed set A00 is a cluster of similar objects (with the set of common
attributes A0) [
The number of formal concepts of a context K = (G; M; I) can be quite large
(2minfjGj;jMjg in the worst case), and the problem of computing this number
is #P-complete [
For a context (G; M; I), a concept X = (A; B) is less general than or equal
to a concept Y = (C; D) (or X Y ) if A C or, equivalently, D B.
For two concepts X and Y such that X Y and there is no concept Z with
Z 6= X; Z 6= Y; X Z Y , the concept X is called a lower neighbor of Y , and Y
is called an upper neighbor of X. This relationship is denoted by X Y . Formal
concepts, ordered by this relationship, form a complete concept lattice which
might be represented by a Hasse diagram [
One can address to [
However, in some applications there is no need to nd all formal concepts of a
formal context or to build the whole concept lattice. Concept lattices, restricted
to include only concepts with frequent intents, are called iceberg lattices. They
were shown to serve as a condensed representation of association rules and
frequent itemsets in data mining [
Here we modied the Close by One algorithm slightly in order to obtain only the upper-most concept of a formal context and its lower neighbors. The description of the algorithm and details of its modication is beyond the scope of this paper. 4
Let us demonstrate the way RMCS works with a toy synthetic dataset shown in Table 1. We consider a binary classication problem with 8 objects comprising a training set and 2 objects in a test set. Each object has 4 binary attributes and a target attribute (class). Suppose we train 4 classiers on this data and try to predict labels for objects 9 and 10.
Using FCA terms, we denote by G = f1; 2; 3; 4; 5; 6; 7; 8; 9; 10g the whole set of objects, Gtest = f9; 10g the test set, Gtrain = GnGtest the training set, M = fm1; m2; m3; m4g the attribute set, C = fcl1; cl2; cl3; cl4g the set of classiers.
Here we run leave-one-out cross-validation on this training set for 4 classiers. Further, we ll in Table 2, where a cross for object i and classier clj means that clj correctly classies object i in the process of cross-validation. To clarify, a cross for object 3 and classier cl4 means that after being trained on the whole training set but object 3 (i.e. on objects f1; 2; 4; 5; 6; 7; 8g), classier cl4 correctly predicted the label of object 3.
Let us consider Table 2 as a formal context with objects G and attributes C (so now classiers play the role of attributes). We refer to it as classication context. The concept lattice for this context is presented in Fig. 1.
As it was mentioned, the number of formal concepts of a context K = (G; M; I) can be exponential in the worst case. But for the toy example it is possible to draw the whole lattice diagram. Thankfully, we do not need to build the whole lattice in RMCS algorithm we only keep track of its top concepts.
Here are these top concepts: (G; ;), (f1; 3; 5; 6g; fcl1g), (f2; 4; 5; 6; 7; 8g; fcl2g), (f1; 2; 4; 8g; fcl3g), (f1; 3; 6; 7; 8g; fcl4g).
To classify objects from Gtest, we rst nd their k nearest neighbors from Gtrain according to some distance metric. In this case, we use k = 3 and Hamming distance. In these conditions, we nd that three nearest neighbors of object 9 are 4, 5 and 7, while those of object 10 are 1, 6 and 8.
Then, we take these sets of nearest neighbors N eighb9 = f4; 5; 7g and N ieghb10 = f1; 6; 8g, and nd maximal intersections of these sets with the extents of formal concepts presented above (ignoring the concept (G; ;)). The intents (i.e. classiers) of the corresponding concepts are given as recommendations for the objects from Gtest. The procedure is summarized in Table 3.
Finally, the RMCS algorithm predicts the same labels for objects 9 and 10 as classiers cl2 and cl4 do correspondingly.
Lastly, let us make the following remarks: 1. We would not have ignored the upper-most concept with extent G if it did not have an empty intent. That is, if we had the top concept of the classication context in a form (G; fclj g) it would mean that clj correctly classied all objects from the training set and we would therefore recommend it to the objects from the test set. 2. One more situation might occur that two or more classiers turn out to be equally good at classifying objects from Gtrain. That would mean that the corresponding columns in classication table are identical and, therefore, the intent of some classication concept is comprised of more than one classier. In such case, we do not have any argument for preferring one classier to another and, hence, the nal label would be dened as a result of voting procedure among the predicted labels of these classiers. 3. Here we considered an input dataset with binary attributes and a binary target class. However, the idea of the RMCS algorithm is still applicable for datasets with numeric attributes and multi-class classication problems. 5
Recommender-based Multiple Classier System
In this section, we discuss the Recommender-based Multiple Classier System (RMCS). The pseudocode of the RMCS algorithm is presented in the listing Algorithm 1.
The inputs for the algorithm are the following: 1. fXtrain; ytraing is a training set,
Xtest is a test set; 2. C = fcl1; cl2; :::; clK g is a set of K base classiers. The algorithm is intended to perform a classication accuracy exceeding those of base classiers; 3. dist(x1; x2) is a distance function for objects which is dened in the attribute space. This might be the Minkowski (including Hamming and Euclidean) distance, the distance weighted by attribute importance and others. 4. k; n_f old are parameters. Their meaning is explained below; 5. topCbO(context) is a function for building the upper-most concept of a formal context and its lower neighbors. Actually, it is not an input for the algorithm but RMCS uses it.
1. Cross-validation on the training set. All K classiers are trained on n_f olds 1 folds of Xtrain. Then a classication table (or context) is formed where a cross is put for object i and classier clj if clj correctly classies object i after training on n_f olds 1 folds (where object i belongs to the rest fold); 2. Running base classiers. All K classiers are trained on the whole Xtrain.
Then, a table of predictions is formed where (i; j) position keeps the predicted label for object i from Xtest by classier clj ; 3. Building top formal concepts of the classication context. The topCbO algorithm is run in order to build upper formal concepts of a classication context. These concepts have the largest possible number of objects in extents and minimal possible number of classiers in their intents (not counting the upper-most concept); 4. Finding neighbors of the objects from Xtest. The objects from the test set are processed one by one. For every object from Xtest we nd its k nearest neighbors from Xtrain according to the selected metric sim(x1; x2). Let us say these k objects form a set N eighbors. Then, we search for a concept of a classication context which extent yields maximal intersection with the set N eighbors. If the intent of the upper-most concept is an empty set (i.e., no classier correctly predicted the labels of all objects from Xtrain, which is mostly the case), then the upper-most concept (G; ;) is ignored. Thus, we select a classication concept, and its intent is a set of classiers Csel; 5. Classication. If Csel consists of just one classier, we predict the same label for the current object from Xtest as this classier does. If there are several selected classiers, then the predicted label is dened by majority rule. 6
The algorithm, described above, was implemented in Python 2.7.3 and tested on a 2-processor machine (Core i3-370M, 2.4 HGz) with 3.87 GB RAM.
We used four UCI datasets in these experiments - mushrooms, ionosphere, digits, and nursery.1 Each of the datasets was divided into training and test sets in proportion 70:30.
Algorithm 1 Recommender-based Multiple Classier System Input: fXtrain; ytraing; Xtest are training and test sets, C = fcl1; cl2; :::; clK g is a set of base classiers, topCbO(context; n) is a function for building the uppermost concept of a formal context and its lower neighbors, dist(x1; x2) is a distance function dened in the attribute space, k is a parameter (the number of neighbors), n_f old is the number of folds for cross-validation on a training set Output: ytest are predicted labels for objects from Xtest train_class_context = [ ][ ] is a 2-D array test_class_context = [ ][ ] is a 2-D array for i 2 0 : : : len(Xtrain) 1 do for cl 2 0 : : : len(C) 1 do train classier cl on (n_f old 1) folds not including object Xtrain[i] pred = predicted label for Xtrain[i] by classier cl train_class_context[i][cl] = (pred == ytrain[i]) end for end for for cl 2 0 : : : len(C) 1 do train classier cl on the whole Xtrain pred = predicted labels for Xtest by classier cl test_class_context[:][cl] = pred end for top_concepts = topCbO(class_context) for i 2 0 : : : len(Xtest) 1 do
N eighbors = k nearest neighbors of Xtest[i] from Xtrain according to sim(x1; x2) concept = argmax(c:extent \ N eighbors); c 2 top_concepts Csel = concept:intent labels = predictions for Xtest[i] made by classiers from Csel ytest[i] = argmax(count_f req(labels)) end for
We ran 3 classiers implemented in SCIKIT-LEARN library 2(written in Python) which served as base classiers for the RMCS algorithm as well. These were a Support Vector Machine with Gaussian kernel ( svm.SVC() in Scikit), logistic regression ( sklearn.linear_model.LogisticRegression() ) and k Nearest Neighbors classier ( sklearn.neighbors.classification.
KNeighborsClassifier() ).
The classication accuracy of each classier on each dataset is presented in Table 4 along with special settings of parameters. Moreover, for comparison, the results for Scikit’s implementation of bagging with SVM as a base classier and AdaBoost on decision stumps 3 are presented.
As we can see, RMCS outperformed its base classiers in all cases, while it turned out to be better than bagging only in case of multi-class classication problems (datasets digits and nursery). 7
In this paper, we described the underlying idea of multiple classier systems, discussed bagging, boosting and stacking. Then, we proposed a multiple classier system which turned out to outperform its base classiers and two particular implementations of bagging and AdaBoost in two multi-class classication problems.
Our further work on the algorithm will continue in the following directions: exploring the impact of dierent distance metrics (such as the one based on attribute importance or information gain) on the algorithm’s performance, experimenting with various types of base classiers, investigating the conditions preferable for RMCS (in particular, when it outperforms bagging and boosting), improving execution time of the algorithm and analyzing RMCS’s overtting.
Acknowledgements. The authors would like to thank their colleague from Higher School of Economics, Sergei Kuznetsov, Jaume Baixeries and Konstantin Vorontsov for their inspirational discussions which directly or implicitly inuenced this study.