Apprendre Traitement des Flux de Données Transactionnelles avec l'Algorithme Apriori | Fondements des Règles d'Association et de l'Analyse Transactionnelle

Glissez pour afficher le menu

L'algorithme Apriori est un outil fondamental pour découvrir des itemsets fréquents dans les données transactionnelles, ce qui est essentiel pour l'analyse du panier d'achat. Au cœur d'Apriori se trouve le principe d'Apriori, également connu sous le nom de propriété de fermeture descendante.

Définition

Principe d'Apriori - Si un itemset est fréquent, alors tous ses sous-ensembles doivent également être fréquents.

Cette observation réduit considérablement le nombre d'itemsets à évaluer, car tout itemset contenant un sous-ensemble peu fréquent peut être immédiatement écarté.

La génération de candidats constitue la phase d'appariement de l'algorithme. À chaque itération, l'algorithme examine les itemsets fréquents retenus lors du tour précédent et les combine pour former de nouveaux groupes plus larges appelés candidats. Pour optimiser ce processus, l'algorithme ne fusionne que les itemsets presque identiques, partageant tous leurs éléments sauf le dernier.

Fonctionnement : Si l'algorithme découvre que {Bread, Milk} et {Bread, Diapers} sont tous deux très populaires individuellement, il les combine pour créer un nouveau candidat à trois éléments pour le tour suivant : {Bread, Milk, Diapers}.

Immédiatement après la génération des nouveaux candidats, l'algorithme lance la phase de pruning pour éliminer les combinaisons inutiles avant toute opération lourde sur la base de données. Cette étape repose entièrement sur le principe d'Apriori, qui stipule qu'un grand itemset ne peut être fréquent que si toutes ses parties plus petites le sont également. Lors du pruning, l'algorithme examine minutieusement chaque nouveau candidat et analyse ses sous-ensembles. Si un seul sous-ensemble n'a pas été retenu lors du tour précédent, le candidat entier est instantanément supprimé.

Fonctionnement : Imaginons que le candidat {Bread, Milk, Eggs} soit généré. L'algorithme vérifie ses sous-composants : {Bread, Milk}, {Bread, Eggs} et {Milk, Eggs}. Si vos historiques de transactions montrent que {Milk, Eggs} est une combinaison rare qui a échoué lors d'un tour précédent, l'algorithme écarte totalement {Bread, Milk, Eggs}. Cela permet d'économiser des ressources de calcul sur une combinaison vouée à l'échec.

Une fois la liste des candidats réduite aux options les plus prometteuses, l'algorithme passe à l'identification des itemsets fréquents. Le système parcourt les bases de données transactionnelles brutes pour compter précisément combien de fois ces groupes de candidats restants apparaissent ensemble lors des achats réels. Le total de chaque candidat est converti en pourcentage. Si ce score atteint ou dépasse le seuil de support minimal que vous avez défini, le candidat est officiellement reconnu comme itemset fréquent.

Définition

Seuil de support minimal : valeur seuil définie par l'utilisateur qui détermine la fréquence minimale qu'un itemset doit atteindre pour être considéré comme significatif dans l'algorithme Apriori. En fixant ce seuil, vous filtrez les itemsets apparaissant trop rarement dans le jeu de données. Un seuil élevé produira moins d'itemsets, mais plus courants, au risque de manquer des combinaisons rares mais intéressantes. Un seuil trop bas peut générer un trop grand nombre d'itemsets, y compris ceux ayant peu de valeur pratique. Le seuil choisi impacte directement la profondeur et l'orientation de l'analyse, il doit donc refléter les objectifs et l'échelle de l'exploration des données.

Ce cycle en trois étapes se répète consécutivement. Il passe des articles uniques aux paires, puis aux groupes de trois, et continue à s'étendre jusqu'à ce qu'une itération ne trouve plus de nouveaux itemsets fréquents, cartographiant ainsi l'ensemble du réseau de comportements d'achat des consommateurs.

Pour illustrer concrètement ces concepts, considérons un exemple avec un petit jeu de données. Supposons que vous ayez les transactions suivantes :

Transaction 1 : {Milk, Bread} ;
Transaction 2 : {Milk, Diaper, Beer, Bread} ;
Transaction 3 : {Milk, Diaper, Beer, Cola} ;
Transaction 4 : {Diaper, Beer} ;
Transaction 5 : {Milk, Diaper, Bread, Beer}.

L'algorithme identifie d'abord tous les articles uniques apparaissant fréquemment, puis génère des paires candidates à partir de ceux-ci, élimine celles contenant des articles peu fréquents, et poursuit ce processus pour découvrir des groupes fréquents plus larges, tels que {Milk, Diaper, Beer}.


              1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
            
