Machine Learning 2. Lecture 8. Association Rule Mining

What this lecture is about

Today's lecture is devoted to methods of association rule mining. It is no accident that it comes right after the logical classification algorithms: there is a strong analogy between mining association rules and searching for logical regularities — conjunctions — as we will see in a moment. But the main difference is that association rule mining is a method of unsupervised learning.

The plan is this: first I will give the problem setting, then a simple algorithm, and then a cool algorithm that is really used in practice. In general, today's lecture stands out somewhat in the whole course: it will be in the spirit of a course on data structures and algorithms. Its main topic is the FP-growth algorithm: we will work out how to implement computationally efficient association rule mining properly.

The problem setting

Definitions and notation

As usual, we have a training sample, and the objects are given by binary features — this is important. To each subset of features one can assign the conjunction of these features. There is a small liberty in notation here: by $\phi$ I will denote both the subset of features and the function of an object that is the conjunction of these features. These are two quite different mathematical objects, but there is a one-to-one correspondence between them, so they are denoted by one letter. I think you will quickly get used to this, and there will be no misunderstandings.

If the conjunction $\phi (x)$ returns one, this means that all the features from the itemset $\phi$ have the value one on the given object $x$, and we will say that the features of this itemset occur together in the object $x$. In general we will say that a feature $f$ occurs in an object $x$ if $f(x)=1$.

Next, let us look at the set of objects on which the features from $\phi$ occur together, and agree to denote the frequency of occurrence of $\phi$ in the sample by $\nu (\phi )$: it is the share of sample objects on which the features from $\phi$ occur together. One can put it this way: in the object–feature matrix a submatrix is picked out that consists entirely of ones. On the feature side we picked out the columns from $\phi$, and on the object side the rows that have only ones on this subset of features. The share of objects of this submatrix we call the frequency of occurrence, or support, of the set of features $\phi$ in the sample. If this support is large enough, we call $\phi$ a frequent itemset. Why this terminology took hold, why the columns of this matrix are now called not features but "items", we will understand in a moment from examples of practical problems.

Here is the key definition we will need today: what an association rule is. It is two subsets of features, between which one usually puts an implication: from $\phi$ follows $y$. It is a pair of disjoint itemsets such that, first, their union is a frequent itemset, that is, the support of $\phi \cup y$ exceeds some threshold $\delta$; this threshold is called MinSupp, the minimum support. In other words, $\phi$ and $y$ frequently occur together, they form a frequent itemset. The second condition: if $\phi$ occurs, then $y$ also occurs frequently. This is written by a formula very similar to the formula of conditional probability: among the objects where $\phi$ occurs, we pick out the objects where $y$ occurs together with $\phi$, and their share turns out high enough — above a confidence threshold called MinConf. These two conditions, MinSupp and MinConf, are denoted exactly so in the literature; this too has taken hold. They define the pair of itemsets that forms a rule: if we observe the set of features $\phi$ in an object, then with high probability the set of features $y$ will be observed too. And "with high probability" means that the conditional probability exceeds MinConf.

Market basket analysis

Where did such a problem come from? In the nineties, when data mining became popular, one of the problems that became very popular was market basket analysis. The problem is this. There is a huge supermarket, customers buy some goods in it, and by a basket we mean the set of goods a person has bought, at the exit from the shop. We have a set of receipts: each receipt is a transaction, one customer bought these goods together. The rows of our object–feature matrix are now in effect receipts, and the columns are goods. Clearly there can be a huge number of receipts, millions, and a large supermarket has some hundreds of thousands of goods. We really do have very big data on how people buy particular goods together.

And one can notice that there are regularities like this: people often take certain goods together. For example, if a person bought bread, then with high probability they will also buy milk; if they bought sausages, they will buy ketchup; if they bought beer, they will buy crisps. This is not an exact condition but a probabilistic one: an "if — then" rule that holds with some probability. That probability is exactly what confidence gives. Our task is to find all such cases where people buy something together, which goods are bought with each other.

A mass of applications can be found for this, to improve the sales of goods. One can optimise the placement of goods on the shelves. One can form personal recommendations: if we have an online shop, we can already make offers to a regular customer based on what is often taken together with the goods they have just put into the basket. Planning promotions, managing prices, the product range and so on.

