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

[<galactic.algebras.concept.core.Concept object at 0x7c630c757180>,
 <galactic.algebras.concept.core.Concept object at 0x7c630c79d400>,
 <galactic.algebras.concept.core.Concept object at 0x7c630c79d340>,
 <galactic.algebras.concept.core.Concept object at 0x7c630c79d300>]

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

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

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

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

[<galactic.algebras.concept.core.Concept object at 0x7c630c7afd40>,
 <galactic.algebras.concept.core.Concept object at 0x7c630c7c9a00>,
 <galactic.algebras.concept.core.Concept object at 0x7c630c7cb700>,
 <galactic.algebras.concept.core.Concept object at 0x7c630c7cb680>,
 <galactic.algebras.concept.core.Concept object at 0x7c630c7cb940>,
 <galactic.algebras.concept.core.Concept object at 0x7c630c7c9900>]

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

[<galactic.algebras.concept.core.Concept object at 0x7c630c747240>,
 <galactic.algebras.concept.core.Concept object at 0x7c630c7ded00>,
 <galactic.algebras.concept.core.Concept object at 0x7c630c7deb80>,
 <galactic.algebras.concept.core.Concept object at 0x7c630c7deb00>,
 <galactic.algebras.concept.core.Concept object at 0x7c630c7ded40>,
 <galactic.algebras.concept.core.Concept object at 0x7c630c7dedc0>]

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

[]

[]

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

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

['Cat']

['twolegs', 'feathers']

{Item(key='Dove', value=<list object at 0x7c630c756940>): <galactic.algebras.concept.core.Concept object at 0x7c630c7ad4c0>,
 Item(key='Hen', value=<list object at 0x7c630c76e880>): <galactic.algebras.concept.core.Concept object at 0x7c630c7ad4c0>,
 Item(key='Duck', value=<list object at 0x7c630c76e8c0>): <galactic.algebras.concept.core.Concept object at 0x7c630c7ad4c0>,
 Item(key='Goose', value=<list object at 0x7c630c76e900>): <galactic.algebras.concept.core.Concept object at 0x7c630c7ad4c0>,
 Item(key='Owl', value=<list object at 0x7c630c76e940>): <galactic.algebras.concept.core.Concept object at 0x7c630c7ad4c0>,
 Item(key='Hawk', value=<list object at 0x7c630c76e980>): <galactic.algebras.concept.core.Concept object at 0x7c630c7ad4c0>,
 Item(key='Eagle', value=<list object at 0x7c630c76e9c0>): <galactic.algebras.concept.core.Concept object at 0x7c630c7ad4c0>,
 Item(key='Fox', value=<list object at 0x7c630c76ea00>): <galactic.algebras.concept.core.Concept object at 0x7c630c7df440>,
 Item(key='Dog', value=<list object at 0x7c630c76ea40>): <galactic.algebras.concept.core.Concept object at 0x7c630c7df440>,
 Item(key='Wolf', value=<list object at 0x7c630c76ea80>): <galactic.algebras.concept.core.Concept object at 0x7c630c7df440>,
 Item(key='Cat', value=<list object at 0x7c630c76eac0>): <galactic.algebras.concept.core.Concept object at 0x7c630c7de440>,
 Item(key='Tiger', value=<list object at 0x7c630c76eb00>): <galactic.algebras.concept.core.Concept object at 0x7c630c7e92c0>,
 Item(key='Lion', value=<list object at 0x7c630c76eb40>): <galactic.algebras.concept.core.Concept object at 0x7c630c7e92c0>,
 Item(key='Horse', value=<list object at 0x7c630c76eb80>): <galactic.algebras.concept.core.Concept object at 0x7c630c7e92c0>,
 Item(key='Zebra', value=<list object at 0x7c630c76ebc0>): <galactic.algebras.concept.core.Concept object at 0x7c630c7e92c0>,
 Item(key='Cow', value=<list object at 0x7c630c76ec00>): <galactic.algebras.concept.core.Concept object at 0x7c63161d6e40>}

{<function small at 0x7c630c76a840>: <galactic.algebras.concept.core.Concept object at 0x7c630c7dcbc0>,
 <function hunt at 0x7c630c785ee0>: <galactic.algebras.concept.core.Concept object at 0x7c630c7dcbc0>,
 <function medium at 0x7c630c784040>: <galactic.algebras.concept.core.Concept object at 0x7c630c7dd340>,
 <function big at 0x7c630c784180>: <galactic.algebras.concept.core.Concept object at 0x7c63161d65c0>,
 <function fly at 0x7c630c7853a0>: <galactic.algebras.concept.core.Concept object at 0x7c63161d65c0>,
 <function swim at 0x7c630c785760>: <galactic.algebras.concept.core.Concept object at 0x7c63161d65c0>,
 <function mane at 0x7c630c7862a0>: <galactic.algebras.concept.core.Concept object at 0x7c63161d65c0>,
 <function hooves at 0x7c630c786660>: <galactic.algebras.concept.core.Concept object at 0x7c63161d65c0>,
 <function twolegs at 0x7c630c784540>: <galactic.algebras.concept.core.Concept object at 0x7c630c7dd400>,
 <function feathers at 0x7c630c76bce0>: <galactic.algebras.concept.core.Concept object at 0x7c630c7dd400>,
 <function fourlegs at 0x7c630c784900>: <galactic.algebras.concept.core.Concept object at 0x7c630c7ddac0>,
 <function hair at 0x7c630c784cc0>: <galactic.algebras.concept.core.Concept object at 0x7c630c7ddac0>,
 <function run at 0x7c630c785b20>: <galactic.algebras.concept.core.Concept object at 0x7c630c7ddac0>}

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

[<galactic.algebras.concept.core.Extent object at 0x7c630c7ac7c0>,
 <galactic.algebras.concept.core.Extent object at 0x7c630c5fec80>,
 <galactic.algebras.concept.core.Extent object at 0x7c630c5feac0>,
 <galactic.algebras.concept.core.Extent object at 0x7c630c5fea00>,
 <galactic.algebras.concept.core.Extent object at 0x7c630c5fed00>,
 <galactic.algebras.concept.core.Extent object at 0x7c630c5fedc0>]

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

[<galactic.algebras.concept.core.Intent object at 0x7c630c7acb40>,
 <galactic.algebras.concept.core.Intent object at 0x7c630c5ff5c0>,
 <galactic.algebras.concept.core.Intent object at 0x7c630c5fe900>,
 <galactic.algebras.concept.core.Intent object at 0x7c630c5fe980>,
 <galactic.algebras.concept.core.Intent object at 0x7c630c5ffb80>,
 <galactic.algebras.concept.core.Intent object at 0x7c630c5ff3c0>]

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