Formal concept analysis.

The table below lists five airlines down the side and nine destinations across the top, with a cross wherever an airline serves a destination. The cells hold only crosses. For the next two sections you can read the table like any spreadsheet with ticks in the cells.

	Latin America	Europe	Canada	Asia Pacific	Middle East	Africa	Mexico	Caribbean	USA
Air Canada	×	×	×	×	×	·	×	×	×
Air New Zealand	·	×	·	×	·	·	·	·	×
Nippon Airways	·	×	·	×	·	·	·	·	×
Ansett Australia	·	·	·	×	·	·	·	·	·
Austrian Airlines	·	×	×	×	×	×	·	·	×

Reading a table like this, you compare rows without being asked to. Air New Zealand and Nippon Airways turn out to have identical rows, and every airline in the table serves Asia Pacific. The instinct is to group rows by the columns they share, and to notice when a group cannot be made any bigger.

FCA makes that instinct precise and then draws the result. The boxed equations on this page are the field’s formal definitions. Each box is followed by a sentence in plain English that says the same thing, so you can skip the boxes and lose only the notation.

FCA has its own names for the parts of the airlines table. The rows are objects (here, the five airlines) and the columns are attributes (here, the nine destinations). The crosses form an incidence relation, which is the formal name for the yes-or-no answer in each cell. For example, Air Canada serves Mexico, so there is a cross where its row meets that column; Air New Zealand does not, so there is none.

In mathematical terms the table is written $𝕂=(G,M,I)$, where the three letters are its parts: $G$ is the set of objects, $M$ the set of attributes, and the relation $I$ says which object has which attribute. The letters come from German: $G$ for Gegenstände (objects) and $M$ for Merkmale (attributes). The field uses the same letters in every language it is written in.

The airlines table already has a yes or a no in every cell, but real datasets do not arrive as crosses. They contain numbers, dates and categories with six values, none of which is a yes or a no, so each has to become yes-or-no columns first. A price could get a column for each value, one for €199 and another for €249, but that makes a column for every price in the data and tells you nothing. Instead, the number becomes a question, such as “under €200”, or a column for each of three price bands. Choosing those questions is called conceptual scaling, and it has a literature of its own. In my experience it is also where most of the work in a real project goes.

Once every cell is a yes or a no, the triple $𝕂$ is called a formal context: a set of objects, a set of attributes and the relation between them. From here on the airlines table is a context, and the rest of the page works only on contexts.

The next two sections show how the rows of a context are grouped. The groups are computed from the crosses alone, so two people who start from the same table always end up with the same groups.

Take Air Canada and Austrian Airlines. Both serve the USA and Europe, so a first guess at what they have in common is those two destinations. However, the guess is incomplete, because both airlines also serve Canada, Asia Pacific and the Middle East. “The destinations they share” therefore needs a sharper definition: a pair of airlines shares many sets of destinations, and only one of those sets leaves nothing out.

So the operation runs in two directions, and each direction sweeps the whole table and takes everything that qualifies. From a set of airlines, collect the destinations that every one of them serves. From a set of destinations, collect the airlines that serve every one of them.

Those two directions are the context’s derivation operators. In mathematical terms both are written with the same prime mark after a set, as in $A\prime$, and which one you get depends on which side of the table the set comes from.

Prime a set of objects and you get the attributes they all have; prime a set of attributes and you get the objects that have all of them. Everything else on this page comes from applying the two operators twice.

If you write queries, the second direction is already familiar: “give me every row that has all of these” is a WHERE clause with its conditions joined by AND. The derivation gives the same kind of exact answer, except that one pass is not enough.

Apply one direction and then the other, and you reach a stopping point. Start with a set of airlines, collect the destinations they all serve, then collect every airline that serves all of those: you come back with at least the airlines you started with, and usually more. Apply the pair a second time and you get the same two sets back. A concept is a pair that has already reached that point: a set of objects and a set of attributes, each of which derives exactly the other.

The extent is the set of objects and the intent is the set of attributes, and every concept on this page is written as one of each.

