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

Ever since the dawn of the recommender system research, the assessment of the recommendation quality as well as of the system's overall performance have quickly become a vital part of the field. Thus, over the years the recommender systems' performance evaluation metrics have been developed into the following four broad classes of: (a) the accuracy metrics for the ratings prediction, such as the Mean Absolute Error (MAE), the Root of Mean Square Error (RMSE) and the Coverage measure; (b) the relevance metrics for the set of recommendations, such as the Precision, Recall and Receiver Operating Characteristic (ROC); (c) the recommendation ranking metrics, such as the Half Life Utility (HLU) and the Discounted Cumulative Gain (DCG); and last, but not least, (d) the recommendation variety metrics: such as the diversity and the novelty of the recommended items (Hernбndez del Olmo & Gaudioso, 2008).

Traditionally, as a means of later assessing any of the quality aspects of a recommender system's performance in the context of a research study, a user dataset is divided in advance into the following two sets: a training set, which is meant for the purpose of training the machine learning model, and a test set, which is meant for the purpose of evaluating the performance of the already trained model, with the dataset's division conducted along the line of the most common optimal relation of 80 to 20 per cent respectively (Cacheda et al., 2011).

Accuracy prediction metrics are certainly the most frequently featured in the recommendation system research literature. In accordance with the presently obsolete basic supposition that a successful recommender system is the one that most accurately predicts user preferences, many of the previously published research papers had the intention of constructing algorithms that would provide more and more accurate user recommendations and of evaluating such models accordingly (Shani & Gunawardana, 2011).

The core performance metrics, which are always used to measure the accuracy of predicted ratings in the context of a user study, include the two closely related metrics of: the Root Mean Squared Error (or RMSE, for short) and its common alternative of the Mean Average Error (or MAE, for short):

recommender system travel solution

where: R - the user-item interaction matrix;

||R|| - denotes the matrix size (i.e. the number of ratings);

- the user's actual item ratings;

- the user's predicted item ratings (Yang et al., 2014).

Both of these metrics solely depend on the magnitude of prediction errors. However, the key difference when comparing the two is that, unlike the MAE metric, the RMSE one tends to be more heavily penalising the models with only a few instances of large prediction errors and instead preferring the models with a uniform level of prediction errors. In sight of this fact, it is also important to add that in the case when the test set has an unbalanced distribution of item ratings, these metrics are very likely to get skewed by the ratings prediction errors of the most frequently rated items. For this reason it is advisable to calculate RMSE and MAE for every item separately and then compute an Average RMSE and Average MAE over all items. Similarly, if, in the case of an unbalanced user distribution, the goal is to determine what level of recommendation accuracy a randomly chosen user is likely to receive, the Average RMSE and Average MAE metrics should be calculated over all users (Hernбndez del Olmo & Gaudioso, 2008).

The most common general task of a given recommender system is to provide any user with a top-k list of a certain fixed k number of item recommendations that were predicted to be the most reflective of the users' tastes. Thus, in order to measure the relevance of such a list of recommended items for every single user, other special metrics are applied instead, for instance, the most widespread ones are those of Recall and Precision. Recall (also known as sensitivity, hit rate or the true positive rate) is a metric that represents the fraction of the total amount of relevant items that were actually recommended to the user u and is obtained by dividing the number of relevant elements N (k, u) present in the top-k list by the total number of relevant items N(u) (relevance is established, for example, in the case if a rating exceeds a certain cut-off value) (Yang et al., 2014):

where: True Positives - the number of relevant items that were recommended;

False Negatives - the number of irrelevant items that were not recommended (Sokolova et al., 2006).

Precision is a metric that represents the fraction of the total amount of recommended items that were actually relevant for the user u and is calculated by the same metric of the number of relevant elements N (k, u) from the top-k list in its numerator and the total number of recommendations k of the top-k list as its denominator (Yang et al., 2014):

where: True Positives - the number of relevant items that were recommended;

False Positives - the number of relevant items that by mistake were not recommended (Sokolova et al., 2006).

In simpler terms, both of these metrics evaluate a recommender algorithm's ability to identify all of the user-relevant items that are present in the test dataset. While it is exactly true for the recall metric, the precision metric is also measuring the system's capacity to draw relevant items in relation to the system's errors of recommending useless items (Shani & Gunawardana, 2011).

For the reason of producing a more balanced evaluation of a model's performance based on the abovementioned metrics of recall and precision, a separate set of indicators called F measures has been derived in order to simultaneously track the behaviour of both of these metrics. The most extensively applied one of the F measures has been the F1 score, which assigns equal weights to both the precision and recall and can be easily computed as a harmonic mean of these two metrics:

where: Precision - the metric showing the fraction of the total number of recommended items that were actually relevant for the user;

Recall - the metric showing the fraction of the total amount of relevant items that were actually recommended to the user (Sokolova et al., 2006).

Conveniently enough, the F1 measure also represents the value of the area under the precision-recall curve, which is helpful when trying to assess the quality of algorithm's performance over a range of recommendation list lengths, in order to determine the most favourable one (Sokolova et al., 2006).

