Sequential Pattern Mining with GSP and PrefixSpan

Define a sequence before counting it

You will count ordered subsequences, distinguish events from itemsets and understand how GSP and PrefixSpan search the pattern space.

• Define sequence, event, itemset and subsequence support.
• Explain GSP candidate generation and Apriori-style pruning.
• Explain PrefixSpan projected databases and prefix growth.
• Apply length, gap, time and item constraints to produce usable patterns.

Order needs a reliable clock

A sequence belongs to one entity and contains timestamped events. Several items may occur in one event, such as products in a single order. Decide how ties, repeated events, sessions and missing timestamps are handled before mining.

A pattern A then B appears if A can be matched before B, not necessarily next to it. Contiguous patterns require adjacency. Maximum-gap and time-window constraints express how far apart matches may be. These definitions can change support dramatically.

GSP extends Apriori to sequences. It joins frequent length-k sequences into candidates, prunes those with infrequent subsequences and scans the database for support. Candidate growth becomes expensive.

PrefixSpan grows frequent prefixes in projected databases containing only suffixes after each prefix occurrence. It avoids generating many impossible candidates. A projected database still needs careful memory management on large or repetitive sequences.

Constraints improve both computation and meaning. Anti-monotone constraints can prune extensions early. Monotone constraints may become true as a pattern grows. Domain rules such as ‘must end in purchase’ focus the output but should be declared before reviewing interesting cases.

Count an ordered two-event pattern

This function checks whether a pattern is a subsequence. It does not require adjacent events.

Find support for view then purchase

sequences = {
    "u1": ["view", "search", "purchase"],
    "u2": ["search", "view", "leave"],
    "u3": ["view", "purchase"],
    "u4": ["view", "search", "view", "purchase"],
}

def contains_subsequence(sequence, pattern):
    position = 0
    for event in sequence:
        if event == pattern[position]:
            position += 1
            if position == len(pattern):
                return True
    return False

pattern = ["view", "purchase"]
matched = [entity for entity, sequence in sequences.items()
           if contains_subsequence(sequence, pattern)]
support = len(matched) / len(sequences)

print("pattern:", " -> ".join(pattern))
print("matched:", matched)
print(f"support: {support:.2f}")

Expected sequence support

pattern: view -> purchase
matched: ['u1', 'u3', 'u4']
support: 0.75

User u1 matches even though search occurs between view and purchase. Add an adjacency or gap rule if that is not the intended definition.

Sequence errors that change the story

Most defects come from event construction rather than the mining algorithm.

• Sorting timestamps as strings can put dates or time zones in the wrong order.
• One prolific entity can dominate occurrence counts. Sequence support normally counts entities once per pattern.
• Including events after the outcome cutoff leaks the future.
• Treating simultaneous items as ordered invents a sequence that was not observed.

Mine constrained learning paths

Create synthetic student sequences from lesson start, quiz retry, hint use and completion events.

• Declare session, tie and gap rules.
• Count all length-two patterns above a support threshold.
• Require one set to end in completion and compare with unrestricted output.
• Confirm the strongest pattern on a later time period.

Sequence evidence

• Event-construction specification.
• Pattern table with entity counts.
• One example showing how a gap rule changes support.

Official references and further reading

• SPMF PrefixSpan documentation (Primary project explanation and format examples)
• SPMF GSP documentation (Primary project explanation for GSP)

Review note for Sequential Pattern Mining with GSP and PrefixSpan: recheck the linked documentation after a dependency changes the relevant API, metric or modelling assumption, then record the tested version beside your result.