Senior Member, IEEE Abdelhamid Bouchachia
email: abouchachia@bournemouth.ac.uk

Charlie Vanaret
email: charlie.vanaret@alumni.enseeiht.fr

GT2FC: An Online Growing Interval Type-2 Self-Learning Fuzzy Classifier

Keywords: Growing interval Type-2 self-learning Fuzzy Classifier Abdelhamid Bouchachia, Charlie Online learning, Type-2 fuzzy rule systems, semi-supervised learning, Growing Gaussian mixture models, online optimization. I ) [3], [5]

published or not. The documents may come

OL faces the challenge of accurately estimating the statistical characteristics of data in the future. In non-stationary environments, the challenge becomes even more important, since the FRS's behavior may need to change drastically over time due to concept drift [START_REF]The problem of concept drift: definitions and related work[END_REF]. The aim of OL is to ensure continuous adaptation. The learning algorithm should store only the learning model (e.g., only rules of the FRS) and uses that model as basis in the future learning steps. As new data arrive, new rules may be created and existing ones may be modified allowing the system to evolve over time.

On the other hand, FRSs are preferred for learning from data due to their transparency to human beings and their power to cope with uncertainty [START_REF] Mendel | Uncertainty, fuzzy logic, and signal processing[END_REF], [START_REF] Wu | A vectorization-optimization-method-based type-2 fuzzy neural network for noisy data classification[END_REF]. Of interest in this study are incremental FRSs that aim at combining the technology of fuzzy systems and online learning to deal with online induction of comprehensible rules. In particular, incremental type-1 FRS have been recently introduced in a number of studies involving control [START_REF] Angelov | An approach for fuzzy rule-base adaptation using on-line clustering[END_REF], diagnostic [START_REF] Lughofer | Evolving Fuzzy Systems -Methodologies, Advanced Concepts and Applications[END_REF], and pattern classification [START_REF] Angelov | Evolving fuzzy-rule-based classifiers from data streams[END_REF], [START_REF] Bouchachia | Towards fuzzy incremental classifiers[END_REF]. Such systems are currently quite established, since they do not only operate online, but also consider related advanced concepts such as concept drift and online feature selection.

Motivated by an ambience intelligence application proposed by the authors [START_REF] Doctor | A type-2 fuzzy embedded agent to realise ambient intelligence in ubiquitous computing environments[END_REF], [START_REF] Hagras | An incremental adaptive life long learning approach for type-2 fuzzy embedded agents in ambient intelligent environments[END_REF], [START_REF] Wagner | An approach for the generation and adaptation of zslices based general type-2 fuzzy sets from interval type-2 fuzzy sets to model agreement with application to intelligent environments[END_REF] using type-2 FRS, this paper presents a novel online type-2 fuzzy rule-based system dedicated to classification to monitor a smart space on behalf of the occupants. To the best of our knowledge, no online type-2 FRS for classification exists yet. However, there have been studies related to: (1) online type-1 FRS [START_REF] Angelov | Evolving fuzzy-rule-based classifiers from data streams[END_REF], [START_REF] Bouchachia | Towards fuzzy incremental classifiers[END_REF] for various modeling tasks, (2) self-evolving type-2 fuzzy neural networks for control [START_REF] Juang | A self-evolving interval type-2 fuzzy neural network with online structure and parameter learning[END_REF] and (3) type-2 FRS for classification [START_REF] Mahmood | Type-2 fuzzy classification of blood pressure parameters[END_REF].

We are interested in an online interval-based type-2 FRS whose rules' premises are Gaussians and which are incrementally generated by a Growing Gaussian Mixture Model (2G2M). We also consider operational mechanisms in 2G2M (i.e., merge of partitions, split of partitions, etc.) to dynamically control the complexity and the quality of the rules. Moreover, in an online setting we cannot expect to receive feedback (i.e., data labels) from the environment all the time; thus, it is necessary to equip the fuzzy classifier with mechanisms that enable learning from both labeled and unlabeled data.

This paper addresses the following questions:

• How can OL be adopted for designing type-2 fuzzy classification systems? • How can the complexity of the rule base be controlled over time? • How can both labeled and unlabeled data be accommodated during rule learning? The remainder of the paper is organized as follows. An overview of the literature related to incremental fuzzy rule systems is presented in Sec. II. Then incremental mixture models are introduced in Sec. III. The description of type-2 fuzzy systems follows in Sec. IV. In Sec. V, we introduce our algorithm 2G2M which generates the partitions of space.

In particular the model refinement mechanisms are discussed therein. Section VI explains the process of fuzzy rule generation. Finally Sec. VII shows the empirical results obtained on various datasets before the paper is then concluded in Sec. X.

II. ONLINE FUZZY RULE-BASED SYSTEMS

Traditional FRSs are designed in batch mode, that is, by using the complete training data at once. For stationary processes this is sufficient, but for time-dependent and complex non-stationary processes, efficient techniques for updating the induced models are needed. To avoid starting from scratch every time, these techniques must be able to adapt the current model using only the new data. They have to be equipped with mechanisms to react to gradual changes or abrupt ones. Moreover, the adaptation of knowledge (model/rule-base) should accommodate any information brought in by the new data and reconcile this with the existing knowledge.

Many approaches do simply perform "adaptive tuning", that is, they permanently re-estimate the parameters of the computed model. However it is quite often necessary to adapt the structure of the rule-base. In contrast to these approaches, some advances in the direction of fully incremental FRS have been made over the recent years (e.g., [START_REF] Angelov | An approach for fuzzy rule-base adaptation using on-line clustering[END_REF], [START_REF] Bouchachia | Towards fuzzy incremental classifiers[END_REF]). While type-1 FRSs are well established, online type-2 FRSs have not yet received much attention. In this section we highlight some of the work on online fuzzy rule systems.

In [START_REF] Angelov | An approach for fuzzy rule-base adaptation using on-line clustering[END_REF] an approach for adaptation of an FRS of Takagi-Sugeno type was proposed. It consists of two steps: (a) generating clusters that represent the rule's antecedents using an on-line version of the subtractive clustering algorithm and (b) estimating the consequents' parameters using the least squares algorithm. New rules are added when new clusters are generated. Similar approaches relying on subtractive clustering and least squares have been proposed later in [START_REF] De Barros | On-line identification of computationally undemanding evolving fuzzy models[END_REF]. In [START_REF] Hagras | An incremental adaptive life long learning approach for type-2 fuzzy embedded agents in ambient intelligent environments[END_REF] a type-2 fuzzy controller was introduced. The FRS is capable of incrementally updating its rules which model the relationship between actuators (output variables) and sensors (input variables) in an ambient environment. Whenever the actuators are changed, the state of the environment is recorded before it is mapped to the rules' premises. The conclusions of the firing rules are then replaced by the actual output emanating from the actuators. If no rule is fired, a new one is added. In [START_REF] Bouchachia | Towards fuzzy incremental classifiers[END_REF], an integrated approach called FRCS was proposed. To accommodate incremental rule learning, appropriate mechanisms are applied at all steps: (1) Incremental supervised clustering to generate the rule antecedents in a progressive manner, (2) online and systematic update of fuzzy partitions, (3) Incremental feature selection using an incremental version of the Fisher's interclass separability criterion to dynamically select features in an online manner.

III. ONLINE CLUSTERING BASED ON GMMS

To automatically generate fuzzy rules, one needs to define the fuzzy membership functions which specify a partitioning of the input and possibly the output space. To do this, there are two types of fuzzy sets: uni-dimensional and multidimensional [START_REF] Castellano | Advances in Fuzzy Clustering and its Applications, chapter Mining Diagnostic Rules Using Fuzzy Clustering[END_REF], [START_REF] Krone | Data-based extraction of unidimensional fuzzy sets for fuzzy rule generation[END_REF]. Using uni-dimensional fuzzy sets, the rule premises are expressed as conjunction of fuzzy sets associated with the individual dimensions. The uni-dimensional fuzzy sets are obtained by projecting the partitions on the individual space features. On the other hand, using multidimensional fuzzy sets, the premises are expressed by the multi-dimensional partitions as a whole. In other terms, a multidimensional (multivariate) space can be divided into multidimensional fuzzy partitions represented in the form of multidimensional fuzzy membership functions. The use of multidimensional functions in fuzzy systems has the advantage of reducing the complexity of the rule base as well as retaining the correlation between the features [START_REF] Leondes | Fuzzy theory systems: techniques and applications[END_REF]. Nevertheless unidimensional functions provide more transparency as rules are explicitly expressed in terms of the input features. Note that "uni-dimensional" is not about "type-1", it is rather about how fuzzy granules are interpreted and how the form of fuzzy rules is desired to look like. Uni-dimensional fuzzy sets involve the individual features (see Eq. 9, Sec. IV), whereas multidimensional fuzzy sets involve granules (see Eq. 10, Sec. IV).

There are 3 types of fuzzy partitioning [START_REF] Jang | Neuro-Fuzzy and Soft Computing: A Computational Approach to Learning and Machine Intelligence[END_REF]: grid partitioning, tree partition, and scatter partitioning via clustering. In this paper, we consider the latter which consists of finding the regions that are susceptible to cover the data. A straightforward way to perform scatter partitioning is clustering. Scatter partitioning offers many advantages because: (a) clustering can be done online, (b) compact rule base can be obtained, and (c) interpretability and transparency can be ensured by transforming multi-dimensional fuzzy sets into uni-dimensional fuzzy sets, that is by projecting the clusters onto the feature axes [START_REF] Bouchachia | Towards fuzzy incremental classifiers[END_REF].

To facilitate a straightforward mapping between clusters and rules, we will propose a clustering algorithm that relies on an incrementally growing version of the Gaussian mixture model (GMM) trained by the Expectation-Maximization algorithm (EM) [START_REF] Dempster | Maximum likelihood for incomplete data via the EM algorithm (with discussion)[END_REF]. GMM is appealing because it can model complex and nonlinear pattern variations, it is efficient in terms of memory, it is able of selecting the optimal model, and it is theoretically guaranteed to converge [START_REF] Arandjelovic | Incremental learning of temporally coherent Gaussian mixture models[END_REF], [START_REF] Gross | Growing Gaussian mixture models for pose invariant face recognition[END_REF].

The approach proposed is characterized by the following:

• Online operation: Since the aim of this study is to investigate growing type-2 FRSs, we will rely on an adaptive growing Gaussian mixture model. The idea is to produce clusters that evolve over time to generate the rules' antecedents. Because the mapping from clusters to type-2 fuzzy sets of the rules must be less burdensome, online Gaussian mixture models are applied. • Semi-supervision: Because of the nature of online setting, not all data that arrive over time are labeled. Therefore, the online GMM-based clustering algorithm to be used in this paper must have semi-supervision mechanisms to accommodate unlabeled data. Note that for FRSs, semisupervised learning is not well established. Only very few studies have investigated this subject [START_REF] Bouchachia | Fuzzy classification in dynamic environments[END_REF], [START_REF] Klose | Semi-supervised induction of fuzzy rules applied to image segmentation[END_REF]. • Uncertainty handling: In real-time applications, data may be noisy, unlabeled and may drift, while the application of GMM trained online by Expectation-Maximization (EM) needs to estimate the influence of the new data. That is, the parameters of the model are not exactly computed due to the very nature of online learning. GMM may not be able to reflect the true data distribution (at time t, EM does not have the data already seen in the past, the new data may be noisy and may drift over time). Thus, it is necessary to consider the model's uncertainty. Here we use type-2 fuzzy GMM which allows to describe each parameter of the model with uncertainty.

GMM's are considered as a model-based clustering method which perceives the data as a population with K different components, where each component is generated by an underlying probability distribution. The density of a D-dimensional data point x i from the j th component is f j (x i ; θ j ), where θ j represents some unknown parameters associated with the component j. The density function associated is expressed as:

f (x i |θ) = K j=1 τ j f j (x i ; θ j ) (1)
where τ j is the weight of the j th component such that

