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

[<galactic.algebras.concept.core.Concept object at 0x74ecec7f5c00>,
 <galactic.algebras.concept.core.Concept object at 0x74ecec472580>,
 <galactic.algebras.concept.core.Concept object at 0x74ecec472700>,
 <galactic.algebras.concept.core.Concept object at 0x74ecec4726c0>]

[[],
 ['Fox', 'Dog', 'Wolf'],
 ['Fox', 'Dog', 'Wolf', 'Cat', 'Tiger', 'Lion', 'Horse', 'Zebra'],
 ['Cat']]

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

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

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

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

[<galactic.algebras.concept.core.Concept object at 0x74ecec485b80>,
 <galactic.algebras.concept.core.Concept object at 0x74ecec53d500>,
 <galactic.algebras.concept.core.Concept object at 0x74ecec485000>,
 <galactic.algebras.concept.core.Concept object at 0x74ecec4a3d00>,
 <galactic.algebras.concept.core.Concept object at 0x74ecec4a3bc0>,
 <galactic.algebras.concept.core.Concept object at 0x74ecec4a3a00>]

[[],
 ['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'],
 ['Cat'],
 ['Dove', 'Hen', 'Duck', 'Goose', 'Owl', 'Hawk', 'Eagle']]

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

[<galactic.algebras.concept.core.Concept object at 0x74ecec4a7ac0>,
 <galactic.algebras.concept.core.Concept object at 0x74ecec4baf40>,
 <galactic.algebras.concept.core.Concept object at 0x74ecec4bb240>,
 <galactic.algebras.concept.core.Concept object at 0x74ecec4baec0>,
 <galactic.algebras.concept.core.Concept object at 0x74ecec4b8800>,
 <galactic.algebras.concept.core.Concept object at 0x74ecec4ba200>]

[[],
 ['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'],
 ['Cat'],
 ['Dove', 'Hen', 'Duck', 'Goose', 'Owl', 'Hawk', 'Eagle']]

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

[]

[]

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

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

['Cat']

['twolegs', 'feathers']

{Item(key='Dove', value=<tuple object at 0x74ecec761530>): <galactic.algebras.concept.core.Concept object at 0x74ecec477f40>,
 Item(key='Hen', value=<tuple object at 0x74ecec780700>): <galactic.algebras.concept.core.Concept object at 0x74ecec477f40>,
 Item(key='Duck', value=<tuple object at 0x74ecec437ab0>): <galactic.algebras.concept.core.Concept object at 0x74ecec477f40>,
 Item(key='Goose', value=<tuple object at 0x74ecec437ab0>): <galactic.algebras.concept.core.Concept object at 0x74ecec477f40>,
 Item(key='Owl', value=<tuple object at 0x74ecec437ba0>): <galactic.algebras.concept.core.Concept object at 0x74ecec477f40>,
 Item(key='Hawk', value=<tuple object at 0x74ecec437ba0>): <galactic.algebras.concept.core.Concept object at 0x74ecec477f40>,
 Item(key='Eagle', value=<tuple object at 0x74ecec437bf0>): <galactic.algebras.concept.core.Concept object at 0x74ecec477f40>,
 Item(key='Fox', value=<tuple object at 0x74ecec437c40>): <galactic.algebras.concept.core.Concept object at 0x74ecec4c8640>,
 Item(key='Dog', value=<tuple object at 0x74ecec7617b0>): <galactic.algebras.concept.core.Concept object at 0x74ecec4c8640>,
 Item(key='Wolf', value=<tuple object at 0x74ecec740700>): <galactic.algebras.concept.core.Concept object at 0x74ecec4c8640>,
 Item(key='Cat', value=<tuple object at 0x74ecec437c90>): <galactic.algebras.concept.core.Concept object at 0x74ecec4c8980>,
 Item(key='Tiger', value=<tuple object at 0x74ecec437ce0>): <galactic.algebras.concept.core.Concept object at 0x74ecec4ca180>,
 Item(key='Lion', value=<tuple object at 0x74ecec42d1e0>): <galactic.algebras.concept.core.Concept object at 0x74ecec4ca180>,
 Item(key='Horse', value=<tuple object at 0x74ecec42e800>): <galactic.algebras.concept.core.Concept object at 0x74ecec4ca180>,
 Item(key='Zebra', value=<tuple object at 0x74ecec42e800>): <galactic.algebras.concept.core.Concept object at 0x74ecec4ca180>,
 Item(key='Cow', value=<tuple object at 0x74ecec760cc0>): <galactic.algebras.concept.core.Concept object at 0x74ecec4a6880>}

