nach oben

2011 | Buch

Kapitel lesen Erstes Kapitel lesen

Formal Concept Analysis

9th International Conference, ICFCA 2011, Nicosia, Cyprus, May 2-6, 2011. Proceedings

herausgegeben von: Petko Valtchev, Robert Jäschke

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

This book constitutes the refereed proceedings of the 9th International Conference on Formal Concept Analysis, ICFCA 2011, held in Nicosia, Cyprus, in May 2011.

The 16 revised full papers presented together with 3 invited talks were carefully reviewed and selected from 49 submissions. The central theme was the mathematical formalization of concept and conceptual hierarchy. The field has developed into a constantly growing research area in its own right with a thriving theoretical community and an increasing number of applications in data and knowledge processing including disciplines such as data visualization, information retrieval, machine learning, software engineering, data analysis, data mining, social networks analysis, etc.

Inhaltsverzeichnis

Frontmatter

Invited Talks

Inductive Databases and Constraint-Based Data Mining

Abstract

We briefly introduce the notion of an inductive database, explain its relation to constraint-based data mining, and illustrate it on an example. We then discuss constraints and constraint-based data mining in more detail. We further give an overview of recent developments in the area, focusing on those made within the IQ project and presented in a recent volume with the same title as this paper, edited by the author, Bart Goethals and Panče Panov, and published by Springer.

Sašo Džeroski

What’s Happening in Semantic Web

... and What FCA Could Have to Do with It

Abstract

The Semantic Web [27] is gaining momentum. Driven by over 10 years of focused project funding in the US and the EU, Semantic Web Technologies are now entering application areas in industry, academia, government, and the open Web.

The Semantic Web is based on the idea of describing the meaning - or semantics - of data on the Web using metadata - data that describes other data - in the form of ontologies, which are represented using logic-based knowledge representation languages [26]. Central to the transfer of Semantic Web into practice is the Linked Open Data effort [7], which has already resulted in the publication, on the Web, of billions of pieces of information using ontology languages. This provides the basic data needed for establishing intelligent system applications on the Web in the tradition of Semantic Web Technologies.

Pascal Hitzler

Galois Connections in Axiomatic Aggregation

Abstract

We investigate the relations between, on the one hand, Galois connections and the related types of maps and, on the other hand, the axiomatic Arrowian approach for the aggregation (or consensus) problem in lattices. In the latter one wants to ”aggregate” n-tuples (n ≥ 2) of elements of a lattice L into an element of this lattice representing their ”consensus”, subject to satisfying some desirable properties. The main axiom is a generalization of Arrow’s [1] independence. The results consist in the characterization of convenient aggregation functions, and especially in impossibility ones when axioms turn to be incompatible. For the many applications of this theory in the domains of social choice or cluster analysis, see, e.g., the book of Day and McMorris [4]. Basic characterizations of Arrowian aggregation functions according to a specific typology of finite lattices are given by Monjardet [10]. They are extended to lattices of Galois maps (or polarized ones, that is maps appearing in Galois connections), then particularized to fuzzy preorders and hierarchical classifications, in Leclerc [7]. A unified presentation is given in Leclerc and Monjardet [8].

An FCA-related representation of Galois maps between two fixed lattices is given in Domenach and Leclerc [5] with the introduction of the so-called ”biclosed” relations. As pointed out in the unifying paper of Ganter [6], the notion of biclosed relations is related to several others in the literature. The first part of the presentation will be devoted to Arrowian aggregation of biclosed relations.

In the second part, we present another relation between Aggregation theory and residuated/residual maps (those appearing in Residuation Theory [2]), which corresponds to ”covariant” Galois connections. Chambers and Miller [3] and Leclerc and Monjardet [9] have recently pointed out that, in a significant class of atomistic lattices, an aggregation function is a meet-projection if and only if it is a residual mapping.

Bruno Leclerc

Regular Contributions

Backing Composite Web Services Using Formal Concept Analysis

Abstract

A Web service is a software functionality accessible through the network. Web services are intended to be composed into coarser-grained applications. Achieving a required composite functionality requires the discovery of a collection of Web services out of the enormous service space. Each service must be examined to verify its provided functionality, making the selection task neither efficient nor practical. Moreover, when a service in a composition becomes unavailable, the whole composition may become functionally broken. Therefore, an equivalent service must be retrieved to replace the broken one, thus spending more time and effort. In this paper, we propose an approach for Web service classification based on FCA, using their operations estimated similarities. The generated lattices make the identification of candidate substitutes to a given service straightforward. Thus, service compositions can be achieved more easily and with backup services, so as to easily recover the functionality of a broken service.