So such a problem arose, and a story even wanders through many textbooks on data mining: supposedly in one large supermarket chain, when such a system was introduced, they discovered a regularity that on Friday evenings nappies were for some reason very often bought together with beer. And when the shelves with nappies and the shelves with beer were placed next to each other, this supposedly brought such profit across the whole chain that it almost paid for introducing the whole system. But in fact this story is made up: if it really worked, it would be in many supermarkets. And my attempt to find, through search engines, a photograph of a rack where beer and nappies stand side by side was not crowned with success. Yet there are hundreds of retellings of this story in various business courses on data mining. So it is more of an anecdote.

Association rules are logical regularities

Let us see that there is a deep analogy between these probabilistic rules and the notion of a logical regularity as we had it in the last lecture. Let me remind you: in the problem of association rule mining we had no classes; both subsets, $\phi$ and $y$, we have to find and pick out in the original set of features. But if we had classes and had to solve a classification problem, we could define for the given class $c$ the share of its own objects that the given predicate $\phi$ picks out — it may be, among other things, a conjunction. The share of objects the rule picks out is nothing other than support: it coincides by definition. And if we impose the condition that among the objects the rule picks out, the share of its own must exceed some threshold, we get the same confidence. Here $p$ is the number of positive examples of the class $c$ and $n$ the number of negative examples of the class $c$; these are exactly the same definitions as in the last lecture.

The analogy shows that association rules and logical regularities are, on the whole, exactly the same thing; the difference is in terminology. Well, and the difference, of course, is that in a classification problem $y$ is the class, and we want to pick out the objects of one class $c$, while in association rules, instead of the class $y$, there is some subset of features, a conjunction, which also has to be found. That is, there is no ready class feature given in advance. But the conditions for finding regularities, support and confidence, are the same both in searching for informative conjunctions, rule induction, as in the last lecture, and in association rules.

The APriori algorithm

Anti-monotonicity and the two stages

Now let us consider an important property that will let us build an efficient association rule mining algorithm, the property of anti-monotonicity. Take the conjunction of the features from the subset $\phi$ and add some number of features — make the itemset $\psi$ out of $\phi$. The support can only decrease. Why? Because if we take more new features into a conjunction of binary features, the set of objects on which the conjunction returns one narrows — or stays the same.

Hence the corollaries — or rather, one and the same corollary in three different formulations. If $\psi$ is a frequent itemset, then all its subsets are frequent: their support is no smaller than the support of $\psi$. If $\phi$ is not frequent, then all the itemsets that are its supersets are not frequent either: if $\phi$ occurs in too few objects of the sample, then by adding more features to $\phi$ we get an itemset that occurs even more rarely. So if we have built some itemset $\phi$ that is not frequent, it is useless to grow it: we will get no more frequent itemsets out of it. We will actively use this rule to add features to frequent itemsets gradually, getting new frequent itemsets from them. This will be the main point in the search for frequent itemsets.

By the way, if you look at the literature on association rule induction, most papers are actually about the problem of finding frequent itemsets; that is what they are called. It is the core of the association rule approach. Why? Because we will now split association rule mining into two stages.

The first stage, the hardest and most substantial, is precisely finding frequent itemsets. It is done by scanning the whole database of receipts, or transactions; this is big data, and it has to be scanned and all the frequent itemsets picked out. The second stage is building the association rules proper. When we have a frequent itemset, we can split it into two disjoint subsets and try to extract $\phi$ and $y$ from it. It will only remain to check whether the confidence condition holds: $y$ must follow from $\phi$, that is, if $\phi$ is frequent, then $y$ is frequent too. This check of all possible splits of frequent itemsets into two subsets is a very fast and efficient algorithm. It is described once, implemented once, runs entirely in main memory, and there are no problems with it. So we will look at the second stage now too, and then forget about it as a closed, solved problem, and go on to the search for frequent itemsets.

Stage 1: finding frequent itemsets

Let us look at the algorithm most often mentioned in textbooks on data mining, but never used in practice, because in practice it is slow and inefficient. But it shows the main idea of association rule mining — how it is implemented in principle. This is the APriori algorithm.

At the input we have the training sample, a binary object–feature matrix — the features are called items here — and two thresholds, MinSupp and MinConf. At the output we must get a list of association rules, that is, pairs $(\phi ,y)$, for each of which two conditions hold: MinSupp — their union must be a frequent itemset, and MinConf — the association "$y$ follows from $\phi$" must hold with a conditional probability exceeding MinConf.

As the first step we pick out all the frequent original features. Clearly a frequent itemset can be a conjunction only of features that are frequent themselves. If some item occurs rarely, it is simply useless to us, and we throw it out at once. At the very first step we build the set $G_1$ of features that are frequent, that is, satisfy the MinSupp condition.

