nach oben

2009 | Buch

Kapitel lesen Erstes Kapitel lesen

Formal Concept Analysis

7th International Conference, ICFCA 2009 Darmstadt, Germany, May 21-24, 2009 Proceedings

herausgegeben von: Sébastien Ferré, Sebastian Rudolph

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

The discipline of formal concept analysis (FCA) is concerned with the form- ization of concepts and conceptual thinking. Built on the solid foundation of lattice and order theory, FCA is ?rst and foremost a mathematical discipline. However,its motivation andguiding principles arebasedon strongphilosophical underpinnings. In practice, FCA provides a powerful framework for the qua- tative, formal analysis of data, as demonstrated by numerous applications in diverse areas. Likewise, it emphasizes the aspect of human-centered information processing by employing visualization techniques capable of revealing inherent structure in data in an intuitively graspable way. FCA thereby contributes to structuring and navigating the ever-growing amount of information available in our evolving information society and supports the process of turning data into information and ultimately into knowledge. In response to an expanding FCA community, the International Conference on Formal Concept Analysis (ICFCA) was established to provide an annual opportunity for the exchange of ideas. Previous ICFCA conferences were held in Darmstadt (2003), Sydney (2004), Lens (2005), Dresden (2006), Clermont- Ferrand (2007), as well as Montreal (2008) and are evidence of vivid ongoing interest and activities in FCA theory and applications. ICFCA 2009 took place during May 21–24 at the University of Applied S- ences in Darmstadt. Beyond serving as a host of the very ?rst ICFCA in 2003, Darmstadt can be seen as the birthplace of FCA itself, where this discipline was introduced in the early 1980s and elaborated over the subsequent decades.

Inhaltsverzeichnis

Frontmatter

Invited Talks

Usability Issues in Description Logic Knowledge Base Completion

Abstract

In a previous paper, we have introduced an approach for extending both the terminological and the assertional part of a Description Logic knowledge base by using information provided by the assertional part and by a domain expert. This approach, called knowledge base completion, was based on an extension of attribute exploration to the case of partial contexts. The present paper recalls this approach, and then addresses usability issues that came up during first experiments with a preliminary implementation of the completion algorithm. It turns out that these issues can be addressed by extending the exploration algorithm for partial contexts such that it can deal with implicational background knowledge.

Franz Baader, Barış Sertkaya

Concept Lattice Orbifolds – First Steps

Abstract

Concept lattices with symmetries may be simplified by “folding” them along the orbits of their automorphism group. The resulting diagram is often more intuitive than the full lattice diagram, but well defined annotations are required to make the folded diagram as informative as the original one. The folding procedure can be extended to formal contexts.

A typical situation where such lattice foldings are useful is when hierarchies of structures are considered “up to isomorphisms”.

Daniel Borchmann, Bernhard Ganter

The Advent of Formal Diagrammatic Reasoning Systems

Abstract

In knowledge representation and reasoning systems, diagrams have many practical applications and are used in numerous settings. Indeed, it is widely accepted that diagrams are a valuable aid to intuition and help to convey ideas and information in a clear way. On the other side, logicians have viewed diagrams as informal tools, but which cannot be used in the manner of formal argumentation. Instead, logicians focused on symbolic representations of logics. Recently, this perception was overturned in the mid 1990s, first with seminal work by Shin on an extended version of Venn diagrams. Since then, certainly a growth in the research field of formal reasoning with diagrams can be witnessed. This paper discusses the evolution of formal diagrammatic logics, focusing on those systems which are based on Euler and Venn-Peirce diagrams, and Peirces existential graphs. Also discussed are some challenges faced in the area, some of which are specifically related to diagrams.

Frithjof Dau

The Logic of Learning

Abstract

