Real-time aanbevelingen voor nieuws

Powered by TCPDF (www.tcpdf.org)

Academiejaar 2013–2014

Faculteit Ingenieurswetenschappen en Architectuur Valentin Vaerwyckweg 1 – 9000 Gent

Real-time aanbevelingen voor nieuws

Masterproef voorgedragen tot het behalen van het diploma van Master in de industriële wetenschappen: informatica

Sam LEROUX Promotoren: Rudy STOOP Luc MARTENS Begeleider:

Toon DE PESSEMIER

VOORWOORD

ii

Voorwoord Deze thesis had niet tot stand kunnen komen zonder de hulp van mijn promotoren en begeleiders. Ik wil ze dan ook uitgebreid bedanken. In de eerste plaats gaat mijn dank uit naar Toon De Pessemier die de masterproef van begin tot einde in goede banen geleid heeft. Hij zorgde er ook voor dat ik mij reeds in de zomervakantie in de materie kon inwerken door een stage te doen. Het resultaat van deze stage bleek een grote hulp te zijn bij de masterproef zelf. Mijn interne promotor was Rudy Stoop. Hij coördineerde de masterproef en kon dankzij zijn uitgebreide ervaring veel handige tips geven. De tweede lezer was Veerle Ongenae, zij zorgde er samen met Rudy Stoop voor dat deze scriptie aan alle eisen voldoet. Deze masterproef werd uitgevoerd bij de onderzoeksgroep Wireless And Cable (WiCa) van de Universiteit Gent. Deze onderzoeksgroep wordt geleid door prof. Luc Martens. Ik wil dan ook hem bedanken voor de kans om deze masterproef te maken.

Sam Leroux, mei 2014

Realtime aanbeveling van nieuws Sam Leroux Universiteit Gent [email protected] mei 2014 Abstract Het aanbod van online nieuwsberichten is overweldigend. Naast de traditionele kranten zijn er ook veel gespecialiseerde niche blogs en sites die periodiek nieuwsberichten aanbieden. Wie up-to-date wil blijven zou verplicht zijn om alle deze bronnen periodiek te controleren. Een aanbevelingssysteem kan een handige hulp zijn. Dit systeem moet dan de nieuwsberichten filteren volgens de interesses van de gebruiker. Er is reeds veel onderzoek gedaan naar aanbevelingstechnieken en er zijn veel systemen die zich al in de praktijk bewezen hebben. Nieuws aanbevelen is echter veel moeilijker dan het aanbevelen van films, boeken of andere producten. Het grootste verschil is het vluchtige karakter van nieuws. De waarde van een artikel is het grootst vlak na het geschreven is en vermindert snel naarmate het artikel ouder wordt. Een succesvol aanbevelingssysteem voor nieuws moet dus in staat zijn om in realtime de aanbevelingen te kunnen berekenen, er is geen tijd om langdurige berekeningen op veel data te doen. Een andere factor die het aanbevelen van nieuws moeilijk maakt zijn de veranderende interesses van de gebruiker. Na een gebeurtenis met een grote impact wil de gebruiker hier artikels over lezen, zelfs al gaat het strikt genomen niet over een onderwerp waar hij vroeger reeds interesse in getoond heeft. Omdat de artikels direct aanbevolen moeten worden kan men geen gebruik maken van de meningen van andere gebruikers (collaborative filtering). Een goede oplossing is aanbevelingen doen op basis van de inhoud van het artikel (content based). Een content based aanbevelingssysteem voor nieuws heeft veel gemeenschappelijk met een zoekmachine. Beiden breken de tekst op in woorden die een gewicht krijgen volgens hun belangrijkheid in de tekst. Een zoekmachine is ontworpen om snel een antwoord op een complexe vraag te geven. In deze thesis wordt een aanbevelingssysteem voor nieuws ontworpen en ge¨ımplementeerd door te steunen op een zoekmachine. Artikels worden periodiek opgehaald en toegevoegd aan de index van de zoekmachine. Wil een gebruiker aanbevelingen ontvangen, dan bouwt het systeem automatisch een zoekopdracht op, op basis van de geschiedenis van de gebruiker. De zoekresultaten zijn de aanbevelingen. Het genereren van aanbevelingen wordt dus vertaald naar het opbouwen en uitvoeren van een zoekopdracht. Om ook de artikels over gebeurtenissen met een grote impact te kunnen aanbevelen bevat het systeem een component die in staat is om trending topics te detecteren, onderwerpen die momenteel veel meer in het nieuws komen dan wat verwacht zou worden op basis van het verleden. Een belangrijke factor in het ontwerp van het systeem is de schaalbaarheid, het systeem moet in staat zijn om grote hoeveelheden berichten snel te verwerken. Door te steunen op Apache Storm, een framework voor schaalbare systemen, wordt dit doel bereikt.

Keywords aanbevelingssystemen, big data, machine learning, Apache Storm, schaalbare systemen

Realtime news recommendations Sam Leroux Ghent University [email protected] may 2014 Abstract The amount of news articles available online is overwhelming. People do not only consume content from the traditional newspapers but also from specialized blogs and websites. To stay informed, users would have to check all these sources periodically. A recommender system would be a huge help. This system can filter the articles according to the interests of the user. A lot of research has been done on recommender systems and a lot of systems haven proven themselves in a production environment. Recommending news is a lot more complicated than recommending static content such as books or films. The biggest challenge is the short life span of a news article. A news article has the largest value right after it is published. The value diminishes rapidly as the article becomes older. A successful news recommender should be able to calculate recommendations in real time. There is no time for long calculations on big datasets. Another difficulty with recommending news is that it’s difficult to anticipate the user’s interests. After an event with a big impact, the user would like to read articles about it, even if the event doesn’t really fit into his traditional interests. News articles have to be recommended as soon as they are published by the newspaper or website. Because the article is brand new, there are no ratings available from other users. Traditional techniques based on these ratings such as collaborative filtering are of no use in this context. Other techniques that take properties of the items themselves into account (content based) are able to recommend articles the moment they become available. Content based techniques for recommending news have a lot in common with a traditional search engine. Both systems extract tokens from the input text and attach a certain weight to these tokens. A search engine is designed to answer complicated questions quickly. In this thesis, a search engine is used as the foundation for building a recommender system. Periodically, articles are fetched from different news sources and are added to the index of the search engine. When the user requests recommendations, the system automatically builds a large search query based on the history of the user. The search engine executes this query. The search results are the recommendations. To be able to detect events with a big impact, the system contains a component to extract trending terms from the documents. An important consideration is the scalability of the system. The system should be able to handle large amounts of data as quickly as possible. This is achieved by using Apache Storm, a framework to build scalable applications.

Keywords recommender systems, big data, machine learning, Apache Storm, scalable systems

INHOUDSOPGAVE

v

Inhoudsopgave Voorwoord

ii

Nederlandstalige abstract

iii

Engelstalige abstract

iv

Inhoudsopgave

v

1 Inleiding 1.1 Probleemstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Doelstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Overzicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 1 2 3

2 Achtergrond 2.1 Aanbevelingssystemen . . . . . . . . . . . . . . . 2.1.1 Architectuur van een aanbevelingssysteem 2.1.2 Aanbevelingsalgoritmen . . . . . . . . . . 2.1.3 Gebruikersfeedback . . . . . . . . . . . . . 2.2 Nieuws aanbevelen . . . . . . . . . . . . . . . . . 2.3 Vergelijkbare systemen . . . . . . . . . . . . . . . 2.3.1 Grouplens . . . . . . . . . . . . . . . . . . 2.3.2 Newsdude . . . . . . . . . . . . . . . . . . 2.3.3 Ænalyst . . . . . . . . . . . . . . . . . . . 2.3.4 Google news . . . . . . . . . . . . . . . . . 2.3.5 SCENE . . . . . . . . . . . . . . . . . . . 2.3.6 Twitter . . . . . . . . . . . . . . . . . . . 2.3.7 Digg . . . . . . . . . . . . . . . . . . . . . 2.3.8 Overige . . . . . . . . . . . . . . . . . . .

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

4 4 5 6 9 10 11 12 12 12 13 13 13 14 14

3 Ontwerp 3.1 Overzicht van de architectuur . . . . . . . . . . . . . . . . . . . . . . . . .

16 16

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

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

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

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

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

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

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

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

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

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

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

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

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

INHOUDSOPGAVE . . . . . . . . .

17 17 19 19 21 21 21 21 22

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

23 23 23 25 25 26 27 27 30 30 30 31 31 31 32 34 35 35 38 38

. . . .

40 40 41 43 45

6 Testen en benchmarks 6.1 Geautomatiseerd testen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1.1 Resultaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47 47 48

3.2

3.1.1 Nieuws ophalen . . 3.1.2 Aanbevelen . . . . 3.1.3 Detectie belangrijke 3.1.4 Clustering . . . . . 3.1.5 Gebruikersinterface 3.1.6 Gebruikersfeedback Aanvullende eisen . . . . . 3.2.1 Schaalbaarheid . . 3.2.2 Uitbreidbaarheid .

vi . . . . . . . . . . . . . . . . . . gebeurtenissen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

4 Implementatie 4.1 Algemeen . . . . . . . . . . . . . . . . . . . . . 4.2 Nieuws ophalen . . . . . . . . . . . . . . . . . . 4.3 Zoekmachine . . . . . . . . . . . . . . . . . . . 4.3.1 Mogelijkheden . . . . . . . . . . . . . . . 4.3.2 Vergelijking performantie Lucene en Solr 4.3.3 Keuze . . . . . . . . . . . . . . . . . . . 4.3.4 Verwerking van artikels . . . . . . . . . . 4.4 Clustering . . . . . . . . . . . . . . . . . . . . . 4.4.1 Apache Mahout . . . . . . . . . . . . . . 4.4.2 Carrot2 . . . . . . . . . . . . . . . . . . 4.4.3 Hiërarchische clustering . . . . . . . . . 4.5 Gebruikersinterface . . . . . . . . . . . . . . . . 4.5.1 Algemeen . . . . . . . . . . . . . . . . . 4.5.2 Adaptieve layout . . . . . . . . . . . . . 4.6 Schaalbaarheid . . . . . . . . . . . . . . . . . . 4.6.1 Batch processing met Mahout . . . . . . 4.6.2 Realtime processing met Storm . . . . . 4.6.3 Lucene . . . . . . . . . . . . . . . . . . . 4.7 Detectie belangrijke gebeurtenissen . . . . . . . 5 Uitbreidingen 5.1 Google trends . . . . . . . . 5.2 Twitter . . . . . . . . . . . . 5.3 Collaborative filtering . . . . 5.4 Ondersteuning van meerdere

. . . . . . . . . talen

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . . . .

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

. . . .

. . . . . . . . .

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

. . . .

. . . . . . . . .

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

. . . .

. . . . . . . . .

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

. . . .

. . . . . . . . .

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

. . . .

. . . . . . . . .

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

. . . .

. . . . . . . . .

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

. . . .

. . . . . . . . .

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

. . . .

. . . . . . . . .

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

. . . .

. . . . . . . . .

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

. . . .

. . . . . . . . .

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

. . . .

. . . . . . . . .

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

. . . .

. . . . . . . . .

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

. . . .

. . . . . . . . .

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

. . . .

INHOUDSOPGAVE 6.2

vii

Gebruikerstesten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.1 Resultaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Grootte van de Lucene-index . . . . . . . . . . . . . . . . . . . . . . . . . .

50 51 52

7 Besluit 7.1 Algemeen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Vernieuwende aspecten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Mogelijke verdere uitbreidingen . . . . . . . . . . . . . . . . . . . . . . . .

54 54 55 57

Bibliografie

58

Lĳst van figuren

67

6.3

INLEIDING

1

Hoofdstuk 1 Inleiding 1.1

Probleemstelling

Het online aanbod van nieuws is enorm groot. Dit nieuws is zowel afkomstig van de traditionele kranten als van gespecialiseerde blogs en websites. Het aantal gepubliceerde artikels per dag neemt ook continu toe. Een traditionele krant zoals The New York Times [1] publiceert ongeveer 350 artikels per dag [3] terwijl The Huffington Post [2] tot wel 1200 artikels per dag beschikbaar maakt [3]. The Huffington Post is een nieuwe speler op de nieuwsmarkt. Deze website werd opgericht in 2005 en is er sindsdien in geslaagd om een belangrijke plaats in het online nieuwslandschap te verwerven. The Huffington Post is niet verbonden met een traditionele krant en publiceert enkel online. Toch bereikt The Huffington Post meer mensen dan The New York Times [4]. Deze vergelijking toont de verschuiving aan van de manier waarop nieuws geconsumeerd wordt. Uit onderzoek bij 1480 volwassenen in de Verenigde Staten blijkt dat voor mensen tussen 18 en 50 jaar het Internet in 2013 de belangrijkste nieuwsbron was [5]. Online nieuws consumeren verschilt fundamenteel van het offline lezen van een krant. Een traditionele krant leest men volgens een vast ritueel waar er tijd voor uitgetrokken wordt. Online nieuwsconsumptie is meer gefragmenteerd, op momenten waar men enkele minuten tijd heeft zoals in een wachtrij haalt men een smartphone boven en leest men één enkel artikel [6].

1.2 Doelstelling

2

Figuur 1.1: Evolutie consumptie van nieuwsberichten [5]

1.2

Doelstelling

De vorige paragraaf gaf twee belangrijke problemen bij het consumeren van online nieuws. Aan de ene kant is het aanbod gigantisch groot, aan de andere kant heeft een gebruiker weinig tijd en is zijn aandacht schaars [37]. Het is dus cruciaal om snel een interessant artikel te vinden. Een aanbevelingssysteem kan een belangrijke hulp hierbij zijn. Dit aanbevelingssysteem moet dan het gigantische nieuwsaanbod filteren zodat de gebruiker snel relevante artikels kan terugvinden. Het doel van deze masterproef is het ontwerpen en implementeren van zo een systeem. Een geschikt systeem moet voldoen aan enkele eisen:

• De gebruiker moet gepersonaliseerde inhoud te zien krijgen. • Het aanbevelen moet in realtime gebeuren. Deze eis houdt in dat een artikel moet aanbevolen kunnen worden zodra het gepubliceerd wordt. • Het opvragen van aanbevelingen moet snel gaan.

1.3 Overzicht

3

• Het systeem moet eenvoudig schaalbaar zijn.

1.3

Overzicht

In dit hoofdstuk werd reeds geschetst wat het doel is van deze masterproef. In hoofdstuk 2 worden algemene aanbevelingssystemen besproken en wordt er uitgelegd wat het aanbevelen van nieuws moeilijk maakt. Hoofdstuk 3 verduidelijkt de architectuur van het systeem en gaat in op de ontwerpbeslissingen zonder de implementatiedetails te vermelden. Deze details komen aan bod in hoofdstuk 4. Hoofdstuk 5 beschrijft enkele uitbreidingen die geïmplementeerd werden om het systeem krachtiger te maken. In hoofdstuk 6 wordt er ingegaan op de manier waarop het systeem getest werd. Hoofdstuk 7 ten slotte bevat een overzicht van de belangrijkste kenmerken van het systeem en beschrijft de verschillen met andere systemen.

ACHTERGROND

4

Hoofdstuk 2 Achtergrond Dit hoofdstuk zorgt voor de nodige achtergrondinformatie om de werking van een aanbevelingssysteem te begrijpen. Eerst worden algemene aanbevelingssystemen beschreven. Er bestaan veel goede publicaties die deze algoritmen in detail beschrijven. Waar relevant wordt er dan ook naar de literatuur verwezen in plaats van in te gaan op de details. Na deze algemene technieken komt het aanbevelen van nieuws aan bod. Ten slotte wordt een overzicht geschetst van enkele bestaande aanbevelingssystemen voor nieuws en enkele interessante publicaties binnen het domein.

2.1

Aanbevelingssystemen

Aanbevelingssystemen (eng: Recommender systems) zijn toepassingen die suggesties kunnen doen in verband met bepaalde items waar een gebruiker in geïnteresseerd kan zijn [7]. Deze items kunnen materiële zaken zijn die een gebruiker kan kopen zoals cd’s of boeken maar kunnen ook minder tastbare zaken zoals reisbestemmingen of restaurants zijn. Aanbevelingsystemen bestaan al geruime tijd en hebben hun nut al vaak bewezen. De meeste aanbevelingsystemen worden gebruikt in één of andere webshop of online dienst. Ze helpen de klant om producten te ontdekken en zorgen zo voor een grotere omzet voor de webshop. Amazon, één van de grootste webshops ter wereld zet sterk in op aanbevelingssystemen, deze gaan van eenvoudige "meest gekocht in deze categorie" tot complexe algoritmen die trachten de persoonlijke interesses te leren [9]. Aanbevelingen blijven niet beperkt tot de online wereld, in 2010 startte de supermarktketen Colruyt met het sturen van gepersonaliseerde folders met kortingsbonnen naar klanten [8].

2.1 Aanbevelingssystemen

5