Zeina Azmeh, Fady Hamoui, Marianne Huchard, Nizar Messai, Chouki Tibermacine, Christelle Urtado, Sylvain Vauttier

Enumerating Minimal Hypotheses and Dualizing Monotone Boolean Functions on Lattices

Abstract

Any monotone Boolean function on a lattice can be described by the set of its minimal 1 values. If a lattice is given as a concept lattice, this set can be represented by the set of minimal hypotheses of a classification context. Enumeration of minimal hypotheses in output polynomial time is shown to be impossible unless P = NP, which shows that dualization of monotone functions on lattices with quasipolynomial delay is hardly possible.

Mikhail A. Babin, Sergei O. Kuznetsov

Border Algorithms for Computing Hasse Diagrams of Arbitrary Lattices

Abstract

The Border algorithm and the iPred algorithm find the Hasse diagrams of FCA lattices. We show that they can be generalized to arbitrary lattices. In the case of iPred, this requires the identification of a join-semilattice homomorphism into a distributive lattice.

José L. Balcázar, Cristina Tîrnăucă

Selecting Important Concepts Using Weights

Abstract

We present an approach that enables one to select a reasonable small number of possibly important formal concepts from the set of all formal concepts of a given input data. The problem to select a small number of concepts appears in applications of formal concept analysis when the number of all formal concepts of the input data is large. Namely, a user often asks for a list of “important concepts” in such case. In the present approach, attributes of the input data are assigned weights from which values of formal concepts are determined. Formal concepts with larger values are considered more important. The attribute weights are supposed to be set by the users. The approach is a continuation of our previous approaches that utilize background knowledge, i.e. additional knowledge of a user, to select parts of concept lattices. In addition to the approach, we present illustrative examples.

Radim Belohlavek, Juraj Macko

Some Complexity Results about Essential Closed Sets

Abstract

We examine the enumeration problem for essential closed sets of a formal context. Essential closed sets are sets that can be written as the closure of a pseudo-intent. The results for enumeration of essential closed sets are similar to existing results for pseudo-intents, albeit some differences exist. For example, while it is possible to compute the lectically first pseudo-intent in polynomial time, we show that it is not possible to compute the lectically first essential closed set in polynomial time unless P = NP. This also proves that essential closed sets cannot be enumerated in the lectic order with polynomial delay unless P = NP. We also look at minimal essential closed sets and show that they cannot be enumerated in output polynomial time unless P = NP.

Felix Distel

A Context-Based Description of the Doubly Founded Concept Lattices in the Variety Generated by M 3

Abstract

In universal algebra and in lattice theory the notion of varieties is very prominent, since varieties describe the classes of all algebras (or of all lattices) modeling a given set of equations. While a comprehensive translation of that notion to a similar notion of varieties of complete lattices – and thus to Formal Concept Analysis – has not yet been accomplished, some characterizations of the doubly founded complete lattices of some special varieties (e.g. the variety of modular or that of distributive lattices) have been discovered. In this paper we use the well-known arrow relations to give a characterization of the formal contexts of doubly founded concept lattices in the variety that is generated by M ₃ – the smallest modular, non-distributive lattice variety.

Stephan Doerfel

Factorization with Hierarchical Classes Analysis and with Formal Concept Analysis

Abstract

We present a comparison between Hierarchical Classes Analysis and the formal concept analytical approach to Factor Analysis regarding the factorization problem of binary matrices. Both methods decompose a binary matrix into the Boolean matrix product of two binary matrices such that the number of factors is as small as possible. We show that the two approaches yield the same decomposition even though the methods are different. The main aim of this paper is to connect the two fields as they produce the same results and we show how the two domains can benefit from one another.

Cynthia Vera Glodeanu

Gene Expression Array Exploration Using $\mathcal{K}$ -Formal Concept Analysis

Abstract

DNA micro-arrays are a mechanism for eliciting gene expression values, the concentration of the transcription products of a set of genes, under different chemical conditions. The phenomena of interest—up-regulation, down-regulation and co-regulation—are hypothesized to stem from the functional relationships among transcription products.

