# A Novel Concept Acquisition Approach Based on Formal Contexts

Authors: Ting Qian; Ling Wei
Journal: The Scientific World Journal
 (2014)

---

## Abstract

As an important tool for data analysis and knowledge processing, formal concept analysis (FCA) has been applied to many fields. In this paper, we introduce a new method to find all formal concepts based on formal contexts. The amount of intents calculation is reduced by the method. And the corresponding algorithm of our approach is proposed. The main theorems and the corresponding algorithm are examined by examples, respectively. At last, several real-life databases are analyzed to demonstrate the application of the proposed approach. Experimental results show that the proposed approach is simple and effective.


---

## Body

## 1. Introduction

Formal concept analysis (FCA), proposed by Wille in 1982 [1], is a field of applied mathematics based on the mathematization of concept and conceptual hierarchy. It thereby activates mathematical thinking for conceptual data analysis and knowledge processing. FCA starts with a formal context defined as a triple containing an object set, an attribute (property) set, and a binary relation between the object set and the attribute set. A formal concept is a pair (object subset, attribute subset) induced by the binary relation, and a concept lattice is an ordered hierarchical structure of formal concepts. A formal context in FCA corresponds to a special information system with input data being two-valued in rough set theory [2].Most of the researches on FCA concentrate on the following topics: construction and pruning algorithm of concept lattices [3, 4]; relationship between FCA and rough sets [5–10]; acquisition of rules [11, 12]; reduction of concept lattices [6, 10, 13]. FCA is also proved to be useful in many fields, such as the organization of web search results on a hierarchical structure of concepts based on common topics [14], information retrieval [15, 16], hierarchical analysis of software code [17–19], visualization in software engineering [19, 20], detecting suspects in human traficking [21], analysis of questionnaire data [22], and mining gene expression data [23]. Further references to applications of FCA can be found in [14, 24].Formal concepts are very important notions of FCA. And intents and extents are also very important elements of formal concepts. The set of intents (extents) is isomorphic to the corresponding concept lattice under the order relationship “⊇” (“⊆”). So, if the set of intents is determined, the corresponding concept lattice is identified. Thus, obtaining all intents or extents is very important. Generally, the basic way to obtain all intents or extents is via their definitions. If there are n objects, then we should calculate 2
n times to obtain all intents. Obviously, the computational costing is very huge. To solve this problem, we give a new method to obtain all intents. And correspondingly, the formal concepts are determined.This paper is organized as follows. In Section2, we briefly review some basic notions related to FCA. In Section 3, a novel concept acquisition approach is introduced and some related conclusions are given. In Section 4, the corresponding algorithm is proposed and experimental results are shown to illustrate the validity of our method. Finally, conclusions are drawn in Section 5.


## 2. Preliminaries

