Distances Between Formal Concept Analysis Structures

In the following, we consider only finite sets.

Formal Concept Analysis (FCA) is a mathematical framework based on lattice theory that aims at structuring the information contained in the relation between objects and their attributes [12]. It is centered around the notion of formal context.

Formal contexts can be represented as crosstables.

A formal context $𝒞$ gives rise to two derivation operators, both usually noted ${\cdot }^{\prime }$, defined as:

where $𝒫(X)$ denotes the powerset of $X$.

For instance, in the Fig. 1 context, ${\{a_2,a_4\}}^{\prime }=\{o_2,o_3\}$ and ${\{a_1\}}^{\prime \prime }=\{a_1,a_2\}$. Both operators ${\cdot }^{\prime }$ form a Galois connection and their compositions ${\cdot }^{\prime \prime }$ are closure operators. Throughout this paper, when in the presence of two different formal contexts ${𝒞}_1$ and ${𝒞}_2$, we shall use ${\cdot }^{{}_{}{}^{\prime }i}$ and ${\cdot }^{{}_{}{}^{\prime \prime }i}$ to denote the derivation and closure operators of context ${𝒞}_i$.

Visually, concepts correspond to maximal rectangles of crosses in the context’s crosstable, up to permutation of rows and columns. In the Fig. 1 context, the pair $(\{o_2,o_3\},\{a_2,a_4\})$ is a concept while the pair $(\{o_3,o_4\},\{a_5\})$ is not as ${\{a_5\}}^{\prime }=\{o_3,o_4,o_5\}$. Concepts can be ordered by the inclusion relation on their extents, i.e. $(E_1,I_1)\le (E_2,I_2)\iff E_1\subseteq E_2$. As per the basic theorem of formal concept analysis [12], the set of all concepts of a context $𝒞$ ordered in such a way forms a complete lattice called the concept lattice of $𝒞$. Additionally, all complete lattices are isomorphic to the concept lattice of some context.

In the Fig. 1 context, the implications $\{a_1\}\to \{a_1,a_2\}$ and $\{a_3,a_4\}\to \{a_2\}$ hold while the implication $\{a_3\}\to \{a_5\}$ does not. For simplicity’s sake, we thereafter say “$X\to Y$” instead of “$X\to Y$ holds”. Some implications can be inferred from others through Armstrong’s axioms:

• $\mathrm{■}$

  if $Y\subseteq X$, then $X\to Y$ (Reflexivity)

• $\mathrm{■}$

  if $X\to Y$, then $X\cup Z\to Y\cup Z$ for all attribute sets $Z$ (Augmentation)

• $\mathrm{■}$

  if $X\to Y$ and $Y\to Z$, then $X\to Z$. (Transitivity)

Several implication bases with interesting properties exist in the literature [5, 4]. In this paper, we are interested in only one.

In the Fig. 1 example, the set $\{a_2,a_3\}$ is a proper premise of the attribute $a_4$ as no proper subset of $\{a_2,a_3\}$ implies $\{a_4\}$. The set of all implications $X\to \{a\}$ where $a$ is an attribute and $X$ is one of its proper premises forms an implication base.

For instance, the logical closure of the attribute set $\{a_1,a_3\}$ by the implication base $ℐ=\{\{a_1\}\to \{a_2\},\{a_2,a_3\}\to \{a_4\}\}$ is ${\{a_1,a_3\}}^{ℐ}=\{a_1,a_2,a_3,a_4\}$. The logical closure, as its name indicates, is a closure operator. If $𝒞$ is a formal context and $ℐ$ an implication base of $𝒞$, then ${\cdot }^{ℐ}={\cdot }^{\prime \prime }$.

A metric on a set $S$ is a function of distance between the elements of $S$ satisfying the following axioms:

• $\mathrm{■}$

  $f(x,x)=0$

• $\mathrm{■}$

  $f(x,y)>0$ when $x\ne y$, (positivity)

• $\mathrm{■}$

  $f(x,y)=f(y,x)$, (symmetry)

• $\mathrm{■}$

  $f(x,z)\le f(x,y)+f(y,z)$. (triangular inequality)