K j=1 τ j = 1.
A typical case is when f j (x i ; θ j ) is a multivariate normal density φ j with θ j representing the characteristics of each component j. These characteristics are the mean µ j and the covariance matrix Σ j . The density φ j reads:

φ j (x i |µ j , Σ j ) = exp{-1/2(x i -µ j ) T Σ -1 j (x i -µ j )} det(2πΣ j ) (2)
Gaussian mixtures are usually trained using the iterative EM algorithm. In the E-step, the posterior probability of the data is computed, while in the M-step, the mixture parameters (τ j , μj , Σj ) are computed. This iterative algorithm is not adequate for online learning, since the aim is to avoid storing the entire data (i.e. the continuous stream of data) and each data point is discarded once it has been processed. Therefore, only online variants of GMM can be applied. Incremental approaches of GMM have been proposed by many authors [START_REF] Arandjelovic | Incremental learning of temporally coherent Gaussian mixture models[END_REF], [START_REF] Lee | Effective Gaussian mixture learning for video background subtraction[END_REF], [START_REF] Neal | A view of the EM algorithm that justifies incremental, sparse, and other variants[END_REF], [START_REF] Sato | On-line EM algorithm for the normalized Gaussian network[END_REF] where various versions of EM are applied. In particular, the approach described by Stauffer and Grimson [START_REF] Stauffer | Adaptive background mixture models for real-time tracking[END_REF] in a tracking context is one of the mostly established approaches. The parameters of the Gaussian mixture are updated as new data arrive. The existing approaches can be split into two categories, we name them here as: refinement-based methods and learning methods. 1) Refinement-based methods: In this category, the methods rely generally on two abstract stages: (i) Processing and integration of the new data into the current model, (ii) Refinement of the resulting model which aims at reducing the complexity of the model that results from the former stage. Usually the refinement is realized using some merge and split operations. Many merge criteria have been used, e.g., the w-statistic for equality of covariance and Hotellings T 2 -statistic for equality of mean [START_REF] Song | Highly efficient incremental estimation of Gaussian mixture models for online data stream clustering[END_REF], fidelity [START_REF] Declercq | Online learning of Gaussian mixture models -a two-level approach[END_REF], weighting [START_REF] Hall | A method to add Gaussian mixture models[END_REF], Chernoff bound [START_REF] Hall | A method to add Gaussian mixture models[END_REF], Kullback-Leibler measure [START_REF] Roberts | Minimum-entropy data partitioning using reversible jump Markov chain monte carlo[END_REF], mutual information [START_REF] Yang | Mutual information theory for adaptive mixture models[END_REF], and minimum description length [START_REF] Arandjelovic | Incremental learning of temporally coherent Gaussian mixture models[END_REF]. 2) Learning methods: In this category, the idea is to apply an online variant of the EM algorithm [START_REF] Radford | Learning in graphical models, chapter A view of the EM algorithm that justifies incremental, sparse, and other variants[END_REF] to train the Gaussian mixtures in an incremental way as new data become available. Based on this idea, there have been several studies dedicated in particular to surveillance systems and video analysis. The work by Stauffer and Grimson [START_REF] Stauffer | Learning patterns of activity using realtime tracking[END_REF] has become the standard formulation for the online learning of Gaussian mixtures which adopts an online EM-approximation based on recursive filter. It relies on a learning rule with a standard scheme:

θ(t) = (1 -η(t))θ(t -1) + η(t) (x(t); θ(t -1)) (3)
where t, θ, η and (.) are time, a model parameter (mean, variance), learning rate, and update amount. An analysis of the learning rate has been conducted in [START_REF] Lee | Effective Gaussian mixture learning for video background subtraction[END_REF] showed in particular that when η(t) = 1/t, the algorithm will run into local optimum on a stationary data distribution and if η(t) = α (α << 1), the most recent observations will have more impact and force the algorithm to take longer before it converges. The author in [START_REF] Lee | Effective Gaussian mixture learning for video background subtraction[END_REF] proposed a solution that ensures temporal adaptability and fast convergence by letting η converge to α instead of 0. More interestingly each Gaussian has its own η computed based on the current likelihood estimates. This allows it to handle Gaussians independently. The algorithm proposed by Lee in [START_REF] Lee | Effective Gaussian mixture learning for video background subtraction[END_REF] differs from Stauffer and Grimson's [START_REF] Stauffer | Adaptive background mixture models for real-time tracking[END_REF] with respect to the update rules of the learning rate η j and the weight of the Gaussian components τ j .

IV. OVERVIEW OF TYPE-2 FUZZY SYSTEMS Type-2 fuzzy sets are a generalization of type-1 sets; T2 FS have membership grades that are themselves fuzzy. That is, the membership at any value is no more a single point but a function. There are two classes of type-2 MFs which can be applied, interval type-2 fuzzy sets and general type-2 fuzzy sets as shown in Fig. 1. Most of the published work has focused on interval type-2 fuzzy sets showing successful applications in robotics, control, image processing and time series [START_REF] Castillo | Type-2 Fuzzy Logic: Theory and Applications[END_REF], [START_REF] Hagras | An incremental adaptive life long learning approach for type-2 fuzzy embedded agents in ambient intelligent environments[END_REF], [START_REF] Mencattini | Estimation of uncertainty in measurement by means of type-2 fuzzy variables[END_REF]. The reason for using interval type-2 fuzzy sets lies in their simplicity. Generalized type-2 fuzzy sets have been also applied in [START_REF] Zhai | Computing the centroid of a general type-2 fuzzy set by means of the centroid-flow algorithm[END_REF], [START_REF] Coupland | A generalised type-2 fuzzy logic system embedded board and integrated development environment[END_REF].

Often the issue is how to define the footprint of uncertainty (FOU) that specifies the notion of type-2 membership functions. FOU is obtained by means of a blurring procedure which allows us to assign an interval of values to each of element of the fuzzy set as shown in Fig. 1. The (possibilistic) weight of such values differ and we could use a three dimensional membership function to show this situation. By doing this, we are characterizing a type-2 fuzzy set. One of the most used methods for defining FOU consists of creating a margin, m, around the original type-1 fuzzy membership function. For instance, for a Gaussian membership function, the FOU allows the mean to lie within an interval [m 1 , m 2 ] [START_REF] Mendel | Type-2 fuzzy sets and systems[END_REF]. A type-2 fuzzy set à is defined as:

à = {((x, u), µ Ã(x, u))|∀x ∈ X, ∀u ∈ J x ⊆ [0, 1]} (4)
where µ Ã(x, u) ∈ [0, 1]. It follows that for a fixed x, we have a set of values, possibly with different weights, that we call In this sense, FOU includes the set of all possible primary MFs embedded in the type-2 fuzzy set as shown in Fig. 2. Therefore, the type-2 fuzzy set can be represented as the union of all its type-2 embedded fuzzy sets:

à = n j=1 Ãj e (5)
where Ãj e is the jth type-2 embedded fuzzy set given by:

Ãj e = {(x i , (u j i , f xi (u j i ))), u j i ∈ {u ik , k = 1, • • • , M i }} (6)
where i = 1, • • • , S, S is the number of elements of Ãj e , f xi (u j i ) is the secondary grade at u j i , n is the number of embedded type-2 fuzzy sets and M i is the number of the possibilistic weights (range of the secondary MFs) associated with each primary grade. That is: n = S i=1 M i . A type-2 fuzzy set can be thought of as a large collection of embedded type-1 sets each having a weight associated with it. At each value x, x = x , the 2-D plane axes are u and µ Ã(x , u) is called a vertical slice of µ Ã(x, u). The secondary MF is a vertical slice of µ Ã(x, u):

µ Ã(x , u) = µ Ã(x ) = u∈J x f x (u)/(u), J x ⊆ [0, 1] (7)
where 0 ≤ f x (u) ≤ 1. Because x can be any x ∈ X, µ Ã(x ) = µ Ã(x) which is referred to as the secondary MF [START_REF] Zhai | Computing the centroid of a general type-2 fuzzy set by means of the centroid-flow algorithm[END_REF]. The secondary MF is a type-1 fuzzy set, hence the name secondary set. It can take different forms [START_REF] Mendel | Type-2 fuzzy sets and systems[END_REF]. As mentioned earlier, the most widely used MF is the rectangularly shaped one, the so-called Interval Type-2 (IT2 MF) due to its simplicity. However, other MFs such as Gaussian, triangular, trapezoidal can also be used.

Referring to Eq. 7, if f x (u) = 1, ∀u ∈ J x ⊆ [0, 1], then the secondary MFs are interval sets. If this holds ∀x ∈ X, then the secondary MF is referred to as interval type-2 MF which characterizes the interval type-2 fuzzy sets. A uniform uncertainty at the primary memberships of x means that we have interval secondary MFs. This is illustrated in Fig. 1. An interval type-2 set is in this sense represented by its domain interval, that is the lower and upper points [l, u] as illustrated in Fig. 3 and which represent the bounds of FOU( Ã). The lower and upper bounds are referred to

[µ Ã(x), µ Ã(x)].
Being interested in fuzzy rule-based classification systems, we need to draw the differences between T1 FRS and T2 FRS. At the operational level, T2 FRS differ from T1 FRS in the type of fuzzy sets and the operations applied on these sets. T2 fuzzy sets are equipped mainly with two newly introduced operators called the meet, and join, which correspond to the fuzzy intersection and fuzzy union. As shown in Fig. 4, T2 FRS at the structural level is similar to T1 FRS but contains an additional module, the type-reducer. Schematically, the structure of the T2 FRS consists of:

1) Fuzzifier: It aims at converting the crisp inputs into input type-2 fuzzy sets. Very often and due to simplicity, only Singleton fuzzification is applied [START_REF] Mendel | Type-2 fuzzy sets and systems[END_REF]. Formally given a crisp vector

x = [x 1 , • • • , x p ] t ∈ X 1 × X 2 × • • • × X p = X,
the Singleton fuzzification transforms x into an input fuzzy set that has only a single point, x , of nonzero membership, that is:

µ Ãx (x, u) = 1/1 for x = x 1/0 f orall x = x (8)
meaning that at x = x the secondary grade is 1 when the primary variable u = 1 and 0 at all other values of the primary variable (x = x ).

2) Fuzzy rule base:

It consists of fuzzy "IF-THEN" rules which are extracted from raw data by means of an inductive learning process.

In a classification type-2 fuzzy rule system, the fuzzy rules for a C-class pattern classification problem with n input variable can be formulated as:

R j ≡ if x 1 is Ãj,1 ∧ ... ∧ x n is Ãj,n then C i (9) where x = [x 1 , • • • , x n ] t such
that each x i is a an input variable and Ãr,i the corresponding fuzzy terms in the form of type-2 fuzzy sets. We may associate these fuzzy sets with linguistic labels to enhance interpretability. C i is a consequent class (i.e., one of the given C classes), and j = 1, • • • , N is the number of fuzzy rules.

Multidimensional fuzzy sets can be used also to build FRS's. The rules are expressed in the form:

R j ≡ if x is K p then C i (10)
where K p is a cluster. The rule means that if the sample x is close to K p then x should belong to class C i . Motivated by interpretability issues, in this paper, we consider the former form (Eq. 9). Type-2 fuzzy rules are generated. In particular, it will describe mechanisms to produce and update the type-2 antecedents of the rules in an online manner to accommodate data arriving sequentially and continuously over time. Such rules should not assume that old data is available.

3) Fuzzy inference engine:

The inference engine computes the output of type-2 fuzzy sets by combining the rules. Specifically, the meet operator is used to connect the type-2 fuzzy propositions in the antecedent. The degree of activation of the jth rule using the n input variables is computed as:

βj (x) = n q=1 µ Ãj,q (x q ), j = 1, • • • , N (11)
The meet operation that replaces the fuzzy 'and' in T1 FRS is given as follows:

à B = u∈Jx w∈Jx f x (u) * g x (w)/(u∧w), x ∈ X (12)
If we use the interval Singleton T2 FRS, the meet is given for input x = x by the firing set, i.e.,

