Zoekfunctionaliteit StamboomNederland

TU Delft TI3800 Bachelor’s Project - 42 Eind Raport

Zoekfunctionaliteit StamboomNederland

Auteurs: Maikel Langezaal Pouja Nikray

Co¨ ordinatoren: M.A. Larson (Vak co¨ordinator) C. Hauff (TU Delft coach) M. Huizing (42)

23 juli 2014

Voorwoord Na 12 weken voltijds te hebben gewerkt hebben wij onze stage periode bij 42 afgerond. In die weken hebben wij gewerkt aan verschillende onderdelen van de nieuwe zoekfunctionaliteit voor de website StamboomNederland. Het was een lange periode en helaas was het niet volgens de planning gegaan door verkeerde tijdsduur inschattingen. We hebben het wel als een leerzame periode ervaren en de ervaringen kunnen we meenemen naar toekomstige projecten. We willen ten eerste Mat Huizing bedanken voor de mogelijkheid om bij 42 onze stage te houden, daarnaast willen we Ailbert Riksen en Robert Bor van 42 bedanken voor hun steun tijdens het project. Voor advies en hulp met de query segmentation en het gehele project willen wij begeleidster Claudia Hauff bedanken. Als laatst willen we ook Tiddo Langerak bedanken voor zijn hulp omtrent PostgreSQL. Maikel Langezaal en Pouja Nikray 22 juli 2014

Samenvatting In opdracht van het bedrijf 42 is er een nieuwe zoekfunctionaliteit ontwikkelt voor het systeem StamboomNederland, dit systeem is in opdracht van het Centraal Bureau voor Genealogie (CBG) ontwikkelt door 42. Het systeem bevat genealogische data voor het bijhouden van stambomen. De huidige zoekfunctionaliteit werkt echter niet naar behoren vandaar de opdracht voor een nieuwe zoekfunctionaliteit, voor deze nieuwe zoekfunctionaliteit is gekozen voor de ontwikkeling voor een systeem dat gebruik maakt van query segmentatie. Query Segmentatie houdt in dat de gebruiker door middel van een gewone zoekbalk een zoekopdracht invult welk wordt ontleed in segmenten, oftwel delen, welk vervolgens bepaalde labels worden toegewezen aan de hand van een ontwikkeld algoritme. Het ontworpen algoritme is aan de hand van onderzoek naar bestaande projecten ontwikkeld en toegepast op het bestaande systeem van Stamboom Nederland waar ook het nodige onderzoek voor is gedaan aan de hand van query logs en het uitvoeren van vragenlijsten met gebruikers. Dit was om te kijken hoe deze zoekopdrachten zouden uitvoeren gegeven het query segmentatie zoek systeem. Het uiteindelijke systeem is getest door middel van een gebruikers test welk positieve resultaten gaf ten opzichte van de oude zoek functionaliteit.

2

Inhoudsopgave 1 Inleiding 2 Project omschrijving 2.1 Het bedrijf . . . . . 2.2 Project Achtergrond 2.3 De website . . . . . . 2.4 Probleem Definitie .

5

. . . .

5 5 6 6 8

3 Planning en Requirements 3.1 Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Aanpak en tijdsplanning . . . . . . . . . . . . . . . . . . . . .

9 9 11

4 Onderzoek 4.1 Huidige Zoek Implementatie . . . . . . . 4.1.1 PostgreSQL Functie: to tsvector 4.1.2 PostgreSQL Functie: to tsquery 4.1.3 PostgreSQL Functie: ts rank . . 4.1.4 Implementatie . . . . . . . . . . 4.1.5 Gebreken . . . . . . . . . . . . . 4.2 Query Log . . . . . . . . . . . . . . . . . 4.3 Vragenlijst 1 . . . . . . . . . . . . . . . 4.4 Vragenlijst 2 . . . . . . . . . . . . . . . 4.4.1 Onderzoek . . . . . . . . . . . . 4.4.2 Resultaten . . . . . . . . . . . . 4.5 Query Segmentation: Literatuur . . . . 4.5.1 Stappen . . . . . . . . . . . . . . 4.5.2 Segmentatie . . . . . . . . . . . . 4.5.3 Labeling . . . . . . . . . . . . . . 4.5.4 Hidden Markov Modellen . . . .

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

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

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

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

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

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

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

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

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

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

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

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

15 15 16 16 16 16 17 17 19 21 22 23 25 26 26 29 29

5 Ontwerp en Implementatie 5.1 Uitgebreid Zoeken: Frontend 5.2 Uitgebreid Zoeken: Backend . 5.3 Rest API . . . . . . . . . . . 5.4 Query segmentation . . . . . 5.4.1 Stap 1: Segmenten . . 5.4.2 Stap 2: Paden . . . . 5.4.3 Stap 3: Sterkste pad .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

30 31 32 33 33 34 36 36

. . . .

. . . .

. . . .

. . . .

. . . .

3

. . . .

. . . . . . .

. . . .

. . . . . . .

. . . .

. . . . . . .

. . . .

. . . . . . .

. . . .

. . . . . . .

. . . .

. . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

5.4.4 5.4.5

Overzicht algoritme . . . . . . . . . . . . . . . . . . . Resultaat . . . . . . . . . . . . . . . . . . . . . . . . .

6 Tests 6.1 Unit Test . . . . . . . . . . . . 6.1.1 SIG . . . . . . . . . . . 6.2 User Test . . . . . . . . . . . . 6.2.1 Doel . . . . . . . . . . . 6.2.2 Opstelling en uitvoering 6.2.3 Resultaten . . . . . . . 6.2.4 Commentaar . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

7 Conclusie

38 39 39 39 40 40 40 41 42 42 43

A Appendix A - Omschrijving Zoekfunctionaliteit van CBG 47 A.1 Korte termijn[in zijn geheel hoge prioriteit] . . . . . . . . . . 47 A.2 Lange termijn[in zijn geheel lage prioriteit] . . . . . . . . . . . 48 B Appendix B - Interview Met 42

50

C Appendix C - Eerste Vragenlijst C.1 Introductie vragenlijst . . . . . C.2 Eerste Biografie . . . . . . . . . C.3 Tweede Biografie . . . . . . . . C.4 Derde Biografie . . . . . . . . . C.5 Vierde Biografie . . . . . . . . .

51 51 51 52 52 53

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

D Appendix D - Tweede Vragenlijst 54 D.1 Introductie Vragenlijst . . . . . . . . . . . . . . . . . . . . . . 54 D.2 Vragen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 E Appendix F - SIG Commentaar 56 E.1 Aanbevelingen . . . . . . . . . . . . . . . . . . . . . . . . . . 56 E.2 Hermeting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 F Appendix G - Stamboompuzzels Usertest

58

G Appendix G - Database Model

61

4

1

Inleiding

Dit is het eindrapport van het Bachelor Project over query segmentation. De opdracht vanuit het bedrijf is om de zoekfunctionaliteit te verbeteren van de huidige zoekmachine op de website van StamboomNederland1 . Het project is om voor deze zoekmachine een vervangende zoekfunctionaliteit te ontwikkelen wat de mogelijkheid moet geven om door middel van vrije tekst, oftewel spraak tekst, zoekopdrachten te kunnen uitvoeren. Hierbij wordt de zoek tekst van de gebruiker opgedeeld in segmenten, waar dan in enkele stappen vervolgens een zoek query van wordt gemaakt, deze kan dan vervolgens worden gebruikt om een zoekopdracht uit te voeren. Er moet worden gezorgd dat de query segmentation effici¨ent wordt gedaan, waarbij effici¨ent inhoud dat de gebruiker zo vaak mogelijk de juiste zoekresultaten krijgt en de zoektijd beperkt is. Om dit te realiseren zal er een algoritme worden bedacht welk toepasbaar is op de database en verwachte zoektermen van StamboomNederland. Allereerst zal een beschrijving worden gegeven van het bedrijf en de achtergrond van de opdracht. Vervolgens wordt de planning en de eisen gegeven die gevolgd worden door de onderzoeksfase. Na de onderzoeksfase komt het ontwerp en de uiteindelijke implementatie. Als laatst wordt de test fase besproken.

2

Project omschrijving

De project opdracht is voortgekomen uit een probleem welk het bedrijf had waar de opdracht voor wordt uitgevoerd. Het bedrijf en het probleem dat deze hadden wordt in deze sectie eerst besproken. Tevens wordt er uitgelegd hoe het huidige project in elkaar zit en wat hierbij het probleem is dat moet worden verbeterd. Als laatste wordt de gekozen oplossing voor dit probleem besproken en wat deze inhoudt.

2.1

Het bedrijf

StamboomNederland, het project waar binnen de opdracht plaats vind, is ontwikkeld door het bedrijf 42 waar ook dit project voor wordt uitgevoerd. Het bedrijf 42 staat voor de realisatie van kwalitatief hoogwaardige maatwerk van software op het JAVA platform en voor iOS App development. 1

http://wwww.stamboomnederland.nl

5

42 is opgericht in 2003 als een in JAVA gespecialiseerd software bedrijf en in 2009 samengegaan met Kensas, een expert in maatwerk oplossingen voor complexe vraagstukken. Hierdoor ontstond er een ICT organisatie met zo’n 35 eigen medewerkers met een hoofdkantoor in Zoetermeer. Om waar te maken dat 42 daadwerkelijk het ultieme antwoord” is, richten deze zich ” op het ontwikkelen van hoogwaardige oplossingen en diensten.

2.2

Project Achtergrond

In opdracht van het Centraal Bureau van Genealogie heeft 42 een systeem ontwikkeld, waarbij mensen en gebeurtenissen kunnen worden ingevoerd. Vervolgens kan er een stamboom worden gegenereerd met alle relaties die er plaats vinden tussen deze personen en gebeurtenissen. Daarnaast is er een mogelijkheid om op een persoon of gebeurtenis in je eigen of in projecten van andere te zoeken en te kijken naar de gegevens van deze persoon en zijn relatie met andere mensen. In het huidige systeem van StamboomNederland is nu opgenomen een fuzzy search”, welk nu gebruik maakt van een full tekst search door middel ” van PostgreSQL statements. Echter is de huidige implementatie van de zoekfunctionaliteit met full tekst search beperkt en werkt niet naar behoren. Vanuit CBG is de wens om een uitgebreide zoekfunctionaliteit te bieden aan de gebruikers. De gewenste zoekfunctionaliteit vanuit de opdrachtgever moet het mogelijk maken om de gebruiker te laten zoeken op verschillende velden. Dit is waar de opdracht zich mee bezig houd. In het kort moet het mogelijk zijn voor de gebruiker om vanuit de front-end op een simpele manier naar verschillende velden te kunnen zoeken.

2.3

De website

Om de project opdracht duidelijk vast te leggen zal hier worden omschreven wat het project is, waarvoor deze wordt gebruikt en welke functionaliteiten deze biedt. Vervolgens wordt het probleem gedefinieerd en vastgelegd wat de rode lijn is van het project. Na het vast stellen van hoe het huidige project nu is en de op te lossen problemen zijn vastgesteld zijn de voorwaarden vast gelegd en opgesteld in een MoSCoW model. StamboomNederland biedt de gebruiker de mogelijkheid om zijn of haar genealogische data te uploaden naar de website en te beheren. Gebruikers kunnen vervolgens de stamboom verder bewerken of een nieuwe stamboom

6

Figuur 1: Een screen shot van de homepage van StamboomNederland toevoegen door personen te maken. In figuur 1 wordt de homepage van de website weergegeven. Bij beheren van de personen, kunnen relaties worden aangegeven, zoals ouder-kind relatie of partner relatie. Een relatie wordt voor de website als een feit gezien, maar er kunnen ook andere feiten worden gekoppeld aan personen, bijvoorbeeld om aan te geven welke banen hij of zij heeft gehad, wanneer de bar-mitzvah heeft plaats gevonden, of wanneer hij of zij gedoopt is etc. Verder kan er een visuele representatie worden weergegeven van alle relaties tussen personen binnen een stamboom. De zoekfunctionaliteit van de website om naar personen te zoeken werkt zoals eerder genoemd met een fuzzy search”. Er kan hiermee gezocht wor” den op basis van voornaam, achternaam, plaats van geboorte en sterfte en op basis van de geboorte/sterf datum. Er worden alleen personen getoond die publiek open staan en of waarvan de gehele stamboom publiek van open staat. De gebuikers bepalen zelf of hun stamboom publiek open staat of niet.

7

2.4

Probleem Definitie

