Algorithme Apriori en anglais simple?

J'ai lu un article wiki sur Apriori. J'ai du mal à comprendre le pruneau et l'étape Join. Quelqu'un peut-il m'expliquer comment l'algorithme Apriori fonctionne en termes simples (de telle sorte que les novices comme moi peuvent facilement comprendre)?

Ce sera bien si quelqu'un explique le processus étape par étape qui y est impliqué.

L' article de Wikipédia n'est pas particulièrement impressionnant. Vous pourriez trouver ces diapositives plus utiles: 1 , 2 , 3 .

À chaque niveau , vous avez -item sets qui sont fréquents (ont un support suffisant). $k$$k$

Au niveau suivant, les ensembles d'éléments + dont vous devez tenir compte doivent avoir la propriété que chacun de leurs sous-ensembles doit être fréquent (avoir un support suffisant). Il s'agit de la propriété apriori : tout sous-ensemble d'éléments fréquents doit être fréquent.$k$$1$

Donc, si vous savez au niveau 2 que les ensembles , , et sont les seuls ensembles avec un support suffisant, alors au niveau 3, vous les joignez les uns aux autres pour produire , , et mais il suffit de considérer plus loin: les autres ont chacun des sous-ensembles avec un support insuffisant (comme ou ).$\{1,2\}$$\{1,3\}$$\{1,5\}$$\{3,5\}$$\{1,2,3\}$$\{1,2,5\}$$\{1,3,5\}$$\{2,3,5\}$$\{1,3,5\}$$\{2,3\}$$\{2,5\}$

L'algorithme Apriori est un algorithme d'exploration de règles d'association utilisé dans l'exploration de données. Il est utilisé pour trouver l'ensemble d'éléments fréquents parmi le nombre donné de transactions.

Il se compose essentiellement de deux étapes

1. Auto-adhésion
2. Élagage

En répétant ces étapes k fois, où k est le nombre d'éléments, dans la dernière itération, vous obtenez des ensembles d'éléments fréquents contenant k éléments.

Regardez ici pour une explication très simple avec un exemple détaillé http://nikhilvithlani.blogspot.com/2012/03/apriori-algorithm-for-data-mining-made.html .

Il a une explication simple sans équations compliquées.

Apriori en anglais simple.

Apriori utilise une approche itérative connue sous le nom de recherche au niveau du niveau, où les k-itemsets sont utilisés pour explorer (k + 1) -itemsets . Tout d'abord, l'ensemble des jeux de 1 élément fréquents est trouvé en analysant la base de données pour accumuler le nombre de chaque élément et en collectant les éléments qui satisfont un support minimum. L'ensemble résultant est noté L1 . Ensuite, L1 est utilisé pour trouver L2 , l'ensemble d'ensembles fréquents de 2 éléments , qui est utilisé pour rechercher L3, et ainsi de suite, jusqu'à ce qu'il ne soit plus possible de trouver des ensembles de k éléments . La recherche de chaque Lk nécessite une analyse complète de la base de données.

À l'itération finale, vous vous retrouverez avec de nombreux k-itemsets qui sont fondamentalement appelés règles d'association . Pour sélectionner des règles intéressantes dans l'ensemble de toutes les règles possibles, diverses mesures de contrainte telles que le soutien et la confiance sont appliquées.

Termes et terminologies

• 1-itemsets signifie {a}, {b}, {c}
• Ensembles de 2 éléments signifie {a, b}, {d, d}, {a, c}
• K-itemsets signifie {i1, i2, i3, ... ik}, {j1, j2, j3, .... jk}

Étape de jointure: signifiant que 1-itemset est fait pour se joindre à lui-même pour générer des 2-itemsets.

Étape d'élagage: ici l'ensemble résultant de la jointure est filtré avec un seuil de support minimum.

ensemble de cardinalité: ensemble résultant de l'étape Prune.

Support = nombre de transcations contenant 'a' et 'b' / nombre total de transactions.

Support => supp (a, b) => p (a U b)

Confiant = nombre de transactions contenant «a» et «b» / nombre de transactions contenant «a».

Confiant => con (a, b) ==> P (b | a) rien que la probabilité conditionnelle.