# On the Calculation of Formal Concept Stability

Authors: Hui-lai Zhi
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

The idea of stability has been used in many applications. However, computing stability is still a challenge and the best algorithms known so far have algorithmic complexity quadratic to the size of the lattice. To improve the effectiveness, a critical term is introduced in this paper, that is, minimal generator, which serves as the minimal set that makes a concept stable when deleting some objects from the extent. Moreover, by irreducible elements, minimal generator is derived. Finally, based on inclusion-exclusion principle and minimal generator, formulas for the calculation of concept stability are proposed.


---

## Body

## 1. Introduction

When making scientific hypotheses about the cause of a natural phenomenon, some data should be gathered randomly to certain extent. A best hypothesis should be independent of this randomness, which means the hypothesis is not determined by any particular piece of data. In Kuznetsov’s research, this sort of independence was called stability [1, 2], and it was used in many occasions such as succinct representation of lattice based taxonomies [3–5], jackknife estimation towards sample functions [6], and the work of Carnap on inductive logic [7].However, computing stability of a concept was proved to be a #P-complete problem and the best algorithms known so far have algorithmic complexity quadratic to the size of the lattice [8]. In this paper we will reconsider this problem and give a new method to improve the computational efficiency.


## 2. Basic Definitions in FCA

Formal concept analysis (FCA) is a generally appropriate framework for building categories defined as object sets sharing some attributes, irrespectively of a particular domain of application [9–13]. This presents a convincing formal model of the philosophical notion of a concept characterized extensionally by the set of entities and intensionally by the set of attributes they have in common.Before proceeding, we briefly recall the FCA terminology and properties [12, 13]. Given a formal context K
=
(
G
,
M
,
I
), where G is called a set of objects, M is called a set of attributes, and the binary relation I
⊆
G
×
M specifies which objects have which attributes, the derivation functions f
(
·
) and g
(
·
) are defined for A
⊆
G and B
⊆
G as follows:
(1)
f
(
A
)
=
{
m
∈
M
∣
∀
g
∈
A
:
g
I
m
}
;
g
(
B
)
=
{
g
∈
G
∣
∀
m
∈
B
:
g
I
m
}
.f
(
A
) is the set of attributes common to all objects of A and g
(
B
) is the set of objects sharing all attributes of B, respectively.A formal concept of the extentK is a pair (
A
,
B
), where A
⊆
G, B
⊆
M, f
(
A
)
=
B, and g
(
B
)
=
A. The set A is called the extent and B is called the intent of the concept (
A
,
B
).A concept(
A
,
B
) is subconcept of (
C
,
D
) if A
⊆
C (equivalently, D
⊆
B). In this case, (
C
,
D
) is called a superconcept of (
A
,
B
). We write (
A
,
B
)
≤
(
C
,
D
) and define the relations ≥, <, and > as usual. If (
A
,
B
)
≤
(
C
,
D
) and there is no (
E
,
F
) such that (
A
,
B
)
<
(
E
,
F
)
<
(
C
,
D
), then (
A
,
B
) is a lower neighbor of (
C
,
D
) and (
C
,
D
) is an upper neighbor of (
A
,
B
); notation: (
A
,
B
)
≺
(
C
,
D
) and (
C
,
D
)
≻
(
A
,
B
).The set of all concepts ordered by relation ≤ forms a lattice, which is denoted byB
(
K
) and called the concept lattice of the context K. The relation defines the covering graph of B
(
K
).LetK
=
(
G
,
M
,
I
) be a formal context and A, A
1, A
2
⊆
G, B, B
1, B
2
⊆
M. Then the following propositions hold:(1)
A
1
⊆
A
2
⇒
f
(
A
2
)
⊆
f
(
A
1
), B
1
⊆
B
2
⇒
g
(
B
2
)
⊆
g
(
B
1
),
(2)
A
⊆
g
(
f
(
A
)
), B
⊆
f
(
g
(
B
)
),
(3)
f
(
A
)
=
f
(
g
(
f
(
A
)
)
), g
(
B
)
=
g
(
f
(
g
(
B
)
)
),
(4)
A
⊆
g
(
B
)
⇔
B
⊆
f
(
A
)
⇔
A
×
B
⊆
I.


