Assignment2_Fall23

Assignment 2: Association Analysis Due: October 20 2023 11:59PM Two datasets (Market, Gene) are provided. For each dataset, we provide the transaction- item representation discussed in class — Each row denotes a transaction, and each transaction consists of a set of items. In this assignment, you are asked to implement Apriori algorithm that discovers a collection of frequent itemsets from a transaction database. Template is for Python 3. You are asked to fill in two functions: apriori_gen and get_freq . apriori_gen generates new candidate itemsets based on the frequent itemsets found in the previous iteration, and prunes the itemsets containing any infrequent itemset of size k -1. get_freq returns the candidate itemsets that meet a minimum support threshold. Do not change the input and output of the two functions in the template. Please take the following steps: 1. Implement Apriori algorithm. The pseudo code can be found below. Apriori ( T , minSupport ){ // T is the database and minSupport is the minimum support 𝐶 1 = {the set of unique single items in T } 𝐿 1 = {the set of single item whose support is not less than minSupport } for (k = 2; 𝐿 𝑘−1 ≠ ∅ ; k++ ){ //generate and prune candidate set 𝐶 𝑘 𝐶 𝑘 is a list of itemsets in which each itemset is formed by merging two itemsets in 𝐿 𝑘−1 if their first k-2 items are identical Remove an itemset from 𝐶 𝑘 if any ( k-1 )-subset of this candidate itemset is not in the frequent itemset list 𝐿 𝑘−1 //Count the support of each candidate itemset for each transaction t in database do { for each candidate 𝑐 in 𝐶 𝑘 // increment the support count of all candidate itemsets that are contained in transaction t if c is a subset of t then count[c] ← count[c] + 1 } for each candidate 𝑐 in 𝐶 𝑘 // Judge if a candidate itemset is frequent or not if the support of c is not less than minSupport then include c in 𝐿 𝑘 } return {𝐿 1 , 𝐿 2 , … , 𝐿 𝑘 } }