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

[<galactic.algebras.concept.core.Concept object at 0x7e76dc11fd80>,
 <galactic.algebras.concept.core.Concept object at 0x7e76d44f8200>,
 <galactic.algebras.concept.core.Concept object at 0x7e76d44f8140>,
 <galactic.algebras.concept.core.Concept object at 0x7e76d44f8100>]

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

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

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

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

[<galactic.algebras.concept.core.Concept object at 0x7e76d450a980>,
 <galactic.algebras.concept.core.Concept object at 0x7e76d4509280>,
 <galactic.algebras.concept.core.Concept object at 0x7e76d450ac80>,
 <galactic.algebras.concept.core.Concept object at 0x7e76d450ab40>,
 <galactic.algebras.concept.core.Concept object at 0x7e76d4509ec0>,
 <galactic.algebras.concept.core.Concept object at 0x7e76d450b900>]

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

[<galactic.algebras.concept.core.Concept object at 0x7e76d4318800>,
 <galactic.algebras.concept.core.Concept object at 0x7e76d4335c00>,
 <galactic.algebras.concept.core.Concept object at 0x7e76d4335a40>,
 <galactic.algebras.concept.core.Concept object at 0x7e76d43246c0>,
 <galactic.algebras.concept.core.Concept object at 0x7e76d4335c40>,
 <galactic.algebras.concept.core.Concept object at 0x7e76d4335cc0>]

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

[]

[]

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

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

['Cat']

['twolegs', 'feathers']

{Item(key='Dove', value=<list object at 0x7e76d44c8f00>): <galactic.algebras.concept.core.Concept object at 0x7e76dc11f240>,
 Item(key='Hen', value=<list object at 0x7e76d44c9240>): <galactic.algebras.concept.core.Concept object at 0x7e76dc11f240>,
 Item(key='Duck', value=<list object at 0x7e76d44c9280>): <galactic.algebras.concept.core.Concept object at 0x7e76dc11f240>,
 Item(key='Goose', value=<list object at 0x7e76d44c92c0>): <galactic.algebras.concept.core.Concept object at 0x7e76dc11f240>,
 Item(key='Owl', value=<list object at 0x7e76d44c9300>): <galactic.algebras.concept.core.Concept object at 0x7e76dc11f240>,
 Item(key='Hawk', value=<list object at 0x7e76d44c9340>): <galactic.algebras.concept.core.Concept object at 0x7e76dc11f240>,
 Item(key='Eagle', value=<list object at 0x7e76d44c9380>): <galactic.algebras.concept.core.Concept object at 0x7e76dc11f240>,
 Item(key='Fox', value=<list object at 0x7e76d44c93c0>): <galactic.algebras.concept.core.Concept object at 0x7e76d431b040>,
 Item(key='Dog', value=<list object at 0x7e76d44c9400>): <galactic.algebras.concept.core.Concept object at 0x7e76d431b040>,
 Item(key='Wolf', value=<list object at 0x7e76d44c9440>): <galactic.algebras.concept.core.Concept object at 0x7e76d431b040>,
 Item(key='Cat', value=<list object at 0x7e76d44c9480>): <galactic.algebras.concept.core.Concept object at 0x7e76d4324f80>,
 Item(key='Tiger', value=<list object at 0x7e76d44c94c0>): <galactic.algebras.concept.core.Concept object at 0x7e76d4344340>,
 Item(key='Lion', value=<list object at 0x7e76d44c9500>): <galactic.algebras.concept.core.Concept object at 0x7e76d4344340>,
 Item(key='Horse', value=<list object at 0x7e76d44c9540>): <galactic.algebras.concept.core.Concept object at 0x7e76d4344340>,
 Item(key='Zebra', value=<list object at 0x7e76d44c9580>): <galactic.algebras.concept.core.Concept object at 0x7e76d4344340>,
 Item(key='Cow', value=<list object at 0x7e76d44c95c0>): <galactic.algebras.concept.core.Concept object at 0x7e76d44e5500>}

{<function small at 0x7e76d448f1a0>: <galactic.algebras.concept.core.Concept object at 0x7e76d4336340>,
 <function hunt at 0x7e76d44ce480>: <galactic.algebras.concept.core.Concept object at 0x7e76d4336340>,
 <function medium at 0x7e76d44cc5e0>: <galactic.algebras.concept.core.Concept object at 0x7e76d4336040>,
 <function big at 0x7e76d44cc720>: <galactic.algebras.concept.core.Concept object at 0x7e76d44e7640>,
 <function fly at 0x7e76d44cd940>: <galactic.algebras.concept.core.Concept object at 0x7e76d44e7640>,
 <function swim at 0x7e76d44cdd00>: <galactic.algebras.concept.core.Concept object at 0x7e76d44e7640>,
 <function mane at 0x7e76d44ce840>: <galactic.algebras.concept.core.Concept object at 0x7e76d44e7640>,
 <function hooves at 0x7e76d44cec00>: <galactic.algebras.concept.core.Concept object at 0x7e76d44e7640>,
 <function twolegs at 0x7e76d44ccae0>: <galactic.algebras.concept.core.Concept object at 0x7e76d4335f80>,
 <function feathers at 0x7e76d44b7100>: <galactic.algebras.concept.core.Concept object at 0x7e76d4335f80>,
 <function fourlegs at 0x7e76d44ccea0>: <galactic.algebras.concept.core.Concept object at 0x7e76d43341c0>,
 <function hair at 0x7e76d44cd260>: <galactic.algebras.concept.core.Concept object at 0x7e76d43341c0>,
 <function run at 0x7e76d44ce0c0>: <galactic.algebras.concept.core.Concept object at 0x7e76d43341c0>}

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

[<galactic.algebras.concept.core.Extent object at 0x7e76dc3531c0>,
 <galactic.algebras.concept.core.Extent object at 0x7e76d4351bc0>,
 <galactic.algebras.concept.core.Extent object at 0x7e76d4351a00>,
 <galactic.algebras.concept.core.Extent object at 0x7e76d4351940>,
 <galactic.algebras.concept.core.Extent object at 0x7e76d4351c40>,
 <galactic.algebras.concept.core.Extent object at 0x7e76d4351d00>]

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

[<galactic.algebras.concept.core.Intent object at 0x7e76d44e74c0>,
 <galactic.algebras.concept.core.Intent object at 0x7e76d43522c0>,
 <galactic.algebras.concept.core.Intent object at 0x7e76d4351800>,
 <galactic.algebras.concept.core.Intent object at 0x7e76d431aac0>,
 <galactic.algebras.concept.core.Intent object at 0x7e76d4352400>,
 <galactic.algebras.concept.core.Intent object at 0x7e76d4352500>]

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