📘 Lattices of formal concepts

📘 Lattices of formal concepts#

Lattices are algebraic structures that capture the notions of order and hierarchy within a set. In the GALACTIC framework, concept lattices are implemented using the ExtensibleConceptLattice class (or the FrozenConceptLattice class) of the galactic.algebras.concept.core module, which allows for the creation, manipulation, and analysis of lattices.

Creating concept lattices#

The constructor of the ExtensibleConceptLattice class takes a series of iterables of Concept, representing the generators of the lattice. These concepts can be created using the Concept class from a given ConceptGaloisConnection. The signature of the constructor makes the FrozenConceptLattice class a closure operator over concepts.

from galactic.algebras.concept.core import (
    Concept,
    ConceptGaloisConnection,
    ExtensibleConceptLattice,
    create_context_from_dataset
)
from galactic.algebras.concept.examples.animals.core import ANIMAL_ATTRS, ANIMAL_DATA
context = create_context_from_dataset(ANIMAL_DATA, ANIMAL_ATTRS)
connection = ConceptGaloisConnection(context)
cat_concept = Concept(connection, items=[context.domain.item(key='Cat')])
dog_concept = Concept(connection, items=[context.domain.item(key='Dog')])
lattice_1 = ExtensibleConceptLattice([cat_concept, dog_concept])
display(
    lattice_1,
    list(lattice_1),
    list(list(str(item) for item in concept.extent)  for concept in lattice_1),
)

<galactic.algebras.concept.core.ExtensibleConceptLattice object at 0x781c4e375c40>

[<galactic.algebras.concept.core.Concept object at 0x781c4ecf0b40>,
 <galactic.algebras.concept.core.Concept object at 0x781c4e1e5d80>,
 <galactic.algebras.concept.core.Concept object at 0x781c4e1e5d00>,
 <galactic.algebras.concept.core.Concept object at 0x781c4e1e7340>]

[[],
 ['Fox', 'Dog', 'Wolf'],
 ['Fox', 'Dog', 'Wolf', 'Cat', 'Tiger', 'Lion', 'Horse', 'Zebra'],
 ['Cat']]

Iterables given to the constructor are used as generators of the lattice. Operation is optimized if an iterable is a lattice itself.

feathers_concept = Concept(
    connection,
    attrs=[context.co_domain.attr(name='feathers')],
)
lattice_2 = ExtensibleConceptLattice([feathers_concept])
display(
    lattice_2,
    list(lattice_2),
    list(list(str(item) for item in concept.extent) for concept in lattice_2),
)
lattice = ExtensibleConceptLattice(lattice_1, lattice_2)
display(
    lattice,
    list(lattice),
    list(list(str(item) for item in concept.extent) for concept in lattice),
)

<galactic.algebras.concept.core.ExtensibleConceptLattice object at 0x781c4e376740>

[<galactic.algebras.concept.core.Concept object at 0x781c4e1a9b80>]

[['Dove', 'Hen', 'Duck', 'Goose', 'Owl', 'Hawk', 'Eagle']]

<galactic.algebras.concept.core.ExtensibleConceptLattice object at 0x781c4e376a40>

[<galactic.algebras.concept.core.Concept object at 0x781c4e206c00>,
 <galactic.algebras.concept.core.Concept object at 0x781c4e207580>,
 <galactic.algebras.concept.core.Concept object at 0x781c4e2076c0>,
 <galactic.algebras.concept.core.Concept object at 0x781c4e206d00>,
 <galactic.algebras.concept.core.Concept object at 0x781c4e2071c0>,
 <galactic.algebras.concept.core.Concept object at 0x781c4e2061c0>]

[[],
 ['Fox', 'Dog', 'Wolf'],
 ['Fox', 'Dog', 'Wolf', 'Cat', 'Tiger', 'Lion', 'Horse', 'Zebra'],
 ['Dove',
  'Hen',
  'Duck',
  'Goose',
  'Owl',
  'Hawk',
  'Eagle',
  'Fox',
  'Dog',
  'Wolf',
  'Cat',
  'Tiger',
  'Lion',
  'Horse',
  'Zebra',
  'Cow'],
 ['Cat'],
 ['Dove', 'Hen', 'Duck', 'Goose', 'Owl', 'Hawk', 'Eagle']]

Operating on concept lattices#

The ExtensibleConceptLattice class (and the FrozenConceptLattice class) provides methods to operate on lattices using the join (\(\vee\)) or meet (\(\wedge\)) operators.

join = lattice_1 | lattice_2
meet = lattice_1 & lattice_2
display(
    join,
    list(join),
    list(list(str(item) for item in concept.extent) for concept in join),
)
display(
    meet,
    list(meet),
    list(list(str(item) for item in concept.extent) for concept in meet),
)

<galactic.algebras.concept.core.ExtensibleConceptLattice object at 0x781c4e376840>

