Categorizing classes of signals by means of fuzzy gradual rules

1 Introduction

Signal functions, such as time series, medical ECG's, are usu­ ally viewed as analytical mappings. Then, a precise represen­ tation is often used. Even when uncertainty is dealt with, it is supposed to pervade parameters of the analytical models, leading to probabilistic or interval-based processing. The main objective ofthis paper is to propose an alternative to this classical type of approaches by investigating the interest of a special kind of fuzzy « if .. then » rules, named gradual rules [Dubois and Prade, 1992; 1994 ], for developing imprecise representations. Actually, the proposed strategy relies on in­ terpolative reasoning. By specifying the interpolative repre­ sentation with gradual rules, there is no need to choose an analytic form for the interpolator and an imprecise model is directly obtained from the constraints expressed by the rules. The proposed rule-based approach is an alternative to works based on fuzzy polynomials [Lowen, 1990] or fuzzy spline interpolation, e.g. [Kawaguchi and Miyakoshi, 1998], which rely on fuzzy-valued functions and still depend on the analyt­ ical form of the interpolant.

What is supposed to be known, in a precise or in an imprecise way, is the behaviour of the function at some reference points, the problem being to interpolate between these points. Figure 1 illustrates our purpose ofbuilding an imprecise mod­ el in a case where the points on which interpolation is based are imprecise and modelled by rectangular areas.

So, we are no longer looking for a function, but for a relation linking the variable to the possible value of the function. Then, this relation is represented by its graphr defined on the Cartesian product X x Z (where X is the input domain, and Z the function range). A similar approach used in automated control, recently proposed in [Sala and Albertos, 2001 ], also considers the building of uncertain fuzzy models in the set­ ting of the approximation of multi-valued functions called "ambiguous functions".

The paper, after some brief background on gradual rules, dis­ cusses the design of the imprecise interpolative representa­ tion in terms of gradual rules, constrained by precise or imprecise reference points. The proposed approach is then applied to the classification of time series. Moreover, a more powerful representation framework, based on fuzzy sets of gradual rules (called fuzzy gradual rules for short) is pro­ posed. It enables us to describe areas through which it is not completely possible that the function may go.

2 Interpolation and gradual rules

The idea of imprecise interpolation suggested above is based on constraints to be satisfied. Namely the results of the inter­ polation should agree with the reference points. These con­ straints define the graph f of a relation on Xx Z.

We first consider the case of precise interpolation points P; with coordinates (x;, z;), i = 1, ... , n. Then the relationf should satisfy:

fori = I, ... , n. Without any further constraint on the nature of the interpolation, we only have:

Thus each interpolation point induces the constraint "If x = X; then z = z;'', represented by the rule (x = x) ~ (z = z;) where ~ is material implication. The relation f is thus obtained as the conjunction:

This relation is extremely imprecise since there is no con­ straint at all outside the reference points. Instead of using a precise type of interpolation function, one may use fuzzy rules in order to express constraints in the vicinity of the in­ terpolation points. The idea is to use rules of the form "the closer xis to x;, the closerz is toz;". The extension of equation ( 1) to gradual rules provides the following expression for the graph r:

where ~ represents Rescher-Gaines implication (a ~ b = 1

if a~ band a~ b = 0 if a > b), and flclose to x.Cx) is the degree I of truth of the proposition '):is close to x;".

We have just to define what is meant by "close to" . LetA; de­ note the fuzzy set of values close to x;. It is natural to set f..LA .(x) = I ifx =x; and to assume that the membership degree to A; decreases on each side of x; with the distance tox;. How­ ever A; will not be necessarily symmetrical. The simplest so­ lution consists in choosing triangular fuzzy sets with a support denoted by [x;-, x/]. In a similar way, the closeness to z; will be modelled by a triangular fuzzy set B; with modal value z; and support [z;-, z/] . Then the interpolation relation only depends on 4n parameters x;-, x/ z;-, z/ for n interpola­ tion points. In order to simplify their tuning, we further as­ sume that at most two rules are simultaneously fired at each point of the input domain, i.e. X;~ X;+ 1- and x/ ~ X;+ 1, i = 1, .. . , n-1. For increasing reference points (i.e. x;<X;+I and z;<z;+I> i =I , ... , n-1), it has been established in [Galichet et a!., 2002] that the interpolation graph is made of connected 4sided areas (as pictured in figure 2) when the following con­ straints hold between the parameters:

Similar relationships can be obtained when considering de­ creasing reference points. These constraints can be related to consistency requirements between gradual rules [Dubois et a!. , 1997] , ensuring the non emptiness of the image of each in­ put point via the relation r .

Figure 2 pictures the interpolation graph which is obtained with three interpolation points, and thus three gradual rules whose Ai's and Bi 's also appear in figure 2. The partitioning of X is obtained by cutting the intervals l':;, xi+I] into three equal parts, i.e. xi+ I- - X; = x/- x i+ I- = xi+ I - x/, as illustrat­ ed by the parameters which define the fuzzy sets A;. The ex­ treme values z 1 - and z 3 + are also predefined. Lastly, the other parameters can be obtained by solving the system of equa­ tions derived from (3) and (4).