Een goed werkend aanbevelingssysteem is van grote waarde voor een bedrijf. Netflix [15], een Amerikaans bedrijf dat streaming van films aanbiedt, loofde in 2006 een prijs van 1 miljoen dollar uit aan wie een aanbevelingsysteem kon maken dat het bestaande systeem overtrof met 10% [16]. Netflix stelde een dataset van geanonimiseerde gebruikersgegevens ter beschikking en verschillende groepen onderzoekers gingen aan het werk. In september 2009 eindigde de wedstrijd. Er waren verschillende teams die de doelstelling gehaald hadden. Een pittig detail is dat het winnende algoritme nooit in productie geïmplementeerd werd, de extra vereiste rekenkracht was veel groter dan de extra opbrengst [17]. Dit toont aan dat het ontwerpen van een aanbevelingsysteem meer is dan gewoon items aanbevelen. Een belangrijk detail is ook hoe duur een systeem is om te implementeren of te laten werken. Aanbevelingssytemen vereisen meestal complexe berekeningen op grote hoeveelheden gegevens. Elk systeem dat in de praktijk gebruikt moet kunnen worden, moet dus in staat zijn om grote datasets op korte termijn te verwerken. Om dit doel te bereiken wordt er momenteel veel onderzoek gedaan naar technieken om berekeningen te distribueren over verschillende machines [11], [12], [13], [94].

2.1.1

Architectuur van een aanbevelingssysteem

Elk aanbevelingssysteem heeft een vergelijkbare structuur. Ze hebben allemaal een datastructuur met de aan te bevelen items en één met gebruikersinformatie. Op basis van deze twee databanken genereert een algoritme dan aanbevelingen. Nadat de items aanbevolen werden kan de consument feedback geven en kan het systeem zijn modellen aanpassen.

Figuur 2.1: Architectuur van een aanbevelingssysteem


2.1.2

6

Aanbevelingsalgoritmen

Er bestaan verschillende manieren om aanbevelingen te genereren. Deze gaan van eenvoudige niet-gepersonaliseerde statistieken tot complexe modellen die zich aanpassen aan het gebruikersgedrag. Deze gepersonaliseerde algoritmen splitst men traditioneel op in twee families: de collaborative filtering technieken en de content based algoritmen [18]. Tegenwoordig zijn er echter ook nieuwe technieken ontwikkeld die niet echt meer passen binnen deze onderverdeling. Niet-gepersonaliseerde technieken. Dit zijn heel eenvoudige statistieken zoals de tien meest gelezen artikels. Ze vereisen nauwelijks aanpassingen om ze in een bestaande omgeving in te passen en kunnen toch al een goede start zijn. Collaborative filtering. Collaborative Filtering (CF) is een veelgebruikte verzameling van aanbevelingsalgoritmen. Het basisidee is dat als twee gebruikers vergelijkbare ratings gegeven hebben aan dezelfde items, we de rating voor een ander item voor de ene gebruiker kunnen voorspellen aan de hand van de rating van de andere gebruiker voor dat item. Men gaat er dus van uit dat mensen die in het verleden een gelijkaardig gedrag vertoonden, dit ook in de toekomst zullen doen. Collaborative filtering is een krachtige techniek die vaak in de praktijk heel goede resultaten geeft. Er zijn echter enkele problemen waar CF geen pasklaar antwoord op heeft. Het grootste probleem met CF staat bekend als het cold start probleem [14]. Dit doet zich voor als het systeem niet voldoende informatie heeft om een goede aanbeveling te doen. Dit kan voorkomen indien er aanbevelingen moeten gegenereerd worden voor een nieuwe gebruiker. Deze gebruiker kan nog niet vergeleken worden met andere gebruikers en er kunnen dus geen gelijkenissen ontdekt worden. Dit zelfde probleem doet zich voor als er een nieuw item in het systeem opgenomen moet worden. er is dan nog niet bekend welk type gebruiker in dit artikel geïnteresseerd is en men kan dus nog geen aanbevelingen doen. Het cold start probleem laat ook zien dat het succes van de aanbevelingen afhangt van de hoeveelheid gebruikers binnen het systeem, hoe meer gebruikers, hoe meer vergelijkbare gebruikers en hoe beter de aanbevelingen zullen zijn [43]. Een probleem dat hier mee samenhangt wordt in de literatuur vaak het grey sheep probleem genoemd: een gebruiker met atypische interesses zal weinig of geen gelijkaardige gebruikers hebben in een klein systeem en zal dus geen goede aanbevelingen kunnen ontvangen [66].


7

Dit probleem toont al een onderverdeling van de CF technieken aan. Aan de ene kant zijn er de user-user collaborative filtering technieken die items aanbevelen die vergelijkbare gebruikers goed beoordeeld hebben. Aan de andere kant zijn er de item-item CF technieken die items aanbevelen die vergelijkbaar zijn met items waar de gebruiker een goede rating aan gegeven heeft [7]. De gelijkenis tussen twee gebruikers wordt bepaald door het aantal items waar beide gebruikers een gelijkaardige score hebben aan gegeven. De gelijkenis tussen twee items wordt bepaald door het aantal gebruikers die een gelijkaardige score hebben gegeven aan beide items. De belangrijkste vaststelling die gemaakt moet worden is dat er geen rekening gehouden wordt met attributen van de items zelf. De gelijkenissen worden enkel op basis van gebruikersgedrag bepaald. Collaborative filtering technieken hebben als groot voordeel dat ze onafhankelijk van het toepassingsdomein kunnen werken. Het aanbevelingssysteem moet geen attributen van de items kennen, de aanbevelingen worden gegenereerd enkel uitgaande van het gebruikersgedrag. Dit laat toe om heel eenvoudig een bestaand aanbevelingssysteem in te bouwen in een bestaande toepassing. Collaborative filtering algoritmen zijn goede algemene technieken. Er is veel informatie over te vinden in de literatuur, enkele interessante publicaties zijn: [7], [9], [10] en [43]. Er zijn ook verschillende kant-en-klare implementaties beschikbaar die heel snel in een bestaand systeem ingevoegd kunnen worden ([84], [85]). Content based. De tegenhanger van CF staat bekend als content based (CB). Strikt genomen gebruikt deze enkel attributen van de items om zijn aanbevelingen te genereren. Er wordt voor elke gebruiker een profiel opgesteld dat aangeeft in welke specifieke waarden voor welke attributen de gebruiker geïnteresseerd is. Per definitie heeft dit type systeem nood aan domeinspecifieke informatie zoals het genre in een aanbevelingssysteem voor films of de prijsklasse in een systeem dat restaurants kan aanbevelen. Ook dit type systeem heeft te kampen met het cold start probleem: komt er een nieuwe gebruiker in het systeem, dan kunnen er nog geen aanbevelingen gedaan worden want het gebruikersprofiel is nog onbestaand. Dit systeem kan echter wel zonder problemen nieuwe items aan, elk nieuw item wordt voorzien van de domeinspecifieke attributen die het item karakteriseren en kan dus direct aanbevolen worden.


8

Het grootste probleem bij content based algoritmen is overspecialisatie. Het systeem zal items aanbevelen die heel gelijkaardig zijn aan reeds bekeken items. Dit kan een voordeel zijn maar vaak is het beter om verrassende aanbevelingen te doen, items die de gebruiker zelf niet zou ontdekken. Strikt genomen slaagt een CB-systeem hier niet in. Overspecialisatie kan ervoor zorgen dat enkel reeds bekeken items voldoen aan het profiel wat het aanbevelingssysteem vrijwel nutteloos maakt [37]. Een content based aanbevelingssysteem staat of valt met het labelen van de items. Elk item moet gekenmerkt worden door enkele passende attributen zodat het systeem in staat is om items te vergelijken. Dit is meestal geen probleem als alle items manueel ingebracht worden zoals bij een webshop. In systemen waar de inhoud afkomstig is van verschillende bronnen is deze extra informatie meestal niet beschikbaar en als ze al beschikbaar is, dan is ze meestal niet consistent tussen de bronnen. Het systeem moet dan zelf trachten om elk artikel te gaan kenmerken. Voor kleine systemen die niet tijdkritisch zijn, zou dit nog eventueel manueel kunnen gebeuren maar meestal moet dit geautomatiseerd gebeuren. Een groot voordeel van content based systemen is dat de nauwkeurigheid onafhankelijk is van het aantal gebruikers. Dit maakt onder andere het testen een stuk eenvoudiger. Een content based systeem kan in tegenstelling tot een collaborative filtering systeem ook goede aanbevelingen genereren voor gebruikers die geïnteresseerd zijn in niche onderwerpen (grey sheep). Interessante publicaties over content based aanbevelingssystemen zijn o.a [54], [68] en [7]. Hybride systemen. Zowel collaborative filtering als content based technieken hebben hun sterktes en zwaktes. Collaborative filtering is heel goed in het genereren van verrassende aanbevelingen maar heeft het cold start probleem als zwak punt. Een content based algoritme is in staat om nieuwe items direct aan te bevelen maar heeft last van overspecialisatie. Een logische manier om deze problemen op te lossen is om beide technieken te combineren tot een hybride systeem. Er bestaan verschillende technieken om hybride systemen op te bouwen [18]. De eenvoudigste manier is het afzonderlijk implementeren van een content based en een collaborative filtering systeem en de resultaten dan te combineren. Dit combineren kan opnieuw op verschillende manieren gebeuren. Men kan beide systemen in serie plaatsen zodat de uitvoer


9

van het ene systeem gefilterd wordt door het andere systeem of men kan ze in parallel plaatsen zodat beide systemen rechtstreeks uitvoer geven. Een andere mogelijkheid om een hybride systeem op te bouwen is het gebruiken van content based informatie binnen een CF-systeem. In dit type systeem wordt de gelijkenis tussen twee items dan zowel bepaald door hun inhoud als door het type gebruikers die het item bekijken. Ook omgekeerd kan men CF-informatie binnen een content based systeem inbouwen. Interessante publicaties over hybride systemen zijn o.a. [18], [19], [20], [37] en [56].

2.1.3

Gebruikersfeedback

Nadat de artikels aanbevolen werden is het cruciaal om feedback te krijgen van de gebruiker zodat het systeem zijn model kan aanpassen om later nog betere aanbevelingen te doen. Ook hiervoor bestaan er verschillende technieken. Deze worden vaak opgesplitst in twee groepen, de expliciete feedback en de impliciete feedback [35]. Expliciete feedback. De meest voor de hand liggende techniek om feedback van de gebruiker te krijgen is om er expliciet om te vragen. De gebruiker kan aangeven wat hij van het item vond door een score te geven. Traditioneel gebruikt men hier een schaal met vijf sterren voor. Deze techniek heeft als groot nadeel dat mensen meestal vrij extreem scores gaan geven, ze houden zich niet bezig met het verschil tussen 3 en 4 sterren maar geven enkel 1 of 5 sterren. Dit gedrag kan duidelijk teruggevonden worden in figuur 2.2 die de verdeling van de scores op YouTube toont. Onderzoek heeft uitgewezen dat metingen waar-

Figuur 2.2: Verdeling ratings op youtube [21]

bij aan de gebruikers gevraagd wordt om expliciet een score tussen één en vijf te geven een

2.2 Nieuws aanbevelen

10

vertekend beeld geven [33]. Een gebruiker interpreteert het verschil tussen een twee en een drie als veel kleiner dan het verschil tussen een vier en een vijf. Als we echt expliciet gebruik maken van deze scores in de berekeningen, dan zullen we onnauwkeurigheden introduceren. Een gedetailleerde schaal heeft dus weinig toegevoegde waarde. Een eenvoudiger alternatief is dan een binaire schaal (+/-) of zelfs één enkele knop (“vind ik leuk”). Een ander nadeel van expliciete feedback is dat het initiatief vraagt van de gebruiker, men mag er niet op rekenen dat elke gebruiker die een item bekijkt ook een expliciete rating geeft. In een systeem dat enkel expliciete feedback gebruikt zal de matrix die de score geeft voor een zeker item voor een zekere gebruiker dus vrij ijl zijn. Impliciete feedback. Naast het expliciet geven van scores kunnen andere acties ook een indicatie zijn van interesse. Het meest voor de hand liggende voorbeeld is het bekijken van een item of het zoeken op een zoekterm. Ook de tijd die de gebruiker op een zekere pagina gebleven is of het deel van een artikel of video dat de gebruiker bekeken heeft kan aangeven in welke mate de gebruiker geïnteresseerd is. Interessante publicaties over gebruikersfeedback zijn o.a. [30], [31], [32] en [34].

2.2

Nieuws aanbevelen

Nieuws aanbevelen verschilt sterk van het aanbevelen van andere inhoud zoals films en boeken. Het grootste probleem waar een systeem dat nieuwsberichten moet aanbevelen mee te kampen heeft is de vluchtigheid van de artikels. De waarde van een artikel is het grootst juist op het moment dat het artikel beschikbaar wordt. Na enkele uren is de waarde al sterk gedaald en zijn er nieuwe artikels die relevant worden. De belangrijkste eis aan een aanbevelingssysteem voor nieuws is dan ook dat het in staat moet zijn om in realtime de aanbevelingen te doen. Met realtime bedoelt men niet alleen dat het opvragen snel moet gebeuren maar vooral dat de artikels direct aanbevolen kunnen worden nadat ze gepubliceerd werden door een nieuwssite. Er is geen tijd om langdurige berekeningen uit te voeren vooraleer de artikels beschikbaar worden. Deze eis zorgt ervoor dat veel bestaande systemen niet toepasbaar zijn voor nieuws. Pure collaborative filtering technieken kunnen een artikel pas gaan aanbevelen nadat verschil-

2.3 Vergelijkbare systemen

11

lende mensen dit artikel gevonden hebben (cold start) en zijn dus niet bruikbaar voor nieuws. Pure content based technieken zonder extra maatregelen zijn ook niet bruikbaar omdat ze veel te gespecialiseerd artikels gaan aanbevelen. Bij nieuws gaat het per definitie om onverwachte gebeurtenissen. Een gebruiker kan tijdelijk wel sterk geïnteresseerd zijn in een bepaald onderwerp als dat onderwerp een grote impact heeft. Er bestaat als het ware een onderscheid tussen lange termijn interesses en interesses op korte termijn [42],[23]. De korte termijn interesses worden bepaald door belangrijke gebeurtenissen en veranderen snel. De lange termijn interesses zijn vrij constant voor een gebruiker [37]. Een goed nieuwsaanbevelingssysteem moet dus op één of andere manier detecteren welke gebeurtenissen belangrijk zijn en dus zeker moeten aanbevolen worden. Een andere factor die nieuws aanbevelen moeilijk maakt is dat het consumeren van nieuws een lage kost heeft. Deze kost is monetair, het artikel raadplegen is gratis maar het lezen van een artikel kost ook relatief weinig tijd. Dit zorgt ervoor dat de gebruiker veel artikels kan consumeren maar heeft als nadeel dat er ruis komt op zijn profiel. Bij een systeem waar het consumeren geld of veel tijd kost moet de gebruiker sterk gemotiveerd zijn vooraleer hij het item zal consumeren en dus is deze informatie een sterkere indicatie van zijn interesse [22]. Het is dus moeilijk om de interesses van de gebruiker te detecteren. Ook als men gebruik maakt van expliciete feedback moet men opletten. Wat is bijvoorbeeld de betekenis van een “vind ik leuk” klik bij een nieuwsartikel? Gaat het om een goed geschreven artikel of gaat het over een gebeurtenis die de gebruiker leuk vindt? En wat bij een goed geschreven artikel over een tragische gebeurtenis, gaat de gebruiker nog steeds op “vind ik leuk” klikken?

2.3

Vergelijkbare systemen

Er werd reeds veel onderzoek gedaan naar technieken om nieuws aan te bevelen. In deze paragraaf wordt er een kort overzicht geschetst van de belangrijkste publicaties binnen dit domein.


2.3.1

12

Grouplens

Dit is één van de eerste systemen die nieuws konden aanbevelen en dateert al van 1994 [44]. Het systeem was ontworpen om Usenet-berichten aan te bevelen. Hiervoor gebruikte het collaborative filtering. Er werd gebruik gemaakt van expliciete feedback (een score tussen één en vijf) maar ook van impliciete feedback (aantal seconden dat een gebruiker een bepaald artikel open heeft gehad). Eén van de problemen die ze ondervonden was dat er een vrij grote groep gebruikers nodig is om optimaal van collaborative filtering gebruik te kunnen maken. Dit zorgt er voor dat testen tijdens de ontwikkeling vrij moeilijk waren. Nog een belangrijke conclusie was dat expliciete feedback veel engagement van de gebruiker vraagt. In de eerste versie vroegen ze de gebruiker om een artikel een score te geven op basis van verschillende criteria (onderwerp, kwaliteit van de tekst, ...). Dit zorgde er natuurlijk voor dat gebruikers zich de moeite niet namen om die ratings te geven wat nefast is voor een collaborative filtering systeem.

2.3.2

Newsdude

