The Impact of Situation Clustering in Contextual-Bandit Algorithm for Context-Aware Recommender Systems

Most existing approaches in Context-Aware Recommender Systems (CRS) focus on recommending relevant items to users taking into account contextual information, such as time, location, or social aspects. However, few of them have considered the problem of user's content dynamicity. We introduce in this paper an algorithm that tackles the user's content dynamicity by modeling the CRS as a contextual bandit algorithm and by including a situation clustering algorithm to improve the precision of the CRS. Within a deliberately designed offline simulation framework, we conduct evaluations with real online event log data. The experimental results and detailed analysis reveal several important discoveries in context aware recommender system.


INTRODUCTION
A considerable amount of research has been done in recommending interesting content for mobile users. Earlier techniques in Context-Aware Recommender Systems (CRS) [3,6,13,5,23,24] are based solely on the computational behavior of the user to model his interests regarding his surrounding environment like location, time and near people (the user's situation). The main limitation of such approaches is that they do not take into account the dynamicity of the user's content.
Few works found in the literature [14,22] solve this problem by addressing it as a need for balancing exploration and exploitation studied in the "bandit algorithm" [21]. A bandit algorithm B exploits its past experience to select documents (arms) that appear more frequently. Besides, these seemingly optimal documents may in fact be suboptimal, because of the imprecision in B's knowledge. In order to avoid this undesired situation, B has to explore documents by choosing seemingly suboptimal documents so as to gather more information about them. Exploitation can decrease short-term user's satisfaction since some suboptimal documents may be chosen. However, obtaining information about the documents' average rewards (i.e., exploration) can refine B's estimate of the documents' rewards and in turn increases long-term user's satisfaction. Clearly, neither a purely exploring nor a purely exploiting algorithm works well, and a good tradeoff is needed.
The authors on [14,22] describe a smart way to balance exploration and exploitation in the field of recommender systems. However, none of them consider the user's situation during the recommendation.
In order to give CRS the capability to provide the mobile user's information matching his/her situation and adapted to the evolution of his/her content (good exr/exp tradeoff in the bandit algorithm), we propose an algorithm witch takes into account the user's situation clusters for defining the (exr/exp) tradeoff, and then selects suitable situations for either exploration or exploitation.
The rest of the paper is organized as follows. Section 2 reviews some related works. Section 3 presents the user's model of our CRS. Section 4 describes the algorithms involved in the proposed approach. The experimental evaluation is illustrated in Section 5. The last section concludes the paper and points out possible directions for future work.

RELATED WORKS
We review in the following recent relevant recommendation techniques that tackle the two issues mentioned above, namely: following the evolution of the user's contents using bandit algorithm and considering the user's situation on recommender system.

Bandit Algorithms Overview
The (exr/exp) tradeoff was firstly studied in reinforcement learning in 1980's, and later flourished in other fields of machine learning [17,20]. Very frequently used in reinforcement learning to study the (exr/exp) tradeoff, the multi-armed bandit problem was originally described by Robbins [21].
The ε-greedy is the one of the most used strategy to solve the bandit problem and was first described in [15]. The ε-greedy strategy choose a random document with epsilon-frequency (ε), and choose otherwise the document with the highest estimated mean, the estimation is based on the rewards observed thus far. ε must be in the open interval [0, 1] and its choice is left to the user.
Another variant of the ε-greedy strategy is what Cesa-Bianchi and Fisher [15] call the ε-decreasing strategy. In this strategy, the document with the highest estimated mean is always pulled except when a random document is pulled instead with an ε i frequency, where n is the index of the current round. The value of the decreasing ε i is given by ε i = {ε 0 / i} where ε 0 ∈ ]0,1]. Besides ε-decreasing, four other strategies are presented in [4]. Those strategies are not described here because the experiments done by [4] seem to show that, with carefully chosen parameters, ε-decreasing is always as good as the other strategies.
Compared to the standard multi-armed bandit problem with a fixed set of possible actions, in CRS, old documents may expire and new documents may frequently emerge. Therefore it may not be desirable to perform the exploration all at once at the beginning as in [9] or to decrease monotonically the effort on exploration as the decreasing strategy in [15].
Few research works are dedicated to study the contextual bandit problem on Recommender System, where they consider user's behavior as the context of the bandit problem.
In [10], authors extend the ε-greedy strategy by updating the exploration value ε dynamically. At each iteration, they run a sampling procedure to select a new ε from a finite set of candidates. The probabilities associated to the candidates are uniformly initialized and updated with the Exponentiated Gradient (EG) [11]. This updating rule increases the probability of a candidate ε if it leads to a user's click. Compared to both εbeginning and decreasing strategy, this technique improves the results.
In [14], authors model the recommendation as a contextual bandit problem. They propose an approach in which a learning algorithm selects sequentially documents to serve users based on contextual information about the users and the documents. To maximize the total number of user's clicks, this work proposes the LINUCB algorithm that is computationally efficient.
The authors in [4,9,14,15,22] describe a smart way to balance exploration and exploitation. However, none of them consider the user's situation during the recommendation.

