0
$\begingroup$

While I was studying the formulation of market basket analysis problem in the book Elements of Statistical Learning in the chapter unsupervised learning, I came through the following statement:

The Apriori algorithm requires only one pass over the data for each value of T ( K ), which is crucial since we assume the data cannot be fitted into a computer’s main memory. If the data are sufficiently sparse (or if the threshold t is high enough), then the process will terminate in reasonable time even for huge data sets.

where, T(K) is the support of item-set K.

The statement

The Apriori algorithm requires only one pass over the data for each value of T ( K )

is not making any sense to me. Since this algorithm involves many repetition then why are they talking about "only one pass"? What does mean by "pass" here? How is T(k) "crucial" here?

And what does mean by the phrase ?

data are sufficiently sparse

$\endgroup$
1
$\begingroup$

The main idea of the apriori algorithm is that if an item is very rare by itself, it cannot be a part of a larger itemset that is common. Ie, if there are only 1 of {bananas}, there cannot be 10 of {bananas, milk}. So, if you are looking for frequent itemsets (eg, >2) of size 2, you might as well just ignore anything with {bananas}. (This is actually not realistic, bananas are one of the most commonly purchased items.)

It's a bit tricky to imagine this algorithm, but the attached picture makes it much clear. You can see from this picture that each scan removes itemsets that are rare on each pass (sweep through the data and check the freq of each istemset, deleting ones with frequency lower than threshold). So, it scans the full dataset once for each size of itemset, but doesn't have to scan the entire set of combinations of the prior itemsets because some itemsets were removed at each pass.

The threshold for frequency is very important. If the threshold for frequency is 100, then you might remove most of the candidate itemsets in the very first pass, and the next scans become very efficient. If it is 0, you remove nothing, and each scan requires a pass through all of the combinations of the prior itemsets.

If the data is sparse (ie, many items have low counts), then you end up eliminating a lot of potential itemsets in the very first passes (of course, this depends on the threshold).

K is an itemset, and T(K) is the frequency of the itemset. The text says The Apriori algorithm requires only one pass over the data for each value of | K |, not T(K). |K| is the cardinality of K, so the number of items. So it only requires one pass per |K|. Ie, |{bananas, bread}| =2. It only requires one pass for the set of 2 item itemsets.

*

$\endgroup$
  • $\begingroup$ Thanks Sir for answer. I get you. But I am not able to understand the language of the book that I have written in question above. Would you explain those statements a little bit? $\endgroup$ – ironman Jun 17 '18 at 17:48
  • $\begingroup$ What does mean by this statement "The Apriori algorithm requires only one pass over the data for each value of T ( K )" $\endgroup$ – ironman Jun 17 '18 at 18:02
  • $\begingroup$ edited @ironman , I think the book is different that the quote $\endgroup$ – user0 Jun 17 '18 at 18:22
  • $\begingroup$ now it's clear to me $\endgroup$ – ironman Jun 17 '18 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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