Computer Science
Computer Science-2021.gz:143453
Computer Science
315455bbcc69ae5edc8652d8571d76b1e22b15d9
Soft Confusion Matrix Classifier for Stream Classification

In this paper, the issue of tailoring the soft confusion matrix (SCM) based classifier to deal with stream learning task is addressed. The main goal of the work is to develop a wrapping-classifier that allows incremental learning to classifiers that are unable to learn incrementally. The goal is achieved by making two improvements in the previously developed SCM classifier. The first one is aimed at reducing the computational cost of the SCM classifier. To do so, the definition of the fuzzy neighborhood of an object is changed. The second one is aimed at effective dealing with the concept drift. This is done by employing the ADWIN-driven concept drift detector that is not only used to detect the drift but also to control the size of the neighbourhood. The obtained experimental results show that the proposed approach significantly outperforms the reference methods.


Introduction
Classification of streaming data is one of the most difficult problems in modern pattern recognition theory and practice. This is due to the fact that a typical data stream is characterized by several features that significantly impede making the correct classification decision. These features include: continuous flow, huge data volume, rapid arrival rate, and susceptibility to change [19]. If a streaming data classifier aspires to practical applications, it must face these requirements and have to satisfy numerous constraints (e.g. bounded memory, single-pass, realtime response, change of data concept) to an acceptable extent. It is not easy, that is why the methodology of recognizing stream data has been developing very intensively for over two decades, proposing new, more and more perfect classification methods [9,24].
Incremental learning is a vital capability for classifiers used in stream data classification [27]. It allows the classifier to utilize new objects generated by the stream to improve the model built so far. It also allows, to some extent, dealing with the concept drift. Some of the well-known classifiers are naturally capable to be trained iteratively. Examples of such classifiers are neural networks, nearest neighbours classifiers, or probabilistic methods such as the naive Bayes classifier [11]. Some of the classifiers were tailored to be learned incrementally. An example of such a method is well-known Hoeffding Tree classifier [26]. Those types of classifiers can be easily used in stream classification systems. On the other hand, when a classifier is unable to learn in an incremental way, the options for using for stream classification are very limited [27]. Only one option is to keep a set of objects and rebuild the classifier from scratch whenever it is necessary [11].
To bridge this gap, we propose a wrapping-classifier-based on the soft confusion matrix approach (SCM). The wrapping-classifier may be used to add incremental learning functionality to any batch classifier. The classifier based on the idea of soft confusion matrix has been proposed in [30]. It proved to be an efficient tool for solving such practical problems as hand gesture recognition [22]. An additional advantage in solving the above-mentioned classification problem is the ability to use imprecise feedback information about a class assignment. The SCM-based algorithm was also successfully used in multilabel learning [31].
Dealing with the concept drift using incremental learning only is insufficient. This is because the incremental classifiers deal effectively only with the incremental drift [9]. To handle the sudden concept drift, additional mechanism such as single/multiple window approach [21], forgetting mechanisms [33], drift detectors [2] must be used. In this study, we decided to use ADWIN algorithm [2] to detect the drift and to manage the set of stored objects. We use the ADWINbased detector because this approach was shown to be an effective method [13,1].
The concept drift may also be dealt with using ensemble classifiers [9]. There are a plethora of ensemble-based approaches [12,4,19] however, in this work we are focused on single-classifier-based systems.
The rest of the paper is organized as follows. Section 2 presents the corrected classifier and gives insight into its two-level structure and the original concepts of RRC and SCM which are the basis of its construction. Section 3 describes the adopted model of concept drifting data stream and provides details of chunkbased learning scheme of base classifiers and online dynamic learning of the correcting procedure and describes the method of combining ensemble members. In section 4 the description of the experimental procedure is given. The results are presented and discussed in section 5. Section 6 concludes the paper.

Preliminaries
Let us consider the pattern recognition problem in which x ∈ X denotes a feature vector of an object and j ∈ M is its class number (X ⊆ d and M = {1, 2, . . . , M } are feature space and set of class numbers, respectively). Let ψ(L) be a classifier trained on the learning set L, which assigns a class number i to the recognized object. We assume that ψ(L) is described by the canonical model [20], i.e. for given x it first produces values of normalized classification functions (supports) g i (x), i ∈ M (g i (x) ∈ [0, 1], g i (x) = 1) and then classify object according to the maximum support rule: To recognize the object x we will apply the original procedure, which using additional information about the local (relative to x) properties of ψ(L) can change its decision to increase the chance of correct classification of x.
The proposed correcting procedure which has the form of classifier ψ (Corr) (L, V) built over ψ(L) will be called a wrapping-classifier. The wrapping classifier ψ (Corr) (L, V) acts according to the following Bayes scheme: where a posteriori probabilities P (k|x), k ∈ M can be expressed in a form depending on the probabilistic properties of classifier ψ(L): P (j|i, x) denotes the probability that x belongs to the j-th class given that ψ(L, x) = i and P (i|x) = P (ψ(L, x) = i) is the probability of assigning x to class i by ψ(L) Since for deterministic classifier ψ(L) both above probabilities are equal to 0 or 1 we will use two concepts for their approximate calculation: randomized reference classifier (RRC) and soft confusion matrix (SCM).

