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

[<galactic.algebras.concept.core.Concept object at 0x7d96c6b07780>,
 <galactic.algebras.concept.core.Concept object at 0x7d96c6b16c00>,
 <galactic.algebras.concept.core.Concept object at 0x7d96c729e740>,
 <galactic.algebras.concept.core.Concept object at 0x7d96c6b16b40>]

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

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

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

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

[<galactic.algebras.concept.core.Concept object at 0x7d96c6b45940>,
 <galactic.algebras.concept.core.Concept object at 0x7d96c6b51940>,
 <galactic.algebras.concept.core.Concept object at 0x7d96c6b2ab40>,
 <galactic.algebras.concept.core.Concept object at 0x7d96c6b45140>,
 <galactic.algebras.concept.core.Concept object at 0x7d96c6b51980>,
 <galactic.algebras.concept.core.Concept object at 0x7d96c6b51800>]

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

[<galactic.algebras.concept.core.Concept object at 0x7d96c6c79fc0>,
 <galactic.algebras.concept.core.Concept object at 0x7d96c6c7fdc0>,
 <galactic.algebras.concept.core.Concept object at 0x7d96c6c7f680>,
 <galactic.algebras.concept.core.Concept object at 0x7d96c6c7f7c0>,
 <galactic.algebras.concept.core.Concept object at 0x7d96c6c7fb80>,
 <galactic.algebras.concept.core.Concept object at 0x7d96c72adac0>]

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

[]

[]

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

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

['Cat']

['twolegs', 'feathers']

{Item(key='Dove', value=<list object at 0x7d96c6ae7a80>): <galactic.algebras.concept.core.Concept object at 0x7d96c6b46240>,
 Item(key='Hen', value=<list object at 0x7d96c6ae7dc0>): <galactic.algebras.concept.core.Concept object at 0x7d96c6b46240>,
 Item(key='Duck', value=<list object at 0x7d96c6ae7ac0>): <galactic.algebras.concept.core.Concept object at 0x7d96c6b46240>,
 Item(key='Goose', value=<list object at 0x7d96c6ae7e00>): <galactic.algebras.concept.core.Concept object at 0x7d96c6b46240>,
 Item(key='Owl', value=<list object at 0x7d96c6ae7e40>): <galactic.algebras.concept.core.Concept object at 0x7d96c6b46240>,
 Item(key='Hawk', value=<list object at 0x7d96c6ae7e80>): <galactic.algebras.concept.core.Concept object at 0x7d96c6b46240>,
 Item(key='Eagle', value=<list object at 0x7d96c6ae7ec0>): <galactic.algebras.concept.core.Concept object at 0x7d96c6b46240>,
 Item(key='Fox', value=<list object at 0x7d96c6ae7f00>): <galactic.algebras.concept.core.Concept object at 0x7d96c72ba840>,
 Item(key='Dog', value=<list object at 0x7d96c6ae7f40>): <galactic.algebras.concept.core.Concept object at 0x7d96c72ba840>,
 Item(key='Wolf', value=<list object at 0x7d96c6ae7f80>): <galactic.algebras.concept.core.Concept object at 0x7d96c72ba840>,
 Item(key='Cat', value=<list object at 0x7d96c6ae7fc0>): <galactic.algebras.concept.core.Concept object at 0x7d96c6b52fc0>,
 Item(key='Tiger', value=<list object at 0x7d96c6b04040>): <galactic.algebras.concept.core.Concept object at 0x7d96c6b167c0>,
 Item(key='Lion', value=<list object at 0x7d96c6b04080>): <galactic.algebras.concept.core.Concept object at 0x7d96c6b167c0>,
 Item(key='Horse', value=<list object at 0x7d96c6b040c0>): <galactic.algebras.concept.core.Concept object at 0x7d96c6b167c0>,
 Item(key='Zebra', value=<list object at 0x7d96c6b04100>): <galactic.algebras.concept.core.Concept object at 0x7d96c6b167c0>,
 Item(key='Cow', value=<list object at 0x7d96c6b04140>): <galactic.algebras.concept.core.Concept object at 0x7d96c6b44240>}

{<function small at 0x7d96c72ab100>: <galactic.algebras.concept.core.Concept object at 0x7d96c6b53640>,
 <function hunt at 0x7d96c6b09f80>: <galactic.algebras.concept.core.Concept object at 0x7d96c6b53640>,
 <function medium at 0x7d96c6b080e0>: <galactic.algebras.concept.core.Concept object at 0x7d96c6b53000>,
 <function big at 0x7d96c6b08220>: <galactic.algebras.concept.core.Concept object at 0x7d96c6b44300>,
 <function fly at 0x7d96c6b09440>: <galactic.algebras.concept.core.Concept object at 0x7d96c6b44300>,
 <function swim at 0x7d96c6b09800>: <galactic.algebras.concept.core.Concept object at 0x7d96c6b44300>,
 <function mane at 0x7d96c6b0a340>: <galactic.algebras.concept.core.Concept object at 0x7d96c6b44300>,
 <function hooves at 0x7d96c6b0a700>: <galactic.algebras.concept.core.Concept object at 0x7d96c6b44300>,
 <function twolegs at 0x7d96c6b085e0>: <galactic.algebras.concept.core.Concept object at 0x7d96c6b52f80>,
 <function feathers at 0x7d96c6ae2c00>: <galactic.algebras.concept.core.Concept object at 0x7d96c6b52f80>,
 <function fourlegs at 0x7d96c6b089a0>: <galactic.algebras.concept.core.Concept object at 0x7d96c6b52d00>,
 <function hair at 0x7d96c6b08d60>: <galactic.algebras.concept.core.Concept object at 0x7d96c6b52d00>,
 <function run at 0x7d96c6b09bc0>: <galactic.algebras.concept.core.Concept object at 0x7d96c6b52d00>}

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

[<galactic.algebras.concept.core.Extent object at 0x7d96c6b44080>,
 <galactic.algebras.concept.core.Extent object at 0x7d96c6950140>,
 <galactic.algebras.concept.core.Extent object at 0x7d96c72b81c0>,
 <galactic.algebras.concept.core.Extent object at 0x7d96c6b6bec0>,
 <galactic.algebras.concept.core.Extent object at 0x7d96c69501c0>,
 <galactic.algebras.concept.core.Extent object at 0x7d96c6950280>]

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

[<galactic.algebras.concept.core.Intent object at 0x7d96c6b44100>,
 <galactic.algebras.concept.core.Intent object at 0x7d96c6950bc0>,
 <galactic.algebras.concept.core.Intent object at 0x7d96c6950980>,
 <galactic.algebras.concept.core.Intent object at 0x7d96c6b6bdc0>,
 <galactic.algebras.concept.core.Intent object at 0x7d96c6950d00>,
 <galactic.algebras.concept.core.Intent object at 0x7d96c6950ac0>]

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