\section{Modeling User Navigation Profiles}
\label{sub:models}

This section models user navigation profiles of the UOL video service. In Section~\ref{sub:ubmg}, we present the basic modeling strategy, applying it to build a general model of
all users in the system.  In Section~\ref{sub:groups}, we categorize users into separate groups and analyze the different user navigation profiles.

\subsection{Overall User Navigation Profile}
\label{sub:ubmg}

In order to understand the navigation profiles of users during their sessions in the system, we build a probabilistic direct graph, where the nodes represent the possible types of
user requests (e.g., search, view, etc.) and the arcs represent the navigation between one type of request to another within a single session. Also weights represent probabilities
of the navigation pattern occurring. We name this graph as UBMG
(User Behavior Model Graph). The UBMG is based on the \textit{Customer Behavior Model Graph} - CBMG~\cite{menasce2000}, a methodology to represent the user
navigation in e-commerce services. The UBMG nodes correspond to the groups of requests defined in Table~\ref{tab:tipos}. The \textit{initial} and
\textit{final} are introduced to represent the first and the last requests of the user sessions, respectively.


\begin{figure}[htb]
\centering
\includegraphics[width=1\textwidth]{fig/ubmg-geral}
\caption{Typical UBMG: Overall User Behavior}
\label{fig:ubmg}
\end{figure}



Figure~\ref{fig:ubmg} illustrates a typical UBMG, considering all user sessions in our workload. We can note that most users initiate their sessions visualizing videos (86\%),
whereas the others visit user profiles or perform searches. In constrast, only a tyny fraction of users start their sessions by browsing lists of videos or evaluating videos. After
viewing a video, most users tend to keep viewing videos or even to finish the session, although transitions to the other states may occur with non-negligible probability.
Interestingly, we find strong self loops in almost all states. For example, search is followed by another search  with a probability of 0.562. Similarly, there is a high
probability (0.545) of a user keep browsing user profiles repeatedly.  Repetition is also evident for browsing lists of videos (probability 0.475). The occurence of such high
probabilities of repeated activities of the same type, particularly browsing, may help driving the design of prefetching mechanisms. 

Next, we propose a method to categorize users into groups according to the different navigation profiles. Such differentiation is important to support the design of customized
services. 


\subsection{Groups of User Navigation Profiles}
\label{sub:groups}

So far we have examined the overall navigation patterns of users across all sessions.
Although the UBMG shown in Figure~\ref{fig:ubmg} is useful to uncover the typical navigation pattern in the system, it provides only an overall 
picture, and thus, does not show the heterogeneity among users in terms of their individual profiles. 
Next, we propose a method to categorize users into groups according to their navigation profiles. 


We start by computing  the UBMG of each individual user, considering all her sessions.  
Next, we apply a clustering algorithm~\cite{hans-clustering}, in order to identify groups with similar characteristics based on an attribute vector.  More specifically, 
we define each session as an unidimensional vector, where each position in the vector contains the probability of a user
navigating from one activity category to another. For each user we compute her individual UBMG across all her sessions 
and then we use the probabilities of the 35 possible UBMG arcs as user attributes to the clustering algorithm. 

We used X-means clustering algorithm~\cite{xmeans2000}, which extends the popular K-means~\cite{cluster} algorithm. A key advantage of X-means over K-means is that the algorithm not
only provides the clusters, but also estimates the best possible number of clusters. Therefore, we do not have to decide a priori the number of profiles. X-means algorithm
finds clusters by minimizing the sum of the squared distances between each vector and the cluster's centroid, a vector that represents the averaged properties of each group. We
consider the Euclidean distance between two vectors, which is computed by as follows: 

\begin{equation} 
D = \frac{1}{n} \sum_{i=1}^{n} (x_i + y_i)^2 
\end{equation} 
\label{eq:euclid} 

\noindent
where $n$ is the size of any vector, and $x$ and $y$ are the two vectors. 

We used the implementation of X-means available on the Weka tool~\cite{weka05} and set the maximum number of groups to 20. The X-means algorithm indicated that 15 distinct groups
was the best choice to fit our dataset.  Sessions with only one request were discarded as they do not add value to our analysis (i.e., their UBMG representations only have arcs that
include the initial or the final state).  In total, we discarded 779,384 sessions, focusing our following analysis on the remaining 348,153 sessions and of 345,152 users.

Table~\ref{tab:profiles} presents the identified groups of identified users, the number number of users, and the 
frequency of occurrence of each group. It also shows 
the predominant \textit{Initial} and \textit{Final} transitions of each group,
by presenting the state \textit{to} and \textit{from} which a user from each group typically navigates.


