TTheheFuFzuzzyzyCClalsassisfieirfierbybyCConocnecpetptLLocoaclaizliaztaitoinonin in aLLaatttitcieceooffcoCnocnecpetpsts a

Abstract

We discuss in this paper several approaches exploiting a base of concepts organized under a lattice in the Fuzzy Classifier by Concept Localization (FC2L) system. We present the 3FU, the total scan and the partial scan as three approaches for locating the adequate concept to a novel object to classify. We present also the experimental results in terms of misclassification rate and response time.

Keywords

• Fuzzy classifier
• concept localization
• Lattice of concepts
• FC2L

Introduction

The main aim of a classifier system [ 17 ] is to assign a class to a novel object using the information concerning the existing ones in a database. Each object of the database is supposed to be described by several exogenous (or descriptive) attributes and an endogenous (or label) one [ 21, 20 ]. The endogenous attribute describes the class of the object.

In the literature, several classifier systems have already been proposed and have been based on statistical [ 5, 17 ], symbolic [ 14, 13 ] or conceptual [ 10 ] approaches. The last ones are being ever attractive efilds, with regard to their mathematical foundation, such as, Galois connection, formal concept and Galois lattice. However, a major difficulty, related to the complexity of these approaches, is encountered [ 11 ]. In fact, the increasing number of the generated concepts in the Galois lattice, limit their practical applications to a reduced sample of data.

The fuzzy classifier by concepts localization (FC2L) [ 7 ] can be considered as a conceptual approach for supervised automatic classicfiation. It’s main feature consists in an incremental generation of a concepts base during the classification task. We have discussed in a previous work [ 9 ] the organization of the concepts base as a simple list and we propose in this paper a lattice structure for it.

This paper is organized as follows: In Section 2, the fundamental operations and properties of fuzzy sets are recalled as well as the mathematical denfiitions and properties of fuzzy Galois lattice structure. In Section 3 we present the FC2L approach and we propose in section 4 its extension by organizing the base of concepts (BC) as a fuzzy lattice. Also, we develop three methods to explore BC which are 3FU, Total Scan and Partial Scan. In section 5 we present the experimental evaluation made on known databases and finally the section 6 concludes the paper. 2

Mathematical foundation

This section presents the fundamental elements on which our approach is based on. It is about mainly a recall on the fuzzy subsets as well as a presentation of the fuzzy formal concepts analysis efild. 2.1

Fuzzy subsets

The theory of the fuzzy subsets [ 19 ] permits to ensure a graduation in the membership of an element to a category. In fact, we admit that an element can belong to a category with a more or less strong manner; e.g., a temperature superior to 35 degrees belongs completely to the category ”high temperature”. However, the temperature 25 degrees can be considered either as ”moderate” and ”high” temperature.

Definition 1. A fuzzy subset Ae of the universe of discourse U = {u1, ...., un} is defined by a membership function μ A : U → [ 0, 1 ], where μ A(u) designates the e e membership degree of u to Ae or the degree of truth of the proposition ” u belongs to the fuzzy subset Ae”. The fuzzy subset Ae is denoted by:

Ae = {μ Aeu(1u1), ...., μ Aeu(nun)} (1) 0.5 0.1 0.9 Example 1. Given U = {a, b, c}. The subset Ae = { a , b , c } is an example of a fuzzy subset.The membership degrees of a, b and c to Ae are, respectively, 0.5, 0.1 and 0.9. More especially, with the membership degree 0.9, the element c possesses a strong adherence to Ae, while the element b, with the degree 0.1, belongs there weakly. 2.2

Fuzzy formal concept