In this section, we recall some basic notions and properties in FCA.Definition 1 (see [24]).
A formal context(
G
,
M
,
I
) consists of two sets G and M and a relation I between G and M. The elements of G are called the objects and the elements of M are called the attributes of the context. In order to express that an object g is in a relation I with an attribute m, we write g
I
m or (
g
,
m
)
∈
I and read it as “the object g has the attributem.”
With respect to a formal context(
G
,
M
,
I
), Ganter and Wille [24] defined a pair of dual operators for any A
⊆
G and B
⊆
M by
(1)
A
*
=
{
m
∈
M
∣
g
I
m
∀
g
∈
A
}
,
B
′
=
{
g
∈
G
∣
g
I
m
∀
m
∈
B
}
.
A formal context is called canonical if∀
g
∈
G, g
*
≠
∅, g
*
≠
M, and ∀
m
∈
M, m
′
≠
∅, m
′
≠
G. We assume that all the formal contexts we study in the sequel are finite and canonical.
Let(
G
,
M
,
I
) be a formal context. ∀
A
1
,
A
2
,
A
⊆
G, ∀
B
1
,
B
2
,
B
⊆
M; the following properties hold.(1)
A
1
⊆
A
2
⇒
A
2
*
⊆
A
1
*,   B
1
⊆
B
2
⇒
B
2
′
⊆
B
1
′.
(2)
A
⊆
A
*
′,  B
⊆
B
′
*.
(3)
A
*
=
A
*
′
*, B
′
=
B
′
*
′.
(4)
A
⊆
B
′
⇔
B
⊆
A
*.
(5)
(
A
1
∪
A
2
)
*
=
A
1
*
∩
A
2
*
,
(
B
1
∪
B
2
)
′
=
B
1
′
∩
B
2
′.
(6)
(
A
1
∩
A
2
)
*
⊇
A
1
*
∪
A
2
*
,
(
B
1
∩
B
2
)
′
⊇
B
1
′
∪
B
2
′.
IfA
*
=
B and B
′
=
A, then (
A
,
B
) is called a formal concept, where A is called the extent of the formal concept and B is called the intent of the formal concept. For any g
∈
G, a pair (
g
*
′
,
g
*
) is a formal concept and is called an object concept. Similarly, for any m
∈
M, a pair (
m
′
,
m
′
*
) is a formal concept and is called an attribute concept. The family of all formal concepts of (
G
,
M
,
I
) forms a complete lattice that is called the concept lattice and is denoted by L
(
G
,
M
,
I
). For any (
A
1
,
B
1
)
,
(
A
2
,
B
2
)
∈
L
(
G
,
M
,
I
), the partial order is defined by
(2)
(
A
1
,
B
1
)
≤
(
A
2
,
B
2
)
⟺
A
1
⊆
A
2
(
⟺
B
1
⊇
B
2
)
.
And the infimum ∧ and supremum ∨ of (
A
1
,
B
1
) and (
A
2
,
B
2
) are defined by
(3)
(
A
1
,
B
1
)
∧
(
A
2
,
B
2
)
=
(
A
1
∩
A
2
,
(
B
1
∪
B
2
)
′
*
)
,
(
A
1
,
B
1
)
∨
(
A
2
,
B
2
)
=
(
(
A
1
∪
A
2
)
*
′
,
B
1
∩
B
2
)
,
respectively.Definition 2 (see [10]).
Let(
G
,
M
,
I
) be a formal context. |
G
|
<
∞ and |
M
|
<
∞. Denote L
M
(
G
,
M
,
I
)
=
{
Y
∣
Y
⊆
M and Y is an intent of (
G
,
M
,
I
)
}.Example 3 (see [10]).
Table1 is a formal context (
G
,
M
,
I
). G
=
{
1,2
,
3,4
,
5,6
} is an object set and M
=
{
a
,
b
,
c
,
d
,
e
} is an attribute set. The corresponding concept lattice L
(
G
,
M
,
I
) is shown in Figure 1, in which every set is denoted directly by listing its elements except G, M, and ∅.Table 1
A formal context(
G
,
M
,
I
).
G
a
b
c
d
e
1
✗
✗
✗
✗
2
✗
✗
3
✗
✗
4
✗
✗
5
✗
6
✗
✗
✗Figure 1
L
(
G
,
M
,
I
) of Example 3.


## 3. A Novel Concept Acquisition Approach

