Règles d’Association

Découvrir les relations cachées dans vos données

Authors
Affiliation

Wilson Toussile1 2

ENSPY

1ENSPY, 2ESSFAR

Published

May 29, 2025

1 Introduction

Imaginez un supermarché. Les règles d’association cherchent à identifier les produits qui sont fréquemment achetés ensemble par les clients. Par exemple, si beaucoup de clients achètent du pain et du beurre dans la même transaction, il existe une règle d’association entre ces deux produits.

1.1 Qu’est-ce qu’une Règle d’Association ?

Definition 1 (Règle d’Association) Une règle d’association est une implication de la forme \(X \Rightarrow Y\), où :

  • \(X\) et \(Y\) sont des ensembles d’items (produits, symptômes, pages web, etc.)
  • \(X\) est appelé l’antécédent (ou prémisse)
  • \(Y\) est appelé le conséquent (ou conclusion)
  • La règle signifie que si un client achète (ou sélectionne, visite…) les items de \(X\), il est probable qu’il achète aussi les items de \(Y\).

1.2 Objectif

L’objectif principal est de découvrir des relations intéressantes et exploitables entre les items d’un jeu de données. Ces relations peuvent être utilisées pour :

  • Comprendre les comportements des clients ou des utilisateurs.
  • Prendre des décisions plus éclairées (ex: placement de produits, recommandations).
  • Optimiser les processus (ex: agencement d’un magasin, organisation d’un site web).

1.3 Importance et Applications

Les règles d’association ont de nombreuses applications dans divers domaines :

  • Marketing et Vente au Détail :

    • Analyse du panier d’achat : comprendre quels produits sont souvent achetés ensemble pour optimiser le placement des produits en magasin ou sur un site web.
    • Recommandations personnalisées : suggérer des produits complémentaires aux clients lors de leurs achats en ligne.
    • Promotions ciblées : créer des offres spéciales sur les combinaisons de produits fréquemment achetées ensemble.

  • Médecine :

    • Identification de cooccurrences de symptômes ou de gènes : aider à diagnostiquer des maladies ou à identifier des facteurs de risque.
    • Analyse des traitements : étudier les combinaisons de médicaments qui sont souvent prescrites ensemble et leur efficacité.

  • Web Mining :

    • Analyse des parcours de navigation : comprendre comment les utilisateurs naviguent sur un site web pour améliorer l’ergonomie et la structure du site.
    • Recommandations de contenu : suggérer des articles, des vidéos ou d’autres contenus en fonction des pages visitées par l’utilisateur.

  • Détection d’Anomalies :

    • Identifier des combinaisons d’événements qui sont rares ou inattendues, ce qui peut indiquer des fraudes ou des erreurs.

  • Autres Domaines :

    • Analyse des réseaux sociaux (ex: communautés d’amis).
    • Bio-informatique (ex: relations entre gènes).
    • Télécommunications (ex: services utilisés ensemble).

2 Concepts Clés Préliminaires

Avant de plonger dans les détails des algorithmes, il est essentiel de définir quelques concepts clés :

Definition 2 (Itemset (Ensemble d’Items)) Un itemset est un ensemble d’un ou plusieurs items. Un item peut être n’importe quelle entité identifiable dans une transaction (un produit dans un supermarché, un mot dans un document, un symptôme médical, etc.).

Example 1  

  • {Lait, Pain} est un itemset contenant deux items.
  • Un itemset peut aussi contenir un seul item : {Pain}

Definition 3 (Transaction) Une transaction est un ensemble d’items qui sont achetés ensemble (ou sélectionnés, visités, etc.) lors d’une même occasion. Chaque transaction représente un événement unique.

Example 2  

  • Une transaction dans un supermarché pourrait être : {Lait, Pain, Oeufs}
  • Dans un site web, une transaction pourrait être : {Page d’accueil, Page produit A, Panier, Paiement}

Definition 4 (Base de Données de Transactions) Une base de données de transactions est une collection de transactions. C’est l’ensemble des données à partir duquel nous allons extraire les règles d’association.

Example 3  

ID Transaction Items Achetés
1 {Lait, Pain, Oeufs}
2 {Pain, Beurre}
3 {Lait, Couches, Bière, Pain}
4 {Lait, Beurre, Pain}
5 {Couches, Bière}

  • Cette table représente une base de données de 5 transactions.

  • Questionnement :

    • Quels produits sont souvent achetés ensemble ?
    • Si un client achète du “Pain”, est-il probable qu’il achète aussi du “Lait” ?
    • Comment quantifier cette “probabilité” ou cette “force” de l’association ?