The second step is a loop over $j$ from 2 to $n$. Remember, $n$ is the number of features; it can be large, there can be hundreds of thousands. But in fact we will never get to this $n$; we will always stop much earlier, when we stop getting frequent itemsets. This will happen much earlier for one simple reason: one can hardly imagine a large number of people who put absolutely all the goods in the supermarket into their basket. There are a few goods in a basket, well 20, well 30, and such large baskets are unlikely to contain frequent itemsets. So there is no need to fear the $n$ here.

What do we do in this loop? The main step: from $G_{j-1}$, that is, from the set of frequent itemsets of the previous iteration, we make $G_j$. We take all the itemsets from $G_{j-1}$ and try to add features to them one at a time in all possible ways — but so that the MinSupp condition holds, that is, so that frequent itemsets result again. All the new frequent itemsets contain exactly one feature more. If you recall the lecture on feature selection, the group method of data handling — which is breadth-first search — there was exactly the same idea; in effect it is the same mechanism as in feature selection. But there we called it beam search, because it was a truncated breadth-first search, while here it is a complete breadth-first search, BFS.

Further, by the principle of anti-monotonicity, the support of the set of features decreases with each addition of features, and at some point none of the itemsets will be frequent any more: we have exhausted all the frequent itemsets, and $G_j$ has come out empty. Then we exit the loop. In fact this is the normal exit from the loop; it will always be exactly this, and not on reaching $n$. That is it, we have found all the frequent itemsets. This really is very easy to do with breadth-first search.

Now it only remains to try to split each of these frequent itemsets into two disjoint parts, to divide it into a premise and a consequence, into $\phi$ and $y$. This will be done by a recursive function, called $\mathrm{AssocRules}$ here. It has three arguments. $R$ is the list of all the association rules we will build: first we set it to the empty set, and at the output we must get the result of our algorithm, the list of all association rules. Then we pass to this function all the conjunctions, that is, all the itemsets we have found in all the $G_j$. It takes $\psi$ and splits it into $\phi$ and $y$ in all possible ways; how it does this we will work out on the next slide.

Stage 2: extracting association rules

This is the second stage, building association rules from the frequent itemsets: we have found the frequent itemsets, and now we split them. At the input are $R$, the list of all association rules, to which this function will add new rules, and $\phi$ and $y$, the rule we have at this stage. Note that when AssocRules is called for the first time for a frequent itemset $\psi$, the second part is the empty set.

Then the function recursively does the following simple work. It takes one feature at a time from $\phi$, moves it into $y$, and checks whether we have got an association rule. If we have, we enter it into the list $R$ and call AssocRules once more, where $\phi$ contains one feature fewer and $y$ exactly that same feature more. So at each step we will move one more feature from $\phi$ to $y$. To do this in all possible ways, we loop over all the features from $\phi$ and try to move them to $y$ one at a time. And if after that ${\phi }^{\prime }$ — the $\phi$ from which we removed a feature — is still not a single element, one more feature can be removed from it, and we call the function AssocRules itself recursively. Note that the recursion is started only for rules that were found: if the rule ${\phi }^{\prime }\to y^{\prime }$ did not pass the confidence threshold, then moving further features from ${\phi }^{\prime }$ to $y^{\prime }$ would only reduce it, since the numerator $\nu ({\phi }^{\prime }\cup y^{\prime })$ does not change, while the denominator $\nu ({\phi }^{\prime \prime })$ for ${\phi }^{\prime \prime }\subset {\phi }^{\prime }$ is, by anti-monotonicity, no smaller than $\nu ({\phi }^{\prime })$.

So I have told you this algorithm. One small technical subtlety remains: what is this condition on the features in the loop? We go through not all the features, but only in increasing order of their serial numbers. Why is this done? To avoid repetitions, when we move from $\phi$ to $y$ first the first feature, then the second, and then try to move again — first the second, then the first, that is, in reverse order we arrange the same split of the set into two disjoint subsets. To prevent this, we always move features into $y$ in increasing order. And it does not matter how the numbering is arranged, the main thing is that there is some numbering at all: ${\mathrm{id}}_f$ is the serial number of the feature $f$ in the whole set. This is a purely technical point, so that when splitting a finite set into all possible subsets we do not go through all the possible orders of the features we move into the second subset.

Let us look once more at the APriori algorithm — I have now told it completely. It consists of two parts: the first is finding frequent itemsets, the second is splitting all the frequent itemsets in all possible ways into a premise and a consequence to form association rules. In the first part we check only support, we use only MinSupp, the threshold $\delta$, while in the second part, on the contrary, only MinConf: support is already ensured by the first part of the algorithm, and we check only the confidence condition.

