Exploration de règles d'association (Apriori)
- Introduite par
- Rakesh Agrawal & Ramakrishnan Srikant
- Année
- 1994
- Type
- Unsupervised pattern discovery algorithm
- Famille
- Pattern mining
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
L'exploration de règles d'association est une technique non supervisée d'exploration de données qui découvre des motifs de cooccurrence parmi des éléments dans des ensembles de données transactionnelles.
Introduite formellement par Agrawal, Imieliński et Swami en 1993, et affinée avec l'algorithme phare Apriori par Agrawal et Srikant en 1994, elle identifie des règles de la forme X ⇒ Y — signifiant que les transactions contenant l'ensemble d'éléments X ont tendance à contenir également l'ensemble d'éléments Y — quantifiées par le support, la confiance et le lift.
L’intuition derrière la méthode
Imaginez un journal de reçus de supermarché : si des milliers de clients qui achètent du pain et du beurre achètent aussi du lait, ce motif mérite une attention particulière. L'exploration de règles d'association fonctionne comme un bibliothécaire méticuleux qui parcourt chaque reçu, compte la fréquence à laquelle les combinaisons d'articles apparaissent ensemble, et met en évidence les combinaisons qui dépassent une fréquence minimale. Une fois les groupes fréquents trouvés, l'algorithme demande : étant donné que vous avez déjà ces articles, dans quelle mesure cela prédit-il le prochain article ? Cette logique en deux passes, fréquence puis confiance, est le cœur d'Apriori.
Histoire
L'article fondateur par Agrawal, Imieliński et Swami (1993) a défini le problème des règles d'association dans le contexte des données de transaction de supermarché. L'article de 1994 de Agrawal et Srikant dans VLDB a introduit l'algorithme Apriori et sa stratégie d'élagage efficace, rendant le minage à grande échelle pratique. Des travaux ultérieurs ont produit FP-Growth (Han et al., 2000), qui évite entièrement la génération de candidats, et ECLAT, qui mine au format de données vertical — établissant une famille algorithmique riche désormais centrale dans les cursus d'exploration de données.
Quand l’utiliser
L'exploration de règles d'association convient aux grands ensembles de données transactionnelles où l'objectif est de découvrir des motifs de cooccurrence sans variable cible prédéfinie. Elle suppose que les éléments sont binaires (présents/absents) par transaction. Elle est appropriée pour l'analyse du panier d'achat, les systèmes de recommandation, l'analyse des flux de clics Web et la découverte de co-diagnostic médical. Elle n'est pas adaptée aux données continues ou ordinales sauf si elles sont pré-discrétisées, aux ensembles de données de très haute dimensionnalité (espace candidat exponentiel), ou lorsque l'inférence causale plutôt qu'associative est requise. Les alternatives incluent FP-Growth pour une énumération plus rapide des ensembles d'éléments fréquents et le séquençage des données lorsque l'ordre temporel est important.
Limites et points d’attention
- Espace candidat exponentiel : le nombre de règles augmente de manière combinatoire avec le nombre d'éléments distincts.
- Le cadre support-confiance peut produire des règles trompeuses lorsque les taux de base des éléments varient considérablement (ajustement par lift requis).
- Le modèle de transaction binaire nécessite la discrétisation des variables continues, introduisant une perte d'information.
- Des seuils de support minimum élevés manquent des règles rares mais précieuses ; des seuils bas génèrent des milliers de règles triviales.
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Entièrement non supervisé : aucune donnée étiquetée ou cible prédéfinie nécessaire.
- Sortie interprétable : les règles sont des énoncés si-alors lisibles par l'homme avec support et confiance quantifiés.
- Évolutif via l'élagage Apriori ; la variante FP-Growth élimine complètement les analyses répétées de la base de données.
- Agnostique au domaine : appliqué dans la vente au détail, la santé, l'analyse Web et la bio-informatique.
Applications
- Vente au détail : placement de produits et recommandation de ventes croisées à partir des journaux de transactions de points de vente.
- Santé : analyse de cooccurrence de diagnostics, procédures ou médicaments dans les dossiers de santé électroniques.
- Analyse Web : découverte de motifs de clics pour la recommandation de pages et l'optimisation de la navigation.
- Bio-informatique : identification d'ensembles de gènes co-exprimés et de motifs d'interaction protéique.
- Cybersécurité : détection d'événements réseau corrélés indiquant des motifs d'intrusion.
Comment ça marche
Comment ça marche
L'algorithme parcourt la base de données transactionnelle D pour compter la fréquence d'apparition de chaque ensemble d'éléments X. Un ensemble d'éléments est déclaré fréquent — et placé dans L_k — uniquement lorsque son support (la fraction des transactions qui le contiennent) atteint ou dépasse le seuil de support minimum défini par l'utilisateur σ_min. Le processus commence avec des éléments individuels (k=1) et construit itérativement des ensembles candidats plus grands.
Formule
L_k = \{ X \subseteq I \mid |X| = k,\; \text{support}(X) = \frac{|\{t \in D : X \subseteq t\}|}{|D|} \geq \sigma_{\min} \}La propriété anti-monotone du support stipule que tout sous-ensemble d'un ensemble d'éléments fréquent doit lui-même être fréquent. Apriori exploite cela en élaguant chaque ensemble candidat de k éléments dont les sous-ensembles (k-1) ne sont pas tous dans l'ensemble fréquent vérifié L_{k-1}. Cela réduit considérablement l'espace de recherche, en évitant les analyses coûteuses de la base de données pour les ensembles d'éléments qui ne peuvent pas être fréquents.
Formule
\forall X \in C_k,\; \forall Y \subset X,\; |Y| = k-1 : Y \notin L_{k-1} \Rightarrow X \notin L_kÀ partir de chaque ensemble d'éléments fréquent X ∪ Y, l'algorithme génère des règles X ⇒ Y où X et Y sont des sous-ensembles disjoints. Une règle n'est conservée que lorsque sa confiance — la probabilité conditionnelle de Y étant donné X, calculée comme support(X ∪ Y) / support(X) — atteint ou dépasse le seuil de confiance minimum γ_min. Cette étape convertit les cooccurrences brutes en énoncés prédictifs directionnels.
Formule
X \Rightarrow Y \text{ where } X \cap Y = \emptyset,\quad \text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \gamma_{\min}Les règles conservées sont classées et filtrées par lift, qui mesure à quel point il est plus probable que Y apparaisse avec X que par hasard. Lift > 1 indique une corrélation positive au-delà de l'indépendance ; lift = 1 indique l'indépendance ; lift < 1 indique une corrélation négative. Des mesures d'intérêt supplémentaires telles que la conviction et le levier peuvent affiner davantage l'ensemble de règles pour un déploiement pratique.
Formule
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)} = \frac{\text{support}(X \cup Y)}{\text{support}(X) \cdot \text{support}(Y)}Pièges courants
- Définir un support minimum trop bas submerge l'analyste de règles fallacieuses ; la sélection du seuil nécessite une connaissance du domaine ou une validation croisée.
- Confusion entre association statistique et causalité : un lift élevé n'implique pas que X cause Y.
- Ignorer la distribution de fréquence des éléments : les éléments courants dominent les règles et évincent les associations significatives d'éléments rares.
- Traiter la confiance seule comme métrique de qualité ; une règle avec une confiance élevée mais un lift faible peut ne pas être meilleure que le hasard.
Questions fréquentes
Quelle est la différence entre support, confiance et lift ?
Le support mesure la fréquence à laquelle un ensemble d'éléments apparaît dans l'ensemble du jeu de données. La confiance mesure la probabilité conditionnelle du conséquent étant donné l'antécédent. Le lift normalise la confiance par la fréquence marginale du conséquent, révélant si la cooccurrence dépasse ce qui serait attendu en cas d'indépendance. Les trois métriques sont nécessaires ensemble pour une évaluation robuste des règles.
Comment l'algorithme Apriori réduit-il le coût computationnel ?
Apriori exploite la propriété anti-monotone : si un ensemble d'éléments est inféquent, tous ses super-ensembles doivent également être inféquents. En rejetant tout candidat dont les sous-ensembles ne sont pas tous vérifiés comme fréquents, l'algorithme élague de vastes portions de l'espace de recherche avant le comptage, réduisant considérablement le nombre de passages dans la base de données requis par rapport à une énumération brute.
Quand devrais-je utiliser FP-Growth plutôt qu'Apriori ?
FP-Growth est préféré lorsque le jeu de données est volumineux et que le seuil de support minimum est bas, car il compresse la base de données transactionnelle dans une structure compacte d'arbre FP et mine les motifs directement sans générer de candidats explicites. Cela élimine les analyses répétées de la base de données complète, le rendant substantiellement plus rapide qu'Apriori sur les jeux de données denses avec de nombreux ensembles d'éléments fréquents.
Méthodes associées
Sources
Agrawal, R., Imieliński, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. ACM SIGMOD, 207–216.
Ouvrir la référence DOICopié.Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th VLDB Conference, 487–499.
Ouvrir la référence de la publicationCopié.