Recommendation System for Travellers Based on TripAdvisor.com Data. Bachelor’s thesis

In a classical fashion, the majority of recommender systems can be separated into the three categories based on their approach towards matching of the new user's input data to an existing database in order to produce relevant recommendations:

a) Content-based filtering approach that is based on the varying degrees of similarity between different items;

b) Collaborative filtering approach that is frequently based on the so-called “neighbourhoods” of similar users;

c) Hybrid filtering approach which aspires to combine in the most balanced and efficient way both of the above approaches (Lu et al., 2015).

To start with, the way a content-based recommender system functions is: firstly, by calculating the similarity between all of the items in a database, for instance, movies, news articles or travel destinations; and then, as a given user updates the system with their item ratings, present that user with a recommendation of items, which were previously measured to be similar to the ones that user has rated the highest. Thus, with content-based filtering the ultimate user recommendation depends exclusively on that single user's profile as well as obviously on the database of item profiles. The origins of the content-based filtering recommenders can be traced back to the first inklings of research in the areas of information retrieval and information filtering techniques, which became to be most extensively applied in the field of Natural Language Processing. For this reason the content-based filtering approach is commonly employed by the recommendation algorithms that are focused on measuring the similarity between chunks of textual data from item contents. Thus, item profiles are often described in terms of keywords, and the similarity between them is calculated via the special measure of term frequency and inverse document frequency metric, commonly abbreviated as TF-IDF, which can be produced in the following way:

where: - the total number of the keyword's appearances in the document ;

- the most frequently encountered keyword in the document;

- the total number of documents;

- the total number of the documents within which the keyword is present (Lops et al., 2011).

In simple terms, the goal behind this basic metric is to identify keywords in a document that are the most relevant for the document's topic, by means of recording the keywords that occur most frequently within that specific document (term frequency) and that are, at the same time, among the least frequently occurring in the general corpus of all other documents (inverse document frequency). This way, the weight of each document is computed as the product of the TF and IDF values (Adomavicius & Tuzhilin, 2005). As a result, based on the weights of documents, the degree of closeness between every single document in the overall corpus can be easily identified either with the help of various distance metrics, for instance the Euclidean distance or the Manhattan distance, or similarity measures, by far the most common of which is the cosine vector similarity (Lops et al., 2011).

However, the overwhelming majority of modern recommender systems do not exclusively rely on such obsolete heuristic methods as basic similarity measures, instead they employ machine learning algorithms that create predictive models by training them on the input data of users. Thus, content-based recommenders are generally divided into the two major subgroups of classifier-based and nearest neighbour-based models (Portugal et al., 2018). The former ones probabilistically assess all the items that have not been rated by a user according to the binary categories of either “recommend” or “do not recommend” based on the user profiles of item ratings, for example, a wide variety of the decision tree models and Bayesian network methods; while the latter models separate all of the items into clusters based on how similar they are, in order to recommend those items that share the same cluster with the ones a given user has rated the highest, for instance, applying the k nearest neighbour classifier technique to the cluster centres produced in the result of the k-means clustering method (Lops et al., 2011).

One of the main problems inherent in the content-based recommendation systems is the extreme homogeneity of recommended items as well as the narrowness of the overall recommendation range. Users are continuously presented with items too similar to those they liked while being completely unable to discover brand new items, which have slightly different profiles of characteristics but may still be of much interest to them. Moreover, the goal of making highly accurate recommendations of items that are too much alike appears to be a much worse method, then trying to diversify the range of recommended items, for instance, suggesting a myriad of similar news articles that, in fact, cover exactly the same event (Adomavicius & Tuzhilin, 2005).

Speaking of the collaborative filtering recommender systems, the key task of such an approach is to predict the relevance (or the rating scores) of items for a particular user based on the similar profiles of other users present in the database, that way quite literally making all the users collaborate in producing a good recommendation for any single user. The respective family of recommendation methods are commonly further separated into the following two major classes: the memory-based and the model-based ones. The simple core difference between these two types of collaborative algorithms is that the memory-based ones make calculations over and store in computer memory the entire user database in order to produce statistical predictions of item ratings for the new users, while the model-based ones employ various machine learning models in order to, firstly, train them on an available compiled dataset and, then, use them to make predictions for new users (Breese et al., 1998). Each of the two types of collaborative filtering algorithms is associated with its major respective group of specific methods which are, namely, the user neighbourhood methods and the latent factor models respectively. Firstly, the former are focused on measuring similarity between either users or items. However, even though the neighbourhood methods might exploit the attributes of items, unlike the content-based algorithms they make a recommendation based not solely on item similarity, but rather on the similarity between users, that way being able to identify like-minded individuals and recommend to each of them those items which they do not share both, but only one of them has rated. Latent factor models, in their own turn, infer the presence of implicit descriptive factors that can be revealed from certain arbitrary, yet computer discernible patterns in the user-item data (Koren, Bell & Volinsky, 2009).