Managing the User's Situation
Few research works are dedicated to manage the user's situation on recommendation. In [7,18] the authors propose a method which consists of building a dynamic user's profile based on time and user's experience. The user's preferences in the user's profile are weighted according to the situation (time, location) and the user's behavior. To model the evolution on the user's preferences according to his temporal situation in different periods, (like workday or vacations), the weighted association for the concepts in the user's profile is established for every new experience of the user. The user's activity combined with the user's profile are used together to filter and recommend relevant content.
Another work [13] describes a CRS operating on three dimensions of context that complement each other to get highly targeted. First, the CRS analyzes information such as clients' address books to estimate the level of social affinity among the users. Second, it combines social affinity with the spatiotemporal dimensions and the user's history in order to improve the quality of the recommendations.
In [3], the authors present a technique to perform user-based collaborative filtering. Each user's mobile device stores all explicit ratings made by its owner as well as ratings received from other users. Only users in spatiotemporal proximity are able to exchange ratings and they show how this provides a natural filtering based on social contexts.
Each work cited above tries to recommend interesting information to users on contextual situation; however they do not consider the evolution of the user's content.  [14,22] Context-Aware Algorithms [3,7,13,18] Clustering-ε-greedy Table 1: Recommendation algorithms comparison Table 1 compares the existing algorithms and the one we propose (Clustering-ε-greedy) w. r. t. two criteria, namely the evolution user's content and the consideration of the user's situation.
In our work we aim at taking advantage of the surveyed approaches and improve their weaknesses. As shown in Table 1, none of the mentioned works tackles both problems of the evolution user's content and user's situation consideration in the recommendation. This is precisely what we intend to do with our approach (Clustering-ε-greedy), exploiting the following new features:  Modeling the CRS as a contextual bandit algorithm by considering the user's situation when managing the (exr/exp)-tradeoff on recommendation.
 Using clustering algorithm we accelerate the context process acquisition and we improve the precision of the CRS.
The two features cited above are not considered in the surveyed approaches as far as we know.
In what follows, we define briefly the structure of the user's model and the methods for inferring the recommendation situations. Then, we explain how to manage the exploration/exploitation strategy, according to the current situation.

USER AND CONTEXT MODELS
The user's model is structured as a case base, which is composed of a set of situations with their corresponding user's preferences, denoted where S i is a user's situation (Section 3.2.1) and UP i its corresponding user's preferences (Section 3.1).

The User's Preferences
The user's preferences are contextual and might depend on many factors, like the location or the current task within an activity. Thus, they are associated to the user's situation and the user's activity. Preferences are deduced during the user's navigation activities. A navigation activity expresses the following sequence of events: (i) the user's logs in the system and navigates across documents to get the desired information; (ii) the user expresses his/her preferences about the visited documents. We assume that a visited document is relevant, and thus belongs to the user's preferences, if there are some observable user's behaviors through two types of preference: -The direct preference: the user expresses his/her interest in the document by inserting a rate, like for example putting starts ("*") at the top of the document.
-The indirect preference: it is the information that we extract from the user's system interaction, for example the number of clicks on the visited documents or the time spent on a document.
Let UP be the preferences submitted by a specific user in the system at a given situation. Each document in UP is represented as a single vector d=(c 1 ,...,c n ), where c i (i=1, .., n) is the value of a component characterizing the preferences of d. We consider the following components: the total number of clicks on d, the total time spent reading d, the number of times d was recommended, and the direct preference rate on d.

Context Model
A user's context C is a multi-ontology representation where each ontology corresponds to a context dimension C=(O Location , O Time , O Social ). Each dimension models and manages a context information type. We focus on these three dimensions since they cover all needed information. These ontologies are described in [1] and are not developed in this paper.

Situation Model
A situation is a projection on one or several user's context dimensions. In other words, we consider a situation as a triple s To build a more abstracted situation, we interpret the user's behavior from this low-level multimodal sensor data using ontologies reasoning means. For example, from S, we obtain the following situation: For simplification reasons, we adopt in the rest of the paper the following notation: The previous example situation became thus: Among the set of captured situations, some of them are characterized as high-level critical situations.

