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

[<galactic.algebras.concept.core.Concept object at 0x764f585356c0>,
 <galactic.algebras.concept.core.Concept object at 0x764f5841c680>,
 <galactic.algebras.concept.core.Concept object at 0x764f5841c5c0>,
 <galactic.algebras.concept.core.Concept object at 0x764f5841c580>]

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

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

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

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

[<galactic.algebras.concept.core.Concept object at 0x764f5842ad40>,
 <galactic.algebras.concept.core.Concept object at 0x764f5842bb80>,
 <galactic.algebras.concept.core.Concept object at 0x764f58429b00>,
 <galactic.algebras.concept.core.Concept object at 0x764f5842b180>,
 <galactic.algebras.concept.core.Concept object at 0x764f5842be00>,
 <galactic.algebras.concept.core.Concept object at 0x764f5842b700>]

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

[<galactic.algebras.concept.core.Concept object at 0x764f5842a1c0>,
 <galactic.algebras.concept.core.Concept object at 0x764f584523c0>,
 <galactic.algebras.concept.core.Concept object at 0x764f58452240>,
 <galactic.algebras.concept.core.Concept object at 0x764f584521c0>,
 <galactic.algebras.concept.core.Concept object at 0x764f58452400>,
 <galactic.algebras.concept.core.Concept object at 0x764f58452480>]

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

[]

[]

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

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

['Cat']

['twolegs', 'feathers']

{Item(key='Dove', value=<list object at 0x764f585e1480>): <galactic.algebras.concept.core.Concept object at 0x764f61e8db80>,
 Item(key='Hen', value=<list object at 0x764f585e18c0>): <galactic.algebras.concept.core.Concept object at 0x764f61e8db80>,
 Item(key='Duck', value=<list object at 0x764f585e1900>): <galactic.algebras.concept.core.Concept object at 0x764f61e8db80>,
 Item(key='Goose', value=<list object at 0x764f585e1940>): <galactic.algebras.concept.core.Concept object at 0x764f61e8db80>,
 Item(key='Owl', value=<list object at 0x764f585e1980>): <galactic.algebras.concept.core.Concept object at 0x764f61e8db80>,
 Item(key='Hawk', value=<list object at 0x764f585e19c0>): <galactic.algebras.concept.core.Concept object at 0x764f61e8db80>,
 Item(key='Eagle', value=<list object at 0x764f585e1a00>): <galactic.algebras.concept.core.Concept object at 0x764f61e8db80>,
 Item(key='Fox', value=<list object at 0x764f585e1a40>): <galactic.algebras.concept.core.Concept object at 0x764f58429e40>,
 Item(key='Dog', value=<list object at 0x764f585e1a80>): <galactic.algebras.concept.core.Concept object at 0x764f58429e40>,
 Item(key='Wolf', value=<list object at 0x764f585e1ac0>): <galactic.algebras.concept.core.Concept object at 0x764f58429e40>,
 Item(key='Cat', value=<list object at 0x764f585e1b00>): <galactic.algebras.concept.core.Concept object at 0x764f58453a80>,
 Item(key='Tiger', value=<list object at 0x764f585e1b40>): <galactic.algebras.concept.core.Concept object at 0x764f58464ac0>,
 Item(key='Lion', value=<list object at 0x764f585e1b80>): <galactic.algebras.concept.core.Concept object at 0x764f58464ac0>,
 Item(key='Horse', value=<list object at 0x764f585e1bc0>): <galactic.algebras.concept.core.Concept object at 0x764f58464ac0>,
 Item(key='Zebra', value=<list object at 0x764f585e1c00>): <galactic.algebras.concept.core.Concept object at 0x764f58464ac0>,
 Item(key='Cow', value=<list object at 0x764f585e1c40>): <galactic.algebras.concept.core.Concept object at 0x764f58730580>}

{<function small at 0x764f585a7880>: <galactic.algebras.concept.core.Concept object at 0x764f58452680>,
 <function hunt at 0x764f585eab60>: <galactic.algebras.concept.core.Concept object at 0x764f58452680>,
 <function medium at 0x764f585e8cc0>: <galactic.algebras.concept.core.Concept object at 0x764f58452980>,
 <function big at 0x764f585e8e00>: <galactic.algebras.concept.core.Concept object at 0x764f58733b00>,
 <function fly at 0x764f585ea020>: <galactic.algebras.concept.core.Concept object at 0x764f58733b00>,
 <function swim at 0x764f585ea3e0>: <galactic.algebras.concept.core.Concept object at 0x764f58733b00>,
 <function mane at 0x764f585eaf20>: <galactic.algebras.concept.core.Concept object at 0x764f58733b00>,
 <function hooves at 0x764f585eb2e0>: <galactic.algebras.concept.core.Concept object at 0x764f58733b00>,
 <function twolegs at 0x764f585e91c0>: <galactic.algebras.concept.core.Concept object at 0x764f58452700>,
 <function feathers at 0x764f585d77e0>: <galactic.algebras.concept.core.Concept object at 0x764f58452700>,
 <function fourlegs at 0x764f585e9580>: <galactic.algebras.concept.core.Concept object at 0x764f584507c0>,
 <function hair at 0x764f585e9940>: <galactic.algebras.concept.core.Concept object at 0x764f584507c0>,
 <function run at 0x764f585ea7a0>: <galactic.algebras.concept.core.Concept object at 0x764f584507c0>}

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

[<galactic.algebras.concept.core.Extent object at 0x764f5871f740>,
 <galactic.algebras.concept.core.Extent object at 0x764f5846e300>,
 <galactic.algebras.concept.core.Extent object at 0x764f5846e280>,
 <galactic.algebras.concept.core.Extent object at 0x764f584186c0>,
 <galactic.algebras.concept.core.Extent object at 0x764f5846e380>,
 <galactic.algebras.concept.core.Extent object at 0x764f5846e440>]

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

[<galactic.algebras.concept.core.Intent object at 0x764f5871ff40>,
 <galactic.algebras.concept.core.Intent object at 0x764f5846e840>,
 <galactic.algebras.concept.core.Intent object at 0x764f5846dfc0>,
 <galactic.algebras.concept.core.Intent object at 0x764f58418d00>,
 <galactic.algebras.concept.core.Intent object at 0x764f5846f040>,
 <galactic.algebras.concept.core.Intent object at 0x764f5846ef00>]

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