Drawbacks of APriori and modifications

The main drawback of this algorithm in fact lies in the first stage. The second stage is a very simple algorithm that raises no questions. But in the first stage questions are raised by such a seemingly harmless thing as repeatedly computing the support of itemsets — this very $\nu$.

Let us estimate what $\nu$ is. Suppose we have a huge transaction database: the objects, the rows, are receipts, and the features, the columns, are the goods in the receipts. Computing $\nu$ for a subset makes us run through the whole database. And this whole database is most likely located on disk: it simply will not fit into any main memory, there may be terabytes. This was of course especially a problem a quarter of a century ago, when this problem appeared: main memory then was certainly not measured in gigabytes, as it is now. Imagine that the whole object–feature matrix is stored somehow on disk, and you need to compute this seemingly harmless quantity, the support of an arbitrary subset of features. You are forced to go to the database. And now estimate how many times you will compute this quantity for various subsets of features — and you will understand that if the data do not fit into main memory, you have no chance of computing it quickly.

Hence the idea: it would be great to devise a data storage scheme such that one could, once, in a linear pass over the transaction database, compute some compressed information about all the frequent itemsets, put this information into main memory, and then search for frequent itemsets by accessing only this compressed information. The whole question of an efficient implementation is how to build an efficient way of compressing the information about frequent itemsets so that it fits into main memory.

But before moving on to that, let us talk a little about what happens in practice with association rule mining, how these algorithms are generalised, whatever they are — APriori or more efficient ones. First, there are many different ways of solving this problem; we will now look at one of them, which is still considered the state of the art, although it was devised quite long ago. But there are alternative ways too. For example, search for frequent itemsets not over the whole database but over some relatively small random subsample, but lower the MinSupp and MinConf thresholds, find more rules than needed, and then simply recheck them once on the whole full transaction database — indeed in one pass. This can be done too, but it is not guaranteed that all the association rules according to the definition with MinSupp and MinConf will be found.

What else happens? Consider a real situation: you want to find the regularity that milk is often bought with bread. Clearly by bread we can mean quite different product positions in the shop. What is an item? Each kind of bread is a separate item; each way of packaging — for example, half a litre of milk and a litre of milk, although it may be one producer — is two different goods, two different items. It is quite clear that in this rule you do not care which bread exactly or which milk exactly, and you must find this regularity not at the low level of items but at higher levels of the product hierarchy. This hierarchy always exists: bread is an internal vertex of the tree, it splits into bread from different producers, then into bread in different packaging, and so on; the same applies to other goods. One has to find association rules involving not only the lowest, terminal items but also any internal vertices of this tree. That is, we build a conjunction out of disjunctions, as it were: at the lower level we can say that $x$ is one of 30 kinds of milk or one of 50 kinds of bread. Building such more complex constructions is actually not hard, on the contrary, it is simpler: you go down the hierarchy from the top and gradually find more and more specialised rules — first more general ones, at the level of product categories, and then at the level of the goods themselves.

Further, in this problem there are all kinds of incremental algorithms that can, for example, take today's transaction database, add this portion of data to the existing data, and rebuild the association rules. Probably not all the rules will change; most will remain even with the newly arrived information taken into account, but new ones may form. And on the other hand, data become outdated: by adding today to the data, we remove from them some day that was three months ago. So we move over the data with a sliding window, and it matters to us not only to add new portions of data but also to remove old ones. It turns out that both increment and decrement must be performed, and the association rules must be rebuilt as this happens.

The FP-growth algorithm

Well then, enough talk; let us move on to really interesting algorithms and the interesting mathematics used here. The idea will be this. We will build a data structure called the prefix tree of frequent itemsets, the FP-tree (FP stands for frequent pattern). By construction it will contain all the information about all the frequent itemsets, but it will be a structure that is easy to fit into main memory: it will be small. And most importantly, we will build this structure in one linear pass over the transaction database, and after that we will no longer access the database at all. Everything we want to know about frequent itemsets will be laid down in this structure, although in some non-trivial way: to get information about a frequent itemset, a specialised query to this structure is needed, and we will understand how it is arranged.

Stage 1: building the prefix FP-tree

First of all, let us work out how this structure is built. The first step: we order all the features by decreasing support, and those that do not pass the MinSupp criterion are simply discarded.