THE PROPOSED RECOMMENDATION ALGORITHM
The problem of recommending documents can be naturally modeled as a multi-armed bandit problem with context information. In our case we consider the user's situation as the context information of the multi-armed bandit. Following previous work [12], we call it a contextual bandit. Formally, our contextual-bandit algorithm proceeds in discrete trials t = 1…T. For each trial t, the algorithm performs the following tasks: Our goal is to design the bandit algorithm so that the expected total reward is maximized.
In the field of document recommendation, when a document is presented to the user and this one selects it by a click, a reward of 1 is incurred; otherwise, the reward is 0. With this definition of reward, the expected reward of a document is precisely its Click Through Rate (CTR). The CTR is the average number of clicks on a recommended document, computed dividing the total number of clicks on it by the number of times it was recommended. It is important to know here that no reward r t,d is observed for unchosen documents d ≠ d t previously displayed.

The ε-greedy Algorithm
The ε-greedy strategy is sketched in Algorithm 1. For a given user's situation, the algorithm recommends a predefined number of documents, specified by parameter N. In this algorithm, UC={d 1 ,…,d P } is the set of documents corresponding to the current user's preferences; D={d 1 ,….,d N } is the set of documents to recommend; getCTR (Alg. 1, line 6) is the function which estimates the CTR of a given document; Random (Alg. 1, lines 5 and 8) is the function returning a random element from a given set; q is a random value uniformly distributed over [0, 1] which defines the exploration/exploitation tradeoff; ε is the probability of recommending a random exploratory document.

Clustering-ε-greedy()
To adapt the ε-greedy algorithm to a context aware environment, we propose to compute the similarity between the present situation and each one in the situation base; if there is a situation that can be reused; the algorithm retrieves it, and then applies the ε-greedy algorithm. The proposed Clustering-εgreedy algorithm is described in Algorithm 6 and involves the following four methods:

RetrieveCase()
Given the current situation S t , the RetrieveCase() method determines the expected user's preferences by comparing S t with the situations in past cases in order to choose the most similar one S p . The method returns, then, the corresponding case (S p , UP p ).
6: Select UP p from UP In Eq.1, sim j is the similarity metric related to dimension j between two concepts x t and x c . This similarity depends on how closely x t and x c are related in the corresponding ontology (location, time or social). α j is the weight associated to dimension j, and it is set out by using the arithmetic mean as follows: and T the number of trials in the previous recommendation.
The similarity between two concepts of a dimension j in an ontological semantics depends on how closely they are related in the corresponding ontology (location, time or social). We use the same similarity measure as [25] defined by Eq. 4: In Eq. 2, LCS is the Least Common Subsumer of x j t and x j c , and depth is the number of nodes in the path from the node to the ontology root.

RecommendDocuments()
In order to insure a better precision of the recommender results, the recommendation takes place only if the following condition To improve the adaptation of the ε-greedy algorithm to HLCS situations, we propose to make the following verification: If the most similar S p ∈ HLCS, the system recommends documents with a greedy strategy and inserts the current situation S t on the HLCS class of situations; otherwise the system uses the ε-greedy() method described in Alg. 1. Alg. 3 summarizes the functional steps of the RecommendDocuments() method. If S p ∈ HLCS then 6.

Auto_improvement()
After recommending documents applying the Recommend-Documents method, two methods are used for improving the system:

UpdatePreferences()
Depending on the similarity between the current situation S t and its most similar situation S p (computed with RetrieveCase()), being 3 the number of dimensions in the context, two scenarios are possible: -sim(S t , S p ) ≠ 3: the current situation does not exist in the case base (Alg. 4, line 5); the InsertCase() method adds to the case base the new case composed of the current situation S t and the current user preferences UP t .
-sim(S t , S p )= 3: the situation exists in the case base (Alg. 4, line3); the UpdateCase() method updates the case having premise situation S p with the current user preferences UP t .

SituationClustering()
To accelerate the computing similarity between the current situation S t and the situations existing in the case base, we use one of the simplest and most efficient algorithms for clustering large datasets [10], the K-means algorithm, which is based on the analysis of variances. This algorithm clusters a group of situation vectors into a predefined number of clusters. It starts with random initial cluster centroids and keeps reassigning the situations in the dataset to cluster centroids based on the semantic similarity between the situations and the cluster centroid. The reassignment procedure will not stop until a fixed iteration number t max (Alg 5, line 6). We call this algorithm the Situa-tionClustering() and it is shown in Alg. 5.  S is the set of situations that belong to cluster cl i and tt is the parameter that activate the clustering algorithm if the iteration tt of Context-ε-greedy() gets the value ct; this parameter is discussed in Section 5.2.1.
The Algorithm 6 summarizes the functional steps of the four methods described above: Input: ε, N, PS, S t , UP, B, t max ,ct ,N

Finding the Optimal Exploration-Exploitation Trade-off
In order to set out the optimal trade-off value ε, we iteratively update it by the method Compute-ε() (Alg.7). First we assume that we have a finite number of candidate values for ε, denoted by Hε= (ε 1 ,..., ε T ).
Our goal is to select the optimal ε from Hε. To this end, we apply the ε-greedy algorithm for proposing an ε i , and then we use a set of weights w = (w 1 ,...,w T ) to keep track of the feedback of each ε i , w i is increased if we receive a number of clicks l i from the user when we use ε i . Receive a click feedback l i from the user 10. w i = w i+ l i ; 11. εε = εε ∪ ε i

