Optimalisatie van zoekopdrachten voor multimediabestanden

Academiejaar 2008 – 2009

Departement Toegepaste Ingenieurswetenschappen Schoonmeersstraat 52 - 9000 Gent

Optimalisatie van zoekopdrachten voor multimediabestanden

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

An DE MOOR Promotoren: Dr. Veerle ONGENAE Prof. Filip DE TURCK

Woord vooraf Deze masterproef kwam tot stand om mijn opleiding industriële wetenschappen aan Hogeschool Gent af te sluiten. Vier jaar lang heb ik zowel theoretische als praktische kennis kunnen verwerven, in het bijzonder over de huidige computertechnologie. Het was een lange, maar ook leerrijke en boeiende ontdekkingsreis. Ik ben dan ook blij dat ik als kers op de taart dit eindwerk kan voorstellen.

Het wereldwijde web is vandaag de dag niet meer weg te denken uit onze leefwereld. Er is een brede waaier aan informatie beschikbaar, verspreid over enkele miljarden pagina’s. Door het snel groeiende web wordt het ook steeds moeilijker om de juiste informatie terug te vinden. Dit roept de vraag op hoe mensen én computers toch nog een zinvolle betekenis kunnen hechten aan al deze gegevens. Deze scriptie gaat er dan ook over om informatie voor eindgebruikers beter doorzoekbaar te maken. Meer specifiek worden methodes onderzocht om gegevens uit een database met multimediale bestanden, de BOM-Vl-database (of kortweg BOM-database), toegankelijker te maken. BOM-Vl, ’Bewaring en Ontsluiting van Multimedia in Vlaanderen’ is een project dat het audiovisueel erfgoed van Vlaanderen digitaal moet bewaren en vrijgeven (BOM-Vl - Bewaring en Ontsluiting van Multimediale Data in Vlaanderen, 2008). Vlaanderen beschikt over enkele duizenden uren beeld- en spraakmateriaal, opgeslagen op analoge dragers. Digitalisatie moet ervoor zorgen dat deze archieven op lange termijn nog bruikbaar zijn. De ontsluiting van deze audiovisuele collectie zorgt ervoor dat iedere ge¨ınteresseerde bijkomende kennis kan verwerven over de Vlaamse cultuur. Momenteel bevat de database die bij dit project hoort, reeds 5.000 uur aan gebroadcast televisiemateriaal. Dit komt overeen met 166.728 televisiefragmenten. Deze bestanden kunnen worden doorzocht met behulp van een klassieke zoekmachine die reeds voorzien is.

Door de

grote hoeveelheid aan gegevens is het echter niet steeds evident om de juiste informatie terug te vinden. Om het zoekproces te vergemakkelijken, zijn daarom tekstuele metadata aan de fragmenten toegevoegd. Ook services zoals YouTube en Google Video maken gebruik van dit soort annotaties, zodat videofragmenten gemakkelijker kunnen worden teruggevonden. Deze metadata kunnen in verschillende vormen aanwezig zijn: systeeminformatie over de bestanden, indeling in categorieën, tags, enzovoort.

Bij de toevoeging van metadata kan echter geen rekening worden gehouden met alle mogelijke scenario’s waarin een gebruiker naar een bepaald fragment zoekt.

Er bestaat dus een kloof

tussen de manier van annoteren en de manier waarop gebruikers items opzoeken. Dit is zeker het geval wanneer bestanden worden gemarkeerd met tags, of zelfgekozen sleutelwoorden. Er kunnen namelijk verschillende tags worden gebruikt voor gelijkaardige concepten: synoniemen, verschillende talen en spellingsfouten kunnen het zoekproces bemoeilijken. Om de zoekresultaten voor eindgebruikers te verbeteren, kunnen een aantal technieken worden toegepast: er kunnen onder andere domeinspecifieke ontologieën worden opgesteld, er kan worden rekening gehouden met gebruikersvoorkeuren, metadata kan worden geclusterd, er kan worden gewerkt met suggesties of een betere visualisatie, en informatie uit verschillende databases kan worden gecombineerd.

Deze scriptie onderzoekt enkele van deze technieken, die kunnen worden toegepast op de BOM-database: Hoofdstuk één behandelt tag clouds, een mechanisme waardoor gebruikers gemakkelijker kunnen navigeren doorheen zoekresultaten. Een tag cloud bevat een visuele weergave van tags die aan bestanden zijn toegevoegd. Hoe groter de tag wordt afgebeeld, hoe vaker deze in de resultaten voorkomt. Na het aanklikken van een tag komt de gebruiker op een pagina met gerelateerde onderwerpen terecht. Het volgende hoofdstuk gaat verder in op de opbouw van enkele domeinspecifieke ontologieën: er wordt besproken hoe de kennis over deelgebieden van België en over het Belgische voetbal kan worden ondergebracht in een ontologie. Deze laatste is een datastructuur, waarin concepten en relaties kunnen worden beschreven. Zo kunnen ook computers gaan redeneren over gegevens, waardoor het mogelijk wordt om meer doelgerichte query’s uit te voeren. Zo kan met de ontologie van België worden gezocht naar gebeurtenissen die zich hebben afgespeeld binnen een bepaald gebied van België. De voetbalontologie maakt het onder andere mogelijk om te zoeken naar personen, die een bepaalde rol hebben vervuld in het voetbal, gedurende een bepaalde periode. Ook kennis uit andere databanken kan interessante informatie opleveren. Het laatste deel van deze scriptie behandelt twee van deze databanken: De eerste databank wordt voorzien door Flickr, een service waar gebruikers foto’s op kunnen sharen. Deze foto’s zijn meestal voorzien van tags, en sluiten goed aan op het taalgebruik van het publiek. De Flickr service kan dan ook worden gebruikt om relaties tussen tags te onderzoeken. Tags die vaak samen voorkomen, kunnen worden gebruikt om meer relevante zoekresultaten te bekomen. De tweede databank bevat geografische informatie van over de hele wereld, en wordt voorzien door de Geonames service. Deze informatie kan worden gebruikt om plaatsnamen uit metadata te extraheren, om zo meer intelligente query’s te kunnen uitvoeren: een gebruiker kan op zoek gaan

naar alle fragmenten die gaan over gebeurtenissen, die zich in een bepaalde regio afspeelden, of die plaatsvonden binnen een bepaalde straal, rond een bepaalde plaats. De resultaten kunnen ook visueel worden voorgesteld aan de hand van de Google Maps service. Voor elke techniek wordt besproken hoe het systeem in Java wordt ge¨ımplementeerd, en in hoeverre de techniek bijdraagt tot een verbetering van de relevantie en/of volledigheid van de set zoekresultaten. Ter verduidelijking worden zowel Engelse termen als implementatieklassen en -methoden in het cursief aangeduid.

Langs deze weg zou ik ten slotte graag nog enkele personen bedanken, die één voor één instonden voor de nodige hulp en steun. Vooreerst mijn oprechte dank aan de mensen van INTEC, die mij dit onderzoeksvoorstel en een stageplaats aanboden. In het bijzonder dank ik mijn promotor, prof. Filip De Turck, en mijn begeleiders dr. Tim Wauters, ir. Stijn Vandamme en ir. Johannes Deleu. Zij zorgden voor de interessante items die ik mocht onderzoeken en voor een goede begeleiding. Ook aan mijn interne promotor, dr. Veerle Ongenae, richt ik graag een woord van dank. Zij zorgde voor de opvolging van mijn thesis en gaf me raad waar nodig. Mijn dank gaat ook uit naar Kathleen Pollefliet, die nuttige tips gaf over de vormgeving en het schrijfproces van de thesis. Daarenboven maakte zij tijd vrij om een gedeelte van deze scriptie na te lezen en te becommentariëren. Ook dr. Jan Cnops dank ik om een deel van mijn scriptie na te lezen. Daarnaast wil ik ook de co¨ ordinator van de masterproef, dr. Marleen Denert, bedanken. Zij zorgde voor de nodige informatie omtrent de thesis en berichtte over de uit te voeren taken. Ten slotte wil ik ook nog een speciaal woord van dank richten aan mijn ouders en mijn vriend. Hun morele steun door de jaren heen zal ik zeker niet vergeten.

An De Moor Wetteren, juni 2009

Abstract (English) Often, metadata are added to multimedia files, to facilitate search in multimedia databases. However, there is a gap between the way of annotation and the way users search for items. This thesis presents some techniques that can be used to improve search results. The first section describes how tags can be visualized by using tag clouds. This mechanism allows the user to easily navigate through search results. The next section discusses how domain knowledge can be represented by ontologies. With the help of these data structures, users can perform more sophisticated queries. Also knowledge from other databases can yield interesting information. The last section of this thesis discusses two of these databases: Flickr and Geonames. The first one, a photo database, can be used to discover relationships between tags. Tags that often occur together, can help the user to find more relevant search results. The second one, a geographical database, can be used to extract place names from metadata. The extracted data make it possible for users to search for events that have occurred around a certain area. This thesis deals with the manner in which these techniques were implemented and tested. KEYWORDS: multimedia databases; metadata; optimized search results; tag cloud; ontology; tag relations; Flickr; Geonames

Abstract (Nederlands) Vaak worden metadata toegevoegd aan multimediale bestanden, zodat deze gemakkelijker kunnen worden teruggevonden in databanken. Er bestaat echter een kloof tussen de manier van annoteren en de manier waarop gebruikers items zoeken. In deze scriptie worden enkele technieken besproken, die kunnen bijdragen tot betere zoekresultaten. Het eerste deel beschrijft hoe tags kunnen worden gevisualiseerd, door middel van tag clouds, zodat gebruikers gemakkelijk doorheen zoekresultaten kunnen navigeren. Het tweede deel behandelt hoe domeinkennis kan worden ondergebracht in ontologieën, zodat meer expressieve query’s kunnen worden uitgevoerd. Ook kennis uit andere databanken kan interessante informatie opleveren. Het laatste deel van deze scriptie behandelt twee van deze databanken: Flickr en Geonames. De eerste, een fotodatabank, kan worden gebruikt om relaties tussen tags te zoeken. Tags die vaak samen voorkomen, kunnen de gebruiker helpen om meer relevante zoekresultaten te vinden. De tweede, een geografische databank, kan worden gebruikt om plaatsnamen uit metadata te extraheren. De geëxtraheerde data maken het mogelijk voor gebruikers om te zoeken naar gebeurtenissen die zich rond een bepaald gebied hebben afgespeeld. Deze scriptie behandelt de manier waarop deze technieken werden ge¨ımplementeerd en getest. SLEUTELWOORDEN: multimediale databases; metadata; geoptimaliseerde zoekresultaten; tag cloud ; ontologie; tag relaties; Flickr; Geonames

7

Inhoudsopgave Woord vooraf

2

Abstract (English)

5

Abstract (Nederlands)

6

Lijst met afkortingen

10

1 Tag Cloud

11

1.1

Het begrip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.2

BOM-gebruikersinterface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.3

BOM-tag clouds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3.1

Werking applicatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.3.2

Implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.3.3

Aanpassingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.3.3.1

1.4

Threadpool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Testresultaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2 Ontologie

28

2.1

Semantisch Web . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.2

Technologieën . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2.1

RDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2.1.1

RDF Schema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.2.2

OWL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.2.3

SPARQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.3

Validatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.4

CROEQS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.5

Toepassingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.5.1

2.5.2

Ontologie van België . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.5.1.1

Implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.5.1.2

Opmerkingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

Voetbalontologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

Inhoudsopgave

8

3 Tag relaties

44

3.1

Tags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.2

Flickr API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.3

Tag Recommendation System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.3.1

Tag co-occurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3.3.2

Tag aggregatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.3.3

Promotie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.3.4

Aanpassingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3.3.5 3.4

3.3.4.1

Gegevensopslag

3.3.4.2

Related tags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

Resultaten

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

Toepassing op BOM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.4.1

BOM-keyword relaties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.4.2

Implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.4.3

Testresultaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4 Extractie van plaatsnamen

64

4.1

Algemeen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

4.2

Geonames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

4.3

Bepaling van BOM-geonames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.3.1

Parsen van BOM-beschrijvingen . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.3.1.1

4.3.2

4.3.3 4.4

4.5

Opslag van BOM-geonames . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.3.2.1

Term-document matrix & inverted file . . . . . . . . . . . . . . . . . 70

4.3.2.2

Implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

Resultaten

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

Plaatsnamen binnen een bepaalde regio . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.4.1

Semantische query’s: boomstructuur van geonames . . . . . . . . . . . . . . . 80

4.4.2

Implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

4.4.3

Testresultaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

Plaatsnamen binnen een bepaalde straal . . . . . . . . . . . . . . . . . . . . . . . . . 88 4.5.1

Uitbreiding van de semantische query’s

4.5.2

Kortste Afstand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

4.5.3

Bepaling van de plaatsen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 4.5.3.1

4.6

Implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

. . . . . . . . . . . . . . . . . . . . . 88

K-d tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

4.5.4

Visualisatie van de resultaten: Google Maps . . . . . . . . . . . . . . . . . . . 95

4.5.5

Implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

4.5.6

Testresultaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

Evaluatie van geonames: deel 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.6.1

Filteren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

Inhoudsopgave

4.6.2

9 4.6.1.1

Beslissingsdiagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

4.6.1.2

Implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

Vergelijking met keywords . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 4.6.2.1

4.6.3 4.7

Implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

Resultaten

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

Evaluatie van geonames: deel 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 4.7.1

Implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

4.7.2

Resultaten

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

Lijst met figuren

124

Lijst met tabellen

126

Literatuurlijst

128

A Ontologie

I

B Geonames (1)

IV

C Geonames (2)

VII

D Handleiding bij CD-ROM

IX

10

Lijst met afkortingen API

Application Programming Interface

BOM-Vl

Bewaring en Ontsluiting van Multimediale Data in Vlaanderen

CROEQS Contemporaneous Role Ontology-based Expanded Query Search CSS

Cascading Style Sheets

DOM

Document Object Model

FIFO

First In, First Out

OWL

Web Ontology Language

RDBMS

Relational Database Management System

RDF

Resource Description Framework

RDFS

Resource Description Framework Schema

REST

Representational State Transfer

SAX

Simple API for XML

SOAP

Simple Object Access Protocol

SPARQL SPARQL Protocol and RDF Query Language URI

Uniform Resource Identifier

UTF-8

8-bit Unicode Transformation Format

W3C

World Wide Web Consortium

XML

eXtensible Markup Language

11

Hoofdstuk 1

Tag Cloud 1.1

Het begrip

Datasets bevatten vaak een overvloed aan gegevens. Voor de gebruiker is het niet altijd even gemakkelijk om te navigeren doorheen al deze items. Een visuele representatie van de gegevens kan hierbij een oplossing bieden. Vaak wordt hiervoor een tag cloud gebruikt: dit is een wolk van woorden, die een visuele weergave is van inhoudstags. Deze wolken worden vaak op websites gebruikt. De inhoudstags zijn labels die aan een content worden toegevoegd, zodat deze achteraf gemakkelijk kunnen worden weergevonden. Wanneer de gebruiker een zoekstring ingeeft, worden alle tags die in de resultset voorkomen, afgebeeld.

Tags die vaker voorkomen, worden groter weergegeven.

Indien de resultset veel

verschillende tags bevat, kan het zijn dat er een maximum opgelegd wordt aan het aantal te tonen tags. De wolk zal dan enkel de meest relevante tags bevatten. Na het aanklikken van zo’n tag komt de gebruiker op een pagina met gerelateerde onderwerpen terecht. Figuur 1.1 toont een voorbeeld van een tag cloud.

Figuur 1.1: Voorbeeld van een tag cloud (WebResources Depot, 2008)

Deze techniek kan ook worden toegepast op de BOM-dataset. Zoals vermeld in ’Woord Vooraf’, bevat deze database gebroadcast televisiemateriaal uit Vlaanderen. Aan de hand van tags die aan de beeldfragmenten zijn toegevoegd, kan voor elke zoekopdracht een bijhorende tag cloud worden gegenereerd. Wanneer een gebruiker op één van deze tags klikt, worden de resultaten van de

Hoofdstuk 1. Tag Cloud

12

zoekopdracht verfijnd: enkel de beeldfragmenten waarbij ook de aangeklikte tag is toegevoegd aan de metadata, worden nog opgenomen in de resultset. Dit hoofdstuk gaat dan ook verder in op de manier hoe een gebruikersinterface wordt voorzien, die tag clouds voor de BOM-database genereert.

1.2

BOM-gebruikersinterface

Een gebruiker kan BOM-fragmenten opzoeken aan de hand van de BOM-interface. Deze is lokaal beschikbaar onder de vorm van een webapplicatie. In de tekstbox kan een zoekstring worden ingegeven, waarna vervolgens een HTML-pagina wordt gegenereerd met de resultaten, gesorteerd op dalende relevantie. In feite wordt er een HTTP POST-request gestuurd naar de zoekmachine. De teruggezonden HTTP-response bevat het totaal aantal items die voldoen aan de query, samen met de details van de eerste tien resultaten. Figuur 1.2 toont als voorbeeld de gegenereerde HTTP-response voor de zoekopdracht ’gent’. Voor deze zoekopdracht worden 8.677 relevante fragmenten gevonden. De figuur toont de details (metadata) van het eerste resultaat.

Figuur 1.2: Eerste resultaat voor zoekopdracht ’gent’


1.3

13

BOM-tag clouds

Indien een gebruiker alle resultaten van een zoekopdracht wil overlopen, kan dit heel wat tijd vergen. De resultaten zullen waarschijnlijk ook fragmenten bevatten, waar de gebruiker niet ge¨ınteresseerd in is. Er zijn dan twee opties: ofwel verfijnt de gebruiker zelf zijn zoekopdracht, ofwel vraagt hij aan de zoekmachine om hem een handje te helpen. Bij deze laatste optie zou de zoekmachine bijvoorbeeld een globaal overzicht kunnen geven van de zoekresultaten. Dit kan handig zijn wanneer de gebruiker de zoekopdracht niet gedetailleerd kan omschrijven. Een globaal overzicht van de zoekresultaten tonen, is niet evident, want de fragmenten kunnen over uiteenlopende onderwerpen gaan. Indien de zoekopdracht echter veel resultaten oplevert (zoals de query ’gent’), zullen er meestal fragmenten zijn die handelen over gelijkaardige onderwerpen. Deze onderwerpen zijn vaak ook opgenomen in de metadata van de fragmenten. Die metadata kunnen worden gebruikt in een tag cloud, die op zijn beurt kan helpen om de gebruiker een algemeen beeld te geven van alle zoekresultaten. Een tag cloud moet uiteraard over tags beschikken.

Hiervoor wordt de waarde van elke

MediaObjectFragmentKeyword sleutel uit de metadata van de zoekresultaten gebruikt (zie figuur 1.2). Deze waarde bestaat uit meerdere termen, waarbij elke term kan beschouwd worden als een tag. Deze worden echter niet allemaal in de tag cloud opgenomen, omdat deze anders te veel tags zou bevatten. Enkel degene die het vaakst terugkomen in de resultaten, worden opgenomen. Het aantal kan bijvoorbeeld beperkt blijven tot twintig verschillende tags.

1.3.1

Werking applicatie

Om de tag clouds te genereren, wordt een grafische gebruikersinterface in Java ontwikkeld. Figuur 1.3 toont een screenshot van de applicatie.

Figuur 1.3: Tag cloud voor zoekopdracht ’urbanus’


14

In het query tekstveld kan de gebruiker een zoekopdracht invoeren. Het gewenst aantal te tonen tags kan worden ingesteld door middel van het #tags tekstveld. Indien de gebruiker op de searchknop duwt, wordt de tag cloud gegenereerd. Het resultaat verschijnt onderaan in het venster. Wanneer bijvoorbeeld op de tag ’film’ wordt geklikt, worden terug de eerste tien zoekresultaten in een webbrowser weergegeven. Het aantal resultaten is hiermee beperkt tot 132, terwijl de niet verfijnde zoekopdracht (’urbanus’) 343 resultaten oplevert. Om de verfijnde resultaten te genereren, wordt een nieuwe HTML-request verstuurd, voor de volgende zoekopdracht: ’+urbanus +MediaObjectFragmentKeyword:FILM’. De plustekens duiden aan dat de twee termen moeten voorkomen in de resultaten (’en’-operatie). Indien deze plustekens worden weggelaten, wordt een ’of’-operatie uitgevoerd: hierbij bevatten de resultaten ofwel de term ’urbanus’, ofwel de term ’MediaObjectFragmentKeyword:FILM’. De lijst met resultaten wordt automatisch gerangschikt volgens dalende orde van relevantie, waardoor resultaten die beide termen bevatten bovenaan de lijst komen te staan. Algemeen geldt het volgende: • Een woord in de query zonder ’+’ of ’-’ vooraan komt het liefst voor in de ge¨ındexeerde velden. Als het woord niet voorkomt, daalt de relevantie. • Een woord in de query met een ’+’ moet voorkomen. • Een woord in de query met een ’-’ mag niet voorkomen. De gebruiker kan dus ook eerst zelf de zoekopdracht verfijnen:

wanneer bijvoorbeeld de

zoekopdracht ’+urbanus +film’ wordt uitgevoerd, bevatten alle resultaten zeker de twee termen. Bij deze query wordt er echter in alle ge¨ındexeerde velden gezocht naar de term ’film’. Bij de aangeklikte tag in de tag cloud is dit niet het geval: daar wordt de term enkel gezocht in de MediaObjectFragmentKeyword velden. Door deze verfijnde opdracht bevat de tag cloud andere tags, zoals te zien is op figuur 1.4. Om de tag cloud op te stellen, moeten alle detailpagina’s met de resultaten worden overlopen. Dit vergt echter veel tijd: standaard bevat elke HTTP-response de details van tien resultaten. Er moeten evenveel HTTP-requests gebeuren als er pagina’s zijn. Het opvragen van de antwoorden kan hierbij enige tijd in beslag nemen. Daarom is de grafische interface voorzien van een extra tekstveld: het max res tekstveld. Hierin kan de gebruiker aangeven hoeveel resultaten er maximum moeten worden verwerkt in de tag cloud. Wanneer dit aantal bijvoorbeeld 500 is, worden enkel de MediaObjectFragmentKeyword velden van de eerste 500 meest relevante resultaten verwerkt in de tag cloud.


15

Figuur 1.4: Tag cloud voor zoekopdracht ’+urbanus +film’

1.3.2

Implementatie

De tag cloud wordt ge¨ımplementeerd in Java. De BOM-resultset die bij een specifieke zoekopdracht hoort, is ook als XML-versie beschikbaar. Om bijvoorbeeld de eerste tien resultaten op te vragen van de zoekopdracht ’leterme’, kan achter de padnaam van de URL (/bomvl4/osearch) de volgende querystring worden opgegeven: ’ ?q=leterme’. Hiermee wordt een HTTP-response gegenereerd in XML-vorm. (Om dit antwoord als HTML-versie te verkrijgen wordt in de padnaam ’osearch’ vervangen door ’search’.) De volgende tien resultaten kunnen worden verkregen door aan de querystring het volgende toe te voegen: ’&pw=10’. Zo kunnen alle resultaten worden opgevraagd. Al deze XML-gegevens kunnen worden verwerkt met een Java SAX-parser. Om de tag clouds te genereren, wordt gebruikgemaakt van een reeds bestaande Java library, OpenCloud (Open Cloud, 2008). Figuur 1.5 toont een overzicht van alle klassen die de applicatie gebruikt. Hieronder worden ze elk kort besproken. De Java bibliotheek OpenCloud biedt reeds enkele klassen om tag clouds gemakkelijk te kunnen construeren. Hiervan worden drie klassen gebruikt in de applicatie: Tag - Deze klasse bevat een aantal attributen om een tag voor te stellen. Onder andere de naam, de hyperlink waarnaar gesurfd wordt wanneer op de tag geklikt wordt, en het aantal keer dat een tag voorkomt in het resultaat (score attribuut), worden hierin bijgehouden. Daarnaast is er ook een gewicht-attribuut, dat de belangrijkheid van de tag aangeeft. Verder wordt met behulp van de methode normalize(int) nog een genormaliseerde score toegekend aan de tag, die berekend wordt aan de hand van de meegegeven factor.


16

Figuur 1.5: Overzicht van de tag cloud applicatie klassen

Cloud - De klasse Cloud houdt alle tags bij in een map van het type HashMap<String,Tag>. Verder bevat deze klasse attributen die bepaalde vereisten en beperkingen opleggen aan de inhoud van de cloud: minWeight en maxWeight leggen bijvoorbeeld een minimum- en maximumwaarde aan de taggewichten op. Het attribuut maxTagsToDisplay legt een maximum op aan het aantal tags die in de visuele wolk worden getoond. Als laatste is er ook een drempelwaarde voorzien (threshold attribuut): dit specifieert het minimum aantal keer dat een tag moet voorkomen in de resultset, zodat hij opgenomen zou worden in de tag cloud. Een afgeleid attribuut houdt ook nog de genormaliseerde drempelwaarde bij. Daarnaast zijn er ook een aantal methoden die zorgen voor het beheer van de tags: De methode addTag(Tag) voegt een Tag toe aan de wolk. Indien een tag met dezelfde naam reeds is opgeslagen, wordt de score vermeerderd, zoniet wordt deze op één gezet. De methode tags() geeft een lijst terug met alle Tag objecten die behoren tot de wolk. Deze methode doet hiervoor beroep op de protected getOutputTags() methode. Deze houdt rekening met de opgelegde voorwaarden, zoals gespecifieerd door de attribuutwaarden: het aantal tags wordt beperkt door maxTagsToDisplay (gesorteerd volgens dalende score), tags die een (genormaliseerde) score hebben onder de drempelwaarde worden verwijderd, enzovoort. Om dit laatste te kunnen uitvoeren, worden eerst de genormaliseerde scores van alle tags ingesteld door middel van de normalize(int) functie. Hierbij is de meegegeven factor


17

gelijk aan de hoogste score die voorkomt in de taglijst. Aan de hand van dit kunnen ook de gewichten van de tags worden ingesteld. Daarvoor wordt de volgende berekening uitgevoerd:

tag . setWeight ( getMinWeight ( ) + tag . getNormScore ( ) ∗ ( getMaxWeight ( ) − getMinWeight ( ) ) ) ;

Het gewicht geeft de mate van belangrijkheid voor de tag aan. Met de getOutputTags() methode wordt dus een lijst van tags bekomen die ook effectief in de visuele tag cloud worden getoond. HTMLFormatter - De HTML-uitvoer van de tag cloud wordt gegenereerd door de methode html(Cloud, Comparator) van de klasse HTMLFormatter. Als argument wordt een Cloud object meegegeven. Eventueel kan ook een comparator worden opgegeven, die de tags in een specifieke volgorde uitschrijft. Indien deze de waarde null krijgt, worden de tags standaard in alfabetische volgorde uitgeschreven. De tags die moeten worden uitgeschreven, worden opgevraagd door middel van de tags() methode van het Cloud object. De vormgeving van de tags wordt verzorgd door middel van de methode css(Cloud).

Deze genereert de nodige CSS-code.

De

lettergrootte van de tag wordt gelijkgesteld aan het corresponderende taggewicht. Verder worden ook de overeenstemmende hyperlinks ingesteld. Met behulp van deze drie klassen kunnen reeds tag clouds worden geconstrueerd. De klassen voorzien echter niet de mogelijkheid om een minimum en maximum lettergrootte op te geven. Daarom worden twee bijkomende afgeleide klassen geschreven: CloudExt en HTMLFormatterExt. De eerste klasse is afgeleid van Cloud en bevat één extra methode: setFont(double minFont, double maxFont). Deze zorgt ervoor dat er een minimum en maximum lettergrootte kan worden opgelegd. Hieronder wordt de bijhorende code afgebeeld:

p u b l i c v o i d setFont ( d o u b l e min , d o u b l e max ) { List tags = allTags ( ) ; s e t M i n M a x R e a l W e i g h t ( tags ) ; double w = 0 . 0 ; f o r ( i n t i =0; i
Opdat de tags de juiste lettergrootte zouden hebben, moeten de taggewichten worden aangepast.


18

Dit kan door voor elke tag de lineaire functie uit te voeren, zoals weergegeven in het else-gedeelte van de if -else-structuur (Howe, 2006). Ook worden de nodige maatregelen getroffen om een deling door nul te voorkomen. Met behulp van deze methode worden de gewichten (en lettergroottes) dus aangepast volgens de twee meegegeven drempelwaarden. Voor deze berekening uit te voeren moeten echter ook het minimum en maximum gewicht, die voorkomen in de CloudExt, gekend zijn. Daarom worden twee extra attributen voorzien, minWeightReal en maxWeightReal, die deze informatie bijhouden. De invulling van de waarden gebeurt door een extra methode die wordt voorzien: setMinMaxRealWeight(List tags). Deze overloopt alle meegegeven tags, en houdt de tijdelijke minimum- en maximumwaarde bij. Op het einde van de lus bevatten de twee attributen dan de juiste waarden. Opdat de aangepaste gewichten (en lettergroottes) ook effect zouden hebben op de HTML-uitvoer van de tag cloud, wordt ook een afgeleide klasse van HTMLFormatter voorzien: HTMLFormatterExt. Deze implementeert één extra methode: html(CloudExt cloud, Comparator comparator, double min, double max). De code is gelijkaardig aan die van de html(Cloud, Comparator) methode van de bovenliggende klasse, maar voorziet twee extra parameters. Hiermee kunnen de minimum en maximum lettergrootte worden aangepast: hiervoor wordt de setFont(double min, double max) methode van de CloudExt klasse opgeroepen. Indien er geen resultaten worden gevonden voor een ingegeven zoekstring (de lijst met tags van het CloudExt object is dan leeg), wordt een HTML-pagina gegenereerd met als uitvoer: No results found. Dit werd ook niet voorzien in de html methode van de HTMLFormatter klasse.

Naast de uitbreiding van de OpenCloud klassen, worden ook nog de volgende klassen ge¨ımplementeerd: ZoekInfo - De klasse Zoekinfo wordt gebruikt om een aantal gegevens bij te houden die betrekking hebben op de HTTP-request en HTTP-response, die horen bij een zoekopdracht die de gebruiker heeft ingegeven. Deze zoekopdracht wordt opgeslagen in het zoekString attribuut. Het afgeleide attribuut zoekUri zorgt ervoor dat de juiste string wordt ingesteld die de HTTP-request van de zoekstring voorstelt. Deze URL moet ook worden gecodeerd in UTF-8 formaat. Hiervoor wordt de methode encode(String s, String enc) gebruikt van de klasse java.net.URLEncoder. Als eerste parameter wordt hierbij de te coderen URL opgegeven, als tweede de encoderingsvorm: ’UTF-8’. Alfanumerieke tekens worden hierbij omgezet naar de bijhorende hexadecimale ASCII-waarde zodat een welgevormde URL ontstaat. Verder bevat deze klasse nog een aantal attributen die horen bij de HTTP-response: het totaal aantal resultaten, en het aantal resultaten per pagina worden hierin bijgehouden. Hieruit kan dan worden afgeleid hoeveel pagina’s er moeten worden geparset om alle resultaten te doorlopen. Hoe meer resultaten er zijn, hoe langer het duurt om de tag cloud te genereren. Daarom kan de gebruiker eventueel ingeven hoeveel resultaten maximaal moeten worden verwerkt. Dit aantal wordt bijgehouden in het attribuut maxResultaten. Als laatste bevat de klasse ook een methode


19

getTagUri(String tag), die aan de hand van de opgegeven tag de juiste URL-string genereert. Deze methode wordt gebruikt om de verschillende tags in de tag cloud te laten verwijzen naar de juiste HTML-pagina, die moet worden gegenereerd bij een klik op de tag. Om de XML-vorm van de HTTP-responses te verwerken, worden twee klassen voorzien. Deze zorgen ervoor dat de antwoorden worden geparset. Er wordt gekozen voor SAX, en niet voor DOM, omdat maar een gedeelte van de gegevens nodig is. Bovendien vereist SAX minder geheugen dan DOM. De twee gebruikte klassen zijn: SAXController - Om ervoor te zorgen dat de XML-antwoorden kunnen worden geparset, wordt de klasse SAXController aangemaakt. De constructor ziet er als volgt uit:

p r i v a t e XMLReader reader ; p r i v a t e SAXHandler handler ; p u b l i c SAXController ( ) { try { S A X P a r s e r F a c to r y factory = S A X P a r s e r F a c t o ry . newInstance ( ) ; SAXParser parser = factory . newSAXParser ( ) ; reader = parser . getXMLReader ( ) ; handler = new SAXHandler ( ) ; reader . s e t C o n t e n t H a n d l e r ( handler ) ; } catch ( ParserConfigurationException e ) { e . p ri nt St a ck Tr ac e ( ) ; } c a t c h ( SAXException e ) { e . p ri nt St a ck Tr ac e ( ) ; } }

Er wordt eerst een SAXParser aangemaakt. Hiervan wordt de XMLReader opgevraagd, die de XML-antwoorden kan parsen. Als ContentHandler wordt een referentie naar een SAXHandler object meegegeven. Verder bevat deze klasse de methode parsePaginas(ZoekInfo, CloudExt). Deze zorgt ervoor dat alle detailpagina’s worden geparset, die bij het resultaat van een zoekopdracht horen. De bijhorende code wordt hieronder weergegeven:

p u b l i c v o i d parsePaginas ( ZoekInfo zoekInfo , CloudExt cloud ) { handler . setCloud ( cloud ) ; handler . setZoekInfo ( zoekInfo ) ; reader . parse ( zoekInfo . getZoekUri ( ) ) ; i n t aantal = zoekInfo . g e t A a n t a l P a g i na s ( ) ; i n t res = zoekInfo . g e t A a n t a l R e s u l t a t e n ( ) ; i f ( zoekInfo . g e t M a x R e s u l t a t e n ( ) != −1 && res > zoekInfo . g e t M a x R e s u l t a te n ( ) ) { aantal = zoekInfo . g e t M a x R e s u l t a te n ( ) / zoekInfo . g e t A a n t a l P e r P a g i n a ( ) ; } i n t volgende = 0 ;


20

f o r ( i n t i = 0 ; i < aantal ; i++) { volgende += zoekInfo . g e t A a n t a l P e r P a g i n a ( ) ; String pag = zoekInfo . getZoekUri ( )+”&pw=”+volgende ; reader . parse ( pag ) ; } }

Als eerste worden de twee parameters als referentie doorgegeven aan de SAXHandler.

Deze

worden gebruikt om de waarden van de juiste XML-elementen bij te houden en op te slaan. Elke XML-pagina bevat een XML-element os:totalResults, dat het totaal aantal resultaten van de zoekopdracht bijhoudt, en een element os:itemsPerPage, dat het aantal fragmenten per pagina bijhoudt.

Aan de hand van deze elementen weet de parsePaginas methode hoeveel keer de

parse(String) methode van de XMLReader moet worden opgeroepen. Aangezien dit aantal pas gekend is na de eerste pagina geparset te hebben, wordt de parse methode eerst één keer opgeroepen. De URL van de te parsen pagina zit in het meegegeven ZoekInfo object. Nadat de methode is uitgevoerd, bevat dit laatste object het aantal pagina’s dat effectief moet worden geparset, samen met het totaal aantal resultaten. Het kan echter zijn dat de gebruiker een maximum waarde heeft opgegeven voor het aantal te verwerken resultaten. Deze waarde zit in het maxResultaten attribuut van het ZoekInfo object. Hiermee moet dan ook rekening worden gehouden. Met deze kennis kan de parse methode nog eens het gewenst aantal keer worden uitgevoerd, door telkens een aangepaste parameter mee te geven. Wanneer een zoekopdracht bijvoorbeeld 34 resultaten telt, en er bevinden zich tien resultaten op één pagina, dan kunnen de laatste vier resultaten als volgt worden opgehaald: /bomvl4/osearch?q=query&pw=30, met als waarde voor query uiteraard de ingegeven zoekstring. SAXHandler - De klasse die de XML-elementen effectief parset en verwerkt, is SAXHandler. Deze klasse implementeert de interface ContentHandler, en parset de documenten. Voor de volgende drie methoden wordt een implementatie voorzien:

v o i d startElement ( String uri , String localName , String qName , Attributes atts ) throws SAXException v o i d endElement ( String uri , String localName , String qName ) throws SAXException v o i d characters ( c h a r [ ] ch , i n t start , i n t length ) throws SAXException

De methoden startElement en endElement zijn nodig om bij te houden welk soort XML-element aan de beurt is.

De characters methode zorgt voor de verwerking van de waarden

die bij de elementen horen.

Behalve bij de eerste pagina, moeten enkel de elementen

bomvl:MediaObjectFragmentKeyword worden verwerkt. Voor elk van deze elementen wordt een nieuw Tag object aangemaakt, en toegevoegd aan het CloudExt object. De Tag constructor verwacht drie parameters: een naam, een link en een score. Als naam wordt de waarde van het XML-element opgegeven. De bijhorende link wordt opgevraagd aan de getTagUri(String) methode


21

van het ZoekInfo object. Als score wordt ten slotte de waarde één meegegeven. Wanneer de eerste pagina wordt geparset die bij een HTTP-response hoort, worden ook de elementen os:totalResults en os:itemsPerPage verwerkt. Ook deze info wordt opgeslagen in het ZoekInfo object, zodat de SAXController weet hoeveel pagina’s er moeten worden verwerkt. De referenties naar het ZoekInfo en CloudExt object worden bij iedere nieuwe zoekopdracht van de gebruiker veranderd door de SAXController. HTMLBuilder - De opdracht om de resultaten van de zoekstring te parsen, en te verwerken in een tag cloud, wordt gegeven door de klasse HTMLBuilder. Deze maakt gebruikt van het Singleton Pattern. Er wordt een private constructor voorzien, zodat slechts één instantie van deze klasse kan worden aangemaakt. Deze instantie kan worden opgeroepen door middel van de getInstance() methode. In de constructor wordt een SAXController object aangemaakt. Deze zorgt ervoor, zoals eerder vermeld, dat de HTTP-responses worden geparset. De klasse beschikt over twee publieke methoden: getHTMLCloud(String zoekstring, int maxResultaten, int tags) en launchBrowser(URL). De eerste methode genereert de tag cloud aan de hand van de meegegeven zoekstring, het maximum aantal resultaten dat moet worden verwerkt, en het maximum aantal tags dat moet worden getoond in de tag cloud. Deze ziet er als volgt uit:

p u b l i c URL getHTMLCloud ( String str , i n t maxRes , i n t tags ) { URL url = n u l l ; try { ZoekInfo info = new ZoekInfo ( ) ; info . s e t M a x R e s u l t a te n ( maxRes ) ; CloudExt cloud = new CloudExt ( ) ; cloud . s e t M a x T a g s T o D i s p l a y ( tags ) ; info . setZoekstring ( str ) ; sc . parsePaginas ( info , cloud ) ; H T M L F o r m a t t e r E x t formatter = new H T M L F o r m a t t e r E x t ( ) ; String htmlStr = formatter . html ( cloud , MIN_FONT , MAX_FONT ) ; url = writeHTMLFile ( htmlStr , CLOUDBESTAND ) ; } c a t c h ( U n s u p p o r t e d E n c o d i n g E x c e p t i o n ex ) { ex . p ri nt St a ck Tr a ce ( ) ; Logger . getLogger ( InhoudsPaneel . c l a s s . getName ( ) ) . log ( Level . SEVERE , n u l l , ex ) ; } r e t u r n url ; }

Er wordt eerst een nieuw ZoekInfo en CloudExt object aangemaakt.

De twee eerste

parameterwaarden van getHTMLCloud worden vervolgens aan het ZoekInfo object doorgegeven. Hierdoor wordt de bijhorende URL voor de HTTP-request gegenereerd. Het maximum aantal tags wordt doorgegeven aan het CloudExt object. Vervolgens wordt de methode parsePaginas(ZoekInfo, CloudExt) van de SAXController opgeroepen.

Nadat deze methode is uitgevoerd, bevat het

CloudExt object alle nodige informatie om de tag cloud in HTML-vorm te genereren. Om deze taak uit te voeren, wordt beroep gedaan op een object van de klasse HTMLFormatterExt.


22

De html(CloudExt cloud, int minFont, int maxFont) methode genereert aan de hand van het meegegeven CloudExt object de HTML-uitvoer.

Er moet ook een minimum en maximum

lettergrootte worden opgegeven. Deze waarden worden opgeslagen in twee constanten (MIN FONT en MAX FONT) van de klasse HTMLBuilder. Als returnwaarde van de getHTMLCloud methode wordt echter niet deze HTML-string gebruikt.

De private methode writeHTMLFile(String

htmlString, String output) van HTMLBuilder zorgt ervoor dat de HTML-string wordt opgeslagen als een HTML-bestand. De returnwaarde van deze methode is de padnaam van het opgeslagen bestand, in URL-vorm. Deze waarde wordt ook door de getHTMLCloud methode teruggegeven als resultaat. Waarom dit nodig is, zal duidelijk worden in de beschrijving van de klasse InhoudsPaneel. Als laatste voorziet de klasse HTMLBuilder, zoals vermeld, ook de methode launchBrowser(URL url).

Deze opent de meegegeven URL in een nieuwe browser.

Hiervoor wordt de klasse

java.awt.Desktop gebruikt. Het venster kan dan op de volgende manier worden geopend:

Desktop . getDesktop ( ) . browse ( url )

InhoudsPaneel - Het visuele gedeelte van de applicatie wordt verzorgd door de klasse InhoudsPaneel. Deze bevat een zoekknop (JButton) en een paneel om de tag cloud terug te geven (JEditorPane). Verder zijn ook drie tekstvelden voorzien (JTextField ): één om de zoekopdracht in te voeren, één om het maximum aantal resultaten in te stellen, en één om het maximum aantal te tonen tags op te geven. Deze laatste twee zijn optioneel: indien het eerste niet wordt ingevuld, worden alle resultaten verwerkt in de tag cloud. Wanneer het tweede veld niet wordt ingevuld, wordt de maximumwaarde voor het aantal tags op 25 ingesteld. Om de mogelijke gebeurtenissen op te vangen, implementeert de klasse de ActionListener en HyperlinkListener interface.

De eerste luistert naar events waarbij op de zoekknop wordt

geduwd: indien dit event optreedt, wordt de getHTMLCloud(String, int, int) methode van de klasse HTMLBuilder opgeroepen.

Als parameters worden de drie (al dan niet) ingevulde

waarden meegegeven uit de tekstvelden. De uitvoer van deze methode, de URL-padnaam van het gegenereerde bestand, wordt daarna gebruikt om de tag cloud te tonen in het JEditorPane object. Hiervoor wordt de methode setPage(URL) van het paneel ingesteld. Het is daarom dat de gegenereerde tag cloud wordt opgeslagen als HTML-bestand. De tweede luisteraar handelt de HyperlinkEvents af. Deze events treden op wanneer op een tag in de tag cloud wordt geklikt. De luisteraar zorgt ervoor dat de bijhorende zoekresultaten in een browser worden weergegeven, door de launchBrowser(URL) methode van HTMLBuilder op te roepen.


1.3.3 1.3.3.1

23

Aanpassingen Threadpool

De opbouw van een tag cloud kan heel tijdsintensief zijn. Om deze uitvoeringstijd kleiner te maken, wordt de implementatie voorzien van threads. Om threads te implementeren, wordt het Thread Pool Pattern gebruikt (Burnett, 2007). Figuur 1.6 toont een schematische weergave van de threadpool werking.

Figuur 1.6: Werking van een threadpool (Burnett, 2007)

Een threadpool co¨ ordineert hierbij alle threads.

De pool kan een beperkt aantal threads

’tegelijkertijd’ laten lopen. Er zijn dan ook meestal meer uit te voeren taken dan beschikbare threads. Daarom bevat de pool een methode die een werkobject aan een wachtrij kan toevoegen. De threadpool hoeft niet te weten welke soort taken hij moet uitvoeren. Daarom implementeren de werkobjecten allemaal de Runnable interface. Zo moet de threadpool zich enkel bezighouden met het tijdstip van uitvoeren. De pool wijst aan elke taak uit de wachtrij een thread toe, totdat er geen vrije threads meer zijn. Deze taken moeten thread-safe zijn. De overige taken blijven in de wachtrij zitten. Zodra een thread zijn toegewezen taak heeft afgerond, wordt een nieuwe taak uit de wachtrij gehaald en uitgevoerd. Dit gaat door totdat alle taken uitgevoerd zijn. Ofwel kan het programma dan sluiten, ofwel kan het wachten totdat er nieuwe taken beschikbaar zijn. Dit Thread Pool Pattern kan worden gebruikt indien er veel taken zijn. Het toewijzen van een nieuwe thread aan elke taak kan namelijk veel overhead met zich meebrengen: threads moeten telkens worden gecreëerd en vernietigd. De threadpool zorgt hierbij voor een betere performantie en stabiliteit. De klassen die voorzien worden om de threadpool te implementeren, worden hieronder kort toegelicht. Deze zijn gebaseerd op een reeds bestaande implementatie (Heaton, 2003). ThreadPool - Het centrale gedeelte van het mechanisme, de threadpool, wordt ge¨ımplementeerd


24

door deze klasse. Aan de constructor wordt het maximum aantal threads opgegeven. Deze threads (type WorkerThread ) worden in een lijst (type Thread[] ) bijgehouden en na initialisatie opgestart. De klasse bevat ook een methode assign(Runnable) die een taak toevoegt aan de wachtrij (type ArrayList). De methode getAssignment() kijkt of er taken in de wachtrij zitten en haalt de eerstvolgende taak eruit (volgens het FIFO principe). Verder bevat de pool ook nog een referentie naar een Done object. Deze houdt het aantal actieve threads bij en zorgt ervoor dat het programma stopt als er geen werk meer is (na het oproepen van de methode complete()). WorkerThread - Dit is een afgeleide klasse van Thread, en implementeert bijgevolg de run() methode. Deze methode roept de getAssignment() methode van de ThreadPool klasse aan, die een taak teruggeeft. Deze taak wordt dan door de WorkerThread gestart, door de run methode van dit object op te roepen. Als de taak uitgevoerd is, wordt dit aan het Done object gemeld. Done - Wanneer er geen werk meer is, moet de pool hiervan op de hoogte worden gebracht. Daar zorgt een object van deze klasse voor. De methode waitDone() wacht totdat er geen actieve threads meer zijn, om dan het programma te sluiten. Verder bevat deze klasse de methoden workerBegin() en workerEnd(), die respectievelijk het aantal actieve threads verhogen en verlagen bij het opstarten en beëindigen van een taak. Om dit mechanisme te implementeren in de tag cloud applicatie, wordt de SAXController klasse aangepast. In de constructor wordt een nieuw ThreadPool object aangemaakt. Als parameter wordt hieraan het maximum aantal threads meegegeven die tegelijkertijd mogen worden uitgevoerd. Voor

de

aanmaak

van

de

XMLReader

wordt

een

nieuwe

methode

voorzien:

getXMLReader(ZoekInfo, CloudExt). Deze maakt op dezelfde manier, zoals in de oorspronkelijke implementatie, een nieuwe XMLReader aan. Aan de constructor van de SAXHandler worden meteen het ZoekInfo en CloudExt object meegegeven. Deze nieuwe methode wordt voorzien omdat voor elke thread een nieuwe XMLReader en SAXHandler moet worden aangemaakt. Verder wordt ook de parsePaginas methode aangepast. De eerste pagina wordt nog steeds op dezelfde manier verwerkt, maar voor elke volgende pagina wordt de methode assign(ParserThread) van het ThreadPool object opgeroepen. ParserThread is hierbij een nieuwe klasse, die de Runnable interface implementeert. Voor elke pagina wordt een nieuw object van deze klasse aangemaakt. Hierbij worden twee parameters meegegeven aan de constructor: een (nieuwe) XMLReader en de URL-string van de te parsen pagina. Wanneer een pagina kan worden afgehandeld, wordt de run() methode van het bijhorende ParserThread object aangeroepen. Deze roept op zijn beurt de parse methode van de XMLReader op. In codevorm ziet de aangepaste methode er als volgt uit:

p u b l i c v o i d parsePaginas ( ZoekInfo zoekInfo , CloudExt cloud ) { try { XMLReader reader = getXMLReader ( zoekInfo , cloud ) ; reader . parse ( zoekInfo . getZoekUri ( ) ) ;


25

i n t aantal = zoekInfo . g e t A a n t a l P a g i n as ( ) ; i n t res = zoekInfo . g e t A a n t a l R e s u l t a t e n ( ) ; i f ( zoekInfo . g e t M a x R e s u l t a t e n ( ) != −1 && res > zoekInfo . g e t M a x R e s u l t a t en ( ) ) { aantal = zoekInfo . g e t M a x R e s u l t a t en ( ) / zoekInfo . g e t A a n t a l P e r P a g i n a ( ) ; } i n t volgende = 0 ; f o r ( i n t i = 0 ; i < aantal ; i++) { volgende += zoekInfo . g e t A a n t a l P e r P a g i n a ( ) ; String pag = zoekInfo . getZoekUri ( ) + ”&pw=” + volgende ; reader = getXMLReader ( zoekInfo , cloud ) ; pool . assign ( new ParserThread ( reader , pag ) ) ; } pool . complete ( ) ; } c a t c h ( IOException ex ) { Logger . getLogger ( SAXController . c l a s s . getName ( ) ) . log ( Level . SEVERE , n u l l , ex ) ; } c a t c h ( SAXException ex ) { Logger . getLogger ( SAXController . c l a s s . getName ( ) ) . log ( Level . SEVERE , n u l l , ex ) ; } }

Als laatste wordt ook de CloudExt klasse aangepast. Wanneer er met threads wordt gewerkt, moet dit steeds met de nodige voorzichtigheid gebeuren. Het toevoegen van tags aan de cloud kan voor problemen zorgen wanneer die door verschillende threads tegelijkertijd wordt opgeroepen. De addTag(Tag) methode moet namelijk onderscheid maken tussen tags die reeds zijn toegevoegd, en tags die nog niet in de cloud aanwezig zijn. Daarom wordt deze methode in de CloudExt klasse overschreven: hierbij wordt ze voorzien van de aanduiding synchronized, zodat er telkens maar één thread tegelijkertijd een Tag object kan toevoegen.

1.4

Testresultaten

Tot slot werd de applicatie getest op een aantal willekeurige zoekopdrachten. In wat volgt worden twee voorbeelden besproken. Als eerste voorbeeld zijn in tabel 1.1 de resultaten van de zoekopdracht ’urbanus’ opgenomen. De kolom ’tag’ duidt de naam van de tags aan die in de tag cloud worden getoond. In de kolom ’#’ wordt per tag het aantal verfijnde zoekresultaten weergegeven die gevonden werden voor de zoekopdracht. Als laatste bevat de kolom ’%’ het procentuele aantal resultaten dat gevonden werd met de verfijnde zoekopdracht, ten opzichte van de resultaten van de originele zoekopdracht. De zoekstring ’urbanus’ leverde in totaal 343 resultaten op. In 93,88 procent van de gevallen komt de tag ’van anus urbanus’ bijvoorbeeld ook voor. Ook de tag ’antwerpen stad’ komt nog in 19,24 procent van de gevallen voor. Om te kijken hoeveel fragmenten van de originele resultset niet gevonden kunnen worden met de tag cloud, kan een HTTP-request naar de BOM-interface worden verstuurd.

Hiervoor

moet als zoekstring de originele zoekopdracht worden opgegeven, gevolgd door alle tags uit de tag cloud, voorafgegaan door een minteken.

Voor de zoekopdracht ’urbanus’ ziet deze

Hoofdstuk 1. Tag Cloud zoekstring er als volgt uit:

26 ’+urbanus -MediaObjectFragmentKeyword:’van anus urbanus”

-MediaObjectFragmentKeyword:’europese landen’ -MediaObjectFragmentKeyword:belgie . . . Deze zoekopdracht leverde zeven resultaten op. Dit betekent dat bij zeven resultaten van de zoekopdracht ’urbanus’, geen enkele waarde uit hun corresponderende MediaObjectFragmentKeyword veld, overeenkomt met een tag uit de tag cloud. Eén van deze resultaten heeft bijvoorbeeld enkel de volgende MediaObjectFragmentKeyword waarden: ’beeldverhaal’, ’gouden’, ’potlood’, ’prijs’, ’strips’. Al deze waarden komen, samen met de zoekstring ’urbanus’, slechts twee of drie keer voor. Tabel 1.1: Resultaten voor de zoekopdracht ’urbanus’ (aantal tags: 30)

tag

#

%

van anus urbanus

322

93,88

europese landen

321

belgie

tag

#

%

beloning

86

25,07

93,59

tekening

82

23,91

307

89,50

persconferentie

79

23,03

verklaring

226

65,89

kind

77

22,45

interview

224

65,31

strip

75

21,87

muziek

205

59,77

beeldende kunst

74

21,57

kunst

161

46,94

verjaardag

72

20,99

film

132

38,48

herdenking

72

20,99

concert

128

37,32

kleding

71

20,70

usa

99

28,86

belgische dynastie

70

20,41

televisieprogramma

97

29,28

brt

70

20,41

mode

96

27,99

frankrijk

70

20,41

modeshow

95

27,70

humor

67

19,53

gent

93

27,11

premiere(eerste voorstelling)

66

19,24

samenleving

86

25,07

antwerpen stad

66

19,24

Totaal aantal zoekresultaten: 343

Tabel 1.2 toont als tweede voorbeeld de resultaten van de zoekopdracht ’leterme’. Deze heeft twee extra kolommen: ’alles’ en ’500’. De zoekopdracht werd namelijk twee keer uitgevoerd: de eerste keer werden alle zoekresultaten opgenomen bij de verwerking, de tweede keer werd dit aantal beperkt tot de eerste 500 resultaten. De twee kolommen duiden aan of de corresponderende tag in allebei de gegenereerde tag clouds voorkomt, of slechts in één van beide. Uit de resultaten blijkt dat bij de tweede uitvoering veertien andere tags in de tag cloud werden opgenomen dan bij de eerste uitvoering. Elf tags komen in beide uitvoeringen voor. Een voordeel van de tweede uitvoering is zijn veel kleinere benodigde tijd: 8 seconden tegenover 307 seconden.

Dit grote tijdsverschil is te wijten aan de verschillende snelheden waarmee

HTML-responses kunnen worden verwerkt. Sommige responses nemen heel wat tijd in beslag: de verwerking ervan kan oplopen tot tien seconden. Andere worden dan weer afgehandeld in minder dan één seconde tijd.


27

Een nadeel is dan weer dat niet alle meest relevante tags worden opgenomen: tags zoals ’vlaams’, ’brussel’, ’splitsing’, . . . komen niet meer voor. In de plaats worden andere tags opgenomen, zoals ’verkiezing’, ’vlaams gewest’, ’muziek’, . . . Deze laatste komt echter maar in 3,46 procent van de gevallen samen voor met de zoekopdracht ’leterme’. Ook kan het zijn dat de lettergroottes in de tag cloud niet meer volledig in verhouding zijn met de aantallen uit de ’#’-kolom: sommige tags kunnen iets groter/kleiner worden afgebeeld dan andere, terwijl die een kleinere/grotere waarde hebben in de ’#’-kolom. Dit komt omdat de scores die aan de tags vasthangen, berekend zijn over slechts een gedeelte van alle resultaten. Tabel 1.2: Resultaten voor de zoekopdracht ’leterme’ (aantal tags: 25)

tag

#

%

alles

500

regering

750

39,31

X

X

parlement

617

32,34

X

verklaring

602

31,55

X

vlaamse

473

24,79

X

leterme yves

459

24,06

X

belgie

458

24,00

X

europese landen

452

23,69

X

vlaams

430

22,54

X

vlaanderen

396

20,75

X

minister

364

19,08

interview

353

debat splitsing

#

%

alles

versterking

227

11,90

X

X

tekst

227

11,90

X

X

rand

227

11,90

X

karakter

227

11,90

X

X

identiteit

227

11,90

X

X

cd&v

196

10,27

X

X

belgische politieke regeringen

195

10,22

X

verkiezing

125

6,55

X

X

samenleving

124

6,50

X

X

X

christendemocratie

120

6,29

X

18,50

X

X

bijeenkomst

108

5,66

X

313

16,40

X

overlegmodellen

103

5,40

X

293

15,36

X

vlaamse gemeenschap

97

5,08

X

politiek

273

14,31

X

vlaams gewest

96

5,03

X

bhv

255

13,36

X

regeringsvorming

91

4,77

X

studiogast

249

13,05

X

persconferentie

91

4,77

X

kamer

243

12,74

X

vlaamse regering

85

4,45

X

b-h-v

237

12,42

X

toespraak

84

4,40

X

brussel

235

12,32

X

muziek

66

3,46

X

maatregelen

230

12,05

X

X

X

tag

500

Totaal aantal zoekresultaten: 1.908

Om de tests uit te voeren, werd het aantal threads ingesteld op 25.

Ter vergelijking: de

uitvoeringstijd van de zoekopdracht ’leterme’, waarbij één thread werd gebruikt, duurde 521 seconden. Dit is 214 seconden trager dan wanneer 25 threads werden gebruikt.

28

Hoofdstuk 2

Ontologie 2.1

Semantisch Web

Hoe kunnen mensen hun weg vinden tussen de grote hoeveelheden informatie die door het World Wide Web aangereikt wordt? Gebruikers zien zoekrobots als een handig middel om de nodige gegevens te vinden. Het zoekproces is echter niet evident voor computers: ze moeten de zoekgegevens weten te interpreteren en verwerken. Dit laatste blijkt vooralsnog een struikelblok te zijn. Computers kunnen namelijk geen informatie verwerken zoals mensen dit doen. Daarom werd een nieuw begrip ingevoerd: het Semantisch Web. Deze uitbreiding van het World Wide Web kwam in 1991 tot stand en is nog volop in ontwikkeling. Hierbij staat de uitwisseling van gegevens, kennis en informatie centraal. Het heeft tot doel om de betekenis van informatie ook toegankelijk te maken voor computers. Hiervoor moeten ze echter gegevens op semantisch (betekenis) niveau begrijpen. Een ontologie kan zo’n begrijpelijke taal voor machines opstellen, zodat ook zij over de gegevens en de betekenis hiervan kunnen redeneren. Op die manier wordt intelligent zoeken mogelijk. Ontologieën gaan een alsmaar belangrijkere rol gaan spelen in het Semantisch Web. Bestaande kennis over een gemeenschappelijk domein kan hiermee worden ondergebracht in een datastructuur. Door middel van concepten, relaties en instanties te definiëren in de datastructuur, kunnen de gegevens van een bepaald domein worden beschreven (Céline Van Damme, 2008). Een ontologie die gaat over televisie zou bijvoorbeeld kunnen bestaan uit de concepten ’presentator’, ’tv-programma’, ’tv-zender’, met bijhorende relaties zoals ’presenteert’, ’behoort tot de categorie’, ’zendt uit’, enzovoort. Hieraan kunnen instanties zoals ’Martine Tanghe’, ’Het Journaal’ en ’VRT’ worden toegevoegd.

2.2

Technologie¨ en

Om een ontologie te definiëren, worden een aantal technologieën gebruikt. Ze hebben elk tot doel om de betekenis van informatie toegankelijk te maken voor de computer. In wat volgt worden drie

Hoofdstuk 2. Ontologie

29

technologieën kort toegelicht: RDF (2.2.1), RDFS (2.2.1.1) en OWL (2.2.2). Verder wordt ook de querytaal SPARQL besproken (2.2.3).

2.2.1

RDF

Een eerste gebruikte technologie is RDF (Herman et al., 2004). Dit is een standaard van het W3C1 , die gebaseerd is op XML. Het grote verschil is dat RDF ook betekenis kan hechten aan gegevens, in tegenstelling tot XML. Het is een taal die het mogelijk maakt om het datamodel te beschrijven aan de hand van objecten en hun relaties. Hierbij wordt gebruikgemaakt van zogenaamde RDF-triples: deze bestaan uit een subject, predicaat en object. Het subject is de entiteit of resource die beschreven wordt (het onderwerp). Het predicaat definieert een eigenschap van dit subject, en zegt tevens iets over het object (relatie). Dit laatste bevat de waarde van de eigenschap. Voorbeelden van triples zijn: • Nederland (subject) heeft als hoofdstad (predicaat) Amsterdam (object). • Jan (subject) maakt (predicaat) zijn huiswerk (object). Zowel het subject, predicaat als object worden ge¨ıdentificeerd door middel van een URI. Hiermee kan op een unieke wijze verwezen worden naar elk identificeerbaar object of concept: tekst, metadata-records, afbeeldingen, videofragmenten, . . . Via de URI kan alle beschikbare informatie over een entiteit worden opgezocht. Verschillende triples kunnen samen een gerichte graaf vormen, waarbij het subject van het ene statement (triple) het object van het andere statement kan zijn. Hoe meer triples bij een entiteit horen, hoe meer informatie erover beschikbaar is. Figuur 2.1 toont een voorbeeld. Hierin wordt ’Brussel’ bijvoorbeeld twee keer als object gebruikt en één keer als subject.

Figuur 2.1: RDF graaf met meerdere triples (Broekstra, 2007) 1

Een organisatie die standaarden voor het World Wide Web creëert


30

Er zijn verschillende elementen ter beschikking om triples te beschrijven. Hieronder volgt een klein voorbeeld van het gebruik van RDF (RDF Tutorial , 2004):

< r d f : D e s c r i p t i o n r d f : a b o u t=” h t t p : //www. r e c s h o p . f a k e / cd / Empire B u r l e s q u e ”> < c d : a r t i s t>Bob Dylan USA Columbia < c d : p r i c e>1 0 . 9 0 1985

Het RDF-document start met de XML-declaratie, gevolgd door het rootelement: . Deze specifieert verder de gebruikte namespaces, samen met hun prefix. Het element bevat de beschrijving van het subject, ge¨ıdentificeerd door het rdf:about attribuut. De kindelementen , , . . . beschrijven de eigenschappen van het subject. 2.2.1.1

RDF Schema

Tot nu toe kunnen er relaties worden beschreven tussen entiteiten aan de hand van triples. Hiermee ligt echter de betekenis van deze triples nog niet vast. Een computer kan immers onmogelijk weten dat ’Nederland’ een land is en dat hierin steden gelegen zijn. Die betekenis kan pas worden vastgelegd als de triple wordt gekoppeld aan een vocabulaire. Hiervoor is het RDF Schema, of kortweg RDFS, ontworpen (Brickley & Guha, 2004). Dit schema is gebaseerd op RDF en bevat een basisverzameling van klassen en relaties waarmee eigenschappen en klassen van RDF knopen kunnen worden uitgedrukt. Er kunnen onder andere ook beperkingen en verplichtingen worden opgelegd aan bepaalde eigenschappen of instanties van klassen. Ook het definiëren van subklassen behoort tot de mogelijkheden. Een RDF Schema legt de rol van termen in een triple vast, en kan bijgevolg worden aanzien als een taal om primitieve ontologieën mee te definiëren. Figuur 2.2 toont een voorbeeld van een RDF Schema.


31

Figuur 2.2: RDF Schema (Broekstra, 2007)

Een ander voorbeeld toont hoe de code van een RDF schema er kan uitzien:

” h t t p : //www. a n i m a l s . f a k e / a n i m a l s#”>

< r d f s : C l a s s r d f : I D=” Animal ” /> < r d f s : C l a s s r d f : I D=” Kangaroo ”> < l i v e s I n>Australia

Het element dat wordt gebruikt bij RDF, wordt hier vervangen door het element, waarbij de naam wordt aangegeven door een ID attribuut. De eigenschappen worden aangeduid met . Hierbij geeft het domain element aan op welke klasse(n) de property wordt toegepast. Het specifieert dus de subject-kant van een triple. Het range element daarentegen geeft aan dat waarden van een bepaalde eigenschap instanties zijn van een bepaalde klasse. Dit komt overeen met de object-kant. Verder kunnen er onder andere nog subklassen


32

(subClassOf ) en subproperty’s (subPropertyOf ) worden gedefinieerd. De laatste lijnen code uit het voorbeeld definiëren de beschrijving van een instantie.

2.2.2

OWL

Omdat RDF in de praktijk te beperkt bleek om ontologieën mee te kunnen definiëren, is OWL ontstaan. Het is een uitbreiding op RDFS en tevens een standaard van het W3C (McGuinness & van Harmelen, 2004). Extra expressiviteit wordt verkregen doordat OWL extra terminologie voorziet. Onderstaande voorbeelden tonen welke extra functionaliteiten aan de eigenschappen kunnen worden gegeven: • transitief: P(x,y) & P(y,z) => P(x,z) – ”Als een spaak een deel is van een wiel, en een wiel deel van een fiets, dan is de spaak ook deel van de fiets” • invers: P1(x,y) <=> P2(y,x) – ”Als Jan de vader is van Elke, dan is Elke een kind van Jan.” • symmetrisch: P(x,y) <=> P(y,x) – ”Jan is een collega van Peter, dus Peter een collega van Jan” • functioneel: P(x,y) & P(x,z) => y = z – ”De wijn is van het jaar 1978.”(De wijn kan maar met 1 wijnjaar worden geassocieerd.) Ook de kardinaliteit kan exact worden gespecifieerd. Door deze extra functionaliteiten kan er aan reasoning worden gedaan: er kunnen conclusies worden getrokken uit bestaande gegevens. Hierdoor kan naar informatie worden gezocht op een manier die bij traditionele zoekmachines en databases ongekend is (Broekstra, 2007). Hieronder volgt een voorbeeld van een gedeeltelijke OWL-beschrijving:

Here comes a description for the ontology < o w l : c a r d i n a l i t y r d f : d a t a t y p e=”&xsd ; n o n N e g a t i v e I n t e g e r ”>1


33

r d f : r e s o u r c e=”#WineYear ” />

r d f : r e s o u r c e=”&xsd ; p o s i t i v e I n t e g e r ” />

...

De code start ook hier met een XML-declaratie en het rootelement zoals in het RDF-voorbeeld. Daaronder wordt een ontologieheader opgenomen, met behulp van het element . Deze bevat informatie over de ontologie zelf. Om klassen op te nemen, wordt er nu gebruikgemaakt van in plaats van .

Verder bestaan er twee soorten eigenschappen:

ObjectProperties en DataTypeProperties. De eerste soort duidt een relatie aan tussen instanties van twee klassen, terwijl de tweede een relatie definieert tussen een instantie van een klasse en een XML Schema datatype. In de voorbeeldcode is hasWineYear een voorbeeld van een ObjectProperty, en yearValue een voorbeeld van een DataTypeProperty. Opdat de computer zou kunnen redeneren,

kunnen de property’s nog verder worden

gespecifieerd door er een extra type aan toe te voegen. worden gebruikt:

De volgende types kunnen

TransitiveProperty, SymmetricProperty, FunctionalProperty, inverseOf en

InverseFunctionalProperty. Daarnaast kunnen er ook restricties worden opgelegd met behulp van allValuesFrom, someValuesFrom, cardinality, hasValue, enzovoort. Meer voorbeelden en mogelijkheden zijn terug te vinden in het OWL-document (McGuinness & van Harmelen, 2004).

2.2.3

SPARQL

Om gegevens op te zoeken in ontologieën die met behulp van RDF en OWL zijn opgesteld, kan SPARQL worden gebruikt. Deze querytaal voorziet in een gelijkaardige syntax als SQL. Query’s worden hier echter toegepast op een kennisdatabase, en niet op een relationele database (zoals bij SQL het geval is). Hierbij is niet alleen de vraagstelling, maar ook de redenering van belang. De belangrijkste verschillen tussen deze twee soorten databases worden hieronder opgesomd (Lops, 2008): • Het schema van een kennisdatabase wordt gevormd door een semantisch netwerk. RDBMS-systeem gebruikt een relationeel model. • Een kennisdatabase is minder gestructureerd en bovendien kan er kennis ontbreken.

Een


34

• Het resultaat kan zowel gedefinieerde gegevens als afgeleide gegevens bevatten. • Query’s moeten worden aangepast aan de structuur en representatie (RDF, OWL, . . . ) van de ontologie. • Bij kennisdatabases is niet altijd op voorhand geweten wat er wel en niet opgeslagen gaat worden (oneindig domein). Met SPARQL wordt geprobeerd de verschillende querytalen voor kennisdatabases die op RDF gebaseerd zijn, te vervangen door één standaard. Meestal bestaat een SPARQL-query uit een set van triple patterns. Deze zien eruit zoals RDF-triples, met het verschil dat zowel het subject, object als predicaat variabel mogen zijn. Variabelen worden aangeduid door een vraagteken vóór de naam van de variabele te plaatsen. Onderstaand voorbeeld geeft een verduidelijking:

PREFIX

dc :

PREFIX

ns :

SELECT

? title ? price

WHERE

{ ? x ns : price ? price . FILTER ( ? price < 3 0 . 5 ) ? x dc : title ? title . }

Het PREFIX-keyword wordt gebruikt om te weten uit welke database de kennis moet worden gehaald. Hierbij kan een afkorting worden ge¨ıntroduceerd, die wordt gebruikt bij de specificatie van het predicaat. Het SELECT-keyword geeft net zoals bij SQL aan welke gegevens het resultaat moet bevatten. Tijdens de uitvoering van de query worden de variabelen gebonden aan RDF-triple componenten. Het WHERE-keyword legt het patroon vast waarnaar moet worden gezocht. Hierbij kunnen met behulp van een filter extra restricties worden opgelegd. In het voorbeeld wordt op zoek gegaan naar alle titels van boeken die minder dan 30.5 eenheden kosten. De variabele x staat hierbij voor om het even welk subject. Verdere informatie is terug te vinden in het W3C SPARQL-document (Prud’hommeaux & Seaborne, 2008).

2.3

Validatie

Opdat het ontologiebestand goed zou kunnen worden verwerkt door software, moet het voldoen aan een aantal regels. De syntax moet hierbij strikt worden gerespecteerd, net zoals bij een XML-bestand. Zo mag er maar één element zijn op het hoogste niveau en moeten alle elementen op de juiste moment worden geopend en gesloten. Indien het bestand alle syntaxregels respecteert, is het well-formed. Om te controleren of een ontologiebestand well-formed is, kan een online ontologievalidator worden gebruikt2 .

Indien het document gevalideerd is, worden alle triples

getoond in tabelvorm met hun corresponderende subjecten, predicaten en objecten. Deze triples 2

http://www.w3.org/RDF/Validator


35

kunnen ook worden weergegeven als een graaf. Naarmate de omvang van het document toeneemt, wordt dit echter al snel onoverzichtelijk. Een tweede manier om het document te testen op zijn welgevormdheid, is het gebruik van Protégé. Dit is een ontologie-editor met een grafische interface (The Protégé Ontology Editor and Knowledge Acquisition System, 2008). Hiermee kan een ontologiebestand worden ingeladen en meteen worden getest op zijn welgevormdheid. Met behulp van deze editor kunnen ook nieuwe ontologieën worden opgebouwd, waarbij de gewenste klassen, property’s en instanties kunnen worden toegevoegd. Verder kunnen SPARQL-query’s worden gedefinieerd en uitgevoerd. Deze tool maakt het bijgevolg mogelijk om op een grafische en meer overzichtelijke manier ontologieën op te bouwen.

2.4

CROEQS

De videofragmenten die de BOM-database bevat, zijn allen voorzien van annotaties (metadata). Dit zorgt voor een betere doorzoekbaarheid. Hierbij kan echter geen rekening worden gehouden met alle mogelijke scenario’s waarin een gebruiker naar een bepaald fragment zoekt. Er bestaat dus een kloof tussen de manier van annoteren en de manier waarop gebruikers items opzoeken. Daarom werd op INTEC het CROEQS project opgestart. CROEQS, Contemporaneous Role Ontology-based Expanded Query Search, is een geavanceerde zoekmachine gebaseerd op een rol-ontologie (Vandamme et al., 2009). Hierbij staat de scheiding van annotaties en domeinkennis over een bepaald onderwerp centraal. Het is de bedoeling dat gebruikers meer geavanceerde query’s op de database kunnen uitvoeren. Dit werd gerealiseerd door bovenop een traditionele, tekstuele zoekmachine een geavanceerd exemplaar te bouwen. Figuur 2.3 toont de opbouw.

Figuur 2.3: Overzicht van het CROEQS-systeem (Vandamme et al., 2009)

Om query’s te kunnen uitvoeren, is er een gebruikersinterface voorzien in de vorm van een webapplicatie (zie paragraaf 1.2).

Een gebruiker kan een HTTP-request sturen naar de


36

zoekmachine. Indien de query een semantische clausule bevat, wordt deze eerst vertaald naar een standaard query. Dit gebeurt met behulp van SPARQL, die op zijn beurt de gedefinieerde ontologie gebruikt. Het resultaat van de vertaling levert een disjunctieve (’of’) uitdrukking op. De vertaalde query wordt doorgestuurd naar de traditionele zoekmachine, die een resultset genereert. Deze indexeert de tekstuele metadata, en gebruikt hiervoor Lucene (Lucene, 2009). Nadien wordt een HTTP-response teruggestuurd naar de gebruiker: deze bevat het totaal aantal gevonden items, samen met de details van de eerste tien resultaten. Momenteel is er reeds een politieke rol-ontologie voorzien voor de BOM-database. Hierdoor is het mogelijk om semantische clausules uit te voeren zoals ’geef mij de politiekers die een specifieke functie uitvoeren/hebben uitgevoerd, gedurende een bepaald tijdsinterval, geassocieerd met een bepaalde organisatie (partij)’. Om dit te verwezenlijken, bevat de ontologie vijf hoofdklassen: ’Person’, ’Role’, ’Organization’, ’Time Interval’ en ’Role Fulfillment’.

Hieraan zijn instanties

gekoppeld. Ook de nodige eigenschappen en relaties zijn gedefinieerd.

2.5

Toepassingen

In wat volgt worden twee ontologieën beschreven die ook kunnen worden ge¨ıntegreerd in de zoekmachine. Als eerste wordt een geografische ontologie van België besproken, ten tweede een ontologie die handelt over het Belgische voetbal. Deze laatste bouwt verder op de rol-ontologie.

2.5.1

Ontologie van Belgi¨ e

Indien de gebruiker een videofragment wil opzoeken dat gerelateerd is aan een bepaald gebied van België, zou het handig zijn dat de resultset ook de fragmenten weergeeft van alle onderliggende deelgebieden. Stel bijvoorbeeld dat er gezocht wordt naar ongevallen in de provincie Oost-Vlaanderen. Hierbij verwacht de gebruiker dat alle gemeenten uit Oost-Vlaanderen, waar een ongeval gebeurd is, worden opgenomen in de resultset. Indien de klassieke zoekmachine wordt gebruikt, worden veel fragmenten die aan de zoekopdracht voldoen, toch niet in het resultaat opgenomen. Vaak zijn fragmenten namelijk wel geannoteerd met de gemeente, maar niet met bovenliggende gebieden, zoals de provincie, of het corresponderende gewest. Om aan de zoekmachine duidelijk te maken dat alle gemeenten uit Oost-Vlaanderen kanshebbers zijn om in het resultaat opgenomen te worden, kan een ontologie worden opgesteld. Aan de hand van deze ontologie kunnen met behulp van SPARQL geëxpandeerde query’s worden opgesteld. Deze kunnen dan worden doorgegeven aan de klassieke zoekmachine. De ontologie maakt het ook mogelijk dat er op meer dan één niveau wordt gezocht: wanneer een gebruiker bijvoorbeeld alle fragmenten wil zien die gaan over het Vlaams Gewest, dan zullen alle fragmenten uit alle onderliggende provincies, alsook uit alle onderliggende gemeenten, kandidaten zijn om opgenomen te worden in het resultaat.

Hoofdstuk 2. Ontologie 2.5.1.1

37

Implementatie

Het op te bouwen ontologiebestand moet alle gewesten, provincies, arrondissementen en gemeenten van België bevatten.

Hiervoor worden eerst handmatig een aantal klasse- en relatiedefinities

opgesteld. Deze definities zien er als volgt uit:

< r d f s : l a b e l>Gebied < r d f s : l a b e l>Land

Als eerste wordt een algemene klasse Gebied opgenomen. Met behulp van het element kan er een leesbare versie aan de bronnaam worden toegevoegd. De klasse Land wordt hiervan afgeleid, net als alle andere gebieden: gewest, provincie, arrondissement en gemeente. Aangezien sommige gemeenten zowel met hun Nederlandse als met hun Franse naam zijn opgenomen, wordt er ook een AnnotationProperty toegevoegd. Deze property’s worden gebruikt om beschrijvingen en annotaties vast te leggen (in dit geval een synoniem). Volgend voorbeeld illustreert het gebruik van deze property:

Synoniem voor het gebied ( Frans )

Als laatste zijn er ook ObjectProperties nodig om de topologische relaties te definiëren. Onderstaand voorbeeld illustreert het gebruik ervan:

r d f : r e s o u r c e=”#Gebied ” />


38

Het type TransitiveProperty duidt op transitiviteit, zoals beschreven in 2.2.2. Met deze regels kan de computer dus kennis opdoen: wanneer er een regel is die zegt ’Oost-Vlaanderen bevat arrondissement Dendermonde’ en een regel ’Vlaams Gewest bevat provincie Oost-Vlaanderen’, dan kan de computer beredeneren dat er impliciet ook een regel is die zegt ’Vlaams Gewest bevat arrondissement Dendermonde’. Omdat er meer dan één type voor het subject geldig is, wordt er gebruikgemaakt van het unionOf element: een provincie is zowel deelgebied van een land als van een gewest. Al deze klasse- en relatiedefinities zijn opgenomen in een bestand (belgie definities.txt): er is een klasse Gebied, Land, Gewest, Provincie, Arrondissement en Gemeente, samen met de bijhorende property’s bevat gemeente, bevat arrondissement, enzovoort. Een volledige beschrijving van de definities bevindt zich in bijlage A. Met behulp van deze definities kunnen de instanties worden beschreven. Deze worden opgesteld aan de hand van een lijst, beschikbaar op Wikipedia (Lijst van Belgische gemeenten naar bestuurlijke indeling, 2008). De lijst bevat per gewest de bijhorende provincies, arrondissementen en gemeenten. Om de gegevens op een gestructureerde manier te kunnen verwerken, wordt een directory aangemaakt. Deze directory bevat per gewest een subdirectory, die op zijn beurt voor elke provincie een tekstbestand bijhoudt. Elk tekstbestand bevat de bijhorende gemeenten, ingedeeld per arrondissement. Om al deze gegevens te verwerken in een ontologiebestand, wordt een Java programma geschreven. Voor elke soort deelgebied (land, gewest, provincie, arrondissement en gemeente) wordt een klasse opgesteld.

Elke klasse, behalve Gemeente, bevat een lijstattribuut dat de

onderliggende deelgebieden bijhoudt: de klasse Land houdt bijvoorbeeld een lijst bij van het type ArrayList, de klasse Gewest heeft een lijst van het type ArrayList, enzovoort. Zo kan er een soort boomstructuur worden aangemaakt. Hierdoor kan de invoer van de Wikipedia lijst gemakkelijk worden verwerkt en opgeslagen. De verwerking van deze invoer gebeurt door de klasse GebiedenGenerator. Deze singleton klasse bevat een methode getRoot(String input), die als waarde een Land object teruggeeft. Dit object fungeert dan als wortel van de boomstructuur, zodanig dat alle onderliggende deelgebieden kunnen worden overlopen. Als parameter moet de naam van de directory worden meegegeven, waarin alle bestanden zijn opgeslagen die de informatie over België bevatten. Al deze informatie wordt ingelezen en opgeslagen in de juiste objecten die de gegevens over de gebieden bijhouden. De getRoot methode wordt aangeroepen door een andere klasse die wordt voorzien: OWLGenerator. Deze klasse staat in voor de eigenlijke aanmaak van het OWL-bestand. Dit gebeurt op basis van


39

de manueel aangemaakte definities en de directory die de informatie over de gebieden bijhoudt. In de constructor wordt eerst de getRoot methode opgeroepen. Deze geeft, zoals vermeld, een Land object terug. Verder zorgt de methode genereerOWL() voor de opbouw van het OWL-bestand. Deze bouwt een string op, die het volledige ontologiebestand voorstelt: zowel de definities als instanties worden hierin verwerkt. Eerst wordt dan ook het bestand ingelezen dat alle opgestelde definities bevat. Hierna wordt een instantie van het juiste type aangemaakt, voor elk gebied uit de boomstructuur. Deze gebieden worden ook voorzien van een relatie per onderliggend gebied op het eerste niveau: de provincie Antwerpen heeft bijvoorbeeld drie relaties bevat arrondissement, want deze provincie telt drie arrondissementen. Hierbij worden de relaties bevat gemeente niet gedefinieerd, aangezien deze informatie al elders is opgeslagen (namelijk bij de corresponderende arrondissementen). Door al deze informatie is de ontologie volledig beschreven. De uitvoer wordt weggeschreven naar een bestand met als naam belgie.owl. Als voorbeeld wordt hieronder een stukje uitvoer van de instanties, met hun bijhorende relaties, getoond:

< r d f s : l a b e l>Luxemburg < r d f s : l a b e l>Aarlen < r d f s : l a b e l>Aarlen <synoniem>Arlon

SPARQL kan nu deze ontologie gebruiken om query’s te expanderen. Om enkele query’s te kunnen uittesten, wordt de ontologie in Protégé ingeladen. Om bijvoorbeeld alle arrondissementen uit de provincie Luxemburg te tonen, kan volgende query worden uitgevoerd:

PREFIX belg :

s e l e c t ? arro ndisseme nt where { ? x belg : b e v a t _ a r r o n d i s s e m e n t ? arro ndisseme nt .


40

? x rdfs : label ’ Luxemburg ’ . }

Een ander voorbeeld toont hoe alle gemeenten uit het arrondissement Aarlen kunnen worden opgevraagd:

PREFIX belg :

s e l e c t ? gemeente where { ? x belg : bevat _gemeen te ? gemeente . ? x rdfs : label ’ A a r l e n ’ . }

2.5.1.2

Opmerkingen

Een voorbeeld van een geografische ontologie is reeds voorhanden op internet (geoOntologies, 2003). Deze bevat klassen en relaties die in principe bruikbaar zijn voor de Belgische ontologie. Aangezien alles hierin vrij ingewikkeld beschreven is en er veel overbodigheden in voorkomen, werd afgestapt van het idee om de Belgische ontologie hierop te baseren, en werden er dus eigen klassen en relaties ingevoerd. De bedoeling is om in Protégé, met behulp van SPARQL, query’s te kunnen genereren die alle onderliggende deelgebieden ook weergeeft. De volgende query zou bijvoorbeeld kunnen worden uitgevoerd:

PREFIX belg :

s e l e c t ? gebied where { belg : Oost−Vlaanderen_P ? y ? gebied . ? y rdfs : subPropertyOf belg : bevat }

Deze heeft tot doel om alle arrondissementen én gemeenten uit de provincie Oost-Vlaanderen te tonen. Jammer genoeg geeft SPARQL in Protégé enkel de arrondissementen terug (dus enkel de deelgebieden van het eerste onderliggende niveau). Na wat opzoekwerk bleek dat dit inderdaad niet gaat in Protégé. Als alternatief zou Jena kunnen worden gebruikt: dit is een Java framework waarmee semantische webapplicaties kunnen worden gebouwd (Jena, 2000). Deze voorziet een API voor RDF en OWL, en beschikt over een SPARQL-zoekmachine. Met deze laatste kunnen wel query’s zoals in het bovenstaande voorbeeld worden uitgevoerd. Deze mogelijkheid werd echter nog niet uitgeprobeerd voor de Belgische ontologie.

2.5.2

Voetbalontologie

De rol-ontologie kan worden toegepast op verschillende domeinen, zo ook op het (Belgische) voetbal. Hiervoor kunnen perfect de vijf hoofdklassen worden gebruikt, die reeds werden gedefinieerd voor de politieke ontologie (zie 2.4). Ook onderstaande ObjectProperties werden hierin reeds voorzien en zijn ook van toepassing op de voetbalontologie:


41

Hiermee kunnen reeds de belangrijkste triples worden beschreven.

Tenslotte worden

AnnotationProperties voorzien om een tijdsinterval te kunnen specifiëren (begin- en einddatum), en om de voor- en achternaam van een persoon te kunnen aangeven. In tegenstelling tot de ontologie van België, zijn hier heel wat uitbreidingsmogelijkheden. Het eerste werk is dan ook op zoek gaan naar klassen en property’s die nuttige informatie opleveren. Figuur 2.4 toont een overzicht van alle opgenomen klassen, terwijl figuur 2.5 alle property’s weergeeft.

Figuur 2.5: Property’s voetbalontologie Figuur 2.4: Klassen voetbalontologie


42

Deze klassen en property’s worden vastgelegd met behulp van Protégé. Met behulp van deze editor kan ook automatisch het bijhorende OWL-bestand worden gegenereerd. De ObjectProperty homeTo, die een stadion toewijst aan een bepaalde club, is bijvoorbeeld als volgt gedefinieerd:

Hierbij duidt het type InverseFunctionalProperty aan dat een Stadium maar aan één FootballClub instantie kan worden toegewezen. Een ander voorbeeld toont het nut van het disjointWith statement:

The role of being coach of a given FootballClub

Dit statement duidt aan dat twee klassen geen gemeenschappelijke instanties kunnen hebben: een coach (Coach) is geen voetbalspeler (Player ), noch een scheidsrechter (Referee). Voor de aanmaak van de instanties wordt opnieuw een Java programma geschreven. De nodige informatie wordt terug eerst opgezocht en opgeslagen in tekstbestanden. Voetbalgegevens zijn gemakkelijk terug te vinden op Wikipedia en de Sporza-site (Sporza, 2008). De volgende methoden worden opgenomen in een (nieuwe) klasse OWLGenerator :

v o i d leesLandenIn ( String invoer ) ; v o i d l e e s S t a d i o n s E n C l u b s I n ( String invoer ) ; v o i d l e e s C o m p e t i t i e s I n ( String invoer ) ; v o i d l e e s B o n d s C o a c h e s I n ( String invoer ) ; v o i d lees Trainers In ( String invoer ) ; v o i d leesSpelersIn ( String invoer ) ; v o i d genereerOWL ( String uitvoer ) ;

De lees methoden zorgen ervoor dat alle informatie, die wordt gevonden over het Belgische voetbal, kan worden ingelezen.

Zo kan onder andere informatie over FIFA-landen, stadions en clubs,

competities, bondscoaches, trainers en voetbalspelers worden verwerkt. Voor alle gedefineerde


43

OWL-klassen wordt ook een gelijknamige Java klasse aangemaakt. Met behulp van de ingelezen informatie en deze klassen wordt het OWL-bestand voetbal.owl opgesteld. Hiervoor zorgt terug de methode genereerOWL. Ook aan de hand van deze ontologie kunnen SPARQL-query’s worden uitgevoerd. Om bijvoorbeeld alle voetballers te tonen, die bij de Belgische voetbalclub KAA-Gent spelen en de Belgische nationaliteit hebben, kan volgende query worden uitgevoerd:

PREFIX fb : SELECT d i s t i n c t ? person WHERE { ? person fb : fulfills ? x . ? x fb : r o l e fb : KAAGentPlayer . ? person fb : hasN ationali ty fb : Belgi¨ e}

Een tweede voorbeeld toont aan hoe alle voetballers kunnen worden opgezocht, die in seizoen 2007 gestopt zijn bij om het even welke ploeg:

PREFIX fb : SELECT d i s t i n c t ? person WHERE { ? person fb : fulfills ? x . ? x fb : during ? y . ? y fb : end_season ? jaar FILTER ( ? jaar = 2 0 0 7 ) }

44

Hoofdstuk 3

Tag relaties 3.1

Tags

Het begrip ’tagging’ is sinds de opkomst van online services zoals Flickr, del.icio.us, last.fm, . . . niet meer weg te denken. Deze services bieden de mogelijkheid om persoonlijke bestanden te sharen. Hierbij markeren gebruikers hun persoonlijke bestanden met zelfgekozen sleutelwoorden (tags). Deze tags zijn meestal goed bruikbaar en sluiten vaak beter aan op het taalgebruik van het publiek dan de termen die bibliotheken gebruiken in hun catalogi. Door multimediale bestanden te annoteren met tags, kan er op een toegankelijkere manier worden gezocht naar de gewenste bestanden. Er is echter een keerzijde verbonden aan het taggen: aangezien er nauwelijks of geen restricties opgelegd zijn aan de keuze van de sleutelwoorden, is het vaak moeilijk om te zoeken naar bestanden die met dergelijke vage begrippen getagd zijn. Verschillende gebruikers kunnen namelijk andere sleutelwoorden gebruiken om gelijkaardige bestanden te taggen. Ook spellingsfouten, synoniemen en het gebruik van verschillende talen kunnen het zoekproces bemoeilijken. Het eerste deel van dit hoofdstuk gaat dan ook verder in op de uitwerking van de strategieën die kunnen worden gebruikt om gebruikers geschikte tags te helpen plaatsen en naar de gewenste bestanden helpen te zoeken. Het tweede deel behandelt de uiteindelijke toepassing: semantische relaties leggen tussen keywords (tags) die in de BOM-database voorkomen, om zo verfijnde zoekresultaten te bekomen.

3.2

Flickr API

Het systeem dat de strategieën uitwerkt en onderzoekt, maakt gebruik van Flickr data. Flickr is een website voor het delen van foto’s, die zoals reeds gezegd ook gebruikmaakt van tagging. Om het taggedrag van gebruikers te bestuderen, wordt de Flickr API gebruikt (Flickr , 2009). Deze API beschikt over een lange lijst van methoden, die door iedereen kan worden gebruikt. Op deze manier kunnen gebruikers hun eigen applicaties ontwikkelen om Flickr data (foto’s, video’s, tags,

Hoofdstuk 3. Tag relaties

45

profielen, groepen) weer te geven. Om de methoden te kunnen gebruiken, is er een API-key vereist. Dergelijke sleutels kunnen aangevraagd worden via de Flickr website. Hierdoor kan de Flickr service het gebruik van de API opvolgen. Er zijn wrappers in verschillende programmeertalen beschikbaar om de methoden aan te roepen. In dit geval wordt de Java versie gebruikt: flickrj (Flickrj , 2008). De Java implementatie maakt gebruik van het REST-protocol. Verzoeken naar de server worden in tegenstelling tot bij SOAP niet verstuurd in XML, maar in URL-vorm. Het antwoord van de server daarentegen wordt wel in XML verkregen. In feite is een request dan ook niets anders dan een GET of POST actie. Om bijvoorbeeld de flickr.test.echo service aan te roepen, kan volgende URL worden gebruikt:

http: // api . flickr . com / services / rest /? method=flickr . test . echo&name=value }

Een voorbeeldantwoord wordt hieronder weergegeven:

<method>flickr . test . echo rest bar 5 f a b f 7 8 1 1 6 3 c 1 4 d 5 4 8 f 6 e 0 2 0 9 a f 7 5 9 6 f

De requests en responses moeten in de applicatie niet expliciet op deze manier worden uitgevoerd: deze worden door de methoden van de API afgehandeld. De klasse Flickr staat centraal bij het gebruik van flickrj. Deze klasse voorziet toegang tot de verschillende interfaces, die op hun beurt de Flickr API inkapselen (wrappen). Aan de constructor worden als parameters de API-key en secret meegegeven.

Als laatste parameter wordt het

transportprotocol opgegeven, namelijk REST. Voor SOAP bestaat er immers nog geen volledige implementatie.

3.3

Tag Recommendation System

Om gebruikers te proberen helpen in hun zoekopdracht naar bepaalde bestanden - in dit geval foto’s - kan het Tag recommendation system worden gebruikt (Sigurbjörnsson & van Zwol, 2008): er wordt vertrokken van een foto, waaraan de eigenaar een aantal tags heeft toegevoegd. Voor elk van die tags worden m kandidaattags gezocht, gebaseerd op tag co-occurrence. Deze tags dienen als invoer voor een aggregatie- en rankingfunctie, die de uiteindelijke recommended tags opleveren. Deze kunnen aan de gebruiker worden getoond als suggestie: indien ze deze tags gebruiken in


46

combinatie met hun eigen zoektags uit de query, of als alternatief, kan de zoekopdracht mogelijks worden verfijnd en verbeterd. Figuur 3.1 toont een overzicht van het proces, toegepast op een voorbeeldfoto.

Figuur 3.1: Voorbeeld van het Tag Recommendation Systeem (Sigurbjörnsson & van Zwol, 2008)

In wat volgt zal het zelfgeschreven Java programma, dat het bovenstaande systeem uittest en evalueert, nader worden toegelicht. Het vertrekt van de input van de gebruiker: dit is een foto id of een lijst van tags. Aan de hand daarvan worden recommended tags gegenereerd, op basis van twee strategieën. Het Java programma zal daarna als basis dienen voor het tweede deel, namelijk de BOM-toepassing. Alle formules en coëfficiënten die in de volgende subparagrafen (3.3.1 tot en met 3.3.3) worden gebruikt, komen ook terug in het paper dat het Tag recommendation system beschrijft (Sigurbj¨ ornsson & van Zwol, 2008).

3.3.1

Tag co-occurrence

Om een lijst met m kandidaattags te bekomen voor elke gebruikerstag is er een zogenaamde co-occurrence waarde nodig. Deze waarde stelt het aantal foto’s voor waarin twee opgegeven tags samen voorkomen. De m grootste co-occurrences per gebruikerstag worden bijgehouden. Tussen welke tags worden deze scores nu berekend? Het is duidelijk dat de eerste tag steeds een gebruikerstag is. De tweede tag moet gerelateerd zijn aan de eerste tag: er moet een verband bestaan tussen de twee. Om relevante tags te bepalen, wordt de methode getRelated(Tag) van de klasse TagsInterface uit de flickrj API opgeroepen voor elke gebruikerstag. Deze geeft een lijst van gerelateerde tags terug. De methode is volgens de API gebaseerd op clustered usage analysis. Hoe dit juist gebeurt, wordt door de API niet verder gespecifieerd. Ook het aantal teruggegeven tags ligt niet vast. Voor elk gevormd tagpaar worden via de PhotosInterface alle foto’s opgezocht die beide tags bevatten.


47

Deze zoekinstellingen kunnen via de parameters worden doorgegeven. Het resultaat geeft een PhotoList terug, waarvan enkel de grootte van de lijst wordt bijgehouden. Deze grootte is gelijk aan de gezochte co-occurrence waarde. Elk paar wordt als object van de zelfgeschreven klasse Pair opgeslagen: deze bevat referenties naar beide tags, samen met de co-occurrence waarde. Alle Pair instanties worden ook nog eens bewaard in een lijst om verdere berekeningen op uit te voeren. De co-occurrence waarde zoals die nu opgeslagen is, is echter nog niet erg betekenisvol. Ze houdt immers geen rekening met de individuele frequenties van de twee tags. Daarom worden deze waarden genormaliseerd aan de hand van twee benaderingen: de symmetrische en asymmetrische.

De symmetrische meting maakt gebruik van de Jaccard coëfficiënt, die als volgt wordt berekend: J(ti , tj ) :=

|ti ∩ tj | |ti ∪ tj |

Deze waarde is gelijk aan de verhouding van de doorsnede van de twee tags (ti en tj ) tot de unie ervan. De doorsnede stelt de originele co-occurrence waarde voor, terwijl de unie de sommatie is van de (afzonderlijke) frequenties van ti en tj . Deze waarden worden terug via de PhotosInterface bekomen en opgeslagen in het bijhorende Pair object. In feite wordt deze formule gebruikt om de gelijkheid van twee tags te bepalen: indien twee tags een hoge Jaccard coëfficiënt hebben, dan komen ze meestal ook samen voor in de dataset. Deze meting is dus vooral nuttig om equivalente tags en synoniemen te vinden. Indien er meer diversiteit gewenst is, biedt de asymmetrische benadering een betere oplossing.

De asymmetrische coëfficiënt is gedefinieerd als volgt: P (tj |ti ) :=

|ti ∩ tj | |ti |

De asymmetrische coëfficiënt houdt, in tegenstelling tot de Jaccard coëfficiënt, enkel rekening met de frequentie van ti , en niet met de unie ti ∪ tj . Deze coëfficiënt kan worden ge¨ınterpreteerd als de waarschijnlijkheid dat een foto geannoteerd is met tag tj , indien geweten is dat hij ook tag ti bevat. Om tag suggesties aan de gebruikers te kunnen doen, wordt best gebruikgemaakt van de laatste benadering: deze geeft eerder relevante tags dan equivalente tags terug. In het Java programma worden beide metingen uitgevoerd, zodat indien nodig de resultaten kunnen worden vergeleken. Voor elke Pair instantie worden de berekeningen uitgevoerd en opgeslagen in ditzelfde object. Alle paren kunnen nu per gebruikerstag in dalende volgorde worden gesorteerd op één van de drie bekomen waarden: co-occurrence zonder normalisatie, symmetrische of asymmetrische benadering. Dit wordt verwezenlijkt door de zelfgeschreven PairComparator klasse, die de Comparator interface implementeert. Voor elke gebruikerstag worden de m paren met de grootste co-occurrence waarde bijgehouden. Bij deze zijn dus ook de kandidaattags gekend. Het resultaat word weergegeven in


48

de vorm van een Vector>: voor elke gebruikerstag wordt een lijst van paren bijgehouden, die de kandidaattags bevatten.

3.3.2

Tag aggregatie

Tot nu toe zijn er aparte lijsten voor elke gebruikerstag, elk gerangschikt volgens dalende co-occurrence waarde. Als er meerdere gebruikerstags zijn opgegeven, moeten de verschillende lijsten worden samengevoegd om één ranking te verkrijgen.

Hiervoor bestaan twee

aggregatiemethoden, namelijk de Vote en Sum strategie. Deze scores leveren een lijst R op met aanbevolen tags, gesorteerd volgens dalende waarde. De Vote methode gebruikt volgende formule om de score te berekenen voor een kandidaattag:  1 if c ∈ Cu vote(u, c) = 0 otherwise score(c) :=

X

vote(u, c)

u∈U

Een gebruikerstag u ’stemt’ (vote) als het ware voor een kandidaattag c als c voorkomt in Cu . Dit laatste symbool staat voor de gerangschikte lijst met de m overgebleven kandidaattags, voor een gegeven gebruikerstag u. Het totaal aantal stemmen dat de tag c gekregen heeft, vormt dan de score. De Sum methode houdt ook rekening met de co-occurrence waarden en berekent de scores als volgt: score(c) :=

X

(P (c|u), if c ∈ Cu )

u∈U

In plaats van alle kandidaattags een gelijke stem te geven, wordt er een gewogen stem gegeven op basis van de (hier) asymmetrische co-occurrence waarden.

3.3.3

Promotie

Om een nog beter resultaat te bekomen, wordt gebruikgemaakt van een promoveerfunctie. Deze functie brengt drie waarden in rekening: • Stability-promotion: gebruikerstags die weinig voorkomen, zijn vaak minder betrouwbaar. Tags met een hoge frequentie worden dan ook meer in rekening genomen. • Descriptiveness-promotion: tags die veel voorkomen zijn vaak te algemeen (zoals bijvoorbeeld een jaartal). Voor dergelijke tags wordt er een demping voorzien. • Rank-promotion: de co-occurrence waarden kunnen snel dalen. Daarom wordt voor het berekenen van de relevantie de ranking van een kandidaattag in rekening genomen.


49

De bijhorende promoveerfuncties zijn terug te vinden in de literatuur (Sigurbjörnsson & van Zwol, 2008). Deze bevatten parameters (m,kr,ks,kd) die getraind moeten worden. Het Java programma gebruikt de waarden die worden voorgesteld in het paper. De vermenigvuldiging van de drie functiewaarden levert de promotiescore promotion(u, c) op. Deze waarde wordt op zijn beurt vermenigvuldigd met de Vote of Sum score. Het resultaat hiervan vormt de uiteindelijke score voor een kandidaattag c. De methode aggregate(Vector> taglists, boolean sum, boolean promotion) berekent op basis van de lijsten deze scores. Hierbij kan worden opgegeven of de Sum of Vote strategie moet worden gebruikt, en of de promotiefunctie moet worden toegepast. Het resultaat is van het type HashMap<String,Double>, dat voor elke aanbevolen tag de score bevat. Nadien worden de scores naar een bestand weggeschreven.

3.3.4 3.3.4.1

Aanpassingen Gegevensopslag

Er gebeuren een heleboel aanvragen naar Flickr over het netwerk om alle foto’s en tags op te halen. Dit vormt een bottleneck en vertraagt het Java programma. Er werd getracht om dit probleem op te lossen met een databank: alle tags die reeds zijn opgevraagd, kunnen worden opgeslagen in een databank, samen met hun informatie zoals de frequenties en co-occurrence waarden. Wanneer een gebruiker een tweede keer dezelfde gebruikerstag ingeeft, kan alle informatie om de relevante tags te bepalen, uit de databank worden gehaald. Zo hoeven er geen onnodige aanvragen te worden verstuurd en kunnen de gegevens op een snellere manier worden opgevraagd. Maar ook deze implementatie heeft één groot probleem: de veranderlijkheid van Flickr data. De opgestelde databank bevat namelijk al snel informatie, die niet meer up-to-date is. Omdat foto’s in een sneltempo (gemiddeld 3.000 per minuut) worden toegevoegd aan Flickr, kunnen de frequenties en co-occurrence waarden uit de databank al snel foutieve informatie opleveren. 3.3.4.2

Related tags

In het voorgaande werd gebruikgemaakt van de Flickr methode getRelated(Tag) om relevante tags te vinden. Omdat echter niet geweten is hoe deze functie precies in zijn werk gaat, werd nog een alternatieve methode voorzien. Hierbij wordt voor elke gebruikerstag een vast aantal foto’s (hier 500) opgevraagd die deze tag bevatten. Deze foto’s worden één voor één doorlopen, en alle tags die bij de foto’s horen, worden opgeslagen in een lijst. Deze tags vervangen dan de tags van de getRelated(Tag) methode. XML RPC-request Het opvragen van de foto’s met behulp van de flickrj API gebeurt snel. De tags die bij een foto horen, moeten echter worden opgevraagd met een aparte methode. Het ophalen van deze tags duurt


50

gemiddeld één seconde per foto. De bepaling van de relevante tags met de alternatieve methode is dus zeer tijdrovend. Daarom werd getest of de tags die bij een foto horen, niet sneller kunnen worden opgehaald met behulp van een XML RPC-request, in plaats van met de flickrj API (die gebruikmaakt van het REST-protocol). De response wordt hierbij meteen verkregen, met alle gegevens over de foto, inclusief de tags. Het antwoord moet echter nog worden geparset, aangezien de gegevens van een XML RPC-response in XML-vorm staan. Om de tags uit het antwoord te parsen, is gemiddeld ook één seconde per foto nodig. Deze manier van tags ophalen bleek dus niet sneller te zijn.

3.3.5

Resultaten

Het ge¨ımplementeerde Tag Recommendation System, werd getest op een aantal zelfgekozen gebruikerstags.

Voor de relevante tags werd zowel beroep gedaan op de Flickr methode

getRelated(Tag), als op de alternatieve methode die een set van 500 foto’s gebruikt, zoals beschreven in paragraaf 3.3.4.2. Tabel 3.1 geeft een overzicht weer van de gekozen gebruikerstags voor elke test. Tabel 3.1: Testgegevens voor het Tag Recommendation System

nr

gebruikerstags

#foto’s

#kandidaattags getRelated(Tag)

1

jaguar

2

jaguar;tiger;cat

3

kikker

4 5

duurtijd (sec)

500 foto’s

getRelated(Tag)

500 foto’s

73.376

68

734

64

916

117

67;61;40

164;156;204

73

1.553

1.940

54

1.209

55

1.302

pinquin

44

/

131

/

124

pinguin

6.802

44

1.017

35

1.144

Voor elke test (kolom ’nr’) worden de gebruikerstags weergegeven die als invoer dienden. De kolom ’#foto’s’ geeft aan hoeveel foto’s in Flickr getagd zijn met de gegeven gebruikerstags. Indien er meerdere gebruikerstags zijn, wordt het aantal foto’s gegeven waarin alle gespecifieerde gebruikerstags samen voorkomen. De kolom ’#kandidaattags’ geeft aan hoeveel kandidaattags werden gevonden voor elke gebruikerstag, voor beide methodes. Hierbij geeft de alternatieve methode steeds veel meer kandidaattags terug. De laatste kolom, ’duurtijd’, geeft aan hoeveel seconden het duurde om tot de resultaten te komen. De berekening met behulp van de alternatieve methode duurde altijd veel langer, omdat er steeds meer kandidaattags werden onderzocht. Alle methoden werden uitgevoerd volgens de asymmetrische benadering. Enkel voor de laatste test (’pinguin’), werden ook de resultaten van de symmetrische benadering opgenomen. In alle tabellen die volgen (3.2 tot en met 3.6), wordt de top vijf van de meest relevante tags getoond, samen met hun score. Deze waarden zijn telkens berekend volgens de twee strategieën: de Sum en Vote strategie, al dan niet met promoveerfuncties (aangeduid met een ’+’ in de tabellen).


51

Tabel 3.2 toont de resultaten voor de gebruikerstag ’jaguar’ met de getRelated(Tag) methode, en met de alternatieve methode. Deze tag is een homoniem, omdat ’jaguar’ zowel een automerk, als een katachtige kan zijn. De resultaten van beide methoden en van elke strategie tonen echter aan dat de tag vooral gerelateerd is aan auto’s: tags zoals ’car’ en ’ferrari’ komen in elk resultaat voor. Enkel de tag ’zoo’, die voorkomt in de Vote strategie, wijst erop dat Flickr ook foto’s bevat waarbij ’jaguar’ voorkomt in de zin van ’katachtige’. Deze strategie is zonder de promoveerfunctie niet zo zinvol bij tests waar slechts één gebruikerstag als invoer is gegeven. De score geeft namelijk enkel aan bij hoeveel van de gebruikerstags de kandidaattag is teruggevonden. Wanneer er slechts één gebruikerstag is, geeft de Vote strategie dan ook steeds de waarde één terug. Hierbij zijn alle kandidaattags dus evenwaardig, en kan de top vijf evengoed uit andere tags bestaan, die niet vermeld zijn in de resultaten. De Sum scores zijn in dit geval dan ook het meest zinvol: deze geven de kans aan dat een foto de kandidaattag bevat, indien ook geweten is dat hij geannoteerd is met de gebruikerstag(s). Wanneer er slechts één gebruikerstag is opgegeven, is dit in principe niets anders dan de berekening van de (a)symmetrische coëfficiënt. In dit geval is bij beide methodes de grootste kans weggelegd voor de tag ’car’: de kans is respectievelijk 24 en 27 procent groot. Er kan worden gesteld dat beide methodes in dit geval gelijkaardige resultaten opleveren. Tabel 3.2: Resultaten voor de tag ’jaguar’

Strategie (asymmetrisch - getRelated(Tag)) sum

sum+

vote

vote+

rang

tag

score

tag

score

tag

score

tag

score

1

car

0,2406

car

0,0178

car

1,0000

car

0,6095

2

porsche

0,1731

porsche

0,0112

zoo

1,0000

porsche

0,5703

3

ferrari

0,1705

ferrari

0,0089

automobile

1,0000

ferrari

0,4761

4

cars

0,1443

cars

0,0055

cars

1,0000

cars

0,3597

5

auto

0,0945

auto

0,0033

ferrari

1,0000

auto

0,3322

Strategie (asymmetrisch - 500 foto’s) sum rang

tag

sum+ score

tag

score

vote tag

vote+ score

tag

score 0,6209

1

car

0,2668

car

0,0201

car

1,0000

car

2

porsche

0,1949

porsche

0,0128

cars

1,0000

porsche

0,5780

3

ferrari

0,1912

ferrari

0,0102

ferrari

1,0000

ferrari

0,4867

4

cars

0,1627

cars

0,0063

porsche

1,0000

cars

0,3662

5

ford

0,1409

ford

0,0052

auto

1,0000

ford

0,3534

Wanneer echter als gebruikerstags naast ’jaguar’ ook ’tiger’ en ’cat’ worden opgegeven, levert dit wel tags op die meer aanleunen bij jaguar als ’katachtige’. De resultaten van deze zoekopdracht wordt weergegeven in tabel 3.3. Toch komen opnieuw tags voor zoals ’car’ en ’porsche’. Nu geeft de Vote strategie echter wél interessante resultaten terug: bij de alternatieve methode hebben zowel ’cats’ als ’animal’ als score de waarde twee. Bij de getRelated(Tag) methode wordt hieraan zelfs nog eentje toegevoegd: daar heeft ook ’zoo’ de waarde twee. Dit wijst erop dat de tag bij twee van


52

de drie gebruikerstags als kandidaattag geselecteerd is. Beide methodes leveren terug gelijkaardige resultaten op. Tabel 3.3: Resultaten voor de tags ’jaguar’, ’tiger’ en ’cat’

Strategie (asymmetrisch - getRelated(Tag)) sum rang

tag

1

zoo

2

car

3

porsche

4 5

sum+ score

vote

tag

score

tag

0,3253

car

0,0201

cats

0,2669

zoo

0,0181

zoo

0,1948

porsche

0,0128

animal

ferrari

0,1913

ferrari

0,0102

cats

0,1813

kitten

0,0092

vote+ score

tag

score

2,0000

zoo

0,7823

2,0000

animals

0,6850

2,0000

car

0,6209

car

1,0000

animal

0,6206

automobile

1,0000

cats

0,6130

Strategie (asymmetrisch - 500 foto’s) sum

sum+

vote

vote+

rang

tag

score

tag

score

tag

score

tag

score

1

car

0,2668

car

0,0201

cats

2,0000

zoo

0,7221

2

zoo

0,2386

zoo

0,0175

animal

2,0000

car

0,6209

3

porsche

0,1949

porsche

0,0128

car

1,0000

animal

0,6206

4

ferrari

0,1912

ferrari

0,0102

ferrari

1,0000

cats

0,6130

5

cats

0,1814

kitten

0,0092

wildlife

1,0000

porsche

0,5780

Om na te gaan of het Tag Recommendation System ook werkt voor Nederlandstalige woorden, werd als derde test de gebruikerstag ’kikker’ ingevoerd. De resultaten hiervan zijn terug te vinden in tabel 3.4. Het valt op dat de twee methodes bij elke strategie dezelfde tags hebben in hun top vijf. Enkel de scores verschillen licht. Er worden vooral Engelstalige woorden teruggegeven (’frog’, ’animal’, ’nature’, . . . ). De tag ’frog’ levert hier een vrij hoge Sum score op: 0,6860. Als vierde test werd de gebruikerstag ’pinquin’ ingegeven. Hierdoor werd gekeken wat de resultaten van een fout gespeld woord zijn: de juiste spelling van ’pinquin’ is namelijk ’pinguin’. (Om perfect te zijn, is het pingu¨ın, maar door het woord te normaliseren worden ook trema’s weggelaten). De resultaten ervan bevinden zich in tabel 3.5. Hier is er slechts één tabel, omdat de methode getRelated(Tag) geen enkele kandidaattag opleverde. De alternatieve methode daarentegen, leverde wél tags op. Uit de resultaten is op te maken dat de meeste foto’s getrokken zullen zijn op dezelfde plaats, en dus hoogstwaarschijnlijk door éénzelfde persoon: tags zoals ’zoo’, ’blijdorp’, ’rotterdam’ wijzen erop dat de foto’s genomen zijn in de Rotterdamse dierentuin. De resultaten van fout gespelde woorden zijn dan ook minder betrouwbaar dan die van juist gespelde tags (ook omdat er maar 44 foto’s deze tag bevatten), maar geven toch nog een aantal relevante tags terug. Sommige fout gespelde woorden zullen echter ook met de alternatieve methode geen (of minder goede) resultaten opleveren. De laatste test werd uitgevoerd op de juist gespelde (genormaliseerde) gebruikerstag ’pinguin’. De resultaten bevinden zich in tabel 3.6. Bij deze test zijn ook de resultaten van de symmetrische


53 Tabel 3.4: Resultaten voor de tag ’kikker’

Strategie (asymmetrisch - getRelated(Tag)) sum

sum+

vote

vote+

rang

tag

score

tag

score

tag

score

tag

score

1

frog

0,6859

frog

0,0913

pad

1,0000

frog

0,7865

2

nature

0,1025

nature

0,0079

nederland

1,0000

natuur

0,5578

3

natuur

0,0861

natuur

0,0062

nature

1,0000

nature

0,4855

4

nederland

0,0779

animal

0,0044

frog

1,0000

animal

0,3808

5

animal

0,0779

nederland

0,0042

green

1,0000

nederland

0,3690


sum+

vote

vote+

rang

tag

score

tag

score

tag

score

tag

score

1

frog

0,6860

frog

0,0913

pad

1,0000

frog

0,7866

2

nature

0,1025

nature

0,0079

nederland

1,0000

natuur

0,5579

3

natuur

0,0860

natuur

0,0062

nature

1,0000

nature

0,4856

4

animal

0,0778

animal

0,0044

frog

1,0000

animal

0,3809

5

nederland

0,0773

nederland

0,0041

green

1,0000

nederland

0,3690

Tabel 3.5: Resultaten voor de tag ’pinquin’


sum+

vote

vote+

rang

tag

score

tag

score

tag

score

tag

score

1

zoo

0,3056

zoo

0,0708

bird

1,0000

zoo

0,4750

2

blijdorp

0,2222

blijdorp

0,0396

curio

1,0000

blijdorp

0,4543

3

dierentuin

0,1667

dierentuin

0,0251

nature

1,0000

dierentuin

0,4034

4

curio

0,1389

bay

0,0148

rotterdam

1,0000

curio

0,2787

5

rotterdam

0,1389

curio

0,0145

zoo

1,0000

bay

0,2556

benadering opgenomen. De symmetrische coëfficiënt levert vooral synoniemen op zoals ’pinguino’, ’pinguine’, ’penguin’, . . . Deze hebben allemaal een lage score. Zo heeft de tag ’pinguino’ als Sum score slechts de waarde 0,0307. Dit komt omdat ’pinguin’ en ’pinguino’ slechts 299 keer tesamen voorkomen, terwijl ’pinguin’ afzonderlijk 6.802 keer voorkomt, en ’pinguino’ 2927 keer. De maximum score van de asymmetrische benadering is wel nog steeds vrij hoog: 0,4350 voor de tag ’zoo’. De tags ’zoo’ en ’pinguin’ komen dan ook vrij veel samen voor, namelijk 2.958 keer.


54

Tabel 3.6: Resultaten voor de tag ’pinguin’

Strategie (symmetrisch - getRelated(Tag)) sum

sum+

vote

vote+

rang

tag

score

tag

score

tag

score

tag

score

1

pinguino

0,0307

pinguino

0,0027

pinguine

1,0000

pinguino

0,7719

2

pingouin

0,0277

pingouin

0,0017

wilhelma

1,0000

pingouin

0,5710 0,5077

3

pinguine

0,0274

pinguine

0,0014

tierpark

1,0000

wuppertal

4

wuppertal

0,0213

wuppertal

0,0010

kingpenguin

1,0000

pinguine

0,4859

5

penguin

0,0145

penguin

0,0007

wuppertal

1,0000

penguin

0,4671

Strategie (symmetrisch - 500 foto’s) sum

sum+

vote

vote+

rang

tag

score

tag

score

tag

score

tag

score

1

zoo

0,4350

zoo

0,0410

bird

1,0000

penguin

0,7473

2

penguin

0,2327

penguin

0,0191

deutschland

1,0000

zoo

0,7369

3

tiere

0,0982

tiere

0,0064

animals

1,0000

tiere

0,6277

4

animal

0,0981

animal

0,0048

zoo

1,0000

wuppertal

0,4443

5

wuppertal

0,0915

wuppertal

0,0038

wuppertal

1,0000

animal

0,4328

Strategie (asymmetrisch - getRelated(Tag)) sum rang

tag

1 2

sum+ score

tag

zoowuppertal

0,0494

pinguino

0,0307

3

pingouin

4

pinguine

5

brillenpinguin

vote

vote+

score

tag

score

tag

score

zoowuppertal

0,0041

spheniscusdemersus

1,0000

zoowuppertal

0,7330

pinguino

0,0020

pinguine

1,0000

pinguino

0,6175

0,0277

pingouin

0,0013

brillenpinguin

1,0000

pingouin

0,4759

0,0274

pinguine

0,0011

africanpenguin

1,0000

pinguine

0,4164

0,0270

brillenpinguin

0,0009

reh

1,0000

wuppertal

0,3949


sum+

vote

vote+

rang

tag

score

tag

score

tag

score

tag

score

1

zoo

0,4354

zoo

0,0413

bird

1,0000

penguin

0,7473

2

penguin

0,2327

penguin

0,0191

deutschland

1,0000

zoo

0,7407

3

tiere

0,0983

tiere

0,0064

animals

1,0000

tiere

0,6277

4

animal

0,0981

animal

0,0048

zoo

1,0000

wuppertal

0,4443

5

wuppertal

0,0915

wuppertal

0,0038

wuppertal

1,0000

animal

0,4355


3.4

Toepassing op BOM

3.4.1

BOM-keyword relaties

55

Elk BOM-fragment is reeds getagd met een aantal keywords (veld MediaObjectFragmentKeyword uit figuur 1.2). Dit maakt het voor de zoekmachine makkelijker om zo goed mogelijk de query van de gebruiker te beantwoorden. Gebruikers kunnen echter andere sleutelwoorden opgeven dan degene die als metadata zijn toegevoegd, maar wel dezelfde betekenis hebben. Hierdoor zal een deel van de BOM-fragmenten niet in het resultaat worden opgenomen. Om dit probleem te beperken, kan de bovenstaande techniek worden gebruikt. Relaties zoeken tussen BOM-keywords en Flickr tags kan extra informatie opleveren: indien twee tags vaak samen voorkomen, wijst dit op een sterke samenhang. Wanneer de co-occurrence tussen een BOM-keyword en Flickr tag hoog is, kan dit keyword ofwel als tag worden toegevoegd bij alle BOM-fragmenten die het eerste keyword bevatten, ofwel als suggestie aan de gebruiker worden getoond. Flickr tags zijn namelijk door gebruikers toegevoegd, en sluiten dus ook vaak aan bij het taalgebruik dat BOM-gebruikers hanteren. Het Tag Recommendation System, zoals beschreven in paragraaf 3.3, verwacht als input één of meerdere gebruikerstags. Voor deze toepassing worden alle keywords genomen die reeds in BOM voorkomen.

Deze zijn opgeslagen in een tekstbestand.

Dit bestand telt momenteel 142.494

keywords. Aangezien Flickr wereldwijd verspreid is, zijn foto’s vaker getagd met Engelse woorden dan met Nederlandse. Daarom worden in het bijzonder de keywords onderzocht waarvoor een Engelse vertaling beschikbaar is. Deze vertaling is eigenlijk een Wikipedia-vertaling, omdat de gebruikte BOM-keywords vaak niet voorkomen in een woordenboek (bijvoorbeeld eigennamen, filmtitels, . . . ). Wikipedia bevat meestal wel informatie over deze domeinen. In totaal zijn reeds 13.009 keywords vertaald. Deze keywords werden niet zelf vertaald, maar zijn ook aanwezig in het tekstbestand.

3.4.2

Implementatie

Omdat de dataset van Flickr snel verandert, wordt een eigen dataset opgesteld om de relaties tussen keywords, en in het bijzonder tussen de vertaalde keywords, te onderzoeken. De vaste dataset zorgt ervoor dat het resultaat niet meer afhankelijk is van het moment waarop de verwerking gebeurt. Ook wanneer relevante tags als suggestie aan de gebruiker worden getoond, hoeft zo de nodige informatie niet meer at runtime aan de Flickr service te worden opgevraagd. Om de dataset op te stellen, worden vier bestanden aangemaakt: Het eerste bestand bevat voor elk vertaald BOM-keyword een lijst met 5.000 foto id’s, waarvan de foto met het corresponderende keyword getagd is. Voor elke foto worden alle tags opgezocht die bij de foto horen. Er wordt dus gebruikgemaakt van de alternatieve methode uit paragraaf 3.3.4.2, maar nu telkens met een set van 5.000 foto’s. Deze gegevens worden opgeslagen in het


56

tweede bestand. Deze twee bestanden kunnen worden gebruikt om de relaties tussen de vertaalde BOM-keywords te onderzoeken. Als laatste wordt een lijst van 1.000.000 random foto id’s aangelegd. Van deze foto’s worden wederom alle tags opgehaald en opgeslagen. De eigenlijke afbeeldingen die met de random foto id’s corresponderen, worden ook opgehaald en opgeslagen in JPG-formaat. Deze kunnen voor latere doeleinden worden gebruikt. Zo kan er een beeld worden gevormd van de foto’s die bij de tags horen. De set van 1.000.000 random foto’s en bijhorende tags, maakt het mogelijk om ook niet vertaalde BOM-keywords te onderzoeken, voor zover deze keywords voorkomen in de opgeslagen tags. Voor deze bestanden aan te maken, moeten er heel wat Flickr aanroepen gebeuren. Voor het ophalen van de foto id’s zijn er al ongeveer 130.000 requests nodig, aangezien elke response maximum 500 id’s bevat. Opdat het resultaat enige nauwkeurigheid zou opleveren, moeten er genoeg gegevens aan de dataset worden toegevoegd. Voor elk vertaald BOM-keyword (afgerond 13.000) worden er dan ook, zoals hierboven vermeld, 5.000 corresponderende foto id’s opgehaald. Niet elk keyword is echter 5.000 keer getagd, zodat het aantal requests op voorhand niet exact gekend is. Voor elk foto id moet er nog eens een oproep gebeuren om de bijhorende tags op te halen. Dit levert maximum nog eens 65.000.000 (13.000 × 5000) extra oproepen op. Daarnaast moet dit ook nog eens gebeuren voor de random foto’s. Het is duidelijk dat dit heel wat oproepen én tijd vergt. Daarom wordt de implementatie voorzien van een thread mechanisme, zodat de requests sneller kunnen gebeuren. De snelheid is echter gelimiteerd omdat de Flickr service maximaal tien aanvragen per seconde toelaat. Hierdoor moet er ook een limiet worden gesteld aan het aantal threads. Om alle uitvoer te genereren, worden vier Java programma’s voorzien:

CreatePhotoFile,

CreateTagFile, CreateRandomPhoto en CreateImages. Deze zijn allen op een gelijkaardige manier ge¨ımplementeerd. Elk hebben ze een methode startProcess, die de hele verwerking uitvoert. Hierbij wordt in eerste instantie een ThreadPool aangemaakt. Deze bevat threads, die voor de eigenlijke verwerking van de gegevens instaan. De eventuele input (BOM-keywords, foto id’s, . . . ) wordt eerst geparset, om nadien al het werk door te geven aan een object van het juiste WorkerThread type. Deze handelt de taak dan verder af. Het thread mechanisme wordt ge¨ımplementeerd met behulp van de klassen die ook bij de tag cloud werden gebruikt (zie paragraaf 1.3.3.1). Figuur 3.2 toont alvast een overzicht van de klassen die worden voorzien om de vier bestanden aan te maken. Om de ThreadPool te kunnen gebruiken, worden vier klassen geschreven die de Runnable interface implementeren. Deze voeren de verschillende taken uit die worden gebruikt in de vier programma’s. De vier klassen worden hieronder weergegeven:


57

Figuur 3.2: Overzicht van de Flickr applicatie klassen

PhotoThread - Deze klasse zorgt ervoor dat er 5.000 foto’s worden opgehaald en weggeschreven, die getagd zijn met het meegegeven BOM-keyword. Het resultaat wordt weggeschreven naar het opgegeven bestand. TagThread - Naast de foto’s moeten ook de tags worden opgehaald die bij een bepaald foto id horen. Hiervoor wordt als hulp eerst een tabel in een MySQL databank aangemaakt. Hierdoor hoeven foto id’s, die meer dan één keer voorkomen, samen met hun bijhorende tags, slechts één keer in het aan te maken bestand te worden opgenomen. Daarom houdt deze tabel bij of de tags van een foto al dan niet reeds zijn opgehaald. RandomPhotoThread - Deze klasse zorgt ervoor dat er 1.000.000 random foto id’s worden opgehaald en weggeschreven. ImageThread - De JPG-foto’s die bij de random photo id’s horen, moeten ook worden opgehaald en opgeslagen. Voor de bestandsnaam van de foto wordt het bijhorende foto id genomen. Het ophalen van de Flickr data gebeurt telkens via de aangemaakte klasse FlickrSearcher. De foto’s en tags worden op dezelfde manier opgehaald zoals in de testimplementatie van paragraaf 3.3. Om bijvoorbeeld de eerste 500 foto’s op te halen die de tag ’jaguar’ bevatten, kan volgende code worden


58

uitgevoerd:

Flickr flickr = new Flickr ( APIKEY , SECRET , new REST ( ) ) ; String usertag = ” j a g u a r ” ; S e a r c h P a r a m e t e r s sp = new S e a r c h P a r a m e t er s ( ) ; String [ ] list = { userTag } ; sp . setTags ( list ) ; P ho to sI n te rf ac e pi = flickr . g e t P h o t o s I n t e r f a c e ( ) ; PhotoList pl = n u l l ; try { pl = pi . search ( sp , 5 0 0 , 1 ) ; } c a t c h ( F li ck rE x ce pt i on fe ) { ... }

Omdat er in de Flickr API geen methode voorzien is om random foto’s op te halen, wordt in de FlickrSearcher klasse de methode getInterestingPhotoIds(Date) ge¨ımplementeerd. Deze haalt voor een bepaalde datum de meest interessante foto’s op via de interface InterestingnessInterface van de Flickr API. De methode geeft voor een opgegeven datum maximum 500 foto’s terug:

Calendar cal = new G r e g o r i a n C a l e n d a r ( ) ; cal . set ( 2 0 0 4 , 0 1 , 0 1 ) ; //YEAR MONTH(00= j a n u a r y ) DATE Date date = cal . getTime ( ) ; ArrayList<String> photoIds = new ArrayList<String >() ; I n t e r e s t i n g n e s s I n t e r f a c e ii = flickr . g e t I n t e r e s t i n g n e s s I n t e r f a c e ( ) ; ArrayList pl = ( ArrayList) ii . getList ( date , n u l l , 5 0 0 , 1 ) ; //maximum 500 f o r ( Photo photo : pl ) { photoIds . add ( photo . getId ( ) ) ; }

Om

aan

1.000.000

foto

id’s

te

komen,

wordt

in

RandomPhotoThread

de

getInterestingPhotoIds(Date) methode opgeroepen voor alle datums vanaf 1 februari 2004 (de oprichting van Flickr) tot en met de huidige datum (hier 5 maart 2009). Voor het ophalen van de JPG-afbeeldingen wordt een laatste methode voorzien: getImage(String). Deze haalt via de getImage(Photo,int) van PhotosInterface de gewenste foto (type BufferedImage) op. Hierbij moet als tweede parameter ook de grootte van de foto worden gespecifieerd, door een gepaste constante op te geven. Deze wordt op ’medium’ ingesteld, zodat een foto gemiddeld 30 kB groot is. De (gedeeltelijke) code ziet er als volgt uit:

String photoId = . . . P ho to sI n te rf ac e pi = flickr . g e t P h o t o s I n t e r f a c e ( ) ; Photo photo = pi . getPhoto ( photoId ) ; BufferedImage image = pi . getImage ( photo , Size . MEDIUM ) ;

Het wegschrijven van de data naar het opgegeven bestand gebeurt door middel van de klasse OutputWriter. Deze voorziet de vier methoden zoals afgebeeld op figuur 3.2.


59

FlickrExceptions Flickr kent een heleboel excepties, die opgeworpen kunnen worden wanneer er informatie wordt opgevraagd. Omdat het programma niet voortijdig zou stoppen, of niet eindeloos zou blijven draaien, worden twee error codes op een speciale manier opgevangen: • 100: Invalid API Key. Dit betekent dat de API Key niet meer geldig is. Bijgevolg is het ook niet meer mogelijk om data op te halen. Als deze foutcode optreedt, wordt het programma dan ook afgesloten met behulp van System.Exit(1). • 105: Service currently unavailable. beschikbaar is.

Dit wil zeggen dat de Flickr service tijdelijk niet

Als deze foutcode optreedt, wordt de aangeroepen methode opnieuw

uitgevoerd na een wachttijd van 300 milliseconden (methode Thread.sleep(300 )). Dit gaat door totdat de fout niet meer optreedt.

3.4.3

Testresultaten

De uitvoering van de vier programma’s (CreatePhotoFile, CreateTagFile, CreateRandomPhoto en CreateImages) nam heel wat tijd in beslag. Na ongeveer drie weken was de volledige dataset opgesteld. Hiervoor maakte elk programma gebruik van acht threads. De uitvoering verliep echter niet zo vlot: omdat er heel veel dataverkeer naar de Flickr service ontstond, werd de Flickr API key soms geblokkeerd. Bijgevolg konden de programma’s niet verder worden uitgevoerd, en moest een nieuwe API key worden aangevraagd. De dataset met de 1.000.000 random foto’s en bijhorende tags, werd door een begeleider geconverteerd naar een term-document matrix. Hoe dit precies gebeurde, wordt hier niet verder besproken. De werking van dit soort matrices komt wel nog aan bod in hoofdstuk 4. Aan de hand van deze term-document matrix kan gemakkelijk de co-occurrence tussen twee tags worden berekend. Er werden ook drie servlets opgesteld door een begeleider, om de dataset te doorzoeken. Twee van deze servlets tonen de frequentie van elke tag die voorkomt in de dataset: een versie waarbij de tags gesorteerd zijn op alfabet en een versie waarbij de tags gesorteerd zijn op frequentie. In totaal zijn er 98.538 tags opgenomen. Tabel 3.7 toont de tien tags die het meeste voorkomen in de dataset met de één miljoen random foto’s, samen met hun frequentie (kolom ’frequentie testset’). Ter vergelijking wordt ook weergegeven hoeveel keer de tag voorkomt in de volledige Flickr database (kolom ’frequentie Flickr’). Het valt op dat de eerste tag ’explore’ in de volledige Flickr database - die in november 2008 reeds meer dan drie biljoen foto’s telde - veel minder voorkomt dan de andere tags uit de top tien. De tag ’nature’ komt daarentegen heel veel voor. Misschien konden de random foto’s dus beter op een andere manier worden bepaald dan met de getInterestingPhotoIds(Date) methode uit paragraaf 3.4.2.


60

Tabel 3.7: Top 10 van tags uit testset met hoogste frequentie

frequentie rang

tag

testset

Flickr

1

explore

40.473

2

blue

29.565

3

sky

27.517

3.720.659

4

bw

27.095

3.202.185

5

nature

26.787

6.075.343

frequentie rang

tag

testset

Flickr

475.930

6

water

25.836

4.372.914

3.356.886

7

red

24.449

3.105.182

8

portrait

23.203

3.801.320

9

sunset

22.835

3.337.508

10

abigfave

22.679

563.437

De derde servlet die werd opgesteld door de begeleider, maakt het mogelijk om alle foto’s op te zoeken, die met één of meerdere tags zijn geannoteerd. Figuur 3.3 toont de gevonden foto’s (kolom ’doc’) voor de tags ’jaguar’, ’tiger’ en ’cat’, samen met de bijhorende tags. Wanneer minstens één tag uit de zoekopdracht voorkomt in de foto, wordt deze laatste als resultaat getoond. In totaal werden voor deze zoekopdracht 5.233 foto’s gevonden. De foto’s zijn gesorteerd volgens een relevantiescore, die als volgt wordt berekend:

#matches norm norm = (#tags bij foto) + (#tags van zoekopdracht) − (#matches) score =

Hierbij is ’#matches’ gelijk aan het aantal tags uit de zoekopdracht, die ook voorkomen bij de foto. Wanneer alle tags uit de zoekopdracht voorkomen bij de foto, is de relevantiescore gelijk aan één. Uit figuur 3.3 blijkt dat geen enkele foto geannoteerd is met zowel ’jaguar’, ’tiger’, als ’cat’. De tags ’cat’ en ’tiger’ komen daarentegen wel samen voor.

Figuur 3.3: Foto’s voor de tags ’jaguar’, ’tiger’ en ’cat’


61

Wanneer bij één van de drie servlets op een tag wordt geklikt, kunnen de co-occurrence waarden tussen deze tag en andere tags worden bekeken. Figuren 3.4, 3.5 en 3.6 tonen respectievelijk de co-occurrence waarden voor de tags ’jaguar’, ’kikker’ en ’pinguin’. Enkel de top vijf van de meest relevante tags wordt weergegeven. Bovenaan wordt het totaal aantal tags weergegeven, die samen voorkomen met de aangeklikte tag. De kolom ’co-occurrence’ geeft aan hoeveel keer de relevante tag (kolom ’keyword’) samen voorkomt met de aangeklikte tag. Het totaal aantal keer dat deze relevante tag voorkomt in de dataset, wordt weergegeven in de kolom ’total’. De laatste kolom, ’implies (sort)’, duidt de kans aan dat de relevante tag voorkomt, als de aangeklikte tag ook voorkomt. Deze waarde is gelijk aan de asymmetrische coëfficiënt, zoals deze ook is berekend bij de testimplementatie (zie paragraaf 3.3.5). De kolom daarvoor, ’implied by (sort)’, geeft de kans aan dat de aangeklikte tag voorkomt, als de relevante tag ook voorkomt. Beide kansen zijn uitgedrukt in procenten. Als testvoorbeelden werden terug dezelfde tags genomen als bij de testimplementatie. Met de servlet is het momenteel enkel mogelijk om de relevante tags voor één tag te bekijken. De test met de tags ’jaguar’, ’tiger’ en ’cat’ kan hier dus niet worden uitgevoerd. Figuur 3.4 toont de relevante tags voor de tag ’jaguar’. Hierbij komen twee tags voor (’zoo’ en ’animal’), die horen bij ’jaguar’ als ’katachtige’. De overige drie tags (’car’, ’etype’ en ’jag’) horen bij foto’s waarbij ’jaguar’ als ’voertuig’ voorkomt. Bij de vorige test (zie tabel 3.2) bestond de top vijf volledig uit tags die slaan op ’jaguar’ als ’voertuig’. In beide gevallen staat de tag ’car’ wel op de eerste plaats. Om de asymmetrische coëfficiënt van beide tests te vergelijken, kunnen de waarden uit respectievelijk de ’implies (sort)’ kolom (nieuwe test) en ’sum score’ kolom (vorige test uit tabel 3.2) worden vergeleken met elkaar. De tag ’car’ komt in de nieuwe test vijf procent meer voor dan in de vorige. De waarden bij de nieuwe test zijn wel berekend op basis van een kleinere dataset.

Figuur 3.4: Top 5 relevante tags voor ’jaguar’

Ook de test met de tag ’kikker’ werd op de nieuwe dataset uitgevoerd (zie figuur 3.5). In dit geval


62

komen twee tags uit de top vijf ook voor bij de vorige test: ’frog’ en ’nature’. De asymmetrische coëfficiënt voor de tag ’frog’ is hier beduidend hoog: in bijna 82 procent van de gevallen komt deze tag voor, als ’kikker’ ook voorkomt. Bij de vorige test uit tabel 3.4 was deze score ook vrij hoog, maar toch iets lager: bijna 69 procent. De score uit kolom ’implied by (sort)’ is daarentegen heel laag: één procent. Dit wijst erop dat Nederlandstalige gebruikers ook vaak een Engelstalige versie voorzien voor hun tags, maar niet omgekeerd. Dit is ook logisch, aangezien de Engelse taal meer wordt gebruikt dan de Nederlandse.

Figuur 3.5: Top 5 relevante tags voor ’kikker’

Figuur 3.6 toont de top vijf van meest relevante tags voor de tag ’pinguin’. Drie van de vijf tags zijn ook terug te vinden in tabel 3.6: ’penguin’, ’animal’ en ’zoo’. De asymmetrische coëfficiënt van de eerste twee tags zijn bij de nieuwe test opmerkelijk hoger: 47 procent tegenover 23 procent voor de tag ’penguin’, en 27 procent tegenover 10 procent voor de tag ’animal’. De tag ’zoo’ komt daarentegen 3,5 procent meer voor bij de oude test dan bij de nieuwe. Als laatste werd ook de test uitgevoerd voor de niet genormaliseerde versie ’pingu¨ın’, en voor de foutief gespelde versie ’pinquin’. Voor de eerste test werd slechts één foto gevonden die de tag ’pingu¨ın’ bevat. De foutief gespelde versie leverde in de nieuwe dataset geen resultaten op.

Figuur 3.6: Top 5 relevante tags voor ’pinguin’


63

Uit deze tests kan worden geconcludeerd dat zowel de kleinere dataset als de volledige Flickr database kan worden gebruikt om relevante tags te zoeken. Zowel de relevante tags zelf, als hun co-occurrence waarden kunnen bij beide datasets wel verschillen, maar leveren steeds bruikbare tags op. De relevante tags voor de vertaalde BOM-keywords kunnen op eenzelfde manier worden bekeken. Voor elk keyword kan de opgehaalde set met 5.000 foto’s worden gebruikt. Deze datasets kunnen dan op dezelfde manier als hierboven worden verwerkt in een servlet.

64

Hoofdstuk 4

Extractie van plaatsnamen 4.1

Algemeen

Uit de metadata die aan bestanden zijn toegevoegd, kan vaak extra kennis worden gefilterd. Zo bevatten alle fragmenten uit de BOM-database als metadata ook een fragmentbeschrijving: deze vertelt iets meer over de inhoud van het bijhorende fragment. In deze beschrijvingen komen dikwijls plaatsnamen terug. Deze data worden vaak ook door de gebruiker als deel van een zoekopdracht ingegeven. Een gebruiker kan bijvoorbeeld ge¨ınteresseerd zijn in alle ongevallen die zich de laatste vijf jaar in Gent, of in een straal van x kilometer rond Gent, voordeden. Het is dan ook nuttig om uit deze beschrijvingen alle plaatsnamen te filteren, zodat deze ook aan de metadata kunnen worden toegevoegd, onder een nieuw veld. Hiervoor kan een beroep worden gedaan op de Geonames service (GeoNames, 2009). In de volgende paragraaf wordt deze service verder toegelicht.

4.2

Geonames

Geonames is een service die bestaat uit een geografische database, die reeds meer dan acht miljoen geografische namen bevat. Al deze namen zijn onderverdeeld in categorieën: er zijn 9 hoofdcategorieën (feature classes) en 645 subcategorieën (feature codes). De hoofdcategorieën die in deze toepassing worden gebruikt, zijn de categorieën aangeduid met een A (country, state, region, . . . ) en een P (city, village, . . . ). Bijlage B geeft een overzicht van de subcategorieën van A en P. Andere geografische namen die niet tot deze categorieën behoren (bijvoorbeeld bergen, rivieren, parken, monumenten, . . . ), worden in deze toepassing niet gebruikt. Bij elke geografische naam zijn bijkomende gegevens opgeslagen, zoals de lengte- en breedtegraad, alternatieve namen in verschillende talen,

de populatie,

administratieve gebieden zoals

arrondissement, provincie, gewest en land, enzovoort. Al deze velden worden eveneens in bijlage B teruggegeven. Geonames biedt een aantal webservices aan, waar alle gegevens over de geografische plaatsen kunnen worden aan opgevraagd. Al deze informatie is ook als datadump beschikbaar, dus

Hoofdstuk 4. Extractie van plaatsnamen

65

in de vorm van een groot tekstbestand, allCountries.txt 1 . Dit bestand wordt dagelijks geupdatet. Om de plaatsnamen uit de BOM-beschrijvingen te filteren, wordt gebruikgemaakt van dit bestand, meer bepaald dat van 7 april 2009 (dit is 171 MB groot).

4.3

Bepaling van BOM-geonames

4.3.1

Parsen van BOM-beschrijvingen

Elk videofragment uit de BOM-database wordt gekenmerkt door vier onderverdelingen, die elk specifieke metadata (id, beschrijving, keywords, . . . ) bevatten die het fragment beschrijven: • ProgrammeGroup: de meest algemene metadata, met als voornaamste de titel van het programma waaruit het fragment komt. • Programme: bijkomende informatie over de programmaopnames, zoals de uitzenddatum en het afleveringnummer, keywords die bij het programma horen, . . . • MediaObject: informatie over het gearchiveerde fragment, zoals de datum van archivering, de bestandsnaam, . . . • MediaObjectFragment: de meest specifieke metadata die bij het fragment horen, zoals de titel, keywords, een beschrijving, . . . De metadata zijn opgeslagen onder de vorm van een boomstructuur waarbij de meer algemene metadata ouderknopen zijn van de meer specifieke metadata. Er zijn dan ook vier streams voorzien, opgeslagen onder de vorm van dumpfiles, die elk de data van één onderverdeling bijhouden. Deze data kunnen worden ingelezen en verwerkt aan de hand van een specifieke reader. De volgende paragraaf behandelt de manier waarop deze reader wordt gebruikt om beschrijvingen in te lezen en vervolgens te parsen. 4.3.1.1

Implementatie

De data uit de streams kunnen worden ingelezen en verwerkt aan de hand van de volgende, reeds bestaande, Java-klassen: DumpfileReader - Deze klasse maakt vier streamreaders van het type DumpfileStreamReader2 aan. Bestanden die een padnaam hebben waarin stream0, stream1, stream2 of stream3 voorkomt, bevatten gegevens over respectievelijk de categorieën ProgrammeGroup, Programme, MediaObject en MediaObjectFragment. De enige methode die hier wordt gebruikt, streamReaders3(), geeft de readers in lijstvorm terug. Aangezien voor deze toepassing enkel de beschrijving (en ter controle ook de tags) van elk MediaObjectFragment moet worden verwerkt, wordt enkel stream3 gebruikt. DumpfileStreamReader2 - Gegevens van één stream worden bijgehouden in de klasse DumpfileStreamReader2. 1

Alle gegevens van één stream bevinden zich in vier bestanden:

Deze en andere datadumps zijn terug te vinden via http://download.geonames.org/export/dump/


66

streamx, streamxd (data), streamxi (index ) en streamxr (reverse). opgeslagen in de vorm van sleutel/waarde-paren.

De metadata zijn

De verschillende sleutels die voorkomen,

kunnnen worden bekomen uit het streamx bestand. In deze toepassing zijn enkel de sleutels MediaObjectFragmentScriptDescription en MediaObjectFragmentKeyword nodig.

Het tweede

bestand bevat de eigenlijke metadata. Het derde zorgt voor indexering van de data, zodat er steeds geweten is op welke plaats in het bestand de specifieke data zich bevindt. Het vierde bestand bevat informatie over de ouder, wat hier verder van geen belang is. De

sleutel/waarde-paren

read(DumpfileDocument):

kunnen deze

worden zorgt

ingelezen

ervoor

dat

met de

behulp

van

de

methode

metadata

van

het

volgende

MediaObjectFragment in de juiste velden terechtkomt van het meegegeven DumpfileDocument. In dit laatste object worden alle sleutel/waarde-paren opgeslagen in de vorm van een TreeMap 2 . Een afgeleide klasse, DumpfileToken, bevat de metadata van één sleutel/waarde-paar, waarin ook het id van het document en van de ouder wordt bijgehouden. DumpfileStreamScanner - Deze klasse scant als het ware specifieke metadata. De constructor verwacht twee parameters: een streamreader van het type DumpfileStreamReader2 (in dit geval stream3 ), en een sleutel. De scanner overloopt dan ook enkel de metadata waarvan de sleutel gelijk is aan deze laatste parameter. De waarde die bij de sleutel hoort, wordt opgeslagen in een DumpfileToken. De twee belangrijkste methodes van de DumpfileStreamScanner klasse zijn lookahead() en accept(). De eerste geeft het opgevulde DumpfileToken terug, de tweede zorgt ervoor dat het volgende document wordt verwerkt (met behulp van de streamreader ), en dat de juiste informatie in het token wordt opgenomen.

Om de BOM-beschrijvingen te kunnen verwerken, worden de volgende zelfgeschreven klassen hieraan toegevoegd: MetadaDocument - Deze klasse is abstract en voorziet de mogelijkheid om specifieke metadata te parsen. De interface IMetaDataDocument wordt hierbij ge¨ımplementeerd en voorziet de volgende methoden:

v o i d parse ( List<String> list ) ; String [ ] getTerms ( ) ;

De parse(List<String>) methode zorgt ervoor dat de meegegeven lijst van metadatawaarden wordt verwerkt. Deze waarden worden opgesplitst in aparte termen, en kunnen worden opgevraagd met de getTerms() methode. MetadataReader - Om de metadata te overlopen die horen bij een specifiek veld, wordt de klasse MetadaReader voorzien. In de constructor wordt een DumpfileReader aangemaakt, waaraan vervolgens de nodige stream (stream3 ) kan worden opgevraagd. Deze stream wordt als parameter 2

Een Java-TreeMap wordt ge¨ımplementeerd als een rood-zwarte boom.


67

meegegeven aan de DumpfileStreamScanner, samen met de sleutel. Hiermee weet de scanner welke sleutel/waarde-paren hij moet bijhouden. De klasse bevat een methode read(IMedataDocument), die het volgende DumpfileToken ophaalt en het juiste sleutel/waarde-paar laat verwerken door het meegegeven IMedataDocument. De code ziet er als volgt uit:

p r i v a t e String key ; p r i v a t e D u m p f i l e S t r e a m S c a n n e r scanner ; p u b l i c b o o l e a n read ( I M e t a D a t a D o c u m e n t doc ) throws IOException { if

( ! scanner . eos ( ) ) { DumpfileToken dtoken = scanner . lookahead ( ) ; Map<String , List<String>> map = dtoken . data ; doc . parse ( map . get ( key ) ) ; scanner . accept ( ) ; return true ;

} e l s e return f a l s e ; }

Eens alle fragmenten zijn verwerkt, geeft de methode de waarde false terug. DescriptionDocument - De beschrijving die bij een fragment hoort, wordt geparset met behulp van een DescriptionDocument. Deze is afgeleid van de abstracte klasse MetadaDocument. Om alle geonames uit een beschrijving te halen3 , moet de beschrijving worden geparset. Dit wordt voorzien door de parse(List<String>) methode, die als volgt wordt ge¨ımplementeerd:

p r i v a t e String [ ] terms ; p r i v a t e i n t numberToken ; p u b l i c v o i d parse ( List<String> inputList ) { i f ( inputList != n u l l ) { String str = inputList . get ( 0 ) ; List<String> list = new ArrayList<String >() ; i f ( str != n u l l ) { str = AsciiUtils . normalise ( str ) . trim ( ) ; i f ( str . length ( ) > 0 ) { String [ ] tokens = str . split ( ” \\ s+” ) ; i f ( tokens . length >= numberToken ) { f o r ( i n t i =0; i
Met een geoname wordt een geografische naam bedoeld die in de Geonames database voorkomt

Hoofdstuk 4. Extractie van plaatsnamen Als parameter wordt een lijst meegegeven, die de metadata bevat.

68 Deze lijst bestaat in dit

geval slechts uit één string: de beschrijving. De methode zorgt er eerst voor dat de beschrijving wordt genormaliseerd, met behulp van de klasse AsciiUtils, die gebaseerd is op een bestaande implementatie (Unaccent letters, 2008). Niet ASCII-tekens worden hierbij geconverteerd naar hun ASCII-variant, niet alfanumerieke tekens worden vervangen door een spatie, en hoofdletters worden vervangen door kleine letters. BOM en Geonames zijn namelijk niet consequent geweest bij de opslag van gegevens: ’België’ kan de ene keer voorkomen met een trema, de andere is het trema weggelaten. Opdat de twee woorden een match zouden opleveren, moeten deze immers uit exact dezelfde tekens bestaan. Na de normalisatie wordt de beschrijving overlopen, en worden de juiste tokenreeksen opgeslagen. Een tokenreeks kan uit één of meerdere tokens bestaan4 , afhankelijk van de parameter numberToken die aan de constructor van deze klasse wordt meegegeven. Wanneer deze bijvoorbeeld de waarde één heeft, wordt de beschrijving opgesplitst in aparte tokens. Hiermee kunnen echter enkel de geonames uit de beschrijvingen worden gehaald, die bestaan uit één woord. Wanneer bijvoorbeeld de waarde twee wordt meegegeven, wordt de beschrijving opgesplitst in termen die telkens twee opeenvolgende tokens bevatten. Hiermee kunnen dan alle geonames worden gevonden die bestaan uit twee woorden. Figuur 4.1 toont een voorbeeld: bovenaan de figuur wordt elk token van de beschrijving apart overlopen. Op deze manier worden de plaatsnamen ’Heist’ (reeks 6) en ’Begijnendijk’ (reeks 16) gevonden5 . Dit betekent dat Heist-op-den-Berg niet als plaatsnaam herkend wordt. Dit kan worden opgelost door de beschrijving nog eens af te lopen, waarbij nu alle vier opeenvolgende tokens als één term worden behandeld. De zesde term is dan gelijk aan Heist-op-den-Berg. ExportMetadata - Deze klasse staat in voor de verwerking van alle beschrijvingen. Hiervoor zorgt de methode convertDescriptions(String input, String output, int numberToken). De eerste parameter geeft aan in welke directory de streams zich bevinden, de tweede geeft aan waar de uitvoer naartoe moet worden geschreven, en de derde specifieert het aantal tokens waaruit één term moet bestaan. Deze parameters worden doorgegeven aan de convert(String input, String output, IMetaDataDocument doc, String key) methode, die voor de verdere verwerking zorgt. Deze methode verwacht nog twee extra parameters: een IMetaDataDocument en een sleutel. Om de beschrijvingen te verwerken, moet een DescriptionDocument worden meegegeven, en als sleutel ’MediaObjectFragmentScriptDescription’. Eerst maakt de convert methode een TermDocumentWriter aan, die de uitvoer wegschrijft, en een MetadataReader, die zorgt voor de verwerking van de beschrijvingen. De read(IMetadaDocument) methode van de reader wordt opgeroepen, met als parameter het MetadataDocument.

Deze

methode wordt telkens opnieuw opgeroepen, zolang de waarde true wordt teruggegeven. Bij een 4

Met een token wordt een reeks van opeenvolgende karakters bedoeld. Een aantal opeenvolgende tokens worden

ook wel ’n-grams’ genoemd (unigram, bigram, trigram, ...) 5 Dit is een fictief voorbeeld, in realiteit worden nog meer steden gevonden, zoals ’Berg’.


69

Figuur 4.1: Extracten van steden uit een beschrijving (na normalisatie)

negatief antwoord (teruggeefwaarde false) zijn alle beschrijvingen verwerkt. Na elke read() oproep worden de termen van het geparsete document weggeschreven met de writeDocument(String[]) methode van de writer. Hoe dit wegschrijven precies gebeurt, wordt behandeld in paragraaf 4.3.2.1. De implementatie van deze methode wordt hieronder weergegeven:

p u b l i c v o i d c o n v e r t D e s c r i p t i o n s ( String input , String output , i n t numberToken ) throws IOException { String key = ” M e d i a O b j e c t F r a g m e n t S c r i p t D e s c r i p t i o n ” ; convert ( bomFile , outputFile , new D e s c r i p t i o n D o c u m e n t ( numberToken ) , key ) ; } p r i v a t e v o i d convert ( String input , String output , I M e t a D a t a D o c u m e n t doc , String key ) throws IOException { T e r m D o c u m e n t W r i t e r writer = new T e r m D o c u m e n t W r i t e r ( output ) ; Metad ataRead er reader = new Meta dataRead er ( input , key ) ; w h i l e ( reader . read ( doc ) ) { i f ( doc . getTerms ( ) != n u l l ) { writer . writeDocument ( doc . getTerms ( ) ) ; } } reader . close ( ) ; writer . close ( ) ; }

Figuur 4.2 toont ter verduidelijking het sequentiediagram voor het ophalen van één geparsete beschrijving: het object van de klasse ExportMetadata vraagt aan de MetadataReader de volgende geparsete beschrijving. De reader doet hiervoor beroep op de DumpfileStreamScanner. Indien deze scanner nog niet alle documenten (beschrijvingen) heeft verwerkt, stopt hij de informatie van het volgende document in een DumpfileToken. Dit wordt door de MetadataReader aan het DescriptionDocument meegegeven, dat op zijn beurt de beschrijving parset. Hierna bevat het


70

document alle termen, die dan door het ExportMetadata object worden weggeschreven naar het uitvoerbestand.

Figuur 4.2: Sequentiediagram: parsen van een beschrijving uit de BOM-database

4.3.2 4.3.2.1

Opslag van BOM-geonames Term-document matrix & inverted file

In de vorige paragraaf werd vermeld dat de geparsete beschrijvingen worden weggeschreven met behulp van een TermDocumentWriter. Deze zorgt ervoor dat alle termen worden opgeslagen in een term-document matrix, zodat de gegevens achteraf gemakkelijk kunnen worden geraadpleegd. Dit mechanisme wordt ook gebruikt door zoekmachines, zoals bijvoorbeeld Google. De werking ervan wordt hieronder beschreven. Een term-document matrix bestaat uit rijen, die de documenten aanduiden (hier beschrijvingen), en kolommen die informatie over de termen bijhouden (Zobel & Moffat, 2006). Voor elke verschillende term (hier een token of tokenreeks), die in minstens één van de documenten voorkomt, is er een kolom voorzien. Per document wordt voor elke term bijgehouden of het document deze term bevat (waarde 1), of niet (waarde 0). Het is dus niet nodig om elke term per document als string bij te houden: een 0 of 1 volstaat. Aangezien een cijfer minder opslagplaats vereist dan een woord, spaart dit heel wat geheugen uit. Hieronder wordt een voorbeeld gegeven met als invoer de onderstaande drie documenten:


71

• document 1: ’ongeval op e17 richting kortrijk’ • document 2: ’vrachtwagen veroorzaakt een ongeval’ • document 3: ’een ongeval in kortrijk eist een dode’

De bijhorende term-document matrix (hier met termen bestaande uit één token) wordt getoond in tabel 4.1. Tabel 4.1: Term-document matrix: theoretisch

termen document

ongeval

op

e17

richting

kortrijk

vrachtwagen

veroorzaakt

een

in

eist

dode

1

1

1

1

1

1

0

0

0

0

0

0

2

1

0

0

0

0

1

1

1

0

0

0

3

1

0

0

0

1

0

0

2

1

1

1

Op basis hiervan kan een omgekeerde lijst (inverted file) worden opgesteld: dit is een indexbestand dat per term aangeeft in welke documenten deze term voorkomt.

De alfabetisch gesorteerde

index biedt een snelle oplossing wanneer op zoek moet worden gegaan naar alle documenten die een bepaalde term bevatten. Tabel 4.2 toont het indexbestand dat hoort bij het bovenstaande voorbeeld. Tabel 4.2: Inverted file

4.3.2.2

term

documenten

dode

3

e17

1

een

2,3

eist

3

in

3

kortrijk

1

ongeval

1,2,3

op

1

richting

1

veroorzaakt

2

vrachtwagen

2

Implementatie

Om alle plaatsnamen op te slaan die in de BOM-beschrijvingen voorkomen, worden in eerste instantie vijf term-document matrices opgesteld. De eerste matrix bevat termen die bestaan uit


72

één token, de tweede termen die bestaan uit twee tokens, enzovoort. Alle termen die voorkomen in de BOM-beschrijvingen worden hierin opgenomen, ook degene die niet overeenkomen met een geoname. In tweede instantie worden de geonames uit deze matrices gehaald. Een test wees uit dat geen enkele term uit de BOM-beschrijvingen, bestaande uit meer dan vijf tokens, overeenkomt met een geoname. Daarom zijn er slechts vijf matrices nodig. Er zijn reeds een aantal Java-klassen beschikbaar op INTEC die een term-document matrix en index kunnen opbouwen en wegschrijven naar een bestand. De opslag ervan gebeurt in een iets andere vorm dan besproken in paragraaf 4.3.2.1. Enige kennis en begrip van de klassen is noodzakelijk voor de verdere implementatie van de toepassing. Daarom worden de belangrijkste aspecten ervan hieronder kort toegelicht: TermDocumentWriter - Deze klasse zorgt voor de aanmaak van een term-document matrix en schrijft deze weg als een bestand met extensie ’tdm’. De methode writeDocument(String[]) zorgt voor de opslag van alle termen die bij één document horen. Hiervoor wordt aan elke term een id gekoppeld. Er wordt echter geen rekening gehouden met gelijke termen: elke term heeft een verschillend id. Het zijn deze id’s die worden weggeschreven, en niet de termen zelf. De termen in stringvorm worden weggeschreven naar een apart bestand. Hiervoor wordt een TermSegmentWriter gebruikt. Nadat de methode voor elk document is uitgevoerd, moet de close() methode worden opgeroepen. Deze schrijft bovenaan het tdm-bestand het totaal aantal documenten en termen weg. Indien het bestand later wordt ingelezen, kan op die manier gemakkelijk worden achterhaald welke termen bij welk document horen. TermSegmentWriter - Om de termen in stringvorm op te slaan, wordt een bestand met als extensie ’t’ aangemaakt. De methode write(int, String) schrijft het id van de term weg, samen met de stringvorm van de term. Bovenaan het t-bestand wordt terug het totaal aantal termen weggeschreven. Dit bestand fungeert als een soort woordenboek: voor elke term kan worden opgezocht welk id ermee overeenkomt. De termen zijn hierin echter nog niet alfabetisch gesorteerd. Ook eenzelfde term kan meerdere malen voorkomen, aangezien er een verschillend id is voor gelijke termen. Tabel 4.3 geeft de term-document matrix terug voor het voorbeeld van paragraaf 4.3.2.1. In tegenstelling tot de matrix uit tabel 4.1, hoeft er enkel een cijfer opgenomen te worden voor termen die werkelijk in het document voorkomen. Tabel 4.4 toont een deel van het bijhorende woordenboek. Opeenvolgende termen worden hierin opeenvolgend genummerd. SimpleSortTerms - Om het woordenboek (t-bestand) alfabetisch te sorteren, kan de klasse SimpleSortTerms worden gebruikt. convert(String input, String output).

Hiervoor wordt een beroep gedaan op de methode Deze leest alle termen met bijhorende id’s uit het

ongesorteerde t-bestand in, en sorteert ze. Vervolgens worden de gesorteerde termen, samen met hun id, op dezelfde wijze als het oorspronkelijke t-bestand weggeschreven naar een nieuw bestand.


73

Tabel 4.3: Term-document matrix: implementatie (1)

document

term id’s

1

0,1,2,3,4

2

5,6,7,8

3

9,10,11,12,13,14,15

Tabel 4.4: Woordenboek (1)

term

term id

ongeval

0

op

1

e17

2

...

...

veroorzaakt

6

een

7

ongeval

8

een

9

...

...

UniqifySortedTerms - Deze klasse zorgt ervoor dat duplicate termen worden verwijderd. De opslag van gelijke termen met een verschillend id zorgt immers voor geheugenverspilling. Daarom koppelt deze klasse aan elke unieke term een uniek id. in het woordenboek te worden opgenomen.

Zo hoeft elke term slechts één keer

Hiervoor zorgt de methode processTerms(String

sortedTermFile, String output). Deze methode leest het gesorteerde woordenboek in en schrijft elke unieke term weg naar een nieuw t-bestand, samen met het nieuw gekoppeld id. Ten slotte wordt met behulp van de methode processTermDocMatrix(String input, String output) een nieuw tdm-bestand aangemaakt, dat opgebouwd is aan de hand van de nieuwe id’s. Nadat het woordenboek gesorteerd is en er de duplicaten uitgehaald zijn (tabel 4.6), ziet de term-document matrix eruit zoals in tabel 4.5 . Tabel 4.5: Term-document matrix: implementatie (2)

document

term id’s

1

6,7,1,8,5

2

10,9,2,6

3

2,6,4,5,3,2,0


74

Tabel 4.6: Woordenboek (2)

term

term id

dode

0

e17

1

een

2

eist

3

in

4

kortrijk

5

ongeval

6

op

7

richting

8

veroorzaakt

9

vrachtwagen

10

IndexWriter - Het indexbestand (met als extensie ’i’) ten slotte, wordt aangemaakt met behulp van de IndexWriter klasse. Met de methode makeHist(String input) wordt aan de hand van de meegegeven term-document matrix eerst een frequentietabel opgebouwd: deze houdt voor elk id bij hoeveel keer het voorkomt in de matrix. De methode makeIndex(String input) zorgt voor de opbouw van de eigenlijke index, aan de hand van de opgestelde frequentietabel. Hiervoor wordt een inttabel (indexDocs) bijgehouden, waarvan de grootte gelijk is aan het totaal aantal termen uit de term-document matrix. Deze wordt opgevuld met alle documentnummers die een bepaalde term bevatten, gesorteerd volgens term id. Per term id worden de bijhorende documentnummers nog eens gesorteerd in numerieke volgorde. Er zijn ook drie klassen beschikbaar, die ervoor zorgen dat de opgeslagen data gemakkelijk kunnen worden ingeladen en worden geraadpleegd: TermSegmentLoader - Om de woordenboekbestanden in te laden,

kan de klasse

TermSegmentLoader worden gebruikt. Deze bevat een attribuut terms van het type String[], waarmee alle termen in stringvorm kunnen worden opgevraagd.

De bijhorende id’s worden

opgeslagen in een inttabel ids. TermDocumentMatrix - Deze klasse houdt de informatie van een term-document matrix bij. De inttabel document data bevat voor elk document alle term id’s. Deze zijn gesorteerd volgens documentnummer. Om te weten op welke plaats de term id’s van een bepaald document zijn opgeslagen, kan de inttabel document offs worden geraadpleegd. Deze geeft telkens de beginplaats aan van de index, per document. IndexSegmentLoader - Het indexbestand kan gemakkelijk worden geraadpleegd met behulp van de klasse IndexSegmentLoader. Deze heeft als attributen twee inttabellen: postings data en postings offs. De eerste tabel houdt per term id alle documenten bij die de corresponderende term


75

bevatten. De lijst die bij één term id hoort, wordt ook wel een posting list genoemd. Om te weten waar welke term terug te vinden is, kan de tweede tabel worden geraadpleegd. Deze geeft voor een bepaalde term id de startindex uit de eerste tabel terug.

Zoals reeds vermeld in paragraaf 4.3.1 worden de vijf term-document matrices, samen met de woordenboeken, aangemaakt door de klasse ExportMetadata. Deze klasse zorgt er ook voor dat de termen worden gesorteerd (met behulp van de klasse SimpleSortTerms), en dat duplicaten worden verwijderd (met behulp van de klasse UniqifySortedTerms). Deze termen komen terecht in vijf nieuwe matrices en worden opgeslagen onder de naam bomxtoken2 (waarbij 1 ≤ x ≤ 5). In wat volgt, worden nog een aantal term-document matrices aangemaakt. De gesorteerde versies, waarbij duplicate termen zijn weggelaten, worden achteraan de bestandsnaam steeds met een ’2’ aangeduid. Nu alle termen opgeslagen zijn in aparte term-document matrices, kunnen hieruit de plaatsnamen worden gehaald. Hiervoor worden de volgende twee klassen ge¨ımplementeerd: ExportGeoAP - Om de BOM-termen te kunnen vergelijken met de geonames, worden ook deze laatste naar een term-document matrix weggeschreven. Hiervoor zorgt de klasse ExportGeoAP. Deze doet een beroep op de (reeds voorziene) klasse AllCountriesReader, die alle regels van het allCountries.txt bestand overloopt. Dit bestand bevat per geoname één regel met bijhorende gegevens. Wanneer een geoname behoort tot de hoofdcategorie ’A’ of ’P’ (zie paragraaf 4.2), wordt de nodige informatie (geonameid, asciiname, en alternatenames veld) uit de regel gehaald en weggeschreven. Het eerste veld wordt weggeschreven naar een gid-bestand. In dit bestand komen alle geonameid’s terecht die behoren tot één van de twee categorieën. De laatste twee velden worden weggeschreven naar een tdm-bestand: geoAP. In deze matrix komt één document met één geografische naam overeen, waarbij de genormaliseerde namen (zowel de ASCII-naam als de alternatieve namen) de termen vormen. De andere velden (bijvoorbeeld latitude, longitude, feature veld ) van de geoname worden niet weggeschreven.

Indien deze later toch nodig zouden zijn, kunnen deze wel gemakkelijk

worden opgevraagd.

Er wordt namelijk ook een ti-bestand (tekstindex) aangemaakt: voor

elke weggeschreven geoname wordt de plaats bijgehouden waar de geoname zich ergens in het allCountries.txt bestand bevindt. Al deze offsets worden in het ti-bestand opgeslagen. Zo kan achteraf met behulp van een RandomAccessFile snel naar een bepaalde regel worden teruggekeerd, zonder dat alle regels hoeven overlopen te worden. Voor deze matrix wordt ook een indexbestand opgebouwd, dat later in dit hoofdstuk nog nuttig zal zijn.


76

Nu zowel de BOM-termen als de geonames zijn opgeslagen, kan er worden gekeken welke BOM-termen met een geoname overeenkomen.

Hiervoor wordt de klasse ExportGeoMatches

voorzien: ExportGeoMatches - Deze klasse zorgt er ten eerste voor dat opnieuw vijf term-document matrices worden aangemaakt. Deze zien eruit zoals de matrices die werden aangemaakt door de klasse ExportMetadata, met het verschil dat ze enkel de termen bevatten die met een geoname overeenkomen. Om dit te realiseren, wordt per aan te maken matrix de writeGeoMatrix(String input, String output) methode opgeroepen. Deze methode ziet er als volgt uit:

p r i v a t e T e r m S e g m e n t L o a d e r geoTerms ; p u b l i c v o i d writ eGeoMatr ix ( String input , String output ) throws IOException { T e r m S e g m e n t L o a d e r bomTerms = new T e r m S e g m e n t L o a d e r ( input ) ; T e r m D o c u m e n t M a t r i x bomDocs = new T e r m D o c u m e n t M a t r i x ( input , 0 ) ; T e r m D o c u m e n t W r i t e r writer = new T e r m D o c u m e n t W r i t e r ( output ) ; f o r ( i n t i =0; i geoList = new ArrayList<String >() ; w h i l e ( u < v ) { // p e r doc termen o p h a l e n i n t item = bomDocs . document_data [ u ++]; String keyword = bomTerms . terms [ item ] ; i n t termId = Arrays . binarySearch ( geoTerms . terms , keyword ) ; i f ( termId >= 0 ) geoList . add ( keyword ) ; } writer . writeDocument ( geoList . toArray ( new String [ 0 ] ) ) ; } writer . close ( ) ; }

Als invoer verwacht deze methode één van de vijf eerder aangemaakte bomxtoken2 matrices (waarbij 1 ≤ x ≤ 5). Deze matrix wordt gebruikt om alle termen, per document, te overlopen. Via het bijhorende t-bestand kan het id van een term aan de bijhorende string worden gekoppeld. Om te kijken of deze string met een geoname overeenkomt, wordt deze opgezocht in een tabel. Deze tabel bevat alle termen uit het t-bestand dat met behulp van de vorige klasse (ExportGeoAP ) werd aangemaakt. Voor het opzoeken wordt de binaire zoekmethode gebruikt. Alle termen die in de lijst worden opgeslagen, komen dus overeen met een geoname, en worden per document weggeschreven naar een nieuwe term-document matrix, met als bestandsnaam bomxGeoWords. Aangezien alle documenten één voor één worden overlopen, worden termen die meermaals voorkomen, ook meermaals opgezocht in de tabel. Dit betekent dat bijvoorbeeld voor het woordje ’de’ 567.302 keer dezelfde opzoeking gebeurt, aangezien deze term 567.302 keer voorkomt in alle BOM-beschrijvingen samen. Een beter alternatief zou zijn om eerst een translatietabel op te stellen tussen de term id’s. Dit kan worden ge¨ımplementeerd met een inttabel: voor elk term id uit de


77

bomxtoken2 matrix wordt één keer de binaire zoekmethode uitgevoerd. Indien de term met een geoname overeenkomt, kan bijvoorbeeld de waarde één worden opgeslagen in de inttabel, op de plaats met als index het id van de bomxtoken2 term. Indien de term geen match oplevert, kan een nul worden opgeslagen. Nadien kunnen alle bomxtoken2 worden overlopen, waarbij voor elke term kan worden nagegaan of hij met een geoname overeenkomt, aan de hand van de translatietabel.

De tweede stap van het hoofdprogramma voegt de vijf bomxGeoWords matrices samen, en brengt ze onder in één nieuwe matrix, bomGeoWordsAll. Dit gebeurt met de methode mergeDocs(String[] inputs, String output). De bijhorende implementatie ziet er als volgt uit:

p u b l i c v o i d mergeDocs ( String [ ] inputs , String output ) throws IOException { T e r m S e g m e n t L o a d e r [ ] bomTermsList = new T e r m S e g m e n t L o a d e r [ inputs . length ] ; T e r m D o c u m e n t M a t r i x [ ] bomDocsList = new T e r m D o c u m e n t M a t r i x [ inputs . length ] ; f o r ( i n t i =0; i
files

ArrayList<String> geoList = new ArrayList<String >() ; f o r ( i n t j =0; j
files

i n t u = bomDocsList [ j ] . document_offs [ i ] ; // b e g i n doc i n t v = bomDocsList [ j ] . document_offs [ i + 1 ] ; // e i n d e doc w h i l e ( u < v ) { // p e r doc termen o p h a l e n i n t item = bomDocsList [ j ] . document_data [ u ++]; String keyword = bomTermsList [ j ] . terms [ item ] ; geoList . add ( keyword ) ; } } writer . writeDocument ( geoList . toArray ( new String [ 0 ] ) ) ; } writer . close ( ) ; }

4.3.3

Resultaten

Om een beeld te krijgen van de resultaten die met het bovenstaande proces werden bereikt, wordt hieronder de output besproken van de eerste tien documenten, voor elke stap in het proces. Alle stappen werden uitgevoerd op een Linux machine die beschikt over acht gigabyte RAM en vier cores. Bij de eerste stap werden de BOM-beschrijvingen geparset en vervolgens genormaliseerd. De uitvoer werd opgeslagen in de vorm van vijf matrices. De uitvoeringstijd van deze stap bedraagde 76 minuten, 15 seconden. Om de matrices op te stellen, werden telkens 166.728 beschrijvingen geparset.


78

Tabel 4.7 geeft voor elke aangemaakte matrix (bomxtoken, 1 ≤ x ≤ 5) de grootte van het tdm-bestand, samen met de grootte van het woordenboekbestand (kolom ’t’). Kolom ’t(2)’ toont de bestandsgrootte van de gesorteerde woordenboek met unieke termen. Het aantal verschillende termen dat in dit laatste woordenboek is opgenomen, wordt in kolom ’# termen’ weergegeven. Tabel 4.7: Aangemaakte bestanden en hun groottes

bestanden en hun groottes (bytes) matrix

tdm

t

bom1token

39.772.924

110.023.089

3.013.110

194.922

bom2token

39.115.088

168.227.455

40.941.972

2.026.649

bom3token

38.463.104

224.544.584

104.660.689

4.165.051

bom4token

37.817.992

278.830.449

158.159.970

5.124.683

bom5token

37.179.432

331.143.200

199.048.228

5.383.688

geoAP

36.497.232

88.803.025

52.741.970

2.881.841

bom1GeoWords

21.163.588

48.460.769

340.958

28.600

bom2GeoWords

927.852

986.886

36.115

2.221

bom3GeoWords

678.116

62.816

7.047

315

bom4GeoWords

667.792

5.510

1.536

58

bom5GeoWords

667.024

666

182

6

21.436.692

49.516.599

385.790

31.200

bomGeoWordsAll

t(2)

# termen

De beschrijvingen werden ingelezen met behulp van een reader. de eerste tien beschrijvingen,

zoals die zijn opgeslagen in stream3,

Tabel 4.8 toont met als sleutel

MediaObjectFragmentScriptDescription. Tabel 4.8: Eerste tien BOM-beschrijvingen

1 2

BEGINGENERIEK DONAAT DERIEMAEKER IN BELLEWAERDE MET TOERISTEN DIE TIPS GEVEN OVER DE ONBEKENDE GAST OP FOTO

3

EINDE.

4

EINDGENERIEK EN PRIJSWINNAARS JAN HOET VANUIT HET MUSEUM VOOR HEDENDAAGSE KUNST IN GENT

5

(CORPUS DELICTI TENTOONSTELLING) OVER EEN BEELDHOUWWERK VAN HUGO DEBAERE

6

KURT VAN EEGHEM VANUIT TURKIJE OVER MUZIEK

7

LEJA VAN HOEYMISSEN IN DE TUIN VAN DELLA BOSIERS EN PRIJSVRAAG

8

RANI DE CONINCK OVER DE EERSTE COMMUNICATIESATELLIET

9

RANI GEEFT VEILIGHEIDSTIP VOOR AAN ZEE

10

RANI IN DE KELDER BIJ BEN CRABBE OVER VANESSA PARADIS


79

Elke beschrijving werd vijf keer geparset. De eerste keer werden de beschrijvingen opgesplitst in aparte tokens. Het resultaat voor de eerste tien documenten (beschrijvingen) wordt getoond in tabel 4.9. Tabel 4.9: Eerste tien documenten na parsen van de BOM-beschrijvingen

1 2

begingeneriek donaat, deriemaeker, in, bellewaerde, met, toeristen, die, tips, geven, over, de, onbekende, gast, op, foto

3

einde

4

eindgeneriek, en, prijswinnaars

5

jan, hoet, vanuit, het, museum, voor, hedendaagse, kunst, in, gent, corpus, delicti, tentoonstelling, over, een, beeldhouwwerk, van, hugo, debaere

6

kurt, van, eeghem, vanuit, turkije, over, muziek

7

leja, van, hoeymissen, in, de, tuin, van, della, bosiers, en, prijsvraag

8

rani, de, coninck, over, de, eerste, communicatiesatelliet

9

rani, geeft, veiligheidstip, voor, aan, zee

10

rani, in, de, kelder, bij, ben, crabbe, over, vanessa, paradis

De wijzigingen ten opzichte van de originele documenten zijn hier miniem: enkel de hoofdletters zijn vervangen door kleine letters, een punt is weggelaten alsook twee haakjes. Vervolgens werd de beschrijving opgesplitst per twee, drie, vier en vijf tokens. Voor de tweede matrix ziet het tweede document er bijvoorbeeld als volgt uit: donaat deriemaeker, deriemaeker in, in bellewaerde, bellewaerde met, met toeristen, toeristen die, die tips, tips geven, geven over, over de, de onbekende, onbekende gast, gast op, op foto

Om de BOM-termen te kunnen vergelijken met de geonames, werd een matrix (geoAP ) opgebouwd die alle geonames uit de categorieën A en P bevat (zie paragraaf 4.2). Zoals getoond in tabel 4.7, werden 2.881.841 verschillende plaatsnamen gevonden. De opbouw van de matrix, samen met de gesorteerde versie met unieke termen, werd opgebouwd in een tijd van 14 minuten, 55 seconden. In de volgende stap werden de termen van elke bomxtoken matrix vergeleken met de termen uit de geoAP matrix. De gevonden BOM-geonames kwamen terug terecht in vijf matrices. Nadien werd de uitvoer van deze matrices (en dus alle BOM-geonames) ondergebracht in één matrix (bomGeoWordsAll ). Deze stap werd uitgevoerd in een tijd van 13 minuten, 51 seconden. Tabel 4.10 toont de uitvoer van de bomGeoWordsAll matrix, voor de eerste tien documenten. Deze termen bestaan telkens uit één woord. In totaal werden voor deze tien documenten 46 geonames gevonden.


80

Tabel 4.10: Gevonden geonames voor de eerste tien documenten

1 2

in, met, die, geven, over, de, op, foto

3

einde

4

en

5

jan, het, in, gent, corpus, over, een, van, hugo

6

kurt, van, eeghem, turkije, over

7

leja, van, in, de, tuin, van, della, en

8

rani, de, over, de

9

rani, aan, zee

10

rani, in, de, bij, ben, over, paradis

Het valt op dat er tussen deze tien documenten heel wat termen staan, die geen plaatsnaam aanduiden. Eigenlijk zouden enkel ’gent’ en ’turkije’ een true match mogen opleveren. Toch komen ook de 44 andere gevonden termen voor in het allCountries.txt bestand. Zo blijkt dat de plaats ’foto’ zelfs in vier landen voorkomt: Zweden, Sierra Leone, Togo en Kameroen. Om een beter resultaat te krijgen, moeten de geonames dan ook aan bijkomende filters worden onderworpen. Dit wordt behandeld in paragraaf 4.6.1.

4.4 4.4.1

Plaatsnamen binnen een bepaalde regio Semantische query’s: boomstructuur van geonames

De resultaten van een query, uitgevoerd op de BOM-database, beantwoorden niet steeds aan de verwachtingen van de gebruiker. Dit komt bijvoorbeeld vaak voor wanneer iemand op zoek is naar bepaalde gebeurtenissen die zich afspeelden in een bepaald gebied. Doordat de beschrijvingen en keywords van BOM-fragmenten niet steeds voorzien zijn van de juiste annotaties, worden heel wat relevante fragmenten niet in de resultaten opgenomen. Een gebruiker kan in de BOM-database bijvoorbeeld op zoek gaan naar alle ongevallen die plaatsvonden in Oost-Vlaanderen. Het komt dan vaak voor dat een BOM-fragment wel geannoteerd is met de gemeente, maar niet met de provincie. Daardoor wordt slechts een klein deel van de fragmenten in de resultaten opgenomen. Dit probleem werd al eens behandeld in paragraaf 2.5.1. Toen werd een ontologie van België opgesteld, om dit soort query’s te kunnen uitvoeren. Deze hield alle informatie over plaatsen en deelgebieden van België bij. In deze paragraaf wordt dit probleem opnieuw aangepakt.

Deze keer wordt er echter

gebruikgemaakt van Geonames: aan de hand van deze database kan een plaatsnaam opnieuw worden gelinkt aan zijn bijhorende, bovenliggende gebieden. Deze keer beperkt dit zich niet tot


81

België, maar wordt een boomstructuur opgebouwd die informatie bevat over plaatsnamen, van over de hele wereld. Deze boom bevat vijf niveaus: naast de plaatsnaam wordt de bijhorende admin1 -, admin2 -, landen continentinformatie opgenomen, voor zover deze gegevens aanwezig zijn in het allCountries.txt bestand. De boom beperkt zich tot geonames die ook in BOM voorkomen. Door de gegevens van de boomstructuur in de BOM-database te importeren, wordt het mogelijk om semantische query’s uit te voeren. Hiervoor wordt een gebruikersinterface voorzien. Deze bevat een zoekbox, die kan worden gebruikt om semantische clausules uit te voeren. Zo is het mogelijk om gebeurtenissen op te zoeken, die zich in een bepaalde regio (provincie, gewest, land, . . . ) afspeelden. Op deze manier zullen waarschijnlijk heel wat meer relevante BOM-fragmenten worden gevonden die aan de zoekopdracht voldoen.

4.4.2

Implementatie

De boomstructuur wordt deze keer opgeslagen onder de vorm van een term-document matrix, met als naam geotree2. Voor elke geoname die in de BOM-database voorkomt, worden de bovenliggende gebieden opgezocht. Al deze plaatsen en gebieden worden gerepresenteerd door hun bijhorende geonameids. Deze informatie wordt opgeslagen in de nieuwe term-document matrix. Opdat de gebruiker query’s zou kunnen uitvoeren, zoals ’geef mij alle ongevallen in Oost-Vlaanderen’, wordt de BOM-database uitgebreid met een nieuw veld, met als sleutel geotagger. De waarde van dit veld bevat voor elk fragment alle geonameids van de geonames die uit de corresponderende beschrijving werden gehaald. Hiernaast bevat dit veld ook alle geonameids van de corresponderende bovenliggende gebieden. Wanneer een BOM-beschrijving bijvoorbeeld de plaats ’Gent’ bevat, worden volgende geotagger waarden toegevoegd: 2797656 (Gent), 2789733 (Oost-Vlaanderen), 3337388 (Vlaams Gewest) en 2802361 (België). Om al deze waarden te kunnen importeren, wordt een nieuwe term-document matrix opgesteld (bomGeoIds2 ), aan de hand van de geotree2 matrix. Deze is eigenlijk een uitbreiding van de bomGeoWordsAll2 matrix. Naast de gevonden geonames bevat deze nieuwe matrix per beschrijving ook alle geonames van de bovenliggende gebieden. Het zijn echter de geonameids die worden opgeslagen in de matrix, en niet de geonames zelf. Om semantische query’s te kunnen uitvoeren, wordt als laatste een servlet voorzien: deze bevat een tekstbox, waarin de gebruiker een zoekopdracht kan ingeven. Indien (een deel van) de query tussen vierkante haken wordt geplaatst, wordt getracht om dit deel om te zetten naar de overeenkomstige geonameid. Wanneer bijvoorbeeld de volgende query wordt ingetypt: +ongeval +[oost vlaanderen], wordt deze query eerst omgezet naar: +ongeval +geotagger:2789733,


82

alvorens deze door te geven aan de klassieke zoekmachine. Hierdoor kunnen de ongevallen worden gevonden, die plaatsvonden in een gebied uit de provincie Oost-Vlaanderen.

Om dit alles te implementeren, worden de volgende klassen voorzien: GeoTree - Deze klasse is verantwoordelijk voor het opstellen van de eerste matrix (geotree2 ). De methode generateDescriptionTree overloopt alle termen van de bomGeoWordsAll2 term-document matrix, en bepaalt voor elke term de bijhorende, bovenliggende gebieden. Deze gebieden kunnen worden opgezocht in het allCountries.txt bestand.

Elk gebied wordt in de boomstructuur

gerepresenteerd door de geonameid. Om te weten op welke regel(s) de bijhorende informatie van de BOM-term te vinden is, kan beroep worden gedaan op de eerder aangemaakte geoAP2 bestanden (zie paragraaf 4.3.2.2). Met behulp van het geoAP2 indexbestand kunnen alle documenten uit de geoAP2 matrix worden gevonden, die overeenkomen met de BOM-term. Hiervoor moet het term id gekend zijn dat met de BOM-term overeenkomt. Dit kan worden opgezocht in het woordenboekbestand. Eens alle geoAP2 documentnummers gekend zijn, kunnen in het geoAP2 tekstindexbestand de bijhorende regels uit het allCountries.txt bestand worden opgezocht. De regels worden één voor één aan de AllCountriesReader doorgegeven, die de regels inleest en de bovenliggende gebieden opzoekt. Deze gebieden bevinden zich in de velden admin3, admin2 en cc2. Tabel 4.11 toont als voorbeeld de gevonden documenten (kolom ’doc nr’) voor de geonames ’Rusland’, ’België’ en ’Gent’. De bovenliggende gebieden worden getoond in de kolommen ’adm2’, ’adm1’ en ’cc2’. De waarden worden hierbij weergegeven in de vorm van codes. Zo komt ’VOV’ overeen met ’Oost-Vlaanderen’, ’VLG’ met ’Vlaams Gewest’, enzovoort. In de boomstructuur moeten deze gebieden echter worden gerepresenteerd door de bijhorende geonameids. Tabel 4.11: Gevonden documenten voor ’Rusland’, ’België’ en ’Gent’

geoname

doc nr

geonameid

adm2

adm1

cc2

feature code

aantal

rusland

2152757

2017370

/

/

RU

PCLI

2.581

808221

2638935

C9

ENG

GB

PPL

3

belgie gent

153746

2802361

/

/

BE

PCLI

9.619

2708817

1020330

/

03

ZA

PPL

11

150293

2797656

VOV

VLG

BE

PPL

4.117

150294

2797657

VOV

VLG

BE

ADM4

4.117

1715753

2755597

1705

03

NL

PPL

82

2109949

801376

/

CI

RU

PPL

50

Om de codes te converteren naar geonameids, wordt een beroep gedaan op drie extra


83

tekstbestanden: countryInfo, admin1Codes en admin2Codes. Deze kunnen net als het allCountries tekstbestand worden teruggevonden op de geonames download server. Het eerste bestand, countryInfo, bevat informatie over elk land. Enkel de geonameids en ISO-codes zijn hierbij van belang. Deze laatste komen overeen met de codes die worden gebruikt in het cc2 veld. In het tweede bestand, admin1Codes, bevinden zich alle codes die overeenkomen met de waarden van het admin2 veld. (De naam van het tekstbestand zorgt dus voor verwarring.) Een admin2 code begint met de landcode, gevolgd door een punt en een aanvullende code. Deze laatste kan zowel uit cijfers als uit letters bestaan. ’Vlaams Gewest’ is bijvoorbeeld terug te vinden onder de code ’BE.VLG’. Het derde bestand, admin2Codes, bevat gelijkaardige informatie, maar dan voor codes die overeenkomen met het admin3 veld. Een admin3 code begint met een code uit het admin1Codes bestand, gevolgd door een punt en een aanvullende code. Deze kan terug bestaan uit cijfers of letters. De code ’BE.VLG.VOV’ duidt bijvoorbeeld de provincie ’Oost-Vlaanderen’ aan. Ook deze laatste twee bestanden bevatten telkens de corresponderende geonameid. Om deze informatie gemakkelijk te kunnen raadplegen,

wordt een aanvullende klasse

AdminCodeLoader voorzien. Deze leest de drie bestanden met de codes in, en slaat de nodige informatie op in een map van het type HashMap<String, Integer>. De sleutel stelt hierbij de code voor, terwijl de waarde de geonameid bijhoudt. Met behulp van deze map kunnen alle codes van de bovenliggende gebieden worden omgezet naar geonameids. In tabel 4.11 is ook te zien dat voor elk van de drie geonames meerdere regels worden gevonden in het allCountries.txt bestand. Enkel de juist ge¨ınterpreteerde geonames moeten worden opgeslagen in de boomstructuur: in de BOM-beschrijvingen zal ’rusland’ bijvoorbeeld hoogst waarschijnlijk steeds als land worden bedoeld, en nooit als plaatsnaam in Groot-Brittannië. Om de foutieve geonames te elimineren, wordt daarom een telling uitgevoerd: per geoname, die door de geoAP2 matrix werd gevonden, wordt gekeken hoeveel keer elk van de bijhorende bovenliggende gebieden (adm2, adm1 en cc2 veld) samen voorkomt met de geoname, in de BOM-beschrijvingen. De som van deze aantallen wordt per geoname bijgehouden. Enkel de geoname met de grootste som wordt opgenomen in de boomstructuur, samen met zijn bovenliggende gebieden. De kolom ’aantal’ in tabel 4.11 toont aan dat zo de juiste geonames worden opgenomen: ’gent’ komt bijvoorbeeld 4117 keer samen voor met één van de volgende bovenliggende gebieden: Oost-Vlaanderen, Vlaams Gewest en België. Daarentegen wordt deze plaats ’slechts’ 52 keer gevonden samen met (een bovenliggend gebied uit) Nederland. De code om de aantallen te tellen voor één document, ziet er als volgt uit:

p r i v a t e i n t idsTogether ( i n t idKeyword , ArrayList geoIdList ) { i n t count = 0 ; Iterator it = geoIdList . iterator ( ) ; w h i l e ( it . hasNext ( ) ) { Integer id = it . next ( ) ; // g i d s R e v e r s e = map d i e p e r geonameid h e t geoAP−docnr b i j h o u d t


84

i n t index = gidsReverse . get ( id . intValue ( ) ) . intValue ( ) ; i n t p = geoDocsListAP . document_offs [ index ] ; i n t q = geoDocsListAP . document_offs [ index + 1 ] ; while (p < q) { // p e r doc termen o p h a l e n ( a l l e namen d i e b i j geonamid horen ) i n t item = geoDocsListAP . document_data [ p ++]; String keyword = geoTermsAP . terms [ item ] ; // k i j k e n o f woord i n BOM−b e s c h r i j v i n g e n voorkomt i n t termId = Arrays . binarySearch ( termsList . terms , keyword ) ; i f ( termId >= 0 ) { //bom documenten o p h a l e n d i e term b e v a t t e n i n t id2 = bomTermsList . ids [ termId ] ; i n t v = bomIndexList . postings_offs [ id2 ] ; i n t w = bomIndexList . postings_offs [ id2 + 1 ] ; w h i l e ( v<w ) { // a l l e termen p e r doc o v e r l o p e n i n t doc = bomIndexList . postings_data [ v ++]; i n t begin = bomDocsList . document_offs [ doc ] ; i n t end = bomDocsList . document_offs [ doc + 1 ] ; w h i l e ( begin<end ) { // i n bomdoc komt ook idkeyword v o o r −> a a n t a l v e r h o g e n i f ( bomDocsList . document_data [ begin++] == idKeyword ) { count++; } }}}} } r e t u r n count ; }

Hierbij is idKeyword het term id van de te onderzoeken geoname uit de bomGeoWordsAll2 matrix. De lijst geoIdList bevat alle geonameids van de bovenliggende gebieden van één document. Deze geonameids worden één voor één overlopen. Alle mogelijke namen die overeenkomen met de geonameid, worden opgezocht in de geoAP2 matrix. Telkens wanneer in de bomGeoWordsAll2 matrix een naam samen voorkomt met de te onderzoeken geoname, wordt de teller met één verhoogd. Op deze manier worden alle relevante BOM-geonames in de boomstructuur opgenomen. Om de gegevens uit de boom later gemakkelijk te kunnen raadplegen, wordt voor elke geoname de overeenkomstige geonameid in een apart tekstbestand, geotree.txt, bijgehouden. Door opnieuw een index- en tekstindexbestand aan te maken, kan opnieuw alle informatie over een opgeslagen geoname gemakkelijk worden opgezocht. Nu de boomstructuur is opgebouwd, kunnen aan elke BOM-beschrijving de bovenliggende gebieden worden toegevoegd, voor zover deze nog niet aanwezig zijn. Deze informatie komt terecht in de tweede op te bouwen matrix: bomGeoIds2. Hiervoor wordt de klasse ExportGeomatches uitgebreid: ExportGeomatches - Deze klasse, die werd voorzien om de bomGeoWordsAll2 matrix op te bouwen (de matrix die voor elke BOM-beschrijving de gevonden geonames bevat, zie paragraaf 4.3.2.2), wordt uitgebreid met een nieuwe methode: writeWithDerivatives(String invoerBom, String invoerTree, String output). Als invoerparameters worden de bomGeoWordsAll2 en geotree2 matrix


85

meegegeven. Aan de hand hiervan wordt een nieuwe matrix opgesteld, die per document alle geonameids bevat van één BOM-beschrijving, samen met de geonameids van alle bovenliggende gebieden. Om geonames te kunnen converteren naar geonameids, wordt ook het geotree.txt bestand ingeladen dat werd aangemaakt bij de opbouw van de boomstructuur. De bomGeoWordsAll2 matrix bevat immers geonames in stringvorm, terwijl de boomstructuur is opgesteld aan de hand van geonameids. Voor elke term van de bomGeoWordsAll2 matrix worden de geonameids van de bovenliggende gebieden opgezocht. Hiervoor wordt beroep gedaan op het indexbestand van de boomstructuur: het term id wordt opgezocht, zodat de documenten kunnen worden opgehaald die de term bevatten. Het document waarvan de eerste term overeenstemt met de te zoeken term, is het gezochte document. Wanneer een plaats niet op het onderste niveau van de boomstructuur ligt, kan het namelijk gebeuren dat de term in meerdere documenten voorkomt. De geonameid van België komt bijvoorbeeld in elk document voor dat informatie over een gemeente in België bijhoudt. Voor elke term worden de bovenliggende gebieden in een lijst bijgehouden. Indien de geonameids voor alle termen zijn bepaald, kunnen alle documenten uit de bomGeoWordsAll2 matrix worden overlopen. Elke term wordt hierbij vervangen door de corresponderende lijst van geonameids. Deze informatie wordt weggeschreven naar de nieuwe matrix, bomGeoIds2. De bekomen matrix, samen met het nieuwe geotagger veld, is door een begeleider ge¨ımporteerd in de BOM-database. Om het systeem te kunnen testen, wordt een servlet geschreven. Hiervoor wordt de volgende klasse ge¨ımplementeerd: GeoServlet - Deze klasse maakt een servlet aan die een zoekbox bevat. Hierin kan de gebruiker een query invoeren met een semantische clausule: indien een plaatsnaam tussen vierkante haken wordt ingegeven, wordt de plaatsnaam, bij een druk op de zoekknop, omgezet naar de corresponderende geotagger waarde (geonameid ). Deze vertaalde query wordt hierna met behulp van een HTTP POST-request doorgegeven aan de klassieke zoekmachine. De HTTP-response bevat opnieuw het totaal aantal resultaten, samen met de details van de eerste tien resultaten. Deze servlet maakt gebruik van de Jetty webserver (Jetty Webserver , 2009). Dit is een eenvoudige HTTP-server en servletcontainer, die volledig geschreven is in Java. De webserver kan gemakkelijk in Java toepassingen worden ingebed en wordt ook gebruikt voor de gebruikersinterface van de klassieke BOM-zoekmachine. De server kan als volgt worden ge¨ınitaliseerd en opgestart:

GeoServlet geoServlet = new GeoServlet ( ” g e o t r e e ” , ” bomGeoWordsAll2 ” ) ; Server server = new Server ( 8 0 ) ; Context root = new Context ( server , ” / ” , Context . SESSIONS ) ; root . addServlet ( new ServletHolder ( geoServlet ) , ” / g e o s e a r c h ” ) ; server . start ( ) ;


86

Er wordt een nieuw Server object aangemaakt, waaraan een poortnummer wordt meegegeven (bijvoorbeeld 80). Dit object zorgt ervoor dat elke aanvraag aan het juiste servletobject wordt doorgegeven. Met behulp van een Context object kan het contextpad worden ingesteld, en kunnen sessies worden beheerd. Hieraan kunnen ook servlets worden toegevoegd, met behulp van de methode addServlet(ServletHolder servlet, String path). Het ServletHolder object houdt informatie over de servlet bij, en zorgt voor het laden van de servlet wanneer dit nodig is. Vervolgens kan de server worden opgestart. De GeoServlet klasse die wordt ge¨ımplementeerd, is afgeleid van de klasse AbstractSimpleServlet, die reeds voorzien is en gebruikt wordt door andere BOM-servlets. Deze is op zijn beurt afgeleid van de javax.servlet.HttpServlet klasse. AbstractSimpleServlet voorziet niets anders dan enkele methoden om het begin (methode writeHeader(PrintWriter writer, String title)) en einde (methode writeTrailer(PrintWriter writer ) van een HTML-pagina weg te schrijven. De PrintWriter, die het antwoord wegschrijft, kan worden opgeroepen met de openWriter(HttpServletResponse response) methode. De

enige

publieke

methode

die

GeoServlet

voorziet,

is

de

doGet(HttpServletRequest,

HttpServletResponse) methode. Indien de servlet wordt aangeroepen zonder request parameter q, wordt met behulp van de PrintWriter een zoekbox weggeschreven naar de HTML-pagina. Hierin kan de gebruiker een zoekopdracht ingeven. Bij een klik op de zoekknop wordt opnieuw een HTTP GET-request gegenereerd en door de doGet methode afgehandeld. Nu bevat de requestparameter q wel een waarde, namelijk de ingegeven query. Elke term tussen vierkante haken wordt omgezet naar de bijhorende geonameid. Voor de omzetting wordt beroep gedaan op een map. Deze bevat alle mogelijke geonames die in de BOM-beschrijvingen voorkomen, samen met hun corresponderende geonameid. Deze informatie wordt gehaald uit het geotree.txt bestand.

4.4.3

Testresultaten

Om het bovenstaande systeem uit te testen, werden een aantal willekeurige semantische query’s uitgevoerd. Tabel 4.12 toont de resultaten hiervan. Er werden zes geonames getest (kolom ’geonames’), telkens in combinatie met een andere term: ’ongeval’, ’moord’, ’festival’ en ’voetbal’. Elke zoekopdracht werd drie keer uitgevoerd: één keer met het bovenstaande systeem, dat de geoname omzet naar een geotagger waarde, en twee keer met de klassieke zoekmachine. Bij de eerste test met de klassieke zoekmachine werden de resultaten beperkt tot degene waarbij de geoname in het MediaObjectFragmentScriptDescription veld voorkomt. De tweede keer werden geen beperkingen opgelegd, en mocht de geoname in om het even welk veld voorkomen. Het aantal resultaten voor elk van de drie uitvoeringen bevinden zich respectievelijk in de kolommen ’g’ (geotagger), ’b’ (beschrijving) en ’a’ (alles). Geonames die geen land, admin1 of admin2 gebied voorstellen (in deze tests ’gent’ en ’parijs’),


87

Tabel 4.12: Aantal resultaten voor geteste query’s (1)

ongeval geoname gent

g

b

moord a

g

b

festival a

g

b

voetbal a

g

b

a

431

431

587

150

150

276

150

150

587

293

293

587

oost-vlaanderen

2.259

106

179

949

40

43

314

0

0

1.210

5

179

belgie

7.943

216

6.835

3.755

131

3.385

1.413

28

2.294

4.786

367

6.835

parijs

142

142

205

48

48

56

36

36

230

40

40

205

46

6

9

62

2

4

32

1

1

44

1

9

7.955

68

107

5.022

21

51

1.545

4

37

2.946

68

107

ivoorkust turkije

hebben steeds hetzelfde aantal resultaten voor de eerst twee uitvoeringen (kolommen ’g’ en ’b’). Dit is logisch, aangezien deze steeds expliciet in de beschrijvingen aanwezig zijn. Geonames die wél een hogerliggend gebieden voorstellen (’oost-vlaanderen’, ’belgie’, ’ivoorkust’ en ’turkije’), hebben steeds een grotere waarde voor de eerste uitvoering, dan voor de tweede. Deze geonames zijn namelijk als hogerliggend gebied toegevoegd aan het geotagger veld, en zijn niet bij alle beschrijvingen expliciet aanwezig. De waarden uit de ’a’-kolom daarentegen zijn soms kleiner en soms groter dan de waarden uit de ’g’-kolom. Indien de waarde groter is, wijst dit op het feit dat er ook geonames zijn die niet in het MediaObjectFragmentScriptDescription veld van een BOM-fragment voorkomen, maar wél in een ander veld. De resultaten tonen aan dat de resultset van een zoekopdracht, die een geoname bevat dat een hogerliggend gebied voorstelt, veel groter is bij de uitvoering met het geotagger systeem, dan bij de uitvoering met de klassieke zoekmachine. Zo worden er voor de zoekopdracht ’+ongeval +oost-vlaanderen’ 2.259 resultaten gevonden wanneer het geotagger systeem wordt gebruikt, en slechts 179 wanneer de klassieke zoekmachine wordt gehanteerd.

De zoekopdracht ’+festival

+oost-vlaanderen’ levert zelfs geen enkel resultaat op met het oude systeem, terwijl het nieuwe systeem 314 resultaten oplevert. Niet alle getoonde resultaten die met het nieuwe systeem worden bereikt, zijn echter ook relevant. Dit geldt vooral voor vreemde regio’s: de zoekopdracht ’+moord +turkije’ levert bijvoorbeeld bijna 240 keer meer resultaten op met het nieuwe systeem, dan met het oude. Ook de query’s met de geoname ’ivoorkust’, zullen veel irrelevante resultaten opleveren. Waarschijnlijk ligt er in Turkije en Ivoorkust minstens één plaatsnaam die wel in de Geonames database voorkomt, maar die in de BOM-database als een irrelevante geoname wordt beschouwd. Wanneer het verschil tussen de ’g’ en ’a’ waarde groot is, gaat het vaak om woorden die in de Nederlandse taal veel worden gebruikt. Om enkel relevante resultaten te krijgen, zullen de foutieve geonames dus eerst moeten worden verwijderd.


4.5

88

Plaatsnamen binnen een bepaalde straal

4.5.1

Uitbreiding van de semantische query’s

In de vorige paragraaf werd besproken hoe een mechanisme werd ge¨ımplementeerd, waarmee semantische query’s kunnen worden uitgevoerd, die op zoek gaan naar alle gebeurtenissen die zich afspeelden in een bepaalde regio. Dit mechanisme kan nog verder worden uitgebreid. Zo zou een gebruiker op zoek kunnen gaan naar bepaalde gebeurtenissen, die zich afspeelden binnen een straal van x kilometer rond een plaatsnaam y. In deze paragraaf wordt deze uitbreiding verder besproken. Om dergelijke semantische query’s te kunnen uitvoeren, is er ten eerste een methode nodig om de afstand te bepalen tussen twee plaatsnamen. Daarnaast is er ook nood aan een efficiënte manier om kandidaat-plaatsnamen te vinden. Indien voor elke mogelijke BOM-geoname de afstand zou moeten worden berekend ten opzichte van plaatsnaam y, zou dit onnodig veel werk opleveren. De volgende subparagrafen gaan verder in op deze problematiek. Het uiteindelijke systeem moet er terug voor zorgen dat de gebruiker semantische clausules kan ingeven.

Dit keer moeten niet de onderliggende gebieden worden opgezocht, maar wel alle

plaatsnamen die binnen een straal van x kilometer rond een plaats y liggen.

4.5.2

Kortste Afstand

De kortste afstand tussen twee plaatsen op aarde kan op verschillende manieren worden berekend. Elke formule verwacht steeds als invoer de geografische coördinaten van beide plaatsen. Deze coördinaten kunnen worden uitgedrukt in een noorder- (NB) of zuiderbreedte (ZB), en een ooster(OL) of westerlengte (WL), uitgedrukt in graden (◦ ). Dit wordt ge¨ıllustreerd op figuur 4.3. Er wordt ook gesproken van latitude (breedte) en longitude (lengte). Om berekeningen uit te voeren, worden de co¨ ordinaten steeds omgezet naar decimale getallen. Hierbij worden noorderbreedte en oosterlengte als positief beschouwd, zuiderbreedte en westerlengte als negatief. Aangezien de aarde niet perfect bolvormig is, varieert de aardstraal van 6.357 tot 6.378 kilometer. Er worden dan ook verschillende modelleringen voor de aarde gebruikt: ze kan als een bol, een ellipso¨ıde of een sfero¨ıde6 worden beschouwd. Elke methode die de afstand berekent tussen twee plaatsen, gebruikt één van deze modellen. Deze methoden zijn echter allen onstabiel voor antipodale plaatsen7 . Dit laatste geval komt in de praktijk zelden voor. Een methode die rekening houdt met de afplatting van de aarde, is de methode van Vincenty (Vincenty, 1975). Deze methode vereist echter veel rekenwerk. Daarom wordt voor de toepassing de grootcirkelmethode gebruikt. Doordat deze methode de aarde als een bol beschouwd, wordt de 6

Een sfero¨ıde is een ellipso¨ıde waarvan twee stralen gelijk zijn. Als de twee gelijke stralen groter/kleiner zijn dan

de derde, wordt er gesproken van een oblate/prolate sfero¨ıde. De aarde wordt soms beschouwd als een oblate sfero¨ıde. 7 Twee punten zijn antipodaal als de rechte die hen verbindt door het middelpunt van de aarde gaat. Beide punten liggen dan diametraal tegenover elkaar. Door dergelijke plaatsen gaan oneindig veel grootcirkels.


89

Figuur 4.3: Coördinatenstelsel van de aarde

afplatting van de aarde niet in rekening gebracht, en worden er bijgevolg afrondingsfouten gemaakt. Toch blijkt de methode tot op 0,55 procent nauwkeurig te zijn. Voor deze toepassing is dit zeker voldoende. Grootcirkelmethode De grootcirkelmethode biedt een eenvoudige manier om de kortste afstand tussen twee gegeven punten te berekenen, door gebruik te maken van grootcirkels. Een grootcirkel is een cirkel op een boloppervlak met volgende eigenschappen: • De cirkel verdeelt het boloppervlak in twee gelijke delen. • De straal van de cirkel en de bol zijn gelijk. • Het middelpunt van de cirkel is gelijk aan dat van de bol. • De kortste weg tussen twee punten, gemeten over de bol, is deel van een grootcirkel. Door twee gegeven plaatsen gaat steeds één grootcirkel, behalve als de plaatsen antipodaal zijn. Door de twee plaatsen wordt de grootcirkel in twee stukken opgedeeld. De cirkelboog met de kortste lengte (ook orthodroom genoemd), is meteen ook de kortste afstand tussen de twee plaatsen (Wojciulewitsch, 1988). Figuur 4.4 toont een grootcirkel G en een breedtecirkel B op een bol. Hierbij is duidelijk dat geen enkele breedtecirkel, behalve de evenaar, een grootcirkel is. Als de afstand moet worden berekend tussen bijvoorbeeld de steden Anchorage en Petrograd, lijkt het vanop een mercatorkaart alsof deze via de breedtecirkel moet worden berekend. Bekeken vanop een wereldbol, wordt het echter duidelijk dat de afstand via de grootcirkel korter is (zie figuur 4.5).


90

Figuur 4.4: Voorbeeld van een grootcirkel op een bol (Frassek, 2006)

Figuur 4.5: Afstand tussen twee steden: links gezien vanop een wereldbol (Wojciulewitsch, 1988), rechts vanop een mercatorkaart.

Om de afstand te berekenen, worden eerst de polaire coördinaten van de vertrekplaats (i=0), respectievelijk de aankomstplaats (i=1) omgezet naar de overeenkomstige cartesische coördinaten ri (zie figuur 4.6). Alle berekeningen worden uitgevoerd in radialen (Weisstein, 1999):   cos λi cos δi    ri =  sin λ cos δ i i   sin δi Hierbij staat λ voor de lengte, en δ voor de breedte. Vervolgens wordt de hoek tussen beide punten berekend, gezien vanuit het middelpunt van de aarde, door middel van het scalair product:


91

cos θ = r1 · r2 = cos δ1 cos δ2 (sin λ1 sin λ2 + cos λ1 cos λ2 ) + sin δ1 sin δ2 = cos δ1 cos δ2 cos(λ1 − λ2 ) + sin δ1 sin δ2 De grootcirkel afstand d wordt dan berekend als volgt: d = a cos−1 [cos δ1 cos δ2 (cos λ1 − λ2 ) + sin δ1 sin δ2 ] Hierbij is a gelijk aan de gemiddelde aardstraal. Als waarde hiervoor wordt 6370 kilometer genomen.

Figuur 4.6: Omrekening van polaire naar cartesische coördinaten voor een punt P1 , waarbij r1 = (x1 , y1 , z1 ) (Frassek, 2006)

4.5.3

Bepaling van de plaatsen

Om de semantische query’s te kunnen uitvoeren, moeten alle plaatsen worden gezocht, die ook in de BOM-database voorkomen, en die zich binnen een straal van x kilometer rond een plaats y bevinden. Om die plaatsen te vinden, zouden alle BOM-geonames één voor één kunnen worden overlopen. Voor elke geoname kan met behulp van de grootcirkelmethode de afstand worden berekend tussen deze plaats en de plaats y. De meeste plaatsen zullen echter niet binnen de gewenste straal x liggen, zeker niet voor kleine afstanden. Op deze manier zullen dan ook onnodig veel afstanden worden berekend. Het is evenmin handig om de coördinaten van elk puntje op de cirkellijn te gaan bijhouden, en alle co¨ ordinaten van de BOM-geonames te gaan afwegen bij de cirkelllijn. Daarom is ervoor gekozen om eerst alle plaatsen te selecteren die binnen een vierkant liggen, waarvan de zijde gelijk is aan de diameter van de cirkel, zodanig dat de cirkel er precies inpast.


92

Dit wordt ge¨ıllustreerd in figuur 4.7. Als plaats y wordt hier Gent (51,050 latitude - 3,717 longitude) gekozen. Deze wordt geplaatst op het middelpunt van de cirkel. Alle plaatsen die zich op niet meer dan twintig kilometer (de gegeven straal x) van het middelpunt y bevinden, liggen binnen de cirkel, en dus ook zeker binnen het vierkant. Nu kunnen de coördinaten die op de hoekpunten van het vierkant liggen, gemakkelijk worden berekend. Hiervoor moet de waarde van de straal x (in kilometers) worden geconverteerd naar graden. Eén graad is minimum 110, 57 en maximum 111, 69 kilometer, naargelang de plaats op aarde. Indien echter het minimum gekozen wordt voor de omzetting, is het zeker dat alle plaatsen die binnen het vierkant liggen, zullen worden gedetecteerd. Naargelang het hoekpunt kan de bekomen waarde van de straal bij de longitude/latitude worden opgeteld of afgetrokken. De co¨ ordinaten van alle punten die binnen het vierkant vallen, worden daarna gebruikt in de grootcirkelmethode, samen met de coördinaten van plaats y. De afstanden groter dan straal x, kunnen op deze manier worden geëlimineerd. Nu is er nog een mechanisme nodig om op een efficiënte manier alle punten te bepalen die zich binnen de rechthoek bevinden. In het voorbeeld moeten alle plaatsen dus een latitude hebben die zich tussen de waarden 50,86912 en 51,23008 bevindt. De longitude moet liggen tussen de waarden 3,53612 en 3,89788. Hoe deze plaatsen worden bepaald, wordt besproken in paragraaf 4.5.3.1.

Figuur 4.7: Bepaling van de minimum en maximum afstanden

4.5.3.1

K-d tree

Elke plaats die zich binnen de berekende rechthoek bevindt, voldoet aan het volgende criterium: ze ligt tussen een minimum en maximum opgegeven lengte en breedte. Er is dus nood aan een gegevensstructuur die toelaat om efficiënt te zoeken in een bereik van twee sleutels: de latitude en


93

longitude. Een gegevensstructuur die hiervoor kan worden gebruikt, is de k-d tree (k-dimensionele boom). Dit is een binaire boom die het mogelijk maakt om meerdimensionale gegevens op te slaan en te zoeken naar alle punten in een meerdimensionale hyperrechthoek (hier steeds een vierkant). In deze toepassing is k=2, aangezien er op twee sleutels moet worden gezocht: de x-coördinaat stelt de longitude voor, de y-co¨ ordinaat de latitude. Elke inwendige knoop is een k-dimensionaal punt, dat de zoekruimte verdeelt in twee subruimtes. De manier waarop deze opgesplitst wordt, is afhankelijk van de splitdimensie d. In elke knoop kan worden beslist welke dimensie wordt gebruikt. Het linkerkind (rechterkind) van een knoop representeert dan de hyperrechthoek die alle punten bevat waarvan de d-coördinaat kleiner (groter) is dan de d-co¨ ordinaat van de ouderknoop. Deze opdeling gaat door totdat elk gebied slechts één punt bevat. Dit is ge¨ıllustreerd in figuur 4.8.

Figuur 4.8: K-d tree: links de opdeling van de zoekruimte, rechts de bijhorende binaire boom (Kdtree, 2006).

De gemiddelde performantie voor een random opgebouwde boom bedraagt O(r + nα ), waarbij √

α=

17−3 . 2

Er bestaan nog andere gegevensstructuren die kunnen zoeken in een hyperrechthoek

(bijvoorbeeld de quadtree), maar de k-d tree is de enige die slechts O(n) geheugenruimte vereist (waarbij n staat voor het aantal punten). De minimum-/maximumwaarde voor de x-coördinaat is -180/180, en -90/90 voor de y-coördinaat. Dit vormt soms een probleem, bijvoorbeeld wanneer alle steden moeten worden gevonden die binnen een straal van 500 kilometer (= 4,52202◦ ) rond een punt P (177, 60) liggen. De rechtse hoekpunten van de rechthoek -in dit geval steeds een vierkant- zullen namelijk als x-coördinaat een waarde boven 180 krijgen (want 177 + 4, 52202 = 181, 52202). Aangezien de aarde 360 graden telt, mag bij


94

de waarde (181,52202) 360 graden worden afgetrokken, zonder dat dit gevolgen heeft. Het resultaat levert dan wel een geldige co¨ ordinaat op (-178,47798). De x-coördinaat van het rechterhoekpunt (172,47798) is nu echter groter dan die van het linkerhoekpunt (-178,47798). Wanneer de punten op deze manier aan de k-d tree worden meegegeven, levert dit een fout op. De zoekruimte moet dus worden opgesplitst in twee rechthoeken, waarbij de hoekpunten wel juist gelegen zijn. Voor de eerste rechthoek levert dit het rechterhoekpunt R1(64, 52202; 172, 47798) op, en het linkerhoekpunt L1(55, 477978; 180).

De tweede rechthoek heeft dan de punten

R2(64, 52202; −180) en L2(55, 477978; −178, 47798). In het algemeen moet de zoekruimte soms worden opgedeeld in twee of vier rechthoeken, naargelang ofwel de lengte of breedte wordt overschreden, ofwel allebei. Figuur 4.9 illustreert de verschillende mogelijkheden: op de linkerbovenfiguur wordt er geen enkele waarde overschreden, en volstaat één zoekruimte. De rechterboven- en linkeronderfiguur overschrijden respectievelijk de breedte en lengte. Het vierkant moet hierdoor worden opgedeeld in twee rechthoeken. Indien allebei de waarden worden overschreden, is een opdeling in vier rechthoeken nodig.

Figuur 4.9: Opdeling van de zoekruimtes


4.5.4

95

Visualisatie van de resultaten: Google Maps

Met behulp van bovenstaand systeem kan de gebruiker op zoek gaan naar gebeurtenissen die zich afspeelden binnen een bepaalde straal rond een bepaalde plaats. Om het systeem te kunnen testen, wordt opnieuw een servlet voorzien met een zoekbox. De gebruiker kan een semantische clausule opgeven door de gewenste plaats tussen vierkante haken te specificeren. Nu moet deze plaats ook worden gevolgd door de gewenste straal (in kilometer). Vervolgens moet de zoekopdracht worden vertaald, zodat deze kan worden doorgegeven aan de klassieke zoekmachine. De vertaling is echter niet evident: de query zou kunnen worden vertaald naar een disjunctieve (of-) uitdrukking, die bestaat uit alle geonameids die door het afstandssysteem worden gevonden. Indien er weinig plaatsen aan de zoekopdracht voldoen, is dit systeem bruikbaar. Wanneer er veel plaatsen worden gevonden, treedt er echter een probleem op: er kunnen namelijk maximum 1024 expressies worden doorgestuurd naar de klassieke zoekmachine. Daarom is een andere manier bedacht om de resultaten van de zoekopdracht aan de gebruiker te tonen: er is voor gezorgd dat de gebruiker eerst alle BOM-geonames te zien krijgt, rond de gevraagde plaats, waar de gebeurtenis effectief is opgetreden. Deze plaatsen worden gevisualiseerd door middel van Google Maps (Google Maps API , 2009). Dit is een dienst van Google, die het mogelijk maakt om geografische locaties op een kaart aan te duiden. Deze dienst is bovendien gemakkelijk integreerbaar op websites, met behulp van de Google Maps API. Elke gevonden plaats wordt op de kaart aangeduid met een marker. Wanneer op een marker wordt geklikt, verschijnt een tekstballon. In deze ballon wordt het aantal gevonden zoekresultaten voor de aangeduide plaats, samen met een link, weergegeven. Deze link verwijst naar de eerste antwoordpagina, die wordt gegenereerd door de klassieke zoekmachine, en die de zoekresultaten voor de aangeklikte plaats bevat. Als voorbeeld wordt in figuur 4.10 de gegenereerde map getoond voor de semantische clausule ’+moord +[gent 20]’.

Figuur 4.10: Google Maps kaart voor zoekopdracht ’+moord +[gent 20]’

Wanneer bijvoorbeeld op de plaats ’Destelbergen’ wordt geklikt, verschijnt een tekstballon die


96

aanduidt dat er 7 zoekresultaten (hits) zijn gevonden voor ’moord’ en ’Destelbergen’ (zie figuur 4.11). Bij een klik op de link, wordt de antwoordpagina getoond zoals te zien is in figuur 4.12. Hierbij is ’Destelbergen’ omgezet naar de bijhorende geonameid. De vertaalde zoekopdracht ziet er dan uit als volgt: ’+moord +geotagger:2799496’.

Figuur 4.11: Tekstballon die hoort bij plaats ’Destelbergen’

Figuur 4.12: Eerste antwoordpagina voor de vertaalde zoekopdracht ’+moord +[gent 20]’


4.5.5

97

Implementatie

Er worden opnieuw enkele klassen ge¨ımplementeerd, om semantische query’s te kunnen uitvoeren. Hieronder worden deze klassen kort toegelicht: DistanceMethods - De afstand tussen twee plaatsen kan worden berekend met behulp van de klasse DistanceMethods. Deze voorziet een statische methode greatCircle(double[] from, double[] to) en berekent, zoals de naam reeds aanduidt, de afstand tussen twee plaatsen, aan de hand van de grootcirkelmethode. De co¨ ordinaten van de twee plaatsen worden als parameters meegegeven. De implementatie ziet er als volgt uit:

public static

f i n a l d o u b l e EARTHRADIUS = 6 3 7 0 ;

p u b l i c s t a t i c d o u b l e greatCircle ( d o u b l e [ ] from , d o u b l e [ ] to ) { d o u b l e lat1 = Math . toRadians ( from [ 0 ] ) ; d o u b l e long1 = Math . toRadians ( from [ 1 ] ) ; d o u b l e lat2 = Math . toRadians ( to [ 0 ] ) ; d o u b l e long2 = Math . toRadians ( to [ 1 ] ) ; d o u b l e alfa = ( Math . cos ( lat1 ) ∗ Math . cos ( lat2 ) ∗ Math . cos ( long2 − long1 ) + Math . sin ( lat1 ) ∗ Math . sin ( lat2 ) ) ; r e t u r n ( Math . acos ( alfa ) ∗ EARTHRADIUS ) ; }

GeoKeyword - Deze klasse houdt de nodige informatie bij over één geoname. Volgende attributen worden hierin bijgehouden:

p r i v a t e i n t geonameid ; p r i v a t e String asciiname ; p r i v a t e String [ ] alter natenam es ; p r i v a t e f l o a t latitude ; p r i v a t e f l o a t longitude ;

Deze attributen worden gebruikt door de volgende klasse: NearestPlaces - De eigenlijke bepaling van alle geonames die zich binnen een bepaalde straal x ten opzichte van een plaats y bevinden, gebeurt door de klasse NearestPlaces. De constructor verwacht twee parameters: als eerste wordt de naam van het tekstindexbestand meegegeven, dat door de GeoTree klasse werd aangemaakt. Zo kunnen de latitude en longitude van elke mogelijke BOM-geoname worden opgehaald uit het allCountries.txt bestand.

De naam van dit laatste

bestand wordt als tweede parameter meegegeven. Vervolgens roept de constructor de private methode loadKdTree(String tekstindexbestand, String allCountries) aan. Deze zorgt ervoor dat alle BOM-geonames in een k-d tree worden opgeslagen. Voor de opbouw van de k-d tree wordt gebruikgemaakt van een reeds bestaande implementatie (Savarese, 2006). Deze bevat een klasse KdTree, waarmee de gelijknamige boom kan worden


98

opgesteld. Door middel van de methode put(Point, Object) wordt elke BOM-geoname in deze k-d tree opgeslagen. Als sleutel wordt een GenericPoint meegegeven, dat de latitude en longitude van de geoname bevat. Als waarde wordt een object van het type GeoKeyword meegegeven, dat alle nodige informatie over de geoname bijhoudt. Zo kan later gemakkelijk de plaatsnaam of geonameid worden weergegeven, dat bij een bepaald coördinatenpaar hoort. De informatie over de geonames die moet worden opgeslagen, is te vinden in het allCountries.txt bestand. Elke regel die gespecifieerd staat in het tekstindexbestand wordt ingelezen en de bijhorende gegevens worden opgeslagen in een GeoKeyword object. Dit wordt dan toegevoegd aan de k-d tree. Alle GeoKeywords worden ook nog eens opgeslagen in een hashmap. Om alle geonames te vinden die aan de specificatie voldoen (de geoname bevindt zich binnen een straal van x kilometer rond plaats y), kan de methode getNearest(double latitude, double longitude, double radius) van de klasse NearestPlaces worden gebruikt. Hierbij wordt plaats y gespecifieerd door de eerste twee parameters, straal x door de laatste parameter. Als waarde geeft deze een ArrayList van GeoKeywords terug, die voldoen aan de specificatie. De implementatie van deze methode ziet er als volgt uit:

p u b l i c ArrayList getNearest ( d o u b l e latitude , d o u b l e longitude , d o u b l e radius ) { ArrayList list = new ArrayList() ; // 1 graad = t u s s e n 1 1 0 . 5 7 en 1 1 1 . 6 9 km, a f h a n k e l i j k van l a t i t u d e −> min . nemen d o u b l e radiusDeg = radius / 1 1 0 . 5 7 ; d o u b l e north = latitude + radiusDeg ; d o u b l e west = longitude − radiusDeg ; d o u b l e south = latitude − radiusDeg ; d o u b l e east = longitude + radiusDeg ; List l = getRectangles ( north , west , south , east ) ; d o u b l e [ ] from = { latitude , longitude } ; Iterator it = l . iterator ( ) ; w h i l e ( it . hasNext ( ) ) { GeoKeyword geo = it . next ( ) ; d o u b l e [ ] to = { geo . getLatitude ( ) , geo . getLongitude ( ) } ; d o u b l e distance = D is ta nc e Me th od s . greatCircle ( from , to ) ; i f ( distance <= radius ) list . add ( geo ) ; } r e t u r n list ; }

Eerst worden de vier hoekpunten berekend, zoals ge¨ıllustreerd in figuur 4.7. Hierna worden met behulp van de methode getRectangleKeywords(double north, double west, double south, double east) alle GeoKeywords bepaald, die binnen het vierkant vallen. Indien nodig, wordt de rechthoek eerst opgesplitst in meerdere rechthoeken, zoals ge¨ıllustreerd in figuur 4.9. Deze rechthoeken corresponderen dan met de zoekruimtes, die worden doorgegeven aan de k-d tree. Deze k-d tree geeft alle punten terug, die binnen een bepaalde zoekruimte vallen:


99

List list = new ArrayList() ; f o r ( i n t i =0; i> it = kdTree . iterator ( new GenericPoint ( westList [ i ] , southList [ i ] ) , new GenericPoint ( eastList [ i ] , northList [ i ] ) ) ; w h i l e ( it . hasNext ( ) ) list . add ( it . next ( ) . getValue ( ) ) ; }

In de lijsten westList, southList, eastList en northList worden de hoekpunten bijgehouden van elke zoekruimte. De volledige implementatie van de getRectangleKeywords methode is terug te vinden in bijlage C. Tot slot wordt voor elke gevonden geoname die binnen het vierkant ligt, de afstand berekend tot de meegegeven plaats, met behulp van de greatCircle(double[] from, double[] to) methode van de DistanceMethods klasse. Indien deze afstand kleiner is dan de opgegeven afstand (parameter radius), wordt het GeoKeyword aan een lijst toegevoegd. Deze lijst is meteen ook de returnwaarde van de getNearest methode en bevat alle gezochte geonames. Om de servlet te implementeren, wordt de klasse DistanceServlet voorzien: DistanceServlet - Net zoals bij GeoServlet maakt deze klasse een servlet met een zoekbox aan, waarmee de gebruiker semantische clausules kan uitvoeren. Opnieuw is de klasse afgeleid van AbstractSimpleServlet, die de hoofding van de te genereren HTML-pagina voorziet. De constructor verwacht twee parameters: de naam van het bestand waarin alle BOM-geonames, samen met hun corresponderende geonameids staan, en de naam van het allCountries.txt bestand. Deze parameters worden doorgegeven aan een object van de klasse NearestPlaces, die voor de bepaling van de geonames zorgt. De klasse voorziet opnieuw een doGet(HttpServletRequest, HttpServletResponse) methode, die ofwel een zoekbox genereert, ofwel de ingegeven semantische clausule verwerkt. In het laatste geval wordt opnieuw gekeken of er een expressie tussen vierkante haken voorkomt. Indien dit het geval is, wordt uit de expressie de plaatsnaam en de straal geparset. Vervolgens wordt de getNearest(double latitude, double longitude, double radius) methode van het NearestPlaces object opgeroepen. Omdat de latitude en longitude van de opgegeven plaatsnaam niet gekend is, worden deze opgezocht aan de hand van de hashmap die de NearestPlaces klasse bijhoudt. Deze geeft voor een bepaalde plaatsnaam het bijhorend GeoKeyword terug, waarin de geografische coördinaten zijn gespecificeerd. Omdat de Google Maps kaart enkel de plaatsen moet aanduiden die ten minste één zoekresultaat opleveren voor de volledige zoekopdracht, moet er voor elke gevonden plaatsnaam een HTTP-request worden gestuurd naar de klassieke zoekmachine. De zoekstring van deze request bestaat uit de ingegeven zoekopdracht, zonder de expressie tussen vierkante haken, maar met de geonameid van de gevonden plaatsnaam.


100

Wanneer bijvoorbeeld zoals in figuur 4.10 naar de resultaten voor de zoekopdracht ’+moord +[gent 20]’ wordt gezocht, moeten eerst 124 requests naar de klassieke zoekmachine worden verstuurd: de getNearest methode levert namelijk 124 plaatsnamen op voor de plaatsnaam ’Gent’ met als radius twintig kilometer. De HTTP-response genereert opnieuw het totaal aantal zoekresultaten, samen met de details van de eerste tien resultaten. Enkel het aantal resultaten is hier van belang. Dit wordt uit het antwoord geparset. Hiervoor wordt een SAXController en SAXHandler voorzien, net zoals bij de implementatie van de tag cloud (zie paragraaf 1.3.2). De SAXController klasse is voorzien van de methode parseDistanceInfo(String zoekstring, HashMap map), die de HTTP-request uitvoert voor elke geoname uit de meegegeven hashmap. Van zodra het aantal resultaten uit de HTTP-response geparset is, werpt de SAXHandler een SAXException op. Zo wordt de rest van de response niet verder bekeken, en kan er meteen worden doorgegaan met de volgende request. Alle aantallen komen terecht in de hashmap, bij het overeenkomstige GeoKeyword. Daarna

kan

het

DistanceServlet

object

de

opgevulde

hashmap

doorgeven

aan

de

writeGoogleMap(String zoekstring, char ch, GeoKeyword gk, HashMap map, PrintWriter writer) methode.

Deze zorgt ervoor dat de Google Maps kaart wordt

aangemaakt. De eerste twee meegegeven parameters zorgen ervoor dat de juiste links kunnen worden ingesteld. (De char duidt aan of er een ’+’ of ’-’ voor de expressie tussen vierkante haken stond). Voor elke geoname uit de hashmap wordt een Google Maps marker aangemaakt, waarna het resultaat wordt weggeschreven met behulp van de writer. De Google Maps API is geschreven in JavaScript. Alvorens de API te kunnen gebruiken, moet er een API key worden aangevraagd. De API en de verkregen key kunnen als volgt worden gebruikt in JavaScript:

< s c r i p t s r c=” h t t p : / / maps . g o o g l e . com/maps? f i l e =a p i& ; v=2& ; key=w aar de ke y ” t y p e=” t e x t / j a v a s c r i p t ”> < s c r i p t t y p e=” t e x t / j a v a s c r i p t ”>

De laatste coderegel duidt aan dat het eigenlijke script hierna begint. In het script wordt als eerste een methode voorzien die voor een opgegeven punt (gespecificeerd door een latitude en longitude), een marker toevoegt aan de kaart. Wanneer een click-event optreedt, wordt een tekstballon getoond, die de hyperlink van de zoekresultaten voor de aangeklikte plaats bevat.

function createMarker ( point , link ) { var marker = new GMarker ( point ) ; GEvent . addListener ( marker , ” c l i c k ” , function ( ) { marker . o p e n I n f o W i n d o w H t m l ( link ) ; }) ; return marker ; }


101

Als tweede bevat het script een initialize methode, die alle plaatsen initialiseert op de kaart:

function initialize ( ) { if ( G B r o w s e r I s C o m p a t i b l e ( ) ) { var map = new GMap2 ( document . getEl ementBy Id ( ” map canvas ” ) ) ; map . setCenter ( new GLatLng ( 5 1 . 0 5 , 3 . 7 1 6 6 6 6 7 ) , 1 0 ) ; var point = new GLatLng ( 5 1 . 1 3 3 3 3 5 , 3 . 6 8 3 3 3 3 4 ) ; var marker = createMarker ( point , ’ + moord s l e i d i n g e ( 8 h i t s ) ’) ; map . addOverlay ( marker ) ; v a r p o i n t = new GLatLng ( 5 1 . 1 , 3 . 8 3 3 3 3 3 3 ) ; v a r marker = c r e a t e M a r k e r ( p o i n t , ’ < a h r e f=” h t t p : / / . . .>+moord lochristi ( 1 hits ) ’ ) ; map . addOverlay ( marker ) ; ... } }

De GMap2 klasse zorgt voor de eigenlijke kaart. Met behulp van de setCenter methode wordt het centrum van de kaart gespecificeerd. Deze methode verwacht zowel een GLatLng coördinaat, als de gewenste zoom level. In dit voorbeeld staat het centrum ingesteld op de plaats ’Gent’ (51,05 latitude; 3,7166667 longitude). Vervolgens wordt een punt van het type GLatLng aangemaakt, voor elke plaats die zich rond het centrum bevindt, en die minstens één zoekresultaat oplevert. De methode createMarker maakt de marker aan, die vervolgens aan de addOverlay methode wordt doorgegeven. Deze laatste zorgt ervoor dat de marker aan de kaart wordt toegevoegd, en dat deze meebeweegt wanneer de kaart wordt verschoven. Zo blijft een marker steeds bij de opgegeven plaatsnaam staan. De initialize methode wordt uitgevoerd wanneer de HTML-pagina wordt geladen. Dit gebeurt in het body element:

4.5.6

Testresultaten

Om het bovenstaande systeem uit te testen, werden net als bij het voorgaande systeem uit paragraaf 4.4, een aantal semantische query’s uitgevoerd. Het resultaat van elke zoekopdracht werd, zoals hierboven besproken, gevisualiseerd met behulp van Google Maps. Tabel 4.13 toont de resultaten van deze tests. Elke zoekopdracht bestaat uit één of meerdere termen, gevolgd door een semantische clausule tussen vierkante haken. Deze clausule bevat telkens een plaatsnaam, gevolgd door een afstand, uitgedrukt in kilometer. Voor de eerste zoekopdracht werd bijvoorbeeld gezocht naar alle moorden binnen een straal van 100 kilometer rond Gent. De kolom ’#plaatsen (tot)’ geeft het aantal BOM-geonames terug die zich binnen de opgegeven straal


102

en rond de opgegeven plaats bevinden. Er werden bijvoorbeeld 1.443 plaatsnamen gevonden, die op ten hoogste 100 kilometer van Gent liggen. De kolom daarnaast, ’#plaatsen (res)’, geeft het aantal BOM-geonames aan waarvoor effectief zoekresultaten werden gevonden. Voor 395 van de 1.443 plaatsnamen die rond Gent liggen, werden BOM-fragmenten gevonden die ook de term ’moord’ bevatten. Het totaal aantal gevonden BOM-fragmenten wordt weergegeven in de kolom ’#res’. Als laatste wordt in de kolom ’tijd (sec)’ de tijd weergegeven (in seconden) die nodig was om de zoekopdracht te verwerken en de resultaten te visualiseren. Tabel 4.13: Aantal resultaten voor geteste quey’s (2)

zoekopdracht

#plaatsen (tot)

#plaatsen (res)

#res

tijd (sec)

+moord +[gent 100]

1.443

395

12.533

45

+moord +[belgie 100]

1.670

450

16.187

52

221

34

502

7

+nieuws +[brugge 10]

22

21

1.319

1

+nieuws +[rome 50]

15

14

3.511

1

+ongeval +[parijs 100]

159

45

1.196

5

+ongeval +fiets +[gent 25]

200

31

290

9

+ongeval +fiets +[oost vlaanderen 25]

212

37

321

10

+moord +[ivoorkust 500]

Net zoals bij het vorige systeem, bevat de resultset van bepaalde zoekopdrachten terug irrelevante BOM-fragmenten, omwille van de foutief ge¨ınterpreteerde geonames die zijn opgenomen. Zo werden er voor de zoekopdracht ’nieuws +[rome 50]’ veertien plaatsnamen gevonden die elk minstens één resultaat opleverden. Drie van deze plaatsnamen zijn echter irrelevant: ’axa’ (een bank), ’e 42’ (een autosnelweg) en ’colonna’ (een achternaam). De overige werden wel correct ge¨ınterpreteerd: er werden onder andere resultaten voor ’vaticaanstad’, ’ostia’, ’castel gandolfo’ en ’valmontone’ opgenomen. In de semantische clausule kunnen ook plaatsnamen worden opgenomen die regio’s (provincies, landen, . . . ) voorstellen. Deze zoekopdrachten zijn echter minder interessant om uit te voeren. Bij één van de tests werd er bijvoorbeeld op zoek gegaan naar fragmenten die gaan over moorden die zijn gebeurd op hoogstens 100 kilometer van België. Hierbij is het de bedoeling dat naast de plaatsnamen, die hoogstens 100 kilometer buiten België gelegen zijn, ook alle gemeenten uit België in aanmerking komen om in het resultaat te worden opgenomen. Deze zoekopdracht leverde echter maar 1.670 kandidaat plaatsnamen op, terwijl dezelfde zoekopdracht met het deelgebied Gent slechts 227 minder plaatsnamen opleverde. Ook voor de provincie Oost-Vlaanderen werden maar een beperkt aantal gebieden gevonden, die binnen de opgegeven straal liggen. De oorzaak hiervan is dat regio’s, net als alle andere plaatsnamen, worden voorgesteld door één enkel coördinatenpaar. Dit komt vaak met het centrum van een regio overeen: zo ligt de provincie Oost-Vlaanderen op 51 graden noorderbreedte en 3,4575 oosterlengte. De Oost-Vlaamse gemeente Merelbeke heeft net dezelfde coördinaten. Dit wordt getoond op figuur 4.13.


103

Figuur 4.13: Naburige gemeenten voor ’oost vlaanderen’

Dit soort semantische query’s kunnen dus het best worden uitgevoerd met plaatsnamen die geen regio’s voorstellen. Indien toch regio’s worden opgenomen, kan eventueel een voldoende grote afstand worden meegegeven, zodat alle onderliggende gebieden toch worden opgenomen in het resultaat. Echter, hoe groter de meegegeven afstand voor een bepaalde geoname, hoe langer het duurt om de google map te genereren. Voor elke naburige geoname moet namelijk een HTTP-request worden verstuurd, om het aantal resultaten van de zoekopdracht - waarin de naburige plaatsnaam is opgenomen - te achterhalen. Zo duurde het bijvoorbeeld 45 seconden om de google map voor de eerste zoekopdracht te genereren: er moesten dan ook 1.443 HTTP-requests worden verstuurd. Het systeem is dus het meest geschikt voor kleine afstanden. De uitvoeringstijd kan wel nog worden gereduceerd, door de implementatie aan te passen: net als bij de generatie van de tag cloud uit hoofdstuk 1, kan een threadpool mechanisme worden voorzien. Zo kunnen meerdere HTTP-requests tegelijkertijd worden verwerkt.

4.6 4.6.1 4.6.1.1

Evaluatie van geonames: deel 1 Filteren Beslissingsdiagram

De geonames die tot nu toe uit de BOM-beschrijvingen zijn geëxtraheerd, leveren heel wat plaatsnamen op.

Omdat verschillende van deze geonames eigenlijk niet verwijzen naar de

geografische plaats, wordt getracht het resultaat te verbeteren met behulp van enkele filters. Elke geoname wordt na filtering geclassificeerd als een true match (een ’echte’ plaatsnaam) of false match (een ’valse’ plaatsnaam). Het beslissingsdiagram in figuur 4.14 geeft een overzicht van de ge¨ımplementeerde filters: Bij de eerste filter wordt gekeken of de geoname al dan niet met een stopwoord overeenkomt. Woorden zoals ’de’, ’een’, ’over’, ’van’, . . . komen hoogst waarschijnlijk niet met een echte


104

Figuur 4.14: Beslissingsdiagram dat aanduidt of een geoname een true of false match is

plaatsnaam overeen. Indien de plaatsnaam hierin wordt teruggevonden, wordt deze aangeduid als een false match. Zoniet wordt de geoname onderworpen aan een tweede filter. Deze gaat na of de geoname ook een persoonsnaam is. Hierbij wordt ervan uitgegaan dat namen zoals ’jan’ eerder aan een persoon moeten worden gelinkt dan aan een geografische plaats. Indien de geoname inderdaad ook met een persoonsnaam overeenkomt, wordt deze als een false match beschouwd. Een derde filter bepaalt of de geoname al dat niet met een land overeenkomt. Deze geonames kunnen vrijwel zeker als een true match worden beschouwd. De vierde filter is gelijkaardig: deze kijkt of de plaatsnaam een dorp of gemeente in België is. Indien opnieuw niet aan de voorwaarde voldaan is, wordt de vijfde filter toegepast. Deze bepaalt of het woordje, dat v´ o´ or de geoname staat in de bijhorende BOM-beschrijving, een lidwoord is. Indien dit bij minstens vijftien procent van de beschrijvingen het geval is, wordt de plaatsnaam als een false match aanzien. Bij zinnen is de kans namelijk vrij klein dat de plaatsnaam voorafgegaan wordt door een lidwoord: woordgroepen zoals ’de Gent’, ’de België’, . . . komen nooit voor. Er zijn echter uitzonderingen: ’De Haan’, ’De Verenigde Staten’, . . . zijn wel correct Nederlandstalige woordgroepen. Daarom worden enkel de gevonden geonames, bestaande uit één token, aan deze filter onderworpen. Ook andere plaatsnamen komen in bepaalde gevallen toch samen voor met een lidwoord. In twee beschrijvingen komt ’Moskou’ bijvoorbeeld samen voor met het lidwoord ’het’: ’Het Moskou City Ballet’ en ’het Moskou-viaduct’. In alle 674 andere gevallen staat er geen lidwoord voor ’Moskou’.


105

Door een geoname pas als false match te aanschouwen wanneer deze in vijftien procent van de gevallen samen met een lidwoord voorkomt, worden ’Moskou’, en andere geonames, niet verkeerd geklasseerd. Voor de zesde en laatste filter wordt opnieuw beroep gedaan op de BOM-beschrijvingen. Indien een geoname samen voorkomt met één van zijn bovenliggende gebieden in de beschrijving, is de kans op een true match groter. De kans dat de geoname ’Antalya’ duidt op een echte plaats, wordt groter indien bijvoorbeeld in de beschrijving die bij de geoname hoort, ook het overeenkomstig land (’Turkije’) voorkomt. Ook wanneer bijvoorbeeld ’Gent’ samen voorkomt met ’Oost-Vlaanderen’, ’Vlaams Gewest’, of ’België’, kan deze worden aangeduid als een true match. Belgische plaatsnamen zijn in de BOM-beschrijvingen echter vaak niet voorzien van keywords die de hogerliggende gebieden voorstellen. Om Belgische plaatsnamen steeds goed te keuren, werd daarom de vierde filter voorzien. 4.6.1.2

Implementatie

Om de filtering uit te voeren, wordt een nieuwe klasse GeoMatchFilter aangemaakt. De methode filterProcedure() zorgt ervoor dat alle BOM-geonames aan de filterstappen worden onderworpen. De bekomen false en true matches worden voor elke filter weggeschreven naar een apart bestand. De geotree2 matrix wordt gebruikt om alle BOM-geonames te overlopen. Hierbij is elke eerste term uit elk document gelijk aan een BOM-geonameid. De corresponderende geonames wordt uit het geotree.txt bestand gehaald. Omwille van synoniemen kunnen meerdere geonames met één geonameid overeenkomen.

Deze informatie wordt opgeslagen in een map van het type

HashMap>. Met behulp van de geotree2 matrix is het ook gemakkelijk om voor een bepaalde geoname de juiste regel op te halen uit het allCountries.txt bestand, die voor sommige stappen nodig is. Deze informatie zit namelijk vervat in het geotree.ti bestand. De eerste filtermethode die wordt opgeroepen voor elke geoname, is de inList(ArrayList<String> list, String geoname) methode. De methode hoeft enkel via binair zoeken de geoname op te sporen in de meegegeven lijst van stopwoorden. Deze alfabetisch gesorteerde lijst bevat zowel Nederlandse, Engelse, Duitse, als Franse stopwoorden8 , en wordt bij het begin van de filterProcedure() methode ingelezen. Indien de plaatsnaam in deze lijst wordt gevonden, wijst dit op een false match. Alle andere filters worden dan niet meer uitgevoerd. Zoniet wordt verdergegaan met de tweede filter. De uitvoering van de tweede filter gebeurt terug door de methode inList. Nu wordt als parameter een lijst met persoonsnamen meegegeven. Deze lijst werd reeds opgesteld door een begeleider. Waneer de geoname wordt gevonden, levert dit terug een false match op. De methode isCountry(int offset) implementeert de derde filter. Om te weten of de geoname met een land overeenkomt, moet het allCountries.txt bestand worden geraadpleegd. Hierin duidt het feature code veld aan tot welke subcategorie de geoname behoort. Geonames waarbij de waarde 8

Een lijst met stopwoorden is te vinden via http://opac.zebi.nl/webopac/help/stopwoorden.htm.


106

van dit veld gelijk is aan ’PCLI’, zijn landen, en dus true matches. Om dit veld te controleren, moet geweten zijn op welke regel de betreffende geoname voorkomt in het allCountries.txt bestand. Deze informatie wordt gehaald uit het geotree.ti bestand, en wordt meegegeven als parameter. De werking van de vierde filter is gelijkaardig aan de vorige. De methode isBelgianCity(int offset) verwacht terug als invoer de regel uit het allCountries.txt bestand, die overeenkomt met de BOM-geoname. Om te kijken of de geoname een Belgische gemeente is, kan worden gekeken naar het cc2 veld in het allCountries.txt bestand. Indien dit staat ingesteld op ’BE’, wijst dit erop dat de geoname deel uitmaakt van België. De plaatsnamen waarvoor dit geldt, worden terug aangeduid als true match. Om de vijfde filtermethode, isWithArticle(String geoname, int idDe, int idHet, int idEen), te kunnen uitvoeren, moet de eerder aangemaakte bom1token2 matrix worden ingeladen. Dit gebeurt bij het begin van de filterProcedure() methode. De isWithArticle methode verwacht als invoer de te onderzoeken geoname, samen met de term id’s van de lidwoorden ’de’, ’het’ en ’een’, zoals die voorkomen in de bom1token2 matrix. Omdat de bom1tokens2 matrix wordt gebruikt, worden enkel geonames onderzocht die uit één token bestaan. Deze matrix bevat immers alleen enkelvoudige termen. Hierdoor worden plaatsnamen zoals ’De Haan’, ’De Verenigde Staten’, . . . niet verkeerd geklasseerd. Een teller houdt bij in hoeveel bom1token2 documenten de geoname samen voorkomt met een lidwoord. Hiervoor wordt elk document uit de bom1token2 matrix, die de te onderzoeken geoname bevat, overlopen met behulp van het bijhorende indexbestand. Het term id vóór het term id dat overeenkomt met de geoname, wordt dan vergeleken met de drie lidwoord-id’s. Indien dit term id gelijk is aan één van de lidwoord-id’s, wordt de teller verhoogd. De bekomen tellerwaarde wordt dan gedeeld door het totaal aantal documenten waarin de geoname voorkomt. Indien het resultaat van deze deling groter is dan 0,15 wordt de geoname als een false match beschouwd. De

zesde

methode

en

laatste

filter

containsArea(int

die

treeDoc,

kan

worden

String

HashMap> hashmap).

uitgevoerd,

geoname,

int

wordt

voorzien

beginDoc,

int

door

de

endDoc,

Deze methode bepaalt of er in minstens

één van de bomGeoWordsAll2 beschrijvingen, die de geoname bevat, ook een corresponderend bovenliggend gebied voorkomt.

Dit kan zowel de bijhorende provincie (veld admin3 ), het

bijhorende gewest (veld admin2 ) of land (veld cc2 ) zijn. Deze drie gebieden worden gehaald uit het document van de geotree2 matrix, dat overeenkomt met de te behandelen geoname (parameter treeDoc). De parameters beginDoc en endDoc geven respectievelijk de plaats aan van de eerste en laatste term uit het document. Via het geotree2 woordenboek worden de geonameids die bij de tweede, derde en vierde term horen, opgezocht. Dit zijn de geonameids van de bovenliggende gebieden.

Alle namen die overeenkomen met


107

deze geonameid, en die in de BOM-beschrijvingen voorkomen, kunnen worden opgezocht in de meegegeven hashmap. Voor elke naam worden alle bomGeoWordsAll2 documenten opgehaald die de naam bevatten. Van zodra in één van deze documenten ook de te onderzoeken geoname voorkomt, levert dit een true match op en stopt het zoeken. Indien geen enkele naam samen voorkomt met de geoname, wordt deze laatste als een false match aangeduid.

4.6.2

Vergelijking met keywords

Om de gevonden geonames te controleren, kan worden gekeken of deze plaatsnamen ook in het MediaObjectFragmentKeyword veld voorkomen. Indien dit veld enkel zou bestaan uit alle relevante geonames, zou dit de correctheid van de geonames uit de beschrijvingen bepalen. In de realiteit kunnen echter ook geonames voorkomen, die eigenlijk niet verwijzen naar de geografische plaats, maar wel bij de keywords staan (zoals bijvoorbeeld ’paus’, ’foto’, ’ballet’, . . . ). Het kan ook gebeuren dat correct ge¨ınterpreteerde geonames niet zijn toegevoegd aan de keywords. De vergelijking met de keywords geeft dus slechts een indicatie van de correcte interpretatie van de gevonden geonames. Deze evaluatie dient dan ook enkel om te kijken hoe goed het systeem werkt, en niet om geonames te filteren. Om dit uit te testen, kunnen voor elke gevonden geoname de volgende scores worden berekend: true positives (TP), false positives (FP), true negatives (TN) en false negatives (FN). De eerste score (TP) geeft aan bij hoeveel documenten de geoname voorkomt in zowel de beschrijving als de keywords. Om de tweede score (FP) te bepalen, wordt geteld hoeveel keer de geoname wel in de beschrijving, maar niet in de keywords voorkomt. De derde score (TN) geeft aan bij hoeveel documenten de geoname in geen van beide velden voorkomt. Voor de laatste score (FN) wordt geteld hoeveel keer de geoname in de keywords voorkomt, maar niet in de beschrijving. Uit de eerste (TP) en laatste score (FN) kan de zogenaamde recall waarde (Re) worden berekend: Re =

TP TP + FN

Deze waarde geeft aan hoeveel van de relevante documenten daadwerkelijk worden gevonden. Een document wordt als relevant beschouwd, indien de geoname bij de keywords voorkomt. De scores, samen met de recall waarde, worden berekend voor alle geonames die in de beschrijvingen en keywords aanwezig zijn. Ook de bovenliggende gebieden, die eigenhandig zijn toegevoegd, worden in rekening genomen. Hieronder volgt een voorbeeld: Onderstaand document levert een FP op voor ’brussel’ en voor ’foto’. De geoname ’belgie’ komt niet voor in de beschrijving, maar levert wel een TP op, aangezien deze een bovenliggend gebied van ’brussel’ is, en dus impliciet in de beschrijving aanwezig is. Alle andere geonames worden in dit document als TN beschouwd: MediaObjectFragmentScriptDescription: 31’29” archief rijkswachtbetoging in *brussel* tegen politiehervorming, ; *foto* vande lanotte en geluid van radio-interview over besteding 8 miljard voor


108

de hervorming. ;archief politiegebouwen, rijkswachtgebouw. MediaObjectFragmentKeyword:

begroting,

*belgie*,

eenheidspolitie,

europese landen,

financiën, herstructurering, nsj.20000413.17, ordedienst, politie, samenleving, staatsfinancies, vande lanotte johan

Volgend document levert een TP op voor ’gent’ en ’belgie’, maar een FP voor ’brussel’: MediaObjectFragmentScriptDescription: 38’50” treinverkeer tussen kust en *brussel* heeft vertraging door zelfmoord. ;buitenbeeld *gent* sint-pieters. ;mensen kijken naar infobord met vertrektijden. ;mensen in gang. ;39’11” MediaObjectFragmentKeyword: *belgie*, binnenbeeld, buitenbeeld, dood, europese landen, *gent*, mobiliteit, nmbs, nsj.20030721.30, ongeval, openbaar vervoer, opnamen, rampenmodellen, sint-pietersstation, spoorweg, station, vertraging, zelfmoord 4.6.2.1

Implementatie

Om de geonames uit de beschrijvingen te kunnen vergelijken met die uit de keywords, moet eerst een extra matrix worden opgesteld (bomTagGeoIds2 ). Deze is gelijkaardig aan de bomGeoIds2 matrix (zie paragraaf 4.4.2), maar bevat nu alle geonameids die overeenkomen met de gevonden geonames uit de keywords, inclusief de bovenliggende gebieden. Alvorens deze nieuwe matrix kan worden opgesteld, moeten alle geonames uit de keywords worden gehaald. Hiervoor wordt opnieuw gebruikgemaakt van de ExportMetada klasse (zie paragraaf 4.3.1). Deze wordt uitgebreid met een nieuwe methode:

p u b l i c v o i d convertTags ( String input , String output ) throws IOException { String key = ” MediaObjectFragmentKeyword ” ; convert ( input , output , new TagDocument ( ) , key ) ; }

De keywords worden op een gelijkaardige manier geparset als de beschrijvingen. Nu wordt er echter een TagDocument meegegeven in plaats van een DescriptionDocument. Deze nieuwe klasse is opnieuw afgeleid van IMedataDocument, en voorziet terug een parse methode. De opslag van de aparte termen is dit keer eenvoudiger: elke reeks van karakters, gescheiden door een komma, wordt als één term aanzien. In dit geval moet er dan ook maar één matrix worden opgesteld (bomTags2 ), in plaats van vijf. De bomTagGeoIds2 matrix wordt opgesteld aan de hand van de bomTags2 matrix, en aan de hand van een nieuwe boomstructuur (geotreeAll2 ): deze bevat alle gevonden geonameids voor zowel de beschrijvingen als de tags, samen met de geonameids van de bovenliggende gebieden. Met behulp van deze nieuwe matrix, en de reeds vroeger opgestelde bomGeoIds2 matrix, kunnen de vier scores, samen met de recall waarde, voor elke geoname worden berekend. Hiervoor wordt


109

de volgende klasse voorzien: RecallCalculator - Deze klasse bevat een methode recall(String geonames, String uitvoer), die voor alle termen, aanwezig in het meegegeven bestand geonames, de vier scores berekent, samen met de recall waarde. De resultaten worden weggeschreven naar het uitvoerbestand. Om deze waarden te berekenen, moeten in de constructor ook de twee matrices worden ingeladen, die de geoname(id)s van de beschrijvingen en de keywords bevatten. Alle geonames worden één voor één opgezocht in de indexbestanden van de twee matrices, zodat de documenten gekend zijn waarin de geoname voorkomt. Voor elk documentnummer dat door beide indexbestanden wordt gevonden, wordt de TP-score met één vermeerderd.

Indien een

documentnummer alleen wordt gevonden door het bomTagGeoIds2 indexbestand, levert dit een FN op. In codetaal kan dit gemakkelijk worden bepaald met behulp van binair zoeken:

i n t index = Arrays . binarySearch ( bomDescIndex . postings_data , beginDesc , endDesc , keywDocnr ) ;

Hierbij is keywDocnr een document dat wordt gevonden door het bomTagGeoIds2 indexbestand. Dit wordt opgezocht in het indexbestand van de beschrijvingen: beginDesc en endDesc duiden aan tussen welke grenzen van de tabel alle beschrijvingen liggen, die de geoname bevatten. Indien het documentnummer hiertussen wordt gevonden, levert dit een TP op. De FP’s kunnen op de omgekeerde manier worden gevonden:

i n t index = Arrays . binarySearch ( bomKeyIndex . postings_data , beginKeyw , endKeyw , descrDocnr ) ;

Het aantal TN’s ten slotte, is gelijk aan het verschil van het totaal aantal documenten en de drie andere scores.

4.6.3

Resultaten

De filterstappen werden ondernomen voor elke geoname uit de beschrijvingen, behalve voor degene die cijfers bevatten. Hierdoor werden in totaal 29.562 geonames onderworpen aan de filters. Tabel 4.14 toont een overzicht van het aantal gevonden false/true matches per filterstap (kolom ’#matches’), op het totaal aantal onderzochte geonames voor die filter (kolom ’#geonames’). Ook de TP’s werden voor elke geoname in elke stap uitgerekend. De laatste kolom geeft het procentuele aantal matches aan met een TP waarde groter dan nul, die bijgevolg zowel in de beschrijvingen als in de keywords voorkomen. Hierbij werden de eigenhandig bijgevoegde hogerliggende gebieden niet in rekening genomen. Voor de eerste filter, die zoekt naar stopwoorden, werden 104 false matches gevonden. Het is bijna 100 procent zeker dat al deze matches in de beschrijvingen als stopwoord worden bedoeld, en


110

Tabel 4.14: Aantal gevonden matches per filterstap en hun TP’s

filterstap

match

#matches

#geonames

% matches met TP>0

1

false

104

29.562

51

2

false

575

29.458

88

3

true

366

28.883

51

4

true

2.875

28.517

50

5

false

2.555

25.642

49

6

true

6.520

23.087

36

false

16.567

23.087

13

nooit als plaatsnaam. Toch komen 51 procent van deze geonames ook voor in de keywords. Dit is te wijten aan het feit dat sommige data verkeerd worden aangeleverd: zo geeft de term ’week van de soep’, die in een BOM-beschrijving voorkomt, aanleiding tot vier keywords: ’week’, ’van’, ’de’ en ’soep’. De tweede filter, die persoonsnamen opspoort, leverde 575 false matches op. Namen zoals ’John’, ’Claudia’, ’Laura’, zullen hoogst waarschijnlijk steeds als persoonsnaam zijn bedoeld, en niet als plaatsnaam. Toch werden in het resultaat ook namen opgenomen zoals ’Costa Brava’, ’Congo’, ’Santa Barbara’, . . . Deze zijn echter wel bedoeld als plaatsnaam en zijn bijgevolg verkeerd geklasseerd. De gebruikte lijst met persoonsnamen bevat dus ook plaatsnamen. Van deze geonames werd 88 procent teruggevonden bij de keywords. Dit is ook logisch, aangezien persoonsnamen ook meestal in de keywords worden opgenomen. De overige geonames komen meestal ook wel voor in de keywords, maar onder hun volledige naam: ’Arthur’ komt bijvoorbeeld voor als ’koning Arthur’, ’Arthur Andersen & co’, ’Gomez Arthur’, enzovoort. Deze naam levert dus geen TP’s op, aangezien de keywords in zijn geheel worden bekeken, en niet als aparte delen. De derde filter, die landen uit de geonames haalt, leverde 366 true matches op. De meeste matches zijn effectief landen, op een paar uitzonderingen na: zo worden ’Franca’, ’Maurici’ en ’Y’ als synoniemen beschouwd van respectievelijk ’Frankrijk’, ’Mauritius’ en ’Yemen’. In de beschrijvingen worden de twee eerste geonames echter als persoonsnamen beschouwd. Eigenlijk moesten deze twee namen reeds door de tweede filter als false match zijn gedetecteerd. Slechts 51 procent van de gevallen zijn ook in de keywords terug te vinden. De FP score van de andere geonames is echter meestal ook klein (deze heeft dikwijls de waarde één). Dit wil zeggen dat deze geonames ook niet vaak voorkomen in de beschrijvingen. Dit is bijvoorbeeld het geval voor plaatsnamen zoals ’Somalia’, ’Sweden’. De alternatieve namen ’Somalie’ en ’Zweden’ hebben bijvoorbeeld wel een TP score die groter is dan één (5 voor ’Somalie’ en 125 voor ’Zweden’). Voor de vierde filter, die plaatsnamen in België opspoort, werden 2.875 true matches gevonden. Toch komen ook hier terug enkele ’foutieve’ true matches terug.

Zo worden bijvoorbeeld de

geonames ’zool’, ’hemelrijk’ en zelfs ’aan de kippen’ als true matches beschouwd. Dit komt omdat


111

deze namen in Geonames onder de categorie populated place vallen. Deze plaatsen zijn meestal dorpen of gemeenten, maar kunnen ook straten of gebouwen aanduiden. Zo blijkt ’zool’ bijvoorbeeld een jeugdhuis in Limburg te zijn. 50 procent van de true matches komen ook als keyword terug. Degene die niet voorkomen, hebben terug dikwijls een lage FP score. De voorlaatste filter, die geonames opspoort die samen voorkomen met lidwoorden, leverde 2.555 false matches op. Een geoname werd hierbij aanschouwd als een false match, indien deze in vijftien procent van de gevallen samen met een lidwoord voorkomt. Om te vergelijken, werd de filter ook een tweede keer uitgevoerd. Bij deze uitvoering werd een geoname als false match beschouwd, vanaf dat hij minstens één keer samen met een lidwoord voorkomt. Dit leverde 3.697 false matches op. De tweede uitvoering elimineerde meer foutief ge¨ınterpreteerde geonames, maar ook plaatsen zoals ’Tenerife’, ’Florida’ en ’Amsterdam’ werden als false match aanzien. ’Amsterdam’ komt slechts in 8 van de 967 gevallen (of nog geen één procent) samen met een lidwoord voor, bijvoorbeeld in de volgende beschrijving: ’schuttersgalerij van het Amsterdam historisch museum’. Door dit kleine percentage werd ’Amsterdam’ bij de eerste uitvoering niét als false match aanschouwd. Woorden zoals ’mail’ en ’rokers’ werden hierbij echter ook niet als false match aangeduid, in tegenstelling tot bij de tweede uitvoering. De laatste filter, die op zoek gaat naar geonames die samen voorkomen met één van de corresponderende bovenliggende gebieden, leverde 6.520 true matches op, naast 16.567 false matches. Deze laatste zijn allemaal goed geklasseerd, op een paar uitzonderingen na: zo komen relevante geonames zoals ’Las Palmas’ en ’Cruz de la Palma’ voor als false match. De true matches daarentegen bevatten ook veel irrelevante geonames. Vooral achternamen van personen komen veel voor, net zoals bij de false matches. Ook de geoname ’mail’ uit de vorige filter is ondergebracht bij de true matches. ’Rokers’ daarentegen is wel als false match aangeduid. Uit de tabel blijkt ook dat de kwaliteit van de true matches (36%) beter is dan die van de false matches (13%). In totaal werden met dit systeem 19.801 BOM-geonames aanzien als false match. Dit wil zeggen dat niet minder dan 67 procent van de plaatsnamen als irrelevant wordt aanschouwd. Zoals aangetoond is dit slechts een indicatie, aangezien er false matches bij true matches worden geklasseerd, en omgekeerd. Om het resultaat de verbeteren, kan het filteringproces eventueel nog worden uitgebreid met andere filters.

Voor elke BOM-geoname werd ook de recall waarde uitgerekend: Tabel 4.15 toont het aantal geonames die respectievelijk een recall waarde hebben tussen 0-19, 20-39, 40-59, 60-79 en 80-100 procent. Deze geonames zijn nog eens onderverdeeld in zeven categorieën, volgens het aantal positives (TP + FP): het aantal geonames die respectievelijk tussen 0-19, 20-59, 60-99, 100-499, 500-999 en meer dan 1.000 positives hebben, worden apart weergegeven. Door deze


112

opsplitsing kan er iets meer inzicht worden verkregen in de resultaten. Tabel 4.15: Aantal geonames, ingedeeld volgens aantal positives en recall waarde

Recall (%) #positives

0-19

20-39

40-59

60-79

80-100

0-19

19.788

556

297

166

1.983

20-59

1.356

299

207

147

467

60-99

385

119

89

64

143

100-499

530

316

230

128

221

500-999

99

73

62

35

37

≥ 1.000

154

177

132

80

41

78,62

5,43

3,58

2,18

10,19

totaal (%)

Figuur 4.15 toont een visuele weergave van deze aantallen, in de vorm van een gestapelde kolom. Per categorie (indeling volgens aantal positives) wordt voor elke reeks (recall waarde) het procentuele aantal geonames weergegeven, dat bijdraagt tot deze categorie.

Figuur 4.15: Grafiek: aantal geonames, ingedeeld volgens aantal positives en recall waarde

Uit de grafiek blijkt dat het procentueel aantal geonames, die een recall waarde hebben tussen 0 en 19 procent, voor elke opeenvolgende categorie daalt. Het aantal geonames met een recall waarde tussen 20 en 79 procent, stijgt daarentegen steeds. Toch behoren het grootste deel van de geonames van alle categorieën, behalve de laatste (≥ 1000), tot de reeks met de laagste recall waarde. Dit betekent dat in de meeste gevallen (78,62 procent) vaak niet meer dan

1 5

van de relevante resultaten

wordt getoond. In 10,19 procent van de gevallen wordt wel vaak het grootste deel (minimum 54 ) van de relevante resultaten getoond. De geonames die tot deze laatste reeks behoren, zullen ook vaker juist worden ge¨ınterpreteerd. In totaal zijn 28.381 geonames opgenomen in het resultaat. Dit zijn er 1.181 minder dan er werden


113

onderzocht bij het filteringproces. Dit komt omdat de recall waarden zijn berekend op basis van de bomGeoIds2 en bomTagGeoIds2 matrix. Deze werken met geonameids, en niet met geonames. Voor alternatieve namen zoals bijvoorbeeld ’belgie’, ’belgium’, ’belgi’ wordt een recall waarde dan ook maar één keer berekend. Alle alternatieve namen hebben namelijk dezelfde geonameid.

4.7

Evaluatie van geonames: deel 2

Het filteringproces en de berekening van de recall waardes leverden maar matige resultaten op. Sommige relevante geonames worden nog steeds als false match aanzien, terwijl sommige irrelevante geonames dan weer als true match worden aanzien. Ook de TP scores en recall waarden van de geonames geven dikwijls kleine waarden terug. Om de oorzaak op te sporen van deze matige resultaten, worden daarom nog enkele extra evaluatiestappen voorzien: In de eerste stap worden de recall waarden nog eens herberekend, op een beperkt aantal BOM-fragmenten. Niet alle fragmenten zijn namelijk voorzien van even goede annotaties. De beperkte deelverzameling wordt getoond in figuur 4.16: er wordt enkel rekening gehouden met geonames die voorkomen in fragmenten die geannoteerd zijn met ’vrt’ en ’nieuws’.

Figuur 4.16: Onderzochte deelverzamelingen A, B en C

In VRT-nieuwsfragmenten zijn namelijk ook meestal de plaatsnamen opgenomen in de keywords. Het onderstaande voorbeeld toont aan dat dit bijvoorbeeld bij VMMA-nieuwsfragmenten niet (altijd) het geval is: Hieronder worden de beschrijving en keywords van een VRT-nieuwsfragment weergegeven, dat gaat over een ongeval in Gent. In de keywords zijn drie plaatsnamen opgenomen: ’belgie’, ’europese landen’ en ’gent’: MediaObjectFragmentScriptDescription: 19.00 uur fietser omgekomen bij ongeluk in dode hoek van vrachtwagen.;29.01 *Gent*.Kruispunt, straat afgespannen.vrachtwagen, politie, fiets onder


114

vrachtwagen. politie op plaats ongeval, onderzoek 29.18 MediaObjectFragmentKeyword: auto, *belgie*, dood, ethiek, *europese landen*, fiets, *gent*, kruispunt, nsj.20040203.24, ongeval, ordedienst, politie, rampenmodellen, transport, verkeer, vrachtwagen In het volgende VMMA-nieuwsfragment, dat ook gaat over een ongeval in Gent, is echter geen enkele plaatsnaam opgenomen in de keywords. Nochtans bevat de beschrijving zowel (een afgeleide versie van) de plaatsnamen ’Gent’ als ’Zelzate’: MediaObjectFragmentScriptDescription:

Een dodelijk ongeval aan het kruispunt van

de Skaldenstraat met de John Kennedylaan in de *Gentse* kanaalzone zorgde voor heel wat verkeershinder op de R4 in de richting van *Zelzate*. Het ongeval gebeurde tussen 08.30 en 09.00 uur. Het is nog niet duidelijk hoeveel voertuigen betrokken zijn bij het ongeval. MediaObjectFragmentKeyword:

dode,

fiets,

ongeval,

slachtoffer,

verkeersongeval,

weggebruiker, zwakke Enkel de geonames uit deelverzamelingen A, B en C uit figuur 4.16 komen dus terug in de resultaten:

A bevat alle geonames die voorkomen in de keywords die opgenomen zijn bij

VRT-nieuwsfragmenten, B bevat deze die zijn opgenomen in het geotagger veld (en dus uit de beschrijvingen zijn gehaald).

Geonames die zowel zijn opgenomen in de keywords als in het

geotagger veld, bevinden zich in doorsnede C. De recall waarde kan dan worden berekend als volgt: Re =

C A

Daarnaast wordt ook de precisionwaarde (Pr) berekend: Pr =

TP C = TP + FP B

De precisionwaarde zegt iets meer over de betrouwbaarheid van de gevonden documenten: de waarde geeft de verhouding aan van het aantal gevonden relevante documenten, op het totaal aantal gevonden documenten. De recall waarde daarentegen, zegt iets meer over de volledigheid van de gevonden documenten: deze waarde geeft de verhouding aan van het aantal gevonden relevante documenten, op het totaal aantal mogelijke relevante documenten. Als tweede stap worden de gevonden BOM-geonames ook vergeleken met een lijst van BOM-geonames, die reeds vroeger werd opgesteld door een begeleider. De derde stap geeft een distributie weer van de landen. Voor alle geonames wordt gekeken hoeveel keer ze met elk mogelijk land voorkomen in de BOM-beschrijvingen. Wanneer een geoname vaak voorkomt met meerdere landen, kan dit op een foutief ge¨ınterpreteerde geoname wijzen.


115

Al deze gegevens worden samengebracht in een Excel bestand, zodat alle evaluatiestappen per geoname kunnen worden bekeken. Ook de filteringstappen uit de vorige evaluatie worden hieraan toegevoegd. In dit geval worden de filterstappen echter allemaal apart uitgevoerd. Elke geoname wordt dus onderworpen aan elke filter, zodat een geoname meerdere keren als true of false match kan worden aangeduid. Om de oorzaak van ’ongewone’ resultaten op te sporen, worden de geonames volgens de echte boomstructuur uitgeschreven: eerst wordt het land uitgeschreven, vervolgens alle deelgebieden, gesorteerd per admin1 en admin2 gebied. Voor elke geoname worden ook het corresponderende continent, land, admin1 en admin2 gebied in een aparte kolom bijgehouden. Met deze sortering wordt het gemakkelijker om in het Excel bestand op te sporen waarom een geoname weinig in de keywords voorkomt, maar wel veel in de BOM-beschrijvingen. Dit Excel bestand biedt dan ook belangrijke informatie aan voor de verdere evalutie van de geonames. Aan de hand van de Excel AutoFilter optie kunnen ook gemakkelijk geonames worden getoond die enkel aan bepaalde voorwaarden voldoen: zo kan bijvoorbeeld snel worden weergegeven welke geonames een TP score hebben groter dan nul (deelverzameling C), welke geonames een recall waarde hebben boven een bepaalde threshold, enzovoort. Ook informatie uit de verschillende Excel kolommen kan worden gecombineerd om de resultaten te evalueren.

4.7.1

Implementatie

Om alle uitvoer naar één Excel bestand te kunnen wegschrijven, wordt een extra klasse aangemaakt: ResultGenerator - Deze klasse zorgt ervoor dat alle evaluatiestappen apart kunnen worden uitgevoerd, en kunnen worden weggeschreven naar een bestand. In de constructor wordt als eerste een convertMap attribuut aangemaakt van het type HashMap<String,ArrayList<String>. Deze bevat voor elke geonameid alle alternatieve namen die bij deze geonameid horen, en die voorkomen in de BOM-beschrijvingen. Ook de geonames van de hogerliggende gebieden, die zelf werden toegevoegd aan de beschrijvingen, worden hierin opgenomen. Om alle geonames volgens de boomstructuur te kunnen uitschrijven, wordt de methode generateTree(String input) voorzien. Deze methode maakt gebruik van de reeds opgestelde geoTree2 matrix. Om de boomstructuur te kunnen opstellen, worden nog vijf extra klassen voorzien: Area, Admin2, Admin1, Country en Continent. De laatste vier klassen zijn afgeleid van de eerste. De resultaten van de evaluatiestappen van een geoname kunnen in een object van één van deze klassen worden opgeslagen, al naargelang het soort gebied dat met de geoname overeenkomt. De klasse Area houdt daarvoor de volgende attributen bij:

String geonameId ; String [ ] geonames ; i n t [ ] keywordCount ; i n t geota ggerCou nt ;


116

i n t [ ] intersectionCount ;

Naast de geonameid wordt een stringlijst (geonames) bijgehouden, die alle alternatieve namen voor een geoname bevat. De laatste drie attributen worden gebruikt om de recall - en precisionwaarden in op te slaan. De eerste tabel houdt het aantal BOM-documenten bij waarin de geoname als keyword voorkomt. Voor elke alternatieve naam wordt dit aantal apart berekend. Het tweede attribuut houdt slechts één waarde bij: het aantal documenten waarin de geoname (eventueel impliciet) in de beschrijving voorkomt. Alternatieve namen leveren steeds dezelfde waarde op, aangezien dit aantal berekend wordt op basis van de geonameid. Eén waarde bijhouden volstaat dus. Het laatste attribuut houdt de doorsnede bij van deze documenten. Met behulp van deze attributen kunnen de recall - en precisionwaarde worden berekend. De afgeleide klassen houden elk één extra attribuut bij: een map waarin de onderliggende gebieden van het eerste niveau worden bijgehouden. Zo voorziet de klasse Continent een map van het type HashMap<String, Country>, zodat alle landen die tot dit continent behoren, kunnen worden bijgehouden. Een Country object kan worden opgevraagd aan de hand van de corresponderende geonameid. Met behulp van deze extra klassen kan de boomstructuur gemakkelijk worden opgesteld. Als eerste worden alle continenten opgeslagen in een continentMap attribuut van het type HashMap<String, Continent>. Vervolgens wordt elk document uit de geoTree2 term-document matrix afgelopen. Ieder document wordt van achter naar voor gelezen: eerst wordt de geonameid van het continent opgevraagd. Dit continent kan worden opgezocht in de continentMap. Vervolgens wordt het land ingelezen en opgezocht in de map die wordt bijgehouden door het Continent object. Indien dit land nog niet aanwezig is, wordt het toegevoegd aan de map. Alle alternatieve namen voor deze geoname, kunnen worden opgevraagd aan het convertMap attribuut van de klasse ResultGenerator. Op deze manier worden ook het admin1 en admin2 gebied afgehandeld. De eerste term van het geoTree2 document wordt opgeslagen als een Area object. Wanneer de boomstructuur is opgebouwd, kunnen gemakkelijk de evaluatiestappen worden uitgevoerd. Om de geonames van de beschrijvingen en keywords te vergelijken, werd in paragraaf 4.6.2.1 gebruikgemaakt van twee matrices, die de corresponderende geonames bevatten voor elk fragment. Om de recall waarden voor de geonames uit de deelverzamelingen te berekenen, kunnen deze matrices niet worden gebruikt. De termen ’vrt’ en ’nieuws’ zijn namelijk opgenomen in de velden ProgrammeGroupDescription en ProgrammeKeyword. Deze informatie kan niet uit de twee matrices worden gehaald. Daarom wordt een beroep gedaan op de klassieke BOM-interface. Voor elke BOM-geoname worden drie HTTP-requests verstuurd, die de volgende querystrings bevatten:


117

+vrt +nieuws +MediaObjectFragmentKeyword:geoname +vrt +nieuws +geotagger:geonameid +vrt +nieuws +MediaObjectFragmentKeyword:geoname +geotagger:geonameid Wanneer de eerste HTTP-response minstens één resultaat oplevert, behoort de geoname tot de deelverzameling A uit figuur 4.16.

De tweede en derde response bepalen of de geoname tot

deelverzameling B en/of C behoort. Om de requests uit te voeren, wordt de klasse SAXController uit paragraaf 4.5.5 uitgebreid met een nieuwe methode: parseAreaInfo(Area area).

Met behulp van de XMLReader worden de

HTTP-requests uitgevoerd en wordt het aantal resultaten uit de HTTP-responses geparset. De eerste en derde HTTP-request worden voor elke alternatieve naam uitgevoerd. De tweede request moet enkel voor de bijhorende geonameid worden uitgevoerd. De geparsete resultaten worden opgeslagen in het meegegeven Area object. De parseArea methode van de SAXController klasse moet worden uitgevoerd voor elke geoname uit de boomstructuur. Hiervoor is in de klasse ResultGenerator ook een methode parseAreaInfo() voorzien. Deze wordt als volgt ge¨ımplementeerd:

p u b l i c v o i d parseAreaInfo ( ) throws IOException { f o r ( Continent continent : continentMap . values ( ) ) continent . parseAreaInfo ( sc ) ; // s c = SAXController }

Voor elk continent wordt de methode parseAreaInfo(SAXController) opgeroepen. Deze methode wordt voorzien door de Area klasse, en wordt in elke afgeleide klasse overschreven. Voor de klasse Continent ziet deze methode er als volgt uit:

p u b l i c v o i d parseAreaInfo ( SAXController sc ) { sc . parseAreaInfo ( t h i s ) ; f o r ( Country country : countryMap . values ( ) ) country . parseAreaInfo ( sc ) ; }

Als eerste wordt de parseAreaInfo methode van de SAXController klasse opgeroepen. Vervolgens wordt de parseAreaInfo methode van de Area klasse iteratief opgeroepen, voor elk deelgebied. Zo worden alle waarden voor elke geoname bekomen. Om de distributie van de landen te genereren, wordt de methode loadCountryInfo(String input) ge¨ımplementeerd. Als input wordt de bomGeoIds2 term-document matrix meegegeven. Met behulp van deze matrix kan voor elk land worden gekeken met welke andere geonames ze voorkomen. Hiervoor wordt een map van het type TreeMap> bijgehouden. Aan de hand van het bomGeoIds2 indexbestand kan elke BOM-beschrijving worden


118

opgezocht die het corresponderende land bevat.

Alle termen van deze documenten worden

opgehaald, en toegevoegd aan de treemap, samen met hun frequentie. Bij het uitschrijven van een naam kan dan voor elk land worden geraadpleegd hoeveel keer de geoname met het land samen voorkomt. Verder worden de geonames terug onderworpen aan de filters uit paragraaf 4.6.1. Deze keer wordt elke filter toegepast op een geoname. Hiervoor kunnen terug de methodes uit paragraaf 4.6.1.2 worden gebruikt. Er wordt ook een bijkomende filter toegepast: deze kijkt of de geoname ook in een andere lijst voorkomt. Deze lijst bevat alle relevante geonames, die bij een eerder onderzoek werden gevonden. De lijst is echter beperkt, omdat deze enkel de geonames bevat die bij de keywords voorkomen. Ten slotte bevat de klasse ResultGenerator een methode generateOutput(String output), die alle gegevens naar een uitvoerbestand wegschrijft. Deze gegevens kunnen dan worden ge¨ımporteerd in een Excel bestand. Dit bestand kan dan dienen voor verdere evaluatie.

4.7.2

Resultaten

De berekening van de recall waardes op de beperkte verzameling BOM-fragmenten, leverde totaal andere resultaten op dan bij de vorige evaluatie uit paragraaf 4.6.3. De resultaten wordt getoond in tabel 4.16 en figuur 4.17. Tabel 4.16: Aantal geonames, ingedeeld volgens aantal positives en recall waarde, op beperkte verzameling

Recall (%) #positives

0-19

20-39

40-59

60-79

80-100

0-19

19.133

344

670

778

8.162

20-59

950

60

126

248

841

60-99

317

28

31

67

202

100-499

631

57

75

155

371

500-999

141

8

15

37

84

≥ 1.000

250

5

24

67

142

62,97

1,48

2,77

3,97

28,81

totaal (%)

In totaal werden 34.019 geonames opgenomen in het resultaat. Dit zijn er meer dan bij de vorige recall berekening, aangezien nu ook alle zelf toegevoegde hogerliggende gebieden zijn opgenomen in het resultaat. In de vorige berekening werden de hogerliggende gebieden enkel opgenomen in het resultaat indien deze niet alleen impliciet, maar ook expliciet voorkomen in de BOM-beschrijvingen. Deze grafiek toont een aantal belangrijke verschillen met grafiek 4.15. Het procentueel aantal geonames met een recall waarde tussen 20 en 59 procent is voor elke categorie (behalve de eerste) beduidend lager dan bij de vorige evaluatie. Het aantal geonames met een recall waarde van ten minste 80 procent is daarentegen opmerkelijk gestegen voor elke categorie: in totaal behoren nu


Figuur 4.17: Grafiek:

119

aantal geonames, ingedeeld volgens #positives en recall waarde, op beperkte

verzameling

28,81 procent van de geonames tot deze reeks (R ≥ 80%), in tegenstelling tot 10,19 procent bij de vorige evaluatie. Dit duidt meteen aan dat VRT nieuws items beter gekeyword zijn.

Om het systeem te evalueren, kan dus de recall waarde worden gebruikt. De precisionwaarde daarentegen kan worden gebruikt om een aantal geonames weg te filteren. Figuur 4.18 toont het aantal geonames die zouden wegvallen, indien ofwel de recall waarde (figuur links), ofwel de precisionwaarde (figuur rechts) van de geonames onder een bepaalde threshold ligt. Beide figuren vertonen gelijkaardige resultaten: dit geldt zowel voor de volledige verzameling van geonames als voor de verzameling van geonames die reeds vroeger werden gevonden.

Figuur 4.18: Grafiek: aantal weggevallen geonames per threshold : links recall, rechts precision

Indien een threshold van 0,001 wordt genomen, valt reeds 63 procent van alle geonames weg, voor zowel de recall - als precisionwaarde. Voor de oude geonames zijn dit respectievelijk 32 en 33 procent. Een threshold van 0,9 laat respectievelijk 75 en 80 procent van alle geonames wegvallen.


120

Bij de oude geonames is dit respectievelijk 54 en 65 procent. Sommige geonames komen ook veel meer voor in het geotagger veld dan in de keywords. Aan de hand van de boomstructuur kunnen de oorzaken hiervan worden opgespoord. Zo werd ’rusland’ bijvoorbeeld 16.405 keer gevonden in het geotagger veld, en slechts 32 keer in de keywords. Door de boom af te lopen, werden een aantal geonames gevonden die gelegen zijn in Rusland, maar eigenlijk geen relevante plaatsnamen zijn. Tabel 4.17 toont een aantal van deze foutieve geonames, samen met hun A-, B- en C-waarde uit figuur 4.16. Tabel 4.17: Foutieve en juist ge¨ınterpreteerde geonames uit Rusland

geoname

juist

ik krant langer moskou om

X

A

B

C

1

368

1

848

394

239

0

194

0

347

369

272

3

6.180

0

geoname rostov

juist

A

B

C

X

3

52

3

280

220

209

sven uit

3

6.610

0

vladivostok

X

2

2

2

volgograd

X

1

750

1

Aan de BOM-fragmenten zijn dus heel wat foutieve namen toegevoegd. Dit wordt ge¨ıllustreerd met een voorbeeldfragment, dat wordt getoond in figuur 4.19:

Figuur 4.19: Beschrijving van fragment en corresponderende geotagger waarden

De relatief kleine beschrijving is toch geannoteerd met heel wat geonames. Op de figuur zijn twee termen uit de beschrijving aangeduid, die een geoname voorstellen. De geoname ’Gent’ wordt juist ge¨ınterpreteerd, de geoname ’krant’ daarentegen is foutief. Alle hogerliggende gebieden die bij deze twee geonames horen, werden omcirkeld. Ten slotte kan ook de distributie van de landen worden geëvalueerd. In totaal werden 235 landen gevonden. Voor elke geoname werd geteld hoeveel keer deze samen met elk van de 235 landen voorkomt in de BOM-beschrijvingen. Deze informatie kan dienen om te kijken of een geoname tot het juiste land behoort: de mutuele informatie tussen de ’stad’ en het ’echte land’ zou hoger moeten zijn dan met andere landen. Dit kan in de toekomst nog verder worden onderzocht.

121

Besluit Het wereldwijde web bevat een berg aan informatie. Voor gebruikers wordt het steeds moeilijker om de meest relevante gegevens terug te vinden. In deze thesis werden dan ook een aantal technieken onderzocht die kunnen bijdragen tot betere en/of verfijnde zoekresultaten voor multimediale databases. Meer specifiek richtte het onderzoek zich op de BOM-Vl database, die multimediale bestanden uit Vlaanderen bevat. Om de bestanden uit deze database te doorzoeken, is reeds een klassieke zoekmachine voorzien. Hiermee kunnen eenvoudige query’s worden uitgevoerd. Met behulp van de onderzochte technieken wordt het echter mogelijk om de zoekmachine uit te breiden, zodat meer geavanceerde query’s kunnen worden uitgevoerd, of wordt het mogelijk om de zoekresultaten beter te visualiseren. Om dit te realiseren, maken al deze technieken gebruik van metadata die aan bestanden zijn toegevoegd. De eerste techniek die werd onderzocht, zorgt voor een betere visualisatie van de zoekresultaten door middel van tag clouds. Er werd een gebruikersinterface voorzien, die tag clouds kan genereren op basis van een zoekopdracht. Zo kan er door middel van tags een globaal overzicht worden gegeven van de zoekresultaten van de klassieke BOM-zoekmachine. Bij een klik op een tag komt de gebruiker terecht op een pagina met verfijnde zoekresultaten, die door de klassieke BOM-zoekmachine wordt gegenereerd. Een gebruiker kan zo eenvoudig op zoek gaan naar bestanden, die meer aan zijn verwachtingen beantwoorden. Het kan echter gebeuren dat sommige bestanden, die voldoen aan de zoekopdracht, toch niet worden weergevonden met de tag cloud. Dit is het geval wanneer bestanden enkel tags bevatten die zelden worden gebruikt als annotatie. Hoe meer tags worden afgebeeld in de tag cloud, hoe groter de kans dat ook weinig voorkomende tags worden opgenomen. Naarmate de zoekopdracht meer resultaten telt, duurt het langer om de tag cloud op te bouwen. Alle resultaten moeten namelijk worden overlopen om de meest voorkomende tags te kunnen opnemen in de tag cloud. Dit performantieprobleem werd reeds gedeeltelijk opgelost door een thread mechanisme te implementeren. Zo kunnen meerdere resultaten ’tegelijkertijd’ worden verwerkt. Het tweede deel van het onderzoek richtte zich op de opbouw van domeinspecifieke ontologieën. Bestaande kennis over geografische gebieden van België en over het Belgische voetbal werden ondergebracht in twee aparte ontologieën. Dit gebeurde door concepten, relaties en instanties


122

vast te leggen in een datastructuur, zodat de betekenis van informatie ook toegankelijk werd voor computers. Door middel van deze ontologieën kunnen gebruikers meer expressieve query’s uitvoeren zoals ’geef mij alle gebeurtenissen die zich afspeelden binnen een bepaalde regio’ en ’geef mij alle personen die een bepaalde rol hebben vervuld in het Belgische voetbal, gedurende een bepaalde periode’. Aan de hand van de ontologieën kunnen deze query’s worden vertaald naar standaard query’s, die op zijn beurt kunnen worden doorgegeven aan de klassieke zoekmachine. Met behulp van een ontologie-editor, die een zoekmachine voorziet om expressieve query’s uit te voeren, werden een aantal zoekopdrachten uitgetest. Dit leverde niet altijd de gewenste resultaten op. Een query waarbij bijvoorbeeld alle onderliggende gebieden van het Vlaams Gewest worden opgevraagd, geeft enkel de provincies uit het Vlaams Gewest als resultaat terug, en niet de onderliggende arrondissementen en gemeenten. Om dit soort query’s uit te voeren, moet dan ook een andere zoekmachine worden gebruikt. Dit kan in de toekomst verder worden onderzocht. Deze ontologieën kunnen ook nog worden uitgebreid naar andere specifieke domeinen.

Een

ander aspect dat verder kan worden onderzocht, is de optimalisatie van de uitvoering van de zoekopdracht.

Naarmate een ontologie groter wordt, gaat ze meer geheugen innemen en de

werking van de zoekrobot vertagen. Er kan ook nog worden onderzocht hoe ontologieën kunnen gepartitioneerd en/of gedistribueerd worden. Wanneer afspraken worden gemaakt omtrent de voorstelling van dezelfde soort data, kunnen gegevens namelijk gemakkelijker worden uitgewisseld tussen verschillende peers. Aan de hand van een derde techniek werden relaties tussen tags bestudeerd. Het komt vaak voor dat relevante bestanden toch niet worden opgenomen in de zoekresultaten, omwille van verschillende tags die worden gebruikt voor gelijkaardige concepten. Aan de hand van de Flickr fotoservice werd getracht om relevante tags voor een bepaalde tag op te zoeken, zodat de zoekresultaten kunnen worden verbeterd. Er werd een vaste dataset opgesteld om relevante tags te kunnen opzoeken. Deze dataset bevat ongeveer één miljoen random foto’s uit de Flickr database. Al deze foto’s, samen met hun tags, moesten worden opgehaald. Om de requests naar de Flickr service vlot te doen verlopen, werd ook dit systeem van een thread mechanisme voorzien. De snelheid moest echter worden gelimiteerd, aangezien Flickr maximum tien aanvragen per seconde toelaat. Bijgevolg verliep de ophaling van de data toch moeizaam. Het is momenteel reeds mogelijk om relevante tags, die bij een bepaalde tag horen, op te zoeken aan de hand van een servlet. De geteste tags leverden steeds een aantal goede resultaten op. Als uitbreiding zouden relevante tags automatisch kunnen worden getoond aan de gebruiker, indien een zoekopdracht wordt ingegeven. Immers, hoe beter de zoekopdracht kan worden gespecificeerd, hoe minder zoekresultaten er verloren gaan.

Hoofdstuk 4. Extractie van plaatsnamen Als laatste werd ook de extractie van plaatsnamen uit metadata onderzocht.

123 Meer bepaald

werden uit alle beschrijvingen, die als annotatie aan de BOM-bestanden zijn toegevoegd, de plaatsnamen geëxtraheerd. Aan elk BOM-bestand werden de gevonden plaatsnamen, samen met de hogerliggende gebieden (provincie, land, ...) in een nieuw metadata veld toegevoegd. Deze informatie kan worden gebruikt om alle gebeurtenissen binnen een bepaald gebied terug te vinden. Hiervoor werd gebruikgemaakt van de geografische database van Geonames. De resultaten werden ook gevisualiseerd voorgesteld op een kaart, door middel van Google Maps. De plaatsnamen die werden gevonden, kunnen echter niet allemaal als relevant worden aanschouwd. Termen zoals ’foto’, ’mail’, ’jan’, . . . zijn wel in de Geonames database aanwezig, maar stellen in de BOM-database geen echte plaatsnamen voor. Om de plaatsnamen en de werking van het uitgebreide zoeksysteem te evalueren, werd een Excel bestand opgesteld. Dit bestand bevat voor elke plaatsnaam een aantal evaluatiestappen. Zo werden de plaatsnamen uit het nieuwe metadata veld vergeleken met de plaatsnamen uit het keyword veld. Het bleek dat veel plaatsnamen vaak enkel voorkomen in het nieuwe metadata veld. Doordat de plaatsnamen in het Excel bestand werden uitgeschreven volgens de boomstructuur, konden de oorzaken van deze (en andere) ’ongewone’ resultaten worden opgezocht. Zo bleek dat plaatsnamen zoals ’ik’, ’krant’, ’langer’, . . . aan Rusland worden gerelateerd, waardoor Rusland in veel gevallen foutief wordt ge¨ınterpreteerd. Er werden ook enkele filters opgenomen, die ’echte’ en ’valse’ plaatsnamen van elkaar kunnen onderscheiden: zo daalt de relevantie van een plaatsnaam indien deze overeenkomt met een stopwoord of een persoonsnaam, of indien deze vaak voorkomt met een lidwoord. Wanneer een plaatsnaam een land aanduidt, een Belgische gemeente is, of in de beschrijving samen voorkomt met één van zijn bovenliggende gebieden, stijgt de relevantie. Met deze filters worden echter nog steeds plaatsnamen verkeerd geklasseerd. Als toekomstig werk kan ook de distributie van landen worden onderzocht: voor elke plaatsnaaam kan worden gekeken hoeveel keer hij met elk land voorkomt. Deze informatie kan worden gebruikt om te kijken of een plaats tot het juiste land behoort. Ten slotte kan worden geconcludeerd dat het voor geen enkele van de onderzochte technieken evident is om de verbetering van de zoekresultaten te meten. Het is namelijk moeilijk om tests uit te voeren op grote schaal. Om de technieken te testen, kunnen wel steeds een aantal willekeurige zoekopdrachten worden uitgevoerd. Sommige zoekopdrachten leveren goede resultaten op, andere dan weer niet. Het testen gebeurt ook steeds subjectief. Verschillende personen hebben namelijk verschillende meningen en voorkeuren. De ene gebruiker kan een bestand relevant vinden, voor een andere gebruik voldoet hetzelfde bestand totaal niet aan zijn verwachtingen. Het resultaat is ook sterk afhankelijk van de metadata die aan bestanden zijn toegevoegd.

124

Lijst met figuren 1.1

Voorbeeld van een tag cloud (WebResources Depot, 2008) . . . . . . . . . . . . . . . 11

1.2

Eerste resultaat voor zoekopdracht ’gent’ . . . . . . . . . . . . . . . . . . . . . . . . 12

1.3

Tag cloud voor zoekopdracht ’urbanus’ . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.4

Tag cloud voor zoekopdracht ’+urbanus +film’ . . . . . . . . . . . . . . . . . . . . . 15

1.5

Overzicht van de tag cloud applicatie klassen . . . . . . . . . . . . . . . . . . . . . . 16

1.6

Werking van een threadpool (Burnett, 2007) . . . . . . . . . . . . . . . . . . . . . . . 23

2.1

RDF graaf met meerdere triples (Broekstra, 2007) . . . . . . . . . . . . . . . . . . . 29

2.2

RDF Schema (Broekstra, 2007) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.3

Overzicht van het CROEQS-systeem (Vandamme et al., 2009) . . . . . . . . . . . . . 35

2.4

Klassen voetbalontologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.5

Property’s voetbalontologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3.1

Voorbeeld van het Tag Recommendation Systeem (Sigurbjörnsson & van Zwol, 2008) 46

3.2

Overzicht van de Flickr applicatie klassen . . . . . . . . . . . . . . . . . . . . . . . . 57

3.3

Foto’s voor de tags ’jaguar’, ’tiger’ en ’cat’ . . . . . . . . . . . . . . . . . . . . . . . . 60

3.4

Top 5 relevante tags voor ’jaguar’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.5

Top 5 relevante tags voor ’kikker’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

3.6

Top 5 relevante tags voor ’pinguin’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

4.1

Extracten van steden uit een beschrijving (na normalisatie) . . . . . . . . . . . . . . 69

4.2

Sequentiediagram: parsen van een beschrijving uit de BOM-database . . . . . . . . . 70

4.3

Co¨ ordinatenstelsel van de aarde . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

4.4

Voorbeeld van een grootcirkel op een bol (Frassek, 2006) . . . . . . . . . . . . . . . . 90

4.5

Afstand tussen twee steden: links gezien vanop een wereldbol (Wojciulewitsch, 1988), rechts vanop een mercatorkaart. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

4.6

Omrekening van polaire naar cartesische coördinaten voor een punt P1 , waarbij r1 = (x1 , y1 , z1 ) (Frassek, 2006) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

4.7

Bepaling van de minimum en maximum afstanden . . . . . . . . . . . . . . . . . . . 92

4.8

K-d tree: links de opdeling van de zoekruimte, rechts de bijhorende binaire boom (Kdtree, 2006). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

4.9

Opdeling van de zoekruimtes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

Lijst met figuren

125

4.10 Google Maps kaart voor zoekopdracht ’+moord +[gent 20]’ . . . . . . . . . . . . . . 95 4.11 Tekstballon die hoort bij plaats ’Destelbergen’

. . . . . . . . . . . . . . . . . . . . . 96

4.12 Eerste antwoordpagina voor de vertaalde zoekopdracht ’+moord +[gent 20]’ . . . . . 96 4.13 Naburige gemeenten voor ’oost vlaanderen’ . . . . . . . . . . . . . . . . . . . . . . . 103 4.14 Beslissingsdiagram dat aanduidt of een geoname een true of false match is . . . . . . 104 4.15 Grafiek: aantal geonames, ingedeeld volgens aantal positives en recall waarde . . . . . 112 4.16 Onderzochte deelverzamelingen A, B en C . . . . . . . . . . . . . . . . . . . . . . . . 113 4.17 Grafiek: aantal geonames, ingedeeld volgens #positives en recall waarde, op beperkte verzameling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 4.18 Grafiek: aantal weggevallen geonames per threshold : links recall, rechts precision . . 119 4.19 Beschrijving van fragment en corresponderende geotagger waarden . . . . . . . . . . 120

126

Lijst met tabellen 1.1

Resultaten voor de zoekopdracht ’urbanus’ (aantal tags: 30) . . . . . . . . . . . . . . 26

1.2

Resultaten voor de zoekopdracht ’leterme’ (aantal tags: 25) . . . . . . . . . . . . . . 27

3.1

Testgegevens voor het Tag Recommendation System . . . . . . . . . . . . . . . . . . 50

3.2

Resultaten voor de tag ’jaguar’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.3

Resultaten voor de tags ’jaguar’, ’tiger’ en ’cat’ . . . . . . . . . . . . . . . . . . . . . 52

3.4

Resultaten voor de tag ’kikker’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.5

Resultaten voor de tag ’pinquin’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.6

Resultaten voor de tag ’pinguin’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

3.7

Top 10 van tags uit testset met hoogste frequentie . . . . . . . . . . . . . . . . . . . 60

4.1

Term-document matrix: theoretisch

4.2

Inverted file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

4.3

Term-document matrix: implementatie (1) . . . . . . . . . . . . . . . . . . . . . . . . 73

4.4

Woordenboek (1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

4.5

Term-document matrix: implementatie (2) . . . . . . . . . . . . . . . . . . . . . . . . 73

4.6

Woordenboek (2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

4.7

Aangemaakte bestanden en hun groottes . . . . . . . . . . . . . . . . . . . . . . . . . 78

4.8

Eerste tien BOM-beschrijvingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

4.9

Eerste tien documenten na parsen van de BOM-beschrijvingen . . . . . . . . . . . . 79

. . . . . . . . . . . . . . . . . . . . . . . . . . . 71

4.10 Gevonden geonames voor de eerste tien documenten . . . . . . . . . . . . . . . . . . 80 4.11 Gevonden documenten voor ’Rusland’, ’België’ en ’Gent’ . . . . . . . . . . . . . . . . 82 4.12 Aantal resultaten voor geteste query’s (1) . . . . . . . . . . . . . . . . . . . . . . . . 87 4.13 Aantal resultaten voor geteste quey’s (2) . . . . . . . . . . . . . . . . . . . . . . . . . 102 4.14 Aantal gevonden matches per filterstap en hun TP’s . . . . . . . . . . . . . . . . . . 110 4.15 Aantal geonames, ingedeeld volgens aantal positives en recall waarde . . . . . . . . . 112 4.16 Aantal geonames, ingedeeld volgens aantal positives en recall waarde, op beperkte verzameling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 4.17 Foutieve en juist ge¨ınterpreteerde geonames uit Rusland . . . . . . . . . . . . . . . . 120 B.1 Subcategorieën horende bij categorie A . . . . . . . . . . . . . . . . . . . . . . . . . . IV B.2 Subcategorieën horende bij categorie P . . . . . . . . . . . . . . . . . . . . . . . . . .

V

Lijst met tabellen B.3 Velden van de ’geoname’ tabel

127 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . VI

128

Literatuurlijst Brickley, D. & Guha, R. (2004). RDF Vocabulary Description Language 1.0: RDF Schema. Geraadpleegd op 7 februari 2009 via http://www.w3.org/TR/rdf-schema. Broekstra, J. (2007). Semantic Web Technologie. Geraadpleegd op 7 februari 2009 via http://www.sgml-ug.nl/LinkClick.aspx?link=xmlholland07-Jeen+Broekstra.ppt. Burnett, C. M. (2007). Thread pool pattern. Geraadpleegd op 11 maart 2009 via http://en.wikipedia.org/wiki/Thread pool. BOM-Vl - Bewaring en Ontsluiting van Multimediale Data in Vlaanderen (2008). Geraadpleegd op 28 februari 2009 via http://www.ibbt.be/files/misc/Bom-Vl%20persbericht.pdf. Céline Van Damme (2008). Geraadpleegd op 7 februari 2009 via http://celinevandamme.com/VanDamme BVD2008.pdf. Flickr (2009). Geraadpleegd op 10 februari 2009 via http://www.flickr.com/services/api/. Flickrj (2008). Geraadpleegd op 10 februari 2009 via http://flickrj.sourceforge.net/. GeoNames (2009). Geraadpleegd op 20 mei 2009 via http://www.geonames.org/. geoOntologies (2003). Geraadpleegd op 12 augustus 2008 via http://www.mindswap.org/2004/geo/geoOntologies.shtml. Google Maps API (2009). Geraadpleegd op 26 mei 2009 via http://code.google.com/intl/nl-BE/apis/maps/. Jena (2000). Geraadpleegd op 20 augustus 2008 via http://jena.sourceforge.net/. Jetty Webserver (2009). Geraadpleegd op 11 mei 2009 via http://www.mortbay.org/jetty/. Kdtree (2006). Geraadpleegd op 22 mei 2009 via http://en.wikipedia.org/wiki/Kd-tree. Lijst van Belgische gemeenten naar bestuurlijke indeling (2008). Geraadpleegd op 11 augustus 2008 via http://nl.wikipedia.org/wiki/Lijst van Belgische gemeenten naar bestuurlijke indeling. Lucene (2009). Geraadpleegd op 7 februari 2009 via http://lucene.apache.org/. RDF Tutorial (2004). Geraadpleegd op 7 februari 2009 via http://www.w3schools.com/rdf.

Literatuurlijst

129

Savarese (2006). Geraadpleegd op 22 mei 2009 via http://www.savarese.com/software/. Sporza (2008). Geraadpleegd op 22 augustus 2008 via http://www.sporza.be/. The Protégé Ontology Editor and Knowledge Acquisition System (2008). Geraadpleegd op 14 augustus 2008 via http://protege.stanford.edu/. Unaccent letters (2008). Geraadpleegd op 11 maart 2009 via http://www.rgagnon.com/javadetails/java-0456.html. Frassek, B. (2006). Astronomie Antwoorden (GrootCirkels). Geraadpleegd op 4 april 2009 via http://www.astro.uu.nl/˜strous/AA/nl/reken/grootcirkel.html. Heaton, J. (2003). Creating a Thread Pool with Java. Geraadpleegd op 4 maart 2009 via http://www.informit.com/articles/article.aspx?p=30483&seqNum=6. Herman, I., Swick, R., & Brickley, D. (2004). Resource Description Framework (RDF). Geraadpleegd op 7 februari 2009 via http://www.w3.org/RDF. Howe, Z. (2006). PHP Tag Cloud. Geraadpleegd op 8 augustus 2008 via http://www.bytemycode.com/snippets/snippet/415/. Lops, J. (2008). Semantische webtechnologie and Federatieve databases. Afstudeerwerk, Rijksuniversiteit Groningen, Faculteit Wiskunde en Natuurwetenschappen, p. 7-19. Geraadpleegd op 7 februari 2009 via http://scripties.fwn.eldoc.ub.rug.nl/scripties/Informatica/Master/2008/Lops.J./. McGuinness, D. L. & van Harmelen, F. (2004). OWL Web Ontology Language Overview. Geraadpleegd op 7 februari 2009 via http://www.w3.org/TR/owl-features. Open Cloud (2008). Open Cloud. Geraadpleegd op 6 augustus 2008 via http://opencloud.sourceforge.net/. Prud’hommeaux, E. & Seaborne, A. (2008). SPARQL Query Language for RDF. Geraadpleegd op 7 februari 2009 via http://www.w3.org/TR/rdf-sparql-query. Sigurbjörnsson, B. & van Zwol, R. (2008). Flickr Tag Recommendation based on Collective Knowledge. Geraadpleegd op 10 februari 2009 via http://www2008.org/papers/pdf/p327-sigurbjornssonA.pdf. Vandamme, S., Deleu, J., Wauters, T., Vermeulen, B., & Turck, F. D. (2009). CROEQS: Contemporaneous Role Ontology-based Expanded Query Search - Implementation and evaluation. Proceedings of the International Conference on Communications Software and Networks (ICCSN), pp. 448–452. Vincenty, T. (1975). Direct and Inverse Solutions of Geodesics on the Ellipsoid with application of nested equations. Geraadpleegd op 6 april 2009 via http://www.ngs.noaa.gov/PUBS LIB/inverse.pdf.

Literatuurlijst

130

WebResources Depot (2008). WebResources Depot. Geraadpleegd op 15 mei 2009 via http://www.webresourcesdepot.com. Weisstein, E. (1999). Great Circle. Geraadpleegd op 4 april 2009 via http://mathworld.wolfram.com/GreatCircle.html. Wojciulewitsch, E. (1988). Cosmografie. Geraadpleegd op 4 april 2009 via http://www.eswo.org/astro/Cosmografie/Cosmografie1.pdf. Zobel, J. & Moffat, A. (2006). Inverted Files for Text Search Engine. ACM Computing Surveys, Vol. 38, No.2, Article 6.

I

Bijlage A

Ontologie Hieronder wordt de volledige beschrijving gegeven van alle gedefinieerde klassen en eigenschappen van de aangemaakte Belgische ontologie:

< !DOCTYPE rdf:RDF [
” h t t p : //www. w3 . o r g /2002/07/ owl#”>

< ! ENTITY xsd ” h t t p : //www. w3 . o r g /2001/XMLSchema#”> ]> Deze ontologie bevat klassen , properties , individuals voor de beschrijving van Belgie < !−− CLASSES −−> < r d f s : l a b e l>Gebied < r d f s : l a b e l>Land < r d f s : l a b e l>Gewest

Bijlage A. Ontologie < r d f s : l a b e l>Provincie < r d f s : l a b e l>Arron disseme nt < r d f s : l a b e l>Gemeente < r d f s : r a n g e r d f : r e s o u r c e=”&xsd ; s t r i n g ” /> Synoniem voor het gebied ( Frans ) < !−− TOPOLOGICAL RELATION −−>
r d f : r e s o u r c e=”#Gebied ” />

< r d f s : r a n g e r d f : r e s o u r c e=”#P r o v i n c i e ” /> < r d f s : r a n g e r d f : r e s o u r c e=”#A r r o n d i s s e m e n t ” />

II

Bijlage A. Ontologie < r d f s : r a n g e r d f : r e s o u r c e=”#Gemeente ” /> < !−− I n d i v i d u a l s −−> ...

III

IV

Bijlage B

Geonames (1) Tabel B.1 geeft een overzicht van de subcategorieën waarin categorie A is onderverdeeld. Tabel B.2 toont eveneens een overzicht, maar dan van de subcategorieën van categorie P. Alle categorieën zijn terug te vinden op de site van Geonames1 . Ten slotte toont tabel B.3 alle velden die zijn opgenomen in het allCountries.txt bestand van Geonames. Tabel B.1: Subcategorieën horende bij categorie A

A country, state, region,. . . ADM1

first-order administrative division

a primary administrative division of a country, such as a state in the United States

ADM2

second-order administrative division

a subdivision of a first-order administrative division

ADM3

third-order administrative division

a subdivision of a second-order administrative division

ADM4

fourth-order administrative division

a subdivision of a third-order administrative division

ADMD

administrative division

an administrative division of a country, undifferentiated as to

LTER

leased area

PCL

political entity

PCLD

dependent political entity

PCLF

freely associated state

PCLI

independent political entity

PCLIX

section of independent political entity

PCLS

semi-independent political entity

PRSH

parish

TERR

territory

ZN

zone

ZNB

buffer zone

administrative level a tract of land leased by the United Kingdom from the People’s Republic of China to form part of Hong Kong

an ecclesiastical district

a zone recognized as a buffer between two nations in which military presence is minimal or absent

1

http://www.geonames.org/export/codes.html

Bijlage B. Geonames (1)

V

Tabel B.2: Subcategorieën horende bij categorie P

P city, village,. . . PPL PPLA

a city, town, village, or other agglomeration of buildings where

populated place seat

of

a

first-order

people live and work administrative

division

PPLC

capital of a political entity

PPLG

seat of government of a political entity

PPLL

populated locality

PPLQ

abandoned populated place

PPLR

religious populated place

PPLS

populated places

PPLW

destroyed populated place

PPLX

section of populated place

STLMT

israeli settlement

seat of a first-order administrative division (PPLC takes precedence over PPLA)

an area similar to a locality but with a small group of dwellings or other buildings a populated place whose population is largely engaged in religious occupations cities, towns, villages, or other agglomerations of buildings where people live and work a village, town or city destroyed by a natural disaster, or by war

Bijlage B. Geonames (1)

VI

Tabel B.3: Velden van de ’geoname’ tabel

geonameid

integer id of record in geonames database

name

name of geographical point (utf8) varchar(200)

asciiname

name of geographical point in plain ascii characters, varchar(200)

alternatenames

alternatenames, comma separated varchar(4000) (varchar(5000) for SQL Server)

latitude

latitude in decimal degrees (wgs84)

longitude

longitude in decimal degrees (wgs84)

feature class

see http://www.geonames.org/export/codes.html, char(1)

feature code

see http://www.geonames.org/export/codes.html, varchar(10)

country code

ISO-3166 2-letter country code, 2 characters

cc2 admin1 code admin2 code

alternate country codes, comma separated, ISO-3166 2-letter country code, 60 characters fipscode (subject to change to iso code), isocode for the us and ch, see file admin1Codes.txt for display names of this code; varchar(20) code for the second administrative division, a county in the US, see file admin2Codes.txt; varchar(80)

admin3 code

code for third level administrative division, varchar(20)

admin4 code

code for fourth level administrative division, varchar(20)

population

bigint (4 byte int)

elevation

in meters, integer

gtopo30

average elevation of 30’x30’ (ca 900mx900m) area in meters, integer

timezone

the timezone id (see file timeZone.txt)

modification date

date of last modification in yyyy-MM-dd format

VII

Bijlage C

Geonames (2) Onderstaande code geeft de implementatie van de getRectangleKeywords(double north, double west, double south, double east) methode uit de NearestPlaces klasse. Deze methode geeft alle GeoKeywords terug die gelegen zijn binnen een rechthoek, gespecificeerd door de vier parameters:

p r i v a t e KDTree kdTree ; p r i v a t e HashMap<String , GeoKeyword> nameMap ; p r i v a t e List g e t R e c t a n g l e K e y w o r d s ( d o u b l e north , d o u b l e west , d o u b l e south , d o u b l e east ) { List list = new ArrayList() ; i n t n u m b e r R e c t a n g le s = 0 ; d o u b l e [ ] northList ; d o u b l e [ ] westList ; d o u b l e [ ] southList ; d o u b l e [ ] eastList ; // 4 z o e k r u i m t e s if

( ( north > 90 | | south < −90) && ( east > 180 | | west < −180) ) { n u m b e r R e c t a n g le s = 4 ; northList = new d o u b l e [ 4 ] ; westList = new d o u b l e [ 4 ] ; southList = new d o u b l e [ 4 ] ; eastList = new d o u b l e [ 4 ] ; northList [ 0 ] = 9 0 ; northList [ 1 ] = 9 0 ; westList [ 0 ] = −180; westList [ 2 ] = −180; southList [ 2 ] = −90; southList [ 3 ] = −90; eastList [ 1 ] = 1 8 0 ; eastList [ 3 ] = 1 8 0 ; i f ( north > 9 0 ) { northList [ 2 ] = north −180; northList [ 3 ] = north −180; southList [ 0 ] = south ; southList [ 1 ] = south ; } else{ northList [ 2 ] = north ; northList [ 3 ] = north ; southList [ 0 ] = south +180; southList [ 1 ] = south +180; } i f ( west < −180) { westList [ 1 ] = west +360; westList [ 3 ] = west +360; eastList [ 0 ] = east ; eastList [ 2 ] = east ; }

Bijlage C. Geonames (2)

VIII

else{ westList [ 1 ] = west ; westList [ 3 ] = west ; eastList [ 0 ] = east −360; eastList [ 2 ] = east −360; } } // 2 z o e k r u i m t e s else

if

( ( north > 90 | | south < −90) | | ( east > 180 | | west < −180) ) {

n u m b e r R e c t a n g le s = 2 ; northList = new d o u b l e [ 2 ] ; westList = new d o u b l e [ 2 ] ; southList = new d o u b l e [ 2 ] ; eastList = new d o u b l e [ 2 ] ; i f ( north > 90 | | south < −90){ westList [ 0 ] = west ; westList [ 1 ] = west ; eastList [ 0 ] = east ; eastList [ 1 ] = east ; northList [ 0 ] = 9 0 ; northList [ 1 ] = ( north >90) ? north −180: north ; southList [ 1 ] = −90; southList [ 0 ] = ( south <−90) ? south +180: south ; } else{ northList [ 0 ] = north ; northList [ 1 ] = north ; southList [ 0 ] = south ; southList [ 1 ] = south ; westList [ 1 ] = −180; westList [ 0 ] = ( west <−180) ? west +360: west ; eastList [ 0 ] = 1 8 0 ; eastList [ 1 ] = ( east >180) ? east −360: east ; } } // 1 z o e k r u i m t e else{ n u m b e r R e c t a n g le s = 1 ; northList = new d o u b l e [ 1 ] ; westList = new d o u b l e [ 1 ] ; southList = new d o u b l e [ 1 ] ; eastList = new d o u b l e [ 1 ] ; northList [ 0 ] = north ; westList [ 0 ] = west ; southList [ 0 ] = south ; eastList [ 0 ] = east ; } f o r ( i n t i =0; i> it = kdTree . iterator ( new GenericPoint ( westList [ i ] , southList [ i ] ) , new GenericPoint ( eastList [ i ] , northList [ i ] ) ) ; w h i l e ( it . hasNext ( ) ) { list . add ( it . next ( ) . getValue ( ) ) ; } } r e t u r n list ; }

IX

Bijlage D

Handleiding bij CD-ROM Op bijgevoegde CD-ROM vindt u naast de scriptie in PDF-formaat (scriptie AnDeMoor.pdf), ook de geproduceerde programmacode terug in de map code. Deze map bevat zes projecten, die telkens werden aangemaakt in de ontwikkelingsomgeving Netbeans: 1. tagclouds 2. ontologie/ontologie belgie 3. ontologie/voetbalontologie 4. flickr/flickr test 5. flickr/flickr bom 6. geonames Deze projecten zijn bedoeld om te onderzoeken hoe de zoekopdrachten van multimediale databases kunnen worden geoptimaliseerd.

Project ´ e´ en, tagclouds, zorgt voor de generatie van tag clouds, zoals beschreven in hoofdstuk één van deze scriptie. De applicatie kan enkel worden uitgevoerd op INTEC, aangezien deze gebruikmaakt van de BOM-zoekmachine die lokaal op INTEC beschikbaar is. Hiervoor is een jar-bestand ter beschikking in de map code\tagclouds\uitvoering.

De applicatie kan worden

opgestart vanuit een command prompt, als volgt: • java -jar tagclouds.jar

Projecten twee en drie zorgen voor de generatie van ontologieën, zoals besproken in het tweede hoofdstuk:

Bijlage D. Handleiding bij CD-ROM

X

Aan de hand van het tweede project, ontologie belgie, kan een ontologie van België worden opgesteld. Deze ontologie is reeds beschikbaar in de map code\ontologie\ontologie belgie, onder de naam belgie.owl. Eventueel kan deze opnieuw worden aangemaakt, door de volgende opdracht uit te voeren: • java -jar ontologie belgie.jar inputdef inputdata output Ook dit jar-bestand is beschikbaar in de map code\ontologie\ontologie belgie\uitvoering. De laatste drie termen van de opdracht specificeren de parameters: met de parameter inputdef wordt het bestand aangeduid dat vooropgestelde definities bevat. Er is reeds een bestand aanwezig, belgie definities.txt, waarin alle nodige definities zijn vastgelegd. De tweede parameter, inputdata, duidt de map aan die alle nodige informatie over gebieden van België bevat. Deze map bevindt zich reeds in de map uitvoering, onder de naam ontologiedata. Als laatste wordt door middel van de parameter output gespecificeerd in welk bestand de uitvoer moet terechtkomen. Dit bestand bevat na uitvoeren van het programma, de volledige ontologie van België. Indien geen parameters worden gespecificeerd in de uitvoeringsopdracht, worden automatisch de reeds aanwezig bestanden als invoer gebruikt. De uitvoer wordt dan automatisch weggeschreven naar belgie.owl.

Het

derde

project,

voetbalontologie,

over het voetbal op te stellen.

bevat

de

nodige

code

om

een

ontologie

Het uitvoeringsbestand is beschikbaar in de map

code\ontologie\voetbalontologie\uitvoering, onder de naam ontologie voetbal.jar.

Dit kan als

volgt worden uitgevoerd: • java -jar ontologie voetbal.jar output De parameter output specificeert waar de ontologie moet worden naartoe geschreven. Als invoer wordt automatisch beroep gedaan op enkele bestanden die reeds aanwezig zijn in de map: als eerste het bestand hoofding.owl, dat de nodige definities bevat, en ook de bestanden gespecificeerd in de map invoer.

Projecten vier en vijf horen bij hoofdstuk drie, dat de relaties tussen tags onderzoekt: Het vierde project, flickr test, hoort bij paragraaf 3.3 van de scriptie. Hiermee kunnen relevante tags voor een bepaalde tag worden opgezocht. Om deze te bepalen, kan de volgende opdracht worden uitgevoerd: • java -jar flickr test.jar input i/t a/f Dit jar-bestand bevindt zich in de map code\flickr\flickr test\uitvoering. De parameter input specificeert voor welk foto id of voor welke tag(s) relevante tags moeten worden gezocht. Indien een id van een Flickr foto wordt meegegeven (bijvoorbeeld 521193180 ), moet als tweede parameter


XI

i worden opgegeven. Hierdoor worden relevante tags gezocht, op basis van alle tags die zijn opgenomen bij de foto. Er kunnen ook zelf één of meerdere tags (gescheiden door ’;’) als input worden meegegeven. Als tweede parameter moet dan de waarde t worden opgegeven. De laatste parameter specificeert welke methode moet worden gebruikt om relevante tags op te zoeken: de Flickr methode (waarde f ), of de alternatieve methode (waarde a), zoals beschreven in paragraaf 3.3. Relevante tags worden als uitvoer weggeschreven naar twee bestanden, aanwezig in de map data: asymres.txt en symres.txt. Deze bevatten de relevante tags, die worden gegenereerd op basis van de asymmetrische of symmetrische coëfficiënt. Het kan even duren vooraleer de uitvoer naar deze bestanden wordt geschreven. Het programma is namelijk enkel bedoeld als testapplicatie, en is bijgevolg niet geoptimaliseerd met bijvoorbeeld een thread mechanisme.

Het vijfde project, flickr bom, bevat de code die een eigen dataset opstelt, om relevante tags voor BOM-keywords te bepalen. Hiervoor zijn de vier programma’s beschikbaar, zoals beschreven in paragraaf 3.4.2. (CreatePhotoFile, CreateTagFile, CreateRandomPhot en CreateImages). Deze kunnen als volgt worden uitgevoerd: • java -cp flickr bom.jar programs.CreatePhotoFile input output begin end • java -cp flickr bom.jar programs.CreateTagFile input output ’photos’/’photorandom’ begin end • java -cp flickr bom.jar programs.CreateRandomPhoto output • java -cp flickr bom.jar programs.CreateImages input begin end

Het jar-bestand bevindt zich in de map code\flickr\flickr bom\uitvoering. Met behulp van het eerste programma, CreatePhotoFile, worden foto id’s opgehaald, voor elk vertaald BOM-keyword dat aanwezig is in het input bestand.

Alle BOM-keywords zijn reeds aanwezig in het

bestand code\flickr\flickrb om\uitvoering\data\allkeywords.txt. Dit kan als input parameter worden meegegeven. De foto id’s worden per keyword weggeschreven naar het output bestand.

Het tweede programma, CreateTagFile, kan worden gebruikt om alle tags op te halen, die bij bepaalde foto id’s horen. De foto id’s waarvoor tags moeten worden opgehaald, bevinden zich in het input bestand. Als invoer hiervoor wordt het uitvoerbestand van het eerste of derde programma gebruikt. Indien het uitvoerbestand van CreatePhotoFile wordt gebruikt, wordt als derde parameter ’photos’ opgegeven. Zoniet wordt ’photorandom’ opgegeven, en moet het uitvoerbestand van CreateRandomPhoto worden gebruikt. De tags worden per foto id weggeschreven naar het output bestand. Om dit te realiseren, wordt als hulp een databank gebruikt. Het schema van deze databank bevindt zich in het bestand code\flickr\flickr bom\uitvoering\photos.sql. De databank is een eenvoudige MySQL databank, en kan bijvoorbeeld worden beheerd met phpMyAdmin1 . 1

Meer informatie over phpMyAdmin bevindt zich op de site http://www.phpmyadmin.net/


XII

Het derde programma, CreateRandomPhoto, haalt random foto id’s op en schrijft deze id’s weg naar het output bestand. De afbeeldingen die bij deze foto id’s horen, kunnen worden opgehaald en opgeslagen met behulp van het vierde programma, CreateImages. Als input waarde moet de naam van het uitvoerbestand van het derde programma worden meegegeven. Alle paden (input en output parameters) moeten relatief worden ingegeven ten opzichte van de map code\flickr\flickr bom\uitvoering\data. Eventueel kunnen bij het eerste, tweede en vierde programma twee extra parameters (begin en end ) worden opgegeven, die een begin- en eindregel opgeven van het input bestand. Zo wordt enkel de data tussen deze twee grenzen uit het input bestand verwerkt.

Het zesde en laatste project, geonames, bevat alle geproduceerde programmacode die hoort bij hoofdstuk vier. Dit project bestaat uit een twintigtal klassen, die elk uitvoer produceren om BOM-geonames te bepalen en te onderzoeken.

Twee van deze klassen, GeoServlet en

DistanceServlet, voorzien servlets die het mogelijk maken om semantische query’s te kunnen uitvoeren.

Deze servlets kunnen terug enkel op INTEC worden uitgevoerd, aangezien deze

terug de BOM-zoekmachine nodig hebben.

Er is wel een jar-bestand voorzien in de map

code\geonames\uitvoering, met als naam geonames.jar. Hiermee kan de uitvoer worden gegenereerd voor elke klasse, als volgt: • java -cp geonames.jar klasse eventuele invoerparameters Hierbij duidt de parameter klasse de klassenaam aan, gevolgd door eventuele invoerparameters. De map code\geonames\uitvoering bevat ook een bestand geonames evaluatie.xls, die de resultaten van de evaluatie voor elke geoname bevat.

De uitvoer van sommige programma’s van deze projecten vereisen veel geheugen. Het is dan ook soms nodig om bij de uitvoeringsopdrachten een extra parameter mee te geven, die ervoor zorgt dat er genoeg geheugen wordt gealloceerd om de programma’s uit te voeren. Indien er bijvoorbeeld 2048 MB geheugen moet worden gealloceerd, kan dit als volgt: • java -Xmx2048m . . . Alle uitvoerbestanden die reeds werden geproduceerd, bevinden zich op een lokale server, en niet op de bijgevoegde cd-rom, aangezien deze bestanden in totaal enkele gigabytes groot zijn.

De jar-bestanden van alle gebruikte bibliotheken bevinden zich per project in de map lib, die zich op zijn beurt bevindt in de map uitvoering van elk project.

Optimalisatie van zoekopdrachten voor multimediabestanden

Recommend Documents