FastFactorization Fast factorization of of Concept concept lattices Latticesby by ? similarity: solution and an open problem Similarity: Solution and an Open Problem Radim Bělohlávek, Jiřı́ Dvořák, and Jan Outrata Radim Bělohlávek, Jiřı́ Dvořák, and Jan Outrata Department of Computer Science, Palacky University, Olomouc Department of Computer Tomkova Science, 40, CZ-779 Palacky 00 Olomouc, University, Czech RepublicOlomouc {radim.belohlavek, jiri.dvorak, Tomkova 40, CZ-779 00 Olomouc,jan.outrata}@upol.cz Czech Republic {radim.belohlavek, jiri.dvorak, jan.outrata}@upol.cz Abstract. An important problem in applications of formal concept analysis is a possibly large number of clusters extracted from data. Fac- torization 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. Keywords: formal concept analysis, fuzzy attributes, factorization, similarity 1 Problem Setting and Preliminaries 1.1 Problem Setting The problem The present paper presents a solution to a problem formulated at CLA 2002 Workshop (Horı́ Bečva, Czech Republic, June 2002) concerning fac- torization of concept lattice over data with fuzzy attributes. Formulated briefly, the problem is as follows: Find a fast way to compute the factor concept lattice over data with fuzzy attributes as described in [2] (factorization is by similarity which is given by a user-specified threshold a). In addition to the solution, we formulate another open problem related to the present one. The present paper is a brief version of a more detailed paper [6] which is under preparation (due to the limited scope, we omit proofs and shorten demonstrating examples and comments in the present paper). ? R. Bělohlávek gratefully acknowledges support by grant No. 201/02/P076 of the GAČR. c V. Snášel, R. Bělohlávek (Eds.): CLA 2004, pp. 47–57, ISBN 80-248-0597-9. VŠB – Technical University of Ostrava, Dept. of Computer Science, 2004. 48 Radim Bělohlávek, Jiřı́ Dvořák, Jan Outrata The context of the problem We assume basic familiarity with formal concept analysis (FCA) [8], and with fuzzy logic and fuzzy sets [3, 10]. It is well-known that an important problem of FCA is the possible large number of formal con- cepts (clusters) in data. One of the ways to cope with this problem is factorization of concept lattices [8]. In [2], a method to factorize concept lattices over data with fuzzy attributes was proposed. Basically, a user specifies a similarity threshold a and the resulting factor lattice contains as its elements the maximal group- ings of formal concepts (elements of the original “large” concept lattice over the data) which are pairwise similar in degree at least a. Parameter a controls the coarseness of the factorization and thus the factor of reduction (for a running from 0 over . . . to 1 we obtain a one-element lattice over . . . to a lattice which is isomorphic to the original concept lattice). The resulting factor concept lattice can be computed by definition as follows: (a) compute the “large” (the original, non-factorized concept lattice); (b) compute the factor concept lattice of the large concept lattice. Although polynomial time delay algorithms exist for both (a) and (b), it is interesting to ask whether there is a way to compute the factor lattice directly from the data, i.e. without the need to compute first the “large” concept lattice. In what follows, we show a positive answer and demonstrate its efficiency on examples. 1.2 Preliminaries Fuzzy sets and fuzzy logic We assume basic familiarity with fuzzy logic and fuzzy sets [3, 10]. An element may belong to a fuzzy set in an intermediate degree not necessarily being 0 or 1. Formally, a fuzzy set A in a universe X is a mapping assigning to each x ∈ X a truth degree A(x) ∈ L where L is some partially ordered set of truth degrees containing at least 0 (full falsity) and 1 (full truth). L needs to be equipped with logical connectives, e.g. ⊗ (fuzzy conjunction), → (fuzzy implication), etc. L together with logical connectives forms a structure L of truth degrees. WeVassume that LWforms a so-called residuated lattice in which arbitrary infima and suprema exist. 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, V the degree S (A, B) to which A is a subset of B is defined by S (A, B) = x∈X A(x) → B(x). Then, A ⊆ B means S (A, B) = 1. 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 by ^ ^ A↑ (y) = (A(x) → I(x, y)) (1), B ↓ (x) = (B(y) → I(x, y)) (2). x∈X y∈Y Fast Factorization of Concept Lattices by Similarity 49 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 , B1 i ≤ hA1 , B1 i iff A1 ⊆ A2 (iff B1 ⊇ B2 ) for hA1 , B1 i, hA2 , B2 i ∈ B (X, Y, I), ≤ models the subconcept-superconcept hierar- chy in B (X, Y, I) (being more general means to apply to a larger collection of ob- jects and to cover a smaller collection of attributes). The structure of B (X, Y, I) is characterized in [4]. For further information on fuzzy concept lattices, see e.g. [3, 7]. 2 Fast factorization by similarity 2.1 Factorization by similarity In this section, we recall the method presented in [2]. Given hX, Y, Ii, intro- duce V a binary fuzzy relation ≈ on B (X, Y, I) by (hA1 , B1 i ≈ hA2 , B2 i) = x∈X A1 (x) ↔ A2 (x) for hAi , Bi i ∈ B (X, Y, I), i = 1, 2, where a ↔ b = (a → b) ∧ (b → a). (hA1 , B1 i ≈ hA2 , B2 i) is called the degree of similarity of hA1 , B1 i and hA2 , B2 i (just the truth degree of “for each object x: x is cov- V by A1 iff x is covered by A2 ”). One can show that (hA1 , B1 i ≈ hA2 , B2 i) = ered y∈Y B1 (y) ↔ B2 (y). 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 , B1 i, hA2 , B2 i) ∈ a ≈ iff (hA1 , B1 i ≈ hA2 , B2 i) ≥ 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 , B 0 i | (hA, Bi, hA0 , B 0 i) ∈ a ≈} _ hA, Bi := {hA0 , B 0 i | (hA, Bi, hA0 , B 0 i) ∈ a ≈}. a Lemma 1. a ≈-blocks are exactly intervals of B (X, Y, I) of the form [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. 50 Radim Bělohlávek, Jiřı́ Dvořák, Jan Outrata 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 [2]. We now present an illustrative example. Consider L with L = {0, 21 , 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. Table 1. A simple fuzzy context given by planets and their properties small large far near Mercury (Me) 1 0 0 1 Venus (V) 1 0 0 1 Earth (E) 1 0 0 1 1 Mars (Ma) 1 0 2 1 Jupiter (J) 0 1 1 21 Saturn (S) 0 1 1 21 1 1 Uranus (U) 2 2 1 0 1 1 Neptune (N) 2 2 1 0 Pluto (P) 1 0 1 0 Consider now the a = 12 . There are twelve 1/2 ≈-blocks and they are depicted                                     Fig. 1. Concept lattice B (X, Y, I) of data in Tab. 1 in Fig. 2 (blocks are higlighted by solid lines). The corresponding factor lattice 1 B (X, Y, I)/ 2 ≈ is depicted in Fig. 3. Fast Factorization of Concept Lattices by Similarity 51                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          !                                                                                                                                   #"    #           $               1 Fig. 2. 2 ≈-blocks on the concept lattice of Fig. 1            1 Fig. 3. Factor lattice B (X, Y, I)/ 2 ≈ 52 Radim Bělohlávek, Jiřı́ Dvořák, Jan Outrata 2.2 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 [9]). We present the solution step-by-step but, due to the limited scope, without proofs. For a fuzzy set C in U and a ∈ L, the fuzzy sets a → C and a ⊗ C in U are defined by (a → C)(u) = a → C(u) and (a ⊗ C)(u) V = a ⊗ C(u) for each u ∈ U . For fuzzy sets C, D in U , put (C ≈ D) = u∈U C(u) ↔ D(u). Furthermore, we call a fuzzy set A in X an extent if there is a fuzzy set B in Y such that hA, Bi ∈ B (X, Y, I) (similarly, B is an intent if there is A with hA, Bi ∈ B (X, Y, I)). Lemma 2. If A is an extent then so is a → A; similarly, if B is an intent then so is a → B. Proof. See [6]. a The next lemma shows that for a formal concept hA, Bi, hA, Bia and hA, Bi (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. Lemma 3. For hA, Bi ∈ B (X, Y, I), we have (a) hA, Bia = h(a ⊗ A)↑↓ , a → Bi and (b) hA, Bi = h(a → A), (a ⊗ B)↓↑ i. a Proof. See [6]. 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 . Proof. See [6]. 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. [5]) that C is called a fuzzy closure operator in X if A ⊆ C(A), S(A1 , A2 ) ≤ S(C(A1 ), C(A2 )), C(A) = C(C(A)), for any A, A1 , A2 ∈ LX . Fast Factorization of Concept Lattices by Similarity 53 Theorem 2. Given input data hX, Y, Ii and a threshold a ∈ L, a mapping Ca sending a fuzzy set A in X to a fuzzy set a → (a ⊗ A)↑↓ in X is a fuzzy closure operator in X for which fix(Ca ) = ESB(a). Proof. See [6]. 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 comput- ing 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 gen- erate 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 [5]. Indeed, the algorithm described in [5] generates extents of all formal con- cepts from B (X, Y, I). Now, the extents of formal concepts are exactly the fixed points of a fuzzy closure operator C defined by C(A) = A↑↓ . Furthermore, as one can check, as the algorithm uses only properties of fuzzy closure operators, it is in fact an algorithm for generating the set of fixed points of a fuzzy clo- sure operator. Adapting the algorithm for our situation and taking in account Remark 1, we get the following algorithm for computing a ≈-blocks [c1 , c2 ], i.e. elements of B (X, Y, I)/a ≈: Suppose X = {1, 2, . . . , n}; L = {0 = a1 < a2 < · · · < ak = 1} (the as- sumption 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 follow- ing, 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 ordi- nary 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 [5]). 54 Radim Bělohlávek, Jiřı́ Dvořák, Jan Outrata Theorem 3. The least fixed point A+ which is greater (w.r.t. <) than a given A ∈ LX is given by A+ = A ⊕ (i, j) where (i, j) is the greatest one with A <(i,j) A ⊕ (i, j). 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 [5], generating fix(Ca ) has polynomial time delay complexity (i.e., given a fixed point, the next one is generated in time polynomial in terms of size of the input hX, Y, Ii [9]). Since generating a a ≈-block [h(a ⊗ A)↑↓ , a → A↑ i, hA, A↑ i] from A takes a polynomial time, our algorithm is of polynomial time delay complexity as well. 3 Examples and experiments 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 (ob- jects from X) and some of their economic characteristics (attributes from Y ). The original values of the characteristics are scaled to interval [0, 1] so that the characteristics can be considered as fuzzy attributes. Tab. 3 summarizes the ef- fect of our algorithm and some related characteristics when using L Ã ukasiewicz fuzzy logical connectives. The whole concept lattice B (X, Y, I) contains 774 formal concepts, computing B (X, Y, I) using the polynomial time delay algo- rithm from [5] takes 2292ms. The columns correspond to different threshold values a = 0.2, 0.4, 0.6, 0.8. Entries “size |B (X, Y, I)/a ≈|” contain the num- ber of a ≈-blocks; “naive algorithm (ms)” contain the time in ms for comput- ing B (X, Y, I)/a ≈ by first generating B (X, Y, I) and subsequently generating the a ≈-blocks by producing [hA, Bia , (hA, Bia )a ]; “our algorithm (ms)” con- tain the time in ms for computing B (X, Y, I)/a ≈ by our algorithm; “reduc- tion |B (X, Y, I)/a ≈|/|B (X, Y, I)|” contain the reduction factors of the size of the concept lattice; “time reduction” contain “our algorithm (ms)” divided by “naive algorithm (ms)” (1/“time reduction” is thus the speedup). Fig. 4 contains graphs depicting reduction |B (X, Y, I)/a ≈|/|B (X, Y, I)| and time reduction from Tab. 3. 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). Fast Factorization of Concept Lattices by Similarity 55 Table 2. Data table (fuzzy context) 1 2 3 4 5 6 7 1 Czech 0.4 0.4 0.6 0.2 0.2 0.4 0.2 2 Hungary 0.4 1.0 0.4 0.0 0.0 0.4 0.2 3 Poland 0.2 1.0 1.0 0.0 0.0 0.0 0.0 4 Slovakia 0.2 0.6 1.0 0.0 0.2 0.2 0.2 5 Austria 1.0 0.0 0.2 0.2 0.2 1.0 1.0 6 France 1.0 0.0 0.6 0.4 0.4 0.6 0.6 7 Italy 1.0 0.2 0.6 0.0 0.2 0.6 0.4 8 Geramny 1.0 0.0 0.6 0.2 0.2 1.0 0.6 9 UK 1.0 0.2 0.4 0.0 0.2 0.6 0.6 10 Japan 1.0 0.0 0.4 0.2 0.2 0.4 0.2 11 Canada 1.0 0.2 0.4 1.0 1.0 1.0 1.0 12 USA 1.0 0.2 0.4 1.0 1.0 0.2 0.4 attributes: 1 - Gross Domestic Product per capita (USD), 2 - Consumer Price Index (1995=100) , 3 - Unemployment Rate (percent - ILO), 4 - Production of electricity per capita (kWh), 5 - Energy consumption per capita (GJ), 6 - Export per capita (USD), 7 - Import per capita (USD) Table 3. L Ã ukasiewicz fuzzy logical connectives, B (X, Y, I) of data from Tab. 2: |B (X, Y, I)| = 774, time for computing B (X, Y, I) = 2292 ms; table entries for thresh- olds a = 0.2, 0.4, 0.6, 0.8 0.2 0.4 0.6 0.8 size |B (X, Y, I)/a ≈| 8 57 193 423 naive algorithm (ms) 8995 9463 8573 9646 our algorithm (ms) 23 214 383 1517 reduction |B (X, Y, I)/a ≈|/|B (X, Y, I)| 0.010 0.073 0.249 0.546 time reduction 0.002 0.022 0.044 0.157 0.6 0.2 0.5 0.15 0.4 time reduction size reduction 0.3 0.1 0.2 0.05 0.1 0 0 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.2 0.3 0.4 0.5 0.6 0.7 0.8 thresholds thresholds Fig. 4. Reduction |B (X, Y, I)/a ≈|/|B (X, Y, I)| and time reduction from Tab. 3 56 Radim Bělohlávek, Jiřı́ Dvořák, Jan Outrata Tab. 4 and Fig. 5 show the same characteriztics when using the minimum- based fuzzy logical operations. Finally, we demonstrate the effects on an example of data table from Tab. 5 with a finer distribution of thresholds, a = 0.1, 0.2, . . . , 0.9. Using L Ã ukasiewicz fuzzy logical operations, the characteristics are the same as for the above example and are depicted in Fig. 6. Table 4. Minimum-based fuzzy logical connectives, B (X, Y, I) of data from Tab. 2: |B (X, Y, I)| = 304, time for computing B (X, Y, I) = 341 ms; table entries for thresholds a = 0.2, 0.4, 0.6, 0.8 0.2 0.4 0.6 0.8 size |B (X, Y, I)/a ≈| 8 64 194 304 naive algorithm (ms) 1830 1634 3787 4440 our algorithm (ms) 23 106 431 1568 reduction |B (X, Y, I)/a ≈|/|B (X, Y, I)| 0.026 0.210 0.638 1.000 time reduction 0.012 0.064 0.113 0.353 1 0.4 0.35 0.8 0.3 0.25 0.6 time reduction size reduction 0.2 0.4 0.15 0.1 0.2 0.05 0 0 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.2 0.3 0.4 0.5 0.6 0.7 0.8 thresholds thresholds Fig. 5. Reduction |B (X, Y, I)/a ≈|/|B (X, Y, I)| and time reduction from Tab. 4 4 Open problem Is there a suitable context-factorization construction by similarity such that for the factorized context hX, Y, Ii/a ≈, the concept lattice B(hX, Y, Ii/a ≈) over hX, Y, Ii/a ≈ is isomorphic to B (X, Y, I)/a ≈? Fast Factorization of Concept Lattices by Similarity 57 Table 5. Data table (fuzzy context) 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.3 0.7 0.25 0.6 0.2 0.5 time reduction size reduction 0.4 0.15 0.3 0.1 0.2 0.05 0.1 0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 thresholds thresholds Fig. 6. Reduction |B (X, Y, I)/a ≈|/|B (X, Y, I)| and time reduction from Tab. 5 References 1. R Bělohlávek. Fuzzy concepts and conceptual structures: induced similarities. In Proc. Joint Conf. Inf. Sci.’98, Vol. I, pages 179–182, Durham, NC, 1998. 2. R Bělohlávek. Similarity relations in concept lattices. J. Logic Comput. 10(6):823– 845, 2000. 3. R. Bělohlávek. Fuzzy Relational Systems: Foundations and Principles. Kluwer Academic/Plenum Publishers, New York, 2002. 4. R Bělohlávek. Concept lattices and order in fuzzy logic. Annals of Pure and Applied Logic (to appear, 22 pp.). 5. Bělohlávek R.: Getting maximal rectangular submatrices from [0,1]-valued object- attribute tables: algorithms for fuzzy concept lattices (submitted). Preliminary version appeared in Proc. Fourth Int. Conf. on Recent Advances in Soft Computing. Nottingham, United Kingdom, 12-13 December, 2002, pp. 200–205. 6. R Bělohlávek, J. Dvořák, J. Outrata. Fast factorization of concept-clusters by similarity (in preparation). 7. A. Burusco, R. Fuentes-Gonzáles. The study of the L-fuzzy concept lattice. Math- ware & Soft Computing, 3:209–218, 1994. 8. B. Ganter, R. Wille. Formal Concept Analysis. Mathematical Foundations. Springer, Berlin, 1999. 9. D. S. Johnson, M. Yannakakis, C. H. Papadimitrou. On generating all maximal independent sets. Inf. Processing Letters 15:129–133, 1988. 10. G. .J. Klir, B. Yuan. Fuzzy Sets and Fuzzy Logic. Theory and Applications. Prentice Hall, Upper Saddle River, NJ, 1995. 11. S. Pollandt. Fuzzy Begriffe. Springer, Berlin, 1997.