Het zoek systeem van StamboomNederland zoals deze nu is werkt niet naar behoren en bevat niet alle functionaliteiten die gewenst zijn. Het huidige systeem gebruikt een algoritme welk veel irrelevante en onnauwkeurige zoekresultaten geeft, vaak komen er zelfs geen eens relevante resultaten voor de gegeven zoekopdracht. Dit komt door de manier waarop PostgreSQL werkt zoals besproken in sectie 4.1. Daarnaast is de zoek functie van de website niet uitgebreid en zouden, door toevoeging van extra functionaliteit, gebruikers preciezer kunnen zoeken zoals gewenst door het CBG. WieWasWie2 is net zoals StamboomNederland een website om genealogische data te beheren. Vanuit CBG was de wens om WieWasWie gebruik te laten maken van data van StamboomNederland. Hiervoor is er een protocol nodig om een communicatie tussen beide websites op te zetten. Verder moet er rekening worden gehouden dat de zoek functionaliteit van beide sites op elkaar mappen. Vandaar dat de wens vanuit het CBG was om een geadvanceerde zoekmachine te ontwikkellen, zodat deze velden kunnen worden gebruikt voor het mappen van de zoekfunctionaliteit van WieWasWie. Verder houdt dit project zich niet bezig met andere ontwikkellingen op het gebied van WieWasWie. Door middel van toevoeging van query segmentation moet het mogelijk worden om met een vrije tekst te zoeken, dit houdt in dat er met zinnen zoals: Kees Janssen uit Amsterdam die is overleden in 1943” kan wor” den gezocht in plaats van met gestructureerde tekst of webforms. Hierdoor blijft de mogelijkheid voor keyword search beschikbaar maar wordt deze uitgebreid met herkennen van tekst en in de achtergrond een geadvanceerde zoek opdracht uit te voeren. Door deze tekst dan op te delen in segmenten en deze segmenten vervolgens aan de juiste labels te verwijzen, waarbij de labels afhankelijk zijn van de informatie die uit de database kan worden opgehaald. Zo wordt uit de gegeven query bijvoorbeeld gehaald de Naam: Kees Janssen”, Plaats: Amsterdam”, Jaar: 1943” welk dan vervolgens ” ” ” kunnen worden omgezet als een gestructureerde query. Waarna deze vervolgens kan worden gebruikt als zoekopdracht om relevante zoekresultaten voor de gegeven zoekopdracht te vinden. 2

https://www.wiewaswie.nl/

8

3

Planning en Requirements

Door het opstellen van de eisen van het project wordt het overzicht van het project een stuk duidelijker. Aan de hand van de opgestelde eisen en verwachte tijd die hiervoor nodig is naast andere taken en onderzoek wat moet worden uitgevoerd kon er een planning worden opgesteld wat een overzicht geeft van de geplande weken van dit project. In deze sectie wordt een overzicht gegeven van de opgestelde eisen aan het project en hoe deze tot stand zijn gekomen. Daarnaast wordt de planning vast gelegd hoe het project zal verlopen zoals verwacht en hoe dit uiteindelijk is verlopen.

3.1

Requirements

Voor het opstellen van de eisen is gekeken naar ontbrekende functionaliteit van de huidige zoekmachine. Daarnaast is er overlegd met 42 over de eisen die zijn gesteld door het CBG aan de hand van door hun geleverd document, zie bijlage A.2. Voor de query segmentation zijn er eisen opgenomen welk het belangrijkste werden gevonden voor CBG. Qua functionaliteit was dit dat er vooral moest kunnen worden gezocht op verschillende velden met eventuele onbekende letters in zowel eigen als open projecten. Aan de hand van de beschreven problemen en de wensen van CBG is een MoSCoW model, zie tabel 1, opgezet om een overzicht te hebben over alle functionele eisen.

9

Tabel 1: Het MoSCoW model voor alle functionele eisen. De ’M’ staat voor must, ’S’ should, ’C’ voor could, ’W’ voor would. # Eisen Prioriteit F0 Moet gezocht kunnen worden op: voornaam, tussenvoegsel, M achternaam, patroniem, (range) geboorte/sterf datum F1 Met ´e´en enkele zoekbar moet er gezocht worden naar alle M velden die in F0 zijn opgenomen F2 Zoeken in publieke projecten M F3 Zoeken in afzonderlijke projecten (projecten van andere ge- M bruikers) F4 Zoeken met een of meerdere onbekende letters (Ann? voor M Anne of Anna) F5 Via een REST api zoeken M F6 User interface voor het zoeken moet de mogelijkheid bieden M om te zoeken zoals in F1 is aangegeven F7 User interface voor het weergeven van de zoekresultaten S moet overzichtelijker worden F8 Zoeken op feiten C F9 Zoeken op broninformatie C F10 Zoeken op notities (De omschrijving van een feit) C F11 Zoeken op id-nummer (Het nummer van een persoon in de C database) F12 Zoeken op beroep en of rol C Naast de functionele eisen zijn er ook nog randvoorwaarden waar het opgeleverde product aan moet voldoen. Deze voorwaarden, zie tabel 2, zijn opgesteld aan de hand van de huidige situatie waarin het systeem werkt en aan welke kwaliteiten de query segmentation moet voldoen.

10

# N0 N1 N2 N3 N4 N5

Tabel 2: Randvoorwaarden Eisen Het moet draaien op Ubuntu 12.04 Het moet non-blocking zijn Het moet kunnen communiceren met PostgreSQL Het moet draaien in een TomCat omgeving Query segmentation Binnen ´redelijk´tijd zoekresultaten weergeven 80% van de geldige queries moeten succesvol worden ge¨ınterpreteerd, geldige queries betekent dat deze binnen het zoekdomein liggen zoals namen, jaren en plaatsen

Het domein waarin de zoekfuncationaliteit moet werken wordt ook meegenomen in het ontwerp. Zo kunnen gebruikers niet alle mogelijke vragen stellen, zoals Wat wordt het weer voor morgen”. De website functioneert ” in een beperkt domein, daarom is het nodig om af te bakenen wat voor queries geldig en zinvol zijn om te beantwoorden. Zoals beschreven in sectie 2.4 beheert StamboomNederland genealogische data. Dat is informatie over het leven van een bepaalde persoon of personen. Specifieker: het gaat alleen om informatie over gebeurtenissen van personen en welke rollen de personen hebben. Met gebeurtenissen wordt er bedoeld: geboorte, sterfte, eerste huisdier, verloving etc. En met rollen wordt er voornamelijk bedoelt of een persoon een kind van, een vader van, moeder van of partner van is. Queries die binnen dit domein vallen worden geldig verklaart.

3.2

Aanpak en tijdsplanning

Naast de daadwerkelijke implementatie van het systeem, met alle vastgelegde eisen en functionaliteiten, zal moeten worden onderzocht hoe de zoek functionaliteit met query segmentation kan worden uitgebreid en hoe het algoritme voor de query segmentation moet worden uitgewerkt om het gewenste resultaat te behalen. Daarnaast zijn er naast de project opdracht zelf nog andere deliverables welke moeten worden gedaan aan verslagen voor de BEP en andere punten voor een goed verloop van het gehele proces tijdens het project. Ook zijn er nog enkele wensen vanuit 42 welk ook deels nodig zijn voor het uit te voeren van het project. Om er voor te zorgen dat er op schema wordt gebleven is er een tijdschema, zie tabel 3.2, gemaakt zoals verwacht wordt dat de planning zal zijn. Er zal een weekelijkse scrum sprint worden gehouden.

11

week 1 • Bekend worden met de gebruikte tools en code • Systeem en probleem analyseren • Deliverables: Geen week 2 • Opstellen van functionele en kwalitatieve eisen • Maken van een planning • Onderzoek naar query segmentation • Deliverables: Plan van aanpak week 3 en 4 • Query log implementeren • Het huidige zoek algoritme documenteren • Verder onderzoek naar query segmentation • Query log analyseren en documenteren • Gebruiker vragenlijst opstellen en data verwerken • Beginnen aan implementatie van afzonderlijke velden • Placeholder toevoegen voor verbeteren van verkrijgende data query log • Deliverables: Usertest documentatie week 5 • Agile week #1 • Nieuwe data vragenlijst analyseren en documenteren • Zoeken op afzonderlijke velden interface en functie implementatie afronden • Deliverables: Algoritme, Back-end afzonderlijke velden zoeken, de REST api week 6 • Agile week #2 12

• Opstellen van zoek algoritme voor query segmentatie • Segmentatie gedeelte uitwerken/implementeren • Deliverables: Geen week 7 • Agile week #3 • Segmentatie afwerken • Labelen van segmenten uitwerken en implementeren • Code evaluatie #1 • Deliverables: Code, beta week 8 • Query segmentatie algoritme afronden • Op of aanmerkingen doorvoeren van SIG • Deliverables: Geen week 9 • Begin presentatie • Verslag werken • Code evaluatie #2 • Deliverables: Code week 10-11 • Ruimte reserveren • Presentatie en verslag afmaken • Deliverables: Eindverslag en presentantie De planning 3.2 is uiteindelijk erg veranderd doordat slecht ingeschat werd hoe lang het zou duren om elk onderdeel te ontwerpen en te implementeren. Zowel het implementeren van de back-end voor uitgebreid zoeken als het implementeren van de query segmentation duurde twee keer langer dan verwacht. week 1 • Bekend worden met de gebruikte tools en code 13

• Systeem en probleem analyseren • Deliverables: Geen week 2 • Opstellen van functionele en kwalitatieve eisen • Maken van een planning • Onderzoek naar query segmentation • Deliverables: Plan van aanpak week 3 en 4 • Query log implementeren • Het huidige zoek algoritme documenteren • Verder onderzoek naar query segmentation • Query log analyseren en documenteren • Gebruiker vragenlijst opstellen en data verwerken • Beginnen aan implementatie van afzonderlijke velden • Placeholder toevoegen voor verbeteren van verkrijgende data query log • Deliverables: Usertest documentatie week 5, 6 en 7 • Nieuwe data vragenlijst analyseren en documenteren • Zoeken op afzonderlijke velden interface en functie implementatie afronden • Code evaluatie #1 • Deliverables: Back-end afzonderlijke velden zoeken, de REST api week 8, 9 • Opstellen van zoek algoritme voor query segmentatie • Segmentatie gedeelte uitwerken/implementeren • Labelen van segmenten uitwerken en implementeren • Op of aanmerkingen doorvoeren van SIG • Eerste versie verslag opleveren 14

• Deliverables: Algoritme voor segmenteren, labellen en eerste versie verslag week 10 • Tentamens • Deliverables: geen week 11-12 • Afronden query segmentatie • Usertest opstellen en uitvoeren • Code evaluatie #2 • Deliverables: Eindverslag en eindproduct

4

Onderzoek

Om te kijken wat er precies fout gaat met de huidige zoek implementatie van de website, wat voor zoekopdrachten mensen gaan invullen en hoe query segmentation werkt is er een onderzoeksfase geweest. In dit hoofdstuk wordt er allereerst gekeken naar de gebrekken van de huidige implementatie. Vervolgens wordt het onderzoek naar het zoek gedrag van de website gebruikers uiteengezet en daarna het verwachte zoek gedrag met de nieuwe implementatie. Tot slot komt in het hoofdstuk het literatuur onderzoek naar query segmentation.

4.1

Huidige Zoek Implementatie

Voor de implementatie van het zoek algoritme wordt er gebruik gemaakt van de ingebouwde functionaliteit van PostgreSQL om full tekst search te doen. Deze informatie kan terug worden gevonden op [3]. Er is gebruik gemaakt van de volgende drie functies van PostgreSQL om full tekst search te implementeren: to tsvector, to tsquery en ts rank. Deze functionaliteiten worden eerst doorlopen voordat de implementatie aan bod komt. Vervolgens wordt gekeken wat de beperkingen zijn om dieper in te gaan waarom de zoek functionaliteit niet werkt naar toe behoren.

15

4.1.1

PostgreSQL Functie: to tsvector

Om gebruik te maken van de full text search moet een tsvector worden gecre¨eerd. Deze vector wordt gemaakt aan de hand van de to tsvector functie op ´e´en of meerder kolommen of woorden. De functie doorloopt de gehele string van tekst dat omgezet moet worden naar een tsvector. Voor elk token dat voorkomt wordt er aangegeven op welke positie het voor kwam in de string. Het ingestelde woordenboek wordt aangeroepen op elk woord. Indien het woordenboek de token herkent wordt er ´e´en of meerdere lexeems (een lexeem is een woord dat meerdere betekenissen kan hebben) geretourneerd die de token representeren. PostgreSQL negeert standaard alle stopwoorden, tevens worden alle tokens die niet worden herkend ook negeert. 4.1.2

