Keywords

1 Introduction

Generally, formal concept analysis (FCA) is a branch of lattice theory that has been developed since 1980-ies [10]. It is a field of applied mathematics based on concepts and concept hierarchies [5, 6]. In consequence, FCA has been exploited by various kinds of applications such as linguistics, information retrieval [1], economics and much more [7]. Commonly, classical FCA analyzes data in form of binary formal context that describes binary relationship among a set of objects and a set of attributes. Such context is based on traditional crisp set theory where an element either belongs fully to a set (take a membership value 1) or does not belong at all (take a membership value 0). FCA is used to generate set of formal concepts, also called fixpoints [10, 13]. Afterward, it builds the corresponding conceptual hierarchy known as formal concept lattice. Concept lattice represents the sub-concept/super-concept relationship (order relations) among the set of generated formal concepts. For association rule mining, FCA can efficiently produce attribute implications that help in extracting hidden association rules. Commonly, classical FCA provides only crisp scaling method to deal with multi-valued context that is not appropriate for human reasoning. The problem of crisp scaling is that it mainly depends on dividing attribute domain into several intervals. And hence, suffers from the problem of crisp boundaries. So it is hard to decide the boundaries between scaled attributes’ intervals [6]. This problem can be perfectly tackled using the fuzzification process for scaling multi-valued attributes to fuzzy sets. Consequently, FFCA faces the limitations of classical FCA. Fuzzy set theory and fuzzy logic are able to handle imprecise data such that an element can belong to a set to some extent with a membership value in the range of [0, 1] [8, 9]. FFCA can be widely utilized in fuzzy association rules’ generation as it can be used to generate fuzzy rules base [27].

This paper contributes to the family of FFCA algorithms. It proposes two efficient enhanced algorithms for extracting fuzzy formal concepts from a fuzzy context. It is well known that extracting set of all formal concepts from large contexts is a time consuming problem whose counting number problem is #P-complete [14]. But fortunately, if the relation (I) between object set(X) and attribute set(Y) is considerably small, one can get set of all formal concepts in a reasonable time even if |X| and |Y|are large [15].

The rest of this paper is organized as follows: Sect. 2 presents the foundations of formal concept analysis. Fuzzy formal concept analysis is addressed in Sect. 3. Section 4 introduces some related works. The proposed algorithms to extract fuzzy formal concepts are presented in Sect. 5. Consequently, Sect. 6 addresses some experiments for testing and evaluating the proposed algorithms. Finally, the conclusion is presented in Sect. 7.

2 Formal Concept Analysis

This section introduces FCA basic notions, more details are found in [2, 5, 6, 10]. Commonly, formal concept analysis aims to discover underlying clusters of objects and attributes within a dataset [16]. It accepts data inputs in the form of object-attribute values known as formal context. A formal context is a representation of a binary relation I between objects G and their attributes M. It can be represented as cross table of object rows, and column attributes (or vice versa). The intersected cell between each object g and attribute m has cross symbol only if \((g, m)\in I \) (donated as gIm). Given \(A\subseteq G\) and \(B\subseteq M\), the derivation of A and B is given by (1) and (2):

$$\begin{aligned} A\uparrow :=\{m\in M ~|~ (g I m) ~\forall g \in A \}. \end{aligned}$$
(1)

where \(A\uparrow \) represents common attributes in M shared by all objects of A.

$$\begin{aligned} B\downarrow :=\{g\in G ~| ~(g I m)~ \forall m~ \in B \}. \end{aligned}$$
(2)

where \(B\downarrow \) represents all objects that share all attributes of B.

Alternatively, \(A\uparrow \) and \(B\downarrow \) can be donated as \(A'\) and \(B'\) respectively.

Definition 1

(A, B) is a formal concept of the context (G, M, I) iff \(A\subseteq G\), \(B\subseteq M\), \(A'= B\) and \(B'=A\). Where A and B are concept extent and intent respectively.

Let \((A_1, B_1)\) and \((A_2, B_2)\) be formal concepts, then \((A_1, B_1)\) is \(\le \) \((A_2, B_2 )~\)if\(~ A_1 \subseteq A_2~ \)and\( ~B_2\subseteq B_1\). The set of all concepts partially ordered by this relation is called concept lattice.