[<galactic.algebras.concept.core.Concept object at 0x781c4e217e40>,
 <galactic.algebras.concept.core.Concept object at 0x781c4e217fc0>,
 <galactic.algebras.concept.core.Concept object at 0x781c4e215440>,
 <galactic.algebras.concept.core.Concept object at 0x781c4e215480>,
 <galactic.algebras.concept.core.Concept object at 0x781c4e222d40>,
 <galactic.algebras.concept.core.Concept object at 0x781c4e220200>]

[[],
 ['Fox', 'Dog', 'Wolf'],
 ['Fox', 'Dog', 'Wolf', 'Cat', 'Tiger', 'Lion', 'Horse', 'Zebra'],
 ['Dove',
  'Hen',
  'Duck',
  'Goose',
  'Owl',
  'Hawk',
  'Eagle',
  'Fox',
  'Dog',
  'Wolf',
  'Cat',
  'Tiger',
  'Lion',
  'Horse',
  'Zebra',
  'Cow'],
 ['Cat'],
 ['Dove', 'Hen', 'Duck', 'Goose', 'Owl', 'Hawk', 'Eagle']]

<galactic.algebras.concept.core.ExtensibleConceptLattice object at 0x781c4e376c40>

[]

[]

Accessing concept lattices#

In addition to the standard lattice properties and methods provided by the core module, the ExtensibleConceptLattice class (and the FrozenConceptLattice class) also provides specific properties related to concept lattices.

  • connection: returns the underlying antitone Galois connection associated to a concept lattice

  • context: returns the underlying context associated to a concept lattice

  • introduced_items(): returns the collection of items introduced at a specific concept

  • introduced_attrs(): returns the collection of attributes introduced at a specific concept

  • item_concepts(): return a mapping from items to the concepts that introduce them

  • attr_concepts(): return a mapping from attributes to the concepts that introduce them

lattice = ExtensibleConceptLattice([cat_concept, dog_concept, feathers_concept])
display(
    lattice.connection,
    lattice.context,
    list(str(item) for item in lattice.introduced_items(cat_concept)),
    list(str(attr) for attr in lattice.introduced_attrs(feathers_concept)),
    dict(lattice.item_concepts),
    dict(lattice.attr_concepts),
)

<galactic.algebras.concept.core.ConceptGaloisConnection object at 0x781c4ecf1440>

<galactic.algebras.concept.core.Context object at 0x781c4ecd5300>

['Cat']

['twolegs', 'feathers']

{Item(key='Dove', value=<tuple object at 0x781c4ecd5210>): <galactic.algebras.concept.core.Concept object at 0x781c4e216740>,
 Item(key='Hen', value=<tuple object at 0x781c4ecef540>): <galactic.algebras.concept.core.Concept object at 0x781c4e216740>,
 Item(key='Duck', value=<tuple object at 0x781c4e1afc90>): <galactic.algebras.concept.core.Concept object at 0x781c4e216740>,
 Item(key='Goose', value=<tuple object at 0x781c4e1afc90>): <galactic.algebras.concept.core.Concept object at 0x781c4e216740>,
 Item(key='Owl', value=<tuple object at 0x781c4e1afd80>): <galactic.algebras.concept.core.Concept object at 0x781c4e216740>,
 Item(key='Hawk', value=<tuple object at 0x781c4e1afd80>): <galactic.algebras.concept.core.Concept object at 0x781c4e216740>,
 Item(key='Eagle', value=<tuple object at 0x781c4e1afdd0>): <galactic.algebras.concept.core.Concept object at 0x781c4e216740>,
 Item(key='Fox', value=<tuple object at 0x781c4e1afe20>): <galactic.algebras.concept.core.Concept object at 0x781c4e23a280>,
 Item(key='Dog', value=<tuple object at 0x781c4ecd5620>): <galactic.algebras.concept.core.Concept object at 0x781c4e23a280>,
 Item(key='Wolf', value=<tuple object at 0x781c4ec87940>): <galactic.algebras.concept.core.Concept object at 0x781c4e23a280>,
 Item(key='Cat', value=<tuple object at 0x781c4e1afe70>): <galactic.algebras.concept.core.Concept object at 0x781c4e23ad00>,
 Item(key='Tiger', value=<tuple object at 0x781c4e1afec0>): <galactic.algebras.concept.core.Concept object at 0x781c4e24c700>,
 Item(key='Lion', value=<tuple object at 0x781c4e36ba60>): <galactic.algebras.concept.core.Concept object at 0x781c4e24c700>,
 Item(key='Horse', value=<tuple object at 0x781c4e1c8d00>): <galactic.algebras.concept.core.Concept object at 0x781c4e24c700>,
 Item(key='Zebra', value=<tuple object at 0x781c4e1c8d00>): <galactic.algebras.concept.core.Concept object at 0x781c4e24c700>,
 Item(key='Cow', value=<tuple object at 0x781c4ecd5a30>): <galactic.algebras.concept.core.Concept object at 0x781c4e23af80>}

