📘 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 ExtensibleLattice class (or the FrozenLattice 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 ExtensibleLattice 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 GaloisConnection. The signature of the constructor makes the FrozenLattice class a closure operator over concepts.

from galactic.algebras.concept.core import (
    Concept,
    GaloisConnection,
    ExtensibleLattice,
    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 = GaloisConnection(context)
cat_concept = Concept(connection, items=[context.domain.item(key='Cat')])
dog_concept = Concept(connection, items=[context.domain.item(key='Dog')])
lattice_1 = ExtensibleLattice([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.ExtensibleLattice object at 0x7111f6cd9d50>

[<galactic.algebras.concept.core.Concept object at 0x7111f6171c40>,
 <galactic.algebras.concept.core.Concept object at 0x7111f617cf80>,
 <galactic.algebras.concept.core.Concept object at 0x7111f617cec0>,
 <galactic.algebras.concept.core.Concept object at 0x7111f617ce80>]

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

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 = ExtensibleLattice([feathers_concept])
display(
    lattice_2,
    list(lattice_2),
    list(list(str(item) for item in concept.extent) for concept in lattice_2),
)
lattice = ExtensibleLattice(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.ExtensibleLattice object at 0x7111f61594e0>

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

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

<galactic.algebras.concept.core.ExtensibleLattice object at 0x7111f6f4a4d0>

[<galactic.algebras.concept.core.Concept object at 0x7111f6196d00>,
 <galactic.algebras.concept.core.Concept object at 0x7111f61a5800>,
 <galactic.algebras.concept.core.Concept object at 0x7111f61a62c0>,
 <galactic.algebras.concept.core.Concept object at 0x7111f61a63c0>,
 <galactic.algebras.concept.core.Concept object at 0x7111f61a56c0>,
 <galactic.algebras.concept.core.Concept object at 0x7111f61a5240>]

[[],
 ['Dove', 'Hen', 'Duck', 'Goose', 'Owl', 'Hawk', 'Eagle'],
 ['Cat'],
 ['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']]

Operating on concept lattices#

The ExtensibleLattice class (and the FrozenLattice 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.ExtensibleLattice object at 0x7111f61596c0>

[<galactic.algebras.concept.core.Concept object at 0x7111f61a5880>,
 <galactic.algebras.concept.core.Concept object at 0x7111f61bad80>,
 <galactic.algebras.concept.core.Concept object at 0x7111f61ae880>,
 <galactic.algebras.concept.core.Concept object at 0x7111f61aea40>,
 <galactic.algebras.concept.core.Concept object at 0x7111f61bacc0>,
 <galactic.algebras.concept.core.Concept object at 0x7111f61bac00>]

[[],
 ['Dove', 'Hen', 'Duck', 'Goose', 'Owl', 'Hawk', 'Eagle'],
 ['Cat'],
 ['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']]

<galactic.algebras.concept.core.ExtensibleLattice object at 0x7111f61597b0>

[]

[]

Accessing concept lattices#

In addition to the standard lattice properties and methods provided by the galactic.algebras.lattice.core module, the ExtensibleLattice class (and the FrozenLattice 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 = ExtensibleLattice([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.GaloisConnection object at 0x7111f61563c0>

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

['Cat']

['twolegs', 'feathers']

{Item(key='Dove', value=<list object at 0x7111f613e7c0>): <galactic.algebras.concept.core.Concept object at 0x7111f617d0c0>,
 Item(key='Hen', value=<list object at 0x7111f61567c0>): <galactic.algebras.concept.core.Concept object at 0x7111f617d0c0>,
 Item(key='Duck', value=<list object at 0x7111f6156800>): <galactic.algebras.concept.core.Concept object at 0x7111f617d0c0>,
 Item(key='Goose', value=<list object at 0x7111f6156840>): <galactic.algebras.concept.core.Concept object at 0x7111f617d0c0>,
 Item(key='Owl', value=<list object at 0x7111f6156880>): <galactic.algebras.concept.core.Concept object at 0x7111f617d0c0>,
 Item(key='Hawk', value=<list object at 0x7111f61568c0>): <galactic.algebras.concept.core.Concept object at 0x7111f617d0c0>,
 Item(key='Eagle', value=<list object at 0x7111f6156900>): <galactic.algebras.concept.core.Concept object at 0x7111f617d0c0>,
 Item(key='Fox', value=<list object at 0x7111f6156940>): <galactic.algebras.concept.core.Concept object at 0x7111f61bb9c0>,
 Item(key='Dog', value=<list object at 0x7111f6156980>): <galactic.algebras.concept.core.Concept object at 0x7111f61bb9c0>,
 Item(key='Wolf', value=<list object at 0x7111f61569c0>): <galactic.algebras.concept.core.Concept object at 0x7111f61bb9c0>,
 Item(key='Cat', value=<list object at 0x7111f6156a00>): <galactic.algebras.concept.core.Concept object at 0x7111f61bbe80>,
 Item(key='Tiger', value=<list object at 0x7111f6156a40>): <galactic.algebras.concept.core.Concept object at 0x7111f61c9540>,
 Item(key='Lion', value=<list object at 0x7111f6156a80>): <galactic.algebras.concept.core.Concept object at 0x7111f61c9540>,
 Item(key='Horse', value=<list object at 0x7111f6156ac0>): <galactic.algebras.concept.core.Concept object at 0x7111f61c9540>,
 Item(key='Zebra', value=<list object at 0x7111f6156b00>): <galactic.algebras.concept.core.Concept object at 0x7111f61c9540>,
 Item(key='Cow', value=<list object at 0x7111f6156b40>): <galactic.algebras.concept.core.Concept object at 0x7111f6cc2780>}

{<function small at 0x7111f61502c0>: <galactic.algebras.concept.core.Concept object at 0x7111f61c80c0>,
 <function hunt at 0x7111f6153920>: <galactic.algebras.concept.core.Concept object at 0x7111f61c80c0>,
 <function medium at 0x7111f6151a80>: <galactic.algebras.concept.core.Concept object at 0x7111f61c8100>,
 <function big at 0x7111f6151bc0>: <galactic.algebras.concept.core.Concept object at 0x7111f6cc30c0>,
 <function fly at 0x7111f6152de0>: <galactic.algebras.concept.core.Concept object at 0x7111f6cc30c0>,
 <function swim at 0x7111f61531a0>: <galactic.algebras.concept.core.Concept object at 0x7111f6cc30c0>,
 <function mane at 0x7111f6153ce0>: <galactic.algebras.concept.core.Concept object at 0x7111f6cc30c0>,
 <function hooves at 0x7111f616c0e0>: <galactic.algebras.concept.core.Concept object at 0x7111f6cc30c0>,
 <function twolegs at 0x7111f6151f80>: <galactic.algebras.concept.core.Concept object at 0x7111f61c8180>,
 <function feathers at 0x7111f6151760>: <galactic.algebras.concept.core.Concept object at 0x7111f61c8180>,
 <function fourlegs at 0x7111f6152340>: <galactic.algebras.concept.core.Concept object at 0x7111f61c8280>,
 <function hair at 0x7111f6152700>: <galactic.algebras.concept.core.Concept object at 0x7111f61c8280>,
 <function run at 0x7111f6153560>: <galactic.algebras.concept.core.Concept object at 0x7111f61c8280>}

Views of concept lattices#

The ItemFamily class and the AttrFamily class of the galactic.algebras.concept.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 ItemFamily, AttrFamily
item_family = ItemFamily(lattice)
attr_family = AttrFamily(lattice)
display(
    item_family,
    list(item_family),
    list(list(str(item) for item in closed) for closed in item_family),
)
display(
    attr_family,
    list(attr_family),
    list(list(str(attr) for attr in closed) for closed in attr_family),
)

<galactic.algebras.concept.core.ItemFamily object at 0x7111f6159e40>

[<galactic.algebras.concept.core.Extent object at 0x7111f618aa00>,
 <galactic.algebras.concept.core.Extent object at 0x7111f61dee40>,
 <galactic.algebras.concept.core.Extent object at 0x7111f61dedc0>,
 <galactic.algebras.concept.core.Extent object at 0x7111f6cb7040>,
 <galactic.algebras.concept.core.Extent object at 0x7111f61deec0>,
 <galactic.algebras.concept.core.Extent object at 0x7111f61def80>]

[[],
 ['Dove', 'Hen', 'Duck', 'Goose', 'Owl', 'Hawk', 'Eagle'],
 ['Cat'],
 ['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']]

<galactic.algebras.concept.core.AttrFamily object at 0x7111f61598a0>

[<galactic.algebras.concept.core.Intent object at 0x7111f617fbc0>,
 <galactic.algebras.concept.core.Intent object at 0x7111f61ec040>,
 <galactic.algebras.concept.core.Intent object at 0x7111f61df780>,
 <galactic.algebras.concept.core.Intent object at 0x7111f61ac7c0>,
 <galactic.algebras.concept.core.Intent object at 0x7111f61ec080>,
 <galactic.algebras.concept.core.Intent object at 0x7111f61ec0c0>]

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