\begin{table}[htb!]
\begin{center}
%\small
\begin{tabular}{|c|c|c|c|c|}
\hline 
Group & \multicolumn{2}{c|}{Predominant Transition} & Number of & Frequency (\%) \\
\cline{2-3} & Initial \textit{to state} & Final \textit{from state}& Users & \\ \hline \hline
0 & 1 & 1 & 195,028 & 55.64 \\ \hline
1 & 2 & 2 e 1 & 15,102 & 4.38 \\ \hline
2 & 1 & 1 & 11,424 & 3.31 \\ \hline
3 & 3 & 1 e 3 & 1,352 & 0.39 \\ \hline
4 & 4 & 1 e 4 & 273 & 0.08 \\ \hline
5 & 5 & 1 & 13,211 & 3.83  \\ \hline
6 & 1 & 2 e 4 & 28,562 & 8.28 \\ \hline
7 & 1 & 5 & 8,427 & 2.44 \\ \hline
8 & 5 & 5 & 9,296 & 2.69  \\ \hline
9 & 5 & 2 e 1 & 803 & 0.23 \\ \hline
10 & 2 e 1 & 3 e 1 & 366 & 0.11 \\ \hline
11 & 1 & 1 & 33,137 & 9.60 \\ \hline
12 & 1 & 1 and others & 3,726 & 1.08 \\ \hline
13 & 1 e 5 & 1 e 5 & 6,722 & 1.95  \\ \hline
14 & 1 e 2 & 1 & 20,723 & 6.00 \\ \hline \hline
\multicolumn{3}{|r|}{Total} & 345,152 & 100.00 \\ \hline
\end{tabular}
\caption{User Navigation Profile - Groups}
\label{tab:profiles}
\end{center}
\end{table}


%\if 0
\begin{figure*}[htb!]
\begin{center}
\begin{tabular}{ccc}
\subfigure[Group 0]{\includegraphics[width=0.315\textwidth]{fig/ubmg-grupo0}
\label{fig:ubmg0}}&
\subfigure[Group 1]{\includegraphics[width=0.315\textwidth]{fig/ubmg-grupo1}
\label{fig:ubmg1}}&
\subfigure[Group 2]{\includegraphics[width=0.315\textwidth]{fig/ubmg-grupo2}
\label{fig:ubmg2}}\\
\subfigure[Group 3]{\includegraphics[width=0.315\textwidth]{fig/ubmg-grupo3}
\label{fig:ubmg3}}&
\subfigure[Group 4]{\includegraphics[width=0.315\textwidth]{fig/ubmg-grupo4}
\label{fig:ubmg4}}&
\subfigure[Group 5]{\includegraphics[width=0.315\textwidth]{fig/ubmg-grupo5}
\label{fig:ubmg5}}\\
\subfigure[Group 6]{\includegraphics[width=0.315\textwidth]{fig/ubmg-grupo6}
\label{fig:ubmg6}}&
\subfigure[Group 7]{\includegraphics[width=0.315\textwidth]{fig/ubmg-grupo7}
\label{fig:ubmg7}}&
\subfigure[Group 8]{\includegraphics[width=0.315\textwidth]{fig/ubmg-grupo8}
\label{fig:ubmg8}}\\
\subfigure[Group 9]{\includegraphics[width=0.315\textwidth]{fig/ubmg-grupo9}
\label{fig:ubmg9}}&
\subfigure[Group 10]{\includegraphics[width=0.315\textwidth]{fig/ubmg-grupo10}
\label{fig:ubmg10}}&
\subfigure[Group 11]{\includegraphics[width=0.315\textwidth]{fig/ubmg-grupo11}
\label{fig:ubmg11}}\\
\subfigure[Group 12]{\includegraphics[width=0.315\textwidth]{fig/ubmg-grupo12}
\label{fig:ubmg12}}&
\subfigure[Group 13]{\includegraphics[width=0.315\textwidth]{fig/ubmg-grupo13}
\label{fig:ubmg13}}&
\subfigure[Group 14]{\includegraphics[width=0.315\textwidth]{fig/ubmg-grupo14}
\label{fig:ubmg14}}
\end{tabular}
\end{center}
\caption{User Behavior Model Graphs for Different User Profiles}
\label{fig:grafos}
\end{figure*}
%\fi

%\begin{figure*}[tbh]
%\begin{center}
%\begin{tabular}{ccc}
%\subfigure[Group 0]{\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo0.eps}\label{fig:ubmg0}}&
%\subfigure[Group 11]{\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo11.eps}\label{fig:ubmg11}}&
%\subfigure[Group 6]{\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo6.eps}\label{fig:ubmg6}}\\
%\subfigure[Group 2]{\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo2.eps}\label{fig:ubmg2}}&
%\subfigure[Group 7]{\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo7.eps}\label{fig:ubmg7}}&
%\subfigure[Group 12]{\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo12.eps}\label{fig:ubmg12}}\\
%\hspace{2cm}
%\subfigure[Group 13]{\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo13.eps}\label{fig:ubmg13}}&
%&\hspace{-2cm}
%\subfigure[Group 14]{\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo14.eps}\label{fig:ubmg14}}
%\end{tabular}
%\end{center}
%\caption{UBMG of Viewers}
%\label{fig:view}
%\end{figure*}



