# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

#
# ## Basic I/O : Implement basic I/O function that can read the data from the dataset and write the results to a file.
#

# Loading required libraries
import pandas as pd
import numpy as np
from itertools import chain, combinations
import time


# ### As part of Basic input, I have created two functions:
#     Function 1(read_as_dataframe) - Reads the data from csv file and returns a dataframe
#     Function 2(read_as_list) - Reads the data from csv or txt file and returns a list

# read the data from the dataset using read_csv from pandas, read stabilized with engine
def read_as_dataframe(filename):
    cols = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10"]# at most 11 columns in the dataset, can be adopted to all datasets
    df = pd.read_csv(filename, names = cols, engine = 'python')
    return df


# Reading Data - flexible to use txt or csv file which reads the line and strips the unnecessary data, split and form a list.
# The FM creates a list of Transaction Database
def read_as_list(file):
    list_out = list()
    
    with open(file) as f:
        row_lines = f.readlines()
   
    for i in row_lines:
        single_line = i.strip().strip(",")
        list_out.append(single_line.split(','))
        
    return list_out


# #### Reading/Input demonstrated in using the function calls below:

# read the file into df by passing filename(parameter)
df = read_as_dataframe("GroceryStore.csv")
df.head()

# read the file to create a list
input_list = read_as_list('GroceryStore.csv')
input_list

# Using the textbook example to demonstrate the functionalities
df_example = read_as_dataframe("ex.csv")
df_example.head()

input_list_example = read_as_list('ex.csv')
input_list_example


# ### Basic Output: Writing a data frame to a file
#     
#      As part of output, 1. the function is created to write a dataframe into a text file
#      2. Writing FP tree into a file

# writing data to a file
def writetoafile(filename,df):
    with open(filename, 'w') as f:
        df.to_csv(filename)


# writing FP tree to a file
def write_tree(filename,fptree):
    file1 = open(filename,"w")
    file1.write(str(fptree))
    file1.close()


def write_list(filename,list_items):
    with open(filename, 'w') as filehandle:
        for list_item in list_items:
            filehandle.write('%s\n' % list_item)


# #### Writing as output demonstrated below:

# +
# Writing outputs to file
# -

# writing dataframe values into a file
writetoafile('output_file.txt',df)

# writing frequent itemlists into a file
write_list("freq_itemsets_fp",all_frequent_itemsets_fp)

# write FP tree into a file
write_tree("fptree.txt",fptree)


#
# ## Frequent Itemset : Find all possible 2, 3, 4 and 5-itemsets given the parameter of minimum-support.

# The Frequent Itemsets are created using three different algorithms which is implemented in this notebook:
#     1. Brute-force approach - Creates all possible combinations and prunes using minimum support
#     2. Apriori approach - Implements Apriori algorithm to generate frequent itemsets
#     3. FP Growth approach - Implements FP Growth algorithm to generate frequent itemsets

# ### This task provides the implementation of Brute-Force algorithm to generate frequent itemsets - 2,3,4 and 5 itemsets by taking minimum support as input parameter

# +
# I have used a modular approach where the functions can be re-used which increases the scalability and achieves literate coding
# enhancing the readility of the implementation

# +
# function to calculate the frequency of occurence of the item_sets

def freq(df,item_sets):
    count_list = [0] * len(item_sets)
    item_list = df.values.tolist()
    count = 0
    support_set = {}
    for i,k in zip(item_sets,range(len(item_sets))):
        for j in range(len(df)):
                if(set(i).issubset(set(item_list[j]))): 
                         count += 1
        count_list[k] = count
        count = 0
    return count_list


# +
# function to generate frequent items given the item-set, support counts and minimum support

def generate_frequent_itemset(count,comb_list,min_sup):
    freq_list = list()
    infreq_list = list()
    for item,i in zip(comb_list,range(len(comb_list))):
        if count[i]>=min_sup:
            freq_list.append(item)
        else:
            infreq_list.append(item)
    return freq_list,infreq_list


# +
# The brute force algorithm implemented below takes a dataframe, minimum support and number of itemsets as input and returns a 
# frequent item-sets as output