βj (x) = [β j (x), β j (x)] = [µ Aj,1 (x 1 ) * • • • * µ Aj,n (x n ), µ Aj,1 (x 1 ) * • • • * µ Aj,n (x n )] (13)
In this paper we adopt the Gaussian membership function given as follows:

µ A (x) = exp - (x -m) 2 2σ 2 = N (m, σ; x) (14)
where m and σ are the mean and the standard deviation of the function. To generate the lower and upper membership functions, we rely on two possible methods:

• The interval set for the Gaussian function with uncertain mean is given by:

µ Ã(x) =      N (m 1 , σ; x) x < m 1 1 m 1 ≤ x ≤ m 2 N (m 2 , σ; x) x > m 2 (15) µ Ã(x) = N (m 2 , σ; x) x ≤ m1+m2 2 N (m 1 , σ; x) x > m1+m2 2 (16)
• For the Gaussian with uncertain deviation, concentration and dilation hedges are used to generate the

µ Ã(x) = µ DIL(A) (x) = [µ A (x)] 1/2 (17) µ Ã(x) = µ CON (A) (x) = [µ A (x)] 2 (18)
The graphical representations of these two types of Gaussian are portrayed in Fig. 5 and Fig. 6. Moreover, according to Eq. 14, we will have the following expressions:

µ Ã(x) = N (m, √ 2σ; x) (19)
µ Ã(x) = N (m, σ √ 2 ; x) (20)
4) Type-reducer: It converts T2 FSs obtained as output of the inference engine into T1 FSs. Type-reduction for FRS (Mamdani and Sugeno models) was proposed by Karnik and Mendel [START_REF] Karnik | Operations on type-2 fuzzy sets[END_REF], [START_REF] Mendel | On km algorithms for solving type-2 fuzzy set problems[END_REF]. This will not be adopted in our case, since the rules' consequent represents the label of a class. Traditionally in Type-1 fuzzy classification systems, the output of the classifier is determined by the rule that has the highest degree of activation:

Winner = C j * , j * = argmax 1≤j≤N β j ( 21
)
where β j is the firing degree of the j rule. In type-2 fuzzy classification systems, we have an interval βj = [β j , β j ] as defined in Eq. 13. Therefore, we compute the winning class by considering the center of the interval [β j (x), β j (x)], that is:

Winner = C j * , where (22)
j * = argmax 1≤j≤N 1 2 (β j (x) + β j (x)) (23)

V. 2G2M: A GROWING GAUSSIAN MIXTURE MODEL

The algorithm 2G2M shown in Algorithm 1 is an incremental algorithm like the ones mentioned in Sec. III. It extends the algorithm presented in [START_REF] Lee | Effective Gaussian mixture learning for video background subtraction[END_REF] in many aspects. The novelties concern the processing of the labeling information, the explicit handling of multi-dimensional data, handling the complexity of the model generated as will be explained later, and finally the re-structuration to accommodate the named changes. The similarities concern mainly the online update procedure which is based on an online approximation of the standard expectation maximization method provided in [START_REF] Stauffer | Learning patterns of activity using realtime tracking[END_REF].

The symbols appearing in Alg. 1 are defined as follows:

K : the number of Gaussians φ j , j = 1 • • • K µ j
: the center of the jth Gaussian Σ 0

: the initial covariance matrix of the Gaussians (= k 0 I D proportional to the identity matrix of size D -the number of features-) α : the learning rate T Σ : the closeness threshold (Eq. 24) τ j

: the weights of the jth Gaussian c j : the sum of the expected posterior (a sufficient statistics in the EM method) of the jth Gaussian L j : the label of the jth Gaussian (cluster) Moreover, Alg. 1 is characterized by the following aspects:

A. Probability of Match

Equation 24 has to be adapted to enable semi-supervised learning. We compute the probability of matching the input x i with the jth Gaussian by considering the following cases:

1) The input x i is unlabeled: all Gaussians need to be considered during the match operation (Eq. 24). 2) The input x i is labeled and jth Gaussian is unlabeled:

such Gaussian is considered during the match operation. 3) The input x i and jth Gaussian have the same label: the Gaussian is of course considered. 4) The input x i and jth Gaussian do not have the same label: the Gaussian is discarded. Moreover the distance d M (x i , φ j ) between an input x i and a Gaussian φ j (µ j , Σ j ) in Eq. 24 is the Mahalanobis distance expressed as follows:

d M (x i , φ j ) = (x i -µ j ) T Σ -1 j (x i -µ j ) (35)

B. Processing of Unlabeled Data

To achieve a semi-supervised learning setting, the 2G2M algorithm is equipped with a mechanism for accommodating labeled and unlabeled data. The Gaussians are updated and eventually created according to the label of both the Gaussian and the incoming input. Similar to the cases outlined in Sec. V-A, the accommodation of new data is done as follows:

1) If the incoming input is not labeled, simply find the highest matching Gaussian, add the contribution of the input and update all Gaussians. Algorithm 1 : Steps of 2G2M

1: Set parameters: K, Σ0, α, TΣ 2: Initialization:

∀j = 1 • • • K, (τ, c, µ, Σ, L)j = (α, 1, ∞, Σ0, 0) 3:
Given a new input xi, compute the probability of match of the input with the Gaussians:

∀j = 1 • • • K pj = τjφj(xi; µj, Σj) if dM (xi, φj) < TΣ 0 otherwise (24)
4: Let R = {j|pj > 0} be the index set of Gaussians matching the input 5: createGaussian ← (R == ∅) (i.e., no match is found: j, pj > 0) 6: if not createGaussian then 7:

Compute the index of highly matching Gaussian:

w = argmax j=1•••K {pj} (25) 8:
if xi is labeled then

9:
if the wth Gaussian is not labeled then 10:

Assign the wth Gaussian the label of xi if not createGaussian then 16:

for j = 1 • • • K do 17:
Compute the expected posterior:

qj = pj k=1•••K p k (26) 18:
Update the parameters of the Gaussian:

cj =cj + qj (27) τj(t) =(1 -α)τj(t -1) + αqj (28) ηj =qj 1 -α cj + α ( 29
)
µj(t) =(1 -ηj)µj(t -1) + ηjxi (30)
Σj(t) =(1 -ηj)Σj(t -1) + ηj(xi -µj(t -1)) 2 (31) 19:
end for Decay the weight of all Gaussians

∀j = 1 • • • K, τj(t) = (1 -α)τj(t -1) (32) 24:
Remove the less contributing Gaussian and create a new one initialized with the new input:

m = argmin j {τj} (33)
(τ, c, µ, Σ, L)m = (α, 1, xi, Σ0, 0) (34

C. Model Refinement

To lower the complexity and enhance the model accuracy, we rely on refinement-based methods that use the two operations: split and merge as explained in Sec. III. Due to the presence of unlabeled data, Gaussians may overlap but also may cover several classes. To avoid these situations, the algorithm has been equipped with mechanisms that perform split and merge operations on the Gaussians.

1) Split Operation: In order to keep the algorithm accurate and precise, large Gaussians (considered to be as "too big") are split into two smaller Gaussians. The chosen criterion for deciding to split a Gaussian φ(µ, Σ) refers to its volume:

V (φ(µ, Σ)) = det(Σ) (36)
The Gaussian φ(τ, µ, Σ) with the maximum volume V above a given threshold T split is split into two Gaussians (φ 1 (τ 1 , µ 1 , Σ 1 ), φ 2 (τ 2 , µ 2 , Σ 2 )) along its dominant principal component (Fig. 7a). The τ 's are the weights of the corresponding Gaussians. The resulting Gaussians after split are assigned a weight τ /2. Let v the (normalized) eigenvector corresponding to the largest eigenvalue λ, and a (which is set to 0.8) a split factor that determines how far the centers of the two new Gaussians are apart from each other. Clearly the expression of ∆v below shrinks the original ellipse along the dominant principal component by a certain proportion which serves to create the new centers and the covariance matrices.

               ∆v = √ aλv τ 1 = τ 2 = τ 2 µ 1 = µ + ∆v µ 2 = µ -∆v Σ 1 = Σ 2 = Σ -∆v∆v T (37)
2) Merge Operation: In order to reduce the complexity, Gaussians of the same label can be merged. The merge operation combines the two closest Gaussians into one single Gaussian. It relies on the Kullback-Leibler divergence (kld) between two D-dimensional Gaussians (φ 1 (µ 1 , Σ 1 ), φ 2 (µ 2 , Σ 2 )) as a merge criterion which reads as follows [START_REF] Schnitzer | Islands of Gaussians: The self organizing map and Gaussian music similarity features[END_REF]:

kld(φ 1 , φ 2 ) = log |Σ 2 | |Σ 1 | + tr(Σ -1 2 Σ 1 ) + ϑ T Σ -1 1 ϑ -D (38)
where ϑ = (µ 2 -µ 1 ), tr indicates the trace. Since kld is asymmetric, a symmetrized variant (skld) of the divergence is used for similarity estimation:

skld(φ 1 , φ 2 ) = 1 2 (kld(φ 1 , φ 2 ) + kld(φ 2 , φ 1 )) (39)
The pair of Gaussians (φ

1 (τ 1 , µ 1 , Σ 1 ), φ 2 (τ 2 , µ 2 , Σ 2 ))
whose skld is minimum and falling below a threshold T merge are combined into a new Gaussian φ(τ, µ, Σ) (Fig. 7b) using:

               f 1 = τ1 τ1+τ2 f 2 = τ2 τ1+τ2 τ = τ 1 + τ 2 µ = f 1 µ 1 + f 2 µ 2 Σ = f 1 Σ 1 + f 2 Σ 2 + f 1 f 2 (µ 1 -µ 2 )(µ 1 -µ 2 ) T (40)
3) Cannot-Merge Link: There is a risk that a Gaussian be split, then re-merged straight away. To avoid this phenomenon, we endow each split or merged Gaussian with a cannotmerge link (CML) similar to "must-link" and "cannot-link" in constraint-based clustering. CML is a positive integer that decreases over time and that disables temporarily subsequent split or merge of the same Gaussians as long as it is greater Figure 8 shows the results of merge and split operations occurring at different time points during clustering of the banana dataset. The accommodation of new data can lead to either modifying the shapes and orientations of the clusters, merging and splitting of existing clusters, or creating new ones. The virtual ellipses show approximately the region of influence of each Gaussian around its center, since 2G2M outputs only the means, the covariance matrices and the mixing parameters.

D. Parameter optimization

Due to their number (maximum number of clusters K, thresholds T Σ -T merge -T split , learning rate α, initial spread Σ 0 ), setting the parameters is in general a difficult problem. Usually they have to be set for each dataset. However, in this paper we rely on genetic algorithms (GA), widely used for solving optimization problems, to provide a set of parameters corresponding to a local optimum of the fitness function. We choose the fitness function to be the number of misclassified examples by the 2G2M algorithm. While the parameters, α and K, are considered as user-defined parameters, the remaining ones, T Σ , T merge , T split and k 0 are determined by GA.

Given the online setting, we do not have access to all data. Hence, to ensure online optimisation of these parameters, we propose an original way of optimizing the parameters online and continuously. We did the following: We generated two versions of GF2FC, one running online which we use in real time and an offline version involving only 2G2M that runs only periodically on small batches of labeled data. For this offline version, data are accumulated and whenever a batch of n labeled examples is collected, it is used in a GA loop to find the optimal parameter values. These are then transferred into the online version. To ensure the optimization continuity, the top m individuals of a given cycle are used to initialize the GA population for the next cycle.

Note that the parameters themselves are encoded together as a chromosome with the classification accuracy measure as a fitness function. The GA parameters used in all experiments are: |Population|=100, number of iteration=100, recombination probability =0.8, mutation probability=0.3, selection method: linear ranking, and crossover method: one-point crossover. The size of the batch is n = 30 and the number of chromosomes retained from the next generation is m = 10. if the new input is labeled then Re-select the meaningful features using the incremental feature selection algorithm in [START_REF] Bouchachia | An evolving classification cascade with self-learning[END_REF] if desired; end if Generate the appropriate fuzzy sets by projecting the clusters on the selected features and form the rules. end for

