ONTWERP VAN EEN RECOMMENDATIESYSTEEM VOOR HET AANBIEDEN VAN DIENSTEN OP SOCIALE NETWERKSITES

ONTWERP VAN EEN RECOMMENDATIESYSTEEM VOOR HET AANBIEDEN VAN DIENSTEN OP SOCIALE NETWERKSITES DENIS DEFREYNE

Promotoren:! ! prof. dr. ir. Filip De Turck, prof. dr. ir. Bart Dhoedt Begeleiders UGent:! Steven Latré, Philip Leroux, Olivier Van Laere, Stijn Verstichel Begeleiders Netlog:! Pieter De Schepper, Joost Roelandts, Vincent Verlee Masterproef ingediend tot het behalen van de academische graad van Master in de ingenieurswetenschappen: computerwetenschappen

Vakgroep Informatietechnologie Voorzitter: prof. dr. ir. Daniël De Zutter Faculteit Ingenieurswetenschappen Academiejaar 2009-2010

ONTWERP VAN EEN RECOMMENDATIESYSTEEM VOOR HET AANBIEDEN VAN DIENSTEN OP SOCIALE NETWERKSITES DENIS DEFREYNE

Promotoren:! ! prof. dr. ir. Filip De Turck, prof. dr. ir. Bart Dhoedt Begeleiders UGent:! Steven Latré, Philip Leroux, Olivier Van Laere, Stijn Verstichel Begeleiders Netlog:! Pieter De Schepper, Joost Roelandts, Vincent Verlee Masterproef ingediend tot het behalen van de academische graad van Master in de ingenieurswetenschappen: computerwetenschappen

Vakgroep Informatietechnologie Voorzitter: prof. dr. ir. Daniël De Zutter Faculteit Ingenieurswetenschappen Academiejaar 2009-2010

I

ii

VOORWOORD

Het schrijven van een thesis is een uitputtende en tijdrovende zaak. Een groot aantal mensen hebben mij echter bijgestaan en ervoor gezorgd dat ik zelfs in moeilijke perioden steeds mijn motivatie en interesse bleef behouden. Dank gaat uit naar mijn promotoren, prof. dr. ir. Filip De Turck en prof. dr. ir. Bart Dhoedt, en uiteraard ook naar mijn begeleiders op de Universiteit Gent, Steven Latré, Philip Leroux, Olivier Van Laere en Stijn Verstichel. Ik wens ook de begeleiders bij Netlog, Pieter De Schepper, Joost Roelandts en Vincent Verlee, te bedanken voor hun steun. Voor de onmisbare hulp met de thesistekst wil ik graag Andy Georges bedanken. Ten laatste wil ik mijn ouders bedanken, en natuurlijk ook mijn vrienden, met name Mattias Poppe, Niels Soetens, Thomas Spranghers en Wim Vander Schelden, voor de schitterende studententijd die ik op de Universiteit Gent beleefd heb.

Denis Defreyne mei 2010

I

iii

TOELATING TOT BRUIKLEEN

“De auteur geeft de toelating deze masterproef voor consultatie beschikbaar te stellen en delen van de masterproef te kopiëren voor persoonlijk gebruik. Elk ander gebruik valt onder de beperkingen van het auteursrecht, in het bijzonder met betrekking tot de verplichting de bron uitdrukkelijk te vermelden bij het aanhalen van resultaten uit deze masterproef.”

Denis Defreyne mei 2010

ONTWERP VAN EEN RECOMMENDATIESYSTEEM VOOR HET AANBIEDEN VAN DIENSTEN OP SOCIALE NETWERKSITES door Denis DEFREYNE Masterproef ingediend tot het behalen van de academische graad van MASTER IN DE INGENIEURSWETENSCHAPPEN: COMPUTERWETENSCHAPPEN: OPTIE SOFTWARE-ENGINEERING Academiejaar 2009–2010 Promotoren: prof. dr. ir. Filip DE TURCK, prof. dr. ir. Bart DHOEDT Begeleiders UGent: Steven LATRÉ, Philip LEROUX, Olivier VAN LAERE, Stijn VERSTICHEL Begeleiders Netlog: Pieter DE SCHEPPER, Joost ROELANDTS, Vincent VERLEE Faculteit Ingenieurswetenschappen Universiteit Gent Vakgroep Informatietechnologie Voorzitter: prof. dr. ir. Daniël DE ZUTTER

Overzicht Websites die grote hoeveelheden inhoud (content) en diensten aanbieden, kampen al snel met het probleem dat gebruikers het steeds lastiger vinden om alle relevante zaken te vinden. Deze masterproef doet onderzoek naar mogelijke technieken die gebruikt kunnen worden om aanbevelingssystemen te bouwen. Zulke systemen zullen aan gebruikers objecten aanbevelen die met grote waarschijnlijkheid door deze gebruiker als goed bevonden zullen worden. De implementatie van dit aanbevelingssysteem maakt gebruik van collaborative filtering en content-based filtering om aanbevelingen te bouwen.

Trefwoorden Recommender systems, collaborative filtering, content-based filtering

Design of a Recommender System for Offering Services on Social Networking Sites Denis Defreyne Supervisor(s): prof. dr. ir. Filip De Turck, prof. dr. ir. Bart Dhoedt Abstract— Web sites that offer large amounts of content and services often have the problem that users find it hard to find relevant items. In this master dissertation, a recommender system aimed at solving this problem was designed and implemented. Given a user, recommender systems offer items that will likely be of interest to this user. The recommender system implemented as part of this master dissertation uses collaborative filtering and content-based filtering to generate recommendations. Keywords— recommender systems, collaborative filtering, content-based filtering

I. Introduction

W

EB sites that offer large amounts of content and services, such as online playable computer games, quickly face the problem that users find it increasingly hard to discover items that are relevant to their interests. Browsing the entire collection of items is hard, if not impossible, due to the vastness of this collection. Users may choose to manually filter the collection or rely on word of mouth communication in order to discover relevant items, but this process is both slow and inaccurate. Such web sites often store information about its users. This information can include age and gender, but also a history of the content items and services that have been used. It may also include ratings for items, so that users can let the site know which items they do not like at all and which items they absolutely love. Using the information gathered from its users, a web site can learn the tastes and preferences of its users. Recommender systems do exactly that, and can, using this information, generate a collection of recommendations that will likely be of interest to a given user. The goal of this master dissertation is to build such a recommender system. II. Technologies Several technologies related to recommendation systems exist. Collaborative filtering [1] is likely the most wellknown technique for building recommender systems, but alternative technologies such as content-based filtering can also be useful for creating a recommender system. This section will briefly explain each technology that was used in the implementation. A. Collaborative filtering Collaborative filtering (CF) is a collection of techniques that attempts to automate word of mouth recommendations. In collaborative filtering, recommenders will suggest items that have not yet been rated by the user request-

ing the recommendations, but have received high ratings by users with similar taste to the given user (neighbours). Collaborative filtering does not make use of properties of the items, such as their categories or tags, nor demographic properties of the users, such as age and gender. A simple and na¨ıve concrete collaborative filtering technique is user-based collaborative filtering. Using this technique, users are represented as n-dimensional vectors, where each element represents the rating for one of n items. In this n-dimensional space, k neighbours of a given user are searched for using a k-Nearest Neighbour method. The items that have been given a high rating by these neighbours, but have not been rated by the user themself, will be recommended to this user. This na¨ıve technique has several drawbacks. The complexity of rating prediction in user-based collaborative filtering is linear in the number of users, and this technique will therefore perform quite badly on systems with more than a few thousand users. In addition to this, it has issues with sparse data: since a user will typically only have rated a small subset of items, finding neighbours of a given user can be quite unreliable. Alternative collaborative filtering techniques such as item-based collaborative filtering aim to solve these problems by using a model. Such models will require a certain time to build, but recommendation generation speed will improve drastically. In addition to improving the performance, some model-based techniques eliminate issues with sparse data, as mentioned above. Item-based collaborative filtering uses a similarity model in which the similarity between each pair of items is expressed. This similarity indicates how closely the rating behaviour for the first item matches the rating behaviour for the second item, or, in other words, how likely it is that a user who likes the first item will also like the second item. B. Content- and audience-based filtering Content-based filtering makes use of a similarity model where similarity is calculated solely on the properties, such as tags, categories and genres, of the individual items. Items that have more properties in common will have a higher similarity. Generation of predictions and recommendations is identical to the methods used for generating predictions and recommendations for item-based collaborative filtering. Audience-based filtering is based on a similarity model where similarity between items is derived from demographic characteristics of the audience that makes use of

Comparison of recommendations (threshold 0,9)

III. Analysis of the dataset

1

0,8 Fraction true positives (sensitivity)

these items. Such characteristics can include age and gender. This algorithm was developed as part of this master dissertation. As with content-based filtering, generation of rating predictions and recommendations is identical to the methods used in item-based collaborative filtering. This algorithm calculates similarity between two items based on a property by generating an interval [E − σ, E + σ] with E being the mean and σ being the standard deviation of this property. The resulting similarity is the size of the intersection divided by the size of the union of these intervals.

0,6

0,4

0,2

0

Two distinct datasets have been used for evaluating the implemented system. The first dataset contains ratings that have been given explicitly by users, while the second dataset contains implicit ratings that have been derived from usage. Ratings in these datasets are real values between 0 and 1, with 1 being the highest rating. The sparsity of both datasets is fairly high compared to datasets that are more commonly used in evaluations, such as the Jester dataset, which has a sparsity of 78.7%. The dataset with implicit ratings has a sparsity of 88.1% and the explicit ratings dataset has a sparsity of 94.3%. Also worth noting is that there are over four times as many implicit ratings than there are explicit ratings, presumably because of the extra effort that giving explicit ratings takes. IV. Evaluation The accuracy of the collaborative filtering, content-based filtering and audience-based filtering implementations have been evaluated in two ways; both the accuracy of the rating predictions and the accuracy of the recommendations have been evaluated. These two distinct ways of evaluating the accuracy of recommender systems have been described in detail in [2]. Comparison of predictions 1

CF (limit 5; explicit; adjusted cosine) CF (limit 5; explicit; adjusted cosine; normalised) CF (limit 5; explicit; pearson) CF (limit 5; explicit; pearson; normalised) random 0

0,2

0,4 0,6 Fraction false positives (1-specificity)

0,8

1

Fig. 2. ROC-curve (false positives versus true positives) for collaborative filtering with explicit, user-provided ratings

well as evaluations for implicit ratings (ratings derived from usage) have also been performed. The evaluation results for collaborative, content-based and audience-based filtering, combined with implicit and explicit ratings, indicate that recommenders based on collaborative filtering give the best results. The evaluation results also indicate that implicit ratings (ratings that are derived from usage) give better results than explicit ratings (ratings that have explicitly been given by users). Explicit ratings as wel as content-based filtering and audience-based filtering still give good results, but are nonetheless surpassed in quality by collaborative filtering combined with implicit ratings. V. Conclusions For the dataset that was used during the implementation and evaluation of the system, collaborative filtering results in the highest recommendation accuracy. Ratings that have been derived from usage perform better than explicit ratings, as they prove to be more accurate as well as more universally available.

0,8

Cumulative frequency

VI. Acknowledgements 0,6

0,4

0,2

0

CF (limit 5; explicit; adjusted cosine) CF (limit 5; explicit; adjusted cosine; normalised) CF (limit 5; explicit; pearson) CF (limit 5; explicit; pearson; normalised) 0

0,2

0,4

0,6

0,8

1

Thanks go out to the people who have assisted me during the writing of this dissertation. This includes Steven Latr´e, Philip Leroux, Olivier Van Laere and Stijn Verstichel. Thanks go out to my supervisors, prof. dr. ir. Filip De turck and prof. dr. ir. Bart Dhoedt. Last, but not least, I would like to thank the people at Netlog for their support; thanks go to Pieter De Schepper, Joost Roelandts and Vincent Verlee in particular.

Error

References Fig. 1. Cumulative histogram of the error for collaborative filtering with explicit, user-provided ratings

Figure 1 shows the accuracy of the predictions while Figure 2 shows the accuracy of the recommendations. Both evaluations were performed for collaborative filtering with explicit ratings. In both cases, the area below the curve is an indication for the quality of the recommender. Evaluations for content-based and audience-based filtering, as

[1] Toby Segaran, Programming collective intelligence, O’Reilly, 2007. [2] Jonathan L. Herlocker, Joseph A. Konstan, Loren G. Terveen, and John T. Riedl, “Evaluating collaborative filtering recommender systems,” ACM Trans. Inf. Syst., vol. 22, no. 1, pp. 5–53, 2004.

I

vii

INHOUDSOPGAVE

Voorwoord

ii

Toelating tot bruikleen

iii

Overzicht

iv

Extended abstract

v

Inhoudsopgave

vii

Lijst van afkortingen

ix

Lijst van symbolen

x

1. Inleiding 1.1. Situering . . . . . . . . . . 1.2. Probleemstelling . . . . . . 1.3. Doelstelling . . . . . . . . . 1.4. Samenwerking met Netlog 1.5. Gebruiksvoorbeelden . . .

. . . . .

1 1 1 2 2 2

. . . . . . . . . . . . . .

3 3 4 5 6 7 8 8 9 9 10 11 12 13 13

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

2. Technologiestudie 2.1. Gelijkaardigheidsmetrieken . . . . . . . . . . 2.2. Collaborative filtering . . . . . . . . . . . . . 2.2.1 User-based collaborative filtering . . 2.2.2 Item-based collaborative filtering . . 2.2.3 Andere technieken . . . . . . . . . . 2.3. Content-based filtering . . . . . . . . . . . . 2.4. k-Nearest Neighbour . . . . . . . . . . . . . . 2.5. Support vector machines . . . . . . . . . . . 2.5.1 Niet-lineaire classificatie . . . . . . . 2.5.2 Toepassing op collaborative filtering 2.6. Regelgebaseerde systemen . . . . . . . . . . 2.7. Clustering . . . . . . . . . . . . . . . . . . . 2.8. Opvangen van ontbrekende waarden . . . . . 2.9. Conclusie . . . . . . . . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . .

3. Architectuur 15 3.1. Vereiste functionele attributen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2. Vereiste kwaliteitsattributen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.3. Lagen 3.3.1 3.3.2 3.3.3 3.3.4

. . . . . . . . . . . Databeheerlaag . Aanbevelingslaag Coördinatielaag . Frontendlaag . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

I

viii

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

16 18 18 19 19

4. Implementatie 4.1. Gebruikte technologieën . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Programmeertaal en standaardbibliotheek . . . . . . . . . . . . . 4.1.2 Databankbeheersysteem . . . . . . . . . . . . . . . . . . . . . . . 4.2. Voorbereiding van data . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3. Genereren van aanbevelingen . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Aanbeveling met gelijkaardigheidsmodelgebaseerde aanbevelers . 4.3.2 Collaborative filtering . . . . . . . . . . . . . . . . . . . . . . . . 4.3.3 Content-based filtering . . . . . . . . . . . . . . . . . . . . . . . . 4.3.4 Audience-based filtering . . . . . . . . . . . . . . . . . . . . . . . 4.4. Databeheer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5. Coördinatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6. Frontend . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

21 21 21 22 22 24 25 26 27 28 30 31 31

5. Evaluatie 5.1. Accuraatheid . . . . . . . . . . . . . . . . . . . 5.1.1 Accuraatheid van voorspellingen . . . 5.1.2 Accuraatheid van aanbevelingen . . . . 5.1.3 Invloed van aantal vergeleken objecten 5.2. Uitvoeringssnelheid . . . . . . . . . . . . . . . 5.3. Parameters . . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

33 33 33 34 39 39 43

6. Mogelijke uitbreidingen en conclusie 6.1. Conclusie . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2. Support vector machines voor audience-based filtering 6.3. Betere manier van vergelijken van distributies . . . . . 6.4. Combineren van impliciete en expliciete ratings . . . . 6.5. Andere manieren van evalueren . . . . . . . . . . . . . 6.6. Betere verwerking van impliciete ratings . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

45 45 45 46 46 47 47

. . . . . .

. . . . . .

. . . . . .

. . . . . .

A. Inhoud van de cd-rom

49

Verklarende woordenlijst

50

Bibliografie

51

Lijst van figuren

54

Lijst van tabellen

55

I

LIJST VAN AFKORTINGEN

ABF CBF CF HTTP JSON kNN LSH LSI PCA PHP PLSI PMF REST RPC SOAP SVD SVM SQL XML

Audience-Based Filtering Content-Based Filtering Collaborative Filtering Hypertext Transport Protocol JavaScript Object Notation k-Nearest Neighbour Locality-Sensitive Hashing Latent Semantic Indexing Principal Component Analysis PHP: Hypertext Preprocessor Probabilistic Latent Semantic Indexing Probabilistic Matrix Factorization Representational State Transfer Remote Procedure Call Simple Object Access Protocol Singular Value Decomposition Support Vector Machine Structured Query Language Extensible Markup Language

ix

I

LIJST VAN SYMBOLEN

#X κ i I Iu IU Nu p r ru s u U x ˆ x ¯

Aantal elementen in de set X Normalisatiefactor Object (item) Set van objecten Set van objecten waarvoor gebruiker u een rating heeft Set van objecten waarvoor de gebruikers in U een rating hebben Buren (neighbours) van gebruiker u Geparametriseerde exponent Rating Rating voor gebruiker u Gelijkaardigheid (similarity) Gebruiker (user) Set van gebruikers Voorspelling voor de waarde van x Gemiddelde waarde van x

x

I

1

1. INLEIDING

