Formal Concept Analysis

  • Formal Concept Analysis is a method used for investigating and processing explicitely given information, in order to allow for meaningful and comprehensive interpretation

    • An analysis of data
    • Structures of formal abstractions of concepts of human thought
    • Formal emphasizes that the concepts are mathematical objects, rather than concepts of mind

Formal Concept Analysis

  • Formal Concept Analysis takes as input a matrix specifying a set of objects and the properties thereof, called attributes, and finds both all the “natural” clusters of attributes and all the “natural” clusters of objects in the input data, where
    • a “natural” object cluster is the set of all objects that share a common subset of attributes, and
    • a “natural” property cluster is the set of all attributes shared by one of the natural object clusters

  • Natural property clusters correspond one-for-one with natural object clusters, and a concept is a pair containing both a natural property cluster and its corresponding natural object cluster
  • The family of these concepts obeys the mathematical axioms defining a lattice, and is called a concept lattice

Definition: Formal Context

  • Context: A triple (G, M, I) is a (formal) context if
    • G is a set of objects (Gegenstand)
    • M is a set of attributes (Merkmal)
    • I is a binary relation between G and M called incidence
  • Incidence relation: I ⊆ G x M
    • if g∈G, m∈M in (g,m)∈I, then we know that “ object g has attribute m „ and we write gIm
  • Derivation operators:
    • For A ⊆ G, A‘={m∈M | (g,m)∈I for all g∈A}
    • For B ⊆ M, B‘={g∈G | (g,m)∈I for all m∈B}

Definition: Formal Concept

  • A pair (A,B) is a formal concept of (G,M,I) if and only if
    • A ⊆ G
    • B ⊆ M
    • A‘ = B, and A = B‘
  • Note that at this point the incidence relationship is closed ; i.e. all objects of the concept carry all its attributes and that there is no other object in G carrying all attributes of the concept
  • A is called the extent (Umfang) of the concept (A,B)
  • B is called the intent (Inhalt) of the concept (A,B)

Generating Formal Concepts

  • Using the derivation operators we can derive formal concepts from our formal context with the following routine:

    1. Pick a set of objects A

    2. Derive the attributes A'

    3. Derive (A')'

    4. (A'',A') is a formal concept

  • A dual approach can be taken starting with an attribute


  1. Pick any set of objects A, e.g. A={duck}.
  2. Derive the attributes A'={small, two legs, feathers, fly, swim}
  3. Derive (A')'={small, two legs, feathers, fly, swim}'={duck, goose}
  4. (A'',A')=({duck, goose},{small, two legs, feathers, fly, swim}) is a formal concept.

Creator: OlliG


Licensed under the Creative Commons
Attribution ShareAlike CC-BY-SA license

This deck was created using SlideWiki.