Let us turn straight to an example. Shown here is a matrix: the rows are receipts, the columns are goods; objects in the rows, features in the columns. I denote each item by a little letter: if the item occurred in the receipt, the letter stands there, and if it did not, a dash. For example, someone bought the items $a$, $d$ and $f$, and so on; we see how these goods were bought together. To be concrete, let us agree that in our example the support threshold is three objects, $\delta =3/\ell$. We see at once that then the features $f$ and $g$ are not frequent: $f$ occurred only twice, $g$ only once. We cannot build any frequent itemsets involving these features, so we throw $f$ and $g$ out of consideration at once.

Next, let us agree on how to represent the rows of this matrix. Since the matrix is very sparse, it is convenient to regard the rows of this matrix not as binary vectors with a large number of zeros but as sequences of letters: the letters denote features. We also agree that we have sorted all the features by decreasing support. When we represent a sparse binary vector by a word made of letters, the first place will always be taken by the most frequent letter. One can see that the column $d$ is the most frequent, it occurs almost everywhere, so the letter $d$ will always stand in first place if it is present. From $a,d,f$ we get $d,a$: we threw out $f$ because it does not have the support. The next word, $a,c,d,e$, turns into $d,c,a,e$ after reordering. Here are these words, and in each word the letters are ordered by decreasing support: $d,b,c,a,e$.

Next we will take all the rows of this matrix in turn and pack them into a very efficient data structure — that very prefix tree. How is it arranged? First, the number of levels of this tree equals the number of features, and the levels from top to bottom are in exactly the same order, by decreasing support of the features: $d,b,c,a,e$. The numbers on the left show how many times the given letter occurred in the whole database.

I said "in one linear pass", but in fact there are of course two passes over the database here: the first pass simply gives us the support of each feature. But we consider that the first pass is done while the database itself is being formed. These counters can be computed like this: as soon as a new record appears in the database, we add ones to the counters of all its features. So the columns of the matrix can be ordered by feature at any moment; we get this for free while the database is formed. So we can consider that the first pass is forming the database, and the second pass is the one we will now make to build the FP-tree from the database. At this moment we already have information about the supports of all the individual features.

Let us go on. The first word is $d,a$. How do we map it onto our data structure? We draw two vertices of the tree, each on its own level: each feature has its own level, and all the vertices of the given feature will live only on this level. The one means that the word occurred once. The next word is $d,c,a,e$: again we already have $d$, we add one to its counter, while $c$, $a$ and $e$ have not occurred after $d$, so we create new vertices for them, each on its own level. The next is $d,b$: $d$ has now occurred for the third time, so we do not create a vertex. The third object begins with the letter $d$, and all such objects are attached to one and the same vertex; only its occurrence counter is incremented. Next: $d$ was there, $b$ was there, $c$ has appeared — when $d,b,c$ came to us, we used the two vertices we already had and added a third.

The new word $b,c$ is the first case where an object began with a completely different vertex, $b$, and we are forced to create in effect a forest of trees: a second tree has started to grow; these will be the objects that begin with the vertex $b$. Next, $d,b,a$: $d$ was there, we increment it, it becomes five; $b$ was there, we added one; $a$ is new — we created a new vertex. Next, $d,b,e$ — one more $e$; then $b,c,e$. Then $d,c$ — the first case where a new transaction came and our tree did not grow by a single vertex: $d,c$ went along the path already in the tree, and we only incremented the counters of the vertices $d$ and $c$. And the same happened with the last $d,b,a$: $d$ was there, $b$ was there, $a$ was there, and the tree needs no growing.

The further we go, the more cases there will be where we add nothing new: new transactions come to us, and our data structure does not grow, because we keep going along paths we have already seen many times. Clearly the growth of this data structure will be substantially sublinear with respect to the growth of the transaction database. As a result, this tree structure can be kept entirely in main memory without taking up very much space.

But I claim that this structure by construction contains complete information about all the frequent itemsets. Why? Because all the time we remembered in each vertex's counter how many times we passed through it. Let us check: the sum of the counters on each level always coincides with the counter we filled in in advance for each feature. We really did go through the whole transaction database and lost nothing: the sums agree, that is, we counted each feature in each object exactly once.

Properties of the FP-tree

Let us introduce notation and at the same time realise what the properties of this FP-tree are and why it really does contain complete information about all the frequent itemsets. Each vertex of the tree we will denote by $v$. Three things are stored in a vertex. The first is a feature: one feature per vertex; moreover, all the vertices of one feature are stored on one level of the tree. Next, an internal vertex has a set of child vertices; note that the tree is not binary at all: there can be any number of child vertices — one, two, three, there are lots of such examples here. And finally, a counter is stored in the vertex.

