An important problem in applications of formal concept analysis is a possibly large number of clusters extracted from data. Factorization is one of the methods being used to cope with the number of clusters. We present an algorithm for computing a factor lattice of a concept lattice from the data and a user-specified similarity threshold a. The elements of the factor lattice are collections of clusters which are pairwise similar in degree at least a. The presented algorithm computes the factor lattice directly from the data, without first computing the whole concept lattice and then computing the collections of clusters. We present theoretical insight and examples for demonstration, and an open problem.
1.1
The context of the problem We assume basic familiarity with formal concept
analysis (FCA) [
Fuzzy sets and fuzzy logic We assume basic familiarity with fuzzy logic and
fuzzy sets [
The set of all fuzzy sets (or L-sets) in X is denoted LX . For fuzzy sets A, B in X we put A ⊆ B (A is a subset of B) if for each x ∈ X we have A(x) ≤ B(x). More generally, the degree S (A, B) to which A is a subset of B is defined by S (A, B) = Vx∈X A(x) → B(x). Then, A ⊆ B means S (A, B) = 1. by Formal concept analysis of data with fuzzy attributes Let X and Y be sets of objects and attributes, respectively, I be a fuzzy relation between X and Y ; I(x, y) ∈ L is the degree to which object x has attribute y. The triplet hX, Y, Ii is called a formal fuzzy context (a data table with fuzzy attributes).
For fuzzy sets A ∈ LX and B ∈ LY , define fuzzy sets A↑ ∈ LY and B↓ ∈ LX A↑(y) = ^ (A(x) → I(x, y)) (1),
B↓(x) = ^ (B(y) → I(x, y)) (2). x∈X y∈Y Then A↑(y) is the truth degree of the fact “y is shared by all objects from A” and B↓(x) is the truth degree of the fact “x has all attributes from B”. Put B (X, Y, I) = {hA, Bi | A↑ = B, B↓ = A}. Elements of B (X, Y, I) are called formal concepts of hX, Y, Ii (interesting clusters in data); B (X, Y, I) is called the concept lattice given by hX, Y, Ii.
Putting hA1, B1i ≤ hA1, B1i iff A1 ⊆ A2 (iff B1 ⊇ B2) for
hA1, B1i, hA2, B2i ∈ B (X, Y, I), ≤ models the subconcept-superconcept
hierarchy in B (X, Y, I) (being more general means to apply to a larger collection of
objects and to cover a smaller collection of attributes). The structure of B (X, Y, I)
is characterized in [
In this section, we recall the method presented in [
Given a truth degree a ∈ L (a threshold specified by a user), consider the thresholded relation a≈ on B (X, Y, I) defined by (hA1, B1i, hA2, B2i) ∈ a≈ iff (hA1, B1i ≈ hA2, B2i) ≥ a. That is, a≈ denotes “being similar in degree at least a”. a≈ is reflexive and symmetric, but need not be transitive. Call a subset B of B (X, Y, I) a a≈-block if it is a maximal subset of B (X, Y, I) such that each two concepts from B are similar in degree at least a. Denote by B (X, Y, I)/a≈ the collection of all a≈-blocks. Put hA, Bia := ^{hA0, B0i | (hA, Bi, hA0, B0i) ∈ a≈} hA, Bia := _{hA0, B0i | (hA, Bi, hA0, B0i) ∈ a≈}.
[hA, Bia, (hA, Bia)a], i.e.
B (X, Y, I)/a≈
= {[hA, Bia, (hA, Bia)a] | hA, Bi ∈ B (X, Y, I)}.
Now, define a partial order ¹ on blocks of B (X, Y, I)/a≈ by [c1, c2] ¹ [d1, d2] iff c1 ≤ d1 (iff c2 ≤ d2) where [c1, c2], [d1, d2] ∈ B (X, Y, I)/a≈, i.e. c1, c2, d1, d2 are suitable formal concepts from B (X, Y, I) and ci ≤ di denotes that in B (X, Y, I), ci is under (a subconcept of) di. Then we have Theorem 1. B (X, Y, I)/a≈ equipped with ¹ is a partially ordered set which is a complete lattice, the so-called factor lattice of B (X, Y, I) by similarity ≈ and a threshold a.
Elements of B (X, Y, I)/a≈ can be seen as similarity-based granules of formal
concepts/clusters from B (X, Y, I).B (X, Y, I)/a≈ thus provides a granular view
on (the possibly large) B (X, Y, I). For details we refer to [
We now present an illustrative example. Consider L with L = {0, 12 , 1} and
LÃukasiewicz fuzzy logical connectives. Consider the data in Tab. 1. X contains
nine objects (Mercury, . . . , Pluto), Y contains four attributes (“size small”,
. . . , “near to sun”). The corresponding concept lattice is depicted in Fig. 1.
Consider now the a = 12 . There are twelve 1/2≈-blocks and they are depicted
in Fig. 2 (blocks are higlighted by solid lines). The corresponding factor lattice
B (X, Y, I)/ 12 ≈ is depicted in Fig. 3.
#" # $
Fig. 2. 12 ≈-blocks on the concept lattice of Fig. 1
51
Computing the factor lattice B (X, Y, I)/a≈ directly from input
data
We are going to propose a way to compute B (X, Y, I)/a≈ directly from input
data. It will turn out that our algorithm has a polynomial time delay (see [
Lemma 2. If A is an extent then so is a → A; similarly, if B is an intent then so is a → B.
The next lemma shows that for a formal concept hA, Bi, hA, Bia and hA, Bia
(defined as infimum and supremum of all formal concepts similar to hA, Bi in
degree at least a) can be computed from hA, Bi directly.
aLnedm(mb)ahA3., BFioar =hAh,(Bai→∈AB),(X(a,⊗Y,BI))↓,↑wi.e have (a) hA, Bia = h(a ⊗ A)↑↓, a → Bi
Proof. See [
Proof. See [
Thus we have (hA, Bia)a = ha → (a ⊗ A)↑↓, (a ⊗(a → B))↓↑i.
Lemma 4. For hA, Bi ∈ B (X, Y, I) we have hA, Bia = ((hA, Bia)a)a.
By Lemma 4, if a a≈-block [c1, c2] is generated by hA, Bi ∈ B (X, Y, I), i.e. c1 = hA, Bia, c2 = (hA, Bia)a, then it is also generated by c2, i.e. c1 = (c2)a and c2 = ((c2)a)a. Therefore, a≈-blocks [c1, c2] are uniquely given by their suprema c2. Moreover, since each formal concept c2 = hA, Bi is uniquely given by A (namely, B = A↑), a≈-blocks are uniquely given by extents of their suprema. Therefore, denote the set of all extents of suprema of a≈-blocks by ESB(a), i.e.
ESB(a) = {A ∈ LX | hA, Bi ∈ B (X, Y, I), [hA, Bia, hA, Bi] ∈ B (X, Y, I)/a≈}.
We are going to present the main result. Let C : A → C(A) be a mapping (assigning a fuzzy set C(A) in X to a fuzzy set A in X). A fixed point of C is any fuzzy set A in X such that A = C(A). Let fix(C) denote the set of all fixed points of C, i.e. fix(C) = {A ∈ LX | A = C(A)}.
Recall (see e.g. [
Therefore, A is a fixed point of Ca if and only if A is the extent of some formal concept c2 which is the supremum of some a≈-block [c1, c2] ∈ B (X, Y, I)/a≈. Remark 1. Suppose we can compute fix(Ca) (we will se later how to do it). By Theorem 2 and the above considerations, going through fix(Ca) and computing for each A ∈ fix(Ca) the corresponding [hA, A↑ia, hA, A↑i] = [h(a ⊗ A)↑↓, a → A↑i, hA, A↑i] generates all a≈-blocks of B (X, Y, I)/a≈.
Remark 2. Strictly speaking, proceeding the just-described way, we do not generate the a≈-blocks [c1, c2] ∈ B (X, Y, I)/a≈, i.e. we do not generate a≈-blocks [c1, c2] as collections of formal concepts [c1, c2] = {hA, Bi | c1 ≤ hA, Bi ≤ c2}. For us, generating a a≈-block [c1, c2] means generating the boundary formal concepts c1, c2 ∈ B (X, Y, I). This is, however, in acordance with the purpose of the factorization of B (X, Y, I): We are looking for a granular view which is more concise than B (X, Y, I) itself.
Let us turn to the problem of generating fix(Ca). To this end, we can use the
algorithm for generating all formal concepts of a given fuzzy context described
in [
Suppose X = {1, 2, . . . , n}; L = {0 = a1 < a2 < · · · < ak = 1} (the assumption that L is linearly ordered is in fact not essential). For i, r ∈ {1, . . . , n}, j, s ∈ {1, . . . , k} we put (i, j) ≤ (r, s) iff i < r or i = r, aj ≥ as. In the following, we will freely refer to ai just by i, thus not distinguish between X × L and {1, . . . , n} × {1, . . . , k}, i.e. we denote (i, aj ) ∈ X × L also simply by (i, j). For A ∈ LX , (i, j) ∈ X × L, put
A ⊕ (i, j) := Ca((A ∩ {1, 2, . . . , i − 1}) ∪ { aj ±i}).
Here, A ∩ {1, 2, . . . , i − 1} is the intersection of a fuzzy set A and the ordinary set {1, 2, . . . , i − 1}, i.e. (A ∩ {1, 2, . . . , i − 1})(x) = A(x) for x < i and (A ∩ {1, 2, . . . , i − 1})(x) = 0 otherwise. Furthermore, for A, C ∈ LX , put A <(i,j) C iff A ∩ {1, . . . , i − 1} = C ∩ {1, . . . , i − 1}
and A(i) < C(i) = aj .
Finally, A < C iff A <(i,j) C for some (i, j). The algorithm is based on the
following theorem (see [
The algorithm for generating a≈-blocks follows.
INPUT: hX, Y, Ii (data table with fuzzy attributes), a ∈ L (similarity threshold) OUTPUT: B (X, Y, I)/a≈ (a≈-blocks [c1, c2])
A := ∅ while A 6= X do
A := A+ store([h(a ⊗ A)↑↓, a → A↑i, hA, A↑i])
As argued in [
Due to the limited scope, we demonstrate our algorithm on a data table (fuzzy
context) from Tab. 2 for which we consider various parameters a (threshold)
and some characteristics for comparison. The data table contains countries
(objects from X) and some of their economic characteristics (attributes from Y ).
The original values of the characteristics are scaled to interval [
The example demonstrates that smaller thresholds lead to larger reduction (in time and size of the concept lattice). Furthermore, we can see that the time needed for computing the factor lattice B (X, Y, I)/a≈ is smaller than time for computing the original concept lattice B (X, Y, I). con iitrzsedue 0.3 00.2
0.5 thresholds 0.5 thresholds 0.3 0.4 0.6 0.7 0.8 0.3 0.4 0.6 0.7 0.8
Fig. 4. Reduction |B (X, Y, I)/a≈|/|B (X, Y, I)| and time reduction from Tab. 3 Is there a suitable context-factorization construction by similarity such that a , the concept lattice B(hX, Y, Ii/a≈) over for the factorized context hX, Y, Ii/ ≈ hX, Y, Ii/a≈ is isomorphic to B (X, Y, I)/a≈? 1 2 3 4 5 1.0 0.8 0.2 0.3 0.5 0.8 1.0 0.2 0.6 0.9 0.2 0.3 0.2 0.3 0.4 0.4 0.7 0.1 0.2 0.3 1.0 0.9 0.3 0.2 0.4 0.8 0.7 0.6 0.4 thresholds 0.6 0.5 0.7 0.8 0.2 0.3 0.7 0.8
Fig. 6. Reduction |B (X, Y, I)/a≈|/|B (X, Y, I)| and time reduction from Tab. 5