Newsdude [47] is ook een vroege poging om een nieuwsaanbevelingssysteem te maken. Het is vooral interessant omdat het één van de eerste publicaties is die dieper ingaan op het verschil tussen korte- en langetermijn interesses. Newsdude gebruikt twee volledig gescheiden modellen om hiermee om te kunnen gaan. Newsdude is een content based systeem [48].

2.3.3

Ænalyst

Voor mensen die speculeren op de beurs is het van cruciaal belang om steeds up-to-date te zijn en om steeds de laatste nieuwsberichten te ontvangen. Het is dan ook logisch dat een aanbevelingssysteem voor nieuws in deze situatie een zeer handig hulpmiddel kan zijn. Ænalyst is een aanbevelingssysteem dat gericht is op het detecteren van gebeurtenissen die een effect hebben op de financiële markten [45]. Ænalyst probeert een verband te vinden tussen nieuwsartikels en veranderingen in de koers van een zeker aandeel. Het systeem probeert de tekst van het artikel te analyseren om dan later op basis van nieuwe artikels een effect op de koers te voorspellen. Artikels over gebeurtenissen met een groot effect op de koers van een aandeel worden aanbevolen. Een andere interessante publicatie die specifiek gericht is op het aanbevelen van financieel nieuws is [92].


2.3.4

13

Google news

Google news [38] is één van de meest populaire nieuwssites die miljoenen gebruikers van over de volledige wereld heeft [37]. Het is het beste voorbeeld van een succesvol aanbevelingssysteem voor nieuws. Collaborative filtering. De eerste versie van Google news gebruikte collaborative filtering [39]. Google News zou veel gebruikers hebben dus collaborative filtering leek een geschikte, krachtige techniek. Al snel ontdekte men dat collaborative filtering voor nieuws een niet zo goede techniek is. Het grootste probleem waar ze mee te kampen hadden was het “first-rater problem” [39],[37],[40]. Dit is het probleem dat reeds werd aangehaald, een artikel kan niet aanbevolen worden als het nog niet gelezen is door een andere gebruiker. Een ander probleem dat ze ontdekten was dat heel populaire items steeds aanbevolen worden zelfs al waren ze niet echt interessant voor de gebruiker [37]. Het voorbeeld dat gegeven wordt is dat van entertainment artikels. De kans is heel groot dat verwante gebruikers zo een artikel bekeken hebben en dat deze artikels dus aanbevolen worden. Hybride systeem. Al gauw zag men in dat collaborative filtering niet echt ideaal is om nieuws aan te bevelen. Men ging dan over naar een hybride systeem dat nog steeds sterk steunde op collaborative filtering maar dat extra technieken gebruikte om de problemen te overwinnen [37]. Meer specifiek gebruikte men een tweede score die aangaf in welke mate de gebruiker geïnteresseerd is in het onderwerp van het artikel. Men gebruikte een systeem dat een classificatie van een artikel kon doen om dit onderwerp te ontdekken.

2.3.5

SCENE

SCENE [48] is vooral interessant omdat er sterk de nadruk wordt gelegd op de schaalbaarheid van het systeem. Deze publicatie gaat ook dieper in op de nood om nieuwsartikels te clusteren. Het systeem bestaat uit twee niveaus waarbij het eerste niveau een overzicht van alle onderwerpen (clusters) is en het tweede niveau bestaat uit de artikels in de clusters [48].

2.3.6

Twitter

Er werd reeds aangehaald dat een nieuwsaanbevelingssysteem in staat moet zijn om trending topics te detecteren. Dit zijn onderwerpen of gebeurtenissen met een grote impact die veel gebruikers interesseren, zelfs al passen ze niet volledig binnen het gebruikersprofiel.


14

Om dit te kunnen doen zou men gebruik kunnen maken van Twitter [64]. Met Twitter kan men eenvoudig toegang krijgen tot de gedachten van miljoenen mensen [46]. Op deze manier kan men dus voorspellen over welke gebeurtenissen er veel artikels gelezen zullen worden. Buzzer. [46] is een aanbevelingsysteem dat sterk steunt op Twitter om interessante artikels te detecteren. Elke gebruiker moet zich in het begin op een aantal RSS-feeds abonneren. Buzzer gebruikt content based technieken om overeenkomsten te vinden tussen nieuwsartikels en tweets van personen die gevolgd worden door de gebruiker [46]. Andere interessante publicaties over het gebruik van Twitter om nieuws aan te bevelen zijn o.a. [49], [50], [58] [93] en [51]. Ook binnen deze thesis wordt er gebruik gemaakt van Twitter om de aanbevelingen te verbeteren. Deze uitbreiding wordt in hoofdstuk 5 besproken.

2.3.7

Digg

Digg [62] is een Amerikaanse website die (nieuws)artikelen publiceert op het gebied van wetenschap en technologie, politiek en amusement [63]. Digg verschilt van de andere systemen die hier behandeld werden omdat het in feite een soort van sociaal netwerk is. Gebruikers kunnen artikels up- en downvoten. Er gebeurt ook een manuele selectie van artikels voor de voorpagina. Digg heeft meer dan drie miljoen geregistreerde gebruikers [51] en is één van de succesvolste nieuwsaanbevelingssystemen. Digg wordt hier vermeld omdat tot nu toe de beste nieuwsaanbevelingssystemen, die in de praktijk ook gebruikt worden, nog steeds niet alles automatisch kunnen doen. Net zoals bij Digg wordt er nog vaak een manuele boost gegeven aan bepaalde artikels. Het doel van deze masterproef is echter om een volledig geautomatiseerd systeem te ontwerpen dat toch kan concurreren met de bestaande systemen.

2.3.8

Overige

Omdat een aanbevelingssysteem voor nieuws zo een handig hulpmiddel is, is er al heel veel onderzoek naar gedaan. Een zoektocht op Google Scholar naar “News recommendation” levert 1320 publicaties op die op de één of andere manier te maken hebben met het aanbevelen van nieuws. Er is hier niet genoeg plaats om een overzicht te geven van alle


15

interessante publicaties. Nog enkele die zeker ook de moeite zijn, zijn: • [52] dat dieper ingaat op enkele technische eigenschappen van een content based nieuwsaanbevelingssysteem. • [53] een heel recent en interessant artikel, puur over het clusteren van nieuwsberichten. Een ander artikel over het clusteren van nieuwsartikels is [57]. Hier ligt de nadruk op het incrementeel clusteren. • [22] een recent onderzoek naar hoe gebruikers van verschillende soorten websites aanbevelingen gebruiken. • [80] een thesis over het aanbevelen van nieuws, de nadruk ligt op het ontwerpen van de gebruikersinterface en de frontend. Deze thesis is complementair met het systeem dat hier besproken wordt, hier ligt de nadruk vooral op de backend en wordt de frontend bewust vrij eenvoudig gehouden. • [94] geeft een vrij compleet overzicht van de moeilijkheden bij het aanbevelen van nieuws en van de mogelijke technieken om nieuws aan te bevelen. Ook wordt er nagegaan hoe een aanbevelingssysteem voor nieuws getest kan worden. • [55] een interessant artikel over “open gebruikersprofielen” binnen een nieuwsaanbevelingsysteem. Er wordt nagegaan of de aanbevelingen die gegenereerd worden beter zijn als de gebruikers de mogelijkheid hebben om hun profiel aan te passen. Via experimenten wordt er aangetoond dat deze openheid een negatief invloed heeft op de kwaliteit van de aanbevelingen.

ONTWERP

16

Hoofdstuk 3 Ontwerp In dit hoofdstuk wordt de architectuur van het systeem beschreven zonder echt concreet in te gaan op de implementatie. Het doel is om de ontwerpkeuzes te verdedigen. De details in verband met de implementatie komen in het volgende hoofdstuk aan bod.

3.1

Overzicht van de architectuur

Figuur 3.1 toont een high level overzicht van de architectuur van het volledige systeem. In de volgende paragrafen wordt elk onderdeel afzonderlijk besproken.

Figuur 3.1: Overzicht architectuur

3.1 Overzicht van de architectuur

3.1.1

17

Nieuws ophalen

De eerste stap bestaat uit het ophalen van de nieuwsberichten. Periodiek moeten de websites van nieuwsbronnen gecontroleerd worden op nieuwe artikels. Indien er nieuwe artikels zijn, moet de inhoud opgehaald worden. Het is de bedoeling dat het nieuws afkomstig is van zoveel mogelijk bronnen, zowel van traditionele kranten en nieuwsagentschappen als van gespecialiseerde blogs en websites.

3.1.2

Aanbevelen

In het vorige hoofdstuk werden verschillende strategieën om aanbevelingen te doen kort uitgelegd. Collaborative filtering technieken zijn jammer genoeg moeilijk bruikbaar in het domein van nieuwsaanbeveling omdat ze er niet in slagen om een artikel direct aan te bevelen nadat het beschikbaar wordt. Wel bruikbaar zijn de content based algoritmen. Een content based algoritme heeft nood aan attributen van de artikels. Deze zijn onder andere de titel, het tijdstip waarop het artikel gepubliceerd werd en de volledige inhoud van het artikel. Een aanbevelingssysteem moet elk artikel intern karakteriseren door een aantal kernwoorden. Dit houdt in dat de tekst opgesplitst wordt in afzonderlijke eenheden (tokens). Op deze tokens moeten er dan enkele operaties uitgevoerd worden. Een eerste stap zou kunnen zijn om veel voorkomende woorden (stopwoorden) te verwijderen. Een andere stap is het herleiden van elk woord tot zijn stamvorm. Eens we de tokens hebben moet er een filtering gebeuren. We moeten nagaan welke woorden het artikel goed beschrijven en welke woorden nauwelijks iets te maken hebben met het onderwerp van het artikel. Al deze bewerkingen komen overeen met wat een zoekmachine doet bij het indexeren van pagina’s. Een goede manier om dit te implementeren zou dan ook zijn om uit te kijken naar een bestaande zoekmachine waar we deze functionaliteit van zouden kunnen lenen. Een content based aanbevelingssysteem heeft echter nog meer gemeenschappelijk met een zoekmachine dan enkel deze preprocessing bewerkingen. Om de uiteindelijke aanbevelingen te doen, moet het algoritme een profiel van de gebruiker vergelijken met de artikels. Artikels die veel gemeenschappelijk hebben met het profiel moeten dan aanbevolen worden. Het profiel is niet veel meer dan een lijst met termen die beschrijven waar de gebruiker reeds artikels over gelezen heeft. Elke term kan eventueel een zeker gewicht hebben. Het vergelijken van elk artikel met het profiel van de gebruiker zouden we dan kunnen zien als


18

het uitvoeren van een zoekopdracht die bestaat uit de termen in het profiel. We kunnen een content based aanbevelingssysteem dus simuleren door het uitvoeren van een zoekopdracht. Dit heeft enkele belangrijke voordelen ten opzichte van een traditioneel content based algoritme. Snelheid. Een zoekmachine is gemaakt om heel snel een antwoord te kunnen geven op een complexe vraag. Dit antwoord is een lijst van documenten die overeenkomen met de zoekopdracht. Een zoekmachine kan overweg met een gigantische hoeveelheid documenten en kan deze toch snel doorzoeken omdat er een efficiënte structuur opgebouwd wordt die dit toelaat (een inverted index [36]). Realtime gedrag. Het vorige puntje had betrekking op de tijd die het systeem nodig heeft om een antwoord te geven op de vraag voor aanbevelingen. Deze is natuurlijk heel belangrijk omdat het rechtstreeks de gebruiker beïnvloedt. In deze masterproef ligt echter de nadruk op het realtime aspect. Het systeem moet in staat zijn om een artikel op te nemen in de aanbevelingen van zodra het gepubliceerd wordt. Bestaande content based systemen hebben vrij veel tijd nodig om gelijkenissen tussen artikels te berekenen. Wanneer er een zoekmachine gebruikt wordt, kan het artikel wel heel snel beschikbaar gemaakt worden. Een zoekmachine bouwt een structuur op die het mogelijk maakt om snel, op basis van een zekere term, de artikels te vinden waar deze term in voorkomt [36]. Om een nieuw artikel beschikbaar te maken moet deze index aangepast worden, dit kan snel en efficiënt verlopen. Het artikel is dus direct beschikbaar nadat het gepubliceerd werd. Zuinig in plaatsgebruik. De zoekmachine heeft een heel efficiënte structuur om documenten op te slaan. Enkel de informatie die nodig is om het artikel terug te vinden moet opgeslagen worden. Een mogelijk probleem bij het gebruiken van een zoekmachine is overspecialisatie. Dit is een algemeen probleem bij content based systemen, maar door de manier waarop een zoekmachine werkt kan het in deze situatie nog een veel groter probleem vormen. In het allerslechtste geval voldoen enkel de reeds bekeken items aan het gebruikersprofiel. Er zullen dus maatregelen genomen moeten worden om dit probleem te vermijden.


3.1.3

19

Detectie belangrijke gebeurtenissen

Door te steunen op een zoekmachine zijn we in staat om een efficiënt content based aanbevelingssysteem op te bouwen. Eén van de eisen die we in hoofdstuk 1 aangehaald hadden was dat het systeem in staat moet zijn om artikels over gebeurtenissen met een grote impact te detecteren zodat deze aanbevolen kunnen worden zelfs al passen ze niet 100% in het gebruikersprofiel. We moeten dus trending topics kunnen detecteren, onderwerpen die momenteel vaker in het nieuws komen dan we zouden verwachten op basis van het verleden. Ook hier kunnen we dankbaar gebruik maken van de zoekmachine. Om artikels over trending topics te krijgen volstaat het een zoekopdracht uit te voeren die zoekt naar trending termen. Een belangrijke component in het systeem zal dus de component zijn die statistieken bijhoudt en die kan aangeven of een bepaald woord momenteel vaker voorkomt dan in het verleden.

3.1.4

Clustering

De nieuwsberichten zijn afkomstig van een groot aantal websites. De kans is dan ook heel groot dat verschillende bronnen een artikel publiceren dat over dezelfde gebeurtenis gaat. De artikels zijn wel verschillend maar ze vertellen hetzelfde verhaal. Stel dat het over een onderwerp gaat dat relevant is voor de gebruiker, dan mogen we toch niet beide artikels aanbevelen want op deze manier zouden we de aanbevelingen vervuilen met duplicaten. Een goede oplossing is het clusteren van artikels. Artikels die over de zelfde gebeurtenis gaan moeten in één cluster terecht komen. Per cluster mag er maar één artikel getoond worden. Er moet zeker een clustering doorgevoerd worden maar de vraag is waar deze past in de architectuur zoals geschetst in figuur 3.1. Helemaal in het begin. Deze oplossing ligt het meest voor de hand. Als er een nieuw artikel beschikbaar gemaakt wordt, plaatsen we het direct binnen een bestaande cluster. Als er geen cluster is die voldoende overlap heeft met het nieuwe artikel, moet er een nieuwe cluster gemaakt worden. We hebben dus nood aan een incrementeel clustering algoritme. Dit is geen probleem, er bestaan verschillende algoritmes die dit efficiënt kunnen doen [57], [59], [60], [61]. Deze manier van werken wordt in veel bestaande aanbevelingssystemen voor nieuws gebruikt (o.a. in [48] en [39]). Nadeel van deze manier van werken is dat het toevoegen van een artikel een vrij zware bewerking wordt, in principe moet dit nieuwe


20

artikel met elk ander artikel vergeleken worden vooraleer we kunnen beslissen aan welke cluster het toegekend kan worden. In de index. De meeste traditionele clusteringalgoritmen vereisen dat alle items vooraf bekend zijn. Een optie die het overwegen waard is, is om periodiek alle artikels in de index te herclusteren. Het voordeel is dat er eenvoudig bestaande technieken gebruikt kunnen worden en dat deze clustering eventueel zelfs eenvoudig gedistribueerd kan uitgevoerd worden. In de context van nieuwsaanbevelingen is dit geen goede oplossing omdat we zouden moeten wachten tot het clusteren voltooid is vooraleer we een nieuw item kunnen aanbevelen. Er bestaan nieuwsaanbevelingssystemen die deze optie gebruiken (o.a. [101]) maar deze slagen er dan niet in om in realtime de aanbevelingen te doen en zijn dus minder interessant. Helemaal op het einde. Deze techniek ligt niet zo voor de hand en werd niet teruggevonden in de literatuur. Hier zouden we elk artikel als een afzonderlijke eenheid opslaan in de index zonder iets van clustering toe te passen. Het aanbevelingssysteem geeft dan een verzameling artikels terug als de gebruiker hier om vraagt. Pas dan wordt er geclusterd, net voordat de artikels getoond worden aan de gebruiker. Het nadeel is dat de clustering bij elk verzoek uitgevoerd moet worden en dat er dus eventueel bepaald werk herhaald moet worden. Dit is echter veel minder erg dan het op het eerste zicht lijkt. De dataset waarop deze clustering moet toegepast worden is relatief klein (grootte-orde 100 artikels) waardoor de clustering vrij snel kan gebeuren. Nog belangrijker is het feit dat al deze artikels zich reeds in het geheugen bevinden, in de vorige twee opties moesten artikels van schijf gehaald worden vooraleer de clustering kon uitgevoerd worden. Het is deze optie die in het uiteindelijke systeem gebruikt wordt. Deze manier van werken heeft nog een belangrijk voordeel. De clustering is niet statisch maar wordt voor elke gebruiker afzonderlijk uitgevoerd. Dit laat toe om voor de ene gebruiker meer gedetailleerde clusters te maken dan voor een andere gebruiker. Als er verkiezingen zijn zal het systeem detecteren dat er extra veel berichten over politiek geschreven worden. Het systeem kan dan beslissen om artikels over de verkiezingsuitslag aan te bevelen, zelfs al is de gebruiker normaal niet geïnteresseerd in politiek. Voor deze gebruiker kunnen we al deze artikels gaan groeperen in één enkele cluster, terwijl deze artikels voor een andere gebruiker in verschillende gedetailleerde clusters opgedeeld moeten worden omdat deze meer interesse heeft in politiek.

