Composite recommendations: from items to packages

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, several applications can benefit from a system capable of recommending packages of items, in the form of sets. Sample applications 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 number 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 domains, as well as to information sources which can provide the cost associated with each item. Because the problem of decidingwhether 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 recommendations. 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 experimentation and empirical analysis. Our findings attest to the efficiency and quality of our approximation algorithms for the top-k packages compared to exact algorithms.     

On recommendation problems beyond points of interest

Recommendation systems aim to recommend items or packages of items that are likely to be of interest to users. Previous work on recommendation systems has mostly focused on recommending points of interest (POI), to identify and suggest top-k items or packages that meet selection criteria and satisfy compatibility constraints on items in a package, where the (packages of) items are ranked by their usefulness to the users. As opposed to prior work, this paper investigates two issues beyond POI recommendation that are also important to recommendation systems. When there exist no sufficiently many POI that can be recommended, we propose (1) query relaxation recommendation to help users revise their selection criteria, or (2) adjustment recommendation to guide recommendation systems to modify their item collections, such that the users׳ requirements can be satisfied.We study two related problems, to decide (1) whether the query expressing the selection criteria can be relaxed to a limited extent, and (2) whether we can update a bounded number of items, such that the users can get desired recommendations. We establish the upper and lower bounds of these problems, all matching, for both combined and data complexity, when selection criteria and compatibility constraints are expressed in a variety of query languages, for both item recommendation and package recommendation. To understand where the complexity comes from, we also study the impact of variable sizes of packages, compatibility constraints and selection criteria on the analyses of these problems. Our results indicate that in most cases the complexity bounds of query relaxation and adjustment recommendation are comparable to their counterparts of the basic recommendation problem for testing whether a given set of (resp. packages of) items makes top-k items (resp. packages). In other words, extending recommendation systems with the query relaxation and adjustment recommendation functionalities typically does not incur extra overhead.     

PENETRATE: Personalized news recommendation using ensemble hierarchical clustering

Recommending online news articles has become a promising research direction as the Internet provides fast access to real-time information from multiple sources around the world. Many online readers have their own reading preference on news articles; however, a group of users might be interested in similar fascinating topics. It would be helpful to take into consideration the individual and group reading behavior simultaneously when recommending news items to online users. In this paper, we propose PENETRATE, a novel PErsonalized NEws recommendaTion framework using ensemble hieRArchical clusTEring to provide attractive recommendation results. Specifically, given a set of online readers, our approach initially separates readers into different groups based on their reading histories, where each user might be designated to several groups. Once a collection of newly-published news items is provided, we can easily construct a news hierarchy for each user group. When recommending news articles to a given user, the hierarchies of multiple user groups that the user belongs to are merged into an optimal one. Finally a list of news articles are selected from this optimal hierarchy based on the user’s personalized information, as the recommendation result. Extensive empirical experiments on a set of news articles collected from various popular news websites demonstrate the efficacy of our proposed approach.     

Cluster ensembles in collaborative filtering recommendation

Recommender systems, which recommend items of information that are likely to be of interest to the users, and filter out less favored data items, have been developed. Collaborative filtering is a widely used recommendation technique. It is based on the assumption that people who share the same preferences on some items tend to share the same preferences on other items. Clustering techniques are commonly used for collaborative filtering recommendation. While cluster ensembles have been shown to outperform many single clustering techniques in the literature, the performance of cluster ensembles for recommendation has not been fully examined. Thus, the aim of this paper is to assess the applicability of cluster ensembles to collaborative filtering recommendation. In particular, two well-known clustering techniques (self-organizing maps (SOM) and k-means), and three ensemble methods (the cluster-based similarity partitioning algorithm (CSPA), hypergraph partitioning algorithm (HGPA), and majority voting) are used. The experimental results based on the Movielens dataset show that cluster ensembles can provide better recommendation performance than single clustering techniques in terms of recommendation accuracy and precision. In addition, there are no statistically significant differences between either the three SOM ensembles or the three k-means ensembles. Either the SOM or k-means ensembles could be considered in the future as the baseline collaborative filtering technique.     

Learning the set covering machine by bound minimization and margin-sparsity trade-off

We investigate classifiers in the sample compression framework that can be specified by two distinct sources of information: a compression set and a message string of additional information. In the compression setting, a reconstruction function specifies a classifier when given this information. We examine how an efficient redistribution of this reconstruction information can lead to more general classifiers. In particular, we derive risk bounds that can provide an explicit control over the sparsity of the classifier and the magnitude of its separating margin and a capability to perform a margin-sparsity trade-off in favor of better classifiers. We show how an application to the set covering machine algorithm results in novel learning strategies. We also show that these risk bounds are tighter than their traditional counterparts such as VC-dimension and Rademacher complexity-based bounds that explicitly take into account the hypothesis class complexity. Finally, we show how these bounds are able to guide the model selection for the set covering machine algorithm enabling it to learn by bound minimization.     