PostgreSQL Functie: to tsquery

Na het maken van de tsvector moet de zoek query input nog worden omgezet naar een tsquery. Dit moet worden gedaan met de functie to tsquery. De functie zet net zoals de to tsvector de input om naar lexeems. In plaats van de nummering van de positie van de token in de tekst wordt met to tsquery elk token gescheiden met een NOT, OR of AND operator om de query mogelijk te maken. 4.1.3

PostgreSQL Functie: ts rank

Een query waarbij de input omgezet wordt naar een tsquery, kan worden gebruikt om te kijken of ´e´en of meerdere lexeems voorkomen in een tsvector. Dit is handig om een ja/nee antwoord te generen op de vraag: komt deze string van tekst voor in deze kolom. PostgreSQL biedt tevens ts rank functie aan om de ja/nee vraag te uitbreiden naar een relevantie vraag. Om een score te geven voor elke resultaat kijkt ts rank naar hoe vaak de zoektermen voorkomen in het document, hoe dicht de zoektermen bij elkaar staan in het document en hoe belangrijk het document en of de zoektermen zijn. Er kunnen gewichten worden gezet op afzonderlijke tokens in de tsquery of tsvector om aan te geven welke belangrijker zijn dan de ander. 4.1.4

Implementatie

De website biedt ´e´en enkele inputbar om gebruik te maken van de zoekfunctionaliteit. Hier kan de voornaam, achternaam, geboorte/sterfte datum en geboorte/sterf plaats (of een combinatie van ´e´en of meerdere) worden ingevuld om te zoek naar personen. Gebruik maken van een joker tekens zoals

16

*, om aan te geven dat het ´e´en of meer tekens moet voorstellen, of ?, exact ´e´en teken, worden niet ondersteunt. De input in het zoekveld wordt direct zonder manipulatie van de frontend verstuurd naar de back-end via POST message. De back-end manipuleert de zoek string om het bruikbaar te maken voor to tsquery. Door gebruik te maken van to tsquery en ts rank worden de database identifiers opgehaald die een relevantie hebben met de ingevoerde zoek string. Het resultaat wordt op de website weergegeven en gesorteerd op de relevantie die door ts rank is bepaald. 4.1.5

Gebreken

Huidige implementatie biedt een full tekst search aan op beperkte data van elke persoon. Zoals vermeld gebruikt deze de standaard instelling van full tekst search van PostgreSQL wat inhoudt het gebruik van een woordenboek, verwijdert alle stopwoorden, woorden omzetten naar stamwoorden etc. Dit is handig en zinvol voor daadwerkelijke teksten, maar niet voor het zoeken naar namen. Bijvoorbeeld wanneer men zoekt naar Jan van Stegen”, wordt ” van” gefilterd door PostgreSQL wat niet wenselijk is. Alle namen voorna” men en of achternamen die geen Jan van Stegen zijn zouden dus niet als resultaat moeten worden weergegeven. In figuur 2 is duidelijk te zien dat het gebruik van PostgreSQL full text search op namen niet wenselijk is, want een gebruiker zou zonder gebruik van jokers exact willen zoeken.

4.2

Query Log

Het tweede onderzoek wat plaats vond, was om te kijken waarop werd gezocht door gebruikers van StamboomNederland met de huidige zoekmachine. Op de server van StamboomNederland worden geen logs bijgehouden dus is er een query log toegevoegd om de zoekopdrachten bij te houden. De analyse van query log bestond uit het handmatig beoordelen van alle zoekopdrachten, waarbij deze werden beoordeeld op de inhoud. Er werd gekeken naar voorkomen van initialen, voornamen, achternamen, jaartallen en plaatsnamen. Daarnaast werd er nog bijgehouden hoe vaak mensen dezelfde query opnieuw zochten of opnieuw zochten met een kleine aanpassing. Met de huidige zoekmachine kan vanwege de fuzzy search op voor- en achternaam gezocht worden maar ook op geboorte/sterf plaats/datum. Uit de analyse van deze log moet blijken waarop nou daadwerkelijk wordt gezocht door de gebruikers. Deze informatie kan vervolgens worden gebruikt

17

Figuur 2: Een screen shot van de zoekresultaten voor de zoekopdracht: Hermans”. Het is te zien dat alle varianten van Hermans worden gepakt ” (Hermanus, Hermannus, Herman etc.), wat niet het verwachtte gedrag is. om te kijken of gebruikers op meer zoeken dan vooral op voor en achternaam en hoe en in welke volgorde gebruikers de zoekopdracht geven. Tevens zou dit onderzoek een vergelijking kunnen geven wanneer de nieuwe zoekfunctionaliteit wordt ge¨ımplementeerd en in productie wordt gezet. Uit de resultaten, die geplot zijn in figuur 3, blijkt dat het zoeken op achternaam de grootste voorkeur heeft voor de gebruikers, waarbij vaak ook een voornaam wordt meegegeven en een enkele keer ook nog een jaartal of plaats. Door redelijk wat gebruikers wordt ook opnieuw gezocht, waarschijnlijk omdat deze niet de gewenste resultaten kregen. Mee te nemen uit dit onderzoek is om ervan uit te gaan dat de meeste gebruikers voornamelijk slechts op voor en achternaam zullen zoeken en te laten zien dat meer kan worden gebruikt om specifieker te zoeken. Het feit dat er weinig gebruikt wordt gemaakt jaartallen en plaatsen kan verwijt worden aan gebrek van informatie op de website. Bij de zoekbalken of help paginas van de website wordt niet duidelijk gemaakt welke mogelijkheden er zijn. Vervolg onderzoek van de zoekopdrachten is om de gebruikers informatie te geven, door middel van een placeholder of infoknop, en kijken of dat het zoekgedrag be¨ınvloed.

18

100

91

Frequentie in %

80 60 45

42

40 20 3

en

n O

pn ie

uw

Pl a

ar t Ja

at s

al le

en al In iti

m rn aa

m

Vo o

rn aa A

ch te

oc ht

1

0

ge z

7

Figuur 3: Frequentie van alle verschillende zoekopdrachten van een periode van tien dagen. Er waren totaal 831 zoekopdrachten.

4.3

Vragenlijst 1

Naast de query logs van de zoekmachine zijn er vragenlijsten gemaakt om te toetsen hoe gebruikers zoeken als ze gebruik maken van natuurlijke taal. Bij beide vragenlijsten werd er gevraagd hoe ze zouden zoeken binnen een stamboom website naar bepaalde personen. Het idee van de vragenlijsten was om informatie te verkrijgen naar, gegeven bepaalde personen, hoe hiernaar werd gezocht en hoe de gebruikers hun zoekopdrachten aanpassen en opbouwen per verschillend persoon Bij de eerste vragenlijst werden er biografie¨en gegeven van de volgende bekende personen: • • • •

Albert Einstein Jaap Stam Jan Pieter Balkenende Catharina-Amalia Beatrix Carmen Victoria 19

Bij elke biografie werden de volgende vragen gesteld: 1. Hoe zou u zoeken naar deze persoon? 2. Hoe zou u zoeken als er meerdere personen met dezelfde naam voor zouden komen? 3. Hoe zou u zoeken naar deze persoon als u zijn of haar naam niet mag gebruiken? (Bijvoorbeeld als de naam van een neefje of een nichtje niet meer weet.) In appendix C.5 is de volledige vragenlijst te vinden. De eerste vraag was om te kijken hoe gebruikers gewoon naar personen zouden zoeken als ze wat informatie hebben gekregen en verder niks. Uit de analyse van de antwoorden, zie vraag 1 in figuur 4, die op deze vraag werden gegeven kwam eruit dat vrijwel iedereen in hun eerste zoekopdracht slechts alleen de voor en achternaam van deze persoon invoerde. Echter wanneer gebruikers de naam niet konden gebruiken, vraag 3 in figuur 4, viel op dat de meeste terug vallen op bekende feiten van de persoon of op geboorteplaats en geboorte datum. Wanneer echter gegeven was dat er meerdere personen bestonden met dezelfde naam en de naam weer mocht worden gebruikt, vraag 2 in figuur 4 ging de voorkeur vaak naar het geven van zoveel mogelijk informatie dus zowel feiten als geboorteplaats, datum en beroep. Invloed van het resultaat van figuur 4 op de implementatie van de nieuwe zoekfunctionaliteit is dat voornamen, achternamen en functies verwacht kunnen worden bij het invoeren van een natuurlijk taal. Tevens kan de data gebruikt worden als trainingsdata en of test data.

20

80 70

70

70

68

59

60

55 54

Frequentie in %

50 40 32 29

30

18

20

20

13

13

10 5

4 0

0

0

0

4 5

2

0

M isc

R

el

at ie

tie

G

eb

Fu nc

ar ja rt e oo

e rt oo G eb

Vo o

rn a

pl aa t

am

m aa rn A

ch te

s

−10

Eerste vraag

Tweede vraag

Derde vraag

Figuur 4: Analyze van de eerste vragenlijst, met 14 responses en een totaal van 168 antwoorden.

4.4

Vragenlijst 2

Bij de eerste vragenlijst werden er biografi¨en gegeven voor elk bekend persoon. In de antwoorden van responses werd alleen informatie gebruikt die in de gegeven biografie voorkwam. Om zeker te zijn dat de antwoorden niet 21

biased zijn, is er een tweede vragenlijst opgesteld. 4.4.1

Onderzoek

Het onderzoek was als volgt, de opgestelde vragenlijst bestaat uit het geven van een zoekopdracht voor totaal acht verschillende personen. Bij elke vraag werd er herhaald dat de personen vaker dan ´e´en keer voor kan komen om te stimuleren dat er meer informatie werd gegeven over de personen. De vragen waren dan ook zo opgesteld om te zoeken naar personen die gebruikers goed kennen zoals bijvoorbeeld familie leden en naar die ze wellicht minder goed kennen zoals bekende Nederlanders. Dit was om te kijken of dit verandering bracht in de manier van zoeken door de gebruiker. Hiernaast werd over elk opgezocht persoon gevraagd hoe goed de gebruiker deze kent. Overzicht van alle vragen is te vinden in de appendix D.2. Met dit onderzoek moeten de volgende vragen worden beantwoorden: • Hoe gebruikers zoeken op personen welk deze goed kennen en dus veel informatie hebben en over personen waar de gebruiker minder over weet. • Wat gebruikers vaak gebruiken als extra informatie en in welke volgorde de informatie wordt gegeven. • Hoe de gebruikers de informatie geven dus op een Google manier ( Voornaam Achternaam Plaats”) of door middel van natuurlijke taal ” ( Voornaam Achternaam woont in Plaats”). ” Al deze informatie kan worden meegenomen bij de ontwikkeling van het algoritme voor omzetten van natuurlijke taal naar een zoekopdracht. De resultaten kunnen gebruikt worden om te analyseren zodat een duidelijk beeld kan worden verkregen bij het uitwerken van het algoritme, door het gebruik van de resultaten kan er worden gezorgd dat de effici¨entie van het algoritme wordt verbeterd. De segmentatie is deels afhankelijk van verwijswoorden (bijv. geboren in, woont in, ouder van etc.), welke zoals uit de vragenlijst blijkt niet altijd worden meegegeven, maar door de data te gebruiken kan er een kansberekening worden uitgevoerd om de kans te berekenen voor het toebehoren veld van een segment. Zo wordt degene genomen welk het meest aannemelijk is gezien de zoekopdracht en plaatsing van het segment. Bij elke vraag werd ook gevraagd naar hoe goed de gebruiker de gezochte persoon kende op een schaal van ´e´en tot tien. Bij de analyse hebben 22

we een directe link gelegd tussen personen die gebruikers goed kennen en minder goed kennen en gekeken of de zoekopdrachten hier verschillend waren. Waarbij vooral werd gekeken naar het verschil in informatie dat werd meegegeven in de query. 100

91

93

Frequentie in %

80 60

60

38

40

19

20 9

3

M isc

rn aa W m oo np la at s Ja ar ta lle n Fu nc tie R el at ie s

ch te A

Vo o

rn

aa

m

0

Figuur 5: Frequenties van velden bij familie leden. 4.4.2

Resultaten