What is this counter? Can we say that, for example, the counter $c=2$ in the vertex $c$ under $d$ is connected with some set of features? We can. If we climb from this vertex to the root of the given subtree, we get some subset of features — here $\{d,c\}$ — and the counter says how many objects went along this path, that is, how many words begin with $d,c$. This is not yet the support of the itemset $\{d,c\}$ in the whole sample: the itemset $\{d,c\}$ also occurs in the word $d,b,c$, which went along another path, through the vertex $b$. So to find out the support of an itemset, one has to collect the counters from all the paths where it occurs — we will come to this in a moment. So, the path from the root of the tree $v_0$ to the vertex $v$ I denote $[v_0,v]$, and the set of features on this path is ${\phi }_v$. The numbers in the vertices are not simple: each of them is a counter of the objects whose words begin with this path.

Some more notation: $V(T,f)$ are all the vertices of the feature $f$, that is, in fact one level of the tree; $C(T,f)$ is the total support of the feature $f$, the very number we originally wrote on the left: how many times the feature occurs in the sample. And the main property of the FP-tree built from the whole sample: it contains complete information about all the frequent itemsets. Perhaps this is not yet very obvious, although by construction we guaranteed it; let us see why the FP-tree contains information about the frequency of all itemsets and how to get this information out of it.

The support of an arbitrary itemset from the FP-tree

Suppose we have an arbitrary subset of features $\phi$ at the input. How do we compute the support of this $\phi$? Very simply. First, we mark all the features that make up our itemset $\phi$. The levels of the tree correspond exactly to the features, so a subset of features is a subset of levels in our tree. Suppose, for example, we took $\phi$ consisting of the features $c$ and $e$. Next, we pick out all the paths each of which contains all the features of this itemset: we look at where in the tree the branches are that contain all the elements of our subset at once. For example, the branch $d,b,e$ does not contain $c$, so we did not pick it out.

Now we have several branches picked out. What will the support of our subset $\phi$ be? It will be made up of the counters of the lower vertices of all such paths. Why the lower ones exactly? Note: here $e$ has a one and $c$ has a two. What is this two made of? The first word $d,c,a,e$, where $c$ and $e$ occurred together. But this two is also made by the word $d,c$, and there is no $e$ there. So to compute the support of $\{c,e\}$, we must take only the paths that contain both $e$ and $c$, and take the counters from the lower level, the level of $e$. Such is the rule: in the first step we pick out all the paths containing all the features from $\phi$, in the second we sum the counters of only the lower vertices of these paths. The claim is that after this we have found the support of the set of features $\phi$.

In this simple way the support of any subset of features can be determined from the tree. Yes, it is a computation, but not a very laborious one, because our tree is not gigantic — precisely because it is a prefix tree, which contains all the information about all the transactions rather compactly.

So we have seen that our structure, the prefix tree or frequent pattern tree, contains complete information about the frequency of all itemsets. We have understood how to build it, but so far by example. Let us turn this into pseudocode and make sure we have understood it well enough to implement it.

The FP-growth algorithm

We have two stages: the first is building the FP-tree, the second is finding all the frequent itemsets in the built tree. We will put the second stage aside for now. There will be a function FP-find that works recursively, calling itself, and does roughly what I showed: it must go through all possible subsets of the levels of this tree in some efficient way.

First let us deal with the construction, which we have already gone through by example. We go through all the objects of our sample, passing through each once — a loop over all objects. Next we take the root of the tree. By the way, although I called the vertex $d$ and the vertex $b$ roots here, there is in fact also a common root, which is not shown. When we have a forest of trees, let us join their vertices by an abstract root $v_0$ that corresponds to no feature, and always start the search from it. This is a purely technical point: $v_0$ is the common root for all these subtrees.

Now we go through all the features that occurred in $x_i$, and we go through them in decreasing order of support — which is the same as saying that we go down the levels of the tree from top to bottom. If we see a feature $f$, and on the current level of the tree under the current vertex there is no vertex with this feature — remember, when at the very beginning we looked at the word $d,a$, the first thing we did was create $d$ and create $a$ — then we create it: we create a vertex in the tree, write our feature into it, and link it with the parent vertex, that is, with the vertex we have just come from. If we are now looking at the first feature, the parent vertex is the common root $v_0$. The counter of the number of times we have passed through this vertex is zero for now, and it has no child vertices yet. And then, regardless of whether the vertex was old or has just been created, we add one to its counter. These counters can be normalised at once, or the normalisation can be computed later: we start accumulating a counter of how many times a path from the root has passed through the given vertex. That is really all: formally written in pseudocode is exactly what we have just gone through by example, transaction by transaction.