Point set silhouettes via local reconstruction

We present an algorithm to compute the silhouette set of a point cloud. Previous methods extract point set silhouettes by thresholding point normals, which can lead to simultaneous over- and under-detection of silhouettes. We argue that additional information such as surface curvature is necessary to resolve these issues. To this end, we develop a local reconstruction scheme using Gabriel and intrinsic Delaunay criteria and define point set silhouettes based on the notion of a silhouette-generating set. The mesh umbrellas, or local reconstructions of one-ring triangles surrounding each point sample, generated by our method enable accurate silhouette identification near sharp features and close-by surface sheets, and provide the information necessary to detect other characteristic curves such as creases and boundaries. We show that these curves collectively provide a sparse and intuitive visualisation of point-cloud data.     

Context-aware recommendation using rough set model and collaborative filtering

Context has been identified as an important factor in recommender systems. Lots of researches have been done for context-aware recommendation. However, in current approaches, the weights of contextual information are the same, which limits the accuracy of the results. This paper aims to propose a context-aware recommender system by extracting, measuring and incorporating significant contextual information in recommendation. The approach is based on rough set theory and collaborative filtering. It involves a three-steps process. At first, significant attributes to represent contextual information are extracted and measured to identify recommended items based on rough set theory. Then the users’ similarity is measured in a target context consideration. Furthermore collaborative filtering is adopted to recommend appropriate items. The evaluation experiments show that the proposed approach is helpful to improve the recommendation quality.     

Distributed collaborative filtering with singular ratings for large scale recommendation

Collaborative filtering (CF) is an effective technique addressing the information overloading problem, where each user is associated with a set of rating scores on a set of items. For a chosen target user, conventional CF algorithms measure similarity between this user and other users by utilizing pairs of rating scores on common rated items, but discarding scores rated by one of them only. We call these comparative scores as dual ratings, while the non-comparative scores as singular ratings. Our experiments show that only about 10% ratings are dual ones that can be used for similarity evaluation, while the other 90% are singular ones. In this paper, we propose SingCF approach, which attempts to incorporate multiple singular ratings, in addition to dual ratings, to implement collaborative filtering, aiming at improving the recommendation accuracy. We first estimate the unrated scores for singular ratings and transform them into dual ones. Then we perform a CF process to discover neighborhood users and make predictions for each target user. Furthermore, we provide a MapReduce-based distributed framework on Hadoop for significant improvement in efficiency. Experiments in comparison with the state-of-the-art methods demonstrate the performance gains of our approaches.     

A context-aware recommender method based on text and opinion mining

A recommender system is an information filtering technology that can be used to recommend items that may be of interest to users. Additionally, there are the context-aware recommender systems that consider contextual information to generate the recommendations. Reviews can provide relevant information that can be used by recommender systems, including contextual and opinion information. In a previous work, we proposed a context-aware recommendation method based on text mining (CARM-TM). The method includes two techniques to extract context from reviews: CIET.5_embed, a technique based on word embeddings; and RulesContext, a technique based on association rules. In this work, we have extended our previous method by including CEOM, a new technique which extracts context by using aspect-based opinions. We call our extension of CARM-TOM (context-aware recommendation method based on text and opinion mining). To generate recommendations, our method makes use of the CAMF algorithm, a context-aware recommender based on matrix factorization. To evaluate CARM-TOM, we ran an extensive set of experiments in a dataset about restaurants, comparing CARM-TOM against the MF algorithm, an uncontextual recommender system based on matrix factorization; and against a context extraction method proposed in literature. The empirical results strongly indicate that our method is able to improve a context-aware recommender system.     

Sequential event prediction

In sequential event prediction, we are given a “sequence database” of past event sequences to learn from, and we aim to predict the next event within a current event sequence. We focus on applications where the set of the past events has predictive power and not the specific order of those past events. Such applications arise in recommender systems, equipment maintenance, medical informatics, and in other domains. Our formalization of sequential event prediction draws on ideas from supervised ranking. We show how specific choices within this approach lead to different sequential event prediction problems and algorithms. In recommender system applications, the observed sequence of events depends on user choices, which may be influenced by the recommendations, which are themselves tailored to the user’s choices. This leads to sequential event prediction algorithms involving a non-convex optimization problem. We apply our approach to an online grocery store recommender system, email recipient recommendation, and a novel application in the health event prediction domain.     

