Matrix Factorization for Package Recommendations

Abstract

Research in recommendation systems has to date focused on recommending individual items to users. However there are contexts in which combinations of items need to be recommended, and there has been less research to date on how collaborative methods such as matrix factorization can be applied to such tasks. Œe research contributions of this paper are threefold. First, we formalize the collaborative package recommendation task as an extension of the standard collaborative recommendation task. Second, we describe and make available a novel package recommendation dataset in the clothes domain, where a combination of a “top” (e.g. a shirt, t-shirt or top) and “boŠom” (e.g. trousers, shorts or skirts) needs to be recommended. Finally, we describe several extensions of matrix factorization to predict user ratings on packages, and report RMSE improvements over the standard matrix factorization approach for recommending combinations of tops and boŠoms.

INTRODUCTION

Recent research into recommendation systems has focused on methods for Collaborative Filtering (CF) [ 5, 20 ] for tasks such as recommending individual or top-N items to users [ 8 ] and for making cross-domain recommendations [ 3, 12, 18 ].

Œere has been less research into package recommendations, where a combination of items needs to be recommended together. Travel is one domain that is mentioned in the literature [ 6, 13 ], where a travel package could consist of a set of destinations and is o‰en recommended to a group of users. For example, in a travel planning task, a user (or group) is recommended a package of places of interest (POI) which satisfy some constraints such as budget or time [ 22, 23 ]. Such travel recommender systems need to be able to handle constraints, e.g. “no more than 3 museums” or “travel distance is less than 10 km”. Another task is to provide alternatives for restaurants, transportation and hotels as POI [ 1 ].

ComplexRec 2017, Como, Italy. 2017. Copyright for the individual papers remains with the authors. Copying permiŠed for private and academic purposes. Œis volume is published and copyrighted by its editors. Published on CEUR-WS, Volume 1892..

Outside of travel/tourism there are several other domains, such as food (e.g. recommending a starter and main course), furniture [ 25 ] and clothing (e.g. recommending a shirt and trousers), which o‚er good opportunities for recommending packages.

