Formal Concept Analysis

Frontmatter

Towards Generic Pattern Mining

Abstract

Frequent Pattern Mining (FPM) is a very powerful paradigm for mining informative and useful patterns in massive, complex datasets. In this paper we propose the Data Mining Template Library, a collection of generic containers and algorithms for FPM, as well as persistency and database management classes. DMTL provides a systematic solution to a whole class of common FPM tasks like itemset, sequence, tree and graph mining. DMTL is extensible, scalable, and high-performance for rapid response on massive datasets. Our experiments show that DMTL is competitive with special purpose algorithms designed for a particular pattern type, especially as database sizes increase.

Mohammed J. Zaki, Nagender Parimi, Nilanjana De, Feng Gao, Benjarath Phoophakdee, Joe Urban, Vineet Chaoji, Mohammad Al Hasan, Saeed Salem

Conceptual Exploration of Semantic Mirrors

Abstract

The “Semantic Mirrors Method” (Dyvik, 1998) is a means for automatic derivation of thesaurus entries from a word-aligned parallel corpus. The method is based on the construction of lattices of linguistic features. This paper models the Semantic Mirrors Method with Formal Concept Analysis. It is argued that the method becomes simpler to understand with the help of FCA. This paper then investigates to what extent the Semantic Mirrors Method is applicable if the linguistic resource is not a high quality parallel corpus but, instead, a medium quality bilingual dictionary. This is a relevant question because medium quality bilingual dictionaries are freely available whereas high quality parallel corpora are expensive and difficult to obtain. The analysis shows that by themselves, bilingual dictionaries are not as suitable for the Semantic Mirrors Method but that this can be improved by applying conceptual exploration. The combined method of conceptual exploration and Semantic Mirrors provides a useful toolkit specifically for smaller size bilingual resources, such as ontologies and classification systems. The last section of this paper suggests that such applications are of interest in the area of ontology engineering.

Uta Priss, L. John Old

Towards a Formal Concept Analysis Approach to Exploring Communities on the World Wide Web

Abstract

An interesting problem associated with the World Wide Web (Web) is the definition and delineation of so called Web communities. The Web can be characterized as a directed graph whose nodes represent Web pages and whose edges represent hyperlinks. An authority is a page that is linked to by high quality hubs, while a hub is a page that links to high quality authorities. A Web community is a highly interconnected aggregate of hubs and authorities. We define a community core to be a maximally connected bipartite subgraph of the Web graph.

We observe that the web subgraph can be viewed as a formal context and that web communities can be modeled by formal concepts. Additionally, the notions of hub and authority are captured by the extent and intent, respectively, of a concept. Though Formal Concept Analysis (FCA) has previously been applied to the Web, none of the FCA based approaches that we are aware of consider the link structure of the Web pages. We utilize notions from FCA to explore the community structure of the Web graph. We discuss the problem of utilizing this structure to locate and organize communities in the form of a knowledge base built from the resulting concept lattice and discuss methods to reduce the complexity of the knowledge base by coalescing similar Web communities. We present preliminary experimental results obtained from real Web data that demonstrate the usefulness of FCA for improving Web search.

Jayson E. Rome, Robert M. Haralick

Automatic Selection of Noun Phrases as Document Descriptors in an FCA-Based Information Retrieval System

Abstract

Automatic attribute selection is a critical step when using Formal Concept Analysis (FCA) in a free text document retrieval framework. Optimal attributes as document descriptors should produce smaller, clearer and more browsable concept lattices with better clustering features. In this paper we focus on the automatic selection of noun phrases as document descriptors to build an FCA-based IR framework. We present three different phrase selection strategies which are evaluated using the Lattice Distillation Factor and the Minimal Browsing Area evaluation measures. Noun phrases are shown to produce lattices with good clustering properties, with the advantage (over simple terms) of being better intensional descriptors from the user’s point of view.

Juan M. Cigarrán, Anselmo Peñas, Julio Gonzalo, Felisa Verdejo

Combining Spatial and Lattice-Based Information Landscapes

Abstract