Utilizing various sparsity measures for enhancing accuracy of collaborative recommender systems based on local and global similarities

Collaborative filtering is a popular recommendation technique, which suggests items to users by exploiting past user-item interactions involving affinities between pairs of users or items. In spite of their huge success they suffer from a range of problems, the most fundamental being that of data sparsity. When the rating matrix is sparse, local similarity measures yield a poor neighborhood set thus affecting the recommendation quality. In such cases global similarity measures can be used to enrich the neighborhood set by considering transitive relationships among users even in the absence of any common experiences. In this work we propose a recommender system framework utilizing both local and global similarities, taking into account not only the overall sparsity in the rating data, but also sparsity at the user-item level. Several schemes are proposed, based on various sparsity measures pertaining to the active user, for the estimation of the parameter α, that allows the variation of the importance given to the global user similarity with regards to local user similarity. Furthermore, we propose an automatic scheme for weighting the various sparsity measures, through evolutionary approach, to obtain a unified measure of sparsity (UMS). In order to take maximum possible advantage of the various sparsity measures relating to an active user, a scheme based on the UMS is suggested for estimating α. Experimental results demonstrate that the proposed estimates of α, markedly, outperform the schemes for which α is kept constant across all predictions (fixed-α schemes), on accuracy of predicted ratings.     

Retiming synchronous circuitry

This paper describes a circuit transformation calledretiming in which registers are added at some points in a circuit and removed from others in such a way that the functional behavior of the circuit as a whole is preserved. We show that retiming can be used to transform a given synchronous circuit into a more efficient circuit under a variety of different cost criteria. We model a circuit as a graph in which the vertex setV is a collection of combinational logic elements and the edge setE is the set of interconnections, each of which may pass through zero or more registers. We give anO(¦V∥E¦lg¦V¦) algorithm for determining an equivalent retimed circuit with the smallest possible clock period. We show that the problem of determining an equivalent retimed circuit with minimum state (total number of registers) is polynomial-time solvable. This result yields a polynomial-time optimal solution to the problem of pipelining combinational circuitry with minimum register cost. We also give a chacterization of optimal retiming based on an efficiently solvable mixed-integer linear-programming problem.     

Folkommender: a group recommender system based on a graph-based ranking algorithm

With the rapid popularity of smart devices, users are easily and conveniently accessing rich multimedia content. Consequentially, the increasing need for recommender services, from both individual users and groups of users, has arisen. In this paper, we present a new graph-based approach to a recommender system, called Folkommender, that can make recommendations most notably to groups of users. From rating information, we first model a signed graph that contains both positive and negative links between users and items. On this graph we examine two distinct random walks to separately quantify the degree to which a group of users would like or dislike items. We then employ a differential ranking approach for tailoring recommendations to the group. Our empirical evaluations on two real-world datasets demonstrate that the proposed group recommendation method performs better than existing alternatives. We also demonstrate the feasibility of Folkommender for smartphones.     

A collaborative user-centered framework for recommending items in Online Social Networks

Recommender Systems are more and more playing an important role in our life, representing useful tools helping users to find “what they need” from a very large number of candidates and supporting people in making decisions in various contexts: what items to buy, which movie to watch, or even who they can invite to their social network, etc. In this paper, we propose a novel collaborative user-centered recommendation approach in which several aspects related to users and available in Online Social Networks – i.e. preferences (usually in the shape of items’ metadata), opinions (textual comments to which it is possible to associate a sentiment), behavior (in the majority of cases logs of past items’ observations made by users), feedbacks (usually expressed in the form of ratings) – are considered and integrated together with items’ features and context information within a general framework that can support different applications using proper customizations (e.g., recommendation of news, photos, movies, travels, etc.). Experiments on system accuracy and user satisfaction in several domains shows how our approach provides very promising and interesting results.     

Product recommendation with temporal dynamics

In many E-commerce recommender systems, a special class of recommendation involves recommending items to users in a life cycle. For example, customers who have babies will shop on Diapers.com within a relatively long period, and purchase different products for babies within different growth stages. Traditional recommendation algorithms produce recommendation lists similar to items that the target user has accessed before (content filtering), or compute recommendation by analyzing the items purchased by the users who are similar to the target user (collaborative filtering). Such recommendation paradigms cannot effectively resolve the situation with a life cycle, i.e., the need of customers within different stages might vary significantly. In this paper, we model users’ behavior with life cycles by employing hand-crafted item taxonomies, of which the background knowledge can be tailored for the computation of personalized recommendation. In particular, our method first formalizes a user’s long-term behavior using the item taxonomy, and then identifies the exact stage of the user. By incorporating collaborative filtering into recommendation, we can easily provide a personalized item list to the user through other similar users within the same stage. An empirical evaluation conducted on a purchasing data collection obtained from Diapers.com demonstrates the efficacy of our proposed method.     

