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...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.展开更多
文摘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.