Different fuzzy extensions of the formal concept have been proposed in the literature according to different points of views. More particularly, we distinguish the proposition of Wolff [ 18 ] that consists to bring back the problem to a non fuzzy context contrary to Pollandt [ 15 ], Belohlavek` [ 3, 4 ] and Burusco et al. [ 1, 2 ] who have used some fuzzy operators in the new denfiitions that they proposed. We recall in what follows the definitions that we already developed in [ 8, 16 ]. Definition 2. Given G a set of objects and M a set of attributes (properties). A fuzzy relation Re between the subsets G and M is a fuzzy subset defined on G × M . The value μ Re(g, m) ∈ [ 0, 1 ] is interpreted as the degree of truth of the proposition” the object g ∈ G possesses the attribute m ∈ M.” Example 2. Table 1 represents a fuzzy relation Re describing to what degree every employee {o1, .., o4} veriefis a given qualicfiation {k1, .., k4}. The relation Re includes, also, an attribute class that represents the assigned class to every employee. Definition 3. Given a triplet < G, M, Re > named fuzzy context and given A, Be two subsets where A is an ordinary subset of G, Be is a fuzzy subset defined on M and δ ∈ [ 0, 1 ]. The two operators fe and hfδ are as follows [ 16 ]: α fe(A) = {m| α = min{μ Re(g, m), g ∈ A}, m ∈ M } (2) ehδ (Be) = {g ∈ G | ∀m, m ∈ M ⇒ (μ B(m) →IL μ R(g, m)) ≥ δ } (3) e e where →IL stands for the Lukasiewicz implication i.e. for a, b ∈ [ 0, 1 ], a →IL b = min(1, 1 − a + b).

For the objects subset A, fe(A) is the fuzzy set of their common properties since we use the min operation. Dually, for the fuzzy subset Be of properties, hδ (Be) computes the set of all objects which satisfy all properties in Be at a given level δ which is called a vericfiation threshold. Operators fe and eh are representing a fuzzy Galois connection between the subsets A and Be[ 8 ].

Definition 4. A fuzzy formel concept (at the level δ ∈ [ 0, 1 ]) of the fuzzy context < G, M, Re > is a pair (A, Be) where :

fe(A) = Be and eh(Be) = A.

Example 3. For δ = 1 and δ = 0.9, we obtain from the fuzzy relation Re (table 1) the following fuzzy concepts depicted resp. in tables 2 and 3: Definition 5. Let C1 = (A1, Be1) and C2 = (A2, Be2) be two fuzzy formel concepts, at the level δ , of the fuzzy context < G, M, Re >. A partial order relation ≤ is defined between C1 and C2 as the following:

C1 ≤

C2 ⇔ A1 ⊆

A2, (Be2 →IL Be1) ≥ δ (4) (5) Remark 1. With the partial order relation ≤ organized within a Lattice[ 16 ].

a set of fuzzy concepts can be FC0 FC1 FC2 FC3 FC4 FC5 FC6 FC7 FC8 FC9 FC0 FC1 FC2 FC4 FC6 FC7 FC8 FC9

Fuzzy classifier by Concepts Localization

We recall that the Fuzzy Classifier by Concept Localization (FC2L) [ 7 ] is a fuzzy classicfiation method that presents the advantage to use the properties of the lattice of concepts without having to generate it before starting the classicfiation. It permits therefore to calculate the approximate fuzzy concept every time from the training sample (EA) which contains a set of samples labeled by their classes. With this method, the training and the classification are not anymore two separate stages. The FC2L method is composed of two steps : (i) Research of the approximate concept and (ii) Class assignment. 3.1

Research of the approximate concept (CAPS)

The localization of the approximate concept consist to search for the objects verifying the properties of the object to classify. First of all, the method uses the operator hδ on the training sample to mark the objects verifying the object to classify. The used fuzzy implication is the Lukasiewicz implication. In order to find the best concept verifying the object to classify and who is not empty, the vericfiation threshold ehδ can be reduced until obtaining of a non empty concept. It is the reason for which this concept is called approximate concept (CAPS). This method propose two alternatives of training of the best verification threshold. The first consists in using a global vericfiation threshold for all objects to classify. The second consist in using an outgoing verification threshold common to all objects and a step to decrement this vericfiation threshold, every concept will be classiefid therefore with its own threshold. This method gave the best results for the majority of the bases used. Then, and after nfiding the objects of the concept, the operator fe is used to determine the minimum degrees of the concepts.

0.4 0.6 0.7 0.5 Example 4 Given the object ox = ( k 1, k 2, k 3, k 4) to classify and a verification threshold δ = 1 and using training sample presented in table 1 The application of hfδ (ox) gives the objets {o1, o2}.Then, the use of fe gives finally the following approximate concept : objects properties

0.5 0.7 0.7 0.5 {o1, o2} k 1, k 2, k 3, k 4 3.2

Class assignment

After having calculated the CAPS, the system must nfially find the class to affect to the new object. The CF2L method proposes three approaches to affect a class to an object: the intersection of the objects, the most decisive attribute and the addition of the degrees. The evaluation tests showed that the best results are those of the intersection of the objects. All these alternatives were detailed in [ 6 ] 3.3

Discussion

The originality of the method FC2L resides in its speed in relation to the other methods of conceptual training. But, this method can be optimized by the reuse of concepts already calculated at the time of the previous classifications. The idea would consist therefore in stocking the concepts calculated in a Basis of Concepts (BC) after every classification in order to reuse them. 4 4.1

Principle

Concepts base as a lattice in CF2L

During the classification of a new object, the research of the CAPS doesn’t take place directly in the training sample. Indeed, an adequate concept is sought-after in the BC, if it exists we affect its class to the object. This research is guided by a new variable named Gap. This variable permits to choose among the concepts that verify the object those that are nearer to the object to classify. If we don’t find adequate concepts in BC, we return to EA. This improvement can prove to be very useful especially if the number of objects in EA and the cardinality of the properties are raised. 4.2

Incremental generation of concepts base

Organization Organized under the shape of a lattice, the Base of Concepts (BC) is not anymore a simple list since the concepts are sorted according to a relation of order ≤ . This permits, on one hand to prevent the redundancy and on the other to accelerate the research at the time of classification. This new structure is composed of several levels. Every level contains the concepts having the same cardinalities of their extensions. This cardinality is called the rank of the level. The head of this basis is the level having the biggest rank. All levels are indeed sorted in the descending order according to their ranks. The order ≤ between the concepts is represented by a father/son relation. The gfiure 1 illustrates the concepts base organization.

Head

Sons

Fathers

Next Concept 1 2 n

Next level Next level

Levels Insertion The insertion of a concept starts with the research of the corresponding level its extension (a level with a rank equal to the number of objects of the concept). If it doesn’t exist, an appropriate one is created and added to the basis of concept in the right order. Otherwise, if it exists, the algorithm veriefis if the concept is already inserted in the basis of concept. If it is a new concept, the algorithm adds the new element, puts up-to-date its father/son relations with the concepts of the others levels. 4.3

Research in BC

We developed three methods to explore BC. The first consists in using the rfist concept that suits the new object, the second more expensive consists to browse all concepts of the lattice then to choose the best concept. Finally, the last that especially gave the best results in term of execution time consists in browsing the lattice partially.

First Fit First Used (3FU) The research of the adequate concept begins from the level head. This idea comes because the concepts situated in the level head are the most specicfi and can give some best results therefore. Research ends as soon as a concept is accepted. Otherwise, the research continues in the other levels concept by concept.

Total Scan The research of the adequate concept begins from the level head. This idea comes because the concepts situated in the level head are the most specific and can give some best results therefore. Research ends when all the concepts had been visited. For every concept that veriefis the new object, we check if it has already a son accepted. In the positive case, we reject it because this means that we have already a concept that is nearer to the new concept. This method wastes the times of execution and has in fact the worst execution time.

Partial Scan It is a recursive method that partially explores the Basis of concepts. Indeed, research is only done on the concepts of the level head. Every concept is tested, if it veriefis the object to classify then it is useless to pass to its fathers since they also verify the properties of the new object and are less good since the smallest one means, the nearest one is the current concept. If a concept doesn’t verify the object to classify, then we redo the same thing with its fathers. In the end of the browse, we choose the best concept according to its gap. 5

Experimental evaluation

The experiment was made on the speech database cited in [ 12 ]. The gfiure 2 gives the execution times comparison as well as the bad classification rate (BCR) of the three search methods. – 3FU : Until a gap equal to 0.2, we consider that the execution time with an empty BC is shorter than with a full one. This is due to the useless search in BC since the classifier will accept only the concepts with a null gap. We have to notice here that these execution times are bigger than classification without BC. But with a gap greater than 0.2, we consider that a full BC gives better results. This can be explained by the fact that we don’t have to calculate the class of the concepts found in BC. – Total Scan : The tests approved that it’s a time-consuming method. We consider that until a gap equal to 0.2, the partial scan is not the best one since it’s very very near to the ordinary FC2L execution time. Although 3FU and total scan gives better execution times with a gap greater than 0.2, it doesn’t mean that they are the best. This difference is due to the number of concept to explore. – Partial Scan : We can say that this method is the best one since it has the best execution time and it has rates of bad classicfiation which are equal or less than the ordinary FC2L method. As the other methods, we consider that until a gap equal to 0.2, the use of an empty gives better results due to the insertion of new concepts. With this method, the execution time for all the gaps and with an empty or full BC, the execution time is lower or equal to the time of execution of classicfiation without the use of BC.

We consider that until a gap equal to 0.2, the partial scan is from afar the best one since it’s very very near to the ordinary FC2L execution time. Although 3FU and total scan gives better execution times with a gap greater than 0.2, it doesn’t mean that they are the best. This difference is due to the number of concept to explore 6

Conclusion

In this paper, we presented the FC2L classiefir then an improvement which consists in generating incrementally a fuzzy lattice to store the calculated fuzzy concepts while classifying objects. The evaluation tests showed that the use of a fuzzy lattice in the FC2L permitted to improve the execution times of the classicfiations while keeping more or less the same bad classicfiation rates. The lattice is in fact a structure allowing a better choice of the concept to reuse. It also permits a partial speedy browse of BC using the fathers’ links. In brief, the bad classicfiation rate and the execution times go down while the number of concepts in BC rises. BCR : Threshold =1 and Step = 0.05 Õ Ö å ³Í ³çû ø û ÿ÷ ³Ð³ ¹³ae ø ³Ð³ ¿ BCR : Threshold =1 and Step = 0.05 Execution time : Threshold =1 and Step = 0.05 o0.1 0o.2 10 0 0

Empty BC

Full BC

Empty BC

Full BC

Gap 130 e 120 i 110 m T 0 0,1 0,2 0,3 0,4 0,5 1 0

1 2 , 4 , 0 0

Gap

BCR: Threshold = 1 & Pas = 0,05 BCR : Threshold =1 and Step = 0.05 EExxeecuctuiotniotinmTei:mThere:shSoeldu=il1=an1d&StPepas= 0=.005,05

Fig. 2. Bad Classification rate and execution time

References

1. R. Fuentes-Gonzalez A. Burusco . The study of the L-Fuzzy Concept Lattice . Mathware and Soft Computing , 1 ( 3 ): 209 - 218 , 1994 .

2. R. Fuentes-Gonzalez A. Burusco . Construction of the L-Fuzzy Concept Lattice . Fuzzy Sets and Systems , 97 ( 1 ): 109 - 114 , 1998 .

3. R. Belohlavek `. Fuzzy concepts and conceptual structures: induced similarities . In Proc. JCIS'98 , North Carolina , USA, volume 1 , pages 179 - 182 , 1998 .

