Recommendation of venues in location-based services using spatial and temporal context

Thumbnail Image

URL

Journal Title

Journal ISSN

Volume Title

Insinööritieteiden korkeakoulu | Master's thesis

Authors

Date

2014-12-15

Department

Major/Subject

Geoinformatiikka

Mcode

M3002

Degree programme

Geomatiikan koulutusohjelma

Language

en

Pages

46

Series

Abstract

With the emergence of mobile devices and wireless networks, location-based services have attracted millions of users. People are increasingly employing these location-based services to explore places (for example restaurants, bars, stores, sights) and share their locations. As this popularity grows, the need for intelligent filtering of the service content is increasing. The objective of this research was to study the means of effectively recommending locations for users in the context of location-based systems. The special qualities of location-based recommendation were emphasized, namely spatial and temporal context. The research consisted of two phases: First, a literature study on different recommendation methods and the means of effectively using spatial and temporal context in recommendation was conducted. Then, a quantitative case study was conducted on an actual location-based service dataset using methods determined in the literature study. Based on the literature study, collaborative filtering was chosen to be used for the recommendation model. The recommendation problem could then be represented as a user-location matrix where each cell represents a utility-value (rating, a binary value, or a frequency value etc.) between a user and a location from which recommendations are based on. To learn the unknown (unvisited) cells of this matrix, a method called matrix factorization (MF) was used due to its dimensional reduction qualities and effectiveness with large, sparse matrices. This matrix factorization was further enhanced with temporal weighing based on the conclusion that user’s preference of locations differs between times of day or week. Finally, spatial context was added to the model by discovering spatial clusters where a user prefers to frequent and learning the maximum conditional probability between a location and these clusters. Based on these methods, a quantitative case study on a real, publicly distributed location-based service dataset was conducted. The dataset was divided using chronological sampling to a learning dataset from which recommendations were made and a test dataset from which the precision of the recommendations was evaluated. The empirical study was performed using three different algorithms: (a) plain matrix factorization, (b) matrix factorization with spatial preferences, and (c) matrix factorization with both spatial preferences and temporal weights. The results determined that the context of spatial and temporal preferences improved the generic matrix factorization model greatly. The dataset, however, was greatly limited and provided significant noise to the model in the form of the majority of users only having a few visitations. Users with higher visitations did however receive significantly higher precision on recommendations despite this noise in the dataset.

Mobiililaitteita ja langattomia verkkoyhteyksiä hyödyntävät sijaintipohjaiset palvelut ovat houkutelleet miljoonia käyttäjiä. Ihmiset käyttävät näitä palveluja yhä enemmän paikkojen, kuten ravintoloiden, kauppojen ja nähtävyyksien tutkimisessa. Suosion kasvaessa lisääntyy tarve älykkäälle sisällön suodattamiselle. Tässä tutkimuksessa kartoitettiin keinoja tiedon suodattamiselle erilaisten suositusmenetelmien avulla. Tutkimuksessa painotettiin sijaintipohjaisen suosituksen erityispiirteitä, sijainti- ja aikapohjaista kontekstia. Tutkimus sisälsi kaksi osuutta: Kirjallisuustutkimus tehtiin erilaisista suositusmenetelmistä ja keinoista hyödyntää sijainti- ja aikakontekstia. Tämän jälkeen valittuja suositusmenetelmiä hyödynnettiin kvantitatiivisessa tutkimuksessa käyttäen oikeaa sijaintipohjaisen palvelun aineistoa. Kirjallisuustutkimuksen pohjalta päädyttiin siihen, että suositukset tehdään käyttäen yhteisöllistä suodatusta. Tällöin suositusongelman voi esittää käyttäjä-sijainti –matriisina, missä jokainen solu esittää hyödyllisyyttä (esimerkiksi arvosanaa, binääriarvoa, frekvenssiarvoa) käyttäjän ja paikan välillä, minkä avulla suositukset tehdään. Tuntemattomien solujen oppimiseen käytettiin matriisin faktorisointi -menetelmää johtuen sen kyvystä pienentää ulottuvuutta ja tehokkuudesta suurien, harvojen matriisien käsittelyssä. Tätä menetelmää kehitettiin temporaalisilla painoarvoilla perustuen oletukseen, jonka mukaan käyttäjät suosivat eri paikkoja eri aikoina. Lopuksi malliin lisättiin sijaintikonteksti etsimällä käyttäjille sijainnillisia klustereita ja arvioitiin maksimaalinen ehdollinen todennäköisyys paikan ja sijaintiklustereiden välillä. Näiden menetelmien perusteella suoritettiin kvantitatiivinen tutkimus käyttäen oikeaa, julkisesti jaettua sijaintipohjaisen palvelun aineistoa. Tämä aineisto jaettiin kronologista näytteenottoa käyttäen oppimisaineistoon, jonka perusteella suositukset tehtiin sekä testiaineistoon, jonka perusteella suosituksien tarkkuutta arvioitiin. Empiirinen tutkimus suoritettiin käyttäen kolmea eri algoritmia: (a) tavallinen matriisin faktorisointi, (b) matriisin faktorisointi sijainnillisten mieltymyksien kanssa sekä (c) matriisin faktorisointi aika- ja sijaintikohtaisten mieltymyksien kanssa. Empiirisen tutkimuksen tulokset osoittivat selvästi että sijainti- ja aikakohtaisen kontekstin käyttö suosituksissa paransi suositusmallin tarkkuutta huomattavasti. Tutkimuksessa käytetty aineisto oli kuitenkin puutteellista ja aiheutti kohinaa mallille johtuen suuresta määrästä käyttäjiä, joilla oli vain muutama vierailu aineistossa. Tästä kohinasta huolimatta käyttäjät, joilla oli suurempi määrä vierailuja, saivat tutkimuksessa huomattavasti tarkempia suosituksia.

Description

Supervisor

Virrantaus, Kirsi

Thesis advisor

Virrantaus, Kirsi

Keywords

location-based system, spatio-temporality, machine learning, recommendation systems, collaborative filtering

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-201501221166

Collections

[dipl] Insinööritieteiden korkeakoulu / ENG