The construction of multi-granularity concept lattices

Abstract

The construction of concept lattices is an important research topic in formal concept analysis. Inspired by multi-granularity rough sets, multi-granularity formal concept analysis has become a new hot research issue. This paper mainly studies the construction methods of concept lattices in multi-granularity formal context. The relationships between concept forming operators under different granularity are discussed. The mutual transformation methods of formal concepts under different granularity are presented. In addition, the approaches of obtaining coarse-granularity concept lattice by fine-granularity concept lattice and fine-granularity concept lattice by coarse-granularity concept lattice are examined. The related algorithms for generating concept lattices are proposed. The practicability of the method is illustrated by an example.

Keywords

Multi-granularity formal concept analysis formal concept formal concept lattice

1 Introduction

Wille put forward the theory of formal concept analysis(FCA) in 1980s [20], which is also called concept lattice theory. It is a mathematical theory for dealing with formal concepts and hierarchical structures between concepts from the relationship between data [7 , 23]. The basic notions of FCA includes formal context, formal concept and corresponding concept lattice. Formal context is a binary relation between objects and attributes. In a formal context the object has the attribute which can be represented by ’1’, if not we can represent it by ’0’. A formal concept consists of two parts: extent (the object covered by the concept) and intent (the common attributes of the concept). As a useful tool for knowledge description and summary, concept lattice theory is widely used in machine learning, pattern recognition, information retrieval, digital library, software engineering and knowledge discovery [5 , 24].

Granular Computing (GrC) was first proposed by Lin in 1997 on the basis of Zadeh’s information granularity [13, 14]. It simulates the natural pattern of human thinking, takes granular as the basic unit of computation, and aims at establishing effective computing models for processing large-scale complex data and information. Then Lin and Yao respectively elaborated on some basic problems of granular computing [14, 22]. At present, granular computing has become an important method for the field of artificial intelligence and large data processing [4, 16]. In general, each object takes only one value with respect to each attribute in an information system. Such information system reflects the object information in a fixed scale. We call it single-scale information system (also known as single-granularity label information system). In fact, the knowledge representation and data processing methods based on single granularity framework are far from meeting the requirements of practical applications. For example, for a place on a map in our country, according to the different granularity levels of administrative regions (such as village, township, county, prefecture-level city, province and so on levels), its affiliated areas are given different regional markers. In multi-granularity labeled data model, the same batch of data can be labeled as different scales or granularity levels, then people can process and analyze data at different scales or granularity levels according to their requirements. Therefore "multi-scale" or "multi-granularity" has become an important direction of granular computing research in recent years [17, 18].

Inspired by the research of multi-granularity information system in rough set, some scholars combined the viewpoint of multi-granularity with formal concept analysis. Hao et al. considered optimal scale selection based on single-attribute multi-granularity formal context [9]. Xie et al. studied rule acquisition and optimal scale selection in multi-scale formal decision contexts and their applications to smart city [21]. Li et al. put forward the definition of multi-granularity concept analysis. Through the forward and reverse scaling methods, the transformation relationship between information system and formal context is studied [11]. The construction of multi-granularity concept lattices is an important issue for multi-granularity formal concept analysis. Based on attribute granularity tree, Belohlavek et al. [1 –3] proposed the transformation method of concept lattices by specifying granularity levels of attributes. Shao et al. [19] proposed a method and related algorithm for the construction of property oriented (object oriented) concept lattice in coarse-granularity and property oriented (object oriented) concept lattice in fine-granularity under multi-granularity formal context.

The transformation method between fine and coarse property (object) oriented concept lattices presented in [19] is not applicable to fine and coarse formal concept lattices. Therefore, in this paper we directly consider the construction of multi-granularity concept lattices. Different from the general research, we consider the sets of objects sharing the fine-attributes forms a covering of the set objects sharing the original attribute, not a partition. The structure of this paper is as follows: In the second part, some basic definitions of concept lattice theory are given. In the third part, the relationship between extremum operators under multi-granularity is discussed, then under the multi-granularity formal context, the methods of transformation between fine-granularity concept lattice and coarse-granularity concept and the corresponding algorithms are given. The conclusion is given in the part four.

2 Preliminaries

In this section, the involved notions of FCA are introduced. Please refer to [20] for details.

Definition 1. [20] A formal context is a triple $F = (G, M, I)$ , where G (object set) and M (attribute set) are both finite nonempty sets, and I ⊆ G × M is called an incidence relation, (x, m) ∈ I indicates that the object x has the attribute m. For any X ⊆ G and B ⊆ M: $X^{*} = {m \in M | \forall x \in X, (x, m) \in I},$ $B^{*} = {x \in G | \forall m \in B, (x, m) \in I} .$

In other words, X^* is the maximal set of attributes shared by all the objects in X, B^* is the maximal set of objects that have all attributes in B. A pair (X, B) is called a formal concept, or a concept for short, if X^* = B and B^* = X, then X and B are regarded as the extent and the intent of the formal concept (X, B) respectively. All the concepts form a complete lattice, which is called the concept lattice of (G, M, I) and denoted by L (G, M, I)(or $L (F)$ for simple), with respect to the partial order relation (X₁, B₁) ≤ (X₂, B₂) ⇔ X₁ ⊆ X₂.

For any X, X₁, X₂ ⊆ G, B, B₁, B₂ ⊆ M, the following properties hold [20]:

$X_{1} \subseteq X_{2} \Rightarrow X_{2}^{*} \subseteq X_{1}^{*}, B_{1} \subseteq B_{2} \Rightarrow B_{2}^{*} \subseteq B_{1}^{*};$