{<function small at 0x781c4e1c44a0>: <galactic.algebras.concept.core.Concept object at 0x781c4e23b000>,
 <function hunt at 0x781c4e1c7920>: <galactic.algebras.concept.core.Concept object at 0x781c4e23b000>,
 <function medium at 0x781c4e1c5a80>: <galactic.algebras.concept.core.Concept object at 0x781c4e23b080>,
 <function big at 0x781c4e1c5bc0>: <galactic.algebras.concept.core.Concept object at 0x781c4e23b100>,
 <function fly at 0x781c4e1c6de0>: <galactic.algebras.concept.core.Concept object at 0x781c4e23b100>,
 <function swim at 0x781c4e1c71a0>: <galactic.algebras.concept.core.Concept object at 0x781c4e23b100>,
 <function mane at 0x781c4e1c7ce0>: <galactic.algebras.concept.core.Concept object at 0x781c4e23b100>,
 <function hooves at 0x781c4e1e00e0>: <galactic.algebras.concept.core.Concept object at 0x781c4e23b100>,
 <function twolegs at 0x781c4e1c5f80>: <galactic.algebras.concept.core.Concept object at 0x781c4e23b180>,
 <function feathers at 0x781c4e1c5760>: <galactic.algebras.concept.core.Concept object at 0x781c4e23b180>,
 <function fourlegs at 0x781c4e1c6340>: <galactic.algebras.concept.core.Concept object at 0x781c4e23b280>,
 <function hair at 0x781c4e1c6700>: <galactic.algebras.concept.core.Concept object at 0x781c4e23b280>,
 <function run at 0x781c4e1c7560>: <galactic.algebras.concept.core.Concept object at 0x781c4e23b280>}

Views of concept lattices#

The ExtentLattice class and the IntentLattice class of the core module provide specialized views (Moore families) of concept lattices that focus on the extents and intents of concepts, respectively.

from galactic.algebras.concept.core import ExtentLattice, IntentLattice
extent_lattice = ExtentLattice(lattice)
intent_lattice = IntentLattice(lattice)
display(
    extent_lattice,
    list(extent_lattice),
    list(list(str(item) for item in extent) for extent in extent_lattice),
)
display(
    intent_lattice,
    list(intent_lattice),
    list(list(str(attr) for attr in intent) for intent in intent_lattice),
)

<galactic.algebras.concept.core.ExtentLattice object at 0x781c4e2d2a40>

[<galactic.algebras.concept.core.Extent object at 0x781c4e24c600>,
 <galactic.algebras.concept.core.Extent object at 0x781c4ecfe700>,
 <galactic.algebras.concept.core.Extent object at 0x781c4e24fe00>,
 <galactic.algebras.concept.core.Extent object at 0x781c4e24fe40>,
 <galactic.algebras.concept.core.Extent object at 0x781c4e24f6c0>,
 <galactic.algebras.concept.core.Extent object at 0x781c4e24f580>]

[[],
 ['Fox', 'Dog', 'Wolf'],
 ['Fox', 'Dog', 'Wolf', 'Cat', 'Tiger', 'Lion', 'Horse', 'Zebra'],
 ['Dove',
  'Hen',
  'Duck',
  'Goose',
  'Owl',
  'Hawk',
  'Eagle',
  'Fox',
  'Dog',
  'Wolf',
  'Cat',
  'Tiger',
  'Lion',
  'Horse',
  'Zebra',
  'Cow'],
 ['Cat'],
 ['Dove', 'Hen', 'Duck', 'Goose', 'Owl', 'Hawk', 'Eagle']]

<galactic.algebras.concept.core.IntentLattice object at 0x781c4e2d22c0>

[<galactic.algebras.concept.core.Intent object at 0x781c4e216e40>,
 <galactic.algebras.concept.core.Intent object at 0x781c4e24f6c0>,
 <galactic.algebras.concept.core.Intent object at 0x781c4e24d980>,
 <galactic.algebras.concept.core.Intent object at 0x781c4e25ce40>,
 <galactic.algebras.concept.core.Intent object at 0x781c4e25ce00>,
 <galactic.algebras.concept.core.Intent object at 0x781c4e25cf40>]

[['small',
  'medium',
  'big',
  'twolegs',
  'fourlegs',
  'hair',
  'feathers',
  'fly',
  'swim',
  'run',
  'hunt',
  'mane',
  'hooves'],
 ['medium', 'fourlegs', 'hair', 'run'],
 ['fourlegs', 'hair', 'run'],
 [],
 ['small', 'fourlegs', 'hair', 'run', 'hunt'],
 ['twolegs', 'feathers']]
Contents