Context-Dependent Recommendations with Items Splitting

Abstract

Recommender systems are intelligent applications that help on-line users to tackle information overload by providing recommendations of relevant items. Collaborative Filtering (CF) is a recommendation technique that exploits users' explicit feedbacks on items to predict the relevance of items not evaluated yet. In classical CF users' ratings are not specifying in which contextual conditions the item was evaluated (e.g., the time when the item was rated or the goal of the consumption). But, in some domains the context could heavily in uence the relevance of the item and this must be taken into account. This paper analyzes the behavior of a technique which deals with context by generating new items that are restricted to a contextual situation. The ratings' vectors of some items are split in two vectors containing the ratings collected in two alternative contextual conditions. Hence, each split generates two ctitious items that are used in the prediction algorithm instead of the original one. We evaluated this approach on semi-synthetic data sets measuring precision and recall while using a matrix-factorization algorithm for generating rating predictions. We compared our approach to the previously introduced reduction based method. We show that item splitting can improve system accuracy. Moreover, item splitting leads to a better recall than the reduction based approach.

1. INTRODUCTION

The Internet, interconnecting information and business services, has made available to on-line users an over abundance of information and very large product catalogues. Hence, users trying to decide what information to consult or what products to choose may be overwhelmed by the number of options. Recommender systems are intelligent applications that try to solve information overload problem by recommending relevant items to a user [ 2, 11 ]. Here an item is usually a descriptive information about a product such as a movie, a book or a place of interest. Recommender systems are personalized Information Retrieval systems where users make generic queries, such as, "suggest a movie to be watched with my family this night".

Collaborative Filtering (CF) is a recommendation technique that emulates a simple and e ective social strategy called \word-of-mouth" and is now largely applied in the \social" web. For example, amazon.com recommends items that user could be interested to buy or delicious.com recommends the links that were tagged by alike users with commonly used tags. CF recommendations are computed by leveraging historical log data of users' online behavior [ 12 ]. The relevance of an item is usually expressed and modeled by the explicit user's rating. The higher is the rating that a user assigned to an item, the more relevant is the item for the user. CF assumes that the user's recorded ratings for items can help in predicting the ratings of like-minded users. We want to stress that this assumption is valid only to some extent. In fact, the user's general interests can be relatively stable, but, the exact evaluation of an item can be in uenced by many additional and varying factors. In certain domains the consumption of the same item can lead to extremely different experiences when the context changes [ 1, 4 ]. Therefore, relevance of an item can depend on several contextual conditions. For instance, in a tourism application the visiting experience to a beach in summer is strikingly di erent from the same visit in winter (e.g., during a conference meeting). Here context plays the role of query re nement, i.e., a context-aware recommender system must try to retrieve the most relevant items for a user, given the knowledge of the current context. However, most CF recommender systems do not distinguish between these two experiences, thus providing a poor recommendation in certain situations, i.e., when the context really matters.

Context-aware recommender systems is a new area of research [ 1 ]. The classical context-aware reduction based approach [ 1 ] extended the classical CF method adding to the standard dimensions of users and items new ones representing contextual information. Here recommendations are computed using only the ratings made in the same context as the target one. For each contextual segment, i.e., sunny weekend, algorithm checks (using cross validation) if generated predictions using only the ratings of this segment are more accurate than using full data set. The authors use a hierarchical representation of context, therefore, the exact granularity of the used context is searched (optimized) among those that improve the accuracy of the prediction. Similarly, in our approach we enrich the simple 2-dim. CF matrix with a model of the context comprising a set of features either of the user, or the item, or the evaluation. We adopt the de nition of context introduced by Dey, where \Context is any information that can be used to characterize the situation of an entity" [ 8 ]. Here, the entity is an item consumption that can be in uenced by contextual variables u1 u2 u3 u4 u5 n+1 items describing the state of the user and the item. In this paper we propose a new approach for using these contextual dimensions to pre- lter items' ratings. Actually, to be precise, the set of ratings for an item is not ltered but it is split into two subsets according to the value of a contextual variable, e.g., ratings collected in \winter" or in \summer" (the contextual variable is the season of the rating/evaluation). These two sets of ratings are then assigned to two new ctitious items (e.g. beach in winter and in summer).

This paper extends the results presented in [ 5, 6 ]. Here we evaluate the same item splitting technique in a di erent set of experiments, namely we measure precision and recall, whereas previously we used MAE. Also the nine semisynthetical data sets are generated di erently. Moreover, we extended our analyzes by studying the behavior of item splitting with respect to the various Information Gain thresholds.

2. ITEM SPLITTING