The basic way to obtain all intents or extents is via their definitions. If there aren objects, then we should calculate 2
n times to get all intents. Obviously, the amount of computation is very large. So our paper presents a new approach to solve the problem. In this section, we give this new method and some theorems to explain its rationality and validity.Before giving the method, we firstly propose a related definition.Definition 4.
Let(
G
,
M
,
I
) be a formal context. |
G
|
<
∞, |
M
|
<
∞. Denote α
n
=
{
X
∣
X
⊆
G and |
X
|
=
n
}, β
n
=
{
Y
∣
Y
⊆
M
,
Y
=
X
* and X
∈
α
n
}, n
=
1,2
,
…
,
|
G
|, where |
·
| presents the cardinal of a set.Since the method in this paper is aimed at obtaining all intents, we use subsetsα
n of G to determine subsets β
n of M. On the contrary, if we want to obtain all extents, the subsets of M can be used to determine subsets of G. This point has been illustrated in the sequel.Theorem 5.
β
1 is an intent of an object concept.Proof.
The proof is immediately obtained from Definitions1 and 4.Theorem 6.
If there existsn (n
=
1,2
,
…
,
|
G
|) such that β
n
+
1
⊆
β
n, then β
n
+
2
⊆
β
n
+
1.Proof.
SupposeY
∈
β
n
+
2. By Definition 4, there exists X
n
+
2
∈
α
n
+
2 such that Y
=
X
n
+
2
*.
SinceX
n
+
2
≠
∅, there exists a
∈
X
n
+
2 such that Y
=
X
n
+
2
*
=
(
X
n
+
2
∖
{
a
}
∪
{
a
}
)
*
=
(
X
n
+
2
∖
{
a
}
)
*
∩
{
a
}
*. Noting that |
X
n
+
2
∖
{
a
}
|
=
n
+
1, we have X
n
+
2
∖
{
a
}
∈
α
n
+
1. Moreover, from β
n
+
1
⊆
β
n, we know that there exists X
n
∈
α
n satisfying (
X
n
+
2
∖
{
a
}
)
*
=
X
n
*; that is, Y
=
X
n
*
∩
{
a
}
*
=
(
X
n
∪
{
a
}
)
*.
Now, we discuss two cases to proveY
∈
β
n
+
1.
The one case is thata
∉
X
n. In this case, |
X
n
∪
{
a
}
|
=
n
+
1. Thus, Y
=
X
n
*
∩
{
a
}
*
=
(
X
n
∪
{
a
}
)
*
∈
β
n
+
1.
The other one is thata
∈
X
n. In this case, Y
=
X
n
*
∩
{
a
}
*
=
X
n
*. Because X
n
+
2
∖
X
n
≠
∅, there exists b
∈
X
n
+
2
∖
X
n such that X
n
⊆
X
n
∪
{
b
}
⊆
X
n
∪
X
n
+
2. Therefore, we have X
n
*
⊇
(
X
n
∪
{
b
}
)
*
⊇
(
X
n
∪
X
n
+
2
)
*; that is, X
n
*
⊇
(
X
n
∪
{
b
}
)
*
⊇
X
n
*
∩
X
n
+
2
*. That means, Y
⊇
(
X
n
∪
{
b
}
)
*
⊇
Y. Therefore, we have Y
=
(
X
n
∪
{
b
}
)
*. Thereby, we can obtain Y
∈
β
n
+
1.
To sum up the above two cases,β
n
+
2
⊆
β
n
+
1 holds.Theorem6 guarantees the convergence of Algorithm 2 involved in the sequel.Corollary 7.
If there existsn (n
=
1,2
,
…
,
|
G
|) such that β
n
+
1
⊆
β
n, then for any m, m
≥
n, we have β
m
+
1
⊆
β
m
⊆
β
n.Proof.
According to the conditionβ
n
+
1
⊆
β
n, we have β
n
+
2
⊆
β
n
+
1 by Theorem 6. Using Theorem 6 repeatedly, we can easily obtain the following results: β
m
+
1
⊆
β
m
⊆
β
m
-
1
⊆
β
m
-
2
⊆
⋯
⊆
β
n
+
1
⊆
β
n.Theorem 8.
SupposeY
∈
β
k, 1
≤
k
≤
|
G
|, 1
<
m
<
k; if Y
∉
β
m, then we have Y
∉
β
m
-
1.Proof.
We will adopt the proof by contradiction.
SupposeY
∈
β
m
-
1; there is X
m
-
1
∈
α
m
-
1 satisfying Y
=
X
m
-
1
*; according to the condition and Definition 4, there is X
k
∈
α
k satisfying Y
=
X
k
*.
BecauseX
k
∖
X
m
-
1
≠
∅, there exists a
∈
X
k
∖
X
m
-
1 such that |
X
m
-
1
∪
{
a
}
|
=
m; that is, X
m
-
1
∪
{
a
}
∈
α
m. Obviously, X
m
-
1
⊆
X
m
-
1
∪
{
a
}
⊆
X
m
-
1
∪
X
k, and thus, X
m
-
1
*
⊇
(
X
m
-
1
∪
{
a
}
)
*
⊇
(
X
m
-
1
∪
X
n
)
*. That is, X
m
-
1
*
⊇
(
X
m
-
1
∪
{
a
}
)
*
⊇
X
m
-
1
*
∩
X
k
*. That means Y
⊇
(
X
m
-
1
∪
{
a
}
)
*
⊇
Y. Therefore, we have Y
=
(
X
m
-
1
∪
{
a
}
)
*. From Definition 4, we know that Y
∈
β
m. It is a contradiction with Y
∉
β
m.
Therefore,Y
∉
β
m
-
1 holds.Corollary 9.
SupposeY
∈
β
k, 1
≤
k
≤
|
G
|, and Y
∉
β
k
-
1,β
k
⊆
β
k
-
1; then for any m, 1
≤
m
<
k, Y
∉
β
m.Proof.
BecauseY
∈
β
k, and Y
∉
β
k
-
1, we have Y
∉
β
k
-
2 by Theorem 8. Using Theorem 8 repeatedly, we have Y
∉
β
m.Theorem 10.
Suppose(
G
,
M
,
I
) is canonical; then β
n
+
1
⊆
β
n if and only if  ∪
i
=
1
n
β
i
∪
{
M
}
=
L
M
(
G
,
M
,
I
).Proof.
Necessity. Suppose β
n
+
1
⊆
β
n.
For anyY
∈
∪
i
=
1
n
β
i
∪
{
M
}, if Y
=
{
M
}, then it is evident that Y
∈
L
M
(
G
,
M
,
I
). If Y
≠
{
M
}, then there exists n
0 such that Y
∈
β
n
0. By Definition 4, there exists X
n
0
∈
α
n
0 such that Y
=
X
n
0
*. Obviously, Y
∈
L
M
(
G
,
M
,
I
). Since Y is arbitrary and M
∈
L
M
(
G
,
M
,
I
), we have ∪
i
=
1
n
β
i
∪
{
M
}
⊆
L
M
(
G
,
M
,
I
).
For anyY
∈
L
M
(
G
,
M
,
I
), by Definition 2 and properties of the operator *, we have Y
=
(
Y
*
)
*
,
Y
*
⊆
G. Without loss of the generality, we can suppose |
Y
*
|
=
m. If m
≤
n, then Y
∈
β
m
⊆
∪
i
=
1
n
β
i by Definition 4. If  m
>
n, from above Corollary 7, we have Y
∈
β
m
⊆
β
n
⊆
∪
i
=
1
n
β
i. Since M
∈
∪
i
=
1
n
β
i
∪
{
M
} and Y is arbitrary, we obtain ∪
i
=
1
n
β
i
∪
{
M
}
⊇
L
M
(
G
,
M
,
I
).
Therefore,∪
i
=
1
n
β
i
∪
{
M
}
=
L
M
(
G
,
M
,
I
).
Sufficiency. We assume β
n
+
1
⊈
β
n and prove ∪
i
=
1
n
β
i
∪
{
M
}
≠
L
M
(
G
,
M
,
I
).
Ifβ
n
+
1
⊈
β
n, then there is Y
∈
β
n
+
1, but Y
∉
β
n. From Corollary 9, for any m, 1
≤
m
<
n, we have Y
∉
β
m. So, Y
∉
∪
i
=
1
n
β
i. (
G
,
M
,
I
) is canonical and Y
∈
β
n
+
1, so Y
≠
M. Thus, Y
∉
∪
i
=
1
n
β
i
∪
{
M
}.
On the other hand, sinceY
∈
β
n
+
1, by Definition 4, there exists X
n
+
1
∈
α
n
+
1, such that Y
=
X
n
+
1
*. By the definition of L
M
(
G
,
M
,
I
), Y
∈
L
M
(
G
,
M
,
I
).
That means there exists one setY such that Y
∉
∪
i
=
1
n
β
i
∪
{
M
}, but Y
∈
L
M
(
G
,
M
,
I
). Therefor, ∪
i
n
β
i
∪
{
M
}
≠
L
M
(
G
,
M
,
I
).Theorem10 gives a sufficient and necessary condition and computation method to find L
M
(
G
,
M
,
I
). Now, the process to calculate all intents is summarized as follows.Step  1. Calculate α
1 and β
1 by Definition 4.Step  2. Calculate α
2 and β
2 by Definition 4. If β
2
⊆
β
1, then the set of intents is β
1
∪
{
M
}. Otherwise, we proceed Step  3.Step  3. Calculate α
3 and β
3 by Definition 4. If β
3
⊆
β
2, then the set of intents is β
1
∪
β
2
∪
{
M
}. Otherwise, calculate β
i (1
≤
i
≤
|
G
|) continuously. The computation needs to stop at β
n
+
1 which exactly meets β
n
+
1
⊆
β
n. Meanwhile, the set of intents is ∪
i
=
1
n
β
i
∪
{
M
}.The merit of our method is that we do not need to calculate allβ
i, 1
≤
i
≤
|
G
| and the computation needs only to stop at β
n
+
1 which exactly meets β
n
+
1
⊆
β
n. Now all the intents have been found and there is no extra computing.In the following, we use an example in the literature [24] to examine the main results about the new method to find all intents of formal concepts.The formal context in Table2 is a minor revision of the famous example, a film “Living Beings and Water” [24]. Since we require all the formal contexts in this paper are canonical, we delete the attribute a (water) from the original formal context. The objects are living beings mentioned in the film and are denoted by G
=
{
1,2
,
3,4
,
5,6
,
7,8
}, where 1 is leech, 2 is bream, 3 is frog, 4 is dog, 5 is spike-weed, 6 is reed, 7 is bean, and 8 is maize. And the attributes in M
=
{
b
,
c
,
d
,
e
,
f
,
g
,
h
,
i
} are the properties which the film emphasizes: b: lives in water, c: lives on land, d: needs chlorophyll to produce food, e: two seed leaves, f: one seed leaf, g: can move around, h: has limbs, and i: suckles its offspring.Table 2
Living beings and water(
G
,
M
,
I
).
G
b
c
d
e
f
g
h
i
1
✗
✗
2
✗
✗
✗
3
✗
✗
✗
✗
4
✗
✗
✗
✗
5
✗
✗
✗
6
✗
✗
✗
✗
7
✗
✗
✗
8
✗
✗
✗The corresponding concept latticeL
(
G
,
M
,
I
) of this formal context is shown in Figure 2.Figure 2
L
(
G
,
M
,
I
).We calculateα
i and β
i (i
=
1,2
,
3
,
…
,
8) firstly:
(4)
α
1
=
{
{
1
}
,
{
2
}
,
{
3
}
,
{
4
}
,
{
5
}
,
{
6
}
,
{
7
}
,
{
8
}
}
,
β
1
=
{
{
b
,
g
}
,
{
b
,
g
,
h
}
,
{
b
,
g
,
c
,
h
}
,
{
c
,
g
,
h
,
i
}
,
{
b
,
d
,
f
}
,
{
b
,
c
,
d
,
f
}
,
{
c
,
d
,
e
}
,
{
c
,
d
,
f
}
}
,
α
2
=
{
{
1,2
}
,
{
1,3
}
,
{
1,4
}
,
{
1,5
}
,
{
1,6
}
,
{
1,7
}
,
{
1,8
}
,
{
2,3
}
,
{
2,4
}
,
{
2,5
}
,
{
2,6
}
,
{
2,7
}
,
{
2,8
}
,
{
3,4
}
,
{
3,5
}
,
{
3,6
}
,
{
3,7
}
,
{
3,8
}
,
{
4,5
}
,
{
4,6
}
,
{
4,7
}
,
{
4,8
}
,
{
5,6
}
,
{
5,7
}
,
{
5,8
}
,
{
6,7
}
,
{
6,8
}
,
{
7,8
}
}
,
β
2
=
{
{
b
,
g
}
,
{
g
}
,
{
b
}
,
∅
,
{
b
,
g
,
h
}
,
{
g
,
h
}
,
{
c
,
g
,
h
}
,
{
b
,
c
}
,
{
c
}
,
{
b
,
d
,
f
}
,
{
d
}
,
{
d
,
f
}
,
{
c
,
d
}
,
{
c
,
d
,
f
}
}
,
α
3
=
{
{
1,2
,
3
}
,
{
1,2
,
4
}
,
{
1,2
,
5
}
,
{
1,2
,
6
}
,
{
1,2
,
7
}
,
{
1,2
,
8
}
,
{
2
,
3
,
4
}
,
{
2,3
,
5
}
,
{
2,3
,
6
}
,
{
2,3
,
7
}
,
{
2,3
,
8
}
,
{
3,4
,
5
}
,
{
3,4
,
6
}
,
{
3,4
,
7
}
,
{
3,4
,
8
}
,
{
4,5
,
6
}
,
{
4,5
,
7
}
,
{
4,5
,
8
}
,
{
5,6
,
7
}
,
{
5,6
,
8
}
,
{
6,7
,
8
}
,
{
1,3
,
4
}
,
{
1,3
,
5
}
,
{
1,3
,
6
}
,
{
1,3
,
7
}
,
{
1,3
,
8
}
,
{
2,4
,
5
}
,
{
2,4
,
6
}
,
{
2,4
,
7
}
,
{
2,4
,
8
}
,
{
3,5
,
6
}
,
{
3,5
,
7
}
,
{
3,5
,
8
}
,
{
4,6
,
7
}
,
{
4,6
,
8
}
,
{
5,7
,
8
}
,
{
1,4
,
5
}
,
{
1,4
,
6
}
,
{
1,4
,
7
}
,
{
1,4
,
8
}
,
{
2,5
,
6
}
,
{
2,5
,
7
}
,
{
2,5
,
8
}
,
{
3,6
,
7
}
,
{
3,6
,
8
}
,
{
4,7
,
8
}
,
{
1,5
,
6
}
,
{
1,5
,
7
}
,
{
1,5
,
8
}
,
{
2,6
,
7
}
,
{
2,6
,
8
}
,
{
3,7
,
8
}
,
{
1,6
,
7
}
,
{
1,6
,
8
}
,
{
2,7
,
8
}
,
{
1,7
,
8
}
}
,
β
3
=
{
{
b
,
g
}
,
{
g
}
,
{
b
}
,
∅
,
{
b
,
g
,
h
}
,
{
g
,
h
}
,
{
c
,
g
,
h
}
,
{
b
,
c
}
,
{
c
}
,
{
b
,
d
,
f
}
,
{
d
}
,
{
d
,
f
}
,
{
c
,
d
}
,
{
c
,
d
,
f
}
}
.Similarly, we can calculateβ
4, β
5, …, β
8 and find β
2
⊇
β
3
⊇
β
4
⊇
β
5
⊇
⋯
⊇
β
8. And we can also know β
2
⊈
β
1. In fact, we only need to calculate β
1, β
2, β
3. Once we have β
3
⊆
β
2, but β
2
⊈
β
1, the computation can be stopped.According to Theorem10, the set of all the intents is β
1
∪
β
2
∪
{
M
}; that is, L
M
(
G
,
M
,
I
)
=
{
{
b
,
g
}, {
g
}, {
b
}, ∅, {
b
,
g
,
h
}, {
g
,
h
}, {
c
,
g
,
h
}, {
b
,
c
}, {
c
}, {
b
,
d
,
f
}, {
d
}, {
d
,
f
}, {
c
,
d
}, {
c
,
d
,
f
}, {
b
,
g
,
c
,
h
}, {
c
,
g
,
h
,
i
}, {
b
,
c
,
d
,
f
}, {
c
,
d
,
e
}, M
}. These results are easily examined from Figure 2.