4. R. Belohlavek`. Fuzzy Galois connections. Math. Logic Journal , 45 ( 4 ): 497 - 504 , 1999 .

5. B. V. Dasarathy . Nearest Neighbors(NN) Norms : NN pattern classification techniques . IEEE Computer Society Press, Los Almitos, CA, 1991 .

6. S. Elloumi and A. Jaoua . Fuzzy classifier based on similarity measures . In Proc. of the International conference CIMCA'99 , Vienna, Austria, volume 2 , pages 271 - 273 , 1999 .

7. S. Elloumi and A. Jaoua . Automatic classification using fuzzy concepts . In Proc. JCIS' 2000 , Atlantic City , USA, volume 1 , pages 276 - 279 , 2000 .

8. S. Elloumi and A. Jaoua . A multi-level conceptual learning approach using fuzzy galois connection . In Proc. of the International Symposium on Innovation in Information and Communication Technology , Amman, Jordan -to appear-, 2001 .

9. S. Elloumi , C. Ben Youssef , S. Ben Yahia , and H. Ounelli . Gen´er´ation incerm´entale de concepts formels et leurs utilisation dans le classifieur flou par localisation de concepts . In Proc. of the 7th African Conference on Research in Computer Science , Tunis, Tunisia, November 2004 .

10. J.G. Ganasia . Charade : Apprentissage de bases de connaissances, in: Induction Symbolique et Numer´ique partir de Donnee´s , pages 309 - 326 . Cep´aduese-d´ition, 1991 .

11. R. Godin . Complexiet´ de structures de treillis. Annuaire Sciences Matehm´atiques Queb´ec , pages 19 - 38 , 1989 .

12. N. Kasabov , R. Kozma , R. Kilgour , M. Laws , J. Taylor , M. Watts, and A. Gray . Speech data analysis and recognition using fuzzy neural networks and self-organised maps . In N. Kasabov and R. Kozma, editors, Neuro-Fuzzy Tools and Techniques for Information Processing . Eds., Physica Verlag, Heidelberg, 1998 .

13. Y. Kodratoff and E. Diday . Induction symbolique et numer´iquea` partir de donnee´s . Cepadues-Editions, 1991 .

