\section{Experimental Analysis}

In this section, we discuss the main results of applying the proposed evaluation methodology to first-time users selected in MovieLens 1M and 10M datasets. Initially, we performed a comparison and analysis of the different recommendation strategies, considering the set of items recommended. For this, we propose to evaluate the intersection of the items recommended by each strategy using a Venn diagram. Next, we evaluate the utility and diversity of each strategy to evaluate the performance of our Maximum Coverage strategy. Our objective is to evaluate the quality of the recommendations of each of the strategies considering the quality dimensions. Finally, we perform specific analyses of the strategies, considering a real scenario in which a maximum of twenty items are recommended. In this step, we specifically evaluated the recommendation of up to twenty items, such as a real e-commerce system such as \textit{Amazon} or \textit{Netflix}, which has a maximum of 20 items at a time for users.\looseness=-1

\subsection{Similarity Analysis}

First, we analyze the intersection of the recommendation lists of each strategy, as shown in the Venn diagrams of Figure \ref{result::01} for each scenario. We can note that only 6\% and 4\%, for ML-1M and ML-10M, respectively, of the recommended items are present in all recommendation lists. This low intersection value is justified when we observe that 84\% and 89\%, for the respective datasets, of the recommended items are unique to the Recent Items strategy. In fact, when we look at the intersection between Popularity, Best Rated and Maximum Coverage, we note that 47\% and 34\% of items for ML-1M and ML-10M are recommended by all of them. We can also note that there is an intersection of 33\% and 51\% of the items for Popularity and Best Rated strategies. Finally, it is important to highlight that the Maximum Coverage strategy presents 36\% and 54\% of distinct items from the baselines.\looseness=-1

	\begin{figure}[ht!]
		\centering
		\subfigure[ML-1M]{%
			\includegraphics[scale=0.35]{figures/compare/venn/vennML1M.png}			
			}
		\quad
		\subfigure[ML-10M]{%
			\includegraphics[scale=0.35]{figures/compare/venn/vennML10M.png}
			}
		\caption{Venn diagrams to represent the intersection rate of the recommendation lists issued by distinct non-personalized RSs, considering the $k=100$.}	
		\label{result::01}
	\end{figure} 
	
Briefly, these results show that: (1) the Popularity strategy has similarities to strategy to recommend Best Rated items, which can be confirmed by the high intersection value between them; (2) the Recent Items strategy presents items totally different from those recommended by other strategies; (3) the Maximum Coverage strategy is able to present popular items due to its intersection with Popularity strategy and also Best Rated items. Moreover, it has a good diversity, since it presents a significant amount of distinct items provided only by itself. This fact indicates that the Maximum Coverage may introduce novelty and diversity to recommendations.\looseness=-1
	
\subsection{Utility vs. Diversity}

Considering the utility related to the evaluated RSs, Figure \ref{result::02}(a) and \ref{result::02}(b) presents the mean accuracy of each RSs, considering distinct top-\textit{k} lists. As expected, Popularity presents the highest accuracy, since popular items occur in a larger number of distinct user lists. Given the high level of intersection between Popularity and Best Rated items, we also observe high accuracy rates related to the latter strategy. Despite recommending items different from those issued by the Popularity strategy, Maximum Coverage exhibits accuracy rates comparable to the latter, mainly for smaller ranking $k$ lists. Evaluating the F1 metric, which performs a harmonic mean of the precision and recall values, we can note that the good performance of the recommendation metrics based on Popularity and Best Rated items. These strategies, as shown in Figure \ref{result::02} (c) and (d), are able to return relevant items to users, since the studied scenarios are related to mass consumption. On the other hand, it may be noted that the Recent Items and Random Popularity strategies do not have relevant items for users.\looseness=-1
\vspace{-0.5cm}
	\begin{figure}[ht!]
		\centering		
		\subfigure[Accuracy ML-1M]{%
			\includegraphics[scale=0.3]{figures/compare/accuracy/accuracyML1M.eps}			
			}
		\quad \hspace{-0.7cm}
		\subfigure[Accuracy ML-10M]{%
			\includegraphics[scale=0.3]{figures/compare/accuracy/accuracyML10M.eps}
			}
		\quad \hspace{-0.7cm}
		\subfigure[F1 to ML-1M]{%
			\includegraphics[scale=0.3]{figures/compare/F1/F1metricML1M.eps}			
			}
		\quad \hspace{-0.7cm}
		\subfigure[F1 to ML-10M]{%
			\includegraphics[scale=0.3]{figures/compare/F1/F1metricML10M.eps}
			}
		\caption{Results related to metrics Accuracy and F1 achieved by each strategy regarding to the items recommended for the first-time users. In fact, Popularity and Best Rated items strategies present the highest accuracy and F1 for both datasets, since the consumption of these users has a bias for the mass consumption.}
		\label{result::02}
	\end{figure}