VI. FUZZY RULE GENERATION

The main steps for rule generation are displayed in Alg. 2. These steps are kept general to ease understanding. In the following, the issues related to rule generation are highlighted.

A. Projection of Gaussians

Once the new input has either generated a new Gaussian or updated an existing one, we use projections of the ndimensional Gaussians on the n axes to determine the MFs of the T2 FRS (Fig. 9). For a Gaussian N (µ, Σ), the projected MF on axis d is a unidimensional Gaussian N (m, σ; x) (Eq. 14), whose parameters are determined as follows:

m = µ d σ = √ Σ dd (41)
where µ d is the d-th coordinate of the vector µ and Σ dd is the d-th diagonal term of the covariance matrix Σ. This Gaussian defines a type-1 membership function.

It is worthwhile to recall that with multi-dimensional fuzzy sets, the number of rules will be the same as that of fuzzy partitions and hence no projection is needed. However, unidimensional fuzzy sets offer a better degree of interpretability, despite the lengthy premises of rules that can be generated (as discussed in Sec. III). Unfortunately the complexity remains high if the data is highly dimensional. This paper focuses on generating rules whose form is shown by Eq. 9. Thus, the features are explicitly used. Thus, to enhance the transparency and the compactness of the rules, it is important that the if-part of the rules does not involve many features [START_REF] Gacto | Interpretability of linguistic fuzzy rule-based systems: An overview of interpretability measures[END_REF]. Very often, low classification performance results from non-informative features. To get rid of those features, usually feature selection methods are used which are of two classes [START_REF] De | Feature analysis: Neural network and fuzzy set theoretic approaches[END_REF]: filters and wrappers. Many methods do not lend themselves the possibility to find the most relevant features from incrementally arriving data. They assume that the whole data is available or at least there is sufficient amount of data.

In order to cope with the complexity of the rules, enhancing the transparency by reducing the number of features in the rules, the incremental feature selection algorithm described in [START_REF] Bouchachia | An evolving classification cascade with self-learning[END_REF][8] is used. The importance of incremental feature selection comes from the fact that the set of selected features change over time. The algorithm uses an incremental version of Fishers interclass separability criterion. As new data instances arrive, some features may be neglected in the rules and some others may be included. The premises of the rules are dynamically and systematically updated. The main goal is that at any time, the rule base reflects the semantical contents of the data already used. In our experiments, when the data dimensionality exceeds a certain number n (one can fix this number at wish), the incremental feature selection algorithm is applied and only the first n important features are retained. It is, however, up to the user to decide, either to keep all features or to select a particular number of them over time.

B. Rule base Optimization

In order to enhance the quality of the T2 fuzzy rules [START_REF] Gacto | Interpretability of linguistic fuzzy rule-based systems: An overview of interpretability measures[END_REF], we use two methods:

1) Cluster refinement: by merging the highly overlapping Gaussians using the Mahalanobis distance, a lower number of type 2 FS's can be obtained which will be used to generate the fuzzy rules. 2) Rule refinement: once the Gaussians are obtained, rules are then generated. These rules undergo an optimization process which consists of merging the membership functions (fuzzy sets) using the Jaccard's similarity measure for type-2 FS's which is based on the analysis provided in [START_REF] Mencar | Distinguishability quantification of fuzzy sets[END_REF]. Those exceeding a threshold are merged using an adapted formula for fusing univariate Gaussians like:

µ new = (s 1 * µ 1 + s 2 * µ 2 )/(s 1 + s 2 ), s new = s 1 + s 2
where s {new,1,2} = 1/σ 2 {new,1,2} . One could also merge the underlying clusters and then consider only the targeted dimension. Another merge method would be to use the Join operation [START_REF] Mendel | Type-2 fuzzy sets and systems[END_REF], but rules premises will not be expressed as Gaussians in a straightforward way. Both methods yield quite compact rules. The first one is easy to perform given that the clustering algorithm, 2G2M, is already equipped with a merge operation. It is however difficult in general to re-define the closeness threshold used in the clustering algorithm, because it is originally and automatically determined by means of a GA-based optimization process on batches of data (See Sec. V-D). The second method on the other hand requires also the definition of the similarity threshold, but it is easier to do so; the higher it is, the less frequent the merge is. For instance with the second method, we can generate rules of the form:

R j ≡ if x i is ( Ãj,i ∨ ... ∨ Ãj,i ) ∧ ((x k is Ãj,k ∨ ... ∨ Ãj,k ) ∨ (x l is ( Ãj,l ∨ ... ∨ Ãj,l )) then C n (42)
For the Banana-shaped data, the fuzzy partitions obtained without any optimization are shown in Fig. 11a. Figures 11b and11c show the optimization results after applying method (1) and method [START_REF] Angelov | Evolving fuzzy-rule-based classifiers from data streams[END_REF]. For the purpose of legibility, type-1 fuzzy membership functions are used. Type-2 fuzzy rules are shown in Tab. I. In particular, we notice that rules generated after method 2 are fewer than those generated after method 1. The number of original rules is usually much higher. Note that in the experiments (Sec. VII), we used the original rule set.

To generate linguistic terms in the rules, the Gaussians will be ordered from low/small to high/large with respect to each dimension. Then those linguistic terms can replace the Gaussians in the rules. However, the meaning of these terms changes dynamically over time as new data arrive. For example, at time t, "large" on the x-axis corresponds to values between 20 and 30. In the future, "large" may indicate values between 50 and 60. A term can, however, be assigned to only one function, but it may represent many clusters.

C. Unlabeled Clusters

Because the 2G2M algorithm (Alg. 1) accommodates both labeled and unlabeled data, the resulting clusters can be either labeled or unlabeled. The unlabeled clusters do not produce any rule, although it is possible to generate rules by computing the class of the neighboring clusters and then use majority voting to assign a label to the unlabeled cluster and therefore, this uncertain aspect is implicitly taken care of by the type-2 fuzzy rule system.

VII. EMPIRICAL EVALUATION

We evaluate the proposed classifier GT2FC using two sets of experiments. For the sake of illustration, the first set of experiments is carried out on a synthetic data set, a Banana shaped dataset. In the second set of experiments, we use real-world datasets: classic datasets (from UCI [START_REF] Frank | UCI machine learning repository[END_REF]) and an ambient intelligence dataset [START_REF] Hagras | An incremental adaptive life long learning approach for type-2 fuzzy embedded agents in ambient intelligent environments[END_REF]. We will investigate many aspects to give insight into the approach. In particular, we study the behavior of online adaptation which is measured by Eq. 43 that expresses the current error rate as: e(t) = misses(t) seen so f ar(t) [START_REF] Song | Highly efficient incremental estimation of Gaussian mixture models for online data stream clustering[END_REF] where misses(t) represents the number of misclassified data until time t and seen so f ar(t) represents the number of presentations (inputs) seen so far.

The datasets are split into labeled and unlabeled sets in two ways:

1) random decreasing: the desired proportion of labeled data is randomly selected and the position in the sequence of the whole data is also random but the frequency of occurrence of labeled examples decreases over time. That is, labeled examples are more frequent at the beginning of the sequence, but become rare and then non-existent towards the end of the sequence. The idea reflects the fact that the system may need more labeled data in earlier stages of the training. Given that the datasets used in this paper are labeled, samples satisfying the following probability are retained, while the rest is considered unlabeled:

∀i ∈ {1, • • • , n}, p label (x i ) = 1 - i n ( 44
)
where i is the order of x i in the input sequence and n is the size of the data(i.e, sequence length). 2) random selection: the desired proportion of labeled data is randomly selected. The position in the sequence of the whole data is random.

A. Classic Datasets

The first class of datasets consists of: Iris, Wine which are obtained from the UCI repository [START_REF] Frank | UCI machine learning repository[END_REF] and a banana-shaped dataset which is artificially generated (already used in the previous sections). The description of these datasets is shown in Tab. II. The banana-shaped dataset consists of a synthetic bidimensional set of 400 points. It has been chosen due to:

• its difficulty for semi-supervised learning algorithms because of its non-linear separability, • its shape which is not Gaussian and • the possibility to visualize it easily, since it is 2dimensional. Using the online optimization approach presented in Sec. V-D, the value of the parameters T Σ , T merge , T split and k 0 will be automatically and over time computed. For the sake of illustration, Tab. III shows the evolution of the parameter setting (early stage, middle stage and final stage).

Considering the two modes of labeled data selection, random decreasing and random, we obtain the results shown in Figs. 12, 13, and 14 which are averaged over 30 runs. Three main conclusions can be drawn:

• the adaptation capability of the algorithm 2G2M: the learning effect is clear and the accuracy of the classification increases as more data are presented. • the random decreasing mode of labeled data selection looks slightly better than the random mode • the variability of the results (standard deviation) at the beginning of the learning is higher than that towards the end of the data presentation. Moreover, the algorithm has been tested on these data sets by splitting them into 60% -40% (60% for training, 40% for testing) to test the performance. The accuracy measure (i.e., the ratio of the correctly classified data) has been used to evaluate the performance of the type-2 fuzzy classifier. Different configurations (proportion of the labeled data, mode of labeled data selection, the maximum number of clusters) have been tested yielding the final classification results shown in Tab. IV after 30 runs. The results look highly promising.

Table V shows the 2G2M behavior over the banana data. It shows in particular new labeled/unlabeled data (0 for unlabeled, 1 for labeled; the true label is between brackets), the matching Gaussian -Winner (the label of the winner is between brackets), the matching probability, the actual number of Gaussians, and the boolean operations creation, merge and split (they are set to 1 if they are executed, otherwise 0). B. Real-World Application: Ambient Intelligence Ambient intelligence (AmI) aims at exploiting sensed information to seamlessly assist the inhabitants of a smart space to carry on their daily activities. Intelligent monitoring solutions of the living space intend to deal efficiently with various aspects like comfort, security and safety, productivity, and energy efficiency for the benefit of the occupants. The major challenges of intelligent environments research include the modeling of the occupants activities and actions, the dynamic evolution of the occupant behavior, the interaction, and the smart monitoring of the physical infrastructure.

A suitable monitoring system for this application must be evolving, in the sense that as new data become available, it has to self-adapt in an online manner. Because, sensors are prone to faults and noise, type-2 fuzzy modeling is very appropriate for dealing with such application. Designed for applications confronting uncertainty, GT2FC is tested on datasets stemming from an AmI environment which is an intelligent student [START_REF] Bilgin | Dynamic profile-selection for zslices based type-2 fuzzy agents controlling multi-user ambient intelligent environments[END_REF], [START_REF] Doctor | A type-2 fuzzy embedded agent to realise ambient intelligence in ubiquitous computing environments[END_REF], [START_REF] Hagras | An incremental adaptive life long learning approach for type-2 fuzzy embedded agents in ambient intelligent environments[END_REF]. The iDorm test bed serves to predict the different classes of user actions. The dataset is generated by recording student activities in the iDorm which is equipped with embedded sensors, actuators, processors and heterogeneous networks that are concealed in a way letting the users behave naturally [START_REF] Hagras | An incremental adaptive life long learning approach for type-2 fuzzy embedded agents in ambient intelligent environments[END_REF]. The data (7 input features) are provided by the sensors: internal light level, external light level, internal temperature, external temperature, chair pressure, bed pressure, occupancy and time. The data used in the following experiments concern two inhabitants: D 1 The goal of the study is to use the data obtained over long periods of time in order to build a classifier capable of learning the user's behavior and actions on the actuators given some environmental conditions that are captured by the sensors.