We now turn our attention to the UBMGs of all 15 groups, which are shown in Figure~\ref{fig:grafos}. 
We start by discussing the profiles of users who predominantly view videos, here referred to as \textit{Viewers}. These profiles correspond to groups
0, 2, 6, 7, 11, 12, 13, and 14. We note that we omit arcs with probabilities lower than 0.03 for the sake of clarity. We also choose to exclude states having only arcs with low
probabilities. 

Figure~\ref{fig:ubmg0} presents the graph of the navigation profile of group 0, the most frequent one accounting for 55.64\% of the users. These
users usually initiate their sessions watching a video. Then 58.5\% of them watch other videos, whereas the rest leave the system. Note that, groups 0 and 11,
represented on Figure~\ref{fig:ubmg11}, are very similar.  The difference is that users of group 11 have a small chance of performing other activities 
(not represented), such as viewing a user profile, evaluating content, and listing videos.  Jointly, these two groups represent more than 65\% of the users.

Figure~\ref{fig:ubmg6} shows the typical user navigation profile of group 6. Similarly to users from group 0 and 11, these users also initiate their sessions watching a video.
However, most of them visit a user profile or evaluate content afterwards. Groups 2 and 7 (Figures~\ref{fig:ubmg2} and ~\ref{fig:ubmg7}, respectively) are also somewhat similar to
groups 0 and 11, whereas group 2 users typically watch videos after searching (probability of 0.981), group 7 users leave the system after the search. One key difference is that
after watching at least one video these users may also search for a new video. 


The last three groups of \textit{Viewers} are the groups 12, 13, and 14, depicted in Figures~\ref{fig:ubmg12},~\ref{fig:ubmg13}, and~\ref{fig:ubmg14}, respectively. After viewing
a video, group 12 users typically access lists of videos and then view another video or access a user profile, with a high chance (almost
49\%) of viewing a video again. Some users from group 13 start their sessions by performing searches (probability of 0.103), whereas a large fraction of users from group 14 start their
sessions by browsing a user profile (probability of 0.436) and then, watching videos with probability 0.98.


Next, we analyze profiles of users who start their sessions predominantly by searching for content. These users, referred to as \textit{Searchers},
correspond to groups 5, 8 and 9.  Figure~\ref{fig:ubmg5} illustrates the typical profile of group 5. These
users start their sessions searching (probability of 0.976) before watching videos with probability 0.95. Similarly, users from group 8 and 9 also start their
sessions by searching (probabilities of 0.99 and 0.91, respectively). However, instead of watching videos after searching like most users from
group 5, users from group 8 typically keep searching repeatedly, with probability 0.47 and leave the system with probability 0.41. After performing a search group 9 
users have a high probability (0.75) to browse a user profile.

Groups 1 and 10, illustrated in Figures~\ref{fig:ubmg1} and~\ref{fig:ubmg10}, correspond to users who start their sessions by browsing profiles.
Indeed, Users from these groups show very similar profiles with the difference that group 1 users have also some chance (probability of 0.53) of accessing lists of videos
maintained by the system. 

Only a small fraction (less than 1\%) of the users start their sessions by listing videos. These users are represented by group 3 (Figure~\ref{fig:ubmg3}). Basically,
they start their sessions listing videos and then they watch videos with probability 0.43 or continue to navigate on the lists of videos. 

Lastly, group 4 (Figure~\ref{fig:ubmg4}) exhibits a suspicious profile: some users begin their sessions by \textit{evaluating} videos. This  behavior suggests some kind of
malicious or opportunistic action, as we would expect that an evaluation should appear only after the user watches at least one video. 


%\begin{figure*}[htb!]
%\begin{center}
%\begin{tabular}{ccc}
%\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo0}\label{fig:ubmg0}&
%\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo1}\label{fig:ubmg1}&
%\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo2}\label{fig:ubmg2}\\
%\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo3}\label{fig:ubmg3}&
%\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo4}\label{fig:ubmg4}&
%\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo5}\label{fig:ubmg5}\\
%\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo6}\label{fig:ubmg6}&
%\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo7}\label{fig:ubmg7}&
%\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo8}\label{fig:ubmg8}\\
%\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo9}\label{fig:ubmg9}&
%\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo10}\label{fig:ubmg10}&
%\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo11}\label{fig:ubmg11}\\
%\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo12}\label{fig:ubmg12}&
%\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo13}\label{fig:ubmg13}&
%\includegraphics[width=0.3\textwidth]{fig/ubmg-grupo14}\label{fig:ubmg14}
%\end{tabular}
%\end{center}
%\caption{User Behavior Model Graphs for Different User Profiles}
%\label{fig:grafos}
%\end{figure*}