Endfor
In Alg. 7. εε is the set of ε that have been previously selected , n is the number of iteration of the learning algorithm, i is the identifier of ε and is the probability of proposing the argmax i (w i ), this parameter starts at low value and iteratively increases until the end of the learning step.

EXPERIMENTAL EVALUATION
In order to evaluate empirically the performance of our approach, and in the absence of a standard evaluation framework, we propose an evaluation framework based on a diary set of study entries. The main objectives of the experimental evaluation are: (1) to find the optimal parameters of our algorithm and (2) to evaluate the performance of the proposed algorithm w. r. t. the ε variation and the dataset size. In the following, we describe our experimental datasets and then present and discuss the obtained results.

Evaluation Framework
We have conducted a diary study with the collaboration of the French software company Nomalys 1 . This company provides a history application, which records the time, the current location, the social and navigation information of its users during their application use. The diary study has taken 18 months and has generated 178369 diary situation entries.  Table 2: Diary situation entries Each diary situation entry represents the capture of contextual time, location and social information. For each entry, the captured data are replaced with more abstracted information using time, spatial and social ontologies. Table 3

Finding the Optimal Parameters
In order to set out the optimal parameters of the Clustering-εgreedy as the iteration of the clustering algorithm and the threshold similarity value, we use a manual classification as a baseline and compare it with the results obtained by our technique. So, we take a random sampling of 1783 situations which corresponds to 10% of the situations entries, we manually gather similar situations; then we compare the constructed groups with the results obtained by our algorithm, with different parameters of the situation clustering and the similarity methods. The results show that the precision has started to converge when t has the value 60 achieving a precision of 0.819. Consequently, we use the identified optimal iteration value (t max = 60) for testing our CRS.

Parameterizing the SituationClustering algorithm
In order to know how long our Clustering-ε-greedy can get optimal result without running the clustering method, we apply the SituationClustering at a different iteration of the Clusteringε-greedy with an interval between [0, 100]. Results in Figure 2 shows that the precision starts to decrease when Clustering-ε-greedy made a clustering after each 40 iterations ct=40 (alg. 5). Therefore, we run the clustering method (SituationClustering) with ct=40 and t max = 60.

Experimental Results
In our experiments, we have firstly collected the 3000 situations (HS) with an occurrence greater than 100 to be statistically meaningful, and the 10000 documents (HD) that have been shown on any of these situations.
The testing step consists of evaluating the existing algorithms (TestedAlgorithm in Alg.8) by giving to these last as an entry a situation S j t selected randomly from the sampling HS, where t is the identifier of the situation, j is the number of time that the situation S t has selected and j max is the number occurrence of S t in HS. The evaluation algorithm calculate and display the average CTR every 1000 iterations, The average CTR for a particular iteration is computed by the method getAVCTR (Alg. 8, line 7) and it is the ratio between the total number of clicks and the total number of displays. The number of documents (N) returned by the recommender system for each situation is 10 and we have run the simulation until the number of iterations (i) reaches 10000. The evaluation algorithm is described in Algorithm 8.

Results for ε Variation
In order to evaluate only the impact of considering the user's situation clustering in our bandit algorithm, we have compared the presented algorithm to a variant were we omitted the clustering part of the clustering-ε-greedy that we called ε-greedy. Each of the competing algorithms requires a single parameter ε. Figure 4 shows how the average CTR varies for each algorithm with the respective ε.  Figure 4 shows that, when the parameter ε is too small, there is an insufficient exploration; consequently the algorithms have failed to identify interesting documents, and have got a smaller number of clicks (average CTR).
Moreover, when the parameter is too large, the algorithms seem to over-explore and thus lose a lot of opportunities to increase the number of clicks.
We can conclude from the evaluation that considering the user's situation clustering is indeed helpful for Context-ε-greedy to find a better match between the user's interest and the evolution of his content (documents).

CONCLUSION
In this paper, we have studied the problem of exploitation and exploration in context-aware recommender systems and propose a new approach that balances adaptively exr/exp by considering the situation clustering.
We have presented an evaluation protocol based on real mobile navigation contexts obtained from a diary study conducted with collaboration with the Nomalys French company. We have evaluated our approach according to the proposed evaluation protocol and show that it is effective.
In order to evaluate the performance of the proposed algorithm, we compare it with other standard exr/exp strategies. The experimental results demonstrate the positif impact of the situation clustering in the contextual bandit algorithm. In the future, we plan to extend our situation with more context dimension, and we plan to evaluate our approach using an online framework.