Unsupervised Learning — Association (part 2)
Apriori, FP‑Growth, and Eclat: three ways to find patterns without drowning in millions of combinations
You already know what association rules are looking for. Now for the fun part: how on earth do they actually find them?
In the previous chapter you learned that association rules don’t group things, they connect them: they uncover which products travel together in the same basket. And you met the three judges that decide whether a rule is worth anything: support (does it happen a lot?), confidence (is it strong?), and lift (is it real or just a coincidence?).
But we left one question hanging in the air, and it’s the most uncomfortable one:
«Okay, but… how does the algorithm actually find those patterns among thousands of products and millions of baskets?»
Because doing it by hand would be, literally, impossible. And I’m not exaggerating here, let me show you why.
The problem: why «trying everything» isn’t an option
Imagine your store sells just 10 products. Sounds like nothing, right? Well, the possible combinations among those 10 products already add up to more than a thousand. Bump it up to 50 products and the combinations jump into the quadrillions. With 200 products, the number is so absurd that no computer on the planet could check them one by one before the sun burns out.
This is the famous combinatorial explosion problem: every new product you add doesn’t add options, it multiplies them. That’s why «just look at all the baskets» doesn’t work. You need clever algorithms that find the frequent itemsets (the groups of products that show up together often) without checking everything.
And that’s where our three protagonists come in. Three very different personalities, one shared goal:
- Apriori → the classic. Goes step by step and prunes whatever’s useless.
- FP‑Growth → the fast one. Compresses all the baskets into a tree.
- Eclat → the minimalist. Crosses lists and that’s it.
Let’s take them one at a time, no rushing.
Apriori — the algorithm that prunes infinity
Apriori is the oldest and easiest to understand of the three. Its idea is so simple it almost sounds like common sense, but it’s brilliant:
If a large combination is frequent, all of its smaller parts have to be frequent too. And the other way around: if a small combination is rare, any larger combination that contains it will be even rarer.
Think about it calmly: if milk + bread is something almost nobody buys together, is it worth bothering to check milk + bread + eggs? Nope. It’s going to be even less frequent. Apriori doesn’t even try. And that’s its superpower: instead of reviewing millions of combinations, it throws out entire branches in one shot.
The intuition: like someone cooking level by level
Apriori works just like someone building recipes by complexity:
- First it looks at the single ingredients. Which products are popular on their own? The ones almost nobody buys, out they go.
- Then it combines them two by two. But only using the ones that survived the previous step.
- Then three by three. Again, only with the survivors.
- And so on, moving up a level each time, tossing out anything that doesn’t reach the minimum support.
An example in our store
Let’s say we set the bar at a minimum support of 5%. Apriori first looks at the individual products and discovers that sunglasses only show up in 2% of the baskets. Goodbye: they’re out. From that moment on, Apriori will never consider any combination that includes sunglasses again (not «sunglasses + cap», not «sunglasses + sunscreen», nothing). In one stroke it just saved itself from reviewing hundreds of useless combinations. That’s pruning infinity.
| ✅ Pros | ❌ Cons |
|---|---|
| Super easy to understand | Gets slow with many products |
| Super easy to implement | Generates too many candidates along the way |
| Perfect for small or medium datasets | Scales poorly with millions of transactions |
FP‑Growth — the algorithm that compresses the universe
FP‑Growth was born precisely to fix Apriori’s weak spot: it generated too many candidates and got stuck. And its solution is a complete change of mindset:
Instead of testing combinations one by one, what if I compress all the baskets into a single structure that already reveals the patterns?
That structure is called an FP‑tree (frequent pattern tree). It’s basically every receipt in your store squeezed into a single tree.
The intuition: compress instead of enumerate
FP‑Growth does this:
- Sorts the products by popularity, from best-seller to least sold.
- Builds a tree where each branch represents a basket.
- And here’s the trick: baskets that share products share a branch. They don’t get repeated.
- Then it extracts the patterns directly from the tree, without generating endless candidate lists.
Think of it this way: if 3,000 customers bought «t‑shirt + trousers», Apriori would treat them as 3,000 cases it has to count one by one. FP‑Growth puts all of them on the same branch of the tree and moves on. It’s like compressing thousands of receipts into a ZIP file that, on top of that, already shows you the patterns when you open it.
| ✅ Pros | ❌ Cons |
|---|---|
| Much faster than Apriori | More complex to implement |
| Doesn’t generate unnecessary candidates | You need to really understand how the FP‑tree works |
| Ideal for large volumes of data | The tree can take up a fair amount of memory |
Eclat — the algorithm that crosses lists
Eclat is the most minimalist of the three. No trees, no step-by-step candidates. Its idea fits in a single sentence:
Each product appears in certain baskets. If you cross those basket lists, you instantly find what gets bought together.
Instead of reading the table «by rows» (basket by basket), Eclat flips it and reads it «by columns»: for each product it stores the list of baskets where it appears. This is called the vertical format.
The intuition: intersecting is finding
Imagine you’ve got this stored:
- t‑shirt → appears in baskets
{1, 3, 5, 8, 10} - trousers → appear in baskets
{3, 5, 8, 11}
Want to know in how many baskets they appear together? No need to run through anything fancy: you just cross (intersect) the two lists and keep what they have in common:
Three baskets. If that beats your minimum support, you’ve already got a frequent pattern. And the best part: to find trios, you just keep crossing that resulting list with the next product’s list. Pure set intersection, nothing more.
| ✅ Pros | ❌ Cons |
|---|---|
| Very fast with data in vertical format | The lists can grow enormously |
| Conceptually dead simple | Not as efficient with sparse data |
| Ideal for dense datasets | Heavily depends on the data format |
The three, side by side
Three different philosophies for the same destination. Here’s how they stack up next to each other:
| Algorithm | Its philosophy | Shines when… | Struggles when… |
|---|---|---|---|
| Apriori | Generates candidates and prunes the rare ones | You want to understand it and the dataset is small/medium | There are tons of products |
| FP‑Growth | Compresses the baskets into a tree | You have millions of transactions and need speed | You need something simple to code |
| Eclat | Crosses basket lists | The data is dense and in vertical format | The data is very sparse |
Which one do I pick? The decision diagram
So you don’t get lost when it’s time to actually decide, here’s the visual summary:
In one sentence: Apriori for learning and for small data, FP‑Growth when the volume is huge, and Eclat when your data is dense and in vertical format.
In summary
All three chase exactly the same thing (discovering which products appear together frequently), but each one does it its own way:
- Apriori prunes: it discards the rare combinations before wasting time on them.
- FP‑Growth compresses: it packs all the baskets into a tree that already reveals the patterns.
- Eclat crosses: it intersects the basket lists and finds the matches on the fly.
Three different paths, one same finish line: finding the frequent itemsets that will later turn into those handy association rules (A → B) we opened the previous chapter with. Pruning, compression, or intersection: pick your tool based on the size and shape of your data, and let the algorithm do the impossible work for you.