## 3. Stability Calculation Based on Minimal Generator

Before proceeding, let us give two symbols which will be used frequently in the following discussion. For a given setA,(1)
|
A
| indicates the cardinality of A;
(2)
2
A indicates the power set of A.Definition 1 (see [1, 2, 8]).
LetK
=
(
G
,
M
,
I
) be a formal context and (
A
,
B
) a formal concept of K. The stability index σ of (
A
,
B
) is defined as follows:
(2)
σ
(
A
,
B
)
=
|
{
C
⊆
A
∣
f
(
C
)
=
B
}
|
2
|
A
|
.Proposition 2.
LetK
=
(
G
,
M
,
I
) be a formal context and (
A
,
B
) be a formal concept of K. If there is a set A
1
⊆
A with f
(
A
1
)
=
B, then f
(
A
2
)
=
B where A
1
⊆
A
2
⊆
A.Proof.
GivenA
1
⊆
A
2
⊆
A, then f
(
A
)
⊆
f
(
A
2
)
⊆
f
(
A
1
). Since (
A
,
B
) is a concept and f
(
A
1
)
=
B, then f
(
A
2
)
=
B is valid.Proposition 3.
LetA
1, A be two sets and A
1
⊆
A. Then |
{
A
2
∣
A
1
⊆
A
2
⊆
A
}
|
=
2
|
A
-
A
1
|.Proof.
NotingA
1 is the subset of A
2 with A
2
=
A
1
∪
s where s
∈
2
A
-
A
1, it follows that |
{
A
2
∣
A
1
⊆
A
2
⊆
A
}
|
=
2
|
A
-
A
1
|.Definition 4 (see [14]).
LetK
=
(
G
,
M
,
I
) be a formal context and (
A
,
B
) a formal concept of K. If there is a subset R of A which makes f
(
R
)
=
B, and for any R
1
⊂
R, f
(
R
1
)
≠
B, then we call R the minimal generator of concept (
A
,
B
).Remark 5.
It is worthwhile to note that for a given concept, it may have more than one minimal generator. A minimal generator of a formal concept is a minimal set that makes the intent of a concept stable.Theorem 6.
LetK
=
(
G
,
M
,
I
) be a formal context and (
A
,
B
) a formal concept of K. If (
A
,
B
) has only one minimal generator R, then
(3)
σ
(
A
,
B
)
=
2
-
|
R
|
.Proof.
SinceR is the minimal generator of (
A
,
B
), by Propositions 2 and 3, we obtain |
{
C
∣
R
⊆
C
⊆
A
}
|
=
2
|
A
-
R
|. Then by Definition 1, we have σ
(
A
,
B
)
=
|
{
C
∣
R
⊆
C
⊆
A
}
|
/
2
|
A
|, and a simple manipulation leads to the conclusion σ
(
A
,
B
)
=
2
-
|
R
|.Theorem 7.
LetK
=
(
G
,
M
,
I
) be a formal context and (
A
,
B
) a formal concept of K. If (
A
,
B
) has a family of minimal generators {
R
i
}
i
∈
1
,
…
,
n, then
(4)
σ
(
A
,
B
)
=
(
∑
i
=
1
n
2
|
A
-
R
i
|
-
∑
1
≤
i
<
j
≤
n
2
|
A
|
-
|
R
i
∪
R
j
|
+
⋯
+
(
-
1
)
n
2
|
A
-
R
1
∪
R
2
∪
⋯
∪
R
n
|
∑
i
=
1
n
2
|
A
-
R
i
|
-
∑
1
≤
i
<
j
≤
n
2
|
A
|
-
|
R
i
∪
R
j
|
)
(
2
|
A
|
)
-
1
.Proof.
Since{
R
i
}
i
∈
1
,
…
,
n is the family of the minimal generators of (
A
,
B
), by Propositions 2 and 3, we have |
{
C
i
∣
R
i
⊆
C
i
⊆
A
}
|
=
2
|
A
-
R
i
|.
According to inclusion-exclusion principle, we can show that|
⋃
i
=
1
n
{
C
i
}
| = ∑
i
=
1
n
2
|
A
-
R
i
| − ∑
1
≤
i
<
j
≤
n
2
|
A
|
-
|
R
i
∪
R
j
| + ⋯ + (
-
1
)
n
2
|
A
-
R
1
∪
R
2
∪
⋯
∪
R
n
|. By Definition 1, it follows that (
A
,
B
) = |
⋃
i
=
1
n
{
C
i
}
|
/
2
|
A
| = (
∑
i
=
1
n
2
|
A
-
R
i
|
-
∑
1
≤
i
<
j
≤
n
2
|
A
|
-
|
R
i
∪
R
j
|
+
⋯
+
(
-
1
)
n
2
|
A
-
R
1
∪
R
2
∪
⋯
∪
R
n
|
)
/
2
|
A
|.Corollary 8.
LetK
=
(
G
,
M
,
I
) be a formal context and (
A
,
B
) a formal concept of K. If (
A
,
B
) has only two minimal generators R
1 and R
2, then
(5)
σ
(
A
,
B
)
=
2
|
A
-
R
1
|
+
2
|
A
-
R
2
|
-
2
|
A
-
R
1
∪
R
2
|
2
|
A
|
.Followed by the above discussion, the only thing left to get the stability index of a formal concept is to find its minimal generator, which will be discussed in Section4.