1.1. Situering Online sociaalnetwerksites zijn in de voorbije jaren uitgegroeid tot een enorm succes. Op dergelijke sites kunnen gebruikers een profiel aanmaken en dit koppelen met profielen van vrienden in hun sociaal netwerk. De populairste sociaalnetwerksites hebben op dit moment enkele honderd miljoenen actieve gebruikers, en het aantal gebruikers dat ingeschreven is op zulke sites blijft snel stijgen. Twee bekende voorbeelden van sociaalnetwerksites zijn Facebook1 en Netlog2 . De sociaalnetwerksites van tegenwoordig evolueren geleidelijk van een profielsite naar een site waarop er steeds meer functionaliteit onder de vorm van applicaties ter beschikking gesteld wordt. Ook spellen zijn een belangrijk aspect geworden van deze websites. Deze sociaalnetwerksites bewaren grote hoeveelheden aan informatie over gebruikers en hun gedrag op deze sites. Deze informatie kan gebruikt worden om de site op een geautomatiseerde manier te personaliseren dus beter af te stemmen op de gebruiker.

1.2. Probleemstelling Door het sterk stijgend aanbod van diensten zoals applicaties en spellen wordt het voor gebruikers steeds minder eenvoudig om relevante functionaliteit te vinden. Gebruikers moeten handmatig naar mogelijk interessante zaken zoeken of aanbevelingen vragen aan vrienden. Dit proces is echter tijdrovend en niet erg accuraat. Een probleem is dat gebruikers niet noodzakelijk dezelfde smaak hebben als hun vrienden. Het zoeken naar aanbevelingen in een vriendenkring is dus niet noodzakelijk een goed idee. Bijvoorbeeld: een gebruiker die graag real-time strategy-spellen speelt, krijgt misschien best geen aanbevelingen van vrienden die uitsluitend turn-based strategy-spellen spelen. Op sociaalnetwerksites zijn games een bijzaak: het hoofddoel van dergelijke sites is niet het aanbieden van spellen, maar het opbouwen van sociale relaties. Dit heeft een zekere impact op het gedrag van gebruikers, en dus ook op de data die door het systeem gebruikt zal worden. Gebruikers gedragen zich immers anders op een sociaalnetwerksite dan op een spelletjes-site. 1 2

http://facebook.com/ http://netlog.com/

Hoofdstuk 1: Inleiding I 2

1.3. Doelstelling Het doel van deze masterproef is om een systeem te ontwikkelen dat automatisch aanbevelingen voor relevante functionaliteit op de sociaalnetwerksite kan aanbieden voor elke gebruiker. Deze aanbevelingen moeten nuttig en bijgevolg accuraat zijn voor de gebruiker. De focus van deze thesis ligt op het aanbevelen van spellen, maar het systeem moet universeel toepasbaar zijn. Het aanbevelen van applicaties moet bijvoorbeeld ook mogelijk zijn.

1.4. Samenwerking met Netlog In het kader van de masterproef werd samengewerkt met de sociaalnetwerksite Netlog. Het is de bedoeling dat het systeem dat als deel van deze masterproef ontwikkeld wordt, kan ingezet worden voor Netlog. De evaluatie van het systeem zal ook gebeuren aan de hand van data die door Netlog ter beschikking gesteld wordt. Netlog is een sociaalnetwerksite die zich hoofdzakelijk op de Europese markt richt. Met meer dan 64 miljoen leden [1] is Netlog algemeen gezien de grootste speler op Europees vlak. Netlog richt zich hoofdzakelijk op jongeren tussen 14 en 24 jaar.

1.5. Gebruiksvoorbeelden Deze sectie geeft enkele voorbeelden van gebruik van het systeem (use cases). Aangezien het systeem qua aangeboden functionaliteit vrij beperkt zal zijn, zijn hier slechts een klein aantal voorbeelden opgenomen. • Een gebruiker bezoekt een sociaalnetwerksite voor de eerste keer. Nadat hij/zij zich geregistreerd heeft, zal de gebruiker zijn profiel beginnen personaliseren door zijn persoonlijke gegevens in te vullen en door diensten te gebruiken. In deze beginsituatie zal het systeem nog niet genoeg informatie hebben om aanbevelingen te maken. • Een gebruiker met een bestaand profiel komt terug op een sociaalnetwerksite. Als deze gebruiker zijn profiel reeds gepersonaliseerd heeft, en indien hij/zij reeds een aantal diensten gebruikt heeft, zal het systeem genoeg informatie hebben om aanbevelingen te maken. Deze aanbevelingen zullen op relevante plaatsen aan de gebruiker getoond worden.

I

3

2. TECHNOLOGIESTUDIE

In dit hoofdstuk worden enkele technieken besproken die men kan gebruiken om een aanbevelingssysteem te bouwen. De voor- en nadelen van deze technieken zullen vergeleken worden, en er zal op basis van deze vergelijkingen een keuze gemaakt worden welke technologieën er gebruikt zullen worden in de implementatie. Het systeem moet in staat zijn om voor een zeer groot aantal gebruikers relevante diensten aan te raden. De door het systeem aangeraden diensten moeten nuttig zijn voor de gebruiker, en bovendien moet het systeem zelfs bij grote datasets nog steeds performant zijn en in ware tijd gebruikt kunnen worden. Er werd onderzoek gedaan naar verscheidene technologieën en hun eigenschappen op vlak van schaalbaarheid, uitvoeringssnelheid en accuraatheid werden vergeleken.

2.1. Gelijkaardigheidsmetrieken Er kan gebruik gemaakt worden van verscheidene metrieken om te bepalen hoe gelijkaardig twee punten in een vectorruimte zijn. Zulke metrieken zullen een waarde tussen 0 en 1 afleveren, met 0 corresponderend met niet gelijkaardig en 1 met volledig gelijkaardig. Deze sectie beschrijft een aantal van deze metrieken. De Euclidean distance score gebruikt de euclidische afstand tussen twee vectoren. Een grotere afstand komt overeen met een kleinere score en een kleinere afstand komt overeen met een grotere score. De score wordt van de afstand afgeleid zodat de score een getal tussen 0 en 1 wordt, waarbij grotere waarden een grotere correlatie aanduiden. De formule is

se (X, Y ) = 1+

√∑

1 n i=1 (Xi

− Yi )2

De Pearson correlation score [2] is een indicatie van de lineaire afhankelijkheid tussen twee vectoren. Twee lineair afhankelijke vectoren hebben een correlatie van 1; twee onafhankelijke vectoren hebben een correlatie van -1. Om een waarde in het [0, 1]-interval te bekomen, moet de correlatie dus eerst getransformeerd worden. Deze score presteert beter dan de Euclidean distance score voor data die niet genormaliseerd is. De formule is

Hoofdstuk 2: Technologiestudie I 4

∑n

− X)(Yi − Y ) √∑ n 2 2 (X − X) i i=1 i=1 (Yi − Y )

sp (X, Y ) = √∑ n

i=1 (Xi

De cosinusgelijkaardigheid (cosine similarity) [2] maakt gebruik van de hoek tussen twee vectoren. Net zoals de Pearson correlation score presteert deze score beter dan de Euclidean distance score op nietgenormaliseerde data. De formule is

sc (X, Y ) =

X ·Y ∥X∥∥Y ∥

De aangepaste cosinusgelijkaardigheid (adjusted cosine similarity) [2] is een aanpassing van de Pearson correlation score die betere resultaten geeft voor item-based collaborative filtering. Bij het berekenen van de gelijkaardigheid van twee objecten bij item-based collaborative filtering correspondeert elke rij met een andere gebruiker. De aangepaste cosinusgelijkaardigheid zorgt dat de gemiddelde rating van de gebruiker van elke rij afgetrokken wordt om de invloed van verschillend rating-gedrag te minimaliseren. De formule is ∑n

− rui )(Yi − rui ) √ ∑n 2 2 i=1 (Xi − rui ) i=1 (Yi − rui )

sac (X, Y ) = √∑n

