A central notion in Formal Concept Analysis is the concept lattice. This lattice allows describing a hierarchical biclustering between objects and attributes of a formal context, whose hierarchy is defined by an order that expresses the specialisation-generalisation relationship between concepts. It is a fundamental way of representing the knowledge implicit in the context. Therefore, in practice, due to its theoretical complexity, it is necessary to define computationally eficient algorithms for its calculation. In the literature, several algorithms, using diferent approaches, have been proposed for the computation of the lattice in the classical framework, where the presence of an attribute in an object is modelled as a binary value, indicating that the attribute is either present or absent. However, it is possible to extend this framework to take into account the diferent degrees to which an attribute could be present in an object. Through this extension, it is possible to model fuzzy situations where the attribute is not 100% present in an object, giving flexibility to the model. In this paper, we review the best known algorithms for the calculation of the concept lattice in the binary version, and we extend them for the calculation of the fuzzy concept lattice, presenting the most significant diferences with respect to the original binary versions. In addition, we will present examples of the execution of these new versions of the algorithms.
In recent years, Formal Concept Analysis (FCA) is reaching a high degree of maturity. Only a
few decades have passed since the first works of the pioneers, R. Wille and B. Ganter [
Within the classical FCA framework, the knowledge extracted from a binary table of data (formal context) is essentially represented as two complementary entities: the concept lattice and a basis of context-valid implications. An interesting research line is the one that studies algorithms to compute both knowledge entities. The intrinsic exponential nature of the process (M. Ojeda-Hernández) (M. Ojeda-Hernández) of building the lattice and the basis of the implications encourages this line to be very active from the very beginning. This paper focuses on this line.
In this work, we emphasise the importance of the concept lattice: it represents an exhaustive analysis of the closed sets according to the well-known derivation operators forming a Galois connection. That allows us to establish a hierarchical biclustering of the relationships between objects and attributes.
Let us recall that the number of concepts can be exponential in the size of the input context
and the problem of determining this number is #P-complete [
The classical FCA framework is extended by considering non-binary relationships between
the objects and attributes, i.e. -fuzzy relations. The first approaches were due to Burusco
and Fuentes [
For FFCA, few algorithms have been developed by adapting the classical ones to the
generalised framework. We highlight [
The rest of the work is organised as follows. In Section 2, we present the background and the most prominent algorithms in classical FCA and in Section 3, we show how to extend the InClose family of algorithms to the fuzzy version. We provide an example of the execution of these new versions in Section 4 and present our conclusions and the future lines of work in Section 5.
In this section we give a brief summary of fuzzy set theory. Throughout the paper, the reader is expected to be familiar with Formal Concept Analysis notions.
Let = (, ∧, ∨, ⊗, →, 0, 1) be a complete residuated lattice, that is, (, ∧, ∨) is a complete lattice with 0 and 1 being the least and the greatest elements of , respectively, (, ⊗, 1) satisfies ⊗ is commutative, associative, and 1 is neutral with respect to ⊗, and ⊗ and → satisfy the so-called adjointness property: for all , , ∈ , we have that ⊗ ≤ if ≤ → .
An -set is a mapping ∶ → from the universe set to the truth values set , where () means the degree to which belongs to . The set of -sets on the universe is denoted by . If is finite, it is common to denote fuzzy sets as = { 1/ 1, 2/ 2, … , / }, where each element belongs to in degree . If = 0, the element might be omitted and if = 1 we denote it by { }. Operations with -sets are defined element-wise. For instance, ⊗ ∈ is defined as ( ⊗ )() = () ⊗ () for all ∈ .
Now we turn our focus to the main features of the classical algorithms that are considered the main background of this work. All of them start from a binary formal context. For the pseudocode and more details, we refer the reader to the sources cited in the text.
Although former attempts to compute the maximal rectangles of a binary relation exist [
NextClosure begins with the computation of the closure of the empty set. After this closure computation, the algorithm recursively enumerates the next closed sets in the lectic order. It is well-known that the complexity is exponential in the worst case, but it is interesting to know that the algorithm has a polynomial delay, (||| | 2) searching all the intents or (|| 2| |) searching all the extents. This fact establishes an upper bound to compute one concept.
Krajča et al. [
With respect to CbO, Fast Close-by-One (FCbO) [
In this paper, due to its simplicity of implementation, we focus on another highly eficient
algorithm named InClose [
The topic of discussion in this section will be the extension of the classical FCA algorithms to a fuzzy setting. Let = (, 0, 1, ∧, ∨, ⊗, →) be a complete residuated lattice. Since all our sets of objects and attributes are finite, without loss of generality we will consider to be finite as well. This is because the set { (, )} ∈,∈ is finite and we can consider ′ to be the smallest complete residuated lattice such that { (, )} ∈,∈ ⊆ ′ ⊆ . The complete residuated lattice ′ exists and is finite, the prove is not the goal of this paper so it is omitted.
In classical algorithms such as InClose2, introduced by Andrews [
The FuzzyInClose2 algorithm is the fuzzy extension to Andrews’ InClose2. In Algorithm 1, the procedure is initialised. For this, only the formal context is needed, then the auxiliary function InClose2_ChildConcepts is called with the initial extent , intent ∅, attribute index 0 and concept list ℂ = ∅.
Input: = (, , ) : A formal context with grades in = {0 < 1 < … < = 1} Output: () : The concept lattice of . 1 ℂ ∶= ∅ 2 InClose2_ChildConcepts( , ∅, 0, ℂ) 3 return () = ℂ
The auxiliary function used above is the one represented in Algorithm 2 below. This is the one that actually extends the InClose2 algorithm to the fuzzy framework and performs the recursive search. Notice how in line 3 we make range from to 1, that is, we run through the elements of in a decreasing order.
Remark 1. The notation of the pseudocode may look cumbersome. It is done set-theory style in order to maximize the amount of information given to the reader. However, from the coding point of view, the computation of the algorithms is much simpler due to the use of vector notation. For instance, in Algorithm 4, in line 5, when it reads ∩ { } ⊊ { / } in vector notation this is just ( ) < .
Notice that prior to line 1 it is required that is an extent. The algorithm starting with = ensures this since is always an extent and all ramifications of the algorithm are built as intersections of with attribute-extents, that always give other extents. It is also required that is the intent corresponding to accumulated over the course of the execution branch that has led to this node. Note that will be completed in the current level of recursion. Hence, ⊆ ↑ is needed. This is ensured in the first iteration of the algorithm since = ∅ but through all the ramifications this holds as well, although it cannot be seen that trivially.
Line 1: Initialize a list as empty.
Line 2: Iterate across the formal context, from a starting attribute + 1 up to attribute , where is the number of attributes in the context.
Line 3: Iterate across the truth values in backwards and...
Line 4: ... call the current truth value .
Algorithm 2: InClose2_ChildConcepts( , , , ℂ)
Input: : An extent; : The intent corresponding to , that will be completed in this execution; : index of the attribute where to start the exploration of this branch; ℂ: the global variable where to accumulate the computed concepts. 7 8 9 10 11 12 1 ∶= ∅ 2 for ∈ { + 1, … , | |} do 3 for ∈ {, … , 1} do 4 ∶= 5 if ∩ { } ⊊ { / } then 6 ∶= ∩ { / }↓ if ↑ ∩ { } = { / } then if = then
∶= ∪ { / } else if ∩ = ↑ then
∶= ∪ {(, , )} 13 ℂ ∶= ℂ ∪ {(, )} 14 for (, , ) ∈ do 15 ∶= ∪ { / } 16 InClose2_ChildConcepts( , , , ℂ)
Line 5: Skip attributes already in , since the truth values are gone through in decreasing order, ∩ { } ≠ ∅ implies belongs to in a higher degree than , so this can be skipped too.
Line 6: Form an extent, , by intersecting the current extent, , with the next column of objects in the context with degree .
Line 7: Skip all such that ↑ ∩ { } ≠ { / }. This is a partial canonicity test because in this iteration we are focused only on .
Line 8: ... if = , then...
Line 9: ...add { / } to the set ...
Lines 10 and 11: ... else, for the canonicity test, if the partial intent of up to is exactly restricted to the first − 1 attributes...
Line 12:... store (, , ) ∈ ...
Line 13: Store the concept (, ) in the list ℂ Line 14: For each extent , attribute and truth value stored in ...
Line 15: Create the intent = ∪ { / }.
Line 16: Call InClose2_ChildConcepts to compute the child concepts of starting from the attribute and complete the intent .
It is interesting to remark that in line 7 the calculation of ↑ ∩ { } does not require the computation of the intent since it is simply ↑ ∩ { } = ↑( ) = ⋀ (() → (,
)) .
∈ Similarly, the computation of the intent ↑ is not needed since it follows from the previous formula: the implementation would only present a loop over the attributes < , computing ↑ ∩ { } using the formula above, and stopping early when ↑ ∩ { } = ↑( ) ≠ ( ) = ∩ { }.
InClose2 has been proved to be correct and fairly quick timewise, even though it does several
redundant computations. For instance, assume that ∩ { / }↓ is empty. Then, for all child
concepts from this extent on, it follows trivially that ∩ { / }
↓ = ∅, hence this iteration may be
skipped with no loss of information. This is taken into account in a series of algorithms called
InClose4, introduced by Andrews [
Next, we give some details of the diferences between FuzzyInClose2 and FuzzyInClose4a. Due to space reasons, only the pseudocode of FuzzyInClose4b is displayed, since it is the fastest and the less computation demanding.
The main method FuzzyInClose4a only difers from the InClose2 version in that the auxiliary function, now called InClose4a_ChildConcepts, requires an extra argument, , that keeps track of the empty intersections occurring in a branch of the execution, and that is initially empty. lower. to InClose4a_ChildConcepts.
There are subtle changes in lines 5, 11 and 12 of InClose2a_ChildConcepts that improve it Line 5 Skip all attributes that are already in in degree or higher or in in degree or Line 5 in InClose4a: we can omit all attributes that are already in in degree or higher or in in degree or lower, by performing the check ∩{
After line 10
Before performing the canonicity test ∩ } ⊊ { / } and ( ∩{ } = ∅ or { / } ⊊ ∩{
}). = ↑ in line 11 (Algorithm 2), the fuzzy version of InClose4a will check if the new extent is empty, thus updating , the record of empty intersections, accordingly: if = ∅ then ∶= { / } ∪ ( ∖ { }). The update of is designed to keep track of the minimal degree for which the computation of the extent provides the empty set. Thus, the condition in line 5 will be optimal and reject all the cases that inherit the empty intersection.
Notice that the execution of FuzzyInClose4a( ) computes all the extents of the given context from to ∅, in case ∅ is indeed an extent.
Another algorithm that blends the spirit of FuzzyInClose2 and the avoiding empty intersections of FuzzyInClose4a is the so-called FuzzyInClose4b algorithm.
Introduced in the classical FCA by Andrews [
Input: = (, , ) : A formal context with grades in = {0 < 1 < … < = 1} Output: () : The concept lattice of . 1 ℂ ∶= ∅ 2 InClose4b_ChildConcepts( , ∅, 0, ∅, ℂ) 3 if ↓ = ∅ then 4 ℂ ∶= ℂ ∪ {(∅, )} 5 return () = ℂ
Input: : An extent; : The intent corresponding to , that will be completed in this execution; : index of the attribute where to start the exploration of this branch; : record for empty intersections; ℂ: the global variable where to accumulate the computed concepts. 7 8 9 10 11 12 13 14 15 1 ∶= ∅ 2 for ∈ { + 1, … , | |} do 3 for ∈ {, … , 1} do 4 ∶= 5 if ∩ { } ⊊ { / } and ( ∩ { } = ∅ or { / } ⊊ ∩ { }) then 6 ∶= ∩ { / }↓ if ↑ ∩ { } = { / } then if = ∅ then
∶= (∖{ }) ∪ { / } else if = then
∶= ∪ { / } else if ∩ = ↑ then
∶= ∪ {(, , )} 16 ℂ ∶= ℂ ∪ {(, )} 17 for (, , ) ∈ do 18 ∶= ∪ { / } 19 InClose4b_ChildConcepts( , , , , ℂ) algorithm. Fortunately, this occurs only once and it is the extent ∅, in the case it is indeed an extent. This is a small price to pay and it is solved in Algorithm 3, lines 3 and 4, where a direct check on (∅, ) being a formal concept is made and, if it is, it is stored in ℂ.
In this section, we present an example of the implementation of the fuzzy versions
FuzzyInClose2, FuzzyInClose4a and FuzzyInClose4b. Due to space restrictions, we
cannot present the complete trace of the execution of these algorithms. However, we have chosen
to present this trace in graphical form, in order to be able to check the diferent steps followed
by each of these algorithms. For this work, we have implemented the algorithms using the
functionalities provided by the fcaR package [
In this example, we consider the formal context of Table 1, where the set of grades for the attributes = {, , , , } is = {0, 1/2, 1}. It is not a large context in order to make the execution graphs legible.
The first of the tested versions is FuzzyInClose2. In Figure 1, we can check the order in which the extent intersections are computed in this algorithm. Starting with ∅, the first level of recursion (intersection of with all attribute extents) is carried out from left to right, in the attribute order defined in the previous section. We have used a colour code to indicate the possible situations that can occur when checking a given node: a red box indicates that the canonicity test has failed at that point; a light orange box indicates that the partial canonicity test is not passed; and a grey box appears when parent and child nodes have the same extent, so the intent of the parent is updated. Once the whole level has been checked, we start to develop the branches in the next phase of the recursion, going through the nodes from left to right. So, under the node labelled {} , we start to develop its branch, following exactly the same procedure as before: we have to go through all the attributes/degrees starting from the attribute {} , and then develop the leftmost branch that is not developed at that moment. Repeating the process, we arrive at 5 levels of recursion for the calculation of all concepts.
The execution graphs for FuzzyInClose4a and FuzzyInClose4b, which take into account the occurrence of empty intersections at each level of recursion of the algorithm, are presented in Figure 2 below. These empty intersections are inherited downwards in the branches arising from that level of recursion, and allow to reduce the number of operations to be performed, as well as the depth of the recursion. The same colour code is used as in Figure 1, adding the blue boxes to represent iterations where an empty extent was found.
As can be seen, there is no great diference, at least in this example, between the two proposals, although there is a clear reduction in the computational load with respect to our baseline of comparison, the FuzzyInClose2 method. We can see that, instead of 5 levels of recursion, in the FuzzyInClose4 family, only 4 appear. Due to the diferent characteristics of both methods, it is to be expected that in larger contexts diferences will appear and that, probably, they will be in favour of the FuzzyInClose4b variant, since it makes a greater pruning in the exploration of the graph of intersections of extents.
Finally, we present in Table 2 a quantitative comparison of the number of operations carried out by each algorithm. We will only count computationally expensive operations: partial canonicity tests, i.e., checks of ↑ ∩ { } = { / }; complete canonicity tests, as in the binary case, on the equality ∩ = ↑ ; and the number of attribute intents computed and the number of intersections of extents. In this table we show the number of such operations for each algorithm.
In the table, diferent facts can be observed. On the one hand, looking at the #Extents column, we can see how versions 4a and 4b of the algorithm build smaller execution graphs, since the number of intersections coincides with the number of nodes explored in the execution of the graph. On the other hand, although the execution graph is the same for versions 4a and 4b, the diferent strategy for exploiting empty intersections produces a clear reduction in the number of operations to be carried out, since fewer tests, both partial and complete, are checked. Thus, the exploration carried out by FuzzyInClose4b is more eficient and, for larger contexts, could be the fastest of the 3 algorithms.
The concept lattice is a fundamental way of representing the knowledge implicit in the context. In the literature, several algorithms, using diferent approaches, have been proposed for the computation of the lattice in the classical framework. In this paper some of the extensions of these algorithms to the fuzzy framework have been introduced. These algorithms are of the family of InClose. After a brief explanation of the code, an example was shown to illustrate the trace of the diferent approaches. Lastly, the algorithms are compared taking into account runtime, number of test calculations and number of extents computed.
As a future work, we devise to study several optimisations to the InClose4 family, taking advantage of the structure of the degrees in . The aim of the possible optimisations will be to reduce the number of computations both of intents and extents, hence reducing the computational cost of the algorithm.
Furthermore, we aim to explore generalisations of other algorithms, such as the FastCbO family or the NextNeighbour or NextPriorityConcept, for the fuzzy setting, along with diferent optimisations that could alleviate the greater computational cost when compared to the binary case. We want to perform a thorough comparison between the diferent versions of the algorithms in terms of execution time and the number of computations required to compute the fuzzy concept lattice. We expect to incorporate the implementation of all algorithms for lattice computation in the fuzzy framework into the above-mentioned fcaR package.
Other research line for future works will study the extension of the provided algorithms to compute the canonical basis of implications in this fuzzy setting. It has already been proved that, in the binary case, CbO-like algorithms can be modified to provide such a basis. We aim to extend the fuzzy versions of the algorithms to compute the basis.
This work has been partially supported by the Ministerio de Ciencia, Innovación y Universidades [FPU19/01467, TIN2017-89023-P, PGC2018-095869-B-I00] and the Junta de Andalucía [UMA2018‐FEDERJA‐001].