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