Chapitre 5 : Frequent Itemset Mining à grande échelle

Le Frequent Itemset Mining (FIM) cherche les combinaisons d’items fréquentes dans une base de transactions (analyse du panier). Ici, la base est massive.

Objectifs

À la fin de ce chapitre, vous devez pouvoir :

• Rappeler Apriori et la propriété d’antimonotonicité

• Citer les optimisations big data (PCY) et les approches distribuées (SON, Toivonen)

1. Rappel : Apriori

Note

Le FIM, le support, l’algorithme Apriori (antimonotonicité) et les règles d’association sont détaillés dans le cours de Data Mining : DM — Frequent Itemset Mining (→ DM).

En bref : un itemset est fréquent si son support (nombre de transactions qui le contiennent) atteint un seuil \(\theta\). Antimonotonicité : tout sous-ensemble d’un itemset fréquent est fréquent → on élague les candidats dont un sous-ensemble n’est pas fréquent (génération par niveaux).

2. Le défi big data

Sur des données massives, le coût d’Apriori vient surtout du comptage des paires (et du nombre de passages sur la base, coûteux si elle est sur disque distribué). D’où des optimisations et des approches distribuées.

3. Optimisations & approches distribuées (brève description)

Méthode	Idée
PCY (Park-Chen-Yu)	Utilise la mémoire libre du 1ᵉʳ passage pour hacher les paires dans des compteurs (buckets) ; un bucket non fréquent élimine d’emblée ses paires → moins de paires candidates au 2ᵉ passage.
Multistage / Multihash	Variantes de PCY avec plusieurs tables de hachage pour filtrer encore plus de paires.
Échantillonnage (simple)	Faire tourner Apriori sur un échantillon tenant en mémoire (seuil abaissé) → candidats, puis vérifier sur toute la base.
Toivonen	Échantillon + negative border : garantit (sans faux négatifs) le résultat exact, quitte à refaire un passage.
SON (Savasere-Omiecinski-Navathe)	Adapté à MapReduce (voir ci-dessous) : exact, deux passages.

4. SON en MapReduce

SON repose sur le principe : un itemset globalement fréquent est fréquent dans au moins un fragment. On l’implémente en deux jobs MapReduce :

• Job 1 — candidats. Map : sur chaque fragment (chunk) de la base, trouver les itemsets fréquents localement (seuil proportionnel \(p\cdot\theta\)) et les émettre comme candidats. Reduce : dédupliquer la liste des candidats.

• Job 2 — comptage global. Map : pour chaque transaction, émettre (candidat, 1) pour les candidats qu’elle contient. Reduce : sommer ; garder ceux dont le support global ≥ \(\theta\).

Résultat exact, en deux passages, parfaitement parallélisable. (C’est l’esprit du TP3 + du TP4 projet « FIM distribué ».)

Exercices

Exercice 1 — Principe de SON

Pourquoi un itemset globalement fréquent est-il nécessairement fréquent dans au moins un fragment ? (raisonnez par l’absurde)

▶ Voir la correction

Si la base est découpée en fragments de fraction p et qu’un itemset a un support local < p·θ dans chaque fragment, alors en sommant sur tous les fragments son support global serait < θ : il ne serait pas fréquent globalement. Par contraposée, s’il est fréquent globalement (≥ θ), il dépasse le seuil local dans au moins un fragment. SON ne produit donc aucun faux négatif.

Exercice 2 — PCY

En quoi PCY réduit-il le nombre de paires candidates par rapport à Apriori, et qu’exploite-t-il pendant le premier passage ?

▶ Voir la correction

Pendant le 1ᵉʳ passage (comptage des items), PCY exploite la mémoire libre pour hacher chaque paire vue dans des buckets et compter les buckets. Au 2ᵉ passage, une paire n’est candidate que si ses deux items sont fréquents et si son bucket est fréquent. Les paires tombant dans un bucket non fréquent sont éliminées d’emblée → beaucoup moins de candidats à compter.