Closure, twice#

Let’s walk it once, on the pair the last section left open. Start with Air Canada and Austrian Airlines. Collecting what both of them serve gives five destinations rather than the two of the first guess: Europe, Canada, Asia Pacific, the Middle East and the USA. Now go back the other way and collect every airline that serves all five. The result is the same two airlines, because no other airline in the table serves the Middle East and Canada as well as the rest. Both sets came back unchanged, so the pair is a concept.

If Africa is added to the five destinations, the airlines shrink to Austrian Airlines alone. Similarly, if Nippon Airways is added to the two airlines, the destinations shrink to Europe, Asia Pacific and the USA. This is what it means for a concept to be maximal in both directions at once: neither the extent nor the intent can grow without the other shrinking.

Here the comparison with a query stops helping. A query answers once: ask which airlines serve Europe and the USA and you get a list. The derivation goes further. It asks what the airlines on that list have in common, which returns more destinations than you asked for, then asks which airlines serve all of those, and repeats until neither set changes. Whatever condition you start from, the pair it stops at is a concept of the table.

The figure below runs those two steps on a single cross. Click on any cross to run them on that one instead: step 1 lights every destination the airline serves, and step 2 lights every airline serving all of them. The lit cells always land as a rectangle, and a third pass never changes anything.

	Latin America	Europe	Canada	Asia Pacific	Middle East	Africa	Mexico	Caribbean	USA
Air Canada	×	×	×	×	×	·	×	×	×
Air New Zealand	·	×	·	×	·	·	·	·	×
Nippon Airways	·	×	·	×	·	·	·	·	×
Ansett Australia	·	·	·	×	·	·	·	·	·
Austrian Airlines	·	×	×	×	×	×	·	·	×

1. step 1 /Air New Zealand serves 3 destinations
2. step 2 /4 airlines serve all 3

extent /

4 objects

Air Canada · Air New Zealand · Nippon Airways · Austrian Airlines

intent /

3 attributes

Europe · Asia Pacific · USA

read: no other airline serves all 3, and no other destination is served by all 4, so neither half can grow.

close another block

Every concept in this table has that shape. For example: Air Canada, Air New Zealand, Nippon Airways and Austrian Airlines all serve Europe, Asia Pacific and the USA. No fifth airline serves all three of those destinations, and no other destination is served by all four of those airlines, so the block cannot grow in either direction. The next section draws all of the table’s concepts at once.

The airlines table has six concepts, found by running the closure on every set of airlines and keeping the pairs that come back unchanged. Order them so that one concept sits below another when every object in its extent is also in the other’s, and the six fall into a diagram. Each node is a concept, and each line is a step from a concept to the next one above it.

If you have drawn a class hierarchy, you can already read most of this diagram. Higher nodes are more general and lower ones more specific, and a node can have more than one parent. The difference is that this diagram was computed from the crosses. A hand-drawn hierarchy usually lacks one property that the computed diagram has: every pair of nodes has exactly one nearest common ancestor and exactly one nearest common descendant. This property makes the diagram a lattice rather than a tree or a general graph.

Every name in the diagram appears exactly once. Each airline is written at the lowest node whose extent contains it, and each destination at the highest node whose intent contains it. To read a node’s extent, follow every path downward from it and collect the airlines you pass; to read its intent, follow the paths upward and collect the destinations. Both the labelling and this way of reading it are in Wille’s 1982 paper. For example, the top node collects one destination, Asia Pacific, which says that every airline in the table serves it. Tracing up from Air New Zealand collects Europe, Asia Pacific and the USA, which is that airline’s whole row.

Here is the airlines table again, with the lattice it produces. Click on a cell to add or remove its cross and the lattice redraws; hover over a node, or move to it with the keyboard, to see its extent and intent below.

	Latin America	Europe	Canada	Asia Pacific	Middle East	Africa	Mexico	Caribbean	USA
