Sequential Pattern Mining: GSP vs. PrefixSpan

A from-scratch implementation of the Generalized Sequential Pattern (GSP) algorithm for mining frequent sequential patterns from transaction data, followed by a rigorous performance comparison against PrefixSpan across varying support thresholds and sequence lengths.

What it does

Part 1 — GSP implementation: a recursive GSP algorithm built from scratch (no external sequence-mining library), applied to transaction data to discover frequent subsequences — combinations of items that recur together across transactions, in a preserved but not necessarily consecutive order.

Part 2 — GSP vs. PrefixSpan benchmark: the custom GSP implementation is compared against PrefixSpan (a pattern-growth algorithm that avoids candidate generation by building projected databases) across 9 parameter combinations — minimum support ∈ {2, 5, 10} × sequence length ∈ {2, 3, 4} — measuring execution time, memory usage, and number of patterns extracted for each.

Key findings

From the full experimental run (see report/ for complete analysis):

Metric	GSP	PrefixSpan
Execution time (min support=2, seq length=2)	3.132s	0.012s
Memory usage (min support=2)	103,656 KB	66,696 KB
Patterns extracted (min support=2, seq length=2)	890	220

• PrefixSpan is dramatically faster than GSP across every tested configuration — the gap is most pronounced at low support thresholds, where GSP's candidate generation explodes combinatorially.
• GSP extracts more patterns than PrefixSpan in every case, but at substantially higher computational cost.
• Lower minimum support → higher cost for both algorithms, as expected, but GSP's cost grows much faster than PrefixSpan's.
• Recommendation: PrefixSpan for large-scale/production use where efficiency matters; GSP remains useful for smaller datasets or when maximizing pattern recall matters more than speed.

Tech stack

Python · pandas · NumPy · Matplotlib · prefixspan · tracemalloc (memory profiling)

Evidence it runs

Real output generated by running both parts end-to-end:

What's in this repo

• gsp_prefixspan_mining.py — full implementation: custom GSP algorithm, pattern visualization, and the GSP vs. PrefixSpan benchmark across 9 parameter combinations.
• data/sample_transaction_data.csv — a synthetic sample transaction dataset (1,000 transactions, matching the Transaction / Items Purchased / Class structure the script expects) included so the code is runnable end-to-end. The key findings above were obtained on the original dataset used for this project, not this sample.
• screenshots/ — real chart output from running the script against the sample data.
• report/ — full write-up: methodology, complete results tables, and analysis from the original experimental run.

How to run it

git clone https://github.com/<your-username>/sequential-pattern-mining-gsp.git
cd sequential-pattern-mining-gsp

pip install -r requirements.txt
python gsp_prefixspan_mining.py

Runs both parts in sequence: GSP pattern mining with a bar chart of the top 10 sequences, then the full GSP vs. PrefixSpan benchmark with time and pattern-count comparison charts. To run against your own data, replace data/sample_transaction_data.csv with a CSV containing Transaction, Items Purchased (comma-separated items), and Class columns.

License

MIT