Next, we evaluate the diversity metric for non-personalized strategies. Figures \ref{result::03}(a) and \ref{result::03}(b) show the average values obtained for this metric, providing a global analysis compared to all list of recommended items. We can observe that the Random Popularity and Recent Items strategy present more diverse items than the other ones. However, these results, when evaluated in conjunction with the usefulness of the items. The Maximum Coverage strategy brings more diverse items than the other strategies. This result is related to the approaches used by each strategies that aim to select random (Random Popularity) or even items that interest to different users (Maximum k-Coverage).\looseness=-1

\begin{figure}[ht!]
	\centering
	\subfigure[Diversity - ML-1M]{%
		\includegraphics[scale=0.35]{figures/compare/diversity/diversityML1M.eps}			
	}
	\quad
	\subfigure[Diversity - ML-10M]{%
		\includegraphics[scale=0.35]{figures/compare/diversity/diversityML10M.eps}
	}
	\caption{Average of Diversity values related to each non-personalized strategy. Recent Items strategy presents the highest values of diversity related to its items recommended, followed by Maximum Coverage strategy. As expected, the Popularity and Best Rated do not present high values of diversity.}
	\label{result::03}
\end{figure}
	
The desirable trade-off between accuracy and diversity by a recommender system can be calculated through the F-measure metric, which performs a harmonic mean of diversity and accuracy, as shown in Figure \ref{result::10}(a) and \ref{result::10}(b). Table \ref{tab::02} compare trough Area Under Curve (AUC) of the generated F-measure rankings. This trade-off shows that the strategy of recommending the Recent Items is not useful to end users, making the recommendation inefficient. The Popularity and Best Rated strategies, which present high accuracy, are not able to diversify the set of presented items, not satisfying users of niche consumers. On the other hand, the Maximum Coverage strategy is statistically better than the baselines, with a p-value of less than 0.001 using the Wilcoxon test for non-normal distributions. In general, the Maximum Coverage strategy presents an average gain of 13.5\% in relation to the strategy of recommending the Best Rated items, which is the strongest baseline in these analyses. These results show that, even though it is not a strategy widely used in the literature, this Maximum Coverage strategy presents potentially relevant results for non-personalized recommendations and may be applicable in real and practical scenarios.\looseness=-1

	\begin{figure}[ht!]
		\centering
		\subfigure[F-measure - ML-1M]{%
			\includegraphics[scale=0.35]{figures/compare/newF1/newF1ML1M.eps}			
			}
		\quad
		\subfigure[F-measure - ML-10M]{%
			\includegraphics[scale=0.35]{figures/compare/newF1/newF1ML10M.eps}
			}
		\caption{F-measure on accuracy and diversity for non-personalized RSs. These results indicate that the Maximum Coverage strategy is superior the traditional ones.}
		\label{result::10}	
	\end{figure}	
	
	\begin{table}[ht]
		\begin{small}
		\begin{center}
			\begin{tabular}{|c|c|c|c|c|c|rc|} 
				\cline{2-8} 
				\multicolumn{1}{ c|  }{} & \textbf{k-value} & \textbf{Popularity} & \textbf{TopRated} & \textbf{Recent Items} & \textbf{MaxCoverage} & \multicolumn{2}{c|}{\textbf{Statics Gain}} \\ 
				\cline{2-8} \hline
				
			\parbox[t]{2mm}{\multirow{5}{*}{\rotatebox[origin=c]{90}{\centering\textbf{ML-1M}}}} 				 		 
				 & \textit{k = 5} & 0.1708 & 0.1821 & 0.0243 & 0.2543 & 8\% &  \textcolor[rgb]{00,0.45,0.10}{$\blacktriangle$} \\ \cline{2-8}
				 & \textit{k = 10} & 0.2034 & 0.2110 & 0.0511 & 0.2697 & 9.25\% &  \textcolor[rgb]{00,0.45,0.10}{$\blacktriangle$} \\ \cline{2-8}
				 & \textit{k = 20} & 0.2255 & 0.2270 & 0.0997 & 0.2693 & 10\% &  \textcolor[rgb]{0.7,0.7,0.0}{$\bullet$} \\ \cline{2-8}
				 & \textit{k = 50} & 0.2316 & 0.2409 & 0.1627 & 0.2574 & 9\% &  \textcolor[rgb]{0.7,0.7,0.0}{$\bullet$} \\ \cline{2-8}
				 & \textit{k = 100} & 0.2257 & 0.2343 & 0.1186 & 0.2375 & 4\% &  \textcolor[rgb]{0.7,0.7,0.0}{$\bullet$} \\ \hline \hline

			\parbox[t]{2mm}{\multirow{5}{*}{\rotatebox[origin=c]{90}{\centering\textbf{ML-10M}}}} 				 
				 & \textit{k = 5} & 0.2089 & 0.2161 & 0.0582 & 0.2335 & 39.7\% &  \textcolor[rgb]{00,0.45,0.10}{$\blacktriangle$} \\ \cline{2-8}
				 & \textit{k = 10} & 0.2302 & 0.2329 & 0.0714 & 0.2544 & 27.8\% &  \textcolor[rgb]{00,0.45,0.10}{$\blacktriangle$} \\ \cline{2-8}
				 & \textit{k = 20} & 0.2476 & 0.2461 & 0.1478 & 0.2709 & 18.6\% &  \textcolor[rgb]{00,0.45,0.10}{$\blacktriangle$} \\ \cline{2-8}
				 & \textit{k = 50} & 0.2533 & 0.2494 & 0.1756 & 0.2718 & 6.8\% &  \textcolor[rgb]{00,0.45,0.10}{$\blacktriangle$} \\ \cline{2-8}
				 & \textit{k = 100} & 0.2447 & 0.2439 & 0.1435 & 0.2537 & 1.35\% &  \textcolor[rgb]{00,0.45,0.10}{$\blacktriangle$} \\ \hline

			\end{tabular}
		\caption{AUC related to the rankings achieve by the metric F-measure based on all $k$ items recommended. The symbol \textcolor[rgb]{00,0.45,0.10}{$\blacktriangle$} denotes significant positive gains, \textcolor[rgb]{0.7,0.7,0.0}{$\bullet$} non significant gains and \textcolor[rgb]{0.7,00,00}{$\blacktriangledown$} significant negative losses from the F-measure distribution. In fact, Maximum Coverage strategy presents the best rankings providing better utility and diversity between the items recommended.}				
		\label{tab::02}
		\end{center}	
		\end{small}	
	\end{table}
	