def brute_force_frequent_itemset(number_itemset,df,min_sup):
    
    list_comb = list(((df['0'].append(df['1']).append(df['2']).append(df['3']).append(df['4']).append(df['5']).append(df['6']).append(df['7']).append(df['8']).append(df['9']).append(df['10'])).unique()))
    list_comb.remove(np.nan)
    
    all_freq_itemlist = list()

# Generating n-itemset by obtaining unique values
    for i in range(1,number_itemset+1):
        
        # Generating combinations
        comb = combinations(list_comb,i)
        comb_list = list(comb)
        
        count = freq(df,comb_list)
        freq_list,infreq_list = generate_frequent_itemset(count,comb_list,min_sup)
        
        if freq_list:
            all_freq_itemlist.append(freq_list)
    
    return all_freq_itemlist


# -

# ### Illustration of Brute-force approach to generate frequent item-sets: 
# ### The two datasets are used to demonstrate the generation of outputs for all the algorithms.
#         1. Grocery store provided as part of coursework
#         2. Textbook example to demonstrate the working of different dataset

# Using a textbook example to generate frequent itemsets
# parameter 1 - number of itemsets. example - given 3, the frequent itemsets 1,2,3 are generated
freq_itemsets_example = brute_force_frequent_itemset(3,df_example,2)

freq_itemsets_example

freq_itemsets0 = brute_force_frequent_itemset(1,df,1250)

freq_itemsets0

# Using the dataset provided as part of coursework
# Upto 3-itemsets generation, min_sup is 2300
freq_itemsets1 = brute_force_frequent_itemset(3,df,2300)

freq_itemsets1

freq_itemsets2 = brute_force_frequent_itemset(5,df,280)

freq_itemsets2

freq_itemsets3 = brute_force_frequent_itemset(5,df,280)

freq_itemsets3

freq_itemsets_big = brute_force_frequent_itemset(12,df,50)

freq_itemsets_big


#
# ## Associated Rule : Find all interesting association rules from the frequent item-sets given the parameter of minimum-confidence.

# The association rules are created using only the frequent item-sets generated using various algorithms as mentioned above.
# The associatioin function takes dataframe(database of transactions), frequent_itemsets and the minimum-confidence to generate
# interesting association rules

# +
# Frequency - Count value of itemsets is determined by reusing the function created for brute-force approach, the count is used
# to calculate association rules, the scan of frequent itemsets is started from the maximum frequent sets and working upwards 
# till 1-frequent itemsets to generate all possible association rules given the minimum confidence percentage value.

def associations(df,itemsets,min_confidence_percent,filename='test_association_values.txt'): 

    file_association = open(filename,'w')
    confidence = float(min_confidence_percent)/100
    calc_confidence = 0.0
    
#   Determining count of values in frequent itemsets
    count = list()
    for k in itemsets:
        c = freq(df,k)
        count.append(c)
        
#   Computing association rules
    n = len(itemsets)-1
    n1 = n 
    n2 = n
    for i in range(n):
        for k in range(len(itemsets[n2])):
            item_count = count[n2][k]
            item = itemsets[n2][k]
            n1 = n2
            for l in range(n2):
                for j in range(len(itemsets[n1-1])):
                    lower_item_count = count[n1-1][j]
                    lower_item = itemsets[n1-1][j]
                    if set(lower_item).issubset(set(item)):
                        calc_confidence = item_count/lower_item_count
                        if calc_confidence >= confidence:
                            print("rule:"+str(lower_item)+"->"+str((set(item)-set(lower_item)))+"->"+str(calc_confidence*100))
                            file_association.write("\nrule:"+str(lower_item)+"->"+str((set(item)-set(lower_item)))+"->"+str(calc_confidence*100))
                n1 = n1-1
        n2 = n2-1
# -



# ### Illustration of Association generation from frequent item-sets: 

# Using textbook example to produce the Association rules
# parameter - frequent itemsets and minimum confidence
associations(df_example,freq_itemsets_example,50)

# +
# associations(df,freq_itemsets2,50)
# -

# Computing Associations for minimum confidence of 50 percent for 1,2,3,4 and 5 frequent item-sets
associations(df,freq_itemsets2,50)

freq_itemsets4 = brute_force_frequent_itemset(5,df,5000)

