<jupyter_start><jupyter_text>Data Mining Assignment 1 - Pattern Mining<jupyter_code>import pandas as pd
import itertools
from tqdm import tqdm, trange
import matplotlib.pyplot as plt
import seaborn as sns
from time import time
import numpy as np
import itertools, collections<jupyter_output><empty_output><jupyter_text>Task 1: Implement Apriori<jupyter_code>class Itemset:
    def __init__(self, items):
        self.set = set(items)  # set to easily check if a set is a subset
        self.sorted = sorted(self.set)  # sorted list to create candidates
        self.products = set(t[0] for t in self.set)
        self.duplicate_product = len(self.products) < len(self.set)
    
    def add(self, items):
        # add items and create a new itemset
        return Itemset(self.sorted + list(items))
    
    def permutation_splits(self):
        # This method can be used AFTER apriori to create (frequent) subsets of a frequent itemset as part of an association rule
        # all combinations from size 1 to len(itemset) and flatten list
        # for example: itemset {1, 2, 3} results into [{1} -> {2, 3}, {2} -> {1, 3}, {3} -> {1, 2}, {1, 2} -> {3}, {1, 3} -> {2}, {2, 3} -> {1}]
        # (2^n - 2) rules will be created
        combinations = sum([list(itertools.combinations(self.sorted, i)) for i in range(1, len(self))], [])
        return [(Itemset(i1), Itemset(i2)) for i1, i2 in zip(combinations, reversed(combinations))]

    def get_association_rules(self):
        if self.duplicate_product:
            return []
        return [AssociationRule(i1, i2) for i1, i2 in self.permutation_splits()]

    def __len__(self):
        return len(self.set)
    
    def __str__(self):
        # makes sure the represented set is ordered
        if len(self.sorted[0]) == 1:
            return '{' + str([t[0] for t in self.sorted])[1:-1] + '}'
        return '{' + str(self.sorted)[1:-1] + '}'
    
    def __repr__(self):
        return str(self)
    
    def __hash__(self):
        # makes the itemset hashable so it can be used a a key in a dict
        return hash(tuple(self.sorted))
    
    def __eq__(self, other):
        if isinstance(other, Itemset):
            return self.set == other.set
        return False
    
    def __iter__(self):
        return iter(self.sorted)
    
class AssociationRule:
    def __init__(self, X, Y):
        # stores two itemsets X and Y such that X -> Y
        self.X = X if isinstance(X, Itemset) else Itemset(X)
        self.Y = Y if isinstance(Y, Itemset) else Itemset(Y)
        
    def __str__(self):
        return f'{self.X} -> {self.Y}'
    
    def __repr__(self):
        return str(self)
    
    def v_map(self, f):
        return AssociationRule([f(t) for t in self.X.sorted], [f(t) for t in self.Y.sorted])
    
    def __hash__(self):
        # makes the itemset hashable so it can be used a a key in a dict
        return hash((self.X, self.Y))
    
    def __eq__(self, other):
        if isinstance(other, AssociationRule):
            return self.X == other.X and self.Y == other.Y
        return False

