Due: Friday, February 3 (Part I) and Friday, February 10 (Part II)

[Readings]

• Read Chapter 6.1 and 6.2 of the textbook.

[Association Rule Mining with Apriori Algorithm]

For this assignment, you are going to implement the Apriori Algorithm described in Chapter 6.2 of the textbook to mine strong association rules. You may use any programming language of your choice, as long as your program can be compiled and run on CS3.

Please send an email to csun@calstatela.edu and ask for an account on CS3. A number of programming languages are available on CS3, including C, C++, Java, and several scripting languages such as Perl, Python, and Ruby. Please try compiling and running a simple program on CS3 before you decide what language you are going to use.

Part I. Test Dataset (30pt)

In the first part of the assignment you are going to design a test dataset which you will use to verify the correctness of your code in Part II. Your test dataset must meet the following requirements:

• Each item in the dataset is represented by an integer.
• The dataset must contain at least 5 unique items and 10 transactions.
• If the minimum support is 30%, the dataset should produce at least 5 frequent itemsets, and the size of the largest frequent itemset should be at least 3.
• If the minimum support is 30% and the minimum confidence is 60%, the dataset should produce at least 3 strong association rules.

Collaborating on the test dataset design is considered cheating. Anyone who submits a dataset that is identical or sufficiently similar to somebody else's will receive an automatic F for the course.

For this part please submit two files. The first file should contain the dataset in the input file format described in Part II. The second file should contain a step-by-step description of applying the Apriori algorithm to the dataset to find the frequent itemsets and the strong association rules with 30% minimum support and 60% minimum confidence.

Part II. Algorithm Implementation (70pt)

Your implementation of the Apriori algorithm must take four command line parameters as follows (I'm going to use Java for examples, but as stated earlier, you may use other programming languages):

java Apriori <inputFile> <outputFile> <minSupportCount> <minConfidence>

• inputFile is the name of a text file that contains the transactions. Each transaction occupies one line, and the items in each transaction are separated by white spaces. You may assume that the items are represented by integers starting from 0. A sample input file retail.txt [1] is available.
• outputFile is the name of a text file that contains the strong association rules discovered. Each association rule occupies one line in the format of

For example:

• minSupportCount is the minimum support count, which is an integer greater than 0, e.g. 1000.
• minConfidence is the minimum confidence, which is a value between 0 and 1, e.g. 0.7.

After you complete your program, please test it with the test dataset you designed in Part I to make sure the results are correct, and then test the program with a larger dataset (e.g. retail.txt) to make sure its performance is reasonable.

Note that

• Use of existing Apriori code or other frequent pattern mining code found online or from other sources will be considered cheating.
• Your program may not rely on any external tools or databases.
• To receive full credit, your program must be able to mine the retail dataset (i.e. retail.txt) with minSupportCount=1000 and minConfidence=0.7 within 30 seconds on CS3.
• I will time the running time of each program. The five fastest programs will receive up to 20% extra credit, and the five slowest programs and the programs that cannot finish the tests due to code inefficiency (e.g. memory overflow) will receive up to 30% extra penalty.

[1] retail.txt is a dataset provided by Tom Brijs and contains the anonymized retail market basket data from an anonymous Belgian retail store.