Bij de vragen van vooral familieleden werden de hoogste scores gegeven op de vraag over de kennis van de gezochte personen. Uit de analyse van de vragen waarbij hoog was gescoord op bekendheid blijkt dat wanneer de gebruiker iemand zoekt die deze redelijk goed kent de meest voorkomende zoekopdrachten bestaan uit voornaam, achternaam met daarnaast in de meeste gevallen een geboorte datum en/of geboorte/woonplaats van de persoon. In enkele gevallen wordt er gebruik gemaakt van relaties, zoals moeder, vader of kind van, zoals te zien is in figuur 5.

23

87

Frequentie in %

80

72

60

51 38

40 20

15

11 1

isc M

rn aa W m oo np la at s Ja ar ta lle n Fu nc tie R el at ie s

ch te A

Vo o

rn aa

m

0

Figuur 6: Frequenties van velden in bij beroemde personen. Het is te zien in figuur 6 dat in tegenstelling tot personen die mensen goed kennen, wordt er bij personen waar de gebruiker weinig kennis over heeft altijd alsnog wel een voornaam en achternaam gebruikt. Wel wordt er hier, indien de persoon nog bekend genoeg is voor de gebruiker, gebruik gemaakt van de geboorte/woonplaats in de zoekopdracht. Wat opvalt bij minder bekende personen is dat vaak een functie of beroep wordt meegegeven van deze personen. De reden waarom voornaam vaker wordt gebruikt dan achternaam is omdat de testpersonen bij de vragen over Amalia alleen haar voornaam hebben gebruikt. In beide gevallen wordt er vrijwel altijd gebruik gemaakt van een voor en achternaam tenzij echt naar een hele onbekende persoon wordt gezocht (bijvoorbeeld Koningin van jaar 1900). Opvallend is dat er bij minder bekende personen vaak hun functie of beroep wordt meegegeven waar dit bij bekende personen nauwelijks wordt gedaan. Bij bekende personen worden vrijwel altijd nog geboorte- en woonplaats meegegeven en meestal ook de leeftijd of geboorte jaar. Tevens werd er verwacht dat er een verschil zou zijn tussen het gebruik van geboortedatum tussen bekende en onbekende personen omdat mensen vaak niet de kennis hebben in welke jaar een be24

roemde/onbekende persoon geboren zijn. Toch is bij beide categori¨en 38% van de tijd een geboortedatum gebruikt. Bij een verdere analyse blijkt dat het grotendeels van de zoekopdracht met geboorte datum bij onbekende personen bij de vraag: Hoe zou u een zoekopdracht invoeren als u naar de ” koningin van Nederland van honderd jaar geleden zou willen zoeken?”, wat wel te verwachten zou zijn. Hier kan uit gezegd worden dat bij het zoeken van overleden onbekende personen ook een jaartal gebruikt zou worden. Uit het geheel blijkt dat de voorkeur van bijna alle zoekopdrachten, ongeveer 77% meer uitgaan naar Google-achtige zoekopdrachten dan naar natuurlijke taal. Dit heeft invloed op het algoritme gezien er dus in de meeste gevallen geen gebruik kan worden gebruikt van verwijswoorden om velden aan segmenten te verwijzen. Zoekopdrachten zoals Voornaam Achternaam ” Plaats” zijn dus vaker voorkomend dan Voornaam Achternaam geboren in ” Plaats”. Uit de data van de vragenlijst kunnen, uit de antwoorden die daadwerkelijk correct waren ingevuld voor ons systeem, als trainingsdata worden gehaald door de velden met de hand (manueel) te labelen op veld volgorde. Hiermee wordt bedoeld te kijken in welke volgorde velden voorkomen, zo is bijvoorbeeld de kans dat er na een voornaam een achternaam komt groter dan dat er na een voornaam meteen een plaats komt. Door dit voor alle zinvolle queries uit de vragenlijst te doen, kan er een goed beeld worden gegeven over wanneer welke veld het meest wordt verwacht. Dit kan mee worden genomen bij de uiteindelijke keuze van het sterkste pad in het algoritme. De antwoorden van de vragenlijst geven een goed beeld van hoe mensen te werk gaan en waar rekening mee moet worden gehouden. De analyse geeft veel bruikbare data voor het algoritme om te zorgen dat deze in de juiste segmenten worden opgedeeld en er uiteindelijk de beste oplossing van mogelijke paden kan worden gekozen aan de hand van de ontwikkelde trainingsdata uit de vragenlijst.

4.5

Query Segmentation: Literatuur

Query segmentation houdt zich bezig met het zoeken door middel van een enkele zoekbox waarmee over verschillende velden kan worden gezocht met ongestructureerde tekst (free-text query) door deze op te delen en vervolgens om te zetten in een gestructureerde query voor een database. De meeste zoekboxen maken het slechts mogelijk om op ´e´en specifiek veld te zoeken, daarnaast zijn er nog de webforms welk het mogelijk maken om verschillende velden in te vullen voor de query. Het idee van het query segmentation algo25

ritme is om met een enkele zoekbox hetzelfde te bereiken als deze webforms met ongestructureerde tekst, bijvoorbeeld met een zoek query als Henk ” Jannsen uit Delft die is geboren in 1940”. Met het algoritme wordt deze tekst dan opgesplitst, oftewel gesegmenteerd, in delen. De nuttige delen worden dan gelabeld en vervolgens gebruikt om een gestructureerde query van te maken voor de database. In deze hoofdstuk worden de twee stappen toegelicht aan de hand van gevonden literatuur. Laatste gedeelte gaat nog dieper in op de Hidden Markov Modellen die gebruikt zijn bij het stap: labellen. 4.5.1

Stappen

De query segmentation bestaat uit meerdere stappen voor het opbouwen van de gestructureerde query vanuit de free-text query. Allereerst wordt de freetext gecontroleerd op spel fouten van maximaal ´e´en letter door gebruik te maken van een woordenboek en vervolgens opgedeeld in stukken, segmenten, waarbij de relevante delen uit de free-text query worden gehaald. Hierna moeten deze segmenten weer worden verwezen naar het juiste veld oftewel het juiste label bij elk segment moet worden gevonden. Als elk segment is gelabeld wordt indien nodig nog genormaliseerd, zodat de velden kunnen worden ingevuld voor de gestructureerde query. 4.5.2

Segmentatie

Voor het segmenteren van een vrije zoek actie binnen het geschreven domein is er gekeken naar eerder onderzoek binnen query segmentation. Tan et al. [4] hadden de observatie gemaakt dat naamwoordengroepen (in het Engels Noun phrase) identiek en onafhankelijk van elkaar zijn verdeeld in een zin. Hun algoritme om te segmenteren is berust op deze aanname. Laat Pc de kans verdeling zijn van de naamwoordengroepen, Q de zoek tekst, S Q een reeks van concepten dan geldt P (S Q ) = Πsi ∈S Q Pc (si )

(1)

waar si een mogelijk segment is. Pc (si ) wordt volgens het unigram model gedefinieerd als Pc (si ) = P (si |s1 s2 s3 . . . si−1 ) (2) De k -segmenten met de hoogste kans worden geselecteerd als de segmenten van de zoek tekst. Om de kans de berekenen moet Pc (si ) bekend zijn. Er worden twee methode ge¨ıntroduceerd om aan deze kans te komen. Voor beide methode moet de frequenties van n-gram woorden tot een bepaalde 26

lengte bekend zijn. Hiervoor hebben Tan et al. 1% van alle teksten gepakt die door de Yahoo! zoekmachine zijn bezocht. Eerst genoemde methode is het gebruiken van Maximum Likehood Estimate (MLE) voor woorden. Dit wordt gegeven door #(w) 0 w0 ∈V #(w )

P (w) = P

(3)

Deze methode heeft twee enorme beperkingen. Het eerste probleem is om te bepalen wat exact in de set V terecht komt. Er zijn te veel mogelijkheden van n-grams om in V mee te nemen. Het tweede probleem is dat MLE voorkeur geeft voor korte n-grams. Terwijl dat niet altijd gewild is. Bijvoorbeeld de kans op Algemeen Dagblad” zal altijd groter zijn dan de kans op Algemeen ” ” Dagblad abonnement”. Vanwege deze problemen is er een tweede methode ge¨ıntroduceerd, namelijk gebruik te maken van expectation-maximization (EM). Het EM algoritme kan worden uitgelegd als volgt: de onbekende parameters worden geschat in de eerste stap en in de tweede stap worden opnieuw de ontbrekende parameters geschat maar dit keer onder de aanname dat de nieuwe geschatte waarden correct zijn. Deze twee stappen worden continue uitgevoerd totdat de stop criteria wordt behaald. Dit principe kan worden toegepast om Pc (si ) te bepalen. Bij het onderzoek van Tjin-Kam-Jet, Trieschnigg en Hiemstra (2013) [5] wordt gebruik gemaakt van een patroon-gebaseerde benadering om de beste interpretatie oftewel segmentatie van de queries te vinden. Het algoritme bestaat uit drie stappen, waarbij eerst wordt gesegmenteerd dan gelabeld en vervolgens wordt genormaliseerd. De patroon herkenning bestaat uit drie delen: een prefix, een body en een postfix gedeelte, waarbij de pre- en postfix elk een eindige lijst van strings aanduiden. De affixes worden dan gebruikte als idioom van natuurlijk taal gebruik oftewel door een bepaalde affix voor een body part kan deze door middel van dit patroon worden verbonden aan een veld waar deze behoort. Naast deze pre en postfixes wordt er gebruik gemaakt van kansen van veld volgorde door middel van Markov modellen, zodat kan worden gekeken welke volgorde voorkeur heeft boven andere. Daarnaast wordt gezocht naar waarde die door opgestelde reguliere expressies zijn gedefinieerd of voorkomen in een woordenboek. De reguliere expressies waar naar wordt gekeken zijn: als een veld Fi voorkomt is moet er ook een veld Fj zijn en ook de negatie ervan voor bepaalde velden Fi mag er geen veld Fj zijn in de query. Ook zijn er 27

categorie¨en voor bepaalde velden zodat niet elk segment van de query aan elk veld mag worden gebonden. Aan de hand van deze expressies en patroon herkenning worden er dan waardes aan elk segment verbonden, waarbij er meerdere waardes per segment kunnen voorkomen. Daarna worden de gevonden segmenten gelabeld en genormaliseerd. Waarna alle mogelijke resultaten die gevonden zijn na het labelen een score wordt gegeven gebaseerd op de gevonden veld waardes en veld orde. Waarbij het uiteindelijk pad met hoogste score wordt gebruikt voor de gestructureerde query. Li et al [1] maakten gebruik van clickthrough data van gebruikers om te achterhalen wat de voorkeur van de gebruiker is bij elke query. Zo wordt er een likelihood bepaald voor een subsequence van woorden aan de hand van de informatie uit de clickthrough data. Bij een query van bijvoorbeeld Bank of America Investment” kwam uit de clickthrough data dat er altijd ” op documenten werd geklikt welke Bank of America” altijd als subsequence ” hadden waardoor er een grote kans is dat dit ´e´en segment is. Voor het bepalen van de query segmenten wordt wederom gebruik gemaakt van het EM algoritme, echter wordt er hierbij een penalty toegevoegd voor lange segmenten om de voorkeur voor deze te onderdrukken. Zo kan voor een gegeven query Q van lengte n, de query segmenten S en de segmentatie partitie B, de kans van deze segmentatie worden uitgerekend met: P (S|Q, θ, ψ) = P (B|Q, n, θ, ψ) = P (Q|B, θ) = ΠM m=1 P (Sm |θ)

(4)

Vervolgens wordt het model uitgebreid met de click documenten, zodat het uit twee delen bestaat: het globale gedeelte P (Sm |θ) en een document specifiek gedeelte P (Sm |θD ). Voor de berekening van P (Sm |θD ) wordt gebruik gemaakt van de documenten en een bigram model om de kans te berekenen op een segmentatie gedeelte Sm . de kans van de segmentatie wordt dan herschreven naar: P (Q|B, θ, θD ) ∝ ΠM m=1 P (Sm |θ)P (Sm |θD )

(5)

Betekenis van naamwoordengroepen in zoekopdrachten kunnen vaak niet uit de context worden gehaald, omdat ze vaak meerdere betekenissen hebben, of te wel ze zijn Multi-Word Expressions. Mishra et al [2] maken deze aanname. Ze zeggen dat elk mogelijk permutatie van MWE’s in een zoekopdracht dezelfde zoekopdracht oplevert. De kans dat een n-gram (waar gram

28

woorden zijn) wordt gegeven door: Pi =

