<jupyter_start><jupyter_text>Sequential Pattern Mining PrefixSpan AlgorithmPrefixSpan extracts frequent sequences with depth-first search **(DFS)** by executing SDB projection operations **`recursively`**.<jupyter_code>import pandas as pd
import numpy as np
import sys
from time import time<jupyter_output><empty_output><jupyter_text>1. Reading and Processing the Dataset<jupyter_code>df = pd.read_csv("paths_finished_wiki.csv")
df.head(5)
def data_preprocessing(df):
    res = []
    for path in df:
        elements = path.replace('<', '').replace('  ', ' ').lower().split(';') # separator
        tmp = []
        for element in elements:
            tmp.append(element.split())
        res.append(tmp)
    return res
data = data_preprocessing(df.path)<jupyter_output><empty_output><jupyter_text>2. PrefixSpan Algorithm Implementation **An overview of how the algorithm works**  A simple example to follow along Note: this example exist in the slides of this subject<jupyter_code>test_case = [[['a'], ['a', 'b', 'c'], ['a', 'c'], ['d'], ['c', 'f']],
 [['a', 'd'], ['c'], ['b', 'c'], ['a', 'e']],
 [['c', 'f'], ['a', 'b'], ['d', 'f'], ['c', 'b']],
 [['e', 'g'], ['a', 'f'], ['c'], ['b'], ['c']]]

sample_data = [
    ['C', 'A', 'G', 'A', 'A', 'G', 'T'],
    ['T', 'G', 'A', 'C', 'A', 'G'],
    ['G', 'A', 'A', 'G', 'T']
]

sample_data =[
[["a"], ["a", "b", "c"], ["a", "c"], ["c"]],
[["a"], ["c"], ["b", "c"]],
[["a", "b"], ["d"], ["c"], ["b"], ["c"]],
[["a"], ["c"], ["b"], ["c"]]
]<jupyter_output><empty_output><jupyter_text>2.1. Find all repeating sequences by  Scanning  the SDB **There are 3 basic cases**:1. The sequence begins with `simultaneously` elements together which we put all together in parentheses, then one of these elements is taken and placed with '**_**'.2. The sequence begins with the '**_**', then the first element of the sequence is simply ignored and the next element is added to the pattern as follows in the next case.3. The sequence starts up with a regular element (as is the case in our dataset), then the strings are scanned normally.<jupyter_code>def calc_frequent_items(sdb, pattern, min_sup):
    if sdb is None:
         return []
    
    if len(pattern) > 0:
        last_element = pattern[-1]
        last_sub_element = last_element[-1]
        
    else:
        last_element = []
    
    freqs = {} 
    p_freqs = {} # p refers to elements -sub_elements- that in parentheses '()'.
    res = []
    for seq in sdb: 
        # case 1
        fseq = seq[0]
        at_beginning = True
        for sub_element in last_element:
            if sub_element not in fseq:
                at_beginning = False
        if at_beginning and len(last_element) > 0:
            pattern_limit = fseq.index(last_sub_element)
            if pattern_limit < len(fseq) - 1:
                for sub_element in fseq[pattern_limit + 1:]:
                    if sub_element in p_freqs.keys():
                        p_freqs[sub_element] += 1
                    else:
                        p_freqs[sub_element] = 1        
        #case 2
        if '_' in seq[0]:
            for sub_element in seq[0][1:]:
                if sub_element in p_freqs:
                    p_freqs[sub_element] += 1
                else:
                    p_freqs[sub_element] = 1
            seq = seq[1:]
            
        #case 3
        visited = [] 
        for element in seq:
            for sub_element in element:
                if sub_element not in visited:
                    visited.append(sub_element)
                    if sub_element in freqs.keys():
                        freqs[sub_element] += 1
                    else:
                        freqs[sub_element] = 1
                        
                        
    for item in freqs.items():
        if item[1] >= min_sup:
            res.append(([item[0]], item[1]))
    for item in p_freqs.items():
        if item[1] >= min_sup:
            res.append((['_',item[0]], item[1]))      
    return sorted(res, key=lambda p: item[0]) #lambda is a virtual function        