In [1,2,3] a generalisation of Formal Concept Analysis was developed with data mining applications in mind, $\mathcal{K}$-Formal Concept Analysis, where incidences take values in certain kinds of semirings, instead of the usual Boolean carrier set. In this paper, we use ($\overline{\mathbb{R}}_{min, +}$)- and ($\overline{\mathbb{R}}_{max, +}$) to analyse gene expression data for Arabidopsis thaliana. We introduce the mechanism to render the data in the appropriate algebra and profit by the wealth of different Galois Connections available in Generalized Formal Concept Analysis to carry different analysis for up- and down-regulated genes.

José María González Calabozo, Carmen Peláez-Moreno, Francisco José Valverde-Albacete

Biclustering Numerical Data in Formal Concept Analysis

Abstract

A numerical dataset is usually represented by a table where each entry denotes the value taken by an object in line for an attribute in column. A bicluster in a numerical data table is a subtable with close values different from values outside the subtable. Traditionally, largest biclusters were found by means of methods based on linear algebra. We propose an alternative approach based on concept lattices and lattices of interval pattern structures. In other words, this paper shows how formal concept analysis originally tackles the problem of biclustering and provides interesting perspectives of research.

Mehdi Kaytoue, Sergei O. Kuznetsov, Amedeo Napoli

Object Configuration Browsing in Relational Databases

Abstract

Conventional means of querying a database for relevant information require some degree of knowledge about the nature and the structural representation of such information. The paper addresses the case where sufficient knowledge is not readily available a priori. A method for data exploration based on the refinement of graphs, which represent summarized views of the underlying data, is proposed and illustrated by a small example featuring relational data extracted from an Electronic Health Record. The method is based on Formal Concept Analysis, extended to the case of several many-valued formal contexts, one for each database table, with additional referential attributes.

Jens Kötters

On Factorization of Concept Lattices by Incompatible Tolerances

Abstract

It is a well-known fact that complete tolerance relations on concept lattices are in one-to-one correspondence with some superrelations (called block relations) of the incidence relation of the underlying formal context. However, sometimes it is useful to consider more general superrelations of the incidence relation, leading to tolerance relations, not compatible with the lattice structure of the concept lattice. In this paper, we give a characterization of such tolerances and present a mathematical framework for factorizing any complete lattice by such incompatible tolerances.

Michal Krupka

Merging Ordered Sets

Abstract

While extending partial orders towards linear orders is a very well-researched topic, the combination of two ordered sets has not yet attracted too much attention. In the underlying article, however, we describe the possibilities to merge two given quasiordered sets in the sense that the restriction of the combined order towards the given ordered sets returns the initial orders again. It turns out that these mergings form a complete lattice. We elaborate these lattices of mergings and present its contextual representation. While the motivating example was discovered in role-oriented software modeling, we give a further possible application in the field of scheduling.

Bernhard Ganter, Christian Meschke, Henri Mühle

Mining Triadic Association Rules from Ternary Relations

Abstract

Ternary and more generally n-ary relations are commonly found in real-life applications and data collections. In this paper, we define new notions and propose procedures to mine closed tri-sets (triadic concepts) and triadic association rules within the framework of triadic concept analysis. The input data is represented as a formal triadic context of the form $\mathbb{K}:=(K_1, K_2, K_3, Y)$, where K ₁, K ₂ and K ₃ are object, attribute and condition sets respectively, and Y is a ternary relation between the three sets. While dyadic association rules represent links between two groups of attributes (itemsets), triadic association rules can take at least three distinct forms. One of them is the following: A ${\underrightarrow{c}}$ D, where A and D are subsets of K ₂, and C is a subset of K ₃. It states that A implies D under the conditions in C. In particular, the implication holds for any subset in C.

The benefits of triadic association rules of this kind lie in the fact that they represent patterns in a more compact and meaningful way than association rules that can be extracted for example from the formal (dyadic) context $\mathbb{K}^{(1)}:= (K_1, K_2 \times K_3, Y^{(1)}) \text{ with } (a_i, (a_j, a_k)) \in Y^{(1)} : \iff (a_i, a_j, a_k) \in Y.$

Rokia Missaoui, Léonard Kwuida

The Agree Concept Lattice for Multidimensional Database Analysis

Abstract

