Abstract
Formal concept analysis (FCA) is a mathematical framework for data analysis and processing tasks. Based on the lattice and order theory, FCA derives the conceptual hierarchies from the relational information systems. From the crisp setting, FCA has been extended to fuzzy environment. This extension is aimed at handling the uncertain and vague information represented in the form of a formal context whose entries are the degrees from the scale [0, 1]. The present study analyzes the fuzziness in a given many-valued context which is transformed into a fuzzy formal context, to provide an insight into generating the fuzzy formal concepts from the fuzzy formal context. Furthermore, considering that a major problem in FCA with fuzzy setting is to reduce the number of fuzzy formal concepts thereby simplifying the corresponding fuzzy concept lattice structure, the current paper solves the problem by linking an interval-valued fuzzy graph to the fuzzy concept lattice. For this purpose, we propose an algorithm for generating the interval-valued fuzzy formal concepts. To measure the weight of fuzzy formal concepts, an algorithm is proposed using Shannon entropy. The knowledge represented by formal concepts using interval-valued fuzzy graph is compared with entropy-based-weighted fuzzy concepts at chosen threshold.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
1 Introduction
Formal concept analysis (FCA) was proposed by Wille (1982) in the early eighties for analysis of tabular data in the form of object–attribute relation (formal context). The basic outputs of FCA are formal concepts, concept lattice and attribute implications. Formal concept is a pair of object and attribute cluster closed with Galois connection in a given formal context. Concept lattice represents hierarchical order between the formal concepts in form of specialization and generalization. Specialization and generalization play a major role in data analysis and processing tasks: generalized concepts contain more objects while specialized concepts contain more attributes (Wille 1982). Attribute implication shows the dependencies among attributes in a given formal context.
Initially, the mathematical foundation of FCA has been introduced in crisp setting in which relation between objects and attributes is bivalent (Ganter and Wille 1999). In contrast of binary attributes, many-valued context describes quantitative attributes such as young, weight and age (Wolf 1998, 2002). FCA with crisp setting cannot represent these types of linguistic words (like ‘young’, ‘age’) precisely because the word ‘young’ is granular variable (Belohlavek 1988; Formica 2010). Also, the linguistic variables are appended with hedges like very, fairly. (Zadeh 1965). Fuzzy logic (Zadeh 1975) computes with linguistic word of human language precisely than crisp setting. Due to this property of fuzzy logic, it was incorporated into FCA to represent the uncertainty and vagueness in the given context (Alcade et al. 2011; Burusco and Fuentes-Gonzales 1994). Fuzzy logic avoids this restricted boundary and vagueness through defining the degree of membership for the granular variables (Zadeh 1965, 1975) and provides us another way to process the formal context (containing membership value). The incorporation of fuzzy logic into concept lattice extended the the notion of FCA as fuzzy formal context (Belohlavek 1999), fuzzy formal concept (Belohlavek 2001), and fuzzy concept lattice (Belohlavek and Vychodil 2005). Generating the fuzzy formal concepts, their hierarchical order visualization in the fuzzy concept lattice and attribute implications is a major concern for knowledge-processing tasks using FCA (Poelmans et al. 2013a, b). Hence, several algorithms were proposed for generating the fuzzy concept lattice (Belohlavek and Vychodil 2005; Belohlavek et al. 2007; Gajdos and Snasel 2013) and attribute implication (Ayouni et al. 2011; Zhang et al. 2005). Very few researches have focused on demonstrating fuzziness in given context, generation of fuzzy formal concepts and its visualization in the fuzzy concept lattice structure (Aswani Kumar and Singh 2014). In this paper, we aimed at providing such an understanding to the readers about fuzziness in a given context, step-by-step generation of fuzzy formal concepts and its visualization to fuzzy as well as interval-valued fuzzy concept lattice structure. For the analysis, we have considered a many-valued context (Belohlavek and Konecny 2007) and transformed it into a binary context with the help of scaling theory (Wolf 1998, 2002). Thereafter, we have demonstrated the generation of fuzzy formal concepts and its lattice structure.
Formal concepts generation and visualization of them in a lattice structure is an important concern for practical applications of FCA in several fields like knowledge discovery (Aswani Kumar 2011), association rule mining(Aswani Kumar 2012; Ayouni et al. 2011), health care (Aswani Kumar and Srinivas 2010b), information retrieval (Aswani Kumar et al. 2012), data analysis (Carpineto and Romano 2004), semantic web (Formica 2010; Maio et al. 2012) and mathematical search (Nguyen et al. 2012). The process of computing all the formal concepts and their hierarchical order visualization in the concept lattice is a complex task. The reason is that the size of concept lattice constructed from the large number of formal concepts becomes improper and impractical. Hence, for reducing the size of concept lattice, several approaches have been established based on fuzzy \(K\)-means clustering (Aswani Kumar and Srinivas 2010a), hedges (Belohlavek and Vychodil 2005), variable threshold (Belohlavek 2007; Ma et al. 2006; Wu et al. 2009), triangular decomposition (Belohlavek 2009), Lindig algorithm (Belohlavek et al. 2007), factorization (Belohlavek et al. 2007), similarity (Belohlavek and Krupka 2009; Formica 2010), JBOS (Dias and Viera 2013), Lukasiewicz logic (Elloumi et al. 2004), modular decomposition (Gely 2011; Singh and Aswani Kumar 2012c), granularity (Kang et al. 2012; Singh and Aswani Kumar 2012a; Wang and Liu 2008), block relations (Konecny and Krupka 2011), T-implication (Li and Jhang 2010), decision context (Li et al. 2012), dual concept lattice (Ma et al. 2013; Mehdi et al. 2011; Medina and Ojeda-Aciego 2012), axialities (Mi et al. 2010), projection (Singh and Aswani Kumar 2012b), fuzzy homomorphism (Singh and Aswani Kumar 2014b; Zhou 2011), composition (Singh and Aswani Kumar 2015) and others (Zhang et al. 2007; Singh and Aswani Kumar 2014a, c). In this paper, we reduce the size of fuzzy concept lattice using the properties of interval-valued fuzzy graph and its properties. The reason is interval-valued fuzzy set provides more adequate description of uncertainty than fuzzy set. In the same time, interval-valued fuzzy graph represents more adequate visualization of fuzzy attributes as nodes when compared to fuzzy (Ghosh et al. 2010) or crisp graph (Berry and Sigayret 2004). With this motivation, Prem Kumar and Aswani Kumar (Singh and Aswani Kumar 2012b) incorporated the link between interval-valued fuzzy graph and concept lattice. Recently, the properties of interval-valued fuzzy graph (Akram and Dudek 2011), fuzzy hypergraph (Akram and Dudek 2013), interval-valued fuzzy formal context (Alcade et al. 2011; Burusco and Fuentes-Gonzales 2001), interval-valued fuzzy Galois connection (Djouadi 2011; Djouadi and Prade 2009), lattices of interval-valued fuzzy set (Ranitovic and Petojevic 2013), interval-valued fuzzy attribute implication (Zhai et al. 2012) and its application (Zerarga and Djouadi 2012) have been studied extensively. Extending upon the work (Singh and Aswani Kumar 2012b), in this paper, we focus on introducing an algorithm for generating interval-valued fuzzy formal concepts using the properties of interval-valued fuzzy graph and Galois connection. We can observe that the contribution of this paper is as follows:
-
(1)
Analyze fuzziness in a given context, understanding of step-by-step generation of fuzzy formal concepts and its issues;
-
(2)
Provide the link between interval-valued fuzzy graph and concept lattice for simplifying the size of fuzzy concept lattice;
-
(3)
Propose an algorithm for generating interval-valued fuzzy formal concepts using the properties of interval-valued fuzzy set and Galois connection;
-
(4)
One of the application of the proposed algorithm; and
-
(5)
Introduce a method for computing the weight of given fuzzy formal concepts using Shannon entropy.
We show that interval-valued fuzzy graph simplifies the size of fuzzy concept lattice structure while preserving specialization and generalization. The importance of obtained interval-valued fuzzy formal concepts is measured by entropy-based-weighted method with comparison.
Rest of the paper is organized as follows: Sect. 2 provides a brief background about FCA in the fuzzy setting. Section 3 provides analysis of fuzzy attributes, step-by-step generation of fuzzy formal concepts and its problems. Section 4 provides interval-valued fuzzy graph representation of concept lattice and its comparison with entropy-based-weighted fuzzy concepts. Section 5 provides discussions followed by conclusions, acknowledgement and references.
2 Formal concept analysis in the fuzzy setting
A fuzzy formal context is a triplet K = (O, P, \(\tilde{R}\)), where O is a set of objects, P is a set of attributes and \(\tilde{R}\) is an L-relation between \(O\) and \(P\) i.e \(\tilde{R}\): O \(\times \) P \( \rightarrow \textit{L}\) (Burusco and Fuentes-Gonzales 1994; Burusco and Fuents-Gonzales 2000) where L is a support set of some complete residuated lattice L defined below. Each \(\tilde{R}(\textit{o},\textit{p})\) represents the membership value at which the object \(o\in \textit{O}\) has the attribute \(p\in \textit{P}\) in [0, 1]. The objects, attributes and relation in a fuzzy formal context are not restricted to be only crisp but also fuzzy (interval) as discussed in Table 1. The condition complete or incomplete discusses about availability, partial availability and non-availability of objects, attributes and relation in the given context studied extensively (Burmeister and Holzer 2005; Dubois and Prade 2012; Kai et al. 2011; Li et al. 2013; Krupka and Lastovica 2012). In this study, first we consider the condition ‘complete’ for demonstration of the proposals. Thereafter, we discuss the notion ‘incomplete’ in formal context with its analysis using the proposed algorithm.
The notions residuated lattice, fuzzy Galois connection and complete lattice are defined below in brief.
A residuated lattice L \(=(L,\wedge ,\vee ,\otimes ,\rightarrow ,0,1)\) is the basic structure of truth degrees, where 0 and 1 represent least and greatest elements, respectively. L is a complete residuated lattice iff (Belohlavek 1999; Pollandt 1997):
-
(1)
\((L,\wedge ,\vee ,0,1)\) is a complete lattice.
-
(2)
\((L,\otimes ,1)\) is commutative monoid.
-
(3)
\(\otimes \) and \(\rightarrow \) are adjoint operators and \( a \otimes b \le c\) iff \(a\le b\rightarrow c, \forall a,b,c\in \mathbf L \).
The operators \(\otimes \) and \(\rightarrow \) are defined distinctly by Lukasiewicz, Godel, and Goguen t-norms and their residua as described below (Belohlavek and Vychodil 2005):
Lukasiewicz:
-
a \(\otimes \) b \(=\) max (a+ b \(-\) 1, 0).
-
a \(\rightarrow \) b \(=\) min (1 \(-\) a + b, 1).
Godel:
-
a \(\otimes \) b \(=\) min (a,b).
-
a \(\rightarrow \) b \(=\) 1 if a \(\le \) b, otherwise b.
Goguen (product):
-
a \(\otimes \) b \(=\) a \(\cdot \) b
-
a \(\rightarrow \) b \(=\) 1 if a \(\le \) b, otherwise b/a.
Classical logic is a special case of complete residuated lattice which is represented as \((\left\{ 0,1\right\} \!,\wedge ,\vee ,\otimes ,\rightarrow ,0,1)\). For any L-set A \(\in L^{\tiny {\textit{O}}}\) of objects, and B \( \in L^{\tiny {\textit{P}}}\) of attributes, we can define an L-set A \(^{\uparrow }\in L^{\tiny {\textit{P}}}\) of attributes and an L-set B \(^{\downarrow }\in L^{\tiny {\textit{O}}}\) of objects as follows (Belohlavek 1999):
-
(1)
A \(^{\uparrow } (p)=\wedge _{o\in {{O}}}( {A}(o) \rightarrow \tilde{R}({o},{p}))\);
-
(2)
B \(^{\downarrow } (o)=\wedge _{p\in {{P}}}({B}(p) \rightarrow \tilde{R}({o},{p}))\).
A \(^{\uparrow } (p)\) is interpreted as the L-set of all attributes p \(\in \textit{P}\) shared by objects from A. Similarly, B \(^{\downarrow } (o)\) is interpreted as the L-set of all objects o \( \in O\) having the attributes from B in common. The fuzzy formal concept is a pair of (A, B)\(\in L^{{\tiny {O}}}\times L^{{\tiny {P}}}\) satisfying \({A}^{\uparrow }={B}\) and \({B}^{\downarrow }={A}\), where fuzzy set of objects A called as extent and fuzzy set of attributes B called as intent.
The pair (\(\uparrow , \downarrow \)) is known as a Galois connection (Belohlavek 2001; Carpineto and Romano 2004; Ganter and Wille 1999). Recently, the properties of galois connection were extended with fuzzy (Pocs 2012), interval-valued fuzzy set (Djouadi 2011; Djouadi and Prade 2009), possibility theory (Dubois and Prade 2012) and variable threshold variable threshold (Belohlavek 2007). When the operator (\(\uparrow \)) is applied on a fuzzy set of objects, it provides a fuzzy set of attributes with its membership value being maximal with respect to integrating the information from all the objects. Consequently, when the operator (\(\downarrow \)) is applied on the fuzzy set constituted by these covered attributes resulting from integrating the membership information between objects and attributes. It takes a fuzzy set of objects with its membership value being maximal with respect to integrating the information from the attributes. Since, we consider the maximal membership value, we cannot find any fuzzy set of objects (attributes) which can make the membership value of the obtained fuzzy set of attributes (objects) bigger, if the pair of the set of objects and the set constituted by its covered attributes forms a fuzzy formal concept.
The set of fuzzy formal concepts FC \(_\mathbf{{K} }\), generated from a given fuzzy formal context K, defines the partial ordering principle of set, i.e., \((\textit{A}_{1},\textit{B}_{1})\le (\textit{A}_{2},\textit{B}_{2})\Longleftrightarrow \textit{A}_{1}\subseteq \textit{A}_{2}(\Longleftrightarrow \textit{B}_{2}\subseteq \textit{B}_{1})\). Together with this ordering, in the complete lattice there exist an infimum and a supremum for some formal concepts (Belohlavek and Vychodil 2005; Carpineto and Romano 2004; Ganter and Wille 1999):
-
\(\wedge _{j\in J}(A_{j}, B_{j}) = (\bigcap _{j\in J} A_{j}, (\bigcup _{j\in J}B_{j})^{\downarrow \uparrow })\),
-
\(\vee _{j\in J} (A_{j}, B_{j}) = ((\bigcup _{j \in J} A_{j})^{\uparrow \downarrow },\bigcap _{j\in J} B_{j})\).
3 Analysis of fuzziness in a given many-valued context
3.1 FCA of data with fuzzy attributes
Definition 1
(Many-valued context) (Carpineto and Romano 2004; Ganter and Wille 1999) A many-valued context consists of sets O, P, W and a ternary relation R, i.e., R \(\subseteq O \times P \times W \) between those three sets for which it holds that, (o, p, w) \(\in \) R and (o, p, v) \(\in \) R always imply w = v. Elements of o are called as objects. Elements of p are called many-valued attributes. Elements of W are called attribute values. Accordingly, (o, p, w) \(\in \) R means the attribute p takes value w for object o simply written as p (o) = w.
For the analysis, we have considered a many-valued context (or a complete context) as shown in Table 2 (Bache and Lichman 2013). These many-valued attributes can be represented as a binary context using following scaling:
Step1. Let us suppose for age:
-
If age is between [0, 30] then young and shown by \(a_{y}\),
-
If age is between [31, 50] then medium and shown by \(a_{m}\),
-
If age is between [51, 100] then old and shown by \(a_{o}\).
Step 2. Let us suppose for height:
-
If height is between [0,160] then short and shown by \(h_{s}\),
-
If height is between [161, 180] then medium and shown by \(h_{m}\),
-
If height is between [181, 250] then tall and shown by \(h_{t}\).
Step 3. If the relation between an object and an attribute exists, then it is denoted as cross ‘\(\times \)’; otherwise, Null, while converting them into the binary. Table 3 shows the scaled context of Table 2 computed via the above steps.
We can observe that the scaled binary context (shown in Table 3) represents the objects with considering the boundary of crisp set theory. The scaled binary context can be represented by a fuzzy formal context (Shown in Table 4) through a defined membership function on the attributes—(\(a_{y}\), \(a_{m}\), \(a_{o}\),..., etc.) as given below:
Definition 2
A fuzzy membership function is defined on the scaled attribute age (\(a_{y}\), \(a_{m}\), \(a_{o}\)) as given below:
-
1.0 if \(a_{1}=a_{2}\),
-
0.75 if 0 \(< \left| a_{1}-a_{2}\right| \le \) 5,
-
0.5 if 6 \( \le \left| a_{1}-a_{2}\right| \le \) 11,
-
0.25 if 12 \(\le \left| a_{1}-a_{2}\right| \le \) 17,
-
0.0 otherwise,
where \(a_{1}\) and \(a_{2}\) represent the difference between given age and scaled attribute age, respectively. The membership values of attribute (age) with their corresponding objects are reflected as a fuzzy relation (\(\tilde{R}\)), shown in Table 4. Similarly, for height (h) we can define the fuzzy relation \(\left\{ 0.0, 0.25, 0.5, 0.75, 1.0 \right\} \) between its corresponding objects. This definition can also be extended for other membership values between [0, 1] through dividing the interval. Further, modifier may be used to enhance the ability to describe the fuzzy set precisely.
Step 4. We can observe that Table 4 represents fuzziness in the scaled binary context (shown in Table 3). The fuzzy context shown in Table 4 represents \(\left\{ 0.0, 0.25,0.5,0.75, 1.0 \right\} \)—fuzzy relation between the objects and the attributes depicted in Table 2. Since Table 4 represents a fuzzy formal context we can generate some fuzzy formal concepts and visualize them in the corresponding fuzzy lattice structure. The step-by-step generation of fuzzy formal concepts from Table 4 is shown in Sect. 3.2.
Several algorithms have been proposed in literature for finding formal concepts in FCA with crisp (Carpineto and Romano 2004; Kuznetsov and Obiedkov 2002), fuzzy(Alcade et al. 2011; Belohlavek and Vychodil 2005; Burusco and Fuents-Gonzales 2000; Popescu 2004), possibility theory (Zhai et al. 2012; Yao 2004a), interval-valued (Djouadi 2011; Djouadi and Prade 2009) as well as rough setting (Wang and Liu 2008; Yao 2004a, b). In this paper, we have considered object intersection and concept covering algorithm for generating the fuzzy formal concepts and lattice structure. This algorithm was first introduced by Carpineto and Romano (2004). In this algorithm (Yang et al. 2008) uses confidence threshold \(\theta \), which has an interval [\(\theta _{1},\) \(\theta _{2}\)] where 0 \(\le \) \(\theta _{1}\) \(\le \) \(\theta _{2}\) \(\le \) 1. The value of threshold \(\theta \) can be set by the user requirement for generating the fuzzy concepts from a given fuzzy formal context. Also, this algorithm uses min operator which satisfies the transitivity condition. These properties help to eliminate some fuzzy relations which are out of the interval [\(\theta _{1}, \theta _{2}\)] from a given fuzzy formal context for knowledge discovery and representation (Belohlavek 2007). Another property of this algorithm is that it generates fuzzy formal concepts and builds the fuzzy lattice structure independently, which takes less time when user requirement is only generating the fuzzy formal concepts.
3.2 Illustration of fuzzy formal concept generation
The steps of algorithm for formal concept generation and constructing fuzzy concept lattice are shown in Tables 5 and 6, respectively (Yang et al. 2008).
We have considered confidence threshold T \( = \) [0.25, 1.0] for generating the fuzzy concepts from Table 4 in this study. Step-by-step demonstration of generating fuzzy formal concepts from Table 4 is described below:
Step 1. With the help of algorithm step 2 shown in Table 5, we can observe that first min = 0.0. Then, o.membership value = 0.0, so p = (\(a_{y}, a_{m}, a_{o}, h_{s}, h_{m}, h_{t}\)). Then, applying fuzzy concept forming operators (\(\uparrow \) and \(\downarrow \)) on these sets we can get:
-
1.
\(\{\oslash ,1.0/\textit{a}_{y}+1.0/\textit{a}_{m}+1.0/\textit{a}_{o}+1.0/\textit{h}_{s}+1.0/\textit{h}_{m}+1.0/\textit{h}_{t}\}\) is a concept, where \(\oslash \) represents null set.
Step 2. When we increase the min-value (o.membership) for computing the next concepts (from the fuzzy context shown in Table 4) as follows:
-
1.
\((1.0/a_{y})^{\downarrow } = \{0.25/\textit{o}_{1}+1.0/\textit{o}_{2}\}\)
\(\{0.25/\textit{o}_{1}+1.0/\textit{o}_{2}\}^{\uparrow } = \{1.0/a_{y}+1.0/h_{s}\}\).
Hence, \(\{0.25/\textit{o}_{1}+1.0/\textit{o}_{2},1.0/a_{y}+1.0/h_{s}\}\) is a fuzzy formal concept.
-
2.
\((1.0/a_{m})^{\downarrow } = \{1.0/\textit{o}_{1}+0.5/\textit{o}_{2}+0.25/\textit{o}_{3}\}\)
\(\{1.0/\textit{o}_{1}+0.5/\textit{o}_{2}+0.25/\textit{o}_{3}\}^{\uparrow } = \{1.0/a_{m}+1.0/h_{s}\}\).
Hence, \(\{1.0/\textit{o}_{1}+0.5/\textit{o}_{2}+0.25/\textit{o}_{3},1.0/a_{m}+1.0/h_{s}\}\) is a fuzzy formal concept.
-
3.
\((1.0/a_{o})^{\downarrow } = \{0.5/\textit{o}_{1}+1.0/\textit{o}_{3}\}\), \(\{0.5/\textit{o}_{1}+1.0/\textit{o}_{3}\}^{\uparrow } = \{1.0/a_{o}+1.0/h_{m}\}\).
Hence, \(\{0.5/\textit{o}_{1}+1.0/\textit{o}_{3},1.0/a_{o}+1.0/h_{m}\}\) is a fuzzy formal concept.
-
4.
\((1.0/h_{s})^{\downarrow } = \{1.0/\textit{o}_{1}+1.0/\textit{o}_{2}+0.25/\textit{o}_{3}\}\)
\(\{1.0/\textit{o}_{1}+1.0/\textit{o}_{2}+0.25/\textit{o}_{3}\}^{\uparrow } = \{1.0/h_{s}\}\).
Hence, \(\{1.0/\textit{o}_{1}+1.0/\textit{o}_{2}+0.25/\textit{o}_{3},1.0/h_{s}\}\) is a fuzzy formal concept.
-
5.
\((1.0/h_{m})^{\downarrow } = \{0.75/\textit{o}_{1}+0.5/\textit{o}_{2}+1.0/\textit{o}_{3}\}\)
\(\{0.75/\textit{o}_{1}+0.5/\textit{o}_{2}+1.0/\textit{o}_{3}\}^{\uparrow } = \{1.0/h_{m}\}\).
Hence, \(\{0.75/\textit{o}_{1}+0.5/\textit{o}_{2}+1.0/\textit{o}_{3}\}, 1.0/h_{m}\}\) is a fuzzy formal concept.
-
6.
\((1.0/h_{t})^{\downarrow } = \{0.5/\textit{o}_{3}\}\), \(\{0.5/\textit{o}_{3}\}^{\uparrow } = \{1.0/a_{o}+1.0/h_{m}+1.0/h_{t}\}\).
Hence, \(\{0.5/\textit{o}_{3}, 1.0/a_{o}+1.0/h_{m}+1.0/h_{t}\}\) is a fuzzy formal concept.
Step 3. With the help of algorithm Steps 4, 5 and 6 shown in Table 5, we can find the intersection between these generated concepts for generating next concepts (from the fuzzy context shown in Table 4) as follows:
-
1.
\(\{1.0/a_{y}+1.0/h_{s}\}^{\downarrow } = \{0.25/\textit{o}_{1}+1.0/\textit{o}_{2}\}\), \(\{0.25/\textit{o}_{1}+1.0/\textit{o}_{2}\}^{\uparrow } = \{1.0/a_{y}+1.0/h_{s}\}\).
Hence, \(\{0.25/\textit{o}_{1}+1.0/\textit{o}_{2}, 1.0/a_{y}+1.0/h_{s}\}\) is a fuzzy formal concept.
-
2.
\(\{1.0/a_{y}+1.0/a_{m}\}^{\downarrow }= \{0.25/\textit{o}_{1}+0.5/\textit{o}_{2}\}\), \(\{0.25/\textit{o}_{1}+0.5/\textit{o}_{2}\}^{\uparrow } = \{1.0/a_{y}+1.0/a_{m}+1.0/h_{s}+1.0/h_{m}\}\).
Hence, \(\{0.25/\textit{o}_{1}+0.5/\textit{o}_{2}, 1.0/a_{y}+1.0/a_{m}+1.0/h_{s}+1.0/h_{m}\}\) is a fuzzy formal concept.
-
3.
\(\{1.0/a_{y}+1.0/h_{m}\}^{\downarrow }= \{0.25/\textit{o}_{1}+0.5/\textit{o}_{2}\}\), \(\{0.25/\textit{o}_{1}+0.5/\textit{o}_{2}\}^{\uparrow } = \{1.0/a_{y}+1.0/a_{m}+1.0/h_{s}+1.0/h_{m}\}\).
Hence, \(\{0.25/\textit{o}_{1}+0.5/\textit{o}_{2}, 1.0/a_{y}+1.0/a_{m}+1.0/h_{s}+1.0/h_{m}\}\) is a fuzzy formal concept.
-
4.
\(\{1.0/a_{m}+1.0/a_{o}\}^{\downarrow }= \{0.5/\textit{o}_{1}+0.25/\textit{o}_{3}\}\), \(\{0.5/\textit{o}_{1}+0.25/\textit{o}_{3}\}^{\uparrow } = \{1.0/a_{m}+1.0/a_{o}+1.0/h_{s}+1.0/h_{m}\}\).
Hence, \(\{0.5/\textit{o}_{1}+0.25/\textit{o}_{3}, 1.0/a_{m}+1.0/a_{o}+1.0/h_{s}+1.0/h_{m}\}\) is a fuzzy formal concept.
-
5.
\(\{1.0/a_{m}+1.0/h_{s}\}^{\downarrow } = \{1.0/\textit{o}_{1}+0.5/\textit{o}_{2}+0.25/\textit{o}_{3}\}\), \(\{1.0/\textit{o}_{1}+0.5/\textit{o}_{2}+0.25/\textit{o}_{3}\}^{\uparrow } = \{1.0/a_{m}+1.0/h_{s}\}\).
Hence, \(\{1.0/\textit{o}_{1}+0.5/\textit{o}_{2}+0.25/\textit{o}_{3}, 1.0/a_{m}+1.0/h_{s}\}\) is a fuzzy formal concept.
-
6.
\(\{1.0/a_{m}+1.0/h_{m}\}^{\downarrow } = \{0.75/\textit{o}_{1}+0.5/\textit{o}_{2}+ 0.25/\textit{o}_{3}\}\), \(\{0.75/\textit{o}_{1}+0.5/\textit{o}_{2}+0.25/\textit{o}_{3}\}^{\uparrow } = \{1.0/a_{m}+1.0/h_{m}+1.0/h_{s}\}\).
Hence,\(\{0.75/\textit{o}_{1}+0.5/\textit{o}_{2}+0.25/\textit{o}_{3}, 1.0/a_{m}+1.0/h_{m}+1.0/h_{s}\}\) is a fuzzy formal concept.
-
7.
\(\{1.0/a_{o}+1.0/h_{s}\}^{\downarrow } = \{0.5/\textit{o}_{1}+0.25/\textit{o}_{3}\}\), \(\{0.5/\textit{o}_{1}+0.25/\textit{o}_{3}\}^{\uparrow } = \{1.0/a_{o}+1.0/a_{m}+1.0/h_{s}+1.0/h_{m}\}\).
Hence, \(\{0.5/\textit{o}_{1}+0.25/\textit{o}_{3}, 1.0/a_{o}+1.0/a_{m}+1.0/h_{s}+1.0/h_{m}\}\) is a fuzzy formal concept.
-
8.
\(\{1.0/a_{o}+1.0/h_{m}\}^{\downarrow } = \{0.5/\textit{o}_{1}+1.0/\textit{o}_{3}\}\), \(\{0.5/\textit{o}_{1}+0.25/\textit{o}_{3}\}^{\uparrow } = \{1.0/a_{o}+1.0/h_{m}\}\).
Hence, \(\{0.5/\textit{o}_{1}+0.25/\textit{o}_{3}, 1.0/a_{o}+1.0/h_{m}\}\) is a fuzzy formal concept.
-
9.
\(\{1.0/a_{o}+1.0/h_{t}\}^{\downarrow }\)= \(\{0.5/\textit{o}_{3}\}\), \(\{0.5/\textit{o}_{3}\}^{\uparrow } = \{1.0/a_{o}+1.0/h_{m}+1.0/h_{t}\}\).
Hence, \(\{0.5/\textit{o}_{3}, 1.0/a_{o}+1.0/h_{m}+1.0/h_{t}\}\) is a fuzzy formal concept.
-
10.
\(\{1.0/h_{s}+1.0/h_{m}\}^{\downarrow } = \{0.75/\textit{o}_{1}+0.25/\textit{o}_{2}+0.25/\textit{o}_{3}\}\), \(\{0.75/\textit{o}_{1}+0.25/\textit{o}_{2}+0.25/\textit{o}_{3}\}^{\uparrow } = \{1.0/a_{m}+1.0/h_{s}+1.0/h_{m}\}\).
Hence, \(\{0.75/\textit{o}_{1}+0.25/\textit{o}_{2}+0.25/\textit{o}_{3}, 1.0/a_{m}+1.0/h_{s}+1.0/h_{m}\}\) is a fuzzy formal concept.
-
11.
\(\{1.0/h_{s}+1.0/h_{t}\}^{\downarrow } = \{0.25/\textit{o}_{3}\}\), \(\{0.25/\textit{o}_{3}\}^{\uparrow } = \{1.0/a_{m}+1.0/a_{o}+1.0/h_{s}+1.0/h_{m}+1.0/h_{t}\}\).
Hence, \(\{0.25/\textit{o}_{3}, 1.0/a_{o}+1.0/a_{m}+1.0/h_{s}+1.0/h_{m}+1.0/h_{t}\}\) is a fuzzy formal concept.
-
12.
\(\{1.0/a_{o}+1.0/h_{m}+1.0/h_{t}\}^{\downarrow } = \{0.5/\textit{o}_{3}\}\), \(\{0.5/\textit{o}_{3}\}^{\uparrow } = \{1.0/a_{o}+1.0/h_{m}+1.0/h_{t}\}\).
Hence, \(\{0.5/\textit{o}_{3}, 1.0/a_{o}+1.0/h_{m}+1.0/h_{t}\}\) is a fuzzy formal concept.
-
13.
\(\{1.0/a_{m}+1.0/a_{o}+1.0/h_{s}+1.0/h_{m}\}^{\downarrow } = \{0.5/\textit{o}_{1}+0.25/\textit{o}_{3}\}\), \(\{0.5/\textit{o}_{1}+0.25/\textit{o}_{3}\}^{\uparrow } = \{1.0/a_{o}+1.0/a_{m}+1.0/h_{s}+1.0/h_{m}\}\).
Hence, \(\{0.5/\textit{o}_{1}+0.25/\textit{o}_{3}, 1.0/a_{o}+1.0/a_{m}+1.0/h_{m}+1.0/h_{t}\}\) is a fuzzy formal concept.
-
14.
\(\{1.0/a_{y}+1.0/a_{m}+1.0/h_{s}+1.0/h_{m}\}^{\downarrow } = \{0.25/\textit{o}_{1}+0.5/\textit{o}_{2}\}\), \(\{0.25/\textit{o}_{1}+0.5/\textit{o}_{2}\}^{\uparrow } = \{1.0/a_{y}+1.0/a_{m}+1.0/h_{s}+1.0/h_{m}\}\).
Hence, \(\{0.5/\textit{o}_{1}+0.25/\textit{o}_{3}, 1.0/a_{y}+1.0/a_{m}+1.0/h_{s}+1.0/h_{m}\}\) is a fuzzy formal concept.
-
15.
\(\{1.0/a_{m}+1.0/a_{o}+1.0/h_{s}+1.0/h_{m}+1.0/h_{t}\}^{\downarrow } = \{0.25/\textit{o}_{3}\}\), \(\{0.25/\textit{o}_{3}\}^{\uparrow } = \{1.0/a_{m}+1.0/a_{o}+1.0/h_{s}+1.0/h_{m}+1.0/h_{t}\}\).
Hence, \(\{0.25/\textit{o}_{3}, 1.0/a_{m}+1.0/a_{o}+1.0/h_{s}+1.0/h_{m}+1.0/h_{t}\}\) is a fuzzy formal concept.
-
16.
\(\{1.0/a_{y}+1.0/a_{m}+1.0/a_{o}+1.0/h_{s}+1.0/h_{m}\}^{\downarrow }= \{0.25/\textit{o}_{1}\}\), \(\{0.25/\textit{o}_{1}\}^{\uparrow } = \{1.0/a_{y}+1.0/a_{m}+1.0/a_{o}+1.0/h_{s}+1.0/h_{m}\}\).
Hence, \(\{0.25/\textit{o}_{1}, 1.0/a_{y}+1.0/a_{m}+1.0/a_{o}+1.0/h_{s}+1.0/h_{m}\}\) is a fuzzy formal concept.
Step 4. Now there is no intersection between the intents. Then, we have to find an attribute which covers all the objects shown in the fuzzy context of Table 4 using the object intersection algorithm. We can find that there does not exist an attribute in Table 4 which can cover all the objects. We can consider \(\oslash \) (for representing null set) at the place of intent. The last fuzzy formal concept (i.e., the top concept) generated from the fuzzy formal context shown in Table 4 is \(\{1.0/\textit{o}_{1}+1.0/\textit{o}_{2}+1.0/\textit{o}_{3},0.25/a_{m}+0.25/h_{s}+0.5/h_{m}\}\).
All the generated fuzzy formal concepts serially (without repetitions) from Table 4 are as follows:
-
1.
\(\{1.0/\textit{o}_{1}+1.0/\textit{o}_{2}+1.0/\textit{o}_{3},0.25/a_{m}+0.25/h_{s}+0.5/h_{m}\}\)
-
2.
\(\{0.25/\textit{o}_{1}+1.0/\textit{o}_{2},1.0/a_{y}+1.0/h_{s} \}\)
-
3.
\(\{1.0/\textit{o}_{1}+0.5/\textit{o}_{2}+0.25/\textit{o}_{3},1.0/a_{m}+1.0/h_{s}\}\)
-
4.
\(\{0.5/\textit{o}_{1}+1.0/\textit{o}_{3},1.0/a_{o}+1.0/h_{m}\}\)
-
5.
\(\{1.0/\textit{o}_{1}+1.0/\textit{o}_{2}+0.25/\textit{o}_{3},1.0/h_{s}\}\)
-
6.
\(\{0.75/\textit{o}_{1}+0.5/\textit{o}_{2}+1.0/\textit{o}_{3},1.0/h_{m}\}\)
-
7.
\(\{0.5/\textit{o}_{3}, 1.0/a_{o}+1.0/h_{m}+1.0/h_{t}\}\)
-
8.
\(\{0.25/\textit{o}_{1}+0.5/\textit{o}_{2}, 1.0/a_{y}+1.0/a_{m}+1.0/h_{s}+1.0/h_{m}\}\).
-
9.
\(\{0.25/\textit{o}_{1}, 1.0/a_{y}+1.0/a_{m}+1.0/a_{o}+1.0/h_{s}+1.0/h_{m}\}\)
-
10.
\(\{0.5/\textit{o}_{1}+0.25/\textit{o}_{3}, 1.0/a_{m}+1.0/a_{o}+1.0/h_{s}+1.0/h_{m}\}\)
-
11.
\(\{0.75/\textit{o}_{1}+0.5/o_{2}+0.25/o_{3}, 1.0/a_{m}+1.0/h_{s}+1.0/h_{m}\}\)
-
12.
\(\{0.25/\textit{o}_{3}, 1.0/a_{m}+1.0/a_{o}+1.0/h_{s}+1.0/h_{m}+1.0/h_{t}\}\)
-
13.
\(\{0.5/\textit{o}_{2}, 1.0/a_{y}+1.0/a_{m}+1.0/h_{s}+1.0/h_{m}\}\)
-
14.
\(\{\oslash ,1.0/\textit{a}_{y}+1.0/\textit{a}_{m}+1.0/\textit{a}_{o}+1.0/\textit{h}_{s}+1.0/\textit{h}_{m}+1.0/\textit{h}_{t}\}\)
where \(\oslash \) represents null set. The fuzzy concept lattice built through the fuzzy formal concepts generated from Table 4 is shown in Fig. 1.
We can observe that nine, twelve and thirteen concepts are specialized concepts in Fig. 1. It represents \(o_{1}\), \(o_{2}\) and \(o_{3}\) objects which cover maximal number of attributes with membership values 0.25, 0.25 and 0.5, respectively. Similarly, from concept 1, we can conclude that all the objects having age (middle), height (short) and height (medium) with membership values 0.25, 0.25, 0.5, respectively. From the binary context shown in Table 3, the following concepts are generated:
-
1.
\(\{(o_{1}, o_{2}, o_{3}), \oslash \}\)
-
2.
\(\{(o_{3}),( a_{o}, h_{m} )\}\)
-
3.
\(\{(o_{1}),(a_{m}, h_{s})\}\)
-
4.
\(\{(o_{1}, o_{2}),( h_{s})\}\)
-
5.
\(\{(o_{2}),( a_{y}, h_{s} )\}\)
-
6.
\(\{\oslash ,(a_{y}, a_{m}, a_{o}, h_{s}, h_{m}, h_{t})\}\)
where \(\oslash \) represents null set.
All the above generated formal concepts from Table 3 are shown in Fig. 2, which reflects objects \(o_{1}\), \(o_{2}\) and \(o_{3}\) as specialization. We can observe that the fuzzy concept lattice shown in Fig. 1 reflects objects \(o_{1}\), \(o_{2}\) and \(o_{3}\) as specialization with precise membership value (also for its covering attributes). This is one of the major advantages of fuzzy concept lattice to the discovery of knowledge, precisely. In this process, it generates more number of fuzzy formal concepts with small variance of membership value. From above analysis, we can conclude that:
-
A given many-valued context can be transformed into a fuzzy formal context.
-
Fuzzy concept lattice represents the vagueness in data (like ‘young’) more precisely, compared with the concept lattice in crisp setting.
-
The major problem with FCA in the fuzzy setting is that it generates more number of fuzzy formal concepts with small variance in membership value.
To deal with mentioned problems more adequately than fuzzy setting in this paper, we try to link interval-valued fuzzy set, interval-valued fuzzy graph to the concept lattice in the next section.
4 Interval-valued fuzzy graph representation of concept lattice
In this section, we discuss the hierarchical order representation of interval-valued fuzzy attribute in the concept lattice. For this purpose, we propose an algorithm for generating the interval-valued fuzzy formal concepts using the properties of interval-valued fuzzy graph and Galois connection. To measure the knowledge represented by interval-valued fuzzy formal concepts, we propose another method for computing the weight of fuzzy formal concepts using Shannon entropy. Further, we compare the knowledge represented by interval-valued fuzzy formal concepts and Shannon entropy in the given interval [0,1].
4.1 Interval-valued fuzzy graph
Reducing the size of fuzzy concept lattice is addressed as one of the major issue in FCA with fuzzy setting. To encounter this problem, we incorporate interval-valued fuzzy graph into the concept lattice in this paper. For this purpose, we need some facts like fuzzy graph representation of concept lattice (Ghosh et al. 2010), interval-valued fuzzy context (Alcade et al. 2011; Djouadi and Prade 2009), interval-valued fuzzy Galois connection (Djouadi 2011; Zerarga and Djouadi 2012). Other related notions like: interval-valued fuzzy set, fuzzy graph, interval-valued fuzzy graph and its properties are defined below:
Definition 3
An interval-valued fuzzy set is based on interval number on [0, 1]. An interval number D is an interval \([a^{-}\!, a^{+}]\) with 0 \(\le a^{-}\le a^{+}\le \) 1. The interval [a, a] is identified with the number \(a \in \) [0,1]. D [0,1] denotes the set of all interval numbers on [0, 1]. For the interval numbers \(D_{1}=[a^{-}_{1}, b^{+}_{1}]\) and \(D_{2}=[a^{-}_{2}, b^{+}_{2}]\), we can define (Akram and Dudek 2011, 2013):
-
1.
min \((D_{1}, D_{2}) =\) min\(([a^{-}_{1}, b^{+}_{1}],[a^{-}_{2}, b^{+}_{2}])\) = [min(\({a^{-}_{1}, a^{-}_{2}}\)), min(\({b^{+}_{1}, b^{+}_{2}}\))]
-
2.
max\((D_{1}, D_{2}) =\) max\(([a^{-}_{1}, b^{+}_{1}],[a^{-}_{2}, b^{+}_{2}])\) = [max(\({a^{-}_{1}, a^{-}_{2}}\)), max(\({b^{+}_{1}, b^{+}_{2}}\))]
-
3.
\((D_{1}\le D_{2})\) iff \({a^{-}_{1} \le a^{-}_{2}}\) and \({b^{+}_{1} \le b^{+}_{2}}\).
-
4.
\((D_{1} = D_{2})\) iff \({a^{-}_{1} = a^{-}_{2}}\) and \({b^{+}_{1} = b^{+}_{2}}\).
-
5.
kD \( = \) [\(ka^{-}_{1}, kb^{+}_{1}\)] where 0 \(\le \) k \(\le \)1. Then, \((\textit{D} [0,1],\le , \vee ,\wedge )\) is a complete lattice with [0, 0] as the least element and [1,1] as the greatest.
Definition 4
An interval-valued fuzzy set I on V is defined as:
I \(=\left\{ (x,[\mu ^{-}_{I} (x),\mu ^{+}_{I} (x)]):x \in V\right\} \), where \(\mu ^{-}_{I} (x)\) and \(\mu ^{+}_{I} (x)\) are fuzzy subsets of V such that \(\mu ^{-}_{I} (x) \le \mu ^{+}_{I} (x)\) for all \(x\in V\).
The union and intersection between any two interval-valued fuzzy sets I \(=[\mu ^{-}_{I} (x),\mu ^{+}_{I} (x)]\) and J \(=[\mu ^{-}_{J} (x),\mu ^{+}_{J} (x)]\) on V can be defined as (Akram and Dudek 2011, 2013):
-
\(I \bigcup J =\) (x, max(\(\mu ^{-}_{I} (x))\), \(\mu ^{-}_{J} (x))\), max\((\mu ^{+}_{I} (x)\), \(\mu ^{+}_{J} (x))\)), where, \(x \in V\),
-
\(I \bigcap J =\) (x, min(\(\mu ^{-}_{I} (x))\), \(\mu ^{-}_{J} (x))\), min\((\mu ^{+}_{I} (x)\), \(\mu ^{+}_{J} (x))\)), where, \(x \in V\)
The union and intersection of two interval-valued fuzzy sets are also interval-valued fuzzy sets.
Definition 5
Fuzzy Graph (Ghosh et al. 2010): A fuzzy graph T = (V, \(\mu \), \(\rho \)) is a non-empty set V together with a pair of functions \(\mu \): V \(\rightarrow \) [0,1] and \(\rho : V \times V \rightarrow \) [0,1] such that for all x, y in V, \(\rho \)(x,y)\(\le \mu (x)\wedge \mu (y)\), where \(\mu \) is said to be the fuzzy vertex set and \(\rho \) is the fuzzy edges set of T.
Definition 6
An interval-valued fuzzy graph of a graph T \( = \) (V, E) is a pair (I, J) where I \( = \) [\(\mu ^{-}_{I}, \mu ^{+}_{I}\)] is an interval-valued fuzzy set on V and J \( = \) [\(\mu ^{-}_{J}, \mu ^{+}_{J}\)] is an interval-valued fuzzy relation on the set E such that (Akram and Dudek 2011, 2013):
-
1.
\(\mu ^{-}_{J} (xy)\le \) min \((\mu ^{-}_{I} (x),\mu ^{-}_{I} (y))\)
-
2.
\(\mu ^{+}_{J} (xy)\le \) min(\(\mu ^{+}_{I} (x),\mu ^{+}_{I} (y)\)) for all \(xy\in E\).
Example 1
Suppose V \(=\left\{ x, y, z \right\} \) and E \(=\left\{ xy,yz,zx \right\} \) for the interval-valued fuzzy graph of a graph T. Let I be an interval-valued fuzzy set of V and J be an interval-valued fuzzy set of E \(\subseteq \) V \(\times \)V defined by:
We can observe that Fig. 3 represents an interval-valued fuzzy graph of a graph T.
Definition 7
An interval-valued fuzzy graph G is complete iff (Akram and Dudek 2011, 2013; Ranitovic and Petojevic 2013):
-
1.
\(\mu ^{-}_{J} (xy)=\) min(\(\mu ^{-}_{I} (x),\mu ^{-}_{I} (y))\) and
-
2.
\(\mu ^{+}_{J} (xy)=\) min(\(\mu ^{+}_{I} (x),\mu ^{+}_{I} (y)\))
for all \((xy)\in E\).
Example 2
Consider a graph T \( = \) (V, E) such that V \( = \) (x, y, z), E \( = \) (xy, yz, zx). If I and J are interval-valued fuzzy subsets defined by:
-
I \( = \) [(x/0.2, y/0.3, z/0.4), (x/0.4, y/0.5, z/0.5)]
-
J \( = \) [(xy/0.2, yz/0.3, zx/0.2), (xy/0.4, yz/0.5, zx/0.4)]
Then, G \( = \) (I, J) is an interval-valued fuzzy complete graph of T. Hence, we can conclude that concept lattice can be represented through interval-valued fuzzy graph containing interval-valued fuzzy formal concepts. In the next section, we provide an illustrative example for the proposed link.
4.2 Proposed algorithm for generating interval-valued fuzzy formal concepts
In this section, we discuss an algorithm for generating interval-valued fuzzy formal concepts using the properties of interval-valued fuzzy set and Galois connection as follows: Let a fuzzy formal context \(\mathbf K = (\textit{O}, \textit{P}\), \(\tilde{R}\)) and \(\textit{subb} (\textit{o}) = \left\{ o_{i},[\mu ^{-}_{\tilde{R}} (o), \mu ^{+}_{\tilde{R}}(o)]\right\} \) and \(\textit{subb}(\textit{p}) = \left\{ p_{j},[\mu ^{-}_{\tilde{R}} (p), \mu ^{+}_{\tilde{R}} (p)]\right\} \) are two connected components in the interval-valued fuzzy graph representation of concept lattice, where subb is used for representing subset. Then, a pair–[(\(o_{i}\), [\(\mu ^{-}_{\tilde{R}} (o),\mu ^{+}_{\tilde{R}}(o)\)]), (\(p_{j}\), [\(\mu ^{-}_{\tilde{R}} (p),\mu ^{+}_{\tilde{R}}(p)\)])] is called as interval-valued fuzzy formal concept iff (\(o_{i}\), [\(\mu ^{-}_{\tilde{R}} (o)\),\(\mu ^{+}_{\tilde{R}}(o)\)]) \( = \) (\(subb(p))^{\downarrow }\) and \((p_{j},[\mu ^{-}_{\tilde{R}} (p),\mu ^{+}_{\tilde{R}}(p)])\!=\!(subb(o))^{\uparrow }\). The membership value can be considered as [1.0, 1.0] for each subset of attributes (P) to apply the Galois connection on the subset of attributes \((p_{j}, [\mu ^{-}_{\tilde{R}} (p),\mu ^{+}_{\tilde{R}}(p)])^{\downarrow }\) which provide the covering objects \((o_{i}, [\mu ^{-}_{\tilde{R}} (o),\mu ^{+}_{\tilde{R}}(o)])\). The membership value of these obtained objects can be computed using the properties of interval-valued fuzzy set and Godel operator as min (\(o_{i},\mu ^{-}_{\tilde{R}} (o)\)) and max (\(o_{i},\mu ^{+}_{\tilde{R}} (o)\)). Subsequently, the Galois connection on these obtained objects \((o_{i}, [\mu ^{-}_{\tilde{R}} (o),\mu ^{+}_{\tilde{R}}(o)])^{\uparrow }\) integrate the maximum attributes covering these objects. i.e if any other extra attribute suppose z \(\in P\) covers the obtained objects \((o_{i}, [\mu ^{-}_{\tilde{R}} (o),\mu ^{+}_{\tilde{R}}(o)])\) then \(p_{j}=(\textit{z} \cup p_{j})\). Similarly, we can find the interval-valued fuzzy formal concepts for each subset of attributes—\(p_{j}\in P\). The generated interval-valued fuzzy formal concepts represent in (FC \(_\mathbf{{K} }\)). These steps can be formulated as an algorithm shown in Table 7.
The proposed algorithm (shown in Table 7) starts investigating the interval-valued concepts for each subsets of given attributes in a fuzzy formal context K with membership value [1.0, 1.0] (using Steps 1 to 3). The covering objects for these attributes are investigated using Galois connection (\(\downarrow \)) (using Step 4). The membership value of obtained objects (extent) is computed by a defined min operator (for lower bound) and a max operator (for upper bound) (using Step 5). Consequently, the operator (\(\downarrow \)) is applied on the fuzzy set constituted by these covered objects resulting from integrating the membership information between objects and attributes (using Step 6). It provides a fuzzy set of attributes with its membership value being maximal with respect to integrating the information from the objects (Using steps 6 to 10)). These steps are repeated for every subset of attributes. The generated interval-valued fuzzy formal concepts are stored in the set (FC \(_\mathbf{{K} }\)) (using step 11). The proposed algorithm uses subset of attributes for generating the inter-valued fuzzy formal concepts which helps in representing them in a hierarchical order.
Complexity: Suppose, number of objects(\(|O|\)) = n and number of attributes \((|P|)\) = m in the given fuzzy formal context. Finding the subset of attribute (P) takes \(2^{m}\) complexity. To combine the covering objects with subset of attributes takes total complexity O(\(2^{m} *n\)). The generated interval-valued fuzzy formal concepts using proposed method contain the fuzzy set of objects and attributes whose membership values are in the computed interval [0, 1]. In this way, the proposed algorithm reduces the number of fuzzy formal concepts and its complexity when compared to the fuzzy setting. We can observe that the proposed algorithm is based on the power set of given attributes and it is computationally expensive for medium or large databases. So, the proposed algorithm only serves as a basis for many opportunities for further development.
4.3 Concept lattice reduction using interval-valued fuzzy graph
For the illustration, we have considered a fuzzy formal context (or complete context) shown in Table 8 (Ghosh et al. 2010). First, we describe the fuzzy graph representation of concept lattice to demonstrate its interval-valued fuzzy graph representation.
The fuzzy formal concepts generated from the fuzzy formal context shown in Table 8 are (Ghosh et al. 2010):
-
1.
\(\{\oslash ,1.0/\textit{p}_{1}+1.0/\textit{p}_{2}+1.0/\textit{p}_{3}+1.0/\textit{p}_{4}+1.0/\textit{p}_{5}+1.0/\textit{p}_{6}\}\)
-
2.
\(\{0.5/\textit{o}_{1},1.0/\textit{p}_{2}+1.0/\textit{p}_{3}+1.0/\textit{p}_{4}+1.0/\textit{p}_{5}\}\)
-
3.
\(\{1.0/\textit{o}_{2},1.0/\textit{p}_{1}+1.0/\textit{p}_{2}+1.0/\textit{p}_{3}\}\)
-
4.
\(\{0.5/\textit{o}_{3},1.0/\textit{p}_{1}+1.0/\textit{p}_{2}+1.0/\textit{p}_{6}\}\)
-
5.
\(\{0.5/\textit{o}_{1}+ 0.5/\textit{o}_{5},1.0/\textit{p}_{3}+1.0/\textit{p}_{4}\}\)
-
6.
\(\{0.5/\textit{o}_{1}+ 0.5/\textit{o}_{4},1.0/\textit{p}_{4}+1.0/\textit{p}_{5}\}\)
-
7.
\(\{1.0/\textit{o}_{1},1.0/\textit{p}_{2}+0.5/\textit{p}_{3}+0.5/\textit{p}_{4}+1.0/\textit{p}_{5}\}\)
-
8.
\(\{0.5/\textit{o}_{1}+1.0/\textit{o}_{2},1.0/\textit{p}_{2}+1.0/\textit{p}_{3}\}\)
-
9.
\(\{1.0/\textit{o}_{2}+0.5/\textit{o}_{3},1.0/\textit{p}_{1}+1.0/\textit{p}_{2}\}\)
-
10.
\(\{1.0/\textit{o}_{3},0.5/\textit{p}_{1}+0.5/\textit{p}_{2}+1.0/\textit{p}_{6}\}\)
-
11.
\(\{0.5/\textit{o}_{1}+1.0/\textit{o}_{5},1.0/\textit{p}_{3}+0.5/\textit{p}_{4}\}\)
-
12.
\(\{0.5/\textit{o}_{1}+1.0/\textit{o}_{4},1.0/\textit{p}_{4}+0.5/\textit{p}_{5}\}\)
-
13.
\(\{1.0/\textit{o}_{1}+0.5/\textit{o}_{4},0.5/\textit{p}_{4}+1.0/\textit{p}_{5}\}\)
-
14.
\(\{1.0/\textit{o}_{1}+1.0/\textit{o}_{5},0.5/\textit{p}_{3}+0.5/\textit{p}_{4}\}\)
-
15.
\(\{0.5/\textit{o}_{1}+1.0/\textit{o}_{2}+1.0/\textit{o}_{5},1.0/\textit{p}_{3}\}\)
-
16.
\(\{1.0/\textit{o}_{1}+1.0/\textit{o}_{2},1.0/\textit{p}_{2}+0.5/\textit{p}_{3}\}\)
-
17.
\(\{1.0/\textit{o}_{2}+0.5/\textit{o}_{3}+0.5/\textit{o}_{6},1.0/\textit{p}_{1}\}\)
-
18.
\(\{1.0/\textit{o}_{2}+1.0/\textit{o}_{3},0.5/\textit{p}_{1}+0.5/\textit{p}_{2}\}\)
-
19.
\(\{0.5/\textit{o}_{1}+1.0/\textit{o}_{4}+0.5/\textit{o}_{5},1.0/\textit{p}_{4}\}\)
-
20.
\(\{1.0/\textit{o}_{1}+1.0/\textit{o}_{4},0.5/\textit{p}_{4}+0.5/\textit{p}_{5}\}\)
-
21.
\(\{1.0/\textit{o}_{1}+1.0/\textit{o}_{2}+1.0/\textit{o}_{5},0.5/\textit{p}_{3}\}\)
-
22.
\(\{1.0/\textit{o}_{1}+1.0/\textit{o}_{2}+0.5/\textit{o}_{3},1.0/\textit{p}_{2}\}\)
-
23.
\(\{1.0/\textit{o}_{1}+1.0/\textit{o}_{4}+1.0/\textit{o}_{5},0.5/\textit{p}_{4}\}\)
-
24.
\(\{1.0/\textit{o}_{1}+1.0/\textit{o}_{2}+1.0/\textit{o}_{3},0.5/\textit{p}_{2}\}\)
-
25.
\(\{1.0/\textit{o}_{2}+1.0/\textit{o}_{3}+1.0/\textit{o}_{6},0.5/\textit{p}_{1}\}\)
-
26.
\(\{1.0/\textit{o}_{1}+1.0/\textit{o}_{2}+1.0/\textit{o}_{3}+1.0/\textit{o}_{4}+1.0/\textit{o}_{5}+1.0/\textit{o}_{6},\oslash \}\)
where \(\oslash \) represents null set.
The fuzzy concept lattice for the above generated concepts is shown in Fig. 4, which represents that:
-
Generalized concepts are 21, 23, 24, and 25 which reflect attributes \(\textit{p}_{3}\), \(\textit{p}_{4}\), \(\textit{p}_{2}\), and \(\textit{p}_{1}\), respectively.
-
Specialized concepts are 2, 3 and 4 which reflect objects \(\textit{o}_{1}\), \(\textit{o}_{2}\), and \(\textit{o}_{3}\), respectively.
Interval-valued fuzzy formal concepts of Table 8 as per the proposed link:
-
1.
\(\{\oslash ,[1.0, 1.0]/\textit{p}_{1}+[1.0, 1.0]/\textit{p}_{2}+[1.0, 1.0]/\textit{p}_{3}+[1.0, 1.0]/\textit{p}_{4}+[1.0, 1.0]/\textit{p}_{5}+[1.0, 1.0]/\textit{p}_{6}\}\)
-
2.
\(\{[0.5, 1.0]/\textit{o}_{1},[1.0, 1.0]/\textit{p}_{2}+[0.5,1.0]/\textit{p}_{3}+[0.5,1.0]/\textit{p}_{4}+[1.0, 1.0]/\textit{p}_{5}\}\)
-
3.
\(\{[1.0, 1.0]/\textit{o}_{2},[1.0, 1.0]/\textit{p}_{1}+[1.0, 1.0]/\textit{p}_{2}+[1.0,1.0]/\textit{p}_{3}\}\)
-
4.
\(\{[0.5,1.0]/\textit{o}_{3},[0.5,1.0]/\textit{p}_{1}+[0.5,1.0]/\textit{p}_{2}+[0.1, 1.0]/\textit{p}_{6}\}\)
-
5.
\(\{[0.5, 1.0]/\textit{o}_{1}+ [0.5,1.0]/\textit{o}_{2},[0.5, 1.0]/\textit{p}_{2}+[0.5, 1.0]/\textit{p}_{3}\}\)
-
6.
\(\{[0.5, 1.0]/\textit{o}_{1}+ [0.5, 1.0]/\textit{o}_{4},[0.5,1.0]/\textit{p}_{4}+[0.5,1.0]/\textit{p}_{5}\}\)
-
7.
\(\{[0.5, 1.0]/\textit{o}_{2}+[0.5, 1.0]/\textit{o}_{3},[0.5,1.0]/\textit{p}_{1}+[0.5, 1.0]/\textit{p}_{2}\}\)
-
8.
\(\{[0.5,0.5]/\textit{o}_{1}+[1.0,1.0]/\textit{o}_{5},[1.0,1.0]/\textit{p}_{3}+[0.5,1.0]/\textit{p}_{4}\}\)
-
9.
\(\{[0.5,1.0]/\textit{o}_{1}+[0.5, 1.0]/\textit{o}_{5},[0.5,1.0]/\textit{p}_{3}+[0.5,1.0]/\textit{p}_{4}\}\)
-
10.
\(\{[0.5,1.0]/\textit{o}_{1} +[1.0,1.0]/\textit{o}_{2}+[1.0,1.0]/\textit{o}_{5},[0.5, 1.0]/\textit{p}_{3}\}\)
-
11.
\(\{[0.5, 1.0]/\textit{o}_{1}+[1.0, 1.0]/\textit{o}_{4}+[0.5,1.0]/\textit{o}_{5},[0.5, 1.0]/\textit{p}_{4}\}\)
-
12.
\(\{[1.0, 1.0]/\textit{o}_{1}+[1.0,1.0]/\textit{o}_{2}+[0.5,1.0]/\textit{o}_{3},[0.5,1.0]/\textit{p}_{2}\}\)
-
13.
\(\{[1.0, 1.0]/\textit{o}_{2}+[0.5, 1.0]/\textit{o}_{3}+[0.5,1.0]/\textit{o}_{6},[0.5, 1.0]/\textit{p}_{1}\}\)
-
14.
\(\{[1.0, 1.0]/\textit{o}_{1}+[1.0, 1.0]/\textit{o}_{2}+[1.0,1.0]/\textit{o}_{3}+[1.0,1.0]/\textit{o}_{4}+[1.0,1.0]/\textit{o}_{5}+[1.0,1.0]/\textit{o}_{6},\oslash \}\)
The fuzzy concept lattice obtained from the above generated fuzzy formal concepts is shown in Fig. 5, which represents that:
-
Generalized concepts are 10, 11, 12 and 13 which reflect attributes \(\textit{p}_{3}\), \(\textit{p}_{4}\), \(\textit{p}_{2}\) and \(\textit{p}_{1}\), respectively.
-
Specialized concepts are 2, 3 and 4 which reflect objects \(\textit{o}_{1}\), \(\textit{o}_{2}\) and \(\textit{o}_{3}\), respectively.
We can observe that the reduced lattice using interval-valued fuzzy graph (shown in Fig. 5) preserves the specialization and generalization as shown in its original lattice( shown in Fig. 4).
We believe that incorporation of interval-valued fuzzy graph to the concept lattice can be helpful for the researchers in the various fields like information retrieval (Aswani Kumar et al. 2012; Li et al. 2013), handling incomplete data (Burmeister and Holzer 2005; Krupka and Lastovica 2012; Li et al. 2013), semantic web (Formica 2010; Maio et al. 2012) and concept lattice reduction (Aswani Kumar and Srinivas 2010a; Dias and Viera 2013; Konecny and Krupka 2011). In the next section, we provide one of the application of the proposed method for handling incomplete data in the given context with an illustrative example.
4.4 Application of the interval-valued fuzzy formal concepts
To illustrate the need of interval-valued fuzzy set in FCA, we have considered a binary context shown in Table 9 (Bache and Lichman 2013). The mark (?) shown in Table 9 represents that information is not available or specially called as incomplete formal context (Burmeister and Holzer 2005; Djouadi and Prade 2009; Dubois and Prade 2012; Krupka and Lastovica 2012; Li et al. 2013). This context can be transformed into a fuzzy formal context through a defined membership value as shown in Table 10. Still this extension cannot be able to represent incomplete information (ex. between (\(o_2\), \(p_2\)) precisely. Recently, (Li et al. 2013) provided a thorough analysis for handling the incomplete contexts. Another method is to fuzzify the information between objects and attributes into interval [0, 1] and represent them with the help of interval-valued fuzzy set. This extension of fuzzy set theory provides us a way to write the relation between objects and attributes in the interval [0, 1] as well as for incomplete information (shown in Table 11) and why it is necessary is discussed by Djouadi and Prade (2009). Thereafter, our study starts that how to analyze the interval-valued fuzzy formal context through their basic notions like interval-valued fuzzy formal concepts and their visualization in the concept lattice.
For the analysis of interval-valued fuzzy formal context hierarchical order is needed. This can be achieved through partition tree obtained by \(\alpha \)-cut as described by Guh et al. (2009). Another representation is through the concept lattice in which formal concepts are represented through interval-valued fuzzy set. This representation can be possible through the help of interval-valued fuzzy graph and its properties which have been recently discussed by Akram and Dudek (Akram and Dudek 2011, 2013). In this study, we discussed another representation of concept lattice through interval-valued fuzzy graph.
The interval-valued fuzzy formal concepts generated from Table 11 (as per the proposed algorithm shown in Table 7) are:
-
1.
\(\{\oslash ,[1.0, 1.0]/\textit{p}_{1}+[1.0, 1.0]/\textit{p}_{2}+[1.0, 1.0]/\textit{p}_{3}\}\),
-
2.
\(\{ [0.9,1.0]/\textit{o}_{1}+[0.8,1.0]/\textit{o}_{2}+[0.3, 0.6]/\textit{o}_{3}+[0.2, 0.4]/\textit{o}_{4}, [1.0, 1.0]/\textit{p}_{1}\}\),
-
3.
\(\{ [0.5, 0.7]/\textit{o}_{1}+[0.0,1.0]/\textit{o}_{2}+[1.0,1.0]/\textit{o}_{3}+[0.6,1.0]/\textit{o}_{4},[1.0, 1.0]/\textit{p}_{2}\}\),
-
4.
\(\{ [0.0, 0.2]/\textit{o}_{1}+[0.5, 0.5]/\textit{o}_{2}+[0.8, 0.8]/\textit{o}_{3}+[0.0, 0.1]/\textit{o}_{4}, [1.0, 1.0]/\textit{p}_{3}\}\),
-
5.
\(\{ [0.5, 1.0]/\textit{o}_{1}+[0.0, 1.0]/\textit{o}_{2}+[0.3, 1.0]/\textit{o}_{3}+[0.2, 1.0]/\textit{o}_{4}, [1.0, 1.0]/\textit{p}_{1}+[1.0, 1.0]/\textit{p}_{2}\}\),
-
6.
\(\{ [0.0, 1.0]/\textit{o}_{1}+[0.5, 1.0]/\textit{o}_{2}+[0.3, 0.8]/\textit{o}_{3}+[0.0, 0.4]/\textit{o}_{4}, [1.0, 1.0]/\textit{p}_{1}+[1.0, 1.0]/\textit{p}_{3}\}\),
-
7.
\(\{ [0.0, 0.2]/\textit{o}_{1}+[0.0, 1.0]/\textit{o}_{2}+[0.8, 1.0]/\textit{o}_{3}+[0.0, 1.0]/\textit{o}_{4}, [1.0, 1.0]/\textit{p}_{2}+[1.0, 1.0]/\textit{p}_{3}\}\),
-
8.
\(\{[1.0, 1.0]/\textit{o}_{1}+[1.0, 1.0]/\textit{o}_{2} + [1.0, 1.0]/\textit{o}_{3}+[1.0, 1.0]/\textit{o}_{4}, \oslash \}\).
For the above generated concepts, interval-valued fuzzy graph representation of concept lattice is shown in Fig. 6, which provides hierarchical order between the objects and attributes. Thus, we can analyze that:
-
(a)
For masters course \({p}_{1}\), object \({o}_{1}\) satisfies 0.9 to 1.0 membership value, \({o}_{2}\) satisfies 0.8 to 1.0 membership value, \({o}_{3}\) satisfies 0.3 to 0.6 membership value and \({o}_{4}\) satisfies 0.2 to 0.4 membership value as shown by concept 2.
-
(b)
For masters course \({p}_{2}\), object \({o}_{1}\) satisfies 0.5 to 0.7 membership value, \({o}_{2}\) satisfies 0.0 to 1.0 membership value, \({o}_{3}\) satisfies 1.0 membership value and \({o}_{4}\) satisfies 0.6 to 1.0 membership value as shown by concept 3.
Similar analysis can be derived from other interval-valued fuzzy formal concepts and its lattice structure.
From the above analysis, we can conclude that:
-
The proposed algorithm can be used for generating interval-valued fuzzy formal concepts.
-
Interval-valued fuzzy formal context represents the data more adequate than fuzzy set.
-
Interval-valued fuzzy graph can be used for simplifying the size of concept lattice structure.
-
Interval-valued fuzzy concept lattice can be used for incomplete information systems and for other data mining applications.
In future, the proposed method can be extended for handling bipolar information in the concept lattice (Singh and Aswani Kumar 2014c). To measure the importance of obtained interval-valued fuzzy formal concepts in the next section, we propose an algorithm based on Shannon entropy. After that we have compared the knowledge discovered from both the methods.
4.5 Entropy-based-weighted fuzzy concept lattice
Recently, entropy-based formula is used for weighted concept lattice and its reduction (Li et al. 2013). In this section, we are introducing it into fuzzy concept lattice. This method reduces the fuzzy formal concepts at different threshold (\(\theta \)) for weight of intent in the interval [\(\theta _{1},\) \(\theta _{2}\)] where 0 \(\le \) \(\theta _{1}\) \(\le \) \(\theta _{2}\) \(\le \) 1 as follows:
Let us consider any object \(o_{i}\in O\) of given fuzzy formal context F. Then the probability (P) of \(i\)-th-object (\(o_{i}\)) possessing the corresponding \(j\)-th-attribute (\(p_{j}\)) can be computed by P\((p_{j}/o_{i})\). The average information weight of object (\(O\)) can be represented by \(E(p_{i})\) followed by its total weight \(w_{j}\). These notions can be computed as follows:
-
1.
\(E(p_{j})=-\sum ^{m}_{j=1}\) P\((p_{j}/o_{i})\) log\(_{2}\)(P\((p_{j}/o_{i}))\), where, \(m\) represents the total number of attributes in the given context F.
-
2.
\(w_{j}= E(p_{j})/ \sum ^{j=1}_{m}E(p_{j}) \).
-
3.
Weight\((B)=\sum (w_j)/m\), where \(B\) is the intent.
To explore the deviation of \(w_{j}\) from \(p_j\), we need to evaluate \(D(p_j)\) as follows:
-
4.
\(D(p_j)=\sqrt{(\sum (w_{j}-\mathrm{weight}(p_j)))/m}\), where \(D(p_j)\) denotes the deviation of the multi-attribute intent value. The deviation of a formal concept provides absolute difference from computed weight of the formal concepts. It provides us a maximum and minimum deviation of each formal concepts to decide their importance. If \(m=1\) then \(\sum (w_{j}-\mathrm{weight}(p_j)) =0\). Similarly, we can compute for other value of \(m\) also.
Table 12 shows the computed weight value for all the attributes of given fuzzy context shown in Table 8. Table 13 shows the weight value for each intent of given node in Fig. 4. We can observe that the concepts can be selected using different threshold of interval as shown in Table 14.
We can observe that the entropy-based-weighted method provides less number of fuzzy formal concepts at different threshold as shown in Table 14.
The steps for the removal of formal concept at chosen threshold are defined in Table 15. Proposed algorithm first computes the weight of each attribute (through steps 1 to 5). The weight of each formal concepts is computed by sum of their intent (extent) to arrange them together based on their computed weight (through steps 6 to 8). The weighted fuzzy formal concept can be removed whose weight is out of the chosen threshold \(0 \le \theta _{1} \le \theta _{2} \le 1\) (through steps 9 to 11). The proposed algorithm selects the concepts having higher weight than the chosen threshold and removes the remaining fuzzy formal concepts.
Complexity: The proposed algorithm shown in Table 15 is based on average weight of intent or extent which takes O (\(m \ln (m)\)) or O (\(n \ln (n)\)) complexity where \(m\) is number of attributes and \(n\) is number of objects in the formal context.
4.6 Comparison
In this study, we discussed that interval-valued fuzzy graph representation of concept lattice reduces the size of given fuzzy concept lattice in the given interval [0, 1]. However, there are few methods being discussed for reducing the size of fuzzy concept lattice based on hedges (Belohlavek and Vychodil 2005), triangular decomposition (Belohlavek 2009), granulation (Kang et al. 2012; Singh and Aswani Kumar 2012c), block relations (Konecny and Krupka 2011), entropy-based (Li et al. 2013), Levenshtein distance (Ma et al. 2013) and fuzzy homomorphism (Singh and Aswani Kumar 2014b). To compare the knowledge representation using interval-valued fuzzy graph, we have considered entropy-based-weighted concept lattice (Li et al. 2013) which provides the concepts in the user-defined interval [0, 1]. For this purpose, we have introduced entropy-based method in FCA with fuzzy setting for fuzzy concept lattice reduction in this paper (as illustrated in Sect. 4.5). In this section, we show the comparison of knowledge represented by entropy-based-weighted fuzzy concepts and interval-valued fuzzy formal concepts as given below:
We can observe that following concepts are obtained from Fig. 4 at threshold \(0.0946<w \le 0.0974\): 1, 2, 3, 4, 5, 8, 9, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 as given in Table 14. If we compare the knowledge (intent) represented by these concepts with interval-valued fuzzy formal concepts, then we can be able to decide the importance of concepts. Table 16 depicts the comparison between the fuzzy concepts from both the proposed methods (shown in Tables 7 and 15), where the first column represents concepts intent extracted through entropy-based method and the second column its corresponding interval-valued fuzzy formal concepts.
We can observe that the knowledge (intent) represented by interval-valued fuzzy formal concepts and entropy-based-weighted concepts is the same. However, interval-valued fuzzy formal concepts represent less number of concepts with more adequate description and entropy-based concepts take less complexity to compute the weight.
5 Discussions
FCA is a well-established mathematical model for knowledge discovery and representation tasks (Poelmans et al. 2013a, b). For handling uncertainty and vagueness in data, FCA was extended from crisp to fuzzy setting. Computing all the fuzzy formal concepts and their hierarchical order visualization in the concept lattice structure is an important concern for practical applications of FCA. In this paper, we focused on analysis of fuzziness in a given many-valued context, step-by-step generation of fuzzy formal concepts and their lattice structure using a many-valued context (shown in Table 2) (Bache and Lichman 2013). We can observe that the given many-valued context shown in Table 2 is represented precisely through the fuzzy formal context shown in Table 4. However, the crisp formal context shown in Table 3 is a special case of fuzzy formal context shown in Table 4 for a defined threshold=1.0. We can observe that the fuzzy concept lattice shown in Fig. 1 represents the knowledge (formal concepts) precisely than crisp concept lattice shown in Fig. 2. In the process of fuzzy formal concept generation, we can identify following problems:
-
FCA with fuzzy setting generates huge number of fuzzy formal concepts for small variance of membership value and
-
The size of concept lattice constructed from a large context becomes impractical and complex. In this case, the problem is how to simplify the size of fuzzy concept lattice visualization for knowledge-processing tasks.
To solve above-mentioned problems, several methods have been introduced (Belohlavek and Vychodil 2005; Kang et al. 2012; Konecny and Krupka 2011; Shao et al. 2007). Aswani Kumar and Srinivas (Aswani Kumar and Srinivas 2010a, b) discussed about fuzzy K-means clustering and SVD decomposition. Belohlavek (2007) has provided more attention to the issue using hedges (Belohlavek and Vychodil 2005), optimal triangular decomposition (Belohlavek 2009), fast factorization (Belohlavek et al. 2007), and similarity method (Belohlavek and Krupka 2009). Dias and Viera (2013) proposed JBOS reduction method for knowledge extraction. Li and Jhang (2010) replaced Lukasiewicz implication using T-implication for attribute reduction discussed by Elloumi et al. (2004). Mi et al. (2010) has presented attribute reduction through axialities. (Singh and Aswani Kumar 2014a, b) introduced a fuzzy homomorphism map and crisp order for given fuzzy formal context.
To deal with the mentioned problems in this paper, we have established the link between interval-valued fuzzy graph and concept lattice. Interval-valued fuzzy set is an extension of traditional fuzzy set which represents membership degrees in the form of intervals [0, 1] (Akram and Dudek 2011). It provides more precise description of uncertainty and vagueness than fuzzy setting. For this purpose, Singh and Aswani Kumar (2012b) incorporated interval-valued fuzzy graph into concept lattice. After that and recently Ranitovic and Petojevic (2013) studied lattices of interval-valued fuzzy sets. These studies provide us a motivation to establish the interval-valued fuzzy graph representation of concept lattice for simplifying the size of fuzzy concept lattice structure. The current paper is different from any other available approaches in the following aspects:
-
(1)
The paper provides an understanding for fuzziness in given context, its advantages and problems.
-
(2)
The paper reduces the size of concept lattice using the properties of interval-valued fuzzy graph.
-
(3)
The proposed algorithm (shown in Table 7) generates the interval-valued fuzzy formal concepts using the properties of interval-valued fuzzy set and Galois connection.
-
(4)
The proposed algorithm shown in Table 15 computes the weight of the given fuzzy formal concepts using Shannon entropy.
To understand the representation of concept lattice through interval-valued fuzzy graph, we have considered a fuzzy formal context shown in Table 8. We can observe that interval-valued fuzzy graph simplifies the fuzzy concept lattice while preserving specialized and generalized concepts. Now the question arises that what is the necessity to incorporate interval-valued fuzzy set into FCA. To elaborate this need, we have considered a context shown in Table 9 (Bache and Lichman 2013) representing incomplete (?) information between \((o_2, p_2)\). The context shown in Table 9 can be transformed into a fuzzy formal context shown in Table 10 using a membership value between [0, 1]. We can observe that extension of FCA in the fuzzy setting is also unable to represent incomplete information. Very recently, Li et al. (2013) discussed a method for handling incomplete information in decision formal context whereas Krupka and Lastovicka (Krupka and Lastovica 2012) in fuzzy formal context. Except these methods another approach is to use an interval-valued fuzzy set for the representation of fuzzy attributes (as shown in Table 11) (Djouadi and Prade 2009). Now, our analysis starts that how to analyze the interval-valued fuzzy formal context shown in Table 11 through its generated interval-valued fuzzy formal concepts and lattice structure. For this purpose, we have proposed an algorithm for generating the interval-valued fuzzy formal concepts (as shown in Table 7). Some of the interval-valued fuzzy formal concepts generated from Table 11 using the proposed algorithm are compared with Djouadi and Prade Djouadi and Prade (2009), we observe that they provide similar analysis. Further, the proposed algorithm provides remaining concepts and their hierarchical order of the generated interval-valued fuzzy formal concepts.
For the comparison of knowledge represented by interval-valued fuzzy formal concepts, we have introduced a method to compute the weight of formal concepts in the fuzzy setting. The reason is that entropy-based-weighted fuzzy formal concepts provide best possible measurement of uncertainty in the given concepts (in the interval [0, 1] as shown in Table 15). Table 16 shows the comparative study of the knowledge represented by each formal concepts obtained by interval-valued fuzzy graph and entropy-based-weighted method in the given interval [0,1]. We can observe that the knowledge (intent) represented by interval-valued fuzzy formal concepts and obtained concepts through entropy-based-weighted method provides good agreement. However, interval-valued fuzzy formal concepts provide less number of concepts with their lattice visualization. We can conclude that interval-valued fuzzy graph can be used for adequate representation of fuzzy formal concepts and reducing the size of concept lattice structure whereas entropy-based concepts can be used for finding the interested concepts at defined threshold. In future, the proposed method can be extended for handling bipolar information and its representation in the concept lattice.
It is hoped that proposed approaches in this study will be helpful for the researchers in the various fields such as association rule mining (Aswani Kumar 2012; Li et al. 2013; Li and Jhang 2010; Zhai et al. 2012), information retrieval (Aswani Kumar et al. 2012; Guh et al. 2009), handling incomplete data (Burmeister and Holzer 2005; Djouadi and Prade 2009; Dubois and Prade 2012), semantic web (Formica 2010; Maio et al. 2012; Nguyen et al. 2012) and concept lattice reduction (Aswani Kumar and Srinivas 2010a; Dias and Viera 2013; Gely 2011; Ma et al. 2013) for knowledge-processing tasks (Poelmans et al. 2013a, b).
6 Conclusions
In this paper, we aimed at providing a better understanding of fuzziness into the given many-valued formal context and demonstrated the generation of fuzzy formal concepts. In this process, the major issue is reducing the number of fuzzy formal concepts and size of concept lattice. To overcome it, we introduced interval-valued fuzzy graph representation of concept lattice as well as entropy-based-weighted fuzzy formal concepts. Summary of the study is as follows:
-
An algorithm has been proposed for generating the interval-valued fuzzy formal concepts using the properties of interval-valued fuzzy graph and Galois connection.
-
An algorithm has been proposed for computing the weight of fuzzy formal concepts using Shannon entropy.
-
The knowledge represented by the reduced lattice using interval-valued fuzzy graph and entropy-based-weighted concepts is similar at some thresholds. Further, interval-valued fuzzy graph provides adequate description of fuzzy formal concepts with their hierarchical order visualization in the concept lattice.
References
Akram M, Dudek WA (2011) Interval-valued fuzzy graphs. Comput Math Appl 61:289–299
Akram M, Dudek WA (2013) Intuitionistic fuzzy hypergraphs with applications. Inf Sci 218:182–193
Alcade C, Burusco A, Fuentes-Gonzales R (2011) The use of linguistics variables and fuzzy propositions in the L-fuzzy concepts theory. Comput Math Appl 62:3112–3122
Aswani Kumar C, Srinivas S (2010) Concept lattice reduction from fuzzy K-means clustering. Expert Syst Appl 37(3):2696–2704
Aswani Kumar C, Srinivas S (2010) Mining associations in health care data using formal concept analysis and singular value decomposition. J Biol Syst 18(4):787–807
Aswani Kumar C (2011) Knowledge discovery in data using formal concept analysis and random projections. Int J Appl Math Comput Sci 21(4):745–756
Aswani Kumar C (2012) Fuzzy clustering based formal concept analysis for association rules mining. Appl Artif Intell 26(3):274–301
Aswani Kumar C, Radavansky M, Annapurna J (2012) Analysis of vector space model, latent semantic indexing and formal concept analysis for information retrieval. Cybern Inf Technol 12(1):34–48
Aswani Kumar C, Singh PK (2014) Knowledge representation using formal concept analysis: a study on concept generation. IGI Global Publishers, Global trends in knowledge representation and computational intelligence, pp 306–336
Ayouni S, Yahia SB, Laurent A (2011) Extracting compact and information lossless sets of fuzzy association rules. Fuzzy Sets Syst 183(1):1–25
Bache K, Lichman M (2013) UCI machine learning repository http://archive.ics.uci.edu/ml. Irvine CA, University of California, School of information and computer science
Belohlavek R (2009) Optimal triangular decompositions of matrices with entries from residuated lattices. Int J Approx Reason 50(8):1250–1258
Belohlavek R (1998) Lattice generated by binary fuzzy relations. In: Proceedings of 4th international conference on fuzzy sets theory and applications, Liptovsky Jan Slovakia, pp 11–19
Belohlavek R (1999) Fuzzy Galois connection. Math Logic Q 45(4):497–504
Belohlavek R (2001) Fuzzy closure operators. J Math Anal Appl 262(2):473–489
Belohlavek R (2007) A note on Variable threshold concept lattices: threshold-based operators are reducible to classical-forming operators. Inf Sci 177(15):3186–3191
Belohlavek R, Dvorak J, Outrata J (2007) Fast factorization in formal concept analysis of data with fuzzy attribute. J Comput Syst Sci 73(6):1012–1022
Belohlavek R, Krupka M (2009) Grouping fuzzy sets by similarity. Inf Sci 179(15):2656–2661
Belohlavek R, Baets BD, Outrata J, Vychodil V (2007) Lindig’s algorithm for concept lattices over graded attributes. In: Torra V, Narukawa Y, Yoshda Y (eds) MDAI, Springer, LNAI 4617, pp 156–167
Belohlavek R, Konecny J (2007) Scaling, granulation and fuzzy attributes in formal concept analysis. In: Proceedings of IEEE international conference on fuzzy systems, pp 1–6
Belohlavek R, Vychodil V (2005) Reducing the size of fuzzy concept lattice by hedges. In: Proceedings of 14th IEEE international conference on fuzzy systems, pp 663–668
Belohlavek R, Vychodil V (2005) What is fuzzy concept lattice. In: Proceedings of CLAV Olomuc, Czech Republic, pp 34–45
Berry A, Sigayret A (2004) Representing concept lattice by a graph. Discret Appl Math 144:27–42
Burmeister P, Holzer R (2005) Treating incomplete knowledge in formal concept analysis. In: Formal concept analysis. Ganter B, Stumme G, Wille R (eds) Berlin, Springer 3626:11–26
Burusco A, Fuentes-Gonzales R (1994) The study of L-fuzzy concept lattice. Math Soft Comput 3:209–218
Burusco A, Fuents-Gonzales R (2000) Concept lattices defined from implication operators. Fuzzy Sets Syst 114(3):431–436
Burusco A, Fuentes-Gonzales R (2001) The study on interval-valued contexts. Fuzzy Sets Syst 121(3):439–452
Carpineto C (2004) Concept data analysis: theory and application. Wiley, England
Dias SM, Viera NJ (2013) Applying the JBOS reduction method for relevant knowledge extraction. Experts Syst Appl 40(5):1880–1887
Djouadi Y (2011) Extended Galois derivation operators for information retrieval based on fuzzy formal concept lattice. In: Benferhal S, Goant J (eds) SUM 2011, Springer, LNAI 6929, pp 346–358
Djouadi Y, Prade H (2009) Interval-valued fuzzy formal concept analysis. In: Rauch et al. (ed) ISMIS, Springer, Berlin, LNAI 5722, pp 592–601
Dubois D, Prade H (2012) Possibility theory and formal concept analysis: characterizing independent sub-contexts. Fuzzy Sets Syst 196(1):4–16
Elloumi S, Jaam J, Hasnah A, Jaoua A (2004) A multi-level conceptual data reduction approach based on the Lukasiewicz implication. Inf Sci 163(4):253–262
Formica A (2010) Concept similarity in fuzzy formal concept analysis for semantic web. Int J Uncertain Fuzziness Knowl Based Syst 18:153–167
Gajdos P, Snasel V (2013) A new FCA algorithm enabling analyzing of complex and dynamic data sets. Soft Comput 18(4):683–694
Ganter B, Wille R (1999) Formal concept analysis: mathematical foundation. Springer, Berlin
Gely A (2011) Links between modular decomposition of concept lattices and bimodular decomposition of a context. In: Napoli A, Vychodil V (eds) Proceedings of the concept lattices and their applications, pp 393–403
Ghosh P, Kundu K, Sarkar D (2010) Fuzzy graph representation of a fuzzy concept lattice. Fuzzy Sets Syst 161(12):1669–1675
Guh YY, Yang MS, Po RW, Lee ES (2009) Interval-valued fuzzy relation-based clustering with its application to performance evaluation. Comput Math Appl 57:841–849
Kai W, Shao-Wen L, You-Hua Z, Shao L (2011) Research on the theory and methods for similarity calculation of rough formal concept in missing-value context. In: Li D, Liu Y, Chen Y (eds) Proceedings of international federation for information processing, pp 425–433
Kang X, Li D, Wang S, Qu K (2012) Formal concept analysis based on fuzzy granularity base for different granulation. Fuzzy Sets Syst 203:33–48
Konecny J, Krupka M (2011) Block relations in fuzzy settings. In: Napoli A, Vychodil V (eds) Proceedings of the concept lattices and their applications, pp 115–130
Krupka M, Lastovica J (2012) Fuzzy concept lattice with incomplete knowledge. In: Greco et al. (ed) 14th International conference on information processing management of uncertainty 2012, CCIS 299, Springer, pp 171–180
Kuznetsov SO, Obiedkov SA (2002) Comparing performance of algorithms for generating concept lattices. J Exp Theor Artif Intell 14(2–3):189–216
Li L, Jhang J (2010) Attribute reduction in fuzzy concept lattices based on the T-Implication. Knowl Based Syst 23:497–503
Li J, Mei C, Lv Y (2012) Knowledge reduction in real decision formal contexts. Inf Sci 189:191–207
Li J, Mei C, Lv Y (2013) Incomplete decision contexts: approximate concept construction, rule acquisition and knowledge reduction. Int J Approx Reason 54(1):149–165
Li J, Mei C, Zhang X (2013) On rule acquisition in decision formal contexts. Int J Mach Learn Cybern 4(6):721–731
Li J, He Z, Zhu Q (2013) An Entropy-based weighted concept lattice for merging multi-source geo-ontologies. Entropy 15:2303–2318
Ma JM, Zhang WX, Cai S (2006) Variable threshold concept lattice and dependence space. In: Proceedings of international conference on fuzzy systems and knowledge discovery. Springer, LNAI 4223, pp 109–118
Ma JM, Zhang WX (2013) Axiomatic characterizations of dual concept lattices. Int J Approx Reason 54:690–697
Maio CD, Fenza G, Loia V, Senatore S (2012) Hierarchical web resources retrieval by exploiting fuzzy formal concept analysis. Inf Process Manag 48(3):399–418
Martin TP, Rahim NHA, Mazidian A, (2013) A general approach to the measurement of change in fuzzy concept lattices. Soft Comput 17(12):2223–2234
Medina J, Ojeda-Aciego M (2012) On multi-adjoint concept lattice based on heterogeneous conjunctors. Fuzzy Sets Syst 208:95–110
Mehdi K, Kuznetsov SO, Napoli A, Duplesis S (2011) Mining gene expression data with pattern structures in formal concept analysis. Inf Sci 181:1989–2001
Mi JS, Leung Y, Wu WZ (2010) Approaches to attributes reduction in concept lattices induced by axialities. Knowl Based Syst 23:504–511
Nguyen TT, Hui S, Chang K (2012) A lattice based approach for mathematical search using formal concept analysis. Expert Syst Appl 39(5):5820–5828
Pocs J (2012) Note on generating fuzzy concept lattices via Galois connections. Inf Sci 185(1):128–136
Poelmans J, Kuznetsov SO, Ignatov DI, Dedene G (2013) Formal concept analysis in knowledge processing: a survey on applications. Expert Syst Appl 40(16):6538–6560
Poelmans J, Ignatov DI, Kuznetsov SO, Dedene G (2013) Formal concept analysis in knowledge processing : a survey on models and techniques. Expert Syst Appl 40(16):6601–6623
Pollandt S (1997) Fuzzy Begriffe. Springer, Berlin
Popescu A (2004) A general approach to fuzzy concepts. Math Logic Q 50(3):265–280
Singh PK, Aswani Kumar C (2012) A method for reduction of fuzzy relation in fuzzy formal context. In: Balasubramaniam P, Uthaya Kumar R (eds) Proceedings of international conference of mathematical modelling and scientific computation, CCIS 283. Springer, pp 343–350
Singh PK, Aswani Kumar C (2012) Interval-valued fuzzy graph representation of concept lattice. In: Proceedings of twelfth international conference on intelligent system design and application. pp 604–609
Singh PK, Aswani Kumar C (2014) A note on computing crisp order context of a given fuzzy formal context for knowledge reduction. J Inf Process Syst. doi:10.3745/JIPS.04.2009
Singh PK, Aswani Kumar C (2015) Analysis of composed contexts through projection. Int J Data Anal Tech Strateg Inder Sci (In Press)
Ranitovic MG, Petojevic A (2013) Lattice representations of interval-valued fuzzy sets. Fuzzy Sets Syst 236(1):50–57
Shao MW, Liu M, Zhang WX (2007) Set approximations in fuzzy formal concept analysis. Fuzzy Sets Syst 158:2627–2640
Singh PK, Aswani Kumar C (2012) A method for decomposition of fuzzy formal context. Proc Int Conf Modell Optim Comput Proc Eng 38:1852–1857
Singh PK, Aswani Kumar C (2014) A note on constructing fuzzy homomorphism map for a given fuzzy formal context. In: Proceedings of the third international conference on soft computing for problem solving. Adv Intell Syst Comput 258:845–855
Singh PK, Aswani Kumar C (2014) Bipolar fuzzy graph representation of concept lattice. Inf Sci 288:437–448
Wang LD, Liu XD (2008) Concept analysis via rough set and AFS algebra. Inf Sci 178:4125–4137
Wille R (1982) Restructuring lattice theory: an approach based on hierarchies of concepts. In: Sets O (ed) Rival I. Reidel, Dordrect, pp 445–470
Wolf KE (1998) Conceptual interpretation of fuzzy theory. In: Zimmerman HJ (ed) Proceedings of 6th EUFIT 1998, Aachen, 1:555–562
Wolf KE (2002) Concepts in fuzzy scaling theory: order and granularity. Fuzzy Sets Syst 132(1):63–75
Wu WZ, Leung Y, Mi JS (2009) Granular computing and knowledge reduction in formal context. IEEE Trans Knowl Data Eng 21(10):1461–1474
Yang KM, Kim EH, Hwang SH, Choi SH (2008) Fuzzy Concept mining based on formal concept analysis. Int J Comput 2(3):279–290
Yao YY (2004) A comparative study of formal concept analysis and rough set theory in data analysis. Proceedings of 4th international conference on rough sets and current trends in computing. Uppsala, Sweden, pp 59–68
Yao YY (2004) Concept lattices in rough set theory. Proceedings of 2004 annual meeting of the North American fuzzy information processing society. IEEE Computer Society, Washington D.C., pp 796–801
Zadeh LA (1965) Fuzzy sets. J Inf Control 8(3):338–353
Zadeh LA (1975) The concepts of a linguistics and application to approximate reasoning. Inf Sci 8:199–249
Zerarga L, Djouadi Y (2012) Interval-valued fuzzy extension of formal concept analysis for information retrieval. In: Huang et al. (ed) ICONIP 2012, part 1, Springer, LNCS 7663, pp 608–615
Zhai Y, Li D, Qu D (2012) Probability fuzzy attribute implications for interval-valued fuzzy set. Int J Database Theory Appl 5:95–108
Zhang WZ, Wei L, Qi JJ (2005) Attribute reduction in concept lattice based on discernibility matrix. In: Slezak D, Yao J, Peters JF (eds) Proceedings of international conference on RSFDGrC, LNAI 3642, Springer, pp 157–165
Zhang WX, Ma JM, Fan SQ (2007) Variable threshold concept lattices. Inf Sci 177(22):4883–4892
Zhou L (2011) On equivalence of fuzzy concept lattice. In: Proceedings of 8th international conference on fuzzy system and knowledge discovery 3:1475–1489
Acknowledgments
Authors sincerely acknowledge the financial support from National Board of Higher Mathematics, Dept. of Atomic Energy, Govt. of India under the grant number 2/48(11)/2010-R&D II/10806. Authors thank the anonymous reviewer for their useful suggestions and remarks to improve the quality of the paper.
Author information
Authors and Affiliations
Corresponding authors
Additional information
Communicated by V. Loia.
Rights and permissions
About this article
Cite this article
Singh, P.K., Aswani Kumar, C. & Li, J. Knowledge representation using interval-valued fuzzy formal concept lattice. Soft Comput 20, 1485–1502 (2016). https://doi.org/10.1007/s00500-015-1600-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-015-1600-1