Air Canada	×	×	×	×	×	·	×	×	×
Air New Zealand	·	×	·	×	·	·	·	·	×
Nippon Airways	·	×	·	×	·	·	·	·	×
Ansett Australia	·	·	·	×	·	·	·	·	·
Austrian Airlines	·	×	×	×	×	×	·	·	×

6 concepts

extent /

5 objects

Air Canada · Air New Zealand · Nippon Airways · Ansett Australia · Austrian Airlines

intent /

1 attribute

Asia Pacific

read: the top concept: every airline is here, and the intent is what all of them share.

In mathematical terms the diagram is called the concept lattice, and the notation distinguishes having the concepts from having them in order.

Plain 𝔅 is the set of concepts; underlined, it is that set with the order on it. The order turns a list of six pairs into a diagram in which a node’s position tells you what it contains. Wille’s 1982 paper gives the theorem: the ordered set is always a lattice, and a complete one. Complete means that every collection of concepts has a single nearest ancestor and a single nearest descendant, and not only every pair of them. The theorem holds for every context, whatever its shape.

A single cross can change the diagram. Air New Zealand and Nippon Airways share a node because their rows are identical. Give Air New Zealand one more destination, say Canada, by clicking that cell, and the two separate. A new concept appears, with Air Canada, Air New Zealand and Austrian Airlines in its extent and Europe, Canada, Asia Pacific and the USA in its intent. The diagram goes from six nodes to seven.

Now take Asia Pacific away from Ansett Australia, the one cross in its row. The count stays at six, but the top node loses its label: no destination is shared by all five airlines any more, so the intent of the top concept is empty. The top node always stands for whatever the whole table has in common, and that can be nothing at all.

The pair at the centre of all this, an extent and an intent, is far older than any computer. Traditional philosophy already held that a concept has exactly those two parts: the things that fall under it, and the properties those things share. Ignatov’s introduction to FCA traces the pairing to the Logic of Port Royal in 1662, and notes that the modern terminology standard (ISO 704) still defines a concept as a unit of thought with the same two parts. Neither the philosophers nor the standard gave a way to compute a concept. “Everything that falls under this concept” is not a set anyone can write down, because it has no boundary, and an algorithm needs something finite to run over.

Rudolf Wille supplied the finite starting point in 1982, in “Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts”. His complaint was that lattice theory had drifted out of reach of the people who might use it. The remedy he proposed was to start from a fixed context, which says in advance which objects and which attributes are in play, and to let the concepts follow from the crosses. The context supplies the boundary that the philosophical definition lacks, because a concept’s extent can only hold objects that are in the table.

The approach reported here goes back to the origin of the lattice concept in nineteenth-century attempts to formalize logic, where a fundamental step was the reduction of a concept to its “extent”. We propose to make the reduction less abstract by retaining in some measure the “intent” of a concept.

— Rudolf Wille · Restructuring Lattice Theory · 1982

Everything above is in that paper: the triple ($G$, $M$, $I$), the two primes, the pair that comes back unchanged, and the theorem that the concepts of any context form a complete lattice. The definitions are unchanged since 1982, while the tables they are applied to have grown, and the next section is about what that growth costs.

Six concepts from five airlines is a small number, and it is not the general case. In the worst case the number of concepts grows exponentially with the size of the table, and even for a table this size the bound allows 2⁵ = 32. Five airlines is the smaller of the two sides, so the exponent is five.

To see that the bound can be reached, take six objects and six attributes, and put a cross everywhere except on the diagonal, so that each object has every attribute except its own.

	a	b	c	d	e	f
1	·	×	×	×	×	×
2	×	·	×	×	×	×
3	×	×	·	×	×	×
4	×	×	×	·	×	×
5	×	×	×	×	·	×
6	×	×	×	×	×	·

Every one of the 2⁶ = 64 subsets of those objects is the extent of a concept, so the diagram has 64 nodes and reaches the bound exactly. No real collection has every object missing exactly its own attribute, which is why its rows are numbered and its columns lettered. The shape is called a contranominal scale, and it is useful because it tells you what your own table would have to contain to behave this badly.