Our approach extends the traditional CF data model by assuming that each rating rui in a m n users-items matrix, is stored (tagged) together with some contextual information c(u; i) = (c1; : : : ; cn); cj 2 Cj , describing the conditions under which the user experience was collected (cj is a nominal variable). The proposed method identi es items having signi cant di erences in the ratings (see later the exact test criteria). For each one of these items, our algorithm splits its ratings into two subsets, creating two new arti cial items with ratings belonging to these two subsets. The split is determined by the value of one contextual variable cj , i.e., all the ratings in a subset have been acquired in a context where the contextual feature cj took a certain value. So, for each item the algorithm seeks for a contextual feature cj that can be used to split the item. Then it checks if the two subsets of ratings have some (statistical signi cant) di erence, e.g., in the mean. If this is the case, the split is done and the original item in the ratings matrix is replaced by the two newly generated items. In the testing phase, the rating predictions for the split item are computed for one of the newly generated item. For example, assume that an item i has generated two new items i1 and i2, where i1 contains ratings for item i acquired in the contextual condition cj = v, and i2 the ratings acquired in context cj v, hence the two sets partition the original set of ratings. Now assume that the system needs to compute a rating prediction for the item i and user u in a context where cj = x. Then the prediction is computed for the item i1 if x = v, or i2 if x 6= v, and is returned as the prediction for i.

Figure 1 illustrates the splitting of one item. As input, the item splitting step takes a m n rating matrix of m users and n items and outputs a m (n + 1) matrix. The total number of ratings in the matrix does not change, but a new item is created. This step can be repeated for all the items having a signi cant dependency of their ratings on the value of one contextual variable. In this paper we focus on a simple application of this method where an item is split only into two items, using only one selected contextual variable. A more aggressive split of an item into several items, using a combination of features, could produce even more \specialized" items, but potentially increasing data sparsity. We note again, that for the same user, and di erent items, one can in principle obtain ratings in di erent contexts, as in our context model context depends on the rating. Therefore, items i1 and i2 could overlap, i.e., could be rated both by the same user in di erent contextual conditions. However, such situation are not very common.

We conjecture that the splitting could be bene cial if the ratings within each newly obtained item are more homogenous, or if they are signi cantly di erent in the new items coming from a split. One way to accomplish this task is to de ne an impurity criteria t [ 7 ]. So, if there are some candidate splits s 2 S, which divide i into i1 and i2, we choose the split s that maximizes t(i; s) over all possible splits in S. A split is determined by selecting a contextual variable and a partition of its values in two sets. Thus, the space of all possible splits of item i is de ned by the context model C. In this work we analyzed tIG impurity criteria. tIG(i; s) measures the information gain (IG), also known as KullbackLeibler divergence [ 10 ], given by s to the knowledge of the item i rating: tIG = H(i) H(i1)Pi1 + H(i2)Pi2 where H(i) is the Shannon Entropy of the item i rating distribution and Pi1 is the proportion of ratings that i1 receives from item i. To ensure reliability of this statistic we compute it only for a split S that could potentially generate items each containing 4 or more ratings. Thus, algorithm never generates items with less than 4 ratings in the pro le. 3.

EXPERIMENTAL EVALUATION

We tested the proposed method on nine semi-synthetic gdeantaersaettesdwuistihngraYtainhgoso!i1n f1, 2, 3, 4, 5g. The data sets were

Webscope movies data set contains 221K ratings, for 11,915 movies by 7,642 users. The semisynthetic data sets were used to analyze item splitting when varying the in uence of the context on the user ratings. The original Yahoo! data set contains user age and gender features. We used 3 age groups: users below 18 (u18), between 18 and 50 (18to50), and above 50 (a50). We modi ed the original Yahoo! data set by replacing the gender feature with a new arti cial feature c 2 f0; 1g that was assigned randomly to the value 1 or 0 for each rating. This feature c is representing a contextual condition that could a ect the rating. We randomly choose 100% items from the data set and then from these items we randomly chose 100% of the ratings to modify. We increased (decreased) the rating value by one if c = 1 (c = 0) and if the rating value was not already 5 (1). For example, if = 0:9 and = 0:5 the corresponding synthetic data set has 90% of altered items' pro les that contains 50% of changed ratings. We generated nine semi-synthetic data sets varying 2 f0:1; 0:5; 0:9g and 2 f0:1; 0:5; 0:9g. So, in these data set the contextual condition is more \in uencing" the rating value as and increase.

In this paper we used matrix factorization (FACT ) as the

1Webscope v1.0, http://research.yahoo.com/

No Context Reduction

