Source code for fca.algorithms.close_by_one
import numpy as np
from fca import Concept
[docs]class CloseByOne:
"""Implements algorithm CloseByOne from Sergei O. Kuznetsov
CbO lists all formal concepts by a systematic search in the space of all
formal concepts, avoiding to list the same concept multiple times by
performing a canonicity test.
(cite: https://www.sciencedirect.com/science/article/pii/S0020025511004804)
More information about the algorithm can be found here:
https://link.springer.com/chapter/10.1007/978-3-540-48247-5_47
"""
[docs] @staticmethod
def generate_from(context, concept, y, n, Yj, intent, output):
"""
Recursively descends through the space of formal concepts, beginning
with :math:`<A,B>`.
Parameters
----------
context : :py:class:`fca.Context`
Context where the concepts should be find.
concept : :py:class:`fca.Concept`
Initial formal concept.
y :
Index of first attribute to be processed.
n :
Number of columns in context.
Yj:
Preallocated :py:class:`numpy.array` for better performance.
intent :
Preallocated intent for better performance.
output : list
Output list for formal concepts.
"""
output.append(concept)
# the least formal concept has been reached or there are no more
# remaining attributes to be processed
if np.logical_and.reduce(concept.intent) or y > n:
return
for j in range(y, n):
if not concept.intent[j]:
intent[:] = False
intent[j] = True
C = np.logical_and(concept.extent, context.down(intent))
D = context.up(C)
Yj[:] = True
Yj[j:] = False
i1 = np.logical_and(concept.intent, Yj)
i2 = np.logical_and(D, Yj)
if np.array_equal(i1, i2):
CloseByOne.generate_from(context, Concept(C, D), j + 1,
n, Yj, intent, output)
[docs] @staticmethod
def generate_concepts(context):
"""
Lists all formal concepts by a systematic search in the space of all
formal concepts, avoiding to list the same concept multiple times by
performing a canonicity test.
Parameters
----------
context : :py:class:`fca.Context`
Context where the concepts should be found.
Returns
-------
output : list
List of concepts.
"""
n = len(context.data[0])
init_extent = context.down(np.full(n, False))
init_intent = context.up(init_extent)
concept = Concept(init_extent, init_intent)
# Preallocating
Yj = np.empty(n, dtype=bool)
intent = np.empty(n, dtype=bool)
output = []
CloseByOne.generate_from(context, concept, 0, n, Yj, intent, output)
return output