fi = calc_frequent_items(test_case,['a'] ,1)
fi<jupyter_output><empty_output><jupyter_text>2.2. Find subsets of sequential patternsThe subsets of sequential patterns can be mined by constructing corresponding projected databases and mine each `recursively`. The projected databases as well as sequential patterns found in them are listed in the following Table<jupyter_code>def generate_SDB(sdb, pattern):
    res = []
    last_element = pattern[-1]
    last_sub_element = last_element[-1]
                        
    for seq in sdb:
        pp_sdb = [] # refers to partial proj. SDB
        
        for element in seq:
            # First Phase: check if the pattern 
            # check if the beginning of the sequence such like <(_ac)>.
            at_beginning = False
            if '_' in element:
                if len(last_element) > 1:
                    if last_element in element:
                        at_beginning = True
            # check if the beginning of the sequence is a normal case such like <ac>.
            else:
                at_beginning = True
                for sub_element in last_element:
                    if sub_element not in element:
                        at_beginning = False
                        break #check if the last element in pattern not at the end of the current element of the sequence
            if at_beginning:
                element_index = seq.index(element)
                pattern_limit_index = element.index(last_sub_element)
                if pattern_limit_index == len(element) - 1:
                    pp_sdb = seq[element_index + 1:]
                else:
                    pp_sdb = seq[element_index:]
                    celem = element[pattern_limit_index:]
                    celem[0] = '_'
                    pp_sdb[0] = celem
                break   
        if len(pp_sdb) != 0:
            res.append(pp_sdb)
    return res
# W = [[['a'],['b'],['c'],['a']]]
gs = generate_SDB(test_case, ['a'])
gs<jupyter_output><empty_output><jupyter_text>A method to concat a new element with the current pattern<jupyter_code>def concat_patterns(p1, p2, s1, s2):
    if p1[0][0] == '_':
            tmp = p1[0]
            p1[0].remove('_')
            p2[-1].extend(tmp)
            p2.extend(p1[1:])
    else:
            p2.extend(p1)
    return (p2, min(s2, s1))<jupyter_output><empty_output><jupyter_text>Based on above, the algorithm of PrefixSpan will be as follows.**Input:** A sequence database `(SDB)`, a starting  values for the pattern and support (\[\], 100000) by deafult and the minimum support `(min_sup)`.**Output:** The complete set of sequential patterns.<jupyter_code>def prefix_span(sdb, pattern,sup, min_sup):
    patterns = []
    
    elements = calc_frequent_items(sdb, pattern, min_sup)
    for element in elements:
        
        p,sup = concat_patterns([element[0]],[pattern], element[1], sup) 
        patterns.append((p,sup))
        p_sdb = generate_SDB(sdb, p)
        p_patterns = prefix_span(p_sdb, p, sup, min_sup)
        patterns.extend(p_patterns)
    return patterns<jupyter_output><empty_output><jupyter_text>A method to display the patterns and its support values<jupyter_code>def print_results(res):    
    fnl_res = []
    for idx, pattern in enumerate(res):

        for element in pattern[0]:
            if len(element) == 0:
                    pattern[0].remove(element)
            for sub_element in element:
                if len(sub_element) == 0:
                    element.remove(sub_element)     
        fnl_res.append({
            'pattern' : str(pattern[0]).replace('[','').replace(']','').replace("\'",'').replace(',','->'),
            'support' : pattern[1]}) 

    return fnl_res
start_time = time()
# res=prefixSpan(data[:5000],[],10000,5)
res=prefix_span(sample_data,[],10000,2)
end_time = time()
elapsed = end_time - start_time
print('Elapsed time is %f seconds.' % elapsed)
print_results(res)
start_time = time()
res=prefix_span(data[:5000],[],10000,5)
# res=prefix_span(test_case,[],10000,2)
end_time = time()
elapsed = end_time - start_time
print('Elapsed time is %f seconds.' % elapsed)
print_results(res)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13317161916312917, 'fraction_numerical': 0.013826561552456033, 'mean_word_length': 2.312977099236641, 'pattern_counts': {'":': 0, '<': 37, '<?xml version=': 0, '>': 41, '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': '124106', 'license': 'MIT', 'n_tokens_mistral': 2634, 'n_tokens_neox': 2501, 'n_words': 733, 'path': 'data_mining_hw1_osama_alhalabi.ipynb', 'repo_name': 'OsamaAlhalabi/Prefix-Span', 'size': '8245'}