Sequential Pattern Mining

Unlike standard market basket analysis, the order of events is the primary analytical dimension. An itemset is defined not just by co-occurrence but by a strict chronological sequence.

• A pattern <(A), (B)> is distinct from <(B), (A)>.
• Algorithms enforce a total or partial ordering on timestamps.
• This captures causality and behavioral progression, such as a user adding an item to a cart before applying a coupon.

The minimum support threshold is the primary constraint used to combat combinatorial explosion. A sequence is considered 'frequent' only if it appears in a user-specified percentage of the total sequence database.

• Defined as support(S) = count(S) / total_sequences.
• Leverages the Apriori property: if a sequence is infrequent, all its supersequences are also infrequent.
• This anti-monotonicity enables efficient candidate generation and pruning in algorithms like GSP and PrefixSpan.

Patterns can be defined with varying strictness regarding time gaps between constituent events.

• Contiguous: Events must occur consecutively with no intermediate events in the source sequence.
• Non-Contiguous: Allows arbitrary gaps between matched events, capturing long-range dependencies.
• Max-Gap Constraint: A time window or event-count limit that prevents matching events separated by unrealistic durations, ensuring the pattern remains temporally relevant.

A sequence is an ordered list of elements, where each element is a set of items occurring simultaneously.

• Intra-element: Items within the same brackets (A, B) are unordered and occur at the same timestamp.
• Inter-element: The brackets themselves are ordered <(A, B), (C)>.
• This dual-level structure allows mining patterns like 'a user viewed a product page and added a warranty simultaneously, then later purchased the bundle,' capturing both set-based and sequential logic.

To reduce output redundancy, mining often targets lossless compression formats instead of the full set of frequent sequences.

• Closed Sequential Pattern: A frequent sequence with no frequent super-sequence having identical support. It represents the exact set of supporting sequences.
• Maximal Sequential Pattern: A frequent sequence with no frequent super-sequence at all.
• These representations drastically reduce the result set size while preserving complete frequency information, critical for interpretability in user journey mapping.

Modern algorithms like PrefixSpan use a pattern-growth approach rather than candidate-generation-and-test.

• The database is recursively projected into smaller, partitioned datasets based on the current prefix.
• This divide-and-conquer strategy avoids the exponential candidate generation of Apriori-based methods.
• It allows for the push-down of user-defined constraints (e.g., item price > $100, specific category taxonomies) directly into the mining loop, drastically improving runtime efficiency.

The foundational algorithm for sequential pattern mining that extends the Apriori principle to ordered data. It operates in distinct phases:

• Sort Phase: Converts the database into customer sequences ordered by transaction time.
• Litemset Phase: Finds all frequent itemsets using a minimum support threshold.
• Transformation Phase: Maps each transaction to the set of frequent itemsets it contains.
• Sequence Phase: Iteratively generates candidate k-sequences from frequent (k-1)-sequences and prunes those with infrequent subsequences.
• Maximal Phase: Removes sequences that are contained within other frequent sequences. The key insight is the downward closure property: if a sequence is frequent, all its subsequences must also be frequent, enabling efficient candidate pruning.

A pattern-growth method that avoids the costly candidate generation of Apriori-based approaches. It works by:

• Divide-and-Conquer: Recursively projects the sequence database into smaller, prefix-based projected databases.
• Prefix Projection: For a given prefix pattern, only the suffix subsequences that follow the prefix are retained, dramatically shrinking the search space.
• Bi-Level Projection: Uses pseudo-projection (pointer-based) when the database fits in memory and physical projection (copy-based) for disk-resident data. PrefixSpan is significantly faster than GSP and AprioriAll on large, dense datasets because it never generates or tests candidate sequences that don't exist in the projected database.

An Apriori-like algorithm that introduces time constraints to sequential pattern mining. GSP adds three critical parameters beyond minimum support:

• Max-Gap: The maximum allowed time interval between consecutive elements in a discovered sequence.
• Min-Gap: The minimum required time interval between consecutive elements.
• Sliding Window: A time window within which events are considered part of the same transaction. These constraints prevent discovering sequences where events are separated by unrealistic time spans (e.g., a purchase journey spanning years). GSP performs a breadth-first search, generating candidate (k+1)-sequences by merging frequent k-sequences that share a common (k-1)-suffix.

A vertical database format algorithm that decomposes the search space using equivalence classes based on common prefixes. Key innovations:

• ID-List Representation: Each sequence is represented as a list of (sequence-ID, event-ID) pairs, enabling efficient support counting through temporal joins of ID-lists.
• Lattice-Based Search: Organizes the search space into a lattice where each equivalence class contains all sequences sharing the same prefix.
• Breadth-First or Depth-First: Can traverse the lattice in either order, with depth-first offering better memory locality. SPADE excels on databases with many distinct items but relatively short sequences, as ID-list intersections become the dominant cost factor.

Two critical compression strategies to reduce the explosion of redundant patterns:

• Closed Sequential Pattern: A frequent sequence that has no proper super-sequence with identical support. Mining closed patterns (e.g., CloSpan, BIDE) preserves complete frequency information while eliminating redundancy.
• Maximal Sequential Pattern: A frequent sequence that has no frequent super-sequence. Algorithms like MSPS and DIMASP find only the longest patterns, providing a lossy but highly compact summary. The distinction matters: closed patterns retain all support information for reconstructing the full set, while maximal patterns only indicate what is frequent without exact counts. In user behavior modeling, closed patterns are preferred for preserving the statistical significance of sub-patterns.

Extends pattern discovery by incorporating domain-specific constraints beyond support thresholds to focus on actionable patterns:

• Item Constraints: Specify which items must or must not appear in patterns (e.g., only patterns containing a 'purchase' event).
• Length Constraints: Bound the minimum or maximum number of elements in a sequence.
• Regular Expression Constraints: Define valid pattern structures using regex-like grammars, enabling complex temporal logic.
• Aggregate Constraints: Filter based on derived metrics like average inter-event time or total sequence duration. Constraint pushing techniques integrate these filters directly into the mining process rather than as post-processing, dramatically reducing the search space. This is essential for next-best-action models where only patterns ending in a conversion event are relevant.