def apriori(_baskets: list[Itemset], _products: list[tuple[Itemset, int]], minsup: int, minconf: float):
    t0 = time()
    L = []
    n_transactions = len(_baskets)
    
    # k=1, generate a list of tuples [({product_id}, support)] where support >= minsup
    L.append([(itemset, support) for (itemset, support) in _products if support >= minsup])
    
    # k=2, for the first pass we will extract all itemsets of size 2 from the baskets and put them in a dict.
    # This deviates from the pseudocode from the slides because generating 5000*5000=25M pairs and 
    # checking those against the whole databese takes multiple years..
    candidates = collections.Counter(Itemset(duo) for itemset in tqdm(_baskets, desc=f'k=2') for duo in itertools.combinations(itemset.sorted, 2))

    k2 = [(c, support) for c, support in candidates.items() if support >= minsup and not c.duplicate_product]
    L.append(k2)
    
    k=3
    # k >= 3, after this we will generate candidate itemsets and check them against the database
    while len(L[k-2]) > 0:
        # generate candidates (N^2)
        Lk = L[k-2]
        candidates = []
        for (i1, _), (i2, _) in itertools.combinations(L[k-2], 2):
            if i1.sorted[:-1] == i2.sorted[:-1] and i2.sorted[-1][0] not in i1.products:
                candidates.append(i1.add(i2.sorted[-1:]))
        
        if len(candidates) == 0:
            break
        
        # prune transactions to speed up the process
        _baskets = [itemset for itemset in _baskets if len(itemset) >= k]
        
        # get support
        support = [sum(c.set.issubset(itemset.set) for itemset in _baskets) for c in tqdm(candidates, desc=f'k={k}')]
        
        L.append([(itemset, s) for itemset, s in zip(candidates, support) if s >= minsup])
        k += 1

    # flatten L and create a dict to quickly get the support of itemsets
    get_support = {itemset: support for itemset, support in sum(L, [])}
    frequent_itemsets = sum(L[1:], []) # concat all itemsets with size >=2
    
    rules = []
    for itemset, support_XUY in frequent_itemsets:
        for rule in itemset.get_association_rules():
            support_X = get_support[rule.X]
            confidence = support_XUY / support_X
            X_prob = support_X / n_transactions
            lift = confidence / X_prob
            if confidence > minconf:
                rules.append((rule, len(itemset), support_X, support_XUY, confidence, lift))
                
    df = pd.DataFrame(rules, columns=['rule X -> Y', 'rule size', 'X support', 'rule support', 'confidence', 'lift'])
    df = df.astype({'rule size':'str'}) # transform rule size to categorial data by casting to str
    df['log(lift)'] = np.log(df['lift'])
    df['confidence'] = df['confidence'].apply(lambda x: round(x, 3))
    df['lift'] = df['lift'].apply(lambda x: round(x, 3))
    
    print(f'\nCompleted in {round(time()-t0, 2)} seconds.')
    return df<jupyter_output><empty_output><jupyter_text>Run on dataset<jupyter_code>dataset = pd.read_csv("dataset.csv")

baskets = dataset.groupby('user_id').product_id.apply(lambda x: Itemset([(y,) for y in x])).tolist()

products = dataset.groupby('product_id').count().reset_index()[['product_id', 'user_id']]
products = [(Itemset([(product_id,)]), support) for product_id, support in tqdm(list(products.itertuples(index=False, name=None)), desc='k=1')]

