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

[<galactic.algebras.concept.core.Concept object at 0x7d5296762e00>,
 <galactic.algebras.concept.core.Concept object at 0x7d5296776140>,
 <galactic.algebras.concept.core.Concept object at 0x7d52968b0140>,
 <galactic.algebras.concept.core.Concept object at 0x7d5296776080>]

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

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

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

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

[<galactic.algebras.concept.core.Concept object at 0x7d5296789d00>,
 <galactic.algebras.concept.core.Concept object at 0x7d529679f080>,
 <galactic.algebras.concept.core.Concept object at 0x7d529679f2c0>,
 <galactic.algebras.concept.core.Concept object at 0x7d529725c1c0>,
 <galactic.algebras.concept.core.Concept object at 0x7d529679f1c0>,
 <galactic.algebras.concept.core.Concept object at 0x7d529679e8c0>]

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

[<galactic.algebras.concept.core.Concept object at 0x7d5296762580>,
 <galactic.algebras.concept.core.Concept object at 0x7d52967bad40>,
 <galactic.algebras.concept.core.Concept object at 0x7d52967bb040>,
 <galactic.algebras.concept.core.Concept object at 0x7d52967bb440>,
 <galactic.algebras.concept.core.Concept object at 0x7d52967bad00>,
 <galactic.algebras.concept.core.Concept object at 0x7d52967baac0>]

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

[]

[]

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

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

['Cat']

['twolegs', 'feathers']

{Item(key='Dove', value=<tuple object at 0x7d529724e750>): <galactic.algebras.concept.core.Concept object at 0x7d5296786e00>,
 Item(key='Hen', value=<tuple object at 0x7d529726ea80>): <galactic.algebras.concept.core.Concept object at 0x7d5296786e00>,
 Item(key='Duck', value=<tuple object at 0x7d529674d440>): <galactic.algebras.concept.core.Concept object at 0x7d5296786e00>,
 Item(key='Goose', value=<tuple object at 0x7d529674d440>): <galactic.algebras.concept.core.Concept object at 0x7d5296786e00>,
 Item(key='Owl', value=<tuple object at 0x7d529674d530>): <galactic.algebras.concept.core.Concept object at 0x7d5296786e00>,
 Item(key='Hawk', value=<tuple object at 0x7d529674d530>): <galactic.algebras.concept.core.Concept object at 0x7d5296786e00>,
 Item(key='Eagle', value=<tuple object at 0x7d529674d580>): <galactic.algebras.concept.core.Concept object at 0x7d5296786e00>,
 Item(key='Fox', value=<tuple object at 0x7d529674d5d0>): <galactic.algebras.concept.core.Concept object at 0x7d52967bbd00>,
 Item(key='Dog', value=<tuple object at 0x7d529724e1b0>): <galactic.algebras.concept.core.Concept object at 0x7d52967bbd00>,
 Item(key='Wolf', value=<tuple object at 0x7d529721d180>): <galactic.algebras.concept.core.Concept object at 0x7d52967bbd00>,
 Item(key='Cat', value=<tuple object at 0x7d529674d620>): <galactic.algebras.concept.core.Concept object at 0x7d52967c8200>,
 Item(key='Tiger', value=<tuple object at 0x7d529674d670>): <galactic.algebras.concept.core.Concept object at 0x7d52967c9880>,
 Item(key='Lion', value=<tuple object at 0x7d529671e140>): <galactic.algebras.concept.core.Concept object at 0x7d52967c9880>,
 Item(key='Horse', value=<tuple object at 0x7d529671fa60>): <galactic.algebras.concept.core.Concept object at 0x7d52967c9880>,
 Item(key='Zebra', value=<tuple object at 0x7d529671fa60>): <galactic.algebras.concept.core.Concept object at 0x7d52967c9880>,
 Item(key='Cow', value=<tuple object at 0x7d529724dc10>): <galactic.algebras.concept.core.Concept object at 0x7d529725d040>}

{<function small at 0x7d5296730860>: <galactic.algebras.concept.core.Concept object at 0x7d52967c8400>,
 <function hunt at 0x7d5296764360>: <galactic.algebras.concept.core.Concept object at 0x7d52967c8400>,
 <function medium at 0x7d5296742480>: <galactic.algebras.concept.core.Concept object at 0x7d52967c8440>,
 <function big at 0x7d52967425c0>: <galactic.algebras.concept.core.Concept object at 0x7d529725e980>,
 <function fly at 0x7d52967437e0>: <galactic.algebras.concept.core.Concept object at 0x7d529725e980>,
 <function swim at 0x7d5296743ba0>: <galactic.algebras.concept.core.Concept object at 0x7d529725e980>,
 <function mane at 0x7d5296764720>: <galactic.algebras.concept.core.Concept object at 0x7d529725e980>,
 <function hooves at 0x7d5296764ae0>: <galactic.algebras.concept.core.Concept object at 0x7d529725e980>,
 <function twolegs at 0x7d5296742980>: <galactic.algebras.concept.core.Concept object at 0x7d52967c84c0>,
 <function feathers at 0x7d5296742160>: <galactic.algebras.concept.core.Concept object at 0x7d52967c84c0>,
 <function fourlegs at 0x7d5296742d40>: <galactic.algebras.concept.core.Concept object at 0x7d52967c85c0>,
 <function hair at 0x7d5296743100>: <galactic.algebras.concept.core.Concept object at 0x7d52967c85c0>,
 <function run at 0x7d5296743f60>: <galactic.algebras.concept.core.Concept object at 0x7d52967c85c0>}

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

[<galactic.algebras.concept.core.Extent object at 0x7d5296787d40>,
 <galactic.algebras.concept.core.Extent object at 0x7d52967d3240>,
 <galactic.algebras.concept.core.Extent object at 0x7d52967d3080>,
 <galactic.algebras.concept.core.Extent object at 0x7d52967d2fc0>,
 <galactic.algebras.concept.core.Extent object at 0x7d52967d32c0>,
 <galactic.algebras.concept.core.Extent object at 0x7d52967d3380>]

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

[<galactic.algebras.concept.core.Intent object at 0x7d5296786fc0>,
 <galactic.algebras.concept.core.Intent object at 0x7d52967d3b40>,
 <galactic.algebras.concept.core.Intent object at 0x7d52967d2e80>,
 <galactic.algebras.concept.core.Intent object at 0x7d52967d2f00>,
 <galactic.algebras.concept.core.Intent object at 0x7d52967ec340>,
 <galactic.algebras.concept.core.Intent object at 0x7d52967ec4c0>]

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