Skip to main content
main-content

Über dieses Buch

This book constitutes the refereed proceedings of the 12th International Conference on Formal Concept Analysis, ICFCA 2014, held in Cluj-Napoca, Romania, in June 2014. The 16 regular papers presented together with 3 invited talks were carefully reviewed and selected from 39 submissions. The papers in this volume cover a rich range of FCA aspects, such as theory, enhanced FCA. Knowledge discovery and knowledge spaces, as well as methods and applications. In addition the book contains a reprint of the first publication "Sub direct decomposition of concept lattices" by Rudolf Wille.

Inhaltsverzeichnis

Frontmatter

Invited Talks

Learning Spaces, and How to Build Them

In Knowledge Space Theory (KST), a knowledge structure encodes a body of information as a domain, consisting of all the relevant pieces of information, together with the collection of all possible states of knowledge, identified with specific subsets of the domain. Knowledge spaces and learning spaces are defined through pedagogically natural requirements on the collection of all states. We explain here several ways of building in practice such structures on a given domain. In passing we point out some connections linking KST with Formal Concept Analysis (FCA).
Jean-Paul Doignon

On the Succinctness of Closure Operator Representations

It is widely known that closure operators on finite sets can be represented by sets of implications (also known as inclusion dependencies) as well as by formal contexts. In this paper, we consider these two representation types, as well as generalizations of them: extended implications and context families. We discuss the mutual succinctness of these four representations and the tractability of certain operations used to modify closure operators.
Sebastian Rudolph

MDL in Pattern Mining A Brief Introduction to Krimp

In this short paper we sketch a brief introduction to our Krimp algorithm. Moreover, we briefly discuss some of the large body of follow up research. Pointers to the relevant papers are provided in the bibliography.
Arno Siebes

Theory

Upper Bound for the Number of Concepts of Contranominal-Scale Free Contexts

We show an improvement of Prisner’s upper bound for the number of concepts of a formal context. The improvement factor is of the order ( max {|G|,|M|}) c , where c is the size of the biggest contranominal scale that can be found as a subcontext. We also prove that the c ∈ O(1) condition is necessary to establish that an arbitrary sequence of contexts has a polynomial number of concepts, by constructing a lower bound. Complexity aspects of calculating c are discussed.
Alexandre Albano

Algebraicity and the Tensor Product of Concept Lattices

In this paper we prove that the tensor product of complete lattices, as it is defined in formal concept analysis, preserves algebraicity. The proof of this fact is based on the compactness of propositional logic. We use this property to show that the box product of (0, ∨ )-semilattices, introduced by G.Grätzer and F.Wehrung in 1999, can be obtained from the tensor product of concept lattices in a manner similar to how it is done in the definition of tensor product in “general” lattice theory.
Bogdan Chornomaz

On the Existence of Isotone Galois Connections between Preorders

Given a mapping f : A → B from a preordered set A into an unstructured set B, we study the problem of defining a suitable preordering relation on B such that there exists a mapping g : B → A such that the pair (f,g) forms an adjunction between preordered sets.
Francisca García-Pardo, Inma P. Cabrera, Pablo Cordero, Manuel Ojeda-Aciego, Francisco J. Rodríguez-Sanchez

Directed Tree Decompositions

In the problem session of the ICFCA 2006, Sándor Radeleczki asked for the meaning of the smallest integer k such that a given poset can be decomposed as the union of k directed trees. The problem also asks for the connection of this number to the order dimension. Since it was left open what kind of decomposition might be used, there is more than one reading of this problem. In the paper, we discuss different versions and give some answers to this open problem.
Sebastian Kerkhoff, Friedrich Martin Schneider

Enhanced FCA

A Proposition for Combining Pattern Structures and Relational Concept Analysis

In this paper we propose an adaptation of the RCA process enabling the relational scaling of pattern structures. In a nutshell, this adaptation allows the scenario where RCA needs to be applied in a relational context family composed by pattern structures instead of formal contexts. To achieve this we define the heterogeneous pattern structures as a model to describe objects in a combination of spaces, namely the original object description space and the set of relational attributes derived from the RCA scaling process. We frame our approach in the problem of characterizing latent variables (LV) in a latent variable model of documents and terms. LVs are used as compact and improved dataset representations. We approach the problem of LV characterization missing from the original LV-model, through the application of the adapted RCA process using pattern structures. Finally, we discuss the implications of our proposition.
Víctor Codocedo, Amedeo Napoli

RCA as a Data Transforming Method: A Comparison with Propositionalisation

