Menu

Algorithme Apriori dans l'exploration de données: mise en œuvre avec des exemples

  • Principal
  • Autre
  • Algorithme Apriori dans l'exploration de données: mise en œuvre avec des exemples

apriori algorithm data mining

Essayez Notre Instrument Pour Éliminer Les Problèmes

Tutoriel approfondi sur l'algorithme Apriori pour découvrir les ensembles d'éléments fréquents dans l'exploration de données. Ce didacticiel explique les étapes d'Apriori et son fonctionnement:

Dans ce Série de didacticiels d'exploration de données , nous avons regardé le Algorithme d'arbre de décision dans notre tutoriel précédent.

Il existe plusieurs méthodes pour l'exploration de données telles que l'association, la corrélation, la classification et le clustering.

sql query interview questions et réponses pour pdf expérimenté

Ce didacticiel se concentre principalement sur l'extraction à l'aide de règles d'association. Par des règles d'association, nous identifions l'ensemble d'éléments ou d'attributs qui se produisent ensemble dans une table.

Algorithme Apriori

Ce que vous apprendrez:

Qu'est-ce qu'un ensemble d'éléments?

Un ensemble d'éléments ensemble est appelé un ensemble d'éléments. Si un ensemble d'éléments a des k-items, il est appelé un k-itemset. Un ensemble d'éléments se compose de deux éléments ou plus. Un jeu d'éléments qui se produit fréquemment est appelé un jeu d'éléments fréquent. L'exploration fréquente d'ensembles d'éléments est donc une technique d'exploration de données pour identifier les éléments qui se produisent souvent ensemble.

Par exemple , Pain et beurre, Logiciel pour ordinateur portable et antivirus, etc.

Qu'est-ce qu'un ensemble d'éléments fréquents?

Un ensemble d'éléments est appelé fréquent s'il satisfait à une valeur seuil minimale de soutien et de confiance. Le support affiche les transactions avec des articles achetés ensemble en une seule transaction. La confiance montre les transactions où les articles sont achetés les uns après les autres.

Pour la méthode d'extraction fréquente d'ensembles d'éléments, nous ne considérons que les transactions qui satisfont aux exigences minimales de support et de confiance. Les connaissances de ces algorithmes de minage offrent de nombreux avantages, une réduction des coûts et un avantage concurrentiel amélioré.

Il y a un compromis entre le temps nécessaire pour extraire les données et le volume de données pour une extraction fréquente. L'algorithme de minage fréquent est un algorithme efficace pour extraire les modèles cachés des ensembles d'éléments en peu de temps et en consommant moins de mémoire.

Exploration fréquente de motifs (FPM)

L'algorithme d'exploration de modèles fréquents est l'une des techniques les plus importantes d'exploration de données pour découvrir les relations entre les différents éléments d'un ensemble de données. Ces relations sont représentées sous la forme de règles d'association. Cela aide à trouver les irrégularités dans les données.

FPM a de nombreuses applications dans le domaine de l'analyse de données, des bugs logiciels, du cross-marketing, de l'analyse des campagnes de vente, de l'analyse du panier de marché, etc.

Les ensembles d'éléments fréquemment découverts via Apriori ont de nombreuses applications dans les tâches d'exploration de données. Les tâches telles que la recherche de modèles intéressants dans la base de données, la recherche de séquences et l'exploration des règles d'association sont les plus importantes d'entre elles.

Les règles d'association s'appliquent aux données de transaction des supermarchés, c'est-à-dire pour examiner le comportement des clients en termes de produits achetés. Les règles d'association décrivent la fréquence à laquelle les articles sont achetés ensemble.

Règles d'association

L'exploration des règles d'association est définie comme suit:

«Soit I = {…} un ensemble d’attributs binaires‘ n ’appelés éléments. Soit D = {….} L'ensemble de la transaction appelée base de données. Chaque transaction en D a un identifiant de transaction unique et contient un sous-ensemble des éléments en I. Une règle est définie comme une implication de la forme X-> Y où X, Y? I et X? Y = ?. L'ensemble des éléments X et Y sont appelés respectivement antécédent et conséquent de la règle. »

L'apprentissage des règles d'association est utilisé pour trouver des relations entre les attributs dans de grandes bases de données. Une règle d'association, A => B, sera de la forme «pour un ensemble de transactions, une certaine valeur de l'ensemble d'éléments A détermine les valeurs de l'ensemble d'éléments B sous la condition dans laquelle le support et la confiance minimaux sont satisfaits».

Le soutien et la confiance peuvent être représentés par l'exemple suivant:

Bread=> butter (support=2%, confidence-60%)

L'instruction ci-dessus est un exemple de règle d'association. Cela signifie qu'il y a une transaction de 2% qui a acheté du pain et du beurre ensemble et que 60% des clients ont acheté du pain ainsi que du beurre.

La prise en charge et la confiance pour les éléments A et B sont représentées par des formules:

Formule d

L'exploration des règles d'association se compose de 2 étapes:

  1. Trouvez tous les ensembles d'éléments fréquents.
  2. Générez des règles d'association à partir des ensembles d'éléments fréquents ci-dessus.

