Laboratory L3i, University of La Rochelle, France ISBN 978{2{7466{6566{8
Edited by CLA 2013 c paper author(s), 2013, for the included papers c Manuel Ojeda-Aciego, Jan Outrata, Editors, for the volume Copying permitted only for private and academic purposes.
This work is subject to copyright. All rights reserved. Reproduction or publication of this material, even partial, is allowed only with the editors' permission. Page count: Impression: Edition: First published: 2013 xii+306 50 1st Published and printed by: Laboratory L3i, University of La Rochelle, France
CLA 2013 was organized by the Laboratory L3i, University of La Rochelle.
Radim Belohlavek Sadok Ben Yahia Jean Diatta Peter Eklund Sergei O. Kuznetsov Engelbert Mephu Nguifo Amedeo Napoli
Manuel Ojeda-Aciego Jan Outrata
Cristina Alcalde Jaume Baixeries Radim Belohlavek Sadok Ben Yahia Anne Berry Karell Bertet Ana Burusco Claudio Carpineto Pablo Cordero Jean Diatta Felix Distel Vincent Duquenne Sebastien Ferre Bernhard Ganter Alain Gely Robert Godin Marianne Huchard Dmitry I. Ignatov Vassilis G. Kaburlasos Jan Konecny Stanislav Krajci Palacky University, Olomouc, Czech Republic Faculte des Sciences de Tunis, Tunisia Universite de la Reunion, France University of Wollongong, Australia State University HSE, Moscow, Russia LIMOS, University Blaise Pascal, Clermont-Ferrand, France INRIA NGE/LORIA, Nancy, France Universidad de Malaga, Spain Palacky University, Olomouc, Czech Republic Univ del Pais Vasco, San Sebastian, Spain Polytechnical University of Catalonia, Spain Palacky University, Olomouc, Czech Republic Faculte des Sciences de Tunis, Tunisia LIMOS, Universite de Clermont Ferrand, France L3i, Universite de La Rochelle, France Universidad de Navarra, Pamplona, Spain Fondazione Ugo Bordoni, Roma, Italy Universidad de Malaga, Spain Universite de la Reunion, France TU Dresden, Germany Universite Pierre et Marie Curie, Paris, France Irisa/Universite de Rennes 1, France TU-Dresden, Germany University of Metz, France Univeristy of Montreal, Canada LIRMM, Montpellier, France State University HSE, Moscow, Russia TEI, Kavala, Greece Palacky University, Olomouc, Czech Republic University of P.J. Safarik, Kosice, Slovakia Sergei O. Kuznetsov Leonard Kwuida Jesus Medina Engelbert Mephu Nguifo Rokia Missaoui Amedeo Napoli Lhouari Nourine Sergei Obiedkov Uta Priss Olivier Raynaud Sebastian Rudolph Baris Sertkaya Laszlo Szathmary Petko Valtchev Francisco Valverde State University HSE, Moscow, Russia Bern University of Applied Science, Switzerland Universidad de Cadiz, Spain LIMOS, University Blaise Pascal, Clermont Ferrand, France UQO, Gatineau, Canada INRIA NGE/LORIA, Nancy, France LIMOS, Universite de Clermont Ferrand, France State University HSE, Moscow, Russia Ostfalia University of Applied Sciences, Wolfenbuttel, Germany LIMOS, University of Clermont Ferrand, France Institute AIFB, University of Karlsruhe, Germany SAP Research Center, Dresden, Germany University of Debrecen, Hungary Universite du Quebec a Montreal, Canada Universidad Nacional de Educacin a Distancia, UNED Spain
Michel Liquiere LIRMM, Montpellier, France Mar a Eugenia Cornejo Pin~ero Universidad de Cadiz, Spain Eloisa Ram rez Poussa Universidad de Cadiz, Spain Alexis Irlande Universidad Nacional de Colombia, Colombia Juan Carlos D az Moreno Universidad de Cadiz, Spain Nader Mohamed Jelassi LIMOS, Clermont Universite, France & URPAH,
Faculty of Tunis, Tunisia
Karell Bertet (chair)
L3i, Universite de La Rochelle, France Dwiajeng Andayani Universite de La Rochelle, France Romain Bertrand L3i, Universite de La Rochelle, France Mickael Coustaty L3i, Universite de La Rochelle, France Ngoc Bich Dao L3i, Universite de La Rochelle, France Christophe Demko L3i, Universite de La Rochelle, France Cyril Faucher L3i, Universite de La Rochelle, France Nathalie Girard LI, Universite de Tours, France Clement Gurin L3i, Universite de La Rochelle, France Muhammad Muzzamil Luqman L3i, Universite de La Rochelle, France Jean-Marc Ogier L3i, Universite de La Rochelle, France Christophe Rigaud L3i, Universite de La Rochelle, France Kathy Theuil L3i, Universite de La Rochelle, France Muriel Visani L3i, Universite de La Rochelle, France CryptoLat - a Pedagogical Software on Lattice Cryptomorphisms and Lattice Properties : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Florent Domenach A lattice-free concept lattice update algorithm based on *CbO : : : : : : : : : : 261
Jan Outrata
Applying User-Guided, Dynamic FCA to Navigational Searches for Earth Science Data and Documentation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 275
Bruce R. Barkstrom A Collaborative Approach for FCA-Based Knowledge Extraction : : : : : : : : 281
My Thao Tang and Yannick Toussaint Towards Description Logic on Concept Lattices : : : : : : : : : : : : : : : : : : : : : : : 287
Julia V. Grebeneva, Nikolay V. Shilov and Natalia O. Garanina Computing Left-Minimal Direct Basis of implications : : : : : : : : : : : : : : : : : : 293 Pablo Cordero, Manuel Enciso, Angel Mora and Manuel
Ojeda-Aciego Comparing Performance of Formal Concept Analysis and Closed Frequent Itemset Mining Algorithms on Real Data : : : : : : : : : : : : : : : : : : : : 299
Lenka Piskova and Tomas Horvath Author Index : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 305 Formal concept analysis has, for many years, laid claim to providing a formal basis for an applied lattice theory. With the many di erent formalisms and implementations, and their applications available today, this claim is stronger than ever, as witnessed by increasing amount and range of publications in the area.
The International Conference \Concept Lattices and Their Applications (CLA)" is being organized since 2002 with the aim of bringing together researchers working on various approaches for studying and practically applying concept lattices. The main aim of CLA is to bring together researchers (students, professors, engineers) involved in all aspects of the study of concept lattices, from theory to implementations and practical applications. As the diversity of the selected papers shows, there is a wide range of theoretical and practical research directions, ranging from algebra and logic to pattern recognition and knowledge discovery. The Tenth edition of CLA was held in La Rochelle, France from October 15th to October 18th, 2013. The event was organized and hosted by the Laboratory L3i, University of La Rochelle.
This volume includes the selected papers and the abstracts of 4 invited talks. This year there were initially 37 submissions from which 22 included papers were accepted as full papers and 5 as short papers. Thus, the program of the conference consisted of four keynote talks given by the following distinguished researchers: Ralph Freese, Bart Goethals, Michel Grabisch and Vincent Duquenne, together with twenty-seven communications, including the full and short papers, authored by researchers from thirteen countries (Belgium, Chile, Cyprus, Czech Republic, Djibouti, Estonia, France, Germany, Mexico, Russia, Slovakia, Spain and USA).
The papers were reviewed by members of the Program Committee with the help of the additional reviewers listed overleaf. We would like to thank them all for their valuable assistance. It is planned that a selection of extended versions of the best papers will be published in a renowned journal, after being subjected again to a peer review.
The success of such an event is mainly due to the hard work and dedication of a number of people, and the collaboration of several institutions. We want to thank the contributing authors, who submitted high quality works, to acknowledge the help of members of the CLA Steering Committee, who gave us the opportunity of chairing this edition, and to thank the Program Committee, the additional reviewers, and the local Organization Committee. All of them deserve many thanks for having helped to attain the goal of providing a balanced event with a high level of scienti c exchange and a pleasant environment.
We would also like to thank the following institutions, which have helped the organization of the 10th CLA International Conference: Region of Poitou-Charentes, Department of Charente Maritime, City of La Rochelle and University of La Rochelle.
Last but not least, most of our bureaucratic tasks related to paper submission, selection, and reviewing have been minimized thanks to the EasyChair conference system, and we should therefore not forget to mention its help after the list of \o cial sponsors".
October 2013 Manuel Ojeda-Aciego
Jan Outrata
Program Chairs of CLA 2013
Ralph Freese Department of Mathematics, University of Hawaii
Honolulu, HI 96822, USA ralph@math.hawaii.edu A lattice L is projective in a variety V of lattices if whenever (1) (2) f : K
L g : L → K is an epimorphism, there is a homomorphism such that f (g(a)) = a for all a ∈ L.
Projective lattices are characterized in [
If g in (2) is only required to be order-preserving, it is called an isotone section of the epimorphism (1). We will characterize which lattices L have an isotope section for every epimorphism (1). We will use this to characterize when the ordinal (linear) sum of two projective lattices in V will be projective and give some surprising examples.
The second of the four conditions characterizing projectivity we will discuss
is join refinement and the dependency relation; the so-called D-relation. This
condition and some closely related concepts are used in many parts of lattice
theory. Besides free lattice, projective lattices and finitely presented lattices, it
has applications to transferable lattices, congruence lattices of lattices,
representing finite lattices as congruence lattices of finite algebras, and ordered direct
bases in database theory [
Bart Goethals University of Antwerp, Belgium
bart.goethals@ua.ac.be Abstract. We propose a transformation method to circumvent the problems with high dimensional data. For each object in the data, we create an itemset of the k-nearest neighbors of that object, not just for one of the dimensions, but for many views of the data. On the resulting collection of sets, we can mine frequent itemsets; that is, sets of points that are frequently seen together in some of the views on the data. Experimentation shows that nding clusters, outliers, cluster centers, or even subspace clustering becomes easy on the carti ed dataset using state-of-the-art techniques in mining interesting itemsets.
Cooperative Games on Lattices
In cooperative game theory, for a given set of players N, TU-games are functions v : 2N → R which express for each nonempty coalition S ⊆ N of players the best they can achieve by cooperation.
In the classical setting, every coalition may form without any restriction, i.e., the domain of v is indeed 2N . In practice, this assumption is often unrealistic, since some coalitions may not be feasible for various reasons, e.g., players are political parties with divergent opinions, or have restricted communication abilities, or a hierarchy exists among players, and the formation of coalitions must respect the hierarchy, etc.
Many studies have been done on games defined on specific subdomains of 2N , e.g.,
antimatroids [
The main problem in cooperative game theory is to define a rational solution of the game, that is, supposing that the grand coalition N will form, how to share among its members the total worth v(N). The core is the most popular solution concept, since it ensures stability of the game, in the sense that no coalition has an incentive to deviate from the grand coalition. For a game v on a family F of feasible coalitions, the core is defined by
C (v) = {x ∈ Rn | x(S) ≥ v(S), ∀S ∈ F , x(N) = v(N)}
where x(S) is a shorthand for ∑i∈S xi. When F = 2N , the core is either empty or a convex
bounded polyhedron. However, for games whose cooperation is restricted, the study of
the core becomes much more complex, since it may be unbounded or even contain
no vertices (see a survey in [
We also present some results when F is not a distributive lattice, but a set lattice closed under intersection, or a regular set system.
Lastly, we introduce games on concept lattices, show that this induces in fact two games, and give some results on the core.
Vincent Duquenne
CNRS-IMJ / C&O, Université Pierre et Marie Curie,
4 place Jussieu, 75005 Paris, France
Abstract. Following [
As for the needed algorithms, many efforts have been done to “overtake” the
NEXT-CLOSURE algorithms since their discovery in 1984 [
Hence in a fresh original spirit of the early eighties, for all these and further developments we still promote “more simplicity with more structure” (and tolerances ...) for deepening the concept systems and lattice applications.
Keywords: closure operator, lattice, canonical basis of implications, quasi / pseudo-closed, (semi) lattice cores, perspectivities / arrows, congruences / tolerances, combinatorial exhaustive enumeration, NEXT-CLOSURE algorithms. Fig. 1. Peasants x possessions. Lattice gluing decomposable, hence substitution properties...
From : Models of possessions and Lattice Analysis, Social Sci. Information (1995).
A Collaborative Approach for FCA-Based Knowledge Extraction Finally, all the strategies are suggested to the expert with their impacts (Table 2) so that the expert can consider choosing one strategy. Once the expert makes a choice, the system will update the lattice accordingly. 3
We experimented our approach for extracting knowledge from a real text corpus of Fibromuscular Dysplasia extracted from PubMed1. The corpus consists of 400 texts.
In the preprocessing step, we used SemRep ([
Next, we built a Java script to transform the set annotations into a formal context. The lattice was produced by Galicia2 and exported as the XML document. The context built from our corpus contains 481 objects, 545 attributes formed by the association of the relationship of the object with which it relates. The lattice contains 523 concepts and the longest path from the Top to the Bottom is 7.
Then, we implemented a system with operation removing a concept from a lattice. When an expert, during the evaluation phase, asks for removing a concept, the system suggests a list of strategies and makes explicit their impacts on the lattice (lists of modified, deleted and new concepts) to the expert. Once the expert chooses one strategy, the system will update the lattice accordingly.
The required time for the expert to remove concepts has not yet been evaluated. Our experience shows that a judicious choice of a strategy in order to remove concepts has a strong impact on the speed of convergence towards a satisfactory knowledge model. 4
We presented a collaborative approach for FCA-based knowledge extraction. Our study shows how domain experts and machines can collaborate in building and changing a lattice. The system handles changes in a lattice and keeps a trace 1 http://www.ncbi.nlm.nih.gov/pubmed 2 http://sourceforge.net/projects/galicia/
My Thao Tang and Yannick Toussaint from the previous lattice. In that way, experts know the impact of a change. Our iterative and interactive approach takes advantage from FCA and reduces limitations due to the use of a formal method to model a complex cognitive process.
This approach opens several perspectives. We can do more to help the expert. Refining the cost function associated to changes can make easier the choice of one strategy. Tagging concepts that the expert agrees with and wants to keep unchanged all along the process could reduce the number of the suggested strategies. Performing several changes at once needs also more investigations.
J.V. Grebeneva, N.V. Shilov, and N.O. Garanina
A.P. Ershov Institute of Informatics Systems, Lavren’ev av., 6, Novosibirsk 630090, Russia j.grebeneva@gmail.com,
shilov@iis.nsk.su, garanina@iis.nsk.su Abstract. In this position paper we start with a motivation of our study of modal/description logics with values in concept lattices. Then we give a brief survey of approaches to lattice-valued modal and/or description logics. After that we study some methods of context symmetrization, because the description logic on concept lattices is defined for symmetric co ntexts only. We conclude with a list of problems related to comparison of different lattice-valued modal/description logics, different variants of context symmetrization and resulting description logics, decidability and axiomatization of these logics. 1 Let us start with an example that can explain our interest to study of polymodal and/or description logics with values in concept lattices. For it let us first fix some moment of time and let (1) U RL be the set of all Uniform Resource Locator that are valid (exist) at this moment, (2) Key be the set of all Key-words in any existing language that are conceivable in this time, (3) F , S and T be binary relations on U RL × Key that are implemented in some (non-real we assume) search engines First, Second and Third at the same moment of time that we fixed above.
Then let Sh&Ga be the set of all web-sites (their URL’s hereinafter) that
a search engine First finds by two key-words Shilov and Garanina; In terms
of Formal Concept Analysis (FCA) [
Assume that we need to know all sites Sh&Ga \ Gr that are found by First by key-words Shilov and Garanina but that (according to Third) does not contain any word that is common for all sites that are found by Second for the key-word Grebeneva. In terms of set theory expanded by FCAderivatives the desired set can be written as U RLSh&Ga \ U RL0G0 r, where ‘ 0’ ? This research is supported by Integration Grant Mathematical and methodological aspects of intellectual Information Systems n.15/10 of Siberian Branch, Russian Academy of Science. c paper author(s), 2013. Published in Manuel Ojeda-Aciego, Jan Outrata (Eds.): CLA 2013, pp. 287{292, ISBN 978{2{7466{6566{8, Laboratory L3i, University of La Rochelle, 2013. Copying permitted only for private and academic purposes. represents derivative in the formal context T = (U RL, Key, F ). Recall that U RLSh&Ga = {Shilov, Garanina}0 in KG, U RLGr = {Grebeneva}0 in KY . So we can not write the following equality
U RLSh&Ga\Gr = {Shilov, Garanina}0 \ {Grebeneva}000, but have to write another one
U RLSh&Ga\Gr = {Shilov, Garanina}↓F \ {Grebeneva}↓S↑T ↓T , where ‘↓F ’ represents the lower derivative in the context F, ‘↓S’ — the lower derivative in the context S, and ‘↓T ’ and ‘ ↑T ’ — the lower and upper derivatives in the context T. We believe that it would be nice to process queries like this one but (unfortunately) modern search engines can not do it; a part of the reason for this inability is due to lack of theory for processing such multi-context queries.
At the same time polymodal and/or descriptive logics (DL) [
[F ](Shilov&Garanina) & ¬[T ][T d][S]Grebeneva or in syntax of a description logic as the following concept term
∀F.(Shilov u Garanina) u ¬∀T.∀T d.∀S.Grebeneva.
An interpretation of FCA constructs in DL has been studied in [
A variant of description logic (namely ALC, Attribute Language with
Complements) with values in concept lattices was defined in [
Modal and Description Logic are closely related but different research paradigms:
they have different syntax and pragmatic, but very closely related semantics (in
spite of different terminology). Lattice-valued modal logics were introduced in
[
Description Logic (DL) is a logic for reasoning about concepts. But there
is also an algebraic formalism developed around concepts in terms of concept
lattices, namely Formal Concept Analysis (FCA). In this section we recall in brief
definition of description logic ALC on concept lattices of (symmetric) contexts
and some properties that follow from this definition, please refer [
Semantics of description logics on concept lattices comes from
lattice-theoretic characterization of ‘positive’ (i.e. without negation) concept constructs (for
close world semantics) that is given in the following proposition [
Conceptual interpretation is a formal context provided by an interpretation function.
Definition 1.
Conceptual interpretation is a four-tuple (G, M, I, Υ ) where (G, M, I) is a formal context, and an interpretation function Υ = ICS ∪ IRS, where CS and RS are standard concept and role symbols, and (1) ICS : CS → B(G, M, I) maps concept symbols to formal concepts, (2) IRS : RS → 2(G×G)∪(M×M) maps role symbols to binary relations. A formal context (G, M, I) or conceptual interpretation (G, M, I, Υ ) is said to be homogeneous (symmetric) if G = M (and binary relation I is symmetric in addition).
Semantics of ALC positive concept constructs >, ⊥, t, u, ∀, and ∃ as well
as semantics of negative construct ¬ are defined in [
Let (G, M, I, Υ ) be a conceptual interpretation, K be a formal context (G, M, I),
and B = (K) be the concept lattice of K. The interpretation function Υ can be
extended to all role terms in a terminological interpretation ((G ∪ M ), Υ ) in
the standard manner so that Υ (R) is a binary relation on (G ∪ M ) for every
role term R. The interpretation function Υ can be extended to all positive ALC
concept terms as follows. (1) Υ (>) = sup B and Υ (⊥) = inf B; (2) Υ (X t
Y ) = sup(Υ (X), Υ (Y )), and Υ (X u Y ) = inf(Υ (X), Υ (Y )); (3) Let Υ (X) =
1 But we use Υ instead of ‘·’ for terminological interpretation function for readability.
(Ex0, In0) ∈ B. Then (a) Υ (∀R. X) = supK {(Ex, In) ∈ B : ∀o ∈ Ex ∀a ∈
In ∀o0 ∈ G ∃a0 ∈ M ((o, o0) ∈ Υ (R) ⇒ o0 ∈ Ex0, (a, a0) ∈ Υ (R), and a0 ∈ In0)},
(b) I(∃R. X) = supK {(Ex, In) ∈ B : ∀o ∈ Ex ∀a ∈ In ∃o0 ∈ G ∀a0 ∈
M ((a, a0) ∈ Υ (R) ⇒ (o, o0) ∈ Υ (R), o0 ∈ Ex0, and a0 ∈ In0)}. In addition, if K
is a symmetric context and Υ (X) = (Ex, In) ∈ B, then Υ (¬X) = (In, Ex).
The following proposition [
The above proposition 2 leads to the following idea: to define semantics of ALC
with values in an arbitrary concept lattice by isomorphic embedding of the
background context into a symmetric one in such a way that for the positive fragment
of ALC the original semantics and the induced semantics equal each other.
Below we examine some opportunities how to “symmetrize” a given context, i.e.
to build a symmetric context from an arbitrary given background context.
Below we are going to study how to build a symmetric context from a given one
by set-theoretic and algebraic manipulations with a binary relation of the
context. Without loss of generality we may assume that the background context is
reduced [
Let K := (G, M, I) be a reduced context where G ∩ M = ∅ and Kd = (M, G, I−) be its dual context. Let also use the following notation for binary relations (on M and/or G): (1) ∅ be the empty binary relation, (2) × be a total binary relation, (3) E be the identity binary relation, (4) Ec be the complement for E. We would like to combine the cross-tables of K and the dual context G M Kd into the symmetric one in the following way: G ? I . Let us represent M I−1 ? the above cross-table in a shorter way as K?d K? and denote the corresponding symmetric context by K◦ := (G◦, M◦, I◦). Recall that B(G, M, I) is the concept lattice of the context K, B(G◦, M◦, I◦) is the concept lattice of the context K◦. Let us use the standard notation ‘0’ for derivatives in the background context K but (for distinction) the notation ‘◦’ for derivatives in the symmetric one. We are going to fill question quadrants by different combinations of ∅, ×, E and Ec. Below we study 9 of these 16 combinations.
Case 1. K∅d K∅ . It is the disjoint union of K and Kd. The concept lattice .
B(K◦) = B(K ∪ Kd) is a horizontal sum [
Case 2. K×d ∅K . The concept lattice of this context is isomorphic to the
vertical sum [
Case 3. (∅,×). This case is the same like a previous, but we have to swap components of the vertical sum.
Case 4. K×d K× . We have here the direct sum K + Kd of contexts K and Kd
[
Case 5. KEd EK . Let (X, Y ) ∈ B(K◦) be a concept and let X = A ∪. B where A ⊆ G, B ⊆ M . We have the following cases: (1) B = ∅. Let X = A. If |A| = 1, then (X, Y ) = ({a}, {a} ∪ A0), and (X, Y ) = (A, A0) otherwise. (2) A = ∅. Let X = B. If |B| = 1, then (X, Y ) = ({b}, {b} ∪ B0), and (X, Y ) = (B, B0) otherwise. (3) |B| = 1 and A 6= ∅. Let X = A ∪ {b}. If {b} ∈ A0 and |A| = 1, then (X, Y ) = ( a A { } ∪ {b}, {a} ∪ {b}), and if {b} ∈ A0 | | > 1, then (X, Y ) = (A ∪ {b}, {b}). (4) |B| > 1 and A 6= ∅. Let |B| > 1, then X = A ∪ B. If B ⊆ {a}0 and | | = 1, A then (X, Y ) = ({a} ∪ B, {a}).
Case 6. K∅d EK . This case is a very similar to the previous one. (1) B = ∅. (X, Y ) = (A, A0). (2) A = ∅. If |B| = 1 then (X, Y ) = ({b}, {b} ∪ B0) else (X, Y ) = (B, B0). (3) |B| = 1. If {b} ∈ A0, we have (X, Y ) = (A ∪ {b}, {b}). (4) |B| > 1. All the concepts in this case will be either > or ⊥.
Case 7. (E,∅). This case is similar to the previous.
Case 8. K×d EK . Let us use subcases as in the case 5. (1) B = ∅. (X, Y ) = (A, G ∪ A0). (2) A = ∅. If |B| = 1, then (X, Y ) = ({b}, {b} ∪ B0), and (X, Y ) = (B, B0) otherwise. (3) |B| = 1. If {b} ∈ A0, then (X, Y ) = (A ∪ {b}, {b} ∪ {b}0), else (X, Y ) = (A ∪ {b}, {b}0). (4) |B| > 1. (X, Y ) = (A ∪ B, B0).
Case 9. (E,×). This case is similar to the case 8. 4 Now we are ready to formulate several topics and problems that we consider natural and important for further research.
In [
In section 2 we represented the definition for description logic ALC with values in concept lattices of symmetric contexts and for positive fragment of ALC with values in arbitrary concept lattices. Questions: (1) Is decidable or axiomatizable the positive fragment of ALC with values in concept lattices? (2) Is decidable or axiomatizable ALC with values in concept lattices of symmetric contexts?
In the section 3 we examine 9 of 16 variants of context symmetrization. Topics for further research are following: (1) to study the remaining 7 cases of context symmetrization and isomorphic embedding with Ec in one or two free quadrants; (2) to examine under which embedding from these in these 16 the induced semantics of the positive fragment of ALC is equal to the original semantics.
Pablo Cordero, Manuel Enciso, Angel Mora, and Manuel Ojeda-Aciego
University of Ma´laga, Spain.
e-mail: {pcordero,enbciso}@uma.es, {amora,aciego}@ctima.uma.es
Abstract. The most popular basis in Formal Concept Analysis is the
Duquenne-Guigues basis, which ensure minimality in the number of
dependencies and it is built with pseudo-intents, and some method to
calculate these basis from an arbitrary set of implications have been
introduced. We propose in this paper, an automated method to calculate a
left-minimal direct basis from the set of all implications built between a
closed set and its corresponding minimal generators. The new basis also
has the minimal property demanded in the Duquenne-Guigues basis. It
is minimal in the cardinal of the set of implications, and minimal in the
size of the left-hand side of the implications.
1
Formal Concept Analysis [
Attribute implication can be managed syntactically using Armstrong’s
Axioms [
In [
We also introduce an automated method to calculate from a set of implications a left-minimal direct basis. The new method is based on the Simplification Logic for Funcional Dependency SLFD [?], a sound and complete inference system for implications. The main characteristics of SLFD is that its inference system is not built around the transitivity rule, like other well known Armstrong-like axiomatic systems for implications.
The work is organized as follows. In Section 2 we summarize preliminary
concepts and results on FCA concerning implications, basis, etc. In Section 3 we
outline the automated method that we have proposed in [
We will use the well-kwon notation used on Formal Concept Analysis (FCA) [
A relevant notion in the framework of Formal Concept Analysis is the concept
of attribute implication [
Alternatively, attribute implications allow us to capture all the information which can be deduced from a context. The set of all valid implications in a context may be syntactically managed by means of the following inference system known as Armstrong’s axioms. An implication basis of K is defined as a set L of implications of K from which any valid implication for K can be deduced by using Armstrong rules.
The goal is to obtain an implication basis with minimal size. This condition
is satisfied by the so-called Duquenne-Guigues (or stem) basis [
In the following, a summary of some interesting result of this survey are
showed. More specifically we present the definitions of some characteristics
studied in the survey that will be used to identify the kind of basis we introduce in
this paper. In the practice, it is interesting considering some properties [
Definition 1. A set of implications Γ it is said – minimal or non-redundant if Γ \ {X → Y } is not equivalent to Γ . – minimum if if it is of least cardinality, that is, | Γ |≤| Γ 0 | for all set of implications Γ 0 equivalent to Γ . – optimal if || Γ ||≤|| Γ 0 || for all set of implications Γ 0 equivalent to Γ , where the size of Γ is defined as || Γ ||=
X {X→Y ∈Γ } (| X | + | Y |)
And finally the two characteristics that constitutes the center of our basis are introduced: Definition 2. Let Γ = {X0 → Y0, . . . Xn → Yn} be a set of implications, it is said a left-minimal basis if there does not exist a Xi → Yi and a subset Xi0 ( Xi such that Γ \ {Xi → Yi} ∪ {Xi0 → Yi} is equivalent to Γ .
A set of implications Γ and is said direct if for all implication A → B the set A ∪ B is a closed set w.r.t. Γ . 3
Some methods to obtain generators of closed sets have been studied in [
We agree with these authors about the importance of the study of closed sets
and minimal generators. They constitute a source of essential information to
analyze a formal context. As we mention in the introduction, in [
In the literature, the most cited algorithm to compute Duquenne-Guigues
basis is the Ganter Algorithm [
Algorithm 1: Algorithm for computing a Duquenne-Guigues basis input : An LSI Φ output: A Duquenne-Guigues basis T := ∅; foreach hB, mg(B)i ∈ Φ do
foreach A ∈ mg(B) do T := T ∪ {A → B} repeat
S := T ; foreach A → B, C → D ∈ T such that A C and B 6⊆ C do
T := T r {C → D}; if B ∪ C 6= D then T := T ∪ {BC → D} until T = S ; S := ∅; foreach A → B ∈ T do S := S ∪ {A → B r A}; return S
In the following example, we show how to link the above algorithm with the
work presented in [
Example 1. For the input T = {ab → c, ac → bd, b → d, d → c}, Algorithm
MinGen 0 (see [
The following theorem ensures the minimality (w.r.t. the cardinality) of the Duquenne-Guigues basis.
Theorem 1. Any Duquenne-Guigues basis is a minimum basis.
In the following, we describe the algorihtm 2 to calculate a Left-Minimal Direct Basis based on Algorithm 1. The algorithm is polynomial and it is described searching a good understanding. Of course, an implementation using lectic order would improve considerably its efficiency.
First, we consider the following equivalence rules.
Definition 3 (Aggregation rules). Let A, B, C and D be sets of attributes. 1. If A ⊆ C then {A → B, C → D} ≡ {A → B, BC → D r B}. 2. If A ⊆ C ⊆ A ∪ B then {A → B, C → D} ≡ {A → BD}. Algorithm 2: Algorithm for computing a Left-Minimal Direct Basis input : An LSI Φ output: A Minimal Direct Basis T := ∅; foreach hB, mg(B)i ∈ Φ do
foreach A ∈ mg(B) do T := T ∪ {(A, A → B)} repeat
S := T ; foreach (M, A → B), (N, C → D) ∈ T such that A
T := T r {(N, C → D)}; if B ∪ C 6= D then T := T ∪ {(N, BC → D)} until T = S ; S := ∅; foreach (M, A → B) ∈ T do S := S ∪ {M → B r M }; return S C and B 6⊆ C do
We let for an extended version of this paper the proof that these equivalences rules are derived rules of equivalences presented in Theorem ??.
We propose in the Algorithm 2 the use of the two aggregation rules for reducing the number of implications and also the consequent of implications. Theorem 2. Let T = {(M1, A1 → B1), . . .} be a set of pairs with minimal generators and implications obtained from minimal generators and closed sets. The exhaustive application of the two Aggregation rules produces a left-minimal direct basis.
Example 2. Let T = {b → agh, d → a, bn → h, ab → def g, abc → djk} be
a set of implications, Algorithm MinGen 0 ([
In the first step of the Algorithm 2 with Φ we build T = {(b, b→abdefgh), (bc,bc →abcdefghkj), (bn, bn → abdef ghn), (bcn, bcn → abcdef ghkn), (d, d → ad)}.
Then, we apply the Aggregation rules foreach couple of elements in T . At the end of these comparisons, we have T = {(b, b → abdef gh), (bc, abcdef gh → abcdef ghkj), (d, d → ad)}. And from this, in the last foreach of the Algorithm 2, it renders the following left-minimal direct basis S = {b → adef gh, bc → adef ghkj, d → a}.
By the other side, Algorithm 1 return the following Duquenne-Guigues basis {b → adef gh, abcdef gh → kj, d → a} which in a minimal basis, but not a left-minimal one. 4 In this paper we present an algorithm which allows the transformation of a set of all closed sets and their corresponding minimal generators into a left-minimal direct basis. The study about the soundness, completeness, and complexity of the algorithms proposed are left to a extended paper.
The new method uses some equivalences deduced in the SLFD Logic and follows the Lectic order to traverse the list of minimal generators and implications associated and return a set of implications but with good properties.
As future work we propose to extend the Duquenne-Guigues basis definition
to consider a generalized fuzzy extension of implications. We propose the
definition introduced in [
Supported by Grants TIN2011-28084 of the Science and Innovation Ministry of Spain, and No. P09-FQM-5233 of the Junta de Andaluc´ıa.
Lenka Piskov´a, Tom´aˇs Horv´ath
University of Pavol Jozef Sˇafa´rik, Koˇsice, Slovakia lenka.piskova@student.upjs.sk, tomas.horvath@upjs.sk Abstract. In this paper, an experimental comparison of publicly available algorithms for computing intents of all formal concepts and mining frequent closed itemsets is provided. Experiments are performed on real data sets from UCI Machine Learning Repository and FIMI Repository.
Results of experiments are discussed at the end of the paper.
1
Formal Concept Analysis (FCA) [
Frequent itemset mining (FIM) introduced in [
FCA and FIM are two research fields that are closely related to each other
[
Finding the set of all intents (of formal concepts) is equivalent to finding
the set of all closed frequent itemsets using a minimum support equal to zero
[
The fastest algorithms for computing formal concepts are FCbO [
Implementations of algorithms for mining closed frequent itemsets were
experimentally compared2 and presented at FIMI’03 and FIMI’04 workshops [
In this paper, we provide an experimental comparison of 10 algorithms on
real-world data sets whose implementations are publicly available, two of them
compute formal concepts (FCbO and In-Close2) and the remaining 8 generate
closed frequent itemsets ([
# Transactions # Items Density (%) Small/Big
Accidents Car Evaluation
Connect Kosarak Mushroom
Retail Tic-tac-toe 340183 1728 67557 990002 8124 88162 958 468 25 129 41270 119 16469 29 33.8 28 43 8.1 23 10.3 34
Big Small Big Big Small Big Small
The experiments were conducted on the computing node with 16 cores equipped with 24 GB RAM memory running GNU/Linux openSUSE 12.1.
The measured times are CPU times. Each algorithm was run three times for each data set and the given minimum support threshold value to get the most accurate results. All reported times are the average times of the three 1 http://www.upriss.org.uk/fca/fcaalgorithms.html 2 http://fimi.ua.ac.be/experiments/ runs. The output was turned off, i.e. the results of algorithms (intents of formal concepts/frequent closed itemsets) were neither written to a file nor to the screen.
Some of the algorithms were originally developed to mine closed frequent itemsets. For Apriori, Carpenter and Eclat we have set the flag -tc to mine closed frequent itemsets. Similarly, we have used the flag -fci for Mafia.
The input file of In-Close2 is in the cxt (formal context) format while the input of other algorithms is in the standard FIMI format - each line represents a list of attributes of an object/a list of items in a transaction. The disadvantage of In-Close2 is that unlike other algorithms it also computes extents of formal concepts (in addition to their intents).
Some algorithms had problems on certain data sets. For mushroom, Apriori gets killed, Carpenter outputs an incorrect number of closed frequent itemsets (238827), DCI Closed does not calculate the result in a reasonable time (we have stopped the computation after a few hours). In-Close2 gives an incorrect number of formal concepts (59343) for tic-tac-toe.
For kosarak, FPClose is either aborted due to the invalid pointer or gives segmentation fault for the support 0.8% and supports less than or equal to 0.6%. For retail with minsup = 0, Apriori gets killed, Carpenter gives an incorrect number of closed frequent itemsets (2186693) and DCI Closed is aborted. In-Close2 gives segmentation fault for the supports lower or equal to 60% on accidents and for all supports except for 90% on connect.
We have compared the performance of the algorithms for mining intents of all formal concepts, i.e. closed frequent itemsets using minsup = 0 (typical task in FCA) on small data sets. The results are depicted in the table 2. Arguably, FCbO is the best algorithm for the given task, it is the fastest algorithm for car and mushroom and the third fastest for tic-tac-toe. LCM and Eclat perform well on these data sets, too. Considering also the results on retail with minsup = 0, LCM is the fastest algorithm and the runner-up are Eclat and FPClose.
For kosarak, in our experimental testing FPClose failed while FPClose was
the fastest algorithm for low as well as high values of support in [
We have experimentally compared algorithms for computing intents of formal concepts and algorithms for mining closed frequent itemsets on real-world data. Our experimental testing has no clear winner for different data sets and minimum support threshold setting. In our opinion, DCI Closed behaves well although it had some problems on the mushroom data set and the retail data set with minsup = 0. On small data sets, the fastest algorithm is FCbO. Acknowledgements: This work was partially supported by the research grants VEGA 1/0832/12 and the Center of knowledge and information systems in Koˇsice (ITMS 26220220158).
1. R. Agrawal, T. Imielinski, A. Swami: Mining association rules between sets of items in large databases. SIGMOD, 1993.
Alam, Mehwish, 237 Alcalde, Cristina, 225 Antoni, Lubom r, 117 Astudillo, Hernan, 163 Baixeries, Jaume, 33 Barbot, Nelly, 175 Barkstrom, Bruce R., 275 Bazin, Alexandre, 45 Bertet, Karell, 81 Burusco, Ana, 225 Buzmakov, Aleksey, 199 Caro-Contreras, David Ernesto, 141 Chekol, Melisachew Wudage, 237 Codocedo, V ctor, 163 Cordero, Pablo, 293 D az, Juan Carlos, 225 De Causmaecker, Patrick, 57 De Wannemacker, Stefan, 57 Dolques, Xavier, 129 Domenach, Florent, 93 Duquenne, Vincent, 7 Egho, Elias, 199 Enciso, Manuel, 293 Freese, Ralph, 1 Fuentes-Gonzalez, Ramon, 225 Ganascia, Jean-Gabriel, 45 Garanina, Natalia O., 287 Glodeanu, Cynthia Vera, 69 Gnatyshak, Dmitry V., 249 Goethals, Bart, 3 Grabisch, Michel, 5 Grebeneva, Julia V., 287 Guerin, Clement, 81 Ignatov, Dmitry I., 249 Jay, Nicolas, 199 Kaytoue, Mehdi, 33 Konecny, Jan, 153 Krdlo, Ondrej, 105, 117 Krajci, Stanislav, 117 Krmelova, Marketa, 187 Kuznetsov, Sergei O., 199, 249 Le Ber, Florence, 129 Medina, Jesus, 225 Mendez-Vazquez, Andres, 141 Miclet, Laurent, 175 Mihalcin, Patrik, 117 Miralles, Andre, 9 Mora, Angel, 293 Napoli, Amedeo, 33, 163, 199, 237 Nebut, Clementine, 9 Ojeda-Aciego, Manuel, 105, 153, 293 Osman Guedi, Abdoulkader, 9 Outrata, Jan, 261 Pelaez-Moreno, Carmen, 211 Piskova, Lenka, 299 Prade, Henri, 175 Rassi, Chedy, 199 Revel, Arnaud, 81 Shilov, Nikolay V., 287 Stanley, Renzo, 163 Tang, My Thao, 281 Torim, Ants, 21 Toussaint, Yannick, 281 Trnecka, Martin, 187 Valverde-Albacete, Francisco Jose, 211 CLA 2013, Proceedings of the Tenth International Conference on Concept Lattices and Their Applications Laboratory L3i & Computer Sciences, Image Processing and Intercation Lab University of La Rochelle Avenur Michel Crepeau 17042 La Rochelle Cedex 1
France Page count: 50