\section{Experimental Project}

This section presents the experimental project designed to evaluate the applicability of Maximum Coverage strategy to the ramp-up problem. First, we present the process to select first-time users in MovieLens datasets. Then, we discuss the quality requirements of RSs, emphasizing the need to get useful and diversified recommendations. We measure utility of recommendations using classical metrics, such as accuracy, precision and recall. Moreover, we adopt the framework proposed by Vargas et. al\cite{vargas2011rank} to measure diversity. Finally, we present our validation methodology, which aims to characterize and evaluate the generated recommendations by each strategy, considering the trade-off between utility and diversity.\looseness=-1

\subsection{First-time users data consolidation}

Given the relevance of these scenarios, we chose MovieLens 1M and MovieLens 10M datasets. Both collections were compiled by GroupLens and contains, respectively, 1 million and 10 millions explicit ratings assigned by users to movies from various categories. Users rated each movie in a range from 1 to 5 stars. In each data set, there are at least twenty ratings assigned by each user to her/his movies of interest. This approach results in a highly sparse data sets, as shown in Table~\ref{datasets}.\looseness=-1 %For this work, the data sets were divided into training and testing, respecting the premise of keeping the consumption of items temporarily ordered, with a distribution of 70\% for training.

	\begin{table}[ht]
		\label{datasets}
		\begin{center}
			\begin{tabular}{|c|c|c|c|} 
				\hline
				 \textbf{Datasets} & \textbf{Users} & \textbf{Items} & \textbf{Sparsity} \\ \hline
				 %\textit{MovieLens 100k} & 943 & 1676 & 93.67\% \\ \hline
				 \textit{MovieLens 1M} & 6,040 & 3,682 & 95.82\% \\ \hline
				 \textit{MovieLens 10M} & 69,878 & 10,677 & 98.66\% \\ \hline
			\end{tabular}
		\end{center}
		\caption{Datasets.}
	\end{table}

For this work, the set of first-time users was defined considering a temporal analysis of user's consume in the data set. Basically, we perform a temporal split in the data in a specific week, which was able to establish that around 15\% to 20\% of users would exist in the system after this data separation. This set of users is considered as first-time users and all information of item consumption of them were excluded to represent the ramp-up problem. Figures \ref{temporal::01}(a) e (b) show the temporal split for scenarios of ML-1M e ML-10M, respectively, considering the first user access in the system. With these data transformations, we have 1,277 and 10,633 first-time users in ML-1M e ML-10M datasets, respectively, which account for 20.25\% e 15.21\% of total users of each data set.\looseness=-1

	\begin{figure}[ht]
		\centering
		\subfigure[ML-1M]{%
			\includegraphics[scale=0.4]{figures/datasets/cutTemporalML1M.pdf}			
			}
		\quad	
		\subfigure[ML-10M]{%
			\includegraphics[scale=0.4]{figures/datasets/cutTemporalML10M.pdf}
			}
		\caption{Temporal data split of each data set.}
		\label{temporal::01}
	\end{figure}

\subsection{Baselines Selected}

Considering the effectiveness of non-personalized strategies to mitigate the Ramp-up Problem, this work has selected some state-of-the-art strategies such as \textit{baselines}. They are:\looseness=-1

\begin{enumerate}

\item \textbf{Popularity:} aims to recommend the $k$ most popular items in the domain, on the assumption that items that interest a large number of users cover the different preferences. Basically, the popularity of an $i$ item is estimated by the number of distinct users who consumed the $i$.\looseness=-1

\item \textbf{TopRated:} is the strategy to recommend the $k$ best evaluated domain items. Basically, the average grade of each item is calculated considering the total number of users and the $k$ items with the highest grades are recommended. The assumption of this approach is that the items most valued tend to interest more distinct users.\looseness=-1

\item \textbf{Recent Items:} consists of recommending the $k$ last items consumed by users in the domain. The assumption of this approach is that users tend to be interested in items that are fashionable and are currently consumed.\looseness=-1

\item \textbf{Random Popularity:} aims to recommend $k$ random items within the group of items that are rated as popular. The popular items group is defined as the items present at the head of the popularity distribution, which are a percentage of items in the domain \cite{anderson2008long}. This strategy is not used in practice, but is used to compare whether proposed strategies are effective in selecting potentially relevant items, or whether only a random selection would be sufficient.\looseness=-1

\end{enumerate}

\subsection{Quality Requirements}

The main works related to evaluation of RSs \cite{bobadilla2013recommender,de2014hybrid} describe three quality requirements: utility, novelty and diversity. The concept of {\bf utility}, which is considered the main goal of a RSs, refers to the capacity of RSs to identify and present to users items that better correspond to their preferences \cite{herlocker2004evaluating}. {\bf Novelty} refers to how distinct the recommended items are in relation to the previous items consumed by a user\cite{mcginty2003role}. Some works consider that a RSs is valuable if the system is able to offer new items or information to users \cite{sarwar2001sparsity,  kawamae2010serendipitous}. {\bf Diversity} is related to how different the recommended items are between each other \cite{vargas2011rank}. Although there exists a variety of domains where RSs are applied, the recommendations are, in general, not well diversified \cite{mcsherry2002diversity, zhou2010solving}.\looseness=-1