0[2] 0.00000 - 0 1 2 0[2] 0.00000 - 2 1 3 1[1] 0.00000 - 3 1 • • • • • • • • • • • • • • • • • • 100 0[2] 0.00492 1(2) 8 0 101 0[1] 0.00000 - 8 1 102 1[2] 0.14111 1(2) 9 0 • • • • • • • • • • • • • • • • • • 278 0[1] 0.05659 7 (
The parameters T Σ , T merge , T split and k 0 are again determined online using GA. Table VIII shows an excerpt of the parameter evolution (early stage, middle stage, final stage). The actual values change over time as batches of labeled data are collected. It is worth mentioning that the values shown in Tab. VIII change depending mainly on size of labeled data.

1) Effect of Increasing Labeled Data: In real-world applications, it is important to know how often a labeling feedback might be necessary to help the learning system to self-adjust. Each of the datasets D 1 and D 2 has been split into 2 sets: training and testing. The training set consists of the first 3/4 of month 1, while the testing set consists of the last 1/4 of month 1 and the whole data of month 2. Note that the classifier is trained online. Details of the data split are shown in Tab. VII.

For both datasets, we obtained the accuracy results illustrated in Fig. 16 and the evolution trend of the current error during the training phase shown in Fig. 15. Clearly larger ratios of labeled data provide better prediction results in both cases of D 1 and D 2 after running the algorithm 100 times and averaging the results. On the other hand the evolution of the current error during the training phase seems to be higher when the ratio of labeled data is 10%, but for the other ratios, the evolution is almost stable as the error is small and sometimes is almost 0. It is important to recall that the classifier has not been trained on the second month.

2) Effect of Labeled Data Presentation: Similar to Sec. VII-A, the effect of using two modes of labeled data selection, random and random decreasing, is studied. The data set is split according to the scheme described in Sec. VII-B1. Two ratios of labeled data, 30% and 50%, are considered.

Figure 17 shows the evolution of the current error for D 1 and D 2 and for both ratios of labeled data. to be created, we vary the number between 5 and 50 for random selection scenario (Fig. 18). The results are obtained by averaging over 100 runs.

In general, a higher number of Gaussians than the actual number of classes tends to provide better accuracy. Also, the Running the algorithm with as many clusters as classes is not efficient enough. Table XI illustrates that better results are obtained with a higher number of clusters. The problem is then the transparency of the rule base which is generated from the clusters. In other terms, increasing the number of clusters leads to a quite large rule base. The tradeoff is then between the accuracy and the transparency. An optimization stage may be required to remove redundant clusters/rules as explained in Sec. VI-B. Note, however, that the number of clusters generated does not depend only on the maximum (threshold) number of clusters allowed, but also on the thresholds T Σ , T merge , T split , the learning rate α and the initial spread Σ 0 . 4) Rule Generation and Feature Selection: To illustrate the effect of adding new data on the selected features, Tab. XII shows the process of feature selection when using D2 data with 70% labeled data (batch size=60). The features are shown in Tab. XIII. The incremental feature selection uses the new batches to update the relevance order of features. An excerpt of rules generated after the presentation of the last labeled batch is shown in Tab. XIV. After merging the similar fuzzy sets according to the 2nd optimization method (see Sec. VI-B), the new version of the rules are shown in Tab. XV.

C. Data Drift Handling

In dynamically evolving environments, the data distribution may drift over time, leading to performance deterioration of the system, that is, the model built using old data becomes inconsistent with the new data. To tackle this problem, the system needs to be equipped with appropriate mechanisms to handle concept drift.

The current state-of-the-art techniques of concept drift are rather data driven, meaning that drift is handled only from the perspective of data. There are many techniques [START_REF] Bouchachia | Incremental learning with multi-level adaptation[END_REF], [START_REF]The problem of concept drift: definitions and related work[END_REF] such as instance selection, instance weighting, and ensemble learning. Although there are several research avenues using data-driven techniques, in this paper we use model-driven drift handling techniques [START_REF] Sahel | Adaptive mechanisms for classification problems with drifting data[END_REF]. Model-driven drift means using appropriate models that are incremental and able to handle drift. We are interested in models that are capable of handling drift in a systematic way without relying on additional techniques, such as time windowing.

We evaluate the adaptation capability of the algorithm GT2FC to data drift. GT2FC is dedicated to dynamically incremental settings requiring to self-adjust over time so that a continuous performance is ensured. The sensitivity of GT2FC to drift is tested using the iDorm data in two ways: 1) Artificial Drift: To generate drifting data from the real world iDorm dataset, we rely on feature selection as a method to determine the feature which is the highly correlated with the classes measured by a partial F-test. Once such a feature has been found, the data set is sorted according to that feature. Then, the indicated feature is discarded from the data. The drift is generated, while its origin is hidden (the drift origin is often unknown in real world situations).

The feature which is most correlated with the output of the iDorm dataset is "internal light level" (first feature). We sort the data according to this feature, then we discard it. Figures 19 and20 show the evolution of the error using the whole data sets D 1 and D 2 . Clearly the algorithm GT2FC is capable of self-adjusting in response to drift as the error rate decreases. Note that in this experiment different numbers of clusters have been tried, the ratio of labeled data has been set to 30% randomly presented, and the results have been averaged over 100 runs.

2) Natural Drift over Two Seasons: As explained in Sec. VII-B, the first iDorm data set D 1 concerns two months June and September, while D 2 concerns March and June. The data of each month differ from that of the other month for both datasets. The two pairs of months refer to two pairs of seasons in UK: (Summer vs. Autumn) and (Spring vs. Summer) respectively. Hence, drift is natural in the data, but sofar in the experiments the data has been split into 2 sets: training and testing, where the training set consists of the first 3/4 of month 1 and the testing set consists of the last 1/4 of month 1 and the whole month 2. In the present experiment, the whole data will be used as a stream to observe how the current error evolves over time.

Figures 21 and22 show the current error over the two seasons for different numbers of clusters. The current error starts to increase in the vicinity of the season change point. While for the first data set D 1 the error increases slightly (but remains small), for the second data set D 2 the error decreases as new data arrive.

VIII. TYPE-2 VS. TYPE 1 AND OTHER INCREMENTAL LEARNING SYSTEMS

To highlight the suitability of the proposed incremental type-2 FS, GT2FC to the ambient intelligence application at hand, we compare it against the type-1 version of GT2FC, denoted in the following as GT1FC, and against other incremental learning algorithms namely Incremental Fuzzy Rule-based Classification System (IFCS) [START_REF] Bouchachia | Fuzzy classification in dynamic environments[END_REF] and the Nearest Generalized Exemplar (NGE) [START_REF] Salzberg | A nearest hyperrectangle learning method[END_REF].

Tables XVI and XVII show the results for different ratios of labeled data. Note that IFCS and NGE are trained using only the labeled data, while GT1FC and GT2FC are trained using both labeled and unlabeled data. The training and the testing data are obtained according to the split explained in Sec. VII-B. Judged by the standard deviation, clearly GT1FC and GT2FC are more efficient and stable as the labeled data size increases compared to IFCS and NGE. Moreover, GT2FC outperforms GT1FC on average especially in the case of D2 (Tab. XVII) although the difference is not significantly high.

For 10% labeled data, the performance of GT2FC and GF1FC is below that of the other algorithms. The reason is that the other algorithms are trained on only labeled data and therefore their prediction power is higher than that of GT2FC which uses labeled and unlabeled data. We notice that the boundary may be between 10% and 30% included, where the rise occurs, although this observation may not always be true (e.g., in Tab. XVI, even with 30%, GT2FC does not perform as well as NGE). To formally check the observation, we run further experiments for the percentages 15%, 20%, and 25% of labelled data which are in the interval [10%, 30%]. The outcome of the new experiments on D1 is 61.1230 ± 0.2900, 68.4492 ± 0.180 and 73.1105 ± 0.1391 and on D2 it is 62.2714 ± 0.3632, 74.1809 ± 0.3170 and 83.5477 ± 0.2428 respectively. Comparing the values in Tab. XVI and Tab. XVII and these new results, the boundary seems rather to be around 30%. The major conclusion is, however, that the accuracy of GT2FC is higher for large ratios of labeled data and increases as such ratio increases.

From a computational time perspective, Tab. XVIII compares the computational time of the 4 algorithms (IFCS, NGE, GT1FC, GT2FC) for one run on the same data (D2) for different ratios of labeled data (10%, 50%, 100%). The results indicate that GT2FC requires more time compared with the other algorithms, especially when dealing with more labeled data. This, however, is expected due to the steps involved in GT2FC which includes many checks related to labels of the data. In particular, IFCS and NGE use only the labeled data.

IX. ONLINE VS. BATCH LEARNING

An online learner receives a new data point x t along with the current hypothesis H t-1 , checks if the data point is covered by the current hypothesis and updates the hypothesis accordingly. Ideally the online learner performs as well as its corresponding offline version, where it can see the data for many epochs. If this happens we say that the algorithm is lossless. In this experiment, we compare the performance XIX shows that when the ratio of labeled data is below 30%, the offline mode performs relatively better, but when the labeled data is above 30%, the online version performs better. The results of the online and the offline versions are close. Therefore GT2FC can potentially perform as well as its offline version.

X. CONCLUSION

In this paper, we proposed a growing interval type-2 fuzzy classifier, called GT2FC, which is equipped with various mechanisms for online learning, quality control and data drift management. The aim is to deal with data whose distribution may change dynamically over time. To generate the type-2 fuzzy membership functions associated with the features in the rules' premises, we proposed a new semi-supervised online learning algorithm, called 2G2M. This algorithm is designed to operate online and to learn from both labeled and unlabeled data. The 2G2M parameters are optimized continuously and regularly using batches of labeled data. To maintain compactness of the rules, the GT2FC classifier uses an online feature selection algorithm, while 2G2M optimizes the clusters online. A broad range of experiments using different datasets (artificial, classic and real-world) were conducted. These experiments provided a picture on the performance of GT2FC and 2G2M algorithms under various settings. The major outcome is that the type-2 classifier performs very well. Moreover, the approach presented in this paper is in the first place illustrative to show how type-2 fuzzy systems can be developed for open-ended dynamic environments to accommodate continuous learning over time.

In the future, we will extend the present work to (i) growing generalized type-2 fuzzy classification systems and (ii) growing type-2 fuzzy classification systems where Gaussian membership functions are characterized not only by uncertain deviation as presented here, but also by uncertain mean.

Fig. 1 :Fig. 2 :

 12 Fig. 1: Type-2 fuzzy sets

2 uFig. 3 :Fig. 4 :

 234 Fig. 3: Interval type-2 fuzzy sets

Fig. 5 :

 5 Fig. 5: Uncertain mean Fig. 6: Uncertain deviation

2 )

 2 If the incoming input is labeled, then a) If the highest matching Gaussian is unlabeled, label it with the label of the input. b) If the highest matching Gaussian and the new input have different labels, then create a new Gaussian. c) If the highest matching Gaussian and the incoming input have the same label, add the contribution of the new input and update all Gaussians.

Fig. 7 :

 7 Fig. 7: Split and merge operations

Fig. 8 :Algorithm 2 :

 82 Fig. 8: Clustering of the Banana shaped dataset.

Fig. 9 :Fig. 10 :

 910 Fig. 9: Projection of a bidimensional Gaussian

  After optimization using the Merge operation (merge threshold=36.99) After optimization using the Jaccard's similarity (Threshold=0.4): the legend shows which functions are merged. The new function is assigned the smallest number (id) of the merged functions. The clusters (bottom right) are the original ones. Functions with magenta color result from merge of functions with different classes.

Fig. 11 :

 11 Fig. 11: Optimization process

Fig. 12 :

 12 Fig. 12: Effect of the selection method (Iris data)

Fig. 13 :

 13 Fig. 13: Effect of the selection method (Wine data)

Fig. 14 :

 14 Fig. 14: Effect of the selection method (Banana data)

Fig. 15 :Fig. 16 :

 1516 Fig. 15: Evolution of the current error during the training phase for different ratios of labeled data

Fig. 17 :D 2 Fig. 18 :

 17218 Fig. 17: Evolution of the current error during the training phase

Fig. 19 :Fig. 20 :Fig. 21 :Fig. 22 :

 19202122 Fig. 19: Artificial drift based on feature selection (D 1 )

