# Attribute Extended Algorithm of Lattice-Valued Concept Lattice Based on Congener Formal Context

Authors: Li Yang; Yang Xu
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

This paper is the continuation of our research work about lattice-valued concept lattice based on lattice implication algebra. For a better application of lattice-valued concept lattice into data distributed storage and parallel processing, it is necessary to research attribute extended algorithm based on congener formal context. The definitions of attribute extended formal context and congener formal context are proposed. On condition that the extent set stays invariable when the new attribute is increased, the necessary and sufficient conditions of forming attribute values are researched. Based on these conditions, the algorithms of generating lattice-valued congener formal context and establishing concept lattice are given, by which we can provide a useful basis for union algorithm and constructing algorithm of lattice-valued concept lattices in distributed and parallel system.


---

## Body

## 1. Introduction

Concept lattice (also called formal concept analysis FCA) was proposed by Wille [1–3] in 1982, and its ideological core is constructing the binary relation between objects and attributes based on bivalent logic. Facing the massive fuzzy information existed in reality, fuzzy concept lattice has appeared [4–9], which is used to describe the fuzzy relation between objects and attributes. As a conceptual clustering method, concept lattices have been proved to benefit machine learning, information retrieval, and knowledge discovery.Lattice-valued concept lattice talked about in this paper, which can be looked as another different kind of fuzzy concept lattice, is constructed on the structure of lattice implication algebra. Its key point different from the classical fuzzy concept lattice is that its values range is not general interval[
0,1
] but a complete lattice structure, on which incomparability fuzzy information can be dealt with very well. This selection of lattice implication algebra has two advantages in contrast to general structure. The first computational process of lattice-valued formal concepts is closed under the fuzzy operation; the second complicated inference is avoided in setting up Galois connection of lattice-valued concept lattice. A large amount of research on lattice-valued concept lattice may be referred to [10–12]. While for lattice implication algebra, Xu et al. [13–15] proposed this concept by combining lattice and implication algebra in the 1980s in order to depict uncertainty information more factually.With the rapid development of network technology, especial in the internet area, distributed storage and parallel processing of data are urgently needed. Distributed construction idea [16, 17] of concept lattice is firstly to form several subcontexts by dividing formal context and then construct the corresponding sublattices and get required concept lattice through combing these sublattices in the end; simply speaking, this idea is to construct concept lattice through combing several sublattices. Based on the horizontal and vertical resolution in formal contexts [18, 19], the union of multiple classical concept lattices includes the horizontal union and vertical union. And these two kinds of union algorithms have their respective preconditions required for formal contexts, which are the same objects sets for the horizontal union and the same attributes sets for the vertical union. However, for lattice-valued concept lattice, it is impossible to execute union operation on the formal contexts by only guaranteeing the same object sets or the same attribute sets, because the formal concepts derived from different formal contexts only with the same objects sets or the same attributes sets will belong to the different types. Therefore, if we want to combine, distributed, and construct the lattice-valued concept lattices, the different formal contexts should be guaranteed to possess both the same object sets and the same attribute sets. According to the three different situations that existed in formal contexts: the same object sets but the different attribute sets, the same attribute sets but the different object sets, the different object sets, and the different attributes, this paper mainly researches the required conditions with attribute increasing, under which the new established lattice-valued concept lattice has the invariable extent set—it is called as congener formal context and then obtains attribute extended algorithm of lattice-valued concept lattices based on congener formal context. The advantages of this algorithm are (i) it is helpful for multiple contexts with different attribute sets to have the same object sets and the same attribute sets and very convenient to execute union operation on multiple concept lattices; (ii) it is also used to improve the reduction ability of lattice-valued concept lattice [20–22], that is, based on the idea of this algorithm; a complicated lattice-valued concept lattice can be divided into several easier sublattices in order to realize reduction, and these sublattices can also be combined by the relevant union algorithm.Based on these analyses, this paper puts forward attribute extended algorithm of lattice-valued concept lattice based on congener formal context. In Section2, we give an overview of classical concept lattice and lattice implication algebra. In Section 3, the related works of lattice-valued concept lattice are briefly summarized. Successively, the definitions of attribute extended formal context and congener formal context are proposed in Section 4, where we show the relevant attribute extended judgment theorems based on congener formal context and give the generation algorithms of attribute extended formal context and lattice-valued formal concepts and make the algorithm analysis among the Bordat algorithm, extended algorithm and union algorithm, respectively. Concluding remarks are presented in Section 5.


## 2. Concept Lattice and Lattice Implication Algebra

In this section, we review briefly the classical concept lattices and lattice implication algebra and they are the foundations of constructing lattice-valued concept lattice.Definition 1 (Birkhoff [1]).
A partial ordered set (poset) is a set, in which a binary relation≤ is defined, which satisfies the following conditions: for any x, y, z,(1)
x
≤
x, for any x (reflexive),
(2)
x
≤
y and y
≤
x implies x
=
y (antisymmetry),
(3)
x
≤
y and y
≤
z implies x
≤
z (transitivity).Definition 2 (Birkhoff [1]).
LetL be an arbitrary set, and let there be given two binary operations on L, denoted by ∧ and ∨. Then the structure (
L
,
∧
,
∨
) is an algebraic structure with two binary operations. We call the structure (
L
,
∧
,
∨
) a lattice provided that it satisfies the following properties:(1)
for anyx
,
y
,
z
∈
L, x
∧
(
y
∧
z
)
=
(
x
∧
y
)
∧
z and x
∨
(
y
∨
z
)
=
(
x
∨
y
)
∨
z;
(2)
for anyx
,
y
∈
L, x
∧
y
=
y
∧
x and x
∨
y
=
y
∨
x;
(3)
for anyx
∈
L, x
∧
x
=
x and x
∨
x
=
x;
(4)
for anyx
,
y
∈
L, x
∧
(
x
∨
y
)
=
x and x
∨
(
x
∧
y
)
=
x.Definition 3 (Ganter and Wille [3]).
The formal context of classical concept lattice is defined as a set structure(
G
,
M
,
I
) consisting of sets G and M and a binary relation I
⊆
G
×
M. The elements of G and M are called objects and attributes, respectively, and the relationship g
I
m is read: the object g has the attribute m. For a set of objects A
⊆
G, A
* is defined as the set of features shared by all the objects in A; that is,
(1)
A
*
=
{
m
∈
M
∣
g
I
m
∀
g
∈
A
}
.
Similarly, for B
⊆
M, B
* is defined as the set of objects that possess all the features in B; that is,
(2)
B
*
=
{
g
∈
G
∣
g
I
m
∀
m
∈
B
}
.Definition 4 (Ganter and Wille [3]).
A formal concept of the context(
G
,
M
,
I
) is defined as a pair (
A
,
B
) with A
⊆
G, B
⊆
M and A
*
=
B, B
*
=
A. The set A is called the extent and B the intent of the concept (
A
,
B
).Definition 5 (Xu [13]).
Let(
L
,
∧
,
∨
,
O
,
I
) be a bounded lattice with an order-reversing involution ′, I, and O the greatest and the smallest element of L, respectively, and let →
:
L
×
L
→
L  be a mapping. If the following conditions hold for any x
,
y
,
z
∈
L:(1)
x
→
(
y
→
z
)
=
y
→
(
x
→
z
),
(2)
x
→
x
=
I,
(3)
x
→
y
=
y
′
→
x
′,
(4)
x
→
y
=
y
→
x
=
I implies x
=
y,
(5)
(
x
→
y
)
→
y
=
(
y
→
x
)
→
x,
(6)
(
x
∨
y
)
→
z
=
(
x
→
z
)
∧
(
y
→
z
),
(7)
(
x
∧
y
)
→
z
=
(
x
→
z
)
∨
(
y
→
z
),then (
L
,
∧
,
∨
,
′
,
→
,
O
,
I
) is called a lattice implication algebra (LIA).Example 6 (Xu [13]).
LetL
=
{
O
,
a
,
b
,
c
,
d
,
I
}, O
′
=
I, a
′
=
c, b
′
=
d, c
′
=
a, d
′
=
b, I
′
=
O, the Hasse diagram of L be defined as Figure 1, and its implication operation be defined as Table 1, then (
L
,
∧
,
∨
,
′
,
→
,
O
,
I
) is a lattice implication algebra.Table 1
Implication Operation ofL
=
{
O
,
a
,
b
,
c
,
d
,
I
}.
⟶
O
a
b
c
d
I
O
I
I
I
I
I
I
a
c
I
b
c
b
I
b
d
a
I
b
a
I
c
a
a
I
I
a
I
d
b
I
I
b
I
I
I
O
a
b
c
d
IFigure 1
Hasse diagram of(
L
,
∧
,
∨
,
′
,
→
,
O
,
I
).


