
\input{tex/figure-experiments.tex}

%---------------------------------------EXPERIMENTAL RESULTS-----------------------------------------------
\vspace{-0.3cm}
\section{EXPERIMENTAL RESULTS}
\label{sec:results}

\vspace{-0.1cm}
We have  implemented just the Greedy Strategy so far. 
In this section we describe the results concerning the execution of the Greedy Strategy over real datasets and the results comparing its performance with two well known baseline algorithms in the literature. The Greedy Strategy was implemented in Java and all the experiments performed on a Windows 7 machine with 3.40 GHz clocked processor and 12 GB RAM.

%\smallskip
\vspace{-0.1cm}
%The Experiments Protocol------------------------------------------------------------------------------------------------------------------
\noindent \textbf{The Experiments Protocol.} In order to evaluate the Greedy Strategy, we adapted the sampling technique proposed by \cite{citeulike:7359992} (holdout for data stream) to the preference mining scenario. This technique  takes three parameters as input~: $n_{train}$, $n_{test}$ and $n_{eval}$. The $n_{train}$ and $n_{test}$ variables represent, respectively, the number of elements in the stream to be used to train and test the model at each evaluation. The variable $n_{eval}$ represents the number of evaluations desired along the stream. For example, let us consider the values $n_{train}$ = 5,000, $n_{test}$ = 100 and $n_{eval}$ = 36. Let $S = \{e_1, e_2, e_3, ...\}$ be a preference stream. The dynamic of evaluation for this example is as follows: (1) elements $e_1$ to $e_{5000}$ from $S$ are used to train the model; (2) elements $e_{5001}$ to $e_{5100}$ are used to test the quality of the model. The \textit{acc}, \textit{CR} and \textit{prec} of the model are calculated according to this period; %In this way we obtain a point in the  graphic of the quality of the model over time; 
(3) elements $e_{5101}$ to $e_{10100}$ are used to train the model, and so on for 36 cycles. %The preference models are produced by the Greedy Strategy at each chunk of $n_{train}$ elements arrived. %Let us call this moment of \textit{refresh point}. At each refresh point FPSMining produces its model from scratch  whereas IncFPSMining updates the model that  has been incrementally generated (at each grace period) so far.
%The time period covered by each training set of 1000 tuples is  ??? in average.
%The time interval between two refresh points is ??? in average.
%Para o usu�rio U1 e lambda de 1 dia, temos:  -Per�odo m�dio de treinamento = 3,27 dias; -Per�odo m�dio de treinamento e testes = 3,56 dias
%Para o usu�rio U1 e  lambda de 7 dias, temos:  -Per�odo m�dio de treinamento = 6,42 dias;  -Per�odo m�dio de treinamento e testes = 6,77 dias
%Ou seja, o per�odo de treinamento � praticamente igual ao per�odo total de treinamento e testes.
%In all the tests the default values for IncFPSMining are grace period = 1k and $\delta = 10^{-7}$.
%The Experiments Protocol------------------------------------------------------------------------------------------------------------------