X⊆ X^**, B ⊆ B^** ;

X^* = X^***, B^* = B^*** ;

X⊆ B^* ⇔ B ⊆ X^* ;

$(X_{1} \cup X_{2})^{*} = X_{1}^{*} \cap X_{2}^{*}; (B_{1} \cup B_{2})^{*} = B_{1}^{*} \cap B_{2}^{*};$

(X^**, X^*) and (B^*, B^**) are both concepts.

For simplicity, for any x ∈ G and m ∈ M, {x} ^* and {m} ^* are replaced by x^* and m^* respectively. We denote by ExtL (G, M, I) the set of all extents of formal concepts in L (G, M, I).

Example 1. Table 1 presents a formal context $F_{1} = (G, M_{1}, I_{1})$ , where G = {1, 2, 3, 4, 5, 6} is the set of objects, M₁ = {a, b, c, d} is the set of attributes. By direct computation, we have $L (F_{1}) = {(\emptyset, abcd), (13, abd), (245, c), (45, acd), (136, ab), (1345, ad), (13456, a), (123456, \emptyset)}$ .

Table 1
A formal context

a b c d

1 1 1 0 1

2 0 0 1 0

3 1 1 0 1

4 1 0 1 1

5 1 0 1 1

6 1 1 0 0

	a	b	c	d
1	1	1	0	1
2	0	0	1	0
3	1	1	0	1
4	1	0	1	1
5	1	0	1	1
6	1	1	0	0

Fig.1 is the Hasse diagram of the concept lattice generated by the formal context in Table 1.

Fig. 1

The Concept Lattice of $F_{1}$ .

Definition 2. Let $F = (G, M, I)$ be a formal context. For E ⊆ M and I_E = I ∩ (G × E), (G, E, I_E) is called a sub-context of (G, M, I). For any X ⊆ G and B ⊆ E: $X^{*_{E}} = {m \in E | \forall x \in X, (x, m) \in I_{E}},$ $B^{*_{E}} = {x \in G | \forall m \in B, (x, m) \in I_{E}} .$

For any X, X₁, X₂ ⊆ G, B, B₁, B₂ ⊆ E, the following properties hold:

X^*_E = X^*∩ E, B^* = B^*_E ;

(X^*_E*_E, X^*_E) and (B^*_E, B^*_E*_E) are both concepts of (G, E, I_E).

ExtL (G, E, I_E) ⊆ ExtL (G, M, I)

3 Multi-granularity formal concept lattice

Knowledge representation and data processing methods based on single granularity framework are far from meeting the needs of practical applications. Let’s consider students’ examination results. In order to make a more accurate evaluation, in some cases, we need divide the attribute ^′Achievement pass′ ([60, 100] points) into the attributes: {′qualified′ ([60, 75] points) , ^′good′ ([76, 89] points) , ^′excellent′ ([90, 100] points)} . ′Achiev- ement pass′ and ^′qualified′,^′good′,^′excellent′ can be looked upon attributes with different granularities. The notion of multi-granularity formal context is thus presented by Li [11] for dealing with granular computing problems related to FCA.

Definition 3. [11] Let $F = (G, M, I)$ be a formal context. ∀a ∈ M, then Ia is the object set possessing by a. For A ⊆ M, A is regarded as the object partition set of (G, M, I), if ∀a, b ∈ A there have a^*∩ b^* = ∅ and ⋃_c∈Ac^* = G.

Assume two formal contexts (G, A₁, I₁) and (G, A₂, I₂). For a ∈ A₁, Bin (a^*) is called the Boolean vector representation of a^*. For b ∈ A₂, b is a fusion attribute of {a_t|t ∈ T_b} if there exists a_t ∈ A₁(t ∈ T_b, T_b is a indicator set) such that ∑_{t∈T_b}Bin (I₁a_t) = Bin (I₂b) holds. For ∀b ∈ A₂, there exists a_t ∈ A₁(t ∈ T_b, T_b is an index set) such that b is a fusion attribute. And each attribute in A₁ is used to fuse one of the attribute in A₂. Then we call (G, A₂, I₂) is a fusion formal context of (G, A₁, I₁).

We note that when multiple attributes need to be refined, they can be refined by a single attribute in turn. Therefore, the following discusses the case where a single attribute needs to be refined. Here some modifications on notations and technical terms have been made to fit the context of our discussion. Let $F_{1} = (G, M_{1}, I_{1})$ and $F_{2} = (G, M_{2}, I_{2})$ be two regular formal contexts, where M₁ = M ∪ {a} and M₂ = (M₁ - {a}) ∪ A = M ∪ A, a is an attribute that needs to be refined. A = {a₁, a₂, ⋯ a_n} is the set of the fine-granularity attributes corresponding to a satisfying $a^{*_{1}} = a_{1}^{*_{2}} \cup a_{2}^{*_{2}} \cup \dots \cup a_{n}^{*_{2}}$ . we note that for any a_i, a_j ∈ A there doesn’t have $a_{i}^{*_{2}} \cap a_{j}^{*_{2}} = \emptyset$ , that is to say ${a_{1}^{*_{2}}, a_{2}^{*_{2}}, \dots, a_{n}^{*_{2}}}$ is a covering of a^*₁, not a partition of a^*₁. We will discuss the two formal context $F_{1}$ and $F_{2}$ in the following.