## 3. Lattice-Valued Concept Lattice

Lattice-valued concept lattice is the combination of classical concept lattice and lattice implication algebra and its ideological core is constructing lattice-valued relation between objects and attributes. It can be used to directly deal with incomparability fuzzy information and is totally different from classical fuzzy concept lattice. In this section, we study the definitions and theorems of lattice-valued concept lattice and give an example to illustrate it.Definition 7.
A four-tupleK
=
(
G
,
M
,
L
n
,
I
~
) is called an n-ary lattice-valued formal context, where G
=
{
g
1
,
g
2
,
…
,
g
r
} is the set of objects, M
=
{
m
1
,
m
2
,
…
,
m
s
} is the set of attributes, L
n is an n-ary lattice implication algebra, and I
~ is a fuzzy relation between G and M; that is, I
~
:
G
×
M
→
L
n.LetG be a nonempty objects set and (
L
n
,
∨
,
∧
,
′
,
→
) an n-ary lattice implication algebra. Denote the set of all the L
n-fuzzy subsets on G as L
n
G, for any A
~
1
,
A
~
2
∈
L
n
G,
(3)
A
~
1
⊆
A
~
2
⟺
A
~
1
(
g
)
≤
A
~
2
(
g
)
,
g
∈
G
;
then (
L
n
G
,
⊆
) is a partial ordered set.LetM be a nonempty attributes set and (
L
n
,
∨
,
∧
,
′
,
→
) an n-ary lattice implication algebra. Denote the set of all the L
n-fuzzy subsets on Mas L
n
M, for any B
~
1
,
B
~
2
∈
L
n
M,
(4)
B
~
1
⊆
B
~
2
⟺
B
~
1
(
m
)
≤
B
~
2
(
m
)
,
m
∈
M
,
then (
L
n
M
,
⊆
) is a partial ordered set.Theorem 8 (Yang and Xu [10]).
LetK
=
(
G
,
M
,
L
n
,
I
~
) be an n-ary lattice-valued formal context and let L
n be an n-ary lattice implication algebra; define mappings f
1, f
2 between L
n
G and L
n
M:
(5)
f
1
:
L
n
G
⟶
L
n
M
,
f
1
(
A
~
)
(
m
)
=
∧
g
∈
G
(
A
~
(
g
)
⟶
I
~
(
g
,
m
)
)
,
f
2
:
L
n
M
⟶
L
n
G
,
f
2
(
B
~
)
(
g
)
=
∧
m
∈
M
(
B
~
(
m
)
⟶
I
~
(
g
,
m
)
)
;
then for any A
~
∈
L
G, B
~
∈
L
M, (
f
1
,
f
2
) is a Galois connection based on lattice implication algebra.Theorem 9 (Yang and Xu [10]).
LetK
=
(
G
,
M
,
L
n
,
I
~
) be a lattice-valued formal context and (
f
1
,
f
2
) the Galois connection, for any A
~
1
,
A
~
2
,
A
∈
L
n
G, B
~
1
,
B
~
2
,
B
∈
L
n
M; there are the following properties:(1)
A
~
1
⊆
A
~
2
⇒
f
1
(
A
~
2
)
⊆
f
1
(
A
~
1
), B
~
1
⊆
B
~
2
⇒
f
2
(
B
~
2
)
⊆
f
2
(
B
~
1
);
(2)
A
~
⊆
f
2
f
1
(
A
~
), B
~
⊆
f
1
f
2
(
B
~
).Definition 10.
LetK
=
(
G
,
M
,
L
n
,
I
~
) be an n-ary lattice-valued formal context; denote the set
(6)
L
(
K
)
=
{
(
A
~
,
B
~
)
∣
f
1
(
A
~
)
=
B
~
,
f
2
(
B
~
)
=
A
~
}
,
and define
(7)
(
A
~
1
,
B
~
1
)
≤
(
A
~
2
,
B
~
2
)
⟺
A
~
1
⊆
A
~
2
(
or
B
~
2
⊆
B
~
1
)
.Theorem 11.
LetK
=
(
G
,
M
,
L
n
,
I
~
) be an n-ary lattice-valued formal context; define the operations ∧ and ∨ on L
(
G
,
M
,
L
n
,
I
~
) as
(8)
∧
j
(
A
~
j
,
B
~
j
)
=
(
⋂
j
A
~
j
,
f
1
f
2
(
⋃
j
B
~
j
)
)
,
∨
j
(
A
~
j
,
B
~
j
)
=
(
f
2
f
1
(
⋃
j
A
~
j
)
,
⋂
j
B
~
j
)
;
then L
(
K
) is a complete lattice.Proof.
For any(
A
~
j
,
B
~
j
)
,
(
A
~
k
,
B
~
k
)
∈
L
(
K
), k
∈
J, and by Theorem 9
(
1
),
(9)
⋂
j
∈
J
A
~
j
⊆
A
~
k
⟹
f
2
f
1
(
⋂
j
∈
J
A
~
j
)
⊆
f
2
f
1
(
A
~
k
)
=
A
~
k
⟹
f
2
f
1
(
⋂
j
∈
J
A
~
j
)
⊆
⋂
k
∈
J
A
~
k
=
⋂
j
∈
J
A
~
j
.
By Theorem 9
(
2
), we can get
(10)
⋂
j
∈
J
A
~
j
⊆
f
2
f
1
(
⋂
j
∈
J
A
~
j
)
;
thus,
(11)
⋂
j
∈
J
A
~
j
=
f
2
f
1
(
⋂
j
∈
J
A
~
j
)
;
by Theorem 9,
(12)
f
1
(
⋂
j
∈
J
A
~
j
)
=
f
1
(
⋂
j
∈
J
f
2
(
B
~
j
)
)
=
f
1
f
2
(
⋃
j
∈
J
B
~
j
)
,
it follows that (
∩
j
∈
J
A
~
j
,
f
1
f
2
(
∪
j
∈
J
B
~
j
)
)
=
(
∩
j
∈
J
A
~
j
,
f
1
(
∩
j
∈
J
A
~
j
)
)
∈
L
(
K
); obviously, (
∩
j
∈
J
A
~
j
,
f
1
f
2
(
∪
j
∈
J
B
~
j
)
) is the lower bound of L
(
K
); on the other hand, suppose that (
A
~
,
B
~
) is a lower bound of L
(
K
); then
(13)
A
~
⊆
A
~
j
⇒
A
~
⊆
⋂
j
∈
J
A
~
j
;
that is,
(14)
(
A
~
,
B
~
)
≤
(
⋂
j
∈
J
A
~
j
,
f
1
f
2
(
⋃
j
∈
J
B
~
j
)
)
,
so
(15)
∧
j
∈
J
(
A
~
j
,
B
~
j
)
=
(
⋂
j
∈
J
A
~
j
,
f
1
f
2
(
⋃
j
∈
J
B
~
j
)
)
∨
j
∈
J
(
A
~
j
,
B
~
j
)
=
(
f
2
f
1
(
⋃
j
∈
J
A
~
j
)
,
⋂
j
∈
J
B
~
j
)
can be proved similarly.
Thus,(
L
(
K
)
,
≤
) is a complete lattice.Example 12.
A lattice-valued formal context and its concept lattice based on the 4-ary lattice implication algebra are shown in Figures2 and 3 and Tables 2 and 3.
In this Hasse diagram (see Figures2 and 3), the fuzzy concepts are shown as follows:0#:(
{
I
,
I
}
,
{
O
,
O
,
a
}
),
1#:(
{
a
,
I
}
,
{
b
,
O
,
a
}
),
2#:(
{
I
,
a
}
,
{
O
,
b
,
I
}
),
3#:(
{
I
,
b
}
,
{
a
,
O
,
a
}
),
4#:(
{
a
,
a
}
,
{
b
,
b
,
I
}
),
5#:(
{
a
,
b
}
,
{
I
,
O
,
a
}
),
6#:(
{
b
,
b
}
,
{
a
,
a
,
a
}
),
7#:(
{
I
,
O
}
,
{
a
,
b
,
I
}
),
8#:(
{
a
,
O
}
,
{
I
,
b
,
I
}
),
9#:(
{
O
,
b
}
,
{
I
,
a
,
a
}
),
10#:(
{
b
,
O
}
,
{
a
,
I
,
I
}
),
11#:(
{
O
,
O
}
,
{
I
,
I
,
I
}
).Table 2
Implication operator ofL
=
{
O
,
a
,
b
,
I
}.
⟶
I
a
b
O
I
I
a
b
O
a
I
I
b
b
b
I
a
I
a
O
I
I
I
ITable 3
Lattice-valued formal contextK
=
(
G
,
M
,
L
4
,
I
~
).
m
1
m
2
m
3
g
1
a
b
I
g
2
b
O
aFigure 2
Hasse diagram of 4-ary lattice implication algebraL
=
{
O
,
a
,
b
,
I
}.Figure 3
Hasse diagram of lattice-valued concept lattice ofK.