However, there exists another popular alternative of evaluating the accuracy of a recommendation list, namely, the Receiver Operating Characteristic analysis (or ROC, for short) and its respective curve, which measures the recall (known as the true positive rate) against the false alarm ratio (also known as the fall-out or the false positive rate):

where: False Positives - the number of relevant items that by error were not recommended;

True Negatives - the number of irrelevant items that were mistakenly recommended (Fawcett, 2006).

The focus of the ROC curves is to reflect the proportion of unwanted items that have still been put on the list of user recommendations. Thus, the central goal of the ROC analysis and the ROC optimisation is to return every relevant item without returning any of the irrelevant ones (Fawcett, 2006).

The choice between the two aforementioned options of the recommendation list accuracy metrics should primarily be decided upon the domain of the recommender's implementation as well as on the goals of the system's application. The general shared agreement among researchers is that in the simple case of wishing to recommend to users as much relevant items as possible the precision-recall curve should be sufficient for such a task. However, especially if the system gets implemented in a business setting, for instance in the domain of e-commerce, and holds as its core aim the maximisation of the number of new purchases and the minimisation of the marketing costs of maintaining the recommender algorithm, then the ROC curves, which are known for their widespread application in the cost/benefit decision analysis, should certainly be chosen over the precision-recall ones for their crucial ability of tracking the system's mistakes of recommending useless items (Shani & Gunawardana, 2011).

In the common instance of assessing the precision-recall or ROC curves for several test users when every user will be presented with a fixed number of k recommendations, the appropriate strategy for the recommendation set relevance evaluation is to calculate the precision and recall metrics at each number k of recommendation list lengths for each user, and then compute the average precision and recall at each number k of recommendation list lengths. The analogous approach can be taken in regard to the construction of an averaged ROC curve, every operating point of which will correspond to a different number of recommendations provided to users (Shani & Gunawardana, 2011).

As the length of the recommendation list is increased, every next recommended item tends to lose relevance to the user more quickly. For this reason, in cases when the k number of recommended items is quite large, it is advisable to introduce measures that reflect the quality of the recommendation list ranking. The two of the most frequently employed such ranking metrics are the Half Life Utility (HLU) and the Normalised Discounted Cumulative Gain (NDCG).

The Half Life metric assumes that a user's interest towards items decays at an exponential rate as he moves from the topmost item down the list of recommendations, which is to say that there is an exactly 50 per cent chance reduction for every next item of a given user actually proceeding on to that following item:

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

d - the neutrality indicator, frequently chosen to be 0;

- the 1-based rank at which the item i appears;

- the rank of the item on the recommendation list, such that there is a 50 per cent chance the user will review that item (Herlocker et al., 2004).

The Normalised Discounted Cumulative Gain, on the other hand, assumes that the relevance gain reduces logarithmically as a user moves down the list of recommendations. The main difficulty in computing NDCG, though, is the requirement to know the true user ratings for every single item on his recommendation list:

where: ,..., - the ranked list of recommended items;

- the true rating of user u for the item p that was ranked in position i;

- the maximum attainable gain value for user u which is obtained with the optimal re-order of the k items in ,...,(Baltrunas et al., 2010).

Over the years the fundamental definition of a successful, useful recommendation has gained in complexity, shifting from the core focus on accuracy to concepts like diversity, novelty and even serendipity (the degree of surprise or unexpectedness) of recommendations (Ge et al., 2010). According to the commonly accepted concept definitions, the novelty aspect of a recommendation can either reflect the degree of how generally unpopular, yet still relevant a recommendation is for a user or, in calculable terms, the degree of difference between the recommended items. However, as items with low popularity scores are quite unlikely to be familiar to the potential users, most typically the novelty of a given item is calculated as the inverse of its popularity rating, which is often simply measured as the total amount of ratings that that particular item has received. The diversity aspect of a recommendation, in its turn, can be defined as the degree of differentiation of the recommended items by their belonging to a certain item type or by differing across other characteristics. As it is impossible to state with absolute certainty the exact range of a few topics the user is most interested in at any specific time, making sure that the recommendation list is comprised of items that collectively cover a wide spectrum of the user preferences, greatly increases the system's chances of matching the user's current needs. This can be achieved by optimising the diversity of the recommendation list, which can be measured in terms of either item features or item content features, such as for instance: the general item types, subtypes, topics, etc. (Kaminskas & Bridge, 2016). The single most common metric that is frequently used to assess the degree of recommendation diversity is called the Coverage measure and can be calculated as a simple fraction in the following way:

where: k - the number representing the extent of top-k lists of user recommendations;

- the total number of distinct items in top-k places of all user recommendation lists;

- the total number of items that are available for being potentially recommended.

Thus, the fact that Coverage might end up as just a small fraction often means that only the most popular items actually end up on the user recommendation lists, which coincidentally also causes over-the-top levels of accuracy, rendering the respective metrics completely unreliable. For this reason a solid recommendation quality can only be achieved at high levels of both accuracy and coverage. Lastly, the ubiquitous use of the Coverage diversity measure, alongside the common metrics of recommendation accuracy, indicates its utmost importance in achieving a balanced performance evaluation of any given recommender system (Lu et al., 2012).

3. Statement of the research question