This approach straightforwardly extends to imprecise refer­ ence points provided that trapezo'idal membership functions are used in place of triangular ones (see figure 3).

3 Classification of time series

Our purpose is now to illustrate how the imprecise interpola­ tive representation framework can be used to classify time se­ ries, see, e.g. [Kadous, 2002]. Supervised classification is assumed, contrary to clustering techniques whose recent de­ velopments are often based on hidden Markov models [Bis­ was et a!., 1998; Li, 2000). The proposed experiment deals with the «Control-Chart» database, freely available from the UCI Data Archive [UCI KDD Archive] . It is a 6-class prob­ lem, with 100 examples of each class, a prototype of each class being presented in figure 4. A categorization of process trends, based on types of variation, is also adopted in qualita­ tive reasoning and model-based diagnosis [Colomer et al. , 2002).

Given an unlabeled time series, the aim of the classification is to decide to which class it belongs. The idea behind the pro­ posed methodology consists in developing an imprecise mod­ el of each class. Then, the time series to classify will be assigned to the class whose model presents the maximal ade­ quacy with the temporal data under consideration. The impre­ cise models are specified using gradual rules as advocated in the previous section.

In figure 5, ten examples of class 5 are plotted simultaneous­ ly. It clearly shows that the reference points are no longer pre­ cise. In this context, triangular membership functions are replaced by trapezoidal membership functions whose cores delimit the rectangular areas associated with the imprecise reference points. According to this slight modification, the graph plotted in figure 5 is obtained from two gradual rules, i.e. A 1 ~ B 1 and A2~B2 . It can be shown that the constraints on the graph shape expressed by equations (3) and ( 4) are still valid.

The model so built can be further improved by truncating the upper and lower parts of the quadrangle-shaped graph. An easy strategy to implement the graph cutting consists in add­ ing a new rule that directly translates the interval-based con­ straint "If t E [a1, a2] then z E [b I> b2]" where al> a2, b 1 and b2 are defined in figure 5. Such an approach results in the final graph given in figure 6.

Figure 7 and 8 present the implemented models for two others classes. The first one associated with class 3 is based on ref­ erence points whose imprecision is only relative to the output. Using strong partitions with triangular input membership functions and trapezoidal output ones, imprecise linear inter­ polation is obtained by means of the two rules A 1 ~B 1 and A2~B2.

Concerning cyclic time series (figure 8), the non-monotonic underlying behavior induces some difficulties in the model­ ling process. Actually, closeness on the right and on the left of the reference points must be handled in different ways. It means that two distinct fuzzy subsets are required for correct­ ly dealing with each reference point. In this framework, the imprecise models of figure 8 is composed of 9 gradual rules.

