Association rules are a simple yet powerful tool for making item-based recommendations. As part of the ECML PKDD 2013 Discovery Challenge, we use association rules to form a name recommender system. We introduce a new measure of association rule con dence that incorporates user similarities, and show that this increases prediction performance. With no special feature engineering and no separate treatment of special cases, we produce one of the top-performing recommender systems in the discovery challenge.
Introduction Association rules are a classic tool for making item-based recommendations. An association rule \a ! b" is a rule that item(set) a in the observation implies item b is also in the observation. Association rules were originally developed for retail transaction databases, although the same idea can be applied to any setting where the observations are sets of items. As part of the ECML PKDD 2013 Discovery Challenge, in this paper we consider a setting where each observation is a set of names in which the user has expressed interest. We then form association rules \a ! b," meaning that interest in name a (or, in general, set of names a) implies interest in name b. The strength with which a implies b is called the con dence of the rule, and in Section 2.2 we explore di erent measures of con dence.
Association rules provide an excellent basis for a recommender system
because they are scalable and interpretable. The scalability of association rule
algorithms has been well studied, and is often linear in the number of items
[
One of the most successful tools for recommender systems, particularly at a
large scale, is collaborative ltering [
Our main contribution is to use ideas from collaborative ltering to create a new measure of association rule con dence, which we call similarity-weighted adjusted con dence. We maintain the excellent scalability and interpretability of collaborative ltering and association rules, yet see a signi cant increase in performance compared to either approach. Our method was developed in the context of creating a name recommender system for the ECML PKDD 2013 Discovery Challenge, and so we compare the similarity-weighted adjusted con dence to other collaborative ltering and association rule-based approaches on the Nameling dataset released for the challenge. 2
Similarity-Weighted Association Rule Con dence We begin by introducing the notation that will be used throughout the rest of the paper. Then we discuss measures of con dence, introduce our similarityweighted adjusted con dence, and discuss strategies for combining association rules into a recommender system. 2.1
We consider a database with m observations x1; : : : ; xm, and a collection of N items Z = fz1; : : : ; zN g. For instance, it may be m visitors to a name recommendation site, with Z the set of valid names. Each observation is a set of items: xi Z; 8i. We denote the number of items in xi as jxij.
We will consider rules \a ! b" where the left-hand side of the rule a is an itemset (a Z) and the right-hand side is a single item (b 2 Z). Notice that a might only contain a single item. We denote as A the collection of itemsets that we are willing to consider: a 2 A. 2.2
The standard de nition of the con dence of the rule \a ! b" is exactly the empirical conditional probability of b given a:
Conf(a ! b) =
Pm i=1 1[a xi and b2xi] ;
Pm i=1 1[a xi] (1) where we use 1[condition] to indicate 1 if the condition holds, and 0 otherwise.
This measure of con dence corresponds to the maximum likelihood estimate of a speci c probability model, in which the observations are i.i.d. draws from a Bernoulli distribution which determines whether or not b is present. Because of the i.i.d. assumption, all observations in the database are considered equally when determining the likelihood that a implies b. In reality, preferences are often quite heterogeneous. If we are trying to determine whether or not a new user x` will select item b given that he or she has previously selected itemset a, then the users more similar to user x` are likely more informative. This leads to the similarity-weighted con dence for user x`:
SimConf(a ! bjx`) =
Pm i=1 1[a xi and b2xi]sim(x`; xi)
Pm i=1 1[a xi]sim(x`; xi) ; where sim(x`; xi) is a measure of the similarity between users x` and xi. The similarity-weighted con dence reduces to the standard de nition of con dence under the similarity measure sim(x`; xi) = 1, as well as sim(x`; xi) = (1; if x` \ xi 6= ?:
0; otherwise: Giving more weight to more similar users is precisely the idea behind user-based collaborative ltering. A variety of similarity measures have been developed for use in collaborative ltering, and here we use the cosine similarity: sim(x`; xi) =
jx` \ xij : pjx`jpjxij (2) (3) (4) (5) 2.3
In [
ConfK (a ! b) =
Pm i=1 1[a xi and b2xi] ; Pm i=1 1[a xi] + K where K is a user-speci ed amount of adjustment, corresponding to a particular pseudocount in the usual Bayesian interpretation. This leads to an increase in performance by reducing the variance of the estimate for itemsets with small support. The Nameling dataset used here is quite sparse, so we add the same adjustment to our similarity-weighted con dence, producing the similarity-weighted adjusted con dence:
SimConfK (a ! bjx`) =
Pm i=1 1[a xi and b2xi]sim(x`; xi) Pm i=1 1[a xi]sim(x`; xi) + K : When K = 0, this reduces to the similarity-weighted con dence in (2).
The similarity-weighted adjusted con dence provides a powerful tool for
determining the likelihood that b 2 x` given that a x`. In general there will be
many itemsets a satisfying a x`, so to use the association rules as the basis
for a recommender system we must also have a strategy for combining con
dence measures across multiple left-hand sides. For each left-hand side a 2 A
satisfying a x`, we can consider SimConfK (a ! bjx`) to be an estimate of the
probability of item b given itemset x`. There is a large literature on combining
probability estimates [
Score(bjx`) = X SimConfK (a ! bjx`): a x` a2A A ranked list of recommendations is then obtained by ranking items by score.
A natural extension to this combination strategy is to consider a weighted
sum of con dence estimates. We consider this strategy in [
We use two simple collaborative ltering algorithms as baselines in our experimental results in Section 3. For user-based collaborative ltering, we use the cosine similarity between two users in (3) to compute 2.4 (6) (7) (8) (9) ScoreUCF(bjx`) = m X 1[b2xi]sim(x`; xi) i=1 For item-based collaborative ltering, for any item b we de ne Nbhd(b) as the set of observations containing b: Nbhd(b) = fi : b 2 xig. Then, the cosine similarity between two items is de ned as before: And the item-based collaborative ltering score of item b is simitem(b; d) =
jNbhd(b) \ Nbhd(d)j : pjNbhd(b)jpjNbhd(d)j ScoreICF(bjx`) =
X simitem(b; d): In addition to these two baselines, we consider the extremely simple baseline of ranking items by their frequency in the training set. We call this the frequency baseline. 3
Name Recommendations with the Nameling Dataset
We now demonstrate our similarity-weighted adjusted con dence measure on the
Nameling dataset released for the ECML PKDD 2013 Discovery Challenge. We
also compare the alternative con dence measures and baseline methods from
Section 2. A description of the Nameling dataset can be found in [
The dataset contains the interactions of users with the Nameling website http: //nameling.net, a site that allows its users to explore information about names and provides a list of similar names. A user enters a name, and the Nameling system provides a list of similar names. Some of the similar names are given category descriptions, like \English given names," or \Hypocorisms." There are ve types of interactions in the dataset: \ENTER SEARCH," when the user enters a name into the search eld; \LINK SEARCH," when the user clicks on one of the listed similar names to search for it; \LINK CATEGORY SEARCH," when the user clicks on a category name to list other names of the same category; \NAME DETAILS" when the user clicks for more details about a name; and \ADD FAVORITE" when the user adds a name to his or her list of favorites. The dataset contains 515,848 interactions from 60,922 users.
The data were split into training and test sets by, for users with su ciently many \ENTER SEARCH" interactions, setting the last two \ENTER SEARCH" interactions aside as a test set. Some other considerations were made for duplicate entries - see the introduction to the workshop proceedings for details. The end result was a training set of 443,178 interactions from the 60,922 users, and a test set consisting of the last two \ENTER SEARCH" names for 13,008 of the users. The task is to use the interactions in the training set to predict the two names in the test set for each of the test users by producing for each test user a ranked list of recommended names. The evaluation metric was mean average precision of the rst 1000 recommendations - see the proceedings introduction for more details. 3.2
We did minimal data pre-processing, to highlight the ability of similarity-weighted adjusted con dence to perform well without carefully crafted features or manual consideration of special cases. We discarded users with no \ENTER SEARCH" interactions, which left 54,439 users. For each user i, we formed the set of items xi as all \ENTER SEARCH," \LINK SEARCH," \LINK CATEGORY SEARCH," \NAME DETAILS," and \ADD FAVORITE" entries individually. That is, each unique entry for each interaction type was treated as a separate feature, and Z was the union of all of the entries found in the interaction database. The total number of items in Z was 34,070. No other data pre-processing was done.
To form rules, we took as left-hand sides a all individual interaction entries: A = Z. We considered as right-hand sides b all valid names to be recommended (among other things, this excludes names that were previously entered by that user - see the proceedings introduction for details on which names were excluded from the test set). 3.3
We applied con dence, adjusted con dence, similarity-weighted con dence, and similarity-weighted adjusted con dence to the training set to generate recommendations for the test users. For the adjusted measures, we found the best performance on the test set with K = 4 for similarity-weighted adjusted con dence and K = 10 for adjusted con dence. We also applied the user-based collaborative ltering, item-based collaborative ltering, and frequency baselines to generate recommendations. For all of these recommender system approaches, the mean average precision on the test set is shown in Table 1.
Similarity-weighted adjusted con dence gave the best performance, and similarity weighting led to a 4:2% increase in performance over (unweighted) adjusted con dence. The adjustment also led to a 9:7% increase in performance from similarity-weighted con dence to similarity-weighted adjusted con dence. User-based collaborative ltering performed well compared to the frequency baseline, but was outperformed by similarity-weighted adjusted con dence by 11:4%. Item-based collaborative ltering performed very poorly.
An advantage of using association rules as opposed to techniques based in
regression or matrix factorization is that there is no explicit error minimization
problem being solved. This means that association rules generally do not have
the same propensity to over t as algorithms based in empirical risk minimization.
We found that the performance on the discovery challenge hold-out dataset was
similar to that which we measured on the public test set in Table 1.
Conclusions. Similarity-weighted adjusted con dence is a natural t for the
Nameling dataset and the name recommendation task. First, the dataset is
extremely sparse (see [
Association rules and similarity-weighted adjusted con dence are powerful tools for creating a scalable and interpretable recommender system that will perform well in many domains.
Acknowledgments. Thanks to Stephan Doerfel, Andreas Hotho, Robert Jaschke, Folke Mitzla , and Juergen Mueller for organizing the ECML PKDD 2013 Discovery Challenge, and for making their excellent Nameling dataset publicly available. Thanks also to Cynthia Rudin for support and for many discussions on using rules for predictive modeling.