In this paper we report on practical information visualization aspects of Conceptual Knowledge Processing (CKP), realizing and illustrating Wille’s “conceptual landscapes” in the context of developing a conceptual information system to determine surfing conditions on the South Coast of New South Wales, Australia. This novel application illustrates some (if not all) of Wille’s CKP tasks: exploring, searching, recognizing, identifying, analyzing, investigating, deciding, restructuring and memorizing (all but improving). It does this by concentrating on combining an information landscape with maps of the physical world.

Jon Ducrou, Peter Eklund

Explaining the Structure of FrameNet with Concept Lattices

Abstract

This paper reports on ongoing work to use Formal Concept Analysis as an auxiliary tool in understanding and visualising the wealth of data produced by lexical-resource building as embodied in the construction of FrameNet, a database to capture the syntax and semantics of language use in Frame Linguistics. We present proof of the abundance of concept lattices both in the theory of frames and in its present day incarnation, the FrameNet resource, with contributions that range from data-visualisation to the fine-tuning of some lexico-theoretical concepts better understood in terms of Formal Concept Analysis.

Francisco J. Valverde-Albacete

Lessons Learned in Applying Formal Concept Analysis to Reverse Engineering

Abstract

A key difficulty in the maintenance and evolution of complex software systems is to recognize and understand the implicit dependencies that define contracts that must be respected by changes to the software. Formal Concept Analysis is a well-established technique for identifying groups of elements with common sets of properties. We have successfully applied FCA to complex software systems in order to automatically discover a variety of different kinds of implicit, recurring sets of dependencies amongst design artifacts. In this paper we describe our approach, outline three case studies, and draw various lessons from our experiences. In particular, we discuss how our approach is applied iteratively in order to draw the maximum benefit offered by FCA.

Gabriela Arévalo, Stéphane Ducasse, Oscar Nierstrasz

Navigation Spaces for the Conceptual Analysis of Software Structure

Abstract

Information technology of today is often concerned with information that is not only large in quantity but also complex in structure. Understanding this structure is important in many domains – many quantitative approaches such as data mining have been proposed to address this issue. This paper presents a conceptual approach based on Formal Concept Analysis. Using software source code as an example of a complex structure we present a framework for conceptually analysing relational structures. In our framework, a browsable space of sub-contexts is automatically derived from a database of relations augmented by a rule engine and schema information. Operations are provided for the user to navigate between sub-contexts. We demonstrate how the use of these operations can lead to quick identification of an area of software source code that establishes an unecessary dependency between software parts.

Richard Cole, Peter Becker

Restructuring Help Systems Using Formal Concept Analysis

Abstract

This paper extends standard help system technology to demonstrate the suitability of Formal Concept Analysis in displaying, searching and navigating help content. The paper introduces a method for building suitable scales directly from the help system index by computing a keyword extension set. The keyword extension technique is generalisable in any document collection where a hand-crafted index of terms is available.

Peter Eklund, Bastian Wormuth

An Application of FCA to the Analysis of Aeronautical Incidents

Abstract

This paper illustrates how a new clustering process dedicated to the analysis of anecdotal reports of aviation incidents has been designed and tested thanks to an FCA tool called Kontex. Special attention has been given to the necessary transcription of the data from the initial relational database to an FCA context. The graphical interface for Kontex, which has been specially implemented for this study, is also presented.

The study presented in this paper validates the process adopted and highlights the use of FCA to help the expert to mine the database without previous knowledge of the searched concepts. The work brought original ideas to the aviation safety community by the development of an incident model and the notion of scenario. For the FCA community, one interesting aspect of this work lies on the use of a first-order context (given by a relational database) and its translation into a classical context.

Nicolas Maille, Irving C. Statler, Laurent Chaudron

Characterization and Armstrong Relations for Degenerate Multivalued Dependencies Using Formal Concept Analysis

Abstract

