Formal Concept Analysis (FCA) plays a crucial role in various domains, especially in qualitative data analysis. Here knowledge are extracted from an information system in form of clusters (forming a concept lattice) or in form of rules (implications basis). The number of extracted pieces of information can grow very fast. To control the number of cluster, one possibility is to put some attributes together to get a new attribute called a generalized attribute. However, generalizing does not always lead to the expected results: the number of concepts can even exponentially increase after generalizing two attributes [7,8]. A natural question is whether there is a similarity measure, (possibly cheap and fast to compute), that is compatible with generalizing attributes: i.e. if m1, m2 are more similar than m3, m4, then putting m1, m2 together should not lead to more concepts as putting m3, m4 together. This paper is an attempt to answer this question.
In Formal Concept Analysis (FCA), a formal context is a binary relation
(G, M, I) that models an elementary information system, whereby G is the set of
objects, M the set of attributes and I ⊆ G×M the incidence relation. To extract
knowledge from such an elementary information system, one possibility is to get
clusters of objects and/or attributes by grouping together those sharing the
same characteristics. These pairs, called concepts, were formalized by Rudolf
Wille [
A0 = {m ∈ M | g I m for all g ∈ A} and
B0 = {g ∈ M | g I m for all m ∈ B}. c paper author(s), 2018. Proceedings volume published and copyrighted by its editors.
Paper published in Dmitry I. Ignatov, Lhouari Nourine (Eds.): CLA 2018, pp.
141{152, Department of Computer Science, Palacky University Olomouc, 2018.
Copying permitted only for private and academic purposes.
A concept is a pair (A, B) such that A0 = B and B0 = A. A is called extent and
B intent of the concept (A, B). The set of concepts of a context K := (G, M, I)
is ordered by the relation (A, B) ≤ (C, D) : ⇐⇒ A ⊆ C, and forms a lattice,
denoted by B(K) and called concept lattice of K. To control the size of concept
lattices, many methods have been suggested: decomposition [
In the rest of this contribution, we will simply say generalization to mean
∃generalization. By generalizing (i.e putting together some attributes) we reduce
the number of attributes and hope to also reduce the size of the concept lattice.
Unfortunately this is not always the case. In [
In [
The rest of the paper is organized as follows: In Section 2, we investigate the existing similarity measures that we found in the literature. In Section 3, we give a new similarity measure that characterize the pairs of attributes which can increase the size of the concept lattice after generalizing. Section 4 exposes an example on lexicographic data and Section 5 concludes the paper. 2
Test of Existing Similarity Measures in ∃-Generalization Similarity and dissimilarity measures play a key role in pattern analysis problems such as classification, clustering, etc. Ever since Pearson proposed a coefficient (i) S(m1, m2) ≥ 0, (ii) S(m1, m2) = S(m2, m1) (iii) S(m1, m1) ≥ S(m1, m2) positivity symmetry maximality of correlation in 1896, numerous similarity measures and distance have been proposed in various fields. These measures can be grouped into tree main types, depending of the data on which they are used: Correlation coefficients: They are often used in data to compare variables with qualitative characters subdivided in more than two states.
Distance similarity coefficients: They are generally used in data with pure quantitative variables. In most cases, for quantitative data, the similarity between two taxa is expressed as a function of their distance in a dimensional space whose coordinates are the characters.
Coefficients of association: They are often used in data with presence-absence characters or in data with individuals having qualitative characters subdivided into two states.
There are two subsets of coefficients of association: those that only depend on characteristics present in at least one of the taxa compared, but are independent of the attributes absent in both taxa (denoted by type 1), and those that also take into account the attributes absent in both taxa (denoted by type 2). Those measures use – a as the number of cases where the two variables occur together in a sample, – d as the number of cases where none of the two attributes occur in a sample, – b as the number of cases in which only the first variable occur, and – c as the number of cases where only the second variable occur. One of the most important similarity measure of type 1 is the Jaccard measure a a+b+c , proposed in order to classify ecological species. Also in the ecological field, the Dice coefficient of association 2a+2ab+c aims at quantifying the extent to which two different species are associated in a biotope, the Sorensen coefficient of association 4a+4ab+c and the Anderberg coefficient of association coefficient 8a+8ab+c are of the same type. The Sneath and Sokal 2 similarity 1 a 12 a+2b+c , put in place in order to compare organisms in numerical taxonomy, the Kulczynski similarity measure 12 ( a+ab + a+ac ) Ochiai similarity measure ( √(a+ba)(a+c) ) are also from this first type.
The most used similarity coefficient of the second type is the Sokal and
Michener coefficient of association a+ad++db+c , also called the simple
matching coefficient, put in place to express the similarity between two species of
bees. Moreover, the Rogers and Tanimoto similarity measure ( 12 (a21+(ad+)+db)+c )
whose aim was to compare species of plants in the ecological field, the Sokal and
2(a+d)
Sneath 1 similarity coefficient ( 2(a+d)+b+c ) was defined to make comparison in
a
numerical taxonomy and the Russels and Rao similarity measure ( a+d+b+c )
put in place with the aim of showing resemblance between species of anopheline
and the
larvae, are included in this type. Same are the Yule and Kendall
similarity coefficients ada+dbc , often used in the statistical field. Some of the above
similarity measures can be found in [
Regarding the definitions of the above kinds of similarity measures, only the coefficients of association suitable to formal contexts, since formal contexts are data with presence-absence characters. We will investigate the impact of these coefficients of association on a special pair of attributes in some formal contexts. The objective is to show that these similarity measures are not helpful in finding whether their generalization increases the size of the lattice or not.
Our first example is an arbitrary formal context (G, M, I) containing two attributes x, y ∈ M such that x0 ⊆ y0 and |x0 ∩ y0| = 1. Then |x0 \ y0| = 0 and the generalization of the attributes x and y does not increase the size of the lattice. Choosing |y0 \ x0| = 20 and |G \ (x0 ∪ y0)| = 1 yields a = |x0 ∩ y0| = 1, b = |x0 \ y0| = 0, c = |y0 \ x0| = 20 and d = |G \ (x0 ∪ y0)| = 1. For the coefficient of association of type 1 with Jaccard (Jc), Dice (Di), Sorensen (So), Anderberg (An), Sneath and Sokal 2 (SS2), Kulczynski (Ku) and Orchiai (Orch), and the coefficient of association of type 2 with Sokal and Michener (SM), Rogers and Tanimoto (RT), Sneath and Sokal 1 (SS1) and Russel and Rao (RR), we get the table below for s(x, y):
Jc 0,05
Di 0,09
So 0,17
An 0,29
SS2 0,02
Ku 0,52
Orch 0,22
SM 0,09
RT 0,05
SS1 0,17
RR 0,05
The table above shows that with almost all these measures, the similarity measured between the attributes x and y is very low, despite the fact that their generalization does not increase the size of the lattice.
Our second example is the formal context K6 := (S6 ∪ {g1}, S6 ∪ {m1, m2}, I) below, with S6 = {1, 2, 3, 4, 5, 6}. We observe that |m01 ∩ m02| = 4, |m01\m02| = 1 and |m02\m01| = 1. Putting together the attributes m1 and m2 by a ∃-generalization increases the size of the lattice by 16. The following table shows the measures of type 1 and type 2 between the attribute m1 and any other attribute i. All the similarity measures of the i ∈ S5 i = 6 i = m2
Jc 0,57 0,83 0,67
Di 0,80 0,91 0,80
So 0,89 0,95 0,89
An 0,94 0,97 0,94
SS2 0,50 0,71 0,50
Ku 0,80 0,92 0,80
Orch 0,80 0,91 0,80
SM 0,71 0,75 0,71
RT 0,56 0,75 0,56
SS1 0,83 0,92 0,83 RR 0,57 0,71 0,57 two types show that the attribute m1 is more similar to m2 than to any other attribute i ∈ S6 (apart from i = 6); But putting m1 and m2 together increases the size of the lattice. We can conclude that these similarity measures are not compatible with the ∃-generalization. We are actually looking for a measure on attributes that will flag pairs of attributes as less similar when putting these together increases the size of the concept lattice. 3
A Similarity Measure Compatible with ∃-Generalization In this section we define a similarity measure on attributes which is compatible with the existential generalization. This generalization means that from an attribute reduced context K := (G, M, I), two attributes a, b are removed and replaced with an attribute s defined by s0 = a0 ∪ b0. We set M0 := M \ {a, b} and K00 :=(G, M0, I ∩(G × M0)), K0s :=(G, M0 ∪·{s}, I0s), (removing a, b from K) (adding s to K00) where I0s := (I ∩(G × M0)) ∪ {(g, s) | g I b or g I a}. Furthermore we denote the set of extents of K00 by Ext(K00). We also set
H(a) := {A ∩ a0 | A ∈ Ext(K00) and A ∩ a0 ∈/ Ext(K00)} ,
H(b) := {A ∩ b0 | A ∈ Ext(K00) and A ∩ b0 ∈/ Ext(K00)} ,
H(a ∪ b) := {A ∩ (a0 ∪ b0) | A ∈ Ext(K00) and A ∩ (a0 ∪ b0) ∈/ Ext(K00)} ,
H(a ∩ b) := {A ∩ (a0 ∩ b0) | A ∈ Ext(K00) and A ∩ (a0 ∩ b0) ∈/ Ext(K00)} .
We will often write h(x) for |H(x)|, for any x ∈ {a, b, a ∩ b, a ∪ b}. Before we
start the construction, let us recall the following result partly proved in [
|B(K)| = |B(Ka)| + h∗(b) = |B(K00)| + h(a) + h∗(b)
where h∗(b) = |{B ∩ b0; B ∈ Ext(Ka), B ∩ b0 ∈/ Ext(Ka)}|. Our aim is to
express h∗(b) as a function of h(b) and h(a∩b). According to [
H∗(b) = {B ∩ b0 | B ∈ Ext(Ka), B ∩ b0 ∈/ Ext(Ka)} = {B ∩ b0 | B ∈ Ext(K00) and B ∩ b0 ∈/ Ext(Ka)}
∪ {B ∩ b0 | B ∈ H(a) and B ∩ b0 ∈/ Ext(Ka)} Replacing Ext(Ka) by Ext(K00) ∪ H(a), we get {B ∩ b0 | B ∈ Ext(K00) and B ∩ b0 ∈/ Ext(Ka)} = H(b) \ H(a) and {B ∩ b0 | B ∈ H(a) and B ∩ b0 ∈/ Ext(Ka)} = H(a ∩ b) \ (H(b) ∪ H(a)). Thus, h∗(b) = h(b) + h(a ∩ b) − |H(a) ∩ H(b)| + |H(a ∩ b) ∩ H(a) ∩ H(b)| − |H(a ∩ b) ∩ H(a)| − |H(a ∩ b) ∩ H(b)|.
Hence,
|B(K)| = |B(K00)| + |H(a)| + |H(b)| + |H(a ∩ b)| + |H(a ∩ b) ∩ H(a) ∩ H(b)|
− |H(a) ∩ H(b)| − |H(a ∩ b) ∩ H(a)| − |H(a ∩ b) ∩ H(b)|
= |B(K00)| + |H(a) ∪ H(b) ∪ H(a ∩ b)|.
b) Although b) was proved in [
• If |H(a ∩ b)| = 0, then |B(K)| = |B(K00)| + |H(a) ∪ H(b) ∪ H(a ∩ b)|
= |B(K00)| + |H(a)| + |H(b)|. • If |H(a ∩ b)| = 1, then we consider two subcases: – The only element of H(a ∩ b) is not in H(a) ∪ H(b). Then, |H(a) ∩ H(b)| = |H(a ∩ b) ∩ H(a) ∩ H(b)|
= |H(a ∩ b) ∩ H(a)| = |H(a ∩ b) ∩ H(b)| = 0 and |B(K)| = |B(K00)| + |H(a)| + |H(b)| + |H(a ∩ b)|. – The only element of H(a ∩ b) is either in H(a) or H(b). Then |H(a ∩ b)| + |H(a ∩ b) ∩ H(a) ∩ H(b)| − |H(a ∩ b) ∩ H(a)| − |H(a ∩ b) ∩ H(b)| is equal to zero and |H(a) ∩ H(b)| ∈ {0, 1}. Thus |B(K)| = |B(K00)| + |H(a)| + |H(b)| + 1 − |H(a) ∩ H(b)|. In all these subcases, considering that |B(K0s)| = |B(K00)| + |H(a ∪ b)|, the increase after the generalization is |B(K0s)| − |B(K)| = |H(a ∪ b)| − |H(a, b)| ≤ 2|a0|+|b0| − 2|a0| − 2|b0| + (d1 + d2 − d0) ≤ 2|a0|+|b0| − 2|a0| − 2|b0| + 1, since d1 + d2 − d0 ≤ 0, with d1 = |{A ⊆ a0 | A ∈ Ext(K00)}|, d2 = |{A ⊆ b0 | A ∈ Ext(K00)}| and d0 = |{A ⊆ a0 ∪ b0 | A ∈ Ext(K00)}|. tu Now, we define the following gain function: ψ : M × M −→ Z
(a, b) 7−→ ψ(a, b) = |H(a ∪ b)| − |H(a, b)| Note that H(a ∪ b) = H(b ∪ a), and H(a, b) = H(b, a) because the order of adding the attributes a and b does not matter. Therefore ψ(a, b) = ψ(b, a). By definition, ψ(a, a) = 0. Further, we define the map δ as followed: δ : M × M −→ R
(1 (a, b) 7−→ 0 if ψ(a, b) ≤ 0 else |a00| + |b00| = am,b∈aMx(|a0| + |b0|).
Since K is a finite context, there is a pair of attributes a0, b0 in M such that We set n0 = 2|a00|+|b00| − 2|a00| − 2|b00| + 1. Then n0 ≥ 2|a0|+|b0| − 2|a0| − 2|b0| + 1 for all pairs {a, b} ⊆ M . With the function δ, we construct the following map: Sgen : M × M −→ R (a, b) 7−→ Sgen(a, b) = 1+δ2(a,b) − |ψ(a,b)| 2n0 where |ψ(a, b)| is the absolute value of ψ(a, b). That leads to the following results. Proposition 1. Let (G, M, I) be a reduced context with |G| ≥ 3 and |M | > 3. Then Sgen is a normalized similarity measure on M .
Proof. Let a, b two attributes of (G, M, I). Since |ψ(a, b)| ≤ n0 we can easily check that 0 ≤ Sgen(a, b) = Sgen(b, a) ≤ Sgen(a, a) = 1 holds. tu
Sgen also has the following properties: Proposition 2. Let (G, M, I) be a reduced context with |G| ≥ 3 and |M | > 3. Let a, b, c, d ∈ M . It holds: a) Sgen(a, b) ≥ 21 if and only if ψ(a, b) ≤ 0. b) If ψ(a, b) ≤ 0 < ψ(d, c) then Sgen(d, c) < Sgen(a, b). c) If 0 < ψ(a, b) ≤ ψ(d, c) then Sgen(d, c) ≤ Sgen(a, b). d) If ψ(a, b) ≤ ψ(d, c) ≤ 0 then Sgen(a, b) ≤ Sgen(d, c).
Proof. Let K = (G, M, I) be such a context and a, b, c, d ∈ M . a) If ψ(a, b) ≤ 0 then δ(a, b) = 1 and
Sgen(a, b) = 1 + δ(a, b) 2 − |ψ(a, b)| = 1 2n0 2 2 + ψ(a, b) n0
Now, Sgen(a, b) ≥ 12 implies 1+δ2(a,b) − |ψ2(na,0b)| ≥ 21 and |ψ(a, b)| ≤ n0δ(a, b). If δ(a, b) = 0 then |ψ(a, b)| = 0. If δ(a, b) = 1 then ψ(a, b) ≤ 0 by definition of δ. Hence, Sgen(a, b) ≥ 12 if and only if ψ(a, b) ≤ 0. b) If ψ(a, b) ≤ 0 < ψ(d, c) then Sgen(d, c) < 12 ≤ Sgen(a, b). c) If 0 < ψ(a, b) ≤ ψ(d, c) then δ(a, b) = δ(d, c) = 0, and d) If ψ(a, b) ≤ ψ(d, c) ≤ 0 then δ(a, b) = δ(d, c) = 1, and
1 Sgen(d, c) = 2 − ψ(d, c) 2n0 Proposition 3. Let (G, M, I) be a reduced context and a, b ∈ M . The following assertions are equivalent: (i) δ(a, b) = 1. (ii) ψ(a, b) ≤ 0. (iii) Sgen(a, b) ≥ 12 . (iv) A ∃-generalization of a and b does not increase the size of the concept lattice. Proof. (i) ⇐⇒ (ii) follows from the definition of δ. (ii) ⇐⇒ (iii) is Proposition 2 a). (ii) ⇐⇒ (iv) follows from the fact that ψ(a, b) = |H(a ∪ b)| − |H(a, b)| is actually the difference |B(G, M ∪ {s} \ {a, b}, I)| − |B(G, M, I)| between the number of concepts before and after generalizing a, b to s with s0 = a0 ∪ b0. Therefore, generalizing two attributes a, b in a reduced context (G, M, I) increases the size of the lattice if and only if Sgen(a, b) < 21 . The threshold 12 is just a consequence of the way Sgen has been defined.
To test our results we have designed a naive algorithm (see Algorithm 1) that computes Sgen on all pairs of attributes a, b of K. If the set of attributes M is considered as a vector, then for any attribute a ∈ M , we set T(a) the set of all attributes coming before a in M . The complexity of our algorithm is given by X (1 + a∈M
X b∈M\T (a)
((q(a, b) + 4)[4(q(a, b) + 1) + 4] + 3), (4q2(a, b) + 24q(a, b) + 35), with q(a, b) = | Ext(K00)|. which is equal to |M | + X
X a∈M b∈M\T (a) ψ(b, a) ← ψ(a, b); 4
An Example from Lexicographic Data
Formal Concept Analysis has been applied to compare lexical databases. In [
building house Haus Geb¨aude large business residential small factory office house large × × × × × × × × × × × × × × × × For this formal context, n0 = 23+3 − 23 − 23 + 1 = 49. Let consider the attributes a := house and b := Geb¨aude. Then a0 ∪ b0 = {f, h} and a0 ∩ b0 = ∅. We have
Ext(K00) = {f ohl, f ol, ohl, f o, f l, ol, oh, hl, f, o, h, l, ∅}, and H(a) = H(b) = H(a ∩ b) = ∅ and H(a ∪ b) = {f ohl}. Therefore, ψ(a, b) = 1 and Sgen(a, b) = 21 − 918 ≈ 0.49. Using our algorithm, we compute ψ(a, b) and Sgen(a, b) for all pairs a, b ∈ M . The table below show ψ(a, b) below the diagonal, and Sgen(a, b) on the rest.
building house
Haus Geb¨aude
large business residential small −1 −2 −3 −3 −2 −3 −3 −1 −1
From the above table, the attributes ”house” and ”Geb¨aude” are less similar. It reflects the fact that these words ”Geb¨aude” (in German) and ”house” (in English) do not have the same meaning. It is also the case for the attributes ”house” and ”business buildings” as well as ”Geb¨aude” and ”residential building”. Hence, putting together each of the above pairs of attributes will increase the size of the lattice. On the contrary, the attributes ”large” and ”Haus”, ”building” and ”Haus” are more similar through Sgen. It is because the word ”Haus” which designates a house, a business office or simply large building in German, often coincides with the words ”building” or ”large building” in English. For these pairs, the existential generalization will not increase the size of the lattice. 5
Conclusion We have constructed a similarity measure compatible with the change in the size of the lattice after a generalization of a pair of attributes in a formal context. That measure should send a warning when grouping two attributes. Also, it enables us to characterize contexts where generalizing two attributes increases the size of the concept lattice. Our next step is to look at the implication between generalized attributes. We suspect that the number of implications decreases if the number of concepts increases.