In the clothes domain, there are some package recommendation approaches based on image features [ 7, 17 ]. Œese approaches collected images (each image containing both top and boŠom) from fashion websites [ 17 ] or fashion magazines [ 7 ] to create a package reference database. Using image processing techniques, they automatically separated top and boŠom. Miura et al. [ 17 ] extracted image features (such as RGB histogram and scale invariant features transform [SIFT] [ 14 ] values) for both top and boŠom. To provide package recommendations, they required the user to provide a query (top or boŠom) image. Œis image was then compared with packages in the reference database, and the closest package reference returned as a recommendation. Similar to Miura’s work, Iwata et al. [ 7 ] extracted visual features (such as colour, texture and SIFT as a bag-of-features, and derived a topic model over these using Latent Dirichlet Allocation (LDA). When a user provided a query image (top/boŠom), Iwata et al. recommended the other part by searching the topic model in their package reference database.

Shen et al. [ 19 ] developed a clothes package recommendation system based on user context. First, they stored clothing items and combinations of items in a user wardrobe database. Œey also annotated its contents using English words. To generate recommendations, their system asked the user about their goals (“destinations” and “want to look like”) and mapped them to possible characteristic of clothes in the user wardrobe.

With respect to recommendations, all these methods have the following drawbacks: (a) they work from a €xed reference database, with no ƒexibility for recommending combinations not in the database; (b) the recommendations provided from the database are not tailored to user preferences (though Shen et al. allow the user to specify some aspects of the style); and (c) Œe methods are highly tailored to the clothes domain and cannot be readily applied to package recommendations in other domains.

To overcome these drawbacks, we formalize package recommendations as a collaborative €ltering task and argue that collaborative package recommendation is an interesting task for three reasons. First, collaborative package recommendation is more challenging than item recommendation since people might dislike a package, even if they like the individual items. Such preferences can reƒect individual taste and style, and recommendations therefore need to be personalized to users. Second, package recommendations face greater data sparsity issues compared to the collaborative item recommendation task. Œe number of possible combinations is large and for the same number of user ratings, the package recommendation matrix is much sparser than for item recommendation. Œird, unlike the previous work described above, we can easily extend our package recommendation approach to other domains (such as food, etc.) by formulating package recommendation as collaborative €ltering.

Œe remainder of this paper is organized as follows. Section 2 de€nes the package recommendation task and the notation used, describes how the dataset was generated, and formulates several Matrix Factorization approaches for package recommendation. Section 3 details our experimental seŠings, Section 4 reports our experiment results, and Section 5 provides a discussion and suggests directions for future work. Œe traditional collaborative €ltering (CF) [ 5, 20 ] task is de€ned as predicting the ratings given by users to items, based on a set of previous ratings by any user to any item. In this paper, we introduce a collaborative €ltering task for package recommendations, where we need to predict ratings given by a user to combinations of items, based on a set of previous ratings by any user to any item or combination of items.

In this paper, we discuss package recommendation for the clothes domain. Consider a set of clothes I a = fi1t; i2t; : : : ; iot ; i1b ; i2b ; : : : ; ipb g, consisting of two disjoint complementary sets: a set of o top items I t = fi1t; i2t; : : : ; iot g and a set of p boŠom items I b = fi1b ; i2b ; : : : ; ipb g, where I t [ I b = I a ; o + p = n. Some of these items and their combinations (a package) have received ratings from one or more of m possible users U = fu1; u2; :::; um g. In our notation, individual ratings are denoted as a triplet ¹u; i; ru;i º, where u 2 U , i 2 I a and ru;i is the rating given by user u to item i. Package ratings are denoted as a quadruple ¹u; it ; ib ; ru;¹it ;ib ºº, where u 2 U , it 2 I t , ib 2 I b , and ru;¹it ;ib º is the rating provided by user u to the package ¹it ; ib º. Our task is to predict the unobserved package ratings for a user from an observed set of ratings for individual items and packages by this and other users. Œis de€nition is easily extended to other domains and to tasks which might involve more than two items within a package. 2.2

Dataset Generation

A boŠleneck to research on package recommendations is the lack of open datasets suited for this task. To overcome this, we generated a dataset by randomly selecting 1,400 “top” and 600 “boŠom” images from Amazon product data [ 15, 16 ] and obtaining 30 ratings each from 200 participants recruited from Amazon Mechanical Turk for individual tops and boŠoms and packages combining them.

For each participant, we €rst asked them whether they wear clothes for men or women, and then provided 30 screens where each screen showed images of one top and one boŠom €ltered for their chosen gender preference. We also asked participants to rate on a scale of 1 to 5 how much: (1) they would like to wear the top, (2) they would like to wear the trousers, (3) they would like to wear the top and trousers together.

An example can be seen in Figure 1. From our participants, we obtained 12,000 individual ratings and 6,000 package ratings. We have made this dataset freely downloadable from the PackageRecDataset Github repository1.

Œe distribution of ratings for our data set are shown in Table 2. Note that the percentage of highly rated packages is much lower than that of either tops or boŠoms, which makes package recommendation a more challenging task. 2.3

Matrix Factorization Methods 2.3.1 Matrix Factorization for Item Recommendations. In collaborative €ltering, there are many approaches to provide rating predictions. Some approaches calculate similarity between users or items [ 5, 20 ], while other approaches use matrix factorization techniques to decompose the rating matrix into two (or more) matrices. Œe €rst winner [ 9 ] of the Netƒix prize reported that matrix 1hŠps://github.com/atwRecsys/PackageRecDataset factorization has many bene€ts for overcoming common problems in recommender systems such as data sparsity and cold start [ 24 ].

Matrix factorization (MF) can be de€ned as producing two factor matrices, say W = wi j 2 Rm k and H = hi j 2 Rk n from one known matrix V = vi j 2 Rm n , so the product of W and H are (approximately) equal to V :

V where each cell is computed as:

W H ; k Õ vˆxy

wxi hiy i=1 Œere are many algorithms for MF, such as Multiplicative [ 10, 11 ], Gradient descent [ 2, 4 ], Alternating Least Square [ 2, 4 ], and more. Œese algorithms aim to minimize the di‚erence between the known values in matrix V and the corresponding values in its multiplicative form W H (the cost function) through an iterative process. When the factors W and H are computed in this manner, it has been found that the product W H provides values for missing cells in V , and that these turn out to be good estimates of these missing ratings.

2.3.2 Extending MF for Package Recommendations. From the de€nitions in Table 1, there are four di‚erent matrices that can be input to matrix factorization methods (V t ; V b ; V a ; V p ). In this paper, we utilized these inputs in seven di‚erent scenarios: (1) In our €rst scenario (Average Predictor), we used the average value of each package in V p (the matrix of user [m] (1) (2) and packages [o p]) as prediction. We used this scenario as a baseline. (2) In our second scenario (MF-Package), we used V p as input and ran MF over this package rating matrix. Using this scenario, we obtained two latent matrices W p and H p , which when multiplied together provided ratings for missing cells. Œis is our second baseline. (3) In our third scenario (MF-Pseudo), to address the matrix sparsity issue in the baseline above, we €rst populated V p by adding some pseudo-ratings (r 0 ) into V p0 , before u;¹it ;ib º then applying MF to the matrix. Starting from a rating by a user for a package, we identi€ed similar packages involving a new item (either top or boŠom) where the cosine similarity between the new and known item was more than speci€ed threshold.

Consider a known package rating ¹u; ixt ; iyb ; ru;¹ixt ;iyb ºº. ru;¹ixt ;iyb º if cossim(iyb , isb ) For each top item izt in the matrix, we added a package pseudorating ru0;¹izt;iyb º where ru0;¹izt;iyb º = ru;¹ixt ;iyb º if cossim(ixt , izt ) θ . Likewise, for each boŠom item isb we added a package pseudorating ¹u; ixt ; isb ; ru0;¹ixt ;isb ºº, where r 0 = u;¹ixt ;isb º θ . A‰er we added these pseudoratings, we ran MF and obtained W p0 and H p0 . Œe package rating predictions are generated by multiplying these matrices. (4,5) In our fourth and €‰h scenarios (MF-Min-Cat and MF-MulCat), we ran MF individually over the user–top (V t ) and user–boŠom (V b ) matrices. From V t we obtained W t and H t , and from V b we obtained W b and H b . Œe package rating predictions rˆu;¹it ;ib º were obtained in two ways: (a) MF-Min-Cat predicted package ratings using the minimum value of rˆu;it and rˆu;ib ; (b) MF-Mul-Cat predicted package ratings using the harmonic mean of rˆu;it and rˆu;ib (Equation 3).

a b harmonic mean¹a; bº = 12 ¹a + bº (3) (6,7) In our sixth and seventh scenarios (MF-Min-All and MFMul-All), we ran MF over all individual rating matrix (V a ). From this process, we obtained W a and H a . Œe package rating predictions rˆu;¹it ;ib º were obtained in two ways: (a) MF-Min-All predicted package rating using the minimum value of rˆu;it and rˆu;ib ; (b) MF-Mul-All predicted ratings using the harmonic mean of rˆu;it and rˆu;ib (Equation 3).

To summarise, scenaro 1 applies Average Predictor baseline over V p , which takes the average rating for each item; scenario 2 applies MF over the user–package matrix; and scenarios 3–7 apply MF to the user–item matrices and combine predicted ratings of items in the package using either a minimum or a harmonic mean function. Given ru;it as a “top” rating, ru;ib as a “boŠom” rating and ru;¹it ;ib º as “package” rating, there are six possibilities:

(1) We do not know ru;¹it ;ib º, but we know ru;it or ru;ib ; (2) We do not know ru;¹it ;ib º, but we know ru;it and ru;ib ; (3) We know ru;¹it ;ib º, but we only know one of ru;it and ru;ib ; (4) We know ru;¹it ;ib º, but do not know either ru;it or ru;ib ; (5) We know ru;it , ru;ib , and ru;¹it ;ib º.

(6) We do not know ru;it , ru;ib , or ru;¹it ;ib º.

Our dataset collected ratings for “top”, “boŠom” and “package” together; thus for any user only (5–6) are possible. However (1–4) are realistic scenarios for a package recommendation system. To cover all these possibilities, we adopted the following methodology. First, we used 4-fold crossvalidation by randomly spliŠing the individual ratings into four parts. We rotated and used 3 parts as the training set and one for testing. Œen in each fold we used only 25% of package ratings ru;¹it ;ib º as the training set, and the remaining 75% package ratings ru;¹it ;ib º as the test set. Œese mechanisms for holding back data to make package predictions ensure that all possibilities are covered in a realistic manner. 3.2

Experimental Settings

We used matrix factorization with gradient descent [ 21 ], with 100 iterations. In this experiment we varied k, the number of latent dimensions in MF (k = 5, 10, 15, 20). We also varied the threshold value for similarity when adding pseudo-transactions in MF-Pseudo using values (θ = 0.5, 0.7, 0.9).

We report the average RMSE performance over the test sets in each fold, as de€ned in Section 3.1. In addition, we also report the average RMSE performance for each known rating. As we can see in Table 2, users tended to give low ratings for package recommendations, and such low-rated packages dominate the dataset. However, for a recommendation task, we are primarily concerned with accurately predicting the highly rated packages. Œe table thus allows for comparison of algorithms on the more realistic task.

In real world situations, we are usually interested in providing top-N packages to users. Œis sort of evaluation is unfortunately not possible for our dataset, as mechanical turkers were given random combinations to rate, and were not allowed to choose items or packages they liked. Œough out of scope for this paper, we would in the future like to evaluate package recommendations using a rank performance metric in a real domain. 4

RESULTS

Table 3 shows the average RMSE for the testing set for di‚erent scenarios. Œe “All” column represent the overall RMSE, while the 1, 2, 3, 4, and 5 columns represent the average RMSE over the known package ratings. For example, column “1” represent average RMSE to ru;¹it ;ib º = 1. Œe yellow cells in this table show our baseline RMSE over the package testing set.

All our adaptations outperform the MF-Package baseline (lower RMSE values in the “All” column), and many of them outperform the Average Predictor. MF-Min-Cat has the best overall performance (the green cell in the “All” column). In our dataset, people overall gave lower rating for packages than for individual items. Estimating the package rating as the minimum of the individual item rating predictions therefore gives beŠer results overall, but increased errors for highly rated packages that we would want to recommend. Œe pseudo-ratings approach reducing sparsity in the package matrix and the minimum function for combining item ratings performed beŠer at predicting low ratings. MF-Pseudo and MF-Min-Cat outperform other scenarios for low ratings (marked as green cells in the “1” and “2” columns). MF-Pseudo increases matrix density by populated the package rating matrix with some pseudo-ratings based on similarity to known packages. Since low package ratings are frequent, MF-Pseudo might get a stronger signal to predict low ratings rather than higher ones.

For highly rated packages, on the other hand,the multiplicative methods for combining individual ratings performed beŠer. MF-Mul-All outperformed other approaches for the high ratings (marked as green cells in the “3”, “4” and “5” columns). Œis is not unexpected, as when we combine two ratings for “top” and “boŠom”, the harmonic mean (MF-Mul-All) will by de€nition give a slightly higher estimate than the minimum (MF-Min-All). 5

CONCLUSIONS AND FUTURE WORK

We have de€ned a new task of collaborative package recommendation and made available the €rst public dataset for this task. We have also suggested several adaptations of the standard matrix factorization approach to item recommendation. All the adaptations outperform the standard MF baseline, and di‚erent adaptations demonstrated strengths in di‚erent situations.

Our work can be extended in a couple of ways. One is take into account item aŠributes (such as colour, dresscode, etc.), and user aŠributes (such as gender and age, etc) within a tensor factorization framework. We would also like to extend our clothes package recommendations by adding other categories (such as accessories) and also investigate the package recommendation methods in other domains, such as food, where we might additionally consider constraints such as allergens and nutrition.

ACKNOWLEDGMENTS

We would like to thank Lembaga Pengelola Dana Pendidikan (LPDP), Departemen Keuangan Indonesia for awarding a scholarship to support the studies of the lead author.

References

[1] Sihem Amer-Yahia , Francesco Bonchi, Carlos Castillo, Esteban Feuerstein, Isabel Mendez-Diaz, and Paula Zabala . 2014 . Composite retrieval of diverse and complementary bundles . IEEE Transactions on Knowledge and Data Engineering 26 , 11 ( 2014 ), 2662 - 2675 .

[2] Michael W Berry , Murray Browne, Amy N Langville , V Paul Pauca , and Robert J Plemmons. 2007 . Algorithms and applications for approximate nonnegative matrix factorization . Computational statistics & data analysis 52 , 1 ( 2007 ), 155 - 173 .

[3] Iva ´n Cantador, Ignacio Ferna´ndez-Tob´ıas, Shlomo Berkovsky , and Paolo Cremonesi . 2015 . Cross-domain recommender systems . In Recommender Systems Handbook . Springer, 919 - 959 .

[4] Moody Chu , Fasma Diele, Robert Plemmons, and Stefania Ragni . 2004 . Optimality, computation, and interpretation of nonnegative matrix factorizations . In SIAM Journal on Matrix Analysis. Citeseer.

[5] Michael D Ekstrand , John T Riedl, and Joseph A Konstan. 2011 . Collaborative €ltering recommender systems . Foundations and Trends in Human-Computer Interaction 4 , 2 ( 2011 ), 81 - 173 .

[6] A Felfernig , S Gordea , D Jannach , E Teppan , and M Zanker . 2007 . A short survey of recommendation technologies in travel and tourism . OEGAI journal 25 , 7 ( 2007 ), 17 - 22 .

[7] Tomoharu Iwata , Shinji Wanatabe, and Hiroshi Sawada . 2011 . Fashion coordinates recommender system using photographs from fashion magazines . In IJCAI , Vol. 22 . Citeseer , 2262 .

[8] George Karypis . 2001 . Evaluation of item-based top-n recommendation algorithms . In Proceedings of the tenth international conference on Information and knowledge management. ACM , 247 - 254 .

[9] Yehuda Koren . 2009 . Œe Bellkor Solution to the Netƒix Grand Prize . Netƒix prize documentation 81 ( 2009 ).

[10] D. D. Lee and H. S. Seung . 1999 . Learning the parts of objects by non-negative matrix factorization . Nature 401 , 6755 ( 1999 ), 788 - 791 .

[11] D. D. Lee and H. S. Seung . 2001 . Algorithms for non-negative matrix factorization .

[12] Bin Li , Qiang Yang , and Xiangyang Xue . 2009 . Can Movies and Books Collaborate? Cross-Domain Collaborative Filtering for Sparsity Reduction. . In IJCAI , Vol. 9 . 2052 - 2057 .

[13] Qi Liu , Enhong Chen, Hui Xiong, Yong Ge, Zhongmou Li , and Xiang Wu . 2014 . A cocktail approach for travel package recommendation . IEEE Transactions on Knowledge and Data Engineering 26 , 2 ( 2014 ), 278 - 293 .

[14] David G Lowe . 1999 . Object recognition from local scale-invariant features . In Computer vision , 1999 . Š e proceedings of the seventh IEEE international conference on , Vol. 2 . Ieee, 1150 - 1157 .

[15] Julian McAuley , Rahul Pandey , and Jure Leskovec . 2015 . Inferring networks of substitutable and complementary products . In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM , 785 - 794 .

[16] Julian McAuley , Christopher TargeŠ, Qinfeng Shi , and Anton Van Den Hengel. 2015 . Image-based recommendations on styles and substitutes . In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM , 43 - 52 .

[17] Shinya Miura , Toshihiko Yamasaki, and Kiyoharu Aizawa . 2013 . SNAPPER: fashion coordinate image retrieval system . In Signal-Image Technology & InternetBased Systems (SITIS) , 2013 International Conference on. IEEE , 784 - 789 .

[18] Shaghayegh Sahebi and Peter Brusilovsky . 2013 . Cross-domain collaborative recommendation in a cold-start context: Œe impact of user pro€le size on the quality of recommendation . In International Conference on User Modeling, Adaptation, and Personalization. Springer, 289 - 295 .

[19] Edward Shen , Henry Lieberman , and Francis Lam . 2007 . What am I gonna wear?: scenario-oriented recommendation . In Proceedings of the 12th international conference on Intelligent user interfaces. ACM , 365 - 368 .

[20] Xiaoyuan Su and Taghi M Khoshgo ‰aar . 2009 . A survey of collaborative €ltering techniques . Advances in arti€cial intelligence 2009 ( 2009 ), 4 .

[21] Ga ´bor Taka´cs, Istva´n Pila´szy, BoŠya´n Ne´meth, and Domonkos Tikk . 2008 . Matrix Factorization and Neighbor Based Algorithms for the Netƒix Prize Problem . In Proceedings of the 2008 ACM Conference on Recommender Systems (RecSys '08) . ACM, New York, NY, USA, 267 - 274 . DOI:hŠps://doi.org/10.1145/1454008. 1454049

[22] Min Xie , Laks VS Lakshmanan, and Peter T Wood . 2010 . Breaking out of the box of recommendations: from items to packages . In Proceedings of the fourth ACM conference on Recommender systems. ACM , 151 - 158 .

[23] Min Xie , Laks VS Lakshmanan, and Peter T Wood . 2011 . Comprec-trip: A composite recommendation system for travel planning . In Data Engineering (ICDE) , 2011 IEEE 27th International Conference on. IEEE , 1352 - 1355 .

[24] Ke Zhou , Shuang-Hong Yang , and Hongyuan Zha . 2011 . Functional matrix factorizations for cold-start recommendation . In Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval. ACM , 315 - 324 .

[25] Tao Zhu , Patrick Harrington, Junjun Li , and Lei Tang . 2014 . Bundle recommendation in ecommerce . In Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval. ACM , 657 - 666 .