i=1 (Xi

De Jaccard-coëfficiënt berekent de gelijkaardigheid tussen twee sets (niet vectoren) door de grootte van de doorsnede te delen door de grootte van de unie. De formule is

sj (X, Y ) =

|X ∩ Y | |X ∪ Y |

De Tanimoto-coëfficiënt is een uitbreiding van de Jaccard-coëfficiënt die werkt op binaire vectoren in plaats van sets. De formule is

st (X, Y ) =

X ·Y ∥X∥2 + ∥Y ∥2 − X · Y

2.2. Collaborative filtering Collaborative filtering [3] komt neer op het automatiseren van mond-tot-mondreclame. Aanbevelingen voor een actieve gebruiker worden gehaald uit objecten die goed bevonden werken door gebruikers met een gelijkaardige smaak, maar die nog niet door de actieve gebruiker gekend zijn. Deze techniek wordt gebruikt voor aanbevelingen te maken op sites zoals Last.fm en Amazon.com [4]. Er zijn twee manieren waarop collaborative filtering gebruikt kan worden [5]. De geheugengebaseerde (memory-based) technieken hebben geen trainingsfase nodig, en berekenen aanbevelingen


rechtstreeks uit de dataset. De modelgebaseerde (model-based) technieken bouwen eerst een model op dat vervolgens gebruikt kan worden om sneller en/of accurater voorspellingen te maken. Geheugengebaseerde technieken zijn slecht schaalbaar aangezien het zoeken van buren lineair is in het aantal gebruikers. Bovendien kunnen ze niet goed overweg met ijle data (data waarvan het merendeel van de elementen niet gekend is): gebruikers worden voorgesteld door vectoren waarvan de elementen overeenstemmen met de ratings die ze aan objecten gegeven hebben, maar aangezien gebruikers vaak slechts van een zeer kleine subset van alle objecten gebruik maken, zullen deze vectoren ijl zijn. Modelgebaseerde technieken zijn performanter dan geheugengebaseerde technieken, zijn beter schaalbaar en kunnen ook beter overweg met ijle data. De modellen voor modelgebaseerde aanbevelers moeten echter eerst opgebouwd worden, wat tijdrovend is (enkele minuten tot enkele uren) en bijgevolg offline moet gebeuren [3, 2]. Collaborative filtering-technieken maken op zichzelf geen gebruik van demografische data, zoals leeftijd en geslacht. Het is echter wel mogelijk om hybride algoritmes te bouwen waarbij verschillende algoritmes samenwerken. De deelresultaten kunnen op verschillende manieren verkregen worden: door gewichten toe te kennen aan de deelresultaten, door de deelresultaten te mengen, door de eerste set van deelresultaten te laten verbeteren door een tweede algoritme, etc [6]. Een mogelijk nadeel van collaborative filtering is dat het voor een terugkoppelingseffect kan zorgen. Collaborative filtering maakt immers gebruik van het gedrag van gebruikers om aanbevelingen te genereren; wanneer gebruikers effectief ingaan op deze aanbevelingen, zal het gedrag hierdoor versterkt worden. Dit effect is niet noodzakelijk wenselijk, en dus kan het nuttig zijn om collaborative filtering te combineren met andere technieken om de invloed van dit effect te reduceren. Er bestaan verscheidene concrete collaborative filtering-technieken. In de volgende secties zullen enkele van deze technieken samen met hun voor- en nadelen toegelicht worden.

2.2.1. User-based collaborative filtering User-based collaborative filtering is een eenvoudige en naïeve geheugengebaseerde collaborative filtering-techniek. Om een voorspelling voor een bepaalde gebruiker u en een bepaald object i te maken, wordt bij deze techniek eerst de buren Nu van u gezocht. Uit de collectie van objecten INu waarvoor minstens één buur een rating geven heeft, worden de objecten gekozen waarvoor u nog geen rating heeft geven. Voor elk van de resulterende objecten wordt vervolgens een voorspelling van de rating gemaakt aan de hand van de ratings van de buren van dit object en de gelijkaardigheid van de buren van u. De formule is \ r(u, i) = r(u) + κ

∑

( ) s(u, u′ ) · r(u′ , i) − r(u′ )

u′ ∈U,u′ ̸=u

\ Hier is r(u, i) de voorspelling voor de actieve gebruiker u en het object i. r(u) en r(u′ ) zijn de gemiddelde ratings van respectievelijk gebruikers u en u′ . s(u, u′ ) is een gewicht dat de gelijkaardigheid tussen de actieve gebruiker u en de gebruiker u′ uitdrukt. r(u′ , i) is de rating van gebruiker u′ voor object i. κ is een normalisatiefactor die ervoor zorgt dat de gewichten tot 1 sommeren. Merk op


dat er in deze formule gebruik gemaakt wordt van de gelijkaardigheid tussen gebruikers, s(u, u′ ); dit is typisch aan user-based collaborative filtering. Aangezien user-based collaborative filtering een geheugengebaseerde techniek is, zal deze techniek slecht schalen bij zeer grote hoeveelheden van gebruikers. De complexiteit van een aanbeveling is O(#U #I) aangezien bij het maken van aanbevelingen voor een gebruiker naar de buren van deze gebruiker gezocht moet worden (O(#U )), en per kandidaatbuur moet de gelijkaardigheid tussen deze kandidaatbuur en de gebruiker berekend worden (O(#I)).

2.2.2. Item-based collaborative filtering Item-based collaborative filtering is een modelgebaseerde techniek waarbij de gelijkaardigheid tussen twee objecten gebruikt wordt [2]. Een objectpaar zal een hoge waarde toegewezen krijgen wanneer gebruikers van het ene object ook het andere object gebruiken, en zal een lage waarde toegewezen krijgen wanneer gebruikers van het ene object het andere object niet of weinig gebruiken. Om tot een gelijkaardigheid voor een objectpaar te komen, worden eerst de gebruikers gezocht die aan beide objecten een rating gegeven hebben. Vervolgens wordt voor elk van deze twee objecten een vector met ratings van deze gebruikers opgesteld. De uiteindelijke gelijkaardigheid van deze twee objecten is dan de gelijkaardigheid van deze twee vectoren. De gelijkaardigheid kan berekend worden aan de hand van de metrieken beschreven in Sectie 2.1; vaak zal de Pearson-correlatie of de aangepaste cosinusgelijkaardigheid gebruikt worden. Een voorbeeldmatrix van gelijkaardigheden is terug te vinden in Tabel 2.1. Om aan de hand van een model aanbevelingen voor een bepaalde gebruiker te maken, worden voor alle objecten een voorspelling van de rating voor deze gebruiker gemaakt. De voorspelling voor een bepaalde gebruiker en een bepaald object is het gewogen gemiddelde van de ratings van alle objecten waarvoor deze gebruiker een rating heeft, waarbij de gewichten gelijk genomen worden aan de gelijkaardigheden van elk van deze objecten. In formulevorm: ∑ \ r(u, i) =

i′ ∈Iu

s(i, i′ ) · r(u, i′ ) ∑

s(i, i′ )

i′ ∈Iu

\ Hier is r(u, i) de voorspelde rating voor gebruiker u en object i. s(i, i′ ) is de gelijkaardigheid tussen de objecten i en i′ . De sommaties lopen over alle objecten i′ ∈ Iu waarvoor de gebruiker u een rating gegeven heeft. Item-based collaborative filtering schaalt veel beter dan user-based collaborative filtering omdat de complexiteit voor het maken van een aanbeveling slechts O(#I 2 ) in plaats van O(#U #I) is en omdat #I ≪ #U . Het aanmaken van een model is O(#U #I 2 ): voor elk objectpaar moet twee vectoren met gebruikersratings vergeleken worden. Modellen voor item-based collaborative filtering kunnen incrementeel aangepast worden [7], wat de schaalbaarheid ook ten goede komt. Merk op dat deze techniek geen problemen heeft met ijlheid van vectoren: zowel bij het aanmaken van het model als het maken van aanbevelingen komen er geen mogelijk ijle vectoren te pas.

Connect Four

City Sim

Transport Sim

Tetris Connect Four City Sim Transport Sim

Tetris


0,8 0,3 0,3

R 0,1 0,2

R R 0,8

R R R -

Tabel 2.1: Een voorbeeld van een matrix zoals deze gebruikt zou kunnen worden in een item-based collaborative filtering-techniek. “-” duidt op een nutteloze waarde (verband tussen object en zichzelf); “R” duidt op een redundante waarde.

2.2.3. Andere technieken Voor collaborative filtering bestaan er meer technieken dan deze die hierboven vermeld werden. Deze sectie licht enkele andere technieken toe. Slope One De Slope One collaborative filtering-technieken [8] zijn modelgebaseerde technieken waarbij predictors van de vorm f (x) = x+b gebruikt worden. Slope one-algoritmes zijn eenvoudig te implementeren, hebben goede uitvoeringssnelheid en accuraatheid, en hun modellen kunnen in ware tijd aangepast worden. Latent Semantic Indexing De Latent Semantic Indexing-techniek gebruikt singuliere waardendecompositie (singular value decomposition, SVD) om het aantal dimensies in de gebruiker-object-matrix te reduceren [9]. Een m × n-matrix M wordt hierbij gefactoriseerd tot M = U · S · V T , waarbij S een m × n-matrix is die de singuliere waarden, gesorteerd in aflopende volgorde op de diagonaal bevat, en elders 0. Uit de matrix S kan nu een nieuwe matrix S ′ afgeleid worden, waarbij S ′ een k × k-matrix is die enkel de k eerste kolommen en k eerste rijen van S bevat. Deze S ′ is zo dat de Frobeniusnorm1 tussen S en S ′ geminimaliseerd wordt. Singuliere waardendecompositie wordt hier dus gebruikt voor principal component analysis. De matrices U ′ en V ′T behouden dan de k eerste kolommen respectievelijk k eerste rijen. U ′ heeft nu nog steeds alle rijen van U , maar slechts k kolommen; V ′T heeft alle kolommen van V T maar slechts k rijen. Dit algemeen schema is geïllustreerd in Figuur 2.1.

De matrices U ′ en V ′ kunnen nu gebruikt worden om efficiënter buren te zoeken. De dimensiereductie heeft als gevolg dat deze matrices U ′ en V ′ minder ruis bevatten dan de originele matrices U en V , en bijgevolg accurater zijn. Het factorizeren van deze matrix is echter niet goed schaalbaar. In [10] wordt probabilistic latent semantic indexing (PLSI) geïntroduceerd, een variant op SVD-gebaseerde LSI die aanzienlijk sneller is. [11] bespreekt probabilistic matrix factoring (PMF), een techniek die goed schaalt en bovendien goed overweg kan met ijle data. 1

de vierkantswortel van de som van de kwadraten van de singuliere waarden


=

×

×

Figuur 2.1: Algemeen schema van SVD. De rechthoeken stellen respectievelijk de matrices M , U , S en V T voor. Onder de gestippelde lijn komen enkel nullen voor. De grijsgekleurde gebieden stellen de gereduceerde matrices U ′ , S ′ en V ′T voor.

2.3. Content-based filtering Content-based filtering [12] is een techniek waarbij objecten aangeraden worden aan een gebruiker, gebaseerd op de beschrijving van deze objecten en een profiel van de interesses van de gebruiker. Bij content-based filtering wordt er geen rekening gehouden met de interesses van buren of vrienden van gebruikers. Content-based filtering kan geïmplementeerd worden aan de hand van een gelijkaardigheidsmodel. De objecteigenschappen waar content-based filtering gebruik van kan maken, hangen af van het type object. In vele gevallen zullen eigenschappen zoals genre, de categorie, de trefwoorden, … gebruikt worden om gelijkaardigheden tussen objecten te berekenen en dus het gelijkaardigheidsmodel op te stellen. De gelijkaardigheid tussen twee objecten kan bepaald worden aan de hand van een gelijkaardigheidsmetrieken. Sectie 2.1 beschrijft een aantal mogelijke metrieken. Het maken van een schatting van de rating voor een gegeven gebruiker en object, en dus het maken van aanbevelingen, gebeurt op dezelfde manier als bij item-based collaborative filtering.

2.4. k-Nearest Neighbour Het vinden van k buren van punten in een bepaalde ruimte is het oplossen van het k-Nearest Neighbour-probleem [13, 14]. Het oplossen van dit probleem is nodig voor de implementatie van userbased collaborative filtering. Een nadeel van k-Nearest Neighbour is dat het niet goed overweg kan met ijle data [14]. Bij datasets met zeer veel ontbrekende informatie zal kNN er niet in slagen om goede buren te vinden. Een naïeve manier om dit probleem op te lossen, is door het gegeven punt met alle andere punten in de ruimte te vergelijken. De k dichtste buren worden steeds bijgehouden. Wanneer een buur gevonden wordt die dichter is dan minstens één buur uit de lijst, wordt de oude buur vervangen door de nieuwe buur. Dit leidt tot een complexiteit O(n) met n het aantal punten in de vectorruimte. kd-bomen (k-dimensionale bomen) zijn datastructuren die gebruikt worden om punten in een kdimensionale ruimte op te slaan. Met kd-bomen kan er efficiënt gezocht worden in een dergelijke


a

b c

Figuur 2.2: Voorbeeld van hypervlakken in SVMs

ruimte met k dimensies; het vinden van buren van een gegeven punt is een voorbeeld van een dergelijke zoekoperatie. Het opbouwen van een kd-boom heeft als complexiteit O(n log2 n). Het zoeken naar buren kan beperkt worden tot de set van vrienden of de set van vrienden-vanvrienden. Dit verkleint de zoekruimte en maakt het zoeken dus minder intensief. De accuraatheid kan hierdoor echter dalen; er wordt in een veel kleinere collectie van punten gezocht, en hierdoor kan de kans dat goede buren gevonden worden, sterk dalen.

2.5. Support vector machines Support vector machines (SVMs) is een categorie van dataclassificatiemethodes waarbij twee sets van vectoren gescheiden worden door tussen deze sets een hypervlak met maximale marge te construeren. Het is een method die van leren onder toezicht (supervised learning) gebruik maakt: vooralleer de support vector machine bruikbaar is, moeten de machine getraind wordt met een aantal trainingsvoorbeelden. Het scheidend hypervlak kan verschillende vormen aannemen naargelang het aantal dimensies van de ruimte waarin de vectoren zich bevinden. In een driedimensionale ruimte zal dit hypervlak een gewoon vlak zijn; in een tweedimensionale ruimte zal het hier echter om een eenvoudige rechte gaan. Dit hypervlak is zo gelegen dat het de afstand tussen de twee sets van vectoren maximaliseert. Figuur 2.2 geeft een voorbeeld van zulke hypervlakken in een tweedimensionale ruimte. Hypervlak a scheidt de twee sets van vectoren, maar de marge tussen beide sets is niet maximaal; hypervlak b scheidt de twee sets met een maximale marge; hypervlak c scheidt de sets niet.

2.5.1. Niet-lineaire classificatie Support vector machines op zichzelf enkel in staat om lineaire classificatie uit te voeren. Met behulp van de zogenaamde kernel trick kunnen support vector machines wel gebruikt worden voor nietlineaire classificatie. Door middel van een kernel worden alle vectoren afgebeeld in een hogerdimensionale getransformeerde ruimte. In deze getransformeerde ruimte wordt dan de lineaire


(a)

(b)

Figuur 2.3: Voorbeeld van het gebruik van de kernel trick. De oorspronkelijke data is weergegeven in (a); de getransformeerde data samen met het scheidend hypervlak in (b)

classificatie uitgevoerd. Op deze manier wordt lineaire classificatie in de nieuwe ruimte equivalent met niet-lineaire classificatie in de originele ruimte. Figuur 2.3 toont een voorbeeld van een dergelijke kernel trick. Hier worden de twee sets van vectoren aangeduid door zwarte of witte punten. In dit voorbeeld wordt de oorspronkelijke ééndimensionale data (deelfiguur a) afgebeeld op een tweedimensionale ruimte aan de hand van de vergelijking (x′ , y ′ ) = (x, |x|) waarbij (x′ , y ′ ) de nieuwe coördinaat is en (x) de oude coordinaat. Door deze transformatie wordt de oorspronkelijke set van vectoren, die niet lineair classificeerbaar zijn, plots wel classificeerbaar in de hoger-dimensionale ruimte. Deelfiguur b toont de getransformeerde vectoren in de hoger-dimensionale ruimte, samen met het scheidend hypervlak.

2.5.2. Toepassing op collaborative filtering Collaborative filtering kan opgevat worden als een classificatieprobleem: gegeven een bepaalde dienst, bepaal of deze relevant is voor de actieve gebruiker. Support vector machines kunnen gebruikt worden om een dergelijk classificatieprobleem op te lossen. Dit kan op twee manieren [15]: per gebruiker een SVM die beslist of een bepaalde dienst relevant is voor deze gebruiker, of per dienst een SVM die beslist of een bepaalde gebruiker van deze dienst gebruik zou willen maken. Figuur 2.4 illustreert deze twee aanpakken. Bij de eerste manier worden alle reeds gebruikte objecten in een ruimte ondergebracht waarbij elke dimensie één ander object voorstelt. In deze ruimte worden dan vectoren die gebruikersratings bevatten, ondergebracht. Elke vector in deze ruimte is voorzien van een binair label dat de categorie voorstelt. De vectoren worden dan door een support vector machine geclassificeerd, zodat voor nieuwe objecten in deze ruimte een voorspelling kan gemaakt worden of een gegeven gebruiker mogelijk gebruik zou willen maken van deze dienst of niet. Bij de tweede manier worden de rollen omgedraaid, en wordt er per gebruiker een support vector machine gebruikt. Elke dimensie in de ruimte komt dan overeen met een gebruiker. De objecten worden als vectoren in deze ruimte ondergebracht. Deze vectoren worden dan op dezelfde manier geclassificeerd om tot een voorspelling te komen.


object 1

gebruiker 1 u3 u2

u4

i4

i3 i1

u1

i2 object 2

(a)

gebruiker 2 (b)

Figuur 2.4: De twee manieren waarop een support vector machine gebruikt kan worden voor collaborative filtering: (a) per object een beslisser, of (b) per gebruiker een beslisser.

Er zijn twee nadelen aan het gebruik van support vector machines voor collaborative filtering. Ten eerste is de ijlheid van de gebruikers-objecten-matrix een probleem dat de accuraatheid van de aanbevelingen kan doen dalen [16]; punten zullen niet accuraat in de vectorruimte geplaatst kunnen worden omwille van ontbrekende informatie. Ten tweede presteert een standaard-SVM niet goed bij collaborative filtering bij een grote imbalans tussen verschillende categoriëen: wanneer slechts een kleine subset van gebruikers geïnteresseerd zijn voor een object, m.a.w. wanneer een grote meerderheid van gebruikers zich niet interesseert voor een object, zal een standaard support vector machine niet accuraat zijn [17].

2.6. Regelgebaseerde systemen Een regelgebaseerd systeem (rule based (expert) system, RBS) neemt beslissingen aan de hand van voorgedefinieerde regels. Zulke regels kunnen aan elkaar gekoppeld zijn en zo een beslissingsboom vormen. Deze boom zal dan voor een bepaalde invoer vanuit de wortel een bepaald pad volgen tot aan een bepaald blad. Een regel uit een regelgebaseerd systeem bestaat uit een conditie en een actie; wanneer de conditie waar is, zal de actie uitgevoerd worden. Regels uit een regelgebaseerd systeem kunnen handmatig opgesteld worden. Een voorbeeld van een dergelijke regel: IF user.uses(photo_service) AND NOT user.uses(video_service) THEN user.recommend(video_service)

Alhoewel het eenvoudig is om regels te schrijven, is het maken van een set van regels in een complex systeem zeker niet eenvoudig om ervoor te zorgen dat alle relevante gevallen correct verwerkt worden door het regelgebaseerd systeem. Er zijn twee mogelijke toepassingen voor regelgebaseerde systemen in de context van deze masterproef. Ten eerste kunnen regelgebaseerde systemen gebruikt worden om de zoekruimte te beperken door informatie die zeker niet relevant is weg te filteren. Bijvoorbeeld: als het systeem een aantal race-games kent, dan kan het systeem beslissen om aan een bepaalde gebruiker geen en-


kel race-spel aan te bevelen als deze gebruiker al een negatieve rating gegeven heeft aan minstens één race-spel. Op deze manier kan vermeden worden dat er onnodige voorspellingen van ratings gemaakt worden voor spellen die waarschijnlijk toch niet relevant zijn. Ten tweede kunnen ze gebruikt worden om te beslissen of een bepaalde dienst voor een bepaalde gebruiker al dan niet relevant is. Bijvoorbeeld: als het systeem de twee objecten Tetris I en Tetris II kent, kan er een regel geschreven worden die zegt dat het systeem het spel Tetris II moet aanbevelen aan een gebruiker als deze gebruiker een hoge rating gegeven heeft aan Tetris I en als deze gebruiker het spel Tetris II nog niet gespeeld heeft.

2.7. Clustering Clustering is het zoeken naar groepen van gelijkaardige zaken. Het is een vorm van unsupervised learning. Terwijl supervised learning-methoden getraind worden met voorbeeld-invoer en -uitvoer, is dit bij unsupervised learning-methoden niet het geval. In de context van aanbevelingssystemen kan dit gebruikt worden om de zoekruimte te verkleinen: in plaats van te zoeken tussen alle mogelijke punten in een ruimte, kan er gezocht worden tussen alle punten in een bepaalde cluster in die ruimte. Clustering kan op verschillende manieren gebeuren. Een aantal mogelijke clusteringstechnieken worden hieronder uitgelegd. Hiërarchisch clusteren Deze manier werkt door steeds opnieuw de twee meest gelijkaardige groepen samen te nemen tot één groep. Voordat het echte clusteren begint, wordt elk object toegekend aan een unieke groep. Het algoritme stopt wanneer er maar één groep overblijft.

Het resultaat van hiërarchisch clusteren is een boom, die opgebroken kan worden in verschillende clusters. Het aantal clusters ligt dus initieel niet vast. Een nadeel van deze techniek is dat het computationeel zeer intensief is. K-means-clusteren Dit werkt door een gegeven aantal punten, centroids genaamd, willekeurig te plaatsen en alle te clusteren punten toe te kennen aan hun dichtstbijzijnde centroid. Bij elke stap worden deze centroids verplaatst naar het gemiddelde van de aan hun toegekende punten, en worden alle punten terug aan de dichtsbijzijnde centroid toegekend. Dit proces loopt tot de assignaties van punten aan centroids niet meer veranderen.

Het resultaat van deze manier van clusteren is een set van k clusters, waarbij k gelijk is aan het aantal centroids. In tegenstelling tot hiërarchisch clusteren ligt het aantal clusters op voorhand vast. Deze manier van clusteren is significant sneller dan hiërarchisch clusteren. MinHashing Dit is een probabilistische hashing-techniek, ook wel gekend onder de naam Simhashing, waarbij twee gebruikers aan dezelfde cluster worden toegekend met een waarschijnlijkheid die proportioneel is aan de mate van overlap tussen de sets van objecten waarvoor de gebruikers een rating hebben toegekend [18, 19]. De gelijkaardigheid tussen twee gebruikers is de gelijkaardigheid van de sets, gebruik makend van de Jaccard-coëfficiënt, van objecten waarvoor ze een rating hebben voorzien. Voor een zeer groot aantal objecten is deze techniek echter niet schaalbaar.

Hoofdstuk 2: Technologiestudie I 13 Locality-Sensitive Hashing Deze techniek is een probabilistische hashing-techniek waarbij objecten die dichter bij elkaar liggen een grotere kans hebben om in dezelfde emmer (bucket) terecht te komen dan objecten die verder van elkaar liggen [20, 19]. Deze clustering-techniek maakt dus gebruik van voorgedefinieerde clusters.

In [21] wordt een clustering-techniek voorgesteld waarbij objecten worden afgebeeld op hun genre, om zo het aantal dimensies van de gebruikers-objecten-matrix te reduceren. Deze techniek vertoont dus gelijkenissen met content-based filtering. Uit alle ratings gegeven aan objecten uit een bepaald genre kan een rating voor dat specifiek genre afgeleid worden, waarop dan clustering kan toegepast worden.

2.8. Opvangen van ontbrekende waarden Zoals eerder vermeld, is de ijlheid van de gebruikers-objecten-matrix een probleem. Het berekenen van de gelijkaardigheid tussen twee vectoren wordt door ontbrekende data bemoeilijkt. Dit probleem kan op twee manieren opgelost worden. Ten eerste kan er gebruik gemaakt worden van een specifieke “null”-waarde. Dit is nuttig in het geval dat het ontbreken van data op zichzelf ook nuttige informatie is. Ten tweede kunnen de ontbrekende waarden automatisch ingevuld worden door middel van default voting [5]. De ontbrekende waarde wordt dan ingevuld met een standaardwaarde die overeenkomt met een neutrale rating zoals 0,5 of zelfs een licht negatieve rating. Deze manier van werken kan echter tot slechte resultaten leiden [16].

2.9. Conclusie Een classificatie van aanbevelingssystemen is weergegeven in Figuur 2.5. Er is besloten om eerst collaborative filtering te implementeren, omdat dit een techniek is die in veel gelijkaardige situaties toegepast wordt. Meer specifiek werd besloten om item-based collaborative filtering te implementeren, aangezien deze modelgebaseerde techniek aan de vereiste uitvoeringssnelheids- en accuraatheidseigenschappen voldoet. De andere collaborative filteringtechnologieën (latent semantic indexing aan de hand van singular value decomposition, support vector machines, probabilistic matrix factorisation, probabilistic latent semantic indexing, …) werden niet gekozen omdat deze problemen hebben met schaalbaarheid en/of hun gevoeligheid voor ijle data. Er werd ook gekozen om content-based filtering te implementeren, aangezien dit een technologie is die vanuit een volledig ander standpunt dan collaborative filtering vertrekt. Er zal een vergelijkende studie gemaakt worden tussen collaborative filtering en content-based filtering. Regelgebaseerde systemen werden niet gekozen omdat deze manier van werken niet zelflerend is en zeer veel manueel werk vraagt om een accuraat, goed werkend systeem te verkrijgen.


Aanradingssystemen

Content-based filtering

Collaborative filtering

Memorybased

User-based (naïef)

Model-based

User-based met kd-boom

Item-based

Met SVM

Met LSI/SVD

Slope One

Figuur 2.5: Classificatie van aanbevelingssystemen

Collaborative Filtering Content-based Filtering Regelgebaseerde systemen

Voordelen

Nadelen

Geen extra inspanning vereist Snel en accuraat Zelflerend

Werkt slechts goed bij veel data Terugkoppelingseffect

Eenvoudig te implementeren

Extra inspanningen vereist Niet zelflerend

Eenvoudig te implementeren Flexibel

Extra inspanningen vereist Mogelijk niet accuraat Niet zelflerend

Tabel 2.2: Voor- en nadelen van de besproken technieken

User-based User-based met kd-boom Item-based Slope One SVM-gebaseerd LSI/SVD-gebaseerd LSI/PMF-gebaseerd PLSI-gebaseerd

Model?

Incr?

IJl?

Compl A

Compl M

Nee Nee Ja Ja Ja Ja Ja Ja

nvt nvt Ja Ja Ja Nee Nee Nee

Slecht Slecht Goed Goed Slecht ? ? ?

O(#U #I) O(#U #I) O(#I 2 ) ? ? ? ? ?

nvt O(#U log2 #U ) O(#I 2 #U ) ? ? ? ? ?

Tabel 2.3: Vergelijking van verschillende Collaborative Filtering-technieken. “Model”: is de technologie modelgebaseerd is of niet? “Incr?”: is het model incrementeel aanpasbaar? “IJl?”: hoe goed wordt ijle data behandeld? “Compl A”: wat is de geschatte complexiteit van het aanmaken van aanbevelingen? “Compl M”: wat is de geschatte complexiteit van het herbouwen van het model?

I

15

3. ARCHITECTUUR

Dit hoofdstuk bespreekt de opbouw van het aanbevelingssysteem. Allereerst bespreken we de functionele en de niet-functionele kwaliteitsattributen. Daarna wordt elke component van het systeem afzondelijk toegelicht.

3.1. Vereiste functionele attributen Het systeem moet twee functies implementeren: a) het genereren van aanbevelingen, gegeven een bepaalde gebruikers-ID, en b) het herbouwen van modellen die er toe dienen om aanbevelingen snel te kunnen maken. Het voorspellen of schatten van de rating van een gegeven object voor een gegeven gebruiker is geen functionaliteit die van buitenaf gebruikt kan worden. Ze wordt wel intern gebruikt om aanbevelingen te maken. Hiervoor worden de objecten op aflopende voorspelde rating gerangschikt, en van de resulterende gesorteerde lijst worden dan de eerste elementen als aanbevelingen gebruikt.

3.2. Vereiste kwaliteitsattributen Accuraatheid Vanzelfsprekend is het belangrijk dat de aanbevolen objecten als positief worden ervaren door de gebruiker. Concreet betekent dit dat de gebruiker akkoord is met de gemaakte aanbevelingen. Het is dus wenselijk het aantal valse positieven minimaal te houden. Uitvoeringssnelheid De uitvoeringssnelheid is één van de belangrijkste attributen. Het systeem moet een real-time-karakter hebben: aanbevelingen moeten binnen een zeer kort tijdsbestek weergegeven kunnen worden, opdat webpagina’s met aanbevelingen voldoende snel door de server gegenereerd kunnen worden. Het systeem moet dezelfde uitvoeringssnelheideigenschappen blijven behouden wanneer er veel aanvragen tegelijkertijd binnenkomen. Het offline genereren van een model voor aanbevelingen kan nuttig zijn om de vereiste uitvoeringssnelheid te bereiken.

In [22] wordt aangetoond dat een responstijd van twee seconden of minder nodig is om het surfgedrag als vloeiend te ervaren. Aangezien het genereren van een webpagina bestaat uit het ophalen van de relevante data, het aanmaken van de aanbevelingen, het assembleren van de webpagina en uiteindelijk het versturen van de webpagina van de server naar de client is twee seconden een absolute bovengrens voor het aanmaken van aanbevelingen.

Hoofdstuk 3: Architectuur I 16 FRONTENDLAAG

COÖRDINATIELAAG

Client A

Client B

API B

Client C

API C

AANBEVELINGSLAAG

DATABEHEERLAAG

Rec A

Databron A

Coördinator

Databron B

Rec B

Databron C

Figuur 3.1: Overzicht van de verschillende lagen in de architectuur

Schaalbaarheid Het systeem moet voorbereid zijn op een steeds groeiend aantal parallelle aanvragen en een steeds groeiend aantal diensten die aangeraden kunnen worden. Hier gaat het hoofdzakelijk om horizontale schaalbaarheid: het aanbevelingssysteem moet zoveel mogelijk parallelliseerbaar en distribueerbaar zijn om aan deze eigenschap te voldoen. Aanpasbaarheid Nieuwe diensten moeten zeer eenvoudig geïntegreerd kunnen worden in het systeem. Dit moet op een manier kunnen die vereist dat er geen of een minimum aan aanpassingen aan de code moeten gebeuren. Verantwoordelijkheiden in het systeem moeten goed gescheiden zijn, zodat het eenvoudig is om nieuwe algoritmes toe te voegen of bestaande algoritmes te wijzigen met slechts een minimum van wijzigingen aan bestaande code. Interoperabiliteit Het systeem moet door alle sites waarop er diensten aangeboden worden en waar historische informatie over gebruikers bewaard wordt, gebruikt kunnen worden via een eenvoudige en vooraf gedefinieerde interface. De werking van het systeem zelf moet verborgen zijn en het moet zich dus als een zwarte doos gedragen.

3.3. Lagen Er werd gekozen voor een gelaagde architectuur om de modulariteit van het systeem te bevorderen. Figuur 3.1 illustreert de verschillende lagen in de architectuur. De interactiesequenties voor de twee vereiste functies, het aanmaken van aanbevelingen en het herbouwen van modellen, zijn geïllustreerd in het sequentiediagram in Figuur 3.2. In dit sequentiediagram komen de objecten waarmee gecommuniceerd wordt, overeen met de vier verschillende lagen in de architectuur. Merk op dat deze figuur sterk vereenvoudigd is: enkel de communicatie tussen de lagen onderling werd in de figuur opgenomen, en alhoewel de aanbevelers in de figuur slechts één keer de databron contacteren, zal dit in de praktijk veel vaker gebeuren. Het sequentiediagram voor het herbouwen van modellen is zeer gelijkaardig aan het sequentiediagram voor het maken van aanbevelingen, en is om die reden niet opgenomen als figuur.

HTTP-aanvraag (aanvraag)

HTTP-antwoord (aanbevelingen)

Gebruiker

aanbevelingen

bouw aanbevelingen

aanbevelingen

data

vraag nodige data

Aanbeveler

data

vraag nodige data

Databron

Figuur 3.2: Voorbeeldsequentiediagram dat het bouwen van aanbevelingen beschrijft. Dit diagram maakt bij wijze van voorbeeld gebruik van twee aanbevelers en een HTTP-frontend, maar meer of minder aanbevelers en andere frontends zijn mogelijk.

aanbevelingen

Aanbeveler

bouw aanbevelingen

Coördinator

bouw aanbevelingen

Frontend

Databron

Hoofdstuk 3: Architectuur I 17


3.3.1. Databeheerlaag De databeheerlaag is verantwoordelijk voor het opvragen en aanpassen van data uit databronnen, zoals SQL-gebaseerde databanken. In het overzicht van de verschillende lagen in de architectuur, Figuur 3.1, is de databeheerlaag de meest rechtse laag. De databeheerlaag zal enkel data aanpassen die door het systeem zelf gegenereerd is. Modeldata valt hier bijvoorbeeld onder. Data die van buitenaf aangeleverd wordt, zoals ratings en objecteigenschapsinformatie, zal door de databeheerlaag niet aangepast worden. De databeheerlaag zorgt er voor dat het opvragen en aanpassen van data op een uniforme manier kan gebeuren, onafhankelijk van de taal die gebruikt wordt om data op te vragen of aan te passen. Deze taal zal vaak SQL zijn, maar dit is geen vereiste. Data hoeft immers niet steeds uit een SQLdatabank te komen, maar kan bijvoorbeeld via een web service over het netwerk afgeleverd worden; in een dergelijk geval kan deze data bijvoorbeeld in XML of JSON gecodeerd zijn. Het cachen van data is ook een verantwoordelijkheid van de databeheerlaag. Data die vaak opgevraagd wordt of waarvan het opvragen kostelijk in termen van tijd is, kan gecached worden om de uitvoeringssnelheid van de databeheerlaag te verbeteren. Het cachen van data is volledig optioneel en het systeem voorziet geen functionaliteit voor het beheren van caches. De abstractie die door de databeheerlaag aangeboden wordt, kan ook aangewend worden bij het vereenvoudigen van de geautomatiseerde tests van de bovenliggende lagen. De abstractie laat toe om tijdens het testen de databronnen in de databeheerlaag te vervangen door test-stubs, zodat het systeem niet meer afhankelijk wordt van externe componenten zoals databankbeheersystemen. Dit komt de kwaliteit van de tests ten goede. Het beheren van de brondata zoals ratings en objecteigenschappen is niet de verantwoordelijkheid van de databronnen, en zelfs niet de verantwoordelijkheid van het systeem. Dergelijke data moet door een extern programma beheerd worden.

3.3.2. Aanbevelingslaag De aanbevelingslaag is verantwoordelijk voor het maken van de eigenlijke aanbevelingen. De aanbevelingslaag bestaat uit individuele aanbevelers, waarbij elke aanbeveler twee functies implementeert: a) het genereren van aanbevelingen, gegeven een bepaalde gebruikers-ID, en b) het herbouwen van de aanbevelersmodellen. Het maken van aanbevelingen kan op twee mogelijke tijdstippen gebeuren. Enerzijds kan dit gebeuren wanneer een gebruiker de aanbevelingen nodig heeft, m.a.w. wanneer de aanbevelingen op een site getoond moeten worden. Anderszijds kunnen anbevelingen in plaats van on-demand ook offline gegenereerd en opgeslagen worden, zodat ze later eenvoudig opgevraagd kunnen worden zonder het aanbevelingssysteem zelf aan te spreken. Aanbevelingen die on-demand gemaakt worden, kunnen ook enige tijd bijgehouden (gecached) worden om te verhinderen dat het aanbevelingssysteem onnodig veel aanbevelingen moet maken voor dezelfde gebruiker. Het herbouwen van modellen voor aanbevelers zal gebeuren op aanvraag van de beheerder van het systeem. Deze functie zal opgeroepen worden wanneer de data waarmee het model oorspronkelijk


is gebouwd, sterk verouderd is. Verouderde modellen brengen immers de kwaliteit van de aanbevelingen in het gedrang. Het herbouwen van het model kan ook nuttig of zelfs nodig zijn nadat nieuwe objecten aan het systeem toegevoegd worden. Indien nodig kan het herbouwen van modellen geautomatiseerd worden door bijvoorbeeld gebruik te maken van cron-jobs; het herbouwen kan gepland worden tijdens de daluren om optimaal van systeembronnen gebruik te maken. De ruwe data die gebruikt wordt door de aanbevelers wordt opgevraagd uit de onderliggende databeheerlaag. De aanbevelingslaag op zichzelf haalt geen data uit de database op. Elke aanbeveler heeft één of meer databronnen, waaruit data gehaald kan worden of waar data naartoe geschreven kan worden. Elke databron heeft een unieke functie: zo kan een bepaalde aanbeveler bijvoorbeeld een databron voor een interne database hebben waar model-data geschreven en gelezen kan worden, en een externe databron waarvan ruwe data gelezen kan worden. Als er aanbevelingen aan deze laag gevraagd worden, is de teruggegeven waarde een lijst van objecten, samen met hun voorspelde rating voor de gegeven gebruiker. Deze lijst is aflopend op voorspelde rating gesorteerd, zodat de objecten die bovenaan in deze lijst staan met de grootste waarschijnlijk goed zullen bevonden worden. De objecten met de hoogste voorspelde rating kunnen dan als effectieve aanbevelingen voor de gegeven gebruiker dienst doen.

3.3.3. Coördinatielaag De coördinatielaag spreekt de individuele aanbevelers uit de onderliggende aanbevelingslaag aan en aggregeert de aanbevelingen gegenereerd door deze aanbevelers. Figuur 3.1 illustreert de positie van de coördinatielaag ten opzichte van de andere lagen. De manier van aggregeren van de aanbevelingen uit de verschillende aanbevelers is configureerbaar gemaakt. Zo kan er bijvoorbeeld ingesteld worden hoeveel resultaten elke aanbeveler moet teruggeven, hoe de verschillende aanbevelingen gecombineerd moeten worden of hoe zwaar de resultaten van een bepaalde aanbeveler moeten doorwegen. De coördinator doet zich voor als een aanbeveler: de coördinator heeft dezelfde publieke functies als een aanbeveler. Het is dus eenvoudig om van een systeem met slechts één aanbeveler gebruik te maken; de coördinator van dit systeem zorgt er dan voor dat alle aanvragen en antwoorden direct naar die ene aanbeveler doorgesluisd worden.

3.3.4. Frontendlaag De frontendlaag is de bovenste laag. Deze laag bevat enerzijds functionaliteit voor het omzetten van inkomende aanvragen naar een uniform formaat dat bruikbaar is voor de onderliggende coordinatielaag, en anderzijds het omzetten van gegenereerde aanbevelingen naar een formaat dat bruikbaar is voor de client. De frontendlaag unificeert dus verschillende interfaces tot één enkele API, namelijk de API die door de onderliggende coördinatielaag aangeboden wordt. Inkomende aanvragen kunnen in verscheidene formaten voorkomen, zoals XML-RPC, JSON-RPC en SOAP. Rechtstreekse functieoproepen zijn ook mogelijk. Er is geen beperking op het soort protocols dat ondersteund wordt. De ondersteunde protocollen zijn bijvoorbeeld niet beperkt tot protocol-


len die bovenop HTTP draaien (alhoewel de voorgaande voorbeelden allemaal van HTTP gebruik kunnen maken); een commandline frontend is bijvoorbeeld ook mogelijk. Een frontend die van de commandline interface gebruik maakt, zal bijvoorbeeld aanvragen genereren gebaseerd op de argumenten die meegegeven zijn aan het programma; de ID van een gebruiker waarvoor aanbevelingen moeten gemaakt worden, is hier een voorbeeld van. Nadat deze argumenten geparsed zijn, zal de frontend de relevante functie(s) op de coördinator oproepen met de ingelezen argumenten. Wanneer de coördinator de berekende resultaten teruggeeft, zal deze output omgezet worden in een leesbare string en vervolgens uitgeprint worden op de standaarduitvoerstroom. Een andere mogelijke frontend is een frontend die zich als web-server voordoet en aanvragen in JSON-formaat kan ontvangen. Wanneer een dergelijke aanvraag binnenkomt, zal deze aanvraag geparsed worden en zullen de relevante functies op de coördinator opgeroepen worden. Nadat de coördinator geantwoord heeft, zal dit antwoord als JSON geformatteerd worden en vervolgens over het netwerk verstuurd worden.

I

21

4. IMPLEMENTATIE

Dit hoofdstuk beschrijft de implementatie van de verschillende componenten in het systeem. Eerst beschrijven we de gebruikte technologieën en vervolgens komen de individuele componenten van het systeem aan bod.

4.1. Gebruikte technologieën 4.1.1. Programmeertaal en standaardbibliotheek Als hoofdprogrammeertaal voor het systeem werd Objective-C (vaak afgekort tot Obj-C) gekozen. Deze taal is een objectgeoriënteerde en dynamisch getypeerde taal die een strikte superset van de gecompileerde programmeertaal C is. [23, 24] De keuze van programmeertaal werd genomen tussen Objective-C, de taal die mijn persoonlijke voorkeur wegdroeg, en PHP, de taal die door Netlog gebruikt wordt. PHP is een wijdverspreide objectgeoriënteerde en geïnterpreteerde scriptingtaal die ontworpen is voor het maken van dynamische webpagina’s [25]. De beslissing om Objective-C te gebruiken in plaats van PHP is om twee redenen gemaakt: 1. C en Objective-C zijn gecompileerde talen; deze boeken dus aanzienlijke snelheidswinsten ten opzicht van geïnterpreteerde talen zoals PHP. Bovendien kan er in C en Objective-C gebruik gemaakt worden van threads, wat verder tot snelheidswinsten kan leiden aangezien zo goed als alle moderne servers uitgerust zijn met verscheidene cores en/of processoren. 2. In (Objective-)C moeten bindingen met externe bibliotheken vaak niet geschreven worden, aangezien de meeste externe bibliotheken rechtstreeks aanspreekbaar zijn in C. Alhoewel er geen specifieke bibliotheken zijn die functionaliteit nodig voor de implementatie van het systeem aanbieden, kunnen er wel bibliotheken gebruikt worden om aan bepaalde kwaliteitseisen van het systeem te voldoen. Objective-C werd verkozen boven C omdat Objective-C objectgeoriënteerde functionaliteit aan C toevoegt. Dit vereenvoudigt de implementatie en bevordert de modulariteit. Objective-C werd ontworpen door Brad Cox als een objectgeoriënteerde laag bovenop C. De OOPfunctionaliteit was sterk geïnspireerd op Smalltalk, een andere dynamisch getypeerde en objectgeoriënteerde taal. NeXT, een bedrijf opgericht door Steve Jobs, koos voor Objective-C als de hoofdprogrammeertaal voor hun besturingssysteem NeXTstep. Wanneer NeXT overgenomen werd door

Hoofdstuk 4: Implementatie I 22

Apple, werd de op Objective-C gebaseerde technologie gebruikt in Apple’s nieuwe besturingssysteem, Mac OS X. [26, 24] De standaardbibliotheek die samen met Objective-C gebruikt wordt, is Foundation. Deze standaardbibliotheek bevat veelgebruikte klassen voor o.a. strings, lijsten en hashtabellen. Deze bibliotheek werd ontwikkeld door NeXT (nu Apple) en, alhoewel de referentieimplementatie geen vrije software is, bestaan er alternatieve implementaties die wel vrij of open-source zijn. Er wordt gebruik gemaakt van GNUstep, een implementatie van Foundation die onder de Lesser General Public License (LGPL) valt en dus gebruikt kan worden voor deze thesis. Aangezien er gebruik gemaakt wordt van een relationeel databankbeheersysteem zal ook de taal SQL (Structured Query Language) gebruikt worden. SQL is een domeinspecifieke taal die gebruikt wordt voor het bevragen en het beheren van relationele databanken.

4.1.2. Databankbeheersysteem Als databankbeheersysteem werd gekozen voor MySQL. Dit is een wijdverspreid en vrij verkrijgbaar open-source relationeel databankbeheersysteem dat vaak gebruikt wordt als onderdeel van de zogenaamde LAMP-stapel1 . MySQL bestaat uit een server die toegang verschaft tot de data; om te communiceren met de server zijn er verscheidene frontends zoals een commandline-frontend en een client-library. [27] Voor het bevragen van MySQL-servers kan het systeem gebruik maken van zowel mysqlclient, de officiële client-bibliotheek van MySQL, als libdrizzle, een alternatieve client-bibliotheek. Omdat mysqlclient onder de General Public License (GPL) valt [28], kan deze bibliotheek echter niet door Netlog gebruikt worden, en daarom kan het systeem ook gebruik maken van libdrizzle, dat gelicentieerd is onder de nieuwe BSD-licentie [29]. Oorspronkelijk werd enkel libdrizzle ondersteund, maar omdat deze bibliotheek nog niet stabiel is [30], werd ook ondersteuning voor mysqlclient toegevoegd.

4.2. Voorbereiding van data Het systeem zal gebruik maken van twee verschillende datasets. Ten eerste is er een dataset met expliciete ratings. De ratings uit deze dataset zijn gehele getallen tussen 1 en 10 (inclusief) die herschaald worden naar het [0, 1]-interval door de eenvoudige transformatie x′ = (x − 1)/9. Ten tweede is er een dataset met impliciete ratings, d.w.z. ratings die afgeleid zijn uit het gedrag van een gebruiker. Concreet wordt de rating van een object afgeleid uit het aantal keer dat een gebruiker een object gebruikt heeft. Wanneer een gebruiker een object nog niet gebruikt heeft, zal de rating een neutrale 0,5 zijn, en elke keer dat de gebruiker een bepaald object gebruikt, zal de impliciete rating voor dit object stijgen, tot aan een maximum van 1. Er zijn verschillende methodes die gebruikt wordt om het aantal keer dat een spel gespeeld is, om te zetten in een reëel getal in het [0, 1]-interval. Figuur 4.1 illustreert enkele van deze mogelijkheden. 1

LAMP is een acroniem voor een set van open-source softwarepaketten die vaak gebruikt worden om dynamische wegpagina’s te genereren. LAMP staat voor het besturingssysteem Linux, de webserver Apache, het databankbeheersysteem MySQL en de programmeertaal PHP.

Hoofdstuk 4: Implementatie I 23 rating

rating

rating

rating

1,0

1,0

1,0

1,0

0,5

0,5

0,5

0,5

# gebruikt

# gebruikt (b)

(a)

# gebruikt (c)

# gebruikt (d)

Figuur 4.1: Enkele mogelijke functies die gebruiksaantallen omzetten in impliciete ratings

In (a) wordt een eenvoudige sigmoïdale curve gebruikt die bij 0,5 begint. In (b) wordt dezelfde curve gebruikt, maar verschoven omdat het weinig gebruiken van een object op zichzelf weinig informatie geeft. In (c) wordt een rechte gebruikt in plaats van een sigmoïdale curve, en in (d) begint de curve licht negatief in plaats van neutraal, zoals voorgesteld in [31]. De geïmplementeerde methode om gebruiksaantallen om te zetten in ratings is aan de hand van een eenvoudige sigmoïdale functie. In de volgende gebruikte functie is r de uiteindelijke rating, c het aantal keer dat dit object door deze gebruiker gebruikt werd, en p een exponent die de curve vlakker of minder vlak kan maken:

r=

( ) 1 1 2 p + · arctan (c) · 2 2 π

Objecten die reeds lange tijd meer gebruikt zijn, zouden een lagere rating kunnen krijgen. De rating voor een bepaald gebruiker-object-paar zou dus kunnen evolueren naar de gemiddelde rating voor dat object. Op deze manier worden veranderende smaken voor een gebruiker opgevangen. Er werd getracht een manier te vinden die een negatieve rating toekent aan objecten die slechts even gebruikt werden. Dergelijke objecten hebben immers een grote kans om een lage impliciete rating te hebben. Deze manier van werken zal echter in bepaalde gevallen slecht presteren: 1. Wanneer een gebruiker een dienst begint te gebruiken, maar deze dienst in het begin slechts weinig gebruikt, zou de rating negatief worden. Dit is niet correct indien de gebruiker niet in staat is de dienst te gebruiken, of de dienst eenvoudigweg niet veel nodig heeft. 2. Wanneer een gebruiker een bepaalde dienst slechts éénmalig nodig heeft, zou de rating negatief worden. Voor diensten die slechts weinig moeten gebruikt worden, zoals spellen die snel uitgespeeld kunnen worden, is deze rating incorrect. De dataset met expliciete ratings en deze impliciete ratings bevatten ratings voor spellen, aangezien er enkel voor spellen nuttige informatie over het gebruiksgedrag aanwezig is. De dataset met expliciete ratings heeft een variant waarbij alle ratings genormaliseerd werden. Deze normalisatie zorgt ervoor dat de verschillen in het rating-gedrag van verschillende gebruikers tenietgedaan wordt. Voor elke gebruiker worden de ratings herschaald naar het het [0, 1]-bereik, zodat na de normalisatie elke gebruiker dezelfde schaal gebruikt om ratings aan objecten toe te kennen. Zie Figuur 4.2 voor een voorbeeld. In het geval dat een gebruiker steeds dezelfde rating geeft aan alle objecten en dus als de minimum- en maximumrating dezelfde is, is de formule niet toepasbaar en worden de ratings van deze gebruiker gelijkgesteld aan een neutrale 0,5.

Hoofdstuk 4: Implementatie I 24 0,0

0,0

0,3 0,4 0,5 0,6 0,7 0,8

0,2

0,4

0,6

0,8

1,0

1,0

Figuur 4.2: Normaliseren van expliciete ratings

Merk op dat er veel minder expliciete ratings dan impliciete ratings voorhanden zijn. Dit wil zeggen dat slechts een kleine fractie van gebruikers expliciete ratings gegeven hebben. Aangezien aanbevelingssystemen enkel aanbevelingen kunnen maken voor gebruikers waarvoor er ratings beschikbaar zijn, is het geen goed idee om enkel expliciete ratings in een aanbevelingssysteem te gebruiken. Het aantal impliciete ratings is hoger omdat er voor het maken van impliciete ratings geen extra inspanning is vereist, terwijl dit bij expliciete ratings wel het geval is. De ijlheid van beide datasets is relatief hoog in vergelijk met datasets die vaak gebruikt worden bij evaluaties van aanbevelingssystemen. De Jester-dataset is hier een voorbeeld van; deze dataset heeft een ijlheid van 78.7%, m.a.w. in de gebruikers-objecten-matrix zijn meer dan driekwart van de waarden niet ingevuld. De dataset met impliciete ratings heeft een ijlheid van 88.1% en de dataset met expliciete ratings, tenslotte, heeft een ijlheid van 94.3%; vermoedelijk is dit het gevolg van de extra inspanning die nodig is om expliciete ratings te geven.

4.3. Genereren van aanbevelingen Deze sectie licht de implementatie van de aanbevelingstechnieken toe. Deze sectie legt zowel de gebruikte algoritmes als de integratie van deze algoritmes in het systeem in detail uit. Er werd geopteerd om drie verschillende algoritmische technieken voor het genereren van aanbevelingen te implementeren. De eerste techniek, collaborative filtering, maakt aanbevelingen puur op basis van het gedrag dat gebruikers vertonen bij het gebruiken van objecten. De tweede techniek, content-based filtering, maakt gebruik van eigenschappen van de objecten, zoals de categorieën waartoe ze behoren, in plaats van het gebruiksgedrag. De derde en laatste techniek, audience-based filtering, maakt gebruik van eigenschappen van het publiek van objecten, zoals de leeftijd en het geslacht van gebruikers van dit object. Deze laatste techniek werd ontwikkeld als onderdeel van deze masterproef. Elke aanbeveler in de aanbevelingslaag bestaat uit een klasse. Voor item-based collaborative filtering is er een aanbeveler die SRItemBasedRecommender heet; de aanbeveler voor content-based filtering heeft de naam SRContentBasedRecommender en voor audience-based filtering heeft de aanbeveler de naam SRAudienceBasedRecommender. Aangezien deze drie aanbevelers echter de functionaliteit voor het maken van voorspellingen en voor het maken van aanbevelingen gemeen hebben, is er een abstract superklasse SRSimilarityModelBasedRecommender die deze functionaliteit omvat. Figuur 4.3 bevat een grafische weergave van deze klassenhiërarchie.


SRRecommender

SRSimilarityBasedRecommender

SRContentBasedRecommender

SRAudienceBasedRecommender

SRItemBasedRecommender

DATABEHEERLAAG

COÖRDINATIELAAG

AANBEVELINGSLAAG

Figuur 4.3: Overzicht van de klassen in de aanbevelingslaag

Elke aanbeveler is verplicht om minstens twee methoden te implementeren: -rebuildModel en -recommendationsForUser:limit:. De eerste methode, -rebuildModel, zorgt dat het model voor deze aanbeveler herbouwd wordt. De -recommendationsForUser:limit:-methode geeft aanbevelingen voor de gegeven gebruiker terug; de limit-parameter zorgt ervoor dat er slechts een beperkt aantal aanbevelingen teruggegeven wordt.

4.3.1. Aanbeveling met gelijkaardigheidsmodelgebaseerde aanbevelers Zowel item-based collaborative filtering als content-based filtering en audience-based filtering maken gebruik van een model waarin de gelijkaardigheden van objecten onderling uitgedrukt wordt. Bij item-based collaborative filtering zullen twee objecten gelijkaardig zijn wanneer gebruikers die het ene object een goede rating geven, het andere object ook een goede rating geven. Bij contentbased filtering zullen twee objecten gelijkaardig zijn wanneer deze objecten eigenschappen gemeen hebben, zoals de categorie waartoe ze behoren. Bij audience-based filtering, tenslotte, zullen objecten gelijkaardig zijn indien hun publiek overlapt. Het opstellen van het model is bij elk van de drie technieken verschillend, maar het maken van voorspellingen voor ratings en het genereren van aanbevelingen is voor beide technieken hetzelfde. Het algoritme voor het genereren van de voorspelling heeft als invoer een gebruikers-ID en een object-ID, en als output een voorspelling van de rating. Het algoritme ziet er als volgt uit: invoer: Een gebruiker, een object en een limiet uitvoer: Een voorspelling; een getal tussen 0 en 1 som ← 0 simTot ← 0 objecten ← limiet objecten met hoogste rating voor gebruiker voor alle object2 uit objecten rating ← rating van gebruiker voor object2 sim ← gelijkaardigheid tussen object en object2 som ← som + rating ∗ sim simTot ← simTot + sim return som/simTot

Algoritme 1: Genereren van een voorspelling


De limietparameter kan gebruikt worden om het algoritme accurater te maken (door de limiet te verhogen) of sneller te maken (door de limiet te verlagen). Het algoritme voor het maken van aanbevelingen neemt een gebruikers-ID als invoer en geeft een lijst van (object, voorspeldeRating)-tupels terug, waarvan voorspelling de kans is dat de gebruiker dit object goed zal vinden. De pseudocode van het algoritme is als volgt: invoer: Een gebruiker en een limiet limiet uitvoer: Een lijst van (object, voorspelling)-tupels aanbevelingen ← [] objecten ← objecten die nog niet gebruikt zijn door gebruiker voor alle object uit objecten voorspeldeRating ← voorspelling van de rating van gebruiker voor object aanbevelingen ← aanbevelingen + (object, voorspeldeRating) sorteer aanbevelingen op basis van aflopende voorspeldeRating return eerste limiet elementen van aanbevelingen

Algoritme 2: Genereren van aanbevelingen

4.3.2. Collaborative filtering Item-based collaborative filtering omvat twee algoritmes: het algoritme dat het model opbouwt, en het algoritme dat de eigenlijke aanbevelingen maakt. Het algoritme dat aanbevelingen maakt kan tenslotte opgesplitst worden in een algoritme dat voor elk object een voorspelling van de rating maakt, en een algoritme dat al deze voorspellingen laat maken en dan de n objecten met de hoogste voorspelde rating teruggeeft. Als invoer neemt het modelgenererend algoritme een lijst van (gebruiker, object, waarde)-tupels die de ratings voorstellen. De uitvoer is een lijst van (object, object, gelijkaardigheid)-tupels die de gelijkaardigheden tussen objecten voorstelt. De pseudocode voor dit algoritme is het volgende: invoer: Een lijst van (gebruiker, object, rating)-tupels uitvoer: Een lijst van (object1, object2, sim, aantal)-tupels simTupels ← [] voor alle objectparen (object1, object2) ratings1 ← [] ratings2 ← [] gebruikers ← gebruikers die voor zowel object1 als object2 een rating hebben aantal ← aantal gebruikers in gebruikers voor alle gebruikers gebruiker uit gebruikers ratings1 ← ratings1 + rating van gebruiker voor object1 ratings2 ← ratings2 + rating van gebruiker voor object2 sim ← gelijkaardigheid tussen ratings1 en ratings2 simTupels ← simTupels + (object1, object2, sim, aantal) return simTupels

Algoritme 3: Genereren van een model in item-based collaborative filtering


Voor het berekenen van de gelijkaardig tussen de twee vectoren kan de Pearson-correlatie of de aangepaste cosinusgelijkaardigheid gebruikt worden. Zie Sectie 2.1 op pagina 3 voor meer informatie over deze gelijkaardigheidsmetrieken. Het model kan na het opstellen genormaliseerd worden: wanneer er voor bepaalde (object, object)paren slechts een klein aantal ratings gevonden wordt, kan de uiteindelijk bekomen gelijkaardigheid tussen deze twee objecten dichter bij het gemiddelde gebracht worden om de ruis op de berekende gelijkaardigheid te verminderen. Het algoritme voor het normaliseren is het volgende: invoer: Een lijst van (object1, object2, sim, aantal)-tupels uitvoer: Een genormaliseerde lijst van (object1, object2, sim, aantal)-tupels avgSim ← gemiddelde gelijkaardigheid van alle objectparen voor alle tupels (object1, object2, sim, aantal) w ← weeg aantal sim ← w ∗ sim + (1 − w) ∗ avgSim return gewijzigde tupels (object1, object2, sim, aantal)

Algoritme 4: Normaliseren van een model in item-based collaborative filtering De weeg()-functie zet een natuurlijk getal c om in een reëel getal w(c) tussen 0 en 1 aan de hand van een sigmoïdale functie (arctan): ( w(c) =

arctan(c) ·

2 π

)p

De parameter p ∈ [0, +∞[ bepaalt de vorm van de curve. Hoe kleiner de exponent, hoe sterker de curve initieel stijgt en hoe scherper de curve dus is. Voor de exponent p werd de waarde 15 genomen in de implementatie. Een dergelijke normalisatie is niet noodzakelijk, en zal zelfs enkel nuttig zijn in gevallen waar er niet genoeg data voorhanden is om een correcte schatting van de gelijkaardigheid van twee objecten te maken. Dit kan het geval zijn wanneer nieuwe objecten geïntroduceerd werden; dergelijke nieuwe objecten moeten eerst een groot aantal keer gebruikt worden voordat de gelijkaardigheid op een accurate manier berekend kan worden.

4.3.3. Content-based filtering Content-based filtering (CBF) zal aanbevelingen maken, gebaseerd op eigenschappen van de aan te raden objecten. Zulke eigenschappen kunnen het genre zijn, de categorie waartoe het object behoort, tags en labels die toegewezen zijn aan het object, etc. Het gebruiksgedrag zal bij content-based filtering niet aangewend worden, maar dit is wel het geval bij collaborative filtering. Demografische eigenschappen van het publiek dat gebruik van deze objecten, zoals leeftijd en geslacht, wordt niet gebruikt bij content-based filtering, maar wel gebruikt worden bij audience-based filtering, een techniek die in de volgende sectie aan bod komt.


Net zoals bij collaborative filtering is content-based filtering ook modelgebaseerd. Dit model zal ook de gelijkaardigheden tussen objecten onderling uitdrukken. In het geval van content-based filtering zullen objecten gelijkaardiger zijn wanneer ze hetzelfde genre hebben, tot dezelfde categorie behoren, of labels of tags gemeenschappelijk hebben. Hiervoor wordt de Jaccard-index gebruikt. Het algoritme dat het model opbouwt, ziet er als volgt uit. In het beschreven algoritme worden enkel categorieën beschouwd, aangezien dit algoritme ook zo geïmplementeerd werd. Het algoritme kan eenvoudig uitgebreid worden om ook rekening te houden met genres, labels en tags. invoer: Een lijst van (object, categorieën)-tupels uitvoer: Een lijst van (object1, object2, sim)-tupels simTupels ← [] voor alle objectparen (object1, object2) cat1 ← categorieën van object1 cat2 ← categorieën van object2 sim ← |cat1 ∩ cat2| / |cat1 ∪ cat2| simTupels ← simTupels + (object1, object2, sim) return simTupels

Algoritme 5: Genereren van een model in content-based filtering

4.3.4. Audience-based filtering Een nadeel van content-based filtering is dat het enkel gebruik maakt van eigenschappen van het object zelf, en niet van afgeleide eigenschappen zoals het geslacht van de gemiddelde gebruiker van dit object. Audience-based filtering (ABF) is een techniek die ontwikkeld werd als deel van deze masterproef om dit nadeel weg te werken. Deze techniek zal aanbevelingen maken op basis van eigenschappen van het publiek dat gebruik maakt van objecten. Eigenschappen die hierbij in rekening gebracht worden, zijn de leeftijd en het geslacht van de gebruikers. Deze techniek heeft in de literatuur geen bestaande naam; de naam “audience-based filtering” werd gekozen omdat dit de werking van de techniek accuraat beschrijft. De huidige implementatie van audience-based filtering is relatief naïef: van zowel de leeftijd als het geslacht wordt het gemiddelde E en de standaardafwijking σ berekend, en aan de hand van deze metrieken worden intervallen [E − σ, E + σ] opgesteld. Het geslacht van een gebruiker wordt omgezet in ofwel 0 (vrouwelijk) of 1 (mannelijk). De mate waarin twee intervallen overlappen, kan berekend worden aan de hand van een aangepaste Jaccard-index. De Jaccard-index kan gebruikt worden om de gelijkaardigheid tussen twee sets te bepalen. De formule ziet er als volgt uit:

sj (X, Y ) =

|X ∩ Y | |X ∪ Y |

De aangepaste Jaccard-index die gebruikt wordt om de gelijkaardigheid tussen twee intervallen in plaats van sets te berekenen, ziet er als volgt uit:


E1

E2

E1 - σ1

E1 + σ1 E2 - σ2

E2 + σ2 ⋂

⋃

Figuur 4.4: Voorbeeld van hoe gelijkaardigheid in audience-based filtering berekend wordt. E is de gemiddelde waarde (het midden van het interval) en σ is de standaardafwijking voor dit interval.

sim′ =

| min(E1 + σ1 , E2 + σ2 ) − max(E1 − σ1 , E2 − σ2 )| | max(E1 + σ1 , E2 + σ2 ) − min(E1 − σ1 , E2 − σ2 )|

Wanneer er echter geen overlap is tussen beide intervallen, is deze formule niet bruikbaar. In dit geval wordt de gelijkaardigheid gelijk gesteld aan 0: { sim =

0 als min(E1 + σ1 , E2 + σ2 ) < max(E1 − σ1 , E2 − σ2 ) ′ sim elders

Zie Figuur 4.4 voor een grafische voorstelling van hoe de gelijkaardigheid tussen twee intervallen berekend wordt. Hierbij stellen E1 en E2 de gemiddeldes van respectievelijk interval 1 en interval 2 voor, terwijl de standaardafwijkingen van de intervallen 1 en 2 voorsgesteld worden als σ1 respectievelijk σ2 . invoer: Een lijst van (object, leeftijdGem, leeftijdStddev, geslachtGem, geslachtStddev)-tupels uitvoer: Een lijst van (object1, object2, simLeeftijd, simGeslacht)-tupels simTupels ← [] voor alle objectparen (object1, object2) int1Leeftijd ← interval corresponderend met leeftijd voor object1 int2Leeftijd ← interval corresponderend met leeftijd voor object2 int1Geslacht ← interval corresponderend met geslacht voor object1 int2Geslacht ← interval corresponderend met geslacht voor object2 simLeeftijd ← gelijkaardigheid tussen int1Leeftijd en int2Leeftijd simGeslacht ← gelijkaardigheid tussen int1Geslacht en int2Geslacht simTupels ← simTupels + (object1, object2, simLeeftijd, simGeslacht) return simTupels

Algoritme 6: Genereren van een model in audience-based filtering


AANBEVELINGSLAAG

DATABEHEERLAAG

SRDataSource

SRSimilarityBasedDataSource

SRContentBasedDataSource

SRAudienceBasedDataSource

SRItemBasedDataSource

Figuur 4.5: Overzicht van de klassen in de databeheerlaag

De uitvoer van dit algoritme is niet één maar twee verschillende gelijkaardigheden: de gelijkaardigheid op basis van leeftijd en de gelijkaardigheid op basis van geslacht. De audience-based filteringaanbeveler kan geconfigureerd worden om te werken met één van de twee gelijkaardigheden, of kan geconfigureerd worden om met een combinatie van gelijkaardigheden te werken (bijvoorbeeld 40% geslacht en 60% leeftijd). De huidige implementatie leidt de leeftijd van een gebruiker af aan de hand van zijn/haar geboortedatum en het tijdstip waarop het model wordt opgebouwd. Bij zeer grote datasets (groter dan één jaar) kan deze aanpak problematisch worden, aangezien de leeftijd van de gebruiker op het moment dat bepaalde objecten gebruikt werden, niet meer zal overeenstemmen met de berekende leeftijd (de leeftijd op het moment dat het model herbouwd wordt). Dit kan voor ruis en dus tot minder accurate resultaten zorgen. Dit is één van de redenen waarom te grote datasets indien mogelijk vermeden moeten worden.

4.4. Databeheer De databeheerlaag bevat de databronnen, die door de aanbevelers gebruikt worden om aanbevelingen te maken. De databronnen hebben geen gemeenschappelijke interface, aangezien verschillende aanbevelers data in verschillende formaten nodig kunnen hebben; de abstracte databronsuperklasse SRDataSource biedt daarom ook geen methoden aan voor het opvragen of aanpassen van data. Voor gelijkaardigheidsmodelgebaseerde aanbevelers (aanbevelers waarvan de klasse een subklasse is van SRSimilarityModelBasedRecommender) bestaat er wel een databronklasse (SRSimilarityModelBasedDataSource) die gemeenschappelijke functionaliteit aanbiedt. Deze functionaliteit bestaat uit het opvragen van alle gebruikers-IDs, alle item-IDs, alle ratings voor een specifieke gebruiker, de gelijkaardigheid tussen twee gegeven items, etc. Functionaliteit voor het aanpassen van gelijkaardigheden tussen items wordt ook aangeboden; dit is immers nodig bij het herbouwen van modellen. Er zijn twee subklassen van de abstracte databronklasse die gebruikt wordt voor gelijkaardigheidsmodelgebaseerde aanbevelers. De databron die overeenstemt met de item-based-aanbeveler heet SRItemBasedDataSource en biedt functionaliteit aan voor het opvragen van gemeenschappelijke ratings voor een gegeven objectpaar (gebruikt bij het herbouwen modellen) en voor het op-


vragen van gemiddelde ratings voor een object (gebruikt bij het normaliseren van modellen). De databron die met de content-based-aanbeveler correspondeert, SRContentBasedDataSource, biedt functionaliteit aan voor het opvragen van categorieën van een object, alsook het opvragen van eigenschappen van het publiek dat gebruik maakt van dit object. Tenslotte is er SRAudienceBasedDataSource, de klasse die functionaliteit aanbiedt voor het opvragen van karakteristieken over het publiek dat gebruik maakt van een bepaald spel. De overervingsboom van deze databronklassen is te vinden in Figuur 4.5.

4.5. Coördinatie De coördinatielaag staat in voor het beheren van verschillende aanbevelers in het systeem. Wanneer een aanvraag voor het maken van aanbevelingen of voor het herbouwen van modellen ontvangen wordt, zal de coördinator deze aanvragen naar de juiste aanbevelers doorsturen en de teruggegeven resultaten combineren. De coördinator werd echter niet met deze functionaliteit geïmplementeerd. Het coördinator-object is in de huidige implementatie slechts in staat om één aanbeveler aan te spreken, en is niet in staat om resultaten van verschillende aanbevelers te combineren. De reden hiervoor is dat elke combinatie van aanbevelingen beter kan gebeuren op niveau van de aanbevelers in plaats van in de coördinator zelf. De combinatie van resultaten op aanbevelersniveau is veel flexibeler en krachtiger, aangezien een effectieve combinatie van aanbevelingen ook brondata en intermediaire data zal nodig hebben, wat niet mogelijk is in de coördinator zelf. De coördinatielaag in de huidige implementatie is dus overbodig en kan dus weggelaten worden.

4.6. Frontend Er werden gekozen om twee verscheidene frontends te implementeren. De eerste frontend is de commandline-frontend, die toelaat om via de commandline aanbevelingen op te vragen en de modellen te herbouwen. De tweede frontend maakt gebruik van een grafische interface om aanbevelingen op te vragen. Deze twee frontends worden in Figuur 4.6 getoond. Oorspronkelijk was het plan om ook een web service-frontend te schrijven, zodat het systeem rechtstreeks van buitenaf aangesproken kan worden. Omwille van tijdgebrek en omdat een dergelijke frontend geen meerwaarde voor onderzoek heeft, werd zo’n frontend werd echter niet geschreven, maar is desondanks eenvoudig te implementeren aangezien de architectuur het mogelijk maakt om verscheidene frontends te ondersteunen.


Figuur 4.6: De geïmplementeerde GUI- en commandline-frontends

I

33

5. EVALUATIE

In dit hoofdstuk worden de evaluatiemechanismen beschreven, en worden de resultaten van de evaluaties besproken. Er werden hoofdzakelijk testen uitgevoerd die de accuraatheid meten van de voorspellingen en van de aanbevelingen gegenereerd door het systeem. Snelheidsevaluaties werden niet uitgevoerd.

5.1. Accuraatheid De accuraatheid van de aanbevelers kan op twee vlakken geëvalueerd worden. Ten eerste kan, vrij eenvoudig, de accuraatheid van de voorspelde ratings gemeten worden. Ten tweede kan ook gemeten worden hoe accuraat de eigenlijke aanbevelingen zijn. De accuraatheid van zowel de voorspellingen als de aanbevelingen kan getest worden met het evaluator-programma. Voor beide soorten evaluaties kan de evaluator gebruik maken van kruisvalidatie (cross-validation) om de accuraatheid van de algoritmes te testen. Hiervoor wordt de dataset aan de hand van een predicaat gepartitioneerd in een trainingsset en een testset; de testdata en de trainingsdata zijn dus volledig disjunct. De evaluaties werden uitgevoerd voor item-based collaborative filtering, content-based filtering en audience-based filtering. Voor elk van deze technieken werd het systeem geëvalueerd met zowel expliciete ratings (niet-genormaliseerd en genormaliseerd) en impliciete ratings (korte dataset van iets minder dan twee maanden).

5.1.1. Accuraatheid van voorspellingen Bij het evalueren van de kwaliteit van de voorspellingen zal het evaluatorprogramma over alle (gebruiker, object, rating)-tupels itereren en een voorspelling van de rating voor het corresponderende (gebruiker, object)-tupel genereren. De rating die door het systeem voorspeld wordt, kan dan vergeleken worden met de ware rating die door de gebruiker gegeven werd. Voor elk (gebruiker, item)-paar wordt de echte rating met de voorspelde rating vergeleken, en wordt de absolute fout (het verschil van de echte rating met de voorspelde rating) opgeslaan [31]. Om de kwaliteit van de voorspellingen na te gaan, wordt er een cumulatief histogram opgesteld voor elke configuratie van aanbevelers en datasets.

Hoofdstuk 5: Evaluatie I 34

Merk op dat de resultaten voor de datasets met impliciete ratings en met expliciete ratings er anders zullen uit zien. Impliciete ratings zullen zich tussen 0, 5 en 1 bevinden (zie Sectie 4.2 op pagina 22), terwijl de expliciete ratings zich tussen 0 en 1 bevinden. Bovendien bevat de impliciete dataset slechts data die over een aantal weken verzameld is, terwijl de expliciete dataset alle ratings bevat die ooit gegeven zijn. Dit onderscheid heeft als gevolg dat de resultaten voor impliciete ratings niet zomaar kunnen vergeleken worden met resultaten voor expliciete ratings. Het doel van een aanbevelingssysteem is om een aantal aanbevelingen voor een gegeven gebruiker te maken en niet om voorspellingen van ratings te maken. Dit is een belangrijk onderscheid: de kwaliteit van de aanbevelingen wordt enkel bepaald door de uiteindelijke volgorde van de aanbevelingen, aangezien de aanbevolen objecten de objecten zullen zijn die het hoogst in deze lijst staan. De accuraatheid van de voorspelde ratings is dus geen goede indicatie van de accuraatheid van de aanbevelingen. De aanbevelingen zelf kunnen nog van goede kwaliteit zijn, zelfs al hebben de voorspelde ratings een grote absolute fout. Systematische fouten in de voorspellingen, bijvoorbeeld, zullen de kwaliteit van de aanbevelingen niet aantasten. De resultaten van de evaluaties voor zowel collaborative filtering, content-based filtering als audience-based filtering, gecombineerd met zowel impliciete ratings als expliciete ratings, zijn weergegeven in Figuren 5.1, 5.2, 5.3 en 5.4. Deze vier grafieken bevatten een cumulatief histogram van de fout, die van 0 tot 1 kan lopen. Als maat voor de accuraatheid voor elke curve wordt de oppervlakte van het gebied boven de curve genomen. Hoe groter deze oppervlakte is, hoe slechter de accuraatheid van de configuratie voor deze curve. Uit de resulterende grafieken kunnen de volgende conclusies getrokken worden: • Het normaliseren van expliciete ratings heeft een negatieve impact op de voorspellingen. Dit effect is duidelijk te zien bij zowel collaborative filtering als content-based/audience-based filtering (Figuren 5.1 en 5.3). • Het gebruik van de aangepaste cosinusgelijkaardigheid in plaats van de Pearson-correlatie bij collaborative heeft een positief effect op de accuraatheid. Dit is vooral zichtbaar bij expliciete ratings (Figuur 5.1). • Bij content-based filtering en expliciete ratings scoort de gelijkaardigheid op basis van categorieën duidelijk beter dan gelijkaardigheid op basis van leeftijd of geslacht (Figuur 5.3). Wanneer er gebruik gemaakt wordt van impliciete ratings scoort de gelijkaardigheid op basis van categorie echter duidelijk slechter (Figuur 5.4). • De grafiek die de accuraatheid van impliciete ratings bij content-based/audience-based filtering toont (Figuur 5.4), vertoont merkwaardige sprongen. Dit kan te verklaren zijn door de vorm van de dataset met impliciete ratings.

5.1.2. Accuraatheid van aanbevelingen Zoals eerder vermeld, is de accuraatheid van voorspellingen op zichzelf niet genoeg om te besluiten of een algoritme in staat is om goede aanbevelingen te maken. Wat er bij aanbevelingen van belang is, is de volgorde waarin deze aanbevelingen zich bevinden; uit deze gesoorteerde lijst zullen immers de eerste paar elementen genomen worden als aanbevelingen die aan de gebruiker getoond zullen worden. De gemaakte aanbevelingen zelf moeten dus ook geëvalueerd worden.


Vergelijking van voorspellingen 1

Cumulatieve frequentie

0,8

0,6

0,4

0,2

0

CF (limiet 5; expliciet; aangepaste cosinusgelijkaardigheid) CF (limiet 5; expliciet; aangepaste cosinusgelijkaardigheid; genormaliseerd) CF (limiet 5; expliciet; pearson) CF (limiet 5; expliciet; pearson; genormaliseerd) 0

0,2

0,4

0,6

0,8

1

Fout

Figuur 5.1: Cumulatief histogram van de fout voor collaborative filtering met expliciete ratings



0,8

0,6

0,4

0,2

0

CF (limiet 5; impliciet klein; aangepaste cosinusgelijkaardigheid) CF (limiet 5; impliciet klein; pearson) 0

0,2

0,4

0,6

0,8

1

Fout

Figuur 5.2: Cumulatief histogram van de fout voor collaborative filtering met impliciete ratings




0,8

0,6

0,4

0,2

0

ABF (limiet 5; leeftijd; expliciet) ABF (limiet 5; leeftijd; expliciet; genormaliseerd) ABF (limiet 5; geslacht; expliciet) ABF (limiet 5; geslacht; expliciet; genormaliseerd) CBF (limiet 5; categorie; expliciet) CBF (limiet 5; categorie; expliciet; genormaliseerd) 0

0,2

0,4

0,6

0,8

1

Fout

Figuur 5.3: Cumulatief histogram van de fout voor content- en audience-based filtering met expliciete ratings



0,8

0,6

0,4

0,2

0

ABF (limiet 5; leeftijd; impliciet klein) ABF (limiet 5; geslacht; impliciet klein) CBF (limiet 5; categorie; impliciet klein) 0

0,2

0,4

0,6

0,8

1

Fout

Figuur 5.4: Cumulatief histogram van de fout voor content- en audience-based filtering met impliciete ratings


Voor elke gebruiker worden een aantal aanbevelingen gemaakt, en wordt er vervolgens nagegaan of deze aanbevelingen wel degelijk door de gebruiker als “goed” bevonden worden. Hiervoor dient er een onderscheid tussen goede en slechte aanbevelingen gemaakt te worden: deze grens (threshold) zal positieven van negatieven scheiden. Er wordt gebruik gemaakt van ROC-curves [31, 32] om de accuraatheid van de onderlinge aanbevelers te meten. Een ROC-curve toont grafisch hoe goed het systeem in staat is om onderscheid te maken tussen signaal en ruis. ROC-curves zetten de relatieve hoeveelheid valse positieven (op de Xas) uit ten opzichte van de relatieve hoeveelheid correcte positieven (op de Y-as). Dit gebeurt voor verschillende datapunten; bij de evaluatie van aanbevelingen stemmen deze punten overeen met verschillende lengtes van de lijst waarin alle aanbevelingen vervat zijn, gesorteerd op aflopende waarschijnlijkheid dat deze aanbeveling correct zal zijn. Een aanbeveler die willekeurige aanbevelingen maakt, zal corresponderen met een ROC-curve die samenvalt met de eerste diagonaal. Hoe beter een aanbeveler, hoe groter de oppervlakte onder de corresponderende ROC-curve. De ideale aanbeveler, die een lijst van aanbevelingen maakt waarbij eerst alle goede aanbevelingen komen, gevolgd dor alle slechte aanbevelingen, correspondeert met een curve die in (0, 0) begint, rechtstreeks naar (0, 1) gaat (corresponderend met alle relevante objecten) en vervolgens eindigt in (1, 1) (corresponderend met alle niet-relevante objecten). Aangezien er bij ROC-curves gebruik gemaakt wordt van een grens (threshold) die goede van slechte objecten scheidt, kan er niet afgeleid worden of de volgorde waarin goede aanbevelingen voorkomen, goed is. Met andere woorden: de onderlinge ordening van goede aanbevelingen zal geen invloed hebben op de ROC-curve. Elke permutatie van goede aanbevelingen zal tot dezelfde ROCcurve leiden. Dit nadeel is impliciet in het gebruik van ROC-curves.

100%

Wanneer aanbevelingen gemaakt worden, zal in de praktijk slechts een beperkt aantal (bijvoorbeeld vijf of tien) objecten met de hoogst voorspelde ratings aan de gebruiker getoond worden. De volgorde waarin de resterende objecten zich bevinden, is van geen belang, aangezien deze objecten niet als aanbevelingen gebruikt worden. De oppervlakte onder de ROC-curve kan dus hier niet zomaar als een metriek voor de accuraatheid van aanbevelers gebruikt worden.

fractie echt positieven

a

b d

e

0%

c

0%

fractie vals positieven 100%

Figuur 5.5: Voorbeelden van ROC-curves


Figuur 5.5 toont enkele voorbeelden van ROC-curves. Curve a correspondeert met een aanbeveler die zeer goed in staat is om goede van slechte aanbevelingen te scheiden. Curve b is een curve die correspondeert met een aanbeveler die in staat is om zeer goede aanbevelingen te scheiden van slechte (stijgt sterk in het begin), maar niet goed in staat is om een accurate volgorde op te leggen aan middelmatige goede tot slechte aanbevelingen (duikt onder de eerste diagonaal). Curve c correspondeert met een gemiddeld goede aanbeveler. Curve d correspondeert met een volledige willekeurige aanbeveler. Curve e correspondeert met een slechte aanbeveler (zelfs slechter dan willekeurig). Merk op dat de oppervlakte onder de curve b suggereert dat de corresponderende aanbeveler niet veel beter is dan een volledig willekeurige aanbeveler. Aangezien echter enkel de eerste aanbevelen in de volledige lijst gegenereerd door aanbevelers van belang zijn, kan de accuraatheid van de aanbeveler corresponderend met curve b toch als goed beschouwd worden. Wanneer het aanbevelingssysteem in een productieomgeving gebruikt zal worden, zal dit systeem enkel spellen aanbevelen die de gebruiker nog niet gebruikt heeft, om zo de gebruiker nieuwe spellen te laten ontdekken. Over niet-gespeelde spellen is er echter geen informatie, en bijgevolg zouden zulke aanbevelingen onmogelijk geëvalueerd kunnen worden. Om deze reden worden bij deze accuraatheidstests wel degelijk reeds gespeelde spellen opgenomen. Bij deze tests wordt dus de accuraatheid van de aanbevelingen gemeten op basis van reeds gespeelde spellen waarvan de rating reeds gekend is. Een correctere evaluatie zou gebruik maken van nietgespeelde spellen: het zijn immers net deze spellen die aangeraden worden. Om dergelijke evaluaties uit te voeren, zijn echter gebruikerstests nodig: het systeem moet enige tijd in productie gebruikt worden, en na afloop van deze periode kan dan gekeken worden of de aanbevelingen die in deze periode gemaakt werden, inderdaad een positieve invloed hadden op het gedrag van gebruikers. Uit de resulterende grafieken kunnen de volgende conclusies getrokken worden: • Collaborative filtering zorgt voor accuratere aanbevelingen dan bij content-based of audience-based filtering; de oppervlakte onder de curve is bij collaborative filtering significant groter dan de oppervlakte bij CBF en ABF. (Figuur 5.7 versus Figuur 5.9; Figuur 5.6 versus Figuur 5.8). Dit is te verwachten aangezien collaborative filtering het gebruiksgedrag modelleert, terwijl CBF en ABF dit niet doen. • Het normaliseren van expliciete ratings heeft een duidelijk positieve invloed op de kwaliteit van de aanbevelingen (Figuur 5.6). Dit is in tegenstelling tot wat de resultaten van accuraatheidstests op basis van voorspellingen (Figuur 5.1) aantoonden. Dat het normaliseren een positieve invloed heeft op de kwaliteit van de aanbevelingen is te verklaren door het feit dat de normalisatie de verschillen in de rating-schalen van verschillende gebruikers teniet doet. • Het gebruik van de Pearson-correlatie bij expliciete ratings maakt de kwaliteit van de aanbevelingen iets beter dan wanneer er de aangepaste cosinusgelijkaardigheid zou gebruikt worden, maar het verschil is klein (5.6). • Bij content-based filtering en audience-based filtering gecombineerd met expliciete ratings (Figuur 5.8) is er geen nuttige informatie af te leiden of normalisatie al dan niet beter is. Er is ook niets te besluiten over het feit of categorie, leeftijd of geslacht het best presteert.


• Wanneer er van impliciete ratings gebruik gemaakt wordt bij content-based en audiencebased filtering (Figuur 5.9), is het gebruik van categorie duidelijk beter dan het gebruik van leeftijd of geslacht.

5.1.3. Invloed van aantal vergeleken objecten Bij het maken van een voorspelling voor een gegeven gebruiker en een gegeven object wordt dit object vergeleken met andere objecten waarvoor de gebruiker reeds een rating gegeven heeft. De gebruikte formule is ∑ \ r(u, i) =

i′ ∈Iu

s(i, i′ ) · r(u, i′ ) ∑

s(i, i′ )

i′ ∈Iu

De sommaties lopen over alle objecten i′ ∈ Iu waarvoor de gebruiker u een rating heeft, maar dit is inefficiënt wanneer het over een grote collectie van objecten gaat. Omwille van deze prestatiereden wordt de collectie beperkt tot de n objecten waarvoor de gebruiker de hoogste rating gegeven heeft. De evaluatieresultaten uit de vorige secties stelden deze n gelijk aan 5, aangezien dit voor een goed compromis tussen snelheid en accuraatheid zorgt. Hogere en lagere waarden zijn echter mogelijk. Figuren 5.10 en 5.11 geven een idee van de impact van een hogere rating; deze twee evaluaties werden uitgevoerd met collaborative filtering en impliciete ratings met een waarde gelijkgesteld aan 5 en 15. Deze twee nieuwe evaluatieresultaten tonen aan dat hogere waarden voor het aantal objecten met de hoogste rating voor accuratere resultaten zorgt. Evaluaties met een waarde gelijk aan 15 werden uitgevoerd voor alle gevallen (CF, CBF, ABF, gecombineerd met impliciete en expliciete ratings), en deze andere evaluaties confirmeren dat hogere waarden steeds resulteren in meer accurate voorspellingen en aanbevelingen.

5.2. Uitvoeringssnelheid Voor het systeem werden er geen uitgebreide uitvoeringssnelheidstesten uitgevoerd. Tijdens de implementatie lag de nadruk op de accuraatheid van het systeem, en werd er dus minder aandacht geschonken aan de uitvoeringssnelheid. Dit wil zeggen dat de individuele componenten waarschijnlijk niet met maximale efficiëntie geïmplementeerd zijn. Snelheidtesten zullen hierdoor waarschijnlijk weinig praktisch nut hebben, aangezien deze eenvoudigweg de inefficiëntie van het systeem zouden meten, in plaats van de complexiteit van de algoritmes zelf. Figuur 5.12 geeft een indicatie van de uitvoeringssnelheid van het systeem. Het maximaal aantal gelijkaardige objecten heeft voor kleine waarden een grote invloed op de uitvoeringssnelheid, maar aangezien er slechts weinig gebruikers zijn met een groot aantal gebruikte items, stabiliseert de uitvoeringssnelheid zich. Het verschil in snelheid tussen impliciete en expliciete ratings kan verklaard worden door het grote verschil in het aantal datapunten die gebruikt worden bij het aanmaken van de aanbevelingen. Bij het maken van de snelheidsevaluaties werd er gebruik gemaakt wordt van een 2 GHz dual-core processor met een harde schijf met een rotatiesnelheid van 5400 RPM.


Vergelijking van aanbevelingen (threshold 0,9) 1

Fractie echte positieven (sensitiviteit)

0,8

0,6

0,4

0,2

0

CF (limiet 5; expliciet; aangepaste cosinusgelijkaardigheid) CF (limiet 5; expliciet; aangepaste cosinusgelijkaardigheid; genormaliseerd) CF (limiet 5; expliciet; pearson) CF (limiet 5; expliciet; pearson; genormaliseerd) willekeurig 0

0,2

0,4 0,6 Fractie valse positieven (1-specificiteit)

0,8

1

Figuur 5.6: ROC-curve (valse positieven versus echte positieven) voor collaborative filtering met expliciete ratings



0,8

0,6

0,4

0,2

0

CF (limiet 5; impliciet klein; aangepaste cosinusgelijkaardigheid) CF (limiet 5; impliciet klein; pearson) willekeurig 0

0,2


0,8

1

Figuur 5.7: ROC-curve (valse positieven versus echte positieven) voor collaborative filtering met impliciete ratings




0,8

0,6

0,4

ABF (limiet 5; leeftijd; expliciet) ABF (limiet 5; leeftijd; expliciet; genormaliseerd) ABF (limiet 5; geslacht; expliciet) ABF (limiet 5; geslacht; expliciet; genormaliseerd) CBF (limiet 5; categorie; expliciet) CBF (limiet 5; categorie; expliciet; genormaliseerd) willekeurig

0,2

0 0

0,2


0,8

1

Figuur 5.8: ROC-curve (valse positieven versus echte positieven) voor content- en audiencebased filtering met expliciete ratings



0,8

0,6

0,4

0,2

0

ABF (limiet 5; leeftijd; impliciet klein) ABF (limiet 5; geslacht; impliciet klein) CBF (limiet 5; categorie; impliciet klein) willekeurig 0

0,2


0,8

1

Figuur 5.9: ROC-curve (valse positieven versus echte positieven) voor content- en audiencebased filtering met impliciete ratings




0,8

0,6

0,4

0,2

0

CF (limiet 15; impliciet klein; aangepaste cosinusgelijkaardigheid) CF (limiet 15; impliciet klein; pearson) CF (limiet 5; impliciet klein; aangepaste cosinusgelijkaardigheid) CF (limiet 5; impliciet klein; pearson) willekeurig 0

0,2

0,4

0,6

0,8

1

Fractie valse positieven (1-specificiteit)

Figuur 5.10: ROC-curve (valse positieven versus echte positieven) voor collaborative filtering met impliciete ratings en het aantal elementen met de hoogste rating gelijkgesteld aan eens 5 en eens 15



0,8

0,6

0,4

0,2

0

CF (limiet 15; impliciet klein; aangepaste cosinusgelijkaardigheid) CF (limiet 15; impliciet klein; pearson) CF (limiet 5; impliciet klein; aangepaste cosinusgelijkaardigheid) CF (limiet 5; impliciet klein; pearson) 0

0,2

0,4

0,6

0,8

1

Fout

Figuur 5.11: Cumulatief histogram van de fout voor collaborative filtering met impliciete ratings en het aantal elementen met de hoogste rating gelijkgesteld aan eens 5 en eens 15


De bepalende factoren voor de snelheid van het systeem werden niet experimenteel bepaald. De bottleneck bij dit systeem zal met hoge waarschijnlijkheid de invoer- en uitvoersnelheid zijn; zowel bij het maken van voorspellingen (en dus bij het maken van aanbevelingen) en bij het herbouwen van modellen wordt er zeer veel data vanuit de databank ingelezen. Het geheugenbruik is geen beperkende factor; bij het uitvoeren van de evaluaties gebruikt het systeem ongeveer 50 MiB.

Tijd nodig voor het aanmaken van 5000 aanbevelingen 7

cf; impl; pearson cf; expl; pearson

6

Duur (min)

5 4 3 2 1 0

1

5

10

15

20

25

30

35

40

45

50

Maximum aantal gelijkaardige objecten

Figuur 5.12: Vergelijking in uitvoeringstijd voor collaborative filtering met zowel impliciete als expliciete ratings. De tijd voor het maken van 5000 aanbevelingen werd gemeten met een aantal verschillende waarden voor het maximum aantal gelijkaardige objecten.

5.3. Parameters Bij de evaluatie zijn er een aantal parameters die aangepast kunnen worden om de resultaten te beïnvloeden. Deze parameters zijn de volgende: aanbeveler Er kan gebruik gemaakt worden van collaborative filtering, content-based filtering (op basis van categorie) en audience-based filtering (op basis van geslacht of op basis van leeftijd). gelijkaardigheidsmetriek Bij collaborative filtering kunnen verschillende gelijkaardigheidsmetrieken gebruikt worden. Er kan gebruik gemaakt worden van de Pearson-gelijkaardigheid en de aangepaste cosinusgelijkaardigheid. Beide metrieken werden gebruikt in de evaluaties. aantal vergeleken objecten Bij het voorspellen van een rating voor een gegeven object-gebruiker-paar wordt er gebruik gemaakt van een aantal objecten die reeds goed bevonden worden door deze gebruiker. In het merendeel van de evaluaties werd deze waarde gelijkgesteld aan 5, maar in Sectie 5.1.3 worden er ook evaluaties getoond waarbij de waarde gelijkgesteld werd aan 15.

Hoofdstuk 5: Evaluatie I 44 normalisatie Expliciete ratings kunnen wel of niet genormaliseerd worden. Beide mogelijkheden werden geëvalueerd. bron van ratings Er kunnen impliciete of expliciete ratings gebruikt worden. Bij de evaluaties werden beide soorten ratings gebruikt.

I

45

6. MOGELIJKE UITBREIDINGEN EN CONCLUSIE

In dit hoofdstuk worden alle resultaten samengevat en besproken. Verder worden er enkele mogelijke uitbreidingen die voor verbeterde resultaten kunnen zorgen, voorgesteld.

6.1. Conclusie Uit de evaluatieresultaten voor collaborative filtering, content-based filtering en audience-based filtering blijkt dat collaborative filtering consistent de beste resultaten geeft voor de gebruikte datasets. Alhoewel content-based en audience-based filtering in staat zijn om goede aanbevelingen te maken, zijn de aanbevelingen die door collaborative filtering gegenereerd worden, kwalitatief steeds beter. Dat collaborative filtering het best presteert, houdt steek: collaborative filtering maakt immers voorspellingen van het gebruiksgedrag puur op basis van het gebruikgedrag dat reeds gekend was, terwijl andere technieken veel minder gebruik maken van deze historische informatie. Deze conclusie wordt versterkt door het feit dat bekende websites zoals Last.fm en Amazon.com [4] ook gebruik maken van collaborative filtering voor het genereren van aanbevelingen. Impliciete ratings, ratings die afgeleid zijn uit het aantal keer dat een bepaalde gebruiker een aantal spel gespeeld heeft, presteren ook beter dan expliciete ratings. Aanbevelingen die gebaseerd zijn op genormaliseerde expliciete ratings presteren bijna even goed als impliciete ratings, maar expliciete ratings hebben het nadeel dat slechts weinig gebruikers wel degelijk zulke expliciete ratings zullen geven, terwijl impliciete ratings reeds beschikbaar zijn vanaf het moment dat een gebruiker zijn eerste spel gespeeld heeft. Het feit dat impliciete ratings beter presteren dan expliciete ratings is te verklaren door het feit dat impliciete ratings veel objectiever zijn dan expliciete ratings, aangezien impliciete ratings niet handmatig door een gebruiker gegeven worden.

6.2. Support vector machines voor audience-based filtering In plaats van een gelijkaardigheidsmodel op te stellen voor audience-based filtering, kan voor elk object een support vector machine getraind worden die beslist of een bepaalde gebruiker al dan niet dit object goed zou vinden. Support vector machines zullen in staat zijn om correlaties te vinden tussen verschillende eigenschappen van het publiek dat gebruikt maakt van objecten, zoals leeftijd en geslacht, wat niet mogelijk is in de huidige implementatie van audience-based filtering. Figuur 6.1 stelt een dergelijke support vector machine voor een bepaald object voor. In dit voorbeeld worden gebruikers u5 en u6 beschouwd als gebruikers die dit bepaald object goed vinden, terwijl

Hoofdstuk 6: Mogelijke uitbreidingen en conclusie I 46

gebruikers u1 tot en met u4 als tegenvoorbeeld gebruikt worden. Het publiek van dit object in het voorbeeld zijn dus hoofdzakelijk jongere meisjes. leeftijd

30

u4

20

u3

10

u1

u2 u6 u5

0 0

1 geslacht (0=m, 1=v)

Figuur 6.1: Mogelijk gebruik van SVM voor audience-based filtering

6.3. Betere manier van vergelijken van distributies Bij audience-based filtering wordt er momenteel gebruik gemaakt van het gemiddelde en de standaardafwijking van een bepaalde eigenschap van het publiek dat van een bepaald object gebruik maakt. Deze manier van werken gaat er echter van uit dat de distributie die met deze eigenschap en dit correspondeert, ongeveer normaal verdeeld is. Dit is niet noodzakelijk geval, en andere manieren om de gelijkaardigheid tussen publieken van objecten te berekenen, kunnen onderzocht worden. Enerzijds kunnen andere distributies gebruikt worden. In plaats van een gaussiaanse verdeling zou bijvoorbeeld een (verschoven) Gamma-distributie beter passen. Anderszijds is het ook mogelijk om de histogrammen van de distributies te vergelijken. Als beide histogrammen genormaliseerd zijn (oppervlakte gelijk aan 1), kan het verschil in oppervlakte dienen als maat voor de ongelijkaardigheid van de twee distributies.

6.4. Combineren van impliciete en expliciete ratings Op dit moment maakt het systeem gebruik van ofwel impliciete, ofwel expliciete ratings. Beide manieren van werken zorgen voor positieve resultaten, maar er zou moeten onderzocht worden of een combinatie van impliciete en expliciete ratings niet beter kan presteren dan ofwel impliciete, ofwel expliciete ratings afzonderlijk. Wanneer een gebruiker een object een extreme expliciete rating geeft (bijvoorbeeld 0,9), samen met een extreme impliciete rating (bijvoorbeeld 0,95, corresponderend met bijvoorbeeld een paar tientallen keer gebruikt), kan er besloten worden om deze twee ratings te combineren tot een rating die extremer is dan beide ratings (bijvoorbeeld 1,0). Anderszijds kunnen twee extreme ratings die elkaar tegenspreken (bijvoorbeeld expliciet 0,1, impliciet 0,9) gecombineerd worden tot een rating die een compromis maakt (bijvoorbeeld 0, 5).


6.5. Andere manieren van evalueren Zoals besproken in het evaluatie-hoofdstuk, hebben de uitgevoerde evaluaties slechts een beperkt nut. De kwaliteit van voorspellingen is bijvoorbeeld niet representatief voor de kwaliteit van de aanbevelingen. De kwaliteit van de aanbevelingen kan niet op een goede manier nagegaan worden omdat er over zeer veel gemaakte aanbevelingen absoluut geen informatie is over hoe goed deze aanbeveling wel degelijk is. Er moet dus gezocht worden naar alternatieve methoden om de aanbevelingen te evalueren. Een mogelijke manier om de evaluaties op een betere manier uit te voeren, is door het systeem gedurende een aantal weken in productie te laten gebruiken, om zo af te leiden of het systeem al dan niet aanbevelingen heeft gegenereerd die gebruikers wel degelijk relevant vonden. Er is ook een ongebruikte derde dataset met impliciete ratings, naast de reeds gebruikte twee datasets met impliciete en expliciete ratings. Deze dataset beslaat een veel langere periode (iets meer dan elf maanden). In de accuraatheidsevaluaties wordt er echter geen direct gebruik gemaakt van de grote datasets. Deze grote dataset kan wel gebruikt worden in de evaluaties door ze op te splitsen in verscheidende disjuncte training- en testing-subdatasets, om zo het echte gedrag van het aanbevelingssysteem te modelleren en een beeld te krijgen van hoe groot de trainingsset best moet genomen worden en hoe lang een model nog goede resultaten blijft geven. 0

1

2

3

4

5

6

7

8

9

(a)

(b)

(c)

(d)

Figuur 6.2: Evaluaties met tijdscomponent

Figuur 6.2 geeft een grafische voorstelling van hoe dergelijke evaluaties met tijdscomponent kunnen werken. Elke kolom stelt een week voor, en elke rij stelt een bepaalde manier van evalueren voor. De donkergrijze weken duiden op weken waarvan de data gebruikt wordt voor training; de lichtgrijze weken zijn weken waarbij het opgebouwde model gebruikt wordt. Op de eerste rij, (a), worden vier weken gebruikt voor training, en wordt het model dan gebruikt voor vier weken. In configuratie (b) wordt het model slechts voor twee weken gebruikt. In configuraties (c) en (d) worden slechts twee weken gebruikt voor het trainen van het model, en wordt dit model dan voor vier respectievelijk twee weken gebruikt.

6.6. Betere verwerking van impliciete ratings De manier waarop gebruiksgegevens naar impliciete ratings omgezet wordt, is momenteel zeer naïef: er wordt gebruik gemaakt van een sigmoïdale functie die bij (0, 12 ) start en (∞, 1) stopt. De exacte gebruikte formule is


( ) 1 1 2 p + · arctan (c) · 2 2 π Hierbij is c het aantal keer dat dit spel door deze gebruiker gespeeld werd, en p een exponent die toelaat om de vorm van de curve aan te passen. In de huidige implementatie werd p gelijkgesteld aan 1,5; grotere exponenten zouden voor een vlakkere curve zorgen. Zie Sectie 4.2 op pagina 22 in het implementatie-hoofdstuk voor details. Het kan nuttig zijn om andere vormen van de curve die gebruiksgegevens in impliciete ratings omzet, te gebruiken. In Sectie 4.2 van de het implementatiehoofdstuk werden enkele alternatieve vormen van deze curve voorgesteld. Zoals in het evaluatiehoofdstuk echter reeds vermeld werd, kan de impact van de methode die gebruikt wordt om gebruiksdata in impliciete ratings om te zetten, niet eenvoudig geëvalueerd worden, en dus is het enkel nuttig om alternatieve methoden te implementeren wanneer er betere manieren om deze methoden te evalueren beschikbaar zijn. Wanneer gebruik gemaakt wordt van impliciete ratings, is het waarschijnlijk een goed idee om steeds een model op te bouwen aan de hand van data van een beperkte periode. Het gedrag van gebruikers zal immers evolueren over tijd, en het zal steeds moeilijker worden om een accuraat model op te bouwen voor een steeds groter wordende dataset met trainingsgegevens. De grootte van de trainingsdataset wordt dus best beperkt tot een aantal weken of een aantal maanden. Het is ook mogelijk om toch een dataset te gebruiken die een langere periode bestrijkt, maar dan de impact van impliciete ratings naargelang van tijd te laten afzwakken. De voorgestelde evaluaties in Sectie 6.5 zullen hierbij helpen om een duidelijker beeld te krijgen van de ideale lengtes van de trainings- en testsets. In de huidige implementatie wordt het aantal keer dat een object gebruikt werd, gebruikt om een rating voor een specifiek gebruiker/object-paar te construeren. Een betere manier zou waarschijnlijk gebruik maken van het aantal minuten dat een gebruiker een object gebruikt heeft. Bijvoorbeeld: één keer een spel voor tien minuten spelen moet waarschijnlijk immers dezelfde impact hebben als tien keer dit spel voor één minuut spelen. Het gemiddeld aantal keer dat gebruikers een bepaald spel gespeeld hebben, kan ook in rekening gebracht worden. Op die manier kan er onderscheid gemaakt worden tussen grote en kleine spellen; sommige spellen zullen immers snel uitgespeeld zijn, terwijl andere spellen veel langer gespeeld kunnen worden voor ze uitgespeeld zijn.

I

49

A. INHOUD VAN DE CD-ROM

De cd-rom die bij dit boek geleverd is, bevat de volledige broncode van het systeem, alsook de broncode van twee bibliotheken die door het systeem gebruikt worden. De twee gebruikte bibliotheken zijn json-framework1 , een bibliotheek voor het parsen van JSON-bestanden zoals het configuratiebestand, en uctest2 , een bibliotheek die het eenvoudig maakt om geautomatiseerde correctheidstests uit te voeren in C en Objective-C. Verder bevat de cd-rom ook alle andere zaken die nodig zijn om het systeem nuttig te kunnen gebruiken. Dit omvat het SQL-script dat de databasetabellen aanmaakt en de datasets importeert (scripts/import.sql), de scripts voor het uitvoeren van de evaluaties (scripts/evaluate), het analyseren van de resultaten (scripts/reformat) en het maken van de grafieken corresponderend met de evaluatieresultaten (scripts/plot). De gebruikte datasets maken geen deel uit van de cd-rom.

1 2

http://code.google.com/p/json-framework/ http://projects.stoneship.org/hg/uctest

I

50

VERKLARENDE WOORDENLIJST

Aanbeveler

Object dat in staat is om aanbevelingen te maken voor een gegeven gebruiker

Aanbeveling Object dat voor een specifieke gebruiker aanbevolen wordt omdat de kans dat deze gebruiker het object goed zal bevinden, groot genoeg geacht wordt Audience-based filtering Techniek waarbij de gelijkaardigheid van twee objecten afhankelijk is van de overlap in eigenschappen van het publiek dat gebruikt maakt van deze objecten Collaborative filtering Techniek waarbij de gelijkaardigheid van twee objecten afhankelijk is van hoe sterk het gebruiksgedrag van deze objecten overeenstemt Content-based filtering Techniek waarbij de gelijkaardigheid van twee objecten afhankelijk is van de overlap in eigenschappen van deze objecten Coördinator Object dat aanvragen voor het genereren van aanbevelingen distribueert over verschillende aanbevelers en de gegenereerde aanbevelingen combineert Databron Object dat instaat voor het opvragen van data uit databanken, caches, e.d., alsook het aanmaken en het aanpassen van modellen voor modelgebaseerde aanbevelers Expliciete ratings Ratings die afgeleid zijn uit ratings die expliciet door gebruikers zijn opgegeven (bijvoorbeeld door middel van rating-sterren) Gelijkaardigheidsmodel Model dat gebruikt maakt van gelijkaardigheden (op basis van gedrag van het publiek, eigenschappen van het publiek of eigenschappen van de objecten zelf) tussen objecten om aanbevelingen te kunnen maken Impliciete ratings Model

Ratings die afgeleid zijn uit het gebruiksgedrag van gebruikers

Datastructuur die gebruikt wordt om op een snelle manier aanbevelingen te genereren

I

51

BIBLIOGRAFIE

[1] Netlog NV. Over Netlog. http://nl.netlog.com/go/about, 2010. [2] Badrul Sarwar, George Karypis, Joseph Konstan, and John Reidl. Item-based collaborative filtering recommendation algorithms. In WWW ’01: Proceedings of the 10th international conference on World Wide Web, pages 285–295, New York, NY, USA, 2001. ACM. [3] Toby Segaran. Programming collective intelligence. O’Reilly, 2007. [4] Wired. Last.fm: Music to Listeners’ Ears. http://www.wired.com/culture/lifestyle/ news/2003/07/59522, 2003. [5] John S. Breese, David Heckerman, and Carl Kadie. Empirical analysis of predictive algorithms for collaborative filtering. pages 43–52. Morgan Kaufmann, 1998. [6] Robin Burke. Hybrid recommender systems: Survey and experiments. User Modeling and UserAdapted Interaction, 12(4):331–370, November 2002. [7] Bradley N. Miller, Joseph A. Konstan, and John Riedl. Pocketlens: Toward a personal recommender system. ACM Trans. Inf. Syst., 22(3):437–476, 2004. [8] Daniel Lemire and Anna Maclachlan. Slope one predictors for online rating-based collaborative filtering. In Proceedings of SIAM Data Mining (SDM’05), 2005. [9] Badrul M. Sarwar, George Karypis, Joseph A. Konstan, and John T. Riedl. Application of dimensionality reduction in recommender system - a case study. In In ACM WebKDD Workshop, 2000. [10] Thomas Hofmann. Probabilistic latent semantic indexing. In SIGIR ’99: Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, pages 50–57, New York, NY, USA, 1999. ACM. [11] Ruslan Salakhutdinov and Andriy Mnih. Probabilistic matrix factorization. In Advances in Neural Information Processing Systems, volume 20, 2008. [12] Michael J. Pazzani and Daniel Billsus. Content-based recommendation systems. In The Adaptive Web, volume 4321 of Lecture Notes in Computer Science, pages 325–341. Springer Berlin Heidelberg, 2007. [13] Miha Grčar. User profiling: Collaborative filtering. In Proceedings of the 7th International Multiconference Information Society IS 2004, volume 4, pages 75–78, October 2004.

I

52

[14] Miha Grčar, Bla Fortuna, Dunja Mladeni, and Marko Grobelnik. kNN versus SVM in the collaborative filtering framework. In Data Science and Classification, Studies in Classification, Data Analysis, and Knowledge Organization, pages 251–260. Springer Berlin Heidelberg, 2006. [15] Justin Basilico and Thomas Hofmann. Unifying collaborative and content-based filtering. In ICML ’04: Proceedings of the twenty-first international conference on Machine learning, page 9, New York, NY, USA, 2004. ACM. [16] Zhonghang Xia, Yulin Dong, and Guangming Xing. Support vector machines for collaborative filtering. In ACM-SE 44: Proceedings of the 44th annual Southeast regional conference, pages 169–174, New York, NY, USA, 2006. ACM. [17] Tong Zhang and Vijay S. Iyengar. Recommender systems using linear classifiers. J. Mach. Learn. Res., 2:313–334, 2002. [18] Moses S. Charikar. Similarity estimation techniques from rounding algorithms. In STOC ’02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 380–388, New York, NY, USA, 2002. ACM. [19] Abhinandan S. Das, Mayur Datar, Ashutosh Garg, and Shyam Rajaram. Google news personalization: scalable online collaborative filtering. In WWW ’07: Proceedings of the 16th international conference on World Wide Web, pages 271–280, New York, NY, USA, 2007. ACM. [20] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In STOC ’98: Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 604–613, New York, NY, USA, 1998. ACM. [21] Paul te Braak, Noraswaliza Abdullah, and Yue Xu. Improving the performance of collaborative filtering recommender systems through user profile clustering. In WI-IAT ’09: Proceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, pages 147–150, Washington, DC, USA, 2009. IEEE Computer Society. [22] Fiona Fui-Hoon Nah. A study on tolerable waiting time: how long are web users willing to wait? In Behaviour & Information Technology, volume 23, pages 153–164, 2004. [23] Apple. The Objective-C Programming Language. http://developer.apple.com/Mac/ library/documentation/Cocoa/Conceptual/ObjectiveC/ObjC.pdf, October 2009. [24] Wikipedia. Objective-C — Wikipedia, The Free Encyclopedia. http://c2.com/cgi/wiki? ObjectiveCee, Januari 2010. [25] The PHP Group. Php. http://php.net/, May 2010. [26] Anonymous. ObjectiveCee — Portland Pattern Repository. http://c2.com/cgi/wiki? ObjectiveCee, Februari 2007. [27] MySQL. http://www.mysql.com/, Januari 2010. [28] MySQL: Legal Policies. http://www.mysql.com/about/legal/, Februari 2010. [29] libdrizzle. https://launchpad.net/libdrizzle, Januari 2010. [30] Denis Defreyne. “bad packet” bug in Drizzle Client & Protocol Library. https://bugs. launchpad.net/libdrizzle/+bug/528410, May 2010.

I

53

[31] Jonathan L. Herlocker, Joseph A. Konstan, Loren G. Terveen, and John T. Riedl. Evaluating collaborative filtering recommender systems. ACM Trans. Inf. Syst., 22(1):5–53, 2004. [32] James A. Hanley and Barbara J McNeil. The meaning and use of the area under a receiver operating characteristic (ROC) curve. Radiology, 143(1):29–36, 1982.

I

54

LIJST VAN FIGUREN

2.1 2.2 2.3 2.4 2.5

Algemeen schema van SVD . . . . . . . . . . Voorbeeld van hypervlakken in SVMs . . . . Voorbeeld van het gebruik van de kernel trick Gebruik van SVM voor collaborative filtering Classificatie van aanbevelingssystemen . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. 8 . 9 . 10 . 11 . 14

3.1 3.2

Overzicht van de verschillende lagen in de architectuur . . . . . . . . . . . . . . . . . . 16 Bouwen van aanbevelingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4.1 4.2 4.3 4.4 4.5 4.6

Mapping van gebruik op rating . . . . . . . . . . . . . . Normaliseren van expliciete ratings . . . . . . . . . . . Aanbevelersklassen . . . . . . . . . . . . . . . . . . . . Voorbeeld van ABF . . . . . . . . . . . . . . . . . . . . . Databronklassen . . . . . . . . . . . . . . . . . . . . . . De geïmplementeerde GUI- en commandline-frontends

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

23 24 25 29 30 32

5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 5.10 5.11 5.12

Predictie met CF met expliciete ratings . . . . . . . . . . Predictie met CF met impliciete ratings . . . . . . . . . . Predictie met CBF/ABF met expliciete ratings . . . . . . . Predictie met CBF/ABF met impliciete ratings . . . . . . . Voorbeelden van ROC-curves . . . . . . . . . . . . . . . . Aanbeveling met CF met expliciete ratings . . . . . . . . . Aanbeveling met CF met impliciete ratings . . . . . . . . Aanbeveling met CBF/ABF met expliciete ratings . . . . . Aanbeveling met CBF/ABF met impliciete ratings . . . . . Aanbeveling met CF met impliciete ratings met aantal 15 Predictie met CF met impliciete ratings met aantal 15 . . Vergelijkingen in uitvoeringstijd . . . . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

35 35 36 36 37 40 40 41 41 42 42 43

6.1 6.2

Mogelijk gebruik van SVM voor audience-based filtering . . . . . . . . . . . . . . . . . . 46 Evaluaties met tijdscomponent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

I

55

LIJST VAN TABELLEN

2.1 2.2 2.3

Voorbeeld van een item-based collaborative filtering matrix . . . . . . . . . . . . . . . . 7 Voor- en nadelen van de besproken technieken . . . . . . . . . . . . . . . . . . . . . . . 14 Vergelijking van verschillende Collaborative Filtering-technieken . . . . . . . . . . . . 14

ONTWERP VAN EEN RECOMMENDATIESYSTEEM VOOR HET AANBIEDEN VAN DIENSTEN OP SOCIALE NETWERKSITES

Recommend Documents