In this paper we propose the characterization of two new structures, the Agree Concept Lattice and the Quotient Agree Lattice of a database relation. Both of them are of great interest for multidimensional database analysis. They provide a formal framework which makes it possible to improve computation time, reduce representation and easily navigate through the Hasse diagram. These structures are generic, apply to various database analysis problems and combine formal concept analysis and database theory. They make use of the concepts of agree set and database partition. Agree set and partition are associated to define the Agree Concept of a database relation. The set of all the Agree Concepts is organized within the Agree Concept Lattice. The Quotient Agree Lattice is along the lines of both the Titanic framework and the quotient cube.

We also briefly present three application fields of the proposed structures. The first two ones are classical since they concern on the one hand the discovery of functional and approximate dependencies for database design and tuning and on the other hand the data cube computation and representation. The latter field has been recently investigated. The underlying issue is to retrieve the most relevant objects according to the user expectations: the Skyline. The multidimensional generalization of the Skyline has been proposed through the Skycube. The proposed structures smartly solve the problem of partial materialization of Skycube with reconstruction guarantee.

Sébastien Nedjar, Fabien Pesci, Lotfi Lakhal, Rosine Cicchetti

Abstract Concept Lattices

Abstract

We present a view of abstraction based on a structure preserving reduction of the Galois connection between a language $\cal L$ of terms and the powerset of a set of instances O. Such a relation is materialized as an extension-intension lattice, namely a concept lattice when L is the powerset of a set P of attributes. We define and characterize an abstraction A as some part of either the language or the powerset of O, defined in such a way that the extension-intension latticial structure is preserved. Such a structure is denoted for short as an abstract lattice. We discuss the extensional abstract lattices obtained by so reducing the powerset of O, together together with the corresponding abstract implications, and discuss alpha lattices as particular abstract lattices. Finally we give formal framework allowing to define a generalized abstract lattice whose language is made of terms mixing abstract and non abstract conjunctions of properties.

Henry Soldano, Véronique Ventos

Exploring the Information Space of Cultural Collections Using Formal Concept Analysis

Abstract

Within the cultural informatics community, there is a strong desire to mine and understand relationships within and among collections of objects. In this paper we describe a case study of applied Formal Concept Analysis to cultural heritage and art collections. We base our inter-disciplinary research on our development of a navigation framework that drives the Virtual Museum of the Pacific – an FCA-based application that employs a conceptual neighbourhood paradigm for browsing concept lattices. We also utilise a feature called conceptual similarity that allows users to search for similar objects and hence promote knowledge discovery of the objects within the collection. We describe how we can construct a meaningful information space derived from museum documentation while considering complexity and associated performance issues of large formal contexts. We report the resulting lattice structure, user experience and relevance of our FCA-based application in browsing and exploring objects from a cultural domain. Our research is an applied case study of term extraction and context creation based on data-sets from the Australian Museum and Powerhouse Museum collections.

Tim Wray, Peter Eklund

Backmatter

Titel: Formal Concept Analysis
herausgegeben von: Petko Valtchev
Robert Jäschke
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-20514-9
Print ISBN: 978-3-642-20513-2
DOI: https://doi.org/10.1007/978-3-642-20514-9

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Invited Talks

Inductive Databases and Constraint-Based Data Mining

What’s Happening in Semantic Web

Galois Connections in Axiomatic Aggregation

Regular Contributions

Backing Composite Web Services Using Formal Concept Analysis

Enumerating Minimal Hypotheses and Dualizing Monotone Boolean Functions on Lattices

Border Algorithms for Computing Hasse Diagrams of Arbitrary Lattices

Selecting Important Concepts Using Weights

Some Complexity Results about Essential Closed Sets

A Context-Based Description of the Doubly Founded Concept Lattices in the Variety Generated by M 3

Factorization with Hierarchical Classes Analysis and with Formal Concept Analysis

Gene Expression Array Exploration Using $\mathcal{K}$ -Formal Concept Analysis

Biclustering Numerical Data in Formal Concept Analysis

Object Configuration Browsing in Relational Databases

On Factorization of Concept Lattices by Incompatible Tolerances

Merging Ordered Sets

Mining Triadic Association Rules from Ternary Relations

The Agree Concept Lattice for Multidimensional Database Analysis

Abstract Concept Lattices

Exploring the Information Space of Cultural Collections Using Formal Concept Analysis

Backmatter

Premium Partner