3 Métriques Fondamentales des Règles d’Association

3.1 Support

  • Définition : Fréquence d’apparition d’un itemset dans la base de données.
  • Formule : \[ \text{Support}(X) = \frac{\text{Nombre de transactions contenant } X}{\text{Nombre total de transactions}} \]
  • Interprétation : Popularité d’un itemset.
  • Exemple de calcul sur le jeu de données du supermarché.
    • Support({Pain})
    • Support({Lait, Pain})
  • **Support minimum (mi— title: “Règles d’Association” subtitle: “Découvrir les relations cachées dans vos données” date: today execute: echo: true warning: false —

4 Introduction

Imaginez un supermarché. Les règles d’association cherchent à identifier les produits qui sont fréquemment achetés ensemble par les clients. Par exemple, si beaucoup de clients achètent du pain et du beurre dans la même transaction, il existe une règle d’association entre ces deux produits.

4.1 Qu’est-ce qu’une Règle d’Association ?

Definition 5 (Règle d’Association) Une règle d’association est une implication de la forme \(X \Rightarrow Y\), où :

  • \(X\) et \(Y\) sont des ensembles d’items (produits, symptômes, pages web, etc.)
  • \(X\) est appelé l’antécédent (ou prémisse)
  • \(Y\) est appelé le conséquent (ou conclusion)
  • La règle signifie que si un client achète (ou sélectionne, visite…) les items de \(X\), il est probable qu’il achète aussi les items de \(Y\).

4.2 Objectif

L’objectif principal est de découvrir des relations intéressantes et exploitables entre les items d’un jeu de données. Ces relations peuvent être utilisées pour :

  • Comprendre les comportements des clients ou des utilisateurs.
  • Prendre des décisions plus éclairées (ex: placement de produits, recommandations).
  • Optimiser les processus (ex: agencement d’un magasin, organisation d’un site web).

4.3 Importance et Applications

Les règles d’association ont de nombreuses applications dans divers domaines :

  • Marketing et Vente au Détail :

    • Analyse du panier d’achat : comprendre quels produits sont souvent achetés ensemble pour optimiser le placement des produits en magasin ou sur un site web.
    • Recommandations personnalisées : suggérer des produits complémentaires aux clients lors de leurs achats en ligne.
    • Promotions ciblées : créer des offres spéciales sur les combinaisons de produits fréquemment achetées ensemble.

  • Médecine :

    • Identification de cooccurrences de symptômes ou de gènes : aider à diagnostiquer des maladies ou à identifier des facteurs de risque.
    • Analyse des traitements : étudier les combinaisons de médicaments qui sont souvent prescrites ensemble et leur efficacité.

  • Web Mining :

    • Analyse des parcours de navigation : comprendre comment les utilisateurs naviguent sur un site web pour améliorer l’ergonomie et la structure du site.
    • Recommandations de contenu : suggérer des articles, des vidéos ou d’autres contenus en fonction des pages visitées par l’utilisateur.

  • Détection d’Anomalies :

    • Identifier des combinaisons d’événements qui sont rares ou inattendues, ce qui peut indiquer des fraudes ou des erreurs.

  • Autres Domaines :

    • Analyse des réseaux sociaux (ex: communautés d’amis).
    • Bio-informatique (ex: relations entre gènes).
    • Télécommunications (ex: services utilisés ensemble).

5 Concepts Clés Préliminaires

Avant de plonger dans les détails des algorithmes, il est essentiel de définir quelques concepts clés :

Definition 6 (Itemset (Ensemble d’Items)) Un itemset est un ensemble d’un ou plusieurs items. Un item peut être n’importe quelle entité identifiable dans une transaction (un produit dans un supermarché, un mot dans un document, un symptôme médical, etc.).

Example 4  

  • {Lait, Pain} est un itemset contenant deux items.
  • Un itemset peut aussi contenir un seul item : {Pain}

Definition 7 (Transaction) Une transaction est un ensemble d’items qui sont achetés ensemble (ou sélectionnés, visités, etc.) lors d’une même occasion. Chaque transaction représente un événement unique.

Example 5  

  • Une transaction dans un supermarché pourrait être : {Lait, Pain, Oeufs}
  • Dans un site web, une transaction pourrait être : {Page d’accueil, Page produit A, Panier, Paiement}

Definition 8 (Base de Données de Transactions) Une base de données de transactions est une collection de transactions. C’est l’ensemble des données à partir duquel nous allons extraire les règles d’association.

Example 6  

ID Transaction Items Achetés
1 {Lait, Pain, Oeufs}
2 {Pain, Beurre}
3 {Lait, Couches, Bière, Pain}
4 {Lait, Beurre, Pain}
5 {Couches, Bière}

  • Cette table représente une base de données de 5 transactions.

  • Questionnement :

    • Quels produits sont souvent achetés ensemble ?
    • Si un client achète du “Pain”, est-il probable qu’il achète aussi du “Lait” ?
    • Comment quantifier cette “probabilité” ou cette “force” de l’association ?

6 Métriques Fondamentales des Règles d’Association

6.1 Support

Le support d’un itemset (ou d’un ensemble d’items) est une mesure de sa fréquence d’apparition dans l’ensemble des transactions. Il indique la popularité d’un itemset.

Définition Formelle :

Le support d’un itemset \(X\), noté \(\text{Support}(X)\), est la proportion des transactions dans la base de données qui contiennent l’itemset \(X\).

Formule :

\[ \text{Support}(X) = \dfrac{\text{Nombre de transactions contenant } X}{\text{Nombre total de transactions}} \]

Interprétation :

  • Un support élevé signifie que l’itemset apparaît fréquemment dans les transactions.
  • Un support faible signifie que l’itemset est rare.

Example 7 (Exemple de Calcul) Reprenons notre exemple de base de données de transactions de supermarché :

ID Transaction Items Achetés
1 {Lait, Pain, Oeufs}
2 {Pain, Beurre}
3 {Lait, Couches, Bière, Pain}
4 {Lait, Beurre, Pain}
5 {Couches, Bière}

Nombre total de transactions = 5.

  • Calculons le support de l’itemset {Pain} :
    • Les transactions contenant {Pain} sont : 1, 2, 3, 4.
    • Nombre de transactions contenant {Pain} = 4.
    • \(\text{Support}(\{\text{Pain}\}) = \dfrac{4}{5} = 0.8=80\%\).
  • Calculons le support de l’itemset {Lait, Pain} :
    • Les transactions contenant {Lait, Pain} sont : 1, 3, 4.
    • Nombre de transactions contenant {Lait, Pain} = 3.
    • \(\text{Support}(\{\text{Lait, Pain}\}) = \dfrac{3}{5} = 0.6=60\%\).

Support Minimum (minsup) :

Dans la pratique, on définit souvent un seuil de support minimum (minsup). Un itemset est considéré comme “fréquent” si son support est supérieur ou égal à ce seuil minsup. Ce seuil permet de filtrer les itemsets qui apparaissent trop rarement pour être considérés comme intéressants ou significatifs. Le choix de minsup est crucial et dépend du domaine et de la taille du jeu de données.

6.2 Confiance (Confidence)

  • Définition : Mesure de la fiabilité d’une règle \(X \Rightarrow Y\). Probabilité d’observer \(Y\) sachant que \(X\) est présent. La confiance d’une règle d’association \(X \Rightarrow Y\) mesure la fiabilité de cette règle. Elle indique la probabilité que l’itemset \(Y\) soit présent dans une transaction, sachant que l’itemset \(X\) y est déjà présent.

Definition 9 (Définition Formelle) La confiance de la règle \(X \Rightarrow Y\), notée \(\text{Confiance}(X \Rightarrow Y)\), est le rapport entre le support de l’union des itemsets \(X\) et \(Y\) (c’est-à-dire le support de l’itemset \(X \cup Y\)) et le support de l’itemset \(X\).

Formule :

\[ \text{Confiance}(X \Rightarrow Y) = \frac{\text{Support}(X \cup Y)}{\text{Support}(X)} \]

Interprétation :

  • La confiance est une valeur comprise entre 0 et 1.
  • Une confiance de 0.75 pour la règle {Pain} \(\Rightarrow\) {Lait} signifie que 75% des clients qui ont acheté du “Pain” ont également acheté du “Lait”.
  • Plus la confiance est élevée, plus la règle est considérée comme fiable ou “forte”.

Example 8 (Exemple de Calcul) Utilisons toujours notre base de données de transactions :

ID Transaction Items Achetés
1 {Lait, Pain, Oeufs}
2 {Pain, Beurre}
3 {Lait, Couches, Bière, Pain}
4 {Lait, Beurre, Pain}
5 {Couches, Bière}

Calculons la confiance de la règle {Pain} \(\Rightarrow\) {Lait} :

  • D’abord, nous avons besoin du support de l’antécédent {Pain}. Nous l’avons calculé précédemment : \(\text{Support}(\{\text{Pain}\}) = \dfrac{4}{5} = 0.8\).
  • Ensuite, nous avons besoin du support de l’union de l’antécédent et du conséquent, c’est-à-dire \(\text{Support}(\{\text{Pain}\} \cup \{\text{Lait}\}) = \text{Support}(\{\text{Pain, Lait}\})\). Nous l’avons aussi calculé : \(\text{Support}(\{\text{Pain, Lait}\}) = \dfrac{3}{5} = 0.6\).
  • Maintenant, nous pouvons calculer la confiance : \(\text{Confiance}(\{\text{Pain}\} \Rightarrow \{\text{Lait}\}) = \dfrac{\text{Support}(\{\text{Pain, Lait}\})}{\text{Support}(\{\text{Pain}\})} = \dfrac{0.6}{0.8} = 0.75=75\%\).

Cela signifie que parmi les clients qui ont acheté du “Pain”, \(75\%\) d’entre eux ont également acheté du “Lait”.

Confiance Minimum (minconf) :

Similaire au support minimum, on définit souvent un seuil de confiance minimum (minconf). Seules les règles dont la confiance est supérieure ou égale à minconf sont conservées. Ce seuil permet de s’assurer que les règles générées sont suffisamment fiables pour être considérées.

6.3 Lift

Le lift d’une règle d’association \(X \Rightarrow Y\) mesure à quel point la présence de \(X\) augmente la probabilité de présence de \(Y\) par rapport à la probabilité de présence de \(Y\) dans l’ensemble des transactions. En d’autres termes, il évalue l’importance de la règle en tenant compte de la popularité de \(Y\).

Definition 10 (Définition Formelle) Le lift de la règle \(X \Rightarrow Y\), noté \(\text{Lift}(X \Rightarrow Y)\), est calculé comme le rapport entre la confiance de la règle et le support du conséquent \(Y\). Il peut également être exprimé en termes de supports :

Formule :

\[ \text{Lift}(X \Rightarrow Y) = \frac{\text{Support}(X \cup Y)}{\text{Support}(X) \times \text{Support}(Y)} = \frac{\text{Confiance}(X \Rightarrow Y)}{\text{Support}(Y)} \]

Interprétation :

  • Lift > 1 : Indique une association positive entre \(X\) et \(Y\). La présence de \(X\) augmente la probabilité de présence de \(Y\). Plus le lift est élevé, plus l’association est forte.
  • Lift = 1 : Indique que \(X\) et \(Y\) sont indépendants. La présence de \(X\) n’affecte pas la probabilité de présence de \(Y\).
  • Lift < 1 : Indique une association négative entre \(X\) et \(Y\). La présence de \(X\) diminue la probabilité de présence de \(Y\). Cela peut suggérer que \(X\) et \(Y\) sont des substituts ou qu’ils sont moins susceptibles d’apparaître ensemble que ce qui serait attendu par hasard.

Example 9 (Exemple de Calcul) Reprenons notre exemple de base de données de transactions :

ID Transaction Items Achetés
1 {Lait, Pain, Oeufs}
2 {Pain, Beurre}
3 {Lait, Couches, Bière, Pain}
4 {Lait, Beurre, Pain}
5 {Couches, Bière}

Calculons le lift de la règle {Pain} \(\Rightarrow\) {Lait} :

  • Nous avons déjà calculé :
    • \(\text{Support}(\{\text{Pain, Lait}\}) = 0.6\)
    • \(\text{Support}(\{\text{Pain}\}) = 0.8\)
    • \(\text{Support}(\{\text{Lait}\}) = \dfrac{3}{5} = 0.6\) (car le lait apparaît dans les transactions 1, 3 et 4)
  • Donc, \(\text{Lift}(\{\text{Pain}\} \Rightarrow \{\text{Lait}\}) = \dfrac{0.6}{0.8 \times 0.6} = \dfrac{0.6}{0.48} = 1.25\).

Ce résultat indique une association positive entre l’achat de “Pain” et l’achat de “Lait”. Le fait d’acheter du “Pain” augmente de 25% la probabilité d’acheter du “Lait” par rapport à la probabilité d’acheter du “Lait” dans l’ensemble des transactions.

6.4 Autres Métriques (Optionnel, pour Niveau Avancé)

Bien que le support, la confiance et le lift soient les métriques les plus couramment utilisées, d’autres peuvent offrir des perspectives supplémentaires sur la force et l’intérêt des règles d’association.

Conviction

La conviction mesure le degré de dépendance du conséquent par rapport à l’antécédent. Elle compare la probabilité que \(X\) apparaisse sans \(Y\) (si \(X\) et \(Y\) étaient indépendants) avec la fréquence réelle de \(X\) apparaissant sans \(Y\). Une conviction élevée signifie que la règle \(X \Rightarrow Y\) est très souvent vraie.

Formule :

\[ \text{Conviction}(X \Rightarrow Y) = \frac{1 - \text{Support}(Y)}{1 - \text{Confiance}(X \Rightarrow Y)} \]

Interprétation :

  • Conviction > 1 : Indique une corrélation positive. Plus la valeur est élevée, plus l’antécédent \(X\) “implique” le conséquent \(Y\). Par exemple, une conviction de 1.5 signifie que la règle \(X \Rightarrow Y\) serait incorrecte 50% plus souvent si l’association était purement aléatoire.
  • Conviction = 1 : Indique que \(X\) et \(Y\) sont indépendants.
  • Conviction < 1 : Indique une corrélation négative.
  • La conviction est sensible à la direction de la règle et peut être infinie si la confiance est de 1 (ce qui signifie que \(Y\) apparaît toujours lorsque \(X\) apparaît).

Leverage (Levier)

Le leverage mesure la différence entre la fréquence observée de \(X\) et \(Y\) apparaissant ensemble et la fréquence qui serait attendue si \(X\) et \(Y\) étaient indépendants. En d’autres termes, il quantifie combien de fois \(X\) et \(Y\) apparaissent ensemble de plus (ou de moins) que ce que l’on attendrait par pur hasard.

Formule :

\[ \text{Leverage}(X \Rightarrow Y) = \text{Support}(X \cup Y) - (\text{Support}(X) \times \text{Support}(Y)) \]

Interprétation :

  • Leverage > 0 : Indique que \(X\) et \(Y\) apparaissent ensemble plus souvent que ce qui serait attendu par indépendance. Une valeur plus élevée indique une association plus forte.
  • Leverage = 0 : Indique que \(X\) et \(Y\) sont indépendants.
  • Leverage < 0 : Indique que \(X\) et \(Y\) apparaissent ensemble moins souvent que ce qui serait attendu par indépendance.

Le leverage est intéressant car il est exprimé en termes de support, ce qui peut donner une idée du nombre absolu de transactions supplémentaires où la règle est observée par rapport à l’indépendance.

Note

Ces métriques avancées, ainsi que d’autres comme le coefficient de Jaccard ou la force de conviction, peuvent être utiles pour affiner la sélection des règles les plus pertinentes, en particulier lorsque le nombre de règles générées est très important.

6.5 Résumé des métriques

Pour évaluer la pertinence et la force des règles d’association, plusieurs métriques sont utilisées. Voici un résumé des plus fondamentales :

Métrique Définition Formule Interprétation Clé
Support(X) Fréquence d’apparition de l’itemset \(X\). \(\frac{\text{Nombre de transactions contenant } X}{\text{Nombre total de transactions}}\) Popularité d’un itemset. Un support élevé indique que l’itemset est courant.
Confiance(X \(\Rightarrow\) Y) Probabilité d’observer \(Y\) sachant que \(X\) est présent. Mesure la fiabilité de la règle. \(\frac{\text{Support}(X \cup Y)}{\text{Support}(X)}\) Si un client achète X, quelle est la probabilité qu’il achète aussi Y ? Une confiance élevée indique une règle plus fiable.
Lift(X \(\Rightarrow\) Y) Mesure à quel point la présence de \(X\) augmente la probabilité de \(Y\) par rapport à la popularité de base de \(Y\). \(\frac{\text{Support}(X \cup Y)}{\text{Support}(X) \times \text{Support}(Y)} = \frac{\text{Confiance}(X \Rightarrow Y)}{\text{Support}(Y)}\) - Lift > 1 : Association positive (plus que par hasard).
- Lift = 1 : Indépendance.
- Lift < 1 : Association négative (moins que par hasard).
Leverage(X \(\Rightarrow\) Y) Différence entre la fréquence observée de \(X \cup Y\) et celle attendue si \(X\) et \(Y\) étaient indépendants. \(\text{Support}(X \cup Y) - (\text{Support}(X) \times \text{Support}(Y))\) - Leverage > 0 : \(X\) et \(Y\) apparaissent ensemble plus souvent qu’attendu.
- Leverage = 0 : Indépendance.
- Leverage < 0 : Moins souvent qu’attendu.
Conviction(X \(\Rightarrow\) Y) Mesure le degré de dépendance de \(Y\) par rapport à \(X\). \(\frac{1 - \text{Support}(Y)}{1 - \text{Confiance}(X \Rightarrow Y)}\) - Conviction > 1 : \(Y\) est dépendant de \(X\). Plus la valeur est élevée, plus la règle est “forte”.
- Peut être \(\infty\) si Confiance = 1.

Seuils Importants :

  • Support Minimum (minsup) : Seuil utilisé pour filtrer les itemsets qui sont considérés comme “fréquents”. Seuls les itemsets avec un support \(\ge\) minsup sont retenus.
  • Confiance Minimum (minconf) : Seuil utilisé pour filtrer les règles d’association. Seules les règles avec une confiance \(\ge\) minconf sont considérées comme “fiables”.

Le choix de ces seuils est crucial et dépend du contexte de l’analyse et de la taille du jeu de données. Des seuils trop bas peuvent générer un très grand nombre de règles, tandis que des seuils trop élevés peuvent masquer des associations potentiellement intéressantes.

7 Algorithmes d’Extraction de Règles d’Association

L’extraction de règles d’association à partir d’un grand volume de transactions pose un défi computationnel significatif.

7.1 Le Défi Computationnel

Le nombre total d’itemsets possibles à partir d’un ensemble de \(N\) items est \(2^N - 1\). Par exemple, avec seulement 20 items, il y a \(2^{20} - 1 \approx 1 \text{ million}\) d’itemsets possibles. Avec 100 items, ce nombre devient astronomique. Évaluer le support pour chacun de ces itemsets serait infaisable.

De plus, pour chaque itemset fréquent, le nombre de règles d’association possibles peut également être très élevé. Si un itemset fréquent contient \(k\) items, il peut générer \(2^k - 2\) règles d’association potentielles (en excluant les règles avec un antécédent ou un conséquent vide).

Face à cette explosion combinatoire, il est impératif d’utiliser des algorithmes efficaces qui peuvent trouver les itemsets fréquents et générer des règles sans avoir à énumérer toutes les possibilités.

7.2 Approche Générale en Deux Étapes

La plupart des algorithmes d’extraction de règles d’association suivent une approche en deux étapes :

  1. Étape 1 : Extraction des Itemsets Fréquents L’objectif est de trouver tous les itemsets dont le support est supérieur ou égal au seuil de support minimum (minsup) défini par l’utilisateur. C’est l’étape la plus coûteuse en termes de calcul.

  2. Étape 2 : Génération des Règles d’Association Une fois les itemsets fréquents identifiés, des règles d’association sont générées à partir de ces itemsets. Pour chaque itemset fréquent \(L\), on génère toutes les règles non vides de la forme \(X \Rightarrow (L-X)\). Ensuite, seules les règles dont la confiance est supérieure ou égale au seuil de confiance minimum (minconf) sont conservées. Cette étape est généralement moins coûteuse que la première.

7.3 Vue d’Ensemble des Algorithmes Usuels

Plusieurs algorithmes ont été développés pour relever ce défi. Les plus connus incluent :

  • Apriori : L’un des premiers et des plus célèbres algorithmes. Il utilise la propriété d’anti-monotonie du support pour élaguer l’espace de recherche des itemsets.

  • FP-Growth (Frequent Pattern Growth) : Une approche alternative qui évite la génération coûteuse de candidats d’Apriori en construisant une structure de données compacte appelée FP-Tree. Il est souvent plus rapide qu’Apriori, en particulier sur des jeux de données denses.

  • Eclat (Equivalence Class Clustering and bottom-up Lattice Traversal) : Un algorithme qui utilise une représentation verticale des données (TID-lists) et une recherche en profondeur (depth-first search) pour trouver les itemsets fréquents. Il peut être très efficace pour certains types de données.

Nous allons explorer ces algorithmes plus en détail dans les sections suivantes.

Algo. Apriori

Algo. FP-Growth