Albano and Chornomaz proved that the largest contranominal scale inside a table limits how many concepts the table can have. Say the largest one in your table has six rows. Then your table has at most as many concepts as there are ways of choosing six rows or fewer from the whole table. That number still grows with the table, but nowhere near as fast as doubling with every row you add. The bound also works in reverse, which is the more useful direction: a table with more concepts than that has a larger contranominal scale somewhere inside it. So the question to ask of your own data is how much of that pattern it contains.

Real tables are not built on a diagonal, so the next one holds real data. Twelve data stores (databases, caches and search engines) run down the side, and nine of their capabilities run across the top. Every cell was read from that engine’s own documentation against a stated test, so the table can be checked: sharding means one dataset partitioned across nodes, acid means documented ACID transactions across more than one operation, and oss-licence means the current release is OSI-licensed or public domain. The table is also a snapshot, and any of these engines could ship a release next month that changes a cell.

The figure below shows that table and its lattice. Some of the concepts cover a single engine and some cover all twelve. The share of the objects that a concept’s extent covers is called its support, and keeping only the concepts whose support reaches a chosen level, while setting the rest aside, is called pruning. Drag the slider to raise that level, and fewer concepts survive it.

	sql	embedded	columnar	in-memory	replication	sharding	acid	full-text	oss-licence
PostgreSQL	×	·	·	·	×	·	×	×	×
MySQL	×	·	·	·	×	·	×	×	×
SQLite	×	×	·	·	·	·	×	×	×
DuckDB	×	×	×	×	·	·	×	×	×
ClickHouse	×	·	×	·	×	×	·	×	×
MongoDB	·	·	·	·	×	×	×	×	·
Redis	·	·	·	×	×	×	·	×	×
Cassandra	·	·	·	·	×	×	·	·	×
Elasticsearch	·	·	·	·	×	×	·	×	×
Neo4j	·	×	·	·	×	·	×	×	×
Oracle	×	·	×	·	×	×	×	×	·
SQL Server	×	·	×	·	×	·	×	×	·

minimum support /

0 of 12 engines

nothing pruned · all 40 concepts

minsupp = 0.50 · 13 of 40 concepts kept · the bottom concept is gone

extent /

12 objects

PostgreSQL · MySQL · SQLite · DuckDB · ClickHouse · MongoDB · Redis · Cassandra · Elasticsearch · Neo4j · Oracle · SQL Server

intent /

0 attributes

none

read: the top concept: its extent covers 12 of 12 engines.

The table has forty concepts, against a bound of 2⁹ = 512: nine capabilities is the smaller of the two sides, so the exponent is nine. Sixty of its 108 cells carry a cross, so the table is 56% full, and it is still nowhere near the worst case. The reason is the one the contranominal scale predicts: real capabilities are correlated. For example, engines that embed do not shard, and correlations like that work against the diagonal pattern, which is why curated comparison tables do not explode.

A class hierarchy written by hand is only as large as its author had reason to make it, so it never comes near this bound. A concept lattice is computed from the crosses, and the table alone sets its size. Pruning is one way of dealing with a lattice too large to read.

The concepts that survive pruning have a name of their own, the iceberg lattice: they sit at the top of the diagram, as the visible tip of an iceberg sits above the water. The iceberg lattice has one parameter, the minimum share itself.

At a threshold of six engines out of twelve, forty concepts become thirteen. What survives is the general structure (the combinations of capabilities that many engines share), and the combinations held by only a few engines are set aside.

While the figure prunes, watch the columns rather than the rows. Attributes fade and objects never do, because support counts objects. An attribute survives exactly when its column has at least the threshold number of crosses, while every object survives because the top concept’s extent contains all of them. in-memory is the first to go, at two engines, and full-text is the last, at eleven.

Pruning does not change the table. No cross is removed and no engine is dropped, so the context is the one you started with, asked a stricter question. The columns below the threshold therefore fade instead of disappearing, and moving the slider back restores them.