3.2 Aanvullende eisen

3.1.5

21

Gebruikersinterface

In deze masterproef ligt de nadruk op het achterliggende systeem maar zonder een geschikte gebruikersinterface is een systeem waardeloos. Recente studies tonen aan dat de consumptie van nieuws (en van andere content) verschuift naar mobiele toestellen [6]. Om een echt bruikbaar systeem te hebben is het dus belangrijk dat gebruikers van mobiele toestellen het systeem eenvoudig kunnen gebruiken.

3.1.6

Gebruikersfeedback

In hoofdstuk 2 werden reeds de verschillende soorten feedback verduidelijkt (expliciete en impliciete feedback). Explicite feedback is minder geschikt bij het aanbevelen van nieuws. Een voetbalfan zal een artikel over een match waarin zijn favoriete ploeg verloren heeft geen hoge score geven terwijl het systeem wel artikels over deze ploeg zou moeten aanbevelen. In het uiteindelijke systeem wordt er enkel geregistreerd of de gebruiker een artikel langer dan 10 seconden open heeft gehad. Er wordt dus enkel impliciete feedback gebruikt. Er werd ook geëxperimenteerd met het meten van welk deel van het artikel de gebruiker bekeken heeft. Dit kan achterhaald worden door na te gaan waar de gebruiker zich bevindt binnen de webpagina aan de hand van de scrollpositie. Uit de experimenten bleek dat dit geen goede meetwaarden geeft, veel webpagina’s bevatten naast het artikel zelf ook nog extra inhoud zoals commentaar van gebruikers of links naar verwante artikels. Vaak blijkt het artikel zelf maar een heel klein deel van de pagina in te nemen. Zelfs als de gebruiker het volledige artikel leest zal hij maar een klein deel van de pagina bekeken hebben.

3.2

Aanvullende eisen

Naast de belangrijkste eisen in verband met de snelheid van het systeem zijn er nog enkele extra eisen waar het systeem aan moet voldoen.

3.2.1

Schaalbaarheid

De hoeveelheid gepubliceerde artikels is de afgelopen jaren enkel gestegen en er is geen reden om te verwachten dat dit in de volgende jaren niet zo zal zijn [3]. Het systeem moet dus zonder problemen in staat zijn om grotere volumes gegevens te verwerken. Alhoewel de verwerkingskracht van een systeem enkel maar stijgt kan het toch nodig zijn om berekeningen te gaan spreiden over verschillende toestellen. Het moet ook mogelijk zijn om

3.2 Aanvullende eisen

22

dynamisch extra toestellen toe te voegen aan de cluster om zo pieken in het verkeer op te vangen.

3.2.2

Uitbreidbaarheid

Dit is een belangrijke eis voor elk stuk software. Hier komt dit vooral neer op eenvoudig nieuwe aanbevelingsstrategieën kunnen toevoegen. Ook dit wordt eenvoudiger indien er gebruik gemaakt wordt van een zoekmachine. Een aanbevelingsstrategie is niet veel meer dan een methode om een zoekopdracht op te bouwen en is dus eenvoudig te implementeren.

IMPLEMENTATIE

23

Hoofdstuk 4 Implementatie In het vorige hoofdstuk werd de algemene structuur van het systeem geschetst. In dit hoofdstuk wordt er ingegaan op de implementatie en de keuzes die hierbij gemaakt werden.

4.1

Algemeen

Als programmeertaal voor het systeem werd er gekozen voor Java [29]. Java is een krachtige programmeertaal die dankzij allerlei bibliotheken bruikbaar is in praktisch alle domeinen.

4.2

Nieuws ophalen

De eerste stap in het aanbevelen van nieuws is natuurlijk het ophalen van de artikels. Hier kunnen we dankbaar gebruik maken van de RSS-functionaliteit die door bijna elke nieuwswebsite aangeboden wordt. Rich Site Summary (RSS) is een XML-taal die een web feed beschrijft [24]. Websites kunnen RSS feeds gebruiken om gebruikers in staat te stellen om nieuwe inhoud op te halen. Het volgende fragment toont een deel van een RSS-feed. Typisch bevat een RSS-feed één channel-element dat de feed beschrijft (titel, beschrijving) en meerdere item-elementen. Elk item-element stelt een artikel voor en bevat o.a. een titel, beschrijving, een link naar de volledige inhoud en eventueel een afbeelding.

4.2 Nieuws ophalen

24 Codefragment 4.1: Voorbeeld RSS [24]

< t i t l e>RSS T i t l e This i s an example o f an RSS f e e d h t t p : //www. someexamplerssdomain . com/main . html Mon, 06 Sep 2010 00 : 0 1 : 0 0 +0000 Mon, 06 Sep 2009 16 : 2 0 : 0 0 +0000 < t t l>1800 < t i t l e>Example e n t r y Here i s some t e x t c o n t a i n i n g an i n t e r e s t i n g d e s c r i p t i o n . h t t p : //www. w i k i p e d i a . or g / unique s t r i n g p e r item Mon, 06 Sep 2009 16 : 2 0 : 0 0 +0000 Een RSS-feed is een eenvoudig XML-bestand en dus kunnen de traditionele technieken om XML te verwerken eenvoudig gebruikt worden. Een betere manier echter is om een gespecialiseerde RSS-library te gebruiken om de feed te parsen. Deze kan beter overweg met fouten en biedt een eenvoudigere interface. Er zijn verschillende RSS-parsers beschikbaar voor Java. In dit project wordt Rome [67] gebruikt. Er werd voor Rome gekozen omdat dit de meest stabiele parser is en omdat er veel documentatie over beschikbaar is. Om steeds de meest recente nieuwsberichten te kunnen aanbevelen moet er vrij vaak gecontroleerd worden of er nieuwe berichten beschikbaar zijn. Niet elke nieuwsbron publiceert even vaak artikels, bij sommige bronnen komen er elke minuut artikels bij, andere bronnen publiceren enkele artikels per dag. Het is belangrijk om de frequentie waarmee er gecontroleerd wordt of er nieuwe artikels zijn aan te passen aan de frequentie waarbij die

4.3 Zoekmachine

25

bron de artikels publiceert. Om dit te doen werd er een heel eenvoudig mechanisme van exponential backoff [71] ingebouwd. Voor elke bron die gecontroleerd moet worden, wordt er een waarde bijgehouden die aangeeft om de hoeveel tijd deze controle moet gebeuren. Als de tijd verstreken is, wordt de RSS-feed opgehaald en indien er nieuwe artikels zijn, wordt de periode gedeeld door twee. Indien er geen nieuwe artikels beschikbaar zijn, wordt de periode verdubbeld. Uiteindelijk convergeert de periode naar een geschikte waarde. Dit is een eenvoudig algoritme maar het blijkt heel goed te werken. Op deze manier verlagen we de belasting voor de eigen systemen maar ook voor de servers die de RSS-feeds aanbieden.

4.3

Zoekmachine

In het vorige hoofdstuk werd reeds vermeld dat het systeem in staat is om de aanbevelingen in realtime te doen dankzij een zoekmachine. Er zijn verschillende opties om toegang te krijgen tot de functionaliteit van een zoekmachine.

4.3.1

Mogelijkheden

Lucene. Apache Lucene is een Java-bibliotheek die gebruikt kan worden om applicaties te maken die in staat zijn om grote hoeveelheden data snel te doorzoeken [25]. Lucene is geen kant-en-klare zoekmachine maar bevat wel de componenten die nodig zijn om een zoekmachine te bouwen. Lucene is de de facto standaard bibliotheek voor het ontwikkelen van complexe zoekmachines [28]. Solr. Apache Solr is een snelle open source zoekmachine die steunt op Lucene [26]. In tegensteling tot Lucene is dit wel een kant-en-klare oplossing. Solr biedt een (REST) webinterface aan om documenten te indexeren en om zoekopdrachten uit te voeren. Dankzij deze webinterface is het eenvoudiger om de belasting te spreiden over verschillende systemen mocht dit nodig zijn. Dit is natuurlijk een groot voordeel omdat schaalbaarheid één van de doelstellingen voor het systeem was. Nadeel van Solr is dat veel van de gespecialiseerde functionaliteit verborgen is achter een gebruiksvriendelijke webinterface. Dit is een groot voordeel wanneer Solr gebruikt moet worden als traditionele zoekmachine maar dit is hier niet het geval. Hier wordt er sterk gesteund op de functionaliteit van de zoekmachine maar wordt ze wel op een manier gebruikt waar ze niet echt voor ontworpen is. We hebben toegang tot de meer gespecialiseerde functionaliteit nodig en in Solr is deze minder eenvoudig toegankelijk dan bij Lucene.

4.3 Zoekmachine

26

Elasticsearch. Elasticsearch is een flexibele en krachtige open source zoekmachine [27]. Net zoals Solr steunt Elasticsearch op Lucene. Elasticsearch verbergt de details van Lucene achter een eenvoudige webinterface. Elasticsearch legt nog meer de nadruk op snelheid en flexibiliteit dan Solr. Nadeel is dat net zoals bij Solr de complexe functionaliteit van Lucene verborgen wordt. Dit is nog meer het geval dan bij Solr.

4.3.2

Vergelijking performantie Lucene en Solr

Elasticsearch kon jammer genoeg niet gebruikt worden omdat de applicatie toegang nodig heeft tot de ruwe informatie over de index. Voor elk artikel moet kunnen opgevraagd worden welke termen hierin voorkomen. Ook statistieken over de volledige index zijn nodig. Zo moeten we kunnen achterhalen hoeveel documenten een zekere term bevatten. In Elasticsearch is dit moeilijk te achterhalen. In Solr is dit iets eenvoudiger op te vragen. Lucene biedt wel eenvoudig toegang tot deze informatie. Een doorslaggevende factor in de keuze tussen Solr en Lucene is de performantie. Solr verpakt de functionaliteit van Lucene in een webinterface en dit veroorzaakt natuurlijk extra overhead. Om het verschil in performantie te testen werd er een proefopstelling opgesteld. Hiervoor werd er een dataset met 21578 artikels van Reuters [65] geïndexeerd. Hierna werden er zoekopdrachten uitgevoerd op deze index. Deze zoekopdrachten bestonden steeds uit de disjunctie (logische OF) van verschillende termen, elk met een eigen gewicht net zoals dit in het uiteindelijke systeem zou gebeuren. Het aantal termen werd steeds verhoogd met 50. Per aantal werd de test 300 keer uitgevoerd en werd de gemiddelde uitvoeringstijd berekend. De resultaten worden voorgesteld in 4.1. Deze grafiek vertoont duidelijk een lineair gedrag zowel voor Solr als voor Lucene. De performantie van Lucene is duidelijk een stuk beter.

4.3 Zoekmachine

27

Figuur 4.1: vergelijking performantie solr en lucene

4.3.3

Keuze

Alle drie de oplossingen zijn goede producten. Elasticsearch en Solr zijn duidelijk meer gericht op applicaties die een traditionele zoekmachine nodig hebben. Dit is hier niet het geval. We willen wel de functionaliteit van een zoekmachine gebruiken, maar de zoekmachine functioneert niet in haar natuurlijke habitat. Dit samen met de betere performantie van Lucene heeft ervoor gezorgd dat het uiteindelijk systeem Lucene gebruikt.

4.3.4

Verwerking van artikels

Er werd reeds aangehaald dat Lucene geen kant-en-klare zoekmachine is, ze bevat enkel de bouwstenen om zoekmachines op te bouwen. Dit zorgt ervoor dat er nog vrij veel werkt kruipt in het configureren en implementeren van bepaalde functionaliteit. Eén van de belangrijkste zaken is het aangeven van hoe Lucene nieuwe artikels moet verwerken. Het doel is om een groot stuk tekst op te splitsen in afzonderlijke delen (tokens) die later gebruikt kunnen worden om snel en efficiënt in de index te zoeken. Dit is ook van belang om trending topics te detecteren, van elk artikel moet achterhaald worden welke tokens dit artikel het best beschrijven zodat er statistieken kunnen bijgehouden worden die aangeven of een zekere term momenteel populair is of niet.

4.3 Zoekmachine

28

Een nieuw artikel ondergaat de volgende bewerkingen: Opsplitsen in tokens. De eenvoudigste techniek is splitsen op witruimte. Herleiden naar lower case. Alle tokens worden omgezet in lowercase. Verwijderen witruimte. Witruimte aan het begin en einde van tokens wegstrippen. Verwijderen van stopwoorden. Stopwoorden zijn woorden die zo vaak voorkomen dat ze waardeloos zijn voor Information Retrieval (IR) [76]. Voorbeelden van stopwoorden zijn “a”, “the”, “this” in het Engels of “de”, “het”, “zodat” in het Nederlands. Deze woorden kunnen gewoon weggelaten worden zonder dat de informatie-inhoud daalt. Het systeem gebruikt een vrij agressieve lijst met stopwoorden die bijvoorbeeld ook de namen van weekdagen en maanden bevat. Er werd ook nagegaan welke termen heel vaak voorkomen binnen een artikel (“editor”,“newspaper”,...) en deze werden ook toegevoegd aan de lijst met stopwoorden. Bezittelijke voornaamwoorden. Woorden zoals “his” en “mine” worden weggewerkt door de stopfilter, deze kan echter niet overweg met gereduceerde vormen. Hiervoor is er een extra filter nodig. Deze filter herleidt “Philip’s book” naar “Philip book”. Herleiden naar stamvorm. Deze filter zorgt ervoor dat “lopen”, “loop” en “gelopen” allemaal herleid worden naar een zelfde stam. Om dit te doen wordt er een Snowball stemmer gebruikt, dit is één van de meest krachtige stemming technieken [77]. Samengestelde begrippen. Indien enkel de vorige filters gebruikt worden zal “Coca Cola” opgesplitst worden in “coca” en “cola”. De klassieke manier om dit te vermijden is om gebruik te maken van n-grammen [78]. Men maakt ketens van telkens n tokens. Voor n = 2 zijn dit bigrammen, voor n = 3 zijn dit trigrammen. De zin “De president van Amerika is Barack Obama” wordt opgesplitst in [“De president”,“president van”,“van Amerika”,“Amerika is”,“is Barack”,“Barack Obama”] indien men bigrammen gebruikt. Dit voorbeeld toont aan dat deze techniek zeker goede resultaten kan teruggeven maar ook veel waardeloze resultaten geeft. Er werden tests uitgevoerd met bigrammen en trigrammen en daaruit bleek dat ze te veel ruis introduceerden om bruikbaar te zijn binnen dit aanbevelingssysteem. Om toch termen die bestaan uit verschillende woorden te detecteren moest

4.3 Zoekmachine

29

er dus een andere strategie verzonnen worden. De meeste van deze termen zijn namen van personen, plaatsen of organisaties. Een voor de hand liggende techniek is dan ook om een eenvoudige reguliere expressie te gebruiken die ketens van woorden zoekt die elk met een hoofdletter beginnen. Deze strategie zorgde voor veel betere resultaten en is bovendien ook sneller. Natuurlijk zijn er veel begrippen die samengesteld zijn uit verschillende woorden die niet met een hoofdletter beginnen. Deze worden dan niet opgepikt door dit systeem. Uit praktijktesten bleek echter dat dit geen al te groot probleem is, juist omdat binnen de context van nieuwsberichten de belangrijkste kernwoorden plaatsnamen en persoonsnamen zijn. De vorige stappen zorgen ervoor dat de volledige tekst van een artikel opgesplitst wordt in tokens. De volgende stap is het filteren van deze tokens zodat enkel de tokens die het artikel goed beschrijven overblijven. Lucene gebruikt hiervoor TFIDF [87]. TFIDF is een metriek om te achterhalen hoe belangrijk een zekere term voor een artikel binnen een verzameling artikels is [86]. TFIDF hecht een waarde aan elke term van een artikel, hoe hoger deze waarde, hoe belangrijker de term voor dit artikel. De TFIDF-score wordt bepaald aan de hand van twee metingen, de Term Frequency (TF) en de Inverse Document Frequency (IDF). De Term Frequency (TF) geeft aan hoeveel keer de term voorkomt in het artikel. Hoe vaker de term voorkomt, hoe groter de kans dat het een belangrijke term is. Deze veronderstelling gaat echter niet altijd op. Als een woord in veel documenten voorkomt is het geen goed kernwoord. TFIDF bestaat daarom naast de Term Frequency ook uit de Inverse Document Frequency (IDF). Deze meet in hoeveel artikels deze term voorkomt. Hoe groter dit aantal, hoe kleiner de IDF. De uiteindelijke TFIDF-score is het product van de TF en de IDF. De TFIDF-waarde is dus het grootst voor termen die vaak voorkomen in het artikel dat bekeken wordt maar die relatief zeldzaam zijn in de andere artikels. De formule maakt dit duidelijk: T F IDF (t, d, D) = T F (t, d) ∗ IDF (t, D)