Although the collaborative filtering approach can be applied by means of many of the same most basic classification and regression methods that were mentioned previously for the content-based approach, such as the various distance, correlation and similarity measures, the probabilistic classifiers (decision tree, random forest and Bayesian models), regression models (linear, polynomial or logistic) and clustering methods, the present paper is going to focus on one of the most promising types of machine learning models for collaborative filtering called the latent factor models, for the main reason that these types of algorithms have proven to deal with huge and sparse datasets more efficiently than the majority of other standalone techniques (Koren et al., 2009).

Latent factor models have been most extensively studied in the research domains of: the Natural Language Processing techniques, with the specific examples including, but not limited to the probabilistic Latent Semantic Analysis (pLSA) being used for information retrieval (Hofmann, 2004) and the Latent Dirichlet Allocation (LDA) employed in text classification (Blei et al., 2003); as well as in the context of the major recommender system algorithms and dimensionality reduction techniques, some examples of which are the matrix factorisation-like methods of singular value decomposition (SVD) being applied for the dimensionality reduction of a user-item ratings matrix (Billsus & Pazzani, 1998).

However, it can be easily argued that one of the most widely known of the latent factor models for collaborative filtering are the matrix factorisation models. These methods have dramatically gained in popularity as a result of the Netflix Prize open competition in the year of 2009, when an SVD algorithm, which later became widely known after its creator as the FunkSVD, was specifically tuned and applied by Simon Funk to produce very surprising improvements in the accuracy of movie recommendations (Piatetsky-Shapiro, 2007). The basic methodology behind the matrix factorisation techniques is based on, firstly, representing both items and users as vectors of latent factors and, then, recommending to users only those items that produce the highest dot product between those factor vectors. Due to the fact that those matrices of user-item interactions often suffered from the data sparsity problem and, as a result, most machine learning models tended to drastically overfit, for the matrix factorisation a regularisation parameter could be naturally implemented into the process of minimising the following squared prediction error, in order to penalise for the extremely high factor vector norms for items and users:

where: - the actual rating of the user u for the item i;

- the unknown factor vector for each item i that is being predicted;

- the unknown factor vector for each user u that is being predicted;

- the dot product, i.e. the predicted rating of the user u for the item i;

- denotes the norm;

- represents the set of user-item pairs where ratings are known;

- the regularisation term (Koren et al., 2009).

There exists a wide range of variations of the matrix factorisation methods that continue to still be experimented with in the domain of recommender system research. The selected range of the three of the most accurate and frequently cited singular matrix factorisation methods, which operate on the basis of noncategorical variables and which without exceptions have all been almost exclusively tested on the most widespread and abundant content of film databases, has been assembled to be the following: the SVD, the SVD++ as well as the NMF algorithms, with every one of them being optimized by means of the regularized SGD learning method (Cacheda el al., 2011; Koren et al., 2009).

First and foremost, the well-established matrix factorisation-like model called the Singular Value Decomposition (SVD), which has proved to be the most accessible out of the range of factorisation methods and at the same time highly efficient with sparse data among other collaborative filtering methods (Cacheda et al., 2011; Gorell, 2016). The basic version of SVD does not deal too well with the data sparsity problem of a user-item matrix, and, when still applied to the very meagre amount of known values, it understandably tends to overfit and fails to make sound predictions for the new users. Initially, most of the research efforts were directed to adapting various data imputation techniques as a way to increase the density of interaction matrices. However, this approach most of the time proves to be extremely costly as well as too complex and case specific (Ranjbar et al., 2015). For this reason a more general and straightforward technique was proposed to yield the double benefits of, firstly, the implementation of the abovementioned regularisation term and, secondly, of including additional bias parameters for each user and each item, which are actually meant to account for the larger part of variations in ratings that are caused by the independent effects associated with particular users and items (Koren et al., 2009; Paterek, 2007). Thus, the ratings prediction formula is modified to include the biases and set to be calculated according to the following four components:

;

where: - the global average rating across all known data points;

- the user bias reflecting the general tendencies of how the user u rates items;

- the item bias reflecting the general tendencies of how the item i is rated by users;

- the dot product of factor vectors accounting for the user-item interaction (Koren et al., 2009).

As a side note, in the cases of considering the addition of a new user or a new item, all of the associated biases and factors are, at first, assumed to be zero. As a result, the problem of minimising the squared error turns to be the following:

where: - the actual rating of the user u for the item i;

- the predicted rating of the user u for the item i;

- the user bias reflecting the general tendencies of how the user u rates items;

- the item bias reflecting the general tendencies of how the item i is rated by users;

- the unknown factor vector for each item i that is being predicted;

- the unknown factor vector for each user u that is being predicted;

- denotes the norm;

- represents the set of actual ratings in the training dataset;

- the regularisation term (Koren et al., 2009).

Furthermore, the unique contribution of the already mentioned Simon Funk's SVD (FunkSVD) algorithm was that it employed the regularisation term as well as a learning algorithm of Stochastic Gradient Descent (SGD), which became widely known for the accessibility of its implementation on the large-scale datasets, especially the ones that are heavily afflicted by the data sparsity problem, as well as for its fairly short running time of the core computations and the subsequent evaluation process, which is due to the fact that SGD stores in memory only the most recently computed rating prediction errors (Lin, 2007). Without going into too much application details, the SGD optimisation algorithm is employed to circle through all of the available data points and make predictions of user ratings, each time readjusting the user and item factor vectors based on the rating predictions' error, until eventually arriving at the optimal pairs of user and item biases as well as of user and item factor vectors, as can be specified in the following mathematical fashion:

;

;

;

;

;

where: - the actual rating of the user u for the item i;

- the predicted rating of the user u for the item i;

- the unknown factor vector for each item i that is being predicted;

- the unknown factor vector for each user u that is being predicted;

- the rating prediction error of the user u for the item i;

- the regularisation term;

- the learning rate (Koren et al., 2009).

Alternatively, soon after the Netflix Prize open competition, where the FunkSVD attracted much attention to the SGD learning algorithm, another optimisation algorithm was popularised by the name of Alternating Least Squares (ALS), which, in essence, is performed by fixing all the factor vectors for users, in order to compute the ones for items, and then switching around to predict those for users through minimising the sum of the squared residuals (Rendle, 2012). The two common use cases for this approach have been observed to be the following: firstly, it can be very efficiently used in the scenario of when the recommender's system is computationally capable enough to sustain the parallelisation of its predictive algorithm's execution; and also, especially in the case of the recommender algorithm being trained on the more abundant implicitly collected data of users, as it would be impractical to apply ALS on the too sparse explicit data (Hu et al., 2008).

Second of all, the enhanced version of the FunkSVD algorithm called the SVD++ was also proposed in order to take into account the implicit ratings of users as well, which can be defined as the fact that a given user has rated a certain item, regardless of what that actual rating value was. Due to the incorporation of implicit ratings, the SVD++ method, when applied on the regularised squared error with the SGD optimisation, often shows an improvement in the accuracy of rating predictions over the FunkSVD algorithm, albeit a small one (Cacheda et al., 2011). As for the calculation of the predicted rating, the new set of factors reflecting the implicit ratings are incorporated as follows:

;

where: - the global average rating across all known data points;

- the user bias reflecting the general tendencies of how the user u rates items;

- the item bias reflecting the general tendencies of how the item i is rated by users;

- the unknown factor vector for each item i that is being predicted;

- the unknown factor vector for each user u that is being predicted;

- the total number of implicit ratings of user u;

- the new set of factor terms that captures implicit ratings (Koren, 2008).

Last, but not least of the three selected matrix factorisation algorithms, the Non-Negative Matrix Factorisation (NMF) algorithm simply introduces a non-negativity constraint to the basic SVD algorithm for both the user and item parameters, which are being calibrated as the training model continues to learn, for the main reason of ensure that the predictions of a data feature values are a more appropriate representation of a user's interests. In order to actualise this constraint the algorithm basically rescales the learning rate to exclude all of the negative components from predicted factor vectors of users and items, that way leaving only the non-negative ones to compute the next iteration of a predicted rating and of its respective error (Luo et al., 2014). Thus, the stages of the SGD learning algorithm are slightly modified in the following way to calculate only the non-negative user and item factors of and respectively, requiring the starting factor values to be positive as well:

