📘 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 0x7cd3da2194e0>

[<galactic.algebras.concept.core.Concept object at 0x7cd3da1cb1c0>,
 <galactic.algebras.concept.core.Concept object at 0x7cd3d96c8740>,
 <galactic.algebras.concept.core.Concept object at 0x7cd3d9698140>,
 <galactic.algebras.concept.core.Concept object at 0x7cd3d96c8680>]

[[],
 ['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 0x7cd3d96a0e50>

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

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

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

[<galactic.algebras.concept.core.Concept object at 0x7cd3d96dbb80>,
 <galactic.algebras.concept.core.Concept object at 0x7cd3d96e9d80>,
 <galactic.algebras.concept.core.Concept object at 0x7cd3d96ebb80>,
 <galactic.algebras.concept.core.Concept object at 0x7cd3d96ebc80>,
 <galactic.algebras.concept.core.Concept object at 0x7cd3d96e9d40>,
 <galactic.algebras.concept.core.Concept object at 0x7cd3d96e9b80>]

[[],
 ['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 0x7cd3d96a1030>

[<galactic.algebras.concept.core.Concept object at 0x7cd3d96d9040>,
 <galactic.algebras.concept.core.Concept object at 0x7cd3d96f9800>,
 <galactic.algebras.concept.core.Concept object at 0x7cd3d96f9f80>,
 <galactic.algebras.concept.core.Concept object at 0x7cd3d96fa0c0>,
 <galactic.algebras.concept.core.Concept object at 0x7cd3d96f9680>,
 <galactic.algebras.concept.core.Concept object at 0x7cd3d96b88c0>]

[[],
 ['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 0x7cd3d96a1120>

[]

[]

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 0x7cd3da1c66c0>

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

['Cat']

['twolegs', 'feathers']

{Item(key='Dove', value=<tuple object at 0x7cd3da1a20c0>): <galactic.algebras.concept.core.Concept object at 0x7cd3da1ea340>,
 Item(key='Hen', value=<tuple object at 0x7cd3da1c1140>): <galactic.algebras.concept.core.Concept object at 0x7cd3da1ea340>,
 Item(key='Duck', value=<tuple object at 0x7cd3d96a8b30>): <galactic.algebras.concept.core.Concept object at 0x7cd3da1ea340>,
 Item(key='Goose', value=<tuple object at 0x7cd3d96a8b30>): <galactic.algebras.concept.core.Concept object at 0x7cd3da1ea340>,
 Item(key='Owl', value=<tuple object at 0x7cd3d96a8c20>): <galactic.algebras.concept.core.Concept object at 0x7cd3da1ea340>,
 Item(key='Hawk', value=<tuple object at 0x7cd3d96a8c20>): <galactic.algebras.concept.core.Concept object at 0x7cd3da1ea340>,
 Item(key='Eagle', value=<tuple object at 0x7cd3d96a8c70>): <galactic.algebras.concept.core.Concept object at 0x7cd3da1ea340>,
 Item(key='Fox', value=<tuple object at 0x7cd3d96a8cc0>): <galactic.algebras.concept.core.Concept object at 0x7cd3d96fe8c0>,
 Item(key='Dog', value=<tuple object at 0x7cd3da1a22f0>): <galactic.algebras.concept.core.Concept object at 0x7cd3d96fe8c0>,
 Item(key='Wolf', value=<tuple object at 0x7cd3da170b80>): <galactic.algebras.concept.core.Concept object at 0x7cd3d96fe8c0>,
 Item(key='Cat', value=<tuple object at 0x7cd3d96a8d10>): <galactic.algebras.concept.core.Concept object at 0x7cd3d96fec00>,
 Item(key='Tiger', value=<tuple object at 0x7cd3d96a8d60>): <galactic.algebras.concept.core.Concept object at 0x7cd3d9714440>,
 Item(key='Lion', value=<tuple object at 0x7cd3d9671a80>): <galactic.algebras.concept.core.Concept object at 0x7cd3d9714440>,
 Item(key='Horse', value=<tuple object at 0x7cd3d96733a0>): <galactic.algebras.concept.core.Concept object at 0x7cd3d9714440>,
 Item(key='Zebra', value=<tuple object at 0x7cd3d96733a0>): <galactic.algebras.concept.core.Concept object at 0x7cd3d9714440>,
 Item(key='Cow', value=<tuple object at 0x7cd3f38d30b0>): <galactic.algebras.concept.core.Concept object at 0x7cd3da1eb000>}

{<function small at 0x7cd3d9690ae0>: <galactic.algebras.concept.core.Concept object at 0x7cd3d96fed00>,
 <function hunt at 0x7cd3d96b0220>: <galactic.algebras.concept.core.Concept object at 0x7cd3d96fed00>,
 <function medium at 0x7cd3d9692340>: <galactic.algebras.concept.core.Concept object at 0x7cd3d96fee00>,
 <function big at 0x7cd3d9692480>: <galactic.algebras.concept.core.Concept object at 0x7cd3da1eb940>,
 <function fly at 0x7cd3d96936a0>: <galactic.algebras.concept.core.Concept object at 0x7cd3da1eb940>,
 <function swim at 0x7cd3d9693a60>: <galactic.algebras.concept.core.Concept object at 0x7cd3da1eb940>,
 <function mane at 0x7cd3d96b05e0>: <galactic.algebras.concept.core.Concept object at 0x7cd3da1eb940>,
 <function hooves at 0x7cd3d96b09a0>: <galactic.algebras.concept.core.Concept object at 0x7cd3da1eb940>,
 <function twolegs at 0x7cd3d9692840>: <galactic.algebras.concept.core.Concept object at 0x7cd3d96fee80>,
 <function feathers at 0x7cd3d9692020>: <galactic.algebras.concept.core.Concept object at 0x7cd3d96fee80>,
 <function fourlegs at 0x7cd3d9692c00>: <galactic.algebras.concept.core.Concept object at 0x7cd3d96fef80>,
 <function hair at 0x7cd3d9692fc0>: <galactic.algebras.concept.core.Concept object at 0x7cd3d96fef80>,
 <function run at 0x7cd3d9693e20>: <galactic.algebras.concept.core.Concept object at 0x7cd3d96fef80>}

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 0x7cd3d96a17b0>

[<galactic.algebras.concept.core.Extent object at 0x7cd3da1eb800>,
 <galactic.algebras.concept.core.Extent object at 0x7cd3d971e000>,
 <galactic.algebras.concept.core.Extent object at 0x7cd3d96c9a00>,
 <galactic.algebras.concept.core.Extent object at 0x7cd3d96f8080>,
 <galactic.algebras.concept.core.Extent object at 0x7cd3d971e040>,
 <galactic.algebras.concept.core.Extent object at 0x7cd3d971e100>]

[[],
 ['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 0x7cd3d96a1210>

[<galactic.algebras.concept.core.Intent object at 0x7cd3da1eacc0>,
 <galactic.algebras.concept.core.Intent object at 0x7cd3d971f080>,
 <galactic.algebras.concept.core.Intent object at 0x7cd3d971dd00>,
 <galactic.algebras.concept.core.Intent object at 0x7cd3d971dd80>,
 <galactic.algebras.concept.core.Intent object at 0x7cd3d971ec40>,
 <galactic.algebras.concept.core.Intent object at 0x7cd3d971ebc0>]

[['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'],
 []]