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

[<galactic.algebras.concept.core.Concept object at 0x745ef4866f80>,
 <galactic.algebras.concept.core.Concept object at 0x745ef43fd480>,
 <galactic.algebras.concept.core.Concept object at 0x745ef43fd3c0>,
 <galactic.algebras.concept.core.Concept object at 0x745ef43fd380>]

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

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

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

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

[<galactic.algebras.concept.core.Concept object at 0x745ef441b000>,
 <galactic.algebras.concept.core.Concept object at 0x745ef4418500>,
 <galactic.algebras.concept.core.Concept object at 0x745ef442c840>,
 <galactic.algebras.concept.core.Concept object at 0x745ef43feb80>,
 <galactic.algebras.concept.core.Concept object at 0x745ef441b480>,
 <galactic.algebras.concept.core.Concept object at 0x745ef441b5c0>]

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

[<galactic.algebras.concept.core.Concept object at 0x745ef4435740>,
 <galactic.algebras.concept.core.Concept object at 0x745ef443ee80>,
 <galactic.algebras.concept.core.Concept object at 0x745ef443ed00>,
 <galactic.algebras.concept.core.Concept object at 0x745ef443ec80>,
 <galactic.algebras.concept.core.Concept object at 0x745ef443eec0>,
 <galactic.algebras.concept.core.Concept object at 0x745ef443ef40>]

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

[]

[]

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

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

['Cat']

['twolegs', 'feathers']

{Item(key='Dove', value=<list object at 0x745ef45fa400>): <galactic.algebras.concept.core.Concept object at 0x745ef5909f40>,
 Item(key='Hen', value=<list object at 0x745ef45fa740>): <galactic.algebras.concept.core.Concept object at 0x745ef5909f40>,
 Item(key='Duck', value=<list object at 0x745ef45fa440>): <galactic.algebras.concept.core.Concept object at 0x745ef5909f40>,
 Item(key='Goose', value=<list object at 0x745ef45fa780>): <galactic.algebras.concept.core.Concept object at 0x745ef5909f40>,
 Item(key='Owl', value=<list object at 0x745ef45fa7c0>): <galactic.algebras.concept.core.Concept object at 0x745ef5909f40>,
 Item(key='Hawk', value=<list object at 0x745ef45fa800>): <galactic.algebras.concept.core.Concept object at 0x745ef5909f40>,
 Item(key='Eagle', value=<list object at 0x745ef45fa840>): <galactic.algebras.concept.core.Concept object at 0x745ef5909f40>,
 Item(key='Fox', value=<list object at 0x745ef45fa880>): <galactic.algebras.concept.core.Concept object at 0x745ef4866e00>,
 Item(key='Dog', value=<list object at 0x745ef45fa8c0>): <galactic.algebras.concept.core.Concept object at 0x745ef4866e00>,
 Item(key='Wolf', value=<list object at 0x745ef45fa900>): <galactic.algebras.concept.core.Concept object at 0x745ef4866e00>,
 Item(key='Cat', value=<list object at 0x745ef45fa940>): <galactic.algebras.concept.core.Concept object at 0x745ef443e580>,
 Item(key='Tiger', value=<list object at 0x745ef45fa980>): <galactic.algebras.concept.core.Concept object at 0x745ef442dd40>,
 Item(key='Lion', value=<list object at 0x745ef45fa9c0>): <galactic.algebras.concept.core.Concept object at 0x745ef442dd40>,
 Item(key='Horse', value=<list object at 0x745ef45faa00>): <galactic.algebras.concept.core.Concept object at 0x745ef442dd40>,
 Item(key='Zebra', value=<list object at 0x745ef45faa40>): <galactic.algebras.concept.core.Concept object at 0x745ef442dd40>,
 Item(key='Cow', value=<list object at 0x745ef45faa80>): <galactic.algebras.concept.core.Concept object at 0x745ef443fac0>}

{<function small at 0x745ef48777e0>: <galactic.algebras.concept.core.Concept object at 0x745ef443cf80>,
 <function hunt at 0x745ef43ddc60>: <galactic.algebras.concept.core.Concept object at 0x745ef443cf80>,
 <function medium at 0x745ef45f3d80>: <galactic.algebras.concept.core.Concept object at 0x745ef443d640>,
 <function big at 0x745ef45f3ec0>: <galactic.algebras.concept.core.Concept object at 0x745ef443fb00>,
 <function fly at 0x745ef43dd120>: <galactic.algebras.concept.core.Concept object at 0x745ef443fb00>,
 <function swim at 0x745ef43dd4e0>: <galactic.algebras.concept.core.Concept object at 0x745ef443fb00>,
 <function mane at 0x745ef43de020>: <galactic.algebras.concept.core.Concept object at 0x745ef443fb00>,
 <function hooves at 0x745ef43de3e0>: <galactic.algebras.concept.core.Concept object at 0x745ef443fb00>,
 <function twolegs at 0x745ef43dc2c0>: <galactic.algebras.concept.core.Concept object at 0x745ef443d700>,
 <function feathers at 0x745ef45f28e0>: <galactic.algebras.concept.core.Concept object at 0x745ef443d700>,
 <function fourlegs at 0x745ef43dc680>: <galactic.algebras.concept.core.Concept object at 0x745ef443e000>,
 <function hair at 0x745ef43dca40>: <galactic.algebras.concept.core.Concept object at 0x745ef443e000>,
 <function run at 0x745ef43dd8a0>: <galactic.algebras.concept.core.Concept object at 0x745ef443e000>}

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

[<galactic.algebras.concept.core.Extent object at 0x745ef443fa00>,
 <galactic.algebras.concept.core.Extent object at 0x745ef446cb80>,
 <galactic.algebras.concept.core.Extent object at 0x745ef446c9c0>,
 <galactic.algebras.concept.core.Extent object at 0x745ef446c900>,
 <galactic.algebras.concept.core.Extent object at 0x745ef446cc00>,
 <galactic.algebras.concept.core.Extent object at 0x745ef446ccc0>]

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

[<galactic.algebras.concept.core.Intent object at 0x745ef443fa40>,
 <galactic.algebras.concept.core.Intent object at 0x745ef446d4c0>,
 <galactic.algebras.concept.core.Intent object at 0x745ef446d280>,
 <galactic.algebras.concept.core.Intent object at 0x745ef446c7c0>,
 <galactic.algebras.concept.core.Intent object at 0x745ef446d580>,
 <galactic.algebras.concept.core.Intent object at 0x745ef446d540>]

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