Remark 1. The operators of $F_{1} = (G, M_{1}, I_{1})$ and $F_{2} = (G, M_{2}, I_{2})$ are *₁ and *₂ respectively. For any B ⊆ M, the corresponding operator is *_B. We note that the object set G is unchanged in our discussion, hence we denote the operator corresponding to a single attribute just by * if it is not necessary to distinguish them. That is to say a^*₁ and a^* are replaced by a^* for simplicity.

Lemma 1. Assume X ⊆ G, A₁, A₂ ⊆ M and B = A₁ ∪ A₂, then we have X^*_B = X^{*_{A
₁}} ∪ X^{*_{A
₂}}.

Example 2. We consider the formal context given by example 1. The attribute {a} can be refined into {a₁, a₂, a₃}. Table 2 presents the fine-granularity formal context $F_{2} = (G, M_{2}, I_{2})$ .

By direct computation, we have

$L (F_{2}) = {(\emptyset, a_{1} a_{2} a_{3} bcd), (1, a_{1} a_{3} bd), (3, a_{1} a_{2} bd), (4, a_{1} a_{2} cd), (5, a_{2} a_{3} cd), (13, a_{1} bd), (34, a_{1} a_{2} d), (45, a_{2} cd), (16, a_{3} b), (15, a_{3} d), (134, a_{1} d), (345, a_{2} d), (136, b), (156, a_{3}), (1345, d), (245, c), (123456, \emptyset)}$ .

Fig. 2 is the Hasse diagram of the concept lattice generated by the formal context in Table 2.

Fig. 2

The Concept Lattice of $F_{2}$ .

Table 2

The fine-granularity formal context

	a ₁	a ₂	a ₃	b	c	d
1	1	0	1	1	0	1
2	0	0	0	0	1	0
3	1	1	0	1	0	1
4	1	1	0	0	1	1
5	0	1	1	0	1	1
6	0	0	1	1	0	0

3.1 The construction of fine-granularity formal concept lattice

In this subsection, we present a method to construct fine-granularity formal concepts by using coarse-granularity formal concepts. Let $F_{1}$ and $F_{2}$ be two formal context given above. Let $C (X) = {A_{i} \subseteq A | X \cap A_{i}^{*_{2}} \neq \emptyset}$ for X ⊆ G.

Theorem 1. Assume $(X, B) \in L (F_{1})$ and a ∉ B, then we can get $(X, B) \in L (F_{2})$ .

Proof. It is obvious that X ⊈ a^* from a ∉ B = X^*₁. By $a^{*} = ⋃_{1 \leq i \leq n} a_{i}^{*}$ , we have ∀a_i ∈ A, $X ⊈ a_{i}^{*_{2}}$ , then X^*_A =∅. By a ∉ B, we can get B ⊆ M, then X^*_M = X^*₁ ∩ M = B ∩ M = B. It is following that X^*₂ = X^*_M ∪ X^*_A = B. We conclude that B^*₂ = B^*_M = B^*₁ = X since B ⊆ M. It follows that $(X, B) \in L (F_{2})$ . □

Theorem 2. Assume $(X, B) \in L (F_{1})$ and a ∈ B, then $(X \cap A_{i}^{*_{2}}, (X \cap A_{i}^{*_{2}})^{*_{2}}) \in L (F_{2})$ for any A_i ∈ C (X).

Proof. From a ∈ B, we have $X \subseteq a^{*_{1}} = ⋃_{1 \leq i \leq n} A_{i}^{*_{2}}$ . It follows that C (X)≠ ∅. For each A_i ∈ C (X), it is easy to know that $X \cap A_{i}^{*_{2}} \subseteq (X \cap A_{i}^{*_{2}})^{*_{2} *_{2}}$ . From $(X \cap A_{i}^{*_{2}})^{*_{M}} \supseteq X^{*_{M}} = B - {a}$ and $(X \cap A_{i}^{*_{2}})^{*_{A}} = {a_{i}}$ , we have $(X \cap A_{i}^{*_{2}})^{*_{2} *_{2}} = ((X \cap A_{i}^{*_{2}})^{*_{M}} \cup (X \cap A_{i}^{*_{2}})^{*_{A}})^{*_{2}} \subseteq ((B - {a}) \cup A_{i})^{*_{2}} = (B - {a})^{*_{2}} \cap A_{i}^{*_{2}} = (B - {a})^{*_{1}} \cap A_{i}^{*_{2}} = (B - {a})^{*_{1}} \cap a^{*} \cap A_{i}^{*_{2}} = B^{*_{1}} \cap A_{i}^{*_{2}} = X \cap A_{i}^{*_{2}}$ . Then $X \cap A_{i}^{*_{2}} = (X \cap A_{i}^{*_{2}})^{*_{2} *_{2}}$ , we can conclude that $(X \cap A_{i}^{*_{2}}, (X \cap A_{i}^{*_{2}})^{*_{2}}) \in L (F_{2})$ . □

Theorem 3. Assume $(X, B) \in L (F_{1})$ and a ∈ B, if for any a_i ∈ A there has $X ⊈ a_{i}^{*}$ , then $((B - {a})^{*_{2}}, B - {a}) \in L (F_{2})$ .

Proof. It is easy to know that B - {a} ⊆ (B - {a}) ^*₂*₂. From hypothesis we have X^*_A =∅, then X = B^*₁ ⊆ (B - {a}) ^*₁ = (B - {a}) ^*_M = (B - {a}) ^*₂ and (B - {a}) ^*₂*₂ ⊆ X^*₂ = X^*_M ∪ X^*_A = X^*_M = X^*₁ ∩ M = B ∩ M = B - {a}. We conclude that B - {a} = (B - {a}) ^*₂*₂, then $((B - {a})^{*_{2}}, B - {a}) \in L (F_{2})$ . □