## 4. Algorithms and Experiments

### 4.1. Algorithms

Algorithm1 is given based on Definition 1 completely.Algorithm 1
(1) input context,
(2) step = 1,
(3) get first step set(
),
(4) intent set = former step set,
(5) step+
+,
(6) later step set=
{
β
:
β
= make arbitrary two ranks meet in the context},
(7) while(step ≤ max rank of context)  {former step set = later step set;
intent set = union of later step set and intent set; step++;},
(8) output the set of intents.Algorithm 2
(1) input context,
(2) step = 1,
(3) get first step set(
),
(4) intent set = former step set,
(5) step+
+,
(6) later step set=
{
β
:
β
= make arbitrary two ranks meet in the context},
(7) while (step ≤ max rank of context)  {if(later step set is not the subset of
former step set)  {former step set = later step set; intent set = union of
later step set and intent set; step+
+;} else {return}
},
(8) output the set of intents.Algorithm2 is based on our approach presented by Theorem 10. Comparing with Algorithm 1, we add a condition to terminate the program.The time complexity of Algorithm2 is analyzed as follows.DenoteN
=
min
⁡
{
|
G
|
,
|
M
|
}; by Definition 4, we know the time complexity of Step I in Algorithms 1 or 2 is O
(
C
N
i
). So we can get two matters as follows.(1)
The time complexity of algorithm isO
(
2
N
).
(2)
Suppose that Algorithm2 will be terminated in the kth step; then the time complexity of Algorithm 2 is O
(
∑
i
=
1
i
=
k
(
C
N
i
)
) by Theorem 10. We can easily get O
(
∑
i
=
1
i
=
k
(
C
N
i
)
)
≤
O
(
2
N
).We present an example demonstrating performance of Algorithm2. The database “patient and Ill symptoms” showed in Table 3 comes from UCI Machine Learning Repository [25]. Suppose there are 12 patients which are denoted by 1
,
…
,
12 and 8 symptoms of patients which are denoted by a
,
…
,
h, where a is headache, b is fever, c stands for painful limbs, d represents swollen glands in neck, e is cold, f is stiff neck, g is rash, and h is vomiting. Input the formal context and run the program; we obtain the set of all intents when n
=
2:{
∅
,
{
b
}
,
{
a
,
b
}
,
{
b
,
e
}
,
{
g
}
,
{
b
,
e
,
g
}
,
{
a
,
b
,
f
,
h
}
,
{
a
,
b
,
c
,
e
}
,
{
a
,
b
,
c
,
d
,
e
,
f
,
g
,
h
}
}
.Table 3
Patients and ill symptoms(
G
,
M
,
I
).
G
a
b
c
d
e
f
g
h
1
✗
✗
✗
✗
2
✗
✗
✗
✗
3
✗
✗
✗
4
✗
✗
✗
✗
5
✗
✗
✗
✗
6
✗
✗
✗
7
✗
✗
✗
8
✗
9
✗
✗
✗
✗
10
✗
11
✗
✗
✗
✗
12
✗
✗
✗
✗