Randomized Reference Classifier (RRC)
RRC is a randomized model of classifier ψ(L) and with its help the probabilities P (ψ(L, x) = i) are calculated. RRC ψ RRC as a probabilistic classifier is defined by a probability distribution over the set of class labels M. Its classifying functions {δ j (x)} j∈M are observed values of random variables {∆ j (x)} j∈M that meet -in addition to the normalizing conditions -the following condition: where E is the expected value operator. Formula (4) denotes that ψ RRC actson average -as the modeled classifier ψ(L), hence the following approximation is fully justified: where can be easily determined if we assume -as in the original work of Woloszynski and Kurzynski [32] -that ∆ i (x) follows the beta distribution.

Soft Confusion Matrix (SCM)
SCM will be used to determine the assessment of probability P (j|i, x) which denotes class-dependent probabilities of the correct classification (for i = j) and the misclassification (for i = j) of ψ(L, x) at the point x. The method defines the neighborhood of the point x containing validation objects in terms of fuzzy sets allowing for flexible selection of membership functions and assigning weights to individual validation objects dependent on distance from x. The SCM providing an image of the classifier local (relative to x) probabilities P (j|i, x), is in the form of two-dimensional table, in which the rows correspond to the true classes while the columns correspond to the outcomes of the classifier ψ(L), as it is shown in Table 1. Table 1. The soft confusion matrix of classifier ψ(L) The value ε i,j (x) is determined from validation set V and is defined as the following ratio: where V j , D i and N (x) are fuzzy sets specified in the validation set V and | · | denotes the cardinality of a fuzzy set [7]. The set V j denotes the set of validation objects from the j-th class. Formulating this set in terms of fuzzy sets theory it can be assumed that the grade of membership of validation object x V to V j is the class indicator which leads to the following definition of V j : The concept of fuzzy set D i is defined as follows: where P (i|x V ) is calculated according to (5) and (6). Formula (10) demonstrates that the membership of validation object x V to the set D i is not determined by the decision of classifier ψ(L). The grade of membership of object x V to D i depends on the potential chance of classifying x V to the i-th class by the classifier ψ(L). We assume, that this potential chance is equal to the probability P (i|x V ) = P (ψ(L, x V ) = i) calculated approximately using the randomized model RRC of classifier ψ(L). Set N (x) plays the crucial role in the proposed concept of SCM, because it decides which validation objects x V and with which weights will be involved in determining the local properties of the classifier ψ(L) and -as a consequencein the procedure of correcting its classifying decision. Formally, N (x) is also a fuzzy set: but its membership function is not defined univocally because it depends on many circumstances. By choosing the shape of the membership function µ N (x) we can freely model the adopted concept of "locality" (relative to x). µ N (x) (x V ) depends on the distance between validation object x V and test object x: its value is equal to 1 for x V = x and decreases with increasing the distance between x V and x. This leads to the following form of the proposed membership function of the set: · denotes Euclidean distance in the feature space X , K d is the Euclidean distance between x and the K-th nearest neighbor in V, β ∈ + and C is a normalizing coefficient. The first factor in (12) limits the concept of "locality" (relatively to x) to the set of K nearest neighbors with Gaussian model of membership grade.
Since under the stream classification framework, there should be only one pass over the data [19], K and β parameters cannot be found using the extensive grid search approach just like it was for the originally proposed approach [30,22]. Consequently, in this work, we decided to set β to 1. Additionally, the initial number of nearest neighbours is found using a simple rule of thumb [6]: To avoid ties, the final number of neighbours K is set as follows: Additionally, the computational cost of computing the neighbourhood may be further reduced by using the kd-tree algorithm to find the nearest neighbours [18]. Finally, from (8), (10) and (11) we get the following approximation: which together with (3), (5) and (6) give (2) i.e. the corrected classifier ψ Corr (L, V).