%\smallskip
\vspace{-0.1cm}
%Real Data---------------------------------------------------------------------------------------------------------------------------------
\noindent \textbf{Real Data.}
In order to evaluate the Greedy Strategy over real-world datasets, we considered data containing preferences related to movies
collected by the GroupLens Research\footnote{\small Available at \url{http://www.grouplens.org/taxonomy/term/14}} from the
MovieLens web site\footnote{\small Available at \url{http://movielens.umn.edu}} concerning ten different users (named $U_i$, for $i=1,2,3,4,5,6,7,8,9,10$).
We simulated preference streams from these data, as follows:
we stipulated a time interval $\lambda$, and each tuple in the dataset $D_i$ of movies evaluated by the user $U_i$ was compared to all others movies of $D_i$ in a radius
$\lambda$ relative to its timestamp, thus generating temporal bituples for each user $U_i$.
We calculated the $\lambda$ (in days) for each user $U_i$ according to the sparsity related to the time of the tuples in the dataset $D_i$, and the values obtained were: $U_1=77$, $U_2=37$, $U_3=6$, $U_4=82$, $U_5=140$, $U_6=50$, $U_7=60$, $U_8=69$, $U_9=7$ and $U_{10}=135$.
%The comparison of two tuples consisted in verifying which one the user has assigned with higher score, and then to insert a temporal bituple of type (higher score tuple, lower score tuple, timestamp generated according to $\lambda$) in the preference stream.
The resulting preference stream $S_i$ has five attributes (director, genre, language, star and year), and its elements correspond to preferences on movies concerning user $U_i$. For example, the dataset $D_1$ is constituted by  movies evaluated by the user $U_1$ from 5th Aug 2001 to 3rd Jan 2009 and the period comprising the ratings given by the ten users is Aug 2000 to Jan 2009.

% ESPECIFICAR QUAL O VALOR DE LAMBDA UTILIZADO NA CONSTRUCAO DE CADA UM DOS DATASETS Di 

%\smallskip

\noindent \textbf{The Baseline Algorithms.}
We did not find any  algorithm in the literature that addresses the exact same problem we address in this article. Nevertheless, the classification task is the closest to the mining preference task among the numerous  existing data mining tasks. So, we decided to design a baseline by adapting a classifier to compare the performance of the Greedy Strategy. In this approach, the classes correspond to the scores given by the users to the movies  and can take the values: 1, 2, 3, 4 or 5 (the best score). This baseline has been designed in such a way that at each cycle of the holdout, both the training sample set and the test sample set of the classifier contain the same movies involved in  temporal bituples used by the Greedy Strategy. This ensures a fair evaluation process. 	
Besides, for a classifier to get a hit it is not necessary that it hits exactly the score given by the user to a particular movie in the test sample set. For example,  suppose that the classifier has predicted the class $c_1$ to the movie $f_1$ and the class $c_2$ to the movie $f_2$, where $f_1$ and $f_2$ are in the test sample set. In this case, if $f_1$ was better rated than $f_2$ by the user in reality, so it is enough that $c_1 > c_2$ for the classifier to get a hit. On the other hand, if $f_1$ was better rated than $f_2$ by the user in reality and $c_1 = c_2$, then the baseline infers that   the pair $(f_1, f_2)$ is incomparable.


\noindent \textbf{The Experiment Results.}
We consider a paired difference one tailed t-test  to measure the statistical significance of the differences between the accuracy (resp. the comparability rate (CR), the precision (prec)) of the Greedy Strategy and the respective measure for each of the two baseline algorithms. We adapted the  technique
described in \cite{Tan:2005:IDM:1095618} (originally designed for comparing classifiers in a batch setting)  for our preference mining task on data stream.
For each one of the three  quality measures $d$ (where $d \in \{CR, acc, prec\}$) let $\overline{d}$ be the difference between the $d$-measure of the Greedy Algorithm and the respective $d$-measure of a given baseline algorithm. The main objetive of the t-test is to compute 
the confidence interval $\gamma$ for $d$ and test if the Null Hipothesis (H0) is rejected.  The confidence interval $\gamma$ is calculated as follows: $\gamma = t_{(1-\alpha), n_{eval}-1} \times \hat{\sigma}_{d}$, where $t_{(1-\alpha), n_{eval}-1}$ is a coeficient obtained in the t-distribution table with ($1 - \alpha$) being the level of  t-test  and $n_{eval}-1$ is the degree of freedom. In all the experiments we considered $\alpha = 0.95$ and $n_{eval}$ varied according the size of the stream. We evaluated the statistical significance of $\overline{d}$ where   $d = CR$ and $d = acc$, since  these measures are evaluated on samples of equal sizes for both algorithms. 

Fig. \ref{fig:experimentalTestSet}(a) compares the performance of the Greedy Strategy with two baseline algorithms obtained by instantiating the  baseline construction methodology described earlier with two classifiers widely used in the literature: Hoeffding Tree (HT) and Naive Bayes (NB).
We used the MOA \cite{Bifet:2010:MMO:1756006.1859903} implementation of Naive Bayes and Hoeffding Tree in the default parameter setting\footnote{\small Hoeffding Tree: gracePeriod $g=200$, splitConfidence $c=10^{-7}$, tieThreshold $t=0.05$, numericEstimator $n=GAUSS10$}.
The values for the holdout parameters were $n_{train} = 5,000$ and $n_{test} = 100$. 
%The values of $n_{eval}$ varied according to the size of the stream.
For each user $U_i$, we calculated the value of $n_{eval}$ in order to cover the whole stream $S_i$, and the following values were obtained: $U_1=36$, $U_2=35$, $U_3=25$, $U_4=22$, $U_5=22$, $U_6=20$, $U_7=18$, $U_8=17$, $U_9=15$ and $U_{10}=15$.
%%% ATENCAO : DIZER EXPLICITAMENTE AQUI QUAIS FORAM OS VALORES DE n_eval utilizados para cada stream considerado. Nao se esqueca que os valores de %todos os parametros devem ser fornecidos para que o experimento possa ser replicado por um outro pesquisador que leia o artigo. Seria super %importante colocar um link onde o codigo esteja disponivel para testes - neste link a pessoa deveria se logar, fornecendo uma senha, etc, de modo
%% a ser ter um controle de quem esta fazendo testes com o nosso algoritmo.
For the Greedy Strategy we used $\alpha_1=0.2$ and $\alpha_2=0.1$ as default values for the parameters of the Alg. 1 (referring to the degree of dependence). The choice of the parameters $\alpha_1$ and $\alpha_2$ depends on the data used in the tests and in this article they were chosen through an experimental study.

For these experiments, the main question is: With $\alpha = 95$\% of certainty, can we conclude that the Greedy Strategy outperforms the other methods?
The null and alternate hypotheses for \textit{acc} and \textit{CR} are $H0: Greedy$ $Strategy \leq HT$, $NB$ and $HA: Greedy$ $Strategy > HT$, $NB$.
The results show that $H0$ is rejected (since all the values contained in the confidence interval are positive), and thus, $HA$ is substantiated.
This shows that even with limited data streams, the Greedy Strategy performs well, and outperforms both algorithms used as baselines.
%The alternative hypothesis considered is that the FPSMining outperforms the other methods, i.e., $HA_{\overline{\textit{acc}}}: \overline{\textit{acc}}_{FPS} > \overline{\textit{acc}}_{HT and NB}$ and $HA_{\overline{\textit{CR}}}: \overline{\textit{CR}}_{FPS} > \overline{\textit{CR}}_{HT and NB}$.
%The results confirm the alternative hypothesis for $\overline{\textit{acc}}$ and $\overline{\textit{CR}}$.
The poor results produced by these classifiers suggest that classifiers are not quite suitable for preference mining tasks. Thus, we argue that the Greedy Strategy, an algorithm specifically designed for preference mining, performs better than classical classifiers adapted for the preference mining task.

%Despite the real dataset we used in the experiments fits perfectly in the setting of preferences, the number of movies rated by users is still very small for the data stream scenario. In an attempt to alleviate this, we took care to consider only the users who rated more movies in this dataset. Thus, although we are not testing an ideal baseline on a large amount of data, the quality of the results obtained with the two baseline algorithms are justified by: 1) Both algorithms and the Greedy Strategy were submitted to the same data, which makes the evaluation process fair; 2) One of the requirements for an algorithm working with data streams is to be ready at any time to make predictions from any amount of training data.
%; 3) We have already shown the scalability of our algorithms on synthetic data.

\noindent \textbf{Performance Analysis.}
Fig. \ref{fig:experimentalTestSet}(b) shows the evolution of the comparability rate of the Greedy Strategy over the number of training instances processed.
In this test, we used the stream $S_1$ (concerning the user $U_1$) and we ploted all \textit{CR} values used to compute the $\overline{\textit{CR}}$ of 93\% shown in the Fig. \ref{fig:experimentalTestSet}(a). Notice that with few training instances processed the Greedy Strategy can not compare many pairs of movies due the limited information that it has received so far. With the increasing in the number of processed training instances, the Greedy Strategy can learning more about the user's preferences and therefore it is able to compare more pairs of movies. Notice also that from 40,000 training instances processed the Greedy Strategy is able to compare almost all pairs of movies which are presented to it.

\noindent \textbf{Execution Time.}
Fig. \ref{fig:experimentalTestSet}(c) shows the time measured in seconds taken by the Greedy Strategy to generate the model at each refreshing point. The same stream used in the experiment reported in Fig. \ref{fig:experimentalTestSet}(b) has been considered here. Notice that  \textit{model-refreshing time} (the time to build a new  model)  is very small, in the order of milliseconds. Though the Greedy Strategy builds the entire BPN at every holdout cycle, the sufficient statistics are updated incrementally, i.e., they are always ready to be used, which makes this process fast.
Notice also that the time remains almost constant with the increasing in the number of training instances processed, mainly due to the efficiency of the memory management used. %Thus, the results depicted in Fig. \ref{fig:experimentalTestSet}(c)  show that the Greedy Strategy is fast and meets the time constraints required in the stream setting.


%Real Data---------------------------------------------------------------------------------------------------------------------------------

%---------------------------------------EXPERIMENTAL RESULTS----------------------------------------------- 