In this paper, we make use of two families of metrics between vectors and sets so as to build our own metrics between FCA structures. The first is the well-known family of Minkowski distances between vectors $X=(x_1,\mathrm{\dots },x_n)$ and $Y=(y_1,\mathrm{\dots },y_n)$ defined as

The second is the family of normalised set-based analogues of Minkowski distances [13] defined, for two sets $X$ and $Y$, as

In this paper, we chose to use the Minkowski distance for sets. Other, more usual distances (e.g. Hamming distance, or another edit distance) might also be interesting, and in most cases they can be plugged into the calculations in Section 3 to describe new families of distances between FCA structures. In [8], some distances are described directly for binary relations and for (semi-)lattices. However, formal contexts are special cases of binary relation (bipartite graphs) and concept lattices are more than lattices as they take two dimensions into account – objects and attributes. Therefore, we did not make use of those distances and instead chose to propose new ones.

We aim at proposing distances between FCA structures. This is not a brand new endeavor. Distances between formal contexts can be obtained by considering contexts as being any more widely known structures, such as bipartite graphs or hypergraphs, and using existing distances for these structures. Similarity measures between concept lattices have already been studied [9]. However, these are not sufficient. What we want is a set of three distances that can be used to compare two entities in their three different forms (context, lattice and implication base) and the knowledge of how these three distances relate to each others. In this paper, we suppose that all pairs of structures we compare use the same objects and attributes.

In this section, we define families of distances for each of the usual structures of FCA, and show that they are metrics. The three families are based on the normalised set-based analogues of Minkowski distances $d_{2,p}$ [13]. In Section 4, we provide experimental results on the interaction of those distances.

As we only consider contexts on the same sets of objects and attributes, the distance between the contexts depends only on their incidence relations. Hence, we define our distances between formal contexts as a distance between binary relations seen as sets of pairs.

The two formal contexts depicted in Fig. 3 have a factual distance of $\approx 0.13$.

As $d_{2,p}$ is a metric, the factual distance is a metric.

We consider concept lattices as pairs of functions that map sets of objects to the set of attributes they have in common and sets of attributes to the set of objects they all describe, i.e. we see concept lattices as representations of the derivation operators ${\cdot }^{\prime }$. If $(E,I)$ is a concept, then all subsets of $E$ that are not subsets of lower neighbours in the lattice are mapped to $I$ and reciprocally. This is notationally easier to express in terms of the derivation operators associated with the formal context of the lattice: object sets $O$ are mapped to $O^{\prime }$. As such, we define our distance between concept lattices as a distance between the derivation operators. For this reason, our distance makes use of the distances between the derivations of every element of the powerset of objects/attributes in both contexts. This has the added benefit of facilitating the comparison of concept lattices with different extents/intents.

In this definition, we chose to use the minimum between the lattice object distance and the lattice attribute distance. One could use the maximum between those two quantities to obtain a slightly different distance.

Figure 4 depicts the two chain concept lattices of the two contexts in Fig. 3. Even though they are isomorphic, their conceptual distance is $\approx 0.33$ with $p=2$ and $q=1$.

In the following example, as well as in the experiments section (Section 4), we chose to fix $p=2$ and $q=1$ in our calculations. Fixing $q=1$ creates an analogue to the Manhattan distance. Then, a generalised mean is computed over the set of attributes (resp. objects). With $p=2$, we are using the root mean square deviation.

The conceptual distance takes its values in $[0,1]$ and is a metric, satisfying the following axioms:

1. 1.

   $CD(x,x)=0$

2. 2.

   $CD(x,y)>0$ when $x\ne y$, (positivity)

3. 3.

   $CD(x,y)=CD(y,x)$, (symmetry)

4. 4.

   $CD(x,z)\le CD(x,y)+CD(y,z)$. (triangular inequality)

These follow directly from the fact that $d_{2,p}$ is a metric:

1. 1.

   because ${ℒ}_1={ℒ}_2\Rightarrow 𝒫({\{o\}}^{\prime 1})=𝒫({\{o\}}^{\prime 2})$ and $d_{2,q}(𝒫({\{o\}}^{\prime 1}),𝒫({\{o\}}^{\prime 1}))=0$

2. 2.

   because $d_{2,q}(𝒫({\{o\}}^{\prime 1}),𝒫({\{o\}}^{\prime 2}))>0$

