User Profiling in Personalization Applications Through Rule Discovery and Validation

Gediminas Adomavicius, Alexander TuzhilinKDD 1999 · DOI

TL;DR

This paper tackles the challenge of creating accurate user profiles for personalization by discovering behavioral rules from transactional data. Their key contribution is a novel, expert-assisted validation framework that efficiently filters out spurious or irrelevant rules, enabling scalable and reliable user profiling.

What Problem Does This Paper Address?

In today's digital landscape, personalization is key for applications ranging from e-commerce recommendations to targeted marketing. To achieve this, systems need to build detailed "profiles" of individual users, understanding their behavior. A common approach is to use data mining techniques to learn rules from a user's transaction history (e.g., "if a user buys cereal, they often also buy milk"). However, data mining often generates a massive number of rules, many of which are trivial, irrelevant, or simply coincidental ("spurious"). The core problem this paper addresses is how to effectively validate these discovered rules to ensure they accurately reflect a user's true behavior, rather than noise, in a way that scales to millions of users.

Methods

The paper proposes a two-phase approach:

  • Phase I: Rule Discovery: This phase uses standard data mining algorithms (like Apriori for association rules or CART for classification rules) to learn behavioral rules from individual users' transactional data. The focus is on generating rules that are specific to each user.
  • Phase II: Rule Validation: This is the paper's main contribution. Instead of validating rules one by one for each user, they propose a collective validation process. All rules discovered across all users are pooled together, tagged with their originating user ID, and then subjected to a series of "validation operators." These operators are designed to allow a human expert to efficiently review and validate large sets of rules. Key operators include:
  • Similarity-based grouping: Groups similar rules together, allowing the expert to validate a whole group at once.
  • Template-based filtering: Filters rules based on expert-defined patterns (accepting or rejecting templates).
  • Redundant rule elimination: Removes rules that are implied by more general rules or factual profile information.
  • Visualization and Statistical Analysis Operators: Provide aggregated views of rules to aid expert understanding.
  • Browsing Operators: Allow direct inspection of individual rules or groups.

The validation process is iterative, with operators applied successively until a termination condition (e.g., a certain percentage of rules validated, or diminishing returns) is met.

Datasets

The paper describes a case study using a real-life marketing application.

  • Dataset: Data from 1,903 households that purchased various beverages over one year.
  • Characteristics: Contained 353,421 transactions (average 186 per household) with 21 attributes (customer ID, date, time, product type, coupon usage, etc.).
  • Rules Generated: The data mining module generated 1,022,812 association rules in total (average 537 per household).

Key Insights and Ideas

  • Collective Validation is Crucial for Scalability: Validating rules individually for millions of users is infeasible. Pooling rules and using expert-assisted operators is the only way to make this process manageable.
  • Human Expertise is Still Essential: While data mining discovers rules, human domain experts are vital for determining which rules are truly meaningful and not just statistical artifacts.
  • Validation Operators Streamline Expert Review: The proposed operators (grouping, templating, redundancy checks) significantly reduce the expert's workload by allowing them to make decisions on sets of rules rather than individual ones.
  • "Diminishing Returns" as a Termination Strategy: The validation process naturally slows down as fewer new, valuable rules are found, making the "law of diminishing returns" a practical stopping criterion.

Key Results

In their marketing application case study:

  • Rules Validated: Out of 1,022,812 initially discovered rules, the system managed to validate all but 14,803 rules (98.5% validation rate).
  • Accepted Rules: 26,878 rules were accepted and incorporated into user profiles (average of ~14 rules per household).
  • Efficiency: The validation process, including expert and computing time, took about 1.5 hours.
  • Scalability Expectation: The authors expect their algorithms, being linear in the number of customers and rules, to scale well for large personalization applications.

Limitations and Future Work

  • Subjectivity: The authors acknowledge that the validation process is inherently subjective, meaning different domain experts might produce different results using the same tools.
  • Future Work: Not explicitly detailed, but the success of the approach suggests further refinement of validation operators and exploration of more automated, yet still expert-guided, validation strategies. The paper also mentions an efficient linear-time rule grouping algorithm developed in a separate work ([AT]).

Summary updated

BibTeX
@inproceedings{adomavicius1999user,
  author = {Gediminas Adomavicius and Alexander Tuzhilin},
  title = {{User Profiling in Personalization Applications Through Rule Discovery and Validation}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {1999},
  doi = {10.1145/312129.312287},
}
Figure