### Formal Concept Analysis

#### Posted by Simon Willerton

Last time I posted about the nucleus of enriched functors. This time I will post about something a bit (!) less abstract — formal concept analysis — something which has applications in data-mining, software engineering and, possibly, catching terrorists. Next time I’ll post about how these two things come together and can give rise to fuzzy concept analysis.

Formal concept analysis is about extracting the relationships and hierarchies available from the common attributes shared by objects. Let’s try to break up this abstract definition with a concrete example.

In the most basic form of formal concept analysis, the input consists of a set of *objects* $G$ (from the German ‘Gegenstände’), a set of *attributes* $M$ (from the German ‘Merkmale’) and a *relation* $I$ (from the German ‘Inzidenzrelation’) between the objects and the attributes expressing which objects have which attributes. This triple $(G,M,I)$ is called the *formal context* and is often expressed as a table. I don’t feel witty enough today to think up a pertinent Café-based example, so instead I will steal a standard example from the formal concept analysis literature. Here is the table.

[For non-native English speakers, bream is a kind of fish.]

The output of the analysis is the *concept lattice* $\mathcal{B}(G,M,I)$ (from the German ‘Begriffsverband’). This is a lattice, which means it is a poset in which each pair of elements have a greatest lower bound and a least upper bound. The concept lattice expresses relationships between the objects and the attributes. Here is the concept lattice for the above example.

I will explain how you go from the formal context to the concept lattice in the main body below. The relation with my last post is contained in the following slogan.

The concept lattice is the nucleus $N(I)$ of the relation $I$.

This comes about by thinking about everything here as being done in the realm of categories enriched over truth values. I’ll explain that next time, but many of you will be able to see that in what you read here.

#### Formal concept analysis

I don’t know anything about the philosophical roots of the subject but the mathematics of formal concept analysis was fomented in a seminal paper of Rudolf Wille in the 80s.

Wille, Rudolf, “Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts” Ordered Sets. Springer, 1982. 445-470.

The theory was based on Garrett Birkoff’s work on lattice theory of the 30s and developed with Wille’s colleague’s Peter Burmeister and Bernard Ganter in Darmstadt.

I got to meet Bernard Ganter briefly recently by a strange coincidence. Nora Ganter was visiting Sheffield last month from Melbourne. I was talking to her about categorical traces and categorical representations. Over coffee it came out that her father was a mathematician and I realised that it was the Bernard Ganter whose name I had first come across the week before when chasing up some references for my Isbell completion paper. However, not only was he her father, but he was also in Sheffield in the role as baby-sitting grandfather to Nora’s daughter. We managed to have a quick chat before I disappeared off on holiday.

#### Objects and attributes

Anyway, getting back to the mathematical story, we start with a set of objects $G$ and a set of attributes $M$, in our example these are $\begin{aligned} G&=\{ \text {fish leech}, \text {bream}, \text {frog}, \dots , \text {corn}\} \\ M&=\{ \text {needs water to live},\text {lives in water},\dots ,\text {breast feeds}\} \end{aligned}$ Given a set of objects $A\subseteq G$ we can form a set of attributes $I^{\ast }(A)\subseteq M$ which is the set of attributes shared by all objects in $A$: $I^{\ast }(A)\coloneqq \{ b\in M\mid a I b\, \text {for all}\, a\in A\}$ So for instance $I^{\ast }(\{ \text {dog},\text {bream}\} )= \{ \text {needs water to live},\text {can move},\text {has limbs}\} .$

This gives us a function – the shared attributes function – between power sets $I^{\ast }\colon \mathcal{P}(G)\to \mathcal{P}(M)$. Power sets come with a natural partial order on them, namely that of being a subset. With respect to this, the shared attributes function $I^{\ast }$ is order reversing: $A\subseteq A'\, \implies \, I^{\ast }(A)\supseteq I^{\ast }(A').$ In words, if you increase the set of objects then you will decrease the set of attributes that they share.

This means we can think of the shared attributes function as an order-preserving function $I^{\ast }\colon \mathcal{P}(G)\to \mathcal{P}(M)^{\mathrm{op}}.$

Similarly we have an order preserving function going the other way $I_{\ast }\colon \mathcal{P}(M)^{\mathrm{op}}\to \mathcal{P}(G)$ which is the objects-with-those-attributes function. So for instance $I_{\ast }(\{ \text {needs water to live},\text {can move},\text {has limbs}\} )= \{ \text {dog},\text {bream},\text {frog}\} .$

#### Galois connections and closure operations

The functions $I^{\ast }$ and $I_{\ast }$ form what is known as a **Galois connection**. This means that for all subsets of objects $A\in \mathcal{P}(G)$ and sets of attributes $B\subseteq \mathcal{P}(M)$ we have
$I^{\ast }(A)\supseteq B \, \Longleftrightarrow \, A\subseteq I_{\ast }(B).$
This is clear, because both expressions are just saying that all the objects in $A$ have all the attributes in $B$.

A Galois connection gives rise to two **closure operations**. The closure operations here are $I_{\ast }I^{\ast }\colon \mathcal{P}(G)\to \mathcal{P}(G)$ and $I^{\ast }I_{\ast }\colon \mathcal{P}(M) \to \mathcal{P}(M)$. The closure operation on sets of objects is to take all objects which share all the attributes that the objects in the original set share. So
$I_{\ast }I^{\ast }(\{ \text {dog},\text {bream}\} )= \{ \text {dog},\text {bream},\text {frog}\} .$

