In this paper we describe details of our approach to the RecSys Challenge 2014: User Engagement as Evaluation. The challenge was based on a dataset, which contains tweets that are generated when users rate movies on IMDb (using the iOS app in a smartphone). The challenge for participants is to rank such tweets by expected user interaction, which is expressed in terms of retweet and favorite counts. During experiments we have tested several current off-the-shelf prediction techniques and proposed a variant of item biased k-NN algorithm, which better reflects user engagement and nature of the movie domain content-based attributes. Our final solution (placed in the third quartile of the challenge leader board) is an aggregation of several runs of this algorithm and some off-the-shelf predictors. In the paper we will further describe dataset used, data filtration, algorithm details and settings as well as decisions made during the challenge and dead ends we explored.
Recommending on the web is both an important commercial application and popular research topic. The amount of data on the web grows continuously and it is virtually impossible to process it directly by a human. Various tools ranging from keyword search engines to binary intra e-shop search or product aggregators were adopted to fight against information overload. Although such tools are definitely useful, they can be used only if the user is able to specify in detail what he/she wants. Recommender systems are complementary to this scenario as they are mostly focused on serendipity – showing surprisingly interesting items the user was not aware of and thus couldn’t search for them by keywords.
Many recommender systems, algorithms or methods have been presented so far. Initially, the majority of research effort was spent on the collaborative systems and explicit user feedback. Although collaborative recommender systems are generally trusted to be more accurate, they suffer from three well known problems: cold start, new object and new user problem.
New user / object problem is a situation, where recommending algorithm is incapable of making relevant prediction because of insufficient feedback about current user / object. The cold start problem refers to a situation short after deployment of recommender system, where the system cannot provide any relevant recommendation, because of insufficient data generally.
Using attributes of objects and hence content based or hybrid recommender systems can speed up learning curve and reduce the cold start problem. Moreover, content-based recommender systems can compute similarity of a new object based on its features effectively eliminating the new object problem.
Our deep belief is that quality of data used for recommendation are often more important than the algorithm which processes them. In another words rather than designing a brand new algorithm we focus on enhancing our datasets and using state-of-theart or slightly modified algorithms to improve predictions.
The task of 2014 RecSys Challenge1 ([
The dataset covers the period from February 2013 to March 2014 and contains in total almost 213,000 tweets from 24,000 users about 15,000 movies. The dataset was divided into training, test and validation subsets based on the timestamp when the tweet was created. Evaluation of the task was based on nDCG metric considering top 10 tweets for each user.
The rest of the paper is organized as follows: review of some related work is in
section 2. In section 3 we provide some insight on the task and how it affected our
solution [
Due to the space reasons, we can provide only a short review of the related work. For general information and introduction to the recommender systems, we suggest
2 http://www.imdb.com
3 https://github.com/sidooms/MovieTweetings/tree/master/recsyschallenge2014
Recommender Systems Handbook [
We would like to mention also our own previous work, which affected our
approach: In [
Our work is also related to the area of linked data. An inspiration to our previous
work was the research by Ostuni et al. [
The area of recommending on social networks is currently well covered in the
research. We would like to mention e.g. Hannon et al. [
This section aims on discussion and initial analysis of the challenge task, focusing mainly on design choices implied by the nature of the task.
The dataset provided by the challenge organizers consisted of user, tweet and item identification, timestamp when the tweet was scraped, user rating of the movie and all information available from the tweet API excerpt from the text of the tweet (see Fig
ure 1). The textual information would be extremely important for prediction of user
engagement in other datasets, but automatically generated tweets from IMDb contain
only template text and thus are not much relevant. The same reason makes also tweet
topic categorization (e.g. CatStream [
The user engagement is generally low throughout the dataset. The average user
engagement in the training set is 0.216, over 95% of the tweets have zero user
engagement and almost 80% of users received zero engagement for all of their tweets. The
situation seems to be similar to the number of purchases on an e-commerce site,
where most of the users only browse items, but do not buy one. Our experiments on
such domain [
Prior to the experiments, we have conducted a small survey of available movie datasets. The IMDb, DBPedia6, and Freebase7 were examined concluding that IMDb contains most of the relevant information available in the other two datasets. Due to 100% coverage of items (each tweet was based on single IMDb object) and availability of querying API8 we decided to use sole IMDb for dataset enhancements. The movie features used in our solution can be distinguished into three classes: Attributes describing popularity (average rating, number of awards, IMDb metascore) Attributes describing widespread of the movie (number of ratings) Attributes describing content (movie name, release date, genre, country, language, director, actors)
There is however some space left for further improvements especially by employing DBPedia features like dcterms:subject or widespread metrics like ingoing / outgoing links or number of Wikipedia language editions.
The test dataset contains large number of new movies unseen in the training data, so we expect that purely collaborative recommenders will not provide very good predictions. Another possible limitation is large number of zero user engagement. This caused problems to some algorithms (e.g. decision trees) as they almost constantly predicted zero for all tweets. The problem can be bypassed e.g. by filtering out (some) examples with zero engagement or by copying other tweets. The task is also not well
7 http://www.freebase.com 8 http://www.omdbapi.com suited for the purely content-based recommenders as there are new users in the test dataset and also for many users we have only a few tweets available. We are deeply convinced that crucial for any recommending task is to estimate on which variables the final success may depend. In the current case each tweet contains almost the same text except for the name of the movie and the user rating, so we do not expect that the tweet itself can affect user engagement.
Important variable determining user engagement is probably composition of user friends and followers. Unfortunately the dataset contains only total numbers of friends and followers for each user, not the variables describing them, but we can at least employ user bias defining average engagement for each user.
Another important component is, according to our assumption, features of the movie that the tweet refers to. The sole movie ID may not be enough as there are numerous new movies in the test set and some movies are not rated with enough users. Thus we need to define content-based similarity between movies under assumption that similar movies will be treated similarly.
Also the date when the tweet was posted may be interesting since the structure of friends or followers might change over time and also popularity of the movie may evolve, but we expect that relation of previous components should be stronger and so we did not pursue this direction and leave it for the future work. The same applies also for the dependence between user rating and user engagement. 4
Engagement of similar movies should be similar. Engagement depends on neighborhood of the current user.
In order to define inter-movie similarity, we used IMDb querying API to generate content-based attributes. We also considered using DBPedia or Freebase, but IMDb contains most of the relevant information and furthermore offers guaranteed 100% item coverage. Three types of attributes were downloaded: attributes describing popularity (average rating, number of awards, IMDb metascore), attributes describing widespread of the movie (number of ratings), attributes describing content (movie name, release date, genre, country, language, director, actors).
The second hypothesis reflects our expectation that composition of user friends and followers would greatly affect observed engagement. The twitter API contains only aggregated information (total numbers of friends and followers for each user), so we decided to use simple user bias instead of machine learning over user’s friends.
Prior to the design of our own recommending algorithm we evaluated several offthe-shelf algorithms using RapidMiner and its Recommender extension. As expected, results of both collaborative-filtering and standard machine learning algorithms were except for SVM rather unsatisfying. Table 1 contains the best achieved results for each algorithm over different settings. Some dataset transformations (e.g. omitting records with zero engagement from the training set, transformation of user engagement in training set etc.) were also examined, but they did not significantly improve the results. = max(0, ) According to the assumptions and hypothesis formulated in Section 3, we decided to pursue especially content-based movie similarity. We implemented a variant of well known k-nearest-neighbors as our main individual recommender (see Algorithm 1), where similarity of tweets is determined as content-based similarity of the respective movies. The similarity is defined as average of attributes similarities. Attribute similarity is defined according to attribute type. Similarity of numeric attributes (average rating, number of ratings, number of awards, IMDb metascore and release date) is defined as their difference normalized by maximal allowed distance (1).
− | − |
For string attributes (movie name) the similarity is defined as inverse of relative Levenshtein distance (2). This allows us to define as similar e.g. movie series.
Finally, similarity of set attributes (genre, country, director and actors) is defined as Jaccard similarity (3). Note that nominal attributes can be dealt as sets of size 1.
Differences between audiences of users will be considered in the form of user bias (average value of engagement per user). The bias of current user is not important, as the evaluation is on per user base, however the bias of other users should be considered within the k-NN algorithm.
Algorithm 1: Hybrid biased k-NN algorithm: for tweet tIDte from the test set, its movie mIDte and fixed k, the algorithm first computes similarities to other movies in training set and selects k most similar movies. Then for each tweet about a similar movie the predicted ranking ̂ is increased according to similarity , user engagement e and bias of the tweeting user. The bias of the current movie is added in the final ̂ prediction too (see Figure 1). function HybridBiasedKNN(tIDte ϵ TestSet, k){ ̂ = 0; extract mIDte from tIDte, extract uIDte , extract mIDte content from IMDb /*compute similarity for all movies */ foreach(mID ϵ TrainSet){
S[mID] = similarity(mIDte, mID); } /*get k most similar movies */ S̅ = getKMostSimilar(mIDte,S,k); /*get all tweets about movies in S̅ */ foreach({uID, mID, e, }: {uID, mID, e} ϵ TrainSet && S̅[mID]= ){ ̂ += * e / bias(uIDte);} ̂ = bias(mIDte) + ( ̂ / sum( )) return tIDte, ̂; }
Several meta modeling techniques were used to derive final predictions based on hybrid k-NN and off-the-shelf algorithms predictions. We have experimented with stacking with random trees, linear regression in cross-validation like setting and also tried several variants of averaging selected predictions (omitting portion of highest and lowest predictions for each tweet). 4.2
Table 2 contains results of several variants of hybrid k-NN algorithm as well as best aggregated predictions (for the sake of clarity we show only a fraction of results expressing different aspects of the data). Generally spoken, the best performing individual recommender was SVM followed by several variants of hybrid k-NN. Almost all experimented settings of hybrid k-NN outperformed other standard machine learning methods (Table 1). Surprisingly, stacking based ensemble did not predict well, probably due to dependence of the results on user, which is hard to express with decision trees. Also linear regression did not improve results, but averaging results of selected algorithms provided a significant improvement over the best individual recommenders.
While evaluating Hybrid Biased k-NN we focused mainly on the utility of each attribute, using of user bias and also ways to combine results from multiple algorithm settings. Only a fraction of our results can be shown due to the space reasons. We can state that most of the attributes used as sole similarity measure provided good results (especially IMDb metascore, director, country and language) – see Table 2.
Avg rating 0.7918 Movie 0.7947 Language 0.8005 name Awards 0.7652 Date 0.7962 Director 0.8029 Metascore 0.8057 Genre 0.7919 Actors 0.7930 # of ratings 0.7964 Country 0.7984
One of our research questions was which value to use as user engagement e. The experiments showed that if using directly sum of retweets and favorites, the algorithm is highly dependent on using user bias. Another option was to use rank of the tweet in the list of current user’s tweets ordered by user engagement (rank of the tweet should better reflect considered success metric). Under this setting was algorithm less dependent on using bias, however overall results were slightly worse.
Another question was how to interpret if all tweets of a user have constantly zero user engagement. Omitting those users from the training set however resulted into the decrease of performance so we suppose that even these tweets carries some negative evidence. Comparing with off-the-shelf algorithms, almost all variants of Hybrid kNN achieved better results.
The neighborhood size k between 50 and 100 provided good results. We also tried numerous variants of combining attribute similarities within the Hybrid k-NN algorithm (omitting some attributes, weighting schemas) and ensemble methods (stacking, linear regression), but so far the best results was achieved by simple average of single attribute predictions omitting single top and bottom result – see Table 3.
In this paper, we presented our solution to the RecSys Challenge 2014. After analysis of the task, available data and current prediction techniques, we proposed a variant of k-NN algorithm leveraging content-based similarity of movies. The algorithm performed comparably with the best examined prediction techniques and the best results were achieved after averaging results of multiple runs of hybrid k-NN and SVM. Our solution was placed ninth in the challenge leader board. Some of our ideas didn’t work as we expected, namely using more advanced ensemble techniques and using ranks of the tweet instead of its user engagement resulted in worse predictions.
There are several directions of the future work. In our research so far we did not pursue temporal dependence at all which could also affect user engagement. The defined movie similarity should be also examined and tuned. We could also try to employ tweet similarity instead of movie similarity (we didn’t so far for the sake of computation effectivity). Also other procedures to aggregate results from multiple algorithms should be examined. Last but not least enhancing current dataset with e.g. DBPedia popularity measures should be considered.
Concerning data structures for similarity search and indexing – the query object is
usually multimodal ([