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.
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\}$ ).
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
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.
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
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.