Item-Split (a) Precision No Context Reduction

Item-Split (b) Recall rating prediction technique. We used the algorithm implemented and provided by Timely Development2. FACT uses 60 factors and the other parameters are set to the same values optimized for another data set (Net ix), so it might not be the best setting, but all the system variants that we compared used the same settings. To evaluate the described methods we used 5-fold cross-validation and measured precision and recall. The usage of precision and recall in recommender systems needs some clari cation. These measures, in its purest sense, are impossible to measure as they would require the knowledge of the rating (relevance) of each item and user combination [ 9 ]. Usually there are thousands of candidate items to recommend (11K in our case) and just for a small percentage of them we know the true user's evaluation (typically less than 1%) . Herlocker et al. [ 9 ] proposed to approximate these measures by computing the prediction just for user item pairs that are present in the ratings data set, and consider items worth recommending (relevant items) only if the user rated them 4 or 5. We computed the measures on full test set (of each fold), while trained the models on the train set. Please refer to [ 5 ] for additional experiments. These include the evaluation of other impurity criteria, the performance of the proposed method on the original Yahoo! data set, and experiments using other prediction methods such as user-based CF while computing Mean Absolute Error (MAE). 3.1

Context-aware Prediction Methods

To understanding the potential of item splitting in a contextdependent set of ratings we tested this approach on the semi-synthetical data sets described earlier, i.e., replacing the gender feature with a new contextual variable that does in uence the ratings. The baseline method is FACT when no contextual information is considered. It is compared with the context-aware reduction based approach [ 1 ], and our item splitting technique. Figure 2 shows comparison of three methods for the nine semi-synthetic data sets. For each data set we computed precision and recall. We considered item as worth recommending if algorithm made a prediction greater or equal to 4. For all the nine data sets the algorithm splits an item if any split leads to an IG bigger than 0.01. The small IG threshold value led to a good results in our previous experiments [ 6 ] and it allows algorithm to split up to 15% of items (depending on the data set). In

2http://www.timelydevelopment.com

Subsection 3.3 we report result while choosing bigger values that typically decrease the impact of item splitting. As we expected, the smaller is the impact of the contextual feature c, the smaller is the improvement of the performance measure obtained by the methods that do use the context. In fact, item splitting improved the performance of baseline method for 4 data sets: 2 f0:5; 0:9g; 2 f0:5; 0:9g. The highest improvement for precision of 9.9% was observed for the data set = 0:9; = 0:9 where most items and most ratings were in uenced by the arti cial contextual feature. Increasing the value of and , i.e., increasing the number of items and ratings that are correlated to the value of the context feature, decreased the overall precision and recall of the baseline method. We conjecture, that the contextual condition plays the role of noise added to the data, even if this is clearly not noise but a simple functional dependency from a hidden variable. In fact, FACT cannot exploit the additional information brought by this feature and cannot e ectively deal with the in uence of this variable.

Reduction based approach increased precision by 1.3% only for = 0:9; = 0:9 data set. This is the data set, where arti cial contextual feature has highest in uence on the ratings and 90% of items are modi ed. In [ 1 ] the authors optimized MAE when searching for the contextual segments where the context-dependent prediction improves the default one (no context). Here, we searched for the segments where precision and recall is improved and we used all better performing segments to make the predictions. For example, Figure 2(a) reports the precision of reduction based. To conduct this experiment, the algorithm rst sought (optimized) the contextual segments where precision is improved (using a particular split of train and test data). Then, when it has to make a rating prediction, used either only the data in one of these segments, i.e., if the prediction is for a item-user combination in one of the found segments, or all the data, i.e., if the item-rating is in one contextual conditions where no improvements can be found with respect to the baseline. Note, that in all three data sets where = 0:5; 2 f0:1; 0:5; 0:9g the results are similar to the baseline approach. In these cased the reduction base approach does consider the segments generated using the arti cial feature. However, the data set was constructed in such a way that half of the items do not have ratings' dependencies on the arti cial feature, and no bene t is observed.

These experiments show that both context-aware pre- ltering approaches can outperform the base line FACT CF method, when the context in uences the ratings. It is worth noting that item splitting is computationally cheaper and it performed better than reduction based. Note also that, accuracy could depend on the particular baseline prediction algorithm, i.e., FACT in our experiments. However, we choose FACT as it is now currently largely used, and in our previous experiments it outperformed traditional user-based CF method [ 5 ]. 3.2

Precision Versus Recall