freq_itemsets4

associations(df,freq_itemsets4,50)

freq_itemsets5 = brute_force_frequent_itemset(5,df,1250)

freq_itemsets5

associations(df,freq_itemsets5,50)

freq_itemsets6 = brute_force_frequent_itemset(5,df,2456)

freq_itemsets6

associations(df,freq_itemsets6,45)

associations(df,freq_itemsets_big,55)


# ## Task 4
# ## Apriori Algorithm : Use Apriori algorithm for finding frequent itemsets.

# The modular approach is again adopted here to split different functions as a module and each module can be combined to 
# effectively implement the Apriori algorithm

# +
# overriding frozen to unfreeze

class MyFrozenSet(frozenset):
    def repr(self):
        return '([{}])'.format(', '.join(map(repr, self)))


# +
# unfreeze and display frozensets(not needed)

def unfreeze(item_sets):
    temp = list()
    for i in item_sets:
        temp.append([MyFrozenSet(j) for j in i])
    return temp


# +
# join the sets Lk * Lk

def join(itemset,n):
    set1 = set()
    set2 = set()
    for i in itemset:
        for j in itemset:
            # joining sets to generate length of size n using all the possible subsets
            if( len(i.union(j)) == n ):
                set1 = [i.union(j)]
                set2 = set2.union(set1)
    return set2


# +
# Generate Candidate set by removing infrequent subsets

def candidate(infreq_itemset,joined_set):
    flag = 0
    candidate_set = set()
    for i in joined_set:
        flag = 0
        for j in infreq_itemset:
            if(frozenset.issubset(j,i)):
                # if the joined set contains infrequent subset it is flagged to be removed
                flag = 1
        if flag == 0:
            # only the unflagged frequent sets are added into candidate set
            candidate_set.add(i)
    return candidate_set


# +
# Prune the Candidate set to obtain frequent itemsets

def prune(count,itemset,sup_count=2):
    freq_itemset = set()
    infreq_itemset = set()
    for item,i in zip(itemset,range(len(itemset))):
        # if the count is greater than support count, it is added into frequent itemsets
        if count[i]>=sup_count:
            freq_itemset.add(item)
        else:
            infreq_itemset.add(item)
    return freq_itemset,infreq_itemset 


# +
def apriori(number_itemset,df,min_sup):
    
# Generating 1-itemset by obtaining unique values and pruning using min_support

# Obtaining unique values

    comb1_list = list((df['0'].append(df['1']).append(df['2']).append(df['3']).append(df['4'])).unique())
    comb1_list.remove(np.nan)
    comb1_set = set()
    for item in comb1_list:
        if item:
            comb1_set.add(frozenset([item]))

# pruning using min_support
    
    count1 = freq(df,comb1_set)
    freq_itemset1,infreq_itemset1 = prune(count1,comb1_set,min_sup)
   
    if number_itemset == 1:
        return freq_itemset1
    
# Generating n-itemset
    all_freq_itemset = list()
    all_freq_itemset.append(list(freq_itemset1))
    freq_itemset = freq_itemset1
    infreq_itemset = infreq_itemset1
    comb_set = comb1_set
    
    for i in range(2,number_itemset+1):
        # joining frequent itemsets
        joined_set = join(freq_itemset,i)
        # Candidate set is created by removing infrequent itemsets
        candidate_set = candidate(infreq_itemset,joined_set)
        # support counts of candidate set is obtained
        count = freq(df,candidate_set)
        # support count is used to prune by comparing with minimum support
        freq_itemset,infreq_itemset = prune(count,candidate_set,min_sup)
        
        if freq_itemset:
            all_freq_itemset.append(list(freq_itemset))
        
    return all_freq_itemset
# -



# ### Illustration of Apriori algorithm to generate frequent item-sets: 

f_itemset_apriori_example = apriori(3,df_example,2)


f_itemset_apriori_example

f_itemset_apriori = apriori(5,df,280)

f_itemset_apriori

associations(df,f_itemset_apriori,50)

#
# ## FP-Growth Algorithm: Use FP-Growth algorithm for finding frequent itemsets.