3. 3.

   because $d_{2,q}(𝒫({\{o\}}^{\prime 1}),𝒫({\{o\}}^{\prime 2}))=d_{2,q}(𝒫({\{o\}}^{\prime 2}),𝒫({\{o\}}^{\prime 1}))$

4. 4.

   because

   $$d_{2,q}(𝒫({\{o\}}^{\prime 1}),𝒫({\{o\}}^{\prime 3}))\le d_{2,q}(𝒫({\{o\}}^{\prime 1}),𝒫({\{o\}}^{\prime 2}))+d_{2,q}(𝒫({\{o\}}^{\prime 2}),𝒫({\{o\}}^{\prime 3}))$$

Computing the conceptual distance is quite easy: for each object $o$, find the concepts with the smallest extents that contain $o$ in both lattices. Their intents are ${\{o\}}^{\prime 1}$ and ${\{o\}}^{\prime 2}$ respectively. Then, computing $d_{2,q}(𝒫({\{o\}}^{\prime 1}),𝒫({\{o\}}^{\prime 2}))$ is straightforward. Algorithm 1 follows this principle. Finding the concept with the smallest extent that contains an object in the lattice ${ℒ}_i$ can be done in $O(|{ℒ}_i|)$ so the time complexity of Algorithm 1 is in $O((|𝒪|+|𝒜|)\times max(|{ℒ}_1|,|{ℒ}_2|))$.

For our distance between implication bases, we consider implication bases as functions mapping attribute sets $X$ to attribute sets $Y=\{y|X\to \{y\}\}$, i.e. we see implication bases as representations of the closure operator ${\cdot }^{\prime \prime }$ on attributes. Note that, from Armstrong’s axioms, we can infer that

Fig. 5 depicts the two proper premises implication bases of the contexts in Fig 3. These two implication bases have a logical distance of $\approx 0.23$. Indeed, the attribute $a_3$ is implied by all supersets of $\{a_4\}$ only in the first context and the attribute $a_4$ is implied by all supersets of $\{a_3\}$ only in the second context.

The logical distance takes its values in $[0,1]$ and is a metric, satisfying the following axioms:

1. 1.

   $LD(x,x)=0$

2. 2.

   $LD(x,y)>0$ when $x\ne y$, (positivity)

3. 3.

   $LD(x,y)=LD(y,x)$, (symmetry)

4. 4.

   $LD(x,z)\le LD(x,y)+LD(y,z)$. (triangular inequality)

Just as those for the conceptual distance, these axioms follow from the fact that $d_{2,q}$ is a metric.

To compute the logical distance, one requires the knowledge of all the attribute sets $X$ that imply a given attribute $a$. This is not explicitly contained in implication bases and retrieving it is the computationally most expensive part of computing the distance. We propose Algorithm 3 to compute the logical distance. We assume that the implication bases are proper premises bases. If this is not the case, other bases can be converted to proper premises bases in output-polynomial time [16].

The algorithm treats each attribute $a$ separately. The first step is to compute the cardinalities of ${ℐ}_1^a\cap {ℐ}_2^a$, ${ℐ}_1^a$ and ${ℐ}_2^a$. To do so, we start with computing the attribute sets $P$ that are minimal such that $P\to \{a\}$ in both implication bases ($commonPremises$). The cardinality of ${ℐ}_1^a\cap {ℐ}_2^a$ is then the number of attributes sets that contain one of the elements of $commonPremises$. To obtain it, we compute the union closure $U_c$ of the set $commonPremises$, i.e. the minimal sets of attributes sets such that $X,Y\in U_c\Rightarrow X\cup Y\in U_c$. The set $U_c$ ordered by set-inclusion forms a lattice. We use Algorithm 2 to associate to each element $x$ of $U_c$ the number of attribute sets that contain $x$ but not its supersets in $U_c$, i.e. the size of the equivalence classes in the union-closed lattice. Algorithm 3 then sums those numbers ($su{m}_c$) to obtain the numbers of attribute sets containing one of the corresponding premises. The same approach is applied to compute the cardinalities of ${ℐ}_1^a$ and ${ℐ}_2^a$. As the size of the union closure is bounded by $2^{|𝒜|}$ (when all singletons are premises), the worst case complexity of Algorithm 3 is in $O(|𝒜|\times 2^{|𝒜|})$.

