A demystifying introduction to Formal Context Analysis (FCA)
Finding structures and rules in complex data, with example and code.
A Demystifying Introduction to Formal Concept Analysis (FCA)
Finding structures and rules in complex data.
How often does this happen? A new data repository comes up or someone points you to a nice new dataset from which you could see that there might be something interesting to do. Then you look at it, and well... it is a bunch of numbers. You can run some stats, and poke around, but what does it really mean?
Maybe formal concept analysis (FCA) can help. It might look complicated, but it is based on one rather simple idea: The one of the concept. A concept (kind of like a class in object-oriented programming) represents a set of objects that share a set of attributes. Generally, in FCA, those attributes are binary.
For example, let's say that we are looking at data about four countries, which can be big or small, and where one might drive on the left, or the right. We can represent the attributes for each of the countries in a binary matrix as below.
That matrix is what is called the formal context and we can see that concepts that make sense here include the ones of big countries, or of big countries driving on the right side. The set of objects (countries) that are included in the first one (called the extent of the concept) are country1, country2 and country3, and the second one only includes country1 and country3. The intent of each concept, i.e. the set of attributes shared is, for the former, [size:big] and, for the later, [size:big,driving:right].
There is one thing we need to add to the definition of a concept and that is at the core of FCA: Concepts have to be closed. What that means is that the set of objects in the extent should be exactly the ones that share the attributes of the intent, and the set of attributes in the intent should be exactly the ones shared by objects in the extent.
From that definition, [size:big] and [size:big,driving:right] **** are closed, but the concept [size:small] is not. Indeed, only country4 has this attribute, but it also has [driving:right]. Therefore, to make it closed, the concept has to be defined by both attributes shared by elements of the extent: [size:small,driving:right]. The same applies to [driving:left]. The closed concept in this case is [size:big, driving:left].
Now, finding closed concepts is certainly interesting, but what makes the whole thing really powerful is that those concepts are naturally organised by subsumption. Intuitively, a concept subsumes another one if it is more general. More formally, it means that its intent (attributes) are included in the other concept's intent, and its extent (objects) includes the other concept's extent. Basically, [size:big] subsumes [size:big,driving:left].
This relation of subsumption is a partial order, which means that one concept might subsume another, be subsumed by another, or neither. Therefore, all the closed concepts for a given dataset (formal context) are naturally organised in a hierarchy (a lattice), from the more general to the more specific.
Of course, for such a small example, it does not really help that much. So, let's have a look at what it does on a more significant example.
The country example, but real
To get a more realistic example, I used Wikidata to retrieve a list of countries and the information (properties) associated with them. Skipping the details (all the code for recreating the dataset is available with the basic implementation of FCA and of the example at github.com/mdaquin/fca.js), the dataset includes information from countries which had values for properties shared by more than 90% of the countries and that had either numerical values, or less than 5 unique categorical values. For each of those countries, the values of properties are transformed into binary attributes by:
For categorical properties, creating an attribute for each possible value, e.g. driving side:left (what machine learning practitioners would call one hot encoding).
For numerical properties, creating attributes for low, medium and high values based on the 33% and 67% percentiles, e.g. population:low (a very basic approach to discretization).
The result is a formal context of 147 objects (countries) and 33 binary attributes. For example, France is represented by the following attributes:
Looking at this formal context feels a bit like looking at the matrix. Columns after columns of Xs which feel kind of random, but also kind of not: There are patterns in there, so let's try to find them.
Building the concept lattice
Building the concept lattice is a complex task, but for the purpose of this example, I used a basic method. First I built all the close concepts by adding each object by its intent, and any intersection with existing concepts' intent that wasn't there already. Then I iterate over the concepts to build the subsumption relations. Finally, I populate each concept with their extent. This is far from the most efficient algorithm to do this (see this paper for a nice list of better ones) and javascript is not quite the best language for it, but on my laptop, it takes just a few minutes to complete, so it is not too bad.
The first thing to notice is that the algorithm finds 8,840 concepts. This might sound like a lot, but it is nowhere near the maximum number of concepts we could have found with that number of attributes! I guess that's the reason most tutorials and examples on FCA tend to use only very basic examples. It is not the techniques that are complicated, it is the result.
However, even if inspecting all those concepts individually would be tedious and mostly pointless work, the key thing here is that they come not as a list of sets of attributes, but through a navigational structure to explore them. Indeed, starting from the top of the lattice (i.e. the concept with no attribute as intent and all objects as extent), we can focus on the next level down for example on countries with a low life expectancy ([life expectancy:low]), to find that there are 20 subconcepts, including countries which also have a low population (14 of them). At the third level, we find only 5 possible other concepts, which in addition to low life expectancy and population, also have:
a low nominal GDP,
a high total fertility rate,
a medium mains voltage,
a low PPP GDP per capita, or
a high inflation rate
There could have been many other concepts, but that only those five are there, and that FCA is based on closed sets of attributes, mean that those other concepts simply did not exist in the data. In our list of countries, you cannot have a low life expectancy and population, and not be in one of those 5 other categories too. The lattice goes deeper into subdividing this group of countries and provides a convenient way to explore the dataset. But can it do more?
Extracting association rules
Other than providing a (rather enormous) navigation structure, the lattice once constructed can also be used to identify rules that apply in the data. The simple intuition here is that if a concept C's intent includes attributes that are not in the intent of any of its parents (i.e. subsuming concept), then those attributes imply the ones of the parents. This is again due to the fact that the concepts are closed: If C's own attributes (its proper intent) could appear without the ones of the parents, then they would have already shown up at levels above.
Unfortunately, that does not happen in our country dataset. We can, however, see when that almost happens. The support of a concept is the number of objects (countries) in its extent. For example, the support of [life expectancy: low, population: low] is 14, as seen above. If the support of a concept C is almost the same as the support of one of its parent concepts D, that must mean that the attributes of D's intent almost imply the ones of C's intent. In other words, if C has a support of 9 with the intent [a,b,c] and S, the subsuming concept, has a support of 10 with the intent [a,b], __ we can say that any object with attributes a and b also has c in 90% of the cases. We have an association rule stating that a and b imply c, with a confidence of 90% (and a support of 9).
That, our country dataset has a lot of. Only focusing on rules with a confidence higher than 95% and a support of at least 25, we can find for example the following rule:
which states that, with 96.1% confidence, countries with a high inflation rate and a high fertility rate also have a low life expectancy, and that this applies to 25 countries in our dataset.
Conclusion
There are many more applications of FCA and association rule extraction, but to me, dataset exploration and understanding is among the most significant ones. The rule above and the structure of the lattice might reflect a certain reality of the world, or might be an artefact of the way the dataset was constructed. It might say something about countries or show some bias in the data. Whichever it is, at a time when the explainability of data processes is becoming increasingly crucial, a process that can tell me "here is something that your data says" or "here is a significant pattern I have found in a corner of your dataset" is invaluable to understand the data and the results of whatever we are doing with it.