## 4. Minimal Generator Computation

Definition 9 (see [15]).
LetK
=
(
G
,
M
,
I
) be a formal context. Object g is called a full attributes object if f
(
g
)
=
M. Dually, attribute m is called the largest common attribute if g
(
m
)
=
G.Definition 10 (see [16]).
LetK
=
(
G
,
M
,
I
) be a formal context. Object g is called a reducible object if there exists a series of objects {
g
i
}
i
∈
T that makes ⋂
i
∈
T
f
(
g
i
)
=
f
(
g
) where T is the index set. Dually, attribute m is called a reducible attribute if there exists a series of attributes {
m
i
}
i
∈
T that makes ⋂
i
∈
T
g
(
m
i
)
=
g
(
m
) where T is the index set.Definition 11.
LetK
=
(
G
,
M
,
I
) be a formal context. K is called a purified formal context, provided that there exists no full attributes object, no largest common attribute, no reducible object, and no reducible attribute.Definition 12.
LetK
=
(
G
,
M
,
I
) be a formal context. A concept is called an object concept if it has the form (
g
(
f
(
g
)
)
,
f
(
g
)
), g
∈
G, and g is called its object label. Dually, a concept is called an attribute concept if it has the form (
g
(
m
)
,
f
(
g
(
m
)
)
), m
∈
M, and m is called its attribute label.Theorem 13.
LetK
=
(
G
,
M
,
I
) be a purified formal context. Then any object concept of K must be an upper bound irreducible element and vice versa.Proof.
Assume that an object concept(
A
,
B
) is not an upper bound irreducible element; then (
A
,
B
) has at least two lower neighbors, and denoting them by (
A
t
,
B
t
)
t
∈
T, T is the index set. Since (
A
,
B
) is an object concept, there exists an object g such that f
(
g
)
=
B. By basic theorem on concept lattice, we have B
=
⋂
t
∈
T
B
t
=
⋂
t
∈
T
f
(
A
t
). By the fact that f
(
A
)
=
B, it follows that f
(
A
)
=
⋂
t
∈
T
f
(
A
t
), which means (
A
,
B
) is a irreducible object, and this is contradict to the definition of purified formal context. The reverse implication is proved in much the same way. Hence, this theorem holds.Theorem 14.
LetK
=
(
G
,
M
,
I
) be a purified formal context. If a concept is an object concept, then its minimal generator consists of its object label.Proof.
The theorem is immediate from Definitions4 and 12.Definition 15.
LetA
=
{
g
t
}
t
∈
T (T is the index set) be a set of objects. Function simplification simp
(
) on set A is defined as
(6)
simp
(
A
)
=
A
-
{
g
i
∣
∃
g
j
,
f
(
g
j
)
⊆
f
(
g
i
)
}
.Lemma 16.
LetA
=
{
g
t
}
t
∈
T (T is the index set) be a set of objects. Then f
(
simp
(
A
)
)
=
f
(
A
).Proof.
Without loss of generality, we assume that there exist two objectsg
i and g
j with f
(
g
i
)
⊆
f
(
g
j
). Then f
(
g
i
)
∩
f
(
g
j
)
=
f
(
g
i
), so a simple manipulation leads to the equation f
(
A
)
=
f
(
⋃
t
∈
T
g
t
)
=
⋂
t
∈
T
f
(
g
t
)
=
⋂
t
∈
T
-
i
f
(
g
t
)
=
f
(
⋃
t
∈
T
-
i
g
t
)
=
f
(
simp
(
A
)
).Lemma 17.
LetK
=
(
G
,
M
,
I
) be a purified formal context and suppose (
A
,
B
) is not an object concept. Then minimal generator of (
A
,
B
) is contained in the union of the minimal generators of its any two lower neighbors.Proof.
As(
A
,
B
) is not an object concept, there exist at least two lower neighbors, denoting them by (
A
t
,
B
t
)
t
∈
1
,
…
,
n with their minimal generators C
i, respectively. By the fact that A
=
⋃
t
=
1
n
A
t, it follows that f
(
A
)
=
⋂
t
=
1
n
f
(
C
t
). Moreover, for any i
≠
j, we can see
(7)
f
(
C
i
)
∩
f
(
C
j
)
⊇
⋂
t
=
1
n
f
(
A
t
)
=
f
(
A
)
.
Suppose⊃ of the above expression holds. Then there exists a concept (
A
′
,
B
′
) with B
′
=
f
(
C
i
)
∩
f
(
C
j
), such that (
A
,
B
)
>
(
A
′
,
B
′
)
>
(
A
t
,
B
t
), for any t
∈
1
,
…
,
n, and this is contradiction to the assumption that (
A
t
,
B
t
)
t
∈
1
,
…
,
n are the lower neighbors of (
A
,
B
). Hence, the theorem is proved.Theorem 18.
LetK
=
(
G
,
M
,
I
) be a purified formal context. If (
A
,
B
) is not an object concept, then its minimal generator is the simplification of the union of its any two lower neighbors’ minimal generators.Proof.
By Lemmas16 and 17 and in light of Definitions 4 and 15, the proof is trivial.Based on Theorems14 and 18, we get the following recursive formula on the calculation of the minimal generator R of a given concept (
A
,
B
).If(
A
,
B
) is an object concept, then R consists of its object label.Otherwise,R is the simplification of union of its any two lower neighbors’ minimal generators.