Despite its name, an iceberg lattice is in general not a lattice. Pruning always keeps the top concept, whose extent is every engine, and drops the bottom one as soon as the threshold removes anything at all. What survives therefore has one node at the top and several at the bottom.

A lattice gives every pair of nodes exactly one nearest common ancestor and exactly one nearest common descendant. Two of those bottom nodes can have no common descendant at all, so half of that guarantee is lost. Stumme and his colleagues, who introduced iceberg lattices, say so, calling the result “an order filter of the whole concept lattice, and thus in general only a join-semi-lattice”.

Their paper gives the name to the set of surviving concepts, which is what the figure above draws. Only afterwards does it add a node at the bottom to make the set a lattice again. That node is the full set of attributes, which in general falls below the threshold, and it is added so that a single algorithm can compute both the full lattice and the iceberg.

Data mining arrived at the same lattice from the other side, and gave every part of it a different name. A transaction database is a formal context: the transactions are the objects, the items are the attributes, and a cross means that the transaction contained the item. A closed itemset is a set of items you cannot add to without losing transactions. In that literature’s own notation, the closure that defines it is c(X) = i(t(X)): map the itemset to the transactions that contain it, then map those transactions back to the items they all share, which is the double derivation written with different letters.

The frequent closed itemsets of a database are therefore exactly the intents of its iceberg lattice, and the two fields reached that point by borrowing from each other. Pasquier and his colleagues, in their 1999 paper on frequent closed itemsets, build the itemsets on the same closure and note that the lattice they form is the concept lattice turned upside down. In the other direction, the iceberg lattice takes support pruning from data mining, where it is the operation that makes association-rule mining tractable.

The vocabulary maps term for term: intent to closed itemset, minimum support to minimum support, and the rules a lattice lets you read off (if every object carrying these attributes also carries that one) to what mining calls an association rule at 100% confidence, meaning a rule the data never contradicts.

In-Close ↗ is one of the concept miners that compute frequent closed itemsets at scale, and it takes a minimum support for objects and another for attributes. The program can also write out a reduced context: a smaller table with the rows and columns below the threshold deleted. However, a reduced context is not an iceberg. Pruning leaves the table alone and keeps the concepts above the line, while deleting rows and columns makes a new, smaller table. The lattice of that new table is larger than the iceberg you pruned to, because the threshold still has to be applied to it.

The airlines lattice holds rules as well as concepts. For example, every airline that serves Africa also serves the Middle East. Rules of this kind are called implications, and a minimal basis of them can be computed instead of found by eye. The table itself has to come from somewhere, and when nobody has tabulated the domain, attribute exploration builds it: the algorithm proposes an implication, a person confirms it or supplies a counterexample, and the table is built from the answers. Every table on this page has two dimensions; triadic concept analysis adds a third, conditions, so that a concept says who has what under which circumstances.

My own research is on the input side of FCA. My thesis, “Appropriating Data from Structured Sources for Formal Concept Analysis”, is about the step covered in a single paragraph under objects and attributes: turning data that was collected for some other purpose into a formal context. That means deciding which objects to include and how to interpret each attribute, and then turning every value into a yes or a no. FcaBedrock, on projects →, is the tool that does that conversion. The decisions are written down once, in a file called a Bedrock spec, and FcaBedrock applies them to structured data such as a CSV file. The same data and the same spec always produce the same formal context, so an analysis can be repeated or shared.

The lattice on research → applies the same method to a table of tradable instruments instead of airlines. The method is the same for both, because FCA reads only crosses, and a cross does not say what it is about. Everything the lattice shows depends on the decisions made when the table was built, and those decisions are the part I work on.

1. Stumme and colleagues define support on an attribute set, as the share of objects carrying all of it, and call a concept frequent when its intent is frequent. The box above puts the same number on the extent instead, because at that point you have met concepts as pairs but not yet itemsets. The two definitions agree exactly: the objects carrying the intent are $B\prime$, and $B\prime$ = $A$. ↩