14. R.S. Michalski, J.G. Carbonel, T.M. Mitchell , and Y. Kodratoff . Apprentissage symbolique, une approche de l' Intelligence Artificielle . Tome 1 , 2 , Cep´adues, 1993 .

15. S. Pollandt. Fuzzy-Begriffe, Formale Begriffsanalyse unscharfer Daten . SpringerVerlag Berlin Heidelberg New York, 1997 .

16. Ahmed Hasnah Ali Jaoua Ibtissem nafkah Samir Elloumi, Jihad Jaam . Conceptual Reduction of Fuzzy context using Lukasiewicz Implication . Information Science , 163 ( 4 ): 252 - 263 , June 2004 .

17. M.S. Weiss and A.C. Kulikowski . Computer Systems that learn . Morgan Kaufman Publishers, 1991 .

18. K.E. Wol.ff Conceptual interpretation of fuzzy theory . In Proc. 6th European Congress on Intelligent techniques and Soft computing , volume I, pages 555 - 562 , 1998 .

19. L. A. Zadeh . Fuzzy sets . Information and Control Journal , 8 : 338 - 353 , 1965 .

20. L. A. Zadeh . Fuzzy Sets and their Application to Pattern Classification And Clustering Analysis . Academic Press, New York, 1977 .

21. A. Zighed , J.P. Auray , and G. Duru . Sipina met´hode et logiciel . Alexandre lacassagne-lyon , 1992 .