(li − n + 1)! li !

(6)

De kans is gebaseerd op de aantal mogelijke permutatie van M die een MWE kandidaat is in een zoekopdracht met lengte li . Om te weten dat M daadwerkelijk een MWE is en niet dat n-gram een bag-of-words is, moet er gekeken worden of M vaker voorkomt dan in een bag-of-words model. Dus wat is de kans dat X groter of gelijk is aan N , waar X een model is van hoe vaak M samen voorkomt in k queries en N het geobserveerde waarde van X in de data is. Met Hoeffding’s Inequality kan er een bovengrens worden gevonden op de kans. Dit wordt gegeven door: P rob[X ≥ N ] ≤ exp − Waar E(X) = een MWE is. 4.5.3

P

i Pi .

2(N − E(X))2 =δ k

(7)

Hoe kleiner δ is hoe groter de kans is dat een n-gram

Labeling

In de paper van Tjin-Kam-Jet, Trieschnigg en Hiemstra (2013) [5] worden de gevonden segmenten met behorende waardes gelabeld, waarbij een label drie betekenissen kan hebben, namelijk: een waarde v wordt verwezen aan een veld F; een veld naam, dus de waarde verwijst naar een veld voor een ander aanliggend segment; of het segment heeft geen bruikbare informatie. De Labels worden bepaald aan de hand van gestelde voorwaarde en opgestelde lijsten voor elk veld. Hierna vind de opbouw van de geconstrueerde query plaats aan de hand van de gevonden labels, hierbij wordt gebruik gemaakt van een stack decoder om de juiste labels aan elk segment te verwijzen. Voor elke waarde bij elk segment worden de mogelijke labels bepaald en het segment gelabeld, waarna voor elk gelabeld segment een nieuw pad in de stack wordt gemaakt. Uit deze stack wordt dan uiteindelijk het sterkste pad genomen, dit sterkste pad wordt bepaald aan de hand van ontworpen Hidden Markov Modellen welk berekenen welk pad het meeste aannemelijk is. 4.5.4

Hidden Markov Modellen

In de paper van Tjin-Kam-Jet et al [6] wordt behandeld hoe de implementatie van een Hidden Markov Model (HMM) helpt bij het bepalen van de beste 29

combinatie van segmenten, oftewel het sterkste pad uit de gebruikte stack te bepalen. Een HMM is een probalistische eindige automaat, die bestaat uit een aantal states en een aantal transitie kansen van state naar state, daarnaast heeft elke state een aantal emissie kansen welk slaan op de kans van de output van de state. De segmenten zijn de sequences welk ingevoerd worden in het ontworpen HMM waarna deze voor elk pad de kans berekent dat dit het juiste pad is. Uiteindelijk wordt het pad gekozen waarvoor deze kans dan het hoogste is. Het ontwikkelde HMM voor NS Reisplanner wordt geconstrueerd aan de hand van de gegeven informatie van het systeem. De states van het HMM komen elk overeen met een input field f ∈ F , met daarnaast nog een begin en eind state. Voor het bepalen van de transitie kansen van state naar state, oftewel van veldtype naar veldtype, worden handmatig gelabelde vrije tekst queries gebruikt als trainingsdata voor de implementatie. Aan de hand van deze trainingsdata wordt dan de maximum liklihood estimate (MLE) bepaald van de volgorde van input velden. Deze berekening van veld naar veld wordt berekent met: PM LE (tij ) =

N umber of times fi appears bef ore fj T otal number of times that fi appears

(8)

De emissie kansen welk door het HMM worden gegenereerd na elke transitie worden bepaald aan het de hand van hoe vaak een gegeven token voorkomt op een bepaald veld en hoe vaak deze in totaal voorkomt. De emissie kansen worden bepaald door: PM LE (eij ) =

N umber of times tokj is emitted at fi T otal number of times tokens emitted at fi

(9)

Vervolgens wordt dit HMM model gebruikt om de kans van alle veld sequenties vanuit de stack dan te bepalen. Waarbij de kansen van het HMM eerst nog worden afgevlakt, omdat anders bepaalde tokens een kans van nul kunnen hebben en wordt er een bonus of penalty gegeven aan langere of kortere paden.

5

Ontwerp en Implementatie

Na het afronden van de onderzoeksfase kan er aandacht worden besteed aan het omzetten van het onderzoek naar een ontwerp en implementatie ervan. Verschillende elementen die zijn gemaakt worden in dit hoofdstuk besproken.

30

Allereerst komen de userinterface en de REST-api aan bod. Vervolgens wordt de backend besproken en hoe de query segmentatie is gemaakt. Als laatst wordt het resultaat besproken.

5.1

Uitgebreid Zoeken: Frontend

Om de zoekfunctionaliteit uit te breiden, zoals aangegeven in 1 bij F6, is er een interface gebouwd waar gebruikers op voornaam, tussenvoegsel, achternaam en geboorte/sterf datum kunnen zoeken. De interface biedt de mogelijkheid om * en ? tekens te gebruiken om ´e´en of meerdere onbekende letters aan te geven. In figuur 7 is de interface te zien.

Figuur 7: Een screen shot van de uitgebreide zoekfunctionaliteit van StamboomNederland Daarnaast kan er door middel van de knop New”, zoals te zien in figuur ” 7, nog relaties worden toegevoegd waarbij er gegevens van deze persoon kunnen worden ingevoerd en het type relatie tot deze persoon wat kind, ouder of partner kan zijn.

31

Figuur 8: Een screen shot van de knop New voor het toevoegen van een relatie in uitgebreid zoeken

5.2

Uitgebreid Zoeken: Backend

De backend van het uitgebreid zoeken werkt door van alle ingevulde velden een query op te bouwen voor de database. Deze query wordt pas opgebouwd wanneer de gebruiker daadwerkelijk zoekt, zodat ongebruikte velden bij de opbouw van de query niet onnodig hoeven worden meegenomen. Een eis aan de uitgebreide zoekfunctionaliteit is om er voor te zorgen dat er exact kan worden gezocht op ´e´en of meerdere velden in de database, waarbij de gewenste velden waar over gezocht moet kunnen worden overeenkomen met de velden in de interface van het uitgebreid zoeken. Voor het verwerken van de ontvangen data vanuit de interface is ervoor gekozen een SearchWrapper” klasse te ontwerpen. Deze bevat een Pers” onWrapper welk de gegevens van de persoon bevat, indien deze velden zijn ingevuld. Daarnaast bevat de SearchWrapper ´e´en of meerdere feiten en rollen in respectievelijk een lijst met FactWrappers en RoleWrappers. De keuze voor deze SearchWrapper is voor het eenvoudig verwerken van de data uit de interface en om deze later bij het opbouwen van de query makkelijk te verwerken, zodat er kan worden gezocht op de correcte velden in de database. Door een interface te hebben tussen de zoekopdracht en het opbouwen van de query om de zoekresultaten op te halen is het mogelijk dat andere bronnen, zoals de REST-api en de query segmentatie, hier gebruik van kunnen maken. Uitdaging van de backend lag bij het maken van de query aan de hand van het SearchWrapper object. Er waren twee problemen: in SearchWrapper hoeven niet alle velden worden ingevuld en alle niet ingevulde velden moeten niet worden meegenomen plus er kunnen 0 tot n rollen zijn en 0 tot n feiten. Het andere probleem is de complexe database. 32

In appendix G is een gedeelte van het database model van StamboomNederland te vinden. De tabellen Roles en Role Types geven aan welke rol een persoon kan hebben, bijv. ouder, kind, gevangen, buurman etc. De tabellen Fact en Fact Types geven aan wat voor feiten een persoon heeft, bijv. geboorte feit, begraven, adoptie etc. De tabel UDFS (User Defined Fields) geeft extra informatie bij een feit, bijvoorbeeld bij het feit beroep wordt in de tabel UDFS aangegeven welke beroep de persoon heeft/had. Voor het oplossen van beide problemen moet het query sequentieel worden opgebouwd, zo kan het probleem worden verdeeld in kleinere problemen. Voor elke subklasse van SearchWrapper, Person, Role en Fact, is er een Query klasse gemaakt die respectief elke klasse omzet naar een query. Op deze manier kan de query overzichtelijk en sequentieel worden opgebouwd.

5.3

Rest API

Naast de interface is een REST-api gebouwd om buiten om de website gebruik te maken van de zoekfunctionaliteit. In de url kunnen dezelfde velden worden gebruikt als bij de interface. Door een mapping te maken van de url parameters naar de SearchWrapper velden is het mogelijk specifiek te kunnen zoeken. Ook bij de REST-api kan gebruik worden gemaakt van wild-cards.

5.4

Query segmentation

Het gebruikte algoritme van de query segmentation welk wordt toegepast op StamboomNederland, zal hier per onderdeel worden uitgelegd. Het algoritme zelf bestaat uit meerdere onderdelen welk moeten worden uitgevoerd om te zorgen dat uiteindelijk alle velden de correcte toewijzing krijgen. De segmentatie begint met het binnen krijgen van de vrije-tekst zoekopdracht waarna deze wordt opgedeeld in stukken, waarbij elk stuk bestaat uit een woord in de vrije-tekst zoekopdracht, waarna van elk stuk wordt gekeken of het bruikbaar is. Indien een stuk bruikbaar is wordt er een segment gemaakt welk bestaat uit ´e´en of meerdere stukken uit de vrije-tekst zoekopdracht en een lijst met de mogelijke velden voor dit segment. Wanneer dit voor alle bruikbare stukken is gedaan blijft nog de vraag welk veld moet worden gekozen uit elk segment om er voor te zorgen dat alles aan het juiste veld wordt toegewezen.

33

5.4.1

Stap 1: Segmenten

Voor het segmenteren is dezelfde methode aangenomen als in [5] omdat hun implementatie van het segmenteren van zoekopdrachten binnen het domein reisplanning enorm identiek is aan het domein van deze opdracht. De preen postfix zijn in dit geval namen, plaatsen en datums, die net zoals [5] uit de database gehaald kunnen worden of kunnen worden geparsed. De affixes hebben dezelfde betekenis, deze zullen een pre- of postfix mappen aan een veld naam. Hieronder wordt dieper in gegaan hoe de pre- en postfixen worden herkend en welke rol de affixen in spelen. Eerste stap is om alle bruikbare informatie uit een zoekopdracht te halen, dit wordt woord voor woord gedaan. Om te kijken of een stuk bruikbaar is wordt er voor elk stuk gekeken of er een veld is welk geldig is voor het stuk, indien een stuk bruikbaar is wordt hiervan een segment gemaakt. Een bruikbaar stuk tekst, oftewel een segment bestaat uit ´e´en of meerdere woorden uit de tekst en bevat een lijst met de mogelijke veldtypes voor dit segment zoals te zien is in figuur 9. Voor het vinden van de mogelijke veldtypes van elk segment worden ze opgezocht in de database voor het vinden van namen en plaatsen, voor het vinden van datums wordt een datum parser gebruikt waarbij wordt gekeken welke stukken samen een datum vormen. Als laatste wordt door middel van een opgesteld woordenboek nog de stukken eruit gehaald welk verwijzen naar feiten of relaties zoals geboren in”, woont in” of kind/ouder van”, ” ” ” dit woordenboek bevat data uit onze vragenlijst en is aangevuld met nog andere verwachten verwijzingen.

34

Segmenten Herman Voornaam van Tussenvoegsel Amsterdam Plaats Achternaam geboren in Geboorte verwijzing 1980 Jaartal Leiden Plaats Achternaam Figuur 9: Boom met segmenten Voor het effici¨ent vinden van alle veldtypes voor elk segment wordt eerst gekeken of deze in het woordenboek voorkomt, wanneer dit niet het geval is wordt er slechts gekeken naar het voorkomen in de database met bijhorende veld waarden. De reden dat er geen lijst valt te maken met plaatsen en namen is vanwege het feit dat een lijst van namen oneindig kan zijn en gezien het mogelijk is dat plaatsnamen handmatig in te vullen zijn kan ook deze

35

lijst oneindig groot zijn. Een database zoekopdracht is dan ook noodzakelijk om te bepalen of een bepaald segment een plaats en/of naam veldtype is. Voor de datums hoeft er niet in de database gezocht worden omdat deze lijst wel eindig is. Een datum bestaat altijd uit 31 dagen, twaalf maanden en jaartallen van vier cijfers waarbij maanden ook in tekst kunnen voorkomen. Hetzelfde geldt voor de verwijzingen welk uit een eindige lijst bestaan waar de ontwikkelde woordenboek zo goed mogelijk uit bestaat. 5.4.2