In this section we illustrate the precision/recall curves for the three selected methods. For this experiments we reused the three data sets: = 0:1; 2 f0:1; 0:5; 0:9g. As was done in the previous experiment, we set the IG threshold to 0.01. For the reduction based approach we optimized precision. The results can be seen in Figure 3. The left gure shows results for = 0:9; = 0:5 data set and the right gure for = 0:9; = 0:9. We skip the = 0:9; = 0:1 data set, as for this data set all three methods perform similarly to each other. Each curve was computed by varying the threshold at which a recommendation is done. For example, all methods obtained the highest precision when recommending the items that were predicted as rating 5. In this case, we do not recommend the items that were predicted with a lower rating. Note that we always count recommendation as relevant if user rated the item 4 or 5. We set the threshold to values equal to f1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5, 5g. Note, that previous experiment (see. Figure 2) was done with the recommendation threshold equal to 4. The recall is equal to 1 if we recommend all the items, i.e., those predicted with a rating of 1 and higher. Even at this level of recall, the precision is more than 70%. This can be explained by the high fraction of high ratings in the data set.

Recommender systems usually try to improve precision. Having recall as small as 0.01, we could still be able to recommend too many items for user to consume, i.e., approximately 119 items in our data set. Interestingly, as we can see it is also much harder to make precise recommendations than to obtain high recall. The curves for all three methods get at when approaching precision 0.97. At this point we recommend only the items that were predicted with rating 5. This is the maximum possible predicted rating by FACT and precision can not be improved by varying the threshold at which recommendation is done. We also observe, that we can achieve higher maximum precision for item splitting method comparing to other methods. When = 0:9 and = 0:9, the highest precision value for item split improves by 7% the baseline method. The improvement when = 0:9 and = 0:5 is 2.7%. This experiment gives valuable insights into the behavior of reduction base approach. We see, that at each level of the recommendation threshold it shows a higher recall value than the other two methods. At the highest level of precision, reduction based approach is close to item splitting and gives improvement of 6.1% in precision for = 0:9; = 0:9 data set and 1.3% for = 0:9; = 0:5 data set. But, the precision/recall curve of reduction based is always below than that of item split.

In conclusion we want to note that considering both precision and recall, we see that both context-aware recommendation methods yields quite similar results. More noticeably, both methods outperforms baseline CF which does not take context into account. 3.3

Item Splitting for Various IG Thresholds

To better understand the item splitting method we further analyzed the prediction processes. We looked at the number of items the algorithm splits and also on which attribute the split was performed. For this purpose we varied the item splitting threshold parameter. For this experiment we used tIG impurity measure and the three data sets: = 0:9 2 f0:1; 0:5; 0:9g. The summary of the results are shown in Figure 4. Figures 4(a), 4(b), 4(c) show the number of splits that the item split algorithm performs varying the IG threshold for the three considered data sets. When using = 0:9; = 0:1 the algorithm chooses the arti cial feature approximately twice as often as the age feature. More precisely, when the threshold is IG = 0:2 item split splits 101.8 items (on average in 5 folds); the arti cial feature was chosen 69.8 and age feature was chosen 32 times. When the in uence of arti cial feature increases, a higher proportion of items are split using the arti cial feature. For the = 0:9; = 0:9 data set and IG = 0:2 it splits 576.8 items using the arti cial feature and 29.8 using the age feature. Note, that despite IG favors attributes with many possible values [ 10 ] item splitting chooses the attribute having larger in uence on the rating. We further observe that the number of split items is not large. For all three data sets we split no more than 2050 items (17%). This low number can be explained by looking at the size of items' pro les. Note that in the considered data sets the average number of ratings per item is 18.5. Algorithm splits item only if the newly generated item has at least 4 ratings. Therefore, item must have a minimum of 8 ratings to be considered for splitting. Lowering the minimum number of ratings in the item prole, could cause unreliable computation of statistics and was observed to decrease the overall performance.

Figures 4(d), 4(e) shows precision and recall accuracy measures for three data sets. We observe, that item splitting is only bene cial when context (i.e., arti cial feature here) has an high in uence on the rating. The best performance for the = 0:9; = 0:1 data set, both for recall and precision, is obtained when no items are split. Each split of an item a ects also the prediction for the items that are not split. Splitting an item is equivalent to create two new items and deleting one, therefore, it causes a modi cation of the data set. When CF generates a prediction for a target user-item pair all the other items' ratings, including those in the new items coming from some split, are used to build that prediction. In [ 5 ] we observed that we can increase the performance on split items, but at the same time the decrease of performance on the untouched items can cancel any bene t. When = 0:9; = 0:5 the situation is dif(a) 90%i-10%r (b) 90%i-50%r (c) 90%i-90%r ferent. We observe, that here splitting more items leads to an increase in precision and decrease in recall. Finally, for = 0:9; = 0:9 splitting more items increase the precision and recall, and this is maximum when the IG threshold is equal to 0.1. In conclusion, we could regard item split as a more dynamical version of reduction based. Here the split is done for each item separately and using an external measure (such as IG) to decide if the split is needed. Using the IG criteria, splitting items is bene cial when context highly in uences the ratings.

