11
$\begingroup$

I read wiki article about Apriori. I have the trouble in understanding the prune and Join step. Can anyone explain me how Apriori algorithm works in simple terms(such that Novice like me can understand easily)?

It will be good if someone explains the step by step process involved in it.

$\endgroup$
1

3 Answers 3

12
$\begingroup$

The Wikipedia article is not particularly impressive. You might find these slides more helpful: 1, 2, 3.

At each level $k$, you have $k$-item sets which are frequent (have sufficent support).

At the next level, the $k$+$1$-item sets you need to consider must have the property that each of their subsets must be frequent (have sufficent support). This is the apriori property: any subset of frequent itemset must be frequent.

So if you know at level 2 that the sets $\{1,2\}$, $\{1,3\}$, $\{1,5\}$ and $\{3,5\}$ are the only sets with sufficient support, then at level 3 you join these with each other to produce $\{1,2,3\}$, $\{1,2,5\}$, $\{1,3,5\}$ and $\{2,3,5\}$ but you need only consider $\{1,3,5\}$ further: the others each have subsets with insufficent support (such as $\{2,3\}$ or $\{2,5\}$ ).

$\endgroup$
2
$\begingroup$

Apriori algorithm is an association rule mining algorithm used in data mining. It is used to find the frequent itemset among the given number of transactions.

It consists of basically two steps

  1. Self-Join
  2. Pruning

Repeating these steps k times, where k is the number of items, in the last iteration you get frequent item sets containing k items.

Look here for a very simple explanation with a detailed example http://nikhilvithlani.blogspot.com/2012/03/apriori-algorithm-for-data-mining-made.html.

It has a simple explanation without any complicated equations.

$\endgroup$
1
  • 2
    $\begingroup$ I left this post notice because it's usually better to provide a summary of the main points you want to emphasize rather than link to a blog without further explanations. Moreover, the purpose of this site is to build a collection of knowledgeable responses to specific questions with minimum dependencies on dangling or ephemeral links. So unless you can guarantee that the above link will be still alive in 10 years, say, I would strongly encourage you to summarize its main points in the present reply. $\endgroup$
    – chl
    Mar 3, 2012 at 11:34
1
$\begingroup$

Apriori in plain English.

Apriori employs an iterative approach known as level-wise search, where k-itemsets are used to explore (k+1)-itemsets. First, the set of frequent 1-itemsets is found by scanning the database to accumulate the count for each item, and collecting those items that satisfy minimum support. The resulting set is denoted as L1. Next, L1 is used to find L2, the set of frequent 2-itemsets, which is used to find L3, and so on, until no more frequent k-itemsets can be found. The finding of each Lk requires one full scan of the database.

At final iteration you will end up with many k-itemsets which is basically called association rules. To select interesting rules from the set of all possible rules various constraint measures such as support and confidence is applied.

Terms & Terminologies

  • 1-itemsets means {a} , {b} , {c}
  • 2-itemsets means {a, b} , {d, d} , {a, c}
  • K-itemsets means {i1, i2, i3,... ik}, {j1, j2, j3, .... jk}

Join step : meaning 1-itemset is made to self join with itself to generate 2-itemsets.

Prune step : here resulting set from join is filtered with minimum support threshold.

cardinality set : resulting set from Prune step .

Support = no.of transcations containing 'a' and 'b' / total no of transaction.

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

Confident = No.of transactions containing 'a' and 'b' / no of transaction containing 'a'.

Confident => con (a, b) == > P (b|a) nothing but conditional probability.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.