Corollary 1. Assume $(X, B) \in L (F_{1})$ and a ∈ B, if for any a_i ∈ A there has $X ⊈ a_{i}^{*}$ , then $((B - {a})^{*_{2}}, B - {a}) = ⋁_{A_{i} \in C (X)} {(X \cap A_{i}^{*_{2}}, (X \cap A_{i}^{*_{2}})^{*_{2}})}$ .

Proof. By theorem 2 and theorem 3, we have $(X \cap A_{i}^{*_{2}}, (X \cap A_{i}^{*_{2}})^{*_{2}}) \in L (F_{2})$ (∀A_i ∈ C (X)) and $((B - {a})^{*_{2}}, B - {a}) \in L (F_{2})$ ,then $⋁_{A_{i} \in C (X)} {(X \cap A_{i}^{*_{2}}, (X \cap A_{i}^{*_{2}})^{*_{2}})} \in L (F_{2})$ . From a ∈ B, we have X ⊆ a^*. It follows that $X = X \cap a^{*} = X \cap (A_{1}^{*_{2}} \cup \dots \cup A_{2^{| A |}}^{*_{2}}) = (X \cap (A_{i_{1}}^{*_{2}})) \cup \dots \cup (X \cap (A_{i_{| C (X) |}}^{*_{2}})) = ⋃_{k = 1, \dots, | C (X) |} {X \cap (A_{i_{k}}^{*_{2}})}$ , where ⋃_{k=1,⋯,|C(X)|} {A_{i
_k}} = C (X). Let $⋁_{A_{i} \in C (X)} {(X \cap A_{i}^{*_{2}}, (X \cap A_{i}^{*_{2}})^{*_{2}})} = ⋁_{k = 1, \dots, | C (X) |} {(X \cap A_{i_{k}}^{*}, (X \cap A_{i_{k}}^{*})^{*_{2}})}$ . It is obvious that $⋁_{k = 1, \dots, | C (X) |} {(X \cap A_{i_{k}}^{*}, (X \cap A_{i_{k}}^{*})^{*_{2}})} = ((⋃_{k = 1, \dots, | C (X) |} {X \cap A_{i_{k}}^{*}})^{*_{2} *_{2}}, ⋂_{k = 1, \dots, | C (X) |} {(X \cap A_{i_{k}}^{*})^{*_{2}}})$ . Then we have $⋂_{k = 1, \dots, | C (X) |} {(X \cap A_{i_{k}}^{*})^{*_{2}}} = (⋃_{k = 1, \dots, | C (X) |} {X \cap A_{i_{k}}^{*}})^{*_{2}} = X^{*_{2}}$ . By the proof of theorem 4, we know X^*₂ = B - {a}. It follows that $⋂_{k = 1, \dots, | C (X) |} {(X \cap A_{i_{k}}^{*})^{*_{2}}} = X^{*_{2}} = B - {a}$ . That is to say the concept $⋁_{A_{i} \in C (X)} {(X \cap A_{i}^{*_{2}}, (X \cap A_{i}^{*_{2}})^{*_{2}})}$ and the concept ((B - {a}) ^*₂, B - {a}) have the same intent. So we have $((B - {a})^{*_{2}}, B - {a}) = ⋁_{A_{i} \in C (X)} {(X \cap A_{i}^{*_{2}}, (X \cap A_{i}^{*_{2}})^{*_{2}})}$ .

□

Remark 2. From the maximum element and the minimum element are easy to get, so we don’t discuss the maximum element and the minimum element in this paper.

Example 3. We consider the formal contexts given by example 1,2. $L (F_{1}) = {(\emptyset, abcd), (13, abd), (245, c), (45, acd), (136, ab),$ (1345, ad) , (13456, a) , (123456, ∅)}. Then each concept in $L (F_{1})$ can transform into the concept of $L (F_{2})$ . We will only show the transformation of some concepts in the following.

(245, c) → (245, c); (theorem 1)

(13, abd) → (13, a₁bd);(13, abd) → (1, a₁a₃bd); (13, abd) → (3, a₁a₂bd);(45, acd) → (45, a₂cd); (45, acd) → (4, a₁a₂cd);(45, acd) → (5, a₂a₃cd); (136, ab) → (13, a₁bd);(136, ab) → (1, a₁a₃bd); (136, ab) → (3, a₁a₂bd);(136, ab) → (16, a₃b); (theorem 2)

(136, ab) → (136, b);(1345, ad) → (1345, d); (13456, a) → (123456, ∅). (theorem 3)

The concepts in

L (F_{1})

are on the left of the arrow, while on the right of the arrow are the concepts in

L (F_{2})

By the above theorems we can conclude that each concept in coarse-granularity concept lattice can be refined into a concept of fine-granularity concept lattice. The following theorem shows that each fine-granularity concept can be obtained by coarse-granularity concept.

Algorithm 1: Computing the fine-granularity formal concept lattice

Input: A coarse-granularity formal concept lattice

L (F_{1})

Output: The fine-granularity formal concept lattice

L (F_{2})

1: Initialize L ← {Maximum element, Minimum element};

2: for each

(X, B) \in L (F_{1})

do;

5: if a ∉ B then L ← (X, B), continue;

6: if a ∈ B and for any a_i ∈ A there has

X ⊈ a_{i}^{*}

, then L ← ((B - {a}) ^*₂, B - {a});