## 4. Attribute Extended Algorithm of Lattice-Valued Concept Lattice

In the pioneering work of extended algorithm of concept lattice, many researchers put emphasis on reconstructing algorithm of concept lattice in adding attributes, and in this reconstructing process, the structure of original concept lattice generally may be changed. Up to now, there have not been any researches on extended algorithm of fuzzy concept lattice, because attribute increase will bound to be leading to the fundamental changes in the fuzzy concepts, and so will be bringing for the structure of lattice-valued concept lattice. In this section, we propose the definitions of attribute extended context and congener context. The relevant judgment theorems and algorithms are to be talked about.


### 4.1. Attribute Extended Theory of Lattice-Valued Fuzzy Concept Lattice

Definition 13.
LetK
=
(
G
,
M
,
L
n
,
I
~
) be an n-ary lattice-valued formal context; the four-tuple K
M
=
(
G
,
M
+
,
L
n
,
I
~
+
) is called an n-ary lattice-valued attribute extended formal context of K, where G is a set of objects, M
+
⊇
M is an extended set of attributes, L
n is an n-ary lattice implication algebra, and I
~
+ is the fuzzy relation of G and M
+; that is, I
~
+
:
G
×
M
+
→
L
n and ∀
g
∈
G, m
∈
M
∩
M
+, satisfying
(16)
g
I
~
m
=
g
I
~
+
m
.For the above formal contexts, there are relevant concept lattices that can be denoted byL
(
G
,
M
,
L
n
,
I
~
), L
(
G
,
M
+
,
L
n
,
I
~
), respectively. And denote the set
(17)
Α
~
=
{
A
~
∣
(
A
~
,
B
~
)
∈
L
(
G
,
M
,
L
n
,
I
~
)
}
,
(18)
Β
~
=
{
B
~
∣
(
A
~
,
B
~
)
∈
L
(
G
,
M
,
L
n
,
I
~
)
}
;
(19)
Α
~
M
=
{
A
~
∣
(
A
~
,
B
~
+
)
∈
L
(
G
,
M
+
,
L
n
,
I
~
)
}
,
(20)
Β
~
M
=
{
B
~
+
∣
(
A
~
,
B
~
+
)
∈
L
(
G
,
M
+
,
L
n
,
I
~
)
}
.Definition 14.
LetK
=
(
G
,
M
,
L
n
,
I
~
) be an n-ary lattice-valued formal context and K
M
=
(
G
,
M
+
,
L
n
,
I
~
+
) an n-ary lattice-valued attribute extended forma context. K
M is called congener formal context of K if
(21)
Α
~
M
=
Α
~
;
accordingly, L
(
K
M
) is called congener concept lattice of L
(
K
).For ann-ary lattice-valued attribute extended formal context K
M
=
(
G
,
M
+
,
L
n
,
I
~
+
), (
f
1
,
f
2
) is a Galois connection between G and M
+, ∀
A
~
∈
L
n
G, m
∈
M, and m
+
∈
M
+; denote
(22)
f
1
(
A
~
)
(
m
)
=
B
~
∈
L
n
M
,
f
1
(
A
~
)
(
m
+
)
=
B
~
+
∈
L
n
M
+
.Theorem 15.
LetK
M
=
(
G
,
M
+
,
L
n
,
I
~
+
) be an n-ary lattice-valued attribute extended formal context of K, ∀
A
~
∈
L
n
G, m
∈
M, m
+
∈
M
+,and g
∈
G; then K
M is the congener formal context of K if and only if
(23)
f
2
(
B
~
+
)
(
g
)
=
f
2
(
B
~
)
(
g
)
.Proof.
Consider that∀
A
~
∈
Α
~
M, ∃
(
A
~
,
B
~
+
)
∈
L
(
G
,
M
+
,
L
n
,
I
~
); that is, (
f
2
(
B
~
+
)
(
g
)
,
B
~
+
)
∈
L
(
G
,
M
+
,
L
n
,
I
~
); ∀
A
~
∈
Α
~, ∃
(
A
~
,
B
~
)
∈
L
(
G
,
M
,
L
n
,
I
~
); that is, (
f
2
(
B
~
)
(
g
)
,
B
~
)
∈
L
(
G
,
M
,
L
n
,
I
~
); by Definition 14, K
M is the congener formal context of K
⇔
Α
~
M
=
Α
~
⇔
f
2
(
B
~
+
)
(
g
)
=
f
2
(
B
~
)
(
g
).Theorem 16.
LetK
M
=
(
G
,
M
+
,
L
n
,
I
~
+
) be an n-ary lattice-valued attribute extended formal context of K, ∀
A
~
∈
L
n
G, n
∈
M
+
/
M,and g
∈
G; then K
M is the congener formal context of K if and only if
(24)
f
2
(
B
~
)
(
g
)
≤
f
2
(
f
1
(
A
~
)
(
n
)
)
(
g
)
.Proof.
By Theorem15, K
M is the congener formal context of K:
(25)
⟺
f
2
(
B
~
+
)
(
g
)
=
f
2
(
B
~
)
(
g
)
⟺
f
2
(
B
~
)
(
g
)
∧
f
2
(
f
1
(
A
~
)
(
n
)
)
(
g
)
=
f
2
(
B
~
)
(
g
)
⟺
f
2
(
B
~
)
(
g
)
≤
f
2
(
f
1
(
A
~
)
(
n
)
)
(
g
)
.Corollary 17.
LetK
M
=
(
G
,
M
+
,
L
n
,
I
~
+
) be an n-ary lattice-valued attribute extended formal context of K, ∀
A
~
∈
L
n
G, n
∈
M
+
/
M, and g
∈
G; then K
M is the congener formal context of K, if ∃
m
j
∈
M, 1
≤
j
≤
s, such that
(26)
f
2
(
f
1
(
A
~
)
(
m
j
)
)
(
g
)
≤
f
2
(
f
1
(
A
~
)
(
n
)
)
(
g
)
.Theorem 18.
LetK
M
=
(
G
,
M
+
,
L
n
,
I
~
+
) be an n-ary lattice-valued attribute extended formal context of K, ∀
A
~
∈
L
n
G, n
∈
M
+
/
M, and g
∈
G; then K
M is the congener fuzzy context of K if  ∃
m
j
1
,
m
j
2
∈
M, 1
≤
j
1
,
j
2
≤
s, such that
(27)
I
~
+
(
g
,
n
)
=
I
~
(
g
,
m
j
1
)
∧
I
~
(
g
,
m
j
2
)
.Proof.
By Theorem16,
(28)
f
2
(
f
1
(
A
~
)
(
n
)
)
(
g
)
=
∧
n
∈
M
+
/
M
(
f
1
(
A
~
)
(
n
)
⟶
I
~
+
(
g
,
n
)
)
=
∧
n
∈
M
+
/
M
(
∧
g
∈
G
(
A
~
(
g
)
⟶
I
~
+
(
g
,
n
)
)
⟶
I
~
+
(
g
,
n
)
)
=
∧
g
∈
G
(
A
~
(
g
)
⟶
I
~
(
g
,
m
j
1
)
∧
I
~
(
g
,
m
j
2
)
)
⟶
(
I
~
(
g
,
m
j
1
)
∧
I
~
(
g
,
m
j
2
)
)
=
(
(
f
1
(
A
~
)
(
m
j
1
)
∧
f
1
(
A
~
)
(
m
j
2
)
)
⟶
I
~
(
g
,
m
j
1
)
)
∧
(
(
f
1
(
A
~
)
(
m
j
1
)
∧
f
1
(
A
~
)
(
m
j
2
)
)
⟶
I
~
(
g
,
m
j
2
)
)
≥
(
f
1
(
A
~
)
(
m
j
1
)
⟶
I
~
(
g
,
m
j
1
)
)
∧
(
f
1
(
A
~
)
(
m
j
2
)
⟶
I
~
(
g
,
m
j
2
)
)
≥
∧
m
∈
M
(
f
1
(
A
~
)
(
m
)
⟶
I
~
(
g
,
m
)
)
=
f
2
(
B
~
)
(
g
)
,
so K
M is the congener fuzzy context of K.Corollary 19.
LetK
M
=
(
G
,
M
+
,
L
n
,
I
~
+
) an n-ary lattice-valued attribute extended formal context of K, ∀
A
~
∈
L
n
G, n
∈
M
+
/
M, and g
∈
G; then K
M is the congener formal context of K if ∃
m
j
1
,
m
j
2
,
…
,
m
j
k
∈
M, 1
≤
j
1
,
j
2
,
…
,
j
k
≤
s, such that
(29)
I
~
+
(
g
,
n
)
=
∧
p
=
1
k
I
~
(
g
,
m
j
p
)
.Theorem 20.
LetK
M
=
(
G
,
M
+
,
L
n
,
I
~
+
) be an n-ary lattice-valued attribute extended formal context of K, ∀
A
~
∈
L
n
G, n
∈
M
+
/
M, and g
∈
G; then K
M is the congener formal context of K if
(30)
I
~
+
(
g
,
n
)
=
I
.Proof.
By Theorem16,
(31)
f
2
(
f
1
(
A
~
)
(
n
)
)
(
g
)
=
∧
n
∈
M
+
/
M
(
f
1
(
A
~
)
(
n
)
⟶
I
~
+
(
g
,
n
)
)
=
∧
n
∈
M
+
/
M
(
f
1
(
A
~
)
(
n
)
⟶
I
)
=
I
≥
f
2
(
B
~
)
(
g
)
,
so K
M is the congener fuzzy context of K.