The first question that may come to mind is “how do these distances compare to each others?”. Let us consider the Fig. 6 example representing three contexts ${𝒞}_{B_3}$, ${𝒞}_{M3}$ and ${𝒞}_{N5}$ corresponding respectively to Boolean (${ℬ}_3$), $M_3$ and $N_5$ concept lattices, and their associated proper premises implication bases ${ℐ}_{B_3}$, ${ℐ}_{M_3}$ and ${ℐ}_{N_5}$. We compute the factual, conceptual and logical distances between ${𝒞}_{{ℬ}_3}$ and the other two and obtain the following results:

We observe that ${𝒞}_{N_5}$ is factually and conceptually closer to ${𝒞}_{{ℬ}_3}$ while ${𝒞}_{M_3}$ is logically closer. The three distances therefore do not always agree. Are they at least correlated? In order to answer this question, we generated structures in different ways. As contexts are the easiest structure to manipulate, we explored the following approaches:

• $\mathrm{■}$

  starting from a full context and iteratively removing crosses either row by row or randomly chosen

• $\mathrm{■}$

  randomly generating contexts

  • –

    by having each cross with a probability $p$

  • –

    by randomly flipping each cross of a reference context with a probability $p$

• $\mathrm{■}$

  generating pseudo-real contexts by sampling real data.

In each case, we computed three correlation coefficients, Pearson, Spearman and Kendall’s $\tau$.

In a first series of experiment, we explored whether we could control the variation of the distances by purposefully modifying a context.

In a second series of experiments, we explored how random generations and modifications of contexts impact the distances, with a focus on how correlated the distances are.

In this experiment, we sampled real datasets to create pseudo-real contexts. We used the Mushroom dataset [20] and the data from A statistical analysis of the work of Bob Ross³³3https://fivethirtyeight.com/features/a-statistical-analysis-of-the-work-of-bob-ross/. We generate pseudo-real data to minimise the risk of interference from the generation method, since generating random formal context is not a trivial task, as shown in [6]. Our sample strategy is the following: we uniformly sample a number $n_o$ of objects along the dimension of objects and a number $n_a$ of attributes along the dimension of attributes. Then, we keep the portion of the incidence relation that correspond to those objects and attributes. Finally, we rename the objects and attributes from 1 to, respectively, $n_o$ and $n_a$ so that two sampled contexts may have the same object and attribute sets. For this set of experiments, our goal is, again, to study the correlations between pairs of distances.

We sampled the Mushroom dataset (8124 objects and 119 attributes) into 1500 smaller contexts (56 objects and 11 attributes) and computed the three distances between pairs of such sampled contexts. The average density of the sampled contexts is $0.19$.

The results are shown in Fig. 12. They show no strong correlation between the distances, except between the factual distance and the logical distance. In this experiment, the logical distance only takes values around a few quantities, unlike in the case of the removal of crosses where the logical distance had exactly the same 10 values.

We sampled the Bob Ross dataset as well. It is a 433$\times$133 context based on the apparition, or not, of some features in Bob Ross’ paintings, for each episode of The Joy Of Painting. We sampled it into 1500 smaller, 44$\times$10 contexts. In this case, the average density is $0.50$.

The results are shown in Fig. 13. In this case, each pair of distances shows a stronger correlation, especially between the factual and conceptual distances. The difference between the two experiments might be related to the density of the contexts, or to intrinsic differences between the data sets, as Bob Ross’ paintings usually had the same few elements appearing together in most episodes.

Domenach’s dissimilary measure is based on the overhanging relation [10] between sets of objects. Two sets are overhanged if one is a subset of the other and their closures are different. To compute a distance between concept lattices, Domenach defines two matrices, $M_1$ and $M_2$, based on the overhanging relation of pairs of objects in each concept lattice. The distance is then based on the $L_1$ norms of those matrices: $\frac{\Vert M_1-M_2\Vert }{\Vert M_1\Vert +\Vert M_2\Vert }$.

We compared our distances with Domenach’s dissimilarity measure on $1000$ pairs of randomly generated contexts. Fig. 14 depicts the results. We observe that Domenach’s dissimilarity measure is independent of our conceptual distance and slightly correlated with our factual distance.