\subsection{Application on Real Scenarios}

In a real scenario of recommendation, such as \textit{Amazon} or \textit{Netflix}, the RSs are interested in presenting a list or ranking of 5, 10 or 20 items of potential interest of a set of users or consumers. Therefore, we present in Figure \ref{results::04} the results of our proposed recommendation strategy for top-5, top-10 and top-20 rankings. From these analyses, it is possible to note that Maximum Coverage strategy presents a similar utility performance when compared to Popularity and Best Rated strategies (see Figures \ref{results::04}(a), \ref{results::04}(b), \ref{results::04}(e), and \ref{results::04}(f)), showing a better accuracy than these baselines in ML-10M (Figure \ref{results::04}(e)) for top-5 and top-10. In terms of diversity of items, we can observe that there is a diversity of items, even on a small list of 5-20 items, as can be confirmed by Figures \ref{results::04}(c) and \ref{results::04}(g). Moreover, based on the F-measure on accuracy and diversity (see Figures \ref{results::04}(d) and \ref{results::04}(h)), we can see a high level of diversity and a significant accuracy, providing a performance that overcomes the other strategies. These superior results are also demonstrated by the AUC of F-measure metric for accuracy and diversity. Observing the Table \ref{tab::02}, the first three columns of each dataset, it is possible to note high levels of gains. For recommendations of 5, 10 or 20 items, our strategy presents gains of  8\%, 9.25\% e 10\% for ML-1M, and 39.7\%, 27.8\% and 18.6\% for ML-10M.\looseness=-1
	
	\begin{figure}[ht!]
		\centering
		\subfigure[]{%
			\includegraphics[scale=0.48]{figures/compare/top20/accuracyML1M.eps}			
			}
		\quad
		\subfigure[]{%
			\includegraphics[scale=0.48]{figures/compare/top20/F1metricML1M.eps}			
			}
		\quad
		\subfigure[]{%
			\includegraphics[scale=0.48]{figures/compare/top20/diversityML1M.eps}			
			}
		\quad
		\subfigure[]{%
			\includegraphics[scale=0.48]{figures/compare/top20/newF1ML1M.eps}			
			}
			
		\subfigure[]{%
			\includegraphics[scale=0.48]{figures/compare/top20/accuracyML10M.eps}			
			}
		\quad
		\subfigure[]{%
			\includegraphics[scale=0.48]{figures/compare/top20/F1metricML10M.eps}			
			}
		\quad
		\subfigure[]{%
			\includegraphics[scale=0.48]{figures/compare/top20/diversityML10M.eps}			
			}
		\quad
		\subfigure[]{%
			\includegraphics[scale=0.48]{figures/compare/top20/newF1ML10M.eps}			
			}	
		\caption{Results of performance metrics for ML-1M and ML-10M data sets, considering the classical recommendation task for real applications, which recommends only 5, 10 or 20 items. We can verify a good performance for Maximum Coverage strategy compared to the other strategies or baselines, with a good level of accuracy and better diversity level.}		
		\label{results::04}		
	\end{figure}