I use the term logical and relational learning (LRL) to refer to the subfield of machine learning and data mining that is concerned with learning in expressive logical or relational representations. It is the union of inductive logic programming, (statistical) relational learning and multi-relational data mining and constitutes a general class of techniques and methodology for learning from structured data (such as graphs, networks, relational databases) and background knowledge. During the course of its existence, logical and relational learning has changed dramatically. Whereas early work was mainly concerned with logical issues (and even program synthesis from examples), in the 90s its focus was on the discovery of new and interpretable knowledge from structured data, often in the form of rules or patterns. Since then the range of tasks to which logical and relational learning has been applied has significantly broadened and now covers almost all machine learning problems and settings. Today, there exist logical and relational learning methods for reinforcement learning, statistical learning, distance- and kernel-based learning in addition to traditional symbolic machine learning approaches. At the same time, logical and relational learning problems are appearing everywhere. Advances in intelligent systems are enabling the generation of high-level symbolic and structured data in a wide variety of domains, including the semantic web, robotics, vision, social networks, and the life sciences, which in turn raises new challenges and opportunities for logical and relational learning.

In this talk, I will start by providing a gentle introduction to the field of logical and relational learning and then continue with an overview of the logical foundations for learning, which are concerned with various settings for learning (such as learning from entailment, from interpretations and from proofs), with the logical inference rules and generality relationships used, and the effects they have on the properties of the search-space. More details can be found in

Luc De Raedt. Logical and Relational Learning. Springer. 2008.

Luc De Raedt

What Can Formal Concept Analysis Do for Data Warehouses?

Abstract

Formal concept analysis (FCA) has been successfully used in several Computer Science fields such as databases, software engineering, and information retrieval, and in many domains like medicine, psychology, linguistics and ecology. In data warehouses, users exploit data hypercubes (i.e., multi-way tables) mainly through online analytical processing (OLAP) techniques to extract useful information from data for decision support purposes.

Many topics have attracted researchers in the area of data warehousing: data warehouse design and multidimensional modeling, efficient cube materialization (pre-computation), physical data organization, query optimization and approximation, discovery-driven data exploration as well as cube compression and mining. Recently, there has been an increasing interest to apply or adapt data mining approaches and advanced statistical analysis techniques for extracting knowledge (e.g., outliers, clusters, rules, closed n-sets) from multidimensional data. Such approaches or techniques cover (but are not limited to) FCA, cluster analysis, principal component analysis, log-linear modeling, and non-negative multi-way array factorization. Since data cubes are generally large and highly dimensional, and since cells contain consolidated (e.g., mean value), multidimensional and temporal data, such facts lead to challenging research issues in mining data cubes. In this presentation, we will give an overview of related work and show how FCA theory (with possible extensions) can be used to extract valuable and actionable knowledge from data warehouses.

Rokia Missaoui, Léonard Kwuida

Time and Logic: A.N. Prior’s Formal Analysis of Temporal Concepts

Abstract

This paper deals with A.N. Prior’s analysis of the concepts of dynamic and static time, i.e., McTaggart’s so-called A- and B-concepts. The relations and mutual dependencies between these temporal concepts are investigated, and Prior’s response to McTaggart’s views is discussed. Furthermore, Prior’s notion of branching time is analysed. It is argued that Prior can be criticized for identifying ‘plain future’ with ‘necessary future’. Finally, Prior’s four grades of tense-logical involvement are introduced and discussed. It is argued that the third grade is the most attractive from a philosophical point of view.

Peter Øhrstrøm

Can Ontology Inform Ontologies?

Abstract

Traditionally, since it was coined in the early 17^th century by German school philosophy, the word “ontology” has been used to name a field of metaphysics as well as distinct metaphysical doctrines. Since the 1990s, the word “ontology” appears increasingly in information sciences, and likewise in fields that have been subjected to ‘informatisation’ such as biology, geography, and medicine. In all these fields, however, the word “ontology” is being used with different meanings, and for the most part with meanings that are distant from its philosophical roots.

Boris Wyssusek

Theory

Factor Analysis of Incidence Data via Novel Decomposition of Matrices

Abstract