### 4.2. Attribute Extended Algorithm of Lattice-Valued Concept Lattice

For general fuzzy concept lattice which is constructed on the interval[
0,1
], attribute effective increased will inevitably change the number of fuzzy concepts and the structure of fuzzy concept lattice. But, for lattice-valued concept lattice, attribute conditional increased which is researched in this paper and will not change the number of formal concepts and the structure of concept lattice. We explain this through Algorithms 1 and 2.Algorithm 1:Generation algorithm of K
M
=
(
G
,
M
+
,
L
n
,
I
~
+
).
Input: then-ary lattice-valued formal context K
=
(
G
,
M
,
L
n
,
I
~
), let M
+
=
M
Output: then-ary lattice-valued attribute extended formal context K
M
=
(
G
,
M
+
,
L
n
,
I
~
+
)
Begin
while ((
G
,
M
,
L
n
,
I
~
)
≠
Φ) do
Calculate the attribute values  I
~
(
g
,
m
j
)  of each attribute  m
j
∈
M
for each  I
~
(
g
,
m
j
1
), I
~
(
g
,
m
j
2
)
∈
K
do
if
I
~
(
g
,
m
j
1
)
∧
I
~
(
g
,
m
j
2
)
≠
Φ
then
I
~
+
(
g
,
n
)
:
=
I
~
(
g
,
m
j
1
)
∧
I
~
(
g
,
m
j
2
)
M
+
:
=
M
∪
{
n
}
else
M
+
=
M
endif;
for each  I
~
(
g
,
m
j
1
), I
~
(
g
,
m
j
2
)
,
…, I
~
(
g
,
m
j
k
)
∈
K
do
if
∧
p
=
1
k
I
~
(
g
,
m
j
p
)
≠
Φ
then
I
~
+
(
g
,
n
)
:
=
∧
p
=
1
k
I
~
(
g
,
m
j
p
)
M
+
:
=
M
∪
{
n
}
else
M
+
=
M
endif;
for
L
n
do
if
∃
I
∈
L
n
then
I
~
+
(
g
,
n
)
:
=
I
M
+
:
=
M
∪
{
n
}
else
M
+
=
M
endif;
endif
endfor;
endfor;
endAlgorithm 2:Generation algorithm of formal concepts.
Input: then-ary lattice-valued concept lattice L
(
G
,
M
,
L
n
,
I
~
)
Output: then-ary lattice-valued attribute extended concept lattice L
(
G
,
M
+
,
L
n
,
I
~
+
)
Begin
while ((
G
,
M
,
L
n
,
I
~
)
≠
Φ) do
Calculate the formal concepts (
A
~
,
B
~
) of K
=
(
G
,
M
,
L
n
,
I
~
)
for each  (
A
~
,
B
~
)
∈
L
(
G
,
M
,
L
n
,
I
~
), denote  A
~
=
(
A
~
(
g
1
)
,
A
~
(
g
2
)
,
…
,
A
~
(
g
r
)
)
∈
Α
~,
B
~
=
(
B
~
(
m
1
)
,
B
~
(
m
2
)
,
…
,
B
~
(
m
s
)
)
∈
Α
~
do
if
∃
n
∈
M
+, s.t., I
~
+
(
g
,
n
)
=
I
~
(
g
,
m
j
1
)
∧
I
~
(
g
,
m
j
2
)
,
m
j
1
,
m
j
2
∈
M
then
B
~
+
=
(
B
~
(
m
1
)
,
…
,
B
~
(
m
s
)
,
B
~
(
m
j
1
)
∧
B
~
(
m
j
2
)
)
(
A
~
,
B
~
+
)
∈
L
(
G
,
M
+
,
L
n
,
I
~
+
)
else
(
A
~
,
B
~
+
)
∉
L
(
G
,
M
+
,
L
n
,
I
~
+
)
endif;
if
∃
n
∈
M
+, s.t., I
~
+
(
g
,
n
)
=
∧
p
=
1
k
I
~
(
g
,
m
j
p
)
,
m
j
1
,
m
j
2
,
…
,
m
j
k
∈
M
then
B
~
+
=
(
B
~
(
m
1
)
,
…
,
B
~
(
m
s
)
,
∧
p
=
1
k
I
~
(
g
,
m
j
p
)
)
(
A
~
,
B
~
+
)
∈
L
(
G
,
M
+
,
L
n
,
I
~
+
)
else
(
A
~
,
B
~
+
)
∉
L
(
G
,
M
+
,
L
n
,
I
~
+
)
endif;
if
∃
n
∈
M
+, s.t., I
~
+
(
g
,
n
)
=
I
,
I
∈
L
n
then
(
A
~
,
B
~
+
)
∈
L
(
G
,
M
+
,
L
n
,
I
~
+
)
else
(
A
~
,
B
~
+
)
∉
L
(
G
,
M
+
,
L
n
,
I
~
+
)
endif;
endif
endif;
endfor;
endExample 21.
For Table3, a 4-ary lattice-valued formal context K
=
(
G
,
M
,
L
4
,
I
~
), we can compute its congener formal context as Table 4.
In this formal contextK
M, M
+
=
{
m
1
,
m
2
,
…
,
m
5
}, I
~
+
:
G
×
M
+
→
L
4, and it follows that ∀
g
∈
G, I
~
+
(
g
,
m
4
)
=
I
~
(
g
,
m
1
)
∧
I
~
(
g
,
m
2
), I
~
+
(
g
,
m
5
)
=
I. According to the theorems and algorithms of attribute increased, the formal concepts of K
M are directly derived from the relevant formal concepts of K as follows:0#:(
{
I
,
I
}
,
{
O
,
O
,
a
,
O
,
I
}
),
1#:(
{
a
,
I
}
,
{
b
,
O
,
a
,
O
,
I
}
),
2#:(
{
I
,
a
}
,
{
O
,
b
,
I
,
O
,
I
}
),
3#:(
{
I
,
b
}
,
{
a
,
O
,
a
,
O
,
I
}
),
4#:(
{
a
,
a
}
,
{
b
,
b
,
I
,
b
,
I
}
),
5#:(
{
a
,
b
}
,
{
I
,
O
,
a
,
O
,
I
}
),
6#:(
{
b
,
b
}
,
{
a
,
a
,
a
,
a
,
I
}
),
7#:(
{
I
,
O
}
,
{
a
,
b
,
I
,
O
,
I
}
),
8#:(
{
a
,
O
}
,
{
I
,
b
,
I
,
b
,
I
}
),
9#:(
{
O
,
b
}
,
{
I
,
a
,
a
,
a
,
I
}
),
10#:(
{
b
,
O
}
,
{
a
,
I
,
I
,
a
,
I
}
),
11#:(
{
O
,
O
}
,
{
I
,
I
,
I
,
I
,
I
}
).Table 4
The congener formal contextK
M
=
(
G
,
M
+
,
L
4
,
I
~
+
) of K.
m
1
m
2
m
3
m
4
m
5
g
1
a
b
I
a
I
g
2
b
O
a
O
I