Despite the cubic complexity of the greedy algorithm used, the execution time required to recommend these items is scalable to the real scenarios applied. Table \ref{tab::03} shows the execution time of the algorithms used, in seconds, showing that Maximum Coverage is feasible in practice. Thus, all these results demonstrate the Maximum Coverage is a complementary option to be adopted behind the traditional methods, being effective in real scenarios.\looseness=-1

	\begin{table}[ht]
		\begin{small}
		\begin{center}
			\begin{tabular}{|c|c|c|c|c|c|} 
				\cline{2-6} 
				\multicolumn{1}{ c|  }{} & \textbf{k-value} & \textbf{Popularity} & \textbf{TopRated} & \textbf{Recent Items} & \textbf{MaxCoverage} \\ 
				\cline{2-6} \hline
				
			\parbox[t]{2mm}{\multirow{3}{*}{\rotatebox[origin=c]{90}{\centering\textbf{\tiny ML-1M}}}} 				 		 
				 & \textit{k = 5} & 0.0296 & 0.1542 & 0.1565 & 1.8573 \\ \cline{2-6}
				 & \textit{k = 10} & 0.0302 & 0.1529 & 0.1576 & 2.3515 \\ \cline{2-6}
				 & \textit{k = 20} & 0.0314 & 0.1581 & 0.1618 & 3.2807 \\ \hline \hline

			\parbox[t]{2mm}{\multirow{3}{*}{\rotatebox[origin=c]{90}{\centering\textbf{\tiny ML-10M}}}} 				 
				 & \textit{k = 5} & 0.4791 & 2.1652 & 1.8166 & 114.5131 \\ \cline{2-6}
				 & \textit{k = 10} & 0.4795 & 2.1397 & 1.8047 & 133.8829 \\ \cline{2-6}
				 & \textit{k = 20} & 0.4911 & 2.1604 & 1.8162 & 157.8802 \\ \hline

			\end{tabular}
		\caption{Runtime of the algorithms used (in seconds).}
		\label{tab::03}
		\end{center}	
		\end{small}	
	\end{table}

\subsection{Recommending non-Popular Items}

The impact of applying the Maximum Coverage strategy is evident in scenarios whose user consumption is strongly biased towards popularity (i.e., mass consumption). By relating the popularity of items and users' consumption history in the studied collections, as shown in Figures \ref{results::05} (a) and \ref{results::05} (b), we observe an effect similar to the so-called long-tail distribution \footnote{A power distribution on the consumption of users who tend to consume a few popular items.} caused by mass consumption. In this context, mass consumption-related recommendations do not represent a good strategy for acquiring niche consumers, as these RSs would be trapped to recommend items from the \textit{head} of this distribution (i.e., widely consumed items).\looseness=-1

	\begin{figure}[ht]
		\centering
		\includegraphics[scale=0.4]{figures/datasets/itemsPopularity.pdf}
		\caption{Popularity items distribution in ML-1M and ML-10M datasets. The vertical lines represent the division between head and tail preformed in elbow point, for each evaluated scenario.}			\label{results::05}			
	\end{figure}
	
When assessing whether items recommended by Maximum Coverage belong to the \textit{head} or \textit{tail} of the popularity distribution, we note that such a strategy is indeed valid for niche consumers. By calculating the second derivative of the popularity distribution (i.e., the elbow point), we found that 14\% and 12\% of the recommended items appear in the distribution tail for ML-1M and ML-10M, respectively. Hence, recommendations generated by Maximum coverage tend to mitigate the problem of long-tail, bringing benefits to various real applications and easing the task of satisfying the niche consumers.\looseness=-1

In fact, analyzing how many distinct users each strategy is able to satisfy minimally (i.e. accuracy superior or equal to 1), we can note that Maximum Coverage strategy achieves 97\% of the users for dataset ML-10M. In turn, the remaining traditional strategies have achieved just 94\% of the users in the same dataset. Despite it corresponds a small percentage difference (i.e. 3\%), it represents 318 users, which is a considerable number. This result corroborates to our hypothesis that recommendations merging popular and non-popular items, which focus on different user preferences, are effective and applicable in practice.\looseness=-1
