📘 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=connection, items=[context.domain.item(key='Cat')])
dog_concept = Concept(connection=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 0x7ef503183a60>

[<galactic.algebras.concept.core.Concept object at 0x7ef5031ce8c0>,
 <galactic.algebras.concept.core.Concept object at 0x7ef5031e1d40>,
 <galactic.algebras.concept.core.Concept object at 0x7ef5031e1c80>,
 <galactic.algebras.concept.core.Concept object at 0x7ef5031e1c40>]

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

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

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

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

[<galactic.algebras.concept.core.Concept object at 0x7ef5031f6d40>,
 <galactic.algebras.concept.core.Concept object at 0x7ef503214b80>,
 <galactic.algebras.concept.core.Concept object at 0x7ef5031f5480>,
 <galactic.algebras.concept.core.Concept object at 0x7ef5031f5d00>,
 <galactic.algebras.concept.core.Concept object at 0x7ef503214ac0>,
 <galactic.algebras.concept.core.Concept object at 0x7ef503214b40>]

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

[<galactic.algebras.concept.core.Concept object at 0x7ef50320fc80>,
 <galactic.algebras.concept.core.Concept object at 0x7ef5031ec1c0>,
 <galactic.algebras.concept.core.Concept object at 0x7ef5031ee800>,
 <galactic.algebras.concept.core.Concept object at 0x7ef503957fc0>,
 <galactic.algebras.concept.core.Concept object at 0x7ef5031ec200>,
 <galactic.algebras.concept.core.Concept object at 0x7ef5031ec240>]

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

[]

[]

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

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

['Cat']

['twolegs', 'feathers']

{Item(key='Dove', value=<list object at 0x7ef5031b2cc0>): <galactic.algebras.concept.core.Concept object at 0x7ef5031ce440>,
 Item(key='Hen', value=<list object at 0x7ef5031b3000>): <galactic.algebras.concept.core.Concept object at 0x7ef5031ce440>,
 Item(key='Duck', value=<list object at 0x7ef5031b2d00>): <galactic.algebras.concept.core.Concept object at 0x7ef5031ce440>,
 Item(key='Goose', value=<list object at 0x7ef5031b3040>): <galactic.algebras.concept.core.Concept object at 0x7ef5031ce440>,
 Item(key='Owl', value=<list object at 0x7ef5031b3080>): <galactic.algebras.concept.core.Concept object at 0x7ef5031ce440>,
 Item(key='Hawk', value=<list object at 0x7ef5031b30c0>): <galactic.algebras.concept.core.Concept object at 0x7ef5031ce440>,
 Item(key='Eagle', value=<list object at 0x7ef5031b3100>): <galactic.algebras.concept.core.Concept object at 0x7ef5031ce440>,
 Item(key='Fox', value=<list object at 0x7ef5031b3140>): <galactic.algebras.concept.core.Concept object at 0x7ef5032146c0>,
 Item(key='Dog', value=<list object at 0x7ef5031b3180>): <galactic.algebras.concept.core.Concept object at 0x7ef5032146c0>,
 Item(key='Wolf', value=<list object at 0x7ef5031b31c0>): <galactic.algebras.concept.core.Concept object at 0x7ef5032146c0>,
 Item(key='Cat', value=<list object at 0x7ef5031b3200>): <galactic.algebras.concept.core.Concept object at 0x7ef5032143c0>,
 Item(key='Tiger', value=<list object at 0x7ef5031b3240>): <galactic.algebras.concept.core.Concept object at 0x7ef503217a00>,
 Item(key='Lion', value=<list object at 0x7ef5031b3280>): <galactic.algebras.concept.core.Concept object at 0x7ef503217a00>,
 Item(key='Horse', value=<list object at 0x7ef5031b32c0>): <galactic.algebras.concept.core.Concept object at 0x7ef503217a00>,
 Item(key='Zebra', value=<list object at 0x7ef5031b3300>): <galactic.algebras.concept.core.Concept object at 0x7ef503217a00>,
 Item(key='Cow', value=<list object at 0x7ef5031b3340>): <galactic.algebras.concept.core.Concept object at 0x7ef5031cea40>}

{<function small at 0x7ef503368ae0>: <galactic.algebras.concept.core.Concept object at 0x7ef503214d40>,
 <function hunt at 0x7ef5031c6340>: <galactic.algebras.concept.core.Concept object at 0x7ef503214d40>,
 <function medium at 0x7ef5031c44a0>: <galactic.algebras.concept.core.Concept object at 0x7ef503215040>,
 <function big at 0x7ef5031c45e0>: <galactic.algebras.concept.core.Concept object at 0x7ef5031cec40>,
 <function fly at 0x7ef5031c5800>: <galactic.algebras.concept.core.Concept object at 0x7ef5031cec40>,
 <function swim at 0x7ef5031c5bc0>: <galactic.algebras.concept.core.Concept object at 0x7ef5031cec40>,
 <function mane at 0x7ef5031c6700>: <galactic.algebras.concept.core.Concept object at 0x7ef5031cec40>,
 <function hooves at 0x7ef5031c6ac0>: <galactic.algebras.concept.core.Concept object at 0x7ef5031cec40>,
 <function twolegs at 0x7ef5031c49a0>: <galactic.algebras.concept.core.Concept object at 0x7ef503215c40>,
 <function feathers at 0x7ef5031aefc0>: <galactic.algebras.concept.core.Concept object at 0x7ef503215c40>,
 <function fourlegs at 0x7ef5031c4d60>: <galactic.algebras.concept.core.Concept object at 0x7ef503214200>,
 <function hair at 0x7ef5031c5120>: <galactic.algebras.concept.core.Concept object at 0x7ef503214200>,
 <function run at 0x7ef5031c5f80>: <galactic.algebras.concept.core.Concept object at 0x7ef503214200>}

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

[<galactic.algebras.concept.core.Extent object at 0x7ef5031cd680>,
 <galactic.algebras.concept.core.Extent object at 0x7ef50322e140>,
 <galactic.algebras.concept.core.Extent object at 0x7ef5031b0fc0>,
 <galactic.algebras.concept.core.Extent object at 0x7ef50320eb80>,
 <galactic.algebras.concept.core.Extent object at 0x7ef50322f0c0>,
 <galactic.algebras.concept.core.Extent object at 0x7ef50322f100>]

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

[<galactic.algebras.concept.core.Intent object at 0x7ef5031ccd00>,
 <galactic.algebras.concept.core.Intent object at 0x7ef503217b40>,
 <galactic.algebras.concept.core.Intent object at 0x7ef504b5f200>,
 <galactic.algebras.concept.core.Intent object at 0x7ef50394c040>,
 <galactic.algebras.concept.core.Intent object at 0x7ef503214e00>,
 <galactic.algebras.concept.core.Intent object at 0x7ef50322c140>]

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