Shopping with Networks: An Approach to Market Basket Analysis

The market basket problem, the search for meaningful associations in customer purchase data, is one of the oldest problems in data mining. The typical solution involves the mining and analysis of association rules, which take the form of statements such as ``people who buy diapers are likely to buy beer.' It is well-known, however, that typical transaction datasets can support hundreds or thousands of obvious association rules for each interesting rule, and filtering through the rules is a non-trivial task. One may use an interestingness measure to quantify the usefulness of various rules, but there is no single agreed-upon measure and different measures can result in very different rankings of association rules.

In this thesis, we take a different approach to mining transaction data. By modeling the data as a product network, we discover more expressive communities (clusters) in the data, which can then be targeted for further analysis. We demonstrate that the network based approach can isolate influence among products without excessive ambiguous associations. We further consider a collaborative marketplace, where it may be beneficial for the market for stores to share their product networks. To that end, we propose a robust privacy preserving protocol that encourages stores to share their product network without compromising their individual information. We demonstrate the effectiveness of the product networks and the privacy preserving protocol on a real-world store data. Finally, we build upon our experience with product networks to propose a comprehensive analysis strategy by combining both traditional and network-based techniques.