### 4.3. Algorithm Analysis

The time complexity of creating concept lattices is the major factor in analyzing the complexity of the algorithm, and computing the formal concepts plays the key role in the whole process of constructing concept lattices. Suppose that the lattice-valued formal context isK
=
(
G
,
M
,
L
n
,
I
~
), where G
=
{
g
1
,
g
2
,
…
,
g
r
}, M
=
{
m
1
,
m
2
,
…
,
m
s
1
}, r, s
1, and n are the positive integers. If we compute the formal concepts under Bordat algorithm, the calculation times of the formal concepts are r
×
n
s
1
(
1
+
s
1
). When increasing s
2 attributes, the calculation times of the formal concepts are changed into r
×
n
s
1
+
s
2
(
1
+
s
1
+
s
2
).If we utilize the extended algorithm, the increaseds
2 attributes can be directly obtained by the preliminary s
1 attributes, so the calculation times of the formal concepts are r
×
n
s
1
(
1
+
s
1
)
+
s
2. Compared with Bordat algorithm, the calculation times of the formal concepts is r
×
n
s
1
(
1
+
s
1
)
+
s
2
≪
r
×
n
s
1
+
s
2
(
1
+
s
1
+
s
2
). And under the action of the extended algorithm, we can also firstly decompose the lattice-valued formal context K
=
(
G
,
M
,
L
n
,
I
~
) into several subformal contexts; that is, {
m
1
,
…
,
m
s
1
}
=
{
m
1
,
…
,
m
s
11
}
∪
{
m
s
11
+
1
,
…
,
m
s
11
+
s
12
}
∪
⋯
∪
{
m
s
1
(
p
-
1
)
+
1
,
…
,
m
s
1
(
p
-
1
)
+
s
1
p
}, where s
1
=
s
11
+
s
12
+
⋯
+
s
1
p, s
11
,
s
12
,
…
,
s
1
p are also the positive integers, and the combination algorithm is executed on them; then the calculation times of the formal concepts is ∑
j
=
1
p
r
×
n
s
1
j
(
1
+
s
1
j
). Because of s
11
,
s
12
,
…
,
s
1
p
<
s
1, we can get r
×
n
s
1
j
(
1
+
s
1
j
)
≪
r
×
n
s
1
(
1
+
s
1
), j
=
1,2
,
…
,
p; then ∑
j
=
1
p
r
×
n
s
1
j
(
1
+
s
1
j
)
+
s
2
≪
r
×
n
s
1
(
1
+
s
1
)
+
s
2; that is to say, the complexity of this algorithm is significantly decreased.Suppose thatK
=
(
G
,
M
,
L
6
,
I
~
) is the lattice-valued formal context based on 6-ary lattice implication algebra, where G
=
{
g
1
,
g
2
,
…
,
g
10
}, M
=
{
m
1
,
m
2
,
…
,
m
50
}. When increasing 10, 20, 30, 40, and 50 attributes into M, we can obtain attributes set M
1
=
{
m
1
,
m
2
,
…
,
m
60
}, M
2
=
{
m
1
,
m
2
,
…
,
m
70
}, M
3
=
{
m
1
,
m
2
,
…
,
m
80
}, M
4
=
{
m
1
,
m
2
,
…
,
m
90
}, and M
5
=
{
m
1
,
m
2
,
…
,
m
100
}. And furthermore, with the help of the extended algorithm, if we decompose K
=
(
G
,
M
,
L
6
,
I
~
) into 5 subcontexts, the calculation times will be greatly reduced. The following experiments, respectively, compare to Bordat algorithm, as Figure 4.Figure 4
Algorithms comparison of Bordat, extended, and union algorithm.In Figure4, the curve B (Bordat algorithm), E (extended algorithm), and U (union algorithm), respectively, presents the calculation times of the formal concepts. By the description of the curves in the experiments, we can draw the conclusion that Bordat algorithm cause the calculation times absolutely increased and its growth rate is far more than that of extended algorithm and union algorithm, and with the help of extended algorithm, we also can see that the calculation times are significantly decreased.