Pourquoi l'exploitation fréquente des jeux d'articles?

Les jeux d'éléments fréquents ou l'exploration de modèles sont largement utilisés en raison de ses larges applications dans les règles d'association d'exploration de données, les corrélations et les contraintes de modèles de graphes qui sont basées sur des modèles fréquents, des modèles séquentiels et de nombreuses autres tâches d'exploration de données.

Algorithme Apriori - Algorithmes de motifs fréquents

L'algorithme Apriori était le premier algorithme proposé pour l'extraction fréquente d'ensembles d'éléments. Il a ensuite été amélioré par R Agarwal et R Srikant et est devenu connu sous le nom d'Apriori. Cet algorithme utilise deux étapes «joindre» et «élaguer» pour réduire l'espace de recherche. Il s'agit d'une approche itérative pour découvrir les ensembles d'éléments les plus fréquents.

Apriori dit:

La probabilité que l'élément I ne soit pas fréquent est si:

  • PI)
  • P (I + A)
  • Si un ensemble d'éléments a une valeur inférieure à la prise en charge minimale, tous ses sur-ensembles tomberont également sous la prise en charge minimale et pourront donc être ignorés. Cette propriété est appelée la propriété Antimonotone.

Les étapes suivies dans l'algorithme Apriori de l'exploration de données sont:

  1. Rejoignez l'étape : Cette étape génère (K + 1) un ensemble d'éléments à partir de K-éléments en joignant chaque élément avec lui-même.
  2. Étape Prune : Cette étape analyse le nombre de chaque élément de la base de données. Si l'élément candidat ne répond pas au support minimum, il est considéré comme peu fréquent et est donc supprimé. Cette étape est effectuée pour réduire la taille des ensembles d'éléments candidats.

Étapes d'Apriori

L'algorithme Apriori est une séquence d'étapes à suivre pour trouver l'ensemble d'éléments le plus fréquent dans la base de données donnée. Cette technique d'exploration de données suit les étapes de jointure et d'élagage de manière itérative jusqu'à ce que l'ensemble d'éléments le plus fréquent soit atteint. Un seuil de support minimum est donné dans le problème ou il est supposé par l'utilisateur.

#1) Dans la première itération de l'algorithme, chaque élément est considéré comme un candidat d'ensembles à 1 éléments. L'algorithme comptera les occurrences de chaque élément.

#deux) Soit un support minimum, min_sup (par exemple 2). L'ensemble des 1 - itemsets dont l'occurrence satisfait le min sup est déterminé. Seuls les candidats qui comptent plus ou égal à min_sup, sont pris en avance pour l'itération suivante et les autres sont élagués.

# 3) Ensuite, les éléments fréquents de 2 éléments avec min_sup sont découverts. Pour cela, dans l'étape de jointure, l'ensemble de 2 éléments est généré en formant un groupe de 2 en combinant des éléments avec lui-même.

# 4) Les candidats à 2 éléments sont élagués en utilisant la valeur de seuil min-sup. Désormais, la table aura 2 ensembles d'éléments avec min-sup uniquement.

# 5) L'itération suivante formera 3 ensembles d'éléments en utilisant l'étape de jointure et d'élagage. Cette itération suivra la propriété antimonotone où les sous-ensembles d'ensembles de 3 éléments, c'est-à-dire les sous-ensembles de 2 éléments de chaque groupe, tombent dans min_sup. Si tous les sous-ensembles de 2 éléments sont fréquents, le sur-ensemble sera fréquent sinon il sera élagué.

# 6) La prochaine étape suivra la création d'un ensemble de 4 éléments en joignant l'ensemble de 3 éléments à lui-même et en l'élaguant si son sous-ensemble ne répond pas aux critères min_sup. L'algorithme est arrêté lorsque l'ensemble d'éléments le plus fréquent est atteint.

Étapes Apriori

(image la source )

Exemple d'Apriori:Seuil de soutien = 50%, confiance = 60%

TABLEAU 1

TransactionListe d'objets
T1I1, I2, I3
T2I2, I3, I4
T3I4, I5
T4I1, I2, I4
T5I1, I2, I3, I5
T6I1, I2, I3, I4

Solution:

Seuil de support = 50% => 0,5 * 6 = 3 => min_sup = 3

1. Nombre de chaque article

TABLEAU 2

ArticleCompter
I14
I25
I34
I44
I5deux

2. Étape de taille: TABLEAU 2 montre que l'élément I5 ne répond pas à min_sup = 3, il est donc supprimé, seuls I1, I2, I3, I4 rencontrent le nombre min_sup.

TABLEAU 3

ArticleCompter
I14
I25
I34
I44

3. Rejoignez l'étape: Ensemble de 2 éléments du formulaire. De TABLEAU 1 découvrez les occurrences de 2-itemset.

TABLEAU 4

ArticleCompter
I1, I24
I1, I33
I1, I4deux
I2, I34
I2, I43
I3, I4deux

Quatre. Étape de taille: TABLEAU -4 montre que l'ensemble d'éléments {I1, I4} et {I3, I4} ne correspond pas à min_sup, il est donc supprimé.

TABLEAU 5

