=Paper=
{{Paper
|id=Vol-110/paper-8
|storemode=property
|title=The Fuzzy Classifier by Concept Localization in a Lattice of Concepts
|pdfUrl=https://ceur-ws.org/Vol-110/paper9.pdf
|volume=Vol-110
|dblpUrl=https://dblp.org/rec/conf/cla/ElloumiYY04
}}
==The Fuzzy Classifier by Concept Localization in a Lattice of Concepts==
https://ceur-ws.org/Vol-110/paper9.pdf
The
TheFuzzy
FuzzyClassifier
Classifierby
byConcept
ConceptLocalization
Localizationin
inaaLattice
Latticeofofconcepts
Concepts
S. Elloumi, Ch. Ben Youssef, and S. Ben Yahia
S. Elloumi, Ch. Ben Youssef, and S. Ben Yahia
Département des Sciences de l’Informatique
Départment des Sciences de l’Informatique,
Faculté des Sciences deFaculté
Tunis des Sciences de Tunis
Campus Universitaire, 1060 Tunis, Tunisie.
{samir.elloumi,
{samir.elloumi;sadok.benyahia}@fst.rnu.tn
sadok.benyahia}@fst.rnu.tn
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
1 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 fields, 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 classification. 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 definitions
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
c V. Snášel, R. Bělohlávek (Eds.): CLA 2004, pp. 80–89, ISBN 80-248-0597-9.
VŠB – Technical University of Ostrava, Dept. of Computer Science, 2004.
The Fuzzy Classifier by Concept Localization in a Lattice of Concepts 81
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 field.
2.1 Fuzzy subsets
The theory of the fuzzy subsets [19] permits to ensure a graduation in the mem-
bership 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 A e of the universe of discourse U = {u1 , ...., un }
is defined by a membership function µAe : U → [0, 1], where µAe(u) designates the
membership degree of u to Ae or the degree of truth of the proposition ” u belongs
to the fuzzy subset A”. The fuzzy subset A
e e is denoted by:
µ (u ) µ (u )
e = { Aeu1 1 , ...., Aeunn }
A (1)
0.5 0.1 0.9
Example 1. Given U = {a, b, c}. The subset A e = { a , b , c } is an example of
a fuzzy subset.The membership degrees of a, b and c to A e 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 A,e 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 lit-
erature 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], Belohlavèk [3, 4] and Burusco et al. [1, 2]
who have used some fuzzy operators in the new definitions 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.”
82 S. Elloumi, Ch. Ben Youssef, S. Ben Yahia
Example 2. Table 1 represents a fuzzy relation R e describing to what degree
every employee {o1 , .., o4} verifies a given qualification {k1 , .., k4}. The relation
R
e includes, also, an attribute class that represents the assigned class to every
employee.
Table 1. Fuzzy Relation R
e
k1 k2 k3 k4 Classe
o1 0.5 1.0 0.7 0.5 C1
o2 0.6 0.7 1.0 0.5 C2
o3 1.0 0.9 1.0 0.1 C2
o4 1.0 0.9 0.9 0.1 C2
Definition 3. Given a triplet < G, M, R e > named fuzzy context and given A,
B two subsets where A is an ordinary subset of G, B
e e is a fuzzy subset defined
on M and δ ∈ [0, 1]. The two operators fe and h
fδ are as follows [16]:
α
fe(A) = {m| α = min{µRe (g, m), g ∈ A}, m ∈ M } (2)
e e = {g ∈ G | ∀m, m ∈ M ⇒ (µ e (m) →I µ e (g, m)) ≥ δ}
hδ (B) (3)
B L R
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 B e of properties,
hδ (B) computes the set of all objects which satisfy all properties in B
e e at a given
level δ which is called a verification threshold. Operators fe and e
h are representing
a fuzzy Galois connection between the subsets A and B[8]. e
Definition 4. A fuzzy formel concept (at the level δ ∈ [0, 1]) of the fuzzy context
< G, M, R
e > is a pair (A, B)
e where :
fe(A) = B
e and e
h(B)
e = A. (4)
Example 3. For δ = 1 and δ = 0.9, we obtain from the fuzzy relation R
e (table
1) the following fuzzy concepts depicted resp. in tables 2 and 3:
Definition 5. Let C1 = (A1 , B e1 ) and C2 = (A2 , B
e2 ) be two fuzzy formel con-
cepts, at the level δ, of the fuzzy context < G, M, R >. A partial order relation
e
≤ is defined between C1 and C2 as the following:
C1 ≤ C2 ⇔ A1 ⊆ A2 , (B
e2 →I B
L
e1 ) ≥ δ (5)
Remark 1. With the partial order relation ≤ a set of fuzzy concepts can be
organized within a Lattice[16].
The Fuzzy Classifier by Concept Localization in a Lattice of Concepts 83
Table 2. Fuzzy concepts for δ = 1
Label Fuzzy Concept (intent × extent)
1.0 1.0 1.0 0.5
FC0 ∅ × { k1 , k2 , k3 , k4 }
0.5 1.0 0.7 0.5
FC1 {o1 } × { k1 , k2 , k3 , k4 }
0.6 0.7 1.0 0.5
FC2 {o2 } × { k1 , k2 , k3 , k4 }
1.0 0.9 1.0 0.1
FC3 {o3 } × { k1 , k2 , k3 , k4 }
0.5 0.7 0.7 0.5
FC4 {o1 , o2 } × { k1 , k2 , k3 , k4 }
0.6 0.7 1.0 0.1
FC5 {o2 , o3 } × { k1 , k2 , k3 , k4 }
1.0 0.9 0.9 0.1
FC6 {o3 , o4 } × { k1 , k2 , k3 , k4 }
0.5 0.9 0.7 0.1
FC7 {o1 , o3 , o4 } × { k1 , k2 , k3 , k4 }
0.6 0.7 0.9 0.1
FC8 {o2 , o3 , o4 } × { k1 , k2 , k3 , k4 }
0.5 0.7 0.7 0.1
FC9 {o1 , o2 , o3 , o4 } × { k1 , k2 , k3 , k4 }
Table 3. Fuzzy concepts for δ = 0.9
Label Fuzzy Concept (intent × extent)
1.0 1.0 1.0 0.5
FC0 ∅ × { k1 , k2 , k3 , k4 }
0.5 1.0 0.7 0.5
FC1 {o1 } × { k1 , k2 , k3 , k4 }
0.6 0.7 1.0 0.5
FC2 {o2 } × { k1 , k2 , k3 , k4 }
0.5 0.7 0.7 0.5
FC4 {o1 , o2 } × { k1 , k2 , k3 , k4 }
1.0 0.9 0.9 0.1
FC6 {o3 , o4 } × { k1 , k2 , k3 , k4 }
0.5 0.9 0.7 0.1
FC7 {o1 , o3 , o4 } × { k1 , k2 , k3 , k4 }
0.6 0.7 0.9 0.1
FC8 {o2 , o3 , o4 } × { k1 , k2 , k3 , k4 }
0.5 0.7 0.7 0.1
FC9 {o1 , o2 , o3 , o4 } × { k1 , k2 , k3 , k4 }
3 Fuzzy classifier by Concepts Localization
We recall that the Fuzzy Classifier by Concept Localization (FC2L) [7] is a fuzzy
classification method that presents the advantage to use the properties of the
lattice of concepts without having to generate it before starting the classifica-
tion. 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.
84 S. Elloumi, Ch. Ben Youssef, S. Ben Yahia
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
verification threshold e
hδ 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 thresh-
old. The first consists in using a global verification 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 verification threshold, every concept
will be classified therefore with its own threshold. This method gave the best
results for the majority of the bases used. Then, and after finding 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 verifica-
tion threshold δ = 1 and using training sample presented in table 1
fδ (ox ) gives the objets {o1 , o2 }.Then, the use of fe gives finally
The application of h
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 finally 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 Concepts base as a lattice in CF2L
4.1 Principle
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
The Fuzzy Classifier by Concept Localization in a Lattice of Concepts 85
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 figure 1
illustrates the concepts base organization.
1
Next level
2
Next Concept
Next level
Sons Fathers
n
Levels
Head
Fig. 1. Concepts base structure
Insertion The insertion of a concept starts with the research of the correspond-
ing 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
86 S. Elloumi, Ch. Ben Youssef, S. Ben Yahia
of concept in the right order. Otherwise, if it exists, the algorithm verifies 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 first
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 specific 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 verifies 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 con-
cepts. Indeed, research is only done on the concepts of the level head. Every
concept is tested, if it verifies 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 figure 2 gives
the execution times comparison as well as the bad classification rate (BCR) of
the three search methods.
The Fuzzy Classifier by Concept Localization in a Lattice of Concepts 87
– 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 classification 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 classification 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 classifier 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
classifications while keeping more or less the same bad classification 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 classification rate and the execution times go down while the number of
concepts in BC rises.
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.
88 S. Elloumi, Ch. Ben Youssef, S. Ben Yahia
3 4 56 78 9 :; < = > ? @ AB CED FHGI JLK M NPORQ S T U V
BCR : Threshold =1 and Step = 0.05 Execution time : Threshold =1 and Step = 0.05
b c%dfeLg
" #%$'&( h+i
)+* a
! , - . .0/21 _^ ` j k ll
m+n
0
0.1 0.2 0.3 0.4 0.5 1 0 W
0.1 W 0.2 X 0.3 Y 0.4 Y 0.5 1 Z[]\
3FU
¹³ г0.05
¿
| ' ' ¡ ¢ £¥¤§¦¨© ª «
BCRÕ:ÖThreshold
å ³Í³Í ³ç
³ç û ø û =1
ÿ÷ ³Ð³
³Ð³
and ¹³ææ ø ³=г
Step Execution time : Threshold =1 and Step = 0.05
10
w xzy|{} µR¶· ¸¹
~R ºR»
uvt ´
5
²± ³ ¼R½|¾ ¾
ºR»
0
0 o0.1 o
0.2 o 0.3 0.4
o o
0.5 1 prq s 0 ¬
0.1 ¬
0.2 ¬ 0.3 ¬0.4 0.5
¬ 1 r® °¯
Total scan
BCR
BCR : Threshold
: Threshold = 1 Step
=1 and & Pas== 0,05
0.05 Execution
Execution timeTime : Seuil
: Threshold =1=and
1 &Step
Pas = 0,05
= 0.05
Empty Empty
10
BC BC
BCR
5 130
Time
120
0 Full BC 110 Full
0,2
0,4
0
1
0 0,1 0,2 0,3 0,4 0,5 1
Gap BC
Gap
Partial scan
Fig. 2. Bad Classification rate and execution time
The Fuzzy Classifier by Concept Localization in a Lattice of Concepts 89
3. R. Belohlavèk. Fuzzy concepts and conceptual structures: induced similarities. In
Proc. JCIS’98, North Carolina, USA, volume 1, pages 179–182, 1998.
4. R. Belohlavèk. Fuzzy Galois connections. Math. Logic Journal, 45(4):497–504,
1999.
5. B. V. Dasarathy. Nearest Neighbors(NN) Norms : NN pattern classification tech-
niques. 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 In-
formation and Communication Technology, Amman, Jordan -to appear-, 2001.
9. S. Elloumi, C. Ben Youssef, S. Ben Yahia, and H. Ounelli. Génération incrémentale
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 Numérique partir de Données, pages 309–326. Cépadues-édition,
1991.
11. R. Godin. Complexité de structures de treillis. Annuaire Sciences Mathématiques
Québec, 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 numérique à partir de données.
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, Cépadues, 1993.
15. S. Pollandt. Fuzzy-Begriffe, Formale Begriffsanalyse unscharfer Daten. Springer-
Verlag 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. Wolff. 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 Clus-
tering Analysis. Academic Press, New York, 1977.
21. A. Zighed, J.P. Auray, and G. Duru. Sipina méthode et logiciel. Alexandre
lacassagne-lyon, 1992.