## 4.1. Attribute Extended Theory of Lattice-Valued Fuzzy Concept Lattice

Definition 13.
LetK
=
(
G
,
M
,
L
n
,
I
~
) be an n-ary lattice-valued formal context; the four-tuple K
M
=
(
G
,
M
+
,
L
n
,
I
~
+
) is called an n-ary lattice-valued attribute extended formal context of K, where G is a set of objects, M
+
⊇
M is an extended set of attributes, L
n is an n-ary lattice implication algebra, and I
~
+ is the fuzzy relation of G and M
+; that is, I
~
+
:
G
×
M
+
→
L
n and ∀
g
∈
G, m
∈
M
∩
M
+, satisfying
(16)
g
I
~
m
=
g
I
~
+
m
.For the above formal contexts, there are relevant concept lattices that can be denoted byL
(
G
,
M
,
L
n
,
I
~
), L
(
G
,
M
+
,
L
n
,
I
~
), respectively. And denote the set
(17)
Α
~
=
{
A
~
∣
(
A
~
,
B
~
)
∈
L
(
G
,
M
,
L
n
,
I
~
)
}
,
(18)
Β
~
=
{
B
~
∣
(
A
~
,
B
~
)
∈
L
(
G
,
M
,
L
n
,
I
~
)
}
;
(19)
Α
~
M
=
{
A
~
∣
(
A
~
,
B
~
+
)
∈
L
(
G
,
M
+
,
L
n
,
I
~
)
}
,
(20)
Β
~
M
=
{
B
~
+
∣
(
A
~
,
B
~
+
)
∈
L
(
G
,
M
+
,
L
n
,
I
~
)
}
.Definition 14.
LetK
=
(
G
,
M
,
L
n
,
I
~
) be an n-ary lattice-valued formal context and K
M
=
(
G
,
M
+
,
L
n
,
I
~
+
) an n-ary lattice-valued attribute extended forma context. K
M is called congener formal context of K if
(21)
Α
~
M
=
Α
~
;
accordingly, L
(
K
M
) is called congener concept lattice of L
(
K
).For ann-ary lattice-valued attribute extended formal context K
M
=
(
G
,
M
+
,
L
n
,
I
~
+
), (
f
1
,
f
2
) is a Galois connection between G and M
+, ∀
A
~
∈
L
n
G, m
∈
M, and m
+
∈
M
+; denote
(22)
f
1
(
A
~
)
(
m
)
=
B
~
∈
L
n
M
,
f
1
(
A
~
)
(
m
+
)
=
B
~
+
∈
L
n
M
+
.Theorem 15.
LetK
M
=
(
G
,
M
+
,
L
n
,
I
~
+
) be an n-ary lattice-valued attribute extended formal context of K, ∀
A
~
∈
L
n
G, m
∈
M, m
+
∈
M
+,and g
∈
G; then K
M is the congener formal context of K if and only if
(23)
f
2
(
B
~
+
)
(
g
)
=
f
2
(
B
~
)
(
g
)
.Proof.
Consider that∀
A
~
∈
Α
~
M, ∃
(
A
~
,
B
~
+
)
∈
L
(
G
,
M
+
,
L
n
,
I
~
); that is, (
f
2
(
B
~
+
)
(
g
)
,
B
~
+
)
∈
L
(
G
,
M
+
,
L
n
,
I
~
); ∀
A
~
∈
Α
~, ∃
(
A
~
,
B
~
)
∈
L
(
G
,
M
,
L
n
,
I
~
); that is, (
f
2
(
B
~
)
(
g
)
,
B
~
)
∈
L
(
G
,
M
,
L
n
,
I
~
); by Definition 14, K
M is the congener formal context of K
⇔
Α
~
M
=
Α
~
⇔
f
2
(
B
~
+
)
(
g
)
=
f
2
(
B
~
)
(
g
).Theorem 16.
LetK
M
=
(
G
,
M
+
,
L
n
,
I
~
+
) be an n-ary lattice-valued attribute extended formal context of K, ∀
A
~
∈
L
n
G, n
∈
M
+
/
M,and g
∈
G; then K
M is the congener formal context of K if and only if
(24)
f
2
(
B
~
)
(
g
)
≤
f
2
(
f
1
(
A
~
)
(
n
)
)
(
g
)
.Proof.
By Theorem15, K
M is the congener formal context of K:
(25)
⟺
f
2
(
B
~
+
)
(
g
)
=
f
2
(
B
~
)
(
g
)
⟺
f
2
(
B
~
)
(
g
)
∧
f
2
(
f
1
(
A
~
)
(
n
)
)
(
g
)
=
f
2
(
B
~
)
(
g
)
⟺
f
2
(
B
~
)
(
g
)
≤
f
2
(
f
1
(
A
~
)
(
n
)
)
(
g
)
.Corollary 17.
LetK
M
=
(
G
,
M
+
,
L
n
,
I
~
+
) be an n-ary lattice-valued attribute extended formal context of K, ∀
A
~
∈
L
n
G, n
∈
M
+
/
M, and g
∈
G; then K
M is the congener formal context of K, if ∃
m
j
∈
M, 1
≤
j
≤
s, such that
(26)
f
2
(
f
1
(
A
~
)
(
m
j
)
)
(
g
)
≤
f
2
(
f
1
(
A
~
)
(
n
)
)
(
g
)
.Theorem 18.
LetK
M
=
(
G
,
M
+
,
L
n
,
I
~
+
) be an n-ary lattice-valued attribute extended formal context of K, ∀
A
~
∈
L
n
G, n
∈
M
+
/
M, and g
∈
G; then K
M is the congener fuzzy context of K if  ∃
m
j
1
,
m
j
2
∈
M, 1
≤
j
1
,
j
2
≤
s, such that
(27)
I
~
+
(
g
,
n
)
=
I
~
(
g
,
m
j
1
)
∧
I
~
(
g
,
m
j
2
)
.Proof.
By Theorem16,
(28)
f
2
(
f
1
(
A
~
)
(
n
)
)
(
g
)
=
∧
n
∈
M
+
/
M
(
f
1
(
A
~
)
(
n
)
⟶
I
~
+
(
g
,
n
)
)
=
∧
n
∈
M
+
/
M
(
∧
g
∈
G
(
A
~
(
g
)
⟶
I
~
+
(
g
,
n
)
)
⟶
I
~
+
(
g
,
n
)
)
=
∧
g
∈
G
(
A
~
(
g
)
⟶
I
~
(
g
,
m
j
1
)
∧
I
~
(
g
,
m
j
2
)
)
⟶
(
I
~
(
g
,
m
j
1
)
∧
I
~
(
g
,
m
j
2
)
)
=
(
(
f
1
(
A
~
)
(
m
j
1
)
∧
f
1
(
A
~
)
(
m
j
2
)
)
⟶
I
~
(
g
,
m
j
1
)
)
∧
(
(
f
1
(
A
~
)
(
m
j
1
)
∧
f
1
(
A
~
)
(
m
j
2
)
)
⟶
I
~
(
g
,
m
j
2
)
)
≥
(
f
1
(
A
~
)
(
m
j
1
)
⟶
I
~
(
g
,
m
j
1
)
)
∧
(
f
1
(
A
~
)
(
m
j
2
)
⟶
I
~
(
g
,
m
j
2
)
)
≥
∧
m
∈
M
(
f
1
(
A
~
)
(
m
)
⟶
I
~
(
g
,
m
)
)
=
f
2
(
B
~
)
(
g
)
,
so K
M is the congener fuzzy context of K.Corollary 19.
LetK
M
=
(
G
,
M
+
,
L
n
,
I
~
+
) an n-ary lattice-valued attribute extended formal context of K, ∀
A
~
∈
L
n
G, n
∈
M
+
/
M, and g
∈
G; then K
M is the congener formal context of K if ∃
m
j
1
,
m
j
2
,
…
,
m
j
k
∈
M, 1
≤
j
1
,
j
2
,
…
,
j
k
≤
s, such that
(29)
I
~
+
(
g
,
n
)
=
∧
p
=
1
k
I
~
(
g
,
m
j
p
)
.Theorem 20.
LetK
M
=
(
G
,
M
+
,
L
n
,
I
~
+
) be an n-ary lattice-valued attribute extended formal context of K, ∀
A
~
∈
L
n
G, n
∈
M
+
/
M, and g
∈
G; then K
M is the congener formal context of K if
(30)
I
~
+
(
g
,
n
)
=
I
.Proof.
By Theorem16,
(31)
f
2
(
f
1
(
A
~
)
(
n
)
)
(
g
)
=
∧
n
∈
M
+
/
M
(
f
1
(
A
~
)
(
n
)
⟶
I
~
+
(
g
,
n
)
)
=
∧
n
∈
M
+
/
M
(
f
1
(
A
~
)
(
n
)
⟶
I
)
=
I
≥
f
2
(
B
~
)
(
g
)
,
so K
M is the congener fuzzy context of K.