Er wordt nagegaan hoe belangrijk een term t is voor een document d binnen een verzameling documenten D. De score is evenredig met het aantal keer dat de term voorkomt in het document en omgekeerd evenredig met het aantal documenten waar de term in voorkomt.

4.4 Clustering

30

Vaak neemt men een logaritme van de TF zodat een term die vier keer voorkomt niet voor dubbel zo veel meetelt als een term die twee keer voorkomt. TFIDF is een oude techniek en er zijn verschillende verfijningen, varianten en alternatieven (o.a. [88], [89], [90], [91]), toch wordt TFIDF nog veel gebruikt omdat het in de praktijk heel goede resultaten geeft en omdat het eenvoudig te implementeren is.

4.4

Clustering

In het vorige hoofdstuk werd vermeld dat de clustering niet op voorhand gedaan wordt maar dat ze op het moment van het opvragen van de aanbevelingen gebeurt. Het is dan ook van cruciaal belang dat deze clustering zo snel mogelijk verloopt. Er werden verschillende oplossingen vergeleken.

4.4.1

Apache Mahout

Apache Mahout is een Java-bibliotheek die toelaat om schaalbare systemen te maken die bepaalde machine learning taken uitvoeren. Mahout bevat implementaties van clustering algoritmen en leek dus een zeer interessante optie. Mahout is gemaakt om gigantische hoeveelheden data te kunnen verwerken. Er wordt dan ook verondersteld dat het geheugen niet groot genoeg is om al deze gegevens op te slaan en dat de invoer op schijf staat. Bij het clusteren van de aanbevelingen bevinden al de gegevens zich reeds in het geheugen. Om Mahout te kunnen gebruiken zou er eerst een bestand op schijf moeten aangemaakt worden dat kan dienen als invoer. Dit veroorzaakt te veel overhead zodat Mahout niet bruikbaar is.

4.4.2

Carrot2

Het genereren van aanbevelingen wordt gesimuleerd door het uitvoeren van een zoekopdracht. Het clusteren van de aanbevelingen komt dus overeen met het clusteren van zoekresultaten. Carrot2 [79] is een opensource bibliotheek die in staat is om zoekresultaten van Lucene of Solr te clusteren. Dit is dus exact wat we willen doen. Er werd dan ook relatief veel tijd besteed aan het experimenteren met Carrot2. Carrot2 is heel gebruiksvriendelijk en werkt heel goed bij een traditionele zoekmachine. Hier was echter meer controle nodig om nog extra optimalisaties door te voeren en dit liet Carrot2 niet toe. Carrot2 kon dus in het uiteindelijke project niet gebruikt worden.

4.5 Gebruikersinterface

4.4.3

31

Hiërarchische clustering

Als derde optie werd er een eenvoudig algoritme bekeken dat in staat is om een hiërarchische clustering door te voeren. Dit leek een goed idee omdat het veel mogelijkheden biedt. Er kan per gebruiker gekozen worden hoe gedetailleerd de clusters moeten worden. Het algoritme dat uiteindelijk gebruikt werd is een variant op deze hiërarchische clustering. Er wordt geen volledige boomstructuur opgebouwd maar de clustering wordt slechts tot op een zeker niveau doorgevoerd, dit zorgt voor een grote snelheidswinst. Ter informatie: het clusteren van 5000 artikels duurt ongeveer 500 ms. In de praktijk moeten er slechts een 250-tal artikels per keer geclusterd worden. Het is dus zeker geen probleem om de clustering op het laatste moment te doen, vlak voor de aanbevelingen worden doorgegeven aan de gebruiker.

4.5 4.5.1

Gebruikersinterface Algemeen

De consumptie van nieuws verschuift steeds meer naar mobiele toestellen [5],[6]. Het is dan ook heel belangrijk dat de clientapplicatie vlot werkt op handheld devices zoals tablets en smartphones. Een mogelijkheid zou een native applicatie zijn, een toepassing die specifiek geschreven is voor één platform zoals android of IOS. Dit heeft als groot nadeel dat de applicatie enkel op dit platform werkt en dat er dus verschillende versies zouden gemaakt moeten worden indien men verschillende besturingssystemen wil ondersteunen. De applicatie heeft echter geen toegang nodig tot de meer low level functionaliteit die beschikbaar is voor native applicaties. Een beter idee is dan ook om een webapplicatie te maken, een website die gebruik maakt van HTML5 en Javascript en die geoptimaliseerd is voor mobiele toestellen. Ook klassieke computersystemen zoals laptops en desktops kunnen dan zonder problemen de applicatie gebruiken. Een probleem bij mobiele toestellen is de beperkte schermgrootte. Een groter probleem is dat de schermgrootte voor verschillende toestellen sterk kan verschillen, een smartphone heeft een schermdiagonaal van ongeveer 5 inch, bij een tablet is dit al 12 inch en meer.


32

Het is dan ook niet voldoende om de layout te schalen, maar de layout moet zich volledig kunnen aanpassen aan de schermgrootte om zo optimaal mogelijk gebruik te kunnen maken van de beschikbare ruimte. Bij het opbouwen van de applicatie werd er handig gebruik gemaakt van JQuery Mobile [81]. JQuery Mobile (JQM) is een javascript bibliotheek die allerhande componenten bevat om eenvoudig een mooie layout op te bouwen die specifiek gemaakt is om bruikbaar te zijn op handheld devices. De artikels die aanbevolen worden zijn afkomstig van honderden verschillende nieuwswebsites en blogs. Er moet dus een manier gezocht worden om al deze artikels van verschillende bronnen op een gebruiksvriendelijke manier te tonen. Er werden verschillende opties overwogen: • Inhoud parsen en tonen. Hier tracht men om automatisch de tekst van het artikel uit te broncode te halen en toont men deze tekst op de eigen website. Dit is mogelijk maar foutgevoelig. Op deze manier verliest men ook alle opmaak en eventuele afbeeldingen of video’s. Deze manier van werken is trouwens ook in strijd met de gebruikersvoorwaarden van de meeste nieuwswebsites die niet toelaten dat de inhoud rechtstreeks overgenomen wordt op een andere website. • Enkel linken naar de nieuwswebsite. Het eigen systeem toont enkel de titel en een link naar de nieuwswebsite. De gebruiker kan het artikel dan rechtstreeks lezen op de nieuwswebsite. Dit is de eenvoudigste methode, maar als men op deze manier werkt verliest men de gebruiker direct zodra hij één artikel leest. Ook metingen van hoe lang de gebruiker het artikel bekeken heeft zijn niet meer mogelijk. • Combinatie. De beste manier is een combinatie van de vorige twee technieken. Het artikel wordt inclusief oorspronkelijke opmaak opgenomen in de eigen website. Hiervoor wordt een iframe gebruikt. De gebruiker ziet de oorspronkelijke website maar alles draait binnen de eigen webapplicatie.

4.5.2

Adaptieve layout

Zoals in de vorige paragraaf reeds vermeld werd, is de kans heel groot dat de gebruiker de applicatie zal gebruiken op één of ander mobiel toestel. Om een goede gebruikerservaring aan te bieden moet er dan ook verstandig omgesprongen worden met de mogelijkheden van


33

het toestel. De clientapplicatie is beschikbaar in twee verschillende layouts. De ene versie is geoptimaliseerd voor tablets en grotere schermen zoals laptops, desktops en smart-TV’s, de andere is specifiek gericht op de kleinere schermen van smartphones. Er wordt automatisch de best passende layout getoond op basis van het type toestel. Hiervoor werd er dankbaar gebruik gemaakt van de Media Query-functionaliteit die beschikbaar is in CSS3. Smartphone Bij een smartphone is de beschikbare ruimte vrij klein. De gebruiker verwacht de interface te kunnen bedienen met zijn duim. Er werd gekozen voor een eenvoudige lijst die alle artikels toont. Indien er een afbeelding beschikbaar is, wordt deze links van de titel getoond. Dankzij de clustering die hiervoor beschreven werd, worden artikels over het zelfde onderwerp gegroepeerd. Per cluster wordt enkel het meest recente artikel getoond in de lijst. De andere artikels zijn beschikbaar door te klikken op de knop die aangeeft hoeveel verwante artikels er zijn. Als de gebruiker op de titel klikt, wordt het artikel geopend. De nieuwswebsite wordt geladen binnen een iframe. De lijst verdwijnt en het artikel wordt op het volledige scherm getoond. Door te klikken op de “back”-knop, kan de gebruiker terugkeren naar de lijst met aanbevelingen.

(a) Overzicht aanbevelingen

(b) Artikel

Figuur 4.2: De gebruikersinterface op een smartphone

4.6 Schaalbaarheid

34

Tablet en grotere schermen Op een tablet is er een veel groter scherm ter beschikking. Hier is het dan ook mogelijk om de lijst met aanbevelingen en het artikel tegelijkertijd te tonen. Dit laat de gebruiker toe om heel snel naar een ander artikel te gaan. De grotere schermruimte laat ook toe om grotere knoppen te hebben. Waar de knoppen die getoond werden op een smartphone enkel kleine icoontjes bevatten, wordt er op een tablet ook tekst binnen deze knoppen getoond.

Figuur 4.3: De gebruikersinterface op een tablet

4.6

Schaalbaarheid

Er werd al verschillende keren aangehaald dat het uiteindelijke systeem heel eenvoudig schaalbaar moet zijn. Als het aantal artikels te groot wordt om stabiel op één enkel toestel te kunnen verwerken, moet het mogelijk zijn om de belasting te spreiden over verschillende toestellen. Op deze manier wordt het mogelijk om eenvoudig steeds groter wordende hoeveelheden nieuwsberichten te verwerken.

4.6 Schaalbaarheid

4.6.1

35

Batch processing met Mahout

Een traditionele techniek om eenvoudig berekeningen te spreiden over verschillende machines is batch processing. Men kan alle benodigde informatie zoals attributen van items en gebruikersprofielen naar een computercluster kopiëren om daar dan berekeningen uit te voeren. Eens de berekeningen klaar zijn worden de resultaten terug naar het eigenlijke systeem gekopieerd en kunnen ze gebruikt worden om te antwoorden op vragen van de gebruikers. Deze manier van werken wordt onder andere door Google News gebruikt [94]. Een veelgebruikte library om met behulp van batch processing aanbevelingen te genereren is Apache Mahout [13]. Mahout bevat alle functionaliteit om eenvoudig aanbevelingssystemen te maken die zonder problemen kunnen schalen. Mahout lijkt dus perfect te voldoen aan de eisen voor een realtime aanbevelingssysteem en in deze masterproef werd er dan ook vrij veel tijd besteed aan het bestuderen van en experimenteren met Mahout. Uiteindelijk werd Mahout niet gebruikt omwille van twee redenen: • Mahout bevat enkel collaborative filtering technieken. Om nieuws aan te bevelen zijn content based technieken interessanter. Het is wel mogelijk om bepaalde functionaliteit te hergebruiken om een content based algoritme te implementeren, maar de huidige oplossing met de zoekmachine is eenvoudiger, sneller, eleganter en bevat meer innovatieve aspecten. • Batch processing is een goede techniek voor aanbevelingssystemen die niet tijdskritisch zijn. In de context van deze masterproef waar de nadruk ligt op het realtime aspect, is er geen tijd om gegevens in en uit de cluster te kopiëren. Indien er van batch processing gebruik gemaakt zou worden, dan kan een artikel pas aanbevolen worden nadat de batch opdracht voltooid is. Dit is dus zeker geen realtime systeem.

4.6.2

Realtime processing met Storm

Er zijn verschillende systemen die grote hoeveelheden data moeten verwerken waarbij de verwerkingstijd van kritisch belang is. Een goed voorbeeld is een procescontrole systeem binnen een grote fabriek. Een interessante library die hierbij gebruikt kan worden is Storm [70]. Storm voorziet alle benodigde componenten om een systeem te maken dat in realtime grote stromen gegevens kan verwerken. Bij batch processing werden de berekeningen op discrete ogenblikken gedaan. Storm zorgt ervoor dat deze berekeningen continu kunnen worden gedaan zodat een

4.6 Schaalbaarheid

36

bericht direct kan verwerkt worden vanaf het beschikbaar wordt. Storm zorgt er ook voor dat alle componenten eenvoudig over verschillende systemen kunnen verspreid worden. Storm werd ontwikkeld door Twitter maar wordt ondertussen ook gebruikt door andere bedrijven die gigantische hoeveelheden gegevens in realtime moeten verwerken [70]. Storm is niet gericht op één toepassing maar is bruikbaar in vrijwel elk domein dat nood heeft aan gedistribueerde systemen die in realtime data moeten verwerken. Om Storm te kunnen gebruiken moet er een topologie (eng: topology) opgebouwd worden. Een topologie beschrijft hoe berichten in het systeem komen en wat er mee moet gebeuren. Een topologie bestaat uit verschillende componenten die elk één specifieke taak hebben. De kracht van Storm is dat het dan naar believen duplicaten kan maken van deze componenten, al dan niet verspreid over verschillende systemen om zo grote hoeveelheden data te kunnen verwerken.

Figuur 4.4: Een Storm topology [70] Een Storm-topologie kan het best gezien worden als een gerichte graaf zonder lussen of als een stroomnetwerk. Elke topologie heeft één of meerdere producenten die berichten in het systeem brengen. In Storm-terminologie zijn dit “Spouts”. Naast deze producenten zijn er nog andere knopen die elk één heel specifieke kleine taak uitvoeren. Deze knopen

4.6 Schaalbaarheid

37

worden “Bolts” genoemd. Om Storm te gebruiken moeten er klassen geschreven worden voor de verschillende types spouts en bolts die het systeem nodig heeft. Elke klasse moet voldoen aan een zekere interface voorgeschreven door Storm. Eens dit gebeurd is kan Storm naar believen bepaalde taken door één of meerdere componenten laten uitvoeren. Storm zorgt er ook voor dat de berekeningen verspreid worden over verschillende threads binnen één machine of over verschillende machines binnen een cluster. Een spout injecteert berichten in het systeem. In ons geval gaat dit over URL’s van RSS-feeds die gecontroleerd moeten worden. Deze berichten worden door Storm verdeeld over verschillende bolts, elk van het zelfde type, die binnen verschillende threads of zelfs op verschillende machines draaien. Deze bolts halen de RSS-feed op en gaan na of er nieuwe artikels zijn. Indien er nieuwe artikels zijn worden de URL’s van deze nieuwe artikels doorgegeven aan een volgende familie bolts. Deze halen de inhoud van het artikel op, verwijderen redundante informatie zoals reclame en geven de echte tekst van het artikel door aan de volgende stap. Deze volgende stap bestaat uit het analyseren van de tekst. Het resultaat van deze stap is een lijst met termen die dit artikel het best beschrijven. Eens alle informatie over het artikel gekend is, kan het artikel opgenomen worden in de index van de zoekmachine. Deze taak wordt gedaan door weer een andere bolt. Nadat de artikels opgenomen werden in de index, moet er statistische informatie bijgehouden worden over welke termen momenteel vaker voorkomen dan in het verleden. Deze taak wordt weer uitgevoerd door een andere verzameling bolts. Periodiek wordt deze statistische informatie opgeslagen in een databank zodat de rest van het systeem eenvoudig deze data kan gebruiken. Storm zorgt er dus voor dat het volledige systeem schaalbaar is. Operaties die relatief veel tijd vragen zoals het ophalen van een volledig artikel kunnen door verschillende threads gedaan worden. Als de hoeveelheid werk te groot wordt voor één machine, kan Storm ervoor zorgen dat de berekeningen op verschillende machines gebeuren. De pipeline-structuur van Storm zorgt er ook voor dat er eenvoudig uitbreidingen mogelijk zijn. Het volgende hoofdstuk bespreekt de extra functionaliteit die dankzij Storm relatief eenvoudig te implementeren is.

4.7 Detectie belangrijke gebeurtenissen

38

Nog een voordeel van Storm is dat er standaard een webinterface ter beschikking wordt gesteld die toelaat om de belasting van de cluster te controleren. Via deze interface kan de applicatie ook gestopt en herstart worden.

Figuur 4.5: De Storm gebruikersinterface