{<function small at 0x74ecec44c2c0>: <galactic.algebras.concept.core.Concept object at 0x74ecec4c8a80>,
 <function hunt at 0x74ecec44f7e0>: <galactic.algebras.concept.core.Concept object at 0x74ecec4c8a80>,
 <function medium at 0x74ecec44d940>: <galactic.algebras.concept.core.Concept object at 0x74ecec4c8b80>,
 <function big at 0x74ecec44da80>: <galactic.algebras.concept.core.Concept object at 0x74ecec4a5840>,
 <function fly at 0x74ecec44eca0>: <galactic.algebras.concept.core.Concept object at 0x74ecec4a5840>,
 <function swim at 0x74ecec44f060>: <galactic.algebras.concept.core.Concept object at 0x74ecec4a5840>,
 <function mane at 0x74ecec44fba0>: <galactic.algebras.concept.core.Concept object at 0x74ecec4a5840>,
 <function hooves at 0x74ecec44ff60>: <galactic.algebras.concept.core.Concept object at 0x74ecec4a5840>,
 <function twolegs at 0x74ecec44de40>: <galactic.algebras.concept.core.Concept object at 0x74ecec4c8c00>,
 <function feathers at 0x74ecec44d620>: <galactic.algebras.concept.core.Concept object at 0x74ecec4c8c00>,
 <function fourlegs at 0x74ecec44e200>: <galactic.algebras.concept.core.Concept object at 0x74ecec4c8d00>,
 <function hair at 0x74ecec44e5c0>: <galactic.algebras.concept.core.Concept object at 0x74ecec4c8d00>,
 <function run at 0x74ecec44f420>: <galactic.algebras.concept.core.Concept object at 0x74ecec4c8d00>}

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

[<galactic.algebras.concept.core.Extent object at 0x74ecec4a6b00>,
 <galactic.algebras.concept.core.Extent object at 0x74ecec76d080>,
 <galactic.algebras.concept.core.Extent object at 0x74ecec4d7540>,
 <galactic.algebras.concept.core.Extent object at 0x74ecec4d7600>,
 <galactic.algebras.concept.core.Extent object at 0x74ecec4d76c0>,
 <galactic.algebras.concept.core.Extent object at 0x74ecec4d7780>]

[[],
 ['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'],
 ['Cat'],
 ['Dove', 'Hen', 'Duck', 'Goose', 'Owl', 'Hawk', 'Eagle']]

<galactic.algebras.concept.core.AttrFamily object at 0x74ecec488a90>

[<galactic.algebras.concept.core.Intent object at 0x74ecec4a6980>,
 <galactic.algebras.concept.core.Intent object at 0x74ecec4d7240>,
 <galactic.algebras.concept.core.Intent object at 0x74ecec4e8680>,
 <galactic.algebras.concept.core.Intent object at 0x74ecec4e8640>,
 <galactic.algebras.concept.core.Intent object at 0x74ecec4e87c0>,
 <galactic.algebras.concept.core.Intent object at 0x74ecec4e88c0>]

[['small',
  'medium',
  'big',
  'twolegs',
  'fourlegs',
  'hair',
  'feathers',
  'fly',
  'swim',
  'run',
  'hunt',
  'mane',
  'hooves'],
 ['medium', 'fourlegs', 'hair', 'run'],
 ['fourlegs', 'hair', 'run'],
 [],
 ['small', 'fourlegs', 'hair', 'run', 'hunt'],
 ['twolegs', 'feathers']]
Contents