Traditional FCA can only deal with binary context but usually the values of a dataset attribute are within a specified domain of values which may be a range of values. In such case, a many-valued context should be handled. Rationally, to use FCA in such situation, conceptual scaling can be used to transform such context into binary one which unfortunately leads to the crisp boundaries problem.

Definition 2

A many-valued context (G, M, V, I) is composed of G objects, M attributes, V attribute values and a ternary-relation \(I\subseteq ~G \times M \times V\). An element of I, \((g, m, w) \in \) I indicates that the attribute m has the value w for the object g.

3 Fuzzy Formal Concept Analysis

Generally, there are multiple points of view for FFCA and hence multiple basic definitions’ sets. This section introduces some basic notions and definitions of FFCA  [12, 17]. In a fuzzy formal context \(\Bbbk (G, M, I= \varphi (G \times M))\), I is a fuzzy set on domain of \(G~\times ~M\) such that each relation \((g, m)\in ~I\) has a membership value \(\mu (g,m)\) in [0, 1]. A confidence threshold is an interval of \([\alpha _1, \alpha _2]\) where 0 \(\le \alpha _1 \le \alpha _2 \le \)1 and is applied to fuzzy context \(\Bbbk (G, M, I)\) to eliminate relation (g, m) if its membership value \(\mu (g,m)\) is out of confidence threshold interval.

Definition 3

A fuzzy formal concept of a fuzzy context \(\Bbbk (G, M, I)\) is a pair \((A_{\mathrm {f}} = \varphi (A),B)\) where \(A~ \subseteq G\) is a fuzzy concept extent, \(B~ \subseteq ~ M\) is a fuzzy concept intent and \(A\uparrow =B\) and \(B\downarrow =A\). There are multiple definitions for \(A\uparrow \) and \(B\downarrow \). The first definition is given by (3) and (4) [11, 18, 19].

$$\begin{aligned} A\uparrow {:=}\{b\in B \,|\,\, \forall a \in A : \, \mu _{\mathrm {I}}(a,b)\ge \mu _{\mathrm {A}}(a)\}. \end{aligned}$$
(3)

where \(A\uparrow \) is the derivation of object set A and represents the concept intent.