Imprecise models are built for the six classes so that the graphs include all the points that compose the training time series ( 10 for each class). The classification of a time-series, given as a collection of points (ti, zJ, ti = i = 1, ... , 60, is then carried out according to its adequacy with the class models. The latter is determined from the number of points of the time series under consideration that belong to the graph of each model, that is:

where r 1 denotes the model graph of the/' class. The final decision is then to assign the time series, supposed unlabeled, to the class that maximizes A),}= 1, ... , 6. Applying this strategy to classify the 600 available examples, perfect classifica­ tion is obtained, i.e. the error rate is null for the training examples but also for the test time series. This result is better than the one obtained with other approaches of the same pro­ blem [Keogh and Kasetty, 2002; Nanopoulos et al., 2001]. It is however important to be cautious about this good perfor­ mance. Indeed, the discrimation between some classes is not robust. This point is illustrated by figure 9 in the case of clas­ ses 3 and 5 which are difficult to differentiate. The adequacy between the I 00 time series of class 3 and models of classes 3 and 5 is plotted. It can be stated that, for many time series, the difference between both obtained scores is small, which means that a slight modification of the models would proba­ bly result in different final decisions. Actuall)', an important intersection between both models induces a loss of the discri­ mination power of the adequacy index. In this framework, one may think of improving the robustness of the classifica­ tion by refining the imprecise models. One possible strategy is then to introduce some membership degrees in the four si­ ded areas while keeping their support unchanged. This can be made by using fuzzy sets of gradual rules as shown now.

Number of points that belong to the models ...

4 Interpolative fuzzy graph

According to the previous sections, it is clear that given a set of rules, i.e. a set of reference points, a collection of crisp graphs can be obtained by varying the support parameters of the A/s and/or the B/s. Moreover, inclusion properties be­ tween the built graphs can be exhibited for controlled varia­ tions of the supports as expressed by the following statements.

where rand r* are the graphs associated respectively with rules Ai ~Bi andAi* ~ Bi. Indeed, (x, z) E r * means that Vi, Ai*(x) ~ Bi(z). According to the assumption that Vi, Ai ~A;*, it follows that Vi, Ai(x) ~ Bi(z) which results in (x, z) E r.

P2: If Bi * ~ Bi, i=I, .. . , n, then r* c r,

where r and r* are now the graphs associated respectively with rules Ai ~ Bi and Ai ~ B i*. Indeed, (x, z) E r* if and only if Vi, A;(x) :=:; B;*(z). Since Vi, B;* ~ B;. it follows that Vi, A;(x) :=:; B;(z), i.e. (x, z) E r.

The combination of P 1 and P2 leads to:

P3 : If A;~ A;* andB; * ~ B;, i=1, ... , n, then r* ~ r, where r and r* are now the graphs respectively associated with rules A; _, B; and A; *_, B;*.

Thus, according to the above inclusion properties, it is possi­ ble to design a family of nested graphs simply by building collections of nested fuzzy subsets on X and Z. Indeed, denote by {A/', AE [0,1]} a family of fuzzy subsets on X such that A/''~ A/' iff.2A' and{B/", AE [0,1]} a family of fuzzy sub­ sets on Z such that B/' ~ B/'' if I-2A'. The family of rules A/' _,B/', AE[0,1], is such that r"' ~ r"-' iff.2A'. Actually, such a construction of nested graphs simply expresses that impli­ cative graphs increase in the sense of inclusion when under­ lying constraints become more permissive. More permissive rules are obtained either by restricting input conditions fur­ ther, or by enlarging output fuzzy sets.

Using a convex linear combination enables the automatic construction of such a collection of nested fuzzy subsets rang­ ing from the lower bound of the family to the upper one. Ap­ plying such a technique results in the following proposal :

where A; 0 and A/ , such thatA; 0 ~A/, are the lower and upper bounds of the family and EB denotes the extended sum of fuzzy numbers. In the same way, nested output fuzzy subsets can be built according to:

where B i 0 and B i 1 , such that B / ~ B ; 0 , are the upper and low­ er bounds of the family. It should be noted that the inclusion ordering of the B ;"' using A is the converse of the one of the A/, due to opposite behaviors with respect to graph inclusion.

Using the so-built fuzzy subset families (see figure 1 0) results in the following graph inclusions:

One interesting point is that the 4-sided shape introduced in section 2 is shared by all nested graphs provided that the low­ er and upper graphs are themselves 4-sided areas. In other words, equalities (3) and (4) hold for any r"- when they hold for r 0 and r 1 as expressed by property P4.

P4: If both (A; 0 , B; 0 ) and (A/, B; 1 ), i=1, .. ,n, satisfy equations (3) and (4), then (3) and (4) are still valid for any (A/', Bh, A

E [0, 1], i=1, .. .J!, when A/' and B/' are built according to (6) and (7).

An interpretation consists in viewing F as a fuzzy set of crisp graphs, that is as a level 2 fuzzy set, i.e. a fuzzy set of fuzzy sets. In this case, F is represented as:

according to Zadeh's notation where the integral sign stands for the union of the fuzzy singletons A I r"-. A single fuzzy gradual rule is pictured in figure 11.

X ..

figure 11 : A fuzzy gradual rule

Figure 12 plots the fuzzy graph obtained when the lower graph r 1 is precise and piecewise linear and the upper graph rD has the quadrangle-based shape of figure 2.

Using fuzzy gradual rules for dealing with the example of section 3 still results in perfect classification. Moreover, the robustness of the classification is improved as illustrated by figure 13, where histograms of the difference N3 - N5 are plotted for class 3 time series (see figure 9). It is clear that the number of examples for which the final decision is brittle, i.e. for the small values of N3 - N5 which are accounted for in the two first bars, decreases when fuzzy gradual rules are used. These results have been obtained by using the same form of indices N 1 given by equation (5) for crisp and fuzzy graphs except that rj (t;, z;) E [0 1] in the fuzzy case. Further im­ provements could probably be obtained by defining more so­ phisticated indices in the fuzzy case.

5 Conclusion

This paper has proposed a modelling framework which is faithful to the imprecision of available data. In the intervals between interpolation points where it is difficult to specify an analytical model, imprecision is captured by means of 4-sided areas. The application of the modelling methodology for clas­ sifying time series has exhibited interesting performance. Moreover, the discrimination power of the approach is im­ proved by using fuzzy gradual rules as introduced in the pre­ vious section. Indeed, they enable us to distinguish between typical members of a class which remain in subareas with high membership degrees from borderline members which go through subareas with smaller membership degrees. Besides, one may probably take further advanvage of the easy inter­ face with the user, provided by the use of gradual rule, for specifying queries in data mining applications (see [Keogh et a!., 2002] for an example of such possible use). Lastly, further research should deal with multidimensional spaces where the language of gradual rules may prove useful in the description of imprecise graphs.