nach oben

1999 | Buch

Kapitel lesen Erstes Kapitel lesen

Formal Concept Analysis

Mathematical Foundations

verfasst von: Prof. Dr. Bernhard Ganter, Prof. Dr. Rudolf Wille

Verlag: Springer Berlin Heidelberg

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten

Über dieses Buch

Formal Concept AllalY.5is is a field of applied mathematics based on the math ematization of concept and conceptual hierarchy. It thereby activates math ematical thinking for conceptual data analysis and knowledge processing. The underlying notion of "concept" evolved early in the philosophical theory of concepts and still has effects today. For example, it has left its mark in the German standards DIN 2:)30 and DIN 2;3:)1. In mathematics it played a special role during the emergence of mathematical logic in the 19th century. Subsequently, however, it had virtually no impact on mathematical thinking. It was not until 1979 that the topic was revisited and treated more thoroughly. Since then, through a large number of contributions, Formal Concept Analysis has obtained such breadth that a systematic presentation is urgently needed, but can no longer be realized in one volume. Therefore, the present book foruse:':! on the mathematical foundations of Formal Concept Analysis, which ran be regarded chiefly as a branch of ap plied lattice theory. A series of examples serves to demonstrate the utility of the lnathematical definitions and results; in particular, to show how Formal Concept Analysis can be used for the conceptual unfolding of data contexts. These examples do not play the role of case studies in data analysis. A is intended for a comprehensive treatment of methods of separate volume conceptual data and knowledge processing. The general foundations of For mal Concept Analysis will also be treated separately.

Inhaltsverzeichnis

Frontmatter

0. Order-theoretic Foundations

Abstract

Formal Concept Analysis is based on mathematical order theory, in particular on the theory of complete lattices. The reader is not required to be familiar with these areas. The mathematical foundations are surveyed in this chapter. However, we limit ourselves to the most important facts, as there is no room for a comprehensive introduction to order theory. For this purpose, we refer to the bibliography listed at the end of this chapter. In general, the reader is supposed to have experience with mathematical texts: we use the technical language of mathematics, in particular of set theory, without further explanation.

Bernhard Ganter, Rudolf Wille

1. Concept Lattices of Contexts

Abstract

The basic notions of Formal Concept Analysis are those of a formal context and a formal concept. The adjective “formal” is meant to emphasize that we are dealing with mathematical notions, which only reflect some aspects of the meaning of context and concept in standard language. However, we will write out the adjective “formal” only in the definition and leave it out later for reasons of convenience, as we have in the title of the first section. Thus, it shall be understood that where we write context or concept we actually mean a formal context or a formal concept, respectively.

Bernhard Ganter, Rudolf Wille

2. Determination and Representation

Abstract

Depending on the circumstances, the task of determining the concept lattice of a context can have different solutions. In the case of a small context, it is useful to start by drawing up a complete list of all concepts. This approach is treated in the first section of this chapter. In the second section, we discuss possibilities to generate line diagrams both automatically or by hand. A list of some dozens of concepts may already be quite difficult to survey, and it requires practice to draw good line diagrams of concept lattices with more than 20 elements. Nested line diagrams permit a satisfactory graphical representation of somewhat larger concept lattices. From some hundred elements at most, a complete graphical representation is no longer possible; in this case it is necessary to apply techniques for splitting up and representing lattices. These will be presented in later chapters.

Bernhard Ganter, Rudolf Wille

3. Parts and Factors

Abstract

If one wishes to examine parts of a rather complex concept system, it seems reasonable to exclude some objects and/or attributes from the examination. We shall describe the effects of this procedure on the concept lattice. The concept lattice of a subcontext always has an order-embedding into that of the original context. Much more information can be obtained when dealing with compatible subcontexts, which will be introduced later in this section. It is easy to identify these particular subcontexts by means of the arrow relations. Thus we obtain a factor lattice of the original concept lattice. The interrelations between factor lattices, congruence relations and such subcontexts will be described in the second section.

Bernhard Ganter, Rudolf Wille

4. Decompositions of Concept Lattices

Abstract

A complex concept lattice can possibly be split up into simpler parts. Here the mathematical model must prove its worth by providing efficacious and versatile methods for the decomposition. Every such decomposition principle can be reversed to make a construction method. Therefore, some of the following subjects will be taken up again in the next chapter with this second focus.

Bernhard Ganter, Rudolf Wille

5. Constructions of Concept Lattices

Abstract

A construction method by means of which we obtain from two contexts K₁ and K₂ a new context, let us say K, can only be a useful construction principle for concept lattices, if it is invariant under reduction. This means that, if the same construction is applied to contexts whose concept lattices are isomorphic to those of K₁ and K₂, then the concept lattice of the result should be isomorphic to that of K.

Bernhard Ganter, Rudolf Wille

6. Properties of Concept Lattices

Abstract

Mathematical lattice theory classifies lattices according to their structural properties. The most important such property, namely distributivity, has already been mentioned in Section 0.3 and has been used several times since then. Now we shall examine it a little more closely. For this purpose, we concentrate on doubly founded lattices, a choice that simplifies many things. Furthermore, we shall examine other interesting properties, for example modularity and semimodularity, which play a particularly important role in geometry. We shall show how semidistributivity and local distributivity can be described by means of the arrow relations and what the consequences of these properties are for the associated closure operators. The last section deals with different notions of dimension of lattices, in particular with that of order dimension.

Bernhard Ganter, Rudolf Wille

7. Context Comparison and Conceptual Measurability

Abstract

Maps between concept lattices that can be used for structure comparison are above all the complete homomorphisms. In Section 3.2 we have worked out the connection between compatible subcontexts and complete congruences, i.e., the kernels of complete homomorphisms. A further approach consists in coupling the lattice homomorphisms with context homomorphisms. In this connection, it seems reasonable to use pairs of maps, i.e., to map the objects and the attributes separately. Those pairs can be treated like maps. We do so without further ado and write, for instance,

$$(\alpha ,\beta ):(G,M,I) \to (H,N,J),$$

if we mean a pair of maps $ \alpha :G \to H,\beta :M \to N, $ using the usual notations for maps by analogy. This does not present any problems, since in the case that $ G \cap M = + H \cap N $ we can replace such a pair of maps (α,β) by the map

$$\alpha \cup \beta :G\dot \cup M \to H\dot \cup N$$

Bernhard Ganter, Rudolf Wille

Backmatter

Titel: Formal Concept Analysis
verfasst von: Prof. Dr. Bernhard Ganter
Prof. Dr. Rudolf Wille
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-59830-2
Print ISBN: 978-3-540-62771-5
DOI: https://doi.org/10.1007/978-3-642-59830-2

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

0. Order-theoretic Foundations

1. Concept Lattices of Contexts

2. Determination and Representation

3. Parts and Factors

4. Decompositions of Concept Lattices

5. Constructions of Concept Lattices

6. Properties of Concept Lattices

7. Context Comparison and Conceptual Measurability

Backmatter