In this work, the RSs utility is calculated using the classical metrics of accuracy, precision and recall. Accuracy consists in simply enumerating how many ranked items were really consumed by users, considering the test data set. Precision represents the probability of an item to be relevant to a user, which can be defined by the ratio of relevant recommend items ($N_{rs}$) by the total number of recommended items ($N_s$), as specified by Equation \ref{prec}.\looseness=-1

\begin{equation}
	Precision = \frac{N_{rs}}{N_s}
\label{prec}
\end{equation}

On the other hand, recall is defined by the ratio of the number of relevant recommended items by the total number of relevant items in the test set ($N_r$). Basically, recall represents the item relevance probability to be selected, as specified by Equation \ref{rec}. In this work, we consider an item as relevant for a user if the user rating assigned to this item is greater or equal to the user's average rating.\looseness=-1

\begin{equation}
	Recall = \frac{N_{rs}}{N_r}
\label{rec}
\end{equation}
	
The $novelty$ of a information generally refers to how different this information is when compared to everything that had previously been observed by a particular user, or by a community as a whole \cite{ricci2011introduction}. For the ramp-up problem, all generated recommendations present maximum level of novelty, since all items are considered new to a user that has not consumed any items before. On the other hand, $diversity$ metric generally applies to a set of items, and relates to how different items are when compared with each other \cite{ricci2011introduction}. Basically, it is calculated as the complement of Pearson’s similarity of the
recommended items $R$, as shown by the equation \ref{div}. This metric comes from the framework proposed by \cite{vargas2011rank}. This metric represents the diversity of items based on the expected average distance from an item to an item list (ILD).\looseness=-1

\begin{equation}
\label{div}
div(R|u) = ILD = \frac{2}{|R|(|R|-1)} \sum_{i_{k} \in R, l < k} d(i_k,i_l)
\end{equation}

Finally, we propose and use a new metric in this work that aims to measure the harmonic mean between accuracy and diversity. This metric has the objective to consider the trade-off between diversity and accuracy, just to evaluate a recommender systems based on both criteria. In order to do it, we normalize the accuracy values considering its highest value according to parameter $k$. High values indicate that the recommender is able to present a useful and diverse set of items to the users. The results of this metric emphasizes the need for recommender to achieve both accuracy and diversity.\looseness=-1

\begin{equation}
	F-measure = 2 \times \frac{div(R|u) \times accuracy(u)}{div(R|u) + accuracy(u)}
	\label{newF1}
\end{equation}

\subsection{Evaluation Methodology}

Under the premise that in the real world, there are several user profiles and that RSs should be able to satisfy them, we intend to distinguish and characterize the proposed strategies, considering the trade-off between utility and diversity. Thus, our evaluation methodology consists first of distinguishing the recommendations generated in order to verify if the items recommended by Maximum Coverage differ from traditional strategies. In order to perform this analysis, we calculate the intersection between the sets generated by the top-100 recommendations, comparing all four strategies evaluated.\looseness=-1

Then, we vary the amount of items recommended by each technique, selecting 5, 10, 20, 50 and 100 first items ranked by each strategy. For each of these sets, we evaluate the recommendations based on utility, diversity and the trade-off between utility and diversity. This process is detailed as follows:\looseness=-1

\begin{itemize}[leftmargin=*]

\item \textbf{Step-1:} Evaluate the utility of each implemented strategy in order to determine whether the recommended items are potentially relevant to users. Calculate the accuracy, precision and recall of each recommender and calculate these metrics average.\looseness=-1

\item \textbf{Step-2:} Evaluate the $diversity$ for each strategy. For each obtained ranking, calculate the average value for each recommendation.\looseness=-1

\item \textbf{Step-3:} Evaluate the trade-off between utility and $diversity$ for each strategy. For each obtained ranking, calculate the \textit{F-measure} average value for each recommendation.\looseness=-1

\end{itemize}

After, we evaluate whether the proposed strategy is able to mitigate the bias of popularity, which makes the most popular items to be more recommended. This analysis allows us to say if the proposed strategy is able to merge popular and non-popular items into the recommendations, thus reaching the niche consumers. Finally, we evaluate the application of proposed strategy in possible realistic scenarios, where only 5, 10 or 20 items are recommended for each user. The objective of this analysis is to verify the gains obtained by the Maximum Coverage strategy in relation to these scenarios. In addition, we evaluated the execution time required for each strategy to generate 5, 10 and 20 items to recommend. With this analysis, we hope to consolidate the practical efficiency of each non-personalized strategy evaluated.\looseness=-1