This paper aims at comparing transformation-based approaches built to deal with relational data, and in particular two approaches which have emerged in two different communities: Relational Concept Analysis (RCA), based on an iterative use of the classical Formal Concept Analysis (FCA) approach, and Propositionalisation coming from the Inductive Logic Programming community. Both approaches work by transforming a complex problem into a simpler one, namely transforming a database consisting of several tables into a single table. For this purpose, a main table is chosen and new attributes capturing the information from the other tables are built and added to this table. We show the similarities between those transformations for what concerns the principles underlying them, the semantics of the built attributes and the result of a classification performed by FCA on the enriched table. This is illustrated on a simple dataset and we also present a synthetic comparison based on a larger dataset from the hydrological domain.
Xavier Dolques, Kartick Chandra Mondal, Agnés Braud, Marianne Huchard, Florence Le Ber

Ordinal Factor Analysis of Graded Data

In the last few years, concept factor analysis has been an object of study in the FCA community. Its main idea is to use formal concepts as factors to explain the data in a more concise way. We study factorisation of graded tabular data by means of well-structured families of concepts which have an ordinal character. This method enables us to obtain a smaller number of items which explain the data while they still have a clear and comprehensible meaning. We illustrate the method and its applicability on a sports data set.
Cynthia Vera Glodeanu, Jan Konecny

Knowledge Discovery and Knowledge Spaces

On Knowledge Spaces and Item Testing

First, we briefly introduce some of the fundamental notions of knowledge space theory and how they relate to formal concept analysis. Knowledge space theory has a probabilistic extension which allows it to be utilized in order to assess knowledge states by looking at responses to a variety of test items, which are designed to demand performing different sets of cognitive operations. Second, we introduce an easy extension to lambda calculus in order to incorporate extra-logical operations. Further we define a weight function on term reductions, which is to be used as a model to calculate item response probabilities for test items after task analysis. We use the new model in order to review the probabilistic extension of knowledge space theory.
Immanuel Albrecht, Hermann Körndle

Scalable Estimates of Concept Stability

Data mining aims at finding interesting patterns from datasets, where “interesting” means reflecting intrinsic dependencies in the domain of interest rather than just in the dataset. Concept stability is a popular relevancy measure in FCA. Experimental results of this paper show that high stability of a concept for a context derived from the general population suggests that concepts with the same intent in other samples drawn from the population have also high stability. A new estimate of stability is introduced and studied. It is experimentally shown that the introduced estimate gives a better approximation than the Monte Carlo approach introduced earlier.
Aleksey Buzmakov, Sergei O. Kuznetsov, Amedeo Napoli

Factors and Skills

Inspired by Knowledge and Learning Spaces, we present a novel framework for explaining the answering patterns of learners through competences and skills. More precisely, we investigate how a given learner-question data may be ascribed by a set of competences such that a learner masters a question if and only if they have a competence that is sufficient for mastering the question. Each competence is some combination of skills, but there may be restrictions on which skills can be combined. In general a question does not require a unique competence.
Bernhard Ganter, Cynthia Vera Glodeanu

Automatized Construction of Implicative Theory of Algebraic Identities of Size Up to 5

Automation of constructing dependencies between algebraic identities of size up to 5 is investigated. For this purpose a robust active learning technique called Attribute Exploration is used. The technique collects algebra–identity pairs from an expert and builds a concise representation of implicative dependencies (implicative theory) between the identities. It is not possible to accomplish the construction of the implicative theory using only finite algebras and due to this fact heuristics and an algorithm for finding appropriate algebras over an infinite universe are introduced. This allowed for accomplishing the constructing and proving all the obtained implications.
Artem Revenko

Closed Patterns and Abstraction Beyond Lattices

Recently pattern mining has investigated closure operators in families of subsets of an attribute set that are not lattices. In particular, various authors have investigated closure operators starting from a context, in the Formal Concept Analysis (FCA) sense, in which objects are described as usual according to their relation to attributes, and in which a closed element is a maximal element of the equivalence class of elements sharing the same support, i.e. occurring in the same objects. The purpose of this paper is twofold. First we thoroughly investigate this framework and relate it to FCA, defining in particular a structure called a pre-confluence, weaker than a lattice, in which we can define a closure operator with respect to a set of objects. Second, we show that the requirements allowing us to define abstract concept lattices also allow us to define corresponding abstract Galois pre-confluences.
Henry Soldano

Methods and Applications

Mining Videos from the Web for Electronic Textbooks

We propose a system for mining videos from the web for supplementing the content of electronic textbooks in order to enhance their utility. Textbooks are generally organized into sections such that each section explains very few concepts and every concept is primarily explained in one section. Building upon these principles from the education literature and drawing upon the theory of Formal Concept Analysis, we define the focus of a section in terms of a few indicia, which themselves are combinations of concept phrases uniquely present in the section. We identify videos relevant for a section by ensuring that at least one of the indicia for the section is present in the video and measuring the extent to which the video contains the concept phrases occurring in different indicia for the section. Our user study employing two corpora of textbooks on different subjects from two countries demonstrate that our system is able to find useful videos, relevant to individual sections.
Rakesh Agrawal, Maria Christoforaki, Sreenivas Gollapudi, Anitha Kannan, Krishnaram Kenthapadi, Adith Swaminathan