## 4.2. Attribute Extended Algorithm of Lattice-Valued Concept Lattice

For general fuzzy concept lattice which is constructed on the interval[
0,1
], attribute effective increased will inevitably change the number of fuzzy concepts and the structure of fuzzy concept lattice. But, for lattice-valued concept lattice, attribute conditional increased which is researched in this paper and will not change the number of formal concepts and the structure of concept lattice. We explain this through Algorithms 1 and 2.Algorithm 1:Generation algorithm of K
M
=
(
G
,
M
+
,
L
n
,
I
~
+
).
Input: then-ary lattice-valued formal context K
=
(
G
,
M
,
L
n
,
I
~
), let M
+
=
M
Output: then-ary lattice-valued attribute extended formal context K
M
=
(
G
,
M
+
,
L
n
,
I
~
+
)
Begin
while ((
G
,
M
,
L
n
,
I
~
)
≠
Φ) do
Calculate the attribute values  I
~
(
g
,
m
j
)  of each attribute  m
j
∈
M
for each  I
~
(
g
,
m
j
1
), I
~
(
g
,
m
j
2
)
∈
K
do
if
I
~
(
g
,
m
j
1
)
∧
I
~
(
g
,
m
j
2
)
≠
Φ
then
I
~
+
(
g
,
n
)
:
=
I
~
(
g
,
m
j
1
)
∧
I
~
(
g
,
m
j
2
)
M
+
:
=
M
∪
{
n
}
else
M
+
=
M
endif;
for each  I
~
(
g
,
m
j
1
), I
~
(
g
,
m
j
2
)
,
…, I
~
(
g
,
m
j
k
)
∈
K
do
if
∧
p
=
1
k
I
~
(
g
,
m
j
p
)
≠
Φ
then
I
~
+
(
g
,
n
)
:
=
∧
p
=
1
k
I
~
(
g
,
m
j
p
)
M
+
:
=
M
∪
{
n
}
else
M
+
=
M
endif;
for
L
n
do
if
∃
I
∈
L
n
then
I
~
+
(
g
,
n
)
:
=
I
M
+
:
=
M
∪
{
n
}
else
M
+
=
M
endif;
endif
endfor;
endfor;
endAlgorithm 2:Generation algorithm of formal concepts.
Input: then-ary lattice-valued concept lattice L
(
G
,
M
,
L
n
,
I
~
)
Output: then-ary lattice-valued attribute extended concept lattice L
(
G
,
M
+
,
L
n
,
I
~
+
)
Begin
while ((
G
,
M
,
L
n
,
I
~
)
≠
Φ) do
Calculate the formal concepts (
A
~
,
B
~
) of K
=
(
G
,
M
,
L
n
,
I
~
)
for each  (
A
~
,
B
~
)
∈
L
(
G
,
M
,
L
n
,
I
~
), denote  A
~
=
(
A
~
(
g
1
)
,
A
~
(
g
2
)
,
…
,
A
~
(
g
r
)
)
∈
Α
~,
B
~
=
(
B
~
(
m
1
)
,
B
~
(
m
2
)
,
…
,
B
~
(
m
s
)
)
∈
Α
~
do
if
∃
n
∈
M
+, s.t., I
~
+
(
g
,
n
)
=
I
~
(
g
,
m
j
1
)
∧
I
~
(
g
,
m
j
2
)
,
m
j
1
,
m
j
2
∈
M
then
B
~
+
=
(
B
~
(
m
1
)
,
…
,
B
~
(
m
s
)
,
B
~
(
m
j
1
)
∧
B
~
(
m
j
2
)
)
(
A
~
,
B
~
+
)
∈
L
(
G
,
M
+
,
L
n
,
I
~
+
)
else
(
A
~
,
B
~
+
)
∉
L
(
G
,
M
+
,
L
n
,
I
~
+
)
endif;
if
∃
n
∈
M
+, s.t., I
~
+
(
g
,
n
)
=
∧
p
=
1
k
I
~
(
g
,
m
j
p
)
,
m
j
1
,
m
j
2
,
…
,
m
j
k
∈
M
then
B
~
+
=
(
B
~
(
m
1
)
,
…
,
B
~
(
m
s
)
,
∧
p
=
1
k
I
~
(
g
,
m
j
p
)
)
(
A
~
,
B
~
+
)
∈
L
(
G
,
M
+
,
L
n
,
I
~
+
)
else
(
A
~
,
B
~
+
)
∉
L
(
G
,
M
+
,
L
n
,
I
~
+
)
endif;
if
∃
n
∈
M
+, s.t., I
~
+
(
g
,
n
)
=
I
,
I
∈
L
n
then
(
A
~
,
B
~
+
)
∈
L
(
G
,
M
+
,
L
n
,
I
~
+
)
else
(
A
~
,
B
~
+
)
∉
L
(
G
,
M
+
,
L
n
,
I
~
+
)
endif;
endif
endif;
endfor;
endExample 21.
For Table3, a 4-ary lattice-valued formal context K
=
(
G
,
M
,
L
4
,
I
~
), we can compute its congener formal context as Table 4.
In this formal contextK
M, M
+
=
{
m
1
,
m
2
,
…
,
m
5
}, I
~
+
:
G
×
M
+
→
L
4, and it follows that ∀
g
∈
G, I
~
+
(
g
,
m
4
)
=
I
~
(
g
,
m
1
)
∧
I
~
(
g
,
m
2
), I
~
+
(
g
,
m
5
)
=
I. According to the theorems and algorithms of attribute increased, the formal concepts of K
M are directly derived from the relevant formal concepts of K as follows:0#:(
{
I
,
I
}
,
{
O
,
O
,
a
,
O
,
I
}
),
1#:(
{
a
,
I
}
,
{
b
,
O
,
a
,
O
,
I
}
),
2#:(
{
I
,
a
}
,
{
O
,
b
,
I
,
O
,
I
}
),
3#:(
{
I
,
b
}
,
{
a
,
O
,
a
,
O
,
I
}
),
4#:(
{
a
,
a
}
,
{
b
,
b
,
I
,
b
,
I
}
),
5#:(
{
a
,
b
}
,
{
I
,
O
,
a
,
O
,
I
}
),
6#:(
{
b
,
b
}
,
{
a
,
a
,
a
,
a
,
I
}
),
7#:(
{
I
,
O
}
,
{
a
,
b
,
I
,
O
,
I
}
),
8#:(
{
a
,
O
}
,
{
I
,
b
,
I
,
b
,
I
}
),
9#:(
{
O
,
b
}
,
{
I
,
a
,
a
,
a
,
I
}
),
10#:(
{
b
,
O
}
,
{
a
,
I
,
I
,
a
,
I
}
),
11#:(
{
O
,
O
}
,
{
I
,
I
,
I
,
I
,
I
}
).Table 4
The congener formal contextK
M
=
(
G
,
M
+
,
L
4
,
I
~
+
) of K.
m
1
m
2
m
3
m
4
m
5
g
1
a
b
I
a
I
g
2
b
O
a
O
I