7: if a ∈ B and ∃A_i ⊆ A s.t.

X \cap a_{i}^{*} \neq \emptyset

, then

L \leftarrow (X \cap A_{i}^{*_{2}}, (X \cap A_{i}^{*_{2}})^{*_{2}})

;

8: construct

L (F_{2})

by L.

Theorem 4. Let $F_{1}$ and $F_{2}$ be two formal context given above. Then we can get that $L (F_{2}) = L_{1} \cup L_{2} \cup L_{3} \cup L_{0}$ , where $L_{1} = {(X, B) | ((X, B) \in L (F_{1})) \land (a \notin B)}$ , $L_{2} = {((B - {a}^{*_{2}}), B - {a}) | ((X, B) \in L (F_{1})) \land (a \in B) \land (\forall a_{i} \in A (X ⊈ a_{i}^{*}))}$ , $L_{3} = {(X \cap A_{i}^{*_{2}}, (X \cap A_{i}^{*_{2}})^{*_{2}}) | ((X, B) \in L (F_{1})) \land (a \in B) \land (\exists A_{i} \subseteq A (X \cap A_{i}^{*_{2}} \neq \emptyset))}$ L₀ = {Maximum element, Minimum element}

Proof. (1)Situation a. When $(X, B) \in L (F_{2})$ ,A∩ B = ∅ and X ⊈ a^*: First we need to proof $(X, B) \in L (F_{1})$ . Since A∩ B = ∅ and X ⊈ a^* we have X^*₂ = X^*_M ∪ X^*_A = X^*_M = B and X^*_a =∅, then X^*₁ = X^*_M ∪ X^*_a = B. By A∩ B = ∅ and a ∉ B, we have B^*₁ = B^*₂ = B^*_M = X. Then $(X, B) \in L (F_{1})$ . Obviously (X, B) satisfies the conditions of theorem 1. So the concept (X, B) can be obtained by (X, B) in $L (F_{2})$ through theorem 1, then we have (X, B) ∈ L₁. Situation b. When $(X, B) \in L (F_{2})$ , A∩ B = ∅ and X ⊆ a^*: First we need to proof $(X, B \cup {a}) \in L (F_{1})$ . Since X^*_A = X^*₂∩ A = B ∩ A = ∅, we have X^*₂ = X^*_M ∪ X^*_A = X^*_M = B. It is easy to get X^*₁ = X^*_M ∪ X^*_a = B ∪ {a} since X^*_a = {a}. By A∩ B = ∅ and a ∉ B, we have B^*₁ = B^*₂ = B^*_M = X. It follows that (B ∪ {a}) ^*₁ = B^*₁ ∩ a^* = X ∩ a^* = X since X ⊆ a^*. So we can conclude that $(X, B \cup {a}) \in L (F_{1})$ . Obviously (X, B ∪ {a}) satisfies the conditions of theorem 3 and B ∪ {a} - {a} = B, B^*₂ = X. So the concept (X, B) can be obtained by (X, B ∪ {a}) in $L (F_{2})$ through theorem 4, then we have (X, B) ∈ L₂. Situation c. When $(X, B) \in L (F_{2})$ and A∩ B ≠ ∅: We consider the concept $(X^{*_{1} *_{1}}, X^{*_{1}}) \in L (F_{1})$ . Assume B ∩ A = A_k, it is obvious $A_{k}^{*_{2}} \subseteq a^{*}$ . From X^*₂ = X^*_M ∪ A_k, we have X^*₁ = X^*_M ∪ {a} = B - A_k ∪ {a}. It follows that $X^{*_{1} *_{1}} \cap A_{k}^{*_{2}} = (B - A_{k} \cup {a})^{*_{1}} \cap A_{k}^{*_{2}} = (B - A_{k})^{*_{M}} \cap a^{*} \cap A_{k}^{*_{2}} = (B - A_{k})^{*_{M}} \cap A_{k}^{*_{2}} = (B - A_{k} \cup A_{k})^{*_{2}} = (B)^{*_{2}} = X$ . Obviously (X^*₁*₁, X^*₁) satisfies the conditions of theorem 2 and $X^{*_{1} *_{1}} \cap A_{k}^{*_{2}} = X$ . So the concept (X, B) can be obtained by (X^*₁*₁, X^*₁) in $L (F_{2})$ through theorem 2, then we have (X, B) ∈ L₃. In summary we can conclude that $L (F_{2}) \subseteq L_{1} \cup L_{2} \cup L_{3} \cup L_{0}$ .

(2) It is obvious that $L_{1} \subseteq L (F_{2})$ , $L_{2} \subseteq L (F_{2})$ and $L_{3} \subseteq L (F_{2})$ , then we can get that $L_{1} \cup L_{2} \cup L_{3} \cup L_{0} \subseteq L (F_{2})$ .

From (1) and (2), we know $L (F_{2}) = L_{1} \cup L_{2} \cup L_{3} \cup L_{0}$ .

□

Based on these theorems, we propose algorithm 1 to compute the fine-granularity formal concept lattice. The algorithm is described as follow:

Example 4. We consider the formal contexts given by example 1,2.

$(245, c) \in L (F_{2})$ satisfies the Situation a, so it can be obtained by $(245, c) \in L (F_{1})$ .

$(136, b), (1345, d) \in L (F_{2})$ satisfies the Situation b, so they can be obtained by $(136, ab), (1345, ad) \in L (F_{1})$ respectively.