#class of FP TREE node
class TreeNode:
    def __init__(self, node_name,count,parentnode):
        self.name = node_name
        self.count = count
        self.node_link = None
        self.parent = parentnode
        self.children = {}
        
    def __str__(self, level=0):
        ret = "\t"*level+repr(self.name)+"\n"
        for child in self.children:
            ret += (self.children[child]).__str__(level+1)
        return ret

    def __repr__(self):
        return '<tree node representation>'
    
    def increment_counter(self, count):
        self.count += count


# Reading Data - flexible to use txt or csv file which reads the line and strips the unnecessary data, split and form a list.
# The FM creates a list of Transaction Database
def read_as_list(file):
    list_out = list()
    
    with open(file) as f:
        row_lines = f.readlines()
   
    1for i in row_lines:
        single_line = i.strip().strip(",")
        list_out.append(single_line.split(','))
        
    return list_out


# To convert initial transaction into frozenset
# Creating a frozen dictionary of Database(transactions) and counting the occurences of transaction - to be used to generate frequent itemsets
def create_frozen_set(database_list):
    dict_frozen_set = {}
    for Tx in database_list:
        if frozenset(Tx) in dict_frozen_set.keys():
            dict_frozen_set[frozenset(Tx)] += 1
        else:
            dict_frozen_set[frozenset(Tx)] = 1
    return dict_frozen_set


#The FP Tree is created using ordered sets
def add_tree_nodes(item_set, fptree, header_table, count):
    if item_set[0] in fptree.children:
        fptree.children[item_set[0]].increment_counter(count)
    else:
        fptree.children[item_set[0]] = TreeNode(item_set[0], count, fptree)

        if header_table[item_set[0]][1] == None:
            header_table[item_set[0]][1] = fptree.children[item_set[0]]
        else:
            add_node_link(header_table[item_set[0]][1], fptree.children[item_set[0]])

    if len(item_set) > 1:
        add_tree_nodes(item_set[1::], fptree.children[item_set[0]], header_table, count)


#The node link is added
def add_node_link(previous_node, next_node):
    while (previous_node.node_link != None):
        previous_node = previous_node.node_link

    previous_node.node_link = next_node


# +
# Generate Frequent Pattern tree
def generate_FP_tree(dict_frozen_set, min_sup):
            
# Creating header table - get previous counter using 'get' and then add that value to the row in consideration to obatin count of each unique item in DB    
    header_table = {}
    for frozen_set in dict_frozen_set:
        for key_item in frozen_set:
            header_table[key_item] = header_table.get(key_item,0) + dict_frozen_set[frozen_set]

# pruning using min_sup to retain only frequent 1-itemsets
    for i in list(header_table):
        if header_table[i] < min_sup:
            del(header_table[i])

# Obtaining only keys which are frequent itemsets
    frequent_itemset = set(header_table.keys())

    if len(frequent_itemset) == 0:
        return None, None

    for j in header_table:
        header_table[j] = [header_table[j], None]
        
    Tree = TreeNode('Null',1,None)
    for item_set,count in dict_frozen_set.items():
        frequent_tx = {}
        for item in item_set:
            if item in frequent_itemset:
                frequent_tx[item] = header_table[item][0]
        if len(frequent_tx) > 0:
            #the transaction itemsets are ordered with respect to support
            ordered_itemset = [v[0] for v in sorted(frequent_tx.items(), key=lambda p: p[1], reverse=True)]
            #the nodes are updated into tree
            add_tree_nodes(ordered_itemset, Tree, header_table, count)
    return Tree, header_table
# -



# #### Mining Frequent item-sets by using generated FP Tree

#FP Tree is traversed upwards
def traverse_fptree(leaf_Node, prefix_path):
    if leaf_Node.parent != None:
        prefix_path.append(leaf_Node.name)
        traverse_fptree(leaf_Node.parent, prefix_path)


#returns conditional pattern base(prefix paths)
def find_prefix_path(base_path, tree_node):
    Conditional_patterns_base = {}

    while tree_node != None:
        prefix_path = []
        traverse_fptree(tree_node, prefix_path)
        if len(prefix_path) > 1:
            Conditional_patterns_base[frozenset(prefix_path[1:])] = tree_node.count
        tree_node = tree_node.node_link

    return Conditional_patterns_base


