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

[<galactic.algebras.concept.core.Concept object at 0x760f8c5c9e00>,
 <galactic.algebras.concept.core.Concept object at 0x760f8c420140>,
 <galactic.algebras.concept.core.Concept object at 0x760f8c73d540>,
 <galactic.algebras.concept.core.Concept object at 0x760f8c420100>]

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

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

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

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

[<galactic.algebras.concept.core.Concept object at 0x760f8c42e7c0>,
 <galactic.algebras.concept.core.Concept object at 0x760f8c42d140>,
 <galactic.algebras.concept.core.Concept object at 0x760f8c42ec80>,
 <galactic.algebras.concept.core.Concept object at 0x760f8c42eb40>,
 <galactic.algebras.concept.core.Concept object at 0x760f8c42dd80>,
 <galactic.algebras.concept.core.Concept object at 0x760f8c42f780>]

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

[<galactic.algebras.concept.core.Concept object at 0x760f8c43f2c0>,
 <galactic.algebras.concept.core.Concept object at 0x760f8c455d80>,
 <galactic.algebras.concept.core.Concept object at 0x760f8c455c00>,
 <galactic.algebras.concept.core.Concept object at 0x760f8c455b80>,
 <galactic.algebras.concept.core.Concept object at 0x760f8c455dc0>,
 <galactic.algebras.concept.core.Concept object at 0x760f8c455e40>]

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

[]

[]

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

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

['Cat']

['twolegs', 'feathers']

{Item(key='Dove', value=<list object at 0x760f8c5e90c0>): <galactic.algebras.concept.core.Concept object at 0x760f8c43fb80>,
 Item(key='Hen', value=<list object at 0x760f8c5e9400>): <galactic.algebras.concept.core.Concept object at 0x760f8c43fb80>,
 Item(key='Duck', value=<list object at 0x760f8c5e9100>): <galactic.algebras.concept.core.Concept object at 0x760f8c43fb80>,
 Item(key='Goose', value=<list object at 0x760f8c5e9440>): <galactic.algebras.concept.core.Concept object at 0x760f8c43fb80>,
 Item(key='Owl', value=<list object at 0x760f8c5e9480>): <galactic.algebras.concept.core.Concept object at 0x760f8c43fb80>,
 Item(key='Hawk', value=<list object at 0x760f8c5e94c0>): <galactic.algebras.concept.core.Concept object at 0x760f8c43fb80>,
 Item(key='Eagle', value=<list object at 0x760f8c5e9500>): <galactic.algebras.concept.core.Concept object at 0x760f8c43fb80>,
 Item(key='Fox', value=<list object at 0x760f8c5e9540>): <galactic.algebras.concept.core.Concept object at 0x760f8c43f300>,
 Item(key='Dog', value=<list object at 0x760f8c5e9580>): <galactic.algebras.concept.core.Concept object at 0x760f8c43f300>,
 Item(key='Wolf', value=<list object at 0x760f8c5e95c0>): <galactic.algebras.concept.core.Concept object at 0x760f8c43f300>,
 Item(key='Cat', value=<list object at 0x760f8c5e9600>): <galactic.algebras.concept.core.Concept object at 0x760f8c43f740>,
 Item(key='Tiger', value=<list object at 0x760f8c5e9640>): <galactic.algebras.concept.core.Concept object at 0x760f8c468480>,
 Item(key='Lion', value=<list object at 0x760f8c5e9680>): <galactic.algebras.concept.core.Concept object at 0x760f8c468480>,
 Item(key='Horse', value=<list object at 0x760f8c5e96c0>): <galactic.algebras.concept.core.Concept object at 0x760f8c468480>,
 Item(key='Zebra', value=<list object at 0x760f8c5e9700>): <galactic.algebras.concept.core.Concept object at 0x760f8c468480>,
 Item(key='Cow', value=<list object at 0x760f8c5e9740>): <galactic.algebras.concept.core.Concept object at 0x760f8c43fdc0>}

{<function small at 0x760f8c5a76a0>: <galactic.algebras.concept.core.Concept object at 0x760f8c448c80>,
 <function hunt at 0x760f8c5ee980>: <galactic.algebras.concept.core.Concept object at 0x760f8c448c80>,
 <function medium at 0x760f8c5ecae0>: <galactic.algebras.concept.core.Concept object at 0x760f8c456040>,
 <function big at 0x760f8c5ecc20>: <galactic.algebras.concept.core.Concept object at 0x760f8c43f400>,
 <function fly at 0x760f8c5ede40>: <galactic.algebras.concept.core.Concept object at 0x760f8c43f400>,
 <function swim at 0x760f8c5ee200>: <galactic.algebras.concept.core.Concept object at 0x760f8c43f400>,
 <function mane at 0x760f8c5eed40>: <galactic.algebras.concept.core.Concept object at 0x760f8c43f400>,
 <function hooves at 0x760f8c5ef100>: <galactic.algebras.concept.core.Concept object at 0x760f8c43f400>,
 <function twolegs at 0x760f8c5ecfe0>: <galactic.algebras.concept.core.Concept object at 0x760f8c456200>,
 <function feathers at 0x760f8c5db600>: <galactic.algebras.concept.core.Concept object at 0x760f8c456200>,
 <function fourlegs at 0x760f8c5ed3a0>: <galactic.algebras.concept.core.Concept object at 0x760f8c4560c0>,
 <function hair at 0x760f8c5ed760>: <galactic.algebras.concept.core.Concept object at 0x760f8c4560c0>,
 <function run at 0x760f8c5ee5c0>: <galactic.algebras.concept.core.Concept object at 0x760f8c4560c0>}

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

[<galactic.algebras.concept.core.Extent object at 0x760f8c6093c0>,
 <galactic.algebras.concept.core.Extent object at 0x760f8c475c40>,
 <galactic.algebras.concept.core.Extent object at 0x760f8c475bc0>,
 <galactic.algebras.concept.core.Extent object at 0x760f9419ee00>,
 <galactic.algebras.concept.core.Extent object at 0x760f8c475cc0>,
 <galactic.algebras.concept.core.Extent object at 0x760f8c475d80>]

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

[<galactic.algebras.concept.core.Intent object at 0x760f8c43fcc0>,
 <galactic.algebras.concept.core.Intent object at 0x760f8c476480>,
 <galactic.algebras.concept.core.Intent object at 0x760f8c476280>,
 <galactic.algebras.concept.core.Intent object at 0x760f8c449180>,
 <galactic.algebras.concept.core.Intent object at 0x760f8c476580>,
 <galactic.algebras.concept.core.Intent object at 0x760f8c476700>]

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