Composite recommendations： from items to packages

• Published in: Frontiers of Computer Science 2012-06, Vol.6 (3), p.264-277
• Main Authors: XIE, Min, LAKSHMANAN, Laks V. S., WOOD, Peter T.
• Format: Article
• Language: English
• Subjects: Algorithms; Approximation; Budgets; Computer Science; Empirical analysis; Information sources; Mathematical analysis; Optical disks; optimization; Packages; recommendation algorithms; Recommender systems; Research Article; Synthetic data; Top; top- k query processing; 复合材料; 总成本; 推荐系统; 旅游规划; 用户选择; 近似算法; 近似质量
• ISSN: 1673-7350; 2095-2228; 1673-7466; 2095-2236
• DOI: 10.1007/s11704-012-2014-1

Classical recommender systems provide users with a list of recommendations where each recommendation consists of a single item, e.g., a book or DVD. However, sev- eral applications can benefit from a system capable of recom- mending packages of items, in the form of sets. Sample appli- cations include travel planning with a limited budget （price or time） and twitter users wanting to select worthwhile tweeters to follow, given that they can deal with only a bounded num- ber of tweets. In these contexts, there is a need for a system that can recommend the top-k packages for the user to choose from. Motivated by these applications, we consider composite recommendations, where each recommendation comprises a set of items. Each item has both a value （rating） and a cost associated with it, and the user specifies a maximum total cost （budget） for any recommended set of items. Our composite recommender system has access to one or more component recommender systems focusing on different do- mains, as well as to information sources which can provide the cost associated with each item. Because the problem of deciding whether there is a recommendation （package） whose cost is under a given budget and whose value exceeds some threshold is NP-complete, we devise several approximation algorithms for generating the top-k packages as recommen- dations. We analyze the efficiency as well as approximation quality of these algorithms. Finally, using two real and two synthetic datasets, we subject our algorithms to thorough ex- perimentation and empirical analysis. Our findings attest tothe efficiency and quality of our approximation algorithms for the top-k packages compared to exact algorithms.