Beyond Frequency: Efficient High-Utility Pattern Discovery in Mobile Commerce
Efficient algorithms for discovering high utility user behavior patterns in mobile commerce environments
This paper introduces the novel problem of High-Utility Mobile Sequential Pattern (UMSP) mining, which integrates spatial moving paths with purchasing utility (profit). It proposes three algorithms—UMSPL (level-wise), UMSPT(DFG), and UMSPT(BFG) (tree-based)—to identify behavioral patterns that are both frequent and highly profitable in mobile commerce.
TL;DR
In the world of mobile commerce, knowing where customers go is useful; knowing where they spend the most money is invaluable. This paper bridges the gap between Mobility Pattern Mining and Utility Mining. It proposes the UMSPT series of algorithms which use a specialized tree structure (MTS-Tree) to find sequences of movements and purchases that yield the highest profit, even if those behaviors aren't the most frequent.
The "Diamond Ring" Problem
Traditional mining algorithms are obsessed with frequency. If 1,000 people buy a 5,000 diamond ring after walking path A->B, a frequency-based model (like Apriori or TJPF) identifies the gum-purchasing as the "significant" pattern.
The authors argue that in a business context, Support Value. The challenge is that "Utility" (Profit) does not satisfy the downward closure property (i.e., a subset of a high-profit pattern isn't necessarily high-profit), which makes the search space explode mathematically.
Methodology: The MTS-Tree and SWDC
To solve the search space problem, the authors implement the Sequence Weighted Downward Closure (SWDC) property. Instead of using raw profit, they use "Sequence Weighted Utilization" (SWU) as an upper bound to safely prune patterns that can never reach the utility threshold.
The MTS-Tree Architecture
The core innovation is the Mobile Transaction Sequence Tree (MTS-Tree). Unlike standard FP-Trees, it must store:
- Locations as nodes.
- Itemsets purchased at those locations.
- SIDs (Sequence IDs) for tracking.
- Path Tables to record "empty" travel (moving between locations without buying anything).
Figure: The MTS-Tree captures the complex relationship between movement paths and purchasing events.
The Two Generation Strategies
- UMSPT(DFG): Uses a Depth-First approach. It's intuitive but generates many conditional trees.
- UMSPT(BFG): Uses a Breadth-First approach with a "Possible Succeeding Node Check." This is the superior method as it prunes useless candidate paths much earlier in the process.
Performance & Benchmarks
The authors compared their algorithms against MSP (an extension of the previous SOTA, TJPF).
Execution Time vs. Minimum Utility
As the profit threshold (Minimum Utility) increases, the UMSPT algorithms become significantly faster because the pruning strategies (SWDC) become more aggressive. The traditional MSP algorithm remains slow because it doesn't consider utility until the very last step.
Figure: Execution time comparison across different utility thresholds.
Scalability
While the tree-based methods (UMSPT) require more memory to store the node links and path tables, their execution time scales linearly with the database size, whereas level-wise methods (UMSPL) suffer from the "candidate explosion" problem when sequences grow longer or more complex.
Critical Insight & Conclusion
The shift from What is frequent? to What is profitable? is a major transition for behavioral informatics.
The Takeaway: For developers building Location-Based Services (LBS) or retail analytics platforms, the UMSPT(BFG) algorithm offers the best balance of speed and accuracy. The primary limitation to consider is memory overhead—if you are working with extremely limited RAM, the level-wise UMSPL might be a necessary, albeit slower, alternative.
Future research in this niche is likely to head toward incremental mining, where the MTS-Tree can be updated in real-time as users move through a retail environment without re-scanning the entire history.