INRIA Nancy { Grand Est and LORIA, France The Eighth International Conference on Concept Lattices and Their Applications
CLA 2011 Nancy, France October 17{20, 2011
CLA 2011, October 17{20, 2011, Nancy, France. Copyright c 2011 by paper authors.
Copying permitted only for private and academic purposes. This volume is published and copyrighted by its editors.
Impression: Edition: First published: 2011 xii+419 100 1st Printed version published by INRIA Nancy { Grand Est and LORIA, France ISBN 978{2{905267{78{8
CLA 2011 was organized by the INRIA Nancy { Grand Est and LORIA
Sadok Ben Yahia Jean Diatta Peter Eklund Sergei O. Kuznetsov Michel Liquiere Engelbert Mephu Nguifo
Jose Balcazar Radim Belohlavek Karell Bertet Francois Brucker Claudio Carpineto Jean Diatta Felix Distel Florent Domenach Mireille Ducasse Alain Gely Cynthia Vera Glodeanu Marianne Huchard Vassilis G. Kaburlasos Stanislav Krajci Sergei O. Kuznetsov Leonard Kwuida Mondher Maddouri Rokia Missaoui Lhouari Nourine
Faculte des Sciences de Tunis, Tunisia Universite de la Reunion, France University of Wollongong, Australia State University HSE, Moscow, Russia LIRMM, Montpellier, France LIMOS, Clermont-Ferrand, France
University of Cantabria and UPC Barcelona, Spain Palacky University, Olomouc, Czech Republic University of La Rochelle, France University of Marseille, France Fondazione Ugo Bordoni, Roma, Italy Universite de la Reunion, France TU Dresden, Germany University of Nicosia, Cyprus IRISA Rennes, France University of Metz, France TU Dresden, Germany LIRMM, Montpellier, France TEI, Kavala, Greece University of P.J. Safarik, Kosice, Slovakia State University HSE, Moscow, Russia Zurich University of Applied Sciences, Switzerland URPAH, University of Gafsa, Tunisie UQO, Gatineau, Canada LIMOS, University of Clermont Ferrand, France
Manuel Ojeda-Aciego Jan Outrata Pascal Poncelet Uta Priss Olivier Raynaud Camille Roth Stefan Schmidt Baris Sertkaya Henry Soldano Gerd Stumme Petko Valtchev
Daniel Borchmann Peggy Cellier Sebastien Ferre Nathalie Girard Alice Hermann Mehdi Kaytoue Petr Krajca Christian Meschke Petr Osicka Violaine Prince Chedy Raissy Yoan Renaud Heiko Reppe Lucie Urbanova Jean Villerd
Felipe Melo Amedeo Napoli Chedy Rassi Jean Villerd
University of Malaga, Spain Palacky University, Olomouc, Czech Republic LIRMM, Montpellier, France Napier University, Edinburgh, United Kingdom LIMOS, University of Clermont Ferrand, France EHESS, Paris, France TU Dresden, Germany SAP Research Center, Dresden, Germany Universite of Paris 13, France University of Kassel, Germany Universite du Quebec a Montreal, Canada
Mathematical Morphology, Lattices, and Formal Concept Analysis : : : : : :
Isabelle Bloch Random concept lattices : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Richard Emilion Galois and his Connections|A retrospective on the 200th birthday of Evariste Galois : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Marcel Erne Canonical extensions, Duality theory, and Formal Concept Analysis : : : : :
Mai Gehrke Galois connections and residuation: origins and developments II : : : : : : : : :
Bruno Leclerc Galois connections and residuation: origins and developments I : : : : : : : : :
Bernard Monjardet Metrics, Betweeness Relations, and Entropies on Lattices and Applications 13
Dan Simovici
Vertical decomposition of a lattice using clique separators : : : : : : : : : : : : : :
Anne Berry, Romain Pogorelcnik and Alain Sigayret Building up Shared Knowledge with Logical Information Systems : : : : : : :
Mireille Ducasse, Sebastien Ferre and Peggy Cellier Comparing performance of algorithms for generating the DuquenneGuigues basis : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Konstantin Bazhanov and Sergei Obiedkov Filtering Machine Translation Results with Automatically Constructed Concept Lattices : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Y lmaz K l caslan and Edip Serdar Guner Concept lattices in fuzzy relation equations : : : : : : : : : : : : : : : : : : : : : : : : : : : Juan Carlos D az and Jesus Medina-Moreno 1 3 5 7 9 11 15 31 43 59 75 Adaptation knowledge discovery for cooking using closed itemset extraction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Emmanuelle Gaillard, Jean Lieber and Emmanuel Nauer Fast Mining of Iceberg Lattices: A Modular Approach Using Generators : 191 Laszlo Szathmary, Petko Valtchev, Amedeo Napoli, Robert Godin, Alix Boc and Vladimir Makarenkov Boolean factors as a means of clustering of interestingness measures of association rules : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 207 Radim Belohlavek, Dhouha Grissa, Sylvie Guillaume, Engelbert Mephu Nguifo and Jan Outrata Combining Formal Concept Analysis and Translation to Assign Frames and Thematic Grids to French Verbs : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 223
Ingrid Falk and Claire Gardent Generation algorithm of a concept lattice with limited access to objects : : 239
Christophe Demko and Karell Bertet Homogeneity and Stability in Conceptual Analysis : : : : : : : : : : : : : : : : : : : : 251
Paula Brito and Geraldine Polaillon A lattice-based query system for assessing the quality of hydro-ecosystems 265
Agnes Braud, Cristina Nica, Corinne Grac and Florence Le Ber The word problem in semiconcept algebras : : : : : : : : : : : : : : : : : : : : : : : : : : : 279
Philippe Balbiani Looking for analogical proportions in a formal concept analysis setting : : : 295
Laurent Miclet, Henri Prade and David Guennec Random extents and random closure systems : : : : : : : : : : : : : : : : : : : : : : : : : 309
Bernhard Ganter Extracting Decision Trees From Interval Pattern Concept Lattices : : : : : : 319
Zainab Assaghir, Mehdi Kaytoue, Wagner Meira and Jean Villerd A New Formal Context for Symmetric Dependencies : : : : : : : : : : : : : : : : : : 333
Jaume Baixeries Cheating to achieve Formal Concept Analysis over a large formal context 349
V ctor Codocedo, Carla Taramasco and Hernan Astudillo A FCA-based analysis of sequential care trajectories : : : : : : : : : : : : : : : : : : : 363
Elias Egho, Nicolas Jay, Chedy Raissi and Amedeo Napoli Querying Relational Concept Lattices : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 377 Zeina Azmeh, Mohamed Hacene-Rouane, Marianne Huchard,
Amedeo Napoli and Petko Valtchev Links between modular decomposition of concept lattice and bimodular decomposition of a context : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 393
Alain Gely
Abduction in Description Logics using Formal Concept Analysis and Mathematical Morphology: application to image interpretation : : : : : : : : : 405
Jamal Atif, Celine Hudelot and Isabelle Bloch A local discretization of continuous data for lattices: Technical aspects : : : 409
Nathalie Girard, Karell Bertet and Muriel Visani Formal Concept Analysis on Graphics Hardware : : : : : : : : : : : : : : : : : : : : : : 413
W. B. Langdon, Shin Yoo, and Mark Harman Author Index : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 417 The Eighth International Conference \Concept Lattices and Applications (CLA 2011)" is held in Nancy, France from October 17th until October 20th 2011. CLA 2011 is aimed at providing to everyone interested in Formal Concept Analysis and more generally in Concept Lattices or Galois Lattices, students, professors, researchers and engineers, a global and an advanced view of some of the last research trends and applications in this eld. As the diversity of the selected papers shows, there is a wide range of theoretical and practical research directions, around data and knowledge processing, e.g. data mining, knowledge discovery, knowledge representation, reasoning, pattern recognition, together with logic, algebra and lattice theory.
This volume includes the selected papers and the abstracts of the 7 invited talks. This year there were initially 47 submissions from which 27 papers were accepted as full papers and 3 papers as posters. We would like to thank here the authors for their work, often of very good quality, the members of the program committee and the external reviewers who did a great job as this can be seen in their reviews. This is one witnesses of the growing quality and importance of CLA, highlightening its leading position in the eld.
Next, this year is a little bit special while the bicentennial of the birth of Evariste Galois (1811{1832) is celebrated, particularly in France. Evariste Galois has something to do with Concept Lattices as they are based on a so-called \Galois connection". Among the invited speakers, some of them will discuss of these fundamental aspects of Concept Lattices. Moreover, this is also the occasion of thanking the seven invited speakers who, at least we hope that, will meet the wishes of the attendees.
We would like to thank rstly our rst sponsors, namely the CNRS GDR I3 and Institut National Polytechnique de Lorraine (INPL). Then we would like to thank the steering committee of CLA for giving us the occasion of leading this edition of CLA, the conference participants for their participation and support, and people in charge of the organization, especially Anne-Lise Charbonnier, Nicolas Alcaraz and Mehdi Kaytoue, whose help was very precious in many occasions. Finally, we also do not forget that the conference was managed (quite easily) with the Easychair system, paper submission, selection, and reviewing, and that Jan Outrata has o ered his les for preparing the proceedings.
Telecom ParisTech, CNRS LTCI, Paris, France Abstract. Lattice theory has become a popular mathematical framework in di erent domains of information processing, and various communities employ its features and properties, e.g. in knowledge representation, in logics, automated reasoning and decision making, in image processing, in information retrieval, in soft computing, in formal concept analysis. Mathematical morphology is based adjunctions, on the algebraic framework of posets, and more speci cally of complete lattices, which endows it with strong properties and allows for multiple applications and extensions. In this talk we will summarize the main concepts of mathematical morphology and show their instantiations in di erent settings, where a complete lattice can be built, such as sets, functions, partitions, fuzzy sets, bipolar fuzzy sets, formal logics . . . We will detail in particular the links between morphological operations and formal concept analysis, thus initiating links between two domains that were quite disconnected until now, which could therefore open new interesting perspectives.
MAPMO, University of Orleans, France Abstract. After presenting an algorithm providing concepts and frequent concepts, we will study the random size of concept lattices in the case of a Bernoulli(p) context. Next, for random lines which are independent and identically distributed or more generally outcomes of a Markov chain, we will show the almost everywhere convergence of the random closed intents towards deterministic intents. Finally we will consider the problem of predicting the number of concepts before choosing any algorithm.
University of Hannover, Germany Abstract. A frequently used tool in mathematics is what Oystein Ore called \Galois connections" (also \Galois connexions", \Galois correspondences" or \dual adjunctions"). These are pairs ('; ) of maps between ordered sets in opposite direction so that x (y) is equivalent to y '(x). This concept looks rather simple but proves very e ective. The primary gain of such \dually adjoint situations" is that the ranges of the involved maps are dually isomorphic: thus, Galois connections present two faces of the same medal.
Many concrete instances are given by what Garrett Birkho termed \polarities": these are nothing but Galois connections between power sets. In slightly di erent terminology, the fundamental observation of modern Formal Concept Analysis is that every \formal context", that is, any triple (J; M; I) where I is a relation between (the elements of) J and M , gives rise to a Galois connection (assigning to each subset of one side its \polar", \extent" or \intent" on the other side), such that the resulting two closure systems of polars are dually isomorphic; more surprising is the fact that, conversely, every dual isomorphism between two closure systems arises in a unique fashion from a relation between the underlying sets. In other words: the complete Boolean algebra of all relations between J and M is isomorphic to that of all Galois connections between {J and {M , and also to that of all dual isomorphisms between closure systems on J and M , respectively.
The classical example is the Fundamental Theorem of Galois Theory, establishing a dual isomorphism between the complete lattice of all intermediate elds of a Galois extension and that of the corresponding automorphism groups, due to Richard Dedekind and Emil Artin. In contrast to that correspondence, which does not occur explicitly in Galois' succinct original articles, a few other closely related Galois connections may be discovered in his work (of course not under that name). Besides these historical forerunners, we discuss a few other highlights of mathematical theories where Galois connections enter in a convincing way through certain \orthogonality" relations, and show how the Galois approach considerably facilitates the proofs. For example, each of the following important structural isomorphisms arises from a rather simple relation on the respective ground sets: { the dual isomorphism between the subspace lattice of a nite-dimensional linear space and the left ideal lattice of its endomorphism ring { the duality between algebraic varieties and radical ideals { the categorical equivalence between ordered sets and Alexandro spaces { the representation of complete Boolean algebras as systems of polars.
LIAFA CNRS { University of Paris 7, France Abstract. The theory of canonical extensions, developed by Jonsson and Tarski in the setting of Boolean algebras with operators, provides an algebraic approach to duality theory. Recent developments in this theory have revealed that in this algebraic guise duality theory is no more complicated outside than within the setting of Boolean algebras or distributive lattices. This has opened the possibility of exporting the highly developed machinery and knowledge available in the classical setting (e.g. in modal logic) to the completely general setting of partially ordered and non-distributive lattice ordered algebras. Duality theory in this setting is a special instance of the connection between formal contexts and concept lattices and thus allows methods of classical algebraic logic to be imported into FCA.
This will be an introductory talk on the subject of canonical extensions with the purpose of outlining the relationship between the three topics of the title.
As a preliminary remark, we recall that all considered contexts are reduced, and so, clarified. The clarification of a context is the fact to keep only one object o for all objects oi such that o′i = o′j (dually for attribute). It is clear that the set { o1, . . . , on} is a module in the bipartite graph and this process is equivalent to replace twin vertices by a representant.
Modules are not well situed for bipartite graphs. Twin vertices and connected components are the only modules for these graphs which are poorly decomposable. In goal to improve the decomposition, Fouquet and all have introduced bimodule, an analog of module for bipartite graphs.
Definition 4 (Bimodule). Let C = (O, A, I) be a bipartite graph, and (X, Y ) ⊂ (O, A), then (X, Y ) is a bimodule if no x ∈ O\X distinguishes A and no y ∈ A\Y distinguishes O.
Example of bimodule is given in Fig. 4: b and c are not distinguished with respect to vertices 4 (none of them are adjacent) or 3 (each of them is adjacent). Similarly, 1 and 2 are not distinguished by a (each of them is adjacent) and d (none of them is adjacent).
1 2 3
4 a b c
d
The whole bipartite (O, A), all vertices and pairs (j, m), j ∈ J , m ∈ M are trivial modules. In the following, we consider only non trivial bimodules, i.e bimodules with at least 3 elements.
Proposition 1. To any non trivial module X of lattice corresponds a bimodule of reduced context.
Proof. By definition of a lattice module, no elements inside the modules are distinguished by elements outside. It follows directly that no ∨-irreducible element outside the module distinguishes ∧-irreducible elements inside, and conversely.
Now, we want to know how a bimodule on the context may be interpretated in the concept lattice. First, we define a set in the lattice L from a bimodule X.
From a bimodule X = (J1, M1) ⊆ (J, M ), we build a subset C of concepts in L such that: – attributes concepts of X are in C, – objects concepts of X are in C, – C = [A, B] is a convex set, with A being maximal elements of C and B being minimal elements of C.
As previously seen, a lattice module corresponds to a context bimodule but, with the previous construction, the converse may be false: There exist bimodules of a context such that [A, B] does not correspond to a module in the lattice. As an example, Fig. 5 shows the lattice for the bipartite graph in Fig. 4. The set [A, B] is bounded by a dashed line.
Nevertheless, we can observe that, even if [A, B] is not a module, there exists a possibility of simplification, replacing a set of elements by two vertices and an edge.
(abcd, ∅) (ac, 2) (ab, 1)
(bcd, 3) (a, 12) (b, 13) (c, 23) (d, 34) (a, 12)
(d, 34) (abcd, ∅) 12
(bcd, 3) bc (∅, 1234) (∅, 1234)
Fig. 5. (a) lattice for bipartite graph in Fig. 4.a and (b) simplified lattice In the following, we show that when [A, B] is not a module, the shape of the set [A, B] is very constrained.
Proposition 2. Let [A, B] be a convex set built from a non trivial bimodule X. If [A, B] is not a module, then 1. | | [A, B] ∩ M | − | [A, B] ∩ J | | ≤ 1 2. if | [A, B] ∩ M | = | [A, B] ∩ J | , then A ⊆ J and B ⊆ M 3. if | max([A, B] ∩ J )| > 1, a+ = ∨ ai, ai ∈ max([A, B] ∩ J ) is such that ai ≺ a+ 4. if | min([A, B] ∩ M )| > 1, b− = ∧ bi, bi ∈ min([A, B] ∩ M ) is such that b− ≺ bi Proof. First, we show that | | [A, B] ∩ M | − | [A, B] ∩ J | | ≤ 1:
Suppose that [A, B] is not a module of the concept lattice, then there exists an element x ̸∈ [A, B] which distinguishes [A, B]. Without lost of generality, we can consider that x ∈ J and there exist y ∈ [A, B] such that x < y. We denote P1 the set of elements of [A, B] which are greater than x and P2 = [A, B]\P1. Since x is a ∨-irreducible element, it does not distinguish any ∧-irreducible elements in [A, B]. It follows that all ∧-irreducible elements in [A, B] are in P1 and none of them in P2 (or conversely).
In a finite lattice, every element e is ∧-dense, i.e. equal to the infimum of ∧-irreducible elements greater than e.
All ∨-irreducible elements in P2 cannot be distinguished by ∧-irreducible elements outside [A, B]. One unique ∨-irreducible element jmax of P2 may be defined by jmax = ∧ mi, . . . , mj , with mi, . . . , mj ̸∈ P1. All other ∨-irreducible elements in P2 are distinguished by ∧-irreducible elements in P1 (and only by these elements). So P2 ∩ J = X ∪ { jmax} (jmax may not exist).
Suppose | X| < | [A, B] ∩ M | , then there exist m1, m2 ∈ [A, B] ∩ M , j1 ∈ X such that j1 < m1, j1 < m2, m1| m2. It follows that j1 < m1 ∧ m2, which is impossible since j1 ∈ P2 and elements in P2 are not comparable to x.
Similarly, suppose | X| > | [A, B] ∩ M | , At least one ∨-irreducible element j of X is smaller than two ∧-irreducible elements m1 and m2 of P1, with m1| m2. This is impossible, so | X| = | [A, B] ∩ M | and | | [A, B] ∩ M | − | [A, B] ∩ J | | ≤ 1.
A ⊆ J and B ⊆ M follow directly of the fact that, by construction A and B contain irreducible elements and for each ∧-irreducible element m ∈ [A, B], there exists a ∨-irreducible element j ∈ [A, B] such that j < m.
It remains to prove that, when max([A, B]∩J ) contains at least two elements, a+ = ∨ ai, ai ∈ max([A, B]∩J ) is such that ai ≺ a+ (and dually for b−). Suppose it is not the case, then exist at least two elements x1 and x2 smaller than a+ and such that x1 and x2 distinguish elements in A. It follows that one can find a ∧-irreducible element which distinguishes ∨-irreducible elements in A and that is a contradiction.
It follows from this proposition that even if a set [A, B] is not a module, it can be collapsed into two vertices j and m such that j < m (but maybe not j ≺ m). j is a representant for the set [A, B] ∩ J and m a representant for the set [A, B] ∩ M . Moreover, j ≺ a+ and b+ ≺ m. 4
It is known that the family of modules of a graph (and so, of a lattice) and the family of bimodules of a bipartite graph are closed by intersection. Since the whole graph is a (trivial) module, it defines a lattice. So, for any set S of vertices, it is possible to use a closure operator to compute the smallest module which contains S. Algorithm 1 adds all vertices which distinguish respectively X and Y and the same process is repeated until no more vertex can be added.
Usually, bimodules decomposition does not produce all possible modules, but an inclusion tree such that all possible bimodules can be deduced from this tree. The root represents the whole graph and the leaves are vertices (trivial Input: (O, A, I) a bipartite graph, (X, Y ) ⊂ (O, A) Output: (Xc, Yc), smallest bimodule containing (X, Y ) begin continue ← true; (Xc, Yc) ← (X, Y ); while continue do continue ← f alse; forall the x ∈ J\Xc do if x distinguishes Yc then
Xc ← Xc ∪ x; continue ← true; end end forall the y ∈ M \Yc do if y distinguishes Xc then
Yc ← Yc ∪ y;
continue ← true;
end
end
end
return (Xc, Yc)
end
Algorithm 1: Computation of the smallest bimodule which contains (X, Y )
bimodules). It follows that the size of the tree is O(n), with n = | O| + | A| . In
[
All results in modular decomposition may be transposed immediatly to concept lattice and associated context to improve the readibility of the lattice.
b c d e f g h i 1 × 2 × 3 × × 4 × 5 × × 6 × × × 7 × × × 8 × × (a) × × 4 i 4 i 3 2 1 12 c c (b) b b e
7
e
8
Fig. 6. (a) “Living Beings and Water ” Context [
Second, investigation of bimodules properties shows that a bimodule may not correspond to a module of the lattice. Nevertheless, it remains possible to use it to produce a simplification of the original lattice. In such a case, the bimodule is collapsed in two elements a and b which represent ∨-irreducible elements and ∧-irreducible elements of the bimodule.
This last case is a particular case of another decomposition proposed for
inheritance hierarchies [
Image Interpretation
Jamal Atif1, Ce´line Hudelot2, and Isabelle Bloch3 1. Universite´ Paris Sud, LRI - TAO, Orsay, France jamal.atif@lri.fr 2. Ecole Centrale de Paris, France, celine.hudelot@ecp.fr 3. Telecom ParisTech - CNRS LTCI, Paris, France isabelle.bloch@telecom-paristech.fr Abstract. We propose an original way of enriching Description Logics with abduction reasoning services by computing the best explanations of an observation through mathematical morphology (using erosions) over the Concept Lattice of a background theory. The intended application is scene understanding and spatial reasoning.
Keywords: Abduction, Description Logics, FCA, Mathematical Morphology, Scene Understanding. 1
Introduction and notations
Scene interpretation can benefit from prior knowledge expressed as ontologies and from
description logics (DL) endowed with spatial reasoning tools as illustrated in our
previous work [
Based on the TBox T and the ABox A parts of a knowledge base K, we consider
ABox abduction [
We also rely on classical notions of (FCA), and denote a formal context by K = (G, M, I), where G is the set of objects, M the set of attributes and I ⊆ G × M a relation between the objects and attributes. For X ⊆ G and Y ⊆ M , the derivation operators are denoted by α and β, with α(X ) = { m ∈ M | ∀ g ∈ X, (g, m) ∈ I} , and β(Y ) = { g ∈ G | ∀ m ∈ Y, (g, m) ∈ I} . The concept lattice is defined from the classical partial ordering (X1, Y1) ≤ (X2, Y2) ⇔ X1 ⊆ X2 (⇔ Y2 ⊆ Y1).
Links between FCA and DL can be formalized via the notion of semantic context
KT := (G, M, I) defined as [
Abduction Operators from Complete Lattices
Mathematical Morphology on
Let (L, ) and (L′ , ′ ) be two complete lattices (which do not need to be equal). An
operator δ : L → L′ is a dilation if it commutes with the supremum. An operator
ε : L′ → L is an erosion if it commutes with the infimum. Classical properties of
mathematical morphology operators on complete lattices can be found in [
Here, with the aim of performing ABox abduction, we would like to reason on
subsets of G in order to find their best explanations (in G). Hence we consider the complete
lattice (P (G), ⊆) and operations from P (G) into P (G), where P (G) is the set of
subsets of G. Since the ordering on G is equivalent to the one of M , reasoning on G will
directly lead to results on M . In order to define explicit operations on P (G), we will make
use of particular erosions and dilations, called morphological ones [
Definition 1 Let A be a set of ABox assertions. A preferred explanation γ of A is defined from the last non-empty erosion as A⊲ ℓne γ d⇔ef γI ⊆ εℓ (AI ). In this equation, AI should be understood as the extent of the semantic concept associated with the DL concept A. When a constraint (e.g. a set of hypotheses belonging to the backgroud thedef ⇔ γI ⊆ ory) H has to be introduced, then this definition is modified as A ⊲ ℓne γ εℓ (HI ∩ AI ).
Starting from the subset to be explained, performing successive erosions amounts to “go down” in the lattice as much as possible, in order to find a non-empty set of interpretations.
Last Consistent Erosion. Another idea to introduce the constraint H is to erode it, as soon as it remains consistent with A. This leads to a second explanatory relation. Definition 2 A preferred explanation γ of A is defined from the last consistent erosion as: A ⊲ ℓc γ d⇔ef γI ⊆ εℓc (HI , AI ) ∩ AI , where AI corresponds to the extent of the semantic context and εℓc is the last consistent erosion defined as εℓc (HI , AI ) = εn(HI ) where n = max{ k | εk(HI ) ∩ AI 6= ∅} .
Here we consider erosion of H (i.e. HI ) alone, which means that we are looking at the subsets (submodels) of the models of A while being the most in the constraint. 408 4 - Disjunction on the left: if C ⊲ ℓc γ and D⊲ ℓc γ, then (C ⊔ D)⊲ ℓc γ (since the erosion is always performed on HI ). However this property does not hold for ⊲ ℓne since erosion does not commute with the supremum. - For the same reasons, we have the following property for ⊲ ℓc : if C ⊲ ℓc γ and
D ⊲ ℓc δ, then (C ⊔ D) ⊲ ℓc γ or (C ⊔ D) ⊲ ℓc δ, but it does not hold for ⊲ ℓne . - For conjunctions, we have a monotony property for ⊲ ℓc : if C ⊲ ℓc γ and γI ⊆ DI (i.e. D | = γ), then (C ⊓ D) ⊲ ℓc γ. For ⊲ ℓne , only a weaker form holds: if C ⊲ ℓne γ and D ⊲ ℓne γ, then (C ⊓ D) ⊲ ℓne γ. Note that this weaker form is also very natural and interesting.
Since both ⊲ ℓne and ⊲ ℓc operators perform erosion in the interpretation set ΔI , any solution belongs then to this set and K is a model of the obtained solution. Hence we have the following theorems: - Soundness: If ∃γ | A ⊲ γ then K | = γ.
- Completeness: K | = γ ⇒ ∃A | K | = A : A ⊲ γ. 3 With the aim of image interpretation, we have proposed abductive inference services in DL based on mathematical morphology over concept lattices, whose construction is based on exploiting the advances of using FCA in DL. The properties and interpretations of the introduced explanatory operators were analyzed, and the rational postulates of abductive reasoning were stated and extended to our context. Future work will concern the complexity analysis of these operators and associated algorithms, and a deeper investigation of their applications to image interpretation.
lattices: Technical aspects Nathalie Girard, Karell Bertet and Muriel Visani Laboratory L3i - University of La Rochelle - FRANCE
ngirar02, kbertet, mvisani@univ-lr.fr
Abstract. Since few years, Galois lattices (GLs) are used in data mining
and defining a GL from complex data (i.e. non binary) is a recent
challenge [
The discretization process consists in converting continuous attributes into
discrete attributes [
More formally for one discretization step, for selecting the best attribute to be cut, let (v1, . . . , vN ) be the sorted values of a continuous attribute V ∈ F . Each vi corresponds to a value verified by one object of the data set D. The set of possible cut-points is CV = (c1V , . . . , cVN−1) where ciV = vi+vi+1 ∀i ≤ N − 1. 2 The best cut-point, denoted c∗V , is defined by:
c∗V = argmaxciV ∈CV (gain(V, ciV , D)) where gain(V, c, D) denotes in a generic manner the splitting criterion computed for the attribute V , the cut-point c ∈ CV and the data set D. The best attribute, denoted V ∗, is the V ∈ F maximizing the splitting criterion computed for its best cut-point (i.e. c∗V ):
V ∗(D) = argmaxV ∈F (gain(V, c∗V , D)) c 2011 by the paper authors. CLA 2011, pp. 409{412. Copying permitted only for private and academic purposes. Volume published and copyrighted by its editors. Local Proceedings in ISBN 978{2{905267{78{8, Inria NGE/LORIA, Nancy, France. Finally for one discretization step, the attribute V ∗ is divided into two intervals: [v1, c∗V ∗ ] and ]c∗V ∗ , vn] and the process is repeated.
This process can be run using, at each step, all the objects in the training set.
This is global discretization. It can also be run during model construction
considering, at each step, only a part of the training set. This is local
discretization. In [
A GL is generally defined from a binary relation R between objects O and
binary attributes I - i.e. a binary data set also called a formal context - denoted
as a triplet T = (O, I, R). A GL is composed of a set of concepts - a concept
(A, B) is a maximal objects-attributes subset in relation - ordered by a
generalization/specialization relation. For more details on GL theory, notation and their
use in classification tasks, please refer to [
The main difference with DT is that splitting an attribute in a GL impacts all the other concepts of the GL that contain this attribute, and due to the order relation between concepts ≤, the structure of the GL is also modified. Whereas, when an attribute is split in a DT node, predecessors and others branches are not impacted. In order to select the best V ∗(M I) over all the concepts sharing this attribute, we introduce different computing of V ∗(M I).
A local discretization of continuous data for lattices: Technical aspects Let M I = {Dq = (Aq, Bq); q ≤ Q}} be the set of meet-irreducible concepts not satisfying S. The best attribute V ∗(Dq) associated to its best cut-point is first computed for each concept Dq ∈ M I:
V ∗(Dq) = argmaxV ∈Bq (gain(V, c∗V , Dq)) where c∗V is defined by (1) for Dq instead of D.
Let us define IM∗I = {V ∗(D1), . . . , V ∗(DQ)} the set of best attributes associated to each concept in M I. The best attribute V ∗(M I) among IM∗I can be defined in two different ways: By local discretization: Local discretization selects the best attribute V ∈ IM∗I as the one having the best gain for M I:
V ∗(M I) = argmaxV ∗(Dq)∈IM∗I (gain(V ∗(Dq), c∗V ∗(Dq), Dq)) By linear local discretization: Linear local discretization takes into account that the split of one attribute V ∈ IM∗I in a concept Dq can impact the other concepts. So we compute a linear combination of the criterion as the sum of the gain for each concept Dq0 ∈ M I containing this attribute V . The selected attribute is the one that gives the best linear combination: V ∗(M I) = argmaxV ∈IM∗I (
X Dq0 ∈MI|V ∈Bq0
|Aq0 | PDq∈MI |Aq| ∗ gain(V, c∗V , Dq0 )) (5) 3
The study is performed on three supervised databases of the UCI Machine
Learning Repository1: the Image Segmentation database (Image1), the Glass
Identification Database (GLASS) and the Breast Cancer Database (BREAST Cancer).
We also use one supervised data set stemming from GREC 2003 database2
described by the statistical Radon signature (GREC Radon). Table 1 presents the
complexity of each lattice structure associated to each discretization
algorithm and the classification performance using each GL by navigation [
Nb concepts Recognition rates
Local Linear Local Global Local Linear Local Global CHAID Image1 527 649 12172 90.33 91.57 82.23 90.95 GLASS 1950 2128 2074 71.11 72.60 73.18 63.72 BREAST Cancer 3608 2613 7784 91.66 91.23 90.05 93,47
GREC Radon 69 92 2192 90.43 90.17 81.42 92.94
CREST centre, Department of Computer Science,
University College London Gower Street, London WC1E 6BT, UK Abstract. We document a parallel non-recursive beam search GPGPU FCA CbO like algorithm written in nVidia CUDA C and test it on software module dependency graphs. Despite removing repeated calculations and optimising data structures and kernels, we do not yet see major speed ups. Instead GeForce 295 GTX and Tesla C2050 report 141 072 concepts (maximal rectangles, clusters) in about one second. Future improvements in graphics hardware may make GPU implementations of Galois lattices competitive.
Keywords: software module clustering, MDG, close-by-one, arithmetic intensity 1
Formal Concept Analysis [
Computer graphics gaming cards (GPUs) are relatively cheap and yet offer
far more computing power than the computer’s CPU alone. (E.g. a 295 GTX
contains 480 fully functioning processors and yet costs only a few hundred pounds.)
Also microprocessor trends suggest faster computing will require parallel
computing in future. There are already hundreds of millions of computers fitted with
graphics hardware which might be used for general purpose computing [
Krajca et al. [
Although In-close [
Krajca’s routines ComputeClosure and GenerateFrom essentially form a depth first search algorithm which builds and navigates a tree of formal concepts from a binary 0/1 matrix describing which object has which property. Since the search is recursive and operates on one point in the tree at one time, it is unsuitable for parallel operation on graphics cards. Our graphics card parallel version retains the tree but uses beam search rather than depth first search.
Instead of proceeding to the first leaf of the tree, recursively backing up
and then going forward to the next leaf and so on, in beam search, we also
start from the top of the tree and then proceed along every branch to the next
level. This requires saving information on the beam for every node at that level.
Beam search next expands the search again to cover everything at the next level
and so on until all the leafs of the tree have been reached. Notice instead of
working on a single point in the tree the beam covers many points which can
be worked on in parallel. Indeed within a couple of levels we can get a beam
containing tens of thousands of individual search points which can be processed
independently. This suits the GPU architecture which needs literally thousands
of independent processing threads for it to deliver its best performance [
Even for quite modest tree depths the beam width is limited by the available space in the GPU card. (We have a configuration limit of 1.8 million simultaneous parallel operations.) When a beam search exceeds this limit, only the first 1.8 million searches are loaded onto the GPU and the rest of the beam is queued on the host PC. (Although we have not done this, in multi-GPU systems it would be possible to split the beam between the GPUs, allocating up to 1.8 million to each GPU.) The GPU only searches to the next level. It returns the concepts found by the searches and the newly discovered branches which remain to be searched. The concepts are printed by the host PC and the new branches are added to the end of the beam to await their turn. Effectively the beam becomes a queue of points in the tree waiting to be searched. The number of parallel searches is mostly limited by the need to have space on the GPU for all the potential new branches. This depends upon the tree’s fan out which is problem dependent. Nonetheless the GPU can manage modest real software engineering examples (e.g. dependence clustering of the Linux kernel). Notice the beam will contain a mixture of pending search points at different depths in the tree.
Dataset krajca wiki random random random random
We would expect a linear speed advantage for FCbO from both using 64 bit operations and from using compiled rather than interpreted code. However on sizable examples, the ratio between the speed of FCbO and that of our Python code is huge. This hints that FCbO has some algorithmic advantage.
GPUs are often limited by the time taken to move data rather than to
perform calculations. “Arithmetic intensity” is the ratio of calculations per data
item. Typically this is in the range 4–64 FLOP/TDE [2, p206], we estimate the
arithmetic intensity of Krajca et al.’s algorithm [
Newer versions of CUDA have make it easier to overlap GPU operations. However our implementation does not do this. Since the work is spread across the multi-processors, we suspect that idle time is not a major problem.
There are many problems which are traditionally solved by depth first search.
However this may not suit low cost computer graphics GPU hardware. We have
implemented a form of beam search and demonstrated it on several existing FCA
benchmarks and ten software engineering dependence clustering problems [
Acknowledgements I am grateful for the assistance of Gernot Ziegler of nVidia. Steve Worley, Sarnath Kannan, Stephen Swift, Stan Seibert and Yuanyuan Zhang. Software engineering MDGs were supplied by Spiros Mancoridis. Tesla donated by nVidia. Funded by EPSRC grant EP/G060525/2.
References
Assaghir, Zainab, 319 Astudillo, Hernan, 349 Atif, Jamal, 405 Azmeh, Zeina, 377 Carlos D az, Juan, 75 Cellier, Peggy, 31 Codocedo, V ctor, 349 Colomb, Pierre, 131 Demko, Christophe, 239 Distel, Felix, 101 Ducasse, Mireille, 31 Egho, Elias, 363 Emilion, Richard, 3 Erne, Marcel, 5 Falk, Ingrid, 223 Ferre, Sebastien, 31 Grissa, Dhouha, 207 Guennec, David, 295 Guillaume, Sylvie, 207 Hacene-Rouane, Mohamed, 377 Harman, Mark, 413 Huchard, Marianne, 377 Hudelot, Celine, 405 Irlande, Alexis, 131 Jay, Nicolas, 363 K l caslan, Y lmaz, 59 Kaytoue, Mehdi, 175, 319 Konecny, Jan, 115 Krupka, Michal, 115 Kuznetsov, Sergei, 175 Langdon, W. B., 413 Le Ber, Florence, 265 Leclerc, Bruno, 9 Lieber, Jean , 87 Llanso, David, 143 Macko, Juraj, 175 Makarenkov, Vladimir, 191 Medina-Moreno, Jesus, 75 Meira, Wagner, 175, 319 Miclet, Laurent, 295 Monjardet, Bernard, 11 Napoli, Amedeo, 175, 191, 363, 377 Nauer, Emmanuel, 87 Nguifo, Engelbert Mephu, 207 Nica, Cristina, 265 Obiedkov, Sergei, 43 Outrata, Jan, 207 Pogorelcnik, Romain, 15 Polaillon, Geraldine, 251 Prade, Henri, 295 Raissi, Chedy, 363 Raynaud, Olivier, 131 Renaud, Yoan, 131 Ryssel, Uwe, 101 Sigayret, Alain, 15 Simovici, Dan, 13 Szathmary, Laszlo, 191 Taramasco, Carla, 349 Valtchev, Petko, 191, 377 Villerd, Jean, 319 Visani, Muriel, 409 Yoo, Shin, 413
Nancy, 2011, 1st 100