Similarly, the closure operation for attributes takes a set of attributes and adds in all other attributes which are shared by the objects with the original attributes. So for example $I^{\ast }I_{\ast }(\{ \text {has limbs}\} )= \{ \text {needs water to live},\text {can move},\text {has limbs}\} .$ It should be reasonably clear that these deserve the name closure operations as they are idempotent, so doing the operation twice doesn’t add anything new.

A **closed set of objects** is one which is equal to its closure, i.e. $A\subseteq G$ such that $I_{\ast }I^{\ast }(A)=A$. So $\{ \text {dog},\text {bream}\}$ is not closed, but $\{ \text {dog},\text {bream},\text {frog}\}$ is. A closed set of objects is a maximal set of objects which share some attributes. There is the analogous notion for attributes, so $\{ \text {has limbs}\}$ is not closed but $\{ \text {needs water to live},\text {can move},\text {has limbs}\}$ is.

#### The concept of a concept

We now reach the fundamental notion of a **concept**. A concept $(A,B)\in \mathcal{P}(G)\times \mathcal{P}(M)$ consists of a set of objects $A$ and a set of attributes $B$ such that $I^{\ast }(A)=B$ and $A=I_{\ast }(B)$. It is immediate that both $A$ and $B$ are closed. In our example we would have the concept
$(\{ \text {dog},\text {bream},\text {frog}\} ,\{ \text {needs water to live},\text {can move},\text {has limbs}\} ),$
we might call this concept ‘limbed animals’. For a concept $(A,B)$ the set of objects $A$ is called the **extent** of the concept and the set of attributes $B$ is called the **intent** of the concept.

You can imagine rather bigger examples than our baby example here, such as $G$ being the set of all species of animal on the planet and $M$ being some suitable set of attributes. I would expect (subject to picking a good set of attributes) that there would be a concept of ‘bird’, with the extent of the concept of bird being the set of all bird species and the intent including attributes such as ‘lays eggs’, ‘has feathers’ and ‘has wings’, but not including ‘can fly’ as we know of bird species such as penguins which can’t fly.

It’s not hard to see that the set of concepts $\mathcal{B}(G,M,I)$ is in bijective correspondence with the set $\mathcal{P}_{\mathrm{cl}}(G)$ of closed sets of objects. In one direction you just take the extent of the concept, $(A,B)\mapsto A$, and in the other direction you take the closed set with its shared attributes, $A\mapsto (A,I^{\ast }(A))$. Similarly we have a bijection with the set $\mathcal{P}_{\mathrm{cl}}(M)$ of closed sets of attributes. So as sets we have bijections $\mathcal{P}_{\mathrm{cl}}(G)\cong \mathcal{B}(G,M,I) \cong \mathcal{P}_{\mathrm{cl}}(M).$

#### The ordering on concepts

The set of all concepts $\mathcal{B}(G,M,I)$ has a natural partial order on it given by the notion of a subconcept. For instance, ‘limbed, water-dwelling animal’ is a subconcept of ‘limbed animal’, and it consists of the following $(\{ \text {bream},\text {frog}\} ,\{ \text {needs water to live},\text {lives in water},\text {can move},\text {has limbs}\} ).$ Clearly, a subconcept has a reduced extent (set of objects) and an increased intent (set of attributes). Formally, for concepts $(A,B),(A',B')\in \mathcal{B}(G,M,I)$ write $(A,B)\le (A',B')$ if $A\subseteq A'$, or equivalently if $B\supseteq B'$. This gives the set of concepts $\mathcal{B}(G,M,I)$ the structure of a poset.

You can look back to the top to see a picture of the poset structure on our example.

In fact, the set of concepts $\mathcal{B}(G,M,I)$ is a *lattice* meaning that each pair of concepts has a greatest lower bound and a least upper bound. Given two concepts $(A,B)$ and $(A',B')$ we want to find the least upper bound (or supremum). We know that any upper bound must be a superconcept of both $(A,B)$ and $(A',B')$, so the extent must contain $A\cup A'$, and the closure $I^{\ast }I_{\ast }(A\cup A')$ is the smallest closed set containing the union so must be the extent of the least upper bound thus
$\sup ((A,B),(A',B'))=(I_{\ast }I^{\ast }(A\cup A'), I^{\ast }(A\cup A')).$
However, $I^{\ast }(A\cup A')$ is the set of attributes shared by everything in the union, and this is the intersection of the set of attributes shared by the objects in $A$ and those shared by the objects in $A'$. In other words
$\sup ((A,B),(A',B'))=(I_{\ast }I^{\ast }(A\cup A'), B\cap B').$

Similarly, the greatest lower bound, or infimum, is given by taking the closure of the union of the intents. $\inf ((A,B),(A',B'))=(A\cap A', I^{\ast }I_{\ast }(B\cup B')).$

#### What has this to do with the nucleus of a profunctor?

Several of you will have realised that the relation $I$ can be viewed as a profunctor enriched in truth values, that the Galois connection is an adjunction between presheaf-type enriched categories and the concept lattice is the centre of the adjunction, i.e. the nucleus of the profunctor. I’ll explain this in more detail next time and go on to say how this point of view can be used to generalize to *fuzzy* concept analysis.

## Re: Formal Concept Analysis

Glad to see that a host here get interested in the area that I have been working on during most of my postgraduate period.

Yeah, FCA has a natural closed relationship with profunctors between quantale-enriched categories (or more generally, quantaloid-enriched categories — for FCA on fuzzy sets).

The main theory of FCA can be translated into purely categorical languages. Indeed, the Galois connection of FCA generalizes the Isbell adjunction in category theory. It is also interesting that the Galois connection in another theory in computer science, rough set theory (RST), generalizes Kan extensions in category theory. We refer to them as Isbell adjunctions and Kan adjunctions in a recent paper.