Stap 2: Paden

Na het verkrijgen van alle segmenten, uit de bruikbare stukken van de vrijetekst zoekopdracht, moet nu de juiste combinatie van segmenten met behorende veldwaarden worden gevonden. Voor het vinden van de juiste segmentatie, oftewel de juiste toewijzing van elk segment aan het correcte veld voor de zoekopdracht, worden alle mogelijke paden met de gevonden segmenten gemaakt. De paden worden gemaakt door te kijken welke types elk segment heeft. Voor elk type in het segment wordt een nieuwe tak gemaakt in een boom waardoor uiteindelijk een boom bestaat met alle mogelijke paden van keuzes per segment. 5.4.3

Stap 3: Sterkste pad

Na het maken van alle mogelijke paden moet het sterkste pad, oftewel het pad waarvan het meest aannemelijk is dat deze de segmenten aan de juiste velden toekent, worden gevonden. Om uit alle gemaakte paden het sterkste pad te vinden wordt gebruik gemaakt van Hidden Markov Modellen, het gebruik van de modellen zorgt voor het berekenen van de kans op het meest aanneembare pad, welk zijn ontwikkeld uit de trainingsdata van de vragenlijsten. Hierbij wordt gebruik gemaakt van de frequentie dat een veld voorkomt en hoe vaak een veld fi voor veld fj (i 6= j) komt volgens het principe van Treinplanner [6, Chapter 2.3]. Het gebruik van deze modellen wordt toegepast in het algoritme door te kijken naar de volgorde van velden in alle paden, hiervan wordt dan het meest aanneembare pad gekozen aan de hand van de kansen die zijn gegenereerd met het Hidden Markov Model. De paden zijn opgebouwd aan de hand van de volgorde dat de segmenten ook worden gevonden in de tekst. Nadat alle paden zijn beoordeeld aan de hand van de Markov modellen wordt het pad met de grootste kans, het sterkste pad, genomen als zoekopdracht over de velden, aannemelijk is dat dit de beste zoekresultaten opgeeft voor de ge-

36

zochte tekst. Zo zal bij het vorige voorbeeld het sterkste pad waarschijnlijk als volgt worden gekozen door de Markov modellen zie figuur: 10, Segmenten Herman Voornaam van Tussenvoegsel Amsterdam Plaats Achternaam geboren in Geboorte verwijzing 1980 Jaartal Leiden Plaats Achternaam Figuur 10: Boom met gekozen pad in rood Bij Treinplanner [6, Chapter 2.3] worden ook nog de positionele kansen gebruikt van elke segment. Bij het schrijven van een natuurlijke zoekopdracht voor een stamboom kunnen segmenten op verschillende posities 37

voorkomen omdat de gegeven informatie onafhankelijk kan zijn van elkaar. Vandaar dat bij deze implementatie alleen de transitie en emissie kansen worden gebruikt. Verder worden de kansen die gegeneerd worden door de HMM nog aangepast. Het HMM zal altijd hogere kansen geven aan het kleinste pad. In dit geval moet de voorkeur gegeven worden aan het langste pad omdat dat het meeste informatie bevat. Om langere paden de voorkeur te geven wordt de volgende formule gebruikt: L(S) =

p P (S)

|S|

(10)

Waar S een pad is van segmenten, |S| het aantal segmenten in het pad en P de HMM kans functie. 5.4.4

Overzicht algoritme

Het uiteindelijke algoritme in het kort begint met het binnen krijgen van de vrije-tekst zoekopdracht, waarna deze moet worden verwerkt naar bruikbare delen voor de zoekopdracht. Dit gebeurt door het cre¨eeren van segmenten vanuit de query waarbij elk segment ´e´en of meerdere typen bevat voor mogelijk velden. Wanneer voor alle segmenten de veldtypes zijn gevonden worden alle paden gegenereerd en door middel van het markov model wordt het sterkste pad gekozen en hiermee de uiteindelijke query uitgevoerd.

Figuur 11: Een screen shot van het zoekopdracht naar alle Groot die geboren zijn voor 2000. In figuur 11 is het resultaat te zien van de query segmentatie implemen38

tatie. Door de backend wordt het woord Groot” herkent als achternaam ” en niet als voornaam omdat in de database alleen personen zijn met die achternaam, geboren” als een geboorte feit en voor 2000” als een datum. ” ” 5.4.5

Resultaat

De REST-api en de userinterface gecombineerd met de backend voldoen aan alle must requirements in 1 behalve het zoeken in afzonderlijke projecten. Tevens zijn ook twee should eisen ge¨ımplementeerd, namelijk zoeken op feiten, beroep en rollen. Met ´e´en enkele bar zoeken is ge¨ımplementeerd door middel van query segmentatie. Alle drie de elementen zitten in prototype fase. Er is besloten op basis van de usertest die besproken wordt in 6 dat alleen de REST-api en het uitgebreid zoeken interface verder worden ontwikkeld om naar productie te brengen. Deze beslissing is gemaakt omdat query segmentatie te traag is (gemiddeld 4 seconden) en te veel tijd kost t.o.v. de andere elementen om het productie klaar te maken. De grootste bottleneck ligt bij het herkennen van voornamen, achternamen en steden. De andere reden is dat gebruikers niet fijn vinden om door middel van natuurlijke taal te zoeken.

6

Tests

Voor het testen van het systeem zelf zijn Unit Tests uitgevoerd om te kijken of alles naar verwachting werkt. Naast het testen van het systeem door Unit Test zijn er ook User Test uitgevoerd om te kijken of het systeem in de praktijk ook werkt zoals verwacht en te kijken waar nog verbeteringen nodig zijn. Tijdens het project is de code ge¨evalueerd door SIG welk een cijfer heeft gegeven voor hoe goed de code onderhoudbaar is, deze informatie is meegenomen en verwerkt in de rest van het project.

6.1

Unit Test

Voor het testen van de code is gebruik gemaakt van JUnit in combinatie met EclEmma en EasyMock. Waarbij alle geschreven methodes zijn getest door middel van assertions met JUnit en waar nodig zijn enkele keren EasyMock gebruikt voor het testen van methodes welk een database verbinding nodig hadden.

39

6.1.1

SIG

Halverwege het project is de code verstuurd naar SIG, welk de code evalueert op onderhoud. De code had een score van drie sterren gekregen op het onderhoudbaarheidsmodel van SIG, dit houdt in dat de code gemiddeld onderhoudbaar is. Punten waarop de code lager had gescoort waren die voor Unit Size, Unit Complexity en Component Independence. Voor het onderdeel van Unit Size wordt er gekeken naar code dat bovengemiddeld lang is. Enkele methodes waren te groot, dit is aangepast en bij nadere code zijn alle methodes waar nodig en mogelijk opgesplitst in verschillende methodes. Dit zorgt ervoor dat deze nu makkelijker te begrijpen zijn, te testen en de code beter onderhoudbaar maakt. Voor de Unit Complexiteit wordt er gekeken naar code dat bovengemiddeld complex is. Wat in dit geval dezelfde methodes waren als die naar voren kwamen bij de Unit Size en waar door het oplossen van de punten van de Unit Size ook dit punt oplost. Als laatste punt was gegeven de Component Independence waarbij wordt gekeken naar de hoeveelheid code die alleen intern binnen een component wordt gebruikt. In dit geval was dit vooral in het services” component ” het geval. Waardoor de nodige methodes zijn aangepast of naar andere componenten zijn verplaatst en de componenten structuur is aangepast. Met het vervolg van het project zal het niveau op ze minst geprobeerd te worden volgehouden en de punten mee te nemen tijdens de rest van het project. Wat uit de tweede evaluatie van SIG bleek is dat ondanks een stijging van 139% van het systeem de onderhoud hetzelfde is gebleven. Het merendeel van de punten waren meegenomen volgens hun evaluatie maar konden op sommige punten nog iets worden verbeterd, vooral op de punten van de indeling zou deze nog wat moeten worden opgesplitst. In appendix E.2 is het volledige commentaar van SIG te vinden.

6.2

User Test

Voor de user test van het ontwikkelde zoeksysteem in stamboom Nederland zullen vrienden, familie en kennissen worden gevraagd om het systeem te testen van alle leeftijden. De uiteindelijke gebruikers zijn ook gewoon de gemiddelde persoon dus alle mensen behoren tot de doelgroep. 6.2.1

Doel

Het doel van de user test is om de oude implementatie van het zoekfunctie te vergelijken op de nieuwe implementatie van de zoekfunctie op de volgende 40

punten: 1. Effectiviteit (a) Lukt het om alle gewensten personen te vinden. 2. Efficiency (a) Hoe snel vindt de gebruiker de personen waar ze naar zoeken (tijd). (b) In hoeveel clicks vindt de gebruiker de persoon. (M.a.w. moet er door meerdere pagina’s worden gebladerd.) (c) In hoeveel zoekopdrachten vindt de gebruiker de persoon. 3. Tevredenheid (a) Biedt de zoekfunctie genoeg functionaliteit om te zoeken. (b) Worden er veel irrelevante zoekresultaten gegeven. (c) Vindt de gebruiker de zoekfunctie snel genoeg. (d) Heeft de gebruiker klachten over de zoekfunctionaliteit. 6.2.2

Opstelling en uitvoering

Aan de gebruikers wordt een puzzel F gegeven met een stamboom waarin bepaalde gegevens staan over een al bestaande stamboom in het systeem. In de stamboom die de gebruiker krijgt missen echter gegevens, de vraag voor de gebruiker is nu om alle onbekende velden op te zoeken in Stamboom Nederland om zo de hele stamboom compleet te maken van de puzzel. De gebruiker wordt gevraagd twee van deze puzzels op te lossen eenmaal met de oude zoekfunctionaliteit en een keer met de nieuwe. Per gebruiker zal het verschillen met welk systeem deze begint, zo begint de ene gebruiker eerst met het nieuwe systeem en daarna het oude systeem en een andere gebruiker zal eerst met het oude systeem beginnen. Dit wordt gedaan zodat mocht het gebruik van de eerste keer met de ene zoekmethode de gebruiker be¨ınvloeden tijdens het testen van de andere, dan wordt dit opgeheven door het omwisselen van met welke wordt begonnen. Terwijl de gebruiker de puzzel invult wordt er met papier en pen bijgehouden in hoeveel zoekopdrachten elk persoon wordt gevonden. Tevens wordt de tijd per puzzel bijgehouden. Daarnaast zal de browser sessie worden opgenomen voor eventuele latere analyse.

41

Nadat de testpersoon beide puzzels heeft geprobeerd op te lossen zal een interview plaats vinden om de tevredenheid te meten t.o.v. beide zoekfunctionaliteiten. Algemene bevindingen zullen ook worden genoteerd, bijvoorbeeld bugs in het systeem of het invoeren van onjuiste zoekopdrachten. 6.2.3

Resultaten

Na het uitvoeren van de puzzel met vijf test personen zijn de resultaten vastgelegd van zowel de oude fuzzy search en de nieuwe query segmentatie search. Uit deze resultaten bleek dat met de oude zoekmachine er af en toe vaker dan ´e´en keer moest worden gezocht, in sommige gevallen zelfs twee tot drie keer, om de persoon te vinden en waren er ook dusdanig meer clicks gemaakt met een gemiddelde van drie tot vier clicks. Bij de nieuwe search werd de persoon vrijwel altijd in ´e´en keer zoeken gevonden en werd er slechts een enkele keer nog een keer gezocht waardoor ook het aantal gemaakte clicks lager lag op een gemiddelde van iets boven de twee. Mede doordat er vaker moest worden gezocht duurde het ook langer voor gebruikers om de puzzel op te lossen met de oude ten opzichte van de nieuwe search, respectievelijk tien minuten tegen over zes minuten per puzzel. Uit de resultaten valt te zien dat met het gebruik van de oude zoekmachine er vaker meer dan ´e´en keer moest worden gezocht en er hierdoor ook meer clicks werden gemaakt voor het vinden van een persoon. Waarbij bij de nieuwe zoekmethode vrijwel altijd de persoon de eerste keer al werd gevonden. Bij gebruik van de oude zoekmethode was in enkele gevallen het ook onmogelijk om bepaalde personen te vinden vanwege de beperkte gegeven informatie, deze personen waren wel te vinden met de nieuwe zoekmachine gezien deze meer mogelijkheden bied voor het zoeken. Daarnaast was de zoektijd met de oude zoek functionaliteit voor het vinden van alle personen iets langer dan die met de nieuwe, dit doordat er vaker moest worden gezocht en niet altijd gelijk de juiste persoon bovenaan in de gegeven resultaten staat. 6.2.4