Matrix decomposition methods provide representations of an object-variable data matrix by a product of two different matrices, one describing relationship between objects and hidden variables or factors, and the other describing relationship between the factors and the original variables. We present a novel approach to decomposition and factor analysis of matrices with incidence data. The matrix entries are grades to which objects represented by rows satisfy attributes represented by columns, e.g. grades to which an image is red or a person performs well in a test. We assume that the grades belong to a scale bounded by 0 and 1 which is equipped with certain aggregation operators and forms a complete residuated lattice. We present an approximation algorithm for the problem of decomposition of such matrices with grades into products of two matrices with grades with the number of factors as small as possible. Decomposition of binary matrices into Boolean products of binary matrices is a special case of this problem in which 0 and 1 are the only grades. Our algorithm is based on a geometric insight provided by a theorem identifying particular rectangular-shaped submatrices as optimal factors for the decompositions. These factors correspond to formal concepts of the input data and allow for an easy interpretation of the decomposition. We present the problem formulation, basic geometric insight, algorithm, illustrative example, experimental evaluation.

Radim Belohlavek, Vilem Vychodil

A Unified Hierarchy for Functional Dependencies, Conditional Functional Dependencies and Association Rules

Abstract

Conditional Functional Dependencies (CFDs) are Functional Dependencies (FDs) that hold on a fragment relation of the original relation. In this paper, we show the hierarchy between FDs, CFDs and Association Rules (ARs): FDs are the union of CFDs while CFDs are the union of ARs. We also show the link between Approximate Functional Dependencies (AFDs) and approximate ARs. In this paper, we show that all those dependencies are indeed structurally the same and can be unified into a single hierarchy of dependencies. A benefit of this hierarchy is that existing algorithms which discover ARs could be adapted to discover any kind of dependencies and, moreover, generate a reduced set of dependencies. We also establish the link between the problem of finding equivalent pattern tableaux of a CFD and the problem of finding keys of a relation.

Raoul Medina, Lhouari Nourine

Robust Elements in Rough Set Abstractions

Abstract

In [3] the classical rough set approach was generalized in the manner that lower and upper approximations were replaced by arbitrary kernel and closure operators respectively. Furthermore, the resulting lattices of rough set abstractions were described as P-products. This approach, though promising, needs additional research to become part of a unifying theory of Rough Set Theory and Formal Concept Analysis. For example, the role of robust elements and the possible existence of suitable negation operators were not addressed. We present results in these directions and on the structure of these lattices.

Christian Meschke

Some Computational Problems Related to Pseudo-intents

Abstract

We investigate the computational complexity of several decision, enumeration and counting problems related to pseudo-intents. We show that given a formal context and a subset of its set of pseudo-intents, checking whether this context has an additional pseudo-intent is in conp, and it is at least as hard as checking whether a given simple hypergraph is not saturated. We also show that recognizing the set of pseudo-intents is also in conp, and it is at least as hard as identifying the minimal transversals of a given hypergraph. Moreover, we show that if any of these two problems turns out to be conp-hard, then unless p = np, pseudo-intents cannot be enumerated in output polynomial time. We also investigate the complexity of finding subsets of a given Duquenne-Guigues Base from which a given implication follows. We show that checking the existence of such a subset within a specified cardinality bound is np-complete, and counting all such minimal subsets is #p-complete.

Barış Sertkaya

Algorithms

Exploring Finite Models in the Description Logic ${\mathcal {EL}}_{\rm gfp}$

Abstract

In a previous ICFCA paper we have shown that, in the Description Logics $\mathcal {EL}$ and ${\mathcal {EL}}_{\rm gfp}$, the set of general concept inclusions holding in a finite model always has a finite basis. In this paper, we address the problem of how to compute this basis efficiently, by adapting methods from formal concept analysis.

Franz Baader, Felix Distel

Yet a Faster Algorithm for Building the Hasse Diagram of a Concept Lattice

Abstract

