Formal Concept Analysis
From data to their conceptualization
Formal Concept Analysis
This description of the concept “bird” is based on sets of
Objects, attributes and a relation form a formal concept
A repertoire of objects and attributes (which might or might not be related) constitutes the „context“ of our considerations
DEFINITIONS
Formal Concept Analysis is a method used for investigating and processing explicitely given information, in order to allow for meaningful and comprehensive interpretation
Formal emphasizes that the concepts are mathematical objects, rather than concepts of mind
a “natural” property cluster is the set of all attributes shared by one of the natural object clusters
The family of these concepts obeys the mathematical axioms defining a lattice, and is called a concept lattice
Using the derivation operators we can derive formal concepts from our formal context with the following routine:
Pick a set of objects A
Derive the attributes A'
Derive (A')'
(A'',A') is a formal concept
A dual approach can be taken starting with an attribute
CONCEPT LATTICE
(A _{ 1 } , B_{1 } ) ≤ (A _{ 2 } ,B _{ 2 } ) : ⇔ A _{ 1 } ⊆A _{ 2 } (⇔ B _{ 2 } ⊆B _{ 1 } )
The ordered set of all formal concepts in (G,M,I) is denoted by Β(G,M,I) and is called concept lattice (Begriffsverband)
A concept lattice consists of the set of concepts of a formal context and the subconceptsuperconcept relation between the concepts
The extent of an arbitrary concept is then found in the principle ideal generated by that concept
The intent of an arbitrary concept is then found in the principle filter generated by that concept
e.g. if X has feather and has beak then is a bird
The implication determines the concept lattice up to isomorphism and therefore offers an additional interpretation of the lattice structure
Implications can be used for a stepwise construction of conceputal knowledge
Start at top with all objects and no attributes
({horse, zebra, lion, wolf, cat, eagle, owl, hawk, duck, goose},).
Make a concepts for the biggest set of attributes (i.e. hair and small)
Are there any objects that exactly match these attributes? No, so we label the concepts with only the attributes
({fox, dog, wolf, cat, tiger, lion, horse, zebra, cow}, {hair})
({dove, hen, duck, goose, owl, hawk, cat}, {small}).
Add one attribute at a time to the attribute sets
fourlegs to small
fourlges and mane to hair
Are there any objects that exactly match these attributes? Yes, so we label the concepts with objects. Giving:
({cat},{small, fourlegs})
({fox, dog, wolf, cat, tiger, lion, horse, zebra, cow}, {hair, fourlges})
({horse, zebra, lion, wolf}, {hair, mane})
And so on… finally when all objects have been labelled, add the full collection of attributes to the bottom node
As G = {1,2,3} there are no further extents
ILLUSTRATION BY A LARGER EXAMPLE


K0

sex

age


ADAM

M

21


BETTY

F

50


CHRIS

/

66


DORA

F

88


EVA

F

17


FRED

M

/


GEORGE

M

90


HARRY

M

50



K

sex


age







M

F

<18

<40

<=65

>65

>=80


ADAM

X



X

X




BETTY


X



X




CHRIS






X



DORA


X




X

X


EVA


X

X

X

X




FRED

X








GEORGE

X





X

X


HARRY

X




X



By selecting a single view (i.e. an attribute space) we can create the following lattices
Diagrams can be combined to create a single lattice representing all the data space
EXTENSIONS
SUMMARY
Formal Concept Analysis is a method used for investigating and processing explicitely given information, in order to allow for meaningful and comprehensive interpretation
A concept is given by a pair of objects and attributes within a formal context (G,M,I)
The ordered set of all formal concepts in (G,M,I) is denoted by B(G,M,I) and is called concept lattice
Within a concept lattices it is possible to derive concept hierarchies, to determine superconcept or subconcepts
REFERENCES
Questions?