4.6.3

Lucene

Een mogelijke bottleneck in het systeem is de zoekmachine. Alle andere componenten kunnen zonder problemen op verschillende toestellen draaien zonder weet te hebben van hoeveel kopieën van een zelfde component er zijn. De zoekmachine is anders, elke component moet toegang hebben tot dezelfde index om steeds de meest recente berichten te kunnen aanbevelen. Gelukkig bestaan er verschillende technieken om een Lucene index over verschillende computers te spreiden. De meest gebruikte oplossing is Katta [69]. Katta kan een Lucene-index over een praktisch onbeperkt aantal machines verdelen zodat de index volkomen schaalbaar is.

4.7

Detectie belangrijke gebeurtenissen

In hoofdstuk 2 werd beschreven dat gebruikers korte en lange termijn interesses hebben. Dit maakt het aanbevelen van nieuws zo moeilijk. Na een gebeurtenis met een grote impact zoals de bomaanslag in Boston willen de gebruikers hiervan direct op de hoogte gebracht

4.7 Detectie belangrijke gebeurtenissen

39

worden, ook al zou uit hun profiel blijken dat ze in het verleden absoluut niet geïnteresseerd waren in artikels over bomaanslagen. Omdat het aanbevelen gesimuleerd wordt door het uitvoeren van een zoekopdracht naar bepaalde termen, komt het aanbevelen van deze trending topics neer op het zoeken naar trending termen. We moeten dus in staat zijn om op elk willekeurig ogenblik een lijst te produceren met termen die op dat moment veel vaker voorkomen dan men zou verwachten op basis van het verleden. Dankzij het gebruik van Lucene binnen een Storm-topologie wordt dit vrij eenvoudig. Eens het artikel geïndexeerd is kan Lucene alle informatie geven die nodig is om de belangrijkste kernwoorden uit een artikel te bepalen. Deze informatie wordt doorgegeven aan een bepaalde bolt die statistieken bijhoudt. Dit is een eenvoudige teller die aangeeft hoeveel keer deze term in een artikel voorkwam in het laatste tijdslot. Dit tijdslot is niet discreet maar werd geïmplementeerd met een sliding window mechanisme om continu in realtime te kunnen inspelen op gebeurtenissen. Lucene zorgt ervoor dat de kernwoorden die worden opgenomen in de statistieken, goede kernwoorden zijn die het artikel beschrijven. Storm zorgt ervoor dat de statistieken in realtime aangepast en beschikbaar worden.

UITBREIDINGEN

40

Hoofdstuk 5 Uitbreidingen In hoofdstuk 3 werd de algemene architectuur van het systeem besproken. In hoofdstuk 4 werd uit de doeken gedaan hoe het systeem praktisch geïmplementeerd werd. Dit hoofdstuk bespreekt enkele uitbreidingen die het systeem krachtiger maken. Al deze uitbreidingen zijn vrij eenvoudig te implementeren dankzij de modulaire structuur van de Storm-topologie.

5.1

Google trends

Het is geen geheim dat Google over gigantisch veel informatie beschikt. Door de zoekopdrachten die mensen uitvoeren te analyseren, kan men ontdekken in welke onderwerpen er momenteel een grote interesse is. Deze kennis wordt reeds gebruikt om epidemies te voorspellen [72], [73], [74] en om voorspellingen te doen over welke producten veel gekocht zullen worden [75]. We kunnen deze informatie ook handig gebruiken om nieuwstrends te ontdekken. Google publiceert elk uur een korte lijst met de zoekopdrachten die op dat moment trending zijn [82]. Dit zijn zoekopdrachten die momenteel veel vaker voorkomen dan in het verleden. Periodiek haal een speciale spout (zie hoofdstuk 4) deze lijst binnen. Deze termen volgen dan de zelfde weg in de topologie als de termen die uit de artikels gehaald worden. Er is verder geen onderscheid tussen beide soorten termen, ze worden allemaal opgenomen in de lijst met statistieken zoals beschreven in het vorige hoofdstuk. Op basis van deze statistieken berekent het systeem dan een eigen lijst met trending termen, die gebruikt worden om aanbevelingen te doen. Aan de hand van deze trending termen kan het systeem extra artikels aanbevelen, zelfs al voldoen ze niet echt aan het gebruikersprofiel.

5.2 Twitter

41

Figuur 5.1: Google hourly trends [82]

5.2

Twitter

In hoofdstuk 2 werd een overzicht gegeven van vergelijkbare systemen en publicaties binnen het domein van nieuwsaanbeveling. Een populaire techniek was het gebruiken van Twitter. Met Twitter kan men eenvoudig toegang krijgen tot de gedachten van miljoenen mensen [46]. Onderzoek heeft dan ook uitgewezen dat de berichten op Twitter heel goed weergeven waar er momenteel een grote interesse in is [49],[50],[51]. Op deze manier kan men dus voorspellen over welke gebeurtenissen er veel artikels gelezen zullen worden. Net zoals de vorige, zorgt deze uitbreiding er voor dat het systeem verrassende, actuele aanbevelingen kan doen waar veel mensen in geïnteresseerd zijn, zelfs al zou dat niet uit hun profiel blijken. Dit was één van de eisen voor een aanbevelingssysteem voor nieuws. Onderzoek heeft aangetoond dat tot wel 85% van de berichten op Twitter over nieuws gaan [58]. Het lijkt dus een zeer goed idee om deze informatie te gebruiken om de aanbevelingen te verbeteren. De eerste techniek waarmee geëxperimenteerd werd, was het verwerken van een steekproef van willekeurige tweets. Twitter biedt een API aan waarmee men eenvoudig een klein deel van de nieuwe tweets kan opvangen. De keuze van tweets is compleet willekeurig. Het idee was dat, aangezien toch een groot deel van de Tweets over nieuws gaan, de andere

5.2 Twitter

42

tweets te verwaarlozen zijn. De resultaten die bekomen werden kwamen echter totaal niet overeen met deze hypothese. Slechts een heel klein deel ging echt over nieuws. De andere tweets gingen over de meest uiteenlopende onderwerpen zoals getoond in tabel 5.1. Deze conclusie komt dus absoluut niet overeen met de resultaten uit de reeds vermelde paper. Deze paper werd in 2010 geschreven, dus het zou kunnen dat het typische gebruik van Twitter ondertussen veranderd is. Er zou echter meer onderzoek nodig zijn op een grotere dataset om deze hypothese te bevestigen. Dit valt buiten het doel van deze thesis.

Insert belated Shinedown lyric here. roboTechnician then neither will i... No matter how comfy it is... RT Fact: Psychology says, the person who tries to keep everyone happy often ... RT @CuteLoveMsgs: Life is so much better when you laugh and not worry. MissBooTayy triple meat triple cheese bacon and jalapenos. #hungercured This isnt funny im ballknge Will I ever forget my potato? RT RealTonyRocha: #humanrights Bulgaria Summarily Expells Asylum Seekers ... Hey Marpione_96 it would be awesome if you can gain more fo.llo.wers ... Tabel 5.1: Een steekproef van het verkeer op Twitter De Twitter-API laat echter ook toe om een filtering door te voeren zodat enkel tweets van bepaalde personen of organisaties doorgegeven worden. Dit is een betere benadering. Er werd een speciale spout (zie hoofdstuk 4) gemaakt die deze nieuwe tweets ophaalt en verwerkt. Er werd een lijst opgesteld van enkele nieuwsagentschappen en kranten die ook actief zijn op Twitter. Deze lijst werd dan ook aangevuld met enkele politici, bloggers en opiniemakers. De tweets die door deze personen verstuurd worden gaan vaak wel over nieuws, vaak nog voordat een gebeurtenis algemeen bekend wordt. Als bijkomend voordeel zijn deze tweets normaal gezien grammaticaal in orde en kunnen we dus eenvoudiger kernwoorden ontdekken. De tweets die verzonden worden door nieuwsagentschappen bevatten de titels van nieuwe artikels. Deze hadden we al ontdekt door de RSS-feed op te halen. Het lijkt dus dat deze tweets weinig toegevoegde waarde hebben. Dit is echter niet het geval: telkens een artikel geretweet wordt, wordt het ook ontvangen door het systeem. Het systeem kan dus

5.3 Collaborative filtering

43

meten hoe populair een artikel is aan de hand van het aantal retweets. Bij het ontvangen van twee artikels via RSS kunnen we geen conclusies trekken in verband met de relatieve belangrijkheid. Door het aantal retweets te vergelijken kunnen we dit wel. We filteren dus wel op basis van de oorspronkelijke afzender van de tweet, maar de echt nuttige informatie is het aantal keer dat deze tweet door andere gebruikers opnieuw verzonden werd. Eens een tweet ontvangen wordt, wordt de tekst verwerkt volgens dezelfde stappen waarmee de inhoud van een artikel verwerkt wordt (zie hoofdstuk 4). De tweet wordt dus opgesplitst in tokens die dan dezelfde weg volgen als de kernwoorden uit de artikels of de populaire zoekopdrachten bij Google. Dit alles was relatief eenvoudig te implementeren dankzij de modulaire structuur van de Storm-topologie. Deze werkwijze gebruikt een lijst van Twittergebruikers die dezelfde is voor elke gebruiker van het systeem. Een andere uitbreiding zou zijn om de gebruiker toe te laten om zelf zo een lijst op te stellen. De gebruiker kan dan zelf kiezen welke Twittergebruikers hij volgt en kan zo dus meer controle uitoefenen op de artikels die hem aanbevolen worden. Deze techniek kan ook teruggevonden worden in de literatuur (o.a. [83]). Deze verfijning werd echter niet meer geïmplementeerd.

5.3

Collaborative filtering

In hoofdstuk 2 werden content based en collaborative filtering technieken vergeleken. We kwamen tot de conclusie dat collaborative filtering niet geschikt was om in realtime aanbevelingen van vluchtige inhoud te doen. Het cold start probleem zorgt ervoor dat het artikel al verouderd is vooraleer we het kunnen aanbevelen. Collaborative filtering is echter wel een heel krachtige en interessante methode omdat ze kan zorgen voor verrassende aanbevelingen. Het zou dus een grote verbetering kunnen zijn mochten we er in slagen om toch op één of andere manier collaborative filtering technieken te gebruiken. Om dit te kunnen doen moeten we afstappen van de klassieke manier om naar collaborative filtering te kijken. Traditioneel wordt zo een algoritme gebruikt om items aan te bevelen. Hiervoor worden dan de meningen van gebruikers vergeleken om zo gelijkaardige gebruikers te ontdekken. Men gaat ervan uit dat gebruikers die in het verleden een zelfde

5.3 Collaborative filtering

44

gedrag vertoonden, dit ook in de toekomst zullen doen. Het vergelijken van gebruikers gebeurt aan de hand van een gebruikersprofiel. Traditioneel bestaat dit gebruikersprofiel uit item-score-paren. Gebruikers met gelijkaardige scores voor dezelfde items worden dan als gelijkaardig gezien. In een content based systeem bestaat dit profiel uit attributen van items waar de gebruiker reeds interesse in getoond heeft. Ook in een content based systeem kunnen we dus zonder problemen gebruikersprofielen vergelijken om zo gelijkaardige gebruikers te ontdekken. Stel dat we nu geen items gaan aanbevelen maar onderdelen van content based profielen. We vergelijken elke gebruiker met elke andere gebruiker en berekenen de gelijkenissen op basis van hun profielen. Vinden we gelijkaardige profielen dan kunnen we deze profielen uitbreiden met attributen uit de andere profielen. Op deze manier kan het content based systeem exact hetzelfde blijven maar bouwen we toch een soort van collaborative filtering techniek in. Deze techniek is nog beter dan ze op het eerste zicht lijkt. We blijven de voordelen van een content based algoritme behouden: we kunnen nog steeds in realtime aanbevelingen doen. Hier bovenop krijgen we het voordeel van collaborative filtering namelijk de verrassende aanbevelingen. Om de gelijkenissen tussen profielen te berekenen moeten we in principe elke gebruiker met elke andere gebruiker vergelijken. Dit is een zware operatie maar dit is veel minder erg dan het lijkt. Het vergelijken is niet tijdskritisch, we kunnen gerust de gebruikersprofielen kopiëren naar een afzonderlijke machine en daar de berekeningen doen. Hiervoor kunnen batch processing technieken zoals Apache Mahout handig gebruikt worden. Eens de berekeningen klaar zijn, kunnen we de profielen samenvoegen. Deze strategie werd geïmplementeerd in een afzonderlijk project. De bedoeling is om dit programma periodiek (bv: via een cron job) te laten draaien. De gebruikersprofielen worden vanuit de databank gekopieerd en er wordt een collaborative filtering algoritme op los gelaten. Eens de collaborative filtering klaar is worden de profielen in de databank aangepast. Terwijl de collaborative filtering de berekeningen aan het doen is kan de rest van het systeem in realtime aanbevelingen blijven genereren. Als de collaborative filtering klaar is wordt het profiel aangepast en kunnen er extra verrassende aanbevelingen gedaan worden.

5.4 Ondersteuning van meerdere talen

45

Figuur 5.2: Uitbreiden van de gebruikersprofielen m.b.v. collaborative filtering Dankzij het gebruik van Apache Mahout [13] is ook deze component volledig schaalbaar. In tegenstelling tot de rest van het systeem steunt de collaborative filtering component niet op een realtime systeem zoals Storm om de grote hoeveelheden data te kunnen verwerken maar op een batch processing systeem. Dit brengt het realtime gedrag van het volledige systeem echter niet in gevaar, er kunnen nog steeds in realtime aanbevelingen gegenereerd worden. Het ophalen van alle profielen uit de databank, het berekenen van de gelijkenissen tussen de profielen, het uitvoeren van de collaborative filtering en het opslaan van de aanpassingen in de databank duurt enkele minuten voor 340 gebruikers met in totaal 175000 termen in de profielen.

5.4

Ondersteuning van meerdere talen

Het volledige systeem werd vanaf het begin opgebouwd om Engelstalige artikels aan te bevelen. Het is echter geen probleem om artikels in een andere taal aan te bevelen. Er is slechts één component die taalafhankelijk is, de component die verantwoordelijk is voor het opsplitsen van de tekst in tokens. Voor elke taal die ondersteund moet worden, moet er dus zo een component gemaakt worden. Als demonstratie werd zo een component geïmplementeerd voor het Nederlands. Deze houdt rekening met Nederlandstalige stopwoorden en met eigenaardigheden specifiek voor

5.4 Ondersteuning van meerdere talen

46

het Nederlands. Ook de component die tweets ophaalt kan eenvoudig geconfigureerd worden om enkel Nederlandstalige berichten te gebruiken. De Google trends daarentegen zijn enkel beschikbaar in het Engels. Testen hebben uitgewezen dat dit echter geen groot probleem is: de meeste zoekopdrachten (Google trends) bevatten toch persoonsnamen en deze zijn meestal hetzelfde in het Nederlands als in het Engels.

TESTEN EN BENCHMARKS

47

Hoofdstuk 6 Testen en benchmarks In dit hoofdstuk wordt er verduidelijkt op welke manier het systeem getest werd. De nadruk ligt hier op het testen van de accuraatheid en van de performantie van het volledige systeem, niet op het testen van afzonderlijke codefragmenten, daarvoor werden er unit testen geschreven met behulp van JUnit [96].

6.1

Geautomatiseerd testen

De beste manier van testen is het testen door echte gebruikers. Tijdens de ontwikkeling is dit moeilijk. Er moet dus gezocht worden naar meer geautomatiseerde testen. Op deze manier kan een kleine aanpassing doorgevoerd worden waarna een volledige test herhaald wordt om na te gaan of de aanpassing voor betere resultaten zorgt. Deze testen moeten op de een of andere manier de performantie en de accuraatheid van het systeem bepalen. Om dit te doen werd een systeem geïmplementeerd dat gebruikers kan simuleren. Een gebruiker wordt gesimuleerd door een object. Deze “gebruikers” worden geïnitialiseerd met een lijst van “interesses”, dit is een eenvoudige lijst met woorden. Periodiek vraagt de gebruiker nieuwe aanbevelingen op. Deze artikels worden overlopen en indien de titel van een artikel een woord bevat dat ook in de lijst met interesses staat, wordt het artikel geconsumeerd. Er worden een honderdtal nepgebruikers aangemaakt die allemaal op deze manier artikels opvragen en consumeren. Elke nepgebruiker houdt dan statistieken bij over hoeveel artikels van de aanbevelingen voldoen aan zijn profiel en over de tijd die het systeem nodig had om de aanbevelingen te berekenen. Deze manier van testen is natuurlijk niet ideaal, de interesses van een echte gebruiker

6.1 Geautomatiseerd testen

48

zijn complexer dan deze eenvoudige techniek. Toch blijken deze testen handig te zijn om puur het aanbevelen te testen. Voor het testen van de performantie is deze methodologie ideaal, men kan verschillende nepgebruikers tegelijkertijd laten werken om na te gaan hoe het systeem kan omgaan met een groot aantal gebruikers.