result = apriori(baskets, products, minsup=4, minconf=0.1)<jupyter_output>k=1: 100%|███████████████████████████████████████████████████████████████████| 11678/11678 [00:00<00:00, 154037.28it/s]
k=2: 100%|████████████████████████████████████████████████████████████████████| 13137/13137 [00:00<00:00, 53321.40it/s]
k=3: 100%|██████████████████████████████████████████████████████████████████████████| 533/533 [00:00<00:00, 957.60it/s]
k=4: 100%|███████████████████████████████████████████████████████████████████████████| 17/17 [00:00<00:00, 1708.72it/s]
k=5: 100%|███████████████████████████████████████████████████████████████████████████████████████| 1/1 [00:00<?, ?it/s]<jupyter_text>We find 659 association rules for `minsup=4` and `minconf=0.0`<jupyter_code>result[['rule X -> Y', 'rule support', 'confidence', 'lift']]<jupyter_output><empty_output><jupyter_text>Task 2: top 10 in terms of support<jupyter_code>r = result.sort_values(by=['rule support'], ascending=False)[['rule X -> Y', 'rule support', 'confidence', 'lift']].head(10)
r.to_csv('results/task2_support_top10.csv', index=False)
r<jupyter_output><empty_output><jupyter_text>Task 3: Interesting rules The distribution of all association rules with support >= 2. Given an association rule X->Y, the rule size (colors) equals XUY.I will ouput the interesting clusters below in a dataframe.<jupyter_code>ax = sns.scatterplot(data=result, x='rule support', y='confidence', hue='rule size')
fig = ax.get_figure()
fig.savefig("results/task3_dist.png") 
ax = sns.scatterplot(data=result, x='rule support', y='confidence', hue='log(lift)')
fig = ax.get_figure()
fig.savefig("results/task3_lift.png") 
ax = sns.scatterplot(data=result, x='log(lift)', y='confidence', hue='rule support')
fig = ax.get_figure()
fig.savefig("results/task3_lift_2.png") 
r = result[result['rule support'] > 40].sort_values(by=['confidence'], ascending=False)[['rule X -> Y', 'rule support', 'confidence', 'lift']].head(3)
intersting_index = r.index.tolist()
r
r = result[result['rule support'] > 10].sort_values(by=['confidence'], ascending=False)[['rule X -> Y', 'rule support', 'confidence', 'lift']].head(5)
intersting_index = intersting_index + r.index.tolist()
r
r = result.sort_values(by=['confidence', 'rule size'], ascending=False)[['rule X -> Y', 'rule support', 'confidence', 'lift']].head(2)
intersting_index = intersting_index + r.index.tolist()
r
result['interesting'] = ''
result.loc[intersting_index, 'interesting'] = 'Top 10'
sns.scatterplot(data=result, x='rule support', y='confidence', hue='interesting')<jupyter_output><empty_output><jupyter_text>Interesting rules<jupyter_code>r = result.iloc[intersting_index].sort_values(by=['lift'], ascending=False)[['rule X -> Y', 'rule support', 'confidence', 'lift']]
r.to_csv('results/task3_interesting_top10.csv', index=False)
r<jupyter_output><empty_output><jupyter_text>Task 4: Additional The itemset also works with tuples of data<jupyter_code>event_to_order = {'view': 0, 'cart': 1, 'purchase': 2, 'remove_from_cart': -1}
order_to_event = {v: k for k, v in event_to_order.items()}

dataset = pd.read_csv("dataset.csv")
dataset['event_type_order'] = dataset['event_type'].apply(lambda x: event_to_order[x])
dataset = dataset[dataset['event_type_order'] >= 0]
dataset['interaction'] = list(zip(dataset.product_id, dataset.event_type_order))
def complete_data(x: Itemset):
    extra_data = []
    for product_id, order in x.sorted:
        for i in range(order):
            extra_data.append((product_id, i))
    return x.add(extra_data)

baskets = dataset.groupby('user_id')['interaction'].apply(Itemset).apply(complete_data).tolist()
products = [(Itemset([k]), v) for k, v in collections.Counter(itertools.chain(*baskets)).items()]
result = apriori(baskets, products, minsup=4, minconf=0.1)
result['rule X -> Y'] = result['rule X -> Y'].apply(lambda x: x.v_map(lambda a: (a[0], order_to_event[a[1]])))
result
ax = sns.scatterplot(data=result, x='rule support', y='confidence', hue='rule size')
fig = ax.get_figure()
fig.savefig("results/task4_dist.png") 
ax = sns.scatterplot(data=result, x='rule support', y='confidence', hue='log(lift)')
fig = ax.get_figure()
fig.savefig("results/task4_lift.png") 
r = result[result['rule support'] > 20].sort_values(by=['lift'], ascending=False)[['rule X -> Y', 'rule support', 'confidence', 'lift']].head(10)  # [result['rule support'] > 30]
r.to_csv('results/task4_top10.csv', index=False)
r<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.17818248375583418, 'fraction_numerical': 0.023977303926054728, 'mean_word_length': 3.9425599276345547, 'pattern_counts': {'":': 0, '<': 38, '<?xml version=': 0, '>': 66, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '114387', 'license': 'Apache-2.0', 'n_tokens_mistral': 4199, 'n_tokens_neox': 3800, 'n_words': 953, 'path': 'assignment_1/code.ipynb', 'repo_name': 'm4urin/2001WETGDT-Data-mining', 'size': '10927'}