CONCLUSIONS AND FUTURE WORK

This paper evaluates a contextual pre- ltering technique for CF, called item splitting. Based on the assumption that certain items may have di erent evaluations in different contexts, we proposed to use item splitting to cope with this. The method is compared with a classical contextaware pre- ltering approach [ 1 ] which uses extensive searching to nd the contextual segments that improve the baseline prediction. As a result we observed that despite the increased data sparsity, item splitting is bene cial, when some contextual feature separates the item ratings into two more homogeneous rating groups. However, if the contextual feature is not in uential the splitting technique sometimes produced a minor decrease of the precision and recall. Item-splitting outperforms reduction based contextaware approach when FACT CF method is used. Moreover, the method is more time and space e cient and could be used with large context-enriched data bases.

The method we proposed can be extended in several ways. For instance one can try to split the users (not the items) according to the contextual features in order to represent the preferences of a user in di erent contexts by using various parts of the user pro le. Another interesting problem is to nd a meaningful item splitting in continuous contextual domains such as time or temperature. Here, the splitting is not easily prede ned but have to be searched in the continuous space. Finally, item splitting could ease the task of explaining recommendations. The recommendation can be made for the same item in di erent context. The contextual condition on which the item was split could be mentioned as justi cations of the recommendations. For example, we recommend you to go to the museum instead of going to the beach as it will be raining today. We would also like to extend our evaluation of the proposed algorithm. First of all, we want to use real world context-enriched data. Moreover, we want to evaluate precision and recall at top-N recommendation list. At the end, we want to develop a solution to be able to deal with missing contextual values. 5.

References

[1] G. Adomavicius , R. Sankaranarayanan , S. Sen , and A. Tuzhilin . Incorporating contextual information in recommender systems using a multidimensional approach . ACM Transactins on Information Systems , 23 ( 1 ): 103 { 145 , 2005 .

[2] G. Adomavicius and A. Tuzhilin . Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions . IEEE Transactions on Knowledge and Data Engineering , 17 ( 6 ): 734 { 749 , 2005 .

[3] G. Adomavicius and A. Tuzhilin . Context-aware recommender systems . In P. Pu, D. G. Bridge , B. Mobasher , and F. Ricci, editors, RecSys , pages 335 { 336 . ACM, 2008 .

[4] S. S. Anand and B. Mobasher . Contextual recommendation . In Lecture Notes In Arti cial Intelligence , volume 4737 , pages 142 { 160 . Springer-Verlag, Berlin, Heidelberg, 2007 .

[5] L. Baltrunas and F. Ricci . Context-based splitting of item ratings in collaborative ltering . In L. D. Bergman , A. Tuzhilin , R. Burke , A. Felfernig , and L. Schmidt-Thieme, editors, RecSys , pages 245 { 248 . ACM, 2009 .

[6] L. Baltrunas and F. Ricci . Context-dependent items generation in collaborative ltering . In G. Adomavicius and F. Ricci, editors, Proceedings of the 2009 Workshop on Context-Aware Recommender Systems , 2009 .

[7] L. Breiman , J. H. Friedman , R. A. Olshen , and C. J. Stone . Classi cation and Regression Trees . Statistics/Probability Series. Wadsworth Publishing Company, Belmont, California, U.S.A. , 1984 .

[8] A. K. Dey . Understanding and using context . Personal Ubiquitous Comput. , 5 ( 1 ):4{ 7 , February 2001 .

[9] J. L. Herlocker , J. A. Konstan , L. G. Terveen , John, and T. Riedl . Evaluating collaborative ltering recommender systems . ACM Transactions on Information Systems , 22 :5{ 53 , 2004 .

[10] J. R. Quinlan . C4 . 5: Programs for Machine Learning (Morgan Kaufmann Series in Machine Learning). Morgan Kaufmann, 1 edition, January 1993 .

[11] P. Resnick and H. R. Varian . Recommender systems . Communications of the ACM , 40 ( 3 ): 56 { 58 , 1997 .

[12] J. B. Schafer , D. Frankowski , J. Herlocker , and S. Sen . Collaborative ltering recommender systems . In The Adaptive Web , pages 291 { 324 . Springer Berlin / Heidelberg, 2007 .