## 5. Example and Analysis

Example 1.
Consider descriptions of several objects in Table1, which is the well known formal context “biology and water” in [16].Table 1
Formal context “biology and water.”
a
b
c
d
e
f
g
h
i
1
*
*
*
2
*
*
*
*
3
*
*
*
*
*
4
*
*
*
*
*
5
*
*
*
*
6
*
*
*
*
*
7
*
*
*
*
8
*
*
*
*The corresponding concept lattice of the above formal context “biology and water” is sketched by Figure1.Figure 1
Concept lattice of the context “biology and water.”For convenience, in the representation of a concept we omit the curly braces and commas. For example, we use(
1234
,
ag
) instead of (
{
1,2
,
3,4
}
,
{
a
,
g
}
).Considering the stability index of concept(
1234
,
ag
), there are two steps.Step
1 (find minimal generator). As (
1234
,
ag
) is not an object concept, its minimal generator is determined by its lower neighbors (
234
,
agh
) and (
123
,
abg
). So we must investigate the minimal generators of (
234
,
agh
) and (
123
,
abg
), respectively. This downward recursive call continues until object concept is encountered. The integral computation process is illustrated by Figure 2, in which seven concepts are visited with concept (
1234
,
ag
) involved.Figure 2
Minimal generator calculation process. (The solid arc represents downward recursive call, and the set besides the dotted upward arc represents the return value.)Step
2 (compute stability index). According to Theorem 6, it follows that
(8)
σ
(
(
1234
,
ag
)
)
=
2
-
|
{
1,4
}
|
=
0.25
.Given a formal context (G, M, I), time complexity of concept lattice construction is O
(
|
G
|
2
|
M
|
L
) (let L be the number of concepts contained in concept lattice) [17]. When calculating the minimal generator of a given concept, we need to recursively traverse its subconcepts. The number of the visited concepts is apparently less than L, so the time complexity of getting minimal generator of a given concept is O
(
|
G
|
2
|
M
|
L
2
).Since stability index of a given concept can be derived directly by Theorems6 and 7, the time complexity of calculating stability of a given concept is still O
(
|
G
|
2
|
M
|
L
2
).Although upper estimate is the same as the already known algorithm [2], our method is more effective and there is a major reason to account for this.LetC be a concept; its integral stability index is derived by summing over stability index J
j
(
C
) with level j ranging from 2 to |
A
|
-
1. Apparently each level must be taken into consideration which means all the subconcepts of C must be visited [2]. But in our method, integral stability index is determined only by its minimal generator. When calculating the minimal generator of C, instead of visiting all the subconcepts of it, the downward recursive traverse will terminate if object concept is encountered, and all the subconcepts of object concept will not be visited any more.By using Example1, a comparison between our method and [2] is conducted with respect to the number of concepts visited, and the result is shown in Table 2.Table 2
A comparison between our method and [2] with respect to the number of concepts visited.
(1234, ag)
(34678, ac)
(12356, ab)
(5678, ad)
(234, agh)
(123, abg)
Our method
5
7
6
6
5
1
Method in [2]
7
8
7
7
5
3
(36, abc)
(678, acd)
(568, adf)
(34, acgh)
(23, abgh)
(68, acdf)
Our method
3
3
3
3
2
1
Method in [2]
3
4
4
3
2
2
(56, abdf)
(4, acghi)
(3, abcgh)
(7, acde)
(6, abcdf)
Our Method
1
1
1
1
1
method in [2]
2
1
1
1
1If we randomly select a concept from Table2, we can see that the average number of concepts visited by our method is 50/17, whereas the number is 61/17 while using the method in [2].Finally, our method shows its advantage when computing stability indexes of all concepts. The procedure is depicted by Algorithm1.Algorithm 1
Compute stability indexes of all concepts of a given formal context
Input: formal contextK
=
(
G
,
M
,
I
)
Output: stability indexes of all concepts ofL
(
K
)
Begin
(1) construct concept latticeL
(
K
);
(2) deem the concept latticeL
(
K
) as an undirected graph and traverse the concept
lattice upwards from the minimal concept ofL
(
K
) by using breadth first search;
(3) if the current visited concept lattice is an object concept, then the minimal
generator is its object label; else, its minimal generator is determined by its any two
lower neighbors’ minimal generator;
(4) compute stability indexes based on minimal generator by using the formulas in
Theorems6 and 7.
End.Apparently, in Algorithm1 every concept is visited only once, so time complexity of this algorithm is still O
(
|
G
|
2
|
M
|
L
2
). But if using the method in [2], we have to compute stability index of each concept one by one, and thus the overall time complexity is L
*
O
(
|
G
|
2
|
M
|
L
2
), that is, O
(
|
G
|
2
|
M
|
L
3
), which is greater than that of Algorithm 1.


## 6. Conclusions

The purpose of this paper is to find a more effective way to calculate stability of a given concept. The critical step of our method is to find minimal generator, and a recursive method is given with the irreducible elements as the ending condition. In light of minimal generator, stability can be computed by using inclusion-exclusion principle.A valuable further work may be how to extend the results to the setting of heterogeneous information system or to the setting of fuzzy formal context.



---

*Source: 917639-2014-07-10.xml*