This paper describes an agent-based approach for making context and intention-aware recommendations of Points of Interest (POI). A two-parted agent architecture was used, with an agent responsible for gathering POIs from a location-based mobile application, and a set of Personal Assistant Agents (PAA), collecting information about the context and intentions of its respective user. Each PAA includes a probabilistic classi er for making recommendations given its information about the user's context and intentions. Supervised, incremental learning occurs when the feedback of the true relevance of each recommendation is given by the user to his PAA. To evaluate the system's recommendations, we performed an experiment based on the pro le used in the training process, using di erent locations, contexts and goals.
With the technological advance registered in the last
decades, there has been an exponential growth of
the information available. In order to cope with
this superabundance, Recommender Systems (RS) are a
promising technique to be used in location-based systems
(see [
CARS-2012, September 9, 2012, Dublin, Ireland.
Copyright is held by the author/owner(s).
relevant information for the user may not only depend on
his preferences, but also in his context. In addition, the
very same content can be relevant to a user in a particular
context, and completely irrelevant in a di erent one. For
this reason, we believe that it is important to have the user's
context in consideration during the recommendation process
[
In this paper, we intend to analyse the advantages of using a Multiagent System (MAS) capable of ltering irrelevant information, while taking into account the user's context. Our system uses standard POI attributes, and also integrates dynamic context data like user's context and goal, in order to process the requests. The system is able to understand the di erences between each user, since each one of them has unique preferences, intentions and behaviours, resulting in di erent recommendations for di erent users, even if their context is the same.
The remaining of the paper starts with a presentation of the system's architecture (section 2). In section 3, we present the experimentation performed. Finally, section 4 presents our conclusions. 2.
In this section, we present the system's architecture and all its components (see gure 1).
This architecture can be seen as a middleware between the user's needs and the information available in our system. More speci cally, the Master Agent is responsible for starting, not only the agents (described in gure 1 as Agent 1 Agent n) that gather data from the Web resources (i.e., location-based mobile applications), but also the user's Personal Assistant Agent (PAA). Moreover, it is capable of aggregating the POIs returned from the Web agents into a well-de ned knowledge representation.
The main purpose of each Web agent is to obtain all the POIs' information available in pre-de ned Web sources. These autonomous agents are constantly searching for new information, and verifying if the data stored in the database (presented in gure 1 as POIs Database) is up-to-date.
As we can see in gure 1, each user has a PAA assigned to him. This agent expects a request from the user, and, based on his context, recommends a list of nearby POIs (see section 3). The PAA learns from the user's past experiences, in order to improve its recommendations. Speci cally, a PAA_1 User_1
Master Agent ... ...
PAA_n
User_n memory memory
POIs' resources
...
Agent_1
Agent_n POIs aggregation module
POIs Database probabilistic classi er is used for that purpose, i.e., the PAA assigns a probability value to the relevance of the POI, given its information, the current user's context and intentions. Therefore, when the feedback of the true relevance of each recommendation is given by the user to his PAA, the PAA updates its memory. As a result, the agent learns every time the user decides to make a request and give his feedback. 3.
Our main goal is to show that we can face the problem of location-based context-aware recommendations with a MAS architecture. In addition, we intend to verify how machine learning algorithms suit the task of predicting the user's preferences, based on his context. An e ectiveness evaluation of our RS, in terms of the accuracy of its predictions, will be performed. This section presents the experimentation, in a controlled simulation, carried out to study the system's performance while recommending POIs. Firstly, the experiment set-up is presented (see 3.1), followed by an exhaustive analysis of the results (see 3.2). 3.1
Our MAS contains agents responsible for obtaining POIs from Web sources. The purpose of these agents is to keep the information up-to-date in the database (see 3.1.1). On the other side, the system has PAAs, that use memory to save the user's experiences (see 3.1.2). In this experiment, only one information source was used (see 3.1.1) and only one user's pro le (see 3.1.3). The experimentation was performed in a speci c area of the city of Coimbra (Portugal), explained in detail in 3.1.5. Di erent scenarios were used to specify both the user's and POIs' contexts (see 3.1.4). To evaluate the system, some well-known metrics are presented in 3.1.6. 3.1.1
As previously mentioned, our system could receive input from various location-based applications. In this experiment in particular, it is used one of the existing POIs' sources available on the Web, which explains why we used only one agent to obtain POI information.
Agent Gowalla obtains all the information through calls to Gowalla's API. It starts by requesting for POIs in a prede ned area (see 3.1.4). During this process, it lters all the POIs that do not belong to the categories we will use (see 3.1.4). This process is repeated every 30 seconds, to allow the agent to detect new POIs whenever they are created, or to discover changes in an existing POI.
Due to the fact that Gowalla's database does not have all the information needed for the experiment, we decided to gather more information about the POIs on the eld. This allowed us to have more details about each POI in order to ful l the requirements of the experiment (see 3.1.5 for more details). After ltering the unused categories (irrelevant to this experiment), this extra information was combined with Gowalla's info in the aggregation module, being then saved to the database (see section 3.1.5). 3.1.2
The recommendation process resorts to WEKA's API1. In order to predict if a POI would be useful for the user and if its recommendation is worthy, it was used a probabilistic classi er that was trained with the Naive Bayes Updateable algorithm. The predicted values vary from 1 (totally irrelevant) to 5 (most relevant), and the algorithm automatically distributes the probability ranges in this scale. POIs with a classi cation of at least 3, are recommended to the user.
When an agent recommends POIs to its user, the agent expects the user to rate each recommendation, and saves this information into its memory, which allows it to learn from the experience. The agent's memory is a set of instances, which we call dataset. In table 1, we can see an example of a dataset. The rst ve columns correspond to the information related to the POI: ID, category, price, schedule (morning, afternoon and night) and day o . The distance eld corresponds to the distance between the POI and the user (near, average or far). The following three columns correspond to the user's context information: time of day, day of the week and his current goal (co ee, lunch, dinner or party). The last column (Label), corresponds to the algorithm's prediction. 3.1.3
As explained in section 2, each user has his own PAA (i.e., a dataset with his own preferences). We performed a simulation period in order to train the PAAs' classi ers. Since we had various PAAs' classi ers (each one with di erent user's pro les), it was impossible to evaluate all of them and we had to choose only one pro le. This pro le can be seen as a stereotype of a user who prefers POIs that are near, cheaper and not closed. For the sake of clarity, the feedback given by the user only considers the POIs' categories and not their names. 3.1.4
Scenario is de ned as the set of information related to the user which a PAA needs to classify a POI, in a certain context. More precisely, a scenario results from the combination of the user's context with the POI's context. We have de ned the user's context by: i) proximity related to a speci c POI (far, average or near, where we consider near 100m, 100m<average 200m and far>200m)2 ; ii) current time of day (morning, afternoon and night); iii) current day of the week; iv) user's goal 1http://weka.sourceforge.net/doc 2It were used \small distance amplitudes" because in this (coffee, lunch, dinner and party). The POI's context is de ned by the POI: a) id; b) category; c) price (cheap, average, expensive); d) timetable (morning, afternoon, night, or combinations); e) day o (a day of the week or combinations). 3.1.5
The number of POIs that exist in Coimbra (Gowalla returned about 954) made it impossible to manually evaluate the whole city. For this reason, it was used a smaller part of the city that had more POIs density and diversity (Coimbra's Downtown). So, we studied the type of POIs in that area, and also restricted the set to three main categories (fFood, Shopping, Nightlifeg, the categories that contain more POIs). The number of sub-categories for Food are 44, Shopping 51 and Nightlife 11, with 59, 29 and 29 di erent POIs, respectively.
As referred above (see 3.1.1), we gathered more information about the POIs. The extra information we manually gathered from the places, was the POI's: Price (cheap, average or expensive); DayO (day(s) the POI closes); Timetable (part of the day in which the POI is open). So, the combination of this new data with Gowalla's information, ful ls the POI's context. 3.1.6
In this topic we present the metrics that will be used in our experiment. Equation 1 will be used to correlate two di erent types of data. Precision, recall and F1 formulas will be used to analyse the system's accuracy.
The Correlation Coe cient ( ) is used to return the correlation coe cient between two arrays, mi and xi, where fmi; xig 2 R, 2 R: 1 1, being i 2 N and corresponding to the matrix's index.
(mi; xi) =
P(mi i rP(mi i m)(xi
x) m)(xi x)
Precision will be used to evaluate the quality of the recommendations. Speci cally, it is the number of correctly recommended POIs divided by the total number of recommended POIs.
P recision =
Recall evaluates the quantity of POIs extracted. More precisely, it is the number of correctly recommended POIs, divided by the total number of correctly evaluated POIs that should have been retrieved.
Recall =
The F 1 score can be interpreted as a weighted average of experiment we only considered situations in which the user reach his destination on foot. (1) (2) (3) the precision and recall.
F1 =
(4) 3.2
Our experiment can be divided in two di erent evaluations: cross validation (3.2.1), and the use of metrics (3.1.6) to compare the output recommendations given by the system with manual evaluation (3.2.2 and 3.2.3). It is important to explain that the system's classi er was trained using a dataset (see 3.1.2) containing: the original training dataset (which has correct classi cations given by us); and a list of instances that were created from all POIs the system recommended during the simulation period. These POIs that were recommended by the system were inserted in that dataset, not with the classi cation given by the system, but instead with the feedback given by the user during the simulation. The resulting classi er was used to do the cross validation experiment (3.2.1). 3.2.1
It was chosen to do 10 runs and 10 folds, because this
is a combination that guarantees better evaluation [
Table 3 shows the detailed accuracy of our classi er, by class (Cl). Each class corresponds to the prediction values, in a scale of 1 to 5, as explained in section 3.1.2. For each class, the table shows the percentage of true positive (TP), false positive (FP), precision (P), recall (R), F1 score (F1) and ROC Area. The results demonstrate that class 1 has better results. This is due to the greater number of instances in the training dataset, classi ed with 1. Indeed, this happens because in many user's contexts there are always some irrelevant POIs (for instance, POIs that do not suit the user's goal). This makes the classi er more accurate in this class. Although the remaining classes do not have the same accuracy, their results are also very promising. 3.2.2
To test our approach, we used a set of pre-de ned scenarios that simulate real situations. Although we only used three di erent user locations (the ones that had more POI density), we analysed 18 di erent user contexts (see section 3.1.4). This 18 combinations were named runs.
The 18 runs resulted from the combination between di erent user's request, each one in a speci c context (see section 3.1.4) and all the nearby POIs recommended by the system. More precisely in this experiment, it was used three user's locations in six di erent situations. Goal, time of day, day of the week: [Coffee, Morning, Sunday]; [Coffee, Afternoon, Monday]; [Coffee, Night, Tuesday]; [Lunch, Afternoon, Wednesday]; [Dinner, Night, Friday]; [Party, Night, Saturday].
Our goal was to compare the system's recommendations with a manual evaluation made by human judges, and to apply some metrics to analyse our system's performance.
The judges evaluated every POI, from every run, according to the current user's context and POI's context, using the following scale: 0 - if the POI does not satisfy the user's context or the user's goal; 1 - if the POI satis es the user's context and the user's goal, but if it is expensive or too far from the user; 2 - if the POI satis es the user's context and the user's goal, and it is not expensive or far.
It is important to refer that the classi er's training dataset was built based on the preferences of a particular user's pro le (i.e., POIs that were near, cheaper, and that were not closed, see section 3.1.3 for more details). The evaluation performed by the human judges was also based on the preferences of the same user's pro le. They were asked to give their personal opinion for a list of scenarios, but never contradicting the user's pro le they were simulating.
To perform the manual evaluation, we create a user interface using Google Maps3. The POIs' names were omitted to avoid that the judges' personal opinion in uenced the evaluation, since the classi er was trained based on the POI's category. We had to do this to prevent discrepancy between the judges preferences and the user's pro le (3.1.3).
The manual evaluation was important to evaluate the performance of the system in ambiguous cases (a POI with an average price and average distance). In this speci c situations, the agreement between the human judges was low (14.3%). However, the PAA was trained to a speci c user's pro le and it is expected, in these ambiguous cases, to give better results for the judge with preferences closer to the user's pro le used in the training process (notice that each user has a PAA that learn with his preferences, individually).
Furthermore, the exact agreement among judges resulted in 93.3% (using the three values in the scale: f0, 1, 2g). In addition, we also calculated the relaxed agreement (using a scale of f0, 2g, considering POIs classi ed as 1 and 2 as correct), resulting in 95.7%. 3.2.3
In order to observe the relationships between the manual evaluation and the output values given by the RS, the correlation coe cients between them were computed and are 3http://code.google.com/apis/maps/index.html shown in gure 2. In addition, the F1 score was calculated ( gure 3). The x-axis represents a run, which corresponds to the simulation of a user's request in a speci c context (see 3.1.4) and all the nearby POIs recommended by the system (see 3.2.2). We simulated di erent requests, leading to a total of 18 runs. More speci cally, runs: f1, 2, 3, 7, 8, 9, 13, 14, 15g = goal Co ee; f4, 10, 16g = goal Lunch; f5, 11, 17g = goal Dinner; and f6, 12, 18g to the goal Party.
In order to avoid some of the ambiguity that could arise when using a 1-5 scale, the human judges evaluated the system in a scale of 0 to 2 (see section 3.1.2 and 3.2.2, respectively). Furthermore, to calculate the correlation (eq. 1) between the system's recommendations and the evaluation of the human judges, the scale of both evaluations was standardised. The system's scale was converted to a scale from 0 to 2: where 1 and 2 corresponds to 0; 3 corresponds to 1; and 4 and 5 corresponds to 2. Therefore, gure 2 shows the correlation coe cients between the most common evaluated value (i.e., the exact agreement correlation, represented as EA) given by each of the human judges (corresponding to H1, H2 and H3, in the chart) and the system's recommendations, through the 18 runs.
As we can see in gure 2, the results are promising. However, some of the results have low correlation values because when we trained the system, we discarded all contexts that make no sense, like having lunch at night or morning and having dinner or to party at morning or afternoon. On the other hand, the goal Co ee is valid in all times of day, resulting in a lot more instances and, consequently, the system performed better when this was the user's goal. In order to overcome this problem, more instances with goals Lunch, Dinner and Party should be added to the training dataset.
The gure 3 shows the evolution of the F1 (eq. 3) values (y-axis), in all the 18 runs (x-axis). In the gure 3, the results represented by the legends named High and Low, correspond to recommendations given by the system, with a score of 2 and a score of 2 and 1, respectively. This allow us to compare the results with a high lter, considering only the best recommendations (score 2), and with a low lter, considering all the good recommendations (score 1 and 2).
As we expected, higher values are obtained for the goal Co ee (see for example run 7 and 8), and low values are obtained for the goal Lunch and Dinner (see for instance runs 16 and 17). This happens because, as we mentioned before, the goal Co ee is valid in all times of day and the system performed better in these situations.
In this paper, we discussed the combination of context and intention-awareness with RS, applied in a locationbased application. We pointed out what advantages are earned in using, besides the context, the user's intentions, and how to integrate both into a location-based RS. We also presented our system's architecture and described its advantages, such as its modular nature. Machine learning techniques were used to train the classi ers, more precisely the Naive Bayes Updateable algorithm. Machine learning can be a powerful tool to predict which content will be interesting for a determined user, but it should be used with caution and the datasets must be well de ned.
Then, we created an experimental set-up to evaluate the system's performance. To test the accuracy of our system, we used various evaluation methods. First, we did a cross-validation test. Next, in order to observe the relationships between the manual evaluation and the output values given by the PAA, the correlation coe cients between them were computed. Nevertheless, after analysing the results in general, the recommendations can be considered very promising, being this a good starting point to develop a context and intention-aware POI RS.
In the future, we are planning numerous improvements
to our work, such as: take into account new attributes
(e.g., POI's quality); test and compare other machine
learning algorithms; analyse other users' pro les; use new
information sources; and make it available to the community
in order to get more feedback. We think that with more
data and more training the results from our system could
improve. Furthermore, we intend to make available to the
user the possibility of changing what values t in each
attributes (e.g., what price is considered cheap). Moreover,
we plan to analyse the system accuracy when applying
selective attention metrics, such as surprise [
Work funded by Fundac~ao para a Ci^encia e Tecnologia | Project PTDC/EIA-EIA/108675/2008, and by FEDER through Programa Operacional Factores de Competitividade do QREN | COMPETE:FCOMP-01