Formal concept analysis (FCA) is increasingly applied to data mining problems, essentially as a formal framework for mining reduced representations (bases) of target pattern families. Yet most of the FCA-based miners, closed pattern miners, would only extract the patterns themselves out of a dataset, whereas the generality order among patterns would be required for many bases. As a contribution to the topic of the (precedence) order computation on top of the set of closed patterns, we present a novel method that borrows its overall incremental approach from two algorithms in the literature. The claimed innovation consists of splitting the update of the precedence links into a large number of lower-cover list computations (as opposed to a single upper-cover list computation) that unfold simultaneously. The resulting method shows a good improvement with respect to its counterpart both on its theoretical complexity and on its practical performance. It is therefore a good starting point for the design of efficient and scalable precedence miners.

Jaume Baixeries, Laszlo Szathmary, Petko Valtchev, Robert Godin

Context Graphs — Representing Formal Concepts by Connected Subgraphs

Abstract

The article introduces a representation of a formal context by an undirected graph called a context graph with the formal objects being the nodes of the graph. We use as a defining property for this graph that it contains every concept extent as a connected subgraph. The graph is not uniquely defined by this property — we focus on those graphs that are edge-minimal and present a result with respect to the number of their edges. We then study how the structure of an edge-minimal context graph can be updated to adjust to the subsequent addition of an object to the context. This leads to an incremental construction algorithm that does not require the explicit computation of formal concepts.

Jens Kötters, Heinz Schmidt, David McG. Squire

Handling Large Formal Context Using BDD – Perspectives and Limitations

Abstract

This paper presents Binary Decision Diagrams (BDDs) applied to Formal Concept Analysis (FCA). The aim is to increase the FCA capability to handle large formal contexts. The main idea is to represent formal context using BDDs for later extraction of the set of all formal concepts from this implicit representation. BDDs have been evaluated based on several types of randomly generated synthetic contexts and on density variations in two distinct occasions: (1) computational resources required to build the formal contexts in BDD; and (2) to extract all concepts from it. Although BDDs have had fewer advantages in terms of memory consumption for representing formal contexts, it has true potential when all concepts are extracted. In this work, it is shown that BDDs could be used to deal with large formal contexts especially when those have few attributes and many objects. To overcome the limitations of having contexts with fewer attributes, one could consider vertical partitions of the context to be used with distributed FCA algorithms based on BDDs.

Andrei Rimsa, Luis E. Zárate, Mark A. J. Song

Applications

A Novel Approach to Cell Formation

Abstract

We present an approach to the cell formation problem, known from group technology, which is inspired by formal concept analysis. The cell formation problem consists in allocating parts (objects) to machines (attributes), based on the machine-part matrix. This can be viewed as forming groups consisting of a set of parts and a set of machines. Such groups resemble formal concepts in the input data. Due to the specific nature of the performance assessment in the cell formation problem, good groups can be thought of as rectangles which, unlike those corresponding to formal concepts, contain a few blanks, i.e. which are not full of crosses in terms of formal concept analysis. Moreover, such groups need to be disjoint both in terms of objects and attributes. In this paper, we present an algorithm for the cell formation problem, experimental results, and a comparison to some methods proposed in the literature.

Radim Belohlavek, Niranjan Kulkarni, Vilem Vychodil

Identifying Ecological Traits: A Concrete FCA-Based Approach

Abstract

This paper describes a method to identify so-called ecological traits of species based on the analysis of their biological characteristics. This biological dataset has a complex structure that can be formalized as a fuzzy many-valued context and transformed into a binary context through histogram scaling. The core of the method relied on the construction and interpretation of formal concepts and was used on a 50 species × 124 histogram attributes table. The concepts were analyzed with the help of an hydrobiologist, leading to a set of ecological traits which were inserted in the original context for validation.

Aurélie Bertaux, Florence Le Ber, Agnès Braud, Michèle Trémolières

A Concept Lattice-Based Kernel for SVM Text Classification

Abstract

Standard Support Vector Machines (SVM) text classification relies on bag-of-words kernel to express the similarity between documents. We show that a document lattice can be used to define a valid kernel function that takes into account the relations between different terms. Such a kernel is based on the notion of conceptual proximity between pairs of terms, as encoded in the document lattice. We describe a method to perform SVM text classification with concept lattice-based kernel, which consists of text pre-processing, feature selection, lattice construction, computation of pairwise term similarity and kernel matrix, and SVM classification in the transformed feature space. We tested the accuracy of the proposed method on the 20NewsGroup database: the results show an improvement over the standard SVM when very little training data are available.