$(1, a_{1} a_{3} bd), (3, a_{1} a_{2} bd), (13, a_{1} bd) \in L (F_{2})$ satisfies the Situation c, so they can be obtained by $(13, abd) \in L (F_{1})$ respectively. $(4, a_{1} a_{2} cd), (5, a_{2} a_{3} cd), (45, a_{2} cd) \in L (F_{2})$ satisfies the Situation c, so they can be obtained by $(45, acd) \in L (F_{1})$ respectively. $(34, a_{1} a_{2} d), (15, a_{3} d), (134, a_{1} d), (345, a_{2} d), (1345, d) \in L (F_{2})$ satisfies the Situation c, so they can be obtained by $(1345, ad) \in L (F_{1})$ respectively. $(16, a_{3} b) \in L (F_{2})$ satisfies the Situation c, so they can be obtained by $(136, ab) \in L (F_{1})$ respectively. $(156, a_{3}) \in L (F_{2})$ satisfies the Situation c, so they can be obtained by $(13456, a) \in L (F_{1})$ respectively.

3.2 The construction of coarse-granularity formal concept lattice

Now we consider how to get coarse-granularity concept lattice from fine-granularity concept lattice.

Theorem 5. Assume $(X, B) \in L (F_{2})$ and A∩ B = ∅. If X ⊈ a^*, then we have $(X, B) \in L (F_{1})$ .

Proof. By A∩ B = ∅ and X ⊈ a^*, we have B^*₁ = B^*₂ = B^*_M = X and X^*_a = X^*_A =∅. Since B = X^*₂ = X^*_M ∪ X^*_A = X^*_M we have X^*₁ = X^*_M ∪ X^*_a = B. It follows that $(X, B) \in L (F_{1})$ . □

Theorem 6. Assume $(X, B) \in L (F_{2})$ and A∩ B = ∅. If X ⊆ a^*, then $(X, B \cup {a}) \in L (F_{1})$ .

Proof. It is easy to know that X ∩ a^* ⊆ (X ∩ a^*) ^*₁*₁. From $(X, B) \in L (F_{2})$ and A∩ B = ∅, we have X^*₂ = X^*_M ∪ X^*_A = X^*_M = B. It follows that X^*₁ = X^*_M ∪ {a} = B ∪ a from X ⊆ a^*. It is obvious that B^*₁ = B^*₂ = X, so we have (B ∪ {a}) ^*₁ = B^*₁ ∩ a^* = X. Then we can conclude that $(X, B \cup {a}) \in L (F_{1})$ . □

Theorem 7. Assume $(X, B) \in L (F_{2})$ and A∩ B ≠ ∅, then $(((B - A) \cup {a})^{*_{1}}, (B - A) \cup {a}) \in L (F_{1})$ .

Algorithm 2: Computing the coarse-granularity formal concept lattice

Input: A fine-granularity formal concept lattice

L (F_{2})

Output: The coarse-granularity formal concept lattice

L (F_{1})

1: Initialize L ← {Maximum element, Minimum element, (a^**, a^*)};

2: for each

(X, B) \in L (F_{2})

do;

5: if A∩ B = ∅ and X ⊈ a^*, then L ← (X, B);

6: if A∩ B = ∅ and X ⊆ a^*, then L ← (X, B ∪ a);

7: if A∩ B ≠ ∅, then L ← (((B - A) ∪ {a}) ^*₁, (B - A) ∪ {a});

8: construct

L (F_{1})

by L.

Proof. It is obvious that (B - A) ∪ {a} ⊆ ((B - A) ∪ {a}) ^*₁*₁. From (B - A) ^*₁ = (B - A) ^*_M ∪ (B - A) ^*_a = (B - A) ^*_M ∪ ∅ = (B - A) ^*_M and (B - A) ^*₂ = (B - A) ^*_M ∪ (B - A) ^*_A = (B - A) ^*_M ∪ ∅ = (B - A) ^*_M,we have ((B - A) ∪ {a}) ^*₁ = (B - A) ^*₁ ∩ a^* = (B - A) ^*_M ∩ a^* ⊇ (B - A) ^*₂ ∩ (A ∩ B) ^*₂ = B^*₂ = X. Then it follows that ((B - A) ∪ {a}) ^*₁*₁ = ((B - A) ^*₁ ∩ a^*) ^*₁ ⊆ X^*₁ = X^*_M ∪ X^*_a = (B - A) ∪ {a} since X ⊆ (A ∩ B) ^*₂ ⊆ a^*. So we can get that (B - A) ∪ {a}) = ((B - A) ∪ {a}) ^*₁*₁, then $(((B - A) \cup {a})^{*_{1}}, (B - A) \cup {a}) \in L (F_{1})$ . □

By the above three theorems we can conclude that each concept in fine-granularity concept lattice can be refined into a concept of coarse-granularity concept lattice through fine-granularity concept.

Example 5. We consider the formal contexts given by example 1,2. Then each concept in $L (F_{2})$ can transform into the concept of $L (F_{1})$ . We will only show the transformation of some concepts in the following.

(245, c) → (245, c); (theorem 5)

(136, b) → (136, ab) ; (1345, d) → (1345, ad); (theorem 6)

(13, a₁bd) → (13, abd);(34, a₁a₂d) → (1345, ad); (156, a₃) → (13456, a)(theorem 7)

The concepts in

L (F_{2})

are on the left of the arrow, while on the right of the arrow are the concept in

L (F_{1})

By the above three theorems we can conclude that each concept in fine-granularity concept lattice can be refined into a concept in coarse-granularity concept lattice. The following theorem shows that each coarse-granularity concept can be obtained.

