Abstract
Personalization in marketing aims at improving the shopping experience of customers by tailoring services to individuals. In order to achieve this, businesses must be able to make personalized predictions regarding the next purchase. That is, one must forecast the exact list of items that will comprise the next purchase, i.e., the so-called market basket. Despite its relevance to firm operations, this problem has received surprisingly little attention in prior research, largely due to its inherent complexity. In fact, state-of-the-art approaches are limited to intuitive decision rules for pattern extraction. However, the simplicity of the pre-coded rules impedes performance, since decision rules operate in an autoregressive fashion: the rules can only make inferences from past purchases of a single customer without taking into account the knowledge transfer that takes place between customers. In contrast, our research overcomes the limitations of pre-set rules by contributing a novel predictor of market baskets from sequential purchase histories: our predictions are based on similarity matching in order to identify similar purchase habits among the complete shopping histories of all customers. Our contributions are as follows: (1) We propose similarity matching based on subsequential dynamic time warping (SDTW) as a novel predictor of market baskets. Thereby, we can effectively identify cross-customer patterns. (2) We leverage the Wasserstein distance for measuring the similarity among embedded purchase histories. (3) We develop a fast approximation algorithm for computing a lower bound of the Wasserstein distance in our setting. An extensive series of computational experiments demonstrates the effectiveness of our approach. The accuracy of identifying the exact market baskets based on state-of-the-art decision rules from the literature is outperformed by a factor of 4.0.
Introduction
Predictive marketing has traditionally focused on two main areas: forecasting aggregate sales volumes or providing item-level recommendations (e.g., "customers who bought this also bought that"). However, a more granular and challenging problem remains relatively unexplored: predicting the market basket. This involves forecasting the specific subset of items a customer will purchase in their next transaction.
Predicting market baskets is an "extreme subset selection" problem. In a retail environment with 50,000 potential items, a typical basket may contain only 10. Furthermore, these baskets are highly dynamic and vary in size. Existing state-of-the-art methods typically rely on association rules—pre-coded logic such as "if a customer buys beer, they will likely buy painkillers." These rules are limited by their autoregressive nature, meaning they only look at an individual's history, and their reliance on exact matches, which fails to recognize that "red wine" and "white wine" serve similar consumer needs.
The kNN-SDTW Framework
To address these limitations, we developed a novel pipeline called kNN-SDTW (k-Nearest Neighbor Subsequential Dynamic Time Warping). This approach moves beyond simple rules by identifying similar shopping patterns across an entire customer base, allowing for "knowledge transfer" between shoppers.
1. Product Embeddings
Using techniques similar to Word2Vec, we map products into a multi-dimensional vector space. This ensures that the model understands semantic relationships; for instance, "Coke" and "Pepsi" are positioned closer together than "Coke" and "Apples." This allows the model to recognize substitutes and complementary goods even if the exact product IDs do not match.
2. Wasserstein Distance for Basket Comparison
To compare two baskets of different sizes, we utilize the Wasserstein distance (also known as the Earth Mover’s Distance). By treating a basket as a probability distribution of products in the embedding space, we can measure the "cost" to transform one basket into another. This "soft matching" is significantly more robust than binary exact-match rules.
3. Subsequential Dynamic Time Warping (SDTW)
Purchase histories are sequences of baskets over time. We use SDTW to find the most similar sub-segments of shopping history across the entire database. If a new customer’s recent history matches a segment of a veteran customer’s past, the model can leverage the veteran's subsequent purchases to predict the new customer's next basket.
4. Computational Efficiency
Calculating the Wasserstein distance is computationally intensive ($O(l^3 \log l)$). To make this scalable, we derived a tight lower bound that operates in $O(l^2)$. This allows the system to prune the search space by approximately 80%, making the algorithm twice as fast as a naive implementation and viable for large-scale retail datasets.
Experimental Results
We evaluated our model against three real-world datasets: aisle-level Instacart data, product-level Instacart data (top 500 products), and the Ta-Feng Grocery Dataset.
Our findings indicate a massive leap in predictive accuracy. On the Ta-Feng dataset, our model achieved an F1-score of 0.263. This outperforms the strongest baseline—the "Personal Top Items" heuristic (0.053)—by a factor of 4.0. While traditional association rules struggled with the complexity of product-level data, the kNN-SDTW model successfully identified underlying behavioral structures.
Key Insights
- Cross-Customer Learning: By identifying "shopping twins," the model can predict future behavior for a customer by looking at what others with similar histories did next.
- Robustness through Soft Matching: The use of Wasserstein distance prevents the model from being penalized for "near misses" (e.g., predicting the wrong brand of a similar product), leading to better sequence alignment.
- Uncertainty Fallback: We implemented a threshold ($\tau$) for similarity scores. If no sufficiently similar sequence is found in the database, the model reverts to a personal top-items heuristic, ensuring it does not make low-confidence guesses for unique or unpredictable shoppers.
Limitations and Future Directions
The model is most effective when there is a clear hierarchical or sequential structure to purchases. It is less dominant in scenarios with extremely high repeat-purchase rates (where "buy what I bought last time" is a near-perfect heuristic) or in very small datasets. Additionally, the model currently does not account for external shocks such as price promotions or seasonal shifts. Future research will focus on integrating these external variables, such as discounts and weather patterns, into the sequence matching process to further refine prediction accuracy.
Summary updated