Diversity in a recommendation list has been recognized as one of the key factors to increase user's satisfaction when interacting with a recommender system. Analogously to the modelling and exploitation of query intent in Information Retrieval adopted to improve diversity in search results, in this paper we focus on eliciting and using the pro le of a user which is in turn exploited to represent her intents. The model is based on regression trees and is used to improve personalized diversi cation of the recommendation list in a multi-attribute setting. We tested the proposed approach and showed its e ectiveness in two di erent domains, i.e. books and movies.
In the recent years, diversi cation has gained more and
more importance in the eld of recommender systems.
Engines able to get excellent results in terms of accuracy of
results have been proved to be not e ective when we
consider other factors related to the quality of user experience
[
Here our focus is on both the individual (or intra-list )
diversity, namely the degree of dissimilarity among all items
in the list provided to a user, and the aggregate diversity
[
In this paper we use regression trees as user modeling technique to infer the individual interests, useful to provide an intent-aware diversi cation. Compared to approaches where item attributes are treated independently one to each other, regression trees make possible to represent user tastes as a combination of interrelated characteristics. For instance, a user could have a preference for horror movies of the 80s irrespective of the director, or for horror movies of the 90s directed by a a speci c director. In a regression tree, conditional probability lets to build such inference rules about user's preferences. We conducted experiments on the movie and on the book domains to empirically evaluate our approach. The performance was measured in terms of accuracy and both individual and aggregate diversity.
The main contributions of this paper are: a novel intent-aware diversi cation approach able to combine multiple attributes. It bases on the use of regression trees (and rules) to infer and encode the model of users' interests; a novel method to combine di erent diversi cation approaches; an experimental evaluation which shows the performance of the proposed approaches with respect to both accuracy and diversity measures.
The paper is organized as follows. Section 2 describes the greedy approach to diversi cation problem, the xQuAD algorithm and some evaluation metrics. We then continue in Section 3 by showing how to face the multi-attribute diversi cation and how to leverage regression trees in the diversication process with xQuAD to provide more personalized recommendations. Section 4 describes the experimental conguration and the datasets used for the experiments while Section 5 presents and describes the experimental results, showing the competitive performance of the proposed approach. In Section 6 we review the related work at the best of our knowledge. Conclusions close the paper.
The recommendation step can be followed by a re-ranking
phase nalized to improve other qualities besides accuracy
[
Data: The original recommendation list P, N Result: The re-ranked recommendation list S n 3 4 5 6 end 7 return S. 1 S = hi; 2 while j S j N do i = argmax fobj(i; S);
i2PnS S = S i ; P = P n fi g
At each iteration, the algorithm selects the item maximizing the objective function fobj (line 3) { which in turn can be de ned to deal with the trade-o between accuracy and diversity { and then adds it to the re-ranked list (line 4).
For our purpose, we focus on the intent-aware approach
xQuAD (eXplicit Query Aspect Diversi cation), with the
aim to diversify the user intents. It was proposed for search
diversi cation in information retrieval by Santos et al. [
More formally, xQuAD greedily selects diverse
recommendations maximizing the following objective function:
fobj(i; S; u) =
r (u; i) + (1
)div(i; S; u)
(1)
with r (u; i) being the score predicted by the baseline
recommender; the parameter allowing to manage the
accuracydiversity balance, where higher values give more weight to
accuracy, while lower values give more weight to diversity.
The last component in Equation 1 promotes the diversity,
providing a measure of novelty with respect to the items
already selected in S. As for the function div(i; S; u), the
original formulation in [
X p(ijf )p(f ju) Y(1 p(sjf )) (2) f s2S where p(ijf ) represents the likelihood of item i being chosen given the feature f while p(fju) represents the user interest in the feature.
A number of measures have been proposed to evaluate the
diversity in a recommendation list. Smyth and McClave [
1 jLj (jLj 1)
X
i;j2L;i6=j
(1
sim(i; j))
(3)
The sim function is a con gurable and application-dependent
component which can use content-based item features or
statistical information (e.g. number of co-ratings) to compute
the similarity between items. We used also the metric
nDCG, that is the redundancy-aware variant of Normalized
Discounted Cumulative Gain proposed in [
1
-iDCG
jLj P
X
r=1
f2F (Lr)(1
log2(1 + r)
)cov(L;f;r 1)
(4)
where cov(L; f; r 1) is the number of items ranked up to
position r 1 containing the feature f . F (Lr) represents
the set of features of the r-th item. The parameter is used
to balance the emphasis between relevance and diversity.
iDCG denotes the value of -nDCG for the best \ideally"
diversi ed list. Considering that the computation of the
ideal value is NP-complete [
In this section we show how we address the intent-aware diversity problem when dealing with multi-attribute item descriptions. The presentation relies on content-based attributes (e.g. genres, years, etc. in the movies domain), but the proposed approach can be used independently of the attributes types. Therefore, one could also use statistical information as item attributes, e.g., popularity or rating variance. As explained in the previous section, we refer to features as possible instances of a generic attribute. We tried di erent reformulations of the div function in xQuAD (Equation 2) to deal with multi-attribute values. After an empirical evaluation, we chose the best divma (for multiattribute) in terms of accuracy-diversity balance: divma(i; S; u) = X where:
A2A
Pf2dom(A) p(ijf )p(f ju)(1
Pf2dom(A) p(f ju) avgj2S p(jjf )) (5) A is the set of attributes; for each attribute A 2 A and each feature in the attribute domain f 2 dom(A), p(ijf ) represents the importance of f for the item i. It is computed as a binary function that returns 1 if the item contains f , 0 otherwise; p(f ju) represents the importance of the feature f for the user u and is computed as the relative frequency of the feature f on the rated items from the user u. Here after we will refer to xQuAD using Equation 5 as basic xQuAD.
DivRT. p(jjm) is the average similarity between m and each rule covered by item j. More formally: Besides dealing with multi-attribute descriptions, the idea behind our approach is to infer and model the user pro le by means of a regression tree, a predictive model where the user interest represents the target variable, which can take continuous values. Once a regression tree is produced for a user u, then it is converted into a set of rules RT (u). Each rule maps the presence/absence of a categorical feature or a constraint on a numerical one to a value v in a continuous interval. This latter indicates the predicted interest of the user on the items satisfying the rule. In our implementation we used the interval [1; 5] since the value of the target variable has been calculated as the rating mean of the training instances classi ed by the inferred rule. Please note that the choice of a speci c value interval for the target variable does not a ect the overall approach. Each rule m has then the form
body(m) 7! interest = v with body(m) = fc1; : : : ; cng. An example of a set of rules produced for a user is shown in Figure 1.
1. fhorror 2 dom(genres); western 2= dom(genres);
DarioArgento 2 dom(directors)g 7! interest = 4:2 2. fhorror 2= dom(genres); thriller 2 dom(genres)g 7! interest = 2:1 3. fyear > 1990; horror 2= dom(genres); drama 2 dom(genres); Aronofsky 2 dom(directors)g 7! interest = 4:0 4. fyear < 1990; drama 2 dom(genres);
AlP acino 2 dom(actors)g 7! interest = 3:9 5. fhorror 2= dom(genres)g 7! interest = 3:2
Eventually, under the assumption that they represent speci c user interests, the computed rules are used in the reranking phase as item features to improve the intent-aware recommendation diversity.
We propose also a div function for xQuAD so that each item is evaluated according to the rules it satis es. divrules(i; S; u) = Here M (u; i) represents the set of rules for the user u matched by the item i while p(mju) represents the importance of the rule m for u and is computed as: p(mju) = interestm jM (u; i)j In Equation 7, interestm is the normalized predicted outcome of the regression tree for the rule m. Finally, the last component in Equation 6 indicates the complement of the coverage of the rule among the already selected recommendations. We propose two di erent versions of this adapted xQuAD.
RT. p(jjm) is a binary function that returns 1 if the item j matches the rule, 0 otherwise. (7) p(jjm) = avgm02M(u;j) sim(m; m0) (8) The rationale behind this formulation is that some rules may be similar with each other thus not bringing any actual diversi cation if considered separately. The computation of sim(m; m0) takes into account the overlapping between the rules m and m0 as follows: sim(m; m0) =
Pci2body(m) overlap(m; m0; ci)
max(jbody(m)j; jbody(m0)j) For instance, considering the attributes represented in Figure 1, we have for actor; genre and director: overlap(m; m0; ci) = 8 1, ci 2 body(m) ^ ci 2 body(m0) < : 0, otherwise For the numerical attribute year we may adopt a different formulation for the function overlap(m; m0; ci). Here we compute, if any, the overlap between the interval in body(m) and the one in body(m0) normalized with respect to maximum interval's length. As an example, if year > 1990 is in body(m) and year < 2010 is in body(m0) we may de ne the overlapping function as overlap(m; m0; ci) = max(dom(yje1a9r9)0) 2m0i1n0(jdom(year)) . The functions introduced above have been used in the experimental setting in order to compute the function overlap(m; m0; ci) (see Section 4).
RT and DivRT can be used instead of the basic xQuAD as diversi cation algorithms in the re-ranking phase. Alternatively, basic xQuAD and RT or DivRT can be pipelined to bene t from the strengths of them both. For instance, one could use xQuAD to select 50 diversi ed recommendations and then RT to select 20 recommendations from those 50, or vice versa. Hereafter, we use the syntax X-after-Y, e.g. xQuAD-after-RT, to indicate that algorithm X is executed on the results of Y. 4.
We carried out a number of experiments to evaluate the performance of the methods presented in the Section 3 on two well known datasets: MovieLens1M and LibraryThing.
MovieLens 1M1 dataset contains 1 million ratings from
6,040 users on 3,952 movies. The original dataset contains
information about genres and year of release, and was
enriched with further attribute information such as actors and
directors extracted from DBpedia2. More details about this
DBpedia enriched version of the dataset are available in [
Moreover, we used the LibraryThing3 dataset, which contains more than 2 million ratings from 7,279 users on 37,232 books. As in the dataset there are many duplicated ratings, 1Available at http://grouplens.org/datasets/movielens 2http://dbpedia.org 3Available at http://www.macle.nl/tud/LT when a user has rated more than once the same item, we selected her last rating. The unique ratings are 749,401. Also in this case, we enriched the dataset by mapping the books with BaseKB4, the RDF version of Freebase5 and then extracting three attributes: genre, author and subjects. The subjects in Freebase represent the topic of the book, for instance Pilot experiment, Education, Culture of Italy, Martin Luther King and so on. The dump of the mapping is available online6. The nal dataset contains 565,310 ratings from 7,278 users on 27,358 books. We built training and test sets by employing a 80%-20% hold-out split. The di erent ratio used for LibraryThing respect to Movielens (60%-40%) depends on its higher sparsity: holding 80% to build the user pro le ensures a su cient number of ratings to train the system.
Number of items Number of ratings Data sparsity Avg users per item Avg items per user Since the number of distinct values was too large for year, actors and director attributes in MovieLens and for all the attributes in LibraryThing, we convert years in the corresponding decades and performed a K-means clustering for other attributes on the basis of DBpedia categories7 for MovieLens and Freebase categories8 for LibraryThing. Table 2 and 3 report the number of attribute values and clusters. The number of clusters was decided according to the calculation of the within-cluster sum of squares (withinss measure from the R Stats Package, version 2.15.3), that is picking the value of K corresponding to an evident break in the distribution of the withinss measure against the number of clusters extracted.
5https://www.freebase.com 6URL removed to guarantee anonymous submission. 7http://purl.org/dc/terms/subject 8http://www.w3.org/1999/02/22-rdf-syntax-ns#type
For both datasets, we used the Bayesian Personalized Ranking Matrix Factorization algorithm (BPRMF) available in MyMediaLite9 as baseline (using the default parameters). We performed experiments using other recommendation algorithms, but we do not report results here since they are very similar to those obtained by BPRMF.
We selected the top-200 recommendations for each user to generate the initial list P used for performing the re-ranking as shown in Algorithm 1.
Accuracy is measured in terms of Precision, Recall and
nDCG, but we only report nDCG values since the trend of
the other two metrics is very similar. Individual diversity
is measured using ILD and -nDCG (see Section 2) with
= 0:5 to equally balance diversity and accuracy, while
aggregate diversity is measured using both the catalog
coverage { computed as the percentage of items recommended
at least to one user { and the entropy { computed as in
[
As similarity measure for computing the ILD metric (Equation 3) we used the Jaccard index. Considering that there are more attributes for each item, we computed the average of the Jaccard index value for each attribute shared between two items. -nDCG is computed as the average of the Equation 4 for each attribute.
As presented in Section 3, we propose two novel diversi cation approaches: RT and DivRT. We also propose a method to combine in sequence di erent algorithms by means of a two phase re-ranking procedure, with the aim of bene ting from the strengths of both. Therefore we evaluated other two approaches: xQuAD-after-RT and RT-afterxQuAD, applying the second re-ranking phase on the set of 50 recommendations provided from the rst phase. We have also evaluated the combination with xQuAD and DivRT, but the results are very similar using RT, so they will not be shown. To evaluate the performances, we compare the top-10 recommendation list generating from all the approaches with basic xQuAD, by varying the parameter from 0 to 0.95 with step xed to 0.05 in Equation 1 (higher values of give more weight to accuracy, lower values to diversity).
The rules are produced using M5Rules10 algorithm
available in Weka based on the M5 algorithm proposed by
Quinlan [
10http://weka.sourceforge.net/doc.dev/weka/ classifiers/rules/M5Rules.html
Results of the experiments on MovieLens and LibraryThing are reported in Figure 2 and 3, respectively.
MovieLens. xQuAD obtains the best results in terms of ILD (Figure 2(a)) and -nDCG (Figure 2(b)), though the xQuAD-after-RT results are very close and, with higher values (namely giving more importance to the accuracy factor), the di erences between them are not signi cant. This outcome is due to the fact that the diversity metrics are attribute-based and xQuAD operates directly diversifying the attributes values, while the proposed rule-based approaches do not take into account all the attributes values. This also explains why the pure rule-based approaches (RT and DivRT) obtain the worst diversity results, while the combined algorithms (xQuAD-after-RT and RT-afterxQuAD) obtain better results. It is noteworthy that these last two con gurations have no substantial di erence with ILD, but, in terms of -nDCG, xQuAD-after-RT considerably overcomes RT-after-xQuAD. This demonstrates that the pipeline of xQuAD and the rule-based approach obtains good diversity. Considering coverage (Figure 2(c)) and entropy (Figure 2(d)) to evaluate the aggregate diversity, the results show that using the rules the recommendations are much more personalized. It is interesting to note the compromise provided by xQuAD-after-RT, that obtains equidistant results between xQuAD and the rulebased algorithms, unlike RT-after-xQuAD that slightly overcomes xQuAD. With respect to the baseline, no con guration is able to give more accurate recommendations (nDCG = 0.14); all are able to increase the individual diversity (ILD = 0.34 and -nDCG = 0.27). With nDCG and the individual diversity, the di erences are always statistically signi cant (p < 0.001), except using the pure ruled-based approaches with > 0.65. The situation is more complex in terms of aggregate diversity, since the coverage grows very little on the baseline (coverage = 0.29) and the entropy slightly decreases (entropy = 0.78) with higher values. According to a comprehensive analysis on MovieLens, the pure rule-based approaches may give personalized and diversi ed recommendations, also with small accuracy loss. However, when individual diversity is more important than aggregate diversity, combining xQuAD with a previous rule-based reranking gives a good compromise between individual and aggregate diversity.
LibraryThing. At rst glance, the LibraryThing results appear similar to those on MovieLens. Although they are generally consistent, there are interesting di erences. Also in this case, xQuAD obtains the best diversity values, with ILD (Figure 3(a)) and -nDCG (Figure 3(b)). However, both the combined approaches obtain really interesting results, very close to xQuAD, except for the lower values (namely giving more importance to the diversi cation factor). Unlike what happens on MovieLens, in this case RT-after-xQuAD obtains good results also in terms of nDCG. The pure rule-based approaches still obtain worse results. Considering coverage (Figure 3(c)) and entropy (Figure 3(d)) to evaluate the aggregate diversity, the results show that using the rules the recommendations are much more personalized than using only xQuAD. The combined approaches are able to improve the aggregate diversity with respect to xQuAD, albeit they are still distant from the pure rule-based approaches, especially in terms of coverage. With respect to the baseline, all con gurations give a little more accurate recommendations, with > 0.65, but the di erences are not statistically signi cant. In terms of individual diversity, all of them are able to overcome the baseline (ILD = 0.4 and -nDCG = 0.285) except when using the pure rule-based approaches in terms of ILD. However they are able to improve -nDCG. For the latter two metrics, the di erences are always statistically signi cant (p < 0.001). In terms of aggregate diversity, xQuAD does not improve the baseline result (coverage = 0.15 and -nDCG = 0.77), while using the rules leads to better results. According to a comprehensive analysis on LibraryThing, the pure rulebased approaches may give more personalized recommendations with a better diversity, especially using RT, with also a small accuracy loss. Similarly to the analysis on MovieLens, the results on LibraryThing suggest that diversifying with only the rules is a good choice when aggregate diversity is more important than individual diversity, conversely xQuAD remains the best choice to improve the individual diversity and combined with the rule-based diversi cation improves also the aggregate diversity.
The nal conclusions of this analysis are that using a regression tree to infer rules representing user interests on multi-attribute values in the diversi cation process with xQuAD leads to more personalized recommendations but with a less diversi ed list and that combining attributebased and rule-based diversi cations in two phase re-ranking is a good way for taking the advantages of both. The better degree of personalization may depend on the fact that the rules are di erent among the users since they represents their individual interests. The lower individual diversity values with ILD and -nDCG are due to the nature of these metrics which are based directly on the attributes values while the pure rule-based approaches do not take into account all the attributes values. 6.
There is a noteworthy e ort by the research community in
addressing the challenge of recommendation diversity. That
interest arises from the necessity of avoiding monotony in
recommendations and controlling the balance between
accuracy and diversity, since increasing diversity inevitably puts
accuracy at risk [
Typically, the proposed approaches aim to replace items
in an already computed recommendation list, by minimizing
the similarity among all items. Some approaches exploit a
re-ranking phase with a greedy selection (see Section 2), for
instance [
Other types of approaches try to directly generate
diversi ed recommendation lists. For instance, [
Multi-attribute diversity has been substantially non-treated
in the literature of recommender systems. A recent work [
Furthermore, increasing attention has been paid to the
intent-aware diversi cation, namely the process of
increasing the diversity taking into account the user interests. Some
approaches are based on adapted algorithms proposed for
the same purpose in the Information Retrieval eld, such as
IA-Select [
The aggregate diversity, also known as sales diversity, is
considered another important factor in recommendation for
both business and user perspective: the user may receive
less obvious and more personalized recommendations,
comply with the target to help users discover new content [
This paper addresses the problem of intent-aware
diversication in recommender systems in multi-attribute settings.
The proposed approach bases on xQuAD [
The experimental evaluation on two datasets in the movie and book domains demonstrates that considering the rules generated from the di erent attributes available in an item description provides diversi ed and personalized recommendations, with a small loss of accuracy. The analysis of the results suggests that a pure rule-based diversi cation is a good choice when the aggregate diversity is more needed than individual diversity. Conversely, basic xQuAD remains the best choice to improve the individual diversity while its combination with the rule-based diversi cation improves also the aggregate diversity.
For future work, we would like to evaluate the impact of our approach also on the recommendation novelty. A way to improve the novelty could be the expansion of the rules by exploiting collaborative information.
Acknowledgements. The authors acknowledge partial support of PON02 00563 3470993 VINCENTE, PON04a2 E RES NOVAE, PON02 00563 3446857 KHIRA e PON01 03113 ERMES.