TABLE I :

 I Fuzzy rules for the Banana-shaped dataset

	Rule	Antecedent	C	Antecedent	C
	1 x1 IN N(-17.66, [0.96,1.93]) ∧ x2 IN N(-3.89, [1.17,2.34])	2 x1 IN N(-17.65, [0.96, 1.92]) ∧ x2 IN N(-3.89, [1.17, 2.34])	2
	2 x1 IN N(-4.97, [1.02,2.04]) ∧ x2 IN N(1.78, [0.97,1.94])	2 x1 IN N(-11.09, [1.91, 3.82]) ∧ x2 IN N(1.61, [1.01, 2.02])	2
	3 x1 IN N(5.37, [1.32,2.65]) ∧ x2 IN N(7.78, [1.20,2.39])	1 x1 IN N(8.631, [2.076, 4.153]) ∧ x2 IN N(4.609, [2.137, 4.275])	1
	4 x1 IN N(-5.46, [1.60,3.20]) ∧ x2 IN N(-7.90, [1.65,3.30])	1 x1 IN N(-5.46, [1.60, 3.20]) ∧ x2 IN N(-7.89, [1.65, 3.30])	1
	5 x1 IN N(-11.88, [1.14,2.28]) ∧ x2 IN N(1.60, [1.01,2.03])	2 x1 IN N(2.69, [0.93, 1.87]) ∧ x2 IN N(-9.00, [0.96, 1.92])	1
	6 x1 IN N(2.70, [0.94,1.88]) ∧ x2 IN N(-9.01, [0.96,1.92])	1 x1 IN N(-14.48, [1.29, 2.58]) ∧ x2 IN N(-14.74, [1.37, 2.74])	2
	7 x1 IN N(-17.18, [0.94,1.89]) ∧ x2 IN N(-9.85, [1.08,2.16])	2 x1 IN N(0.28, [0.96, 1.93]) ∧ x2 IN N(-1.477, [1.171, 2.343])	2
	8 x1 IN N(10.51, [0.98,1.96]) ∧ x2 IN N(2.78, [1.34,2.68])	1 x1 IN N(5.98, [0.93, 1.87]) ∧ x2 IN N(-6.09, [0.97, 1.94])	1
	9 x1 IN N(-14.28, [1.20,2.39]) ∧ x2 IN N(-15.12, [0.98,1.96])	2 x1 IN N(9.01, [0.91, 1.82]) ∧ x2 IN N(-3.96, [1.34, 2.68])	1
	10 x1 IN N(0.28, [0.97,1.93]) ∧ x2 IN N(-1.48, [1.17,2.34])	2
	11 x1 IN N(5.98, [0.94,1.88]) ∧ x2 IN N(-6.10, [0.97,1.94])	1
	12 x1 IN N(9.02, [0.91,1.83]) ∧ x2 IN N(-3.96, [1.34,2.69])	1
	Rule		Antecedent		C
	1 x1 IN N(-17.60, [0.968,1.93]) ∧ (x2 IN N(-2.31, [1.42,2.85]) ∨ (x2 IN N(-9.45, [2.04, 4.08]))		2
	2 (x1 IN N(-5.27, [2.62, 5.24]) ∨ x1 IN N(-13.10, [1.44,2.89])) ∧ x2 IN N(1.61, [1.01,2.02])		2
	3 x1 IN N(-13.10, [1.44,2.89]) ∧ (x2 IN N(1.61, [1.01,2.02]) ∨ x2 IN N(-15.12, [0.98,1.96]))		2
	4 x1 IN N(5.47, [1.28,2.56]) ∧ (x2 IN N(7.78, [1.19,2.39]) ∨ x2 IN N(-6.10, [0.97,1.94]))		1
	5 (x1 IN N(-5.27, [2.62, 5.24]) ∨ x1 IN N(5.470, [1.28,2.56]) ∨ x1 IN N(9.79, [1.89, 3.78]) ∧ x2 IN N(-5.30, [1.91,3.83])	1
	6 x1 IN N(2.69, [0.93,1.87]) ∧ x2 IN N(-9.45, [2.04, 4.08])			1
	7 (x1 IN N(0.28, [0.97,1.93]) ∨ x1 IN N(-17.60, [0.96,1.93])) ∧ x2 IN N(-2.31, [1.42,2.85])		2

TABLE II :

 II Datasets used to test the algorithm

	Dataset	Features Classes Instances
	Iris	4	3	150 [50 50 50]
	Wine	13	3	178 [59 71 48]
	Banana shaped 2	2	400 [200 200]

TABLE III :

 III Excerpt of the parameter settings for 2G2M resulting from GA optimization for the classic and the banana datasets.

	Parameter		Iris			Wine			Banana
		Early	Middle	Final	Early	Middle	Final	Early Middle Final
	K (maxnumber of clusters)	10	10	10	10	10	10	20	20	20
	α (learning rate)	0.25	0.25	0.25	0.25	0.25	0.25	0.01	0.01	0.01
	T Σ (closeness threshold)	3.16	4.83	5.01	14.30	10.26	10.05	3.73	5.40	5.08
	Tmerge (merge threshold)	14.74 12.12	10.13	132.33	159.33	150.67	19.5	18.14	15.05
	T split (split threshold)	9.33	2.42	5.25	6.00	15.52	10.97	6.34	9.80	10.19
	k 0 (initial Gaussians' spread) 0.14	1.31	0.009	1.72	1.99	4.05	3.18	2.81	1.15

TABLE IV :

 IV Average accuracy results using the classic datasets

	Dataset Ratio of labeled data Clusters Accuracy (%)
	Iris	10% (random)	10	89.17±0.10
		30% (random)	15	93.25±0.03
		10% (random decr.)	10	93.58±0.04
		30% (random decr.)	15	94.25±0.05
	Wine	10% (random)	10	80.28±0.33
		30% (random)	10	82.41±0.09
		10% (random decr.)	10	81.25±0.02
		30% (random decr.)	10	85.02±0.10
	Banana 10% (random)	20	97.00±0.05
		30% (random)	20	99.15±0.02
		10% (random decr.)	20	98.13±0.03
		30% (random decr.)	20	98.98±0.02
	dormitory (called iDorm)

TABLE V :

 V Execution of running 2G2M on the banana dataset

	data	labeled[label]	Matching prob.	Winner	# Gaussians	Creation
	1

  5 classes and D 2 which consists of 2 classes. D 1 has been collected over June and September, while D 2 has been collected over March and June. It is important to note that data of each month differ from that of the other month; hence notions like data drift can be studied. Tab. VI summarizes both datasets in terms of number of data points and classes. The classes have been generated by combining the output variables corresponding to 6 actuators: intensity spot light, desk and bed side lamps, window blinds, heater, and PC-based applications comprising word and media playing program. The different combinations of values are considered as classes. The classes reflect some distinct settings.

				1)	10	0
	279	1[2]	0.00021	9(2)	10	0
	280	0[2]	0.11371	10(2)	10	0
	which consists of

TABLE VI :

 VI Characteristics of the datasets

	Data set	Month 1 Month 2 Number of
					classes
	Inhabitant 1	904	561	5
	Inhabitant 2	326	995	2
	TABLE VII: Split of the iDorm datasets
	Data set Online		Testing	Testing
		Training	(Month 1)	(Month 2)
		(Month 1)
	D 1	684		220	561
	D 2	246		80	995
	TABLE VIII: Parameter evolution for the iDorm datasets
	Parameter		Stages
			Early Middle Final
	K		20	20	20
	α		0.05	0.05	0.05
	T Σ	0.75	0.39	0.85
	T merge	27.99 83.15	64.25
	T split	3.01	0.41	0.53
	k 0	4.44	0.12	0.61
	TABLE IX: Effect of the mode of data presentation on the
	accuracy (30% of data is labeled)
	Presentation mode	D 1	D 2
	Random		77.59 88.06
	Random decreasing 66.21 72.21

TABLE X :

 X Effect of the mode of data presentation on the accuracy (50% of data is labeled)

	Presentation mode	D 1	D 2
	Random	80.98 94.91
	Random decreasing 67.76 78.80

  TableIXand Tab. X present the classification results. Clearly the GT2FC algorithm performs better in the case of random mode of labeled data presentation independently of the data set used. Note that the results are averaged over 100 runs.3) Effect of the Maximum Number of Gaussians: To observe the effect of changing the maximum number of clusters

TABLE XI :

 XI Effect of the maximum number of clusters (30% of data is labeled, random selection mode)

	Max. Clusters	D 1	D 2
	5	74.31 70.82
	10	77.25 88.06
	20	78.18 92.98
	30	78.91 93.67
	40	82.24 95.48
	50	81.42 96.04

TABLE XII :

 XII Feature ordered by importance

		Features
	Batch 1 3 1 8 2 7 5 4 6
	Batch 2 1 8 2 3 4 5 6 7
	Batch 3 1 2 3 8 7 4 5 6
	Batch 4 8 1 2 7 3 4 5 6
	TABLE XIII: Features of the iDorm datasets
	Feature	Id Feature	Id
	InternalLightLevel	1 ExternalLightLevel	2
	InternalTemperature 3 ExternalTemperature 4
	ChairPressure	5 BedPressure	6
	Occupancy	7 Hour	8

TABLE XIV :

 XIV Fuzzy rules for D2 ∧ x2 IN N(81.115, [0.863,1.726]) ∧ x3 IN N(22.809, [0.851,1.703]) ∧ x4 IN N(7.443, [0.853,1.706]) ∧ x5 IN N(-0.115, [0.863,1.726]) ∧ x6 IN N(1.115, [0.863,1.726]) ∧ x7 IN N(1.000, [0.850,1.699]) ∧ x8 IN N(11.564, [0.544,1.088]) 1 2 x1 IN N(67.000, [0.850,1.699]) ∧ x2 IN N(76.589, [0.714,1.427]) ∧ x3 IN N(22.736, [0.850,1.699]) ∧ x4 IN N(7.500, [0.850,1.699]) ∧ x5 IN N(0.000, [0.850,1.699]) ∧ x6 IN N(1.000, [0.850,1.699]) ∧ x7 IN N(1.000, [0.850,1.699]) ∧ x8 IN N(11.242, [0.654,1.309]) 1 3 x1 IN N(8.733, [2.425,4.850]) ∧ x2 IN N(0.683, [0.869,1.738]) ∧ x3 IN N(23.556, [0.677,1.353]) ∧ x4 IN N(8.158, [0.706,1.413]) ∧ x5 IN N(0.000, [0.643,1.286])

	Rule	Antecedent	C
	1 x1 IN N(83.655, [0.964,1.928]) ∧ x6 IN N(1.000, [0.643,1.286]) ∧ x7 IN N(1.000, [0.643,1.286]) ∧ x8 IN N(18.645, [1.363,2.726])	2
	• • •	• • •	• • •
	18 x1 IN N(13.000, [1.143,2.286]) ∧ x2 IN N(82.000, [1.143,2.286]) ∧ x3 IN N(24.400, [1.143,2.286]) ∧ x4 IN N(8.500, [1.143,2.286]) ∧ x5 IN N(0.000, [1.143,2.286])	2
	∧ x6 IN N(1.000, [1.143,2.286]) ∧ x7 IN N(1.000, [1.143,2.286]) ∧ x8 IN N(13.112, [0.511,1.022])
	19 x1 IN N(0.000, [1.143,2.286]) ∧ x2 IN N(1.000, [1.143,2.286]) ∧ x3 IN N(23.260, [1.143,2.286]) ∧ x4 IN N(8.500, [1.143,2.286]) ∧ x5 IN N(0.000, [1.143,2.286])	2
	∧ x6 IN N(0.000, [1.143,2.286]) ∧ x7 IN N(1.000, [1.143,2.286]) ∧ x8 IN N(19.896, [0.511,1.022])
	20 x1 IN N(6.000, [0.303,0.606]) ∧ x2 IN N(0.745, [0.520,1.039]) ∧ x3 IN N(23.587, [0.323,0.647]) ∧ x4 IN N(8.391, [0.443,0.886]) ∧ x5 IN N(0.000, [0.303,0.606])	2
	∧ x6 IN N(1.000, [0.303,0.606]) ∧ x7 IN N(1.000, [0.303,0.606]) ∧ x8 IN N(19.194, [0.438,0.876])

TABLE XV :

 XV Fuzzy rules for D2 after merge of similar fuzzy sets

	Rule	Antecedent	C
	1 x1 IN N(83.655, [0.964,1.928]) ∧ x2 IN N(81.115, [0.863,1.726]) ∧ x3 IN N(22.772, [0.601,1.203] ∧ x4 IN N(7.472, [0.602,1.204]) ∧ x8 IN N(11.432, [0.418,0.836])	1
	2 x1 IN N(67.000, [0.850,1.699]) ∧ x2 IN N(76.589, [0.714,1.427]) ∧ x3 IN N(22.772, [0.601,1.203] ∧ x4 IN N(7.472, [0.602,1.204]) ∧ x8 IN N(11.432, [0.418,0.836])	1
	3 x1 IN N(8.733, [2.425,4.850]) ∧ x2 IN N(0.729, [0.446,0.892]) ∧ x3 IN N(23.562, [0.282,0.565]) ∧ x4 IN N(8.356, [0.340,0.681]) ∧ x8 IN N(19.444, [0.323,0.646])	2
	• • •	• • •	• • •
	18 x1 IN N(13.000, [1.143,2.286]) ∧ x2 IN N(82.000, [1.143,2.286]) ∧ x3 IN N(24.400, [1.143,2.286]) ∧ x4 IN N(8.356, [0.340,0.681]) ∧ x8 IN N(13.112, [0.511,1.022])	2
	19 x1 IN N(0.000, [1.143,2.286]) ∧ x2 IN N(1.000, [1.143,2.286]) ∧ x3 IN N(23.562, [0.282,0.565]) ∧ x4 IN N(8.356, [0.340,0.681]) ∧ x8 IN N(19.444, [0.323,0.646])	2
	20 x1 IN N(6.000, [0.303,0.606]) ∧ x2 IN N(0.729, [0.446,0.892]) ∧ x3 IN N(23.562, [0.282,0.565]) ∧ x4 IN N(8.356, [0.340,0.681]) ∧ x8 IN N(19.444, [0.323,0.646])	2

TABLE XVIII :

 XVIII Computational time

	Algorithm Ratio of labeled data
		0.1	0.5	1
	IFCS	0.91	3.09	8.15
	NGE	0.18	0.20	0.23
	GT1FC	11.05 14.37 14.54
	GT2FC	14.50 18.66 19.52
	accuracy of the proposed online GT2FC against its offline
	version. Table

TABLE XVI :

 XVI GT2FC vs. other online classifiers: Case D1 17±5.03 88.39±3.28 86.64±1.16 86.25±0.42 86.12±0.27 85.92±0.10 NGE 88.08±2.34 87.37±0.10 87.40±0.04 87.42±0.02 87.43±0.01 87.43±0.03 GT1FC 59.12±0.30 89.71±0.13 93.68±0.05 96.20±0.01 96.68±0.01 97.01±0.01 GT2FC 60.19±0.34 89.44±0.10 95.50±0.04 96.89±0.01 96.78±0.01 97.00±0.01

	Algorithm		Ratio of labeled data in the training data
		0.1	0.3	0.5	0.7	0.9	1
	IFCS	76.14±2.38 75.33±1.12 75.49±0.68 75.27±0.27 75.24±0.27 75.22±0.03
	NGE	82.27±3.62 83.83±2.81 79.63±5.22 75.54±3.43 74.31±0.05 74.33±0.05
	GT1FC	55.43±0.23 75.36±0.15 80.62±0.02 81.42±0.01 82.88±0.01 83.13±0.01
	GT2FC	60.28±0.24 79.55±0.02 80.73±0.01 81.65±0.01 82.88±0.01 83.76±0.01
		TABLE XVII: GT2FC vs. other online classifiers: Case D2
	Algorithm		Ratio of labeled data in the training data
		0.1	0.3	0.5	0.7	0.9	1
	IFCS	91.

TABLE XIX :

 XIX Online vs. batch (D2)

	Algorithm	Ratio of labeled data in the training data
	0.1	0.3	0.5	0.7	0.9	1
	GT2FC (Online) 60.19±0.34 89.44±0.10 95.50±0.04 96.89±0.01 96.78±0.01 97.00±0.01
	GT2FC (Offline) 70.05±0.31 93.23±0.04 94.86±0.03 96.20±0.01 96.46±0.01 96.68±0.01

IEEE TRANSACTIONS ON FUZZY SYSTEMS, VOL. XXXX, NO. XXXX, XXXXX 2013

ACKNOWLEDGMENT

The authors wish to thank very much Hani Hagras for kindly providing the iDorm data.


The method of quarter-squares

The method of quarter-squares is a multiplication method which makes use of the identity

ab = 1 4 (a + b) 2 -(a -b) 2 .
If we possess a table of squares, and wish to compute the product ab, it is then sufficient to compute a + b, a -b, to look up the table for these two values, to subtract the values read in the table, and to divide the result by 4. This seems complex, but for large numbers it is more efficient than to compute directly the product. 1There have been a number of tables of squares around, in particular those of Ludolf published in 1690 [31], and those published by Séguin in 1801 and giving the squares up to 10000. But these authors did mostly not have multiplications in mind, although Ludolf showed how squares could be used to compute a multiplication. At the beginning of the 19th century, the method of quarter-squares was mentioned in passing by Laplace in 1809 [9, p. 261] and Gergonne in 1816 [13, pp. 159-160], but they did not produce tables.

2 The first tables of quarter-squares (1817)

In 1817, Voisin [51] and Bürger [START_REF] Anton | Tafeln zur Erleichterung in Rechnungen für den allgemeinen Gebrauch eingerichtet[END_REF] published independently the first tables of quartersquares. Voisin and Bürger both understood that a table of squares could be useful for multiplications, but they went one step beyond, and removed the need to divide the difference of the squares by 4. Their tables gave the quarter-squares for all integers up to 19999 (Bürger) and 20000 (Voisin).

A table of quarter-squares is also very advantageous with respect to space. Such a table is a linear table, with only one entry. With slightly more work than a mere table of multiplication, it is possible with a table of quarter-squares to do computations that would require many thousands of pages with a conventional table of multiplication, such as Crelle's table [START_REF] Crelle | Rechentafeln, welche alles Multipliciren und Dividiren mit Zahlen unter Tausend ganz ersparen, bei grösseren Zahlen aber die Rechnung erleichtern und sicherer machen[END_REF].

In 1820, in the second edition of his Philosophy of arithmetic [30, pp. 246-257], John Leslie described tables of quarter-squares, and in particular Voisin's table, of which he gave an excerpt up to 2000. Leslie expressed the hope that someone would compute a table up to 200000.

Centnerschwer's table (1825)

Jakub Centnerszwer (1798-1880) was a Polish mathematician and teacher of Jewish origin [START_REF] Centnerschwer | Encyklopedyja powszechna[END_REF]. He published several works, among them a table of quarter-squares in 1825 and a coin conversion table in 1842 [START_REF] Centnerszwer | Nowe tablice zamiany monety polskiej na rossyjska i odwrotnie[END_REF]. His son was the publisher and bookseller Gabriel Centnerszwer (1841Centnerszwer ( -1917) ) and his grandson was the chemist Mieczysław Centnerszwer (1874Centnerszwer ( -1944)).

The table of quarter-squares was published in German under the germanized name Centnerschwer [START_REF] Centnerschwer | Neu erfundene Multiplikations-und Quadrat-Tafeln, vermittelst welcher man die Produkte aller vierziffrigen und die Wurzeln aller fünfziffrigen Zahlen sehr leicht finden kann, wie auch zur Erleichterung anderer mathematischen Rechnungen[END_REF]. This table gives the quarter-squares from 0 up to 19999 on 40 pages, whereas Voisin needs 123 pages and Bürger 80 pages for the same range.

At first sight, Centnerschwer's table appears confusing, but its usage is in fact simple. In order to find the quarter-square of n = 100a + b, one first locates the column marked a (the second line, just above the line with I's and II's) and the line b. At their intersection, the table gives f (a, b) = n2 400 . For instance, 2 for n = 8763, we find the value 191975. This is not the final result, but all the digits except the last two. Then, two small tables (not reproduced here) 3 give the last two digits as a function of m = n mod 200, or more precisely as a function of n mod 100 and of the type of column in which a appears, that is "I" or "II." For m = 163, this table gives 42, as m 2 4 = 6642.25. The final result is therefore 191975|42.

The main table can also be used to find the square of any integer up to 9999. Indeed, when b is even, that is when b = 2c (0 ≤ c < 50), then we have This is then used as follows: if one wishes to compute the square of x = 100p + z, we distinguish two cases: 1) z < 50 and 2) z ≥ 50. In the first case, we will take a = 2p, and in the second case we will take a = 2p + 1. For example, if we wish to compute 3744 2 , we have p = 37 and c = z = 44. Therefore, a = 74, we are in a column marked "I" and we look up the line b = 2c = 88, where we find 140175. These are all the digits of 3744 2 , except the last two. The latter are found in a separate table (not reproduced here), as a function of the last two digits of 3744, as all squares of numbers ending with 44 end with the same two digits. The table gives 36, so that 3744 2 = 140175|36.

f (a, b) = (100a + 2c) 2 400 (1) = (100(a/2) + c) 2 100 = g(a/2, c) (2)
If we wish to compute 4573 2 , we have p = 45 and c = z -50 = 23. Therefore, a = 91, we are in a column marked "II" and we look up the line b = 2c = 46, where we find 209123. Like above, the last two digits of the square are found in a separate table as a function of 73, so that eventually 4573 2 = 209123|29.

Incidentally, it is interesting to observe that the way Centnerschwer splits the results of his table bears some analogy with the organization of Kulik's table of quarter-squares published in 1851 [START_REF] Philipp | Neue Multiplikationstafeln : ein unentbehrliches Hülfsmittel für Jedermann, um schnell, sicher und ohne Ermüdung zu rechnen[END_REF], and thus also of Blater's There have also been several applications of quarter-squares for mechanical aids. In 1829, Schiereck invented a calculating machine based on quarter-squares [START_REF] Weiss | [END_REF] and in 1841 he devised an instrument for the measurement of the area of triangles, useful in surveying, and also based on quarter-squares [START_REF] Friedrich | Beschreibung des Pediometers, eines Instruments, um den Flächeninhalt in Karten ohne Rechnung zu erhalten[END_REF][START_REF] Haeberlin | Die Viertelquadratemethode und das Pediometer des Joseph Friedrich Schiereck[END_REF].

In a book published in 1857, Edward Sang also suggested the use of quarter-squares for multiplications [6, pp. 50-51].

The use of quarter-squares declined in the first half of the 20th century [START_REF] David | Tables of quarter-squares, sociologic[al] applications, and contributions of George W. Jones[END_REF], but Bojko in 1909 [2] and Plassmann in 1933 [START_REF] Plassmann | Tafel der Viertel-Quadrate aller Zahlen von 1 bis 20009 zur Erleichterung des Multiplizierens vierstelliger Zahlen[END_REF] each published tables of quarter-squares up to 20000. In the 1950s, however, new applications of the quarter-squares method for multiplication on analog devices surfaced, and this prompted their use for the implementation of multiplication in digital processors [START_REF] Jayashree | On binary multiplication using the quarter square algorithm[END_REF][START_REF] Johnson | A digital quarter square multiplier[END_REF].

Finally, we mention that tables of triangular numbers can also be used in a way similar to quarter-squares in order to facilitate the multiplications [8].

Figure 1: An excerpt of Centnerschwer's table [START_REF] Centnerschwer | Neu erfundene Multiplikations-und Quadrat-Tafeln, vermittelst welcher man die Produkte aller vierziffrigen und die Wurzeln aller fünfziffrigen Zahlen sehr leicht finden kann, wie auch zur Erleichterung anderer mathematischen Rechnungen[END_REF]. In the first column, notice that the prefix 90 was misplaced at 90330 instead of at 90300.

  If a = 2p, then f (a, b) = (100p + c) 2 100 . If a = 2p + 1, then f (a, b) = (100p + 50 + c) 2 100 .

  table published in 1887 [1] and Bojko's table published in 1909 [2].

Table Range

 Range

			Pages Density
	Voisin (1817)	20000	123	162.6
	Bürger (1817)	20000	80	250.0
	Centnerschwer (1825)	20000	40	500.0
	Merpaut (1832)	40000	400	100.0
	Kulik (1851)	30000	40	750.0
	Laundy (1856)	100000	200	500.0
	Blater (1887)	200000	200	1000.0
	Bojko (1909)	20000	20	1000.0
	Plassmann (1933)	20009	200	100.0

Table 1 :

 1 A comparison of the main tables of quarter-squares. The density is the ratio of the range by the number of pages. The tables which pack the greatest ranges in the smallest number of pages are those of Blater and Bojko.

For a survey of the quarter-square method, see the articles by McFarland[START_REF] David | Tables of quarter-squares, sociologic[al] applications, and contributions of George W. Jones[END_REF][START_REF] David | Quarter-squares revisited: earlier tables, division of labor in table construction, and later implementations in analog computers[END_REF] and Weiss[START_REF] Weiss | Die Multipliziertafeln: ihre Ausgestaltung und Verwendung[END_REF].

This example is given by Centnerschwer's on page xxviii.

This table appears apparently on a foldout, and was not digitized by Google.

Note on the titles of the works: Original titles come with many idiosyncrasies and features (line splitting, size, fonts, etc.) which can often not be reproduced in a list of references. It has therefore seemed pointless to capitalize works according to conventions which not only have no relation with the original work, but also do not restore the title entirely. In the following list of references, most title words (except in German) will therefore be left uncapitalized. The names of the authors have also been homogenized and initials expanded, as much as possible.The reader should keep in mind that this list is not meant as a facsimile of the original works. The original style information could no doubt have been added as a note, but we have not done it here.


7.5 8.0 8.5 9.0 9.

The method of quarter-squares

The method of quarter-squares is a multiplication method which makes use of the identity

ab = 1 4 (a + b) 2 -(a -b) 2 .
If we possess a table of squares, and wish to compute the product ab, it is then sufficient to compute a + b, ab, to look up the table for these two values, to subtract the values read in the table, and to divide the result by 4. This seems complex, but for large numbers it is more efficient than to compute directly the product. 1There have been a number of tables of squares around, in particular those of Ludolf published in 1690 [30], and those published by Séguin in 1801 and giving the squares up to 10000. But these authors did mostly not have multiplications in mind, although Ludolf showed how squares could be used to compute a multiplication. At the beginning of the 19th century, the method of quarter-squares was mentioned in passing by Laplace in 1809 [8, p. 261] and Gergonne in 1816 [12, pp. 159-160], but they did not produce tables.

2 The first tables of quarter-squares (1817)

In 1817, Voisin [50] and Bürger [START_REF] Anton | Tafeln zur Erleichterung in Rechnungen für den allgemeinen Gebrauch eingerichtet[END_REF] published independently the first tables of quartersquares. Voisin and Bürger both understood that a table of squares could be useful for multiplications, but they went one step beyond, and removed the need to divide the difference of the squares by 4. Their tables gave the quarter-squares for all integers up to 19999 (Bürger) and 20000 (Voisin).

More exactly, when a number is odd, its quarter-square is of the form n + 0.25 and Voisin and Bürger only gave the value n. So if a and b are both odd or both even, the values of the quarter-squares are given exactly. If one of the integers is odd and the other is even, both quarter-squares are in default by 0.25, but the difference of these two values is correct. So, although the tables of Voisin and Bürger are not totally accurate for a table of squares, they serve the purpose of a table of multiplication. If one wished to use them as a table of squares, one would need to remember to add 1 to the result multiplied by 4, whenever the value entered is odd.

A table of quarter-squares is also very advantageous with respect to space. Such a table is a linear table, with only one entry. With slightly more work than a mere table of multiplication, it is possible with a table of quarter-squares to do computations that would require many thousands of pages with a conventional table of multiplication, such as Crelle's table [START_REF] Crelle | Rechentafeln, welche alles Multipliciren und Dividiren mit Zahlen unter Tausend ganz ersparen, bei grösseren Zahlen aber die Rechnung erleichtern und sicherer machen[END_REF].

In 1820, in the second edition of his Philosophy of arithmetic [29, pp. 246-257], John Leslie described tables of quarter-squares, and in particular Voisin's table, of which he gave an excerpt up to 2000. Leslie expressed the hope that someone would compute a table up to 200000.

Later tables of quarter-squares

A number of other tables of quarter-squares were published during the 19th century (table 1). Centnerschwer [4] published a table of quarter-squares up to 20000 in 1825, Kulik in 1833 and 1851 (up to 30000) [START_REF] Philipp | Toasirtafeln, zur leichtern Berechnung des Längen-Flächenund Kubik-Inhaltes und der verschiedenen Münz-Maß-und Gewichts-Beträge[END_REF][START_REF] Philipp | Neue Multiplikationstafeln : ein unentbehrliches Hülfsmittel für Jedermann, um schnell, sicher und ohne Ermüdung zu rechnen[END_REF], Merpaut in 1832 (up to 40000) [33], Laundy in 1856 [27], and Blater in 1887 [1]. Laundy's table gave the quarter-squares up to 100000, whereas Blater extended it to 200000. In 1836, Galbraith published a small table of quarter-squares in a more general collection of tables [START_REF] Galbraith | New and concise general tables for computing the obliquity of the ecliptic[END_REF]. This table was probably borrowed from Voisin's table.

In the preface of his table of quarter-squares [27, p. iv], Laundy also mentions that Peter Gray had in his possession a manuscript of a table of quarter-squares extending to 200000 by Shortrede, but that table was never published.

There have also been several applications of quarter-squares for mechanical aids. In 1829, Schiereck invented a calculating machine based on quarter-squares [START_REF] Weiss | Die Rekonstruktion der Rechenmaschine von Schiereck 1829[END_REF] and in 1841 he devised an instrument for the measurement of the area of triangles, useful in surveying, and also based on quarter-squares [START_REF] Friedrich | Beschreibung des Pediometers, eines Instruments, um den Flächeninhalt in Karten ohne Rechnung zu erhalten[END_REF][START_REF] Haeberlin | Die Viertelquadratemethode und das Pediometer des Joseph Friedrich Schiereck[END_REF].

In a book published in 1857, Edward Sang also suggested the use of quarter-squares for multiplications [5, pp. 50-51].

The use of quarter-squares declined in the first half of the 20th century [START_REF] David | Tables of quarter-squares, sociologic[al] applications, and contributions of George W. Jones[END_REF], but Bojko in 1909 [2] and Plassmann in 1933 [START_REF] Plassmann | Tafel der Viertel-Quadrate aller Zahlen von 1 bis 20009 zur Erleichterung des Multiplizierens vierstelliger Zahlen[END_REF] each published tables of quarter-squares up to 20000. In the 1950s, however, new applications of the quarter-squares method for multiplication on analog devices surfaced, and this prompted their use for the implementation of multiplication in digital processors [START_REF] Jayashree | On binary multiplication using the quarter square algorithm[END_REF][START_REF] Johnson | A digital quarter square multiplier[END_REF].

Finally, we mention that tables of triangular numbers can also be used in a way similar to quarter-squares in order to facilitate the multiplications [7]. 4 Plassmann Joseph Plassmann (1859-1940) was a professor of astronomy in Munster, Germany. He made observations of variable stars and published a number of popular works in astronomy, in particular his Himmelskunde : Versuch einer methodischen Einführung in die Hauptlehren der Astronomie in 1898.

In 1933, Plassmann published his table of quarter-squares, which could also be used to find squares, or square roots. In the introduction to his table, Plassmann also gives a number of developments for various constants, in order to make it easier to multiply by these constants. There is an overlap between one double page and the next one. The first double page gives the quarter-squares from 0 to 209. The second double page gives the quarter-squares from 200 to 409, the third double page from 400 to 609, and so on, the last double page giving the quarter-squares from 19800 to 20009.

Quarter-squares are given in full. For instance, on the last double page, we find the quarter-square of 19834 which is given at the intersection of line 1983 and column 4: 98346889.

Some of the values are appended with a dot, meaning that the exact quarter-square is not an integer, but that integer plus 0.25. For instance, the quarter-square of 19833 is given as "98336972." meaning that its real value is 98336972.25.

Plassmann's table also gives the squares. Each quarter-square is in fact the square of another number. This is of course also true of other tables of quarter-squares, but Plassmann's table provides an explicit and easy access to these squares. Such an explicit access could have been provided by Merpaut or Laundy. Using q(x) for the exact (noninteger) quarter-square, we have q(10n) = 25n 2 = (5n) 2 . Consequently, the first column of every double page of Plassmann's table gives the squares of integers increasing by steps of 5. On the last double page, the first column gives the squares of 9900, 9905, 9910, 9915, etc. and these values are given in the last column at the right. The nine remaining values of a line are also squares, since q(10n + m) = 25n 2 + m 2 4 + 5nm = (5n + m/2) 2 . The first of the two lines at the bottom give the values 0.0, 0.5, 1.0, 1.5, . . . , 4.5, which are the values of m/2. Therefore, the first line of the last double page gives the squares of 9900, 9900.5, 9901, 9901.5, 9902, . . . , up to 9904.5. The second line gives the squares of 9905, 9905.5, . . . Plassmann does not give any historical background and we do not know which other tables of quarter-squares he had seen, if any. The fact that Plassmann gives the values in full may mean that he had actually not seen the more condensed tables of Kulik or Blater, for instance.

Figure 1 : 6 Figure 2 :

 162 Figure 1: Excerpt of Plassmann's table of quarter-squares.

Figure 3 :

 3 Figure 3: Excerpt of Plassmann's table of quarter-squares.

Table Range

 Range

			Pages Density
	Voisin (1817)	20000	123	162.6
	Bürger (1817)	20000	80	250.0
	Centnerschwer (1825)	20000	40	500.0
	Merpaut (1832)	40000	400	100.0
	Kulik (1851)	30000	40	750.0
	Laundy (1856)	100000	200	500.0
	Blater (1887)	200000	200	1000.0
	Bojko (1909)	20000	20	1000.0
	Plassmann (1933)	20009	200	100.0

Table 1 :

 1 A comparison of the main tables of quarter-squares. The density is the ratio of the range by the number of pages. The tables which pack the greatest ranges in the smallest number of pages are those of Blater and Bojko.

5

  Structure of Plassmann's table and reconstructionPlassmann's table gives the quarter-squares of all integers from 0 to 20009 and spans 200 pages. A comparison with Laundy's table shows that the arrangement of the values is practically the same, only that Plassmann puts on two pages two fifths of what Laundy puts on one page. Each double page of Plassmann's table covers a range of 210 values, on 21 lines of 10 columns.

For a survey of the quarter-square method, see the articles by McFarland[START_REF] David | Tables of quarter-squares, sociologic[al] applications, and contributions of George W. Jones[END_REF][START_REF] David | Quarter-squares revisited: earlier tables, division of labor in table construction, and later implementations in analog computers[END_REF] and Weiss[START_REF] Weiss | Die Multipliziertafeln: ihre Ausgestaltung und Verwendung[END_REF].

Note on the titles of the works: Original titles come with many idiosyncrasies and features (line splitting, size, fonts, etc.) which can often not be reproduced in a list of references. It has therefore seemed pointless to capitalize works according to conventions which not only have no relation with the original work, but also do not restore the title entirely. In the following list of references, most title words (except in German) will therefore be left uncapitalized. The names of the authors have also been homogenized and initials expanded, as much as possible.The reader should keep in mind that this list is not meant as a facsimile of the original works. The original style information could no doubt have been added as a note, but we have not done it here.