#Condtional FP Tree and Condtional Pattern Base is recursively mined
def mining(fptree, header_table, min_sup, prefix, frequent_itemset):
    FPGen = [v[0] for v in sorted(header_table.items(),key=lambda p: p[1][0])]
    for base_path in FPGen:
        all_frequentset = prefix.copy()
        all_frequentset.add(base_path)
        #appending frequent itemset
        frequent_itemset.append(all_frequentset)
        #obtain conditional pattern bases for itemsets
        Conditional_pattern_bases = find_prefix_path(base_path, header_table[base_path][1])
        #Conditional FP Tree generation
        Conditional_FPTree, Conditional_header = generate_FP_tree(Conditional_pattern_bases,min_sup)

        if Conditional_header != None:
            mining(Conditional_FPTree, Conditional_header, min_sup, all_frequentset, frequent_itemset)





# ### Illustration of FP Growth algorithm to generate frequent item-sets: 

# Creating FP Tree and header table for the example dataset
# parameters - input list(frozenset), minimum support count value
fptree_example, header_table_example = generate_FP_tree(create_frozen_set(input_list_example), 2)

# Display of Tree showing it as object - tree node representation
fptree_example

# printing string values of a tree
str(fptree_example)

# printing FP Tree
print(fptree_example)

# Displaying header table
header_table_example

# function call to write FP tree into a file
write_tree("fptreeexample.txt",fptree_example)

# Mining to obtain frequent itemsets
all_frequent_itemsets_example = []
#call function to mine all ferquent itemsets
mining(fptree_example, header_table_example, 2, set([]), all_frequent_itemsets_example)

# Display frequent itemsets
all_frequent_itemsets_example

associations(df,[all_frequent_itemsets_example],50)

# ##### Testing on Dataset

fptree, header_table = generate_FP_tree(create_frozen_set(input_list), 200)

fptree

str(fptree)

print(fptree)

header_table

# function call to write FP tree into a file
write_tree("fptree.txt",fptree)

# Mining to obtain frequent itemsets
all_frequent_itemsets_fp = []
#call function to mine all ferquent itemsets
mining(fptree, header_table, 200, set([]), all_frequent_itemsets_fp)

all_frequent_itemsets_fp

#  
# ## Experiment on the Dataset : Apply your associated rule mining algorithms to the dataset and show some interesting rules.

associations(df_example,freq_itemsets_example,50)

associations(df_example,freq_itemsets_example,70)

associations(df_example,freq_itemsets_example,60)

# ##### Testing on dataset

associations(df,freq_itemsets2,50)

associations(df,freq_itemsets4,50)

associations(df,freq_itemsets5,45)

associations(df,freq_itemsets6,45)

#

# ##### The modular approach of coding is done so the function can be reused for different algorithms. Sufficient comments are added to make the code readable

#
# ## Run-Time Performance

# +
# Measuring run-time performance of generating frequent itemsets
#1. Brute force approach
# -

start1 = time.time()
freq_itemsets1 = brute_force_frequent_itemset(5,df,200)
end1 = time.time()
print("The time taken by Brute force algorithm implemented: ")
print(end1-start1)

# +
#2. Apriori approach
# -

start2 = time.time()
f_itemset_apriori = apriori(5,df,200)
end2 = time.time()
print("The time taken by Apriori algorithm implemented: ")
print(end2-start2)

# +
#3. FP Growth approach
# -

start3 = time.time()
fptree, header_table = generate_FP_tree(create_frozen_set(input_list), 200)
all_frequent_itemsets_fp = []
mining(fptree, header_table, 200, set([]), all_frequent_itemsets_fp)
end3 = time.time()
print("The time taken by FP Growth algorithm implemented: ")
print(end3-start3)

all_frequent_itemsets_fp

# From the above analysis, the FP Growth runs faster compared to other two algorithms by recursively computing.
# Brute Force works slower by making use of all combinations, Apriori works faster compared to Brute Force by 
# making use of only prior information(Frequent sets) instead of all the combinations. It is generally slower
# because of database scanning at each step of pruning



StarcoderdataJupyterScriptsDedupFiltered