Description
In this homework, you are asked to implement SON algorithm “son.py” in Apache Spark using Python. Recall that given a set of baskets, SON algorithm divides them into chunks/partitions and then proceed in two stages. First, local frequent itemsets are collected, which form candidates; next, it makes second pass through data to determine which candidates are globally frequent. In this homework, please implement an Apriori algorithm for stage one. You may find Python itertools package to be useful in your implementation: https://docs.python.org/2/library/itertools.html#itertools.combinations Requirements: You must use mapPartitions() that invokes Apriori to find frequent itemsets in each partition. Format of execution: bin/spark-submit __ son.py baskets.txt .3 output.txt baskets.txt is a text file which contains a basket (a list of comma-separated item numbers) per line. For example 1,2,3 1,2,5 1,3,4 2,3,4 1,2,3,4 2,3,5 1,2,4 1,2 1,2,3 1,2,3,4,5 .3 is a minimum support ratio (that is, for an itemset to be frequent, it should appear in at least 30% of the baskets). output.txt is the name of output file. Format of output: You should save all frequent itemsets into one text file. Each line of the file contains one itemset (a list of comma-separated item numbers). The order doesn’t matter. For example, INF 553 – Spring 2017 2 4 1,3,4 1,2,3 2 1,3 2,4 2,3 1 2,3,4 1,4 3 3,4 1,2,4 2,5 1,2 5 Submissions: Name your python script as __ son.py and submit to blackboard by the due time. Notes: 1. The program takes 3 arguments: Input file Minimum support ratio Output file 2. All basket item are positive integers. 3. Make sure to follow the output format (The order of output itemset doesn’t matter) and the submission naming format. If you don’t follow either one or both of them, 20% points will be deducted. 4. A standalone Apriori need to be implemented in stage one. The second stage needs to be done in Spark (using mapPartitions()) too. 5. We will be using Moss for plagiarism detection.
