Theory

Before presenting the functionalities of this framework, we need to introduce some important theoretical concepts.

The aim of this framework is to propose operations on lattice theory and Formal Concept Analysis (FCA).

You can skip this introduction if you have an understanding of lattice theory and FCA.

Formal concept analysis

Formal Concept Analysis (FCA) involves the definition of concepts in a given context. These concepts and contexts are completely and precisely defined.

FCA was introduced in 1982 by Rudolf Wille as an application of lattice theory which is based on the works of M. Barbut and B. Monjardet 1 on the whole lattice theory and on Galois connexions.

FCA is used in many fields, such as data mining, text mining, machine learning, semantic web, knowledge management, software development, chemistry and biology. 2

For a better understanding, we will see an overview of lattice theory without digging deep into mathematical theory, then we will introduce the definition of what a concept and a context are.

Lattice theory

Lattice theory was introduced by Birkhoff in his book Trends in LATTICE THEORY

Let’s first introduce the notion of an order relation.

A binary relation \(R\) on a set \(E\) is a set of pairs \((x,y)\), which is a subset of all the pairs \(\in E^2\), We can also write \(xRy\) to say \(x\) has \(R\) relation with \(y\).

We say that \(R\) is an order relation and we note it \(\leq\) if it is:

  • reflexive: \(a \leq a\)

  • transitive: \(a \leq b\) and \(b\leq c\) implies \(a \leq c\)

  • anti-symmetric: \(a \leq b\) and \(b \leq a\) implies \(a = b\)

An ordered set is a pair \((E,\leq)\), with \(E\) being a set and \(\leq\) an order relation on \(E\).

\(a\) is called lower neighbour of \(b\), if \(a < b\) and there is no element \(c\) such as \(a < c < b\), so in this case \(b\) is an upper neighbour of \(a\). (we write: \(a \prec b\)).

Every finite ordered set \((E,\leq)\) can be represented by a line diagram called a Hasse diagram.

Two elements \(x\), \(y\) of an ordered set \((E,\leq)\) are considered comparable if \(x \leq y\) or \(y \leq x\), otherwise they are incomparable.

Let \((E,\leq)\) be an ordered set, and \(X\) a subset of \(E\). A lower bound of \(X\) is an element \(s\) of \(E\) with \(s < x\) for all \(x \in X\). An upper bound of \(X\) is defined dually. If there is a largest element in the set of all lower bounds of \(X\), it is called the infimum of \(X\) and is denoted by \(\inf X\) or \(\bigwedge X\), dually, a least upper bound is called supremum and denoted by \(\sup X\) or \(\bigvee X\).

Infimum and supremum are frequently also called meet and join.

An ordered set \(V = (L,\leq)\) is a lattice if for any two elements \(x, y \in L\), the supremum and the infimum exists.

\(L\) is called a complete lattice, if the supremum \(\bigvee X\) and the infimum \(\bigwedge X\) exist for any subset \(X\) of \(L\). Every complete lattice \(L\) has a largest element, \(\bigvee L\), called the unit element of the lattice, denoted by \(1_L\). Dually, the smallest element \(0_L\) is called the zero element.

Irreducible element: element that can’t be obtained as the join or the meet of any subset of other elements:

Example

The picture bellow represents a lattice. The elements in orange are meet-irreducible and those in green are join-irreducible.

The digit example

Concept and context

If we have a set of objects \(A\) share the same set of attributes \(B\), so that’s mean the pair \((A, B)\) is a formal concept. Concepts are defined in a given context.

A formal context is a triple \((G,M,I)\), \(M\) is a set of object, \(G\) is a set of attributes, and \(I\) is a relation between \(M\) and \(G\), if an object \(g\) has a relation with an attribute \(m\), we write \(gIm\) and we say that the object \(g\) has the attribute \(m\).

The table bellow is an example of a context.

the couple \((\{3,5\}, \{odd,prime\})\) forms a formal concept.

number

composite

even

odd

prime

square

1

x

x

2

x

x

x

3

x

x

4

x

x

x

x

5

x

x

we define the operators \(\alpha\) and \(\beta\) as follows:

  • \(\alpha : 2^G \to 2^M\)

    \(\alpha\) associates common attributes \(B\) to some objects \(A\)

  • \(\beta : 2^M \to 2^G\)

    \(\beta\) associates shared objects \(A\) to attributes \(B\)

\((\alpha,\beta)\) is a Galois connection between \(2^G\) and \(2^M\) if:

  • \(\alpha\) is an antitone map from \(2^G\) to \(2^M\)

  • \(\beta\) is an antitone map from \(2^M\) to \(2^G\)

  • \((\beta\: o\: \alpha)\) and \((\alpha\: o\: \beta)\) are extensive.

A concept is a pair \((A,B)\) with \(A \subseteq G\), \(B \subseteq M\), \(B = \alpha(A)\: and\: A = \beta(B)\)

\(\leq\) : binary relation of specialisation/generalisation between concepts

\[(A_1,B_1) \leq (A_2,B_2) \iff A_1 \subseteq A_2 \iff B_2 \subseteq B_1\]

Examples

Here we present two examples:

The first is constituted of a set of numbers from 0 to 9 as the set of objects \(G = \{0,1,2,3,4,5,6,7,8,9\}\) and some of their properties as a set of attributes \(M = \{even,odd,prime,composite,square\}\)

The table bellow show the context of this example.

number

composite

even

odd

prime

square

0

x

x

x

1

x

x

2

x

x

3

x

x

4

x

x

x

5

x

x

6

x

x

7

x

x

8

x

x

9

x

x

x

The first figure shows the concept lattice corresponding to this first example.

The second example is about animals and their characteristics, here is the context.

Animals

1

2

3

4

5

6

7

8

9

10

11

12

13

Dove

x

x

x

x

Hen

x

x

x

Duck

x

x

x

x

x

Goose

x

x

x

x

x

Owl

x

x

x

x

x

Hawk

x

x

x

x

x

Eagle

x

x

x

x

x

Fox

x

x

x

x

x

Dog

x

x

x

x

Wolf

x

x

x

x

x

x

Cat

x

x

x

x

x

Tiger

x

x

x

x

x

Lion

x

x

x

x

x

x

Horse

x

x

x

x

x

x

Zebra

x

x

x

x

x

x

Cow

x

x

x

x

where:

  • Attribute 1 is: small

  • Attribute 2 is: medium

  • Attribute 3 is: big

  • Attribute 4 is: towlegs

  • Attribute 5 is: fourlegs

  • Attribute 6 is: feathers

  • Attribute 7 is: hair

  • Attribute 8 is: fly

  • Attribute 9 is: hunt

  • Attribute 10 is: run

  • Attribute 11 is: swim

  • Attribute 12 is: mane

  • Attribute 13 is: hooves

And below we give the concept lattice of the second example.

The animal example
1

  1. Barbut & B. Monjardet, Ordre et Classification (2 tomes)

2

https://en.wikipedia.org/wiki/Formal_concept_analysis