title: Implementation of apriori with spark
body: <p>I intend to implement the Apriori algorithm according to YAFIM article with pySpark.  It contains with two phases in processing workflow: </p>
  
  <ol>
  <li>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.</li>
  </ol>
  
  <p>[1]: <a href="http://bayanbox.ir/download/2410687383784490939/phase1.png" rel="nofollow noreferrer">http://bayanbox.ir/download/2410687383784490939/phase1.png</a> phase-1</p>
  
  <ol start="2">
  <li>Phase 2: in  this  phase,  we  iteratively  using  k-frequent itemsets to generate (k+1)-frequent itemsets.  </li>
  </ol>
  
  <p>[2]: <a href="http://bayanbox.ir/view/6380775039559120652/phase2.png" rel="nofollow noreferrer">http://bayanbox.ir/view/6380775039559120652/phase2.png</a> phase-2</p>
  
  <p>To implement the first phase I have written the following code:</p>
  
  <pre><code>from operator import add
  transactions = sc.textFile("/FileStore/tables/wo7gkiza1500361138466/T10I4D100K.dat").cache()
  minSupport = 0.05 * transactions.count()
  items = transactions.flatMap(lambda line:line.split(" "))
  itemCount = items.map(lambda item:(item, 1)).reduceByKey(add)
  l1 = itemCount.filter(lambda (i,c): c &gt; minSupport)
  l1.take(5)  
  
  output: [(u'', 100000), (u'494', 5102), (u'829', 6810), (u'368', 7828), (u'766', 6265)]
  </code></pre>
  
  <p>My problem is that I have no idea for implementing the second phase, and especially getting the candidate set item.</p>
  
  <p>For example, suppose we have the following RDD (frequent 3-itemsets):</p>
  
  <pre><code>([1, 4, 5], 7), ([1, 4, 6], 6), ...
  </code></pre>
  
  <p>We want to find the candidate 4-itemsets so that if in the 3-itemsets, the two first items is the same, you will have four items available as follows:</p>
  
  <pre><code>[1, 4, 5, 6], ...
  </code></pre>