Claudio Carpineto, Carla Michini, Raffaele Nicolussi

Two FCA-Based Methods for Mining Gene Expression Data

Abstract

Gene expression data are numerical and describe the level of expression of genes in different situations, thus featuring behaviour of the genes. Two methods based on FCA (Formal Concept Analysis) are considered for clustering gene expression data. The first one is based on interordinal scaling and can be realized using standard FCA algorithms. The second method is based on pattern structures and needs adaptations of standard algorithms to computing with interval algebra. The two methods are described in details and discussed. The second method is shown to be more computationally efficient and providing more readable results. Experiments with gene expression data are discussed.

Mehdi Kaytoue, Sébastien Duplessis, Sergei O. Kuznetsov, Amedeo Napoli

Ontology-Based Formal Concept Differences Analysis in Radiology Report Impact by the Adoption of PACS

Abstract

Following the advent of information technology and the rapid growth of its application in the medical field, the picture archiving and communication system (PACS) became very popular in mid- to large-scale hospitals. This study aimed to compare the concept lattice of radiology report content before and after the adoption of PACS. This study proposes a formal concept analysis process to produce different levels of ontological concepts from the radiology report. Ontology concept lattice diagrams are presented along with the correlation of concepts and their corresponding significance. The conceptual clustering method is applied to obtain a reasonable number of concepts. To find differences, the structure of ontology is compared in different phases by using a distance measurement. The study results showed a delicate change in radiology report terms before and after the adoption of the system. Given the quantitative analysis results, a qualitative-focused ethnography will be further conducted with several radiologists.

Telung Pan, Kwoting Fang

Revisiting the Potentialities of a Mechanical Thesaurus

Abstract

This paper revisits the lattice-based thesaurus models which Margaret Masterman used for machine translation in the 1950’s and 60’s. Masterman’s notions are mapped onto modern, Formal Concept Analysis (FCA) terminology and three of her thesaurus algorithms are formalised with FCA methods. The impact of the historical and social situatedness of Roget’s Thesaurus on such algorithms is considered. The paper concludes by discussing connections between Masterman’s research and modern research.

Uta Priss, L. John Old

FCA-Based Two Dimensional Pattern Matching

Abstract

We propose a concept lattice-based approach to multiple two dimensional pattern matching problems. It is assumed that a pattern can be described as a set of vertices (or pixels) and that a small set of vertices around each vertex corresponds to an attribute in a concept lattice. Typically, an attribute should be a succinct characterisation of domain-dependent relevant information about the neighbourhood of the vertex. The set of objects in the lattice is the set of 2D patterns to be matched. Searching in the 2D image is carried out in reference to the intents of lattice concepts. Thus, by searching a small region of the text, one can efficiently identify which sets of pattern objects may potentially be found in a larger environment of that region. As experimental data, we use 2D images derived from microchip design layouts and 2D matching patterns derived from microchip design rules.

Fritz Venter, Derrick G. Kourie, Bruce W. Watson

History

RESTRUCTURING LATTICE THEORY: AN APPROACH BASED ON HIERARCHIES OF CONCEPTS

Abstract

Lattice theory today reflects the general Status of current mathematics: there is a rich production of theoretical concepts, results, and developments, many of which are reached by elaborate mental gymnastics; on the other hand, the connections of the theory to its surroundings are getting weaker and weaker, with the result that the theory and even many of its parts become more isolated. Restructuring lattice theory is an attempt to reinvigorate connections with our general culture by interpreting the theory as concretely as possible, and in this way to promote better communication between lattice theorists and potential users of lattice theory.

Rudolf Wille

Backmatter

Titel: Formal Concept Analysis
herausgegeben von: Sébastien Ferré
Sebastian Rudolph
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-01815-2
Print ISBN: 978-3-642-01814-5
DOI: https://doi.org/10.1007/978-3-642-01815-2