cla.inf.upol.cz
11th International Conference on Concept Lattices and Their Applications
Volume editors Karell Bertet Universite de La Rochelle La Rochelle, France Sebastian Rudolph Technische Universitat Dresden Dresden, Germany E-mail: sebastian.rudolph@tu-dresden.de Technical editor Sebastian Rudolph, sebastian.rudolph@tu-dresden.de Cover design c P. J. Safarik University, Kosice, Slovakia 2014 This work is subject to copyright. All rights reserved. Reproduction or publication of this material, even partial, is allowed only with the editors' permission. CLA 2014 was organized by the Institute of Computer Science, Pavol Jozef Safarik University in Kosice.
Steering Committee
Sadok Ben Yahia Jean Diatta Peter Eklund Sergei O. Kuznetsov Engelbert Mephu Nguifo Amedeo Napoli Manuel Ojeda-Aciego Jan Outrata Program Chairs
Program Committee
Cristina Alcalde Jamal Atif Jaume Baixeries Radim Belohlavek Sadok Ben Yahia Francois Brucker Ana Burusco Claudio Carpineto Pablo Cordero Mathieu D'Aquin Christophe Demko Jean Diatta Florent Domenach Vincent Duquenne
Faculte des Sciences de Tunis, Tunisia Universite de la Reunion, France University of Wollongong, Australia State University HSE, Moscow, Russia Universite de Clermont Ferrand, France LORIA, Nancy, France Universidad de Malaga, Spain Palacky University, Olomouc, Czech Republic
Univ del Pais Vasco, San Sebastian, Spain Universite Paris Sud, France Polytechnical University of Catalonia, Spain Palacky University, Olomouc, Czech Republic Faculty of Sciences, Tunis, Tunisia Ecole Centrale Marseille, France Universidad de Navarra, Pamplona, Spain Fondazione Ugo Bordoni, Roma, Italy Universidad de Malaga, Spain The Open University, Milton Keynes, UK Universite de La Rochelle, France Universite de la Reunion, France University of Nicosia, Cyprus
Universite Pierre et Marie Curie, Paris, France Sebastien Ferre Universite de Rennes 1, France Bernhard Ganter Technische Universitat Dresden, Germany Alain Gely Universite Paul Verlaine, Metz, France Cynthia Vera Glodeanu Technische Universitat Dresden, Germany Robert Godin Universite du Quebec a Montreal, Canada Tarek Hamrouni Faculty of Sciences, Tunis, Tunisia Marianne Huchard LIRMM, Montpellier, France Celine Hudelot Ecole Centrale Paris, France Dmitry Ignatov State University HSE, Moscow, Russia Mehdi Kaytoue LIRIS - INSA de Lyon, France Jan Konecny Palacky University, Olomouc, Czech Republic Marzena Kryszkiewicz Warsaw University of Technology, Poland Sergei O. Kuznetsov State University HSE, Moscow, Russia Leonard Kwuida Bern University of Applied Sciences, Switzerland Florence Le Ber Strasbourg University, France Engelbert Mephu Nguifo Universite de Clermont Ferrand, France Rokia Missaoui Universite du Quebec en Outaouais, Gatineau,
Canada Amedeo Napoli LORIA, Nancy, France Lhouari Nourine Universite de Clermont Ferrand, France Sergei Obiedkov State University HSE, Moscow, Russia Manuel Ojeda-Aciego Universidad de Malaga, Spain Jan Outrata Palacky University, Olomouc, Czech Republic Pascal Poncelet LIRMM, Montpellier, France Uta Priss Ostfalia University, Wolfenbuttel, Germany Olivier Raynaud LIMOS, Universite de Clermont Ferrand, France Camille Roth Centre Marc Bloch, Berlin, Germany Bar s Sertkaya SAP Research Center, Dresden, Germany Henry Soldano Laboratoire d'Informatique de Paris Nord, France Gerd Stumme University of Kassel, Germany Laszlo Szathmary University of Debrecen, Hungary Petko Valtchev Universite du Quebec a Montreal, Canada Francisco J. Valverde Albacete Universidad Nacional de Educacion a Distancia,
Spain Additional Reviewers
Organization Committee
Looking for Bonds between Nonhomogeneous Formal Contexts : : : : : : : : : Ondrej Kr dlo, L'ubom r Antoni and Stanislav Krajci An Algorithm for the Multi-Relational Boolean Factor Analysis based on Essential Elements : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 107
Martin Trnecka and Marketa Trneckova On Concept Lattices as Information Channels : : : : : : : : : : : : : : : : : : : : : : : : 119 Francisco J. Valverde Albacete, Carmen Pelaez-Moreno and
Anselmo Pen~as Using Closed Itemsets for Implicit User Authentication in Web Browsing : 131 Olivier Coupelon, Diye Dia, Fabien Labernia, Yannick Loiseau and Olivier Raynaud The Direct-optimal Basis via Reductions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 145 Estrella Rodr guez Lorenzo, Karell Bertet, Pablo Cordero, Manuel Enciso and Angel Mora Ordering Objects via Attribute Preferences : : : : : : : : : : : : : : : : : : : : : : : : : : : 157
Inma P. Cabrera, Manuel Ojeda-Aciego and Jozef Pocs DFSP: A New Algorithm for a Swift Computation of Formal Concept Set Stability : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 169
Ilyes Dimassi, Amira Mouakher and Sadok Ben Yahia Attributive and Object Subcontexts in Inferring Good Maximally Redundant Tests : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 181
Xenia Naidenova and Vladimir Parkhomenko Removing an Incidence from a Formal Context : : : : : : : : : : : : : : : : : : : : : : : 195
Martin Kauer and Michal Krupka Formal L-concepts with Rough Intents : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 207
Eduard Bartl and Jan Konecny Reduction Dimension of Bags of Visual Words with FCA : : : : : : : : : : : : : : 219
Ngoc Bich Dao, Karell Bertet and Arnaud Revel A One-pass Triclustering Approach: Is There any Room for Big Data? : : : 231 Dmitry V. Gnatyshak, Dmitry I. Ignatov, Sergei O. Kuznetsov and Lhouari Nourine Three Related FCA Methods for Mining Biclusters of Similar Values on Columns : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 243 Mehdi Kaytoue, Victor Codocedo, Jaume Baixeries and Amedeo Napoli De ning Views with Formal Concept Analysis for Understanding SPARQL Query Results : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 255
Mehwish Alam and Amedeo Napoli A Generalized Framework to Consider Positive and Negative Attributes in Formal Concept Analysis : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 267 Jose Manuel Rodr guez-Jimenez, Pablo Cordero, Manuel Enciso and Angel Mora Author Index : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 279 Formal Concept Analysis is a mathematical theory formalizing aspects of human conceptual thinking by means of lattice theory. As such, it constitutes a theoretically well-founded, practically proven, human-centered approach to data science and has been continuously contributing valuable insights, methodologies and algorithms to the scienti c community.
The International Conference \Concept Lattices and Their Applications (CLA)" is being organized since 2002 with the aim of providing a forum for researchers involved in all aspects of the study of FCA, from theory to implementations and practical applications. Previous years' conferences took place in Horn Becva, Ostrava, Olomouc (all Czech Republic), Hammamet (Tunisia), Montpellier (France), Olomouc (Czech Republic), Sevilla (Spain), Nancy (France), Fuengirola (Spain), and La Rochelle (France). The eleventh edition of CLA was held in Kosice, Slovakia from October 7 to 10, 2014. The event was organized and hosted by the Institute of Computer Science at Pavol Jozef Safarik University in Kosice. This volume contains the selected papers as well as abstracts of the four invited talks. We received 28 submissions of which 22 were accepted for publication and presentation at the conference. We would like to thank the contributing authors, who submitted high quality works. In addition we were very happy to welcome ve distinguished invited speakers: Jaume Baixeries, Hassan At-Kassi, Uta Priss, and Ondrej Cepek. All submitted papers underwent a thorough review by members of the Program Committee with the help of additional reviewers. We would like to thank all reviewers for their valuable assistance. A selection of extended versions of the best papers will be published in a renowned journal, pending another reviewing process.
The success of such an event heavily relies on the hard work and dedication of many people. Next to the authors and reviewers, we would also like to acknowledge the help of the CLA Steering Committee, who gave us the opportunity of chairing this edition and provided advice and guidance in the process. Our greatest thanks go to the local Organization Committee from the Institute of Computer Science, Pavol Jozef Safarik University in Kosice, who put a lot of effort into the local arrangements and provided the pleasant atmosphere necessary to attain the goal of providing a balanced event with a high level of scienti c exchange. Finally, it is worth noting that we bene ted a lot from the EasyChair conference management system, which greatly helped us to cope with all the typical duties of the submission and reviewing process.
Relationship between the Relational Database Model and FCA
The Relational Database Model (RDBM) [
The RDBM can be formulated from a set-theoretical point of view, such that a tuple is a partial function, and other basic operations in this model such as projections, joins, selections, etc, can be seen as set operations.
Another important feature of this model is the existence of constraints, which are first-order predicates that must hold in a relational database. These constraints mostly describe conditions that must hold in order to keep the consistency of the data in the database, but also help to describe some semantical aspects of the dataset.
In this talk, we consider some aspects of the RDBM that have been
characterized with FCA, focusing on different kinds of constraints that appear in
the Relational Model. We review some results that formalize different kinds of
contraints with FCA [
Hassan A¨ıt-Kaci
ANR Chair of Excellence
CE DAR Project
LIRIS Universite´ Claude Bernard Lyon 1
France The world is changing. The World Wide Web is changing. It started out as a set of purely notational conventions for interconnecting information over the Internet. The focus of information processing has now shifted from local disconnected disc-bound silos to Internet-wide interconnected clouds. The nature of information has also evolved. From raw uniform data, it has now taken the shape of semi-structured data and meaningcarrying so-called “Knowledge Bases.” While it was sufficient to process raw data with structure-aware querying, it has now become necessary to process knowledge with contents-aware reasoning. Computing must therefore adapt from dealing with mere explicit data to inferring implicit knowledge. How to represent such knowledge and how inference therefrom can be made effective (whether reasoning or learning) is thus a central challenge among the many now facing the world wide web.
So called “ontologies” are being specified and meant to encode formally encyclopedic as well as domain-specific knowledge. One early (still on-going) such effort has been the Cyc1 system. It is a knowledge-representation system (using LISP syntax) that makes use of a set of varied reasoning methods, altogether dubbed “commonsense.” A more recent formalism issued of Description Logic (DL)—viz. the Web Ontology Language (OWL2)—has been adopted as a W3C recommendation. It encodes knowledge using a specific standardized (XML, RDF) syntax. Its constructs are given a modeltheoretic semantics which is usually realized operationally using tableau3-based reasoning.4 The point is that OWL is clearly designed for a specific logic and reasoning method. Saying that OWL is the most adequate interchange formalism for Knowledge Representation (KR) and automated reasoning (AR) is akin to saying that English is the best designed human language for facilitating information interchange among humans—notwithstanding the fact that it was simply imposed by the most recent pervasive ruling power, just as Latin was Europe’s Lingua Franca for centuries.
Thus, it is fair to ask one’s self a simple question: “ Is there, indeed, a single most
adequate knowledge representation and reasoning method that can be such a norm? ”
1 http://www.cyc.com/platform/opencyc
2 http://www.w3.org/TR/owl-features/
3 http://en.wikipedia.org/wiki/Method_of_analytic_tableaux
4 Using of tableau methods is the case of the most prominent SW reasoner [
I personally do not think so. In this regard, I share the general philosophy of Doug Lenat5, Cyc’s designer—although not the haphazard approach he has chosen to follow. 6
If one ponders what characterizes an ontology making up a knowledge base, some specific traits most commonly appear. For example, it is universally acknowledged that, rather than being a general set of arbitrary formal logical statements describing some generic properties of “the world,” a formal knowledge base is generally organized as a concept-oriented information structure. This is as important a change of perspective, just as object-oriented programming was with respect to traditional method-oriented programming. Thus, some notion of property “inheritance” among partially-ordered “concepts” (with an “is-a” relation) is a characteristic aspect of KR formalisms. In such a system, a concept has a straightforward semantics: its denotes of set of elements (its “instances”) and the “is-a” relation denotes set inclusion. Properties attached to a concept denote information pertaining to all instances of this concept. All properties verified by a concept are thereforeinherited by all its subconcepts.
Sharing this simple characteristic, formal KR formalisms have emerged from symbolic mathematics that offer means to reason with conceptual information, depending on mathematical apparatus formalizing inheritance and the nature of properties attached to concepts. In Description Logic7, properties are called “roles” and denote binary relations among concepts. On the other hand, Formal Concept Analysis (FCA8) uses an algebraic approach whereby an “is-a” ordering is automatical derived from propositional properties encoding the concepts that are attached to as bit vectors. A concept is associated an attribute with a boolean marker (1 or “true”) if it possesses it, and with a (0 or “false”) otherwise. The bit vectors are simply the rows of the “property matrix” relating concepts to their attributes. This simple and powerful method, originally proposed by Rudolf Wille, has a dual interpretation when matching attributes with concepts possessing them. Thus, dually, it views attributes also as partially ordered (as the columns of the binary matrix). An elegant Galois-connection ensues that enables simple extraction of conceptual taxonomies (and their dual attribute-ordered taxonomies) from simple facts. Variations such as Relational Concept Analysis (RCA9) offer more expressive, and thus more sophisticated, knowledge while preserving the essential algebraic properties of FCA. It has also been shown how DL-based reasoning (e.g. OWL) can be enhanced with FCA.10
Yet another formalism for taxonomic attributed knowledge, which I will present in more detail in this presentation, is the Order-Sorted Feature (OSF ) constraint formalism. This approach proposes to see everything as an order-sorted labelled graph. 5 http://en.wikipedia.org/wiki/Douglas_Lenat 6 However, I may stand corrected in the future since knowledge is somehow fundamentally haphazard. My own view is that, even for dealing with a heterogenous world, I would rather favor mathematically formal representation and reasoning methods dealing with uncertainty and approximate reasoning, whether probabilistic, fuzzy, or dealing with inconsistency (e.g. rough sets, paraconsistency). 7 http://en.wikipedia.org/wiki/Description_logic 8 http://en.wikipedia.org/wiki/Formal_concept_analysis 9 http://www.hse.ru/data/2013/07/04/1286082694/ijcai_130803.pdf 10 http://ijcai-11.iiia.csic.es/files/proceedings/
T13-ijcai11Tutorial.pdf Sorts are set-denoting and partially ordered with an inclusion-denoting “is-a” relation, and so form a conceptual taxonomy. Attributes, called “ features,” are function-denoting symbols labelling directed edges between sort-labelled nodes. Such OSF graphs are a straightforward generalization of algebraic First-Order Terms (FOTs) as used in Logic Programming (LP) and Functional Programming (FP). Like FOTs, they form a lattice structure with OSF graph matching as the partial ordering, OSF graph unification as infimum (denoting set intersection), andOSF graph generalization as supremum.11 Both operations are very efficient. These lattice-theoretic properties are preserved when one endows a concept in a taxonomy with additional order-sorted relational and functional constraints (using logical conjunction for unification and disjunction for generalization for the attached constraints). These constraints are inherited down the conceptual taxonomy in such a way as to be incrementally enforceable as a concept becomes gradually refined.
The OSF system has been the basis of Constraint Logic Programming for KR
and ontological reasoning (viz. LIF E ) [
In this presentation, I will give a rapid overview of the essential OSF formalism for knowledge representation along its reasoning method which is best formalized as order-sorted constraint-driven inference. I will also illustrate its operational efficiency and scalability in comparison with those of prominent DL-based reasoners used for the Semantic Web.
The contribution of this talk to answering the question in its title is that the Semantic Web effort should not impose a priori putting all our eggs in one single (untested) basket. Rather, along with DL, other viable alternatives such as the FCA and OSF formalisms, and surely others, should be combined for realizing a truly semantic web. 11 This supremum operation, however, does not (always) denote set union—as for FOT subsumption, it is is not modular (and hence neither is it distributive). 12 http://en.wikipedia.org/wiki/Head-driven_phrase_structure_ grammar 13 http://www.cs.haifa.ac.il/˜ shuly/malta-slides.pdf 14 http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.2021
Linguistic Data Mining with FCA
ZeLL, Ostfalia University of Applied Sciences
Wolfenbu¨ttel, Germany
www.upriss.org.uk
The use of lattice theory for linguistic data mining applications in the widest sense has been independently suggested by different researchers. For example, Masterman (1956) suggests using a lattice-based thesaurus model for machine translation. Mooers (1958) describes a lattice-based information retrieval model which was included in the first edition of Salton’s (1968) influential textbook. Sladek (1975) models word fields with lattices. Dyvik (2004) generates lattices which represent mirrored semantic structures in a bilingual parallel corpus. These approaches were later translated into the language of Formal Concept Analysis (FCA) in order to provide a more unified framework and to generalise them for use with other applications (Priss (2005), Priss & Old (2005 and 2009)).
Linguistic data mining can be subdivided into syntagmatic and paradigmatic approaches. Syntagmatic approaches exploit syntactic relationships. For example, Basili et al. (1997) describe how to learn semantic structures from the exploration of syntactic verb-relationships using FCA. This was subsequently used in similar form by Cimiano (2003) for ontology construction, by Priss (2005) for semantic classification and by Stepanova (2009) for the acquisition of lexicosemantic knowledge from corpora.
Paradigmatic relationships are semantic in nature and can, for example, be extracted from bilingual corpora, dictionaries and thesauri. FCA neighbourhood lattices are a suitable means of mining bilingual data sources (Priss & Old (2005 and 2007)) and monolingual data sources (Priss & Old (2004 and 2006)). Experimental results for neighbourhood lattices have been computed for Roget’s Thesaurus, WordNet and Wikipedia data (Priss & Old 2006, 2010a and 2010b).
Previous overviews of linguistic applications of FCA were presented by Priss (2005 and 2009). This presentation summarises previous results and provides an overview of more recent research developments in the area of linguistic data mining with FCA. (a) Classes of Museums w.r.t Artists and Countries, e.g., the concept on the top left corner with the attribute France contains all the French Museums, i.e., Musee du Louvre (Louvre) and Musee d’Art Moderne (MAM). (VIEW BY ?museum) (b) Classes of Artists w.r.t Museums and Countries. (VIEW BY ?artist)
Fig. 1: Lattice-Based Views w.r.t Museum’s and Artist’s Perspective .
number of concepts, iceberg concept lattices can be used [
FCA also allows knowledge discovery using association rules. An implication
over the attribute set M in a formal context is of the form B1 → B2, where
B1, B2 ⊆ M . The implication holds iff every object in the context with an
attribute in B1 also has all the attributes in B2. For example, when (A1, B1) ≤
(A2, B2) in the lattice, we have that B1 → B2. Duquenne-Guigues (DG) basis
for implications [
Lattice-Based View Access
SPARQL Queries with Classification Capabilities The idea of introducing a VIEW BY clause is to provide classification of the results and add a knowledge discovery aspect to the results w.r.t the variables appearing in VIEW BY clause. Let Q be a SPARQL query of the form Q = SELECT ?X ?Y ?Z WHERE {pattern P} VIEW BY ?X then the set of variables V = {?X, ?Y, ?Z} 6. According to the definition 1 the answer of the tuple (V, P ) is represented as [[({?X, ?Y, ?Z}, P )]] = μi where i ∈ {1, . . . , k} and k is the number of mappings obtained for the query Q. For the sake of simplicity, μ|W is given as μ. Here, dom(μi) = {?X, ?Y, ?Z} which means that μ(?X) = Xi, 6 As W represents set of attribute values in the definition of a many-valued formal context, we represent the variables in select clause as V to avoid confusion. μ(?Y ) = Yi and μ(?Z) = Zi. Finally, a complete set of mappings can be given as {{?X → Xi, ?Y → Yi, ?Z → Zi}}.
The variable appearing in the VIEW BY clause is referred to as object variable7 and is denoted as Ov such that Ov ∈ V . In the current scenario Ov = {?X}. The remaining variables are referred to as attribute variables and are denoted as Av where Av ∈ V such that Ov ∪ Av = V and Ov ∩ Av = ∅, so, Av = {?Y, ?Z}. Example 2. Following the example in section 2, an alternate query with the VIEW BY clause can be given as: SELECT ?museum ?artist ?country WHERE { ?museum rdf:type dbpedia-owl:Museum . ?museum dbpedia-owl:location ?city . ?city dbpedia-owl:country ?country . ?painting dbpedia-owl:museum ?museum .
?painting dbpprop:artist ?artist} VIEW BY ?museum
?museum ?artist ?country μ1 Musee d’Art Moderne Pablo Picasso France μ2 Museo del Prado Raphael Spain ... ... ... ...
Here, V ={?museum, ?artist, ?country} and P is the conjunction of patterns in the WHERE clause then the evaluation of [[({?museum, ?artist, ?country} , P )]] will generate the mappings shown in Table 1. Accordingly, dom(μi) = {?museum, ?artist, ?country}. Here, μ1(?museum) = M usee d0Art M oderne, μ1(?artist) = P ablo P icasso and μ1(?country) = F rance. We have Ov = {?museum} because it appears in the VIEW BY clause and Av = {?artist, ?country}. Figure 1a shows the generated view when Ov = {?museum} and in Figure 1b, we have; Ov = {?artist} and Av = {?museum, ?country}.
Designing a Formal Context of Answer Tuples The results obtained by the query are in the form of set of tuples, which are then organized as a many-valued context.
Obtaining a Many-Valued Context (G, M, W, I): As described previously, we have Ov = {?X} then μ(?X) = {Xi}i∈{1,...,k}, where Xi denote the values obtained for the object variable and the corresponding mapping is given as {{?X → Xi}}. Finally, G = μ(?X) = {Xi}i∈{1,...,k}. Let Av = {?Y, ?Z} then M = Av and the attribute values W = {μ(?Y ), μ(?Z)} = {{Yi}, {Zi}}i∈{1,...,k}. The corresponding mapping for attribute variables are {{?Y → Yi, ?Z → Zi}}. 7 The object here refers to the object in FCA. In order to obtain a ternary relation, let us consider an object value gi ∈ G and an attribute value wi ∈ W then we have (gi, “?Y 00, wi) ∈ I iff ?Y (gi) = wi, i.e., the value of gi for attribute ?Y is wi, i ∈ {1, . . . , k} as we have k values for ?Y . Obtaining Binary Context (G, M, I): Afterwards, a conceptual scaling used for binarizing the many-valued context, in the form of (G, M, I). Finally, we have G = {Xi}i∈{1,...,k}, M = {Yi} ∪ {Zi} where i ∈ {1, . . . , k} for object variable Ov = {?X}. The binary context obtained after applying the above transformations to the SPARQL query answers w.r.t to object variable is called the formal context of answer tuples and is denoted by Ktuple.
Example 3. In the example Ov = {?museum}, Av = {?artist, ?country}. The answers obtained by this query are organized into a many-valued context as follows: the distinct values of the object variable ?museum are kept as a set of objects, so G = {M useeduLouvre, M useodelP rado, . . . }, attribute variables provide M = {artist, country}, W1 = {Raphael, LeonardoDaV inci, . . . } and W2 = {F rance, Spain, U K, . . . } in a many-valued context. The obtained manyvalued context is shown in Table 2. Finally, the obtained many-valued context is conceptually scaled to obtain a binary context shown in Table 3.
Museum Musee du Louvre Musee d’Art Moderne Museo del Prado National Gallery
Artist Country {Raphael, Leonardo Da Vinci, Caravaggio} {France}
{Pablo Picasso} {France} {Leon{aRrdaophDaael,VCinacria,vCagagraiov,agFgraion,cFisrcaoncGisocyoa}Goya} {UK}
{Spain}
The organization of the concept lattice is depending on the choice of
object variable and the attribute variables. Then, to group the artists w.r.t the
museums where their work is displayed and the location of the museums, the
object variable would be ?artist and the attribute variables will be ?museum
and ?country. Then, the scaling can be performed for obtaining a formal
context. In order to complete the set of attribute, domain knowledge can also be
taken into account, such as the the ontology related to the type of artists or
museums. This domain knowledge can be added with the help of pattern structures,
an approach linked to FCA, on top of many-valued context without having to
perform scaling. For the sake of simplicity, we do not discuss it in this paper.
Once the context is designed, the concept lattice can be built using an FCA
algorithm.There are some very efficient algorithms that can be used [
A different perspective on the same set of answers can also be retrieved, meaning that the group of artists w.r.t museums and country. For selecting French museums according to the artists they display, the object variable will be Ov = {?artist} and attribute variables will be Av = {?museum, ?country}. The lattice obtained in this case will be from Artist’s perspective (see Figure 1b). Now, it is possible to retrieve Musee du Louvre and Musee d’Art Moderne, which are the French museums and to obtain a specific French museum displaying the work of Leonardo Da Vinci a specific concept can be selected which gives the answer Musee du Louvre.
FCA provides a powerful means for data analysis and knowledge discovery. VIEW BY can be seen as a clause that engulfs the original SPARQL query and enhances it’s capabilities by providing views which can be reduced using iceberg concept lattices. Iceberg lattices provide the top most part of the lattice filtering out only general concepts. The concept lattice is still explored levelwise depending on a given threshold. Then, only concepts whose extent is sufficiently large are explored, i.e., the support of a concept corresponds to the cardinal of the extent. If further specific concepts are required the support threshold of the iceberg lattices can be lowered and the resulting concept lattice can be explored levelwise.
Knowledge Discovery: Among the means provided by FCA for knowledge discovery, the Duquenne-Guigues basis of implications takes into account a minimal set of implications which represent all the implications (i.e., association rules with confidence 1) that can be obtained by accessing the view i.e., a concept lattice. For example, implications according to Figure 1(a) state that all the museums in the current context which display Leonardo Da Vinci also display Caravaggio (rule: Leonardo Da Vinci → Caravaggio). It also says that only the museums which display the work of Caravaggio display the work of Leonardo Da Vinci Such a rule can be interesting if the museums which display the work of both Leonardo Da Vinci and Caravaggio are to be retrieved. The rule Goya, Raphael, Caravaggio → Spain suggests that there exists a museum which have works of Goya, Raphael, Caravaggio only in Spain, more precisely Museo Del Prado. (These rules are generated from only the part of SPARQL query answers shown as a context in Table 3). 5
Experimentation The experiments were conducted on real dataset. Our algorithm is implemented in Java using Jena8 platform and the experiments were conducted on a laptop with 2.60 GHz Intel core i5 processor, 3.7 GB RAM running Ubuntu 12.04. We extracted the information about the movie with their genre and location using SPARQL query enhanced with VIEW BY clause. The experiment shows that even though the background knowledge (ontological information) was not extracted the views reveal the hidden hierarchical information contained in the SPARQL query answers and can be navigated accordingly. Moreover, it also shows that useful knowledge is extracted from the answers through the the views using DG−Basis of implications. We also performed quantitative analysis where we discussed about the sparsity of the semantic web data. We also tested how our method scales with growing number of results. The number of answers obtained by YAGO were 100,000. The resulting view kept the classes of movies with respect to genre and location. The construction of YAGO ontology is based on the extraction of instances and hierarchical information from Wikipedia and Wordnet. In the current experiment, we sent a query to YAGO with the VIEW BY clause.
PREFIX rdf: http://www.w3.org/1999/02/22-rdf-syntax-ns# PREFIX yago: http://yago-knowledge.org/resource/ SELECT ?movie ?genre ?location WHERE { 8 https://jena.apache.org/
While querying YAGO it was observed that the genre and location information was also given in the ontology. The first level of the obtained view over the SPARQL query results over YAGO kept the groups of movies with respect to their languages. e.g., the movies with genre Spanish Language Films. However, as we further drill down in the concept lattice we get more specific categories which include the values from the location variable such as Spain, Argentina and Mexico. There were separate classes obtained for movies based on novels which were then further specialized by the introduction of the country attribute as we drill down the concept lattice. Finally with the help of lattice-based views, it can be concluded that the answers obtained by querying YAGO provides a clean categorization of movies by making use of the partially ordered relation between the concepts present in the concept lattice.
DG-Basis of Implications: DG-Basis of Implications for YAGO were calculated. The implications were filtered in three ways. Firstly, pruning was performed naively with respect to support threshold. Around 200 rules were extracted on support threshold of 0.2%. In order, to make the rules observable, the second type of filtering based on number of elements in the body of the rules was applied. All the implications which contained one item set in the body were selected. However, if there still are large number of implications to be observed then a third type of pruning can be applied which involved the selection of implications with different attribute type in head and body, e.g., in rule#1 head contains United States which is of type country and body contains the wikicategory. Such kind of pruning helps in finding attribute-attribute relations.
Table 4 contains some of the implications. Calculating DG − Basis of implications is actually useful in finding regularities in the SPARQL query answers which can not be discovered from the raw tuples obtained. For example, rule#1 states that RKO picture films is an American film production and distribution company as all the movies produced and distributed by them are from United States. Moreover, rule#2 says that all the movies in Oriya language are from India. This actually points to the fact that Oriya is one of many languages that is spoken in India. This rule also tells that Oriya language is only spoken in India. Rule#3 shows a link between a category from Wikipedia and Wordnet, which clearly says that the wikicategory is more specific than the wordnet category as remake is more general than Film remakes.
Impl. ID Supp. Implication 1. 96 wikicategory RKO Pictures films → United States 2. 46 wikicategory Oriya language films → India 3. 64 wikicategory Film remakes → wordnet remake 0 3 .
0
Fig. 2: Experimental Results. Besides the qualitative evaluation of LBVA, we performed an empirical evaluation. The characteristics of the dataset are shown in Table 5. These concepts were pruned with the help of iceberg lattices and stability for qualitative analysis.
The plots for the experimentation are shown in Figure 2. Figure 2(a) shows a comparison between the number of tuples obtained and the density of the formal context. The density of the formal context is the proportion of pairs in I w.r.t the size G × M . It has very low range for both the experiments, i.e., it ranges from 0.14% to 0.28%. This means in particular that the semantic web data is very sparse when considered in a formal context and deviates from the datasets usually considered for FCA (as they are dense). Here we can see that as the number of tuples increases the density of the formal context is decreasing which means that sparsity of the data also increases.
We also tested how our method scales with growing number of results. The number of answers obtained by YAGO were 100,000. Figure 2(b) illustrate the execution time for building the concept lattice w.r.t the number of tuples obtained. The execution time ranges from 20 to 100 seconds, it means that the the concept lattices were built in an efficient way and large data can be considered for these kinds of experiments. Usually the computation time for building concept lattices depends on the density of the formal context but in the case of semantic web data, as the density is not more than 1%, the computation completely depends on the number of objects obtained which definitely increase with the increase in the number of tuples (see Table 5).
No. of Tuples |G| |M| No. of Concepts 20% 3657 2198 7885 40% 6783 3328 19019 60% 9830 4012 31264 80% 12960 4533 43510 100% 15272 4895 55357
Conclusion and Discussion In LBVA, we introduce a classification framework based on FCA for the set of tuples obtained as a result of SPARQL queries over LOD. In this way, a view is organized as a concept lattice built through the use of VIEW BY clause that can be navigated where information retrieval and knowledge discovery can be performed. Several experiments show that LBVA is rather tractable and can be applied to large data.
For future work, we are interested in extending the VIEW BY clause by
including the available background knowledge of the resources using the formalism
of pattern structures [
A generalized framework to consider positive and negative attributes in formal concept
analysis.
J. M. Rodriguez-Jimenez, P. Cordero, M. Enciso and A. Mora
Universidad de M´alaga, Andaluc´ıa Tech, Spain.
{pcordero,enciso}@uma.es {amora,jmrodriguez}@ctima.uma.es Abstract. In Formal Concept Analysis the classical formal context is analized taking into account only the positive information, i.e. the presence of a property in an object. Nevertheless, the non presence of a property in an object also provides a significant knowledge which can only be partially considered with the classical approach. In this work we have modified the derivation operators to allow the treatment of both, positive and negative attributes which come from respectively, the presence and absence of the properties. In this work we define the new operators and we prove that they are a Galois connection. Finally, we have also studied the correspondence between the formal context in the new framework and the extended concept lattice, providing new interesting properties. 1
Introduction Data analysis of information is a well established discipline with tools and techniques well developed to challenge the identification of hide patterns in the data. Data mining, and general Knowledge Discovering, helps in the decision making process using pattern recognition, clustering, association and classification methods. One of the popular approaches used to extract knowledge is mining the patterns of the data expressed as implications (functional dependencies in database community) or association rules.
Traditionally, implications and similar notions have been built using the
positive information, i.e. information induced by the presence of attributes in objects.
In Manilla et al. [
In the framework of formal concept analysis, some authors have proposed the
mining of implications with positive and negative attributes from the apposition
of the context and its negation (K|K) [
ISBN 978{80{8152{159{1, Institute of Computer Science, Pavol Jozef Safarik University in Kosice, 2014. 268 2
R. Missaoui et al. [
In [
In this work we propose a deeper study of the algebraic framework for Formal Concept Analysis taking into account positive and negative information. The first step is to consider an extension of the classical derivation operators, proving to be Galois connection. As in the classical framework, this fact will allows to built the two usual dual concept lattices, but in this case, as we shall see, the correspondence among concept lattices and formal contexts reveal several characteristics which induce interesting properties. The main aim of this work is to establish a formal full framework which allows to develop in the future new methods and techniques dealing with positive and negative information.
In Section 2 we present the background of this work: the notions related with
formal concept analysis and negative attributes. Section 3 introduces the main
results which constitute the contribution of this paper.
2
In this section, the basic notions related with Formal Concept Analysis (FCA)
[
X↑ = {m ∈ M | hg, mi ∈ I for all g ∈ X} Y ↓ = {g ∈ G | hg, mi ∈ I for all m ∈ Y } (1) (2) X↑ is the subset of all attributes shared by all the objects in X and Y ↓ is the subset of all objects that have the attributes in Y . The pair (↑, ↓) constitutes a Galois connection between 2G and 2M and, therefore, both compositions are closure operators.
A pair of subsets hX, Y i with X ⊆ G and Y ⊆ M such X↑ = Y and Y ↓ = X is named a formal concept. X is named the extent and Y the intent of the concept. These extents and intents coincide with closed sets wrt the closure operators because X↑↓ = X and Y ↓↑ = Y . Thus, the set of all formal concepts is a lattice, named concept lattice, with the relation hX1, Y1i ≤ hX2, Y2i if and only if X1 ⊆ X2 (or equivalently, Y2 ⊆ Y1) This concept lattice will be denoted by B(G, M, I).
The concept lattice can be characterized in terms of attribute implications being expressions A → B where A, B ⊆ M . An implication A → B holds in a context K if A↓ ⊆ B↓. That is, any object that has all the attributes in A has also all the attributes in B. It is well known that the sets of attribute implications that are valid in a context satisfies the Armstrong’s Axioms: [Ref] Reflexivity: If B ⊆ A then ` A → B. [Augm] Augmentation: A → B ` A ∪ C → B ∪ C. [Trans] Transitivity: A → B, B → C ` A → C.
A set of implications Σ is considered an implicational system for K if: an implication holds in K if and only if it can be inferred, by using Armstrong’s Axioms, from Σ.
Armstrong’s axioms allow us to define the closure of attribute sets wrt an
implicational system (the closure of a set A is usually denoted as A+) and it
is well-known that closed sets coincide with intents. On the other hand, several
kind of implicational systems has been defined in the literature being the most
used the so-called Duquenne-Guigues (or stem) basis [
A more general framework is necessary to deal with this kind of information.
In [
I o1 o2 o3 o4 × × × × × × Table 1. A formal context that work we emphasized the necessity of a full development of an algebraic framework.
First, we begin with the introduction of an extended notation that allows us to consider the negation of attributes. From now on, the set of attributes is denoted by M , and its elements by the letter m, possibly with subindexes. That is, the lowercase character m is reserved for positive attributes. We use m to denote the negation of the attribute m and M to denote the set {m | m ∈ M } whose elements will be named negative attributes.
Arbitrary elements in M ∪ M are going to be denoted by the first letters in the alphabet: a, b, c, etc. and a denotes the opposite of a. That is, the symbol a could represent a positive or a negative attribute and, if a = m ∈ M then a = m and if a = m ∈ M then a = m.
Capital letters A, B, C,. . . denote subsets of M ∪ M . If A ⊆ M ∪ M , then A denotes the set of the opposite of attributes {a | a ∈ A} and the following sets are defined: – Pos(A) = {m ∈ M | m ∈ A} – Neg(A) = {m ∈ M | m ∈ A} – Tot(A) = Pos(A) ∪ Neg(A) Note that Pos(A), Neg(A), Tot(A) ⊆ M .
Once we have introduced the notation, we are going to summarize some
results concerning the mining of knowledge from contexts in terms of implications
with negative and positive attributes [
In our opinion, a deeper study was done by R. Missaoui et al. in [
In [
First, we extend the definitions of derivation operators, formal concept and attribute implication.
Definition 1. Let K = hG, M, Ii be a formal context. We define the operators ⇑: 2G → 2M∪M and ⇓: 2M∪M → 2G as follows: for X ⊆ G and Y ⊆ M ∪ M , X⇑ = {m ∈ M | hg, mi ∈ I for all g ∈ X}
∪ {m ∈ M | hg, mi 6∈ I for all g ∈ X} Y ⇓ = {g ∈ G | hg, mi ∈ I for all m ∈ Y }
∩ {g ∈ G | hg, mi 6∈ I for all m ∈ Y } Definition 2. Let K = hG, M, Ii be a formal context. A mixed formal concept in K is a pair of subsets hX, Y i with X ⊆ G and Y ⊆ M ∪ M such X⇑ = Y and Y ⇓ = X.
Definition 3. Let K = hG, M, Ii be a formal context and let A, B ⊆ M ∪ M , the context K satisfies a mixed attribute implication A → B, denoted by K |= A → B, if A⇓ ⊆ B⇓.
For example, in Table 1, as we previously mentioned, two different situations were presented. Thus, in this new framework we have that K 6|= b → d and K |= b → d whereas K 6|= b → c either K 6|= b → c.
Now, we are going to introduce the mining method for mixed attribute
implications. The method is strongly based on the set of inference rules built by
supplementing Armstrong’s axioms with the following ones, introduced in [
The closure of an attribute set A wrt a set of mixed attribute implications Σ, denoted as A++, is defined as the biggest set such that A → A++ can be inferred from Σ by using Armstrong’s Axioms plus [Cont] and [Rft]. Therefore, a mixed implication A → B can be inferred from Σ if and only if B is a subset of the closure of A, i.e. B ⊆ A++. Algorithm 1: Mixed Implications Mining
Data: K = hG, M, Ii Result: Σ set of implications begin Σ := ∅; Y := ∅; while Y < M do foreach X ⊆ Y do
A := (Y r X) ∪ X; if Closed(A, Σ) then
C := A⇓⇑; if A 6= C then Σ := Σ ∪ {A → C r A} return Σ end
Y := Next(Y ) // i.e. successor of Y in the lectic order 272 6
The proposed mining method, depicted in Algorithm 1, uses the inference
rules in such a way that it is not centered around the notion of key, but it
extends, in a proper manner, the classical NextClosure algorithm [
The algorithm to calculate the mixed implicational system doesn’t need to exhaustive traverse all the subsets of mixed attributes, but only those ones that are closed w.r.t. the set of implications previously computed. The Closed function is defined having linear cost and is used to discern when a set of attributes is not closed and thus, the context is not visited in this case.
Function Closed(A,Σ): boolean
Data: A ⊆ M ∪ M with Pos(A)∩Neg(A) = ∅ and Σ being a set of mixed implications.
Result: ‘true’ if A is closed wrt Σ or ‘false’ otherwise.
begin foreach B → C ∈ Σ do if B ⊆ A and C * A then exit and return false if B r A = {a},
A ∩ C 6= ∅, and a 6∈ A then exit and return false return true end 3
Mixed concept lattices As we have mentioned, the goal of this paper is to develop a deep study of the generalized algebraic framework. In this section we are going to introduce the main results of this paper providing the properties of the generalized concept lattice. The main pillar of our new framework are the two derivation operators introduced in Equations 4 and 5. The following theorem ensures that the pair of these operators is a Galois connection: Theorem 1. Let K = hG, M, Ii be a formal context. The pair of derivation operators (⇑, ⇓) introduced in Definition 1 is a Galois Connection.
Proof. We need to prove that, for all subsets X ⊆ G and Y ⊆ M ∪ M ,
X ⊆ Y ⇓ if and only if Y ⊆ X⇑ First, assume X ⊆ Y ⇓. For all a ∈ Y , we distinguish two cases: 1. If a ∈ Pos(Y ), exists m ∈ M with a = m and, for all g ∈ X, since X ⊆ Y ⇓, hg, mi ∈ I and therefore a = m ∈ X⇑. 2. If a ∈ Neg(Y ), exits m ∈ M with a = m and, for all g ∈ X, since X ⊆ Y ⇓, hg, mi 6∈ I and therefore a = m ∈ X⇑.
Conversely, assume Y ⊆ X⇑ and g ∈ X. To ensure that g ∈ Y ⇓, we need to prove that hg, ai ∈ I for all a ∈ Pos(Y ) and hg, ai ∈/ I for all a ∈ Neg(Y ), which is straightforward from Y ⊆ X⇑. tu
Therefore, above theorem ensures that ⇑◦⇓ and ⇓◦⇑ are closure operators. Furthermore, as in the classical case, both closure operators provide two dually isomorphic lattices. We denote by B](G, M, I) to the lattice of mixed concepts with the relation
hX1, Y1i ≤ hX2, Y2i iff X1 ⊆ X2 (or equivalently, iff Y1 ⊇ Y2) Moreover, as in the classical FCA, mixed implications and mixed concept lattice make up the two sides of the same coin, i.e. the information mined from the mixed formal context may be dually represented by means of a set of mixed attribute implications or a mixed concept lattice.
As we shall see later in this section, unlike the classical FCA, mixed concept lattices are restricted to an specific lattice subclass. There exist specific properties that lattices may observe to be considered a valid lattice structure which corresponds to a mixed formal context. In fact, this is one of the main goal of this paper, the characterization of the lattices in the mixed formal concept analysis.
In Table 3 six different lattices are depicted. In the classical framework, all of them may be associated with formal contexts, i.e. in the classical framework any lattice corresponds with a collection of formal context. Nevertheless, in the mixed attribute framework this property does not hold anymore. Thus, in Table 3, as we shall prove later in this paper, lattices 3 and 5 cannot be associated with a mixed formal context.
The following two definitions characterizes two kind of significant sets of attributes that will be used later: Definition 4. Let K = hG, M, Ii be a formal context. A set A ⊆ M ∪ M is named consistent set if Pos(A) ∩ Neg(A) = ∅.
The set of consistent sets are going to be denoted by Ctts, i.e.
Ctts = {A ⊆ M ∪ M | Pos(A) ∩ Neg(A) = ∅} If A ∈ Ctts then |A| ≤ |M | and, in the particular case where |A| = |M |, we have Tot(A) = M . This situation induces the notion of full set: 274 8
Lattice 1
Lattice 2
Lattice 3 Lattice 4
Lattice 5
Lattice 6
The following lemma, which characterize the boundary cases, is straightforward from Definition 1.
Lemma 1. Let K = hG, M, Ii be a formal context. Then ∅⇑ = M ∪ M , ∅⇓ = G and (M ∪ M )⇓ = ∅.
In the classical framework, the concept lattice B(G, M, I) is bounded by hM ↓, M i and hG, G↑i. However, in this generalized framework, as a direct consequence from above lemma, the lower and upper bounds of B](G, M, I) are h∅, M ∪ M i and hG, G⇑i respectively.
Lemma 2. Let K = hG, M, Ii be a formal context. The following properties hold: 1. For all g ∈ G, {g}⇑ is a full consistent set. 2. For all g1, g2 ∈ G, if g1 ∈ {g2}⇑⇓ then {g1}⇑ = {g2}⇑. 1 3. For all X ⊆ G, X⇑ = Tg∈X {g}⇑.
Proof. 1. It is obvious because, for all m ∈ M , hg, mi ∈ I or hg, mi ∈/ I and {g}⇑ = {m ∈ M | hg, mi ∈ I} ∪ {m ∈ M | hg, mi ∈/ I} being a disjoint union.
Thus, Tot({g}⇑) = M and Pos({g}⇑) ∩ Neg({g}⇑) = ∅. 1 That is, g1 and g2 have exactly the same attributes. 2. Since (⇑, ⇓) is a Galois connection, g1 ∈ {g2}⇑⇓ (i.e. {g1} ⊆ {g2}⇑⇓) implies {g2}⇑ ⊆ {g1}⇑. Moreover, by item 1, both {g1}⇑ and {g2}⇑ are full consistent and, therefore, {g1}⇑ = {g2}⇑. 3. In the same way that occurs in the classical framework, since (⇑, ⇓) is a Galois connection between (2G, ⊆) and (2M∪M , ⊆), for any X ⊆ G, we have that X⇑ = Sg∈X {g} ⇑ = Tg∈X {g}⇑. tu The above elementary lemmas lead to the following theorem emphasizing a significant difference with respect to the classical construction and it focuses on how the inclusion of new objects influences the structure of mixed concept lattice. Theorem 2. Let K = hG, M, Ii be a formal context, g0 be a new object, i.e. g0 ∈/ G, and Y ⊆ M be the set of attributes that g0 satisfies. Then, there exists g ∈ G such that {g}⇑ = {g0}⇑ if and only if there exists an isomorphism between B](G, M, I) and B](G ∪ {g0}, M, I ∪ {hg0, mi | m ∈ Y }).
That is, if a new different object (an object that differs at least in one attribute from each object in the context) is added to the formal context then the mixed concept lattice changes.
Proof. Obviously, if there exists g ∈ G such that {g}⇑ = {g0}⇑, from Lemma 2 g and g0 have exactly the same attributes, and moreover the lattices B](G, M, I) and B](G ∪ {g0}, M, I ∪ {hg0, mi | m ∈ Y }) are isomorphic.
Conversely, if the mixed concept lattices are isomorphic, there exists X ⊆ G such that the closed set X⇑ in B](G, M, I) coincides with {g0}⇑. Thus, in the mixed concept lattice B](G ∪ {g0}, M, I ∪ {hg0, mi | m ∈ X}), by Lemma 2, we have that {g0}⇑ = X⇑ = ∩g∈X {g}⇑. Moreover, since {g0}⇑ is a full consistent set, X 6= ∅ because of, by Lemma 1, ∅⇑ = M ∪ M . Therefore, for all g ∈ X (there exists at least one g ∈ X), g0 ∈ {g}⇑ and, by Lemma 2, {g}⇑ = {g0}⇑. tu Example 1. Let K1 = ({g1, g2}, {a, b, c}, I1) and K2 = ({g1, g2, g3}, {a, b, c}, I2) be formal contexts where I1 and I2 are the binary relations depicted in Table 4. Note that K2 is built from K1 by adding the new object g3. In the classical frameI1 g1 g2 a × × b
c
I2 g1 g2 g3 a b c work, the concept lattices B({g1, g2}, {a, b, c}, I1) and B({g1, g2, g3}, {a, b, c}, I2) are isomorphic. See Figure 1.
However, the lattices of mixed concepts cannot be isomorphic because the new object g3 is not a repetition of one existing object. See Figure 2.
The following theorem characterizes the atoms of the new concept lattice B]. B { ( g1, g2 , a, b, c , I )
1
B { Fig. 1. Lattices obtained in the classical framework B { B {
Fig. 2. Lattices obtained in the extended framework Theorem 3. Let K = hG, M, Ii be a formal context. The set of atoms in the lattice B](G, M, I) is {h{g}⇑⇓, {g}⇑i | g ∈ G}.
Proof. First, fixed g0 ∈ G, we are going to prove that the mixed concept h{g0}⇑⇓, {g0}⇑i is an atom in B](G, M, I). If hX, Y i is a mixed concept such that h∅, M ∪ M i < hX, Y i ≤ h{g0}⇑⇓, {g0}⇑i, then {g0}⇑ ⊆ Y = X⇑ M ∪ M . By Lemma 2, {g0}⇑ ⊆ X⇑ = Tg∈X {g}⇑. Moreover, for all g ∈ X 6= ∅, by Lemma 2, both {g0}⇑ and {g}⇑ are full consistent sets and, since {g0}⇑ ⊆ {g}⇑, we have {g0}⇑ = {g}⇑. Therefore, {g0}⇑ = X⇑ = Y and hX, Y i = h{g0}⇑⇓, {g0}⇑i.
Conversely, if hX, Y i is an atom in B](G, M, I), then X 6= ∅ and there exists g0 ∈ X. Since (⇑, ⇓) is a Galois connection, {g0}⇑ ⊇ X⇑ = Y and, therefore, h{g0}⇑⇓, {g0}⇑i ≤ hX, Y i. Finally, since hX, Y i is an atom, we have that hX, Y i = h{g0}⇑⇓, {g0}⇑i. tu
The following theorem establishes the characterization of the mixed concept lattice, proving that atoms and join irreducible elements are the same notions. Theorem 4. Let K = hG, M, Ii be a formal context. Any element in B](G, M, I) is ∨-irreducible if and only if it is an atom.
Proof. Obviously, any atom is ∨-irreducible. We are going to prove that any ∨-irreducible element belongs to {h{g}⇑⇓, {g}⇑i | g ∈ G}. Let hX, Y i be a ∨irreducible element. Then, by Lemma 2, Y = X⇑ = Tg∈X {g}⇑. Let X0 be the smaller set such that X0 ⊆ X and Y = Tg∈X0 {g}⇑. If X0 is a singleton, then hX, Y i ∈ {h{g}⇑⇓, {g}⇑i | g ∈ G}.
Finally, we prove that X0 is necessarily a singleton. In other case, a bipartition of X0 in two disjoint sets Z1 and Z2 can be made satisfying Z1∪Z2 = X0, Z1 6= ∅, Z2 6= ∅ and Z1 ∩ Z2 6= ∅. Then, Y = Tg∈Z1 {g}⇑ ∩ Tg∈Z2 {g}⇑ = Z1⇑ ∩ Z2⇑ and so hX, Y i = hZ1⇑⇓, Z1⇑i ∨ hZ2⇑⇓, Z2⇑i and Z1⇑ 6= Y 6= Z2⇑. However, it is not posible because hX, Y i is ∨-irreducible. tu
As a final end point of this study, we may conclude that unlike in the classical framework, not every concept lattice may be linked with a formal context. Thus, lattices number 3 and 5 from Table 3 cannot be associated with a mixed formal context. Both of them have one element which is not an atom but, at the same time, it is a join irreducible element in the lattice. More specifically, there does not exists a mixed concept lattice with three elements. 4
Conclusions In this work we have presented an algebraic study of a general framework to deal with negative and positive information. After considering new derivation operators we prove that they constitutes a Galois connection. The main results of the work are devoted to establish the new relation among mixed concept lattices and mixed formal concepts. Thus, the most outstanding conclusions are that: 278 12 – the inclusion of a new (and different) object in a formal concept has a direct effect in the structure of the lattice, producing a different lattice. – no any kind of lattice may be associated with a mixed formal context, which induces a restriction in the structure that mixed concept lattice may have. Acknowledgements Supported by grant TIN2011-28084 of the Science and Innovation Ministry of Spain, co-funded by the European Regional Development Fund (ERDF). References
At-Kaci, Hassan, 3 Al-Msie'Deen, Ra'Fat, 95 Alam, Mehwish, 255 Antoni, L'ubom r, 35, 83 Baixeries, Jaume, 1, 243 Bartl, Eduard, 207 Ben Yahia, Sadok, 169 Bertet, Karell, 145, 219 Bich Dao, Ngoc, 219 Cabrera, Inma P., 157 Ceglar, Aaron, 23 Cepek, Ondrej, 9 Codocedo, Victor, 243 Cordero, Pablo, 145, 267 Coupelon, Olivier, 131 Dia, Diye, 131 Dimassi, Ilyes, 169 Enciso, Manuel, 145, 267 Gnatyshak, Dmitry V., 231 Gunis, Jan, 35 Huchard, Marianne, 11, 95 Ignatov, Dmitry I., 231 Ikeda, Madori, 47, 59
Author Index
Liquiere, Michel, 11 Loiseau, Yannick, 131 Mora, Angel, 145, 267 Mouakher, Amira, 169 Naidenova, Xenia, 181 Napoli, Amedeo, 243, 255 Nebut, Clementine, 11 Nourine, Lhouari, 231 Ojeda-Aciego, Manuel, 157 Otaki, Keisuke, 47, 59 Parkhomenko, Vladimir, 181 Pattison, Tim, 23 Pelaez-Moreno, Carmen, 119 Pen~as, Anselmo, 119 Pocs, Jozef, 157 Priss, Uta, 7 Raynaud, Olivier, 131 Revel, Arnaud, 219 Rodr guez Lorenzo, Estrella, 145 Rodr guez-Jimenez, Jose Manuel, 267 Saada, Hajer, 11 Seki, Hirohisa, 71 Seriai, Abdelhak, 95 Snajder L'ubom r, 35 Trnecka, Martin, 107 Trneckova, Marketa, 107 Urtado, Christelle, 95 Valverde Albacete, Francisco J., 119 Vauttier, Sylvain, 95 Yamamoto, Akihiro, 47, 59 Title: CLA 2014, Proceedings of the Eleventh International
Conference on Concept Lattices and Their Applications Publisher: Pavol Jozef Safarik University in Kosice Expert advice: Library of Pavol Jozef Safarik University in Kosice (http://www.upjs.sk/pracoviska/univerzitna-kniznica) Year of publication: 2014 Number of copies: 70 Page count: XII + 280 Authors sheets count: 15 Publication: First edition Print: Equilibria, s.r.o.