ArticleCompter
I1, I24
I1, I33
I2, I34
I2, I43

5. Rejoignez et élaguez l'étape: Ensemble de 3 éléments du formulaire. Du TABLEAU 1 trouver les occurrences de 3-itemset. De TABLEAU 5 , découvrez les sous-ensembles de 2 éléments qui prennent en charge min_sup.

Nous pouvons voir que pour les sous-ensembles d'éléments {I1, I2, I3}, {I1, I2}, {I1, I3}, {I2, I3} se produisent dans TABLEAU 5 ainsi {I1, I2, I3} est fréquent.

Nous pouvons voir que pour les sous-ensembles d'éléments {I1, I2, I4}, {I1, I2}, {I1, I4}, {I2, I4}, {I1, I4} ne sont pas fréquents, car ils ne se produisent pas dans TABLEAU 5 ainsi {I1, I2, I4} n'est pas fréquent, donc il est supprimé.

TABLEAU 6

Article
I1, I2, I3
I1, I2, I4
I1, I3, I4
I2, I3, I4

Seul {I1, I2, I3} est fréquent .

6. Générer des règles d'association: À partir de l'ensemble d'éléments fréquemment découverts ci-dessus, l'association pourrait être:

outil de réparation de logiciel pour windows 10

{I1, I2} => {I3}

Confiance = support {I1, I2, I3} / support {I1, I2} = (3/4) * 100 = 75%

{I1, I3} => {I2}

Confiance = support {I1, I2, I3} / support {I1, I3} = (3/3) * 100 = 100%

{I2, I3} => {I1}

Confiance = support {I1, I2, I3} / support {I2, I3} = (3/4) * 100 = 75%

{I1} => {I2, I3}

Confiance = support {I1, I2, I3} / support {I1} = (3/4) * 100 = 75%

{I2} => {I1, I3}

Confiance = support {I1, I2, I3} / support {I2 = (3/5) * 100 = 60%

{I3} => {I1, I2}

Confiance = support {I1, I2, I3} / support {I3} = (3/4) * 100 = 75%

Cela montre que toutes les règles d'association ci-dessus sont fortes si le seuil de confiance minimum est de 60%.

L'algorithme Apriori: pseudo-code

C: ensemble d'articles candidats de taille k

L: ensemble d'articles fréquents de taille k

Psudocode

(image la source )

Avantages

  1. Algorithme facile à comprendre
  2. Les étapes de jointure et d'élagage sont faciles à implémenter sur de grands ensembles d'éléments dans de grandes bases de données

Désavantages

  1. Cela nécessite un calcul élevé si les ensembles d'éléments sont très volumineux et que la prise en charge minimale est maintenue très faible.
  2. La base de données entière doit être analysée.

Méthodes pour améliorer l'efficacité d'Apriori

De nombreuses méthodes sont disponibles pour améliorer l'efficacité de l'algorithme.

  1. Technique basée sur le hachage: Cette méthode utilise une structure basée sur le hachage appelée table de hachage pour générer les k-itemsets et son décompte correspondant. Il utilise une fonction de hachage pour générer la table.
  2. Réduction de transaction: Cette méthode réduit le nombre de transactions numérisées dans les itérations. Les transactions qui ne contiennent pas d'éléments fréquents sont marquées ou supprimées.
  3. Partitionnement: Cette méthode ne nécessite que deux analyses de base de données pour extraire les ensembles d'éléments fréquents. Il indique que pour qu'un ensemble d'éléments soit potentiellement fréquent dans la base de données, il doit être fréquent dans au moins une des partitions de la base de données.
  4. Échantillonnage: Cette méthode sélectionne un échantillon aléatoire S de la base de données D, puis recherche un ensemble d'éléments fréquents dans S. Il peut être possible de perdre un ensemble d'éléments fréquents global. Cela peut être réduit en abaissant le min_sup.
  5. Comptage d'ensembles d'éléments dynamiques: Cette technique peut ajouter de nouveaux ensembles d'éléments candidats à tout point de départ marqué de la base de données lors de l'analyse de la base de données.

Applications de l'algorithme Apriori

Quelques champs où Apriori est utilisé:

  1. Dans le domaine de l'éducation: Extraction des règles d'association dans le data mining des étudiants admis à travers les caractéristiques et les spécialités.
  2. Dans le domaine médical: Par exemple, analyse de la base de données des patients.
  3. En foresterie: Analyse de la probabilité et de l'intensité des feux de forêt avec les données sur les feux de forêt.
  4. Apriori est utilisé par de nombreuses entreprises comme Amazon dans le Système de recommandation et par Google pour la fonction de saisie semi-automatique.

Conclusion

L'algorithme Apriori est un algorithme efficace qui analyse la base de données une seule fois.

Cela réduit considérablement la taille des jeux d'éléments dans la base de données, offrant ainsi de bonnes performances. Ainsi, l'exploration de données aide les consommateurs et les industries à mieux dans le processus de prise de décision.

Consultez notre prochain tutoriel pour en savoir plus sur l'algorithme de croissance fréquente des modèles !!

Tutoriel PREV | Tutoriel SUIVANT

lecture recommandée

^