Theorem 8. Let $F_{1}$ and $F_{2}$ be two formal context given above. Then we have $L (F_{1}) = L_{4} \cup L_{5} \cup L_{6} \cup L_{0}^{'}$ , where $L_{4} = {(X, B) | ((X, B) \in L (F_{2})) \land (A \cap B = \emptyset) \land (X ⊈ a^{*})}$ , $L_{5} = {(X, B \cup a) | ((X, B) \in L (F_{2})) \land (A \cap B = \emptyset) \land (X \subseteq a^{*})}$ , $L_{6} = {(((B - A) \cup {a})^{*_{1}}, (B - A) \cup {a} | ((X, B) \in L (F_{2})) \land (A \cap B \neq \emptyset)}$ , $L_{0}^{'} = {Maximum element, Minimum element, (a^{* *}, a^{*})}$

Proof. (1) Situation a : When $(X, B) \in L (F_{1})$ and a ∉ B: First we need to proof $(X, B) \in L (F_{2})$ . Since a ∉ B, we have X^*₁ = X^*_M ∪ X^*_a = X^*_M = B. From a ∉ X^*₁, we know X^*₂∩ A = ∅, then X^*₂ = X^*_M ∪ X^*_A = X^*_M = B. It is obvious that B^*₂ = B^*₁ = X. So we can get that $(X, B) \in L (F_{2})$ . Then the concept (X, B) can be obtained by (X, B) in $L (F_{2})$ through theorem 5, then we have (X, B) ∈ L₄.

Situation b : When $(X, B) \in L (F_{1})$ , a ∈ B, |B|>1 and ∀a_i ∈ A such that $X ⊈ a_{i}^{*}$ : First we need to proof $(X, B - {a}) \in L (F_{2})$ . From ∀a_i ∈ A such that $X ⊈ a_{i}^{*}$ , we have X^*₂ = X^*_M ∪ X^*_A = B - {a}. By a ∈ B, we know X ⊆ a^*, it follows that X = B^*₁ = ((B - {a}) ∪ {a}) ^*₁ = (B - {a}) ^*_M ∩ a^* = (B - {a}) ^*_M = (B - {a}) ^*₂. So we can get that $(X, B - {a}) \in L (F_{2})$ . We know the concept (X, B) can be obtained by (X, B - {a}) in $L (F_{2})$ through theorem 6, then we have (X, B) ∈ L₅.

Situation c : When $(X, B) \in L (F_{1})$ , a ∈ B, |B|>1 and ∃a_i ∈ A such that $X \subseteq a_{i}^{*}$ : First we need to proof $(X, (B - {a}) \cup {a_{i}}) \in L (F_{2})$ . Since a ∈ B and $X \subseteq a_{i}^{*}$ we know X^*_M = X^*₁ - {a} = B - {a} and X^*₂ = X^*_M ∪ X^*_A = (B - {a}) ∪ {a_i}. It is obvious X ⊆ ((B - {a}) ∪ {a_i}) ^*₂, then we have $((B - {a}) \cup {a_{i}})^{*_{2}} = (B - {a})^{*_{2}} \cap a_{i}^{*} \subseteq (B - {a})^{*_{M}} \cap a^{*} = (B - {a} \cup {a})^{*_{1}} = B^{*_{1}} = X$ . We can get $(X, (B - {a}) \cup {a_{i}}) \in L (F_{2})$ . It follows that ((B - {a})∪ {a_i}) ∩ A = {a_i} ≠ ∅ and (((B - {a}) ∪ {a_i}) - A) ∪ {a} = B. So the concept (X, B) can be obtained by (X, (B - {a}) ∪ {a_i}) in $L (F_{2})$ through theorem 7, then we have (X, B) ∈ L₆.

Situation d : If $(a^{*}, a) \in L (F_{1})$ , then $(a^{*}, a) \in L_{0}^{'}$ . In summary we can conclude that $L (F_{1}) \subseteq L_{4} \cup L_{5} \cup L_{6} \cup L_{0}^{'}$ . (2) It is obvious that $L_{4} \subseteq L (F_{1})$ , $L_{5} \subseteq L (F_{1})$ , $L_{6} \subseteq L (F_{1})$ and $L_{0}^{'} \subseteq L (F_{1})$ , then we can get that $L_{4} \cup L_{5} \cup L_{6} \cup L_{0}^{'} \subseteq L (F_{1})$ .

□

Based on these theorems, we propose algorithm 2 to compute the coarse-granularity formal concept lattice. The algorithm is described as follow:

Example 6. We consider the formal contexts given by example 1,2.

$(245, c) \in L (F_{1})$ satisfies the Situation a, so it can be obtained by $(245, c) \in L (F_{2})$ .

$(136, ab), (1345, ad) \in L (F_{1})$ satisfies the Situation b, so they can be obtained by $(136, b), (1345, d) \in L (F_{1})$ respectively.

$(13, abd), (45, acd), (13456, a) \in L (F_{1})$ satisfies the Situation c, so they can be obtained by $(13, a_{1} bd), (45, a_{2} cd), (156, a_{3}) \in L (F_{2})$ respectively.

Theorem 9. Assume $(X, B) \in L (F_{1})$ . Then $X \in ExtL (F_{1}) \cap ExtL (F_{2})$ , when X satisfies one of the following conditions:

a ∉ B;

a ∈ B, for any a_i ∈ A there has $X ⊈ a_{i}^{*}$ and (B - {a}) ^*₁ = X.