Automated Enzyme Classification by Formal Concept Analysis

Enzymes are macro-molecules (linear sequences of linked molecules) with a catalytic activity that make them essential for any biochemical reaction. High throughput genomic techniques give access to the sequence of new enzymes found in living organisms. Guessing the enzyme’s functional activity from its sequence is a crucial task that can be approached by comparing the new sequences with those of already known enzymes labeled by a family class. This task is difficult because the activity is based on a combination of small sequence patterns and sequences greatly evolved over time. This paper presents a classifier based on the identification of common subsequence blocks between known and new enzymes and the search of formal concepts built on the cross product of blocks and sequences for each class. Since new enzyme families may emerge, it is important to propose a first classification of enzymes that cannot be assigned to a known family. FCA offers a nice framework to set the task as an optimization problem on the set of concepts. The classifier has been tested with success on a particular set of enzymes present in a large variety of species, the haloacid dehalogenase superfamily.
François Coste, Gaëlle Garet, Agnès Groisillier, Jacques Nicolas, Thierry Tonon

Multilayered, Blocked Formal Concept Analyses for Adaptive Image Compression

Formal Concept Analysis (FCA) decomposes a matrix into a set of sparse matrices capturing its underlying structure. A similar task for real-valued data, transform coding, arises in image compression. Existing cosine transform coding for JPEG image compression uses a fixed, decorrelating transform; however, compression is limited as images rarely consist of pure cosines. The question remains whether an FCA adaptive transform can be applied to image compression. We propose a multi-layer FCA (MFCA) adaptive ordered transform and Sequentially Sifted Linear Programming (SSLP) encoding pair for adaptive image compression. Our hypothesis is that MFCA’s sparse linear codes (closures) for natural scenes, are a complete family of ordered, localized, oriented, bandpass receptive fields, predicted by models of the primary visual cortex. Results on real data demonstrate that adaptive compression is feasible. These initial results may play a role in improving compression rates and extending the applicability of FCA to real-valued data.
Ruairí de Fréin

Attribute Exploration with Proper Premises and Incomplete Knowledge Applied to the Free Radical Theory of Ageing

The classical free radical theory of ageing assumes that oxidative damage by reactive oxygen species (ROS) accumulates with age in a self-enhancing process. The theory has been confirmed by many experiments in various species. However, it is seriously challenged since several years. In this ambiguous situation, we collected and ordered existing knowledge, with a focus on the integration of conflicting findings.
We developed a specific method of knowledge base construction and give a first example of its application. Data reported in literature or generated by our experimental partners is formalized as Ripple Down Rules (RDR), a structure of general rules and exceptions. This rule set is validated and completed by the attribute exploration algorithm: Several, most specific RDR are accepted as background implications for an exploration starting from the examples collected during the RDR knowledge base growth.
The RDR classify biological cases, which are defined by attributes like organism, cell type or stimulation experiment. The classes are different and chosen according to leading questions. We focus on low/high ROS concentration in age and on lifespan. Implications with proper premises are suited for such disjoint basic sets of premises and conclusions. We implemented an easily understandable exploration algorithm in conexp-clj, furthermore an extension of this algorithm to incomplete counterexamples. The correctness and completeness of both algorithms is proven.
Johannes Wollbold, Rüdiger Köhling, Daniel Borchmann

History

Subdirect Decomposition of Concept Lattices

In [1], G.Birkhoff exhibited the subdirect product of algebraic structures as a universal tool, which since has been extensively used in the study of algebraic theories. Although a subdirect product is not uniquely determined by its factors, there are useful construction methods based on subdirect products (cf. Wille [8], [9], [10]). The aim of this paper is to make these methods available for handling the “Determination Problem” of concept lattices as it is exposed in Wille [11]. In particular, a useful method for determining concept lattices via its scaffoldings will be developed under some finiteness condition.
Rudolf Wille

Backmatter

Weitere Informationen

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Globales Erdungssystem in urbanen Kabelnetzen

Bedingt durch die Altersstruktur vieler Kabelverteilnetze mit der damit verbundenen verminderten Isolationsfestigkeit oder durch fortschreitenden Kabelausbau ist es immer häufiger erforderlich, anstelle der Resonanz-Sternpunktserdung alternative Konzepte für die Sternpunktsbehandlung umzusetzen. Die damit verbundenen Fehlerortungskonzepte bzw. die Erhöhung der Restströme im Erdschlussfall führen jedoch aufgrund der hohen Fehlerströme zu neuen Anforderungen an die Erdungs- und Fehlerstromrückleitungs-Systeme. Lesen Sie hier über die Auswirkung von leitfähigen Strukturen auf die Stromaufteilung sowie die Potentialverhältnisse in urbanen Kabelnetzen bei stromstarken Erdschlüssen. Jetzt gratis downloaden!

Bildnachweise