In this paper, we present a semantic content-based approach that is employed to study driver preferences for Points of Interest (POIs), e.g. banks, grocery stores, etc., and provide recommendations for new POIs. Initially, logs about the places that the driver visits are collected from the cloud-connected navigation application running in the car. Data about the visited places is gathered from multiple sources and represented semantically in RDF by `lifting' it. This semantic data is then combined with driver context and then input into a machine learning algorithm that produces a probabilistic model of the driver's preferences of POIs. When the driver searches for POIs in an unknown area, this preference model is used to recommend places that he is most likely to prefer using a nearest-neighbor approach. In this paper, we describe the details of this content-based approach for recommendation, along with the results of a user study that was conducted to evaluate the approach.
In deploying connected services to the car, it is important that driver safety is given a high priority. To reduce possible distractions in accessing information, the in-vehicle navigation system enforces restrictions on the way information is presented to the driver. One such constraint is that the number of items that can be displayed in a list on a single screen is xed to a limited number of slots. When the driver searches for banks in the car, for example, the search results are displayed as a list lled in the available slots. If the number of search results exceeds the number of slots, then the extra results are pushed to the next page. Accordingly, there arises a need for presenting the most relevant information to the driver in those slots. We model this, as a recommendation problem of providing personalized, contextualized information to the driver. In particular, this paper discusses the recommendation of Points of Interest (POIs), e.g. banks, grocery stores, etc., in the car using a combination of semantic technologies and a recommendation system.
In our previous paper on Learning Driver Preferences of POIs using a
Semantic Web Knowledge System[
The paper is organized as follows. We rst provide a detailed explanation of the recommendation task and describe the reasons for the selection of a contentbased approach. We then describe how we learn the driver preferences. This is followed by an explanation of how the learned model is used in the recommendation of POIs. We also brie y describe the underlying system, which uses semantic technologies in the data representation and services, called the Semantic User Preference Engine or Supe. This is followed by a description of the user study that was conducted using an implementation of Supe, and its results. We also include relevant work in the Semantic Web and recommendation literature, for modeling user preferences and recommendations. Lastly, we conclude by summarizing our ndings along with future work. 2
The selection of the algorithm for POI recommendation in the car is largely based on two issues: the nature of the data available and desired recommendation to be produced. In the rst case, data comes from the usage history of the navigation application in the vehicle. The user can select a place to navigate to in three ways, as can be seen in Fig. 1: (1.a) driver chooses a POI from the head-unit; (1.b) user selects a POI from a suite of installed applications on his smartphone or (1.c) user pre-selects a POI from his desktop/browser application and `sends' the POI over the Cloud to the navigation application running in the car. The selected POIs from these connected devices can be tracked on the Server running in the Cloud before sending it to the navigation application. As we can only track places that the driver has visited, which we assume he likes, we only have positive training examples. For the second issue, we want to try to provide a recommendation that answers the question, `Which POIs among the ones available around the driver is he most likely to prefer?', when the user searches for POIs. Accordingly, the recommender system should be able to choose the place most likely to be preferred by the user from a set of candidate places returned by the database.
Recommender systems are popularly classi ed into Collaborative Filtering,
Content-based approaches or a mixture thereof[
BEFORE Tracking Preferred POIs and Building Preference Model
AFTER PresenDng Personalized Results when User Requests a POI Search 1.a)th Uese Nra sveigleacDtso na PUOniIt f rom 2) DesDnaDon sent to
NavigaDon Unit 1.b) Select place from suite of installed applicaDons 1.c) “Send” POI to car from desktop / browser applicaDon
Supe BEFORE: Learn the user’s
Preference Model AFTER: Use the Preference Model for Recommending
POIs
1) Request for POI Search
e.g. “search banks”
2) Result sorted by
esDmated preference
(Preferred list of banks)
reason of failure of recommendation in the dataset. As an example, consider a
person who lives in San Jose, CA. The places that he visits frequently in his
neighborhood - e.g. his bank, grocery store, etc., along with history of others
in his neighborhood become part of the training dataset. When the user travels
to a remote place - e.g. Livermore, CA (about 40 miles away) and wants to
search for a bank, it is highly unlikely that there would be another set of users
who go to the same bank as the user in San Jose and might have visited a
bank in that particular neighborhood in Livermore. Contextual information is
also important in providing relevant recommendations. Though Collaborative
Filtering techniques that include context by introducing new dimensions apart
from the traditional two -Users and Items - have been studied[
In contrast, a content-based approach seems more intuitive. In the rst
example, the user might prefer a certain banking chain, which has a branch in
his neighborhood and he would prefer a local branch when he is searching for
ATMs in Oakland. In case of gas stations, he may have a preference for cheaper
gasoline. A single Collaborative Filtering approach would be insu cient for
recommending such cases, especially in the case of uctuating gas prices. Contextual
information can be appended to the POI data as extended attributes to generate
a context-speci c version of the item, which can then be used to provide
recommendations. The content-based approach for POI recommendation employed in
this paper, is similar to other recommender systems in relevant literature [
Before we can recommend POIs to the driver, we rst need to generate a model of his preferences. To do so, the data collected from his navigation history is rst converted into machine learnable data. When connected devices send data to the in-vehicle navigation application or the driver selects a destination on the navigation system, Supe tracks the visited/consumed POIs and stores them as driver history. The process of generation of the user's preference model from this data is described below. Fig. 2 shows the steps involved in converting POI data about a bank, visited by the driver, into machine learnable data. hasName hasLoca+on hasDistance hasDrive hasAverage CLASS
FromWork ThruATM Ra+ng 142 FALSE 3.7
preferred rdf:type=bank hasName=“Bank of America”
hasAverageRa7ng=4.5 BofA_94086
hasDistanceFromWork hasLoca7on =2535m _:x hasDriveThruATM
=TRUE hasCity=“Sunnyvale”
hasAddress=“123 Murphy St.” c) Instance Molecule with Added User Context
CONVERSION TO MACHINE
LEARNABLE DATA 2535 TRUE hasAddress
4.5 hasCity
preferred
CLASS 43 Murphy St. 123 Murphy St.
Sunnyvale preferred Sunnyvale preferred rdf:type=bank
BofA_94086 hasLoca7on _:x hasDriveThruATM
=TRUE hasCity=“Sunnyvale”
hasAddress=“123 Murphy St.” b) Instance Molecule for Bank of America hasName=“Bank of America” hasAverageRa7ng=4.5
ADDING
CONTEXT
LIFTING { name: “Bank of America”, yelp_id: “BofA_94086”, category: “bank”, loca@on:{ address: “123 Murphy St.”, Bank of city: “Sunnyvale” America } hasDriveThruATM: “yes”, ra@ng: 4.5 }
XYZ Credit
Union a) Business Data JSON Returned by Yelp API
d) Bank Table with Training Instances for Classifier
Fetching RDF data for the Visited POIs: Data for the POIs, which were
collected as driver history, is retrieved from multiple sources like a POI database
or Web Services (by searching for the POI using information like its name,
location, address, etc.). For example, the JSON response from a Web Service
(e.g. Yelp API) for the \Bank of America" branch, which the user visited, is
shown in Fig. 2 (a). As each of these sources might have di erent schemas, it
is necessary to integrate this information together into a common vocabulary.
At the heart of Supe is a Places Ontology (see Fig. 3). The ontology de nes
a concept hierarchy of places along with the properties associated with each
concept. Data from the di erent sources is `lifted' into this ontology and merged
together. For the \Bank of America" that the user visited, the lifting process
converts the JSON response of the Web Service into an RDF instance molecule
[
Adding Context: Data from the driving history along with the driver's personal information is then used to automatically generate context information. The relevant triples, generated using pre-de ned rules, are then added to the RDF instance molecule from the previous step. For example, if the user has his home or work address stored, then the distance from home or distance from work GroceryStore
POI Bank hasDriveThruATM, … hasName, hasLoca,on , hasAverageRa,ng, … MovieTheatre hasCarWash, …
GasStation contexts can be added. User context hasDistanceFromWork is added to the instance molecule in Fig. 2 (c). The user's preference model can now be trained with the instance molecule generated.
Converting the RDF Instance Molecule to Machine Learnable data: Since we use a content-based approach for recommendation, we need to convert RDF into a representation that machine learning algorithms can understand. The translation of instance molecules into a table of training data, as used by conventional machine learning algorithms, is relatively straight-forward and is explained below. (Due to lack of space, Fig. 2 (d) only shows a representative set of columns that can be derived from Fig. 2 (c)). 1. The Table: All instances belonging to one concept are grouped together in a single table, e.g. banks in Fig. 2 (d). 2. Rows in the Table: Each instance molecule to be added to the preference model translates to a row in the table. Instead of dropping the URI, as identi ers usually do not contribute to the learned model, we add the identi er to the table (not depicted in Fig. 2 (d)) to bias the model with a higher preference to a previously visited place. 3. Columns in the table The attributes or property-value pairs for the instance get translated as columns and values in the table. The properties for which the type of the table is a domain, appear as columns. For example, while the hasDriveThruATM is a property of Banks, the hasName property is inherited from the parent concept POI and is also present in the table in Fig. 2. 4. Values in the Table: RDF Literals in a column are translated as one of string, numeric or nominal values. The relevant information for the conversion into either of these types can be determined from the ranges of the properties in the ontology, or speci ed explicitly during ontology construction. For example, a value of the hasName property translates to string type, the hasAverageRating property translates to numeric type and the hasDriveThruATM property translates to nominal type. For values of properties that are RDF Blank Nodes, we use nesting of tables where we track inner values for the properties of the blank node (e.g. hasLocation property) . For properties with URI values, we can choose to either use the lexical value of the identi er as cell value in the table if we want to introduce bias, or represent the instance in a nested table similar to blank nodes if the values of its properties are important. For missing attributes, the cells in the table are empty. 5. Class Column in the Table: Since visited places translate to only positive training examples, all class values in the table are marked as `preferred' Building the Preference Model: The table above, similar to the training data used for a nave-Bayes classi er, is then used to generate a preference model. The preference model generated is an optimized variation of the table, containing frequency counts/mathematical functions, and helps in calculating the likelihood probabilities. Instead of building the entire preference model from scratch every time a new instance is added, we use an incremental approach. 4
In content-based recommendation systems, determining if the user likes/dislikes
a particular item is a classi cation problem [
Fetching Candidate POIs and Adding Context: When the user wants to search for POIs, Supe rst retrieves candidate places that match the search criteria from the POI Database/Web Services. Necessary user and situation context are added to the POIs after lifting them into RDF, similar to the steps described in Section 3. These POIs can then be scored to nd out how likely is the user to prefer each of them.
Nearest-neighbor to a hypothetical Bliss-point Our approach is inspired from the nearest-neighbor algorithms used in clustering and classi cation.To nd how likely is the user to prefer each POI, we rst nd out how likely is the user to prefer its properties. Let's suppose that each candidate POI has only two properties - name and average rating of all users. The rst candidate POI hasName \Bank of America" and hasAverageRating of 3:5. We can calculate the likelihood probabilities - P (hasN ame = \Bankof America"jpref erred) and P (hasAverageRating = 3:5jpref erred) using the table from Fig. 2, similar to the likelihood calculation in a nave-Bayes approach. We can plot this point in a Euclidean space with the properties as the di erent axes (see Fig. 4 (a)). For a hypothetical POI that is always preferred by the user, each of its attributes would have the preference likelihood as 1.0. We can now plot this `bliss-point' on the Euclidean space. We can similarly plot other candidate POIs (see Fig. 4 (b)). The euclidean distance from the bliss-point is used for the recommendation, and the POI that is nearest to the bliss-point is recommended to the user. P(hasName| (0,1) preferred)
Bliss-‐point (1,1) P(hasName| preferred) (0,1) P(hasName= “Bank Of America”| preferred) Distance from Bliss-point We can easily extend the above method to an ndimensional space. The values of the attributes in the columns in the table in Fig. 2 (d) can either be Literals, Blank Nodes, URIs or missing. For literal values, the likelihood probability is calculated as follows: (i) a Gaussian distribution is used for the probabilities of numeric values (ii) a document similarity metric is used for the probabilities of string values and (iii) symbol probability is used for the probabilities nominal values. The distance for a property with a blank node is calculated recursively, by rst calculating the likelihood probabilities of its inner values, and then its distance from another hypothetical bliss-point in its own high dimensional space. For URIs, we can use a dual strategy depending on the nature of the property. In some cases, to bias toward previously seen values for properties, we calculate likelihood as its probability of the occurrence of that URI in that column. If the attributes of the corresponding instance are more important, then the likelihood can be calculated similar to the blank node. The distances from the bliss-point of multiple POIsneed to be normalized before they can be compared. This is done by dividing the distance by the distance of the origin to the bliss-point, thus taking care of missing attributes. For a multivalued property, we take the average of the distances of all its values. As an example, the distance from bliss-point for the Bank of America POI in Fig. 2 (d), would be calculated as follows.
v u u u D(Bof A 94086) = uu +(1 u t (1
P (2353 j pref erred))2 + (1
+(1
P (4:5 j pref erred))2 + D( : x)2 v u u W here D( : x) = uut +(1 (1
2 Recommending the POIs to the User The candidate items retrieved from the database are scored using the distance from bliss-point metric and sorted according to the distance. The sorted list of POIs is then sent by the Supe system to the navigation application as a recommendation. Once the user selects a POI from the list, it is fed back to the preference model and the system is able to learn incrementally. 5
Since the Supe system is described in detail elsewhere [
We implemented a smart-phone application emulating the in-vehicle navigation application for a user study. The application allowed users to search for POIs belonging to di erent categories (e.g. gas stations, banks, restaurants, etc.). A cloud-based server supporting the application was implemented using the description of Supe above. Around 50 people, who used their car for running household chores or for their daily commute to work, in the Bay Area (around San Francisco, CA) were selected for the user study. Each user was asked to add at least 10 places to his preference model by driving to the POIs he would visit in
ApplicaEons on the Devices
LinkeCdODNFaIDtaENTIAL Web Services
Object Store
Knowledge Services
Machine Learning Ontology1 his daily life and letting the application know that he like the place, by clicking a `like' button. Each user was also asked to perform 10 search tasks, where he would search for POIs and choose to one out of the recommended places. The application usage was recorded.
The following screenshot (Fig. 6) shows two instances of POI search for one such user. Initially, there are 3 slots for displaying recommendations, and any other places in the recommended POI list are scrollable. The rst image shows the results for search for banks in the user's daily commute area. The ones marked with a pin are the places that he has visited (and liked) and are used to build his preference model. When the user was in a remote place and in need of cash, he searched for banks using the application. The second capture shows that two of his preferred banks were ranked among the top three in the list. Intuitively the reader may gure out that this user prefers a speci c banking company. The model is able to detect this preference because its likelihood probability on the hasName axis is high. Similar patterns were also detected for other users in di erent categories, like gas stations, restaurants, etc.
(a) (b)
The users had been given two weeks to complete the tasks during which observations were made on the performance of their preference model. For each POI search task, a successful recommendation was counted if, from the 20 candidate POIs that the database returned, the user selected one of the top 3 recommendations. We tracked the success-rate (percentage of successful recommendations in the search task) of the preference model with the increasing size of the preference model and also with the number of searches performed. The selected POI was fed back to the preference model for learning the preference incrementally. Fig. 7 shows the performance of the preference model for one user. As can be seen, after the initial stabilization period, the success rate steadily improved with increasing number of instances in the preference model and as more searches were performed. Overall, for the 48 participants that completed the task, the success rate at the completion of the tasks was 47.63% on an average. This is better than a strategy for random recommendation of 3 out of 20 candidate POIs, which would result in a 15% success rate. Though the improvement in the success-rate was satisfactory, there is a clear scope for better performance. In the future, we intend to use this result as a baseline for comparisons with updates to the learning technique.
The use of a probabilistic approach also allowed us to `look inside' the preference model of a user. For example, for the user in Fig. 6, his preferences for the hasName attribute (word cloud) and distance from current location context (distribution) are shown in Fig. 8. These visualizations were useful for intuitively understanding the likelihood probabilities of the properties. 7
Content-based preference modeling has received large research attention in
recommendation systems over the past few years[
In the past year, the combination of RDF and machine learning has gained
some traction. The work that is perhaps most similar to our approach on
converting RDF to a machine learning table, is found in Lin et. al [
In this paper we described a semantic content-based approach for recommending POIs according to driver preferences learned using the navigation history. Our approach was able to build the preference model using RDF data associated with the driver history as a result of the following: (i) it used an easy translation method between semantic content (RDF data) into machine learnable tables (ii) the content-based approach was easily extendable to include and learn the contextual preference (e.g. distanceFromWork, etc.) (iii) the distance from bliss-point metric was used to recommend POIs from a set of candidates using the modeled preferences (iv) the probabilistic nature of the likelihood of the attributes in the preference model helped study the user's preferences by visualization. This was veri ed through a user study that produced a 47.63% success-rate.
Though our preliminary evaluation shows promising results with actual users, using simple metrics, it has scope for improvements. We intend to explore other machine learning techniques (e.g. kernel based, one-class classi cation, etc.) to improve the preference model, as future work. We also intend to test this on a larger dataset of driver history.