import pandas as pd
from itertools import combinations

# Example transaction dataset
transactions = [
    ['Milk', 'Bread'],
    ['Milk', 'Diaper', 'Beer', 'Bread'],
    ['Milk', 'Diaper', 'Beer', 'Cola'],
    ['Diaper', 'Beer'],
    ['Milk', 'Diaper', 'Bread', 'Beer']
]

# Convert transactions to a DataFrame of one-hot encoded items
all_items = sorted(set(item for transaction in transactions for item in transaction))
df = pd.DataFrame([{item: (item in transaction) for item in all_items} for transaction in transactions])

def apriori(df, min_support=0.6):

    def get_support(itemset):
        return (df[list(itemset)].all(axis=1).sum()) / len(df)

    # Step 1: Finding frequent 1-itemsets
    frequent_itemsets = []
    current_level = []
    for item in all_items:
        support = get_support([item])
        if support >= min_support:
            current_level.append(frozenset([item]))
            frequent_itemsets.append((frozenset([item]), support))

    k = 2
    while current_level:
        # Step 2: Candidate generation
        candidates = []
        level_list = list(current_level)
        for i in range(len(level_list)):
            for j in range(i+1, len(level_list)):
                union = level_list[i] | level_list[j]
                if len(union) == k and union not in candidates:
                    # Step 3: Pruning
                    subsets = list(combinations(union, k-1))
                    if all(frozenset(subset) in current_level for subset in subsets):
                        candidates.append(union)

        # Step 4: Support counting
        next_level = []
        for candidate in candidates:
            support = get_support(candidate)
            if support >= min_support:
                next_level.append(candidate)
                frequent_itemsets.append((candidate, support))

        current_level = next_level
        k += 1

    # Format output
    return [(set(itemset), round(support, 2)) for itemset, support in frequent_itemsets]

# Running Apriori and displaying frequent itemsets
frequent_itemsets = apriori(df, min_support=0.6)
for itemset, support in frequent_itemsets:
    print(f"Frequent Itemset: {itemset}, Support: {support}")

Ce code Python illustre une implémentation simple de l'algorithme Apriori pour identifier les itemsets fréquents dans des données transactionnelles. Voici comment chaque étape est réalisée :

Préparation des données

Les transactions sont représentées sous forme de liste de listes, où chaque sous-liste contient les articles achetés ensemble.
Tous les articles uniques sont identifiés et triés.
Un DataFrame encodé en one-hot est créé : chaque ligne représente une transaction et chaque colonne correspond à un article, avec True ou False indiquant la présence ou l'absence.

Étapes de l'algorithme Apriori

1. Identification des itemsets fréquents de taille 1

L'algorithme calcule le support de chaque article individuel (la proportion de transactions contenant l'article).
Si le support d'un article atteint ou dépasse le seuil min_support (ici, 0,6), il est considéré comme fréquent et inclus dans la première liste des itemsets fréquents.

2. Génération des candidats

Pour les itemsets de longueur k (à partir de 2), l'algorithme génère de nouveaux itemsets candidats en combinant les itemsets fréquents de l'itération précédente qui partagent tous les articles sauf un.
Seules les combinaisons uniques sont prises en compte, ce qui évite les doublons.

3. Élagage

Les sous-ensembles de longueur k-1 de chaque nouveau candidat sont vérifiés.
Si un sous-ensemble n'est pas présent dans la liste des itemsets fréquents de l'itération précédente, le candidat est élagué (exclu), conformément au principe d'Apriori.

4. Comptage du support

Pour chaque candidat restant, l'algorithme compte combien de transactions contiennent tous les articles du candidat.
Le support est calculé et comparé au seuil. Seuls les candidats atteignant le seuil sont conservés comme itemsets fréquents pour l'itération suivante.

5. Itération

Les étapes 2 à 4 se répètent, en augmentant la taille des itemsets à chaque fois, jusqu'à ce qu'aucun nouvel itemset fréquent ne soit trouvé.

Résultat

La liste finale inclut tous les itemsets fréquents et leurs valeurs de support.
Le code affiche chaque itemset fréquent et son support, montrant quelles combinaisons d'articles apparaissent fréquemment ensemble dans les transactions.

1. Laquelle des propositions suivantes décrit le mieux l'étape de génération des candidats dans l'algorithme Apriori ?

2. Quelle est la principale raison de l'élagage des itemsets candidats lors de l'algorithme Apriori ?

Tout était clair ?

Merci pour vos commentaires !

Section 1. Chapitre 4

Demandez à l'IA

Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion

Section 1. Chapitre 4