6.1.1

Resultaten

De hierboven beschreven testen werden gedurende tien dagen uitgevoerd. Er werden 100 nepgebruikers aangemaakt, elk met een verschillend profiel. Zij vroegen steeds nieuwe aanbevelingen op en consumeerden de voor hun relevante artikels. Figuur 6.1 toont de resultaten van deze test. De weergegeven waardes zijn het gemiddelde voor 100 gebruikers. De blauwe lijn geeft het totaal aantal aanbevelingen weer, de oranje lijn geeft aan hoeveel aanbevelingen er strikt genomen relevant zijn. Op het eerste zicht lijken deze resultaten niet spectaculair, slechts 10 tot 20 procent van de teruggegeven artikels zou relevant zijn. Dit is echter een verkeerde conclusie omwille van drie redenen: • Het aanbevelingssysteem beveelt artikels aan op basis van de titel, de beschrijving en de volledige inhoud. Het testsysteem kijkt enkel naar de titel om te beslissen of een artikel relevant is of niet. Er zijn dan ook veel relevante artikels die ten onrechte als niet relevant gezien worden door het testsysteem. • De nepgebruikers worden geconfigureerd met een klein aantal termen als intern profiel, enkel als één van deze termen letterlijk voorkomt in de titel van een artikel wordt het artikel als relevant gezien. • Het aanbevelingssysteem beveelt niet enkel artikels aan op basis van een persoonlijk profiel maar ook op basis van trending topics. De helft van de aanbevelingen zijn persoonlijke aanbevelingen, de andere helft zijn aanbevelingen op basis van trending topics. Voor een menselijke gebruiker zijn beide soorten aanbevelingen nuttig, het testprogramma zal enkel “relevante” artikels vinden bij de persoonlijke aanbevelingen. Het is dus duidelijk dat het testsysteem heel wat te wensen overlaat. Het was echter ook niet de bedoeling om een complex testsysteem te implementeren. Zelfs met deze beperkingen heeft het testsysteem heel wat nut, het is immers eenvoudig om een volledige reeks testen te herhalen na een aanpassing om na te gaan wat de gevolgen van de aanpassing zijn.

6.1 Geautomatiseerd testen

49

Figuur 6.1: Evolutie relevante aanbevelingen Het is belangrijk om op te merken dat er enkel artikels van de laatste twee dagen werden aanbevolen. De test duurde tien dagen, de artikels die op het einde werden aanbevolen zijn dus niet meer dezelfde als deze in het begin. Een interessantere grafiek is figuur 6.2. Deze toont een detailopname van de eerste 12 uur. Op deze figuur is duidelijk het leerproces te zien.

6.2 Gebruikerstesten

50

Figuur 6.2: Evolutie relevante aanbevelingen - detailopname Deze testen tonen duidelijk aan dat het systeem er in slaagt om een correct profiel van de gebruiker op te bouwen. Deze geautomatiseerde testen zijn ook handig om na te gaan wat de performantie is van het systeem. Gemiddeld heeft het systeem 800 ms nodig om 250 aanbevelingen te genereren voor één specifieke gebruiker. Deze tijd bestaat uit het ophalen van het gebruikersprofiel en de trending termen uit de databank, het opbouwen en uitvoeren van een zoekquery en het clusteren van de artikels. Dit is dus snel genoeg om een goede gebruikerservaring te verzekeren.

6.2

Gebruikerstesten

De geautomatiseerde testen uit de vorige paragraaf waren een handige hulp tijdens de ontwikkeling. Ze tonen ook heel duidelijk aan dat het systeem er in slaagt om gepersonaliseerde aanbevelingen te doen. Een echte gebruiker is echter heel wat complexer dan het eenvoudige testprogramma. De automatische testen zijn dus geen alternatief voor een echte gebruikerstest.

6.2 Gebruikerstesten

51

Het systeem werd getest door studenten van de opleiding Journalistiek aan de Artevelde Hogeschool in Gent [95]. De tests werden gedurende twee weken uitgevoerd. Het systeem dat getest werd was het basissysteem, zonder de uitbreidingen die in het vorige hoofdstuk vermeld werden.

6.2.1

Resultaten

Een aanbevelingssysteem is een lerend systeem. Bij een nieuwe gebruiker worden er eerst algemene artikels aanbevolen op basis van de trending topics. Eens de gebruiker enkele artikels gelezen heeft, zal het systeem een profiel kunnen opbouwen en zullen er persoonlijke aanbevelingen kunnen gedaan worden. Indien het systeem er in slaagt om een correct profiel van de gebruiker op te bouwen zou men dus verwachten dat de gebruiker vooral nog op artikels klikt die deel uit maken van de persoonlijke aanbevelingen. De gebruiker zal ook artikels lezen die aanbevolen werden op basis van de trending topics maar dit zullen er waarschijnlijk minder zijn. Het doel van de gebruikerstest was om deze hypothese te bevestigen. Er werd een eenvoudig programma geschreven dat in staat is om een logbestand te parsen en om te zetten naar een grafische voorstelling zoals in figuur 6.3a . Voor elke gebruiker bevat deze figuur een kolom, elk vakje binnen een kolom komt overeen met een artikel dat de gebruiker bekeken heeft. Dit vakje wordt rood ingekleurd als het artikel aanbevolen werd omdat het over een trending topic gaat. Een blauw vakje komt overeen met een persoonlijke aanbeveling. Deze figuur toont de activiteit van zowel de menselijke testgebruikers als van de geautomatiseerde testen. Figuur 6.3b geeft dit gedetailleerd weer voor een typische (menselijke) testgebruiker. Deze figuur bevestigt duidelijk de hypothese. Het systeem is dus ook in staat om voor een echte gebruiker een goed profiel op te bouwen.

6.3 Grootte van de Lucene-index

52

(a) Alle gebruikers (b) Detail voor één gebruiker

Figuur 6.3: Grafische voorstelling logbestand Aangezien er toch vooral artikels bekeken worden die aanbevolen werden op basis van het persoonlijk profiel zou men kunnen overwegen om meer van deze persoonlijke aanbevelingen te genereren en minder algemene aanbevelingen. Uit navraag bij de gebruikers bleek echter dat dit geen goed idee zou zijn. De meeste gebruikers lezen de titels van deze algemene artikels en weten daarmee genoeg om up-to-date te zijn, zonder de volledige inhoud te moeten lezen. Artikels die op basis van de persoonlijke interesses aanbevolen werden, worden meestal wel volledig gelezen. In hoofdstuk twee werd er al aangehaald dat gebruikers interesses hebben op korte en op lange termijn. Uit deze gebruikerstest blijkt nu dat mensen deze twee soorten artikels op een andere manier behandelen.

6.3

Grootte van de Lucene-index

Volgende grafiek toont aan hoe de grootte van de Lucene-index op schijf evolueert met het aantal artikels.

6.3 Grootte van de Lucene-index

53

Figuur 6.4: Grootte lucene index als functie van het aantal artikels Het is mogelijk om artikels uit de index te verwijderen. Het lijkt dus een goed idee om periodiek oude artikels te verwijderen om zo de grootte van de index te beperken. Dit is echter niet ideaal. Een Lucene-index is een sterk geoptimaliseerde structuur. Na het verwijderen moet de index opnieuw geoptimaliseerd worden om de verwijdering echt door te voeren. Deze optimalisatie is een heel dure operatie. Het verwijderen van oude artikels heeft ook een belangrijk neveneffect. Om kernwoorden uit artikels te halen wordt er sterk gesteund op TFIDF zoals beschreven in hoofdstuk 4. TFIDF houdt rekening met het aantal artikels waarin een term voorkomt. Hoe meer artikels er zijn die deze term bevatten, hoe minder belangrijk de term wordt gezien. Als men enkel recente artikels in de index houdt zullen bepaalde termen in een relatief veel groter aantal artikels voorkomen, deze termen worden dan ten onrechte als minder belangrijk gezien. Door het verwijderen van oude artikels gaat dus vrij veel informatie verloren.

BESLUIT

54

Hoofdstuk 7 Besluit 7.1

Algemeen

Hoofdstuk 1 begon met de algemene probleemstelling en het doel van deze masterproef. Het belangrijkste doel was om artikels te kunnen aanbevelen van zodra ze beschikbaar werden. Aangezien de hoeveelheid artikels enkel maar stijgt moest de oplossing volledig schaalbaar zijn. Hoofdstuk 2 bevatte de resultaten van de literatuurstudie. Eerst werd er gekeken naar algemene aanbevelingssystemen en daarna naar aanbevelingssystemen voor nieuws. Ook de verschillen tussen beiden en de moeilijkheden bij het aanbevelen van nieuws werden hier behandeld. In hoofdstuk 3 werd de architectuur geschetst van het systeem. Het belangrijkste resultaat van dit hoofdstuk was dat er een zoekmachine gebruikt werd om de aanbevelingen te genereren. Dankzij het expliciete gebruik van deze zoekmachine is het systeem in staat om in realtime de aanbevelingen te doen. Hoofdstuk 4 ging in op de echte implementatie. Een belangrijke keuze was het gebruiken van Storm. Dankzij Storm is het systeem volledig schaalbaar. Storm zorgt ook voor een uitbreidbaar systeem. Deze uitbreidingen werden in hoofdstuk 6 besproken. De uitbreidingen hadden vooral als doel om extra verrassende aanbevelingen te genereren. Er werd onder andere gebruik gemaakt van trending zoekopdrachten van Google en van retweets van nieuwsberichten op Twitter. Ook werd er een collaborative filtering systeem geïmplementeerd dat nog extra verrassende aanbevelingen kan teruggeven.

7.2 Vernieuwende aspecten

55

Het systeem werd grondig getest. In hoofdstuk 5 werden de verschillende testen en testresultaten besproken.

7.2

Vernieuwende aspecten

Er werd al veel onderzoek gedaan naar aanbevelingssystemen voor nieuws. In hoofdstuk 2 werden de belangrijkste publicaties binnen dit domein opgesomd. Het systeem dat in deze thesis besproken werd verschilt echter op een aantal vlakken fundamenteel van deze systemen. Gebruikmaken van een zoekmachine. Een content based aanbevelingssysteem heeft veel gemeenschappelijk met een zoekmachine. In verschillende projecten worden er dan ook delen van een bestaande zoekmachine gebruikt binnen een content based aanbevelingssysteem. Aangezien Lucene zowat de gouden standaard is op het vlak van opensource zoekmachines komt dit vaak neer op het gebruiken van de Lucene indexstructuur. Deze thesis gaat echter nog een stap verder en vertaalt het aanbevelen expliciet naar het uitvoeren van een zoekopdracht. Schaalbaarheid. Systemen zoals Google News zijn in staat om grote hoeveelheden gebruikers zonder problemen te bedienen. De systemen die beschreven worden in verschillende papers slagen hier echter niet altijd in. Het systeem uit deze masterproef is heel eenvoudig schaalbaar dankzij het gebruik van Storm. Een zoektocht op het Internet levert niet direct een ander aanbevelingssysteem op dat ook gebruik maakt van Storm. Het systeem dat hier beschreven wordt is dus het eerste of toch zeker één van de eerste aanbevelingssystemen dat steunt op Storm. Clustering. Elk aanbevelingssysteem voor nieuws moet op de één of andere manier een clustering doorvoeren. De clustering op zich is dus niets nieuws. Wat wel uniek is in het systeem dat in deze thesis besproken werd, is het moment waarop deze clustering gebeurt. De clustering wordt pas helemaal op het einde gedaan, vlak voor de resultaten getoond worden aan de gebruiker. Zoals besproken in hoofdstuk 3 heeft dit verschillende voordelen. Het belangrijkste voordeel is dat de clustering per gebruiker wordt uitgevoerd en dat er dus mogelijkheden zijn om per gebruiker een verschillend niveau van details te tonen. Deze strategie van gepersonaliseerde clustering werd niet teruggevonden in een ander aanbevelingssysteem. Door de clustering pas uit te voeren vlak voor de resultaten aan

7.2 Vernieuwende aspecten

56

de gebruiken getoond worden is er geen wachttijd nodig vooraleer een artikel opgenomen kan worden in de resultaten. De beslissing om de clustering helemaal op het einde te doen was dan ook één van de cruciale stappen om een echt realtime aanbevelingssysteem te verkrijgen. Onafhankelijk van specifieke nieuwsbronnen. De meeste systemen die in de literatuur beschreven worden zijn specifiek ontworpen voor een specifieke verzameling van nieuwsbronnen. Het systeem uit deze thesis kan artikels binnenhalen van elke mogelijke RSS-feed. Er zijn verder geen speciale eisen voor deze bronnen. Er kunnen zonder problemen extra nieuwsbronnen toegevoegd worden aan het systeem terwijl het systeem draait. De artikels van deze bronnen worden dan onmiddellijk beschikbaar gemaakt. Twitter. In hoofdstuk 2 werden er verschillende nieuwsaanbevelingssystemen beschreven die er in slagen om actuele berichten aan te bevelen door gebruik te maken van Twitter. Ook het systeem uit deze thesis gebruikt Twitter, maar op een iets andere manier. De traditionele manier is om een steekproef te nemen van alle berichten op Twitter en om na te gaan over welke onderwerpen er veel berichten zijn. Binnen dit systeem wordt dit niet gedaan maar er wordt gekeken naar berichten die afkomstig zijn van dezelfde organisaties die de artikels publiceren die worden aanbevolen. Het doel is om aan de hand van het aantal retweets een schatting te kunnen maken van hoe belangrijk dit artikel is. Google trends. Deze uitbreiding diende vooral om aan te tonen dat de Storm structuur heel modulair is. Geen enkel ander aanbevelingssysteem voor nieuws gebruikt deze informatie terwijl het wel heel handige informatie is omdat ze bekomen werd door het analyseren van het zoekgedrag van miljoenen mensen. Inbouwen van collaborative filtering. Er bestaan al veel hybride systemen die een collaborative filtering techniek inbouwen in een content based systeem. De strategie die in deze thesis beschreven werd verschilt echter fundamenteel van de bestaande technieken. Hier dient de collaborative filtering om het profiel van de gebruiker te verbeteren. Dit profiel wordt dan gebruikt in een content based systeem. Het is belangrijk om op te merken dat ook deze uitbreiding volledig schaalbaar is.

7.3 Mogelijke verdere uitbreidingen

7.3

57

Mogelijke verdere uitbreidingen

Een interessante verdere uitbreiding zou zijn om de gebruiker zelf toe te laten om een aantal RSS-feeds in te geven die hij wil volgen. In het systeem zoals het hier beschreven werd, is er één verzameling RSS-feeds waaruit er aanbevelingen worden gegenereerd voor alle gebruikers. Analoog zou het ook mogelijk zijn om per gebruiker de personen die gevolgd worden op Twitter te configureren. Een andere uitbreiding zou zijn om rekening te houden met de omgeving of de context van de gebruiker. Misschien wil de gebruiker andere nieuwsberichten lezen bij het ontbijt, op de trein of op het werk. Deze uitbreiding is relatief eenvoudig te implementeren omdat er expliciet een zoekmachine gebruikt wordt. In het systeem zoals het hier beschreven werd krijgt de gebruiker in het begin enkel algemene aanbevelingen. Eens hij verschillende artikels bekeken heeft, beschikt het systeem over een profiel en kunnen er persoonlijke aanbevelingen gedaan worden. Een mogelijke uitbreiding zou zijn om de gebruiker toe te laten om zelf zo een profiel in te geven of aan te passen. Een andere mogelijkheid zou zijn om toegang te vragen tot het facebook-profiel van de gebruiker om dan zo te achterhalen wat zijn interesses zijn. Aanbevelingssystemen worden steeds slimmer, vaak kunnen gebruikers niet helemaal meer achterhalen waarom een bepaald item aanbevolen wordt. Er wordt dan ook veel onderzoek gedaan naar transparante aanbevelingssystemen die aangeven waarom ze denken dat een bepaald item interessant is voor een zekere gebruiker [97], [98], [100]. Binnen deze thesis werd er een klein experiment uitgevoerd met heel beperkte verklaringen. Bij elk artikel werd er vermeld of het artikel aanbevolen werd op basis van het gebruikersprofiel of omdat het artikel over een gebeurtenis gaat waar er momenteel veel interesse in is. De gebruikers gaven echter aan dat deze informatie niet echt nuttig was. Een betere benadering zou zijn om aan elk artikel enkele tags te hechten zoals beschreven wordt in [99]. De gebruiker zou dan verder kunnen doorklikken naar artikels over verwante onderwerpen door op de tags te klikken. Binnen deze masterproef lag de nadruk op het genereren van de aanbevelingen. De gebruikersinterface werd daarom vrij sober gehouden. Een mogelijke uitbreiding zou dan ook zijn om deze front-end te verbeteren. Een uitgebreid onderzoek over gebruikersinterfaces voor een nieuwsaanbevelingssysteem kan teruggevonden worden in [80].

BIBLIOGRAFIE

58