Functional dependencies, a notion originated in Relational Database Theory, are known to admit interesting characterizations in terms of Formal Concept Analysis. In database terms, two successive, natural extensions of the notion of functional dependency are the so-called degenerate multivalued dependencies, and multivalued dependencies proper. We propose here a new Galois connection, based on any given relation, which gives rise to a formal concept lattice corresponding precisely to the degenerate multivalued dependencies that hold in the relation given. The general form of the construction departs significantly from the most usual way of handling functional dependencies. Then, we extend our approach so as to extract Armstrong relations for the degenerate multivalued dependencies from the concept lattice obtained; the proof of the correctness of this construction is nontrivial.

Jaume Baixeries, José Luis Balcázar

Formal Concept Analysis Constrained by Attribute-Dependency Formulas

Abstract

An important topic in formal concept analysis is to cope with a possibly large number of formal concepts extracted from formal context (input data). We propose a method to reduce the number of extracted formal concepts by means of constraints expressed by particular formulas (attribute-dependency formulas, ADF). ADF represent a form of dependencies specified by a user expressing relative importance of attributes. ADF are considered as additional input accompanying the formal context 〈X, Y, I〉. The reduction consists in considering formal concepts which are compatible with a given set of ADF and leaving out noncompatible concepts. We present basic properties related to ADF, an algorithm for generating the reduced set of formal concepts, and demonstrating examples.

Radim Bělohlávek, Vladimír Sklenář

On Computing the Minimal Generator Family for Concept Lattices and Icebergs

Abstract

Minimal generators (or mingen) constitute a remarkable part of the closure space landscape since they are the antipodes of the closures, i.e., minimal sets in the underlying equivalence relation over the powerset of the ground set. As such, they appear in both theoretical and practical problem settings related to closures that stem from fields as diverging as graph theory, database design and data mining. In FCA, though, they have been almost ignored, a fact that has motivated our long-term study of the underlying structures under different perspectives. This paper is a two-fold contribution to the study of mingen families associated to a context or, equivalently, a closure space. On the one hand, it sheds light on the evolution of the family upon increases in the context attribute set (e.g., for purposes of interactive data exploration). On the other hand, it proposes a novel method for computing the mingen family that, although based on incremental lattice construction, is intended to be run in a batch mode. Theoretical and empirical evidence witnessing the potential of our approach is provided.

Kamal Nehmé, Petko Valtchev, Mohamed H. Rouane, Robert Godin

Efficiently Computing a Linear Extension of the Sub-hierarchy of a Concept Lattice

Abstract

Galois sub-hierarchies have been introduced as an interesting polynomial-size sub-order of a concept lattice, with useful applications. We present an algorithm which, given a context, efficiently computes an ordered partition which corresponds to a linear extension of this sub-hierarchy.

Anne Berry, Marianne Huchard, Ross M. McConnell, Alain Sigayret, Jeremy P. Spinrad

A Generic Algorithm for Generating Closed Sets of a Binary Relation

Abstract

In this paper we propose a “divide and conquer” based generating algorithm for closed sets of a binary relation. We show that some existing algorithms are particular instances of our algorithm. This allows us to compare those algorithms and exhibit that the practical efficiency relies on the number of invalid closed sets generated. This number strongly depends on a choice function and the structure of the lattice. We exhibit a class of lattices for which no invalid closed sets are generated and thus reduce time complexity for such lattices. We made several tests which illustrate the impact of the choice function in practical efficiency.

Alain Gély

Uncovering and Reducing Hidden Combinatorics in Guigues-Duquenne Bases

Abstract

Mannila and Räihä [5] have shown that minimum implicational bases can have an exponential number of implications. Aim of our paper is to understand how and why this combinatorial explosion arises and to propose mechanisms which reduce it.

A. Gély, R. Medina, L. Nourine, Y. Renaud

A Parallel Algorithm for Lattice Construction

Abstract

The construction of the concept lattice of a context is a time consuming process. However, in many practical cases where FCA has proven to provide theoretical strength, e.g., in data mining, the volume of data to analyze is huge. This fact emphasizes the need for efficient lattice manipulations. The processing of large datasets has often been approached with parallel algorithms and some preliminary studies on parallel lattice construction exist in the literature. We propose here a novel divide-and-conquer (D&C) approach that operates by data slicing. In this paper, we present a new parallel algorithm, called DAC-ParaLaX, which borrows its main operating primitives from an existing sequential procedure and integrates them into a multi-process architecture. The algorithm has been implemented using a parallel dialect of the C ++ language and its practical performances have been compared to those of a homologue sequential algorithm.