Stage 2: recursive search for frequent itemsets

Let us go on; the most interesting part is ahead: how we will go through all possible sets of features, that is, all possible subsets of the levels of our tree. What will this procedure be? It has three arguments: from the tree $T$ it finds all the frequent itemsets that contain a given frequent itemset $\phi$ and adds them to the list $R$. We will now arrange on the set of levels of this tree something like the same breadth-first search. Here we have the itemset $\phi$, and we have already realised how to compute its support from the tree quickly. Picking out a subset, we can always compute its support quickly. And then we will add to this subset of features, in all possible ways, the features that remain higher in this tree. So we need a recursive function that adds new features to a given $\phi$ in all possible ways — but only from those that are higher than the highest feature of $\phi$. This will be the way to go through the set of all subsets of the levels of the tree, that is, in essence all possible subsets $\phi$.

Example $\phi =\{c,e\}$: the itemset was chosen from the levels $c,a,e$; we will add to it only the features located higher, $d$ and $b$ (slide).

Why is it organised exactly so, why do we go through the tree from the bottom up and why in exactly this order? Because there is a very efficient way of finding a certain subtree — we will call it the conditional FP-tree — generated by all the objects on which $\phi$ already equals one. Look at this picture: we have already built $\phi$, and now we want to check whether some more features lying higher in the tree can be added to $\phi$. The features that have already entered $\phi$ determine our support: this means that we are now considering the set of transactions in which the features of $\phi$ already occur together. Imagine the whole transaction database, from which you have chosen only the objects where $\phi$ occurs. Clearly such a subset of objects is much, much smaller: each time, by adding one more feature, we greatly reduce the number of objects that contain this feature.

Let us imagine that from this set of objects, which is much smaller than the whole transaction database, we have built an FP-tree — in the same way. It too will be much smaller, very much cut down, and it is in this cut-down, or conditional, FP-tree that we will look for new features to add to $\phi$. An intermediate structure appears, called the conditional FP-tree: it is the tree that could have been built from the subsample of the objects for which $\phi$ already equals one; this is simply a definition. And we will have a very efficient way of building this conditional tree. Running ahead, I will say that the conditional FP-tree is always a subtree of our main tree: it can be made from it by discarding some vertices, and this discarding is always implemented very efficiently. Moreover, it leads to a conditional FP-tree much smaller than the original, and so the algorithm will work very efficiently.

Let us implement this idea and look at it in more detail. So, the function FP-find takes as input an FP-tree — to begin with this will be the full FP-tree, and then we will call it passing conditional FP-trees — a frequent itemset $\phi$, and a list of itemsets $R$. Our task in one iteration is to add one more feature to $\phi$ in all possible ways, and if, adding features, we still get frequent itemsets, to add them to the common list.

What do we do? We go through all the features, over the levels from the bottom up, and check whether the feature has support in the given tree: whether the itemset $\phi \cup \{f\}$ is frequent. If it is, we add it to the list. We can do this quickly, because we already know how to compute the support of an itemset from the tree: pick out a subset of levels, pick out all the paths where these features occurred, and on the lowest level sum the counters stored in the vertices. In a conditional tree it is even simpler: all its objects already contain $\phi$, and the support of $\phi \cup \{f\}$ is simply the sum of the counters of the level $f$.

So, if the itemset is frequent, we add it to the list, and now we build a new tree — the conditional FP-tree conditioned on the given feature. How we build it we will work out a little later: it is very easy to do, but it will need to be looked at in more detail. And now we find from this conditional tree all the frequent itemsets that include both $\phi$ and the feature $f$, that is, we recursively call the function FP-find, where $T^{\prime }$ is a tree substantially smaller than the original $T$, and $\phi$, on the other hand, has grown by one more feature. So the recursion will not be too deep: its depth will never exceed the number of levels in our tree, because each time we add one more feature to $\phi$.

The conditional FP-tree

Now the last non-trivial point of this algorithm: how to build conditional FP-trees quickly. By definition the conditional FP-tree is the tree we would have built if the transaction database contained only the records where $f$ equals one. But of course we will not build it anew: we will get the conditional FP-tree from the current tree, and this can be done quickly and cheaply.