Bibliografie [1] The new york times. http://www.nytimes.com/. [2] The huffington post. http://www.huffingtonpost.com/. [3] Who’s winning at volume in publishing. http://digiday.com/publishers/ whos-winning-at-volume-in-publishing/. [4] Huffington post passes nyt in web visitors. http://www.poynter.org/latest-news/ mediawire/135401/huffington-post-tops-nyt-in-web-traffic-in-may/. [5] Amid criticism, support for media’s ’watchdog’ role stands out overview. http://www.people-press.org/2013/08/08/ amid-criticism-support-for-medias-watchdog-role-stands-out/. [6] Section 3: News attitudes and habits. http://www.people-press.org/2012/09/ 27/section-3-news-attitudes-and-habits-2/. [7] Francesco Ricci, Lior Rokach, and Bracha Shapira. Introduction to recommender systems handbook. Springer, 2011. [8] Efficiënter en duurzamer: Colruyt informeert klanten op maat. http: //www.colruyt.be/colruyt/static/1024/persberichten/pers_26_01_10_ n.htm?KeepThis=true&TB_iframe=true&height=475&width=555. [9] Greg Linden, Brent Smith, and Jeremy York. Amazon. com recommendations: Itemto-item collaborative filtering. Internet Computing, IEEE, 7(1):76–80, 2003. [10] Xiaoyuan Su and Taghi M Khoshgoftaar. A survey of collaborative filtering techniques. Advances in artificial intelligence, 2009:4, 2009. [11] Peng Han, Bo Xie, Fan Yang, and Ruimin Shen. A scalable p2p recommender system based on distributed collaborative filtering. Expert systems with applications, 27(2):203–210, 2004.

BIBLIOGRAFIE [12] Distributed recommender system. distrecommender/index.html.

59 http://www.select.cs.cmu.edu/projects/

[13] Apache mahout. http://mahout.apache.org/users/recommender/ recommender-documentation.html. [14] cold start. http://en.wikipedia.org/wiki/Cold_start. [15] Netflix. http://www.netflix.com/global. [16] Netflix price. http://www.netflixprize.com/. [17] Why netflix never implemented the algorithm that won the netflix 1 million challenge. http://www.techdirt. com/blog/innovation/articles/20120409/03412518422/ why-netflix-never-implemented-algorithm-that-won-netflix-1-million-challenge. shtml. [18] Gediminas Adomavicius and Alexander Tuzhilin. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions. Knowledge and Data Engineering, IEEE Transactions on, 17(6):734–749, 2005. [19] Marko Balabanović and Yoav Shoham. Fab: content-based, collaborative recommendation. Communications of the ACM, 40(3):66–72, 1997. [20] Mark Claypool, Anuja Gokhale, Tim Miranda, Pavel Murnikov, Dmitry Netes, and Matthew Sartin. Combining content-based and collaborative filters in an online newspaper. In Proceedings of ACM SIGIR workshop on recommender systems, volume 60. Citeseer, 1999. [21] ratings future. http://thedigitalanalyst.com/2012/12/13/ the-future-of-online-ratings-and-reviews/. [22] Alan Said, Alejandro Bellogín, Jimmy Lin, and Arjen de Vries. Do recommendations matter?: news recommendation in real life. In Proceedings of the companion publication of the 17th ACM conference on Computer supported cooperative work & social computing, pages 237–240. ACM, 2014. [23] Mozhgan Tavakolifard Jon Atle Gulla Kevin C. Almeroth Jon Espen Ingvaldsen Gaute NygreenErik Berg. Tailored news in the palm of your hand: A multiperspective transparent approach to news recommendation.

BIBLIOGRAFIE

60

[24] Rss. http://en.wikipedia.org/wiki/RSS. [25] Apache lucene. http://lucene.apache.org/core/. [26] Apache solr. https://lucene.apache.org/solr/. [27] elasticsearch. http://www.elasticsearch.org/. [28] M McCandless, E Hatcher, and O Gospodnetic. Lucene in action. 2010. [29] Java. http://www.java.com/. [30] Douglas W. OardJinmook Kim. Implicit feedback for recommender systems. [31] Xavier AmatriainJosep M. PujolNuria Oliver. I like it... i like it not: Evaluating user ratings noise in recommender systems. [32] Yajie HuMitsunori Ogihara. Nextone player: A music recommendation system based on user behavior. [33] Recommender systems: We’re doing it (all) wrong. http://technocalifornia. blogspot.be/2011/04/recommender-systems-were-doing-it-all.html. [34] Patty Kostkova Gawesh Jawaheer , Martin Szomszor. Comparison of implicit and explicit feedback from an online music recommendation service. [35] Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30–37, 2009. [36] Doug Cutting and Jan Pedersen. Optimization for dynamic inverted index maintenance. In Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, pages 405–411. ACM, 1989. [37] Jiahui Liu, Peter Dolan, and Elin Rønby Pedersen. Personalized news recommendation based on click behavior. In Proceedings of the 15th international conference on Intelligent user interfaces, pages 31–40. ACM, 2010. [38] Google news. https://news.google.com/. [39] Abhinandan S Das, Mayur Datar, Ashutosh Garg, and Shyam Rajaram. Google news personalization: scalable online collaborative filtering. In Proceedings of the 16th international conference on World Wide Web, pages 271–280. ACM, 2007.

BIBLIOGRAFIE

61

[40] Nathaniel Good, J Ben Schafer, Joseph A Konstan, Al Borchers, Badrul Sarwar, Jon Herlocker, and John Riedl. Combining collaborative filtering with personal agents for better recommendations. In AAAI/IAAI, pages 439–446, 1999. [41] Ricardo Carreira, Jaime M Crato, Daniel Gonçalves, and Joaquim A Jorge. Evaluating adaptive user profiles for news classification. In Proceedings of the 9th international conference on Intelligent user interfaces, pages 206–212. ACM, 2004. [42] Daniel Billsus and Michael J Pazzani. A hybrid user model for news story classification. COURSES AND LECTURES-INTERNATIONAL CENTRE FOR MECHANICAL SCIENCES, 99:108, 1999. [43] Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. Item-based collaborative filtering recommendation algorithms. In Proceedings of the 10th international conference on World Wide Web, pages 285–295. ACM, 2001. [44] Paul Resnick, Neophytos Iacovou, Mitesh Suchak, Peter Bergstrom, and John Riedl. Grouplens: an open architecture for collaborative filtering of netnews. In Proceedings of the 1994 ACM conference on Computer supported cooperative work, pages 175–186. ACM, 1994. [45] Victor Lavrenko, Matt Schmill, Dawn Lawrie, Paul Ogilvie, David Jensen, and James Allan. Language models for financial news recommendation. In Proceedings of the ninth international conference on Information and knowledge management, pages 389–396. ACM, 2000. [46] Owen Phelan, Kevin McCarthy, and Barry Smyth. Using twitter to recommend real-time topical news. In Proceedings of the third ACM conference on Recommender systems, pages 385–388. ACM, 2009. [47] Daniel Billsus and Michael J Pazzani. A personal news agent that talks, learns and explains. In Proceedings of the third annual conference on Autonomous Agents, pages 268–275. ACM, 1999. [48] Lei Li, Dingding Wang, Tao Li, Daniel Knox, and Balaji Padmanabhan. Scene: a scalable two-stage personalized news recommendation system. In Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval, pages 125–134. ACM, 2011.

BIBLIOGRAFIE

62

[49] Owen Phelan, Kevin McCarthy, Mike Bennett, and Barry Smyth. Terms of a feather: Content-based news recommendation and discovery using twitter. In Advances in Information Retrieval, pages 448–459. Springer, 2011. [50] Fabian Abel, Qi Gao, Geert-Jan Houben, and Ke Tao. Analyzing user modeling on twitter for personalized news recommendations. In User Modeling, Adaption and Personalization, pages 1–12. Springer, 2011. [51] Kristina Lerman and Rumi Ghosh. Information contagion: An empirical study of the spread of news on digg and twitter social networks. ICWSM, 10:90–97, 2010. [52] Mária Bieliková, Michal Kompan, and Dušan Zeleník. Effective hierarchical vectorbased news representation for personalized recommendation. Computer Science and Information Systems, 9(1):303–322, 2012. [53] MARCUS LÖNNBERG and LOVE YREGÅRD. Large scale news article clustering. 2013. [54] Pasquale Lops, Marco de Gemmis, and Giovanni Semeraro. Content-based recommender systems: State of the art and trends. In Recommender Systems Handbook, pages 73–105. Springer, 2011. [55] Jae-wook Ahn, Peter Brusilovsky, Jonathan Grady, Daqing He, and Sue Yeon Syn. Open user profiles for adaptive news systems: help or harm? In Proceedings of the 16th international conference on World Wide Web, pages 11–20. ACM, 2007. [56] Robin Burke. Hybrid recommender systems: Survey and experiments. User modeling and user-adapted interaction, 12(4):331–370, 2002. [57] Nachiketa Sahoo, Jamie Callan, Ramayya Krishnan, George Duncan, and Rema Padman. Incremental hierarchical clustering of text documents. In Proceedings of the 15th ACM international conference on Information and knowledge management, pages 357–366. ACM, 2006. [58] Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. What is twitter, a social network or a news media? In Proceedings of the 19th international conference on World wide web, pages 591–600. ACM, 2010. [59] Moses Charikar, Chandra Chekuri, Tomás Feder, and Rajeev Motwani. Incremental clustering and dynamic information retrieval. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 626–635. ACM, 1997.

BIBLIOGRAFIE

63

[60] Yoshiharu Ishikawa, Yibing Chen, and Hiroyuki Kitagawa. An on-line document clustering method based on forgetting factors. In Research and Advanced Technology for Digital Libraries, pages 325–339. Springer, 2001. [61] Xiaoke Su, Yang Lan, Renxia Wan, and Yuming Qin. A fast incremental clustering algorithm. 2009. [62] Digg. http://digg.com/. [63] Digg - wikipedia. http://nl.wikipedia.org/wiki/Digg. [64] Twitter. http://twitter.com/. [65] Reuters dataset. reuters21578/.

http://www.daviddlewis.com/resources/testcollections/

[66] Marco De Gemmis, Leo Iaquinta, Pasquale Lops, Cataldo Musto, Fedelucio Narducci, and Giovanni Semeraro. Preference learning in recommender systems. PREFERENCE LEARNING, 41, 2009. [67] rome. https://rometools.jira.com/wiki/display/ROME/Home. [68] Raymond J Mooney and Loriene Roy. Content-based book recommending using learning for text categorization. In Proceedings of the fifth ACM conference on Digital libraries, pages 195–204. ACM, 2000. [69] Katta. http://katta.sourceforge.net/. [70] Storm. http://storm.incubator.apache.org/. [71] Exponential backoff - wikipedia. http://en.wikipedia.org/wiki/Exponential_ backoff. [72] Jeremy Ginsberg, Matthew H Mohebbi, Rajan S Patel, Lynnette Brammer, Mark S Smolinski, and Larry Brilliant. Detecting influenza epidemics using search engine query data. Nature, 457(7232):1012–1014, 2009. [73] Google flu trends. http://www.google.org/flutrends/. [74] Herman Anthony Carneiro and Eleftherios Mylonakis. Google trends: a web-based tool for real-time surveillance of disease outbreaks. Clinical infectious diseases, 49(10):1557–1564, 2009.

BIBLIOGRAFIE

64

[75] Simeon Vosen and Torsten Schmidt. Forecasting private consumption: survey-based indicators vs. google trends. Journal of Forecasting, 30(6):565–578, 2011. [76] Rachel Tsz-Wai Lo, Ben He, and Iadh Ounis. Automatically building a stopword list for an information retrieval system. In Journal on Digital Information Management: Special Issue on the 5th Dutch-Belgian Information Retrieval Workshop (DIR), volume 5, pages 17–24, 2005. [77] Martin F Porter. Snowball: A language for stemming algorithms, 2001. [78] Peter F Brown, Peter V Desouza, Robert L Mercer, Vincent J Della Pietra, and Jenifer C Lai. Class-based n-gram models of natural language. Computational linguistics, 18(4):467–479, 1992. [79] Carrot2 open source search results clustering engine. http://project.carrot2. org/. [80] Kent Robin Haugen. Mobile news: Design, user experience and recommendation. 2013. [81] Jquery mobile. http://jquerymobile.com/. [82] Google hourly trends. http://www.google.com/trends/hottrends/atom/hourly. [83] Owen Phelan, Kevin McCarthy, Mike Bennett, and Barry Smyth. On using the real-time web for news recommendation & discovery. In Proceedings of the 20th international conference companion on World wide web, pages 103–104. ACM, 2011. [84] Zibin Zheng, Hao Ma, Michael R Lyu, and Irwin King. Wsrec: A collaborative filtering based web service recommender system. In Web Services, 2009. ICWS 2009. IEEE International Conference on, pages 437–444. IEEE, 2009. [85] Sugestio. https://www.sugestio.com/. [86] Anand Rajaraman and Jeffrey David Ullman. Mining of massive datasets. Cambridge University Press, 2012. [87] Lucene tfidf. http://lucene.apache.org/core/4_0_0/core/org/apache/lucene/ search/similarities/TFIDFSimilarity.html.

BIBLIOGRAFIE

65

[88] Z Xu, Minmin Chen, K Weinberger, and Fei Sha. An alternative text representation to tf-idf and bag-of-words. In Proceedings of 21st ACM Conf. of Information and Knowledge Management (CIKM), 2012. [89] Ho Chung Wu, Robert Wing Pong Luk, Kam Fai Wong, and Kui Lam Kwok. Interpreting tf-idf term weights as making relevance decisions. ACM Transactions on Information Systems (TOIS), 26(3):13, 2008. [90] Stefan Büttcher, Charles LA Clarke, and Brad Lushman. Term proximity scoring for ad-hoc retrieval on very large text collections. In Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, pages 621–622. ACM, 2006. [91] John S Whissell and Charles LA Clarke. Improving document clustering using okapi bm25 feature weighting. Information Retrieval, 14(5):466–487, 2011. [92] Robert P Schumaker and Hsinchun Chen. Textual analysis of stock market prediction using breaking financial news: The azfin text system. ACM Transactions on Information Systems (TOIS), 27(2):12, 2009. [93] Qi Gao, Fabian Abel, Geert-Jan Houben, and Ke Tao. Interweaving trend and user modeling for personalized news recommendation. In Proceedings of the 2011 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology-Volume 01, pages 100–103. IEEE Computer Society, 2011. [94] Lei Li, Ding-Ding Wang, Shun-Zhi Zhu, and Tao Li. Personalized news recommendation: a review and an experimental investigation. Journal of Computer Science and Technology, 26(5):754–766, 2011. [95] Artevelde Hogeschool Gent. http://www.arteveldehogeschool.be. [96] Junit. http://junit.org/. [97] Nava Tintarev and Judith Masthoff. A survey of explanations in recommender systems. In Data Engineering Workshop, 2007 IEEE 23rd International Conference on, pages 801–810. IEEE, 2007. [98] Mustafa Bilgic and Raymond J Mooney. Explaining recommendations: Satisfaction vs. promotion. In Beyond Personalization Workshop, IUI, volume 5, 2005.

BIBLIOGRAFIE

66

[99] Jesse Vig, Shilad Sen, and John Riedl. Tagsplanations: explaining recommendations using tags. In Proceedings of the 14th international conference on Intelligent user interfaces, pages 47–56. ACM, 2009. [100] Jonathan L Herlocker, Joseph A Konstan, and John Riedl. Explaining collaborative filtering recommendations. In Proceedings of the 2000 ACM conference on Computer supported cooperative work, pages 241–250. ACM, 2000. [101] G Sudha Sadhasivam. A personalized online news recommendation system.

LĲST VAN FIGUREN

67

Lĳst van figuren 1.1

Evolutie consumptie van nieuwsberichten [5] . . . . . . . . . . . . . . . . .

2

2.1 2.2

Architectuur van een aanbevelingssysteem . . . . . . . . . . . . . . . . . . Verdeling ratings op youtube [21] . . . . . . . . . . . . . . . . . . . . . . .

5 9

3.1

Overzicht architectuur . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

4.1 4.2 4.3 4.4 4.5

vergelijking performantie solr en lucene . . De gebruikersinterface op een smartphone De gebruikersinterface op een tablet . . . . Een Storm topology [70] . . . . . . . . . . De Storm gebruikersinterface . . . . . . . .

. . . . .

27 33 34 36 38

5.1 5.2

Google hourly trends [82] . . . . . . . . . . . . . . . . . . . . . . . . . . . . Uitbreiden van de gebruikersprofielen m.b.v. collaborative filtering . . . . .

41 45

6.1 6.2 6.3 6.4

Evolutie relevante aanbevelingen . . . . . . . . . . . . . Evolutie relevante aanbevelingen - detailopname . . . . Grafische voorstelling logbestand . . . . . . . . . . . . Grootte lucene index als functie van het aantal artikels

49 50 52 53

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . .

Real-time aanbevelingen voor nieuws

Recommend Documents