Proof. (1) From theorem 1 we have $(X, B) \in L (F_{2})$ . Then $X \in ExtL (F_{1}) \cap ExtL (F_{2})$ . (2) From theorem 3 we have $((B - {a})^{*_{2}}, (B - {a})) \in L (F_{2})$ . By a ∉ B - {a} and A∩ B - {a} = ∅, we can get (B - {a}) ^*₂ = (B - {a}) ^*₁ = X. Then $X \in ExtL (F_{1}) \cap ExtL (F_{2})$ . □

4 Conclusion

The construction of formal context is one of research focuses in FCA. Multi-granularity concept lattice has become a research hotspot of concept lattice at present. This paper mainly studies the construction of multi-granularity concept lattices, systematically analyzes the transformation relationship between concepts in fine and coarse formal context, then gives the methods of transformation between fine-granularity concept lattice and coarse-granularity concept and related algorithms. The practicability of the method is illustrated by an example.

Footnotes

Acknowledgment

This work has been partially supported by the National Natural Science Foundation of China (Grant No. 61976130)

References

Belohlavek

, De Baets

and Konecny

, Zoom-in/zoom-out algorithms for fca with attribute granularity, Computer Information Sciences II, pages 549–555, 2011.

Belohlavek

, De Baets

, Outrata

and Vychodil

, Inducing decision trees via concept lattices, In Proceedings of the Fifth International Conference on Concept Lattices and Their Applications, CLA 2007, Montpellier, France, October 24–26, 2007, 2007.

Belohlavek

, De Baets

and Konecny

, Granularity of attributes in formal concept analysis,, Information Sciences 260 (2014), 149–170.

Chen

C.L.P.

and Zhang

C.Y.

, Data-intensive applications, challenges, techniques and technologies: A survey on big data, Information Sciences 275(11) (2014), 314–347.

Formica

, Concept similarity in fuzzy formal concept analysis for semantic web, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 18(02) (2010).

Formica

, Semantic web search based on rough sets and fuzzy formal concept analysis, Knowledge-Based Systems 26(9) (2012), 40–47.

Ganter

and Wille

, Formal Concept Analysis, 1999.

Godin

, Missaoui

and Alaoui

, Incremental concept formation algorithms based on galois (concept) lattices, Computational Intelligence 11(2) (2010), 246–267.

Hao

, Fan

and Li

, Optimal scale selection in mutil-scale contexts based on granular scale rules, Patern Recognition and Artificial Intelligence 29(3) (2016), 272–280.

10.

Klimes

, Using formal concept analysis for control in cyber-physical systems, Procedia Engineering 69(1) (2014), 1518–1522.

11.

JinHai

L.I.

, WeiZhi

W.U.

and Shuo

, Multi-scale theory in formal concept analysis, Journal of Shandong University (Natural Science), 2019.

12.

, Mei

and Lv

, Knowledge reduction in decision formal contexts, Knowledge-Based Systems 24(5) (2011), 709–715.

13.

Lin

T.Y.

, Granular computing on binary relations ii: Rough set representations and belief functions, Rough Sets in Knowledge Discovery, pages 121–140, 1998.

14.

Lin

T.Y.

, Granular computing: structures, representations, and applications, In International Conference on Rough Sets, 2003.

15.

Nguyen

P.H.P.

and Dan

, A basic mathematical framework for conceptual graphs, IEEE Transactions on Knowledge & Data Engineering 18(2) (2006), 261–271.

16.

Pedrycz

, Granular Computing: An Introduction, 2000.

17.

Qian

, Liang

and Dang

, Incomplete multigranulation rough set, IEEE Transactions on Systems, Man, and Cybernetics – Part A: Systems and Humans 40(2) (2010), 420–431.

18.

Qian

, Liang

, Yao

and Dang

, Mgrs: A multi-granulation rough set ą,, Information Sciences An International Journal 180(6) (2010), 949–970.

19.

Shao

MingWen

, Lv

MengMeng

, Li

KenWen

and Wang

ChangZhong

, The construction of attribute(object)-oriented multi-granularity concept lattices, International Journal of Machine Learning and Cybernetics, pages 1–16, 2018.

20.

Wille

, Restructuring lattice theory: An approach based on hierarchies of concepts, Orderd Sets D Reidel 83 (1982), 314–339.

21.

Xie

, Yang

and Li

, Rule acquisition and optimal scale selection in multi-scale formal decision con-texts and their applications to smart city,, Future Generation Computer Systems 83 (2018), 564–581.

22.

Yao

, Granular computing: Basic issues and possible solutions, Proceeding of the 5th Joint Conference on Computing and Information, pages 186–189, 2010.

23.

Zhang

WenXiu

, Ma

JianMin

and Fan

ShiQing

, Variable threshold concept lattices,(22), Information Sciences 177 (2007), 4883–4892.

24.

Zhao

, Li

, Liu

and Xu

, Cognitive concept learning from incomplete information, International Journal of Machine Learning & Cybernetics 7(4) (2016), 1–12.

The construction of multi-granularity concept lattices

Abstract

Keywords

1 Introduction

2 Preliminaries

Table 1 A formal context a b c d 1 1 1 0 1 2 0 0 1 0 3 1 1 0 1 4 1 0 1 1 5 1 0 1 1 6 1 1 0 0

3.2 The construction of coarse-granularity formal concept lattice

4 Conclusion

Footnotes

Acknowledgment

References

Table 1
A formal context

a b c d

1 1 1 0 1

2 0 0 1 0

3 1 1 0 1

4 1 0 1 1

5 1 0 1 1

6 1 1 0 0