L'algorithme Apriori d'IBM a extrait ce que les clients achètent ensemble en élaguant les candidats impossibles

Les détaillants voulaient savoir quels produits sont achetés ensemble, mais le nombre de combinaisons d'articles possibles explosait de façon exponentielle avec le nombre de références (SKU).

Apriori, publié en 1994, exploite une propriété : tout sur-ensemble d'un ensemble d'articles peu fréquent doit lui-même être peu fréquent. Il compte les articles individuels, conserve les fréquents, les développe en paires, et répète, de sorte qu'il ne compte jamais un candidat dont le parent a déjà échoué.

L'astuce transforme une recherche qui devient rapidement ingérable en une recherche qui ne touche que la petite frontière des ensembles fréquents. Elle a fait de l'analyse du panier de la ménagère une requête de base de données pratique.

Si un ensemble est rare, tous ses sur-ensembles le sont aussi

La clôture descendante élague la recherche avant qu'elle ne croisse, de sorte que le temps d'exécution suit les ensembles fréquents, et non tous les ensembles.

Une analyse de la base de données par niveau maintient la mémoire limitée aux ensembles candidats.

Il donne des ensembles fréquents exacts, et non une heuristique ou une approximation par échantillonnage.

Le même élagage se généralise à l'extraction de séquences et de motifs au-delà des paniers.

Avant d'explorer un espace immense, cherchez une propriété monotone qui vous permette de rejeter des branches entières d'un coup. Une règle qui exclut une région réduit la recherche de l'exponentiel au linéaire.

Apriori est devenu l'algorithme canonique des règles d'association et une leçon standard en fouille de données. Il a semé le domaine qui alimente l'analyse de recommandation, d'assortiment et de vente croisée, ainsi que les méthodes ultérieures comme fpgrowth et d'autres qui réduisent ses analyses.