Let us show by example how a conditional FP-tree is built from a given one. Here we have an FP-tree, and we want to make from it a conditional tree conditioned on the lowest feature $e$. What must we do? Look at the definition: the conditional FP-tree is the tree built from the transactions involving the feature $e$. The information about all such transactions is stored in this tree on the paths from the vertices $e$ to the root. How many such paths are there? As many as there are vertices on the level $e$: $e$ occurred three times. So we will get the conditional FP-tree if we take all the paths from the vertices of the lowest feature $e$ to the root of the tree and discard everything else.

They must be taken carefully, taking into account what the values of the counters will be. The values of the counters will change: now they must take into account only the transactions in which the feature $e$ took part. How will we do this? We will go along all these paths from the bottom up, each time passing the counter from bottom to top. The vertex $b$ will now have not a five but a one: $e$ will pass a one to this $b$. Why? Because we are interested only in the cases where $e$ occurred together with $b$. All the other four were without the feature $e$: there was $d,b$, there was $d,b,c$, there were two $d,b,a$ — together they made up the five here, and of them we are interested only in the one transaction where $e$ too was one. So $b$ in the cut-down tree will have a one. In effect we raise the counters from the lower level along the paths from the bottom up, and if paths happen to merge, the counters are summed at that point: thus ones arrive at the vertex $d$ from $b$ and from $c$, and the result is a two. After that the lower level can be removed, because we have already taken the feature $e$ into account: in a conditional FP-tree, the level of the feature it is built on is no longer there.

Let us check: does this FP-tree really contain the information about the three transactions involving the feature $e$? There were three, and they are indeed all accounted for: the counter of $d$ is two, that of $b$ is one; together they add up to three. This tree really does record complete information about all the transactions involving the feature $e$.

We have in fact come almost to the end of this really not very simple algorithm. Let us do the last thing: write in pseudocode the algorithm for building a conditional tree that we have just gone through by example. In essence there will be no loops here, three simple steps. At the input are the tree $T$ and the feature $f$, and we want to build the conditional tree $T^{\prime }$. The first step: we keep in the tree only the vertices on the paths from the vertices of the feature $f$ upward to the root. This is what we did for $e$: we found all its vertices and laid paths from these vertices to the root — thereby building the skeleton of the conditional tree. Second: we raise the values of the counters from the vertices corresponding to the feature $f$ from the bottom up and use the summation rule: if two paths meet at a vertex, we sum the values of the counters there. And the third step: all the vertices of the feature $f$ itself are removed from the conditional tree, because we have already taken them into account earlier; their supports are already counted.

Why so? We can go back to the picture with the levels. We always consider some subset of features $\phi$ and try to add to it new features that are located higher in the tree. This means that when we consider the conditional tree conditioned on the subset $\phi$, we have already taken into account all the frequent itemsets that contain these features, and we are now trying to add a new feature to all these frequent itemsets. This is simply a mechanism for going through all the subsets of the levels of this tree, and we always go through them from the bottom up.

That is the whole algorithm. Let us run through it once more in retrospect. The first thing we did was build the FP-tree in one linear pass over the transaction database. Second, we start FP-find with the full tree, $\phi$ the empty set and $R$ the empty set: we start growing frequent itemsets from scratch and start filling the list of frequent itemsets $R$. Then we go through the features from the bottom up: as soon as we have removed the lowest feature, we start adding one of the upper ones to it. In this way we gradually go through all the subsets of the levels of this tree, and that is the same as all the subsets of the set of features.

The efficiency of FP-growth

The ${\log }_{10}$ of the algorithm's running time as a function of MinSupp, compared with other algorithms (on the census data); the lower curves are two different implementations of FP-growth. Christian Borgelt. An Implementation of the FPgrowth Algorithm. 2005.

And the final plot, from a paper on the implementation of this algorithm: it shows how much faster this way of finding frequent itemsets is than simple algorithms. Here the upper curve is APriori, the lower curves are two slightly different implementations of FP-growth. On the horizontal axis is MinSupp, on the vertical the logarithm of the time needed to find all the frequent itemsets. First, clearly, as the support grows, the number of itemsets decreases and the time decreases. But note that on the logarithmic scale the time of FP-growth comes out much smaller than that of the other algorithms.

Summary

We have come to the end. A brief summary. Association rule mining is, first, a kind of logical classification algorithm based on conjunctions, only here we have classification without a teacher: which class to classify against is also built into the problem; the role of the class is played by the subsets $y$, which we also construct. The FP-growth algorithm was invented quite long ago, but in effect it still remains the state of the art and one of the fastest association rule mining algorithms. And for practical applications a great many of its generalisations have been devised — for hierarchies, for increment and decrement, and so on.

Seminar