Jean François Djoufak Kengue, Petko Valtchev, Clémentin Tayou Djamegni

Using Intermediate Representation Systems to Interact with Concept Lattices

Abstract

Automated layout of line diagrams for concept lattices is a hard problem as it requires not only asthetical but also semantic considerations. While many layout approaches have been proposed to produce line diagrams that are perceived as good for many applications, a general approach that suits all applications has not yet been found. Instead of proposing another specific layout approach we propose a framework that allows modelling layout constraints that are not only applied for automated layout, but also during manipulation of the diagram layout.

Peter Becker

Crisply Generated Fuzzy Concepts

Abstract

In formal concept analysis of data with fuzzy attributes, both the extent and the intent of a formal (fuzzy) concept may be fuzzy sets. In this paper we focus on so-called crisply generated formal concepts. A concept \(\langle{A,B}\rangle \in \mathcal{B}(X, Y, I)\) is crisply generated if A = D ^↓ (and so B = D ^↓↑) for some crisp (i.e., ordinary) set D ⊆ Y of attributes (generator). Considering only crisply generated concepts has two practical consequences. First, the number of crisply generated formal concepts is considerably less than the number of all formal fuzzy concepts. Second, since crisply generated concepts may be identified with a (ordinary, not fuzzy) set of attributes (the largest generator), they might be considered “the important ones” among all formal fuzzy concepts. We present basic properties of the set of all crisply generated concepts, an algorithm for listing all crisply generated concepts, a version of the main theorem of concept lattices for crisply generated concepts, and show that crisply generated concepts are just the fixed points of pairs of mappings resembling Galois connections. Furthermore, we show connections to other papers on formal concept analysis of data with fuzzy attributes. Also, we present examples demonstrating the reduction of the number of formal concepts and the speed-up of our algorithm (compared to listing of all formal concepts and testing whether a concept is crisply generated).

Radim Bělohlávek, Vladimír Sklenář, Jiří Zacpal

Triadic Concept Graphs and Their Conceptual Contents

Abstract

Concept graphs

Lars Schoolmann

Alpha Galois Lattices: An Overview

Abstract

What we propose here is to reduce the size of Galois lattices still conserving their formal structure and exhaustivity. For that purpose we use a preliminary partition of the instance set, representing the association of a “type” to each instance. By redefining the notion of extent of a term in order to cope, to a certain degree (denoted as α), with this partition, we define a particular family of Galois lattices denoted as Alpha Galois lattices. We also discuss the related implication rules defined as inclusion of such α-extents and show that Iceberg concept lattices are Alpha Galois lattices where the partition is reduced to one single class.

Véronique Ventos, Henry Soldano

A Finite State Model for On-Line Analytical Processing in Triadic Contexts

Abstract

About ten years ago, triadic contexts were presented by Lehmann and Wille as an extension of Formal Concept Analysis. However, they have rarely been used up to now, which may be due to the rather complex structure of the resulting diagrams. In this paper, we go one step back and discuss how traditional line diagrams of standard (dyadic) concept lattices can be used for exploring and navigating triadic data.

Our approach is inspired by the slice & dice paradigm of On-Line-Analytical Processing (OLAP).We recall the basic ideas of OLAP, and showhowthey may be transferred to triadic contexts. For modeling the navigation patterns a user might follow, we use the formalisms of finite state machines. In order to present the benefits of our model, we show how it can be used for navigating the IT Baseline Protection Manual of the German Federal Office for Information Security.

Gerd Stumme

Complete Subalgebras of Semiconcept Algebras and Protoconcept Algebras

Abstract