### 4.2. Experimental Results

In this section, we conduct some experiments to compare Algorithm2 with Algorithm 1. In the experiments, four real life databases we selected are as follows:(1)
Living beings and water [24] introduced in Section 4.1.
(2)
Patients and ill symptoms [25] introduced in Section 4.1.
(3)
Bacterial Taxonomy [26]. Data are presented for 6 species most of whom having data for more than one strain and 16 phenotypic characters (0 and 1). The species areEscherichia coli (ecoli),Salmonella typhi (styphi),Klebsiella pneumoniae (kpneu),Proteus vulgaris (pvul),Proteus morganii (pmor), andSerratia marcesens (smar). The phenotypic characters are H2S, MAN, LYS, IND, ORN, CIT, URE, ONP, VPT, INO, LIP, PHE, MAL, ADO, ARA, and RHA.
(4)
Membership of Developing Countries in Supranational Group [24]. In this data, 130 developing countries are objects. Six properties (group of 77, nonaligned, least developed countries, most seriously affected countries, Organization of Petrol Exporting Countries, and African Caribbean and Pacfic Countries) are attributes.The results are shown in Table4 and Figure 3, where Time 1 and Time 2 are the running time of Algorithms 1 and 2, respectively. |
I
| presents the number of intents and the efficiency is equivalent to (Time 1 − Time 2)/Time 1. It can be seen that Algorithm 2 is much more efficient than Algorithm 1 along with the increase of |
I
|.Table 4
A contrast between algorithms.
Data
|
G
|
|
M
|
|
I
|
Time 1
Time 2
Efficiency
1
8
8
19
733
686
6.4%
2
12
8
9
733
718
2.1%
3
17
16
53
921
733
20.4%
4
130
6
23
1504
1217
19.1%Figure 3
Database analysis.