## 4.3. Algorithm Analysis

The time complexity of creating concept lattices is the major factor in analyzing the complexity of the algorithm, and computing the formal concepts plays the key role in the whole process of constructing concept lattices. Suppose that the lattice-valued formal context isK
=
(
G
,
M
,
L
n
,
I
~
), where G
=
{
g
1
,
g
2
,
…
,
g
r
}, M
=
{
m
1
,
m
2
,
…
,
m
s
1
}, r, s
1, and n are the positive integers. If we compute the formal concepts under Bordat algorithm, the calculation times of the formal concepts are r
×
n
s
1
(
1
+
s
1
). When increasing s
2 attributes, the calculation times of the formal concepts are changed into r
×
n
s
1
+
s
2
(
1
+
s
1
+
s
2
).If we utilize the extended algorithm, the increaseds
2 attributes can be directly obtained by the preliminary s
1 attributes, so the calculation times of the formal concepts are r
×
n
s
1
(
1
+
s
1
)
+
s
2. Compared with Bordat algorithm, the calculation times of the formal concepts is r
×
n
s
1
(
1
+
s
1
)
+
s
2
≪
r
×
n
s
1
+
s
2
(
1
+
s
1
+
s
2
). And under the action of the extended algorithm, we can also firstly decompose the lattice-valued formal context K
=
(
G
,
M
,
L
n
,
I
~
) into several subformal contexts; that is, {
m
1
,
…
,
m
s
1
}
=
{
m
1
,
…
,
m
s
11
}
∪
{
m
s
11
+
1
,
…
,
m
s
11
+
s
12
}
∪
⋯
∪
{
m
s
1
(
p
-
1
)
+
1
,
…
,
m
s
1
(
p
-
1
)
+
s
1
p
}, where s
1
=
s
11
+
s
12
+
⋯
+
s
1
p, s
11
,
s
12
,
…
,
s
1
p are also the positive integers, and the combination algorithm is executed on them; then the calculation times of the formal concepts is ∑
j
=
1
p
r
×
n
s
1
j
(
1
+
s
1
j
). Because of s
11
,
s
12
,
…
,
s
1
p
<
s
1, we can get r
×
n
s
1
j
(
1
+
s
1
j
)
≪
r
×
n
s
1
(
1
+
s
1
), j
=
1,2
,
…
,
p; then ∑
j
=
1
p
r
×
n
s
1
j
(
1
+
s
1
j
)
+
s
2
≪
r
×
n
s
1
(
1
+
s
1
)
+
s
2; that is to say, the complexity of this algorithm is significantly decreased.Suppose thatK
=
(
G
,
M
,
L
6
,
I
~
) is the lattice-valued formal context based on 6-ary lattice implication algebra, where G
=
{
g
1
,
g
2
,
…
,
g
10
}, M
=
{
m
1
,
m
2
,
…
,
m
50
}. When increasing 10, 20, 30, 40, and 50 attributes into M, we can obtain attributes set M
1
=
{
m
1
,
m
2
,
…
,
m
60
}, M
2
=
{
m
1
,
m
2
,
…
,
m
70
}, M
3
=
{
m
1
,
m
2
,
…
,
m
80
}, M
4
=
{
m
1
,
m
2
,
…
,
m
90
}, and M
5
=
{
m
1
,
m
2
,
…
,
m
100
}. And furthermore, with the help of the extended algorithm, if we decompose K
=
(
G
,
M
,
L
6
,
I
~
) into 5 subcontexts, the calculation times will be greatly reduced. The following experiments, respectively, compare to Bordat algorithm, as Figure 4.Figure 4
Algorithms comparison of Bordat, extended, and union algorithm.In Figure4, the curve B (Bordat algorithm), E (extended algorithm), and U (union algorithm), respectively, presents the calculation times of the formal concepts. By the description of the curves in the experiments, we can draw the conclusion that Bordat algorithm cause the calculation times absolutely increased and its growth rate is far more than that of extended algorithm and union algorithm, and with the help of extended algorithm, we also can see that the calculation times are significantly decreased.


## 5. Conclusions

As the theoretical premise of the union operation of lattice-valued concept lattice, our research about attribute extended algorithm of lattice-valued concept lattice is helpful to provide useful conditions not only to distribute various databases but also to make an important progress toward practical application of concept lattice. From the definitions of attribute extended formal context and congener formal context, this paper researches the necessary and sufficient conditions of forming attribute values under the condition that the extent set keeps invariable when the new attribute is increased. The algorithms of generating lattice-valued formal context and building concept lattice based on these conditions are proposed.



---

*Source: 836137-2014-06-30.xml*