In order to define a negation on formal concepts in Formal Concept Analysis, the more general notions of semiconcepts and protoconcepts were introduced. The theory of the resulting protoconcept and semiconcept algebras is developed in Boolean Concept Logic as a part of Contextual Logic. In this paper it is shown that each complete subalgebra of a semiconcept algebra is itself the semiconcept algebra of an appropriate context. An analogous result holds for the complete subalgebras of protoconcept algebras. These contexts can be obtained from the original context through partitions of the object and the attribute set satisfying certain conditions. Characterizations of the complete subalgebras of semiconcept and protoconcept algebras in terms of contexts, in terms of subsets, and through closed subrelations are given.

Björn Vormbrock

Coherence Networks of Concept Lattices: The Basic Theorem

Abstract

For representing different views and their connections, networks of formal contexts are considered which are coded by so-called multicontexts. The coincidences between the network contexts of a multicontext give rise to a coherence network of concept lattices. It is the aim of this paper to state and to prove the Basic Theorem on Coherence Networks of Concept Lattices as an extension of the Basic Theorem on Concept Lattices.

Sascha Karl Dörflein, Rudolf Wille

Turing Machine Representation in Temporal Concept Analysis

Abstract

The purpose of this paper is to investigate the connection between the theory of computation and Temporal Concept Analysis, the temporal branch of Formal Concept Analysis.

The main idea is to represent for each possible input of a given algorithm the uniquely determined sequence of computation steps as a life track of an object in some conceptually described state space. For that purpose we introduce for a given Turing machine a Conceptual Time System with Actual Objects and a Time Relation (CTSOT) which yields the state automaton of a Turing machine as well as its configuration automaton. The conceptual role of the instructions of a Turing machine is understood as a set of background implications of the derived context of a Turing CTSOT.

Karl Erich Wolff, Wendsomde Yameogo

Protoconceptual Contents and Implications

Abstract

The development of a mathematical model for judgments understood as compositions of concepts and relations has been an important branch of research in recent years. It led to the definitions of concept and protoconcept graphs which are based on information contained in a power context family, where incidence relations between objects (or tuples of objects) and attributes are stored.

A theory of the information those graphs represent (called conceptual content) has been developed for concept graphs in [PW99] and [Wi03]. In [HK04], an extension of this theory to protoconcept graphs not considering object implications (as it is done for concept graphs) has been established. The first part of this paper concentrates on the investigation of the protoconceptual content of protoconcept graphs respecting both protoconceptual and object implications.

The second part compares the different structures of conceptual and protoconceptual contents of a given power context family, showing how more background information (using object implications and concepts instead of protoconcepts) reduces the number of possible contents.

The third and final part analyzes how the different approaches can be generalized. Here we will concentrate on the (generalized) conceptual content of a formal context.

In each part an information context will be defined, which provides an accessible representation of the lattice of (proto-)conceptual closures.

Joachim Hereth Correia, Julia Klinger

Planarity of Lattices

An Approach Based on Attribute Additivity

Abstract

Popular lattice drawing algorithms do not take planarity into account and find plane diagrams mainly heuristically. We present a characterization of planar lattices based on a theorem of Dushnik and Miller [4] and the “left”-relation introduced by Kelly and Rival [6]. In particular, our work is helpful for drawing plane attribute additive diagrams.

Christian Zschalig

Bialgebraic Contexts for Distributive Lattices – Revisited

Abstract

In [8], Vogt used so-called bialgebraic contexts to represent the lattice Sub(L) of all sublattices of a finite distributive lattice L as the substructure lattice of an appropriately defined finite (universal) algebra, based on Rival’s description (see [4] and [5]) by means of deleting suitable intervals from L. We show how to extend Vogt’s context in order to obtain a conceptually simpler description of Sub ₀₁(L) – the lattice of all 0-1-preserving sublattices of L – by means of quasiorders and an associated total binary operation on J (L)², the set of all pairs of non-zero join-irreducibles of L. Our approach is based on Birkhoff- resp. Priestley-duality, a standard reference is [1].

Jürg Schmid

Which Concept Lattices Are Pseudocomplemented?

Abstract

We give a contextual characterization of pseudocomplementation by means of the arrow relations.

AMS Subject Classification: 06D15

Bernhard Ganter, Léonard Kwuida

Backmatter