## 4.1. Algorithms

Algorithm1 is given based on Definition 1 completely.Algorithm 1
(1) input context,
(2) step = 1,
(3) get first step set(
),
(4) intent set = former step set,
(5) step+
+,
(6) later step set=
{
β
:
β
= make arbitrary two ranks meet in the context},
(7) while(step ≤ max rank of context)  {former step set = later step set;
intent set = union of later step set and intent set; step++;},
(8) output the set of intents.Algorithm 2
(1) input context,
(2) step = 1,
(3) get first step set(
),
(4) intent set = former step set,
(5) step+
+,
(6) later step set=
{
β
:
β
= make arbitrary two ranks meet in the context},
(7) while (step ≤ max rank of context)  {if(later step set is not the subset of
former step set)  {former step set = later step set; intent set = union of
later step set and intent set; step+
+;} else {return}
},
(8) output the set of intents.Algorithm2 is based on our approach presented by Theorem 10. Comparing with Algorithm 1, we add a condition to terminate the program.The time complexity of Algorithm2 is analyzed as follows.DenoteN
=
min
⁡
{
|
G
|
,
|
M
|
}; by Definition 4, we know the time complexity of Step I in Algorithms 1 or 2 is O
(
C
N
i
). So we can get two matters as follows.(1)
The time complexity of algorithm isO
(
2
N
).
(2)
Suppose that Algorithm2 will be terminated in the kth step; then the time complexity of Algorithm 2 is O
(
∑
i
=
1
i
=
k
(
C
N
i
)
) by Theorem 10. We can easily get O
(
∑
i
=
1
i
=
k
(
C
N
i
)
)
≤
O
(
2
N
).We present an example demonstrating performance of Algorithm2. The database “patient and Ill symptoms” showed in Table 3 comes from UCI Machine Learning Repository [25]. Suppose there are 12 patients which are denoted by 1
,
…
,
12 and 8 symptoms of patients which are denoted by a
,
…
,
h, where a is headache, b is fever, c stands for painful limbs, d represents swollen glands in neck, e is cold, f is stiff neck, g is rash, and h is vomiting. Input the formal context and run the program; we obtain the set of all intents when n
=
2:{
∅
,
{
b
}
,
{
a
,
b
}
,
{
b
,
e
}
,
{
g
}
,
{
b
,
e
,
g
}
,
{
a
,
b
,
f
,
h
}
,
{
a
,
b
,
c
,
e
}
,
{
a
,
b
,
c
,
d
,
e
,
f
,
g
,
h
}
}
.Table 3
Patients and ill symptoms(
G
,
M
,
I
).
G
a
b
c
d
e
f
g
h
1
✗
✗
✗
✗
2
✗
✗
✗
✗
3
✗
✗
✗
4
✗
✗
✗
✗
5
✗
✗
✗
✗
6
✗
✗
✗
7
✗
✗
✗
8
✗
9
✗
✗
✗
✗
10
✗
11
✗
✗
✗
✗
12
✗
✗
✗
✗