Commentaar

Uit de interviews en analyse van het gebruik van beide zoek functionaliteiten bleek dat de gebruikers met de oude zoek functionaliteit vaak veel onnauwkeurige zoek resultaten kregen en dat de persoon die werd gezocht vaak niet degene was die boven aan in de resultaten stond. Bij de nieuwe zoek functionaliteit stond de gezochten personen wel altijd bovenaan tenzij er meerdere

42

personen met dezelfde gegevens natuurlijk voorkomen, met de nieuwe functionaliteit werden wel alleen exacte zoekresultaten gegeven waarbij er dus echter geen zoekfouten konden worden gemaakt gezien deze anders geen relevante resultaten geeft. Daarnaast kost het de nieuwe zoekfunctionaliteit iets langer dan de oude om een zoekopdracht te verwerken. Uit de interviews met de gebruikers bleek dat zij het niet natuurlijk vonden om natuurlijke taal te gebruiken bij het zoeken. De gebruikers waren gewend om Google-achtige zoektermen te gebruiken om te zoeken. Ze vonden het wel fijner zoeken met de nieuwe zoekmachine dan met de oude omdat er geen rare onnodige zoekresultaten kwamen. Alle gebruikers vonden beide zoek implementaties wel te traag werken. Alle testpersonen vonden het wel een leuke toevoeging aan de website. Andere commentaar wat de testpersonen hadden was dat ze de user interface van de website onduidelijk en lelijk vonden.

7

Conclusie

Met de opgestelde eisen voor het verbeteren van de zoekfunctionaliteit van StamboomNederland is er een onderzoek geweest naar de gebreken en problemen van de huidige implementatie. Het grootste probleem was het incorrect gebruik van PostgreSQL functies. Deze functies zijn niet gemaakt om full text search te doen op namen. Hierdoor faalt het systeem in het correct weergeven van zoekresultaten voor namen van personen en steden. Om een beeld te krijgen van wat het huidige zoekgedrag is van de gebruikers is een query log bijgehouden en geanalyseerd. De belangrijkste waarneming was dat mensen herhaaldelijk zochten en alleen maar voornamen en achternamen gebruikten. Het vervolg onderzoek was het kijken wat het zoekgedrag was wanneer mensen natuurlijke taal konden gebruiken. Waarnemingen waren dat mensen bij het zoeken van familie leden voornamelijk voornaam, achternaam, geboorte/sterf datum/plaats gebruiken plus het aangegeven van relaties (ouder/kind). Om tot een implementatie te komen zodat gebruikers natuurlijke taal kunnen gebruiken is er onderzoek gedaan naar query segmentation. Er is toen gekozen om de Reisplanner [6] nauw te volgen bij de implementatie. Na de onderzoekfase is de backend ontworpen en ge¨ımlementeerd, met het belangrijkste element de SearchWrapper klasse. Deze klasse functioneerde als een interface tussen de frontend en de backend, hierdoor was het mogelijk om een duidelijk scheiding te cree¨en. Bij de frontend is er een userinterface gebouwd die de gebruikers de mogelijkheid geeft om nauwkeu-

43

rig te zoeken naar personen op de website. De REST-api bevat dezelfde functionaliteit en kan buiten de website om gebruikt worden. Voor het gebruik van natuurlijk taal is een HMM gecree¨ert en getraind om de meest aannemelijk volgorde van segmenten aan te geven. Met het HMM was het mogelijk om zinnen zoals: De ouders van Jan Willen” of ” Pieterse geboren te Zoetermeer in 1990” correct om te zetten naar een ” zoekopdracht. Uit de usertest blijkt dat de query segmentatie implementatie correct werkt en beter dan de oude zoekfunctie. Helaas is de query segmentatie in prototype fase en zal niet naar productie worden gebracht. De REST-api en de interface worden wel naar productie gebracht.

44

Referenties [1] Yanen Li, Bo-Jun Paul Hsu, ChengXiang Zhai, and Kuansan Wang. Unsupervised query segmentation using clickthrough for information retrieval. In Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval, pages 285–294. ACM, 2011. [2] Nikita Mishra, Rishiraj Saha Roy, Niloy Ganguly, Srivatsan Laxman, and Monojit Choudhury. Unsupervised query segmentation using only query logs. In Proceedings of the 20th international conference companion on World wide web, pages 91–92. ACM, 2011. [3] The PostgreSQL Global Development Group. PostgreSQL 9.1.13 Documentation - 12.3. Controlling Text Search. Beschikbaar op "http://www.postgresql.org/docs/9.1/static/ textsearch-controls.html". [4] Bin Tan and Fuchun Peng. Unsupervised query segmentation using generative language models and wikipedia. In Proceedings of the 17th international conference on World Wide Web, pages 347–356. ACM, 2008. [5] Kien Tjin-Kam-Jet, Dolf Trieschnigg, and Djoerd Hiemstra. Using a stack decoder for structured search. In Flexible Query Answering Systems, pages 519–530. Springer, 2013. [6] KTTE Tjin-Kam-Jet, RB Trieschnigg, and Djoerd Hiemstra. A probabilistic approach for mapping free-text queries to complex web forms. 2012.

45

Appendix A Omschrijving zoekfunctionaliteit van CBG B Interview met 42 C Eerste vragenlijst D Tweede vragenlijst E SIG commentaar F Stamboompuzzels usertest G Database model

46

A

Appendix A - Omschrijving Zoekfunctionaliteit van CBG 25 maart 2013

A.1

Korte termijn [in zijn geheel hoge prioriteit]

Persoon Uitgebreid zoeken via apart zoekscherm (pop-up scherm; ter vervanging van de eenvoudige zoekregels?) met afzonderlijke invoerregels, gekoppeld aan de belangrijkste naamvelden in het scherm ’Persoon details’ : – voornaam. – tussenvoegsel. – achternaam. – patroniem. Er moet zowel op de afzonderlijke velden gezocht kunnen worden (bv. alleen achternaam), als op combinaties (bv. voornaam, patroniem, tussenvoegsel n achternaam; of alleen voornaam en achternaam). Bij het tussenvoegselveld moet de gebruiker de mogelijkheid hebben om specifiek te zoeken zonder tussenvoegsel: bv. via extra vinkje ’zonder tussenvoegsel’. Bij de uitgebreide zoekfunctie moet zowel de keuzemogelijkheid aanwezig zijn om in algemene zin te zoeken in alle publieke projecten van andere gebruikers, of heel specifiek in het huidige openstaande project (een geactiveerd project waar je zelf eigenaar van bent, of een publiek project van een andere gebruiker dat op dat moment al door jou wordt bezocht). Er wordt exact gezocht, tenzij de gebruiker aangeeft dat ook mag worden gezocht op synoniemen (varianten) of via jokers op delen van namen: – ? voor een enkele onbekende letter (met ’Jans?en’ wordt dan zowel op ’Janssen’ als ’Janszen’ gezocht). – * voor n of meer onbekende letters (met ’van der Ve*’ vind je dan ook ’van der Veen’, ’van der Veer’ en ’van der Velde’). 47

– voor synoniemen zal vermoedelijk gebruik gemaakt moeten worden van een synoniemenlijst, die door het CBG kan worden aangeleverd (zodat het programma weet dat ’Jan’ een variant is voor ’Johannes’ en ’Beeck’ een variant voor ’Beek’). Zoekresultaten worden alfabetisch geordend. Bij de zoekresultaten van een zoekopdracht in publieke projecten moet ook nog het probleem worden opgelost dat nu maximaal 4 pagina’s met zoekresultaten worden getoond (ook als het totaal aantal zoekresultaten meer pagina’s beslaat): ALLE pagina’s met zoekresultaten moeten worden getoond. Daarbij ook mogelijkheid creren om via een invoervakje direct naar het gewenste paginanummer te bladeren (zonder steeds op ’volgende’ te hoeven klikken); dat is vooral handig wanneer een zoekopdracht heel veel treffers oplevert. Tevens op basis van de uitgebreide zoekfunctie een mogelijkheid creren om het afschermen van privacygevoelige gegevens te vergemakkelijken: bv. er voor zorgen dat als een persoon in een stamboom door een gebruiker op niet-openbaar wordt gezet, automatisch ook zijn/haar partner en nakomelingen op niet-openbaar worden gezet.

A.2

Lange termijn [in zijn geheel lage prioriteit]

Bij de ontwikkeling van de uitgebreide zoekfunctie rekening houden met het feit dat in de toekomst (via het zelfde zoekscherm?) ook op de volgende zaken gezocht moet kunnen worden: Feit – feiten (=feittypes) [eventueel ook zoeken op bv. combinatie achternaam en feittype]. Van belang voor het zoeken naar beroepen, woonplaatsen, titels, testamenten, etc. Kan lastig zijn om te realiseren: je wilt namelijk niet alleen zoeken op het feittype ’beroep’, maar ook op de beroepsnaam die bij dat feittype is ingevoerd. Het zelfde geldt voor woonplaatsen, titels, testamenten, etc. Het wordt waarschijnlijk bemoeilijkt door het feit dat in het ene geval in het bijbehorende veld ’Notitie’ moet worden gezocht en in het andere geval in een aparte invoerregel waar een titel of opleiding wordt vermeld.

48

Bron – broninformatie [woorden uit het veld ’Inhoud’ in het scherm ’Broninformatie details’]. Van belang voor het zoeken naar informatie in bronbewerkingen die in StamboomNederland zijn ondergebracht. – bronnen [bronnamen, eventueel in combinatie met brontypes]. Notities – notities [woorden uit het veld ’Notitie’ in het scherm ’Persoon details’ en woorden uit het veld ’Notitie’ in het scherm ’Feit details’].3 Labels – labels die aan een bepaalde persoon, feit en/of bron zijn gekoppeld [bv. het label ’Christenslaaf’ in n van mijn eigen projecten]. Van belang omdat het om termen kan gaan die niet zo snel langs andere weg te vinden zijn. Lang niet iedere gebruiker zal echter labels aan zijn personen, feiten en/of bronnen hangen. ID-nummer – id-nummer [zal in de praktijk waarschijnlijk weinig gebruik van worden gemaakt, maar het kan in bepaalde gevallen handig zijn].

3

Het zoeken naar ’notities’ en ’broninformatie’ (bv. afschriften van archiefstukken) zal vooral in algemene zin worden gebruikt, zonder dat de zoekopdracht aan specifieke namen/personen uit een project is gekoppeld, maar misschien is het toch handig om t.z.t. de mogelijkheid te bieden een gecombineerde zoekopdracht te geven naar voornaam, patroniem, achternaam en/of notities/broninformatie (of een gecombineerde zoekopdracht naar alleen notities en broninformatie).

49

B

Appendix B - Interview Met 42

14 mei 2014 Dit interview is gehouden met 42 om de resultaten van query log te bespreken. Een week daarvoor is een log ge¨ımplementeerd om het zoek gedrag van de gebruikers te analyseren. De verwachting van het resultaat van 42 was dat mensen grotendeels alleen op achternaam en voornaam zoeken. Ze verwachtte niet dat mensen andere informatie in de zoekbalk zouden invoeren dan alleen de namen, terwijl het mogelijk is. Dit om het feit dat er via de website de gebruikers niet worden ge¨ınformeerd over de verschillende zoek mogelijkheden. De verwachting kwam overeen met de resultaten van de analyse van de query log. Een verrassing voor 42 was het aantal keren dat mensen gebruik maakte van initialen (bijv. M.D. Langezaal). Hieruit werd geconcludeerd dat de nieuwe zoekfunctionaliteit ook gebruik moet kunnen maken van initialen. Er zou een placeholder moeten komen of een info knop om aan de gebruikers duidelijk te maken wat de mogelijkheden zijn. Een placeholder is een stuk tekst wat in de zoekbalk komt en verdwijnt wanneer de gebruiker typt. Op basis van dit interview is een vervolg onderzoek gestart om een placeholder of infoknop te gebruiken om te kijken of het zoekgedrag van de gebruikers veranderen.

50

C

Appendix C - Eerste Vragenlijst

C.1

Introductie vragenlijst