Alleviating the new user problem in collaborative filtering by exploiting personality information

The new user problem in recommender systems is still challenging, and there is not yet a unique solution that can be applied in any domain or situation. In this paper we analyze viable solutions to the new user problem in collaborative filtering (CF) that are based on the exploitation of user personality information: (a) personality-based CF, which directly improves the recommendation prediction model by incorporating user personality information, (b) personality-based active learning, which utilizes personality information for identifying additional useful preference data in the target recommendation domain to be elicited from the user, and (c) personality-based cross-domain recommendation, which exploits personality information to better use user preference data from auxiliary domains which can be used to compensate the lack of user preference data in the target domain. We benchmark the effectiveness of these methods on large datasets that span several domains, namely movies, music and books. Our results show that personality-aware methods achieve performance improvements that range from 6 to 94 % for users completely new to the system, while increasing the novelty of the recommended items by 3–40 % with respect to the non-personalized popularity baseline. We also discuss the limitations of our approach and the situations in which the proposed methods can be better applied, hence providing guidelines for researchers and practitioners in the field.     

Collaborative filtering based on collaborative tagging for enhancing the quality of recommendation

We propose a collaborative filtering method to provide an enhanced recommendation quality derived from user-created tags. Collaborative tagging is employed as an approach in order to grasp and filter users’ preferences for items. In addition, we explore several advantages of collaborative tagging for data sparseness and a cold-start user. These applications are notable challenges in collaborative filtering. We present empirical experiments using a real dataset from del.icio.us. Experimental results show that the proposed algorithm offers significant advantages both in terms of improving the recommendation quality for sparse data and in dealing with cold-start users as compared to existing work.     

Div-clustering: Exploring active users for social collaborative recommendation

Collaborative recommendation (CR) is a popular method of filtering items that may interest social users by referring to the opinions of friends and acquaintances in the network and computer applications. However, CR involves a cold-start problem, in which a newly established recommender system usually exhibits low recommending accuracy because of insufficient data, such as lack of ratings from users. In this study, we rigorously identify active users in social networks, who are likely to share and accept a recommendation in each data cluster to enhance the performance of the recommendation system and solve the cold-start problem. This novel modified CR method called div-clustering is presented to cluster Web entities in which the properties are specified formally in a recommendation framework, with the reusability of the user modeling component considered. We improve the traditional k-means clustering algorithm by applying supplementary works such as compensating for nominal values supported by the knowledge base, as well as computing and updating the k value. We use the data from two different cases to test for accuracy and demonstrate high quality in div-clustering against a baseline CR algorithm. The experimental results of both offline and online evaluations, which also consider in detail the volunteer profiles, indicate that the CR system with div-clustering obtains more accurate results than does the baseline system.     

A unified framework for recommending items,groups and friends in social media environment via mutual resource fusion

Up to now, more and more online sites have started to allow their users to build the social relationships. Take the Last.fm for example (which is a popular music-sharing site), users can not only add each other as friends, but also join online interest groups where they shall meet people with common tastes. Therefore, in this environment, users might be interested in not only receiving item recommendations (such as music), but also getting friend suggestions so they might put them in the contact list, and group recommendations that they could consider joining. To support such demanding needs, in this paper, we propose a unified framework that provides three different types of recommendation in a single system: recommending items, recommending groups and recommending friends. For each type of recommendation, we in depth investigate the contribution of fusing other two auxiliary information resources (e.g., fusing friendship and membership for recommending items, and fusing user-item preferences and friendship for recommending groups) for boosting the algorithm performance. More notably, the algorithms were developed based on the matrix factorization framework in order to achieve the ideal efficiency as well as accuracy. We performed experiments with two large-scale real-world data sets that contain users’ implicit interaction with items. The results revealed the effective fusion mechanism for each type of recommendation in such implicit data condition. Moreover, it demonstrates the respective merits of regularization model and factorization model: the factorization is more suitable for fusing bipartite data (such as membership and user-item preferences), while the regularization model better suits one mode data (like friendship). We further enhanced the friendship’s regularization by integrating the similarity measure, which was experimentally proven with positive effect.