Creating the validation set
In this section, the procedure of creating the validation set V from the training L is described. In the original work describing SCM [30], the set of labelled data was wplit into the learning set L and the validation set V. The learning set and the validation set were disjoint L ∩ V = ∅. The cardinality of the validation set was controlled by the γ parameter |V| = γ|L|, γ ∈ [0, 1]. The γ coefficient was usualy set to 0.6, however to achieve the highest classification quality, it should be determined using the grid-search procedure. As it was said above, in this work we want to avoid using the grid-search procedure. Therefore, we construct the validation set using three-fold cross-validation procedure that allows using of the entire learning set as a validation set. The procedure is described in Algorithm 1. Learn the ψ(L k ) using L k ; Update the class-specific decision sets Di using predictions of ψ(L k ) for instances from V k (see (10)); Learn the ψ(L) using L; 9 end

Classification of Data Stream
The main goal of the work is to develop a wrapping-classifier that allows incremental learning to classifiers that are unable to learn incrementally. In this section, we describe the incremental learning procedure used by the SCM-based wrapping-classifier.

Model of Data Stream
We assume that instances from a data stream S appear as a sequence of labeled examples {(x t , j t )}, t = 1, 2, ..., T , where x t ∈ X ⊆ d represents a d-dimensional feature vector of an object that arrived at time t and j t ∈ M = {1, 2, . . . , M } is its class number. In this study we consider a completely supervised learning approach which means that the true class number j t is available after the arrival of the object x t and before the arrival of the next object x t+1 and this information may be used by classifier for classification of x t+1 . Such a framework is one of the most often considered in the related literature [3,25].
In addition, we assume that a data stream can be generated with a timevarying distribution, yielding the phenomenon of concept drift [9]. We do not impose any restrictions on the concept drift. It can be real drift referring to changes of class distribution or virtual drift referring to the distribution of features. We allow sudden, incremental, gradual, and recurrent changes in the distribution of instances creating a data stream. Changes in the distribution can cause an imbalanced class system to appear in a changing configuration.

Incremental learning for SCM classifier
We assumed that the base classifier ψ(L) wrapped by the SCM classifier is unable to learn incrementally. Consequently, an initial training set has to be used to build the classifier. This initial data set is called an initial chunk B. The desired size of the initial bath is denoted by |B des |. The initial data set is built by storing incoming examples from the data stream. By the time the initial batch is collected, the prediction is impossible. Until then, the prediction is made on the basis of a priori probabilities estimated from the incomplete initial batch.
Since ψ(L) is unable to learn incrementally, incremental learning is handled with changing the validation set. Incoming instances are added to the validation set until the ADWIN-based drift detector detects that the concept drift has occurred. The ADWIN-based drift detector analyses the outcomes of the corrected classifier for the instances stored in the validation set [2]. When there is a significant difference between the older and the newer part of the validation set, the detector removes the older part of the validation set. The remaining part of the validation set is then used to correct the outcome of ψ(L). The ADWINbased drift detector also controls the size of the neighbourhood. Even if there is no concept drift, the detector may detect the deterioration of the classification quality when the neighbourhood becomes too large.
The detailed procedure of the ensemble building is described in Algorithms 2 and 3.

Experimental Setup
To validate the classification quality obtained by the proposed approaches, the experimental evaluation, which setup is described below, is performed.
The classifiers implemented in WEKA framework [15] were used. If not stated otherwise, the classifier parameters were set to their defaults. We have chosen the classifiers that offer both batch and incremental learning procedures.
The experimental code was implemented using WEKA [15] framework. The source code of the algorithms is available online 1 2 .
During the experimental evaluation, the following classifiers were compared: 1. ψ B -The ADWIN-driven classifier created using the unmodified base classifier (The base classifier is able to update incrementally.) [2]. 2. ψ nB -The ADWIN-driven created using the unmodified base classifier with the incremental learning disabled. The base classifier is only retrained whenever ADWIN-based detector detects concept drift. 3. ψ S -The ADWIN-driven approach using SCM correction scheme with onlinelearning. As described in Section 3. 4. ψ nS -The ADWIN-driven approach created using SCM correction scheme but the online-learning is disabled. The SCM-corrected classifier is only retrained whenever ADWIN-based detector detects concept drift.
To evaluate the proposed methods, the following classification-loss criteria are used [29]: Macro-averaged FDR (1-precision), FNR (1-recall), Matthews correlation coefficient (MCC). The Matthews coefficient is rescaled in such a way that 0 is perfect classification and 1 is the worst one. Quality measures from the macro-averaging group are considered because this kind of measures is more sensitive to the performance for minority classes. For many real-world classification problems, the minority class is the class that attracts the most attention [23].
Following the recommendations of [5] and [10], the statistical significance of the obtained results was assessed using the two-step procedure. The first step is to perform the Friedman test [5] for each quality criterion separately. Since multiple criteria were employed, the familywise errors (FWER) should be controlled [17]. To do so, the Holm [17] procedure of controlling FWER of the conducted Friedman tests was employed. When the Friedman test shows that there is a significant difference within the group of classifiers, the pairwise tests using the Wilcoxon signed-rank test [5] were employed. To control FWER of the Wilcoxon-testing procedure, the Holm approach was employed [17]. For all tests, the significance level was set to α = 0.01.
Datasets used in this experiment are available online 4 To examine the effectiveness of the incremental update algorithms, we applied an experimental procedure based on the methodology which is characteristic of data stream classification, namely, the test-then-update procedure [8]. The chunk size for evaluation purposes was set to 200.