;

;

where: - the factor f of the vector which is predicted for each user u;

- the factor f of the vector which is predicted for each item i;

- the new regularisation parameter for user u;

- the new regularisation parameter for item i (Luo et al., 2014).

Hybrid recommendation systems, as the name suggests, combine the two approaches described before to minimise the drawbacks of each one taken individually. Adomavicius and Tuzhilin (2005) identify four types of hybrid systems. The first type is creating one content-based and one collaborative filtering recommender and combining their results either via voting or linear combination of their outputs. The second type combines collaborative filtering with some content-based system features. Some of the examples include assigning a content-based profile to each user and then finding similar user profiles instead of similar sets of rated items. The third method incorporates some content-based model characteristics into collaborative filtering. One of the approaches described is similar to matrix factorisation, but instead of reducing dimensionality of a simple user-item rating matrix it utilises user content profiles as described in the second approach. Finally, there are systems that combine both content-based and collaborative filtering approach in equal proportion (Adomavicius & Tuzhilin, 2005).

As Portugal et al. (2018) showcase in their systematic review of the various recommender system methodologies, in the course of the past ten years the collaborative filtering (66 papers) algorithms have gained more attention from academics than the content-based (45 papers) and hybrid (18 papers) ones. Moreover, neighbourhood and model-based collaborative filtering approaches have each of them generated vastly more attention as compared to the years before the 2012; while the hybrid recommender methodology remained to be the least researched out of the three classical approaches, which is, for the large part, due to the fact that it does not have any singular filtering methods directly associated with it, but rather requires a more consuming effort of assembling a whole recommender system out of any combination of the different types of filtering methods.

Burke (2002) was the first one to propose a solid classification of such ways of combining the contributions made by each of the two recommender approaches, otherwise known as hybridisation methods. The first and consequently the most popular one of these methods is the weighted one, which weighs the employed recommender algorithms according to their predictive accuracy, by means of assigning them with a set of votes to denote the extent of their contribution to the ultimate user recommendation. Furthermore, the other two methods that usually act as alternatives to the weighted one and that, unlike the weighted method, can be appropriately employed not only when combining techniques of the same relative value are called switching and mixed hybridisation methods; with the first one consisting in switching between recommender techniques depending on the present-moment system tasks and the latter one being applied whenever a side-by-side recommendation output from both techniques is more favourable. Furthermore, feature combination hybrid is a method of implementing both collaborative and content-based features for the purposes of producing a single recommendation. Quite unlike feature combination, feature augmentation does not converge the different techniques, but sequences them in a way that the recommendation output of one technique acts as feature input to the other. Similarly, the cascade method unravels in a staged process, however, the one in which recommendation output from the first technique is used only for further refinement by the next one. Lastly, an even more unique case of creating a confluence of the two different filtering approaches has been proposed as the meta-level method, which is similar to the feature augmentation, however the next technique in a sequence takes as its input not the previous one's feature, but instead incorporates the previous recommender technique as a whole; for instance, several content-based models are employed to predict restaurant preferences for every separate user, and then these basic models, which, in essence, are just vectors of estimates, are fed into a collaborative filtering model to make predictions by comparing across users (Burke, 2002).

Due to the reason that the TripAdvisor platform incorporates features of a social network to enhance the quality of its travel recommendations and to promote independent communities of active users, it is necessary to point out the specifics of recommender systems that operate on the basis of social trust networks. First of all, the term social trust can be defined as a connection between a pair of users based on either explicit feedback (subscription, voting, commenting) or implicit feedback (frequency of interactions: page visits, message exchanges) (Yang et al., 2014). In parallel to the two types of feedback, there is a respective distinction between two types of alternative data sources that are assumed to enhance recommendation quality: rich side information on items and users and interaction-associated information. The former is mainly concerned with recording social trust relationships between users by exploring a subscription-based social network or by analysing various user-contributed data, like numerical ratings and textual reviews, photo and video material as well as social tags and geotags; while the latter most commonly covers information on time, location and user mood status recorded at particular instances of user-item interactions (Shi et al., 2014).