## 4.2. Experimental Results

In this section, we conduct some experiments to compare Algorithm2 with Algorithm 1. In the experiments, four real life databases we selected are as follows:(1)
Living beings and water [24] introduced in Section 4.1.
(2)
Patients and ill symptoms [25] introduced in Section 4.1.
(3)
Bacterial Taxonomy [26]. Data are presented for 6 species most of whom having data for more than one strain and 16 phenotypic characters (0 and 1). The species areEscherichia coli (ecoli),Salmonella typhi (styphi),Klebsiella pneumoniae (kpneu),Proteus vulgaris (pvul),Proteus morganii (pmor), andSerratia marcesens (smar). The phenotypic characters are H2S, MAN, LYS, IND, ORN, CIT, URE, ONP, VPT, INO, LIP, PHE, MAL, ADO, ARA, and RHA.
(4)
Membership of Developing Countries in Supranational Group [24]. In this data, 130 developing countries are objects. Six properties (group of 77, nonaligned, least developed countries, most seriously affected countries, Organization of Petrol Exporting Countries, and African Caribbean and Pacfic Countries) are attributes.The results are shown in Table4 and Figure 3, where Time 1 and Time 2 are the running time of Algorithms 1 and 2, respectively. |
I
| presents the number of intents and the efficiency is equivalent to (Time 1 − Time 2)/Time 1. It can be seen that Algorithm 2 is much more efficient than Algorithm 1 along with the increase of |
I
|.Table 4
A contrast between algorithms.
Data
|
G
|
|
M
|
|
I
|
Time 1
Time 2
Efficiency
1
8
8
19
733
686
6.4%
2
12
8
9
733
718
2.1%
3
17
16
53
921
733
20.4%
4
130
6
23
1504
1217
19.1%Figure 3
Database analysis.


## 5. Conclusion

To find new methods to solve the difficult problems of the concept lattice construction is a hot problem. Constructing concept lattices is a novel research branch for data processing and data analysis. Different methods play essential roles in different problems. This paper first defines some basic notions. Based on the basic notion of intents, we obtain a new judgment method of finding all intents of formal concepts. Moreover, an example is given to explain the feasibility of this method. At last, we give the corresponding algorithm of this method and do the experiments to illustrate the effectiveness of this method.For Algorithm2, we have the following discussion which can be applied to real application. We can compare |
G
| with |
M
| of a formal context. If |
G
|
≤
|
M
|, then we use subsets of G to determine subsets of M and output the set of intents. Otherwise, according to the duality principle, the subsets of M can be used to determine subsets of G and output the set of extents. We will improve the corresponding algorithm of this method in the future.



---

*Source: 136324-2014-07-23.xml*