Results and Discussion
To compare multiple algorithms on multiple benchmark sets, the average ranks approach is used. In this approach, the winning algorithm achieves a rank equal to '1', the second achieves a rank equal to '2', and so on. In the case of ties, the ranks of algorithms that achieve the same results are averaged.
The numerical results are given in Table 2 to 5. Each table is structured as follows. The first row contains the names of the investigated algorithms. Then, the table is divided into six sections -one section is related to a single evaluation criterion. The first row of each section is the name of the quality criterion investigated in the section. The second row shows the p-value of the Friedman test. The third one shows the average ranks achieved by algorithms. The following rows show p-values resulting from the pairwise Wilcoxon test. The p-value equal to .000 informs that the p-values are lower than 10 −3 . P-values lower than α are bolded. Due to the page limit, the raw results are published online 5 To provide a visualization of the average ranks and the outcome of the statistical tests, the rank plots are used. The rank plots are compatible with the rank plots described in [5]. That is, each classifier is placed along the line representing the values of the achieved average ranks. The classifiers between which there are no significant differences (in terms of the pairwise Wilcoxon test) are connected with a horizontal bar placed below the axis representing the average ranks. The results are visualised on figures 1 -4.
Let us begin with an analysis of the correction ability of the SCM approach when incremental learning is disabled. Although this kind of analysis has been already done [30,22], in this work it should be done again since the definition of the neighbourhood is significantly changed (see Section 2.3). To assess the impact of the SCM-based correction, we compare the algorithms ψ nB and ψ nS for different base classifiers. For ψ HOE and ψ NB base classifiers the employment of SCM-based correction allows achieving significant improvement in terms of all quality criteria (see Figures 1 and 2). For the remaining base classifiers, on the other hand, there are no significant differences between ψ nB and ψ nS . These results confirm observations previously made in [30,22]. That is, the correction ability of the SCM approach is more noticeable for classifiers that are considered to be weaker ones. The previously observed correction ability holds although the extensive grid-search technique is not applied.
In this paper, the SCM-based approach is proposed to be used as a wrappingclassifier that handles the incremental learning for base classifiers that are unable to be updated incrementally. Consequently, now we are going to analyse the SCM approach in that scenario. The results show that ψ S significantly outperforms ψ nB for all base classifiers and quality criteria. It means that it works great as the incremental-learning-handling wrapping-classifier. What is more, it outperforms ψ nS also for all base classifiers and criteria. It clearly shows that the source of the achieved improvement does not lie in the batch-learning-improvement-ability but the ability to handle incremental learning is also present. Moreover, it handles incremental learning more effective than the base classifiers designed to do so. This observation is confirmed by the fact that ψ S also outperforms ψ B for all base classifiers and quality criteria.

Conclusions
In this paper, we propose a modified SCM classifier to be used as a wrappingclassifier that allows incremental learning of classifiers that are not designed to be incrementally updated. We applied two modifications of the SCM wrappingclassifier originally described in [30,22]. The first one is a modified neighbourhood definition. The newly proposed neighbourhood does not need an excessive gridsearch procedure to be performed to find the best set of parameters. Due to the modified neighbourhood definition, the computational cost of performing the SCM-based correction is significantly smaller. The second modification is to incorporate ADWIN-based approach to create and manage the validation set used by SCM-based algorithm. This modification not only allows the proposed method to effectively deal with the concept drift but also it can shrink the neighbourhood when it becomes too wide.
The experimental results show that the proposed approach outperforms the reference methods for all investigated base classifiers in terms of all considered quality criteria.
The results obtained in this study are very promising. Consequently, we are going to continue our research related to the employment of randomised classifiers in the task of stream learning. Our next step will probably be a proposition of a stream learning ensemble that used the SCM-correction method proposed in this paper.