Voor onze Bachelor stage bij 42 zijn wij bezig om de zoekfunctionaliteit van http://www.stamboomnederland.nl te verbeteren. Op deze website kunnen mensen stambomen maken om een overzicht te krijgen van hun hele familie. Op dit moment kunnen gebruikers alleen op naam, geboorte/sterfte datum en geboorte/sterf plaats zoeken. Bijv door in te typen: Pouja Harder” wijk”. Zou bovenaan de zoekresultaten een Pouja moeten komen te staan die geboren is in Harderwijk. Wij willen de beperkte zoekbar uitbreiden door de gebruiker de mogelijk te geven om door middel van natuurlijke taal te zoeken. Dus met het vorige voorbeeld zou het worden: Pouja die geboren is in Harderwijk”. ” Om een indruk te krijgen wat voor vragen mensen zouden stellen, hebben wij dit vragen formulier opgesteld. Er worden vier biografien gegeven van bekende personen, elk met drie vragen. De vraag is om door middel van natuurlijk taalgebruik deze personen op te zoeken.

C.2

Eerste Biografie

Albert Einstein (Ulm, 14 maart 1879 - Princeton (New Jersey), 18 april 1955) was een Duits-Zwitsers-Amerikaanse theoretisch natuurkundige en uitvinder. Hij wordt algemeen gezien als een van de belangrijkste natuurkundigen uit de geschiedenis, naast Isaac Newton en James Clerk Maxwell. Zelf noemde hij altijd Newton als een veel belangrijker natuurkundige dan hijzelf, omdat Newton anders dan Einstein behalve theoretische ook grote experimentele ontdekkingen deed. In het dagelijks leven is de naam Einstein synoniem geworden met grote intelligentie. Vragen: 1. Gegeven de biografie van de persoon hier boven. Hoe zou u zoeken naar deze persoon? Geef antwoord hoe u dit in de zoekbox zou invoeren dus bijvoorbeeld Albert Einstein”? ” 2. Hoe zou u zoeken als er meerdere personen zouden voorkomen met dezelfde naam? Wederom zoekopdracht uitschrijven zoals u deze zou invoeren, bijvoorbeeld: Albert Einstein geboren in 1879”? ” 3. Welke zoek opdracht zou u invullen als u de naam van de persoon niet mag gebruiken? Geef ook hier aan hoe u het daadwerkelijk zou

51

invoeren dus bijvoorbeeld Duitse Natuurkundige” of Natuurkundige ” ” geboren in 1879”

C.3

Tweede Biografie

Jan Pieter (roepnaam: Jan Peter) Balkenende (Biezelinge, 7 mei 1956) is een Nederlands CDA-politicus en was van 22 juli 2002 tot 14 oktober 2010 minister-president van Nederland. Balkenende groeide op in het dorp Biezelinge in de provincie Zeeland. Hij voltooide het atheneum aan het Christelijk Lyceum voor Zeeland in Goes en haalde aan de Vrije Universiteit Amsterdam het doctoraalexamen voor Geschiedenis en Nederlands recht. Zijn politieke carrire begon in Amstelveen, waar hij van 1982 tot en met 1998 gemeenteraadslid was. In deze periode promoveerde hij ook tot doctor in de rechtsgeleerdheid en werd hij (parttime) bijzonder hoogleraar christelijk sociaal denken aan de VU, een functie die hij tot zijn bediging als minister-president in 2002 vervulde. Vragen: 1. Gegeven de biografie van de persoon hier boven. Hoe zou u zoeken naar deze persoon? 2. Hoe zou u zoeken als er meerdere personen zouden voorkomen met dezelfde naam? 3. Welke zoek opdracht zou u invullen als u de naam van de persoon niet mag gebruiken?

C.4

Derde Biografie

Catharina-Amalia Beatrix Carmen Victoria, Prinses van Oranje, Prinses van Oranje-Nassau, Prinses der Nederlanden (Den Haag, 7 december 2003) is het oudste kind van koning Willem-Alexander der Nederlanden en koningin Mxima. Ze is sedert 30 april 2013 de eerste in lijn van troonsopvolging en wordt formeel aangeduid als Hare Koninklijke Hoogheid de Prinses van Oranje. De prinses heeft twee zusjes: prinses Alexia (2005) en prinses Ariane (2007). Vragen: 1. Gegeven de biografie van de persoon hier boven. Hoe zou u zoeken naar deze persoon? 2. Hoe zou u zoeken als er meerdere personen zouden voorkomen met dezelfde naam? 52

3. Welke zoek opdracht zou u invullen als u de naam van de persoon niet mag gebruiken?

C.5

Vierde Biografie

Jakob (Jaap) Stam (Kampen, 17 juli 1972) is een Nederlands voetbaltrainer en voormalig speler. Sinds het seizoen 2010/2011 is hij assistent-trainer bij PEC Zwolle. Begin januari 2013 maakte hij samen met trainer Art Langeler bekend dat het seizoen 2012/2013 hun laatste bij PEC Zwolle zou zijn. Tijdens zijn carrire als speler was Stam in Nederland actief voor FC Zwolle, Cambuur, Willem II, PSV en Ajax en daarbuiten voor Manchester United, Lazio en AC Milan. Hij won onder meer de Champions League, de Wereldbeker en diverse landstitels en nationale bekers. Stam speelde tussen 1996 en 2004 63 wedstrijden in het Nederlands Elftal en was actief op het EK 1996, WK 1998, EK 2000 en EK 2004. Vragen: 1. Gegeven de biografie van de persoon hier boven. Hoe zou u zoeken naar deze persoon? 2. Hoe zou u zoeken als er meerdere personen zouden voorkomen met dezelfde naam? 3. Welke zoek opdracht zou u invullen als u de naam van de persoon niet mag gebruiken?

53

D

Appendix D - Tweede Vragenlijst

D.1

Introductie Vragenlijst

Voor onze Bachelor stage bij 42 zijn wij bezig om de zoekfunctionaliteit van http://www.stamboomnederland.nl te verbeteren. Op deze website kunnen mensen stambomen maken om een overzicht te krijgen van hun hele familie. Op dit moment kunnen gebruikers alleen op naam, geboorte/sterfte datum en geboorte/sterf plaats zoeken. Bijv door in te typen: Pieter Hasse” laer 1651 amsterdam”. Zou bovenaan de zoekresultaten een Pieter Hasselaer moeten komen te staan die geboren is in 1651 in Amsterdam. Wij willen de beperkte zoekbar uitbreiden door de gebruiker de mogelijk te geven om door middel van natuurlijke taal te zoeken. Deze vragenlijst is bedoeld om een indruk te krijgen van wat voor zoekopdrachten mensen zouden invullen. Ga bij elke zoekopdracht ervan uit dat er meerdere personen met zelfde voor en/of achternaam voor zouden kunnen komen. Hoe zou u dan specifieker zoeken naar deze personen? Bijvoorbeeld voornaam achternaam, geboren in jaar, te plaats, dochter, zoon, broer of zus van, werkt als, uit/rond/tussen jaar, etc.

D.2

Vragen

Bij elke vraag werd er vermeld: Gebruik meer dan alleen voor en achter” naam, personen kunnen vaker dan n keer voorkomen. Als u het oncomfortabel vind u eigen of andermans naam te gebruiken, gebruik dan: [Naam1] [Naam2] etc.”. Na elke vraag konden mensen hun antwoord toelichten en aangeven hoe goed ze de persoon kende waar de vraag om ging. 1. Hoe zou u een zoekopdracht invoeren als u naar u zelf zou zoeken? 2. Hoe zou u een zoekopdracht invoeren als u naar n van u ouders zou zoeken? 3. Hoe zou u een zoekopdracht invoeren als u naar u neefje/nichtje zou zoeken? 4. Hoe zou u een zoekopdracht invoeren als u naar een voor u bekende Nederlander zou zoeken? 5. Hoe zou u een zoekopdracht invoeren als u naar de koningin van Nederland van honderd jaar geleden zou willen zoeken?

54

6. Hoe zou u de zoekopdracht uitvoeren als u iemand zou zoeken waar u de achternaam niet van weet? 7. Hoe zou u de zoekopdracht uitvoeren als u zoekt naar Sven Kramer? 8. Hoe zou u een zoekopdracht uitvoeren om Willem Alexander te vinden?

55

E E.1

Appendix F - SIG Commentaar Aanbevelingen

De code van het systeem scoort 3 sterren op ons onderhoudbaarheidsmodel, wat betekent dat de code gemiddeld onderhoudbaar is. De hoogste score is niet behaald door een lagere score voor Unit Size, Unit Complexity en Component Independence. Voor Unit Size wordt er gekeken naar het percentage code dat bovengemiddeld lang is. Het opsplitsen van dit soort methodes in kleinere stukken zorgt ervoor dat elk onderdeel makkelijker te begrijpen, te testen en daardoor eenvoudiger te onderhouden wordt. Binnen de langere methodes in dit systeem, zoals bijvoorbeeld de createQueryString”-methode binnen de ” AdvancedSearch”-class, zijn aparte stukken functionaliteit te vinden welke ” ge-refactored kunnen worden naar aparte methodes. Aparte stukken code binnen de ifs” zijn een goede indicatie dat er een autonoom stuk functiona” liteit te ontdekken is. Het is aan te raden kritisch te kijken naar de langere methodes binnen dit systeem en deze waar mogelijk op te splitsen. Voor Unit Complexity wordt er gekeken naar het percentage code dat bovengemiddeld complex is. Ook hier geldt dat het opsplitsen van dit soort methodes in kleinere stukken ervoor zorgt dat elk onderdeel makkelijker te begrijpen, makkelijker te testen en daardoor eenvoudiger te onderhouden wordt. In dit geval komen de meest complexe methoden ook naar voren als de langste methoden, waardoor het oplossen van het eerste probleem ook dit probleem zal verhelpen. Voor Component Independence wordt er gekeken naar de hoeveelheid code die alleen intern binnen een component wordt gebruikt, oftewel de hoeveelheid code die niet aangeroepen wordt vanuit andere componenten. Hoe hoger het percentage code welke vanuit andere componenten wordt aangeroepen, des te groter de kans dat aanpassingen in een component propageren naar andere componenten, wat invloed kan hebben op toekomstige productiviteit. In dit geval valt met name op dat vrijwel alle code uit het services” ” component in andere componenten gebruikt wordt. Dit component lijkt dan ook andere functionaliteiten dan services” te bevatten, zoals bijvoorbeeld ” de domein-modellen. Het is aan te raden de componenten structuur en de naamgeving nogmaals kritisch te bekijken. Over het algemeen scoort de code gemiddeld, hopelijk lukt het om dit niveau te behouden tijdens de rest van de ontwikkelfase. De aanwezigheid van test-code is in ieder geval veelbelovend, hopelijk zal het volume van de testcode ook groeien op het moment dat er nieuwe functionaliteit toegevoegd

56

wordt.

E.2

Hermeting

In de tweede upload zien we dat de omvang van het systeem is gestegen (met 139%) en dat daarbij de score voor onderhoudbaarheid gelijk is gebleven. Wat betreft de Unit Size zien we dat de genoemde ’createQueryString’ methode is aangepakt, wat voor kortere methoden heeft gezorgd. Daarintegen zien we dat er enkele langere methoden zijn toegevoegd (bijvoorbeeld ’createRoleQuery’ in de ’RolesQuery’-class), hier had dezelfde refactoring plaats kunnen vinden. Bij de componenten valt op dat er een extra component genaamd ’domain’ is toegevoegd met daarin de enkele class ’FieldName’. Hier lijkt een begin gemaakt te zijn met een nieuwe indeling, maar gegeven dat het ’services’ component nog steeds 58% van de code bevat lijkt deze refactoring nog niet volledig doorgevoerd te zijn. Uit deze observaties kunnen we concluderen dat de aanbevelingen van de vorige evaluatie deels zijn meegenomen in het ontwikkeltraject. Het is goed om te zien dat de hoeveelheid test-code ongeveer evenveel is gestegen als de hoeveelheid productie-code.

57

F

Appendix G - Stamboompuzzels Usertest

Hieronder zijn de twee volledige stambomen te zien die gebruikt zijn bij de usertest.

Figuur 12: Stamboom puzzel 1

58

Figuur 13: Stamboom puzzel 2 De twee stambomen hieronder zijn de stambomen die de testpersonen kregen en waar enkele gegevens weggehaald zijn.

Figuur 14: Lege stamboom puzzel 1

59

Figuur 15: Lege stamboom puzzel 2

60

G

Appendix G - Database Model

Een gedeelte van het database model van StamboomNederland. Alleen de tabellen die gebruikt worden door de zoekfunctionaliteit zijn weergegeven.

61

62