$$\begin{aligned} B\downarrow {:=}\{a{/} \mu _{\mathrm {A}}(a)\, |\, \mu _{\mathrm {A}}(a)=min_{b\in B}(\mu _{\mathrm {I}}(a,b)\}. \end{aligned}$$
(4)

where \(B\downarrow \) is the derivation of attribute set B and represents the concept extent.

Another definition that uses an \(\alpha \) threshold is presented in [2, 17]. This definition is given by (5) and (6).

$$\begin{aligned} A\uparrow {:=}\{m\in M \,|\, \, \forall g \in A :\alpha _1 \le ~\mu _{\mathrm {I}}\le \alpha _2\}. \end{aligned}$$
(5)
$$\begin{aligned} B\downarrow {:=}\{g\in G \, |\, \forall m \in B :\alpha _1 \le ~\mu _{\mathrm {I}}(g,m)\le \alpha _2\}. \end{aligned}$$
(6)

where \( A\uparrow \)=B represents the fuzzy concept intent and \(B\downarrow \)=A represents the fuzzy concept extent.

4 Related Works

Generally, most algorithms related to fuzzy concepts’ extraction fall under one of the following categories: crisply generated fuzzy concepts, fuzzy concepts with fuzzy extents/crisp intents, fuzzy concepts with crisp extents/fuzzy intents and fuzzy concepts with fuzzy extents/fuzzy intents. Most algorithms that generate fuzzy concepts take the benefit of utilizing current existing FCA algorithms to generate fuzzy concepts. These algorithms mainly transform the fuzzy context into an isomorphic crisp one [23]. Such transformation process varies from one approach to another. Some examples of the algorithms that follow this category can be found in [6, 12, 20].

Commonly, it is noted that the count of crisply generated fuzzy concepts is considerably less than the count of all fuzzy concepts (with fuzzy extents/fuzzy intents). Although transforming fuzzy context into binary one allows to use existing crisp algorithms, there is still an extra cost involved due to: (1) extra processing for transforming the context to crisp one and the subsequent concepts’ conversion to fuzzy ones as well as (2) expanding the context results in increasing objects’ number and hence significant increase in computation [12]. The algorithm presented in [6] transforms fuzzy context to corresponding crisp one by setting maximum membership value per linguistic variable to 1 and others to 0. Then it uses any traditional algorithm to get whole crisp intents set. Finally it fetches the corresponding fuzzy objects by getting intent\(\downarrow \) from the original fuzzy context. Approach presented in [12] transforms the fuzzy context into corresponding binary one by pair each object in fuzzy context with each non-zero membership value \(\mu _I (O_i,b_j)\) and creates a new crisp object \(O_i/\mu _I(O_i,b_j)\). Then it uses any traditional concept generation algorithm to generate all possible formal concepts. Finally, it converts the crisp objects back to fuzzy ones and removes redundant objects by selecting the largest membership value.

Additionally, some other algorithms that generate fuzzy concepts with fuzzy intents/fuzzy extents can be found in \(B\check{e}lohl\grave{a}vek\)’s methods presented in [21, 22, 24, 25]. \(B\check{e}lohl\grave{a}vek\)’s methods are based on the fact that the relation between fuzzy subsets is strongly linked to the implication notion. In consequence, one can formulate FFCA in terms of fuzzy algebras. In short, this approach describes the complete lattice L as following: L = \(\langle L,\vee ,\wedge ,\otimes ,\rightarrow ,0,1 \rangle \) where \(\langle L,\vee ,\wedge ,0,1 \rangle \) is a complete lattice, \(\langle L,\otimes ,1 \rangle \) is an abelian monoid, \(\rightarrow ,\otimes \) are operations that form an adjoint pair (meaning, \(a \otimes b \le c \Leftrightarrow a \le b \wedge c\)). The set of all fuzzy sets in universe X is denoted by \(L^X\) where \(A: X \rightarrow L\) is a mapping that assigns every \(x \in X\) a truth value A(x)\(\,\in \) L. In this approach, the number of generated fuzzy concepts depends mainly on the number of distinct membership values produced by the used implication function (Lukasiewicz/G\(\ddot{o}\)del implications). Such kind of algorithms perfectly generates all possible fuzzy concepts but it generates inordinately large number of concepts so it consumes larger amount of time and hence is of limited practical use. Consequently, recent algorithms are proposed to reduce number of generated fuzzy concepts such as [3, 4].

It can be noted that the algorithms designed to extract fuzzy concepts with crisp intent/fuzzy extent or fuzzy intent/crisp extent, usually produce relatively smaller number of fuzzy concepts in a reasonable time compared with full fuzzy concepts. These algorithms mainly reduce the complexity. Yet, they suffer from ignoring one fuzzy side of the concept (intent or extent). Some examples of such algorithms are presented in [2, 6, 12].

5 The Proposed Algorithms to Extract Fuzzy Formal Concepts

In this section, two algorithms are proposed to extract fuzzy formal concepts in terms of fuzzy extents and crisp intents. Both algorithms take a raw input context and a threshold interval as inputs and filter the input context with conditions on the membership values while processing. Consequently, they don’t waste time to convert the entire context to the filtered one as a separate process that has complexity of O (N\(\times \)M) where N and M are the counts of rows and columns respectively. In both proposed algorithms, the set operations performed on the extents are fuzzy set operations introduced by Zadeh [8] while the set operations performed on intents are traditional set operations.

The first proposed Algorithm 1 computes the extent membership value of each concept using the minimum function as described previously in (4). In consequence, it extracts intents using (3). It is based mainly on the attribute set and works more efficiently in case of existence of redundant attributes (more symmetric correlated attributes), otherwise it becomes much closer to the recent fuzzy CbO algorithm [12].

figure a

On the other hand, the second proposed Algorithm 2 depends mainly on distinct intents per objects. So, it works more efficiently in case of the counts of distinct intents per objects are relatively small. Generally, the performed experiments show that Algorithm 2 reaches a great reduction in complexity when compared with some existing algorithms specially with large data sets. This backs to its dependency on the unique set of extents with maximal set of intents and ignorance of the subsets of intents with same extent set. Accordingly, despite of ignoring some concepts, it extremely enhances the overall performance (a trade off between precision and complexity). Consequently, the proposed Algorithm 2 reduces the total number of generated fuzzy concepts as a result of using (5) and (6) with lower cost than that obtained in [2, 17].

figure b

6 Experiments and Evaluation

In this section, some experiments are conducted over a data set titled “countries investment confidence marks” available in [26]. A transformed subset of this dataset is also used in [6, 20]. As a preparation phase, the original data set is fuzziffied respecting a set of predefined linguistic terms. The original dataset has 43 countries (objects) and 15 confidence criteria (attributes). All 15 confidence criteria take a value in the range [0, 4] such that 0 means less confidence mark (maximum risk) and 4 means minimum risk. The fuzzification process of the values of such attributes are done by applying three linguistic terms low, medium and high using the membership functions illustrated in Fig. 1. These membership functions are also used in [6]. Accordingly, the total count of attributes became 45 attributes as a result of the fuzzification process.

A snapshot of a subset of the original dataset (10 objects, 3 attributes) is presented in Table 1. As noted, attribute symbols are used for simplification such that: A, B and C denote political stability, general attitude towards the investors, and nationalization respectively. The corresponding fuzziffied context of the original dataset is presented in Table 2 using the linguistic terms defined in Fig. 1.

Fig. 1.
figure 1

Membership functions of linguistic terms \(\{low, medium~and~high\}\) defined over the linguistic variable marks

Full size image
Table 1. Countries investment confidence marks
Full size table
Table 2. Fuzzified countries investment confidence marks
Full size table
Table 3. Comparison between proposed Algorithm 2 and fuzzy CbO respecting threshold interval vs number of iterations
Full size table
Table 4. Comparison between proposed Algorithm 1 and fuzzy CbO with regard to attribute redundancy rate vs number of iterations
Full size table
Table 5. Comparison between proposed Algorithm 2 and fuzzy CbO respecting threshold interval vs number of iterations
Full size table

The proposed algorithms have been compared with fuzzy CbO algorithm [12]. Table 3 shows the result of comparison between proposed Algorithm 2 and fuzzy CbO in terms of the number of performed iterations for different threshold intervals. On the other hand, the proposed Algorithm 1 doesn’t show a big enhancement over fuzzy CbO with respect to different threshold intervals. However, it shows a big enhancement when tested over different percentages of attributes redundancy (symmetric correlation). The results are illustrated in Table 4. Also a test is performed with threshold interval [0.3, 1] on different object counts (10, 20, 30 and 43) and the test results are illustrated in Table 5 and shown in Figs. 2 and 3.

The experiments of the first proposed Algorithm 1 vs fuzzy CbO show that the first algorithm works extremely better in case of existence of symmetric correlated attributes. In contrary, it becomes more closer to fuzzy CbO when no symmetric correlations exist between the dataset attributes. On the other hand, the second proposed algorithm is more efficient than both of first proposed one and fuzzy CbO. This is due to reducing the number of generated concepts such that it only persists the largest unique intents and omits other subsets of this largest intent with same extents (with tiny difference in membership values).

Fig. 2.
figure 2

Experiments of fuzzy CbO vs proposed Algorithm 1

Full size image
Fig. 3.
figure 3

Experiments of fuzzy CbO vs proposed Algorithm 2

Full size image

7 Conclusion

Generally, FFCA represents one important and challenging field of the data mining research area. Many researches have been introduced to enhance such field. Yet, there is still a need for more efficient approaches in order to enhance the whole process output and accelerate related processes. Commonly, the process of extracting fuzzy formal concepts is the most complex process in FFCA. In this paper, two proposed algorithms have been introduced to reduce the complexity associated with this process. The first proposed algorithm generates the same concepts as fuzzy CbO but with a reduction in complexity and hence the execution time. It works better in case of the existence of symmetric correlated attributes. On the other hand, the second proposed algorithm generates less number of fuzzy concepts due to elimination of the very closed concepts extents. It works more efficiently when the number of distinct intents of objects is relatively smaller. It is not affected by any redundant object intent as it works mainly on the distinct set of intents. The experiments show the added value of the proposed algorithms.